JPS59132500A - ２ビツト誤り訂正方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明は情報処理システム等の記憶装置における誤り訂
正方式に関する。

１ビツトエラー訂正２ビツトエラー検出符号（ＳＥＣ−
ＤＥＤ符号：　Ｓｉｎｇｌｅ　Ｅｒｒｏｒ　Ｃｏｒｒｅ
ｃｔｉ　−ｏｎ　Ｄｏｕｂｌｅ　Ｅｒｒｏｒ　Ｄｅｔｅ
ｃｔｉｏｎ−シングルエラーコレクションダブルエラー
ティテクションー符号）を用いてノ・−ドエラー（固定
エラー）を含む２ビツト１でのエラー金訂正する方式と
して、従来、下記のものが知られている。

その一つは、特開昭５１−１３７３３５号公報記載の欠
陥メモリ許容制御方式に開示されており、他の一つは、
特開昭５６−６８９９７号公報記載のエラー訂正方式に
開示されている。

しかしながら前者は、後述するように、チェックピット
金発生するためのパリティ発生マトリックに特別の制約
があ凱情報ピットおよびチェックビット金すべて反転し
てもシンドロームが変らないような種類のパリティ発生
マトリックスしか用いることができないという欠点があ
る。

また後者は、５ＥＣ−ＤＥＤ符号を用いて情報ビットと
チェックビットとをメモリに書込み、読出し時に２ビツ
トエラーが発見されると１読出したこの情報ビットおよ
びチェックピット全すべて反転して再び同じメモリに書
込みこれを再び読出した後、更に情報ビットおよびチェ
ックピントをもう一度反転し、この再反転した情報ビッ
トおよびチェックピッＩｆ用いてシンドロームを発生し
、ハードエラーを含む２ビツトまでのエラー訂正金可能
にしているが、このため処理ステップがやや多くなると
いう欠点がある。

本発明の目的は、上述の従来の欠点全除去した方式を提
供するにある。

本発明の方式は、１ビツトエラー訂正２ビツトエラー検
出符号を用い友記憶装置の誤ジ訂正方式であって、アド
レス信号により指定された前記記憶装置のアドレスから
読み出され複数の情報ビットおよびチェックビットから
なるデータに対する２ビツトエラーの検出に応答してこ
の読み出されたデータのビラトラ反転して読み出したア
ドレスと同じアドレスに書込んだあとこのテークを再読
出しする反転書込再読出し手段と、この再読出しされた
データから特定のシンドローム金発生させるシンドロー
ム発生手段と、前記再読出しされたテークの情報ビット
のうちの前記シンドロームによｐ指定されるビット以外
の情報ピノ１４反転する訂正実行手段とを備えている。

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

最初に、、５ＥＣ−ＤＥＤ符号を用いてハードウェアエ
ラー？含む２ビツトまでのエラーを訂正するための原理
について説明する。

第１図（Ａ）、　（ａおよび（Ｑはパリティ発生マトリ
ックス全説明するための図である。すなわち、情報ビｙ
）’！ｚＤ。−Ｄ１５の１６ピツトとし、チェックビッ
トｋ　Ｃｏ　−０５の６ビツトとすると、チェックビッ
トＣＯ〜Ｃ５は情報ビットＤｏ＝Ｄ１ｓに基づいて第１
図（Ｂ）で示した各式によって生成される。

また、シンドロームｋ　Ｓ　ｏ〜Ｓ５　の６ビノトとす
ると、これらの各ビットＳ　Ｏ−８５は情報ピッ）Ｄｏ
＝Ｄｚｓおよびチェックビットｃｏ−０５に基づいて第
１図（ｑで示した各式によって生成される。

第１図（Ａ）はこれらの関係を見易くするためにマトリ
ックスの形で示しｔものである。例えばチェツクビット
０３′ｆｃ第１図（均に示した式で求めるには、マトリ
ックスの０３の縦列金“ｌ“が出る点まで下に辿凱その
点の横列（今の場合上から゛数えて第４番目の横列）の
データビットＤ　　−Ｄｏ　　　　　　　１５ のうちの“ｌ゛が立っているビットが上式に従って０３
を作るときに排他的論理オロをとるべき情報ビットとな
る。ｔｆＣ，例えば、シンドローム８３を求めるには、
Ｓ３で示した横列（第４番目の横列）のデータビットＤ
ｏ＝Ｄ＋ｓおよびチェックビットｃｏ−０５のうちの“
工“が立っているビットが第１図（Ｃ）に示した式に従
ってシンドローム８３　’Ｃ作るときに排他的論理和を
とるべき情報ビットおよびチェックビットとなる。

第１図（Ｎのように光示したマトリックス全以後パリテ
ィ発生マトリックスまたは単にマトリックスと称するこ
とにする。

次に、この第１図（５）に示すパリティ発生マトリック
スケ用いたエラー訂正について説明する。例えば、書込
むべき情報ビットＤ。−Ｄ１５がすべて“０“と仮定す
ると、第１図（Ａ）のマトリックスケ用いた場合には、
チェックビットＣｏ　−Ｃｓ　はすべて“１“になる。

従って、メモリに書込むべきテークは第２図の書込みデ
ータのようになる。

この書込みデータに対して、第１図（５）のマトリック
スを用いてシンドロームＳｏ〜Ｓｓ　　ｋ生成すると１
丁べてのＳｏ〜Ｓ５　のヒツトが“Ｏ゛になることが分
かる。

