JPS58501924A - パツケ−ジ・エラ−訂正装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 パッケージ・エラー訂正装置 本発明はメモリ・アレイにおけるパッケージ・エラーヲ訂正するエラー訂正コー ド（ＥＥＣＣ）に関する。具体的には、本発明は単一モノリシック・メーモリ・ チップの全てのエラーを訂正し、かつ２個のモノリシック・チップの各々が単一 ワードからの２ビツトを含むとき、メモリにおけるそのような２個のチップの全 てのエラーを検出するエラー訂正コードに関する。

、エラー訂正の観点からすれば、半導体メモリ・システムは１個のチップにつき １ビツトの割合で構成されることが望ましい。このような構成のメモリでは、７ ２ビツトのコードワードを記憶するのに７２個のチップを必要とし、ワードの各 ビットは異ったチップ上におかれる。チップごとに１個のビットを使用するメモ リ構成の利点は、チップが全面的にエラーを示すとき、単一エラー訂正／二重エ ラー検出（ＳＥＣ／ＤＥＤ）のエラー訂正コードを使用できることである。

チップごとに１個のビットを使用する構成の不利点は、それがチップごとに複数 ビットを使用する構成よりも多くの電力を消費することである。何故ならば、Ｅ ＣＣコードワードを形成するのに多くのチップが必要であり、各チップはメモリ がアクセス場れるときパワーアップされねばならないから（２） である。従って、チップ当り複数ビットを使用するように構成されたメモリにお いてビット・エラー及びパッケージ・エラーの尽力によって生じた嗅−エラーを 訂正し二重エラーを検出するＦＥＣＣコードが非常に望まれる。

ハラｙｒ　−シ・エラーを検出するための単一エラー訂正／二重エラー検出コー ドは、米国特許第４０７７０２８号に開示されている。この特許に開示されたコ ードの問題点は、それがパソ、ｔｙ−−シ・エラーを訂正しないことである。

Ｂｏｓｓｅｎの米国特許第３６３４８２１号に説明忌れるよう７ｂ接続コードは 、追加のチェック記号を付加することによって、単一マルチビット・パッケージ のエラーを訂正し２個のマルチビット・パッケージのエラーを検出するように適 合化させることができる。ｂ隣接コードを用いる場合の問題点は、検出及び訂正 を行う場合に、多数のチェック・ビットが必要ときれることである。そのような 隣接コードを使用すれば、１バイトのエラーを訂正し２バイトのエラーを検出す るために、６個のＥＣＣチェック・ビット・バイトが必要である。そのコードに よって訂正可能なバイト数ｎは、ｎ−２ｂ＋２に等しい。かくて、２ピツ１ト・ バイトの場合、ｎ二重である。６個のバイトの中の６個はＥＣＣチェック・ビッ ト・バイトであるから、５バイトのみがデータ・ビット・バイト全ての単一パン ケージ・エラーを訂正し、全ての二重パッケージ・エラーを検出する他の方法は 、リード・ソロモン（Ｒｅｅｄ−８ｏｌｏｍｏｍ　）コードを使用することであ る。このような手法は、１９８０年１０月１日から５日まで開催てれた第１０回 エラ一対策コンピュータ・シンポジウム会議録の第４１頁から第４６頁に、「メ モリ・システムのための単一バイト・エラー訂正−二重バイト・エラー検出コー ド」と煩してＫａｎｅｄ及びＦｕｊｉｗａｒａＫよって説明てれている（Ｐｒｏ ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１０ｔｈ　Ｆａｕｌｔ　ＴｏｌｅｒａｎｔＣ ｏｍｐｕｔｉｎｇ　Ｓｙｍｐｏｓｉｕｍ：Ｓｉｎｇｌｅ　Ｂｙｔｅ　Ｅｒｒｏｒ Ｃｏｒｒｅｃｔｉｎｇ−Ｄｏｕｂｌｅ　Ｅ３ｙｔｅ　Ｅｒｒｏｒ　Ｄｅｔｅｃｔ ｉｎｇＣｏｄｅｓ　ｆｏｒ　Ｍｅｍｏｒｙ　Ｓｙｓｔｅｍｓ）。その記事によれ ば現存するリード・ソロモン・パッケージ・エラー訂正コードは、チェック・ビ ットを効率的に使用する長いコード長パッケージ・エラー訂正コードを発生する ため拡張でれるっこの一般化てれたコードは概してチェック・ビットを効率的に 使用できるが、モジュラ−化芒れたものは、それほど効率的でない。

