JPH0361210B2

JPH0361210B2 -

Info

Publication number: JPH0361210B2
Application number: JP57028325A
Authority: JP
Inventors: Toshio Horiguchi
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1982-02-24
Filing date: 1982-02-24
Publication date: 1991-09-19
Also published as: JPS58144952A

Description

【発明の詳細な説明】本発明は２重バイト誤りを訂正する回路に関
し、特に少ない回路量でランダムな２重バイト誤
りを高速に訂正する回路に関する。

磁気フアイル等のフアイル装置のデータ信頼性
を向上するためにしばしば単一バイト誤りを訂正
するリード・ソロモン（Reed−Solomon）符号
やｂ隣接誤り訂正符号が用いられている。磁気媒
体よりもエラーレートの悪い媒体を用いる場合又
はデータ信頼度をより向上させるためにはランダ
ムな２重バイト誤りを訂正する能力をもつリー
ド・ソロモン符号を用いるのが望ましい。しかし
ながら、２重バイト誤り訂正の欠点のひとつは誤
つたバイトの位置と誤りパターンを解読する回路
の規模が大きくなる点にある。

ひとつのバイトは一般にｍビツトで表わされ、
このようなバイトの誤りを訂正するには符号内で
の誤り位置と誤りパターンを解読する必要があ
る。解読（復号）に際してはまず、シンドローム
から誤り位置を計算し、ついで得られた誤り位置
を用いて誤りパターンを計算する方法が用いられ
る。２重バイト誤りを訂正するリード・ソロモン
符号の復号は公知であるが、この方法は次の３つ
のステツプを取るので復号過程が複雑となる欠点
をもつ。

（ステツプ１）シンドロームから誤りバイト位
置に関する２次方程式、すなわちエラー・ロケー
シヨン多項式（error location polynomial）の
係数を求める。

（ステツプ２）エラー・ロケーシヨン多項式の
２つの根を求める。この根は誤りバイト位置を表
わす。

（ステツプ３）求められた２つの誤り位置とシ
ンドロームとから各誤り位置に対応する２つの誤
りパターンを求める。

このため従来の２重バイト誤り訂正を含む復号
器は復号遅延時間が大きくしかも回路規模も大き
くなる欠点を有していた。ここで、復号遅延時間
とはデータ・ブロツクの受信の終了時点から訂正
されたデータの転送を開始するまでの時間であ
る。フアイル装置においてはデータはバイト単位
にシリアルに転送される。受信データ・ブロツク
はバツフア・メモリに一度貯えられた後に誤りを
訂正され、ついで上位装置に転送される。

従来の２重バイト誤り訂正方法では、データ・
ブロツクの受信終了時間から前記ステツプ１，２
及び３を実行し、バツフア・メモリに貯えられた
データの誤りを訂正してから上位装置に転送する
ので復号遅延時間が大きくなる。特にバースト誤
り訂正のために２重バイト誤り訂正リード・ソロ
モン符号を複数個インタリーブする際には、この
復号遅延時間がかなり大きくなり実用上問題とな
る。

復号遅延時間を小さくするためにはエラー・ロ
ケーシヨン多項式を立てずにシンドロームから直
接的に誤り位置とパターンを求める方法が必要で
あるが、このような方法はこれまで知られていな
かつた。

従つて本発明の目的は２重バイト誤り訂正リー
ド・ソロモン符号に対して、エラー・ロケーシヨ
ン多項式を立てずに直接的に誤り位置とパターン
を求める誤り訂正回路を提供することにある。

本発明の２重バイト誤り訂正回路はデータ・ブ
ロツクの受信終了後、エラー・ロケーシヨン多項
式を立てることなしにバツフアメモリからデー
タ・バイトを読み出し、誤りを訂正しながら上位
装置にデータ・バイトを転送するので復号遅延時
間はゼロである。又、誤り訂正回路の回路量も少
い。さらに、符号を複数個インタリーブするのに
適した構造を持つ。

本発明の２重バイト誤り訂正回路は、任意の整
数ｍで定義されるガロワGF（2^m）の原始元αを用
いて構成される２重バイト誤り訂正リード・ソロ
モン符号のパリテイ検査行列Ｈ、１１………１………１ α¹α²………αⁱ………αⁿ Ｈ＝ α²α⁴………α²ⁱ………α²ⁿ α³α⁶………α³ⁱ………α³ⁿ に従つてデータを符号化するシステムにおいて、
ｎバイトの受信符号ブロツクにランダムに生起し
た２重バイト誤りを訂正する復号回路を提供す
る。ここでｎ＝2^m−１で、バイトはｍビツトで表
わされる。ここでｎバイトのブロツクの中の４バ
イトが検査バイトで、（ｎ−４）バイトが情報バ
イトである。

