JPH077920B2

JPH077920B2 - 互除演算方式

Info

Publication number: JPH077920B2
Application number: JP61304560A
Authority: JP
Inventors: 佳之岡田
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1986-12-19
Filing date: 1986-12-19
Publication date: 1995-01-30
Anticipated expiration: 2010-01-30
Also published as: JPS63156430A

Description

【発明の詳細な説明】〔概要〕本発明はデータの誤り訂正符号の復号化をする際等に互
除演算をする場合に項毎に係数データを格納する桁移動
可能な係数格納手段を設けるとともに演算結果の順次帰
還を繰り返すことにより小規模の回路構成により誤り位
置多項式等の剰余多項式または商多項式を導出すること
ができる。

〔産業上の利用分野〕

本発明は光ディスク等の大容量記憶装置の誤り訂正符号
として用いられる多重誤り訂正リード・ソロモン符号の
復号処理等において使用するEuclidの互除法による互除
演算を行う方式に関する。

〔技術の背景〕

電子計算器のメモリ等を介してデータを伝送する際の伝
送により生じる伝送誤りに対する対策として誤り訂正符
号が伝送するデータに付加される。伝えたい記号ｋ個を
情報記号といい、付加する余分の符号ｊ個の検査記号と
いい、情報記号ｋ個と検査記号ｊ個を合計したｎ＝ｋ＋
ｊ個の記号列を符号語といい、このｎの値を符号長とい
う。送信側で検査符号を付加する操作を符号化といい、
受信語の誤りを検出して正しい情報記号列を復元する操
作を複合化という。ここでは、検査記号としてBCH符号
等の誤り訂正符号を使用する。BCH符号は一般ガロア体G
F（ｑ）上の非２元符号に容易に拡張できるものであ
る。GF（qm）の原始元をαとするとα，α²,…，α²tを
根とする最小次数の多項式の多項式を生成多項式とすれ
ば、符号長ｎ＝qm−1,情報記号数ｋ≧qm−１−2mt、検
査記号数ｎ−ｋ≦2mt、最小距離dmin≧2t＋１である。
非２元符号の中で特に重要なものはRS符号（リード・ソ
ロモン符号）であり、ｍ＝１の非２元BCH符号である。R
S符号は同一の最小距離をもつ線形符号の中で検査記号
数が最小となる優れた符号である。そのため、2m元の符
号はその各記号をGF（２）上のｍ次元ベクトルで表現す
ることにより２元符号として用いられ、これにより、ｔ
重バイト誤り訂正符号が構成できることになる。

さて、ｔ重誤り訂正符号の復号化において使用する誤り
位置多項式σ（ｘ）、誤り評価多項式ω（ｘ）の導出は
次式よりEuclidの互除法を用いて行う。

Ｃ（ｘ）・x²t＋σ（ｘ）ｓ（ｘ）＝ω（ｘ）（１） degω（ｘ）＜degσ（ｘ）≦ｔ（２）ここでdegは多項式の次数を表し、Ｃ（ｘ）は任意の多
項式であり、Ｓ（ｘ）はシンドローム多項式であって、
符号長ｎのRS符号｛an_-1,an_-2,…,a₀｝に対するｔ重誤
り訂正の各シンドローム多項式は、シンドロームSi（ｉ
＝1,2,2t−１） Si＝an_-1（αｉ）n^-1＋an_-2（αｉ）n^-2＋a₁（αｉ）^１
＋a₀（３）を用いてで表される。

すなわち、既知の多項式x²t,S（ｆ）の最大公約多項式
（GCD）を求めるEuclid互除法の過程から（２）式を満
足する互いに素なσ（ｘ），ω（ｘ）を導出することが
できる。その際、（１）式の形から明らかなようにσ
（ｘ）はＣ（ｘ）・x²tをＳ（ｘ）を除する場合の商多
項式として、ω（ｘ）は剰余多項式として得られること
になる。本発明はこのようなEuclid互除法による互除演
算を行う場合に使用する互除演算方式を提供するもので
ある。

〔従来の技術〕

従来、以上述べた互除演算を実現する回路として第４図
乃至第６図に示すものがあった。

