JPH0760394B2 - 誤り訂正・検出方式 - Google Patents
誤り訂正・検出方式Info
- Publication number
- JPH0760394B2 JPH0760394B2 JP61302226A JP30222686A JPH0760394B2 JP H0760394 B2 JPH0760394 B2 JP H0760394B2 JP 61302226 A JP61302226 A JP 61302226A JP 30222686 A JP30222686 A JP 30222686A JP H0760394 B2 JPH0760394 B2 JP H0760394B2
- Authority
- JP
- Japan
- Prior art keywords
- bit
- error
- matrix
- bits
- error correction
- 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.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、誤り訂正・検出方式に関し、特にブロックエ
ラーを検出するのに好適な１ビットエラー訂正・２ビッ
トエラー検出方式に関する。
ラーを検出するのに好適な１ビットエラー訂正・２ビッ
トエラー検出方式に関する。
従来、１ビットエラーを訂正し、２ビットエラーを検出
し、さらに単一のブロックエラーを検出するSEC-DED-Sb
ED符号（Single bit Error Correcting-Double bit Err
or Detecting-Single b bit byte Error Detecting Cod
e）を用いた誤り訂正・検出方式としては、（１）電子
通信学会論文誌1984年５月号第593頁〜第598頁に示され
る符号を用いたものや、（２）アイ・ビー・エム，ジェ
イ・アール・アンド・ディー,28.2（1984年３月号），
第129頁（IBM,J.R＆D,VOL.28,NO2.p129）に示される符
号を用いたものなどが知られている。
し、さらに単一のブロックエラーを検出するSEC-DED-Sb
ED符号（Single bit Error Correcting-Double bit Err
or Detecting-Single b bit byte Error Detecting Cod
e）を用いた誤り訂正・検出方式としては、（１）電子
通信学会論文誌1984年５月号第593頁〜第598頁に示され
る符号を用いたものや、（２）アイ・ビー・エム，ジェ
イ・アール・アンド・ディー,28.2（1984年３月号），
第129頁（IBM,J.R＆D,VOL.28,NO2.p129）に示される符
号を用いたものなどが知られている。
しかし、これらの誤り訂正・検出方式では共に特定の単
一ブロック内の３ビット以上エラーを検出するのみで、
ブロック間にまたがる３ビット以上エラーについては配
慮されていなかった。
一ブロック内の３ビット以上エラーを検出するのみで、
ブロック間にまたがる３ビット以上エラーについては配
慮されていなかった。
ところで、複数ビットのデータ出力を持つ記憶素子を用
いた半導体記憶装置等において、２種類以上のブロック
分割に対して、それぞれのブロックエラーを検出するこ
とが要求される場合がある。例えば、４ビット構成のIC
メモリを、３ビット構成のドライバーICで駆動する場
合、４ビットブロックに対するブロックエラーが検出で
きると同時に、３ビットブロックに対するブロックエラ
ーも検出できることが望ましい。この場合、上記従来技
術によりSEC-DED-S4ED符号を構成すると、４ビットブロ
ックエラーは検出できるが、４ビットブロック間にまた
がる３ビットブロックエラーは、一般に検出されないと
いう問題がある。
いた半導体記憶装置等において、２種類以上のブロック
分割に対して、それぞれのブロックエラーを検出するこ
とが要求される場合がある。例えば、４ビット構成のIC
メモリを、３ビット構成のドライバーICで駆動する場
合、４ビットブロックに対するブロックエラーが検出で
きると同時に、３ビットブロックに対するブロックエラ
ーも検出できることが望ましい。この場合、上記従来技
術によりSEC-DED-S4ED符号を構成すると、４ビットブロ
ックエラーは検出できるが、４ビットブロック間にまた
がる３ビットブロックエラーは、一般に検出されないと
いう問題がある。
本発明の目的は、このような従来の問題を解決し、ｂビ
ットブロックエラーを検出すると同時に、（ｂ−１）ビ
ット以下のブロックエラーの検出も行え、さらに任意の
連続する（ｂ−１）ビット内のエラー（（ｂ−１）ビッ
トバーストエラー）検出が可能なSEC-DED-SbED符号を用
いた誤り訂正・検出方式を提供することにある。
ットブロックエラーを検出すると同時に、（ｂ−１）ビ
ット以下のブロックエラーの検出も行え、さらに任意の
連続する（ｂ−１）ビット内のエラー（（ｂ−１）ビッ
トバーストエラー）検出が可能なSEC-DED-SbED符号を用
いた誤り訂正・検出方式を提供することにある。
上記問題点を解決するため、本発明では、複数（ｂ）ビ
ットのブロック複数よりなる情報を、次の部分パリティ
行列Ｐを含むパリティ行列に基づいて復号する手段を有
し、該復号手段により１ビットエラー訂正・２ビットエ
ラー検出・同一ブロック内３ビット以上エラー検出・任
意の３ビット以上（ｂ−１）ビット以下バーストエラー
検出を行うことに特徴がある。
ットのブロック複数よりなる情報を、次の部分パリティ
行列Ｐを含むパリティ行列に基づいて復号する手段を有
し、該復号手段により１ビットエラー訂正・２ビットエ
ラー検出・同一ブロック内３ビット以上エラー検出・任
意の３ビット以上（ｂ−１）ビット以下バーストエラー
検出を行うことに特徴がある。
Ｐ＝〔A0…A0A1…A1…Ab…Ab〕 ただし、 Ai（ｉ＝０〜ｂ）は、Ai＝Ｂ・Ciなるｂ×ｂ行列， Ci（ｉ＝０〜ｂ）は、ｂ×ｂ行列 をｉ回掛け合わせたｂ×ｂ行列， ＢはCiの行および列を任意に入れ換えたｂ×ｂ行列であ
る。
る。
本発明においては、複数（ｂ）ビットのブロック複数よ
りなる情報を、上記の部分パリティ行列Ｐ＝〔A0…A0A1
…A1…Ab…Ab〕を含むパリティ行列に基づいて復号する
ことにより、ｂビットブロックエラーおよび（ｂ−１）
ビットバーストエラーが検出できることを以下に詳述す
る。
りなる情報を、上記の部分パリティ行列Ｐ＝〔A0…A0A1
…A1…Ab…Ab〕を含むパリティ行列に基づいて復号する
ことにより、ｂビットブロックエラーおよび（ｂ−１）
ビットバーストエラーが検出できることを以下に詳述す
る。
まず、行列AiおよびＰの性質について説明する。
行列Ci（ｉ＝０〜ｂ）は、 となる。したがって、行列Ｂは次のｂ＋１個の行ベクト
ルD0〜Dbの内、異なるｂ個の行ベクトルを選ぶことによ
り構成できる。
ルD0〜Dbの内、異なるｂ個の行ベクトルを選ぶことによ
り構成できる。
行列Ｂのｋ行目が行ベクトルDj（ｊ＝０〜ｂ）である
時、行列Ｐのｋ行目は、ベクトルDjと行列C0〜Cbとの積
を取ることにより、 となる。以上より、次のことが導かれる。
時、行列Ｐのｋ行目は、ベクトルDjと行列C0〜Cbとの積
を取ることにより、 となる。以上より、次のことが導かれる。
（性質ｉ）行列Aiは、行ベクトルD0〜Dbの内の異なるｂ
個により構成される （性質ii）行列Ｐの一部であるｂ×2b行列 〔Ai Ai+1〕 は、次のｂ＋１個の行ベクトルE0〜Ebの内、異なるｂ個
の行ベクトルを選んで構成できる。
個により構成される （性質ii）行列Ｐの一部であるｂ×2b行列 〔Ai Ai+1〕 は、次のｂ＋１個の行ベクトルE0〜Ebの内、異なるｂ個
の行ベクトルを選んで構成できる。
これらの性質をもとに、行列Ｐを部分行列として含むパ
リティ行列を復号に用いれば、ｂビットブロックエラー
および（ｂ−１）ビットバーストエラーが検出できるこ
とを示す。SEC-DED符号では任意の２ビットエラーが検
出できるので、ｂビットブロック内３ビット以上エラー
および（ｂ−１）ビット以下３ビット以上バーストエラ
ーが検出できることを示す。そのため、ここでは行列Ｐ
により規定されるｂビットのシンドロームSpの重み
（“1"の数）に着目する。性質１より、行列Aiの各列の
重みが１または２であるので、１ビットエラーに対する
Spの重みは１または２である。一方、 （１）ブロック内３ビット以上エラーに対するSpの重み
は３以上である。なぜならば、ブロックを規定する行列
Aiに関する性質ｉより、 （ａ）AiがD0を含まない場合、Spの重みはエラービット
数と等しく、３以上である。
リティ行列を復号に用いれば、ｂビットブロックエラー
および（ｂ−１）ビットバーストエラーが検出できるこ
とを示す。SEC-DED符号では任意の２ビットエラーが検
出できるので、ｂビットブロック内３ビット以上エラー
および（ｂ−１）ビット以下３ビット以上バーストエラ
ーが検出できることを示す。そのため、ここでは行列Ｐ
により規定されるｂビットのシンドロームSpの重み
（“1"の数）に着目する。性質１より、行列Aiの各列の
重みが１または２であるので、１ビットエラーに対する
Spの重みは１または２である。一方、 （１）ブロック内３ビット以上エラーに対するSpの重み
は３以上である。なぜならば、ブロックを規定する行列
Aiに関する性質ｉより、 （ａ）AiがD0を含まない場合、Spの重みはエラービット
数と等しく、３以上である。
（ｂ）AiがD0を含む場合、４ビット以上エラーに対して
は、AiのD0を除く（ｂ−１）行に対応するシンドローム
の重みが３以上である。
は、AiのD0を除く（ｂ−１）行に対応するシンドローム
の重みが３以上である。
（ｃ）AiがD0を含む場合、３ビットエラーに対しては、
AiのD0を除く（ｂ−１）行に対するシンドロームの重み
が２または3,D0行のシンドロームが“1"であるので、Sp
の重みは３以上であるからである。
AiのD0を除く（ｂ−１）行に対するシンドロームの重み
が２または3,D0行のシンドロームが“1"であるので、Sp
の重みは３以上であるからである。
（２）同一の行列Aiを有する２つのブロック間にまたが
るｂビット以下３ビット以上バーストエラーに対するSp
の重みは３以上である。なぜならば、着目するｂビット
バーストに対応する行列を構成する列ベクトルは行列Ai
を構成する列ベクトルに相等しく、上記（１）と同様の
議論に帰着されるからである。
るｂビット以下３ビット以上バーストエラーに対するSp
の重みは３以上である。なぜならば、着目するｂビット
バーストに対応する行列を構成する列ベクトルは行列Ai
を構成する列ベクトルに相等しく、上記（１）と同様の
議論に帰着されるからである。
（３）異なる２つの行列Ai,Ai+1を有する２つのブロッ
ク間にまたがる（ｂ−１）ビット以下３ビット以上バー
ストエラーに対するSpの重みは３以上であるなぜなら
ば、着目する（ｂ−１）ビットバーストに対応する行列
Xijは性質iiより次のｂ＋１個の行ベクトルF0〜Fbの内
の異なるｂ個により構成されるが、 （ａ）XijがF0またはF1を含まない場合、XijのF0,F1を
除く（ｂ−１）行に対応するシンドロームの重みが３以
上である。
ク間にまたがる（ｂ−１）ビット以下３ビット以上バー
ストエラーに対するSpの重みは３以上であるなぜなら
ば、着目する（ｂ−１）ビットバーストに対応する行列
Xijは性質iiより次のｂ＋１個の行ベクトルF0〜Fbの内
の異なるｂ個により構成されるが、 （ａ）XijがF0またはF1を含まない場合、XijのF0,F1を
除く（ｂ−１）行に対応するシンドロームの重みが３以
上である。
（ｂ）XijがF0,F1をともに含む場合、４ビット以上エラ
ーに対しては、XijのF0,F1を除く（ｂ−２）行に対応す
るシンドロームの重みが３以上である。
ーに対しては、XijのF0,F1を除く（ｂ−２）行に対応す
るシンドロームの重みが３以上である。
（ｃ）XijがF0,F1をともに含む場合、３ビットエラーに
対しては、XijのF0,F1を除く（ｂ−２）行に対応するシ
ンドロームの重みが２または3,F0行またはF1行に対応す
るシンドロームのうちいずれか一方が“1"であるので、
Spの重みは３以上であるからである。
対しては、XijのF0,F1を除く（ｂ−２）行に対応するシ
ンドロームの重みが２または3,F0行またはF1行に対応す
るシンドロームのうちいずれか一方が“1"であるので、
Spの重みは３以上であるからである。
以上（１），（２），（３）より、ブロック内３ビット
以上エラーおよび（ｂ−１）ビット以下３ビット以上バ
ーストエラーに対するSpの重みは３以上となり、重み１
または２の１ビットエラーと間違うことなく検出でき
る。
以上エラーおよび（ｂ−１）ビット以下３ビット以上バ
ーストエラーに対するSpの重みは３以上となり、重み１
または２の１ビットエラーと間違うことなく検出でき
る。
以下、本発明の一実施例を、図面により詳細に説明す
る。
る。
第１図は、本発明に用いるパリティ行列の一構成例を示
す図である。ここでは、ｂ＝5,チェックビット８ビット
に対して、符号長60ビットまでとれる。第１図のパリテ
ィ行列は、部分行列Ｐ（上位５行）と、符号長の拡張お
よびSEC-DED機能を付加するための奇数重み列化のため
の下位３行とからなる。第１図のパリティ行列を用いれ
ば、上位５行で決まるシンドロームの重みが、１ビット
エラーに対しては１か２になるのに対して、５ビットブ
ロック内および任意の４ビットバースト内の３ビット以
上エラーに対しては３以上となり、検出可能であること
がわかる。
す図である。ここでは、ｂ＝5,チェックビット８ビット
に対して、符号長60ビットまでとれる。第１図のパリテ
ィ行列は、部分行列Ｐ（上位５行）と、符号長の拡張お
よびSEC-DED機能を付加するための奇数重み列化のため
の下位３行とからなる。第１図のパリティ行列を用いれ
ば、上位５行で決まるシンドロームの重みが、１ビット
エラーに対しては１か２になるのに対して、５ビットブ
ロック内および任意の４ビットバースト内の３ビット以
上エラーに対しては３以上となり、検出可能であること
がわかる。
以下、本実施例において、３バイト（24ビット）のデー
タを４ビット構成のICメモリと６ビット構成のドライバ
／レシーバを使った記憶装置に読み書きするものとす
る。24ビットのデータに対してSEC-DED機能を付加する
にはチェックビットはｂビットあればよいが、４ビット
構成のICメモリを用いるので、チェックビットを８ビッ
トまでとってもICメモリ数を増やすことはない。
タを４ビット構成のICメモリと６ビット構成のドライバ
／レシーバを使った記憶装置に読み書きするものとす
る。24ビットのデータに対してSEC-DED機能を付加する
にはチェックビットはｂビットあればよいが、４ビット
構成のICメモリを用いるので、チェックビットを８ビッ
トまでとってもICメモリ数を増やすことはない。
第２図（ａ）は本発明の一実施例で用いるパリティ行列
を示す図であり、第２図（ｂ）はチェックビット生成行
列を示す図である。
を示す図であり、第２図（ｂ）はチェックビット生成行
列を示す図である。
第２図（ａ）のパリティ行列は、ｂ＝6,チェックビット
８ビットに対して前記手段により構成された符号長42ビ
ットのパリティ行列を32ビットに短縮化したものであ
る。第２図（ａ）のパリティ行列を用いれば、１ビット
エラー訂正・２ビットエラー検出の他、６ビットブロッ
ク内および任意の５ビットバースト内の３ビット以上エ
ラーが検出できる。したがって、１個のICメモリ（４ビ
ット構成）、あるいは１個のドライバ／レシーバ（６ビ
ット構成）が故障しても、誤訂正することなく検出でき
る。第２図（ｂ）の行列は、第２図（ａ）のパリティ行
列に、チェックビット部（C0ないしC7）が単位行列とな
るように周知の等価行操作を施して得られるチェックビ
ット生成行列を示している。
８ビットに対して前記手段により構成された符号長42ビ
ットのパリティ行列を32ビットに短縮化したものであ
る。第２図（ａ）のパリティ行列を用いれば、１ビット
エラー訂正・２ビットエラー検出の他、６ビットブロッ
ク内および任意の５ビットバースト内の３ビット以上エ
ラーが検出できる。したがって、１個のICメモリ（４ビ
ット構成）、あるいは１個のドライバ／レシーバ（６ビ
ット構成）が故障しても、誤訂正することなく検出でき
る。第２図（ｂ）の行列は、第２図（ａ）のパリティ行
列に、チェックビット部（C0ないしC7）が単位行列とな
るように周知の等価行操作を施して得られるチェックビ
ット生成行列を示している。
第３図は、本発明の一実施例を示す誤り訂正・検出装置
の全体構成図である。
の全体構成図である。
記憶装置３へのデータ書込み時、処理装置１より与えら
れた書込みデータ10（SD0〜23）は、チェックビットジ
ェネレータ２に入力される。チェックビットジェネレー
タ２は、第２図（ｂ）の行列に基づいてチェックビット
20（C0〜７）を生成し、生成されたチェックビット20
は、書込みデータ10とともに記憶装置３に書込まれる。
記憶装置３からのデータ読出し時、読出しデータ30（FD
0〜23）および読出しチェックビット31（FC0〜７）は、
シンドロームジェネレータ４に入力される。シンドロー
ムジェネレータ４は、第２図（ａ）のパリティ行列に基
づいてシンドローム40（S0〜７）を生成し、シンドロー
ムデコーダ５に供給する。シンドロームデコーダ５は、
第２図（ａ）のパリティ行列に基づいてシンドローム40
を解読し、１ビットエラー訂正信号50を生成し訂正回路
６に供給するとともに、信号線51を介して処理装置１に
対して訂正可能エラー（CE），訂正不能エラー（UCE）
を報告する。訂正回路６は、１ビットエラー訂正信号50
に基づいて読出しデータ30を訂正し、訂正済データ60を
処理装置１に供給する。
れた書込みデータ10（SD0〜23）は、チェックビットジ
ェネレータ２に入力される。チェックビットジェネレー
タ２は、第２図（ｂ）の行列に基づいてチェックビット
20（C0〜７）を生成し、生成されたチェックビット20
は、書込みデータ10とともに記憶装置３に書込まれる。
記憶装置３からのデータ読出し時、読出しデータ30（FD
0〜23）および読出しチェックビット31（FC0〜７）は、
シンドロームジェネレータ４に入力される。シンドロー
ムジェネレータ４は、第２図（ａ）のパリティ行列に基
づいてシンドローム40（S0〜７）を生成し、シンドロー
ムデコーダ５に供給する。シンドロームデコーダ５は、
第２図（ａ）のパリティ行列に基づいてシンドローム40
を解読し、１ビットエラー訂正信号50を生成し訂正回路
６に供給するとともに、信号線51を介して処理装置１に
対して訂正可能エラー（CE），訂正不能エラー（UCE）
を報告する。訂正回路６は、１ビットエラー訂正信号50
に基づいて読出しデータ30を訂正し、訂正済データ60を
処理装置１に供給する。
第４図は、第３図におけるチェックビットジェネレータ
２の一構成例を示す図である。
２の一構成例を示す図である。
チェックビットジェネレータ２は、８個の９〜18入力排
他的論理和ゲート21〜28より構成される。各排他的論理
和ゲートは、第２図（ｂ）の行列に基づいて、それぞれ
１ビットのチェックビットを生成する。例えば、排他的
論理和ゲート21は、第２図（ｂ）の行列の第１行に基づ
いて、書込みデータSD0〜2,SD5〜7,SD10〜12,SD15〜17,
SD20〜23のモジュロ２の加算をとることにより、チェッ
クビットC0を生成する。
他的論理和ゲート21〜28より構成される。各排他的論理
和ゲートは、第２図（ｂ）の行列に基づいて、それぞれ
１ビットのチェックビットを生成する。例えば、排他的
論理和ゲート21は、第２図（ｂ）の行列の第１行に基づ
いて、書込みデータSD0〜2,SD5〜7,SD10〜12,SD15〜17,
SD20〜23のモジュロ２の加算をとることにより、チェッ
クビットC0を生成する。
第５図は、第３図におけるシンドロームジェネレータ４
の一構成例を示す図である。
の一構成例を示す図である。
シンドロームジェネレータ４は、８個の６〜19入力排他
的論理和ゲート41〜48より構成される。各排他的論理和
ゲートは、第２図（ａ）のパリティ行列に基づいて、そ
れぞれ１ビットのシンドロームを生成する。例えば、排
他的論理和ゲート41は、第２図（ａ）のパリティ行列の
第１行列に基づいて、読出しデータFD4,FD9,FD14,FD19
および読出しチェックビットFC0,FC6,FC7のモジュロ２
の加算をとることによりシンドロームS0を生成する。
的論理和ゲート41〜48より構成される。各排他的論理和
ゲートは、第２図（ａ）のパリティ行列に基づいて、そ
れぞれ１ビットのシンドロームを生成する。例えば、排
他的論理和ゲート41は、第２図（ａ）のパリティ行列の
第１行列に基づいて、読出しデータFD4,FD9,FD14,FD19
および読出しチェックビットFC0,FC6,FC7のモジュロ２
の加算をとることによりシンドロームS0を生成する。
第６図は、第３図におけるシンドロームデコーダ５およ
び訂正回路６の一構成例を示す図である。
び訂正回路６の一構成例を示す図である。
シンドロームデコーダ５は、デコーダ52,論理和ゲート5
3,54,否定ゲート55,論理積ゲート56より構成され、訂正
回路６は読出しデータFD0ないしFD23に対応した24個の
２入力排他的論理和ゲートより構成される。デコーダ52
は、第２図（ａ）のパリティ行列の各列に対応したシン
ドロームパターンを検出して32本の１ビットエラー訂正
信号を生成する。例えば、シンドロームがパリティ行列
のd0列に対応する“00110010"（10進数で50）の時、読
出しデータFD0の１ビットエラー訂正信号T50を付勢す
る。すべての１ビットエラー訂正信号は論理和ゲート54
に入力され、訂正可能エラー報告信号CEが生成される。
訂正不能エラー報告信号UCEは、少くとも１ビットのシ
ンドロームが“1"であり、かつ訂正可能エラーでない
（CE）時付勢される。
3,54,否定ゲート55,論理積ゲート56より構成され、訂正
回路６は読出しデータFD0ないしFD23に対応した24個の
２入力排他的論理和ゲートより構成される。デコーダ52
は、第２図（ａ）のパリティ行列の各列に対応したシン
ドロームパターンを検出して32本の１ビットエラー訂正
信号を生成する。例えば、シンドロームがパリティ行列
のd0列に対応する“00110010"（10進数で50）の時、読
出しデータFD0の１ビットエラー訂正信号T50を付勢す
る。すべての１ビットエラー訂正信号は論理和ゲート54
に入力され、訂正可能エラー報告信号CEが生成される。
訂正不能エラー報告信号UCEは、少くとも１ビットのシ
ンドロームが“1"であり、かつ訂正可能エラーでない
（CE）時付勢される。
このように、本実施例においては、６ビットブロック内
および５ビットバースト内の３ビット以上エラーも検出
できるので、４ビット構成のICメモリおよび６ビット構
成のドライバ／レシーバのいずれの故障も検出可能とな
り、信頼性を上げることができる。また、本実施例で
は、上記検出能力をICメモリ数を増やすことなく実現で
きる。
および５ビットバースト内の３ビット以上エラーも検出
できるので、４ビット構成のICメモリおよび６ビット構
成のドライバ／レシーバのいずれの故障も検出可能とな
り、信頼性を上げることができる。また、本実施例で
は、上記検出能力をICメモリ数を増やすことなく実現で
きる。
以上説明したように、本発明によれば、１ビットエラー
訂正・２ビットエラー検出・ｂビットブロックエラー検
出に加え、（ｂ−１）ビットバーストエラーも検出でき
るので、検出能力の高い誤り訂正・検出を実現できる。
訂正・２ビットエラー検出・ｂビットブロックエラー検
出に加え、（ｂ−１）ビットバーストエラーも検出でき
るので、検出能力の高い誤り訂正・検出を実現できる。
第１図は本発明の誤り訂正・検出方式で用いるパリティ
行列の例を示す図、第２図（ａ），（ｂ）はそれぞれ本
発明の一実施例で用いるパリティ行列を示す図，チェッ
クビット生成行列を示す図、第３図は本発明の一実施例
を示す誤り訂正・検出装置の全体構成図、第４図は第３
図のチェックビットジェネレータの詳細構成図、第５図
は第３図のシンドロームジェネレータの詳細構成図、第
６図は第３図のシンドロームデコーダ／訂正回路の詳細
構成図である。 1:処理装置、2:チェックビットジェネレータ、3:記憶装
置、4:シンドロームジェネレータ、5:シンドロームデコ
ーダ、6:訂正回路。
行列の例を示す図、第２図（ａ），（ｂ）はそれぞれ本
発明の一実施例で用いるパリティ行列を示す図，チェッ
クビット生成行列を示す図、第３図は本発明の一実施例
を示す誤り訂正・検出装置の全体構成図、第４図は第３
図のチェックビットジェネレータの詳細構成図、第５図
は第３図のシンドロームジェネレータの詳細構成図、第
６図は第３図のシンドロームデコーダ／訂正回路の詳細
構成図である。 1:処理装置、2:チェックビットジェネレータ、3:記憶装
置、4:シンドロームジェネレータ、5:シンドロームデコ
ーダ、6:訂正回路。
Claims (2)
- 【請求項１】複数（ｂ）ビットのブロック複数よりなる
情報を、次の部分パリティ行列Ｐを含むパリティ行列に
基づいて復号する手段を有し、該復号手段により１ビッ
トエラー訂正・２ビットエラー検出・同一ブロック内３
ビット以上エラー検出・任意の３ビット以上（ｂ−１）
ビット以下バーストエラー検出を行うことを特徴とする
誤り訂正・検出方式。 Ｐ＝〔A0…A0A1…A1…Ab…Ab〕 ただし、 Ai（ｉ＝０〜ｂ）は、Ai＝Ｂ・Ciなるｂ×ｂ行列， Ci（ｉ＝０〜ｂ）は、ｂ×ｂ行列 をｉ回掛け合わせたｂ×ｂ行列 ＢはCiの行および列を任意に入れ換えたｂ×ｂ行列であ
る。 - 【請求項２】特許請求の範囲第１項記載の誤り訂正・検
出方式において、上記部分パリティ行列Ｐを短縮化した
行列を含むパリティ行列に基づいて復号する手段を有
し、該復号手段により１ビットエラー訂正、２ビットエ
ラー検出、（ｂ−１）ビット以下ブロックのブロックエ
ラー検出を行うことを特徴とする誤り訂正・検出方式。
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 JPS63155237A (ja) | 1988-06-28 |
| JPH0760394B2 true 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) |
Families Citing this family (14)
| 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 |
| JP2820124B2 (ja) * | 1996-06-27 | 1998-11-05 | 日本電気株式会社 | 主記憶装置 |
| 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 |
| US7962837B2 (en) * | 2007-09-13 | 2011-06-14 | United Memories, Inc. | Technique for reducing parity bit-widths for check bit and syndrome generation for data blocks through the use of additional check bits to increase the number of minimum weighted codes in the hamming code H-matrix |
| 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 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4077028A (en) * | 1976-06-14 | 1978-02-28 | Ncr Corporation | Error checking and correcting device |
| 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
Also Published As
| Publication number | Publication date |
|---|---|
| US4888774A (en) | 1989-12-19 |
| JPS63155237A (ja) | 1988-06-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3325914B2 (ja) | データ用誤り訂正検出方法及びコンピュータ・メモリ用 誤り検出回路 | |
| US6751769B2 (en) | (146,130) error correction code utilizing address information | |
| US5418796A (en) | Synergistic multiple bit error correction for memory of array chips | |
| US5768294A (en) | Memory implemented error detection and correction code capable of detecting errors in fetching data from a wrong address | |
| US4775979A (en) | Error correction system | |
| US5251219A (en) | Error detection and correction circuit | |
| JPH0760394B2 (ja) | 誤り訂正・検出方式 | |
| US4631725A (en) | Error correcting and detecting system | |
| JPS5960654A (ja) | エラ−訂正システム | |
| US5537427A (en) | Modular multiple error correcting code system | |
| US5386425A (en) | Two-dimensional error correcting method and decoder | |
| US5691996A (en) | Memory implemented error detection and correction code with address parity bits | |
| KR950033822A (ko) | 에러검출 및 정정용 반도체 메모리 장치 | |
| US5757823A (en) | Error detection and correction for four-bit-per-chip memory system | |
| US5450423A (en) | Data error correcting/detecting system and apparatus compatible with different data bit memory packages | |
| US5761221A (en) | Memory implemented error detection and correction code using memory modules | |
| JPH05158722A (ja) | 誤り検出・訂正方式 | |
| US5459740A (en) | Method and apparatus for implementing a triple error detection and double error correction code | |
| KR860003576A (ko) | Pcm 신호의 에러 프라그 처리를 위한 방법과 장치 | |
| US5608740A (en) | Error correcting method | |
| JP2684031B2 (ja) | データの復号化方法 | |
| JPS6345642A (ja) | 誤り訂正・検出方式 | |
| JPS58218255A (ja) | 符号誤り検出訂正方式 | |
| SU763975A1 (ru) | Запоминающее устройство с обнаружением и исправлением ошибок | |
| JPS5857783B2 (ja) | 誤り検出訂正方式 |