(57)【特許請求の範囲】
【請求項１】
ビットのコード化された列における予め規定されたエラーを検出するためのパリティ検査行列を発生するための装置であって、
コンピュータ命令を記憶するメモリと、
前記コンピュータ命令を実行して、（ｉ）前記パリティ検査行列の列における要素に対する値を選択し、（ｉｉ）シンドロームを生成するために、前記予め規定されたエラーのうちの１つを前記選択された値で処理し、（ｉｉｉ）前記シンドロームの要素が前記予め規定されたエラーの１つを示す値を有する場合に、前記選択された値を前記パリティ検査行列の前記列に割当てるプロセッサとを含む、装置。
【請求項２】
処理することは、前記予め規定されたエラーの１つを前記選択された値で乗算することを含む、請求項１に記載の装置。
【請求項３】
前記要素が前記予め規定されたエラーの１つを示さない値を有する場合、前記プロセッサはコンピュータ命令を実行して、（ｉ）前記列における前記要素に対する異なった値を選択し、（ｉｉ）前記処理することおよび前記割当てることを前記異なった値を用いて繰返す、請求項１に記載の装置。
【請求項４】
前記プロセッサはコンピュータ命令を実行して、（ｉ）新しい予め規定されたエラーを選択し、（ｉｉ）前記新しい予め規定されたエラーを用いて前記選択すること、前記処理することおよび前記割当てることを繰返す、請求項１に記載の装置。
【請求項５】
前記選択すること、前記処理することおよび前記割当てることは、前記パリティ検査行列の最後の列から始まり、前記パリティ検査行列の第１の列まで列ごとに進められる、請求項１に記載の装置。
【請求項６】
前記予め規定されたエラーは、前記予め規定されたエラーが前記選択された値で処理される際にｎビット列（ｎ＞１）に含まれ、
前記プロセッサはコンピュータ命令を実行して、前記予め規定されたエラーが前記パリティ検査行列の異なった列で処理される場合に前記予め規定されたエラーを前記ｎビット列内で位置づけし直す、請求項５に記載の装置。
【請求項７】
前記列における要素に対する前記値は、前記列に対して可能であるビット組合せを含み、
前記選択することは、今度は、処理のために各々の可能なビット組合せを選択することを含む、請求項１に記載の装置。
【請求項８】
前記プロセッサはコンピュータ命令を実行して、前記パリティ検査行列からビットの列をコード化するための生成行列を定める、請求項１に記載の装置。
【請求項９】
予め規定されたエラーに対し、前記パリティ検査行列の列は
前記列における要素に対する値を選択することと、
シンドローム要素を生成するために、前記予め規定されたエラーを前記選択された値で処理することと、
シンドローム要素が前記予め規定されたエラーを示す値を有する場合に、前記選択された値を前記パリティ検査行列に割当てることとによって発生させられる、請求項５に記載の装置。
【請求項１０】
前記予め規定されたエラーは異なった長さを有する、請求項１に記載の装置。
【請求項１１】
ビットのコード化された列における予め規定されたエラーを検出するためのパリティ検査行列を発生する方法であって、
前記パリティ検査行列の列における要素に対する値を選択するステップと、
シンドロームを生成するために、選択された値で前記予め規定されたエラーのうちの１つを処理するステップと、
前記シンドロームの要素が前記予め規定されたエラーの１つを示す値を有する場合に、前記選択された値を前記パリティ検査行列の前記列に割当てるステップとを含む、方法。
【請求項１２】
前記処理するステップは、前記選択された値によって前記予め規定されたエラーの１つを乗算するステップを含む、請求項１１に記載の方法。
【請求項１３】
前記要素が前記予め規定されたエラーの１つを示さない値を有する場合に、
前記列における前記要素に対して異なった値を選択するステップと、
前記異なった値を用いて前記処理するステップおよび前記割当てるステップを繰返すステップとをさらに含む、請求項１１に記載の方法。
【請求項１４】
ビットのコード化された列における予め規定されたエラーを検出するためのパリティ検査行列を発生するためのコンピュータプログラムを記録するコンピュータ可読記録媒体であって、前記コンピュータプログラムはコンピュータが、
前記パリティ検査行列の列における要素に対する値を選択し、
シンドロームを生成するために、前記予め規定されたエラーのうちの１つを前記選択された値で処理し、
前記シンドロームの要素が前記予め規定されたエラーの１つを示す値を有する場合に、前記選択された値を前記パリティ検査行列の前記列に割当てるようにさせる命令を含む、コンピュータ可読記録媒体。
【請求項１５】
処理することは、前記予め規定されたエラーの１つを前記選択された値で乗算することを含む、請求項１４に記載のコンピュータ可読記録媒体。
【請求項１６】
前記コンピュータプログラムは、前記コンピュータが、
前記要素が前記予め規定されたエラーの１つを示さない値を有する場合に前記列における前記要素に対する異なった値を選択し、
前記異なった値を用いて前記処理することおよび前記割当てることを繰返すようにさせる命令をさらに含む、請求項１４に記載のコンピュータ可読記録媒体。
【請求項１７】
前記予め規定されたエラーは異なった長さを有する、請求項１４に記載のコンピュータ可読記録媒体。
【発明の詳細な説明】
【０００１】
【発明の背景】
この発明は、一般的にコード化ビット列におけるエラーを検出することに関する。
【０００２】
ディスクドライブなどのデータ記憶システムは、データを破損し得るさまざまなエラーが生じやすい。たとえば、媒体および電子ノイズにより磁気ディスクの内容が変わることがあり、これによってエラーが生じる。このようなエラーはデータ記憶システムに独特のものではない。むしろ、データを記憶し、検索しおよび／または送信するどんなシステム（たとえば通信システム）もこのようなエラーのおそれがある。
【０００３】
このため、コード化手法は、データエラーの検出を容易にし、場合によってはデータエラーの訂正をするよう開発された。このようなコード化手法の１つでは、データが記憶または送信される前にデータにパリティビットを付加する。デバイスはデータを受信し、パリティビットに基づいてデータにエラーが存在するかどうかを判定する。これらのコードを用いて効率よく検出できるのは１ビットエラーなど、ある特定の長さのエラーのみである。
【０００４】
これよりさらに一歩進んだ、データにおけるエラーを訂正するコード化手法では、多数のパリティビットが必要となる。しかしながら、用いられるパリティビットが多ければ多いほどデータビットのために用いることのできる記憶空間／帯域幅が小さくなる。
【０００５】
【発明の概要】
この発明の一局面は、さまざまなビット（１，０）組合せおよび長さを有する予め規定されたエラーを検出および／または訂正することに関する。特に、データにおけるパリティビットに基づいて予め規定されたエラーを検出するのに用いられるパリティ検査行列が発生する。パリティ検査行列からデータにパリティビットを付加するための生成行列が作り出される。
【０００６】
この局面で、パリティ検査行列の列における要素の値が選択される。予め規定されたエラーは、選択された値で処理されてシンドローム行列を生成する。選択された値は、シンドロームの要素が予め規定されたエラーを示す値を有する場合にパリティ検査行列の列に割当てられる。
【０００７】
予め規定されたエラーを表わすシンドローム要素を生成する値をパリティ検査行列に含めることによって、パリティ検査行列を用いてそのエラーを検出するのを確実にすることが可能となる。これを予め規定されたエラーのリストにおける各エラーに対して行なうことにより、リストにおけるすべてのエラーを検出できるパリティ検査行列が生成される。これは、異なった長さを有するエラーを含むどんなエラーのリストに対しても行なうことができる。コード化は、パリティ検査行列の簡単な変形を用いて実行できる。
【０００８】
また、この局面には１つ以上の以下の特徴／機能を含めてもよい。
選択された値を用いて予め規定されたエラーを処理することには、予め規定されたエラーを選択された値で乗算することが含まれていてもよい。選択された要素の値が予め規定されたエラーを表わすものではなかった場合、要素に対して異なった値が選択される。異なった値は予め規定されたエラーで処理され、新しいシンドロームを生成し、異なった値は、そのシンドロームが予め規定されたエラーを表わす値を有している場合にパリティ検査行列の列に割当てられる。また、新しい予め規定されたエラーを選択して前述のプロセスをその新しい予め規定されたエラーに対して繰返してもよい。
【０００９】
上述の選択すること、処理することおよび割当てることはパリティ検査行列の最後の列から始まり、列ごとにパリティ検査行列の第１の列まで進められる。予め規定されたエラーが選択された値で処理される場合、予め規定されたエラーはｎビット列（ｎ＞１）に含められる。予め規定されたエラーはパリティ検査行列の異なる列で処理された場合にはｎビット列における異なる場所に移動される。
【００１０】
列における要素に対する値はその列にとって可能であるビット組合せを含む。
列に対する値は、今度は処理のための可能なビット組合せの各々を選択することによって選択される。ビットの列をコード化するための生成行列はパリティ検査行列から定められる。論理ゲートを含むデコーダを用いてパリティ検査行列を発生する。
【００１１】
この発明の別の局面では、ビットのコード化された列における予め規定されたエラーは、予め規定されたエラーに基づいてパリティ検査行列を発生し、かつそのパリティ検査行列でビット列を処理して１つ以上の要素を有するシンドロームを生成することによって検出される。その後、シンドロームが予め規定されたエラーを示す要素を有するかどうかが判定される。
【００１２】
この局面には、また、１つ以上の以下の特徴／機能が含まれていてもよい。
パリティ検査行列の列における要素ｈi（ｉ≧１）は１≦ｊ≦Ｍに対し、以下の式を満たすよう選択される。
【００１３】
【数４】
0004663093.tif 000002
【００１４】
ここで、ｌはエラーにおけるビットの数、ｎはコード化ビット列におけるビットの数、Ｍはエラーの数、そしてｅはエラーにおけるビットである。パリティ検査行列の一部分は単位行列を含む。
【００１５】
別の局面において、ビットの列はコード化され、予め規定されたエラーの検出を可能にする。予め規定されたエラーを検出するパリティ検査行列が発生し、生成行列がパリティ検査行列から定められる。ビットの列はそこで、生成行列により処理される。
【００１６】
別の局面では、エラー検出コード（「ＥＤＣ」）を用いてコード化ビット列を訂正する。これは、コード化ビット列に対するデータを受け、データとデータに対応するビット組合せとの距離を定めることによって行なわれる。データを置換するため、エラー検出コードにより許容されかつ最小距離を有するビット組合せが選択される。ＥＤＣを用いてこの態様でエラー訂正を行なうことにより、エラー訂正は比較的数の少ないビットで実行される。
【００１７】
この局面にはまた、１つ以上の以下の特徴／機能が含まれてもよい。エラー検出コードでは、コード化ビット列におけるビットの数がある条件を満たす必要がある。この条件は、コード化ビット列が偶数個の１を有することであるかもしれない。
【００１８】
この簡潔な概要はこの発明の性質を迅速に理解できるように提示したものである。この発明の例示の実施例の詳細な説明を以下に挙げる。
【００１９】
【詳細な説明】
図１にはパーソナルコンピュータ（「ＰＣ」）１０が示される。ＰＣ１０は、ビット列をコード化および復号化するディスクドライブ１１と、ユーザに対し情報を表示する表示スクリーン１２と、データを入力する入力デバイス１４とを含む。ネットワークインターフェイス１５およびファックス／モデムインターフェイス１６もまた、ＰＣ１０をネットワークに接続するのに設けられる。
【００２０】
図２は、ディスクドライブ１１の構成要素を示す。ディスクドライブ１１の構成要素の中には、データ記憶ディスク１７、トランスデューサヘッド１９、プリアンプ２０、アナログ可変利得増幅器（「ＶＧＡ」）２１、フィルタ２２、アナログデジタル（「Ａ／Ｄ」）コンバータ２４、デコーダ２５、エンコーダ２６、第２の訂正段２７およびライタ２９がある。
【００２１】
データ記憶ディスク１７は、その記憶表面のそれぞれに規定される同心のデータ記憶チャネルを有する磁気ディスクである。これらのチャネル３０のクローズアップが図３に示される。データ記憶ディスク１７はディスクドライブ１１内部で回転させられ、その間データがそのチャネルから読出され／書込まれる。データ記憶ディスク１７は１つしか示されていないが、ディスクドライブ１１には２つ以上のディスクが含まれていてもよい。
【００２２】
トランスデューサヘッド１９は、データ記憶ディスク１７からデータを読出し、かつデータを書込む能力を有する巨大磁気抵抗ヘッド（「ＧＭＲ」）（または類似のデバイス）であってもよい。トランスデューサヘッド１９は、ディスク１７の記憶表面３１の上方に「飛行する」関係で関連づけられており、これは、データを読出し書込むために記憶表面３１に対して、かつその上方でトランスデューサヘッド１９が可動であることを意味する。
【００２３】
読取の間、ヘッド１９はディスク１７上の選択されたチャネルにごく近接して「飛行する」際に磁束遷移を感知する。これらの磁束遷移３２はプリアンプ２０に与えられる。プリアンプ２０は磁束遷移をミリボルト（ｍＶ）からボルト（Ｖ）へ増幅する電圧プリアンプである。結果生じるプリアンプされたアナログ信号（または「リード」信号）３４はＶＧＡ２１に与えられる。ＶＧＡ２１はさらに、リード信号３４を増幅して、結果生じる増幅されたリード信号３５をフィルタ２２に与える。
【００２４】
フィルタ２２は、増幅されたリード信号３５から実質的な方形波を発生するアナログフィルタ／等化器である。この目的のため、フィルタ２２は、信号３５が最終的にその源を発するディスク１７上のデータゾーンのデータ転送速度に従ってプログラムされる。結果生じるフィルタ処理された信号３６は高速Ａ／Ｄコンバータ２４内でサンプリングおよび量子化される。Ａ／Ｄコンバータ２４は信号３６から生じたデジタルデータ３７を出力する。データ３７はディスク１７上に記憶されたデータを表わし、「ソフト」である。これは、正確に１または０ではないかもしれない量子化された電圧値（たとえばゼロ値は実際に「０」である代わりに「０．２５」であり得る）をデータ３７が含むことを意味する。
【００２５】
ディスク１７上に記憶されるデータは、エラー検出コード（「ＥＤＣ」）を用いて記憶の前にコード化され、これは、データ３７もまたコード化されることを意味する。デコーダ２５はビタビ検出器を用いて、ＥＤＣに基づいてデータ３７におけるエラーを訂正し、かつシンボル間（「ＩＳＩ」）干渉を訂正する。スライサがＡ／Ｄコンバータ２４とデコーダ２５との間に含まれ、データ３７を「ハード」（これはデータ３７が１および０の値を含むことを意味する）にする代替の実施例では、デコーダは入来データにおけるエラーを検出するためだけにＥＤＣを用いる。
【００２６】
エンコーダ２６は第２の訂正段２７からデータ４０を受け、データ記憶ディスク１７に記憶される前にデータ４０にＥＤＣを付加する。基本的には、エンコーダは行列乗算を用いてパリティビットをデータ４０に付加する。復号化プロセスを以下に説明する。ライタ２９は、コード化データ４１をデータ記憶ディスク１７上のチャネルに書込むための回路である。
【００２７】
エンコーダ２６およびデコーダ２５は、論理ゲート（ＮＯＲ、ＡＮＤ、ＯＲ）などのハードウェアまたはソフトウェアで実現されてもよい。ハードウェア実現例は図２に示される。ソフトウェア実現例では、エンコーダ２６およびデコーダ２５の機能はプロセッサ４２およびメモリ４４を用いて実現される（図４を参照）。たとえば、メモリ４４は符号化アプリケーション４５および復号化アプリケーション４６を記憶し、これらはプロセッサ４２によって実行され、以下に説明する符号化および復号化プロセスを行なう。図４のディスクドライブにおいて２つ以上のプロセッサおよび／またはメモリを用いてもよい。
【００２８】
第２の訂正段２７はリードソロモン（Read-Solomon）エラー訂正デコーダであり、これはデコーダ２５によって訂正されなかったデータ３９におけるエラーを訂正する。第２の訂正段２７から、データはたとえばコンピュータ１０におけるコントローラ（図示せず）に出力され、これはデータを処理して表示スクリーン１２、ネットワークインターフェイス１５および／またはファックス／モデムインターフェイス１６に提供する。第２の訂正段２７はまた、外部源（コントローラなど）からデータを受け、そのデータをエンコーダ２６に与える。
【００２９】
Ｉ．エラー検出
エンコーダ２６は生成（または「Ｇ」）行列を用いてデータ４０をコード化し、デコーダ２５はパリティ検査（または「Ｈ」）行列を用いてコード化データ３７におけるエラーを検出／訂正する。特定的には、エンコーダ２６はデータ４０をＧ行列によって乗算しコード化データ４１を生成する。デコーダ２５が「ハード」のデータを受ける実施例では、デコーダ２５はコード化データをＨ行列によって乗算してその中のエラーを検出する。デコーダ２５が「ソフト」のデータを受ける実施例では、デコーダ２５はＨ行列から生成されるビタビ検出器を用いて、データにおけるエラーを訂正する。ビタビ検出器はデコーダ２５において生成されてもよく、デコーダ２５に設けられてもよい。Ｈ行列からのビタビ検出器の生成については、ジャック・Ｅ・ウルフ（Jack E. Wolf）による「格子（trellis）を用いる線形ブロックコードの有効な最尤度復号化」（“Efficient Maximum Likelihood Decoding Of Linear Block Codes Using A Trellis,” IEEE Transactions on Information Theory（1978年１月））に記載されるように周知であり、この内容はここに引用により援用される。
【００３０】
Ｇ行列はＨ行列から定められるため、Ｈ行列を発生するためのプロセスを最初に説明する。
【００３１】
Ａ．Ｈ行列の決定
Ｈ行列は、１つ以上の予め規定されたエラータイプを検出するよう設計される。これらのエラータイプは、期待されるチャネル出力と実際のチャネル出力との間の差を表わす（エラーがなければ、差は０となる）。各エラータイプは、その発生の確率に基づいて選択された１つ以上のビットの組合せである。たとえば、［１０１］、［１１］および［１］のエラータイプは、たとえばチャネルの特定の特性により、ある特定のメモリチャネルに対して確率が高いかもしれない。したがって、Ｈ行列はこれらのエラータイプのいずれを検出するようにも設計され得る。他のエラータイプも起こり得る。このようなエラーは、上述の第２の訂正段２７など、他の手段を用いて検出し訂正してもよい。
【００３２】
Ｈ行列はどんな数のエラータイプを検出するように設計してもよく、エラータイプはどんな数のビットを含んでいてもよい。しかしながら、この実施例は例によって最もよく示されるため、以下ではエラータイプ［１０１］、［１１］および［１］に対するＨ行列を発生することを説明する。以下、これらを「サンプル」エラータイプと称する。
【００３３】
第１に、Ｈ行列の大きさが定められる。この大きさは、ある部分では、各コード化ビット列におけるパリティビットの数に基づく。検出すべきエラータイプの数により、ビット列をコード化するのに（Ｇ行列によって）付加すべきパリティビットの数が示される。特定的には、パリティビットの数ｒ（ｒ≧１）は次の式で定められ、ここでＭは検出すべきエラータイプの数である。
【００３４】
ｒ＝ｌｏｇ2（Ｍ＋１）        （１）
Ｈ行列における行の数はパリティビットの数ｒに等しく設定される。Ｈ行列における列の数はコード化ビット列におけるビットの数ｎ（ｎ≧１）に等しく設定される。これは、行列乗算を可能にするため行なわれる（以下参照）。ｎの値は次の式により定められ、ここでｋ（ｋ≧１）はコード化されていないビット列におけるビットの数であり、ｒは上に規定したとおりである。
【００３５】
ｎ＝ｋ＋ｒ        （２）
サンプルエラータイプに対し、Ｍは３の値を有する。ｒの値は次の式によって定められる。
【００３６】
ｒ＝ｌｏｇ2（３＋１）＝２        （３）
サンプルエラータイプを検出するためのＨ行列は、よって、２つの行を有することとなる。たとえば、ｎが５であると仮定して（デコーダ２５をこの値でプログラムできる）、サンプルエラータイプを検出するためのＨ行列は以下に示すように２×５行列となり、ここで「ｘ」は未知の要素値を示す。
【００３７】
【数５】
0004663093.tif 000003
【００３８】
次に、Ｈ行列の要素が定められる。これらの値は、結果生じるＨ行列がｎの長さのビット列における予め規定されたエラータイプを検出できるように設定される。サンプルエラータイプに関しては、これは、５ビット列においてこれらのエラータイプが起こるどんな点においても［１０１］、［１１］および［１］をＨ行列が検出できることを意味する（たとえば、［０１０１０］、［１０１００］、［０００１］、［０１１００］、以下同様）。
【００３９】
図５には、予め規定されたエラータイプに基づいてＨ行列の要素に対する値を定めるためのプロセス４９が示される。プロセス４９はデコーダ２５によって「復号処理中に」（“on-the-fly”）実行されてもよく、その場合、デコーダ２５はデコーダ２５に与えられるエラータイプの新しいセットの各々に対しＨ行列を自動的に発生する。代わりに、プロセス４９を「オフラインで」実行してもよく、この場合、Ｈ行列はデコーダ２５の外部で発生し、その後デコーダ２５に与えられる（たとえばダウンロードされる）。
【００４０】
ここで、プロセス４９は、サンプルエラータイプを検出するのに用いられるＨ行列に関して説明される（等式４）。ステップ５０１において、プロセス４９はＨ行列の列を選択する。プロセス４９は、Ｈ行列の最後の列を選択して、Ｈ行列の第１の列まで列ごとに戻ってゆくという意味で再帰的である。
【００４１】
このように、最後の列（この場合は列５）から始めて、ステップ５０２において、プロセス４９は列５に対する列要素値を選択する。どの可能なビット組合せを選択してもよい。たとえば、Ｈ行列において列当り２つの要素があるため、各列に対する可能性のあるビット組合せは［０、０］、［０、１］、［１、０］および［１、１］である。プロセス４９は今度はこれらのビット組合せの各々を選択し、各ビット組合せがサンプルエラータイプのそれぞれに対するエラーを示す値を生成するかどうかをテストする。これらのビット組合せはどんな順序で選択してもよい。
【００４２】
Ｈ行列の列に対するビット値をテストするため、プロセス４９はエラー（たとえば［１０１］）を選択し（５０３）、このエラーをｎ長ビット列内に位置づけ、選択されたビット値で（エラーを有する）ｎ長ビット列を処理する（たとえば乗算する）（５０４）。結果生じる処理から、エラーを示す少なくとも１つの要素（たとえば１の値を有する要素）を有する行列（「シンドローム」と称される）が生成されれば、選択された値を現在の列に割当てることができる（が割当てる必要はない）（ｎ長の列がエラーを含むため、結果生じる値はエラーを示さなければならない）。結果生じる処理により、エラーを示さない要素値を有するシンドロームが生成された（たとえば、すべての要素が０の値を有する）場合、選択された値は現在の列に割当てることができない（そうでなければ、プロセス４９は実際にエラーがある場合にもエラーを示さないことになる）。
【００４３】
現在の例では、ｎは５であるため、各サンプルエラータイプは、サンプルエラーにおいて存在するいずれかの「１」の値を除いてすべて０の値を有する５ビット列内に位置づけられる。５ビット列内でのエラータイプの位置づけは、テストされる列に依存する。Ｈ行列の第１の列に対しては、各サンプルエラータイプの最上位ビット（「ＭＳＢ」）が５ビット列の最下位ビット（「ＬＳＢ」）として設定される。Ｈ行列の第２の列に対しては、各サンプルエラータイプは５ビット列において左へ「シフト」され、各エラータイプのＭＳＢが５ビット列における第２のＬＳＢとなるようにし、以下同様に左へ「シフト」される。
【００４４】
下の表１には、Ｈ行列の対応する列による乗算のための５ビット列内のサンプルエラータイプのそれぞれの位置づけが示され、列「５」はＨ行列の最後の列であり、列「１」はＨ行列の第１の列である。
【００４５】
【表１】
0004663093.tif 000004
【００４６】
たとえば、Ｈ行列の最後の列（列５）がステップ５０１において選択され、［０、０］列要素値がステップ５０２において選択され、サンプルエラータイプ［１０１］がステップ５０３において選択されたと仮定する。この場合、ステップ５０４において、表１の［１０１］および列５から）［００００１］が、［０、０］列要素値がその列５に付加されるＨ行列により処理される（たとえば乗算される）。この処理において、以下に示すように、Ｈの転置（ＨT）が用いられる。
【００４７】
【数６】
0004663093.tif 000005
【００４８】
結果生じるシンドロームの各要素がひと桁の数であることを確実にするために等式５の行列乗算においてガロア体二進演算が用いられる。ガロア体二進演算の規則は表２に挙げる。
【００４９】
【表２】
0004663093.tif 000006
【００５０】
等式５の行列乗算において、（エラーを有する）［００００１］の５ビット列におけるゼロはＨTにおける未知分（すなわちｘ）を打ち消す。この結果、シンドロームのための要素値として［１ｘ０、１ｘ０］または［０、０］が残る。この５ビット列［００００１］においてエラーが存在するため、要素値［０、０］はＨ行列の列５に付加することができない。これは、要素値［０、０］がシンドローム［０、０］を生じ、このシンドロームはエラーを示さない（ステップ５０５）ものであるためである。そこで、ステップ５０２において新しい列要素値が選択される。次に、ステップ５０２からステップ５０４がこれらの新しい列要素値を用いて列５に対して繰返される。
【００５１】
ステップ５０２において新しい要素値［０、１］が選択され、ステップ５０３においてエラー［１０１］が選択されると仮定する。この場合、ステップ５０４における乗算により［１、０］のシンドロームが生成される。このシンドロームは［１］の要素値を含み、これは［１０１］に対するエラーを示す（ステップ５０５）。しかしながら、［１、０］はすべてのサンプルエラータイプに対してテストされていないため（エラーがステップ５０６に残っている）、他のエラータイプもまたテストしなければならない。それぞれの他のサンプルエラー［１１］および［１］に対し、（表１からの）列５に対する５ビット列は［１０１］に対するものと同じである。よって、列要素値［０、１］、［１、０］および［１、１］はすべて、すべてのエラーに対しエラーを示すシンドロームを生成する。したがって、ステップ５０８において、Ｈ行列の列５に［０、１］、［１、０］および［１、１］のうちのいずれが割当てられてもよい。このように、プロセス４９では同じエラーのセットを検出するために２つ以上のＨ行列を生成することができる。
【００５２】
以下に述べる理由から、ステップ５０８において、プロセス４９は以下に示すようにＨ行列の列５に要素値［０、１］を割当てる。
【００５３】
【数７】
0004663093.tif 000007
【００５４】
すべてのエラータイプが列５に対するすべての列要素値に対して検査された後に、プロセス４９はステップ５０９に進む。Ｈ行列の列１から列４に対する要素値は未だ定められていないため、プロセス４９はステップ５０９からステップ５０１へ進み、ここでＨ行列における次の列を選択する。これは列４である。
【００５５】
列４に対し、ステップ５０２において［０、０］値が選択され、ステップ５０３においてサンプルエラータイプ［１０１］が選択される。このため、［０００１０］（列４におけるサンプルエラー［１０１］に対する表１からの５ビット列）がステップ５０４においてＨTによって乗算され、［０、０］値はＨの列４に付加される。
【００５６】
【数８】
0004663093.tif 000008
【００５７】
等式７に示されるように、要素値［０、０］に対する結果生じるシンドロームはすべてゼロを含む。すなわち、（エラーを有する）５ビット列におけるゼロはＨTにおけるｘを打ち消す。この結果、このシンドロームに対し、次が残る。
【００５８】
［１・０＋０・１、１・０＋０・０］＝［０、０］        （８）
ゼロ値はエラーを示さず（ステップ５０５）、かつエラーがビット列内に存在しているため、Ｈ行列の列４における要素値として［０、０］を用いることができない。したがって、ステップ５０２において新しい値が選択される。次に、ステップ５０３からステップ５０５がこれらの新しい値を用いて列４に対して繰返される。
【００５９】
ステップ５０２において［１、０］の新しい列要素値が選択され、かつステップ５０３においてサンプルエラータイプ［１０１］が選択されたと仮定する。この場合、ステップ５０４における乗算により、［０、１］のシンドロームが生成される。このシンドロームは［１］を含むが、これは［１０１］に対するエラーを示す（ステップ５０５）。しかしながら、列要素値［０、１］をステップ５０６により他のサンプルエラータイプ［１１］および［１］に対してテストしなければならない。これらの他のエラータイプに対し、表１からのそれらの列４の５ビット列が要素値［０、１］に対してテストされる。ビット列は双方とも、列要素値［０、１］に対して少なくとも１つの［１］の値を有するシンドロームを生じる。したがって、［０、１］はＨ行列の列４に割当ててもよい。同じプロセスに従って、［１、１］もまた列４に割当てることができるが、［０、１］は列４に割当てることができないことが定められる。
【００６０】
以下に述べる理由により、ステップ５０８においてプロセス４９は、以下に示すようにＨ行列の列４に［１、０］を割当てる。
【００６１】
【数９】
0004663093.tif 000009
【００６２】
Ｈ行列の列１から列３は（等式９）未だ定められていないため（すなわち、ステップ５０９において列が残っている）、プロセス４９はステップ５０１においてＨ行列における次の列を選択する。これは列３である。
【００６３】
列３に対し、ステップ５０２において［０、０］値が選択され、ステップ５０３においてサンプルエラータイプ［１０１］が選択される。このため、［００１０１］（列３におけるサンプルエラー［１０１］に対する表１からの５ビット列）がステップ５０４においてＨTによって乗算され、［０、０］要素値はＨの列３に付加される。
【００６４】
【数１０】
0004663093.tif 000010
【００６５】
等式１０の行列乗算において、（エラーを有する）［００１０１］５ビット列における０はＨTにおけるｘを打ち消す。これにより、シンドロームに対して［０、０］値が残る。ゼロ値はエラーを示さないため（ステップ５０５）、列要素値［０、０］はＨ行列の列３に用いることができない。ステップ５０２において新しい列要素値が選択される。これらの新しい値に対してステップ５０３からステップ５０５が繰返される。
【００６６】
残りの列要素値［０、１］、［１、０］および［１、１］のうち、［１、１］のみがすべての３つのサンプルエラーに対して［１］の値を有するシンドロームを生成する。したがって、［１、１］がステップ５０８において以下のようにＨ行列の列３に割当てられる。
【００６７】
【数１１】
0004663093.tif 000011
【００６８】
Ｈ行列の列１および列２は未だ定められていないため（すなわち、ステップ５０９において列が残っている）、プロセス４９はＨ行列における次の列を選択する。これは列２である。この後、Ｈ行列が完成するまで列２および列１に対して前述のプロセスが繰返される。
【００６９】
上述のように、所与のセットのエラータイプに対し２つ以上の行列が生成され得る。５ビットのコード化ビット列におけるサンプルエラータイプを検出するのに用いることのできる完全なＨ行列の１つは以下のとおりである。
【００７０】
【数１２】
0004663093.tif 000012
【００７１】
等式１２のＨ行列を調べることによって、Ｈ行列の最後の２×２（より概括的にはｒ×ｒ）ブロックが単位行列Ｉであることが明らかになり、ここでＩは次のとおりである。
【００７２】
【数１３】
0004663093.tif 000013
【００７３】
これは、どんな組織線形コードにも当てはまることであり、組織線形コードとは、パリティビットがビット列の一方端で分離されているか、そうでなければビット列における情報ビットと混ざり合っていないコードを意味する。
【００７４】
上記に照らして、組織線形コードに対するＨ行列を設計するには、Ｉr（ｒ個のパリティビットに対するＩ行列）をＨ行列の最後のｒ×ｒブロックに自動的に付加してもよい。このように、上述のプロセス４９を用いて計算する必要があるのは始めのｎ−ｒ列のみである。このことにより、処理時間が低減されＧの決定を簡略化することができる（以下参照）。
【００７５】
一般的には、組織線形コードに対し、Ｈ行列の始めのｎ−ｒ列の各要素ｈi（ｉ≧１）は、１≦ｊ≦Ｍに対し以下の式を満たし、ここでｌはエラーの長さ（ビットの数）であり、ｅはエラーにおけるビットであり、Ｍおよびｎは上に規定したとおりである。
【００７６】
【数１４】
0004663093.tif 000014
【００７７】
Ｂ．Ｇ行列の決定
一旦Ｈ行列が発生すると、Ｇ行列がＨ行列から定められる。Ｈ行列がデコーダ２５によって「復号処理中に」定められた場合、Ｇ行列もまたデコーダ２５により定められ、その後エンコーダ２６に与えられてもよい。代わりに、Ｇ行列は「オフラインで」定められ、エンコーダ２６に与えられてもよく、または、Ｇ行列がエンコーダ２６に与えられ、エンコーダ２６自体がＧ行列を定めてもよい。
【００７８】
１．組織線形コード
まず、組織線形コードに対するＧ行列決定について説明する。最後のｒ×ｒブロック５１がＩ行列であるｎ×ｒのＨ行列に対し（図６（ａ）を参照）、Ｇ行列は、始めのｋ個の列をＩ行列５２に設定し、Ｈ行列の始めのｋ個の列［Ｚ］５３の転置をとり、ＺT  ５４（ここでＺTはＺの転置である）をＧ行列の最後のｒ個の列として設定することによって定められる（図６（ｂ）を参照）。したがって、等式１２のＨ行列に対し、対応するＧ行列は以下のとおりである。
【００７９】
【数１５】
0004663093.tif 000015
【００８０】
２．非組織線形コード
非組織線形コードに対し、Ｇ行列は以下のように定められる。行列Ｑが以下の式を満たすような態様でｎ×ｒのＨ行列に基づいて規定され、ここでＩnおよびＩrはそれぞれ、ｎ×ｎ要素およびｒ×ｒ要素を備えた単位行列Ｉである。上と同様に、ｒはｎビットのコード化ビット列におけるパリティビットの数である。
【００８１】
【数１６】
0004663093.tif 000016
【００８２】
Ｑ行列に対しガウス消去が実行され、ＱにおけるＨ行列の最後のｒ個の列を単位行列Ｉrに等しくする。この結果を達成するよう行なわれるガウス消去の結果、Ｈ行列はＱにおけるＨsに変換される。Ｈsは（Ｈと同じ場所における）Ｑにおけるｎ×ｒ行列であり、その始めのｎ−ｒ列はパリティ行列Ｐとして規定され、その最後のｒ×ｒ列はＩrである。パリティ行列Ｐは、Ｇ行列を用いたコード化においてビット列に付加すべきパリティビットに対応する。
【００８３】
Ｑの右上のｒ×ｒブロックは行列Ａとして示され、Ｑの左下のｎ×ｎブロックは行列Ｂとして示され、Ｑの残った右下のブロックは用いられず、したがって行列ｘとして示される。これは以下の等式１７に示される。
【００８４】
【数１７】
0004663093.tif 000017
【００８５】
ここで、定義によれば、
Ｈs＝Ａ・Ｈ・Ｂ        （１８）
である。
【００８６】
Ｇ行列はＩ行列、Ｐ行列およびＢ行列から以下のように定められる。
Ｇ＝｜ＩkＰT｜・ＢT        （１９）
ここでｋはコード化されていないビット列におけるビットの数であり、このため、以下の式が得られる。
【００８７】
Ｇ・ＨT＝［０］        （２０）
また、等式１６から等式２０までを組織線形コードに対するＧ行列を定めるのに用いてもよい。しかしながら、このプロセスは、図６（ａ）および図６（ｂ）に関連して上に説明したものより計算が集約的なものである。
【００８８】
ここで、以下に対してＧ行列を定める一例が示される。
【００８９】
【数１８】
0004663093.tif 000018
【００９０】
Ｑ行列は以下のように規定される。
【００９１】
【数１９】
0004663093.tif 000019
【００９２】
ＱにおけるＨの最後の３つの列においてＩ3行列を得るためのガウス消去は、Ｑの第３の列および第５の列を交換することによって行なわれ、次の式が得られる。
【００９３】
【数２０】
0004663093.tif 000020
【００９４】
次に、Ｑ1の第３の行がＱ1の第１の行に付加され、次の式が得られる。
【００９５】
【数２１】
0004663093.tif 000021
【００９６】
最後に、Ｑ2の第３の行がＱ2の第１の行に付加され、次の式が得られる。
【００９７】
【数２２】
0004663093.tif 000022
【００９８】
等式２５に示されるように、Ｑ3の行１から行３、列３から列５に規定される行列はＩ3行列である。
【００９９】
等式２５から、以下の等式２６のようにＢ行列を抽出することができ、ここでは等式２７のようになる。
【０１００】
【数２３】
0004663093.tif 000023
【０１０１】
また、等式２５から、以下の式が得られる。
【０１０２】
【数２４】
0004663093.tif 000024
【０１０３】
それぞれ等式２８および等式２７におけるＰTおよびＢTに対する行列から、Ｇ行列が以下のように定められる。
【０１０４】
【数２５】
0004663093.tif 000025
【０１０５】
ＩＩ．エラー訂正
この実施例では、ＥＤＣを用いてコード化ビット列のエラー訂正を行なった。
これは、エラー訂正コード（「ＥＣＣ」）よりもＥＤＣが必要とするビットは少なく、よって占める記憶空間および帯域幅がより小さいため有利である。
【０１０６】
用いることのできるＥＤＣの１つは、ビット列をコード化するのにそのビット列に付加されるパリティビットの数に基づいている。このＥＤＣでは、すべてのコード化ビット列が偶数個の１を有する必要がある。したがって、パリティビットは、ビット列がこの条件を満たすことを確実にするように各ビット列に付加される。たとえば、コード化されていないビット列が２ビット長であると仮定する。第３のパリティビットはそのビット列をコード化するために各２ビット列に付加され、これによってビット列を３ビット長にする。２ビット列における１の数が偶数である場合、その２ビット列に０が付加され、これによって１の数を偶数に保つ。２ビット列における１の数が奇数である場合、２ビット列に１を付加することによって１の数を偶数にする。
【０１０７】
エラー検出器において、各ビット列における１の数は、その数が奇数であるか（その場合ビット列にエラーが存在する）または偶数であるか（この場合、そのビット列にはエラーが存在しない可能性が高い）を判定するために検査される。
図７は、このようなＥＤＣを用いてエラー訂正を行なうプロセス５０を示す。このプロセスは「ソフト」データを受けるデコーダにおいて実行されてもよい。
【０１０８】
ステップ７０１において、プロセス５０はデータ記憶媒体から読出された生データを受ける。このデータは上述のように増幅されてもよくフィルタ処理されてもよい。この例では、このデータが０．１Ｖ、０．９Ｖおよび０．３Ｖの電圧値を有すると仮定する。ステップ７０２において、プロセス５０は、電圧値と許容可能なビット組合せとの間の「距離」を定める。ここで「距離」というのは、電圧値と０または１の離散値との差の総和を意味する。ここで「許容可能な」ビット値とは、ＥＤＣにより許容されるビット列組合せを意味し、すなわち、偶数個の１を有するビット列は許容され、奇数個の１を有するビット列は許容されない。許容不可能なビット組合せについては距離を定める必要はないが、これは、定義により、こうしたビット組合せが誤ったものとなるためである。
【０１０９】
したがって、たとえば、０．１、０．９および０．３とビット組合せ［０１１］との距離は以下のように定められる。
【０１１０】
0004663093.tif 000026
［０００］、［１０１］および［１１０］である残りの許容可能なビット組合せ（この例では、偶数個の１を有するビット組合せを意味する）に対する距離は以下のとおりである。
【０１１１】
［０００］＝１．３
［１０１］＝２．５
［１１０］＝１．３        （３１）
ステップ７０３において、最小距離を有する許容可能なビット組合せが選択されデータを置換する。前述の例では、［０１１］が最小距離（０．９）を有するため、これが０．１、０．９および０．３の代わりに用いられる。このプロセスは残りのコード化ビット列に対して繰返される。
【０１１２】
この発明は上述の実施例に記載されるハードウェア、ソフトウェアまたは特定の例に限定されない。図５は単に、この発明を実施する上での１つのやり方を例示することを意図しているにすぎない。たとえば、図５のステップは、特に乗算のためにエラーおよび要素値を選択することに関連するステップについては、順番を並べ替えてもよい。同様に、特定の実現例に応じてプロセス中により少ない数のステップが含まれてもよく、さらなるステップを含めてもよい。たとえば、図５のプロセス４９は、各列に対し、一旦その列に対する容認可能なビット値が定められると停止してもよい。
【０１１３】
この発明を用いて、たとえばマルコフチャネル、ギルバート・エリオット（Gilbert-Elliot）チャネルおよびＡＲＱ（自動再送要求）チャネルなどの、どんな記憶媒体において、バーストエラーを含むエラーを検出し訂正してもよい。しかしながら、この発明はデータ記憶システムとの使用に限定されるものではない。
実際、この発明はエラーが生じ得るいかなるシステムにおいてエラーを検出し訂正するのに用いられてもよい。たとえば、この発明は、通信システムおよび衛星送信システムなどにおいてビットエラーを検出し訂正するために受信機によって用いられてもよい。また、この発明は上記のセクションＩＩに記載されるＥＤＣに限定されるものではない。どんなＥＤＣを用いてもよい。
【０１１４】
ここに記載されない他の実施例もまた上記の特許請求の範囲に含まれる。
【図面の簡単な説明】
【図１】  コンピュータの斜視図である。
【図２】  コンピュータに含まれるディスクドライブのブロック図である。
【図３】  ディスクドライブにおけるデータ記憶ディスクの上面図である。
【図４】  ディスクドライブの代替の実施例のブロック図である。
【図５】  エラー検出（パリティ検査）行列を定めるためのプロセスを示すフロー図である。
【図６】  パリティ検査行列およびそこから定められる生成行列を示すブロック図（ａ）および（ｂ）である。
【図７】  エラー検出コードを用いてエラー訂正を行なうためのプロセスを示すフロー図である。
【符号の説明】
１０  パーソナルコンピュータ、１１  ディスクドライブ、１２  表示スクリーン、１４  入力デバイス、１５  ネットワークインターフェイス、１６  ファックス／モデムインターフェイス、１７  データ記憶ディスク、１９  トランスデューサヘッド、２０  プリアンプ、２１  アナログ可変利得増幅器、２２  フィルタ、２４  アナログデジタルコンバータ、２５  デコーダ、２６  エンコーダ、２７  第２の訂正段、２９  ライタ、３０  チャネル、３２  磁束遷移、３４  リード信号、３５  増幅されたリード信号、３６  フィルタ処理された信号、３７  デジタルデータ、４０  データ、４１  コード化データ、４２  プロセッサ、４４  メモリ、４５  符号化アプリケーション、４６  復号化アプリケーション、４９  プロセス、５０  プロセス。
【図１】
0004663093.tif 000027
【図２】
0004663093.tif 000028
【図３】
0004663093.tif 000029
【図４】
0004663093.tif 000030
【図５】
0004663093.tif 000031
【図６】
0004663093.tif 000032
【図７】
0004663093.tif 000033