(57)【特許請求の範囲】
【請求項１】
ディスク記憶媒体から読み出されたランダム化されたデータ中の誤りを訂正する誤り訂正プロセッサであって、該ランダム化されたデータは、第１および第２の組の交差する符号語と、該ランダム化されたデータに対して生成されたＥＣＣ冗長記号と、ランダム化される前のデータに対して生成されたチェック記号とを含み、該ランダム化されたデータは、疑似ランダムデータシーケンス多項式を用いてデータをランダム化することによって生成されており、該チェック記号は、有限領域の生成器多項式に従って生成されており、該誤り訂正プロセッサは、
（ａ）該ＥＣＣ冗長記号を用いて、該ランダム化されたデータ中の誤りを訂正するためのＥＣＣ復号化器と、
（ｂ）該ランダム化されたデータを受信したことに応答して、（ｉ）該第１の組の符号語に対する第１のパスの間にデータ検証シンドロームを生成することと、（ｉｉ）該ランダム化されたデータを訂正するために該ＥＣＣ復号化器によって生成された訂正値を用いて、誤り検証シンドロームを生成することと、（ｉｉｉ）該データ検証シンドロームを該誤り検証シンドロームと結合して、最終検証シンドロームを生成することとにより、最終検証シンドロームを生成するためのシンドローム生成器と、
（ｃ）該最終検証シンドロームを所定の値と比較して、該ランダム化されたデータに対する訂正の有効性および完全性を検証するための訂正検証器であって、該所定の値は、該生成器多項式に対する該疑似ランダムデータシーケンス多項式の剰余除算である、訂正検証器と、
（ｄ）該訂正検証器が、該ランダム化されたデータに対する訂正が有効かつ完全であることを示した後、該ランダム化されたデータを非ランダム化するための非ランダム化器と
を含む、誤り訂正プロセッサ。
【請求項２】
前記ＥＣＣ復号化器が、前記第１の組の符号語および前記第２の組の符号語をシーケンシャルなパスで処理することによって、前記ランダム化されたデータ中の誤りを訂正する、請求項１に記載の誤り訂正プロセッサ。
【請求項３】
（ａ）前記ＥＣＣ復号化器が前記ランダム化されたデータを処理するのと同時に、前記シンドローム生成器が部分検証シンドロームを生成し、
（ｂ）該シンドローム生成器が、該ＥＣＣ復号化器によって処理されている特定のランダム化されたデータ記号の位置に応じて該部分検証シンドロームを調整するためのオフセットコントローラを含む、請求項２に記載の誤り訂正プロセッサ。
【請求項４】
前記ＥＣＣ復号化器が、ランダム化されたデータ記号を訂正するための訂正値を生成するときに、
（ａ）前記オフセットコントローラが、前記訂正されたデータ記号の位置に応じて前記部分検証シンドロームを調整し、
（ｂ）前記シンドローム生成器が、該訂正値を用いて該部分検証シンドロームを更新する、請求項３に記載の誤り訂正プロセッサ。
【請求項５】
前記オフセットコントローラが、前記部分検証シンドロームにＸＫｍｏｄＧ（ｘ）を掛けることによって該部分検証シンドロームを調整し、Ｋはオフセット値であり、ｍｏｄ演算子は剰余除算を行う、請求項３に記載の誤り訂正プロセッサ。
【請求項６】
（ａ）前記非ランダム化器が、所定のシード値に従ってランダムパターンを生成し、
（ｂ）該ランダムパターンが、前記ランダム化されたデータと結合されて、該ランダム化されたデータを非ランダム化する、請求項１に記載の誤り訂正プロセッサ。
【請求項７】
前記チェック記号が、巡回冗長符号（ＣＲＣ）に従って生成される、請求項１に記載の誤り訂正プロセッサ。
【請求項８】
ディスク記憶媒体から読み出されたランダム化されたデータ中の誤りを訂正する方法であって、該ランダム化されたデータは、第１および第２の組の交差する符号語と、該ランダム化されたデータに対して生成されたＥＣＣ冗長記号と、ランダム化される前のデータに対して生成されたチェック記号とを含み、該ランダム化されたデータは、疑似ランダムデータシーケンス多項式を用いてデータをランダム化することによって生成されており、該チェック記号は、有限領域の生成器多項式に従って生成されており、該方法は、
（ａ）該ＥＣＣ冗長記号を用いて、該ランダム化されたデータ中の誤りを訂正するステップと、
（ｂ）該ランダム化されたデータを受信したことに応答して、（ｉ）該第１の組の符号語に対する第１のパスの間にデータ検証シンドロームを生成することと、（ｉｉ）該ランダム化されたデータを訂正するためにＥＣＣ復号化器によって生成された訂正値を用いて、誤り検証シンドロームを生成することと、（ｉｉｉ）該データ検証シンドロームを該誤り検証シンドロームと結合して、最終検証シンドロームを生成することとにより、最終検証シンドロームを生成するステップと、
（ｃ）該最終検証シンドロームを所定の値と比較して、該ランダム化されたデータに対する訂正の有効性および完全性を検証するステップであって、該所定の値は、該生成器多項式に対する該疑似ランダムデータシーケンス多項式の剰余除算である、ステップと、
（ｄ）訂正検証器が、該ランダム化されたデータに対する訂正が有効かつ完全であることを示した後に、該ランダム化されたデータを非ランダム化するステップと
を包含する、方法。
【請求項９】
前記訂正するステップは、前記第１の組の符号語および前記第２の組の符号語をシーケンシャルなパスで処理することによって、前記ランダム化されたデータ中の誤りを訂正する、請求項８に記載の誤りを訂正する方法。
【請求項１０】
前記検証シンドロームを生成するステップが、
（ａ）前記ランダム化されたデータを処理してＥＣＣ誤りシンドロームを生成するのと同時に、部分検証シンドロームを生成するステップと、
（ｂ）該ＥＣＣ誤りシンドロームを生成するために処理されている特定のランダム化されたデータ記号の位置に応じて該部分検証シンドロームを調整するステップと
を包含する、請求項９に記載の誤りを訂正する方法。
【請求項１１】
前記検証シンドロームを生成するステップが、
（ａ）訂正されたデータ記号の位置に応じて前記部分検証シンドロームを調整するステップと、
（ｂ）前記データ記号を訂正するために用いられる前記訂正値で、該部分検証シンドロームを更新するステップと
をさらに包含する、請求項１０に記載の誤りを訂正する方法。
【請求項１２】
前記部分検証シンドロームを調整するステップが、該部分検証シンドロームにＸＫｍｏｄＧ（ｘ）を掛けるステップを包含し、Ｋはオフセット値であり、ｍｏｄ演算子は剰余除算を行う、請求項１０に記載の誤りを訂正する方法。
【請求項１３】
（ａ）非ランダム化器が、所定のシード値に従ってランダムパターンを生成し、
（ｂ）該ランダムパターンが、前記ランダム化されたデータと結合されて、該ランダム化されたデータを非ランダム化する、請求項８に記載の誤りを訂正する方法。
【請求項１４】
前記チェック記号が、巡回冗長符号（ＣＲＣ）に従って生成される、請求項８に記載の誤りを訂正する方法。
【請求項１５】
ディスク記憶媒体から読み出されたデータ中の誤りを訂正する誤り訂正プロセッサであって、該データは、第１および第２の組の交差する符号語と、ＥＣＣ冗長記号と、チェック記号とを含み、該データは、疑似ランダムデータシーケンス多項式を用いてランダム化されており、該チェック記号は、有限領域の生成器多項式に従って生成されており、該誤り訂正プロセッサは、
（ａ）該ＥＣＣ冗長記号を用いて、該データ中の誤りを訂正するためのＥＣＣ復号化器と、
（ｂ）該データを受信したことに応答して、（ｉ）該第１の組の符号語に対する第１のパスの間にデータ検証シンドロームを生成することと、（ｉｉ）該データを訂正するために該ＥＣＣ復号化器によって生成された訂正値を用いて、誤り検証シンドロームを生成することと、（ｉｉｉ）該データ検証シンドロームを該誤り検証シンドロームと結合して、最終検証シンドロームを生成することとにより、最終検証シンドロームを生成するためのシンドローム生成器と、
（ｃ）該最終検証シンドロームを所定の値と比較して、該データに対する訂正の有効性および完全性を検証するための訂正検証器であって、該所定の値は、該生成器多項式に対する該疑似ランダムデータシーケンス多項式の剰余除算である、訂正検証器と、
（ｄ）該訂正検証器が、該ランダム化されたデータに対する訂正が有効かつ完全であることを示した後、該データを非ランダム化するための非ランダム化器と
を含む、誤り訂正プロセッサ。
【請求項１６】
ディスク記憶媒体から読み出されたランダム化されたデータ中の誤りを訂正する誤り訂正プロセッサであって、該ランダム化されたデータは、第１および第２の組の交差する符号語と、該ランダム化されたデータに対して生成されたＥＣＣ冗長記号と、ランダム化される前のデータに対して生成されたチェック記号とを含み、該ランダム化されたデータは、疑似ランダムデータシーケンス多項式を用いてデータをランダム化することによって生成されており、該チェック記号は、有限領域の生成器多項式に従って生成されており、該誤り訂正プロセッサは、
（ａ）該ディスクから読み出された該ランダム化されたデータを格納するためのデータバッファと、
（ｂ）該データバッファから該ランダム化されたデータを受け取るように接続されたＥＣＣ復号化器であって、該ランダム化されたデータ中の誤りを訂正するための訂正値およびＥＣＣ誤りシンドロームを生成するためのＥＣＣ復号化器と、
（ｃ）該ＥＣＣ復号化器が該データバッファから該ランダム化されたデータを受け取るのと同時に該データバッファから該ランダム化されたデータを受け取るように接続されたシンドローム生成器であって、（ｉ）該第１の組の符号語に対する第１のパスの間にデータ検証シンドロームを生成することと、（ｉｉ）該ランダム化されたデータを訂正するために該ＥＣＣ復号化器によって生成された訂正値を用いて、誤り検証シンドロームを生成することと、（ｉｉｉ）該データ検証シンドロームを該誤り検証シンドロームと結合して、最終検証シンドロームを生成することとにより、最終検証シンドロームを生成するシンドローム生成器と、
（ｄ）該最終検証シンドロームを所定の値を比較して、該ランダム化されたデータに対する訂正の有効性および完全性を検証するための訂正検証器であって、該所定の値は、該生成器多項式に対する該疑似ランダムデータシーケンス多項式の剰余除算である、訂正検証器と、
（ｅ）該データバッファから該ランダム化されたデータを受け取るように接続された非ランダム化器であって、該訂正検証器が、該ランダム化されたデータに対する訂正が有効かつ完全であることを示した後、該ランダム化されたデータを非ランダム化するための非ランダム化器と
を含む、誤り訂正プロセッサ。
【請求項１７】
前記検証シンドロームが、巡回冗長符号（ＣＲＣ）に従って生成される、請求項１６に記載の誤り訂正プロセッサ。
【請求項１８】
前記シンドローム生成器が、ランダム化されたデータ記号が訂正されるときに前記ＥＣＣ復号化器によって生成される訂正値を用いて、前記検証シンドロームを更新する、請求項１６に記載の誤り訂正プロセッサ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ記憶装置のための誤り訂正システムに関し、特に、書込み動作中にデータがランダム化される前に巡回冗長検査（ＣＲＣ）シンボルが生成されるときの、ランダムデータに対してＣＲＣを実施することによって、積符号などの多次元符号に対する訂正の有効性および完全性を証明するための効率的な方法および装置に関する。
【０００２】
【従来の技術】
コンピュータ記憶装置（磁気ディスクドライブおよび光ディスクドライブ）において、記録チャネルの帯域幅は、信号パワーと同様に限定される。性能利得を成し遂げるために、様々な符号化技術を用いてシステムのノイズに対する免疫を高めることによって効果的な信号対ノイズ比（ＳＮＲ）を増加させている。このため、任意の低ビット誤り率を維持しながら記憶密度を増加させることによって、記憶容量を増加させることが可能となる。
【０００３】
現在、記録装置において用いられている符号には一般に２つのタイプがある。チャネル符号および誤り訂正符号（ＥＣＣ）である。チャネル符号は、記録チャネルの特定の特徴によって引き起こされるノイズに対するものである。例えば、ランレングス限定（ＲＬＬ）符号は、アナログ搬送波信号におけるデータシンボルを示すパルス間の最小スペーシングを限定することによって、ノイズをシンボル間干渉に減衰するように設計されたチャネル符号である。記録されるデータのスペクトル内容は、読返し時にデータを正確に検出するシステムの能力にも悪影響を与え得る。この結果、いくつかのデータシーケンスは、他のデータシーケンスよりも検出が困難となり得る。この現象を考慮するために、通常、データをランダム化するためのチャネル符号が、記録装置において用いられている。このような記録装置は、データをディスク記憶媒体に書き込む前にランダム化することによってデータを効果的に「不透明にする（whiten）」する。読み返し時に、記録チャネルは、データがランダム化されない場合よりも低いビット誤り率でランダムデータを検出することができる。記憶媒体から読み出されたデータは、ホストに転送される前に非ランダム化される。
【０００４】
誤り訂正コーディング（ＥＣＣ）において、記録されるバイナリデータは、数学的に処理され、データに追加される冗長シンボルを生成し、ディスク記憶媒体に書き込まれる符号語を形成する。読み返し時には、記録された符号ワードは、読出し信号から評価（検出）され、冗長シンボルは、評価された符号ワードを最初に記録されたユーザデータに復号化するために用いられる。実際、冗長シンボルは、符号ワードが記録チャネルを通過するときに、符号ワードをノイズから保護するバッファを提供する。十分なノイズがこのバッファに「浸透（penetrate）」すると、ノイズは、書き込まれた符号ワードを異なる受信符号ワードに変化させ、この結果、ユーザデータに復号化されるときに誤りを生じる。
【０００５】
誤り訂正符号においてより多くの冗長シンボルが用いられるほど、符号語の周囲のバッファは大きくなり、復号化誤りが発生する前に耐えられ得るノイズが多くなる。しかし、任意の低ビット誤り率を維持しながら所定のチャネルに対して達成可能な最大ユーザデータ転送率（または記録密度）を指す「チャネル容量」として公知の任意の所定の記録チャネルの性能には上限がある。最終的には、チャネル容量は、チャネル帯域幅および信号対ノイズ（ＳＮＲ）比の関数である。上記のように、チャネル符号および誤り訂正符号は、効果的なＳＮＲを増加させることによって性能を向上させる手段である。
【０００６】
記録チャネルの信頼性および効率を最大にするために、ユーザデータを符号化／復号化するための解決法が多数ある。最終目標は、実現を簡単にし、コストを下げると共に、チャネル容量に近づくシステムを設計することである。ブロック誤り訂正符号、特に、リード−ソロモンブロック符号は、その優れた誤り訂正特性および実現コストおよび複雑性が低いことにより、通常、ディスク記憶システムにおいて用いられる。
【０００７】
ブロック符号は、ソースデータストリームのｋシンボル入力ブロックを、ｎシンボル出力ブロックまたは符号語に符号化する。ここで、ｎ−ｋは、冗長シンボルの数である、ｋ／ｎは、符号率と呼ぶ。次に、符号語は、通信媒体を通して転送され（通信媒体に記憶され）、受信器によって復号化される。符号化プロセスは、入力ブロックに対して数学演算を行い、出力符号語は、符号ｄminの最小距離として参照されるパラメータによって他の符号語とは異なったものにされる。符号語間の最小距離ｄminは、システムが、受信された符号語が誤って復号化される前の耐え得るノイズの量を決定する。
【０００８】
リード−ソロモン符号では、データストリームは、シンボルのシーケンスとして処理され、シンボルは、典型的には、有限フィールドＧＦ（２w）から選択される。パラメータｗは、シンボル当たりのバイナリデータビットの数を示す。ｋシンボル入力ブロックの各シンボルは、データ多項式Ｄ（ｘ）の係数を示す。次に、冗長シンボル（多項式Ｗ（ｘ）とも呼ぶ）は、生成器多項式Ｇ（ｘ）によって除算される入力データ多項式Ｄ（ｘ）の剰余除算として計算される。
【０００９】
【数１】
0004346135.tif 000002
ここで、ｍは、冗長シンボルの数と等しい生成器多項式の次数である。次に、冗長多項式Ｗ（ｘ）は、データ多項式Ｄ（ｘ）に加えられ、符号語多項式Ｃ（ｘ）を生成する。
【００１０】
【数２】
0004346135.tif 000003
当業者には言うまでもなく、上記の動作を行う符号化器回路は、リニアフィードバックシフトレジスタ（ＬＦＳＲ）を用いて最小のコストで実現され得る。
【００１１】
符号化の後、符号語Ｃ（ｘ）は、ノイズ通信チャネルを通して転送され、受信された符号語Ｃ’（ｘ）は、転送された符号語Ｃ（ｘ）に誤り多項式Ｅ（ｘ）を加えたものと等しくなる。受信された符号語Ｃ’（ｘ）は、以下のステップに従って訂正される。（１）誤りシンドロームＳiを計算する。（２）誤りシンドロームＳｉを用いて誤りロケータ多項式の係数を計算する。（３）誤りロケータ多項式のルートを計算する。ルートの対数は、誤り位置Ｌiである。（４）誤りシンドロームＳiおよび誤りロケータ多項式のルートを用いて誤り値を計算する。
【００１２】
誤りシンドロームＳｉは、生成器多項式Ｇ（ｘ）の因数によって除算される受信符号語多項式Ｃ’（ｘ）の剰余除算として計算される。
【００１３】
【数３】
0004346135.tif 000004
このとき
【００１４】
【数４】
0004346135.tif 000005
であり、ここで、αは、有限フィールドＧＦ（２w）の基本要素である。復号化プロセスの他のステップを実施し、誤りロケータ多項式を計算し、誤りロケータ多項式のルートを計算し、誤り値を計算する技術は、当業者により周知であり、本発明を理解するために必要ではない。例えば、「COEFFICIENT UPDATING METHOD AND APPARATUS FOR REED-SOLOMON DECODER」という名称の下記で参照する米国特許第５，４４６，７４３号を参照のこと。
【００１５】
誤り許容度をさらに増加させるための当該技術分野で公知の他の技術としては、符号語を、多次元または積符号として知られるものに改作することが挙げられる。ディジタルビデオディスク（ＤＶＤ）記憶システムは、例えば、一般に、図３Ａに示す二次元積符号を用いる。符号語は、交差する水平（行またはＱ）および垂直（列またはＰ）符号語に改作され、復号化プロセスは、反復パスにおいて実行される。まず、水平符号語に対してパスが行われ、できるだけ多くの誤りが訂正される。訂正不可能な水平符号語はすべて、変更されずに残される。次に、垂直符号語に対してパスが行われ、できるだけ多くの誤りが訂正される。ここで、垂直符号語において訂正されるシンボルもまた、交差する水平符号語に対する対応のシンボルを訂正する。この結果、水平符号語は、次の水平パスにおいて訂正可能となり得る。同様に、水平パスにおいて訂正されるシンボルは、前回訂正不可能であった垂直符号語を、次の垂直パスにおいて訂正可能にし得る。この反復プロセスは、全積符号が訂正されるか、または訂正不可能になるまで続行される。
【００１６】
図３Ａの二次元積符号はさらに、行および列符号語に対する訂正の有効性を検査するのに用いられるＣＲＣ冗長シンボルを有する。ＣＲＣ冗長は、典型的には、以下の式に従ってユーザデータを処理することによって生成される。
【００１７】
【数５】
0004346135.tif 000006
ここで、Ｐ（ｘ）は、有限フィールドＧＦ（２m）における係数を有する多項式として示されるユーザデータであり、ｎ−ｋは、ＣＲＣ冗長シンボルの数であり、Ｇ（ｘ）は、生成器多項式である。次に、ＣＲＣ冗長は、得られる符号語Ｃ（ｘ）がディスクに書き込まれる前にユーザデータに追加される。読出し動作中、ディスクから読み出されたデータは、以下の式に従って処理され、ＣＲＣシンドロームＳCRCを生成する。
【００１８】
【数６】
0004346135.tif 000007
ここで、Ｃ’（ｘ）は、ディスクから読み出された（ＣＲＣ冗長を含む）受信符号語多項式である。符号語Ｃ’（ｘ）に誤りがない場合、シンドロームＳCRCはゼロになる。
【００１９】
ＣＲＣ冗長は、典型的には、ＥＣＣ冗長シンボルを符号化する前に書込み動作中にデータに対して生成され、ＣＲＣシンドロームは、ＥＣＣ冗長が積符号を訂正するために用いられた後、読出し動作中に生成される。このように、ＣＲＣシンドロームは、訂正を検証し、訂正ミスを検出するように動作する。これは、非常に重要な機能である。なぜなら、この機能によって、誤り訂正システムが、「悪いデータ」がホストシステムを通過することを防止するためである。
【００２０】
図１は、ＣＤ／ＤＶＤ光ディスク記憶システムにおいて典型的に見いだされる従来の誤り訂正システムの概観を示す。書込み動作中（装置は読出し専用でないと仮定する）、ホストシステムから受信されたユーザデータは、データバッファ１に記憶される。次に、ＣＲＣ生成器および訂正検証器２は、ユーザデータをバッファからライン３を介して読み出し、ＣＲＣ冗長シンボルを生成し、冗長シンボルが追加されたユーザデータをデータバッファ１に再び記憶する。その後、データ（ＣＲＣ冗長を含む）は、データバッファ１から再び読み出され、データランダム化器４によってランダム化にされ、ランダムデータは、データバッファ１に再び記憶される。次に、Ｐ／Ｑ符号化器／復号化器５は、データバッファ１からランダムデータを読み出し、ＥＣＣ／シンドローム生成器１２は、ＰおよびＱ符号語に対してＥＣＣ冗長シンボルを生成し、図３Ａに示す二次元積符号を形成する。個別のＰおよびＱ符号語は、ＥＣＣ冗長シンボルを追加した後、データバッファ１に再び記憶される。全積符号が生成されると、全積符号は、データバッファ１から読み出され、光記憶媒体６に書き込まれる。
【００２１】
システムが、コンパクトディスク（ＣＤ）データフォーマット用に構成される場合、Ｃ１およびＣ２として参照されるさらなる冗長が生成され、データがディスクに書き込まれる前に、データに追加される。従って、ＣＤ記録フォーマットを容易にするために、誤り訂正システムは、Ｃ１符号化器／復号化器７、Ｃ２符号化器／復号化器８、および周知のクロスインターリーブリード−ソロモン符号（ＣＩＲＣ）を実現するためのインターリーブ器／非インターリーブ器９を有する。典型的には、スタティックＲＡＭ（ＳＲＡＭ）１０は、ＣＩＲＣコーディングプロセスを実現するために用いられ、ＳＲＡＭは、ダイナミックＲＡＭ（ＤＲＡＭ）よりもはるかに速く、後者は、データバッファ１を実現するために用いられる。
【００２２】
読出し動作中、プロセスは逆に進行する。ＣＤフォーマット用に構成する場合、Ｃ１およびＣ２復号化器は、ランダムデータが光ディスク６から読み出され、データバッファ１に記憶されるときに、ランダムデータに予め訂正を行う。完全な積符号が、データバッファ１で利用できるようになると、Ｐ／Ｑ復号化器５は、ＰおよびＱ符号語に対して反復パスを開始し、さらなる訂正を行う。ＥＣＣ／シンドローム生成器は、ライン１３を介して誤り訂正器１４に転送されるＥＣＣシンドロームを生成する。誤り訂正器は、ＥＣＣシンドロームを用いて、上記のように、個々の符号語における誤りを訂正する。ＰまたはＱパスの終わりには、ＥＣＣ誤りシンドロームはすべてゼロになり、これは、積符号が、（訂正ミスがなければ）誤りを含まないことを意味し、ランダムデータは、データバッファ１から読み出され、非ランダム化器４よって非ランダム化される。データが非ランダム化される間、ＣＲＣ生成器および訂正検証器２によって処理され、ＣＲＣシンドロームを生成する。ＣＲＣシンドロームがゼロである場合、これは、ＰおよびＱ符号語に対する訂正は有効かつ完了していることを意味し、データは、再び、データバッファ１から読み出され、非ランダム化され、非ランダム化されたデータは、ホストシステムに転送される。ＣＲＣシンドロームがゼロでない場合、これは、積符号の訂正ミスがあったことを示し、ＣＲＣ生成器および訂正検証器２は、誤りメッセージをライン１１を介してホストシステムに転送し、ホストシステムは、再試行動作（即ち、ディスクからデータを再び読み出す試み）を開始する。
【００２３】
【発明が解決しようとする課題】
図１に示す従来の誤り訂正システムの基本的な欠点は、データが、ＣＲＣ検証ステップを実施する前に、非ランダム化されなければならないことである。このためには、上記のように全積符号を読み出し、データを非ランダム化し、ＣＲＣシンドロームを生成するためにさらにバッファにアクセスしなければならない。明らかに、これは、記憶システムの待ち時間を増加させ、特に、円滑で中断されない性能を成し遂げるために、音声／映像データの大きなブロックが、連続したストリームにおいて記憶システムから読み出されなければならないマルチメディアアプリケーションにはあまり望ましくない。
【００２４】
従って、検証シンボルがランダム化の前に生成され、ＥＣＣシンボルがランダム化の後に生成されるときの、ＣＤ／ＤＶＤ積符号などの多次元符号に対する訂正の有効性および完全性の証明に関連する待ち時間を避けるコンピュータ記憶装置における誤り訂正システムが求められている。
【００２５】
【課題を解決するための手段】
本発明による誤り訂正プロセッサは、ディスク記憶媒体から読み出されたランダム化されたデータ中の誤りを訂正するための誤り訂正プロセッサであって、該ランダム化されたデータは、該ランダム化されたデータに対して生成されたＥＣＣ冗長記号と、ランダム化される前のデータに対して生成されたチェック記号とを含み、該誤り訂正プロセッサは、（ａ）該ＥＣＣ冗長記号を用いて、該ランダム化されたデータ中の誤りを訂正するためのＥＣＣ復号化器と、（ｂ）該ランダム化されたデータに応答して、検証シンドロームを生成するためのシンドローム生成器と、（ｃ）該検証シンドロームを所定の値と比較して、該ランダム化されたデータに対する訂正の有効性（validity）および完全性を検証するための訂正検証器と、（ｄ）該訂正検証器が、該ランダム化されたデータに対する訂正が有効で且つ完全であることを示した後、該ランダム化されたデータを非ランダム化するための非ランダム化器とを含んでおり、これにより上記目的が達成される。
【００２６】
（ａ）前記ランダム化されたデータが、交差する符号語の第１および第２の組を含み、（ｂ）前記ＥＣＣ復号化器が、該第１の組の符号語および該第２の組の符号語をシーケンシャルなパス（pass）で処理することによって、該ランダム化されたデータ中の誤りを訂正してもよい。
【００２７】
（ａ）前記シンドローム生成器が、前記第１の組の符号語に対する第１のパスの間にデータ検証シンドロームを生成し、（ｂ）該シンドローム生成器が、前記ランダム化されたデータを訂正するために前記ＥＣＣ復号化器によって生成される訂正値を用いて、誤り検証シンドロームを生成し、（ｃ）該シンドローム生成器が、該データ検証シンドロームを該誤り検証シンドロームと結合して、前記所定の値と比較される最終検証シンドロームを生成してもよい。
【００２８】
（ａ）前記ＥＣＣ復号化器が前記ランダム化されたデータを処理するのと同時に、前記シンドローム生成器が部分検証シンドロームを生成し、（ｂ）該シンドローム生成器が、該ＥＣＣ複号化器によって処理されている特定のランダム化されたデータ記号の位置に応じて、該部分検証シンドロームを調整するためのオフセットコントローラを含んでいてもよい。
【００２９】
前記ＥＣＣ復号化器が、ランダム化されたデータ記号を訂正するための訂正値を生成し、（ａ）前記オフセットコントローラが、前記訂正されたデータ記号の位置に応じて前記部分検証シンドロームを調整し、（ｂ）前記シンドローム生成器が、該訂正値を用いて該部分検証シンドロームを更新してもよい。
【００３０】
（ａ）前記チェック記号が、有限領域の生成多項式Ｇ（ｘ）に従って生成され、（ｂ）前記オフセットコントローラが、前記部分検証シンドロームにＸK ｍｏｄＧ（ｘ）を掛けることによって該部分検証シンドロームを調整し、ここで、Ｋはオフセット値であり、ｍｏｄ演算子は剰余除算（modulo division）を行ってもよい。
【００３１】
（ａ）前記チェック記号が、有限領域の生成多項式に従って生成され、（ｂ）前記所定の値が、該生成多項式に基づいてもよい。
【００３２】
（ａ）前記非ランダム化器が、所定のシード（seed）値に従ってランダムパターンを生成し、（ｂ）該ランダムパターンが、前記ランダム化されたデータと結合されて、該ランダム化されたデータを非ランダム化してもよい。
【００３３】
（ａ）前記チェック記号が、有限領域の生成多項式に従って生成され、（ｂ）前記所定の値が、該生成多項式および前記ランダムパターンに基づいてもよい。
【００３４】
前記チェック記号が、巡回冗長符号（ＣＲＣ）に従って生成されてもよい。
【００３５】
本発明による方法は、ディスク記憶媒体から読み出されたランダム化されたデータ中の誤りを訂正する方法であって、該ランダム化されたデータは、該ランダム化されたデータに対して生成されたＥＣＣ冗長記号と、ランダム化される前のデータに対して生成されたチェック記号とを含み、該方法は、（ａ）該ＥＣＣ冗長記号を用いて、該ランダム化されたデータ中の誤りを訂正するステップと、（ｂ）該ランダム化されたデータに応答して、検証シンドロームを生成するステップと、（ｃ）該検証シンドロームを所定の値と比較して、該ランダム化されたデータに対する訂正の有効性および完全性を検証するステップと、（ｄ）該訂正検証器が、該ランダム化されたデータに対する訂正が有効で且つ完全であることを示した後に、該ランダム化されたデータを非ランダム化するステップとを包含しており、これにより、上記目的が達成される。
【００３６】
（ａ）前記ランダム化されたデータが、交差する符号語の第１および第２の組を含み、（ｂ）前記訂正するステップは、該第１の組の符号語および該第２の組の符号語をシーケンシャルなパスで処理することによって、該ランダム化されたデータ中の誤りを訂正してもよい。
【００３７】
前記検証シンドロームを生成するステップが、（ａ）前記第１の組の符号語に対する第１のパスの間にデータ検証シンドロームを生成するステップと、（ｂ）前記ランダム化されたデータを訂正するための訂正値を用いて、誤り検証シンドロームを生成するステップと、（ｃ）該データ検証シンドロームを該誤り検証シンドロームと結合して、前記所定の値と比較される最終検証シンドロームを生成するステップとを包含してもよい。
【００３８】
前記検証シンドロームを生成するステップが、（ａ）前記ランダム化されたデータを処理してＥＣＣ誤りシンドロームを生成するのと同時に、部分検証シンドロームを生成するステップと、（ｂ）該ＥＣＣ誤りシンドロームを生成するために処理されている特定のランダム化されたデータ記号の位置に応じて、該部分検証シンドロームを調整するステップとを包含してもよい。
【００３９】
前記検証シンドロームを生成するステップが、（ａ）訂正されたデータ記号の位置に応じて前記部分検証シンドロームを調整するステップと、（ｂ）前記データ記号を訂正するために用いられる前記訂正値で、該部分検証シンドロームを更新するステップとをさらに包含してもよい。
【００４０】
（ａ）前記チェック記号が、有限領域の生成多項式Ｇ（ｘ）に従って生成され、（ｂ）前記部分検証シンドロームを調整する前記ステップが、該部分検証シンドロームにＸK ｍｏｄＧ（ｘ）を掛けるステップを包含し、ここで、Ｋはオフセット値であり、ｍｏｄ演算子は剰余除算を行ってもよい。
【００４１】
（ａ）前記チェック記号が、有限領域の生成多項式に従って生成され、（ｂ）前記所定の値が、該生成多項式に基づいてもよい。
【００４２】
（ａ）前記非ランダム化器が、所定のシード値に従ってランダムパターンを生成し、（ｂ）該ランダムパターンが、前記ランダム化されたデータと結合されて、該ランダム化されたデータを非ランダム化してもよい。
【００４３】
（ａ）前記チェック記号が、有限領域の生成多項式に従って生成され、（ｂ）前記所定の値が、該生成多項式および前記ランダムパターンに基づいてもよい。
【００４４】
前記チェック記号が、巡回冗長符号（ＣＲＣ）に従って生成されてもよい。
【００４５】
本発明による別の誤り訂正プロセッサは、ディスク記憶媒体から読み出されたデータ中の誤りを訂正するための誤り訂正プロセッサであって、該データは、ＥＣＣ冗長記号とチェック記号とを含み、該誤り訂正プロセッサは、（ａ）該ＥＣＣ冗長記号を用いて、該データ中の誤りを訂正するためのＥＣＣ復号化器と、（ｂ）該データに応答して、検証シンドロームを生成するためのシンドローム生成器と、（ｃ）該検証シンドロームを所定の値と比較して、該データに対する訂正の有効性および完全性を検証するための訂正検証器と、（ｄ）該訂正検証器が、該ランダム化されたデータに対する訂正が有効で且つ完全であることを示した後、該データを非ランダム化するための非ランダム化器とを含んでおり、これにより上記目的が達成される。
【００４６】
本発明による別の誤り訂正プロセッサは、ディスク記憶媒体から読み出されたランダム化されたデータ中の誤りを訂正するための誤り訂正プロセッサであって、該ランダム化されたデータは、該ランダム化されたデータに対して生成されたＥＣＣ冗長記号と、ランダム化される前のデータに対して生成されたチェック記号とを含み、該誤り訂正プロセッサは、（ａ）該ディスクから読み出された該ランダム化されたデータを格納するためのデータバッファと、（ｂ）該データバッファから該ランダム化されたデータを受け取るように接続され、該ランダム化されたデータ中の誤りを訂正するために、ＥＣＣ誤りシンドロームおよび訂正値を生成するためのＥＣＣ復号化器と、（ｃ）該ＥＣＣ復号化器が該データバッファから該ランダム化されたデータを受け取るのと同時に該データバッファから該ランダム化されたデータを受け取るように接続され、検証シンドロームを生成するためのシンドローム生成器と、（ｄ）該検証シンドロームを所定の値を比較して、該ランダム化されたデータに対する訂正の有効性および完全性を検証するための訂正検証器と、（ｅ）該データバッファから該ランダム化されたデータを受け取るように接続され、該訂正検証器が、該ランダム化されたデータに対する訂正が有効で且つ完全であることを示した後、該ランダム化されたデータを非ランダム化するための非ランダム化器とを含んでおり、これにより上記目的が達成される。
【００４７】
前記検証シンドロームが、巡回冗長符号（ＣＲＣ）に従って生成されてもよい。
【００４８】
前記シンドローム生成器が、ランダム化されたデータ記号が訂正されるときに前記ＥＣＣ復号化器によって生成される訂正値を用いて、前記検証シンドロームを更新してもよい。
【００４９】
多次元符号に対する訂正の有効性および完全性の証明に関連する待ち時間を避けるコンピュータ記憶装置のための誤り訂正システムが開示される。好ましい実施態様において、検証は、巡回冗長検査（ＣＲＣ）を用いて実施される。書込み動作中、ＣＲＣ冗長シンボルは、ホストシステムから受信したユーザデータに対して計算され、ＣＲＣシンボルを追加した後、データは、疑似ランダムデータパターンで排他的論理和計算することによってランダム化される。次に、ＥＣＣシンボルは、ランダム化データに対して（好ましくは、リードソロモン符号を用いて）生成され、行（Ｑ）および列（Ｐ）符号語の積符号を形成する。次に、この積符号は、ディスクに書き込まれる。読み返し時、積符号は、データバッファに記憶され、Ｐ／Ｑ復号化器によって復号化される。Ｑ符号語に対する第１パスの間、データＣＲＣシンドロームは、訂正されていないランダム化データに対して生成され、データＣＲＣシンドロームは、データＣＲＣレジスタに記憶される。さらに、第１パスおよび次のパスにおいては、ＰまたはＱ符号語に訂正がなされるとき、訂正値は、誤りＣＲＣレジスタに適用される。完全なＣＲＣ符号語を処理した後、データＣＲＣレジスタと誤りＣＲＣレジスタとは組み合わされ、最終ＣＲＣシンドロームが生成される。最終ＣＲＣシンドロームは、定数と比較され、積符号に対する訂正が有効かつ完了しているかどうかを決定する。このとき、定数は、ランダムデータパターンに対するＣＲＣと等しい。このように、ＣＲＣ検査は、ランダム化データに対して行われ得る。これによって、ＣＲＣシンドロームを生成する前にデータを非ランダム化するためのデータバッファへのアクセスに関連する待ち時間が避けられる。
【００５０】
本発明によって提供される他の利点は、ＰおよびＱ符号語の訂正と同時に実行中にＣＲＣシンドロームを生成する能力である。従って、ＣＲＣ符号語を処理した直後に、ＣＲＣシンドロームは、訂正の有効性および完全性を検査するために利用可能である。つまり、ＣＲＣシンドロームを生成するためにデータバッファにアクセスする必要はないのである。
【００５１】
本発明の実施可能性局面は、ＰおよびＱパス中にデータおよび誤りＣＲＣシンドロームを調節し、ＣＲＣ符号語シンボル内のオフセットを補うことである。例えば、垂直（即ち、Ｐ）符号語を処理する場合、処理される各垂直シンボルに対して、１行のデータシンボルによって誤りＣＲＣシンドロームを調節する必要がある。これは、以下の式によってデータおよび誤りＣＲＣシンドロームを乗算する特殊な乗算器回路を用いて実行される。
【００５２】
【数７】
0004346135.tif 000008
ここで、ｋは、オフセット（例えば、１行のシンボル）、およびＧ（ｘ）は、ＣＲＣ生成器多項式である。
【００５３】
各データセクタに追加された個別のＣＲＣシンボルを有する多数のデータセクタを備えたＤＶＤ積符号については、ＣＤモードにおいてＣ１およびＣ２符号化／復号化に用いられるＳＲＡＭが、各データセクタに対する部分データおよび誤りＣＲＣシンドロームを記憶するために用いられる。ＰおよびＱパスの間、データおよび誤りＣＲＣシンドロームレジスタは、Ｐ／Ｑ復号化器によって処理される現在のデータシンボルに応じて、適切な部分ＣＲＣシンドロームでロードされる。各データセクタを処理した後、各データセクタに対するデータＣＲＣシンドロームと誤りＣＲＣシンドロームとは組み合わされ、疑似ランダムデータパターンに対するＣＲＣと等しい定数と比較される。
【００５４】
本発明の上記ならびに他の局面および利点は、以下の本発明の詳細な説明を図面を参照しながら読むことによってより明確に理解される。
【００５５】
【発明の実施の形態】
なお本発明の優先権主張の基礎となる米国出願は、「AN ECC SYSTEM EMPLOYING A DATA BUFFER FOR STORING CODEWORD DATA AND A SYNDROME BUFFER FOR STORING ERROR SYNDOROMES」という名称の同時に出願された米国特許出願第０８／９７０，７３０号、ならびに「CONCURRENTGENERATION OF ECC ERROR SYNDROMES AND CRC VALIDATION SYNDOROMES IN A DVDSTORAGE DEVICE」という名称の同時に出願された米国特許出願第０８／９７０，６００号および「COEFFICIENT UPDATING METHOD AND APPARATUS FOR REED-SOLOMON DECODER」という名称の米国特許第５，４４６，７４３号である。上記の米国特許出願および米国特許は、本願では、参考のために援用する。
【００５６】
[システムの概観]
図２は、本発明の誤り訂正システムの概観を示す。このシステムの動作は、以下の変更を除いて、図１を参照しながら上述した従来のシステムと同様である。読出し動作中、ＥＣＣ誤りシンドロームは、第１水平パスにおいて、積符号の水平符号語および垂直符号語の両方に対して同時に生成される。ＥＣＣ誤りシンドロームは、ＳＲＡＭ１５内に記憶され、ＳＲＡＭ１５はＣＤ積符号を復号化するときにＣＩＲＣ誤り訂正用にも用いられる。これにより、記憶装置の待ち時間が大幅に減少する。なぜなら、次の水平または垂直パスの間にＥＣＣ誤りシンドロームを再生するためにデータバッファ１にアクセスする必要がないからである。本発明の他の重要な変更は、積符号の訂正と同時にＣＲＣシンドロームを生成すること、およびデータバッファに記憶されたデータを非ランダム化する前にＣＲＣシンドロームを検査することである。これにより、ＣＲＣシンドロームを生成するために、データバッファ１から積符号全体を読み出す必要がなくなり、記憶システムの待ち時間はさらに減少する。
【００５７】
図１の従来の誤り訂正システムと異なる構成要素は、ＳＲＡＭ１５、Ｐ／Ｑ復号化器１６（ＥＣＣ／シンドローム生成器１７および誤り訂正器１８を含む）、およびＣＲＣ生成器および訂正検証器１９である。ＥＣＣ／シンドローム生成器１７は、ライン２０を介して誤り訂正器に転送されるＥＣＣシンドロームを生成および記憶する際にＳＲＡＭ１５を用いる。データバッファ１に記憶される符号語を訂正するための誤り訂正器１８によって生成される訂正値は、ＥＣＣシンドロームを更新する際に使用されるＥＣＣ／シンドローム生成器１７にもライン２１を介して通信される。ＣＲＣ生成器および訂正検証器１９はまた、ＳＲＡＭ１５を用いて、ＤＶＤ積符号の１６個のデータセクタに対する１６個の部分ＣＲＣシンドロームを記憶する。ＳＲＡＭ１５内に記憶される部分ＣＲＣシンドロームは、誤り訂正器１８によって生成される訂正値を用いて更新される。訂正値は、ライン２１を介して、ＣＲＣ生成器および訂正検証器１９と通信される。
【００５８】
[データフォーマット]
図３Ａは、ＤＶＤ記憶装置において典型的に用いられる２次元積符号のデータフォーマットを示す。積符号は、１６個のデータセクタを有し、各データセクタは、１２個の水平符号語（Ｑ符号語）を有する。各水平符号語は、好ましくはリード−ソロモン符号に従って生成される１０個のＥＣＣ冗長シンボルを有する。１８２個の垂直符号語（Ｐ符号語）があり、それぞれ、図示するように、１６個の冗長シンボルを有する。ＥＣＣ冗長シンボルは、ＥＣＣ符号語も形成する。即ち、ＥＣＣ冗長シンボルは、ユーザデータと同様に訂正可能である。従って、右側には、１０個のＥＣＣ符号語を含む全部で１８２個の垂直符号語があり、下側には、１６個の水平ＥＣＣ符号語を含む２０８個の水平符号語がある。
【００５９】
１６個のデータセクタのそれぞれの端部には、ＥＣＣ冗長シンボルを使用して符号語に対する訂正の有効性および完全性を証明するのに用いられる４個のＣＲＣシンボルがある。上記のように、書込み動作中、ＣＲＣシンボルは、通常、データがランダム化される前およびＥＣＣ冗長シンボルを加える前に、ユーザデータに対して生成される。従って、ＣＲＣシンボルは、ＥＣＣシンボルをカバーしない。さらに、従来の誤り訂正システムは、ＣＲＣ検査を行う前にデータを非ランダム化しなければならない。
【００６０】
図３Ｂは、図３Ａの積符号の最初の２個のデータセクタのさらなる詳細を示す。ＥＣＣ符号語の訂正と同時にＣＲＣシンドロームを生成する本発明の技術について、図３Ｂを参照しながら以下に説明する。
【００６１】
[データランダム化器／非ランダム化器]
本発明の誤り訂正システムは、ユーザデータを不透明にし、検出するのが困難なデータシーケンスがディスクに記録されるのを防止する。図２を参照しながら上述したように、データバッファ１に記憶されるユーザデータは、ＣＲＣシンボルが生成された後にランダム化される。次に、ＥＣＣ／シンドローム生成器１２は、ランダム化データを処理し、図３Ａに示す積符号のＰおよびＱ符号語に対するＥＣＣ冗長を生成する。読み返し時に、積符号は訂正され、訂正が確認される。訂正が有効かつ完了している場合、データは非ランダム化され、ホストシステムに転送される。
【００６２】
データをランダム化／非ランダム化するための回路は当業者に周知であり、図３Ｃおよび図３Ｄは、この回路を示す。回路は、ライン２３に与えられる疑似ランダムデータシーケンスを生成するためのランダムパターン生成器を有する。読出し動作中、データバッファ１に記憶されるユーザデータおよびＣＲＣシンボルは、加算器２４においてランダムデータシーケンスに加えられ（排他的論理和計算）、それによって、データがディスクに書き込まれる前にデータをランダム化する。読み返し時に、ランダムパターン生成器２２は、加算器２５において、ディスクから読み出されたデータに加えられ（排他的論理和計算）、それによって、データをホストシステムに転送する前にデータを非ランダム化する。
【００６３】
好ましくは、疑似ランダムデータシーケンスは、８ビットシンボル（ＥＣＣ符号のシンボルサイズ）を用いて生成される。疑似ランダムデータシーケンスを生成するための好ましい実施態様は、図３Ｄに示すように、リニアフィードバックシフトレジスタ（ＬＦＳＲ）を用いることである。ＬＦＳＲ回路は、ライン２６を介してシード値で初期化され、疑似ランダムデータシーケンスは、シード値に応じて異なる。異なるシード値は、図３Ａに示す各ＤＶＤ積符号に対して用いられる。
【００６４】
[水平および垂直ＥＣＣシンドロームの同時生成]
ＥＣＣおよびＣＲＣシンドロームを同時に生成し、訂正値を用いてＥＣＣおよびＣＲＣシンドロームを更新する回路および流れ図を以下に開示する。本発明のＥＣＣシンドローム生成器１７について２つの実施態様がある。第１の実施態様では、水平パスの間に水平符号語に対してシンドロームが生成されるのと同時に、ＥＣＣシンドロームが、垂直符号パスに対して生成される。以下にさらに詳細に記載するように、ＳＲＡＭ１５は、垂直シンドロームの生成を容易にする。このように、垂直符号語に対するＥＣＣシンドロームが、水平パスの直後にＳＲＡＭ１５内において利用できるので、垂直符号語は、ＥＣＣシンドロームを生成するためにデータバッファにアクセスせずに訂正され、それによって、誤り訂正待ち時間が大幅に減少する。本実施態様は、訂正が、通常、水平および垂直符号語に対する一回のパスの後完了する、ＤＶＤ記憶装置などにおけるように、大量のＥＣＣ冗長を用いる積符号に特に適している。
【００６５】
ＥＣＣシンドローム生成器１７の第２の実施態様は、より少ないＥＣＣ冗長を用いる積符号に向けられており、そのため、多数の水平および垂直パスを必要とする。この実施態様では、ＳＲＡＭ１５は、水平および垂直符号語の両方に対してＥＣＣシンドロームを記憶する。ＥＣＣシンドロームの両セットは、第１水平パスの間に同時に生成され、ＥＣＣシンドロームは、訂正値を用いて更新される。このように、データバッファにアクセスし、ＥＣＣシンドロームを再生成する際の待ち時間は、水平および垂直パスの両方に対して避けられる。誤り訂正は、わずかな時間で行われる。なぜなら、第１パスに続くパスは、データを訂正するためにデータバッファにアクセスすることのみが必要であるからである。
【００６６】
本発明の第１の実施態様では、垂直誤りシンドロームのみがＳＲＡＭ１５内に記憶されるが、これは、図４および図５を参照することによって理解される。図４は、各水平パスにおける水平符号語に対する誤りシンドロームを生成するために用いられる回路を示す。即ち、水平誤りシンドロームは常に再生成され、ＳＲＡＭ１５内には記憶されない。水平誤りシンドロームＳiを生成するために、図４の回路は、以下の生成器多項式Ｇ（ｘ）の因数によって各水平符号語Ｃ’（ｘ）の剰余除算を計算する。
【００６７】
【数８】
0004346135.tif 000009
このとき
【００６８】
【数９】
0004346135.tif 000010
である。この計算を行うために、水平符号語（ＥＣＣ冗長を含む）のシンボルは、データバッファ１から連続して読み出され、ライン２７を介して、リニアフィードバックシフトレジスタ（ＬＦＳＲ）２８0から２８9のバンクに与えられる。好ましい実施態様において、各水平符号語は、図３Ａに示すように、１０個のＥＣＣ冗長シンボルを含むので、図４では１０個のＬＦＳＲが存在することになる。各ＬＦＳＲには、フィードバックパスにおいて、対応するαi係数乗算器が設けられている。各ＬＦＳＲは、生成器多項式Ｇ（ｘ）の各因数について剰余除算を行い、これによって、上式についての誤りシンドロームＳiを生成する。図４に開示する回路は、当業者に周知であり、本発明の新規の局面は、垂直符号語に対して誤りシンドロームを同時に生成することにある。図５は、この詳細を示す。
【００６９】
数学的に、垂直符号語に対する誤りシンドロームは、上記の水平符号語に対するのと同様に計算される。即ち、垂直誤りシンドロームＳiは、生成器多項式Ｇ（ｘ）の因数で各垂直符号語Ｃ’（ｘ）の剰余除算を計算することによって生成される。従来のシンドローム生成器は、通常、図４に示すのと同じ回路を用いて垂直誤りシンドロームを生成する。即ち、垂直符号語（ＥＣＣ冗長を含む）のシンボルは、データバッファ１から連続して読み出され、ＬＦＳＲのバンクを通してシフトされる。本発明において、垂直誤りシンドロームは、水平誤りシンドロームの生成と同時に生成され、垂直パスの間に垂直符号語を読み出すためにデータバッファへアクセスすることが避けられる。
【００７０】
図５は、垂直誤りシンドロームを同時に生成するための回路を示す。この回路の動作は、図３Ａに示す積符号を参照することによって理解される。ＳＲＡＭ１５は、１８２個の垂直符号語のそれぞれに対して１６個の誤りシンドロームＳiを記憶する容量を有する。ＳＲＡＭ１５内における垂直誤りシンドロームＳiは、第１水平パスの初めにゼロに初期化される。第１水平符号語を処理する際、シンボルは、データバッファ１から連続して読み出され、ライン２７を介して図４のＬＦＳＲに与えられ、水平誤りシンドロームを生成する。シンボルは、同時に、ライン２７を介して図５に示す回路に与えられ、垂直誤りシンドロームを生成する。図４と同様に、図５は、生成器多項式Ｇ（ｘ）の１６個の因数によって垂直符号語シンボル（各垂直符号語は、１６個ＥＣＣ冗長シンボルを有する）の剰余除算を計算するためのシンドローム生成回路２９0から２９15のバンクを有する。
【００７１】
図５に示す個々のシンドローム生成回路２９0から２９15を理解するために、第１水平符号語がデータバッファから読み出されるときの動作について考えよう。第１水平符号語の第１シンボルは、第１垂直符号語の第１シンボルに対応する。従って、制御ライン３０は、第１垂直符号語に対して、１６個の垂直誤りシンドローム（各８ビット）をＳＲＡＭ１５から取り出す。各８ビット垂直ＥＣＣシンドロームは、対応するレジスタ３１0から３１15にラッチされ、乗算器３２0から３２15の出力として選択され、対応するαiフィードバック係数３３0から３３15によって乗算される。ライン２７上の符号語シンボルは、乗算器３４0から３４15の出力として選択され、加算器３５0から３５15において、係数乗算器の出力として加算される。加算器３５0から３５15の出力で更新されたシンドロームは、次に、ＳＲＡＭ１５内に再記憶される。第１水平符号語の第２シンボルを処理する際、制御ライン３０は、第２の垂直符号語に対して、１６個垂直誤りシンドロームをＳＲＡＭ１５から取り出し、上記の手順が繰り返される。このプロセスは、水平符号語のそれぞれに対して続行し、水平パスの終わりには、垂直符号語を訂正するための誤りシンドロームが、ＳＲＡＭ１５内に記憶される。
【００７２】
水平パスの間に水平符号語が訂正される場合、ＳＲＡＭ１５内に記憶されている対応する垂直誤りシンドロームは、訂正されたシンボルを考慮するために更新されなければならない。図２のシンドローム生成器１７および誤り訂正器１８は、好ましくは、隣接する符号語上で動作する。換言すると、シンドローム生成器１７が、現在の水平符号語に対して誤りシンドロームを生成している間、誤り訂正器１８は、前の水平符号語に対してシンボルを訂正する。さらに、誤り訂正は、水平誤りシンドロームの生成を追跡し、訂正値で垂直誤りシンドロームの調整を単純にする。
【００７３】
例えば、シンドローム生成器１７が、誤り訂正器１８が、第１の水平符号語を訂正する間、図３Ａの第２水平符号語に対して誤りシンドロームを生成することについて考慮する。シンドローム生成器１７が、第２符号語の第３シンボル３６を通過し、第１符号語の第３シンボル３７に誤りがあると仮定する。誤り訂正器１８は、データバッファ１に記憶されている第１水平符号語の第３シンボル３７を訂正するために用いられる訂正値を生成し、訂正値は、図５の垂直シンドローム生成回路２９0から２９15にライン２１を介して与えられる。制御ライン３０は、レジスタ３１0から３１15にラッチされる、第３垂直符号語に対する垂直誤りシンドロームをＳＲＡＭ１５から取り出す。次に、レジスタ３１0から３１15の出力は、加算器３５0から３５15に対する入力として、乗算器３４0から３４15を通して選択される。ライン２１を介して与えられる訂正値は、乗算器３２0から３２15の出力として選択され、対応のαiフィードバック係数３３0から３３15によって乗算され、加算器３５0から３５15において垂直誤りシンドロームに加算される。訂正値を対応するαiフィードバック係数３３0から３３15によって乗算することは、現在の垂直ＥＣＣシンドローム値と、訂正されているシンボルとの間のオフセット（即ち、垂直符号語における１つのシンボルのオフセット）を考慮するのに必要である。
【００７４】
水平パスの終わりには、垂直符号語に対する誤りシンドロームは、完全に生成され、即座に処理に利用できる。従って、垂直パスを実行するためには、垂直誤りシンドロームは、ＳＲＡＭ１５から単に取り出され、垂直符号語を訂正するために誤り訂正器１８によって使用される。垂直パスの後、積符号のＣＲＣシンボルが、誤りがまだ残っていることを示す場合、上記のプロセスが繰り返される（即ち、水平および垂直誤りシンドロームが、次の水平パスにおいて再生成される）。
【００７５】
本発明の他の実施態様において、水平および垂直シンドロームは両方ともＳＲＡＭ１５内に記憶される。なぜなら、これらは、第１水平パスにおいて同時に生成されるからである。このように、上記の実施態様のように、次の水平パスの間に水平シンドロームを再生成する必要はない。シンドロームは、水平および垂直パスの間に単に取り出され、符号語を訂正するために使用される。本実施態様は、積符号を訂正するために多数のパスが必要である場合（例えば、記録密度を増加させることによって、ＥＣＣ冗長シンボルが減少する場合、またはＳＮＲが減少する場合）に特に有利である。
【００７６】
図６Ａおよび図６Ｂは、それぞれ、本実施態様による訂正値を用いて垂直および水平シンドロームを更新するための回路を示す。これらの回路は、オフセットを考慮する必要がないので、誤り訂正値２１を、αiで乗算する必要がないこと以外は、図５の回路と実質的に同様に動作する。好ましい実施態様において、第１水平パスにおいて水平および垂直誤りシンドロームを最初に生成するための図４および図５の回路は、次のパスにおいて誤りシンドロームを更新するための図６Ａおよび図６Ｂの回路と共用される。制御ライン３０を介したアドレッシングは、どの誤りシンドロームのセット（水平または垂直）が、適切な時点でＳＲＡＭ１５から取り出されるかを決定する。
【００７７】
図７Ａは、本発明の動作を説明するフロー図であり、図示しないコントローラによって実行される。第１の水平パス３７の間に、水平および垂直ＥＣＣシンドロームおよびデータＣＲＣシンドロームが同時に生成され、ＳＲＡＭ１５内に記憶される。また、第１の水平パス３７の間に、水平符号化語が訂正され、訂正値を用いて、垂直シンドロームおよびＳＲＡＭ１５内に記憶された誤りＣＲＣシンドロームが更新される。第１のおよび次の水平パスの後、ステップ３８で、積符号への訂正の有効性および完全性が最終ＣＲＣシンドロームを用いて確認される。水平パス後も誤りが残る場合は、ステップ４０で垂直パスが実行され、垂直符号語が訂正される。ここでは、訂正値を用いて、シンドロームバッファ内に記憶された水平シンドロームが更新される。垂直パスの後、ステップ４２で、訂正の有効性および完全性が最終ＣＲＣシンドロームを用いて確認される。垂直パス後も誤りが残る場合は、ステップ４４で別の水平パスが実行され、水平符号語が訂正される。実際の適用に依存して、訂正はＳＲＡＭ１５内に記憶された水平シンドロームを用いて行われる（すなわち、水平シンドロームはＳＲＡＭ１５内で既に利用可能な場合は再生成されない）。水平および垂直パス、ならびにＣＲＣ検査は、積符号が訂正されるかまたは訂正不能と決定されるまで繰り返される。
【００７８】
第１の水平パスの間に水平および垂直シンドロームならびにデータＣＲＣシンドロームを同時に生成するフロー図を図７Ｂに示し、また、第１のパスの間に水平符号語を訂正し、訂正値を用いて垂直シンドロームおよび誤りＣＲＣシンドロームを更新するフロー図を図７Ｃに示す（図７Ｂおよび図７Ｃのフロー図は平行して実行される）。図７Ｂを参照して、ステップ４６で、ＣＯＬおよびＲＯＷ変数がゼロに初期化される。ＳＲＡＭ１５がクリアされ、ブロック訂正不能誤りフラグ（ＢＬＫ＿ＵＮＣ）がクリアされ、そしてＦＩＲＳＴ＿ＰＡＳＳフラグが設定されて、これが第１の水平パスであることを示す。次に、ステップ４８で、ＲＯＷの水平符号語に対してシンボルが読み出され、これを用いて、上述のように、図４の回路を用いて水平ＥＣＣシンドロームが、および図５の回路を用いて垂直ＥＣＣシンドロームが更新される。ステップ５０でＦＩＲＳＴ＿ＰＡＳＳフラグが設定されている場合は、このデータシンボルはまた、図７Ｆのフロー図を実行することによってステップ５２でデータＣＲＣシンドロームを更新するためにも用いられる。次にステップ５４でＣＯＬ変数がインクリメントされ、現在の水平符号語のための次のシンボルを用いて、第１の水平パスの間に水平および垂直ＥＣＣシンドロームならびにデータＣＲＣシンドロームが更新される。
【００７９】
ステップ５６でＣＯＬ変数が１８２に等しいときは、現在の水平符号語のための最終シンボルが読み出されたことを意味する。ステップ５８でループを実行して、誤り訂正手順（図７Ｃのフロー図）が前の水平符号語の処理を終了させるのを待つ。前の符号語の訂正が終了すると、図７Ｃのステップ８８で、訂正フラグが非使用中にリセットされる。図７Ｂのステップ６０で訂正フラグは使用中に設定され、Ｃ＿ＲＯＷ変数は現在のＲＯＷに設定され、ＲＯＷ変数はインクリメントされ、ＣＯＬ変数はゼロにリセットされる。この時点で、図７Ｃの訂正手順が実行され、現在の水平符号語（すなわちＣ＿ＲＯＷの符号語）が訂正され、同時に、次の水平符号語（すなわちＲＯＷの符号語）のためにＥＣＣシンドロームが生成される。
【００８０】
図７Ｃを参照して、ステップ６４でループを実行して、図７Ｂのシンドローム生成手順が、現在の水平符号語の処理を終了して訂正フラグを使用中に設定するのを待つ。ステップ６６で、訂正の間に現在のコラムを追跡するＣ＿ＣＯＬ変数がゼロにリセットされ（すなわち、訂正中の水平符号語の最初のシンボルにリセットされ）、符号語訂正不能フラグ（ＣＷ＿ＵＮＣ）がクリアされる。ステップ６８で、訂正中の水平符号語のためのＥＣＣシンドロームがＳＲＡＭ１５から取り出され、誤りロケータ多項式が生成され、ルートが有効シンボル位置に対応するかどうかが決定される。ステップ６９で、ＥＣＣシンドロームが、誤りがないことを示すゼロである場合は、ステップ７１で誤りＣＲＣシンドロームが更新される。ステップ７０で、シンドロームが、誤りが多すぎるか、または誤りロケータ多項式のルートが無効シンボルを指す場合は、ステップ７３で、ＣＷ＿ＵＮＣおよびＢＬＫ＿ＵＮＣフラグが設定され、符号語およびブロック全体（積符号）が訂正不能誤りを含むことを示し、ステップ７１で誤りＣＲＣシンドロームが更新される。ステップ７０で符号語が訂正可能である場合は、ステップ７２で、Ｃ＿ＲＯＷの水平符号語のためのＥＣＣシンドロームがクリアされる（ゼロにセットされる）。次にループを実行して、Ｃ＿ＲＯＷの水平符号語が訂正される。ステップ７４で、Ｃ＿ＣＯＬのシンボルが誤りである場合は、分岐を実行して、データバッファ内に記憶されたシンボルが訂正され、訂正値を用いて垂直シンドロームが更新される。この訂正は、ステップ７６でＣ＿ＣＯＬがＣＯＬより小さくなるまで遅延される。すなわち、図７Ｃの誤り訂正手順は、図７Ｂのシンドローム生成手順が現在の訂正コラムＣ＿ＣＯＬをパスするまで待つ。これは、図５の回路が正しく作動するためには必要である。何故なら、この回路は、訂正値２１にαi３３iを乗算して、１つのシンボルのオフセットを計算するものであるからである。図７Ｃのステップ７８で、データバッファ内に記憶された水平符号語シンボルが訂正値を用いて訂正され、ステップ８０で、訂正値を用いて、図５に関連して上述したようにＣ＿ＣＯＬの垂直符号語のための垂直シンドロームが更新される。ステップ８１で、誤りＣＲＣシンドロームが訂正値により更新され（訂正値がゼロの場合でも）、ステップ８２で、変数Ｃ＿ＣＯＬが水平符号語の次のシンボルにインクリメントされ、訂正ループが再実行される。
【００８１】
ステップ８４でＣ＿ＣＯＬが１８２に等しい場合は、水平符号語の最終シンボルが処理されたことを意味する。次の垂直パスの間に現在の水平符号語のための誤りシンドロームの更新を迅速に行うために、ステップ８６で、これらの誤りシンドロームが最初の符号語シンボルに再配置される。これは次の計算によって実行される。
【００８２】
【数１０】
0004346135.tif 000011
上記の動作を行う回路について以下により詳細に述べる。
【００８３】
図７Ｃのステップ８８で、訂正使用中フラグがクリアされ、ステップ６４で、訂正手順は図７Ｂのシンドローム生成手順が次の水平符号語のための誤りシンドロームの生成を終了するのを待つ。シンドローム生成手順および誤り訂正手順は、最終水平符号語が処理される（すなわち、図７Ｂのステップ６２でＲＯＷが２０８に等しくなる）まで平行して実行される。このとき、ステップ６３でＦＩＲＳＴ＿ＰＡＳＳフラグがクリアされ、制御は図７Ａに戻る。図７Ａのステップ３８で、第１の水平パス後も誤りが残っている場合は、ステップ４０で垂直パスが実行される。この手順のフロー図は図７Ｄに示す。
【００８４】
ステップ９０で、訂正変数Ｃ＿ＣＯＬおよびＣ＿ＲＯＷはゼロにリセットされ（すなわち、第１の垂直符号語の最初のシンボルにリセットされ）、符号語訂正不能フラグ（ＣＷ＿ＵＮＣ）はクリアされる。次にステップ９２で、訂正中の垂直符号語のためのシンドロームがＳＲＡＭ１５から取り出され、誤りロケータ多項式を生成し、ルートが有効シンボル位置に対応するかどうかを決定する。ステップ９３で、ＥＣＣシンドロームがゼロで誤りがないことを示す場合は、ステップ９５で誤りＣＲＣシンドロームが更新される。ステップ９４で、シンドロームが、誤りが多すぎるか、または誤りロケータ多項式のルートが無効シンボルを指す場合は、ステップ９７で、ＣＷ＿ＵＮＣおよびＢＬＫ＿ＵＮＣフラグが設定され、ステップ９５で誤りＣＲＣシンドロームが更新される。ステップ９４で、符号語が訂正可能である場合は、ステップ９６で、垂直符号語のためのＥＣＣシンドロームがクリアされる（ゼロに設定される）。次にループを実行して、Ｃ＿ＣＯＬの垂直符号語が訂正される。ステップ９８で、Ｃ＿ＲＯＷのシンボルが誤りである場合は、分岐を実行して、ステップ１００でデータバッファ内に記憶されたシンボルが訂正され、ステップ１０２で訂正値を用いて水平シンドロームが更新される。図６Ａの回路を用いて、図５を参照して上述したのと類似の方法で水平シンドロームが更新される。Ｃ＿ＲＯＷの水平ＥＣＣシンドロームがＳＲＡＭ１５から取り出され、αi３３iで乗算され、訂正値３５iに加算され、ＳＲＡＭ１５内に戻される。図７Ｄのフローチャートには示していないが、訂正が行われない場合も（すなわち訂正値がゼロの場合も）符号語の各シンボルに対して水平シンドロームが更新される。これにより、図６Ａのシンドローム更新回路が簡略化される。すなわち、ＥＣＣシンドロームを次の符号語シンボルに位置付けるのに、αi乗算器３３iしか必要としない。
【００８５】
図７Ｄのステップ１０４で、誤りＣＲＣシンドロームが訂正値に更新され（訂正値がゼロの場合も）、ステップ１０５で、Ｃ＿ＲＯＷ変数が現在の垂直符号語の次のシンボルにインクリメントされる。ステップ１０６で、Ｃ＿ＲＯＷが２０８に等しくなる、つまり現在の垂直符号語の最終シンボルが処理されるまで、訂正ルームが繰り返される。最終シンボルが処理されると（または、ステップ９４で符号語が訂正不能である場合）、ステップ１０７で、Ｃ＿ＣＯＬの垂直符号語のための誤りシンドロームが符号語の最初のシンボルに再配置される。これは次の計算によって実行される。
【００８６】
【数１１】
0004346135.tif 000012
上記の動作を行う回路について以下により詳細に述べる。
【００８７】
ステップ１０８で、Ｃ＿ＣＯＬ変数が次の垂直符号語にインクリメントされ、Ｃ＿ＲＯＷ変数がゼロにリセットされて、次の垂直符号語の最初のシンボルを指す。ステップ１１０でＣ＿ＣＯＬが１８２に等しくなり、垂直符号語のすべてが処理されたことを示すまで、図７Ｄの訂正手順が繰り返される。
【００８８】
垂直パスの最後に、ステップ４２で積符号に誤りが残っている場合は、ステップ４４で水平訂正パスが実行される。水平シンドロームがＳＲＡＭ１５内に記憶されていない場合、ステップ４４で図７Ｂのフロー図が実行され、水平ＥＣＣシンドロームが再生成される（ＦＩＲＳＴ＿ＰＡＳＳを偽として）。しかし、ＳＲＡＭ１５内に水平ＥＣＣシンドロームが記憶されている場合は、図７Ｅのフロー図が実行され、単に訂正システムの待ち時間を低減させるＥＣＣシンドロームが取り出され処理される。
【００８９】
図７Ｅのステップ１１２で、訂正変数Ｃ＿ＣＯＬおよびＣ＿ＲＯＷがゼロにリセットされ（すなわち、第１の水平符号語の最初のシンボルにリセットされ）、符号語訂正不能フラグ（ＣＷ＿ＵＮＣ）がクリアされる。次にステップ１１４で、訂正中の水平符号語のためのシンドロームがＳＲＡＭ１５から取り出され、誤りロケータ多項式を生成し、ルートが有効シンボル位置に対応するかどうかを決定する。ステップ１１５で、ＥＣＣシンドロームがゼロで誤りがないことを示す場合は、ステップ１１７で誤りＣＲＣシンドロームが更新される。ステップ１１６で、シンドロームが、誤りが多すぎるか、または誤りロケータ多項式のルートが無効シンボルを指す場合は、ステップ１１９でＣＷ＿ＵＮＣおよびＢＬＫ＿ＵＮＣフラグが設定され、符号語およびブロック全体（積符号）が訂正不能誤りを含むことを示し、ステップ１１７で、誤りＣＲＣシンドロームが更新される。ステップ１１６で、符号語が訂正可能である場合は、ステップ１１８で、Ｃ＿ＲＯＷの水平符号語のためのＥＣＣシンドロームがクリアされる（ゼロに設定される）。次にループを実行して、Ｃ＿ＲＯＷの水平符号語が訂正される。
【００９０】
ステップ１２０で、Ｃ＿ＣＯＬのシンボルが誤りである場合は、分岐を実行して、ステップ１２２でデータバッファ内に記憶されたシンボルが訂正され、ステップ１２４で訂正値を用いて垂直シンドロームが更新される。垂直パスの間に水平ＥＣＣシンドロームを更新するのに図６Ａを参照して上述したのと同様の方法で、図６Ｂの回路を用いて垂直ＥＣＣシンドロームが更新される。Ｃ＿ＣＯＬの垂直ＥＣＣシンドロームがＳＲＡＭ１５から取り出され、αi３３iで乗算され、訂正値３５iに加算され、ＳＲＡＭ１５内に戻される。図７Ｅのフローチャートには示していないが、訂正が行われない場合も（すなわち訂正値がゼロの場合も）符号語の各シンボルに対して、垂直ＥＣＣシンドロームが更新される。これにより図６Ｂのシンドローム更新回路が簡略化される。すなわち、ＥＣＣシンドロームを次の符号語シンボルに位置付けるのに、αi乗算器３３iしか必要としない。
【００９１】
図７Ｅのステップ１２６で、誤りＣＲＣが訂正値を用いて更新され（訂正値がゼロの場合も）、ステップ１２７で、Ｃ＿ＣＯＬ変数が現在の水平符号語の次のシンボルにインクリメントされる。ステップ１２８で、Ｃ＿ＣＯＬが１８２に等しい場合は、現在の水平符号語の最終シンボルが処理されたことを意味する。最終シンボルが処理されると（または、ステップ１１６で符号語が訂正不能である場合）、ステップ１３０で、Ｃ＿ＲＯＷの水平符号語のための誤りシンドロームが符号語の最初のシンボルに再配置される。これは次の計算によって実行される。
【００９２】
【数１２】
0004346135.tif 000013
ステップ１３２で、Ｃ＿ＲＯＷ変数が次の水平符号語にインクリメントされ、Ｃ＿ＣＯＬ変数がゼロにリセットされて、次の水平符号語の最初のシンボルを指す。ステップ１３４でＣ＿ＲＯＷが２０８に等しくなり、水平符号語のすべてが処理されたことを示すまで、図７Ｅの訂正手順が繰り返される。
【００９３】
再び図７Ａを参照すると、ステップ４４で水平パスが完了した後、誤りが残っている場合は、ステップ４０で別の垂直パスが実行される。積符号が訂正されるかまたは訂正不能であると決定されるまで、繰り返し水平および垂直パスが続けられる。各データセクタのためのデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームを生成するフロー図を図７Ｇから図７Ｉに示し、ＣＲＣシンドロームを生成する回路を図８から図１１に示す。これらのフロー図および回路は以下のように動作する。
【００９４】
[ＣＲＣシンドロームの生成および検証]
図３Ａの各データセクタのためのＣＲＣシンドロームは２つの部分、すなわちデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームで生成される。データＣＲＣシンドロームは、非訂正データに対するＣＲＣとして生成され、誤りＣＲＣシンドロームは、訂正値に対するＣＲＣとして生成される。図３Ａの積符号のデータセクタの処理が終了すると、データＣＲＣシンドロームと誤りＣＲＣシンドロームとが組み合わされて最終ＣＲＣシンドロームが生成され、定数と比較されて、このセクタに対する訂正が有効且つ完全であるかどうかが決定される。上述のように、データＣＲＣシンドロームおよび誤りＣＲＣシンドロームは、ランダム化データに対して積符号を訂正するのと同時に生成される。すなわち、従来のように訂正後およびデータの非ランダム化後に生成されるのではない。
【００９５】
図１の従来の誤り訂正システムでは、ＣＲＣ冗長シンボルＣＲＣREDは、データ多項式Ｄ（ｘ）を生成器多項式Ｇ（ｘ）で割った剰余除算として生成される。
【００９６】
【数１３】
0004346135.tif 000014
ＣＲＣ冗長シンボルＣＲＣREDをデータ多項式Ｄ（ｘ）に加算した後、疑似ランダムデータシーケンス多項式Ｒ（ｘ）を加算することによってデータをランダム化し、この結果、符号語多項式Ｃ（ｘ）がディスクに書き込まれる。
【００９７】
【数１４】
0004346135.tif 000015
読み戻されると、受け取られた符号語多項式Ｃ’（ｘ）はＥＣＣ冗長シンボルを用いて訂正され、訂正された符号語から疑似ランダムデータシーケンスＲ（ｘ）が減算され、以下のＣＲＣシンドロームＳCRCが生成される。
【００９８】
【数１５】
0004346135.tif 000016
ＣＲＣシンドロームＳCRCは次にゼロと比較され、訂正の有効性および完全性が確認される。
【００９９】
本発明では、ＣＲＣ検査は、訂正された符号語を非ランダム化する前に行われる。本発明の実現可能な改変として、データをランダム化／非ランダム化するために用いられる疑似ランダムデータシーケンスにわたって、最後のＣＲＣシンドロームをＣＲＣと比較してもよい。これは、以下の数学関係により理解される。
【０１００】
【数１６】
0004346135.tif 000017
ここで、Ｄ（ｘ）はデータ多項式、ＣＲＣREDはＣＲＣ冗長度、およびＲ（ｘ）は、データをランダム化するためにデータ多項式に加えられる疑似ランダムデータシーケンス多項式である。結果としてディスクに書き込まれる符号語Ｃ（ｘ）は、上述の従来技術の場合と同じである。しかし、データを非ランダム化する前に（すなわち、疑似ランダムデータシーケンス多項式Ｒ（ｘ）を減算する前に）受け取られた符号語Ｃ’（ｘ）をＣＲＣ生成器多項式で除算すれば、以下の関係が導かれる。
【０１０１】
【数１７】
0004346135.tif 000018
ここで、Ｅ（ｘ）は誤り多項式である。上記の式は以下のように書き換えることができる。
【０１０２】
【数１８】
0004346135.tif 000019
上記の式で、（Ｄ（ｘ）・ｘn-k＋ＣＲＣRED）  ｍｏｄ  Ｇ（ｘ）＝０である。従って、以下の式となる。
【０１０３】
【数１９】
0004346135.tif 000020
このように、受け取られた符号語Ｃ’（ｘ）がＥＣＣ冗長を用いて完全に訂正された場合（すなわち、Ｅ（ｘ）＝０）、受け取られた符号語Ｃ’（ｘ）に対して生成される最後のＣＲＣシンドロームは、上記の式から分かるように、疑似ランダムデータシーケンスＲ（ｘ）をＣＲＣ生成器多項式Ｇ（ｘ）で除算した剰余除算に等しい。疑似ランダムデータシーケンスＲ（ｘ）および生成器多項式Ｇ（ｘ）は既知であるため、疑似ランダムデータシーケンスＲ（ｘ）を生成器多項式Ｇ（ｘ）で割った剰余は定数となる。すなわち、最後のＣＲＣシンドロームは単にこの定数と比較され、ＥＣＣシンドロームを用いた訂正が有効且つ完全であるかどうかが決定される。ＣＲＣシンドロームは、受け取られた符号語の訂正と同時に生成されるため、ＣＲＣシンドロームは直ちに利用可能となる。つまり、従来技術のようにＣＲＣシンドロームを生成するために、データバッファから符号語全体を読み出す必要はない。
【０１０４】
ＣＲＣシンドロームを受け取られた符号語の訂正と同時に生成するために、本発明は、第１の水平パスの間に非訂正データに対してデータＣＲＣシンドロームを生成し、また、水平および垂直パス両方の間に訂正値に対して誤りＣＲＣシンドロームを生成する。図３Ａの積符号のデータセクタの処理が終了すると、データＣＲＣシンドロームと誤りＣＲＣシンドロームとが組み合わされて最終ＣＲＣシンドロームを生成し、これが定数（Ｒ（ｘ）  ｍｏｄ  Ｇ（ｘ））と比較される。
【０１０５】
本発明では、データＣＲＣシンドロームおよび誤りＣＲＣシンドロームは従来の方法では（すなわち、リニアフィードバックシフトレジスタ（ＬＦＳＲ）を用いて）生成されない。何故なら、垂直パスの間にデータシンボルがデータバッファから順次読み出されるのではないからである。そうではなく、データおよびＣＲＣシンドロームが、処理中のデータシンボルの位置に対応するように調整される。この調整は、データＣＲＣシンドロームおよび誤りＣＲＣシンドロームを以下の値で乗算することによって実行される。
【０１０６】
【数２０】
0004346135.tif 000021
ここで、ｋは符号語にわたってシンドロームを「移動させる」シンボルの数を表す。例えば、第１の水平パスの間にデータＣＲＣシンドロームを生成するとき、データＣＲＣシンドロームは、
【０１０７】
【数２１】
0004346135.tif 000022
で乗算され、これにより、データＣＲＣシンドロームが現在の水平符号語の次のシンボルに調整される。垂直パスの間、誤りＣＲＣシンドロームは、
【０１０８】
【数２２】
0004346135.tif 000023
で乗算され、これにより、誤りＣＲＣシンドロームが現在の垂直符号語の次のシンボルに調整される。ＣＲＣシンドロームを生成するこの方法の数学的な基礎について、ＣＲＣ生成器および訂正検証器を実現する回路に関連して以下に述べる。
【０１０９】
図３Ａに示すように、１６個のデータセクタがあり、それぞれにＣＲＣ冗長が付けられている。従って、第１の水平パスの間に１６個のデータＣＲＣシンドロームが生成され、水平および垂直パス両方の間に１６個の誤りＣＲＣシンドロームが更新される。これらのシンドロームは好ましくはＳＲＡＭ１５内に記憶され、これによりＳＲＡＭ１５を用いて、ＣＤ−ＲＯＭフォーマットのためのＣＩＲＣ誤り訂正およびＤＶＤフォーマットのためのＣＲＣシンドローム生成の両方が可能になる。第１の水平パスの間に新しいセクタがそれぞれ処理されるに従って、現在のデータＣＲＣシンドロームは開始値に初期化される。データＣＲＣシンドロームを次のセクタのための開始値に初期化する前に、前のデータセクタのための現在のデータＣＲＣシンドロームがＳＲＡＭ１５内に記憶される。同様に、垂直符号語の処理時には、誤り訂正システムが１６個のデータセクタを通って垂直方向に進行するに従って、現在のデータセクタに対応する適切な誤りＣＲＣシンドロームがＳＲＡＭ１５から取り出される。処理中の現在のデータセクタに従ってデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームを更新するこのプロセスは、図７Ｆから図７Ｊのフロー図により理解される。
【０１１０】
図７Ｆは、図３Ａの積符号に対する第１の水平パスの間にデータＣＲＣシンドロームを生成するフロー図を示す。この積符号の最初の２つのデータセクタは図３Ｂに示されている。図７Ｆのフロー図は、図７Ｂのステップ５２で新しいデータシンボルがデータバッファから読み出される度に実行される。図７Ｆのステップ１３６で、検査を行ってデータＣＲＣシンドロームを次のデータセクタの最初のシンボルに初期化すべきかどうかが決定される。例えば、第１の水平符号語の最初のシンボルを処理するとき、ステップ１３８で、データＣＲＣシンドロームを記憶するデータレジスタＤＡＴＡ＿ＲＥＧが、図３Ｂの第１のデータセクタの最初のシンボル１６０により初期化される。次のデータセクタに到達すると（すなわち、ステップ１３６でＲＯＷが１２に等しいとき）、ステップ１３８で第１のデータセクタのためのデータＣＲＣシンドロームがＳＲＡＭ１５内に保存され、ＤＡＴＡ＿ＲＥＧが、次の水平符号語のための最初のデータシンボル２０４により初期化される。
【０１１１】
図７Ｆのフロー図について続けて説明すると、データセクタの最初のシンボルが処理されず、且つステップ１４４でＣＯＬが１７２より小さい場合、ステップ１４６でデータＣＲＣシンドロームは１シンボル（１列）だけ右に調整され、現在のデータシンボルがデータＣＲＣシンドロームに加えられる。ステップ１４４で、ＣＯＬが１７１より大きい場合は、現在のデータシンボルはデータＣＲＣシンドロームに加えられない。何故なら、これはＣＲＣ符号語には含まれないＥＣＣ冗長シンボルであるからである（ＥＣＣ冗長は、上述のように書き込み動作中にＣＲＣ符号語が生成された後で加えられる）。例えば、図３Ｂの第１の水平符号語が処理されるとき、データＣＲＣシンドロームの生成は、図７Ｂのステップ６０でＣＯＬがゼロにリセットされて、次の水平符号語の処理が開始されるまで、シンボル１４８で停止状態となる。次に、ステップ１４６で、第２の水平符号語の最初のデータシンボル１５０をデータＣＲＣシンドロームに加える前に、データＣＲＣシンドロームは先ず１シンボルだけ右に（すなわち、図３Ｂのシンボル１５０に）調整される。
【０１１２】
データセクタの最終水平符号語の処理が終了すると（すなわち、ステップ１５４でＲＯＷ＋１  ｍｏｄ  １２が０に等しく、ステップ１５６でＣＯＬが１８１に等しいとき）、データＣＲＣシンドロームは、対応するデータセクタの最終シンボルに位置付けられる。例えば、第１のデータセクタの処理が終了すると、データＣＲＣシンドロームは図３Ｂのシンボル１５２に対して位置付けられる。上述のように、それぞれの対応する誤りＣＲＣシンドロームもまた、ＣＲＣ検査を行う前にデータセクタの最終データシンボルに位置付けられる。
【０１１３】
第１のデータセクタの処理が終了すると、図７Ｆのステップ１３６で、ＲＯＷは１２に等しく、ＲＯＷ  ｍｏｄ  １２はゼロに等しい。従って、ステップ１３８で、第１のデータセクタのための現在のデータＣＲＣシンドロームはＳＲＡＭ１５内に保存され、ＤＡＴＡ＿ＲＥＧは、ＳＲＡＭ１５から取り出される、第２のデータセクタのための開始位置により（すなわち、図３Ｂのシンボル１４２に）初期化される。ステップ１４６で、第２のデータセクタのＣＲＣ符号語のためのデータシンボルがデータＣＲＣシンドロームに加えられる。このプロセスは、１６個のデータＣＲＣシンドロームのすべてが生成されＳＲＡＭ１５内に記憶されるまで続く。
【０１１４】
水平および垂直パスの間に誤りＣＲＣシンドロームを生成するフロー図を図７Ｇから図７Ｊに示す。第１の水平パスの間に、図７Ｃのステップ８１で誤りＣＲＣシンドロームが訂正値に更新される（訂正値がゼロの場合も）。図７Ｇのステップ１５９で、現在のパスが水平であるか垂直であるかに依存して分岐が実行される。現在水平パスを行っている場合は、ステップ１６１でＣ＿ＲＯＷが１９１より大きいならば、ＥＣＣ冗長はＣＲＣシンドロームの一部ではないので、誤りＣＲＣシンドロームは更新されない。垂直パスの場合は、ステップ１６２で訂正列Ｃ＿ＣＯＬおよび訂正行Ｃ＿ＲＯＷ  ｍｏｄ  １２がゼロであるならば、ステップ１６４で、誤りＣＲＣシンドロームＥＲＲ＿ＲＥＧを生成するレジスタに、現在のデータセクタに対応するＳＲＡＭ１５からの一部誤りＣＲＣシンドロームがロードされる。
【０１１５】
ステップ１６６で、符号語が訂正不能である（すなわち、訂正不能フラグ（ＣＷ＿ＵＮＣ）が設定される）か、または現在の水平符号語のためのＥＣＣシンドロームがゼロで訂正が不可能であることを示す場合は、ステップ１６８で、符号語が現在のデータセクタの最終水平符号語であるかどうかに依存して分岐が実行される。データセクタの最終符号語である（すなわち、Ｃ＿ＲＯＷ＋１  ｍｏｄ１２がゼロに等しい）場合は、ステップ１６９で、誤りＣＲＣシンドロームを１７１シンボルだけ右にシフトすることによって、現在のデータセクタのための誤りＣＲＣシンドロームが、ＣＲＣ符号語の最終シンボルに（例えば、図３Ｂのシンボル１５８からシンボル１５２に）位置付けられ、Ｃ＿ＣＯＬが１７２に設定される。後述の乗算テーブル数を減らすために、ステップ１６９での誤りＣＲＣシンドロームの１７１シンボルだけ右へのシフトは、誤りＣＲＣシンドロームを１シンボルだけ右にシフトすることを１７１回繰り返すループにおいて実行される。現在の符号語がデータセクタの最終符号語でない場合は、ステップ１７０で、誤りＣＲＣシンドロームは、単に、現在の水平符号語を飛ばすために１行下に調整される。この後、制御は図７Ｅに戻り、データセクタの次の水平符号語の処理を続ける。
【０１１６】
ステップ１６６で、符号語訂正不能フラグ（ＣＷ＿ＵＮＣ）が設定されず、且つ現在の水平符号語のためのＥＣＣシンドロームがゼロでない場合は、図７Ｈのステップ１７２で、現在の訂正列Ｃ＿ＣＯＬの値に基づいて分岐が実行される。Ｃ＿ＣＯＬが０から１７１である場合は、現在の水平符号語の最初のデータシンボルを処理していないならば（すなわち、ステップ１７４でＣ＿ＣＯＬが０でないならば）、ステップ１７６で誤りＣＲＣシンドロームが１シンボル（１列）だけ右に調整され、ステップ１７８で現在のデータシンボルのための訂正値が誤りＣＲＣシンドロームに加えられる。このプロセスは、現在の水平符号語のための訂正値のすべてが、誤りＣＲＣシンドロームに加えられるまで続く。水平符号語のＥＣＣシンボルは（ステップ１７２でＣ＿ＣＯＬが１７３から１８０であるときは）、上述のようにこれらはＣＲＣ符号語の一部ではないため、誤りＣＲＣシンドロームには加えられない。現在の水平符号語の最終データシンボルが処理されると（すなわち、ステップ１７２でＣ＿ＣＯＬが１７２に等しいとき）、ステップ１８０で、誤りＣＲＣシンドロームが、現在の水平符号語が現在のデータセクタの最終符号語であるかどうかに基づいて調整される。符号語がデータセクタの最終水平符号語ではない場合は（すなわち、ステップ１８０で（ＲＯＷ＋１）ｍｏｄ  １２が０ではない場合は）、ステップ１８２で、誤りＣＲＣシンドロームは１シンボルだけ右に調整され、これにより次の水平符号語の最初のシンボルに対して位置付けられる。現在の水平符号語が現在のデータセクタの最終符号語である場合は、ステップ１８１で、ＤＡＴＡ＿ＲＥＧが現在のデータセクタのためのデータＣＲＣシンドロームと共にＳＲＡＭ１５からロードされ、ＥＲＲ＿ＲＥＧと組み合わされる。上述のように結果が疑似ランダムシーケンスにわたってＣＲＣに等しくない場合は、ステップ１８３でブロック訂正不能フラグ（ＢＬＫ＿ＵＮＣフラグ）が設定される。次に、ステップ１８４で、誤りＣＲＣシンドロームは１２行だけ上におよび１シンボルだけ右に調整されて、データセクタの最初のシンボルに対して再配置される。例えば、誤りＣＲＣシンドロームが、図３Ｂの第１のデータセクタのＣＲＣ符号語の最終シンボル１５２に位置する場合、ステップ１８４で誤りＣＲＣシンドロームを１２行だけ上におよび１シンボルだけ右に調整することにより、誤りＣＲＣシンドロームはデータセクタの最初のシンボル１６０に位置付けられる。次にステップ１８５で、現在のデータセクタのための誤りＣＲＣシンドローム（ＥＲＲ＿ＲＥＧに記憶）がＳＲＡＭ１５内に再び記憶される。
【０１１７】
図７Ｇおよび図７Ｈの誤りＣＲＣ更新手順は、図３Ａの１６個のデータセクタすべてに対して誤りＣＲＣシンドロームが生成され、疑似ランダムシーケンスにわたってＣＲＣと比較されるまで繰り返される。第１の水平パスの終了時に、図７Ｋのステップ２５４でＢＬＫ＿ＵＮＣフラグが調べられ、積符号の訂正の有効性および完全性が確認される。誤りが残っている場合には、垂直パスが実行され、図７Ｄのステップ１０４で（または、垂直符号語が飛ばされる場合はステップ９５で）、図７Ｉの誤りＣＲＣ更新手順が実行されて、誤りＣＲＣシンドロームを、垂直符号語に適用された訂正値により更新する。
【０１１８】
図７Ｇのステップ１５９で、制御は図７Ｉに分岐して、垂直パスのための誤りＣＲＣシンドロームを更新する。図７Ｉのステップ１８６で現在の訂正列Ｃ＿ＣＯＬが１７１より大きい場合は、水平ＥＣＣシンボルに対する垂直符号語はＣＲＣ符号語に含まれないため、何も更新されない。ステップ１８６でＣ＿ＣＯＬが１７２より小さい場合は、ステップ１８８で検査が行われ、誤りＣＲＣシンドロームが、現在の垂直符号語を下向きに進行して現在のデータセクタの最終行に到達したかどうかを決定する。現在の訂正行Ｃ＿ＲＯＷ  ｍｏｄ  １２がゼロに等しい場合は、ステップ１９０で、現在のデータセクタのための一部誤りＣＲＣシンドロームがＳＲＡＭ１５から取り出され、ＥＲＲ＿ＲＥＧにロードされる。
【０１１９】
ステップ１９２で符号語訂正不能誤りフラグ（ＣＷ＿ＵＮＣ）が設定されているか、または現在の垂直符号語のためのＥＣＣシンドロームがゼロである場合は、図７Ｊのフロー図が実行されて、誤りＣＲＣシンドロームを１シンボルだけ右に調整する（すなわち、現在の垂直符号語が飛ばされる）。ステップ１９３でＣ＿ＣＯＬが１７１に等しくない場合は（すなわち、データセクタの最終垂直符号語を処理していない場合は）、ステップ１９４で、第１のデータセクタのための誤りＣＲＣシンドロームが１シンボル（１列）だけ右に調整される。ステップ１９６で現在のデータセクタのための一部誤りＣＲＣシンドロームがＳＲＡＭ１５内に記憶され、ステップ１９７でＣ＿ＲＯＷが１２だけインクリメントされる。すなわち次のデータセクタに移される。ステップ１９８でＣ＿ＲＯＷが１９１より大きくない場合は、ステップ２００でＥＲＲ＿ＲＥＧが次のデータセクタのための一部誤りＣＲＣシンドロームと共にＳＲＡＭ１５からロードされ、ステップ１９４でこの誤りＣＲＣシンドロームが１シンボルだけ右に調整され、ステップ１９６でＳＲＡＭ１５内に再記憶される。このループは、ステップ１９８でＣ＿ＲＯＷが１９１より大きくなるまで繰り返され、１９１より大きくなると、すべての誤りＣＲＣシンドロームが１シンボル（１列）だけ右に調整されて、現在の垂直符号語が飛ばされる。
【０１２０】
図７Ｊのステップ１９３でＣ＿ＣＯＬが１７１に等しい場合は、最終垂直符号語（ＥＣＣ冗長の前）は飛ばされることになる。従って、各データセクタのための最終ＣＲＣシンドロームを各データセクタのために生成し、誤りが残っている場合はＢＬＫ＿ＵＮＣフラグを設定する必要がある。ステップ２０１で、現在のデータセクタ（ＥＲＲ＿ＲＥＧに記憶）のための誤りＣＲＣシンドロームが１１データシンボルだけ下に（例えば、図３Ｂのシンボル１４８からシンボル１５２に）調整される。ステップ２０１は実際には、ＥＲＲ＿ＲＥＧを１シンボル（Ｄ１）だけ下に調整するのを１１回繰り返すループとして実現される。次にステップ２０３で、ＤＡＴＡ＿ＲＥＧが、ＳＲＡＭ１５からの現在のデータセクタのためのデータＣＲＣシンドロームにより初期化され、ＤＡＴＡ＿ＲＥＧをＥＲＲ＿ＲＥＧと組み合わせることによって最終ＣＲＣシンドロームが生成される。最終ＣＲＣシンドロームが疑似ランダムシーケンスにわたってＣＲＣに等しくない場合は、ステップ２０５でブロック訂正不能フラグ（ＢＬＫ＿ＵＮＣ）が設定される。ステップ２０７で、誤りＣＲＣシンドロームは、１２行だけ上におよび１データシンボルだけ右に（例えば、図３Ｂのシンボル１５２からシンボル１６０に）調整することによって、データセクタの開始点に調整される。ステップ２００で次のデータセクタのための誤りＣＲＣシンドロームがＥＲＲ＿ＲＥＧにロードされ、上記の手順が繰り返される。ステップ１９８でＣ＿ＲＯＷが１９１より大きい場合は、各データセクタに対してＣＲＣ検査が行われ、誤りＣＲＣシンドロームは各データセクタの開始点に再配置されているはずである。
【０１２１】
再び図７Ｉを参照して、ステップ１９２で、符号語訂正不能フラグ（ＣＷ＿ＵＮＣ）がセットされず、ＥＣＣシンドロームがゼロでなければ、ステップ２０６で分岐が実行され、現在の訂正行Ｃ＿ＲＯＷの値に基づいて誤りＣＲＣシンドロームが更新される。ステップ２０６でＣ＿ＲＯＷが１９２〜２０７であれば、ＣＲＣ符号語にＥＣＣ冗長記号が含まれないため、制御は単に戻るだけである。Ｃ＿ＲＯＷが０〜１９１であれば、現在の誤りＣＲＣシンドロームは、ステップ２０８で１記号だけ下に調整され、ステップ２１０で、次の記号の訂正値が誤りＣＲＣシンドロームに加えられる。誤りＣＲＣシンドロームがデータセクタの最初の行にある場合（即ち、ステップ２１２でＣ＿ＲＯＷｍｏｄ１２がゼロである場合）、誤りＣＲＣシンドロームを１記号だけ下に調整するステップ２０８はスキップされる。
【０１２２】
ステップ２０９で、現在のデータセクタの最後の行に達すると（即ち、Ｃ＿ＲＯＷ＋１ｍｏｄ１２がゼロであれば）、誤りＣＲＣシンドロームは、垂直方向の次の符号語のデータセクタのトップ位置に調整される。これは、ステップ２１１で誤りＣＲＣシンドロームを１記号下（Ｄ１）に調整し、さらに、ステップ２１３で１記号右で１２記号上（ＵＰ１２＿Ｒ１）に調整する。ステップ２１５でＣ＿ＣＯＬが１７１に等しければ、誤りＣＲＣシンドロームは、データセクタの最後の記号の上に配置され、ＣＲＣチェックが行われる。ステップ２１７で、現在のデータセクタのデータＣＲＣシンドロームとともに、ＤＡＴＡ＿ＲＥＧがＳＲＡＭ１５からロードされ、ＥＲＲ＿ＲＥＧと結合され、最終ＣＲＣシンドロームが生成される。最終ＣＲＣシンドロームが疑似ランダムシーケンス上のＣＲＣに等しくなければ、ステップ２１９でブロック訂正不能フラグ（ＢＬＫ＿ＵＮＣ）がセットされる。その後、ステップ２１３で、誤りＣＲＣシンドロームは、１２行上で１データ記号右（ＵＰ１２＿Ｒ１）に動かされ、データセクタの最初の記号上に再配置され（例えば、図３Ｂの記号１５２から記号１６０に動かされ）、ステップ２１４で、現在のデータセクタの誤りＣＲＣシンドローム（ＥＲＲ＿ＲＥＧに格納されている）が、ＳＲＡＭ１５に復元される。
【０１２３】
垂直方向のパスの終わりで、ＢＬＫ＿ＵＮＣフラグが図７Ｋのステップ２５４で検査され、積符号に対する訂正の有効性および完全性が検証される。誤りがまだ残っていれば、水平方向のパスがもう一度行われる。水平方向の符号語のＥＣＣシンドロームがＳＲＡＭ１５に格納されると、図７Ｅのフロー図が実行され、ステップ１１７および１２６で誤りＣＲＣシンドロームが更新される。水平方向の符号語のＥＣＣシンドロームがＳＲＡＭ１５に格納されなければ、図７Ｃのフロー図が実行され、ステップ７１および８１で誤りＣＲＣシンドロームが更新される。
【０１２４】
図７Ｋのフロー図は、積符号が完全に訂正されているかどうか、または、水平方向もしくは垂直方向のパスの終わりで積符号が訂正不可能であるかどうかを判定するステップを示す。ステップ２５２で、システムは、ＥＣＣ＿ＢＵＳＹフラグがクリアされるのを待ってから、ＢＬＫ＿ＵＮＣフラグの検査を行う。ステップ２５４でブロック訂正不能フラグ（ＢＬＫ＿ＵＮＣ）がセットされず、前の水平方向または垂直方向のパスの間に訂正不可能な誤りに遭遇しなかったことが示されると、訂正手順は、従来技術で必要とされるような別のパスを行わずに、ステップ２５８で成功としてフローから出る。
【０１２５】
ステップ２５４でＢＬＫ＿ＵＮＣフラグがセットされると、ステップ２５６でパスカウント変数ＰＡＳＳ＿ＣＮＴがインクリメントされ、ＰＡＳＳ＿ＣＮＴが所定の最大値を上回ると、積符号は訂正不可能となり、訂正手順はステップ２６６で失敗としてフローから出る。ステップ２５６でＰＡＳＳ＿ＣＮＴが所定の最大値未満であり、ステップ２６０で、前の水平方向および垂直方向のパスで変更がなされていなければ（訂正が行われていなければ）、それ以上パスを行っても役に立たないため、訂正手順はステップ２６６で再び失敗としてフローを出る。ステップ２６０で変更がなされていれば、ステップ２６２でＢＬＫ＿ＵＮＣフラグがクリアされ、水平方向または垂直方向のパスをもう一度実行することによって、ステップ２６４で訂正手順が続けられる。
【０１２６】
ＣＲＣシンドロームＳCRCが、積符号の訂正と同時に計算されるため、訂正手順は、水平方向または垂直方向のいずれかのパスの終わりでうまく終了し得る。従って、本発明では、訂正が終了したかどうかを検証するために、従来技術で必要とされていた別のパスが必要でない。さらに、本発明では、データを非ランダム化して訂正プロセスの終わりにＣＲＣシンドロームＳCRCを生成するために必要とされていた別のパスが必要でない。従って、本発明は、光記憶装置のスループットを大幅に増加することにより、従来技術に対する大幅な改良を提供する。
【０１２７】
[ＣＲＣ生成器回路]
図２のＣＲＣ生成器および訂正検証器１９は、書き込み動作の間に、図３Ａに示される１６個のデータセクタについてＣＲＣ冗長記号を生成し、読み出し動作の間に、図７Ａ〜図７Ｊを参照して上で説明したように誤り訂正器１８によって行われた訂正を検証する際に用いられるＣＲＣシンドロームＳCRCを生成する。図８は、書き込み動作の間にＣＲＣ冗長記号を生成するための従来のリニアフィードバックシフトレジスタ（ＬＳＦＲ）を示す。図８に示されるＬＦＳＲの動作は周知であり、このＬＳＦＲは、入力多項式Ｄ（ｘ）を以下に示す生成多項式Ｇ（ｘ）で割る。
【０１２８】
Ｇ（ｘ）＝ｇiｘi＋ｇi-1ｘi-1＋...＋ｇ1ｘ＋ｇ0
入力多項式Ｄ（ｘ）の係数は、ＬＦＳＲを通してシリアルにシフトされる。ここで、シフト数は、入力多項式の次数に１を加えた数に等しい。剰余、即ち、ＣＲＣ冗長は、シフトレジスタの最終状態である。図３Ａに示されるデータセクタの各々についてＣＲＣ冗長を生成するために、データのｋビットは、多項式Ｐ（ｘ）の係数として表される。従って、ＣＲＣ冗長は、以下のように計算される。
【０１２９】
ＣＲＣ冗長＝Ｐ（ｘ）・ｘn-k ｍｏｄＧ（ｘ）
ここで、ｎ−ｋはＣＲＣ冗長記号の数であり、Ｇ（ｘ）は生成多項式である。最後のシフト後のレジスタの内容がＣＲＣ冗長であり、このＣＲＣ冗長はその後、ユーザデータに付加されて、ＣＲＣ符号語を形成する。このＣＲＣ符号語は、積符号に組み込まれて、その後、ディスクに書き込まれる。
【０１３０】
読み出し動作の間、ディスクから読み出されたデータが処理され、以下の式に従ってＣＲＣシンドロームＳCRCが生成される。
【０１３１】
ＣＲＣシンドロームＳCRC＝Ｃ’（ｘ）ｍｏｄＧ（ｘ）
ここで、Ｃ’（ｘ）は、ディスクから読み出されたＣＲＣ符号語（ＣＲＣ冗長を含む）である。従来技術では、誤り訂正器１４が訂正をし終わると、データバッファ１からデータが読み出され、非ランダム化器４によって非ランダム化される。非ランダム化されたデータはその後シリアルに処理されるため、図８の同じＬＦＳＲ回路を用いて、上記式によりＣＲＣシンドロームＳCRCを生成することができる。
【０１３２】
本発明では、図７Ａ〜図７Ｊを参照して説明したように、ＣＲＣシンドロームＳCRCは、積符号の訂正と同時に生成される。従って、データが一連の連続するビットとして処理されないため、ＣＲＣシンドロームＳCRCを生成するために図８のＬＦＳＲ回路を用いることはできない。本発明のＣＲＣシンドローム生成器がどのようにしてＣＲＣシンドロームＳCRCを生成するかを説明する前に、本発明のＣＲＣシンドローム生成器の概要を説明する。
【０１３３】
図９は、ＤＡＴＡCRC回路３００およびＥＲＲＯＲCRC回路３０２を含む、図２のＣＲＣシンドローム生成器１９のブロック図である。図７Ａを参照して上で説明したように、ＤＡＴＡCRCは、ステップ３７で、図２のデータバッファ１から読み出された未訂正のランダム化されたデータを用いて、図３Ａの積符号上の最初の水平方向のパスの間に生成される。ＥＲＲＯＲCRCは、水平方向および垂直方向の符号語の反復処理の間に誤り訂正器１８によって生成される訂正値を用いて生成される。データセクタの終わりに達すると、ＤＡＴＡCRCおよびＥＲＲＯＲCRCは、ＣＯＭＢＩＮＥ回路３０４によって結合され、最終ＣＲＣシンドロームＳCRC３０６が生成される。この最終ＣＲＣシンドロームＳCRC３０６は、比較器３０７で定数と比較され、データセクタがまだ誤りを含んでいるかどうかが判定される。ＣＯＭＢＩＮＥ回路３０４によって行われる数学的機能は、ＤＡＴＡCRCおよびＥＲＲＯＲCRCの単純な排他的ＯＲ（ＸＯＲ）である。
【０１３４】
上述のように、図３Ａの積符号には１６個のデータセクタがある。したがって、ＳＲＡＭ１５に格納されるデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームは１６個である。ＣＲＣチェックは、ＳＲＡＭ１５からデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームをそれぞれ読み出し、これらのデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームをそれぞれＤＡＴＡCRC回路３００およびＥＲＲＯＲCRC回路３０２にロードすることによって、各データセクタについて行われる。比較器３０７は、最終ＣＲＣシンドロームＳCRCを、各データセクタをランダム化するために用いられる疑似ランダムデータシーケンス上のＣＲＣに等しい定数と比較する。疑似ランダムデータシーケンスはブロック（積符号）ごとに異なるため、記憶媒体から新しいブロックが読み出されるたびに、対応するＣＲＣ定数が比較器３０７にロードされる。
【０１３５】
図９のＤＡＴＡCRC回路３００およびＥＲＲＯＲCRC回路３０２は、図１０により詳細に示される。図９のＤＡＴＡCRC回路３００およびＥＲＲＯＲCRC回路３０２は、受け取ったＣＲＣ符号語多項式Ｃ’（ｘ）を、以下のような複数の部分集合多項式の線形結合として表すことによって、データＣＲＣシンドロームおよび誤りＣＲＣシンドロームを生成する。
【０１３６】
Ｃ’（ｘ）＝Ｃj（ｘ）＋Ｃj-1（ｘ）＋...＋Ｃ0（ｘ）
ここで、各部分集合多項式Ｃk（ｘ）は、符号語多項式Ｃ’（ｘ）からの所定のビット数を含む。本明細書に開示される実施形態では、各部分集合多項式は、符号語多項式Ｃ’（ｘ）の８ビットを含み、以下のように１６進法で表される。
【０１３７】
【数２３】
0004346135.tif 000024
このようにして、ＣＲＣシンドロームＳCRCは、概念的に、以下のように各部分集合多項式のＣＲＣシンドロームの線形結合として生成され得る。
【０１３８】
ＣＲＣシンドロームＳCRC＝Ｃ0（ｘ）ｍｏｄＧ（ｘ）＋Ｃ1（ｘ）ｍｏｄＧ（ｘ）＋...＋Ｃj（ｘ）ｍｏｄＧ（ｘ）
上記式は、以下のように表すこともできる。
【０１３９】
【数２４】
0004346135.tif 000025
ここで、
【数２５】
0004346135.tif 000026
は、符号語Ｃ’（ｘ）からの８ビットの多項式である（即ち、
【数２６】
0004346135.tif 000027
である）。本発明で用いられる別の数学的関係は、以下の式である。
【０１４０】
【数２７】
0004346135.tif 000028
再び図３Ｂを参照して、上記式を用いて、水平方向の符号語上の最初のパスの間の最初のデータセクタの最初の記号１６０についてのデータＣＲＣシンドロームが計算される。最初の記号１６０は、上記符号語Ｃ’（ｘ）の最も有意な係数、および上記部分集合多項式Ｃj（ｘ）のゼロでない係数を含む。最初の記号１６０は、（加算器３１０で、最上位ビットにゼロをパディング（zero padding）し、ゼロを加えた後に）図１０の３２ビットレジスタ３０８にロードされる。その後、図３Ｂの符号語の次の記号１４０が読み出され、乗算器３１２で、レジスタ３０８の内容にｘK ｍｏｄＧ（ｘ）が掛けられ、データＣＲＣシンドロームが１記号右にシフトされる（即ち、図７Ｆのステップ１４６でＫ＝Ｒ１である）。その後、乗算結果は、（加算器３１０で符号語の次の記号１４０を加算して、その特定の部分集合多項式についてのＣＲＣシンドローム計算を開始した後に）レジスタ３０８に再ロードされる。この計算は、残りの記号に対して行われ、図３Ｂの水平方向の最初の符号語の最後の記号１４８が読み出されるまで続けられる。その後、ＣＲＣシンドロームは、レジスタ３０８の内容にｘK ｍｏｄＧ（ｘ）を掛けることによって、図３Ｂの場所１５０に調整される。ここで、Ｋは、１つ右の記号に等しい（即ち、上記図７Ｆのステップ１４６でＫ＝Ｒ１である）。オフセットＫの適切な値は、図１０の乗算器３１２のＳＥＬ制御ラインを介して選択される。
【０１４１】
このプロセスは、図３Ｂの最初のデータセクタの水平方向の最後の符号語の最後の記号が読み出されるまで続けられ、レジスタ３０８は、ＣＲＣ符号語Ｃ’（ｘ）の最初の記号（即ち、部分集合多項式Ｃj（ｘ））についてのデータＣＲＣシンドロームであって、その他の記号（即ち、その他の部分集合多項式）について計算されたデータＣＲＣシンドロームに加えられるデータＣＲＣシンドロームを含み、これにより、最初のデータセクタのＣＲＣ符号語Ｃ’（ｘ）全体についてのデータＣＲＣシンドロームを生成する。この時、最初のデータセクタについてのデータＣＲＣシンドロームは、図３Ｂの最後の記号１５２に配置される。図７Ｆのフロー図が再び実行され、次のデータセクタの最初の記号２０４が処理されると、図７Ｆのステップ１３８で、最初のデータセクタについてのデータＣＲＣシンドロームがＳＲＡＭ１５に格納され、次のデータセクタの最初の記号２０４がレジスタ３０８にロードされる。上記プロセスは、２番目およびそれ以降のデータセクタについても繰り返され、最初の水平方向のパスの終わりで、１６個のデータＣＲＣシンドロームがすべて生成され、ＳＲＡＭ１５に格納される。
【０１４２】
誤りＣＲＣを生成するための図９のＥＲＲＯＲCRC回路３０２はまた、図１０の回路を含む。図２の誤り訂正器１８によって訂正値が生成されると、この訂正値は、加算器３１０でレジスタ３０８に加えられる。乗算器３１２は、水平方向または垂直方向の符号語の各記号が処理されているとき、訂正値が生成されるかどうかに関わらず（即ち、訂正値がゼロであっても）、レジスタ３０８の内容への適切なＫオフセットの乗算を続ける。各データセクタの終わりで、データＣＲＣシンドロームおよび誤りＣＲＣシンドロームが結合され、最終ＣＲＣシンドロームＳCRCJが生成される。上述のように、この最終ＣＲＣシンドロームＳCRCJは、訂正の有効であるかどうかおよび完全であるかどうかを判断するために用いられる。
【０１４３】
図１０のｘK ｍｏｄＧ（ｘ）乗算器３１２を実現するための好適な実施形態は、図１１を参照して理解される。図１１は、ｘK+i ｍｏｄＧ（ｘ）という計算によって生成される剰余のテーブルを表す。ここで、ｉは｛０，...，３１｝に等しい。図１１のテーブルは、ＣＲＣシンドロームの計算中に用いられるＫオフセット値（即ち、Ｒ１、Ｄ１およびＵＰ１２＿Ｒ１）の各々について生成される。その後、図１０のレジスタ３０８の内容に適切なテーブルを掛けることによって（即ち、３２ビットベクトルに３２×３２行列を掛けることによって）乗算が行われる。
【０１４４】
３２ビットＣＲＣ生成多項式Ｇ（ｘ）についてのｘK ｍｏｄＧ（ｘ）の乗算を実現するための実際のテーブルは、図１３Ａ〜図１３ＥのＶＨＤＬソースコードに示される。「ｃｏｎｓｔａｎｔ  ｒ１＿ｄｖｄ＿ｔｂｌ」として示されたテーブルは、１記号右へのシフト（Ｒ１）調整を実現し、「ｃｏｎｓｔａｎｔ  ｄ１＿ｄｖｄ＿ｔｂｌ」として示されたテーブルは、１行下へのシフト（Ｄ１）調整を実現し、「ｃｏｎｓｔａｎｔ  ｕ１２ｒ１＿ｄｖｄ＿ｔｂｌ」として示されたテーブルは、１２記号上、１記号右のシフト（ＵＰ１２＿Ｒ１）調整を実現する。
【０１４５】
図１３Ａ〜図１３ＥのＶＨＤＬソースコードの残りは、図１０のレジスタ３０８の内容に適切なテーブルを掛ける（即ち、３２ビットベクトルに３２×３２行列を掛ける）ことによって、実際の乗算を実行する。入力レジスタ即ちベクトルと行列との積が、出力ベクトルであり、出力ベクトルの各要素は、テーブル（即ち、行列）のｉ番目の行のｎ個の要素と、レジスタ（即ち、列入力ベクトル）の対応する成分との積の和を求めることによって生成される。この和は、以下のように表すことができる。
【０１４６】
【数２８】
0004346135.tif 000029
ここで、ｙiは、乗算器３１２の出力ベクトルであり、ａikは、図１１のテーブルのｉ番目の行の３２ビットであり、ｘkは、図１０のレジスタ３０８に格納された３２ビットである。乗算器３１２からの出力ベクトルｙiは、加算器３１０で入力ビットに加えられ、その結果が、レジスタ３０８に格納される。
【０１４７】
[ＳＲＡＭ]
図２のＳＲＡＭ１５の構造および動作は、図１２Ａを参照して理解される。上述のように、ＳＲＡＭ１５は、動作モードに依存して２つの機能を実行する。即ち、ＣＤモードでは、ＳＲＡＭ１５は、Ｃ１／Ｃ２符号化のためのデータバッファ処理を与え、ＤＶＤモードでは、ＳＲＡＭ１５は、積符号についてのＥＣＣシンドロームと、ＣＲＣ検証符号についてのＣＲＣシンドロームとを格納する。ＤＶＤモードの場合の好適な実施形態では、図３Ａに示される積符号の垂直方向のＥＣＣシンドロームが１８２個だけ、１６個のデータセクタに対応する１６個のＣＲＣシンドロームとともに、ＳＲＡＭ１５に格納される。ＤＶＤ積符号の２０８個の水平方向のＥＣＣシンドロームは、水平方向のパスの各々で再生成され、ＳＲＡＭ１５には格納されない。当業者は、この構成が単に特定の実施形態であって、ＳＲＡＭ１５の容量を、垂直方向および水平方向のＥＣＣシンドローム、およびＣＲＣシンドロームを格納するように増加させることができることを認識するであろう。
【０１４８】
図１２Ａを参照して、ＳＲＡＭ１５は、好ましくは、１６個の２５６×８ビットメモリセル３１４0〜３１４15のバンクとして実現される。各メモリセルは、２５６データバイトにアクセスするための８ビット入力アドレスと、アドレス指定されたデータバイトを出力するための８ビット出力バスとを含む。アドレス復号化器３１６は、制御ライン３１７を介して構成される動作モードに依存して、１２ビットアドレス３１８を復号化する。ＣＤモードの場合、メモリセル３１４0〜３１４15のバンクは、４ｋ×８ビットバッファとしてアドレス指定される。即ち、アドレス３１８の１２ビットを全部用いて、Ｃ１／Ｃ２復号化のための８ビットの１データバイトにアクセスする。アドレス３１８の最初の８ビットは、メモリセル３１４0〜３１４15の各々から同じデータバイトを選択するために用いられる。メモリセルの出力は、トライステートバッファ３２０0〜３２０15を介してワイアードＯＲされる（wireored）。アドレス３１８の残りの４ビットを用いて、適切なトライステートバッファがイネーブルされ、それにより、バス３２２上に、Ｃ１／Ｃ２復号化に用いられる適切なデータバイトをアサートする。
【０１４９】
ＤＶＤモードの場合、ＳＲＡＭ１５は、２５６×１２８バッファとしてアドレス指定される。即ち、アドレス３１８の最初の８ビットだけを用いて、メモリセル３１４0〜３１４15の各々から同じデータバイトを選択する。各メモリセルから出力される１６データバイトは、３２４で結合され、図５および図６Ｂに示されるような垂直方向の符号語の１６個のＥＣＣシンドロームを形成するか、または、図３Ａに示されるデータセクタについてのＣＲＣシンドロームの４バイトを形成する。
【０１５０】
ＤＶＤモードの場合の垂直方向のＥＣＣシンドロームおよびＣＲＣシンドロームの好適なマッピングは、図１２Ｂに示される。最初の１８２個のアドレスが、１８２個の垂直方向の符号語の１６個のＥＣＣシンドロームを格納するために用いられる。次の１０個のアドレスはスキップされ、アドレス１９２〜２０７は、図３ＡのＤＶＤ積符号の１６個のデータセクタについての４バイトのデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームを１６個格納するために用いられる。アドレス１９２〜２０７を用いてデータＣＲＣシンドロームおよび誤りＣＲＣシンドロームにアクセスすることにより、アドレスの３つの最下位ビットしか変わらないため、複号化回路が簡略化される。ＳＲＡＭ１５の残りは、ＤＶＤモードでは使用されない。
【０１５１】
本発明の目的は、本明細書に開示された実施形態により十分に実現されている。当業者は、本発明の本質的な機能から逸脱することなく、様々な実施形態によって本発明の様々な局面を達成することができることを認識するであろう。例えば、図３Ａに示される積符号は、典型的にはデジタルビデオディスク（ＤＶＤ）で用いられるが、本発明は、コンパクトディスク（ＣＤ）に用いられるフォーマットを含む他の積符号フォーマットに等しく適用可能である。さらに、本発明は、積符号だけでなく、他の多次元符号にも適用され得る。このように、本明細書に開示された特定の実施形態は例示的なものであって、前掲の特許請求の範囲によって適切に解釈される本発明の範囲を限定することを意味するものではない。
【０１５２】
【発明の効果】
本発明によれば、少なくとも以下の効果が得られる。
【０１５３】
まず、ランダム化データに対してＣＲＣ検査を行うことによって、ＣＲＣシンドロームを生成する前にデータを非ランダム化するためのデータバッファへのアクセスに関連する待ち時間が避けられる。
【０１５４】
さらに、ＰおよびＱ符号語の訂正と同時に実行中にＣＲＣシンドロームを生成することにより、ＣＲＣ符号語を処理した直後に、訂正の有効性および完全性を検査するためにＣＲＣシンドロームを利用可能にする。これにより、ＣＲＣシンドロームを生成するためにデータバッファにアクセスする必要がなくなる。
【図面の簡単な説明】
【図１】ＣＤ／ＤＶＤ光記憶装置において典型的に用いられる従来の誤り訂正システムのブロック図である。
【図２】ランダムデータに対して実行中にＣＲＣシンドロームを生成するＣＲＣ生成器および訂正検証器を有する、本発明の誤り訂正システムのブロック図である。
【図３Ａ】１６個のデータセクタを有するＤＶＤ光記憶装置において典型的に用いられる積符号のフォーマットを示す図である。
【図３Ｂ】図３Ａの積符号の最初の２つのデータセクタのフォーマットを示す図である。
【図３Ｃ】本発明において用いられるデータランダム化器／非ランダム化器の詳細を示す図である。
【図３Ｄ】本発明において用いられるデータランダム化器／非ランダム化器の詳細を示す図である。
【図４】本発明の第１実施態様による水平符号語誤りシンドロームを生成する詳細な回路を示す図である。
【図５】水平符号語に対する誤りシンドロームの生成と同時に、垂直符号語誤りシンドロームを生成する詳細な回路を示す図である。
【図６Ａ】本発明の他の実施態様について、シンドロームバッファが、水平および垂直符号語の両方に対する誤りシンドロームを記憶するとき、水平および垂直誤りシンドロームをそれぞれ更新する回路を示す図である。
【図６Ｂ】本発明の他の実施態様について、シンドロームバッファが、水平および垂直符号語の両方に対する誤りシンドロームを記憶するとき、水平および垂直誤りシンドロームをそれぞれ更新する回路を示す図である。
【図７Ａ】本発明の誤り訂正システムによって実行されるステップの概略を示す流れ図である。
【図７Ｂ】水平符号語に対する第１パスの間に水平および垂直誤りシンドロームを同時に生成し、積符号に対する訂正の有効性および完全性を検査するためのＣＲＣシンドロームを同時に生成するための流れ図である。
【図７Ｃ】第１（および次の）水平パスの間水平符号語を訂正し、訂正値を用いてシンドロームバッファおよびＣＲＣ誤りレジスタにおいて記憶される垂直誤りシンドロームを更新するための流れ図である。
【図７Ｄ】シンドロームバッファに記憶される垂直誤りシンドロームを用いて垂直パス中に垂直符号語を訂正し、訂正値を用いてシンドロームバッファおよびＣＲＣ誤りレジスタに記憶される水平誤りシンドロームを更新するための流れ図である。
【図７Ｅ】シンドロームバッファに記憶される水平誤りシンドロームを用いて次の水平パス中に水平符号語を訂正し、訂正値を用いてシンドロームバッファおよびＣＲＣ誤りレジスタに記憶される垂直誤りシンドロームを更新するための流れ図である。
【図７Ｆ】全積符号に対する第１水平パス中にデータＣＲＣシンドロームを生成するための流れ図である。
【図７Ｇ】水平パス中に訂正値を用いて誤りＣＲＣシンドロームを更新するための流れ図である。
【図７Ｈ】水平パス中に訂正値を用いて誤りＣＲＣシンドロームを更新するための流れ図である。
【図７Ｉ】垂直パス中に訂正値を用いて誤りＣＲＣシンドロームを更新するための流れ図である。
【図７Ｊ】垂直パス中に訂正値を用いて誤りＣＲＣシンドロームを更新するための流れ図である。
【図７Ｋ】ＣＲＣデータレジスタの内容とＣＲＣ誤りレジスタの内容とを組合せ、水平および垂直パスの終わりにおける訂正の有効性および完全性を検査するための最終ＣＲＣシンドロームを生成する流れ図である。
【図８】書込み動作中にＣＲＣ冗長を生成し、読出し動作中にＣＲＣシンドロームを生成するのに用いられる従来のリニアフィードバックシフトレジスタ（ＬＦＳＲ）を示す図である。
【図９】ＣＲＣシンドロームのデータパートを計算するためのＤＡＴＡCRC回路と、ＣＲＣシンドロームの誤り部分を計算するためのＥＲＲＯＲCRC回路と、ＤＡＴＡCRCレジスタとＥＲＲＯＲCRCレジスタとを組合せて、ランダムデータパターンに対するＣＲＣと等しい定数と比較される最終ＣＲＣシンドロームＳCRCを生成するための回路とを有するＣＲＣ訂正検証回路のブロック図である。
【図１０】図９のＤＡＴＡCRC／ＥＲＲＯＲCRC回路の詳細なブロック図である。
【図１１】乗算器がｘK ＭＯＤ  Ｇ（ｘ）を計算するためのマトリクスの一般的な形態を示す図である。
【図１２Ａ】ＳＲＡＭの構造、ならびにＣＤフォーマット用および積符号に対する部分シンドロームを記憶するためのＣ１／Ｃ２符号、およびＤＶＤフォーマット用のＣＲＣ検証符号を復号化する間にどのようにＳＲＡＭが構成されるかを示す図である。
【図１２Ｂ】本発明の好ましい実施態様における垂直ＥＣＣシンドロームおよびＣＲＣ検証シンドロームのＳＲＡＭマッピングを示す図である。
【図１３Ａ】３２ビットＣＲＣ生成多項式Ｇ（ｘ）についてのｘK ｍｏｄＧ（ｘ）の乗算を実現するための実際のテーブルを生成するＶＨＤＬソースコードを示す図である。
【図１３Ｂ】３２ビットＣＲＣ生成多項式Ｇ（ｘ）についてのｘK ｍｏｄＧ（ｘ）の乗算を実現するための実際のテーブルを生成するＶＨＤＬソースコードを示す図である。
【図１３Ｃ】３２ビットＣＲＣ生成多項式Ｇ（ｘ）についてのｘK ｍｏｄＧ（ｘ）の乗算を実現するための実際のテーブルを生成するＶＨＤＬソースコードを示す図である。
【図１３Ｄ】３２ビットＣＲＣ生成多項式Ｇ（ｘ）についてのｘK ｍｏｄＧ（ｘ）の乗算を実現するための実際のテーブルを生成するＶＨＤＬソースコードを示す図である。
【図１３Ｅ】３２ビットＣＲＣ生成多項式Ｇ（ｘ）についてのｘK ｍｏｄＧ（ｘ）の乗算を実現するための実際のテーブルを生成するＶＨＤＬソースコードを示す図である。
【符号の説明】
１  データバッファ
３  ライン
４  ランダム化器／非ランダム化器
７  Ｃ１符号化器／復号化器
８  Ｃ２符号化器／復号化器
９  インターリーブ器／非インターリーブ器
１５  ＳＲＡＭ
１６  Ｐ／Ｑ復号化器
１７  ＥＣＣ／シンドローム生成器
１８  誤り訂正器
１９  ＣＲＣ生成器および訂正検証器
２０  ライン
２１  ライン
【図１】
0004346135.tif 000030
【図２】
0004346135.tif 000031
【図３Ａ】
0004346135.tif 000032
【図３Ｂ】
0004346135.tif 000033
【図３Ｃ】
0004346135.tif 000034
【図３Ｄ】
0004346135.tif 000035
【図４】
0004346135.tif 000036
【図５】
0004346135.tif 000037
【図６Ａ】
0004346135.tif 000038
【図６Ｂ】
0004346135.tif 000039
【図７Ａ】
0004346135.tif 000040
【図７Ｂ】
0004346135.tif 000041
【図７Ｃ】
0004346135.tif 000042
【図７Ｄ】
0004346135.tif 000043
【図７Ｅ】
0004346135.tif 000044
【図７Ｆ】
0004346135.tif 000045
【図７Ｇ】
0004346135.tif 000046
【図７Ｈ】
0004346135.tif 000047
【図７Ｉ】
0004346135.tif 000048
【図７Ｊ】
0004346135.tif 000049
【図７Ｋ】
0004346135.tif 000050
【図８】
0004346135.tif 000051
【図９】
0004346135.tif 000052
【図１０】
0004346135.tif 000053
【図１１】
0004346135.tif 000054
【図１２Ａ】
0004346135.tif 000055
【図１２Ｂ】
0004346135.tif 000056
【図１３Ａ】
0004346135.tif 000057
【図１３Ｂ】
0004346135.tif 000058
【図１３Ｃ】
0004346135.tif 000059
【図１３Ｄ】
0004346135.tif 000060
【図１３Ｅ】
0004346135.tif 000061