本発明の復号回路は前記検査行列Ｈの第１行，
第２行，第３行及び第４行に対応するシンドロー
ムS₁，S₁，S₂及びS₃を生成するシンドローム生成
回路と、前記シンドロームの間の排他的ORS₀
S₁，S₁S₂及びS₂S₃をとる回路と、前記排他的
ORA₀＝S₀S₁，A₁＝S₁S₂及びA₂＝S₂S₃に
関してA₀・A₂A₁ ²＝０を検出することによつて
誤りパターンを求めめる論理回路とから構成され
る。

実施例を説明する前に本発明の原理について説
明する。本発明において、シンドロームS₀，S₁，
S₂及びS₃は前記パリテイ検査行列Ｈに従つて生成
される。すなわち、b₁，b₂，………，b_oを受信さ
れたｎバイトの符号語（バイトb₁はｍビツト）と
すると、シンドロームは下式に従つて生成される S₀＝b₁ ……b_i ……b_o S₁＝b₁α¹……b_iαⁱ……b_oαⁿ S₂＝b₁α²……b_iα²ⁱ……b_oα²ⁿ S₃＝b₁α³…b_iα_3i……b_oα³ⁿ｝ (1) ここで、は排他的ORを示す。ｉ番目のバイ
トb_iに誤りパターンe_i、ｊ番目のバイトb_jに誤り
パターンe_jの誤りが生じたとするとシンドローム
は下式のように表わされる。但しe_i≠０，e_j≠０，
ｉ＝j₀ S₀＝e_i e_j S₁＝e_iαⁱe_jα^j S₂＝e_iα²ⁱe_jα^2j S₃＝e_iα³ⁱe_jα^3j｝ (2) 上記シンドロームS₀，S₁，S₂及びS₃はそれぞれ
α⁰（＝１），α¹，α²及びα³をフイードバツク係数に
持つシンドローム・レジスタにバイトb_o，b_o-1，
……，b₂，b₁をこの順に入力することによつて生
成される。

本発明においては、シンドローム生成後に誤り
位置を探すためにシンドローム・レジスタをさら
にシフトする。式(2)で表わされる２重シンボル誤
りを仮定すれば、ｋ回シフト後のシンドローム
（シンドローム・レジスタの内容）S₀，S₁，S₂及
びS₃は次式で表わされる。

S₀＝e_i e_j S₁＝e_iα^i+k e_jα^j+k S₂＝e_iα^2(i+k)e_jα^2(j+k) S₃＝e_iα^3(i+k)e_jα^3(j+k)｝ (3) 上記シンドロームの間の排他的OR、すなわち
A₀＝S₀S₁，A₁＝S₁S₂及びA₂＝S₂S₃は下式
で表わされる。

A₀＝S₀S₁＝e_i（１α^i+k）e_j（１α^j+k） A₁＝S₁S₂＝e_i（１α^i+k e_j（１α^j+k A₂＝S₂S₃＝e_i（１α^i+k）α^2(i+k) e_j（１α^j+k）α^2(j+k)｝ (4) ここで、Ｌ＝A₀A₂A₁ ²と定義すれば、シフト
回数ｋがｋ＝ｎ−ｉ又はｋ＝ｎ−ｊの時だけＬ＝
０となることが以下のようにして分る。Ｌ＝
A₀A₂A₁ ²に前式(4)を代入すれば、Ｌは次の式(5)
で表わされる。

Ｌ＝e_ie_j（１α^i+k）（１α^j+k)（α^2(i+k)α^2(j
+k)）(5) ここで、ｉ≠ｊであるからα^2(i+k)α^2(j+k)≠０
である。Ｌ＝０となるのは１α^i+k＝０又は１
α^j+k＝０の時だけである。換言すればα^i+k＝１又
はα^j+k＝１の時に限つてＬ＝０となる。ここでαⁿ
＝α⁰＝１であるから、ｉ＋ｋ＝ｎ又はｊ＋ｋ＝ｎ
の時、すなわちｋ＝ｎ−ｉ及びｋ＝ｎ−ｊの時に
限りＬ＝０となる。ｉ＋ｋ＝ｎ（又はｊ＋ｋ＝ｎ）
の時にＬ＝０となることは次のようにも理解でき
る。ｉ＋ｋ＝ｎの時は前式(4)において１＋α^i+k
＝０であるからA₀，A₁，A₂は次のようになる。

