JPH0452556B2

JPH0452556B2 -

Info

Publication number: JPH0452556B2
Application number: JP58195368A
Authority: JP
Inventors: Moteibai Pateru Aauindo
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1982-12-29
Filing date: 1983-10-20
Publication date: 1992-08-24
Also published as: CA1199411A; US4504948A; BR8307181A; EP0112988A2; JPS59124011A; ZA837725B; EP0112988A3

Description

【発明の詳細な説明】

〔産業上の利用分野〕この発明は全般的には巡回エラー訂正符号を用
いたエラー訂正システムに関し、具体的には複数
バイトエラー訂正システムにおけるシンドローム
バイトのデコードの改良を行おうとするものであ
る。〔背景技術とその問題点〕磁気記録装置に関連して巡回エラー訂正符号を
用いることが従来よく定着しており、記録システ
ムに良好な効率およびコスト効果を付加するもの
として広く認識されている。一般に、エラー訂正処理は検出されたエラーの
各々のロケーシヨンおよびパターンを決定するた
めにシンドロームバイトの処理を含む。シンドロ
ームバイトは、データが記録媒体に書き込まれる
ときに生成されるECC（Error Correct Code）書
込みチエツクキヤラクタと、データが記録媒体か
ら転送または読み出されるときに生成される
ECC読出しチエツクキヤラクタとをEX−OR
（Exclusive OR）処理することの結果として生
じる。いくつだけECCチエツクキヤラククタが
用いられるかは符号に要求される能力および検出
または訂正されるべきデータバイトの個数に依存
する。一例を挙げると、磁気記録装置に８ビツト
バイトを記録することに関連して用いられる多く
の現在のECCシステムにおいては、255バイトポ
ジシヨンの長さを持つ符号語中の検出されるべき
エラーの各々について２バイトのチエツクバイト
が用いられる。この結果、たとえば、249個のデ
ータバイトおよび６個のチエツクバイトからなる
１データブロツク中の３個までのエラーを検出す
るには６個のチエツクバイトが必要となる。そし
て、そのようなシステムにおいては６個の独特の
シンドロームバイトが生成される。記録媒体から
読み出された255バイトからなるデータワード中
にエラーがないならば、すべてのシンドロームバ
イトは各々すべてゼロのパターンを含む。このよ
うな状況下では、シンドローム処理は必要でな
く、データワードは中央処理装置に送られ得る。
しかしながら、１個またはそれ以上のシンドロー
ムバイトが非零であれば、シンドローム処理はエ
ラーバイトのロケーシヨンを特定する過程および
さらに各エラーロケーシヨンに対してエラーパタ
ーンを特定する過程を含む。種々の出版物および特許文献において通常のシ
ンドローム処理に伴う基礎的な数学的概念および
操作が従来開示されてきた。一般に、このような
操作および数学的表現は、Peterson氏によつて
「エラーロケーシヨン多項式」と呼ばれてきたも
のを用いてエラーのロケーシヨンを特定すること
を第１に含む。エラーロケーシヨン多項式を用い
て伴われる数学的操作および表現の全目的は、シ
ステムにおいて生成されたシンドロームバイトの
みを用いてエラーバイトのロケーシヨンを特定す
ることである。従来では、のちに用いられるハードウエアが各
ロケーシヨンのエラーパターンを特定できるよう
に第１にエラーのあるロケーシヨンが特定され
る。そして、シンドロームバイトをデコードして
エラーのあるロケーシヨンを第１に特定するのに
二元論理を採用できるようエラーロケーシヨンを
シンドロームの形で表現する。そして、このため
に、数学的解析の始めとしてエラーロケーシヨン
多項式が採用されてきた。多数エラー訂正システ
ムのための従来のシンドローム処理デコーダのエ
ラーロケーシヨン部については２つの問題点があ
つた。第１の問題点は、多数エラーの状態の各々につ
いて個別の論理回路のセツトが必要となることで
ある。たとえば、システムが３個までのエラーを
訂正するよう設計されていると、エラーロケーシ
ヨンを特定するのに３つの個別独立の論理回路の
セツトが必要とされる。すなわち、３個のエラー
があるときにエラーロケーシヨンを特定するのに
必要とされる論理回路は、３個未満のすなわち、
２個または単一のエラーがあるならば、ロケーシ
ヨンを特定するのに採用され得ない。同様に、２
個のエラーがあるときエラーロケーシヨンを特定
するよう設計された論理回路は、符号語中に１個
のエラーのみ存在するならば、エラーロケーシヨ
ンを特定できない。この結果、このような従来の
デコーダの価格は極めて高いものであつた。多数エラー訂正システムのための従来のシンド
ローム処理デコーダに関する第２の問題点は、エ
ラーロケーシヨンに達するためにシンドロームバ
イトを数学的に処理する際に除算のステツプが必
要とされることである。高次の二元体における除
算操作は時間およびハードウエア実装の双方にお
いて損失が多いということは良く認められるとこ
ろである。この発明は多数エラー訂正システムにおけるシ
ンドローム処理デコーダであつて、除算操作を用
いることのない態様で各エラーロケーシヨンを特
定し得、さらに、最大値以下の個数のエラーがあ
るシステムにおいて最大個数のエラーロケーシヨ
ンを特定するのに用いられるハードウエアのサブ
セツトを採用するものを提供する。〔発明の概要〕この発明によれば、シンドロームバイトを用い
てつぎのエラーロケーシヨン方程式(1)の係数の適
当な値を形成するシステムが開示される。 _t 〓^m=0 Δ_nα^mi＝０ただしiε｛Ｉ｝ ……(1) この式(1)は特別な代表的な場合、たとえば３バ
イトエラー訂正システムのために書き直す時、以
下の形をとる。 Δ₃α³ⁱ＋Δ₂α²ⁱ＋Δ₁αⁱ＋Δ₀＝０ただしiε｛Ｉ
｝
……(2) このシステムは以下の行列方程式(3)において選
択される行列式に対応したロケーシヨンパラメー
タの集合を形成するために適切なシンドロームに
ついてGF（2⁸）の元の代数で乗算操作および加算
操作を実行して係数を生成することを含む。 S₀ S₁ S₂ S₁ S₂ S₃ S₂ S₃ S₄σ₀ σ₁ σ₂＝σ₃S₃ S₄ S₅ (10) ここでシンボルσ₃，σ₂，σ₁およびσ₀は従来のエ
ラーロケーシヨン多項式の係数を表わす。ロケーシヨンパラメータの数式は、最大個数の
エラーについてのパラメータを形成する過程で最
大個数より少ないエラーについての共通因数が形
成されるように公式化される。これはエラーロケ
ーシヨン方程式(2)の係数の演算および選択を簡略
化する。３個のエラーの符号についてのパラメー
タおよび対応する共通因数は以下の４つの式にし
たがつて形成される。 Δ₃₃＝S₂（S₁S₃S₂S₂）S₃（S₀S₃S₁S₂）
S₄（S₁S₁S₂S₀）……(4) Δ₃₂＝S₃（S₁S₃S₂S₂）S₄（S₀S₃S₁S₂）
S₅（S₁S₁S₂S₀）……(5) Δ₃₁＝S₀（S₄S₄S₃S₅）S₁（S₃S₄S₂S₅）
S₂（S₃S₃S₂S₄）……(6) Δ₃₀＝S₁（S₄S₄S₃S₅）S₁（S₃S₄S₂S₅）
S₃（S₃S₃S₂S₄）……(7) それゆえ、この発明の目的の１つは多数バイト
エラーをともなうエラー訂正システムのための改
良されたデコーダであつて、種々のエラー状態に
ついてエラーロケーシヨンを特定するのにただ１
セツトの組合せ論理回路が採用されるものを提供
することにある。この発明の他の目的は多数エラーを訂正できる
エラー訂正システムのための改良されたデコーダ
であつて、エラーロケーシヨンを特定するのに用
いられるエラーロケーシヨン多項式の係数をどの
ような除算操作をも用いることなく形成するもの
を提供することにある。この発明についてのすでに述べられた、または
その他の目的、特徴および利点は、添付図面に示
されるこの発明の好ましい実施例についての以下
のより具体的な説明から明らかになるであろう。〔実施例〕第１図に示されるシステムについてまず詳述し
よう。エラーロケーシヨンを特定するためのシン
ドローム処理用ハードウエアおよびこのハードウ
エアの操作方法についての詳細な説明は、このデ
コードが実施された態様の数学的表現および証明
によつて、たどられる。どのようなエラー数のエ
ラー証正システムにおいても動作するようデコー
ドを構成可能とするにはどうしたらよいのかとい
うことを、この表現は数学的述語で表現する。第１図はオン・ザ・フライ（on−the−fly）デ
コーダのブロツク図を示す。このオン・ザ・フラ
イ・デコーダについては本件出願人が出願中であ
る。その出願においても示されるように、ｎシン
ボルの符号語の鎖の形で入力されてくるデータの
不断の継列においてデコード処理が連続し、この
ため、その名称がオン・ザ・フライ・デコードで
ある。実際的な観点から、所定のデコード処理が
以下のテストに合致するならば、すなわち、先行
して受け取られた符号語の訂正済みのデータバイ
トが、つぎの符号語のデータバイトが受け取られ
る間にユーザ・システムに送出されるならば、そ
のデコード処理はオン・ザ・フライであると考え
ることができる。デコーダはブロツク６，７，８，９を有し、先
に受け取られ流出されていく符号語に存在するエ
ラーをデコードして訂正するときに、流入されて
くる符号語についてシンドロームを計算する。流
出されていく符号語の１つの訂正されたデータシ
ンボルの出力と同時に起こる、流入されてくる符
号語の１つのデータシンボルの入力に、各クロツ
クサイクルが関連する。バツフア５は流入シンボ
ルおよび流出シンボルの間で少なくともｎシンボ
ルの未訂正のデータを内部に保持する。 GF（2⁸）における３つのエラーを訂正するリー
ド・ソロモン符号がコンピユータ製品におけるア
プリケーシヨンのための特に重要な例として用い
られる。GF（2⁸）の256個の元が慣用的に８ビツ
ト２元ベクトルの集合によつて表わされる。この
ような表現の１つは表１において与えられる。３
つのエラーを訂正するリード・ソロモン符号に
は、生成多項式の根α⁰，α¹，α²，α³，α⁴，α⁵に対
応する６個のチエツクシンボルがある。ここでα
は有限体GF（2⁸）の元であり、８ビツト２元ベク
トルによつて表わされる。ブロツク６によつて計
算される対応するシンドロームは、それぞれS₀，
S₁，S₂，S₃おS₄およびS₅と表記される。このよう
なシンドロームはどのような既知の従来の処理に
も一致する通常の方法で、受け取られた符号語か
ら計算される。このステツプのための手段はよく
知られており、エクスクルーシブ・オア回路
（EX−OR回路とする）およびシフトレジスタを
用いる。ブロツク７の論理回路の詳細は第２図お
よび第３図で示される。

