JPS59123945A - 多数バイトエラ−訂正システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は全般的にはエラー訂正システムに関し、具体
的には、１つの符号語中の多数バイトのエラーを訂正す
るためのエラー訂正システムであって、エラーロケーシ
ョンの特定およびエラーパターンの特定が同時に達成さ
れるものに関する。

〔背景技術とその問題点〕

最近の情報処理システムに関連する多くのデータ記憶シ
ステムは、高信頼性およびデータの完全性に対してコス
ト効率の良い設計を得るために何らかのタイプのエラー
訂正システムを採用している。データ処理システムが記
憶システムからデータを検索する能力、すなわちアクセ
ス時間は、全記憶システムの効率の目安として十分了解
されている。多くのデータ処理システムにおいて、エラ
ー訂正符号全デコードするだめの時間はアクセス時間の
直接的な要素である。記憶装置の能力が増大してきてい
るので、強化された信頼性および有効性の要請もまた増
大してきている。この結果、エラー訂正システムによっ
てソフトエラーを処理するのに必要な時間が全アクセス
タイムに対してより多くのパーセンテージをしめるよう
になっている。従来技術において示唆された複数バイト
エラー訂正システムでは複数バイトのエラーのデコード
に比較的長い時間が必要とされる。これが高（３） 効率の記憶システムにこれらを使用する際の主たる難点
の１つであった。

以下の参照文献は従来のエラー訂正システムの基本的か
つ重要な側面を示す。

（１）　　１．Ｓ、Ｒｅｅｄ氏およびＧ、Ｓｏｌｏｍｏ
ｎ氏の”　Ｐｏｌｙｎｏｍｊａｌ　　Ｃｏｄｅｓ　０ｖ
ｅｒ　ＣｅｒｔａｉｎＦｉｎｉｔｅ　　Ｆｉｅｌｄｓ”
　（Ｊ、　　Ｓｉａｍ、　　８　（１９６０）！、３０
０−３０４） （２）　　Ｒ，Ｃ，Ｂｏｓｅ氏およびり、に、Ｒａｙ−
Ｃｈａｕｄｈｕｒｉ氏の”　Ｏｎ　　ａ　　Ｃ１ａｓｓ
　　ｏｆ　　ＥｒｒｏｒＣｏｒｒｅｃｔｉｎｇ　　Ｂｉ
ｎａｒｙ　Ｇｒｏｕｐ　　Ｃｏｄｅｓ”（Ｉｎｆｏｒｍ
ａｔｉｏｎ　　ａｎｄ　　Ｃｏｎｔｒｏｌ、３（１９６
ｏ）ｐ、６８−７９） （３）　　Ａ　　Ｈｏ　ｃ　ｑ　ｕ　ｅ　ｎ　ｇ　ｈ　
ｅ　ｍ氏の”ＣｏｄｅｓＣｏｒｒｅｃｔｅｕｒｓ　　ｄ
’ｅｒｒｅｕｒｓ”（Ｃｈｉｆｆｒｅｓ（Ｐａｒｉｓ）
２（１９５９）ｐ、１４７−１５６）（４）　　Ｗ、Ｗ
、Ｐｅｔｅｒｓｏｎ氏の”　Ｅｎ　ｃｏｄ　ｉｎｇａｎ
ｄ　　Ｅｒｒｏｒ　　Ｃｏｒｒｅｃｔｉｏｎ　　Ｐｒｏ
ｃｅｄｕｒｅｓｆｏｒ　　ｔｈｅ　　Ｂｏｓｅ−Ｃｈａ
ｕｄｈｕｒｉ　　Ｃｏｄｅｓ”（ＩＥＥＥ　　Ｔｒａｎ
ｓａｃｔｉｏｎ　　Ｉｎｆｏｒｍａｔｉｏｎ（４） Ｔｈｅｏｒｙ、、６（１９６０）ｐ、４５９−４７０）
（５）　　Ｄ、Ｃ，Ｇｏｒｅｎｓｔｅｉｎ氏およびＮ。

Ｚｉｅｒｌｅｒ氏の”　Ａ　　Ｃ１ａｓｓ　　ｏｆ　　
Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ　　Ｃｏｄｅｓ　　
＋ｎ　　ｐ　　　Ｓｙｍｂｏｌｓ　”（Ｊｏｕｒｎａｌ
　　ｏｆ　　Ｓｏｃ、Ｉｎｄｕｓ、ＡｐｐｌｉｅｄＭａ
ｔｈ、９（１９６１）ｐ、２０７−２１４）（６）　　
Ｅ、Ｒ，Ｂｅｒｌｅｋａｍｐ氏のＯｎＤｅｃｏｄｉｎｇ
　　Ｂｉｎａｒｙ　　Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｊ　
−Ｈｏｃｑｕｅｎｇｈｅｍ　　Ｃｏｄｅｓ”　　（Ｉ　
ＥＥＥＴｒａｎｓ、Ｉｎｆｏ、Ｔｈｅｏｒｙ　　１１　
（１９６５）ｐ。

５７７−５７９） （７）　　Ｊ、Ｌ、Ｍａｓｓｅｙ氏の”　５ｔｅｐ−ｂ
ｙ−８ｔｅｐ　　Ｄｅｃｏｄｉｎｇ　　ｏｆ　　ｔｈｅ
　　Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇ
ｈｅｍ　　Ｃｏｄｅｓ”（ＩＥＥＥ　　Ｔｒａｎｓ、Ｉ
ｎｆｏ、Ｔｈｅｏｒｙ　　１　１　　（１９６５）１　
５８０−５８５） （８）　　Ｒ，Ｔ、Ｃｈｉｅｎ氏の１°Ｃｙｃ　ｌ　ｉ
　ｃＤｅｃｏｄｉｎｇ　　Ｐｒｏｃｅｄｕｒｅ　　ｆｏ
ｒ　　ｔｈｅ　　Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏ
ｃｑｕｅｎｇｈｅｍ　　Ｃｏｄｅｓ”（Ｉ　ＥＥＥ　　
　Ｔｒａｎｓ、Ｉｎｆｏ−Ｔｈｅｏｒｙ　　１　０　（
１９６４）ｐ、３５７−１６３） （９）　　Ｇ、　　Ｄ、　　Ｆｏ　ｒｎｅｙＸＪｒ、氏
の”ＯｎＤｅｃｏｄｉｎｇ　　ＢＣＨＣｏｄｅｓ”（Ｉ
ＥＥＥ　　Ｔｒａｎｓ。

Ｉｏｆｏ、Ｔｈｅｏｒｙ　　１１（１９６５）ｐ、５４
９−５５７） Ｑ□　　Ｗ、Ｗ、Ｐｅｔｅｒａｏｎ氏およびＥ、　　Ｊ
。

Ｗｅｌｄｏｎ、Ｊｒ、氏のＥｒｒｏｒ　　Ｃｏｒｒｅｃ
ｔｉｎｇＣｏｄｅｓ、第２版（ＭＩＴ　　Ｐｒｅｓｓ、
　１９７２）参考文献（１）、（２）および（３）は一
般にリードソロモン符号およびＢＣＨ（ポーズ・チョド
レー・オツケンジエム）符号として通常知られている巡
回エラー訂正符号の広範囲な教材となる。これらの符号
は、二元有限体、または拡張された二元有限体の上に定
義されたときに、二元バイトエラーのようなシンボルエ
ラーの訂正を行うために用いられ得る。

