JPH01316041A - ２進符号化された情報中の誤りを検出する方法および２進符号化された情報を格納する回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はコンピュータ装置のための誤り検出および修正
の分野に関するものである。

〔従来の技術〕

デジタルコンピュータ装置は２逆打号化された情報で動
作する。その２逆打号化された情報においては、データ
が比較的高い電気的状態または比較的低い電気的状態と
しておのおの格納される一連の情報片としてコンピュー
タ装置において表わされる。典型的には、高い電気的状
態は１により表され、低い電気的状態は０により表わさ
れる。

コンピュータ装置は、電気的に高い状態を電気的に低い
状態へ変更させ、または電気的に低い状態を電気的に高
い状態へ変更させるような種々の問題がある。そのよう
な誤りを検出できることは重要であシ、かつそれらの誤
りを修正できることは有利である。どのような誤り検出
および修正技術においても少くとも２つの衝突する優先
度がある。

その１つは、装？ｆを不当に複雑にしたり、装置の動作
速度を低下させたりしないように、技術ができるだけ簡
単かつ小型でなければ々ら々いことである。第２に、そ
の技術はできるだけ多くの誤りを修正でき、かつ予測で
きる全ての誤、１検出できなければならないことである
。

誤りを検出および修正する技術が数多く知られている。

形も簡単な例の１つは、データ流中の１ビット誤りを検
出するためにパリティビットを使用することである。１
パリテイビツトを使用すると１ビット誤りが検出される
が、１ビット誤り全修正することはできず、２ビット誤
りは検出しない。

１９５０年に、リチャードＨハミング（Ｒｉ　ｃｈａｒ
ｄＨａｍｍｉｎｇ　）が、１ビツト誤９を検出および修
正する方法を開発した。その方法は−・ミンク符号法と
して知られている。−・ミンク符号法を用いて符号化さ
れた２逆打号化された情報片の例が第２図に示されてい
る。

別の符号化法がプロダクト（Ｐｒｏｄｕｃｔ）法として
知られている。この方法には数多くの変形例がある。１
つの変形例が第３Ａ図と第３Ｂ図に示されているもので
あって、 データブロック中の各行と各列に全体的なパリティチエ
ツクを利用する。この方法は全ての１ビット誤りを検出
および修正できる。本質的にはこの方法は１組のデータ
を基にしてパリティビットを計算し、それから第１の１
組のパリティビットを基にして第２の１組のパリティビ
ットを発生するものである。

〔発明の概要〕

この明細書では２逆打号化された情報中の誤りを検出お
よび修正する方法および装置について説明する。コンピ
ュータ装置の速度向上を助けるためには、必要とする論
理レベルの数をできるだけ少くする、誤りを検出および
修正する方法と装置を設計することが望ましい。第１の
ｌ＆ｌのパリティビットを基にして第２の１組のパリテ
ィビットを発生する、誤！ｌｌを検出および修正する方
法は少くとも１つの付加論理レベルを本来的に必要とす
る。

本発明の方法と装置は、データビットのみを基にしてパ
リティビットを発生するために論理関数を利用する。こ
の１組のパリティビットは誤りの検出および修正を可能
にする。

更に、本発明の好適な実施例は、各メモリチップからＮ
ビットを同時に読出すことができるメ、モリチップを有
するコンピュータ装置において動作するために設計され
る。そのようなコンピュータ装置においては、任意の１
ピツト誤りまたは２ビット誤りと、与えられたチップ内
の任意のビ２トまたは全ての、ビットが反転されるよう
、な任意の誤りを検出でき今ことが望尊しい。従来、「
予測される」誤ジは１ビット誤りまたは２ビット誤りで
あって、２ビット誤りより大きな誤りはなかったようで
あった。２ビット誤りょシ大きな誤りがないという仮定
は、各サイクルに各チップから１ビットが読出されると
いう［１だけの態様係数（ｂｙ　−ｏｎｅ、　ｆｏｒ、
ｍ　ｆａｃｔｏｒ）　Ｊ　技術において許容できる。し
かし、１Ｎだけの態様係数」技術、すなわち、チップか
らＮビットを同時に読出すことを許すことができるチッ
プを有するコンピュータ装置においては、２ビツトよシ
大きい誤りをひき起す１チツプ故障の大きな可能性が存
在する。

本発明はどのような「簡単な一１誤りでも修正できる。

簡単な誤９というのは任意の１ビツトが反転されている
ような誤りと定義できる。本発明は、与えられたチップ
力）ら読出され女任意の２ビットが反転され、マタは任
意のビットもしくは全てのビットが反転されるような誤
りとして定義される任意の「予測される」誤りも検出す
る。本発明は、（１）どのチップもデータビットとチエ
ツクビットの両方は含まず、（２）データチップ上の全
てのビットに対して、値がそれらのビットによυ値が影
響を受けるチエツクビットのセントが区別された１つの
チエツクビットと全て交差する、（３）全ての影響を受
けるチエツクビットチップに対して、チップ上の３ビツ
トの値によυ影響を受けないようガデータビットが存在
しない、ように、データ入力を基にしてチエツクビット
すなわちパリティビットを発生し、データビットとチエ
ツクビットを格納することを開示するものである。任意
の３つのチエツクビットに対して、値が３つのチエツク
ビットの全てに影響を及ぼすよう々データビットが１つ
あるか、無いように構成されたビットを本発明の好適な
実施例は有する。第２に、任意の４つのチエツクビット
に対して、値が４つのチエツクビットの全てに影響を及
ぼすようなデータビットが無い。第３に、任意のデータ
ビットに対して、値がそれの値により影響されるような
チエツクビットが正確に３個ある。

本質的には、データビットの８個に組合わされた時に結
果としての９ビツト語のパリティを偶数にするような値
をチエツクビットが表わすように、チップ上におけるチ
エツクビットとデータビットの構成を本発明の好適な実
施例は開示するものである。８個のデータビットは前記
規則に従って選択される。

本発明により利用される別々の５つの回路について説明
する。それらの回路は、メモリに格納するデータを受け
た時に適切なパリティビットを発生する回路と、メモリ
回路と、データがメモリから読出された時にそのデータ
が正しいことをチエツクするために適切なパリティビッ
トを発生する回路と、修正可能な誤差または修正できな
い誤差が検出されたことを判定する回路と、誤差を修正
する回路とである。

本発明により、ｎだけの態様係数メモリ回路からデータ
が読出された時に、任意の「簡単な」誤差が修正され、
任意の「予測される」誤差が確実に修正される。

この明細書では２逆打号化された情報中の誤差を検出お
よび修正する方法および装置を説明する。

本発明を完全に理解できるようにするために、以下の説
明においては、ゲートの種類、ビット数等のような特定
の事項の詳細について数多く述べである。しかし、その
ような特定の詳細事項なしに本発明を実施できることが
尚業者には明らかであろう。その他の場合には、本発明
を不必要に詳しく説明して本発明をあいまいしないよう
にするために、周知の回路および周知の構造は詳しくは
説明しない。

コンピュータ装置においては、情報は２逆打号化された
態様で格納され、送られる。種々の原因のために、情報
の１つまたは複数の２進ビツトを反転させることができ
る。本発明は情報片中の１ビツトの反転を検出および修
正でき、かつ情報片中の２ビツトの反転を検出できる。

更に、本発明は１組のパリティピッ）ｆ使用することに
より誤差の検出と修正を行う。コンピュータ装置回路に
おいて論理関数を用いてデータビットだけの関数として
パリティビットが発生される。このことは、とくに、第
１の１組のパリティビットをデータの関数として発生し
、第２のＩＩｖＩのパリティピラトラ第１の１組のパリ
ティビットの関数として発生する誤差修正技術および誤
差検出技術と比較して、コンピュータ装置の速度の面で
重要である。

