JPS58177600A - メモリ・システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の背景〕 本発明はメモリ・アドレスの自動的スキューを行わしめ
ることにより、訂正不能なエラーを有するメモリ・ワー
ドを、エラー訂正符号によって訂１丁可能なエラーを有
するメモリ・ワードへ変更することに係る。

多くのエラー訂正及び検出方式は、訂正可能なエラーの
数よりも多いエラを検出可能でるることが知られている
。１ことえば、６４データ・ピントのメモリ・ワードは
、該メモリ・ワードと同じ位置に記憶され１こ８検査ビ
ツトを使用することにより、１ピント・エラーを訂正し
且つ２ビツト・エラーを検出することができる。かくて
、データ及び検査ビットを記憶する７２セルのうち任意
の１つに障害が生じたとしても、これをエラー訂正回路
によって訂正することが可能となる。このエラー訂正回
路は１メモリ・ワードに存在する２ビツト・エラーを検
出するためにも使用することができるが、一般にはかか
る２ビツト・エラーを訂正することはできない。すなわ
ち、１ピントの障害が生じた場合には、この特定の障害
ピントを識別して訂正することができるけれども、２ビ
ツトの障害が生じた場合には？′一般にその発生事実を
検出することができるだけで、これらの障害ピントを識
別して訂正することはできないのである。

前述の如く、２ビツト・エラーの訂正に関連して「一般
に」という用語が使用されたのは、１工ラー訂正符号の
成るものが特定の型の２ビツト・エラー、たとえば位置
的にに接する２ビツト・エラーを訂正することがめると
いう理由による。しかしながら、必ずしもすべての２ビ
ツト・エラーが訂正可能なパターンで生ずるわけではな
い。従って、−膜化して説明すると、エラー訂正及び検
出方式はその訂正能力よりも多い数のエラーを検出する
、と云うことができる。

訂正可能なエラーよりも多い数のエラーを検出しうると
いう、前述の如きエラー訂正符号の能力を有効に利用す
る１こめに、米国特許第５６４４９０２号に、検出可能
でるるか、訂正不能なエラーを、検出可能でしかも訂正
可能なエラーへ変更するための手段を開示している。こ
の特許では、メモリ・ユニットは複数の了レイから成り
、該了レイの各々は当該メモリ・ユニットにおける１ビ
ツト位置のすべてのビットを保持するようにされている
。これらのアレイは、所与のメ手り・ワードがアドレス
されるときその適正なビットが各アレイから選択される
ように、デコーダ回路を通してそれぞれアドレスされる
。この特許で示唆されているのに、デコーダへ供給され
るアドレスを永久的に修正し、かくてアレイを物理的に
スワップして諸ピノｉｆメモリ・ワード間でスワップす
ることにより、訂正不能なエラーを有するメモリ・ワー
ドを訂正可能なエラーを有するメモリ・ワードへ変更す
る、ということでろろ。

他の米国特許第３８１２３３６号及びＩＢＭＴｅｃｈｎ
ｉｃａｌ　　Ｄｉｓｃｔｏｓｕｒｅ　　Ｂｕｌｌｅｔｉ
ｎ。

Ｖｏｌ、１　６、屋４、Ｓｅｐｔｅｍｂｅｒ　　１９７
５、ｐａｇｅ　ｉ　２４５なる文献には、メモリ・ビッ
トのスワップを行うためのアドレス修正方式が記述さレ
テいる。この方式では、特定ビット・了レイのデコーダ
へ供給されるアドレスは、メモリ・ワードの特定ピント
位置に関連するシフト・レジスタに記憶されたデータの
１関数として、論理回路によって修正される石ちこの論
理回路は、特定ピント位置のデコーダに加わる各入力ご
とに１つの排他的ＯＲゲートを含んでいる。排他的ＯＲ
ゲートの各々はその入力としてワード・アドレスの１デ
イジント及び成るシフト・レジスタ段の出力を受取り、
そしてその出力をデコーダの１人力へ供給する。