この事実は情報ピントＤｏ−Ｄｔｓが任意の値をとる場
合にも成立する。すなわち、ある情報ピッ）Ｄｏ〜Ｄ１
５に対し、第１図（〜のマトリックスによりチェックビ
ットＣｏ＝Ｃ５ｋ生成し、これをもとの情報ピッ）Ｄ、
−ＤＩ５に付加して書込みデータＤｏ−Ｄｔｓ　Ｃｏ−
Ｃ５（ＩＪ後Ｄｏ　−Ｃｓ　）　ｋ生成すると、この書
込みテークＤｏ−０５に対するシンドロームは、常にす
べてのビットが°゛０”になる（こうなるように第１図
（ｑのシンドロームの式は構成されている）。

さて、第１図（〜のマトリックス金兄るとさらに次のこ
とが分る。

例えば、情報ビットＤｏだけにエラーが発生すると、上
述のようにして今まですべて“０“であっタシンドロー
ムＳｏ〜５ｓｔｆ、マトリックスのＤｏの下の縦行金み
てその中にある“ｌ“に対らするシンドロームビットの
値だけが反転する。つまりこの場合はシンドロームビッ
トＳ、、Ｓｌ、Ｓ２だけが反転して“１“となり、時局
、シンドロームＳｏ、Ｓ５　ばｌ　ｌ　ｌ　０００にな
ることが分る。同様にして、情報ピッ）ＤＢにエラーが
生ずるとシンドロームは０Ｏ１ｊ０１になり１また１チ
１ツクビツトＣ３にエラーが生ずるとシンドロームは０
ｏｏｉｏｏ　になることが分る。

いずれの縦行の“ｌ“の和もすべて奇数になるように構
成されている。従夕て、１ビツトエラーに対して生ずる
シンドロームはシンドローム中の”１“の総数が必らず
奇数になる。

このため、書込みデータ中に発生するエラーのビット数
を２ビツト″！たけそれ以下の場合に限ることにすると
（これ以上のエラーを発生する確率は非常に少ない）、
シンドロームを調べることにより、エラーが全くない場
合（すべてのシンドロームビットがＯ″になる）、ｌピ
ントエラーがある場合（シンドローム中の“ｌ　”の和
が奇数になる）、２ビツトエラーがある場合（シンドロ
ーム中のｌ“の和が偶数になる）の３つの場合に容易に
識別することがＯＴ能となる。

しかも、このうちの１ビツトエラーの場合には、生じた
シンドロームと第１図のマトリックスと全比較すること
によ、りＤｏ−Ｄｘｓのうちのどのビットがエラー？起
したか全容易に見出丁ことができる。例えば、シンドロ
ームが０ＯＩＩＯＩＫなった場合には°°ｌ“の総数が
３で奇数であるため１ビツトエラーであることが分かり
、かつ、第１図（へのマトリックスのＤＯ−ＤｉｓＱ下
の各縦行を次々に調べると０Ｏ１１０１のシンドローム
を生ずるのはＤＢがエラーを起した場合にかぎられるこ
とが分る。このようにして１ビツトエラーの場合には第
１図四のマトリックスを用いて、生ずるシンドロームか
ら容易に１ビツトエラーを識別し、また訂正すべきエラ
ービット全指定することができるので１ビツトエラーの
訂正が可能である。

しかし、２ビツトのエラーがある場合には、これを検出
することはできるがどのビットにエラーがあるかを指定
できないために訂正はでさない。

こうして、第１図（〜のマトリックスを用いると、上述
のようにしてこれが５ＥＣ−ＤＥＤ符号になっているこ
とが分る。

さて５次にこれを用いてハードエラーを含む２ビツトエ
ラーがある場合の誤り訂正方式について説明する。

一例として、書込みデータが、第２図に示すようにすべ
てのｆ￥ＤＨピッｌ−Ｄ、−Ｄ、５が“０゛°で。

その友め上述のようにすべてのチェックビットＣｏ　−
Ｃｓ　　が”　ｌ“になる場合について説明する。

このような書込みデータをメモリに書込み、これをメモ
リから読出しｔときに、第２図の読出しデータに示すよ
うに、情報ピッ）ＤｏおよびＤＢにエラーが生じていた
き仮定する。この読出しデータから第１図（Ａ）のマト
リクスによりシンドロームを作ると、第２図の読出しデ
ータシンドロームで示すように１１０１０１ｍ発生する
。このシンドロームは“１“の個数が偶数であるため、
上述のように、２ビツトエラーｔｉわしでいる。従って
、これを用いてそのままエラー訂正を行なうことはでき
ない。そこで、シンドロームからこのように２ビツトエ
ラーであることを検知すると、この読出しデータのすべ
てのビットＩ）ｏ、ｃ５　ｉ反転して第２図に示す再書
込みデータを作り、これを同じメモリに再書込みし、こ
の再書込みし几テータを再読出しする。

このような、反転、再書込み、再読出しの一連の処理は
ハードエラーとソフトエラーに対して異なった影響を与
える。今１上述のり、およびＤＢの２ビツトエラーの中
で、Ｄｏが７・−ドエラー（２本のアンダーラインで示
″ｊ）でＤＢがソフトエラー（１本のアンダーラインで
示す）であったと仮定する。こうすると、再読出しした
データは第２図の再読出しデータに示すように、Ｄｏに
対しては゛０゛°全書込んだのにもか＼わらず固定値“
１“とじて再読出しデータ中に現われる。従って、再読
出しデータ全もとの書込みデータのすべてのビラトラ反
転したデータと見なすと、ノ・−ドエラーのＤｏに関す
るかぎ９丁でに訂正されたことになっている。これに対
してソフトエラーのＤＢは再読出しデータ中に“０“と
じて現われ。

