JPH0916422A - 誤り検出・訂正方法 - Google Patents

Abstract

(57)【要約】 【目的】 情報語中の特定のブロックを強く保護する誤
り訂正方法を提供する。 【構成】 入力データ１は符号化回路２によって検査ビ
ットが付加され、チャネル３を通して通信路４に送出さ
れる。通信路４を経て受信された情報語はチャネル５を
通して復号回路６に入力される。復号回路６では、受信
した情報語Ｄにパリティ検査マトリクスＨの転置行列Ｈ
^T を乗算してシンドロームＳを生成し、さらにこのシン
ドロームＳのパターンに基づいて、誤り訂正を行う。誤
りが訂正され、復号が完了した情報は出力データ７とし
て出力される。また偶数誤りがある場合は、誤り検出出
力２４が出力される。パリティ検査マトリクスＨは６−
１に示すような構造を持ち、１ビット誤り訂正に加え
て、情報語中の特定のブロック中のすべての誤り訂正、
２ビット誤り検出の機能を有する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、誤りを自動訂正して装
置・システムの信頼性を向上させるための誤り訂正方法
に関し、特に、温度、振動、ノイズ等による作業環境の
劣悪な状況下において正常動作させなければならない産
業用装置・システム、または医療、航空宇宙、公共シス
テム等、信頼性の要求される装置・システムにおいて利
用される誤り訂正方法に関する。

【０００２】

【従来の技術】誤りを自動訂正する方法としては、例え
ば次のように、従来より多くの方法が存在する。 （１）回路・装置を三重化してその出力の多数決をとる
方法。 （２）回路・装置を二重化して各回路・装置に検査機能
をもたせ、検査機能により一方が誤りを検出したら他方
の出力を正常な出力とする方法。 （３）誤りを検出したら再度動作をやり直す方法。 （４）誤り訂正符号を適用して誤りの自動訂正を行う方
法。

【０００３】本発明は、このうち誤り訂正符号による方
法に関するものである。誤り訂正符号は従来より符号理
論として研究され、各種機能を有する符号が計算機、通
信、ＡＶ機器の分野において多く実用に供されている。
特に、高速な自動誤り訂正が要求される計算機の分野に
おいては、半導体メモリを使用した装置を対象に、ノイ
ズ等によるソフトエラーを考慮して、１ビット誤り訂正
・２ビット誤り検出の機能を有する符号が主に使用され
ている。

【０００４】ここで、誤り訂正符号の基本的な技術につ
いて、簡単に説明する。図１２は誤り訂正符号を使用し
た一般的な自動誤り訂正方式を示す図である。図１２に
おいて、入力データ９１は符号化回路９２に与えられ
る。符号化回路９２は後述のパリティ検査マトリクスに
基づいて、検査ビットを付加する。このように符号化さ
れた情報を「情報語」と呼ぶ。情報語は送信情報として
チャネル９３を介して通信路９４へ送られる。通信路９
４は送信情報を伝達し、通信先への受信情報を与える。
受信情報はチャネル９５を介して復号回路９６へ送ら
れ、復号回路９６は受信情報を解読して再生情報すなわ
ち出力データ９７を生成する。

【０００５】しかし通信路９４の途中には、誤動作や外
部ノイズ等の外乱要因（図中ノイズ源９９として示す）
があり、チャネル９５に現れる受信情報は必ずしも正し
くなく、誤りを含む可能性を有する。この誤りを訂正す
るのが復号回路９６の役割である。なお、この図は通信
システムを想定したものであるが、実際にはメモリシス
テムにも誤り訂正符号を応用することも多い。その場合
は、通信路９４が実際のメモリ素子となり、チャネル９
３はメモリへの書き込み、チャネル９５はメモリからの
読み出しに相当すると考えればよい。

【０００６】情報語を一般にｎビットの２進数であらわ
し、Ｄ＝（ｄ_{0 ,} ｄ_1,...,ｄ_n-1 ）とするとき、この中
には符号により決定されるｒビットの検査ビットを含
む。符号化の方法は、０と１の２進数を要素とするｒ行
ｎ列のパリティ検査マトリクス（以下Ｈマトリクスと呼
ぶ）で表現する。誤りを含まない情報語ＤとＨマトリク
スの間には次の関係が成立する。すなわち、Ｄとして予
め次の関係が成立するようにその検査ビットが決められ
ている。

【０００７】

【数２】 Ｄ・Ｈ^T ＝０ ‥‥‥‥（２） ここで、Ｈ^T はＨの行と列を入れ換えた転置行列であ
る。このとき、何らかの原因でＤ中に誤りが生起する
と、上記（２）式左辺の計算結果は０（ｒビットの零ベ
クトル）ではなくなる。この結果は、シンドロームＳと
呼ばれ、ｒビットからなるベクトルで表現される。すな
わち、Ｓ＝０であれば誤りなしと判定し、Ｓ≠０であれ
ば誤りを検出し、そのＳのパターンをＨに基づき解析す
ることにより誤りの位置と大きさを求め訂正する。これ
が、符号による誤り訂正の原理である。必要とする機能
を有する符号をいかに構成するかは、いかにマトリクス
Ｈを構成するかということに等しい。

【０００８】最近、メモリ素子の急激な発展により１素
子あたり４、８、１６ビット等の複数ビットの同時入出
力を有する素子が中心的になりつつある。このような素
子を使用した装置・システムにおいては、特許第１２３
９４３０号（昭和５９年１１月１３日）等に見られるよ
うな１ビット誤り訂正・２ビット誤り検出・１バイト誤
り検出、あるいは特許第１２３６４１１号（昭和５９年
１０月１７日）に見られるような１バイト誤り訂正・２
バイト誤り検出の機能を有する符号が使用されるように
なっている。ここでバイトとは前記４、８、１６等の複
数ビットの単位を意味する。