前記文献のものでは、障害ピントのデコーダ入力アドレ
スは、この障害ピントが要求されるときこれに〕代って
ビット位負０がアクセスされるように、シフト・レジス
タに配置される。一方、前記特許のものでは、ガロア体
の敲る数が各シフト・レジスタ段にそれぞれ記憶される
。すなわち、０が第１ピント位置のシフト・レジスタに
記憶され、以下同様の操作が行われて、最後に必要とさ
れる最大数が最終ピント位置のシフト・レジスタに記憶
されるのでめる。多重ピント・エラーが検出されろ場合
、第１ビット位置のシフト・レジスタを除く各シフト・
レジスタは１ガロア数だけシフトされる。このことは障
害メモリ・ワードを構成する諸ピントを分散させること
によって、検出された多重ピント・エラーが取除かれる
ことを保証する。この分散の結果、障害ピントの各々は
異なるメモリ・ワードに終結し、かくて訂正不能な多重
ビット・エラー状態が訂正可能な多数の１ビツト・エラ
ー状態へ変更されることになる。

この方式の１つの利点は、検出された多重ビット　エラ
ー状態が１回の試行操作で除去されるという点にある。

また、この操作で以前に訂正された多重ピント・エラー
状態が再現しないという利点もめる。しかしながら、こ
の方式に訂正中のメモリ・ワード又は他のメモリ・ワー
ドに訂正不能な新しいエラー状態を生せしめることかめ
る。この生起確率は、メモリが大容量となり且つ障害ピ
ントの数が増えるにつれて、増大する傾向かめる。

従って、一層改良されたビット・スワップ方式を提供す
ることが望ましい。

前記文献は、障害ビットの位置が既知である場合にはそ
のアクセスを回避しうろことを示している。また、米国
特許第３７８１８２６号及び第６８９７６２６号には、
障害ビットの位置に関するテスト結果を使用し、該位置
に従って諸チップを複数のグループへ分割することが記
述されている。

後者の特許のものでは、同じセクションに障害領域を有
する各チップは各メモリ・カード上に同じパターンで配
置される。そして、どのメモリ・ワードも１より多い障
害ピントを含まないように、エラーをスキューさせるた
めのアドレス配線が行わ躯。もしエラー検出及び訂正手
段によって所与の障害が検出されるならば１．、障害メ
モリ・ワードのアドレスの２セクシヨンを排他的ＯＲす
ることにより、障害ピットを識別することができる。

〔発明の概要〕

本発明によれば、メモリ・ワード間のビット・スワツピ
ングは、当該メモリにおける障害ビットに関するデータ
を使用することによって行われる。

ビット・了ドレスの置換（ｐｅｒｍｕｔａｔｉｏｎ）Ｈ
排他的プロセスによって行われ、該プロセスは（メモリ
のエラー訂正回路によっては訂正不能な）ビット障害の
整列に帰着するようなアドレスの組合せを識別するとと
もに、他の組合せに対する選択プロセスを制限する。訂
正不能な障害の組合せを決定するために、種々の障害は
、チップ障害、ワード線障害、ビット線障害又はビット
障害の如き型によって類別される。然る後、ビット・ア
ドレスは、障害の数の減少順に置換される。

従って、不発明の目的に、訂正不能なエラー状態を訂正
可能なエラー状態へ変更するように、メモリ・ワード中
のピントをスリップする１こめの方式を提供することに
るる。

不発明の他の目的は、メモリ中の障害セルに関するデー
タを使用してメモリ・ワード中のビットをスリップする
ことにめる・　　、□′！ 本発明の他の目的は、エラーの′１型によって類別わ、
、、。え。、、−ケア、い’Ｉ−ｅ９．ヮー１゜中のビ
ットをスワップすること二ニる。

＼ 〔発明の詳細な説明〕　　　　　＼ ゛＼ 第７図を参照するに、７２ビツト（ｎ、＝７２）のメモ
リ・ワードを構成する各ビット位装置Ｂ１ 乃至Ｂ　　　の記憶セル１ｏは、各ビット位置に７２ 対応する各メモリ・カード１２中の複数のアレイ１４に
それぞれ配列される。アレイｉｌ：ｆ：１６ビツトのア
レイであり、各セル１ｏは４本のワード線１８と４本の
ビット線２ｏの交点にそれぞれ配置される。各アレイ１
４は対応するワード・デコーダ２２及びビット・デコー
ダ２４を通してアドレスされ、該デコーダは２ピツト・
アドレスｗｏ１Ｗ　及びＢＢ　　をそれぞれ受取る。