従って、パッケージ・エラーが１つ又はそれ以上のエラー・ビットである場合に 、単一パッケージ・エラーを訂正し二重パッケージ・エラーを検出するために必 要な訂正ビットの数を効率的に使用する新しいモジュラ−化てれたコードが望本 発明によれば、データ・ワードをコード・ワードへエン（４） コードする符号化手段が設けられ、任意のパッケージニ存在する全ての単一ビッ ト・エラー・シンドロームの排他的ＯＲ結合は、各パッケージごとに独特の合成 シンドロームを生じる。このコードは単一エラー検出二重エラー訂正コードであ って、ｍ個のビットをカバーするように拡張てれている。ここでｍはパッケージ 中のビットの数に等しい。

本発明の目的は、単−及び二重ビット・エラーを訂正し、同時に単一パッケージ ・エラーを訂正するとともに二重パッケージ・エラーを検出する新しいコードの 使用システムを実現することである。

本発明の他の目的は、先行技術で必要とされるよりも少ないチェック・ビットを 使用して、単一パッケージ・エラーを訂正し二重パンケージ・エラーを検出する システムを実現することである。

本発明の他の目的は、全ての単一パッケージ・エラーヲ訂正し、全ての二重パッ ケージ・エラーを検出するモジュラ−化されたコードの使用システムを実現する ことである。

図面の簡単な説明 第１図は本発明を使用するメモリの略図を示し、第２図は第１図に示きれたメモ リのＥＣＣ：ｒ−ンコーダの略図を示し、第３図は第１図に示されたメモリのＥ ＥＣＣデコーダの略図を第１図において、２４ビット・コードワードはメモリの １２個のモノリンツク・チップ１０の上に記憶てれる。各チップ」二では２個の ビットが使用きれる。後に明らかになる理由によって、８個のビットはチェック ・ビットであり、１６個のビットはデータビットである。各チップ１０の」二に あるデータ・ビットが単一の記号を表わすとすれば、コードワードは１２個の記 号より構成てれる。本発明によれは、各記号は単一ビットであると仮定きれ、Ｓ ＥＣ／ＤＥＤエラー訂正コードは、この仮定に基いて発生でれる。

３個の同様な物体をＲ個のポケ−）・に置く順列を考える。

Ｋ−Ｒ・（Ｒ−１）・（Ｒ−２）／６個のデータ記号とすれは、■（７２通りの 可能な順列が存在する。そのよう々順列の各々について、次の規ｌ１１１Ｊに従 いＲ成分列ベクトル■を形成する。

■は空のボケートに対応する位置にＡを含み、物体を含むポケットに対応する泣 ＠にＢを含む。例えばＲ＝４、Ｋ＝８のきき、次のような４個の列ベクトルが存 在する。

従って、Ａ及びＢを含むに７２個のＲ成分ベクトルを形成することができるっベ クトルのあるもの（ｄ、１世のベクトルの循環ソフトであるっこわらのベクトル をいくつかの等価の集合に群別し、谷集（６） 合中のベクトルが集合代表の循環シフトであるようにすることができる。■１を 等価集合の代表であるとする。Ｖｌの６個のＢへ順次にＢ、Ｃ，Ｄを代入するこ とによって、ベクトルｖ２が形成される。ここで、ｖ１７含む等価集合にあるベ クトルの数だけｖ２を循環シフトすることによって、ベクトル集合を発生する。

この手順によって、Ｋ／２個のベクトルを発生することができる。Ａ及びＢの成 分のみを有するベクトル集合と、Ａ、Ｂ、Ｃ，Ｄの成分を有するベクトルの誘導 された集合とを結合することによって、Ｋ個の列ベクトルが得られる。形成され たマトリクスをＰと呼べば、Ｒ＝４のとき次のようになる。

ここで、Ｐの中のＡ、Ｂ、Ｃ，Ｄへ次のマトリクスを代入する。

（７）　特表昭５８−５０１９２４　（３）マトリクスＰは８×１６の２進マト リクスとなる。２進マトリクヌＰをオーダ２Ｒの単位行列で連結すると、次の表 に示されるパリティ・チェック・マ］・リクスＨが得られる。構成されたコード はＣＦ　（４）の上で４の最小距離を有し、従って、１つの記号が２ビツトで構 成てれる場合に、上記コードは単一記号エラーを訂正し、かつ二重記号エラーを 検出することができることを証明することができる。