A₀＝e_j（１α^j+k A₁＝e_j（１α^j+k A₂＝e_j（１α^j+k）α^2(j+k) この時から、明らかにA₀・A₂＝A₁ ²＝e_j ²（１
α^j+k）²・α^2(j+k)であるから、Ｌ＝A₀・A₂A₁ ²＝
０である。

以上より、バイト位置ｉとｊに誤りが生じてい
ればシンドローム・レジスタを（ｎ−ｉ）回及び
（ｎ−ｊ）回シフトした時にＬ＝０となることが
示された。ここで、ｎバイトのバツフア・メモリ
（シフト・レジスタ）を用意しておき、ｎバイト
の受信データ・バイトb_o，b_o-1，……，b₂，b₁を
シンドローム・レジスタに入力すると同時にバツ
フア・メモリにも入力するものとする。そして、
誤り訂正のためにシンドローム・レジスタをシフ
トすると同時にバツフア・メモリに貯えられてい
るデータをシフト出力するものとする。バツフ
ア・メモリからはデータバイトb_o，b_o-1，……，
b₁がこの順にシフト出力される。従つて、（ｎ−
ｋ）回目のシフトでバツフア・メモリからはデー
タ・バイトb_kが出力される。

いま、ｉ番目のデータb_iとｊ番目のデータb_jに
誤りがあるとすれば（ｉ＞ｊ）、（ｎ−１）回目の
シフトでＬ＝０となり、同時にバツフア・メモリ
からデータバイトb_iが出力される。さらに（ｎ−
ｊ）回目のシフトでＬ＝０となり、バツフア・メ
モリからデータバイトb_jが出力されることにな
る。すなわち、誤りのあるバイトがバツフア・メ
モリから出力された時点で丁度Ｌ＝０となる。従
つて、Ｌ＝０となるバイトに対する誤りパターン
を求めれば誤りを訂正できる。

誤りパターンは下式で求められる。

ｅ＝S₀A₀ ²（A₀A₁）^-1 (6) ｉ番目のバイトb_iに誤りパターンe_i，ｊ番目の
バイトb_jに誤りパターンe_jが生じていれば、ｋ回
目のシフト（ｋ＝ｎ−ｉ）でＬ＝０となり、この
時A₀，A₁，A₂及びS₀は下式で表わされる。

S₀＝e_i e_j A₀＝e_j（１α^j+k A₁＝e_j（１α^j+k）α^j+k A₂＝e_j（１α^j+k）α^2(j+k)｝ (7) この時、誤りパターンｅは下式のようにe_iに等
しくなる。

ｅ＝S₀A₀ ²（A₀A₁）^-1＝e_i (8) 又、この時バツフア・メモリからはバイトb_iが
出力されているから、バイトb_iの誤りはb_ie_iで
訂正される。

ｊ番目のバイトb_jの誤りパターンe_jに対しても
前式(7)，(8)と同様な式が成立し、バイトb_jの誤り
が訂正される。ここで、誤りパターンｅを計算す
る式は式(6)以外にも存在し、例えばｅ＝S₀A₀
（１√₂・₀ ^-1）^-1，ｅ＝S₀A₀（１A₂・
A₁ ^-1）^-1等でも計算できるが、式(6)の計算方法が
最も容易と考えられる。

以上のように２重バイト誤りに対して、誤り位
置はＬ＝A₀A₂A₁ ²＝０により、誤りパターンは
ｅ＝S₀A₀ ²（A₀A₁）^-1によつて求められる。

前記Ｌ及びｅによつて単一バイト誤りも訂正で
きることを以下で示す。いま、ｉ番目のバイトb_i
に誤りパターンe_iの誤りが生じたとするとシンド
ロームS₀〜S₃は下式で表わされる。

S₀＝e_i S₁＝e_iαⁱ S₂＝e_iα²ⁱ S₃＝e_iα³ⁱ｝ (9) シンドローム・レジスタをｋ回シフトするとシ
ンドロームは S₀＝e_i S₁＝e_iα^j+k S₂＝e_iα^2(j+k) S₃＝e_iα^3(j+k)｝ (10) となる。A₀，A₁，A₂は A₀＝S₀S₁＝e_i（１α^i+k） A₁＝S₁S₂＝e_i（１α^i+k）α^i+k A₂＝S₂S₃＝e_i（１α^i+k）α^2(i+k)｝ (11) であるから、任意のシフト回数ｋに対してＬ＝
A₀A₂A₁ ²＝０である。又、誤りパターンｅ＝S₀
A₀ ²（A₀A₁）^-1はｉ＋ｋ≠ｎに対してｅ＝０、
ｉ＋ｋ＝ｎに対してはｅ＝e₁となる。すなわち、
任意のシフト回数ｋに対してＬ＝０であるが、ｋ
≠ｎ−ｉの時はｅ＝０であるから訂正ミスは生じ
ない。又、ｋ＝ｎ−ｉの時はｅ＝e_iとなり誤りが
正しく訂正される。

