JPS58215800A - メモリ再構成方法 - Google Patents

Abstract

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

Description

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

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

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

訂正可能なエラーよりも多い数のエラーを検出しうると
いう、前述の如きエラー訂正符号の能力を有効に利用す
るために、米国特πｆ第３６４４−９０２号は、検出可
能であるが訂正不能なエラーを、検出可能でしかも訂正
可能なエラーへ変更するための手段を開示している。こ
の特許では、メモリ・ユニットは複数のアレイから成り
、該アレイの各々は当該メモリ・ユニットにおける１ビ
ツト位置のすべてのビントラ保持するようにされている
。

これらのアレイは、所与のメモリ・ワードがアドレスさ
れるときその適正なビットが各アレイから選択されるよ
うに、デコーダ回路を通してそれぞれアドレスされる１
、この特許で示唆されているのは、デコーダへ供給され
るアドレスを永久的に修正し、かくてアレイを物理的に
スワップして諸ビットをメモリ・ワード間でスワップす
ることにより、訂正不能なエラーを有するメモリ・ワー
ドを訂正可能なエラーを有するメモリ・ワードへ変更す
る、ということである。

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

Ｖｏｌ、１’６、Ａ４、Ｓｅｐｔｅｍｂｅｒ　　１９７
ろ−ｐａ、ｇｅ　１２４５なる文献には、メモリ・ビッ
トのスワップを行うためのアドレス修正方式が記述され
ている。、この方式では、特定ビット・アレイのデコー
ダへ供給されるアドレスは、メモリ・ワードの特定ビッ
ト位置に関連するシフト・レジスタに記憶されたデータ
の関数として、論理回路に工って修正される。この論理
回路は、特定ビット位置のデコーダに加わる各入力ごと
に１つの排他的ＯＩｔゲグーを含んでい石。排他的ＯＲ
ゲートの各々はその入力としてワード・アドレスの１デ
イジツト及び成るシフト・レジスタ段の出力を受取り、
そしてその出力をデコーダの１人力へ供給するっ前記文
献のものでは、障害ビットのデコーダ入力アドレスは、
この障害ピントが要求されるときこれに代わってビット
立置０がアクセスされるように、シフト・レジスタに配
置される。一方前記特許のものでは、ガロア体の異なる
数が各シフト・レジスタ段にそれぞれ記憶される。すな
わち、０が第１ビット位置のシフト・レジスタ段に記憶
され、以下同様の操作が行われて、最後に必要とされる
最大数が最終ビット位置のシフト・レジスタに記憶され
るのである。多重ビット・エラーが検［れる場合、第１
ピントｆｉ′Ｌ置のシフト・レジスタを除く各シフト・
レジスタは１ガロア数だけシフトされる。このことは、
障害メモリ・ワードを構成する諸ビット６分散させるこ
とによって、検出された多重ビット・エラーが取除かれ
ることを保証する。この分散の結果、障害ビットの各々
は異なるメモリ・ワードに終結し、かくて訂正不能な多
重ピント・エラー状態が訂正可能な多数の１ピント・エ
ラー状態へ変更されることになる。

また、米国特許第５７８１８２６号及び第５８９７６２
６号には、障害ピントの位置に関するテスト結果を使用
し、該位置に従って諸チップを複数のグループへ分割す
ることが記述さＪｔている。

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

１９８２年６月２９日に出願された米国特許出願第３６
２９２５号では、メモリ・ワード間のビット・スワツピ
ングは、当該メモリ中の障害ビットに関するデータを使
用することによって行われる。ピント・アドレスの置換
（ｐｅｒｍｕｔａｔｉｏｎ）は排他的プロセスによって
行われ、該プロセスは（メモリのエラー訂正回路によっ
ては訂正不能な）ピント障害の整列に帰着する工う夷ア
ドレスの組合せを識別するとともに、他の組合せに対す
る選択プロセスを制限する。その実施態様では、訂正不
能な障害の組合せを決定するために、種々の障害は、チ
ップ障害、ワード線障害、ビット線障害又はピント障害
の如き型によって類別される。然る後、ビット・アドレ
スは障害の数の減少順に置換さオＬる。

〔発明、の概要〕

本発明によれば、メモリ・ワード間のビット・スワツピ
ングは、当該メモリ中の障害ビットに関するデータを使
用する、新しいプロセスに裏って行われる。前記米国特
許出願第３６２９２５号では、各ビン）　［ｉ′Ｌ置の
障害ビットに対するアドレス位置は排他的プロセスによ
って選択されるが、この排他的プロセスは既にアドレス
が置換されたビット位置のみを考慮する、本発明では、
これか０置換すべきピント位置におけるビット障害に関
するデータも考慮される。このするため、障害ビットの
挿入に対する゛優先ワード・アドレス位置″のリストが
維持される。優先（ｐｒｅｆｅｒｒｅｄ）ワード・アド
レス位置とは、その時点において障害ピッｈ　ＩＬＬ置
のスレッショルドよす低いレベルヲ保持するようなもの
である。各障害ビットがこれらの優先ワード・アドレス
位置のうち１つへ置換されると、当該障害ビットの配置
を考慮するためにこのリストが変更される。置換が行わ
れるまで、障害ピントの（置換されていない）実際の物
理アドレスがこのリスト全計算するのに使用される置換
された後は、メモリの論理アドレスがこのリストｌ変更
するのに使用される。

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