第４図には１セル（１回の演算）当りの回路の構成を示
し、第６図にはｔ重バイト訂正の場合のRS符号の複合化
に際してのブロック回路構成（2t個のセル）を示す。

本例では各セルは第４図に示すように、Ri（ｘ）,Qi
（ｘ）を互除演算して剰余多項式に相当するRi
₊₁（ｘ）,Qi₊₁（ｘ）を得る部分90と、λｉ（ｘ），μ
ｉ（ｘ）について演算して商多項式に相当する多項式を
得る部分91及びRi（ｘ）Qi（ｘ），についての次数dRi,
dQiを計測する部分92並びにこれらの部分の制御を行う
σ（ｘ），ω（ｘ）導出制御部79とから主に構成されて
いる。

Ri（ｘ）,Qi（ｘ）を互除演算して剰余多項式に相当す
るRi₊₁（ｘ）,Qi₊₁（ｘ）を得る部分90においてはガロ
ア体GF（2m）の積回路65,66及びGF（2m）の和回路69、
遅延回路73,81、マルチプレクサ54,55,71,75、レジスタ
60,61,77,78から構成されている。一方、λｉ（ｘ），
μｉ（ｘ）について演算して商多項式に相当する多項式
λi₊₁（ｘ），μi₊₁（ｘ）を得る部分91においては、GF
（2m）の積回路67,68及びGF（2m）の和回路70、遅延回
路74,82、マルチプレクサ56,57,72,76、レジスタ79,80
から構成されている。また、Ri（ｘ）,Qi（ｘ），につ
いての次数dRi,dQiを計測する部分92はコンパレータ51,
52,53、ダウンカウンタ62,63及びマルチプレクサ58,59
等から構成されている。

ｔ重誤り訂正の場合には以上述べたセルのうちσ
（ｘ），ω（ｘ）導出部を除いて2t個使用する必要があ
る。尚、第６図にｔ＝３バイト訂正であって、ガロア体
GF（2⁴）上のRS符号の場合の互除演算に直接関係する本
例の主要な部分を抜き出して示している。

次に本例の動作を第７図の流れ図及び表１に基づいて説
明する。

表１にはｔ＝３バイト訂正であってｍ＝４の場合の従来
例に係るσ（ｘ），ω（ｘ）の導出回路の動作過程を示
す。すなわち、GF（2⁴）の原始元をα（原始多項式Ｐ
（ｘ）＝x⁴＋ｘ＋１の元）とし、３重誤り訂正のシンド
ローム多項式をＳ（ｘ）＝α¹x⁵＋α¹⁰x⁴＋α⁷x³＋α²x²＋α⁹x＋α^１とした場合σ（ｘ），ω（ｘ）導出結果を示している。

ステップS120において初期値としてR₀（ｘ）＝（ｘ）
²t,Q₀（ｘ）＝Ｓ（ｘ），λ_０（ｘ）＝0,μ_０（ｘ）＝
1,dR₀＝2t,dQ₀＝2t−１とおいて前記部分90 0,91 0,92
0に送出する。表１においてはR₀（ｘ）＝α¹⁵x⁶,Q
₀（ｘ）＝Ｓ（ｘ）＝α¹x⁵＋α¹⁰x⁴＋α⁷x³＋α²x²＋α
⁹x＋α¹,λ_０（ｘ）＝0,μ_０（ｘ）＝1,dR₀＝6,dQ₀＝5,
と具体的に示されている。

ステップS121において、R₀（ｘ）の次数dR₀（表１では
６）と訂正可能なバイト数ｔ（表１では３）とまたはQ₀
（ｘ）の次数dQ₀（表１では５）とｔとをコンパレータ5
1,52とで比較する。まだdR₀≧ｔまたdQ₀≧ｔであるので
ステップS122に進む。ステップS122ではコンパレータ53
によってdR₀とdQ₀とを比較する。表１の場合にはdR
₀（６）≧dQ₀（５）であるのでQ₀（ｘ）を除数、R
₀（ｘ）を被除数としてステップS123を通ってステップS
125に進む。dR₀＜dQ₀と判断された場合にはステップS12
4に進みマルチプレクサ54〜59を使って、Q₀（ｘ）を被
除数、R₀（ｘ）を除数とするように交換し、λ_０（ｘ）
とμ_０（ｘ）と、及びdR₀とdQ₀とについても役割りを交
換する。

