(57)【特許請求の範囲】
【請求項１】
誤り訂正数ｔのリードソロモン符号またはＢＣＨ符号を用いてデータ列の誤りを訂正する誤り訂正装置であって、
少なくとも２ｔ＋１個のシンボルをパリティ列としてそれぞれ含む複数のデータ列を格納するデータ格納手段と、
前記複数のデータ列のうち第１のデータ列から、１組のシンドロームを計算するシンドローム計算手段と、
前記１組のシンドロームから、誤り位置多項式の係数を計算する誤り位置多項式計算手段と、
前記誤り位置多項式の係数を用いて訂正が成功する否かを判定し、訂正失敗と判定したとき、前記データ格納手段に第２のデータ列を要求し、訂正成功と判定したとき、訂正成功の判定結果を出力する判定手段と、
前記訂正成功の判定結果を受け取ったとき、前記１組のシンドロームおよび誤り位置多項式の係数を用いて、前記第１のデータ列の誤りを訂正する訂正手段と
を備えることを特徴とする誤り訂正装置。
【請求項２】
前記誤り位置多項式計算手段は、ｉ番目のシンドロームを用いてバーレカンプマッシ法によりｉ−１番目の多項式の係数からｉ番目の多項式の係数を求める計算を繰り返し、前記判定手段は、２ｔ番目の多項式の係数と２ｔ＋１番目の多項式の係数を比較し、該２ｔ番目の多項式の係数と２ｔ＋１番目の多項式の係数が一致しなければ、訂正失敗と判定することを特徴とする請求項１記載の誤り訂正装置。
【請求項３】
前記訂正手段は、前記訂正成功の判定結果を受け取ったとき、前記誤り位置多項式を用いて前記第１のデータ列の誤り位置を検索するチェーンサーチ実行手段と、検索された誤り位置の正しい値を計算する誤り値計算手段を含むことを特徴とする請求項１または２記載の誤り訂正装置。
【請求項４】
前記訂正手段は、前記１組のシンドロームのうち少なくとも１つのシンドロームが非零であり、かつ、前記チェーンサーチにより誤り位置が見つからない場合、訂正失敗と判定して前記データ格納手段に前記第２のデータ列を要求する判定手段をさらに含むことを特徴とする請求項３記載の誤り訂正装置。
【請求項５】
前記１組のシンドロームを格納するシンドローム格納手段と、前記第１のデータ列と第２のデータ列の差分から各シンドロームの差分を求め、得られた差分を該１組のシンドロームに含まれる各シンドロームに加算することで該１組のシンドロームを更新し、更新された１組のシンドロームを該第２のデータ列の１組のシンドロームとして出力するシンドローム更新手段をさらに備えることを特徴とする請求項１または２記載の誤り訂正装置。
【請求項６】
与えられた情報列と生成多項式の係数を用いて、少なくとも２ｔ＋１個のシンボルからなるパリティ列を生成し、該与えられた情報列に該パリティ列を付加してデータ列を生成する符号化手段をさらに備えることを特徴とする請求項１または２記載の誤り訂正装置。
【請求項７】
誤り訂正数ｔのリードソロモン符号またはＢＣＨ符号を用いてデータ列の誤りを訂正する誤り訂正装置を有する情報記憶装置であって、該訂正装置は、
少なくとも２ｔ＋１個のシンボルをパリティ列としてそれぞれ含む複数のデータ列を格納するデータ格納手段と、
前記複数のデータ列のうち第１のデータ列から、１組のシンドロームを計算するシンドローム計算手段と、
前記１組のシンドロームから、誤り位置多項式の係数を計算する誤り位置多項式計算手段と、
前記誤り位置多項式の係数を用いて訂正が成功する否かを判定し、訂正失敗と判定したとき、前記データ格納手段に第２のデータ列を要求し、訂正成功と判定したとき、訂正成功の判定結果を出力する判定手段と、
前記訂正成功の判定結果を受け取ったとき、前記１組のシンドロームおよび誤り位置多項式の係数を用いて、前記第１のデータ列の誤りを訂正する訂正手段と
を備えることを特徴とする情報記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記録再生装置、受信装置等における誤り訂正技術に関し、特に、リードソロモン（Reed Solomon）符号を用いてデータ列の誤りを訂正する装置に関する。
【背景技術】
【０００２】
磁気ディスク装置のような記録再生装置や通信システムにおいて、リードソロモン符号（例えば、下記の非特許文献１を参照）が誤り訂正符号（ＥＣＣ）として用いられている。
【０００３】
誤り訂正装置において、ＥＣＣ復号器に入力されるデータ列は、検出器から出力される。通常は、図１２に示すように、検出器１１から単一のデータ列が復号候補としてＥＣＣ復号器１２に入力され、復号が行われる。この場合、復号に失敗すると、誤りを訂正することはできない。
【０００４】
そこで、図１３に示すように、検出器２１から複数のデータ列がＥＣＣ復号器２２に入力される装置が用いられる場合もある。この場合、ＥＣＣ復号器２２は、それぞれのデータ列を候補として復号を行うため、訂正能力が向上する。
【０００５】
図１４は、図１３のＥＣＣ復号器２２の構成例を示している。このＥＣＣ復号器２２は、シンドローム計算部４１、誤り位置多項式計算部４２、チェーンサーチ実行部４３、および誤り値計算部４４を備える。
【０００６】
検出器２１から出力された複数のデータ列は、一旦、データ保存部３１に格納され、１つずつＥＣＣ復号器２２に入力される。このとき、ＥＣＣ復号器２２は、以下の手順でデータ列に含まれる誤りを訂正する。
【０００７】
ステップ１：シンドローム計算部４１は、ＥＣＣ復号器２２に入力されたデータ列のシンドローム多項式を計算する。
ステップ２：誤り位置多項式計算部４２は、シンドローム多項式から誤り位置多項式を計算する。誤り位置多項式の計算アルゴリズムとしては、例えば、ユークリッド法またはバーレカンプマッシ（Berlekamp Massey）法が用いられる（例えば、下記の非特許文献２および３を参照）。
【０００８】
ステップ３：チェーンサーチ実行部４３は、ステップ２で得られた誤り位置多項式を用いてチェーンサーチを実行し、データ列上の誤りのある位置（誤り位置）を決定する。
ステップ４：誤り値計算部４４は、誤り位置の誤った値を正しい値に訂正する。
【０００９】
その後、復号判定部３２は、誤り値計算部４４から出力される訂正後のデータ列の正当性をチェックし、正当でなければ訂正失敗と判定して、データ保存部３１に次の復号候補を出力するように指示する。
【００１０】
ここで、図１５から図１９までを参照しながら、リードソロモン符号に基づく誤り訂正の具体例を説明する。
誤り訂正数ｔのリードソロモン符号は、次数２ｔの生成多項式から生成される。符号化に用いるガロア体をＧＦ（２3 ）とし、誤り訂正数ｔを１とすると、リードソロモン符号の生成多項式は、原始元αを用いて、例えば、次式のように書ける。
Ｇ（ｘ）＝（ｘ−１）（ｘ−α）
＝ｘ2 ＋α3 ｘ＋α                    （１）
この場合、３ビットのビット列が１シンボルとして扱われ、ＥＣＣ符号器では、２ｔ（＝２）シンボルのパリティ列が情報列に付加される。例えば、図１５に示すようなビット列を符号化する場合、“００１”、“１１０”、および“１０１”は、ガロア体表示における１、α5 、およびα4 にそれぞれ対応付けられる。ｊ番目のシンボルは、送信語列の多項式におけるｘjの項の係数を表す。したがって、このビット列は、多項式ｘ4 ＋α5 ｘ3 ＋α4 ｘ2を表している。
【００１１】
ＥＣＣ符号器は、図１６に示すように、ビット列が表す多項式を（１）式の生成多項式で割り算し、得られた剰余多項式α4 ｘ＋α4 を表すパリティ列を、ビット列に付加する。この剰余多項式では、ｘの１次および０次の項の係数がともにα4 であるから、図１７に示すようなパリティ列が付加され、５シンボルからなる送信語列が生成される。
【００１２】
この送信語列が磁気ディスクに記録され、読み出された場合、図１８に示すように、誤りを含む受信語列がＥＣＣ復号器２２に入力される可能性がある。この受信語列が表す受信語多項式は、次のようになる。
Ｙ（ｘ）＝αｘ4 ＋α5 ｘ3 ＋α4 ｘ2 ＋α4 ｘ＋α4       （２）
この場合、シンドローム計算部４１は、次式によりシンドローム多項式を計算する。
Ｓ（ｘ）＝ｓ1 ＋ｓ2 ｘ
ｓ1 ＝Ｙ（１）
ｓ2 ＝Ｙ（α）                    （３）
シンドロームｓi （ｉ＝１，２，．．．，２ｔ）は、生成多項式Ｇ（ｘ）のｉ番目の根を受信語多項式Ｙ（ｘ）に代入して得られる値であり、シンドローム多項式Ｓ（ｘ）は、シンドロームｓiをｘi-1 の項の係数とする多項式である。受信語列に誤りが含まれていなければ、すべてのｓi が０となる。
【００１３】
次に、誤り位置多項式計算部４２は、シンドローム多項式Ｓ（ｘ）から、次のような誤り位置多項式Ｃ（ｘ）を計算する。
Ｃ（ｘ）＝１＋α-4ｘ      （４）
次に、チェーンサーチ実行部４３は、誤り位置多項式Ｃ（ｘ）を用いてＣ（αj ）の値（ｊ＝０，１，２，３，４）を計算し、Ｃ（αj ）＝０となる位置ｊを誤り位置として出力する。この例では、Ｃ（α4 ）＝１＋α-4・α4 ＝０となるので、４番目のシンボルに誤りがあることが分かる。
【００１４】
次に、誤り値計算部４４は、シンドローム多項式Ｓ（ｘ）と誤り位置多項式Ｃ（ｘ）を用いて、所定のアルゴリズムで４番目のシンボルの正しい値を計算し、そのビット列を訂正する。ここでは、正しい値１が求められ、図１９に示すように、受信語列における４番目のシンボルが、αから１に変更される。
【００１５】
磁気ディスクでは、ｔ＝２０とするリードソロモン符号が用いられることがあり、ＥＣＣ符号器では、図２０に示すように、４０シンボルのパリティ列が生成され、１セクタのビット列の前に挿入される。この場合、シンドローム多項式Ｓ（ｘ）と誤り位置多項式Ｃ（ｘ）は、例えば、次のようになる。
Ｓ（ｘ）＝ｓ1 ＋ｓ2 ｘ＋・・・＋ｓ40ｘ39          （５）
Ｃ（ｘ）＝１＋ｘ＋α2 ｘ2 ＋・・・＋α35ｘ8       （６）
【非特許文献１】今井秀樹, “符号理論”, 電子情報通信学会編，pp.155-175
【非特許文献２】E. R. Berlekamp, “Algebraic Coding Theory”, McGraw-Hill Book Co., pp.176-199 and pp.218-240, New York, 1968
【非特許文献３】J. L. Massey, “Shift-Register Synthesis and BCH Decoding”, IEEE Transactions on Information Theory, vol. IT-15, pp.122-127, 1969
【発明の開示】
【発明が解決しようとする課題】
【００１６】
上述した従来のＥＣＣ復号器には、次のような問題がある。
実際の受信語列は５シンボルよりはるかに長いため、受信語多項式Ｙ（ｘ）の次数が大きくなる。このため、複数の候補のデータ列を復号する際、シンドローム多項式Ｓ（ｘ）の計算やチェーンサーチの計算量が膨大になり、復号処理に長時間を要する。
【００１７】
また、図１４の構成では、復号の成否をＥＣＣ復号器の出力側で判定しているため、ある候補がＥＣＣ復号器の訂正能力を超える誤りを含んでいるために訂正が失敗した場合でも、一連の復号処理を実行することになり、効率が悪い。そこで、候補のデータ列の復号が失敗しているか否かの判定を早期に行って、失敗していると分かった場合は処理を中止し、早く次の候補の復号に移ることが望ましい。
【００１８】
本発明の課題は、リードソロモン符号の復号処理における計算量を削減し、処理を高速化することである。
【課題を解決するための手段】
【００１９】
図１は、本発明の第１および第２の誤り訂正装置の原理図である。
本発明の第１の誤り訂正装置は、データ格納手段１０１、シンドローム計算手段１０２、誤り位置多項式計算手段１０３、判定手段１０４、および訂正手段１０５を備え、誤り訂正数ｔのリードソロモン符号またはＢＣＨ（Bose Chaudhuri Hocquenghem）符号を用いてデータ列の誤りを訂正する。
【００２０】
データ格納手段１０１は、少なくとも２ｔ＋１個のシンボルをパリティ列としてそれぞれ含む複数のデータ列を格納する。シンドローム計算手段１０２は、複数のデータ列のうち第１のデータ列から、１組のシンドロームを計算する。誤り位置多項式計算手段１０３は、その１組のシンドロームから、誤り位置多項式の係数を計算する。
【００２１】
判定手段１０４は、誤り位置多項式の係数を用いて訂正が成功する否かを判定し、訂正失敗と判定したとき、データ格納手段１０１に第２のデータ列を要求し、訂正成功と判定したとき、訂正成功の判定結果を出力する。訂正手段１０５は、訂正成功の判定結果を受け取ったとき、上記１組のシンドロームおよび誤り位置多項式の係数を用いて、第１のデータ列の誤りを訂正する。
【００２２】
一般に、誤り訂正数ｔのリードソロモン符号によれば、２ｔ次の生成多項式に基づいて２ｔ個のシンボルからなるパリティ列を付加することにより、データ列に含まれる誤ったシンボルをｔ個まで訂正することができる。これに対して、より高次の生成多項式に基づいて数シンボルのパリティを余分に付加することで、リードソロモン符号の冗長性が増加し、シンドロームを数個余分に求めることができるようになる。
【００２３】
例えば、２ｔ＋１次の生成多項式に基づいて２ｔ＋１個のシンボルからなるパリティ列を付加すれば、２ｔ＋１個のシンドロームを求めることができる。それらのシンドロームから誤り位置多項式の係数を計算することで、復号途中でデータ列の訂正の成否を判定することが可能になる。
【００２４】
そして、訂正失敗と判定された場合、第１のデータ列の訂正を行わずに第２のデータ列の復号処理が開始されるため、第１のデータ列に対する無駄なチェーンサーチ等を省略することができ、計算量が削減される。
【００２５】
本発明の第２の誤り訂正装置は、データ格納手段１０１、シンドローム計算手段１０２、シンドローム格納手段１０６、シンドローム更新手段１０７、および訂正手段１０８を備え、リードソロモン符号またはＢＣＨ符号を用いてデータ列の誤りを訂正する。
【００２６】
データ格納手段１０１は、複数のデータ列を格納する。シンドローム計算手段１０２は、複数のデータ列のうち第１のデータ列から、１組のシンドロームを計算する。シンドローム格納手段１０６は、その１組のシンドロームを格納する。訂正手段１０８は、その１組のシンドロームを用いて第１のデータ列の誤りを訂正する。
【００２７】
シンドローム更新手段１０７は、第１のデータ列の訂正に失敗したとき、第１のデータ列と第２のデータ列の差分から各シンドロームの差分を求め、得られた差分を上記１組のシンドロームに含まれる各シンドロームに加算することでその１組のシンドロームを更新し、更新された１組のシンドロームを第２のデータ列の１組のシンドロームとして出力する。
【００２８】
一般に、シンドロームは、データ列が表す多項式に所定値を代入して計算されるため、第１のデータ列と第２のデータ列の差分に対応する項のみを計算することで、シンドロームの差分を求めることができる。
【００２９】
そこで、第１のデータ列の訂正に失敗したとき、第２のデータ列の各シンドロームを改めて計算し直すのではなく、既に計算されている第１のデータ列の各シンドロームに差分を加算することで、第２のデータ列の各シンドロームが求められる。これにより、第２のデータ列に対するシンドロームの計算を簡略化することができ、計算量が削減される。
【００３０】
データ格納手段１０１、シンドローム計算手段１０２、誤り位置多項式計算手段１０３、判定手段１０４、シンドローム格納手段１０６、およびシンドローム更新手段１０７は、例えば、後述する図５のデータ保存部２３１、シンドローム計算部５０１、誤り位置多項式計算部５０４、比較部５０５、シンドローム保存部５０２、およびシンドローム更新部５０３にそれぞれ対応する。
【００３１】
訂正手段１０５は、例えば、図５のチェーンサーチ実行部５０６、判定部５０７、および誤り値計算部５０８に対応し、訂正手段１０８は、例えば、図５の誤り位置多項式計算部５０４、比較部５０５、チェーンサーチ実行部５０６、判定部５０７、および誤り値計算部５０８に対応する。
【発明の効果】
【００３２】
本発明によれば、リードソロモン符号またはＢＣＨ符号の復号途中でデータ列の訂正の成否を判定することができるため、訂正失敗の場合の無駄なチェーンサーチ等を省略することが可能になる。また、２番目以降の復号候補のデータ列に対するシンドロームの計算を、大幅に簡略化することが可能になる。したがって、全体的に計算量が削減され、復号処理が高速化される。
【発明を実施するための最良の形態】
【００３３】
以下、図面を参照しながら、本発明を実施するための最良の形態を詳細に説明する。
本実施形態では、記録再生装置の代表例である磁気ディスク装置における誤り訂正処理について説明する。図２は、磁気ディスク装置の記録再生システムの構成例を示している。この記録再生システムは、プリアンプ２０１、リードチャネル２０２、およびハードディスクコントローラ２０３からなる。
【００３４】
プリアンプ２０１は、増幅器２１１およびドライバ２１２を備える。リードチャネル２０２は、サーマルアスペリティ（ＴＡ）検出器２２１、可変利得増幅器（ＶＧＡ）２２２、ローパスフィルタ（ＬＰＦ）２２３、アナログ／デジタルコンバータ（ＡＤＣ）２２４、有限インパルス応答（ＦＩＲ）フィルタ２２５、検出器２２６、ドライバ２２７、および記録補償器２２８を備える。
【００３５】
ハードディスクコントローラ２０３は、データ保存部２３１、ＥＣＣ復号器２３２、ＲＬＬ（Run Length Limited）復号器２３３、ＣＲＣ（Cyclic Redundancy Check ）復号器２３４、ＥＣＣ符号器２３５、ＲＬＬ符号器２３６、およびＣＲＣ符号器２３７を備える。
【００３６】
記録データは、まず、ハードディスクコントローラ２０３内でＣＲＣ符号器２３７を経由して、ＲＬＬ符号器２３６により、拘束条件が満たされるデータ列に変換される。そして、ＥＣＣ符号器２３５により、そのデータ列にパリティ列が付加される。
【００３７】
次に、リードチャネル２０２では、記録データは、記録補償器２２８およびドライバ２２７を経由してプリアンプ２０１に送出される。記録補償器２２８は、磁化反転が隣接する個所で反転間隔を多少広げるための補償処理を行う。プリアンプ２０１では、ドライバ２１２により、記録ヘッドへのライト電流を発生させる。
【００３８】
一方、再生の際は、まず、再生ヘッドからのアナログ電圧が、プリアンプ２０１の増幅器２１１により増幅された後、アナログ信号としてリードチャネル２０２に出力される。リードチャネル２０２では、ＴＡ検出器２２１により、アナログ信号のサーマルアスペリティ検出処理が行われた後、ＶＧＡ２２２、ＬＰＦ２２３、およびＡＤＣ２２４を経由してデジタル信号への変換が行われる。そして、ＦＩＲフィルタ２２５により波形等化が行われた後、検出器２２６によりビット列が生成される。
【００３９】
次に、生成されたビット列は、ハードディスクコントローラ２０３に戻され、一旦、データ保存部２３１に格納された後、ＥＣＣ復号器２３２により、誤り訂正が行われる。そして、ＲＬＬ復号器２３３およびＣＲＣ復号器２３４を経由して、再生データとして出力される。
【００４０】
図３は、図２のＥＣＣ符号器２３５の構成例を示している。ＥＣＣ符号器２３５は、パリティ生成部３０１を含む。パリティ生成部３０１は、生成多項式を用いて記録データのビット列からパリティ列を生成する。一般に、誤り訂正数ｔのリードソロモン符号の生成多項式は、次式のように書くことができる。
Ｇ（ｘ）＝（ｘ−α）（ｘ−α2 ）・・・（ｘ−α2t）      （７）
したがって、ｔ＝２０の場合、通常は、次式のような４０次の生成多項式が用いられる。
Ｇ（ｘ）＝（ｘ−α）（ｘ−α2 ）・・・（ｘ−α40）      （８）
これに対して、本実施形態では、復号の成否を早期に判定するために、生成多項式の次数を１つ増やして、次式のような４１次の生成多項式を用いる。
Ｇ（ｘ）＝（ｘ−α）（ｘ−α2 ）・・・（ｘ−α40）（ｘ−α41）      （９）
このため、図４に示すように、４１シンボルのパリティ列が生成され、１セクタのビット列の前に挿入される。ここでは、例えば、ガロア体ＧＦ（２10）が符号化に用いられ、１セクタは４１０シンボルからなり、１シンボルは１０ビットからなるものとする。
【００４１】
図５は、図２のＥＣＣ復号器２３２の構成例を示している。ＥＣＣ復号器２３２は、シンドローム計算部５０１、シンドローム保存部５０２、シンドローム更新部５０３、誤り位置多項式計算部５０４、比較部５０５、チェーンサーチ実行部５０６、判定部５０７、および誤り値計算部５０８を備える。
【００４２】
リードチャネル２０２から送出された複数の復号候補は、データ保存部２３１に格納され、１つずつＥＣＣ復号器２３２に入力される。まず、１番目の候補のデータ列に対して、ＥＣＣ復号器２３２は、以下の手順で復号処理を行う。
【００４３】
ステップ１：シンドローム計算部５０１は、データ列のシンドローム多項式（多項式の係数）を計算し、シンドローム多項式を誤り位置多項式計算部５０４に出力する。このとき、２ｔ＋１個のシンドロームｓi （ｉ＝１，２，．．．，２ｔ，２ｔ＋１）の値が求められる。また、２番目以降の候補の復号処理で利用するために、シンドローム計算部５０１は、シンドローム多項式をシンドローム保存部５０２に格納する。
【００４４】
ステップ２：誤り位置多項式計算部５０４は、バーレカンプマッシ法により、シンドローム多項式から誤り位置多項式を計算する。
バーレカンプマッシ法では、通常、多項式の初期値から始めて、生成多項式の次数と同じ回数だけ多項式の更新を繰り返すことで、誤り位置多項式が計算される。このとき、ｉ番目の多項式Ｃi （ｘ）を求めるには、ｉ番目のシンドロームｓi の値が必要となる。
【００４５】
誤り位置多項式計算部５０４は、２ｔ番目の多項式Ｃ2t（ｘ）と２ｔ＋１番目の多項式Ｃ2t+1（ｘ）を、データ列とともに比較部５０５に出力する。
ステップ３：比較部５０５は、多項式Ｃ2t（ｘ）とＣ2t+1（ｘ）の係数を比較し、２つの多項式が一致するか否かをチェックする。
【００４６】
バーレカンプマッシ法では、データ列に含まれる誤りの数がｋ個（ｋ≦ｔ）の場合、２ｋ＋１回目以降の繰り返しでは多項式が更新されず、Ｃ2k（ｘ）以降の多項式はすべて同じになるという性質がある。したがって、Ｃ2t（ｘ）とＣ2t+1（ｘ）が一致すれば、誤りの数は高々ｔ個であり、誤り訂正能力の範囲内であることが分かる。逆に、Ｃ2t（ｘ）とＣ2t+1（ｘ）が一致しなければ、誤り訂正能力を超えていることになる。
【００４７】
そこで、比較部５０５は、Ｃ2t（ｘ）とＣ2t+1（ｘ）が一致すれば、この候補の訂正が成功すると判定して、データ列、シンドローム多項式、誤り位置多項式、および判定結果を、チェーンサーチ実行部５０６に出力する。また、Ｃ2t（ｘ）とＣ2t+1（ｘ）が異なる場合は、この候補の訂正が失敗したと判定して、データ保存部２３１に次の復号候補を出力するように指示する。
【００４８】
このように、１シンボルのパリティを余分にデータ列に付加することにより、バーレカンプマッシ法の多項式を１つ余分に計算することができるため、復号途中でデータ列の訂正失敗を検出することが可能になる。なお、数シンボルのパリティを余分に付加するフォーマットを用いてもよい。
【００４９】
ステップ４：チェーンサーチ実行部５０６は、誤り位置多項式Ｃ（ｘ）を用いてチェーンサーチを実行し、データ列上のすべての位置ｊについてＣ（αj ）の値を計算する。そして、データ列、シンドローム多項式、誤り位置多項式、およびＣ（αj ）の計算結果を、判定部５０７に出力する。ここで、Ｃ（αj ）＝０となる位置ｊが、誤り位置に相当する。
【００５０】
ステップ５：判定部５０７は、シンドローム多項式とＣ（αj ）の計算結果を用いて、訂正の成否を判定し、訂正が成功すると判定した場合は、チェーンサーチ実行部５０６から受け取った情報と判定結果を誤り値計算部５０８に出力する。また、訂正が失敗したと判定した場合は、データ保存部２３１に次の復号候補を出力するように指示する。
【００５１】
ステップ６：誤り値計算部５０８は、シンドローム多項式と誤り位置多項式を用いて、所定のアルゴリズムで誤り位置の誤った値を正しい値に訂正する。そして、訂正後のデータ列からパリティ列を削除して、後段のＲＬＬ復号器２３３に出力する。
【００５２】
したがって、１番目の候補の訂正が成功した場合は、誤り訂正されたデータ列がＥＣＣ復号器２３２から出力される。訂正が失敗して、２番目以降の候補を復号する必要が生じた場合は、シンドローム保存部５０２に格納された情報を用いて、復号処理が行われる。
【００５３】
この場合、ステップ１において、シンドローム更新部５０３は、復号対象の候補と、シンドローム保存部５０２に格納された１番目の候補とを比較して、異なっているシンボルを取り出し、シンドローム保存部５０２に格納されたシンドローム多項式を更新する。そして、更新されたシンドローム多項式を、誤り位置多項式計算部５０４に出力する。ステップ２以降の処理は、上述した１番目の候補の場合と同様である。
【００５４】
このように、図５のＥＣＣ復号器２３２によれば、２番目以降の候補に対してシンドローム多項式の計算を簡略化でき、比較部５０５で訂正失敗と判定された場合、チェーンサーチを行わなくても済むので、大幅に計算量が削減される。また、判定部５０８で訂正失敗と判定された場合、誤り訂正を行わなくても済むので、さらに計算量が削減される。
【００５５】
例えば、図６に示すように、ｎ＋１シンボルからなる１番目の候補と復号対象の候補を比較すると、１番目の候補におけるｊ＝１の位置のシンボルはα12であり、復号対象の候補における同じ位置のシンボルはα6 であるから、値が異なっていることが分かる。この場合、１番目の候補の受信語多項式Ｙ１（ｘ）と、復号対象の候補の受信語多項式Ｙ（ｘ）は、それぞれ次のようになる。
Ｙ１（ｘ）＝α2 ｘn ＋α22ｘn-1＋・・・＋α12ｘ＋α5       （１０）
Ｙ（ｘ）＝α2 ｘn ＋α22ｘn-1＋・・・＋α6 ｘ＋α5         （１１）
また、１番目の候補のシンドローム多項式Ｓ１（ｘ）と、復号対象の候補のシンドローム多項式Ｓ（ｘ）は、それぞれ次のようになる。
Ｓ１（ｘ）＝ｓ１1 ＋ｓ１2 ｘ＋・・・＋ｓ１2tｘ2t-1＋ｓ１2t+1ｘ2t
ｓ１i ＝Ｙ１（αi ）  （ｉ＝１，２，．．．，２ｔ，２ｔ＋１）      （１２）
Ｓ（ｘ）＝ｓ1 ＋ｓ2 ｘ＋・・・＋ｓ2tｘ2t-1＋ｓ2t+1ｘ2t
ｓi ＝Ｙ（αi ）  （ｉ＝１，２，．．．，２ｔ，２ｔ＋１）          （１３）
ここで、ｓ１i は１番目の候補のｉ番目のシンドロームを表し、ｓi は復号対象の候補のｉ番目のシンドロームを表す。このとき、ｓi は、ｓ１i を用いて次式のように書ける。
ｓi ＝ｓ１i ＋Ｙ（αi ）−Ｙ１（αi ）
＝ｓ１i ＋（α6 −α12）αi           （１４）
（１４）式は、シンボル値の変化量（α6 −α12）とαi の積を、シンドローム保存部５０２に格納されたｓ１i の値に加算すれば、更新後のシンドロームｓi の値が得られることを示している。
【００５６】
また、複数のシンボルの値が異なっている場合も、（１４）式と同様にして、更新後のシンドロームｓi を計算することができる。この場合、シンドロームの差分Ｙ（αi ）−Ｙ１（αi ）は、シンボル値が異なっているすべての位置ｊについて、シンボル値の変化量と（αi ）j の積を加算した結果となる。
【００５７】
こうして更新されたシンドロームｓi を用いて、バーレカンプマッシ法により、多項式Ｃ1 （ｘ）〜Ｃ2t+1（ｘ）が順次計算される。ｔ＝２０の場合、多項式Ｃ1 （ｘ）、Ｃ40（ｘ）、およびＣ41（ｘ）は、例えば、次のようになる。
Ｃ1 （ｘ）＝１＋αｘ
Ｃ40（ｘ）＝１＋ｘ＋α2 ｘ2 ＋・・・＋α35ｘ20
Ｃ41（ｘ）＝１＋αｘ＋α50ｘ3 ＋・・・＋α100 ｘ20      （１５）
この場合、Ｃ40（ｘ）とＣ41（ｘ）が一致しないため、復号対象の候補の訂正は失敗と判定され、次の候補の復号が行われる。
【００５８】
次に、図７から図１０までを参照しながら、図５のＥＣＣ復号器２３２が行う復号処理について、さらに詳細に説明する。
図７は、シンドローム更新部５０３の処理のフローチャートである。シンドローム更新部５０３は、まず、復号対象の候補と、シンドローム保存部５０２に格納された候補のデータ列を比較して、それぞれの候補から異なっているシンボルの値を取り出す（ステップ７０１）。
【００５９】
次に、シンボルが異なっているすべての位置ｊについて、シンボルの変化量と（αi ）j の積の総和を求めて、その値をシンドロームの差分Ｙ（αi ）−Ｙ１（αi ）とする（ステップ７０２）。そして、シンドローム保存部５０２に格納されたシンドロームに差分を加算して、シンドロームを更新する（ステップ７０３）。
【００６０】
図８は、誤り位置多項式計算部５０４の処理のフローチャートである。誤り位置多項式計算部５０４は、まず、初期化処理を行って、多項式Ｃ0 （ｘ）、多項式Ｂ（ｘ）、整数ａ、ｂ、およびＬを以下のように設定する（ステップ８０１）。
Ｃ0 （ｘ）＝１
Ｂ（ｘ）＝１
ａ＝１
ｂ＝１
Ｌ＝０
次に、反復回数を示す制御変数ｉを１とおく（ステップ８０２）。そして、シンドロームｓi の値を用いてバーレカンプマッシ法により、ｉ−１番目の多項式Ｃi-1 （ｘ）の係数からｉ番目の多項式Ｃi （ｘ）の係数を求める（ステップ８０３）。ここでは、多項式Ｃi-1（ｘ）のｊ次の項の係数をｃj （ｊ＝１，２，．．．，Ｌ）として、以下のアルゴリズムにより多項式Ｃi （ｘ）の係数が求められる。
１）ｃｏｍｐｕｔｅ
【００６１】
【数１】
0004598711.tif 000002
【００６２】
２）Ｉｆ  ｄ＝０，ｔｈｅｎ
Ｃi-1 （ｘ）→Ｃi （ｘ）
ａ＋１→ａ
３）Ｉｆ  ｄ≠０  ａｎｄ  ２Ｌ＞ｉ−１，ｔｈｅｎ
Ｃi-1 （ｘ）−ｄｂ-1ｘa Ｂ（ｘ）→Ｃi（ｘ）
ａ＋１→ａ
４）Ｉｆ  ｄ≠０  ａｎｄ  ２Ｌ≦ｉ−１，ｔｈｅｎ
Ｃi-1 （ｘ）−ｄｂ-1ｘa Ｂ（ｘ）→Ｃi（ｘ）
ｉ−Ｌ→Ｌ
Ｃi-1 （ｘ）→Ｂ（ｘ）
ｄ→ｂ
１→ａ
次に、ｉと生成多項式の次数２ｔ＋１を比較する（ステップ８０４）。ｉ＜２ｔ＋１であれば、ｉ＝ｉ＋１とおいて（ステップ８０６）、ステップ８０３の計算を繰り返す。そして、ｉが２ｔ＋１に達すると、多項式Ｃ2t（ｘ）とＣ2t+1（ｘ）の係数を比較部５０５に出力する（ステップ８０５）。
【００６３】
図９は、比較部５０５の処理のフローチャートである。比較部５０５は、まず、多項式Ｃ2t（ｘ）の各係数と多項式Ｃ2t+1（ｘ）の各係数を比較し（ステップ９０１）、すべての係数が一致すれば、多項式Ｃ2t+1（ｘ）の係数を誤り位置多項式の係数として、チェーンサーチ実行部５０６に出力する（ステップ９０２）。いずれかの係数が一致しなければ、訂正失敗と判定して、データ保存部２３１に次の候補を要求する（ステップ９０３）。
【００６４】
図１０は、判定部５０７の処理のフローチャートである。判定部５０７は、まず、各シンドロームｓi （ｉ＝１，２，．．．，２ｔ，２ｔ＋１）の値をチェックし（ステップ１００１）、すべてのシンドロームｓiが０であれば、訂正不要と判定して、判定結果を誤り値計算部５０８に出力する（ステップ１００３）。
【００６５】
いずれかのシンドロームｓi が０でなければ、次に、各Ｃ（αj ）（ｊ＝０，１，．．．，ｎ）の値をチェックし（ステップ１００２）、Ｃ（αj ）＝０となるものがあれば、その位置ｊを誤り位置として、誤り値計算部５０８に出力する（ステップ１００４）。すべてのＣ（αj ）が０でなければ、訂正失敗と判定して、データ保存部２３１に次の候補を要求する（ステップ１００５）。
【００６６】
以上の実施形態では、磁気ディスク装置における誤り訂正について説明したが、本発明は、光ディスク装置等のストレージ製品や、通信システムにおける受信装置等にも適用可能である。また、本発明は、ＢＣＨ符号にも適用可能である。
【００６７】
また、ＥＣＣ符号器およびＥＣＣ復号器は、ハードウェアだけでなく、ソフトウェアにより実現することもできる。ソフトウェアにより実現する場合、例えば、図１１に示すような情報処理装置（コンピュータ）が用いられる。
【００６８】
図１１の情報処理装置は、ＣＰＵ１１０１、メモリ１１０２、入力装置１１０３、出力装置１１０４、外部記憶装置１１０５、媒体駆動装置１１０６、ネットワーク接続装置１１０７を備え、それらはバス１１０８により互いに接続されている。
【００６９】
メモリ１１０２は、例えば、ＲＯＭ（read only memory）、ＲＡＭ（random access memory）等を含み、処理に用いられるプログラムおよびデータを格納する。ＣＰＵ１１０１は、メモリ１１０２を利用してプログラムを実行することにより、符号化処理および復号処理を行う。
【００７０】
メモリ１１０２には、生成多項式の係数、シンドローム多項式の係数、誤り位置多項式の係数、復号候補のデータ列、誤り訂正後のデータ列等が、処理対象または処理結果のデータとして格納される。この場合、メモリ１１０２は、図５のデータ保存部２３１およびシンドローム保存部５０２としての役割を果たす。
【００７１】
図３のパリティ生成部３０１と、図５のシンドローム計算部５０１、シンドローム更新部５０３、誤り位置多項式計算部５０４、比較部５０５、チェーンサーチ実行部５０６、判定部５０７、および誤り値計算部５０８は、メモリ１１０２に格納されたプログラムに対応する。
【００７２】
入力装置１１０３は、例えば、キーボード、ポインティングデバイス等であり、ユーザからの指示や情報の入力に用いられる。出力装置１１０４は、例えば、ディスプレイ、プリンタ、スピーカ等であり、ユーザへの問い合わせや処理結果の出力に用いられる。
【００７３】
外部記憶装置１１０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。情報処理装置は、この外部記憶装置１１０５に、プログラムおよびデータを格納しておき、必要に応じて、それらをメモリ１１０２にロードして使用する。
【００７４】
媒体駆動装置１１０６は、可搬記録媒体１１０９を駆動し、その記録内容にアクセスする。可搬記録媒体１１０９は、メモリカード、フレキシブルディスク、光ディスク、光磁気ディスク等の任意のコンピュータ読み取り可能な記録媒体である。ユーザは、この可搬記録媒体１１０９にプログラムおよびデータを格納しておき、必要に応じて、それらをメモリ１１０２にロードして使用する。
【００７５】
ネットワーク接続装置１１０７は、ＬＡＮ（local area network）等の任意の通信ネットワークに接続され、通信に伴うデータ変換を行う。情報処理装置は、必要に応じて、プログラムおよびデータを外部の装置からネットワーク接続装置１１０７を介して受け取り、それらをメモリ１１０２にロードして使用する。
【図面の簡単な説明】
【００７６】
【図１】本発明の誤り訂正装置の原理図である。
【図２】記録再生装置の構成図である。
【図３】ＥＣＣ符号器の構成図である。
【図４】本発明の送信語列のフォーマットを示す図である。
【図５】本発明のＥＣＣ復号器の構成図である。
【図６】複数の復号候補の差異を示す図である。
【図７】シンドローム更新部の処理のフローチャートである。
【図８】誤り位置多項式計算部の処理のフローチャートである。
【図９】比較部の処理のフローチャートである。
【図１０】判定部の処理のフローチャートである。
【図１１】情報処理装置の構成図である。
【図１２】単一の復号候補を示す図である。
【図１３】複数の復号候補を示す図である。
【図１４】従来のＥＣＣ復号器の構成図である。
【図１５】情報列を示す図である。
【図１６】パリティ生成演算を示す図である。
【図１７】送信語列を示す図である。
【図１８】誤りを含む受信語列を示す図である。
【図１９】訂正された受信語列を示す図である。
【図２０】従来の送信語列のフォーマットを示す図である。
【符号の説明】
【００７７】
１１、２１、２２６  検出器
１２、２２、２３２  ＥＣＣ復号器
３１、２３１  データ保存部
３２  復号判定部
４１、５０１  シンドローム計算部
４２、５０４  誤り位置多項式計算部
４３、５０６  チェーンサーチ実行部
４４、５０８  誤り値計算部
１０１  データ格納手段
１０２  シンドローム計算手段
１０３  誤り位置多項式計算手段
１０４  判定手段
１０５  訂正手段
１０６  シンドローム格納手段
１０７  シンドローム更新手段
１０８  訂正手段
２０１  プリアンプ
２０２  リードチャネル
２０３  ハードディスクコントローラ
２１１  増幅器
２１２、２２７  ドライバ
２２１  サーマルアスペリティ検出器
２２２  可変利得増幅器
２２３  ローパスフィルタ
２２４  アナログ／デジタルコンバータ
２２５  有限インパルス応答フィルタ
２２８  記録補償器
２３３  ＲＬＬ復号器
２３４  ＣＲＣ復号器
２３５  ＥＣＣ符号器
２３６  ＲＬＬ符号器
２３７  ＣＲＣ符号器
３０１  パリティ生成部
５０２  シンドローム保存部
５０３  シンドローム更新部
５０５  比較部
５０７  判定部
５０８  誤り値計算部
１１０１  ＣＰＵ
１１０２  メモリ
１１０３  入力装置
１１０４  出力装置
１１０５  外部記憶装置
１１０６  媒体駆動装置
１１０７  ネットワーク接続装置
１１０８  バス
１１０９  可搬記録媒体
【図１】
0004598711.tif 000003
【図２】
0004598711.tif 000004
【図３】
0004598711.tif 000005
【図４】
0004598711.tif 000006
【図５】
0004598711.tif 000007
【図６】
0004598711.tif 000008
【図７】
0004598711.tif 000009
【図８】
0004598711.tif 000010
【図９】
0004598711.tif 000011
【図１０】
0004598711.tif 000012
【図１１】
0004598711.tif 000013
【図１２】
0004598711.tif 000014
【図１３】
0004598711.tif 000015
【図１４】
0004598711.tif 000016
【図１５】
0004598711.tif 000017
【図１６】
0004598711.tif 000018
【図１７】
0004598711.tif 000019
【図１８】
0004598711.tif 000020
【図１９】
0004598711.tif 000021
【図２０】
0004598711.tif 000022