本発明の他の目的は、メモリ中の障害セルに関するデー
タを使用してメモリ・ワード中のビット全スワップする
ことにある。

本発明の他の目的は、エラーの型によって類別された既
知のエラー状態に基いて、メモリ・ワード中のピントを
スワップすることにある。

〔実施態様の説明〕

第１図を参照するに、７２ピツ１（ｎ＝７２）−・のメ
モリ・ワードを構成する各ビット位置Ｂ１ないしＢ７２
の記憶セル１０は、各ビット位置に対応する各メモリ・
カード１２中の複数のアレイ１４にそれぞれ配列される
。アレイ１４は１６ビントのアレイであり、各セル１０
は４本のワード線１８及び４本のピント線２０の交点に
それぞれ配置される。各アレイ１４は対応するワード・
デコーダ２２及びピント・デコーダ２４全通してアドレ
スされ、該デコーダは２ピット・アドレスＷｏ、Ｗｌ及
びＢ。、Ｂ１’ｉそれぞれ受取る。

各アレイ１４に関連するワード・デコーダ２２及びビッ
ト・デコーダ２４に加えて、各カード１２は４ピツＩ・
のチップ・アドレろＣ′ないし０５′全受取るテンプ・
デコーダ２６１ｃ含む。チップ・デコーダ２６は、各カ
ード１２に設けられた１６個のアレイ１４のうち１個の
出力を選択する。

チップ・アドレス・ピントＣ′ないしＣ′０ろ は排他的ＯＲ回路３０ａないし３０ｄのそれぞれの出力
であり、該回路はメモリ・アドレス・レジスタ３２から
アドレス・ビットＣないしＣａ′ｆｆ：それぞれ受取る
とともに、シフト・レジスタ形式の制御レジスタ３４か
ら他のアドレス・ビットＺ。

ないしＺ３をそれぞれ受取る。従って、もしアドレス・
ヒスｌ−Ｚ　　ないしＺ６の全部がＯであれば、０ テソゾ・デコーダ２６はメモリ・アドレス・レジスタ３
２によって要求された特定のアレイ１４をアクセスする
ことになる。さもなければ、すなわチｆｌｉｌｌ　ｍ＋
Ｉレンスタ３４中のアドレス・ビットＺ　　ｆｚいしＺ
、の組合せが他のものであれば、チップ・デコーダ２６
は他のアレイ１４のうち１個をアク−ヒスする。

要約すると、メモリ・アドレス・レジスタ５２は、８ア
ドレス・ピッＥ　（Ｎ　　ないしｃ３、Ｗｏ、Ｗｌ、ｎ
ｏ、Ｂｌｉすべてのカード１２１ないし１２　へ共通に
転送する。各カード１２では、アドレス・ピントＷ、Ｗ
Ｂ　　１Ｂ　　は１６個の０１’０１ アレイ１４にある同じセル１０にアクセスするつアドレ
ス・ビットＣ′ないし０３′は各カード１２に設けられ
た１６個のチップのうち１イｍを選択し、かくてその出
力をアクセスされたメモリ・ワードのビットＩ３１ない
しＢ７２の１つとして読出す。もしアドレス・ビットＺ
　ないしＺ３の全部がＤであれば、各カード１２の同じ
アレイ１４にある同じピント１立置かアクセスされる。

一方、もし任意のカード１２　に設けられた制御レジス
りろ４の内容Ｚ　ないしＺ３が全部０でなければ、この
カード１２　のビット出力１３　　は他のアレイ＋　　
　　　　　　　　　　　　　　　　　　　　４１４の同
じビット１立１４から供給される。

本発明に従って、制御レジスタ６４の内容は、チップの
障害に関する記憶データに基いて選択される。本明細書
では、このプロセスを抽象的な用語で記述するのではな
く、成る例をあげてこオｔを順々に説明してゆくことに
する。第２図の障害マツプを参照するに、そこには第１
図に示したメモリの最初の１０ビット泣置Ｂ　ないし１
３１ｏに存在する複数の障害が示されている。以下の記
述では、説明の便宜上、メモリ中の残りのビット１立置
にはエラーが存在しないものと仮定する。第２図では、
障害のあるアレイ１４は記号Ｘで示されている。図示の
如く、１６個のワードＯないしＦのうち、ワード６及び
９は３ビツト・エラーを有し、ワード０．２、ろ及びＣ
は２ビツト・エラーを有し、ワードＡ及びＥは１ビツト
・エラーを有するのに対し、残りのワードはエラーケ有
さない。ここで、このメモリは１エラー訂正及び２エラ
ー検出（Ｓ　ＩＤ　Ｃ／　ｌ）　Ｅ　Ｄ　）　ｉｐ力を
備えているものと仮定する６、第２図に示すように、こ
のメモリにはエラーのないワードが８個存在しているの
で、ろビット・−ｎラー及び２ビツト・エラーを含むワ
ードに関連する８ピント・エラーを、エラーのないこれ
らのワードへ分散させることができる。

