JPH0136134B2 - - Google Patents

Description

【発明の詳細な説明】

〔発明の背景〕 本発明はメモリ・アドレスの自動的スキユーを
行わしめることにより、訂正不能なエラーを有す
るメモリ・ワードを、エラー訂正符号によつて訂
正可能なエラーを有するメモリ・ワードへ変更す
ることに係る。 多くのエラー訂正及び検出方式は、訂正可能な
エラーの数よりも多いエラを検出可能であること
が知られている。たとえば、64データ・ビツトの
メモリ・ワードは、該メモリ・ワードと同じ位置
に記憶された８検査ビツトを使用することによ
り、１ビツト・エラーを訂正し且つ２ビツト・エ
ラーを検出することができる。かくて、データ及
び検査ビツトを記憶する72セルのうち任意の１つ
に障害が生じたとしても、これをエラー訂正回路
によつて訂正することが可能となる。このエラー
訂正回路は１メモリ・ワードに存在する２ビツ
ト・エラーを検出するためにも使用することがで
きるが、一般にはかかる２ビツト・エラーを訂正
することはできない。すなわち、１ビツトの障害
が生じた場合には、この特定の障害ビツトを識別
して訂正することができるけれども、２ビツトの
障害が生じた場合には、一般にその発生事実を検
出することができるだけで、これらの障害ビツト
を識別して訂正することはできないのである。 前述の如く、２ビツト・エラーの訂正に関連し
て「一般に」という用語が使用されたのは、１エ
ラー訂正符号の或るものが特定の型の２ビツト・
エラー、たとえば位置的に隣接する２ビツト・エ
ラーを訂正することがあるという理由による。し
かしながら、必ずしもすべての２ビツト・エラー
が訂正可能なパターンで生ずるわけではない。従
つて、一般化して説明すると、エラー訂正及び検
出方式はその訂正能力よりも多い数のエラーを検
出する、と云うことができる。 訂正可能なエラーよりも多い数のエラーを検出
しうるという、前述の如きエラー訂正符号の能力
を有効に利用するために、米国特許第3644902号
は、検出可能であるが、訂正不能なエラーを、検
出可能でしかも訂正可能なエラーへ変更するため
の手段を開示している。この特許では、メモリ・
ユニツトは複数のアレイから成り、該アレイの
各々は当該メモリ・ユニツトにおける１ビツト位
置のすべてを保持するようにされている。これら
のアレイは、所与のメモリ・ワードがアドレスさ
れるときその適正なビツトが各アレイから選択さ
れるように、デコーダ回路を通してそれぞれアド
レスされる。この特許で示唆されているのは、デ
コーダへ供給されるアドレスを永久的に修正し、
かくしてアレイを物理的にスワツプして諸ビツト
をメモリ・ワード間でスワツプすることにより、
訂正不能なエラーを有するメモリ・ワードを訂正
可能なエラーを有するメモリ・ワードへ変更す
る、ということである。 他の米国特許第3812336号及びIBM Technical
Disclosure Bulletin、Vol.16、No.４、
September1973、page1245なる文献には、メモ
リ・ビツトのスワツプを行うためのアドレス修正
方式が記述されている。この方式では、特定ビツ
ト・アレイのデコーダへ供給されるアドレスは、
メモリ・ワードの特定ビツト位置に関連するシフ
ト・レジスタに記憶されたデータの関数として、
論理回路によつて修正される。この論理回路は、
特定ビツト位置のデコーダに加わる各入力ごとに
１つの排他的ORゲートを含んでいる。排他的
ORゲートの各々はその入力としてワード・アド
レスの１デイジツト及び或るシフト・レジスタ段
の出力を受取り、そしてその出力をデコーダの１
入力へ供給する。前記文献のものでは、障害ビツ
トのデコーダ入力アドレスは、この障害ビツトが
要求されるときこれに代つてビツト位置０がアク
セスされるように、シフト・レジスタに配置され
る。一方、前記特許のものでは、ガロア体の異な
る数が各シフト・レジスタ段にそれぞれ記憶され
る。すなわち、０が第１ビツト位置のシフト・レ
ジスタに記憶され、以下同様の操作が行われて、
最後に必要とされる最大数が最終ビツト位置のシ
フト・レジスタに記憶されるのである。多重ビツ
ト・エラーが検出される場合、第１ビツト位置の
シフト・レジスタを除く各シフト・レジスタは１
ガロア数だけシフトされる。このことは障害メモ
リ・ワードを構成する諸ビツトを分散させること
によつて、検出された多重ビツト・エラーが取除
かれることを保証する。この分散の結果、障害ビ
ツトの各々は異なるメモリ・ワードに終結し、か
くして訂正不能な多重ビツト・エラー状態が訂正
可能な多数の１ビツト・エラー状態へ変更される
ことになる。 この方式の１つの利点は、検出された多重ビツ
ト・エラー状態が１回目の試行操作で除去される
という点にある。また、この操作で以前に訂正さ
れた多重ビツト・エラー状態が再現しないという
利点もある。しかしながら、この方式は訂正中の
メモリ・ワード又は他のメモリ・ワードに訂正不
能な新しいエラー状態を生ぜしめることがある。
この生起確率は、メモリが大容量となり且つ障害
ビツトの数が増えるにつれて、増大する傾向があ
る。従つて、一層改良されたビツト・スワツプ方
式を提供することが望ましい。 前記文献は、障害ビツトの位置が既知である場
合にはそのアクセスを回避しうることを示してい
る。また、米国特許第3781826号及び第3897626号
には、障害ビツトの位置に関するテスト結果を使
用し、該位置に従つて諸チツプを複数のグループ
へ分割することが記述されている。後者の特許の
ものでは、同じセクシヨンに障害領域を有する各
チツプは各メモリ・カード上に同じパターンで配
置される。そして、どのメモリ・ワードも１より
多い障害ビツトを含まないように、エラーをスキ
ユーさせるためのアドレス配線が行われる。もし
エラー検出及び訂正手段によつて所与の障害が検
出されるならば、障害メモリ・ワードのアドレス
の２セクシヨンを排他的ORすることにより、障
害ビツトを識別することができる。 〔発明の概要〕 本発明によれば、メモリ・ワード間のビツト・
スワツピングは、当該メモリにおける障害ビツト
に関するデータを使用することによつて行われ
る。ビツト・アドレスの置換（permutation）は
排他的プロセスによつて行われ、該プロセスは
（メモリのエラー訂正回路によつては訂正不能な）
ビツト障害の整列に帰着するようなアドレスの組
合せを識別するとともに、他の組合せに対する選
択プロセスを制限する。訂正不能な障害の組合せ
を決定するために、種々の障害は、チツプ障害、
ワード線障害、ビツト線障害又はビツト障害如き
型によつて類別される。然る後、ビツト・アドレ
スは、障害の数の減少順に置換される。 従つて、本発明の目的は、訂正不能なエラー状
態を訂正可能なエラー状態へ変更するように、メ
モリ・ワード中のビツトをスワツプするための方
式を提供することにある。 本発明の他の目的は、メモリ中の障害セルに関
するデータを使用してメモリ・ワード中のビツト
をスワツプすることにある。 本発明の他の目的は、エラーの型によつて類別
された既知のエラー状態に基いてメモリ・ワード
中のビツトをスワツプすることにある。 〔発明の詳細な説明〕 第１図を参照するに、72ビツト（ｎ＝72）のメ
モリ・ワードを構成する各ビツト位置B_p1乃至
B_p72の記憶セル１０は、各ビツト位置に対応する
各メモリ・カード１２中の複数のアレイ１４にそ
れぞれ配列される。アレイ１４は16ビツトのアレ
イであり、各セル１０は４本のワード線１８と４
本のビツト線２０の交点にそれぞれ配置される。
各アレイ１４は対応するワード・デコーダ２２及
びビツト・デコーダ２４を通してアドレスされ、
該デコーダは２ビツト・アドレスW₀，W₁及び
B₀，B₁をそれぞれ受取る。 各アレイ１４に関連するワード・デコーダ２２
及びビツト・デコーダ２４に加えて、各カード１
２はチツプ・アドレス・ビツトC₀′，C₁′を受取る
ようなチツプ・デコーダ２６を含む。このチツ
プ・デコーダ２６は、所与のANDゲート２８を
付勢することによつて、各カード１２に設けられ
た４個のアレイ１４のうち１個の出力を選択す
る。 チツプ・アドレス・ビツトC₀′，C₁′は排他的
OR回路３０及び３２のそれぞれの出力であり、
該回路はメモリ・アドレス・レジスタ３３からア
ドレス・ビツトC₀，C₁を受取るとともに、シフ
ト・レジスタ形式の制御レジスタ３４から他のア
ドレス・ビツトZ₀，Z₁をそれぞれ受取る。従つ
て、もしアドレス・ビツトZ₀，Z₁がともに０であ
れば、チツプ・デコーダ２６はメモリ・アドレ
ス・レジスタ３３によつて要求された特定のアレ
イ１４をアクセスすることになる。さもなけれ
ば、すなわち制御レジスタ３４中のアドレス・ビ
ツトZ₀，Z₁の組合せが他のものであれば、チツ
プ・デコーダ２６は他の３個のアレイ１４のうち
１個をアクセスする。 要約すると、メモリ・アドレス・レジスタ３３
は６アドレス・ビツトC₀，C₁，W₀，W₁，B₀，
B₁をすべてのカード１２ａ乃至１２ｎへ共通に
転送する。各カード１２では、アドレス・ビツト
W₀，W₁，B₀，B₁は４個のアレイ１４にある同
じセル１０をアクセスする。アドレス・ビツト
C₀′，C₁′は各カード１２に設けられた４個のチツ
プのうち１個を選択し、かくてその出力をアクセ
スされたメモリ・ワードのビツトB_p1乃至B_p72の
１つとして読出す。もしアドレス・ビツトZ₀，Z₁
がともに０であれば、各カード１２の同じアレイ
１４にある同じビツト位置がアクセスされる。一
方、もし任意のカード１２ｉに設けられた制御レ
ジスタ３４の内容Z₀，Z₁がともに０であれば、こ
のカード１２ｉのビツト出力B_piは他のアレイ１
４の同じビツト位置から供給される。 本発明に従つて、制御レジスタ３４の内容はチ
ツプの障害に関する記憶データに基いて選択され
る。図示された実施態様では、これらの障害は型
によつて類別される。すなわち、この記憶データ
は当該チツプに存在する障害の型を指定する。第
２図を参照すれば、このことが一層良く理解でき
る。第２図は第１図に示したものと同じ４個のカ
ードA₀乃至A₃を示しているが、ここでは互いに
異なる４種類の障害が生じうるものと想定されて
いる。即ち、カードA₀ではチツプ１０上のすべ
てのビツトが障害を有する。これをチツプ障害
（又はチツプ・キル）と呼ぶ。チツプ障害を識別
するには、当該チツプのアドレスに続いて４個の
Ｘを与えることが必要である（例：10、
XXXX）。また、カードA₀のチツプ１１では、ワ
ード線１０上のすべてのビツトが障害を有する。
これをワード線障害と呼ぶ。ワード線障害を識別
するには、当該チツプのアドレス及び当該ワード
線のアドレスに続いて２個のＸを与えることが必
要である（例：11、10、XX）。第３の型の障害
は、所与のビツト線に沿つて配列されたすべての
ビツトが応答しないようなものである。これをビ
ツト線障害と呼ぶ。カードA₂では、チツプ１０
上のビツト線１０がこのような障害を有する。ビ
ツト線障害を識別するには、当該チツプのアドレ
スと当該ビツト線のアドレスとの間に２個のＸを
挿入することが必要である（例：10、XX、10）。
最後の型の障害は、カードA₃のチツプ１１に見
られるような、ビツト障害である。このビツト障
害を識別するには、当該ビツトのチツプ・アドレ
ス、ワード・アドレス及びビツト線アドレス・を
与えることが必要である（例：11、00、10）。 第２図には、前記した型の種々の障害が示され
ている。これらの障害ビツトを識別するための障
害マツプは次のようになる。 ｛A_0j｝＝10、XX、XX；11、10、XX A_1j ＝11、00、XX A_2j ＝00、11、XX；10、XX、10 A_3j ＝11、00、10 但し、｛A_ij｝＝カードA_iに設けられたアレイに
おける既知の障害ビツトのアドレス XX＝リストされたアドレスにおける障
害状態 第２図から理解しうるように、この単純化され
たメモリの諸ワードは、すべてのカードのすべて
の制御レジスタ３４においてZ₁及びZ₂がともに０
へセツトされているとき、多重ビツト・エラー状
態を有することになろう。たとえば、メモリ・ワ
ード110010は、カードA₁におけるワード線障害
及びカードA₃におけるビツト線障害の結果とし
て、多重ビツト・エラー状態を有する。またメモ
リ・ワード100010、100110、101010及び101110
は、カードA₀におけるチツプ障害及びカードA₂
におけるビツト障害の結果として、多重ビツト・
エラー状態を有する。 米国特許第3812336号で記述されているように、
これらの多重ビツト・エラー状態は、１つ以上の
制御レジスタ３４中のデータを変更することによ
つて取除くことができる。たとえば、メモリ・ワ
ード110010における２ビツト・エラー状態は、カ
ードA₃における完全なチツプのビツトを使用す
ることによつて取除くことができる。このことを
可能にするには、制御レジスタ３４ｄの内容を00
から01、10又は11へ変更すればよい。しかしなが
ら、制御レジスタ３４ｄの内容を選択する場合、
他のワード線に多重ビツト・エラー状態を導入し
ないように注意しなければならない。このため、
本発明では所与のアルゴリズムに従つてコード化
されたプロセツサ手段を使用し、前述の如き障害
マツプ中のデータを調べることにより、制御レジ
スタ３４の内容の種々の組合せについて生ずる各
種の衝突を識別するようにしている。 ここで、CR₀、CR₁……、CR_o-1をｎ個の制御
レジスタ３４の内容であると仮定し、CR_iの各々
がｒビツト長であると仮定する。また、｛A_ij｝が
カードA_iに存在する１組の障害ビツトのアドレス
（障害アドレスの集合）であると仮定する。障害
アドレスの集合｛A_ij｝が与えられると、制御レ
ジスタの内容CR_iは、複数組の計算結果CR₁
｛A_1j｝、CR₂｛A_2j｝、……、CR_o｛A_oj｝が互
いに素となるように選ばれなければならない。こ
れは、以下のアルゴリズムに従つて制御レジスタ
の内容CR_iを計算することにより、完全にするこ
とができる。云いかえれば、制御レジスタの内容
CR_iはいかなるエラーも同じワードに置かれない
ようなものでなければならない。これは次のよう
にして行うことができる。 ステツプ １：CR₀＝00をセツト ２：Ａ＝零をセツト ３：ｉ＝０をセツト ４：Ａ＝AU｛A_ij｝CR_iを計算 ５：ｉ＝ｉ＋１をセツト ６：B_i＝Ａ｛A_ij｝を計算 ７：CR_i＝_i（B_iにはない任意の要素）をセツ
ト ８：もし_iが空（零集合）であれば、終了す
る。 ９：もしｉ＝ｎ−１であれば、出口に行く。さ
もなければ、ステツプ４まで行き、上記ス
テツプを継続する。 但し、｛A_ij｝＝カードA_i（ｉ＝０、１、…、ｎ−
１）上の障害アドレスの集合 ｉ＝任意のカード０、…、ｎ−１ Ａ＝当該アルゴリズムによつて決定され
且つ使用される累積された置換障害アド
レスの集合 Ｕ＝集合論で使用される直和を表わす記
号 このアルゴリズムはAPLで実現することがで
き、これを流れ図の形式で示せば第４図のとおり
である。但し、この場合において、Ａはアルゴリ
ズム中の当該実行点まで置換されたすべての障害
の論理アドレス・リストであり、は以下の真理
値表によつて定義された排他的OR演算である。