【０００９】前述のように、情報語には種々の物理的要
因により誤りが発生し、訂正が必要となる。誤りは情報
語のどの部分にも発生し得るが、情報語中には一般に非
常に重要な情報部分を含むことが多くあり、この部分に
生じた誤りはすべて訂正したい場合がある。例えば、情
報語中のアドレス情報、制御情報やデータベース等にお
けるポインタ情報等がこれに該当し、他のデータ部分に
比較し非常に重要な情報を含む。この部分における誤り
は、その後の処理に重大な影響を及ぼすことは明らかで
ある。従って、当該重要部分に対し、語中の他の部分に
生じた誤りによる影響をできるだけ受けないような手段
を講じる必要がある。すなわち、情報語中の特定部分を
他と比較して強く保護する必要があり、情報語中で保護
の度合いが異なる部分を内在した符号が要求されてい
る。

【００１０】このような背景の下では、前述の１ビット
誤り訂正・２ビット誤り検出符号や１バイト誤り訂正・
２バイト誤り検出符号では十分その要求を満足できない
ことは明らかである。

【００１１】一般に、情報語中において保護する度合い
をディジット単位に変化させた符号として、従来、例え
ば、IEEE Transactions on Information Theory, vol.
IT-3, no.4, pp. 600-607, October 1967 に掲載された
B. Masnick と J. Wolfによる論文“On Linear Unequa
l Error Protection Codes”に示すような Unequal Err
or Protection Code（ＵＥＰ符号）が提案され理論的研
究が行われてきた。

【００１２】

【発明が解決しようとする課題】しかし、これまでのＵ
ＥＰ符号は復号が大変複雑であり、また検査ビットを非
常に多く必要とすることから経済的観点より大きな問題
を有していた。

【００１３】特に、計算機用情報語を考えると、語中で
決められた位置に存在するアドレス情報、コントロール
情報等の複数ビットのブロックに対し、ブロック中の各
ビットは一様な度合いで誤りから保護するモデルで十分
な場合が多い。ただし、ブロック内に対する保護の度合
いとブロック外に対する保護の度合いは異なり、当然前
者が強い。このときも、ブロック外の各ビットに対する
保護は一様でよい。さらに、外部からの物理的影響によ
る情報語中の任意のビットに生じる１ビット誤りを訂正
する機能を付加し、これに先の固定位置に存在するブロ
ック内で生起したすべての誤りを訂正する機能を有する
符号モデルで実用的に十分である。

【００１４】このような単純なモデルであれば、必然的
に復号が容易であり検査ビット数も少ないはずである。
この１ビット誤り訂正・２ビット誤り検出の機能は、半
導体メモリ素子における（たとえ、複数ビット出力素子
においても）主な誤りはランダムな１ビット誤りであ
り、またメモリ以外においても外部雑音による誤りは１
ビットであることが多いことに根拠を置いている。

【００１５】情報語に対する保護の度合いに関する以上
のような考察を踏まえ、従来の複雑な符号に代わる、実
用的な誤り訂正方法が求められている。本発明は、この
ような点に鑑みてなされたものであり、誤りに対して特
に保護を必要とする情報語中の一部分について、この部
分に生じたすべての誤りを正しく訂正する機能を有し、
また高速かつ経済的に実現し得る誤り訂正方法を提供す
ることを目的とする。

【００１６】特に、本発明ではブロック中のいかなる誤
りも訂正し、また情報語中に生じたランダムな１ビット
誤りを訂正し２ビット誤りを検出するだけでなく、ブロ
ックの誤りと１ビットの誤りまたは２ビット誤りが同時
に生起した場合でも、これらを検出し、誤ってブロック
中の誤りとして誤訂正することを避けた符号を開示す
る。すなわち、ブロック内の保護の度合いは、ブロック
内で生じたすべての誤りは訂正できること、またブロッ
ク外で生じた１ビットまたは２ビットの誤りが加わって
もこれらを検出し、ブロック内の情報は保護されるこ
と、の点で最も強い度合いである。一方、ブロック外で
は任意のランダムな１ビット誤りであればこれを正しく
訂正し、２ビットの誤りであれば確実に検出するという
保護の度合いであり、前者に比較すれば小さい。これに
より、当該ブロックを誤りから強く保護した符号を提供
するものである。

【００１７】

【課題を解決するための手段】本発明では上記課題を解
決するために、検査ビットが付加され、かつｂ（ｂ＞
２）ビットのブロックを１個有する情報語に対する誤り
検出・訂正方法において、パリティ検査マトリクスＨ

【００１８】

【数３】