従つて、単一バイト誤りが２重バイト誤りと同
様に正しく訂正されることが示された。

以上のように本発明では受信データ・バイトか
らシンドロームを生成するとともにバツフア・メ
モリに受信データを格納し、誤り訂正時にはシン
ドローム・レジスタをシフトするとともにバツフ
ア・メモリからデータ・バイトをシフト出力しな
がら誤つているバイトを訂正できる。換言すれ
ば、データを転送しながら誤りを訂正する。

従つて、データの受信終了後、即時的にデータ
の転送が可能であるから、復号遅延はゼロと考え
られる。これは本発明の一特徴であつて、誤りロ
ケーシヨン多項式を立ててから誤り訂正を行う従
来の方式では復号遅延はゼロとすることはできな
い。

以下図面を用いて本発明を説明する。

第１図は本発明の実施例を示すブロツク図であ
る。図において回路１〜４はそれぞれｍビツトの
レジスタ（シンドローム・レジスタ）で、回路２
０〜２２はそれぞれガロワ体GF（2^m）の要素α¹，
α²，及びα³を乗算する回路である。但し、αは
GF（2^m）の原始元である。回路５〜１２はそれぞ
れｍビツトの排他的OR回路である。図において
排他的OR回路５とレジスタ１はシンドロームS₀
の生成回路を、排他的OR回路とレジスタ２及び
α¹乗算回路２０はシンドロームS₁の生成回路を構
成する。又、排他的OR回路７とレジスタ３及び
α²乗算回路２１はシンドロームS₂の生成回路を、
排他的OR回路とレジスタ４及びα³乗算回路２２
はシンドロームS₃の生成回路を構成している。

回路１３はｎバイトのデータを貯えるバツフ
ア・メモリ（シフト・レジスタ）である。ここで
ｎ＝2^m−１であり、バイトはｍビツトである。ｎ
バイトのデータは第１図入力線ｄを介して前記各
シンドローム生成回路とバツフア・メモリ１３に
入力する。シンドローム・レジスタ１〜４及びバ
ツフア・メモリ１３のシフト・クロツクは第１図
における信号線によつて供給される。データ・バ
イトb_i（ｍビツト）を信号線に入力するととも、
信号線ｃにシフト・クロツクを加えることによつ
て、データ・バイトb_iがシンドローム・レジスタ
とバツフア・メモリに取り込まれる前記式(1)に則
して云えば、最初にデータバイトb_oを入力すると
ともにシフト・クロツクを入力する。次にデー
タ・バイトb_n-1について同様のオペレーシヨンを
行う。以下同様にしてデータ・バイトb₁までオペ
レーシヨンを行うとレジスタ１〜４の内容は式(1)
又は(2)で表わされるシンドロームS₀〜S₃となる。
第１図における排他的OR回路９の出力信号A₀＝
S₀S₁、排他的OR回路１０の出力信号A₁＝S₁
S₂及び排他的OR回路１１の出力信号A₂＝S₂S₃
は誤り位置検出回路１４に入力する。誤り位置検
出回路１４は信号A₀，A₁及びA₂が条件Ｌ＝A₀A₂
A₁ ²＝０を満たす時に出力信号ｇを論理１、す
なわちｇ＝１とする。出力信号ｇは第１図のゲー
ト回路１６のゲート信号として働く。第１図の誤
りパターン解読回路１５は信号A₀，A₁及びS₀か
ら誤りパターンｅをｅ＝S₀A₀ ²（A₀A₁）^-1に則
して生成し出力する。前記ゲート信号ｇと誤りパ
ターン信号ｅはゲート回路１６に入力する。ゲー
ト回路１６はゲート信号ｇが論理１の時その出力
ｆをｆ＝ｅとし、ゲート信号ｇが論理０の時は出
力ｆをｆ＝０とする通常のAND回路で構成され
る。排他的OR回路１２はバツフア・メモリ１３
の出力信号ｂとゲート回路１６の出力信号ｆの排
他的OR回路をとり信号ｈ＝ｂｆを出力する。
排他的OR１２の前記出力ｈは誤りが訂正された
データ・バイトを供給する。第１図において、シ
ンドロームS₀〜S₃の生成が終了した後、誤り訂正
を行うにはシフト・クロツクを信号線ｃに入力す
れば良い。ｋ番目のシフト・クロツクでシンドロ
ーム・レジスタ１，２，３及び４の内容は式(3)で
表わされるシンドロームとなり、バツフア・メモ
リ１３の出力ｂにはデータ・バイトb_o-kが出力さ
れる。

