JPS5918739B2 - エラ−訂正処理装置 - Google Patents

Description

【発明の詳細な説明】 本発明は、エラー訂正処理装置、特にをビット・１バー
ストブロツクエラー訂正／２バーストブロツクエラー検
出コードを採用したエラー訂正処理装置において、単位
検査マトリクスを元にしてｐブロック分のチェック・ビ
ットを附加してＮ・（ｐ＋１）ブロック分の検査マトリ
クスを使用するようにし、複数個のＮブロック情報に対
してエラー・ブロック検出回路を共通化することによつ
て回路構成を簡単化したエラー訂正処理装置に関するも
のである。

例えば大容量の記憶装置においては、動作の信頼度を向
上するために、エラー訂正／検出コードが広く採用され
ている。

しかし一般には１ビット・エラー訂正／２ビット・エラ
ー検出を行なうコードが多く用いられているに過ぎない
。このため、複数ビット分を１個のメモリ素子上に格納
して１ブロック情報とし、これらブロック情報を複数個
分用いて１ワードを構成せしめる如き場合を考えると、
１つのメモリ素子に障害が発生すると１ブロック全体の
情報に障害を生じエラー訂正は不能となつてしまう。こ
のことを考慮して１プロツクｂビツト内のどのようなエ
ラーでも訂正可能にするため、Ｄ．Ｃ．ＢＯｓｓｅｎに
よる［ｂ一隣接エラー訂正コード」が．ＢＭＪ．Ｒｅｓ
．ＤｅｖｅｌＯｐ．？ＶＯｌ．ｌ４？腐４ラＰｐ４Ｏ２
−４０９，１９７０に示されている。

しかし、該コードの場合、情報ビツトを（２ｂ−１）プ
ロツク即ち（２ｂ−１）・ｂビツトまでしかとれないと
いう制限がある。例えばｂ＝４とした場合情報ビツト数
ｍは６０となりチエツク・ビツト数ｋは８となる。一方
記憶装置においてワード中の１プロツクはｔビツトによ
つて構成することが適当であり、１プロツクを４ビツト
とし、８プロツクを１ワードとすると、１ワード６４ビ
ツトとなる。即ち上記ｂ＝４としたコードでは必要な情
報ビツト数が不足する。このため、ｂ＝８とすればよい
が、ｂ＝８とすると、チエツク・ビツト数ｋ−１６とな
り、上記１ワード６４ビツトに対して使用するコードと
しては効率が悪くかつ装置が複雑となる。

そこでｂ＝４の場合において４次の既約多項式を用いる
代わりに、ＨＯｎｇ＆Ｐａｔｅｌによる「拡張されたｂ
隣接エラー訂正コード（ＩＥＥＥＴｒａｎｓ．ＣＯｍｐ
ｕｔ．，ｖＯｌ．Ｃ−２１，滝１２，ｐｐ．１３２２−
１３３１．Ｄｅｃ．１９７２）」にもとずいて５次の多
項式を用いると、情報ビツトを３１プロツク即ち１２４
ビツトまでとることができ、しかもチエツク・ビツト数
が９ビツトとなり効率が良い。即ち装置もｂ＝８の場合
にくらべて簡単となる。しかし例えばｂ＝４に対して９
個のチエツク・ビツトを附加するには３プロツク（１プ
ロツク・４ビツト）分を必要とし、チエツク・ビツト数
１２ビツトの場合とプロツク数は同じとなつてしまう。
ＨＯｎｇ＆Ｐａｔｅｌによれば、ｂ＝４、チエツク．ビ
ツト数１２ビツトの「拡張されたｂ一隣接コード」は情
報ビツトとして２７０プロツク即ち１０８０ビツトまで
とることができる。

第１図は該ｂ＝４、チエツク・ビツト数１２ビツトの検
査マトリクスを表わし、情報ビツトに対する上半２５５
プロツクには８次の既約多項式を用い、下半１５プロツ
クには４次の既約多項式を用いるようにしている。情報
ビツトとして例えば１２０ビツト分で足りるような場合
には、上記第１図に示す検査マトリクス（以下Ｈマトリ
クスという）を第２図図示の如くより簡単化することが
可能である。

