JPS5953640B2 - 記憶装置 - Google Patents

Description

【発明の詳細な説明】 本発明は、情報処理装置に関し、特に電子計算機等の主
記憶装置の高速記憶装置に関する。

従来、電子計算機等の情報処理装置の主記憶装置等の高
速でかつ大容量の記憶装置においては、それに記憶され
た情報内容の信頼性を向上させるために、ハミング符号
等の誤り訂正符号を付加して用いていた。例えば、ハミ
ング符号数ｍは、情報符号数にとすれば、に≦２ｍ−ｍ
−１必要であり、情報符号数の少ないこの種の記憶装置
においては、誤り訂正符号数の割合が多くなり、経済性
を害することになる欠点があつた。本発明の目的は、誤
り訂正符号を複数個のアドレスの情報ビットに１つ各ア
ドレスに分散させて付加することにより、情報符号数に
対する誤り訂正符号数の割合を減少させると共に、各ア
ドレスの情報ビットに付加された誤り訂正符号の一部を
用いて、読み出された記憶情報に誤りがあるかどうかを
判定し、誤りがなければそのまま読出し、誤りがあれば
これらの複数個のアドレスの全てを読出し訂正を行なう
ことができる記憶装置を提供することにある。

本発明は、データと第１の検査ビットと第２の検査ビッ
トとを一組の情報とし、一群をなす複数組の前記情報の
うちの複数のデータによつて各組の第１の検査ビットが
作成され、各組に属するデータと第１の検査ビットのす
べてによりそれぞれの組の第２の検査ビットが作成され
る１以上の群を１組単位で記憶する記憶手段と、この記
憶手段のアドレスを指定するアドレス指定手段と、この
アドレス指定手段から出力されるアドレス指定信号によ
り前記一組の情報を読み出した後、前記一組の情報の全
てのビットに対し前記第２の検査ビットを用いてパリテ
イ検査を行ない１ビット誤りがあるか否かを検出する１
ビット誤り検出回路と、この検出により誤りがある場合
、この組が属する群の複数組の情報を前記記憶手段から
読み出してこの群の前記第１および第２の検査ビットを
用いて１ビット誤りを訂正する誤り訂正回路とを含むこ
とを特徴とする構成である。

本発明の原理を表１及び第１図を用いて説明する。

記憶装置のＯ及び１番地に、それぞれＤ。

，Ｄｌ，Ｄ２，Ｄ３及びＤ４，Ｄ５，Ｄ６，Ｄ７の各４
ビツトの情報符号を記憶させるものとする。特にＤ。−
Ｄ３及びＤ４〜Ｄ７がそれぞれ第１図の１及び２のよう
に与えられたとき、これらの情報符号から表１のパリテ
イ検査マトリクスを用いて上記マトリクスの各行のパリ
テイをとることにより誤り訂正符号ＰＯＰｌＰ２Ｐ３Ｐ
４Ｐ５がつくられる。これは、あらかじめ定められたデ
ータであり、この作成方法は以下に示すような式で作成
できる。これは、前記記憶装置に対して与えられ符号ｅ
は排他的論理和を示す。

まず表１において であり、表２に対しては、 であり、表３において の各式によつて求めうる。

すなわち、表１においてＯで囲まれたものが誤り訂正符
号Ｐ。

−Ｐ５としてつくられる。ＤＯ−Ｄ７にＰ。−Ｐ５が付
加されて第１図の３が生成されると、第１図の４及び５
がそれぞれＯ番地及び１番地に書き込まれる。次に、０
番地が読み出されると、第１図の６のような記憶内容が
読み出され、表１を用いて第１行すなわちＣ２の行のパ
リテイをとると、第１図の８のようにＯとなり、第１図
の６の情報符号Ｄ。

〜Ｄ３には誤りのないことがわかり、第１図の７のよう
な情報符号が読み出される。一方、第１図の９に示すよ
うに、例えばＤ。に誤りがある記憶情報がＯ番地から読
み出されると、表１のＣ２の行のパリテイをとると今度
は、第１図の１０のように１となり、第１図の９に示さ
れた記憶情報中に誤りがあることがわかる。このような
場合には、１番地の記憶情報、第１図の１１に示された
ものを読み出すことにより、ＤＯ−Ｄ７及びＰ。−Ｐ５
から表１を用いて、各行のパリテイをとつてシンドロー
ムＣ２２Ｃ５ラＣＯラＣｌｙＣ３ラＣ４を求めると）第
１図の１２のように、Ｃ２，ＣＯ，Ｃｌが１となるので
、表１からＤ。に誤りがあることがわかり、第１図の１
３のようにＤ。の誤りが訂正されて、正して情報が得ら
れる。以上の説明から明らかなように、０番地の記憶情
報Ｄ。

