JPS63157527A - 最大公約多項式生成回路 - Google Patents

Abstract

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

Description

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

本発明は、ＢＣＨＣＨ２Ｘ号化復号において、ＧＣＤ（
最大公約数）生成を行う技術に関する。

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

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

この誤り訂正符号には、対象とするシステムに応じた種
々の物があるが、最も代表的なものは巡回符号と呼ばれ
る線形符号の１クラスである。これには、ランダム誤り
訂正に適したＢＣＨＣＨ２Ｘ−スト誤り訂正に適したフ
ァイヤー符号、更にＢＣＨＣＨ２Ｘｆｌｌであり、バイ
ト誤り訂正に適したＲｅｅｄ−Ｓｏｌｏｍｏｎ符号（以
下、Ｒ３符号）等が含まれる。

なかでも、Ｒ３符号は、同一の符号長と訂正能力を持つ
線形符号の中で、最も冗長度を低（出来るという特徴を
持つ、実用上非常に重要な符号であり、衛星通信、磁気
ディスク、コンパクトディスク（以下、ＣＤと呼ぶ）等
に広（利用されている。

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

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

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

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

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

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

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

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

多項式の拡張ＧＣＤ問題を解くための基本的なシストリ
ック・アルゴリズムは、既にＫ　ｕ　ｎ　ｇによって示
されているが、これはＰｒｏｇｒａｍａｂｌｅ　５ｙｓ
ｔｏｒｉｃＣｈｉｐでソフト的に実行する巳とを前提と
したものであった。

以上の点に鑑み、本発明はユークリッドの互除法にシス
トリック・アルゴリズムの考え方を応用し、実際にＢ　
ＣＨ符号のＧＣＤ生成器に適用するための具体的アルゴ
リズムを検討し、特に、同一のプロセッシング・エレメ
ント（以下ＰＥ）によって実現することを目的としてい
る。

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

［実施例］ 本発明の詳細な説明に入る前に誤り訂正の原理について
説明する。　゛ １層１１Δ１旦 まず、Ｒ３符号の原理について述べる。Ｒ３符号は、同
一の符号長と訂正能力を持つ線形符号の中で、最も冗長
度を低くできるという特徴を持つ、実用土非常に重要な
符号である。

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

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

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

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

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

１　（ｘ）　＝　Ｉｏ　＋　ｉｌ　ｘ　＋ｒ　＋　ｘ”
　＋−＋Ｉｈ−Ｉ　Ｘ’−”　＋１ｋ−１ｘ’−’　　
　（２１１）同様に付加される（ｎ−ｋ）個の検査シン
ボルＣ＝（Ｃｏ＋　ｃ、、”・、ｃ、−に−１）　　　
　　　　　（２１２）は、 Ｃ（ｘ）＝　ｃ、＋ｃ、ｘ＋ｃ、ｘ”＋　−＝　Ｃ１１
−に−１’Ｘ’−’−’　　　　　（２−１３）更に、
これらをまとめた符号語Ｆ Ｆ＝（ｆａ、　　ｆ＋、　　ｆａ、・・・ｆ−＋）　　
　　　　　（２１４）＝ＣｉＣ１”’Ｃｎ−に一１＋ｊ
Ｏ＋ｊｌ＋ｆ！＋””ｔｋ−１）　　　　（２１５）は
、 Ｆ（ｘ）　＝　ｆｅ＋ｆ　＋　ｘ＋ｆｚ　ｘ２＋　・・
−ｆｌｌ−ｔ　ｘｌ′−”＋ｆｌｌ−，ｘ”−’　　（
２−１６）と多項式表現される。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

σ　（Ｘ）・Ｓ　（ｘ）　＝　［ω　（Ｘ）コ　ｍｏｄ
ｘ”　　　　　　　　　　　　　　　　　（２−３８）
従って適当な多項式Ａ　（ｘ）を用いてσ（Ｘ）、　Ｓ
　（Ｘ）。

ω（Ｘ）の関係が次のように表わされる。

