JPS594741B2 - ブロツク誤り検出訂正方式 - Google Patents

Description

【発明の詳細な説明】 本発明は、複数ビットからなるブロック誤りを検出・訂
正する誤り検出訂正方式に関するものである。

従来、情報処理装置の主記憶装置では、主として、記憶
素子の故障を救済することを目的として、１ビットの誤
りを訂正し、２ビットの誤りを検出する単一誤り訂正・
二重誤り検出符号（ＳＥＣ一ＤＥＤ符号（Ｓｉｎｇｌｅ
ＥｒｒｏｒＣｏｒｒｅｃｔｉｏｎＤｏｕｂｌｅＥｒｒｏ
ｒＤｅｔｅｃｔｉｏｎｃｏｄｅ）と以下略称する。

）を用いた誤り訂正方式を採用して、装置信頼度の向上
をはかつてきた。一方、記憶素子の高集積化に伴い、１
素子あたり複数ビットのデータ出力を有するＬＳＩ記憶
素子が出現している。

この複数ビット出力のＬＳＩ、記憶素子においては、１
素子に故障を生じた場合に、その故障素子から出されて
いる複数ビット全体に誤りが波及する可能性がある。こ
のため、複数ビツト出力素子に対してＳＥＣ−ＤＥＤ符
号を適用してもその信頼度の向上は不十分なものとなる
。これに対し、ＢＯｓｓｅｎは、（Ｄ．Ｃ．ＢＯｓｓｅ
ｎ；ｂ−ＡｄＪａｃｅｎｔＥｒｒＯｒＣＯｒｒｅｃｔｉ
Ｏｎ．，ＩＢＭＪ．Ｒｅｓ．ＤｅｖｅｌＯｐ．Ｊｕｌｙ
ｌ９７Ｏを参照）あらかじめ区切られた複数ビツト（ｂ
ビツト）のプロツク内に生じたあらゆる誤りを訂正する
能力を持つ単一関連ｂビツト誤り訂正符号（単一ｂ−Ａ
ｄｊａ−Ｃｅｎｔ誤り訂正符号、以下ＳｂＥＣ符号（Ｓ
ｉｎｇｌｅｂ−Ａｄｊａｃｅｎｔｂｉｔ−ＧｒＯｕｐＥ
ｒｒＯｒＣＯｒｒｅ一ＣｔｉＯｎｃＯｄｅ）と略称する
。）の適用を提案した。このＳｂＥＣ符号によれば、複
数ビツト出力素子に対しても、記憶素子内の故障を完全
に救済する事が出来る。現伏のＳＥＣ−ＤＥＤ符号を使
用している主記憶装置では、符号の２重誤り検出機能に
より、同一アドレス上の２ビツトの誤りを完全に検出す
る事が出来る。

これに対し、ＳｂＥＣ符号は、２個のプロツクにまたｔ
）３つた誤りを検出することは保証されていない。

このため、複数ビツト出力素子とＳｂＥＣ符号を使用す
る主記憶装置では、２個の素子にまたがる２ビツト以上
の誤りを完全に検出する事は出来ない。特に２個の記憶
素子にまたｔ）３る２ビツトの誤りを完全に検出する事
ができず、この点、ＳｂＥＳ符号は、ＳＥＣ−ＤＥＤ符
号と比較して、その能力ｔ）３劣つている。上記のＳｂ
ＥＣ符号の問題点を解決するためには、ｂビツトのプロ
ツク内の誤りを訂正Ｌ、しかも２個のプロツクにまたが
る最大２・ｂビツトまでの誤りを検出する申一関連ｂビ
ツト誤り訂正・二重関連ｂビツト誤り検出符号（ＳｂＥ
Ｃ−ＤｂＥＤ符号（Ｓｉｎｇｉｅｂ−Ａｄｊａｃｅｎｔ
ｂｉｔ−ＧｒＯｕｐＥｒｒ−０ｒＣ０ｒｒｅｃｔｉ０ｎ
Ｄ０ｕｂ１ｅｂ−Ａｄｊａｃｅｎｔｂｉｔ−ＧｒＯｕｐ
ＥｒｒＯ′ＲＤｅｔｅｃｔｉＯｎｃＯｄｅ））が必要で
ある。

しかしＳｂＥＣ−ＤｂＥ｝舟号として従来知られている
Ｒｅｅｄ−ＳＯｌＯｍＯｎＯＳｂＥＣ一ＤｂＥＤ符号（
．Ｓ．Ｒｅｅｄ＆Ｇ．ＳＯＩＯｍＯｎ：ＰＯｌｙｎＯｍ
ｉａＩＣＯｄｅＯｖｅｒＣｅｒｔａｌｎＦｉｎｉｔｅＦ
ｉｅＩｄｓ．，Ｊ．ＳＯｃ．Ｉｎｄ．Ａｐｐｌ．Ｍａｔ
ｈ．，０１．８，Ｊｕｎｅ１９６０．参照）は、その符
号長が限定されており、ｂ＝２，３，４などの場合、主
記憶装置用符号として必要な情報長、例えば６４ビツト
、１２８ビツトを得る事は出来ない。また、Ｐｒｉｃｅ
は、（米国特許第３，７５５，７７９号明細書参照）関
連２ビツト誤り訂正・非関連２ビツト誤り検出符号とし
て、情報長６４ビツトの場合の構成例を示している。

しかしこの符号を使用した誤り検出訂正装置では、２個
のプロツクにまたがつて生じた３ビツト、４ビツトの誤
りに対する検出能力は保証されず、Ｉ，かも情報長６４
ビツトに対して１３ビツトの冗長を必要としている。ま
た、これら複数ビツトの関連誤りを訂正する符号におい
ては、その符号化・復号化回路は、くり返し性を有して
おらず、そのため、この回路をＬＳＩ化する場合につい
て、そのパターンコード数が増加する欠点を有していた
。本発明の目的は、あらかじめ区切られたｂビツトのプ
ロツク内のあらゆる誤りを訂正可能であり、しかも２つ
のプロツクにまたがつた２・ｂビツトまでの誤りを検出
できる関連ｂビツト誤り訂正符号を採用し、Ｌかも前記
の従来の符号とは異なり、任意の符号長が選択可能な符
号を使用するプロツク誤り検出訂正方式を提供すること
にある。

