JP2556495B2 - 符号処理装置 - Google Patents

Description

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

本発明は、BCH符号の符号化復号において、シンドロ
ーム生成、GCD（最大公約数）生成、誤り訂正及び消失
誤り訂正を行うための方法に関する。

特に、次の演算を行うための方法に関する。

１） ｙ＝r_n-1・x^n-1＋r_n-2・x^n-2＋……＋r₁・ｘ＋r₀ ２） ｙ＝GCD（A,B） ただし、ｙは多項式A,Bの最大公約多項式 ３） ｙ＝Ａ・Ｂ ただし、 Ａ＝a_n・xⁿ＋a_n-1・x^n-1＋a₁・ｘ＋a₀ Ｂ＝b_n・xⁿ＋b_n-1・x^n-1＋b₁・ｘ＋b₀ ４） ｙ＝A mod B 〔従来技術とその問題点〕 近年、メモリーシステムを始めとする、各種デイジタ
ルシステムの信頼性向上の対策として誤り検出・誤り訂
正符号（以下、単に誤り訂正符号という）の適用が浸透
してきている。

この誤り訂正符号には、対象とするシステムに応じた
種々の物があるが、最も代表的なものは巡回符号と呼ば
れる線形符号の１クラスである。これには、ランダム誤
り訂正に適したBCH符号、バースト誤り訂正に適したフ
アイヤー符号、更にBCH符号の１種であり、バイト誤り
訂正に適したReed−Solomon符号（以下、RS符号）等が
含まれる。なかでも、RS符号は、同一の符号長と訂正能
力を持つ線形符号の中で、最も冗長度を低く出来るとい
う特徴を持つ、実用上非常に重要な符号であり、衛生通
信，磁気デイスク，コンパクトデイスク（以下、CDと呼
ぶ）等に広く利用されている。

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

そこで本出願人が先に出願した「BCH符号化復号方
式」（昭和61年12月22日出願）ではVLSIアーキテクチヤ
の特徴を生かし、次のことを実現した。

１）高信頼性（大能力） ２）高速性 ３）内部構造の規則性 ４）大集積化 これによって、10−20Mwps＝80−160Mbps以上の処理
速度を持つRS符号化復号器が実現出来ることを示した。
また、訂正能力に対して同じ構成のPEを１次関数的に増
やしていくことによって任意の高信頼性を得られる構成
にした。これは衛生通信等、高信頼性と高速性が求めら
れているシステムには非常に有効である。また、復号処
理の中心である誤り位置多項式と誤り数値多項式を求め
る処理を10−20Mlps（codelength/sec）で行うことも出
来るので高速処理には非常に有効な方法である。

しかし、CDまたは磁気デイスクなどで用いられている
データの転送レートは10Mbps以下であることが多く、ハ
ード容量の小型化が求められており、その点については
なお問題があった。

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

以上の点に鑑み本発明は、本出願人が先に出願した上
記「BCH符号化復号方式」に示したRS符号化復号器のア
ーキテクチヤの特徴を生かしたながら２）の高速性の条
件を犠牲にすることによって４）の条件を小型化で達成
出来るアーキテクチヤを提案する。

〔実施例〕

以下、図面に基づいて本発明の実施例について説明す
る。

前述したRS符号化復号器のアーキテクチヤはシストリ
ツク・アーキテクチヤの考え方を適用したものである。
シストリツク・アーキテクチヤの特徴は、１つの処理が
同一のPEの同一のネツトワークによって処理されること
である。これは全てのプロセツシング・エレメント（P
E）で行われる処理が同一であり、その入出力関係も同
一であることを示している。従って１度の処理を１つの
PEで行った後、次のPEに処理結果を送らずにメモリ（レ
ジスタ）部に蓄えておき自分自身にフイードバツクする
ことによって、PEの数を増やさずに処理することが出来
る。そこで、今回の基本となるPEを第１図のように定め
る。第１図において、１−４は第36図と同じであるが、
５−７のレジスタがｍ段のレジスタ列またはメモリ部と
なっている。回路規模はGF（2⁸）を考えた場合、１のセ
レクタを第37図の構成で約50ゲート、2,3の乗算器を第3
8図の構成で１つを約300ゲート、４の加算器を第39図の
構成で約50ゲート、５−７のレジスタ１つを約50ゲート
で計算する。

また１つのPEに注目した場合、前アーキテクチヤでは
１度の処理を行い処理結果を出力した後、そのPEは次の
入力を受け取ることが出来るので1PEの処理速度を最大
に生かした高速処理が可能であるが、処理結果を次のPE
に送らず自分自身にフイードバツクする場合、次の入力
を受け取ることが出来ないので外部的にみた場合１つの
PEへのデータの転送レートは遅くなる。但し、PE自体の
処理速度は１−４からなるPEの演算部で決定され、その
構成は変わらないので10−20Mhzである。ここでは、後
の都合のために1PEの処理速度は16Mhzとする。

以下、このPEを基本型としてステツプ１−４の処理を
実現するが、小型化を目的とするために各々の処理にお
いて不必要な部品は削り、各々の処理においてPEを最適
化していく。

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

RS符号は、非二元BCH符号（Bose−Chavdhuri−Hocque
nghen code）の特別な場合であり、有限体（以下、GFと
略す。）GE（ｑ）の元で構成される。ここでは、ｑはGF
（ｑ）の元の数である。このｑを用いると、RS符号を特
徴づける各種パラメータが以下のように定義される。

・符号長:n（一符号中のシンボル数） ｎ≦ｑ−１ （２−１） ・情報シンボル性:k（一符号中の情報シンボル数） ・検査シンボル数:n−ｋ（一符号中の検査シンボル数） ｎ−ｋ＝dmin−１ （２−２） ・訂正能力:t（一符号中の訂正できるシンボ数） （［ｘ］ガウス記号..xを越えない最大の整数） ここではdminは最小距離（ハミング距離）と呼ばれる
ものである。

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

例えば、符号化したいｋ個の情報シンボルを Ｉ＝（i₀,i₁,…,i_k-1） （２−10） とする時、これは次のように多項式で表現される。

Ｉ（ｘ）＝i₀＋i₁x＋i₁x²＋…＋i_k-2x^k-2＋i_k-1x
^k-1 （２−11） 同様に付加される（ｎ−ｋ）個の検査シンボル Ｃ＝（c₀,c₁,…,c_n-k-1） （２−12） は、 Ｃ（ｘ）＝c₀＋c₁x＋c₂x²＋…c_n-k-1・x^n-k-1 （２−1
3） 更に、これらをまとめた符号語Ｆ Ｆ＝（f₀,f₁,f₂,…f_n-1） （２−14） ＝（c₀,c₁…c_n-k-1,i₀,i₁,i₂,…i_k-1） （２−15） は、 Ｆ（ｘ）＝f₀＋f₁x＋f₂x²＋…f_n-2x^n-2＋f_n-1x^n-1（２
−16） と多項式表現される。

ところで符号語多項式Ｆ（ｘ）はそれを生成した生成
多項式Ｇ（ｘ）で割り切る事ができる。ところが、（２
−17）式（次頁参照）の生成多項式は、α，α²,…α
^n-kという根を持つから、符号語多項式Ｆ（ｘ）はこの
根を代入すると、次式が成立する。

Ｆ（α^ｉ）＝０（ｉ＝1,2,…・,n−ｋ） （２−21） この（２−21）式を行列表現すると次のようになる
（F^TはＦの転置行列）。

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

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

GF（2^m）（m:正整数）上で定義された符号長ｎ＝2^m−
１のRS符号について考えると、シンボルはｍビット２進
数で表わされ、演算はGF（2^m）上で行われる。また生成
多項式には（２−17）式を用い、符号の最小距離は簡単
の為dmin＝2t＋１と置く事にする。