Ａ　（ｘ）・ｘ”＋　ａ　（ｘ）・Ｓ　（ｘ）　＝ω（
ｘ）　　　　　　（２−３９）ところで、誤りの個数ｌ
は＜ｐｔ≦ｔ）としているから、ω（Ｘ）とび（Ｘ）は ｄｅｇ　ω（ｘ）　＜　ｄｅｇ　ａ　（ｘ）≦ｔ（２−
４０）を満たす。さらにω（Ｘ）とσ（Ｘ）は互いに素
（最大公約（ＧＣＤ）多項式が定数）であるから（２−
３９）、（２−４０）式を満たすω（Ｘ）とσ（Ｘ）は
定係数の違いを除いて一意的に定まる。以上よりω（Ｘ
）とび（Ｘ）はｘ！１とＳ　（ｘ）の最大公約（ＧＣＤ
）多項式を求めるユークリッドの互除法の過程で求め得
る。ここで゛、ユークリッドの互除法を利用した最大公
約（ＧＣＤ）多項式の算出方法について簡単に述べる。

まず、２つの多項式ＡとＢの最大公約多項式をＧＣＤ　
［Ａ、Ｂ］と０表わすことにする。又、このＡとＢに対
し次のような多項式λと百 ・ｄｅｇＡ≧ｄｅｇＢの場合Ａ　＝　Ａ−［Ａ　−Ｂ−
’］　−Ｂ　　　（２−４１）百＝Ｂ（２−４２） ・ｄｅｇＡ≧ｄｅｇＢの場合λ＝Ａ（２−４３）Ｕ　＝
　Ｂ−［Ｂ　−Ａ−’］・Ａ（２−４４）（［Ｘ−Ｙ−
’］：多項式Ｘを多項式Ｙで割った商）を定義すると、
ＧＣＤ　［Ａ、Ｂ］とＧＣＤ　［Ａ、百］は、次式を満
たす。

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

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

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

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

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

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

ｄｅｇＢｏ　＝２ｔ−１）、ＧＣＤ　［Ａｏ、Ｂｏｌを
求める途中で を満たす多項式り、　　Ｗが求まれば、Ｄが誤り位置多
項式σ（Ｘ）、Ｗが誤り評価多項式ω（Ｘ）を各々表わ
している。このようなσ（Ｘ）とω（Ｘ）は、定係数の
違いを除いて一意的に定まることがわかっている。従っ
て、ＡｏとＢｏに対して次のような　多項式Ａ、　　Ｂ
、　　Ｕ、　　Ｖ、　　Ｌ、　Ｍを定義し その初期値を Ｕ＝Ｍ＝１　；　　Ｌ＝Ｖ＝Ｏ；　　（Ａ＝Ａｏ、Ｂ＝
Ｂｏ）とおいて第１５図の繰返しステップを実行してい
き、ｄｅｇＡ　（ｄｅｇＢ）　＜ｔとなった時にＡ　（
Ｂ）がω（ｘ）、Ｌ　（Ｍ）がσ（Ｘ）として各々求ま
る。

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

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

第１５図について説明する。まず、ステップ１において
Ｕ＝Ｍ＝ｌ、Ｌ＝Ｖ＝Ｏ，Ａ＝Ａｏ、Ｂ＝Ｂ。

とおいて、初期値を設定する。ステップ２においてｄｅ
ｇＡ≧ｄｅｇＢの判定を行い、ステップ３において多項
式Ａ、　Ｂの最高次係数β、αを各々Ａ、Ｂにたがいち
がいに乗じ、式（２−４１）、　　（２−４３）の繰返
しステップにおけるＧＦ上の除算を省略している。

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

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