参考文献（４）および（５）はエラーロケーション多項
式全使用することを提案して多数エラーのデコードの問
題を解決する基本的な手がかりを与える。

これらの参考文献（４）および（５）はエラーロケ、−
ション多項式の係数を解くために線形方程式の集合を用
いることを提案する。

参考文献（６）および（７）はエラーロケーション多項
式の係数を算出するために繰り返し法を用いることを示
唆する。エラーロケーション多項式の根はエラーのある
シンボルのロケーションヲ表わす。

参考文献（８）は巡回する試行錯誤の手順を用いてこれ
らの根を捜すだめの簡単な機械化された方法、チェノ・
サーチ（Ｃｈｉｅｎ　　５ｅａｒｃｈ　）’ｊｒ提案す
る。他方、参考文献（９）は非二元またはより高次の二
元シンボルに関する符号の場合にエラーバリューに算出
する際の他の簡素化を提供する。

参考文献（４）および（５）におけるエラーロケーショ
ン多項式の寄与は、多数バイトエラー訂正システムにお
いてこの多項式の根がエラーのあるシンボルのロケーシ
ョンを表わす点で重要であった。本件出願人はこの発明
に関連する発明について出願している。この出願はエラ
ーロケーション多項式の係数を得るための改良されたシ
ンドローム処理ユニット全開示する。

（７） 複数バイトエラー訂正システムにおいて複数バイトエラ
ーのデコード方法は一般に４つの一連のステップからな
る。

ステップ１；エラーシンドロームを計算する。

ステップ２；エラーシンドロームからエラーロケーショ
ン多項式の係数を決定する。

ステップ３；チェノ・サーチによりエラーロケーション
多項式からエラーロケ− ションを特定する。

ステップ４；各エラーロケーションに対してバイトエラ
ーバリューを決定する。

すべての既知の複数バイトエラーのデコード方法では、
ステップ４の開始に先立ってステップ３を完了させるこ
とが要求される。このような状況のために、従来のシス
テムではステップ４を実行するハードウェアによっての
ちに利用されるステップ３の結果を算出するだめの付加
的なハードウェアもまた必要とされる。参考文献（６）
およびＣ１ｌは従来のデコード方法に関する有益な検耐
ヲ与えている。

（８） 〔発明の概要〕 この発明は従来技術の問題が除去されているエラー訂正
システムを提供することを目的としている。

この発明によれば複数バイトエラーのデコード手順のス
テップ３および４が同時に完了されるエラー訂正システ
ムが提供される。とくに、まだ決定されるはずのない残
存エラーのロケーションについての明確な情報なしに、
巡回規則においてエラーロケーションおよびエラーバリ
ューの各々が割算される。ステップ６はチェノ・サーｆ
　（７）　機能を含み、エラー訂正手順の完全な機械化
へと拡張され、この結果、符号語におけるデータキャラ
クタはチェノ・サーチの各サイクルに同期して１回１つ
ずつエラー訂正システムからデータ処理システムに転送
され得る。最初のバイトデータに対するアクセス時間は
、このため、エラーについてのエラーロケーションの特
定やエラーバリューの形成の所要時間によって打撃を受
けない。ステップ（９） ６の結果は通常記憶されなければならなかったが、もは
や記憶される必要がないので、エラー訂正システムのハ
ードウェアもまた大部簡素化される。

エラーの実際の個数が予定された最大値よりも少ないと
きでも、同一のハードウェアのセットがチェノ・サーチ
の間の適切なサイクルですべてのエラーについてエラー
バリューを形成して訂正を行う。このような装置は従来
の単一シンボル訂正符号においてのみ実現可能であった
。

この発明のエラーパターン処理回路と関連して、先に述
べた他の出願で開示されたシンドローム処理ユニットが
採用されるとき、この改良されたシステムは、エラーロ
ケーション方程式の係数全得る際の動作が別々に行われ
るのをすべて回避する。

上述能の出願において検討されるように、最大値より少
ない数のエラーが符号語にある状況では、さらにハード
ウェアが簡素化される結果となる。

このことは、エラー訂正システムの回路がＶＬＳＩのか
たちで実施されようとしているときには重要になる。回
路が２を個の入力シンドロームバイトで動作するよ５Ｖ
ＬＳＩのかたちで実施されたときに、同一の回路を２ｔ
より少ない入力シンドロームバイトを与える場合に用い
ることができる点で簡素化は重要である。

したがって、この発明の目的の１つは関連するデータ記
憶システムのアクセス時間への影響が最小となる複数バ
イトエラー訂正システムを提供することである。

この発明の他の目的はエラー訂正ンステムからの符号語
の転送が、すべてのエラーロケーションの同一性がわか
るまえに開始される複数バイトエラー訂正システム金提
供することである。

この発明のさらに他の目的はエラーのある符号語のバイ
トごとのロケーションおよびエラーパターンが、バイト
がエラー訂正システムから転送されていくときに同時に
見分けられ、これによってエラーが飛行中（ｏｎ−ｔｈ
ｅ−ｆｌｙ）に訂正される複数バイトエラー訂正システ
ムを提供することである。

この発明の他の目的はつぎのよ５なＥＣＣ（エラー訂正
符号）システムを提供することである。

このＥＣＣシステムは、このシステムがそれに対応して
設計されている最大個数までのどのような個数のエラー
をも訂正するよう動作可能であり、このため、同一のハ
ードウェアが１つのアプリケーションにおいてエラーの
最大個数より少ないエラーを訂正するために採用され得
る。すなわち、より少ない個数のチェックバイトやシン
ドロームバイトを採用する異なるアプリケーションと交
互に採用され得る。

この発明の他の目的はエラーパターン葡得る際にたった
１つの反転作用が含まれるＥＣＣシステムを提供するこ
とである。

すでに述べられた、またはそれ以外のこの発明の目的、
特徴および利点は、添付図面において示されるようなこ
の発明の好ましい実施例の以下のより具体的な説明から
明らかとなるであろう。

（１１） 〔実施例〕 初めに、第１図において示されるシステムを詳述する。

そののち、エラーロケーションを特定するシンドローム
処理論理回路およびこの論理回路を操作する方法を、こ
の論理回路が実施された態様の数学的な表現および証明
によって、たどる。

この表現はどのようなエラー数にも一般的である場合に
関しエラー訂正システムの動作を数学的述語で詳述する
。

第１図はオン・ザ・フライＥＣＣシステムのブロック図
を示す。このシステムは先に述べた他の出願において開
示され権利請求されたシンドローム処理論理回路を含む
。この出願において詳述されるように、シンドローム処
理ユニットはエラーロケーション方程式に対する係数を
形成する。第１図のシステムの訂正処理は連続的である
。絶えることのないデータストリームがｎシンボルの符
号語の鎖のかたちでデコータに入り、そののち出ていく
。そのため、オン・ザ・フライ・デコーデ（１３） （１２） インクという名前である。

実際的な観点から、所定のデコード処理が以下のテスト
に合致するならば、すなわち、先行して受は取られた符
号語の訂正されたデータバイトが、後続の符号語のデー
タバイトが受は取られているときにユーザシステムに送
出されるならば、それはオン・ザ・フライと考えること
ができる。

（以下余白） （１４） デコーダはブロック６．７．８．９を有し、先に受は取
られ流出されていく符号語に存在するエラーをデコード
して訂正するときに、流入されてくる符号語についてシ
ンドロームを計算する。流出されていく符号語の１つの
訂正されたデータシンボルの出力と同時に起こる、流入
されてくる符号語の１つのデータシンボルの入力に、各
クロックサイクルが関連する。バッファ５は流入シンボ
ルおよび流出シンボルの間で少なくともｎシンボルの未
訂正のデータを内部に保持する。