【００１９】ただし前記パリティ検査マトリクスＨの各
部分行列は、Ｉ_b ＝ｂ×ｂ単位行列、Ｉ_r ＝ｒ×ｒ単位
行列、Ｐ＝偶数重みを有する（ｒ−ｂ）次の相異なるｂ
個の列ベクトルから構成される（ｒ−ｂ）×ｂの行列、
Ｑ＝整数１の２進表現を最大（２^r-b-1 −ｂ−１）個の
列ベクトルにもつ最大ｂ×（２^r-b-1 −ｂ−１）の行
列、Ｍ_e ＝偶数重みを有する最大（２^r-b-1 −ｂ−１）
個の列ベクトルから構成される最大（ｒ−ｂ）×（２
^r-b-1 −ｂ−１）の行列、ただし前記Ｍ_e の列ベクトル
は、前記行列Ｐを構成するｂ個の列ベクトルｐ_i （０≦
ｉ≦ｂ−１）において、ｐ₀ とｐ_j （１≦ｊ≦ｂ−１）
の和ベクトルｕ_j を求め、偶数重みを有する（ｒ−ｂ）
次ベクトルのうち、前記列ベクトルｐ₀ と前記和ベクト
ルｕ_j を除く相異なる非零列ベクトルを最大（２^r-b-1
−ｂ−１）個選んで前記Ｍ_e の列ベクトルとし、０＝最
大（２^r-b-1 −（ｒ−ｂ））個のｂ次の零列ベクトルか
ら構成される零行列、Ｍ_O ＝３以上の奇数重みを有する
（ｒ−ｂ）次の相異なる列ベクトルから構成される最大
（ｒ−ｂ）×（２^r-b-1 −（ｒ−ｂ））行列、に基づい
て符号化された前記情報語に、前記パリティ検査マトリ
クスＨの転置行列を乗算してｒビットのシンドロームＳ
を生成し、すべては零でない前記シンドロームＳに基づ
いて、誤りの検出・訂正を行う誤り検出・訂正方法が提
供される。

【００２０】本発明ではさらに、誤りの検出・訂正にお
いて、前記シンドロ−ムＳが、前記パリティ検査マトリ
クスＨを構成する列ベクトルｈ_i （０≦ｉ≦ｎ−１）に
一致する場合は、対応する前記情報語のｉ番目のビット
を訂正し、前記シンドロ−ムＳが、前記列ベクトルｈ_i
のいずれとも一致しない場合は、前記シンドロームＳの
上位ｂビットからなるベクトルＳ_F に前記行列Ｐの転置
行列Ｐ^T を乗算して得られるベクトルＳ_F ・Ｐ^T が、前
記シンドロームＳの下位（ｒ−ｂ）ビットからなるベク
トルＳ_P に一致するとき、前記ブロックの誤りと判定
し、前記シンドロームＳの上位ｂビットを誤りパターン
として前記ブロックの誤りを訂正する誤り検出・訂正方
法が提供される。

【００２１】

【作用】パリティ検査マトリクスＨに基づいて検査ビッ
トが付加され、かつｂビットのブロックを１個有する情
報語を受信すると、受信した情報語にパリティ検査マト
リクスＨの転置行列を乗算し、生成されたシンドローム
Ｓに基づいて、誤りの検出・訂正を行う。

【００２２】また、誤りの検出・訂正においては、最初
にシンドロームＳとパリティ検査マトリクスＨの列を比
較し、１ビット誤りを検出して訂正する。さらにＳ_F ・
Ｐ^TとＳ_p とを比較し、ブロック内の誤りを検出して訂
正する。

【００２３】

【実施例】以下、本発明の実施例を図面に基づいて説明
する。図１は本発明の概略構成を示すブロック図であ
る。図１において、入力データ１は符号化回路２によっ
て検査ビットが付加され、チャネル３を通して通信路４
に送出される。通信路４を経て受信された情報語はチャ
ネル５を通して復号回路６に入力される。復号回路６で
は、受信した情報語Ｄにパリティ検査マトリクスＨの転
置行列Ｈ^T を乗算してシンドロームＳを生成し（図中６
−１）、さらにこのシンドロームＳのパターンに基づい
て、誤り訂正を行う（図中６−２）。誤りが訂正され、
復号が完了した情報は出力データ７として出力され、別
途用途に使用される。偶数誤りがある場合は、誤り検出
出力２４が出力され、例外処理の起動などに使用され
る。

【００２４】ここで、本発明における符号化と復号の方
法は、前記のパリティ検査マトリクスＨ（以下Ｈマトリ
クス）によって特徴付けられる。Ｈマトリクスは、図中
６−１に示すような特徴ある構造を有し、その詳細を図
２を使用して説明する。

【００２５】図２は本発明の誤り訂正方法の情報語のフ
ォ−マット、およびパリティ検査マトリクスＨの構成を
示す図である。図２（ａ）は長さｎビットを有する情報
語のフォーマットを示す。すなわち、長さｂビットを有
するブロックを先頭に位置付け、ｒビットからなる検査
ビットを最後に置く。ブロックは、検査ビットと重なら
なければどこの位置でもよいが、ここでは一般性を失う
ことなく先頭に置くこととする。もし、実際に先頭位置
でなければ、それに応じてＨマトリクスの中の対応する
部分マトリクスをＨの中で移動すればよい。

【００２６】図２（ｂ）は、このような情報語をベクト
ルで表現したものである。ｄ₀ からｄ_b-1 がｂビットの
ブロック情報であり、ｄ_n-r からｄ_n-1 がｒビットの検
査ビットである。