本発明の好適な実施例は、各データビットの関数として
発生される３つのパリティビットを有することにより誤
りの検出および修正を行う。後で詳しく説明するように
、各データビットが３つの群の部材であシ、各群はそれ
のために発生されたパリティビットを有する。この技術
により、第１の１組のパリティビットをデータを基にし
て発生し、第１の１組のパリティビットを基にして第２
の１組のパリティビットを発生する従来の方法より少い
論理レベルを用いて誤りを検出および修正するという利
点が得られる。

また、本発明は、同じメモリ回路に格納されている任意
の数のビットの反転を検出できる。このことは、ビット
がメモリ回路から１度にｎビット読出される場合に重要
である。この場合には、回路の１つの故障により多数の
ビットが悪化することになる。本発明は、データビット
を組織化し、それらのデータビットに対してパリティビ
ットを発生するものである。

入力データからパリティビットを発生する回路と、メモ
リ回路と、データがメモリから発生される時にパリティ
ビラトラ発生する回路と、誤りが生じたかどうかを判定
し、その誤りを修正可能できるかどうかを判定する回路
と、修正可能な誤りを修正する回路とをこの明細書にお
いて開示する。

〔実施例〕

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

第１図は２逆打号化された語１５中の誤りを検出するた
めにパリティビット１６を使用する周知の方法を示す。

この方法は偶数パリティと奇数パリティのいずれかの使
用と、選択されたパリティの種類の選択と、２つの通信
装置の間の一致との使用を含む。たとえば、偶数パリテ
ィにおいては、パリティビットを含んでいる語中の１の
総数が偶数テあるように、パリティビットの値が選択さ
れる。それとは逆に、奇数パリティにおいては、・＜リ
テイビットを含んでいる語中の１の総数が奇数であるよ
うに、パリティビットの値が選択される。

語を別の装置へ送る前に、または語をメモリに格納する
前にパリティビットが発生される。他の装置が語を受け
た時、または語がメモリから読出された時に、語中の１
の総数が偶数パリティシステムにおいては偶数でアシ、
！たは奇数パリティシステムにおいては奇数であるよう
にするためにチエツクが行われる。たとえば偶数パリテ
ィシステムにおいては、語中の１の数が奇数パリティで
あれば、装置は誤差が生じていると仮定して、その語を
再び送ることを求める。パリティビットを単独で用いる
と１ビツトの誤りを検出できるが、誤りの修正または２
ビツトの誤りを検出することはできない。

第２図は２逆打号化された語中の１ビツトの誤りを検出
および修正可能する周知の方法を示す。

この方法は前記リチャード・ハミング（Ｒｉｃｈａｒｄ
Ｈａｍｍｉｎｇ）により開発され、１９５０年に初めて
発表された。それはハミング符号として知られている。

そのハミング符号は誤りの検出および修正可能を行える
ようにするために多数のパリティビットを利用する。−
・ミンク符号においては、Ｎビット語にに個のパリティ
ビットが付加されて、長さがＮ＋にビットである新しい
語を形成する。それらのビットは０ではなくて１から始
って番号が付けられ、ビット１を最も左側のビットにす
る。ビット番号が２であるべき全てのビットがパリティ
ビットであり、残りの全てのビットはデータのために用
いられる。

第２図に示すように、７ビツトのＡＳＣＩＩ語の場合に
はパリティピッ）１，２，４．８が付加される。ビット
３，５，６，７，９，１０．１１は７つのデータビット
である。ノ・ミンク符号を用いて表わされ、偶数パリテ
ィを用いる７ビツトＡＳＣＩＩ語（第２図）においては
、ビット１はビット１゜３．５．７，９．１１をチエツ
クするために用いられるパリティビットである。ビット
２はビット２．３，６，７，１０．１１をチエツクする
。ビット４はビット４，５，６．７をチエツクする。

ビット８はビット８，９，１０．ｌｌ’ｉチエツクする
。一般に、Ｂ□十Ｂ２・・・十Ｂｋ＝Ｎとカるように、
ビットＮはビットＢ１．Ｂ２．・・・Ｂｋによりチェッ
クされる。たとえば、１＋４＝５であるからビット５は
ビット１と４によりチェックされ、２＋４−６であるか
らビット６はビット２と４にニジチエツクされる。先に
述べたように、・・ミンク符号は１ビツト誤Ｖｔ検出お
よび修正できる。ノ・ミンク符号は２ピツトより大きい
誤りの検出は保障しない。

第３Ａ図と第３Ｂ図は、１組の２進符号化され九語を語
の１つのブロックにまとめ、各行（ｔ−たけブロック中
の語）と各列のためのパリティビットを発生する方法の
１つを適用する周知の方法を示すものである。たとえば
、第３Ａ図において、ブロック２０は２進符号化された
書式の語のブロックを表すことができる。そうすると、
ブロック２１はブロック２０中の俗語に対するパリティ
チエツクを表すことができる。ブロック２３はブロック
２０中の各列に対するパリティチエツクビットを表すこ
とができる。ブロック２２は列２１と行２３に対するパ
リティチエツクビットを表すことができる。

第３Ｂ図はこの方法を用いるプロダクト符号の例を示す
。領域２５は２進符号化された語を表し、領域２６は領
域２５中の俗語に対して偶数パリティ法を用いるパリテ
ィチエツクビットの列である。

行２７は、領域２５中の各列に対する偶数パリティ法を
再び用いたパリティチエツクビットを表す。

ブロック中の２進符号化された語の行と列に簡単なパリ
ティチエツクを利用するプロダクト符号を用いるこの方
法は全ての１ビツト誤ｆ）を修正できる。１ビット誤り
が生ずると、その誤りが生じている行と列がパリテイチ
エツクの異常により示されるこの方法は２ピツト以上の
誤りの検出を保障できない。

本発明は、２ピツト幅よシ広いランダムアクセスメモリ
（ＲＡＭ）　　（すなわち、与えられたメモリサイクル
中に２ピツト以上を格納および読出すことができるＲＡ
Ｍ　　）を利用するコンピュータ装置において誤υ修正
および検出を行う方法および装置に関するものである。

本発明は下記のような特性を有する。□ ｆｌ）　　任意の１ビット誤りの検出および修正が可能
である （２）任意の２ビット誤りを検出可能である（３）任意
の１つの装置（ＲＡＭ）が誤った結果の任意の組合わせ
を発生し、その障害を検出可能である。

本発明は、データビットをチエツクビットに組合わせる
ための１組の基準を示すものである。その基準は下記の
３つの規則で構成される。

（１）任意の３つのパリティビットに対し梁それら３つ
のパリティビットに影響を及ぼす値を持つ１つのデータ
ビットがあシ、またはデータビットがない （２）任意の４つのチエツクビットに対して、それら４
つのチエツクビットに影響を及ぼす値を有するデータビ
ットがない （３）任意のデータビットに対して、値がそれの値によ
り影響されるような正確に３つのチエツクビットがおる
。

本発明は、上記規則に従ってパリティビットをチエツク
ビットにどのようにして組合わせるかを選択し、かつビ
ットを物ｉ的装置（−ＲＡＭ）内゛に上記規則に適合す
るやυ方でマツプ□するための方法を開示するものであ
る。一般に、チエツクビットは、１組の組合わされてい
るデータビット排他的オア（ＸＯＲ）または排他的ノブ
（ｘＮＯＲ）をとることによ多発生さｈる。ＸＯＲとＸ
ＮＯＲは、同じチエツクビットチップに格納されている
チエツクビットに対して交替させられる。

