JPS6345642A - 誤り訂正・検出方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、誤り訂正・検出方式に関し、特にブロックエ
ラーを検出するために好適な１ビットエラー訂正・２ビ
ット工ラー検出方式に関するものである。

〔従来の技術〕

従来、１ビットエラーを訂正し、２ビットエラーを検出
し、さらに単一のブロックエラーを検出する５ＥＣ−Ｄ
ＥＤ−３ｂＥＤ符号（Ｓ　ｉｎｇｌｅ　ｂｉヒＥ　ｒｒ
ｏｒ　　Ｃｏｒｒｅｃｔｉｎｇ　−Ｄ　ｏｕｂｌｅ　　
ｂｉｔ　　Ｅ　ｒｒｏｒＤｅｔｅｃｔｉｎｇ　−Ｓ　ｉ
ｎｇｌｅ　　　ｂ　　　ｂｉし　　ｂｙｔｅ　　　Ｅ　
ｒｒｏｒＤ　ｅｔａｃｔｉｎｇ　　Ｃｏｄｅ）を用いた
誤り訂正・検出方式％式％ ６７−　Ｄ、　Ｎ　ｏ、　５）第５９３頁〜第５９８頁
に示す符号を用いるもの。

（ロ）アイ・ビー・エム、ジエイ・アール・アンド・デ
イ−、２８，２（１９８４年３月号）第１２４頁〜第１
３１１頁（Ｖｏｌ、２８．Ｎｏ、２）に示される符号を
用いるもの。

等が知られている。

５ＥＣ−ＤＥＤ−３ｂＥＤ符号は、主記憶装置に広く用
いられている１ビット誤り訂正・２ビット誤り検出符号
（ＳＥＣ−ＤＥＤ符号）に、複数（ｂ）ピッ１への塊り
、例えばバイトの誤りの検出能力を付加した符号であっ
て、この符号は複数ビットのデータ出力を持つ記憶素子
を用いた半導体記憶装置の高信頼化に役に立つ。上記（
イ）の新しい５ＥＣ−ＤＥＤ−３））ＥＤ符号では、最
大符号ビット長Ｌｏは、検査ビット数をｒ（ｒ≧ｂ＋２
）、バイト長をｂとすると、Ｌｏ＝　（ｂ＋２）　　・
ｂ・２ｒ−１）−２で与えられる。そして、バイト長り
≧１６ビットで、従来の符号より長い符号長を持つ。ま
た、検査ビット数ｒ＝ｂ＋２では、従来の符号とは異な
って、符号化・復号回路の高速化とＬＳＩ化に適した巡
回性最小重み符号を与える。

しかし、これら（イ）（ＣＩ）の誤り訂正・検出方式で
は、共に特定の単一ブロック内の３ビット以上のエラー
を検出するのみであり、ブロック間にまたがる３ビット
以上のエラーについては、何も配慮されていなかった。

〔発明が解決しようとする開通点〕

ところで、２種類以上のブロック分割に対して。

各々ブロックエラーを検出することが要求される場合が
ある。例えば、４ビット構成のＩＣメモリを、３ビット
構成のドライバＩＣで駆動する場合、４ビットブロツク
に対するブロックエラーが検出できると同時に、３ビッ
トブロツクに対するブロックエラーも検出できることが
望ましい。この場合、前述の従来技術により５ＥＣ−Ｄ
ＥＤ−８４ＥＤ符号を構成すると、４ビットブロツクエ
ラーは検出できるが、４ビットブロック間にまたがる３
ビットブロツクエラーは、一般に検出できない。

本発明の目的は、このような従来の問題を解決し、１ビ
ットエラー訂正・２ビットエラー検出、ｂビットブロッ
クエラー検出に加えて、（ｂ−１）ビットバーストエラ
ーも検出することができる５ＥＣ−ＤＥＤ−８ｂＥＤ符
号を用いた誤り訂正・検出方式を提供することにある。

〔問題点を解決するための手段〕

上記目的を達成するため、本発明の誤り訂正・検出方式
は、ｂビットのブロック複数よりなる情報を、次のマト
リクスＰを部分マトリクスとして含むバリテイマトリク
スに基づいて復号することに特徴がある。

