JPS6041771B2 - 二重誤り訂正回路 - Google Patents

Description

【発明の詳細な説明】 本発明は二重誤り訂正回路に関し、特に並列データに対
する二重ランダム誤り訂正回路に関する。

データ処理装置のメモリには信頼性を向上させるために
、従来から主として単一誤り訂正兼二重誤り検出ハミン
グ符号が用いられてきた。

この符号化システムでは特定個数のデータビットに最少
個数のチェックビットを付加してメモリに記憶しておき
、メモリから読み出す時に生じる単一誤りを訂正し、か
つ又二重誤りを検出している。前記符号化システムの特
徴は付加されるチェックビットの個数が少なくて済むと
いうことと、簡単な回路によつて前記誤りが並列的に訂
正兼検出できることにある。しかしながら、メモリの信
頼性を更に向上させるには二重ランダム誤り訂正システ
ムを採用することが望ましい。この二重ランダム誤りは
、例えば、周知の二重誤り訂正■…符号すなわちボーゼ
シヨードウリ符号（Ｂｏｓｅ一Ｃｈａｕｄｈｕｒｉ符
号）によつても訂正される。しかしこのＢＣＨ符号を採
用すると並列的に二重誤りを訂正するための相当多量で
かつ複雑な論理回路が必要になるという欠点をもつてい
る比較的簡単な回路によつて二重誤りを訂正できる符号
には多数決論号可能二重誤り訂正符号がある。この符号
を用いれば二重ランダム誤りが多数決論理によつて並列
的に訂正され得る。特許公告公報昭和４奔一２０１３号
に記述される直交ラテン方陣符号は前記多数決論号可能
二重誤り訂正符号の良好な一例てある。前記直交ラテン
方陣符号では、ｍを１より大きい任意の整数とするとイ
個のデータビットに４ｍ個のチェックビットを付加する
ことにより二重ランダム誤りが訂正される。この符号を
用いた誤り訂正システムは簡単な多数決論理回路によつ
て二重誤りが並列的に訂正できるという利点を有してい
るものの、一個のデータビットに４ｍ個の多重なチェッ
クビットを付加する必要があるという、欠点を併せもつ
ている。したがつて前記直交ラテン方陣符号よりも少な
い冗長度を有する多数決論号可能二重誤り訂正符号を用
いた誤り訂正システムの実現が望まれる〔ここで冗長度
は冗長度■（チェックビットの個数）／（チェックビッ
トの個数＋データビットの個数）で定義され、前記ラテ
ン方陣符号の冗長度は４ｍ／（ｄ＋４ｍ）＝４／（ｍ＋
４）で与えられる〕。しかしながら、これまで上述のよ
うな二重誤り訂正システムは存在しなかつた。本発明の
目的は従来の多数決復号可能二重誤り訂正符号よりも少
ない冗長度を有する多数決復号可能二重誤り訂正符号を
用いた新規な二重誤り訂一正回路を提供することにある
。

本発明の二重誤り訂正回路はｍを３以上の任意の奇数と
して、ｄ＋艮（ｍ−１）個のデータビットに伍＋１個の
チェックビットを付加する符号−化回路と、前記データ
ビット及びチェックビットからシンドロームビツトを発
生する回路とこのシンドロームビツト発生回路の出力を
多数決論理によつて解続することによつて上記データビ
ット及びチェックビット内に生じた１個又は２個のラン
ダム誤りを訂正する多数決回路を有する復号回路とから
構成されている。

以下図面を参照して本発明の詳細な説明する。

第１図はデータ処理装置内におけるメモリと本発明の誤
り訂正回路との関係を示すブロック図で５ある。第１図
において符号化回路１は演算回路４において発生された
データからチェックビットを生成する。このデータはチ
ェックビットと共にメモリ２に貯えられる。後に必要と
するときこのデータはチェックビットと共にメモリ２か
ら読み出一され、復号化回路３によつて誤りを訂正され
た後に再び演算回路４に供給される。以下では、本発明
に用いる多数決復号可能二重誤り訂正符号の構成及び前
記符号の符号化回路１と復号化回路３の構成を一例をも
つて説明する。

最初にｍ＝５の場合を例として前記符号及び回路構成を
説明する。この場合、ｍ＝５であるから３１〔＝ｄ＋艮
（ｍ−１）〕個のデータビットに１６（＝伍＋１）個の
チェックビットを付加することとなり本発明で用いる二
重誤り訂正符号が得られる。