ＣＦ（２）における３つのエラーを訂正するリード・ソ
ロモン符号がコンピュータ製品におけるアプリケーショ
ンのだめの特に重要な例として用いられる。ＧＦ（２Ｂ
）の２５６個の元が慣用的に８ビツト２元ベクトルの集
合によって表わされる。このような表現の１つは表１に
おいて与えられる。６つのエラーを訂正するリード・ソ
ロモン符号には、生成多項式の根α　、α１、α２、α
６、α４、α５に対応する６個のチェックシンボルがあ
る。ここでαは有限体ＧＦ（２８）＋７）元であり、８
ビツト２元ベクトルによって表わされる。ブロック６に
よって計算される対応するシンドロームは、それぞれｓ
□、ｓｌ、Ｓ２、Ｓ６おＳ　およびＳ５と表記される。

このようなシフト０−ムはどのような既知の従来の処理
にも一致する通常の方法で、受は取られた符号語から計
算される。このステップのための手段はよく知られてお
り、エクスクル−シブ・オア回路（ＥＸ−ＯＲ回路とす
る）およびシフトレジスタを用いる。ブロック７の論理
回路の詳細は第２図および第３図で示される。

表１−１ （１７） 表１−２ （１８） 表１−６ （１９） 表１−４ 　　ＱｎＸ 表１−５ （ｌＵ） 表１−６ 表１−７ ブロック７の全部の機能は第２図および第６図に示され
、第１に、６つのエラーの場合に対応してロケーション
パラメータΔ　　＼　Δ　　　Δ６３　３２ゝ　　６１ およびΔ　　を得るために第２図において以下の０ ４つの方程式を実行することである。２つのエラーの場
合にはロケーションパラメータはΔ２２、Δ　　および
Δ２０”も含む。この場合、たとえ１ はサフイツクヌ３３は４つのパラメータの１つを特定す
る。係数Δ３、Δ２、Δ１およびΔ。はこれらロケーシ
ョンパラメータから第３図において示される論理回路に
よって、具体的な符号語に含まれる正確なエラー数にし
たがって選択される。

６３、　３２、Δ６１およびΔ３ｏのための式３式％ は以下のとおりである。

Δ３３−８２　（ＳＩ　Ｓ３■Ｓ　２　Ｓ　２　）■５
６（ＳｏＳＰ１Ｓ２）の８４（Ｓ１８１のＳ　２　Ｓ　
Ｏ）　　　　　　　　（１）Δ３２−８３（Ｓ、Ｓ６■
Ｓ　２　Ｓ　２　）■５４（Ｓ４Ｓ４■５３Ｓ５）■５
５（Ｓ１８１の５２Ｓｏ）（２） Δ３．−８゜（Ｓ４Ｓ４■５３Ｓ５）の８１（Ｓ６Ｓ４
■Ｓ　２　Ｓ　ｓ　）の５２（Ｓ３８６＠５２８４）　
　　　　　　　　（３）Δ３ｏ二８１（Ｓ４Ｓ４■５３
Ｓ５）■８２（Ｓ６Ｓ４■Ｓ　２　Ｓ　ｓ　）■５３（
Ｓ３Ｓ６■５２８４）（４） これらのパラメータはエラーロケーション方程式（１７
）の係数を決定するのに使われる。そののチ、エラーロ
ケーションおよびエラーパターンが第１図に示されるオ
ン・ザ・フライ・システムのブロック８および９によっ
て決定される。ブロック７の詳細は第２図および第３図
に示される。

第２図に示される組合せ論理回路は２つの基本的な論理
ブロック１０および１１を有する。第１のブロック１０
はＸによって表わされ、ＧＦ（２ｂ）における２つの８
ビツト２元ベクトルに関する積操作に対応する。他方、
第２のブロック１１はＧＦ（２”）における２つの８ビ
ツト２元ベクトルに関する加算操作を表わす。ブロック
１１の操作は８個の２人力ＥＸ−ＯＲゲートを用いた単
純なビットごとのＥＸ−ＯＲの論理機能である。他方、
積操作はブロック１０で表わされ、より複雑であり、そ
して、７１個のＥＸ−ＯＲ回路および６４個のアンド回
路を含む。７１個のＥＸ−ＯＲ回路および６４個のアン
ド回路が必要なことはブロック１０の種機能の以下の説
明から理解しうる。

（以下余白） （２６） フロック１０の種操作は２個の８ビツト・ベクトルＡお
よびＢに関するもので第６のベクトルＣを生成する。こ
こで、 Ａ：〔ａｏ１ａ１１ａ２〜ａ３１ａ４〜ａ５１ａ６、ａ
７〕Ｂ＝〔ｂｏＸｂｌ、ｂ２、ｂ６、ｂ４、ｂ５、ｂ６
、ｂ７〕Ｃ＝［ｅｏ　％　ｃｌＮ　０２％　ｅｓ　％　
８４％　ｅｓ　％°６＼０７〕この積は２つのステップ
処理を通じて得られる。

第１に、積多項式Ｆの係数ｆ、全計算する４つことでＦ
＝Ａ　Ｘ　Ｂ　（ｍｏｄ、　２　）である。係数ｆ、（
ｉ＝０、・・・・１４）の割算に６４個のアンド・ゲー
トおよび４９個のＥＸ−ＯＲゲートが必要とされる。す
なわち 　００ ｆｌ−ａｏｂ１■ａ　ｉ　ｂ　。

ｆ　２−＆　ｏ　ｂ　２■ａ１５１■ａ　２　ｂ　。

ｆ　３　＝ａ　ｏ　ｂ　３■ａ１ｂ２■ａ２ｂ１■ａ　
３　ｂ　。

ｆ７＝ａＯｂ７■８１ｂ６■ａ　２ｂ　５（ｆ）−−−
−■ａ６ｂ１■ａ　７ｂ　。

ｆ８−ａ１ｂ７■ａ　２　ｂ　６■ａ　３　ｂ　ｓ■・
・・・■ａ７ｂ１ｆ１６＝ａ６ｂ７■ａ７ｂ６ １４　　７７ 第２に、ｐ（Ｘ）を法として多項式Ｆの剰余を求める。

ここでｐ　（ｘ）は８次の原始２元多項式である。

ｐ（ｘ）＝　１　＋Ｘ　６＋Ｘ　５．＋Ｘ　７＋Ｘ　８
を用いる。ｐ（Ｘ）　’に法とするｆ、の剰余は最大で
２２個のＥＸ−ＯＲゲートを必要とする。

ｃｏ−ｆｏ■ｆ８Φｆ９■ｆ１ｏ■ｆ１２■ｆ１３Ｃ１
−ｆ１■ｆ９■’ｉｏ■ｆ１１■’１３■’１４Ｃ２＝
ｆ２■ｆ１ｏ■’１１■ｆ１２■ｆ１４Ｃ３−ｆ３■ｆ
８■ｆ９■’１０■’１１Ｃ４−ｆ４■ｆ９■ｆ１０■
ｆ１１■ｆ１２Ｃ５−ｆ５■ｆ８■ｆ、■’１１ Ｃ６−ｆ６■ｆ９■ｆ１ｏ■’１２ Ｃ７−ｆ７■ｆ８■ｆ９■ｆ１１■ｆ１２１９只） （２７） 積の処理の実施は、係数ｆ　からｆｌ４に対して要求さ
れる積項の各々ごとに１個の２人カアンド・ゲートを伴
い、これらアンド・ゲートの出力を結合するために１個
の２人力ＥＸ−ＯＲゲートを伴う。したがって、各ブロ
ック１０は６４個のアンド・ゲートおよび７１個のＥＸ
−ＯＲゲートを表わす。

