JPH10508988A - Ｃｒｃ／ｅｄｃチェッカシステム - Google Patents

Abstract

(57)【要約】 ＥＤＣ／ＣＲＣチェッカ（70）は、訂正パスの間に、１データブロックが訂正されているあいだに、ＥＤＣ／ＣＲＣチェックをおこなうことによって、ブロック訂正に引き続いてＥＤＣ／ＣＲＣを目的としてバッファにアクセスすることを不要にする。訂正パスのあいだ、ＥＤＣ／ＣＲＣの和が累算される。その和は、そのブロックのパスが完了した後、もしそのブロックにおけるＥＤＣ／ＣＲＣバイトによりそのブロックが訂正されたことが確認されれば、ゼロになる。ブロックの一回の訂正パスのあいだに、訂正されていない、最も最近のコードワードのバイトが、累算された和に加算される。最も最近のコードワードのバイトとバイト同期関係にある以前のコードワードのバイトは、（必要であれば）訂正され、かつ（訂正がおこなわれる時には）以前のコードワードのバイトを訂正するのに用いられた誤りパターンを含む誤りパターン係数もまた、累算された和に加算される。ここで説明される実施形態では、ブロックは、複数のコードワードカラムを有するものとして概念づけられ、バイト同期関係は、訂正されていないバイトが累算されるときには、次の以前のコードワードの対応するバイトに対して訂正がおこなわれるようにするものである。本発明の各種実施形態では、複数のコードワードを同時に操作することが可能になる。

Description

