JPH0315216B2 - - Google Patents

Description

【発明の詳細な説明】

発明の分野 この発明は、メモリ・システムに関し、特に誤
り検出及び誤り訂正回路を含むメモリ・システム
に関する。 従来技術の説明 デイジタル処理においては、２進データ・ビツ
トにおける誤りの検出と訂正を必要とすることが
よくあり、誤り検出及び訂正技術は従来からあつ
た。これらの技術には付加的な情報ビツトを発生
し、既存データ・ビツトに付加するものが含まれ
る。換言すれば、付加ビツトはもとの情報ビツト
から生成され、より長いビツト長のワードを形成
するようにもとの情報ビツトと組合される。これ
らの付加ビツトはパリテイ・ビツトと呼ばれ、場
合によつて選択したビツト・グループ及び全デー
タ・ワードに対して偶数又は奇数となるように発
生される。マトリツクスはデータ倍され、パリテ
イ・ビツトを発生させることがよくある。これら
マトリツクスはパリテイ・チエツク・マトリツク
スと呼ばれる。22ビツト・コード（16データ・ビ
ツト＋６パリテイ・ビツト）用のパリテイ・チエ
ツク・マトリツクスは次のような性質があること
が明らかとなつた。 (a) マトリツクス内の各列は単一誤り訂正機能を
保持するため固有でなければならない。 (b) 単一誤りの場合、誤りビツトの位置に対応す
る列はシンドロームとして再生される。 (c) ２以上の多重誤りの場合、得られた又は生成
されたシンドロームは、誤りを含むビツトに対
応するパリテイ・チエツク・マトリツクス列の
排他的論理和からなる。二重ビツト誤り検出回
路の場合、パリテイ・チエツク・マトリツクス
の各列は固有であるだけでなく、各列は他の２
列の排他的論理和であつてはならない。この情
報はパリテイ・マトリツクスにより誤りの検出
及び訂正を判断するのに有用であるが、データ
の特定の状態を検出するのが望ましいことがよ
くある。この場合、全データ・ビツトの２進状
態が０又は１であることを検出することが必要
とされる。 この発明の目的は、誤り検出及び誤り訂正技術
を用いることにより訂正したデータを生成すると
共に、データがある状態となつたことを表示をす
るメモリ・システムを提供することである。 発明の要約 この発明によれば、情報メモリを含むデイジタ
ル処理システムに情報メモリを備える。この情報
メモリには、いくつかのデイジタル情報ビツトを
受取り、これらの情報ビツトに付加することによ
り１つの情報ワードを形成する数、ビツトのパリ
テイ・ビツトを発生するパリテイ・ビツト発生回
路が備えられる。パリテイ・ビツト発生器にはパ
リテイ・ビツトを修飾するマトリツクス加算器が
接続される。このワードとその修飾パリテイ・ビ
ツトはメモリ回路に記憶される。 この発明の他の特徴によれば、このメモリ情報
システムは、メモリ回路に記憶され、パリテイ・
ビツトをを含む情報を受取り、これらパリテイ・
ビツトを修飾する第２のマトリツクス加算器を備
える。この第２のマトリツクス加算器にはシンド
ローム発生器が接続され、情報ワード及び修飾パ
リテイ・ビツトを受取り、数ビツトのシンドロー
ム・ビツトを発生する。このシンドローム発生器
には情報補正回路が接続され、情報ビツト及びシ
ンドローム・ビツトを受取る。次いで、情報補正
回路はシンドローム・ビツトにより情報ビツトを
処理し、補正した情報ワードを発生する。シンド
ローム発生器にはシンドロームを処理し、かつ記
憶したデータのある状態を表わす一連のフラグ出
力を発生するシンドローム発生器が接続される。 好ましい一実施例においては、マトリツト加算
回路に接続されたパリテイ・ビツト発生回路を含
み、かつ両回路をメモリ回路に接続する情報シス
テムが備えられる。このパリテイ・ビツト発生回
路は、電気的には、データ・マトリツクスとして
取扱うデータにより（モジロ２の演算にて）掛算
され、数ビツトのパリテイ・ビツトを発生し、こ
れをデータ・ワードに付加して一つの記憶ワード
を形成するパリテイ・マトリツクスを含む。この
パリテイ・ビツト発生器は排他的論理和回路を用
いてマトリツクス掛算を実行する。更に、このメ
モリ・システムにはデータ及びパリテイを表わす
特殊ワードを発生してメモリ回路に記憶するフラ
グ発生器も含まれる。この特殊ワードはメモリ回
路をアクセスする装置に対して特定の状態を定義
するために用いられる。 この発明の他の特徴によれば、情報メモリは更
にメモリ回路から情報を受取り、パリテイ・ビツ
トを修飾する第２のマトリツクス加算器を備え
る。このマトリツクス加算器にはシンドローム発
生器が接続され、これには数ビツトのシンドロー
ム・ビツトを発生するパリテイ・マトリツクス掛
算機能が含まれる。シンドローム発生器にはシン
ドローム・ビツトにより受取つた情報ビツトを処
理し、訂正された情報ワードを生成する情報訂正
回路が接続される。シンドローム発生器にはシン
ドローム・ビツトを処理し、定義した特殊状態を
表現するフラグ出力を発生するフラグ検出回路も
接続される。 この発明の好ましい他の実施例において、シン
ドローム発生器は、電気的にパリテイ・マトリツ
クスをデータ倍すると等価な（モジロ２演算で
の）マトリツクス掛算を実行するように接続され
た複数の排他的論理和回路を含む。フラグ発生回
路は記憶用の特殊ワードを発生するのに用いられ
るもので、データ・ビツトとパリテイ・ビツトの
両方を表わす一組のビツトを発生する。この特殊
ワードがシンドローム発生器に入力されると、シ
ドロームを発生し、このシンドロームがフラグ検
出回路により解析されると、フラグを発生して定
義した状態を表わす。この実施例には特定のマト
リツクスと電気的に同等なものが得られるように
インバータと直結線からなるマトリツクス加算器
も備えられる。 更に他の実施例では、２進形式のデータ・ビツ
トを発生する中央処理装置を有するデイジタル処
理システムが備えられる。この中央処理装置はメ
モリ・システムに接続される。このメモリ・シス
テムには、中央処理装置からデータ・ビツトを受
取り、これらデータ・ビツトを処理し、１つの情
報ワードを形成するようにデータ・ビツトに付加
される数ビツトのパリテイ・ビツトを発生するパ
リテイ・ビツト発生器が備えられる。情報ワード
は更にマトリツクス加算器により処理され、マト
リツクス加算器は情報ワードにおけるパリテイ・
ビツトを修飾する。次にこの情報ワードはメモリ
に記憶される。フラグ発生器は可能とするそれぞ
れの状態を表わす特殊情報ワードを発生する動作
もする。これらの特殊ワードは他の情報ワードと
共にメモリにも記憶される。これら情報ワードが
アクセスされると、この情報ワードにおけるパリ
テイ・ビツトを修飾する。更に、この情報ワード
はシンドローム発生器により処理され、数ビツト
のシンドローム・ビツトを発生する。このシンド
ローム発生器には、情報訂正回路が接続され、こ
れに情報ワードを入力し、この情報ワードのデー
タ・ビツトをシンドローム・ビツトにより処理
し、データ・ビツトにのみ含まれる訂正情報ワー
ドを発生させる。このシンドローム発生器にはフ
ラグ検出回路も接続され、これにシンドロームを
入力し、このシンドロームを処理してフラグ出力
を発生させる。このフラグ出力は特殊状態を表わ
すもので、フラグ発生回路により符号化され、か
つ情報ワードとして記憶されていたものである。 この発明の特徴とされる新規の構成を特許請求
の範囲に記載している。しかし、この発明自体
は、他の特徴及び効果と共に、付図と関連させて
読む以下の詳細な説明を参照することにより十分
に理解されるものである。 好ましい実施例の詳細な説明 先に述べたように、この発明の目的はあるデー
タの状態、特に２データの状態を定義する誤り訂
正メモリ・システムを提供することである。その
第１はデータがデータ・バスののフローテイング
を示す全て１のときであり、その第２はデータ・
バスの短絡を示す全て０のときである。これは、
データをパリテイ・ビツトにより評価するとき
に、固有の３重誤りとして認識可能なメモリ・デ
ータ・バスからの入力を全て１又は全て０とする
ことにより達成される。可能とするパリテイ・チ
エツク・マトリツクスの列は使用した列の排他的
論理和として使用又は消去されていないもので、
実際にシンドロームの固有な３重誤りであること
が明らかとなつた。これらの２状態（０及び１）
を定義するのが好ましいので、データ・バスのパ
リテイ及びデータ・ビツトの評価に基づく固有な
３重誤りにこれら２つの状態を表わすのが好まし
い。しかしながら、偶数又は奇数パリテイを用い
る符号は固有の３重誤りとして両シンドロームを
発生することはない。通常のパリテイ・チエツ
ク・システムは、表に示すようなパリテイ・マ
トリツクスと線形マトリツクスのデータ・ビツト
とを掛算する形式をもつ。