また本発明の他の目的は上記符号を使用して、その符号
化・復号化回路がくり返し構成を有し、ＬＳＩに適する
回路構成を実現し得るようにすることにある。以下実帷
例について詳細に説明する。第１図は本発明の実施例の
プロツク図であり、情報６は符号化回路を構成するチエ
ツクビツト生成回路１に加えられ、情報６に対応したチ
エツクビツト７が生成されて、情報６とこのチエツクビ
ツト７とは、記憶装置、各種伝送路等を総称して示すプ
ロセツサ２に加えられる。このプロセツサ２の出力情報
９はシンドローム生成回路３に加えられる。このシンド
ローム生成回路３とシンドロームデコード回路４と誤り
訂正回路５とにより復号化回路ｂ｛構成され、シンドロ
ーム生成回路３は出力情報９からのシンドロームビツ口
２を生成し、シンドロームデコード回路４に於いてデコ
ードされて誤り位置指摘情報ビツト１０となり、この誤
り位置指摘情報ビツト１０と出力情報９中の情報６に対
応する情報８とが誤り訂正回路５に加えられて、誤りが
訂正された後再生情報１１が出力される。被符号化情報
６は各々がｂビツトからなるｋ個のプロツクのデータＤ
。

，Ｄｌ，・・・・・・Ｄｋ−１により構成され、チエツ
クビツト７は各々ｂ｛ｂビツトからなるｒ個のプロツク
のデータＣｌ，Ｃ，，一 ・・・・Ｃｒより構成され、
チエツクビツト生成回路１はの関係式に従つたデータＣ
，を生成するものである。なおりは２より大なる整数で
、ｋは１より大なる整数であつて、ｒはｋに依存して決
定される整数である。このような符号化により、（ｋ＋
ｒ）個のプロツク中の任意の１プロツクに発生した誤り
（単一の関連誤り）を訂正Ｌ、２個のプロツクにまたが
つて発生した誤り（二重の関連誤り）を完全に検出する
ことができるものである。

ここで、本発明の詳細な説明に先立ち、本発明で利用す
る先行技術であるＲｅｅｄ−ＳＯｌＯｍＯｎのＳｂＥＣ
−ＤｂＥＤ符号を用いた誤り検出・訂正について説明す
る。

Ｒｅｅｄ− ＳＯｌＯｍＯｎＯＳｂＥＣ−ＤｂＥＤ符号
を使用する誤り検出・訂正方式に於けるチエツクビツト
生成回路は、ｋ個のプロツクからなる被符号化情報から
３個のプロツクからなるチエツクビツト部を炸成Ｌ、（
ｋ＋３）個のプロツクとして送信情報を生成する回路で
ある。

この回路は、次の関係式に従つてチエツクビツトプロツ
クを生成する。但し、ここにｋは１くｋく２ｂ−１を満
足する整数であり、Ｄ．はプロツク中の第０プロツクを
表わＬ．Ｄｌは第１プロツクを表わし、Ｄ，は第２プロ
ツクを表わし、以下同様にしてＤｋ−１は第ｋ番目、即
ち、最後のプロツクを表わす。情報ビツ壮の代表的なプ
ロツクをＤｊで表わしている。また式（１）のＴは有限
体（ＧａｌＯｉｓＦｉｅｌｄ）ＧＦ（２ｂ）の生成元で
あつて、零元（０）、単位元１をあわせて、有限体ＧＦ
（２ｂ）を生成する。則ち、はＧＦ（２ｂ）を形成する
。以上において示された乗算、加算はＧＦ（２ｂ）上の
演算である。式（１）のＣｌ，Ｃ，，Ｃ，の計算は次に
示す符号化マトリクス旧。によつて記述できる。ここで
、 Ｃ＝（Ｃｌ，Ｃ，，Ｃ，） Ｄ ＝（ ＤＯ．Ｄ，，・ ・−・−Ｄｊ・ ・・・・
Ｄ，−１）ｔ：転置次に復号においては、次の関係式を
用いてシンドロームビツトを生成する。

シンドロームビツトはｂビットのプロツクでぁるＳ，，
ｓ，，ｓ，から構成される。ここで、「Ｉ」（ダツシユ
）はそれが付されてない送信情報に、対応する受信情報
のプロ．ツクを示す。

また、旧，は次式で与えられ、Ｈマトリクスと呼ばれて
いる。Ｓ ＝（ Ｓ，，Ｓ，，Ｓ３） また、有限体ＧＦ（２ｂ）上の元はＧＦ（２）上の元で
表現せねばならない。

変換は、ＧＦ（２）上のｂ次の既約多項式ｇ（ｘ）から
、次のｂ行ｂ列の同伴行列（ＣＯｍｐａｎｉＯｎｍａｔ
ｒｉｘ）によつてＴを置換することにより行うことがで
きる。ここで、Ｉｂ−，は（ｂ−１）行（ｂ−１）列の
単位行列であり、Ａ．，ａｌ・．．．Ａ，−，はＧＦ（
２）の元であつて式（８）に示すｂ次の既約多項式ｇ（
ｘ）の係数である。

ここに Ａｂ＝１ また、Ｈマトリクス（パリテイ検査マトリクス）が（６
）式で与えられる符号がＳｂＥＣ−ＤｂＥＤ符号である
ことは（６）式の任意の３列を取り出して作成した行列
が正則であることから証明する事ができる。

その詳細は前述のＲｅｅｄ−ＳＯｌＯｍＯｎ著の文献及
びＪ．Ｋ．ＷＯｌｆ：ＡｄｄｉｎｇＴｗＯＩｎｆＯｒｍ
ａ一ＴｉＯｎＳｙｍｂＯｌｓｔＯＣｅｒｔａｉｎＮＯｎ
ｂｉｎａｒｙＢＣＨＣＯｄｅｓａｎｄＳＯｍｅＡｐｐｌ
ｉｃａｔＩＯｎｓ・，Ｂ．Ｓ．Ｔ．Ｊ．，Ｓｅｐｔ．ｌ
９６９．に示されている。Ｒｅｅｄ−ＳＯｌｍＯｎＯ）
ＳｂＥＣ−ＤｂＥＤ符号として最大の符号長を持つのは
そのＨマトリツクスが次式で示され、符号長は式００）
で与えられる。ここで明らかなように、Ｒｅｅｄ−ＳＯ
ｌＯｍＯｎのＳｂＥＣ−ＤｂＥＤ符号はその冗長（チエ
ツクプロツクの個数ｒ）が３に固定されており、情報長
を（２ｂ−１）以上に任意に延ばしてゆく事は出来ない
。符号長Ｎ＝（２ｂ＋２）・ｂ（ビツト） ・・佃第１
表はｂ−２，３，４の場合におけるＲｅｅｄ−ＳＯｌＯ
ｍＯｎＯＳｂＥＣ−ＤｂＥＤ符号の情報長（ ２ｂ−１
）・ ｂであり、情報長６４ビツト、１２８ビツトの主
記憶用符号としてはこの符号は不適当である事がわかる
。