エラーロケーション多項式の第１項、４３３式の５２（
Ｓ１Ｓ６■Ｓ　２　Ｓ　２　）は第２図における破線の
ブロック１６によって実行される。ブロック１６の出力
はゲート１８において式の第２項とともにＥＸ−ＯＲ演
算され、この演算結果がゲート１９において式の最終環
とともにＥＸ−ＯＲ演算される。

他のパラメータΔ　　　Δ　　およびΔ３ｏの３２ゝ　
　　６１ 各々を得る際に伴われるブロックは第２図において類似
した態様でたどることができる。

単に２個のエラーが生じる場合に対応するパラメータΔ
　　、Δ　　およびΔ２ｏが式（１）におい２２　　　
２１ てΔ３３に対する共通因数となる。これら共通円（１０
） 数は ７２２＝Ｓ１Ｓ１■５２ＳＯ（５） Δ２１＝ＳｏＳ３■５１Ｓ２（６） Δ２０＝ＳＩＳ３■５２Ｓ２（７） 第２図において、Δ　　、Δ　　およびΔ２゜２２　　
　２１ に対する計算はΔ３３に対する計算における中間的な副
産物として示される。同様に、Δ１１およびΔ１ｏはΔ
２２に対する式（４８）の共通因数であり、つぎの式で
与えられる。

Δ　＝　Ｓ　　　　　　　　　　　　　　　　（ｓ）１
　　０ Δ　＝　Ｓ　　　　　　　　　　　　　　　　（９）０
　　１ エラーロケーション多項式のシンドロームニ対する以下
の従前の関係式から、ロケーションパラメータを得るた
めの式がどのように導き出されるかについてはのちにこ
の欄において示される。

第３図ｆｄロケーションバラメ○りΔ６６〜Δ６゜およ
び共通因数Δ２２〜Δ１ｏからエラーロケーション多項
式の係数を選択するための論理回路を示す・第６図の論
理回路は入力パラメータΔ６６〜Δ３ｏおよび共通因数
Δ２２〜Δ１ｏからエラー数を特定してつぎの一般式に
おける適切な値Δ□を選択するように作用する。

Δ３５がゼロでなく、３個のエラーがあることを示すと
きに、係数Δ６〜Δ。は値Δ３６〜Δ３゜となる。示さ
れるように、Δ３３がゼロでないときに、アンドゲート
４１の出力は低レベルである。

そして、アンドゲート４１の出力はアンドゲート４２．
４３および４４の各々の入力端で反転され各アンドゲー
ト４２〜４４をイネーブルとするので、アンドゲート４
１の出力はΔ　　、Δ　　および２　３１ Δ３ｏの信号がアンドゲート４２〜４４をそれぞれ通じ
てゲートされ得るようにする。

Δ６３がゼロであり２以上のエラーがないことを示すな
らば、同様の論理機能はΔ２２によって達成される。こ
のような状況において、Δ２、Δ１およびΔ。はそれぞ
れアントゲ−）５１．５２および５６の動作を通してそ
れぞれΔ　　、Δ２　２１ およびΔ２ｏの値を取る。この機能は２つのエラーのだ
めのシンドローム方程式に対応する。

Δ２２もまたゼロであれば、第６図の論理回路は同様に
Δ　およびΔ　をΔ　　およびΔ１２の１　　　　　　
　０　　　１１ 値とするよう機能する。アンドゲート６０はイネーブル
信号を与えるので、Δ　　およびΔ２２が３ ともにゼロであれば、アンドゲート６１および６２はΔ
　　およびΔ１０’それぞれオアゲート７１ １．７２を通じてゲートする。

したがって、第３図の全論理回路は第２図の論理回路に
よって形成されたロケーションパラメータからエラーロ
ケーション方程式のための係数Δ３、Δ２、Δ、および
Δ。の正しい値を生成、すなわち選択するよう機能する
。

（以下余白） （５３） さて、以下に表わされるエラーバリュ一方程式の係数Φ
を形成するハードウェアについて詳述し包括的な場合の
エラーバリュ一方程式は・この欄で後に詳述される。一
般式は、以下の式のように係数を規定し得るような図面
に示された特別な３バイトエラー訂正システム用に変換
できる。

Φ　＝Δ　Ｓ　　　　　　　　（至） 　　００ Φ　＝Δ　Ｓ１ΦΔ　Ｓ　　　　　６４１　２　　　３
２ Φ　＝Δ　Ｓ　　　　　　　　　（Ｉ啼　　３１ 第４図の論理回路は要するに上の６つの方程式を実行し
、２つの基本的な論理ブロック１１０および１１１を有
する。ブロック１１０は２個の８ビツトベクトルの積関
数を与えるように作用し、第２図に関連して先に詳述し
たブロック１０と同ｌｚＡ） −である。ブロック１１１は２個の８ビツトベクトルの
加算関数であり、第２図において先に詳述したブロック
１１と同一である。エラーバリュー係数Φおよびエラー
ロケーション係数Δが得うれルト、実際のエラーロケー
ションおよびエラーパターンかどうかの試行錯誤の体系
的なサーチ、すなわちチェノ・サーチを機械化するため
に第５図の回路が採用される。第５図の回路はエラーバ
リュ一方程式かつぎのように書き直されるときにエラー
バリュ一方程式を実行するように作用する。

図示されるように、第５図はエラーロケーション係数を
受ける４個の帰還型シフトレジスタ１２０−０．１２０
−１．１２０−２および１２ｏ−６と、エラーパターン
係数を受ける６個の帰還型シフトレジスタ１３０−０．
１３０−１および１３０−２に有する。１２０が付され
たブロックは１ Δ　α　■Δ　α２ｉ■Δ　α１■Δ　ただいｃ（Ｉ）
　　（１７）３　　　　　２　　　　　１　　　　０の
式を実行し、他方、ブロック１３０は式（１６）の分子
を実行する。式（１６）の分母は反転ブロック１４０に
よりＥＸ−ＯＲゲート１２５の出力から形成される。こ
の出力は式αカのために形成された１つの項である。反
転回路１４０の機能および詳細はこの欄においてさらに
続いて検討される。ＥＸ−ＯＲゲート１２７の出力はア
ンドゲート１２８を介して訂正不可能なエラー状態にあ
ることを表示するように作用する。この状態は符号語の
長さに依存する。そして、エラー数が符号の予定された
訂正能力を上まわるならばいくつかの場合に起こるであ
ろう。

積ブロック１４５は、先に詳述された積ブロック１１０
および１０と同一の態様で２個の８ビツトベクトルを乗
算し、７６個のＥＸ−ＯＲゲートおよび６４個のアンド
ゲートヲ有する。これらゲートのそれぞれは２人カゲー
トである。

積ブロック１４５の出力はエラーパターンＥ。

であシ、これがアンドブロック１４６に供給される。ア
ンドブロック１４６は８個の２人カアンドゲート’を有
する。ゲート１４６に供給されたエラーパターン・ベク
トルＥ　は、ＥＸ−ＯＲブロック１２７の出力がゼロで
あるとエラーロケーション論理回路が示すときのみ、Ｅ
Ｘ−ＯＲブロック１４７に供給される。ＥＸ−ＯＲブロ
ック１４７の他の入力はバッファ４から供給される。