１　　　　　０ゝ　　　１ 各アレイ１４に関連するワード・テコ２ダ２２及びビッ
ト・デコーダ２４に加えて、各カード１２にチップ・ア
ドレス・ビットＣｏ′、Ｃ１′を受寧ろようなチップ・
デコーダ２６を含む。このチップ・デコーダ２６は、所
与のＡＮＤゲート２８を付勢するこぎよって、各カード
１２に設けられた４個のアレイ１４のうち１個の出力を
選択する。

チップ・アドレス・ビットＣ′、Ｃ′は排１ 他的ＯＲ回路５０及び３２のそれぞれの出力でろシ、該
回路はメモリ・アドレス・レジスタ３３からアドレス・
ビットｃｏ、、Ｃ１を受取るとともに、シフト・レジス
タ形式の制御レジスタ３４から他のアドレス・ビットｚ
ｏ１　Ｚｌをそれぞれ受取る。

従って、もしアトシス・ピントＺ　ｏ　１Ｚ　１がとも
に０であれは、チップ・デコーダ２６はメモリ・アドレ
ス・レジスタ６３によって要求された特定のアレイ１４
をアクセスすることになる。さもなければ、すなわち制
御レジスタ３４中のアドレス・ビットＺｏ１Ｚ１の組合
せが他のものであれば、チップ・デコーダ２６は他の５
個の了レイ１４のうち１個をアクセスする。

要約すると、メモリ・了ドレス・レジスタ３３は６丁ド
レス・ビットｃｏ、Ｃ１、ＷＯ，Ｗｌ、Ｂ　ａ　１Ｂ　
１をすべてのカード１２ａ乃至１２ｎへ共通に転送する
。各カード１２では、了ドレス・ビットＷｏ１Ｗ１、Ｂ
ｏ、Ｂ、Ｕ４個の了レイ１４にめる同じセル１０を７ク
セスする。了ドレス・ピントＣ′、Ｃ１′は各カード１
２に設けられた４個のチップのうち１個を選択し、かく
てその出力をアクセスされたメモリ・ワードのビットＢ
　　乃至Ｂ　　　の１つとして読出す。もし了ｐ１　　
　　ｐ７２ ドレス・ビットｚｏ１　ｚｌがともに０であれば、各カ
ード１２の同じ了レイ１４にめる同じビット位置がアク
セスされる。一方、もし任意のカード１２ｉに設けられ
た制御レジスタ３４の内容２゜、ｚｌがともに０でなけ
れば、このカー＋”１２ｉのビット出力Ｂ　、は他の了
レイ１４の同じピント１ 位置から供給される。

本発明に従って、制御レジスタ３４の内容はチップの障
害に関する記憶データに基いて選択される・図示された
実施態様では、これらの障害は型によって類別される。

すなわち、この記憶データは当該チップに存在する障害
の型を指定する。第２図を参照すれば、このことが一層
良（理、解できる。第２図に第１図に示したものと同じ
４個のカードＡ。乃至Ａ３を示しているが、ここでは互
いに異がる４種類の障害が生じうるものと想定されてい
る。即ち、カードＡＯではチップ１０上のすべてのビッ
トが障害を有する。これをチップ障害（又はチップ・キ
ル）と呼ぶ。チップ障害を識別するには、当該チップの
了ドレスに続いて４個のＸを与えることが必要でめる（
例：　１０、ＸＸＸＸ）。

また、カードＡｏのチップ１１でに、ワード線１０土の
すべてのビットが障害を有する。これをワード線障害と
呼ぶ。ワード馨障害を識別するには、当該チップの了ド
レス及び当該ワード線のアドレスに続いて２個のＸを与
えることが必要でるる（例：１１．１０、ｘＸ）。第３
の型の障害は、所うのビット線に沿って配列されたすべ
てのビットが応答しないようなものでるる。これをビッ
ト線障害と呼ぶ。カードＡ２では、チップ１０上のピン
ト線１０がこのような障害を有する。ビット線障害を識
別するには、当該チップの了ドレスと当該ビット線の了
ドレスとの間に２個のＸを一入することが必要でめる（
例；１０、ＸＸ、１０）。

