(57)【特許請求の範囲】
【請求項１】
ガロア体（ｐw+i）上の、距離ｄの変形リードソロモンエラー検出符号（ＥＤＣ）を用いて、データシンボルを符号語に符号化して、ＧＦ（ｐw）におけるＥＤＣ符号語を生成するための方法であって、前記方法は、
Ａ．ｗビットシンボルにｉ＋１個のビットを追加し、前記シンボルを符号化して、ｄ−１個の（ｗ＋ｉ＋１）ビットＥＤＣ冗長シンボルを生成するステップを含み、前記ＥＤＣ冗長シンボルは各々、ｈ（ｘ）モジュロｐ（ｘ）の累乗であり、ｈ（ｘ）は前記体の原始元であり、ｐ（ｘ）は、ｐ（ｘ）=ｘw+i+ｘw+i-1+...+ｘ2+ｘ+１の形式の既約多項式であり、前記方法はさらに、
Ｂ．前記ＥＤＣ冗長シンボルと予め定められた定数項とを含む予備ＥＤＣ符号語を生成するステップと、
Ｃ．前記予備ＥＤＣ符号語のシンボルの各々にある選択されたｉ個のビットのいずれかが、対応するｉ＋１番目のビットと同じ値に設定されていないかを確認し、前記選択されたｉ個のビットのうちのいずれかが前記対応するｉ＋１番目のビットと同じ値に設定されていない場合に、前記予備ＥＤＣ符号語と、前記シンボルの各々にあるｉ＋１個のビットのうちの選択されたビットが１に設定されかつ前記シンボルの各々にあるｉ＋１個のビットのうちの残りのビットが０に設定された、１つ以上の変形符号語の組合わせであるＥＤＣ変更子符号語とを組合せることにより、変形ＥＤＣ符号語を形成して、ｉ個のビットが、対応するｉ＋１番目のビットと同じ値を有する符号語シンボルを生成するステップと、
Ｄ．ｉ＋１個のビットがすべて１に設定されたシンボルの補数をとるステップと、
Ｅ．ｉ＋１個のビットを前記符号語シンボルから切り捨てて、ｗビットシンボルを有するＥＤＣ符号語を生成するステップとを含む、方法。
【請求項２】
前記ステップＣがさらに、
ａ．各ＥＤＣシンボル中の選択されたｉ個のビットの各々であって、対応するｉ＋１番目のビットと同じ値に設定されていないビットの場所に応じて、前記各ＥＤＣシンボルに対して１つまたはそれ以上の変形符号語を選択するステップと、
ｂ．前記変形符号語を組合せて、前記ＥＤＣ変更子符号語を生成するステップとを含む、請求項１に記載の方法。
【請求項３】
前記ステップＣがさらに、
ａ．各ＥＤＣシンボル中の選択されたｉ個のビットの各々であって、対応するｉ＋１番目のビットと同じ値に設定されていないビットの場所に応じて、前記各ＥＤＣシンボルに対して１つまたはそれ以上の変形符号語に対応するＲ個の情報シンボルを選択するステップと、
ｂ．前記選択されたＲ個の情報シンボルを組合せるステップと、
ｃ．前記組合せを符号化して、（ｄ−１）個のＥＤＣ冗長シンボルと、すべて０に設定されるｉ＋１ビットを有するＲ個の擬似冗長シンボルとを含む前記ＥＤＣ変更子符号語を生成するステップとを含み、ただし、Ｒは、［（ｉ×ｄｅｇ（ｇ（ｘ）））／ｗ］であり、ｄｅｇ（ｇ（ｘ））は、ジェネレータ多項式ｇ（ｘ）の次数であり、［  ］は天井関数を表わし、請求項１に記載の方法。
【請求項４】
ＧＦ（ｐw+i）上の変形リードソロモン符号を用いてデータシンボルを符号化して、ＧＦ（ｐw）におけるシンボルを有する符号語を生成するための方法であって、前記方法は、
Ａ．ｗ＋ｉ＋１個の項を備えた既約多項式ｐ（ｘ）を有し体のシンボルが多項式ｈ（ｘ）モジュロｐ（ｘ）によって決まるガロア体上の、距離ｄの符号を選択するステップを含み、ｈ（ｘ）は前記体の原始元であり、前記方法はさらに、
Ｂ．ＧＦ（ｐw+i）の各シンボルを、重みの低い（ｗ＋ｉ＋１）ビットシンボルとして表現するステップと、
Ｃ．ジェネレータ多項式ｇ（ｘ）=（ｘ+αL）*（ｘ+αL+1）*...（ｘ+αL+n-k-1）を用いて前記（ｗ＋ｉ＋１）ビットシンボルを符号化して、（ｗ＋ｉ＋１）ビットＥＤＣシンボルを生成するステップと、
Ｄ．前記ＥＤＣ冗長シンボルと予め定められた定数項とを含む予備ＥＤＣ符号語を生成し、前記予備ＥＤＣ符号語のシンボルの各々にある選択されたｉ個のビットのいずれが、対応するｉ＋１番目のビットと同じ値に設定されていないかを確認し、同じ値に設定されていない場合に、前記予備ＥＤＣ符号語と、前記シンボルの各々にあるｉ＋１個のビットのうちの選択されたビットが１に設定されかつ前記シンボルの各々にあるｉ＋１個のビットのうちの残りのビットが０に設定された、１つ以上の変形符号語の組合わせであるＥＤＣ変更子符号語とを組合せることにより、変形ＥＤＣ符号語を形成して、ｉ個のビットが、対応するｉ＋１番目のビットと同じ値を有する符号語シンボルを生成するステップと、
Ｅ．選択されたｉ＋１個のビットを前記符号語シンボルから切り捨てて、ｗビットシンボルを有するＥＤＣ符号語を生成するステップとを含む、方法。
【請求項５】
前記符号を選択するステップが、既約多項式ｐ（ｘ）=ｘw+i+ｘw+i-1+...+ｘ1+ｘ0に関連するガロア体上の符号を選択するステップをさらに含む、請求項４に記載の方法。
【請求項６】
前記符号化するステップが、ＧＦ（２2+i）のシンボルの（ｗ＋ｉ＋１）ビット表現を用い、前記符号化は重みの低い（ｗ＋ｉ＋１）ビット表現を用いる、請求項４に記載の方法。
【請求項７】
ＧＦ（２w+i）上の距離ｄの符号に従ってｗビットシンボルを符号化して、（ｗ＋ｉ＋１）ビット冗長シンボルを生成するための符号器であって、前記符号器は、
Ａ．前記ｗビットのシンボルに（ｉ＋１）ビットの０を付加して、前記前記ＧＦ（２w+i）のシンボルの（ｗ＋ｉ＋１）ビット表現を生成するためのレジスタと、
Ｂ．前記ＧＦ（２w+i）のシンボルの（ｗ＋ｉ＋１）ビット表現と、ジェネレータ多項式の係数の（ｗ＋ｉ＋１）ビット表現とを、前記シンボルの（ｗ＋ｉ＋１）ビット表現を循環的にシフトさせたものを組合せることによって、各々が乗算する、ｄ−１個の乗算器と、
Ｃ．ｄ−２個の加算器とを含み、前記加算器は、前記乗算器が生成した（ｗ＋ｉ＋１）ビットの積を、前記シンボルの（ｗ＋ｉ＋１）ビット表現に、または前記加算器が生成した以前の和に加算し、前記加算器は、ｗビットシンボルすべてが符号化されたときに前記（ｗ＋ｉ＋１）ビット冗長シンボルを生成する、符号器。
【請求項８】
ＧＦ（ｐw+i）上の変形リードソロモン符号を用いてｗビットデータシンボルを符号化することにより生成されたＧＦ（ｐw）におけるシンボルを有する符号語のエラーを検出するための方法であって、前記方法は、
Ａ．ｗビット符号語シンボルを、ｐ（ｘ）=ｘw+i+ｘw+i-1...+ｘ1+ｘ0でありかつｈ（ｘ）が原始元を表わす多項式ｈ（ｘ）モジュロｐ（ｘ）によって決まる（ｗ＋ｉ＋１）ビットシンボルによって、表現するステップと、
Ｂ．ジェネレータ多項式ｇ（ｘ）=（ｘ+αL）*（ｘ+αL+1）*...（ｘ+αL+d-1）を用いて、前記（ｗ＋ｉ＋１）ビット符号語シンボルを符号化して、シンドロームＳL，ＳL+1'...，ＳL+d-1を生成するステップと、
Ｄ．前記シンドロームが０またはｐ（ｘ）に等しいかどうか判断し、そうであれば、前記符号語にはエラーがないと判断し、エラーのないデータシンボルを与えるステップと、
Ｅ．前記シンドロームが０またはｐ（ｘ）に等しくなければ、前記符号語にはエラーがあると判断し、データにはエラーがあることを示す信号をアサートするステップとを含む、方法。
【請求項９】
前記ＧＦ（２w+i）のシンボルの（ｗ＋ｉ＋１）ビット表現は、重みの低い（ｗ＋ｉ＋１）ビット表現である、請求項８に記載の方法。
【請求項１０】
前記方法は、
Ｆ．前記シンドロームに関連したエラー場所およびエラー値を用いて、訂正された符号語に関連する再構成されたシンドロームｓ′L，ｓ′L+1，...，ｓ′L+d-1を決定するステップと、
Ｇ．前記前記シンドロームを前記再構成されたシンドロームと組合せるステップと、
Ｈ．前記組合せが０またはｐ（ｘ）に等しければ、前記再構成されたシンドロームに関連するエラーのないデータを生成するステップと、
Ｊ．前記組合せが０またはｐ（ｘ）に等しくなければ、データは訂正不能であることを示す信号をアサートするステップとをさらに含む、請求項８に記載の方法。
【請求項１１】
前記再構成されたシンドロームを決定するステップは、
ａ．ｉ個のエラー場所および関連するエラー値の各々に対して、部分的な再構成されたシンドロームｓ′L,iを決定するステップと、
ｂ．エラー場所ｅｌｏｃiに基づく
0003989558.tif 000022
の累乗によって、前記部分的な再構成されたシンドロームｓ′L,iを乗算することにより、再構成されたシンドロームｓ′L+1,i，...ｓ′L+d-1,iを決定するステップと、
ｃ．最終的な再構成されたシンドロームをs″L=s′L,0+s′L,1+...+s′L,z-1として生成するステップとをさらに含み、ｚはエラーの数である、請求項１０に記載の方法。
【請求項１２】
前記シンドロームを決定するステップは、
ｃ．２（w+i）/2要素のルックアップテーブルを用いて、ｕｐｐｅｒiおよび
ｌｏｗｅｒiがそれぞれｅｌｏｃiの（ｗ＋ｉ）／２最上位および最下位ビットである、
0003989558.tif 000023
を決定するステップと、
ｄ．
0003989558.tif 000024
として決定するステップと、
ｅ．前記部分的な再構成されたシンドローム
0003989558.tif 000025
を決定するステップとをさらに含む、請求項１１に記載の方法。
【請求項１３】
ジェネレータ多項式ｇ（ｘ）=（ｘ+αL）*（ｘ+αL+1）*...（ｘ+αL+d-1）および既約多項式ｐ（ｘ）を有するガロア体ＧＦ（ｐw+i）上のｗビットシンボルを備えるデータ符号語を復号するための復号システムであって、前記復号システムは、
Ａ．前記符号語のシンボルの（ｗ＋ｉ＋１）ビット表現を用いて、エラー場所ｅｌｏｃiおよびエラー値ｅｖａｌiを決定するための手段と、
Ｂ．前記エラー場所およびエラー値に基づいてシンドロームＳLを決定し、エラーを前記シンドロームに従って訂正して、訂正されたデータ符号語を生成するための手段と、
Ｃ．前記訂正された符号語にはエラーがないかどうか判断するための手段とを含み、前記エラーがないかどうか判断するための手段は、
ａ．部分的な再構成されたシンドローム
0003989558.tif 000026
を生成するための手段と、
ｂ．再構成されたシンドロームs′L+1,i,s′L+2,i,...s′L+d-1,iを、
0003989558.tif 000027
として生成するための手段と、
ｃ．最終的な再構成されたシンドロームを、
s″L=s′L,0+s′L,1+s′L,2+...+s′L,z,...,s″L+d-1=s′L+d-1,0s′L+d-1,1+s′L+d-1,2+...+s′L+d-1,z
として生成するための手段とを含み、ｚは前記システムによって決まるエラーの数であり、さらに、
ｄ．対応するシンドロームと最終的な再構成されたシンドロームとを組合せ、この組合せがすべて０またはｐ（ｘ）であれば訂正されたデータ符号語にはエラーがないと判断するための手段を含み、前記システムは、
Ｄ．訂正されたデータ符号語にエラーがなければ、訂正されたデータ符号語のエラーのないデータシンボルを与えるための手段と、
Ｅ．訂正されたデータ符号語にエラーがあれば、エラー信号を与えるための手段とをさらに含む、復号システム。
【請求項１４】
前記再構成されたシンドロームを生成するための手段は、
0003989558.tif 000028
を、
0003989558.tif 000029
として生成し、ｕｐｐｅｒiおよびｌｏｗｅｒiはそれぞれ、ｅｌｏｃiの（ｗ＋ｉ）／２最上位および最下位ビットである、請求項１３に記載の復号システム。
【請求項１５】
前記再構成されたシンドロームを生成するための手段は、
0003989558.tif 000030
を含む２（2+i）/2エントリのルックアップテーブルを含む、請求項１４に記載の復号システム。
【請求項１６】
前記再構成されたシンドロームを生成するための手段は、
0003989558.tif 000031
を、
0003989558.tif 000032
の置換として生成する、請求項１５に記載の復号システム。
【請求項１７】
前記再構成されたシンドロームを生成するための手段は、
0003989558.tif 000033
を含む第２の２（w+i）/2エントリのルックアップテーブルを含む、請求項１５に記載の復号システム。
【発明の詳細な説明】
発明の分野
本発明は変形リードソロモンエラー訂正符号器に関する。
発明の背景
デジタルコンピュータシステムにおいては大容量記憶媒体、具体的にはディスクに記録されるデータの密度が増大するのに従って、データのエラー訂正符号化の重要性が大幅に増している。記録密度が高くなると、ディスクの記録表面のわずかな欠陥も大量のデータを破壊する可能性が生じる。データの損失を避けるために、その名のとおりエラー訂正符号（ＥＣＣ）を用いて誤りのあるデータを訂正する。
データシンボルのストリングは、ディスクに書込まれる前に、数学的に符号化されてＥＣＣシンボルを形成する。次にこのＥＣＣシンボルはデータストリングに付加されて符号語、すなわちデータシンボルプラスＥＣＣシンボルを形成し、この符号語がディスクに書込まれるかまたはストアされる。データをディスクから読取るときには、読取るべきデータシンボルを含む符号語がディスクから検索されて数学的に復号化される。復号化中にデータ中のエラーが検出され、可能であればＥＣＣシンボルの操作によって訂正される。（復号化の詳細な説明については、ピーターソン（Peterson）およびウェルドン（Weldon）による、「エラー訂正符号（Error Correction Codes）」、第２版、ＭＩＴプレス（MIT Press）、１９７２年、を参照されたい。）
ストアされたデジタルデータは複数のエラーを含み得る。複数のエラーの訂正に使用される最も効果的なタイプのＥＣＣの１つは、リードソロモン符号である。（リードソロモン符号の詳細な説明については、ピーターソンおよびウェルドンによる、「エラー訂正符号」を参照されたい。）データシンボルのストリングにおける複数のエラーを訂正するために、リードソロモン符号は、「ＧＦ（Ｐq）」で表わされるガロア体として知られているシンボルの組の種々の数学的特性を効率的かつ効果的に利用する。「Ｐ」は素数であり「ｑ」は体の各要素またはシンボルにおける基数をＰとする桁数と考えることができる。通常デジタルコンピュータアプリケーションにおいては「Ｐ」は２の値を取り、したがって「ｑ」は各シンボルにおけるビットの数である。
リードソロモン符号に基づくＥＣＣが効果的に符号化および訂正、または「保護」することのできるシンボルの数は、選択されるガロア体、すなわちＰqシンボルのサイズ、および符号が訂正することのできるエラーの最大数により限定される。ＧＦ（Ｐq）に対する巡回リードソロモン符号語の最大長さはＰq−１シンボルである。したがって、ＥＣＣにより保護可能な、すなわち符号語に含まれるデータシンボルの最大数は、Ｐq−１シンボルマイナス「ｅ」であり、「ｅ」はＥＣＣシンボルの数である。ガロア体が大きいほど、符号語は長くなり、訂正すべきエラーの所与の最大数に対しＥＣＣが保護できるデータも多くなる。
より大きなガロア体を用いてデータシンボルのより大きなストリングを保護することが可能であるが、ガロア体を用いて８よりも大きく８の乗数でない多数のビットを有する符号語シンボルを得ることは、システムの回路を複雑にする。システムの残りの部分は８ビットシンボルまたはバイトすなわち８ビットの倍数であるシンボルで動作する。したがって、もしＥＣＣが８ビットよりも長いシンボルを用いるならば、システムは、システムの残りの部分が使用する８ビットシンボルとＥＣＣ回路が用いるより長いシンボルとの間でシンボルの変換を行なうインターフェイスを含んでいなければならない。
ＧＦ（２8）に基づくＥＣＣは、もし２つの８ビットＥＣＣシンボルをデータに付加して符号語を２５５すなわち２8−１バイト長にするのであれば、１つのエラーに対し２５３の８ビットデータシンボルまたは「データバイト」までのストリングを保護できる。ＥＣＣが２つ以上のエラーを訂正するのであれば、より多くのＥＣＣシンボル、すなわち訂正すべきさらなるエラー各々について２つを符号語において用いなければならない。このことは、所与の長さの符号語に対しより少ないデータバイトの保護が可能であることを意味している。
情報は磁気ディスクにおいて長さが５１２または５７６バイトであるセクタにストアされることが多い。したがって、ＧＦ（２8）に基づくＥＣＣを何回かインターリーブして、５１２または５７６バイトセクタ全体を保護しなければならない。効果的にインターリーブを行なうことによって、データシンボルのストリングをいくつかのより小さなセグメント、すなわち各々が２５５シンボル未満のセグメントに分割し、各セグメントを符号化されるべきデータシンボルのストリームとして扱う。インターリーブの利点は、インターリーブにより所与の符号を用いてより多数のデータシンボルを符号化することができ、かつインターリーブにより、異なる符号語における隣接するデータシンボルを符号化することによるエラーのバーストを効果的に分離することである。しかしながら、インターリーブを用いるシステムでは、エラー訂正が、データシンボルを変形することにより実際にエラーを導入してしまい、有効であるが正しくない符号語を生み出す可能性がある。この「訂正誤り」を防止するために、別のエラー検出符号またはクロスチェックを典型的には用いて、インターリーブされたエラー訂正符号を用いて行なった変形が確実に正しいデータシンボルを生み出すようにする。
先行技術によるシステムでは、ＧＦ（２8）に対する８ビットシンボルエラー検出符号（ＥＤＣ）またはＧＦ（２16）に対する１６ビットシンボルエラー検出符号を用いている。８ビットシンボル符号の実現は簡単であるが、最大距離がわずか２であり比較的弱い。その代わりに、より強い１６ビットシンボル符号は、１６ビットシンボルの操作が要求され実現するのが複雑である。
ＧＦ（２10）に基づくエラー検出符号は、十分な符号語長さ、すなわち符号語あたり２10−１すなわち１０２３シンボルを有し、セクタ全体を容易にクロスチェックする。しかしながら、ＧＦ（２10）符号において用いられる１０ビットシンボルの符号化および復号化には問題がある。
上記のように、コンピュータ伝送および記憶ハードウェアはバイトに対して、すなわち８ビットシンボルに対して、または長さが１６ビットシンボルといったように８ビットの倍数であるシンボルに対してセットアップされる。このように通常は１０ビットシンボルの操作のために準備されていない。したがって、ＧＦ（２10）ＥＤＣを用いるのであれば、情報を、最初に１０ビットシンボルとして符号化するために、次にバイトとして伝送または記憶するために、最後に１０ビットシンボルとして復号化するために、バイトと１０ビットシンボルとの間で変換しなければならない。符号器および復号器双方において、バイトと１０ビットシンボルとの間で変換しなければならないということは、ＥＤＣクロスチェックプロセスに別のステップの複雑性を加えてしまう。さらに、データは８ビットシンボルに基づく変調符号により変調されるため、ＥＤＣに対し１０ビットシンボルを用いるとより多くのエラーが生まれる可能性がある。なぜなら、変調符号シンボルは２つ以上のＥＤＣシンボルに復調され得るからである。このように、変調符号語シンボルの誤った復調により、２つの誤りのあるＥＤＣ符号語シンボルが生じる可能性がある。
１つの解決法は、ＧＦ（２10）において符号語を生成し、１０２３バイト（データ、ＥＣＣシンボル）までを保護し、それでもなお８ビットシンボルまたはバイトをＥＤＣシンボルとして使用することである。ＧＦ（２10）に対するＥＣＣを用いる先行技術のシステムでは、１つ以上の予め定められた擬似データバイトをデータバイトに加え、データバイトプラス擬似データバイトからなるストリングを符号化して所望の数の１０ビットＥＣＣシンボルを生成している。次に、１０ビットＥＣＣシンボルの各々において選択された２つのビットを、既知の２ビットパターンたとえば「００」と比較する。１０ビットＥＣＣシンボルの各々における選択された２ビットが２ビットパターンと同じであれば、ＥＣＣシンボルの選択されたビットは無視されまたは切捨てられ、ＥＣＣシンボル各々の残りの８ビットをデータバイトおよび付加された擬似データバイトと連結させて符号語を形成する。この符号語を後に復号化し、ガロア体加算および／または乗算のために必要な既知の２ビット切捨てパターンを付加することにより何らかのエラー訂正を行なうことができる。
ＥＣＣ１０ビットシンボルのいずれかにおけるいずれかの選択されたビットが切捨てパターンと同じでなければ、付加された擬似データバイトを変形して、データバイトプラス変形された擬似データバイトの符号化により、選択されたビットが切捨てパターンと同じになる１０ビットＥＣＣシンボルが生成されるようにする。次に、今では既知の切捨てパターンと同じである選択されたビットは無視され、ＥＣＣシンボル各々の残りの８ビットおよび変形された擬似データバイトは、データバイトとともに符号語としてストアされる。再び、変形された擬似データバイトおよびＥＣＣシンボルの残りの８ビットは復号化および符号語をバイトとして訂正することを可能にするのに必要なすべての情報を含む。
先行技術のシステムは、同一譲受人に譲渡される、「エラー訂正符号エンコーダ（Error Correction Code Encoder）」と題された米国特許第４，８５６，００３号において述べられている。本願発明者らは、複雑性のより低い回路を用いてＧＦ（２10）に対するジェネレータ多項式ｇ（ｘ）に従ってデータを操作し、ＧＦ（２8）において符号語冗長シンボルを生成する、エラー検出／訂正システムを考案した。このようなシステムを用いて、選択された体ＧＦ（２w+i）に対しデータを符号化し、ＧＦ（２w）において冗長シンボルを生成することも可能である。
発明の概要
改良されたリードソロモンエラー訂正システムは、選択された体ＧＦ（２w+i）に対するジェネレータ多項式ｇ（ｘ）に従いｗビットデータシンボルを符号化し、（ｗ＋ｉ＋１）ビットＥＤＣ冗長シンボルを生成する。符号器は、項ｘd-1、ｘd-2…ｘ1の係数としてのこれらのシンボルとともに予備ＥＤＣ符号語を形成し、予備ＥＤＣ符号語を１つ以上のＥＤＣ変形符号語の組合せと組合せることによりＥＤＣ冗長シンボルを変形する。この結果、すべて０またはすべて１に設定されるｉ＋１の選択されたビットを有する変形されたＥＤＣ冗長シンボル、および、変形されたＥＤＣシンボルに加えられる「Ｒ」（ｗ＋ｉ＋１）ビット擬似冗長シンボルが得られる。
この符号化システムは次に、すべて１に設定されるｉ＋１ビットを伴う変形されたＥＤＣシンボルの補数を取り、ｉ＋１ビットがすべて０に設定されるシンボルを生成する。システムは次に、すべてゼロのｉ＋１ビットを変形されたＥＤＣシンボルおよび擬似冗長シンボル各々から切捨て、ＧＦ（２w）の要素であるシンボルを有するＥＤＣ符号語を生成する。
復号器はＥＤＣ符号語を復号化するために、擬似冗長シンボルを含むＥＤＣ符号語全体を復号化して、適切なエラーシンドロームを生成する。復号器はＥＤＣ符号語を（ｗ＋ｉ）ビットシンボルとして復号化してもよく、またはＥＤＣ符号語を（ｗ＋ｉ＋１）ビットシンボルとして復号化し、以下でより詳細に説明するように、より複雑性の低い回路を用いて何らかのガロア体演算をおこなうようにしてもよい。
具体的には、あるガロア体、ＧＦ（２w+i）を、以下の既約多項式によって生成できる。
p（x）=xw+i+xw+i-1+...+x1+x0
次に体の要素を、ｈ（ｘ）モジュロｐ（ｘ）の累乗として表現することができ、この場合ｈ（ｘ）は、原始の体の元を表わす多項式である。エラー訂正システムは、ＧＦ（２w+i）の要素の（ｗ＋ｉ＋１）ビット表現を用いて、乗算および要素の２i乗などのガロア体演算を行なう回路を簡素化する。このシステムは（Ｗ＋ｉ＋１）ビット表現を用いてこれらの体演算を、以下でより詳細に説明するように循環シフトおよび置換の組合せとして行なう。
【図面の簡単な説明】
本発明の上記およびさらなる利点については、添付の図面と関連付けて以下の説明を参照することにより理解がより深まるであろう。
図１は、本発明に従い構成される符号化システムの機能ブロック図である。
図２は、図１の符号器の演算のフローチャートである。
図３は、本発明に従い構成される復号化システムの機能ブロック図である。
図４は、図３の復号器の演算のフローチャートである。
図５は、図３に示されたシンドロームプロセッサの一部の機能ブロック図である。
実施例の詳細な説明
１．体演算
選択されたｗ＋ｉに対し、ガロア体ＧＦ（２w+i）を以下の既約多項式により生成できる。
p（x）=xw+i+xw+i-1+...+x2+x+1
「離散数学（Discrete Mathematics）」、１０６／１０７（１９９２）第４９７-５０２頁において発表された、Ｊ．Ｋ．ウォルフ（J.K. Wolf）による、「ｍのある値に対しＧＦ（２m）において乗算を行なうための効率的な回路（Efficient Circuits For Multiplying in GF（2） For Certain Values of m）」と題された文献を本明細書に引用により援用するが、この文献ではこうした体について述べられている。ｍ＝ｗ＋ｉの初めのいくつかの値は、２、４、１０、１２、１８、２８、３６、５２、５８、６０…である。
しかしながら「ｘ」は原始元ではない。したがってこうした体の各々につき、非ゼロの体の要素すべてをｈ（ｘ）モジュロｐ（ｘ）の累乗として表現できるように、多項式ｈ（ｘ）を定めている。多項式ｈ（ｘ）はこうして、体の原始元を表現する。
例として、ｗ＋ｉ＝１０に対し、ＧＦ（２w+i）すなわちＧＦ（２10）は、以下の既約多項式
p（x）=x10+x9+x8+x7+x6+x5+x4+x3+x2+x1+1
および以下の多項式
h（x）=x3+x+1
を有する。ＧＦ（２10）の各要素はこのようにして、（ｘ3＋ｘ＋１）モジュロｐ（ｘ）の累乗として表現できる。
ガロア体ＧＦ（２m）の各要素を、次数ｍ−１の多項式によりすなわちｍビットシンボルにより表現し得る。上記においてｍ＝ｗ＋ｉであり、ｍはウォルフの文献において述べられた値の１つである。この要素はこのようにして唯一のシンボルａ（ｘ）と関連付けられる。ＧＦ（２m）の要素をその代わりに次数ｍの多項式によりすなわち（ｍ＋１）ビットシンボルにより表現するときには、この要素は２つの異なっているが関連するシンボルｂ（ｘ）およびｃ（ｘ）と関連付けられ、以下のとおりとなる。
b（x）+c（x）=p（x）
このようにｂ（ｘ）およびｃ（ｘ）は補数である。
ｍ＝１０に対し、ＧＦ（２10）の１０ビット要素、およびｈ（ｘ）モジュロｐ（ｘ）により生成される要素の１１ビット表現を以下に示す。
0003989558.tif 000002
0003989558.tif 000003
図１および３を参照して以下で説明する符号化および復号化システムは、好ましくは、下記の利点を有する１１ビットシンボル表現を用いる。
第１に、１１ビットシンボルを２i乗することは、シンボルのビットの置換である。シンボルｂ（ｘ）に対し、
b（x）=b10x10+b9x9+...+b1x+b0
であり、係数またはビットにより表現すると、
b（x）=b10b9b8b7b6b5b4b3b2b1b0
となり、ｂ（ｘ）を２iのさまざまな累乗を行なうとそれぞれ以下のとおりとなる。
（b（x））2=b5b10b4b9b3b8b2b7b1b6b0
（b（x））4=b8b5b2b10b7b4b1b9b6b3b0
（b（x））8=b4b8b1b5b9b2b6b10b3b7b0
上記において
0003989558.tif 000004
のｘkの係数は、
0003989558.tif 000005
の係数である。
第２に、２つの１１ビットシンボルの乗算は、シンボルの一方の循環的にシフトされたコピーと他方のシンボルの係数またはビットとの排他的ＯＲを取ることによって行なうことができる。２つのシンボルｂ（ｘ）およびｄ（ｘ）に対し、以下のように表わされる。
b（x）=b10b9b8b7b6b5b4b3b2b1b0
d（x）=d10d9d8d7d6d5d4d3d2d1d0
d（x）*d（x）=
b0*（d10d9d8d7d6d5d4d3d2d1d0）
+b1*（d9d8d7d6d5d4d3d2d1d0d10）
+b2*（d8d7d6d5d4d3d2d1d0d10d9）
+b3*（d7d6d5d4d3d2d1d0d10d9d8）
+b4*（d6d5d4d3d2d1d0d10d9d8d7）
+b5*（d5d4d3d2d1d0d10d9d8d7d6）
+b6*（d4d3d2d1d0d10d9d8d7d6d5）
+b7*（d3d2d1d0d10d9d8d7d6d5d4）
+b8*（d2d1d0d10d9d8d7d6d5d4d3）
+b9*（d1d0d10d9d8d7d6d5d4d3d2）
+b10*（d0d10d9d8d7d6d5d4d3d2d1）
式中、「＊」は、ＧＦ（２）に対する乗算を表わす。上記各行のｄ（ｘ）の成分は各々の循環的にシフトされたコピーである。シンボルｂ（ｘ）およびｄ（ｘ）を交換して同じ結果を得ることができる。
第３に、定数乗算器は、重みのより低い１１ビット表現を使用するときには、最小数の排他的ＯＲゲートで容易に実現される。たとえば、０００１０００１００としても表現される１１ビット定数１１１０１１１０１１により、
b（x）=b10b9b8b7b6b5b4b3b2b1b0
を乗算することは、重みのより低い表現を用い、ｂ（ｘ）を２ビットずつ循環的にシフトし加算するすなわち排他的ＯＲを取り、結果を６ビットずつ循環的にシフトされたｂ（ｘ）の結果に加えることによって得ることができる。
b10b9b8b7b6b5b4b3b2b1*0001000100=
1*（b8b7b6b5b4b3b2b110b9）+1*（b4b3b2b1b10b9b8b7b6b5）
１１ビット表現のより重みの低いものをすべての乗算に対して用いるのであれば、加算しなければならないシンボルの循環的にシフトされたコピーの最大数は５である。対照的に、２つの１０ビットシンボルの乗算には、シンボルの１つの１０の変形コピーまで加算する必要がある。さらに、１０ビットコピーへの変形は一般的に循環シフトよりも複雑である。
２．符号化システム
図１を参照して、符号化システム１０は、ＧＦ（２w+i）に対する距離ｄのジェネレータ多項式ｇ（ｘ）に従いデータを符号化し、（ｗ＋ｉ＋１）ビット冗長シンボルを生成するリードソロモン符号器１２を含む。この例ではｗ＝８、ｉ＝２およびｄ＝４であり、ＧＦ（２10）に対するジェネレータ多項式は以下のとおりである。
g（x）=（x+α64）*（x+α65）*（x+α66）=x3+α300x2+α365x+α195
図２を参照して、すべてがＧＦ（２w）すなわちＧＦ（２8）の要素でありかつ全体としてデータシンボルと呼ばれるデータおよびＥＣＣシンボルが符号化される前に、ｉ＋１のゼロがレジスタ１３のシンボルに付加または含められる（ステップ２００）。この例では、３つのゼロが８ビットシンボルに付加されて１１ビットシンボルを形成する。スイッチ１４を閉位置にして、１１ビットデータシンボルは加算器２１においてレジスタ１８の内容に加算される。その和が次に乗算器１５、１６および１７において定数α300、α365、およびα195それぞれにより乗算される。これら定数はジェネレータ多項式の係数である。これら係数は最も重みの低い１１ビット表現形式であり、乗算器１５−１７は最小数の排他的ＯＲゲートを用いて実現される。
乗算器１５および１６からの積はモジュロ２で加算器２２および２３においてそれぞれレジスタ１９および２０の内容に加算される。これらの和は次にレジスタ１８および１９を更新する。同様に、乗算器１７により得られた積はレジスタ２０を更新する。
すべてのデータシンボルが符号器１２に与えられ１１ビットシンボルとして符号化された後、レジスタ１８−２０の内容はＥＤＣ冗長シンボルの１１ビット表現となる。スイッチ１４が次に開放され、１１ビットＥＤＣ冗長シンボルは、予備ＥＤＣ符号語のｘ3、ｘ2およびｘ項の係数としてそれぞれ符号器からレジスタ２４にシフトされる（ステップ２０２）。定数項ｘ0の係数はゼロに設定される。
符号化システムは次に、予備ＥＤＣ符号語が変形を必要とするかどうかを判断する（ステップ２０４、２０６）。各ＥＤＣ冗長シンボルについて、ＥＤＣシンボルプロセッサ２６は、先頭のｉ＋１ビットがすべて同じ値に設定されるかどうかを決定する。この例では、このシステムはプロセッサ２６において各ＥＤＣ冗長シンボルにおいてｘ9およびｘ8の位置にあるビットがｘ10の位置にあるビットと同じビット値に設定されるかどうかを決定する。システムはこのようにして１に設定される先頭ビットを有する特定のＥＤＣ冗長シンボルに対し、第２および第３の先頭ビットもまた１かどうかを決定する。そうでなければ、プロセッサ２６はレジスタ２４からの予備符号語およびプロセッサにより生成されるレジスタ２８におけるＥＤＣ変更子符号語を組合せることによりＥＤＣシンボルを変形する。
ＥＤＣ変更子符号語は本質的に、各々が、先頭のｘw+i-1からｘwビットのうち１に設定される異なる１つを有しかつこれらビットの残りの各々がゼロに設定される、１つ以上の変更符号語ｒcの組合せである。より具体的には、ｉ*（ｄ−１）の変更符号語があり、１つ１つが、ｄ−１のＥＤＣ冗長シンボルの各々におけるビット位置ｘw+i-1からｘwにあるビット各々に対するものである。この例では、６の変更符号語があり、３のＥＤＣシンボルの各々において１つがビット８および９をそれぞれ変形する。
所与のＥＤＣ冗長シンボルにおけるこれらビットのうち特定の１つが先頭ビットすなわちビット位置ｘw+iにあるビットと同じ値を有さないとき、符号器はＥＤＣ冗長シンボルを変形してその特定のビットを変える。そのために、符号器はＥＤＣ冗長シンボルを、以下の例でより詳細に説明するように、１に設定される対応するビットを有する変形符号語の適切なシンボルと組合せる。ｉ＋１ビットのもう１つのものが先頭ビットと同じ値に設定されない場合、ＥＤＣ冗長シンボルはさらに、また１に設定される特定ビットを有する変形符号語と組合せることにより変形される。
プロセッサ２６もまたＲの擬似冗長シンボルＰ1、Ｐ2…を生成する。すべてゼロに設定されるｉ＋１ビットを有する擬似冗長シンボルは、変形されたＥＤＣ冗長シンボルに付加されて、ＥＤＣ符号語が確実に適切に復号化されるようにする。必要な擬似冗長シンボルの数は以下のとおりである。
0003989558.tif 000006
式中ｄｅｇ（ｇ（ｘ））はジェネレータ多項式の次数であり、［  ］は天井関数を表わす。この例では、Ｒ＝１であり、ＥＤＣ擬似冗長シンボルはＥＤＣ符号語の定数項すなわちｘ0項の係数である。
ＥＤＣシンボルが変形されると、符号化システムは必要に応じて、ＥＤＣ冗長シンボルの最初のｉ＋１個の係数がすべて０であるかどうかを判断する（ステップ２０８）。そうであれば、システムはｉ＋１個のビットをシンボルから切り捨て、ｗビット変形ＥＤＣ冗長シンボルを生成する（ステップ２１２）。もしｉ＋１個のビットがすべて１であれば、システムはまずシンボルの補数をとり、これらのビットをすべて０にし、その後ビットを切り捨てて、対応するｗビット変形ＥＤＣシンボルを生成する（ステップ２１０，２１２）。システムはＥＤＣ冗長シンボルの各々に対してこれを行ない、ＧＦ（２w）の要素であるシンボルを有するＥＤＣ符号語を生成する。
例において、変形符号語は下記のとおりである。
0003989558.tif 000007
好ましくは、それらのｉ＋１個のビットがすべて０に設定された定数項を有するように選択された変形符号語ｒcが、変形リードソロモン符号選択および符号化システム（MODIFIED REED SOLOMON CODE SELECTI0N AND ENCODING SYSTEM）と題された同時係属中の米国特許出願連続番号第０８／７４９，２３５号において議論されているシステムおよび技術を用いて選択され、この出願は同一譲渡人に譲渡され、引用によって援用される。
ｘ1の係数のビット８を変形するために用いられる変形符号語ｒ0は、ビット８として１を、かつビット１０および９として０を含む対応するシンボルを有し、残りの符号語シンボルの各々においてはそれぞれのビット１０、９および８としてすべて０を有する。ｘ1の係数のビット９を変形するために用いられる変形符号語ｒ1は、ビット９として１を、かつビット１０および８として０を含む対応するシンボルを有し、残りの符号語シンボルの各々においはそれぞれのビット１０、９および８としてすべて０を有する。ｘ2の係数を変形するために用いられる変形符号語ｒ2およびｒ3ならびにｘ3の係数を変形するために用いられるｒ4およびｒ5についても同様に、対応するシンボルのビット８またはビット９が０に設定され、これらのシンボルの残りのｉ個のビットが０に設定され、残りのシンボルの各々においてそれぞれのｉ＋１個のビットのすべてが０に設定される。
変形符号語は変更子テーブル３０にストアされる。これに代えて、これらの符号語の各々の、０ではない１つの「情報」シンボルのみがテーブルにストアされてもよい。その後、システムは符号器１２において、ストアされたシンボルの各々を符号化し、符号語ｒcを再度生成する。したがって、テーブル３０は各符号語についてｘ3の係数を含み得る。
一例として、符号器１２は、データを符号化して、下記の予備ＥＤＣ符号語冗長シンボルを生成し、
ｃ3＝10101101011ｘ3
ｃ2＝01111101010ｘ2
ｃ1＝11111101111ｘ1
ｘ0の係数はすべて０に設定される。したがって、ＥＤＣ変形符号語は、ｘ3の係数のビット９を変形するためのｒ5ならびにｘ2の係数のビット９および８をそれぞれ変形するためのｒ2およびｒ3の組合せである。
したがって、変形符号語の、０ではない情報シンボルは、符号語ｒ5、ｒ3およびｒ4の、０ではない情報シンボルの組合せであり、
α953＋α177＋α126＝α293
これは符号器１２において符号化され、ＥＤＣ変形符号語を生成し、
α293ｘ3＋α593ｘ2＋α658ｘ1＋α488ｘ0
これを二進形式で表わすと下記のようになる。
1101100100ｘ3＋1100100000ｘ2＋00011110101ｘ＋0000111001
この符号語は、ＥＤＣ予備符号語の冗長シンボルと組合せられ、すなわち、ＥＤＣ変形符号語の係数が、ＥＤＣ予備符号語の冗長シンボルと組合せられて、ＥＤＣ符号語の冗長シンボルを形成する。
ｃ′3＝10101101011＋1011100100＝11110001111＝α108
ｃ′2＝01111101010＋01100100000＝00011001010＝α460
ｃ′1＝11111101111＋00011110101＝11100011010＝α164
ｃ′0＝00000000000＋00000111001＝00000111001＝α488
したがって、最後のＥＤＣ変形符号語は下記のとおりとなる。
α108ｘ3＋α460ｘ2＋α488ｘ0
次に、システムはサブプロセッサ３２において、ｉ＋１個のビットがすべて０に設定されたＥＤＣシンボルからｉ＋１個のビットを切り捨てる。これらのビットがすべて１に設定されたシンボルからｉ＋１個のビットを切り捨てる前に、例においてシステムはシンボルの補数をとり、ｉ＋１個のビットをすべて０に設定する。システムはまずｘ3およびｘ1の係数の補数をとり、次いでＥＤＣ符号語をシンボルの各々からｉ＋１個のビットを切り捨てて、ＧＦ（２8）のシンボルを有するＥＤＣ符号語を生成する。その後、８ビットＥＤＣ冗長シンボルが、８ビットデータおよびＥＣＣシンボルを有するセクタに記録される。
次に図３および図４を参照して、復号器３００は、ＥＤＣ符号語を用いてエラーシンドロームｓ64、ｓ65およびｓ66を決定することによりセクタシンボルをクロスチェックし、このＥＤＣ符号語はデータシンボルと、変形ＥＤＣシンボルと、擬似冗長シンボルとを含む（ステップ４００）。復号器３００は３つのレジスタ３０１、３０２および３０３を含み、これらは符号化の最後にエラーシンドロームを含み、復号器３００はさらに３つの乗算器３０４、３０５および３０６を含み、これらはそれぞれレジスタ３０１から３０３の内容を定数αkで乗算し、ここでｋ＝６４、６５または６６である。
セクタシンボルが復号器３００に与えられる前に、システムはｉ＋１個または３個の、すべて０のビットをレジスタ２９９のシンボルに加える。その後、１１ビットシンボルが加算器３１０、３１１および３１２の各々に与えられ、これらの加算器はさらに乗算器３０４から３０６からの積をそれぞれ受取る。シンボルとそれぞれの積とが組合せられ、結果がレジスタ３０１から３０３を更新するために用いられる。セクタシンボルのすべてが符号化されると、レジスタ３０１から３０３はシンドロームｓ64、ｓ65およびｓ66を含む。
シンドロームプロセッサ３０８は、ＥＤＣシンドロームｓ64，ｓ65およびｓ66すべてが０であるか、またはｐ（ｘ）であり、かつ、インターリーブされたＥＣＣによって公知の態様で生成されたＥＣＣシンドロームがすべて０であれば、セクタにはエラーがないとする（ステップ４０２）。
セクタにエラーがある場合、エラー訂正プロセッサ３１０はＥＣＣに従った公知の態様でエラーを訂正し、シンドロームプロセッサ３０８は、ＥＣＣによって決定したエラー場所ｅｌｏｃ、とエラー値ｅｖａｌiとに基づいてＥＤＣシンドロームｓ′kを再構成する（ステップ４０４）。まず、システムは、部分的に再構成されたＥＤＣシンドロームを決定する。
0003989558.tif 000008
ｋ＝６４、６５、６６、かつｉ＝０、１、２…ｚ−１の場合、ｚはエラーの数に等しい。ｋ＝６４の場合、これは２6であり、
0003989558.tif 000009
の置換である。
さらに図５を参照して、シンドロームプロセッサ３０８は２つのルックアップテーブル３１６および３１８と、乗算器３２０と、置換ハードウェア３２２とを用いて、１０ビット要素
0003989558.tif 000010
を２6によって累乗する。
0003989558.tif 000011
とする。
ただし、
0003989558.tif 000012
はｅｌｏｃiの５つの最上位ビットを含み、
0003989558.tif 000013
は１０ビットシンボルｅｌｏｃiの５つの最下位ビットを含む。したがって、
0003989558.tif 000014
0003989558.tif 000015
はいずれも３２、すなわち２5内に制限されるため、
0003989558.tif 000016
を生成するテーブル３１６には３２個のエントリしかない。したがって、テーブルはα0からα31に関するエントリを含み、好ましくは、これらのエレメントの、重みの低い１１ビット表現を含む。このため、３２エントリのテーブルが２10エントリのテーブルの代わりに用いられ、格納スペースを節約するだけでなく、関連テーブルアドレス回路構成の複雑性をかなり低減する。
したがって、
0003989558.tif 000017
の置換である。この置換はハードウェアにおいて行なわれるか、または、これもまた３２個のエントリしか有さない第２のルックアップテーブル３１８を用いて行なうことができる。この値が決定すると、それは乗算器３２０において
0003989558.tif 000018
によって乗算され、
0003989558.tif 000019
を生成する。さらに
0003989558.tif 000020
を２6で累乗することは、ハードウェアにおいて行なうことができる置換であり、これは図面において３２２で示される。
再構成された部分的なＥＤＣシンドロームｓ′64,iが決定すると、乗算器３２４から３２６、加算器３３０から３３３および置換ハードウェア３２８を用いて、関連した部分的なシンドロームｓ′65,iおよびｓ′66,iが下記のとおり容易に決定する。
0003989558.tif 000021
したがって、最終的に再構成されるＥＤＣシンドロームは、
s″k=s′k,0+s′k,1+...+s′k,z-1
であり、ｋ＝６４、６５および６６の場合、ｚはＥＣＣによって決定するエラーの数である。
訂正されたセクタにエラーがないかどうかを判断するために、ステップ４０６においてシンドロームプロセッサは、ＥＤＣシンドロームｓkと、最終的に再構成されたＥＤＣシンドロームｓ″kとを組合せ、この組合せがすべて０であるか、またはｐ（ｘ）のいずれかであるかを判断する。そうであれば、システムは訂正されたセクタにはエラーがないと判断する。そうでなければ、システムはセクタの訂正が失敗したと判断する（ステップ４０８）。
図１および図３の符号器および復号器は、ジェネレータ多項式として下記の式を有するＧＦ（２10）に対する別の符号を用いてもよい。
g（x）=x3+α422x2+α609x+α561
この符号について、ＥＤＣ変形符号語ｒcのｘ3項の係数である、ＥＤＣ変更子符号語テーブル３０のエントリは下記のとおりである。
r0 α821
r1 α462
r2 α21
r3 α723
r4 α783
r5 α736
上述の符号化および復号化システムは、ハードウェア、特に、乗算および２iによるシンボルの累乗のために必要なハードウェアを簡単にするために、１１ビットシンボルを用いる。さらに、復号器は小さなルックアップテーブルを用い、したがって、エラー場所および値に基づくシンドロームを決定するために、比較的簡単な関連アドレス回路構成を用いる。このため、クロスチェックシステムは全体的に比較的低価格であり、なおかつ訂正の誤りに対してデータセクタ全体を保護する。
【図１】
0003989558.tif 000034
【図２】
0003989558.tif 000035
【図３】
0003989558.tif 000036
【図４】
0003989558.tif 000037
【図５】
0003989558.tif 000038