以下では前記３１個のデータビットをＤｌ，ｄ２，ｄ３
，・・，Ｄ３Ｏ，ｄ３ｌと表わし、前記１６個のチェッ
クビットをＣ。Ｏ，ＣｌＯ９Ｃｌｌ９Ｃｌ２９Ｃｌ３９
Ｃｌ４９Ｃ２Ｏ９Ｃ２ｌ９３Ｏ９Ｃ２４９Ｃ３Ｏ，Ｃ３
ｌ，・・，Ｃ３，と表わす。ここでＤ，及びＣＩＪは１
またはＯのいづれかの値をとる。本発明による符号化回
路１は次の関係式（１），（２），（３），（４）に則
してデータビットからチェックビットを発生する。（こ
こで以後の全ての式において１記号は排他的０Ｒを示し
、Σ４は排他的０Ｒに関する総和を示すものとする。）
チェックビットを発生する前記関係式（１），（２），
（３），（４）をそれらの係数を与える符号化行列ｊに
よつて表わすとすれば玩は第２図で与えられる。

但し、第２１１Ｆ５において空なる行列要素は０である
。第２図の行列比を用いれば前記関係式（１），（２）
，（３），（４）は次式のようなベクトルと行列の乗算
て表わされる。既に述べたように第１図の符号化回路１
は式（１），（２），（３）及び（４），あるいは式（
５）に則してデータビットとからチェックビットを発生
する。

例えばチェックビットＣｌＯは式（２）のようにデータ
ビットＤｌ，ｄ２，ｄ３，ｄ４，ｄ５及びＤ２６の排他
ビρＲをとることにより生成されるが、これは、第３図
のように６個の入力を有する排他的０Ｒ回路５によつて
容易に実現される。他の１４個のチェックビットＣｌｌ
９Ｃｌ２９Ｃｌ３？Ｃｌ４９Ｃ２Ｏ９Ｃ２ｌ９ｌ９Ｃ２
４９Ｃ′３０９Ｃ３１，・・・Ｃ３４を生成する回路も
同様式（２），（３）又は（４）に則してデータビット
の排他的０Ｒをとる回路によつて実現される。又チェッ
クビットＣ。Ｏは式（１）により、全てのデータビット
Ｄｌ，ｄ２，ｄ３，・・，Ｄ３Ｏ，ｄ３ｌの排他的０Ｒ
をとつて生成される式（１）及び（２）に着目すればＣ
。Ｏは次式（６）によつても表わされる。従つて式（６
）によればチェックビットＣ。

Ｏは第３図の回路で発生されるチェックビットＣｌＯ，
Ｃｌｌ，Ｃｌ２，Ｃｌ３及びＣｌ４の排他的０Ｒをとつ
て生成される。すなわち、ＣＯＯは第４図のように５個
の入力を．有する排他的０Ｒ回路６によつて発生される
。

以上のようにして生成された１帽のチェックビットＣＯ
Ｏ９Ｃｌｌ９Ｃｌ２９Ｃｌ３９Ｃｌ４９Ｃ２Ｏ９ｌ９Ｃ
２４９Ｃ知・・，Ｃ３４は３１個のデータビットＤｌ，
ｄ２，・・，Ｄ３ｌと共にメモリに書き込まれる。必要
に応じて、これ，らのチェックビット、データビットは
メモリから読み出される。以下においてはメモリから読
み出されたチェックビット、データビットにはダツシユ
記号を付けて表わすものとする。すなわち読み出しされ
たチェックビットはＣ″００Ｃ″１０Ｃ″１１，Ｃ１２
，σ１３９Ｃ５１４９Ｃ′２０９１９Ｃ′２４９σ３０
▼０９Ｃ′３４と表わし、データビットはｄ″１，ｄ″
２，・・，ｄ″ょと表わすものとする。メモリから読み
出されたこれらのビットに生じた２個以下の誤りはデコ
ーダ（復号化回路）によつて訂正される。以下において
デコーダについて説明する。第５図はデコーダのブロッ
ク図である。

