(57)【要約】ＤＲＡＭチップの障害に関連するエラー訂正およびエラー検出と、特に適合されたサーバメモリサブシステムとを提供する。それは、１２８データビットワードおよび１６チェックビット（図５、５４）の符号ワードにおいて構成される×４ビットＤＲＡＭ装置を用いる。これらの１６チェックビット（図５、５４）は、ファミリ内の（すなわち、×４ＤＲＡＭにおける）４ビット隣接エラー訂正と、１２８ビットワード全体にわたる２ビット非隣接エラー検出とが可能な、ならびにワードにわたる１ビット訂正が可能な符号を提供するような方法で生成される。各装置はビットの別個のファミリとして考慮され得、２つ以上のファミリにおいて発生するエラーは訂正不可能であるが、２つのファミリの各々における１つのビットのみがエラーである場合には検出され得る。シンドローム生成および再生成は、特定の大きな符号ワードとともに用いられる。シンドロームをデコードし、これを再生成されたシンドロームと照らし合わせることにより、記載される特徴を提供するのに十分なデータがもたらされる。
2005508548.tif 000002
【特許請求の範囲】
【請求項１】
１２８ビットの第１のデータワードにおいていずれかの単一の４ビットＲＡＭからデータにおける１５の起こり得るファミリのビットエラーをすべて検出かつ訂正し、さらに、２ビットの非ファミリのエラーをすべて検出し、前記第１の１２８ビットワードにおける訂正不可能なマルチビットエラーを検出するための装置であって、前記第１の１２８ビットワードはコンピュータシステム内のＲＡＭメモリにおいて記憶可能な、かつそこから検索可能なデータワードであり、前記コンピュータシステムは、前記第１のデータワードを前記ＲＡＭメモリに送るための前記メモリへの入力回路と、前記ＲＡＭメモリからの検索された１２８ビットデータワードを記憶装置から検索するための出力回路とを有し、前記検索された１２８ビットデータワードは、エラーが発生しない場合、前記第１のデータワードに等しくなり、前記装置はさらに、
前記入力回路に関連付けられるチェックビット発生器を含み、このチェックビット発生器は、予め定められた態様で前記１２８ビットデータワードから生成された１６チェックビットを生成し、かつ、記憶されたチェックビットとして前記１２８ビットデータワードに関連付けられる記憶装置のために前記生成された１６チェックビットを前記１２８ビットデータワードとともに前記ＲＡＭメモリに送るためのものであり、前記装置はさらに、
前記出力回路に関連付けられるチェックビット再発生器を含み、このチェックビット再発生器は、前記予め定められた態様で前記検索された１２８ビットデータワードから再生成された１６チェックビットを生成するためのものであり、前記装置はさらに、
前記再生成された１６チェックビットから１６シンドロームビットを生成するためのシンドローム発生器を含み、前記再生成された１６チェックビットの各々は、前記生成されたチェックビットのうち１つに加えられるモジュラ２であり、これにより１６ビットシンドロームを作り出し、前記装置はさらに、
ノーエラー信号、訂正可能なデータ信号および訂正可能なチェックビット信号を生成するためのシンドロームデコードおよびコンパレータ回路を含み、前記訂正可能なデータ信号は、シンドロームデコード回路を介して前記１６ビットシンドロームをデコードすることにより訂正が必要かどうかを決定することにより生成され、前記訂正可能なチェックビット信号は、前記生成された１６チェックビットのために訂正が必要かどうかを決定することにより生成され、前記ノーエラー信号は、前記シンドローム信号値が予め定められた値である場合に生成される、装置。
【請求項２】
マルチビット検出不能（ＭＵＥ）エラー信号生成回路をさらに含み、このマルチビット検出不能（ＭＵＥ）エラー信号生成回路は、前記ノーエラー信号がエラーを示し、前記チェックビットエラー信号または前記データエラー信号がまたエラーがないことを示す場合にＭＵＥ信号を生成するためのものである、請求項１に記載の装置。
【請求項３】
前記ノーエラー信号を生成する前記予め定められたシンドローム信号値は０である、請求項１に記載の装置。
【請求項４】
前記ＲＡＭメモリは、前記１６の生成されたチェックビットとともに、前記第１のデータワードを２つの７２ビットＤＲＡＭに記憶する、請求項１に記載の装置。
【請求項５】
前記チェックビット生成回路は、前記第１のデータワードからの入力のＸＯＲツリーであり、前記入力は１６のブランチに接続され、各ブランチは１ビットの出力を生成し、１６のブランチすべてからの１ビットの前記出力は、前記生成された１６チェックビットである、請求項１に記載の装置。
【請求項６】
前記各ブランチは、前記第１のデータワードから前記入力のうちいくつかだけを受信するよう接続され、前記第１のデータワードのうちどのビットが入力としてどのブランチに
供給されるかは、１６ビットごとに１２８の予め定められたファミリのパターン符号によって決定される、請求項５に記載の装置。
【請求項７】
前記予め定められたファミリのパターン符号は図２Ａおよび図２Ｂに述べられる、請求項６に記載の装置。
【請求項８】
予め定められた符号化されたビットパターンは、前記１６のブランチの各々に接続される前記データ入力間におけるすべてのリンクを説明し、前記予め定められた符号化されたビットパターンは、図２Ａ〜図２Ｄに述べられるビットパターンに等しい、請求項５に記載の装置。
【請求項９】
前記シンドローム発生器回路は、データ入力のそのパターンにおいて、前記シンドローム発生器回路へのデータ入力の前記パターンが前記ＲＡＭメモリに記憶されているデータではなく前記ＲＡＭメモリに記憶されるデータビットからのデータ入力を受信する以外は、前記チェックビット生成回路に等しく、さらに、各々の１６チェックビットのうち１つは、前記シンドローム発生器回路の１６のブランチの各々とＸＯＲ演算される、請求項９に記載の装置。
【請求項１０】
前記シンドローム発生器回路出力は、データビットのいずれかのファミリがエラーであるか、前記示されたファミリにおけるそれらのビットのうちどれがエラーであるか、前記シンドローム発生器出力が前記装置のシンドロームデコード回路を通過する際に追加のエラーがあるかどうかを示す情報を提供する、請求項９に記載の装置。
【請求項１１】
シンドロームデコード回路をさらに含み、前記シンドロームデコード回路は、前記シンドローム発生器から出力を受取り、これを、前記データワードのどのビットがエラーであるかを示す信号にデコードするためのものであり、前記シンドロームデコード回路はさらに、
前記１２８ビットデータワードのためにデコードするよう前記シンドロームを受信するためのゲートの第１の並列ネットワークを含み、前記第１の並列ネットワークは４８０の部分を有し、各部分は前記シンドロームの１６ビットをすべて受取り、このような部分のファミリのグループにおける他のこのような３つの部分とともに、前記データワードの４つのファミリのビットの各々に対してエラーがあるかどうかを示し、前記シンドロームデコード回路はさらに、
前記シンドロームを受取るためのゲートの第２の並列ネットワークを含み、前記ネットワークは６０の部分を有し、各部分は前記シンドロームの１６ビットをすべて受取り、このような部分のファミリのグループにおける他のこのような３つの部分とともに、前記データワードに関連するチェックビットの４つのファミリのビットの各々に対してエラーがあるかどうかを示す、請求項１に記載の装置。
【請求項１２】
前記第２の並列ネットワークは、前記並列ネットワークのビットのいずかがエラーを示す場合、単一のエラービット出力を生成する、請求項１１に記載の装置。
【請求項１３】
１２８ビットの第１のデータワードにおいていずれかの単一の４ビットＲＡＭからデータにおける１５の起こり得るファミリのビットエラーをすべて検出かつ訂正し、さらに２ビットの非ファミリのエラーをすべて検出し、前記第１の１２８ビットワードにおける訂正不可能なマルチビットエラーを検出するための装置であって、前記第１の１２８ビットワードはコンピュータシステム内のＲＡＭメモリに記憶可能なデータワードであり、このコンピュータシステムは、前記ＲＡＭメモリに前記１２８ビットデータワードを送る際に１６チェックビット（図５、５４）を前記１２８ビットデータワード（５３）から生成し、前記１２８ビットデータワードおよび前記１６ビットチェックビットデータはともに、そこから一緒に検索可能であり、前記コンピュータシステムは、前記第１のデータワード
を前記ＲＡＭメモリに送るための前記メモリへの入力回路と、前記ＲＡＭメモリからの検索された１２８ビットデータワードを記憶装置から検索するための出力回路とを有し、前記検索された１２８ビットデータワードは、エラーが発生しない場合、前記第１のデータワードに等しくなり、前記装置はさらに、
前記ＲＡＭメモリから検索された前記１６チェックビットと前記１２８ビットデータワードとから１６シンドロームビットを生成するためのシンドローム発生器（図６、６０Ａおよび６０Ｂ）と、
ノーエラー信号、訂正可能なデータ信号および訂正可能なチェックビット信号を生成するためのシンドロームデコード（８１）およびコンパレータ（８２）回路とを含み、前記訂正可能なデータ信号は、シンドロームデコード回路を介して前記１６ビットシンドロームをデコードすることにより訂正が必要かどうかを決定することにより生成され、前記訂正可能なチェックビット信号は、前記生成された１６チェックビットのために訂正が必要かどうかを決定することにより生成され、前記ノーエラー信号は、前記シンドローム信号値が予め定められた値である場合に生成される、装置。
【請求項１４】
１２８ビットの第１のデータワードにおいていずれかの単一の４ビットＲＡＭからデータにおける１５の起こり得るファミリのビットエラーをすべて検出かつ訂正し、さらに、２ビットの非ファミリのエラーをすべて検出し、前記第１の１２８ビットワードにおける訂正不可能なマルチビットエラーを検出するための装置であって、前記第１の１２８ビットワードはコンピュータシステム内のＲＡＭメモリに記憶可能なデータワードであり、このコンピュータシステムは、前記ＲＡＭメモリに前記１２８ビットデータワードを送る際に前記１２８ビットデータワードから１６チェックビットを生成し、前記１２８ビットデータワードおよび前記１６ビットチェックビットデータはともにそこから一緒に検索可能であり、前記コンピュータシステムは、前記ＲＡＭメモリに前記第１のデータワードを送るための前記メモリへの入力回路と、前記ＲＡＭメモリからの検索された１２８ビットデータワードを記憶装置から検索するための出力回路とを有し、前記検索された１２８ビットデータワードは、エラーが発生しない場合、前記第１のデータワードと等しくなり、前記装置はさらに、
前記出力回路に関連付けられるチェックビット再発生器を含み、このチェックビット再発生器は、前記予め定められた態様で前記検索された１２８ビットデータワードから再生成された１６チェックビットを生成するためのものであり、前記装置はさらに、
前記再生成された１６チェックビットから１６シンドロームビットを生成するためのシンドローム発生器を含み、前記再生成された１６チェックビットの各々は前記生成されたチェックビットのうち１つに加えられるモジュラ２であり、これにより１６ビットシンドロームを作り出し、前記装置はさらに、
ノーエラー信号、訂正可能なデータ信号および訂正可能なチェックビット信号を生成するためのシンドロームデコードおよびコンパレータ回路を含み、前記訂正可能なデータ信号は、シンドロームデコード回路を介して前記１６ビットシンドロームをデコードすることにより訂正が必要かどうかを決定することにより生成され、前記訂正可能なチェックビット信号は、前記生成された１６チェックビットのために訂正が必要かどうかを決定することにより生成され、前記ノーエラー信号は、前記シンドローム信号値が予め定められた値である場合に生成される、装置。
【請求項１５】
１２８ビットの第１のデータワードにおいていずれかの単一の４ビットＲＡＭファミリからデータにおける１５の起こり得るファミリのビットエラーをすべて検出かつ訂正し、さらに、２ビットの非ファミリのエラーをすべて検出し、前記第１の１２８ビットワードにおける訂正不可能なマルチビットエラーを検出するための方法であって、前記第１の１２８ビットワードはコンピュータシステム内のＲＡＭメモリに記憶可能な、かつそこから検索可能なデータワードであり、前記方法を実行するための前記コンピュータシステムは、前記第１のデータワードを前記ＲＡＭメモリに送るための前記メモリへの入力回路と、
前記ＲＡＭメモリからの検索された１２８ビットデータワードを記憶装置から検索するための出力回路とを有し、前記検索された１２８ビットデータワードは、エラーが発生しない場合、前記第１のデータワードに等しくなり、前記方法はさらに、
ａ）  前記第１のデータワードが前記ＲＡＭメモリに記憶されるべきときにいつでも前記第１のデータワードに１６ビットチェックビット出力を与え、前記第１のデータワードとともに前記与えられた１６ビットチェックビット出力を記憶するステップと、
ｂ）  前記記憶された１６ビットチェックビット出力とともに前記第１のデータワードを検索するステップと、
ｃ）  前記記憶された１６ビットチェックビット出力から１６ビットシンドロームを作り出すステップと、
ｄ）  前記１６ビットシンドロームが予め定められた値であるかどうかと、それが前記予め定められた値であるかどうかとを判断し、「ノーエラー」信号を生成するステップと、
ｅ）  前記１６ビットシンドロームをデコードして、前記検索された第１のデータワードの前記１２８ビットがあれば、どれが訂正可能なエラーであるかを示し、訂正可能なエラーであるものがあれば、「訂正可能なエラー」信号と、前記検索された第１のデータワードの前記１２８ビットのどれが訂正可能なエラーであるかを示す信号とを生成するステップと、
ｆ）  訂正可能なエラーをいずれも訂正するステップと、
ｇ）  （ｉ）前記訂正可能なエラー信号と前記ノーエラー信号とが一致しない場合、または（ii）前記訂正可能なＥＣＣエラー信号と前記ノーエラー信号とが一致しない場合、「訂正不可能なエラー」信号を生成し、そうでない場合、「良好なデータ」信号を生成するステップとを含む、方法。
【請求項１６】
前記第１のデータワードの前記１２８ビットのどれが訂正可能なエラーであるかの前記表示を用いて、別のシステムに潜在的な不良チップについて知らせるステップをさらに含む、請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の背景
１．発明の分野
この発明は、特にメモリ素子内のコンピュータシステム内で発生し得るエラーを訂正しかつ検出することに関し、より特定的には、ファミリの１〜４ビット訂正で補われる１ビット訂正と２ビットワード幅の検出とが好ましいシステムに関し、さらにより特定的には、４ビットＲＡＭ装置に記憶される１２８ビットデータワードに関する。
【背景技術】
【０００２】
２．背景情報
メモリをエラー訂正符号（ＥＣＣ）空間の専用にすると費用がかかるので、完璧なエラー訂正および検出に対する要求には妥協が必要とされる。持続性のある商業用の実現可能性については、特に最大規模のコンピュータシステムと、エラー検出および訂正において適切な妥協を伴う、一般的にデータ記憶システムを用いる他のＲＡＭとを依然として備えなければならない。単一のマルチビットＲＡＭ装置に障害を起こさせ、その障害を動的に訂正する能力を与えることと、また、４ビットＲＡＭファミリ内の１、２、３または４ビットに同じ能力を与えることと、さらにワードのどこにでもある非ファミリのエラーのいずれかの２ビットの検出を提供することとにより、メモリサブシステムの信頼性をより高める何らかのＥＣＣを用いる方法が選ばれている。この能力により、実行中にすべての１ビットおよびファミリ内の２、３または４ビットエラーが訂正され、訂正されたデータワードが作り出され、他のいずれかのエラーまたはエラータイプを備えた固定されない（固定不能な）破損したそれらのデータワードとして識別される。これらは起こる可能性が最も高いエラーであるので、我々の選択した妥協が有用であると考えられる。
【０００３】
ＲＡＭ装置密度およびメモリサブシステム帯域幅の要件は時間が経つにつれて増すので、マルチデータビットＲＡＭ装置を用いてそれらの要件を満たそうとするメモリサブシステムの設計者にとってはより困難となった。しかしながら、そうすることで、過去の標準的な１ビット訂正／２ビット検出（ＳＢＣ／ＤＢＤ）を利用するメモリサブシステムの信頼性が損なわれる。ＲＡＭ装置の幾何学的構造がより小さくなり、装置の障害率が増すと、データワードは障害の影響をより受けやすくなり、これにより装置における２つ以上のビットに影響が及ぶ。さらに、１ビットエラーが依然としてＲＡＭ装置の最も中心的な障害モードであるにもかかわらず、幾何学的構造の小型化およびこれらの装置の信頼性特徴のために、ソフトの１ビット障害率は増えつつある。したがって、複数の装置から２ビットエラーを少なくとも検出することがより重要となり、このため、データ破損を検出しかつ問題なくこれを処理することができる。この発明はその保護を提供する。実質的に費用を増大させずに向上したエラー検出および向上したエラー訂正を提供することが、冗長なエラー訂正符号（ＥＣＣ）ビット対情報データビットの増加率のために、この発明の付加的な目標となる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
過去において、エラー訂正および検出に対処する２つの主要な方法があった。主流な一方法はデータワードにわたって複数のＳＢＣ／ＤＢＤフィールドを作り出し、ＲＡＭの各ビットを別個のＳＢＣ／ＤＢＤフィールドに進ませることであった。この方法に伴う問題点は、余分なチェックビットをサポートするためにＲＡＭの費用が余分にかかることである。たとえば、保護が必要な１２８ビットデータワードを有し、この１２８ビットデータワードが×４ＲＡＭ装置を用いて実現された場合、提案された発明と同じ障害適用範囲を提供するのに８チェックビットを４グループ要することとなる。これらのチェックビットは（８）×４ＲＡＭ装置において実現されることとなる。我々の発明は、×４装置を用いる場合、３２ではなく、１６チェックビットまたは４ＲＡＭ装置だけでよい。極めて大容量のメモリについては、その余分のＲＡＭの追加費用は、商業的には法外に高くはないとしてもかなり高額である。
【０００５】
別の方法では２つのＥＣＣフィールドを用い、各ＥＣＣフィールドが２ビット「隣接」訂正を提供する。（当該技術における「隣接」という語は、所与のＲＡＭ装置内のビットのファミリ内であること（すなわち、ビットに属する）ことを意味し、必ずしもビットが互いに「隣り合う」ことを意味するわけではない。）この方法はまた、８チェックビットを２グループ実現するために４つのＲＡＭ装置を必要とするので、同額の費用がかかることとなる。しかしながら、各々のＥＣＣフィールド内では、複数の装置にわたる２ビットエラーがすべて検出されるわけではない。したがって、費用は同じであるが、同じ信頼性特徴を有するわけではない。
【０００６】
マルチビット隣接エラー訂正またはチップキル（Chip Kill）は、２ビット非隣接エラー検出と組合わされる。これは、単一のＲＡＭ装置内の障害を検出かつ訂正し、さらに１２８ビットワード内においていずれかの２つのＲＡＭ装置におけるいずれかの１ビットのソフトまたはハードのエラーに起因する障害を検出する能力を伴う。これを達成した解決策は他にはなかった。我々の発明では、（シンドロームデコードのための）特定のＲＡＭエラー定義テーブルとともに固有のＥＣＣテーブルが用いられる。これらはいずれも先行技術にはない。
【０００７】
先行技術の発明は、１ビットエラー訂正およびマルチビット隣接訂正を、少なくとも少数の付加的なＥＣＣタイプのビットとではなく、２ビット非隣接エラー訂正と組合せるエラー符号訂正特徴に備わる信頼性のレベルを考慮に入れていなかった（ＥＣＣは、エラー訂正符号を意味し、当該技術においては一般的な短縮形である）。
【０００８】
こうして、メモリの費用が低くかつ信頼性の高いエラー訂正および検出が必要とされ、ファミリのエラー訂正を提供することにより、単一のＤＲＡＭまたはＲＡＭ装置内で起こり、ワード内で起こる可能性が最も高いマルチビットエラーの捕捉が可能となる。したがって、問題をこのように考慮することにより、起こり得るすべてのエラーを訂正しようとするのではなく、以下に述べられるように発明的で低費用のエラー検出および訂正システムを設計してきた。
【０００９】
当該技術において類似のシステムがあったが、これらは我々の発明の利点または要件をすべて有するわけではない。おそらく、最も類似する引用は、チェン（Chen）他に発行された米国特許（第６，０１８，８１７号）にあり、その全体がこの引用によりこの明細書中に援用される。同じサイズの（×４ビット）ＲＡＭ装置を用いると、チェンの第８１７号の引用では、４ビット幅のＲＡＭを用いる場合、各７２データビットに対して１２ＥＣＣビットが必要とされるが、我々の発明では、４ビット幅のＲＡＭを用い、１２８データビットに対してＥＣＣの１６ビットだけで十分な信頼性の要求に対処する。（ＲＡＭは総称であり、ＤＲＡＭを含み、我々の好ましい実現例はＤＲＡＭチップ上で展開されたが、他のＲＡＭ装置を用いてもよい。）さらに、チェンの第８１７号は、×８ＲＡＭ装置を用いる場合、７２データビット当たり１６ＥＣＣビットを必要とする。チェンの第８１７号のどちらの実施例と比べても、我々の発明はよりいっそうのエラー検査をもたらし、さらにことによると、よりいっそうのエラー訂正をもたらすようであるが、ＥＣＣビットをあまり必要としないようである。
【００１０】
１２ＥＣＣビット符号をサポートすべき特定の符号は、チェンに対する米国特許第５，７５７，８２３号に記載され（、この引用によりこの明細書中にも援用され）ているようである。チェンの第８２３号に関して付加的な第３の節約に関連する費用の節約は、当業者によって理解されるだろう。チェンが１段目の４０〜５２行目で述べるように、メインメモリに対するメモリ関与における５％の節約でさえもコンピュータシステムにとっては極めて重要である。
【００１１】
対象となっている追加の特許はブレーク（Blake）他の米国特許第５，６８２，３９４号を含み、これは不能化特徴を示し、さらに、この引用によりこの明細書中に援用される。
【００１２】
最後にアドブー（Adboo）他の第５，４９０，１５５号がまた、引用によりこの明細書中に援用され、×４ＤＲＡＭエラーを訂正するためのシステムを記載し、アドブーは我々の発明と同様に１２８ビットデータワードに対して１６チェックビットを用いる。しかしながら、アドブーは、チェックビットが各６４ビットに対して２つの同一のパリティツリーによって生成されることを必要とし、各パリティツリーは同数の入力を有し、出力は、単一のＤＲＡＭまたはＲＡＭ装置内において最大で４ビットエラーまで訂正するよう対にされる。おそらくより重要なことには、アドブーはワードにおける１つの１ビットエラー、ワードにおける１つの隣接２ビットエラー、またはワードにおける隣接４ビットエラーを検出しかつ訂正することしかできない。アドブーは、２つの無関係の１ビットエラー、または最大で４ビットエラーまでを有するファミリのグループ以外の１ビットエラーを検出することができないが、我々の発明では可能である。アドブーの図９Ａを参照すると明らかに分かるように、２チェックビットにおけるエラー（または、実際には無関係な２ビットエラーの多く）は無関係または非隣接であるが、訂正不可能かつ検出不可能なエラーをもたらす。アドブーのこの欠点の例として、ビットＣ４に対する符号が０００１であり、Ｃ７に対する符号が１０００であることに留意されたい。これらの２つの値をＸＯＲ演算することにより結果が１００１となり、これはビット０がエラーであることを示す。こうして、Ｃ４およびＣ７がともにエラーである場合、シンドロームは、ビット０がエラーであり、このような事の発生が稀な事象であり得るとしても、２つの１ビットエラーを見落としていたので、容認できない状況であることを示すだろう。
【００１３】
したがって、コンピュータシステムメモリの信頼性を改善し、かつ最低限のデータの量でそうするために、より強力なエラーの検出および訂正が必要とされる。エラー訂正システムおよびチップキルタイプシステムは、２ビットの非ファミリのエラー検出とともに、この技術的な問題に対して商業的に最も有用な解決策を提供するだろう。
【００１４】
概要および以下の詳細な説明における図面に関連して我々の発明を記載するが、その範囲は添付の特許請求の範囲によってのみ限定される。
【課題を解決するための手段】
【００１５】
発明の概要
極めて複雑な符号シーケンスが発見されており、これはビットファミリ内のマルチビットエラーを訂正する機会を与えるが、同時に、そのビットファミリ以外の付加的な１ビットエラーすべてを検出する機会も与え、さらに、他の多くの訂正不可能なマルチビットエラーを検出する機会を与える。この符号は１６「チェック」またはＥＣＣビットのみを必要とし、これらは、１２８ビットデータワードに対してこの発明の符号を用いることにより、１２８ビットのうち示される各々をコードによって示される１６チェックビットの各ＸＯＲツリーに供給することによって生成される。同じ発生器（または同じ符号によって構成される同一のもの）は、１２８ビットメモリワードがメインメモリから読出され、かつ、保存されたチェックビットを再発生器の出力とＸＯＲ演算することにより、最初に生成されたチェックビットとの比較がなされてシンドローム符号を生成する際に、１６チェックビットを再生成する。（これは、１２８データビットを同じＸＯＲツリー構成に通し、かつツリーの各ブランチに対してチェックビットを加えるのと数学的に同じことであり、実際にはより短いサイクル時間が必要とされるので、シンドロームを作り出す方が好ましい。）結果として生じるシンドロームはデコードされ、再び符号シーケンスを用いてデコードゲートを構成して、すべての訂正可能なエラー（それらのうち５４０）を識別し、訂正不可能なエラーのほとんどの状態を識別し、エラーが検出されるが訂正不可能である場合に検出可能なエラーまたは破損したデータがない場合、良好なデータを示す。
【００１６】
符号シーケンスは、ＥＣＣ発生器および再発生器／シンドローム発生器がともに訂正されて符号の変更に適合され、その上シンドロームデコードがシフトを補償するよう修正される限り、ビットのＥＣＣ値を他のビットにシフトすることにより修正することが可能である。
【発明を実施するための最良の形態】
【００１７】
好ましい実施例の詳細な説明
好ましい構成要素の概念および部分を最初に説明し、次にこの発明の好ましい機能を説明する。
【００１８】
まず図１を参照すると、５つの列を有するＲＡＭエラー定義テーブル１０が示され、その最初の４つ（Ｒ）は、問題にされている各ＲＡＭに対するＤＲＡＭまたはＲＡＭビット数を示す。これらの４つのビットはファミリビットまたはファミリであると表わされる。というのも、これらは単一のＲＡＭ装置内にあるからである。テキストによっては、これは「隣接」と称されるが、１つのＲＡＭにおける最後のビットは次のＲＡＭにおける最初のビットに隣接するとも考えられ得るので、その用語は紛らわしいものであることがわかる。したがって、この特許出願内で述べる目的のために、ＤＲＡＭまたはＲＡＭ装置内のビットをすべてファミリのビットと考え、外部にあるものはファミリではないかまたは同じファミリの部分ではないものとする。後の参照のために、図１のテーブル１０の行０〜１６を明示する。
【００１９】
テーブル１０は、ＲＡＭ  Ｘ、４ビットＲＡＭまたはＸ４  ＲＡＭ装置におけるビットのファミリの各々に対して、領域Ｓにおいて起こり得るすべてのエラー状態（１６あり、これらはエラーを含まない）を説明する。（１２８ビットワードにおいては、３２個のこのような装置、すなわちＲＡＭ０〜３１があり、我々の好ましい発明のシステムにおいては、付加的な４つの装置が存在することとなり、このようなＲＡＭ  Ｘ装置が１２８ビットデータ＋１６ビットのＥＣＣワードにつき全体で３６個となる。）列ＥＴＣは、各エラータイプに対するエラータイプ符号を示す。したがって、Ｓ３は、ＲＡＭ  Ｘのビット３にエラーがあり、ファミリには他にエラーがないことを示す。Ｄ２は、１つの起こり得る２ビットのファミリ内のエラー状態を示し、この場合ＲＡＭ  Ｘのビット２および１がエラーである。Ｔは、ＲＡＭ  Ｘに対する４つの起こり得る３ビットのファミリ内のエラー状態のうち１つを示し、Ｑ（Ｑ０）は、４つのビットすべてがエラーであることを示す。
【００２０】
テーブル１０における１の構成が任意であり、かつ、すべての起こり得るエラーを識別するがこれらを別々の位置に有する固有のテーブルが結果として生じるように当業者が１５個の１を異なる位置に配置することができるであろうことに留意されたい。このようなテーブルがいずれも、所望の場合、この発明の範囲から逸脱することなく、図１のこの好ましいテーブルの代わりに用いられてもよい。たとえば、最初の４行における１の対角線は、列０、行０が１を有し、列１、行１が１を有し、列２、行２が１を有し、列３、行３が１を有し、テーブルの残りの部分が同じままであり得るように反転され得、こうして、この発明の別の実現可能な変形例を作り出す。これは、この開示の残りの部分を参照すると十分に理解されるだろう。このテーブルは、ビットの各ファミリ（すなわち、各４ビットＲＡＭ装置）を評価する際に検討される。
【００２１】
図２Ａおよび図２Ｂには、各ビット０〜１２７に対するビットＥＣＣ０〜１５の信号状態の各々を特定する単一のＥＣＣテーブル２０が示される。概要部分で述べたように、ビットのファミリを別の位置にシフトすることにより、またはファミリの多くを異なる位置にシフトすることによりこの発明を修正し得、このシフトされたテーブルに特定される符号に関連してこの発明の他の構成要素をシフトする場合、別の形でこの発明を再度作り出し得る。このことは、たとえば、ビット１２７〜１２４のファミリがビット７２〜７５より下となるようそれらのＥＣＣテーブル（各列１２７〜１２４に対して行ＥＣＣ０〜１５）がシフトされている場合、かつ、現在列７２〜７５より下にあるＥＣＣビットのビットパターンに対するＥＣＣテーブルがシフトされて１２４〜１２７より下のＥＣＣビットを置換える場合、この発明が依然として機能するだろうことを意味する。したがって、発見される符号は図２Ａ〜図２Ｄにおける表現に固有のものではないが、３２ファミリビット符号パターンのセットは、この発明がこの明細書中に詳細に記載されるように機能するよう想定するために、１６ビット符号ごとに１２８ビットを生成するよう忠実に再生成されなければならない。
【００２２】
図３Ａ〜図３Ｃは訂正可能なシンドローム符号のテーブルであり、これは、１６進で特定されるが１０進の形式で印字されているので、たとえば、（テーブル３０に示される）１２はＣhexまたは１１００2に等しい。こうして、テーブルにおける各数字は、ファミリ内の特定のエラーを示すのに必要なシンドローム符号の４ビットを特定する。チェックビット（３２〜３５）に対して４つのファミリがあるので、３６のファミリ（０〜３５）が存在する。１５の起こり得るエラー符号が左端の列において特定され、ファミリ（ＤＲＡＭ番号）が最上列に沿って特定される。こうして、０、９、２、７のシンドローム符号はファミリ０（ＲＡＭ  ０）におけるＴ３エラーを示し、これは、図１を参照すると、ビット０、１および２がエラーであることを意味する。こうして、このテーブルは、この発明の好ましい実施例が処理することのできる５４０の訂正可能なエラーを特定し、かつ、それらがこの発明の好ましい形態に従って生成されるシンドロームにいかに基づいているかを特定する。（「０」と示されるファミリ（または列）がデータワードのビット１２７〜１２４に対応することに留意されたい。）
図４には、２つの関連した図部分４０および４１におけるデータフローが示される。図４０はＤＲＡＭまたはＲＡＭ装置３１へのデータの経路を示し、１６チェックビットがブロック４２において生成され、チェックビットおよびデータの最初の１２８ビットがともにライン４３および４４上でそれぞれメモリ素子に送られる。メモリに記憶された後にワードを検索するステップは、チェックビット再生成４５および比較４６と、作り出されるシンドロームに基づく、データワードおよびチェックビットにおける訂正可能なエラーに対するデコード４７および４８とともに仮のノーエラー信号の生成４９とを含む。１２８ビットデータワードは、（５４０のシンドローム符号のうち１つが生成されて、どのビットを訂正する必要があるかを特定する）データ訂正ブロック３５において（それがあり得る場合に）訂正される。さらに、エラー状態検出がブロック３６において実行され、これにより、エラーがあったことと、それが訂正可能（であり訂正されたか）または訂正不可能であったかどうかとを示すインジケータ信号が生成される。シンドロームは、所望の場合、どのビットが不良であるかを示すために報告され得る。
【００２３】
図５〜図８は、概要において図４から提供されるこのプロセスをより詳細に例示する。
【００２４】
好ましい実施例は、２つの標準的な７２ビットＤＩＭＭを用いるメモリで作動する。（ＤＩＭＭはデュアルインライン・メモリ・モジュールに対する一般用語であり、現在販売されているメモリの一般的な形態であり、ＤＩＭＭユニットにつき３６個の×４ＤＲＡＭを最も一般的に有する。）これらの一般的なＤＩＭＭは、１２８データビットおよび１６チェックビットが存在する１４４ビットワードを有するよう、簡単に実現される。標準的なＤＩＭＭを利用することによりシステムの費用が大いに削減され、この発明の価値が高められる。この２つのＤＩＭＭ構成のもと、１６チェックビットが、メモリに送り込まれるあらゆる１２８ビットワードに対して生成される。チェックビットは、ＲＡＭビットの特定のパターンにわたる計算された奇数パリティである。１６チェックビットは生成された後、図２Ａ〜図２Ｄのテーブル２０におけるエラー訂正符号テーブルを用いて、メモリに記憶される。テーブル２０は、好ましい実施例によって説明される形態で用いられるこの発明のＥＣＣ符号を示す。各ワードに関連付けられる１６チェックビットは、各データビット［１２７：０］に対する各ＥＣＣ行における「１」のセットにわたり奇数パリティを計算することによって生成される。（こうして、「テーブル」はパリティツリーにおいて実際に実現される。）
データワードを検索する際に、チェックビットを生成するプロセスが別の方法で繰返される。
【００２５】
チェックビット再生成は、ＲＡＭからの読出データビット［１２７：０］を用いて行なわれる。これらの再生成されたチェックビットは、記憶されたチェックビット、すなわちＲＡＭからのビット［１４３：１２８］と、ビットごとに比較される。ＸＯＲ関数を用いる比較により、１６ビットシンドローム符号がもたらされる。シンドローム符号がデコードされるときに１２８ビットデータワードにおけるどのビットまたはビットのファミリが訂正可能なエラーであり得るかが決定される。
【００２６】
ここで図５を参照すると、メモリに書込まれるべき１２８ビットワードを含む書込データを用いて、図２Ａ〜図２ＤのＥＣＣテーブルにおける値に基づいた所定の接続に従い、奇数パリティツリー５０を介して１６チェックビットを生成することに留意されたい。こうして、ツリー５０に対する第１のＸＯＲゲートブランチ５１については、図２Ａ〜図２Ｄの最上行で特定される１２８ビットデータワードのビット０、１、４、８など、ビット１０３までが、ＸＯＲゲート５１に供給されて、１６チェックビットの第１のチェックビット（ＥＣＣ）のための出力を生成する。ブランチは、１６ＥＣＣビットの各ビットに対してこの態様で構成される。単に発見的目的のためだけに、チェックビット０および１５をそれぞれ生成するＸＯＲゲート５１および５２を含むブランチが例示される。こうして、１２８ビット（０〜１２７）の入力ライン５３から、１６の出力ビットがライン５４上で生成される。これにより図４のブロック４２の機能が達成され、データと、図２Ａ〜図２Ｄのテーブルの符号を介してデータに対応する生成されたチェックビットとが、このとき、メモリに書込まれるよう準備される。（先述のように、図２Ａ〜図２Ｄの符号ワードは、符号のファミリをあちこちにシフトすることにより修正され得るが、依然としてこの発明の範囲内である。このチェック生成モジュールについては、効果は同じであるが好ましい実施例のうち１つとは形態が異なる符号を生成するこのようなシフトは、符号のスワップされた値に対応するツリーの１６のブランチへの入力の、その変化した分散に反映されることとなる。）すべての場合においては、生成された後のチェックビット符号は、この特定のメモリデータワードを記憶するために用いられるものに関連するＲＡＭメモリ素子に記憶されるべきであり、こういった訳で、記憶のために１ワードにつき１２８＋１６ビットが必要とされる。ファミリの制限のために、図３のシンドロームデコードチャートによって示されるように、×４ＤＲＡＭにビットを記憶することが好ましい。こうして、ビット１２７から０がＤＲＡＭ０から３１に４ビットごとに記憶される。さらに、１６ＥＣＣビットがＤＲＡＭ３２〜３５に記憶されるべきである。
【００２７】
メモリからワードを検索することが望まれる場合、プロセスは、この発明の好ましい実施例に従い、図６Ａ、図６Ｂ、図７および図８に関連して説明される部分を利用する。
【００２８】
図６Ａおよび図６Ｂには代替的な実施例が示される。図６Ａでは、処理がより速い可能性がある。というのも、図６Ａでは符号がすべて各シンドロームビットに対する単一のＸＯＲブランチを介して進むが、図６Ｂでは、記憶されたチェックビットに別個に対応するよう各ブランチに対するＸＯＲゲートが加えられるからである。数学的には、これらは同じであるが、図６Ａの変形例はゲート遅延がより少ないためにより高速であるはずである。さらに、図５におけるように、（ここでは、ライン６３Ａまたは６３Ｂ上でメモリ素子から入ってくる）１２８の入力ラインは、１６ビットを生成するようＸＯＲツリーの１６のブランチに分散される。図６Ａでは、これらのブランチの各々において、付加的な入力が、記憶されたチェックビット、すなわち分散されたＣ０〜Ｃ１５を用い、メモリからブランチ０〜１５にそれぞれ送られる。図６Ｂでは、ＸＯＲツリーブランチはＸＯＲによる付加的なルートを有し、これにより、各ブランチ６１Ｂ〜６２Ｂからの１２８ビットのうち割当てられたもののＸＯＲの結果を、ＸＯＲゲートＢ０〜Ｂ１５により、それぞれ、ＥＣＣの記憶された符号ビットＣ０〜Ｃ１５とＸＯＲ演算する。いずれにしても、このデータワードおよびチェックビット符号に対するシンドローム符号を出力として含む、１６ラインの出力ライン６４Ａおよび６４Ｂがある。
【００２９】
こうして、図６Ａおよび図６Ｂに図示されるように、チェックビットはＲＡＭから読出され、図２Ａ〜図２Ｄのこの発明のＥＣＣテーブルに従い、上述のようにパリティツリーを介して同じ１２８ビットデータワードから生成される１６ビットとＸＯＲ演算されて、１６ビットのシンドローム符号を生成する。さらに、読み手が、この明細書中における、シフトされたテーブルでの基本的な概念を用いることを考慮に入れる場合、すなわち図２Ａおよび図２Ｂのテーブルがシフトされる場合、１６のブランチへの入力ラインはテーブルシフトに従ってシフトされるべきである。
【００３０】
これらのシンドローム符号がテーブル２ａおよび２ｂに図示され、データワードにおける１２８ビットの各々に対するシンドローム符号にとって利用可能な各１６ビットに対する１または０が示されていることを述べる先の説明を再考する。図３Ａ〜図３Ｃのテーブルは、各ＲＡＭ装置に対するエラーの各タイプを表わすシンドローム符号値を示すことにより、５４０の訂正可能なエラーを表わす。シンドローム符号は１６進の１０進形式で表示される４つの数字のセットである。
【００３１】
シンドローム符号は複雑なＡＮＤゲートを介してデコードされる。これは、図７において、さらに図９Ａ、図９Ｂおよび図１０Ｂを参照すると、当業者にとって理解可能な概略的な方法で図示される。これらの図は以下の通り適応し合う。図９Ａおよび図９ＢのＡＮＤゲート（それぞれ９１および９５）は、図７のＡＮＤゲートＡｎ（０〜５３９）および図１０のＡＮＤゲート０〜１５に対する同じ全体構成を示す。図１０のＡＮＤゲート０〜１４は図９Ａのゲート９１のために示されるものと同一の入力を有するが、それら入力は、この発明の符号によって決定されるその特定のビットに関連する符号セクションに従って反転され（、２つのこのようなＡＮＤゲートのために例として後により詳細に記載され）る。これらのＡＮＤゲートは図７のＡＮＤゲートＡｎと同じである。４つのＯＲゲートの次の各セットの利用に関わる、後に続くＡＮＤゲートの各グループは、ＡＮＤ０〜１４のために図１０に示されるのと類似のパターンでグループ化され、このため、８つのエラー出力は、それらの各々を、起こり得るエラー（ファミリにおける４つのビットの各々に対して８つ）の図１の構成に従って供給することができる。入力は、図２Ａ〜図２Ｄにおいて説明されるそのファミリに対する符号に従って反転される。このように簡略化して例示する理由は、機能をより詳細に説明すると明らかとなるだろう。
【００３２】
テーブル１０に示されるように４ビットの各ファミリに対する１５の起こり得るエラータイプと１つのノーエラー状態とがあることについて再考する。１５番目のＥＣＣ値は常に０入力であるので、すなわち、すべてのビットがファミリにおいて良好である場合ノーエラー値は存在しないので、１２８ビットワードに対してシンドロームデコードに対処するのに、実際には１５のＡＮＤゲートだけでよいことに留意すべきである。
【００３３】
シンドロームのその単一の値を計算し、それをルックアップテーブルと比較することが可能であり得るが、シンドロームにおいて見出される特定のエラーをより速く突き止める方法は、エラーを訂正するために用いることができるようなものであるが、ビットの各ファミリに対する１５ＡＮＤゲートに１６シンドロームビットのセットを同時に与えることである。図１０は、４つのＯＲゲートが１５のＡＮＤゲートからの８つずつの入力でいかに設定されるかを示す。図１０を説明する前に、図９を参照すると、このような第１のＡＮＤゲート９０がビット１２７を訂正するよう入力を供給し得る。負の入力または反転された入力がシンドロームビット０、１、２、３、６、７、９および１３〜１５のために供給されることに留意されたい。これは、図２Ａ〜図２Ｄのチャートのビット１２７に対する０のビットパターンと一致する。図３Ａ〜図３Ｃのテーブルがまた用いられてもよく、これは、図２Ａ〜図２Ｄのテーブルの置換えであり、ワードとワードのチェックビットとにおけるファミリの各々に対する１５の起こり得るエラー状態の各々に対するいくつかのモジュラ２の結果である。このＡＮＤゲート９０の入力構成は、図１０からわかるように、ＯＲゲート１２７に固有のものであり、（図９Ａのゲート９０と同じ）ゲート０からの唯一の出力がゲート１２７に進む。図９ＢのＡＮＤゲート９９は異なる構成を有し、テーブル３の列０より下のＤ１の結果に対応する。こうして、Ｄ１に対する１０進値（０、１、１および５）が２進パターン、すなわち、０、０、０、０：０、０、０、１：０、０、０、１：０、１、０、１になり、これが、図９Ｂのゲート９９への入力上でインバータシーケンスにおいて繰返される。２ビットエラー値を得るために、図２Ａ〜図２Ｄのテーブルからの２つの関連するビットの値がＸＯＲ演算される。こうして、（Ｄ１のエラーに対してエラーであり得るテーブル１からの）関連したビット０、２がビット１２６および１２４に対応し、これによりＥＣＣビットの２つの２進パターンが与えられる。すなわち、それぞれ、０、０、０、０、０、０、１、０、０、１、０、０、０、１、０、０、および０、０、０、０、０、０、１、１、０、１、０、０、０、１である。これら（これらを加えたモジュラ２）をＸＯＲ演算することにより、２進パターン０、０、０、０：０、０、０、１：０、０、０、１：０、１、０、１、すなわち、ＡＮＤゲート９９への入力に適用されるパターンがもたらされる。ＡＮＤゲートはすべて、図７に示される好ましい実施例において４８０の訂正可能なエラーすべてに対して同様に構成される。さらに、チェックビットのために訂正可能なエラービットで同じことを行なうが、そこでは単に出力を単一の６０入力ＯＲゲート９４に供給するだけである。というのも、チェックビット内で訂正し得るエラーがあったかどうかを知ることにのみ関心があるからである。
【００３４】
所望の場合、発見されたエラーがいずれもメンテナンスプロセッサに送られ得、これを行なう場合、エラーを有するファミリを決定するために４つのＯＲゲートへの入力としてチェックビットの４つのファミリに１６の各ＡＮＤゲートセットを適用するパターンを継続することが望まれる可能性がある。しかしながら、メンテナンスおよび置換え機能がいかに実行されるかはこの発明の範囲を超えているので、どのファミリがエラーを有しているかを示す出力を供給してメンテナンス／置換えの問題をシステムのユーザに示し得ることに留意することで十分である。
【００３５】
５４１番目のＡＮＤゲート（５４１、図７）はすべての反転された入力を有し、シンドロームがすべて０である場合、「ノーエラー」出力がそこから生成される。
【００３６】
ＡＮＤゲート機能がいかに働くかを繰返して述べるために、図９Ａをさらに参照する。この組合せを用いる８つの可能なシンドロームがあり、これはビット１２７におけるエラーを示し得る。これらは図１で発見される。それらはテーブル１０チャートのビット０、４、５、６および１１〜１４である。したがって、シンドロームにおけるビットがいずれも、ＡＮＤゲート９０への反転されない入力ビットすべてに対する１の値でない場合、ま
たはシンドロームにおけるビットがいずれもＡＮＤゲート９０への反転された入力ビットに対する０の値でない場合、それは１の出力をもたらし、ＯＲゲートの値を反転し、ビット１２７に対するエラーを示す。このようにして、ビット１２７（および同様にデータワードの他の１２７のビットすべて）については、１つの１６ＡＮＤゲートセットが単一のクロックサイクルにおいていずれの正の出力をも生成し、それが供給するＯＲゲートが高出力（１）に進み、そのＯＲゲートに対応するそのビットが反転または訂正される必要があることだろうことを示す。
【００３７】
図７の略図７０においては、全体の構成が示される。ここで、シンドローム入力ライン７１は、シンドロームの１６ビット入力を（訂正可能なエラーの１２８ビットのデータワードをテストする）ブロック８１に与え、かつ、ライン７３を介して（エラーがないか１６チェックビットをテストする）ブロック８２に与える。シンドローム符号はまた、ライン７２上でＡＮＤゲート（５４１）に送られ、結果が０である場合、エラー状態ブロック８３にエラーがないことを示す。
【００３８】
ブロック８１のＡＮＤゲートは１６ビットシンドロームから値を生成し、これは、ノー、すなわち、このゲートがこのゲートに対応する図３Ａ〜図３Ｃのテーブルから得られる値と一致するものを有さないこと、またはイエス、すなわち一致するものがあることを表わす。
【００３９】
１６のシンドローム符号の各々は５４１のＡＮＤゲートを介して送られる（図７）。（ＡＮＤゲートハードウェアに障害がなければ、）５４１の出力ラインのうち、１つだけが「１」を表わし得るが、他の５４０の出力ラインは「０」を示す。ＡＮＤゲート０〜４７９の出力はＯＲゲート８３に供給され、これは、エラーがある場合、出力上で１を示すはずである。０〜４７９のＡＮＤゲートはまた、１２８ビットデータワードの各ビットを表わすＯＲゲート０〜１２７へ、ＯＲゲートごとに８ずつ出力を供給する。１の出力を与えるこれらのうちいずれについても、そのゲートによって表わされるビットは、その信号値を変えるよう反転されなければならない。というのも、それがエラーであると判断されるからである。雲状のもの７９は、この説明を簡略化するために、ＡＮＤゲート出力からＯＲゲート入力への相互接続を表わす。ゲート５４１は、訂正可能なエラーが検出されない場合、１を示すこととなる。エラーが示されない場合、１２８ビットデータワードおよびその１６ビットパリティチェック符号は良好なデータである。ＡＮＤゲート０〜４８０のうち１つからのエラー信号は特定のエラーパターンを示し、これを用いて、どのビットがエラーであるかを特定することにより１２８データビットを訂正することができる。ＯＲゲート０〜１２８の出力はＸＯＲゲート８５に送られ、これにより、１２８ビットデータワード入力における不良なビットをいずれもライン８６上で反転させて不良なデータを訂正する単純な手段が提供される。シンドローム符号を用いて、エラーがないかどうか、訂正可能なエラーがあるかどうか、または訂正不可能なエラーがあるかどうかを判断し、エラー状態ボックス８３（図８を参照）において処理される。
【００４０】
図８には３つのインジケータが提供され、検出されるが訂正不可能なエラー１０５、検出されかつ訂正されるエラー１０６、および検出不可能なエラー１０７が略語で示される。ノーエラー（No Error）入力は、完全に反転されたシンドローム入力とともにＡＮＤゲートから入り、シンドロームビットがすべて０である場合に限り、１を生成する。訂正可能なデータ（CORRECTABLE DATA）入力は図７のＯＲゲート８４から入る。信号訂正可能なチェックビット（CORRECTABLE CHECK BIT）は図７のＯＲゲート９４から入り、６０の検出可能なチェックビットエラーのうち１つがこのデータワードで発生したことを示す。こうして、ライン１０６が正である場合、５４０の起こり得る検出可能なエラーのうち１つが発見され、データワードは、どのエラーが１２８に加えて１６のチェックビットのうちどれに発生したかを知ることに基づいて訂正された。エラーがない場合、ライン１０７は正であるはずである。しかしながら、３つの入力のうちいずれかの２つが正である場合、出力１０５は正であるはずであり、１２８ビットデータワードにおける訂正不可能なエラーおよび不良なデータを示す。
【００４１】
したがって、要約すると、データ訂正回路は、ファミリにおいては最大４ビットまで、および１２８ビットワードのいずれかのファミリにおいては最大１ビットまでトグルすることができる。３つの状態ラインは、ノーエラー、訂正可能なエラー、または複数の訂正不可能なエラー（ＭＵＥ）を示す。この論理は、１５が掛けられる３６のＲＡＭ装置のために、訂正を決定すべき５４０のＡＮＤゲートを必要とし、この１５とは、ファミリ内における４つの１ビットエラーの可能性と、ファミリ内における６つの２ビットエラーの可能性と、ファミリ内における４つの３ビットエラーの可能性と、ファミリ内における１つの４ビットエラーとの合計である。番号５４１は任意にノーエラーと示される。複数のビットエラーがいずれも、訂正可能なエラーのうち１つにマッピングしないこと、すなわちノーエラーを、コンピュータ計算に基づいて知る。したがって、補数により、「ノーエラー」信号がない場合、および、エラー信号はあるが訂正可能なエラー信号がない場合、ＭＵＥがなければならず、ワードは破損したデータとして処理されることとなる。
【００４２】
隣接するビットは同じＲＡＭ装置またはファミリ内に位置するが、非隣接ビットは、異なるＲＡＭ装置またはファミリ上に位置する、１４４ビットワード内におけるいずれかの２つ以上のビットである。×４ビットＤＲＡＭチップまたは装置の使用は、この発明の構成の不可欠な局面である。１２８ビットワード専用の３２のＲＡＭ装置があり、４つのＲＡＭ装置が１６チェックビットのために２つの標準的なＤＩＭＭにわたって割当てられる。単一のＲＡＭ内のマルチビット訂正および２つの異なるＲＡＭ内の２ビット検出により、メモリの信頼性が増し、データ破損の起こる可能性が低くなることを理解することが重要である。これらの制限を超えて生じるデータの問題も訂正または検出され得るが、これは、ＥＣＣサイズおよびワードサイズの制限のために保証されないことがさらに理解される。
【００４３】
いずれかの１つの１ビットエラーの可能性が比較的高く、この発明がこれらのエラーのすべてを訂正することが理解される。さらに、いずれかの１つの装置におけるマルチビットエラーの生じる可能性はいずれかの２つの非隣接ビットエラーの可能性よりもはるかに低いが、これらは生じる可能性が次に高い２つのエラータイプを表わす。現在の発明により、すべての２ビット非隣接エラーが、データ破損を防いで、この第２の最も一般的なエラータイプから検出される。さらに、この発明は、いかなる単一のＲＡＭ装置内においても１ビットおよびマルチビット訂正を提供する。サーバメモリサブシステムにおけるエラーの最も重大な原因をカバーすることにより、この発明を利用する際にエラーが訂正されないかまたは検出すらされない可能性は極めて低く、これにより極めて妥当な費用でメモリの信頼性が高められる。標準的な６４ビット×４ビットＤＩＭＭを利用することにより、システムの費用が大いに削減され、この発明の価値が増すことを理解することも重要である。こうして、出願人は、訂正可能かつ検出可能なエラーの商業的に有用なサブセットを規定し、かつ、いかにＥＣＣ符号の特定のセットを用いて訂正可能かつ検出可能なエラーの商業的に有用なセットが訂正または検出されるかを示す説明を提供してきた。
【００４４】
したがって、この発明は添付の特許請求の範囲によってのみ限定される。
【図面の簡単な説明】
【００４５】
【図１】ワードにおける各ＲＡＭ装置のために、起こり得るエラー状態とそれらに対する４つのビット符号とを規定する２進値の好ましい実施例のテーブルを示す図である。
【図２Ａ】この発明の好ましい実施例に従った、エラー訂正符号２進値のテーブルを示す図である。
【図２Ｂ】この発明の好ましい実施例に従った、エラー訂正符号２進値のテーブルを示す図である。
【図２Ｃ】この発明の好ましい実施例に従った、エラー訂正符号２進値のテーブルを示す図である。
【図２Ｄ】この発明の好ましい実施例に従った、エラー訂正符号２進値のテーブルを示す図である。
【図３Ａ】図２Ａ〜図２ＤのＥＣＣ値と図１の起こり得るエラー状態テーブルとを用いる、この発明の好ましい実施例に従った、訂正可能なビットを識別する値のテーブルを示す図である。
【図３Ｂ】図２Ａ〜図２ＤのＥＣＣ値と図１の起こり得るエラー状態テーブルとを用いる、この発明の好ましい実施例に従った、訂正可能なビットを識別する値のテーブルを示す図である。
【図３Ｃ】図２Ａ〜図２ＤのＥＣＣ値と図１の起こり得るエラー状態テーブルとを用いる、この発明の好ましい実施例に従った、訂正可能なビットを識別する値のテーブルを示す図である。
【図４】好ましい実施例に従ったプロセスの流れを示すＥＣＣブロック図である。
【図５】図２Ａ〜図２Ｄのエラー訂正符号のテーブルに従って構成され、この発明の好ましい実施例に従ったパリティツリーの２つのブランチを示すブロック図であり、この発明は、この明細書中に説明されたいずれかの実施例におけるこのような１６のブランチを用いて１２８ビットワードに対して１６チェックビットを生成する。
【図６Ａ】この発明の好ましい実施例に従ったパリティツリーの２つのブランチを示すブロック図であり、この発明は、このような１６のブランチを用いて、この明細書中にさらに説明されるように用いられる１６のシンドローム符号ビットを生成し、図６Ｂと数学的に等しい図である。
【図６Ｂ】この発明の好ましい実施例に従ったパリティツリーの２つのブランチを示すブロック図であり、この発明は、このような１６のブランチを用いて、この明細書中にさらに説明されるように用いられる１６のシンドローム符号ビットを生成し、図６Ａと数学的に等しい図である。
【図７】この発明の好ましい実施例に従ったシンドロームデコード関数を示し、さらに、エラー状態ビットの生成を示し、かつこの発明の好ましい実施例にも従ったブロック図である。
【図８】図７の図よりも詳細にエラー状態関数を示すブロック図である。
【図９Ａ】ＡＮＤゲートと、図７の回路に対するこのＡＮＤゲートへのシンドロームラインの入力構成とを示し、図１０に図示される図７のサブパートに関連して最良に考慮されるブロック図である。
【図９Ｂ】ＡＮＤゲートと、図７の回路に対するこのＡＮＤゲートへのシンドロームラインの入力構成とを示し、図１０に図示される図７のサブパートに関連して最良に考慮されるブロック図である。
【図１０】４つのＸＯＲゲートのセットを含み、各々が図９のＡＮＤゲートのうち８つから入力を受信する、図７の回路のサブパートを示す図である。
【図１】
2005508548.tif 000003
【図３Ａ】
2005508548.tif 000004
【図４】
2005508548.tif 000005
【図５】
2005508548.tif 000006
【図６Ａ】
2005508548.tif 000007
【図６Ｂ】
2005508548.tif 000008
【図７】
2005508548.tif 000009
【図８】
2005508548.tif 000010
【国際公開パンフレット】
2005508548.tif 000011
2005508548.tif 000012
2005508548.tif 000013
2005508548.tif 000014
2005508548.tif 000015
2005508548.tif 000016
2005508548.tif 000017
2005508548.tif 000018
2005508548.tif 000019
2005508548.tif 000020
2005508548.tif 000021
2005508548.tif 000022
2005508548.tif 000023
2005508548.tif 000024
2005508548.tif 000025
2005508548.tif 000026
2005508548.tif 000027
2005508548.tif 000028
2005508548.tif 000029
2005508548.tif 000030
2005508548.tif 000031
2005508548.tif 000032
2005508548.tif 000033
2005508548.tif 000034
2005508548.tif 000035
2005508548.tif 000036
2005508548.tif 000037
2005508548.tif 000038
2005508548.tif 000039
2005508548.tif 000040
2005508548.tif 000041
2005508548.tif 000042
2005508548.tif 000043
2005508548.tif 000044
2005508548.tif 000045
2005508548.tif 000046
2005508548.tif 000047
2005508548.tif 000048
2005508548.tif 000049
2005508548.tif 000050
【国際公開パンフレット（コレクトバージョン）】
2005508548.tif 000051
【国際調査報告】
2005508548.tif 000052
2005508548.tif 000053
2005508548.tif 000054