ＲＡＭからビットが戻されると、誤りがあるかどうかを
判定するためにそれらのビラトラ調べなければならない
。誤りがあると、その誤りを修正できるかどうかを判定
せねばならない。誤９を修正できるかどうかを判定する
ために、ＲＡＭにより戻された情報からの各チエツクビ
ットに対してシンドロームビットが発生される。チエツ
クビットがそれの関連するデータビットのＸＯＲにより
発生されたとすると、チエツクビットとそれの関連する
データビットのＸＯＲをとることによりシンドロームビ
ットが発生される。関連するデータビットのＸＮＯＲか
らチエツクビットが発生されたトスると、チエツクビッ
トおよびそれの関連するデータビットのＸＮＯＲをとる
ことによりシンドロームビットが発生される。したがっ
て、誤りがない時はシンドロームビットはＯである。デ
ータ語およびそれのチエツクビットから発生された全て
のシンドロームビットが０であるとすると、データ中に
は誤りは存在しない。１であるシンドロームビットが正
確に１つ存在するものとすると、チエツクビットには１
ビツトの誤ｐがあったのであるから、データを変更せず
に使用できる。３つのシンドロームビットが１で、それ
ら３つのチエツクビットに組合わされているデータビッ
トのセットが１データビツトに正確に交差下るものとす
ると、修正可能なデータの誤９が存在したことになる。

そうするとデータはその交差されたデータビットを反転
することにより修正される。１に等しいシンドロームビ
ットの他の任意の組合わせは修正できない誤りである。

回路上のデータを組織化し、データビットの群化を決定
し、かつＷＡりを検出する一般的な方法として次の過程
を利用できる。たとえば、基準装置が６４ビツト装置で
あると仮定する。第１の過程はデータビットを二次元プ
レイに配置することである。そのアレイ中の行の数は下
記の式によりデータ幅から決定される。

ｘ＝Ｉｏｇ２（データ幅） ｙ　−（ｘ／２　）最も近い整数まで丸められた行の数
＝２ 列の数＝２（ｘ−ｙ） または、とくに、 ｘ＝ＩＯｇ２６４＝６ ｙ　＝　（６／２）＝３ 行の数−２８＝８ （６−ａ）　　ｓ 列の数＝２　　　−２＝８ 次に、データビットを第１４Ａ図のＭＸＮアレイ２０１
に配列できる。ここに、Ｍは行の数、Ｎは列の数である
。プレイ中の各位置は１つのデータピッ）１−表し、デ
ータビットは任意の順序で組織化できる。説明のために
、データビットの番号１をプレイの右下隅置き、そこか
ら上方へ連続して進み、１番上に達したら左どなシの１
番下へ降υる、というようにしてデータビット６４がア
レイ２０１の上左隅にくるようにする。

対角線２０２と２０３のよ？な、アレイを通る平行な対
角線を引くことによりデータビットが群にまとめられる
。各対角線はＮビットを有する。第１の対角線２０２は
（（Ｘ（１）、Ｙ（１））、（Ｘ（２）、Ｙ（２））。

、　、　、　（Ｘ、（Ｎ）　、ＹｒＮ）月として定義さ
れる。第２の対角線２０３は（（Ｘｒｌ）、、Ｙ（２）
）、（Ｘ（２）、Ｙ［３））。

、、、（ｘＣＮ）、ｙＣＮ＋ｘ）））として定義される
。対角線を群にまとめる時は、対角線がプレイを循環す
るように、ｊ＞Ｍであるような（Ｘ（＋）、Ｙ（ｊ））
に達すると、ビット（Ｘ（ｉ）、Ｙ（ｊ−Ｍ））カモ群
中の次のビットとして用いられる。一般に、対角線は（
（Ｘ（１）、Ｙ（Ｑ））、（Ｘ（２）、Ｙ（Ｑ＋１））
、、、、　　（Ｘ（Ｎ）　、Ｙ（Ｑ十Ｎ）月として定義
される。ここに、Ｑは対角線の数である。Ａ（１）、Ａ
、（２：）２．、、Ａ（Ｍ）と呼ぶことができるいま定
義したＭ個の対角線群がある。

第１の対角線ビットセットに垂直々第２の対角線ビット
セットが形成される。第２のセットの第１の対角線２０
４は（（Ｘ（Ｎ）、Ｙ（１））、（Ｘ（Ｎ−１）。

Ｙ（２））、、、、（Ｘ（１）、Ｙ（Ｎ）月として定義
される。

第２の対角線２０５は（（Ｘ（Ｎ）、Ｙ（２））、（Ｘ
（Ｎ−１１゜Ｙ（３））、、、、（Ｘ（１）、Ｙ（Ｎ＋
１）））として定義される。対角線がプレイを循環する
ように、ｊ＞Ｍであるような（Ｘ［ｉ）、Ｙ（ｊ））に
達すると、（Ｘ口）。

Ｙ（ｊ−Ｍ））が群中の次のビットとして用いられる。

一般に、対角線は（（Ｘ（ＩＮ、Ｙ（Ｑ））、、　（Ｘ
（Ｎ−１）。

Ｙ（Ｑ＋１））、、、、　（Ｘ（１）、Ｙ（Ｑ＋Ｎ）月
として定義される。ここに、Ｑは対角線の数である。第
２の対角線群セットはＢ（１）、Ｂ（２）、、、、Ｂ（
Ｍ）と呼ぶことができる。

各データビットが正確に２つの群により交差さ　−せら
れるように、いま定義したＮビットの２ＸＭセットがあ
る。

それから、パリティビットを発生するために対角線群が
評価される。各パリティビットはデータビットをカバー
する（語幅／ＲＡＭ幅）。上の例では、個々のＲＡＭが
情報の４ビツトを格納し、語幅が６４ビツトであると仮
定している。したがって、各パリティビットは６４／４
データビツトすなわち１６ビツトをカバーナ・る。各パ
リティビットは対角線群をカバーする（語幅／（ＲＡＭ
幅ｘ　Ｎ　）、すなわち、上の例では（６４／（４Ｘ８
））＝６４／３２　＝２群である。

一般に、各パリティビットが１本の対角線をカバーする
ものとすると、個々の対角線Ａ（１］、Ａ（２）、、、
、Ａ（Ｍ）とＢ（１）、Ｂ（２）、、、、Ｂ’（Ｎ）は
パリティビットの発生に用いられる。各パリティビット
が例のように２本の対角線をカバーするものとすると、
Ｃ（ｉ）＝Ａ（１）とＢ口〕の組合わせであるように対
角線が群にまとめられる。各パリティビットが４つの対
角線群をカバーするものとすると、上記のように群Ｃ（
’ｉ）がＡ（ｆ）とＢ（１）の組合わせとしてまず発生
される。ｉ−１〜Ｎに対して群Ｄ（ｉ）がＡ（Ｎ＋ｉ）
とＢ（Ｎ＋ｉ）の組合わせとして発生される。それから
パリティビットは群Ｋ（＋）に組合わされる。その群２
口〕は、ｉ＝１〜Ｎに対して群Ｃ（ｉ）とＤ（ｉ）の組
合わせとして発生される。

ＲＡＭ幅＝Ｒの装置に対しては、Ｒだけ多いパリティビ
ットを発生するためのデータビットの群化を定義せねば
ならない。これは下記の手続きを利用することによ９行
われる。第１に、データビットのアレイ中の列が、 ｃ（ｉ〕−（（Ｘ〔１〕、Ｙ（１，、Ｍ））、（Ｘ（２
）、Ｙ（１゜、Ｍ））、、、、（Ｘ（Ｎ／２）、Ｙｌ：
１．、Ｍ）））Ｇ（２）−（（Ｘ（（’Ｎ／２）＋１）
、ＹＣｌ、、Ｍ））、（Ｘ（（Ｎ／２Ｎ／２＋２））、
Ｙ（１，、Ｍ））、−、、（Ｘ〔（Ｎ／２）＋（Ｎ／２
））、Ｙ（１，、Ｍ：ｌ）） であるように２つの群Ｇ〔１〕とＧ〔２〕に分けられる
。

Ｈ［１）’−（（Ｘ（１，、Ｎ）　、Ｙ（１’）　）、
　（Ｘ（１，、Ｎ）　、Ｙ（１））。

、、、（Ｘ（１，、Ｎ）、Ｙ（２ＸＩＸＭ／Ｒ）））お
よび一般的には、ｉ＝２〜Ｒ／２に対して、Ｈ口）＝（
（Ｘ（１，、Ｎ）　、Ｙ（（（＋−１）Ｘ（２ｘＭ／Ｒ
））＋１））、　（Ｘ（１、’　、Ｎ）　、Ｙ（（（＋
−１）ｘ（２ｘＭ／Ｒ））＋２）　）。