第５図のようにデコーダ４０はシンドロームビツト発生
回路２０と誤り訂正実行回路２１とから構成されている
。メモリ２から読み出された前記３１個のデ・ータビツ
ト及び１帽のチェックビットはまずシンドロームビツト
発生回路２０に入力し１帽のシンドロームビツトに変換
される。このシンドロームビツトには誤りを訂正するの
に必要な情報が含まれており、この情報を誤り訂正実行
回路２１が解読して誤り訂正を実行する。以下において
、まずシンドロームビツト発生回路２０について説明す
る。シンドロームビツト発生回路２０は１帽のチェック
ビットＣＯＯ９ＣｌＯ９Ｃｌｌ９Ｃｌ２９Ｃｌ３９Ｃｌ
４９Ｃ２Ｏ９゜Ｏ９Ｃ２４９Ｃ３Ｏ９゜゜９Ｃ３４に対
応する１帽のシンドロームビツトＳＯＯ９ＳｌＯ９Ｓｌ
ｌ９Ｓｌ２９Ｓｌ３９Ｓｌ４９Ｓ２Ｏ９ｌ９Ｓ２４９Ｓ
珈０９Ｓ３４を発生するＯ例えばＣｌＯに対応するシン
ドロームビツトＳｌＯは以下のように発生される。Ｃｌ
Ｏを発生する式は（２）式よりＣｌＯ＝Ｄｌ４ｄ２ｌｄ
３４ｄ４４ｄ５４ｄ８であるがこれは次式のように書き
直される。シンドロームビツトＳｌＯは上式の右辺Ｄｌ
，ｄ２，ｄ３，ｄ４，ｄ５，ｄぉ，ＣｌＯをそれぞれ読
み出された時の記号ｄ″１，ｄ゛２，ｄ″３，ｄ″４，
ｄ″５，ｄ″ぉ，ｃ″１０におきかえて得られる。

すなわちＳｌＯは次の式によつて発生される。ＳｌＯ＝
ｄ″１４ｄ″２４ｄ″３１ｄ″４４ｄ″５４ｄ″２６１
Ｃ″１０同様にしてチェックビットの発生式（１），（
２），（３），（４）より以下のシンドロームビツトの
発生式（８），（９卜，［株］，（１１）が得られる。

すなわち 一ーー −ーー −
ーー −“ノ上式（８），（９），Ａｌ，（１１）は第
２図の符号化行列塊を用いれば下式のように行列とベク
トルの演算で表わすことができる。シンドロームビツト
発生回路２０は上記１帽のシンドロームビツトを上記（
８），（９），［相］，（１１）式に従つて発生する回
路である。

例えばシンドロームビツトＳｌＯの発生は（９）式つり
第６図のように７個の入力を有する排他的０Ｒ回路５０
によつて実施できる。他の托個のシンドロームビツトも
同様にして発生される。前述したように、第５図の誤り
訂正実行回路２１はシンドロームビツト発生回路２０に
よつて発生されたシンドロームビツトを解読して誤りの
訂正を実行するので、シンドロームビツトは誤り訂正に
必要な情報を有していなければならない。式（８），（
９），（１０，（１１）によつて発生されたシンドロー
ムビツトが上記の誤り訂正に必要な情報を有しているこ
とは以下のようにして解る。まず、データビットｄ１に
生じた誤りをＥ，とすると、メモリから読み出されたデ
ータビットｄ１は下式（１２）によつて表わされること
に注意する必要がある。すなわち、Ｄ，が誤つているな
らば誤りＥ，はＥ，＝１であり、正しければ虜＝Ｏであ
る。同様にチェックビットＣ，，に生じた誤りをＥｉＪ
とすると、メモリから読み出されたチェックビットＣｉ
ｊか下式（１３）によつて表わされる。入すれば（７）
式が成立するのでＳｌＯは下式（１４）で表わされるこ
とが分る。

これは（９）式のＳｌＯ，すなわちＳｌＯ＝ｄ″１４ｄ
″２４ｄ″３１ｄ″４１ｄ″５，ｄ″ぉ４Ｃ″１０に表
わされているｄ″１，ｄ″２，ｄ″３，ｄ″４，ｄ″５
，ｄ″２６，Ｃ″１０をそれぞれ誤りＥｌ９ｅ２９ｅ３
９ｅ４９ｅ５９ｅ２６９ＥｌＯに置きかえたものに等し
い。