次にR₀（ｘ）とQ₀（ｘ）の最高次の係数、各々α¹⁵α^１
をレジスタ60,61に、またdR₀＝6,dQ₀＝５をダウンカウ
ンタ62,63に保持する。こうして、除数及び被除数が定
まった段階でステップS125に進みゼロ検知手段64によっ
てq₀（多項式Q₀（ｘ）の最高次の係数α^１）が０か否か
が判断される。

ステップS125においてq₀≠０であるのでステップS126に
進み、当該ステップにおいて２組の積回路65,66,67,68
と１組の和回路69,70を使って除算が行われる。当該除
算により得られた剰余多項式R₁（ｘ）、商多項式λ
_１（ｘ）はマルチプレクサ71,72を介してレジスタ77,79
に保持する。この段階は表１では＃１の段階に相当し、
R₁（ｘ）＝q₀R₀（ｘ）−r₀Q₀（ｘ）（r₀:多項式R
₀（ｘ）の最高次の係数、q₀:Q₀（ｘ）の最高次の係数）
＝α¹⁰x⁵＋α⁷x⁴＋α²x³＋α⁹x²＋α¹x,λ_１（ｘ）＝q₀
λ_０（ｘ）−r₀μ_０（ｘ）＝α¹⁵x、その際ダウンカウ
ンタ62のdR₀を−１ダウンカウントしてdR₁＝dR₀−１が
得られる。またQ₀（ｘ），μ_０（ｘ）は遅延回路73,7
4、マルチプレクサ75,76を介してレジスタ78,80にその
まま保持され各々Q₁（ｘ），μ_１（ｘ）としてR
₁（ｘ），λ_１（ｘ）とともに第４図では90₁,91₁,921の
段階、第５図及び表１では＃２の段階へ進み、以上述べ
たのと同様の手順を繰り返す。

一方、ステップS122でdR＜dQと判断された場合にはステ
ップS124に進みマルチプレクサ54〜59を使って、Ｑ
（ｘ）を被除数、Ｒ（ｘ）を除数とするように交換し、
λ（ｘ）とμ（ｘ）と、及びdRとdQとについても役割り
を交換してステップS125に進む。表１の場合には＃2,＃
４のステップS122でdR₁＜dQ₁,dR₃＜dQ₃と判断されステ
ップS127において除数と被除数とが交換されている。

またステップS125においてｑ＝０と判断された場合には
ステップS127に進み除算をせずに次数dQを１だけ減らし
て再びステップS121に戻り同様の手順を繰り返す。

こうして以上の手順を繰り返すことによりステップS121
において、dR＜ｔまたはdQ＜ｔと判断された場合にはス
テップS128に進みdQ＜ｔの場合にはステップS130におい
てσ（ｘ）＝μ（ｘ），ω（ｘ）＝Ｑ（ｘ）として出力
する。またステップS128でdR＜ｔと判断された場合には
ステップS129においてσ（ｘ），ω（ｘ）＝Ｒ（ｘ）と
して出力する。表１の場合には＃６（ｔ＝３）の段階で
乗余多項式からω（ｘ）が得られ、商多項式からσ
（ｘ）を得ることができる。

〔発明が解決しようとする問題点〕

ところで、従来例に係る誤り位置多項式を導出する場合
に使用する互除演算方式にあっては、第８図に例えばガ
ロア体GF（2⁸）上の原始多項式Ｐ（ｘ）＝x⁸＋x⁴＋x³＋
x²＋１の剰余を演算する積回路（AND回路64個EXOR回路7
7個）に示すように各セル毎に回路規模の大きいGF（2
m）積回路を４個使用することが必要であり、更にｔ重
誤り訂正では４×2t個（例えば８バイト訂正の場合64
個）のGF（2m）積回路が必要とされる。従って回路規模
が非常に大きくなる。また、各セル毎にdR,dQ,tの比較
機能を有するが、これらは最高次数の多項式の係数が入
力した場合のみ動作してマルチプレクサ54〜59の条件を
決めるだけで、後は動作せず回路規模の大きさに比べて
効率的でない。更に、実際のデータの誤りのバイト数が
ｔ−１以下の場合、不必要な動作をするセルが生じると
いう問題点を有していた。

