JPS63157525A - 消失位置多項式生成回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、誤り訂正の分野に関し、また、通信路を対称
とする信号処理において、並列°処理を行う技術に関す
る。′ 本発明は、ＢＣＨ符号の符号化復号において、消失誤り
訂正を行う技術に関する。

〔従来技術とその問題点〕

近年、メモリーシステムを始めとする、各種ディジタル
システムの信頼性向上の対策として誤り検出・誤り訂正
符号（以下、単に誤り訂正符号という）の適用が浸透し
てきている。

この誤り訂正符号には、対象とするシステムに處した種
、々の物があるが、最も代表的なものは巡回符号と呼ば
れる線形符号の１クラスである。

これには、ランダム誤り訂正に適したＢＣＨ符号、バー
スト誤り訂正に適したファイヤー符号、更にＢＣＨ符号
の１種であり、バイト誤り訂正に適したＲ　ｅ　ｅ　ｄ
　−Ｓ　ｏ　ｌ　ｏ　ｍ　ｏ　ｎ符号（以下、Ｒ３符号
）等が含まれる。なかでも、ＲＳ符号は、同一の符号長
と訂正能力を持つ線形符号の中で、最も冗長度を低く出
来るという特徴を持つ、実用上非常に重要な符号であり
、衛星通信、磁気ディスク、コンパクトディスク（以下
、ＣＤと呼ぶ）等に広（利用されている。

このＲＳ符号の復号法には種々の物であり、２ないし３
程度の小さな訂正能力に対する復号器の装置化は比較的
容易である。しかし、高信勅性を得る為には、訂正能力
を大きくする必要がある。その場合、装置の規模及び制
御が非常に複雑になり、復号処理に掛かる計算時間も大
きくなると言った問題が生じる。この為、現在ＣＤでは
ＣＩＲＣと呼ばれる一種の２重符号化を用いているが、
より高信頼性または高速性が要求されるシステムでは問
題がある。また、高信頼性を得るために光磁気ディスク
などではＬｏｎｇ　　Ｄｉｓｔａｎｃｅ　Ｃ０ｄｅ　（
以下、Ｉ、ＤＣ）と呼ばれる多重誤り訂正符号が提案さ
れているが、高速性の実現が問題である。衛星通信では
、高信頼性と高速性の２つが要求されているが、装置化
を考えた場合、以上の２つの条件を満足させることは非
常に困難であった。

しかし、近年の半導体技術と進歩によって装置のＶＬＳ
Ｉ化を考えることができるようになった。そのときＶＬ
ＳＩのアーキテクチャの特徴を生かした復号法を考える
ことは重要である。ＶＬＳＩアーキテクチャの特徴とは
内部構造を規則的に構成することによって、大集積化を
実現することである。

また、、Ｒ３符号の復号手順は、次のような４つのステ
ップに分けられる。

ステップ１）　　シンドローム生成 ステップ２）誤り位置多項式と誤り数値多項式の生成 ステップ３）誤り位置と誤りの値の生成ステップ４）誤
り訂正の実行 ステップ２はＲ３符号の復号に於て最も複雑なステップ
であり、そのためのアルゴリズムには、主にピーターソ
ンの方法とバーレカンブ・マツセイの方法及び、ユーク
リッドの互除法がよく知られている。ユークリッドの互
除法に基づく誤り位置多項式と誤り数値多項式の導出は
多項式の拡張ＧＣＤ（最大公約）問題に帰菅できる。多
項式の拡張ＧＣＤ問題はシストリック・アルゴリズムに
よって解（ことが出来る。シストリック・アルゴリズム
はＫ　ｕ　ｎ　ｇらによって提案されたＶＬＳＩ向きア
ルゴリズムであり、そのアーキテクチャは簡単なプロセ
ッシング・エレメント（以下、ＰＥと呼ぶ）のネットワ
ークによって構成され、次のような特徴を持つ。

工）同一処理プロセッサのネットワークをデータが移動
する間に計算が行われる。

■）プロセッサ間のネットワークは一定規則に従って隣
接するもの同士の接続によって構成される。

■）ネットワークのノード（プロセッサ）からノードに
データが渡るのに少な（とも１ユニツトの時間遅れがあ
る。

このアーキテクチャはバイブライン方式の１つであり、
データを規則正しく循環させて並列処理を行う。また並
列に動作するＰＨの数を増やすことにより、処理能力を
増大させることが出来る。

〔問題点を解決するための手段及び作ｍ〕以上の点に鑑
み、本発明はシストリック・アルゴリズムの考え方を応
用し、実際にＩ３　ＣＨ符号の消失誤り訂正器に適用す
るための具体的アルゴリズムを検討し、特に、消失位置
多項式生成回路を同一のプロセッシング・エレメント（
以下ＰＥ）によって実現することを目的としている。

°さらに、同一のＰＥの構成を変化させて、ハード量と
高速性のトレード・オフを実現させる構成を示す。

［実施例］ 本発明の詳細な説明に入る前に誤り訂正の原理につりで
説明する。

１ＵＬｉΔ皿皿 まず、Ｒ３符号の原理について述べる。Ｒ８符号は、同
一の符号長と訂正能力を持つ線形符号の中で、最も冗長
度を低くできるという特徴を持つ、実用上非常に重要な
符号である。

Ｒ３符号は、非二元ＢＣＨ符号（Ｂｏｓｅ−Ｃｈａｖｄ
ｈｕｒｉ−１−１ｏｃｑｕｅｎｇｈｅｎ　　ｃｏｄｅ）
の特別な場合であり、有限体く以下、ＧＦと略す。）　
ＧＦ　（ｑ）の元で構成される。ここでは、ｑはＧＦ　
（ｑ）の元の数である。

このｑを用いると、ＲＳ符号を特徴づける各種パラメー
タが以下のように定義される。

・符　号　長　：　ｎ（−符号中のシンボル数）ｎ≦ｑ
−１（２−１） ・情報シンボル数：　ｋ（−符号中の情報シンボル数）
・検査シンボル数：ｎ−ｋ（−符号中の検査シンボル数
）ｎ−に＝ｄｍｉｎ−１（２−２） ・訂正能力　：　ｔ（−符号中の訂正できるシンポ数）
（［Ｘ］ガウス記号０．Ｘを越えない最大の整数）ここ
ではｄｍｉｎは最小距離（ハミング距離）と呼ばれるも
のである。

征−ユー化 まず、ここで符号語等の多項式表現について説明する。

例えば、符号化したいに個の情報シンボルを１”　（’
ａｎ　　ｉ、、＋＋、　　Ｉｋ−１）　　　　　　　　
（２１０）とする時、これは次のように多項式表現され
る。

１（ｘ）＝ｉｏ＋ｉ、ｘ＋ｉ、ｘ”＋・＝＋ｉ、−，ｘ
’−”＋ｉ、−，ｘ”−’　　　（２−１１）同様に付
加される（ｎ−ｋ）個の検査シンボルＣ＝　（ｃ。＋　
　Ｃ＋　＋　・・・、　Ｃｍ−＊−＋　）　　　　　　
　　（２１２）は、 Ｃ（ｘ）＝　Ｃｏ＋Ｃ＋　ｘ＋ｃ＝ｘ”＋　＋＋　ＣＭ
−に−１”Ｘ”−ト’（２−１３）更に、これらをまと
めた符号語Ｆ Ｆ”　（ｆ６．　　ｆｌ、　　ｆｌ、・・・ｆ、−、）
　　　　　　　　（２−１４）＝ｃ、・・自”’Ｃｎ−
に−１・ｔｏ・Ｌ　＋　１！　＋・・・ｔｍ−＋）　　
　　　　（２１５）は、 Ｆ（ｘ）　＝　ｆｏ＋ｆ　、　ｘ−Ｈ，ｘ”＋　−・−
’　ｆ、−、ｘ’−”＋ｆ、−，ｘ’−’　（２−１６
）と多項式表現される。

次に、Ｒ８符号は最初に述べたように巡回符号の一種で
あるが、巡回符号を特徴づけるものに、符号化／復号の
際に用いられる生成多項式Ｇ　（ｘ）がある。この生成
多項式は、符号の検査シンボル数（ｎ−ｋ）に等しい次
数を持ち、かつ（ｘ’−’　）を割り切るものでなけれ
ばならないが、ＲＳ符号では、次のような式を用いる。

Ｇ（ｘ）＝（ｘ−ａ　）（ｘ−ａ２）−（ｘ−ａｎ−’
）　　　（２−１７）（Ｇ（ｘ）＝（ｘ−ＩＸｘ−ａ）
−（ｘ−ａ”−トつでも可）（２−１８）ここでは、α
は符号が定義される有限体ＣＦ　（ｑ）の原始光である
。

この（ｎ−ｋ）次の生成多項式を用いて（ｎ、　ｋ）Ｒ
Ｓ符号を得るには、以下のような手順をふむ。

ｉ）情報シンボル多項式Ｉ　（ｘ）　（（２−１１）式
）にｘｎｌを乗じる。

１ｉ）Ｉ（ｘ）・Ｘｎ−ｋを生成多項式Ｇ　（ｘ）で割
った剰余多項式をＲ（ｘ）とする。

１ｉｉ）このＲ（ｘ）を検査シンボル多項式Ｃ（ｘ）に
おきかえ、Ｉ　（ｘ）・ｘｎ−ｋに付加したものを符号
語多項式Ｆ　（ｘ）とする。