同様に（８），（９），ＡＣｊｊ，（１１）式のシンド
ロームビツトに表われている全てのｄ″，Ｃ″ょはそれ
ぞれ誤りＥｉ，．Ｅｊｋに置きかえられることが示され
るので、結局全てのシンドロームビツトは誤りＥｉ，．
Ｅｊｋだけで書きあられされる。以上のように全てのシ
ンドロームビツトは誤りＥｉ．．Ｅｊｋによつて表わさ
れるのて誤り訂正回路はまず必要なシンドロームビツト
から誤りＥｉを求め、ついで（１２）式を書きかえた式
Ｄ，＝ｄ″６１ｅｊに上記の求められたＥ，を代人して
誤りを訂正し元のＤ，を求めることができる。

以下において誤り訂正方法及び誤り訂正実行回路２１に
ついて説明する。

最初にデータビットｄ１に生じた誤りを訂正する方法及
び回路について説明する。

式（８），（９），００，（１１）の内でｄ″１を含ん
でいるシンドロームビツトはＳ。Ｏ，ＳｌＯ，Ｓ９，Ｓ
３４である。すなわちこれらは式（８），（９），（１
Ｃｊｉ，（１１）よりである。 一”− 一
ーー ″″− 一”一いまＳ（Ｘ）を含む線形和Ａ＝Ｓ
ＯＯｌＳｌ。ｌＳｌ，ｌＳ２。ｌジ１Ｓ３１１Ｓ３３を
作ると、この線形和は式（８），（９），Ａａ，（１１
）よりである。

前述のようにシンドロームビツトに表われるｄ″，、Ｃ
″，，はそれぞれ誤りＥｉ．．Ｅｉｊに置きかえられる
から、上記Ａ，ＳｌＯ，Ｓ２Ｏ，Ｓ３４は次式（１５）
，（１６），（１７），（１８）に書き直される。すな
わち上記（１５），（１６），（１７），（１８）式を
注目すれば、誤りｅ１はＳｌＯ，Ｓ２Ｏ，Ｓｌ３４，Ａ
のどの式にも含まれており、かつ又ＳｌＯ，Ｓ２Ｏ，Ｓ
３４，Ａはｅ１以外に共通の誤りビットを含んでいない
ことが分る。

この事実はあらゆる２個以下の誤りに対して、ｅ１はＳ
ｌＯ，Ｓ２Ｏ，Ｓ３４，の４個の内の３個をとる多数決
論理によつて正しく求まることを意味している。すなわ
ち誤りｅ１は次の（１９）式によつて求まる。さらに前
述の（１２）式、すなわちｄ″，＝ＤｊｌｅｉがＤ，＝
ｄ″，４ｅ，と書きなおされることに着目すればｄ″１
の誤りは次の（２０）式によつて訂正される。すなわち
（２０）式によつてｄ１が求まる。（２０）？龜ｉ１ル
た誤りの訂正を実行する回路は例えば第７図によつて実
施される。第７図において６０，６１，６２，６５で示
される回路は２個の入力を有する排他的オアゲートてあ
り、６３の回路は４個の入力を有する排他的オアゲート
であり、又６４て示される回路は４個の入力を有する多
数決回路てある。多数決回路６４は４個の入力のうち３
個以上の入力が同時に論理１になるときだけ出力が論理
１になる回路であつて例えばＡＮＤゲート、０Ｒゲート
によつて容易に実現できるのが既に知られている。一般
にデータビットＤ，（但し１≦ｊ≦２５）の誤りは以下
のように訂正されるのが示される。

式（８）．（９），Ｇα，（１１）から分るようにデー
タビットｄ″ｊ（１≦ｊ≦２５）を含んでいるシンドロ
ームビツトは一般にＳ。Ｏ，Ｓｌａ，Ｓ２ｂ，Ｓ３。の
形で表わされる。データビットｄ″，（１≦ｊ≦２５）
を含むシンドロームビツトＳ。

Ｏ，Ｓｌａ，Ｓ２ｂ，Ｓ．３ｃとすればｄ″ｊの誤りは
下式によつて訂正される。Ｅｊ＝多数決（Ｓｌａ，Ｓ２
ｂ，Ｓ３ｃＡ）但しＡ＝Ｓ（Ｘ）１１，Ｓ１〔ａ＋沙〕
）１−飄１Ｓ２］但し、式（２１）において（ ）記号
は〔Ｘ〕＝ＸｍＯｄＬｌｌＯ５，すなわち〔ｘ〕はＸを
５で割つた時の剰余を意味する。