【表】

【表】 このマトリツクス掛算の結果は、一組のパリテ
イ・ビツトとなる。２進のマトリツクス掛算を用
いるときはモジユロ２の演算を用いる。表は22
列からなる偶数パリテイのマトリツクスである。
しかし、最初の６列は除去でき、残りの16列マト
リツクスと16ビツト・データとの掛算により、６
ビツト・シンドロームが得られる。この発明にお
いては基準符号のマトリツクス掛算により得たシ
ンドロームは他のマトリツクスに加算される。こ
の第２マトリツクスは列ベクトルである。マトリ
ツクス掛算のシンドローム結果に加算した列ベク
トル111000を用いることにより、フローテイング
の場合、及び３重誤りに対するバス短絡の場合の
両者を表わすことが明らかとなつた。このシステ
ムを実行するためには16ビツトのデータを表の
マトリツクスの最初の16列により掛算することが
必要である。この結果は６ビツトのシンドローム
列ベクトルとなり、これを列ベクトル111000に加
算する。この加算の結果は６ビツトの列ベクトル
となり、これを付加的なパリテイ・ビツトとして
用い、このパリテイ・ビツトを16ビツトのデータ
と組合せることにより、メモリに記憶する22ビツ
トのメモリ・ワードが得られる。 22ビツトのメモリ・ワードをメモリからアクセ
スするときは、再び６ビツトのパリテイが同一列
のベクトル111000に付加され、列ベクトルの和は
メモリからの16ビツトのメモリ・ワードと組合さ
れる。この22ビツトの列ベクトルは表の22列マ
トリツクスにより掛算され、６ビツトのシンドロ
ームを生成する。この６ビツトのシンドローム
は、表に訂正可能な１ビツト誤りを示すものと
して、又は表に検出可能な２重ビツト誤りを示
すものとして示されている。更に表はフラグ
（フラグ０〜フラグ10）として示す固有の３重誤
りを含む残りのシンドローム・パターンを表わ
す。

