JP5143203B2 - メモリシステム - Google Patents

Description

実施形態は、メモリシステムに関する。

大容量のデータを記憶して利用するメモリとして三次元化が容易な抵抗変化型メモリ（ＲｅＲＡＭ）などが注目されている。しかし、どのようなセルが用いられている場合であっても、大容量化にはセルの状態をいくつかのレベルで細分化し、複数のビットを一つのセルに押し込むことが有効である。これについては、ＮＡＮＤ型フラッシュメモリにその例を見ることができる。

但し、このような多値記憶セルを用いた場合、セルの状態の設定の不安定性によって誤読み書きが生じ易くなる。これはレベル数を増やす事とトレードオフの関係にある。そのため、ＮＡＮＤ型フラッシュメモリの場合、せいぜい８や１６レベルに留まるばかりでなく、データとレベルとの対応も煩雑であった。

特開２００９−１８１４３９号 ＷＯ２００８−０９９７２３号

実施形態は、データの信頼性が高い多値記憶セルを用いたメモリシステムを提供することを目的とする。

本実施形態に係るメモリシステムは、ｐ（ｐは３以上の素数）以上の物理量レベルを持つセルユニットからなるセルアレイと、バイナリ表現の入力データを、ｐの剰余体であるＺｐの要素で表現された書き込みコードに変換するコード生成部と、Ｚｐの各要素をそれぞれ異なる前記物理量レベルに対応させて前記セルユニットに前記書き込みコードを書き込むコード書き込み部とを備え、前記入力データをｐ−１個の前記セルユニットに記録する場合において、これらｐ−１個の前記セルユニットのうち、前記入力データが０の場合と、１ビットのみが１の場合で、同一の物理量レベルに書き込まれるセルユニットはないことを特徴とする。

実施形態に係るメモリシステムのビットエラーとコードエラーとの関係を示す図である。 本実施形態に係るメモリシステムの概略図である。 本実施形態に係るメモリシステムのバイナリデータ及びコードデータの構成を示す図である。 本実施形態に係るメモリシステムのバイナリからｐ進数への変換過程の一部を示す図である。 本実施形態に係るメモリシステムのｐ進数への変換回路の構成を示す図である。 本実施形態に係るメモリシステムの“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックの回路図である。 本実施形態に係るメモリシステムの全加算器の回路記号を示す図である。 本実施形態に係るメモリシステムの全加算器の回路図である。 本実施形態に係るメモリシステムの半加算器の回路記号を示す図である。 本実施形態に係るメモリシステムの半加算器の回路図である。 本実施形態に係るメモリシステムの“Ｘ ｔｏ ｐ”回路ブロックの構成を示す図である。 本実施形態に係るメモリシステムの“Ｘ ｔｏ ｐ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｐ−ａｄｉｃ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｐ−ａｄｉｃ”回路ブロックのブロック図である。 本実施形態に係るメモリシステムの“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路のブロック図である。 本実施形態に係るメモリシステムの“Ｄ−ｒ”レジスタの回路図である。 本実施形態に係るメモリシステムの“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路を制御するクロックのタイミングチャートである。 本実施形態に係るメモリシステムのｐ進数からバイナリへの変換過程の一部を示す図である。 本実施形態に係るメモリシステムの２^ｈ進数への変換回路の構成を示す図である。 本実施形態に係るメモリシステムの“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックの回路図である。 本実施形態に係るメモリシステムの“ａ ｔｏ Ｘ”回路ブロックの構成を示す図である。 本実施形態に係るメモリシステムの“ａ ｔｏ Ｘ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｐ ｔｏ Ｘ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｐ ｔｏ Ｘ”回路ブロックのブロック図である。 本実施形態に係るメモリシステムの“ｂｉｎａｒｙ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｂｉｎａｒｙ”回路ブロックのブロック図である。 本実施形態に係るメモリシステムの“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路のブロック図である。 本実施形態に係るメモリシステムの“Ａ−ｒ”レジスタの回路図である。 本実施形態に係るメモリシステムのタイミング信号発生回路の動作概念図である。 本実施形態に係るメモリシステムのクロックを生成するフリップフロップ回路の回路図である。 本実施形態に係るメモリシステムのタイミング信号発生回路の回路図である。 本実施形態に係るメモリシステムのｐ−ａｄｉｃセルへのＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのｐ−ａｄｉｃセルからの読み出し方法を説明する図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルで表示可能な素数を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルへのＺｐの割り付け方を説明する図である。 図３７に示す割り付け方の効果を説明する図である。 図３７に示す割り付け方の効果を説明する図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルに対するＺｐの割り付け例を示す図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルの対応可能なリー・メトリックを説明する図である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルからの読み出し方法を説明する図である。 本実施形態に係るメモリシステムのｐ−ａｄｉｃセルのレベル数毎のパフォーマンスを示す表である。 本実施形態に係るメモリシステムのペアｐ−ａｄｉｃセルのレベル数毎のパフォーマンスを示す表である。 本実施形態に係るメモリシステムのデータ／コードの変換手順のフローチャートである。 本実施形態に係るメモリシステムのデータ／コードの変換手順のフローチャートである。 本実施形態に係るメモリシステムのデータ／コードの変換手順のフローチャートである。 本実施形態に係るメモリシステムのブロック図である。 本実施形態に係るメモリシステムのエンコード部の回路構成例を示す図である。 本実施形態に係るメモリシステムの“Ｘ Ｚｐ”回路ブロックにおける積演算処理を模式的に示した図である。 本実施形態に係るメモリシステムの“Ｘ Ｚｐ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“Ｘ Ｚｐ”回路ブロックのブロック図である。 本実施形態に係るメモリシステムの“Ｘ Ｚｐ”回路ブロックの演算処理を模式的に示した図である。 本実施形態に係るメモリシステムの“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックの回路図である。 本実施形態に係るメモリシステムの“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックのブロック図である。 本実施形態に係るメモリシステムの“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックのブロック図である。 本実施形態に係るメモリシステムのシンドロームの構成要素を求める演算回路のブロック図である。 本実施形態に係るメモリシステムの解探索多項式を求める演算回路のブロック図である。 本実施形態に係るメモリシステムのハッセ（Ｈａｓｓｅ）微分多項式の係数を求める演算回路のブロック図である。 本実施形態に係るメモリシステムの解探索多項式の根及びその多重度を求める演算回路のブロック図である。 本実施形態に係るメモリシステムの素数とその逆元及び階乗の対応を示す表である。 本実施形態に係るメモリシステムの“ｊ^−１ ｄｅｃ”回路ブロックとして利用可能なデコーダ回路の回路図である。 本実施形態に係るメモリシステムの“ｈ ｂｉｔ ＬＭｐ”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“ｈ ｂｉｔ ＬＭｐ”回路ブロックのブロック図である。 本実施形態に係るメモリシステムのエラーコードのリー・メトリックを求める演算回路のブロック図である。 本実施形態に係るメモリシステムのＣ＝ＡＧからＡ＝ＣＧ^−１を求める演算回路のブロック図である。 本実施形態に係るメモリシステムの“（ｊ）^−１（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックの回路記号を示す図である。 本実施形態に係るメモリシステムの“（ｊ）^−１（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックのブロック図である。

［実施形態の概要］
メモリシステムは、加工の微細化の他、メモリセルに用いる物理現象やセルアレイ部分の三次元構造化などの工夫によって記憶容量密度の増大を成し遂げている。これに加え、安定した製造工程が達成された後の記憶容量密度の向上には、メモリセルの持つ物理量を複数のレベルに区分し、メモリセルを多値記憶化させる事が有効な手段となる。

しかし、微細化された多値記憶セルの場合、データ書き込みに関しては、本来書き込むべきレベルの隣接レベルに誤ってデータを書き込む誤書き込みや、データ読み出しに関しては、メモリセルが記憶しているレベルの隣接レベルに対応したデータであるとして誤ったデータを読み出す誤読み出しが生じやすくなる。また、データ保持に関しても、隣接レベル間における状態遷移が生じ易くなる。

このようにメモリセルの多値記憶化は、状態の安定性を損なうため、かなりの制限があった。このメモリセルの多値記憶化の欠点を克服して、有効に活用できれば、安定したメモリシステムの製造工程を長期に亘って利用でき、記憶容量の高密度化を達成することができる。

そこで、本実施形態に係るメモリシステムでは、リー・メトリック・コード（Ｌｅｅ ｍｅｔｒｉｃ ｃｏｄｅ）を用いたＥＣＣ（Ｅｒｒｏｒ Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅ）システムを搭載している。

リー・メトリック・コードを用いたＥＣＣシステムでは、エラーのトータル数でデータの訂正を行うため、小さなレベル変化を伴うエラーが生じた場合には多くのセル数を訂正することができる。この点、上記のような隣接レベル間のエラーに対しては有効である。一方、大きなレベル変化を伴うエラーについても、エラーのトータル数の範囲内であればエラーの訂正が可能であるため、広範囲なエラー分布に対応することができる。

ここで、１セルに多値を記憶させる場合、各レベルを基底レベルからの高さとして捉えることができるため、本来であれば、バイナリで情報をデジタル化するよりも、有限整数、特に素数で情報をデジタル化することが望ましい。そこで、本実施形態では、素数ｐを要素とする剰余体Ｚｐ（以下、単に「Ｚｐ」と呼ぶ）によるリー・メトリック・コードを用いる。

この場合、メモリシステムの外部では、通常、データは、バイナリで取り扱われるため、バイナリからＺｐへの変換が必要となる。そこで、以下では、効率的なオンチップＥＣＣシステムを搭載したメモリシステムを実現するために、バイナリからＺｐへの表現変換とリー・メトリック・コードを用いたＥＣＣのための具体的な回路について言及する。ここで、これら変換回路を構成するトランジスタはスイッチとして機能するため、データの表示と演算はあくまでバイナリを基本としている点に注意を要する。

なお、入力されるバイナリデータとメモリセルに記憶されるｐ進数のコードは線形の関係にないため、変換回路においてはバイナリデータとｐ進数のコードの対応を勝手に設定することができる。そのため、変換回路をロックした場合、メモリセルが記憶するｐ進数のコードからバイナリデータを逆読みすることは困難であり、この点においてメモリシステムのセキュリティ強化を図ることも可能である。

従来用いられるメモリセルでは、データをバイナリの‘１’、‘０’として記憶する。そのため、リー・メトリック・コードのようなＺｐの数を直接扱う場合には予め数を２進数にしてから各桁をメモリセルに記憶する必要がある。

そこで、エラーが生じたコード語とエラー量との関係に関して、メモリシステムのメモリセルがビット単位で情報を記憶する場合におけるコードとしてのエラー量とメモリセルのビットエラーとの関係について図１を用いて説明する。

図１に示すように、Ｚｐの数ｎ個で構成されるコードをＣ＝（ｃ_１，ｃ_２，ｃ_３，・・・，ｃ_ｎ−１，ｃ_ｎ）、このＣをメモリシステムに記憶する際などに生じたコードエラーをＥ＝（ｅ_１，ｅ_２，ｅ_３，・・・，ｅ_ｎ−１，ｅ_ｎ）、Ｃの各成分ｃがＥによって変化した後の語をＹ＝（ｙ_１，ｙ_２，ｙ_３，・・・，ｙ_ｎ−１，ｙ_ｎ）とする。

Ｃはメモリシステム内ではバイナリとして記憶されるので、メモリセルに生じたビットエラーはその生じた場所によってＥとしての量が異なってくる。

ここで、Ｚｐの各数がｈビットのバイナリで表示されるとして考える。どのメモリセルにも同じように生じるビットエラーがリー・メトリック・コードのコードエラーに対応し、その量はＥとなる。

コード語をｈビットのバイナリで表すので２^０の位置の１ビットエラーはコード語では±１のエラー量（Ｚｐでは１またはｐ−１の変化）となり、２^ｈ−１の位置での１ビットエラーは±２^ｈ−１（ｍｏｄ ｐ）のエラー量となる。このようにメモリセルの位置によってコードエラーへの重みが異なることになる。したがって、全てのメモリセルのビットエラーのパターンに対応するためには、コード語の全てのエラー量に対応できる必要がある。

コード語を上記のようにバイナリに直してメモリシステムに記憶した場合、メモリシステムのメモリセルの構成はどの様なものでも対応できる。しかし、上記のように、リー・メトリック・コードを用いたＥＣＣでは、総エラー量Σｅ_ｊ（ｊ＝１〜ｎ）が所定の値未満でないと、エラー訂正ができない。つまり、エラーが生じたメモリセルの位置によってはエラー訂正できない場合があり、この点において、バイナリでメモリセルに記憶させた場合、全てのメモリセルに均等に対応することができない。

以上から、リー・メトリック・コードを用いる場合、従来のように、バイナリデータをメモリセルに記憶することは適当ではない。そこで、本実施形態では、メモリセルの状態、つまりトランジスタの閾値や抵抗素子の抵抗値を複数のレベルに分割したいわゆる多値レベルセルに対し、各レベルにＺｐの数をそのまま対応させて記憶する。これによって、上記不具合を解消することができる。以下において、リー・メトリック・コードなどＺｐの数を直接記憶する多値レベルセルを「ｐ−ａｄｉｃセル」と呼ぶ事もある。また、ｐ−ａｄｉｃセルを用いたメモリシステムを「ｐ−ａｄｉｃメモリシステム」と呼ぶ事もある。

次に、Ｚｐの数をデータとして扱うｐ−ａｄｉｃメモリシステムの概要について図２を用いて説明する。

以下では、ｐ−ａｄｉｃメモリシステム外にあるＩＴ機器などバイナリでデータを取り扱う環境を「ｂｉｎａｒｙ ｗｏｒｌｄ」と呼ぶことにする。これに対し、演算処理などバイナリのデータを取り扱う部分も含め、データをＺｐで取り扱うｐ−ａｄｉｃメモリシステム内の環境を「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」と呼ぶことにする。この場合、「ｂｉｎａｒｙ ｗｏｒｌｄ」は、「ｐ−ａｄｉｃ Ｚ_２ ｗｏｒｌｄ」と呼ぶこともできる。

本実施形態に係るメモリシステムは、「ｂｉｎａｒｙ ｗｏｒｌｄ」と「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」とのインタフェースとして、バイナリのデータをＺｐのデータに変換する“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路と、Ｚｐのデータをバイナリのデータに変換する“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路とを有する。

「ｂｉｎａｒｙ ｗｏｒｌｄ」（外部）のデータは、“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路を介して「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」（メモリシステム）に入力される。メモリシステム内部では、データをＺｐの数のままｐ−ａｄｉｃセルに記憶する。このようにデータをＺｐの数で記録することによって、リー・メトリック・コードを用いたＥＣＣの処理が容易になる。ＥＣＣによってエラー処理されたＺｐのデータは、“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路を介して「ｂｉｎａｒｙ ｗｏｒｌｄ」に出力される。

このように、メモリシステムに“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路及び“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路を設けることで、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」を意識することなく、ｐ−ａｄｉｃメモリシステムを「ｂｉｎａｒｙ ｗｏｒｌｄ」で取り扱うことができる。

［バイナリデータからＺｐデータへの変換］
次に、“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路の具体的な回路構成を説明する前提として、バイナリデータからＺｐデータへの変換原理について説明する。

Ｚｐ＝ＧＦ（ｐ）（「ＧＦ」は、ガロア体の意味であり、「ＧＦ（ｐ）」は、整数を素数ｐで除算した余りの集合となる）を用いる場合、ｐは当然のことながら２の累乗では表せないため、ＧＦ（２^ｎ）を用いる場合とは違ってデータのビットパターン全てをコードとしてそのまま用いることはできない。そこで、データの全てのビットパターンをＺｐの要素で１対１に表す変換が必要となる。

ここで、Ｚｐの要素は０〜ｐ−１の整数で代表され、これらの整数は全て、ｈビットのバイナリで表すことができるものとする。このときｈビットの全てのビットパターンが使われるわけではないため、バイナリのｈビットのデータをそのままＺｐの要素として扱うわけにはいかない。

つまり、図３中（Ａ）に示すように、「ｂｉｎａｒｙ ｗｏｒｌｄ」からメモリシステムに与えられる一まとまりのデータＤをｈビットずつに区切り、ｎ個の集まり、すなわち２^ｈ進数でｎ桁のデータＤ＝（ｄ_０，ｄ_２，・・・，ｄ_ｎ−１）として見る。この場合、各桁には、２^ｈ−１以下の数でｈビットのビットパターンの全てが出現することになる。

一方、図３中（Ｂ）に示すようにｎ語長のＺｐ表現のコードＣ＝（ｃ_０，ｃ_２，・・・，ｃ_ｎ−１）では、ｈとｐの間にｃ_ｊ＜ｐ＜２^ｈの関係が成立する場合、ｈビットの全てのビットパターンを利用しない。

次に、データＤとコードＣが１対１で対応する変換について考えるが、これは２^ｈ進数からｐ進数への表現の変換に相当する。この変換の条件について検討し、素数ｐの選択条件のいくつかを限定する。

１つ目の条件として、バイナリのデータＤをδ桁の２^ｈ進数として扱うための条件について説明する。

一括で処理するバイナリのデータＤのビット数をＭ＝δｈとする。この場合、Ｄには、ｈビットの組がδ個あることになる。これら各組が２^ｈ進数の各桁を表すと考えると、Ｄは、δ桁の２^ｈ進数と見ることができる。

つまり、ＭビットのデータＤの全てのビットパターンは、このようなδ桁数の表示と考えることができる。この表示をＺｐの要素へ変換して、リー・メトリック・コードとして構成できるようにする。即ち、δ桁の２^ｈ進数をｐ進数に変換し、ｐ進数の各桁の数をＺｐのデータとする。

そこで、この変換に最適なｐを検討する。

２^ｈ進数からｐ進数への変換の不変量として、Ｍビットよりなり、１桁当たりｈビットで表わすことができるδ桁の２^ｈ進数の整数Ｄ（ｈ）を用いる。つまり、Ｄ（ｈ）は数１のように表すことができる。

［数１］

数１において、ｄ_０、ｄ_１、・・・、ｄ_δ−３、ｄ_δ−２、ｄ_δ−１は、ｈビットのまとまりが表すデータである。

ここで、Ｄ（ｈ）の形で表現できる数の最大数、最小数をｐ進数にした場合、各桁の数の表示がｈビットのバイナリで表わされるｐを見つける。その際の条件として、２^ｈ進数からｐ進数に変換した場合の桁数の増加量は最大１桁とする。つまり、ｐ進数にした後の桁数を最大δ＋１桁までとする。

また、Ｄ（ｈ）は、ｈビットのまとまりのバイナリ表示をａ_０、ａ_１、・・・、ａ_δ−２、ａ_δ−１、ａ_δとすると、数２のように表わすことができる。

［数２］

ここで、Ｄ（ｈ）の形式が普遍的に構成できるδとｈの関係を求める。即ち、最低でもδ桁の表現がｈの選択によって可能なＤ（ｈ）の最小数Ｄ_ｍｉｎ（ｈ）、最大数Ｄ_ｍａｘ（ｈ）は、数３のようになる。

［数３］

従って、最小数Ｄ_ｍｉｎ（ｈ）−１は、δ−１桁となるため、Ｄ（ｈ）の形式でなくなってしまう。そこで、ｈ−１ビットのまとまり、即ち、２^ｈ−１進数でできる最大数Ｄ_ｍａｘ（ｈ−１）を考慮すると、Ｄ_ｍｉｎ（ｈ）−１≧Ｄ_ｍａｘ（ｈ−１）になる場合、Ｄ（ｈ）の表現としてδ桁よりも下回ることはない。

即ち、タＤ（ｈ）がδ桁の２^ｈ進数表現以外に成立しないためのδとｈの条件は、数４のような関係となる。

［数４］

２つ目の条件として、数５に示すように、データＤをδ＋１桁のｐ進数表現で扱える条件を説明する。

［数５］

数５から、全て整数であるため、データＤをδ＋１桁のｐ進数表現で扱える条件は、数６のようになる。

［数６］

即ち、数７のように表わすことができる。

［数７］

更に、δ／（δ＋１）＝（１−１／δ）／（１−（１／δ）^２）＞１−１／δ＞１−１／ｈ（ｈ≦δ）及びｐが素数であることから、素数ｐの選択条件は、数８のようになる。

［数８］

ちなみに、このときδ桁のｐ進数の最小値ｐ^δ−１に対して、
［数９］

が成立するため、ｐ進数変換後のデータＤがδ−１桁になることはない。

以上、数８に示す条件で素数ｐを選択すれば、２^ｈ進数からｐ進数への変換で桁数の増加を最大１に抑えることができる。

次に、データとして等価な「ｂｉｎａｒｙ ｗｏｒｌｄ」のδ桁の２^ｈ進数Ｄ（ｄ_０，ｄ_１，・・・，ｄ_δ−１）から「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」のδ＋１桁のｐ進数Ｄ（ａ_０，ａ_１，・・・，ａ_δ−１ ，ａ_δ）への変換の原理を説明する。

始めに、ｈビットの２進数に注目してこれを数Ａとする。数Ａは、数１０のようになる。

［数１０］

また、ｈビットの素数ｐの選択条件は、数８の通りである。

ここで、ｄ_ｈ−１＝１と置くと、２^ｈ−１≦Ａ＜２^ｈなので、数１１のような関係が成立する。

［数１１］

数１１において、０≦Ａ−ｐの場合、剰余の２^ｈ−１の係数は０になるため、剰余は、ｈ−１ビットのＺｐの数になる。

また、ｄ_ｈ−１＝０と置くと、Ａ＜ｐなのでＡはＺｐの数そのものになる。したがって、Ａ−ｐ＜０からＡ−ｐ≦−１となり、更に、（２Ａ＋１）−２ｐ≦−１となる。

つまり、ｈビットの２進数には、数８に示す素数ｐの選択条件から、ｐがたかだか１つしか含まれない。更に、剰余などのＺｐの数は、これを２倍して１を足しても、ｐがたかだか１つしか含まれない。したがって、ｈ＋１ビットのバイナリに対してｐを引く操作を繰り返して、ｐの引ける数を数えて行くと、含まれるｐの個数のバイナリ表現を直接得ることができる。

図４は、バイナリからｐ進数への変換過程の一部を示す図であり、ｐ進数の重みｐ^０の桁（最下位桁）の係数を求めるための計算過程となる。

バイナリのＡは、図４中の式Ｅ１（＝Ｃ_０２^０＋Ｃ_１２^１＋・・・＋Ｃ_ｈ−１２^ｈ−１+Ｃ_ｈ２^ｈ＋・・・＋Ｃ_ｊ−ｈ２^ｊ−ｈ＋Ｃ_{ｊ−ｈ＋１}２^{ｊ-ｈ＋１}＋・・・＋Ｃ_ｊ−１２^ｊ−１＋Ｃ_ｊ２^ｊ）で表わすことができる。

始めに、図４中Ｓ１で示すように、式Ｅ１のうち２^ｊの重みを持つ最上位の桁からｈ桁分、つまり、２^{ｊ−ｈ＋１}〜２^ｊの重みを持つ桁に対応する式Ｅ２（＝Ｃ_{ｊ−ｈ＋１}２^{ｊ−ｈ＋１}＋・・・＋Ｃ_ｊ−１２^ｊ−１＋Ｃ_ｊ２^ｊ）をｐ２^{ｊ−ｈ＋１}で割って、商Ｃ^ｋ＋１ _{ｊ−ｈ＋１}及び剰余（Ｒ^ｋ _０＋・・・＋Ｒ^ｋ _ｈ−２２^ｈ−２＋Ｒ^ｋ _ｈ−１２^ｈ−１）２^{ｊ−ｈ＋１}を求める。

続いて、図４中Ｓ２で示すように、式Ｅ２をｐ２^{ｊ−ｈ＋１}で割った剰余と、式Ｅ１のうち２^ｊ−ｈの重みを持つ桁に対応する項Ｃ_ｊ−ｈ２^ｊ−ｈとを足した式Ｅ３（＝（Ｃ_ｊ−ｈ＋２（Ｒ^ｋ _０＋・・・＋Ｒ^ｋ _ｈ−２２^ｈ−２＋Ｒ^ｋ _ｈ−１２^ｈ−１））２^ｊ−ｈ）をｐ２^ｊ−ｈで割って、商Ｃ^ｋ＋１ _ｊ−ｈ及び剰余（Ｒ^ｋ−１ _０＋・・・＋Ｒ^ｋ−１ _ｈ−２２^ｈ−２＋Ｒ^ｋ−１ _ｈ−１２^ｈ−１）２^ｊ−ｈを求める。

以降、図４中Ｓ２と同様の計算に桁をずらしながら繰り返し、最後に、式Ｅ４（＝Ｃ_０２^０＋２（Ｒ^１ _０＋・・・Ｒ^１ _ｈ−２２^ｈ−２＋Ｒ^１２^ｈ−１））２^０）をｐ２^０で割って、商Ｃ^ｋ＋１及び剰余（Ｒ^０ _０＋・・・＋Ｒ^０ _ｈ−２２^ｈ−２＋Ｒ^０ _ｈ−１２^ｈ−１）２^０を求める。

これら一連の計算によって、素数ｐの総数は２の累乗の最上位からＣ^ｋ＋１ _{ｊ−ｈ＋１}２^{ｊ−ｈ＋１}、Ｃ^ｋ＋１ _ｊ−ｈ２^ｊ−ｈ、・・・のように求めることができる。ここで、素数ｐの個数の最上位が元々の式Ｅ１の最上位２^ｊに対してｈ−１だけ指数の小さい２^{ｊ−ｈ＋１}になっていることに注意する。つまり、ｈビットのｐ進数の係数を得たときに、素数ｐの総数のバイナリ表現は、ｈ桁ではなく、ｈ−１桁だけ減るのである。最終的に得られるｐ２^０の係数Ｃ^ｋ＋１ _０を求める際の剰余（Ｒ^０ _０＋Ｒ^０ _１２＋・・・＋Ｒ^０ _ｈ−２２^ｈ−２＋Ｒ^０ _ｈ−１２^ｈ−１）２^０がＺｐの数であり、ｐ進数の重みｐ^０の桁の係数となる。

更に、以上の計算ステップで得られたｐの個数のバイナリ表現のＣ^ｋ＋１ _ｍを新たなデータとし、図４と同様の計算ステップを繰り返すと、ｐ進数の重みｐ^１の桁の係数Ｒ^ｈ _０＋Ｒ^ｈ _１２＋・・・＋Ｒ^ｈ _ｈ−２２^ｈ−２＋Ｒ^ｈ _ｈ−１２^ｈ−１が得られる。

以降、同様の計算ステップを繰り返すことで、ｐ進数の各桁の係数を順次求めることができる。

つまり、バイナリデータに含まれる素数ｐの数え上げをする回路は、ｈ＋１ビットのバイナリのデータを素数ｐで割った剰余を求める回路をラダーにすることで構成するできることが分かる。