第２図図示のＨマトリクスは、第１図に示すＨマトリク
スの上半２５５プロツク中から１５プロツク分を抽出し
、下半１５プロツクとチエツク・プロツクとをそのまま
採用したものと考えてよい。しかし、該第２図図示のＨ
マトリクスの場合、上半１５プロツクに対して８次の既
約多項式が用いられ、下半１５プロツクに対して４次の
既約多項式が用いられていることから、エラー訂正を行
なう回路構成が複雑となる。即ち第２図図示のビツトＡ
Ｏ（０）ないしＢｌ４（３）に対して夫々異なつた回路
を用いる必要がある。このことから、例えばＮプロツク
分の情報ビツト数に対応する単位検査マトリクスを基本
とし、これらを巡回させることによつて情報ビツト数を
拡張することが藤原英二氏によつて提案されている（藤
原：「高信頼度メイン・メモリの一構成失、電子通信学
会ＥＣ７５−２１）。

しかし、該方式を用いる場合も、復号化回路が必らずし
も簡単でない。本発明は、上記の点を考慮してＮプロツ
ク分の情報ビツト数に対応する単位Ｈマトリクスをその
まま複数個使用する形のＨマトリクスを用いると共に必
要とするチエツク・ビツト数を低減せしめて、エラー訂
正回路構成を簡単化したエラー訂正処理装置を提供する
ことを目的としている。

そしてそのため、本発明のエラー訂正処理装置はｂビツ
ト・１バーストプロツクエラ一訂正／２バーストプロツ
クエラ一検出コードを採用した情報転送システムにおけ
るエラー訂正処理装置において、Ｎプロツク分の情報ビ
ツト数とｍプロツク分のチエツク・ビツト数とに対応す
る単位検査マトリクスを元にしてＭ．ｐプロツク分のチ
エツク・ビツトを附加することなく単にｐプロツク分の
チエツク・ビツトのみを附加し該単位検査マトリクスの
一部を同じ行にかつ一部を異なる行に繰返し配列した拡
大したＮ・（ｐ＋１）プロツク分の情報ビツト数に対応
する検査マトリクスを使用すると共に、該検査マトリク
スを使用して得られたシンドロームにもとずいて、上記
チエツク・ビツト部分または上記Ｎ・（ｐ＋１）プロツ
ク分の情報ビツトを（ｐ＋１）個に区分したいずれの区
分範囲内にエラー・プロツクが存在するかを検出するエ
ラ一範囲抽出回路、および上記区分範囲内のいずれのプ
ロツクにエラーが存在するかを検出するエラー・プロツ
ク検出回路をもうけ、上記エラー範囲抽出回路出力と上
記エラー・プロツク検出回路出力とによりエラー・プロ
ツクのバースト・エラーを訂正するようにしたことによ
り、より少ないチエツク・ビツトを附加した形で訂正可
能な情報ビツト数を拡大したことを特徴としている。以
下第３図以降を参照して説明する。第３図は８プロツク
の情報ビツトを単位とし１６プロツク分に拡大した本発
明は用いる一実施例Ｈマトリクス、第４図は第３図図示
のＨマトリクスを具体的に示したＨマトリクス、第５図
は本発明による他の一実施例Ｈマトリクス、第６図は第
３図即ち第４図図示のＨマトリクスを用いた場合におけ
るエラー発生態様にもとずくシンドロームの状態をまと
めた説明図、第７図ＡないしＤは本発明のエラー訂正処
理装置の一実施例構成、第８図は第７図Ａに示す一部回
路を具体的に表わした一実施例を示す。

本発明の場合、第３図図示の如く例えばｂ＝４とし４次
の既約多項式を用いて構成した８プロツク分の情報ビツ
トに対する単位Ｈマトリクス１を元にしてチエツク・ビ
ツト２を１プロツク分だけ附加することによつて、全体
として８Ｘ２プロツク分の情報ビツトに対するＨマトリ
クスを構成し、該Ｈマトリクスを用いるようにしている
。