Ｆ（ｘ）＝Ｉ（ｘ）−ｘｎ−’−Ｃ（ｘ）＝Ｑ（ｘ）・
Ｇ（ｘ）　　（２２０）（２−２０）式を見てもわかる
様に、符号語多項式Ｆ　（ｘ）はそれを生成した生成多
項式〇（ｘ）で割り切る事ができる。ところが、（２−
１７）式の生成多項式は、α、α２．・・・α１という
根を持つから、符号語多項式Ｆ　（ｘ）はこの根を代入
すると、次式が成立する。

Ｆ（ａ’）＝Ｏ（ｉ＝１．２．・・・・、　ｎ−ｋ）　
　（２−２１）この（２−２１）式を行列表現すると次
のようになる（ＦＴはＦの転置行列）。

ここで、左辺の行列Ｈは、検査行列と呼ばれ復号におい
ても重要な意味を持つ。

復ＪＬ法 既に述べたように、Ｉｔｓ符号はＢ　ＣＨ符号の一種で
あるから、一般的なりＣｌ−１符号の復号アルゴリズム
を利用して復号を行う事ができる。但しその場合復号処
理における加算９乗算等のシンボルの取扱いは、そのＲ
３符号が定義される有限体ＣＦ　（ｑ）の上で行われな
ければいけない。

ＧＦ　（２”）　（ｍ　：正整数）上で定義された符号
長ｎ　＝　２”　−１のＲ３符号について考えると、シ
ンボルはｍビット２進数で表わされ、演算はＧＦ（２’
″）上で行われる。また生成多項式には（２−１７）式
を用い、符号の最小距離は簡単の為ｄｍｉｎ＝２ｔ＋１
と置（事にする。

ｇ（ｘ）＝、（ｘ−ａ　Ｘｘ−ａつ・・・（ｘ−ａ”−
”＞　　（２−１７）ただし、αは有限体ＧＦ　（２″
り上の原始光さて、このようなＲＳ符号の復号手順は、
一般的なり　ＣＨ符号の場合と同様、次のような４つの
ステップに分けられる。

ステップ１）　シンドローム計算。

ステップ２）　誤り位置多項式と誤り評価多項式の算出
。

ステップ３）　誤り位置と誤りの値の推定。

ステップ４）　誤り訂正の実行。

ステップ１　シンドローム■ユ まず、 送信された符号語をＦ　：　Ｆ＝（ｆｏ、　Ｉ＋、−−
−ｆｎ−＋）生じた誤りをＥ　　　　：　Ｅ＝（ｃｏ、
　ｅｌ、”’ｅｎ−１）受信された受信語をＲ：　Ｒ＝
（ｒｏ、　ｒｌ、”ｒｎ−１）＝Ｆ＋Ｅ ＝　（ｆ＋）＋ｅｏ、　　ｆ＋＋ｅ＋、　−＝　ｆｎ−
Ｉ＋ｅｎ−１）とすると、受信語の多項式表現Ｒ（ｘ）
は次のようになる。

Ｒ（ｘ）　＝Ｆ　（ｘ）　＋Ｅ　（ｘ）＝　　（ｆｏ＋
ｅｏ）　　＋　　（ｆ＋＋ｅ＋）　　ｘ＋　　＝＋　（
ｆｎ−＋　＋ｅｎ−＋　）　ｘ″−’　　　　（２２３
）ところが、符号多項式Ｆ　（ｘ）に生成多項式Ｇ　（
ｘ）（（２−１７）式）の根ａ’　（ｉ＝１．　・・・
、ｎ−ｋ）を代入すると（Ｆ（α’）　＝Ｏ）が成立す
るから、受信語多項式Ｒ（ｘ）に同様にａ　ｉ　（ｉ＝
１．　・・・・、ｎ−ｋ）を代入すると Ｒ（α’）＝Ｆ（α’）＋Ｅ（α’）＝Ｏ＋Ｅ（α’）
＝Ｅ（αＩ）のように、誤りＥだけで決まる値が求まる
。

これをシンドロームと呼び、改めて Ｓ＝　（ｓｏ、　ｓ＋、　＝　、　Ｓｎ−に−１）　　
　　　（２−２５）ｓｉＲ（α”’）＝Ｅ（α１Ｆ’）
　（ｉ＝　０　、１、−、　ｎ−に−１）　　（２−２
６）と定義する。このシンドロームは誤りに関するすべ
ての情報（誤りの位置と大きさ）を含んでいる。

（シンドロームは誤りがなければ０であるので、誤りの
有無を検出できる。）シンドローム（（２−２５）。

（２−２６）式を行列表現すると次のようになる。

５＝Ｈ−Ｒ”　　（Ｒ”：Ｒの転訝行列）、　　（２−
２８）スーツブ２　誤　１″ＩＹＩＩｆ　　王゛　誤　
、・　タ　エの一ステップ２では、ステップｌの計算結
果のシンドロームを利用して誤り位置多項式と誤り評価
多項式の算出を行う。まず、ここでは誤りＥ＝（ｅ、、
ｅ、・・・ｅｎ−＋）の非零の元の数、すなわち誤りの
個数を１（１≦ｔ）とおく。また、誤りの生じている位
置をｊｕ　（ｕ＝１゜２−１り　（ｊｕ＝ｏ、１−ｎ−
１）とし、位置ｊｕにおける誤りを０１．とする。更に
（２−２）、（２−３）式をｎ−に＝ｄｍｉｎ−］＝２
ｔ　　　　　　、　　　（２−３０）とお（。すると、
（２−２６）式のシンドローム及びシンドローム多項式
は、次のように表わされる。

とおくと、次式が得られる。

Ｓ　　（ｘ）＝　　［Ｓ−（ｘ）コ　ｍａｄ　　ｘ”　
　　　　　（２−３５）さて、ここで誤り位置多項式σ
（ｘ）を次のように定義する。この多項式は、受信語中
の誤り位置ｊｕ（ｕ”　Ｌ２＋”””＋　’　）　（Ｊ
ｕ　＝Ｌ’　＋”””ｎ　１　）に対応するＧＦ　（２
”）の元α月”を根とする多項式である。

ｔｙ　（ｘ）＝（１−（Ｚ”Ｘ）　（１−ａ”ｘ）　・
（１−ａ”ｘ）＝ｎ　（１−（！”Ｘ）Ｕ纏１ 次に、以上述べたσ（ｘ）、５−（ｘ）に対し誤り評価
多項式ω（ｘ）を次のように定義する。

すると、（２−３４）、（２−３５）、（２−３７）式
より、次式が成立する。

σ　（ｘ）−８（ｘ）　　＝　　［ω　（ｘ）コ　ｍｏ
ｄｘ２Ｉ　　　　　　　　　　　　　　　　（２−３８
）従って適当な多項式Ａ　（ｘ）を用いてσ（ｘ）、　
Ｓ　（ｘ）・ω（ｘ）の関係が次のように表わされる。

Ａ　（ｘ）−ｘ”＋　ａ　（ｘ）・Ｓ　（ｘ）　＝（Ｉ
Ｊ　（ｘ）　　　　　　（２−３９）ところで、誤りの
個数ｌはＣＩ！≦ｔ）としているから、ω（ｘ）とσ（
ｘ）は ｄｅｇ　ω（ｘ）　＜　ｄｅｇ　ａ　（ｘ）≦ｔ（２−
４０）を満たす。さらにω（ｘ）とσ（ｘ）は互いに素
（最大公約（ＧＣＤ）多項式が定数）であるから（２−
３９）、（２−４０）式を満たすω（ｘ）とσ（ｘ）は
定係数の違いを除いて一意的に定まる。以上よりω、（
ｘ）とａ　（ｘ）はｘ　２１とＳ　（ｘ）の最大公約（
ＧＣＤ）多項式を求めるユークリッドの互除法の過程で
求め得る。ここで、ユークリッドの互除法を利用した最
大公約（ＧＣＤ）多項式の算出方法について簡単に述べ
る。まず、２つの多項式ＡとＢの最大公約多項式をＧＣ
Ｄ　［Ａ、Ｂ］と表わすことにする。又、このＡとＢに
対し次のような多項式にとｎ １ｄｃｇΔ≧ｄｅｇｎの場合Ｎ＝Δ−［Ａ−１３’］−
１３（２−４１）＋１＝Ｉ）　　　　　　　　　（２−
４２）・ｄｃｇ八≧へｃｇｌ〕の場合λ＝　Ａ　　　　
　　　　（２−４３）Ｌ１＝ｎ−［１−Ａ　’］−Ａ　
　　（２−４４）（［ｘ−ｙ−’］：多項式Ｘを多項式
Ｙで割った商）ヲ定ａ　ｔ　ルト、ＧＣＤ　［Ａ、Ｉｌ
ｌ　トＧｃＤ　［Ａ、１１コは、次式を満たす。

ＧＣＤ　［Ａ、Ｂ］　＝ＧＣＤ　［ＡＪ］　　　　（２
−４５）従って、上述のλとｎとを改めてＡ、　Ｂとお
き、各々の次数ｄｅｇＡ、　ｄｅｇＢの大小関係に応じ
て（２−４１）。

（２−４２）式もしくは（２−４３）、　　（２−４４
）式の変換を行うといった操作を繰返し実行して、Ａと
Ｂのどちらかが零多項式になった時、もう一方の非零多
項式がＡとＢの最大公約多項式として得られる。なお、
多項式ＡとＢの最大公約多項式を求める事は、次のよう
な多項式ＣとＤを求める事と変りない。なお、ｄｅｇは
次数のことである。

ＧＣＤ　［Ａ、１１３］　＝Ｃ−Ａ十Ｄ−ＩＪ　　　　
（２−４６）すると、上記繰り返しステップを実行して
、次数がｉ＝ｄｅｇ八≧ｄｅへＢと表わされる多項式へ
とＢの最大公約多項式を求める過程で、次式を満足する
多項式Ｃ，Ｄ、　　Ｗを求める事ができる。