ｐ＝　［Ａｏ　・・・ＡｏＡｌ　・・・・Ａ１・・・・
・・・・Ａｂ−１・・・・Ａｂ−ＩＩ・・・・Ｉ］ただ
し、Ａｉ　　（ｉ＝ｏ　〜ｂ−１）は、ｂｘｂＩは、ｂ
ｘｂ単位マトリクスである。

〔作　　用〕

本発明においては、（ｂ−１）ビット以下のブロックエ
ラーも検出できるように、任意の連続する（ｂ−ｉ）ビ
ット内のエラー（これを、（ｂ−１）ビットバーストエ
ラーと呼ぶ）を検出できる機能を持たせる。以下、ｂビ
ットブロックエラーおよび（ｂ−１）ビットバーストエ
ラーが検出できる原理を詳述する。５ＥＣ−ＤＥＣ符号
は、任意の２ビットエラーが検出できるので、ｂビット
ブロック内の３ビット以上のエラー、および（ｂ　−１
）ビット以下３ビット以上のバーストエラーが検出でき
ればよい。

本発明においては、部分マトリクスＰにより規定される
ｂビットのシンドロームＳｐの′１″の数、すなわち重
みは、１ビットエラーに対しては１あるいは２である。

一方、次の事項により、ｂビットブロック内、および（
ｂ−１）ビットバースト内の３ビット以上のエラーが全
て検出できることを示す。

（イ）ｂビットブロック内３ビット以上のエラーに対す
るｓｐの重みは、Ａ□およびＩの構成により３以上とな
る。

（ロ）同一の部分マトリクスＡｉあるいは■を有する２
つのｂビットブロック間にまたがる（ｂ−１）ビット以
下３ビット以上エラーに対するｓｐの重みは（イ）に準
じ３以上となる。

（ハ）異なる部分マトリクスＡ工およびＡ工や１を有す
る２つのｂビットブロン９間にまたがる（ｂ−１）ビッ
トバーストに対するｂＸ（ｂ−１）部分マトリクスＡ′
は、その行２列を入れ換えると。

次のようになる。

（ｂ−ｔ） このバースト内の３ビット以上エラーに対するＳｐの重
みは３以上となる。

（ニ）異なる部分マトリクスＡｂ−１および工を有する
２つのｂビットブロン９間にまたがる（ｂ−１）ビット
バーストに対するｂｘ（ｂ−１）部分マトリクスＡ”は
、その行２列を入れ換えると、次のようになる。

（ｂ−１） このバースト内の３ビット以上エラーに対するＳｐの重
みは３以上となる。

（イ）〜（ニ）より、ｂビットブロック内および（ｂ−
１）ビットバースト内の３ビット以上エラーは、全て検
出可能である。

〔実施例〕

以下、本発明の一実施例を１図面により詳細に説明する
。第１図は、本発明に用いるバリテイマトリクスの一構
成例を示す図である。ここでは、ｂ＝５．チエツクビッ
ト８ビットに対して、符号長６０ビットまでとれる。

第１図のパリティマトリックスは、部分７１ヘリク、１
．Ｐ（上位５桁）と符号長の拡張および５ＥＣ−ＤＥＣ
機能を付加するための奇数重み列化のための下位３行と
からなる１周知のように、第１図の符号語において、シ
ンドロームＳｏ、Ｓ工・・・Ｓ７は、対応する行の符号
ｃｉ、（ｔ：ｏ、ｉ、・・・・５１）およびチエツクビ
ットＣｉ（ｉ　＝　Ｏ、・・・７）の排他的論理和をと
った値であり、情報符号に誤りがないときには、これら
は全て０となる。

一方、情報符号に誤りがある場合、１ビット誤りでは誤
りのある行のＳ工の重みが必ず１となり、２ビット誤り
では誤りのある行のＳ、の重みは１とならずに０となる
。従って、１ビット誤り訂正、２ビット誤り検出が可能
である。すなわち、１ビットの誤りがあれば、シンドロ
ームＳ。−８７のうち１となるビット数が奇数であり、
２ビット誤りがあれば５ｏ−８７のうちｌとなるビット
数が偶数である。本実施例では、この他に、第１図のバ
リテイマトリクスを用いれば、上位５行で決まるシンド
ロームの重みが、１ビットエラーに対しては１または２
になるのに対して、５ビットブロツク内および任意の４
ビットバースト内の３ビット以上エラーに対しては３以
上となり、検出可能であることがわかる。