以下、本発明の再配列プロセスを実行する前、実行して
いる間及び実行した後の第１図のメモリにおける１組の
障害マツプをそオｔぞれ示している第２図ないし第６図
を参照しつつ、この再配列プロセスに使用されるアルゴ
リズムを説明する。

ステップ１：最犬のエラー分散能力（ｅｒｒｏｒｄｉｓ
ｐｅｒｓｉｏｎ　　ｃａｐａｂｉｌｉｔｙ：ＰＴ）に従
ってすべてのピッ］・・セクション（以下単に「セクン
ヨン」という）全識別する。すなわち、もし適切な置換
ベクトルを見つけることができれば、これが分散可能な
エラーの最大数である。たとえば、もしセクンヨン３”
５成功裡に置換することができれば、ワード２及びワー
ドろが１ビツト・エラーのみを有し且つワード９が（３
ビツト・エラーの代わりに）２ピント・Ａラ−一−を有
するようにすることができる。従って、セクションろの
最大エラー分散能力は乙に等しい。同様に、４ビツト・
エラーを有する七りンヨン６では、適切な置換ベクトル
によって最大ろピントのエラーを分散させることができ
る。この例では、セクンヨンろ、６．２．５．１．４．
７．８は、潜在的に６．６．２．２．１．１．１．１ビ
ットのエラーをそれぞれ取除くことかできる（第２図の
最下部に示した分散能力の数値を参照）。

ステップ２：エラーのないすべてのワード：アドレス、
すなわちこの例ではワード・アドレス１．４．５．７．
８、】３．１）、Ｆを識別する。

スフ　７　フ３　：　’！た、１ビツト・エラーを有す
るセクションに対応するようなすべてのワード・アドレ
ス、すなわちこつ例ではワード・アドレスろ、６．９を
識別する。というのは、セクション４．７．８はワード
・アドレス３．６．９において１ビット・エラーを有す
るにすぎないからである。

これらのワード・アドレスは°゛無視ｄｏｎ’ｔｃａｒ
ｅ）”ワード・アトし／スと呼ばれ、当該アルゴリズム
の後続反復ステップの間に相互に両立する（ｍｕｔｕａ
ｌｌｙ　　ｃ、、ｏｍｐａｔｉｂｌｅ）置換ベクトルを
見つけるために使用することができる。

ステップ４：最大のエラー分散能力を有する１つのセク
ションを選択する。この例では、セクション３及び６が
これに該当するので、これらのうち１つが選択される゛
ことになる。ここでは、セクション６が選択されるもの
とする。次に、セクション６における障害ワード・アド
レス、すなわちこの例ではワード・アドレス６．９、Ｃ
ＸＥを識別する。

ステップ５：セクション６における各障害ワード・アド
レスと、ステップ２で識別されたエラーのないワード・
アドレス及びステップ６で識別烙れた“無視′”ワード
・アドレスとの、排他的ＯＲ演算を行う。この排他的Ｏ
Ｒ演算によって得られたベクトルから、相互に両立する
置換ベクトルを選択する。もし完全に両立する成るベク
トルを見つけることができｔけＩｔば、′°無視パ置換
ベクトル・セットを使用するようにする。

もし”無視”置換ベクトル・セントですら役に立たなけ
れば、最大のエラーを取除くような任意の置換ベクトル
を選択する。たとえば、（画表で丸印によって表わされ
ているような）完全に両立する置換ベクトル１を利用す
ることができなければ、次善のものとして置換ベクトル
ろ、９、Ｂのうち任意のものを選択することができる。

というのは、これらの置換ベクトルは６ビント・エラー
を分散させるに際し、１ビツト・エラーを２ピント・エ
ラーの正味の分散と束にするからである。

ここで、３ビツト・エラー全部を分散可能な置換ベクト
ル１が見つけられる。そうする間、エラーのないワード
７．８、Ｄｌ　Ｆは用い尽くされる。

ワード・アドレスＥには１ビツト・エラーが存在してい
たにすぎないので、このエラーはワード・アドレスＦへ
移され、かくてワードＥをエラーのないワードにする。

セクション乙におけるアドレス置換後の障害マツプは第
５図に示されており、そこではＰＴ及び各ワード中のエ
ラー数がそれぞれ更新されている。