この様な多項式を求める問題を拡張ＧＣＤ問題と呼ぶ。

従って、誤り位置多項式σ（ｘ）と誤り評価多項式ω（
ｘ）は、（２−４７）式において、多項式ＡをＸ２′１
多項弐〇をＳ　（ｘ）とおいた場合の拡張ＧＣＤ問題を
解く事により求まる。

−ルゴリズム まず前述したように、σ（ｘ）とω（ｘ）の専用アルゴ
リズムは拡張ＧＣＤ問題に帰着できる。すなわち、ｘ２
′を多項式ＡＯ，シンドローム多項式Ｓ　（ｘ）（（２
−３２）式）を多項式Ｂｏとおいた時（ｄｅｇＡｏ＝２
ｔ。

ｄｅｇＢｏ＝２ｔ−１）、ＧＣＤ　［Ａｏ、Ｂｏ］を求
める途中で を満たす多項式り、　　Ｗが求・ま・れば、Ｄが誤り位
置多項式σ（ｘ）、Ｗが誤り評価多項式ω（ｘ）を各々
表わしている。このようなσ（ｘ）とω（ｘ）は、定係
数の違いを除いて一意的に定まることがわかっている。

従って、ＡｏとＢｏに対して次のような　多項式Ａ、　
　Ｂ、　　Ｕ、　Ｖ、　Ｌ、　Ｍを定義し その初期値を Ｕ＝Ｍ＝ｌ　；、Ｌ＝Ｖ＝Ｏ；　　（Ａ＝Ａｏ、Ｂ＝Ｂ
ｏ）とおいて第１５図の繰返しステップを実行していき
、ｄｅｇＡ　（ｄｅｇＢ）　＜ｔとなった時にＡ　（Ｂ
）がω（ｘ）、Ｌ　（Ｍ）がσ（ｘ）として各々求まる
。

なお、第１５図の方法では、多項式Ｂの最高次係数αと
多項式Ａの最高次係数βを各々Ａ、　　Ｈにたがいちが
いに乗する事により、繰返しステップおけるＧＦ上の除
算を省略している。（（２−４１）。

（２−４３）式参照）このようにしても、σ（ｘ）とω
（ｘ）の値に本質的な問題は生じない。

第１５図について説明する。まず、ステップｌにおいて
Ｕ＝Ｍ＝１．　Ｌ＝Ｖ＝Ｏ，Ａ＝Ａｏ、　ｌ３＝Ｉ３゜
とおいて、初期値を設定する。ステップ２においてｄｃ
ｇＡ≧ｄｅｇｌ’ｌの判定を行い、ステップ３において
多項式Ａ、　　Ｉ３の最高次係数β、αを各々Ａ、　Ｉ
３にたがいちがいに乗じ、式（２−４１）、　　（２−
４３）の繰返しステップにおけるＧＦ上の除算を省略し
ている。

ステップ４においてｄｅｇＡ、ｄｅｇＢが所定の次数よ
り小さくなった場合、ステップ５，６に進み、ω（ｘ）
＝Ａ、σ（ｘ）　＝Ｌ、ω（ｘ）　＝Ｂ、σ（ｘ）　＝
Ｍを算出す、る。

なお、第１５図の繰返しステップを実行するには、Ａと
Ｂの次数に応じた３つの実行モードが必要であり、それ
らを以後次のように呼ぶ事にする。

ｉ）　　ｄｅｇＡ、　ｄｅｇＢ≧ｔかつｄｅｇＡ≧ｄｅ
ｇＢ−’ｒｅｄｕｃｅＡ”ｉｉ）ｄｅｇＡ、ｄｅｇＢ≧
ｔかつｄｅｇＡ≧ｄｅｇＢ−・・“ｒｅｄｕｃｅＢ″１
ｉｉ）　ｄｅｇＡ　＜　ｔ　　もしくは　ｄｅｇＢ＜ｔ
　　−”　”ｎｏｐ”ステップ３１ｒ　１♂　曾Ｐ　の
」の　〜ステップ３では、ステップ２で得られた誤り位
置多項式σ（ｘ）と誤り評価多項式ω（ｘ）から、誤り
位置と誤りの値の推定を行う。まず、受信語Ｒ＝　（ｒ
ｏ、　ｘ、−−−、ｒｎ＝’）中のシンボルの位ｆｆ１
ｔ＝ｏ。

ｌ・・・ｎ　−１に応じたＧＦ（２”）の元α−１を誤
り位置多項式σ（ｘ）に逐次代入する。この時、（２−
３６）式よりσ（ａ　”　’　）　＝　Ｏが成立するな
らば、ｉが誤り位置ｊｕに対し、α−１＝α−１ｕが成
立している事がわがる。（ｊ　ｕ　＝　０　、１−ｎ　
−１、ｕ　＝　１　、２−１　、　１≦ｔ）また、その
ようなα１＝α−）“に対する誤り評価多項式ω（ｘ）
の値は次のようになる。

更に、σ′（ｘ）をσ（ｘ）の微分とすると、が成立す
る。従って（２−４８）式と（２−４９）式より誤り位
置ｊｕにおける誤りの値Ｃ１は次式より求められる。

前述したように、復号のステップ３）では、ステップ２
）で得られた誤り位置多項式σ（ｘ）、誤り評価多項式
ω（ｘ）ならびにσ（ｘ）の微分σ′（ｘ）という３つ
の多項式に、そのＲＳ符号が定義されるＣＦ（２”）の
元α−’　（ｊ＝ｎ−１，・２，１．０）を逐次代入し
てその値を求める計算が必要となる。（ここでは受信シ
ンボルが受信語多項式の高次の項から入力される。すな
わちｒｊがｊ＝ｎ−１，・・・、２，１．０の順で入力
されるとする。従って、ステップ３）についての説明で
は、ａ＝　（ｊ＝ｎ−１，・−・、２，１．０）の代入
の順が逆となる事に注意しなければならない。）ここで
、具体的に必要な計算は単に多項式に変数を代入し、そ
の値を求めるだけであるから　（５−１０）式と同様の
アルゴリズムを利用できる。例えば、を次多項弐ｆ　（
ｘ）の計算は次のように展開される。

ｆ　　（ｘ）　　＝　　ｆｔｘ’＋ｆｔ−１ｘ’　−’
＋・・・十ｒ、ｘ−）−ｆ。　　　　　　　　　　　　
　　　　　　（５−１１）＝　Ｉ−・・［（ｆｔｘ＋ｆ
ｔ−１）　ｘ−Ｈｔ−２）　ｘ＋・・・＋ｆ＋ｌ　ｘ＋
ｆｏ　　（５−１２）但し、シンドローム計算では各セ
ルが代入すべきＸをあらかじめ持っており、各セルに係
数を与えてスーツ　４　　Ｗ　　　の！−′− （２−９）式より、誤りの生じている位置ｊｕにおける
受信シンボルｒ。は、本来の符号語のシンボルｆ２と誤
りの大きさｅ２から次のように表わされる。

ｒＪｕ＝　ｒｌｕ　−ｅｌ、、（２５１）従ってステッ
プ４では、ステップ３の実行結果ａ　（α−’）　＝Ｏ
が成立した位置ｉ　（ｉ＝０．１．−ｎ　　１）におい
て、受信シンボルｒ１から を引＜　　（ＧＦ（２”）上）　　ｆ、　＝　ｒ＋　−
ｅｌ　　　　（２−５３）事により、位置ｉにおける誤
り訂正を実行する。

次に上述した誤り訂正の原理を考慮した上で、本発明の
実施例の構成・動作について説明する。

ここでシストリック・アーキテクチャの基本となるプロ
セッシング・エレメント（ＰＥ）を図１のように定める
。

第１図に於て、ｌはＡ、　　ｎ、　Ｃの入力をＳｌ、　
Ｓ２の選択信号によって表１のようにＸ、　　Ｙに出力
するセレクタであり、２，３に示すＯはガロア体上の乗
算器でありＲＯＭによって実現できるが、ゲート回路に
よっても実現できる。また、４に示す■はガロア体上の
加算器でありＥＸＯＲ回路によって実現できる。５から
７はクロックＣＫによってラッチするレジスタである。

ＧＦ　（２’）上のゲート回路によるセレクタ、及び乗
算器、加算器（原始多項式ｐ　（ｘ）　＝ｘ’＋ｘ’＋
ｘ”＋ｘ”＋ｘ＋１の場合）を考えた場合、第２図、第
３図、第４図のように実現でき、ＩＰＨに要する回路規
模、及び処理速度は各々約８００ゲート、及びｌゲート
に要するディレィを５−１０ｎｓとした場合１０−２０
Ｍｈｚ＝８０−１６１０−２Ｏ（１シンボル（８ビツト
）単位で処理を行うため）となる。（ｌゲートにおける
ディレィはＴＴＬレベルとしたが、ＰＨに於ける処理部
であるセレクタ、乗算器、加算器は１箇所に固められて
いるので、ｖＬＳＩ化の際この部分を最適化して高速化
することによって更に処理速度の高速化が図れる。） また、ＩＰＥの構成を第５図のように拡張することによ
って、インターフェース部の少ない接続にすることが゛
出来る。第５図は１のセレクタを５人力４出力のセレク
タとしく出力の組合せは選択信号Ｓ１．。

４によって表２のようにする）、レジスタを５個に増や
したものである。このＰＥに要する回路規模は約１００
０ゲートとなるが、処理速度は変わらない。