図５は、「ｂｉｎａｒｙ ｗｏｒｌｄ」のδ桁の２^ｈ進数Ｄ（ｄ_０，ｄ_１，・・・，ｄ_δ−１）から「ｐ−ａｄｉｃ Ｚｐ ｍｏｄ ｐ ｗｏｒｌｄ」のδ＋１桁のｐ進数Ｄ（ａ_０，ａ_１，・・・，ａ_δ−１，ａ_δ）への変換計算の過程の構成を模式的に示した図である。

なお、図５に示す“ｈ ｒｅｓ”と示した四角は、入力されたバイナリデータを素数ｐで割り、商と剰余を求める演算回路である。この演算回路の入力はｈ＋１ビットのバイナリデータであり、出力はこのバイナリデータを素数ｐで割った剰余となる。また、入力されたバイナリデータが素数ｐ以上の場合、商をキャリーＣとして出力する。以下、この演算回路素子を“ｈ ｒｅｓ”回路ブロックと呼ぶ。

始めに、第０ステップ（図５中Ｓ０）では、δ桁の２^ｈ進数のデータＤ（ｄ_０，ｄ_１，・・・，ｄ_δ−１）に対して最右側のｄ_δ−１側から素数ｐの数え上げを行う。ここでは、ｄ_δ−１に対して、“ｈ ｒｅｓ”回路ブロックに入力されたｈ＋１ビットのバイナリデータの最上位ビットに０を入れてｄ_δ−１を素数ｐで割った剰余と共に商であるキャリーＣ^１ _{ｈ（δ−１）}を直接生成する。

続いて、ｈ〜１ビット目が先の“ｈ ｒｅｓ”回路ブロックの出力（ｈビットで表現された剰余）、０ビット（最下位ビット）目がｄ_δ−２の最上位ビットＤ^δ−２ _ｈ−１（＝Ｄ_{ｈ（δ−２）−１}）であるｈ＋１ビットのバイナリデータを入力とする次のｈ ｒｅｓ回路によって、入力されたバイナリデータを素数ｐで割った剰余と共に商であるキャリーＣ^１ _{ｈ（δ−１）−１}を作る。

以降、“ｈ ｒｅｓ”回路ブロックに入力されるｈ＋１ビットのバイナリデータのうちの０ビット目がｄ_０の最下位ビットＤ^０ _０（＝Ｄ_０）になるまで、ｈ（δ−１）＋１個の“ｈ ｒｅｓ”回路ブロックを用いてキャリーＣ^１ _０〜Ｃ^１ _{ｈ（δ−１）}を生成する。これら生成されたキャリーＣ^１ _０〜Ｃ^１ _{ｈ（δ−１）}によって表現されるバイナリデータは、データＤに含まれる素数ｐの個数になっている。

そして、ｄ_０を入力とする“ｈ ｒｅｓ”回路ブロックの出力が、δ＋１桁のｐ進数Ｄ（ａ_０，ａ_１，・・・，ａ_δ−１ ，ａ_δ）のうち、ａ_０のバイナリ表示になる。

続いて、第１ステップ（図５中Ｓ１）では、第０ステップで得られたデータＤに含まれる素数ｐの個数に対して、更に素数ｐがいくつ含まれるかを計算してｐ^２の個数を求め、ｐ進数Ｄの重みｐ^１の桁の係数ａ_１のバイナリを求める。

第１ステップでは、キャリーＣ^１ _０〜Ｃ^１ _{ｈ（δ−１）}に対して最右側のＣ^１ _{ｈ（δ−１）}側から素数ｐの数え上げを行う。キャリーＣ^１ _{ｈ（δ−２）＋１}〜Ｃ^１ _{ｈ（δ−１）}に対する素数ｐの数え上げに際しては、ｈ＋１ビットの入力バイナリデータの最上位ビットに０を入れて入力バイナリデータを素数ｐで割った剰余と共にキャリーＣ^２ _{ｈ（δ−２）＋１}を直接生成する。

続いて、ｈ〜１ビット目が先の“ｈ ｒｅｓ”回路ブロックの出力（ｈビットで表現された剰余）、０ビット（最下位ビット）目がＣ^１ _{ｈ（δ−２）}であるｈ＋１ビットのバイナリデータを入力とする次の“ｈ ｒｅｓ”回路ブロックによって、入力されたバイナリデータを素数ｐで割った剰余と共に商であるキャリーＣ^２ _{ｈ（δ−２）}を生成する。

以降、“ｈ ｒｅｓ”回路ブロックに入力されるｈ＋１ビットのバイナリデータのうちの０ビット目がＣ^１ _０〜Ｃ^１ _{ｈ（δ−１）}の最下位ビットＣ^１ _０になるまで、ｈ（δ−２）＋１個の“ｈ ｒｅｓ”回路ブロックを用いてキャリーＣ^２ _０〜Ｃ^２ _{ｈ（δ−２）＋１}を生成する。これら生成されたキャリーＣ^２ _０〜Ｃ^２ _{ｈ（δ−２）＋１}によって表現されるバイナリデータは、データＤに含まれる素数ｐ^２の個数になっている。

そして、Ｃ^１ _０を入力とする“ｈ ｒｅｓ”回路ブロックの出力が、δ＋１桁のｐ進数Ｄ（ａ_０，ａ_１，・・・，ａ_δ−１ ，ａ_δ）のうち、ａ_１のバイナリになる。

続く第２ステップ（図５中Ｓ２）では、第１ステップで得られたデータＤに含まれるｐ^２の個数に対して、更に素数ｐがいくつ含まれるかを計算してｐ^３の個数を求め、ｐ進数Ｄの重みｐ^２の桁の係数ａ_２のバイナリを求める。

以降、同様にｐ進数の重みｐ^δの桁の係数ａ_δのバイナリ表示を求める第δ−１ステップ（図５中Ｓδ−１）まで行う。

なお、ステップＳδ−１のキャリーＣ^δ＋１ _０〜Ｃ^δ＋１ _δ−ｈは計算には使用しない。

次に、図５に示した“ｈ ｒｅｓ”回路ブロックである“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロック（足し算回路）について具体的に説明する。

図６は、“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックの回路記号である。“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックは、ｈ＋１ビットのバイナリＡ_０〜Ａ_ｈを入力し、ｈビットのバイナリＱ_０〜Ｑ_ｈ−１及びキャリーＰＦ０を出力する。

“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックは、入力バイナリＡの素数ｐによる剰余Ｑを出力すると共に、入力バイナリＡがｐ以上の場合にＰＦ０から‘１’、ｐ未満の場合にＰＦ０から‘０’を出力する。

ここで、ｈ＝７、ｐ＝７９の場合について考える。この場合、バイナリＡ、バイナリＱ、素数ｐの間には、数１２に示す関係が成立する。

［数１２］

図７は、ｈ＝７、ｐ＝７９とした場合の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックの回路図である。

“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックは、ＰＦ０生成部Ｕ１、５個の半加算器（Ｈａｌｆ ａｄｄｅｒ）ＨＡ１〜ＨＡ５、及び２個の全加算器（Ｆｕｌｌ ａｄｄｅｒ）ＦＡ１、ＦＡ２を有する。

ＰＦ０生成部Ｕ１は、所定の電圧が供給されるＶｃｃ端子と、接地電圧が供給されるＶｓｓ端子との間に、直列に接続されたＰＭＯＳトランジスタＱＰ１〜ＱＰ４、及びＮＭＯＳトランジスタＱＮ１〜ＱＮ５を有する。これらトランジスタＱＰ１、ＱＰ２、ＱＰ３、ＱＰ４、ＱＮ１、ＱＮ２、ＱＮ３、ＱＮ４、及びＱＮ５は、それぞれ、Ａ_０、Ａ_４、Ａ_５、Ａ_７、Ａ_０、Ａ_１、Ａ_２、Ａ_３、及びＡ_６で制御される。

また、ＰＦ０生成部Ｕ１は、その他に、５個のＰＭＯＳトランジスタＱＰ５〜ＱＰ９、３個のＮＭＯＳトランジスタＱＮ６〜ＱＮ８、及びインバータＩＶ１を有する。

トランジスタＱＰ５〜ＱＰ８は、それぞれ、トランジスタＱＰ１のソース及びドレイン間に接続されている。また、トランジスタＱＰ９は、トランジスタＱＰ１のソース及びトランジスタＱＰ３のドレイン間に接続されている。トランジスタＱＰ５、ＱＰ６、ＱＰ７、ＱＰ８、及びＱＰ９は、それぞれ、Ａ_１、Ａ_２、Ａ_３、Ａ_４、及びＡ_６で制御される。

トランジスタＱＮ６、ＱＮ７は、それぞれ、トランジスタＱＮ１のソース及びトランジスタＱＮ４のドレイン間に接続されている。また、トランジスタＱＮ８は、トランジスタＱＮ１のソース及びトランジスタＱＮ５のドレイン（Ｖｓｓ端子）間に接続されている。トランジスタＱＮ６、ＱＮ７、及びＱＮ８は、それぞれ、Ａ_４、Ａ_５、及びＡ_７で制御される。

インバータＩＶ１は、入力がトランジスタＱＰ４とＱＮ１との接続点に接続されている。このインバータＩＶ１の出力がキャリーＰＦ０になる。

半加算器ＨＡ１は、入力がＡ_０及びＰＦ０、出力がＱ_０、桁上げ出力がＣ０となっている。半加算器ＨＡ２は、入力がＣ０及びＡ_１、出力がＱ_１、桁上げ出力がＣ１となっている。半加算器ＨＡ３は、入力がＣ１及びＡ_２、出力がＱ_２、桁上げ出力がＣ２となっている。半加算器ＨＡ４は、入力がＣ２及びＡ_３、出力がＱ_３、桁上げ出力がＣ３となっている。全加算器ＦＡ１は、入力がＣ３及びＡ_４、桁上げ入力がＰＦ０、出力がＱ_４、桁上げ出力がＣ４となっている。全加算器ＦＡ２は、入力がＣ４及びＡ_５、桁上げ入力がＰＦ０、出力がＱ_５、桁上げ出力がＣ５となっている。半加算器ＨＡ５は、入力がＣ５及びＡ_６、出力がＱ_６となっている。

以上の構成によって、ＰＦ０生成部Ｕ１は、“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックに入力されるバイナリＡがｐ＝７９以上か否かを判断し、その結果をＰＦ０から出力する。バイナリＡがｐ＝７９以上の場合、７９をバイナリＡから引くために、半加算器ＨＡ１１１〜ＨＡ１１５、及び全加算器ＦＡ１１１〜ＦＡ１１２によって、８ビットバイナリの７９の補数である４９をバイナリＡに加えている。

次に、“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックに用いられている２進数の加算を行なう基本的な単位となる全加算器ＦＡと半加算器ＨＡについて説明する。

全加算器ＦＡは、図８に示すように、入力Ａ、Ｂ、桁上げ入力Ｃｉｎ、出力Ｓｏｕｔ、及び桁上げ出力Ｃｏｕｔを持つ。

全加算器ＦＡは、図９に示すようにＸＯＲ（排他的論理和）回路、ＸＮＯＲ（否定排他的論理和）回路、出力回路Ｕ１、及び桁上げ出力回路Ｕ２からなる。

ＸＯＲ回路は、入力Ａ及びＢ間に直列接続されたＰＮＯＳトランジスタＱＰ１及びＱＰ２と、これらトランジスタＱＰ１及びＱＰ２間のノードｎ１及びＶｓｓ端子間に直列接続されたＮＭＯＳトランジスタＱＮ１とＱＮ２とを有する。このうちトランジスタＱＰ２及びＱＮ１のゲートは、入力Ａに接続されている。また、トランジスタＱＰ１及びＱＮ２のゲートは、入力Ｂに接続されている。この構成によって、ノードｎ１がＸＯＲ回路の出力となる。

ＸＮＯＲ回路は、入力Ａ及びＢ間に直列接続されたＮＭＯＳトランジスタＱＮ３及びＱＮ４と、これらトランジスタＱＮ３及びＱＮ４間のノードｎ２とＶｃｃ端子との間に直列接続されたＰＭＯＳトランジスタＱＰ３及びＱＰ４とを有する。このうちトランジスタＱＮ４及びＱＰ３のゲートは、入力Ａに接続されている。また、トランジスタＱＮ３及びＱＰ４のゲートは、入力Ｂに接続されている。この構成によって、ノードｎ２がＸＮＯＲ回路の出力となる。

出力回路Ｕ１は、桁上げ入力Ｃｉｎ及び出力Ｓｏｕｔ間に接続されたＰＭＯＳトランジスタＱＰ５、並びに、同じく接続されたＮＭＯＳトランジスタＱＮ５と、ノードｎ２及び出力Ｓｏｕｔ間に接続されたＮＭＯＳトランジスタＱＮ６と、ノードｎ１及び出力Ｓｏｕｔ間に接続されたＰＭＯＳトランジスタＱＰ６とを有する。このうちトランジスタＱＰ５のゲートは、ＸＯＲ回路の出力であるノードｎ１に接続されている。トランジスタＱＮ５のゲートは、ＸＮＯＲ回路の出力であるノードｎ２に接続されている。トランジスタＱＮ６及びＱＰ６のゲートは、桁上げ出力Ｃｉｎに接続されている。また、出力回路Ｕ１は、ノードｎ１及びＶｓｓ端子間にＮＭＯＳトランジスタＱＮ７を有する。トランジスタＱＮ７のゲートは、ＸＮＯＲ回路の出力であるノードｎ２に接続されている。

桁上げ出力回路Ｕ２は、桁上げ入力Ｃｉｎ及び桁上げ出力Ｃｏｕｔ間に接続されたＰＭＯＳトランジスタＱＰ７、並びに、同じく接続されたＮＭＯＳトランジスタＱＮ８と、入力Ｂ及び桁上げ出力Ｃｏｕｔ間に接続されたＰＭＯＳトランジスタＱＰ８、並びに、同じく接続されたＮＭＯＳトランジスタＱＮ９とを有する。このうちトランジスタＱＰ７及びＱＮ９のゲートは、ＸＮＯＲ回路の出力であるノードｎ２に接続されている。トランジスタＱＮ８及びＱＰ８のゲートは、ＸＯＲ回路の出力であるノードｎ１に接続されている。また、桁上げ出力回路Ｕ２は、Ｖｃｃ端子とノードｎ２との間に接続されたＮＭＯＳトランジスタＱＮ１０を有する。トランジスタＱＮ１０のゲートは、ＸＯＲ回路の出力であるノードｎ１にインバータを介して接続されている。

以上の構成によって、全加算器ＦＡは、入力Ａ及び入力ＢをＸＯＲ回路及びＸＮＯＲ回路で論理演算し、更に、この結果及び桁上げ入力Ｃｉｎを出力回路Ｕ１及び桁上げ出力回路Ｕ２に入力し、出力Ｓｏｕｔ及び桁上げ出力Ｃｏｕｔを生成する。

半加算器ＨＡは、図１０に示すように、入力Ａ、Ｂ、出力Ｓｏｕｔ、及び桁上げ出力Ｃｏｕｔを持つ。

半加算器ＨＡは、図１１に示すように一般的な論理ゲートとインバータで構成できる。具体的には、入力Ａと入力Ｂを入力とするＮＡＮＤゲートＧ１、入力Ａと入力Ｂを入力とするＯＲゲートＧ２、ＮＡＮＤゲートＧ１の出力とＯＲゲートＧ２の出力を入力とするＮＡＮＤゲートＧ３、ＮＡＮＤゲートＧ１の出力を入力とするインバータＩＶ１、及びＮＡＮＤゲートＧ３の出力を入力とするインバータＩＶ２によって構成できる。この構成によって、インバータＩＶ１の出力が桁上げ出力Ｃｏｕｔ、インバータＩＶ２の出力が出力Ｓｏｕｔとなる。

次に、“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックを用いた“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路の構成について考える。

図１２中（Ａ）は、“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路の第ｋステップの回路を、“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックを用いて構成したものである。

ここでは、データをδ桁の２^ｈ進数表現にした場合の第ｊ桁目をｄ_ｊとする。この場合、ｄ_ｊはｈビットのバイナリで表示できるが、この表示の係数Ｄを他のｄの係数Ｄと区別するために、数１３に示すようにサブインデックスを用いる。

［数１３］

また、第ｋステップの演算の入力である前ステップ（第ｋ−１ステップ）のキャリーはＣ^ｋ _０〜Ｃ^ｋ _{ｈ（δ−ｋ）＋ｋ−１}であり、サブインデックスの２の累乗の２進数としての係数となっていて、この２進数によって表現される数がデータに含まれるｐ^ｋの個数となる。

第ｋステップでは、図１２中（Ａ）に示すように、入力はｈ（δ−ｋ）＋ｋ個のバイナリ（キャリーＣ^ｋ _０〜Ｃ^ｋ _{ｈ（δ−ｋ）＋ｋ−１}）であり、これをｈ（δ−（ｋ＋１））＋ｋ＋１個の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックで受ける。

１つ目の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロック＜１＞は、入力バイナリＡ_０〜Ａ_ｈ−１、Ａ_ｈに、それぞれＣ^ｋ _{ｈ（δ−ｋ）＋ｋ−ｈ}〜Ｃ^ｋ _{ｈ（δ−ｋ）＋ｋ−１}、０が入力され、出力Ｑ_０〜Ｑ_ｈ−１、キャリーＰＦ０から、それぞれＲ^{ｈ（δ−（ｋ＋１））＋ｋ} _０〜Ｒ^{ｈ（δ−（ｋ＋１））＋ｋ} _ｈ−１、Ｃ^ｋ＋１ _{ｈ（δ−（ｋ＋１））＋ｋ}が出力される。

図示しない２つ目の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロック＜２＞は、入力バイナリＡ_１〜Ａ_ｈ、及びＡ_０にそれぞれ１つ目の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロック＜１＞の出力Ｒ^{ｈ（δ−（ｋ＋１））＋ｋ} _０〜Ｒ^{ｈ（δ−（ｋ＋１））＋ｋ} _ｈ−１、及びキャリーＣ^ｋ _{ｈ（δ−（ｋ＋１））＋ｋ−１}が入力され、出力Ｑ_０〜Ｑ_ｈ−１、及びキャリーＰＦ０から、それぞれＲ^{ｈ（δ−（ｋ＋１））＋ｋ−１} _０〜Ｒ^{ｈ（δ−（ｋ＋１））＋ｋ−１} _ｈ−１、及びＣ^ｋ＋１ _{ｈ（δ−（ｋ＋１））＋ｋ−１}が出力される。

以降、図１２中（Ａ）に示すように、同様の入出力を持つ“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックが、合計ｈ（δ−（ｋ＋１））＋ｋ＋１個並び、各“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックから出力されるキャリーＣ^ｋ＋１ _０〜Ｃ^ｋ＋１ _{ｈ（δ−（ｋ＋１））＋ｋ}が、次のステップである第ｋ＋１ステップの入力となる。

このように、バイナリからｐ進数への変換は、図１２中（Ｂ）に示す模式図のように、キャリーＣの最上位ビット側から順次実行される。

図１２中（Ａ）は、第ｋステップに関係する回路構成であるが、各ステップを時分割で処理することで、図１２中（Ａ）に示す回路構成を各ステップで使い回すことができる。この場合、各“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックの入出力を単純なオン／オフによって制御可能にするために、“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックの必要数が最大となる第０ステップの回路構成に、更に、δ個の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックが付加される。

この様に構成されたｈ（δ−１）＋δ＋１個の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックからなる回路を“Ｘ ｔｏ ｐ”回路ブロックと呼ぶ。

図１３に示すように、この“Ｘ ｔｏ ｐ”回路ブロックの入力は、図１２中（Ａ）においてｋ＝０とした場合よりもδ個多く、Ｃ^０ _０〜Ｃ^０ _{ｈδ＋δ−１}の合計（ｈ＋１）δ個となっている。また、出力は、ｈ個おきの“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックから出力されるδ＋１個のｈビットのバイナリＲ^０ _０〜Ｒ^０ _ｈ−１、Ｒ^ｈ _０〜Ｒ^ｈ _ｈ−１、・・・、Ｒ^{ｈ（δ−１）} _０〜Ｒ^{ｈ（δ−１）} _ｈ−１、Ｒ^ｈδ _０〜Ｒ^ｈδ _ｈ−１と、次のステップの入力となるｈδ＋δ−ｈ個のキャリーＣ^１ _０〜Ｃ^１ _{ｈ（δ−１）＋δ}となる。

次に、“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路のコア部分となる“ｐ−ａｄｉｃ”回路ブロックについて説明する。

図１４は、“ｐ−ａｄｉｃ”回路ブロックの回路記号を示す図である。

“ｐ−ａｄｉｃ”回路ブロックは、図１４に示すように、Ｂ_０〜Ｂ_δ＋１、Ｉ_０〜Ｉ_{ｈδ＋δ−１}を入力し、ｒ_０〜ｒ_{ｈδ＋δ−１}を出力する。

図１５は、“ｐ−ａｄｉｃ”回路ブロックのブロック図である。“ｐ−ａｄｉｃ”回路ブロックは、１ステップの回路構成を“Ｘ ｔｏ ｐ”回路ブロックとして、これに“Ｘ ｔｏ ｐ”回路ブロックの入出力を制御する制御スイッチＳＷが付加された構成となっている。

具体的には、入力Ｉ_０〜Ｉ_{ｈδ＋δ−１}は、それぞれ、制御スイッチＳＷ１を介してＣ^０ _０〜Ｃ^０ _{ｈδ＋δ−１}として“Ｘ ｔｏ ｐ”回路ブロックに入力される。これらδグループの制御スイッチＳＷ１は、それぞれ入力／Ｂ_１〜／Ｂ_δ（‘／’は否定を表わす）によって制御される。

１個の制御スイッチＳＷ１は、入力ＩＮと出力ＯＵＴを接続するトランスファトランジスタＴＱと、出力ＯＵＴを接地電圧に引き下げるＮＭＯＳトランジスタＱＮを有する。トランスファトランジスタＴＱは、制御信号がＣＮＴ＝‘０’の場合にオンし、トランジスタＱＮは、制御信号がＣＮＴ＝‘１’の場合にオンする。

制御スイッチＳＷ１の場合、制御信号ＣＮＴは、／Ｂ_１〜／Ｂ_δとなる。したがって、Ｂ＝‘１’の場合、Ｉ_０〜Ｉ_{ｈδ＋δ−１}がそのままＣ^０ _０〜Ｃ^０ _{ｈδ＋δ−１}として出力され、Ｂ＝‘０’の場合、入力に依らず出力は‘０’となる。これは、“ｐ−ａｄｉｃ”回路ブロックへの入力Ｉ_０〜Ｉ_{ｈδ＋δ−１}が不定であっても、“Ｘ ｔｏ ｐ”回路ブロックの入力が不定になることを回避するためである。

Ｃ^０ _０〜Ｃ^０ _{ｈδ＋δ−１}が入力された“Ｘ ｔｏ ｐ”回路ブロックは、前述の通り、Ｒ^０ _０〜Ｒ^ｈδ _ｈ−１、Ｃ^１ _０〜Ｃ^１ _{ｈδ＋δ−ｈ}を出力する。

“Ｘ ｔｏ ｐ”回路ブロックから出力されたＣ^１ _０〜Ｃ^１ _{ｈδ＋δ−ｈ}は、制御スイッチＳＷ２を介して“ｐ−ａｄｉｃ”回路ブロックの出力であるｒ_ｈ〜ｒ_{ｈ（δ＋１）＋δ−ｈ}となる。これらδグループの制御スイッチＳＷ２は、入力／Ｂ_１〜／Ｂ_δによって制御される。したがって、制御スイッチＳＷ２は、Ｂ＝‘０’の場合、Ｃ^１ _０〜Ｃ^１ _{ｈδ＋δ-ｈ}をそのままｒ_ｈ〜ｒ_{ｈ（δ＋１）＋δ−ｈ}として出力する。

また、“Ｘ ｔｏ ｐ”回路ブロックから出力されたＲ^０ _０〜Ｒ^ｈδ _ｈ−１は、制御スイッチＳＷ３を介して、“ｐ−ａｄｉｃ”回路ブロックの出力であるｒ_０〜ｒ_{ｈ（δ＋１）−１}となる。これらδグループの制御スイッチＳＷ３は、それぞれＢ_０∧／Ｂ_１〜Ｂ_δ∧／Ｂ_δ＋１で制御される。これによって、例えば、Ｒ^０ _０及びｒ_０間にある制御スイッチＳＷ３は、Ｂ_０＝‘１’、Ｂ_１＝‘０’の場合のみ、Ｒ^０ _０をそのままｒ_０として出力する。

制御スイッチＳＷを制御するＢ_１〜Ｂ_δ＋１は、タイミング信号であり、順次立ち上がる信号である。これに合わせて入力Ｉのパスが下位ビット側からｈビットずつ閉じ、出力ｒのパスが出力Ｒのパスと切り替わる。

ｐ進数の各桁の係数Ａに相当するＲは、次のステップの計算過程に入るまでに、そのステップの結果を出力するため、隣接するタイミング信号Ｂと論理演算した信号によってオン／オフ制御される制御スイッチＳＷ３を介して後述する外部の“Ｄ−ｒ”レジスタに出力される。

次に、前述した回路をまとめて構成された“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路について説明する。

図１６は、“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路のブロック図である。“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路は、“ｐ−ａｄｉｃ”回路ブロックに“Ｄ−ｒ”レジスタが結合されて構成される。

“Ｄ−ｒ”レジスタは、図１６に示すように、タイミング信号Ｂ及びクロックｃｌｋで制御されるレジスタで、入力ｒ_０〜ｒ_{ｈδ＋δ−１}、Ｄ_０〜Ｄ_ｈδ−１、出力Ｉ_０〜Ｉ_{ｈδ＋δ−１}を持つ。

図１７は、“Ｄ−ｒ”レジスタの回路図である。

“Ｄ−ｒ”レジスタは、ビット毎に２つのインバータからなるフリップフロップＦＦを有している。このフリップフロップＦＦには、制御スイッチＳＷ１を介してＤ_ｊ（ｊ＝０〜ｈδ−１）が入力され、制御スイッチＳＷ２を介してｒ_ｊが入力される。一方、フリップフロップＦＦの出力側には、制御スイッチＳＷ３を介してインバータＩＶ１が接続されている。このインバータＩＶ１の出力がＩ_ｊとなる。

制御スイッチＳＷ１〜ＳＷ３は、タイミング信号Ｂ_０及びクロックｃｌｋによって制御される。具体的には、制御スイッチＳＷ１は／ｃｌｋ∧／Ｂ_０＝‘１’の場合、制御スイッチＳＷ２は／ｃｌｋ∧Ｂ_０＝‘１’の場合、制御スイッチＳＷ３はｃｌｋ＝‘１’の場合にそれぞれオンする。

なお、“Ｄ−ｒ”レジスタの入力にないＤ_ｈδ〜Ｄ_{ｈδ＋δ−１}は‘０’とする。

“Ｄ−ｒ”レジスタの初期状態は、バイナリＤ_０〜Ｄ_ｈδ−１が設定され、残りは‘０’で埋められた状態となっている。以後、Ｂ_０が立ち上がるとｃｌｋの立ち下がりに同期してデータｒ_ｊを取り込み、ｃｌｋの立ち上がりに同期して取り込んだｒ_ｊをＩ_ｊとして出力する。