【発明の詳細な説明】 ＣＲＣ/ＥＤＣチェッカシステム 本願は、以下の同時に出願された特許出願、すなわち、Ｃhris Ｚookにより19 94 年 9 月 16 日に出願され、"ＭＵＬＴＩＰＵＲＰＯＳＥ ＥＲＲＯＲ ＣＯＲ ＲＥＣＴＩＯＮ ＣＡＬＣＵＬＡＴＩＯＮ ＣＩＲＣＵＩＴ"と題された米国特許 出願第 08/306,918 号、およびＣhris Ｚookにより1994 年 9 月 16 日に出願さ れ、"ＶＥＲＳＡＴＩＬＥ ＥＲＲＯＲ ＣＯＲＲＥＣＴＩＯＮ ＳＹＳＴＥＭ"と 題された米国特許出願第08/307,259号に関連している。本願では、上記特許出願 のすべてが参考として援用される。 背景 １．発明の分野 本発明は、ＣＲＣチェッキング機能を利用する誤り訂正システムを含むがそれ には限定されない、誤り訂正システムに関する。 ２．関連する技術および他の考察 ディスクドライブのような情報記憶装置は、一般に誤り訂正能力を有している 。この装置からトランスデュースされた情報は、典型的には、バイトのかたちで バッファに格納される。格納された情報は、通常、バイトから構成される複数の ブロックにフォーマットされる。例えばＣＤディスクドライブの場合、バッファ は、複数のセクタ（コンピュータデータを処理するとき）または複数のフレーム （ディジタルオーディオデータを処理するとき）を含んでいる。ここでは、これ らを包括的に「ブロック」と称する。 誤り訂正能力によれば、それぞれのセクタは、典型的には、複数のＣＲＣまた はＥＤＣチェックバイトを有する。図２は、それぞれが26バイトから構成される 86のカラムにグループ分けされたブロックを図示している。ブロック内では、バ イトから構成されるカラムはそれぞれ、１個のカラムコードワードを備えており 、各カラムの最後の２バイトは、カラムコードワードのＥＣＣ部分を構成して おり、各カラムの残りの部分（つまり、最初の24バイト）は、カラムコードワー ドのデータ部分を構成している。例えば、バイト0000、0086、0172、・・・1978は 、カラムコードワードＣＷ₀のデータ部を含んでおり、バイト0001、0087、0173 、・・・1979は、カラムコードワードＣＷ₁のデータ部を含んでいる。以下も同様で ある。図２に図示されているように、それぞれのブロックの最後の４つのデータ バイト（例えば、バイト2060、2061、2062、2063）は、誤り訂正情報を含んでい るので、ＥＤＣバイトまたはＣＲＣバイトとして知られている。あるフォーマッ トでは、ＣＲＣバイトは、必ずしもブロックのデータ部分の最後の数バイトでは ない。例えば、図２のブロックを完全には満たさないデータフォーマットでは、 ＣＲＣバイトをデータの最後に続けて配置し、その後に、それらのブロックが満 たされるまでゼロバイトで埋め込まれたＣＲＣバイトを置くこともできる。 誤り訂正多項式の演算以外では、ＣＲＣまたはＥＤＣチェックバイトが、付加 的なチェック手段を提供する。一般に、ＣＲＣバイトは、データバイト（または 、場合によってはビット）をバイト値（またはビット値）で表されたデータの多 項式Ｄ(x)の係数として扱い、Ｄ(x)x^n-kmodＧ(x)を計算することによって発生さ れる。ここで、ｋはデータシンボルの個数であり、n-kはＣＲＣシンボルの個数 であり、Ｇ(x)はＣＲＣ発生器多項式である。コンパクトディスク（ＣＤ）ドラ イブの場合、ＣＲＣ発生器は、ビット値で表される。 従来より、ＣＲＣまたはＥＤＣバイトを用いるバッファのチェックは、そのバ ッファが訂正された後におこなわれている。具体的には、誤り訂正フェーズのあ いだ、バッファのバイトは、コードワードとしてアクセスされ、誤り訂正多項式 を用いて処理される。誤り多項式によるコードワードに対する処理の結果、誤り を含んでいるコードワードのバイトを指定する誤りポインタが、それらのポイン タにより位置の特定されたバイトの訂正に用いられる誤りパターンと共に発生さ れる。誤りポインタおよび誤りパターンによる発生の後、バッファにおけるバイ トが、ポインタにより指定されたバイトを訂正する目的でアクセスされる。 ポインタにより指定されたバイトの訂正に引き続いて、特にＣＲＣまたはＥＤ Ｃチェックを目的として、バッファが再びアクセスされる。ＣＲＣまたはＥＤＣ チェ ックのあいだ、バッファにおけるすべてのバイトから構成される多項式（ＣＲＣ バイトを含む）は、ＣＲＣ発生器多項式により除算される。もしその剰余がゼロ であれば、ブロックが正確に訂正されたことが確認される。 ＣＲＣまたはＥＤＣ機能は、データの完全性を確認するに当たっての付加的な レベルを提供てきるという利点を有してはいるものの、ＣＲＣ／ＥＤＣチェック のためにはバッファに対して特別なアクセスが必要になるので、全体的な動作速 度が低下してしまう。 要旨 ＥＤＣ／ＣＲＣチェッカは、訂正パスのあいだに１ブロックのデータが訂正さ れているあいだに、ＥＤＣ／ＣＲＣチェックをおこなうことによって、ブロック 訂正に引き続いてＥＤＣ／ＣＲＣを目的としてバッファにアクセスすることを不 要にする。訂正パスのあいだ、ＥＤＣ／ＣＲＣの和が累算される。この和は、そ のブロックのパスが完了した後、もしそのブロックにおけるＥＤＣ／ＣＲＣバイ トによりそのブロックが訂正されたことが確認されれば、ゼロになる。ブロック の一回の訂正パスのあいだに、訂正されていない、最も最近のコードワードのバ イトは、累算された和に加算される。最も最近のコードワードのバイトとバイト 同期関係にある以前のコードワードのバイトは、（必要であれば）訂正され、か つ（訂正がおこなわれる時には）以前のコードワードのバイトを訂正するのに用 いられた誤りパターンを含む誤りパターン係数もまた、累算された和に加算され る。ここで説明される実施形態では、ブロックは、複数のコードワードカラムを 有するものとして概念づけられ、バイト同期関係は、訂正されていないバイトが 累算されるときには、次の以前のコードワードの対応するバイトに対して訂正が おこなわれるようにするものである。 よって、本発明のＥＤＣ／ＣＲＣチェッカは、最も最近のコードワードＣＷ_n に対するシンドローム発生に用いられているブロックバイトに対するＣＲＣチェ ックをおこなうのと同時に、以前のコードワード（例えば、ＣＷ_n-1）の対応し て位置づけられたバイトに対しても訂正がおこなわれうるようにする。以前のコ ードワードの対応するバイトに対して訂正がおこなわれているとき、以前のコー ドワ ードの対応するバイトに対する誤りパターン係数もまた、累算された和に加算さ れる。なぜなら、対応するそのようなバイトは、訂正されていない状態で、それ 以前に和に加算されていたからである。実際には、誤りパターン係数は、誤りパ ターンの定数の倍数である。その定数の倍数の値は、実現されるバイト位置同期 関係に依存している。 本発明のＥＤＣ／ＣＲＣチェッカは、バッファに対して別個にアクセスするこ とを必要とせずにＥＤＣ／ＣＲＣチェックをおこなうことができるという利点を 有する。さらに、本発明は、ブロックを完全には満たさず、ＣＲＣバイトをデー タの最後に続けて配置し、その後に、それらのブロックが満たされるまでゼロバ イトで埋め込まれたＣＲＣバイトを置くことができるデータフォーマットともコ ンパチブルである。 図面の簡単な説明 本発明の上記目的、特徴および利点、ならびにその他の目的、特徴および利点 は、添付の図面に図示されている好ましい実施形態の、以下に述べるより詳細な 説明から明らかになるであろう。なお、全図面を通して、参照番号は同一の部分 を指すものとする。また、図面は必ずしも実際の縮尺に則ったものではなく、本 発明の原理を図示するさいに強調されているところもある。 図１は、本発明によるＥＤＣ／ＣＲＣチェッカを用いる誤り訂正システムの一 例の模式的ブロック図である。 図２は、バッファに格納されているデータの１セクタを図示しており、セクタ は、複数のロウおよびカラムをなして格納されるものと概念づけられている。 図３Ａは、本発明のある実施形態によるＥＤＣ／ＣＲＣチェッカ回路を示す模 式図である。 図３Ｂは、データバイトと誤りパターンとが本質的に同時アクセス可能である 、本発明のある実施形態によるＥＤＣ／ＣＲＣチェッカ回路を示す模式図である 。 図４Ａは、２つのコードワード（例えば２つのカラム）が一度に処理されうる 、本発明のある実施形態によるＥＤＣ／ＣＲＣチェッカ回路を示す模式図である 。 図４Ｂは、図４Ａの回路と等価である、ＥＤＣ／ＣＲＣチェッカ回路を示す模 式図 である。 図４Ｃは、２つのコードワード（例えば２つのカラム）が一度に処理可能であ り、かつ、データバイトおよび誤りパターンが本質的に同時アクセス可能である 、本発明のある実施形態によるＥＤＣ／ＣＲＣチェッカ回路を示す模式図である 。 図５は、２つのインタリーブされたブロックに分割されるものと概念づけられ たバッファを図示しており、それぞれのブロックは、複数のロウおよびカラムを なして組織されるものと概念づけられたバイトを有している。 図６は、ＥＤＣ／ＣＲＣチェッキング演算に伴う各ステップを図示するフロー チャートである。 図７は、図４Ａのチェッカのチップ指向のインプリメンテーションを示す模式 的ブロック図である。 図面の詳細な説明 図１は、システムコントローラ10を介してバッファ（破線15によって概略的に 示される）と通信する誤り訂正システムを示す。バッファは、その中に例えば図 ２に示すような複数のブロックを格納している。図１の誤り訂正システムは、さ らに発生器、つまり発生部20（例えば、シンドローム発生用）、計算器、つまり 計算部30（例えば、誤りパターン計算用）、訂正器、つまり訂正部60、およびＥ ＤＣチェッカ部70を含む。図１の誤り訂正システムの動作の全体は、コントロー ラ10により、例えばバスＣＢＵＳ上に運ばれる制御信号およびその他の信号を用 いることによって管理される。 図１に示されているように、ＥＤＣ／ＣＲＣチェッカ70は、訂正器60からのラ インＥＲＲ上の誤りパターン、およびラインＧＤＡＴ上のバッファデータを受け 取るように接続されている。システムコントローラ10は、コントロールバスＣＢ ＵＳを用いて、ＥＤＣ／ＣＲＣチェッカ70の動作全般を、訂正器60およびバッフ ァへのアクセスと共に、管理する。システムコントローラの動作および訂正の一 例は、ここで参考として援用される1994 年 9 月 16 日に出願された Ｃhris Ｚ ookによる「多目的誤り訂正システム(ＶＥＲＳＡＴＩＬＥ ＥＲＲＯＲ ＣＯＲＲ ＥＣＴＩＯＮ ＳＹＳＴＥＭ)」と題された米国特許出願第 08/307,259 号を参照 すれば理解される コンパクトディスク（ＣＤ）のディスクドライブのコンテクストで理解される。 しかし、本発明の原理はそのような例に限定されるものではなく、ＥＤＣ／ＣＲ Ｃチェッキング全般に広く適用可能であることは理解されたい。 以下にさらに詳しく説明するように、システムコントローラ10の管理の下に、 ＥＤＣ／ＣＲＣチェッカ70は、訂正器60と協調して、バイトが訂正されるバッフ ァの同じパスのあいだに訂正の正確さのＥＤＣ／ＣＲＣベリファイをおこなうよ うに効果的に動作する。 図３Ａは、データ（図２のバッファに格納されている）を操作し、本発明の原 理を説明するのに適したＥＤＣ／ＣＲＣチェッカの機能模式図である。図３Ａの チェッカ70は、累算レジスタ702のかたちのメモリを特徴としている。累算レジ スタ702は、レジスタフィードスイッチすなわちＭＵＸ 704によりフィードされ る。このＭＵＸ 704は、最終的にはシステムコントローラ10に接続される選択ラ イン705により動作される。レジスタフィードＭＵＸ 704は、３つの選択可能な 信号源に接続されている。すなわち、加算器706、ロウ乗算器708およびカラム乗 算器710である。ロウ乗算器708は、加算器712に接続されている。レジスタ702の 内容−残余の、または累算された和−は、レジスタ出力ライン714上で利用可能 である。レジスタ出力ライン714は、カラム乗算器710と、加算器712と、加算器7 06とに接続されている。 バッファからの訂正されていないデータバイトは、ラインＧＤＡＴ上でＡＮＤ ゲート715の第１端子に与えられる。ＡＮＤゲート715の第２端子は、システムコ ントローラ10から信号ＮＯＴ ＬＡＳＴ ＣＯＬを受け取る。チェッカ70が和を取 る目的でバッファから依然としてデータバイトを得ているあいだに、信号ＮＯＴ ＡＳＴ ＣＯＬは、バッファからの訂正されていないデータバイトを、ＡＮＤゲ ート715を通して効率よくゲートし、加算器712に与える。 加算器712は、レジスタ702に累算された和（ライン714上で利用可能である） と、バッファからの訂正されていないデータバイト（ラインＧＤＡＴ上で与えら れる）とを加算する。加算器712によりつくられた和は、ロウ乗算器708に入力と して与えられる。前述したように、ロウ乗算器708からの出力は、ＭＵＸ 704に 与えられる選択可能な入力の１つである。 訂正器60からの誤りパターンを運ぶラインＥＲＲは、乗算器716に接続されて いる。現在のコードワードと以前のコードワードとの間のバイト同期オフセット （例えば、カラムオフセット）に対応可能とするために、乗算器716は、定数x⁸m odＧ(x)により乗算して、誤りパターン係数を発生する。乗算器716により発生さ れた積（誤りパターン係数）は、加算器706の第１入力端子に与えられる。加算 器706の第２入力端子は、上述したように、レジスタ出力ライン714に接続されて いる。 図３Ａにおいて、ロウ乗算器708のための乗算定数は、x^8・86modＧ(x)である。 この定数は、次のロウへと進めるはたらきをする(すなわち、バッファにおいて8 6バイトだけ進める。ここで、１バイトは８ビットである)。カラム乗算器710の ための乗算定数は、x^{-(86・24-1)・8}modＧ(x)である。この定数は、あるカラムコ ードワードのデータ部分の最後のバイトから、次のカラムコードワードの先頭へ と移動するはたらきをする(すなわち、バッファにおいて2063バイトだけ後退す る。ここで、１バイトは、８ビットである)。 図３Ａに図示されている例では、訂正されていないデータ（ラインＧＤＡＴ上 にある）の１バイトと、ブロックのバイト位置同期の取られた別のバイトとは、 ただちに共に利用可能となるのではなく、チェッカに対してシーケンシャルに（ まず誤りパターンが、次いでデータバイトが）与えられるという前提を含む。一 方、図３Ｂの実施形態は、訂正されていないデータバイトと、誤りパターンとが 同時にアクセス可能である、チェッカ70'を示している。図３Ｂの実施形態では 、加算器706は除かれており、ＭＵＸ 704は２入力スイッチになっており、乗算 器716の出力は、第３の入力として加算器712に与えられる。 図４Ａは、パフォーマンス上の理由からある種の実施形態では望ましいことも あるものである、２つのコードワード（例えば、一度に２つのカラム）を処理す るように構成されたチェッカ70"を示している。図４Ａの実施形態は、例えば、 バッファが２つのインタリーブされたブロックを含むものとして概念づけられて おり、バッファの２つのコードワードが一度に操作される時に利用可能である。 例えば、図５は、２つのインタリーブされたブロック（偶数ブロックおよび奇数 ブロック）を示している。ここで、１ブロックのそれぞれのカラムにおけるバイ トは、カラムコードワードを構成している。すなわち、0000、0043、0086、・・・ 、0989として表現されたバイトは、偶数ブロックの第１のカラムコードワードの データ部分を形成しており、バイト0001、0044、0087、・・・0990は、偶数ブロッ クの第２のカラムコードワードのデータ部分を形成している。以下も、偶数ブロ ックおよび奇数ブロックのそれぞれにおける合計43のカラムコードワードについ て同様である。また、図５に示すように、各ブロックの最後の２バイト（具体的 には1030、1031と表現されたバイト）は、ＥＤＣまたはＣＲＣバイトである。 図４Ａのチェッカ70"は、累算レジスタ702"を備えている。レジスタ702"への フィードは、選択信号705"により支配される、スイッチつまりＭＵＸ 704"によ り制御される。チェッカ70"は、４つの入力信号を受け取る。すなわち、より低 いオーダーのデータ入力信号ＤＡＴ_Lと、より低いオーダーの誤りパターン入力 信号ＥＲＲ_Lと、より高いオーダーのデータ入力信号ＤＡＴ_Hと、より高いオーダ ーの誤りパターン入力信号ＥＲＲ_Hとの４つである。図５のインタリーブされた ブロックのシナリオを参照すれば、例えば、より低いオーダーの入力は、偶数ブ ロックに対応し、より高いオーダーの入力は奇数ブロックに対応していてもよい 。すなわち、ＤＡＴ_Lは、偶数ブロックからのカラムコードワードＣＷeven_Nの選 択されたバイトに対する訂正されていないデータであり、ＥＲＲ_Lは、カラムコ ードワードＣＷeven_Nの選択されたバイトと所定のバイト同期関係にある（カラ ムコードワードＣＷeven_N-1における）バイトに対する誤りパターンであっても よい。ＤＡＴ_Hは、奇数ブロックからのカラムコードワードＣＷodd_Nの選択され たバイトに対する訂正されていないデータであり、ＥＲＲ_Hは、カラムコードワ ードＣＷodd_Nの選択されたバイトと同期関係にある（カラムコードワードＣＷod d_N-1における）バイトに対する誤りパターンであってもよい。 チェッカ70"は、さらに５つの乗算器を備えている。すなわち、カラム乗算器7 10"と、ロウ乗算器708"と、それぞれラインＤＡＴ_H、ＥＲＲ_LおよびＥＲＲ_H上に 設けられた乗算器750、760および770の５つである。乗算器708、710、750、760 および770に対する乗算定数は、表Ｉにより与えられる。 乗算器750、760、770の出力は、スイッチつまりＭＵＸ 780のそれぞれの入力 端子に接続されている。ＭＵＸ 780の出力端子は、加算器 790の第１入力端子に 接続されている。加算器790の第２入力端子は、レジスタ702"の出力ライン714" に接続されている。加算器790の出力端子は、ＭＵＸ 704"の第１入力端子に接続 されており、ＭＵＸ 704"の他の２つの入力端子は、乗算器708"および710"の出 力端子に接続されている。図３Ａの実施形態の場合と同様に、ラインＤＡＴ_Lは 、信号ＮＯＴ ＬＡＳＴ ＣＯＬがオンである限りそれを通してデータバイトをゲ ートするためにその上に接続されたＡＮＤゲート715"を有している。 図４Ｂは、図４Ａの回路70"と本質的には等価であるチェッカ回路70"'を示し ている。図４Ｂのチェッカ回路70"'は、いくつかの点で図４Ａの回路70"と異な る。第１の相違は、16ビット値に変換される信号ＤＡＴ_L16、ＤＡＴ_H16、ＥＲＲ_H16 およびＥＲＲ_L16のフォーマットを伴う。具体的には、ＥＲＲ_H16は、ＥＲＲ_H と、８つのゼロビットとを連結することにより得られる16ビット値である。ここ で、ＥＲＲ_Hは、高いオーダーの位置にある。ＥＲＲ_L16は、ＥＲＲ_Lと、８つの ゼロビットとを連結することにより得られる16ビット値である。ここで、ＥＲＲ_L は、低いオーダーの位置にある。ＤＡＴ_H16およびＤＡＴ_L16は、それぞれＥＲ Ｒ_H16およびＥＲＲ_L16と同様に形成される。連結以前の誤りおよびデータバイト は、それぞれ８ビット長であり、ＣＲＣ多項式は16ビット長であるので、ＥＲＲ の乗算、すなわちＤＡＴにＸ⁸を乗ずることは、単に下位８ビットを上位８ビッ トにシフトすることであり、また（以下に述べるように）図４Ｂの乗算器765の 使用を、図４Ａの乗算器750、 760、770よりもむしろ容易にする。 図４Ｂと図４Ａとの間の第２の相違は、ラインＥＲＲ_H16およびＥＲＲ_l16がＭ ＵＸ767をフィードしており、ＭＵＸ767は乗算器765をフィードしている点であ る。乗算器765の乗算定数は、x¹⁶modＧ(x)である。乗算器765およびＤＡＴ_H16は ともに、ＭＵＸ780"'に接続されている。ＭＵＸ780"'の出力は、加算器790"'に 接続されている。 図７は、２つの16ビット多項式を用いて２つのチェックをおこなうための２つ のＣＲＣ／ＥＤＣ回路を設けている、図４Ｂのチップ指向のインプリメンテーシ ョンを示している。図７のチェッカ70"'は、一対の前置乗算器チップ730(0)、73 0(1)と、一対の累算レジスタ732(0)、732(1)と、ＥＤＣ比較器734とを備えてい る。チェッカ70"'では、両回路共に、(それぞれ前置乗算器730(0)、730(1)を介 して)、同一のデータの後続する同一の誤りパターンを受け取る。 図７において、前置乗算器730(0)は多項式x¹⁶+x¹⁵+x²+1を用い、前置乗算器73 0(1)は、多項式x¹⁶+x²+x+1を用いる。例えば、図４Ｂに示されているそれぞれの 乗算器について、図７のそれぞれの前置乗算器730は、それ自身のＸＯＲ論理ゲ ートのセットを有している。前置乗算器730の乗算器用の論理ゲートセットの構 成は、特定の乗算器への入力信号を、その乗算器固有の16×16の２進行列で乗算 し（例えば、複数のロウおよびカラムをペアにし、その内積をとり）、16ビット の出力信号を得ることと等価である。信号ＤＡＴ_L16、ＤＡＴ_H16、ＥＲＲ_H16お よびＥＲＲ_L16について既に述べたように、乗算以前に、入力信号（例えば、Ｄ ＡＴ_Lのような８ビット入力ベクトル）は、その一端または他端が８つのゼロで 埋め込まれて、その乗算用の16ビットベクトルをつくる(例えば、ベクトルＤＡ Ｔ_L16を生じる)。 それぞれの乗算器の出力ベクトルのビットは、入力ベクトルのビットの線形結 合であるので、行列乗算、すなわち[0]=[I] [T]^Kにより得られる。ここで、[I] および[0]は、その右側にビット０をもつ入力および出力ロウベクトルであり、[ T]は、xmodＧ(x)で乗算するための行列である。 前置乗算器730(0)については、乗算器765の乗算を説明する16×16の２進行列 は表２に与えられている。ロウ乗算器708"用の行列は、表３に与えられてい る。カラム乗算器710"用の行列は、表４に与えられている。前置乗算器730(1)に ついては、乗算器765の乗算を説明する16×16の２進行列は表５に与えられてい る。ロウ乗算器708"用の行列は、表６に与えられている。カラム乗算器710"用の 行列は、表７に与えられている。 上記乗算の例としては、 ＥＲＲ_H・Ｘ²⁴modＧ₁(x)=ＥＲＲ_H・Ｘ⁸・Ｘ¹⁶modＧ₁(x)=ＥＲＲ_H16・Ｘ¹⁶modＧ₁(x ) [I]=[Ｅ₀Ｅ₁Ｅ₂...Ｅ₇0000000] 出力のＢＩＴ０は、Ｅ₀+Ｅ₂+Ｅ₃+Ｅ₄+Ｅ₅+Ｅ₆+Ｅ₇である。 図３Ａと同様に、図４Ａおよび図４Ｂに図示の例においても、訂正されていな いデータ（ラインＧＤＡＴ上）の２バイトと、そのブロックの別のバイト位置同 期のとられたバイト用の２つの誤りパターンとは、ただちに共に利用可能となる のではなく、チェッカ70"にシーケンシャルに（まず誤りパターンが、次いでデ ータバイトが）与えられることを前提として含む。図４Ｃの実施形態が、図４Ａ の実施形態と異なるのは、図４Ｃのチェッカ70"'が、本質的に同時に利用可能と なるデータバイトおよび誤りパターンのペアを処理する点である。図４Ｃの実施 形態のロウおよびカラム乗算器の定数は、図４Ａの実施形態の場合と同じである 。 図４Ｃの実施形態では、チェッカ70""は、カラム乗算器710""またはロウ乗算 器708""により（２入力ＭＵＸ 705""を介して）フィードされるレジスタ702""を 備えている。レジスタ出力ライン714""は、加算器790""の第１入力端子に接続さ れている。加算器790""のその他４つの入力端子は、それぞれラインＤＡＴ_L、Ｄ ＡＴ_H、ＥＲＲ_LおよびＥＲＲ_Hに接続されている。ラインＤＡＴ_H、ＥＲＲ_Lおよ びＥＲＲ_Hは、それぞれ、その上に接続された乗算器750""、760""および770""を 有している。加算器790""の出力端子は、ロウ乗算器708""の入力端子に与えられ る。ＡＮＤゲート715""は、ラインＤＡＴ_LおよびＤＡＴ_H上に設けられている。 動作 例えば図２を参照して既に述べたように、本発明のセクタは、86のカラムから 構成されるブロックを含んでいる。ここで、そのブロックのそれぞれのカラムに おけるバイトが１コードワードを構成している。ＣＲＣ／ＥＤＣチェックを目的 として、コードワードのデータ部分のみが利用される。したがって、以下で用い られる「コードワード」は、そうではないと特に断らない限り、コードワードの データ部分のみを意味するものとする(つまり、コードワードのＥＣＣ部分を除 くものとする)。例えば、0000、0086、0172、・・・1978表現されたバイトは、 第１のカラムコードワードのデータ部を形成しており、バイト0001、0087、0173 、・・・1979は、第２のコードワードのデータ部を形成している。以下も、ブロッ クの合計86のコードワードのすべてについて同様である。また、図１に示されて いるように、それぞれのブロックの最後の４つのデータバイト（具体的には、例 えばバイト2060、2061、2062、2063と表されたバイト）は、ＥＤＣバイトまたは ＣＲＣバイトである。 システムコントローラによるＥＤＣ／ＣＲＣチェッカ70の管理に伴う各ステッ プは、図７に示されている。ステップＳ２において、カウンタ値ＲＯＷＣＯＵＮ ＴおよびＣＯＬＣＯＵＮＴは、累算レジスタ702における値（ＲＥＧＳＵＭ）と 共に、ゼロに初期化される。また、最後のカラムフラグ（ＬＡＳＴＣＯＬ）は、 ＦＡＬＳＥに初期化される。初期化ステップＳ２に続いて、偶数番のステップＳ ４〜Ｓ22を含むループが実行される。 このループのはじめ（ステップＳ４）に、ＲＯＷＣＯＵＮＴおよびＣＯＬＣＯ ＵＮＴの現在の値により参照されるバイトと同期のとられたバイト関係にある、 バッファ内のバイトについて訂正がなされているかどうかが判定される。ここで 説明されている実施形態では、バイト同期関係とは、訂正が以前のコードワード に対して（つまり、以前のコードワード、すなわち[ＣＯＬＣＯＵＮＴ-1，ＲＯ ＷＣＯＵＮＴ]のバイトＲＯＷＣＯＵＮＴについて）おこなわれるようにするも のであるので、バッファ内の第１のカラムコードワードに対するループを実行す るときには、何の訂正も実行されない。 具体的には、ここで説明されている実施形態では、バイト位置同期とは、ステ ップＳ２において、ブロックのバイト（ＣＯＬＣＯＵＮＴ-1，ＲＯＷＣＯＵＮＴ ）に対する誤りパターンが存在するかどうかが判定されるようにするものである 。前述したように、ステップ1608の判定は、ブロックの第１のコードワードを処 理する時には、否定になる。しかし、後続するカラムコードワードの処理のあい だの判定は、以下を代表として説明される。図１のバイト0001がＲＯＷＣＯＵＮ ＴおよびＣＯＬＣＯＵＮＴの現在の値によりアクセスされるとき、誤りパターン の発生に関する判定が、バイト0000についてなされる。図１のバイト0087がＲＯ ＷＣＯＵＮＴおよびＣＯＬＣＯＵＮＴの現在の値により示されるとき、誤りパタ ーンの発生に関 する判定は、バイト0086についてなされる。以下も同様である。なお、本発明は このような特定のバイト同期関係に限定されないことは理解されたい。なぜなら 、その他のオフセット（例えば、さまざまに異なる度合いのカラムオフセット） が、システム全体のその他の考察に基づいて適当である範囲内で用いられうるか らである。 第１のコードワード以外のコードワードに対応するループの実行については、 以前のコードワードの対応するバイトが訂正を必要とすることがある。訂正が必 要とされるとき、ステップＳ６において、同期のとられたバイト（例えば、以前 のコードワードの同期のとられたバイト）に対する誤りパターン係数が、レジス タ702に加算される。この誤りパターン係数は、誤りパターン（Ｅ(x)、信号ＥＲ Ｒにより運ばれる）を、乗算器716を用いて乗算器定数（x⁸modＧ(x)）で乗算す ることにより得られる。換言すれば、ステップＳ６では、レジスタ702は、ＲＥ ＧＳＵＭ+Ｅ(x)x⁸modＧ(x)を得る。同期のとられたバイトが、そのブロックの最 も最近にアクセスされたバイトから１カラムだけ（つまり、１バイトすなわち８ ビットだけ）オフセットされるという事実が、同期のとられたバイトに対する誤 りパターンはx⁸modＧ(x)により乗算されねばならない理由となる。この同じルー プを実行するあいだ、ステップＳ６で利用された誤りパターンは、また、バッフ ァ内のブロックにおけるデータバイトを訂正するためにも用いられる。 ステップＳ８では、バッファからの訂正されていないデータバイトがすべて、 既にレジスタ702に加算されたかどうか（つまり、ＣＯＬＣＯＵＮＴがバッファ におけるコードワードの個数を超えたかどうか）が判定される。この判定は、フ ラグＬＡＳＴＣＯＬの値をチェックすることによりなされる。もしバッファから の訂正されていないデータバイトがすべて加算されていないのなら、実行は、ス テップＳ10に続く。そうでなければ、実行は、ステップＳ12に続く。 ステップＳ10では、チェッカ70は、ブロックからの次の訂正されていないデー タバイトを得る。具体的には、ステップＳ10において、ブロックからの次の訂正 されていないデータバイトは、データバイト（ＣＯＬＣＯＵＮＴ、ＲＯＷＣＯＵ ＮＴ）となる。このループを最初に実行するとき、得られる最初のバイトは、バ イト0000となる。このループを引き続いて連続的に繰り返し実行する ために、ステップＳ10では、ブロックのさらなるバイトがＥＣＣカラムコードワ ードの順番でアクセスされる(例えば、バイト0086、0172、・・・、1978、0001、00 87、・・・1979、0002、・・・2063)。ステップＳ10では、ステップＳ10で得られたバ イトは、（ラインＧＤＡＴ上で）で与えられ、レジスタ702に累算された和（Ｒ ＥＧＳＵＭ）に（加算器712により）加算される。加算器712の和は、今度はロウ 乗算器708のロウ進み乗算定数x^86・8modＧ(x)およびレジスタ702に格納されてい る積により乗算される。よって、ステップＳ10では、次の訂正されていないデー タバイト係数Ｄ(x)x^86・6modＧ(x)が、レジスタ702内の値（ＲＥＧＳＵＭ）に加 算される。 ステップＳ12は、ブロックからの訂正されていないデータバイトがすべてレジ スタ702に加算されており（例えば、ステップ710と同様に）、最後のコードワー ドに対する誤りパターン係数の処理のみがおこなわれている時に実行される。ス テップＳ12では、レジスタ702の内容は、ロウ乗算器708の乗算定数x^86・6modＧ(x )により乗算される。 ステップＳ10またはＳ12を実行した後、ステップＳ14では、ＲＯＷＣＯＵＮＴ の値は１だけインクリメントされる。もし、ステップＳ16で判定されるときに、 ＲＯＷＣＯＵＮＴのインクリメントされた値が24に等しくないのなら、ステップ Ｓ４に始まるループが、現在のコードワードの次のバイトについて実行される。 しかし、もしＲＯＷＣＯＵＮＴのインクリメントされた値が24に等しいのなら、 ステップＳ18が実行される。ＲＯＷＣＯＵＮＴの値は、24を超えることを許され ない。なぜなら、それぞれのカラムコードワードには24のデータバイトしかない からである。 ステップＳ18では、新しいカラムへの進みを考慮して、カラム乗算器710は、 レジスタ702の内容を、カラム調整定数x^{-(86・24-1)・8}modＧ(x)で乗算するはたら きをする。 ステップＳ18の後、ステップＳ20では、ＲＯＷＣＯＵＮＴはゼロにリセットさ れ、ＣＯＬＣＯＵＮＴは１だけインクリメントされる。ステップＳ22は、フラグ ＬＡＳＴＣＯＬがセットされているかどうかをチェックする。もしフラグＬＡＳ ＴＣＯＬがセットされていないのなら、（ステップＳ24で）ＣＯＬＣＯＵＮＴの 値が最後のカ ラムの数を超えた（例えば、ＣＯＬＣＯＵＮＴが86である）かどうかチェックさ れる。もしブロックの最後のカラム（例えば、最後のコードワード）が超えられ ていないのなら、実行は、ステップＳ２に戻り、ブロックの新しいコードワード の最初のバイトについて継続する。そうでなければ、フラグＬＡＳＴＣＯＬは、 ステップＳ２に戻ってブロックの最後のコードワードに対する何らかの誤りパタ ーンを処理する以前に、ステップＳ26でＴＲＵＥにセットされる。 ブロックの最後のコードワードに対する誤りパターン係数（がもしあれば、そ れ）がレジスタ702に加算された後、フラグＬＡＳＴＣＯＬを（ステップＳ22で ）ＴＲＵＥにセットすることによって、実行は、ステップＳ28にジャンプする。 ステップＳ28では、レジスタ702における値（つまり、値ＲＥＧＳＵＭ）がゼロ であるかどうかが判定される。ループがすべて終了した後のレジスタ702におけ る値は、バッファにおける全バイト（ＣＲＣバイトを含む）から構成される多項 式をＣＲＣ発生器の多項式で除算したときの剰余である。レジスタ702の値がゼ ロであることは、訂正器60によりおこなわれた誤り訂正が正確であることを確証 する。 よって、レジスタ702にブロックの誤ったままになる可能性のある（つまり、 訂正されていない）データバイトを加算することは、レジスタ702にブロックの 位置的に同期のとられたバイトに対する誤りパターン係数（があれば、それ）を 加算することと、時間的に合わせられていることがわかる。 図３Ｂのチェッカ70'、図４Ａのチェッカ70"、図４Ｂのチェッカ70"'および図 ４Ｃのチェッカ70""の動作は、図７に伴う各ステップについて既に述べた議論を 参照すれば理解される。図４Ａ、図４Ｂおよび図４Ｃでは、２つのコードワード が一度に操作される。図７の実施形態では、図６の各ステップが、２つの構成要 素であるチェッカ回路70"'のそれぞれについて実行される。ここで、各構成要素 をなすチェッカ回路は、同一のデータを受け取るが、２つの16ビット多項式の互 いに異なる１つずつを用いて動作する。最後に、両チェッカ回路は、ブロックを 訂正可能とするためには、結果的にゼロとならなければならない。 よって、以上の説明から明らかなように、本発明によれば、ＣＲＣ／ＥＤＣチ ェックは、データバイトの訂正が実行されるバッファを通る同一のパスの間にお こな われる。本発明の方法は、バッファにおけるバイトにシーケンシャルにアクセス することと、バッファの第１の選択されたバイトを累算された和に（例えば、ス テップＳ10で）加算することとを伴う。ここで、アクセスされるバイトは、もし その訂正が必要とされるのなら、まだ訂正を受けてはいない。このパスが第１の 選択されたバイトを指しているあいだに、そのブロックの第２のバイトが、第２ のバイトに対する誤りパターンを用いて訂正される。ここで、第１の選択された バイトと第２の選択されたバイトとの間には、バイト位置同期関係がなりたち、 また、第２のバイトは、訂正されていない状態で、累算された和に既に加算され ている。第２のバイトに対する誤りパターン係数は、累算された和に（例えば、 ステップＳ６で）加算される。それに引き続いて、ただし同一のパスの間に、第 １のバイトに対する誤りパターン係数が、累算された和に加算される。 以上に本発明を、その好ましい実施形態に言及しながら具体的に示し、説明し てきたが、その形式および詳細については、本発明の精神および範囲から離れる ことなく、さまざまな改変がその中になされうることは、当業者には理解できる であろう。例えば、望みとあれば、２つよりも多くのインタリーブに適応させる ことも可能である。 独占所有権、すなわち特権を請求する本発明の実施形態は、以下のように規定 される。