、＝（Ｘ（１，、Ｎ）、Ｙ（（（１−１）Ｘ（２ｘＭ／
Ｒ））＋（２ｘＭｌ／Ｒ）　）　）　）　） であるように行はＲ／２群Ｈ〔１〕に分けられる。ここ
に、Ｒ＝ＲＡＭ幅である。残りのパリティビットを計算
するためのデータビットは、 Ｆ［ｊ）＝ｉ＝１〜Ｒ／２に対するＧ〔１〕とＨ口〕の
交差Ｆ（ｉ＋（Ｒ／２））＝１〜Ｒ／２に対するＧ〔２
〕とＨ（＋）の交差であるようにＧ（１）　、Ｇ（２）
　、Ｈ（ｉ）の交差により形成される。

パリティビットを発生するためにＲ群のデータビットが
発生される。

次の過程はどのビットがどの物理的装置□に格納される
かを決定することである。データビットとパリティビッ
トは別々の装置に格納される。各装置はＲビットを格納
する。第１のチエツクビットチップがＦ（１，、Ｒ）に
より発生されたチエツクビットを格納する。Ｗ＝１であ
るとすると、第２のチップはデータビットＡ（１，、Ｒ
）により発生されたチエツクビットによυ充され、第３
のチップはビットＢ（１，、Ｒ）により発生されたチエ
ツクビットで充される。ｗ＝２であるとすると、第２の
チエツクビットチップはチエツクビットＣＣ１，３，５
、、（２ｘＲ−１））により発生されたチエツクビット
により充され、第３のチップはＣ’（２，４，６，、（
２×Ｒ）〕に上シ発生されたチエツクビットで充される
。Ｗ＝４であるとすると、第２のチエツクビットチップ
はＥ（１，３，５’、、（２ＸＲ−１））により発生さ
れたチエツクビットにより充され、第３のチップ　。

はＥ（’２，４，６．．（２ＸＲ））により発生された
チエツクビットで充される。

データビットＡ（１，、Ｒ］の対角線群はチップ上のデ
ータビットの構成を格納することを決定するために用い
られる。各対角線群はＲデータビットまたはある整数倍
ＺＸＲデータビットを有する。

データビットＡｒ１．、Ｒ）からの各データビットは２
データビツトの上に格納される。与えられた任意の対角
線群からのデータビットはデータチップの上に任意の順
序で格納できる。

第４図は本発明の好適な実施例の主な４つの部品を示す
。本発明はデータをＲＡＭ６１　に格納する。

それらのＲＡＭの配列については第６図を参照して詳し
く説明する。それらのＲＡＭに格納すべきデータは線６
６へ入力され、好適な実施例においてはそのデータは３
２ビツト幅である。データの３２ビツトはパリティ発生
器６０へ入力される。

パリティ発生器の回路については第５Ａ図゛と、第５Ｂ
図および第１０図を参照して詳゛シ＜説明する。パリテ
ィ発生器６０からの出力は、後で述べる関数に従って発
生され′ｆＣ１２パリティビットである。

下記の関数式においては、ＢＰｎはパイトノ（リテイの
値を示す。ここに、ｎはパリティ発生器６０からの１２
ピツト出力を表すＯ〜１１である。この明細書で用いる
ＸＯＲは排他的オア機能を表す。

ＢＰＯ＝３１　Ｘ）Ｒ３０ＸＣＲ２９ＸＤＲ２８ＸＤＲ
２７ＸＤＲ２６ＸＣＲ２５ＸＯＲ２４ＢＰＩ−ＮＯＴ（
２３ＸＤＲ２２ＸＤＲ２１ＸＯＲ２０ＸＯＲ１９ＸＣＥ
　１８　ＸＱＲ１７ＸＯＲ１６）ＢＦ２−１５　′ｘＸ
ｔ１４　ＸＯＲ１３Ｘ）Ｒ１２ＸＤＲ１１ＸＤＲ１０Ｘ
ＯＲ９ＸＤＲ８ＢＰ３＝ＮＯＴ（７ＸＤＲ６ＸＯＲ５Ｘ
ＯＲ４ＸＯＲ３ＸＯＲ２庇１庇０）ＢＰ４＝３１　Ｘ［
Ｉ’Ｌ　２３ＸＱＲ１５ＸＯＲ７ＸＤＲ２４ＸＯＲ１７
℃Ｒ１０ＸＯＲ３ＢＰ５−ＮＯＴ（３０ＸＯＲ２２ＸＯ
Ｒ１４庇６爲２７庇１６鳶９　Ｘ（Ｒ２）ＢＦ２−２９
　ＸＤＲ２１ＸＯＲ１３ＸＤＲ５ＸＤＲ２６ＸＤＲ１９
ＸＤＲ８ＸＯＲＩＢＰ７＝ＮＯＴ（２８鷺２０庇１２℃
し口１２５℃Ｒ１８ＸＯＲ１１庇０）ＢＰ８＝２７　Ｘ
ＤＲ１９ＸＯＲ１１Ｍｌｌｔ　３罵３１　Ｘ（累加庇１
３Ｘ爪６ＢＰ９＝ＮＯＴ（２６庇１８罵１０庇２庇３０
庇２３　Ｘ）Ｒ１２庇５）ＢＰ１０＝２５ＸＯＲ１７Ｘ
ＤＲ９ＸＯＲＩ　ＸＤＲ２９瓜２２Ｘ）Ｒ１５Ｘ）Ｒ４
＋ｊ１１昂ノｆｉ庵兜Ｃｎ礒、Ｌ医ルイあ今１つパ１１
÷イビットと３２データビツトはメモリ６１へ入力され
る。メモリ６１からのデータの読出しはメモリからの４
４ビツトの読出しと、４４ビツトの第２のパリティ発生
器６２への入力とを含む。パリティ発生器２に含まれて
いる回路については第７Ｂ図と第１１図を参照して詳し
く説明する。パリティ発生器６２は下記関数に従ってパ
リティビットを発生する。この明細書ではそれらの・き
りティビットをシンドロームビットと呼び、下記の関数
式ハＳ　ＹＮ　Ｄ　ｎで各シンドロームビットを識別す
る。

霞 ゛−−− １２シンドロームビツトは誤り検出ブロック６４へ入力
される。この誤り検出ブロック６４の回路については第
８Ａ図と、第８Ｂ図および第１２図を参照して詳しく説
明する。この誤り検出ブロック６４は誤りが生じている
かどうか、およびその誤りを本発明に、ｌ：９修疋でき
るかどうかについて検出する。この実施例においては、
誤ジが存在するかどうかを判定するための関数は、 誤９存在＝　（ＳＹＮＤＯＯＲ５ＹＮＤＩ　ＯＲ５ＹＮ
Ｄ２０Ｒ８ＹＮＤ３０Ｒ５ＹＮＤ４０Ｒ５ＹＮＤ５０Ｒ
５ＹＮＤ６０Ｒ５ＴｈＴＤ７０Ｒ５ＹＮＤ８０Ｒ５ＹＮ
Ｄ９０Ｒ，５ＹＮＤＩＯＯＲ５ＹＮＤＩＩ）である。い
いかえると、シンドロームビットのいずれかが１であれ
ば誤りが存在すると仮定される。

誤υを修正できるか否かを判定するために下記の関数が
用いられる。第１に、関数ＦＯＮＥ（ａ、　ｂ。

ｃ、　、　、　、ｎ）の正確に１つが真（論理１）であ
る時だけその関数ＦＯＮＥ（ａ、ｂ、ｃ、、、、ｎ）が
真であるように関数ＦＯＮＥを定める。そうすると、修
正可能な誤りは下記の通りである。