この“Ｄ−ｒ”レジスタは、“ｐ−ａｄｉｃ”回路ブロックと結合してタイミング信号Ｂ_ｊ毎に計算のステップを進める。各クロックの変化の様子は図１８に示す。クロックｃｌｋからクロックｃｋが作られ、更にタイミング信号Ｂ_ｊが作られる。

各計算ステップでｐ進数の各桁Ａ_ｊが下位側から出力ｒとして得られ、これをタイミング信号Ｂ_ｊの後半のＩ_ｊの取り込みと同じタイミングで保持していく。

全計算ステップが終了すると“Ｄ−ｒ”レジスタには、ｐ進数のデータＤの各桁の係数ａをバイナリに変換した場合の各桁の係数Ａ^ｊ _ｍが保持されている。

なお、後に色々な場合について比較するが、実用的な素数ｐを用いたシステムでは計算ステップの数は１０以下となり、“ｐ−ａｄｉｃ”回路ブロックに含まれる“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックの数は５０以下となる。

［Ｚｐデータからバイナリデータへの変換］
次に、データとして等価な「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」のδ＋１桁のｐ進数Ｄ（ａ_０，ａ_１，・・・，ａ_δ−１，ａ_δ）から「ｂｉｎａｒｙ ｗｏｒｌｄ」のδ桁の２^ｈ進数Ｄ（ｄ_０，ｄ_１，・・・，ｄ_δ−１）への変換の具体的回路を以下に示す。

ｐ進数から２進数への変換は、ｐ進数に含まれる素数ｐの個数を数え上げ、その個数分だけ素数ｐのバイナリ表示を加え合わせていく作業となる。この作業では、ｐ進数の最大の次数の桁から次数を１つずつ下げてバイナリに変換し、最終的に素数ｐのゼロ次でのバイナリが同じ数の２進数になっていることを使う。そのため、ｈビット毎の計算からｈ＋１ビットを得て、このうちの最下位ビットを分離して、次の２の累乗の次数における計算を行なうという計算過程の繰り返しで処理することができる。

図１９は、ｐ進数からバイナリへの変換過程の一部を示す図である。ここでは、既に、ｐ進数のデータに含まれるｐ^ｎ＋１の個数をバイナリで表現できているものとして、ｐ進数の重みｐ^ｎの桁の数のバイナリ表示を用いて、ｐ^ｎの個数のバイナリを得る過程について説明する。

データに含まれるｐ^ｎ＋１の個数のバイナリ表現が、Ｃ_０２^０＋Ｃ_１２^１＋・・・＋Ｃ_ｊ−１２^ｊ−１＋Ｃ_ｊ２^ｊ＋Ｃ_ｊ＋１２^ｊ＋１＋・・・であった場合、データＤのｐ^ｎの個数は、図１９中の式Ｅ１（＝ｐ^ｎ（Ａ_０２^０＋Ａ_１２_１＋・・・＋Ａ_ｈ−１２^ｈ−１）＋ｐ^ｎ＋１（Ｃ_０２^０＋Ｃ_１２^１＋・・・＋Ｃ_ｊ−１２^ｊ−１＋Ｃ_ｊ２^ｊ＋Ｃ_ｊ＋１２^ｊ＋１＋・・・））のように表わすことができる。ここで、ｐ^ｎの係数は、Ａ_０２^０＋Ａ_１２_１＋・・・＋Ａ_ｈ−１２^ｈ−１はｐ進数の重みｐ^ｎの桁のｈビット表現となる。

始めに、図１９中Ｓ１で示すように、ｈビットのバイナリに素数ｐを加える演算として、式Ｅ１のうちｐ^ｎの項ｐ^ｎ（Ａ_０２^０＋Ａ_１２^１＋・・・＋Ａ_ｈ−１２^ｈ−１）にｐ^ｎ＋１の項のうちｐ進数の重みｐ^ｎ＋１の桁をバイナリ表現したときの最下位ビットに対応するｐ^ｎ＋１Ｃ_０２^０の項を加え、式Ｅ２（＝ｐ^ｎ（Ａ_０２^０＋Ａ_１２^１＋・・・＋Ａ_ｈ−１２^ｈ−１）＋ｐ^ｎ＋１Ｃ_０２^０）を生成する。この式Ｅ２から、ｈ＋１ビットのバイナリ表示ｐ^ｎ（Ｃ^ｋ _０２^０＋Ｑ^１ _１２^１＋・・・＋Ｑ^１ _ｈ−１２^ｈ−１＋Ｑ^１ _ｈ２^ｈ）を得る。更に、次の処理のために、式Ｅ２から式Ｅ２に含まれるｐ^ｎの個数の２進数表現の最下位の項ｐ^ｎＣ^ｋ _０２^０を分離した新たなｈビットのバイナリｐ^ｎ２^１（Ｑ^１ _１２^０＋・・・＋Ｑ^１ _ｈ−１２^ｈ−２＋Ｑ^１ _ｈ２^ｈ−１）を得ておく。

続いて、図１９中Ｓ２で示すように、ｈビットのバイナリに素数ｐを加える演算として、図１９中Ｓ１で得られたｐ^ｎ２^１（Ｑ^１ _１２^０＋・・・＋Ｑ^１ _ｈ−１２^ｈ−２＋Ｑ^１ _ｈ２^ｈ−１）に式Ｅ１のうちｐ^ｎ＋１Ｃ_１２^１の項を加え、式Ｅ３（＝ｐ^ｎ２^１（Ｑ^１ _１２^０＋・・・＋Ｑ^１ _ｈ−１２^ｈ−２＋Ｑ^１ _ｈ２^ｈ−１）＋ｐ^ｎ＋１Ｃ_１２^１）を生成する。この式Ｅ３から、ｈ＋１ビットのバイナリ表示ｐ^ｎ２^１（Ｃ^ｋ _１２^０＋Ｑ^２ _１２^１＋・・・＋Ｑ^２ _ｈ−１２^ｈ−１＋Ｑ^２ _ｈ２^ｈ）を得る。更に、次の処理のために、式Ｅ３から式Ｅ３に含まれるｐ^ｎの個数の２進数表現の最下位の項ｐ^ｎＣ^ｋ _１２^１を分離したｐ^ｎ２^２（Ｑ^２ _１２^０＋・・・＋Ｑ^２ _ｈ−１２^ｈ−２＋Ｃ^２ _ｈ２^ｈ−１）を得ておく。

以降、図１９中Ｓ２と同様に、ｐ^ｎの個数のバイナリ表現ｐ^ｎＣ^ｋ _ｊ２^ｊを全て得てこのステップの計算を終了する。

この次のステップでは同様にしてｐ進数のｐ^ｎ−１の個数のバイナリ表現を求める。

以上のように、計算の過程では、ｈビットのバイナリに素数ｐを加えた数がｈ＋１ビット以下になるように素数ｐが選ばれていることを利用している。

ｈビットのバイナリの数Ａは、数１４のように表わすことができことから、０≦Ａ＜２^ｈが成立する。

［数１４］

また、ｈビットの素数ｐは、２^ｈ−１＜ｐ＜２^ｈの範囲となる。したがって、数１５のような関係が成立する。

［数１５］

数１５は、ｈビットのバイナリに素数ｐを加えても、数８に示した素数ｐの選択条件からｈ＋１ビット以下のバイナリで表現できることを意味する。

したがって、データをｐ進数からバイナリに変換する“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路は、入力ｈビット、出力ｈ＋１ビットの加算回路のラダーで構成できることが分かる。

図２０は、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」のδ＋１桁のｐ進数Ｄ（ａ_０，ａ_１，・・・，ａ_δ−１，ａ_δ）から「ｂｉｎａｒｙ ｗｏｒｌｄ」のδ桁の２^ｈ進数Ｄ（ｄ_０，ｄ_１，・・・，ｄ_δ−１）への変換回路の構成を模式的に示した図である。

なお、図２０中“ｈ＋ｐ”と示した四角は、入力されたｈビットのデータに対して、入力されたキャリーＣに応じて素数ｐを加え、ｈ＋１ビットのバイナリを出力する演算回路である。以下、この回路を“ｈ＋ｐ”回路ブロックと呼ぶ。

始めに、第０ステップ（図２０中Ｓ０）では、ｐ進数のδ−１次の桁のバイナリ表示に対してδ次の桁のバイナリ表示をキャリーすなわちｐ^δの個数のバイナリ表現として上述した計算を行う。これによって、ｐ^δ−１の個数としてキャリーＣ^１ _０〜Ｃ^１ _ｈ２−１の２ｈビットを得る。このキャリーＣ^１ _０〜Ｃ^１ _ｈ２−１が次の第１ステップの入力となる。

続いて、第１ステップ（図２０中Ｓ１）では、ｐ進数のδ−２次の桁のバイナリ表示に対して、第０ステップで得られたキャリーＣ^１ _０〜Ｃ^１ _ｈ２−１をｐ^δ−１の個数のバイナリ表現として前述の計算を行う。これによって、ｐ^δ−２の個数としてキャリーＣ^２ _０〜Ｃ^２ _ｈ３−１の３ｈビットを得る。このキャリーＣ^２ _０〜Ｃ^２ _ｈ３−１が次の第２ステップ（図２０中Ｓ３）の入力となる。

以降、第０ステップ及び第１ステップと同様のステップを重ね、第δ−１ステップでは、ｐ進数表現の０次の桁のバイナリ表示に対して、前の第δ−２ステップで得られたキャリーＣ^δ−１ _０〜Ｃ^δ−１ _ｈδ−１をｐの個数のバイナリ表現として前述の計算を行ない、ｐ^０の個数すなわちＤの２進数表現としてキャリーＣ^δ _０〜Ｃ^δ _{ｈ（δ＋１）−１}のｈ（δ＋１）ビットを得る。但し、上位のｈビットはＤのｐ進数と２^ｈ進数との設定からゼロとなる。これらのキャリーＣ^δ _０〜Ｃ^δ _{ｈ（δ＋１）−１}からＣ^δ _ｈδ〜Ｃ^δ _{ｈ（δ＋１）−１}を除いたＣ^δ _０〜Ｃ^δ _ｈδ−１をｈビット毎にまとめるとＤのバイナリ表現Ｄ（ｄ_０，ｄ_１，・・・，ｄ_δ−１）を得ることができる。

次に、図２０に示した“ｈ＋ｐ”回路ブロックである“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックについて具体的に説明する。

図２１は、“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックの回路記号である。“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックは、ｈビットのバイナリＢ_０〜Ｂ_ｈ−１と１ビットのキャリー（ｃａｒｒｙ）を入力し、ｈ＋１ビットのバイナリＱ_０〜Ｑ_ｈを出力する。この“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックは、入力Ｂに対し、ｃａｒｒｙが‘１’なら素数ｐを加え、その結果をＱとして出力する。

ここで、ｈ＝７、ｐ＝７９の場合の“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックについて考える。この場合、バイナリｂ、バイナリＱ、素数ｐの間には、数１６に示す関係が成立する。

［数１６］

図２２は、ｈ＝７、ｐ＝７９とした場合の“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックの回路図である。

“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックは、３個の半加算器（Ｈａｌｆ Ａｄｄｅｒ）ＨＡ１〜ＨＡ３、及び４個の全加算器（Ｆｕｌｌ Ａｄｄｅｒ）ＦＡ１〜ＦＡ４を有する。

半加算器ＨＡ１は、入力がＢ_０及びｃａｒｒｙ、出力がＱ_０、桁上げ出力がＣ０となっている。全加算器ＦＡ１は、入力がＢ_１及びｃａｒｒｙ、桁上げ入力がＣ０、出力がＱ_１、桁上げ出力がＣ１となっている。全加算器ＦＡ２は、入力がＢ_２及びｃａｒｒｙ、桁上げ入力がＣ１、出力がＱ_２、桁上げ出力がＣ２となっている。全加算器ＦＡ３は、入力がＢ_３及びｃａｒｒｙ、桁上げ入力がＣ２、出力がＱ_３、桁上げ出力がＣ３となっている。半加算器ＨＡ２は、入力がＢ_４、桁上げ入力がＣ３、出力がＱ_４、桁上げ出力がＣ４となっている。半加算器ＨＡ３は、入力がＢ_５、桁上げ入力がＣ４、出力がＱ_５、桁上げ出力がＣ５となっている。全加算器ＦＡ４は、入力がＢ_６及びｃａｒｒｙ、桁上げ入力がＣ５、出力がＱ_６、桁上げ出力がＱ７となっている。

以上の構成によって、“ｐ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックは、ｃａｒｒｙ＝‘１’なら、入力バイナリＢにｐ＝７９を加える。

なお、全加算器ＦＡ及び半加算器ＨＡの回路構成については、図９及び図１１と同様であるため割愛する。

次に、以上説明した“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックを用いた“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路の構成について考える。

図２３は、“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路の第ｋステップの回路構成を、“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックを用いて構成したものである。

ここで、データをδ＋１桁のｐ進数表現のｊ次の桁の係数ａ_ｊは、ｈビットのバイナリで表現できるが、このバイナリ表現の係数Ａを他の桁の係数ａと区別するめに、数１７に示すようなサブインデックスを用いる。

［数１７］

また、第ｋステップの演算の入力である前ステップ（第ｋ−１ステップ）のキャリーはＣ^ｋ _０〜Ｃ^ｋ _{ｈ（ｋ＋１）−１}であり、サブインデックスの２の累乗の２進数としての係数となっていて、この２進数が表現する数がデータに含まれるｐ^δ−ｋの個数となる。

第ｋステップでは、図２３中（Ａ）に示すように、ｈ（ｋ＋１）個の“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックで処理される。各“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックには、１個のキャリー（ｃａｒｒｙ）と、ｐ進数表現の１桁分の係数を表示するｈ個のバイナリが入力される。

１つ目の“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロック＜１＞は、ｃａｒｒｙ、入力Ｂ_０〜Ｂ_ｈ−１に、それぞれＣ^ｋ _０、Ｑ^−１ _０〜Ｑ^−１ _ｈ−１が入力され、Ｑ_０、Ｑ_１〜Ｑ_ｈに、それぞれＣ^ｋ＋１ _０、Ｑ^０ _０〜Ｑ^０ _ｈ−１が出力される。

図示しない２つ目の“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロック＜２＞は、ｃａｒｒｙ、入力Ｂ_０〜Ｂ_ｈ−１に、それぞれＣ^ｋ _１、Ｑ^０ _０〜Ｑ^０ _ｈ−１が入力され、Ｑ_０、Ｑ_１〜Ｑ_ｈに、それぞれＣ^ｋ＋１ _１、Ｑ^１ _０〜Ｑ^１ _ｈ−１が出力される。

以降、図２３中（Ａ）に示すように、同様の入出力を持つ“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックが、合計ｈ（ｋ＋１）個並び、各“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックから出力されるキャリーＣ^ｋ＋１ _０〜Ｃ^ｋ＋１ _{ｈ（ｋ＋１）−１}が、次にステップである第ｋ＋１ステップの入力となる。

このように、ｐ進数からバイナリへの変換は、図２３中（Ｂ）に示す模式図のように、キャリーＣの最下位ビット側から順次実行される。

図２３は、上記の通り、第ｋステップに関係する回路構成であるが、各ステップを時分割で処理することで、図２３中（Ａ）に示す回路構成を各ステップで使い回すことができる。この場合、各“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックの入出力を単純なオン／オフによって制御可能にするために、ｋ＝０とした場合のｈ個の“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックを最小構成の回路ブロックとする。

この様に構成されたｈ個の“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックからなる回路を“ａ ｔｏ Ｘ”回路ブロックと呼ぶ。

図２４に示すように、この“ａ ｔｏ Ｘ”回路ブロックの入力は、Ｑ^−１ _０〜Ｑ^−１ _ｈ−１とＣ^０ _０〜Ｃ^０ _ｈ−１の２ｈ個となり、出力はＱ^ｈ−１ _０〜Ｑ^ｈ−１ _ｈ−１とＣ^１ _０〜Ｃ^１ _ｈ−１の２ｈ個となる。

次に、前述の“ａ ｔｏ Ｘ”回路ブロックを用いて、ｐ進数の次数を１つ下げるための１ステップ分の回路を構成する。以下では、この回路を“ｐ ｔｏ Ｘ”回路ブロックと呼ぶ。この“ｐ ｔｏ Ｘ”回路ブロックは、全計算ステップに共通に使用することができる。

図２５は、“ｐ ｔｏ Ｘ”回路ブロックの回路記号である。“ｐ ｔｏ Ｘ”回路ブロックはタイミング信号Ｂ_１〜Ｂ_δ−１で制御され、入力であるＱ^−１ _０〜Ｑ^{ｈ（δ−１）−１} _ｈ−１、Ｃ^δ−１ _０〜Ｃ^δ−１ _ｈδ−１から、Ｃ^δ _０〜Ｃ^δ _{ｈ（δ＋１）−１}を出力する。

図２６は、“ｐ ｔｏ Ｘ”回路ブロックのブロック図である。

“ｐ ｔｏ Ｘ”回路ブロックは、δ個の“ａ ｔｏ Ｘ”回路ブロックからなる。

１個目の“ａ ｔｏ Ｘ”回路ブロック＜１＞は、“ｐ ｔｏ Ｘ”回路ブロックの入力の一部であるＱ^−１ _０〜Ｑ^−１ _ｈ−１、及びＣ^δ−１ _０〜Ｃ^δ−１ _ｈ−１を入力し、Ｑ´^ｈ−１ _０〜Ｑ´^ｈ−１ _ｈ−１、及び“ｐ ｔｏ Ｘ”回路ブロックの出力の一部であるＣ^δ _０〜Ｃ^δ _ｈ−１を出力する。

２個目の“ａ ｔｏ Ｘ”回路ブロック＜２＞は、Ｑ^ｈ−１ _０〜Ｑ^ｈ−１ _ｈ−１、及び“ｐ ｔｏ Ｘ”回路ブロックの入力の一部であるＣ^δ−１ _ｈ〜Ｃ^δ−１ _ｈ２−１を入力し、Ｑ´^ｈ２−１ _０〜Ｑ´^ｈ２−１ _ｈ−１、及び“ｐ ｔｏ Ｘ”回路ブロックの出力の一部であるＣ^δ _ｈ〜Ｃ^δ _ｈ２−１を出力する。入力のうち、Ｑ^ｈ−１ _０〜Ｑ^ｈ−１ _ｈ−１は、１個目の“ａ ｔｏ Ｘ”回路ブロック＜１＞の出力Ｑ´^ｈ−１ _０〜Ｑ´^ｈ−１ _ｈ−１がタイミング信号Ｂ_δ−１で制御される制御スイッチＳＷ１を介して入力される信号である。

３個目の“ａ ｔｏ Ｘ”回路ブロック＜３＞は、Ｑ^ｈ２−１ _０〜Ｑ^ｈ２−１ _ｈ−１、及び“ｐ ｔｏ Ｘ”回路ブロックの入力の一部であるＣ^δ−１ _ｈ２〜Ｃ^δ−１ _ｈ３−１を入力し、Ｑ´^ｈ３−１ _０〜Ｑ´^ｈ３−１ _ｈ−１、及び“ｐ ｔｏ Ｘ”回路ブロックの出力の一部であるＣ^δ _ｈ２〜Ｃ^δ _ｈ３−１を出力する。入力のうち、Ｑ^ｈ２−１ _０〜Ｑ^ｈ２−１ _ｈ−１は、２個目の“ａ ｔｏ Ｘ”回路ブロックの出力Ｑ´^ｈ２−１ _０〜Ｑ´^ｈ２−１ _ｈ−１がタイミング信号Ｂ_δ−２で制御される制御スイッチＳＷ２を介して入力される信号である。

以降、δ個目の“ａ ｔｏ Ｘ”回路ブロック＜δ＞まで同様に接続される。

このように、“ａ ｔｏ Ｘ”回路ブロックの入出力間を制御スイッチＳＷで接続するのは、計算ステップ毎に入力の接続が外部入力と内部入力で切り替わるためであり、外部入力の場合に内部回路の出力が干渉しないようにするためである。

図２６の回路構成の場合、タイミング信号Ｂ_０だけが‘１’のタイミングにおいて、全ての制御スイッチＳＷがオフされ、１番目の“ａ ｔｏ Ｘ”回路ブロックだけが活性化する。これが第０ステップに相当する。

続いて、タイミング信号Ｂ_１も‘１’になると、２番目の“ａ ｔｏ Ｘ”回路ブロックまでが活性化する。これが第１ステップに相当する。

以降、タイミング信号Ｂ_２〜Ｂ_δ−１が順次立ち上がっていく毎に、各ステップで必要な“ａ ｔｏ Ｘ”回路ブロックが活性化されていく。

次に、２^ｈ進数変換回路のコア部分となる“ｂｉｎａｒｙ”回路ブロックについて説明する。

図２７は、“ｂｉｎａｒｙ”回路ブロックの回路記号である。

“ｂｉｎａｒｙ”回路ブロックは、図２７に示すように、Ｂ_０〜Ｂ_δ、Ｉ_０〜Ｉ_{ｈ（δ＋１）−１}を入力し、ｒ_０〜ｒ_{ｈ（δ＋１）−１}を出力する。

図２８は、“ｂｉｎａｒｙ”回路ブロックのブロック図である。“ｂｉｎａｒｙ”回路ブロックは、１ステップの回路構成を“ｐ ｔｏ Ｘ”回路ブロックとして、これに“ｐ ｔｏ Ｘ”回路ブロックの入出力を制御する制御スイッチＳＷが付加された構成となっている。

具体的には、入力Ｉ_ｈ〜Ｉ_{ｈ（δ−１）−１}は、それぞれ、制御スイッチＳＷ１を介してＣ^δ−１ _０〜Ｃ^δ−１ _ｈδ−１として“ｐ ｔｏ Ｘ”回路ブロックに入力される。これらδ個の制御スイッチＳＷ１は、それぞれタイミング信号Ｂ_０〜Ｂ_δ−１によって制御される。したがって、制御スイッチＳＷ１は、Ｂ＝‘１’の場合、Ｉ_ｈ〜Ｉ_{ｈ（δ＋１）−１}がそのままＣ^δ−１ _０〜Ｃ^δ−１ _ｈδ−１として出力され、Ｂ＝‘１’の場合、入力に依らず出力は‘０’となる。

また、入力Ｉ_０〜Ｉ_ｈδ−１は、それぞれ、制御スイッチＳＷ２を介してＱ^−１ _０〜Ｑ^{ｈ（δ−１）−１} _ｈ−１として“ｐ ｔｏ Ｘ”回路ブロックに入力される。これらδ個の制御スイッチＳＷ２は、それぞれＢ_δ∧Ｂ_δ−１〜Ｂ_１∧Ｂ_０によって制御される。したがって、例えば、Ｉ_０及びＱ^−１ _０間にある制御スイッチＳＷ２は、Ｂ_δ＝‘１’、Ｂ_δ−１＝‘０’の場合のみ、Ｉ_０をそのままＱ^−１ _０として出力する。

“ｐ ｔｏ Ｘ”回路ブロックから出力されたＣ^δ _０〜Ｃ^δ _{ｈ（δ＋１）−１}は、制御スイッチＳＷ３を介して、“ｂｉｎａｒｙ”回路ブロックの出力であるｒ_０〜ｒ_{ｈ（δ＋１）−１}となる。これら制御スイッチＳＷ３は、タイミング信号Ｂ_δ−１〜Ｂ_０によって制御される。したがって、制御スイッチＳＷ３は、Ｂ＝‘１’の場合、Ｃ^δ _０〜Ｃ^δ _{ｈ（δ＋１）−１}をそのままｒ_０〜ｒ_{ｈ（δ＋１）−１}として出力する。

以上の回路構成によって、“ｐ ｔｏ Ｘ”回路ブロックは、入力と出力のビット幅をｈビットずつ順次増やしながら各計算ステップに対応する。各計算ステップでｐ進数の桁の数Ａを順次上位桁から取り込み、全ての計算ステップが終了したときに得られるのがデータのバイナリ表現となる。

前述のように、タイミング信号Ｂ_０〜Ｂ_δは、順次立ち上がる信号である。これに合わせて入力Ｉと出力ｒへのパスが上位ビット側からｈビットずつ導通していく。

ｐ進数の各桁の数Ａは、後述する外部の“Ａ−ｒ”レジスタに初期設定されて、次の計算ステップに入るまでに、選択的にパスが切り替わるように、隣接するタイミング信号Ｂで論理演算した信号によってオン／オフ制御される制御スイッチＳＷ３を介して“Ａ−ｒ”レジスタに出力される。

次に、前述した回路をまとめて構成された“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路について説明する。

図２９は、“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路のブロック図である。“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路は、“ｂｉｎａｒｙ”回路ブロックに“Ａ−ｒ”レジスタが結合されて構成される。

“Ａ−ｒ”レジスタは、図２９に示すように、タイミング信号Ｂ_０及びクロックｃｌｋで制御されるレジスタで、入力ｒ_０〜ｒ_{ｈ（δ＋１）−１}、Ａ_０〜Ａ_{ｈ（δ＋１）−１}、出力Ｉ_０〜Ｉ_{ｈ（δ＋１）−１}を持つ。

図３０は、“Ａ−ｒ”レジスタの回路図である。

“Ａ−ｒ”レジスタは、ビット毎に２つのインバータからなるフリップフロップＦＦを有している。このフリップフロップＦＦには、制御スイッチＳＷ１を介してＡ_ｊ（ｊ＝０〜ｈ（δ＋１）−１）が入力され、制御スイッチＳＷ２を介してｒ_ｊが入力される。一方、フリップフロップＦＦの出力側には、制御スイッチＳＷ３を介してインバータＩＶ１が接続されている。このインバータＩＶ１の出力がＩ_ｊとなる。

制御スイッチＳＷ１〜ＳＷ３はタイミング信号Ｂ_０及びクロックｃｌｋによって制御される。具体的には、制御スイッチＳＷ１は／ｃｌｋ∧／Ｂ０＝‘１’の場合、制御スイッチＳＷ２は／ｃｌｋ∧Ｂ０＝‘１’の場合、制御スイッチＳＷ３はｃｌｋ＝‘１’の場合にそれぞれオンする。

“Ａ−ｒ”レジスタの初期状態は、ｐ進数の桁Ａ_０〜Ａ_{ｈ（δ＋１）−１}となっている。

以後、タイミング信号Ｂ_０が立ち上がるとクロックｃｌｋの立ち下がりに同期して取り込んだｒ_ｊを、クロックｃｌｋの立ち上がりに同期してＩ_ｊとして出力する。

この“Ａ−ｒ”レジスタは“ｂｉｎａｒｙ”回路ブロックと結合してタイミング信号Ｂ_ｊ毎に計算ステップを進める。各クロックの変化の様子は、図１８と同様である。クロックｃｌｋからｃｋが作られ、更にタイミング信号Ｂ_ｊが作られる。