もし、データ・バイトb_o-kに誤りがあれば、誤
り位置検出回路１４の出力信号ｇが論理１となる
と同時に、誤りパターン解読回路１５の出力信号
ｅがデータ・バイトb_o-kの誤りパターンe_o-kに等
しくなり、データバイトb_o-kの誤りが排他的OR
１２を介して訂正される。

以下においてｍ＝４、すなわちガロワ体GF
（2⁴）で定義される。リード・ソロモン符号に対
する本発明の誤り訂正回路の構成を説明する。ｍ
＝４よりこの符号の符号長ｎは15（＝2⁴−１）で
ある。ここで１バイトは４ビツトを表わす。ｎ＝
15バイトの中の４バイトは検査バイトで残りの11
バイトは情報バイトである。

原始多項式Ｐ（ｘ）＝X⁴＋Ｘ＋１を法とするガ
ロワ体GF（2⁴）を考えれば、ガロワ体GF（2⁴）の
16個の要素０，α⁰（＝１），α¹α₂，………α¹⁴（但
し
α¹⁵＝α⁰）は第２図のように４ビツトのバイナ
リ・ベクトル（a₀a₁a₂a₃）で表わされる。

例えば、図のようにα⁹＝（0101）である。第２
図の対応を示す図で以下のように構成される。ガ
ロワ体GF（2⁴）の任意の要素αⁱはα⁰＝（1000），α¹
＝（0100），α²＝（0010）及びα³＝（0001）の線形結
合、すなわちαⁱ＝a₀α⁰a₁α¹a₂α²a₃α³＝
（a₀a₁a₂a₃）で表わされる。ここで、原始元αが
多項式Ｐ（ｘ）の根であることからＰ（α）＝１
αα⁴＝０である。よつてα⁴α⁰α¹＝（1100）。
又、例えば、α⁹は α⁹＝α⁴・α⁴・α¹＝（α⁰α¹）²α¹＝（α⁰α²）
α¹＝α¹
α³＝（0101）。

第１図におけα¹乗算回路２０は４ビツト入力
（a₀a₁a₂a₃）にα¹を乗算した結果（b₀b₁b₂b₃）を
出力する回路である。

ここで、（b₀b₁b₂b₃）＝α¹（a₀a₁a₂a₃）＝α¹（a₀α⁰a₁α¹
a₂α²a₃α³）＝a₀α¹a₁α²a₂α³a₃α⁴ ＝a₀α¹a₁α²a₂α³a₃（α⁰α¹）＝a₃α⁰（a₀a₃）α¹a₁α²a₂α³ ＝（a₃（a₀a₃）a₁a₂）であるから、b₀＝a₃，b₁＝a₀a₃，b₂＝a₁，b₃＝
a₂となる。

第３図は上式に対応す第１図のα¹乗算回路２０
を具体的に排他的OR回路３０を用いて構成した
ブロツク図である。

第４図は第１図におけるα²乗算回路２１を具体
的に構成したブロツク図であり、第３図のα¹乗算
回路を２段カスケード接続して構成される。

第５図は同様に第１図のα³乗算回路２２を具体
的にしたブロツク図であり、第３図のα¹乗算回路
を３段カスケード接続して構成される。

次に第１図における誤り位置検出回路１４の構
成について説明する。この回路は既に説明したよ
うに入力A₀，A₁及びA₂の間に条件A₀A₂A₁ ²＝
０が成立する時だけ出力ｇを論理１にする回路で
ある。条件A₀A₂A₁ ²＝０は次の（12a）〜
（12b）の式と等価である。

A₀A₂A₁ ²＝０（12a） A₁ ²／A₀A₂＝０（12b） A₁ ²／A₂A₀＝０（12c） A₀／A₁ ^A _1A2＝０（12d）従つて、誤り位置検出回路１４は上式（12a）〜
（12d）のいづれを用いても実現できる。以下で
は（12a）の条件判定を用いた場合の回路構成に
ついて説明する。

第６図は条件A₀A₂＝A₁ ²を用いた誤り位置検出
回路１４のブロツク図を示す。第６図において回
路４０は入力信号A₀とA₂とをガロワ体GF（2⁴）
の上で乗算してA₀・A₂を出力する回路であり、
回路４１は入力信号A₁をGF（2⁴）の上で２乗し
てA₁ ²を出力する回路である。ここで、入力A₀，
A₁，A₂及び出力A₀・A₂，A₁ ²はそれぞれ４ビツ
トである。回路４２は回路４０の出力信号A₀・
A₂と回路４１の出力信号A₁ ²との排他的ORをと
り、A₀・A₂A₁ ²を出力する４ビツトの排他的
OR回路である。回路４３は回路４２の出力信号
A₀・A₂A₁ ²の全てのビツトがゼロであることを
検出するＮＲ回路である。ＮＲ回路４３は
A₀・A₂A₁ ²＝０の時だけ出力信号ｇを論理１と
する。