依然としてＤＢのソフトエラーだけが残っていることに
なる。

さて、第１図（Ｎのマトリクスを用いて、この再読出し
データに対するシンドロームを作ると、第２図の再読出
しデータシンドロームのように、Ｏｏｔ　ｔｏｔ　　に
なるが、このシンドロームは第１図（〜のマトリックス
全参照すると、まさにＤＢに誤りがあるのを指示してい
る。従ってこの場合には、再読出しデータによりシンド
ロームを作り、このシンドロームの指定するビットだけ
全そのままにして、残りのすべての再読出しデータ（但
し情報ピントのみでよい）を反転すると第２図の訂正デ
ータに示すようにもとの正しいデータに訂正することが
できる。

以上はハードエラーが１個の場合であるが、２個とも・
・−ドエラーである場合には、再読出しデータの段階で
、これをもとの書込みデータのすべてのビノトヲ反転し
念データと児なすと、ｊでにすべてのエラーが訂正され
たデータとなっているため、これによるシンドロームは
すべて°゛０“になる。従って上述と同様の処理全行な
うとこの再読出しデータはすべて反転され、正しく訂正
されたデータが得られる。

さて１以上に示し友方法により、反転した再読出しデー
タのシンドロームを用いて、１ビツトエラーのエラービ
ットの位置を正しく指定できるのは、これに使用した第
１図ｆＡ）のパリティ発生マトリクスに特別の制約があ
るからである。

−′ｆ′なわち、第１図（７！のマトリクスの各シンド
ローム５ｏ−ｓｓ　　に対応する各横列中に含まれる“
ｌ゛°の数はすべて層数になっているため、ある書込み
データに対するシンドロームは、その書込みデータ全す
べ、て反転しても変らないという特徴音もっている。こ
のため、もとの読出しデータ中に１個のソフトエラーし
か含まれない場合には。

この読出しデータのシンドロームをとるこ七でこのソフ
トエラーのエラービット金指定できるが。

この他に１１１のハードエラー全含む場合にも、上述の
ような反転処理した再読出しデータのシンドロームをと
ることで１１固のソフトエラーしが含まないもとの読出
しデータのシンドロームと全く同じにできる。従ってこ
の再読出しデータのシンドロームを用いて直接もとのソ
フトエラーのエラーピラトラ指定で＠、上述のような手
続きによりハードエラーを含む場合の２ビツトエラーの
訂正が可能になるのである。

以上のような制約をもつ特別なパリティ発生マトリック
スを使用するのが、前述の特開昭５１−１３７３３５　
　号公報記載の方式の特徴である。

しかしながら、５ＥＣ−ＤＥＤ符号を構成でさ、しかも
上述の制約条件を満足しないようなパリティ発生マトリ
ックスを便用する必要が生ずる場合が起る。これらのパ
リティ発生マトリクスに対しては上述の方式すなわち再
読出しデータの段階でシンドロームを作りこれにより訂
正ビットを決定するという方式を適用することはでさな
い。

例えば、第３図は第１図と同様な形で１つの５ＥＣ−Ｄ
ＥＤパリティ発生マトリクス金示すが、第３図（〜のマ
トリクスは各シンドロームＳｏ”Ｓｓに対する各横列の
“ｌ゛の和が奇数であるため１８Ｅ（、−ＤＥＤパリテ
ィ発生マトリクスとしての条件金具えてはいるが、上述
の方式を用いてエラー訂正を行なうことはできない。

このようなマトリクスに対しても適用でさる方式として
特開昭５６−６８９９７号公報記載のエラー訂正方式が
ある。

これは次の如きものである。−例として前と同様に、情
報ビットＤｏ−Ｄ１５がすべて“０″のデータを用いり
−このデータから第３図（〜のマトリクスによりチェッ
クビットＣｏ＝Ｃ５ｋ生成するとチェックビットはすべ
て“ｌ“になシ、この結果、書込みデータは第４図の書
込みデータの如くなる。

前述と同様に、情報ビットＤｏにハードエラーが、−ま
た、Ｄ８にソフトエラーがあったと仮定すると、読出し
データおよびこれより求められた読出しデータシンドロ
ームは、それぞれ第４図に示すようにな−る。この読出
しデータシンドロームの“°１“の数は偶数であるため
、これより２ビツトエラーであることが識別される。

そこで、読出しデータのすべてのビノトヲ反転して再書
込みデータを作り、これにより同じメモリに再書込み全
行ない、これを再読出しする。この再読出しデータのす
べてのピッＨ−もう一度反転して再読出し反転データを
作ると、第４図に示すように、この反転データは、ハー
ドエラーが除かれてソフトエラーだけがそのまま残った
形のデータとなる。従って、この反転データからシンド
ロームを作ると、第４図の再読出し反転データシンドロ
ームで示すように０１１０１０　　となり、第３図（Ａ
）のマトリックスを参照することによ凱こ（７）　ジア
ドロームを発生するのは情報ビットＤｓＪｒビットエラ
ーであるときであることが識別され、このビットＤａ　
ｋ反転することで２とットエラーの訂正が完了する。

この方式は、前述の方式とちがってすべてのＳＥ（、−
ＤＥＤ　　パリティ発生マトリクスに対して適用できる
が、一方、上述のように１再読出しデータの段階でシン
ドロームをとることができず、これをもう一度反転し、
）・−ドエラーを除去した無反転のデータとしてからシ
ンドロームを取らなければならないという欠点を有して
いる。