（ＦＯＮＥ（ＳＹＮＤＯ５ＹＮＤＩ　５ＹＮＤ２５ＹＮ
Ｄ３）　ＡＮＤＦＯＮＥ（ＳＹＮＤ４５ＹＮＤ５５ＹＮ
Ｄ６　Ｓ輸７）訳ＤＦＩＮＥ（Ｓ責の８Ｓ晋Ｄ９Ｓ闇１
０．Ｓ藺１１すＯＲ （ＮＯＴ（ＳＹＮＤＯＯＲ５ＹＮＤＩ　ＯＲ５ＹＮＤ２
０Ｒ５ＹＮＤ３）ＡＮＤＮＯＴ（ＳＹＮＤ４０Ｒ５ＹＮ
Ｄ５０Ｒ５ＹＮＤ６０Ｒ５ＹＮＤ７）ＡＮＤＦ’０ＮＥ
（ＳＹＮＤ８５ＹＮＤ９５ＹＮＤＩＯ５ＹＮＤＩＩ））
ＯＲ （ＮｏＴ（ＳＹＮＤＯＯＲ５ＹＮＤＩ　ＯＲ５ＹＮＤ２
０Ｒ５ＹＮＤ３）ＡＮＤＮｏＴ（ＳＹＮＤ８０Ｒ５ＹＮ
Ｄ９０Ｒ５ＹＮＤＩＯＯＲ５ＹＮＤＩＩ）ＡＮＤＦＯ匪
（ＳＹＮＤ４５ＹＮＤ５５ＹＮＤ６５ＹＮＤ７））ＯＲ （ＮＯＴ（ＳＹＮＤ４０Ｒ５ＹＮＤ５０Ｒ５ＹＮＤ６０
Ｒ５ＹＮＤ７）ＡＮＤＮＯＴ（ＳＹＮＤ８０Ｒ５ＹＮＤ
９０Ｒ５ＹＮＤＩＯＯＲ５ＹＮＤＩＩ）ＡＮＤＦ’０Ｎ
Ｅ（ＳＹＮＤＯ５ＴｈｌＤＩ　５ＹＮＤ２５ＹＮＤ３）
）本質的には、４つの条件のうちの１つが生じた時に誤
９は修正できる。第１に、３つのシンドロームビット群
の各群における１つの、かっただ１つのシンドロームビ
ットが真であると誤り’＆修正でｅる。第２に、第１の
シンドロームビット群中の全てのシンドロームビットと
、第２のシン、ドロームビット群中の全てのシンドロー
ムビットカＯで、第３のシンドロームビット群中の１つ
のシンドロームビットが１の時に誤りを修正できる。第
３に、　第１のシンドロームビット群および第３のシン
ドロームビット群中の全てのシンドロームビットがＯで
、第２のシンドロームビット群中の１つのシンドローム
ビットが１の時に修正可能な誤りが生ずる。第４に、第
２のシンドロームビット群中と゛第３のシンドロームビ
ット群中の全てのシンドロームピツトが０で、第１のシ
ンドロームビット群中１つのシンドロームビットが１で
ある時に誤りを修正できる。

修正可能な誤りが検出されると線６９が低い状態にセッ
トされる。修正できない誤りが検出されると線γ０が低
い状態にセットされる。誤りがないと線６９と７０は高
い状態にセットされる。この回路は線６９と７０が同時
に低い状態になることは許さない。

ここで説明している実施例においては、回路６３が修正
可能な誤りのために用いられる。回路６３については第
９Ａ図と、第９Ｂ図および第１３図を参照して詳しく説
明する。回路６３はパリティ発生器６２から１２のシン
ドロームビット出力を入力として受け、かつ３２のデー
タビットを入力として受ける。１が生ずると回路６３は
修正可能な誤りを修正し、データ値を出力する。誤りが
起らないと回路はデータ値を出力する。いずれの場合に
もデータ値は線６８へ出力される。この実施例において
は回路６３は下記の関数を加えることによジそれを行う
。

出力ＤＡ’ｉ’Ａｎ＝Ｄｎ　ＸＮＯＲＩＮＰＵＴ　ＤＡ
ＴＡｎここに、Ｄｎは下記の関数に従って計算されるＤ
Ｏ＝ＳＹＮＤ３　ＡＮＤ　８ＹＮＤ７　ＡＮＤ　５ＹＮ
ＤＩＩＤ１＝ＳＹＮＤ３　ＡＮＤ　５ＹＮＤ６　ＡＮＤ
　５ＹＮＤＩＯＤ４＝ＳＹＮＤ３　ＡＮＤ　５ＹＮＤ７
　ＡＮＤ　５ＹＮＤＩＯＤ５＝ＳＹＮＤ３　ＡＮＤ　５
ＹＮＤ６　ＡＮＤ　５ＹＮＤ９Ｄ６＝ＳＹＮＤ３　ＡＮ
Ｄ　５ＹＮＤ５　ＡＮＤ　５ＹＮＤ８　　　　　　　　
□Ｄ７＝ＳＹＮＤ３　ＡＮＤ、５ＹＮＤ４　ＡＮＤ　５
ＹＮＤＩＩＤ８＝ＳＹＮＤ２　ＡＮＤ　５ＹＮＤ６　ａ
　５ＹＮＤＩＩＤ９＝ＳＹＮＤ２　ＡＮＤ　５ＹＮＤ５
　ＡＮＤ　５ＹＮＤＩＯＤ１０＝ＳＹＮＤ２　ＡＮＤ　
８ＹＮＤ４　ＡＮＤ　５ＹＮＤ９ＤＩ　１＝ＳＹＮＤ２
　ＡＮＤ　５ＹＮＤ７　ＡＮＤ　５ＹＮＤ８Ｄ１２＝Ｓ
ＹＮＤ２　ＡＮＤ　５ＹＮＤ７　ＡＮＤ　５ＹＮＤ９Ｄ
１３＝ＳＹＮＤ２　ＡＮＤ　５ＹＮＤ６　ａ　５ＹＮＤ
８ＤＩ４マ５ＹＮＤ２　ＡＮＤ　５ＹＮＤ５　ＡＮＤ　
５ＹＮＤＩＩＤ１５＝８ＹＮＤ２　ＡＮＤ　５ＹＮＤ４
ＡＮＤ　８ｍＤ１０Ｄ１６＝ＳＹＮＤＩ　ＡＮＤ　５Ｙ
ＮＤ５　ｍ：ｉ’５ＹＮＤＩＩＤ１７＝ＳＹＮＤＩ　Ａ
ＮＤ　５ＹＮＤ４　ＡＮＤ　５ＹＮＤＩＯＤ１８−８Ｙ
ＮＤＩ　ＡＮＤ　ｓｙｍ７ＡＮＤ　５ＹＮＤ９ｏ１９−
ｓＹＮｏＩＡＮＤ　５ＹＮＤ６　ＡＮＤ　５ＹＮＤ８Ｄ
２０＝ＳＹＮＤＩ　ＡＮＤ　ＳＹＩ＜Ｄ７ΔＤ　ＳＹ？
中８Ｄ２１＝ＳＹＮＤＩ　ＡＮＤ　５ＹＮＤ６　ＡＮＤ
　５ＹＮＤ１１６２２＝ｓＹＮＤＩ　ＡＮＤ　５ＹＮＤ
５　ＡＮＤ　５ＹＮＤＩＯ゛Ｄ２３＝ＳＹＮＤＩ　ＡＮ
ｏ　Ｓ晋Ｄ４ΔＤＳ翫９Ｄ２４＝ＳＹＮＤＯＡＮＤ　５
ＹＮＤ４　ＡＮＤ　５ＹＮＤＩＩＤ２５＝ＳＹＮＤＯＡ
ＮＤ　５ＹＮＤ７　、ＡＮＤ　５ＱＩＯＤ２６＝ＳＹＮ
ＤＯＡＮＤ　５ＹＮＤ６　ＡＮＤ　５ＹＮＤ９Ｄ２７７
ＳＹＮＤＯＡＮＤ　５ＹＮＤ５　、ＡＮＤ　５ＹＮＤ８
Ｄ２８＝ＳＹＮＤＯＡＮＤ　５ＹＮＤ７　ＡＮＤ、５Ｙ
ＮＤ１１Ｄ２９＝ＳＹＮＤＯＡＮＤ　Ｓ￥ＮＤ６　ＡＮ
Ｄ　５ＹＮＤＩＯＤ３０＝ＳＹＮ［）ＯＡＮＤ　５Ｔｈ
Ｔｐ５　、ＡＮＤ　ＳＹＮ［）９Ｄｎを発生するために
用いられる任意の１つのシンドロームビットが発生され
る全ての場合に、この式を適用するとＩＮＰＵＴ　ＤＡ
ＴＡｎが０ＵＴＰＵＴ　ＤＡＴＡｎに等しくされる。Ｄ
ｎを発生するために用いられる全てのシンドロームビッ
トが１であると、関数はＤＡＴＡｎ　を反転して０ＵＴ
ＰＵＴ　ＤＡＴＡｎを生ずる。

