(57)【特許請求の範囲】
【請求項１】
同期エラーの検出に用いるための符号化システムであって、
Ａ．距離ｄリードソロモンコードまたはＢＣＨコードに従ってデータを符号化するためのエンコーダを含み、このエンコーダはデータコードワードを生成し、さらに
Ｂ．距離ｄ′リードソロモンコードまたはＢＣＨコードのコードワードであるが、距離ｄコードのコードワードではない剰余類リーダを生成するための手段を含み、ここでｄ／２＜ｄ′＜ｄであり、さらに
Ｃ．剰余類リーダをデータコードワードに付加して、記録するためのコードワードを生成するための加算器を含み、このコードワードには距離ｄコードのすべてのコードワードからの距離ｄ′である項が含まれる、符号化システム。
【請求項２】
剰余類リーダを生成するための手段は、データコードワードに距離ｄ′コードの短くしたコードワードのｒ＋１個のコピーを加えるＸＯＲゲートを含む、請求項１に記載の符号化システム。
【請求項３】
剰余類リーダを生成するための手段は、データコードワードに短くしたコードワードｍ（ｘ）*ｇ′（ｘ）のｒ＋１個のコピーを加える、請求項２に記載の符号化システム。
【請求項４】
システムは、多項式ｍ（ｘ）を規約多項式となるよう選択する、請求項３に記載の符号化システム。
【請求項５】
剰余類リーダを生成するための手段は、
【数１】
0004527255.tif 000012
を生成し、ここでｍ（ｘ）*ｇ′（ｘ）は距離ｄ′コードの短くしたコードワードであり、ｄ"はｍ（ｘ）*ｇ′（ｘ）よりも大きいかまたはこれに等しく、ｎ≧ｐ＋ｒｄ"＋ｄ′−１であり、かつｇ′（ｘ）はコードの長さｎを有する距離ｄ′コードの生成多項式である、請求項２に記載の符号化システム。
【請求項６】
システムは、剰余類リーダがデータコードワードの中心となるようにＰの値を選択する、請求項５に記載の符号化システム。
【請求項７】
システムは、多項式ｍ（ｘ）を規約多項式となるよう選択する、請求項５に記載の符号化システム。
【請求項８】
剰余類リーダを生成するための手段は、剰余類リーダを
【数２】
0004527255.tif 000013
として生成するためのシフトレジスタを含み、ここでｍ（ｘ）*ｇ′（ｘ）は距離ｄ′コードの短くしたコードワードであり、ｄ"はｍ（ｘ）*ｇ′（ｘ）の次数よりも大きく、ｎ≧p＋ｒｄ"＋ｄ′−１であり、かつｇ′（ｘ）はコードの長さｎを有する距離ｄ′コードの生成多項式である、請求項２に記載の符号化システム。
【請求項９】
システムは、剰余類リーダがデータコードワードの中心になるようＰの値を選択する、請求項８に記載の符号化システム。
【請求項１０】
システムは、多項式ｍ（ｘ）を規約多項式となるよう選択する、請求項８に記載の符号化システム。
【請求項１１】
距離ｄ′コードは、ｄ′連続根を伴う生成多項式を有する、請求項１に記載の符号化システム。
【請求項１２】
項ｂ（ｘ）*ｘS＋ｂ（ｘ）をテストするための手段をさらに含み、ここでｂ（ｘ）は剰余類リーダであり、−Ｔ≦Ｓ≦Ｔであり、Ｔは同期エラーにおけるシンボルの最大数であり、この手段によってその項が距離ｄコードのコードワードではないことを判断する、請求項１１に記載の符号化システム。
【請求項１３】
距離ｄリードソロモンコードまたはＢＣＨコードに従って符号化されたデータコードワード中の同期エラーを検出するための方法であって、
Ａ．ｄ′＜ｄのとき、距離ｄ′リードソロモンコードまたはＢＣＨコードのコードワードであるが、データコードワードにデータを符号化するために用いられる距離ｄコードのコードワードではない剰余類リーダｂ（ｘ）を選択するステップと、
Ｂ．−Ｔ≦Ｓ≦ＴであってＴが同期エラーにおけるシンボルの最大数であるとき、項ｂ（ｘ）*ｘS＋ｂ（ｘ）をテストすることによって、その項が距離ｄコードのコードワードではないことを判断するステップと、
Ｃ．記録する前にデータコードワードに剰余類リーダを付加するステップと、
Ｄ．検索されたコードワードに剰余類リーダを付加するステップと、
Ｅ．ステップＤの結果のコードワードをデコードし、かつコードワードのエラーを検出するステップと、
Ｆ．デコードするステップが距離ｄコードが訂正できるよりも多くのエラーを検出したときに、データを誤りとラベルするステップとを含む、方法。
【請求項１４】
剰余類リーダを生成するステップは、剰余類リーダに距離ｄ′コードのｒ＋１個のコピーの短くしたコードワードを含むステップをさらに含む、請求項１３に記載の方法。
【請求項１５】
剰余類リーダを生成するステップは、剰余類リーダにｒ＋１個のコピーの短くしたコードワードｍ（ｘ）*ｇ′（ｘ）を含むステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
剰余類リーダを生成するステップは、多項式ｍ（ｘ）が規約多項式となるよう選択するステップを含む、請求項１５に記載の方法。
【請求項１７】
剰余類リーダを生成するステップは、剰余類リーダを
【数３】
0004527255.tif 000014
として生成することをさらに含み、ここでｄ"はｍ（ｘ）*ｇ′（ｘ）の次数よりも大きく、ｎ≧ｐ＋ｒｄ"＋ｄ′−１であり、かつｇ′（ｘ）はコードの長さｎを有する距離ｄ′コードの生成多項式である、請求項１５に記載の方法。
【請求項１８】
剰余類リーダを生成するステップは、剰余類リーダがデータコードワードの中心となるようｐの値を選択するステップを含む、請求項１７に記載の方法。
【請求項１９】
剰余類リーダを生成するステップは、剰余類リーダを
【数４】
0004527255.tif 000015
として生成するステップを含み、ここでｄ"はｍ（ｘ）*ｇ′（ｘ）の次数よりも大きく、ｎ≧ｐ＋ｒｄ"＋ｄ′−１であり、かつｇ′（ｘ）はコードの長さｎを有する距離ｄ′コードの生成多項式である、請求項１５に記載の方法。
【請求項２０】
剰余類リーダを生成するステップは、剰余類リーダがデータコードワードの中心になるようｐの値を選択するステップをさらに含む、請求項１９に記載の方法。
【請求項２１】
剰余類リーダを生成するステップは、多項式ｍ（ｘ）が規約多項式となるよう選択するステップを含む、請求項１９に記載の方法。
【請求項２２】
剰余類リーダを生成するステップは、ｄ′連続根を伴う生成多項式を有する距離ｄ′コードを選択するステップを含む、請求項１３に記載の方法。
【請求項２３】
ａ．距離ｄ′コードとして、ｄ′連続根を伴う生成多項式を有する距離ｄ′＝ｄ−１コードを選択するステップと、
ｂ．ｄ′距離コードが同期エラーの検出に用いるための適切なテストを行なう剰余類リーダを含まないとき、距離ｄ′コードとして、ｄ′連続根を伴う生成多項式を有する距離ｄ′＝ｄ′−１コードを選択するステップと、
ｃ．ｄ′距離コードが同期エラーの検出に用いるための適切なテストを行なう剰余類リーダを含まないときに、ステップａおよびｂを繰返すステップとをさらに含む、請求項２２に記載の方法。
【請求項２４】
剰余類リーダを付加するステップは、剰余類リーダをデータコードワード冗長シンボルに付加するステップを含む、請求項１３に記載の方法。
【発明の詳細な説明】
【０００１】
データは、磁気ディスク上のセクタに分割されたトラックに記録される。各セクタは、セクタ番号およびその他の情報を列記した見出し部分と、データが記録されたデータ部分とを含む。セクタ間には同期情報も含まれているため、ディスクドライブはセクタの開始を決定することができ、最終的にはセクタのデータ部分の開始を決定できる。
【０００２】
記録の前に、データは典型的にはエラー訂正コード（ＥＣＣ）を用いてデータコードワードに符号化される。次いでそのデータコードワードがセクタのデータ部分に記録される。その後データを読取るために、ディスクドライブは適切なトラックの上に読書きヘッドを移動し、記録された同期情報を用いて目的のセクタのデータ部分の開始を決定する。次いでヘッドはデータコードワードを読取り、それをデコーダに供給する。デコーダはコードワードシンボルを処理し、必要に応じてＥＣＣを用いてもしエラーがあればそれを訂正することによって、データを再生する。
【０００３】
ドライブがデータコードワードの開始位置の決定を誤ったとき、すなわち同期エラーが起こったときには、ドライブはデータコードワードの一部分と、同期エラーの方向に依存して、データコードワードに先行する情報またはデータコードワードに後続する情報とを読取る。デコーダがディスクから読取られたものを有効なデータコードワードとして誤って解釈すると、デコーダは次いでコードワード中のそれがエラーだと知覚したものを「訂正」し、その結果をエラーのないデータとしてアプリケーションまたはユーザに送る。
【０００４】
最もよく用いられるＥＣＣはリードソロモンコードである。リードソロモンコードはデータをガロア体（２q）上に符号化し、ここでｑはコードシンボルまたは要素中のビット数である。リードソロモンコードは循環している。したがって、ｃ0ｃ1...ｃcが短くされていないコードワードであって、ここでｃjがＧＦ（２p）の要素であるとき、ｃ1...ｃcｃ0およびｃcｃ0ｃ1...ｃc-1もまたコードワードである。つまり、１つまたはそれ以上のシンボルの同期エラーによって、異なるが有効なコードワードが生成される可能性がある。同期エラーが全シンボルではなくいくつかのビットを含むとき、デコーダはすべてのコードワードシンボルが誤っていると検出しがちである。したがってデコーダはエラーを訂正できず、そのデータを誤りとしてラベルする。
【０００５】
シンボルサイズの同期エラーの誤解釈を防ぐために、特定の先行システムではコードワードが記録される前に、各データコードワードにノイズ様シーケンスを加える。この付加は、ガロア体演算を用いて、シーケンスおよびデータコードワードをＸＯＲ処理することによって成し遂げられる。デコードする前に、このシステムはシーケンスに対してＸＯＲ処理することによってシーケンスを取除き、検索されたコードワードを得る。読取動作がコードワードの開始と同期したとき、すなわち同期エラーがないときには、シーケンスのＸＯＲ処理および検索されたコードワードは、元のデータコードワードを再生する。
【０００６】
さもなければ、検索されたコードワードに対するシーケンスのＸＯＲ処理はコードワードにエラーをもたらす。シーケンスが適切に選択されたと仮定すると、次いでデコーダはＥＣＣが訂正できる以上のエラーを検出し、その同期エラーを起こしたデータを誤りとラベルする。シーケンスが適切に選択されないときは、ＸＯＲ処理演算はその代わりに、ＥＣＣによって「訂正」可能な、異なるが有効なコードワードを生成するおそれがある。
【０００７】
先行システムは、ノイズ様シーケンスを見出すために試行錯誤法を用いる。試行錯誤法は時間がかかり、また必ずしも同期エラーを含む検索されたコードワードに最大数のエラーをもたらすシーケンスを生成しない。さらに、先行システムは選択されたシーケンスをエンコーダに記憶しなければならないため、システムに要求される全記憶量が増加する。したがって記憶容量に制限のあるシステムに対しては、この同期エラー技術は非実用的であろう。
【０００８】
この発明のエラー訂正システムは、距離ｄリードソロモンコードに従って符号化されたデータコードワードに対して、距離ｄリードソロモンコードの距離ｄ′スーパーコードのコードワードである剰余類リーダ（coset leader）をＸＯＲ処理することによって、記録のためのコードワードを生成する。剰余類リーダは、距離ｄコードのコードワードでないように選択される。後でコードワードが検索されるときには、システムは検索されたコードワードに対して剰余類リーダをＸＯＲ処理する。同期エラーがなければ、このＸＯＲ演算は元のデータコードワードを再生する。しかし同期エラーがあるときには、ＸＯＲ処理演算によって、検索されたコードワードには距離ｄリードソロモンコードの有効なコードワードの各々からのハミング距離ｄ′である項がもたらされる。その結果、ｄ′＞ｄ／２である限り、ＥＣＣが訂正できる以上のエラーが含まれるようになる。
【０００９】
このシステムは、距離ｄリードソロモンコードの生成多項式に基づいた剰余類リーダをそこから選択するためのスーパーコードを決定する。αがＧＦ（２q）の初期要素であるとき、連続根αLαL+1αL+2...αL+d-1を有する生成多項式を伴うコードに対しては、システムはスーパーコードとして、ｄ−１連続根を有する生成多項式を伴う距離ｄ−１リードソロモンコードを第１に選択する。したがってこのスーパーコードは、根αL+1αL+2...αL+d-1または根αLαL+1αL+2...αL+d-2を有する生成多項式を有する。次いでこのシステムは、これらのコードの１つから、これもまた距離ｄコードのコードワードではない剰余類リーダｂ（ｘ）を選択する。
【００１０】
このシステムは次に、項ｊ（ｘ）＝ｂ（ｘ）*ｘS＋ｂ（ｘ）が、対象となるすべてのＳに対する距離ｄコードの有効なコードワードではないことをチェックする。以下により詳しく述べるとおり、ここで−Ｔ≦Ｓ≦Ｔであり、Ｔは読書きヘッドが同期エラーを起こし得るシンボルの最大数である。必然的に距離ｄ−１コードのコードワードであるｊ（ｘ）が、距離ｄコードのコードワードではないとき、同期エラーを含む検索されたコードワードに対するｂ（ｘ）のＸＯＲ処理は、距離ｄコードのすべての有効なコードワードからの最小ハミング距離ｄ−１である項をコードワードにもたらす。
【００１１】
ｊ（ｘ）が距離ｄコードの有効なコードワードであるとき、システムは距離ｄ−１コードからの残りの剰余類リーダの各々を選択しテストする。適切なものがないときには、システムはｄ−２連続根を伴う生成多項式を有する距離ｄ−２リードソロモンコードからの剰余類リーダを選択およびテストし、以下同様にする。
【００１２】
システムの記憶要求を減少させるために、剰余類リーダは、距離ｄ′コードの短くされたコードワードのｒ＋１バージョンを含むコードワードとなるよう選択されてもよい。したがって剰余類リーダは次のようになる。
【００１３】
【数５】
0004527255.tif 000002
【００１４】
ｄ"はｍ（ｘ）*ｇ′（ｘ）の次数よりも大きいかまたはこれに等しく、ｐ＋ｒｄ"＋ｄ′−１≦ｎであり、ここでｇ′（ｘ）は距離ｄ′コードの生成多項式であり、ｎはコードの長さである。項ｍ（ｘ）は規約多項式となるよう選択されてもよく、ｐおよびｄ"は後述のとおり選択される。次いでこのシステムは剰余類リーダ全体の代わりに短くされたコードワードを記憶し、短くされたコードワードをデータコードワードのシンボルに対してｒ＋１回ＸＯＲ処理する。
【００１５】
その代わりにこのシステムは、短くしたコードワードにαeを繰返し乗ずることによって剰余類リーダを生成してもよく、その剰余類リーダは次のようになる。
【００１６】
【数６】
0004527255.tif 000003
【００１７】
これは、その初期状態においては係数ｘP*ｍ（ｘ）*ｇ′（ｘ）を含み、各繰返しにおいてその内容にαeを乗ずる線形フィードバックシフトレジスタを用いて直ちに生成できる。ｒおよびｅは、α(r+1)e＝１であってｒ回の繰返しの後にシフトレジスタが初期状態に戻るような値であることが望ましい。さもなければ、システムはｒ回の繰返しの後、レジスタをその元の状態に再ロードする。その代わりに、以下により詳細に考察するとおり、シフトレジスタは短くされたコードワードに任意のαj値を乗じてもよい。
【００１８】
このシステムはまた、予め定められた初期状態に対してセットされたｍビット２進最大長線形フィードバックシフトレジスタを用いて、剰余類リーダのデータ部分を生成してもよい。しかし、システムに距離ｄ′コードに対する別のエンコーダを含むことを避けるために、システムは関連する冗長シンボルを記憶する。
【００１９】
代替的には、システムはデータコードワードの冗長シンボルに対してのみ剰余類リーダをＸＯＲ処理し、データシンボルを保存してもよい。以下に詳細に考察するとおり、選択された剰余類リーダはｐ＝０，１...，ｄ−ｄ′−１に対してｘP*ｇ′（ｘ）であってもよく、ここでｐの値は剰余類リーダが冗長シンボルの「中心」になるよう選択される。
【００２０】
この発明について、添付の図面を参照しながら以下に説明する。
この発明のシステムを、リードソロモンコードに関して以下に考察する。しかし、このシステムはＢＣＨコードとともに用いてもよい。以下に考察する加法および乗法の演算はガロア体演算である。
【００２１】
図１において、ＥＣＣエンコーダ１０は距離ｄリードソロモンＥＣＣに従ってデータを符号化し、データコードワードｃ（ｘ）を生成する。データコードワードはＸＯＲゲート１４に供給され、ＸＯＲゲートはコードワードに剰余類リーダｂi（ｘ）を付加する。以下により詳細に考察するとおり、ｄ′＜ｄであるとき、剰余類リーダはＥＣＣの距離ｄ′スーパーコードのコードワードであるが、距離ｄコードのコードワードではない。次いでその結果は、ディスクドライブ（図示せず）によって従来の手法により記録される。
【００２２】
図２に示されるとおり、後にコードワードを検索するときには、剰余類リーダをコードワードに対して再びＸＯＲ処理することによって、剰余類リーダがコードワードから取除かれる。次いでその結果はデコーダ１６によって、距離ｄＥＣＣに従って従来の手法でデコードされる。適切な場合には、デコーダ１６はデコードされたコードワードのエラーを訂正し、データを再生する。
【００２３】
検索されたコードワードが同期エラーを含むとき、検索されたコードワードに剰余類リーダを加えることによって、コードワードにさらなるエラーがもたらされる。以下に考察するように、ＸＯＲ処理演算が、検索されたコードワード中に距離ｄＥＣＣすべての有効なコードワードからのハミング距離ｄ′である項を含むように、剰余類リーダが選択される。コードワードにこの項が含まれることによって、同期エラーを起こしたコードワードのエラー数がＥＣＣが訂正できる数よりも大きくなり、したがってデコーダはこのデータを誤りとしてラベルする。
【００２４】
より特定的には、ＥＣＣエンコーダ１０によって生成されるデータコードワードは距離ｄリードソロモンコードのコードワードであって、ここではＲＳ［ｄ］コードとも呼ばれる。定義により、このデータコードワードは最小のハミング距離ｄによって互いに分離される。ＲＳ［ｄ］コードは、それぞれ最小ハミング距離２，３...，ｄ−１によって分離されるコードワードを有するコードＲＳ［２］,ＲＳ［３］...ＲＳ［ｄ−１］に含まれる。これらのＲＳ［ｄ′］コードは、すべての距離ｄコードワードと、その他の各コードワードからのより少ない距離ｄ′であるコードワードとを含むため、ＲＳ［ｄ］コードのスーパーコードである。
【００２５】
このシステムは、データコードワードｃ（ｘ）に対してＸＯＲ処理するために、ＲＳ［ｄ′］コードのコードワードであるがＲＳ［ｄ］コードのコードワードではない剰余類リーダｂi（ｘ）を選択する。したがってこのシステムはデータコードワードに対して、すべての有効なデータコードワードからのハミング距離ｄ′である項をＸＯＲ処理し、コードワードｃ（ｘ）＋ｂi（ｘ）＝ｗ（ｘ）を記録するために生成する。後にコードワードを検索するときには、剰余類リーダｂi（ｘ）をコードワードに対して再びＸＯＲ処理することによってこれを取除く。同期エラーがないとき、このシステムは次のデータコードワードを再生する。
【００２６】
【数７】
0004527255.tif 000004
【００２７】
しかし同期エラーがあるときには、後述のとおり、検索されたコードワードはＳシンボルによってタイミングを合せてシフトされ、ここで−Ｔ≦Ｓ≦Ｔであり、Ｔは同期エラーにおける最大シンボル数である。検索されたコードワードｃR（ｘ）は、シフトされ先端が削除されたバージョンの記録されたコードワードと、同期エラーの方向に依存して、記録されたコードワードシンボルに先行または後続するＳシンボルとを含む。したがって検索されたコードワードは項ｃr（ｘ）＝ＴＲＵＮＣＡＴＥ｛ｃ（ｘ）*ｘS＋ｂi（ｘ）*ｘS｝を含み、ここで関数ＴＲＵＮＣＡＴＥ｛  ｝は次の多項式に対して定められ、
【００２８】
【数８】
0004527255.tif 000005
【００２９】
ｘの正および負の累乗は、ｎがコードの長さであるとき、ＴＲＵＮＣＡＴＥ｛ｆ（ｘ）｝＝ｆn-1ｘn-1＋ｆn-2ｘn-2＋...＋ｆ1ｘ＋ｆ0である。
【００３０】
同期エラーを有する検索されたコードワードに対する剰余類リーダのＸＯＲ処理は、コードワードに次の項をもたらす。
【００３１】
【数９】
0004527255.tif 000006
【００３２】
したがってこのシステムは、対象となるすべてのＳ値に対して、ｊ（ｘ）＝ｂi（ｘ）*ｘS＋ｂi（ｘ）がＲＳ［ｄ］コードのコードワードではないことをテストし、この剰余類リーダが所望の同期エラー特性を与えることを確認する。先端を削除しないとき、同期エラーを有する検索されたコードワードに含まれる項は、すべての有効なデータコードワードからの距離ｄ′であり、それは同期エラーを有する検索されたコードワードｃR（ｘ）に、ＥＣＣが訂正できる以上のエラーをもたらす。以下により詳細に考察するとおり、特定の剰余類リーダを選択することによって、先端の削除が関連するハミング距離に与え得る悪影響を最小化してもよい。
【００３３】
ＲＳ［ｄ′］コードの生成多項式は、ＲＳ［ｄ］コードの生成多項式のｄ′要素を選択することによって定め得る。ｄ連続根αL，αL+1...αL+d-1を有する生成多項式ｇ（ｘ）を伴うＲＳ［ｄ］コードに対しては、システムはＲＳ［ｄ−１］コードの生成多項式ｇ′（ｘ）に対するｄ−１連続根を選択する（ステップ３００、３０２）。ｇ′（ｘ）の根は次の２つから選択される。すなわちαL+1，αL+2...αL+d-1およびαL，αL+1...αL+d-2である。次いでこのシステムはこれらのＲＳ［ｄ−１］コードの１つから、ＲＳ［ｄ］コードのコードワードではない剰余類リーダｂi（ｘ）を選択する（ステップ３０４）。
【００３４】
選択した剰余類リーダが同期エラーの検出に適しているかどうかを判断するためには、このシステムは次の項すなわち
【００３５】
【数１０】
0004527255.tif 000007
【００３６】
がＲＳ［ｄ］コードのコードワードではないことをテストする（ステップ３０６、３０８）。Ｓの値は−ＴからＴの範囲であり、ここでＴはディスク上に記録されている、同期パターンを見出すためにシステムが用いるウィンドウの大きさの最大値である。したがってシステムは、セクタ間に記録されたオーバーヘッド情報の両側の、最大Ｔのシンボルを見て同期パターンを見出す。パターンが見出されないときは、ディスクドライブ（図示せず）は典型的には読書きヘッドを再位置決めし、再びＴシンボルウィンドウ中の同期パターンをつきとめようとする。したがって読取操作は、どちらの方向にも最大Ｔシンボルによって同期エラーを起こし得る。
【００３７】
剰余類リーダｂi（ｘ）は、ＲＳ［ｄ］コードの生成多項式ｇ（ｘ）の根によって分割されることによりテストされる。どの根もｂi（ｘ）を分割しないとき、その剰余類リーダはＲＳ［ｄ］コードのコードワードではない。次にこのシステムは対象とする各Ｓに対する関連多項式ｊ（ｘ）を同様にテストする。
【００３８】
システムが選択したコードから適切な剰余類リーダを見出せないとき、システムは他のＲＳ［ｄ−１］コードからの剰余類リーダをテストする（ステップ３１０、３１２）。システムが適切な剰余類リーダを見出せないときは、システムは次にｄ−２連続根を伴う生成多項式を有するＲＳ［ｄ−２］コードからの剰余類リーダをテストし、以下同様にする（ステップＳ３１０、３１４）。
【００３９】
所与のＲＳ［ｄ′］コードに対する剰余類リーダは、ＲＳ［ｄ′］コードに従ってデータを符号化することにより任意のデータｐ（ｘ）から生成されてもよい。生成されたコードワードｃp（ｘ）は次いで前述のとおりテストされ、ＲＳ［ｄ］コードのコードワードであるかどうかが判断される。もしそうであれば、新しいコードワードがｃp（ｘ）＝ｃp（ｘ）＋ｘaｇ′（ｘ）として生成され、次いでそのコードワードがテストされる。必要に応じてシステムは次のコードワードｃp（ｘ）＝ｃp（ｘ）＋ｘa+1ｇ′（ｘ）を生成およびテストし、以下同様にする。
【００４０】
生成されたコードワードｃp（ｘ）がＲＳ［ｄ］コードのコードワードではないとき、システムはｂi（ｘ）＝ｃp（ｘ）を定め、ｂi（ｘ）＋ｂi（ｘ）*ｘSが、対象とするすべてのＳに対するＲＳ［ｄ］におけるコードワードであるかどうかをテストする。もしそうであれば、システムはデータｐ（ｘ）を修正して、新しいコードワードｃp（ｘ）を生成およびテストし、以下同様にする。一般的に、ｐ（ｘ）はすべてゼロにセットされる。
【００４１】
このアプローチを用いて剰余類リーダを生成すると、システムはすべての剰余類リーダを記憶する必要がある。必要とされる記憶量を減少させるために、システムはこの代わりにＲＳ［ｄ′］コードの短くされたコードワードを処理することによって剰余類リーダを生成してもよい。この場合システムは剰余類リーダ全体ではなく、短くされたコードワードを記憶する。
【００４２】
図４において、システムはＲＳ［ｄ′］コードのコードワードの、すべてゼロの先行シンボルを無視し、短くされたコードワードｍ（ｘ）*ｇ′（ｘ）から剰余類リーダを生成する（ステップ４００）。したがって剰余類リーダは
【００４３】
【数１１】
0004527255.tif 000008
【００４４】
となり、ここで（ステップ４０２）ｄ"はｍ（ｘ）*ｇ′（ｘ）の次数に等しいか、またはより大きくなるように選択され、ｄ"およびｐは本質的に剰余類リーダをデータコードワードの「中心」にするように選択され、ｎがコードの長さであるとき、ｐ＋ｒｄ"＋ｄ′−１≦ｎである。コードワードの開始からｐシンボルシフトされた剰余類リーダは、短くされたコードワードのｒ＋１個のコピーを含む。ｄ"がｍ（ｘ）*ｇ′（ｘ）＋１の次数よりも大きいとき、剰余類リーダ中のｍ（ｘ）*ｇ′（ｘ）のそれぞれのコピーの間に、ゼロに占められた間隙が存在する。ｐ＞Ｔであれば、剰余類リーダのシンボルは先端を削除されたシンボルに含まれないため、記録されたコードワードの先端削除は、項ｊ（ｘ）＝ｂi（ｘ）*ｘS＋ｂi（ｘ）がＲＳ［ｄ］コードの各々の有効なコードワードから分離される最小限の距離に悪影響を与えない。したがってすべてのコードワードからの距離ｄ′である、ここに含まれる項は、あらゆる検索されたコードワードに十分な数のエラーをもたらし、そのためにデコーダはこの同期エラーを起こしたデータを誤りとラベルするはずである。
【００４５】
多項式ｍ（ｘ）は規約多項式にセットされてもよく、ほとんどのアプリケーションにおいてｍ（ｘ）は１に等しくセットされてもよい。剰余類リーダは、短くしたコードワードをデータコードワードの適切なシンボルに対して繰返しＸＯＲ処理することによって生成できる。代替的には、図５の参照とともに以下に考察するとおり、剰余類リーダはシフトレジスタ中に生成されてもよい（ステップ４０４）。
【００４６】
その代わりに、システムは短くしたコードワードｍ（ｘ）*ｇ′（ｘ）にαeを乗ずることによって剰余類リーダを生成してもよい。図５に示されるとおり、その剰余類リーダすなわち
【００４７】
【数１２】
0004527255.tif 000009
【００４８】
は、線形シフトレジスタ１２eによって生成可能である。シフトレジスタ１２eは、多項式ｘp*ｍ（ｘ）*ｇ′（ｘ）の係数を含むｄ−１レジスタ３０と、レジスタの内容にαeを乗ずる定数乗算器３２とを含む。ｒおよびｅの値は好ましくはα(r+1)e＝１となるように選択され、したがってレジスタ３０の内容はｒ回の繰返しの後に初期状態に戻る。
【００４９】
乗算器３２がα0＝１にセットされるか、またはフィードバック経路から取除かれたとき、シフトレジスタ１２eを用いて、データコードワードに対するＸＯＲ処理のために項ｍ（ｘ）*ｇ′（ｘ）を繰返し供給してもよい。こうしてこのシフトレジスタを用いて、前述の剰余類リーダすなわち
【００５０】
【数１３】
0004527255.tif 000010
【００５１】
を生成できる。
その代わりに剰余類リーダは、各々の繰返しにおいて項ｘP*ｍ（ｘ）*ｇ′（ｘ）に異なる値のαjを乗ずることによって生成されてもよい。図６に示されるシフトレジスタ１２jは、前述のレジスタ３０と乗算器４２とを含み、この乗算器は各々の繰返しの後に更新されてたとえば次のものを生成する。
【００５２】
【数１４】
0004527255.tif 000011
【００５３】
したがって、乗算器４２は各々の繰返しの後αaからαa+1に更新される。
代替的には、図７に示されるように、システムは予め定められた初期状態にセットされた最大長のシフトレジスタ１２mを用いて剰余類リーダのデータ部分を生成してもよい。シフトレジスタ１２mは各々の繰返しでｍビットシンボルを生成し、シフトレジスタを繰返し用いて剰余類リーダのデータ部分におけるすべてのシンボルを生成できる。シフトレジスタは、データシンボルの数よりも大きい周期を有する多項式に従ってセットアップされる。図面に示されるとおり、レジスタ１２mは多項式ｘ2＋αjｘ＋αjに従ってセットアップされる２段のシフトレジスタであってもよく、ここでαjはガロア体の初期要素である。
【００５４】
しかしこのシステムは剰余類リーダ冗長シンボルを記憶するため、ＲＳ［ｄ′］コードに対する別個のエンコーダは不必要である。またこのシステムは、シフトレジスタの初期状態と、必要とされる繰返しの数とを記憶しなければならない。
【００５５】
いくつかのアプリケーションに対しては、剰余類リーダは、データコードワードの冗長シンボルに対してのみＸＯＲ処理された、短くされたコードワードである。これらのアプリケーションのほとんどに対して、剰余類リーダはｘpｇ′（ｘ）であり、ここでｐの値は剰余類リーダを冗長シンボルの中心にするよう選択される。したがってこのシステムはｇ′（ｘ）のみを記憶する。
【００５６】
前述のシステムおよび方法は、検索されたコードワード中に、すべての有効なデータコードワードからの選択された距離である項を含む。これは、試行錯誤によって見出され必ずしもすべての有効なデータコードワードから選択された距離だけ離れていない、先行システムによって用いられるノイズ様シーケンスと対照的である。
【００５７】
さらに現行システムの剰余類リーダは、ＲＳ［ｄ′］コードの短くされたコードワードから生成したり、または線形シフトレジスタを用いて生成したりすることもできる。このことにより、すべてのシーケンスを記憶する必要がある先行システムよりも、必要とされる記憶量を減少することができる。
【図面の簡単な説明】
【図１】  この発明に従って構成された、符号化システムの機能ブロック図である。
【図２】  この発明に従って構成された、デコードシステムの機能ブロック図である。
【図３】  剰余類リーダを選択する演算の流れ図である。
【図４】  剰余類リーダを選択するさらなる演算の流れ図である。
【図５】  剰余類リーダを生成するためのシフトレジスタの機能ブロック図である。
【図６】  剰余類リーダを生成するための代替的なシフトレジスタの機能ブロック図である。
【図７】  剰余類リーダを生成するための最大長のシフトレジスタの機能ブロック図である。
【符号の説明】
１０  ＥＣＣエンコーダ、１２  剰余類リーダエンコーダ、１４  ＸＯＲゲート。
【図１】
0004527255.tif 000016
【図２】
0004527255.tif 000017
【図３】
0004527255.tif 000018
【図４】
0004527255.tif 000019
【図５】
0004527255.tif 000020
【図６】
0004527255.tif 000021
【図７】
0004527255.tif 000022