前記GF（2⁴）上の乗算回路４０はAND及び排
他的OR回路から成るランダム・ロジツク回路又
は既存のプログラム可能なＲＭ（リード・オン
リ・メモリ）等のメモリ素子を用いて実現でき
る。特に本実施例の場合、入力A₀とA₂それぞれ
４ビツトで、出力A₀・A₂が４ビツトであるから、
回路４０は８ビツト・アドレス入力／４ビツト出
力（256語×８ビツト）のＲM1個で実現でき
る。ＲＭを用いる場合にはA₀をＲＭの上位
４ビツト・アドレスに、A₂をＲＭの下位４ビ
ツト・アドレスに入力し、対応するアドレス・ロ
ケーシヨンに積A₀・A₂を格納しておけば良い。

第７図は前記ROMのアドレスと出力の対応を
示す図である。図のようにROMのアドレス入力
がA₀＝α^p，A₂＝α^qならばA₀・A₂＝α^p+qが出力さ
れ、A₀又はA₂が０ならばA₀・A₂＝０が出力され
る。以上のようなアドレスと出力の対応は第２図
に示すαⁱとベクトル（a₀a₁a₂a₃）の対応を用いて
構成できる。例えばA₀＝α⁸＝（1010），A₂＝α¹¹＝
（0111）ならばA₀・A₂＝α⁸⁺¹¹＝α¹⁵⁺⁴＝α⁴＝
（1100）であるから、ROMのアドレス入力A₀＝
（1010），A₂＝（0111）に対応する出力はA₀・A₂
＝（1100）である。以上のようにｍ＝４の場合、
乗算回路４０は８ビツト・アドレス入力／４ビツ
ト・データ出力（256語×４ビツト）のＲＭで
１個で実現できる。一般にGF（2^m）上の乗算回路
４０は２ｍビツト・アドレス入力／ｍビツト出力
（2^2m語×ｍビツト）のROM1個で実現できる。市
販のプログラム可能なROMとしては256語×８
ビツト，1024語×８ビツト，4096語×８ビツトが
入手可能であから、これらのROMを１個用いて
それぞれGF（2⁴），GF（2⁵）及びGF（2⁶）の乗算回
路を実現できる。ｍ≧７であるGF（2^m）乗算回路
は、2^2m語×ｍビツトROMが入手できないので、
ROM1個は実現できない。この場合、複数個の
ROMを用いるか又はランダム・ロジツクでGF
（2^m）乗算回路を構成する必要がある。

第８図はGF（2⁴）乗算回路４０をAND回路、
排他的OR回路から成るランダム・ロジツクで構
成した場合のブロツク図を示す。GF（2⁴）乗算回
路４０の入力A₀とA₂をそれぞれ（a₀a₁a₂a₃），
（b₀b₁b₂b₃）で表わし、積出力A₀・A₂を
（c₀c₁c₂c₃）で表わせば、積（c₀c₁c₂c₃）は次のよ
うに表現される。

（c₀c₁c₂c₃）＝（a₀a₁a₂a₃）・（b₀b₁b₂b₃）＝（a₀α⁰a₁α¹a₂α²a₃α³）・（b₀b₁b₂b₃）＝a₀・α⁰（b₀b₁b₂b₃） a₁・α¹（b₀b₁b₂b₃） a₂・α²（b₀b₁b₂b₃） a₃・α³（b₀b₁b₂b₃）上式は入力（b₀b₁b₂b₃）からα⁰（b₀b₁b₂b₃），α¹
（b₀b₁b₂b₃），α²（b₀b₁b₂b₃）及びα³（b₀b₁b₂b₃）を
生成し、それぞれa₀，a₁，a₂及びa₃とのANDを
取り、さらに排他的ORを取れば積（c₀c₁c₂c₃）
が生成されることを示している。従つて、GF
（2⁴）乗算回路４０は第８図のようにα¹乗算回路
５２，５３及び５４、ANDゲート５５，５６，
５７及び５８と排他的OR回路５９を用いて構成
される。α乗算回路５２，５３及び５４は第３図
のα乗算回路と同一のものである。