ｉ）　　ｄｅｇＡ、　ｄｅｇＢ≧ｔかつｄｅｇＡ≧ｄ　
ｅ　ｇ　Ｂ−・・“ｒｅｄｕｃｅＡ″ｉｉ）　　ｄｅｇ
Ａ、　ｄｅｇＢ≧ｔかつｄｅｇＡ≧ｄｅｇＢ−“ｒｅｄ
ｕｃｅＢ”１ｉｉ）　ｄｅｇＡ　＜　ｔ　　もしくは　
ｄｅｇＢ＜ｔ　’・・・’ｎｏｐ”スーツプ３　テ　　
）ｖｆρ　の　の ステップ３では、ステップ２で得られた誤り位置多項式
σ（Ｘ）と誤り評価多項式ω（Ｘ）から、誤り位置と誤
りの値の推定を行う。まず、受信語Ｒ＝　（ｒｏ、　ｘ
、・・、ｒｎ＝）中のシンボルの位置ｉ＝０゜１・・・
ｎ−１に応じたＧＦ（２″′）の元αりを誤り位置多項
式σ（Ｘ）に逐次代入する。この時、（２−３６）式よ
りσ（ａ−’）　＝Ｏが成立するならば、ｉが誤り位ｆ
ｆ１ｊｕに対し、α−１＝α−ｊｕが成立している事が
わがる。（ｊ　ｕ　＝　０　、１−・−ｎ　−１、ｕ　
＝　１　、２　・＝　１　、　１≦ｔ）また、そのよう
なα−１＝α−１”に対する誤り評価多項式ω（Ｘ）の
値は次のようになる。

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

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

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

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

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

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

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

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

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

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

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

Ｓ＋−＋＝（・べ（ｒａ−１木（！’　＋　ｒｎ−ｔ）
＊（Ｚ’　＋　ｒｎ−ｓ）＊α’　＋　・・・＋　ｒｌ
）＊α１＋ｒ６ 従って、上式は次のように分解される。

ｚｏ　＝Ｏ Ｚ＋　　＝Ｚ＋−＋　　＊　ａ’＋ｒＡ−＋　　　　　
　　　　　　　　（ｉ＝　１．−、ｎ）Ｓ、−、＝　Ｚ
。

第１図のＰＥを第６図のように用い、第８図のように信
号を送る。

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

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

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

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

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

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

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

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

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

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

＝２ｔ、　ｄｅｇＢｏ＝２ｔ−Ｂ、ＧＣＤ　［Ａｏ、　
Ｂｅ］を求める途中で、 ｄ　ｅ　ｇ　Ｗ　＜　ｔ　、　　ｄ　ｅ　ｇ　Ｄ≦ｔＣ
＊　Ａｏ　＋　Ｄ　＊　Ｂｏ　＝　Ｗを満たす多項式り
、Ｗ（Ｄが誤り位置多項式σ（Ｘ）、Ｗが誤り数値多項
式ω（Ｘ）を表す）を求める問題に帰着される。このよ
うなσ（Ｘ）とω（Ｘ）は、定係数の違いを除いて一意
的に定まることがわかっている。従って、八〇と８０に
対して次のような多項式Ａ、　　Ｂ、　　Ｕ、　　Ｖ、
　　Ｌ、　Ｍを定義し、Ａ　＝　Ｕ　＊　Ａｏ　＋　Ｌ
　＊　Ｂ０Ｉ３　＝　Ｖ　＊　Ａｓ　＋　Ｍ　＊　Ｂ。

その初期値を。

Ｕ　＝　Ｍ　＝　１　、　　Ｌ　＝　Ｖ　＝Ｏ，（Ａ　
＝　Ａｏ、　　Ｂ　＝　Ｂｏ）とおいて第１５図の繰り
返しステップを実行していき、ｄｅｇＡ　（ｄｅｇＢ）
＜ｔとなったときにＡ　（Ｂ）がω（Ｘ）、Ｌ　（Ｍ）
かび（Ｘ）として各々求まる。

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

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

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

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

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

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

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

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

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

また、Ｐｒｏｃｅｓｓ処理２を回、即ちｌ多項式毎の処
理をＩＰＥに割り当てた場合、第２２図のように接続さ
れる。第２２図においてａｌ−１、ｂｌ−１を実現する
ためにレジスタ５，７の後にレジスタを挿入している。