スデツプ°６：続いて、最大のエラー分散能カ（ＰＴ）
’を有する次のセクションに進み、エラーのない残りの
ワード・アドレスを使用してステフグ５０手順を、反復
する。ここで注意すべきは、ステップ５は最大のエラー
分散能力（ＰＴ）の値を変更することがあり、従って次
のセクションはＰＴの更新された値に基いて選択されね
ばならない、ということである。かくて、次のセクショ
ンとしテ、セクション６が選択される。セクション３に
おける障害ワードは、２．３．９である。

）ｌ　　　　匁　　　　　　　Ｓ　　　　　　　　Ｓ相
互に両立する置換ベクトルとして、６ビント・エラーを
分散可能な置換ベクトル７が見つけられる。このプロセ
スでは、エラーのないワード４．５、Ｅが使用される。

更新されたＰＴを含む障害マツプは、第４図に示されて
いる。

ステップ７：ここで残りの各セクション１．２．５．７
において最大のエラー分散能力は１であることがわかる
。この状況では、最少数のエラーを有するセクションに
ついて作業を行うことが望ましい。セクション１及び２
はそれぞれ２ビツト・エラーを有しているから、そのど
ちらを選択してもよい。ここではセクション２金選択す
るものとする。セクション２における障害ワードは、０
及び２である。ステップ６と同様に、エラーのない残り
のワード１及びＢｆｆ：使用してステップ５の手・−／
″ 順を反復すると、次の結果が得られる。

゛°鋪見″ワード・アドレス エラーのないワード・アドレス　　１　Ｂ、３６９１１
３＋！＋６９ ５９．１４Ｂ ここでは、置換ベクトル１を選択するために、°°無視
゛′アドレスが利用される。これは１ピント・エラーを
分散させると同時に、新しい１ビツト・エラーを追加す
るが、この新しいエラーは１個の障害（これはエラーの
ないワード・アドレスが利用可能であれば、そこへ移動
させることができる）を有するセクション４を選択する
ことによって分散させることができる。また、容認街能
な状況を与えるために、置換ベクトル−６，９又はＢを
選択してもよい。ステップ７の後の障害マツプ４４、第
５図に示されている。

ステップ８：セクション７は１ピツト・エラーを有する
にすぎないが、これは２ビツト・エラーを有するセクシ
ョン５中のエラーと結合するのでこのセクション７は作
業すべき次の適切なセクションである。置換ベクトルの
選択は、ステップ７で説明したセクション４のそれと同
じである。

従って、すべてのエラーを分散させるような置換ベクト
ルの完全なセットは、次のとおりである。

１ ７ １ １ ７　　　　　　　　　　　　　　Ｄ ココテ注意すべきは、もしステップ７でセクション２０
代わりにセクション１が選択されたならば、”無視”′
アト）スを要することなしに置換ベクトル１が相互に両
立するものとして見つけられたであろう、ということで
ある。セクション１に対する置換ベクトル１はワード０
及びＡにおけるエラーをワード１及び１３へ置換し、か
くてセクション４をそのままにする。最終的な障害マツ
プは第６図に示されており、そこではすべての多重ビッ
ト・エラーが分散されている。第７図は、前述のアルコ
リズムを示す流れ図である。このアルゴリズムはＡＰＬ
等のプログラム言語で容易に実現することができる、け
れども、本明細書では記述を簡潔にするためその人つな
実現プログラムは示されていない。

このアルゴリズムは１エラー訂正／２エラー検出（ＳＥ
Ｃ／ＤＥＤ）能力金有するメモリに関連して説明された
が、このアルゴリズムは２エラー訂正／３エラー検出（
Ｉ）ＥＣ／ＴＩすＤ）能力を有するメモリ中のエラーを
分散させるためにも使用することができる。後者の型の
メモリについては、６個又はそれ以上のエラーを有する
ワードを識別することが必要である。これに続いて、こ
れらのエラーを１個以下のエラーを有するワードへ分散
させるために、アドレス置換が使用される。この置換は
、前述のように更新されたエラー分散能力（ＰＴ）の最
高直によって決定される順序で行われる。

前述の説明は、アレイ１４（第１図）で生じた障害の型
、すなわちこの障害がビット障害、ワード線障害又はチ
ップ障害のどれに類別されるか、ということを考慮して
いない。第８図に関連してなされる以下の説明では、障
害の型が類別され、一層複雑なメモリへ適用される。こ
のメモリは１８枚のカードから成り、該カードの斧々は
１２８個の６５にチ゛ツブを有する。これらのチップは
、５２×４アレイとして各カードに設けられる。各カー
ドは７２ビツト幅の各メモリ・ワードに対しそＪＬぞｉ
ｔ　４ピントｆ与え、かくて２００万個の７２ビツト・
メモリ・ワードを提供する（基本記憶モジュールＢＳ、
Ｍ）。しかしながら、エラー分散論理の側から見れば、
このメモリは７２セクシヨンから成るものと考えること
ができる。各セクションには、５個の排他的ＯＲゲート
及び５個のラッチを有するそオを自体の独立したアドレ
ス変換論理が備えられる。この論理の結線様式は、３２
チップ行全識別するアドレス・ヒツトが前記ランチに前
取て記憶され装置２換ビットの値に従って変換されるよ
うに、決められている。