これが修正可能な誤りであると回路６４が判定したと仮
定すると、この関数は誤りであった１ビットを反転した
であろう。

ここで説明している実施例は、第６図に示すように、メ
モリ回路中で組織化されているデータに依存する。各メ
モリ回路３０〜４０は１度に４ビツトを出力できる。メ
モリ回路４３はデータビットを含み、メモリ回路４４は
パリティチエツクビットを含む。本発明において情報お
よびメモリ回路を組織化するのに用いられる１つの規則
は、１つのメモリ回路がデータビットとパリティビット
を持つことができることである。この実施例においては
、回路３０はデータビット０，８，１６゜２４を出力で
きる。回路３１はデータビット１゜９．１７．２５等を
出力できる。回路３８はチエツクビット０，１，２．３
’に出力できる。回路３９はチエツクピッ）４，５，６
．７を出力できる。

回路４゛０はチエツクビット８，９，１０．１１を出力
できる。この実施例においてメモリチップ上にデータビ
ットとチエツクビットをどのようにして配列するかにつ
いての情報が下記の表に示されている。

チップ　　　　　データビット ０　　　　　　０．８，１６．２４ １　　　　　　１．９，１７．２５ ２　　　　　　２．１０，１８．２６ ３　　　　　　３．１．１，１９．２７　　　　・４　
　　　　　４．１２，２０．２８ ５　　　　　　５．１３，２１．２９ ６　　　　　　６．４４，２２．３０ ７　　　　　　７．１５，２３．３１ チツプ　　　　　チエツクビット　　 ８　　　　　　０．１，２．３ ９　　　　　　４．５，６．７ １０　　　　　　８　；　９　、１０．１１第１０図は
第４図のパリティ発生器６′０により用いられる回路を
示す。各回路１００〜１１１は、第４図を参照して説明
したバイｉパリ嬰イｉントＢＰＯ〜ＢＰＩＩ　を計算す
るための関数に一致する。

回ｍ１ｏｏと１０１については第５Ａ図と第５Ｂ図をそ
れぞれ参照して詳しく説明する。回路１０２〜１１１は
回路１００　、１０１に類似のパターンに追従する′こ
とが当業者□には明らかであろう。ここで説明誇いる実
施例は排他的オアゲート’ｔ−利用するが、′−のゲー
トを用いて同じ機能を実現することが可能である。排他
的オアゲートを使用することは、その排他的オアゲート
への入力と結果としての出力ビットで構成されている語
のハ゛リティを偶数にするパリティピラトラ発生するた
めに設計される。

この回路の代９に他の回路を使用できる。更に、奇数パ
リティを用いる技術を本発明の要旨を逸脱することなし
に開発できることがわかる。この実施例においては、試
験のために信号ＢＡＤ／Ｉが利用され、通常は低い信号
へ結合される。

第５Ａ図は、バイトパリティビット（ＢＰＯ）　’ｉ発
生するための機能を実現するために本発明のこの実施例
により用いられる回路を示す。この回路および明細書で
示されている全ての回路においては、排他的オアゲート
は下記の真理値表に従う。

排他的オアゲート７６は入力として、線８１上のデータ
ビット２８と、線８２上のデータビット２９と、線８０
ａ上の第３のビットとを用いる。この第３のビットは回
路の試験中に誤ったパリティピラトラ発生するために用
いられる。排他的オアゲート７７は入力として、線８３
上のデータビット３１と、線８４上のデータビット２６
と、線８５上のビット２７とを用いる。排他的オアゲー
ト７８は入力として、線８６上のデータビット３０と、
線８７上のデータビット２７と、線８８上のデータビッ
ト２５を用いる。排他的オアゲート７６゜７７．７８の
出力は排他的オアゲート７９への入力として用いられる
。排他的オアゲート７９の出力は線９７へ出力され、Ｂ
ＰＯに一致する。

第５Ｂ図はＢＰＩを発生するためにこの実施例で用いら
れる回路を示す。排他的オアゲート１１は入力として線
８０ｂ上の、回路の試験のために誤りパリテイを発生す
るために用いることができるビットと、線８９上のデー
タビット２３と、ａ９０上のデータビット１８とを受け
る。排他的オアゲート７２は入力として、線９１上のデ
ータビット２１と、線９２上のデータビット２２と、線
９３上のビット１７とを受ける。排他的オアゲートＴ３
は入力として、線９４上のデルタビン）２０と、線９５
上のデータビット１９と、線９６上のデータビット１６
を用いる。排他的オアゲート７１゜７２．７３の出力は
排他的オアゲート７４への入力として用いられる。排他
的オアゲート７４の出力は反転されて線９８へ出力され
、ＢＰｌに一致する。

第１１図はメモリからデータが読出される時にシンドロ
ームビットを発生するために用いられる回路を示す。第
１１図の回路は第４図のブロック６２に一致する。第１
１図において、回路１２０〜１３１はシンドロームビッ
ト５ＹＮＤＯ−８ＹＮＤＩ　１　をそれぞれ発生するた
めに用いられる。回路１２０と１２１については第７Ａ
図と第７Ｂ図をそれぞれ参照して詳しく説明する。残シ
の回路１２２〜１３１の動作は回路１２０と１２１につ
いての説明から明らかであろう。

第７Ａ図は、第４図を参照して説明した式に従ってシン
ドロームビットＯを発生するために用いられる回路を示
す。この回路は４つの排他的オアゲートで構成される。

排他的オアゲート１４１は入力として線１３２上のＢＰ
Ｑと、線１３３上のデータビット２８と、線１３４上の
データビット２９とを受ける。排他的オアゲート１４２
は入力として、線１３５上のデータビット３１と、線１
３６上のデータビット２６と、線１３７上のデータビッ
ト２７とを受ける。排他的オアゲート１４３は入力とし
て、線１３８上のデータビット３０と、線１３９上のデ
ータビット２４と、線１４０上のデータビット２５を用
いる。排他的オアゲー）　１４１　、１４２　、１４３
の出力は排他的オアゲート１４４への入力として用いら
れる。排他的オアゲート１４４の出力は線１４５へ出力
されるシンドロームビットＯである。

第７Ｂ図は、第４図を参照して説明した式に従ってシン
ドロームビット１を発生するために用いられる回路を示
す。この回路も４つの排他的オアゲートで構成される。

排他的オアゲート１５５は入力として線１４６上のＢＰ
Ｉと、線１４７上のデータビット２３と、線１４８上の
データビット１３とを受ける。排他的オアゲート１５６
は入力として、線１４９上のデータビット２１と、線１
５０上のデータビット２２と、線１５１上のデータビッ
ト１７とを受ける。排他的オアゲート１５７は入力とし
て、線１５２上のデータビット２０と、ａ１５３上のデ
ータビット１９と、線１５４上のデータビット１６を用
いる。排他的オアゲート１５５　、１５６　、１５７の
出力は排他的オアゲート１５８への入力として用いられ
る。排他的オアゲート１５８の出力は線１５９へ出力さ
れるシンドロームビット１である。