これに対して、本発明の方式は、丁べての５ＥＣ−ＤＥ
Ｄパリティ発生マトリクスに対して適用可能であり、し
かも、再読出しデータの段階でシンドローム金とジ、こ
の再読出しデータの反転とシンドロームによる誤り訂正
とを並行に行なうことを可能にするものである。

次に５本発明の原理を、−例として第３図（Ｎのパリテ
ィ発生マトリクスに１２つた場合について説明する。′ 上述の場合と同様に、−例として情報ビット１）ｏ、Ｄ
ｌ、がすべて°０“のデータを用い、これから第３図（
Ａ）のマトリクスによりチェックビットＣｏ−Ｃ５ｋ生
成すると、上述の場合と同様にチェックビットはすべて
“１“にな９この結果、書−込みデータは第５図の書込
みデータの如くなる。

上述と同様に、情報ビットＤｏにハードエラーが、また
、Ｄ８にソフトエラーがあったと仮定すると、読出しデ
ータおよびこれよシ求められたシンドロームは第５図に
示す読出しデータおよび読出しデータシンドロームのよ
うになる。

このシンドロームの“ｌ“の個数が偶数であるため、こ
れより２ビツトエラーであることが識別される。

そこで、読出したデータのすべてのビットを反転して再
書込みデータ全作シ、これによｐ同じメモリに再書込み
全行ないこれを再読出しする。Ｏこまでの処理は上述の
場合と全く同様である。

さて、この再読出しデータは、第５図に示すように、エ
ラーを含まないもとの書込みデータ金反転したデータと
比較すると、ソフトエラーのあったＤ８のビットだけが
異なっている。

一方、この再読出しデータから第３図（Ａｌのマトリク
スを用いてシンドローム８ｏ＝Ｓｓｋ作ると、第５図の
再読出しデータシンドロームで示すように１００１０１
　　となる。このシンドロームを用いて第３図（〜のマ
トリクスから、前述と同様な方法により、このシンドロ
ームの指定スるエラービット金求めると、Ｄ９となシ、
上述のＤ８に指示しないつ これは次の理由による。

第３図（〜のマトリクスの各シンドロームに対する横列
の“ｌ“の和はすべて奇数の９個になっている。このた
め、Ｄ、、Ｃ５の丁べてのデータを反転するとシンドロ
ームも反転してしまうのである。

実際に、上述の再読出しデータシンドローム１ｏｏｔｏ
ｉ　　’ｉ反転し之第５図に示す修正シンドローム０１
１０１０　　’１１”作ると、これは正にＤ８のビノト
ヲ指定する所望のシンドロームとなっていることが分る
。

以上のことから次の点が明らかである。

すなわち、第３図に示すような各シンドローム５ｏＬｓ
５　に対する横列のｌ“の個数がすべて奇数であるよう
なパリティ発生マトリックスを用いて、再読出しデータ
（反転データ）に対するエラーピット金指定するシンド
ロームを作るには、再読出しデータに対する通常のシン
ドローム全作り、これを反転すればよい。

こうして、第５図に示すように、再読出しデータシンド
ローム１ｏｏｉｏｔ　　から、これを反転した修正シン
ドローム０１１０’ｌＯ’に作り、この（白正シンドロ
ームが指定するデータビット（現在の場合清報ピッ）Ｄ
ｓ）１Ｍ外の各ビット全すべて反・転することにより正
しくソフトエラーを訂正できる。

以上のように、本方式金用いると再読出しデータ（反転
データ）から直接シンドローム（修正シンドローム）を
作り、これ全周いて、このシンドロームの指定するビッ
トだけ全そのままとし、他の再読出しデータの情報ビッ
ト’ｒすべで反転することにより正しくエラー訂正され
た情報ビットを得ることができる。

本方式を更に一般化した場合の例として、次に、第６図
に示すパリティ発生マド“リクス全用いる場合について
説明するっ 上述の場合と同様に、−例として清報ビットＤ　ｏ　＝
　Ｄ　ｔｓ　をすべて“０”とすると、第６図（八に示
すパリティ発生マトリクスから求め定チェックピッ）Ｃ
ｏ、Ｃ５はすべて“ｌ“になり、書込みテユタは第７図
の書込みデータのようになる。前と同様に、Ｄｏ　にノ
・−ドエラー、ＤＢにソフトエラーがあったと仮定する
と、読出しデータは同図のようになり、これより求めた
読出しデータシンドロームは１１０１０１　　となるつ
　この“１　”の１同数か偶数であることから、２ビツ
トエラーであることが識別される。そこで、前述と同様
に、読出しテ・−夕金反転して再書込みデータとし、同
じメモリに書き込む。これを再読出しして再読出しデー
タを作ると、第７図のように、もとの正しい書込みデー
タを反転したものと較べてソフトエラービットの位置Ｄ
８だけが異なるデータとなる。

この再読出しデータから第６図（へのマトリックスを用
いて再読出しデータシンドロームを作ると１０００１１
　　になる。これは第６図（〜のマトリクスによるとＤ
４のビット金指示するシンドロームとなυエラービット
Ｉ）８’ｉ正しく指示しない。

このマトリクスの場合の修正シンドロームは次のように
して求められる。