式（２１）がｊ＝１の時には誤りを正しく訂正すること
は既に式（１５），（１６），・・，（２０）を用いて
説明した。

以下においてｊ＝１８の時にも式（２１）が誤りを正し
く訂正することを示そう。ｊ＝１８よりｄ″１８を含ん
でいるシンドロームビツトは式（８），（９），ＱＯ，
（１１）よりＳ。Ｏ，Ｓｌ３，Ｓ２２及びＳ３ｌである
。式（２１）によればＥｌ８は下式によつて求められる
。但しＡ＝ＳＣＸ）１Ｓ１０１Ｓ１２１Ｓ２４１Ｓ２１
１Ｓ３１１Ｓ３３上式（２２）のＳｌ３，Ｓ２２，Ｓ３
４，Ａは式（８），（９），［株］，（１１）より下式
で表わされる（但しｄ″４及びＣｄ″Ｉｊをそれぞれ誤
りＥｊ及びＥｉｊに置きかえる）。

ＶＶＶＶｌＶＶＡシＶ＆ＪＸＶＶＡＶノ式（２３）を見
れば分るように、Ｓｌ３，Ｓ２２，Ｓ３４，Ａはいづれ
もＥｌ８を含み、かつＥｌ８以外に共通の誤りを含んで
いない。

従つてＥｌ８はあらゆる２個以下の誤りに対してＳｌ３
，Ｓ２２，Ｓ３４及びＡの多数決をとることによつて得
られる。従つて前式（２１）がｊ＝１８すなわちｄ″１
８の誤りノを正しく訂正し得ることが示された。

一般にｄ″，，（１≦ｊ＝≦２５）の誤りも前式（２１
）によつて訂正されることが示されるが説明は省略する
。

前式（２１）に従つたｄ″ｊ（１≦ｊ≦２５）の誤り訂
正実行回路は既に説明した第７図のＪｄ″１に対する誤
り訂正回路と同様に構成されるので説明は省略する。以
上ではｄ″ｊ（１≦ｊ≦２５）の誤りを訂正する方法及
び回路について説明した。以下ではｄ″，（２６≦ｊ≦
３１）の誤りを訂正する方法及び回路を）示そう。最初
にｄ″２６の誤りを訂正する方法及び回路を説明する。

式（８），（９），Ｑｌ，（１１）から分るようにｄ′
２６を含むシンドロームビツトはＳＯＯ９ＳｌＯ９Ｓｌ
ｌ９Ｓｌ２である。ＳＯＯを含む線形和Ｂ＝ＳＯＯ４Ｓ
２ＯｌＳ２ｌｌＳ２２４Ｓ２３ｌＳ２４４Ｓｌ３を作れ
ば、式（８），（９），Ｑｌ，（１１）より、ＳｌＯ，
Ｓｌｌ，Ｓｌ２，Ｂは誤りＥｉ・Ｅｉｊによつて下式で
表わされる前式（２４）を見れば分るようにＳｌＯ，Ｓ
ｌｌ，Ｓｌ２，ＢはいづれもＥ２６を含み、かつＥ２６
以外に共通の誤りを含まない。

従つてＥ２６はあらゆる２個以下の誤りに対してＳｌＯ
，Ｓｌｌ，Ｓｌ２及びＢの多数決をとることによつて得
られる。すなわちｄ″９の誤りは下式によつて訂正する
ことができる。式（２５）に則してｄ″２６の誤りの訂
正を実行する回路は例えば第８図のように実施される。

第８図において回路７０，７１，７２は排他的０Ｒ回路
、回路７３は既に説明した４個の入力を有する多数決回
路である。データビットｄ″，（但し２６≦ｊ≦３１）
を含むシンドロームビツトは前式（８），（９），（１
０），（１１）から分るように一般にＳ。Ｏ，ｓａｂｌ
Ｓａ（ｂ＋１）、Ｓａ（５＋。、の形としている。一般
にデータビットｄ″ｊ（２６≦ｊ≦３１）を含むシンド
ロームビツトをＳＯＯ９Ｓａｂ）Ｓａ（ｂ＋１）〜Ｓａ
（ｂ＋２）とするれ一ぱｄ″，の誤りは下式（２６）に
よつて訂正されることが示されるが説明は省略する。−
ＪＶ７Ｊ′ 但し前式（２６）においてくａ＋１〉記号は、く１＋１
〉＝２、く２＋１〉＝３及びく３＋１〉＝１を意味する
。