即ち、マトリクスの上半と下半とは図示第１横行と第２
横行とを交換するだけで同じ構成をとり、エラー訂正回
路に必要な構成を簡単化せしめている。第３図に示すお
よびＴは夫々４Ｘ４ビツトのマトリクスよりなり、これ
を具体化すると第４図図示の如くなるものである。なお
、本発明の場合、Ｈマトリクスの上半と下半との任意の
横行を交換して構成したものであればよく、第５図図示
の如きＨマトリクスを用い得ることは言うまでもない。
以下第４図に示すＨマトリクスを使用するものとして説
明をつづける。例えば記憶装置に格納された１ワードの
内容をＣＯツＣ１？Ｃ２？Ｃ３｝とし）かつ１プロツク
の内容をａ１｛Ａｉ（０），・・・・・・Ａｉ（３）｝
，Ｂｉ｛Ｂｉ（０），・゜゜．・・Ｂｉ（３）｝，Ｃｉ
｛Ｃｉ（０），・・・・・・Ｃｉ（３）｝とするとき、
該１ワードの内容Ｗを読出した後第４図図示のＨマトリ
クスを乗すると次のシンドロームＳが得られる。

即ちここでシンドロームＳ｛ＳＯ，Ｓｌ，Ｓ，，Ｓ３｝
で表わされ、各要素ＳｉはＳｉ｛Ｓｉ（０），・・・・
・・Ｓｉ（３）｝である。

本発明の場合、上記１６プロツク内のいずれにエラーが
存在するかによつて、上記シンドロームＳＯ，Ｓｌ，Ｓ
２，Ｓ３は第６図図示の如きパターンをとる。

図中例えばエラー・プロツクＡｉとあるのは読出された
１ワード情報中のプロツクＡ。ないしＡ３のいずれか１
つにエラーが存在することを示し、ＣＯとあるのはプロ
ツクＣ。にエラーが存在することを示し、ＣＯ，Ｃｌと
あるのはプロツクＣ。とＣ，とに夫々エラーが存在する
ことを示し、Ａｉ，ｃＯとあるのはプロツクＡ。ないし
Ａ３のいずれか１つとプロツクＣ。とに夫々エラーが存
在することを示し、ＡｉａｊとあるのはプロツクＡ。な
いしＡ３内のいずれか２つにエラーが存在することを示
し、ＡｉｂｊとあるのはプロツクＡＯないしＡ３のいず
れか１つとプロツクＢ。ないしＢ３のいずれか１つとに
エラーが存在することを示している。またｅ１およびＥ
２は夫々エラーが存在するときにシンドロームＳｉ（４
ビツト）に現われるパターンを表わしている。１プロツ
クにおけるバーストエラ一発生時には、Ａｉ，ｂｉ，ｃ
ｉの３群中のどのプロツクにエラーを含んでいるかによ
り第６図図示の如く各種のシンドロームのパターンが現
われる。

即ち、（１）プロツクＣｉ中にエラーが生じているとき
には、シンドロームＳ。

ないしＳ３のうち、Ｓｉのみがオール零とならない。（
２）プロツクＡｉ中にエラーが生じているときにはシン
ドロームＳ。

，Ｓ２，Ｓ３が夫々オール零でなく、シンドロームＳ１
はオール零となり、かつ次の式が成立する。ト そして、シンドロームＳ。

がプロツクＡ。ないしＡ７中の第１番目のプロツクにエ
ラーがあることを表わすパターンとなつている。（３）
プロツクＢｉ中にエラーが生じているときには、シンド
ロームＳｌ，Ｓ２，Ｓ３が夫々オール零でなく、シンド
ロームＳ。

はオール零となり、かつ次の式が成立する。Ｙ８轟
可 ｙυ そして、シンドロームＳ１がプロツクＢ。

ないしＢ７中の第１番目のプロツクにエラーがあること
を表わすパターンとなつている。（４）シンドロームＳ
。

ないしＳ３がすべてオール零の場合には、エラーが存在
しないことを表わしている。（５）そして上記以外の場
合、訂正不能なエラーとして検出される。

第７図ＡないしＤは上記（１）ないし（５）にもとずい
て、１プロツクーバーストエラ一を訂正する本発明の一
実施例構成を示している。