第９図は第６図におけるGF（2⁴）２乗回路４１
のブロツク図を示す。２乗回路４１における４ビ
ツトの入力信号A₁と出力信号A₁ ²を、ベクトルで
表わしA₁＝（a₀a₁a₂a₃），A₁ ²＝（b₀b₁b₂b₃）とすれ
ばb₀〜b₃はb₀＝a₀a₂，b₁＝a₂，b₂＝a₁a₃，b₃
＝a₃で表わされる。すなわち、（b₀b₁b₂b₃）＝（a₀a₁a₂a₃）² ＝（a₀α⁰a₁α¹a₂α²a₂α²a₃α³）² ＝a₀α⁰a₁α²a₂α⁴a₃α⁶ であり、α⁴＝α₀α¹及びα⁶＝α²α³であるから、（b₀b₁b₂b₃）＝a₀α⁰a₁α²a₂（α⁰α¹）a₃（α
²
α³）＝（a₀a₂）α⁰a₂α¹（a₁a₃）α²
a₃α³ ＝（（a₀a₂）a₂（a₁a₃）a₃）である。よつてb₀＝a₀a₂，b₁＝a₂，b₂＝a₁a₃
及びb₃＝a₃が成り立つ。従つてGF（2⁴）２乗回路
４１は第９図のように排他的OR回路５０，５１
を用いて構成される。

一般にGF（2_n）２乗回路も以上のように排他的
OR回路を用いて構成される。

又、GF（2⁴）２乗回路４１は４ビツト・アドレ
ス入力／４ビツト出力（16語×４ビツト）の
ROMを用いても構成できる。すなわち、アドレ
ス入力がA₁＝α^pの時はA₁ ²＝α^2pを出力し、アド
レス入力がA₁＝０の時はA₁ ²＝０を出力するよう
にROMをプログラムしておけば良い。例えばア
ドレス入力がA₁＝α¹¹＝（0111）の時はA₁ ²＝α²²
＝α¹⁵⁺⁷＝α⁷＝（1101）を出力するようにROMを
プログラムしておく。

以上のように第１図の誤り位置検出回路１４は
構成される。次に第１図における誤りパターン解
読回路１５の構成を説明する。誤りパターン解読
回路１５は式(6)、すなわちｅ＝S₀A₀ ²（A₀
A₁）^-1に則して構成できる。

第１０図は誤りパターン解読回路１５のブロツ
ク図を示す。第１０図において回路６０は入力
A₀及びA₁からGF（2⁴）の上でA₀ ²（A₀A₁）^-1を
計算する回路であり、回路６１は４ビツトの排他
的OR回路である。

第１１図は前記回路６０の構成を示す。回路６
０は入力A₀とA₁から出力A₀ ²（A₀A₁）^-1を計算
する回路であるから、第１１図のように入力A₀
とA₁の排他的ORA₀A₁をとる回路７１、前記
排他的ORA₀A₁のGF（2⁴）における逆元（A⁰
A₁）^-1を求める回路７２、A₀の２乗A₀ ²を求める
回路７０及び前記A₀ ²と（A₀A₁）^-1とをGF（2⁴）
において乗算する乗算回路７３とから構成され
る。ここで、２乗回路７０は第９図のGF（2⁴）の
２乗回路と同一構成であり、乗算回路７３は第８
図の乗算回路と同一構成である。A₀A₁の逆元
（A₀A₁）^-1を求める回路７２はランダム・ロジ
ツク又は2⁴語×４ビツトのROMで構成されるが、
ランダム・ロジツクを用いると回路量が多くなる
のでROMを用いるのが望ましい。ＲＭを用い
る場合にはアドレス入力がA₀A₁＝α^pの時は
（A₀A₁）^-1＝α^-p＝α^15-Pを出力するようにROM
をプログラムしておく。例えばアドレス入力が
A₀A₁＝α⁶＝（0011）の時は（A⁰A₁）^-1＝α^15-6
＝α⁹＝（0101）が出力される。又、アドレス入力
がA₀A₁＝０＝（0000）の時は（A⁰A₁）^-1＝０
＝（0000）を出力するようにROMをプログラム
しておく。A₀ ²（A⁰A₁）^-1を求める回路６０は以
上のように構成されるが、他の方法でも構成でき
る。回路６０の入力A₀とA₁はいづれも４ビツト
であり、また出力A₀ ²（A⁰A₁）^-1も４ビツトであ
るから、回路６０は８ビツト・アドレス入力／４
ビツト出力（2⁸語×４ビツト）のＲM1個で実
現できる。すなわち、A₀をROMアドレスの上位
４ビツトに入力し、A₁を下位４ビツトに入力し、
対応するアドレス・ロケーシヨンにA₀ ²（A₀
A₁）^-1を格納しておけば良い。