第５図において、ＥＸ−ＯＲブロック１２７の出力端の
ゼロによって示されるようにエラーが捜し出されたと見
分けられ、そわ・故そのパイ４ト位置に対する正しいエ
ラーパターンを積ブロック１４５の出力が含むことが示
されることによって決定される適切な時点で、ＥＸ−Ｏ
Ｒブロック１４７にエラーデータバイトが各々供給され
るように、クロック信号Ｃがシフトレジスタおよびバッ
ファに供給される。

第５図の回路の動作は以下のとおりである。クロック０
の時点で係数Δ３、Δ２、Δ１およびΔ。

と係数Φ２、Φ１およびΦ。が適切なシフトレジスタに
入力される。各クロックサイクルはこれらシフトレジス
タにシフト動作をさせる。シフト動作は各レジスタの内
容を特定の定数で、すなわちΔ６、Δ２およびΔ１のシ
フトレジスタの場合にはそれぞれα６、α２およびαで
、Φ２およびΦ１のシフトレジスタの場合にはそれぞれ
α２およびαで乗算する。第１番目のクロックサイクル
で、第５図のＥＸ−ＯＲ回路１２’１．１２５および１
２７からなる上部の組はシフトレジスター２０の出力端
において弐〇ηのすべての項を受けとる。和がゼロのと
き、式ａカは満たされ１つのエラーロケーションが特定
される。同様にして第１番目のクロックサイクルでＥＸ
−ＯＲ回路１３１．１３２からなる下部の組がシフトレ
ジスター３０の出力端において式（１６）の分子を受け
とる。式（１６）の分母は、先に述べたように、ＥＸ−
ＯＲ回路１２５から容易に入手できる。逆算操作のため
のブロック１４０および種操作のためのブロック１４６
は、式（１６）にしたがって各ロケーションに対応した
エラーパターンＥ、を計算する。

ＣＦ（２８）における代数学の逆算は、８テジツト２元
系列を特定の８デジット２元系列に写像する組合せ論理
回路を通じて得ることができる。

この写像は最大で３０４個の２端子アンドゲートおよび
４９４個の２端子オアゲートを必要とする。

逆算を得る方法はのちにこの欄で示される。エラーロケ
ーションが特定されるとき、バッファ４からのデータキ
ャラクタが出力加算ネットワーク１４６〜１４７を通じ
て変更される。他のすべての値の１については、アンド
ゲート１４６が閉じられるのでＢ５の計算値は無視され
る。符号語のすべてのバイトが送出されたとき（最後の
クロックサイクルＣで）、シンドロームがゼロでないの
にエラーロケーションが特定されなかったならば、エラ
ーが沢山ありすぎたこととなる。ラッチ１５６およびア
ンドゲート１５７はこのこと１ＵＥ（Ｕｎｃｏｒｒｅｃ
ｔａｂｌｅ　　Ｅｒｒｏｒ　）信号で表わす。

第５図のテコータにおいて訂正されたバイトはＢ　　、
Ｂ　　、Ｂ　　　・・・・・・、Ｂ　　　という順序０
　１　２ゝ　　　　　　ｃ−１ で送出される。チェックバイトが低次の位置に対応する
ので、これはエンコード動作における順序に較べて逆の
順序である。デコード方程式α力および（１６）中の１
について（ｃ−ｊ）ｅ代入して、すなわちこれらを （Δα　）α　　■（Δα２　ｃ　）α−２ｊ■３ｃ　
　−３ｊ ２ （ΔαＣ）α−ｊ■Δ−０　　　　　　（１８）０ に書き直して、クロックサイクルのカウントｊとバイト
ロケーション番号ｉとの間に逆関係を導入することによ
り、この逆転を容易に除去することができる。これらの
式においてｊはクロックサイクルのカラントラ表わす。

そして、ｊは１からＣへと連続的であり、これがバイト
エラーバリューの（ｃ−１）から０に対応する。これは
、バイトをＢ　　１・・・・・・、Ｂ１、Ｂｏの順序で
送出さ−１ せ、この順序はエンコーディング処理におけるそれと同
じである。

上述の修正を達成するために、以下の変更が第５図の論
理回路に加えられる。（１）シフトレジスタ３　　２　
　　　　　　　　　−３　　−２乗算器α　、α　およ
びαがそれぞれα　　、α　１及びα−１によって置き
換えられる。（２）係数Δ６、Δ２、α０、α２ｃおよ
びα０によって予め乗算される。

このような前置乗算回路は値Ｃに依存し、各々は少数の
ＥＸ−ＯＲゲーＩｆ要する。α２５５＝１であるのでｃ
　＝　２５５のときにはこの前置乗算が不要であること
に留意されたい。上述の修正された論理回路は第６図に
表わされる。

（以下余白） 以下では、第２図および第６図の論理回路手段において
用いられる式を数学的に誘導する。

ＧＦ（２８）における３バイトエラー訂正リード・ソロ
モン符号では、生成多項式の根α０、α１、α２、α６
、α４、α５に対応して６個のチェックシンボルがある
。対応するシンドロームはそれぞれｓ　　　ｓ　　　ｓ
、ｓ、ｓ　　およびＢ５に０ゝ　　　１ゝ　　　２　　
　３　　　４よって表記される。

ここで最大で３個のシンボルにエラーがあるとよびＥ　
　で表記され、誤ったシンボルのロケ−５ ジョンは１，１　　およびｉ３で表記される。そ２ うすると、シンドロームおよびエラーの間の関係は ただしｊ＝０．１．２．３．４．５　　　（ＩＡ）環式
を考える。これはエラーロケーション多項式と呼ばれ、 Ｘ３■σＸ２■σＸ■σ　　　　　　（２Ａ）２　　１
　０ で与えられる。式（２人）でＸ−α　の代入を行い３ｉ
　　　　　　２ｉ α　■σα　■σα■σｏ＝０ ２ま ただい＝１１．１２および＋　３　　　　（３Ａ　）を
得る。

式（１Ａ）および（３Ａ）から、シンドロームＳ。

およびエラーロケーション多項式の係数σ、の間に成立
する以下の関係式を導き出せる。

式（４Ａ）を解いて、 のとおりのσ　、σ　およびσ２を得ることかで１ きる。こξでΔ　　、Δ ６３　６２・７６１および’３０ は ７６６−８２（Ｓ１８３の８２８２）の８３　（Ｓ　ｏ
　Ｓ　３■ｓ　１Ｓ　２　）■Ｓ　　（Ｓ　　Ｓ　■Ｓ
　　Ｓ　　）　　　　（６Ａ）４　　１１　　２０ Δ３２−８３（Ｓｌ”３■Ｓ　２　Ｓ　２　）■Ｓ　４
（Ｓ　ｏ　Ｓ　３■ｓ　１Ｓ　２　）■ｓ　　＜ｓ　　
ｓ　　のｓ　　ｓ　　＞　　　　　（７Ａ）５　　１１
　　２０ Δ６ｌ−８ｏ（Ｓ４Ｓ４■５３８５）の８１（Ｓ３Ｓ４
■５２Ｓ５）Ｏ８（Ｓ　　Ｓ　　■ｓ　　ｓ　　）　　
　　　（８Ａ）２　　３３　　２４ ４６０−８１（Ｓ４Ｓ４■ｓ　ｓ　ｓ　ｓ　）Ｏ５２（
Ｓ３Ｓ４■Ｓ　２　Ｓ　５）■Ｓ　３　（Ｓ　３　Ｓ　
３■８２８４）（９Ａ）より得る。