ｇ（ｘ）＝（ｘ−α）（ｘ−α^２）…（ｘ−α^n-k）
（２−17） ただし、αは有限体GF（2^m）上の原始元 さて、このようなRS符号の復号手順は、一般的なBCH
符号の場合と同様、次のような４つのステツプに分けら
れる。

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

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

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

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

ステツプ１） シンドローム計算 まず、 送信された符号語をF:F＝（f₀,f₁,…f_n-1） 生じた誤りをＥ :E＝（e₀,e₁,…e_n-1） 受信された受信語をR:R＝（r₀,r₁,…r_n-1） ＝Ｆ＋Ｅ ＝（f₀＋e₀,f₁＋e₁,…f_n-1＋e_n-1） とすると、受信語の多項式表現Ｒ（ｘ）は次のようにな
る。

Ｒ（ｘ）＝Ｆ（ｘ）＋Ｅ（ｘ） ＝（f₀＋e₀）＋（f₁＋e₁）ｘ＋…・ ＋（f_n-1＋e_n-1）x^n-1 （２−23） ところが、符号多項式Ｆ（ｘ）に生成多項式Ｇ（ｘ）
（（２−17）式）の根α^ｉ（ｉ＝1,…,n−ｋ）を代入す
ると（Ｆ（α^１）＝０）が成立するから、受信語多項式
Ｒ（ｘ）に同様にαｉ（ｉ＝1,…,n−ｋ）を代入すると Ｒ（α^ｉ）＝Ｆ（α^ｉ）＋Ｅ（α^ｉ）＝０＋Ｅ（α^ｉ） ＝Ｅ（α^ｉ） （２−24） のように、誤りＥだけで決まる値が求まる。

これをシンドロームと呼び、改めて Ｓ＝（s₀,s₁,…,s_n-k-1） （２−25） siR（αⁱ⁺¹）＝Ｅ（αⁱ⁺¹）（ｉ＝0,1,…,_n-k-1） （２
−26） と定義する。このシンドロームは誤りに関するすべての
情報（誤りの位置と大きさ）を含んでいる。

（シンドロームは誤りがなければ０であるので、誤りの
有無を検出できる。）シンドローム（（２−25），（２
−26）式を行列表現すると次のようになる。

Ｓ＝Ｈ・R^T（R^T:Rの転置行列） （２−28） ステツプ２） 誤り位置多項式と誤り評価多項式の算出 ステツプ２では、ステツプ１の計算結果のシンドロー
ムを利用して誤り位置多項式と誤り評価多項式の算出を
行う。まず、ここでは誤りＥ＝（e₀,e₁…e_n-1）の非零
の元の数、すなわち誤りの個数をｌ（ｌ≦ｔ）とおく。
また、誤りの生じている位置をju（ｕ＝1,2…ｌ）（ju
＝0,1…ｎ−１）とし、位置juにおける誤りをe_juとす
る。更に（２−２），（２−３）式を ｎ−ｋ＝dmin−１＝2t （２−30） とおく。すると、（２−26）式のシンドローム及びシン
ドローム多項式は、次のように表わされる。

また、新たに とおくと、次式が得られる。

Ｓ（ｘ）＝［Ｓ_∞（ｘ）］mod x^2t （２−35） さて、ここで誤り位置多項式σ（ｘ）を次のように定
義する。この多項式は、受信語中の誤り位置ju（ｕ＝1,
2,……,l）（ju＝0,1……ｎ−１）に対応するGF（2^m）
の元α^-juを根とする多項式である。

次に、以上述べたσ（ｘ）、Ｓ_∞（ｘ）に対し誤り評
価多項式ω（ｘ）を次のように定義する。

すると、（２−34），（２−35），（２−37）式よ
り、次式が成立する。

σ（ｘ）・Ｓ（ｘ）＝［ω（ｘ）］modx^2t （２−38） 従って適当な多項式Ａ（ｘ）を用いてσ（ｘ）,S
（ｘ），ω（ｘ）の関係が次のように表わされる。

Ａ（ｘ）・x^2t＋σ（ｘ）・Ｓ（ｘ）＝ω（ｘ）（２−3
9） ところで、誤りの個数ｌは（ｌ≦ｔ）としているか
ら、ω（ｘ）とσ（ｘ）は degω（ｘ）＜degσ（ｘ）≦ｔ （２−40） を満たす。さらにω（ｘ）とσ（ｘ）は互いに素（最大
公約（GCD）多項式が定数）であるから（２−39），
（２−40）式を満たすω（ｘ）とσ（ｘ）は定係数の違
いを除いて一意的に定まる。以上よりω（ｘ）とσ
（ｘ）はx^2tとＳ（ｘ）の最大公約（GCD）多項式を求め
るユークリツドの互除法の過程で求め得る。ここで、ユ
ークリツドの互除法を利用した最大公約（GCD）多項式
の算出方法について簡単に述べる。まず、２つの多項式
ＡとＢの最大公約多項式をGCD［A,B］と表わすことにす
る。又、このＡとＢに対し次のような多項式と ・degA≧dagBの場合 ＝Ａ−［Ａ・B^-1］・Ｂ （２−41） ＝Ｂ （２−42） ・degA≧dagBの場合 ＝Ａ （２−43） ＝Ｂ−［Ｂ・A^-1］・Ａ （２−44） （［Ｘ・Y^-1］：多項式Ｘを多項式Ｙで割った商） を定義すると、GCD［Ａ・Ｂ］とGCD［，］は、次式
を満たす。

GCD［A,B］＝GCD［，］ （２−45） 従って、上述のととを改めてA,Bとおき、各々の
次数degA,degBの大小関係に応じて（２−41），（２−4
2）式もしくは（２−43），（２−44）式の変換を行う
といった操作を繰返し実行して、ＡとＢのどちらが零多
項式になった時、もう一方の非零多項式がＡとＢの最大
公約多項式として得られる。なお、多項式ＡとＢの最大
公約多項式を求める事は、次のような多項式ＣとＤを求
める事と変りない。なお、degは次数のことである。

GCD［A,B］＝Ｃ・Ａ＋Ｄ・Ｂ （２−46） すると、上記繰り返しステツプを実行して、次数がｉ
＝degA≧degBと表わされる多項式ＡとＢの最大公約多項
式を求める過程で、次式を満足する多項式C,D,Wを求め
る事ができる。

この様な多項式を求める問題を拡張GCD問題と呼ぶ。
従って、誤り位置多項式σ（ｘ）と誤り評価多項式ω
（ｘ）は、（２−47）式において、多項式Ａをx^2t、多
項式ＢをＳ（ｘ）とおいた場合の拡張GCD問題を解く事
により求まる。

基本アルゴリズム まず前述したように、σ（ｘ）とω（ｘ）の導出アル
ゴリズムは拡張GCD問題に帰着できる。すなわち、x^2tを
多項式A₀、シンドローム多項式Ｓ（ｘ）（（２−32）
式）を多項式B₀とおいた時（degA₀＝2t,degB₀＝2t−
１）、GCD［A₀,B₀］を求める途中で を満たす多項式D,Wが求まれば、Ｄが誤り位置多項式σ
（ｘ）、Ｗが誤り評価多項式ω（ｘ）を各々表わしてい
る。このようなσ（ｘ）とω（ｘ）は、定係数の違いを
除いて一意的に定まることがわかっている。従って、A₀
とB₀に対して次のような 多項式A,B,U,V,L,Mを定義し その初期値を Ｕ＝Ｍ＝1;L＝Ｖ＝0;（Ａ＝A₀,B＝B₀）とおいて第40
図の繰返しステツプを実行していき、degA（degB）＜ｔ
となった時にＡ（Ｂ）がω（ｘ）、Ｌ（Ｍ）がσ（ｘ）
として各々求まる。

なお、第40図の方法では、多項式Ｂの最高次係数αと
多項式Ａの最高次係数βを各々A,Bにたがいちがいに乗
ずる事により、繰返しステツプおけるGF上の除算を省略
している。（（２−41），（２−43）式参照）このよう
にしても、σ（ｘ）とω（ｘ）の値に本質的な問題は生
じない。