第１２図はこのROMのアドレス入力と出力の
対応を示す図である。図のようにようにアドレス
入力A₀又はA₁が０の時、又はA₀＝A₁の時は０を
出力するようにROMをプログラムしておく。こ
れ以外の場合、すなわちA₀≠０からA₁≠０かつ
A₀≠A₁の時は、アドレス入力A₀＝α^p，A₁＝α^q
（ｐ≠ｑ）に対応してA₀ ²（A⁰A₁）^-1＝α^2p（α^p
α^q）^-1を出力するようにROMをプログラムしてお
く。例えば、アドレス入力がA₀＝α⁸＝（1010），
A₁＝α¹¹＝（0111）の時はA₀ ²（A⁰A₁）^-1＝α¹⁶（α⁸
α¹¹）＝α^-6＝α⁹であるからA₀ ²（A⁰A₁）^-1＝α⁹
＝（0101）を出力する。以上のように第１図の誤
りパターン検出回路１５は構成される。

以上の説明から分るように本発明の２重バイト
誤り訂正回路は、比較的少ない回路量で、かつ誤
りロケーシヨン多項式を立てずに直接的に２重バ
イト誤りを訂正できるので本発明の目的を十分に
達成できる。

【図面の簡単な説明】

第１図は本発明による２重バイト誤り訂正回路
の一実施例を示すブロツク図、第２図はガロワ体
GF（2⁴）の要素αⁱとバイナリ・ベクトルとの対応
を示す図、第３図はα¹乗算回路のブロツク図、第
４図はα²乗算回路のブロツク図、第５図はα³乗算
回路のブロツク図、第６図は誤り位置検出回路の
ブロツク図、第７図は前記誤り位置検出回路に使
用されるGF（2⁴）の上での乗算回路を読出し専用
メモリを用いて実施する場合のメモリのアドレス
と出力の対応を示す図、第８図はGF（2⁴）の上で
の乗算回路の構成を示すブロツク図、第９図は
GF（2⁴）の上での２乗回路の構成を示すブロツク
図、第１０図は誤りパターン解読回路のブロツク
図、第１１図は入力A₀とA₁からGF（2⁴）の上で
A₀ ²（A⁰A₁）^-1を計算する回路の構成を示すブロ
ツク図、第１２図は入力A₀とA₁からGF（2⁴）の
上でA₀ ²（A⁰A₁）^-1を計算する回路を読出し専用
メモリを用いて実施する場合のメモリのアドレス
と出力の対応を出す図である。図において１，２，３，４はシンドローム・レ
ジスタ、５，６，７，８，９，１０，１１，１
２，３０，４２，５０，５１，５９，６１，７１
は排他的OR回路、２０，２１，２２はα¹，α²，
α³乗算回路をそれぞれ示す。１３はバツフア・メ
モリ、１４は誤り位置検出回路、１５は誤りパタ
ーン解読回路、１６はANDゲート回路、４０は
GF（2⁴）の上での乗算回路、４１はGF（2⁴）の上
での２乗回路、４３はNOR回路をそれぞれ示す。
５２，５３，５４はα¹乗算回路、５５，５６，５
７，５８はANDゲート回路、６０はGF（2⁴）の
上でA₀ ²（A⁰A₁）^-1を計算する回路、７０はGF
（2⁴）の上での２乗回路、７２はGF（2⁴）の上で
の逆元回路、７３はGF（2⁴）の上での乗算回路を
それぞれ示す。

Claims

【特許請求の範囲】１任意の整数ｍで定義されるガロワ体GF（2^m）
の原始元αを用いて構成される２重バイト誤り訂
正符号のパリテイ検査行列 111………１………１ 1α¹α²………αⁱ………α^2m-2 1α²α⁴………α²ⁱ………α^2(2m-2) 1α³α⁶………α³ⁱ………α^3(2m-2) に従つてデータを符号化復号化するシステムにお
ける２重バイト誤り訂正回路において、前記符号
化データを受信し、受信データ・バイトから前記
検査行列の第１行，２行，３行及び４行に対応し
てシンドロームS₀，S₁，S₂及びS₃を生成するシン
ドローム生成回路と、前記シンドロームの間の排
他的ORであるS₀○＋S₁，S₁S₂及びS₂S₃をとる
回路と、前記排他的ORであるS₀S₁，S₁S₂，
S₂S₃に関して（S₀S₁）・（S₂S₃）（S₁
S₂）²＝０を検出し誤りバイトの位置と誤りパター
ンを求める論理回路とから成る２重バイト誤り訂
正回路。