そこで本発明のエラー検出・訂正方式では、次の定理１
から任意の符号長を持つ事のできるＳｂＥＣ−ＤｂＥＣ
符号を作成し、この符号を採用する。

定理 １ ＧＦ（２ｂ）上の元で表現したＳｂ．ＥＣ−ＤｂＥＤ符
号のＨマトリクスを第１マトリクスとし、その列ベクト
ルを１Ｖｉ（１＝１，２・・・ ，ｎ）とする。

一方、別のＳｂＥＣ−ＤｂＥＤ符号のＧＦ（２ｂ）表現
のＨマトリクスに対し、ある行の要素をすべて単位元「
Ｉ」とする変形を加える。この変形を加えたＨマトリク
スを第２マトリクスとし、第２マトリクスのすべて「工
」である行の成分を除く各列ベクトルを１Ｗｊ（ｊ ＝
１，２，・・ｍ）とする。但し，ここに、Ｎ，ｍは有限
体ＧＦ（２ｂ）上での符号長である。この時、上記第１
マトリクスのＩＶ，、第２マトリクスのＩＷＪから次式
（１１）のように新Ｌい列のベクトルＣｉｊを炸成すれ
ば、この（Ｌ′，ｊをその列ベクトルとするＨマトリク
スで表わされる符号はＳｂＥＣ−ＤｂＥＤ符号であり、
その符号長はｍ−ｎで与えられる。

次にこの定理を証明する。

証明 まず、式０１）から新Ｌく作成される符号ｔ）３ＳｂＥ
Ｃ一ＤｂＥＤ符号である事を示す。

ＳｂＥＣ−ＤｂＥＤ符号である事は式０１）の（１′，
Ｊから任意の３列を取り出して作成した行列が正則であ
る事と等価である。また、第１マトリクス、第２マトリ
クスの性質から次式を満足するのはＧＦ（２ｂ）上の元
Ｅａ，ｅｂはすべて零の場合のみである。次に列ベクト
ルＣｉｊの任意の３列から次式０４）を作成する。

式０４）を満足する解（ Ｅｌ，ｅ，，ｅ，）について
吟味する。

１）Ｃｌ，Ｃ，，Ｃ３が相異なる時。

この時は、式０４）のＩＶの行に着目すれば、式０３）
よりＥ，，ｅ，，ｅ３はすべて零となる。

１１）Ｃｌ，Ｃ，，Ｃ，がすべて同一の時。

この時はＣｉｊの構成法からＤｌ，ｄ，，ｄ，はすべて
相異なる。よつて式０４）の｝Ｗの行に着目して式０か
らＥ，，ｅ，，ｅ，はすべて零でなければならない。１
１ｉ）Ｃ，，Ｃ２，Ｃ，のうち、２つが一致し、他の１
つが異なる時。

この時は、Ｃ，とＣ，が等しくＣ，がそれらと異なると
仮定しても一般性は失われない。

式（１４）のＩＶの行に着目すればＥｌ，ｅ，，ｅ，ｔ
）３次式（１５）を満足せねばならぬことがわかる。

次にＥｌ，ｅ，，ｅ，について、式０４）のＩＷの行に
着目すれば、Ｄｌ，ｄ，が相異なる事からｅｌとＥ，は
零でなければならない。以上の関係によつて、式（１４
）を満足する場合は、Ｅ，，ｅ，，ｅ，がすべて零であ
る場合のみである事が証明できた。また以上から符号長
がｍ−ｎである事は自明である。よって、（Ｌ′ぃから
任意の３列を取り出して昨成した行列は正則であり、（
１′，ｊから作られた符号はＳｂＥＣ−ＤｂＥＤ符号で
ある。次に定理１を用いて、Ｒｅｅｄ−ＳＯｌＯｍＯｎ
のＳｂＥＣ−ＤｂＥＤ符号から、任意の符号長のＳｂＥ
Ｃ−ＤｂＥＤ符号を構成する。

まず、そのＨマトリクスが式（９）で表わされるＲｅｅ
ｄ− ＳＯｌＯｍＯｎＯＳｂＥＣ−ＤｂＥＤ守号を第１
マトリクスとし、同一のＲｅｅｄ−ＳＯｌＯｍＯｎのＳ
ｂＥＣ−ＤｂＥＤ符号から第２マトリクスを導出して、
定理１によりそのＨマトリクスがＧＦ（２ｂ）上で５行
構成のＳｂＥＣ−ＤｂＥＤ符号を構成する。

ここで、第２マトリクスは式（１６）のように変形され
る。このような変形が任意のｂについて可能である事は
容易に証明する事ができる。ここで、Ｔｌ，Ｔｒｎ，は
変形の結果として得られるＧＦ（２ｂ）の元である。

式（９）と式（自）に定理１を適用すれば、そのＨマト
リクスが５行構成の符号が得られ、その符号長Ｎは次式
（自）で与えられる。

Ｎ−（２ｂ＋２）２・ｂ （ビツト） ・・・・・・・
・・０７）次に例として、ｂ−２の場合を示す。

まず、ｂ＝２のＲｅｅｄ−ＳＯＩＯｍＯｎ符号のＨマト
リクスは次式で与えられる。空白の要素は零元である。
式（自）に対して、その１行目がすべてＩとなるように
変形を加えるど次のＨマトリクスを得る。ここで、ガロ
ア体ＧＦ（２ｂ）上での演算方法を具体的に示しなｔ）
３ら、式（自）から式（自）への変換方法について説明
する。ガロア体ＧＦ（２ｂ）上の加算と乗算は以下の様
に実行できる。

