JPS6232820B2 - - Google Patents

Description

【発明の詳細な説明】 〔技術分野〕 本発明はメモリのアドレス指定、特にメモリ素
子中の欠陥乃至は故障の結果として生じる一群の
誤りを分散させるために擬似ランダム方式でメモ
リをアドレス指定することに関する。 〔先行技術文献〕 (1) 米国特許第3585586号明細書 (2) 米国特許第4006467号明細書 (3) 米国特許第4041453号明細書 (4) F.E.Sakalay，“Address Skip−−Ａ
Means for Utilizing Imperfect Storage””
IBM Technical Disclosure Bulletin、第20
巻、第５号、1977年10月、1841〜1842頁 (5) R.F.Meyers，Ｎ・Ｇ・Thoma，“Use of
Partially Good Memory Chips”Ibid、第21
巻、第９号、1979年２月、3582〜3583頁 (6) R.Mcpeters，“Module Personalization for
‘Partially Good’Chip Utilization”Ibid、
第21巻、第11号、1979年４月、4535〜4536頁 (7) W.W.Peterson，E.J.Weldon，Error
Correcting Codes，MIT Press，1972年 (8) 米国特許第3234521号明細書 (9) 米国特許第3768071号明細書 以下の説明では、上記文献を番号(1)〜(9)で参照
することにする。 〔本発明の背景〕 メモリ素子、特に半導体メモリ素子の製造にお
いては、歩留まりが100％になることはなく、製
造されたメモリ素子（例えばメモリ・チツプ）に
は不完全なものが含まれる。メモリ素子に生じる
誤りの原因及び個数は一定していないが、メモリ
素子中に存在している欠陥の性質から、メモリ素
子の連続する記憶位置に誤りが生じる傾向があ
る。例えば、メモリ・チツプの基板に欠陥領域が
あつて、その中に複数の記憶位置が含まれている
と、複数の連続するデータが誤つて書込まれたり
読出されたりすることがある。またアドレス線の
欠陥によつて誤りが生じることもある。このよう
な誤りは連続する又は周期的なアドレス系列にも
関係している。 データ処理や科学技術計算においては、メモリ
の保全性を維持することが重要であり、１ビツト
の誤りも許されないのが普通である。しかしなが
ら、メモリの応用分野によつては散発的な誤りを
許容し得るものがある。例えば、２進数で表わさ
れたペル（画素）を記憶するメモリは誤りを或る
程度許容し得る。各ペルが黒又は白だけを表わす
のであれば単一ビツトでよいが、その間の灰色レ
ベルをも表わす場合には、各ペルについて複数の
ビツトが必要である。以下では、説明の便宜上、
各ペルを黒又は白に限定して、即ち各ペルが単一
ビツトから成つているものとして話を進めるが、
各ペルが複数ビツトから成つている場合も同様で
ある。 ペルは、例えばフアクシミリ装置による書類デ
ータの伝送に使用される。フアクシミリ装置にお
いては、伝送されるべき書類は単位面積当りのペ
ル数で表わされる所与の解像度で光学系によりス
キヤンされ、次いでデイジタル信号に変換された
後、受信装置へ送られる。受信装置は、スキヤン
された画像をインク・ジエツト方式、レーザ・ス
キヤン方式、感熱方式などで復元する。このよう
なスキヤン及び復元技術は複写機でも使用され得
る。 スキヤナとプリンタとの間にメモリを設けてお
くと、動作速度の異なつたスキヤナ及びプリンタ
を使用することができ、更に１回のスキヤンで複
数のコピーを作成することができる。 復元される書類の質を上げるためには解像度を
高くする必要があり、更にそれに伴つてメモリの
容量を大きくする必要があるが、その代り誤りペ
ルによる影響は少なくなる。従つて、解像度を高
くしてメモリの容量を大きくした場合には、散発
的な誤りを或る程度許容することができる。メモ
リ素子のコスト及び歩留まりを考えると、誤りを
許容し得るメモリには不完全なメモリ素子を使用
するのが望しい。 欠陥のあるメモリ素子を用いたことによる問題
に対処するための最も一般的な技術は誤り検出訂
正技術である。初期の機械では、パリテイ検査、
５者択２符号などを利用した誤り検出が行われて
いた。例えばIBM650計算機では２−５進符号が
使用されていた。パリテイ検査は文献(7)の42〜43
頁に記載されている。 誤り訂正には、ハミング符号、多重パリテイ検
査、及びヴイタビ（Viterbi）符号のような冗長
符号などが使用される。ハミング符号は、ワード
に所定数の検査ビツトを付加することによつて単
一誤りを訂正できるようにしたものである。多重
パリテイ検査では、パリテイ検査の結果として誤
りビツトが識別されるように、ワードが複数の群
に分けられ且つ各群にパリテイ・ビツトが付加さ
れる。冗長符号技術は、例えば同じワードを３回
（以上）送信したり書込んだりするもので、有効
なワードは多数決によつて決められる。これらの
誤り訂正技術を組合わせたものも知られている。
例えば文献(7)の119頁には、パリテイ検査及びハ
ミング符号の組合わせが記載されている。また同
402頁以下には、単一誤り及び二重誤り訂正符号
が記載されている。 文献(8)には、欠陥記憶位置を有するメモリを使
用するための他の技術として、欠陥記憶位置のア
ドレス及びその代替アドレスを連想メモリに書込
んでおくメモリ・システムが記載されている。 半導体メモリ素子を使用する場合には、文献(5)
及び(6)に記載されているように、一部に欠陥にあ
るチツプを組合わせてそれらの良好部分だけを使
用することにより、誤りのないメモリが構成され
得る。 ワード中の欠陥ビツト数を１以下に抑える必要
がある場合には、文献(9)に記載されている技術が
有効である。それによれば、１つのマーク・ビツ
トを含むワードがパリテイ・ビツトと共に書込ま
れ、直ちに読出される。パリテイ誤りがなけれ
ば、ワードは正しく書込まれたものとみなされ
る。パリテイ誤りがあると、ワード全体が補数化
（反転）された後、再び書込まれる。マーク・ビ
ツトはワードが補数化されたことを示す。メモリ
からワードを読出したときにはまずマーク・ビツ
トが検査される。マーク・ビツトが補数化を示し
ていなければ、読出されたワードはそのまま使用
され、補数化を示していると、ワードは補数化さ
れた後に使用される。 上述の技術はデータの保全性を維持しつつ欠陥
メモリを使用するために考え出されたもので、一
部に欠陥のあるメモリ素子が使用されるという点
で歩留まりが上がり、結果としてメモリのコスト
が安くなる。 フオルト・トレラント・システムにおける欠陥
メモリ素子の使用についてはそれ程研究が進んで
おらず、文献も見当たらない。フオルト・トレラ
ント・システムにおいては、散発的に生じる誤り
ビツトは無視できるが、連続する多数の記憶位置
に影響を及ぼすような欠陥があると無視できない
効果が生じ、例えば大きな黒領域（又は白領域）
が誤つて白領域（又は黒領域）になることがあ
る。本発明は、このような大きな誤りの集合が生
じ得るシステムを対象にしている。 本発明の他の背景技術としては、バースト誤り
がランダム誤りに変換されるようにフアクシミリ
信号を符号化するもの（文献(1)）、各ワード中の
欠陥ビツトを１以下に抑えるようにメモリを構成
するもの（文献(2)）、及び伝送で失なわれるのが
単位パルス・ビツトだけになるように多重化
PCM信号を符号化し、その再構成を解釈によつ
て行うようにしたものがある。 〔実施例の要約〕 本発明は、フオルト・トレラント型の装置で使
用されるデータを記憶するメモリ・システムに関
するもので、アドレス指定の順序をランダム化す
ることを特徴としており、データを記憶するため
の複数のアドレス指定可能な記憶位置を有する記
憶手段と、ランダム・アドレスを与えるランダム
化手段を含むアドレス指定手段と、アドレス指定
された記憶位置に対してデータの書込み又は読出
しを行うアクセス手段とを見備している。 本発明の良好な実施例においては、アドレス指
定された記憶位置に書込まれるビツト又は該記憶
位置から読出されたビツトを補数化する手段も設
けられる。 本発明は、メモリの連続する記憶位置に欠陥が
あつても、それによる誤りの集合（バースト誤
り）を擬似ランダム方式で分散させることによつ
てメモリ欠陥の累積効果を除くもので、これによ
り、従来の技術では使用できなかつた欠陥メモリ
素子が使用可能になる。 〔実施例の説明〕 本発明を適用し得るシステムを第１図に示す。
メモリ１はメモリ・アドレス・レジスタ
（MAR）１２及びメモリ・データ・レジスタ
（MDR）１４を有する。MAR１２は擬似ランダ
ム発生器（PRG）１５からアドレスを受取り、
MDR１４はメモリ１から読出されたデータ又は
データ母線１７からメモリ１に書込まれるべきデ
ータを受取る。 データはスキヤナの如き入力装置１８から供給
される。入力装置１８は、例えば書類をスキヤン
して、その黒領域及び白領域に対応する２進信号
を発生する。メモリ１から読出されたデータは、
フアクシミリ・システムにおける受信装置の如き
利用装置１９へ送られる。利用装置１９は、デー
タの２進値に従つて白及び黒のドツトを生成する
インクジエツト・プリンタ又はレーザ・プリンタ
であつてもよい。システム全体の制御は、マイク
ロプロセツサの如き制御装置１１が受け持つ。 第１図のシステムの動作を簡単に説明すると、
まず入力装置１８が書類をスキヤンして、白領域
及び黒領域を表わす一連の２進信号を発生する。
これらの２進信号は、PRG１５からのアドレス
を用いてメモリ１に書込まれる。書類のスキヤン
が完了すると、書込みのときと同じ順序でメモリ
１からデータが読出され、利用装置１９へ送られ
る。利用装置１９は、受取つたデータから白領域
及び黒領域を復元することによつて、元の書類の
コピーを作成する。前述のように、第１図のシス
テムの代表例はフアクシミリ・システムである。
第１図中の極性切替え装置１６については後述す
る。 PRG１５は最大長PRG及び固定長PRGの何れ
であつてもよい。以下では、文献(7)に記載されて
いるようなシフトレジスタ型のPRGについて述
べることにする。第２図は３段構成の最大長
PRGシフトレジスタを示している。一般に、ｍ
段のPRGによつて発生される繰返しのない２進
系列の最大長は２^m−１に等しい。（−１）の項
は、全ゼロの系列が含まれないことを表わしてい
る。従つて、３段の場合の最大長は７である。最
初の段２１は初期設定信号によつてセツトされる
ものとする。出力は段２１から取出される。２番
目の段２２への入力はXOR（排他的オア）ゲー
ト２５から与えられ、３番目の段２３への入力は
最初の段２１から与えられる。初期設定信号によ
つて段２１に２進１がセツトされた状態において
は、シフトレジスタの内容は001になつている。
この状態で各段にシフトパルスが印加されると、
段２１にあつた２進１は段２３へシフトされる。
XORゲート２５は、段２１からの２進１及び段
２３からの２進０をモンジユロ２加算して段２２
へ２進１を与える。段２１には段２２からの２進
０がシフトされてくる。この結果、シフトレジス
タの内容は110になる。以下同様なシフトを繰返
すと、段２１から出力系列
101110010111001011100……が出力される。この
出力系列において繰返される最大長系列（Ｍ系
列）は1011100であり、擬似ランダム系列を構成
する７ビツトから成る。シフトレジスタの内容は
001(1)，110(6)，011(3)，111(7)，101(5)，100(4)及び
010(2)の順に変化し、001に戻る。シフトレジスタ
の内容が000になることはない。もしシフトレジ
スタの内容が000になると、シフトパルスをいく
ら印加しても、段２１から出力されるのは２進０
だけである。 Ｍ系列は、シフトレジスタの段間のすべてに
XORゲートを介するフイード・バツク接続を行
うことをしない限り発生される。例えば第２図に
おいて、XORゲート２５を段２１の入力に接続
すると、1110100のＭ系列が発生され、シフトレ
ジスタの値は１，５，７，６，３，４，２の順に
変化する。しかしながら、第２図のXORゲート
２５に加えて、別のXORゲートを段２１の入力
に接続すると、４ビツトの系列1100しか発生され
ず、シフトレジスタの値も１，７，４，３の順に
変化するだけである。一般に、フイードバツク・
タツプはｍビツトのすべての組合わせについて既
約多項式を計算するか、又はＺ変換を用いること
によつて得られる。 第２図はPRGの基本原理を示したもので、本
実施例においては、第３図に示されている19ビツ
トのPRGが使用される。即ち、第１図において
PRG１５からMAR１２へ供給されるアドレスは
19ビツトである。19ビツトのアドレスを用いる
と、メモリ１の記憶位置を524288まで指定でき
る。これは次のような仮定に基いている。 まず、書類の最大寸法を21.6cm（8.5インチ）×
35.6cm（14インチ）とし、その復元は単位長当り
240個のペルの解像度で行われるものとする。こ
こでの単位長は2.54cm（１インチ）である。従つ
て、単位面積当りのペル数は57600になり、書類
全体（１頁）を記憶するには、約680万個のペル
が必要である。１ワードを16ビツトとすると、こ
れは428400個のワードに相当する。従つて、メモ
リ１は少なくとも428400個のアドレス指定可能な
記憶位置を有していなければならない。これらの
記憶位置をアドレス指定するには少なくとも19個
のアドレス・ビツトが必要である。 上述のように、19ビツトのアドレスを用いる
と、記憶位置を524288までアドレス指定でき、こ
れは書類全体のワード数よりも多いから、PRG
は最大長（２¹⁹−１）より短い出力系列を有する
ものでよい。従つて、本発明においては、完全な
Ｍ系列発生器は不要であるが、Ｍ系列発生器の初
期設定を適切に行うことによつて必要な数のアド
レスだけを発生させるようにしてもよい。 またPRGにおいては、出力ビツトの重みを
MAR１２における重みに一致させる必要はな
い。従つて、ｍ段の各PRGはｍ〓種類のアドレ
ス系列を発生すると考えることができる。 複数のメモリ素子から成るメモリ・システムに
おいては、誤りは不規則に分布しているわけでは
なく、製造技術や欠陥の型に応じて誤りビツトの
大部分が１又は０になる傾向がみられる。以下、
このような誤りを支配的誤りと呼ぶことにする。
通常の書類においては、その面積の約90％が白で
あるから、支配的誤りの値を白ペルに対応させる
のが望ましい。そうすれば、支配的誤りの生じて
いる領域とその周りの領域とを混同するおそれが
少なくなる。更に、黒の背景上における白のドツ
トの認識度は、その逆の場合よりも低い。従つ
て、白ペルを支配的誤りの値によつて表わすこと
ができるように、第１図のシステムにメモリ・デ
ータを補数化するための手段を設けておくのが望
ましい。第１図の極性切替え装置１６がこれに相
当する。 制御装置１１からの極性信号によつて制御され
る極性切替え装置１６の詳細は第４図に示されて
いる。図示の様に、データ母線１７からの入力デ
ータはそのままMDR１４へ送られるが、メモリ
１からMDR１４へ読出された出力データはXOR
ゲート４５を通つてデータ母線１７へ送られる。
図には示していないが、XORゲート４５はデー
タのビツト毎に設ける必要がある。XORゲート
４５の他方の入力には極性信号が印加される。
XORゲード４５は、極性信号が０であればデー
タ・ビツトをそのまま通し、極性信号が１であれ
ば補数化する。 制御装置１１は支配的誤りの値に応じて１又は
０の極性信号を発生する。メモリ１における支配
的誤りの値は次のようにして調べられる。 まずメモリ１のすべての記憶位置に０が書込ま
れ、次いで読出されて、その中に生じている１つ
ビツトの数が計数される。次に、すべての記憶位
置に１が書込まれ、次いで読出されて、その中に
生じている０のビツトの数が計数される。１が黒
ペルを表わしていて、前者のビツト数が後者のビ
ツト数よりも多かつた場合には、制御装置は極性
信号を１に設定し、その反対の場合には極性信号
を０に設定する。１が白ペルを表わしている場合
には、極性信号の設定はこれとは反対にされる。
極性値の設定に使用される切替え入力を制御装置
１１に設けるようにしてもよい。 第１図のシステムに適する制御装置１１の詳細
は第５Ａ図乃至第５Ｄ図に示されている。第５Ａ
図は制御装置１１のシーケンス制御部を示したも
ので、２つのフリツプフロツプ５１及び５２（何
れもＤ型）を含む。フリツプフロツプ５１及び５
２の出力に接続された解読器５３は、フリツプフ
ロツプ５１及び５２の状態に応じた状態信号Ｓ０
〜Ｓ３を発生する。 制御装置内部で必要なクロツク信号は、第５Ｂ
図に示されているクロツク源５４から供給され
る。第５Ｂ図においては、クロツク信号は一対の
ANDゲート５５１及び５５２を介してアツプダ
ウン型のカウンタ５５に印加される。解読器５６
はカウンタ５５のカウント値を解読して、それが
０でなければＮ信号を発生し、カウント値がペル
を記憶するのに必要な記憶位置の数（本実施例で
は、428400）に達するとＭ信号を発生する。 制御装置１１は最初は状態Ｓ０にあり、第５Ａ
図のフリツプフロツプ５１及び５２は両方共リセ
ツトされている。解読器５３からのＳ０出力は第
５Ｂ図のカウンタ５５をリセツト状態に保ち、更
に第５Ｃ図のORゲート５７を通つてPRG１５へ
の初期設定信号として使用される。状態Ｓ０はア
イドル状態に相当する。 第５Ａ図のスイツチＳが閉じられると、AND
ゲート５２１へ有効化信号が印加される。このと
きANDゲート５２１にはフリツプフロツプ５１
及び５２のリセツト出力B′及びA′が印加されて
いるから、ANDゲート５２１はこれらの入力に
よつて条件付けられる。この結果、フリツプフロ
ツプ５２が次のクロツク信号の発生に伴つてセツ
トされ、ANDゲート５２１を無効化すると共
に、状態をＳ１に切替える。このとき、ANDゲ
ート５２１に代つてANDゲート５２２がフリツ
プフロツプ５１のリセツト出力B′及びフリツプフ
ロツプ５２のセツト出力Ａによつて条件付けら
れ、フリツプフロツプ５２にＤ入力を供給するの
で、フリツプフロツプ５２はセツト状態に保たれ
る。 状態Ｓ１においては、第５Ｄ図に示されている
ANDゲート５８からの同期入力信号によつて入
力装置１８が制御される。ANDゲート５８は解
読器５３からのＳ１出力及びクロツク源５４から
のクロツク信号によつて条件付けられ、入力装置
１８からメモリ１への書込みを行わせる。解読器
５３のＳ１出力は第５Ｂ図のANDゲート５５１
にも印加されて、カウンタ５５をカウント・アツ
プさせる。更に状態Ｓ１においては、解読器５３
のＳ１出力を通すORゲート５０１及びANDゲー
ト５０の働きによつてPRG１５へシフト信号が
送られ、PRG１５の各段へ印加される（第２図
及び第３図参照）。制御装置１１は、第５Ｂ図の
解読器５６がＭ信号を発生するまで、即ちカウン
タ５５のカウント値が428400に達するまで、状態
Ｓ１に留まる。 フリツプフロツプ５２がセツトされている状態
で解読器５６がＭ信号を発生すると、ANDゲー
ト５１１が条件付けられ、次のクロツク信号の発
生に伴つてフリツプフロツプ５１をセツトする。
この結果、制御装置１１は状態Ｓ３に入る。これ
は第５Ｃ図のORゲート５７を介してPRG１５を
再初期設定するための過渡状態であつて、１クロ
ツク・サイクルの間しか続かない。 フリツプフロツプ５１がセツトされるとそのリ
セツト出力B′が０になるため、ANDゲート５２
２は最早条件付けられず、従つて次のクロツク信
号の発生に伴つてフリツプフロツプ５２がリセツ
トされる。この結果、制御装置１１は状態Ｓ２に
入る。 状態Ｓ２においては、第５Ｄ図のANDゲート
５９がクロツク信号及び解読器５３のＳ２出力に
より条件付けられて、利用装置１９を制御する。
解読器５３のＳ２出力は第５Ｃ図のORゲート５
０１にも供給されてANDゲート５０を条件付
け、状態Ｓ３の間に再初期設定されたPRG１５
から書込みのときと同じアドレス系列を発生させ
る。この間、カウンタ５５は同じくＳ２出力によ
つて条件付けられるANDゲート５５２の出力に
よりカウント・ダウンされる。解読器５６はカウ
ント値が０にならない限りＮ信号を発生してお
り、従つてこの間ANDゲート５１２がＮ信号及
びフリツプフロツプ５１のセツト出力Ｂによつて
条件付けられているので、フリツプフロツプ５１
はセツト状態に保たれる。カウンタ５５のカウン
ト値が０になるとANDゲート５１２が無効化さ
れ、従つて次のクロツク信号の発生に伴つてフリ
ツプフロツプ５１がリセツトされる。この結果、
制御装置１１はアイドル状態Ｓ０に戻る。 上述の動作シーケンスはスイツチＳを再び閉じ
ることによつて繰返される。制御装置１１の機能
が第５Ａ図乃至第５Ｄ図に示したようなハードウ
エアによつて実現される場合には、前述の極性信
号は操作員によつて設定されるスイツチを介して
供給されることになろう。 第１図のシステムにおいては、制御装置１１が
なすべきシーケンス制御は実際にはもつと複雑で
あり、更にシステムの変更や拡張の可能性を考え
ると、制御装置１１としてはハードウエア回路の
代りにマイクロプロセツサを用いる方が望まし
い。

【図面の簡単な説明】

第１図は本発明を適用し得るシステムの一例を
示すブロツク図、第２図は３段構成のPRGの回
路図、第３図は第１図のシステムで使用される
PRG１５の回路図、第４図は極性切替え装置１
６の回路図、第５Ａ図、第５Ｂ図、第５Ｃ図及び
第５Ｄ図は制御装置１１の回路図である。

Claims (1)

1. 【特許請求の範囲】 １ 散発的な誤りを無視し得るフオルト・トレラ
   ント型の装置で使用されるメモリ・システムにし
   て、 初期設定された後にランダム・アドレスを順次
   に発生するランダム・アドレス発生手段と、 前記ランダム・アドレスによつてアドレス指定
   される複数の記憶位置を有するメモリと、 前記ランダム・アドレスの発生が所定数に達す
   ると前記ランダム・アドレス発生手段を初期設定
   して前記ランダム・アドレスを再発生させる制御
   手段とを備えてなるメモリ・システム。 ２ 前記メモリから読出されたデータ全体が前記
   メモリにおける支配的誤りの型に応じて反転され
   る特許請求の範囲第１項記載のメモリ・システ
   ム。