第２図（ａ）（ｂ）は、本発明で用いら九るバリテイマ
トリクス例およびチエツクビット生成マトリクス例をそ
れぞれ示す図である。

第２図の実施例では、３バイト（２４ビット）のデータ
を４ビット構成のＩＣメモリと６ビット構成のドライバ
／レシーバを使用した記憶装置に読み書きするものとす
る。２４ビットのデータに対して５ＥＣ−ＤＥＤ機能を
付加するためには、チエツクビットは６ビットあればよ
いが、４ビット構成のＩＣメモリを用いるので、チエツ
クビットを８ビットまでとってもＩＣメモリ数を増加す
ることはない。第２図（ａ）では１本実施例で使用され
るバリテイマトリクスを示しており、ｂ＝６゜チエツク
ビット８ビットに対して、上記方法により構成された符
号長４２ビットのバリテイマトリクスを３２ビットに短
縮化したものである。第２図（ａ）のバリテイマトリク
スを用いれば、１１ヒツトエラー訂正・２ビットエラー
検出の他に、６ビットブロック内および任意の５ビット
バースト内の３ビット以上エラーが検出できる。従って
、１個のＩＣメモリ（４ビット構成）、あるいは１個の
ドライバ／レシーバ（６ビット構成）が故障しても、誤
訂正することなく検出できる。

第２図（ｂ）では、第２図（ａ）のバリテイマトリクス
に、チエツクピット部（ＣＯ〜Ｃ７）が単位７１−リク
スとなるように、周知の等偏行操作を施して得られるチ
エツクピット生成マｊ−リクスを示している。

第３図は、本発明の一実施例を示す誤り訂正検出装置の
全体構成図である。

記憶装置３へのデータ書き込み時、処理装置１より与え
られた書き込みデータ１０（ＳＤＯ〜２３）は、チエツ
クビットジェネレータ２に入力される。

チエツクピットジェネレータ２は、第２図（ｂ）のマト
リクスに基づいてチエツクピッｌ−２０（Ｃ０〜７）を
生成し、生成されたチエツクピット２゜は、書き込みデ
ータ１０とともに記憶装置３に書き込まれる。

記憶装置３からのデータ読み出し時には、データ３０（
ＦＤＯ〜２３）および読み出しチエツクピット３１（Ｆ
ＣＯ〜７）は、シンドロームジェネレータ４に入力され
る。シンドロームジェネレータ４は、第２図（、）のバ
リテイマトリクスに基づいてシンドローム４０（Ｓｏ〜
７）を生成し、シンドロームデコーダ５に供給する。シ
ンドロームデコーダ５は、第２図（、）のバリテイマト
リクスに基づいてシンドローム４０を解読し、１ビット
工ラー訂正信号５０を生成し、訂正回路６に供給すると
ともに、線５１を介して処理袋［１に対して訂正可能エ
ラー（ＧＥ）、訂正不可能エラー（ＵＣＥ）を報告する
。訂正回路６は、１ビット工ラー訂正信号５０に基づい
て読み出しデータ３０を訂正し、訂正済データ６０を処
理装置１に供給する。

第４図は、第３図におけるチエツクビットジェネレータ
の構成例図である。チエツクビットジェネレータ２は、
８個の９〜１７人力の排他的論理和ゲート２１〜２８で
構成されている。各排他的論理和ゲートは、第２図（ｂ
）のマトリクスに基づいて、それぞれ１ビットのチエツ
クピットを生成する。例えば、排他的論理和ゲート２１
は、第２図（ｂ）のマトリクスの第１行に基づいて、書
き込みデータＳＤＯ〜ＳＤ９，５Ｄ１２〜５０１４゜５
Ｄ１８，５Ｄ１９のモジュロ２の加算をとることにより
、チエツクピッｌ−〇〇を生成する。

第５図は、第３図におけるシンドロームジェネレータの
構成例を示す図である。