第８図はかかるメモリの障害マツプを表わす。

一般にこのメモリは３２×にマトリクスから成る。

第８図の例では、障害アレイを有する５２セクシヨンが
存在する。各セクションにおける障害の型には、完全な
テンプ障害、１以上のビット線障害、１以上のワード課
障害又は１以上のセル障害若しくはピント線、ワード線
及びセル障害の組合せがありうる。このような障害が２
以−ヒのセクションで生じて、それらのアドレスが相互
に整列するようになると、１メモリ・ワードあたり２ヒ
ツト以」二のエラーが生じうる。アドレス変換の目的は
このようなアドレス整列を回避すると共に、２ビツト以
上の障害を回避しうる様な構成を提供する事である。第
８図の枠内に示したエントリ”０”乃至°°４′”は、
それぞれ″障害なし”、”チップ障害″、°′ヒント線
障害°′、゛ワード線障害”及び”七ノド障害”を表す
。エン）　ＩＪ　”　５”乃至”７″及び”９″Ａ４は
多重障害の状況を表わす。たとえば、エントリ５はビッ
ト線障害及びワード線障害を含むチップを暗示している
のに対し、エントリ７はワード線障害及びセル障害を含
むチップを表わす。障害のあるビット線、ワード線及び
セルの実際のアドレスに加えて、第８図に示す如き障害
マツプで利用可能な情報を含むものは、完全な障害マツ
プと呼ばれる。

以下では、完全な障害マツプを使用することによって、
エラー分散アルゴリズムをステップごとに説明する。次
いで、このアルゴリズムを部分障害マツプへ適用する。

ここで、完全な障害マツプ、すなわち第８叩に示され且
つ以下の第１表で要約されているような障害データが利
用可能であるものと仮定する。第８図には各チップにお
けるすべての障害型のアドレスが示されているけれども
、第１表には当該アルゴリズムによって考慮せねばなら
ない障害のアドレスだけが示されているにすぎない。な
ぜなら、これらの障害だけが、その同一の１アドレス”
又は゛°アドレス成分”に起因する整列全潜在的に生ぜ
しめることがあるからである。以下の第２表には、当該
アルゴリズムが利用可能な種々の置換ベクトルをランダ
ムに選択する場合にその選択から除外さオｔねばならな
いような置換ベクトルがリストされている。たとえば、
第２表の第１行に示すように、もし当該アルゴリズムが
セク／ヨン１４について置換ベクトルｐ１を選択するな
らば、セクンヨン２８に対する置換ベクトル全選択する
際に置換ベクトル（ｐｌ）−４）は除外されねばならな
い。さもなければ、障害の分散を行った後に、行アドレ
ス１６におけるワード線障害と行アドレス９におけるセ
ル障害が整列し、かくて２ビツト・エラーを有する１つ
のメモリ・ワードを生せしめることになろう。

以下の第３表は第８図及び第１表に基いて作成された初
期エラー要約表を示す。この表は６２行及び７列からな
る。第１列は行アドレスを表わし、第２列は各行アドレ
スにおける障害の数を表わす。

第６列ないし第６列は、各行アドレスにおけるチップ障
害、ビット線障害、ワード線障害及びセル障害の数をそ
れぞＩ’を表わす。第７列は、２ピツトリ、−Ｌのエラ
ーを有するメモリ・ワードの数を表わす。丸印で囲んだ
エントリは、障害の整列を生せしめるような同一アドレ
スを有する複数の障害を表わす。たとえば、行アドレス
５において、セク７ヨン２０及び２８の２チツプは同一
アドレスを有する障害ビット線を有し、従って各々が２
ピント・エラーを有する２５６メモリ・ワード金主せし
めることになる。

ステップ１：第８図及び第１表ないし第６表を参照して
、まず°°作業マトリクス′″、′１′なわち障害の整
列を生ぜしめ、従って２ビツト以」二のエラーｉ有する
メモリ・ワードを生せしめる工うなセクションだけ全抽
出する。たとえば、第８図の行アドレス１７を参照する
に、そこではセクション４２におけるチップ障害が、セ
クション６の（ワード紳士セル）障害、セクンヨン８の
ワード線障害、セクション４１のピント線障害及びセク
ション７１のセル障害とそれぞれ整列する。これらの障
害の整列に応じて、２ビット以上のエラーを有する７７
２メモリ・ワードが生ぜられる。従って作業マトリクス
には、これらのセクション６．８．４１．４２及び７１
が含まれる。

この例のメモリでは、ワード・マトリクスは次のセクシ
ョンから成る３２Ｘ２４マトリクスである。