第１２図は、誤りが生じたか、およびその誤りが修正可
能な誤りか、修正不可能な誤りかを判定するためにこの
実施例で用いられる回路を示す。

この回路は第４図を参照して先に説明したブロック６４
であって、修正可能な誤りが生じたかどうかを判定する
機能を実現するために用いられる。

この回路は２つの別々の論理装置と見ることができる。

破線で囲まれている部分１６０内の回路は、第４図を参
照して説明したＦＯＮＦ関数とノット（ＳＹＮＤｎ　Ｏ
Ｒ５ＹＮＤｎ＋１０Ｒ５ＹＮＤ＋２０Ｒ５ＹＮＤｎ＋３
）関数を発生するために用いられる。ブロック１６１は
正当々４つの修正可能な誤り状態の試験を行うために用
いられる回路である。

第８図は第１２図のブロック１６０内の回路を更に示す
。シンドロームビット０，１１２，３が線１６８　、１
６９　、１７０　、１７１をそれぞれ介して回路１６２
へ供給される。回路１６２は値ＡＯＮＥを線１７２に出
力する。ＡＯＮＦの値は、線１６８〜１７１のただ１つ
だけが真（論理１）の値を持つ時に真（論理１）であり
、他の場合には偽（論理０）である。シンドロームビッ
ト０〜３は線１６８〜１１１ヲ介してノ７ケ−）１６５
へも供給される。このノアゲートの出力は反転されて値
ＡＺＥＲＯとして線１７３へ出力される。回路１６３と
ノアゲート１６６はシンドロームビット４〜７に対して
同様に動作する。回路１６４とノアゲート１６７はシン
ドロームビット８〜１１に対して同様に動作する。

第８Ｂ図は修正可能な誤りである４つの状態を検出する
ために用いられる回路を示す。また、この回路は誤りが
生じ々いかどうかも示す。全てのシンドロームビットが
０の時にナントゲート１７４は出力０を生ずる。これは
誤りがないことを示す。

どのシンドロームビットも１であればナントゲート１７
４の出力は１であって誤りが生じたことを示す。誤りが
生じない時は、ナントゲート１７４の出力（０）がナン
トゲート１８０　、１１Ｎへの入力として用いられる。

そうするとそれらのナントゲート１８０．１８１の出力
が１にされて、誤りが生じなかったことを示す。

誤りが生じ、したがってナントゲート１７４からの出力
が１であると、ナントゲート１８０と１８１の出力がナ
ントゲート１７５〜１７８への４つの入力により影響を
受ける。各ナントゲート１７５〜１７８は、第４図を参
照して先に説明した修正可能な誤り状態に一致する。た
とえば、シンドロームビット５ＹＮＤＯ、５ＹＮＤＩ　
、　５ＹＮＤ２　、５ＹＮＤ３の１つ、かっただ１つが
１で、シンドロームビット５ＹＮＤ４　、５ＹＮＤ５　
。

５ＹＮＤ６　、５ＹＮＤ７の１つ、かっただ１つが１で
あり、更ＶＣ’／７　）”０−ムヒッ）　５ＹＮＤ８，
５ＹＮＤ９，５ＹＮＤＩＯ。

５ＹＮＤＩＩの１つ、かっただ１つが１である時にナン
トゲート１７５の出力はＯである。ナントゲート１７５
〜１７８の出力は反転されてノアゲート１７９への入力
として用いられる。したがって、ナンドゲ−ト１７５の
出力がＯであるとその出力は１へ反転され、オアゲート
１７９の出力を１にする。この値は反転されてナントゲ
ート１８１への入力として用いられる。ナントゲート１
７４の出力が１で誤りが生じたことを示すと仮定すると
、ナントゲート１８１の出力は１である。オアゲー）　
１７９の出力はナントゲート１８０への入力としても用
いられる。

オアゲート１７９の出力が１で、ナントゲート１７４の
出力が１であるとすると、ナントゲート１８０の出力は
０である。線６９上の０は修正可能な誤り状態が生じた
ことを示す。残りのナントゲート１７６〜１７８は他の
３つの修正可能な誤り状態を実現することが当業者には
明らかであろう。それらのナントゲート１７６〜１７８
のいずれかからの出力が０であるとすると、線７０へ出
力される結果としての出力はＯであって、ナントゲート
１７５の出力について説明した解析と同じ解析に従う。

”修正可能で橙い餡シ状−が生じたとすると、ナンドケ
ート１７５〜１７８の出力は全て１である。それらの出
力は反転されてオアゲート１７９への入力とじ七″用い
られるから、オアゲート１７９の出力は１である。この
場合には、誤りが生じて、ナントゲート１７４からの出
力が１であると仮定すると、−７０へ供給されるナント
ゲート１ａ’ｏｇ出カは０であって、修正可能な誤りが
生じたことを示す。

要約すれば、線６９と７０がともに高い状態（論理１を
示す）であれば誤りは生じていない。

線７０が低い状態で（論理０）であると修正可能でない
誤りが生じたことを示す。線６９が低い状態にあること
は修正可能々誤りが生じたことを示す。最後に、線６９
と７０がともに同時に低くなることは可能でない。

第１３図は、第４図を参照して先に述べたようにＤｏ−
Ｄ３１　　を計算する機能を実現するためにこの実施例
で用いられる回路を示す。破−プａンク説明子る。第９
Ａ図を参照して行う説明から、第１３図に示されている
残りの回路の動作ｄ二尚業者には明らかであろう。

数Ｄｏを計算するために用いられる回路をボデ。□関数
Ｄｏは、ナントゲート１８９への入力としそ線１８６ヲ
介して供給されるシンド・−・ピッ１３と、線１８７を
介して供給されるシンドロームビット７と、線１８８を
介して供給されるシンドロームビット１１とを用いて計
算される。その入力として用いられる各シンドロームビ
ットが１であれば線１９０−へ出力されるそのナントゲ
ート１８９の出力ＤＯはＯである。他の全ての場合には
ナンドゲ−１・１８９の出力は１である。第８Ａ図と、
第８Ｂ図と、第１２図とを参照して説明したように修正
可能な０が反転されることを示す。これは第９Ｂ図に示
されている回路により修正不可能とされ暮。

第９Ｂ図に示されている回路は排他的メアゲート１９３
を示す。この排他的オアゲートへはメモリから線１９１
を介してデータ入力が供給されるとともに、第１３図に
示されている回路の処理結果が線１９２を介己て供給さ
れる。排他的オアゲート１９３から線１９４へ供給され
る出力は、修正可能な誤りの場合、またはメモｉｊ中に
誤りが生じガい場合には修正データである。たとえば、
線１９１上あビットＯに対してメモリからの入力がＯで
あって、線１９２′Ｊｋ介して排他的オアゲート１９３
へ入力される線１９２上の入力である第９八−に示され
ているナントゲート１８９からの出力がＯであるとする
と、排他的オアゲートの出力は反転されて、ビットＯに
対する線１９４上の出力は１である。一般に、第１３図
に示されているナントゲートのいずれかからのＯである
出力は対応する人力ビットを反転させ、第１３図に示さ
れているナントゲートアいずれかからの１＋ある出力は
メモリからのデータ入力を同じ状態に維持させる。ｉの
回路は第４図に開示されているデータを修正すふための
式を効果的に実現する。

【図面の簡単な説明】