このＰＥを用いることによって、全てのＰＥを同じクロ
ックで動作させ、全体のシステムの制御を各ＰＥの選択
信号Ｓ１．．４のみとすることが出来る。

（シンドローム生成部） ステップｌでは受信系列Ｒ（ｒｎ−ＩＩ　ｒｎ−２”・
＋ｒｌ＋ｒ□）からステップ２で必要なシンドローム多
項式％式％ 具体的なシンドローム多項式の係数の計算は、受信系列
Ｒの受信シンボルｒｎ−Ｉ、　ｒｎ−２”’、ｒｌ、　
　ｒｏがシリアルに送られるので、次式のような繰り返
しアルゴリズムで表される。

ｓ、、＋　＝（・（（ｒ、、、＊α’＋ｒｎ、ｚ）＊α
’＋ｒｎ、）＊α’＋・＋ｒ、）＊α１＋ｒ６ 従って、上式は次のように分解される。

Ｚ０＝Ｏ Ｚ＋　＝２１−＋　＊（２’　＋　ｒｎ−＋　　　　　
　　（！”　１．・・−、ｎ）Ｓｂ、＋　＝　Ｚｌｌ 第１図のＰＥを第６図のように用い、第８図のように信
号、を送る。

最初（ｉ＝１）、ｒｎ−１がセレクタ人力Ｂに入力され
る。セレクタのＹ出力はＢ入力を選択し、ｒｎ−１を出
力する。このときＺｌ＝Ｚｏ＊α’　＋　ｒ　ｎ−１を
計算するためにＺｏ＝ＯとなるようにセレクタのＸ出力
はＣを選択し、Ｏを出力する（Ｓｌ、２＝１．Ｏ）。

そのＸ、　　Ｙ出力は各々αＩ、　　１を乗算され、そ
の出力同士を加算することによってＺｌ”ｒｎ−１力に
生成され、次のクロックでレジスタ６に入力される。

また、同じクロックでレジスタ７にはＹ出力ｒ１−１が
入力される。次に（ｉ＝２．・・・＋　ｎ）、セレクタ
のＸ出力をＡ入力が選択されるようにすることによって
前出力Ｚｉ−１がＸから出力されるので（ＳＬ、　２＝
０゜０）、Ｚｉ＝Ｚｉ−１＊ｔｌ’＋　ｒｎ−ｉが計算
され、ｉ＝ｎのときシンドローム多項式の１つの係数５
ｉ−１が生成される。その間レジスタ７からは、ｒｌが
順次出力される。

このＰＥを第７図のように接続して、α１の値を割り付
けることによってシンドローム多項式の各係数が順次生
成される（タイミングは第８図に示す）。

また、シンドローム多項式の各係数を同時に生成させる
には、第１０図のようにＰＥ同士を接続する。この場合
、受信シンボルｒ１の通信距離が各ＰＥによって異なる
ことに注意しなければならない（タイミングは第１１図
に示す）。

また、第５図のＰＥを第１２図のように用い、第１３図
のように接続することによって、シンドローム多項式の
各係数を最後のＰＥから連続して出力することが出来る
。第１３図の回路に第１４図のように信号を入力する。

最初のＩ’Ｅにおいて通常セレクタ出力ＷはＤ入力を選
択しているが、シンドローム５２１−１が生成されたと
き選択信号Ｓ　１、．４　＝１０１０とすることによっ
てＷ　１．：　Ａ入力を出力してレジスタ８にシンドロ
ーム５２１−１を入力し、５（ｘ）から出力させる。次
のＰＥにシンドロームＳ　２１−２が生成されたときＤ
入力から前ＰＥの出力５２Ｌ−１が入力されているので
Ｓ　２Ｌ−２を１クロツクずらすためにへ入力をＺに出
力して（Ｓｌ、、４＝１１１０）、レジスタ９にシンド
ロームＳ　２１−２を取り込む。その出力を次のクロッ
クでＷに出力することによって（Ｓｌ、、４＝ＯＯＩＯ
）レジスタ８にＳ２ト２が入力され、Ｓ　（ｘ）から５
２Ｌ−１の次にＳ　２１−２を出力させることが出来る
。

それ以降のＰＥはシンドロームＳ　ｉ−＋が生成されて
からＳ　（ｘ）に出力させるタイミングが更に１クロツ
クづつずれてい（ので、Ｓｌ、、４＝ＯＯ１０とするタ
イミングを１クロツクづつずらしてい（。これによって
、最後のＰＥのＳ　（ｘ）からシンドローム多項式の係
数５２１−１　、・・・、Ｓｏを連続出力させることが
出来る。

第７図、第１０図、第１３図共に、必要なＰＥの数は２
を個であり、処理速度は１０−２１０−２Ｏ（ｗｏｒｄ
／　ｓ　ｅ　ｃ　）である。

（ＧＣＤ生成部　（誤り位置多項式及び誤り数値多項式
生成））ステップ２の誤り位置多項式σ（ｘ）と誤り数
値多項式ω（ｘ）の導出アルゴリズムは、拡張ＧＣＤ問
題に帰着できる。即ち、ｘ　２　＋を多項式Ａ０、シン
ドローム多・項式Ｓ　（ｘ）を多項式Ｂ０とおいた時（
ｄ　ｅ　ｇ　Ａ　。

＝２ｔ、　ｄｅｇＢｏ＝２ｔ　−１）、ＧＣＤ　［Ａ、
、　Ｂ、］を求める途中で、 ｄｅｇＷ＜ｔ、ｄｅｇＤ≦ｔ Ｃ＊　Ａ、　＋　Ｄ　＊’Ｂｏ　＝　Ｗを満たす多項式
り、Ｗ（Ｄが誤り位置多項式σ（ｘ）、Ｗが誤り数値多
項式ω（ｘ）を表す）を求める問題に帰着される。この
ようなσ（ｘ）とω（ｘ）は、定係数の違いを除いて一
意的に定まることがわかっている。従って、Δ。とＢｏ
に対して次のような多項式Ａ、　　ｎ、　　Ｕ、　　Ｖ
、　　Ｌ、　　Ｍを定義し、Δ＝Ｕ＊Ａｏ十Ｌ＊Ｉ３゜ し＝　Ｖ　＊　Ａ０＋　Ｍ　＊　［ｌＩ＋その初期値を Ｕ＝Ｍ＝１．　　Ｉ、＝Ｖ＝Ｏ，（Ａ＝Ａ、、　　ｌ３
＝Ｂ、）とおいて第１５図の繰り返しステップを実行し
ていき、ｄｃｇＡ（ｄｅｇＩ３）＜ｔとなったときにＡ
　（ｎ）がω（ｘ）、Ｌ　（Ｍ）がσ（ｘ）として各々
求まる。

なお第１５図の方法では多項式Ｂの最高次係数αと多項
式への最高次係数βをＡ、　　Ｂに各々互い違いに乗す
ることにより、繰り返しステップにおけるＧＦ上の除算
を省略している。このようにしても、σ（ｘ）、とω（
ｘ）の値に本質的な問題は生じない。

しかし、ここで問題となるのは処理の途中で多項式の長
さが変化することである。例えば、１回の処理に注目し
た場合ｄｅｇＡとｄｅｇＢの差の大きさによって、生成
されるＡまたはＢの多項式の次数、即ち多項式の長さが
変化する。このような入力多項式の長さの変化にＰＥの
機能を対応させようとすると、各ＰＥに非常に複雑な機
能が要求される。またその場合、個々のＰＥの計算量が
不均等になり効率が悪い。この問題を解決するために、
Ｋ　ｕ　ｎ　ｇらの拡張Ｇ　ＣＤ　ＩＬ’ｌ　ｉを解く
シストリック・アルゴリズムでは、各ＰＥへの多項式の
入力を個々の係数データとＡ、　　Ｈの次数差に分けて
いるが、ここでは各ＰＥへの入力を多項式の係数データ
のみとし、次数差は別の回路によって次の３つのモード
として生成°し、ＰＥのセレクタ選択信号として用いる
。

１）　　ｒｅｄｕｃｅＡ；　　＝　ｄｅｇＡ、　ｄｅｇ
Ｂ≧ｔかツｄｅｇＡ≧ｄｅｇＢ２）　　ｒｅｄｕｃｅＢ
；　　＝　ｄｅｇＡ、ｄｅｇＢ≧ｔかつｄｅｇＡ≧ｄｅ
ｇＢ３）　　ｎｏｐ　　　；　　＝　ｄｅｇＡ＜ｔまた
はｄｅｇＢ＜ｔまた、個々のＰＨの計算量を均等にする
ために、１回の処理におけるＡまたはＢの次数の変化を
高々１次にとどめる。このようにすると、Ａ、　Ｂのｄ
ｅｇＡ。

ｄｅｇＢ次の項が非零とは限らなくなるが、Ａ　（Ｂ）
のｄｅｇＡ　（ｄｅｇＢ）次の項が零であれば、Ａ　（
Ｂ）を単に高位シフトしてやるといつた操作を行えば問
題ない。

従って、第１５図のアルゴリズムは第１６図のようにす
ることが出来る。第１５図においてＡ　（Ｂ）またはＬ
　（Ｍ）を求めるアルゴリズムは次数処理を除いて同じ
であるので、第１６図ではＰ　ｒ　ｏ　ｃ　ｅ　ｓ　ｓ
部を共通の表現で示している。実際の回路ではＡ　（Ｂ
）を求めるときとＬ　（Ｍ）を求めるときでＰｒｏｃｅ
ｓｓ部を独立に２つ持つか、１つを２回用いなければな
らない。以下、１つのＰｒｏｃｅｓｓ処理について評価
を行うが、１つのＰｒｏｃｅｓｓ部を２回用いる場合は
処理速度を半分にし、２つのＰｒｏｃｅｓｓ部を独立に
持つ場合には必要なＰＨの数を２倍にすればよい。