最後の型の障害は、カードＡ３のチップ１１に見られる
ような、ビット障害でるる。このビット障害を識別する
には、当該ビットのチップ・アドレス、ワード・アドレ
ス及びピント線アドレスを与えることが必要でるる（例
：１１．００．１０）。

第２図には、前記した型の種々の障害が示されている。

これらの障害ビットを識別するための障害マツプは次の
ようになる。

ｌ　Ａｏｊ）＝１０、ＸＸ、　ＸＸ：　１１．１０、ｘ
ｘＡ、＝１１．００、ＸＸ Ｊ ｐ、　　、　　＝ＯＤ、１１、ｘｘ：１ｏ、ＸＸ、１０
Ｊ Ａ、＝１１．００．１０ ６コ 但し、（Ａ、、）＝カードＡ、に設けられたアレイＩ　
　Ｊ　　　　　　　　　　　　　　、１における既知の
障害ビットのア ドレス ＸＸ＝リストされた了ドレスにおける 障害状態 第２図から理解しうるように、この単純化されたメモリ
の諸ワードは、すべてのカードのすべての制御レジスタ
６４において２　及びＺ２がともにＤヘセントされてい
るとき、多重ピント・エラー状態を有することになろう
。たとえば、メモリ・ワード１１００１０は、カードＡ
　におけるワ−ド線障害及びカードＡ３におけるビット
線障害の結果として、多重ビット・エラー状態を有する
。

捷たメモリ・ワード１０００’１０．１００１１０．１
０１０１０及びＩ　Ｄ　１１１０Ｈ、カードＡｏにオケ
るチップ障害及びカードＡ２におけるピット線障害の結
果として、多重ビット・エラー状態を治する。

米国特許第３８１２３３６号で記述されているように、
これらの多重ピント・エラー状態ハ、１つ以との制御レ
ジスタろ４中のデータを変更することによって取除くこ
とができる。たとえば、メモリ・ワード１１００１０に
おける２ピント・エラー状態は、カードＡ５における完
全なチップのビットを使用すること（よって顧除くこと
ができる。このことを可能にするに社、制御レジスタ３
４ｄの内容゛を００から０１．３０又は１１へ変更すれ
ばよい。しかしながら、制御レジスタ５４ｄの内容を選
択する場合、他のワード線に多重ピント・エラー状態を
導入しないように注意しなければならない。このため、
不発、明では所与のアルゴリズムに従ってコード化され
たプロセッサ手段を使用し、前述の如き障害マツプ中の
データを調べることによシ、制御レジスタ′５４の内容
の種々の組合せについて生ずる各種の衝突を識別するよ
うにしている。

ここで、ＣＲＣＲ４・・・・・・、ＣＲｎ−１を０ゝ ｎ個の制御レジスタ６４の内容であると仮定し、ＣＲ，
の各々がｒビット長でるると仮定する。また、（Ａｉ　
ｊ）がカードＡ、に存在する１組の障害ビットのアドレ
ス（障害、アドレスの集合）でめると仮定する。障害ア
ドレスの集合（Ａ、、）がＩＪ 与えられると、制御レジスタの内容ＣＲ，は、複！ 数組の計りＦ結果ｃＲｅ（Ａ　、）、ＣＲ２＄（１１コ Ａ　　）、・・・・・・、ＣＲ■（Ａ　、）が互いに２
Ｊ　　　　　　　　　　　　　　ｎ　　　　　　ｎｊ素
となるように選ばれなければならない。これは、以下の
アルゴリズムに従って制御レジスタの内容ＣＲを計算す
ることにより、完全にすることができろ。云いかえれば
、制御レジスタの内容ＣＲ。

はいかなるエラーも同じワードに置かれないようなもの
でなければならない。これに次のようにして行うことが
できる。

ステップ １、ＣＲｏ＝００　をセント ２、　八　二零　をセント ３：ｉ＝０　　　をセット ４　：　　Ａ　　＝ＡＵ（Ａ、−）＄ｃＲ，を計ＮＩＪ
　　　　　　　　　　１ ５：　　ｉ　　＝ｉ＋１　　をセット ６：　　Ｂ、＝Ａ■（Ａ、、）　　を計算１　　　　　
　　　　　　１Ｊ ７　：ＣＲ，＝Ｂ、（Ｂ、にはない任意の要素′）、１
　　　　　　１　　　　　　１ をセット ８：もしＹ７が空（零集合）でめれば、終了する。