そこで本発明は以上の問題点を解決するためになされた
ものであり、大きな回路規模を必要とせず、しかも効率
の良い誤り位置多項式導出方式を提供するためになされ
たものである。

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

以上の問題点を解決するため本発明は第１図に示すよう
に、多項式Ａ（ｘ）及びＢ（ｘ）についての係数データ
を項毎に桁移動可能に各々降べき順に格納する係数格納
手段1,2と、多項式Ａ（ｘ）及びＢ（ｘ）の次数dA
（ｘ）,dB（ｘ）を計測する次数計測手段３と、当該係
数格納手段1,2が各々格納している前記係数データのう
ち最高次数項の係数データを各々保持する係数保持手段
4,5と、係数格納手段1,2に格納されている係数データと
係数保持手段4,5に保持されている係数データとについ
て順次各々積をとる積回路6,7と、積回路６と積回路７
との出力結果同士を順次加算する和回路と、和回路８の
出力結果と係数格納手段1,2に格納されている係数デー
タとのどちらか一方の選択を前記次数に基づいて行ない
各々多項式Ａ（ｘ）またはＢ（ｘ）として係数格納手段
1,2へ帰還させまたは出力させる出力選択手段9,10とを
少なくとも有するものである。

〔作用〕

本発明は第１図に示すように、例えば誤り位置多項式を
導出する際には、技術の背景で述べたようにＡ（ｘ）,B
（ｘ）としてx²t及びシンドローム多項式ｓ（ｘ）を使
用し、当該多項式Ａ（ｘ）,B（ｘ）の係数データを係数
格納手段1,2に各次数の項毎に順次格納する。又各多項
式Ａ（ｘ）,B（ｘ）の次数dA（ｘ）,dB（ｘ）は次数計
測手段４によって順次計測される。

もし、次数dA（ｘ）≦dB（ｘ）であることを次数計測手
段３が計測した場合にはＡ（ｘ）を除数とし、Ｂ（ｘ）
を被除数として除算を行うことになる。すなわち、積回
路６において係数保持手段５に保持された多項式Ｂ
（ｘ）の最高次数の係数データと係数格納手段１に格納
されている多項式Ａ（ｘ）の係数データとの積を順次と
って和回路８に和回路８に送出する。一方、積回路７に
おいても積回路６と同様に係数保持手段４に保持されて
いる多項式Ａ（ｘ）の最高次数の係数データと係数格納
手段２に格納されている多項式Ｂ（ｘ）の係数データと
の積がとられ和回路８に順次同期して送出される。

和回路８では積回路６と積回路７との出力結果が順次加
算される。すると出力選択手段９は次数dA（ｘ）≦dB
（ｘ）である場合には係数格納手段１に格納されている
多項式Ａ（ｘ）についての係数データを順次選択して帰
還させ再び係数格納手段１へ格納させる。一方、出力選
択手段10は和回路８の出力結果を順次選択して多項式Ｂ
（ｘ）として帰還させ、係数格納手段２へ順次初期の係
数データと入れ換わりながら格納させる。

こうして、次数計測手段３がdA（ｘ）≦dB（ｘ）である
ことを計測している限りは以上の手順を繰り返し、次数
計測手段３が逆にdB（ｘ）＜dA（ｘ）であることを計測
した場合には出力選択手段９は前とは逆に和回路８の出
力結果を選択して復帰させ、出力選択手段10は係数格納
手段２に格納されている多項式Ｂ（ｘ）についての係数
データを帰還させることになる。

尚、以上の手順を繰り返すことにより次数dA（ｘ）,dB
（ｘ）が所定次数より小さくなったことを計測した場
合、例えばｔ重誤り訂正符号の復号化処理における誤り
位置多項式の導出の場合にはdA（ｘ）,dB（ｘ）≦ｔに
なった場合には技術の背景で述べたように第（２）式を
満たしているので以上の処理を終了させ処理結果である
Ａ（ｘ）,B（ｘ）を剰余多項式または商多項式として出
力する。