【００２７】図２の（ｃ）はパリティ検査マトリクス
（Ｈマトリクス）の構成を示す。Ｈマトリクスは、部分
マトリクスＨ_F 、Ｈ₁ 、Ｈ₂ 、Ｉ_r からなる。図２の
（ｄ）に示すように、Ｈ_F はｂ列からなり、上段にｂ×
ｂの単位行列Ｉ _b 、下段に異なる偶数重みを有するｂ個
の列ベクトルから構成される（ｒ−ｂ）×ｂの行列Ｐよ
りなる。ここで「重み」とは、列ベクトルの要素のうち
値が１である要素の数を意味する。Ｈ₁ 上段の行列Ｑ
は、整数１の２進表現を最大（２^{r- b-1} −ｂ−１）個列
ベクトルに持つ、最大ｂ×（２^r-b-1 −ｂ−１）の行列
である。整数１の２進表現とは、すなわちベクトルの最
初の要素のみが１で、残りの要素はすべて０であるよう
なベクトルを意味する。Ｈ₁ の下段は偶数重み列ベクト
ルから構成される最大（ｒ−ｂ）×（２^r-b-1 −ｂ−
１）の行列Ｍ_e である。行列Ｍ_e は次のステップ〔Ｓ１
１〕〜〔Ｓ１４〕の方法で求められる。 〔Ｓ１１〕行列Ｐのｂ個の列ベクトルをそれぞれｐ₀ ，
ｐ₁...，ｂ _b-1とする。 〔Ｓ１２〕ｐ₀ ，ｐ_i （１≦ｉ≦ｂ−１）の和をｕ_i と
する。 〔Ｓ１３〕重みが偶数のベクトルのうち、ｐ₀ ，ｕ
_i （１≦ｉ≦ｂ−１）を除く非零列ベクトルを最大２
^r-b-1 −ｂ−１個用意する。 〔Ｓ１４〕これらを用いて行列Ｍ_e を次のように求め
る。

【００２８】Ｍ_e ＝〔ｖ₁ ，ｖ₂ ........，ｖ_m 〕（ｍ
≦２^r-b-1 −ｂ−１） また、Ｈ₂ は、上段に最大ｂ×（２^r-b-1 −（ｒ−
ｂ））の零行列０、下段に重み１を除く相異なる奇数重
み列ベクトルから構成される最大（ｒ−ｂ）×（２
^r-b-1 −（ｒ−ｂ））の行列Ｍ₀ からなる。さらにＩ_r
はｒ×ｒの単位行列である。Ｈ_F 、Ｉ_r はそれぞれブロ
ック、検査ビット部に対応している。

【００２９】なお本符号の情報語の最大ビット長ｎ_max
は、

【００３０】

【数４】 ｎ_max ＝２^r-b ＋ｂ−１ ‥‥‥‥（４） にて表すことが出来る。後述の機能を有する符号として
は、これが理論的最大長であることが証明できる。

【００３１】本発明で開示する符号、すなわち図２に示
すＨマトリクスは、次の３つの機能を有している。 〔機能１〕１ビット誤り訂正 〔機能２〕２ビット誤り検出 〔機能３〕ブロック中のすべての誤り訂正 これらの機能をすべて有する符号であれば、前述のブロ
ック中のすべての誤りの他に、ブロック外で１ビット誤
りが加わっても、これらを確実に検出できることは、容
易に証明できる。さらに、ブロック中のすべての誤りの
他にブロック外で２ビット誤りが加わっても、これらを
確実に検出し、少なくともブロックの誤りとして誤訂正
しないことも同様に証明できる。また、本機能を有する
符号は、ブロックの誤りに加え、ブロック外で１ビット
の誤りが生じても、これらを検出するだけではなく、正
しく訂正できる符号であることも証明できる。

【００３２】次に、本発明の符号、すなわち第２図に示
すＨマトリクスが、上記３つの機能を満足していること
を証明する。〔機能１〜３〕の訂正および検出ができる
ためには、一般に、それぞれの誤りによるシンドローム
が、すべて相異なることが証明できればよい。

【００３３】まず、〔機能１〕の１ビット誤り訂正が実
現できることは、Ｈマトリクス中のすべての列ベクトル
が相異なることから証明できる。すなわち、１ビット誤
りによるシンドロームは、（２）式の左辺を計算して、
そのｒビットのベクトルとして求められ、これがＨマト
リクスのいずれかの列ベクトルと一致すれば、その列に
対応するビットが誤りとして訂正できる。従って、Ｈ中
の列ベクトルがすべて異なれば、１ビットの誤りが特定
でき、訂正できることになる。

【００３４】次に〔機能２〕の２ビット誤り検出につい
ては、２ビット誤りによるシンドロームが１ビット誤り
およびブロック誤りによるシンドロームと一致しないこ
とを示す必要がある。本符号のＨマトリクスが、すべて
奇数重みの列ベクトルから構成されており、２ビット誤
りのシンドロームは偶数重みとなることから、１ビット
誤りのシンドロームと一致することはない。次に、
Ｈ₁ 、Ｈ₂ 、Ｉ_r に相当する情報部にそれぞれ２ビット
誤りが生じたとき、ブロック誤りによるシンドロームと
異なることは明らかである。また、Ｈ₁ に相当する情報
部に１ビットの誤りと、Ｈ₂ に相当する情報部に１ビッ
トの誤りが生じたとき、そのシンドロームは、上位ｂビ
ットが整数１の２進表現のパターン、下位（ｒ−ｂ）ビ
ットは重み奇数のパターンとなり、明らかにブロック誤
りによるシンドロームと異なる。同様に、Ｈ₂ とＩ_r に
相当する部分で、それぞれ１ビット誤りが生じた場合
も、ブロック誤りによるシンドロームと異なることは容
易に言える。最後に、Ｈ₁ とＩ_rに相当する情報部にそ
れぞれ１ビット誤りが生じた場合、シンドロームとして
上位ｂビットに重み２、下位ｒ−ｂビットに重み偶数の
パターンとなるときが問題であるが、上記〔Ｓ１１〕〜
〔Ｓ１４〕で述べたような行列ＰとＭ_e の関係により、
このシンドロームがブロック誤りによるシンドロームと
一致することはない。