９：もしｉ　”　ｎ　−１であれば、出口に行く。さも
なければ、ステップ４に行き、上記ステップを継続する
。

但し、ＩＡ、、）＝カードＡ、（ｉ＝［１，１、・・Ｉ
Ｊ　　　　　、　　　　　　　　　　　１・・、ｎ−１
）上の障害アドレ スの集合 ｌ　＝任意のカード０、・・・・、ｎ−ＩＡ　＝当該ア
ルゴリズムによって決 定され且つ使用される累積さ れた置換障害アドレスの集合 Ｕ　＝集合論で使用される直利を表 わす記号 このアルゴリズムはＡＰＬで実現することができ、これ
を流れ図の形式で示せば第４図のとおりである。但し、
この場合において、Ａはアルゴリズム中の当該害行点ま
で置換されたすべての障害の論理アドレス・リストであ
シ、■は以下の真理値表によって定義された排他的ＯＲ
演算である。

但し、０．１、Ｘは以下の真理値衣によって定義されろ
。

これらの真理値衣は、第３図に示した排他的ＯＲ回路の
動作を定義する。この排他的ＯＲ回路はハードウニ了形
式の実現形態で使用され、前述のアルゴリズムにおける
ステップ４及び６を計算するために使用することができ
る。

ここで、第４図のアルゴリズムに第２図の障害子ドレス
をそれぞれ代入することにより、制御レジスタの内容Ｃ
Ｒ０をそれぞれ次のようにして求めることかできる。

ロ　　　　　　Ｈ′へ −Ｈへ の　　　　　　　　　　　　　　　　　ト０　　　　　
　　　　　　　　　″　　　　　　−ｆ−Ｆ　　　　　
　Ｏ ’；ｘ！、　　　　　　（）　　　　　　　　　Ｃ）　
　　　　　”Ｉ−一一 −ｖ−−−〇　　”へ ｐ　　　　　ｒｖ−Ｃ）　　伽 、−、ｒ−ｙ　　　　　　　Ｃ１− ＸＸ　　　　　　　　ＸＸ　　　の Ｎ’＋ｌ／ｌ　　　　　　　唖　Ｏ ＜＜＜　　　・−ＣＱｃｔ５　　　　　　　　峙　　　
−ぐ　　　　　　　　　　　　　　　の　　史　　　　
　　　　　　　　　　　トこのようにして求めたＣＲＪ
を該当する制御しジスタ３４に挿入すると、第２図に示
し１０種々の障害は第５図に示すように適正に再配列さ
れることになる。すなわち、第２図のカードＡ２におけ
ろチップ・了ドレス００及び１０は実効的に他のチップ
・了ドレス１１及び０１にそれぞれ変換され、そして第
２図のカードＡ６におけろチップ・了トレス１１は実効
的に他のチップ・了ドレス００に変換されるのである。

このアルゴリズムは他のソフトウェアで実現することも
できる。以下にはその１つの例が示されている。但し、
以下の例では、障害の表示は、殆んどのプログラミング
言語に適合するように、２進表示ではなく、１０進表示
でなされている。

第６図の４ピント・了レイは、アドレス・ピントが１０
進表示で表わされている点を除くと、第２図の了レイと
同様の構成を有する。第６図で黒く示した領域は、当該
メモリの障害ビットを表わす。第６図から以下の障害マ
ンブを生成することができろ。