もしΔ６６の値が０ならば、式（４Ａ）は６個未満のエ
ラーがあることを示す従属集合である。この°場合、シ
ンドロームは２個のエラーに対応して処理され、ここで
は２バイトエラーの場合についての同様の方程式からパ
ラメータΔ　　、Δ　　および２２　　　２１ Δ２ｏが誘導され、これらは Δ２２＝Ｓ１Ｓ１■５２Ｓｏ（１０Ａ）Δ２ｌ−８ｏＳ
６■５１ｓ２（１１Ａ）Δ２ｏ−８１Ｓ３■５２Ｓ２（
１２Ａ）より得られる。

Δ　−８Δ　■Ｓ　Δ　■Ｓ　Δ　　　（１３Ａ）３３
　２２０　３２１　４２２ のように曹き直し得る式（６Ａ）から理解されるように
、これらがΔ３６の共通因数であることに留意する。そ
うすると、２バイトエラーの場合に対応するバリューΔ
　　、Δ　　およびΔ２ｏは２２　　　２１ 個別に計算する必要がない。これらはΔ３６を得るため
の計算の副産物のかたちで手に入るのである。同様に、
１バイトエラーの場合に対応するΔ１１およびΔ　　は ０ Δ　””Ｓ　　　　　　　　　（１４Ａ）１　０ Δ　＝Ｓ　　　　　　　　　（１５Ａ）０　１ によシ得られ、これらはΔ２２の共通因数であり、シン
ドロームとして宕易に入手可能でもある。

マが正確なエラー数ｆｔ：表記するとしよう。■は６．
２．１また０をとり得る。

正確なエラー数はつぎのように決定される。

ｖ＝３ｉｆΔ６６メ０ ｖ＝ＯｉｆΔ３３＝Δ２２＝Δ１１−０２バイトエラー
および１バイトエラーのような特別な場合は適当な行列
式を選択することにより自動的に適用され得る。この目
的のためにΔ３、Δ２、Δ、およびΔ。を Δ　＝Δ　　　　　　　　　　　　　　　　　　　　（
１７Ａ）　　　６３ （４６） Δ　＝Δ　　ｉｆ　　ｖ＝３　　　　　　　　（１８Ａ
）２　　６２ Δ百ｖ：２ ２ Δ＝Δ百ｖ＝３　　　（１９Ａ） 　　　３１ Δ百ｖ＝２ １ Δ　　　ｉｆ’ｖ−＝１ １ Δ　二Δ　　ｉｆ　　ｖ＝３　　　　　　　（２０Ａ）
　　　６０ Δ　　百　■二２ ０ Δ百ｖ＝１ ０ のように規定しよう。そうすると、式（５Ａ）　ｅのよ
うに書き直せる。

通常、係数が式（２１Ａ）のσ　、σ　およびσ２１ であると、エラーロケーション多項式（６Ａ）は周知の
チェノ・サーチの手順を通じてエラーロケーションを決
定するために用いられる。し〃）シなＩＩｓら、Δ　に
よって割り切れてしまうことを回避するためにエラーロ
ケーション方程式を修正するととがある。修正されたエ
ラーロケーション方程式％式％（２２） として得られる。エラーロケーション数は、式（２２Ａ
）を満たすｉに属する７個の１つしかないノくリューの
集合である。

ツキニエラーバリューＥ、　、Ｅ、　およびＥｉ６１１
　　　　　ｔ２ を求める式を誘導する。ｊ＝０．１および２についての
式（１人）から を得、この（２３）　ｋＥｉ　１について解いて（２４
Ａ） を得る。式（２人）から ・　＝・ｉ１■パ２■・”３（２６Ａ）を得、式（２４
Ａ）、（２５Ａ）および（２６Ａ）からを得る。式（５
Ａ）を用いると式（２７Ａ）を（２８Ａ） に約分できる。式（２８Ａ）のエラーバリューＥ、１は
１１の項で表わされ、このため１２およびｉ６について
の明白なバリューなしにそれを計算し得ることに留意さ
れたい。他のエラーバリューＥｉ２およびＥｉ３も同様
な式で表わされる。エラーバリューを求めるためのより
一般的な式は現行の変数ｉを１１に置き換えて式（２８
Ａ）　　を曹き直すこと’　　　　（４９）　　　　　
　　　　　　　へ１・によりつぎのように得られる。

ここで、係数Φ　、Φ　およびΦ２は １ Φ　＝Ｓ　　Δ ｏｏｏ　　　　　　　　　　　　　　　（３０Ａ）Φ１
−”’１’２■８２’３　　　　　　　　（３１Ａ）Φ
２”’　１　’　５　　　　　　　　　　　　（３２Ａ
）により与えられる。式（２９Ａ）はデコード処理の通
常のステップ４をステップ３に連結させることができ、
ここではエラーバリューＥ、　、Ｅｉ２およ１ びＥｉ６が１ラー０ケーシヨンのチ１ン°サーチに同期
して計算される。

そして、シンドロームデコーダは式（２２Ａ）および（
２９Ａ）における種々の数量をｉに属する値の各々に対
して遅速的な繰り返しの態様で計算することから成り、
そして式（２２Ａ）が満たされるときは（５０） 〔を個のエラーの一般的な場合〕 以下の説明では、第２図、第６図、第４図および第５図
において示された６バイトエラーまでの特別な場合に対
応する論理回路が広くｔバイトエラーについても適用可
能であることを立証するために、一般的な場合について
数学的な誘導を行う。

一般的なりＣＨまたはり一ド・ソロモン符号において、
符号語はｎ個のシンボルからなシ、生成ａ＋１　　　ａ
＋２　　　　　　　ａ＋ｒ〜１多項式の根α８、α　　
、α　　、・・・・・・　αに対応したｒ個のチェック
・シンボルがｎ個のシンボルに含まれる。ここでαはガ
ロア体ＧＦ（２５６）の元である。整数ａとしてゼロが
採用されるが、以下の結論はこのようなａの値について
も誘導が可能である。対応するシンドロームはそれぞれ
ｓ、ｓｓ　　　・　・・・、５ｒ−１によって０　１ゝ
　　２ゝ 表記される。シンドロームは供給された符号語から 介　　・・・・・・　介 ２、　　　、　　ｎ−１は供給された符号語のｎ個のシ
ンボルである。

所定の符号語中の実際のエラーシンボル数を■と表記す
る。エラーバリューはＥ、にょって表記！ ロケーションからなる集合からエラーロケーションバリ
ューを表わす。そしてシンドロームおよびエラーの間の
関係は （２Ｂ） で与えられる。どのような非零のシンドロームバリュー
もエラーがあることを示す。デコーダはエラーロケーシ
ョンおよびエラーバリューを決定するためにこれらシン
ドロームを処理する。不明瞭さをともなうことなしにデ
コードし得る最高のエラー数’Ｉｔと表記しよう。を個
のエラーのエラーロケ−ンヨンおよびエラーバリューを
決定するにけｒ＝２ｔのシンドロームの集合が必要であ
る。

根がα１の多項式を考える。ことで１Ｅ（Ｉ）である。