図中、１０はシンドローム発生器、１１はエラー範囲抽
出回路、１２はエラー・プロツク検出回路、１３は訂正
不能エラー検出回路、１４はエラー・チエツクプロツク
訂正回路、１４−０ないし１４−３は夫々プロツクＣ。

ないしＣ３訂正回路、１５はエラー情報プロツク訂正回
路、１５ａ−０ないし１５ａ−７は夫々プロツクＡ。な
いしＡ７訂正回路、１５ｂ−０ないし１５ｂ−７は夫々
プロツクＢ。ないしＢ７訂正回路、１６ないし１７は夫
々オア回路、１８ないし２７は夫々ノア回路、２８ない
し３１は夫々排他的オア回路網、３２ないし４４は夫々
アンド回路、４５ないし４７は夫夫排他的オア回路を表
わしている。１ワードを構成するビツトＡ。

（０）ないしＣ３（３）よりなる情報に対して、シンド
ローム発生器１０において第４図図示のＨマトリタスを
作用せしめると、該Ｈマトリクスの第１横行に対応して
ビツトＳ。（０）ないしＳ。（３）よりなるシンドロー
ムＳ。が発生され、Ｈマトリクスの第２横行に対応して
ビツトＳ１（０）ないしＳ１（３）よりなるシンドロー
ムＳ１が発生され、Ｈマトリクスの第３横行に対応して
ビツトＳ２（０）ないしＳ２（３）よりなるシンドロー
ムＳ２が発生され、Ｈマトリクスの第４横行に対応して
ビツトＳ３（０）ないしＳ３（３）よりなるシンドロー
ムＳ３が発生される。これら発生されたシンドロームＳ
。

ないしＳ３は夫々エラー範囲抽出回路１１に供給される
。このときアンド回路３２が論理「１」を発生するとき
、シンドロームＳ。ないしＳ３はすべてオール零であり
、エラーが存在しないことを表わす。またアンド回路３
８の出力１１が論理「１」を発生するとき、プロツクＡ
ｉ内にエラーが存在することを表わし、アンド回路３７
の出力１２が論理「１」を発生するとき、プロツクＢｉ
内にエラーが存在することを表わす。更にアンド回路３
６の出力１３−０が論理［１」を発生するときプロツク
Ｃ。に、アンド回路３５の出力１３−１が論理「１」を
発生するときプロツクＣ１に、アンド回路３４の出力１
３−２が論理［１」を発生するときプロツクＣ，に、ア
ンド回路３３の出力１３−３が論理［１」を発生すると
きプロツクＣ３に夫夫エラーが存在することを表わす。
シンドロームＳ。

とＳ１とはオア回路１６に供給されその出力Ｓ。ｅｓｌ
と、シンドロームＳ２とＳ３とが夫々エラー・プロツク
検出回路に供給される。そして出力１５−０が論理「１
」を示すときプロツクＡ。かＢ。かにエラーがあること
を表わし、同様に出力１５−７が論理［１」を示すとき
プロツクＡ７かＢ７かにエラーがあることを表わす。第
７図Ｃはエラー・チエツクプロツク訂正回路を表わし、
例えばプロツクＣ。

訂正回路１４−０においては出力１３−０が論理「１」
となる条件のもとにおいてシンドロームＳ。とプロツク
Ｃ。の内容とが比較され、エラー訂正された出力Ｃ。を
発生する。プロツクＣ１ないしＣ３についても同様にも
しもエラーが存在すれば夫々訂正された出力を得ること
ができる。第７図Ｄはエラー情報プロツク訂正回路を表
わし、例えばプロツクＡ。

訂正回路１５ａ−０においては、出力１１と１５−０と
が共に論理［１］なる条件でシンドローム１４即ちＳ〔
１Ｓ１とプロツクＡ。の内容とが比較され、エラー訂正
きれた出力Ａ。を発生する。またプロツクＢ。訂正回路
１５ｂ−０においては、出力１２と１５−０とが共に論
理「１」なる条件でシンドローム１４とプロツクＢ。の
内容とが比較され、エラー訂正された出力Ｂ。を発生す
る。プロツクａ１ないしＡ７およびｂ１ないしＢ７につ
いても同様にもしもエラーが存在すれば夫々訂正された
出力を得ることができる。更に訂正不能エラー検出回路
１３は、２プロツクにまたがるエラー発生状態を検出す
る。