【表】

【表】ブロツク７の全部の機能は第２図および第３図
に示され、第１に、以下の４つの式を実行してロ
ケーシヨンパラメータΔ₃₃，Δ₃₂，Δ₃₁およびΔ₃₀
を形成することである。これらパラメータΔ₃₃，
Δ₃₂，Δ₃₁およびΔ₃₀はまたパラメーータΔ₂₂，Δ₂₁
およびΔ₂₀を内包する。そして、具体的な符号語
に含まれるエラーの正確な個数にしたがつて第３
図に示される論理回路によつてそのようなロケー
シヨンパラメータから係数Δ₃，Δ₂，Δ₁およびΔ₀
を選択する。Δ₃₃，Δ₃₂，Δ₃₁，およびΔ₃₀につい
ての式は以下のとおりである。 Δ₃₃＝S₂（S₁S₃S₂S₂）S₃（S₀S₃S₁S₂）S₄（S₁S₁S₂S₀）……(4) Δ₃₂＝S₃（S₁S₃S₂S₂）S₄（S₀S₃S₁S₂）S₅（S₁S₁S₂S₀）……(5) Δ₃₁＝S₀（S₄S₄S₃S₅）S₁（S₃S₄S₂S₅）S₂（S₃S₃S₂S₄）……(6) Δ₃₀＝S₁（S₄S₄S₃S₅）S₂（S₃S₄S₂S₅）S₃（S₃S₃S₂S₄）……(7) このようなパラメータはエラーロケーシヨン方
程式(2)の係数を決定するために用いられる。その
のち、第１図に示され先の出願において詳述され
るオン・ザ・フライのシステムのブロツク８およ
び９によつてエラーロケーシヨンおよびエラーパ
ターンが決定され得る。このエラーは他の公知で
より慣用されているエラー訂正システムにしたが
つて訂正してもよい。第２図に示される組み合わせ論理回路は２種類
の基本的な論理ブロツク１０および１１を含む。
第１のブロツク１０はＸにより表わされ、２つの
８ビツトベクトルを内包するGF（2⁸）における積
操作に対応し、他方、第２のブロツク１１はEX
−ORの元論理操作を表わす。ブロツク１１の動
作は８個の２入力EX−ORゲートを用いた簡単
なビツトごとのEX−OR論理機能である。他方、
ブロツク１０によつて表わされる積操作はより複
雑であり、71個のEX−OR回路および64個のア
ンド回路を伴う。ブロツク１０の積関数を説明す
る以下の例から、７個のEX−OR回路および64
個のアンド回路を必要とすることを理解し得る。ブロツク１０の積操作は２個の８ビツト・ベク
トルＡおよびＢに関するもので第３のベクトルＣ
を生成する。ここで、Ａ＝〔a₀，a₁，a₂，a₃，a₄，a₅，a₆，a₇〕Ｂ＝〔b₀，b₁，b₂，b₃，b₄，b₅，b₆，b₇〕Ｃ＝〔c₀，c₁，c₂，c₃，c₄，c₅，c₆，c₇〕この積は２つのステツプ処理を通じて得られ
る。第１に、積多項式Ｆの係数f_iを計算する。こ
こでＦ＝Ａ×Ｂ（mod.2）である。係数f_i（ｉ＝０，
……14）の計算に64個のアンド・ゲートおよび49
個のEX−ORゲートが必要とされる。すなわち f₀＝a₀b₀ f₁＝a₀b₁a₁b₀ f₂＝a₀b₂a₁b₁a₂b₀ f₃＝a₀b₃a₁b₂a₂b₁a₃b₀ 〓〓〓〓 f₇＝a₀b₇a₁b₆a₂b₅…a₆b₁a₇b₀ f₈＝a₁b₇a₂b₆a₃b₅…a₇b₁ 〓〓〓〓 f₁₃＝a₆b₇a₇b₆ f₁₄＝a₇b₇ 第２に、ｐ（ｘ）を法として多項式Ｆの剰余を
求める。ここでｐ（ｘ）は８次の原始２元多項式
である。ｐ（ｘ）＝１＋X³＋X⁵＋X⁷＋X⁸を用い
る。ｐ（ｘ）を法とするf_iの剰余は最大で22個の
EX−ORゲートを必要とする。 C₀＝f₀f₈f₉f₁₀f₁₂f₁₃ C₁＝f₁f₉f₁₀f₁₁f₁₃f₁₄ C₂＝f₂f₁₀f₁₁f₁₂f₁₄ C₃＝f₃f₈f₉f₁₀f₁₁ C₄歪＝f₄f₉f₁₀f₁₁f₁₂ C₅＝f₅f₈f₉f₁₁ C₆＝f₆f₉f₁₀f₁₂ C₇惑＝f₇f₈f₉f₁₁f₁₂ 積の処理の実施は、係数f₀からf₁₄に対して要求
される積項の各々ごとに１個の２入力アンド・ゲ
ートを伴い、これらアンド・ゲートの出力を結合
するために１個の２入力EX−ORゲートを伴う。
したがつて、各ブロツク１０は64個のアンド・ゲ
ートおよび71個のEX−ORゲートを表わす。エラーロケーシヨン多項式の第１項、Δ₃₃式の
S₂（S₁S₃S₂S₂）は第２図における破線のブロツ
ク１６によつて実行される。ブロツク１６の出力
はゲート１８において式の第２項とともにEX−
OR演算され、この演演算結果がゲート１９にお
いて式の最終項とともにEX−OR演算される。他のパラメータΔ₃₂，Δ₃₁およびΔ₃₀の各々を得
る際に伴われるブロツクは第２図において類似し
た態様でたどることができる。単に２個のエラーが生じる場合に対応するパラ
メータΔ₂₂，Δ₂₁およびΔ₂₀が式(1)においてΔ₃₃に
対する共通因数となる。これら共通因数は Δ₂₂＝S₁S₁S₂S₀ ……(5) Δ₂₁＝S₀S₃S₁S₂ ……(6) Δ₂₀＝S₁S₃S₂S₂ ……(7) 第２図において、Δ₂₂，Δ₂₁およびΔ₂₀に対する
計算はΔ₃₃に対する計算における中間的な副産物
として示される。同様に、Δ₁₁およびΔ₁₀はΔ₂₂に
対する式(8)の共通因数であり、つぎの式で与えら
れる。 Δ₁₁＝S₀ ……(8) Δ₁₀＝S₁ ……(9) シンドロームについてのエラーロケーシヨン多
項式の下記の従来の関係式から、ロケーシヨンパ
ラメータを得るための式がどのように導き出され
るかについてはのちにこの欄において示される。 S₀ S₁ S₂ S₁ S₂ S₃ S₂ S₃ S₄σ₀ σ₁ σ₂＝σS₃ S₄ S₅ (10) 第３図はロケーシヨンパラメータΔ₃₃〜Δ₃₀お
よび共通因数Δ₂₂〜Δ₁₀からエラーロケーシヨン
多項式の係数を選択するための論理回路を示す。
第３図の論理回路は入力パラメータΔ₃₃〜Δ₃₀お
よび共通因数Δ₂₂〜Δ₁₀からエラー数を特定して
つぎの一般式における適切な値Δ_nを選択するよ
うに作用する。 Δ_n＝Δ_nn ただしｍ＞ｖ Δ_vn ただしｍ≦ｖ ……(11) Δ₃₃がゼロでなく、３個のエラーがあることを
示すときに、係数Δ₃〜Δ₀は値Δ₃₃〜Δ₃₀となる。
示されるように、Δ₃₃がゼロでないときに、アン
ドゲート４１の出力は低レベルである。そして、
アンドゲード４１の出力はアンドゲート４２，４
３および４４の各々の入力端で反転され各アンド
ゲート４２〜４４をイネーブルとするので、アン
ドゲード４１の出力はΔ₃₂，Δ₃₁およびΔ₃₀の信号
がアンドゲート４２〜４４をそれぞれ通じてゲー
トされ得るようにする。 Δ₃₃がゼロであり２以上のエラーがないことを
示すならば、同様の論理機能はΔ₂₂によつて達成
される。このような状況において、Δ₂，Δ₁およ
びΔ₀はそれぞれアンドゲート５１，５２および
５３の動作を通してそれぞれΔ₂₂，Δ₂₁およびΔ₂₀
の値を取る。この機能は２つのエラーのためのシ
ンドローム方程式に対応する。 Δ₂₂もまたゼロであれば、第３図の論理回路は
同様にΔ₁およびΔ₀をΔ₁₁およびΔ₁₂の値とするよ
う機能する。アンドゲート６０はイネーブル信号
を与えるので、Δ₃₃およびΔ₂₂がともにゼロであ
れば、アンドゲート６１および６２はΔ₁₁および
Δ₁₀をそれぞれオアゲート７１，７２を通じてゲ
ートする。したがつて、第３図の全論理回路は第２図の論
理回路によつて形成されたロケーシヨンパラメー
タからエラーロケーシヨン方程式のための係数
Δ₃，Δ₂，Δ₁およびΔ₀の正しい値を生成、すなわ
ち選択するよう機能する。以上では３バイトエラー訂正リードソロモン符
号という特別な場合について詳述したけれども、
以上に教示したところにしたがつてどのような多
数エラー訂正巡回符号たとえばBCH符号のため
のデコーダをも実施し得る。以下では、第２図および第３図の論理回路手段
において用いられる式を数学的に誘導する。 GF（2⁸）における３バイトエラー訂正リード・
ソロモン符号では、生成多項式の根α⁰，α¹，α₂，
α³，α⁴，α⁵に対応して６個のチエツクシンボルが
ある。対応するシンドロームはそれぞれS₀，S₁，
S₂，S₃，S₄およびS₅によつて表記される。ここで最大で３個のシンボルにエラーがあると
仮定しよう。エラーバリユーはE_i1，E_i2およびE_i3
で表記され、誤つたシンボルのロケーシヨンは
i₁，i₂およびi₃で表記される。そうすると、シン
ドロームおよびエラーの間の関係は S_j＝α^ji1E_i1α^ji2E_i2α^ji3E_i3 ただしｊ＝０，１，２，３，４，５
（1A）で与えられる。根がαⁱ¹，αⁱ²およびαⁱ³の多項式を
考える。これはエラーロケーシヨン多項式と呼ば
れ、（ｘαⁱ¹）（ｘαⁱ²）（ｘαⁱ³）＝ x³σ₂x²σ₁xσ₀ …（2A）で与えられる式（2A）でｘ＝αⁱの代入を行い α³ⁱσ₂α²ⁱσ₁αⁱσ₀＝０ただしｉ＝i₁，i₂およびi₃…（3A）を得る。式（1A）および（3A）から、シンドロームS_j
およびエラーロケーシヨン多項式の係数σ_iの間に
成立する以下の関係式を導き出せる。 S₀ S₁ S₂ S₁ S₂ S₃ S₂ S₃ S₄σ₀ σ₁ σ₂＝S₃ S₄ S₅ ……(4A) 式(4A)を解いて、 σ₀＝Δ₃₀／Δ₃₃、σ₁＝Δ₃₀／Δ₃₃、σ₂＝Δ₃₂／Δ_3
3…(5A) のとおりのσ₀，σ₁およびσ₂を得ることができる。
ここでΔ₃₃，Δ₃₂，Δ₃₁およびΔ₃₀は Δ₃₃＝S₂（S₁S₃S₂S₂）S₃（S₀S₃S₁S₂S₄（
S₁S₁S₂S₀）…(6A) Δ₃₂＝S₃（S₁S₃S₂S₂）S₄（S₀S₃S₁S₂）S₅（S₁S₁S₂S₀）…(7A) Δ₃₁＝S₀（S₄S₄S₃S₅）S₁（S₃S₄S₂S₅）S₂（S₃S₃S₂S₄）…(8A) Δ₃₀＝S₁（S₄S₄S₃S₅）S₁（S₃S₄S₂S₅）S₃（S₃S₃S₂S₄）…(9A) より得る。もしΔ₃₃の値が０ならば、式(4A)は３個未満の
エラーがあることを示す従属集合である。この場
合、シンドロームは２個のエラーに対応して処理
され、ここでは２バイトエラーの場合についての
同様の方程式からパラメータΔ₂₂，Δ₂₁およびΔ₂₀
が誘導され、これらは Δ₂₂＝S₁S₁S₂S₀ ……(10A) Δ₂₁＝S₀S₃S₁S₂ ……(11A) Δ₂₀＝S₁S₃S₂S₂ ……(12A) より得られる。 Δ₃₃＝S₂Α₂₀S₃Δ₂₁S₄Δ₂₂ ……(13A) のように書き直し得る式(6A)から理解されるよう
に、これらがΔ₃₃の共通因数であることに留意す
る。そうすると、２バイトエラーの場合に対応す
るバリユーΔ₂₂，Δ₂₁およびΔ₂₀は個別に計算する
必要がない。これらはΔ₃₃を得るための計算の副
産物のかたちで手に入るのである。同様に、１バ
イトエラーの場合に対応するΔ₁₁およびΔ₁₀は Δ₁₁＝S₀ ……(14A) Δ₁₀＝S₁ ……(15A) により得られ、これらはΔ₂₂の共通因数であり、
シンドロームとして容易に入手可能でもある。ｖが正確なエラー数を表記するとしよう。ｖは
３，２，１また０をとり得る。正確なエラー数はつぎのように決定される。ｖ＝3ifΔ₃₃＝／０ｖ＝2ifΔ₃₃＝０かつΔ₂₂＝／０ｖ＝1ifΔ₃₃＝Δ₂₂＝０かつΔ₁₁＝／０ｖ＝0ifΔ₃₃＝Δ₂₂＝Δ₁₁＝０ ……(16A) ２バイトエラーおよび１バイトエラーのような
特別な場合は適当な行列式を選択することにより
自動的に適用され得る。この目的のためにΔ₃，
Δ₂，Δ₁およびΔ₀を Δ₃＝Δ₃₃ ……(17A) Δ₂＝Δ₃₂if ｖ＝３ Δ₂₂if ｖ＝２ ……(18A) Δ₁＝Δ₃₁if ｖ＝３ Δ₂₁if ｖ＝２ Δ₁₁if ｖ＝１ ……(19A) Δ₀＝Δ₃₀if ｖ＝３ Δ₂₀if ｖ＝２ Δ₁₀if ｖ＝１ ……(20A) のように規定しよう。そうすると、式(5A)を σ₀＝Δ₀／Δ_v、σ₁＝Δ₁／Δ_v、σ₂＝Δ₂／Δ_v……(
21A) のように書き直せる。通常、係数が式(21A) のσ₀，σ₁およびσ₂である
と、エラーロケーシヨン多項式(3A)は周知のチエ
ン・サーチの手順を通じてエラーロケーシヨンを
決定するために用いられる。しかしながら、Δ_v
によつて割り切れてしまうことを回避するために
エラーロケーシヨン方程式を修正することがあ
る。修正されたエラーロケーシヨン方程式は Δ₃α³ⁱΔ₂α²ⁱΔ₁αⁱΔ₀＝０ ……(22A) として得られる。エラーロケーシヨン数は、式(2
２Ａ）を満たすｉに属するｖ個の１つしかないバ
リユーの集合である。つぎにエラーバリユーE_i1，E_i2およびE_i3を求め
る式を誘導する。ｊ＝０，１および２についての
式(1A)から１１１ αⁱ¹ αⁱ² αⁱ³ α²ⁱ¹ α²ⁱ² α²ⁱ³E_i1 E_i2 E_i3＝S₀ S₁ S₂ ……(23A) を得、この(23A) をE_i1について解いて E_i1＝S₀αⁱ²⁺ⁱ³S₁（αⁱ²αⁱ³）S₂／
αⁱ²⁺ⁱ³αⁱ¹（αⁱ²αⁱ³）α²ⁱ¹ を得る。式(2A)から σ₀＝αⁱ¹ ⁱ² ⁱ³ ……(25A) σ₂＝αⁱ¹α_i2αⁱ³ ……(26A) を得、式(24A) ，(25A) および(26A) から E_i1＝S₀σ₀αⁱ¹S₁σ₂α²ⁱ¹S₁αⁱ¹S₂／σ₀α²ⁱ¹α₂……(27A) を得る。式(5A)を用いると式(27A) を E_i1＝S₀Δ₀（S₁Δ₂S₂Δ₃）αⁱ¹S₁Δ
₃α²ⁱ¹／Δ₀Δ₂α²ⁱ¹……(28A) に約分できる。式(28A) のエラーバリユーE_i1は
i1の項で表わされ、このためi2およびi3について
の明白なバリユーなしにそれを計算し得ることに
留意されたい。他のエラーバリユーE_i2およびE_i3
も同様な式で表わされる。エラーバリユーを求め
るためのより一般的な式は現行の変数ｉをi1に置
き換えて式(28A) を書き直すことによりつぎのよ
うに得られる。 E_i＝Φ₀Φ₁α_iΦ₂α²ⁱ／Δ₀Δ₂α_2i (29A) ここで、係数Φ₀，Φ₁およびΦ₂は Φ₀＝S₀Δ₀ ……(30A) Φ₁＝S₁Δ₂S₂Δ₃ ………(31A) Φ₂＝S₁Δ₃ ……(32A) により与えられる。式(29A) はデコード処理の通
常のステツプ４をステツプ３に連結させることが
でき、ここではエラーバリユーE_i1，E_i2およびE_i3
がエラーロケーシヨンのチエン・サーチに同期し
て計算される。そして、シンドロームデコーダは式(22A) およ
び(29A) における種々の数量をｉに属する値の
各々に対して循環的な繰り返しの態様で計算する
ことから成り、そして式(22A) が満たされるとき
は出力されてくるシンボルをいつでもE_iを用いて
訂正するようにする。〔ｔ個のエラーの一般的な場合〕以下の説明では、第２図、第３図，第４図およ
び第５図において示された３バイトエラーまでの
特別な場合に対応する論理回路が広くｔバイトエ
ラーについても適用可能であることを立証するた
めに、一般的な場合について数学的な誘導を行
う。一般的なBCHまたはリード・ソロモン符号に
おいて、符号語はｎ個のシンボルからなり、生成
多項式の根α^a，α^a+1，α^a+2，……α^a+r-1に対応し
たｒ個のチエツク・シンボルがｎ個のシンボルに
含まれる。ここでαはガロア体GF２５６の元で
ある。整数ａとしてゼロが採用されるが、以下の
結論はこのようなａの値についても誘導が可能で
ある。対応するシンドロームはそれぞれS₀，S₁，
S₂，……，S_r-1によつて表記される。シンドロー
ムは供給された符号語から S_j＝_o-1 〓〓ⁱ⁼⁰ α^jiＢ〓_i ｊ＝０，１，２…，（ｒ−１）……(1
B) のようにして計算され得る。ここでＢ〓₀，Ｂ〓₁，Ｂ〓
_２，……，Ｂ〓_o-1は供給された符号語のｎ個のシン
ボルである。所定の符号語中の実際のエラーシンボル数をｖ
と表記する。エラーバリユーはE_iによつて表記さ
れる。ここで、ｉは｛Ｉ｝＝｛i₁，i₂，……，i_v｝
で与えられるｖ個の異なるエラーロケーシヨンか
らなる集合からエラーロケーシヨンバリユーを表
わす。そしてシンドロームおよびエラーの間の関
係は S_j＝〓ⁱ 〓{^I}α^jiE_i ｊ＝０，１，２…，（ｒ−１）……(2B) で与えられる。どのような非零のシンドロームバ
リユーもエラーがあることを示す。デコーダはエ
ラーロケーシヨンおよびエラーバリユーを決定す
るためにこれらシンドロームを処理する。不明瞭
さをともなうことなしにデコードし得る最高のエ
ラー数をｔと表記しよう。ｔ個のエラーのエラー
ロケーシヨンおよびエラーバリユーを決定するに
はｒ＝2tのシンドロームの集合が必要である。根がαⁱの多項式を考える。ここでiε｛Ｉ｝であ
る。これはエラーロケーシヨン多項式と呼ばれ、〓 ie｛Ｉ｝（１−α^-iｘ）＝_v 〓^m=0 σ_nx^m＝_t 〓^m=0 σ_nx^m (3B) で定義される。ここでσ₀＝１，σ_v＝／０、かつσ_n＝
０（ｍ＞ｖ）である。ｍｖの未知の係数σ_nは式
（１Ｂ）のシンドロームから以下のようにして決定さ
れ得る。式(3B)にｘ＝αⁱを代入して _t 〓^m=0 σ_nα^mi＝０ただしiε｛Ｉ｝ ……(4B) を得る。式(2B)および(4B)を用いれば、シンドロ
ームS_jおよびエラーロケーシヨン多項式の係数σ_n
がつぎの関係式を満たすことを容易に示すことが
できる。 _t 〓^m=0 σ_nS_n+k＝０ただしｋ＝０，１，……，ｔ−１ ……(5B) 式(5B)の組を行列表記で S₀ S₁…S_t S₁ S₂…S_t-1 S_t-1 S_t S_2t-1σ₀ σ₁ σ_t-1 σ_t＝０ ……(6B) として書き直せる。方程式(6B)の左片のtx（ｔ＋１）のシンドロー
ム行列をＭで表記しよう。行列Ｍ中の最終列を除
去して得た正方行列をM_tとしよう。M_tが正則で
あれば上の方程式の組はクラマの法則を用いて解
くことができ、 σ_n／σ_t＝Δ_tn／Δ_ttただしｍ＝０，１，……ｔ−１ ……(7B) を得る。ここでΔ_ttは行列M_tからなる非零の行列
式であり、ｍ＝０，１，……，ｔ−１の各々につ
いて行列M_tのｍ番目の列をシンドローム行列Ｍ
の最終列の負数で置き換えて得た行列の行列式を
Δ_tnで表記する。行列M_tが正則でなければ、すなわちΔ_ttがゼロ
であれば、方程式(5B)は従属集合であり、これは
ｔより少ないエラーがあることを意味する。この
場合、σ_tはゼロである。式(6B)においてσ_tおよび
シンドローム行列の最終列および最終行を削除す
ることができる。この結果得られた行列方程式は
ｔ−１個のエラーのためのものに対応する。この
処理は適宜繰り返され、最終的な行列はｖ個のエ
ラーのためのものに対応し、Ｍは正則となる。そ
して行列式Δ_vnの集合が必要とされる。ここで、
ｍ＝０，１，……，ｖである。ｖ＝ｔ−１のΔ_vnが、行列M_tの第（ｍ−１）番
目の行およびｔ番目の列に関連したΔ_ttの共通因
数であることは容易に理解される。このような共
通因数の項でΔ_ttを表わすことができる。この発明はその好ましい実施例を参照して具体
的に図示および詳述されたけれども、この発明の
精神および範囲を逸脱することなく形態および細
部に種々の他の変更をなし得ることは当業者にお
いて容易に理解されるところである。

【図面の簡単な説明】

第１図はこの発明をオン・ザ・フライ方式の３
バイトエラー訂正システムに適用した一実施例を
系統的に示すブロツク図、第２図は第１図例にお
いてロケーシヨンパラメータを演算するデコーダ
に彩用される組み合わせ論理回路を概略的に示す
図、第３図は第１図例において３個以下のエラー
が検出されたときに正確なエラー数を特定して適
切なロケーシヨンパラメータを選択することによ
り係数Δ_nを得る組み合わせ論理回路を示す図で
ある。５……ｎバイトのバツフア、６……シンドロー
ム演算を行うブロツク、７……Δ_j演算を行うブ
ロツク、８……Φ演算を行うブロツク、９……エ
ラーロケーシヨンおよびエラーバリユー演算を行
うブロツク、１０……積操作を行う第１のブロツ
ク、１１……加算操作を行う第２のブロツク、４
１〜４４、５１〜５３、６０〜６３……アンドゲ
ート、７１，７２……オアゲート。

Claims

【特許請求の範囲】１符号語が2^b個のキヤラクタ・ポジシヨンを有
し、このキヤラクタの各々がｂ個の二元ビツトの
個別の連結からなるバイトにより表わされ、シン
ドロームバイトが各々ｂ個の二元ビツトを有し、
生成多項式の根α^a，α^a+1，α^a+2，……，α^a+2t-1
（αは2^b個の元を有する有限体の元）を写すパリ
テイチエツク行列にしたがつて前記シンドローム
バイトが形成され、前記符号語中のｔ個までのエ
ラーを2t個の前記シンドロームバイトを処理する
ことにより検出し得るような多数バイトエラー訂
正システムにおいて、前記符号語から2t個のシンドロームバイトを生
成するためのシンドローム生成手段と、前記2t個のシンドロームに応答して前記符号語
に対応するエラーロケーシヨン多項式のために
（ｔ＋１）個の係数を発生する回路手段とを備え、前記回路手段は、前記シンドロームバイトの所
定の論理演算により前記エラーロケーシヨン多項
式のロケーシヨンパラメータ△_tn（ここで、ｍ＝
０，１，２，……ｔ）信号およびこのロケーシヨ
ンパラメータに対応する共通因数△_on（ここで、
ｍ≦ｎ，ｎ＝１，２，……ｔ−１）信号をそれぞ
れ発生する第１の論理手段と、前記ロケーシヨン
パラメータ信号と前記共通因数信号とを組合わせ
て論理演算することによつて前記エラーロケーシ
ヨン多項式の係数△_n＝〔△_nn（ただし、ｍ＞ｖ），
△_vn（ただし、ｍ≦ｖ）〕（ここで、ｖ＝１，２，
……ｔ）信号を出力する第２の論理手段とを含む
ことを特徴とする多数バイトエラー訂正システ
ム。