第40図について説明する。まず、ステツプ１において
Ｕ＝Ｍ＝1,L＝Ｖ＝0,A＝A₀,B＝B₀とおいて、初期値を設
定する。ステツプ２においてdegAdegBの判定を行い、
ステツプ３において多項式A,Bの最高次係数β，αを各
々A,Bにたがいちがいに乗じ、式（２−41），（２−4
3）の繰返しステツプにおけるGF上の除算を省略してい
る。

ステツプ４においてdegA,degBが所定の次数より小さ
くなった場合、ステツプ5,6に進み、ω（ｘ）＝A,σ
（ｘ）＝L,ω（ｘ）＝B,σ（ｘ）＝Ｍを算出する。

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

ｉ） degA,degB≧ｔかつdegA≧degB…“reduceA" ii） degA,degB≧ｔかつdegA≧degB…“reduceB" iii） degA＜ｔもしくはdegB＜ｔ…“nop" ステツプ３）誤り位置と誤りの値の推定 ステツプ３では、ステツプ２で得らた誤り位置多項式
σ（ｘ）と誤り評価多項式ω（ｘ）から、誤り位置と誤
り値の推定を行う。まず、受信語Ｒ＝（r₀,r₁,…r_n-i）
中のシンボルの位置ｉ＝0,1……ｎ−１に応じたGF
（2^m）の元α^-iを誤り位置多項式σ（ｘ）に逐次代入す
る。この時、（２−36）式よりσ（a^-i）＝０が成立す
るならば、ｉが誤り位置juに対し、α^-i＝α^-i＝α^-ju
が成立している事がわかる。（ju＝0,1…ｎ−1,u＝1,2
…1,1≦ｔ）また、そのようなα^-i＝α^-juに対する誤り
評価多項式ω（ｘ）の値は次のようになる。

更に、σ′（ｘ）をσ（ｘ）の微分とすると、 が成立する。従って（２−48）式と（２−49）式より誤
り位置juにおける誤りの位置e_juは次式より求められ
る。

前述したように、復号のステツプ３）では、ステツプ
２）で得られた誤り位置多項式σ（ｘ），誤り評価多項
式ω（ｘ）ならびにσ（ｘ）の微分σ′（ｘ）という３
つの多項式に、そのRS符号が定義されるGF（2^m）の元α
^-j（ｊ＝ｎ−1,…2,1,0）を逐次代入してその値を求め
る計算が必要となる。（ここでは受信シンボルが受信語
多項式の高次の項から入力される。すなわちrjがｊ＝ｎ
−1,…,2,1,0の順で入力されるとする。従って、ステツ
プ３）についての説明では、α^-j（ｊ＝ｎ−1,…,2,1,
0）の代入の順が逆となる事に注意しなければならな
い。）ここで具体的に必要な計算は単に多項式に変数を
代入し、その値を求めるだけであるから第40図と同様の
アルゴリズムを利用できる。例えば、ｔ次多項式ｆ
（ｘ）の計算は次のように展開される。

ｆ（ｘ）＝ftx^t＋ft−1x^t-1＋…＋f₁x＋f₀ ＝｛…〔（ftx＋ft−１）ｘ ＋ft−２〕ｘ＋…＋f₁｝ｘ＋f₀ 但し、シンドローム計算では各セルが代入すべきｘを
あらかじめ持っている。

ステツプ４） 誤り訂正の実行 （２−９）式より、誤りの生じている位置juにおける
受信シンボルr_juは、本来の符号語のシンボルf_juとの誤
りの大きさe_juから次のように表わされる。

f_ju＝r_ju−e_ju （２−51） 従ってステツプ４では、ステツプ３の実行結果σ（α
^-i）＝０が成立した位置ｉ（ｉ＝0,1,…ｎ−１）におい
て、受信シンボルr_iから を引く（GF（2^m）上） f_i＝r_i＝e_i （２−53） 事により、位置ｉにおける誤り訂正を実行する。

（シンドローム生成部） 次に、本発明の実施例に係るBCH符号化復号器の構成
及び作用について構成単位毎に詳述する。

ステツプ１ではシリアルに送られてくる受信系列Ｒ＝
（r_n-1,r_n-2…,r₁,r₀）からのステツプ２で必要なシン
ドローム多項式の係数（S_2t-1,S_2t-2…,S₁,S₀）をシリ
アルに出力させる必要がある。具体的なシンドローム多
項式の係数の計算は、次の繰り返しアルゴリズムを用い
る。

S_j-1＝（…（（r_n-1 ^＊α^ｊ＋r_n-2）^＊α^ｊ ＋r_n-3）^＊α^ｊ＋…＋r₁）^＊α^ｊ＋r₀ また、上式を次のように分解する。

Z₀＝０ Z_i＝Z_i-1 ^＊α^ｊ＋r_n-i （ｉ＝1,…,n） S_j-1＝Z_n 回路を小型化するために、第41図のPEにおいて意味の
ない３の乗算器と５のレジスタを削る。これによって、
PEの演算部は400ゲートとなる。ここで、第42図の受信
シンボルの動きに注目すると、１つの受信シンボルr_n-i
は値を変えることなく＃１のPEから＃2tのPEまで送ら
れ、加算されるZ_i-1＊α^ｊの項が変化するだけである。
そこで前章ではシンドローム生成部のPEをα^ｊ（ｊ＝1,
…,2t）毎に割り付けたが、ここではα^ｊ入力からα^ｊ
（ｊ−1,…,2t）の値が順次入力され、ｊ＝１からｍ迄
を１周期として周期的にα^ｊ（ｊ＝1,…,m）の入力が繰
り返されるようにする。そして受信系列の入力であるr_i
は１つの受信シンボルの値が１周期の間保持されながら
受信シンボルr_n-i（ｉ＝1,…,n）が入力されるようにす
る。これによって、レジスタ７も削ることが出来、r_i入
力を直接加算器に入力する。但し、レジスタ６はZ_iの演
算結果を＃１のPEから＃ｍのPEの分まで１周期分保存さ
せる必要があるので、ｍ段必要である。ｍ＝2tの場合の
信号の流れを第３図に示す。

最初（ｉ＝１）、セレクタの選択信号S1,2はr_n-1が入
力されているときのみS1,2＝10となり、Ｘ出力からはＣ
入力である０が出力されｉ＝１のときの演算結果である
Z₁＝r_n-iが2t段のレジスタに順次入力される。それ以後
（ｉ＝2,…,n）、S1,2＝00とすることによってセレクタ
のＸ出力はＡ入力を選択し、前演算の結果であるZ_i-1が
順次Ｘ出力から出力され基本クロツクCKに毎α^ｊ（ｊ＝
1,…,2t）と乗算され、r_n-iと加算されることによってZ
_i＝Z_i-1＊α^ｊ＋r_n-i（ｊ＝1,…,2t）が演算され、順位
レジスタに入力される。従って、2t段のレジスタはS_i-1
（ｊ＝1,…,2t）の演算の途中結果を一時保存して再び
フイードバツクさせるためのメモリ部となっている。こ
れによって、2t個のPEの処理を１つのPEで実現できる
が、レジスタ段数分だけ入力r_n-iを保持する必要がある
ので、処理速度は（16/2t）Mwpsとなる。

ここでは、回路の小型化のために乗算器３は削り、５
と７のレジスタ列も省いている。従って、第２図のPEの
回路規模は（400＋ｍ＊50）ゲートとなり、処理速度は
（16/m）Mwpsとなる。ｍはレジスタの段数であるが、全
処理を1PEで行わせる場合ｍ＝2tとなる。１例として、
訂正能力ｔ＝８とした場合1PEの回路規模は120ゲートと
なり、処理速度は1Mhz＝8Mbpsとなる。