全計算ステップが終了すると“Ａ−ｒ”レジスタには、入力であるｐ進数Ａのバイナリ表現Ｄ_ｊが保持される。

なお、後で色々な場合について比較するが、実用的な素数ｐを用いたシステムでは計算ステップの数は１０以下となり、“ｂｉｎａｒｙ”回路ブロックに含まれる“ｈ＋１ ｂｉｔ ａｄｄ ｐ”回路ブロックの数は５０以下となる。

［タイミング信号発生回路］
次に、“ｂｉｎａｒｙ ｔｏ ｐ−ａｄｉｃ”変換演算回路、“ｐ−ａｄｉｃ ｔｏ ｂｉｎａｒｙ”変換演算回路を時分割で制御するクロックなどを発生するタイミング信号発生回路について説明する。

始めに、タイミング信号発生回路の動作概念について説明する。

タイミング信号発生回路は、後述する単位回路を順次接続して構成される回路であり、この単位回路数によって、必要最小限のステップ数を発生させることができる。

図３１は、このタイミング信号発生回路の動作概念図である。

タイミング信号発生回路は、単位回路の状態が‘１’である状態をクロックｃｋでシフトしていき、‘１’状態と‘０’状態の境界からタイミング信号Ｂを発生させる。

クロックｃｌｋからその立ち上がりでトグルするクロックｃｋ及び／ｃｋは、図３２に示すフリップフロップ回路ＦＦで生成する。つまり、フリップフロップ回路ＦＦは、／ｃｋ及びｃｌｋを入力とするＮＡＮＤゲートＧ１、ｃｋ及びｃｌｋを入力とするＮＡＮＤゲートＧ２、ＮＡＮＤゲートＧ１の出力を一方の入力とするＮＡＮＤゲートＧ３、並びにＮＡＮＤゲートＧ２の出力を一方の入力とするＮＡＮＤゲートＧ４を有する。ＮＡＮＤゲートＧ３の他方の入力と、ＮＡＮＤゲートＧ４の他方の入力は、それぞれＮＡＮＤゲートＧ４の出力と、ＮＡＮＤゲートＧ３の出力に接続されている。

図３１に示すように、クロックｃｋが変化する毎に、フリップフロップ回路ＦＦの境界が右に移動し、右端に達すると、反射して左に移動する。そして、フリップフロップ回路ＦＦの境界が左端に達すると、反射して右に移動する。以降、右への境界移動、左への境界移動を繰り返していく。このような動作によって、フリップフロップ回路ＦＦの境界をタイミング信号Ｂの出力とした場合、図１８に示すように、クロックｃｋの周期ずつずれて立ち上がるタイミング信号Ｂが生成される。

続いて、図３３で、タイミング信号発生回路ブロックの詳細な回路構成についてその一例を説明する。

タイミング信号発生回路ブロックは、単位回路間のノードｎから出力される境界信号ｂ０〜ｂｍからタイミング信号Ｂ_０〜Ｂ_２ｍ＋２を生成するタイミング信号生成部Ｕ１と、単位回路を接続してなる境界信号生成部Ｕ２と、単位回路の状態の移動方向を決定する信号Ｒ及びＬを生成する移動方向生成部Ｕ３とからなる。

タイミング信号生成部Ｕ１は、それぞれがＬ及びｂｊ（ｊ＝０〜ｍ）を入力し、Ｂ_ｊを出力するｍ＋１個のＯＲゲートＧ１と、それぞれがＲ及びｂｊを入力し、Ｂ_ｋ（ｋ＝２ｍ＋１〜ｍ＋１）を出力するｍ＋１個のＮＯＲゲートＧ２とを有する。

境界信号生成部Ｕ２は、図３３に示すように、複数の単位回路によって構成されている。

各単位回路Ｕ４は、２つのクロスカップルされたインバータと、単位回路Ｕ４の状態を隣接する単位回路Ｕ４に伝搬させるための６個のＮＭＯＳトランジスタによって構成されている。

具体的には、例えば、１つ目の単位回路Ｕ４＜１＞は、クロスカップルされたインバータＩＶ１及びＩＶ２を有する。

このうち、インバータＩＶ１の出力ノード及びＶｓｓ端子間には、直列接続された３つのＮＭＯＳトランジスタＱＮ１〜ＱＮ３を有する。これらトランジスタＱＮ１、ＱＮ２、ＱＮ３は、それぞれ‘Ｈ’（常にオン）、信号Ｒ、クロックｃｋで制御される。

一方、インバータＩＶ２の出力ノード及びＶｓｓ端子間には、直列接続された３つのＮＭＯＳトランジスタＱＮ４〜ＱＮ６を有する。これらトランジスタＱＮ４、ＱＮ５、ＱＮ６は、それぞれ隣接する単位回路Ｕ４＜２＞のインバータＩＶ３の出力、信号Ｌ、クロックｃｋで制御される。

また、２つ目の単位回路Ｕ４＜２＞は、クロスカップルされたインバータＩＶ３及びＩＶ４を有する。

このうち、インバータＩＶ３の出力ノード及びＶｓｓ端子間には、直列接続された３つのＮＭＯＳトランジスタＱＮ７〜ＱＮ９を有する。これらトランジスタＱＮ７、ＱＮ８、ＱＮ９は、それぞれ隣接する単位回路Ｕ４＜１＞のインバータＩＶ２の出力、信号Ｌ、クロック／ｃｋで制御される。

一方、インバータＩＶ４の出力ノード及びＶｓｓ端子間には、直列接続された３つのＮＭＯＳトランジスタＱＮａ〜ＱＮｃを有する。これらトランジスタＱＮａ、ＱＮｂ、ＱＮｃは、それぞれ、隣接する３つめの単位回路Ｕ４＜３＞のインバータＩＶ５の出力、信号Ｌ、クロック／ｃｋで制御される。

以降、１つ目のユニット回路Ｕ４＜１＞と２つ目のユニット回路Ｕ４＜２＞と同様の単位回路Ｕ４が交互に接続された構成となっている。

この構成によって各単位回路Ｕ４間の各ノードｎが境界信号ｂ０〜ｂｍとなる。また、最初のインバータＩＶ１の出力が信号Ｆ、最後のインバータＩＶａの出力が信号Ｃとなる。

移動方向生成部Ｕ３は、図３３で示すように、フリップフロップ回路ＦＦで構成されている。つまり、移動方向生成部Ｕ３は、Ｆ及び／ｃｋを入力とするＮＡＮＤゲートＧ３、Ｃ及び／ｃｋを入力とするＮＡＮＤゲートＧ４、ＮＡＮＤゲートＧ３の出力を一方の入力とするＮＡＮＤゲートＧ５、並びにＮＡＮＤゲートＧ１４４の出力を一方の入力とするＮＡＮＤゲートＧ１４６を有する。ＮＡＮＤゲートＧ５の他方の入力と、ＮＡＮＤゲートＧ６の他方の入力は、それぞれＮＡＮＤゲートＧ５の出力と、ＮＡＮＤゲートＧ６の出力に接続されている。

移動方向生成部Ｕ３は、境界信号生成部Ｕ２の両端のノードｎ０、ｎｍの信号Ｆ及びＣによって状態の移動方向を決める信号Ｒ及びＬを発生させている。

以上説明した回路によって、「ｂｉｎａｒｙ ｗｏｒｌｄ」と「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」との間を往来させる扉は構成できる。

［リー・メトリック・コードの概要］
次に、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」でのデータ処理について説明する。ここでは、コードを構成する各桁を「コード語シンボル」と呼ぶものとする。

コード語シンボルｃは、数１８に示す整数となる。

［数１８］

これら整数のリー・メトリックを｜ｃ｜とし、全てのリー・メトリック｜ｃ｜をｐ／２以下の整数で表すとリー・メトリック｜ｃ｜の定義は数１９のようになる。

［数１９］

コードＣは、ｎ＝ｐ−１個のコード語シンボルｃの並びと考えられるため、図１にも示したようにＣ＝（ｃ_１，ｃ_２，…，ｃ_ｎ）で表すことができ、コードＣの計量ｗ（Ｃ）は数２０のように各コード語シンボルｃのリー・メトリック｜ｃ｜の和として定義される。

［数２０］

また、コード間の距離はコードに対応する各コード語シンボルの差のリー・メトリックの和で定義される。ここで２つのコードＣとＹの差（リー距離）ｄ_Ｌ（Ｃ，Ｙ）は数２１のようになる。

［数２１］

さらに、コードＣの最小リー距離は、数２２に示すようにコードＣの計量ｗ（Ｃ）の最小の計量で定義される。

［数２２］

このとき、リー・メトリック・コードは、数２３に示す生成行列Ｇ及びシンドローム行列Ｈを持ったコード間の最小距離が２γであり、且つ、γ−１以下のリー・メトリックのエラー訂正が可能なコードである。

［数２３］

ここで、コードＣのシンボル数をｎ、データ語Ｄのシンボル数をｋとすると、γ＝ｎ−ｋであり、γはコードＣに含まれる冗長なシンボル数を表している。

この様に構成されるリー・メトリック・コードを作るために入力変換されたデータであるｋ桁のｐ進数の桁の数をＺｐの数として、これをリー・メトリック・コードのデータ語Ｘとして、Ｇ行列から演算Ｃ＝ＸＧとしてコード表現が得られる。得られたコード語をメモリに記憶する。記憶したＺｐの数に生じたエラーの情報は、メモリから読み出したリー・メトリック・コードのデータ語Ｙとして、演算Ｓ＝ＹＨ^ｔ（Ｈ^ｔはＨの転置行列）からシンドロームを得て、エラーの位置と量が計算できエラーが訂正できる。

次に、リー・メトリック・コードを記憶するメモリセルとして最適なものを示すためにリー・メトリック・コードに現れる量の間の条件関係をまとめる。

Ｚｐのリー・メトリック・コードを用いると、「ｂｉｎａｒｙ ｗｏｒｌｄ」で２^ｈ進数δ桁のデータであるから、コードの語長をｎ、すなわちＣ＝（ｃ_１，ｃ_２，・・・・，ｃ_ｎ）、データの語長をｋ、訂正可能なエラーのリー・メトリックの最大値をε＝γ−１とするとき、δ＋１個のコードデータに対して、数２４のようなコードを作ることができる。

［数２４］

すなわち、ｋ＝δ＋１がリー・メトリック・コードでのデータの語長に相当することになる。

素数ｐの選択をδ＋１＝ｋとなるように決めて、更に、ｋ＝ｎ−γ＝ｐ−１−ε−１＝ｐ−ε−２から数２５が素数ｐの具備すべき条件となる。

［数２５］

ここで、素数ｐの条件をまとめると、訂正可能なエラーのリー・メトリックの総量をε、「ｂｉｎａｒｙ ｗｏｒｌｄ」でのＥＣＣ一括処理データビット数をＭとすると、Ｍ及びｐの選択条件は、δｈ＝Ｍと数２５から、数２６のようになる。

［数２６］

このとき、Ｚｐ上のコードとして、データとの冗長語長はγ＝ε＋１＝ｎ−ｋ＝ｎ−（δ＋１）であるから、「ｂｉｎａｒｙ ｗｏｒｌｄ」のデータの２^ｈ進数としての桁数δと、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」のコード語数ｎとの間には、数２７のような関係が成立する。

［数２７］

［ｐ−ａｄｉｃセル］
次に、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」でリー・メトリック・コードＣ＝（ｃ_１，ｃ_２，・・・，ｃ_ｎ）の各コードｃ_ｊを記憶するメモリセルについて説明する。

一つにつき複数の値の物理量を設定できるメモリセルで、この量が物理的に順序集合をなすメモリセルをＺｐの表現に対応させるときに、このメモリセルを「ｐ−ａｄｉｃセル」と呼ぶことにする。

ｐ−ａｄｉｃセルとしては、具体的には、ＭＯＳトランジスタの複数の閾値を物理量として用いるメモリセル、可変抵抗体の複数の抵抗値を物理量として用いるメモリセル、保持された磁束量子の数を物理量として用いるメモリセル、トラップされた電荷の量を物理量として用いるメモリセルなど、ある物理量を量設定の順序集合の一つの要素として保持できるメモリセルであれば何でもよい。以下において、物理量の順序を「レベル」と呼ぶことにする。

この様なメモリセルに対してレベルとＺｐの要素との割り付けを行ったメモリセルがｐ−ａｄｉｃセルとなる。

ｐ−ａｄｉｃセルへのＺｐの割り付け例を図３４に示す。この例は、一つのメモリセルにＺｐの表現の数と同じレベルを設定し、レベルと表現を割り付けたものである。つまり、セルユニットであるｐ−ａｄｉｃセルは、１つのメモリセルから構成されている。

図３４中ａ〜ｆは、それぞれ素数ｐとして７、１１、１３、１７、１９、２３の場合を示した例である。それぞれｐ個に区分された物理量の順序の区分に分けて、それぞれの区分をＺｐに割り付けている。

メモリセルのエラーとしては順序の近いレベル間で誤動作する可能性が高いので、リー・メトリックが近いものはレベルの順序で近いものを割り当てることになるが、これは必然的に物理量としてのレベルの順序とＺｐの表現としての順序を一致させることになる。Ｚｐの順序は巡回的であるので、１つのメモリセルに対する順序の割り付け方はｐ通り存在する。図３４に示したのは最低レベルを０に割り付けた場合であるが、Ｚｐのリー・メトリックによる順序が保たれるようなセルレベルとＺｐの表現が対応していれば、図３４に示す例以外の割り付けも利用できる。また、メモリセル毎にこの割り付け方が変わっても、セルアレイの外から見たリー・メトリック・コードの一貫性は維持できる。

レベル変化によるリー・メトリックの変化については図３４中ａに示すｐ＝７の場合に詳細に示した。変化量をｄＬ＝１、２、３とし、対応するレベルの跳びは矢印で示されている。いずれも対応するレベル変化の場合の数はｐ＝７である。

これはｐが素数であるので変化量とは互いに素であることによる。また、リー・メトリックの変化量としては（ｐ−１）／２以下しかないことに注意する。Ｚｐの順序が巡回的であることからｄＬ＝１や２では、破線で示す矢印のように、レベルとしての跳びの大きい誤動作が現れる可能性は低いと考えられる。

図３４中ａ〜ｆでは、リー・メトリックの変化量として、ε＝（ｐ−１）／４の場合とε´＝（ｐ−１）／３の場合とで、各ｐについて代表的なレベル変化を示した。これらのリー・メトリックとしての変化は物理的レベルの誤動作としては、いずれの素数ｐに対してもεとε´で各々ほぼ同じ量になる。したがって、同じ物理量を利用するメモリセルに対してｐを大きくすればコードのエラーも大きくなりエラー訂正可能量も大きくする必要がある。

次に、ｐ−ａｄｉｃセルの読み出し方法について図３５を用いて説明する。

言葉の定義として、「バイアスを区分的にシリアル印加する」とは、メモリセルのレベルにしたがって順番にバイアスを変化させることを言う。

ΔΣ変調（デルタシグマへんちょう）などを用いてセルレベルの物理量を直接センスすることも考えられるが、ここでは、メモリセルへの書き込みとベリファイも考慮して、メモリセルに与えるバイアスを区分的にシリアル印加してリファレンスの物理量Ｉｒｅｆと比較し、どのバイアスでＩｒｅｆを超えたかを検知するセンスの方式を用いる例について説明する。

図３５は、ｐ−ａｄｉｃセルからの読み出し動作に必要となるブロック構成である。

図３５には、ｐ−ａｄｉｃセルがアレイ状に配列されたｐ−ａｄｉｃセルアレイと、ｐ−ａｄｉｃセルから読み出した物理量をＩｒｅｆと比較するセンスアンプ部ｔ−ＳＡ、ｔ−ＳＡの結果に基づいて、ｐ−ａｄｉｃセルから読み出したデータを保持するレジスタ、センスアンプ部ｔ−ＳＡとレジスタを選択的に接続する“Ｚｐ→ｈ ｄｅｃ”回路ブロック、及びロウデコード／ワード線ドライバからなるコード読み出し部とが示されている。

ｐ−ａｄｉｃセルアレイでは、ＺｐのデータＡ＝（ａ_１，ａ_２，・・・，ａ_ｎ）の各コードａ_ｊを記憶するｐ−ａｄｉｃセルに同時にアクセスする。このアクセスの方法として、ワード線ＷＬとビット線ＢＬを使う従来の方法を想定し、１つのワード線ＷＬと複数のビット線ＢＬとのクロスポイントに設けられたｐ−ａｄｉｃセルにバイアスをかける。このバイアスは、電圧、電流、又はその他の物理量であって、センスアンプ部ｔ−ＳＡを用いてＩｒｅｆと比較可能な物理量としてビット線ＢＬに現すものである。

ワード線ＷＬの一端に設けられたロウデコーダ／ワード線ドライバ（Ｒｏｗ Ｄｅｃ．／ＷＬ Ｄｒｉｖｅｒ）は、ワード線ＷＬを選択し、このワード線に対して、読み出しに必要なバイアスを区分的にシリアル印加する。この際のバイアスの区分はｐ段階となる。

なお、このコード読み出し部のロウデコード／ワード線ドライバは、コード書き込みの際には、コード書き込み部の一部として、選択ワード線ＷＬに対し、コード書き込みに必要なバイアスを区分的にシリアル印加する。この際のバイアスの区分は、ｐ−１段階となる。

センスアンプ部ｔ−ＳＡは、Ｉｒｅｆとｐ−ａｄｉｃセルからの物理量Ｉｃｅｌｌとを比較する回路である。センスアンプ部ｔ−ＳＡは、図３５に示すように、ＩｃｅｌｌとＩｒｅｆとをセンスアンプｓａで比較し、先の比較結果をラッチＬ２に退避させた後、現在の比較結果をラッチＬ１に上書き保持する。

センスアンプ部ｔ−ＳＡの出力は、ラッチＬ１、Ｌ２のデータ内容が異なる時のみ信号Ｌとして‘１’を出力する。即ち、Ｉｃｅｌｌが順序にしたがって変化するときにＩｒｅｆとＩｃｅｌｌの順序関係が最初に逆転したシリアルサイクルでのみ出力Ｌが‘１’になる。なお、ラッチＬ１とラッチＬ２の初期値は両者同じにしておき、最初のＩｒｅｆとＩｃｅｌｌの比較の際に正しいセンス出力が得られるように準備しておく。

“Ｚｐ→ｈ ｄｅｃ”回路ブロックは、区分的にシリアル印加するバイアスを制御する信号Δ０、Δ１、・・・、Δｐ−２、Δｐ−１を入力とし、この入力に応じて、選択レジスタを指定するｈビットの選択線ＳＬ_０〜ＳＬ_ｈ−１を活性化させる。ワード線ＷＬによって同時に選択されたｎ個のｐ−ａｄｉｃセルに対応するセンスアンプ部ｔ−ＳＡの出力は、各々ｈ個のレジスタに選択的に接続されるが、この“Ｚｐ→ｈ ｄｅｃ”回路ブロックは、信号Δ０、Δ１、・・・、Δｐ−２、Δｐ−１に応じて活性化される選択線ＳＬ_０〜ＳＬ_ｈ−１によって、センスアンプ部ｔ−ＳＡとレジスタとの対応付けを行う。

レジスタは、信号ＲＳで、内容をリセット、つまり‘０’にし、信号ｊ及びセンスアンプ部ｔ−ＳＡから出力される信号Ｌが共に‘１’になった場合に内容を‘１’に置き換える。

以上のような構成において、ｐ−ａｄｉｃセルからの読み出し動作は以下のようになる。

データ読み出し前、レジスタの初期値は‘０’になっている。

ここで、レベル０から順にセンス動作を実行し、レベルｊのステップでのセンスアンプ部ｔ−ＳＡの出力Ｌが‘１’になったとする。同時に、レベルｊのステップでは、“Ｚｐ→ｈ ｄｅｃ”回路ブロックに活性化された信号Δ_ｊが入力されており、“Ｚｐ→ｈ ｄｅｃ”回路ブロックは、ｊをｈビットのバイナリに変換し、対応する選択線ＳＬを活性化させる。

これによって、信号Ｌと信号ｊは共に‘１’となり、対応するレジスタの内容は‘１’に書き換えられる。

以上の動作によって、ｐ−ａｄｉｃセルへの全てのステップが終了した時点で、レジスタにはｐ−ａｄｉｃセルに記憶されたＺｐの要素のバイナリ表示Ａが格納されている。このレジスタに格納されたＡが「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」での演算処理を受けることになる。

以上、Ｚｐの表現にｐ−ａｄｉｃセルを１セル用いる場合について説明した。しかし、選択したい素数ｐに対してメモリセルのレベルが不足する場合、ペアでｐ−ａｄｉｃセルを用いてレベル数を稼ぐことができる。以下では、このようにペアで用いられるｐ−ａｄｉｃセルを「ペアｐ−ａｄｉｃセル」（セルユニット）と呼ぶこともある。

そこで、ペアｐ−ａｄｉｃセルでＺｐを表現する方法について説明する。

１個のｐ−ａｄｉｃセルにｎレベルが設定可能とする場合、このｐ−ａｄｉｃセルをペアで用いるとｎ^２のレベルの設定が可能になる。このレベル数に素数ｐを対応付ける場合、ｐはｎ^２より小さく且つ因数分解できないとの条件から、許される素数の形はｐ＝ｎ^２−２、ｎ^２−３、ｎ^２−５、・・・となる。

ここで、ペアｐ−ａｄｉｃセルのレベルを最大限有効活用できる素数ｐについて考える。

図３６は、１個当たりのｐ−ａｄｉｃセルに設定可能なレベル数ｎと、ｎ^２、ｎ^２−２、ｎ^２−３、及びｎ^２−５との関係をまとめた表である。図３６中下線で示された数が素数となる。ｎが偶数の場合、素数はｐ＝ｎ^２−３又はｐ＝ｎ^２−５、ｎが奇数の場合、素数はｐ＝ｎ^２−２のタイプとなることはｎ^２の遇奇性から分かる。なお、図３６から、ｎ＝１１とした場合、ｎ^２−５までに素数は存在しない。

続いて、ペアｐ−ａｄｉｃセルのレベルについて説明する。ペアｐ−ａｄｉｃセルの各々のレベルからその組合せでレベルを設定する方法は種々考えられるが、基本的にはペアｐ−ａｄｉｃセルのいずれかのレベルが１変わればペアｐ−ａｄｉｃセルのレベルも１変わるように設定される。

ペアｐ−ａｄｉｃセルに設定された具体的な設定よりも、レベル間の距離の方が、エラー訂正の観点からは重要である。

図３７は、１１×１１の範囲のレベル間距離の行列を示した図である。図３７は、図中斜線で表した中心のレベルを基準にしてペアｐ−ａｄｉｃセルのレベルをいくつ跳び移れば対応するレベルになるかを示している。いわば中心のレベルから見た周りのレベルへの移り難さを表したものである。この数値が小さいレベル間では誤動作が生じやすい。この様なレベル間距離があるときに、Ｚｐの要素の順序とレベルとを如何に対応させるかについては、リー・メトリックの変化とレベル間距離との変化を近づけられるかがポイントとなる。

Ｚｐの要素をゼロを基点として±の数直線で−（ｐ−１）／２〜（ｐ−１）／２の範囲で表したとき、リー・メトリックは中心から見た両端が最大となる。

ここで、数直線をこの数値線の中心でガラが変わる紐と考え、この紐を如何に伸ばせばリー・メトリックが大きくならないかを考える。なお、図３７では紐のガラを実線と破線で表現している。

リー・メトリックが大きくならないためには、紐の両端がなるべくレベル距離の大きいところ、すなわち図３７に示す行列の角にきて、且つ、紐のガラの変更点ができるだけ紐の中心部分になるように配置すると良い。

この場合、図３７に示すように、紐を畳み込み、割付にできた余裕であるダミー部はゼロの中心部に繋げ、紐の中心部の対角線上で適当な位置にゼロを配置して紐が最短リー・メトリックで折り返された紐の部分と最短距離になるようにして、Ｚｐの変化が無い様にしてやるのが良い。

以上説明したＺｐの割付は、行列の中心のレベルからのレベル距離とリー・メトリックとが適合するように設定されたが、次は、他のレベル位置からのレベル距離との適合の効果を見る。

図３８、図３９は、共に斜線で示したレベルのペアｐ−ａｄｉｃセルに対して、レベル距離とＺｐの割付の数直線の紐の対応を示している。０の周辺には紐の対応する部分の近い部分が素直に畳み込まれている様子が分かる。したがって、ペアｐ−ａｄｉｃセルのレベルの変化がリー・メトリック・コードの変化に対して可能な限り適合されていることが分かる。

次に、素数ｐに対する割り付けの具体例について説明する。

１つのｐ−ａｄｉｃセルのレベル数が３、４、５、６、７、８、９、１０の場合の、素数ｐ＝７、１３、２３、３１、４７、６１、７９、９７の割り付けの具体例を図４０〜図４７に示す。図４０〜図４７は、図４８中ａで示すように、各行列表の縦軸が１つ目のメモリセル＜１＞のレベル、横軸が２つ目のメモリセル＜２＞のレベルであり、その組合せによって表されるペアｐ−ａｄｉｃセルにＺｐの要素（−（ｐ−１）／２〜（ｐ−１）／２）を割り付けている。

図４８中ｂ及びｃに示すように、εとε´は一定のレベル距離パターンを仮定して、そのときの最大リー・メトリック変化量を表す。すなわち、εは図４８中ｂに示すように、レベル距離２までの変化を対応可能なリー・メトリックであり、ε´はレベル距離３とレベル距離４の一部であるペアｐ−ａｄｉｃセルの両方がレベル距離２の変化をした場合に対応可能なリー・メトリックである。

図４０〜図４７に示す行列表の中で、実線がεに対応するＺｐ割り付け移動であり、破線がε´に対応する割り付け移動である。なお、ｐ＝３１までは如何なる変化に対してもε´で対応可能である。

次に、ペアｐ−ａｄｉｃセルからの読み出し方法の一例を説明する。

ペアｐ−ａｄｉｃセルの読み出し方法は、基本的には、図３５を用いて説明した単体のｐ−ａｄｉｃセルの読み出す方法と同様である。したがって、ここでは、異なる点を中心に説明する。

ペアｐ−ａｄｉｃセルを構成する個々の単体セルを見た場合、異なるレベルが設定されているので、これらを同時に読み出す。そこで同時に選択されるワード線ＷＬに対してペアｐ−ａｄｉｃセルを構成するセルアレイとしてメモリセル＜１＞からなるｐ−ａｄｉｃセルアレイ＜１＞と、メモリセル＜２＞からなるｐ−ａｄｉｃセル＜２＞を設ける。これらｐ−ａｄｉｃセルアレイ＜１＞、ｐ−ａｄｉｃセルアレイ＜２＞は物理的に区別されている必要はなく、少なくともセルアレイの構成上のアドレスの割付で決まる論理的な概念で区別されていれば良い。セルアレイに与えるバイアスとしては、図３５の場合と同様、Δ_０〜Δ_ｌ−１を区分的にシリアル印加する。ここで、ｌは１つのｐ−ａｄｉｃセルに設定できる最大のレベル数であり、例えば、図４０〜図４７に示した行列表の行又は列の数であるｎそのものである。