第８図は、第１図に示すエラー範囲抽出回路１２の詳細
を示している。

本発明の場合第４図に示す図示矢印１．１５１′，と「
、・・・・・・の第３横行と第４横行とは同じマトリク
スとなつていることから、共通の回路２８，２９，２２
，２３，３９や３０，３１，２４，２５，４０を用いる
ことが可能となる。以上説明した如く、本発明によれば
第４図図示の如きＨマトリクスを用いることにより、第
７図に示す如くエラー範囲抽出回路とエラー・プロツク
検出回路とを用いることができ、回路構成が大幅に簡単
化される。

そしてまた２プロツクにまたがるバースト・エラーを検
出できる。

【図面の簡単な説明】

第１図および第２図は夫々本発明の前提として考慮され
たＨマトリクス、第３図は８プロツクの情報ビツトを単
位とし１６プロツク分に拡大した本発明に用いる一実施
例Ｈマトリクス、第４図は第３図図示のＨマトリクスを
具体的に示したＨマトリクス、第５図は本発明による他
の一実施例Ｈマトリクス、第６図は第３図即ち第４図図
示のＨマトリクスを用いた場合におけるエラー発生態様
にもとずくシンドロームの状態をまとめた説明図、第７
図ＡないしＤは本発明のエラー訂正処理装置の一実施例
構成、第８図は第７図Ａに示す一部回路を具体的に表わ
した一実施例を示す。 図中、１は単位Ｈマトリクス、１０はシンドローム発生
器、１１はエラー範囲抽出回路、１２は工ラ一・プロツ
ク検出回路、１３は訂正不能エラー検出回路、１４はエ
ラー・チエツクプロツク訂正回路、１５はエラー情報プ
ロツク訂正回路を夫夫表わす。

Claims (1)

1. 【特許請求の範囲】 １ ｂビット・１バーストブロツクエラー訂正／２バー
   ストブロツクエラー検出コードを採用した情報転送シス
   テムにおけるエラー訂正処理装置において、Ｎブロック
   分の情報ビット数とｍブロック分のチェック・ビット数
   とに対応する単位検査マトリクスを元にしてｍ・ｐブロ
   ック分のチェック・ビットを附加することなく単にｐブ
   ロック分のチェック・ビットのみを附加し該単位検査マ
   トリクスの一部を同じ行にかつ一部を異なる行に繰返し
   配列した拡大したＮ・（ｐ＋１）ブロック分の情報ビッ
   ト数に対応する検査マトリクスを使用すると共に、該検
   査マトリクスを使用して得られたシンドロームにもとず
   いて、上記チェック・ビット部分または上記Ｎ・（ｐ＋
   １）ブロック分の情報ビットを（ｐ＋１）個に区分した
   いずれの区分範囲内にエラー・ブロックが存在するかを
   検出するエラー範囲抽出回路、および上記区分範囲内の
   いずれのブロックにエラーが存在するかを検出するエラ
   ー・ブロック検出回路をもうけ、上記エラー範囲抽出回
   路出力と上記エラー・ブロック検出回路出力とによりエ
   ラー・ブロックのバースト・エラーを訂正するようにし
   たことにより、より少ないチェック・ビットを附加した
   形で訂正可能な情報ビット数を拡大したことを特徴とす
   るエラー訂正処理装置。 ２ 上記エラー・ブロック検出回路は、情報ビットを（
   ｐ＋１）個に区分した複数個の区分範囲に対して共通に
   もうけられ、該区分範囲内のどのブロック位置にエラー
   が存在するかを検出するよう構成された特許請求の範囲
   第１項記載のエラー訂正処理装置。 ３ ２ブロックにまたがるバースト・エラーを訂正不能
   エラーとして検出する訂正不能エラー検出回路をもうけ
   たことを特徴とする特許請求の範囲第１項または第２項
   記載のエラー訂正処理装置。