───────────────────────────────────────────────────── 【要約の続き】 には、次の以前のコードワードの対応するバイトに対し て訂正がおこなわれるようにするものである。本発明の 各種実施形態では、複数のコードワードを同時に操作す ることが可能になる。

Claims (1)

1. 【特許請求の範囲】 １．バッファ内にブロックの形態で格納された情報のバイトをチェックするシ ステムであって、 該バッファの訂正アクセスのあいだに、該ブロックの指定されたバイトを訂正 するのに用いられる誤りパターンを出力する訂正ユニットと、 該バッファの該訂正アクセスのあいだに、該ブロックの該バイトに対して処理 をおこない、該ブロックが訂正されたことを確認するためにＣＲＣ／ＥＤＣ情報 を用いるＣＲＣ／ＥＤＣチェッカと、 を備えているシステム。 ２．前記ＣＲＣ／ＥＤＣチェッカが前記ブロックの前記バイトの和をとるよう に動作する、請求項１に記載のシステム。 ３．前記訂正アクセスのあいだ、訂正されているバイトと、和のとられている バイトとの間にバイト位置同期関係がなりたつ、請求項２に記載のシステム。 ４．前記訂正パスのあいだ、前記チェッカが、前記ブロックからの選択された バイトを前記和に加算した後、該選択されたバイトが該選択されたバイトに対す る誤り値を用いて訂正されているあいだに、該和に対して、該選択されたバイト に対する該誤り値を含む係数をも加算する、請求項３に記載のシステム。 ５．前記訂正パスのあいだ、前記チェッカが、前記バッファからの選択された バイトを前記和に加算した後、該選択されたバイトが該選択されたバイトに対す る誤り値を用いて訂正されているあいだに、該和に対して、該選択されたバイト に対する該誤り値を含む係数をも加算する、請求項２に記載のシステム。 ６．バッファにおけるバイトの訂正ユニットによる訂正と同期して、該バッフ ァにおける情報のバイトをチェックするＣＲＣ／ＥＤＣチェッカシステムであっ て、 和が累算されるメモリ装置と、 該メモリに累算された該和に対して （1）該訂正ユニットによりまだ訂正されていない、該バッファの１バイト、 および （2）該和に既に加算された１バイトに対する誤りパターン を加算する加算器と、 を備えているチェッカ。 ７．前記和に加算された前記バイトが、前記誤りパターンが加算されている前 記バイトとバイト位置同期関係を有している、請求項６に記載のチェッカ。 ８．前記バッファが、複数のカラムおよびロウを含むものと概念づけられ、該 バッファに加算される前記バイトと、前記誤りパターンが加算される前記バイト とが同一のロウにある、請求項７に記載のチェッカ。 ９．前記誤りパターンが、前記累算された和に加算される誤りパターン係数に 含まれており、該誤りパターン係数が、さらに定数の倍数を含んでいる、請求項 ７に記載のチェッカ。 10．前記定数の倍数の値が、前記バイト位置同期関係に依存している、請求項 ９に記載のチェッカ。 11．バッファに格納されている情報のバイトをチェックする方法であって、 該バッファ内の第１の選択されたバイトにアクセスし、該第１の選択されたバ イトを累算された和に加算するステップと、 該バッファ内の第２の選択されたバイトに対する誤りパターンを用いて、該バ ッファにおける該第２の選択されたバイトを訂正するステップと、 該第２の選択されたバイトに対する誤りパターンを、該累算された和に加算す るステップと、 を含む方法。 12．前記第１の選択されたバイトと、前記第２の選択されたバイトとの間にバ イト位置同期関係がなりたつ、請求項11に記載の方法。 13．前記バッファが、複数のカラムおよびロウを含むものと概念づけられ、前 記第１の選択されたバイトと、前記第２の選択されたバイトとが、同一のロウに ある、請求項12に記載の方法。 14．前記誤りパターンが、前記累算された和に加算される誤りパターン係数に 含まれており、該誤りパターン係数が、さらに定数の倍数を含んでいる、請求項 12に記載の方法。 15．前記定数の倍数の値が、前記バイト位置同期関係に依存している、請求項 14に記載の方法。 16．バッファに格納されている情報のバイトをチェックする方法であって、 バッファ内のバイトにシーケンシャルにアクセスするステップと、 該バッファの第１の選択されたバイトを累算された和に加算するステップであ って、該アクセスされたバイトは、もしその訂正が必要とされるのなら、まだ訂 正を受けてはいない、ステップと、 該バッファ内の第２の選択されたバイトに対する誤りパターンを用いて、該第 ２の選択されたバイトを訂正するステップと、 該第２の選択されたバイトに対する該誤りパターンを、該累算された和に加算 するステップと、 を含む方法。 17．前記第１の選択されたバイトと、前記第２の選択されたバイトとの間にバ イト位置同期関係がなりたつ、請求項16に記載の方法。 18．前記バッファが、複数のカラムおよびロウを含むものと概念づけられ、該 バッファに加算される前記バイトと、前記誤りパターンが加算される前記バイト とが、同一のロウにある、請求項16に記載の方法。 19．前記誤りパターンが、前記累算された和に加算される誤りパターン係数に 含まれており、該誤りパターン係数が、さらに定数の倍数を含んでいる、請求項 16に記載の方法。 20．前記定数の倍数の値が、前記バイト位置同期関係に依存している、請求項 19に記載の方法。 21．バッファ内にブロックフォーマットで格納された情報のバイトを、該バッ ファの１パスのあいだにチェックする方法であって、 該１パスのあいだに第１の選択されたバイトを累算された和に加算するステッ プと、 該累算された和に対して、該第１の選択されたバイトに対する誤りパターンを 加算する、後続はするが該同一パス内のステップと、 を含む方法。 22．前記第１の選択されたバイトが前記累算された和に加算された後、前記誤 りパターンを用いて該第１の選択されたバイトを訂正するステップをさらに含ん でいる、請求項21に記載の方法。 23．前記誤りパターンが、前記累算された和に加算される誤りパターン係数に 含まれており、該誤りパターン係数が、さらに定数の倍数を含んでいる、請求項 22に記載の方法。 24．前記定数の倍数の値が、前記バイト位置同期関係に依存している、請求 項23に記載の方法。 25．バッファ内にブロックフォーマットで格納された情報のバイトをチェック する方法であって、 該バッファ内のバイトに該ブロックを通して一回のパスアクセスでシーケンシ ャルにアクセスするステップと、 アクセスされる時に、第１のバイトを累算された和に加算するステップであっ て、該第１のバイトは、もしその訂正が必要とされるのなら、まだ訂正を受けて はいない、ステップと、 該ブロックの第２のバイトに対する誤りパターンを用いて、該第２のバイトを 訂正するステップであって、該第２のバイトが、訂正されていないままで、該累 算された和に既に加算されている、ステップと、 該第２のバイトに対する該誤りパターンを、該累算された和に加算した後、該 同一のパスのあいだに、 第３のバイトを該累算された和に加算し、 該第１のバイトに対する誤りパターンを用いて該第１のバイトを訂正し、かつ 該第１のバイトに対する該誤りパターンを該累算された和に加算する、ステッ プと、 を含む方法。 26．前記第１の選択されたバイトと、前記第２の選択されたバイトとの間にバ イト位置同期関係がなりたつ、請求項25に記載の方法。 27．前記バッファが、複数のカラムおよびロウを含むものと概念づけられ、前 記第１の選択されたバイトと、前記第２の選択されたバイトとが、同一のロウに ある、請求項26に記載の方法。 28．前記誤りパターンが、前記累算された和に加算される誤りパターン係数に 含まれており、該誤りパターン係数が、さらに定数の倍数を含んでいる、請求 項26に記載の方法。 29．前記定数の倍数の値が、前記バイト位置同期関係に依存している、請求項 28に記載の方法。 30．前記ブロックを通した前記単一パスアクセスが完了したとき、もし該ブロ ックが正しく訂正されていれば、前記累算された和がゼロである、請求項25に記 載の方法。 31．バッファにおけるデータブロック内のバイトについてＥＤＣ／ＣＲＣチェ ックをおこなう方法であって、 該ブロック内の訂正されていないデータバイトにシーケンシャルにアクセスし 、それぞれの訂正されていないデータバイトを、該バイトにアクセスしたときに 、累算された和に加算するステップと、 訂正されていないデータバイトがアクセスされるときに、該ブロック内の位置 に関連するデータバイトが、利用可能な誤りパターンを有しているかどうかを判 定するステップであって、該位置に関連するデータバイトは、該累算された和に 既に加算されている、ステップと、もし利用可能な誤りパターンが存在するのな ら、 該位置に関連するデータバイトに対する該利用可能な誤りパターンを、該累算 された和に加算する、ステップと、 を含む方法。 32．前記ブロック内の訂正されていないデータバイトにシーケンシャルにアク セスする前記ステップのあいだに、前記位置に関連するデータバイトを訂正する ステップ をさらに含んでいる、請求項31に記載の方法。 33．前記位置に関連するデータバイトが、前記アクセスされた訂正されてい ないデータバイトとバイト同期の取られた関係にある、請求項31に記載の方法。 34．バッファにおけるデータブロック内のバイトについてＥＤＣ／ＣＲＣチェ ックをおこなう方法において、該バイトがコードワードに組織される、方法であ って、 該ブロック内の最も最近のコードワードに対する訂正されていないデータバイ トを累算された和にシーケンシャルに加算するステップと、 該最も最近のコードワードに対する訂正されていないデータバイトがアクセス されるときに、以前のコードワードにおける対応するデータバイトが、利用可能 な誤りパターンを有しているかどうかを判定するステップであって、該以前のコ ードワードの該対応するデータバイトは、該累算された和に既に加算されている 、ステップと、もし利用可能な誤りパターンが存在するのなら、 該以前のコードワードの該対応するデータバイトに対する該利用可能な誤りパ ターンを、該累算された和に加算するステップと、 を含む方法。 35．前記最も最近のコードワードの訂正されていないデータバイトが、前記累 算された和に加算されていくあいだに、前記以前のコードワードの前記対応する データバイトを訂正するステップ をさらに含んでいる、請求項34に記載の方法。 36．前記以前のコードワードの前記対応するデータバイトが、前記累算された 和に加算されていく前記最も最近のコードワードの前記データバイトとバイト同 期の取られた関係にある、請求項34に記載の方法。