カード　　チップ　　ワード線　　ビット線０　　　２
　　　　０　　　　０ １　　　０　　　　４　　　　５ １　　　１　　　　３　　　　０ ２　　　１　　　　０　　　　５ ３　　　　　２　　　　　　１　　　　　　　４第６図
から容易に理解しうるように、当初はメモリ・ワード（
１，３，３）及ｂ（２，１，４）に訂正不能なエラーが
存在する。まず、１０進表示がどのように作用するかを
理解するために、カード２へＣＲ値２が加わり、４カー
ド３へＣＲ値１が加わるものとする。そうすると、カー
ド２における障害チップの論理下ドレスは１から３へ変
わる。これは、その物理アドレス１と加えられりＣＲ値
２との排他的ＯＲ演算結果でろる。同様に、カード３に
おける障害チップの論理下ドレスは２から３＝２＋１に
変わる。かくて、当該メモリは実効的に第７図に示すよ
うに再構成され、従って訂正不能なエラーはもはや存在
しないことがわかる。前述のように、ｃＲ値を適切に選
択することにより、第６図の実施態様における訂正不能
なエラーを分散させうろことを説明したので、以下でＩ
ｎ　Ａ　Ｐ　Ｌで記述するに適したＣＲ選択了ルゴリズ
ムを説明する。

一層詳細には、このアルゴリズムは次のように進行する
。

（１）　　Ａ（７をカード０における障害のリストでろ
るとする。かくて、このアルゴリズムの任意の実行点に
おけるＡは、この点に至るまで障害チップの論理下ドレ
スで置換された障害のリストとなる。カード０は置換し
ないので、ＣＲ＝Ｏとなる。

（２）Ｎ＝０　　をセントする。

（３）Ｎを１だけ増分する。

（４）■二〇　をセットする。

（５）■を１だけ増分する。

（６）　　カードＮにおける障害をＡＮで表わし、ＡＮ
における第Ｉ番目の障害をＡＮＩで表わすものとする。

またＡにおける全障害の論理チップ・アドレスを含む集
合でるって、ＡＮＩが所与の障害と同じ論理チップ・了
ドレスを占有するようにカードＮが置換された場合には
ＡＮＩがこの障害とともに訂正不能エラーを生ぜしめる
ような特性を有する集合を、ＣＡＮＨＩＴで表わすもの
とする。かくて、ＣＡＮＨＩＴの１つの要素を、ＡＮＩ
にその論理チップ・了ドレスとして与えるようなＣ’Ｒ
値を取除くことが要請される。これらのＣＲ値は次のよ
うに表わされる。

（ＡＮＩの物理チップ・了ドレス）（［）ＣＲ＃ＣＡＮ
ＨＩＴ。

又は ＣＲ４Ｉ′（ＡＮＩの物理チップ・了ドレス）■ＣＡＮ
ＨＩＴかくて、ＣＡＮＨＩＴ中の値とＡＮＩの物理チッ
プ・アドレスとの排他的ＯＲ演算を行ない、そしてその
結果値を考察中のＣＲ値の集合から取除く。

（７）　　もし工がＡＮ中の障害の数よシ小さければ、
ステップ５に進む。

値が存在するならば、その１つの値（た、とえは最初の
値）を第Ｎ番目のカードに対するＣＲ値として選択する
。さもなければ、終了する（この場合、当該メモリにお
ける訂正不能なすべてのエラーを分散させることに失敗
したことになる〕。

（９）　　もしＮが当該メモリにおける最終カードの番
号よりも小さければ、ステップ５に進む。さもなければ
、当該メモリにおける訂正不能なすべてのエラーを成功
裡に分散させたことになる。

以下のＡＰＬプログラムは不明細書の補足資料として提
供される。

第６図のメモリに作用する場合のこのアルゴリズムを以
下カードごとに説明する。

カード０：カード０を置換する必要にないから、ＣＲ＝
０となる。かくてＡは１×４の マトリクス（０，２，０，０）でめる。

カード１　：Ａ１１１’Ｘ次に示すとおり２×４のマト
リクスでめる。

１０４’３ １　　１　　３　０ 従って、Ａ１１は（１，０ミ４．３）でろシ、ＣＡＮＨ
，ＩＴ＝’２でめる。というのは、チップ障害（９・　
２・　０．０）とＡ１１とが同一の論理チップ・アドレ
スへ置かれたならば、訂正不能エラーを生ぜしめるから
でるる。かくて、 ＣＲ（（Ａ　１１の物理チップ・了ドレス）■ＣＡＮＨ
ＩＴ。

又は ＣＲ＠（ｐｌ＄＋２：、　又ｎ ＣＲ＝２ を満足するようなＣＲが取除かれる。ここで、ＣＲにつ
いての選択の余地は０．１及び３でめる。