次の表は、第１図に示されるメモリに関してＥＣＣのパリティ・マトリクスＨと マツチング・マトリクスＭとを示す。

（９） 爆 パリティ・マトリクス■］において、各列はコード・ワードの１ビツトを弄わす 。それぞね０２列の間にある垂直線は、パッケージ又はチップの境界を弄わす。

即ち、２４ビツト・コード・ワードにあるそれぞれの２ビツトは、第１図に示さ れるような異なったチップ上にある。マトリクスＭの８行の各々における２進の １は、１６個のデータ・ビットと共に記憶てれる８個のチェック・ビットの１つ を発生するため、どのビットがエンコーダによって相互に排他的ＯＲ結合てれる かを示す。例えば、マトリクスの最上位の行から、最初のチェック・ビットを発 生するため、ワード中のデータ・ビット１、ろ、９．１１．１２．１３．１６は 相互に排他的ＯＲ結合される。

マツチング・マトリクスＭは、デコーディング中に発生されたシンドロームを示 す。もしエラーが存在しない場合、シンドロームは、マトリクスの第１列に示し たように、８個の口のヌトＩＪングである。もし訂正可能又は訂正不可能なエラ ーがあれば、シンドロームの１つ又はそれ以上は１である。

マツチング・マトリクスＭにおいて１を含む各列は、ビット位置の１つにおける 単一エラーのシンドローム・パターンテあるか、又は単一パッケージ・エラーの シンドローム・パターンである。例えば、マツチング・マトリクスＭの最初の２ つの垂直線の間にある３列の最初の列は、単一エラーがワードの最初のビット中 に生じた時のシンドロームを示し、第２（１０） の列は、ワードの第２ビツト中に位置する単一エラーのシンドロームを示し、最 初の２つの列のシンドロームの排他的ＯＲである第６の列は、ワード中の最初の ２つのビットを含むパッケージのエラーに対するシンドローム・パターンテある 。

第２図に示されるように、第１図のメモリに記憶されたパリティ・ビットを発生 するため、訂正機能のある排他的ＯＲエンコーディング・トリー１２が使用され る。エンコーディング・トリーは、前記のパリティ・マトリクスＨに従って構成 されている。例えば、チップ９の最初のビットニラるデータは、チップ１．２． ５．６．７の最初のビットにあるデータと、チップ６．８の第２ビツトにあるデ ータとを排他的ＯＲ結合したものである。もし２路排他的ＯＲゲートが使用され れば、各チェック・ビットは、６個の排他的ＯＲゲートと、論理遅延の６レベル とを使用して発生される。

第３図において、シンドローム発生器１４の８ビツト出力（ｄ、第１１図のチッ プ１０から読出された２４個のデータ・ビットとチェック・ビットを排他的ＯＲ 結会したものである。

シンドローム・デコーダ１６は、米国特許出願第１０３６３６号に示されるもの と同じである。デコーダ１６は６７ワードの連想記憶装置であり、単一ビット又 はパッケージ・エラーに対するシンドローム・ビット・パターン、及びエラーの ないワードのシンドローム・ビット・パターンの各々が、異ったワード・ロケー ７ョンに記憶てれている。

（１１）　特表昭５８−５０１９２４（４）谷シンドロームと共に、エラー・ビ ットの位置を示すビット番号が２進シーケンヌで記憶てれている。シンドローム ・デコーダ１６のテーブルが質問でれて一致状態を生じると、記憶てれたシンド ローム及びエラーのビット位置を示す６ビツトの２進数が、連想記憶装置がら読 出てれる。