〔実施例〕

次に本発明の実施例を説明する。

第２図に本実施例に係るブロック図を示す。

本実施例はｔ重誤り位置多項式を導出するための互除演
算方式であり、Ａ（ｘ）,B（ｘ）として本実施例では実
施態様項に述べたようにＡ（ｘ）＝x³t⁺¹,B（ｘ）＝Ｓ
（ｘ）・xt⁺¹＋１としてσ（ｘ），ω（ｘ）を１つの多
項式として導出するようにする。

Ａ（ｘ）,B（ｘ）の係数を次数毎に桁移動可能に各々格
納する係数格納手段1,2としてのパイプライン・レジス
タ11,12と、Ａ（ｘ）,B（ｘ）の次数を計測する次数計
測手段３と、Ａ（ｘ）,B（ｘ）の最高次数の係数を各々
保持する係数保持手段4,5としてのレジスタ14,15と、多
項式Ａ（ｘ）,B（ｘ）の最高次数の係数が０か否かを検
知するゼロ検知手段22,23と、積回路６としてのGF（2
m）上の積回路16と、積回路７としてのGF（2m）上の積
回路17と、和回路８としてのGF（2m）上の和回路18と、
出力選択手段9,10としてのマルチプレクサ19,20と、前
記次数に基づいてマルチプレクサ19,20のどちらか一方
の出力結果を出力するマルチプレクサ26と、マルチプレ
クサ19の出力または多項式Ａ（ｘ）の係数データのどち
らか一方を選択するマルチプレクサ27と、マルチプレク
サ20の出力または多項式Ｂ（ｘ）の係数データのどちら
か一方を選択するマルチプレクサ28と、以上の動作御す
るσ（ｘ），ω（ｘ）導出制御手段30とから構成されて
いる。

係数格納手段1,2としてのパイプライン・レジスタ11,12
はＡ（ｘ）,B（ｘ）の次数から明らかなように、最大項
数は3t＋１であるから3t＋１個の係数を降べきの順に格
納することができるように3t＋１個のレジスタを各々有
している。例えば３バイト訂正の場合にはｔ＝３である
からパイプライン・レジスタの数は10個となる。

次数計測手段３はＡ（ｘ）,B（ｘ）の次数dA（ｘ）,dB
（ｘ）を計測するものであり、マルチプレクサ35,36
と、ダウンカウンタ37,38と、比較器39,40とから構成さ
れている。

次に本実施例の動作について第２図、第３図及び表２に
基づいて説明する。

本実施例は第３図の流れ図に示すように、ステップS1に
おいて多項式Ａ（ｘ）,B（ｘ）として各々x³t⁺¹,S
（ｘ）・xt⁺¹＋１、またＡ（ｘ）,B（ｘ）の次数として
dA（ｘ）＝2t,dB（ｘ）＝2t−１（後述するようにｔ＋
１は単に桁を移動させるために加えたものなので除いて
考える）を初期値として設定する。表２にはより具体的
にｔ＝３バイト訂正の場合を示しているからＡ（ｘ）＝
x¹⁰,B（ｘ）＝Ｓ（ｘ）・x⁴＋１となる。また表２の場
合にはシンドローム多項式は具体的にＳ（ｘ）＝α¹x⁵
＋α¹⁰x⁴＋α⁷x³＋α²x²＋α^９＋α^１としている。この
ように多項式Ａ（ｘ）,B（ｘ）を設定することにより、
従来のようにλ（ｘ）とμ（ｘ）とを別々の多項式とし
て演算処理するのではなく、Ａ（ｘ）,B（ｘ）の多項式
の中に含めて演算処理をすることができる。そのため、
λ（ｘ）とμ（ｘ）との初期値である0,1をＡ（ｘ）,B
（ｘ）の中に加えるとともに、本来のＡ（ｘ）,B（ｘ）
を各々xt⁺¹倍することによって本来のＡ（ｘ）,B（ｘ）
とλ（ｘ）とμ（ｘ）とが混ざり合わないようにした。