〔加算〕

０＋０ ＝０Ｔ１＋０ ＝Ｔｌ Ｏ＋Ｉ − Ｔ１＋Ｉ ＝Ｔ２ Ｏ＋Ｔ１＝ＴｌＴｌ＋Ｔ１−０ ０＋Ｔ２−Ｔ２Ｔｌ＋Ｔ２−１ ＋０ ＝１Ｔ２＋Ｏ ＝Ｔ２ ｌ＋Ｉ −０Ｔ２＋Ｉ＝Ｔｌ ｌ＋Ｔ１＝Ｔ２Ｔ２＋Ｔ１− １＋Ｔ２＝ＴｌＴ２＋Ｔ２−０ 〔乗算〕 ０Ｘ０−０ ０×−０ ０ＸＴ１＝０ ０×Ｔ２＝０ Ｔ１×Ｏ−０ Ｔ１×Ｉ＝Ｔｌ Ｔｌ×Ｔ１−Ｔ２ Ｔｌ×Ｔ２＝１ １×０ ＝０Ｔ２×０＝０ ＩＸＩ＝ Ｔ２×＝Ｔ２ ＩＸＴｌ＝ＴｌＴ２×Ｔ１＝１ １＞＜Ｔ２＝Ｔ２Ｔ２×Ｔ２＝Ｔ１ 以上の演算一覧からも分かる様に、加算または乗算され
る２個の数は、その順序を入れ換えても、演算の結果に
変化はない。

当然のことであるが、演算の結果はガロア体ＧＦ（２ｂ
）の元である。ここに示した例は、ガロア体ＧＦ（２２
）の例であるが、他のｂの値でも、上記の様な演算一覧
表を作成できる。（ただし、ｂが多麿坊、演算表は大き
くなる。）さて、式（自）から式（自）への変換に戻る
。ここで、符号理論の良く知られた性質として、以下の
性質ｂ｛あることは、当業者において、周知の事実であ
ることに留意されたい。（１） Ｈマトリツクスの任意
の行の全ての要素に、ガロア体ＧＦ（２ｂ）の非零元（
即ち「０］でない、任意の元）を乗じても符号の能力に
変化はない。

（２） Ｈマトリツクスの任意の行を他の任意の行に加
算しても、符号の能力は変化しない。（３） Ｈマトリ
ツクスＤ任意の列の全ての要素に、ガロア体ＧＦ（２５
）の非零元（即ち「ｏ」でない、任意の元）を乗じても
符号の能力に変化はない。

ここで、上記（１）〜（３）の性質において、加算、乗
算はすべて、ガロア体ＧＦ（２ｂ）上の演算であること
は、言うまでもない。また、上記の（１）〜（３）で言
う、「符号の能力」とは、ＳｂＥＣ−ＤｂＥＤ機能であ
ることは、論を待たない。さらに、当業者に周知の符号
の性質として、以下の２つの性質がある。

（４） Ｈマトリツクスの列ベクトルの順序をいれかえ
ても、符号の能力に変化はない。

（５） Ｈマトリツクスの行ベクトルの順序をいれかえ
ても、符号の能力に変化はない。

以上の（１）〜（５）をまとめると、符号のＨマトリツ
クスに対して、（１）〜（５）に示した操作を帷しても
、符号の誤り検出・訂正能力は変化しないことになる。

実際、符号理論研究の分野では、（１）Ｈマトリツクス
の行および列の順序の変更、（２）ある行ベクトルを他
の行ベクトルに加算する、（３）ある列ベクトルまたは
行ベクトルに、非零の元を乗じる操作）等のＨマトリツ
クスに対する演算操作のみで得られたＨマトリツクスが
表現する符号は、新規な符号とはみなされず、変換前の
Ｈマトリツクスにより表現される符号と全く同一である
とみなされている。

さて、上記の（１）〜（５）のＨマトリツクスの性質を
使用し、式（自）のＨマトリツクスを変換してゆく。

まず、式（自）をガロア体ＧＦ（２ｂ）上の表現として
、以下の様に再掲する。ここで、上記の性質（１）を使
用して、Ｈマトリツクスの第１行にＴ１を乗じる。

結果は以下の様になる。ここで、第１行にＴ１を乗じた
目的は、後程、第２行と第３行を第１行に加算した時に
、第１行の要素に「Ｏ」元が出現するのを防止すること
にある。

次に、上記の第２行を第１行に加算する。

性質（２）から、符号の能力（即ち、単一のプロツク誤
りを訂正し、２重のプロツク誤りを検出する能力）は変
化しない。さらに、上記の第３行を第１行に加算する。

性質（２）から、符号の能力は変化しない。ここで、第
］行目の各要素は全て、非零の元となつたことに留意さ
れたい。

一般的な証明は省略するが、任意のｂの値に対して、上
記の様な処理（即ち、式（９）のＨマトリツクスの第１
行に、特定のある非零の元を乗じたのち、第２行と第３
行を第１行に加算する演算処理）により、Ｈマトリツク
スの第１行の要素を全て非零元とすることｆ）５できる
。あとは、上記の性質（３）に従い、各列ベクトルの最
上部の要素が「１」となるように、各列ベクトルに特定
のある元を乗じる。

上記の列では、左から、「Ｔ２」，「Ｔ１」，「Ｔ１」
，「Ｔ２」を各列ベクトルに乗じてやる必要がある。以
上の演算の結果、次のマトリツクスを得る。

Ｈマトリツクスの性質として、列ベクトルの順序を入れ
換えても、符号の能力に変化ｔ）′３無い。したがつて
、上式の列ベクトルの順序を変更して、式（自）を得る
。式（自）と０９から次に示す符号長７２ビツトのＳｂ
ＥＣ−ＤｂＥＤ符号を得る事ができる。

この符号はこのままではチエツクプロツクを持たないが
後に示すようにこのＨマトリツクスに簡単な変形を加え
る事によつてチエツクプロツクを生成することＢ３でき
る。次に、５行構成を、そのＨマトリクスとして持つ、
ＳｂＥＣ−ＤｂＥＤ符号と３行構成のＳｂＥＣ一ＤｂＥ
Ｄ符号から、そのＨマトリクスが７行構成のＳｂＥＣ−
ＤｂＥＤ符号を得る事ができる。