１、ろ、６．８．１１．１４．１８．１９．２０．２５
．２８．２９、 ろ２、乙６．４１．４２．４７．４８．５１．５４、６
３、６５、７１ ステップ２：第８図及び第２表を参照して、障害の各型
ごとに１セツトの゛°目標アドレス″ヲ選択する。ここ
で゛′目標アドレス″とは、多重ビット・エラーを有す
るメモリ・ワードの数を増加させることなしに、特定の
型の障害を移動することができるようなアドレスをいう
。

この例では、次の複数セントのアドレスが障害の各型Ｋ
　ｉｔする目標アドレス・セット全構成する。

（障害のない行アドレス）−（なし）　　　　・（セル
障害のみを有する行アドレス又は障害のない行アドレス
） ＝（２，７，１２，１９，２０，２１，２６，２７，２
８）第１回目の選択： （ピント線障害を有する行アドレス又はピント線障害及
びセル障害を有する行アドレス）＝（３，４，８，１１
，１４，１５，１Ｂ、１，３１）第２回目の選択： （ビット線障害又はセル障害を有する行アドレス） ＝　（２、ろ、　４、７、８、１１、１２、１４、１５
、１８、１９．２０．２１．２６．２７．２８．３０，
３１）第１回目の選択： 【ワード線障害を有する行アドレス又はワード線障害及
びセル障害を有する行アドレス）＝　（ｏ、　ｉ、５．
１０．２０．２４．２９）第２回目の選択： ［ワード線障害又はセル障害を有する行アドレス）− ＝（０，１，２，５，７，１０，１２，１，９，２０，
２１，２２，２４，２６、２７，２８，２９） ｆビット線障害に対する第２回目の選択対象となる目標
アドレス・セット）又は（ワード線障害に対する第２回
目の選択対象となる目標アドレス・セット） ＝（０，１，２，６，４，５，７，８，１０，１１，１
２，１４，１５，１８，１９，２０，２１，２２，２４
，２６，２７，２８，６０、ろ１） 第８図では、障害のない行アドレスは存在しておらず、
従って理想的に云えば、チップ障害を移動することがで
きるような目標アドレスは存在しないことになる。この
ような状況では、次善の目標アドレスとしてセル障害の
み金有する行１ドレスを選択することが鳳きる。同様に
、ビット線障害及びワード線障害を既に有する行アドレ
スを、ビット線障害及びワード線障害に対する目標アド
レスとして選択することが望まれるであろう。このよう
にすると、目標アドレス・セットのサイズをほぼ同じに
維持することが可能となるからである。このことは分散
される障害の数とは無関係であり、従って一層多くの障
害を分散させるのに役立つ。

ステップ３二”作業マトリクス”の各セクションごとに
、障害の各型のアドレスとそれらの“目標アドレス・セ
ット°°中のアドレスとを排他的ＯＲ演算することによ
り、相互に両立する最大の置換ベクトルを見出す。たと
えば、行アドレス５及び１０にセル障害を有し且つ行ア
ドレス１７にワード線障害を有する°′作業マトリクス
″のセクション８については、相互に両立する最大の置
換ベクトルは次のように決定される。

〔セル障害に対する目標アドレス・セント中のアドレス
〕■〔セク／ヨン８中のセル障害のアドレス〕 〔ワード線障害に対する目標アドレス・セット中のアド
レス〕■〔セク／ヨン８中のワード線障害のアドレス〕 ここで、相反に両立する最大のものばかりでなく、完全
に両立する（３ウエイの）１セントの置換ベクトルを容
易に選択することができる。これらは、丸印で囲まれた
エントリによって示されている。これらの任意のものは
、多重ピント・エラーｅ有するメモリ・ワードの数を減
少させることができる。従って、当該アルゴリズムはそ
の１つをランダムに選択する。相互に両立する最大の置
換ベクトルは必ずしも完全に両立する置換ベクトルでは
ないが、完全に両立する置換ベクトルは當に相互に両立
する最大の置換ベクトルである。たとえば、セクション
８について完全に両立する置換ベクトルを見出すことが
できない場合は、当該アルゴリズムは２ウエイの両立性
を探索する。このような状況で、もし１．１：り多い選
択が可能であれば、当該アルゴリズムは、多重ピッｉ・
・エラーを有するメモリ・ワードの数を最小にするよう
な置換ベクトルを選択する。当該アルゴリズムが各セク
ションを次々と処理するにつれて、目標アドレス・セッ
トは継続的に更新される。１対の障害が再整列した場合
には、当該アルゴリズムはこの対における第２のセクシ
ョン金自動的にスキップする。当該アルゴリズムのかか
る特性は、高度の収束性を可能とする。

第９図はメモリの最終的な障害マツプを示し、以下の第
４表は障害を分散させた後の対応するエラー要約図表を
示す。第４表の第７列はオールロケ含んでいるが、これ
はメモリ・ワードに２ビット以上のエラーを生ぜしめた
すべての障害が分散されたことを暗示している。