ここで、本来のＡ（ｘ）,B（ｘ）は互除演算によって得
られる余剰多項式に相当するもので、これによりω
（ｘ）が得られる。一方、λ（ｘ）とμ（ｘ）とは商多
項式に相当するものであり、これにより、σ（ｘ）を得
ることができる。

表２の＃１の段階においては、これらの多項式の係数デ
ータは各々マルチプレクサ27,28により選択されて、係
数格納手段1,2としてのパイプライン・レジスタ11,12に
降べきの順に格納される。

当該係数格納手段1,2に格納された係数データのうち、
最終段のパイプライン・レジスタに格納されている最高
次数の係数、すなわち、Ａ（ｘ）についてはａ（表２に
おいてはα¹⁵＝１）、Ｂ（ｘ）においてはｂ（表２にお
いてはα^１）を係数保持手段4,5としてのレジスタ14,15
に各々保持される。

ステップS2において、次数計測手段３のマルチプレクサ
35,36はＡ（ｘ）,B（ｘ）の初期値としての各次数dA
（ｘ）,dB（ｘ）を選択し（表２の場合にはdA（ｘ）＝
6,dB（ｘ）＝５）、ダウン・カウンタ37,38に蓄えら
れ、コンパレータ40によってｔ（表２の場合は３）とdA
（ｘ）とが比較される。初期値ではdA（ｘ）＝2t（表２
では６）であるからdA（ｘ）＞ｔであることが計測され
るので、ステップS3に進む。

ステップS3ではゼロ検知手段22によりＡ（ｘ）の最高次
数の係数ａが０であるか否かが検知される。Ａ（ｘ）が
初期値の場合には０でないのでステップS4に進みＢ
（ｘ）の最高次数の係数ｂが０であるか否かがゼロ検知
手段23により検知される。初期値の場合はＢ（ｘ）の最
高次数の係数dBは０でないのでステップS5に進む。

ステップS5においてはコンパレータ39によりdA（ｘ）＜
dB（ｘ）であるか否かが計測される。初期値の場合には
dA（ｘ）,dB（ｘ）は各々2t,2t−１（表２の場合には各
々6,5）であるのでステップS6でＡ（ｘ）,B（ｘ）につ
いて交換が行われることなく、ステップS8に進みＡ
（ｘ）が被除数,B（ｘ）が除数として除算が行われ、そ
の結果Ａ（ｘ）＝bA（ｘ）−aB（ｘ）（表２では,b＝α
_１であり、適当に桁数を移動させて）が得られる。すな
わち、表２では、この式はＡ（ｘ）＝α^１×α¹⁵x¹⁰−
α¹⁵×（α¹x⁹＋α¹⁰x⁸＋α⁷x⁷＋α²x⁶＋α⁹x⁵＋α¹x⁴
＋α¹⁵）×ｘである。この除算の結果Ａ（ｘ）の次数dA
（ｘ）は１減少することになり、表２の場合では＃１の
２段目に記載されているようにＡ（ｘ）＝α¹⁰x⁹＋α⁷x
⁸＋α²x⁷＋α⁹x⁶＋α¹x⁵＋α¹⁵となり、dA（ｘ）＝５と
なる。この場合、次数計測手段３はマルチプレクサ35に
より選択された次数dA（ｘ）＝2tをダウン・カウンタ37
により次数dA（ｘ）を１だけ減少させてdA（ｘ）＝2t−
１とし、またパイプライン・レジスタ11に格納されてい
る多項式Ａ（ｘ）の係数を１桁ずつ桁移動させる。表２
の場合には３段目に記載されているように１桁移動させ
る。尚、Ｂ（ｘ）については変化しない。

こうして得られた（Ａ（ｘ）＝α¹⁰x⁹＋α⁷x⁸＋α²x⁷＋
α⁹x⁶＋α¹x⁵＋α¹⁵x,B（ｘ）＝α¹x⁹＋α¹⁰x⁸＋α⁷x⁷
＋α²x⁶＋α⁹x⁵＋α¹x⁴＋α¹⁵は各々出力選択手段9,10
としてのマルチプレクサ19,20によリステップS2に帰還
される。