同様にして、奇数行数をそのＨマトリクスの行数として
有するＳｂＥＣ−ＤｂＥＤ符号を次々と作る事が可能で
ある。一方、そのＨマトリクスがＧＦ（２ｂ）上で偶数
となるＳｂＥＣ−ＤｂＥＤ符号が必要な場合は、第１マ
トリクスとして奇数行数のものを選び、第２マトリクス
として、式（２１）で与えられるマトリクスを使用すれ
ばよい。

第２図及び第３図は式（２０）と式（２１）を用いて具
体的に符号を購成してゆく手順を示している。

なお第２Ａ図は第２図のａ−ｃの配置説明図、第３Ａ図
は第３図のａ−ｃの配置説明図である。第２図は定理１
を用いて作成した情報長１３２ビツトのＳ２ＥＣ−Ｄ２
ＥＤ符号の例であり、第３図は、そのＨマトリクスにチ
エツクビツトに相当する列（図中丸で印をつけた列）が
生成されるように変形させたものである。

情報長１２８ビツトの符号は、第３図のＨマトリクスか
ら列を選び、情報長１２８ビツト、符号長１４０ビツト
の（１４０，１２８）Ｓ２ＥＣ−Ｄ２ＥＤ符号を作成す
れば良い。以上の構成法によつて得られる符号のＨマト
リクスのＧＦ（２ｂ）土の行数をｒとするとき、一般的
に６その符号長Ｎは、次式で表現できる。

ここでト一↓卜『ｘ］はＸを越えない最大の整数をあら
れす。

以上、任意の符号長を有するＳｂＥＣ−ＤｂＥＤ符号の
構成法を示した。

次に上記のプロツク誤り検出訂正符号を使用して、その
符号化・復号化回路にくり返し性を与える構成法につい
てのべる。本手法は特に、そのＨマトリクスｔ）３ＧＦ
（２ｂ）上の表現で偶数行数であるＳｂＥＣ−ＤｂＥＤ
符において有用である。まず、ＳｂＥＣ−ＤｂＥＤ符号
のＨマトリクスが次式のように与えられるとする。

ここで、１Ｈ０はＧＦ（２ｂ）上の元から構成されるＳ
ｂＥＣ−ＤｂＥＤ符号であり、式（２３）の上半分の行
に対するチエツクプロツクを持つている。

。１ＨはこのＩＨＯを上下方向に反転させたものであり
、式（２３）がＳｂＥＣ−ＤｂＥＤ符号であるために次
の条件を満足しなければならない。

（１）ＩＨＯはｒ／２列のチエツクプロツクを持つてい
る。

ここで更に残りのｒ／２列のチエツクプロツクをも含め
て考えた時、全体としてＳｂＥＣ−ＤｂＥＤ符号である
こと。（Ｉｉ）１Ｈ０の最上位の行は（チエツクビツト
プロツクの列をのぞく。

）すべて非零の元で構成されていること。（１１０１Ｈ
０の最下位の行はすべて零元であること。

以上の条件を満足すれば式（２３）で示した符号が、や
はりＳｂＥＣ−ＤｂＥＤ符号である事は、容易に証明す
る事Ｂ３出来る。ここで、その符号化・復号回路ｔ）３
、くり返し２を持つ事を示す。

まず、Ｈマトリクスのくり返し単位（ＩＨＯ）を次のよ
うにあられす。

０，１，ｈｉｊ０ＧＦ（２ｂ），２くｉ＜ｒ−１，１く
ｊ＜ｋ−１，ここに１Ｈ０は残りのＲ７２列のチエツク
プロツクを含めて、ＳｂＥＣ−ＤｂＥＤ符号であり、デ
ータプロツクＤ。

，Ｄｌ・・・Ｄ２ｋ−１に対して、各々ｂビツトからな
るチエツクプロツクＣｌ，Ｃ２・・・Ｃ，ｔ）３次式に
従つて生成される。ここで、 回路と、１ Ｃｉの．？，Ｈ，，゜Ｄｊ−１の項の生成項の生成回路
とは、全く同一の回路構成であり、式（２３）の符号で
は、そのチエツクビツト生成回路を同一の回路２個から
構成可能である。

上記チエツクビツトとデータプロツクＤ。

，Ｄｌ・・・Ｄ２，−１から得られるコードワード｛Ｄ
Ｏ，Ｄｌ，Ｄ２・・・Ｄ２，−１，Ｃ１，Ｃ２，・・・
Ｃｒ｝が処理を受けたものを｛Ｄａ，Ｄ″１，Ｄ？・・
・ＤＵぃ、，Ｃ′Ｉ，Ｃｉ・・・Ｃ ｝であられす。復
号化には、シンドロームビツトの生成と、そのシンドロ
ームのデコードを行う。

まず、各ｂビツトのシンドロームＳｌ，Ｓ２，Ｓ３・・
・Ｓ，の生成を次式に従つて行う。生成回路と、１１）
Ｓ，−ｉ＋１におけるΣＨｒ．．ｉ＋１，ｊ−，・Ｄ
１−１の生成回路は同一の構成であつて、チエツクプロ
ツクＣ″．を加算する回路も含めて、シンドローム生成
回路は全体でくりかえし２を持つ。

一方、シンドロームデコード回路はシンドロームビツト
を受信して、当該列に誤りが生じている場合について、
その誤りパターンを出力する。

次の列Ｄ．に誤りＥ．が生じたとすれば、シンドローム
デコード回路は次式（２８）式の連立から、誤りパター
ンｅ１を出力する機能を有する。

一方、データプロツクＤｊ＋ｋのデコード回路は（２９
）式の成立を確認して、誤りパターンを出力する。

式（２８），（２９）、及びＨｉ，ｊ＝Ｈ，−１，ｊで
あることから、データプロツクＤｊのデコード回路はそ
のまま入カシンドロームを差し換えるのみで、データプ
ロックＤｊ＋ｋのデコード回路として使用できる。

即ち、ＤＯ−Ｄｋ−１のデータプロツクに対するデコー
ド回路は、そのままＤｋ〜Ｄ，ｋ−１のデコード回路と
して使用できる。以上、任意の符号長を有するＳｂＥＣ
−ＤｂＥＤ符号の新しい構成法を示した。