次に、説明の完全を期すため、部分的な障害マツプだけ
が利用可能な状況で、障害を分散させるための一般的接
近方法を説明する。障害マツプの性質は、障害の型及び
個々のチップにおけるそれらのアドレスについて利用可
能な情報の量に応じて変わりうる。例えば、成る障害マ
ツプは、チップ障害、ピント線／ワード線障害及びセル
障害のみを識別し、障害のある線がワード線又はヒント
線のどちらであるかという情報を与えない。一方、第２
の障害マツプは、チップ障害、ヒント線障害、ワード線
障害及びセル障害を識別する事ができるが、所与のチッ
プにおける障害ピント線、ワード線又はセルの１）ｚ＃
を識別する事ができない。これら障害マツプを使用する
一般的接近方法は同じであるけれども、第２の障害マツ
プを利用するほうが一層簡単であり、また所要時間も一
層少ないことは明らかである。

この一般的接近方法は利用可能な障害情報を受取る事か
ら開始し、そして恰も全てのヒツト線、ワード線及びセ
ル障害が個々のチップ中で異なるアドレスを有するかの
様に、全ての可能な障害を分散させる。云いかえれば、
任意の２ビツト線及びセルは置換可能な任意の行アドレ
スに集めることができるのである。同様に、任意の２ワ
ード線及びセルは置換可能な任意の行アドレスに集める
ことができる。

この後、メモリは置換ベクトルの値に従って再構成され
、そして２ビット以−ヒのエラーを有するメモリ・ワー
ドについてテストが行われる。再構成されたメモリ中の
障害メモリ・ワードのアドレス及び該メモリ・ワード中
の障害ビットの位置は、以前には利用できなかった成る
障害の型に関する情報及びそれらのアドレスを与える。

この新しい情報に、Ｊ−って障害マツプが更新され、そ
して新しい１セツトの置換ベクトルが再び見出される。

続いて、メモリは再構成され、そしてテストが行われる
。この手順は、多重ビット・エラーを有するメモリ・ワ
ードが無くなるか又は多重ピント・エラーを有するメモ
リ・ワードの数をそれ以上減らすことができなくなるま
で、反復されるのである。

当該アルゴリズムは、第１表の障害マツプ及び＄６表の
対応するエラー要約衣がそれぞれ利用可能であることを
仮定している。唯一の相違点は、第２表でりえられる情
報、すなわち選択から除外すべき置換ベクトルのリスト
が、当該アルゴリズムには利用可能ではない、というこ
とである。この部分的な情報が利用可能であり、そして
すべてのビット線、ワード線及びセル障害のアドレスが
一意的であるものと仮定すると、当該アルゴリズムは置
換ベクトルのリストを言１算することにエリ、第１０図
の再構成された新しいメモリ・マツプ及び以下の第５表
の対応する要約衣に示すように、すべての障害を分散さ
せる。

これらの置換ベクトルとそのそれぞ２ｔのセクションは
次に示すとおりである。

セクション：１．６．８．１１．１３．１４．１７．１
８．２１．２５．２８．２９、ろ２、′３６．４２．４
８．５１．５６置換ペクトルーフ、２０．２０．７．７
．９．１６．１０．２３．１ノ、７．２９．２０．６．
１１．２７．１２．２７第１０図の再構成されたメモリ
・マツプをテストすると、セクション１４中のセル障害
とセクション４８中のワード線障害が行アドレス２２で
整列することに起因して、２ビツト・エラーを有する１
つのメモリ・ワードが存在することがわかる。

この整列は、セル障害とワード線障害が共通のアドレス
要素を有することに起因するものである。

従って、セクション１４及び２８に対する置換ベクトル
９及び２７は相互に受入れることができな・い。この例
では、当該アルゴリズムはセク７ヨ７４８のために他の
置換ベクトル２１を見出す。この置換ミクトルはメモリ
を第４表に示すように再構成するが、とれは前述の完全
な障害マツプで得られたものと同じである。このように
して再構成されたメモリでは、どのメモリ・ワードも２
ビツト以上のエラーを有していない。

前述の説明からすると、当該アルゴリズムは置換ベクト
ル全決定するために各列ごとに順次に進行するかのよう
に受取られるかもしれないが、必ずしもそのようにする
必要はない。というのは、もし多くのセクションがテッ
プ障害を有しておらず、そしてピント線、ワード線及び
セル障害に対する第１回目の選択対象である“目標アド
レス°“セントが最大の両立性という基準を満足すれば
、これらのセクションを同時に処理することができるか
らである。チップ障害を有するか又は第２回目の選択対
象である６目標アドレス・セント”を必要とし、従って
目標アドレス・セットの更新を必要とする他のセクショ
ンは、順次動作全必要とする。このような接近方法は、
完全な順次動作に比較して当該アルゴリズムの実行速度
を４０％程度まで向上させることができる。