【表】

【表】

【表】

【表】

【表】

【表】

【表】

【表】

【表】

【表】

【表】 前述のように表のマトリツクス及び列ベクト
ル111000を用いると、フラグ０は、全てのデータ
が正常であることを示す固有のシンドロームとな
る。フラグ１は、全てのビツトが１、又はデー
タ・バスがフローテイングであることを示すシン
ドロームである。フラグ７はデータ・バスが短絡
されていることを示す。表の他のフラグは定義
されていない。しかし、回路をメモリに付加して
データをアクセスしたときに、誤り訂正回路によ
り検出されるデータとしてフラグをプロセツサ又
は他の装置によりメモリに記憶させるようにして
もよい。これらフラグは処理システムにより用い
られ、記憶している特殊データの形式又は実行す
べき特殊なソフトウエア・ルーチンを示すように
してもよい。一実施例においてはフラグは、プロ
セツサにインタラプトを発生させるフラグ検出回
路から出力を発生させる。このインタラプトによ
り、特定のソフト・ウエア・ルーチンを実行さ
せ、メモリから処理装置にロードするデータの残
りの部分を正しく処理させる。この方法では、プ
ロセツサがフラグの存在を判断するためにデータ
を読込むことを必要とすることなく、フラグをメ
モリにロードできる。このフラグは、誤り訂正回
路によりデータを処理するときにセツトされるの
で、コンピユータの時間が節約される。 第１ａ図はメモリに情報ワードを記憶するた
め、既に述べたパリテイ・ビツト発生器及びマト
リツクス加算器を用いるメモリ・システムを示
す。16ビツトのデータがパリテイ・ビツト発生器
に入力され、これは６ビツトのパリテイをマトリ
ツクス加算器に入力する。マトリツクス加算器
は、既に説明したように入力された６ビツトのパ
リテイ・ビツトと列ベクトル111000とを加算して
第２の６ビツト・パリテイ・ビツトを発生させた
後、16ビツトのデータと組合せて記憶する22ビツ
トの情報ワードを発生させる。この情報ワードは
第１ｂ図に示す回路によりメモリから、アクセス
される。22ビツトのデータ・ワードはマトリツク
ス加算器に入力され、これは第１ａ図において既
に加算された22ビツトワードの最初の６ビツト又
はパリテイ・ビツトに列マトリツクス111000を加
算する。この６ビツト列のベクトル加算の結果は
16ビツトのデータ・ワードに加算された後、22ビ
ツトのワードをシンドローム発生器に入力して６
ビツトのシンドロームとなる。６ビツトのシンド
ロームは16ビツトをデータと共に訂正回路に入力
される。シンドローム発生器の出力はフラグ検出
回路にも入力され、フラグ出力とデータ正常信号
を発生させ、このデータ正常信号は訂正回路との
組合により、訂正回路のデータが有効であること
を判断させることができる。 第２図は第１ａ図のパリテイ・ビツト発生器及
び第１ｂ図のシンドローム発生器の論理回路図で
ある。第１ａ図においては、16ビツトの入力があ
るので、第２図の排他的論理和ゲート（P₀〜P₅
で示す）は０入力となる。従つて、16ビツトは入
力D₀〜D₁₅で示すように排他的論理和ゲートに入
力され、パリテイ・ビツトBS₀〜BS₅を得る。シ
ンドローム・ビツトを受取る第１ａ図のマトリツ
クス加算器を第３図に示す。マトリツクス加算器
は単なる３つのインバータ及び通過する３本線か
らなり、列ベクトル111000のモジユロ２によるマ
トリツクス加算の電気的な等価出力をする。この
結果、第３図の22ビツトは第１ａ図のようにメモ
リに記憶される。データをアクセスするときは、
データを第３図と同一のマトリツクス加算器であ
る第１ｂ図のマトリツクス加算器に渡す。第１ｂ
図のマトリツクス加算器の出力は、修飾シンドロ
ーム、ビツトをもつ22ビツトのメモリ・ワードで
あり、第２図のシンドローム発生器と同一のシン
ドローム発生器に入力される。このシンドロー
ム・ビツトは第２図に示すようにP₀〜P₅からな
る。第１ｂ図のシンドローム発生器の出力は第２
図に示すようにBS₀〜BS₅である。 第１ｂ図の訂正回路は第４ａ図に示す16論理回
路の形式からなる。第４ａ図の16論理回路におけ
る実際の入力を第４ｂ図の表に示す。従つて、
CD₀ビツトの場合、入力は図示のようにD₀，
BS₂，BS₄及びBS₅である。訂正回路の出力は
CD₀〜CD₁₅ビツトである。しかし、このデータ
の有効性はフラグ検出回路により決定される。フ
ラグ検出回路は、前述のように固有の３重誤りと
して示したフラグのみではなく、正常データ、即
ち誤りなし、１ビツト誤り（訂正可能）及び２重
ビツト誤り（検出可能）の存在も検出する。フラ
グ検出回路には第５ａ図に示すように11アンド・
ゲートが含まれる。11アンド・ゲートに対する実
際の入力を第５ｂ図の表に対応する出力と共に示
す。シンドロームが全て０のときにデータ正常が
出力されることに注目すべきである。フローテイ
ング・バスをシンドロームの000111により示し、
データ・バスをシンドローム111000により示す。
フラグ検出回路に対する２重誤り検出回路を第５
ｃ図に示す。第５ｄ図は単一誤り検出回路を示
す。第５ｅ図は、データ正常信号を発生するのに
用いるオア・ゲートを示し、このオア・ゲートは
訂正回路から出力されるデータの評価信号であ
る。 デイジタル・プロセツサが誤り訂正信号を用い
るときは、第１ａ図に示すような回路のマトリツ
クス加算器とメモリとの間にフラグ発生器を挿入
することができる。このフラグ発生器は、第１ｂ
図の回路によりデコードした場合に表４に示すよ
うに定義されたフラグの一つを発生するビツト・
パターンを発生する。このようにしてデイジタル
処理システムはメモリのデータにフラグを付け、
後にアクセスするときに前述の方法で処理をす
る。

