(57)【要約】【課題】符号語の第２の組と交差する符号語の第１の組を含む多次元符号を訂正するための効率的な誤り訂正プロセッサを提供すること。【解決手段】誤り訂正は、符号語の第１および第２の組に対して繰り返しの通過を行うことにより実行される。個々の符号語は、符号語データの関数として計算される誤りシンドロームを用いて訂正される。好適な実施形態では、個々の符号語は、リード−ソロモン符号に従って符号化され、誤りシンドロームは、符号語多項式を生成多項式の因子で割るモジュロ除算として計算される。誤り訂正プロセッサのスループットを増加するために、シンドロームバッファを使用して、第１の組の符号語および第２の組の符号語の両方の誤りシンドロームを同時に生成することを容易にする。この態様で、第１の組の符号語に対する通過が終わると、第２の組の符号語の誤りシンドロームは、すぐに処理のために利用可能になる。【選択図】図３
2008148334.tif 000002
【特許請求の範囲】
【請求項１】
符号語の第２の組と交差する符号語の第１の組を含む複数次元符号の形で記憶媒体（６）上に記録されるデジタルデータの誤りを訂正するための誤り訂正プロセッサであって、図３に示される誤り訂正プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の分野）
本発明は、コンピュータ記憶装置のための誤り訂正システムに関し、具体的には、多次元符号の符号語（ｃｏｄｅｗａｒｄ）のシンドローム（ｓｙｎｄｒｏｍｅ）を生成する有用な方法および装置に関する。
【背景技術】
【０００２】
（発明の背景）
コンピュータシステムのための記憶装置では、同心または螺旋データトラックの形の回転磁気または光ディスクの表面に遷移の連続を書き込むために、デジタルデータストリームは、書き込み変換器の動作（例えば、コイルの電流またはレーザビームの強度）を変調する。記録されたデータの読み出しは、読み出し変換器をデータトラックの上で位置決めし、表面遷移を検知し、そして結果として得られるアナログ読み出し信号を、最初に記録されたデータを表す推定データシーケンスに復調することを必要とする。
【０００３】
データをディスク記憶装置に記録し、そしてディスク記憶装置から読み出すプロセスは、デジタルデータがケーブルまたは大気などの雑音を伴う通信媒体を介して送られる通信チャネルと同様である。通信システムおよび記録システムの両方における目標は、送られた／記録されたデータを信頼性高く且つ効率的に受け取る／読み出すことである。信頼性は、データがどれくらい正確に受け取られたかの尺度である。あるいは、記録／通信プロセスに固有の雑音により改悪された後にチャネル信号から検出される推定データシーケンスのビット誤り率である。効率は、ソースデータレートの尺度である。即ち、特定のビット誤り率を維持しながら、ソースデータを通信媒体を介していかに速く送ることができるか、である。コンピュータ記憶システムでは、効率は、所与のトラックの線形データ密度、および１インチあたりの同心トラック数（ｔｐｉ）の尺度である。
【０００４】
「雑音を伴うチャネルの符号化定理」として知られていることにおいて、シャノン（Ｓｈａｎｎｏｎ）は、通信システムの信頼性パラメータと効率パラメータとが関連していることを示した。雑音が通信チャネルにおいて引き起こす基本的な制限は、通信の信頼性の制限ではなく、通信速度の制限である。誤り確率をゼロに近づけながら、離散的無記憶チャネルを介してデータを送ることができる最大のレートは、チャネル容量と呼ばれる。チャネル容量は、結局、チャネルバンド幅と、信号対雑音比、即ち、ＳＮＲとの関数である。
【０００５】
通信システムにおいてＳＮＲを増加し、従って、システムの信頼性および効率を増加する周知の方法は、ソースデータを誤り訂正符号（ＥＣＣ）に従って符号化することである。誤り訂正符号は、雑音に対するシステムの免疫を増加させることにより、有効ＳＮＲを増加する。ブロック誤り訂正符号は通常、ディスク記憶システムにおいて使用され、特に、リード−ソロモンブロック符号が、その優れた誤り訂正特性、低い実現コストおよび低い複雑性のために、使用されている。
【０００６】
ブロック符号は、ソースデータストリームのｋ記号入力ブロックを、ｎ記号出力ブロックまたは符号語に符号化する。ここで、ｎ−ｋは、冗長記号の数であり、ｋ／ｎは、符号化率と呼ばれる。次いで、符号語が、通信媒体を介して送られ（通信媒体に記憶され）、そして受信器により復号化される。符号化プロセスは、出力符号語が、符号の最小距離ｄminと呼ばれるパラメータだけ互いに異なるように、入力ブロックに対して数学的演算を行う。符号語間の最小距離ｄminは、受け取られた符号語が誤って復号化される前にシステムが耐えることができる雑音量を決定する。
【０００７】
リード−ソロモン符号では、データストリームの各記号は、典型的には、有限体ＧＦ（２w）から選択される。ここで、ｗは、記号中のバイナリデータビット数である。ｋ記号入力ブロックの各記号は、データ多項式Ｄ（ｘ）の係数を表す。次いで、冗長符号（多項式Ｗ（ｘ）としても表される）が、入力データ多項式Ｄ（ｘ）を生成多項式Ｇ（ｘ）で割るモジュロ除算（ｍｏｄｕｌｏ  ｄｉｖｉｓｉｏｎ）として計算される。
【０００８】
【数１】
2008148334.tif 000003
【０００９】
ここで、ｍは、生成多項式の次数であり、冗長記号の数に等しい。次いで、冗長多項式Ｗ（ｘ）がデータ多項式Ｄ（ｘ）に付加され、符号語多項式Ｃ（ｘ）を生成する。
【００１０】
【数２】
2008148334.tif 000004
【００１１】
上記演算を行う符号器回路は、単に線形フィードバックシフトレジスタ（ＬＦＳＲ）として実現することができる。
【００１２】
符号化後、符号語Ｃ（ｘ）は、雑音を伴う通信チャネルを介して送られる。受け取られた符号語Ｃ’（ｘ）は、送られた符号語Ｃ（ｘ）に誤り多項式Ｅ（ｘ）を足した値に等しい。受け取られた符号語Ｃ’（ｘ）は、以下のステップに従って訂正される。（１）誤りシンドロームＳiを計算する、（２）誤りシンドロームＳiを用いて、誤りロケータ多項式の係数を計算する、（３）誤りロケータ多項式の根（ｒｏｏｔ）を計算する；根の対数は、誤りロケータ多項式の根である、（４）誤りシンドロームＳiおよび誤りロケータ多項式の根を用いて、誤り値を計算する。
【００１３】
誤りシンドロームＳiは、受け取られた符号語多項式Ｃ’（ｘ）を生成多項式Ｇ（ｘ）の因子で割るモジュロ除算として計算される。
【００１４】
【数３】
2008148334.tif 000005
【００１５】
このとき、
【００１６】
【数４】
2008148334.tif 000006
【００１７】
ここで、αは、有限体ＧＦ（２w）の原始要素である。復号化プロセスのその他のステップを行い、誤りロケータ多項式を計算し、誤りロケータ多項式の根を計算し、そして誤り値を計算する技術は当業者により周知であるため、本発明を理解するためには必要でない。例えば、上で参照した「ＣＯＥＦＦＩＣＩＥＮＴ  ＵＰＤＡＴＩＮＧ  ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＲＥＥＤ−ＳＯＬＯＭＯＮ  ＤＥＣＯＤＥＲ」と題された米国特許第５，４４６，７４３号を参照されたい。
【００１８】
従来技術で知られている、システムの誤り耐性をさらに増加させる別の技術は、符号語を配列して、多次元または積符号として知られているものにすることである。例えば、光ディスク記憶システムは、通常、図２に示されるような２次元積符号を使用する。符号語は、交差する水平方向（即ち、行）および垂直方向（即ち、列）の符号語に配列され、そして復号化プロセスが、繰り返しの通過により行われる。まず、できるだけ多くの誤りを訂正するために、水平方向の符号語の通過が行われ、訂正不可能な水平方向の符号語があれば、それは改変されないままである。次いで、できるだけ多くの誤りを訂正するために、垂直方向の符号語に対して通過が行われ、垂直方向の符号語において訂正された記号がまた、交差する水平方向の符号語の対応する記号を訂正する。その結果、水平方向の符号語は、次の水平方向の通過中に訂正可能であり得る。同様に、水平方向の通過中に訂正された記号は、以前に訂正不可能であった垂直方向の符号語を、次の垂直方向の通過中に訂正可能にし得る。この反復プロセスは、積符号全体が訂正されるか、または訂正不可能であると考えられるまで続く。
【００１９】
積符号の多次元の局面は、誤り耐性を大幅に増加するが、水平方向および垂直方向の符号語に対する繰り返しの通過は、かなりの量の計算時間を必要とする。光ディスク記憶装置では、この計算時間は、ディスクからデータを読み出す際の待ち時間になり、そしてまた、データを連続ストリームで急いで転送することを妨げ得る。これは、円滑でとぎれないオーディオ／ビデオストリーミングを必要とするマルチメディアの応用では特に、非常に望ましくない可能性がある。上で参照した「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＥＦＦＩＣＩＥＮＴＬＹ  ＰＲＯＣＥＳＳＩＮＧ  Ａ  ＭＵＬＴＩ−ＤＩＭＥＮＳＩＯＮＡＬ  ＣＯＤＥ１」と題された米国特許出願は、誤りを含むとしてフラグが立てられた水平方向および垂直方向の符号語だけを処理することにより（即ち、誤りのない符号語はスキップされる）、積符号の処理時間を短縮する方法を開示している。それでも、水平方向および垂直方向の各通過中に誤りシンドロームを再生するためにデータバッファから符号語を読み出す際に、かなりの待ち時間がある。
【００２０】
Ｋａｓｈｉｄａらに発行された米国特許第５，６３１，９１４号には、最初の水平方向の通過中に水平方向および垂直方向の符号語の誤りシンドロームを同時に生成することにより積符号を処理するための誤り訂正装置が開示されている。誤りシンドロームはシンドロームバッファに格納され、次いで、その後の訂正フェーズ中に水平方向および垂直方向の符号語中の誤りを検出および訂正するために使用される。水平方向の符号語に付与された訂正値は、交差する垂直方向の符号語の誤りシンドロームを更新するために使用され、そしてその逆の場合も同様であるため、その後の水平方向または垂直方向の通過中に誤りシンドロームを再生することは不要である。しかし、この技術は、訂正プロセスに待ち時間をもたらす。なぜなら、誤り訂正フェーズが始まり得る前、最初の水平方向の通過中に、水平方向および垂直方向の符号語の誤りシンドロームを生成しなければならないからである。
【発明の開示】
【発明が解決しようとする課題】
【００２１】
従って、多次元符号を復号化するための、より高速でより効率的な誤り訂正プロセッサが必要とされている。
【課題を解決するための手段】
【００２２】
（発明の要旨）
符号語の第２の組と交差する符号語の第１の組を含む多次元符号を訂正するための効率的な誤り訂正プロセッサが開示される。誤り訂正は、符号語の第１および第２の組に対して繰り返しの通過を行うことにより実行される。個々の符号語は、符号語データの関数として計算される誤りシンドロームを用いて訂正される。好適な実施形態では、個々の符号語は、リード−ソロモン符号に従って符号化され、そして、誤りシンドロームは、符号語多項式を生成多項式の因子で割るモジュロ除算として計算される。
【００２３】
誤り訂正プロセッサは、多次元符号語全体を格納するためのデータバッファを含み、データバッファに格納された個々の符号語は、繰り返しの通過中に訂正される。データバッファにアクセスする際の待ち時間を最小限にするために、誤り訂正プロセッサは、個々の符号語についての誤りシンドロームを格納するためのシンドロームバッファを含む。この態様で、誤りシンドロームがシンドロームバッファにおいて既に利用可能であるとき、データバッファから個々の符号語を読み出す必要がなくなる。シンドロームバッファは、好ましくは、ダイナミックｒａｍ（ＤＲＡＭ）として実現されるデータバッファと比べて非常に高速であるスタティックｒａｍ（ＳＲＡＭ）として実現される。
【００２４】
第１の実施形態では、第２の組の符号語の誤りシンドロームは、第１の組の符号語の誤りシンドロームを生成するのと同時に生成される。第１の組の符号語に対する通過が終了すると、第２の組の符号語の誤りシンドロームは、すぐにシンドロームバッファから利用可能となり、第２の組の符号語をデータバッファから読み出して誤りシンドロームを生成することが不要になる。これにより、誤り訂正プロセッサのスループットが大幅に増加する。
【００２５】
第２の実施形態では、シンドロームバッファは、第１の組の符号語と第２の組の符号語の両方の誤りシンドロームを格納する。第１の組の符号語および第２の組の符号語の両方の誤りシンドロームは、第１の組の符号語に対する最初の通過中に同時に生成される。この態様で、最初の水平方向の通過後のデータバッファへの唯一のアクセスは、データ記号を訂正することであり、符号語全体をデータバッファから読み出して誤りシンドロームを再生することが不要になる。なぜなら、誤りシンドロームは既にシンドロームバッファにおいて利用可能であるからである。
【００２６】
両実施形態において、シンドロームバッファに格納された誤りシンドロームは、交差する符号語で記号が訂正されると、更新される。例えば、第１の組の符号語の記号が訂正されると、その訂正された記号で第１の組の符号語と交差する第２の組の符号語についての誤りシンドロームがシンドロームバッファから読み出され、そして訂正値を用いて更新される。第１の組の符号語および第２の組の符号語の両方の誤りシンドロームが格納される第２の実施形態では、誤りシンドロームは、訂正されたデータ記号の場所に従って、訂正値を用いて自動的に調節される。
【００２７】
本発明の上記およびその他の局面および利点は、図面を考慮しながら以下に示す本発明の詳細な説明を読むことによって、より良く理解される。
【発明を実施するための最良の形態】
【００２８】
（好適な実施形態の詳細な説明）
概要
ディスク記憶装置のための典型的な従来技術の誤り訂正プロセッサの概要が図１に示される。書き込み動作（記憶装置はリードオンリでないと仮定する）の間、ユーザデータはホストコンピュータから転送され、データバッファ２に格納される。次いで、冗長／シンドロームジェネレータ４は、多次元符号の個々の符号語についてＥＣＣ冗長記号を生成するために、データバッファ２からデータを読み出す。一旦多次元符号のサブセット符号語が生成されると、サブセット符号語に対してＣＲＣ検査記号が生成され、次いで、多次元符号語全体が、ディスク記憶媒体６に書き込まれる。ディスク記憶媒体６は、磁気であっても光学であってもよい。
【００２９】
好適な実施形態では、個々の符号語は、リード−ソロモン符号により生成される。リード−ソロモン符号語Ｃ（ｘ）は、以下の形の多項式として表される。
【００３０】
【数５】
2008148334.tif 000007
【００３１】
ここで、Ｄ（ｘ）はデータ多項式であり、Ｇ（ｘ）は生成多項式であり、ｍは生成多項式Ｇ（ｘ）の次数である。データ多項式Ｄ（ｘ）の係数は、ホストシステムから受け取られ且つデータバッファ２に格納されるデータストリームのｗビット記号である。符号語Ｃ（ｘ）を生成するために、データ多項式Ｄ（ｘ）にｘmが掛けられ、そしてＥＣＣ冗長記号が付加される。ここで、ＥＣＣ冗長記号は、以下のモジュロ除算として生成される。
【００３２】
【数６】
2008148334.tif 000008
【００３３】
符号化プロセスは、当業者に周知であるように、線形フィードバックシフトレジスタ（ＬＦＳＲ）を用いて容易に実現され得る。
【００３４】
読み出し動作の間、多次元符号語は、ディスク記憶装置６から読み出され、そしてデータバッファ２に格納される。次いで、訂正プロセッサは、符号語の第１および第２の組に対する繰り返しの通過を開始する。個々の符号語は、データバッファ２から読み出され、そして誤りシンドロームＳiは、符号語多項式Ｃ’（ｘ）を生成多項式Ｇ（ｘ）の因子で割ることにより計算される。
【００３５】
【数７】
2008148334.tif 000009
【００３６】
このとき、
【００３７】
【数８】
2008148334.tif 000010
【００３８】
ここで、αは、有限体ＧＦ（２w）の原始要素である。シンドロームＳiがゼロでない場合、それは、符号語Ｃ’（ｘ）が、誤った記号を少なくとも１つ含むことを示す。シンドロームＳiは、ライン１０を介して誤り訂正器８に転送される。誤り訂正器８は、誤り位置および訂正値を計算する。次いで、誤った記号はデータバッファ２から読み出されて訂正され、そして、訂正された記号が、データバッファ２に戻される。
【００３９】
図２は、典型的なデジタルビデオディスク（ＤＶＤ）記憶システムにおいて現在使用されている２次元積符号の例示的なフォーマットを示す。この積符号は、１６個のセクタを含み、各セクタは、１２個の符号語を含む。従って、合計で２０８個の水平方向の符号語および１８２個の垂直方向の符号語となる。各セクタの端部には、水平方向および垂直方向の通過の終わりにユーザデータの訂正の有効性および完全性を確認するためのＣＲＣバイトが４バイトある（上記の参考文献である「ＥＲＲＯＲ  ＣＯＲＲＥＣＴＩＯＮ  ＡＮＤ  ＣＯＮＣＵＲＲＥＮＴ
ＶＥＲＩＦＩＣＡＴＩＯＮ  ＯＦ  Ａ  ＰＲＯＤＵＣＴ  ＣＯＤＥ」と題された米国特許出願を参照されたい）。水平方向の符号語の各々は、１７２個の８ビットユーザデータ記号と、１０個の８ビットＥＣＣ冗長記号とを含む。垂直方向の符号語の各々は、１９２個の８ビットユーザーデータ記号と、１６個の８ビットＥＣＣ冗長記号とを含む。
【００４０】
図１に示される従来技術の誤り訂正プロセッサは、水平方向および垂直方向の各通過中に誤りシンドロームＳiを生成するために、データバッファ２から（水平方向または垂直方向の）符号語全体を読み出す。これは、積符号の符号語全体を訂正するために数回の通過が必要とされる場合は特に、データバッファ２にアクセスする際の待ち時間があり、効率的でない。
【００４１】
誤り訂正プロセッサ
従来技術の欠点を克服する本発明の誤り訂正プロセッサが、図３に示される。図１の誤り訂正プロセッサと同様に、本発明は、ホストから受け取った書き込みデータと、ディスク記憶装置から受け取った読み出しデータとを格納するためのデータバッファ２を使用する。ただし、図１とは異なり、本発明は、誤りシンドロームを格納するためのシンドロームバッファ１２を使用して、符号語が処理されるたびに誤りシンドロームを再生するためにデータバッファ２にアクセスする際の待ち時間を回避する。さらに、シンドロームジェネレータ１４は、交差する符号語の第１および第２の組についての誤りシンドロームを同時に生成するように改変される。この態様で、第１の組の符号語の処理直後に、第２の組の符号語の誤りシンドロームが利用可能になり、第２の組の符号語をデータバッファ２から読み出して誤りシンドロームを生成することが不要になる。
【００４２】
誤り訂正器８は、図１の従来技術と実質的に同じように動作する。ただし、誤り訂正器８では、従来技術に加えて、シンドロームバッファ１２に格納された誤りシンドロームを更新するために、訂正値がライン１６を介してシンドロームジェネレータ１４に送られる。第２の組の符号語中の記号に訂正が行われると、その訂正された記号で第１の組の符号語と交差する第２の組の符号語の誤りシンドロームが、訂正値を用いて更新される。例えば、図２に示される２次元積符号について考える。水平方向の通過中に２番目の水平方向の符号語の３番目の記号１７が訂正されると、３番目の垂直方向の符号語の誤りシンドロームが、訂正値を用いて同時に更新される。この態様で、水平方向の符号語に訂正が行われる場合であっても、水平方向の符号語に対する通過の終了直後に、すべての垂直方向の符号語の誤りシンドロームが利用可能となる。これにより、誤り訂正器８が、誤りシンドロームを再生するためにデータバッファから符号語を読み出す必要なく、垂直方向の符号語の訂正をすぐに開始することができるようになる。
【００４３】
シンドロームバッファ１２は、好ましくは、データバッファ２と比べて非常に高速なスタティックｒａｍ（ＳＲＡＭ）として実現される（シンドロームバッファ１２よりかなり多くのデータを格納するデータバッファ２は、好ましくは、コスト効率はより優れているがより低速であるダイナミックｒａｍ（ＤＲＡＭ）を用いて実現される）。さらに、シンドロームバッファ１２は、好ましくは、データバッファ２よりも幅の広いデータバスを使用し、多数の誤りシンドロームを並行してアクセスおよび更新できるようにする。
【００４４】
同時シンドロームジェネレータ
以下に、本発明のシンドロームジェネレータ１４の２つの実施形態が開示される。第１の実施形態では、垂直方向の符号語のシンドロームは、水平方向の通過中に水平方向の符号語のシンドロームを生成するのと同時に生成される。以下により詳細に説明されるように、シンドロームバッファ１２は、垂直方向のシンドロームの生成を容易にする。従って、シンドロームバッファ１２に格納された垂直方向の符号語のシンドロームは、水平方向の通過の直後に利用可能となり、シンドロームを生成するためにデータバッファにアクセスすることなく、垂直方向の符号語を訂正することができるため、誤り訂正待ち時間を大幅に短縮する。本実施形態は、デジタルビデオディスク（ＤＶＤ）記憶装置などの場合のように大量のＥＣＣ冗長を使用する積符号に特によく適している。なぜなら、通常、水平方向および垂直方向の符号語に対する１回の通過が終わると、訂正が終了するからである。
【００４５】
より少ないＥＣＣ冗長を使用し、従って水平方向および垂直方向の通過を多数回必要とする積符号に向けられる本発明の第２の実施形態によれば、シンドロームバッファ１２は、水平方向の符号語および垂直方向の符号語の両方の誤りシンドロームを格納する。シンドロームの２つの組はともに、最初の水平方向の通過中に同時に生成され、そして、シンドロームは、訂正値を用いて更新される。この態様で、誤りシンドロームを再生するためにデータバッファにアクセスする際の待ち時間が、水平方向の通過および垂直方向の通過の両方について回避される。誤り訂正は、数分の１の時間で行われる。なぜなら、最初の通過の後に行われる通過は、データを訂正するためにデータバッファにアクセスするだけでよいからである。
【００４６】
シンドロームバッファ１２に垂直方向の誤りシンドロームだけを格納する本発明の第１の実施形態は、図４および図５を参照して理解される。図４は、水平方向の各通過中に、水平方向の符号語のシンドロームを生成するために使用される回路を示す。即ち、水平方向の誤りシンドロームは常に再生され、シンドロームバッファ１２には格納されない。水平方向の誤りシンドロームＳiを生成するために、図４の回路は、水平方向の符号語Ｃ’（ｘ）の各々を生成多項式Ｇ（ｘ）の因子で割るモジュロ除算を行う。
【００４７】
【数９】
2008148334.tif 000011
【００４８】
このとき、
【００４９】
【数１０】
2008148334.tif 000012
【００５０】
この計算を実行するために、水平方向の符号語の記号（ＥＣＣ冗長を含む）がデータバッファ２から順次読み出され、そして、ライン１８を介して、線形フィードバックシフトレジスタ（ＬＦＳＲ）２０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を掛けるからである。図７Ｃのステップ７８で、データバッファに格納された水平方向の符号語の記号が、訂正値を用いて訂正され、ステップ８０で、図５を参照して上で説明したように、訂正値を用いて、Ｃ＿ＣＯＬの垂直方向の符号語の垂直方向のシンドロームを更新する。ステップ８２で、変数Ｃ＿ＣＯＬが、水平方向の符号語中の次の記号に増分され、そして訂正ループが再実行される。
【００６３】
ステップ８４でＣ＿ＣＯＬが１８２に等しいとき、訂正されている水平方向の符号語の最後の記号が処理されたことになる。次の垂直方向の通過中に行われる現在の水平方向の符号語の誤りシンドロームの更新を容易にするために、ステップ８６で、現在の水平方向の符号語の誤りシンドロームが、符号語の最初の記号に配置しなおされる。これは、以下の計算により行われる。
【００６４】
【数１１】
2008148334.tif 000013
【００６５】
異なるオフセット値を用いて同様の計算を行う例は、上で参照した「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＲＡＴＡＴＵＳ  ＦＯＲ  ＥＦＦＩＣＩＥＮＴＬＹ  ＰＲＯＣＥＳＳＩＮＧ  Ａ  ＭＵＬＴＩ−ＤＩＭＥＮＳＩＯＮＡＬ  ＣＯＤＥ」と題された米国特許出願において提供される。
【００６６】
図７Ｃのステップ８８で、訂正ビジーフラグがクリアされ、そして訂正手順は、ステップ６４で、図７Ｂのシンドローム生成手順が、次の水平方向の符号語の誤りシンドロームを生成し終わるのを待つ。シンドローム生成手順と誤り訂正手順とは、最後の水平方向の符号語が処理されるまで（即ち、図７Ｂのステップ６２でＲＯＷが２０８と等しくなるまで）、並行して行われる。図７Ａのステップ３８で、最初の水平方向の通過後に誤りがまだ残っていれば、ステップ４０で、垂直方向の通過が実行される。これについてのフロー図は、図７Ｄに示される。
【００６７】
ステップ９０で、訂正変数Ｃ＿ＣＯＬおよびＣ＿ＲＯＷがゼロにリセットされる（即ち、最初の垂直方向の符号語の最初の記号にリセットされる）。次いで、ステップ９２で、訂正されている垂直方向の符号語のシンドロームが処理され、誤りロケータ多項式を生成し、そして、根が有効な記号場所に対応するかどうかを判定する。ステップ９４で、シンドロームが、誤りが多すぎることを示すか、または、誤りロケータ多項式の根が無効記号を指すと、符号語は訂正不可能であると考えられる。ステップ９４で符号語が訂正可能であれば、ステップ９６で、Ｃ＿ＣＯＬの垂直方向の符号語のシンドロームがクリアされる（ゼロに設定される）。次いでループが実行され、Ｃ＿ＣＯＬの垂直方向の符号語を訂正する。ステップ９８で、Ｃ＿ＲＯＷの記号が誤っていれば、分岐が実行され、ステップ１００で、データバッファに格納された記号を訂正し、そしてステップ１０２で、訂正値を用いて水平方向のシンドロームを更新する。図６Ａの回路は、図５を参照して上で説明された態様と同様の態様で水平方向のシンドロームを更新するために用いられる。Ｃ＿ＲＯＷの水平方向のシンドロームがシンドロームバッファ１２から取り出され、αi３０iが掛けられ、訂正値３４iに付加され、次いでシンドロームバッファ１２に戻される。図７Ｄのフローチャートには示されていないが、水平方向のシンドロームは、訂正が行われなくても（即ち、訂正値がゼロであっても）、符号語の各記号について更新される。これにより、図６Ａのシンドローム更新回路が単純化され、このシンドローム更新回路は、誤りシンドロームを次の符号語記号に配置するためにαi乗算器３０iしか必要としない。
【００６８】
図７Ｄのステップ１０４で、変数Ｃ＿ＲＯＷは、現在の垂直方向の符号語中の次の記号に増分される。ステップ１０６で、Ｃ＿ＲＯＷが２０８に等しければ、現在の垂直方向の符号語の最後の記号が処理されたことになる。最後の記号が処理された後（または、ステップ９４で符号語が訂正不可能であれば）、Ｃ＿ＣＯＬの垂直方向の符号語の誤りシンドロームは、ステップ１０７で、符号語の最初の記号に配置しなおされる。これは、以下の計算により行われる。
【００６９】
【数１２】
2008148334.tif 000014
【００７０】
ステップ１０８で、変数Ｃ＿ＣＯＬが、次の垂直方向の符号語に増分され、そして変数Ｃ＿ＲＯＷは、次の垂直方向の符号語の最初の記号を指すよう、ゼロにリセットされる。図７Ｄの訂正手順は、ステップ１１０でＣ＿ＣＯＬが１８２に等しくなり、垂直方向の符号語のすべてが処理されたことを示すまで繰り返される。
【００７１】
垂直方向の通過の終わりに、図７Ａのステップ４２で、ＣＲＣ記号を用いて、行われた訂正が有効で完全なものであるかどうかを確認する。ステップ４２で積符号中に誤りがまだ残っていれば、ステップ４４で、水平方向の訂正通過が実行される。これについての詳細は、図７Ｅのフロー図に示される。
【００７２】
ステップ１１２で、訂正変数Ｃ＿ＣＯＬおよびＣ＿ＲＯＷはゼロにリセットされる（即ち、最初の水平方向の符号語の最初の記号にリセットされる）。次いで、訂正されている水平方向の符号語のシンドロームはステップ１１４で処理され、誤りロケータ多項式を生成し、そして、根が有効記号位置に対応するかどうかを判定する。ステップ１１６で、シンドロームが、誤りが多すぎることを示すか、または、誤りロケータ多項式の根が無効記号を指すと、符号語は訂正不可能であると考えられる。ステップ１１６で符号語が訂正可能であれば、ステップ１１８で、Ｃ＿ＲＯＷの水平方向の符号語のシンドロームがクリアされる（ゼロに設定される）。次いでループが実行され、Ｃ＿ＲＯＷの水平方向の符号語を訂正する。ステップ１２０で、Ｃ＿ＣＯＬの記号が誤っていれば、分岐が実行され、ステップ１２２で、データバッファに格納された記号を訂正し、そして、ステップ１２４で、訂正値を用いて垂直方向のシンドロームを更新する。図６Ｂの回路は、垂直方向の通過中に水平方向の誤りシンドロームを更新する場合の図６Ａを参照して上で説明された態様と同様の態様で、垂直方向のシンドロームを更新するために使用される。Ｃ＿ＣＯＬの垂直方向のシンドロームは、シンドロームバッファ１２から取り出され、αi３０iが掛けられ、訂正値３４iに付加され、次いでシンドロームバッファ１２に戻される。図７Ｅにのフロー図には示されていないが、垂直方向のシンドロームは、訂正が行われなくても（即ち、訂正値がゼロであっても）、符号語の各記号について更新される。これにより、図６Ｂのシンドローム更新回路が単純化され、このシンドローム更新回路は、誤りシンドロームを次の符号語記号に配置するためにαi乗算器３０iしか必要としない。
【００７３】
図７Ｅのステップ１２６で、変数Ｃ＿ＣＯＬは、現在の水平方向の符号語中の次の記号に増分される。ステップ１２８で、Ｃ＿ＣＯＬが１８２に等しければ、現在の水平方向の符号語の最後の記号が処理されたことになる。最後の記号が処理された後（または、ステップ１１６で符号語が訂正不可能であれば）、Ｃ＿ＲＯＷの水平方向の符号語の誤りシンドロームは、ステップ１３０で、符号語の最初の記号に配置しなおされる。これは、以下の計算により行われる。
【００７４】
【数１３】
2008148334.tif 000015
【００７５】
ステップ１３２で、変数Ｃ＿ＲＯＷが、次の水平方向の符号語に増分され、そして変数Ｃ＿ＣＯＬは、次の水平方向の符号語の最初の記号を指すよう、ゼロにリセットされる。図７Ｅの訂正手順は、ステップ１３４でＣ＿ＲＯＷが２０８に等しくなり、水平方向の符号語のすべてが処理されたことを示すまで繰り返される。
【００７６】
再び図７Ａを参照して、ステップ４４での水平方向の通過が終了した後、ステップ３８で、ＣＲＣ記号を用いて、積符号に行われた訂正が有効で完全なものであるかどうかを確認する。誤りがまだ残っていれば、ステップ４０で、別の垂直方向の通過が実行される。繰り返し行われる水平方向および垂直方向の通過は、積符号が訂正されるまで、または訂正不可能であると考えられるまで続く。
【００７７】
本発明の目的は、本明細書に開示された実施形態を通して十分に認識された。当業者は、本質的な機能から逸脱することなく、異なる実施形態を通して、本発明の様々な局面を達成することができることを認識する。例えば、図２に示される積符号は、典型的にはデジタルビデオディスク（ＤＶＤ）において使用されるが、本発明は、コンパクトディスク（ＣＤ）において使用されるフォーマットなどの、その他の積符号フォーマットにも等しく適用可能である。さらに、本発明は、積符号だけではなく、その他の多次元符号に適用されてもよい。このように、開示された特定の実施形態は例示的なものであって、前掲の特許請求の範囲により適切に解釈される本発明の範囲を限定するものではない。
【図面の簡単な説明】
【００７８】
【図１】ディスク記憶媒体上に格納される多次元符号語を訂正するための従来技術の誤り訂正プロセッサのブロック図である。
【図２】典型的にはデジタルビデオディスク（ＤＶＤ）において使用される２次元積符号の図である。
【図３】誤りシンドロームを格納するためのシンドロームバッファを含む、本発明の誤り訂正プロセッサのブロック図である。
【図４】本発明の第１の実施形態による、水平方向の符号語の誤りシンドロームを生成するための詳細な回路図である。
【図５】水平方向の符号語の誤りシンドロームを生成するのと同時に、垂直方向の符号語の誤りシンドロームを生成するための詳細な回路図である。
【図６Ａ】本発明の別の実施形態において、シンドロームバッファが水平方向の符号語および垂直方向の符号語の両方の誤りシンドロームを格納する場合に、水平方向および垂直方向の誤りシンドロームをそれぞれ更新する回路を示す図である。
【図６Ｂ】本発明の別の実施形態において、シンドロームバッファが水平方向の符号語および垂直方向の符号語の両方の誤りシンドロームを格納する場合に、水平方向および垂直方向の誤りシンドロームをそれぞれ更新する回路を示す図である。
【図７Ａ】シンドロームバッファに格納された水平方向および垂直方向の誤りシンドロームを用いて積符号を処理する場合の、誤り訂正プロセッサにより実行されるフロー図である。
【図７Ｂ】水平方向の符号語に対する最初の通過中に水平方向および垂直方向の誤りシンドロームを同時に生成する場合のフロー図である。
【図７Ｃ】最初の水平方向の通過中に水平方向の符号語を訂正し、そして、訂正値を用いて、シンドロームバッファに格納された垂直方向の誤りシンドロームを更新する場合のフロー図である。
【図７Ｄ】シンドロームバッファに格納された垂直方向の誤りシンドロームを用いて、垂直方向の通過中に垂直方向の符号語を訂正し、そして、訂正値を用いて、シンドロームバッファに格納された水平方向の誤りシンドロームを更新する場合のフロー図である。
【図７Ｅ】シンドロームバッファに格納された水平方向の誤りシンドロームを用いて、その後の水平方向の通過中に水平方向の符号語を訂正し、そして、訂正値を用いて、シンドロームバッファに格納される垂直方向の誤りシンドロームを更新する場合のフロー図である。
【図１】
2008148334.tif 000016
【図２】
2008148334.tif 000017
【図３】
2008148334.tif 000018
【図４】
2008148334.tif 000019
【図５】
2008148334.tif 000020
【図６Ａ】
2008148334.tif 000021
【図６Ｂ】
2008148334.tif 000022
【図７Ａ】
2008148334.tif 000023
【図７Ｂ】
2008148334.tif 000024
【図７Ｃ】
2008148334.tif 000025
【図７Ｄ】
2008148334.tif 000026
【図７Ｅ】
2008148334.tif 000027