すなわち、第６図ＦＡ）に示すマトリクスのシンドロー
ムＳ、、Ｓ５　の各横列の“Ｉ“の個数はそれぞれ、Ｓ
ｏに対応する列は９（奇数）、Ｓｌに対応する列は１０
（偶数）、Ｓ２に対応する列は９（奇数）、Ｓ３に対応
する列は９（奇数）、Ｓ４に対しする列は９（奇数）、
Ｓ５に対応する列け８（偶数〕となっている。前述のよ
うに、この横列の“ｌ“の和が偶数になるシンドローム
については、すべてのデータを反転してもシンドローム
ビットは不変であり、一方奇数になるシンドロームビッ
トはデータの反転とともに反転する。従って、第６図（
Ａ）に示すマトリクスの場合には、データが反転すると
、Ｓｏ＋　　ＳＬ　８３．８４のビットが反転するので
、反転データから作ったシンドローム５ｏ−８ｓ　（１
０００１１）の中のＳｏ、Ｓ２，５３ＩＳ４のビットだ
けを反転して修正シンドローム００１１０１　　ｋ作る
と、第６図（へのマトリクスから明らかなようにこの修
正シンドロームは正しくエラービットＤ８を指定する。

従って、上述と同様に、この修正シンドロームの指示す
るピント（現在の場合Ｄａ　）だけをそのままとし、他
の再読出しデータを反転すれば正しいもとの書込みデー
タが得られる。勿論これは情報ビットＤ（＋−Ｄｚｓだ
けに適用し修正シンドロームの指示する情報ビットだけ
をそのままとし、他の再読出しデータの情報ビラトラ反
転すればよい。

以上に述べた方式は、５ＥＣ−ＤＥＤパリティ発生マト
リクスの溝成に関係なく一般的に適用できることは明ら
かである。こうして、５ＥＣ−ＤＥＤパリティ発生マト
リクスに何等制約を加えることなく、シかも再読出しデ
ータ（反転データ）の段階でシンドロームを求めエラー
訂正を行なえる誤り訂正方式が得られることになる。

なお、第７図においては書込みデータの情報ピッ）　Ｄ
　６−　Ｄ　１５としてすべてが“０“の場合について
説明したが、これがすべて“ｌ“の場合金第８図に、ま
た“１０１０・・・ｌＯ“で２１固ハードエラー金含む
場合金第９図に、ざらに°“０１０１・・　０１”の場
合金弟１０図に示す。これらに用いたパリティ発生マト
リクスは第６図（Ａ）に示したものであり、従って上述
と同様に再読出しデータシンドローム５ｏ−８５の中の
Ｓ、、Ｓ２．Ｓ、およびＳ４のビットだけを反転して修
正シンドロームを作っている。まｔ１ハードエラー（２
本のアンター−ラインで示す）およびソフトエラー（１
本のアンタ−ラインで示−ｊ）のビット位置はそれぞれ
の図について変えであるが、これらの図から以上に述べ
た本方式の原理により所望のエラー訂正を行えるのが明
らかに理解できるであろう。

なお、本方式で通常シンドロームから修正シンドローム
全作るには、上述のように、パリティ発生マトリクスの
各シンドロームビットに対する横列の“１　”の和が奇
数になるビットについてだけ通常シンドロームのビット
全反転すればよい。

以上で本方式の原理は明らかとなったので、次に、本発
明の一実施例を図面を参照して詳述する。

第１１図は本発明の一実施例を示すブロック図である。

本実施例は、書込みレジスタｌ　、５ＥＣ−ＤＥＤ符号
発生回路２、選択回路３、メモリ回路４、読出しレジス
タ５、シンドローム発生回路６１テコード回路７、訂正
実行回路８および制御回路９を含んでいる。

さて、本実施例の動作は下記の通やである。

書込みデータは第７図〜第１０図で説明したようにＤＯ
”−Ｄ１５の情報ビットからなるものとしてこれらの情
報ビットＤＯ”’−Ｄ１５はライン１０００金介してレ
ジスタｌに格納される。

５ＥＣ−ＤＥＤ符号発生回路２は、第６図に示しｆＣ８
Ｅｃ−ＤＥＤパリティ発生マトサクスに従って、レジス
タｌに格納された情報ビットＤｏ−Ｄ、５からチェック
ビットＣｏ−Ｃｓｆｆ１生成しくっまシ第６図（Ｂ）で
示す式に基づいてチェックビットＣ８〜Ｃｓ　ｋ生成し
）、これを情報ビットＤ。−Ｉ）ｔｓに付加して書込み
データＤｏ、Ｃ５とし、ライン２０００から選択回路３
に出力する。

選択回路３は、制御回路９からライン９００３を介して
供給される制御信号により、通常の書込みの場合にはラ
イン２０００側の入力全選択し、上述の書込みデータＤ
ｏ＝Ｃｓ　　ｋライン３０００を介してメモリ回路４に
書込データ入力として供給する。

一方、メモリ回路４には、書込むべきメモリアドレス金
指定する信号がライン９０００　を介して制御回路９に
供給され、さらに回路９からライン９００４　ｋ介して
メモリアドレス指定信号として供給される。また制御回
路９はライン９０ｏ５を介してメモリ回路４を書込状態
に制御する。

この結果、情報ピッ）　Ｄ　ｏ　−Ｄ　１５にチェック
ビットＣｏ、Ｃ５が付加された書込みデータＤｏ〜Ｃ５
はメモリ回路４の中の指定されたメモリアドレスに書込
まれる。

次に、メモリ回路４から書込んだデータを読出す場合に
は以下のようになる。