シンドローム発生器１４がオール・ゼロのシンドローム、換言すれば、アクセス されたワード中にエラーがないことを示すシンドロームを発生したものと仮定す る。連想記憶装置中のシンドロームと共に記憶てれたオール・ゼロのシンドロー ムは、エラーがないことを示す６個の追加的なゼロのストリングである。この６ 個のゼロのストリングはデコーダ１８へ送られる。デコーダ１８はゲート制御回 路２ｏヘノ−エラー信号（ＮＥ）を送る。ゲート制御回路２ｏは、出力レジスタ ２２に記憶されたエラーのないデータ・ワードを転送するためのゲート信号を、 ゲート２１のために発生する。ここで、シンドローム発生器は、単一ビット・エ ラーがビット・ロケー７ョンｌで生じたことを示すシンドロームｓ１を発生する ものと仮定する。単一ビット・エラーを示す全てのシンドロームは、シンドロー ム・デコーダ１６に記憶てれているから、シンドロームＳｉの質問は、６ビツト の２進表現になったビットｉのロケーションが、シンドローム・デコーダがう読 出される。７エラー・ビットのロケーションを示す６ビツト２進数はデコーダ１ ８へ送られる。デコーダ１８は、それをピッ（１２） ト・（ンハータ２４　（７）２４（固のロケーションの１つヘデコードする。ビ ット・インバータ２４は、出力レジスタ２２に記憶てれたワードのビットｌを反 転するために設けられる。ピッ）ｉが反転された後、ゲート制御回路２ｏは、訂 正てれたワードをプロセッサへ送るための信号を、ゲート２１のために発生する 。もしシンドローム発生器１４がパッケージ・エラー・シンドロームＳｐｉを発 生すると、連想記憶装置への質問は、パッケージｐｉのロケーションを、６ビツ ト２進表現で発生する。このエラー・ビットのロケーションを示す６ビツト２進 数はシンドローム・デコーダ１６から読出すれ　デコーダ１８へ送られる。デコ ーダ１８は、パッケージ・エフ　−を構成するビット１及び１＋１を反転するた め、上記２進数をビット・インバータ２４にある２４個のロケーションの２つヘ デコードする。ビット・インバータ２４は２つのエラー・ビットを反転し１、正 しいデータ・ワードがプロセッサへ送られる。

ここで、シンドローム発生器１４が、シンドローム・デコーダ１６に記憶された ３６個あシンドロームのいずれ七も一致しないシンドロームＳｕを発生したもの と仮定する。その場合、シンドローム・デコーダ１６は、デコーダ１８へ６ビノ トの不一致信号を与える。デコーダ１８は訂正不能エラー信号Ｕビをゲート制御 回路２ｏへ送る。回路２ｏは、ＵＥ倍信号受取ると、適切なプロセッサへＵＥ状 態が存在するとと（１３） を知らせる。

これまで説明した実施例は１つの例に過さない。実施例に対しては適当な変更が なてれてよい。例えば、Ｒ及びＫの異った値に関して、他のコードを発生すると 々ができる。次の表は、可能なコードのパラメータを示す。

２Ｒｊ固のチェック・ビットに対しては、コードは２に個のデータ・ヒント捷で を有することができる。ここでに＝Ｒ・（Ｒ−１）　、　（Ｒ−２）／３である 。データ・ビットの数が２によりも少ないアプリヶ−ノヨンでは、コードは常に 短くすることができる。これは正確な数のデータ・ビットを発生するため、Ｐに ある列ベクトルを必要な数たけ削除することによって斤される。例えば、６２個 のデータ・ビット及び１０４固のチェック・ビットを有するコードを構成するた めＫｌｊ、４０個の可能な列のうち８個の２進列が、元のパリティ・チェック・ マトリクスから削除逼れる。

ＦＩＧ、Ｉ ＦＩＧ、２

Claims (1)

1. 【特許請求の範囲】 Ｎ個のパッケージを含み、各パッケージから取られたＭ個のビットがメモリ・デ ータ・ワードのビットを構成するメモリに関して単一ビット・エラー訂正二重工 ろ一検出コードを使用するエラー訂正装置において（Ｍ、Ｎは共に２以上の整数 ）、Ｎ個のパッケージをカバーするように拡張されたＮビット単一エラー訂正二 重エラー検出コードに従ってメモリ・データ・ワードをコード・ワードへエンコ ードシ、パッケージにおけるＭ個の全ての単一ビット・エラー・シンドロームを 排他的ＯＲ結合して各パッケージについて独特の合成シンドロームを生じるよう にするエンコーダと、単一ビット・エラー及び単一パッケージ・エラーのロケー ションを決定し、全ての二重ビット・エラー及び二重パッケージ・エラーを検出 するため、それぞれの単一ビット・エラー・シンドロームを全ての可能な単一ビ ット・エラー・シンドローム及び全ての可能な合成シンドロームと比較する手段 を含むデコーダとを具備するパッケージ・エラー訂正装置。 （１）