ＧＣＤ生成のための主な具体的計算は、第１６図のＰｒ
ｏｃｅｓｓと表された部分であるので、これをＰＥで実
現することを考える。但し、Ｓｅｔで表された次数処理
、及び５ｔａｔｅを設定する部分は変則的な処理である
ので、外部回路によって実現する。この回路は第３１図
に示すようにα、βの０検出回路１．２（ＯＲによって
構成される）と次数の比較器３、４．５　（コンパレー
タ）の結果から５ｔａｔｅを定める回路６　（ＲＯＭ等
）と次数の減算器７，８（アダーによって構成される）
によって構成され非常に小さな回路規模で実現出来る。

Ｐｒｏｃｅｓｓ処理は、入力→選択→積和処理となって
いるのでＩＰＥの動作に対応している。５ｔａｔｅの状
態はセレクタの選択信号Ｓｔ、　　Ｓ２によって表３の
ように対応させる。Ｐｒｏｃｅｓｓ処理１回をＩＰＨに
割り当てた場合、第１８図のように接続される。第１８
図において一番上の段は、α、βを設定するための段で
あり、各ＰＥで決定されたα。

β（Ｇ、　Ｈから出力）はその下の列全てに共通である
。また５ｔａｔｅの状態もまた各列について共通である
。

この場合、必要なＰＨの数は２ｔ＊　（２ｔ＋２）個で
あり、処理速度は１符号語単位で処理されるので１０−
２１０−２Ｏ（ｌｅｎｇｔｈ／５ｅｃ）　＝ｎ＊　（１
０−２０）Ｍｗｐｓ　（ｗｏｒｄ／５ｅｃ）　＝ｎ＊　
（８０−１６０）　Ｍｂｐｓ（ｂ　ｉ　ｔ　／　ｓ　ｅ
　ｃ　）　（ｎは符号長）となる。

また、Ｐｒｏｃｅｓｓ処理２を回、即ちｌ多項式毎の処
理をｌＰＥに割り当てた場合、第２２図のように接続さ
れる。第２２図においてａ目、ｂＩｌを実現するために
レジスタ５．７の後にレジスタを挿入している。これに
よって、次のＰＥへの係数データ入力をＡ、　　Ｉ３．
　Ｃの多項式について、個々の多項式の次数に相当する
項を互いに揃えて高次から順次入力することになる。ま
たα、βを設定するためにＣＫ　２、及びＣＬで制御さ
れるレジスタを外部的に付加する必要がある。入力多項
式Ａ、　　Ｉ３．　　Ｃを５ｔａｔｅによって選択した
ｘ、ｙ出。

力多項式の最高次数の係数を各々互い違いにβ。

αとしＨ，Ｇから出力してＣＫ　２でラッチして、各々
のＰＥ毎にその値をレジスタに保存する。但し、Ａ、　
　Ｂ、　　Ｃの多項式の最高次数入力中はα。

βが定ま、らないためＣＬによって０が出力される（最
高次数の処理結果は０となることが決っているため）。

この場合、必要なＰＨの数は２ｔ＊２個であり、処理速
度はＰｒｏｃｅｓｓ処理２を回をＩＰＲに割り付けるの
で、（１０−２０）　／２ｔＭ１ｐｓとる。

ここで、第２５図に示す例について第１８図、第２２図
の接続でＡ　（Ｂ）を求める場合の信号の流れを各々第
１９図、第２３図に示し、Ｌ　（Ｍ）を求める場合の信
号の流れを第２０図、第２４図に示す。（α。

βの値はＡ　（Ｂ）の処理の時決定され、Ｌ　（Ｍ）の
処理の時まで保存されるとする） また、第５図に示すＰＥを第２６図のように用いて、第
２７図のように接続することによって第２２図の接続を
最初に定めた通信路の条件である隣同士か自分自身とで
き、かつ第１３図のシンドローム出力Ｓ　（ｘ）を直接
受けて誤り位置多項式、及び誤り数値多項式を出力する
ことが出来る。（タイミングは第２３図、第２４図と同
じ。但し、＃０のＰＥはＡ　（Ｂ）の処理の最初のみＳ
ｌ、、４＝ＯＯＯＯ１以降Ｓ１．。

４＝０１００とし、Ｌ　（Ｍ）の処理の最初のみＳｌ、
、４＝１１００、以降Ｓ１．．４＝０１００とすること
によって第２３図、第２４図の入力が実現される。）ま
た、Ｐｒｏｃｅｓｓ処理の＃毎の処理をＩＰＨに割り当
てた場合、第５図のＰＥを図２８のように用いて、第２
９図のように接続される。この場合、必要なＰＥの数は
２を個であり、処理速度は（１０−２０）／　（２ｔ＋
２）　Ｍｌｐｓとなる（タイミングは第１９図、第２０
図と同じ）。

（誤り位置、及び誤り値生成部） ステップ３では、ステップ２で得られた誤り位置多項式
σ（ｘ）、誤り数値多項式ω（ｘ）、ならびにσ（ｘ）
の微分のσ′（ｘ）という３つの多項式に、そのＲ３符
号が定義されるＧＦ　（２−）の元α−’（ｉ＝ｎ−１
，・・・、１．０）を逐次代入してその値を求める計算
が必要である。ここで具体的に必要な計算は単に多項式
に変数を代入し、その値を求めるだけであるから、シン
ドローム計算と同様の繰り返しアルゴリズムを利用でき
る。例えば、ｔ−１火炎項式「（ｘ）の計算は次のよう
に展開される。

ｆ（ｘ）　＝ｆ、−，＊　’ｘ’−’＋ｆ、−、＊　ｘ
’−”　・・・＋ｆ　、　＊　ｘ＋ｆ。

”（（（Ｌ−＋　＊ｘ＋ｆ、ω＊＋ｆ、−３）＊Ｘ＋・
・・十ｆυ＊ｘ十ｆｏ）従って、シンドローム計算と同
様の次式のように分解される。

Ｚ０＝Ｏ Ｚ（＝　Ｚｌ−＋　＊　Ｘ　＋　Ｌ−＋　　　　　　（
ｊ　＝　１　＋・・・、１）ｆ（ｘ）＝Ｚ。

但し、シンドローム計算では各Ｉ’Ｅが代入すべきＸを
予め持っており、各ｒ’Ｅに係数を代入していったが、
ここでは係数ｆ、−＋　０　＝１　、・・・、１）が予
めわかっておりＸが各ＰＥに代入される。

従って、第１図のＰＥを第３２図のように用い、第３３
図のように接続して、第３４図のように信号を送る。第
３３図は、選択信号Ｓｌ、２＝００に固定してＢ入力に
係数ｆ、ｌを設定して置きＡ入力からα−１を順次入力
して行くことにより、最後のＰＥからｆ（α−１）の値
が順次出力されるようにしたものである。１つのＩ’Ｅ
にＺ＋−１（前ＰＥのｅ出力）とα−１（前ＰＥのα−
」出力）が同時に入力され、そのＩ’ＥからＺ＋　＝　
Ｚｌ−＋　＊α−’　＋　ｆ、−、、及びα−１が出力
される構成になっている。

この処理を、ｉ＝１からｔまで各々のＰＥに割り付ける
ことによって、ｆ　（ｘ）が計算される。

また、第５図の構成のＰＥを第３５図のように用い、第
３６図のように接続して、第３７図のように信号を送る
。まず係数ｆの設定は、Ｅ入力にｆｌ−＋（ｊ＝１．・
・・、１）を順次入力し、各ＰＥが設定されるべきＬｌ
の値が入力されたとき、選択信号Ｓ１．．４＝ＯＯＩＯ
とする。これによって、Ｗ、Ｚ出力からｆｌ−１が出力
されレジスタ８に「１．が入力される。それ以後、Ｓｌ
、。

４＝００００とすることによってレジスタ８にｆｌ−１
が蓄えられる。そして、次の受信系列の処理を行うとき
、Ｓｌ、、４＝０１１０とすれば、レジスタ８に蓄えら
れていたＬｌがＹ出力から出力されレジスタ７に入力さ
れる。以降、選択信号Ｓｔ、、４＝ＯＯＯＯとすればＹ
出力からは常に「１１が出力され、各ＰＥにｆ　＋−１
が設定されたことになる。その間、Ｘ出力はへ入力を選
択し、α−’（ｉ＝ｎ−１，・・・、０）が出力され続
け、そのα−１出力はレジスタ５から１クロック遅本で
次のＰＥに順次送られる。それを１受信系列毎に行うこ
とによって、第３４図のｆ（α−１）の計算が行われる
。これを、第１３図、第２７図の回路とつなげることに
よってステップ１−３がインターフェース回路なしで実
現できる。

第３４図、第３６図の回路はω（ｘ）、σ（ｘ）。

σ′（ｘ）の計算のために３セツト必要である。１セツ
トはｔ個必要であるので、必要なＰＥの数は３ｔ個であ
り、処理速度はα″′（ｉ＝ｎ−１，・・・、０）が１
ワード毎に対応して順次処理されるため１０−２１０−
２Ｏである。

ここで、σ（ｘ）の微分式σ′（ｘ）の係数を考える。

ｆ（ｘ）＝ｆ、、＊ｘ”＋ｆ＋−２＊ｘｌ−”＋−＋ｆ
、＊ｘ＋ｆ。