また、全処理を1PEで構成せず、複数のPEに分けて構
成する場合、第２図のPEを第４図のように接続する。こ
のとき、受信シンボルを1PE毎に１周期単位で遅らせる
ためにCK2（１周期毎のクロツク）で制御されるレジス
タが必要である。PEの数をｋとすると全体の処理は（2t
/k）に分散されるので、1PEに必要なレジスタの段数は
ｍ＝（2t/k）となる。従って、第４図の回路規模は（2t
/m）＊（400k＋ｍ＊50）ゲートとなる。第５図に２つの
PEで構成した場合の信号の流れを示す。この場合α^ｊの
割付けは、＃１のPEがα^ｊ（ｊ＝1,…,t）、＃２のPEが
α^ｊ（ｊ＝ｔ＋1,…,2t）となる。この場合、レジスタ
段数ｍ＝ｔであるので処理速度は2Mhz＝16Mbpsとなり、
回路規模は800＊２＝1600ゲートとなる。

ｍ＝１としたとき必要なPEの数はｋ＝2tととなり、CK
2＝CKとなるのでCK2で制御されるレジスタはレジスタ７
と等価になり、処理速度も16Mwpsとなる。従って、これ
は第42図の無駄な回路を省いた構成になっている。ま
た、セレクタのＢ入力が空いていることを利用して、前
PEのＳ（ｘ）出力を入力することによって最後のPEから
シンドローム多項式の係数（S_2t-1,S_2t-2,…,S₁,S₀）を
Ｓ′（ｘ）としてシリアルに出力することができる。

（GCD生成部（誤り位置多項式及び誤り数値多項式生
成）） ステツプ２の誤り位置多項式σ（ｘ）と誤り数値多項
式ω（ｘ）の導出アルゴリズムは、拡張GCD問題に帰着
できる。第43図の回路に於いて、各々のPEは１度のProc
ess処理が終るとその出力を次のPEに渡し、自らは次の
入力を受け取り2t回のProcess処理を行った。その2t回
のProcess処理結果を次のPEに出力せず、自らのレジス
タに蓄えシンドローム多項式Ｓ（ｘ）とx^2tの１連の入
力が終った後、レジスタに蓄えた結果をフイードバツク
して、１つのPEで全処理を行うことを考える。

そのときのPEの構成を第６図に示す。第43図と同様に
Stateを設定する回路とα，βを保持するためのCK2とCL
で制御されるレジスタと、a_i-1,b_i-1を実現するために
レジスタ列5,7の後にもう１段レジスタを挿入する必要
がある。従って、PE内のレジスタ段数をｍとしたとき、
1PEにおいて必要な回路規模（State設定の回路はコント
ロール部であるので除く）は、（700＋（3m＋４）＊5
0）ゲートとなる。（700は演算部の回路規模であり、
（3m＋４）はレジスタの総数である） １つのPEで全処理を行う場合には、ｍ＝2t（処理結果
の多項式の次数は2t以上にならないため）となり、第40
図に示す例についてＡ（Ｂ）を求める場合の信号の流れ
の初めの部分を第７図に示し、Ｌ（Ｍ）を求める場合の
信号の流れの初めの部分を第８図に示す。セレクタ選択
信号の切り替え、及びCK2の制御は挿入したレジスタも
考慮にいれて、基本クロツクCKが（ｍ＋１）毎に行うこ
とによって第44図，第45図の動作が逐次的に１つのPEで
行われることが分かる。

なお、Ａ（Ｂ）を求めるときとＬ（Ｍ）を求めるとき
でProcess部を独立に２つ持つか、１つを２回用いなけ
ればならない。以下、１つのProcess処理について評価
を行うが、１つのProcess部を２回用いる場合は処理速
度を半分にし、２つのProcess部を独立に持つ場合には
必要なPEの数を２倍にすればよい。

ここでは、シンドローム多項式Ｓ（ｘ）（またはＭ＝
１）、及びx^2t（またはＬ＝０）の入力時のみセレクタ
選択信号S1,2＝11としてX,Y出力にD,E入力が出力される
セレクタを用いる。（表にセレクタ出力の組合せを示
す）また、Ａ（Ｂ）とＬ（Ｍ）を１つのProcess部で処
理する場合、第９図に示すPEを用いて、第10図のように
S1..4を制御することによりＡ＝x^2t,B＝Ｓ（ｘ）,L＝0,
M＝１の入力を行うことも出来る。（セレクタ選択信号
の組合せを表に示す）但し、第43図の＃2t＋２のPEはセ
レクタによる信号選択のみ意味があるので、第９図のPE
のＷ出力を利用しPEによる処理回数を2t＋１回とする。
（また第６図のPEでは別にセレクタを設けることによっ
て処理回路を2t＋１回に減らす。また、＃2t＋２の信号
選択はdegB＜ｔの場合S4＝１とすることによってＢ入力
がＷから出力される。） 従って、ここでの処理速度は第43図の処理をレジスタ
段数ｍ毎に行うので（16/2t/m）Mlpsとなる。１例とし
て、ｔ＝８としてｍ＝2tとしたときの回路規模は3300ゲ
ート、処理速度は1/16Mlps＝n/16Mwpsとなる。

また全処理を1PEで構成せず、複数のPEに分けて構成
する場合、第６図のPEを第11図のように接続する。この
とき、係数データを各PEで循環させながら動作させるた
めに、最後のPEの出力を最初にPEにフイードバツクさせ
る必要がある。PEの数をｋとすると全体の処理は（2t/
k）に分散されるので、1PEに必要なレジスタの段数はｍ
＝（2t/k）となる。従って、第11図の回路規模は（2t/
m）＊（700＋（3m＋４）＊50）のゲートとなる。

第12図に２つのPEで構成した場合の信号の流れを示
す。この場合、レジスタの段数ｍ＝ｔであるので処理速
度は2/16Mlpsとなり、回路規模は1950＊２＝3900ゲート
となる。

ｍ＝１としたとき必要なPEの数はｋ＝2tとなり、処理
速度は16Mlpsとなる。この構成では最後のPEから最初の
PEへフイードバツクを行うので、2t＋１回の処理回数に
対してPEの数は2tで済む。シストリツクな接続にするた
めにPEの数を処理回数に対応させて2t＋１とすると、信
号をフイードバツクする必要がなくなるので第43図とし
て同じ構成になる。（この場合＃2t＋２のPEはセレクタ
となる） （誤り位置、及び誤り数値生成部） ステツプ３もステツプ１と同様に次の繰り返しアルゴ
リズム、及び分解式を用いることが出来る。

ｆ＝（ｘ）＝f_t-1＊x^t-1＋f_t-2＊x^t-2…＋f₁＊ｘ＋f₀ ＝（…（（f_t-1＊ｘ＋f_t-2）＊ｘ＋f_t-3）＊ ｘ＋…＋f₁）＊ｘ＋f₀） Z₀＝０ Z_i＝Z_i-1＊ｘ＋f_t-i（ｊ＝1,…,t） ｆ（ｘ）＝Z_t また、回路を小型化するためにステツプ１と同様に乗
算器３とレジスタ５を削る。また第46図の回路において
α^-1（ｉ＝ｎ−1,…,0）の入力はステツプ１と同様に＃
１のPEから＃ｔのPEまで値を変えること無く送られるだ
けである。そこでｊ＝１からｍまでを１周期としてα^-1
の１つの値が保持されるようにα^-1（ｉ＝ｎ−1,…,0）
を入力する。