Ａ１２＝（１，１，６、０）でめシ、そしてＣＡＮＨＩ
　Ｔは依然として２であるから、ＣＲ値３＝１ｅ２を取
除くことが望ましい。今やＣＲについての選択の余地は
０及び１でめる。ＣＲ＝Ｏが選択され、かくてカード１
は全く置換されないことになる。この場合、Ａは次のと
おシでるる。

０　２　０　０ Ａ＝１　　０　　４　　５ １　１　５　０ カード２：Ａ２＝（２，１，０，３）でめり、ＣＡＮＨ
’ＩＴ＝０．１．２でろる。次の条件を満足するＣＲが
取除かれる。

Ｃ１Ｒｔ２　ｉ−Φ１’０’；　１．２　）ＭＥ４．’
０．５　）今や残っている唯一のＣＲ値はＣＲ＝２でろ
る。

これを適用すると、Ａ２における障害の論理アドレスは
（２，３，０，３）となり、従ってＡは次のとおりとな
る。

０２００ Ａ二１０４３ １１３０ ２３０６ −カー）”５：Ａ３＝（５，２，１，４）でろり、ＣＡ
ＮＨＩ　Ｔ＝２でめる。ｅ’Ｒ＝Ｏ＝２■２が取除かれ
る。ＣＲについての選択の 余地に１．２．６でめる。ＣＲ＝１が 選択され、従ってＡ６における障害の 論理アドレスは（３，３，１，４）と なる。最後的に、Ａが次のように得ら れる。

０２００ １０４５ Ａ＝１　１　５　０ ２３０３ ３３１４ 基本的アルゴリズムについてなされた、簡単ではめるが
強力な増強策は、メモリの諸カードを考察する当該アル
ゴリズムの順序に関係する。前述のように、このアルゴ
リズムにこのメモリを”左１ から右へ″順次に進行する。すなわち、諸カードがその
順序０．１．２、・・・・・・どおシに考察されるので
るる。このアルゴリズムを大幅に改善するには、すべて
の状況について同一の任意的順序付けを使用するのでは
なく、考察中の特定の障害１ノブを考慮したカード順゛
序付けを使用することができる。

一般に、このアルゴリズムはエラーの数に従つ１、二カ
ードの順序付けを含む。このアルゴリズムを実行中の特
定の点で、ＣＲ値を探そうとしているカードが°°悪く
″なるにつれて、すなわちこのカードの“障害度”が犬
きくなるにつれて、そのＣ１化値に対する選択の余地は
一層小さくなる。さら（（−１他のすべての条件が同等
でるる場合、このアルゴリズムで既に考慮された障害が
増大するにつオー１．て、集合”　Ａ″における障害に
よって既に占有で才１ているメモリ中の論理アドレスが
増大するので、、ＣＲ値に対する選択の余地が一層小さ
くなる。

かくて、もしこのアルゴリズムが°′最悪′″のカー１
−’　＝ｆ最後に考慮するならば、その成功の見込みは
殆んどなく、従って該カードについて適切なＣＲを・見
出すことはできないでろろう。そうすると、これらのカ
ードを°゛最悪″の側から゛最良″の側−＼順番に取る
ことが理に適っている。

このような順序付けを正確ＫＩｊ定するには、”最悪″
という意味を正確に決定することが必要でるる。これら
のカードを順序付ける土で成功を収めた簡単な方法は、
“最悪”のカードを゛最大”の障害セルを含むカードと
定義することでるる。

かくて、当該アルゴリズムでこの方式を使用すると、最
も障害の多いセルから順番に複数のセルが取られる。図
示されたメモリでは、各ピット線又は各ワード線の障害
は４障害セルとしてカウントされ、各チップ障害は１６
障害セルとしてカウントされる。

たとえば、前述の順序付は方式を第６図のメモリで使用
すると、当該アルゴリズムは複数のカードを０，１．２
．３の順番に取るので、当該アルゴリズムは成功するこ
とになる。

もちろん、他の順序方式も可能でろる。たとえば、゛′
最悪″″のカードを、障害のない完全なチップの数が最
も少ないカードとして定義することができる。