読出すべきメモリアドレスを指定する信号をライン９０
００　ｋ介し、まｔ読出しを指定する信号をライン９０
０１ｅ介して制御回路９に供給し、さらにライン９００
２　’ｅ介して制御回路９に起動パルス全供給する。

この結果、制御回路９は以下に示す読出しシーケンスを
開始する。

まず、指定されたメモリアドレスをライン９００４金介
して回路４に供給するとともに、ライン９００５を介し
て回路４を読出し状態にセットする。この結果、指定さ
れたメモリアドレスの内容が前述の第７図〜第１０図で
示した読出しデータとしてライン４０００　ｋ介して読
出され、制御回路９からライン９００６　　’に介して
供給される制御信号により読出しレジスタ５に格納され
る。

レジスタ５の内容は読出しデータとしてライン５０００
　　’に介してシンドローム発生回路６に供給される。

回路６は、供給された読出しデータにょシ第６図に示し
；１８Ｅｃ−ＤＥＤパリティ発生マトリクスに基づいて
シンドローム５ｏ−８ｓｋ発生する。

すなわち、供給されたレジスタ５の出力である読出しデ
ータＤｏ−Ｃｓｋ用いて第６図（ｑに示した各式により
シンドロームの各ビットＳ。−８ｓ　ｋ発生する。

もし、シンドロームｓ　ｏ　”　ｓ　ｓ　　の中に“１
゛°が含まれておりその個数が偶数の場合には、前述の
ように供給されたデータに２ビツトエラーがあることを
表わし、この情報はライン６０００　　’ｉ介して制御
回路９に通報される。

最初に、上述のシンドロームＳｏ〜Ｓ５　の中ニ１１１
“が全く含まれていないか、または含まれる“ｌ”の個
数が奇数である場合について説明する。

この場合には読出しデータにはエラーが全くないか、ま
たは、１個のエラーしかない場合なので通常の５ＥＣ−
ＤＥＤ符号方式を適用して容易にエラー訂正を行なうこ
とができる。すなわち、上述のようにして発生したシン
ドロームＳｏ、Ｓ５　はライン６ＱＯ１’に介してデコ
ード回路７に供給され、ここでシンドロームＳ　ｏ　−
８５はデコードされて、エラーした場合に該シンドロー
ムを発生するようなビット位置に“１″を有する訂正信
号とな９１ライン７０００　’ｅ介して出力される。す
なわち、ライン６００１　から供給されｔシンドローム
ＳＯ〜Ｓ５　が例えば１００１１Ｏの場合には、第６図
（Ａ）のマトリクスより、このようなシンドロームを発
生するのは情報ビットＤ９にエラーがある場合であり、
この場合の訂正信号出力はＤ９の位置だけが“１″で他
の情報ピッ）ＤＯ−Ｄ８　およびＤＩＯ〜ＤＩ５にはす
べて“０“を有する出力が訂正信号となυライ７７００
０　ｋ介して訂正実行回路８に供給される。一方、訂正
実行回路８には、読出しレジスタ５から読出しデータの
各情報ビットＤｏ〜Ｄｉｓがライン５０００　　ｋ介し
て供給されており、この各情報ビットとこれに対応する
前記訂正信号の各ビットとは５回路８において排他的論
理和によって合成される。この結果、情報ビットの中の
シンドロームＳｏ、Ｓ５　によって指定されたビット位
置にあるビットだけが反転され、訂正が行なわれてライ
ン５ｏｏｏ　ｉ介し読出されたデータとして出力される
。

シンドロームＳｏ、、Ｓ５　がすべて０″′の場合には
、デコード回路７の出力の各ビットもすべて“０“にな
９、読出しレジスタ５の出力の中の情報イツトがそのま
ま回路８およびライン８０００を介し読出されたデータ
として出力される。

以上に用いるデコード回路７は、′：ｉｉ＃＃シンドロ
ーム８０−８５　　の６ビツトの必要な各組合せにモリ
アドレスをもち、各メモリアドレスごとに１６ビツトの
容量を有するＲＯＭの、５ｏ＝Ｓｓの６ビツトで定まる
各メモリアドレスごとに、この出力すべ＠１６ビツトの
信号を書き込むことにより容易にＲＯＭによるデコード
回路として実現できる。

さて、以上は、最初に読出された読出しデータＤｏ、Ｃ
５によるシンドロームＳ、、Ｓ５の中に含まれる°°ｌ
“の個数が０か奇数である定め、読出しデータＤ、−Ｃ
５の中には１ビツト以下のエラーしか含まれないと判定
された場合の動作であるが、上述の“１“の個数が偶数
（０を含まない）である場合には２ビツトのエラーを含
むと判定され、この情報は前述のようにライン６００（
１’を介して制御回路９に通報され、これが２ビツトエ
ラーに対する制御回路９の処理を起動する。

以下、この場合の処理について詳述する。

読出しレジスタ５の現在の内容、すなわち、第７図〜第
１Ｏ図で読出しデータとして表示されたデータＤ、、Ｃ
５に対し、そのすべてのビットが反転された反転出力が
、レジスタ５からライン５００１　　’に介して取り出
され、選択回路３の一方の入力として供給されているが
、制御回路９は、２ビツトエラーに対する処理が起動さ
れると、ライン９００３　’に介して制御信号を選択回
路３に供給し、ライン５００１　側のこの反転出力を入
力として選択するように切替え、また、ライン９００５
を介しメモリ回路４に対して書込みを指定する。

なお、ライン９００４のメモリ回路４に対するアドレス
指定信号は前と同、じアドレスを指定する。

