(57)【特許請求の範囲】
【請求項１】
「ｊ」個のエラー訂正シンボルとｊ個のエラーシンドロームとを生成するための、生成多項式の根による、データシンボルの操作システムであって、前記システムは、
Ａ．並列動作し、データシンボルまたは伝搬フィードバック和を受取り、対応する更新値を生成するｊ個のセルと、
Ｂ．複数段のブロックフィードバック加算器とを含み、共通の段内のブロックフィードバック加算器は並列動作し、第１番目の段内のブロックフィードバック加算器は隣接するセルによって生成された更新値を合せて加算し、後続の段内のブロックフィードバック加算器は隣接するブロックフィードバック加算器によって生成された和を合せて加算し、最後の段内のブロックフィードバック加算器は少なくとも２つの中間和を生成し、前記システムはさらに、
Ｃ．第１のセルから最後のセルへと和を伝搬させるため、中間和を合せて加算する中間フィードバック加算器と、
Ｄ．所与のブロック内のセルによって生成された値に、前のブロックによって生成された和を加算するための複数の中間フィードバック加算器と、
Ｅ．セルに、中間フィードバック加算器によって生成された伝搬フィードバック和またはデータシンボルのいずれかを与えるためのスイッチとを含む、データシンボルの操作システム。
【請求項２】
隣接するセルの間のＡＮＤゲートをさらに含み、該ＡＮＤゲートは、エンコード演算中は前のセルから次のセルへと更新値を通し、シンドローム発生演算中はセル間を更新値が通ることを防止する、請求項１に記載のデータシンボルの操作システム。
【請求項３】
各セルは、
ａ．生成多項式の根と関連付けられるガロア体乗算器と、
ｂ．レジスタと、
ｃ．更新加算器とを含む、請求項２に記載のデータシンボルの操作システム。
【請求項４】
該更新加算器は、該レジスタの内容を次のデータシンボルに加算し、加算結果を該ガロア体乗算器に与え、
該ガロア体乗算器は、生成多項式の根によって該結果を乗算し、対応する更新値を生成して、更新値をレジスタおよび関連付けられるブロックフィードバック加算器に与える、
請求項３に記載のデータシンボルの操作システム。
【請求項５】
該更新加算器は、次のデータシンボルを該レジスタのための更新値に加算し、和をレジスタを更新するため与え、
該ガロア体乗算器は、生成多項式の根によって、更新されたレジスタの内容を乗算し、対応する次の更新値を生成して、更新値を該更新加算器および該関連付けられるブロックフィードバック加算器に与える、請求項３に記載のデータシンボルの操作システム。
【請求項６】
各セルはさらに、エンコード演算中は、ガロア体乗算器によって生成される積が更新値に含まれる第１の位置にあり、シンドローム発生演算中は、最後のデータシンボル以外のすべてのデータシンボルがセルに与えられるときは第１の位置にあり、最後のデータシンボルがセルに与えられるときはガロア体乗算器をバイパスする第２の位置にある、バイパススイッチを含む、請求項４に記載のデータシンボルの操作システム。
【請求項７】
「ｊ」個のエラー訂正シンボルを生成するため、データシンボルをエンコードするためのエラー訂正システムであって、前記システムは、
Ａ．データシンボルまたは伝搬フィードバック和を受取るため、および対応する更新値を生成するため、並列動作するｊ個のセルと、
Ｂ．複数段のブロックフィードバック加算器とを含み、共通の段内のブロックフィードバック加算器は並列動作し、第１番目の段内のブロックフィードバック加算器は隣接するセルによって生成された更新値を合せて加算し、後続の段内のブロックフィードバック加算器は隣接するブロックフィードバック加算器によって生成された和を合せて加算し、最後の段内のブロックフィードバック加算器は少なくとも２つの中間和を生成し、前記システムはさらに、
Ｃ．最後の段のブロックフィードバック加算器によって生成された中間和を合せて加算し、第１のセルから最後のセルへ和を伝搬する、中間フィードバック加算器と、
Ｄ．所与のブロック内のセルによって生成された値に前のブロックによって生成された和を加算するための複数の中間フィードバック加算器と、
Ｅ．エンコード演算中に前のセルから次のセルへと更新値を通すため、およびシンドローム発生演算中に更新値が通るのを防止するための複数のＡＮＤゲートと、
Ｆ．セルに、中間フィードバック加算器によって生成された伝搬フィードバック和またはデータシンボルのいずれかを与えるためのスイッチとを含む、データシンボルをエンコードするためのエラー訂正システム。
【請求項８】
ａ．セルによって計算されたシンドロームから変更されたエラーロケータ多項式を生成するためのデコード手段と、
ｂ．変更されたエラーロケータ多項式からエラー位置を決定するためのエラー位置特定手段とをさらに含む、請求項７に記載のデータシンボルをエンコードするためのエラー訂正システム。
【請求項９】
該デコード手段は、該変更されたエラーロケータ多項式を、
【数１】
0004368020.tif 000020
として生成する、請求項７に記載のデータシンボルをエンコードするためのエラー訂正システム。
【請求項１０】
エラー値を、
【数２】
0004368020.tif 000021
として決定するためのエラー値手段をさらに含む、請求項７に記載のデータシンボルをエンコードするためのエラー訂正システム。
【請求項１１】
エラー訂正方法であって、前記方法は、
Ａ．データシンボルを、並列動作するｊ個のセルに与えるステップと、
Ｂ．各セルにおいて、与えられたデータシンボルを生成多項式の根で乗算し、対応する更新値を生成するステップと、
Ｃ．並列動作して、隣接するセルによって生成された更新値を合せて加算し、関連付けられるブロックフィードバック和を生成するステップと、
Ｄ．並列動作して、ブロックフィードバック和を合せ、新しい関連付けられるブロックフィードバック和を生成するステップと、
Ｅ．所与のブロックについて、ブロック内のすべてのセルからの寄与を含む単一のフィードバック和が生成されるまで、ステップＤを繰返すステップと、
Ｆ．並列動作して、隣接するブロックからのフィードバック和を合せ、関連付けられる和を生成するステップと、
Ｇ．すべてのセルからの寄与を含む単一の伝搬和が生成されるまで、ステップＦを繰返すステップと、
Ｈ．伝搬和を並列に、セルに与え、関連付けられる更新値を生成するステップと、
Ｉ．ステップＨをｊ−１回繰返し、ｊ個のエラー訂正シンボルを生成するステップと、
Ｊ．ｊ個のエラー訂正シンボルをデータシンボルと連結させ、データコードワードを生成するステップとを含む、エラー訂正方法。
【請求項１２】
Ｋ．データコードワードからのデータシンボルをセルに与え、各セルにおいて関連付けられる更新値を生成するステップと、
Ｌ．各セルにおいて、データコードワードからの次のデータシンボルと更新値とを合せ、関連付けられる次の更新値を生成するステップと、
Ｍ．コードワード内の各データシンボルについてステップＬを繰返すステップと、
Ｎ．最後のデータシンボルに関連付けられる更新値を変更されたエラーシンドロームとして与えるステップと、
Ｏ．変更されたエラーシンドロームから、エラー値多項式および変更されたエラーロケータ多項式を決定するステップと、
Ｐ．変更されたエラーロケータ多項式から変更されたエラー位置を、そしてエラー値多項式からエラー値を決定するステップと、
Ｑ．変更されたエラー位置から実際のエラー位置を決定するステップと、
Ｒ．エラー位置およびエラー値を使用してデータコードワード内のエラーを訂正するステップとをさらに含む、請求項１１に記載のエラー訂正方法。
【請求項１３】
Ｋ．データコードワードからのデータシンボルをセルに与え、各セルにおいて関連付けられる更新値を生成するステップと、
Ｌ．各セルにおいて、データコードワードからの次のデータシンボルと更新値とを合せ、関連付けられる次の更新値を生成するステップと、
Ｍ．コードワード内の最後のデータシンボル以外のすべてのデータシンボルについてステップＬを繰返すステップと、
Ｎ．最後から２番目の更新値と最後のデータシンボルとを合せ、最後の更新値を生成するステップと、
Ｏ．最後の更新値をエラーシンドロームとして与えるステップと、
Ｐ．エラーシンドロームからエラーロケータ多項式およびエラー値多項式を決定するステップと、
Ｑ．エラーロケータ多項式およびエラー値多項式からエラー位置およびエラー値を決定するステップと、
Ｒ．エラー位置およびエラー値を使用してデータコードワード内のエラーを訂正するステップとをさらに含む、請求項１１に記載のエラー訂正方法。
【請求項１４】
変更されたエラーロケータ多項式を決定するステップは、変更されたエラーロケータ多項式を、
【数３】
0004368020.tif 000022
として生成する、請求項１２に記載のエラー訂正方法。
【請求項１５】
エラー値を決定するステップは、エラー値を
【数４】
0004368020.tif 000023
として決定することを含む、請求項１２に記載のエラー訂正方法。
【発明の詳細な説明】
【０００１】
【発明の分野】
この発明は、一般に、エラー訂正システムに関し、特に、データのエンコードおよび関連付けられるエラーシンドロームの生成を両方行なうハードウェアを使用するシステムに関する。
【０００２】
【発明の背景】
リード−ソロモンエラー訂正コード（ＥＣＣ）によって、ＥＣＣシンボルを生成するためデータをエンコードするためのエンコーダは周知である。「ｊ」個のＥＣＣシンボルを生成する従来のエンコーダは、ｊ個のガロア体乗算器を含む。ガロア体乗算器はそれぞれ、コード生成多項式ｇ（ｘ）のｊ個の係数と関連付けられる。エンコーダはまた、所与のデータシンボルと関連付けられる積を前のデータシンボルのエンコードの結果と合せるフィードバック加算器と、加算器によって生成された和を保持するｊ個のレジスタとを含む。エンコードの終了時に、ｊ個のレジスタにはＥＣＣシンボルが入っていることになる。
【０００３】
データシンボルがエンコーダに与えられるとき、シンボルは最後のレジスタの内容と合され、その結果がガロア体乗算器に与えられ、ガロア体乗算器はｇ（ｘ）の係数によって結果を同時に乗算する。第１のガロア体乗算器により生成された積は、第１のレジスタを更新する。残りのガロア体乗算器によって生成された積はそれぞれ、残りのレジスタの内容と合され、その結果がこれらのレジスタを更新するため使用される。そして、最後のレジスタが、（ｉ）最後のガロア体乗算器によって生成された積と、（ii）前のレジスタの内容との和で更新される。
【０００４】
次に、最後のレジスタの更新された内容は次のデータシンボルと合され、その結果がガロア体乗算器にフィードバックされ、残りのフィードバック加算器は、乗算器により生成された積を前のデータシンボルのエンコードの結果に加算し、この和をレジスタの更新のため与える、等々。最後のデータシンボルがエンコードされるとすぐに、ＥＣＣシンボルがｊ個のレジスタから読出されるかまたはクロックアウトされ、データシンボルと連結されて、適宜、伝送または記憶されるデータコードワードを生成する。
【０００５】
このようなエンコーダでは、加算器は並列動作してレジスタのための更新された和を生成するので、レイテンシは単一のフィードバック加算器に関連付けられる時間である。したがって、レイテンシは本質的に存在しない。
【０００６】
デコード演算の一部として、デコードシステムは、データコードワードのデータシンボルを操作して、エラーシンドロームを生成し、エラーシンドロームはデータ内のエラーを位置特定するために使用される。従来のエラーシンドローム発生器は、ｊ組の関連付けられる更新加算器、ガロア体乗算器およびレジスタを含み、各組が同時にかつ本質的に個別に動作して関連付けられるエラーシンドロームを生成する。
【０００７】
各更新加算器は、関連付けられるガロア体乗算器によって生成された積を次のデータシンボルに加算し、関連付けられるレジスタをこの和で更新する。次に、各ガロア体乗算器は、レジスタの内容を、ＥＣＣと関連付けられるエラーシンドローム生成多項式の係数で乗算し、その積を関連付けられる更新加算器に与える。更新加算器は、積を次のデータシンボルに加算し、その和を関連付けられるレジスタに与える、等々。最後のデータシンボルがシンドローム発生器に与えられ、レジスタを更新するため、ガロア体乗算器それぞれによって生成された積に加算された後、ｊ個のレジスタにはｊ個のエラーシンドロームが含まれることになる。
【０００８】
エンコーダ内に含まれるガロア体乗算器およびシンドローム発生器は、比較的複雑なコンポーネントである。１９９２年にＩＥＥＥから出版された、ゲルハルト・フェトバイス（Gerhard Fettweis）およびマーティン・ハスナー（Martin Hassner）の『ハードウェアの複雑性の低い組合せ型リード・ソロモンエンコーダおよびシンドローム発生器（A Combined Reed-Solomon Encoder And Syndrome Generator With Small Hardware Complexity）』は、エンコードおよびシンドローム発生の両方のために同じガロア体乗算器を使用するハードウェアを説明している。このように、組合せ型のハードウェアは、エンコーダとシンドローム発生器とが別個になったハードウェアにおいて必要な乗算器の数の２分の１の乗算器を使用する。前掲の論文はここに引用により援用される。
【０００９】
前掲論文で説明される組合せ型ハードウェアは、ｊ組の関連付けられるレジスタ、ガロア体乗算器、更新加算器およびフィードバック加算器を含む。ｊ個のレジスタは、ｊ個の関連付けられる更新加算器により生成される更新された和を保持する。各ガロア体乗算器は、関連付けられるレジスタの内容を生成多項式の根によって乗算し、その積を関連付けられるフィードバック加算器に与える。エンコード演算中、関連付けられるＡＮＤゲートは、前のフィードバック加算器により生成された和を加算器へと通す。加算器は次に、この積に伝搬和を加算し、その結果を、関連付けられる更新加算器および、次のＡＮＤゲートを通じて次のフィードバック加算器へと通す。次のフィードバック加算器は、関連付けられる乗算器により生成された積に伝搬和を加算し、その結果は、関連付けられる更新加算器へ、および次のＡＮＤゲートを通じて次のフィードバック加算器へと与えられる、等々。このように、フィードバック加算器および関連付けられるＡＮＤゲートは加算器がチェーンとして動作するフィードバック経路を形成する。
【００１０】
シンドローム発生演算中、ＡＮＤゲートは１つのフィードバック加算器から次のフィードバック加算器への和の伝搬をブロックすることによって、本質的に加算器のチェーンを切り、ｊ組の関連付けられるレジスタ、乗算器および加算器は別個に動作してｊ個のエラーシンドロームを生成する。
【００１１】
組合せ型のハードウェアでは、ｊ個のフィードバック加算器のチェーンを伝搬和が通るのにかかる時間に対応するレイテンシが、エンコード演算において存在する。もし、加算器のチェーンが長ければ、和はクロックサイクル中加算器のチェーン全体を通って伝搬せねばならないので、これによってデータをエンコードできる速度が制限される。したがって、システムは、関連付けられるレイテンシを超える速度でクロックされることはできない。
【００１２】
【発明の概要】
この発明は、エンコード演算中並列動作して中間和を生成するマルチプル・セルブロックに分けられる組合せ型エンコード／シンドローム発生回路である。そして、中間和は、第１のセルから最後のセルへとシステムにわたって和を伝搬させるため組合せられる。エンコード中のシステムにわたっての和の伝搬に関連付けられるレイテンシは、したがって、ｊ−１個の加算器のチェーンを通じての和の伝搬に関連付けられる時間から、ｌｏｇ2ｊ個の加算器を通じての和の伝搬に関連付けられる時間に減じられる。
【００１３】
さらに特定的には、各セルは、ガロア体乗算器、関連付けられる更新加算器およびレジスタを含む。２つのセルを含むブロックは、関連付けられるガロア体乗算器、レジスタおよび更新加算を２組、ならびに各セルによって並列に生成される積を合せて加算することによって関連付けられる中間和を生成するブロックフィードバック加算器を含む。３以上のセルを備えるブロックは、複数のセルによって生成された積を選択的に合せ最低限の遅延で、ブロック内の各セルからの寄与を含む中間和を生成するよう、並列動作する付加的なフィードバック加算器を含む。さらにシステムは、異なるブロックによって同時に生成された中間和を合せて加算し、システムを通じて和を伝搬させる。また、所与のブロックからの中間和は次のブロックのそれぞれのセルによって生成された積に並列に合され、関連付けられるレジスタにフィードバックされる更新信号内に前のセルの各々からの寄与が含まれる。
【００１４】
シンドローム発生演算中、セルは本質的に別個に動作しシンドロームを生成する。
【００１５】
このシステムは、従来のフェトバイス−ハスナー回路よりも多くのフィードバック回路を含むが、これは、（ａ）中間和の生成、（ｂ）伝搬和への和の組合せ、および（ｃ）隣接するブロック内のセルへの中間和の加算のためにエンコード中に加算器が必要なためである。しかし、このシステム内のフィードバック加算器の多くは並列動作するため、このシステムを通じての遅延は従来のシステムの遅延よりも減じられる。
【００１６】
【詳細な説明】
以下に従来のフェトバイス−ハスナーシステムのエンコード演算を説明し、その後、フェトバイス−ハスナーシステムよりもレイテンシの少ない、エラー訂正シンボルを生成するエンコード／シンドローム発生システムのエンコード演算を説明する。
【００１７】
図１に示すように、従来のフェトバイス−ハスナー回路１は、それぞれのガロア体乗算器２によって生成された積を和に含ませることによって、フィードバック経路６にわたって和を伝搬する。各ガロア体乗算器２は、関連付けられる更新加算器３によって生成された和を、生成多項式ｇ（ｘ）＝（ｘ＋ａ0）（ｘ＋ａ1）（ｘ＋ａ2）…（ｘ＋ａj-1）の根で乗算する。関連付けられるフィードバック加算器４は、この積を伝搬和と合せ、ＡＮＤゲート５が、この和をフィードバック経路６に沿って通す。フィードバック加算器４によって生成された和はまた、関連付けられるレジスタ７を更新する。次のクロックサイクル中に、レジスタ７の内容は、関連付けられる更新加算器３内の次のデータシンボルと合される。ｎ番目のクロックサイクル中、すなわち、ｎ番目のデータシンボルがシステムに与えられているときに、ｉ番目のフィードバック加算器４によって生成される伝搬和は、
【００１８】
【数５】
0004368020.tif 000002
【００１９】
ただし、ｒn-1,iはｉ番目のレジスタ７の内容を表わし、ｄnはｎ番目のデータシンボルである。レジスタ７は、前のクロックサイクルの間に生成された伝搬和を含み、式１は、
【００２０】
【数６】
0004368020.tif 000003
【００２１】
となる。ｉ≧０かつｙn,-1＝０の場合、伝搬和は、
【００２２】
【数７】
0004368020.tif 000004
【００２３】
である。
伝搬和は、前の乗算器すべてによって生成された積を含む。したがって、関連付けられるレイテンシは、本質的に、ｊ−１個のフィードバック加算器４を通じてフィードバック経路６に沿って和が通されるのにかかる時間である。各加算器は、ＸＯＲゲートとして実現され、クロックサイクルはしたがって、少なくともｊ−１個のＸＯＲゲートのチェーンを通じての遅延の長さがなければならない。
【００２４】
Ａ．エンコード演算
遅延を減じるため、図４および図５を参照して以下に説明する組合せ型エンコード／シンドローム生成システム１００は、並列動作して中間和を生成する複数のマルチプル・セルブロック２０に分けられる。そして中間和は合され、伝搬和を生成する。セルおよびブロックが並列動作するので、システムにわたっての和の伝搬に関連付けられる時間は著しく減じられる。
【００２５】
図２を参照し、図４および図５に示されるシステム１００のｉ番目のセル１０iは、ｎ番目の時間期間においてデータシンボルｄnを関連付けられるレジスタ１４iの内容ｒn-1,iに加算する更新加算器１２iを含む。加算結果は、ガロア体乗算器１６内で生成多項式のｉ番目の根によって乗算され、ライン１５上でセル出力信号、
【００２６】
【数８】
0004368020.tif 000005
【００２７】
を生成する。
また図３を参照し、ブロック２０i+1は、２つのセル１０iおよび１０i+1と、関連付けられる中間和
【００２８】
【数９】
0004368020.tif 000006
【００２９】
を生成するブロックフィードバック加算器２２i+1を含む。便宜上、ブロック２０およびブロックフィードバック加算器２２は、ブロック内の最後のセルの参照番号で参照する。
【００３０】
マルチプルブロック２０は、合せてグループ３０として動作し、グループ３０はより大きなブロックとも考えることができる。２つのブロックを含むグループ３０i+3は、２つのブロックによって生成されたそれぞれの和を合せて加算し関連付けられる中間和を生成するフィードバック加算器２４i+3を含む。フィードバック加算器２６は、中間和を前のグループからの伝搬和に加算し、その結果を次のグループへ通す、等々。各グループはまた、前のグループからの中間和をそれぞれのセル１０によって生成される積に加算するため、フィードバック加算器２６と並列動作する１以上の中間フィードバック加算器２３も含む。中間フィードバック加算器２３によって生成された和Ｉn,iは次に、関連付けられるレジスタ１４iを、ｒn,i＝Ｉn,iなどに更新するようフィードバックされる。グループ内の第２のブロック内の所与のレジスタ１４iに与えられる更新和Ｉn,iはこのように、グループ内の第１のブロック内のセルも含めシステム内の前のセルすべてによって生成された積を組入れる。
【００３１】
通常、各々２つのセルを有するｍ個のブロックを含むグループは、中間和
【００３２】
【数１０】
0004368020.tif 000007
【００３３】
を生成し、これは式３に示す伝搬和と等しい。
図４に示すように、８つの冗長シンボルを生成するためのシステム１００は、２つのセルを含む４つのブロック２０1、２０3、２０5および２０7を含む。４つのブロックは、並列動作し、ブロックフィードバック加算器２２1、２２3、２２5および２２7において４つの和Ｂn,iを１組生成する。ブロック２０1および２０3、ならびにブロック２０5および２０7は、グループ分けされ、それぞれグループ３０3および３０7として並列動作し、フィードバック加算器２４3および２４7に中間和を生成する。そして伝搬和フィードバック加算器２６7は、中間和を合せて、システム内で第１のセルから最後のセルへと和を伝搬する。
【００３４】
システムを通じての遅延は、和Ｂn,iを並列に生成し、和を並列に加算して中間和を生成し、中間和を合せ伝搬和を生成するのに関連付けられる時間である。したがって遅延は、３つのＸＯＲゲートを通じて伝搬するための時間である。
【００３５】
上述のように、異なった中間和が、次のブロックまたはグループ内の中間フィードバック加算器２３iに並列に選択的に与えられ、さまざまなセル１０i内の関連付けられるレジスタ１４iを更新する和Ｉn,iに含まれる。
【００３６】
より特定的には、第１のブロック２０1内のフィードバック加算器２２1によって生成された和Ｂn,1は、フィードバック加算器２４3内で第２のブロックによって同時に生成された和Ｂn,3と合される。その結果が中間和Ｍn,3である。
【００３７】
【数１１】
0004368020.tif 000008
【００３８】
Ｍn,3は、次のグループ３０i+7に伝搬され、またグループ内の最後のセル１０3のレジスタ１４3を更新するためフィードバックされる。同時に、和Ｂn,1は中間フィードバック加算器２３2へ与えられ、中間フィードバック加算器２３2は、関連付けられるレジスタ１４2へフィードバックされる更新値内にこの和を含ませる。第２のブロック内の各セルはこのようにして、すべての前のセルからの寄与によって適切に更新される。
【００３９】
第１および第２のブロックと並列動作する第３および第４のブロック２０5および２０7はＢn,5およびＢn,7を生成する。これらの和はフィードバック加算器２４7において合され、関連付けられる中間和Ｍn,7を生成する。次に、第１のセルから最後のセル１０7へ和を伝搬させるため、中間和は、第１のグループにより生成された中間和とフィードバック加算器２６7において合される。また、第１のグループ内で生成された中間和は、中間フィードバック加算器２３4、２３5および２３6へ同時に与えられ、前のセル各々によって生成された積が、関連付けられるレジスタ１４4、１４5および１４6にフィードバックされる更新信号内に含まれるようになる。
【００４０】
すべてのデータシンボルがシステムに与えられ、関連付けられる和がシステムを通じて伝搬された後、フィードバック加算器２６7によって生成された和が更新加算器１２iに通されるようスイッチ３０が再位置付けされる。そして、スイッチ３０は同じ位置のままで、システムはさらにｊ−１回クロックされ、ｊ個の冗長シンボルを生成する。
【００４１】
データシンボルがシステムに供給される間、スイッチ３２はデータシンボルを出力ライン３４へと通す。その後、スイッチ３２は、次のｊ−１回のクロックサイクルの間冗長シンボルを出力ライン３４へと通すよう再位置付けされる。
【００４２】
システム１００のレイテンシは、対応するフィードバック加算器のさまざまな「層」を通じて通過することに関連付けられる遅延である。第１の層において、システムは、フィードバック加算器２２iを並列動作させ、個々のセルによって生成された積を合わせ、関連付けられる遅延が単一のＸＯＲゲートを通じて通るのにかかる時間となる。次に、和は、フィードバック加算器２４iを含む第２の層に同時に与えられる。これらの加算器も並列動作し、フィードバック加算器の第１の層によって生成された和を合わせて、次の和の組を生成する。第２の層を通じての関連付けられる遅延はやはり、単一のＸＯＲゲートを通過するのにかかる時間である。フィードバック加算器２４iによって生成される和の組は、中間和の組である。第３の層においては、フィードバック加算器２６7は単一のＸＯＲゲートを通じて中間和を合わせ、第１のセル１０0から最後のセル１０7へ和を伝搬させる。このように、システム内には８つのＥＣＣシンボルを生成する３つの層があり、関連付けられるレイテンシは３つのＸＯＲゲートを通じての遅延である。これは、７つのＸＯＲゲートのチェーンを通じての遅延に関連付けられるレイテンシを持ち、８つのＥＣＣシンボルを生成する従来のフォトバイス−ハスナーシステムとは対照的である。
【００４３】
９以上のＥＣＣシンボルを生成するシステムにおいては、システムを通じて一グループから他グループへと和が伝搬するよう、ブロックはより多数の並列動作するブロックのグループに編成される。このようなシステムでは、レイテンシは、本質的に、構成要素であるブロックまたはグループを通じての遅延である。
【００４４】
たとえば、システムが、２つの８セルグループとして動作する１６個のセルを含むとする。各グループは並列動作する８つの構成要素セルを備える４つの２セルブロックとして動作し、やはり並列で、合わされる積を生成し、関連付けられる４つのブロック和を生成する。このように、ブロック和は、単一のＸＯＲゲートを通じて通ることに関連付けられる遅延で生成される。次に４つのブロック和は、やはり単一のＸＯＲゲートを通じての遅延で、２つのより大きなブロック和へと並列に合わされる。次に、２つのより大きなブロック和が合わされて、もう１つの単一のＸＯＲゲートを通じての遅延で、グループに対しての中間和を生成する。グループを通じての関連付けられる遅延はしたがって、３つのＸＯＲゲートを通過することに関連付けられる遅延である。
【００４５】
２つのグループ内で並列に生成された中間和は、次に、合わされて１以上のＸＯＲゲートを通ることに関連付けられる遅延で、伝搬和を生成する。このように、１６個のＥＣＣシンボルを生成するシステムを通じての総遅延は、４つのＸＯＲゲートに関連付けられる遅延である。通常、Ｌ個のセルを含むシステムを通じての遅延は、ｌｏｇ2Ｌ個のＸＯＲゲートを通じての伝搬にかかる時間である。
【００４６】
上述のように、システム１００は従来のシステムよりも多くのＸＯＲゲートまたは加算器を必要とする。８セルシステムにおいて伝搬和を生成するために必要とされるフィードバック加算器の総数は１２であり、４つの２セルブロックの各々に１つずつ、各ブロック対の結果を２つの中間和に合わせるためにもう２つ、中間和を伝搬和に合わせるために１つ、そして、第２、第３および第４の２セルブロックのさまざまなセル用に中間和を更新値に含ませるために５つの中間フィードバック加算器がある。さらに、全部で２０個のＸＯＲゲートに対し、システムは８つのセルの各々内に更新加算器を含む。もし、システムが２つの８セルグループを含むのであれば、すなわち１６個のセルを含むのであれば、システムは全部で４８個のゲートを含み、第１の８セルグループに対して２０、第２の８セルグループに対して２７、そして２つのグループによって生成された中間和を合わせるために１つである。第２のグループ内の余分な７つの加算器は、第１のグループによって生成された中間和を第２のグループ内の各セルによって生成された更新値に加算する中間フィードバック加算器である。
【００４７】
システム１００において必要とされるＸＯＲゲートの総数、すなわち、更新およびフィードバック加算器の総数は、システム内のセルの数に基づく。２L個のセルを備えるシステムにおいては、ＸＯＲゲートの総数は、
Ｎ＝（Ｌ＋２）*２L-1
である。したがって、８つの冗長シンボルを生成するシステム、したがって８＝２3個のセルを有するシステムにおいては、上記からＸＯＲゲートの総数は（３＋２）２2＝２０となる。８つの冗長シンボルを生成する従来のフェトバイス−ハスナー回路は、全部で８つの更新加算器と７つのフィードバック加算器または１５個のＸＯＲゲートを有する。図４に示す回路１００はしたがって付加的な５つのＸＯＲゲートを有する。しかし、システム１００にわたっての和の伝搬に関連付けられる遅延は、従来のシステムにおける７つのＸＯＲゲートのチェーンを通っての通過の遅延から、ｌｏｇ2個のＸＯＲゲート、または３個のＸＯＲゲートのチェーンを通じての通過の遅延に減じられる。
【００４８】
より一般的には、セルの数が２のべき乗ではないシステム、すなわち冗長シンボルの数がＲ≠２Lのシステムでは、ＸＯＲゲートの数は式
【００４９】
【数１２】
0004368020.tif 000009
【００５０】
によって決定され、ただし、
【００５１】
【数１３】
0004368020.tif 000010
【００５２】
である。たとえば、Ｒ＝２5＋２2かつＳ＝１で、３６個の冗長シンボルを生成するシステムでは、Ｎ個のＸＯＲゲートが必要であり、
【００５３】
【数１４】
0004368020.tif 000011
【００５４】
である。このシステムは、ＬS＋１または６個のＸＯＲゲートを通じての遅延で、冗長シンボルを生成する。これと対照的に、従来のシステムは７１個のＸＯＲゲートを使用して冗長シンボルを生成し、Ｒ−１または３５個のＸＯＲゲートを通じての遅延を有する。
【００５５】
システム１００がシンドローム発生のために使用されるとき、ライン２８上の信号をデアサートすることで、ＡＮＤゲート５が非活性化される。そしてセル１０は、個別に動作して関連付けられるシンドロームを生成する。バイパススイッチ４０は、ガロア体乗算器へではなく、関連付けられるフィードバック加算器２２iへ直接的に、そして、したがって関連付けられるレジスタ１４iへ直接的につながるよう、各セル内に含まれてよい。このとき、レジスタ１４iはエラーシンドロームＳiを含み、Ｓiはエラー位置を決定するため従来の態様で使用される。
【００５６】
バイパススイッチ４０がシステム１００内に含まれていない場合、システムは変更されたエラーシンドロームαiＳiを生成する。図７を参照して以下に説明するように、我々はエラー位置を決定するため、変更されたエラーシンドロームを直接使用するデコードシステムを開発した。図７のデコードシステムは、従来のデコードシステムよりも複雑であり、エンコーダとデコーダの複雑性のトレードオフが図られている。
【００５７】
次に図６を参照し、代替的システム１０１は、更新加算器１２iとガロア体乗算器１６との間にレジスタ１４iが位置付けられたセルを含む。このシステムでは、データがフィードバック信号Ｉn,iへ加算され、その結果はレジスタを更新するため使用される。したがってレジスタは、和
【００５８】
【数１５】
0004368020.tif 000012
【００５９】
を含み、ただしＹn-1,iは前のクロックサイクルからの伝搬和である。次のクロックサイクルにおいてガロア体乗算器は、レジスタの内容を、生成多項式の根によって乗算し、関連付けられるフィードバック加算器２２iへ積αi*（Ｙn-1,i＋ｄn）を与える。したがって、フィードバック加算器は、結果
【００６０】
【数１６】
0004368020.tif 000013
【００６１】
を生成し、この式は再び式３と同じ結果である。
システム１０１はエンコード演算中、システム１００と同じ減じられたレイテンシを有する。シンドローム発生中は、データシンボルは更新されたレジスタ内に直接含まれるため、レジスタは実際のエラーシンドロームを含み、上に述べた変更されたシンドロームを含むのではない。したがって、システムは、バイパススイッチ４０（図４）を必要とすることなく、従来のデコードシステムに関連して使用され得る。
【００６２】
Ｂ．デコード演算
生成多項式ｇ（ｘ）＝（ｘ−αL）（ｘ−αL+1）…（ｘ−２L+2t）の長さｎのリードソロモンＥＣＣおよび有限体ＧＦ（２n）については、コードワードの位置はαi、αl…αn-1である。デコードのためのコードワードはｃ＋ｅであり、ｃはエラーぬきのコードワードであり、ｅはエラーを表わす。もし位置Ｘ0、Ｘ2、…Ｘv-1にｖ個のエラーがあり、対応するエラー値がＹ0、Ｙ1…Ｙv-1であれば、実際のエラーシンドロームは、
【００６３】
【数１７】
0004368020.tif 000014
【００６４】
である。上述のように、エラーシンドロームはコードワードｃ＋ｅから計算できる。
【００６５】
エラーロケーション多項式、
【００６６】
【数１８】
0004368020.tif 000015
【００６７】
はまた、たとえば周知のベールカンプ−マッセイまたはユークリッドデコーディングアルゴリズムおよび
Ｓj+v-1＋σ1Ｓj+v-2＋…σv-1Ｓj＝０  ただし  ｊ＝１，２…ｖ
などを使用して、エラーシンドロームＳiから既知の態様で決定できる。そしてエラー値およびエラー位置は既知の態様で計算可能である。
【００６８】
上述のように、システム１００は、バイパススイッチ４０がない場合、変更されたシンドロームを生成する。変更されたシンドロームは、
αi+LＳi＝Ｔi  ただし  ｉ＝１，２…ｖ
である。上述のシステムでは、Ｌ＝０かつＴi＝αiＳiである。
【００６９】
我々は、既知のベールカンプ−マッセイまたはユークリッドデコーディングアルゴリズムを使用して、変更されたシンドロームから、変更されたエラーロケータ多項式
【００７０】
【数１９】
0004368020.tif 000016
【００７１】
を計算できると判定し、
Ｔj+v-1＋Ａ1Ｔj+v-2＋…Ａv-1Ｔj＝０
となる。もし、Ω（ｘ）≡Ａ（ｘ）Ｔ（ｘ）ｍｏｄＸ2tであれば、変更されたエラー位置Ｚ1、…ＺvはΩ（ｘ）の根であり、エラー値は、
【００７２】
【数２０】
0004368020.tif 000017
【００７３】
である。Ａ（ｘ）により生成される変更されたエラー位置は、αＺ1、αＺ2…αｚvであり、ただし
【００７４】
【数２１】
0004368020.tif 000018
【００７５】
である。したがって、実際のエラー位置は、Ａ（ｘ）から計算される変更されたエラー位置から１つ位置がずらされた
【００７６】
【数２２】
0004368020.tif 000019
【００７７】
である。
次に図６を参照し、変更されたシンドロームとともに使用するためのデコードシステム２００は、変更されたシンドロームＴi＝αL=iＳiから、変更されたエラーロケータ多項式Ａ（ｘ）を決定し、変更されたエラー位置を決定するためＡ（ｘ）の根を計算するエラーロケータプロセッサ７０を含む。エラー値プロセッサ７２は、上述のようにエラー値Ｙmを計算するため、変更されたエラー位置Ｚ1…Ｚvを使用する。そして、エラー訂正プロセッサは実際のエラー位置をαＺ、…αＺvとして決定し、計算されたエラー値を使用してエラーのあるシンボルを訂正する。
【００７８】
このように、変更されたエラーシンドロームが使用されるときは、エラー訂正プロセッサについて１つ余計なステップができる。エンコーダの単純性についてのトレードオフ、すなわち、バイパススイッチ４０の除去によってより複雑なデコーダとなる。
【００７９】
上述の説明はこの発明の特定の実施例に限定されている。しかし、この発明のすべてのまたはいくつかの利点を達成しつつ、この発明の変形例および修正例が作られ得ることが明らかであろう。したがって、添付の請求の範囲の目的は、このような変形および修正をこの発明の真の精神および範囲内にあるものとしてカバーすることである。
【図面の簡単な説明】
【図１】  従来のフォトバイス−ハスナー回路の機能ブロック図である。
【図２】  セルの機能ブロック図である。
【図３】  ２セルブロックの機能ブロック図である。
【図４】  ８つの冗長シンボルを生成するマルチプルブロックシステムの機能ブロック図である。
【図５】  代替的セルを備える図４のシステムの機能ブロック図である。
【図６】  図４のシステムの変更されたものとともに使用するためのデコードシステムの機能ブロック図である。
【符号の説明】
１２  更新加算器、１４  レジスタ、１６  ガロア体乗算器、２０  マルチプル・セルブロック、２２  ブロックフィードバック加算器、２３  中間フィードバック加算器、１００  組合せ型エンコード／シンドローム発生システム。
【図１】
0004368020.tif 000024
【図２】
0004368020.tif 000025
【図３】
0004368020.tif 000026
【図４】
0004368020.tif 000027
【図５】
0004368020.tif 000028
【図６】
0004368020.tif 000029