【表】 但し、０、１、Ｘは以下の真理値表によつて定
義される。

【表】 これらの真理値表は、第３図に示した排他的
OR回路の動作を定義する。この排他的OR回路
はハードウエア形式の実現形態で使用され、前述
のアルゴリズムにおけるステツプ４及び６を計算
するために使用することができる。 ここで、第４図のアルゴリズムに第２図の障害
アドレスをそれぞれ代入することにより、制御レ
ジスタの内容CR_iをそれぞれ次のようにして求め
ることができる。

【表】

【表】 このようにして求めたCR_iを該当する制御レジ
スタ３４に挿入すると、第２図に示した種々の障
害は第５図に示すように適正に再配列されること
になる。すなわち、第２図のカードA₂における
チツプ・アドレス00及び10は実効的に他のチツ
プ・アドレス11及び01にそれぞれ変換され、そし
て第２図のカードA₃におけるチツプ・アドレス
11は実効的に他のチツプ・アドレス00に変換され
るのである。 このアルゴリズムは他のソフトウエアで実現す
ることもできる。以下にはその１つの例が示され
ている。但し、以下の例では、障害の表示は、殆
んどのプログラミング言語に適合するように、２
進表示ではなく、10進表示でなされている。 第６図の４ビツト・アレイは、アドレス・ビツ
トが10進表示で表わされている点を除くと、第２
図のアレイと同様の構成を有する。第６図で黒く
示した領域は、当該メモリの障害ビツトを表わ
す。第６図から以下の障害マツプを生成すること
ができる。 カード チツプ ワード線 ビツト線 ０ ２ ０ ０ １ ０ ４ ３ １ １ ３ ０ ２ １ ０ ３ ３ ２ １ ４ 第６図から容易に理解しうるように、当初はメ
モリ・ワード１，３，３及び２，１，４に訂正不
能なエラーが存在する。まず、10進表示がどのよ
うに作用するかを理解するために、カード２へ
CR値２が加わり、カード３へCR値１が加わるも
のとする。そうすると、カード２における障害チ
ツプの論理アドレスは１から３へ変わる。これ
は、その物理アドレス１と加えられたCR値２と
の排他的OR演算結果である。同様に、カード３
における障害チツプの論理アドレスは２から３＝
２＋１に変わる。かくて、当該メモリは実効的に
第７図に示すように再構成され、従つて訂正不能
なエラーはもはや存在しないことがわかる。前述
のように、CR値を適切に選択することにより、
第６図の実施態様における訂正不能なエラーを分
散させうることを説明したので、以下ではAPL
で記述するに適したCR選択アルゴリズムを説明
する。 一層詳細には、このアルゴリズムは次のように
進行する。 (1) A0をカード０における障害のリストである
とする。かくて、このアルゴリズムの任意の実
行点におけるＡは、この点に至るまで障害チツ
プの論理アドレスで置換された障害のリストと
なる。カード０は置換しないので、CR＝０と
なる。 (2) Ｎ＝０をセツトする。 (3) Ｎを１だけ増分する。 (4) Ｉ＝０をセツトする。 (5) Ｉを１だけ増分する。 (6) カードＮにおける障害をANで表わし、AN
における第Ｉ番目の障害をANIで表わすもの
とする。またＡにおける全障害の論理チツプ・
アドレスを含む集合であつて、ANIが所与の
障害と同じ論理チツプ・アドレスを占有するよ
うにカードＮが置換された場合にはANIがこ
の障害とともに訂正不能エラーを生ぜしめるよ
うな特性を有する集合を、CANHITで表わす
ものとする。かくて、CANHITの１つの要素
を、ANIにその論理チツプ・アドレスとして
与えるようなCR値を取除くことが要請される。
これらのCR値は次のように表わされる。 （ANIの物理チツプ・アドレス）CR∈
CANHIT、又は CR∈（ANIの物理チツプ・アドレス）
CANHITかくて、CANHIT中の値とANIの物
理チツプ・アドレスとの排他的OR演算を行な
い、そしてその結果値を考察中のCR値の集合
から取除く。 (7) もしＩがAN中の障害の数より小さければ、
ステツプ５に進む。 (8) もしCRの値のうち取除かれなかつた任意の
値が存在するならば、その１つの値（たとえば
最初の値）を第Ｎ番目のカードに対するCR値
として選択する。さもなければ、終了する（こ
の場合、当該メモリにおける訂正不能なすべて
のエラーを分散させることに失敗したことにな
る）。 (9) もしＮが当該メモリにおける最終カードの番
号よりも小さければ、ステツプ３に進む。さも
なければ、当該メモリにおける訂正不能なすべ
てのエラーを成功裡に分散させたことになる。
以下のAPLプログラムは本明細書の補足資料
として提供される。 第６図のメモリに作用する場合のこのアルゴリ
ズムを以下カードごとに説明する。 カード０：カード０を置換する必要はないから、
CR＝０となる。かくてＡは１×４の
マトリクス（０、２、０、０）であ
る。 カード１：A1は次に示すとおり２×４のマトリ
クスである。 １ ０ ４ ３ １ １ ３ ０ 従つて、A11は（１、０、４、３）であり、
CANHIT＝２である。というのは、チツプ障害
（９、２、０、０）とA11とが同一の論理チツ
プ・アドレスへ置かれたならば、訂正不能エラー
を生ぜしめるからである。かくて、 CR∈（A11の物理チツプ・アドレス）
CANHIT、又は CR∈０２、又は CR＝２ を満足するようなCRが取除かれる。ここで、CR
についての選択の余地は０、１及び３である。 A12＝（１、１、３、０）であり、そして
CANHITは依然として２であるから、CR値３＝
１２を取除くことが望ましい。今やCRについ
ての選択の余地は０及び１である。CR＝０が選
択され、かくてカード１は全く置換されないこと
になる。この場合、Ａは次のとおりである。 ０ ２ ０ ０ Ａ＝１ ０ ４ ３ １ １ ３ ０ カード２：A2＝（２、１、０、３）であり、
CANHIT＝０、１、２である。次の
条件を満足するCRが取除かれる。 CR∈１｛０、１、２｝＝｛１、０、３｝ 今や残つている唯一のCR値はCR＝２である。
これを適用すると、A2における障害の論理アド
レスは（２、３、０、３）となり、従つてＡは次
のとおりとなる。 ０ ２ ０ ０ Ａ＝１ ０ ４ ３ １ １ ３ ０ ２ ３ ０ ３ カード３：A3＝（３、２、１、４）であり、
CANHIT＝２である。CR＝０＝２
２が取除かれる。CRについての選択
の余地は１、２、３である。CR＝１
が選択され、従つてA3における障害
の論理アドレスは（３、３、１、４）
となる。最後的に、Ａが次のように得
られる。 ０ ２ ０ ０ １ ０ ４ ３ Ａ＝１ １ ３ ０ ２ ３ ０ ３ ３ ３ １ ４ 基本的アルゴリズムについてなされた、簡単で
はあるが強力な増強策は、メモリの諸カードを考
察する当該アルゴリズムの順序に関係する。前述
のように、このアルゴリズムはこのメモリを“左
から右へ”順次に進行する。すなわち、諸カード
がその順序０、１、２、……どおりに考察される
のである。このアルゴリズムを大幅に改善するに
は、すべての状況について同一の任意的順序付け
を使用するのではなく、考察中の特定の障害マツ
プを考慮したカード順序付けを使用することがで
きる。 一般に、このアルゴリズムはエラーの数に従つ
たカードの順序付けを含む。このアルゴリズムを
実行中の特定の点で、CR値を探そうとしている
カードが“悪く”なるにつれて、すなわちこのカ
ードの“障害度”が大きくなるにつれて、その
CR値に対する選択の余地は一層小さくなる。さ
らに、他のすべての条件が同等である場合、この
アルゴリズムで既に考慮された障害が増大するに
つれて、集合“Ａ”における障害によつて既に占
有されているメモリ中の論理アドレスが増大する
ので、CR値に対する選択の余地が一層小さくな
る。かくて、もしこのアルゴリズムが“最悪”の
カードを最後に考慮するならば、その成功の見込
みは殆んどなく、従つて該カードについて適切な
CRを見出すことはできないであろう。そうする
と、これらのカードを“最悪”の側から“最良”
の側へ順番に取ることが理に適つている。 このような順序付けを正確に規定するには、
“最悪”という意味を正確に決定することが必要
である。これらのカードを順序付けする上で成功
を収めた簡単な方法は、“最悪”のカードを“最
大”の障害セルを含むカードと定義することであ
る。かくて、当該アルゴリズムでこの方式を使用
すると、最も障害の多いセルから順番に複数のセ
ルが取られる。図示されたメモリでは、各ビツト
線又は各ワード線の障害は４障害セルとしてカウ
ントされ、各チツプ障害は16障害セルとしてカウ
ントされる。 たとえば、前述の順序付け方式を第６図のメモ
リで使用すると、当該アルゴリズムは複数のカー
ドを０、１、２、３の順番に取るので、当該アル
ゴリズムは成功することになる。 もちろん、他の順序方式も可能である。たとえ
ば、“最悪”のカードを、障害のない完全なチツ
プ数が最も少ないカードとして定義することがで
きる。 アドレス置換を実現する際に可能な変形は、ワ
ード線及び／又はビツト線アドレスをチツプ・ア
ドレスとともに置換することである。 他の変形は第４図のステツプ８を修正すること
により、_iが空である場合には、当該アルゴリズ
ムが以前のCR値の選択に戻り、そして１より多
い選択が可能であつた場合とは異なる選択を行う
ようにすることである。 第８図を参照するに、第１図に示したものと同
様のメモリ４０は通常のエラー訂正（ECC）論
理４２によつて検査される。ECC論理４２から
訂正不能エラー信号が生ずると、メモリ・テスタ
４４によつてメモリ・アレイのテストが行われ
る。テスタ４４は、訂正不能エラーを有するメモ
リ位置へテスト・パターンを印加するための装置
である。たとえば、テスタ４４はオール１のパタ
ーンに続いてオール０のパターンをこのようなメ
モリ位置へ印加することにより、０又は１に縮退
されたビツトを決定することができる。障害ビツ
トが識別された場合、これらのアドレスは障害マ
ツプ４６中のメモリに（本明細書で説明した様式
又は目的に応じて他の様式に従つて）記憶され
る。 また訂正不能エラー状態は、制御レジスタ３４
中のデータを変更して訂正不能エラー状態を取除
くために、置換発生論理４８の動作を開始させ
る。本発明に従つた置換発生論理４８は前述のア
ルゴリズムを実行可能なマイクロコード化プロセ
ツサである。 置換発生論理４８の出力はメモリ４０の種々の
ビツト位置に対するCR値であるから、これらの
CR値は制御レジスタ３４へ供給される。制御レ
ジスタ３４はLSSD式シフト・レジスタで構成す
ることが可能であり、こうするとLSSDチエーン
に沿つて適正な制御レジスタ段へデータをシフト
することができる。 本発明の実施態様は前述のとおりであるが、他
の実施態様も可能である。たとえば、前掲の米国
特許第3812336号に記述されているように、各ビ
ツトの位置を単一のアレイに設けることも可能で
ある。また、ワード線及びビツト線を置換するこ
とも可能である。

【図面の簡単な説明】

第１図は本発明が適用されるメモリの概略図、
第２図は第１図のメモリにおける１組の障害を示
す図、第３図は第１図のメモリで使用するに適し
た排他的OR回路を示す図、第４図は訂正不能エ
ラーを再配列するための本発明のアルゴリズムを
示す流れ図、第５図はメモリ・アドレスを第４図
のアルゴリズムに従つて再配列した後の第２図の
１組の障害を示す図、第６図は第１図のメモリに
おける他の障害を示す図、第７図はメモリ・アド
レスを第４図のアルゴリズムに従つて再配列した
後の第６図の障害を示す図、第８図は本発明の実
施態様を包含するメモリ・システムを示すブロツ
ク図である。

Claims (1)

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