こうして、＃２の段階においてはdA（ｘ）＝dB（ｘ）＝
５であるので、＃１の場合と同様にＡ（ｘ）を被除数と
し、Ｂ（ｘ）は除数とし、ａ＝α¹⁰,b＝α^１としてＡ
（ｘ）＝bA（ｘ）−aB（ｘ）を演算して除算を行うこと
になる。この結果表２では、Ａ（ｘ）＝α^１×（α¹⁰x⁹
＋α⁷x⁸＋α²x⁷＋α⁹x⁶＋α¹x⁵＋α¹⁵x）−α¹⁰×（α¹
x⁹＋α¹⁰x⁸＋α⁷x⁷＋α²x⁶＋α⁹x⁵＋α¹x⁴＋α¹⁵）＝
（α¹¹＋α¹¹）X⁹＋（α^８＋α²⁰）x⁸＋（α^３＋α¹⁷）
x⁷＋（α¹⁰＋α¹²）x⁶＋（α^２＋α¹⁹）x⁵＋α¹¹x⁴＋α
¹⁶x＋α²⁵が得られる。その際、ガロア体上では減算は
加算と同一視されることを考慮し、またα¹⁵＝1,原始多
項式α^４＋α＋１＝０を用いると、第１項は消え、第２
項はα^８＋α²⁰＝α^８＋α¹⁵⁺⁵＝α^８＋α^５＝α^４（α
^４＋α）＝α^４となる。以下同様に計算すると、Ａ
（ｘ）＝α⁴x⁸＋α⁶x⁷＋α³x⁶＋α¹⁰x⁵α¹¹x⁴＋α¹x＋
α¹⁰が得られ、Ｂ（ｘ）は前と同様にＢ（ｘ）＝α¹x⁹
＋α¹⁰x⁸＋α⁷x⁷＋α²x⁶＋α⁹x⁵＋α¹x⁴＋α¹⁵のままで
ある。

このようにして＃３に進み、以上の手順が繰り返される
ことになる。

もし、ステップS2において次数計測手段３のコンパレー
タ40により、dA（ｘ）＜ｔであると計測された場合には
ステップS9に進みＡ（ｘ）＝ω（ｘ）xt＋σ（ｘ）がマ
ルチプレクサ26により選択されて出力され、目的とする
誤り位置多項式ω（ｘ），σ（ｘ）が得られる。

例えば表２においては＃６で２段目に示すようにＡ
（ｘ）の次数dA（ｘ）＝２はｔ＝３よりも小さくなり除
算はここで終了し、最下段にω（ｘ），σ（ｘ）として
各々ω（ｘ）＝α²x²＋α²x＋α¹¹,σ（ｘ）＝α⁷x³＋
α³x²＋α⁹x＋α¹⁰が得られる。

またステップS3においてゼロ検知手段13によりａ＝０と
検知された場合にはステップS11に進み次数計測手段５
のダウン・カウンタ37はＡ（ｘ）の次数dA（ｘ）から１
を減少させてdA（ｘ）＝dA（ｘ）−１として直ちにステ
ップS2に進む。

さらに、ステップS4においてゼロ検知手段14がＢ（ｘ）
の最高次数の係数ｂが０であることを検知した場合には
ステップS10に進み次数計測手段５のダウン・カウンタ3
8はＢ（ｘ）の次数dB（ｘ）から１減少させてdB（ｘ）
＝dB（ｘ）−１として直ちにステップS2に進む。

尚、ステップS5においてdA（ｘ）＜dB（ｘ）と計測され
た場合にはステップS7に進みＡ（ｘ）とＢ（ｘ）との除
数、被除数の役割及びdA（ｘ）,dB（ｘ）を交換し、ス
テップS8に進み除算が行われる。表２においては＃３及
び＃５において交換がなされている。

こうして、本実施例ではゼロ検知手段を設けているた
め、最高次の係数が０であることを検知した場合には第
３図に示す流れ図においてステップS5以下の手順を行わ
ないので処理手順が簡単化され処理速度が向上すること
になる。特に誤りの訂正能力が向上するとその処理速度
の向上の程度は著しいことになる。