次に情報長６４ビツトを有するＳ２ＥＣ−Ｄ２ＥＤ符号
の誤り検出訂正装置の具体的購成例を示す。第４図は、
本発明の実帷例におけるＨマトリクスであり、ここでは
ＧＦ（２２）の元で示した。

あらかじめ区切られた２ビツトのプロツク中、１個のプ
ロツクに生じた１ビツト以上の誤りを訂正し、２個のプ
ロツクにまたｔ）３る２ビツト〜４ビツトの誤りを検出
する能力を有する。符号のＨマトリクスは式（２３）で
示した構成を有し、その符号化復号化回路にくりかえし
２を与える事ができる。

また、そのくり返し単位は本発明の手法（定理１）に従
つて、Ｒｅｅｄ−ＳＯｌＯｍＯｎの符号から構成された
式（至）の符号に対して、チエツクプロツクを生成させ
るべく、式（１）の４，５行目を１行目に加えたＨマト
リクスから列を選んで作成した。ここで、式（２３）の
構成法を満足するように列は選ばれている。ここで、第
４図のＨマトリツクスを構成する方法を具体的に説明し
ておく。

まず、式（２３）に戻つて考える。

図４の左半分は式（２３）の［ＨＯｌ．第４図の右半分
は式（２３）の「０Ｈ］であることに留意されたい。Ｈ
Ｏとしては、任意のものを持つてくることができるが、
前述した様に、以下の３つの条件を満している必要があ
る。（Ａ） ＨＯはｒ／２個のチエツクプロツクを持つ
ＳｂＥＣ−ＤｂＥＤ符号のＨマトリックスであり、残り
のｒ／２個のチエツクプロツクを付加しても、ＳｂＥＣ
−ＤｂＥＤ符号としての能力を持つこと。

（Ｂ） ＨＯの最上位の行の安素は、（チエツクプロツ
クをのぞいて）全て「」元であること。

（０Ｈ０の最下位の行の要素は全て「ｏ」であること。

ＨＯは、上記の囚〜（Ｂ）の条件をみたせば任意であり
、本質的には、本明細書で開示した定理１で得られるＨ
マトリツクスを使用する必要はない。

たとえば、既存の技術を利用して、ＨＯを式（９）の符
号から生成する事もできる。そして、この場合も、本発
明の一実誰例である。ただし、本明細書においてのべた
様に、既存のＳｂＥＣ−ＤｂＥＤ符号からＨ。を作成す
る場合には、ｒ＝４に限定される。その理由は、Ｈマト
リツクスが３行構成のＳｂＥＣ−ＤｂＥＤ符号以外に、
ＳｂＥＣ−ＤｂＥＤ符号の構成法が従来知られていなか
つたからにある。従つて、本発明が任意のｒの値に対し
て成立することを示すためには、発明者により発見され
た定理である前述の定理１を使用する必要がある。簡単
な例として、既存のＳｂＥＣ−ＤｂＥＤ符号を式（２３
）に適用した例を示し、そのあとで、第４図の説明を行
うことにする。式（２３）のＨ。

を、既存のＳｂＥＣ−ＤｂＥＤ符号から作る時には、上
記の条件（４）〜（Ｂ）を満足するマトリツクスとして
以下のＨ。が選択可能となる。このＨ。に残るｒ／２個
のチエツクプロツクを付加すると、以下の様になる。こ
こで、このＨａで表現される符号の機能について考えて
見よう。

上記の現で表現される符号の最右端の列をのぞいた部分
は、式（９）のＳｂＥＣ−ＤｂＥＤ符号のＨマトリクス
に前零の１行を追加したものに等しい。

したｔ）３つて、明らかに、上記のＨａで表現される符
号の最右端の列をのぞいた部分は、単一プロツク誤り訂
正・２重プロツク誤り検出の機能を持つている。また、
最右端の一列についてかんがえると、この最右端の列の
みが、上記の馬の第４行目の要素に非零元を持つている
。従つて、この最右端の列に生じた誤りは、訂正可能で
あることになる。（シンドロームの最下位の要素が非零
であるため。）さらに、上記の山の最右端の列と、その
他の１列にまたがつて、２重のプロツク誤りが生じたと
する。この時には、シンドロームの最下位の要素が非零
であり、しかも、シンドロームの上から３個の要素中に
非零元を含むことになり、検出できる。以上の様な考察
から、上記Ｈａによる符号はＳ５ＥＣ−ＤｂＥＤ符号で
あることは明らかである。さて、上記のＨらをそのまま
使用すると、式が長くなるので、以下の様に、短縮化し
て式（２３）の要旨を解説し、符号の構成法を示そう。

この短縮化で、上記の団をそのまま使用する時にくらべ
、符号化可能なデータ長は短くなるが、ＳｂＥＣ−Ｄｂ
ＥＤ符号の機能は失われない。このばあい、ＨＯは以下
の様になる。

このＨ。

ｂ３、前述した、（４）〜（Ｂ）の条件を満たすことは
いうまでもない。再び、式（２３）、即ち本発明の核心
にもどろう。

式（２３）では、その右半分として、ＨＯの行ベクトル
の順序を反転したものを要求している。従つて、この場
合、「０Ｈ」は以下の様になる。従つて、式（２３）の
全体は、 以下の様になる。

ただし、最右端の２列は順序を入れ換えた。

この符号では、符号化・復号化回路に２の繰り返しを与
え、回路のＬＳＩ化に適した構成とすることｔ）３でき
る。なお、符号理論の当業者には良く知られた定理によ
り、Ｈマトリツクスの行を相互に入れ換えても符号の能
力に変化はない。従つて、上記のＨは以下の様にも書け
る。列ベクトルの順序、行ベクトルの順序の入れ換えは
、符号化・復号化回路の構成にはなんら影響を与えない
ことは自明である。さらに、Ｈマトリツクスを以下のよ
うにしても、符号の能力に変化はなく、符号化・復号化
回路に２の繰り返し性を与えうる性質も変化することは
ない。

以上の例は、ｒ＝４のみ適用可能であることはいうまで
もない。

ｒが任意の値の場合でも、式（２３）が実絶しうること
を示すためには、ＨＯを構成するために、前述した定理
１を使用する必要がある。第４図の説明にもどる。第４
図のＨマトリツクスを構成するためには、まず、式（１
）に相当するマトリツクスを構成する必要がある。

