(57)【特許請求の範囲】
【請求項１】
エラーロケータ多項式の解を求めることで、コードワードの４つのエラー位置を決定するエラーロケータプロセッサを用いて、リードソロモン符号またはＢＣＨ符号の前記コードワード内の４つのエラーの位置を決定する方法であって、
前記エラーロケータプロセッサは、
２つのエラー位置を決定するために２次元多項式を解くように構成された２エラープロセッサと、
３つのエラー位置を決定するために３次元多項式を解くように構成された３エラープロセッサと、
４つのエラー位置を決定するために４次元多項式を解くように構成された４エラープロセッサとを含み、
この前記４エラープロセッサにより実行される方法は、
ａ．四次エラーロケータ多項式
【数１】
0003830527.tif 000050
を操作して
【数２】
0003830527.tif 000051
の形の多項式を生成するステップと、
ｂ．多項式を因数分解して、
【数３】
0003830527.tif 000052
にするステップと、
ｃ．ステップａおよびステップｂの多項式の係数を等置するステップと、
【数４】
0003830527.tif 000053
ｄ．唯一の未知数ｔを持つ方程式
【数５】
0003830527.tif 000054
を決定するステップと、
ｅ．前記３エラープロセッサを使用して解ｔ0について解くステップとを備え、
【数６】
0003830527.tif 000055
の解について解くステップは、
ｉ．変数を
【数７】
0003830527.tif 000056
ここで
【数８】
0003830527.tif 000057
に変えて、
【数９】
0003830527.tif 000058
の形の方程式を生成するステップと、
ii．ステップｉの方程式をｚ3で乗して、変数ｚ3を持つ二次方程式を得るステップと、
【数１０】
0003830527.tif 000059
iii．ステップiiの二次方程式をｚ3について解くステップと、
iv．ｚ3の立方根ｚ0を決定するステップと、
v．ｚ0の値を式
【数１１】
0003830527.tif 000060
に代入するステップとを含み、
ｆ．ｕおよびｗを解とする二次方程式を形成するステップと、
【数１２】
0003830527.tif 000061
ｇ．前記２エラープロセッサを使用して解ｐ0およびｐ1について解くステップと、
ｈ．解をθ（ｙ）に代入して前記２エラープロセッサを使用して以下の１対の二次方程式の解を決定するステップと、
【数１３】
0003830527.tif 000062
ｉ．１対の二次方程式の解ｙ0、ｙ1およびｙ2、ｙ3を、四次エラーロケータ多項式の解と関連付けるステップと、
ｊ．四次エラーロケータ多項式の解をコードワード内の位置と関連付けるステップとをさらに備える、コードワード内の４つのエラーの位置を決定する方法。
【請求項２】
エラーロケータ多項式の解を求めることで、コードワードの４つのエラー位置を決定するエラーロケータプロセッサを用いて、リードソロモン符号またはＢＣＨ符号の前記コードワード内の４つのエラーの位置を決定する方法であって、
前記エラーロケータプロセッサは、
２つのエラー位置を決定するために２次元多項式を解くように構成された２エラープロセッサと、
４つのエラー位置を決定するために４次元多項式を解くように構成された４エラープロセッサとを含み、
この前記４エラープロセッサにより実行される方法は、
ａ．四次エラーロケータ多項式
【数１４】
0003830527.tif 000063
を操作して、
【数１５】
0003830527.tif 000064
の形の多項式を生成するステップと、
ｂ．多項式を、因数分解して
【数１６】
0003830527.tif 000065
にするステップとを備え、
エラーロケータ多項式をθ（ｙ）に変換するステップは、
ｉ．変数をｘ＝ｙ＋ｒここで
【数１７】
0003830527.tif 000066
に変え、項を展開しまとめて
【数１８】
0003830527.tif 000067
の形の方程式を生成するステップと、
ｉｉ．
【数１９】
0003830527.tif 000068
をステップｉの方程式に代入し、
【数２０】
0003830527.tif 000069
の形の方程式を生成するステップを含み、ここでｓはステップｉの方程式の定数項であり、さらに、
iii．
【数２１】
0003830527.tif 000070
ここで
【数２２】
0003830527.tif 000071
に展開される、
【数２３】
0003830527.tif 000072
の解を求めるステップとを含み、
ｃ．ステップａおよびステップｂの多項式の係数を等置するステップと、
【数２４】
0003830527.tif 000073
ｄ．唯一の未知数ｔを持つ方程式
【数２５】
0003830527.tif 000074
を決定するステップと、
ｅ．前記３エラープロセッサを使用して解ｔ0について解くステップとを備え、
ｆ．ｕおよびｗを解とする二次方程式を形成するステップと、
【数２６】
0003830527.tif 000075
ｇ．前記２エラープロセッサを使用して解ｐ0およびｐ1について解くステップと、
ｈ．解をθ（ｙ）に代入して前記２エラープロセッサを使用して以下の１対の二次方程式の解を決定するステップと、
【数２７】
0003830527.tif 000076
ｉ．１対の二次方程式の解ｙ0、ｙ1およびｙ2、ｙ3を、四次エラーロケータ多項式の解と関連付けるステップと、
ｊ．四次エラーロケータ多項式の解をコードワード内の位置と関連付けるステップとをさらに備える、コードワード内の４つのエラーの位置を決定する方法。
【請求項３】
エラーロケータ多項式の解を求めることで、コードワードの４つのエラー位置を決定するエラーロケータプロセッサを用いて、リードソロモン符号またはＢＣＨ符号のコードワード内の４つのエラーの位置を決定する方法であって、
前記エラーロケータプロセッサは、
２つのエラー位置を決定するために２次元多項式を解くように構成された２エラープロセッサと、
４つのエラー位置を決定するために４次元多項式を解くように構成された４エラープロセッサとを含み、
この前記４エラープロセッサにより実行される方法は、
ａ．四次エラーロケータ多項式
【数２８】
0003830527.tif 000077
を操作して、
【数２９】
0003830527.tif 000078
の形の多項式を生成するステップと、
ｂ．多項式を、因数分解して
【数３０】
0003830527.tif 000079
にするステップと、
ｃ．ｔ、ｕ、ｖ、およびｗの値を決定するステップとを備え、
ｔ、ｕ、ｖ、およびｗの値を決定するステップは、
ｉ．ステップａおよびステップｂの多項式の係数を等置するステップと、
【数３１】
0003830527.tif 000080
ｉｉ．唯一の未知数ｔを持つ方程式を決定するステップと、
【数３２】
0003830527.tif 000081
ｉｉｉ．解ｔ0について解くステップとを含み、
【数３３】
0003830527.tif 000082
の解について解くステップは、
ａ．変数を
【数３４】
0003830527.tif 000083
ここで
【数３５】
0003830527.tif 000084
に変え、
【数３６】
0003830527.tif 000085
の形の方程式を生成するステップと、
ｂ．ステップａの方程式をｚ3で乗してｚ3を変数とする二次方程式を得るステップと、
【数３７】
0003830527.tif 000086
ｃ．ステップｂの二次方程式をｚ3について解くステップと、
ｄ．ｚ3の立方根ｚ0を決定するステップと、
ｅ．ｚ0の値を式
【数３８】
0003830527.tif 000087
に代入するステップとを有し、
ｉｖ．ｕおよびｗを解とする二次方程式を形成するステップと、
【数３９】
0003830527.tif 000088
ｖ．ｕおよびｗである解ｐ0およびｐ1について解くステップとをさらに含み、
ｄ．値ｔ、ｕ、ｖ、およびｗをθ（ｙ）に代入し、前記２エラープロセッサを使用して、以下の１対の二次方程式の解を決定するステップと、
【数４０】
0003830527.tif 000089
ｅ．前記１対の二次方程式の解ｙ0、ｙ1およびｙ2、ｙ3を、四次エラーロケータ多項式の解と関連付けるステップと、
ｆ．四次エラーロケータ多項式の解をコードワード内の位置と関連付けるステップとを含む、コードワード内の４つのエラーの位置を決定する方法。
【請求項４】
エラーロケータ多項式の解を求めることで、コードワードの４つのエラー位置を決定するエラーロケータプロセッサを用いて、リードソロモン符号またはＢＣＨ符号のコードワード内の４つのエラーの位置を決定する方法であって、
前記エラーロケータプロセッサは、
２つのエラー位置を決定するために２次元多項式を解くように構成された２エラープロセッサと、
４つのエラー位置を決定するために４次元多項式を解くように構成された４エラープロセッサとを含み、
この前記４エラープロセッサにより実行される方法は、
ａ．四次エラーロケータ多項式
【数４１】
0003830527.tif 000090
を操作して、
【数４２】
0003830527.tif 000091
の形の多項式を生成するステップと、
ｂ．多項式を、因数分解して
【数４３】
0003830527.tif 000092
にするステップとを備え、
エラーロケータ多項式をθ（ｙ）に変換するステップは、
ｉ．変数をｘ＝ｙ＋ｒ、ここで
【数４４】
0003830527.tif 000093
に変え、項を展開しまとめて、
【数４５】
0003830527.tif 000094
の形の方程式を生成するステップと、
ii．
【数４６】
0003830527.tif 000095
をステップｉの方程式に代入し、
【数４７】
0003830527.tif 000096
の形の方程式を生成するステップとを含み、ここでｓはステップｉの方程式の定数項であり、さらに
iii.展開すると、
【数４８】
0003830527.tif 000097
ここで
【数４９】
0003830527.tif 000098
の解を求めるステップとを含み、
ｃ．ｔ、ｕ、ｖ、およびｗの値を決定するステップと、
ｄ．値ｔ、ｕ、ｖ、およびｗをθ（ｙ）に代入し、前記２エラープロセッサを使用して、以下の１対の二次方程式の解を決定するステップと、
【数５０】
0003830527.tif 000099
ｅ．前記１対の二次方程式の解ｙ0、ｙ1およびｙ2、ｙ3を、四次エラーロケータ多項式の解と関連付けるステップと、
ｆ．四次エラーロケータ多項式の解をコードワード内の位置と関連付けるステップとをさらに備える、コードワード内の４つのエラーの位置を決定する方法。
【請求項５】
リードソロモン符号またはＢＣＨ符号のコードワード内の４つのエラーの位置を決定するデコーダであって、
前記コードワードと関連するエラーシンドロームの組を生成するシンドローム発生器と、
前記エラーシンドロームからエラーロケータ多項式を生成するエラーロケータ多項式発生器と、
前記エラーロケータ多項式の解を求めることで、前記コードワードのエラー位置を決定するエラーロケータプロセッサとを備え、
前記エラーロケータプロセッサは、
２つのエラー位置を決定するために２次元多項式を解くように構成された２エラープロセッサと、
３つのエラー位置を決定するために３次元多項式を解くように構成された３エラープロセッサと、
４つのエラー位置を決定するために４次元多項式を解くように構成された４エラープロセッサとを含み、前記４エラープロセッサは、前記エラーロケータ多項式発生器が４次のエラーロケータ多項式を生成した場合に、
ａ）四次エラーロケータ多項式
【数５１】
0003830527.tif 000100
を操作して
【数５２】
0003830527.tif 000101
の形の多項式を生成し、
ｂ）多項式を因数分解して、
【数５３】
0003830527.tif 000102
にし、
ｃ）前記ステップａおよびｂで得られた多項式の係数を以下のように等置し、
【数５４】
0003830527.tif 000103
ｄ）唯一の未知数ｔを持つ方程式
【数５５】
0003830527.tif 000104
を決定し、
ｅ）前記３エラープロセッサを使用して解ｔ0について解き、
【数５６】
0003830527.tif 000105
の解について解くにあたり、
ｉ．変数を
【数５７】
0003830527.tif 000106
ここで
【数５８】
0003830527.tif 000107
に変えて、
【数５９】
0003830527.tif 000108
の形の方程式を生成し、
ii．ｉの方程式をｚ3で乗して、変数ｚ3を持つ二次方程式を得て、
【数６０】
0003830527.tif 000109
iii．iiの二次方程式をｚ3について解き、
ｉｖ．ｚ3の立方根ｚ0を決定し、
ｖ．ｚ0の値を式
【数６１】
0003830527.tif 000110
に代入し、
ｆ）ｕおよびｗを解とする以下の二次方程式を形成し、
【数６２】
0003830527.tif 000111
ｇ）前記２エラープロセッサを使用して解ｐ0およびｐ1について解き、
ｈ）前記ステップｇでの解を
に代入して以下の１対の二次方程式の解を決定し、
【数６３】
0003830527.tif 000112
ｉ）前記１対の二次方程式の解ｙ0、ｙ1およびｙ2、ｙ3を、四次エラーロケータ多項式の解と関連付け、
ｊ）前記四次エラーロケータ多項式の解をコードワード内の位置と関連付ける、デコーダ。
【請求項６】
リードソロモン符号またはＢＣＨ符号のコードワード内の４つのエラーの位置を決定するデコーダであって、
前記コードワードと関連するエラーシンドロームの組を生成するシンドローム発生器と、
前記エラーシンドロームからエラーロケータ多項式を生成するエラーロケータ多項式発生器と、
前記エラーロケータ多項式の解を求めることで、前記コードワードのエラー位置を決定するエラーロケータプロセッサとを備え、
前記エラーロケータプロセッサは、
２つのエラー位置を決定するために２次元多項式を解くように構成された２エラープロセッサと、
４つのエラー位置を決定するために４次元多項式を解くように構成された４エラープロセッサとを含み、前記４エラープロセッサは、前記エラーロケータ多項式発生器が４次のエラーロケータ多項式を生成した場合に、
ａ）四次エラーロケータ多項式
【数６４】
0003830527.tif 000113
を操作して、
【数６５】
0003830527.tif 000114
の形の多項式を生成し、
ｂ）多項式を、因数分解して
【数６６】
0003830527.tif 000115
にし、
ｃ）ｔ、ｕ、ｖ、およびｗの値を決定し、
ｔ、ｕ、ｖ、およびｗの値を決定するにあたり、
ｉ．ステップａおよびステップｂの多項式の係数を等置し、
【数６７】
0003830527.tif 000116
ｉｉ．唯一の未知数ｔを持つ方程式を決定し、
【数６８】
0003830527.tif 000117
ｉｉｉ．解ｔ0について解き、
【数６９】
0003830527.tif 000118
の解について解くにあたり、
ａ．変数を
【数７０】
0003830527.tif 000119
ここで
【数７１】
0003830527.tif 000120
に変え、
【数７２】
0003830527.tif 000121
の形の方程式を生成し、
ｂ．ステップａの方程式をｚ3で乗してｚ3を変数とする二次方程式を得て、
【数７３】
0003830527.tif 000122
ｃ．ステップｂの二次方程式をｚ3について解き、
ｄ．ｚ3の立方根ｚ0を決定し、
ｅ．ｚ0の値を式
【数７４】
0003830527.tif 000123
に代入し、
ｉｖ．ｕおよびｗを解とする二次方程式を形成し、
【数７５】
0003830527.tif 000124
ｖ．ｕおよびｗである解ｐ0およびｐ1について解き、
ｄ）値ｔ、ｕ、ｖ、およびｗをθ（ｙ）に代入し、前記２エラープロセッサを使用して、以下の１対の二次方程式の解を決定し、
【数７６】
0003830527.tif 000125
ｅ）前記１対の二次方程式の解ｙ0、ｙ1およびｙ2、ｙ3を、四次エラーロケータ多項式の解と関連付け、
ｆ）四次エラーロケータ多項式の解をコードワード内の位置と関連付け、コードワード内の４つのエラーの位置を決定する、デコーダ。
【発明の詳細な説明】
発明の分野
この発明は、一般に、データ処理システムに関し、より特定的には、エラー訂正コードを用いたデータにおけるエラーを復号しかつ訂正するためのシステムに関する。
発明の背景
磁気ディスクなどの磁気媒体上に記憶されたデータは、典型的には、符号化された形で記憶されており、したがって記憶されたデータ内のエラーを恐らくは訂正することができる。エラーは、たとえば、符号間干渉、ディスク内の欠陥、またはノイズによって起こり得る。ディスク上に記憶されるデータの密度が増加するに伴い、より多くのエラーが起こりかねず、システムはより多数のエラーを訂正せねばならない。システムがエラーを訂正する速度は、システムがデータを処理する全体的な速度において重要である。
記憶する前に、多ビットデータシンボルはエラー訂正コード（ＥＣＣ）を用いて符号化される。データシンボルがディスクから検索され復調されるとき、ＥＣＣが用いられ、その名前が示しているように誤ったデータを訂正する。
特定的には、ｋ個のデータシンボルの列はディスクに書込まれる前に、（ｎ，ｋ）ＥＣＣを用いて数学的に符号化され、ｎ−ｋ  ＥＣＣシンボルを形成する。ＥＣＣシンボルは次にデータの列に添えられｎ−シンボルエラー訂正コードワードを形成し、これは次にディスクに書込まれるかまたはディスク上に記憶される。データがディスクから読出されるとき、データシンボルおよびＥＣＣシンボルを含むコードワードは検索されそして数学的に復号される。復号の間、データ内のエラーは検出されそしてもし可能ならば、ＥＣＣシンボルの操作によって訂正される（復号についての詳細な説明に関しては、ピーターソン(Peterson)およびウェルドン(Weldon)の『エラー訂正コード(Error Correction Codes)』第２版、MIT出版、1972を参照）。
データシンボルの列の中の多数のエラーを訂正するためには、システムは典型的には、ガロア体として知られる数組のシンボルのさまざまな数学的特性を効率的かつ効果的に利用するＥＣＣを用いる。ガロア体は、「ＧＦ（Ｐm）」と表わされ、「Ｐ」は素数であり、「ｍ」は体の中の各要素またはシンボル内の基数「Ｐ」の桁数と考え得る。Ｐは普通デジタルコンピュータおよびディスクドライブアプリケーションにおいては値２をとり、したがって、ｍは各シンボル内のビット数である。一般にガロア体とともに使用されるＥＣＣは、リードソロモン符号またはＢＣＨ符号である。
リードソロモン符号またはＢＣＨ符号の改変されたコードワードの復号には本質的に４つの主要ステップがある。システムはまずＥＣＣシンボルの操作の結果に基づいたエラーシンドロームを決定する。次に、エラーシンドロームを用いて、システムはエラーロケータ多項式を決定する。これはエラーの数と同じ数の次数を有する多項式である。システムは次にエラーロケータ多項式の解を求め、各解からコードワード内の関連するエラーの位置を決定する。最後に、システムはエラー位置に対するエラー値を求める。デジタルコンピュータなどの２進システムにおいてはエラー位置に対して可能なエラー値は１つしかないので、エラー値を決定するステップは重要ではない。
エラー訂正処理の中で最も時間を費やすのは、シンドロームを決定し、エラー位置を求めるステップである。ここに説明する発明は、３つまたは４つのエラーの位置を求めるためにエラー訂正システムの費やす時間を減じる。これは、三次および四次のエラーロケータ多項式の解を求めることを含む。
先行のシステムにおいては、四次の多項式の解は、試行錯誤またはマトリックス操作もしくはルックアップテーブルによって決定されている。試行錯誤法は、あらゆる可能な値、すなわちコードワード位置に関連する適用可能なＧＦ（２2m）のすべての要素を多項式に代入し、各値について多項式の数値を求めることによって行なわれる。もし所与の値について多項式がゼロに等しければ、その値が解である。このシステムは、次に可能な値を多項式に代入しその値が解かどうかを判断することによってこの試行錯誤処理を続け、すべての可能な値が試されてしまうかまたはすべての４つの解が決定されるまでこれを続ける。この試行錯誤処理は、最適化された形態では通常チェンサーチとして知られているが、時間のかかるものである。さらに、コードワード内のエラーの位置によって処理に費やされる時間が変化するために、処理にかかる時間を予測することができない。
マトリックス操作およびルックアップテーブル法は、
σ4x4+σ3x3+σ2x2+σ1x+σ0
の形の一般四次多項式を変換して、
x4+x2+ax+b
の形の多項式にすることを含んでいる。
ルックアップテーブルが使用されるのならば、テーブルは、ａおよびｂの可能な値のすべての組に対しての解の組を含んでいる。今日使用されている典型的にはＧＦ（２8）にわたるＥＣＣについては、テーブルは２16のエントリを有し、その各々が３２ビットすなわち４つの８ビット要素を有する。したがって、テーブルはかなりの量の記憶空間を占め、比較的複雑なアドレッシング機構を必要とする。
マトリックス操作法を用いたシステムは、f(α),f(α1),f(α2),...f(αm-1)で、ここでf(x)=x4+x2+ax+bであるものを決定することにより、ｍ×ｍのマトリックスを生成する。次に、マトリックスを操作してマトリックスによって広がりが規定される空間のナル空間を決定する。多項式の解は次にナル空間にわたるベクトルから得ることができる（より詳細な説明については、Ｅ・Ｒ・ベールカンプ(Berlekamp)『代数的コード理論(Algebraic Coding Theory)』、マグロウヒルブックカンパニー(McGraw Hill Book Company)、1968年を参照）。この方法では、ｍ×ｍのマトリックスのビット毎の操作が必要となり、典型的にはマトリックスを変換するために多くの操作演算が必要である。したがって、この方法は時間がかかりかつ計算に集中している。
ここで説明するこの発明のシステムは、４つのエラー位置を求めるためにかかる時間を減じ、四次多項式の解を決定することを含む。このシステムは、ベールカンプによって『代数的コード理論』に説明されているような二次多項式の解を決定する周知の方法を利用している。さらに、このシステムは、ファンデルホルスト(Van der Horst)およびバーガー(Berger)によって「三重エラー訂正２進ＢＣＨコードの完全なデコーディング(Complete Decoding of Triple-Error-Correcting Binary BCH Codes)」『情報理論についてのIEEE紀要(IEEE Transactions on Infomation Theory)』、Vol.IT-22、1976年、138頁から147頁に説明されている三次多項式の解を決定する方法を利用している。
ファンデルホルストおよびバーガーの教示に従って三次多項式の解を求めるためには、ＧＦ（２2m）にわたってのガロア体要素の立方根を決定することが必要である。後にここで説明するように、本発明者は比較的迅速かつ容易に立方根を求めるためのある発明の回路を開発した。
発明の概要
この発明は、四次エラーロケータ多項式を最終的に２つの二次方程式に変換し、これらの方程式の解を求め、これらの解からエラーロケータ多項式の解を決定することによって、ＧＦ（２2m）内の４つのエラーのエラー位置を決定するシステムである。
より特定的には、このシステムは、最初に四次多項式
σ(x)=σ4x4+σ3x3+σ2x2+σ1x+σ0
［１］
を操作して、
θ(y)=y4+θ2y2+θ1y+θ0
［２］
の形にする。ここで、θiはエラーロケータ多項式の項の係数の組合せである。y3の項の係数がゼロであることに注意されたい。
このシステムは次にθ(y)を因数分解して、
θ(y)=(y2+t*y+u)*(y2+v*y+w),
［３］
にし、ここで「*」は乗法を表わし、そしてこの式を展開して、
θ(y)=y4+(t+v)y3+(t*v+u+w)y2+(t*w+v*u)y+u*w.
［４］
にし、ここでｔ、ｕ、ｖ、およびｗは未知数である。式２および式３の係数を等置して、このシステムは、
t+v=0
t*v+u+w=t2+u+w=θ2
［５］
t*w+u*v=t+w+t*u=t*(w+u)=θ1
u*w=θ0
と決定する。
このシステムは次に変数ｔを唯一の未知数とする方程式を生成する。
t3+θ2t+θ1=0
［６］
この三次方程式は以下により詳細に説明するように、ファンデルホルストおよびバーガーによって説明されている方法を用いて解くことができる。
一旦方程式６の解t0が決定されると、この解はθ1についての式に代入され、そしてこの式およびθ0についての式を用いてｕおよびｗを解とする二次方程式が形成される。
p2+(θ2+t02)p+θ0=0
［７］
このシステムは次に二次多項式を解くためのベールカンプの方法を用いて、方程式７の解p0およびp1を求める。解p0およびp1はそれぞれｕおよびｗであるが、多項式３に代入され、各項はゼロとされ、２つの二次方程式が生成される。
y2+t0*y+p0=0
［８］
y2+t0*y+p1=0
ベールカンプ法を用いて決定される方程式８の解はまた、θ(y)の解でもあり、したがってエラーロケータ多項式の解を生成するために直接用いることができる。
この直接的解法は、４つの解を求める、先行の試行錯誤またはマトリックス操作法よりも迅速である。さらに、他の先行の既知のシステムにおいて必要とされるように大きなルックアップテーブルを記憶したりそこにエントリしたりすることは必要ない。
【図面の簡単な説明】
この発明の性質および目的をより完全に理解するために、添付された図面に関連する以下の詳細な説明を参照されたい。図面中では、
図１は、この発明により構築されるデコーダの機能ブロック図である。
図２は、ＧＦ（２2m）要素の立方根を決定するための発明の回路の機能ブロック図である。
図３は、図２の回路の動作のフローチャートである。
図４は、ＧＦ（２8）についての図２の回路である。
図５は、図１のデコーダが４つのエラーの位置を決定するときに行なう動作のフローチャートである。
好ましい実施例の説明
ここで説明する加減乗除の数学演算は、ＧＦ（２2m）にわたってのガロア体の演算である。
次に図１を参照すると、デコーダ１０はシンドローム発生器１２を含み、これは、従来の態様でエラーシンドロームの関連する組を生成するために動作する。もしシンドロームがすべてゼロであれば、シンドローム発生器１２はコードワードにエラーはないと判断する。そうでなければ、シンドローム発生器はシンドロームをエラーロケータ多項式発生器１４に送り、これは従来の態様でシンドロームから次数「ｅ」のエラーロケータ多項式を生成する。ここでｅはコードワード内のエラーの数である。エラーロケータ多項式発生器１４は次にエラーロケータ多項式をエラーロケータプロセッサ１６に送り、これはエラーロケータ多項式の解、すなわちエラー位置を決定するための適切な処理を選択しかつ実施する。図１は、これらの処理をいくつかのブロックまたはプロセッサとして描いている。つまり、１つのエラー位置を決定するためのプロセッサ１８、２つのエラー位置を決定するためのプロセッサ２０、３つのエラー位置を決定するためのプロセッサ２２、４つのエラー位置を決定するためのプロセッサ２４、および４つより多くのエラー位置を決定するためのプロセッサ２６である。
２つ、３つ、および４つのエラープロセッサ２０、２２および２４は相互接続されている。以下に説明するように、エラーロケータプロセッサ１６は対応するエラーロケータ多項式を最終的に関連する二次方程式の組に変換することによって３つおよび４つのエラー位置を決定するためにかかる時間を減ずる。そのために、４つのエラープロセッサ２６は３つのエラープロセッサ２４および２つのエラープロセッサ２２の両者を利用する。同様に、３つのエラープロセッサ２４は２つのエラープロセッサ２２を利用する。これらの処理は、別個の専用プロセッサ内で起こっているように描かれているが、１つまたは２つ以上の多目的プロセッサ内で行なわれてもよい。
エラーロケータプロセッサ１６は、従来の態様で１つおよび２つのエラーの位置を決定する。これは、ファンデルホルストおよびバーガーによって説明される方法によって３つのエラーの位置を決定する。しかしながら、これは、ガロア体要素の立方根を決定する必要なステップを行なうために発明の回路を使用する。この回路および３つのエラーの位置を決定するための方法が、図２および図３を参照し以下に説明される。
エラーロケータプロセッサ１６は、図４を参照して以下に説明される独特の処理を用いて４つのエラーの位置を決定する。この処理を説明する前に、２つのエラー位置処理および３つのエラー位置処理がそれぞれＡ節およびＢ節で説明される。
Ａ．２つのエラー位置の決定
もしコードワードが２つのエラーを含んでいたならば、エラーロケータ多項式の形は、
σ(x)=σ2x2+σ1x+σ0
［１］
となる。この多項式の解を求めるために、このシステムは多項式をゼロに等しいとおく。
σ(x)=σ2x2+σ1x+σ0=0
［２］
そしてこの方程式を解x0およびx1について解く。
方程式２を解くためにエラーロケータプロセッサ１６はこの方程式の形を変換する。
y2+y+C=0
［３］
変数を、
0003830527.tif 000002
と変えることによって、方程式２は、
0003830527.tif 000003
となる。次に、これを
0003830527.tif 000004
で除することによって、このシステムは次の方程式を生成する。
0003830527.tif 000005
したがって、方程式３のＣは
0003830527.tif 000006
である。
方程式５の解がＧＦ（２2m）内に存在するためには、方程式の両辺の「トレース」は同じでなくてはならない。トレースは、
0003830527.tif 000007
と定義される。
トレース（０）は０に等しく、したがって、解がガロア体内に存在するためには、
0003830527.tif 000008
である。項の合計のトレースは、個々の項のトレースの合計に等しい。ＧＦ（２2m）においては、トレース(y2)=トレース(y)であり、これらの和はガロア体和法を用いると、ゼロである。したがって、方程式５はもしトレース（Ｃ）＝０ならばＧＦ（２2m）内に解を有する。
方程式５の一般解は、２ｍ−１個の「基底解」の線形結合である。基底解とは、ガロア体の「基底要素」Ｃ1，Ｃ2・・・Ｃ2m-1の１つをＣとする方程式３の解である。基底要素とは、線形結合させると体のすべての他の要素を生成することができる体の要素である。これらの要素は、たとえば、各々が２ｍ−１個の０と１つの１とを含む、すなわちαi=000・・・１からαj=100・・・00である２ｍ−１個の要素の組であってもよい。このような体においては、C=00110・・・0は基底要素00100・・・0と00010・・・0との線形結合である。方程式５の一般解は、合計すると
0003830527.tif 000009
を生成する基底要素に対応する基底解の線形結合である。
生成元多項式x4+x+1で定義されるＧＦ（２4）においては、ゼロのトレースを有する各要素αiはまたその最も重要なビットとしてゼロを有する。したがって、この体内の問題のＣは基底要素α0=0001、α1=0010およびα2=0100の結合である。対応する基底解は、
(α5)2＋α5=α0  ここでy0=α5
(α9)2＋α9=α1  ここでy0=α9
(α3)2＋α3=α2  ここでy0=α3
であり、もう１つの基底解の組は、
(α10)2＋α10=α0  ここでy1=α10
(α7)2＋α7=α1  ここでy1=α7
(α14)2＋α14=α2  ここでy1=α14
である。このガロア体内では、たとえば、Ｃがα8=0101に等しい方程式３の解は、Ｃを
C=α0＋α2=0001+0100
に分解し、基底解の対応する組を合計し、たとえば、
y0=α5＋α3=α11
として第１の解を生成し、第２の解を、
y1=y0+α0
と決定することによって決定される。次に、このシステムは二次エラーロケータ多項式の解を、
0003830527.tif 000010
として決定する。
Ｂ．３つのエラー位置の決定
３つのエラーに関連するエラーロケータ多項式の形は、
σ(x)=σ3x3+σ2x2+σ1x+σ0
［８］
である。解を求めるために、このシステムは、多項式をゼロに等しいとおく。
σ(x)=σ3x3+σ2x2+σ1x+σ0=0
［９］
そしてこの方程式の形を変換して、
y3+ay+b=0
とする。このために、システムは変数を変え、
0003830527.tif 000011
として、方程式９は、
0003830527.tif 000012
となる。次にシステムは方程式１０の項を展開して、
0003830527.tif 000013
とし、同類項をまとめて、
0003830527.tif 000014
を生成する。ＧＦ（２2m）においては、同一項の合計はゼロに等しいので、方程式は、
0003830527.tif 000015
となる。このシステムは方程式１２をσ3で除し、次の形の方程式を生成する。
y3+ay+b=0
[13]
ここで
0003830527.tif 000016
もしａ≠０ならば、システムは変数を変え、
0003830527.tif 000017
とし、方程式１３は、
0003830527.tif 000018
となる。次に方程式１５を展開し同類項をまとめて、
0003830527.tif 000019
を生成する。このシステムは次に方程式１６をｚ3で乗じて、
(z3)2+bz3+a=0,
[17]
を生成し、この式は、変数z3を有する二次方程式である。次に方程式１７はＡ節で説明した２つのエラー方法を用いて解くことができる。
一旦１つの解z03が決定されると、このシステムは以下に図２および図３を参照して説明される回路を用いて立方根z0を求める。ｍが偶数である限り、方程式１７の第２の解z1は、
0003830527.tif 000020
であり、ｍは偶数であるので２2m−１は３で割り切れるので、指数
0003830527.tif 000021
は常に整数である。方程式１７の第３の解は、
z2=z1+z0
である。このシステムは次にこれらの解をｙについて式に代入し、代入の結果を個々に
0003830527.tif 000022
に加えて、三次エラーロケータ多項式の解x0、x1およびx2を生成する。
もしａ＝０ならば、方程式１３の解はy=b1/3である。ｂの立方根を求めるために、このシステムは図２に示す回路を使用する。一旦立方根がわかれば、このシステムはy1およびy2を、
0003830527.tif 000023
と決定し、これらの値から解x0、x1およびx2を決定する。
次に図２および図３を参照すると、回路２００は、ＧＦ（２2m）の要素α3kの立方根を、この要素を
0003830527.tif 000024
に関連する累乗で乗することによって求める。いずれのＧＦ（２2m）の要素の２L乗も、複数の従来のガロア体乗算器を使用して容易に達成される。
回路２００は、恒等式x2-1=(x-1)*(x+1)を利用している。ｘが２mに等しいと、この恒等式は、２2m−１＝（２m−１）*（２m＋１）となる。因子２m−１または２m＋１の１つは３で割り切れるが、両方の因子が割り切れるわけではない。もしたとえば、ｍ＝４であれば、因子２m−１は３で割り切れ、２m＋１は割り切れない。回路２００はまた
0003830527.tif 000025
という事実も利用している。
回路２００を用いて、ガロア体要素α3kは、乗算器２０２内で、３で割り切れない恒等式の因子に対応する累乗に乗される（ステップ３００）。ｍ＝４の例では、要素は、２m＋１乗に乗される。そして、ルックアップテーブル２０４を用いて、積
0003830527.tif 000026
の立方根
0003830527.tif 000027
を求める（ステップ３０２）。可能な積
0003830527.tif 000028
の立方根についてしかエントリを持たないテーブルは、比較的小さい。ＧＦ（２8）の例では、テーブルは５つのエントリしか持たない。
乗算器２０２はまた、要素α3kを
0003830527.tif 000029
に対応する累乗で乗し（ステップ３０４）、その結果は、ルックアップテーブル２０４によって生成された立方根で、ＧＦ乗算器２０６内で乗される（ステップ３０６）。
0003830527.tif 000030
ステップ３０８において、このシステムは、この積を
0003830527.tif 000031
乗し、立方根αkを生成する。
図４は、ＧＦ（２8）、すなわちｍ＝４についての回路２００を示している。α3kを２m＋１乗するために、この回路は、ＧＦ乗算器２０１内で、まず要素を２mまたは２4＝１６乗する。次に、ＧＦ乗算器２０３内で、積α3k(16)=α48kを要素α3kで乗して、積
0003830527.tif 000032
を生成する。この積は、５つの要素のルックアップテーブル２０４に入るために使用される。
α0→α0
α51→α17
α102→α34
α153→α51
α204→α68
これによってα17kが生成される。
ＧＦ乗算器２０７および２０９を用いて、要素α3kは
0003830527.tif 000033
乗される。ＧＦ乗算器２０７はまず要素を２2または４乗し、ＧＦ乗算器２０９は積α3k(4)=α12kを要素α3kで乗し、積α15kを生成する。
ＧＦ乗算器２０６は次に２つの積を乗するα17k*α15k=α32k。この結果は次に乗算器２１０内で
0003830527.tif 000034
乗され、立方根、αkを生成する。
回路２００は、そこに与えられたすべての要素に対して結果を生成する。しかしながら、ガロア体のすべての要素に対する立方根が必ずしもあるわけではない。したがって、このシステムは結果をテストして（ステップ３１０）、その結果が実際の立方根であるかどうかを判断せねばならない。したがってこのシステムは、結果をそれ自身で２回乗し、その積が回路に与えられた要素と等しいかどうかを判断する（ステップ３１２）。もし等しければ、立方根は正確であり、エラー位置が決定できる（ステップ３１４）。しかしながらもし積が要素に等しくなければ、システムはエラー位置が見つからないと判断する（ステップ３１６）。そしてシステムはエラー位置を探す処理を終了する。
Ｃ．４つのエラー位置の決定
４つのエラーに関連するエラーロケータ多項式の形は、
σ(x)=σ4x4+σ3x3+σ2x2+σ1x+σ0
[18]
である。解を求めるため、システムはこの多項式をゼロに等しいとおく。
σ(x)=σ4x4+σ3x3+σ2x2+σ1x+σ0=0
[19]
そしてこの方程式の形を変換し、
y4+dy2+ey+h=0
とする。特定的には、ここで図５を参照すると、システムはステップ５００において変数を変える。
0003830527.tif 000035
そして方程式１９は
γ(y)=σ4(y+r)4+σ3(y+r)3+σ2(y+r)2+σ1(y+r)+σ0=0
[20]
となる。ステップ５０２においてこのシステムは項を展開して、
γ(y)=σ4(y4+r4)+σ3(y3+y2r+yr2+r3)+σ2(y2+r2)+σ1(y+r)+σ0=0
とし、同類項をまとめて、
γ(y)=σ4y4+σ3y3+(σ3r+σ2)y2+(σ3r2+σ1)y+σ4r4+σ3r3+σ2r2+σ1r+σ0=0
[21]
を生成する。次に、ステップ５０４において、このシステムはｒに対して
0003830527.tif 000036
を代入し、ここで
0003830527.tif 000037
であるので、線形項の係数はゼロである。したがって方程式２１は、
0003830527.tif 000038
となり、ここで「ｓ」は方程式２１の定数項である。
この方程式を直接解くのではなくこのシステムはステップ５０６において、
0003830527.tif 000039
の解を求める。
したがって、このシステムは、
0003830527.tif 000040
または、
θθ(y)=y4+θ2y2+θ1y+θ0=0
[25]
ここで
0003830527.tif 000041
を解く。ステップ５０８においてこのシステムはまず方程式２５を因数分解して、
θ(y)=(y2+t*y+u)*(y2+v*y+w)=0
[26]
とする。ここで方程式２５は因数分解できるものと仮定しているが、これはエラーロケータ多項式の解がＧＦ（２2m）内に存在するとするならば妥当な仮定である。
このシステムは方程式２６の項を展開して、
θ(y)=y4+(t+v)y3+(t*v+u+w)y2+(t*w+v*u)y+u*w=0
[27]
とし、この方程式の係数を方程式２５の係数に等しいものとおく（ステップ５１０）。
t+v=0
t*v+u+w=θ2
t*w+v*u=θ1
u*w=θ0
したがって、
t=v
t2+(u+w)=θ2
t*(w+u)=θ1
u*w=θ0
ステップ５１２において、このシステムは次に唯一の未知数「ｔ」を持つ方程式を決定する。θ2、θ1およびθ0はエラーロケータ多項式の係数の組合せであるので、既知であることを思い出されたい。したがって、このシステムは
0003830527.tif 000042
とおき、これをθ2についての式に代入し、かつｔで乗することによって、方程式
t3+θ2t+θ1=0
[28]
を生成する。
この結果は、上のＢ節で説明した演算を用いて解くことができる三次多項式である（ステップ５１４）。特定的には、このシステムは変数を変え、
0003830527.tif 000043
そして方程式２８は、
0003830527.tif 000044
となる。項を展開しかつまとめて、
0003830527.tif 000045
かつｚ3で乗することによって、このシステムは、変数ｚ3を持つ二次方程式である方程式(z3)2+θ1z3+a3=0を生成する。
Ａ節の方法を用いて、このシステムは方程式２９の解を求める。
このシステムはこうして変数を変え、
z3=θ1g
[30]
とし、そして二次方程式は、
θ12g2+θ12g+a3=0
[31]
または
0003830527.tif 000046
となる。もしトレース
0003830527.tif 000047
ならば、方程式３１の解はＧＦ（２2m）内に存在する。解が存在すると仮定すると、これらは、
0003830527.tif 000048
を基底要素の線形結合に分解し、基底要素を対応する基底解と関連付けることによって、決定される。
一旦解が決定されると、システムはそれらのうち１つをたとえばｇ0をｚ3について式３０に代入し、図２の回路を用いてｚ3の立方根ｚ0を決定する。このシステムは次に式
0003830527.tif 000049
のｚにｚ0を代入して、これからｔ0を決定する。
ｗおよびｕを決定するために、このシステムはステップ５１６において、値ｔ0および式
t2+(u+w)=θ2および
u*w=θ0
を用いて、解としてｕおよびｗを有する二次方程式３３を生成する。
(p+u)*(p+w)=
p2+(u+w)*p+(u*w)=
p2+(θ2+t02)*p+θ0=0,
[33]
このシステムは次に、Ａ節の方法を用いて方程式３３の解を決定する。次にステップ５１８においてこれらの解ｐ0およびｐ1を方程式２６の因数に代入して、二次方程式を生成する。
y2+t0*y+p0=0
および
[34]
y2+t0*y+p1=0,
そして、ステップ５２０においてＡ節の方法を用いて解ｙ0、ｙ1およびｙ2、ｙ3について解く。方程式３３の解ｙ0、ｙ1、ｙ2およびｙ3はθ(y)の解であり、１／ｙ0、１／ｙ1、１／ｙ2および１／ｙ3はγ(y)の解である。次にこのシステムはステップ５２２において１／ｙ0、・・・１／ｙ3を式ｘ＝ｙ＋ｒに代入し、四次エラーロケータ多項式の解を決定する。最後に、このシステムはステップ５２４において、エラーロケータ多項式の解をコードワード内の位置と関連付ける。
この四次エラーロケータ多項式の解を決定する直接的方法は、チェンサーチを行なったりまたはｍ×ｍのマトリックスを操作したりするよりも迅速である。さらに、この方法においては、他の先行する既知のシステムにおいて使用される大きなルックアップテーブルが必要ない。
【図１】
0003830527.tif 000126
【図２】
0003830527.tif 000127
【図３】
0003830527.tif 000128
【図４】
0003830527.tif 000129
【図５】
0003830527.tif 000130
0003830527.tif 000131