各ｐ−ａｄｉｃセルアレイにおいて、ＺｐのデータＡ＝（ａ_１，ａ_２，・・・，ａ_ｎ）の各コードａ_ｊを記憶するｐ−ａｄｉｃセルに同時にアクセスする。

ワード線ＷＬによって同時に選択された各ｐ−ａｄｉｃセルアレイのｎ個のｐ−ａｄｉｃセルに対応するセンスアンプ部ｔ−ＳＡの出力は、各々ｌ個のレジスタに選択的に接続される。

これらのレジスタとセンスアンプ部ｔ−ＳＡの出力Ｌの選択的接続を制御するのは、図３５の場合とは異なり、区分的にシリアル印加されるバイアスの印加タイミングに対応して‘１’となるｌ本の信号δ_０、δ_１、・・・、δ_ｌ−２、δ_ｌ−１となる。信号δ_ｊはｐ−ａｄｉｃセルのレベルに対応したバイアスであるため、レベルｊの検知ステップでセンスアンプ部ｔ−ＳＡの出力Ｌが‘１’であれば、対応するｐ−ａｄｉｃセルのレベルはｊということになる。

レジスタは、図３５の場合と同様、予め信号ＲＳによって‘０’に初期化されているが、センスアンプ部ｔ−ＳＡの出力信号Ｌとδ_ｊが共に‘１’になった場合、レジスタの内容は‘１’に設定される。メモリセルへの全ての検知ステップを終了した時点でレジスタにはメモリセルに記憶されたレベルが保持されている。

この保持された各メモリセルのレベルＬを、前述のＺｐとレベルとの対応行列表にしたがって、ペアｐ−ａｄｉｃセルを構成するメモリセル＜１＞、メモリセル＜２＞に対応するレジスタの内容の論理積（ＡＮＤ）を取り、対応するＺｐの要素を得る。得られたＺｐの要素に対しては、前述の“Ｚｐ→ｈ ｄｅｃ”回路ブロックを用いてｈビットのバイナリ表示にして、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」での演算処理を受ける。

次に、ｐ−ａｄｉｃセル及びペアｐ−ａｄｉｃセルのレベル数によるパフォーマンスの比較を行なう。

始めに、単体のｐ−ａｄｉｃセルを用いた場合に関し、図３４に示した具体例について、図５０に評価項目毎にまとめた。図５０に示す表の第１列目が評価項目となる。各評価項目は以下の通りである。

Ｌ： ｐ−ａｄｉｃセルのレベル数
ｐ： 使用する素数
ｈ： Ｚｐをバイナリ表示するために必要な最小ビット数
ε： （ｐ−１）／４より大きな最小の整数であり、エラー訂正できるエラーのリー・メトリック総量
ε´： （ｐ−１）／３より大きな最小の整数であり、エラー訂正できるエラーのリー・メトリック総量
ここで、ε及びε´は、ｐ−ａｄｉｃセルの設定レベル数に依らず、ｐ−ａｄｉｃセルのレベルを作る物理量の誤動作の量が、ほぼ一定であると仮定して設定している。

Ｍ： Ｍ＝ｈ（ｐ−ε−３）によって決定する値であり、ＥＣＣで一括処理を行う「ｂｉｎａｒｙ ｗｏｒｌｄ」のバイナリのデータ量
Ｍ´： Ｍ´＝ｈ（ｐ−ε´−３）によって決定する値であり、ＥＣＣで一括処理を行う「ｂｉｎａｒｙ ｗｏｒｌｄ」のバイナリのデータ量
δ： Ｍの２^ｈ進数としての桁数
δ´： Ｍ´の２^ｈ進数としての桁数
ｐ−１： リー・メトリック・コードのコード語を記憶するのに必要なｐ−ａｄｉｃセル数
ｌｏｇ_２Ｌ： ｐ−ａｄｉｃセルをバイナリを記憶する多値セルとした場合に、ｐ−ａｄｉｃセルに記憶できるビット数
Ｍ／ｌｏｇ_２Ｌ： 「ｂｉｎａｒｙ ｗｏｒｌｄ」でデータＭをｐ−ａｄｉｃセルと同じレベル数を持つ多値セルに記憶させる場合のメモリセル数
但し、Ｍ／ｌｏｇ_２Ｌは、ＥＣＣが設けられていないことを条件として算出している。

Ｍ´／ｌｏｇ_２Ｌ： 「ｂｉｎａｒｙ ｗｏｒｌｄ」でデータＭ´をｐ−ａｄｉｃセルと同じレベル数を持つ多値セルに記憶させる場合のメモリセル数
但し、Ｍ´／ｌｏｇ_２Ｌは、ＥＣＣが設けられていないことを条件として算出している。

冗長度： データＭを「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」でｐ−ａｄｉｃセルにＥＣＣを入れて記憶する場合のセル数と、同じデータＭを「ｂｉｎａｒｙ ｗｏｒｌｄ」で同じｐ−ａｄｉｃセルを多値セルとしてＥＣＣ無しで記憶する場合のセル数との比
冗長度´： データＭ´を「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」でｐ−ａｄｉｃセルにＥＣＣを入れて記憶するセル数と、同じデータＭを「ｂｉｎａｒｙ ｗｏｒｌｄ」で同じｐ−ａｄｉｃセルを多値セルとしてＥＣＣ無しで記憶する場合のセル数との比
ε／（ｐ−１）： εを用いた場合の最大訂正できるセル数の割合
ε´／（ｐ−１）： ε´を用いた場合の最大訂正できるセル数の割合
なお、図５０では、素数３や５では本実施形態に係るメモリとしての「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」を構成できないので、７以上の素数について示されている。

ここで、実用面からレベル数はせいぜい２０くらいまでとし、且つ、コスト的なメリットの観点からＥＣＣを入れた場合の冗長度を２以下として考えると、図５０中で点々で示した列が選択可能な範囲となる。この範囲において、ほぼ３０％の訂正率が確保されるため、かなり信頼性の高いメモリシステムが構築できると考えられる。

続いて、ペアｐ−ａｄｉｃセルに関し、図４０〜図４７に示した具体例について、図５１に評価項目毎にまとめた。図５１に示す表の第１列目が評価項目となる。評価項目のうち図５０に示す項目と異なる評価項目は以下の通りである。

Ｌ： ペアｐ−ａｄｉｃセルを構成する単体のメモリセルのレベル数
Ｌ^２−ｐ： ペアｐ−ａｄｉｃセルのレベルにＺｐを割り付けたときの余分なレベルであって、図４０〜図４７に示した具体例におけるＺｐの‘０’を冗長に割り付けたレベルの数
２（ｐ−１）： リー・メトリック・コードのコード語を記憶するのに必要なｐ−ａｄｉｃセル数
ここで、ｐ−ａｄｉｃセルはペアで利用されるため、図５０に示す表の２倍となる。

なお、図５１に示すεとε´は、図５０に示すεとε´とは異なり、ｐ−ａｄｉｃセルのレベルの変化距離を固定し、Ｚｐ割付の対応するリー・メトリックとして焼きなおしたもので、レベル数が多い場合はレベルを作る物理量の誤動作変化量は小さくなるものとして算出されている。即ち、レベルの多いセルは精度良く作られると仮定している。

さて、メモリセルのレベル数を余り多くすることができない場合にペアｐ−ａｄｉｃセルを利用するという前提のもと、実用的なＬとして１０以下と仮定する。したがって、素数ｐは１００以下となる。さらに、コスト的なメリットを考えて冗長度を２以下にすると考えると図５１中で点々で示した列が選択可能な範囲となる。この範囲において、訂正率がほぼ２０％確保されるため、かなり信頼性の高いメモリシステムが構築できると考えられる。

［ｐ−ａｄｉｃメモリシステムのデータ／コード処理手順］
次に、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」でのＥＣＣの演算について、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の入口での変換手順、Ｚｐデータとしてメモリシステムに入力されたコードをエンコードする手順、メモリシステムから読み出されたコードをデコードする手順、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の出口での変換手順についてまとめる。

ここでは、Ｚｐを決める素数であるｐ、ｐのバイナリ表示に必要な最少ビット数であるｈ、一括処理データの「ｂｉｎａｒｙ ｗｏｒｌｄ」での２^ｈ進数としての桁数であるδ、訂正可能なエラーのリー・メトリック総量であるε＝γ−１については決まっているものと仮定する。また、以下の説明においてｎ、ｋはそれぞれｎ＝ｐ−１、ｋ＝ｎ−γとする。

「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の入口における変換手順は、以下のようになる。

（手順０） 始めに、外部からメモリシステムに入力されたバイナリデータをｈビットずつまとめ、数２８に示す２^ｈ進数表現のδ桁のデータ語Ｄ（ｈ）に変換する（図５２のＳ１）。

［数２８］

続いて、数２８に示すデータ語Ｄ（ｈ）を、更に、数２９に示すｐ進数表現のδ＋１桁のデータ語Ｄ（ｈ）に変換する（図５２のＳ２）。

［数２９］

Ｚｐデータとしてメモリシステムに入力されたコードをエンコードする手順は、以下の通りである。

（手順１） 始めに、手順０によって得られたＺｐの要素ａ_０〜ａ_δにゼロを追加し、数３０に示すデータＤのｋ個の要素ａ_０〜ａ_ｋ−１とする。

［数３０］

続いて、このデータＤに生成行列Ｇを乗じてコードＣのｎ個のコード語成分ｃ_１〜ｃ_ｎを得る（図５２のＳ３）。各コード語成分の値は数３１に示す通りである。

［数３１］

最後に、このコード語成分ｃ_ｊをメモリセルに記憶する（図５２のＳ４）。

メモリシステムから読み出されたコードをデコードする手順は、以下の通り７つの手順に大別できる。なお、以下において手順の番号は、エンコードの手順を含めた通し番号となる。また、以下に示す手順２及び手順３は、Ｚｐの各要素（ｍ＝０〜ｐ−２）に対して繰り返すことに注意されたい。

（手順２） メモリセルから読み出したコードＹを読み出す（図５３のＳ５）。コードＹは数３２に示す構成となっている。ここで、ｅ_ｊは、コードＹの位置ｊにあるコード語シンボルのエラーのリー・メトリックを示す。

［数３２］

続いて、コードＹを構成するｎ個のコード語シンボルの値ｙ_ｊ（ｊ＝１〜ｎ）にｊ^ｍを掛けて、ｊ^ｍｙ_ｊをＺｐの数として計算する。シンボル値ｙ_ｊは多レベルのメモリセルの場合、レベルから求めることができる。また、一般のバイナリメモリならバイナリデータから得られる数である。コードＹにシンドローム行列Ｈの転置行列を乗じて数３３に示すように、シンドロームＳ_ｍ〜Ｓ_ｍ＋εからなるシンドローム系列^ｍＳ（＝^ｍＹＨ^Ｔ）を得る（５３のＳ６）。

［数３３］

（手順３） 始めに、訂正可能なシンボル数の上限ε（＝γ−１）に対して、η＝ε、ｕ＝ηＳ_ｍ ^−１を計算し、手順２で求めたシンドロームＳ_ｌからｕＳ_ｍ〜ｕＳ_ｍ＋εを求める。続いて、このｕＳ_ｍ〜ｕＳ_ｍ＋εから数３４に示す解探索多項式Ψ（ｘ）の係数ψ_ｊを順次計算する（図５３のＳ７）。

［数３４］

ここで、Ψ（ｘ）の次数がηである場合、つまりψ_η≠0の場合、手順５に進み解を得る。ψ_η＝０の場合、解無しとして処理を終了するか、訂正の可能性をさらに探索すべくη＝ε−１とおいて手順２を繰り返す。Ψ（ｘ）の次数がη、即ちψ_η＋１≠０且つψ_η≠０の場合、手順４に進み解を得る。一方、ψ_η＝０の場合、解無しとして処理を終了する。この手順３で処理できなくなった場合、対応できないエラー分布であるため、解無しとしてエラー訂正を中止する。

（手順４） 手順３でψ_ε≠０となって解を得られることが分かった場合、手順４、手順５で解を得る。先ず手順４では解の多重度を得るために、数３５に示すハッセ（Ｈａｓｓｅ）微分多項式［Ψ（ｘ）］^［ｉ］を求める。手順３で得られた係数ψ_ｊに対して、一連の２項係数を乗じることで掛けることでハッセ微分多項式の係数が得られる（図５３のＳ９）。

［数３５］

（手順５） 得られたハッセ微分多項式に対して、Ｚｐの要素１〜ｐ−１を代入して、０次微分多項式（＝Ψ（ｘ））がゼロとなる要素ｒを全て求める。続いて、数３６に示すように、各ｒに対してｎ−１次微分多項式はゼロであるが、ｎ次微分多項式はゼロでない次数ｎを求める（図５４のＳ１０）。

［数３６］

得られたｒは、エラーが生じたコードのコード語シンボルの位置の逆元であり、それに対応するｎは、生じたエラー量から変換された量となる。

（手順６） 手順６では、解の多重度ｎからエラー量を変換で求める。エラーのあるコード語シンボルの位置はｔ＝ｒ^−１となり、解を得るための多項式を得るために行なった変換の逆変換をｎに施すことになる。ｕｔ^ｍｅ_ｔ＝ｎの関係があるので、ｅ_ｔ＝（ｕｔ^ｍ）^−１ｎとすればｎから本来のエラー量ｅ_ｔを得ることができる。このエラー量ｅ_ｔをメモリセルから読み出したコードＹのシンボル値ｙ_ｔから引いて、訂正されたコードＣのシンボル値ｃ_ｔを得る（図５４のＳ１１）。

ここまでで、メモリセルに記憶された正しいコードＣが得られたので、手順７、手順８によって、メモリシステムに入力されたバイナリデータを求める。

（手順７） 手順６によってエラー訂正されたコードＣと生成行列Ｇから、ＸＧ＝Ｃなる多元連立一次方程式を介して、ｋ個のＺｐの要素ａ_０〜ａ_ｋ−１とＸ（＝ａ_０，ａ_１，・・・ａ_ｋ−１）を求める。これによって、δ＋１個のＺｐの要素ａ_０〜ａ_δが得られたことになる。得られた要素ａ_０〜ａ_δから、δ＋１桁のｐ進数表現のデータ語Ｄ（ｈ）を作る（図５４のＳ１２）
（手順８） 最後に、このデータ語Ｄ（ｈ）をδ桁の２^ｈ進数表現に変換し、各桁の数字をバイナリ表現にする。以上によってメモリシステムに入力されたバイナリデータの復元が完了する（図５４のＳ１３）。

次に、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」でのデータ処理の手順で用いた方法の原理を説明しておく。この原理は従来の方法を改良したもので「シンドローム変換法」と呼ぶことにする。

メモリシステムに保持されたコード語Ｃの成分は、Ｚｐの数であり、成分毎に様々な擾乱を受けて変化を起こし、数３７に示すように、異なる成分からなるコード語Ｙへと変化する。

［数３７］

このＹからＣを復元するのがデコードである。デコードに先立ちシンドロームを求める。

シンドローム^ｍＳは、あるｍをＺｐから選択して、^ｍＳ＝（Ｓ_ｍ＋ｌ）（ｌ＝０〜γ−１）とし、ｍ＝０よりＳ_０を得て｜Ｓ_０｜≦γ−１ならデコードを開始する。シンドローム^ｍＳは、Ｈ行列を利用して数３８のような行列演算によって、要素がＳ_ｍ＋０、Ｓ_ｍ＋１、・・・、Ｓ_{ｍ＋γ＋１}として求まる。

［数３８］

ここで、Ｈ^ｔはＨの転置行列である。これはＧ行列とＨ行列の構成がＧＨ^ｔ＝０（ｍｏｄ ｐ）となるように構成されていることより、Ｙ＝Ｃ＋Ｅとおくと、ＳはＥの成分で表せる。なお、ｍ＝０として、Ｅ＝（ｅ_１，ｅ_２，・・・，ｅ_ｎ）とすると、Ｓ_０＝Σｅ_ｊとなっていてＳ_０は各シンボルのエラーの総和になっている。｜Ｓ_０｜≦γ−１の場合、以下のシンドローム変換法でエラーを求めることができる。この条件を満たさなくても計算上はコード成分に対するエラーの値を得るが、真のコードに対するエラーか、或いは隣のコードに対するエラーかを判別できないため、エラー訂正に用いることはできない。これはコード間のリー・メトリックの最小値が２γであることによる。

エラー訂正に利用できることが確実な場合、次にコード語のエラーの成分ｅ_ｉの計量を全て一括して変換する。有限体の固定した要素と全ての要素との積を作ることにより有限体の全ての要素が得られることを利用して、予め定めた要素ηに対して｜Ｓ_ｍ｜≠０となるｍに対して、ｕＳ_ｍ≡ηなるｕを求める。メモリセルアレイに記憶されたエラーを含むコードＹにこのｕを乗じてシンドロームを求めると、^ｍＳにｕを乗じた成分のシンドローム成分としてｕＳ_ｍ、ｕＳ_ｍ＋１、・・・、ｕＳ_{ｍ＋γ＋１}を得る。これをｕＳと表記する。つまりｕＳは数３９のように表わすことができる。

［数３９］

変換された後では、変換後のエラーの総和ｕＳｍがηになっていることに注意する。また、この総和からエラーの成分ｅ_ｊがｕ（ｊ）^ｍｅ_ｊとみなせることも分かる。これらのシンドロームが唯一のエラーの情報であり、これを元に正しいコードの復元を行う。

続いて、デコードの原理をエラーが予め分かっているとして説明する。

メモリセルアレイに記憶されたコードは、エラーＥ＝（ｅ_１，ｅ_２，・・・，ｅ_ｎ）（ｎ＝ｐ−１）を持つので、新たなシンドロームにといって仮想的なエラーは｛ｕ（１）^ｍｅ_１，ｕ（２）^ｍｅ_２，・・・，ｕ（ｎ）^ｍｅ_ｎ｝となる。これらｎ＝ｐ−１個のエラー成分を変換したものを２つの組Ｊ_＋とＪ₋に数４０のように分類する。

［数４０］

すなわち、エラーコード語シンボルのエラー量がｕ（ｊ）^ｍｅ_ｊ＜ｐ／２の場合、コード語シンボルｃ_ｊの位置ｊの集まりであるＪ_＋と、エラーコード語シンボルのエラー量がｕ（ｊ）^ｍｅ_ｊ＞ｐ／２の場合のコード語シンボルｃ_ｊの位置ｊの集まりであるＪ₋とに分類される。ＧＦ（ｐ）上の多項式Λ（ｘ）、Ｖ（ｘ）をこれらの組をもとに数４１のように構成する。

［数４１］

このように、多項式Λ（ｘ）はＪ_＋のエラー成分位置ｊの逆数を根として持ち、そのエラー成分のリー・メトリックであるｕ（ｊ）^ｍｅ_ｊを根の多重度として持つ多項式となる。一方、多項式Ｖ（ｘ）はＪ₋のエラー成分位置ｊの逆数を根として持ち、そのエラー成分のリー・メトリックｐ−ｕ（ｊ）^ｍｅ_ｊを根の多重度として持つ多項式となる。デコードは、最終的にこれらの多項式をシンドロームの情報のみから構成して解くことによってエラーの情報を得る過程となる。つまり、これら多項式Λ（ｘ）、Ｖ（ｘ）とシンドロームとの関係を求める必要がある。各シンドロームｕＳをその次数の係数に持つ級数多項式で構成すると、数４２のように、エラー成分の位置と仮想エラー成分の値をその因子に持つ有理多項式で表わされる。

［数４２］

数４２から、多項式Λ（ｘ）、Ｖ（ｘ）、シンドロームＳ（ｘ）の間には数４３に示す関係式が成立する。

［数４３］

続いて、数４３に示す関係式を利用して、シンドロームＳ（ｘ）から多項式Λ（ｘ）、Ｖ（ｘ）を求める。

シンドロームＳ（ｘ）から、数４４に示す次数がγ−１以下の多項式Ψ（ｘ）を求める。

［数４４］

多項式Ψ（ｘ）の展開式において、数４４に示す式の両辺の同次次数の係数の比較から、係数ψ_ｊは、シンドロームＳ_ｉと既に求まっている係数ψ_ｊ−１とを用いて反復法で求めることができる。シンドロームｕＳ_１〜ｕＳ_{ｍ＋γ−１}から多項式Ψ（ｘ）の係数ψ_０〜ψ_γ−１を求めた結果を数４５に示す。

［数４５］

この多項式Ψ（ｘ）はΛ（ｘ）／Ｖ（ｘ）に等価な多項式であるが、互いに素なλ（ｘ）とｖ（ｘ）のキー条件は数４６のようになるため、ηをうまく選択することでＶ（ｘ）＝１とでき、Ψ（ｘ）をΛ（ｘ）そのものとして採用することができる。

［数４６］

多項式の次数に関する条件ｄｅｇ λ（ｘ）−ｄｅｇ ｖ（ｘ）＝η、ｄｅｇ λ（ｘ）＋ｄｅｇ ｖ（ｘ）≦γ−１から０≦２ｄｅｇ ｖ（ｘ）≦γ−１−ηなので、０≦γ−１−η≦１ならｄｅｇ ｖ（ｘ）＝０になることが分かる。即ち、γ−１≧η≧γ−２の場合、Ｖ（ｘ）＝１且つΛ（ｘ）＝Ψ（ｘ）とできて、Ψ（ｘ）はこの条件を満たす。このときシンドロームから求めたΨ（ｘ）が予め決めたηとη＝ｄｅｇ Ψ（ｘ）＝ｄｅｇ Λ（ｘ）が成立するはずである。成立する場合、キー条件を全て満たすため、Ψ（ｘ）を用いて解を得ることができる。一方、不成立の場合、エラーがキー条件を満たさず、解無しとなる。

この方法は全てのエラーコード成分位置を集合Ｊ_＋に集める変換をエラーに対して施せることに相当する。また、別の観点からは変換したエラーの総和がγ−１以下、γ−２以上になるように変換することによってエラー修正ができるようになる可能性があることを示す。

ここで、可能性と言ったのはふたつの意味があり、第１は、全てのエラー成分位置がＪ_＋に集められて、シンドロームから求めたΨ（ｘ）の次数がちょうどηに等しいことが必要だからである。第２は、｜Ｓ_０｜≦γ−１でなくても計算上はエラー量を得ることができるが、誤訂正を排除するためにこの条件を加える必要があるからである。

次の例で示すように１コード語成分のエラーに対してはどのようなエラーに対してもこの方法で解を得られ、２コード語成分についてはシンドロームを循環的に用いることでどのようなエラーにもこの方法で解を得られることが分かる。

解探索では、Λ（ｘ）＝Ψ（ｘ）、Ｖ（ｘ）＝１とおいてＺｐの要素から方程式を満たす解を見つけ、得られた根の多重度とから、逆変換を施して真のエラーＥを得る。

次に、エラーの計量を変換して解探索多項式を求めるシンドローム変換法で、根の数すなわちエラーを生じたコード語の成分の数に対してどの様なエラーが探索できるか検討する。

始めに、解探索多項式から得られる根が１根の場合について検討する。

根をｊ^−１とするとエラーコードＥ＝（０，ｅ_ｊ，…，０）（ｎ＝ｐ−１）の成分位置はｊであり、そのエラー量はｅ_ｊである。適当なｕ（ｊ）^ｍを乗じて変換し、これらが各々ｐ／２以下でＪ_＋＝｛ｊ；ｕ（ｊ）^ｍｅ_ｊ＜ｐ／２｝にまとまれば、数４７に示す多項式Ψ（ｘ）が構成できる。

［数４７］

数４７からエラーの量に拠らず必ずｕ（ｊ）^ｍｅ_ｊ＝ηとなりＪ_＋に入る。したがって１コード語のエラーは完全にその値を得ることができるが、コード語間の最小距離が２γであるので、｜ｅ_ｊ｜がγ以上では真のコード語を特定できず、ｍの選択によって様々な値のエラー量を得ることになる。各々のエラー量がコード語に対し、そのうちの一つが真のコード語からのエラーとなる、いわゆるリスト訂正となる。

続いて、解探索多項式から得られる根が２根の場合について検討する。

根をｉ^−１とｊ^−１とするとエラーコードＥ＝（０，…，ｅ_ｉ，…，ｅ_ｊ，…，０）（ｎ＝ｐ−１）の成分位置はｉとｊであり、それらのエラー量はｅ_ｉとｅ_ｊである。適当なｕ（ｊ）^ｍを乗じて変換し、これらが各々ｐ／２以下になりＪ_＋＝｛ｉ，ｊ；ｕＵ（ｉ）^ｍｅ_ｉ，ｕ（ｊ）^ｍｅ_ｊ＜ｐ／２｝にまとまれば、数４８のΨ（ｘ）が構成できるので、多項式Ψ（ｘ）からエラー量を求めることができる。

［数４８］

適当なｕ(ｊ)^ｍをエラーコードに乗じて変換し、これらが各々ｐ/２以下になりＪ_＋にまとまるには、ｅ_ｉとｅ_ｊが一定の関係を持たねばならない。これは両者が等しければ十分であり、等しければｕ（ｊ）^ｍによる変換でどの様なエラー量もηにできるため、２コード語成分のエラーは完全にその値を得ることができる。

しかし、コード語間の最小距離が２γであるのがリー・メトリック・コードであるから、｜ｅ_ｉ｜＋｜ｅ_ｊ｜がγ以上では真のコード語を特定できず、ｍの選択によって様々な値のエラー量を得ることになる。各々のエラー量がコード語に対応し、そのうちの１つが真のコード語からのエラーとなる。ちなみに、２つのエラーの距離がある条件を満たせば適当な変換によって両者をＪ_＋にまとめられるので、両者が等しいは必要条件ではない。

次に、２コードのエラーを等しくする変換方法について説明する。

２つのエラーコードをｉ、ｊとし、それぞれにエラー量をｅ_ｉ、ｅ_ｊとする。この場合、シンドロームは、Ｓ_０＝ｅ_ｉ＋ｅ_ｊとなる。更にシンドローム計算から分かるように、シンドロームは、Ｓ_ｍ＝ｉ^ｍｅ_ｉ＋ｊ^ｍｅ_ｊとなる。つまり、適当なｍを選択することで、ｉ^ｍｅ_ｉ≡ｊ^ｍｅ_ｊとすることができる。

ここで、Ｚｐの原始根と指数表示を用いてｅ_ｉ＝α^（ｅｉ）、ｅ_ｊ＝α^（ｅｊ）、ｉ＝α^（ｉ）、ｊ＝α^（ｊ）とすると、ｍ（ｉ）＋（ｅ_ｉ）≡ｍ（ｊ）＋（ｅ_ｊ）が成立する。したがって、ｍは、ｍ≡−｛（ｅ_ｊ）−（ｅ_ｉ）｝／｛（ｊ）−（ｉ）｝によって求めることができる。

以上から、シンドロームの系列（Ｓ_ｍ，Ｓ_ｍ＋１，…，Ｓ_{ｍ＋γ−１}）を用いて、ｕＳ_ｍ＝ηとなる係数ｕを求めれば良い。