またft−ｉの係数はステツプ１と同様に１周期毎にf
_t-i（ｊ＝1,…,m）の入力が繰り返さなければならな
い。ステツプ２のGCD生成部からの出力を考えた場合、
係数f_t-i（ｊ＝1,…,t）は１度出力されるが、周期的に
繰り返し出力されない。そこで、選択信号S1,2によって
表のような組合せで出力されるセレクタとｍ段のレジス
タ列７を用いて、第13図のようにPEを構成し、第14図の
ように信号を送る。GCD生成部から係数_t-i（ｊ＝1,…,
t）が出力されているときはセレクタ選択信号をS1,2＝1
1（f_t-1が入力されているときのみ）からS1,2＝01とす
ることによって、Ｙ出力から係数f_t-i（ｊ＝1,…,t）が
順次出力され、レジスタ列７に入力される。

その出力をＢ入力フイードバツクしてセレクタ選択信
号をS1,2＝10（f_t-1が入力されているときのみ）からS
1,1＝00とすることによって、再びＹ出力から係数f_t-i
（ｊ＝1,…,t）が出力され、レジスタ列７に入力され
る。以後その動作を繰り返すことによって係数f_t-i（ｊ
＝1,…,t）の周期的な入力が実現される。これによって
ステツプ１と同様にｍ個のPEの処理を１つのPEで実現で
きるが、レジスタ段数分だけ入力α^-1を保持する必要が
あるので、処理速度は（16/m）Mwpsとなる。（ｍはレジ
スタ段数） また1PEに必要な回路規模は（400＋（ｍ＋１）＊50）
ゲートとなる。

ｍはレジスタ段数であるが、全処理を1PEで行わせる
場合ｍ＝ｔとなる。但し、ω（ｘ），σ（ｘ），σ′
（ｘ）の処理のためにPEは３セツト必要である。１例と
して、訂正能力ｔ＝８とした場合回路規模は３＊850＝2
550ゲートとなり、処理速度は2Mwpsとなる。

また全処理を1PEで構成せず、複数のPEに分けて構成
する場合、第13図のPEを第15図のように接続する。この
とき、α^-1を1PE毎に１周期単位で遅らせるためにCK2
（１周期毎のクロツク）で制御されるレジスタが必要で
ある。

PEの数をｋとすると全体の処理は（t/k）に分散され
るので、1PEに必要なレジスタ段数はｍ＝（t/k）とな
る。従って、第15図の回路規模は（t/m）＊（400＋（ｍ
＋１）＊50）ゲートとなる。第16図に２つのPEで構成し
た場合の信号の流れを示す。この場合、ｔ＝８であるの
でｍ＝（t/2）＝４として回路規模は３＊２＊650＝3900
ゲートとなり、処理速度は4Mwpsとなる。

ｍ＝１としたとき必要なPEの数はｋ＝ｔとなり、CK2
＝CKとなるのでCK2で制御されるレジスタはレジスタ５
と等価になり、f_t-iの割り付け部をのぞいて第46図と同
じ構成になり、処理速度も16Mwpsとなる。

また、第17図にσ（ｘ），とσ′（ｘ）を１つのPEで
処理する場合PEを示し、第18図に信号の流れを示す。ス
テツプ３は１周期がｔであるので1PEを２度用いること
が出来、またσ′（ｘ）の係数がσ（ｘ）の係数を用い
ることを利用する。これによって、ステツプ３が２セツ
トのPEで実現でき、第18図に示すようにσ（ｘ），σ′
（ｘ）の動作は2t毎となり、ω（ｘ）の出力も第19図の
ようにすることによって2t毎に動作させることが出来
る。ここでは出力の組合せが表のようになるセレクタを
用いてＹ出力が０となるときだけセレクタ選択信号をS
1..3＝001とすればよい。この場合、処理速度は2Mwps/2
＝1Mwpsとなり、必要なPEのセツトも２セツトとなるの
で回路規模は２＊850＝1700ゲートとなる。

（消失位置多項式生成部） ここでは、ステツプ１からのシンドローム多項式の係
数出力Ｓ（ｘ）を受けて消失訂正を行うために必要なＳ
（ｘ）＊λ（ｘ）を生成する。

まず、消失位置多項式λ（ｘ）を生成することを考え
る。

λ（ｘ）＝（１−Y₁＊ｘ）＊（１−Y₂＊ｘ）…（１−Y₅
＊ｘ） であり、前章と同様にλ（ｘ）を次のように分解する。

Z₀＝１ Z_i＝（１−Y_i＊ｘ）＊Z_i-1 ＝Y_i＊Z_i-1＊ｘ＋Z_i-1（ｉ＝1,…,s） λ（ｘ）＝Z₅ まず、回路を小型化するために乗算器３及びレジスタ
６を削る。ここでは処理クロツク数またはレジスタ段数
に対応させる。またZ_i-1入力を１クロツク遅らせるため
のレジスタを１つ用意する。従って、PEの構成は第22図
のようになり、1PEに必要な回路規模は（400＋（ｍ＋
１）＊50）のゲートとなる。（ｍはレジスタ段数）第23
図に信号の流れを示す。

1PE内のレジスタ段数ｍ（ここではｍ＝2tとする）を
１周期としてY_iの１つの値が保持されるようにY_i（ｉ＝
1,…,s）を入力する。最初、（Y₁入力時）セレクタ選択
信号をS1,2＝11としＸにＤ入力Z₀＝１、ＹにＣ入力０を
入力し演算結果のY₁を次のクロツクでレジスタ列６に入
力する。以降、S1,2＝10としてＸにＣ入力０、ＹにZ₀を
１クロツク遅らせたＡ入力を出力し、演算結果Z₀＝１を
次のクロツクでレジスタ列６に入力する。その次のクロ
ツク以降は演算結果が０であるので０がレジスタ列６に
入力される。１周期後、（Y₂入力時）レジスタ列６から
前演算結果Z₁＝Y₁＊ｘ＋１（次数ｘは信号の順序を表
す）が出力されるので、S1,2＝01としＸに前演算結果の
最高次係数Y1をＡ入力から、ＹにＣ入力の０を出力し演
算結果のY₁＊Y₂をクロツクでレジスタ列６に入力する。
以降、S1,2＝00としてＸにZ₁の次の係数１をＡ入力か
ら、Ｙに１クロツク遅らせたZ₁の最高次係数Y₁をＢ入力
から選択し、演算結果Y₁＋Y₂を次のクロツクでレジスタ
列６に入力する。このときＸからは０、ＹからはZ₁の次
の係数１が出力され、次のクロツクで演算結果１がレジ
スタ列６に入力され、以降演算結果が０であるので０が
入力される。Y₂入力時の動作をY₃入力以降も繰り返すこ
とによってY₅入力後にレジスタ列６からλ（ｘ）が高次
の係数から出力される。

ｓ≦2tであるので、Y_i＝０（ｉ＝ｓ＋1,…,2t）を入
力すればよい。

従って、処理速度は（16/2t/m）Mlpsとなる。１例と
して、ｔ＝８として全処理を1PEで行わせる場合、回路
規模は1250ゲートとなり、処理速度は1/16Mlpsとなる。

また、全処理を1PEで構成せず、複数のPEに分けて構
成する場合、第22図のPEを第24図のように接続する。こ
のときY_iの値を2tクロツクの間保持するために各PE毎に
Y_iを設定するレジスタが必要である。PEの数をｋとする
と全体の処理は（2t/k）に分散されるので、1PEに必要
なレジスタ段数はｍ＝（2t/k）となる。従って、第24図
の回路規模は（2t/m）＊（400＋（ｍ＋１）＊50）ゲー
トとなる。第25図に２つのPEで構成した場合の信号の流
れを示す。このとき回路規模は850＊２＝1700ゲートと
なり、処理速度は2/16Mlpsとなる。

ｍ＝１としたとき必要なPEの数はｋ＝2tとなり、処理
速度も（16/2t）Mlpsとなり、第47図の構成と等価にな
る。

次に、乗算回路Ｓ（ｘ）＊λ（ｘ）を考える。乗算Ｃ
（ｘ）＝Ａ（ｘ）＊Ｂ（ｘ）の計算を前章と同様に次の
ように分解する。

