(57)【特許請求の範囲】
【請求項１】
線形ブロック誤り訂正符号のために信頼できないワードをデコードするシステムであって、
信頼できない符号ワードの各記号に対し共通の信頼度尺度を有するハードデコーダと、
前記ハードデコーダから有用な結果が得られ得るか否かを判断する論理と、
前記信頼できない符号ワードの各記号ごとに独自の信頼度値を有するソフト判断デコーダとを含む、システム。
【請求項２】
前記判断を行なう前記論理は、前記信頼できない符号ワードにおける誤りに対応する信頼度しきい値を計算するプロセッサをさらに含む、請求項１に記載のシステム。
【請求項３】
前記判断を行なう前記論理は、
前記ハードデコーダからの総信頼度を決定する論理と、
前記ハードデコーダの総信頼度を前記信頼度しきい値と比較することにより、前記ハードデコーダから有用な結果が得られ得るか否かを判断する比較論理とをさらに含む、請求項１に記載のシステム。
【請求項４】
前記判断を行なう前記論理は、信頼度しきい値の組を決定する論理をさらに含む、請求項１に記載のシステム。
【請求項５】
前記判断を行なう前記論理は、前記ハードデコーダからの総信頼度を決定する論理をさらに含む、請求項４に記載のシステム。
【請求項６】
前記信頼できない符号ワードにおける誤りの数に基づいて誤りしきい値を選択するセレクタと、
前記総信頼度を前記しきい値信頼度と比較することにより、前記ハードデコーダが有用な結果を与え得るか否かを判断する論理とをさらに含む、請求項５に記載のシステム。
【請求項７】
第２のデコーダはソフト判断デコーダである、請求項１に記載のシステム。
【請求項８】
第２のデコーダは誤りおよび消去デコーダである、請求項１に記載のシステム。
【請求項９】
前記信頼できない符号ワードは線形ブロック符号によって発生される、請求項１に記載のシステム。
【発明の詳細な説明】
【０００１】
【背景】
この発明は誤り訂正符号技術に関する。誤り訂正コード技術は、デジタルシステムにおいては、デジタルデータにおける誤りを訂正し検出するために用いられる。このような技術は、特に、製造欠陥などのため比較的高い誤り率を有し得る磁気ディスクとともに用いられる。いくつかのタイプの誤り訂正技術が公知となっている。１つのタイプの誤り訂正技術はいわゆる「ブロック符号」を用いる。ブロック符号の一例として、いわゆる「リードソロモン（ＲＳ）符号」がある。リードソロモンブロック符号のようなブロック符号はデータ記号で動作する。データ記号は２進ビットデータのベクトルである。記号は、ビットをワードの群に対する特定のビット位置でベクトルにグループ分けすることによって生ずる。ブロック符号をディスクドライブにおいて用いると、データ記号の列をディスク上に記録する前に、その列が数学的にエンコードされて、誤り訂正コード記号を発生させ、それらがデータ記号に付加されることにより、符号ワードが形成される。これらの符号ワード、つまりデータ記号および誤り訂正符号記号はそのディスク上に記憶される。その記憶されたデータがそのディスクから検索されると、それら符号ワードが数学的にデコードされて、デコードされた符号ワードを形成する。
【０００２】
データ記号における複数のデータ誤りの訂正は、そのようなデータ誤りの数が、そのアルゴリズムが設計された誤りの最大数を超えない場合に行なわれ得る。現在、ほとんどのデコードスキームはいわゆる「ハードデコード」を用いる。ハードデコードとは、信頼できない符号ワードの各記号が各他の記号と全く同じ信頼度尺度を有する技術である。便宜上、一般に各記号の信頼度尺度は１の値を割当てられる。第２の技術である、いわゆる「ソフト判断デコード」は、各記号毎に独自の信頼度尺度を用いる。各記号は０と１との間の独自の値または任意の範囲の値を割当てられる。このソフト判断デコードアルゴリズムは、より多くの誤りを訂正できしたがってより堅牢でありかつより高性能ではあるが、非常に複雑になる傾向がある。したがって、ソフト判断デコードの実用的な実現例は低速であり、または十分なハードウェアを用いて速度を増大させる場合には費用がかかりしたがって非実用的となることが多い。
【０００３】
【発明の概要】
この発明のある局面に従うと、信頼できない符号ワードをデコードするための方法および装置は、その符号ワードの各記号に対し共通の信頼度尺度を有するデコーダでその信頼できない符号ワードをデコードすることと、有用な結果が第１のデコーダから得られ得るかどうかを判断することとを含む。有用な結果が得られ得ない場合には、その信頼できない符号ワードの各記号毎に独自の信頼度値を用いる第２のデコーダでその信頼できない符号ワードをデコードする。
【０００４】
以下の利点のうち１つ以上が与えられる。ハードデコードはたいていの誤り出現に対して用いられ得、より低速なソフト判断デコードはより頻繁でない出現に対して用いられ得る。これによって、全体の性能が改善される。選択肢として、このハードデコードは、その最大量よりも少ない誤りを処理するよう設計され得る。換言すると、その実現されるハードデコーダは、選択されたハードデコードアルゴリズムの誤り訂正能力を十分にまたは完全に実現する必要はない。このハードデコードは、最もありそうな数の誤り、たとえば１記号につき１つまたは２つの誤りを訂正し、それほどありそうにないより大きな数の誤りはソフト判断デコードに任せるだけでよい。通常のハードデコーダ実現例によって訂正可能な記号誤りのわずか数分の１を訂正することによって、ハードウェアを節約し、より頻繁ではないがより大きな数の誤りはソフト判断デコードに訂正させることによって、全体的により高速となる。
【０００５】
【詳細な説明】
ここで図１を参照して、コンピュータシステム１０は、プロセッサ１２と、主メモリ１４と、記憶サブシステム１５を含み、それらはすべてコンピュータバス１６を介して結合される。記憶サブシステム１５は、バスアダプタ１８と、記憶バス１９と、記憶装置２０とを含む。記憶装置２０の好ましい例として磁気ディスクがある。他の例には、光ディスク、磁気テープ、および固体ディスクがある。記憶装置２０は誤り訂正エンコーダ２２と誤りデコーダ回路３０とを含む。
【０００６】
次に図２を参照して、記憶サブシステム１５の一部が誤り訂正符号エンコーダ２２を含んで示されている。この誤り訂正符号エンコーダ２２は、バスアダプタ１８から入力データを与えられて、誤り訂正符号記号を発生させる。これら誤り訂正符号記号はデータ記号に結び付けられるかまたは関連付けられるものであり、ディスクインターフェイス２３に与えられて、ディスクへの書込動作においてディスクドライブ２６（図１）上に記憶される。ディスクからの読出動作においては、データ記号および検査記号が記憶装置２０から検索される。データ記号はディスクインターフェイス２３および誤り訂正デコーダ回路３０に与えられる。誤り訂正デコーダ回路３０は、検索されたデータ記号から誤り訂正符号記号の組を発生させる。発生された記号は、記憶装置２０から検索された誤り訂正検査記号と比較される。誤りデコーダ回路３０はそのような誤りを、それらが誤りデコーダ３０の誤り訂正能力を超えない限りにおいて、訂正する。誤りデコーダ回路３０は、信頼できないワードをデコードするハードデコーダおよびソフト判断デコーダと、そのデコーダがハードデコードまたはソフト判断デコードのいずれを用いるべきかを判断する判断論理とを含む。
【０００７】
次に図３を参照して、線形ブロック誤り訂正符号のためのデコーダ３０は、ある数の周知のハードデコードアルゴリズムのうちの任意のものに従って動作するハードデコーダ３２を含む。このハードデコーダ３２は、高速のハードデコード技術を実現して主要技術を与えることにより、デコーダ３０に与えられる信頼できない符号ワードｃ（ｊ）をデコードする。このデコーダ３０はさらに判断論理３３を含む。この判断論理３３は、ハードデコーダ３２からの出力を調べることによって、そのハードデコーダからのその出力がデコーダ３０からの出力として受入れられ得るかどうかを判断する。このハードデコーダからの出力が受入れられ得ない場合には、判断回路３３によってソフト判断デコードプロセスが呼出されデコーダ３０からそのデコードされた出力が与えられる。
【０００８】
信頼できないワードｃ（ｊ）はハードデコーダ３２に与えられる。この信頼できないワードｃ（Ｊ）から、ハードデコーダ３２は、ｅ＜ｄ／２として、ｂ（１）、ｂ（２）、…ｂ（ｅ）として表現されるｅ個の非０記号の誤りパターンを発生させる。この誤りパターンｂ（１）、ｂ（２）、…ｂ（ｅ）は誤りパターン信頼度計算回路３４に与えられる。回路３６は、その信頼できないワードにおける誤りの数を、ハードデコーダ３２によって決定されるように記憶する。
【０００９】
信頼できない符号ワードｃ（ｊ）は、それらに関連付けられ、チャネルプロセッサ（図示せず）によって発生されるかまたは与えられる対応の信頼度ｒ（ｊ）を有する。これら信頼度尺度の値は誤りパターン記号ｂ（ｊ）とともに誤りパターン信頼度回路３４に与えられる。この誤りパターン信頼度回路３４によって、誤りパターン記号ｂ（ｊ）の信頼度が、ｓ（ｊ）を、ｂ（ｊ）に関連付けられる位置に対する信頼度として、以下のように数え上げられる。
【００１０】
【数１】
0004486198.tif 000002
【００１１】
判断論理３３は、ハードデコーダ３２からの出力において与えられる誤りの数（たとえばｂ（ｊ）項の数）を計数する回路３６を含む。計数された誤りの数に基づいて、セレクタ回路４０が複数の信頼度しきい値のうちの１つを選択する。これら信頼度しきい値は信頼度しきい値プロセッサ３８によって決定される。この信頼度しきい値プロセッサ３８は、信頼度入力ｒ（ｊ）で動作することにより、値ｅ（ｍａｘ）に従って出力しきい値Ｔ（ｄ−１）、Ｔ（ｄ−２）、…Ｔ（ｄ＿ｍａｘ−１）およびＴ（ｄ−ｅ＿ｍａｘ）の組を発生させる。したがって、これらしきい値のすべてが、信頼できない符号ワードに出現し得る誤りの数に基づいて計算または決定される。これらのしきい値は、セレクタ４０によって、各信頼できない符号ワードごとに選択される。
【００１２】
選択肢として、ハードデコーダによって与えられるｅの最大値ｅ＿ｍａｘは、（ｄ−１）／２よりもはるかに小さく設計され得る。換言すれば、その実現されるハードデコーダは、選択されるハードデコーダアルゴリズムの誤り訂正能力を十分または完全に実現する必要はなくてもよい。ハードデコーダは、最もありそうな誤り数、たとえば１つの記号につき１つまたは２つの誤りを訂正し、それほどありそうにないより大きな誤り数はソフト判断デコーダに任せるだけでよい。通常のハードデコーダ実現例によって訂正され得る記号誤りのほんの何分の１かを訂正することによって、ハードウェアを節約し、それほど頻繁でないより大きな誤り数はソフト判断デコーダに訂正させることによって、全体的により高速となる。ハードデコーダ３２が誤りパターンを与えない場合には、信頼度尺度Ｓが非常に大きな数に任意に設定される。これによってソフト判断デコードアルゴリズムが確実に呼出される。
【００１３】
選択された信頼度しきい値４０を誤りパターン信頼度出力Ｓと４２で比較することによって、ハードデコーダ３２の出力がデコーダ３０の出力として受入れられ得るかどうか、またはソフト判断デコードプロセス４４を呼出してデコーダ３０からの出力を与えるべきかが判断される。信頼度尺度Ｓが選択されたしきい値（Ｔ）以下である場合は、そのハードデコードパターンが最終のデコーダパターンとして受入れられる。そうでない場合には、より時間がかかるかまたはより複雑なソフト判断デコードアルゴリズムを呼出して最終的なデコードされた誤りパターンを発生させる。
【００１４】
Ｓがしきい値以下である場合にはハードデコーダ出力はソフト判断デコード出力と絶対に同じであるような態様でしきい値を計算することが重要である。逆に、Ｓがしきい値よりも大きい場合には、ハードデコーダ出力誤りパターンはソフト判断出力と同じであってもなくてもよい。このようなしきい値を発生させるためのアルゴリズムであれば、任意のものを用いてそれらしきい値を計算してもよいが、下に２つの例を挙げることにする。
【００１５】
次に図４を参照して、しきい値を発生させる処理６０を示す。この処理６０（一般記憶処理と称される）は記憶素子６２を信頼度値ｒ（ｊ）の各々に割当てる。まず、すべての値ｍ（ｊ）を１、つまり最も高い信頼度値に等しくセットする。この一般記憶処理６０では、信頼度値の順序付け６４が行なわれるが、これは、記憶素子における最初の記憶された値より小さい信頼度を探すサーチによって信頼度値を減ずることにより行なわれる。そのような値が発見されると、ｍ（１）が最も信頼性の低い尺度を記憶する状態で、順序正しく分類されるｄ−１の記号の最低信頼度尺度として、信頼度が記憶される。
【００１６】
各新たなｒ（ｊ）に対し、
ｒ（ｊ）＞ｍ（ｄ−１）である場合にはなにもせず；
そうでない場合にはｒ（ｊ）とｍ（ｄ−１）、ｍ（ｄ−２）、…との比較を
ｒ（ｊ）＜ｍ（ｋ）かつｒ（ｊ）＞ｍ（ｋ−１）となるまで行ない
次いでｍ（ｄ−１）＝ｍ（ｄ−２）
ｍ（ｄ−２）＝ｍ（ｄ−３）
…
ｍ（ｋ＋１）＝ｍ（ｋ）
ｍ（ｋ）＝ｒ（ｊ）をセットする。
【００１７】
これらの値が順序正しく記憶された後、しきい値の決定６６が行なわれるが、これは、ｋ＝ｄ−ｅｍａｘ、…ｄ−２、ｄ−１で記憶素子ｍ（１）〜ｍ（ｋ）の各々において値を単に合計することによって行なわれる。
【００１８】
この処理は有用なしきい値を発生させるが、それは、ハードデコーダ３２によって誤りパターンがｅ個の誤りおよび信頼度尺度Ｓを伴って発生されるからである。別の誤りパターンが以下に示されるが、これは少なくとも（ｄ−ｅ）の非０記号を含む。どのｄ−ｅの非０記号も少なくともＴ（ｄ−ｅ）の信頼度尺度を有する。この信頼度尺度Ｓがしきい値以下である状態では、Ｓより小さい信頼度尺度を伴う誤りパターンを発見することは不可能である。したがって、Ｓがしきい値未満である場合、ハードデコーダ３２出力は最善のソフト判断出力と同じとなり、したがって、ハードデコーダからの出力を回路３０からの出力として選択することは適切である。
【００１９】
次に図５を参照して、信頼度しきい値を決定するための代替処理７０（部分記憶処理）では、部分記憶の割当て７２を行なうことによって最も信頼性が低い記号の一部のみを記憶することが含まれる。この方策では、わずかｋ個の記憶素子を用いることにより、１とｄ−２との間の任意の値を有し得るｋ個の最低信頼度尺度を記憶する。ｊ≦Ｔの場合、しきい値決定７４が以下のように行なわれ、ｊ＞Ｋの場合、しきい値決定７６が以下のように行なわれる：
【００２０】
【数２】
0004486198.tif 000003
【００２１】
換言すれば、図４の一般記憶処理６０の値ｍ（Ｋ＋１）、ｍ（Ｋ＋２）、…ｍ（ｄ−１）は、この部分記憶処理７０ではすべて同じ値ｍ（Ｋ）に置き換えられる。この部分記憶処理７０のしきい値は、ｊ≧ＫであるＴ（ｊ）のしきい値に対しては一般記憶処理６０のしきい値と同一である。ｊ＞Ｋの場合には、この部分記憶処理７０のしきい値は一般記憶処理６０に見られるしきい値よりも小さい。この結果、この部分記憶処理７０を用いて、より多くのハードデコーダ誤りパターンが拒絶される。しかしながら、Ｋの値は正確に選ばれる。ｍ、ｋおよびｊの値はｍ（Ｋ）の値に非常に近くあるべきである。この場合、この部分記憶処理７０におけるすべてのしきい値の値は実際には図４の一般記憶処理６０に示されるものと同じである。しかしながら、この部分記憶処理７０は、特にＫの値が小さい場合には、比較および挿入動作がより少ない。
【００２２】
ハードデコードにおいては、信頼できない符号ワードの各記号は全く同じ信頼度尺度を有する。便宜上、各記号のこの信頼度尺度に値１を割当てる。しかしながら、ソフト判断デコードでは、各記号に対する信頼度尺度は、上述したように、独自の値、たとえば０と１との間または一般には任意の範囲の値を割当てられる。ハードデコードは、したがって、より全般的なソフト判断デコード処理の特別な場合である。有用とするために、ソフト判断デコードでは、信頼度尺度は、記号の組の信頼度がその組の個々の記号の信頼度から得られ得るという特性を有さなければならない。したがって、Ｒが記号の組｛ａ（１）、ａ（２）、…、ａ（ｅ）｝の信頼度尺度であり、かつｒ（ｊ）がａ（ｊ）の信頼度尺度である場合、２つの単純な関係が得られる。
【００２３】
【数３】
0004486198.tif 000004
【００２４】
これら２つの関係は対数演算によって関係付けられる。ここで用いられるとおりでは、等式１を用いて信頼度尺度を計算する。この信頼度尺度はブロック符号で動作する。ブロック符号は３つのパラメータ（ｎ，ｋ，ｄ）で特徴付けられ、ｎは符号ワードごとの記号の総数であり、ｋは符号ワードごとの情報記号の数であり、ｄは任意の２つの信頼できない符号ワード間の最小ハミング距離である。好適なハードデコードアルゴリズムは、信頼できない符号ワードにおいて、（ｄ−１）／２までの、およびそれを含む、記号誤りを訂正し得る。
【００２５】
ここに記載される技術は、（ｄ−１）／２またはそれより少ない記号誤りを含む独自の誤りパターンを発生させることができる少なくとも１つの公知のハードデコードアルゴリズムを有するすべての線形ブロック（ｎ，ｋ，ｄ）符号に適用可能である。線形ブロック符号には、２つの符号ワードの加算の結果別の符号ワードがもたらされるという特性がある。符号ワード（ａ（１）、ａ（２）、…、ａ（ｎ））と符号ワード（ｂ（１）、ｂ（２）、…、ｂ（ｎ））との加算は（ａ（１）＋ｂ（１）、ａ（２）＋ｂ（２）、…、ａ（ｎ）＋ｂ（ｎ））と定義され、＋は、符号記号ａ（ａ）およびｂ（ｊ）が上に規定される下層フィールドに対するフィールド加算を示す。
【００２６】
いくつかの例を挙げれば十分であろう。以下の２つの例は、ハードデコードおよびソフト判断デコードの効果を例示する目的を果たすものである。
【００２７】
例１
リードソロモン（７，３，５）符号ワードを
（００１，０１１，１００，１１０，１１０，００１，１００）にし、
信頼できない符号ワードを
（０００，０１１，１０１，１００，１１０，００１，１００）にし
信頼度尺度を
（０．１，０．３，０．２，０．３，０．５，０．９，０．９）にする。
【００２８】
ここで用いられるとおりでは、ｎ個の要素からなる集合（ｃ（１），ｃ（２），…，ｃ（ｎ））に対する表記は、符号ワード、信頼できない符号ワード、または誤りパターンであり、記号ｃ（ｊ）がコンマ（，）によって分離され；ｎ個の要素からなる集合（ｒ（１），ｒ（２），…，ｒ（ｎ））はｃ（ｊ）に対する信頼度尺度ｒ（ｊ）を伴う信頼度尺度である。ｃ（ｊ）はｍ個の２進ビット（例１ではｍ＝３）を含む記号であり、ｒ（ｊ）は実数である。この例では、０．０が記号に対する最も信頼性の低い尺度であり、１．０が最も信頼性の高い尺度である。
【００２９】
記号単位で符号ワードおよび信頼できない符号ワードの比較、つまり排他的論理和演算を行なうことによって、以下の誤りパターンが生ずる。
【００３０】
（００１，０００，００１，０１０，０００，０００，０００）
この誤りパターンにおいては、すべてが０である記号は、その特定の記号が正しいことを意味する。非０記号はその記号の誤り値を記す。したがって、上記の誤りパターンでは３つの誤りがある。
【００３１】
これらの誤り値およびそれらの対応の信頼度尺度は、ａ（１）＝００１、ｒ（１）＝０．１；ａ（２）＝００１、ｒ（２）＝０．２；ａ（３）＝０１０、ｒ（３）＝０．３である。等式１を用いると、Ｒ＝０．１＋０．２＋０．３＝０．６である。したがって、この誤りパターンの信頼度尺度は０．６である。
【００３２】
十分なソフト判断デコードアルゴリズムはこの同じ誤りパターンをその出力として生ずるはずである。これは最小距離５符号であるため、ハードデコードは２つまたはそれより少ない誤りを訂正できる。ハードデコードアルゴリズムが上記の信頼できない符号ワードに適用される場合、ハードデコーダ出力誤りパターンは、ａ′（１）＝０１１、ｒ′（１）＝０．３；ａ′（２）＝１１０、ｒ′（２）＝０．５で（０００，０１１，０００，０００，１１１，０００，０００）である。再び、等式１により、このハード誤りパターンの信頼度が：Ｒ′＝０．３＋０．５＝０．８＞０．６＝Ｒによって与えられる。これは、ソフト判断アルゴリズムによって与えられる誤りパターンが正しい誤りパターンであるより大きな可能性を有することを意味する。したがって、ハードデコーダによって与えられる誤りパターンは拒絶されるべきである。
【００３３】
一般記憶処理６０は以下のようにしてしきい値を発生させる：ハードデコーダ３２がある誤りパターンをｅ個の誤りおよび信頼度尺度Ｓで発生させる場合、別の誤りパターンが、下に示されるように、少なくとも（ｄ−ｅ）の非０記号を含む。（ｄ−ｅ）の非０記号を伴う任意のパターンは少なくともＴ（ｄ−ｅ）の信頼度尺度を有する。Ｓ≦Ｔ［ｄ−ｅ］では、Ｓより小さい信頼度尺度を伴う誤りパターンを見つけることは不可能である。したがって、Ｓ≦Ｔ［ｄ−ｅ］である場合、ハードデコーダ出力は「最善の」ソフト判断デコード出力と同じである。
【００３４】
例１では、したがって、ｄ＝５であり、信頼度尺度は以下によって与えられる。
【００３５】
（０．１，０．３，０．２，０．３，０．５，０．９，０．９）
したがって、ｍ［１］＝０．１、ｍ［２］＝０．２、ｍ［３］＝０．３、およびｍ［４］＝０．３は、順序正しく記憶されるｄ−１または４つの最も信頼性の低い尺度である。次いで、しきい値は以下のようになる。
【００３６】
【数４】
0004486198.tif 000005
【００３７】
ハードデコーダがａ′［１］＝０１１、ｒ′［１］＝０．３；ａ′［２］＝１１１０、ｒ′［２］＝０．５；およびｅ＝２で誤りパターン（０００，０１１，０００，０００，１１０，０００，０００）を発生させる場合、この誤りパターンの信頼度はＲ′＝０．３＋０．５＝０．８＞Ｔ［ｄ−ｅ］＝Ｔ［ｄ−２］＝０．６で与えられる。この結果、このデコードされた誤りパターンは即座に受入れられるべきではない。ソフト判断デコード出力がより小さな信頼度尺度で誤りパターンを発生させるかもしれない可能性があるからである。
【００３８】
例２
元の符号ワードを例１にて与えられたものと同じとする。この符号ワードは、ここで、信頼性のある尺度（０．７，０．８，０．７，０．９，０．６，０．６，０．５）を伴って、（００１，０１１，１００，００１，１１０，００１，１００）に、信頼できないようにされる。ソフト判断デコードは、ａ（１）＝１１１およびｒ（１）＝０．９で誤りパターン（０００，０００，０００，１１１，０００，０００，０００）を生ずるはずである。これは、ハードデコードによって得られる誤りパターンでもある。この場合、ハードデコーダの出力は、ソフト判断デコードに進む必要なく受入れられることになる。上述の２つの例から、ハードデコードの結果はソフト判断デコードの結果と同時であってもよいことがわかる。
【００３９】
上記したように単純な基準を確立することによって、ハードデコード出力の結果がソフト判断デコード出力の結果と同一であるかどうかを判断するために、この基準を用いてより複雑で時間がかかるソフト判断デコードの処理をトリガすべきか否かを判断することができる。同様に、一般記憶処理６０もこの例においてしきい値を与える。信頼できない符号ワードに対する信頼度尺度は、上に与えられるように、（０．７，０．８，０．７，０．９，０．６，０．６，０．５）である。ハードデコードされた出力は、ａ′（１）＝１１１、ｒ′（１）＝０．９およびｅ＝１で誤りパターン（０００，０００，０００，１１１，０００，０００，０００）を発生する。ｍ（ｊ）は、ｍ（１）＝０．５、ｍ（２）＝０．６、ｍ（３）＝０．６、ｍ（４）＝０．７であり、しきい値は以下によって与えられる。
【００４０】
【数５】
0004486198.tif 000006
【００４１】
ハードデコードされた誤りパターンはたった１つの誤りしか含まず、つまりｅ＝１である。したがって、Ｒ′＝ｒ（１）＝０．９である。この値は、Ｔ（ｄ−ｅ）＝Ｔ（ｄ−１）＝２．４より小さい。したがって、このハードデコードされた誤りパターンは、最善のソフト判断デコードされた出力と同じである。この結果、この出力は最終出力として受入れられ得、ソフト判断デコードに進む必要は全くない。
【００４２】
しきい値Ｔ（ｋ）は、すべてのｋに対しＴ（ｋ−１）よりも大きく、ｅ個のデコードされたハード誤りの信頼度尺度はＴ（ｄ−ｅ）と比較されるため、より小さい重みの誤りパターンがそのしきい値を超える可能性はより大きな重みを有する誤りパターンよりもはるかに小さい。さらには、大きな重みの誤りパターンの信頼度尺度は小さな重みの誤りパターンよりも大きなことが多いということも注目すべきである。このことによって、小さな重みの、ハードデコードされた誤りパターンがソフト判断デコードされた誤りパターンと同一である可能性がさらに増大する。
【００４３】
（ｎ，ｋ，ｄ）符号に対するハードデコードアルゴリズムの出力は、うまくすれば、ｅ＜ｄ／２としてｅ個の非０記号を伴う誤りパターンを発生させる。以下に示すように、他のどのような誤りパターンも少なくともｄ−ｅの非０記号を有する。この属性を利用して、ハードデコードされた誤りパターンがソフト判断デコードと同一である可能性を有するか否かを判断する基礎を形成する。この受入れ基準は１方向に誤り得ることが重要である。換言すれば、ある基準がハードデコードされた誤りパターンを受入れる場合、その誤りパターンはソフト判断デコーダ出力のそれと同一でなければならず、逆に、その基準がハードデコードされた誤りパターンを拒絶しても、その誤りパターンは依然としてソフト判断出力と同一であり得る（この場合のペナルティはスループットであって性能ではない）。十分な基準では、ハードデコーダ出力がソフト判断デコーダ出力と同一である場合、可能な限り少ないハードデコーダ出力を拒絶するはずである。
【００４４】
このアーキテクチャは、誤りおよび消去デコードアルゴリズムとともに用いられ得る。誤りおよび消去デコードアルゴリズムは信頼できない符号ワードの各記号を２つの分類のうちの１つに分類する。一方の分類は、より低い信頼度を伴う記号である消去と称され、他方の分類は消去されない記号を含む。このほか、誤りのみハードデコードするよりわずかにより複雑な誤りおよび消去デコードアルゴリズムもある。図４の一般記憶処理６０は、ハードデコードを用いることによって、消去を含む信頼できない符号ワードをデコードし得る。
【００４５】
このデコードは、信頼度値１を任意の非消去記号に、および信頼度値０．５を任意の消去記号に割当てる。信頼できない符号ワードにおける「ｅ＿ｅｒａｓｕｒｅ」消去記号の場合、ｊ＞ｅ＿ｅｒａｓｕｒｅに対し、ｍ［１］＝０．５、ｍ［２］＝０．５、…、ｍ［ｅ＿ｅｒａｓｕｒｅ］＝０．５、ｍ［ｊ］＝１である。次いで、しきい値が、ｊ≦ｅ＿ｅｒａｓｕｒｅおよびｊ＞ｅ＿ｅｒａｓｕｒｅに対し以下のように与えられる。
【００４６】
【数６】
0004486198.tif 000007
【００４７】
この処理は、ハードデコーダ３２を用いて「ｅ＿ｈａｒｄ」誤りを伴う誤りパターンを得、その誤りパターンに対し計算された信頼性がＴ［ｄ−ｅ＿ｈａｒｄ］以下である場合にはハードデコーダ３２の出力をデコーダ３０からの最終のデコードされた出力として受入れる。そうでない場合には、誤りおよび消去アルゴリズムを呼出して、最終のデコードされた符号ワードを得る。
【００４８】
しきい値Ｔ［ｊ］はｅ＿ｅｒａｓｕｒｅの各値に対して計算され得ることに注目されたい。したがって、各記号ごとに信頼度情報を処理する必要はない。ハードデコードされた出力では、誤りパターンの信頼度は、ｅ＿１を、そのデコードされた誤りパターンにおける消去記号の数として、以下のように与えられる：
【００４９】
【数７】
0004486198.tif 000008
【００５０】
もう１つの重要な点は、消去記号の各々はハードデコーダにそのまま与えられてもよく、または任意の固定値（たとえばすべて０の記号）によって置き換えられてもよい、という点である。線形ブロック符号における誤りパターン間にはある重み付け関係が存在する。ある線形ブロック（ｎ，ｋ，ｄ）符号の場合、Ｃ〜を１×ｎ符号ワードＣの配置行列として、以下のように、ｎ  Ｘ  （ｎ−ｋ）パリティ行列Ｈが存在する：
【００５１】
【数８】
0004486198.tif 000009
【００５２】
Ｅを誤りパターンとして、信頼できない符号ワードＣ′＝Ｃ＋Ｅを与えると、Ｅのハミング重みが（ｄ−１）／２以下である場合には、ハードデコードアルゴリズムはＥを回復する。（ｎ個の要素からなる集合のハミング重みは、そのｎ個の要素からなる集合における非０要素の数である。）ハードデコードアルゴリズムは誤りシンドローム「Ｙ」の計算またはそれに等価な計算で開始することが多い。０に等しいＹの値の場合、それは誤りが全くないことを示す。０ではないＹの値の場合、それは誤りおよびその誤りを訂正する追加の処理を示す。
【００５３】
【数９】
0004486198.tif 000010
【００５４】
しかしながら、普通の展開によると、Ｙは以下のようになる：
【００５５】
【数１０】
0004486198.tif 000011
【００５６】
各誤りパターンＥに対し、独自なＹの値が存在する。しかしながら、同じＹの値を有するｑk個の誤りパターンが存在する。これは、等式３から、ｑk個の符号ワードのうちの任意の１つをＣとして割当てることによって理解され得る。Ｙ［（ｎ−ｋ）個の要素からなる集合］の所与の値に対し、ハードデコードアルゴリズムによって、ｎ個の要素からなる集合が、（ｄ−１）／２またはそれより少ない非０記号をそのデコードされた誤りパターンとして、発生される。
【００５７】
理想的なソフト判断デコードアルゴリズムは以下を満足させる誤りパターンＥ＿ｓｏｆｔを与え：
【００５８】
【数１１】
0004486198.tif 000012
【００５９】
Ｅ＿ｓｏｆｔの信頼度尺度は以下の等式を満足させる誤りパターンＥのすべてのうちで最も小さいものである：
【００６０】
【数１２】
0004486198.tif 000013
【００６１】
ハードデコードがｅ≦（ｄ−１）／２の記号誤りを伴う誤りパターンＥ＿ｈａｒｄを得る場合、他の誤りパターンは、Ｃを符号ワードとして、Ｅ＿ｈａｒｄ＋Ｃの形態となる。その符号の最小距離はｄであるので、Ｃは少なくともｄ′≧ｄの非０記号を含む。これは、すべて０である、ｎ個の要素からなる集合が、線形（ｎ，ｋ，ｄ）符号の符号ワードであるからである。したがって、この誤りパターンは、（ｄ′−ｅ）から（ｄ′＋ｅ）までの非０記号のどこかに重みを有し得る。Ｅ＿ｈａｒｄの非０記号がＣの非０記号のいずれとも重ならない場合、（Ｅ＿ｈａｒｄ＋Ｃ）は（ｄ′＋ｅ）の非０記号を有する。Ｅ＿ｈａｒｄの非０記号がＣのｅの非０部分集合の選択からくる場合、（Ｅ＿ｈａｒｄ＋Ｃ）の非０要素は（ｄ′−ｅ）である。（ｄ′−ｅ）の最小値は（ｄ−ｅ）である。したがって、他のどのような誤りパターンも、少なくとも（ｄ−ｅ）の非０記号を含む。
【００６２】
【他の実施例】
この発明をその詳細な記載と関連付けて説明してきたが、上記の記載は例示的なものであって、この発明の範囲を限定するように意図されるものではなく、この発明の範囲は前掲の特許請求の範囲によって規定されることを理解されたい。他の局面、利点および修正も前掲の特許請求の範囲内に入る。
【図面の簡単な説明】
【図１】  記憶装置を含むコンピュータのブロック図である。
【図２】  符号ワードデコードスキームのアーキテクチャのブロック図である。
【図３】  図１の記憶装置の誤り訂正装置のブロック図である。
【図４】  誤りデコードスキームのアーキテクチャのブロック図である。
【図５】  図４のデコーダスキームのために信頼度しきい値を発生させるための例示的技術の流れ図である。
【符号の説明】
３０  デコーダ、３２  ハードデコーダ、３４  誤りパターン信頼度計算Ｓ、３８  信頼度しきい値プロセッサ。
【図１】
0004486198.tif 000014
【図２】
0004486198.tif 000015
【図３】
0004486198.tif 000016
【図４】
0004486198.tif 000017
【図５】
0004486198.tif 000018