また、本実施例によればＡ（ｘ）,B（ｘ）として剰余多
項式だけではなく商多項式をも１つの多項式としてω
（ｘ），σ（ｘ）を導出するようにしているため回路規
模がその分縮小されることになる。

尚、λ（ｘ）とμ（ｘ）とをＡ（ｘ）,B（ｘ）の中に含
めて以上述べた動作に従って計算することもできるし、
別途回路を設けて計算してもλ（ｘ）とμ（ｘ）とにつ
いても同様に以上の方式を用いて導出することができ
る。

〔発明の効果〕

本発明では誤り位置多項式を導出する際に桁移動の可能
な係数格納手段を使用するとともに順次演算の結果得ら
れた多項式を順次帰還させることにより当該演算を繰り
返して互除演算を行うようにしているため大幅に回路規
模を縮小することができる。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、第２図は実施例に係
るｔ重誤り訂正のω（ｘ），σ（ｘ）の導出回路図、第
３図は実施例に係るｔ重誤り訂正のω（ｘ），σ（ｘ）
の導出アルゴリズム、第４図は従来例に係るｔ重誤りの
訂正のω（ｘ），σ（ｘ）の１セル当りの導出回路図、
第５図は従来例に係るｔ重誤り訂正のω（ｘ），σ
（ｘ）の導出回路図、第６図は従来例に係る表２の３バ
イト誤り訂正のω（ｘ），σ（ｘ）の導出回路図、第７
図は従来例に係るｔ重誤り訂正のω（ｘ），σ（ｘ）の
導出アルゴリズム、第８図はガロア体GF（2⁸）上のＡ
（ｘ）×Ｂ（ｘ）＝Ｙ（ｘ）の積回路図である。 1,2……係数格納手段３……係数計測手段 4,5……係数保持手段 6,7……積回路８……和回路 9,10……出力選択手段

Claims

【特許請求の範囲】

【請求項１】多項式Ａ（ｘ）及びＢ（ｘ）についての係
数データを項毎に桁移動可能に各々降べき順に格納する
係数格納手段（１），（２）と、多項式Ａ（ｘ）及びＢ（ｘ）の次数dA（ｘ）,dB（ｘ）
を計測する次数計測手段（３）と、当該係数格納手段（１），（２）が各々格納している前
記係数データのうち最高次数項の係数データを各々保持
する係数保持手段（４），（５）と、係数格納手段（１），（２）に格納されている係数デー
タと係数保持手段（４），（５）に保持されている係数
データとについて順次各々積をとる積回路（６），
（７）と、積回路（６）と積回路（７）との出力結果同士を順次加
算する和回路（８）と、和回路（８）の出力結果と係数格納手段（１），（２）
に格納されている係数データとのどちらか一方の選択を
前記次数に基づいて行ない各々多項式Ａ（ｘ）またはＢ
（ｘ）として係数格納手段（１），（２）へ帰還させま
たは出力させる出力選択手段（９），（10）とを少なく
とも有することを特徴とする互除演算方式。
【請求項２】前記多項式Ａ（ｘ）またはＢ（ｘ）の最高
次数項の係数が０であるか否かを検知するゼロ検知手段
と、当該検知手段によって当該係数が０であることを検知し
た場合には前記積回路（６），（７）に入力する前に係
数格納手段（１），（２）に格納されている当該多項式
の係数データを１桁分桁移動させる桁移動手段と、積回路（６），（７）に入力する前に当該多項式の次数
を１乗分削減させる次数削減手段とを設けたことを特徴
とする特許請求の範囲第１項記載の互除演算方式。
【請求項３】ｔ重誤り訂正符号を含む符号データから作
成されるシンドローム多項式Ｓ（ｘ）に基づいて復号処
理をする際に、所定の２つの多項式Ａ（ｘ）,B（ｘ）と
して各々x³t⁺¹、Ｓ（ｘ）xt⁺¹＋１を使用して誤り位置
多項式を導出することを特徴とする特許請求の範囲第１
項記載の互除演算方式。