又〔 〕記号は〔Ｘ〕＝ＸｍＯｄＬ］１０５を示す。

例えばｄ″３１の誤りを訂正を実４行するには、式（８
），（９），ＡＯ，（１１）よりｄ″３１を含むシンド
ロームビツトはＳＯＯ９Ｓ３２９Ｓ３３９Ｓ３４である
から式（２６）より、ｄ″３１の誤りは下式で訂正され
る。１１ゝ４ｊ１Ｗ３３１ノ 前式（２６）に則したｄ″ｊ（２６≦ｊ≦３１）の誤り
訂正実行回路は既に説明した第８図のｄ″２６に対する
誤り訂正実行回路と同様に構成されるのて説明は省略す
る。

以上においては第２図のｍ＝５の場合の本発明ノによる
符号化行列比に則した符号化回路１と、シンドロームビ
ツト発生回路２０とデータビットｄ″１，ｄ″２，ｄ″
３，・・，ｄ″３０，ｄ″３７の誤りを訂正する誤り訂
正実行回路２１とから構成されている復号化回路４０に
ついて説明した。

次にｍを３以上の任意の奇数とする一般の場合の本発明
による符号化方法及び誤り訂正方法を説明する。

ｍ＝５の時の符号化行列は第２図のＨ５で与えられた。
一般のｍの場合の符号化行列は第９図のＨｍで与えられ
る。第９図のＨｍの中にある部分行ダ旧，は第１０図で
与えられる。第９図及び第１０図より符号化行列は０ｍ
＋１）ｘ（支）十艮（ｍ−１））の行列である。第９図
及び第１０図を見れは符号化行列Ｈｍの構成法は明白と
考えられるので、これ以下の説明は要しない。いまＲ＝
ｄ＋？（ｍ−１）個のデータビットをＤｌ，ｄ２，ｄ３
，・・，ＤＲ−１，ｄＲとし、動＋１個のチェックビッ
トをＣＯＯ９ＣｌＯ９Ｃｌｌ９Ｃｌ２９個９Ｃｌ（ｍ−
２）９Ｃ１（ｍ−１）９Ｃ２０９Ｃ２１９Ｃ２２９を９
Ｃ２（ｍ−１）９Ｃ３０９Ｃ３１９Ｃ３２９９９Ｃ３（
ｍ−１）とすればチェックビットはデータビット及び前
記符号化行列Ｈｍを用いて下式のようにベクトルと行列
の乗算によつて生成される。上記チェックビットはデー
タビットと共にメモリに記憶される。

但しＲ＝ｄ＋？（ｍ−１）である。

次にメモリから読み出されたチェックビット及びデータ
ビットにダツシユ記号をつけて表わせば？＋１個のシン
ドロームビツトＳ（Ｘ），ＳｌＯ，Ｓｌｌ，Ｓｌ２？
″″？Ｓ１（ｍ−２）９Ｓ１（ｍ−１）９Ｓ頒９Ｓ２１
９Ｓ２２９０１９Ｓ２（ｍ−１）９Ｓ３０９Ｓ３１９Ｓ
３２９１９Ｓ３（ｍ−１）は下式のように行列とベクト
ルの演算によつて生成される。

但しＲ＝イ＋？（ｍ−１）である。

前式（２９）で与えられるシンドロームビツトを用いて
データビットｄ′，（但し１≦ｊ≦イ置（ｍ−１））の
誤りを以下のように訂正することができる。

前式（２９）においてｄ″，（１≦ｊ≦イ）を含むシン
ドロームビツトは一般にＳ（Ｘ），Ｓｌａ，Ｓ知Ｓ３，
の形で表わされる。このＳ。Ｏ，Ｓｌａ，Ｓ２ｂ，ジを
用いてｄ″，（１≦ｊ≦７７１′）の誤り訂正は下式（
３０）で行うことができる。Ｖｊ−ＪＶ−Ｊノ 但し上式において〔 〕記号は〔Ｘ〕 ＸｍＯｄｕｌＯｍを意味する。

次に、前式（２４）においてｄ″，≦イ＋？（ｍ−１）
を含むシンドロームビツトは一般にＳ。