−Ｄ３，ＰＯ−Ｐ２及び１番地の記憶情報Ｄ４〜Ｄ７，
Ｐ３〜Ｐ５に対して、それぞれパリテイＣ２及びＣ５を
求めることにより１ビツトの誤りがあるかどうか明らか
にされ、もし誤りがなければ、当該番地をそのまま読み
出し、一方誤りがあれば両番地を読み出すと共にシンド
ロームＣ２，Ｃ５，ＣＯ，Ｃｌ，Ｃ３，Ｃ４を得ること
により、１ビツトの訂正を行なつて読み出すことにより
、情報符号に対する誤り訂正符号の比率を少なくするこ
とができる。表２に示したのは、偶数番地へＤ。−Ｄ７
を奇数番地へＤ８〜Ｄｌ５が記憶されるような場合の誤
り訂正符号Ｐ。

−Ｐ５の発生方法を示すパリテイ検査マトリクスの１例
で、誤り訂正符号Ｐ。，Ｐ，，Ｐ２及びＰ３，Ｐ４，Ｐ
５はそれぞれ偶数番地及び奇数番地に情報符号Ｄ。−Ｄ
，及びＤ８〜Ｄ，，と共に記憶される。又、表３に示し
たのは、偶数番地へＤ。〜Ｄ，５を、奇数番地へＤ，６
〜Ｄ３ｌが記憶されるような場合の誤り訂正符号Ｐ。−
Ｐ，の発生方法を示すパリテイ検査マトリクスの１例で
、誤り訂正符号Ｐ。−Ｐ３及びＰ４〜Ｐ７はそれぞれＤ
。−Ｄｌ５と共に偶数番地及びＤ，６〜Ｄ３ｌと共に奇
数番地へ記憶される。なお、表２におけるＰ，及びＰ５
はそれぞれＤ。

〜Ｄ７，ＰＯ，Ｐ２及びＤ，〜Ｄｌ，，Ｐ３，Ｐ４に対
してつくられ、表２におけるＰ，及びＰ，はそれぞれＤ
Ｏ５Ｄｌ５９ＰＯ″Ｐ２及びＤｌ６ゝＤ３ｌＰＰ４″Ｐ
６に対してつくられ、表２に説明した場合と同様で、い
ずれも誤り訂正符号はＯで囲まれたものが最終的につく
られる。ハミング符号と比べて、表２又は表３のパリテ
イ検査マトリクスを付加して、記憶情報を２つのアドレ
スへ記憶させた場合、いずれも１ビツトの誤り訂正符号
が減少することになる。

次に本発明の一実施例について、第２図を参照して説明
する。

第２図を参照すると、本発明の一実施例はｋビツトの書
込情報７０を入力とし、偶数アドレスの書き込情報を保
持する書込みレジスタ５０、書込情報７０を入力とし、
奇数アドレスの書込情報を保持する書込レジスタ５１、
書込レジスタ５０及び５１の書込情報出力７２及び７３
を入力とし、偶数アドレスに書き込まれる誤り訂正符号
７４及び奇数アドレスに書き込まれる誤り訂正符号７５
を出力する１ビツトの誤り訂正符号発生回路５２、偶数
アドレスへ書き込まれる符号７４及び書込レジスタ５０
の出力である７２又は奇数アドレスへ書き込まれる符号
７５及び書込レジスタ５１の出力である７３を、それぞ
れ誤り訂正符号７６及び書込み情報７７として出力する
マルチプレクサ５３と、入力７６及び７７を指定された
アドレスに記憶させ誤り訂正符号７８及び読出情報７９
を出力とする記憶回路５４、偶数番地から読み出された
誤り訂正符号７８及び読出情報７９を入力として、これ
らを保持する読出情報レジスタ５５、奇数番地から読み
出された７８及び７９を入力として、これらを保持する
読出情報レジスタ５６，５５の出力である偶数アドレス
から読み出された誤り訂正符号及び読出情報８０、並び
に５６の出力である奇数アドレスから読み出された誤り
訂正符号及び読出情報８１を入力とし、この情報８０又
は８１に１ビツトの誤りがあるかどうかを示す信号８４
を出力する誤り検査回路５７、前記情報８０及び８１を
入力としシンドローム符号８２を出力するシンドローム
発生回路５８、シンドローム８２を入力とし、誤り位置
を解読し誤り位置を指定する信号８３を出力とする誤り
位置解読回路５９、誤り位置指定信号８３、情報８０及
び８１のうち読出情報を入力として、誤り位置指定信号
８３により８０又は８１の誤りを訂正し、かつ指定され
た偶数アドレス又は奇数アドレスに記憶された情報８５
を出力する誤り訂正回路６０と、アドレス及び読出又は
書込命令入力信号７１並ぴに誤り検査回路の出力信号８
４を入力とし、書込レジスタ５０及び５１をそれぞれセ
ツトする信号８６及び８７、マルチプレクサ５３の出力
７６及び７７が偶数アドレスへ書き込まれるものか、奇
数アドレスへ書き込まれるものかを切替える信号８８記
憶回路５４の指定されたアドレスに書込み又は読出しを
行なわせる信号８９、読出しレジスタ５５及び５６にそ
れぞれ偶数アドレスの誤り訂正符号７８及び読出情報７
９をセツトする信号９０及び奇数アドレスの７８及び７
９をセツトする信号９１、誤り検査回路５７の入力８０
又は８１のいずれかについて検査を行なわせるかを指定
する信号９２、誤り位置解読回路５９の出力８３を出力
させる信号９３と誤り訂正回路６０の出力８５として偶
数アドレスの情報と奇数アドレスの情報のうちいずれを
与えるかを指定する信号９４を出力する制御回路６１と
を含む。

