(57)【特許請求の範囲】
【請求項１】
ECC復号化器によって行われる誤り訂正符号(ECC)に対する訂正を検査するための訂正検査器であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、該ECC復号化器が、所定の条件が満たされた場合に、符号語を飛ばし、
（ａ）該多次元符号におけるデータに応答して計算され、該ECC復号化器が、該多次元符号における該データを処理するときに時間的に近接して計算される検査値を記憶するための少なくとも１つのレジスタと、
（ｂ）該ECC復号化器が、該多次元符号における符号語を飛ばすときに、オフセット値に従って該検査値を調整するためのオフセットコントローラと、
（ｃ）該ECC復号化器が該多次元符号の処理を終了するとき、最終の検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効であるか否かを示す、比較器と、
を有する訂正検査器。
【請求項２】
前記検査値が、一次元符号に従って、前記多次元符号における前記データにわたって生成される、請求項１に記載の訂正検査器。
【請求項３】
前記一次元符号がCRC符号である、請求項２に記載の訂正検査器。
【請求項４】
前記オフセットコントローラが、前記検査値を、XK mod G(x)で乗算し、ここで、Kが、前記ECC復号化器が符号語を飛ばすときに前記多次元符号における飛ばしたシンボルの数に対応する前記オフセット値であり、G(x)が、前記一次元符号の生成器多項式である、請求項２に記載の訂正検査器。
【請求項５】
（ａ）前記多次元符号が、複数の列符号語および複数の行符号語を含む積符号であり、
（ｂ）１つの飛ばした列符号語に対応する前記オフセット値が、行符号語の１つのシンボルである、請求項２に記載の訂正検査器。
【請求項６】
（ａ）前記多次元符号が、複数の列符号語および複数の行符号語を含む積符号であり、
（ｂ）１つの飛ばした行符号語に対応する前記オフセット値が、行符号語におけるシンボルの数および行符号語の数に対して計算される、請求項２に記載の訂正検査器。
【請求項７】
前記検査値が、第１および第２の検査値を含み、前記少なくとも１つのレジスタが、
（ａ）前記多次元符号のシンボルに応答して該第１の検査値を記憶するデータレジスタと、
（ｂ）前記ECC復号化器によって生成される訂正値に応答して該第２の検査値を記憶するための誤りレジスタと、
を有する、請求項１に記載の訂正検査器。
【請求項８】
（ａ）前記第１の検査値が、前記ECC復号化器によって前記第１のセットの符号語にわたって第１のパスの間計算され、
（ｂ）前記第２の検査値が、前記多次元符号におけるデータを訂正する前記ECC復号化器と時間的に近接して計算される、請求項７に記載の訂正検査器。
【請求項９】
前記第１の検査値および前記第２の検査値を組み合わせて、前記最終の検査値を生成する手段をさらに有する、請求項７に記載の訂正検査器。
【請求項１０】
前記ECC復号化器によって生成される訂正値を前記オフセット値によって調整される前記検査値に加えるためのmod-2加算器をさらに有し、該加算の結果が、前記レジスタに記憶される該検査値と置換される、請求項１に記載の訂正検査器。
【請求項１１】
ECC復号化器によって行われる誤り訂正符号（ECC) に対する訂正を検査する方法であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、該ECC復号化器が、所定の条件が満たされる場合に、符号語を飛ばし、
（ａ）該多次元符号におけるデータに応答し、かつ、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して、検査値を計算するステップと、
（ｂ）該ECC復号化器が、該多次元符号における符号語を飛ばすときに、オフセット値に従って該検査値を調整するステップと、
（ｃ）該ECC復号化器が該多次元符号の処理を終了するとき、最終の検査値と所定値とを比較するステップであって、該比較の結果が、該ECC復号化器によって行われる訂正が有効であるか否かを示す、ステップと、
を包含する方法。
【請求項１２】
前記検査値が、一次元符号に従って、前記多次元符号における前記データにわたって生成される、請求項11に記載の方法。
【請求項１３】
前記一次元符号がCRC符号である、請求項12に記載の方法。
【請求項１４】
前記オフセット値が、前記検査値を、XK mod G(x)で乗算することによって計算され、ここで、Kが、前記ECC復号化器が符号語を飛ばすときに前記多次元符号における飛ばしたシンボルの数に対応する前記オフセット値であり、G(x)が、前記一次元符号の生成器多項式である、請求項12に記載の方法。
【請求項１５】
（ａ）前記多次元符号が、複数の列符号語および複数の行符号語を含む積符号であり、
（ｂ）１つの飛ばした列符号語に対応する前記オフセット値が、行符号語の１つのシンボルである、請求項12に記載の方法。
【請求項１６】
（ａ）前記多次元符号が、複数の列符号語および複数の行符号語を含む積符号であり、
（ｂ）１つの飛ばした行符号語に対応する前記オフセット値が、行符号語におけるシンボルの数および行符号語の数に対して計算される、請求項12に記載の方法。
【請求項１７】
前記検査値が、第１および第２の検査値を含み、
（ａ）前記多次元符号のシンボルに応答して該第１の検査値を計算するステップと、
（ｂ）前記ECC復号化器によって生成される訂正値に応答して該第２の検査値を計算するステップと、
をさらに包含する、請求項11に記載の方法。
【請求項１８】
（ａ）前記第１の検査値が、前記ECC復号化器によって前記第１のセットの符号語にわたって第１のパスの間計算され、
（ｂ）前記第２の検査値が、前記ECC復号化器が前記多次元符号におけるデータを訂正する時と時間的に近接して計算される、請求項17に記載の方法。
【請求項１９】
前記第１の検査値と前記第２の検査値とを組み合わせて、前記最終の検査値を生成するステップをさらに包含する、請求項17に記載の方法。
【請求項２０】
前記検査値を調整するステップが、
（ａ）前記ECC復号化器によって生成されるmodulo-2訂正値を、前記オフセット値によって調整される該検査値に加えるステップと、
（ｂ）該検査値を該加算の結果と置換するステップと、
をさらに包含する、請求項11に記載の方法。
【請求項２１】
第２のセットの符号語を交差する第１のセットの符号語を含む多次元誤り訂正符号（ECC) における誤りを訂正するための誤り検出および訂正（EDAC) システムであって、
（ａ）該多次元符号の該第１および第２のセットの符号語を記憶するためのデータバッファと、
（ｂ）該第１および第２のセットの符号語を繰り返しパスにおいて該バッファから読み出すためのECC復号化器であって、該ECC復号化器が、所定の条件が満たされる場合、符号語を該バッファから読み出さない、ECC復号化器と、
（ｃ）該多次元符号におけるデータに応答して計算される検査値および該ECC復号化器によって生成される訂正値を記憶するための少なくとも１つのレジスタであって、該検査値が、該ECC復号化器が、該多次元符号の該データを該バッファから読み出すときに時間的に近接して計算される、レジスタと、
（ｄ）該ECC復号化器が、該多次元符号における符号語を該バッファから読み出さないときに、オフセット値に従って該検査値を調整するためのオフセットコントローラと、
（ｅ）該ECC復号化器が、該多次元符号の処理を終了するときに、最終の検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効が否かを示す、比較器と、
を有する、誤り検出および訂正（EDAC）システム。
【請求項２２】
前記検査値が、一次元符号に従って前記多次元符号における前記データにわたって生成される、請求項21に記載の誤り検出および訂正（EDAC) システム。
【請求項２３】
前記一次元符号がCRC符号である、請求項22に記載の誤り検出および訂正（EDAC)システム。
【請求項２４】
前記オフセットコントローラが、前記検査値を、XK mod G(x)で乗算し、ここで、Kが、前記ECC復号化器が符号語を前記バッファから読み出さないときに前記多次元符号における飛ばしたシンボルの数に対応する前記オフセット値であり、G(x)が、前記一次元符号の生成器多項式である、請求項22に記載の誤り検出および訂正（EDAC) システム。
【請求項２５】
ECC復号化器によって行われる誤り訂正符号（ECC) に対する訂正を検査するための訂正検査器であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、
（ａ）該多次元符号におけるデータに応答して計算され、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して計算される検査値を記憶するための少なくとも１つのレジスタと、
（ｂ）該ECC復号化器が、少なくとも２つの該パスに対する該第１のセットの符号語の処理を終了した後、最終の検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効かつ完了したか否かを示す、比較器と、
を有する訂正検査器。
【請求項２６】
前記多次元符号が、光ディスク記憶装置において用いられる積符号である、請求項25に記載の誤り訂正検査器。
【請求項２７】
訂正不可能な誤りが、前記ECC復号化器によって、前記第１のセットの符号語の直前のパスにおいて検出された場合、前記最終検査値が、前記所定値と比較される、請求項25に記載の誤り訂正検査器。
【請求項２８】
ECC復号化器によって行われる誤り訂正符号(ECC)に対する訂正を検査する方法であって、前記ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、
（ａ）該多次元符号におけるデータに応答し、かつ、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して、検査値を計算するステップと、
（ｂ）該ECC復号化器が少なくとも２つの該パスに対する該第１のセットの符号語の処理を終了した後、最終の検査値と所定値とを比較するステップであって、該比較の結果が、該ECC復号化器によって行われる訂正が有効であるか否かを示す、ステップと、
を包含する方法。
【請求項２９】
前記多次元符号が、光ディスク記憶装置において用いられる積符号である、請求項28に記載の方法。
【請求項３０】
訂正不可能な誤りが、前記ECC復号化器によって、前記第１のセットの符号語の直前のパスにおいて検出された場合、前記最終検査値が、前記所定値と比較される、請求項28に記載の方法。
【請求項３１】
ECC復号化器によって行われる誤り訂正符号（ECC) に対する訂正を検査するための訂正検査器であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、
（ａ）該多次元符号におけるデータに応答して計算され、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して計算されるデータ検査値を記憶するためのデータレジスタと、
（ｂ）該多次元符号における該データを訂正するための該ECC復号化器によって生成される訂正値に応答して計算される誤り検査値を記憶するための誤りレジスタと、
（ｃ）該データレジスタの内容と該誤りレジスタの内容とを組み合わせて、最終検査値を生成する手段と、
（ｄ）該最終検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効かつ完了したか否かを示す、比較器と、
を有する訂正検査器。
【請求項３２】
前記多次元符号が、光ディスク記憶装置において用いられる積符号である、請求項31に記載の誤り訂正検査器。
【請求項３３】
（ａ） 前記ECC復号化器が、符号語に応答して誤りシンドロームを生成するためのシンドローム生成器と、該誤りシンドロームを用いて該符号語における誤りを訂正するための誤り訂正器とを有し、
（ｂ）該シンドローム生成器および該誤り訂正器が互いに、非同期して動作し、
（ｃ）該データ検査値が、該シンドローム生成器が該符号語についての該誤りシンドロームを生成する時と時間的に近接して生成され、該誤り検査値が、該誤り訂正器が該符号語を訂正する時と時間的に近接して生成される、請求項31に記載の誤り訂正検査器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、光記憶装置のための誤り検出および訂正システム（ＥＤＡＣ）に関し、特に、積符号(product code)などの多次元符号を処理するための改良された方法および装置に関する。
【０００２】
【従来の技術】
ＣＤ−ＲＯＭ、ＤＶＤ等の光記憶装置は、大量のオーディオ、ビジュアル、および／またはコンピュータデータを不揮発性の様式で記憶するために使用される。データのセクタは、典型的には、回転する光ディスク上のらせん状のトラックに記録され、リードバックされる際に、データは、記録プロセスのノイズおよび動態のために、誤りを受ける。化けたデータの正確な再生には、リード−ソロモン(Reed-Solomon)符号等の誤り訂正符号（ＥＣＣ）を実行する誤り検出および訂正（ＥＤＡＣ）システムが必要とされる。光記憶装置に用いられるＥＤＡＣシステムは、典型的には、多層状であり、これは、ユーザデータが、一連のＥＣＣ層を実行する一連の符号化器を通されることを意味する。リードバックの際に、データは、誤りの無いユーザデータが最終的に抽出されるまで、層状のＥＣＣに従って、逆順で復号化される。
【０００３】
ＣＤ−ＲＯＭ型記憶装置に用いられる典型的なデータパスが、図１に図示される。書き込み動作の間に、ホストからのユーザデータは、ＰECCおよびＱECCの冗長記号をそれぞれ有するＰおよびＱ符号語の積符号へと符号化される（２）。Ｐ／Ｑ符号化器２によるデータ出力は、次にスクランブルされ（４）、スクランブルされたデータが、データを２４バイトブロックで処理し、４バイトのＣ２冗長性を添付するＣ２符号化器６を通される。Ｃ２符号化器６の出力は、次に２８バイトのブロックへとインターリーブされ（８）、インターリーブされたデータは、４バイトのＣ１冗長性を添付するＣ１符号化器１０を通される。データは、次に、３２バイトブロックでディスク１２に書き込まれ、リードバックされる間に、このプロセスが逆に実行される。Ｃ１およびＣ２冗長性は、クロスインターリーブリード−ソロモン符号（Cross Interleave Reed-Solomon Code）（ＣＩＲＣ）と呼ばれる。
【０００４】
読み出し動作の間に、Ｃ１復号化器１０は、ディスクから読み出された３２バイトのブロックを復号化し、４バイトのＣ１冗長性を用いて、２バイトの誤りまで訂正する。２つを越える誤りが検出されると、その時は、Ｃ１復号化器１０は、ブロックの３２バイトの各々に対してＣ１消去ポインタを生成する。Ｃ２復号化器６は、インターリーブ解除器８によるデータ出力を訂正する際の補助を行うために、Ｃ１消去ポインタを使用する（Ｃ２復号化器は、最大４つのＣ１消去ポインタおよび４バイトのＣ２冗長性を用いて最大４バイトの誤りを訂正することができる）。Ｃ２復号化器６が、データブロックをうまく訂正すると、Ｃ１消去ポインタは、Ｃ２消去ポインタとして次に回され得る。データブロックが訂正不可能であれば、Ｃ２復号化器は、ブロックの２８バイト毎にＣ２消去ポインタを設定する。Ｐ／Ｑ復号化器２は、スクランブル解除器４によるデータ出力を修正する際の補助を行うために、Ｃ２消去ポインタを使用する。
【０００５】
図２ａには、２，３５２バイトの情報を含むＣＤ−ＲＯＭ記憶装置に使用される典型的なセクタフォーマットが図示される。最初の１２バイトは、セクタ中の残りのデータへのバイト同期に使用される同期マーク１４を格納する。次の４バイトが、セクタアドレスおよび動作モード等のヘッダ情報１６を格納する。次の２０４８バイトが、ユーザデータ１８を格納し、次には、４バイトのＣＲＣ冗長性２０および８バイトのパッド(pad)２２が続く。最後の２７６バイトには、図２ｂに図示されるような積符号のＰおよびＱ符号語に対するＰECCおよびＱECC冗長性２４Ａおよび２４Ｂが格納される。ＰECCおよびＱECC冗長性２４Ａおよび２４Ｂは、書き込み動作の間に図１のＰ／Ｑ符号化器２によって生成され、リードバックされる際に、ヘッダ１６、ユーザデータ１８、およびＣＲＣバイト２０における誤りを検出および訂正するために、Ｐ／Ｑ復号化器２によって使用される。
【０００６】
Ｐ／Ｑ符号化器／復号化器２の動作は、周知であり、図２ｂを参照して理解される。データは、２組の交差する(intersecting)符号語、すなわち、添付されたＰECC冗長性を含むＰ列符号語の組と、図示されるようにデータを対角線上に処理することよって生成される、添付されたＱECC冗長性を含むＱ行符号語の組に配置される。読み出し動作の間、誤り訂正プロセスは、反復的に動作する。パスが、Ｐ符号語上に作られ、次に、パスがＱ符号語上に作られ、次に別のパスが、Ｐ符号語上に作られる（以下同様）。Ｐ符号語における誤りの数が、符号の誤り訂正能力を越えると、Ｑ符号語上のパスが、Ｐ符号語が、次のパスにおいて訂正可能となるのに十分な数の誤りを訂正し得る。同様に、Ｐ符号語上のパスの間に十分な誤りが訂正されれば、訂正不可能なＱ符号語が、訂正可能となり得る。従って、Ｐ／Ｑ復号化器２は、全ての符号語が訂正されるまで、あるいは、反復数がある所定の最大値を越えるまで（セクタが訂正不可能であることを表す）、ＰおよびＱ符号語を反復的パスにおいて処理する。
【０００７】
図１に示されるようなＣ２符号化データをインターリーブする（８）ことに加えて、図２ａのＰおよびＱ積符号もインターリーブされ、それによって図２ｃに示されるような、ＥＶＥＮおよびＯＤＤ積符号が形成され得る。このフォーマットにおいては、ＥＶＥＮ積符号は、セクタの偶数のバイトを格納し、ＯＤＤ積符号は、セクタの奇数バイトを格納する。当業者は、インターリーブすることにより、長いバースト誤りを訂正する能力が、その誤りを複数の符号語に広げることによって向上されることを理解する。さらに、データをＥＶＥＮおよびＯＤＤ積符号にインターリーブすることにより、Ｐ／Ｑ復号化器２が、２つの符号語（２つのＰまたは２つのＱ）を同時に訂正することが可能となり、それによってスループットが大幅に増加する。
【０００８】
記憶装置のスループットの増加は、重要な設計上の考慮である。Ｐ／Ｑ復号化器２の速度は、ＰおよびＱ符号語を読み出すために必要とされるバッファアクセスの数、および符号語を訂正するために必要とされる処理時間に直接関連する。従来技術の、積符号を処理するためのＥＤＡＣシステムの多くにおいては、符号語が、誤りが無いと決定された、あるいは前の反復において完全に訂正され得たかどうかに関わらず、ＰおよびＱ符号語の全てが、各反復中に読み出され、処理される。「クロスインターリーブされた誤り訂正符号化データの復号化器」という名称の米国特許第5,412,667号は、誤りが無いと符号語に「印をつける」ことにより、光記憶装置において、積符号プロセッサの速度を向上させる。このように、誤りの無い符号語は、後続のパスの間、飛ばされ(skipped)、これによって、ＥＤＡＣシステム全体の速度が大幅に向上する。誤りが、特定の符号語（ＰまたはＱ）において訂正されると、訂正されたバイトで交差する符号語のみが、誤りを含むと印をつけられ、それによって、それらのシンドロームが、次のパス間に再び計算される。この方法は、各パスにおいて、ＰおよびＱ符号語の全てを処理することに対する改善であるが、Ｃ２復号化器６によって生成される、または内部的に生成されるような消去ポインタ(erasure pointers)を考慮に入れていない。換言すれば、米国特許第5,412,667号は、消去ポインタの重要性を考慮することなく、次のパス間での処理のために、訂正されたデータバイトで交差する符号語のみに印をつける。
【０００９】
従って、光記憶装置の積符号において、ＰまたはＱ符号語を読み出し、処理するかどうかを決定する際に、消去ポインタ（例えば、Ｃ２消去ポインタ）を考慮に入れる、より効率的なＥＤＡＣシステムに対する必要性がある。
【００１０】
本発明の別の局面は、図１のＰ／Ｑ復号化器２によってなされた訂正の有効性をチェックするために使用される、図２ａに示されるＣＲＣ冗長性２０に関わる。ＣＲＣ冗長性２０は、典型的には、
ＣＲＣ冗長性＝Ｐ（ｘ）・ｘn-kｍｏｄＧ（ｘ）
によるヘッダおよびユーザデータを処理することによって生成される。ただし、Ｐ（ｘ）は、有限のフィールドＧＦ（２）における係数を有する多項式として表されるヘッダおよびユーザデータであり、ｎ−ｋは、ＣＲＣ冗長性記号の数であり、Ｇ（ｘ）は、生成器多項式である。次にＣＲＣ冗長性２０は、生じた符号語がディスクに書き込まれる前に、図２ａに図示されるようなユーザデータに付加される。読み出し動作の間に、ディスクから読み出されたデータは処理され、それによって、ＳCRC＝Ｃ（ｘ）ｍｏｄＧ（ｘ）によるＣＲＣシンドロームＳCRCが生成される。ただし、Ｃ（ｘ）は、ディスクから読み出されたデータ多項式または符号語（ＣＲＣ冗長性を含む）である。データＣ（ｘ）に誤りがなければ、シンドロームＳCRCは、０となる。Ｐ／Ｑ符号化器２が積符号の訂正を終了した後にＣＲＣシンドロームを生成することにより、ＣＲＣは、Ｐ／Ｑ訂正を検査し、訂正間違いを検出するように動作する。これは、ＥＤＡＣシステムが、「悪いデータ」をホストシステムに渡すことを防止するので、非常に重要な機能である。
【００１１】
【発明が解決しようとする課題】
Ｐ／Ｑ復号化器２が積符号の訂正を終了した後にＣＲＣシンドロームＳCRCを生成するには、全てのデータがバッファから読み出されることが必要である。このオーバーヘッドは、ＥＤＡＣシステムの全スループットを大幅に低減し得るが、「ＣＲＣ／ＥＤＣチェッカーシステム」という名称の米国特許第5,592,498号に開示されるように、それは回避可能である。米国特許第5,592,498号において、ＣＲＣシンドロームＳCRCは、ＰおよびＱ符号語の処理と同時に生成される。Ｐ符号語の第１のパスにおいて、仮のＣＲＣシンドロームＳCRCが生成され、次に、Ｐ／Ｑ復号化器が訂正を行う時に、ＣＲＣシンドロームＳCRCが、訂正を反映させるように同時に更新される。このように、Ｐ／Ｑ復号化器２が、積符号の各パスの処理を終えると、ＣＲＣシンドロームＳCRCは、訂正が有効で、完了したかどうかをチェックするために直ちに利用可能である。しかし、米国特許第5,592,498号に開示されるＣＲＣ発生器は、特定のＰまたはＱ符号語を飛ばすＰ／Ｑ復号化器２と同時に動作せず、むしろ、各パスにおいてＰおよびＱ符号語の全てを読み出すＰ／Ｑ復号化器２と一緒に動作するのみである。
【００１２】
先行技術のＰ／Ｑ復号化器の別の不利な点は、積符号が完全に訂正されたかどうかの判定に関連して生じる遅延である。先行技術のＰ／Ｑ復号化器は積符号の訂正と同時にはＣＲＣシンドロームＳCRCを生成しないため、Ｐ／Ｑ復号化器は、実際に訂正が終了したかどうかを判定するための別のパスを作らなければならない。例えば、Ｐ符号語についてのパスの終了後に訂正不可能な誤りに遭遇すると、先行技術のＰ／Ｑ復号化器は、Ｑ符号語についての別のパスを行い、訂正が実際に終了したことを検査する（即ち、Ｑシンドロームがすべてゼロであることを検査する）。従って、先行技術のＰ／Ｑ復号化器は、ＰパスまたはＱパスについてすべてのゼロのシンドロームが生成されるまで、訂正の有効性を調べるためのＣＲＣシンドロームＳCRCを生成せず、これでは非効率的である。
【００１３】
従って、Ｐ／Ｑ復号化器２が符号語を飛ばしても、Ｐ／Ｑ復号化器２が積符号を処理しているのと同時にＣＲＣシンドロームＳCRCを計算できるＣＲＣシンドローム生成器が必要とされている。本発明の別の目的は、先行技術のＥＤＡＣシステムにおいて、訂正が終了したことを検査するために必要とされる別のパスを不要にするとともに、ＣＲＣシンドロームＳCRCを生成するために必要とされる別のパスも不要にすることである。
【００１４】
【課題を解決するための手段】
本発明による訂正検査器は、ECC復号化器によって行われる誤り訂正符号(ECC)に対する訂正を検査するための訂正検査器であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、該ECC復号化器が、所定の条件が満たされた場合に、符号語を飛ばし、（ａ）該多次元符号におけるデータに応答して計算され、該ECC復号化器が、該多次元符号における該データを処理するときに時間的に近接して計算される検査値を記憶するための少なくとも１つのレジスタと、（ｂ）該ECC復号化器が、該多次元符号における符号語を飛ばすときに、オフセット値に従って該検査値を調整するためのオフセットコントローラと、（ｃ）該ECC復号化器が該多次元符号の処理を終了するとき、最終の検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効であるか否かを示す、比較器とを有している。
【００１５】
前記検査値は、一次元符号に従って、前記多次元符号における前記データにわたって生成されてもよい。
【００１６】
前記一次元符号がCRC符号であってもよい。
【００１７】
前記オフセットコントローラは、前記検査値を、XK mod G(x)で乗算し、ここで、Kが、前記ECC復号化器が符号語を飛ばすときに前記多次元符号における飛ばしたシンボルの数に対応する前記オフセット値であり、G(x)が、前記一次元符号の生成器多項式であってもよい。
【００１８】
（ａ）前記多次元符号が、複数の列符号語および複数の行符号語を含む積符号であり、（ｂ）１つの飛ばした列符号語に対応する前記オフセット値が、行符号語の１つのシンボルであってもよい。
【００１９】
（ａ）前記多次元符号が、複数の列符号語および複数の行符号語を含む積符号であり、（ｂ）１つの飛ばした行符号語に対応する前記オフセット値が、行符号語におけるシンボルの数および行符号語の数に対して計算されてもよい。
【００２０】
前記検査値は、第１および第２の検査値を含み、前記少なくとも１つのレジスタが、（ａ）前記多次元符号のシンボルに応答して該第１の検査値を記憶するデータレジスタと、（ｂ）前記ECC復号化器によって生成される訂正値に応答して該第２の検査値を記憶するための誤りレジスタとを有してもよい。
【００２１】
（ａ）前記第１の検査値は、前記ECC復号化器によって前記第１のセットの符号語にわたって第１のパスの間計算され、（ｂ）前記第２の検査値が、前記多次元符号におけるデータを訂正する前記ECC復号化器と時間的に近接して計算されてもよい。
【００２２】
前記訂正検査器は、前記第１の検査値および前記第２の検査値を組み合わせて、前記最終の検査値を生成する手段をさらに有してもよい。
【００２３】
前記訂正検査器は、前記ECC復号化器によって生成される訂正値を前記オフセット値によって調整される前記検査値に加えるためのmod-2加算器をさらに有し、該加算の結果が、前記レジスタに記憶される該検査値と置換されてもよい。
【００２４】
本発明による方法は、ECC復号化器によって行われる誤り訂正符号（ECC) に対する訂正を検査する方法であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、該ECC復号化器が、所定の条件が満たされる場合に、符号語を飛ばし、（ａ）該多次元符号におけるデータに応答し、かつ、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して、検査値を計算するステップと、（ｂ）該ECC復号化器が、該多次元符号における符号語を飛ばすときに、オフセット値に従って該検査値を調整するステップと、（ｃ）該ECC復号化器が該多次元符号の処理を終了するとき、最終の検査値と所定値とを比較するステップであって、該比較の結果が、該ECC復号化器によって行われる訂正が有効であるか否かを示す、ステップとを包含する。
【００２５】
前記検査値は、一次元符号に従って、前記多次元符号における前記データにわたって生成されてもよい。
【００２６】
前記一次元符号はCRC符号であってもよい。
【００２７】
前記オフセット値は、前記検査値を、XK mod G(x)で乗算することによって計算され、ここで、Kが、前記ECC復号化器が符号語を飛ばすときに前記多次元符号における飛ばしたシンボルの数に対応する前記オフセット値であり、G(x)が、前記一次元符号の生成器多項式であってもよい。
【００２８】
（ａ）前記多次元符号は、複数の列符号語および複数の行符号語を含む積符号であり、（ｂ）１つの飛ばした列符号語に対応する前記オフセット値は、行符号語の１つのシンボルであってもよい。
【００２９】
（ａ）前記多次元符号は、複数の列符号語および複数の行符号語を含む積符号であり、（ｂ）１つの飛ばした行符号語に対応する前記オフセット値は、行符号語におけるシンボルの数および行符号語の数に対して計算されてもよい。
【００３０】
前記検査値は、第１および第２の検査値を含み、（ａ）前記多次元符号のシンボルに応答して該第１の検査値を計算するステップと、（ｂ）前記ECC復号化器によって生成される訂正値に応答して該第２の検査値を計算するステップとをさらに包含してもよい。
【００３１】
（ａ）前記第１の検査値は、前記ECC復号化器によって前記第１のセットの符号語にわたって第１のパスの間計算され、（ｂ）前記第２の検査値は、前記ECC復号化器が前記多次元符号におけるデータを訂正する時と時間的に近接して計算されてもよい。
【００３２】
前記第１の検査値と前記第２の検査値とを組み合わせて、前記最終の検査値を生成するステップをさらに包含してもよい。
【００３３】
前記検査値を調整するステップは、（ａ）前記ECC復号化器によって生成されるmodulo-2訂正値を、前記オフセット値によって調整される該検査値に加えるステップと、（ｂ）該検査値を該加算の結果と置換するステップとをさらに包含してもよい。
【００３４】
本発明による誤り検出および訂正（EDAC) システムは、第２のセットの符号語を交差する第１のセットの符号語を含む多次元誤り訂正符号（ECC) における誤りを訂正するための誤り検出および訂正（EDAC) システムであって、（ａ）該多次元符号の該第１および第２のセットの符号語を記憶するためのデータバッファと、（ｂ）該第１および第２のセットの符号語を繰り返しパスにおいて該バッファから読み出すためのECC復号化器であって、該ECC復号化器が、所定の条件が満たされる場合、符号語を該バッファから読み出さない、ECC復号化器と、（ｃ）該多次元符号におけるデータに応答して計算される検査値および該ECC復号化器によって生成される訂正値を記憶するための少なくとも１つのレジスタであって、該検査値が、該ECC復号化器が、該多次元符号の該データを該バッファから読み出すときに時間的に近接して計算される、レジスタと、（ｄ）該ECC復号化器が、該多次元符号における符号語を該バッファから読み出さないときに、オフセット値に従って該検査値を調整するためのオフセットコントローラと、（ｅ）該ECC復号化器が、該多次元符号の処理を終了するときに、最終の検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効が否かを示す、比較器とを有している。
【００３５】
前記検査値は、一次元符号に従って前記多次元符号における前記データにわたって生成されてもよい。
【００３６】
前記一次元符号はCRC符号であってもよい。
【００３７】
前記オフセットコントローラは、前記検査値を、XK mod G(x)で乗算し、ここで、Kが、前記ECC復号化器が符号語を前記バッファから読み出さないときに前記多次元符号における飛ばしたシンボルの数に対応する前記オフセット値であり、G(x)が、前記一次元符号の生成器多項式であってもよい。
【００３８】
本発明による訂正検査器は、ECC復号化器によって行われる誤り訂正符号（ECC) に対する訂正を検査するための訂正検査器であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、（ａ）該多次元符号におけるデータに応答して計算され、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して計算される検査値を記憶するための少なくとも１つのレジスタと、（ｂ）該ECC復号化器が、少なくとも２つの該パスに対する該第１のセットの符号語の処理を終了した後、最終の検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効かつ完了したか否かを示す、比較器とを有してもよい。
【００３９】
前記多次元符号は、光ディスク記憶装置において用いられる積符号であってもよい。
【００４０】
訂正不可能な誤りが、前記ECC復号化器によって、前記第１のセットの符号語の直前のパスにおいて検出された場合、前記最終検査値が、前記所定値と比較されてもよい。
【００４１】
本発明による方法は、ECC復号化器によって行われる誤り訂正符号(ECC)に対する訂正を検査する方法であって、前記ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、（ａ）該多次元符号におけるデータに応答し、かつ、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して、検査値を計算するステップと、（ｂ）該ECC復号化器が少なくとも２つの該パスに対する該第１のセットの符号語の処理を終了した後、最終の検査値と所定値とを比較するステップであって、該比較の結果が、該ECC復号化器によって行われる訂正が有効であるか否かを示す、ステップとを包含してもよい。
【００４２】
前記多次元符号は、光ディスク記憶装置において用いられる積符号であってもよい。
【００４３】
訂正不可能な誤りが、前記ECC復号化器によって、前記第１のセットの符号語の直前のパスにおいて検出された場合、前記最終検査値が、前記所定値と比較されてもよい。
【００４４】
本発明による訂正検査器は、ECC復号化器によって行われる誤り訂正符号（ECC) に対する訂正を検査するための訂正検査器であって、該ECC符号が、第２のセットの符号語を交差する第１のセットの符号語を有する多次元符号であり、該ECC復号化器が、該第１および第２のセットの符号語を反復パスにおいて処理し、（ａ）該多次元符号におけるデータに応答して計算され、該ECC復号化器が、該多次元符号における該データを処理する時に時間的に近接して計算されるデータ検査値を記憶するためのデータレジスタと、（ｂ）該多次元符号における該データを訂正するための該ECC復号化器によって生成される訂正値に応答して計算される誤り検査値を記憶するための誤りレジスタと、（ｃ）該データレジスタの内容と該誤りレジスタの内容とを組み合わせて、最終検査値を生成する手段と、（ｄ）該最終検査値と所定値とを比較するための比較器であって、該比較の結果が、該ECC復号化器によって行われる訂正が有効かつ完了したか否かを示す、比較器とを有してもよい。
【００４５】
前記多次元符号は、光ディスク記憶装置において用いられる積符号であってもよい。
【００４６】
（ａ） 前記ECC復号化器は、符号語に応答して誤りシンドロームを生成するためのシンドローム生成器と、該誤りシンドロームを用いて該符号語における誤りを訂正するための誤り訂正器とを有し、（ｂ）該シンドローム生成器および該誤り訂正器が互いに、非同期して動作し、（ｃ）該データ検査値が、該シンドローム生成器が該符号語についての該誤りシンドロームを生成する時と時間的に近接して生成され、該誤り検査値が、該誤り訂正器が該符号語を訂正する時と時間的に近接して生成されてもよい。
【００４７】
以下に作用を説明する。
【００４８】
典型的には光ディスク記憶装置で用いられる誤り訂正符号（ＥＣＣ）を処理するための多層誤り検出／訂正（ＥＤＡＣ）システムを開示する。ＥＤＡＣシステムの第１の層は、マルチバーストリード−ソロモン符号などの一次ＥＣＣを含み、第２の層は、該一次ＥＣＣを用いてなされた訂正の有効性を検査するために用いられるＣＲＣ符号などの二次ＥＣＣを含む。一次ＥＣＣは多次元であり、本明細書に開示した実施形態では、一次ＥＣＣは、典型的にはＣＤ−ＲＯＭ記憶装置で用いられる二次元Ｐ／Ｑ積符号である。二次ＥＣＣは、一次ＥＣＣと調和して動作する。ＥＤＡＣシステムは、一次ＥＣＣを用いてデータを処理および訂正するとき、それと同時に二次ＥＣＣを更新する。このようにして、ＥＤＡＣシステムが一次ＥＣＣを用いたデータの処理を終了すると、訂正の有効性を調べるために、二次ＥＣＣによって生成された検査シンドロームがすぐに利用可能となる。その結果、ＰパスまたはＱパスの終了後に訂正不可能な誤りに遭遇する場合に必要とされる別のパスは不要になる。ＥＤＡＣシステムの処理を大幅に増加するために、多次元一次ＥＣＣの反復パスの間、誤りの無い符号語は飛ばされる。符号語が飛ばされると、二次ＥＣＣを用いて生成された検査シンドロームは、飛ばされたデータバイトを補償する（account for）ように調整される。ＤＡＴＡシンドローム回路は符号語データを用いて更新され、ＥＲＲＯＲシンドローム回路は符号語データに与えられた訂正値を用いて更新される。多次元一次符号の各パスの後、ＤＡＴＡシンドロームは、ＥＲＲＯＲシンドロームと結合され、検査シンドロームが生成される。
【００４９】
本発明の上記およびその他の局面および利点については、添付の図面を参照しながら以下に示す本発明の詳細な説明を読めばよりよく理解される。
【００５０】
【発明の実施の形態】
図３は、本発明のＰ／Ｑ符号化器／復号化器２のブロック図であり、このＰ／Ｑ符号化器／復号化器２は、読み出し／書き込みデータを格納するためのデータバッファ２６と、データバッファ２６へのアクセスを調停する（arbitrate）ためのコントローラ２８と、一次ＥＣＣ／シンドローム生成器２９と、誤り訂正器３０（例えば、マルチバーストリード−ソロモン）と、二次ＥＣＣ生成器／訂正検査器３２（例えば、ＣＲＣ）とを含む。書き込み動作の間、以下のステップが非同期で行われる。（１）ホストからのユーザデータをデータバッファ２６に格納する；（２）ＥＣＣ生成器２９がバッファ２６からのユーザデータを読み出し、図２ｃのインタリーブされたＰ／Ｑ積符号についてＰECCおよびＱECCを生成する；（３）データがバッファ２６から読み出され、Ｃ２符号化器６に転送されると、ＣＲＣ生成器３２が、図２ｃのインタリーブされたＰ／Ｑ積符号についてＣＲＣシンボル２０を生成する。読み出し動作の間、以下のステップが同時に且つ非同期で実行される。（１）Ｃ２復号化器からのデータをデータバッファ２６に格納する；（２）符号語に処理のためにフラグが立てられると、シンドローム生成器２９がデータバッファ２６からデータを読み出し、誤りシンドロームを生成する；（３）シンドロームがゼロでなければ、ＥＣＣ誤り訂正器３０がシンドロームおよびＣ２消去ポインタ３４を用いて、データを訂正する。ここで、訂正値がＣＲＣ訂正検査器３２に与えられ、ＣＲＣ訂正検査器３２がそれに応じてＣＲＣシンドロームＳCRCを調整する；（４）ＰパスまたはＱパスの間に訂正不可能な誤りに遭遇しなければ、ＣＲＣシンドロームＳCRCを用いて、訂正が有効であるかどうか、および訂正が終了したかどうかを調べる。
【００５１】
消去ポインタと符号語に対する訂正とに基づいて符号語を飛ばすことによりＰ／Ｑ符号化器２を促進する本発明の技術と、ＣＲＣシンドロームＳCRCを同時に生成する本発明の技術とについて、以下に図４ａから図４ｋのフロー図を参照して説明する。
【００５２】
（消去ポインタ処理）
図２ｃに示す積符号におけるＰおよびＱ符号語のそれぞれは、誤っている可能性のあるシンボルを示す消去ポインタの関連する配列（またはポインタ）、および符号語が誤りなしかどうか（すなわち、飛ばされ得るか）を示す読み出しフラグを有する。前述の通り、符号語ポインタは図１に示すＣ２復号化器６によって初期化され得、Ｐ／Ｑ復号化器２の積符号における誤りの訂正を助ける。積符号の処理の間、Ｐ／Ｑ復号化器２は本発明の促進アルゴリズムに基づいてポインタをセットまたはクリアし得る。促進アルゴリズムのフローチャートを図４ａ〜図４ｋに示す。
【００５３】
一旦Ｃ２復号化器６から図３に示すデータバッファ２６に完全な積符号が転送されたら、図４ａから始まって、初期化ステップ３６が読み出しフラグREAD_P[]およびREAD_Q[]をクリアし、訂正不可能な誤りに遭遇したかどうかを示すＵＮＣフラグをクリアし、誤り訂正器３０が符号語の訂正で使用中であるかどうかを示すECC_BUSYフラグをクリアし、パスカウント変数PASS_CNTをゼロに設定し、ＰおよびＱ符号語を通過する最初のパスを表すFIRST PASSフラグをセットする。最初のパスの間、Ｐ符号語およびＱ符号語のすべてが、読み出しフラグの状態に関係なく読み出され、処理される。
【００５４】
初期化ステップ３６の実行後、COL変数がステップ３８においてゼロにセットされる（すなわち、第１のＰ符号語にセットされる）。COL変数は、処理されている現在の列のＰ符号語を追跡する。そしてステップ４０において、ROW変数がゼロにセットされる（すなわち、現在のＰ符号語における第１のシンボルにセットされる）。ROW変数は、現在のＰ符号語の現在の行シンボルを追跡する。次に、ステップ４２において現在のＰ符号語に対する読み出しフラグREAD_P[COL]がセットされる場合、またはそれが最初のＰパスである場合、ループが実行されて、現在のＰ符号語が読み出され、誤りシンドロームが生成される。図２ｃに示す現在のEVEN（偶数）およびODD（奇数）Ｐ符号語からの現在のシンボル（Ｈ、Ｌと呼ぶ）は、ステップ４４において図３に示すデータバッファ２６から読み出され、ステップ４６においてシンドローム生成器２９に入力される。これがＰ符号語上の最初のパスである（すなわち、ステップ４８においてFIRST PASS（最初のパス）が真である）場合、ステップ４４において読み出されたシンボルはまた、ステップ５０において図４ｈに示すフローチャートのステップを実行することによってデータCRCシンドロームを更新するために使用される。図４ｈに示すフローチャートについては、以下で詳細に説明する。ループの最後において、ROWがステップ５２において現在のＰ符号語の最後のシンボルのところにない（すなわち、２５でない）場合、ROWはインクリメントされ、ループが再実行されて、誤りシンドロームの計算およびデータCRCシンドロームの更新に使用される次のシンボルが読み出される。
【００５５】
一旦現在のＰ符号語についてすべてのシンボルが読み出されたら（すなわち、ROWがステップ５２において２５であるとき）、図３に示すシンドローム生成器２９は符号語に対するECCシンドロームを生成している。ステップ５３において読み出しフラグREAD_P[COL]がクリアされ、これによって現在のＰ符号語が次のＰパスの間、（現在のＰ符号語の読み出しフラグが後述するように再びセットされない限り）飛ばされる。ステップ５４においてシンドロームがゼロであり、符号語が誤りなしであることを示し、そしてそれが最初のパスでない（すなわち、ステップ５６においてFIRST PASS（最初のパス）が偽である）場合、ステップ５８において現在のＰ符号語ポインタが読み出される。ステップ６０において、ポインタの位置で現在のＰ符号語と交差するＱ符号語に対して読み出しフラグREAD_Q[POINTERS]がセットされ、次いで現在のＰ符号語に対するポインタがクリアされる。最初のパスの間（すなわち、ステップ５６においてFIRST PASS（最初のパス）が真であるとき）、消去ポインタは変更されず、ポインタを読み出すためのステップ５８におけるバッファへのアクセスの待ち時間が回避される。いずれの場合も、誤りCRCシンドロームはステップ６１において後述する図４ｉに示すフローチャートのステップを実行することによって更新され、次のＰ符号語の上に位置付けられる。
【００５６】
ステップ５４においてシンドロームがゼロではなく、Ｐ符号語が誤りを含むことを示す場合は、現在のＰ符号語に対するポインタがステップ６２において読み出される。次に、システムはステップ６４においてECC_BUSYフラグをチェックする。ECC_BUSYフラグがセットされている（誤り訂正器３０が前の符号語の訂正で使用中であることを示す）場合、システムはECC_BUSYフラグがクリアされるまで待つ。一旦クリアされると、ECC_BUSYフラグはステップ６６においてセットされ、現在のＰ符号語について誤り訂正手順が開始される。誤り訂正手順は、図４ｃに示すフローチャートで説明するが、次のＰ符号語に対するシンドロームの生成と平行して実行される。すなわち、ステップ６６においてECC_BUSYフラグをセットした後、図４ａに示すシンドローム生成手順は直ちに次のＰ符号語の処理を開始し、一方、前のＰ符号語は誤り訂正器３０によって訂正される。
【００５７】
ステップ４２において、読み出しフラグREAD_P[COL]がセットされず、それが最初のパスでない場合、現在のＰ符号語は飛ばされ、バッファからの符号語の読み出しおよび誤りシンドロームの生成に関連する待ち時間が回避される。しかし、誤りCRCシンドロームはやはりステップ６１において更新され、次のＰ符号語の上に位置付けられる。誤りなしを示すフラグが付けられる符号語を飛ばすことにより、Ｐ／Ｑ復号化器２のスループットが有意に向上され、これは本発明の重要な局面である。
【００５８】
一旦最後のＰ符号語が処理されたら（すなわち、ステップ６８においてCOLが４２に等しいとき）、図４ｋに示すフローチャートのステップが実行され、積符号の訂正が有効かつ完全であるかが決定される。完全に訂正されていない場合、図４ｂのフローチャートのステップが実行され、Ｑ符号語が処理される。
【００５９】
図４ｂに示すＱ符号語の処理のフローチャートは、図４ａに示すＰ符号語の処理のフローチャートと本質的に同じである。まず、ROW_INIT変数が第１のＱ符号語に初期化され（すなわち、ステップ７０においてゼロにセットされ）、その後、Ｑパスの間、現在のＱ符号語を追跡する。ステップ７２において、ROW変数が現在のＱ符号語に（すなわち、ROW_INITに）セットされ、COLは０に（すなわち、現在のＱ符号語における第１のシンボルに）セットされる。ステップ７４において現在のＱ符号語に対する読み出しフラグREAD_Q[ROW_INIT]がセットされる場合、またはそれが最初のパスである場合、ループが実行されて現在のＱ符号語に対する誤りシンドロームが生成される。図２ｃに示す現在のEVEN（偶数）およびODD（奇数）Ｑ符号語からの現在のシンボル（Ｈ、Ｌと呼ぶ）は、ステップ７６において図３に示すデータバッファ２６から読み出され、ステップ７８においてシンドローム生成器２９に入力される。ステップ８０においてROWが２５でない場合、ROWはインクリメントされるか、ステップ８２においてROWはゼロ（一番上の行）に再初期化され、これにより現在のＱ符号語において次のシンボルが処理される（図５参照）。ループの最後において、COLがステップ８４において現在のＱ符号語の最後のシンボルのところにない（すなわち、４２でない）場合、COLはインクリメントされ、ループが再実行されて、誤りシンドロームの計算に使用される次のシンボルが読み出される。
【００６０】
一旦現在のＱ符号語についてすべてのシンボルが読み出されたら（すなわち、COLがステップ８４において４２であるとき）、図３に示すシンドローム生成器２９は符号語に対するECCシンドロームを生成している。ステップ８５において読み出しフラグREAD_Q[ROW_INIT]がクリアされ、これによって現在のＱ符号語が次のＱパスの間、（現在のＱ符号語の読み出しフラグが後述するように再びセットされない限り）飛ばされる。ステップ８６においてシンドロームがゼロであり、符号語が誤りなしであることを示し、そしてそれが最初のパスでない（すなわち、ステップ８８においてFIRST PASS（最初のパス）が偽である）場合、ステップ９０において現在のＱ符号語ポインタが読み出される。ステップ９２において、ポインタの位置で現在のＱ符号語と交差するＰ符号語に対して読み出しフラグREAD_P[POINTERS]がセットされ、次いで現在のＱ符号語に対するポインタがクリアされる。最初のパスの間（すなわち、ステップ８８においてFIRST PASS（最初のパス）が真であるとき）、消去ポインタは変更されず、ポインタを読み出すためのステップ９０におけるバッファへのアクセスの待ち時間が回避される。いずれの場合も、誤りCRCシンドロームはステップ９４において後述する図４ｊに示すフローチャートのステップを実行することによって更新され、次のＱ符号語の上に位置付けられる。
【００６１】
ステップ８６においてシンドロームがゼロではなく、Ｑ符号語が誤りを含むことを示す場合は、現在のＱ符号語に対するポインタがステップ９６において読み出される。次に、システムはステップ９８においてECC_BUSYフラグをチェックする。ECC_BUSYフラグがセットされている（誤り訂正器３０が前の符号語の訂正で使用中であることを示す）場合、システムはECC_BUSYフラグがクリアされるまで待つ。一旦クリアされると、ECC_BUSYフラグはステップ１００においてセットされ、現在のＱ符号語について誤り訂正手順が開始される。誤り訂正手順は、図４ｃに示すフローチャートで説明するが、次のＱ符号語に対するシンドロームの生成と平行して実行される。すなわち、ステップ９８においてECC_BUSYフラグをセットした後、図４ｂに示すシンドローム生成手順は直ちに次のＱ符号語の処理を開始し、一方、前のＱ符号語は誤り訂正器３０によって訂正される。
【００６２】
ステップ７４において、読み出しフラグREAD_Q[ROW_INIT]がセットされず、それが最初のパスでない場合、現在のＱ符号語は飛ばされ、バッファからの符号語の読み出しおよび誤りシンドロームの生成に関連する待ち時間が回避される。しかし、誤りCRCシンドロームはやはりステップ９４において更新され、次のＱ符号語の上に位置付けられる。
【００６３】
一旦最後のＱ符号語が処理されたら（すなわち、ステップ１０２においてROW_INITが２５に等しいとき）、図４ｋに示すフローチャートのステップが実行され、積符号の訂正が有効かつ完全であるかが決定される。完全に訂正されていない場合、ステップ１０３においてFIRST PASS（最初のパス）フラグがクリアされ、図４ａに示すフローチャートのステップを再実行することによってＰ符号語上で別のパスが実施される。
【００６４】
ここで図４ｃを参照して説明を続けるが、このフローチャートのステップは、ＰまたはＱ符号語が誤りを含む（すなわち、シンドロームがゼロでない）ときに実行される。図４ｃのフローチャートは、誤りシンドロームを生成するための図４ａおよび図４ｂのフローチャートと平行して実行される。すなわち、現在の符号語（ＰまたはＱ）に対して生成されたシンドロームがゼロでない場合、シンドロームが次の符号語に対して生成されている間に図４ｃに示すフローチャートのステップが実行されて符号語を訂正する。誤り訂正手順はステップ１０４において、ECC_BUSYフラグが図４ａのステップ６６または図４ｂのステップ１００においてセットされるまで（すなわち、ＰまたはＱ符号語が訂正を必要とするまで）待機する。符号語を訂正するために、制御はステップ１０６において、その符号語に対してセットされたポインタの数に応じて分岐する。符号語が訂正された後、誤りCRCシンドロームは、以下に詳細に記載する図４ｉのフローチャートのステップを実行することによって、ステップ１０８において訂正値を用いて調整される。その後、ECC_BUSYフラグがステップ１１０においてクリアされ、制御はシステムが訂正すべき次の符号語を待つループの最上部に戻る。
【００６５】
再度図４ｃのステップ１０６の分岐を参照し、利用可能なポインタが無いときは、図４ｄのフローチャートのステップが実行される。Ｐ符号語がＰパスの間に訂正を必要とすると仮定すると、Ｐ符号語に対する誤りシンドロームがステップ１１２において１つの誤りと一致する場合、ステップ１１４において誤り訂正器３０はその誤りを訂正する。ステップ１１６においてＣ２ポインタが利用可能である（しかしクリアされている）場合、読み出しフラグREAD_X[CORRECTION]（ここでXはＰパスに対するＱである）がステップ１１８において、訂正されたシンボルのところでＰ符号語と交差するＱ符号語に対してセットされる。誤りシンドロームがステップ１１２において１つの誤りと一致しない場合、ステップ１２０において符号語が訂正不可能であることを示すUNCフラグがセットされる。符号語が訂正不可能である場合、またはステップ１１６において利用可能なＣ２ポインタがない場合、現在のＰ符号語に対するすべてのポインタがステップ１２２においてセットされ、ステップ１２４において、交差するＱ符号語のすべてに対して読み出しフラグREAD_X[]がセットされる。
【００６６】
再度図４ｃのステップ１０６における分岐を参照し、１つの消去ポインタが存在する場合、図４ｅのフローチャートのステップが実行される。Ｐ符号語がＰパスの間に訂正を必要とすると仮定すると、誤りシンドロームがステップ１２６において１つの誤りと一致し、誤りの位置がステップ１２８においてポインタと一致する場合、ステップ１３０において誤り訂正器３０は現在のＰ符号語においてその誤りを訂正する。次いでポインタがステップ１３２においてクリアされ、読み出しフラグREAD_X[CORRECTION]がステップ１３４において、訂正されたシンボルのところで現在のＰ符号語と交差するＱ符号語に対してセットされる。誤りシンドロームがステップ１２６において１つの誤りと一致しない場合、または誤りの位置がステップ１２８においてポインタと一致しない場合、ステップ１３６においてUNCフラグがセットされ、現在のＰ符号語に対するすべてのポインタがステップ１３８においてセットされ、ステップ１４０において、交差するＱ符号語のすべてに対して読み出しフラグREAD_X[]がセットされる。
【００６７】
再び図4cのステップ106のブランチを参照する。２つの消去ポインタが存在すると、図4fのフロー図が実行される。Ｐ符号語がＰパス中に訂正を必要とすると仮定すると、ポインタ位置にあるＰ符号語のシンボルは、ステップ142で訂正され、読出しフラグREAD_X[CORRECTIONS]は、ステップ144において、訂正されたシンボルにおいて現在のＰ符号語を交差するＱ符号語についてセットされる。ステップ146でC2ポインタが得られる場合、現在のＰ符号語のポインタは、ステップ148でクリアされ、そうでない場合には、ステップ150で現在のＰ符号語の読出しフラグREAD_X[CURRENT]が設定される。現在のＰ符号語の読出しフラグが設定される理由は、C2ポインタが利用可能でない場合、ポインタを有さない誤りが存在する可能性が高く、訂正ミスが発生するからである。従って、ポインタはクリアされず、次のＱパスは、起こりうる訂正ミスを訂正することが可能となる。次のＰパスにおいて、現在のＰ符号語は、再び読み出され、シンドロームがゼロである場合、ポインタはクリアされる。
【００６８】
再び図4cのステップ106のブランチを参照する。３つ以上の消去ポインタが存在すると、図4gのフロー図が実行される。Ｐ符号語がＰパス中に訂正を必要とすると仮定すると、ステップ152において、読出しフラグREAD_X[POINTERS]は、ポインタにおいて現在のＰ符号語を交差するＱ符号語についてセットされる。
【００６９】
このＰおよびＱ符号語にわたる繰り返し手順は、すべての符号語を訂正するために十分なポインタがクリアされる（または繰り返しの数が最大を越える）まで続行する。再び、全訂正手順が実施される。なぜなら、処理用にフラグされた符号語のみがデータバッファから読み出されるからである。この本発明の局面は、以下のセクションに記載するCRCシンドロームSCRCを同時に生成する方法と共に、従来のＰ／Ｑデコーダと比較して有意な性能向上を提供する。
【００７０】
（CRCシンドローム生成）
図３のCRC生成器32は、シンドローム生成器29が第１のＰパス中にシンドロームを生成するのと同時に、および誤り訂正器30がすべてのＰおよびＱパスの間ＰおよびＱ符号語における誤りを訂正するのと同時に、CRCシンドロームSCRCを生成する。このように、CRCシンドロームSCRCは、ＰおよびＱパスのそれぞれの後に、訂正が有効かつ完了しているか否かをチェックするのに即座に用いられる。この結果、訂正が完了しているかどうかを決定するために、従来技術によって必要とされていた積コードについてのさらなるパスが避けられ、積コードを訂正した後にCRCシンドロームSCRCを生成するためのさらなるオーバーヘッドが避けられる。
【００７１】
リアルタイムでCRCシンドロームSCRCを生成するプロセスは、図５を参照しながら理解される。読出し動作中、図１のＰ／Ｑ復号化器２は、読出しフラグに関係なく（即ち第１のＰパス中に符号語は飛ばされない）、列0で開始するＰ（または列）符号語のすべてを処理することによって、図３のデータバッファ26に記憶される積コードを処理し始める(154)。次に、Ｑ（または行）符号語のすべては、行0で開始して処理される(156)。Ｑ符号語は、図示するように積符号の対角線上にわたるシンボルを含む。次のＰおよびＱパスにおいて、Ｐ／Ｑ復号化器２は、符号語に対する読出しフラグがセットされていない場合には、符号語を飛ばし得る（このことは、符号語を処理することが無用であることを示している）。
【００７２】
CRCシンドロームSCRCは、積コードのシンボルのすべてが読み出されるため、第１のＰパス中に完全に生成され得る。その後、CRCシンドロームSCRCは、次のＰまたはＱパス中に積符号になされるすべての訂正を反映するように単に更新されされる。しかし、ECCデコーダ２は、ＰまたはＱパス中の符号語を飛ばし得るので、CRCシンドロームSCRCの位置は、飛ばされた符号語を補償するように調整されなければならない。図4aおよび図4bのシンドローム生成プロセスは、図4cの誤り訂正プロセスと同時かつ非同期に行われるので、本発明は、２つのCRCシンドローム生成回路を用いる。１つは、図4aのステップ50におけるＰ符号語の第１のパス中の「データ」CRCシンドロームを計算するためのものであり、もう１つは、図4cのステップ108におけるＰおよびＱパスにおいて図３の誤り訂正回路30によって生成される訂正値を用いて計算される「誤り」CRCシンドロームを生成するためのものである。また、符号語が飛ばされるとき、誤りCRCシンドロームのみが、図4aのステップ61および図4bのステップ94で調整される。ＰおよびＱパスの終了時に、データおよび誤りCRCシンドロームは、結合されて、訂正が有効かつ完了しているか否かをチェックするのに用いられる最終のCRCシンドロームSCRCを生成する。
【００７３】
データCRCシンドロームは、図4aのＰ符号語について第１のパス中に完全に生成される。ステップ50において、データCRCシンドロームは、図4hに示すフロー図を実行することによって現在の符号語シンボルを用いて調整される。これは、図５を参照しながら理解される。第１のＰパスの始まりにおいて、データCRCレジスタは、図５の位置154、即ち、第１のＰ符号における第１のシンボル156の１つ上のシンボルに配置される。図4aのステップ44において、第１のシンボル156は、データバッファ26から読み出され、ステップ46においてシンドローム生成器に入力される。同時に、第１のシンボル156は、図4hのフロー図を実行することによって、ステップ50でデータCRCシンドロームを更新するために用いられる。図4hのステップ158において、ROWは、24未満であるので、シンボルは、図５における154から第１のＰ符号語の第１のシンボル156に調整した後、データCRCレジスタに加算される。ステップ160における動作
DATA_REG・xDOWN_1 MOD G(x) + DATA(H,L)
は、Ｐ符号語シンボルDATA(H,L)をデータCRCシンドロームに加算する前に、データバッファにおいて飛ばされたシンボルを補償するするためにデータCRCシンドロームを１行下のシンボルに調整する。ステップ160において、データCRCレジスタのコンテンツをxDOWN_1 MOD G(x)で乗算して、データCRCシンドロームを１つ下の行に調整することについては、以下に詳細に説明する。
【００７４】
書き込み動作中において、図２ａのヘッダ１６およびユーザデータ１８を、単一符号語またはビットまたは係数のリニアシーケンスを有する多項式(polynomial)として処理することによりCRC冗長性が発生するため、データCRCレジスタを１行下げて調節することは必要である。結果として、読み出し動作の間、積符号中のデータをリニア符号語または多項式として扱い、これをCRC生成器多項式Ｇ（ｘ）で除算することにより、CRCシンドロームSCRCが生成される。P符号語のシンボルは積符号の列中に存するため（例えば、図２ｃにおいて列０すなわちバイト0000、0043、0086、0129．．．が１番目のP符号語を格納する）、シンドロームを生成するためのCRCレジスタは、バッファ内の飛ばされたシンボルを補償するように調節されなければならない。従って、P符号語中の次のシンボルをデータCRCシンドロームに加える前に、データCRCレジスタを、ステップ１６０においてシンボルのDOWN_1行分調節する。
【００７５】
図５に示すP符号語のPECC冗長性シンボル１６２ａおよび１６２ｂは、書き込み動作中にはCRCシンドロームに加えられない−−従って、これらは読み出し動作中において飛ばされる。図４ｈのステップ１５８においてROWが２４に等しいとき、ステップ１６０を飛ばすことにより、PECC冗長性１６２ａおよび１６２ｂはデータCRCシンドローム中に加えられない。ＲＯＷが現在のP符号語の最後のシンボルに等しいとき（すなわちステップ１６４においてROWが２５に等しいとき）、ステップ１６６においてデータCRCレジスタを
ｘUP_24_RIGHT_2 MOD G(x)
で乗算することにより、データCRCレジスタを図５の位置１６８から位置１７０まで、すなわち次のP符号語における第１のシンボル１７２のシンボル１つ上まで、調整する。UP_24オフセットにより、データCRCシンドロームは２４行上に移動され、RIGHT_2オフセットにより、データCRCシンドロームは１列移動される（オフセットはRIGHT_1ではなくRIGHT_2である。なぜなら、データはインターリーブされて図２ｃを参照して上述したようにEVENまたはODD積符号を作成するからである）。
【００７６】
P符号語を処理する間、図４ａのステップ５４における誤りシンドロームは、非ゼロ（符号語が誤りを含むことを示す）であり得る。従って、ステップ６６においてECC_BUSYフラグをセットすることによって誤り訂正手順が開始され、図３の誤り訂正器３０が、次のP符号語に対するシンドローム生成と非同期的かつ同時に、現在のP符号語を訂正する。現在のP符号語が訂正される際、訂正値を用いて図４ｉのフローチャートを実行することにより、図４ｃのステップ１０８において誤りCRCシンドロームを更新する。
【００７７】
図４ｉ中、ステップ１７４において、システムがP符号語を訂正中であるかQ符号語を訂正中であるかに応じて、分岐する。今回がP符号語についての最初のパスであるため、図４ｉのフローチャートを実行することにより、誤りCRCシンドロームを適宜更新する。ステップ１７６において、変数C_COLを現在のCOLにセットし（すなわちP符号語が訂正中である）、変数C_ROWをその符号語の１番目のシンボルにセットする（すなわちゼロにセットする）。次に、ステップ１７８においてUNCフラグがセットされた（符号語が訂正不可能であったことを示す）、あるいはシンドロームがゼロである（符号語が誤りを含まなかったことを示す）ならば、ステップ１８０において、誤りCRCレジスタを
ｘRIGHT_2 MOD G(x)
で乗算することにより、誤りCRCシンドロームを単に次のP符号語に調節する。しかし、ステップ１７８において訂正中である符号語が１番目のP符号語である場合、これを常に処理することにより、誤りCRCシンドロームを最後のシンボル上に位置させる（すなわち図５のシンボル162b）−−このことにより、後述の乗算演算ＸK MOD G(X)を実現するために必要なテーブルの数が減少する。
【００７８】
P符号語についての各パスの最初において、誤りCRCシンドロームを１番目のP符号語中の１番目のシンボルに位置させる（すなわち図５のシンボル１５６に位置させる）。その後、誤りCRCシンドロームを残りのP符号語中の１番目の１つ上に位置させる（例えば、誤りCRCシンドロームを、２番目のP符号語を処理する前に位置１７０に位置させる）。従って、１番目のP符号語以外の全てを処理するとき、１番目のシンボルに対する訂正値をステップ１８４において誤りCRCシンドロームに加算する前に、まずステップ１８２において誤りCRCシンドロームを１行下げるように調節する。すなわち、ステップ１８６においてステップ１８２を飛ばす分岐は、１番目のP符号語の１番目のシンボル（すなわちC_COLおよびC_ROWがゼロのとき）についてしか選択されない。従って、次のシンボルの訂正値を加算する前に、誤りCRCシンドロームはステップ１８２において常に１行下げて調節される。
【００７９】
ステップ１８４においてERR(H,L)と示す訂正値は、EVEN積符号およびODD積符号の両方について、P符号語中の現在のシンボルのためのものである。訂正値は、EVEN積符号およびODD積符号のシンボルのいずれかについて、ゼロ（すなわち訂正なし）または非ゼロ（すなわち訂正がなされた）であり得る。各シンボルを通じて誤りCRCシンドロームが「進められる(step)」ため、P符号語中の各シンボルについて訂正値を生成する。しかし、PECCシンボルを処理する際の訂正値は、書き込み動作中においてCRC冗長性に含まれないため、ゼロである。現在のP符号語中の全てのシンボルを処理した後（すなわちステップ１８８においてC_ROWが２５に等しい）、ステップ１９０において誤りCRCシンドロームを２６行（UP_26）上げ、かつ１列動かして（RIGHT_2）調整することにより、誤りCRCシンドロームを次のP符号語中の１番目のシンボルの１つ上に（例えば、１番目のP符号語を処理した後、図５のシンボル162bから位置１７０に）位置させる。次に、図４ｉのフローチャートを再び実行して次のP符号語を処理しまたは飛ばす。
【００８０】
全てのP符号語が処理されるまで（すなわちステップ６８においてCOLが４２に等しくなるまで）、図４ａのフローチャートを繰り返す。P符号語についての最初のパスの後、データCRCシンドロームの生成が完了する。このように、後続のPパスおよびQパスの間、訂正値を用いて誤りCRCシンドロームのみが調整される。また、１番目のPパスの後、制御は図４ｋに分岐し、CRCシンドロームSCRCを用いて（誤りおよびデータCRCシンドロームを結合させた後）積符号に対する訂正が有効かつ完全であるか否かをチェックする。訂正が完全でなければ、制御は図４ｂに分岐してQ符号語を処理する。
【００８１】
Qパスを開始する前に、誤りCRCシンドロームを図５の１番目のQ符号語の１番目のシンボル１５６に調整する。前のPパスの間に最後のP符号語のシンドロームがゼロであれば（すなわち最後のP符号語についての読み出しフラグがセットされておらず、ステップ４２において最初のPパスでなく図４ａのステップ４３において誤りシンドロームがゼロにセットされている）、あるいはステップ５４においてシンドロームがゼロであれば、図４ｉのフローチャートを実行することにより図４ａのステップ６１において誤りCRCシンドロームを更新する。図４ｉにおいて、ステップ１７８においてシンドロームがゼロなので、ステップ１８０において、誤りCRCレジスタの内容を
ｘRIGHT_2 MOD G(X)
で乗算することにより、現在のP符号語を飛ばすように誤りCRCシンドロームを調整する。
【００８２】
この演算(operation)により、誤りCRCシンドロームを図５の位置１９２から位置１５６に（すなわち１番目のQ符号語中の１番目のシンボルに）位置させる。図４ａのステップ５４において最後のP符号語に対して生成されるシンドロームが非ゼロであれば、図４ｃのステップ１０８において誤りCRCシンドロームを更新する。図４ｉのステップ１９０において誤りCRCレジスタを
ｘUP_26_RIGHT_2 MOD G(X)
で乗算することにより、誤りCRCシンドロームを図５の位置１９４から位置１５６に位置させる。
【００８３】
Q符号語についてのパス中、ステップ７４において現在のQ符号語を飛ばした場合またはステップ８６においてシンドロームがゼロの場合は、誤りCRCシンドロームを図４ｂのステップ９４において更新してもよい。誤りCRCシンドロームはまた、図４ｂのステップ８６においてシンドロームが非ゼロである場合も、図４ｃのステップ１０８において更新される。Qパス中に誤りCRCシンドロームを更新するためのフローチャートを、図４ｊに示す。ステップ１９６において、C_ROW変数を現在のQ符号語に（すなわちROW_INITに）セットし、C_COL変数を０に（すなわち現在のQ符号語の１番目のシンボルに）セットする。ステップ１９８において、UNCフラグがセットされており現在のQ符号語が訂正不可能であるか、符号語のシンドロームがゼロでありかつ符号語が最後のQ符号語でない場合（すなわちC_ROW < ２５）、ステップ２００において、誤りCRCレジスタを
ｘDOWN_1 MOD G(X)
で乗算することにより現在のQ符号語を飛ばす。例えば、１番目のQ符号語が飛ばされたならば、ステップ２００における乗算により、誤りCRCシンドロームは図５の位置１５６から位置２０２に（すなわち次のQ符号語中の１番目のシンボルに）位置される。後述のｘK MOD G(X)乗算を実現するために必要なテーブルの数を減少させるために、誤りCRCシンドロームは最後のQ符号語を通じて常に進められる（ROW_INIT = 25）。
【００８４】
ステップ１９８においてUNCフラグがセットされておらずかつ現在のQ符号語のシンドロームがゼロでない場合、あるいは最後のQ符号語である場合は、Q符号語を通じて誤りCRCシンドロームを進め、図４ｉを参照して上述したPパスと同様な訂正値を用いて更新する。Pパスとは対照的に、誤りCRCシンドロームは常に各Q符号語の１番目のシンボル上に位置される。従って、ステップ２０４においてC_COLがゼロならば、誤りCRCシンドロームは調整されず、訂正値はステップ２０６において単に誤りCRCレジスタ中に加えられる。ステップ２０４においてC_COLがゼロでなければ（すなわち１番目のシンボルにいなければ）、現在の位置に応じて誤りCRCシンドロームを調整する。ステップ２０８においてC_ROWが２５でなければ、ステップ２１０において誤りCRCレジスタの内容を
ｘDOWN_1_RIGHT_2 MOD G(X)
で乗算することにより誤りCRCシンドロームをQ符号語の次のシンボルに調整する。例えば、誤りCRCシンドロームが図５における１番目のQ符号語の１番目のシンボル１５６上に位置しているならば、上述の乗算により、誤りCRCシンドロームは１番目のQ符号語の次のシンボル２１２に位置される。ステップ２０８においてC_ROWが２５ならば、ステップ２１４において誤りCRCレジスタの内容を
ｘUP_25_RIGHT_2 MOD G(X)
で乗算することにより、誤りCRCシンドロームをQ符号語の次のシンボルに調整する。
【００８５】
例えば、図５の１番目のQ符号語を処理する際にC_ROWが２５に等しいとき、誤りCRCシンドロームは位置２１６から位置２１８に調整される。やはり、ステップ２０６において訂正値はEVENQ符号語およびODDQ符号語のいずれかまたは両方についてゼロまたは非ゼロであり得、PECCおよびQECCシンボルを処理する際の訂正値は、CRC冗長性に含まれないため常にゼロである。ステップ２２０においてC_ROWおよびC_COLをインクリメントし、ステップ２２４においてC_ROWが２６であればステップ２２２においてC_ROWをゼロにリセットする。
【００８６】
このプロセスを、現在のQ符号語の最終シンボルが処理されるまで（すなわちステップ２２６においてC_COLが４３に等しくなるまで）繰り返す。この時点において、誤りCRCシンドロームを次のQ符号語の１番目のシンボル上に位置変えする。誤りCRCレジスタの調整は、現在のQ符号語に依存する。図５のQ符号語０から９に対して、最後のシンボル位置はそれぞれ２２８から１９４である。従って、ステップ２３０においてROW_INITが10未満であれば、誤りCRCレジスタへの調整s値はRIGHT_2_UP_16である。例えば、RIGHT_2オフセットにより、誤りCRCシンドロームは図５の位置２２８から位置２３２に位置され、UP_16オフセットにより誤りCRCシンドロームは位置２３２から位置２０２に（すなわち次のQ符号語の１番目のシンボルに）位置される。ｘK MOD G(X)乗算を実現するために必要なテーブルの数を減少させるために、RIGHT_2_UP_16調整を２段階で実行する。すなわち、まずステップ２３４において誤りCRCレジスタを
ｘUP_25_RIGHT_2 MOD G(X)
で乗算し、次にステップ２３６において誤りCRCレジスタを
ｘDOWN_9 MOD G(X)
で乗算する。
【００８７】
ステップ２３０において現在のQ符号語(ROW_INIT)が10から24であれば、現在のQ符号語中の最後のシンボルはそれぞれ、図５の位置２４２から２４４にある。この場合、誤りCRCシンドロームを次のQ符号語の１番目のシンボル上に位置させるための誤りCRCシンドロームの調整値は、RIGHT_2_DOWN_10である。例えば、現在のQ符号語が10であれば、図５において１番目のシンボルは２４６にあり、最後のシンボルは２４２にある。RIGHT_2オフセットにより、誤りCRCシンドロームは位置２４２から位置２０２に位置され、DOWN_10オフセットにより誤りCRCシンドロームは位置２０２から位置２４８に（すなわち次のQ符号語中の１番目のシンボルに）位置される。やはり、ｘK MOD G(X)乗算を実現するために必要なテーブルの数を減少させるために、RIGHT_2_UP_10調整を２段階で実行する。すなわち、まずステップ２５０において誤りCRCレジスタを
ＸDOWN_1_RIGHT2 MOD G(X)
で乗算し、次にステップ２３６において誤りCRCレジスタを
ＸDOWN_9 MOD G(X)
で乗算する。
【００８８】
上述のRIGHT_2_UP_16オフセットは、別のPパスを開始する前の最後のQ符号語の終わりの誤りCRCシンドロームに対する調節値と同じ調節値である。すなわち、RIGHT_2オフセットにより、誤りCRCシンドロームは位置２３８から位置２４０に位置され、UP_16オフセットにより、誤りCRCシンドロームは図５の位置２４０から位置１５６に（すなわち１番目のP符号語中の１番目のシンボルに）位置される。このように、ステップ２３０においてROW_INITが２５に等しいとき、ステップ２３４および２３６における乗算により、誤りCRCシンドロームに対してRIGHT_2_UP_16の調節を行い、１番目のP符号語の１番目のシンボル上に位置させる。
【００８９】
P符号語およびQ符号語についての各パスの終わりにおいて、図４ｋのフローチャートを実行して積符号が完全に訂正されたか訂正不可能であるかを決定する。ステップ２５２において、システムはCRCチェックを行う前にECC_BUSYフラグがクリアされるのを待つ。ステップ２５４において訂正不可能誤りフラグUNCがセットされていなければ（前回のPパスまたはQパス中に訂正不可能な誤りに出会わなかったことを示す）、CRCシンドロームSCRCは、積符号になされた訂正が有効かつ完全であるか否かを示す。CRCシンドロームSCRCはP符号語およびQ符号語の処理と同時に生成されるため、PパスおよびQパスの終わりにおいてCRCシンドロームSCRCは、P/Qデコーダ２によってなされる訂正の有効性検証のためにすぐに使用可能である。ステップ２５６においてCRCシンドロームSCRCが正しければ、訂正手順は、従来技術で必要とされるような追加的なパスを行うことなくステップ２５８において成功して終了する。
【００９０】
ステップ２５４でUNCフラグがセットされれば、ステップ２５６においてパスカウント変数PASS_CNTがインクリメントされ、PASS_CNTが所定の最大値を越えれば、積符号は訂正不可能であり訂正手順はステップ２５８において不成功で終了する。ステップ２５６においてPASS_CNTが最大値未満であれば、PおよびQパス中ステップ２６０において変更がなされていなければ（訂正無しかつ変更されたポインタ無し）、訂正手順はやはりステップ２５８において不成功で終了する。なぜなら追加のパスは役立たないからである。そうでない場合、UNCフラグをステップ２６２においてクリアし、ステップ２６４において別のPまたはQパスを実行することにより訂正手順を継続する。
【００９１】
CRCシンドロームSCRCはP符号語およびQ符号語の訂正と同時に計算されるため、訂正手順はPパスまたはQパスの終わりにおいて成功して終了し得る。結果として、本発明は、従来技術において訂正が完全かどうかを決定するために必要とされる追加的なパスを回避する。さらに本発明は、従来技術において訂正プロセスの終わりにCRCシンドロームSCRCを生成するために必要とされる追加的なパスを回避する。このように、本発明は、光記憶装置用のEDACシステムのスループットを大きく増大させることにより、従来技術に対して大きな改良を提供する。
【００９２】
（CRCシンドローム生成器）
図３のCRC生成器３２は、書き込み動作中において図２ａに示すセクタのためにCRC冗長性２０を生成し、読み出し動作中において、図４ａ〜図４ｋを参照して上述した誤り訂正器３０によってなされる訂正の有効性検証に用いるためのCRCシンドロームSCRCを生成する。図６は、書き込み動作中においてCRC冗長性２０を生成するための、従来のリニアフィードバックシフトレジスタ（LSFR）を示している。図６に示すLFSRの動作は周知である−−LFSRは入力多項式Ｄ（ｘ）を生成器多項式G(x)：
G(x)＝  ｇiｘi ＋ ｇi-1ｘi-1 ＋ ．．． ＋ ｇ1ｘ ＋ ｇ0
で除算する。入力多項式D(x)の係数はLFSRを通ってシリアルにシフトされる。シフト数は入力多項式の次数(degree)＋１に等しい。図２ａに示すセクタのためにCRC冗長性２０を生成するために、ユーザデータ１８およびヘッダ１６のｋビットを多項式P(X)の係数として表す。CRC冗長性は、
CRC冗長性＝P(x)・ｘn-k mod G(x)
として計算される。ｎ−ｋはCRC冗長性シンボルの数であり、G(x)は生成器多項式である。最終シフトの後のレジスタの内容はCRC冗長性２０であり、これを次に、得られる符号語がディスクに書き込まれるよりも前に図２ａに示すようにユーザデータにアペンドする。
【００９３】
読み出し動作中において、ディスクから読み出されるデータを処理し、
CRCシンドロームSCRC ＝ C(x) mod G(x)
に従ってCRCシンドロームSCRCを生成する。
【００９４】
上式においてC(x)は、ディスクから読み出されたデータ多項式または符号語（CRC冗長性を含む）である。従来技術において、図２ａの符号語は、誤り訂正器３０が訂正を終えた後に図３のデータバッファ２６からシリアルに読みだされる。従って、図６の同じLFSR回路を用いて上式に従いCRCシンドロームSCRCが生成される。
【００９５】
本発明において、ＣＲＣシンドロームＳCRCは、図４ａ〜図４ｋを参照しながら上述したように符号語を訂正する際に同時に生成される。従って、符号語が一連の連続するビットとして処理されていないので、図６のＬＦＳＲ回路を用いてＣＲＣシンドロームＳCRCを生成することはできない。本発明のＣＲＣシンドローム生成器がどのようにしてＣＲＣシンドロームＳCRCを生成するのかを説明する前に、本発明のＣＲＣシンドローム生成器の概要を説明する。
【００９６】
図７は、ＤＡＴＡCRC回路３００およびＥＲＲＯＲCRC回路３０２を備える図３のＣＲＣシンドローム生成器３２のブロック図である。図４ａを参照して上述したように、ＤＡＴＡCRCは、図３のデータバッファ２６から読み出した未訂正データを用いて図２ｃの積符号に対する第１のＰパスの間にステップ５０において生成される。ＥＲＲＯＲCRCは、ＰおよびＱ符号語の反復的処理の間に誤り訂正器３０によって生成される訂正値を用いて生成される。ＰおよびＱパスの終わりに、ＤＡＴＡCRCおよびＥＲＲＯＲCRCを結合回路３０４によって結合させて、最終的なＣＲＣシンドロームＳCRCを生成する。このＣＲＣシンドロームＳCRCを、図４ｋのステップ２５６において所定の訂正値と比較することにより、ＰおよびＱ符号語の訂正が有効であり且つ完了しているかどうかを決定する。結合回路３０４によって行われる数学的機能は、ＤＡＴＡCRCおよびＥＲＲＯＲCRCの単純な排他的論理和である。
【００９７】
図７のＤＡＴＡCRC３００およびＥＲＲＯＲCRC３０２を図８により詳細に示す。好適な実施形態において、ＣＲＣシンドローム生成器多項式Ｇ（ｘ）の次数は３２であるが、実行を簡単にするために、それぞれ次数１６である２つの多項式Ｇ0（ｘ）およびＧ1（ｘ）に因数分解される(factored)。図７のＤＡＴＡCRC３００およびＥＲＲＯＲCRC３０２は、図２ａの符号語多項式Ｃ（ｘ）を、複数のサブセット多項式の１次結合(linear combination)
Ｃ（Ｘ）＝Ｃj（ｘ）＋Ｃj-1（ｘ）＋．．．＋Ｃ0（ｘ）
として表すことによって、ＣＲＣシンドロームＳCRCを生成する。但し、各サブセット多項式Ｃk（ｘ）は、符号語多項式Ｃ（ｘ）の中の所定数のビットを含む。本願に開示される実施形態において、各サブセット多項式は、符号語多項式Ｃ（ｘ）の１６ビットを含み、１６進数表記においては、
0003966993.tif 000002
となる。このようにして、ＣＲＣシンドロームＳCRCを、概念的に、各サブセット多項式のＣＲＣシンドロームの１次結合
ＣＲＣシンドロームＳCRC＝Ｃ0（ｘ） ｍｏｄ Ｇ（ｘ）＋Ｃ1（ｘ） ｍｏｄＧ（ｘ）＋．．．＋Ｃj（ｘ） ｍｏｄ Ｇ（ｘ）
として生成することができる。上記等式を、
ＣＲＣシンドロームＳCRC＝￣Ｃ0（ｘ）・ｘ16・0 ｍｏｄ Ｇ（ｘ）＋￣Ｃ1（ｘ）・ｘ16・1 ｍｏｄ Ｇ（ｘ）＋．．．＋￣Ｃj（ｘ）・ｘ16・j ｍｏｄ Ｇ（ｘ）
と書き直すことができる（本願においては、「Ｃ」の上側にバー「￣」を付した記号を「￣Ｃ」で代用する）。但し、￣Ｃk（ｘ）は符号語Ｃ（ｘ）の中の１６ビット多項式である（即ち、￣Ｃk（ｘ）＝Ｃk（ｘ）・ｘ-16k）。本発明において利用される別の数学的関係は、
￣Ｃk（ｘ）・ｘn+m ｍｏｄ Ｇ（ｘ）＝（￣Ｃk（ｘ）・ｘn ｍｏｄ Ｇ（ｘ））・ｘm ｍｏｄ Ｇ（ｘ）
である。
【００９８】
再び図５を参照して、上記等式を用いて、Ｐ符号語に対する第１のパスの間に、図２ｃの偶数および奇数積符号の第１のバイト１５６について、ＣＲＣシンドロームを計算することができる。偶数および奇数積符号からのバイト１５６は、上記符号語Ｃ（ｘ）の最上位係数および上記サブセット多項式Ｃj（ｘ）のゼロでない係数を含む。再び図８を参照して、図２ｃの偶数および奇数符号語の第１のバイト２５６は、１６ビットレジスタ３０８Ａおよび３０８Ｂにロードされる（加算器３１０Ａおよび３１０Ｂにおいてゼロを加算した後）。その後、偶数および奇数Ｐ符号語の次のバイト２０２が読み出されると、乗算器３１２Ａおよび３１２Ｂにおいて、レジスタ３０８Ａおよび３０８Ｂの内容にｘK ｍｏｄ Ｇ（ｘ）を掛ける。但し、Ｋは１行分のビット（ＤＯＷＮ＿１）に等しい。その後、乗算結果をレジスタ３０８Ａおよび３０８Ｂに再ロードする（加算器３１０Ａおよび３１０Ｂにおける、その特定のサブセット多項式についてのＣＲＣシンドローム計算を開始する偶数および奇数Ｐ符号語の次のバイト２０２の加算の後）。第１のＰ符号語の最後のバイト１６８の読み出しが完了するまで、上記計算を残りのバイトについても行う。レジスタ３０８Ａおよび３０８Ｂの内容にｘK ｍｏｄ Ｇ（ｘ）を掛けることによって図５の位置１７０にＣＲＣシンドロームを調節する。但し、Ｋは、２４行分上、１列分右に等しい（即ち、上述した図４ｈのステップ１６６におけるＫ＝ＵＰ＿２４＿ＲＩＧＨＴ＿２）。図３のコントローラ２８は、乗算器３１２Ａおよび３１２ＢのＳＥＬ制御ラインを介して、オフセット値Ｋに対して適切な値を選択する。この処理は、図５の最後のＰ符号語の最後のシンボルの読み出しが完了するまで行われ、レジスタ３０８Ａおよび３０８Ｂは、他のバイト（即ち、他のサブセット多項式）について計算されるＣＲＣシンドロームに加算される、符号語Ｃ（ｘ）全体の初めの２バイトについての（即ち、サブセット多項式Ｃj（ｘ）についての）ＣＲＣシンドロームを含み、これにより、符号語Ｃ（ｘ）全体についてのデータＣＲＣシンドロームを生成する。
【００９９】
誤りＣＲＣを生成する図７のＥＲＲＯＲCRC回路３０２は、図８の回路部(circuitry)をも含む。図３の誤り訂正器３０によって、ある訂正値が生成されると、その訂正値は、加算器３１０Ａおよび３１０Ｂにおいてレジスタ３０８Ａおよび３０８Ｂに加算される。乗算器３１２Ａおよび３１２Ｂは、訂正値が生成されたかどうか、あるいは、上述のようにＰまたはＱ符号語が飛ばされたかどうかに関わらず、ＰまたはＱ符号語における各シンボルが処理される度に、レジスタ３０８Ａおよび３０８Ｂの内容に適切なＫオフセットを掛ける乗算を続ける。ＰおよびＱパスの終わりに、データＣＲＣおよび誤りＣＲＣを結合させ、これにより、訂正が有効であり且つ完了しているかどうかを図４ｋのステップ２５６において決定する際に使用される最終的なＣＲＣシンドロームＳCRCを生成する。
【０１００】
図８のｘK ｍｏｄ Ｇ（ｘ）乗算器３１２Ａおよび３１２Ｂを実施する好適な実施形態は、図９を参照して理解される。図９は、計算
ｘK+i ｍｏｄ Ｇ（ｘ）
によって生成される余り(remainders)のテーブル(table)を表す。但し、ｉは、｛０．．１５｝に等しい。図９のテーブルは、ＣＲＣシンドロームの計算の際に使用されるＫオフセット値のそれぞれについて生成される。その後、図８のレジスタ３０８Ａおよび３０８Ｂの内容を適切なテーブルで掛けることによって（即ち、１６ビットベクトルに１６×１６マトリクスを掛けることによって）、乗算処理を行う。
【０１０１】
因数分解された２つの１６ビットＣＲＣ生成器Ｇ0（ｘ）およびＧ1（ｘ）についてのｘK ｍｏｄ Ｇ（ｘ）乗算を実行するための実際のテーブルを、図１０ａ〜図１０ｆのＶＨＤＬソースコードに示す。第１の組のテーブルは、Ｐ符号語の第１のパスの間にｘK ｍｏｄ Ｇ（ｘ）乗算を実行するためのものである。例えば、ｒｏｗ１＿ｔｂｌのラベルが付けられたテーブルは、第１のＣＲＣ生成器Ｇ0（ｘ）についてのＤＯＷＮ＿１オフセットを実行するためのものであり、テーブルｒｏｗ２＿ｔｂｌは、第２のＣＲＣ生成器Ｇ1（ｘ）についてＤＯＷＮ＿１オフセットを実行するためのものである。同様に、テーブルｃｏｌ１＿ｔｂｌおよびｃｏｌ２＿ｔｂｌは、それぞれ第１および第２のＣＲＣ生成器についてのＵＰ＿２４＿ＲＩＧＨＴ＿２オフセットを実行するためのものである。ＶＨＤＬコードにおける第２の組のテーブルは、ＰおよびＱ符号語に対する後続のパスの間に（即ち、誤りＣＲＣシンドロームのみが更新されるときに）、ｘK ｍｏｄ Ｇ（ｘ）乗算を実行するためのものである。これらのテーブルのラベルは説明不要な自明ラベルである。例えば、ｒ２＿１＿ｔｂｌおよびｒ２＿２＿ｔｂｌのラベルが付けられたテーブルは、それぞれ第１および第２のＣＲＣ生成器についてのＲＩＧＨＴ＿２オフセットを実行するためのものである。
【０１０２】
図１０ａ〜図１０ｆのＶＨＤＬソースコードの残りは、図８のレジスタ３０８Ａおよび３０８Ｂの内容に適切なテーブルを掛けることによって（即ち、１６ビットベクトルに１６×１６マトリクスを掛けることによって）、実際の乗算処理を行うためのものである。入力レジスタまたはベクトルと、マトリクスとの積は出力ベクトルであり、出力ベクトルの各要素(element)は、テーブル（またはマトリクス）のｉ行目のｎ個の要素の積を、レジスタの対応成分(components)と合算する(summing)ことによって生成される。この和(sum)は、
【０１０３】
【数１】
0003966993.tif 000003
【０１０４】
と書くことができる。但し、ｙiは、乗算器３１２Ａおよび３１２Ｂの出力ベクトルであり、ａikは、図９のテーブルのｉ行目の１６ビットであり、ｘkは、レジスタ３０８Ａおよび３０８Ｂに格納された１６ビットである。乗算器３１２Ａおよび３１２Ｂからの出力ベクトルｙiを加算器３１０Ａおよび３１０Ｂにおいて入力ビットに加え、その結果をレジスタ３０８Ａおよび３０８Ｂに再格納(restored)する。
【０１０５】
本願に開示される実施形態を通して本発明の目的が完全に認識される。本発明の複数の局面を、その本質的な機能から逸脱することなく、他の様々な実施形態によって達成できることが当業者には理解される。開示した特定の実施形態は、説明用であり、添付の請求項によって適切に解釈される本発明の範囲を制限するものではない。
【０１０６】
【発明の効果】
本発明によれば、少なくとも以下の効果が得られる。
【０１０７】
すなわち、Ｐ／Ｑ復号化器が符号語を飛ばしても、Ｐ／Ｑ復号化器が積符号を処理しているのと同時に、ＣＲＣシンドローム生成器はＣＲＣシンドロームＳCRCを計算できる。また、ＥＤＡＣシステムにおいて、訂正が終了したことを検査するために必要とされる別のパスが不要となるとともに、ＣＲＣシンドロームＳCRCを生成するために必要とされる別のパスも不要となる。
【図面の簡単な説明】
【図１】ＣＤ−ＲＯＭ光記憶装置で用いられる典型的な誤り検出／訂正（ＥＤＡＣ）システムのブロック図である。
【図２ａ】ＣＤ−ＲＯＭ光記憶装置で用いられるセクタの典型的なフォーマットを示す図である。
【図２ｂ】図２ａのヘッダおよびユーザデータを符号化するためのＰ／Ｑ積符号のフォーマットを示す図である。
【図２ｃ】偶数バイトおよび奇数バイトをそれぞれ格納するＥＶＥＮ  Ｐ／Ｑ積符号およびＯＤＤ  Ｐ／Ｑ積符号として実現される図２ｂのＰ／Ｑ積符号を示す図である。
【図３】ＥＣＣ／シンドローム生成器、誤り訂正器、およびＣＲＣ生成器／訂正検査器を含む、本発明のＥＤＡＣシステムのブロック図である。
【図４ａ】積符号のＰ（または列）符号語の処理についてのメインフロー図である。
【図４ｂ】積符号のＱ（または行）符号語の処理についてのメインフロー図である。
【図４ｃ】「誤りの無い」符号語を飛ばしやすくするための消去ポインタの処理について、および符号語が訂正されたときの誤りＣＲＣシンドロームの更新についてのフロー図である。
【図４ｄ】符号語が誤り（ゼロでないシンドローム）とゼロの消去ポインタとを含む場合のフロー図である。
【図４ｅ】符号語が誤り（ゼロでないシンドローム）と１つの消去ポインタとを含む場合のフロー図である。
【図４ｆ】符号語が誤り（ゼロでないシンドローム）と２つの消去ポインタとを含む場合のフロー図である。
【図４ｇ】符号語が誤り（ゼロでないシンドローム）と３つ以上の消去ポインタとを含む場合のフロー図である。
【図４ｈ】Ｐ符号語の第１のパスの間に行われるデータＣＲＣシンドロームの更新についてのフロー図である。
【図４ｉ】Ｐ符号語のパスの間に行われる誤りＣＲＣシンドロームの更新についてのフロー図である。
【図４ｊ】Ｑ符号語のパスの間に行われる誤りＣＲＣシンドロームの更新についてのフロー図である。
【図４ｋ】ＣＲＣシンドロームＳCRCを用いて訂正が有効であり且つ終了しているかどうかを調べるために、ＰパスまたはＱパスの終わりで実行されるフロー図である。
【図５】Ｐ／Ｑ積符号の処理順序と、検査ＣＲＣシンドロームＳCRCがどのように生成されるか、とを示す図である。
【図６】書き込み動作の間にＣＲＣ冗長性を生成する際に用いられ、且つ、読み出し動作の間にＣＲＣシンドロームを生成する際に用いられる、従来の線形フィードバックシフトレジスタ（ＬＦＳＲ）を示す図である。
【図７】ＣＲＣシンドロームのＤＡＴＡ部を計算するためのＤＡＴＡCRC回路と、ＣＲＣシンドロームのＥＲＲＯＲ部を計算するためのＥＲＲＯＲCRC回路と、ＤＡＴＡレジスタおよびＥＲＲＯＲレジスタを組み合わせて最終のＣＲＣシンドロームＳCRCを生成するための回路とを含むＣＲＣ訂正検査回路のブロック図である。
【図８】図７のＤＡＴＡCRC回路およびＥＲＲＯＲCRC回路の詳細なブロック図である。
【図９】図８に示す乗数ｘK ｍｏｄ Ｇ（ｘ）を計算するためのマトリクスの一般的な形態を示す図である。
【図１０ａ】２つの１６ビットＣＲＣ生成器についてのｘK ｍｏｄ Ｇ（ｘ）乗算を実行するための実際のテーブルを示すＶＨＤＬソースコードを示す図である。
【図１０ｂ】２つの１６ビットＣＲＣ生成器についてのｘK ｍｏｄ Ｇ（ｘ）乗算を実行するための実際のテーブルを示すＶＨＤＬソースコードを示す図である。
【図１０ｃ】２つの１６ビットＣＲＣ生成器についてのｘK ｍｏｄ Ｇ（ｘ）乗算を実行するための実際のテーブルを示すＶＨＤＬソースコードを示す図である。
【図１０ｄ】２つの１６ビットＣＲＣ生成器についてのｘK ｍｏｄ Ｇ（ｘ）乗算を実行するための実際のテーブルを示すＶＨＤＬソースコードを示す図である。
【図１０ｅ】２つの１６ビットＣＲＣ生成器についてのｘK ｍｏｄ Ｇ（ｘ）乗算を実行するための実際のテーブルを示すＶＨＤＬソースコードを示す図である。
【図１０ｆ】２つの１６ビットＣＲＣ生成器についてのｘK ｍｏｄ Ｇ（ｘ）乗算を実行するための実際のテーブルを示すＶＨＤＬソースコードを示す図である。
【符号の説明】
２    Ｐ／Ｑ符号化器／復号化器
６    Ｃ２符号化器／復号化器
２６  データバッファ
２８  コントローラ
２９  ＥＣＣ／シンドローム生成器
３０  誤り訂正器
３２  ＣＲＣ生成器／訂正検査器
３４  Ｃ２ポインタ
３００  ＤＡＴＡCRC回路
３０２  ＥＲＲＯＲCRC回路
３０４  結合回路
３０８Ａ、３０８Ｂ  レジスタ
３１０Ａ、３１０Ｂ  加算器
３１２Ａ、３１２Ｂ  乗算器
【図１】
0003966993.tif 000004
【図２ａ】
0003966993.tif 000005
【図２ｂ】
0003966993.tif 000006
【図２ｃ】
0003966993.tif 000007
【図３】
0003966993.tif 000008
【図４ａ】
0003966993.tif 000009
【図４ｂ】
0003966993.tif 000010
【図４ｃ】
0003966993.tif 000011
【図４ｄ】
0003966993.tif 000012
【図４ｅ】
0003966993.tif 000013
【図４ｆ】
0003966993.tif 000014
【図４ｇ】
0003966993.tif 000015
【図４ｈ】
0003966993.tif 000016
【図４ｉ】
0003966993.tif 000017
【図４ｊ】
0003966993.tif 000018
【図４ｋ】
0003966993.tif 000019
【図５】
0003966993.tif 000020
【図６】
0003966993.tif 000021
【図７】
0003966993.tif 000022
【図８】
0003966993.tif 000023
【図９】
0003966993.tif 000024
【図１０ａ】
0003966993.tif 000025
【図１０ｂ】
0003966993.tif 000026
【図１０ｃ】
0003966993.tif 000027
【図１０ｄ】
0003966993.tif 000028
【図１０ｅ】
0003966993.tif 000029
【図１０ｆ】
0003966993.tif 000030