Ａ（ｘ）＝a_m-1＊x^m-1＋a_m-2＊x^m-2＋…＋a₁＊ｘ＋a₀と
したとき Ｃ（ｘ）＝a_m-1＊Ｂ（ｘ）＊x^m-1 ＋a_m-2＊Ｂ（ｘ）＊x^m-2 ＋…＋a₁＊Ｂ（ｘ）＊ｘ＋a₀B（ｘ） となるので Z₀＝０ Z_i＝Z_i-1＊ｘ＋Ｂ（ｘ）＊a_m-i（ｊ＝1,…,m） Ｃ（ｘ）＝Z_m 従って、Ｂ（ｘ）が入力されている間a_m-iを保持しZ_i
＝Z_i-1＊ｘ＋８（ｘ）＊a_m-iを演算した後レジスタ列６
に挿入し、１周期後その演算結果をZ_i-1としてフイード
バツクすればよい。しかし、入力Ｓ（ｘ）及びλ（ｘ）
はステツプ１のシンドローム生成部、及び前述の誤り位
置多項式生成部から１度基本クロツクCKの転送レートで
入力されるだけである。そこで、レジスタ列5,7を用い
て繰り返し入力を実現し、CK2で制御されるレジスタを
用いて設定値を保持する。また、レジスタ列７からのＢ
（ｘ）出力はレジスタ列６からのZ_i-1出力より１クロツ
ク遅れてフイードバツクされる必要があるのでPEの構成
は第26図のようになる。Ｂ（ｘ）＝Ｓ（ｘ）,a_m-i＝λ
_2t-i（ｉ＝0,…,2t）とした場合の信号の流れを第27図
に示す。（1PE内のレジスタ段数ｍ−１＝2t−１とす
る） 先ず、セレクタ選択信号S1,2＝01としてλ（ｘ）をＦ
入力からＷ出力を通してレジスタ列５に入力する。その
ときλ（ｘ）の最高次係数λ_2tをCK2によって制御され
るレジスタに蓄え、乗算器３の入力に設定する。またＳ
（ｘ）をλ（ｘ）より１クロツク遅らせてＥに入力し、
Ｙに出力させレジスタ列７に入力する。その間ＸはＣ入
力０を出力する。これによってλ_2t＊Ｓ（ｘ）が演算さ
れ、レジスタ列６に入力される。このときλ（ｘ）＊Ｓ
（ｘ）の最高次係数λ_2t＊S_2t-1は演算されているのでC
KDによってラツチされ出力される。１周期をｍ（ここで
はｍ＝2t）として、１周期後セレクタ選択信号S1,2＝00
とする。Ｂからはｍ段のレジスタ列７によってフイード
バツクされたＳ（ｘ）が入力され、再びＹからレジスタ
列７に入力される。Ｄからはｍ段のレジスタ列５によっ
て最高次係数がずれたλ（ｘ）がフイードバツクされＷ
に出力される。従って、CK2ではλ（ｘ）の次の係数λ
_2t-1が蓄えられ乗算器３に設定される。Ａからはｍ−１
段のレジスタ列６によって全演算結果の最高次係数がず
れたものがフイードバツクされＢ（ｘ）＝Ｓ（ｘ）に対
し１次係数がずれた形で入力される。これによって、Z_i
＝Z_i-1＊ｘ＋Ｂ（ｘ）＊a_m-iが演算されたレジスタ列６
に入力される。以降CK2にλ_０が入力され演算が終了す
るまで同様に演算が行われる。但し、答えとなる演算結
果は入力にフイードバツクするときずれてしまうので、
演算される度にCKDによって出力される。またλ（ｘ）
の係数も入力にフイードバツクするときずれてしまうの
で１次づつ係数が減ってしまう。ずらされた係数は必要
ないのでフイードバツクされるときセレクタ選択信号を
S1,2＝10とすることによってX,Wに０を出力する。

また演算終了後レジスタ列６には答えの演算結果が残
っているので同様の動作を繰り返すことによりレジスタ
列６の結果が１係数づつずらされてCKDから出力され
る。

1PEに必要な回路規模はPE内のレジスタ段数をｍ−１
とした場合（400＋3m＊50）ゲート）となる。また、処
理速度は演算終了から出力終了まで考える必要があるの
で（16/4t/m）/2となる。全処理を1PEで行う場合PE内の
レジスタ段数ｍ＝2tとなり、１例として訂正能力ｔ＝８
とした場合、回路規模は2800ゲートとなり、、処理速度
は（1/32）Mlpsとなる。

また、全処理を1PEで構成せず、複数のPEに分けて構
成する場合、第26図のPEを第28図のように接続する。こ
のときa_m-iの値を2tクロツクの間保持するために各PE毎
にa_m-iを設定するレジスタが必要である。PEの数をｋと
すると全体の処理は（2t/k）に分散されるので、1PEに
必要なレジスタ段数はｍ＝（2t/k）となる。従って、第
28図の回路規模は（2t/m）＊（400＋3m＊50）ゲートと
なる。第29図に２つのPEの構成した場合の信号の流れを
示す。このとき回路規模1600＊２＝3200ゲートとなり、
処理速度は（1/16）Mlpsとなる。

ｍ＝１としたとき必要なPEの数はｋ＝2tとなり、処理
速度も（1/2）Mlpsとなる。

（符号器） 符号化は情報Ｉ（ｘ）＝（I_k-1,I_K-2,…,I₀）からパ
リテイＰ（ｘ）＝（P₂t,P_2t-1,…,P₁）を生成する。符
号化とは生成多項式を ｇ（ｘ） ＝g_m＊x^m＋g_m-1＊x^m-1＋g_m-2＊x^m-2…＋g₁＊ｘ＋g₀ とすると Ｐ（ｘ）＝Ｉ（ｘ）＊^m mod g（ｘ） を求めることであり、 ｇ′（ｘ）＝g_m-1＊x^m-1＋g_m-2＊x^m-2…＋g₁＊ｘ＋g₀ とすると この式は次のように分解される。

Z₀＝Ｉ（ｘ） Z_i＝g_m＊Ｚ′_i-1＋Z_m＊ｇ′（ｘ） （ｉ＝1,…,k） Ｐ（ｘ）＝Z_k ここでZ_mは多項式Z_i-1の最高次係数とし、Ｚ′_i-1はZ
_i-1から最高次係数を除いた多項式とする。Z_mをｇ′
（ｘ）入力中保持し、Z_m＊ｇ′（ｘ）の演算を行う。こ
こでは、g_m＝１とし、第30図のようにPEを構成する。

g_iからｇ′（ｘ）の係数g_m-1からg₀がｍを１周期とし
て周期的に乗算器２に入力される。またCK2（１周期毎
のクロツク）とCLによって制御されるレジスタによって
Z_mを保持し、Ａに入力する。Ｚ′_i-1は前演算結果Z_i-1
を周期に対して１クロツク早く出力することによって実
現する。従ってレジスタ列６の段数をｍ−１とし、Ｂ入
力にフイードバツクする。情報Ｉ（ｘ）はＣから入力さ
れ１周期の間１つの値が保持されるように入力する。

第31図に符号化の様子を示す。先ずｉ＝１のときを考
える。初期状態としてCK2で制御されるレジスタに情報
シンボルI_k-1が保持され、Ｃ入力からは情報I_k-m-1が入
力され、レジスタ列６に情報シンボルがI_k-2からI_k-m迄
蓄えられている場合を考える。演算部ではＡ入力からの
I_k-1にｇ′（ｘ）を乗じて、Ｂ入力からのI_k-2〜I_k-m、
及びＣ入力からのI_k-m-1と加算して、レジスタ別６に入
力する。（Ｙ出力に対するB,C入力の切り替えはセレク
タ選択信号S1,2によって行われ、Ｂ入力の時S1,2＝00、
Ｃ入力の時S1,2＝01とする） その演算結果をZ₁の高次の項からＩ′_k-1＝I_k-1＊g
_m-i＋I_k-i-1とする。（ｊ＝1,…,m）ｉ＝２以降もＩ′
_k-iに対しての同様の処理をｉ＝ｋまで行うことにより
符号化が行われる。