第１図は２逆打号中の誤りを検出するためにパリティピ
ッｌ−を用いる従来の方法を示し、第２図はセ進符号中
の誤りを検出するためにへミング符号を用いる従来の方
法を示し、第３Ａ図は２逆打号化された語のブロック中
の誤りを扁出および修正するためにプロダクト符号を用
いる従来の方法を示ナブロック図、第３Ｂ図は２逆打号
化された語のブロック中の誤りを検出および修正するた
めにプロダクト符号を用いる例を示し、第４図は本発明
により用いられる回路を示すブロック図、第５Ａ図はデ
ータがメモリへ入力される時に本発明により利用される
パリティビットを発生するために用いられるパリティ発
生回路を示す回路図、第５Ｂ図はデータがメモリへ入力
される時に本発明により利用されるパリティピラトラ発
生するために用いられる回路を示す回路図、第６図は本
発明により用いられるメモ′り回ＦＮ５を示すブロック
図、第７Ａ図はメ′モリから語が読出される時にパリテ
ィビットを一発生するために本発明により利用される回
路を示す回路図、第７Ｂ図はメモリから語が読出される
時にパリティピラトラ発生するために本発明によジ利用
される回路を示す回路図、第８Ａ図は誤りを修正できる
かどうかを判定するために本発明により利用される回路
を示す回路図、第８Ｂ図は誤りを修正できるかどうかを
判定するために本発明により利用される回路を示す回路
図、第９Ａ図はメモリから読出されたビットが誤ってい
るかどうかを判定するために本発明によυ利用される回
路の回路図、第９Ｂ図はメモリから読出されたビット中
の誤！ｌｌを修正するために本発明により利用される回
路の回路図、第１０図はデータがメモリへ入力される時
にパリティピラトラ発生するために本発明により用いら
れるパリティビット発生回路の回路図、第１１図はデー
タがメモリから読出される時にパリティビラトラ発生す
るために本発明により用いられるパリティビット発生回
路の回路図、第１２図はメモリから読出されたデータの
語中の誤りを修正するために本発明により利用される回
路の回路図、第１３図はメモリから読出されたデータの
語中のビットを修正するために本発明により利用される
回路の回路図、第１４Ａ図と第１４Ｂ図は本発明により
利用される、データビットを群にまとめる方法を示すビ
ットマトリックスである。 ３０〜４０・・・・メモリ回路、６０．６２・・・・パ
リティ発生器、６１・・・・メモリ、６４・・・・誤ｐ
検出器、７１〜７４・・・・排他的ノアゲート、７６〜
７９，１２０〜１３１　・・・・シンドロームビット発
生器、１４１〜１４４　、１５５〜１５８・・・・排他
的オアゲート、１６５〜１６７・・・・ノアゲート、１
７４〜１８１・・・・ナントゲート。 特許出願人　　アーデント・コンピュータ・　　　、コ
ーポレーション

Claims (4)

【特許請求の範囲】
1. （１）複数の情報符号要素を受ける過程と、前記情報符
   号要素を群化する過程と、 前記情報符号要素群を基にして第１の複数のパリテイ符
   号を発生する過程と、 前記情報符号と前記パリテイ符号を複数の回路に格納す
   る過程と、 前記回路から前記情報符号要素と前記パリテイ符号要素
   を受ける過程と、 前記情報符号要素および前記パリテイ符号要素を基にし
   て第２の複数のパリテイ符号を発生する過程と、 前記情報符号要素が前記回路により受けられてから前記
   情報符号要素の１つが状態を変化したかどうかを、前記
   第２の複数のパリテイ符号要素を基にして判定する過程
   と、 を備え、前記情報符号要素は前記パリテイ符号要素が格
   納される回路とは異なる回路に格納され、前記状態の変
   化は前記２進符号化された情報を示し、それにより前記
   ２進符号化された情報が検出されることを特徴とする２
   進符号化された情報中の誤りを検出する方法。
2. （２）情報語中の全ての１ビット誤りを検出および修正
   し、かつ１つの回路から受けた任意の数のビットの２ビ
   ット誤りの全てを検出し、かつ反転を検出する、２進符
   号化され情報中の誤りを検出および修正する方法におい
   て、 情報語を構成する複数の２進符号を受ける過程と、 前記複数の２進符号を群化する過程と、 各前記２進符号群に対してパリテイ符号を発生する過程
   と、 前記回路から前記情報符号要素と前記パリテイ符号要素
   を受ける過程と、 前記情報符号および前記パリテイ符号を基にして、前記
   ２進符号群とパリテイ符号のためのパリテイ値を表すシ
   ンドローム符号を発生する過程と、前記シンドローム符
   号を複数の群にまとめる過程と、 ａ）各前記シンドローム符号群の１つにおける前記シン
   ドローム符号の１つが、修正可能な誤りが生じたことを
   示す、第１の所定の状態にあるか、 ｂ）第１の前記シンドローム符号群の１つが第１の所定
   の状態および前記シンドローム符号の各残りが、修正可
   能な誤りが生じたことを示す、第２の所定の状態にある
   か、 を判定する過程と、 ｃ）１つまたは複数の前記シンドローム符号が前記第１
   の所定の状態にあるか、 ｄ）修正可能な誤りが生じたか、 を判定する過程と、 を備え、任意の３つの前記パリテイ符号に対して前記１
   つの２進符号が存在し、または各前記３つのパリテイ符
   号に影響を及ぼす前記２進符号が存在しないように、前
   記複数の２進符号が群にまとめられ、 任意の４つの前記パリテイ符号に対して、前記２進符号
   のいずれも各前記４つのパリテイ符号に影響を及ぼさな
   いように、前記複数の２進符号は群にまとめられ、 前記２進符号の任意の１つが３つの前記パリテイ符号の
   値に影響を及ぼすように、前記複数の２進符号は更に群
   にまとめられ、 前記複数の２進符号と前記複数のパリテイ符号は複数の
   回路に格納され、 前記複数の２進符号は前記パリテイ符号とは別の回路に
   格納され、 前記２進符号の任意の１つが３つをこえない前記パリテ
   イ符号要素に影響を及ぼさないように、前記複数の２進
   符号は前記回路上で更に群にまとめられ、 前記シンドローム符号の１つは各２進符号群ごとに発生
   され、前記シンドローム符号は前記２進符号群およびパ
   リテイ符号に対するパリテイ値を表し、 条件（ｃ）が起きて、条件（ｄ）が起きなかつたとする
   と、修正できない誤りが生じたことになり、それにより
   、２進符号化された情報中の誤りを検出することを特徴
   とする２進符号化された情報中の誤りを検出および修正
   する方法。
3. （３）情報語中の任意の１ビット誤りを検出および修正
   でき、かつ２ビット誤りを検出でき、更に単一のメモリ
   回路の故障を検出でき、２進符号化された情報を格納す
   る回路において、 前記情報語を前記回路へ入力する入力手段へ結合され、
   第１の複数のパリテイ符号を発生する第１のパリテイ発
   生手段と、 所定数の情報ビットを受け、かつそれらの情報ビットを
   供給するメモリ回路を複数個含み、前記第１のパリテイ
   発生手段と前記入力手段へ結合されて、前記２進符号化
   された情報と前記第１の複数のパリテイ符号を格納する
   メモリ手段と、前記メモリ手段へ結合され、前記メモリ
   手段から情報ビットを受けて、第２の複数のパリテイ符
   号を発生する第２のパリテイ発生手段と、 この第２のパリテイ発生手段へ結合されて、前記２進符
   号化された情報中に、または前記第１の複数のパリテイ
   符号中に誤りが生じたかを検出する誤り検出手段と、 前記第２のパリテイ発生手段と前記メモリ手段へ結合さ
   れ、修正された２進符号化された情報を前記回路から出
   力する修正手段と、 を備えることを特徴とする２進符号化された情報を格納
   する回路。
4. （４）複数の情報符号要素を受ける過程と、前記情報符
   号要素を群にまとめる過程と、 前記情報符号要素群を基にして第１のパリテイ符号セッ
   トを発生する過程と、 を備え、各前記情報符号要素は少くとも３つの前記パリ
   テイ符号要素に組合わされ、それにより、前記２進符号
   化された情報中の誤りを検出して、前記情報符号要素お
   よび前記第１のパリテイ符号要素セットを基にして修正
   されることを特徴とする２進符号化された情報中の誤り
   を検出および修正する方法。