シンドロームジェネレータ２は、８個の７〜２１人力排
他的論理和ゲート４１〜４８から構成される。これらの
排他的論理和ゲートは、第２図（、）のバリテイマトリ
クスに基づいて、それぞれ１ビットのシンドロームを生
成する９例えば、排他的論理和ゲート４１は、第２図（
、）のバリテイマトリクスの第１行に基づいて、読み出
しデータＦＤＯ〜ＦＤ５．ＦＤＩ　１，５Ｄ１６．ＦＤ
２１および読み出しチエツクビットＦＣ２，ＦＣ７のモ
ジュロ２の加算をとることにより、シンドロームを生成
する。

第６図は、第３図におけるシンドロームデコーダおよび
訂正回路の構成例図である。シンドロームデコーダ５は
、デコーダ５２、論理和ゲート５３．５４．否定ゲート
５５、論理積ゲート５６より構成され、また訂正回路６
は、読み出しデータＦＤＯ〜Ｆ′Ｄ２３に対応した２４
個の２人力排他的論理和ゲートより構成される。デコー
ダ５２は、第２図（ａ）のバリテイマトリクスの各列に
対応したシンドロームパターンを検出して、３２本の１
ビット工ラー訂正信号を生成する。例えば、シンドロー
ムがバリテイマトリクスの（１０列に対応する’１００
０００１１”（１０進数では１３１）のとき、読み出し
データＦＤＯの１ビット工ラー訂正信号Ｔ１３１を付勢
する。全ての１ビット工ラー訂正信号は論理和ゲート５
４に入力され、訂正可能エラー報告信号ＣＥが生成され
る。訂正不能エラー報告信号ＵＣＥは、少なくとも１ビ
ット・のシンドロームがＩＩ　１　′ｌであり、かつ訂
正可能エラーでない（］　）時に付勢される。

本実施例においては、６ビットブロツク内および５ビッ
トバースト内の３ビット以上エラーも検出できるので、
４ビット構成のＩＣメモリおよび６ビント構成のドライ
バ／レシーバのいずれの故障も検品可能となり、信頼性
を向上させることができる。また、本実施例では、上記
の検出能力をＩＣメモリ数を増加することなく、実現す
ることができる。

Ｃ発明の効果〕 以上説明したように、本発明によれば、１ビットエラー
訂正・２ビットエラー検出・ｂビットブロックエラー検
出に加えて、（ｂ−１）ビットバーストエラーも検出で
きるので、検出能力の高い誤り訂正・検出回路を実現で
きる。

【図面の簡単な説明】 第１図は本発明の誤り訂正・検出方式で用いられるバリ
テイマトリクス例を示す図、第２図は本発明の一実施例
を示すバリテイマトリクスおよびチエツクビット生成マ
トリクスを示す図、第３図は本発明の一実施例を示す誤
り訂正・検出回路の全体構成図、第４図は第３図におけ
るチエツクビットジェネレータの詳細図、第５図は第３
図におけるシンドロームジェネレータの詳細図、第６図
は第３図におけるシンドロームデコーダおよび訂正回路
の詳細図である。 ｌ：処理装置、２：チエツクビットジェネレータ、３：
記憶装置、４ニシンドロームシエネレータ、５：シンド
ロームデコーダ、６：訂正回路。 第１図 第　　　２　　　図　　　（ａ） 第３図 第４図 ５Ｆ）Ｏ−２３ 第　　　　　５　　　　　図

Claims (1)

1. 【特許請求の範囲】 １、複数ビット（ｂビットとする）のブロック複数より
   なる情報を、次の部分マトリクスＰを含むバリテイマト
   リクスに基づいて復号する手段を有し、該復号手段によ
   り１ビットエラー訂正・２ビットエラー検出・同一ブロ
   ック内３ビット以上エラー検出・任意の３ビット以上（
   ｂ−１）ビット以下のバーストエラー検出を行うことを
   特徴とする誤り訂正・検出方式。 Ｐ＝〔Ａ＿０‥Ａ＿０Ａ＿１…Ａ＿１‥‥Ａ＿ｂ＿−＿
   １……Ａ＿ｂ＿−＿１Ｉ…‥Ｉ〕 ただし、Ａ＿ｉ（ｉ：０〜ｂ−１）は、ｂ×ｂマトリク
   ス▲数式、化学式、表等があります▼ の各行を列方向にｉビッ ト巡回置換したマトリク ス、 Ｉは、ｂ×ｂの単位マトリクスである。