アドレス置換を実現する際に可能な変形は、ワード線及
び／又はビット線アドレスをチップ・アドレスとともに
置換することでろる。

他の変形に第４図のステップ８を修正することＶこより
、Ｂ　が空である場合には、当該アルゴリズムが以前の
ＣＲ値の選択に戻り、そして１より多い選択が可能でめ
った場合とに異なる選択を行うよう（ですることでろる
。

第８図を参照するに、第１図に示したものと同様のメモ
リ４０に通常のエラー訂正（ＦＣＣ）論理４２（でよっ
て検査される。ＥＣＣ論理４２からｉＪ　＋Ｅ不能エラ
ー信号が生ずると、メモリ・テスタ・１４によってメモ
リ・アレイのテストが行われる。

デスタ４４は、訂正不能エラーを有するメモ〃位置へテ
スト・パターンを印加するための装置でめろ。１ことえ
ば、テスタ４４（グオール１のパターン（・こ続いてオ
ールＯのパターンをこのようなメモリｆ、′ＬＷへ印加
することにより、０又は１に縮退されｆｌビットを決定
することができろ。障害ピントが識別された場合、これ
らのアドレスは障害マツプ４６中のメモリに（本明細書
で説明した様式又は目的に応じて他の様式に従って）記
憶される。

また訂正不能エラー状態は、制御レジスタ３４中のデー
タを変更して訂正不能エラー状態を取除くために、置換
発生論理４８の動作を開始させる。

本発明に従った置換発生論理４８は前述のアルゴリズム
を実行可能なマイクロコード化プロセッサでるる。

置換発生論理４Ｂの出力にメモリ４０の徨々のビット位
置に対するＣＲ値でめるから、これらのＣＲ値は制御レ
ジスタ３４へ供給される。制御レジスタ３４はＬＳＳＤ
式シフト・レジスタで構成することが可能であり、こう
するとＬＳＳＤＳＳ−ンに沿って適正な制御レジスタ段
へデータをシフトすることができる。

本発明の実施態様は前述のとおシでるるか、他の実施態
様も可能でるる。たとえば、前掲の米国特許第３８１２
３３６号に記述されているように、各ピントの位置を単
一のアレイに設けることも可能でるる。ま１こ、ワード
線及びピット線を置換することも可能である。

【図面の簡単な説明】

第１図は本発明が適用されるメモリの概略図、第２図は
第１図のメモリにおける１組の障害を示す図、第６図は
第１図のメモリで使用するに適した排他的ＯＲ回路を示
す図、第４図は訂正不能エラーを再配列するための本発
明のアルゴリズムを示す流れ図、第５図はメモリ・アド
レスを第４図のアルゴリズムに従って再配列した後の第
２図の１組の障害を示す図、第６図は第１図のメモリに
おける他の障害を示す図、第７図はメモリ・アドレスを
第４図のアルゴリズムに従って再記２列した後の第６図
の障害を示す図、第８図は不発明の実施態様を包含する
メモリ・システムを示すブロック図でるる。 出願人　　インタブカショカル・ビジネス・マシーノズ
・コーポレーション代理人　弁理士　　頓　　　宮　　
　孝　　　−（外１名〕

Claims (1)

1. 【特許請求の範囲】 各メモリ・ワードを樽成するビット位置の各々カ同一の
   論理アドレス・ビットでアクセスされるように編成され
   たメモリに付随して、障害ビットを複数のメモリ・ワー
   ド間に分配するように選択、　　された置換ビットに基
   き、所与のビット位置に対する論理アドレス・ビットを
   それとは異なる物理アドレス・ピントに変換するための
   置換手段を設けることにより、前記メモリの内容を保護
   するエラー訂正手段によって訂正することができないメ
   モリ・ワード中のエラー状態を除去するようにしたメモ
   リ・システムにおいて： 前記メモリにおける既知の障害をその物理アドレス及び
   障害の型の組合せで記憶するための記憶手段と； 前記メモリの所与のビット位置に対する前記置換ビット
   を、他のビット位置における障害の既知の論理アドレス
   及び該所与のビット位置における障害の物理アドレスに
   基いて選択するため、の選択手段とを備えて成る、メモ
   リ・システム。