【００３５】最後に〔機能３〕のブロック中のすべての
誤り訂正が実現できることは、Ｈ_Fの上段がＩ_b である
ことから、ブロック中にいかなる誤りが生じても、上位
ｂビットのシンドロームがそれぞれ異なることから容易
に証明できる。ただし、この時のシンドロームが、前記
１ビット誤りのシンドロームと一致しないことを証明し
なければならない。

【００３６】まず、Ｉ_r に相当する情報部（検査ビット
部）で生じた１ビット誤りによるシンドロームを考え
る。ブロック誤りのシンドロームに近いものは、Ｉ_b と
同じ部分マトリクスを有するＩ_r 中（検査ビット部）に
存在する。この部分における１ビット誤りによるシンド
ロームは、その上位ｂビットに重み１を有するが、その
下位（ｒ−ｂ）ビットはすべて零であることから、ブロ
ックの誤りによるシンドロームとは明らかに異なる。

【００３７】また、ブロック誤りによるシンドロームが
Ｈ₁ に相当する情報部の１ビット誤りと一致しないこと
は、行列Ｐと行列Ｍ_e の関係から明らかである。同様に
Ｈ₂ に相当する情報部の１ビット誤りのシンドロームと
一致しないことは、Ｈ₂ の上段に零行列を有することか
ら容易に証明できる。

【００３８】以上により、第２図に示すＨマトリクス
が、〔機能１〜３〕のすべてを満足することが証明でき
た。図３は、本発明の誤り訂正方法の処理手順を示すフ
ローチャートである。本発明によれば、受信された情報
語の誤りの検出および訂正は、次のステップによって行
われる。 〔Ｓ１〕情報語にＨマトリクスの転置行列を乗じ、ｒ次
のベクトルであるシンドロームＳを計算する。 〔Ｓ２〕シンドロームＳが零ベクトル（すべての要素が
零であるベクトル）かどうかを判断する。零ベクトルで
あれば、情報語に誤りがないものとし、復号を完了す
る。零ベクトルでない場合はステップＳ３へ進む。 〔Ｓ３〕シンドロームＳと、Ｈマトリクスを構成するｎ
個の列ベクトルｈ_i （０≦ｉ≦ｎ−１）各々とを比較す
る。もしシンドロームＳがｉ番目の列ベクトルｈ _i と一
致した場合は、ステップＳ４に進む。もし一致する列ベ
クトルがない場合は、ステップＳ５に進む。 〔Ｓ４〕情報語中のｉ番目のビットすなわちｄ_i を訂正
し、復号を完了する。 〔Ｓ５〕シンドロームＳの上位ｂビットからなるベクト
ルＳ_F に、Ｈマトリクスの部分行列Ｐの転置行列Ｐ^T を
乗算し、シンドロームＳの下位（ｒ−ｂ）ビットからな
るベクトルＳ_P と比較を行う。ここで、

【００３９】

【数５】 Ｓ_F ・Ｐ^T ＝Ｓ_P ‥‥‥‥（５） であれば、ブロック内にのみ誤りが存在すると認識し、
ステップＳ６へ進んで訂正を行う。一致しない場合は、
誤り検出とする。 〔Ｓ６〕シンドロームＳの上位ｂビット、すなわちＳ_F
を誤りパターンとして、ブロックを訂正し、復号完了す
る。

【００４０】以上のアルゴリズムによれば、最初にステ
ップＳ１とＳ２によって、誤りがないかどうかを判断
し、ステップＳ３とＳ４によって任意の位置の１ビット
誤りを訂正する。さらにステップＳ５によって、ブロッ
ク内の誤りであるか、ブロック外の誤りとの組合せであ
るかを判断する。ブロック内の誤りであれば、ステップ
Ｓ６にて、すべての誤りを訂正する。

【００４１】以下に本発明を具体的に実現する構成につ
いて述べる。図４は本発明の実施例である通信システム
の構成を示すブロック図である。入力データ１は符号化
回路２によって検査ビットが付加され、チャネル３を通
して通信路４に送出される。通信路４を経て受信された
情報語はチャネル５を通してシンドローム生成回路８へ
入力され、シンドローム９を作成する。また、このシン
ドロームはシンドロームデコード回路１０へ入力され、
具体的な誤り指示を与える誤りポインタ信号群１１を出
力し、訂正回路１２にて受信情報の誤りを反転し訂正す
る。訂正された情報はチャネル７を介して出力され、別
途用途に使用される。

【００４２】次に、以上の構成において、さらに具体的
な符号例を用いて、実際に符号化回路、復号回路が構成
できることを示す。図５は、ｂ＝４，ｒ＝８とした場合
におけるＨマトリクスを示す図である。情報語の長さ
は、（４）式よりｎ_max ＝１９ビットが最大となり、図
５のＤのように、ブロック長は４ビット、検査長は８ビ
ット、ブロックと検査部を除く部分の長さは７ビットと
なる。従って、ｄ₀ 〜ｄ₁₈の情報語に対し、ｄ₀ 〜ｄ₃
がブロック内のデータ、ｄ₁₁〜ｄ₁₈が検査ビットとな
る。情報語の各ビットと、Ｈマトリクスの各列とは、図
５のように対応している。Ｈマトリクスを構成する部分
行列の要件について図２の説明の中で述べたが、本実施
例においては、行列Ｐ、Ｑ、Ｍ_e およびＭ_o は図５に示
す通りである。

【００４３】図６は、本実施例における符号化回路２の
詳細を示す回路図である。この回路は図５に示すＨマト
リクスからｄ₁₁〜ｄ₁₈の検査ビットを構成するものであ
り、次の関係式から生成される。

【００４４】

【数６】