また、初期状態を実現するために第32図（ｍ＝４の場
合）のようにする。情報入力はI_k-1〜I₀迄１周期の間値
が保持されるように入力する。先ずセレクタ選択信号S
1,2＝01とし、最初の受信シンボルI_k-1をＣから入力し
Ｙに出力する。Ａ入力へはCK2で制御されるレジスタのC
Lによって０を入力し、Ｘに出力させる。PE内のレジス
タ段数がｍ−１であるので、Ｂ入力には周期の１クロツ
ク前にI_k-1がフイードバツクされる。そのときS1,2＝00
とし１クロツク分だけＢ入力をＹに出力しS1,2の設定を
元に戻す。このときＣからは次の受信シンボルI_k-2が入
力されるのでレジスタ列６にはI_k-1を１クロツク分入力
した後、I_k-2を入力することになる。I_k-2入力中、レジ
スタ列６からのフイードバツク入力とのずれは２クロツ
ク分になるので、それに合わせてセレクタ選択信号をS
1,2＝00とする。そのとき、I_k-1の後にI_k-2が１クロツ
ク選択される。以上の動作をI_k-m迄行うことによってレ
ジスタ列６に_Ik-1〜I_k-mが蓄えられていく。I_k-m-1を入
力するとき、I_k-1はレジスタ列６からはみ出すがCK2で
制御されるレジスタにラッチされることによって初期状
態が実現される。

また、演算終了後の情報Ｉ（ｘ）とパリテイＰ（ｘ）
の切り替えもセレクタのＺ出力を利用して第33図のよう
にして行う。上述の符号化演算中、Ｚは１周期毎の情報
シンボルの入力であるＣ入力を出力する。演算終了後パ
リテイ出力をレジスタ列６を通して循環させるが、PE内
のレジスタ段数がｍ−１であるのでCK2制御されるレジ
スタはパリテイの１循環毎に１次ずれたパリテイを出力
しＡ入力にフイードバツクする。そのときＺはＡ入力を
選択しパリテイ１周期毎に出力する。

従って、このときの回路規模、及び処理速度は（400
＋ｍ＊50）ゲート、及び（16/m）Mwpsである。全処理を
1PEで構成する場合、ｍ＝2tとなる。１例として訂正能
力ｔ＝８とした場合、1PEの回路規模は1200ゲートとな
り、処理速度は1Mwps＝8Mbpsとなる。

また、全処理を1PEで構成せず、複数のPEに分けて構
成する場合、第30図のPEを第34図のように接続する。PE
の数をｋとすると全体の処理は（2t/k）に分散されるの
で、1PEに必要なレジスタの段数は、ｍ＝（2t/k）とな
る。従って、第34図の回路規模は（2t/m）＊（400＋ｍ
＊50）ゲートとなる。第35図に２つのPEで構成した場合
の信号の流れを示す。この場合、レジスタ段数はｍ＝ｔ
であるので処理速度は2Mwps＝16Mbpsとなり、回路規模
は800＊２＝1600ゲートとなる。

ｍ＝１としたとき必要なPEの数はｋ＝2tとなるが、＃
ｋのPEから＃１のPEへのフイードバツク、及びＩ（ｘ）
の同時入力は変わらないので、このアーキテクチヤにお
いても符号器はやはりシストリツクな構成にならない。

（誤り訂正実行部、及びシステム） ステツプ３のｆ（α^-i）出力は第17図のPEを用いた場
合2t毎に1CK分だけ出力されるが、σ′（α^-i）とσ
（α^-i），ω（α^-i）ではタイミングが半周期ずれるの
でσ′（α^-i）はCK2（2t毎のクロツク）で制御される
レジスタでラツチさせ、σ（σ^-i），ω（α^-i）はCK
2′（CK2を半周期ずらしたクロツク）でラツチし、更に
CK2で制御されるレジスタでラツチすることによって第4
8図と同様なステツプ４の誤り訂正が実現される。（タ
イミングは第21図に示す。但し、GCD生成部においては
Ａ（Ｂ）,L（Ｍ）の処理を１つのProcess部を２回用い
ている場合は、ω（ｘ）の係数が先に送られてくるので
バツフアを介する必要がある）ステツプ４の誤り訂正の
実行部を最適化すると第20図のようになる。ω
（α^-i），σ（α^-i,σ′（α^-i）の出力のタイミング
を合わせた後の動作は前章と同じである。従って、ステ
ツプ４に於いて必要な回路規模はバツフアと逆数生成用
ROMを除いて、450＋５＊50＝700ゲートとなる。ステツ
プ４の誤り訂正実行部はシストリツクな構造を持たない
ので、レジスタ段数を増加しても回路の小型化を行うこ
とは出来ない。従って、その状況に応じて最適な回路の
簡単化を行えばよい。またα^-i（ｉ＝ｎ−1,…,0）発生
回路も同様である。

以上述べてきたように、RS符号の各復号ステツプは高
速性と引き替えに回路を小型化できる。第49図の復号器
に於いて１例として次の組合せにすることによって、各
PEの制御をセレクタ選択信号とCK2のみで全体のシステ
ムを動かすことが出来る。

ステツプ１）SYNDROME:第２図 ステツプ２）GCD:第６図 ステツプ３）EVALUATE:第13図 ステツプ４）CORRECT:第20図 符号化復号器をシステムとして考えた場合、第50図の
消失誤り訂正のための復号器を１例として、次の組合せ
にすることによって小型化された符号化復号器として実
現できる。

１）SYNDROME:第２図 ２）GCD:第６図 ３）EVALUATE:第13図 ４）CORRECT:第20図 ５）ERASURE I:第22図 ６）ERASURE II:第26図 これはステツプ４で示した復号器にERASURE ＩとERA
SURE IIを加えたものである。また、ステツプ４で示し
た復号器に第30図の符号器を加えて符号化復号器とする
ことも出来る。（符号化と復号を同時に行わない場合に
は、PEの接続、及びPEの制御を符号化と復号で可変にす
ることによって第49図の回路で回路規模を変えることな
く符号変化復号器を実現できる） 各々の処理における回路規模（ゲート単位）、及び処
理速度（Mwps単位）は前述したように次の通りである。
（wps＝word/sec） １） （2t/m）＊（400＋ｍ＊50）,16/m ２） （2t/m）＊（700＋（3m＋４）＊50）,n＊（16/2t
/m） ３） ２＊（2t/m）＊（400＋（ｍ＋１）＊50）,16/m ４） 700 ５） （2t/m）＊（400＋（ｍ＋１）＊50）,n＊（16/2t
/m） ６） （2t/m）＊（400＊（3m＋２）＊50）,n＊（16/4
t）/m） ７）ENCODE:第30図；（2t/m）＊（400＋ｍ＊50）,16/m １例としてRS復号器がｔ＝８としたとき次のような回
路規模、及び処理速度で実現できる。（符号長ｎ≧4tで
あり、また1PEで実現するためにｍ＝2tとする） 1200＋3300＋2500＋700＝7700gate 1Mwps＝8Mbps またｔ＝２の場合は 600＋1500＋1300＋700＋3100gate 4Mwps＝32Mbps となる。

図１において、PEの基本構成を示したが、GF（2^m）の
回路規模をＭゲートとすると、GF（2^2m）の回路規模は
約4Mゲートとなる。しかし、１ワードの構成がｍビツト
から2mビツトとなることを考えると、1PE当りの処理速
度は10〜20Mwps（ワード／秒）であるのでｍ・（10〜2
0）Mbpsから2m・（10〜20）Mbpsとなり、２倍になる。
そこで実質的な処理速度をbpsとすると、同一処理速度
によるPEの構成は図１のPEのレジスタ段数を２段とすれ
ばよい。すると、必要なPEの数は、ｋ＝（2t/m）、ｍ＝
２であるのでｔ個となる。従って、ガロア体の構成をGF
（2^M）からGF（2^2M）とした場合、、同一処理速度での
回路規模の増加は２倍となる。一般的にガロア体の構成
をGF（2^m）からGF（2^a-m）とした時、回路規模の増加
は、ａ倍となる。