これによって、次のＰＥへの係数データ入力をＡ、　　
Ｂ、　　Ｃの多項式について、個々の多項式の次数に相
当する項を互いに揃えて高次から順次入力することにな
る。またα、βを設定するためにＣＫ　２、及びＣして
制御されるレジスタを外部的に付加する必要がある。入
力多項式Ａ、　　Ｂ、　　ＣをＳ　ｔ　ａ　ｔｅによっ
て選択したｘ、　　ｙ出力多項式の最高次数の係数を各
々互い違いにβ。

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

βが定まらないためＣＬによってＯが出力される（最高
次数の処理結果はＯとなることが決っているため）。こ
の場合、必要なＰＥの数は２を千２個であり、処理速度
はＰｒｏｃｅｓｓ処理２を回をｌＰＨに割り付けるので
、（１０−２０）　／　２　ｔ　Ｍ　ｌ　ｐ　ｓとる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ｆ（ｘ）　”　ｆｔ−１＊　Ｘ’−’　＋　ｆｔ−＊　
＊　Ｘ’−”　＋　−＋ｆｌ　＊　Ｘ　＋　ｆ。

としたとき、ｆ　（ｘ）の微分式ｆ’（ｘ）はｆ’　（
ｘ）　＝　（ｔ−１）　＊ｆｔ−，＊ｘ”＋（ｔ　−２
）＊ｆ、−，＊ｘ’−”＋・＋ｆ　。

となる。（ｔ−ｉ）の値が偶数のとき、ガロア体の性質
から（ｔ−ｉ）＝Ｏとなるので、ｆ’（ｘ）の係数は飛
び飛びにＯの値をもつ。従って、σ′（Ｘ）の係数の設
定はＯ係数の時、係数設定時に選択信号Ｓ１．。

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

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

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

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

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

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

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

Ｚ、＝１ Ｚｌ　＝（Ｉ　　Ｙｌ　＊　Ｘ）　＊　ＺＩ−＋＝Ｙ１
　＊　ＺＩ−１＊　Ｘ　＋　Ｚｌ−１（１＝　１　＋・
・・ｏｓ）λ（ｘ）　−Ｚ。

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

先ず、＄１（ｉ＝１）のＰＨについてセレクタの選択信
号をＳｌ、２＝０１とし、六入力Ｚ０＝１をＸに出力し
、Ｃ入力ＯをＹに出力する。演算結果であるＹ　＋　＊
　Ｚ　ｏ　”　Ｙ　ｒはレジスタ６に入力され、Ｘ出力
ｚ０はレジスタ５によってｌクロック遅らされＢに入力
される。それ以後、Ｓｌ、２＝１０とすることによって
ＸにＣ入力０を、Ｙに１クロック遅らされたＺｏを出力
し、次のクロックで演算結果Ｚ、＝Ｌがレジスタ６に入
力され、ＱからＺ、　＝　（Ｙ、　＊　ｘ　＋１　）が
順次出力されたことになる。次に＃２以降のＰＨについ
て（ｉ＝２．・・・、ｓ）、まずセレクタ選択信号をＳ
ｌ、　２＝Ｏ１とし、ＱからのＺ、−３出力の最高次の
係数を六入力としてＸに出力し、Ｃ入力ＯをＹに出力す
る。それによって、ｙ、　＊　ｚ、、の最高次の項が演
算されレジスタ６に入力される。レジスタ５からはｌク
ロック遅らされたＺｌ−１が出力され、Ｂ入力にフィー
ドバックされる。Ｂ入力にＺ　ｌ−１がフィードバック
されたときＳｌ、２＝００とすることによって、ＹＩ　
＊　ＺＩ−＋　＊　Ｘ　十Ｚ１−１の演算結果が順次レ
ジスタ６から出力され、次のＰＨに入力される。従って
、＃ＳのＰＥからλ（Ｘ）の結果が高次の項から出力さ
れる。

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

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

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

Ａ　（Ｘ）　”　ａｍ−＋　＊ｘ’−’　＋　ａ−、＊
ｘ−−”＋−−）　ａｔ　＊　Ｘ＋ａ。