としたとき、ｆ（’ｘ）の微分式ｆ’（ｘ）はｆ’　（
ｘ）＝（ｔ　　１）＊Ｌ−１＊ｘ’−”＋（ｔ　　２）
＊ｆｌ：４＊Ｘ’−”＋−＋ｆｌとなる。（ｔ−ｉ）の
値が偶数のとき、ガロア体の性質から（ｔ−ｉ）＝Ｏと
なるので、ｆ’（ｘ）の係数は飛び飛びに０の値をもつ
。、従７．り、て１．１σ′（ｘ）の係数の設定はＯ係
数の時、係数設定時に選択信号Ｓ１．。

４＝００１０の代わりにＳｌ、、４＝ＯＯ０１とすれば
、Ｃ入力のＯがＷ出力から出力されレジスタ８に設定さ
れる。

（消失位置多項式生成部） Ｓ個の消失誤りが位置ｊｌ、　ｊ２．・・・＋ＪＳに生
じ、１個の消失以外の誤りが位置ｋｌ、　　ｋ２．・・
・、ｋｒに生じている場合を考える。但し、 ２ｒ＋ｓ＋１≦ｄ　　（ｄ：最小距離）が成立している
と仮定する。ここで、 Ｙｉ＝ａ１’　　　（ｉ＝＝ｔ、　　２．−、ｓ）とし
、消失位置多項式λ（ｘ）を λ（ｘ）＝（１−Ｙ＋＊ｘ）＊（Ｉ　　Ｙ＝＊ｘ）−・
・（ｌ　　Ｙｉ＊ｘ）とお（と ５（ｘ）＊λ（ｘ）　（７（ｘ）　＝　ω（ｘ）ｍｏｄ
ｘ”が成立することが導ける。但しσ（ｘ）は誤り位置
多項式であり、ω（ｘ）は となるｒ＋ｓ−１次以下の多項式である。但し、Ｅ。

は位置ｊｉの誤りの値であり、Ｌｋはαｋ　ｌ　（ｉ　
＝１．・・・。

ｒ）であり、ｅｌは位置ｋｉの誤りの値である。

このとき、σ（ｘ）、ω（ｘ）をユークリッドの互除法
によって求めるためには、第１５図、第１６図のアルゴ
リズムにおいてシンドローム多項式Ｓ　（ｘ）を５（ｘ
）＊λ（ｘ）で置き換え、ｄｅｇＡ＜ｔ　（ｄｅｇＢ＜
１）をｄｅｇＡ＜を十ｓ　（ｄｅｇＢ＜ｔ＋ｓ）で置き
換えればよい。

従って、消失誤り訂正を行うにはＳ　（ｘ）　＊λ（ｘ
）をＰＥを用いて生成すればよい（ｄｅｇＡ　（Ｂ）＜
ｔ＋Ｓへの置き換えはコントロール部で行われる）。

λ（ｘ）を計算するためにλ（ｘ）の式を次式のように
分解する。

Ｚ０＝１ ＺＨ＝（Ｉ　　　Ｙ＋　＊　ｘ　）　　＊　Ｚｌ−＋”
Ｙｌ　＊　Ｚｌｌ　＊　Ｘ　＋　Ｚｌ−＋　（ｊ＝　１
＋・・・、ｓ）λ（ｘ）　＝　Ｚ。

従って、λ（ｘ）の具体的計算はＺｌ　＝：　Ｙｌ　＊
　Ｚｌ−＋　＊　Ｘ十２＋−＋を行えば良い。次数は信
号の順序を示しているだけであるので、まずＺｌ−１の
入力にＹｌを乗じて、ｌクロック遅らせたＺｌ−１と加
算すればよい。よって、λ（ｘ）を生成するには第４２
図のようにＰＥを用い、第４３図のように接続すればよ
い（タイミングは第４４図に示す）。

先ず、Ｓｌ　（ｉ＝１）のＰＨについてセレクタの選択
信号をＳｌ、２＝０１とし、六入力Ｚ、＝１をＸ　Ｌ。

出力し、Ｃ入力０をＹに出力する。演算結果であるＹＩ
＊Ｚ６＝Ｙｌはレジスタ６に入力され、Ｘ出力ｚ０はレ
ジスタ５によって１クロック遅らされＢに入力される。

それ以後、Ｓｌ、２＝ｌＯとすることによってＸにＣ入
力Ｏを、Ｙに１クロック遅らされたＺ。

を出力し、次のクロックで演算結果Ｚ。＝１がレジスタ
６に入力され、Ｑから２１＝（Ｙ１＊Ｘ＋１）が順次出
力されたことになる。次に＃２以降のＰＥについて（ｉ
＝２．・・・、ｓ）、まずセレク、り選択信号をＳｌ、
２＝０１とし、ＱからのＺ　ｌ−１出力の最高次の係数
を六入力としてＸに出力し、Ｃ入力ＯをＹに出力する。

それによって、Ｙ　＋　＊　Ｚ　＋−＋の最高次の項が
演算されレジスタ６に入力される。レジスタ５からはｌ
クロック遅らされたＺｌ−１が出力され、Ｂ入力にフィ
ードバックされる。Ｂ入力にＺ、−１がフィードバック
されたときＳｌ、２＝ＯＯとすることによって、Ｙｌ　
＊　ｚ、−、、＊　Ｘ　＋　Ｚｌ−１の演算結果が順次
レジスタ６から出力され、次のＰＨに入力される。従っ
て、＃ＳのＰＥからλ（ｘ）の結果が高次の項から出力
される。

Ｓ≦２ｔであるのでここで必要なＰＨの数は２ｔであり
、Ｓ以上のＰＥのＹに〇を割り付ければ＃２ｔのＰＥか
らλ（ｘ）の結果が高次の項から出力される。

またλ（ｘ）　＊Ｓ　（ｘ）を生成するには第４５図の
ようにＰＥを用い、第４６図のように接続する（タイミ
ングは第４７図に示す）。第４６図の構成は第４８図に
示す多項式の乗算回路と全く同じ構成になっている。セ
レクタ選択信号はＳｌ、２＝ＯＯに固定しておけば良い
。乗算回路の動作は公知であるのでここでは省略する。

しかし、第４６図の乗算回路はλ（ｘ）の入力が全ての
ＰＥに入力され通信距離が異るので、第５図のＰＥを第
５２図の様に用い、第５３図のように接続する事によっ
て通信距離を同じにすることが出来る（タイミングは第
５４図に示す）。ここでは乗算Ｃ（ｘ）　＝　Ａ（ｘ）
　＊　Ｂ（ｘ）の計算を次の様に分解する。

Ａ　（ｘ）　＝　ａ、、−＋＊ｘ”−’＋　ａｌｌ、＊
ｘ″−”＋・＋　ａ、＊Ｘ＋ａ。

としたとき Ｃ（ｘ）＝　ａｆｆｉ−、＊Ｂ（ｘ）＊ｘ”−’　＋ａ
、−ｚ＊Ｂ（ｘ）＊ｘ−”十−・−−＋　ａ　＋＊Ｂ（
ｘ）　＊ｘ　＋　ａ０＊Ｂ（ｘ）となるので ２、　　＝０ Ｚ　（＝Ｚ　＋−＋　＊　ｘ　＋　Ｂ　（ｘ　）　＊　
ａ　＋ｗ−１（１＝１　＋　・・・＋　ｒｌ’ｌ　）Ｃ
（ｘ）＝　Ｚ、。

従って、ここでは各ＰＥへのＳｌの割付を逆にし、＃１
のＩ’ＥにＳよ−１を割り付ける（Ｓ、、−１の割付力
は後述する）。まず＃ｌのｒ’Ｅではｉ　ｏ　”　Ｏと
し、２．　＝　２゜＋　ｎ（ｘ）＊　ａ、、、、１　（
ａ、、　＋　＝　８２１　＋、　ｒ３（ｘ）　＝λ（ｘ
））を計算し、次のＩ’Ｅはその出力に対し更に１クロ
ック遅らせた１３　（ｘ）を、ｒ３　（ｘ　）　＊　ａ
　ｍ　−ｉ　、として加算する事によって２１＝Ｚ＋−
１＊Ｘ＋Ｂ　（ｘ）　＊ａｍ１の演算が行われる。これ
をｍ＝２を回、即ち２を個のＥ’Ｅに割り付ける事によ
ってＣ（ｘ）の計算が行われる。

また、第５３図の接続は第１３図のシンドローム生成部
からの出力Ｓ　（ｘ）を直接受けてＳ　（ｘ）　＊λ（
ｘ）を生成する構成になっている。第５３図の回路に於
て、各々のＰＥに設定すべき３．（ｊ＝２ｔ　　ｉ。

・・・、０）が送られてきたときＳ　１、．４　＝　０
１０１とすることによってレジスタ９に８１が入力され
、それ以後Ｓ　１、．４　＝　０１００とすることによ
つてレジスタ９の出力がＣ入力にフィードバックされる
ので、レジスタ９に８１が蓄えられ、そのＰＥにＳＩが
選択されたことになる。前述の乗算は各ＰＥのセレクタ
選択信号をＳｌ、、４＝”０１００とし、２＋−＋を六
入力に、λ（ｘ）をＣ入力に入力することによって行わ
れる。

但し、λ（ｘ）はＺ、の入力から１クロック遅れて入力
させるために、前ＰＥにおいてレジスタ７からのλ（ｘ
）出力をＤ入力にフィードバックしＷ出力を通じてレジ
スタ８から出力させる。