これはエラーロケーション多項式と呼ばれ、 （３Ｂ） で定義される。ここでσｏ−１、σＶＶＯ２かつσ　＝
０（ｍ＞ｖ）である。ｍ≦■の未知の係数σ　は式（１
Ｂ）のシンドロームから以下のようにして決定され得る
。

式（３Ｂ）にＸ−α　を代入して を得る。式（２Ｂ）および（４Ｂ）　　’を用いれば、
シンドロームＳ、およびエラーロケーション多項式の（
５３） 係数σ　がつぎの関係式の組を満たすことを容易に示す
ことができる。

Σ　　σ　Ｓ　　　　＝Ｑ　　ただしに＝０．１、川・
、ｔ−１□−ｏ　　ｍ　ｍ　＋ｋ （５Ｂ） 式（５Ｂ）の組を行列表記で として書き直せる。

方程式（６Ｂ）の左片のｔｘ（ｔ＋１）のシンドローム
行列′ｆ：Ｍで表記しよう。行列Ｍ中の最終列を除去し
て得た正方行列をＭ　としよう。Ｍ　が正則１　　　　
　　　　　　　　　１ であれば上の方程式の組はクラマの法則を用いて解くこ
とができ、 を得る。ここでΔ　　は行列Ｍｔからなる非零の１１ 行列式であり、ｍ−０，１、・・・・・・、ｔ−１の各
々について行列Ｍ　Ｏｍ番目の列をシンドロームを 行列Ｍの最終列の負数で置き換えて得た行列の行列式を
Δ　　で表記する。

ｍ 行列Ｍ　が正則でなければ、すなわちΔ１１がゼロであ
１屯方程式（５Ｂ）は従属集合であり、これはｔより少
ないエラーがあることを意味する。この場合、σ　はゼ
ロである。式（６Ｂ）においてσ。

およびシンドローム行列の最終列および最終行を削除す
ることができる。この結果得られた行列方程式はｔ−１
個のエラーのだめのものに対応する。

この処理は適宜繰り返され、最終的な行列は７個のエラ
ーのだめのものに対応し、Ｍは正則となる。

そして行列式Δ　　の集合が必要とされる。ここ　ｍ で、ｍ−０，１、・・・・・・、■である。

ｖ　＝　ｔ　−１のΔ　　が、行列Ｍ　の第（ｍ−１）
ｖｍ　　　　　　　　　　　を 番目の行およびｔ番目の列に関連したΔ、の共通因数で
あることは容易に理解される。このような共通因数の項
でΔ５．を表わすことができる。

それゆえ、ｖｍｔ−１におけるΔ　　の値を個別　ｍ に計算する必要がない。これらはΔ、のための計算の副
産物として入手しうる。実際、そのつぎのより小さな値
のＶのためのΔ　　は、より低次　ｍ の共通因数の段階的な関係を通じて、すべてΔ。

のための計算の副産物として入手できる。それゆえ、エ
ラーがより少ない場合においては、デコーダがΔ　　−
０を見出し、■についての訂正バリ１ ニーを求めるために先行して行われた計算に逆戻りし、
すでに計算された共通因数Δ　　を用いる。

　ｍ これはｔ＝３の場合のハードウェア手段を通じて先に図
示されている。

すべてのより少ないエラーのだめの特別な場合に適合す
るように、式（７Ｂ）　ｔより便利な一般的な形 で置き換える。ここですべてのｍ）ｖでΔ　　＝　ｍ ＯでΔ　　〆０という事実からＶが決定され、Δ□はつ
ぎのような新たな表記で定義される。

σ　＝１なので、式（９Ｂ）を用いればすべてのｍの値
についてσ　を決定することができる。ただし、全体の
デコード処理において係数σ　が必要とされないことは
理解される。この目的のために式（４Ｂ）および（９Ｂ
）から によって与えられるような修正されたエラーロケーショ
ン方程式＊ｍる。エラーロケーションツクリューｉｇ（
Ｉ）は式（１１Ｂ）を満たすｌに含まれる７個の独特の
値の集合である。

（５７） 式（２Ｂ）で定義されるようなエラーロケーション多項
式は７個のエラーロケーションバリューに対応した７個
の根を持つ。ロケーションバリューｉ−ｊに対応した根
以外のすべてのエラーロケーション多項式の根を持つ１
つの多項式を考える。

この多項式は ｌ〆ｊ として定義される。実際のエラーロケーション数Ｖがｔ
より小さいとき、ｍ””ｖ、・・・・・、ｔ−１につい
て係数σ、　　がゼロとなる。単一のノ・−Ｊ　〜　ｍ ドウエアセットによってすべてのＶの値の処理を行える
ようにするためにこのことがなされる。式（１２Ｂ）に
Ｘ＝α　を代入して を得る。

シンドロームＳ、°および新たな多項式の係数σ。

３　　　　　　　　　　　　　　　　　　　　　　　３
％”を含む式（５Ｂ）中の式と同一の式を調べよう。式
（２Ｂ）’を用いればＳ　について代入を行って（１４
Ｂ） を得る。式（１４Ｂ）に紹ける加算パラメータｍおよび
ｉの順序を入れかえて （１５Ｂ） を得る。さて式（１３Ｂ）および（１５Ｂ）’に用いれ
ばを得る。それゆえ、エラーバリューを求める式ヲ得る
。エラーバリューを求める上式は良く知られている。こ
れをさらに約分してより便利な形とすることにしよう。

この目的のために、つぎの補助定理１．２および３を証
明する。

補助定理１では、エラーロケーション多項式の既知の係
数σ　の項で係数σ、　　を表わす関係ｋ　　　　　　
　、）、ｍ 式を得る。

〔補助定理１〕 〔証明〕 式（３Ｂ）および（１２Ｂ）における多項式の定義から を得る。式（１９Ｂ）の両片の多項式における各項の係
数を比較すれば を得る。式（２０Ｂ）を用いてσ　について代入を行に ただし０≦ｍａｔ　　　　（２１Ｂ） を得る。式（２１Ｂ）から相殺環を除去することに基づ
いて を得る。これで補助定理１の証明を終える。

つぎに、式（１７Ｂ）における数式の分子を補助定理１
の結論を用いて書き直す。

〔補助定理２〕 〔証明〕 補助定理１を用いれば （６１） を得る。加算パラメータｍおよびｋの順序を入れ変えて を得る。式（４Ｂ）を用いれば式（２５Ｂ）をのように
書き直すことができる。これで補助定理２の証明を終え
る。

さて補助定理１の結論を用いて以下の補助定理において
式（１７Ｂ）の分母についてのより簡便な数式を得る。

〔補助定理６〕 ただし０≦μ＜ｔ　　　（２７Ｂ） 〔証明〕 補助定理１を用いればσ、ｆｆσ　の項で表１１ｍｋ わすことかできる。これらの値を代入してを得る。ＲＨ
８で式（２８Ｂ）の右辺を表記しよう。

この補助定理を証明するためにＲＨ８を配列しなおす。

初めに、式（４Ｂ）からの結論を用いてＲＨ８のいくつ
かの項（ｍ＞μの項）を のように書き直す。そののち、上式においてｋにｍ十り
を代入すればＲＨ８は になる。加算パラメータｍおよびｈの順序を入れ換えれ
ば のようなｌ’ｔＨ８についての他の形を得る。ｍにに−
ｈを代入すれば数式ＲＨ８は となる。ただし式（５Ａ）から ただしｈ＜ｏ　　かつ０≦μ十ｈ＜ｔ　　　（３ｉ）を
得る。それゆえ、式（３２Ｂ）に式（３！ＩＢ）を用い
ればＲＨ８の最終的な形を得る。