としたとき Ｃ（ｘ）　＝　ａｍ−＋＊Ｂ（ｘ）＊ｘ−’　＋ａ−，
＊Ｂ（ｘ）、＊ｘ−２＋−・・・”　＋　ａ＋＊Ｂ（ｘ
）　＊ｘ　＋　ａｏ＊Ｂ（ｘ）となるので Ｚ０＝Ｏ Ｚｌ　　”　Ｚｌ−Ｉ＊Ｘ　＋　Ｂ（ｘ）　＊ａｍ−１
（１＝１　！　”’　ｌ　ｍ）Ｃ（ｘ）＝　Ｚヨ 従って、ここでは各ＰＥへのＳ、の割付を逆にし、＃ｉ
のＰＥに５２１−１を割り付ける（Ｓ２１−１の割付力
は後述する）。まず＃ｌのＰＥではＺ０＝０とし、Ｚ　
＋　”　Ｚ　。

＋、　１１３（ｘ）　＊　ａｍ−＋　（ａｍ−１＝　ｓ
２＋−＋　ｌ　Ｂ（Ｘ）　”：λ（Ｘ））を計算し、次
のＰＥはその出力に対し更に１クロツタ遅らせたＢ　（
ｘ）を、Ｂ（ｘ）＊ａｍ−ｉとして加算する事によって
Ｚ＋＝Ｚ＋−１＊ｘ＋Ｂ　（ｘ）　＊ａ＠−１の演算が
行われる。これをｍ＝２を回、即ち２を個のＰＥに割り
付ける事によってＣ（ｘ）の計算が行われる。

また、第５３図の接続は第１３図のシンドローム生成部
からの出力Ｓ　（ｘ）を直接受けてＳ　（ｘ）　＊λ（
ｘ）を生成する構成になっている。第５３図の回路に於
て、各々のＰＥに設定すべきＳｌ　（ｊ＝２ｔ　　１゜
・・・、０）が送られてきたときＳｌ、、４＝０１０１
とすることによってレジスタ９に８１が入力され、それ
以後Ｓ１．．４＝０１００とす、ることによってレジス
タ９の出力がＣ入力にフィードバックされるので、レジ
スタ９に８１が蓄えられ、そのＰＥにＳｌが選択された
ことになる。前述の乗算は各ＰＥのセレクタ選択信号を
ＳＬ、、４＝ＱＬＯＯとし、Ｚｌ−１を八人力に、４λ
（Ｘ）をＣ入力に入力することによって行われる。

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

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

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

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

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

それをＰＥを第５６図のように用いて第５７図のように
接続することによって、第５５図と全く同じ構成にする
ことが出来名。＃２ｔ＋ｌのＰＨの接続が変則的である
のは、情報Ｉ　（Ｘ）　＝　ｅｒｋ−８＋　Ｉｋ−２＋
・・・。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

１）ＳＹＮＤＲＯＭＥ　　：第１３図 ２）　　ＧＣＤ　　　　　　：第２７図３）、ＥＶＡＬ
ＵＡＴＥ　　：第３６図４）ＣＯＲＲＥＣＴ　　　：第
３８図 ５）ＥＲＡＳＵＲＥ　Ｉ・　：第５０図６）ＥＲＡＳＵ
ＲＥＩＩ　　　　：第５３図これは第４１図の復号器に
ＥＲＡＳＵＲＥ　ＩとＥＲＡＳＵＲＥ　ＩＩを加えたも
のであるが、処理速度は変わらず、全体のシステムで必
要なＰＥの数は次のようになる＋（２ｔ）　＋　（２ｔ
＋１）　＋　（４ｔ）　＋　１　＋　（２ｔ）　＋　（
２ｔ）１＝　（１２ｔ＋３）＊１０００１００Ｏまた消
失訂正を行わない場合、第４１図の復号器に第５７図の
符号器を加える必要がある。このとき全体のシステムに
必要なＩ’Ｅの数は第４１図の復号器で必要なＰＥの数
（７ｔ　＋　３）に（２ｔ＋１）を加えた（９ｔ＋４）
である（符号化と復号を同時に行わない場合には、ＰＥ
の接続、及びＰＨの制御を符号化と復号で可変にするこ
とによって第４１図の回路で回路規模を変えることなく
符号化復号器を実現できる）。

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

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

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

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