また、第５０図の回路はＹ＋　（ｉ　＝１　、・・・、
ｓ）が連続入力される場合のλ（ｘ）生成部を示してい
る。

これも第５図のＩ’Ｅを第４９図の様に用い、第５１図
のように信号を送ることによってＹ（ｘ）の入力が各々
のＰＥに設定される。通常、セレクタ選択信号はＳｌ。

。 ４＝００００　（＃１のＰＥのみＳｌ、、４＝ｌＯ００
）とし、設定すべきＹｌがＤ入力から入力されたときＳ
ｌ、、４＝ＯＯ０１（＃１のＰＥ（７）み１．．４＝１
１０１）とすることによって、Ｚ出力にＤ入力が選択さ
れレジスタ９にＹｉが入力され、以後セレクタ選択信号
の設定を戻すことによって、レジスタ９の出力はＣ入力
、Ｚ出力を通じてレジスタ９にフィードバックされレジ
スタ９にＹｉの値が蓄えられ、乗算器２の入力としてＹ
ｉの値が設定されたことになる。■設定後のλ（ｘ）生
成の動作は第４４図と同様になる。

（符号器） 符号器は通常多項式の除算回路によって構成される。除
算回路は第５５図の構成になっている。

それをＰＥを第５６図のように用いて第５７図のように
接続することによって、第５５図と全く同じ構成にする
ことが出来る。＃２ｔ＋１のＩ’Ｅの接！ｆｆａが変則
的であるのは、情報＋　（ｘ）　＝（Ｌｌ、　Ｔｏ−２
，・・・。

■。）とパリティＰ　（ｘ）　”　（Ｐ２＋、　　Ｐ２
１−＋、・・・、Ｐｌ）を選択して符号語にするセレク
タの役目をさせているためである。従って、最初は＃ｌ
から＃２ｔまでのｒ’Ｅの選択信号をＳｔ、２＝１０．
　＃２ｔ＋１のＩ’Ｅの選択信号をｓｔ、２＝０１とし
、情報１　（ｘ）の先頭ワードＩ　ｋ−１が＃２ｔ＋１
のＰＥのＣ入力から入力されたとき、＃ｌから＃２ｔま
でのＩ’Ｅの選択信号をＳｌ。

２＝００とする。その間＃２ｔ＋１のＰＥのＧからは情
報Ｉ　（ｘ）がＣ入力を通じてＹ出力から出力される。

Ｃ入力に情報ｒ　（ｘ）の最終ワード■。が入力され終
ると＃ｌから＃２ｔまでのＰＥの選択信号をＳＬ。

２＝Ｏ１とし、＃２ｔのＩ’Ｅの選択信号をＳｌ、　２
＝ＯＯとする。それによって、１２ｔ＋１のＰＥのＧか
ら情報１　（ｘ）に続いてパリティが出力される（タイ
ミングは第５８図に示す）。第５７図の回路は通信路が
各々のＰＥによって異なる。

（誤り訂正実行部、及びシステム） ステップ４の誤り訂正の実行部も、第３８図のように第
１図のＰＨによって構成される。但し、０検出回路（Ｏ
Ｒによって構成される）とガロア体上の逆数生成回路（
ＲＯＭ等）を外部的に加える必要がある。ＧＣＤ生成部
においてＡ　（１３）、　Ｌ　（Ｍ）の処理を１つのＰ
ｒｏｃｅｓｓ部を２回用いている場合は、ω（ｘ）の係
数が先に送られてくるのでω（α″）の値も先に計算さ
れ、この回路に送られる。この場合、σ（α−１）、σ
′（α−１）の出力タイミングを合わせるためにバッフ
ァを挿入し、ω（α−１）の出力を遅らせる必要がある
（ＧＣＤ、生成部に於て２つのＰｒｏｃｅｓｓ部で同時
にＡ　（Ｂ）とＬ　（Ｍ）の処理を行う場合はバッファ
を挿入する必要はない）。

タイミングを合わせたω（α一つとσ′（α−１）が入
力されたときω（α−′）をＢに入力し、σ′（α−′
）を逆数にして乗算器３に入力する。・σ（α−′）は
、０検出回路に入力されσ（α１）−〇の時０、σ（α
１）≠０の時ｌとしてセレクタ選択信号Ｓ２に入力する
。誤り位置、即ちσ（α″′）二〇の時Ｓｌ、２＝００
となるのでＴ出力は、ω（α″）を出力しσ′−１（α
一つと乗算することによって誤りの値ω（α゛つ／σ′
（α−１）が乗算器３から出力される。誤り位置でない
ときはσ（σ′）≠０であるので、Ｓｌ、２＝０１とな
りＹ出力はＣ入力のＯを出力するので、乗算器３の出力
は０となる。Ｘ出力からは常にバッファによって遅らさ
れた受信語系列ｒ、’　（ｉ＝ｎ−１，・・・、Ｏ）が
出力され、乗算器２からは受信語列ｒご　が出力される
。

従って、乗算器からの出力同士をＥＸＯＲすることによ
って誤り訂正が実行される。

また前３節において【（α−′）の値を求めるためにα
−’　（ｉ＝ｎ−１，・・・、０）を入力する必要があ
るが、α司（ｉ＝ｎ−１，−、Ｏ）発生回路として図１
のＰＥを第３９図のように用いることが出来る。第３９
図におい、てα′＝α−０とし、α８＝αとし、αｎ−
１を発生させる１つ前のクロックに於てセレクタ選択信
号Ｓｌ、　２＝１０とし、それ以後Ｓｌ、２＝ＯＯとす
れば良い。その様子を第４０図に示す。

以上述べてきたように、ユークリッドの互除法に基づ（
ＲＳ符号の復号器の各ステップを同一のＰＨによって構
成した。１例として各ステップを次の組合せにすること
によって、各Ｉ’Ｅの選択信号Ｓ１．。

４の制御のみで全体のシステムを動かすことが出来る。

その全体のシステムを第４１図に示す。

ステップ１）ＳＹＮＤＲＯＭＥ　　：第１３図ステップ
２）　　ＧＣＤ　　　　　、　　：第２７図ステップ３
）ＥＶＡＬＵＡＴＥ　　：第３６図ステップ４）ＣＯＲ
ＲＥＣＴ　　　：第３８図これによって、全体のシス・
テＲで必要なＰＥの数は次のようになる。

Ｓ　　　　Ｇ　　　　　ＥＣ ［（２ｔ）　＋　（２ｔ＋２）　＋　（３ｔ）　＋１１
−”　（７ｔ＋３）　＊　１０００１００Ｏこれに各Ｐ
Ｅの選択信号Ｓ１．．４を第１４図、第２３図、第２４
図、第３７図のように制御するコントロール回路を付加
することによって全体のシステムが構成される（コント
ロール回路はＲＯＭ等によって非常に小さな回路規模で
実現される。またα−１を第３９図で発生させる場合必
要なＩＣＥの数は７ｔ＋５となる）。

このシステムの処理速度は、ＧＣＤ生成部で１つのＰｒ
ｏｃｅｓｓ部を２回用いる場合には４ｔクロック以上か
かるので符号長ｎがｎ＞４ｔであれば１０−２０　Ｍ　
ｗ　ｐ　ｓで実現できる（２つのＰｒｏｃｅｓｓ部を用
いる場合の処理時間は２ｔであるので問題はない）。

符号化復号器をシステムとして考えた場合、消失誤り訂
正のための復号器は符号器としても用いることが出来る
ので、第５９図の消失誤り訂正のための復号器は１例と
して、次の組合せによって符号化復号器として実現でき
る。

１）ＳＹＮＤＲＯＭＥ　　：第１３図 ２）　　ＧＣＤ　　　　　　：第２７図３　）　　Ｅ　
Ｖ　Ａ　Ｌ　Ｕ　Ａ　Ｔ　Ｅ　　：第３６図４）ＣＯＲ
ＲＥＣＴ　　　：第３８図 ５）ＥＲＡＳＵＲＥ　Ｉ　　：第５０図６）ＥＲＡＳＵ
ＲＥＩＩ　　　　：第５３図これは第４１図の復号器に
ＥＲＡＳＵＲＥ　ＩとＥＲＡＳＵＲＥ　Ｔｌ　−を加え
たものであるが、処理速度は変わらず、全体のシステム
で必要なＰＨの数は次のようになる。

＋（２ｔ）　＋　（２ｔ＋１）　＋　（４ｔ）　＋　１
　＋　（２ｔ）　＋　（２ｔ）１＝　（１２ｔ＋３）＊
　１０００　ｇａｔｅまた消失訂正を行わない場合、第
４１図の復号器に第５７図の符号器を加える必要がある
。このとき全体のシステムに必要なＰＥの数は第４１図
の復号器で必要なＰＥの数（７ｔ　＋　３）に（２ｔ＋
１）を加えた（９ｔ＋４）である（符号化と復号を同時
に行わない場合には、ＰＥの接続、及びＰＥの制御を符
号化と復号で可変にすることによって第４１図の回路で
回路規模を変えることな（符号化復号器を実現できる）
。

以上のように、第１図または第５図のＰＥを用いること
によって、１０−２０　Ｍ　ｗ　ｐ　ｓの処理速度を持
っＲ３符号化復号器が次の回路規模で実現できる。