しかし、ｍは当初不明であるため、２つのコード語シンボルの様々なエラーに対応するには、次のような変換方法を用いる。最初に、ｍを０からｐ−２までスキャンし、各ｍに対する係数ｕをｕ＝ηＳｍ^−１によって算出する。これによって、（ｕＳ_ｍ，ｕＳ_ｍ＋１，…，ｕＳ_{ｍ＋η−１}）を求めることができる。続いて、これら（ｕＳ_ｍ，ｕＳ_ｍ＋１，…，ｕＳ_{ｍ＋η−１}）から多項式Ψ（ｘ）を構成する。最後に、構成された多項式Ψ（ｘ）のうち、ｄｅｇ Ψ（ｘ）＝ηを満たすｍを抽出する。以上によって抽出されたｍのときにΨ（ｘ）を構成してｄｅｇ Ψ（ｘ）＝ηとなったらそのｍのときにΨ（ｘ）を用いて根と多重度を求める。

以上のように、解探索多項式の根が２根以下すなわち２コード語成分のエラー以下ならどの様なエラーでも求めることができる方法が得られたが、次は、３根以上の場合についてはどうなるかを検討する。

３根以上で解が得られる条件は全ての根のエラー量を変換してＪ_＋＝｛ｊ；｛ｊ∈（１，２，・・・，ｎ）；ｕ（ｊ）^ｍｅ_ｊ＜ｐ／２｝に属するようにできることであり、このとき数４９に示すようにΨ（ｘ）がη次の多項式として構成される。

［数４９］

どの様なエラー量に対してもこの様にできる変換は、２根以下では存在するが、３根以上では簡単な変換として構成することは困難である。そこで２コード語成分以下のエラーが生じている場合にはどの様なエラーに対しても対処できる方法として、前述の２根の場合の変換と解探索の方法をそのまま用いる。但し、３根以上のエラー成分がＪ_＋にまとまるエラー分布の場合を増やすために、新たなスキャンとして、ηのもうひとつの候補γ−２＝ε−１に対しても同じ方法を繰り返し適用する。

即ち、ηをεとε−１の各ηに対してｍを０からｐ−２と順に変えてｕ≡ηＳ_ｍ ^−１として（ｕＳ_ｍ，ｕＳ_ｍ＋１，・・・，ｕＳ_ｍ＋ε）→Ψ（ｘ）とし、ｄｅｇ Ψ（ｘ）＝ηならΛ（ｘ）＝Ψ（ｘ）から解が得られる。これを解いて解探索終了。ｄｅｇ Ψ（ｘ）≠ηなら解けないエラー分布であり、解無しとして終了する。

この解法の中には２根や１根の解法が含まれ、２根以下ならコード語成分にランダムに生じた如何なるエラーでも計算ができる。３根以上のコード語成分のエラーでは、エラー量の分布が狭いなど特殊な場合については、最大ε＝γ−１コード語成分の訂正が可能である。特にエラー量の分布が、全てのエラー量が等しいか同じ様な値に集中している場合については、２根以下の場合と同じであるのであらゆる種類のエラーが生じてもコード語成分の計算が可能ある。しかし誤訂正を考慮すると、真のコードへの訂正はΣ｜ｅ_ｊ｜≦εの場合のみとなり、他の場合には様々なコードに対するエラー量、即ち誤訂正のエラーが得られ、この中に真のコードからのエラーが存在することになる。

また、ηの選択を２つにしたスキャンによって３コード語成分以上のエラー分布でＪ_＋にまとめる変換の場合が増えるため、訂正できる場合が増えることは確実であるが、どの様な分布がさらに訂正可能となるかは明確ではない。

なお、３根以上の場合にはε以下のエラーに対して、従来のユークリッド（Ｅｕｃｌｉｄ）法で解探索多項式を求められる全ての場合に対してＪ_＋への変換ができるわけではないため、シンドローム変換法で対応できるわけではない。しかし、エラーの成分のエラー量のパターンが似ている場合には差はなく、シンドローム変換法で３根以上でも容易に対応できる点は大きなメリットとなる。

ｐ−ａｄｉｃセルのようにエラーの量が各メモリセルで似ている場合には処理の規模と計算がより簡略化され、オンチップシステムとして有効になる。

無論、シンドローム変換法と従来のユークリッド法とを併用することで、訂正できるエラー分布の範囲を向上させることができる。しかし、ユークリッド法で複雑な演算処理と回路を用いるため、回路規模の簡略化と処理の高速化が損なわれてしまう。また、リー・メトリック・コードを用いたメモリシステムの解探索にユークリッド法をそのまま用いることができるのも当然である。

［ｐ−ａｄｉｃメモリシステムの構成］
次に、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」のリー・メトリック・コードを用いた本実施形態に係るメモリシステムの構成について説明する。

図５５は、本実施形態に係るメモリシステムのブロック図である。

「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」において、メモリシステムの最大のメリットは、リー・メトリック・コードを用いたＥＣＣを利用することができる点である。したがって、ＥＣＣ利用を前提としてメモリシステムを構成している。

本メモリシステムは、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の入口処理を実行する部分、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」における処理を実行する部分、及び「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の出口処理を実行する部分の３つの部分に大別することができる。

「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」への入口処理を実行する部分として、ｐ進数変換部１０１がある。このｐ進数変換部１０１は、後述するエンコード部２０１と共に、コード生成部に含まれる。入力された「ｂｉｎａｒｙ ｗｏｒｌｄ」のバイナリデータＤは、最初、このｐ進数変換部１０１によってｐ進数変換された上でデータＡとして「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」に入力される。

「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」における処理を実行する部分には、エンコード部２０１、ｐ−ａｄｉｃセルメモリ部２０２、エラー検出・訂正部（２０３〜２０６）、及びデコード部２０７がある。

エンコード部２０１では、ｐ進数変換部１０１から入力されたデータＡに対し生成行列Ｇを作用させてリー・メトリック・コード化し、書き込みコードＣとしてｐ−ａｄｉｃセルメモリ２０２に記憶保持する。

ここで、ｐ−ａｄｉｃセルメモリ２０２は、フラッシュメモリ、ＰＲＡＭ、ＲｅＲＡＭ等の大容量記憶メモリである。

ｐ−ａｄｉｃセルメモリからデータを読み出す際には、コード化されたデータＣはエラーを含み読み出しコードＹとして読み出される。

シンドローム生成部２０３では、シンドローム^ｍＳの計算をシンドローム行列Ｈと、Ｙの各コード語成分の位置に合わせてその場所の座標数のｍ乗を掛ける処理を数５０に示す対角行列を用いて行なう。

［数５０］

そこでｍ＝０として、^ｍＳ＝０の場合、エラーが生じていないので、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」における最後の処理のステップをすべくコードＹをデコード部２０７に出力する。一方、^ｍＳ≠０の場合、ｍ＝０の場合の^ｍＳの最初の成分Ｓ_０が｜Ｓ_０｜＞γなら、エラー訂正は確実には不可能なのでＮＧ信号を出力した上で、エラー込みのコードＹをデコード部２０７に出力する。その他の場合には、シンドローム^ｍＳを解探索多項式生成部２０４に出力する。

解探索多項式生成部２０４では、このシンドローム^ｍＳからη＝γ−１として解探索多項式Ψ（ｘ）を求め、そのη次の次数の係数がψ_η≠０の場合、そのψ（ｘ）をハッセ微分多項式生成部２０５に出力する。一方、ψ_η＝０の場合、η＝γ−２として再び多項式Ψ（ｘ）を求める。そして、その多項式Ψ（ｘ）のη＋１次の次数の係数ψ_η＋１＝０の場合、η次の次数の係数ψη≠０ならΨ（ｘ）がη次であるのでΨ（ｘ）をハッセ微分多項式生成部２０５に出力する。一方ψη＝０なら、ｍを１つ増やしながらシンドローム^ｍＳを求める処理を繰り返す。そして、ｍがｐ−２になるまで繰り返してもΨ（ｘ）のη次の係数ψ_η＝０なら、エラー訂正は不可能であるのでＮＧ信号を出力した上で、エラー込みのコードＹをデコード部２０７に出力する。

ハッセ微分多項式生成部２０５では、入力されたΨ（ｘ）からハッセ微分多項式を求め、これらの根ｒとその根の多重度ｎを算出し、ｔ＝ｒ^−１としてコード復元部２０６に出力する。

コード復元部２０６では、この算出された根ｒとその根の多重度ｎを用いてエラーの生じたコード語の位置座標と、エラー量ｅ_ｔを求めて、エラー量のリー・メトリックの総量Σ｜ｅ_ｔ｜を算出する。これがγ−１以下ならリー・メトリック・コードのコードデータＣを復元する。一方、γ以上なら誤訂正の可能性があるため、訂正不可能と考え、次のη或いは次のｍについて処理すべく、シンドローム生成部２０３或いは解探索多項式生成部２０４に処理を移す。但し、ｍ＝ｐ−２でη＝γ−２の場合には、ＮＧ信号を出力した上で、デコード部２０７に処理を移す。

デコード部２０７では、コードデータＣに生成行列Ｇの逆変換を実行し、ｐ進数を得てコードＡを得る。このコードＡは、「ｂｉｎａｒｙ ｗｏｒｌｄ」に出力される。

「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の出口処理を実行する部分として、２^ｈ進数変換部３０１がある。

２^ｈ進数変換部３０１では、コードＡを２^ｈ進数へとバイナリ表現の出力データに変換して出力する。これが復元されたバイナリデータＤとなる。

ここからは、「ｐ−ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の各ブロックの回路構成について具体例を示して説明する。

図５６中（Ａ）は、エンコード部２０１の回路構成例である、図５６中（Ｂ）は、エンコード部２０１を制御する２重のクロックｃｋとｃｌを示す図である。

図５６中（Ｂ）に示すように、クロックｃｌは、ｃｋの立ち上がりに遅れて立ち上がるパルスであり、クロックｃｋ毎にｃｌ_０〜ｃｌ_{ｐ−ε−３}の合計ｐ−ε−２発のｃｌが順次立ち上がる。そして、ｃｌ_{ｐ−ε−３}が立ち上がると、これに遅れて次にクロックｃｋが立ち上がる。同様の波形がｃｋ_０からｃｋ_ｐまで繰り返される。

これらクロックｃｋ、ｃｌのうち、ｃｋは“Ｃｏｕｎｔｅｒ（１ ｔｏ ｐ−１）”回路ブロック及び“Ｒｉ（１〜ｐ−１）”レジスタ部を制御し、ｃｌは、“Ｘ ｋ−ｔｉｍｅｓ”回路ブロック、“Ｒｏ（０〜ｋ−１）”レジスタ部、及び“Ｒｇｓｔｒ”レジスタ部を制御する。

“Ｃｏｕｎｔｅｒ（１ ｔｏ ｐ−１）”回路ブロックは、初期状態が０で、クロックｃｋが立ち上がる毎に改めてクロック数を数えて出力する回路である。すなわちｃｋ_ｊ（ｊ＝１〜ｐ−１）のうち、ｃｋ_ｊの立ち上がりでｊを“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックに出力する。

“Ｒｉ（１〜ｐ−１）”レジスタ部は、コード語Ｃの成分ｃ_ｊを記憶するレジスタで、合計ｐ−１個の数を記憶することができる。この“Ｒｉ（１〜ｐ−１）”レジスタ部は、ｃｋの立ち上がりのタイミングに合わせて順次個々のレジスタに数を記憶していく。即ちｃｋ_ｊ＋１の立ち上がりのタイミングで要素ｃ_ｊとなるデータをレジスタに取り込む。ｃｋ_ｐの立ち上がりによって、レジスタにｐ−１個の要素ｃ_ｊが取り込まれる。つまり、コード語Ｃを記憶することができる。

“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックは、クロックｃｌが立ち上がる度に出力に入力を乗じる回路である。“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックでは、入力されるｊを合計ｐ−ε−２回のｃｌの立ち上がりの度に出力に乗じる。即ち、ｃｌ_ｉ（ｉ＝０〜ｐ−ε−３）の立ち上がりによって、“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックの出力は（ｊ）^ｉ＋１となる。この出力は“Ｘ Ｚｐ”回路ブロックに出力される。

“Ｒｏ（０〜ｋ−１）”レジスタ部は、ｋ個の数を記憶できるレジスタであり、初期状態では、コードＡのｋ＝ｐ−ε−２個の成分ａ_０〜ａ_{ｐ−ε−３}を記憶している。“Ｒｏ（０〜ｋ−１）”レジスタ部には、クロックｃｌが入力されており、このクロックｃｌが立ち上がる度にコードＡの成分ａ_０〜ａ_{ｐ−ε−３}を順次出力する。即ち、ｃｌ_ｉ（ｉ＝０〜ｐ−ε−３）を受けてａ_ｉを出力する。

“Ｘ Ｚｐ”回路ブロックは、入力の掛け算をＺｐで行なう回路である。“Ｘ Ｚｐ”回路ブロックには、クロックｃｌ_ｉ毎に“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックの出力（ｊ）^ｉ＋１と“Ｒｏ（０〜ｋ−１）”レジスタ部の出力ａ_ｉが入力され、（ｊ）^ｉ＋１ａ_ｉを出力する。この出力された数（ｊ）^ｉ＋１ａ_ｉを加算していくのが、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック及び“Ｒｇｓｔｒ”レジスタの組み合わせである。

“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックは、２つの入力の数の和をｐを法として求める回路である。一方、“Ｒｇｓｔｒ”レジスタは、初期状態が‘０’でクロックｃｌの入力毎に、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックからの入力を遮断し、自身が保持する内容を“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックに出力するレジスタである。図５６に示すような、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック及び“Ｒｇｓｔｒ”レジスタの接続によって、クロックｃｌの入力毎に前回出力した数に新たな“Ｘ Ｚｐ”回路ブロックから出力される数を加算していく。即ち、クロックｃｌ_０〜ｃｌ_{ｐ−ε−３}が立ち上がると、コードＡをリー・メトリック・コードに変換した後のＣの成分ｃ_ｊが、クロックｃｋ_ｊのサイクルで出力される。これが次のｃｋ_ｊ＋１のサイクルの頭で“Ｒｉ（１〜ｐ−１）”レジスタ部に保持される。これによって、コードＡから変換されたコードＣを得ることができる。

次に、図５６に示された“Ｘ Ｚｐ”回路ブロックを構成する積演算回路について説明する。

始めに、Ｚｐでの数の掛け算を行なう回路の原理の説明を行なう。

Ｚｐの２つの数ａとｂをそれぞれｈビットでバイナリ表示したときの各ビットは数５１のように表示し、各ビットの積をｈ×ｈの要素のＭ_ａｂで表す。

［数５１］

ただし、ｈはｐをバイナリ表示できる最小のビット数とする。

ここで、使用する計算の根拠となる２つの事項を挙げる。

（第１の事項） ０≦ａ、ｂ≦ｐ−１から、０≦ａ／２＋ｂ≦３／２（ｐ−１）＜２（ｐ−１）となる。つまり、Ｚｐのｈビットバイナリ表示の一方の数の最下位ビットを無視し、桁を１桁ずらしてｈ−１ビットバイナリの数とみなしたものと、ｈビットで表される数とを加えた場合でも、その和には、ｐが高々１つ含まれるのみである。したがって、この和をｐが法としてみればｈビットのバイナリで表示することができる。

（第２の事項） ０≦ａ≦ｐ−１から、２ａ＋１≦２ｐ−２＋１＝２ｐ−１となる。つまり、ｈビットバイナリ表示の数に最下位ビットを加えてｈ＋１ビットの数にした場合でも、その和には、ｐは高々１つ含まれるのみである。したがって、この和をｐを法としてみればｈビットのバイナリで表示することができる。

そこで、これら２つの事項を利用して計算を行う。

数５２は、上記第１の事項を利用した前半の計算ステップ群である。なお、上記第１の事項を利用した部分については下線を付している。また、図５７は、前半の計算ステップ群を、模式的に示した図である。

［数５２］

前半の計算ステップ群の第１のステップでは、始めに、数５２中の（ｂ）式に示すように、ｐを法として得られたｈビットの数から最下位ビットＭ_００をはき出し、残りの数を２でくくる。

続いて、この２で括られた項から、数５２中の（ｂ）式に示すように、掛ける数ｂの最下位ビットＢ_０と掛けられる数ａとの乗算を行いｈ＋１ビットの数（Ｍ_１０＋Ｍ_２０＋・・・＋Ｍ_{ｈ−１・０}２^ｈ−２）を作る。これと共に、この時点における掛ける数ｂの最下位ビットＢ_１と掛けられる数ａとの乗算を行い、数５２中の（ｃ）式に示すように、ｈビットの数（Ｍ_０１＋Ｍ_１１２＋・・・＋Ｍ_{ｈ−１・１}２^ｈ−１）を作る。

最後に、数（Ｍ_１０＋Ｍ_２０＋・・・＋Ｍ_{ｈ−１・０}２^ｈ−２）と数（Ｍ_０１＋Ｍ_１１２＋・・・＋Ｍ_{ｈ−１・１}２^ｈ−１）とを加算し、数５２中の（ｄ）式に示すように、新たなｈビットの数（Ｑ^０ _０＋Ｑ^０ _１２＋・・・＋Ｑ^０ _ｈ−１２^ｈ−１）を作る。

以降同様の計算ステップを、数５２中の（ｏ）式で示すように、掛ける数ｂの最上位ビットＢ_ｈ−１と掛けられる数Ａとの乗算を行いｈビットの数（Ｑ^ｈ−２ _０＋Ｑ^ｈ−２ _１２＋・・・＋Ｑ^ｈ−２ _ｈ−１２^ｈ−１）を得るまで繰り返す。

数５３は、上記第２の事項を利用した後半の計算ステップ群である。なお、上記第２の事項を利用した部分については２重下線を付している。また、数５３中の（ｐ）式は数５２中の（ｏ）式に続く式である。

［数５３］

後半のステップ群では、前半のステップ群で得られた２ｈ−１ビットの数からｐを引いてｐ以下の数を得る。

始めに、数５３中の（ｏ）式で示された前半のステップ群で得た２ｈ−１ビットの数のうち、最上位からｈ＋１ビット分の数Ｑ^ｈ−３ _０２^ｈ−２＋２^ｈ−１（Ｑ^ｈ−２ _０＋Ｑ^ｈ−２ _１２＋・・・＋Ｑ^ｈ−２ _ｈ−１２^ｈ−１）を２^ｈ−２で括る。この結果が、数５３中の（ｐ）式となる。

続いて、数５３中の（ｐ）式で示されたｈ＋１ビットのバイナリ表示の数Ｑ^ｈ−３ _０＋２（Ｑ^ｈ−２ _０＋・・・＋Ｑ^ｈ−２ _ｈ−１２^ｈ−１）からｐを引いて、数５３中の（ｑ）式に示すような、ｈビットの数（Ｑ^ｈ−１ _０＋Ｑ^ｈ−１ _１２＋・・・＋Ｑ^ｈ−1 _ｈ−１２^ｈ−１）を得る。

以降、ビット数を減らしながら同様の計算ステップを繰り返す。そして、数５３中の（ｕ）式に示すようなｈビットの表示を得て終了する。

以上、数５２及び数５３で示す全計算ステップの終了によって、Ｚｐの数の乗算の結果としてｈビットの積が得られる。

図５８は、“Ｘ Ｚｐ”回路ブロックの一般的な回路記号を示す図であり、図５９は、“Ｘ Ｚｐ”回路ブロックのブロック図である。また、図６０は、図５９に示す回路構成による演算処理を模式的に示した図である。

“Ｘ Ｚｐ”回路ブロックは、大別して、数５２で示した前半の計算ステップ群を処理する回路と、数５３で示した後半の計算ステップ群を処理する回路とからなる。

前半の計算ステップ群を処理する回路は、ＡＮＤゲートＧ１と、ｈ−１個の“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックとで構成される。

ＡＮＤゲートＧ１は、掛けられる数ａの第ｉ（ｉ＝０〜ｈ−１）ビットと、掛ける数ｂの第ｊ（ｊ＝０〜ｈ−１）ビットとの論理積を取り、これをＭ_ｉｊとして出力する。

“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックは、Ｚｐの２数のｐを法としての和を求める回路である。“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックは、Ａ_０〜Ａ_ｈ−１、及びＢ_０〜Ｂ_ｈ−１を入力し、Ｑ_０〜Ｑ_ｈ−１を出力する。

１つ目の“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜１＞は、Ａ_０〜Ａ_ｈ−２、Ａ_ｈ−１、及びＢ_０〜Ｂ_ｈ−１に、それぞれＭ_１０〜Ｍ_{ｈ−１・０}、‘０’、Ｍ_０１〜Ｍ_{ｈ−１・１}を入力し、Ｑ_０〜Ｑ_ｈ−１からＱ^０ _０〜Ｑ^０ _ｈ−１を出力する。

以上のように、前半の計算ステップ群を処理する回路は、“ｈ ｂｉｔ ＡＤｍｏｄ ｐ”回路ブロック＜１＞〜“ｈ ｂｉｔ ＡＤｍｏｄ ｐ”回路ブロック＜ｈ−１＞の出力と入力とを順次接続して構成されている。

後半の計算ステップ群を処理する回路は、ｈ−１個の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックで構成されている。この“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックは図６、図７に示す回路である。

１つ目の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロック＜１＞は、Ａ_０、及びＡ_１〜Ａ_ｈに、それぞれＱ^ｈ−３ _０、及びＱ^ｈ−２ _０〜Ｑ^ｈ−２ _ｈ−１を入力し、Ｑ_０〜Ｑ_ｈ−１からＱ^ｈ−１ _０〜Ｑ^ｈ−１ _ｈ−１を出力する。

２つ目の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロック＜２＞は、Ａ_０、及びＡ_１〜Ａ_ｈに、それぞれＱ^ｈ−４ _０、及びＱ^ｈ−１ _０〜Ｑ^ｈ−１ _ｈ−１を入力し、Ｑ_０〜Ｑ_ｈ−１からＱ^ｈ _０〜Ｑ^ｈ _ｈ−１を出力する。

以上のように、後半の計算ステップ群を処理する回路は、“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロック＜１＞〜＜ｈ−１＞の出力と入力とを順次接続して構成されている。

全ての回路はクロック非同期で動作し、入力Ｍ_ａｂを与えることによって出力Ｑが確定する。

ここで、“Ｘ Ｚｐ”回路ブロックの回路規模に言及する。

例えば、ｐ＝１７とした場合、ｈ＝５となる。この場合、“Ｘ Ｚｐ”回路ブロックは、ｈ−１＝４個の“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックとｈ−１＝４個の“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックで構成することができる。このことから、“Ｘ Ｚｐ”回路ブロックの回路規模は小さいと言える。

なお、“Ｘ Ｚｐ”回路ブロックでは、２ｈ−２個必要となる。

次に、図５９に示された“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックを詳述する。

図６１は、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックの回路記号である。

“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックは、Ａ及びＢから入力される数ａ及びｂの和を求めて、得られた和の素数ｐによる剰余をＱから出力する。

ここで、ｈ＝７、ｐ＝７９の場合について考える。この場合、数ａ、ｂ、素数ｐ、剰余のバイナリ表示Ｑの間には、数５４に示す関係が成立する。

［数５４］

図６２は、ｈ＝７、ｐ＝７９とした場合の“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックの回路図である。

“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックは、ＰＦ０生成部Ｕ１、６個の半加算器ＨＡ１〜ＨＡ６、及び８個の全加算器ＦＡ１〜ＦＡ８を有する。

ＰＦ０生成部Ｕ１は、図７に示す“ｈ＋１ ｂｉｔ ｍｏｄ ｐ”回路ブロックのＰＦ０生成部Ｕ１と同じであるため説明を省略する。

半加算器ＨＡ１は、入力がＡ_０及びＢ_０、出力がＳ０、桁上げ出力がＣ０´となっている。全加算器ＦＡ１は、入力がＡ_１及びＢ_１、桁上げ入力がＣ０´、出力がＳ１、桁上げ出力がＣ１´となっている。全加算器ＦＡ２は、入力がＡ_２及びＢ_２、桁上げ入力がＣ１´、出力がＳ２、桁上げ出力がＣ２´となっている。全加算器ＦＡ３は、入力がＡ_３及びＢ_３、桁上げ入力がＣ２´、出力がＳ３、桁上げ出力がＣ３´となっている。全加算器ＦＡ４は、入力がＡ_４及びＢ_４、桁上げ入力がＣ３´、出力がＳ４、桁上げ出力がＣ４´となっている。全加算器ＦＡ５は、入力がＡ_５及びＢ_５、桁上げ入力がＣ４´、出力がＳ５、桁上げ出力がＣ５´となっている。全加算器ＦＡ６は、入力がＡ_６及びＢ_６、桁上げ入力がＣ５´、出力がＳ６、桁上げ出力がＣ６´となっている。半加算器ＨＡ２は、入力がＳ_０及びＰＦ０、出力がＱ_０、桁上げ出力がＣ０となっている。半加算器ＨＡ３は、入力がＣ０及びＳ１、出力がＱ_１、桁上げ出力がＣ１となっている。半加算器ＨＡ４は、入力がＣ１及びＳ２、出力がＱ_２、桁上げ出力がＣ２となっている。半加算器ＨＡ５は、入力がＣ２及びＳ３、出力がＱ_３、桁上げ出力がＣ３となっている。全加算器ＦＡ７は、入力がＳ４及びＰＦ０、桁上げ入力がＣ３、出力がＱ_４、桁上げ出力がＣ４となっている。全加算器ＦＡ８は、入力がＳ５及びＰＦ０、桁上げ入力がＣ４、出力がＱ_５、桁上げ出力がＣ５となっている。半加算器ＨＡ６は、入力がＣ５及びＳ６、出力がＱ_６となっている。

以上の構成によって、ＰＦ０生成部Ｕ１は、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックに入力されるバイナリＡ及びＢの和がｐ＝７９以上か否かを判断し、Ａ及びＢの和がｐ＝７９以上の場合、７９をＡ及びＢの和から引くために、半加算器ＨＡ２〜ＨＡ６、及び全加算器ＦＡ７、ＦＡ８によって、８ビットバイナリの７９の補数である４９をＡ及びＢの和に加えている。

次に、図５６に示す“Ｘ ｋ−ｔｉｍｅｓ”回路について説明する。

図６３は、“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックの回路記号である。

“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックは、入力Ｘの累乗（Ｘ）^ｊを算出し出力する回路であり、クロックｃｌ_ｊ（ｊ＝１〜ｐ−１）で制御される。

“Ｘ ｋ−ｔｉｍｅｓ”回路は、“Ｘ Ｚｐ”回路ブロックと、クロックｃｌに同期して動作する“Ｒｇｓｔｒ”レジスタ＜１＞及び“Ｒｇｓｔｒ”レジスタ＜２＞とを有する。