Ｏ，Ｓａｂ９Ｓａ（ｂ＋１）９Ｓａ（ｂ＋２）の形で表
わされる。このＳｌ９Ｓａｂ９Ｓａ（ｂ＋１）９Ｓａ（
ｂ＋２）を用いて）ｄ″，（ｄ＋１≦ｊ≦ボ＋艮（ｍ−
１）の誤り訂正は下式（３１）によつて行うことができ
る。但し上式において〔 〕記号〔Ｘ〕＝ ＸｍＯｄＬｌｌＯｍを意味し、又くａ＋１〉記号はく１
＋１〉＝２，〈２＋１〉＝３，〈３＋１〉＝１を意味し
ている。

従つて本発明による誤り訂正方法は前式（２８）に従う
符号化方法、前式（２９）に従うシンドロームビツト発
生方法と前式（３０）及び（３１）に従う誤り訂正の実
行方法に要約される。

すなわち、式（２８）に則してｄ＋艮（ｍ−１）個のデ
ータビットから伍＋１個のチェックビットが生成され、
これらデータビットとチェックビットは共にメモリに記
憶される。次にメモリから読み出されたイ＋？（ｍ−１
）個のデータビットど如＋１個のチェックビット式に則
して？＋１個のシンドロームビツトが生成され、次いで
前記伍＋１個のシンドロームビツトを用いて、式（３０
）及び（３１）に則して、イ＋？（ｍ−１）個のデータ
ビットと師＋１個のチェックビットに生じた２個以下の
ランダム誤りが訂正される。

従つて、本発明による誤り訂正回路は前式（２８）に則
した符号化回路、前式（２９）に則したシンドロームビ
ツト発生回路及び前式（３０）及び（３１）に則した誤
り訂正実行回路を実現すれば良いことになる。

既に説明したように本発明の一例、ｍ＝５の場合の符号
回路は第３図及び第４図のように実施され、シンドロー
ムビツト発生回路は第６図のように実施され、又誤り訂
正実行回路は第７図及び第８図のように実施された。

同様に一般のｍ（但しｍは奇数）の場合の前記符号化回
路、前記シンドロームビツト発生回路及び前記誤り訂正
実行回路も構成され得るので説明は省略する。尚以上の
説明では符号化回路と復号化回路との間にメモリを構成
したが、この他に伝送回線にも適用出来ることは明らか
である。以上のように本発明はｍを３以上の任意の奇数
とした時、イ＋？（ｍ−１）のデータビットに？＋１個
のチェックビットを付加することにより任意の二個以下
の誤りを訂正する構成を有している。

【図面の簡単な説明】

第１図はデータ処理装置内におけるメモリと本発明の誤
り訂正回路との関係を示すブロック図、第２図は本発明
において３１個のデータビットから１帽のチェックビッ
トを発生するために用いられる符号行ダ旧．を示す図、
第３図及び第４図はチェックビットを発生する回路の一
例を示す図、第５図は復号化回路の一例を示すブロック
図、第６図はシンドロームビツトを発生する回路の一例
を示す図、第７図及び第８図は誤り訂正を実行する回路
の一例を示す図、第９図は本発明においてイ＋？（ｍ−
１）個のデータビットから伍＋１個のチェックビットを
発生するために用いられる符号化行列Ｈｍを示す図、第
１０図は第９図の行列Ｈｍ内の部分行列Ｈ１を示す図て
ある。 図において、１は符号化回路、２はメモリ、３”は復号
化回路、４は演算回路、５，６，５０，６０，６１，６
２，６３，６５，７０，７１及び７２は排他的０Ｒ回路
、４０は復号化回路、２０はシンドロームビツト発生回
路、２１は誤り訂正実行回路、６４及び７３は多数決回
路てある。

Claims (1)

【特許請求の範囲】
1. １ ｍを３以上の任意の奇数とする▲数式、化学式、表
   等があります▼個のデータビットに前記データビットを
   もとに３ｍ＋１個のチェックビットを付加する符号化回
   路と、前記付加されたデータビットとチェックビットを
   もとに３ｍ＋１個のシンドロームビットを発生する回路
   および前記シンドローム発生回路の出力を多数決論理に
   よつて解読する多数決回路とを有し前記付加されたデー
   タビットおよびチェックビット内に生じた任意の２個以
   下の誤りを訂正する復号化回路とを含み構成されたこと
   を特徴とする二重誤り訂正回路。