Ｒ８符号化復号器：　７ｔ−ｔ−３（９ｔ＋、４）消失
誤り訂正符号化復号器：　１２ｔ＋３例として、ｔ＝２
とｔ＝８のＲ３符号化復号器を考えた場合、ｔ＝２で１
７０００ゲート、ｔ＝８で５９０００ゲートとなり、コ
ントロール回路を入れてもＶＬＳＩでは十分実現可能な
範囲である。また、内部構造の規則性と通信距離の最適
化によりＶ　Ｌ　Ｓ　Ｉ化しやす（、ＰＥの数を増加さ
せることによって処理能力も１次関数的に増加できる構
成になっている。またＶＬＳＩ化の際、セレクタ、乗算
器、加算器からなる演算部は１箇所に固められているの
で最適化することによって１０−２１０−２Ｏ以上の処
理速度が得られる構成になっている。

又、復号処理の中心であるステップ２の誤り位置多項式
、及び誤り数値多項式の生成をこのＰＥを用いて第１８
図の様に接続する事によって１０−２１０−２Ｏの高速
処理が実現できる。ステップ１．３の処理も特殊な処理
によって高速化する（符号語毎に並列化する等）か、ま
たはこのＰＥを第６０図のように接続することによって
１０−２０　Ｍ　ｌ　ｐ　ｓの高速処理が実現できる。

但し、回路規模は非常に大きくなる。

また、このＰＥを用いてＸ１発生回路、及び除算器が第
６１図、第６２図のように構成できる（タイミングは第
６１図、第６２図に示す）。

以上のように、このＰＥを用いてガロア体上の種々の演
算が可能であり、Ｒ８符号の符号化復号器が効率的に構
成できる。

〔発明の効果〕

本発明ではＶ　Ｌ　Ｓ　Ｉアーキテクチャの特徴を生か
し、次のことを実現した。

■）高信頼性（大能力） ２）高速性 ３）内部構造の規則性 ４）大集積化 これによって、１０−２１０−２Ｏ（ｗｏｒｄ／５ｅａ
）以上の処理速度を持つ消失誤り訂正器が実現できるこ
とを示した。また、訂正能力に対して同じ構成のＰＥを
１次関数的に増やしていくことによって任意の高信頼性
を得られる構成にした。また、各々のＰＥの制御もセレ
クタ選択信号の制御のみを行うことにより全てのＰＥを
同じクロックで動作させるおとができる。これは高速性
と高信頼性が求められるシステムには非常に有効な方式
である。

【図面の簡単な説明】

第１図は本発明の実施例に係るプロセッシング・エレメ
ント（ＰＥ）の構成図 第２図は１）１乙のセレクタの構成を示す図第３図はＩ
）　Ｅのガロア体上の乗算器の具体的構成を示す図 第４図はＰＥのガロア体上の加算器の具体的構成を示す
図 第５図は本発明による拡張されたＩ’Ｅの構成図第６図
は本発明による第１図を用いたシンドローム生成用ＰＥ
の構成図 第７図は本発明による第１図を用いたシンドローム生成
用ＰＥの接続図 第８図は本発明による第１図を用いたシンドローム生成
用１’Ｅのタイミング図 第９図は本発明による第１図を用いたシンドローム生成
用ＰＥの他の構成を示す図 第１０図は本発明による第１図を用いたシンドローム生
成用ＰＥの他の構成を示す接続図 第１１図は本発明による第１図を用いたシンドローム生
成用Ｉ’Ｅの他の構成を示すタイミング図第１２図は本
発明による第５図を用いたシンドローム生成用ＰＥの構
成図 第１３図は本発明による第５図を用いたシンドローム生
成用ＰＨの接続図 第１４図は本発明による第５図を用いたシンドローム生
成用ＰＥのタイミング図 第１５図はＧＣＤを求めるためのアルゴリズムを示す図 第１６図は本発明によるＰＥを用いたＧＣＤ生成の為の
アルゴリズムを示す図 第１７図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｈの構成図 第１８図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅの接続図 第１９図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅのタイミング図 第２０図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅのタイミング図 第２１図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅの他の構成を示す図 第２２図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｈの他の構成を示す接続°間 第２３図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅの他の構成を示すタイミング図第２４図は本発明によ
る第１図を用いたＧＣＤ生成用ＰＥの他の構成を示すタ
イミング図第２５図はＧＣＤ生成の例を示す図 第２６図は本発明による第５図を用いたＧＣＤ生成用［
’Ｅの構成図 第２７図は本発明による第５図を用いたＧＣＤ生成用！
’Ｅの接続図 第２８図は本発明による第５図を用いたＧＣＤ生成用Ｐ
Ｈの他の構成を示す図 第２９図、第３０図は本発明による第５図を用いたＧＣ
Ｄ生成用ＰＨの他の構成を示す接続図第３１図は５ｔａ
ｔｅ生成回路ブロック図第３２図は本発明による第１図
を用いた誤り評価用ＰＨの構成図 第３３図は本発明による第１図を用いた誤り評価用ＰＥ
の接続図 第３４図は本発明による第１図を用いた誤り評価用ＰＨ
のタイミング図 第３５図は本発明による第５図を用いた誤り評価用１）
Ｅの構成図、 第３６図は本発明による第５図を用いた誤り評価用１）
Ｅの接続図 第３７図は本発明による第５図を用いた誤り評価用ＰＥ
のタイミング図 第３８図は本発明による第１図を用いた誤り訂正実行用
ｒ’Ｅの構成図 第３９図は本発明による第１図を用いたαソー（α“）
１発生用ＰＥの構成図 第４０図は本発明による第１図を用いたα’−（α′）
１発生用ＰＥのタイミング図 第４１図は本発明による誤り訂正復号器のシステム構成
図 第４２図は本発明による第１図を用いた消失位置多項式
生成用ＰＥの構成図 第４３図は本発明による第１図を用いた消失位置多項式
生成用ＰＨの接続図 第４４図は本発明による第１図を用いた消失位置多項式
生成用ＰＨのタイミング図 第７１５図は本発明による乗算用ＰＥの構成図第４６図
は本発明による乗算用ＰＥの接続図第４７図は本発明に
よる第１図を用いた乗算用ＰＥのタイミング図 第４８図は従来の乗算回路の構成を示す図第４９図は本
発明による第５図を用いた消失位置多項式生成用ＰＥの
°構成図 第５０図は本発明による第５図を用いた消失位置多項式
生成用ＰＨの接続図 第５１図は本発明による第５図を用いた消失位置多項式
生成用ＰＥのタイミング図 第５２図は本発明による第５図を用いた乗算用ＰＥの構
成図 第５３図は本発明による第５図を用いた乗算用ＰＥの接
続図 第５４図は本発明による第５図を用いた乗算用ＰＥのタ
イミング図 第５５図は従来の符号化回路 第５６図は本発明による第１図を用いた符号化用ＰＥの
構成図 第５７図は本発明による第１図を用いた行司化用ＰＥの
接続図 第５８図は本発明による第１図を用いた符号化用ＰＥの
タイミング図 第５９図は本発明による消失誤り訂正符号化復号器のン
ステム構成図 第６０図は本発明による第１図を用いた高速積和演算算
器を示す図 第６１図は本発明による第１図を用いたＸ２″′発生器
を示す図 第６２図は本発明による第１図を用いた除算器を示す図 ■　・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・乗算器、■　・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・加算器、第７　叉 招５Ｚ ・・１　　＋　　ｔ　　Ｉ−Ｓ　　＋　　Ｉ　　＋−第
８２ 男ｌど区 も１３図 ・・１１ 第１４國 泊／　ｌ、、　Ｊ　（Ｃ）：、ｐ、、ｃ、＝ｂ勇毛１１
：、区（Ｃ７）：Ｊｄω 第１ム図（ｅ　）：ノｄα Ｃに　ｔｔｔ！ｔｌｔ＋を 第？０國 第２２Ｘ 〜　　（ラ　　マ　こ　　夕　　ａ い　央　）−Ｑ 酬 鴇 ｏ　　　　　　　＞　　　　　　　　　Ｘ　　　　％　
　　　　　　Ｋ誌　　　　　　　　　　　　　　　　　
　　　　　　　稔第２７囚 ｃＫｔ　　を 第４０図 躬４１図 Ｃに↑　↑ Ｑ　　　　屋ヱ三Ｔ＝口＝＝＝＝　　ベズ・（χ・ｚ−
１ｏ）５１．２　　　　　２　０　　　　　　　　　　
　　？５７ｔ（’Ｉ−Ｚ◆７ａ）ｆ　　　　　　　　　
　　　　　ｘ？二逼χＹ＋”Ｙ−１’＝＝＝＝二　　　
ｈ仇入ｘ（７Ｑ　　　　　【■翌！菰工Ｔ［′１・λ″
゛１・ゝ“男４４図 Ｃに　↑　↑ ３　　　　）ｖ’、５ｚ　＊Ｓｚ　ｌ＠５ｘ葦＝（＝２
ｔ　　　彰］≠℃冗Ｃ■＝ 躬４７１責 。４ｆ＋　　躬５３図 仄＝口［ 唱５４図 Ｖ３） ｃＫｔ　　を 第６７図

Claims (1)

【特許請求の範囲】
1. （１）多入力多出力、または多入力−出力のセレクタ回
   路と、そのセレクタ回路の出力を少なくとも一方の入力
   にもつガロア体上の乗算器と、その乗算器出力を加算す
   るガロア体上の加算器と、その加算器出力及び前記セレ
   クタ回路出力を蓄えるレジスタから構成される演算回路
   を複数同型に接続することによって処理能力を増大させ
   、Ｙ＿ｉ（ｉ＝１，・・・，ｓ）の値を入力して、多項
   式λ（ｘ）λ（ｘ）＝（１−Ｙ＿１・ｘ）・（１−Ｙ＿
   ２・ｘ）・・・（１−Ｙ＿ｓ・ｘ）の係数を求めること
   を特徴とする消失位置多項式生成回路。