第１１図において、第１図のものと同様のメモリ４０は
通常のエラー訂正装置（ＦＣＣ）４２によって検査され
る。エラー訂正装置４２が訂正不能工２−信号ｅＲ生す
ると、メモリ・アレイのテストがメモリ・テスタ４４に
よって開始される。

テスタ４４は、訂正不能エラーを含むメモリ位置へテス
ト・パターンを印加するような装置である。

たとえば、テスタ４４は、０又は１へ縮退したビットを
決定するために、オール１のパター７に！いてオール０
のパターンを障害メモリ位置へ印加することができる。

障害ピントが識別されると、そのアドレスは前述のよう
にメモリ゛７ステム中の障害マンプ装＠４６に記憶され
るが父は適当な他のマンピンク手段に記憶される。障害
マツプの生成は、１９８１年１２月１８日に出願された
米国特許出願第３４５９４４号明ａｊ書に記述されてい
る。

また訂正率ａヒエラー信号は、制御レジスタ３４中のデ
ータを変更して訂正下Ｗｅ　１ラー状態を取除くために
、置換生成論理４８の動作を開始させる。

本発明に従って、置換生成論理４８は前述のアルゴリズ
ムを実行可能なマイクロコード化グロセッザから成る。

置換生成論理４８の出力はメモリの種々のビット位置に
対する置換信号値であり、従ってこれらの値は制御レジ
スタ６４へ供給される。制御レジスタ３４はＬ　Ｓ　Ｓ
　Ｉ）シフトレジスタのステージから構成されうる。こ
の裏うにすると、データはＬＳＳＤＳＳ−ンに活って適
正なステージへシフト人力することができる。

【図面の簡単な説明】

第１図は本発明を利用したメモリの概略ブロック図、＠
２図乃至第６図は本発明の再配列プロセヌを実行する前
、実行している間及び実行した後の第１図のメモリにお
ける１セントの障害を示す図、第７図は本発明に従って
訂正不能エラーを再配列するための流れ図、第８図乃至
第１０図は本発明に従った障害の再配列を実行する前及
び実行した後の第２セントの障害を示す図、第１１図は
本発明を利用したメモリ・システムのブロック図である
。 出ＷｆＡ　人　　インターカショカル叱ジネス・マシニ
ング・コ−Ｊレーション代理人　弁理士　　　頓　　　
宮　　　孝（外１名） 手　　続　　補　　正　　書（自発） 昭和５８年ど月ノＺ日 特許庁長官若　杉　和　夫　殿 １、事件の表示 昭和５８年　特許願　第８７７７２　　号２、発明の名
称 メモリ再構成方式 ３、補正をする者 事件との関係　　特許出願人 住　所　アメリカ合衆国１０５０４、ニューヨーク州ア
ーモシク（番地なし） ４、代理人 住　所　郵便番号　１０６ 東京都港区六本木−丁目４番３４号 第２１森ビル 日本アイ・ビー・エム株式会社内 ６　補正の対象 （１）明細書の発明の詳細な説明の欄 （２）図面 Ｚ　補正の内容 （１）発明の詳細な説明の欄の記載を次の正誤表に従っ
て補正する。 （２）明細書第１８頁第７行〜第１０行の「というのは
・・・・・・からである。」を「というのは、これらの
置換ベクトルは２ワードにおけるエラー整列を分散させ
ることができるからである。」に補正する。 （３）　　同第３０頁の第１表を別紙１のように補正す
る。 （４）　　同第６１頁の第２表を別紙２のように補正す
る。 （５）同第６５頁第１１行の「＝（ｏｌ　１．５．１０
．２０．２４．２９）」をｒ＝（ｏ、１．５．１０．２
４．２９）」と補正する。 （６）同第３６頁第４行の「２８．３０，３１１Ｊを「
２８．２９．３０，３１１Ｊと補正する。 （７）本願添付第７図ケ別祇添付訂正第７図のように補
正する。

Claims (1)

1. 【特許請求の範囲】 各メモリ・ワードを構成するビットｔｆ装置の各々が同
   一の論理アドレス・ビットでアクセスされるように編成
   されたメモリに付随して、障害ビットを複数のメモリ・
   ワード間に分配するように選択さ第１．た置換ビットに
   基き、所与のピント位置に対する論理アドレス・ピント
   ラそれとは異なる物理−アドレス・ビットに変換するグ
   ζめの置換手段を設けることにより、前記メモリの内容
   を保護するエラー訂正手段によって訂正することができ
   ないメモリ・ワード中のエラー状態を除去するようにし
   たメモリ・ンステムにおいて： 各ピッ）　ｆｆｆ置における各障害の物理アドレスと該
   障害を移動可能な複数の目標ワード位置の論理アドレス
   とを比較し、多数の障害を目標ワード位置に移動させる
   ような置換ビラトラ選択し、すべての訂正不能エラーが
   置換されるまで前記比較及び還部操作を反復するように
   したことを特徴とする、メモリ再構成方式。