“Ｒｇｓｔｒ”レジスタ＜１＞は、入力がＸに接続され、出力が“Ｘ Ｚｐ”回路ブロックの一方の出力に接続されている。“Ｒｇｓｔｒ”レジスタ＜２＞は、入力に“Ｘ ｋ−ｔｉｍｓ”回路ブロックの出力が接続され、出力に“ｋ−ｔｉｍｅｓ”回路ブロックの一方の入力が接続されている。“Ｒｇｓｔｒ”レジスタ＜２＞には初期状態として‘１’が保持されている。

この回路構成によって、“Ｘ ｋ−ｔｉｍｅｓ”回路ブロックは、自身の出力を１サイクル遅れで取り込み、これによって入力Ｘと出力（Ｘ）^ｊの積を得る。

クロックｃｌが入るごとに出力（Ｘ）^ｊに入力Ｘを累積的に掛ける。クロックｃｌ_ｊ（ｊ＝１〜ｋ）の立ち上がる前に“Ｒｇｓｔｒ”レジスタ＜１＞にデータＸを設定しておき、初期設定が‘１’の“Ｒｇｓｔｒ”レジスタ＜２＞を同期させることで、ｊ発目のｃｌ_ｊで（Ｘ）^ｊを得る。

次に、後述の演算処理で多用するＺｐの要素ｊのｍ乗を計算する回路ブロックを説明する。以下では、この回路ブロックを“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックと呼ぶ。

図６５は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックの回路記号を示す図である。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックは、クロックｃｋ_ｉ（ｉ＝０〜ｐ−２）とｃｌ_ｊ（ｊ＝１〜ｐ−１）で制御され、クロックｃｌ_ｊの立ち上がりに同期して（ｊ）^ｉを出力する。

図６６中（Ａ）は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックのブロック図であり、図６６中（Ｂ）は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックを制御するクロックｃｋ_ｉ及びｃｌ_ｊのタイミングチャートである。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックは、Ｚｐのゼロ以外の全ての要素１〜ｐ−１に対して、０〜ｐ−２乗を順次算出し、レジスタに保持する回路である。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックは、図６６に示す通り、“Ｘ Ｚｐ”回路ブロック、“Ｃｏｕｎｔｅｒ（１ ｔｏ ｐ−１）”回路ブロック、“Ｒｏ（１〜ｐ−１）”レジスタ部を有する。

指数を決めるクロックがｃｋ_ｉで、何回目のクロックｃｋ_ｉであるかで指数ｉが決まる。一方、Ｚｐの要素を１から順次指定するのがクロックｃｌで、クロックｃｌ_ｊの回数ｊが要素数となる。

“Ｃｏｕｎｔｅｒ（１ ｔｏ ｐ−１）”回路ブロックは、“Ｘ Ｚｐ”回路ブロックの一方の入力に接続されている。ｃｋ_ｉをスタート信号とし、ｃｌ_ｊの立ち上がりのタイミングで１〜ｐ−１の範囲でカウントアップする。

“Ｒｏ（１〜ｐ−１）”レジスタ部は、ｐ−１個のレジスタからなり、ｉｎのクロック／ｃｌ_ｊの立ち上がりで入力ｉ_１〜ｉ_ｐ−１を順次１〜ｐ−１番目のレジスタに格納し、ｏｕｔのクロックｃｌ_ｊの立ち上がりで順次１〜ｐ−１番目のレジスタの内容ｉ_１〜ｉ_ｐ−１を出力する。

図６６に示すように、“Ｃｏｕｎｔｅｒ（１ ｔｏ ｐ−１）”回路ブロックと“Ｒｏ（１〜ｐ−１）”レジスタ部への入力クロックｃｋ及びｃｌを同期させ、“Ｒｏ（１〜ｐ−１）”レジスタ部の出力と“Ｃｏｕｎｔｅｒ（１ ｔｏ ｐ−１）回路ブロックの出力とを“Ｘ Ｚｐ”回路ブロックで乗算すると、クロックｃｋ_ｉが立ち上がった後、ｃｌ_ｊが立ち上がる毎に“Ｘ Ｚｐ”回路ブロックから（ｊ）^ｉが出力される。

次に、シンドローム^ｍＳの成分要素を一括して求める演算回路を説明する。以下、この演算回路を「シンドローム成分要素生成回路」と呼ぶ。

ｍを０〜ｐ−２の範囲でスキャンすると、シンドローム^ｍＳの成分として必要なものは、Ｓ_０〜Ｓ_{ｐ−２＋ε}のε個である。シンドローム^ｍＳの成分生成に必要な演算処理の式を数５５に示す。

［数５５］

図６７中（Ａ）は、シンドローム成分要素生成回路の回路図であり、図６７中（Ｂ）は、シンドローム成分要素生成回路を制御するクロックｃｋ_ｉ（ｉ＝０〜ｐ−２＋ε）、ｃｌ_ｊ（ｊ＝１〜ｐ−１）のタイミングチャートである。

シンドローム成分要素生成回路は、図６７中（Ａ）に示すように、“Ｒｏ（１〜ｐ−１）”レジスタ部、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロック、“Ｘ Ｚｐ”回路ブロック、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック、“Ｒｇｓｔｒ”レジスタ、及び“Ｒｉ（０〜ｐ−２＋ε）”レジスタを有する。

ｐ−ａｄｉｃセルアレイから読み出されたデータＹは“Ｒｏ（１〜ｐ−１）”レジスタに初期設定として格納される。“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックからは（ｊ）^ｉを発生させる。これら“Ｒｏ（１〜ｐ−１）”レジスタ及び“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックは、クロックｃｌ_ｉによって同期され、Ｙの成分ｙ_ｊが出力されると同時に（ｊ）^ｉが出力されるように制御される。これらの積（ｊ）^ｉｙ_ｊを“Ｘ Ｚｐ”回路ブロックで生成し、クロックｃｌ_ｊ（ｊ＝１〜ｐ−１）と同期して、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック及び“Ｒｇｓｔｒ”レジスタのループによって加算していき、シンドローム成分Ｓ_ｉを作る。得られたＳ_ｉをクロックｃｋ_ｉ＋１で“Ｒｉ（０〜ｐ−２＋ε）”レジスタの第ｉ番目のレジスタに格納する。この過程をクロックｃｋ_ｉのｉ＝０〜ｐ−２＋εについて処理し、全てのシンドローム成分を得て“Ｒｉ（０〜ｐ−２＋ε）”レジスタ部に格納する。

次に、解探索多項式Ψ（ｘ）を求める演算回路を説明する。以下、この演算回路を「解探索多項式生成回路」と呼ぶ。

解探索多項式Ψ（ｘ）のｘの各次数ｊの係数ψ_ｊを求める演算の処理に必要な処理式を数５６に示す。

［数５６］

図６８は、解探索多項式生成回路のブロック図である。

解探索多項式生成回路は、シンドロームｕＳ＝（ｕＳ_ｍ，ｕＳ_ｍ＋１，・・・，ｕＳ_ｍ＋ε）を用いてエラーを探索するステップで用いる回路である。

解探索多項式生成回路によれば、複雑なユークリッド法を用いることなく、単純な巡回回路で解探索多項式Ψ（ｘ）を生成できる。

解探索多項式生成回路は、数５６に示す第２式右辺のうちΣψ_ｊ−１Ｓ_ｍ＋ｉを求める第１の部分回路Ｕ１と、同じく数５６に示す第２式右辺のうち−ｕ（ｊ）^−１を求める第２の部分回路Ｕ２とを有する。

第１の部分回路Ｕ１は、ε−１個の直列接続された“Ｒｇｓｔｒ”レジスタ＜１＞〜＜ε＞と、各“Ｒｇｓｔｒ”レジスタ間の接続点に接続されたε−１個の“Ｘ Ｚｐ”回路ブロック＜１＞〜＜ε＞を有する。

“Ｒｇｓｔｒ”レジスタ＜１＞の初期値は‘１’であり、その他の、“Ｒｇｓｔｒ”レジスタ＜２＞〜＜ε＞の初期値は‘０’である。

第１の部分回路Ｕ１は、各“Ｒｇｓｔｒ”レジスタに入力されるクロックｃｋで制御され、ｊ回目のクロックｃｋ_ｊの立ち上がりで、“Ｒｇｓｔｒ”レジスタの接続点から各次数の係数ψ_ｊ−１、ψ_ｊ−２、・・・、ψ_{ｊ−（ε−１）}、ψ_ｊ−εを出力する。係数が存在しない接続点は‘０’になるため、“Ｘ Ｚｐ”回路ブロック＜１＞〜＜ε＞によるシンドローム成分Ｓ_ｍ＋１〜Ｓ_ｍ＋εとの積演算に寄与しない。“Ｘ Ｚｐ”回路ブロック＜１＞〜＜ε＞の出力は２つずつ“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックで和演算され、これら“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックのラダーによって最終的にΣψ_ｊ−ｉＳ_ｍ＋ｉを得る。

第２の部分回路Ｕ２は、“Ｃｏｕｎｔｅｒ（１ ｔｏ ε）”回路ブロック、“Ｘ Ｚｐ”回路ブロック＜ａ＞、＜ｂ＞、及び“ｊ^−１ ｄｅｃ”回路ブロックを有する。

第２の部分回路Ｕ２は、クロックｃｋ_ｊに応じて“Ｃｏｕｎｔｅｒ（１ ｔｏ ε）”回路ブロックで生成されたｊとシンドローム成分Ｓ_ｍから“Ｘ Ｚｐ”回路ブロック＜ａ＞及び“ｊ^−１ ｄｅｃ”回路ブロックによって（ｊＳ_ｍ）^−１を生成する。そして、この生成された（ｊＳ_ｍ）^−１と設定されたηから“Ｘ Ｚｐ”回路ブロック＜ｂ＞によってｕ（ｊ）^−１を得る。

そして、“Ｘ Ｚｐ”回路ブロック＜ｃ＞によって、第１の部分回路Ｕ１で生成されたΣψ_ｊ−ｉＳ_ｍ＋ｉと第２の部分回路Ｕ２で生成されたｕ（ｊ）^−１との乗算を行い、係数ψ_ｊを得る。

係数ψ_ｊは、ｈビットのバイナリであり、負数の表示にするために補数表現となっている。そこで、“Ｘ Ｚｐ”回路ブロック＜ｃ＞の出力に対し、インバータＩＶで反転させた上で、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックで‘１’を加算する。これによって、ｈビットのバイナリの補数表現を得ることができる。

なお、図６８に示す“ｊ^−１ ｄｅｃ”回路ブロックは、Ｚｐの要素ｊの逆元ｊ^−１を求める回路である。“ｊ^−１ ｄｅｃ”回路ブロックの詳細については、後述する。

以上説明した解探索多項式生成回路によれば、クロックｃｋをε回入れると各ノードにｊ＝εとした係数ψ_ｊ〜ψ_ｊ−εが得られる。

なお、実用的なｐ−ａｄｉｃセルメモリに用いる場合、εとして５や６が選ばれるため、解探索多項式生成回路に必要な回路ブロック数は少なく、回路規模としては実用上十分に小さいと考えられる。

Ψ（ｘ）の次数がηに一致した場合、このΨ（ｘ）の根とその多重度を求める必要がある。そこで、次は、根の多重度を求める際に必要となるハッセ微分多項式の係数を計算する演算回路を説明する。以下では、この演算回路を「ハッセ微分多項式係数生成回路」と呼ぶ。

ハッセ微分多項式の係数とその係数とΨ（ｘ）の係数との関係は、数５７のようになる。

［数５７］

つまり、数５７からも分かるように、ハッセ微分多項式係数生成回路は、Ψ（ｘ）の係数と２項係数の掛け算を行い、各微分の階数での各次数の係数をクロックｃｋ及びｃｌを用いて生成し、全ての係数をレジスタに格納する。

図６９中（Ａ）は、ハッセ微分多項式係数生成回路のブロック図であり、図６９中（Ｂ）は、ハッセ微分多項式係数生成回路を制御するクロックｃｋ及びｃｌのタイミングチャートである。

ハッセ微分多項式係数生成回路は、Ｚｐの各要素ｉの階乗ｉ！が記録された“ｉ！”テーブル、その逆元が記録された“（ｉ！）^−１”テーブル、及び解探索多項式Ψ（ｘ）の係数ψ_ｉが記録された“ψ_ｉ”テーブルを有する。“ｉ！”テーブル及び“（ｉ！）^−１”テーブルに関しては、例えば、ｐ＝１７の場合、実用上十分小さい規模に抑えることができる。

また、“ψ_ｉ”テーブルに関しては、図６８で示す解探索多項式生成回路で生成されるため、これを使う。

ハッセ微分多項式係数生成回路は、図６９に示すように、“ｉ！”テーブル、“（ｉ！）^−１”テーブル、及び“ψ_ｉ”テーブルと、“Ｘ Ｚｐ”回路ブロックと、これらの接続を切り替える制御スイッチＳＷを有する。非選択のノードは、“Ｘ Ｚｐ”回路ブロックによる積演算の結果が‘０’となるように、制御スイッチＳＷの出力側のノードを、初期状態で‘０’に放電されている。

クロックｃｋのクロック数は、微分の階数に対応しており、ｃｋ_ｉのｉは１〜εの値をとる。一方、クロックｃｌは、次数に相当し、微分の階数が上がれば不要な次数が増える。そのため、クロックｃｋに対して毎回同じ数の発生をする必要はないが、図６９の回路では毎回同じ回数ε発生させる。したがって、格納タイミングはε^２個あるが、係数を格納する“Ｒ ｉ（０〜ε）／ｊ（０〜ε−１）”レジスタ部は、全てのクロックに対応したレジスタがある必要はなく、ほぼ半分のレジスタがあれば良い。

なおｃｋ_０はレジスタにΨ（ｘ）の係数、すなわちΨ^［０］に相当する係数を予め格納しておくために便宜上設けたものである。

次に、解探索多項式Ψ（ｘ）の根とその多重度を計算する演算回路を説明する。以下、この演算回路を「解探索多項式根／多重度演算回路」と呼ぶ。

解探索多項式根／多重度演算回路は、ハッセ微分多項式の０階微分をΨ（ｘ）とみなし、Ｚｐの各要素に対してハッセ微分多項式がゼロでなければ次の要素に計算を移し、ハッセ微分多項式がゼロである間は微分の階数を上げる。各Ｚｐの要素に対して、ハッセ微分多項式がゼロでない最初のハッセ微分の階数をレジスタに残していくと、階数がゼロではない要素が根であり、その残された階数がその根の多重度になる。つまり、レジスタから内容が‘０’ではないものを選び、その保持された値がその根の多重度となる。

具体的に、解探索多項式Ψ（ｘ）の根をαとし、Ψ（ｘ）のｉ階のハッセ微分多項式を［Ψ（ｘ）］^［ｉ］とすると、αの多重度をｎとした場合の関係式は数５８のようになる。

［数５８］

解探索多項式根／多重度演算回路は、この数５８を具備するｎを、Ｚｐの各要素αに対して、Ψ（ｘ）の根であるか否かに関わらず求める。ｎ＝０の場合、αが根でないことを意味する。

図７０中（Ａ）は、解探索多項式根／多重度演算回路のブロック図であり、図７０中（Ｂ）は、解探索多項式根／多重度演算回路を制御するクロックｃｋ、ｃｌ、及びｃｌｋのタイミングチャートである。

解探索多項式根／多重度演算回路は、クロックｃｋでＺｐの要素１〜ｐ−１についてスキャンし、クロックｃｌでハッセ微分の階数、クロックｃｌｋでその階数のハッセ微分多項式の値を求める。クロックｃｋは、計算しているハッセ微分多項式の値がゼロでなくなった場合に発生させ、次のＺｐの要素でのサイクルに入る。

解探索多項式根／多重度演算回路は、図７０中（Ａ）に示すように、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロック、“Ｒｏ ｉ（０〜ε）／ｊ（０〜ε）”レジスタ部、“Ｘ Ｚｐ”回路ブロック、“Ｒｇｓｔｒ”レジスタ＜１＞、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック、“Ｒｇｓｔｒ”レジスタ＜２＞、“ｃｌｏｃｋ ｃｌ ｇｅｎ．”回路ブロック、“Ｃｏｕｎｔｅｒ（０ ｔｏ ε）”回路ブロック、“Ｌｉ（１〜ｐ−１）”レジスタ部を有する。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックは、クロックｃｋをα回受けて要素αを選択し、クロックｃｌｋをｊ＋１回受けてαのｊ乗を出力する。

“Ｒｏ ｉ（０〜ε）／ｊ（０〜ε）”レジスタ部は、クロックｃｌ_ｉ及びｃｌｋ_ｊを受けてハッセ微分多項式の係数ψ^［ｉ］ _ｊを出力するレジスタであり、図６９に示す“Ｒ ｉ（０〜ε）／ｊ（０〜ε−１）”レジスタ部に相当するものである。

“Ｘ Ｚｐ”回路ブロックは、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックからの出力α^ｊと、“Ｒｏ ｉ（０〜ε）／ｊ（０〜ε）”レジスタ部からの出力ψ^［ｉ］ _ｊを積演算し、α^ｊψ^［ｉ］ _ｊを出力する。

以上、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロック、“Ｒｏ ｉ（０〜ε）／ｊ（０〜ε）”レジスタ部、及び“Ｘ Ｚp”回路ブロックに対し、クロックｃｌｋをε＋１回与えてやることでハッセ微分多項式の値を得ることができる。なお、クロックｃｋ、ｃｌ、及びｃｌｋの制御を簡単にするため、この計算では存在しない０の値の項の和も計算する。したがって、本来は必要なクロックｃｌｋの総数は半分程度となる。

微分多項式の値［Ψ（α）］^［ｉ］は、ゼロの場合‘０’、その他の場合‘１’として“Ｒｇｓｔｒ”レジスタ＜１＞に取り込まれる。

“Ｒｇｓｔｒ”レジスタ＜１＞で保持された値は、クロックｃｌｋ_０のタイミングで、クロックｃｋ_α（α＝１〜ｐ−１）として出力される。このクロックｃｋ_αは、クロックｃｌｋ_εでリセットされるまで保持される。

“Ｒｇｓｔｒ”レジスタ＜１＞は、初期値が‘１’であるため、クロックｃｋ_１は最初のｃｌｋ_０で立ち上がる。クロックｃｋ_２以降は、計算結果にしたがってｃｌｋのいずれかのサイクルのｃｌｋ_０で立ち上がる。

“ｃｌｏｃｋ ｃｌ ｇｅｎ．”回路ブロックは、クロックｃｌｋ_０に同期してクロックｃｌ_ｉを発生させて、クロックｃｋ_αが立ち上がる毎にクロックｃｌ_０にリセットする。

”Ｃｏｕｎｔｅｒ（０ ｔｏ ε）”回路ブロックは、クロックｃｋ_αで０にリセットされ、クロックｃｌが入るたびにカウントアップし、クロックｃｌの回数−１を出力する。この出力は、“Ｌｉ（１〜ｐ−１）”レジスタ部に格納される。

“Ｌｉ（１〜ｐ−１）”レジスタ部は、入力をクロックｃｋ_αによって切り換えていくので、α番目のレジスタにはその多重度が格納されることになる。

ところで、ｐが小さい場合、計算で利用するＺｐの要素で、テーブルとして持っておけるものについては、予め用意しておけば良い。これによって、計算を省略することができ、回路規模が小さくすることができる。例えば、実用的なｐはせいぜい１９程度までであるので、要素の逆元や階乗などはテーブルにしておく。これらのテーブルは、バイナリのデコーダを構成することになる。

特に、Ｚｐの要素の逆元は、変化する入力要素に対して直ぐに必要となる場合が多いので、デコーダ回路として構成しておくことが望ましい。

要素ｊから逆元ｊ^−１を求めるには、ｊ×ｊ^−１≡１（ｍｏｄ ｐ）の関係を求めておき、ｊ及びｊ^−１をｈビットのバイナリ表示を数５９に示すように構成し、これの変換デコーダを作れば良い。

［数５９］

具体的な変換デコーダの構成については、後述する。

また、要素ｊの階乗ｊ！は、ハッセ微分多項式の係数の計算で必要になるが、これも予め求めて順に利用すればよい。

なお、ｊ！を計算する際、Ｚｐの要素での値を求めている。そのため、ｐが素数であり、階乗を構成する各要素の数とは互いに素であることから、数６０に示す漸化式を利用することで、大きな数を扱わなくても階乗を求めることができる。

［数６０］

図７１は、具体的な例として、実用には少し大きい素数として、ｐ＝２３の場合の逆元と階乗の表である。これらの数字の５ビットでのバイナリ表示を用いると変換デコーダを作ることができる。

次に、変換デコーダである“ｊ^−１ ｄｅｃ”回路ブロックの具体的な回路構成について説明する。

図７２中（Ａ）は、ｈ＝７とした場合のｊの逆元ｊ^−１を求めるデコーダ回路のブロック図であり、図７２中（Ｂ）は、本デコーダ回路を制御するクロックτ_０及びτ_１のタイミングチャートである。

本デコーダ回路は、７ビットのバイナリデータＩを７ビットの他のバイナリデータＯにデコーダする一般的な回路の構成となっている。

Ｉにｊ、Ｏにｊ^−１を入れて考えれば、“ｊ^−１ ｄｅｃ”回路ブロックとして用いることができる。本デコーダ回路は、Ｚｐの要素間の変換に使用され、クロックτ_０、τ_１の２つのクロックで動作する。

デコード回路は、論理ゲートによって、ビットＩ_０〜Ｉ_５を２ビットずつ部分デコードして信号／Ａ_０〜／Ａ_３、／Ｂ_０〜／Ｂ_３、Ｃ_０〜Ｃ_３を生成し、更に、／Ａ_ｉ及び／Ｂ_ｋからＮＯＲゲートを用いてＡ_ｉＢ_ｋを生成する。

また、デコード回路は、出力ビットＯ_ｍ毎に１６個のＶｓｓへの放電経路を持ったＮＯＲ接続を有し、ＮＯＲノードをラッチしたレベルを反転してＯ_ｍとする。なおラッチ回路のリセットには、クロックτ_０を１クロックだけ用いる。

１６個の放電経路は、それぞれ信号Ａ_ｉＢ_ｋ（ｉ＝０〜３、ｋ＝０〜３）でゲートされ、更に、入力ビットＩ_６と／Ｉ_６で分岐する。この分岐の下に変換の対応にしたがってＣ_ｍｉ（ｍｉ＝０〜３）で制御されるＮＭＯＳトランジスタのＯＲ接続が配置される。これらの分岐はクロックτ_１でＶｓｓに接続される。

Ｃ_ｍｉで制御されるトランジスタは、変換においてビットＯ_ｍに対応する入力ＩのビットをＡ_ｉＢ_ｋで分類した後、Ｉ_６の‘１’、‘０’で分類してＣ_０〜Ｃ_３の中から含まれるものを選択することによって配置される。

演算処理で求めたエラーＥについては、そのリー・メトリックがε以下であることを確認して、誤訂正とならいないことが分かってから訂正される。

そこで、次は、Ｚｐの要素のリー・メトリックを計算する演算回路素子について説明する。以下において、この演算回路素子を“ｈ ｂｉｔ ＬＭｐ”回路ブロックと呼ぶ。

ｈビットのバイナリ表示のＺｐの要素ａについて、そのリー・メトリックＱ＝｜ａ｜は、Ｑ＝／ＰＦ０×ａ＋ＰＦ０×（ｐ−ａ）と表現できる。ここでＰＦ０は、ａ≧（ｐ＋１）／２の場合に‘１’、ａ＜（ｐ＋１）／２の場合に‘０’になる。したがって、ａのリー・メトリックを求めるには、ａ≧（ｐ＋１）／２の場合、ｐからａを引く、即ち、ｐにａの補数を加えれば良い。

ここで、具体例として、ｈ＝７、ｐ＝７９の場合について説明する。

ｈ＝７、ｐ＝７９の場合のＡとＱの関係は数６１のようになる。

［数６１］

図７３は、“ｈ ｂｉｔ ＬＭｐ”回路ブロックの回路記号であり、図７４は、ｈ＝７、ｐ＝７９とした場合の“ｈ ｂｉｔ ＬＭｐ”回路ブロックのブロック図である。

“ｈ ｂｉｔ ＬＭｐ”回路ブロックは、ｈビットのバイナリＡ_０〜Ａ_ｈ−１を入力し、ｈビットのバイナリＱ_０〜Ｑ_ｈ−１を出力する。

“ｈ ｂｉｔ ＬＭｐ”回路ブロックは、ＰＦ０生成部Ｕ１、ＸＯＲゲートＧ１、２個の半加算器ＨＡ１、ＨＡ２、及び５個の全加算器ＦＡ１〜ＦＡ５を有する。

ＰＦ０生成部Ｕ１は、Ｖｃｃ端子及びＶｓｓ端子間に、直列に接続されたＰＭＯＳトランジスタＱＰ１、ＱＰ２、ＮＭＯＳトランジスタＱＮ１、及びＱＮ２を有する。これらトランジスタＱＰ１、ＱＰ２、ＱＮ１、及びＱＮ２は、それぞれ、入力Ａ_５、Ａ_６、Ａ_３、及びＡ_５で制御される。

また、ＰＦ０出力部Ｕ１は、その他に、２個のＰＭＯＳトランジスタＱＰ３、
ＱＰ４、２個のＮＭＯＳトランジスタＱＮ３、ＱＮ４、及びインバータＩＶ１を有する。

トランジスタＱＰ３、ＱＰ４は直列接続されており、その両端は、トランジスタＱＰ１のソース及びドレインに接続されている。トランジスタＱＮ３は、トランジスタＱＮ１のソース及びドレイン間に接続されている。また、トランジスタＱＮ４は、トランジスタＱＮ１のソース及びトランジスタＱＮ２のドレイン（Ｖｓｓ端子）間に接続されている。トランジスタＱＰ３、ＱＰ４、ＱＮ３、及びＱＮ４は、それぞれ、入力Ａ_３、Ａ_４、Ａ_４、及びＡ_６で制御される。インバータＩＶ１は、入力がトランジスタＱＰ２及びＱＮ１の接続点に接続されている。このインバータＩＶ１の出力がキャリーＰＦ０になる。

ＸＯＲゲートＧ１は、Ａ_ｊ（ｊ＝０〜７）及びＰＦ０を入力し、Ｂ_ｊを出力する。

全加算器ＦＡ１は、入力がＢ_０及びＰＦ０、桁上げ入力がＰＦ０、出力がＱ_０、桁上げ出力がＣ０となっている。全加算器ＦＡ２は、入力がＢ_１及びＰＦ０、桁上げ入力がＣ０、出力がＱ_１、桁上げ出力がＣ１となっている。全加算器ＦＡ３は、入力がＢ_２及びＰＦ０、桁上げ入力がＣ１、出力がＱ_２、桁上げ出力がＣ２となっている。全加算器ＦＡ４は、入力がＢ_３及びＰＦ０、桁上げ入力がＣ２、出力がＱ_３、桁上げ出力がＣ３となっている。半加算器ＨＡ１は、入力がＣ３及びＢ_４、出力がＱ_４、桁上げ出力がＣ４となっている。半加算器ＨＡ２は、入力がＣ４及びＢ_５、出力がＱ_５、桁上げ出力がＣ５となっている。