【００４５】ここで、プラス記号を丸印で囲った記号は
排他的論理和を表す。図６は、ｄ₀ 〜ｄ₁₀の１１ビット
からなるデータが、情報語Ｄのビットｄ₀ 〜ｄ₁₀として
そのまま出力され、検査ビットｄ₁₂〜ｄ₁₄は、それぞれ
ｄ_1,ｄ_2,ｄ₃ のデータ信号から直接生成されることを示
している。２−１１、２−１５、２−１６、２−１７、
２−１８は、上式からそれぞれ検査ビットを生成する回
路であり、多入力パリティチェッカである。すなわち、
論理１の入力信号の数が偶数である場合は、出力が０と
なり、奇数である場合は出力は１となる。なお２入力の
場合は、いわゆる排他的論理和ゲートに等しい。

【００４６】図７はシンドローム生成回路８の詳細を示
す回路図である。この回路は図５に示すＨマトリクスを
もとにして次に示す関係式で構成される。

【００４７】

【数７】

【００４８】ｓ₀ 〜ｓ₇ はシンドロームＳの各要素であ
り、８−０〜８−７はそれぞれ上式にもとづいて構成さ
れる多入力パリティチェッカである。復号回路８が受け
取る受信情報には、符号化回路から出力される送信情報
と区別するためにダッシュ（’）を付している。つま
り、符号化された直後の送信情報には誤りはないが、受
信情報には通信路（あるいはメモリ）を通過する段階
で、何らかの誤りが混入されている可能性があるため、
両者を区別して取り扱う。

【００４９】次に、作成したシンドロームに基づき、誤
り訂正を行う回路について述べる。図８はシンドローム
デコード回路１０の構成を示すブロック図である。１５
は、ｒビットのシンドローム信号群９を入力して1 ビッ
ト誤りに対する誤りビットポインタを生成する１ビット
誤りポインタ生成回路であり、特に情報語の下位ｎ−ｂ
ビットの誤りの位置を示すポインタ信号群１７を出力す
る。

【００５０】１９は、ｒビットのシンドロームからブロ
ック誤りを検出するブロック誤り検出回路であり、２０
はそこから出力されるブロック誤り検出信号Ｅ_B であ
る。２１は、ブロック誤りポインタ生成回路であり、ブ
ロック誤り検出信号Ｅ_B がオンになると、上位ｂビット
のシンドローム１８を用いて、ブロック中の各ビットに
対する誤りポインタを作成する。１６はそのポインタ信
号群であり、１ビット誤りポインタ生成回路１５で生成
されたブロック外の１ビット誤りに対するポインタ信号
群１７と合わせた計ｎビット分の信号が、最終的な誤り
ポインタ信号群１１としてシンドロームデコード回路１
０から出力される。

【００５１】２２は、２ビット誤り検出回路であり、２
ビット誤りを検出すると２ビット誤り検出信号２４を出
力する。この２ビット誤り検出信号２４はブロック中の
２ビット誤りに対しても、出力される。

【００５２】次に、図５に示す具体的な符号に対するデ
コード法とその回路について示すとともに、一般に、ｒ
ビットのシンドロームＳから図２に示す符号の一般的な
構成に対してデコードする方法についても併せて述べ
る。

【００５３】まず、Ｓ＝０のとき、（２）式で示すよう
に、受信情報には誤りなしと判断する。Ｓ≠０のとき、
誤り検出とみなし、ｒビットのシンドロームがＨマトリ
クス列ベクトルに一致するとき、その列ベクトルに対応
するビットの誤りとみなし、訂正のための信号を出力す
る。

【００５４】図９は図５に示す符号における１ビット誤
りポインタ生成回路１５の具体的回路を示す図である。
１９ビットの全情報に対し入力の８ビットのシンドロー
ムが、どのＨマトリクスの列ベクトルのパターンに一致
するかを調べる論理回路である。本実施例では、シンド
ロームを上位ｂビットのシンドロームＳ_F と、残りの
（ｒ−ｂ）ビットのシンドロームＳ_P とに２分割し、Ｓ
_F のパターンとしてはすべて零のパターンと重み１のパ
ターンしかないことから、１５−１９から１５−２３に
示す４入力ＡＮＤゲートを５個用意する。またＳ_P につ
いては、Ｈマトリクスの第５行・第５列以降を見て、１
２個の相異なる列ベクトルパターンがあることから、１
５−２４から１５−３５に示す４入力ＡＮＤゲートを１
２個用意する。そして１５−４から１５−１８に示す２
入力ＡＮＤゲートによって、ブロック部を除くＨマトリ
クスの各列ベクトルパターンに一致するように、１５−
１９から１５−３５のゲート出力を合成する。このよう
にして１５ビットのポインタ信号群１７（ｅ₄ 〜ｅ₁₈）
が生成される。

【００５５】図１０は、ブロック誤りポインタ生成回路
２１、ブロック誤り検出回路１９、２ビット誤り検出回
路２２の詳細を示す回路図である。図１０の中段はブロ
ック誤り検出回路１９であり、ブロックに生じたすべて
の誤りに対し、ブロック誤り検出信号２０を出力する回
路である。このとき、図２に基づく符号からブロック誤
り検出の論理を求める方法について述べる。Ｈマトリク
スにおけるＨ_F の構成から、次の関係式が成立する。

【００５６】

【数８】 Ｄ_F ・Ｉ_b ^T ＝Ｓ_F Ｄ_F ・Ｐ^T ＝Ｓ_P ‥‥‥‥（８） ここで、Ｄ_F は重要情報であるｂビットの長さを有する
ブロック情報である。式（８）からＤ_F を消去すると、