この結果、読出しデータＤｏ、Ｃ５のすべてのビットを
反転したデータが、再書込みデータとしてメモリ回路４
の同じメモリアドレスに再書込みされる。

一制御回路９は、この再書込みがすむと、直ちにライン
９００５　を介してメモリ回路４を読出し状態に制御し
、再書込みしたデータを直ちに再読出しして読出しレジ
スタ５に格納する。これが第７図〜第１Ｏ図で示した再
読出しデータとなる。

この再読出しデータは、第７図〜第１Ｏ図で説明しｔよ
うに、読出しデータ中に含まれていたエラーの中のハー
ドエラーだけを訂正した反転データとなっている。従っ
て、もとの読出しデータの中にハードエラーが含まれて
いる場合には、必らずｌピッ１１下のエラーしか含まれ
ないデータ全反転したものとなっている。このため、現
在読出しレジスタ５の中に含まれている再読出しデータ
は、これを用いて前述の修正シンドロームを生成し、こ
れにより一指定されるビット位置のビットだけをそのま
まとし、残りの他のビットを丁べて反転丁ればエラー訂
正された出力を得ることが可能なデータである。

さて、修正シンドロームを作るには、前述のように通常
のシンドロームの特定のピント位置だけを反転すればよ
いので、容易に実現可能である。

第１２図は本実施例のシンドローム発生回路６に含まれ
るシンドローム修正回路部の詳細を示した回路図である
。

回路６は、通常シンドローム発生回路６０とシンドロー
ム修正回路６１とを含む。

通常シンドローム発生回路６０は、現在の例では第６図
（Ｃ）に示す式により入カデータＤ、−，Ｃ５からシン
ドローム５ｏ＝８ｓ　　ｆｃ発生丁為公卸のシンドロー
ム発生回路であり、こうして発生された通常のシンドロ
ームＳ、、−８５の各ビットはそれぞれラインＳ−０，
Ｓ−１，８−２・・・Ｓ−５？介して出力される。

８ＥＣ−ＤＥＤパリティ発生マトリクスとして第６図（
Ａ）ｔ−用いる場合に修正シンドロームを作るには、前
述したように、Ｓ、、Ｓ２，８３およびＳ４の各ピッＩ
ｆ反転Ｔればよい。これは第１２図に示すようにシンド
ロームの反転すべきビットに対応する各２インに排他的
論理和回路を挿入し、これら排他的論理１０回路の一方
の入力として、回路６０の対応する出力を接続し、他方
の入力として制御回路９からの再読出し制御線９００７
　を接続する。制御線９００７は回路９によシ通常の読
出し時には論理値“０“をとり、再読出し時には論理値
“１″をとるように制御される。

この結果、前述の通常の読出し時には回路６は回路６０
で発生した通常のシンドロームをそのまま出力し、前述
したような通常データに対するエラービット位置を指定
するシンドロームとしてデコード回路７に供給される。

また、現在のように、再読出し時には、回路６は回路６
０で発生した通常のシンドロームを、その中のＳ、Ｓ２
，８．およびＳ４　の各ピッ１反転することにより修正
シンドロームに変換し、デコード回路７に供給する。こ
の結束、現在、読出しレジスタ５に格納されている反転
データ（再読出しチータラから、エラーピント位置を正
しく指定するシンドロームが得られ、それが回路７に供
給されることになる。従って、回路７の出力には、前述
と同様に、エラービット位置のビットだけが“１“で他
は“°０′であるような出力が発生する。

次に、本実施例における訂正実行回路８の回路例を第１
３図に示す。

各ｔｕｈビットＤＯ−ＤＩ５対心に、３人力の排他的論
理和回路が設けられていて、該回路のそれぞれ３個の入
力には、デコード回路７の対応するビット出力（ライン
７０００　　）と読出しレジスタ５の対応するビット出
力（ライン５０００　　）と、前記再読出し制御線９０
０７とがそれぞれ供給されている。

この結果５通常の読出し時には、誤υ訂正回路８は、読
出しレジスタ５の情報ビットＤＯ−Ｉ）１ａの中の、デ
コード回路７で“１″′を出力したビット位置のビット
だけが反転されて前述の訂正が行なわれる。

ま九、現在の再読出し時には、読出しレジスタ５に格納
されｔ情報ピッ）ＤｏｘＤｌｓの中の、デコード回路７
で“１″を出力し次ビット位置のビットだけが反転され
ず、他のすべての情報ビットが反転されるので、回路８
の出力８０００　には、前述し友ように、正しくエラー
訂正された出力が現れることになる。

以上述べ友ように５本実施例に従うと、パリティ発生マ
トリクスに制約なく、再読出しデータを用いてシンドロ
ームを発生させ、ハードエラーを含む２ビツトまでのエ
ラーを訂正できる。しかも再読出しデータの反転はシン
ドロームによる誤り訂正と並行して行なうことができる
。ま次回書込みデータは読出しレジスタ５の７リツプ７
０ツブ回路の反転出力をそのまま使用して行なえるので
特別の反転回路は不要である。

次に、上述の実施例と一部が異なる別の実施例を第１４
図にブロック図として示す。

上述の実施例と異なる点は、新たに選択回路１０を設け
たこと、および、それにともなって訂正実行回路ざとし
て３人力ではなくて２人力の排他的論理和回路ヲ用いこ
れを簡単化し定ことの２点である。

