JPS63155237A - 誤り訂正・検出方式 - Google Patents
誤り訂正・検出方式Info
- Publication number
- JPS63155237A JPS63155237A JP61302226A JP30222686A JPS63155237A JP S63155237 A JPS63155237 A JP S63155237A JP 61302226 A JP61302226 A JP 61302226A JP 30222686 A JP30222686 A JP 30222686A JP S63155237 A JPS63155237 A JP S63155237A
- Authority
- JP
- Japan
- Prior art keywords
- bit
- matrix
- bits
- syndrome
- error
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
- G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
- G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
- G06F11/1012—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using codes or arrangements adapted for a specific type of error
- G06F11/1028—Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/19—Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Quality & Reliability (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Detection And Correction Of Errors (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、誤り訂正・検出方式に関し、特にブロックエ
ラーを検出するのに好適な１ビットエラー訂正・２ビッ
ト工ラー検出方式に関する。
ラーを検出するのに好適な１ビットエラー訂正・２ビッ
ト工ラー検出方式に関する。
従来、１ビットエラーを訂正し、２ビットエラーを検出
し、さらに単一のブロックエラーを検出する５ＥＣ−Ｄ
ＥＤ−９ｂＥＤ符号（Ｓｉｎｇｌｅ ｂｉｔ’Ｅｒｒｏ
ｒ Ｃｏｒｒｅｃｔｉｎｇ −Ｄｏｕｂｌｅ ｂｉｔ
Ｅｒｒｏｒ Ｄｅｔｅｃｔｉｎｇ −Ｓｉｎｇｌｅ ｂ
ｂｉｔ ｂｙｔｅ Ｅｒｒｏｒ Ｄｅｔｅｃｔｉｎｇ
Ｃｏｄｅ）を用いた誤り訂正・検出方式としては、（＋
）電子通信学会論文誌１９８４年５月号第５９３頁〜第
５９８頁に示される符号を用いたものや、（２）アイ・
ビー・エム、ジェイ・アール・アンド・ディー、２８．
２（１９８Ｊｉ年３月号）、第１２９頁（ＩＢＭ、Ｊ、
Ｒ＆Ｄ、ＶＯＬ、２８．ＮＯ２，ｐ１２９）に示される
符号を用いたものなどが知られている。
し、さらに単一のブロックエラーを検出する５ＥＣ−Ｄ
ＥＤ−９ｂＥＤ符号（Ｓｉｎｇｌｅ ｂｉｔ’Ｅｒｒｏ
ｒ Ｃｏｒｒｅｃｔｉｎｇ −Ｄｏｕｂｌｅ ｂｉｔ
Ｅｒｒｏｒ Ｄｅｔｅｃｔｉｎｇ −Ｓｉｎｇｌｅ ｂ
ｂｉｔ ｂｙｔｅ Ｅｒｒｏｒ Ｄｅｔｅｃｔｉｎｇ
Ｃｏｄｅ）を用いた誤り訂正・検出方式としては、（＋
）電子通信学会論文誌１９８４年５月号第５９３頁〜第
５９８頁に示される符号を用いたものや、（２）アイ・
ビー・エム、ジェイ・アール・アンド・ディー、２８．
２（１９８Ｊｉ年３月号）、第１２９頁（ＩＢＭ、Ｊ、
Ｒ＆Ｄ、ＶＯＬ、２８．ＮＯ２，ｐ１２９）に示される
符号を用いたものなどが知られている。
しかし、これらの誤り訂正・検出方式では共に特定の単
一ブロック内の３ビット以上エラーを検出するのみで、
ブロック間にまたがる３ビット以上エラーについては配
慮されていなかった。
一ブロック内の３ビット以上エラーを検出するのみで、
ブロック間にまたがる３ビット以上エラーについては配
慮されていなかった。
ところで、複数ビットのデータ出力を持つ記憶素子を用
いた半導体記憶装置等において、２種類以上のブロック
分割に対して、それぞれのブロックエラーを検出するこ
とが要求される場合がある。
いた半導体記憶装置等において、２種類以上のブロック
分割に対して、それぞれのブロックエラーを検出するこ
とが要求される場合がある。
例えば、４ビット構成のＩＣメモリを、３ビット構成の
ドライバーＩＣで駆動する場合、４ビットブロツクに対
するブロックエラーが検出できると同時に、３ビットブ
ロツクに対するブロックエラーも検出できることが望ま
しい。この場合、上記従来技術により５ＥＣ−ＤＥＤ−
３４ＥＤ符号を構成すると、４ビットブロツクエラーは
検出できるが、４ビットブロック間にまたがる３ビット
ブロツクエラーは、一般に検出されないという問題があ
る。
ドライバーＩＣで駆動する場合、４ビットブロツクに対
するブロックエラーが検出できると同時に、３ビットブ
ロツクに対するブロックエラーも検出できることが望ま
しい。この場合、上記従来技術により５ＥＣ−ＤＥＤ−
３４ＥＤ符号を構成すると、４ビットブロツクエラーは
検出できるが、４ビットブロック間にまたがる３ビット
ブロツクエラーは、一般に検出されないという問題があ
る。
本発明の目的は、このような′従来の問題を解決し、ｂ
ビットブロックエラーを検出すると同時に、（ｂ−１）
ビット以下のブロックエラーの検出も行え、さらに任意
の連続する（ｂ−１）ビット内のエラー（（ｂ−１）ビ
ットバーストエラー）検出が可能な５ＥＣ−ＤＥＤ−３
ｂＥＤ符号を用いた誤り訂正・検出方式を提供すること
にある。
ビットブロックエラーを検出すると同時に、（ｂ−１）
ビット以下のブロックエラーの検出も行え、さらに任意
の連続する（ｂ−１）ビット内のエラー（（ｂ−１）ビ
ットバーストエラー）検出が可能な５ＥＣ−ＤＥＤ−３
ｂＥＤ符号を用いた誤り訂正・検出方式を提供すること
にある。
上記問題点を解決するため、本発明では、複数（ｂ）ビ
ットのブロック複数よりなる情報を、次の部分パリティ
行列Ｐを含むパリティ行列に基づいて復号する手段を有
し、該復号手段により１ビットエラー訂正・２ビットエ
ラー検出・同一ブロック内３ビット以上エラー検出・任
意の３ビット息上（ｂ−１）ビット以下バーストエラー
検出を行うことに特徴がある。
ットのブロック複数よりなる情報を、次の部分パリティ
行列Ｐを含むパリティ行列に基づいて復号する手段を有
し、該復号手段により１ビットエラー訂正・２ビットエ
ラー検出・同一ブロック内３ビット以上エラー検出・任
意の３ビット息上（ｂ−１）ビット以下バーストエラー
検出を行うことに特徴がある。
Ｐ＝〔Ａ０・・・ＡｉＡｉ・・・Ａｉ・・・・Ａｂ・・
・・ＡＩ、）ただし、 Ａｉ（ｉ＝０〜ｂ）は０Ａ１＝Ｂ−ＣＩＦなるｂｘｂ行
列。
・・ＡＩ、）ただし、 Ａｉ（ｉ＝０〜ｂ）は０Ａ１＝Ｂ−ＣＩＦなるｂｘｂ行
列。
Ｃ’（ｉ＝ｏＮｂ）は、ｂｘｂ行列
をｉ同種は合わせたｂｘｂ行列。
ＢはＣ１の行および列を任意に入れ換えたｂｘｂ行列で
ある。
ある。
本発明においては、複数（ｂ）ビットのブロック複数よ
りなる情報を、上記の部分パリティ行列Ｐ＝〔Ａｉ・・
・ＡｉＡｉ・・・Ａ１・・・・Ａｂ・・・・Ａ ｂ ）
を含むパリティ行列に基づいて復号することにより、ｂ
ビットブロックエラーおよび（ｂ−１）ビットバースト
エラーが検出できることを以下に詳述する。
りなる情報を、上記の部分パリティ行列Ｐ＝〔Ａｉ・・
・ＡｉＡｉ・・・Ａ１・・・・Ａｂ・・・・Ａ ｂ ）
を含むパリティ行列に基づいて復号することにより、ｂ
ビットブロックエラーおよび（ｂ−１）ビットバースト
エラーが検出できることを以下に詳述する。
まず、行列Ａ□およびＰの性質について説明する。
行列Ｃ’（ｉ＝０〜ｂ）は、
となる。したがって、行列Ｂは次のｂ＋を個の行ベクト
ルＤ、〜Ｄｂの内、異なるｂ個の行ベクトルを選ぶこと
により構成できる。
ルＤ、〜Ｄｂの内、異なるｂ個の行ベクトルを選ぶこと
により構成できる。
Ｄ、＝１１・・・・・・ｌ
Ｄ、＝ｌＯ・・・・・・Ｏ
Ｄ、＝ＯＩＯ・・・・Ｏ
ｂビット
行列Ｂのに行目が行ベクトルＤＪ（ｊ・０〜ｂ）である
時、行列Ｐのに行目は、ベクトルＤＪと行列Ｃ°〜Ｃｂ
との積を取ることにより、 ｊ＝ｏの時＝Ｄ、・・・Ｄ、Ｄｂ・・・Ｄｂ・・・Ｄｌ
・・Ｄ。
時、行列Ｐのに行目は、ベクトルＤＪと行列Ｃ°〜Ｃｂ
との積を取ることにより、 ｊ＝ｏの時＝Ｄ、・・・Ｄ、Ｄｂ・・・Ｄｂ・・・Ｄｌ
・・Ｄ。
ｊ；ｌの時：Ｄｌ・・・Ｄ、Ｄ、・・・Ｄ、・・・Ｄ、
・・Ｄ。
・・Ｄ。
ｊ＝ｂの時：Ｄｂ・・Ｄ ｂＤ ｂ−、・・Ｄ ｂ −
＋・・Ｄ、・・Ｄ。
＋・・Ｄ、・・Ｄ。
となる。以上より、次のことが導かれる。
（性質ｉ）行列Ａｉは５行ベクトルＤ、〜Ｄｂの内の異
なるｂ個により構成される。
なるｂ個により構成される。
（性質ｉｆ）行列Ｐの一部であるｂＸ２ｂ行列〔Ａ□
Ａｉ＋＋） は、次のｂ＋１個の行ベクトルＥ、〜Ｅｂの内、異なる
ｂ個の行ベクトルを選んで構成できる。
Ａｉ＋＋） は、次のｂ＋１個の行ベクトルＥ、〜Ｅｂの内、異なる
ｂ個の行ベクトルを選んで構成できる。
Ｅ、＝Ｄ、Ｄｂ ＝１１・・・ＩＯ・・・０１Ｅ、＝Ｄ
、Ｄ、 ＝ｌＯ・・・０１・・・・・ＩＥｂ＝ Ｄｂ
Ｄｂ−、＝ Ｏ・−・０１０ ・・・ｌ Ｏし一−１−
一−」 ２ｂビット これらの性質をもとに、行列Ｐを部分行列として含むパ
リティ行列な復号に用いれば、ｂビットブロックエラー
および（ｂ−ｉ）ビットバーストエラーが検出できるこ
とを示す。５ＥＣ−ＤＥＤ符号では任意の２ビットエラ
ーが検出できるので、ｂビットブロック内３ビット以上
エラーおよび（ｂ・−１）ビット以下３ビット以上バー
ストエラーが検出できることを示す、そのため、ここで
は行列Ｐにより規定されるｂビットのシンドロームＳｐ
の重み（“ｌ”の数）に着目する。性質１より、行列Ａ
ｉの各列の重みが１または２であるので、１ビットエラ
ーに対するＳｐの重みは１または２である。一方。
、Ｄ、 ＝ｌＯ・・・０１・・・・・ＩＥｂ＝ Ｄｂ
Ｄｂ−、＝ Ｏ・−・０１０ ・・・ｌ Ｏし一−１−
一−」 ２ｂビット これらの性質をもとに、行列Ｐを部分行列として含むパ
リティ行列な復号に用いれば、ｂビットブロックエラー
および（ｂ−ｉ）ビットバーストエラーが検出できるこ
とを示す。５ＥＣ−ＤＥＤ符号では任意の２ビットエラ
ーが検出できるので、ｂビットブロック内３ビット以上
エラーおよび（ｂ・−１）ビット以下３ビット以上バー
ストエラーが検出できることを示す、そのため、ここで
は行列Ｐにより規定されるｂビットのシンドロームＳｐ
の重み（“ｌ”の数）に着目する。性質１より、行列Ａ
ｉの各列の重みが１または２であるので、１ビットエラ
ーに対するＳｐの重みは１または２である。一方。
（１）ブロック内３ビット以上エラーに対するｓｐの重
みは３以上である。なぜならば、ブロックを規定する行
列Ａｉに関する性質ｉより、（ａ）Ａｉがり、を含まな
い場合、ｓｐの重みはエラーピット数と等しく、３以上
である。
みは３以上である。なぜならば、ブロックを規定する行
列Ａｉに関する性質ｉより、（ａ）Ａｉがり、を含まな
い場合、ｓｐの重みはエラーピット数と等しく、３以上
である。
（ｂ） Ａ 、がり、を含む場合、４ビット以上エラー
に対しては、Ａｉのり、を除＜ （ｂ−１）行に対応す
るシンドロームの重みが３以上である。
に対しては、Ａｉのり、を除＜ （ｂ−１）行に対応す
るシンドロームの重みが３以上である。
（Ｃ）Ａｉがり、を含む場合、３ビットエラーに対して
は、Ａｉのり、を除＜ （ｂ−１）行に対するシンドロ
ームの重みが２または３．Ｄ０行のシンドロームが“１
″であるので、Ｓｐの重みは３以上であるからである。
は、Ａｉのり、を除＜ （ｂ−１）行に対するシンドロ
ームの重みが２または３．Ｄ０行のシンドロームが“１
″であるので、Ｓｐの重みは３以上であるからである。
（２）同一の行列Ａｉを有する２つのブロック間にまた
がるｂビット以下３ビット以上バーストエラーに対する
ｓｐの重みは３以上である。なぜならば１着目するｂビ
ットバーストに対応する行列を構成する列ベクトルは行
列Ａｉを構成する列ベクトルに相等しく、上記（１）と
同様の議論に帰着されるからである。
がるｂビット以下３ビット以上バーストエラーに対する
ｓｐの重みは３以上である。なぜならば１着目するｂビ
ットバーストに対応する行列を構成する列ベクトルは行
列Ａｉを構成する列ベクトルに相等しく、上記（１）と
同様の議論に帰着されるからである。
（３）異なる２つの行列Ａｉ＋Ａｉや、を有する２つの
ブロック間にまたがる（ｂ−１）ビット以下３ビット以
上バーストエラーに対するＳｐの重みは３以上である。
ブロック間にまたがる（ｂ−１）ビット以下３ビット以
上バーストエラーに対するＳｐの重みは３以上である。
なぜならば、着目する（ｂ−１）ビットバーストに対応
する行列ｘ１は性質ｉｉより次のｂ十１個の行ベクトル
Ｆ、〜Ｆｂの内の異なるｂ個により構成されるが、 Ｆ、＝１・・・１０・・・０ Ｆ１＝１・・・０１・・・Ｉ Ｆ□＝１０・・・・・・・・０ ？ Ｆｂ＝Ｏ・・・・・・・・０１ ｂ−ｉビット （ａ）ＸｔａがＦ、またはＦｌを含まない場合、Ｘ、の
Ｆ、、 Ｆ、を除＜ （ｂ−１）行に対応するシンド
ロームの重みが３以上である。
する行列ｘ１は性質ｉｉより次のｂ十１個の行ベクトル
Ｆ、〜Ｆｂの内の異なるｂ個により構成されるが、 Ｆ、＝１・・・１０・・・０ Ｆ１＝１・・・０１・・・Ｉ Ｆ□＝１０・・・・・・・・０ ？ Ｆｂ＝Ｏ・・・・・・・・０１ ｂ−ｉビット （ａ）ＸｔａがＦ、またはＦｌを含まない場合、Ｘ、の
Ｆ、、 Ｆ、を除＜ （ｂ−１）行に対応するシンド
ロームの重みが３以上である。
（ｂ）ＸｔｙがＦ、、 Ｆ、をともに含む場合、４ビ
ット以上エラーに対しては、Ｘ９のＦ、、Ｆ、を除く（
ｂ−２）行に対応するシンドロームの重みが３以上であ
る。
ット以上エラーに対しては、Ｘ９のＦ、、Ｆ、を除く（
ｂ−２）行に対応するシンドロームの重みが３以上であ
る。
（Ｃ）ＸＬＪがＦ、、 Ｆ、をともに含む場合、３ビ
ットエラーに対しては、Ｘ、のＦ、、 Ｆ、を除く（
ｂ−２）行に対応するシンドロームの重みが２または３
．Ｆ０行または１１行に対応するシンドロームのうちい
ずれか一方が１″であるので、ｓｐの重みは３以上であ
るからである。
ットエラーに対しては、Ｘ、のＦ、、 Ｆ、を除く（
ｂ−２）行に対応するシンドロームの重みが２または３
．Ｆ０行または１１行に対応するシンドロームのうちい
ずれか一方が１″であるので、ｓｐの重みは３以上であ
るからである。
以上（１）、 （２）、 （３）より、ブロック内３ビ
ット以上エラーおよび（ｂ−１）ビット以下３ビット以
上バーストエラーに対するｓｐの重みは３以上となり１
重み１または２の１ビットエラーと閏違うことなく検出
できる。
ット以上エラーおよび（ｂ−１）ビット以下３ビット以
上バーストエラーに対するｓｐの重みは３以上となり１
重み１または２の１ビットエラーと閏違うことなく検出
できる。
以下、本発明の一実施例を、図面により詳細に説明する
。
。
第１図は、本発明に用いるパリティ行列の一構成例を示
す図である。ここでは、ｂ＝５．チェックピット８ビッ
トに対して、符号長６０ビットまでとれる。第１図のパ
リティ行列は１部分行列Ｐ（上位５行）と、符号長の拡
張およびＳ ＥＣ−ＤＥＤ機能を付加するための奇数重
み列化のための下位３行とからなる。第１図のパリティ
行列を用いれば、上位５行で決まるシンドロームの重み
が、１ビットエラーに対しては１か２になるのに対して
、５ビットブロツク内および任意の４ビットバースト内
の３ビット以上エラーに対しては３以上となり、検出可
能であることがわかる。
す図である。ここでは、ｂ＝５．チェックピット８ビッ
トに対して、符号長６０ビットまでとれる。第１図のパ
リティ行列は１部分行列Ｐ（上位５行）と、符号長の拡
張およびＳ ＥＣ−ＤＥＤ機能を付加するための奇数重
み列化のための下位３行とからなる。第１図のパリティ
行列を用いれば、上位５行で決まるシンドロームの重み
が、１ビットエラーに対しては１か２になるのに対して
、５ビットブロツク内および任意の４ビットバースト内
の３ビット以上エラーに対しては３以上となり、検出可
能であることがわかる。
以下、本実施例において、３バイト（２４ビット）のデ
ータを４ビット構成のＩＣメモリと６ビット構成のドラ
イバ／レシーバを使った記憶装置に読み書きするものと
する。２４ビットのデータに対して５ＥＣ−ＤＥＣ機能
を付加するにはチェックピットはｂビットあればよいが
、４ビット構成のＩＣメモリを用いるので、チェックピ
ットを８ビットまでとってもＩＣメモリ数を増やすこと
はない。
ータを４ビット構成のＩＣメモリと６ビット構成のドラ
イバ／レシーバを使った記憶装置に読み書きするものと
する。２４ビットのデータに対して５ＥＣ−ＤＥＣ機能
を付加するにはチェックピットはｂビットあればよいが
、４ビット構成のＩＣメモリを用いるので、チェックピ
ットを８ビットまでとってもＩＣメモリ数を増やすこと
はない。
第２図（ａ）は本発明の一実施例で用いるパリティ行列
を示す図であり、第２図（ｂ）はチェックピット生成行
列を示す図である。
を示す図であり、第２図（ｂ）はチェックピット生成行
列を示す図である。
第２図（ａ）のパリティ行列は、ｂ＝６．チェックピッ
ト８ビットに対して前記手段により構成された符号長４
２ビットのパリティ行列を３２ビットに短縮化したもの
である。第２図（ａ）のパリティ行列を用いれば、１ビ
ットエラー訂正・２ビットエラー検出の他、６ビットブ
ロツク内および任意の５ビットバースト内の３ビット以
上エラーが検出できる。したがって、１個のＩＣメモリ
（４ビット構成）、あるいは１個のドライバ／レシーバ
（６ビット構成）が故障しても、誤訂正することなく検
出できる。第２図（ｂ）の行列は、第２図（ａ）のパリ
ティ行列に、チェックピット部（ＧｏないしＣ７）が単
位行列となるように周知の等偏行操作を施して得られる
チェックピット生成行列を示している。
ト８ビットに対して前記手段により構成された符号長４
２ビットのパリティ行列を３２ビットに短縮化したもの
である。第２図（ａ）のパリティ行列を用いれば、１ビ
ットエラー訂正・２ビットエラー検出の他、６ビットブ
ロツク内および任意の５ビットバースト内の３ビット以
上エラーが検出できる。したがって、１個のＩＣメモリ
（４ビット構成）、あるいは１個のドライバ／レシーバ
（６ビット構成）が故障しても、誤訂正することなく検
出できる。第２図（ｂ）の行列は、第２図（ａ）のパリ
ティ行列に、チェックピット部（ＧｏないしＣ７）が単
位行列となるように周知の等偏行操作を施して得られる
チェックピット生成行列を示している。
第３図は、本発明の一実施例を示す誤り訂正・検出装置
の全体構成図である。
の全体構成図である。
記憶装置３へのデータ書込み時、処理装置１より与えら
れた書込みデータ１０（ＳＤＯ〜２３）は、チェックピ
ットジェネレータ２に入力される。チェックビットジェ
ネレータ２は、第２図（ｂ）の行列に基づいてチェック
ピット２０（Ｃｏ〜７）を生成し、生成されたチェック
ピット２０は、書込みデータ１０とともに記憶装置３に
書込まれる。
れた書込みデータ１０（ＳＤＯ〜２３）は、チェックピ
ットジェネレータ２に入力される。チェックビットジェ
ネレータ２は、第２図（ｂ）の行列に基づいてチェック
ピット２０（Ｃｏ〜７）を生成し、生成されたチェック
ピット２０は、書込みデータ１０とともに記憶装置３に
書込まれる。
記憶装置３からのデータ読出し時、読出しデータ３０（
ＦＤＯ〜２３）および読出しチェックビット３１（ＦＣ
Ｏ〜７）は、シンドロームジェネレータ４に入力される
。シンドロームジェネレータ４は、第２図（ａ）のパリ
ティ行列に基づいてシンドローム４０（Ｓｏ〜７）を生
成し、シンドロームデコーダ５に供給する。シンドロー
ムデコーダ５は、第２図（ａ）のパリティ行列に基づい
てシンドローム４０を解読し、１ビット工ラー訂正信号
５０を生成し訂正回路６に供給するとともに、信号線５
１を介して処理装置１に対して訂正可能エラー（ＣＥ
）。
ＦＤＯ〜２３）および読出しチェックビット３１（ＦＣ
Ｏ〜７）は、シンドロームジェネレータ４に入力される
。シンドロームジェネレータ４は、第２図（ａ）のパリ
ティ行列に基づいてシンドローム４０（Ｓｏ〜７）を生
成し、シンドロームデコーダ５に供給する。シンドロー
ムデコーダ５は、第２図（ａ）のパリティ行列に基づい
てシンドローム４０を解読し、１ビット工ラー訂正信号
５０を生成し訂正回路６に供給するとともに、信号線５
１を介して処理装置１に対して訂正可能エラー（ＣＥ
）。
訂正不能エラー（ＵＣＥ）を報告する。訂正回路６は、
１ビット工ラー訂正信号５０に基づいて読出しデータ３
０を訂正し、訂正済データ６０を処理装置１に供給する
。
１ビット工ラー訂正信号５０に基づいて読出しデータ３
０を訂正し、訂正済データ６０を処理装置１に供給する
。
第４図は、第３図におけるチェックビットジェネレータ
２の一構成例を示す図である。
２の一構成例を示す図である。
チェックビットジェネレータ２は、８個の９〜１８人力
排他的論理和ゲート２１〜２８より構成される。各排他
的論理和ゲートは、第２図（ｂ）の行列に基づいて、そ
れぞれ１ビットのチェックビットを生成する０例えば、
排他的論理和ゲート２１は、第２図（ｂ）の行列の第１
行に基づいて。
排他的論理和ゲート２１〜２８より構成される。各排他
的論理和ゲートは、第２図（ｂ）の行列に基づいて、そ
れぞれ１ビットのチェックビットを生成する０例えば、
排他的論理和ゲート２１は、第２図（ｂ）の行列の第１
行に基づいて。
書込みデータＳＤＯ〜２．ＳＤ５〜７．ＳＤＩＯ〜１２
，５Ｄ１５〜１７．５Ｄ２０〜２３のモジュロ２の加算
をとることにより、チェックビットＣＯを生成する。
，５Ｄ１５〜１７．５Ｄ２０〜２３のモジュロ２の加算
をとることにより、チェックビットＣＯを生成する。
第５図は、第３図におけるシンドロームジェネレータ４
の一構成例を示す図である。
の一構成例を示す図である。
シンドロームジェネレータ４は、８個の６〜１９人力排
他的論理和ゲート４１〜４８より構成される。各排他的
論理和ゲートは、第２図（ａ）のパリティ行列に基づい
て、それぞれ１ビットのシンドロームを生成する６例え
ば、排他的論理和ゲート４１は、第２図（、ａ）のパリ
ティ行列の第１行列に基づいて、読出しデータＦＤ４．
ＦＤ９．ＦＤ１４゜ＦＤ１９および読出しチェックビッ
トＦＣＯ，ＦＣ６、Ｆｅ２のモジュロ２の加算をとるこ
とによりシンドロームＳＯを生成する。
他的論理和ゲート４１〜４８より構成される。各排他的
論理和ゲートは、第２図（ａ）のパリティ行列に基づい
て、それぞれ１ビットのシンドロームを生成する６例え
ば、排他的論理和ゲート４１は、第２図（、ａ）のパリ
ティ行列の第１行列に基づいて、読出しデータＦＤ４．
ＦＤ９．ＦＤ１４゜ＦＤ１９および読出しチェックビッ
トＦＣＯ，ＦＣ６、Ｆｅ２のモジュロ２の加算をとるこ
とによりシンドロームＳＯを生成する。
第６図は、第３図におけるシンドロームデコーダ５およ
び訂正回路６の一構成例を示す図である。
び訂正回路６の一構成例を示す図である。
シンドロームデコーダ５は、デコーダ５２．論理和ゲー
ト５３，５４．否定ゲート５５．論理積ゲート５６より
構成され、訂正回路６は読出しデータＦＤＯないしＦＤ
２３に対応した２４個の２人力排他的論理和ゲートより
構成される。デコーダ５２は、第２図（ａ）のパリティ
行列の各列に対応したシンドロームパターンを検出して
３２本の１ビット工ラー訂正信号を生成する。例えば、
シンドロームがパリティ行列のｄｏ列に対応する００１
１００１０”（１０進数で５０）の時、読出しデータＦ
ＤＯの１ビットエラー訂正信号Ｔ５０を付勢する。すべ
ての１ビット工ラー訂正信号は論理和ゲート５４に入力
され、訂正可能エラー報告信号ＣＥが生成される。訂正
不能エラー報告信号ＵＣＥは、少くとも１ビットのシン
ドロームが“１”であり、かつ訂正可能エラーでない（
ＣＥ）時付勢される。
ト５３，５４．否定ゲート５５．論理積ゲート５６より
構成され、訂正回路６は読出しデータＦＤＯないしＦＤ
２３に対応した２４個の２人力排他的論理和ゲートより
構成される。デコーダ５２は、第２図（ａ）のパリティ
行列の各列に対応したシンドロームパターンを検出して
３２本の１ビット工ラー訂正信号を生成する。例えば、
シンドロームがパリティ行列のｄｏ列に対応する００１
１００１０”（１０進数で５０）の時、読出しデータＦ
ＤＯの１ビットエラー訂正信号Ｔ５０を付勢する。すべ
ての１ビット工ラー訂正信号は論理和ゲート５４に入力
され、訂正可能エラー報告信号ＣＥが生成される。訂正
不能エラー報告信号ＵＣＥは、少くとも１ビットのシン
ドロームが“１”であり、かつ訂正可能エラーでない（
ＣＥ）時付勢される。
このように、本実施例においては、６ビットブロツク内
および５ビットバースト内の３ビット以上エラーも検出
できるので、４ビット構成のＩＣメモリおよび６ビット
構成のドライバ／レシーバのいずれの故障も検出可能と
なり、信頼性を上げることができる。また、本実施例で
は、上記検出能力をＩＣメモリ数を増やすことなく実現
できる。
および５ビットバースト内の３ビット以上エラーも検出
できるので、４ビット構成のＩＣメモリおよび６ビット
構成のドライバ／レシーバのいずれの故障も検出可能と
なり、信頼性を上げることができる。また、本実施例で
は、上記検出能力をＩＣメモリ数を増やすことなく実現
できる。
以上説明したように、本発明によれば、１ビットエラー
訂正・２ビットエラー検出・ｂビットブロックエラー検
出に加え、（ｂ−１）ビットバーストエラーも検出でき
るので、検出能力の高い誤り訂正・検出を実現できる。
訂正・２ビットエラー検出・ｂビットブロックエラー検
出に加え、（ｂ−１）ビットバーストエラーも検出でき
るので、検出能力の高い誤り訂正・検出を実現できる。
第１図は本発明の誤り訂正・検出方式で用いるパリティ
行列の例を示す図、第２図（ａ）、 （ｂ）はそれぞれ
本発明の一実施例で用いるパリティ行列を示す図、チェ
ックビット生成行列を示す図、第３図は本発明の一実施
例を示す誤り訂正・検出装置の全体構成図、第４図は第
３図のチェックビットジェネレータの詳細構成図、第５
図は第３図のシンドロームジェネレータの詳細構成図、
第６図は第３図のシンドロームデコーダ／訂正回路の詳
細構成図である。 １：処理装置、２：チェックビットジェネレータ、３：
記憶装置、４ニシンドロームシエネレータ、５：シンド
ロームデコーダ、６：訂正回路。 第１図 第 ３ 図 第 ヰ 図 第 ５ 図 ＦＣＯ−７ＦＤｏ−２３ 第６図
行列の例を示す図、第２図（ａ）、 （ｂ）はそれぞれ
本発明の一実施例で用いるパリティ行列を示す図、チェ
ックビット生成行列を示す図、第３図は本発明の一実施
例を示す誤り訂正・検出装置の全体構成図、第４図は第
３図のチェックビットジェネレータの詳細構成図、第５
図は第３図のシンドロームジェネレータの詳細構成図、
第６図は第３図のシンドロームデコーダ／訂正回路の詳
細構成図である。 １：処理装置、２：チェックビットジェネレータ、３：
記憶装置、４ニシンドロームシエネレータ、５：シンド
ロームデコーダ、６：訂正回路。 第１図 第 ３ 図 第 ヰ 図 第 ５ 図 ＦＣＯ−７ＦＤｏ−２３ 第６図
Claims (1)
- 【特許請求の範囲】 １、複数（ｂ）ビットのブロック複数よりなる情報を、
次の部分パリテイ行列Ｐを含むパリテイ行列に基づいて
復号する手段を有し、該復号手段により１ビットエラー
訂正・２ビットエラー検出・同一ブロック内３ビット以
上エラー検出・任意の３ビット以上（ｂ−１）ビット以
下バーストエラー検出を行うことを特徴とする誤り訂正
・検出方式。 Ｐ＝〔Ａ＿０・・・Ａ＿０Ａ＿１・・・Ａ＿１・・・・
Ａ＿ｂ・・・・Ａ＿ｂ〕ただし、 Ａ＿ｉ（ｉ＝０〜ｂ）は、Ａ＿ｉ＝Ｂ・Ｃ＾ｉなるｂ×
ｂ行列、Ｃ＾ｉ（ｉ＝０〜ｂ）は、ｂ×ｂ行列 ▲数式、化学式、表等があります▼ をｉ回掛け合わせたｂ×ｂ行列、 ＢはＣ＾ｉの行および列を任意に入れ換えたｂ×ｂ行列
である。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61302226A JPH0760394B2 (ja) | 1986-12-18 | 1986-12-18 | 誤り訂正・検出方式 |
| US07/132,993 US4888774A (en) | 1986-12-18 | 1987-12-15 | Error detection system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61302226A JPH0760394B2 (ja) | 1986-12-18 | 1986-12-18 | 誤り訂正・検出方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63155237A true JPS63155237A (ja) | 1988-06-28 |
| JPH0760394B2 JPH0760394B2 (ja) | 1995-06-28 |
Family
ID=17906462
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61302226A Expired - Lifetime JPH0760394B2 (ja) | 1986-12-18 | 1986-12-18 | 誤り訂正・検出方式 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US4888774A (ja) |
| JP (1) | JPH0760394B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH1011307A (ja) * | 1996-06-27 | 1998-01-16 | Nec Corp | 主記憶装置 |
| JP2009070356A (ja) * | 2007-09-13 | 2009-04-02 | United Memories Inc | ハミングコードｈ行列における最小重み付けコード数を増やすべくチェック・ビットのパリティビット幅および追加チェック・ビットの使用によるデータブロックの症候群発生を減らす技術 |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05158722A (ja) * | 1991-12-10 | 1993-06-25 | Hitachi Ltd | 誤り検出・訂正方式 |
| JPH088760A (ja) * | 1994-06-16 | 1996-01-12 | Toshiba Corp | 誤り訂正装置 |
| SG76501A1 (en) * | 1996-02-28 | 2000-11-21 | Sun Microsystems Inc | Error detection and correction method and apparatus for computer memory |
| US6041430A (en) * | 1997-11-03 | 2000-03-21 | Sun Microsystems, Inc. | Error detection and correction code for data and check code fields |
| KR20010057145A (ko) * | 1999-12-18 | 2001-07-04 | 윤종용 | Ｘｏｒ 코드, 이를 이용한 직렬 연접 부호기 및 복호기 |
| FR2823035B1 (fr) * | 2001-04-03 | 2003-07-11 | St Microelectronics Sa | Code de detection et/ou de correction d'erreurs a haute efficacite |
| FR2830637A1 (fr) * | 2001-10-05 | 2003-04-11 | St Microelectronics Sa | Code de detection et/ou de correction d'erreurs a haute efficacite |
| US7543212B2 (en) * | 2004-09-13 | 2009-06-02 | Idaho Research Foundation, Inc. | Low-density parity-check (LDPC) encoder |
| US7489538B2 (en) * | 2005-11-14 | 2009-02-10 | University Of Idaho | Radiation tolerant combinational logic cell |
| US7576562B1 (en) | 2006-06-19 | 2009-08-18 | The United States Of America As Represented By The United States National Aeronautics And Space Administration | Diagnosable structured logic array |
| US8081010B1 (en) | 2009-11-24 | 2011-12-20 | Ics, Llc | Self restoring logic |
| FR2953666B1 (fr) * | 2009-12-09 | 2012-07-13 | Commissariat Energie Atomique | Procede de codage ldpc a redondance incrementale |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5325330A (en) * | 1976-06-14 | 1978-03-09 | Ncr Co | Device for checking and correcting error |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4359772A (en) * | 1980-11-14 | 1982-11-16 | International Business Machines Corporation | Dual function error correcting system |
| DE3122381A1 (de) * | 1981-06-05 | 1982-12-23 | Ibm Deutschland Gmbh, 7000 Stuttgart | Verfahren und einrichtung zur erzeugung von pruefbits zur sicherung eines datenwortes |
| JPS61139846A (ja) * | 1984-12-12 | 1986-06-27 | Hitachi Ltd | 誤り訂正・検出方式 |
-
1986
- 1986-12-18 JP JP61302226A patent/JPH0760394B2/ja not_active Expired - Lifetime
-
1987
- 1987-12-15 US US07/132,993 patent/US4888774A/en not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5325330A (en) * | 1976-06-14 | 1978-03-09 | Ncr Co | Device for checking and correcting error |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH1011307A (ja) * | 1996-06-27 | 1998-01-16 | Nec Corp | 主記憶装置 |
| JP2009070356A (ja) * | 2007-09-13 | 2009-04-02 | United Memories Inc | ハミングコードｈ行列における最小重み付けコード数を増やすべくチェック・ビットのパリティビット幅および追加チェック・ビットの使用によるデータブロックの症候群発生を減らす技術 |
Also Published As
| Publication number | Publication date |
|---|---|
| US4888774A (en) | 1989-12-19 |
| JPH0760394B2 (ja) | 1995-06-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5418796A (en) | Synergistic multiple bit error correction for memory of array chips | |
| US4464753A (en) | Two bit symbol SEC/DED code | |
| JP3325914B2 (ja) | データ用誤り訂正検出方法及びコンピュータ・メモリ用 誤り検出回路 | |
| US6751769B2 (en) | (146,130) error correction code utilizing address information | |
| US5251219A (en) | Error detection and correction circuit | |
| JP2617455B2 (ja) | 符号化装置 | |
| EP0031183A2 (en) | Multi-processor computer system | |
| JPS63155237A (ja) | 誤り訂正・検出方式 | |
| US5768294A (en) | Memory implemented error detection and correction code capable of detecting errors in fetching data from a wrong address | |
| US4689792A (en) | Self test semiconductor memory with error correction capability | |
| JP2001249854A (ja) | メモリ設計のための共有式誤り訂正 | |
| US5691996A (en) | Memory implemented error detection and correction code with address parity bits | |
| EP0147336A2 (en) | Error correcting and detecting system | |
| JPH071640B2 (ja) | 半導体記憶装置の欠陥救済装置 | |
| JPH0529935B2 (ja) | ||
| US5757823A (en) | Error detection and correction for four-bit-per-chip memory system | |
| US5761221A (en) | Memory implemented error detection and correction code using memory modules | |
| US5459740A (en) | Method and apparatus for implementing a triple error detection and double error correction code | |
| EP0300139B1 (en) | Error correcting code for b-bit-per-chip memory with reduced redundancy | |
| US20260050513A1 (en) | System and Method for Protecting Data | |
| EP0603932B1 (en) | Method and apparatus for implementing a quasi-product code with different degrees of protection against errors | |
| US4868829A (en) | Apparatus useful for correction of single bit errors in the transmission of data | |
| US20020059548A1 (en) | Error detection and correction | |
| US12423181B2 (en) | Low complexity system and method for detection and correction of data with additional metadata from corruption | |
| EP0097159B1 (en) | Two bit per symbol sec/ded code |