次にその動作について説明する。

先ず、記憶回路５４の２ｍ番地（偶数番地）及び２ｍ＋
１番地（奇数番地）にそれぞれ任意のｋビツトの情報を
書き込む場合には、入力信号７１によりアドレス２ｍを
指定すると共に、読出し命令を発すると、入力７０とし
て最初に与えられた書込み情報は、信号８６によりレジ
スタ５０にセツトされ、次に入力７０として与えられた
書込み情報は、信号８７によりレジスタ５１にセツトさ
れ、これらの出力７２及び７３は誤り訂正符号発生回路
５２に与えられて、偶数アドレス及び奇数アドレスに記
憶される書込惰報と共にそれぞれ記憶される誤り訂正符
号７４及び７５が得られるが、回路５２は例えば表１、
表２、表３に示したようなパリテイ検査マトリクスによ
り誤り訂正符号を発生するものである。

次いで、マルチプレクサＳは、出力信号７６及び７７と
してそれぞれ７４及び７２を出力するように、すなわち
記憶回路５４の偶数アドレスに記憶される誤り訂正符号
及び書込み情報を出力するように、信号８８により制御
された後、信号８９が記憶回路５４の２ｍ番地に信号７
６及び７７を書き込むよう発せられ、当該番地に書込み
が行なわれた後、信号８８は、マルチプレクサ５３の出
力７６及び７７をそれぞれ７５及び７３を出力するよう
に、すなわち記憶回路５４の奇数アドレスに記憶される
誤り訂正符号及び書込み情報を出力するように発せられ
、信号８９は記憶回路５４の２ｎ＋１番地に信号７６及
び７７を書き込むように発せられて当該番地に書込みが
行なわれる。このようにして任意の対になつた偶数番地
及び奇数番地に対して書込みを行なうことができる。一
方、読出し時においては、まず入力信号７１により指定
アドレス及び読出し命令力堵１脚回路６１に入力される
が、以下では指定アドレスが２ｎ番地（偶数番地）であ
る場合について説明する。

Ｆｒｊｌ脚回路６１の出力信号８９は、記憶回路５４の
２ｎ番地を読出すように発せられ、２ｎ番地の誤り訂正
符号７８及び読出し情報７９が出力され信号９０により
レジスタ５５にセツトされた後、その出力８０は誤り検
査回路５７に入力されて、信号９１は８０のパリテイ検
査を行なうよう、すなわち例えば表１、表２のＣ２、表
３のＣ，のパリテイ検査を行なうよう発せられて、信号
８０に１ビツトの誤りがあるかどうかが検査され、もし
誤りがなければ信号８４は匍卿回路６１に対して誤りの
ないことを通知するので、信号９３は誤り位置解読回路
５９の出力８３にその指定を行なわないように発せられ
ると共に、誤り訂正回路６０の出力は、偶数アドレスに
記憶された情報である８０がそのまま読出し情報８５と
して出力されるように信号９４が発生されて、読出しが
行なわれる。ところが、誤り検査回路５７において、記
憶情報８０に１ビツトの誤りがあることが発見されると
、信号８４は匍卿回路６１に対して誤りのあることを通
知し、その結果、信号８９が再び記憶回路５４の２ｎ＋
１番地を読み出すよう発せられ、誤り訂正符号７８及び
読出し情報７９が出力され、信号９１によりレジスタ５
６にそれらがセツトされた後、出力８０及び出力８１が
シンドローム発生回路５８に与えられて、シンドローム
符号８２が発生され、信号９３は誤り位置解読回路５９
の出力として解読信号８３を出力するように発せられる
ので、誤り位置の解読が行なわれて、信号８３が記憶情
報８０及び８１と共に誤り訂正回路６０に与えられて、
信号９４により偶数アドレスの記憶情報の１ビツトが訂
正されて、回路６０の出力として読出し情報８５が出力
されて、誤り訂正が行なわれる。読出しが２ｎ＋１番地
（奇数アドレス）に対して行なわれる場合も、偶数アド
レスの場合と同様で、もし誤りがないと誤り検査回路５
７により判断されれば、そのまま読み出され、１ビツト
の誤りが発見されると、対になつた偶数アドレス２ｎ番
地の記憶情報を読み出すことにより、１ビツトの誤り訂
正を行なうことができる。