選択回路ｌＯは再１読出し制御８９００７の制御により
、正常読出し時にはライン５０００　’に介して供給さ
れる読出しレジスタ５の正常出力を選択して誤り訂正回
路ぎに供給し、また再読出し時にはライン５００１　　
’を介して供給される読出しレジスタ５の反転出力を選
択して誤り訂正回路ぎに供給する。従って、正常読出し
時には、レジスタ５の中の情報ピッ）　Ｄ　ｏ−Ｄ　１
ｓのうちデコード回路７で１″を出力しｔビット位置に
相当するビットだけが反転して訂正され、また再読出し
時には、レジスタ５の中の情報ピットＤｏ−Ｄ１５のう
ちのデコード回路７で“ｌ“を出力したビット位置に相
当するビットだけが反転せず（２回反転されてもとに戻
り）、他のすべての情報ピットは反転されるので同様に
正しく訂正が行なわれる。

なお、以上のいずれの実施例においても８ＥＣ−ＤＥＤ
パＪｊティ発生マトリクスとして第６図（Ａ）を用いる
場合について説明し友が、これは−例を　　。

示しｔもので本発明は何もこれに限定されるものではな
い。

また、第１２図のシンドローム発生回路６および第１３
図の訂正実行回路８もその一回路例を示したもので本発
明は何もこれに限定されるものではない。

以上述べたように５本発明を用いると、５ＥＣ−ＤＥＤ
符号を用いて２ビツトまでの誤り訂正（２ビツトのハー
ドエラーま几は、１ビツトのハードエラー＋１ビツトの
ソフトエ２−または、１ビツトのン７ト、エラーの訂正
）が可能となる。本発明に用いる５ＥＣ−ＤＥＤパリテ
ィ発生マトリクスには制約がなく、シかも反転したまま
の再読出しデータを用いて直接シンドロームを発生し、
この再読出しデータの再１反転はシンドロームによる誤
り訂正そ並行して行なうことを可能にする。

これにより柔軟性に富んだ高効率の誤り訂正方式を提供
できる。

【図面の簡単な説明】

第１図ＦＡ）、　（ＩＩＪ、　（Ｑはパリティ発生マ）
　ＩＪクスを説明するための図、第２図はハードエ２−
？含む２ビツトエラーがある場合の誤り訂正方式を説明
するための図、第３図ｆＡ）、　（Ｂ１．　（Ｑは第２
のパリティ発生マトリクスを説明する几めの図、第４図
は第３図のパリティ発生マトリクスを用いる従来例の誤
り訂正方式を説明する友めの図、第５図、第７図、第８
図、第９図、第１Ｏ図は本発明の誤り訂正方式の原理を
説明するための図、第６図（Ａ）。 （Ｅ９．　ｆＱは第３のパリティ発生マトリクスを説明
するための図、第１１図は本発明の一実施例を示すブロ
ック図、第１２図は前記実施例で用いるシンドローム発
生回路に含まれるシンドローム発生回路部の回路例を示
す図、第１３図は前記実施例に用いる訂正実行回路の回
路庸すを示す図、および第１４図は本発明の別の実施例
を示すブロック図である。 図において、ｌ・・・・・・番込みレジスタ、２・・・
・・・５ＥＣ−ＤＥＤ符号発生回路、３・・・・・・選
択回路、４・・・・・・メモリ回路、５・・・・・・読
出しレジスタ、６・・・・・・シンドローム発生回路、
７・・・・・・デコード回路、８゜ざ・・・・・・訂正
実行回路、９・・・・・・制御部、ｌＯ・・・・・・選
択回路、６０・・・・・・通常シンドローム発生回路、
６１・・・・・・シンドローム修正回路。 代理人　弁理士　　内　原　　　晋　ゝ・゛・□パ、′
Ｎ−−／ −ｌｌｆ飯ヒ゛ノと　　□−４１７りと＝、Ｆ−ｅＪ　
＝　　９．：＋　■Ｄｓ　（ｆ）　Ｄｓ　■Ｄａ　（Ｅ
）　Ｄｒｏ　ｅＤｕ　（ＥＩＤｔｙ　ｅＤｕ　ｅ）Ｄｕ
シ＝島■島■ｐよ■Ｄ、！ｌＩ■Ｉｎｔｏ■Ｄｔｒ■、
ｌ）／Ｊ■ρ１４■ρに■ｅ６躬　１　図 ６９５− □ノ乃１すν乙°゛ゾ）　　　　　　　　　　　　　　
　　　６．、クリ・、、／−−第３図 □ノド１１板と２ンＦ　　　　　　　　　　　　　　　
　づ６ｔ・ツク６ニ゛、）−ｓ−−、Ｓ＝ρ、■ｐ４■
Ｄ６■ｈ■ゐ■ｐｔｔ■尚■ｒ５′＄１区

Claims (1)

1. 【特許請求の範囲】 １ビツトエラー訂正２ピツトエラー検出符号を用いた記
   憶装置の誤り訂正方式において、アドレス信号により指
   定された前記記憶装置のアドレスから読み出され複数の
   情報ビットおよびチェックビットとからなるデータに対
   する２ビツトエラーの検出に応答してこの読み出された
   データのピントを反転して読み出したアドレスと同じア
   ドレスに書込んだあとこのデータを再読出しする反転書
   込再読出し手段と、 この再読出しされたデータから特定のシンドロームを発
   生させるシンドローム発生手段と。 前記再読出しされたデータの情報ビットのうちの前記シ
   ンドロームにより指定されるビット以外の情報ビラトラ
   反転する訂正実行手段とを備えたことを特徴とする２ビ
   ット誤り訂正方式。