〔発明の効果〕

以上説明したように、本発明によれば、有限体上で定
義された誤り訂正符号を処理する符号処理装置に、外部
よりの複数の入力の一部を入力し、選択信号に応じて少
なくとも２つを選択して出力するセレクタと、該セレク
タの出力の１つと、前記複数の入力の１つとを乗ずる１
つ以上の乗算器と、１つの該乗算の出力と、他の１つの
前記乗算器または前記セレクタの出力、あるいは前記複
数の入力の１つとを加算する加算器と、該加算器の出
力、または前記セレクタの１つ以上の出力を、一旦保持
した後、外部へ出力する複数段のレジスタとを具え、該
レジスタの出力を前記外部よりの入力の１つとしてフィ
ードバック入力する処理要素を１つ、または直列に接続
して複数有する処理回路を複数具備し、前記処理回路の
１つに、受信語及び前記有限体の原始元のべきを入力し
て、シンドローム多項式を生成し、前記処理回路の他の
１つに前記シンドローム多項式を入力して、誤り位置多
項式及び誤り評価多項式を生成し、前記処理回路の他の
１つに、前記誤り位置多項式及び該多項式を微分した多
項式、前記誤り評価多項式のいずれかと、前記原始元の
べきとを入力して、各多項式に前記原始元のべきを代入
する演算を実行し、該演算の結果に基づいて、前記受信
語の誤りの位置及び値を推定して訂正するようにし、各
処理回路中の各処理要素に、複数段のレジスタを設け、
出力をフィードバック入力して処理することにより、処
理要素の数を減らし、回路規模を小さくすることができ
るという効果がある。また、必要に応じて、処理要素を
直列に接続して処理を高速化し、処理速度と回路規模の
バランスを考慮して、適切な装置を実現することができ
る。

【図面の簡単な説明】

第１図は本発明による小型化プロセツシング・エレメン
ト（PE）の構成図 第２図は本発明による第１図のPEを最適化したシンドロ
ーム生成回路の説明図 第３図は本発明による第２図のPEのタイミング図 第４図は本発明による第２図のPEの接続図 第５図は本発明による第２図のPEを２つ用いたシンドロ
ーム生成回路のタイミング図 第６図は本発明による第１図のPEを用いたGCD生成回路
の説明図 第７図は本発明による第１図のPEを用いたGCD生成回路
のタイミング図 第８図は本発明による第１図のPEを用いたGCD生成回路
のタイミング図 第９図は本発明による第１図のPEを用いたGCD生成回路
の説明図 第10図は第９図の入力タイミング図 第11図は本発明による第１図のPEを最適化したGCD生成
回路の説明図 第12図は本発明による第11図のPEを２つ用いたGCD生成
回路のタイミング図 第13図は本発明による第１図のPEを最適化した誤り評価
回路の説明図 第14図は本発明による第13図のPEのタイミング図 第15図は本発明による第13図のPEの接続図 第16図は本発明による第13図のPEを２つ用いた場合のタ
イミング図 第17図は本発明による第13図のPEを最適化した誤り評価
回路の説明図 第18図は本発明による第17図のタイミング図 第19図は本発明による第17図のタイミング図 第20図は本発明による最適化された誤り訂正実行部 第21図は本発明による第20図のタイミング図 第22図は本発明による第１図のPEを最適化した消失位置
多項式生成回路の説明図 第23図は本発明による第22図のPEのタイミング図 第24図は本発明による第22図のPEの接続図 第25図は本発明による第22図のPEを２つ用いた場合のタ
イミング図 第26図は本発明による第１図のPEを最適化した乗算回路
の説明図 第27図は本発明による第26図のPEのタイミング図 第28図は本発明による第26図のPEの接続図 第29図は本発明による第26図のPEを２つ用いた場合のタ
イミング図 第30図は本発明による第１図のPEを最適化した符号器の
説明図 第31図は本発明による第30図のPEのタイミング図（処理
中） 第32図は本発明による第30図のPEのタイミング図（初期
入力時） 第33図は本発明による第30図のPEのタイミング図（数値
出力時） 第34図は本発明による第30図のPEの接続図 第35図は本発明によるPEを２つ用いた場合のタイミング
図 第36図は従来のプロセツシング・エレメント（PE）の構
成図 第37図は従来のプロセツシング・エレメント（PE）のセ
レクタの構成図 第38図は従来のプロセツシング・エレメント（PE）の乗
算器の構成図 第39図は従来のプロセツシング・エレメント（PE）の加
算器の構成図 第40図はGCDを求めるためのアルゴリズムを説明するた
めの図 第41図は従来のシンドローム生成用PEを説明するための
図 第42図は従来のシンドローム生成用PEの接続図 第43図は従来のGCD生成用PEの接続図 第44図は従来のGCD生成用PEの動作のタイミングを示す
図 第45図は従来のGCD生成用PEの動作タイミングを示す図 第46図は従来の誤り評価用PEの接続図 第47図は従来の消失位置多項式生成用PEの接続図 第48図は従来の誤り訂正実行用PEを説明するための図 第49図は従来の誤り訂正復号器をシステムを構成図 第50図は消失誤り訂正復号器の例を示す図 ……加算器

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭63−157525（ＪＰ，Ａ) 特開 昭63−164624（ＪＰ，Ａ) 特開 昭63−156430（ＪＰ，Ａ) 電子通信学会技術研究報告，信学技報 Ｖｏｌ．86，Ｎｏ．301，Ｐ．15−22 （ＩＴ86−102，ＩＴ86−103)

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】有限体上で定義された誤り訂正符号を処理
   する符号処理装置であって、 外部よりの複数の入力の一部を入力し、選択信号に応じ
   て少なくとも２つを選択して出力するセレクタと、 該セレクタの出力の１つと、前記複数の入力の１つとを
   乗ずる１つ以上の乗算器と、 １つの該乗算器の出力と、他の１つの前記乗算器または
   前記セレクタの出力、あるいは前記複数の入力の１つと
   を加算する加算器と、 該加算器の出力、または前記セレクタの１つ以上の出力
   を、一旦保持した後、外部へ出力する複数段のレジスタ
   とを具え、該レジスタの出力を前記外部よりの入力の１
   つとしてフィードバック入力する処理要素を１つ、また
   は直列に接続して複数有する処理回路を複数具備し、 前記処理回路の１つに、受信語及び前記有限体の原始元
   のべきを入力して、シンドローム多項式を生成し、前記
   処理回路の他の１つに前記シンドローム多項式を入力し
   て、誤り位置多項式及び誤り評価多項式を生成し、前記
   処理回路の他の１つに、前記誤り位置多項式及び該多項
   式を微分した多項式、前記誤り評価多項式のいずれか
   と、前記原始元のべきとを入力して、各多項式に前記原
   始元のべきを代入する演算を実行し、該演算の結果に基
   づいて、前記受信語の誤りの位置及び値を推定して訂正
   することを特徴とする符号処理装置。
2. 【請求項２】前記処理回路の１つに、受信語を入力し
   て、消失位置多項式を生成し、前記処理回路の他の１つ
   に、前記消失位置多項式と前記シンドローム多項式とを
   入力し、積多項式を生成して、消失訂正を行うことを特
   徴とする特許請求の範囲第１項記載の符号処理装置。
3. 【請求項３】前記処理回路の１つに、情報と生成多項式
   を入力して、パリティを生成し、前記情報を符号化する
   ことを特徴とする特許請求の範囲第１項記載の符号処理
   装置。