式（イ）から第４図を構成する手順を示す。先ず、式（
イ）のＨマトリツクスの第４，５行を第１行に加算する
。

この加算により、符号の能力は変化しないことはすでに
のべた。加算結果を臥下に示めそう。この加算の目的は
、チエツクプロツクを生成することにある。

さて、第４図を作成するために、上記の列ベクトル中で
、一番上の要素ｔ）３「ｏ」でない列を取り出す。ただ
し、チエツクプロツクについては、すべてとりだし、右
端に配置しておく。式（２４）を生成するには、各列ベ
クトルの第１要素は［１］でなければならない。したが
つて、各８列ベクトルに、その第１要素ｔ）卜１となる
ように、特定の元を乗じる。従つて、上記のマトリツク
スの下に、全零の行ベクトルを付加すれば、式（２４）
として使用できる。

ただし、第４図の例では、１繰り返し単位（即ち、ＨＯ
）あたりのデータビツト数は、３２ビツトであるから、
上記の（チエツクプロツクをのぞく）２２列の列ベクト
ルから、１６列ベクトルを適当に選択して式（２４）を
構成すればよい。このばあい、以下の１６列を選択した
。

この例では、列は、符号化・復号化回路の回路量削減の
観点から、符号のＨマトリツクスを「１」，［０」表現
で表現したときの重み（１の数）ができるだけ小さくな
る様に、配慮して選択してある。この１６列に、１行の
全零行ベクトルと（この場合ｒ＝６であるから）、３列
のチエツクプロツクを付加して、ＨＯを構成できる。０
Ｈは、このＨ。

の上下を反転したものにすぎない。従つて、となり、チ
エツクプロツクの位置を入れ換えて、次の様になる。

この、ＨＯと０Ｈから、第４図が得られる。

ただし、第４図では、チエツクプロツクの位置を変更し
て示してあるが、これにより、符号化・復号化の回路が
実質的に変更されることはない。まず、第４図の符号を
使用する誤り検出訂正装置のチエツクビツト生成回路、
シンドローム生成回路を説明する。

第５図はシンドローム生成のための１２行構成のパリテ
イ検査マトリクス（１くり返し単位分）を示したもので
ある。ここで、Ｐｌ，Ｐ２，Ｐ３，Ｐ４は、もう一方の
くりかえし単位の回路において、Ｄｌ６〜Ｄ，，に相当
する分から作成されたパリテイ和を受け取る端子であり
、Ｐ１を出力する回路は第５図でＰ７を作成する回路に
等しく、Ｐ２を出力する回路は、Ｐ８の回路に等しく、
以下Ｐ３を出力する回路はＰ５を出力する回路に、Ｐ４
を出力する回路は、Ｐ６を出力する回路にそれぞれ等し
い。ＤＯ−Ｄ３ｌはデータプロツクＤａ，Ｄ′Ｉ・・・
・・・ＤＳ５に相当する信号であり、シンドローム生成
のためＣｔ，ｃ：，ｃ二を端子Ｃｈｌ，Ｃｈ２，Ｃｈ３
）Ｃｈ４ラＣｈ５９Ｃｈ６に入力する。前述の具体的な
ハードウエア構成の一例を第６図に示す。ここで６１は
多入力パリテイ検査ツリーであつて、６１が次式に従つ
てパリテイ和を生成することを示している。なお他の信
号Ｓ，〜Ｓ５，Ｐ５〜Ｐ８についても同様である。ＳＯ
＝ＤＯ４ｄ２ｌｄ４４ｄ６（＋）Ｄ８ｌｄｌＯ（１）Ｄ
ｌ２４ｄｌ４４ｄｌ６ｌｄｌ８４ｄ２Ｏ４ｄ２２（＋）
Ｄ２４（＋）Ｄ２６４ｄ２８ｌｄ３ＯｌＣｈｌ９なお４
は排他的論理和を示す。

この第６図の回路を１つのくり返し単位として、第７図
に示すようにチエツクビツト生成回路を構成できる。

同じく、第６図のハードウエアをひとつのくり返し単位
として、第８図に示すシンドローム生成回路を作成でき
る。但し、ここで、信号名の前に「ｒ」を付加したもの
は、処理を受けたあとの信号を示す。即ち、Ｄ３ｌの処
理後の信号名称はＲｄ３ｌで表わしてある。第９図はシ
ンドロームデコード回路の１くりかえし単位の構成例で
あつて、ＰＬＡによつて構成している。

しかし、この回路は、他の、一般のゲートによる組合せ
回路によつても当然構成可能である。ここでは、上半部
のＡＮＤアレーと下半部の０Ｒアレーとからなり、その
ＡＮＤアレーの入力を２ビツト毎にデコードする構成を
有するＰＬＡを使用しており、例えば、入力Ｓ。，Ｓｌ
はデコードされ、ＡＮＤアレーの上から４行までの信号
で示される値を持つている。

ここで、ＳＯ，Ｓｌ．・．Ｓｌｌは前記シンドロームデ
コード回路から受信したシンドロームビツトである。デ
コードは次のようにして行う。

例として、列ＤｌＯを考える。列ＤｌＯの列ベクトルは
次式で示される。誤りパターンは（０，１）（１，０）
（１，１）の３種存在する。

この３種の場合について、論理レベル「１」となるＡＮ
Ｄアレー入力は次表に示す通りである。よつて、誤り位
置指摘信号Ｅ２Ｏ，ｅ２，は次式で得られる。

以上はＤｌＯの列について示したが、同様にして、他の
すべての列に対するデコード回路も作成できる。

第９図において、１０で示す０Ｒアレーの出力信号Ｅ。

−Ｅ３，は、ＤＯ−Ｄ３，に相当する誤り位置指摘信号
であつて、当該ビツトに誤りが発生すれば、「１」とな
る。ＣＯＲ信号は誤りの訂正を行つたことを示す信号で
あり、論理的にはＥ。