【００５７】

【数９】 Ｓ_F ・Ｐ^T ＝Ｓ_P ‥‥‥‥（９） の関係が成立する。従って、非零のシンドロームが式
（９）の関係を満足するとき、ブロック誤りであること
を検出する。具体的には、図５の符号の場合、

【００５８】

【数１０】 Ｓ＝〔Ｓ_F ｜Ｓ_P 〕 ‥‥‥‥（１０） ただし、Ｓ_F ＝〔ｓ_0,ｓ_1,ｓ_2,ｓ₃ 〕 Ｓ_P ＝〔ｓ_4,ｓ_5,ｓ_6,ｓ₇ 〕 より、次の関係が得られる。

【００５９】

【数１１】

【００６０】よって、次の信号Ｅ_B が１となるとき、ブ
ロック誤り検出となる。

【００６１】

【数１２】

【００６２】ここで、〔 〕は、その内に記述された関
係式が成立するとき「１」という値をとることを表し、
∩はＡＮＤを表す。図１０上段の２１は、ブロック誤り
検出信号Ｅ_B （図中２０）を基にブロック誤りをビット
単位に指摘するブロック誤りポインタ生成回路である。
Ｅ_B が１のとき、明らかにＳ_F はブロック誤りパターン
に等しいことから、ブロック誤りを各ビット単位に容易
に展開することができる。このときシンドロームＳが非
零であることの条件を信号２３により付与して、２１−
０から２１−３の３入力ＡＮＤゲートにより、ｅ₀ 〜ｅ
₃ のポインタ信号群１６を得る。

【００６３】図１０下段の２２は２ビット誤り検出回路
を示し、非零のシンドロームに対し、シンドロームの重
みが偶数のとき、２ビット誤り、さらに一般的に言う
と、偶数ビット誤りを検出したことになる。このための
論理を構成するために、図１０では、２２−２に示す８
入力ＯＲゲートにシンドローム全ビットを入力する。ゲ
ート２２−２の出力が１のとき、シンドロームが非零で
あることを意味する。ここで、２２−１のパリティチェ
ッカでシンドロームの重みが偶数であること（すなわ
ち、パリティチェッカの反転出力が１となること）を確
認し、２２−３のゲートでシンドロームの非零条件とＡ
ＮＤをとって、最終的な２ビット誤り検出信号２４を得
る。

【００６４】図１１は訂正回路１２の詳細を示す回路図
である。誤りポインタ信号群１１に基づき、受信信号中
に存在する誤りを反転して訂正する回路である。前述の
ように誤りポインタ信号群１１は、ポインタ信号群１６
と１７からなり、情報語の上位ｂビットのブロックに対
してはポインタ信号群１７により、また残りのｎ−ｂビ
ットに対してはポインタ信号群１６により訂正を行う。
すなわち、あるポインタ信号ｅ_i （０≦ｉ≦ｎ−１）が
‘１’であれば、対応する受信信号ｄ_i ' を排他的論理
和回路で反転して訂正を行う。また、ポインタ信号が
‘０’であれば、その受信信号には誤りは存在しないと
して受信信号がそのまま出力される。訂正後の出力信号
群は７として示される。なおシンドロームＳが零ではな
く、かつ誤りポインタ信号ｅ_i （０≦ｉ≦ｎ−１）がい
ずれも零であるときは、訂正不能な誤りがあることを意
味している。このような検出信号を出力することは、本
実施例の中では図示されてはいないが、単純な論理回路
によって実現し得るものである。

【００６５】図６から図１１の回路図で明らかなよう
に、本発明の誤り訂正方法を実行する回路は、比較的単
純な組合せ論理回路のみで構成されている。したがって
集積回路にて容易に実現可能で、その符号化および復号
の動作は高速である。このような回路を通信制御回路に
組み込むことにより、信頼性の高いシステムが実現でき
る。

【００６６】以上は、図５に示すｂ＝４，ｒ＝８で、デ
ータ長が１９ビット、検査長８ビットの符号を中心に示
したが、今まで述べたように本発明に係わる符号の構成
は、任意のｂおよびｒ，ｎに対し構成可能であることは
明らかである。また、重要な情報を有するブロックは、
実施例では情報語の先頭に位置するものとしたが、ブロ
ックは任意の位置で同様に構成することができる。すな
わち、図２に示す本発明の一般的符号構成に対し、ブロ
ックの始まる位置に部分マトリクスＨ_F を移動すればよ
いことから明らかである。また、実施例で述べたすべて
の回路構成は全く同一でよく、Ｈ_F を移動したことによ
り、その分、一部の回路で入力信号の順序が移動するだ
けである。

【００６７】また、実施例の説明においては、通信シス
テムへの応用を想定したが、本発明をメモリシステムに
応用することもできる。その場合は、通信路４が実際の
メモリ素子となり、チャネル３はメモリへの書き込み、
チャネル５はメモリからの読み出しに相当すると考えれ
ばよい。符号化回路２や復号回路６の動作は通信システ
ムの場合も、メモリシステムの場合も全く同様であり、
これらをメモリ制御回路の一部分として組み込むことが
可能である。

【００６８】

【発明の効果】以上説明したように本発明では、アドレ
ス情報、制御情報等、その部分に誤りが生じると以降の
動作に甚大な影響を与えるような重要な情報部分を情報
語中に含むとき、これを強く保護するための従来にない
新たな符号構成と、その高速な訂正回路構成を与えるも
のである。これにより、この部分の任意の誤りが生じて
も、これらを高速かつ経済的に訂正することができ、本
符号による誤り訂正手法を採用した装置、システムの信
頼度を格段に向上させることができる。