この具体例では入力が４０以上になったらａの補数をｐに加えている。ａの補数は、ＰＦ０＝１の場合、ＸＯＲゲートでａの各ビット表示Ａ_ｊを反転してＢ_ｊとし、これに１を加えて生成されている。

ｐ＝７９は、７９＝（１００１１１１）_２であるので、これをＰＦ０で表し、更に、１としてＰＦ０を使い、７９をＰＦ０を１として表したものとＡ_ｉの反転又はそのものとなるＢ_ｊと加えている。

“ｈ ｂｉｔ ＬＭｐ”回路は、クロックに非同期で動作し、入力を入れると計算されたリー・メトリックを出力する。

次に、エラーコード語Ｅのリー・メトリックｗ（Ｅ）＝Σ｜ｅ_ｊ｜（ｊ＝１〜ｐ−１）を計算する演算回路について説明する。以下、この演算回路を「リー・メトリック演算回路」と呼ぶ。

図７５は、リー・メトリック演算回路のブロック図である。

リー・メトリック演算回路は、“Ｒｏ（０〜ｐ−１）”レジスタ部、“ｈ ｂｉｔ ＬＭｐ”回路ブロック、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック、及び“Ｒｇｓｔｒ”レジスタを有する。

多項式Ψ（ｘ）から得られたエラーコード語Ｅは、“Ｒｏ（０〜ｐ−１）”レジスタ部に初期値として格納されている。“Ｒｏ（０〜ｐ−１）”レジスタ部からは、Ｅの成分ｅ_ｊをクロックｃｋ_ｊによって順次取り出される。

“ｈ ｂｉｔ ＬＭｐ”回路ブロックは、この取り出された成分ｅ_ｊからそのリー・メトリック｜ｅ_ｊ｜を計算する。“ｈ ｂｉｔ ＬＭｐ”回路ブロックは、クロックｃｋ_ｊ毎に計算された成分のリー・メトリック｜ｅ_ｊ｜を“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックに出力する。

“Ｒｇｓｔｒ”レジスタと“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックによって構成されるループで、この｜ｅ_ｊ｜を加算していく。そして、ｐ−１回目のクロックｃｋが立ち上がった時点の“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロックの出力がｗ（Ｅ）＝Σ｜ｅ_ｊ｜となる。

なお、ＥはΨ（ｘ）の根αと多重度の組みとして、前述の演算で得られたα、［ｎ］から、変換ｔ＝α−１、ｅ_ｔ＝（ｕｔ^ｍ）^−１ｎによって成分ｅ_ｔが得られる。ｗ（Ｅ）≦εなら、一連のエラー探索が終わり、Ｅによって、訂正を行うことができる。

エラー探索を終了し、エラーコードＥによって訂正されたリー・メトリック・コードＣが得られたら、これをＺｐのデータコードＡに戻す必要がある。この演算はＧを生成行列として、Ｃ＝ＡＧの逆演算を行うことに相当するが、行列の逆を得るのは規模の大きな演算となる。そのため、Ａの要素を逐次的にＣの要素から求めて行く。計算の過程を数６２に示す。但し、数６２において、ｊ＝１〜ｐ−１、ｎ＝ｐ−１、ｐ−ε−３＝ｎ−γ−１＝ｋ−１であることに注意されたい。

［数６２］

数６２に示したように、ｃ_ｊ＝Σ（ｊ）^ｉ＋１ａ_ｉの関係を順次変形して、ａ_０からａ_１、続いてａ_１からａ_２、・・・と逐次的にａ_ｍを求めて行くことが計算の原理となる。

両辺にｊの累乗の逆元を掛けてｊのＺｐの全ての元についての項として足し合わせる。このときＺｐの全ての元の和はゼロとなることを利用して変形している。

数６３は、Ｃの成分とＡの成分の関係式である。

［数６３］

次に、この数６３の関係式を具体的に実現する演算回路について説明する。

なお、ａ_ｍを得てから、ａ_ｍ＋１を求める際、ｃ^（ｍ） _ｊを求めながらａ_ｍ＋１でのｊについての和を順次計算して行く。この際、ｊについての必要な累乗は、ｃ^（ｍ） _ｊではｍ＋１乗、ａ_ｍ＋１ではｍ＋２乗となる。そのため、本演算回路では、Ｚｐの要素の累乗を計算する回路ブロックを若干修正したものを用いる。

図７６中（Ａ）は、Ｃ＝ＡＧからＡ＝ＣＧ^−１を求める演算回路（以下、この演算回路を「逆変換回路」と呼ぶ）のブロック図であり、図７６中（Ｂ）は、逆変換回路を制御するクロックｃｋ及びｃｌのタイミングチャートである。

逆変換回路は、データコードＡの要素を１つずつ演算で求める第１の部分回路Ｕ１と、この演算に必要なリー・メトリック・コードＣの成分の変換を都度行う第２の部分回路Ｕ２とからなる。

部分回路Ｕ１及びＵ２には、Ｚｐの要素ｊのｍ＋１乗とｍ乗を発生する“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックが配置されている。この“（ｊ）^ｉ（ｊ＝１〜ｐ−１）２”回路ブロックは、部分回路Ｕ１に対しては、クロックｃｌのサイクル数をｊとした場合、クロックｃｋ_ｉのサイクル数ｉを指数とした要素ｊの累乗を出力する。一方、部分回路Ｕ２に対しては、クロックｃｌのサイクル数をｊとした場合、クロックｃｋ_ｉのサイクル数よりも１だけ小さいｉを指数とした要素ｊの累乗を出力する。

この“（ｊ）^ｉ（ｊ＝１〜ｐ−１）２”回路ブロックは、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックに対し、更に、内部ノードの信号を取り出した回路として改めてシンボル化したものである。詳細については、後述する。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックは、クロックｃｌの１サイクル目で、部分回路Ｕ１に対しては、Ｚｐの要素そのものを出力し、部分回路Ｕ２に対しては、１が出力される。この部分回路Ｕ２に出力される１は、本来の演算で現れる値ではないため、演算結果に影響を及ぼさないようにする工夫が必要となる。そこで、この１の影響を無くすために、部分回路Ｕ２の積演算では、クロックｃｋの最初のサイクルの際、もう一方の入力を‘０’とし、積演算の結果がゼロになるようにしている。

始めに、第１の部分回路Ｕ１について説明する。

第１の部分回路Ｕ１は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックの他、“（ｊ）^−１ ｄｅｃ”回路ブロック、２つの“Ｘ Ｚｐ”回路＜１＞、＜２＞、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜１＞、“Ｒｇｓｔｒ”レジスタ＜１＞、及び“Ｌｉ（０〜ｋ−１）”レジスタ部を有する。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックの出力（ｊ）^ｍ＋１は、“（ｊ）^−１ ｄｅｃ”回路ブロックに入力される。

“（ｊ）^−１ ｄｅｃ”回路ブロックでは、（ｊ）^ｍ＋１を、その逆元（ｊ）^{−（ｍ＋１）}に変換し、“Ｘ Ｚｐ”回路ブロック＜１＞に出力する。

“Ｘ Ｚｐ”回路ブロック＜１＞は、“（ｊ）^−１ ｄｅｃ”回路ブロックから入力された（ｊ）^{−（ｍ＋１）}と、クロックｃｋ間のｐ−１個のクロックｃｌと同期して第２の部分回路Ｕ２から出力されるｃ_ｊ（＝ｃ^{（ｍ−１）} _ｊ）との積演算をし、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜１＞に出力する。

“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜１＞から出力された積は、初期値が‘０’の“Ｒｇｓｔｒ”レジスタ＜１＞と“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜１＞からなるループによって加算されて行く。この結果は、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜１＞から“Ｘ Ｚｐ”回路ブロック＜２＞に出力される。

“Ｘ Ｚｐ”回路ブロック＜２＞では、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜１＞から出力された和と（ｐ−１）^−１との積を演算し、数６２に示した計算式に従ったａ_ｍを得る。このａ_ｍは、次のサイクルの始まりであるクロックｃｋ_ｍ＋１によって“Ｌｉ（０〜ｋ−１）”レジスタ部の第ｍ番目のレジスタに格納される。

続いて、第２の部分回路Ｕ２について説明する。

第２の部分回路Ｕ２は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックの他、“Ｒｇｓｔｒ”レジスタ＜２＞、“Ｘ Ｚｐ”回路ブロック＜３＞、２つの“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜２＞、＜３＞、及び“Ｒ（１〜ｐ−１）”レジスタ部を有する。

“Ｒｇｓｔｒ”レジスタ＜２＞は、設定されたａ_ｍをｃｋ_１以降のサイクルで出力する。即ち、出力ａ_ｍ−１は、クロックｃｋ_ｍで出力される。クロックｃｋの最初のサイクルｃｋ_０では“Ｒｇｓｔｒ”レジスタ＜２＞の出力ノードの初期値は‘０’に設定されている。これは、前述の通り、クロックｃｌ_１の際の積演算の結果をゼロにするためである。

“Ｘ Ｚｐ”回路ブロック＜３＞では、クロックｃｋのサイクルｃｋ_ｍで発生する“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックの出力（ｊ）^ｍと、“Ｒｇｓｔｒ”レジスタ＜２＞の出力ａ_ｍ−１との積を生成しインバータＩＶ１を介して“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜２＞に出力する。

“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜２＞では、インバータＩＶ１を介して出力された“Ｒｇｓｔｒ”レジスタ＜２＞の出力ａ_ｍ−１の補数を求め、−ｊ^ｍａ_ｍ−１を生成し、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜３＞に出力する。

“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜３＞では、“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜２＞から出力された−ｊ^ｍａ_ｍ−１と、クロックｃｌに同期して“Ｒ（１〜ｐ−１）”レジスタ部から出力されるｃ_ｊ（＝ｃ^{（ｍ−２）} _ｊ）との和を生成し、ｃ^{（ｍ−１）} _ｊとして出力する。この“ｈ ｂｉｔ ＡＤ ｍｏｄ ｐ”回路ブロック＜３＞から出力されたｃ^{（ｍ−１）} _ｊは、クロックｃｌの立ち下がりに同期して“Ｒ（１〜ｐ−１）”レジスタ部の第ｊ番目のレジスタに記録される。なお、“Ｒｇｓｔｒ”レジスタ＜２＞の設定から“Ｒ（１〜ｐ−１）”レジスタ部の初期値は、ｃ^{（ｍ−２）} _ｊ＝ｃ^{（ｍ−１）} _ｊ＝Ｃとなる。

次に、図７６に示す“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックについて説明する。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックは、Ｚｐのゼロ以外の全ての要素１〜ｐ−１に対して、０〜ｐ−２乗を順次求めてレジスタに保持する回路である“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）”回路ブロックを変形させた回路である。

図７７は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックの回路記号を示す図である。また、図７８中（Ａ）は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックのブロック図であり、図７８中（Ｂ）は、“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックを制御するクロックｃｋ及びｃｌのタイミングチャートを示す。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路ブロックは、図７７に示すように、入力されるクロックｃｋ_ｉ（ｉ＝０〜ｐ−２）及びｃｌ_ｊ（ｊ＝１〜ｐ−１）に同期して（ｊ）^ｉ＋１及び（ｊ）^ｉを出力する。

“（ｊ）^ｉ（ｊ＝１ ｔｏ ｐ−１）２”回路は、“Ｃｏｕｎｔｅｒ（１〜ｐ−１）”回路ブロック、“Ｘ Ｚｐ”回路ブロック、及び“Ｒ（１〜ｐ−１）”レジスタ部を有する。

“Ｒ（１〜ｐ−１）”レジスタ部は、ｐ−１個のレジスタからなり、ｉｎのクロック／ｃｌの立ち上がりで入力を順次１〜ｐ−１番目のレジスタに格納し、ｏｕｔのクロック／ｃｌの立ち上がりで順次１〜ｐ−１番目のレジスタの内容を出力する。

“Ｘ Ｚｐ”回路ブロックでは、入力クロックｃｌに同期してカウントアップされる“Ｃｏｕｎｔｅｒ（１〜ｐ−１）”回路ブロックの出力と“Ｒ（１〜ｐ−１）”レジスタ部の出力との乗算を行う。

以上の構成によって、“Ｒ（１〜ｐ−１）”レジスタ部からは、ｃｋ_ｉの立ち上がった後のｃｌ_ｊの各サイクルでｃｌ_ｊが立ち上がる毎に（ｊ）^ｉが出力される。これと同時に、“Ｘ Ｚｐ”回路ブロックからは、（ｊ）^ｉとは指数が１つだけ異なった（ｊ）^ｉ＋１が出力される。

［シンドローム変換法］
次に、リー・メトリック・コードを表すコードの空間で見たとき、シンドローム変換法によるエラーの訂正が行っていることを検討し、この方法の有効に活用できる条件を検討する。

実際には不明な真のエラーコード語の点をＥ＝（ｅ_１，ｅ_２，・・・，ｅ_ｊ，・・・，ｅ_ｎ）とすると、シンドローム変換法では、これを仮想的なエラーコード語の点^ｍＥ＝（ｕ（１）^ｍｅ_１，ｕ（２）^ｍｅ_２，・・・，ｕ（ｊ）^ｍｅ_ｊ，・・・，ｕ（ｎ）^ｍｅ_ｎ）に変換している。このとき成分座標自体は不変であることに注意する。この場合、シンドロームは数６４のようになる。

［数６４］

これらの変換はｍ≠ｍ´、η≠η´の場合、^ｍＥ≠^ｍ´Ｅとなる。即ち、ηが異なれば同一の点になることが無い。これは、^ｍＥ＝^ｍ´Ｅの場合、全てのｉに対してｕ（ｉ）^ｍｅ_ｉ＝ｕ´（ｉ）^ｍ´ｅ_ｉ、つまり数６５が成立しなければいけないが、数６５は、Ｅ＝０以外では成立しないためである。

［数６５］

そこで、（ｊ）^ｐ−１＝１であるからｍ＝０〜ｐ-２についてスキャンし、ηとしてシンドローム変換法が解探索多項式の構成を簡単にするのに有効なηとしてγ−１とγ−２の２つを使う。こうすると、真のエラーコード語点も含めて、２（ｐ−１）個の点が得られる。これらの点が真のエラーと同じ様なリー・メトリックの制約を受けると考えられるエラーコード語点を全て含んでいれば、解探索多項式を求めて解を得ることによって、漏れの無いエラーの探索と、訂正が可能な場合の訂正ができる。

エラーコード語点を全て含まない場合は、真のエラーから変換された点以外にエラーに対応する点がありえるため、解探索が出来ないからといってエラーが特定できないとは言い切れず、エラー訂正に漏れが生じる場合もある。

そこで次は、エラー量の条件と、訂正が可能な条件を具体的に説明する。

シンドローム変換法では、シンドロームを巡回的に使用するｐ−１個の変換とηの値を用い、最大２（ｐ−１）個の変換を用いている。そこで次は、この変換によって、発生し得るエラーを全てカバーできるかを検討する。

前述の通り、エラーコード語の点をＥ＝（ｅ_１，ｅ_２，・・・，ｅ_ｊ，・・・，ｅ_ｎ）とすると、シンドローム変換法では、これを仮想的なエラーコード語の点^ｍＥ＝（ｕ（１）^ｍｅ_１，ｕ（２）^ｍｅ_２，・・・，ｕ（ｊ）^ｍｅ_ｊ，・・・，ｕ（ｎ）^ｍｅ_ｎ）となる。

ξ個のエラー成分位置があり、これらをｊ_ｉ（ｉ＝１〜ξ）で表すと、シンドローム変換では数６６のように和をηとできる。

［数６６］

数６６において、ε_ｉを変数と考えて、変数ε_ｉとしては１〜ｐ−１となること、ξ個の和がηと固定されていることから、各変数の値の選択は、（ｐ−１）^ξ−１となる。但し、このままでは最後の選択に０を含むため、この場合を排除する。

ξ個の自由変数ε_ｉの和がηと合同になる場合の数をｎ（ξ）とすると、最後の選択の前に和がηとなる場合を除いておかなければならないため、ｎ（ξ）＝（ｐ−１）^ξ−１−ｎ（ξ−１）となる。これから数６７のようなｎ（ξ）を得る。

［数６７］

この場合の中には成分が全て０〜ｐ／２の範囲にあるもの、即ち、Ｊ_＋のみに成分が属するものがあるため、変換の数が場合の数以上であれば、異なる変換は異なる場合をカバーできるので、Ｊ_＋の仮想エラーを作ることができて、シンドローム変換法で解ける。

シンドローム変換法から見た場合、この条件は、ξ＝２の場合であり、これは前述の考察の通り２根の場合である。しかし、３根以上（ξ≧３）の場合では解を求められないエラーの場合を排除することはできない。

つまり、これは、シンドローム変換法は処理が簡単であるものの、エラー訂正の取りこぼしがあることを示している。色々なパターンのエラーが生じてしまう可能性がある場合には、シンドローム変換法の変換の範囲を、シンドローム成分を循環的に変換する以外の変換方法を用いて変換数を増やすか、処理は複雑になりオンチップには不向きではあるがユークリッドの反復法を用いて解探索多項式を構成するのが良いことが分かる。

次に、リー・メトリック・コードでエラー訂正が可能な条件としてのｗ（Ｅ）≦εと、シンドローム変換法の漏れの無い探索条件との関係で、演算処理結果で得られるエラー量と誤訂正の関係をまとめる。

（１） εの分配数≦探索数の場合
・ 真のエラー語のリー・メトリックがε＝γ−１以下の場合： シンドローム変換法で得られた解Ｅで、そのリー・メトリックＷ（Ｅ）≦εなるものが見つかったら、それが真のエラーであることは確実なので、そこで解探索は終了する。

これはε以下のエラー語間の自己写像で解法が閉じるので、真のエラーと解法が適用できるエラーが対応するためである。

・ 真のエラー語のリー・メトリックがγ以上の場合： シンドローム変換法で得られた解Ｅで、そのリー・メトリックＷ（Ｅ）≦εなるものが見つかったら、これは隣のコードへの誤エラーであるが、このようなエラーと真のエラーの判断はリー・メトリック・コード上では出来ない。

なお、これはどの様なＥＣＣであっても排除できない誤訂正の場合である。

・ シンドローム変換法で得られた解Ｅに、そのリー・メトリックｗ（Ｅ）≦εなるものがない場合： コード語間の隙間にエラーコード点が落ち込んだ場合であり、シンドローム変換法では真のエラーを見つけることが出来る可能性がある。

エラーは真のコードに最短であり、そのコードにユニークに帰属すると考えられるので、シンドローム変換法で得られたエラーＥの中から最小のリー・メトリックｗ（Ｅ）＞εを持つものをＥ_ｍｉｎとして、Ｅ_ｍｉｎがただ１つの成分構成によって満たされる場合、Ｅ_ｍｉｎを真のエラーとして採用する。これは真のエラーから変換で得られる全ての仮想的なエラーで真のエラーの発生パターンの全ての場合を網羅しているので、エラーが確定するためである。但し、Ｅ_ｍｉｎが複数ある場合は確定しないので解が得られない。

（２） ε分配数＞探索数の場合
真のエラーに対する誤訂正の他に、シンドローム変換法としての取りこぼしが生じてしまう。

探索の手順としては、εの分配数≦探索数の場合、「解Ｅが見つかる毎にｗ（Ｅ）を計算する。ｗ（Ｅ）≦εの場合、真のエラーが見つかったため処理を終了し、ｗ（Ｅ）＞εの場合、スキャンを続けて、更に、小さいｗ（Ｅ）を見つける。全ての処理の最後で最小のｗ（Ｅ）がｗ（Ｅ）＞εの場合、解法が適用できない場合である」となる。

［ｐ−ａｄｉｃメモリシステムの検証方法］
最後に、「ｐ-ａｄｉｃ ｗｏｒｌｄ」での演算処理の回路の動作を検証する簡便な方法について説明する。

「ｂｉｎａｒｙ ｗｏｒｌｄ」と「ｐ-ａｄｉｃ Ｚｐ ｗｏｒｌｄ」の入口での変換やｐ-ａｄｉｃメモリシステムへのリー・メトリック・コード変換の回路は複雑であり、その働きを検証し特定するのは困難である。

そこで、入力データとセルアレイが保持するデータの状態を見て回路動作の判断が出来れば有効となる。特殊なデータパターンに対してｐ−ａｄｉｃセルの取る状態が特殊になることを利用してこの検証を行うことが出来るので、これを説明する。この検証方法は、一括処理されるデータとして‘０’と‘１’を用い、このときのセルアレイのメモリセルの状態をモニターして判断する方法となる。

入力データは、数６８のように表わすことができる。

［数６８］

ここで、ＥＣＣ一括処理対象の入力データをバイナリで１とする。この場合、入力データのバイナリ表現と、ｐ進数表現は数６９のようになる。

［数６９］

入力データのバイナリを１とした場合、Ｚｐとセルレベルの対応が各メモリセルで同一であるとすると、これを記憶するするメモリセル群の多値レベルは全て異なるものに設定される。

バイナリデータ数として０を入れた場合と１を入れた場合で同じレベル設定のメモリセルが存在しない。これは数７０の関係から、必要にして十分な判断条件であり、リー・メトリック・コードでは０は（０，０，…，０，０，０）のコード語、１は（１，２，…，ｐ−３，ｐ−２，ｐ−１）のコード語になるからである。

［数７０］

なお、バイナリデータの‘１’がどのビット位置を‘１’とした時であるかは回路の設定によるものなので、この変換を固有な対応にするとデータを容易に解読できないようにも出来る。

これらの回路動作の判定条件からも分かるように、セルレベルとＺｐの数の対応はメモリセル毎に変えることが出来、入力バイナリと記憶データのｐ進数に線形の関係がないので変換回路においてはバイナリとｐ進数の対応を勝手に設定できる。したがって、この回路をロックすれば記憶データから直接入力バイナリを逆読みすることは困難であり、データのセキュリティへの応用も容易となることも分かる。

以上をまとめると、本実施本実施形態に係るｐ−ａｄｉｃメモリシステムのコード変換によれば、メモリシステムに入力されるコードと、メモリセルに記録されたレベルの対応は、結果的に以下のようになる。

（１） 所定数のｐ−ａｄｉｃセルを処理単位にした場合、入力されたバイナリデータが０の場合、処理単位に属する全てのｐ−ａｄｉｃセルに対しＺｐの０に対応するセルレベルが書き込まれる。

（２） ｐ−１個のｐ−ａｄｉｃセルを処理単位にした場合、入力されたバイナリデータの１ビットのみが‘１’の場合、処理単位に属するｐ−ａｄｉｃセルには、Ｚｐの１〜ｐ−１に対応する全てのセルレベルが書き込まれる。

（３） 上記（２）の場合であって、処理単位に属する全てのメモリセルのＺｐの要素とセルレベルとの対応関係が同一であった場合、処理単位に属するメモリセルに書き込まれたセルレベルは全て異なる。

（４） 上記（１）及び（２）から、ｐ−１個のｐ−ａｄｉｃセルを処理単位にした場合、処理単位に属する各メモリセルにおいて、入力されたバイナリデータが０だった場合に書き込まれるセルレベルと、入力されたバイナリデータの１ビットのみが‘１’だった場合に書き込まれるセルレベルは異なっている。

以上、従来、メモリセルの多値化には安定した精度の高い動作を必要としたが、本実施形態に係るメモリシステムによれば、高効率のエラー訂正によって、従来に比べて、動作マージンを大きくとることができるため、メモリセルの更なる多値化を図ることができる。

［その他］
以上、発明の実施の形態を説明したが、本発明はこれらに限定されるものではなく、発明の趣旨を逸脱しない範囲内において、種々の変更、追加等が可能である。

本発明の実施形態は、３以上のレベル数を有するセルを用いたメモリシステムであれば適用することができる。例えば、フラッシュメモリ、ＤＲＡＭ、ＰＲＡＭ、ＲｅＲＡＭなどを用いたメモリシステムに適用することが可能である。

１０１・・・ｐ進数変換部、２０１・・・エンコード部、２０２・・・ｐ−ａｄｉｃセルメモリ部、２０３・・・シンドローム生成部、２０４・・・解探索多項式生成部、２０５・・・ハッセ微分多項式生成部、２０６・・・コード復元部、２０７・・・デコード部、３０１・・・バイナリ変換部。

Claims (10)

1. ｐ（ｐは３以上の素数）以上の物理量レベルを持つセルユニットからなるセルアレイと、
   バイナリ表現の入力データを、ｐの剰余体であるＺｐの要素で表現された書き込みコードに変換するコード生成部と、
   Ｚｐの各要素をそれぞれ異なる前記物理量レベルに対応させて前記セルユニットに前記書き込みコードを書き込むコード書き込み部と
   を備え、
   前記入力データをｐ−１個の前記セルユニットに記録する場合において、これらｐ−１個の前記セルユニットのうち、前記入力データが０の場合と、１ビットのみが１の場合で、同一の物理量レベルに書き込まれるセルユニットはない
   ことを特徴とするメモリシステム。
2. 前記書き込みコードは、リー・メトリック・コードである
   ことを特徴とする請求項１記載のメモリシステム。
3. 前記コード生成部は、ｐを法とする足し算回路の組み合わせからなる
   ことを特徴とする請求項１又は２記載のメモリシステム。
4. 前記セルユニットに記録された物理量レベルを、この物理量レベルに対応するＺｐの要素によって表現された読み出しコードとして読み出すコード読み出し部と、
   前記読み出しコードをバイナリ表現の出力データに変換するデコード部と
   を備える
   ことを特徴とする請求項１〜３のいずれか１記載のメモリシステム。
5. 前記読み出しコードのエラー検出・訂正を行うエラー検出・訂正部を備え、
   前記エラー検出・訂正部は、前記読み出しコードからシンドロームを生成し、このシンドロームの成分の組み合わせを順次変更しながらエラー探索する
   ことを特徴とする請求項４記載のメモリシステム。
6. 前記エラー検出・訂正部は、ｐを法とする足し算回路からなる
   ことを特徴とする請求項５記載のメモリシステム。
7. 前記エラー検出・訂正部は、予め算出されたＺｐの要素の逆元及び階上の少なくとも一方のテーブルを有する
   ことを特徴とする請求項５又は６記載のメモリシステム。
8. 前記デコード部は、前記エラー検出・訂正部によって、前記読み出しコードのエラーが検出できなかった場合、エラーを含む前記読み出しコードをそのまま前記出力データに変換する
   ことを特徴とする請求項５〜７のいずれか１項記載のメモリシステム。
9. 前記所定のセルユニットにおけるＺｐの要素と前記物理量レベルとの対応関係は、他の前記セルユニットにおけるＺｐの要素と前記物理量レベルとの対応関係と異なる
   ことを特徴とする請求項１〜８のいずれか１項記載のメモリシステム。
10. 前記セルユニットは、複数のメモリセルからなる
    ことを特徴とする請求項１〜９のいずれか１項記載のメモリシステム。