−Ｅｌ５の論理和を取つたものに等しい。又ＣＢＥ信号
はチエツクプロツクに誤りＢ３あつたことを示す信号で
ある。第９図のシンドロームデコード回路を使用したシ
ンドロームデコード回路４及び誤り訂正回路５の全体を
第１０図に示す。誤り訂正回路５は、２入力排他的オア
回路ＥＸＯＲから成り、誤り位置指摘信号Ｅｉが「１」
レベルになると６受信信号Ｒｄｉを反転する。第１１図
は誤り検出回路であつて、１１０はオアゲート、１１１
ａ，１１１ｂはアンドゲート、１１５は反転出力端子を
有するオアゲートである。

シンドロームビツトＳ１〜Ｓｌｌ中に少なくとも「１」
が１つあればオアゲート１１０の出力１１４は「１」と
なり、誤りｆ）３検出されたことを報知する誤り検出信
号ＥＲＲが出力される。２個のくり返し単位毎の誤りの
訂正を行つたことを示す信号ＣＯＲ（ＣＯＲＯ，ＣＯＲ
ｌ）と、チエツクプロツクに誤りが生じている事を示す
信号ＣＢＥ（ＣＢＥＯ，ＣＢＥｌ）はこの第１１図の回
路で処理され、アンドゲート１１１ｂの出力１１３は誤
りの訂正を行つたことを示す信号ＣＲＲとなる。

もし信号ＣＲＲが「Ｏ」で信号ＥＲＲが「１」であれば
アンドゲート１１１ａの出力１１２が「１」となり、誤
り訂正不可能な誤りの検出、即ち、二重のプロツク誤り
の検出信号ＤＥＤｂ｛出力される。以上説明したように
、本発明の誤り検出・訂正方式は、任意の符号長に対し
て、あらかじめ区切られたｂビツトのプロツク中の１個
のプロツクに生じた１ビツト以上の誤りを訂正し、２個
のプロツクにまたがつて生じた２ビツト以上、２・ｂビ
ツト以下の誤りを検出する能力を有することから、特に
、複数ビツト出力のメモリ素子に対して、その障害を救
済する上で効果的である。また、その冗長は、ｂ＝２、
情報長６４ビツトの場合では、１２ビツトであり、従来
知られている２ビツトのあらかじめ区切られたプロツク
中の１個のプロツクに生じた１ビツト以上の誤りを訂正
し、ランダム的な２ビツトの誤りを検出する能力を持つ
符号の冗長に比べても少い。

また、本発明のプロツク誤り検出・訂正方式は、情報長
６４ビツトの場合について、その符号化、復号化回路に
２のくり返し性を与えた構成とすることＢ３できる。

【図面の簡単な説明】

第１図は本発明の実施例のプロツク図、第２図Ａ，ｂ，
ｃは本発明の実施例の情報長１３２ビツトのＳ２ＥＣ−
Ｄ２ＥＤ符号のＨマトリクスの説明図、第２Ａ図は第２
図Ａ，ｂ，ｃの配置説明図、第３図Ａ，ｂ，ｃは第２図
Ａ，ｂ，ｃ（７）Ｈマトリクスに対してチエツクプロツ
クを持つようにした変形Ｈマトリクスの説明図、第３Ａ
図は第３図Ａ，ｂ，ｃの配置説明図、第４図は本発明の
実施例の誤り検出訂正のＨマトリクスの説明図、第５図
は本発明の実帷例の誤り検出訂正の１繰返し嚇位のＨマ
トリクスの説明図、第６図は本発明の実抱例のチエツク
ビツト生成回路の１繰返し弔位の回路図、第７図はチエ
ツクビツト生成回路のプロツク図、第８図はシンドロー
ム生成回路のプロツク図、第９図はシンドロームデコー
ド回路の１繰返し単位の回路図、第１０図はシンドロー
ムデコード回路と誤り訂正回路とのプロツク図、第１１
図は誤り検出回路のプロツク図である。 １はチエツクビツト生成回路、２はプロセツサ、３はシ
ンドローム生成回路、４はシンドロームデコード回路、
．５は誤り訂正回路、６は被符号化情報、７はチエツク
ビツト、８は被符号化情報に対応する出力情報、９はプ
ロセツサの出力情報６１０は誤り位置指摘情報、１１は
誤り訂正後の情報、１２はシンドロームビツトである。

Claims (1)

1. 【特許請求の範囲】 １ 各々ｂビットから成る２ｋ個のデータブロックＤ＿
   ０、Ｄ＿１、…Ｄ＿２＿ｋ＿−＿１を一つの被符号化情
   報とし、該被符号化情報に付加すべき各々ｂビットより
   成るｒ個のチェックブロックＣ＿１、Ｃ＿２、…Ｃ＿ｒ
   を、▲数式、化学式、表等があります▼ の関係式に従つて発生するチェックビット生成回路を備
   え、前記データブロックとチエツクブロツクとが記憶、
   伝送等の処理をされた後の前記データブロック及びチェ
   ックブロックに対応するデータブロックＤ′＿０、Ｄ′
   ＿１、…Ｄ′＿２＿ｋ＿−＿１及びチエツクブロツクＣ
   ′＿１、Ｃ′＿２、…Ｃ′＿ｒから次式に従ってシンド
   ロームビツトＳ＿１、Ｓ＿２、…Ｓ＿ｒを生成するシン
   ドローム生成回路▲数式、化学式、表等があります▼ 前記シンドロームビツトのデコードを行なうシンドロー
   ムデコード回路、該シンドロームデコード回路の出力の
   誤り位置指摘情報により前記データブロックＤ′＿０、
   Ｄ′＿１、…Ｄ′＿２＿ｋ＿−＿１の誤りを訂正する誤
   り訂正回路を備え、（但し、ｉ＝１、２、…ｒ、ｂ＞２
   、ｈ＿ｉ＿ｊ及びｈ＿ｒ＿−＿ｉ＿＋＿１＿，＿ｊ＿−
   ＿ｋは有限体ＧＦ（２＾ｂ）上の元で単一ブロック誤り
   訂正・二重ブロック誤り検出符号のＨマトリックスのチ
   ェックブロックに相当する列を除くｉ行ｊ列及びｒ−ｉ
   ＋１行ｊ−ｋ列の要素である。 ）１個のブロック内に１ビット以上ｂビット以下の誤り
   について訂正し、２個のブロックにまたがつて生じた２
   ビット以上２・ｂ以下の誤りを検出することを特徴とす
   るブロック誤り検出訂正方式。