【図面の簡単な説明】

第１ａ図はシンドローム発生器及びマトリツク
ス加算器により処理されたデータを記憶するメモ
リ・システムのブロツク図、第１ｂ図は誤り訂
正、誤り検出及びフラグ検出回路を含むメモリ・
システムのブロツク図、第２図はシンドローム発
生器の論理回路図、第３図はマトリツクス加算器
の論理回路図、第４ａ図は訂正回路の要素の回路
図、第４ｂ図は訂正回路の入力及び各データ・ビ
ツト位置を示す図、第５ａ図はフラグ検出回路に
おけるフラグ発生器の論理図、第５ｂ図は第５ａ
図に示す異なる回路要素への入力を定義する図、
第５ｃ図は２重誤り表示器を減少させる論理回路
図、第５ｄ図はフラグ検出回路における単一誤り
表示器を形成する論理回路図、第５ｅ図はフラグ
検出回路におけるデータ誤りなし表示器を形成す
る論理回路図である。

Claims (1)

1. 【特許請求の範囲】 １ 複数の情報ビツトを受け取り、当該複数の情
   報ビツトに付加して一つのワードを形成する様に
   複数のパリテイ・ビツトを発生するパリテイ・ビ
   ツト発生器と、 前記パリテイ・ビツト発生器に接続されて前記
   パリテイ・ビツトを修飾するマトリツクス加算器
   と、 前記マトリツクス加算器に接続されて前記ワー
   ドを記憶する記憶手段、 とを備えることを特徴とする誤り検出及びフラグ
   回路をもつ情報メモリ。 ２ 特許請求の範囲第１項に記載の誤り検出及び
   フラグ回路をもつ情報メモリにおいて、 前記パリテイ・ビツト発生器はパリテイ・マト
   リツクスとデータとのマトリツクス掛け算をおこ
   なつて前記パリテイ・ビツトを発生することを特
   徴とする情報メモリ。 ３ 特許請求の範囲第２項に記載の誤り検出及び
   フラグ回路をもつ情報メモリにおいて、 前記パリテイ・ビツトは前記パリテイ・ビツト
   発生器内の複数の排他的論理和回路によつて発生
   されることを特徴とする情報メモリ。 ４ 特許請求の範囲１項に記載の誤り検出及びフ
   ラグ回路をもつ情報メモリにおいて、 前記記憶手段に記憶される特殊ワードがフラグ
   発生器内で発生され、当該特殊ワードは前記記憶
   手段をアクセスする全ての装置に対して特殊状態
   を表すことを特徴とする情報メモリ。 ５ 特許請求の範囲第１項に記載の誤り検出及び
   フラグ回路をもつ情報メモリにおいて、 前記マトリツクス加算器に接続されたシンドロ
   ーム発生器は修飾されたパリテイ・ビツトを持つ
   前記情報ワードを受け取つて複数のシンドロー
   ム・ビツトを発生し、前記シンドローム発生器に
   接続された情報訂正回路が前記シンドローム・ビ
   ツトをもつ情報ビツトを処理して訂正された情報
   ワードを発生し、前記シンドローム発生器に接続
   されたフラグ検出回路が前記シンドローム・ビツ
   トを受け取つてフラグ出力を発生することを特徴
   とする情報メモリ。