第２図の一実施例においては、書き込み時においては、
２ｎ番地と２ｎ＋１番地に対し、１動作で書き込むよう
説明したが、書替えを行なうような場合には、一度２ｎ
又は２ｎ＋１番地を読出した後、これらを書込み情報と
して用いると共に２ｎ＋１又は２ｎ番地へ書込む情報を
外部から与えて書き込む動作を行なうような装置として
拡張できることも明らかである。

さらに、第２図の一実施例においては、誤り訂正符号を
共有する番地が２つであつたが、３つ以上に拡張するこ
とも容易にできることも明らかである。

本発明は、以上説明したように、同一アドレスに記憶さ
れる情報符号数をｋ１検査符号数をｍとし、ｊ個のアド
レスに対して１ビツトの誤りを訂正できる場合には、で
表わされ、従来の と比較した場合の如く２個のアドレスに対して１ビツト
の誤りを訂正できる場合は、となり、同一の符号検査数
ｍに対してｍ≧３の場合、同一アドレスに記憶される情
報符号数の許容範囲は、多くなる。

これはすなわち情報符号数に対する誤り訂正符号数の割
合を減少させると共に、各アドレスの情報ビツトに付加
された誤り訂正符号の一部を用いて読み出された記憶情
報に誤りがあるかどうか判定し、誤りがなければそのま
ま読み出し、誤りがあれば、これらの複数個のアドレス
の全てを読み出し訂正を行なうことができる効果がある
。本発明を用いた場合通常読出し情報に誤りがあること
は極めてまれであるので、複数個のアドレスを読み出す
ために要する時間の増加は問題とならないし、一方書込
み時には複数個のアドレスに書込みを行なうのに時間を
要するが、通常の高速記憶装置においては、読出しに比
べて書込みの比率が極めて低く、大きな問題とはならず
、さらに読出し専用記憶装置においては、非常に有効で
ある。

また、記憶装置に使用される誤り訂正符号を複数のアド
レスの情報符号に対して１つ与えると共に、１つのアド
レスの誤り訂正符号のみで当該アドレスに記憶された情
報に誤りがあるかどうかを検出することができるような
記憶装置を構成することにより、情報符号数に対する誤
り訂正符号数を減らすことにより、誤り訂正符号を用い
た記憶装置を安価につくることができる効果がある。

ところで、本発明によれば、読出し動作は誤りがほとん
どないので速いが、書込み動作は、誤り訂正符号が分散
されるので複数のアドレスに対して行なう必要があり遅
くなる。しかしながら、通常の計算機では、読出しの方
が書込みよりも比率がかなり高く、又読出し専用記憶装
置に対しては非常に有効となる。

【図面の簡単な説明】

第１図は本発明の原理を説明する図、第２図は本発明の
一実施例を説明する図である。 ５０，５１・・・・・・書込レジスタ、５２・・・・・
・誤り訂正符号発生回路、５３・・・・・・マルチプレ
クサ、５４・・・・・・主記憶部、５５，５６・・・・
・・読出レジスタ、５７・・・・・・１ビツト誤り検査
回路、５８・・・・・・シンドローム発生回路。

Claims (1)

【特許請求の範囲】
1. １ データと第１の検査ビットと第２の検査ビットとを
   一組の情報とし、一群をなす複数組の前記情報のうち複
   数のデータによつて各組の第１の検査ビットが作成され
   、各組に属するデータと第１の検査ビットのすべてによ
   りそれぞれの組の第２の検査ビットが作成される１以上
   の群を１組単位で記憶する記憶手段と、この記憶手段の
   アドレスを指定するアドレス指定手段と、このアドレス
   指定手段から出力されるアドレス指定信号により前記一
   組の情報を読み出した後、前記一組の情報の全てのビッ
   トに対し前記第２の検査ビットを用いてバリテイ検査を
   行ない１ビットの誤りがあるか否かを検出する１ビット
   誤り検出手段と、この検出により誤りがある場合、この
   組が属する群の複数組の情報を前記記憶手段から読み出
   してこの群の前記第１および第２の検査ビットを用いて
   １ビット誤りを訂正する誤り訂正手段とを含むことを特
   徴とする記憶装置。