【図面の簡単な説明】

【図１】本発明の概略構成を示すブロック図である。

【図２】本発明の誤り訂正方法の情報語のフォ−マッ
ト、およびパリティ検査マトリクスＨの構成を示す図で
ある。

【図３】本発明の誤り訂正方法の処理手順を示すフロー
チャートである。

【図４】本発明の実施例である通信システムの構成を示
すブロック図である。

【図５】本発明において、ｂ＝３，ｒ＝７とした場合の
Ｈマトリクスの例を示す図である。

【図６】符号化回路２の詳細を示す回路図である。

【図７】シンドローム生成回路８の詳細を示す回路図で
ある。

【図８】シンドロームデコード回路１０の構成を示すブ
ロック図である。

【図９】１ビット誤りポインタ生成回路１５の詳細を示
す回路図である。

【図１０】ブロック誤りポインタ生成回路２１、ブロッ
ク誤り検出回路１９、２ビット誤り検出回路２２の詳細
を示す回路図である。

【図１１】訂正回路１２の詳細を示す回路図である。

【図１２】誤り訂正符号を使用した一般的な自動誤り訂
正方式を示す図である。

【符号の説明】

１ 入力データ ２ 符号化回路、 ３、５ チャネル ４ 通信路 ６ 復号回路 ６−１ シンドローム生成 ６−２ 誤り訂正 ７ 出力データ ２４ 誤り検出出力

Claims (6)

【特許請求の範囲】
1. 【請求項１】検査ビットが付加され、かつｂ（ｂ＞２）
   ビットのブロックを１個有する情報語に対する誤り検出
   ・訂正方法において、 パリティ検査マトリクスＨ 【数１】 ただし前記パリティ検査マトリクスＨの各部分行列は、 Ｉ_b ＝ｂ×ｂ単位行列、 Ｉ_r ＝ｒ×ｒ単位行列、 Ｐ＝偶数重みを有する（ｒ−ｂ）次の相異なるｂ個の列
   ベクトルから構成される（ｒ−ｂ）×ｂの行列、 Ｑ＝整数１の２進表現を最大（２^r-b-1 −ｂ−１）個の
   列ベクトルにもつ最大ｂ×（２^r-b-1 −ｂ−１）の行
   列、 Ｍ_e ＝偶数重みを有する最大（２^r-b-1 −ｂ−１）個の
   列ベクトルから構成される最大（ｒ−ｂ）×（２^r-b-1
   −ｂ−１）の行列、 ただし前記Ｍ_e の列ベクトルは、 前記行列Ｐを構成するｂ個の列ベクトルｐ_i （０≦ｉ≦
   ｂ−１）において、ｐ₀ とｐ_j （１≦ｊ≦ｂ−１）の和
   ベクトルｕ_j を求め、 偶数重みを有する（ｒ−ｂ）次ベクトルのうち、前記列
   ベクトルｐ₀ と前記和ベクトルｕ_j を除く相異なる非零
   列ベクトルを最大（２^r-b-1 −ｂ−１）個選んで前記Ｍ
   _e の列ベクトルとし、 ０＝最大（２^r-b-1 −（ｒ−ｂ））個のｂ次の零列ベク
   トルから構成される零行列、 Ｍ_O ＝３以上の奇数重みを有する（ｒ−ｂ）次の相異な
   る列ベクトルから構成される最大（ｒ−ｂ）×（２
   ^r-b-1 −（ｒ−ｂ））行列、 に基づいて符号化された前記情報語に、前記パリティ検
   査マトリクスＨの転置行列を乗算してｒビットのシンド
   ロームＳを生成し、 すべては零でない前記シンドロームＳに基づいて、誤り
   の検出・訂正を行う誤り検出・訂正方法。
2. 【請求項２】前記誤りの検出・訂正は、 前記シンドロ−ムＳが、前記パリティ検査マトリクスＨ
   を構成する列ベクトルｈ_i （０≦ｉ≦ｎ−１）に一致す
   る場合は、対応する前記情報語のｉ番目のビットを訂正
   し、 前記シンドロ−ムＳが、前記列ベクトルｈ_i のいずれと
   も一致しない場合は、前記シンドロームＳの上位ｂビッ
   トからなるベクトルＳ_F に前記行列Ｐの転置行列Ｐ^T を
   乗算して得られるベクトルＳ_F ・Ｐ^T が、前記シンドロ
   ームＳの下位（ｒ−ｂ）ビットからなるベクトルＳ_P に
   一致するとき、前記ブロックの誤りと判定し、前記シン
   ドロームＳの上位ｂビットを誤りパターンとして前記ブ
   ロックの誤りを訂正することを特徴とする請求項１記載
   の誤り訂正方法。
3. 【請求項３】前記誤りの検出・訂正は、 前記シンドロームＳが非零で重みが偶数であることによ
   って、２ビット誤りを検出することを特徴とする請求項
   １記載の誤り検出・訂正方法。
4. 【請求項４】前記Ｓ・Ｇ_F ^T が前記ベクトルＳ_P に一致
   しないことによって、訂正不可能な誤りを検出すること
   を特徴とする請求項２記載の誤り検出・訂正方法。
5. 【請求項５】前記誤り検出・訂正方法は、情報通信シス
   テムに使用されることを特徴とする請求項１記載の誤り
   検出・訂正方法。
6. 【請求項６】前記誤り検出・訂正方法は、メモリシステ
   ムに使用されることを特徴とする請求項１記載の誤り検
   出・訂正方法。