また、このＰＥを用いでＸゝ発生回路、及び除算器が第
６１図、第６２図のように構成できる（タイミングは第
６１図、第６２図に示す）６以上のように、このＰＥを
用いてガロア体上の種々の演算が可能であり、Ｒ３符号
の符号化復号器が効率的に構成できる。

〔発明の効果〕

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

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

【図面の簡単な説明】

第１図は本発明の実施例に係るプロセッシング・エレメ
ント（ＰＥ）の構成図 第２図はＰＨのセレクタの構成を示す間第３図はＰＥの
ガロア体上の乗算器の具体的構成を示す図 第４図はＰＨのガロア体上の加算器の具体的構成を示す
図 第５図は本発明による拡張されたＰＨの構成図第６図は
本発明による第１図を用いたシンドローム生成用ＰＥの
構成図 第７図は本発明による第１図を用いたシンドローム生成
用ＰＥの接続図 第８図は本発明による第１図を用いたシンドローム生成
用ＰＥのタイミング図 第９図は本発明による第１図を用いたシンドローム生成
用ＰＨの他の構成を示す図 第１０図は本発明による第１図を用いたシンドローム生
成用ＰＥの他の構成を示す接続図 第１１図は本発明による第１図を用いたシンドローム生
成用ＰＥの他の構成を示すタイミング図第１２図は本発
明によ乞第５図を用いたシンドローム生成用ＰＨの構成
図 第１３図は本発明による第５図を用いたシンドローム生
成用ＰＥの接続図 第１４図は本発明による第５図を用いたシンドローム生
成用ＰＨのタイミング図 第１５図はＧＣＤを求めるためのアルゴリズムを示す図 第１６図は本発明によるＰＲを用いたＧＣＤ生成の為の
アルゴリズムを示す図 第１７図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅの構成図 第１８図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅの接続図 第１９図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅのタイミング図 第２０図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｈのタイミング図 第２１図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｈの他の構成を示す図 第２２図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅの他の構成を示す接続図 第２３図は本発明による第１図を用いたＧＣＤ生成用Ｐ
Ｅの他の構成を示すタイミング図第２４図は本発明によ
る第１図を用いたＧＣＤ生成用ＰＥの他の構成を示すタ
イミング図第２５図はＧＣＤ生成の例を示す画 筆２６図は本発明による第５図を用いたＧＣＤ生成用Ｐ
Ｈの構成図 第２７図は本発明による第５図を用いたＧＣＤ生成用Ｐ
Ｅの接続図 第２８図は本発明による第５図を用いたＧＣＤ生成用Ｐ
Ｅの他の構成を示す図 第２９図、第３０図は本発明による第５図を用いたＧＣ
Ｄ生成用ＰＥの他の構成を示す接続図第３１図は５ｔａ
ｔｅ生成回路ブロック図第３２図は本発明による第１図
を用いた誤り評価用ＰＥの構成図 第３３図は本発明による第１図を用いた誤り評価用ＰＥ
の接続図 第３４図は本発明による第１図を用いた誤り評価用ＰＥ
のタイミング図 第３５図は本発明による第５図を用いた誤り評価用ＰＥ
の構成図 第３６図は本発明による第５図を用いた誤り評価用ＰＨ
の接続図 第３７図は本発明による第５図を用いた誤り評価用ＰＥ
のタイミング図 第３８図は本発明による第１図を用いた誤り訂正実行用
ＰＥの構成図 第３９図は本発明による第１図を用いたα’−（α８）
１発生用ＰＥの構成図 第４０図は本発明による第１図を用いたα’−（αＱ＋
発生用ＰＥのタイミング図 第４１図は本発明による誤り訂正復号器のシステム構成
図 第４２図は本発明による第１図を用いた消失位置多項式
生成用ＰＨの構成図 第４３図は本発明による第１図を用いた消失位置多項式
生成用ＰＨの接続図 第４４図は本発明による第１図を用いた消失位置多項式
生成用ＰＨのタイミング図 第４５図は本発明による乗算用ＰＨの構成図第４６図は
本発明による乗算用ＰＥの接続図第４７図は本発明によ
る第１図を用いた乗算用ＰＥのタイミング図 第４８図は従来の乗算回路の構成を示す図第４９図は本
発明による第５図を用いた消失位置多項式生成用ＰＥの
構成図 第５０図は本発明による第５図を用いた消失位置多項式
生成用ＰＨの接続図 第５１図は本発明による第５図を用いた消失位置多項式
生成用ＰＥのタイミング図 第５２図は本発明による第５図を用いた乗算用ＰＨの構
成図 第５３図は本発明による第５図を用いた乗算用ＰＥの接
続図 第５４図は本発明による第５図を用いた乗算用ＰＨのタ
イミング図 第５５図は従来の符号化回路 第５６図は本発明による第１図を用いた符号化用１’Ｅ
の構成図 第５７図は本発明による第１図を用いた符号化用ＰＥの
接続図 第５８図は本発明による第１図を用いた符号化用ＰＥの
タイミング図 第５９図は本発明による消失誤り訂正符号化復号器のシ
ステム構成図 第６０図は本発明による第１図を用いた高速積和演算算
器を示す図 第６１図は本発明による第１図を用いたＸ２″発生器を
示す図 第６２図は本発明による第１図を用いた除算器を示す図 ○　・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・乗算器、■　・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・加算器、第７　叉 ２　　Ｓｔ 第９７ ・・１１ 第１４７ 第１１：）図（・灯）ｄω 第１ろはコ（ｅ）：ノｄグ 第２１区 Ｎ　　　　　　　　Ｎ１　−　〜　　＋ＩＮ　　　　　
　　　〜　’−Ｎ　　　り一　　　く　　ラ　＜（ｂ９
Ｇ、（ラ　【　５　　（も４　　−　Ｑ　　　×　　　
ψ　　　Ｘ　り寸−Ｌ 第２７凶 ｃＫｉ　　ｆ 第４０図 男４１間 Ｃに↑　↑ Ｑ　　　　　　　　　　　　　η・Ｙｔ　ＹＩ＃Ｙ！　
　１　　　　°　　　　　　　　　　　　　　　　’ｇ
ｘ＊（ｔ＋ｚ＋ｔａ）５１．２　　　　　　　　　　　
　　　２　　　　０　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　ｈｙ−（７，ｚ−７，ン
１　　　　　　　　　　　　　　”Ｇ＝ｉＹ＋ヨ？Ｉ　
　　　Ｏ％（ｔ）”入ｘ−に７Ｑ　　　　　　　　　　
　　刈＝［五に四５２賞ＥＣ］＝コ（］［＝　　　　り
山Ｚ中１１　入ズ第４４図 Ｃに　↑　↑ ３　　　ＥコＣ蚕＝■ヨ【＝ ２ｔ　　　彰８コ＝■＝ 躬４７図 。４，１　　嶌５３図 口〕麗■二二二 唱５４図 ｖ３ン ｃＫｔ　　を 第４７図

Claims (1)

【特許請求の範囲】
1. （１）多入力多出力または、多入力−出力のセレクタ回
   路と、そのセレクタ回路の出力を少なくとも一方の入力
   にもつガロア体上の乗算器と、その乗算器出力を加算す
   るガロア体上の加算器と、その加算器出力及び前記セレ
   クタ回路の出力を蓄えるレジスタから構成された演算回
   路を複数同型に接続することによって処理能力を増大さ
   せ、 多項式Ａ、Ｂを入力して、Ａ、Ｂの最大公約多項式ＧＣ
   Ｄ〔Ａ、Ｂ〕を生成することを特徴とする最大公約多項
   式生成回路。