ただし０≦μ＜　ｔ　　　　　　（３４Ｂ）式（３２Ｂ
）からつぎのような補助定理乙の系をも得る。

〔系〕

で与えられる。

補助定理６およびその系はμの値の選択を通じて式（１
７Ｂ）の分子を求める式の７アミＩＪ　ｔ−与える。

以下のことに注意する。

（ａ）補助定理における数式はシンドロームＳＰ＋。、
Ｓ　　１・・・・・・、Ｓ　　　　を必要とする。他方
、系μ＋１　　　　μ＋ｔ−１ における数式はシンドロームＳｏＸ　Ｓｌ、・・・・・
・、Ｓ　　を必要とする。このことは削除訂正の場合−
１ にとくに重要である。

（ｂ）　　系における数式は、補助定理における数式に
較べてσ　Ｓ　　　という種類の乗算の回数がｋ　　　
ｋ−ｍ より少ない。系においては、この回数はμの選定に依存
し、Ｌを７を下まわる最大の整数とすればμｍりのとき
この回数が最小となる。μｍ７に選定したときの乗算の
回数はい２＋２　ｔ　）／４に最も近い整数である。

（ｃ）　　より少ないエラーの場合（Ｖａｔ）は１重エ
ラーのためのハードウェアと同様のハードウェアによっ
て自動的に処理される。μが所定のものに選ばれたとき
に、もしｔ≧ｔ１＞μであれば、同様のハードウェアを
シンドロームＳ０１　Ｓｌ、・・・・・・、Ｓ、１から
なるより小さな集合およびｔｌまでのエラーに適用する
のに用いることができる。この観点から、ｐの値をより
小さくすることが望ましく、μｍ０に選んだときにデコ
ーダのハ−ドウエアの適用に関し最大限のフレクシビリ
ティが得られる。μｍ０としたときに系における数式に
必要とされる乗算の回数は（ｔ２−ｔ＋２）／である。

これは、μｍＬのときの最小値としての（ｔ２＋２ｔ）
／４の２倍より少ない。

以上の観察を考慮して補助定理３の系における数式がデ
コーダ手段において用いられるであろう。

大きな値のｔについては、・・−ドウエアに最大の節約
をもたらすためにμｍＬとすることは有益である。ｔか
小さな値の場合には、すでに製作されたハードウェアを
修正することなしに、後日必要に応じてｔの値を減らす
ことができるというフレキシビリティを得るためにμ二
〇を用いうる。

さてμｍ０としたうえで補助定理２と補助定理乙の系と
の結論を用いて式（１７Ｂ）’に書き直すことができる
。この結果として、どのエラーバリューとして表わされ
得る。ここでΦ　はつぎのとおりである。

式（９Ａ）を考慮すれば、上式は正規化され、とののよ
うにΔ　の項によるエラーバリューを得ることができる
。ここでΦ　はつぎのとおりである。

二元基礎体の場合、式（３９Ｂ）の分子の項はｍが偶数
であると（ｍ　ｍａｄ　２＝Ｏ）ゼロになる。二元基礎
体のためのＥ　を求めるための結果として生　　ｏｄｄ となる。ここで である。

エラーロケーションのチェノ・サーチにおいてｉの値の
各々についてなされた式（１１Ｂ）の計算結果から式（
４１Ｂ）における分子を求めるための計算結果が副次的
に予め入数されることに留意されたい。エラーロケーシ
ョンを求めるサーチに同期して、ｉの値の各々について
の分母が計算され、分子の逆数で乗算され得る。この合
成されたＥ　は、エラーロケーション方程式（１１Ｂ）
が満たされるたびに、出力されていく１番目のデータシ
ンボルＢ。

を訂正するために用いられる。

以下に続く表２はＧＦ（２８）における２５５個の非零
の元を表示する。各々は対応する送元とともに示される
。原始多項式ｐ（３）−Ｘ８＋Ｘ７十Ｘ５＋Ｘ６＋１が
これらの元を生成するために用いられた。元け８デジツ
トの二元ベクトルにより表わされ、このベクトルは多項
式表記では左がわに高次項に対する係数を持つ。この表
の逆関数は、通常の８ビツト・エンコード・デコード論
理回路を用いるブロック４０を通じて実行される。これ
は最大で６０４個のアンドゲートおよび４９４個のオア
ゲートを必要とする。

この発明はその好ましい実施例を参照して具体的に図示
および詳述されたけれども、この発明の精神および範囲
を逸脱することなく形態および細部に種々の他の変更を
なし得ることは当業者において容易に理解されるところ
である。

弄２−１ 表２−２ （７１） 表２−３ （７６） （７２） 表２−４ （７４） 表２−５ 表２−６ （７５） 表２−７ （７６）

【図面の簡単な説明】

第１図はこの発明が採用された多数エラー訂正システム
のブロック図、第２図および第６図は第１図に示される
、エラーロケーション多項式のエラーロケーション係数
Δを形成するシンドローム処理ユニットの系統図、第４
図はエラーバリューを表記するための係数Φを生成する
だめの論理回路の系統的論理図、第５図はエラーサーチ
を実行し、エラーバリュー決定し、さらに正しくないバ
５・・・・ｎバイトのバッファ、６１・・・シンドロー
ム演算を行うブロック、７・・・・Ｄ、演算を行うブロ
ック、８二・・・Φ演算を行うブロック、９・す・エラ
ーロケーションおよびエラーバリュー演算を行うブロッ
ク、ＣＬ・・・・りｐツク。 出願人　　インターナショナル・ビジネス・マシーンズ
・コを乃ン復代理人　弁理士　　澤　　　１）　　俊　
　　夫ｎ　　　　　　　　　　　　Ｎ　　　　　　　　
　　　　　Ｐ−。 （〈〈〈 リ　　　　　　　　　　　　　ｎ　　　　　　　　　　
　　　円　　　　　　　　　　円（Ｊ′ククク

Claims (1)

1. 【特許請求の範囲】 符号語が２ｂ個のキャラクタ・ポジションを有し、この
   キャラクタの各々がｂ個の二元ビットの個別の連結から
   なるバイトにより表わされ、シンドロームバイトが各々
   ｂ個の二元ビラトラ有し、生成多項式の根α１、α８＋
   １、α８＋２、・・・・・・ａ　＋　２　ｔ　　１　＜
   αは２ｂ個の元を有する有限体の元）α を写すパリティチェック行列にしたがって上記シンドロ
   ームバイトが形成され、上記符号語中のｔ個までのエラ
   ーを２を個の上記シンドロームバイトを処理することに
   より検出し得るような多数バイトエラー訂正システムに
   おいて、 １個の符号語を読むことから２を個のシンドロームバイ
   トラ生成してシステム本体に供給するシンドローム生成
   手段と、 各クロックサイクルの間に、１個の符号語をなすバイト
   の各々を継続して上記システム本体から送出するととも
   に、つぎの符号語をなすバイトの各々を継続して上記シ
   ステム本体に供給するよう制御するクロック手段と、 上記つぎの符号語が上記システム本体に入力されるとき
   に上記システム本体から継続してバイトが転送される期
   間に上記２を個のシンドロームバイトに応答して上記１
   個の符号語中のｔ個までの誤ったバイトを訂正して上記
   １個の符号語およびつぎの符号語を継続したバイトの連
   続した系列として処理するようにする手段とを有するこ
   と′（ｌ−特徴とする多数バイトエラー訂正システム。