JPS63164624A - シンドロ−ム生成回路 - Google Patents

Abstract

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

Description

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

本発明は、ＢＣＨ符号の符号化復号において、シンドロ
ーム生成を行う技術に関する。

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

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

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

これには、ランダム誤り訂正に適したＢＣＨ符号。

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

このＲ８符号の復号法には種々の物があり、２ないし３
程度の小さな訂正能力に対する復号器の装置化は比較的
容易である。しかし、高信頼性を得る為には、訂正能力
を大きくする必要がある。

その場、合、装置の規模及び制御が非常に複雑になり、
復号処理に掛かる計算時間も大きくなると言った問題が
生じる。この為、現在ＣＤではＣＩＲＣと呼ばれる一種
の２重符号化を用いているが、より高信頼性または高速
性が要求されるシステムでは問題がある。また、高信頼
性を淋るために光磁気ディスクなどではＬｏｎｇ　　Ｄ
ｉｓｔａｎｃｅ　　Ｃｏｄｅ（以下、ＬＤＣ）と呼ばれ
る多重誤り訂正符号が提案されているが、高速性の実現
が問題である。

衛星通信では、高信頼性と高速性の２つが要求されてい
るが、装置化を考えた場合、以上の２つの条件を満足さ
せることは非常に困難であった。

そこで本出願人が先に出願したｒＢＣＨ符号化復号方式
」（昭和６１年１２月２２日出願）テ１ｔＶＬｓＩアー
キテクチャの特徴を生かし、次のことを実現した。。

Ｉ）高信頼性（大能力） ２）高速性 ３）内部構造の規則性 ４）大集積化 これによって、１０−２０　Ｍ　ｗ　ｐ　ｓ　＝　８０
−１６０　Ｍ　ｂ　ｐ　ｓ以上の処理速度を持つＲ３符
号化復号器が実現出来ることを示した。また、訂正能力
に対して同じ構成のＰＥを１次関数的に増やしていくこ
とによって任意の高信頼性を得られる構成にした。これ
は衛星通信等、高信頼性と高速度性が求められるシステ
ムには非常に有効である。また、復号処理の中心である
誤り位置多項式と誤り数値多項式を求める処理を１０−
２０Ｍ］ｐｓ　（ｃｏｄｅｌｅｎｇｔｈ／５ｅｃ）で行
うことも出来るので高速処理には非常に有効な方法であ
る。

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

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

以上の点に鑑み、本発明は、本出願人が先に出願した上
記ｒＢＣ）（符号化復号方式」に示したＲ３符号化復号
器のアーキテクチャの特徴を生かしなから２）の高速性
の条件を犠牲にすることによって４）の条件を小型化で
達成出来るアーキテクチャを〔実施例〕 以下図面に基づいて本発明の実施例について説明する。

前述したＲ５符号化復号器のアーキテクチャはシストリ
ック・アーキテクチャの考え方を適用したものである。

シストリック・アーキテクチャの特徴は、１つの処理が
同一のＰＨの同一ネットワークによって処理されること
である。これは全てのプロセッシング・エレメント（Ｐ
Ｅ）で行われる処理が同一であり、その入出力関係も同
一であることを示している。従って１度の処理を１つの
ＰＥで行った後、次のＰＨに処理結果を送らずにメモリ
（レジスタ）部に蓄えておき自分自身にフィードバック
することによって、ＰＥの数を増やさずに処理すること
が出来る。そこで、今回の基本となるＰＥを第１図のよ
うに定める。第１図において、１−４は第３６図と同じ
であるが、５−７のレジスタがｍ段のレジスタ列または
メモリ部となっている。

回路規模はＧＦ（２’）を考えた場合、ｌのセレクタを
第３７図の構成で約５０ゲート、２，３の乗算器を第３
８図の構成で１つを約３００ゲート、４の加算論を第３
９図の構成で約５０ゲート、５−７のレジスタ１つを約
５０ゲートで計算する。

また１つのＰＥに注目した場合、前アーキテクチャでは
１度の処理を行い処理結果を出力した後、そのＰＥは次
の入力を受は取ることが出来るのでＩＰＥの処理速度を
最大に生かした高速処理が可能であるが、処理結果を次
のＰＥに送らず自分自身にフィードバックする場合、次
の入力を受は取ることが出来ないので外部的にみた場合
１つのＰＥへのデータの転送レートは遅（なる。但し、
ＰＥ自体の処理速度は１−４からなるＰＥの演算部で決
定され、その構成は変わらないので１０−２０　Ｍ　ｈ
　ｚである。ここでは、後の都合のためにＩＰＥの処理
速度は１６　Ｍ　ｈ　ｚとする。

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

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

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

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

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

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

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

１（Ｘ）＝ｉｏ＋ｉ１Ｘ＋ｉｌＸ”＋・”＋１ｌ−２Ｘ
ｋ−”＋ｊｋ−＋Ｘ’−’　　（２−１１）同様に付加
される（ｎ−ｋ）個の検査シンボルＣ＝　（ｃｏ、　ｃ
、、・・・＋　Ｃｎ−＊−＋　）　　　　　　　　（２
１２）は、 Ｃ（ｘ）　＝　Ｃｏ＋Ｃ１ｘ＋ｃｚ　ｘ”＋　−Ｃｎ−
ｍ−＋”Ｘ’−に−’　　　　（２−１３）更に、これ
らをまとめた符号語Ｆ Ｆ＝（ｆｏ、ｒｌ、　ｆ２＋・・・ｒ、、−、）（２−
１４）”（Ｃ１１＋　ＣＩ　・・’　Ｃｎ−に−１＋　
ｌ　Ｏ山＊　’ｘ　＋　・・・ｌｂ−＋　）　　　　　
（２１５）は、 Ｆ（ｘ）　＝　ｆｏ＋ｆ、　ｘ＋ｆｘ　ｘ”十・・−ｆ
ｌ、−、ｘ’−”＋ｆｌｌ−，ｘ”−’　　（２−１６
）はそれを生成した生成多項式Ｇ（ｘ）で割り切る事が
α、α２．・・・αｉという根を持つから、符号語多項
式Ｆ　（ｘ）はこの根を代入すると、次式が成立する。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ｓ　＝　Ｈ・Ｒ”　　（Ｒ”　：　Ｒの転置行列）（２
−２８）ステップ２　伸　１置　　エど　５・　　　エ
ル１且ステップ２では、ステップ１の計算結果のシンド
ロームを利用して誤り位置多項式と誤り評価多項式の算
出を行う。まず、ここでは誤りＥ　＝（ｅ　ｏ　＋　２
１・・ｅｎ−１）の非零の元の数、すなわち誤りの個数
を１（Ｉｌ≦ｔ）とおく。また、誤りの生じている位置
をｊｕ　（ｕ＝１゜２−・−１）　（ｊｕ＝０．１−・
−ｎ−１）とし、位置ｊｕにおける誤りをｅ、。とする
。更に（２−２）、　　（２−３）式をｎ−に−＝ｄｍ
ｉｎ−１＝２ｔ　　　　　　　　（２−３０）とおく。

すると、（２−２６）式のシンドローム及びシンドロー
ム多項式は、次のように表わされる。

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

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

ａ　　（ｘ）　＝　（１−ａ）’ｘ）　（１−ａ）２ｘ
）　＝−（１−α”ｘ）＝　ＦＴ　　（１−ａ”ｘ）ｍ
１ 次に、以上述べたσ（Ｘ）、Ｓ〜（Ｘ）に対し誤り評価
多項式ω（ｘ）を次のように定義する。

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

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

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

Ａ　（ｘ）・ｘ　２１＋σ（Ｘ）・Ｓ　（ｘ）　＝ω（
ｘ）　　　　　　（２−３９）ところで、誤りの個数ｌ
は（ｌ≦ｔ）としているから、ω（Ｘ）とび（ｘ）は ｄｅｇ　ω（ｘ）　＜　ｄｅｇ　ｖ　（ｘ）≦ｔ　　　
　　（２−４０）を満たす。さらにω（Ｘ）とび（ｘ）
は互いに素（最大公約（ＧＣＤ）多項式が定数）である
から（２−３９）、　　（２−４０）式を満たすω（ｘ
）とσ（ｘ）は定係数の違いを除いて一意的に定まる。

以上よりω（Ｘ）とａ　（ｘ）はｘ　２　ＬとＳ　（ｘ
）の最大公約（ＧＣＤ）多項式を求めるユークリッドの
互除法の過程で求め得る。ここで、ユークリッドの互除
法を利用した最大公約（ＧＣＤ）多項式の算出方法につ
いて簡単に述べる。まず、２つの多項式ＡとＢの最大公
約多項式をＧＣＤ　［Ａ、Ｂｌと表わすことにする。又
、このＡとＢに対し次のような多項式λとｎ ＊　ｄｅｇＡ≧ｄｅｇＢの場合λ＝　Ａ−［Ａ　−Ｂ’
−’コーＢ（２−４１）Ｂ＝Ｂ　　　　　　　　（２−
４２） ・ｄｅｇＡ≧ｄｅｇＢの場合λ＝Ａ（２−４３）Ｂ°＝
Ｂ−［Ｂ嚢Ａ−１］拳Ａ　　　　　　（２−４４）（［
Ｘ−Ｙ−’］：多項多項式子項式Ｙで割った商）を定義
すルト、ＧＣＤ　［Ａ、Ｂｌ　（！：ＧＣＤ　［λ、Ｂ
］ハ、次式を満たす。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

前述したように、復号のステップ３）では、ステップ２
）で得られた誤り位置多項式σ（Ｘ）、誤り評価多項式
ω＜ｘ＞ならびにσ（Ｘ）の微分σ′（Ｘ）という３つ
の多項式に、そのＲ３符号が定義されるＧＦ（２”）の
元ａ−’　（ｊ＝ｎ−１，・−・２，１．０）を逐次代
入してその値を求める計算が必要となる。（ここでは受
信シンボルが受信語多項式の高次の項から入力される。

すなわちｒｊがｊ＝＝ｎ−１，・・・、２，１．０の順
で入力されるとする。従って、ステップ３）についての
説明では、α月（ｊ＝ｎ−１，・・・、２，１．０）の
代入の順が逆となる事に注意しなければならない。）外
と同様のアルゴリズムを利用できる。例えば、を次多項
式ｆ　（ｘ）の計算は次のように展開される。

ｆ　（ｘ）　＝　ｆｔｘ’＋ｆｔ−１ｘ”＋・・・＋ｆ
　、ｘ＋ｆ、　　　　　　笹叫井。

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

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

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

ステップ１ではシリアルに送られて（る受信系列Ｒ”　
（ｒ　ｎ−１＋　ｒ　ｎ−２”・＋　ｒ　Ｉ　＋　ｒ　
Ｏ）からステップ２で必要なシンドローム多項式の係数
（Ｓ　２１−１　、　Ｓ　２１−２・・・。

Ｓ　１　＋　　Ｓ　ｏ　）をシリアルに出力させる必要
がある。

具体的なシンドローム多項式の係数の計算は、次の繰り
返しアルゴリズムを用いる。

ＳＩ−＋　＝（”’（ｂ、、−＋　＊（１’　＋　ｒｅ
−ｚ）　＊α’　＋　ｒｎ−ａ　）　＊α’　＋　・・
・＋　ｒｌ　）＊α’　＋　ｒ。

また、上式を次のように分解する。

２、＝０ Ｚｌ　　：Ｚｌ−１＊　　α’＋ｒ＋＋−＋　　　　　
　　　　　　　　（ｉ＝　１．−°−、ｎ）Ｓ、−１＝
　Ｚ。

回路を小型化するために、第４１図のＰＥにおいて意味
のない３の乗算器と５のレジスタを削る。これによって
、ＰＥの演算部は４００ゲートとなる。ここで、第４２
図の受信シンボルの動きに注目すると、１つの受信シン
ボルｒｎ−ｉは値を変えることなく＃ｌのＰＥから＃２
ｔのＰＥまで送られ、加算されるＺｉ−＋＊αノの項が
変化するだけである。そこで前章ではシンドローム生成
部のＰＥをα’　（ｊ＝１．・・・、２ｔ）毎に割り付
けたが、ここではα１人力からα’（Ｊ＝ｌｌ゛・・・
、２ｔ）の値が順次入力され、ｊ＝１からｍ迄を１周期
として周期的にα’（３＝”＋・・・、ｍ）の入力が繰
り返されるようにする。そして受信系列の入力であるｒ
ｌは１つの受信シンボルの値カ月周期の間保持されなが
ら受信シンボルｒ。−１（ｉ＝１．・・・ｒｎ）が入力
されるようにする。これによって、レジスタ７も削るこ
とが出来、ｒｌ入力を直接加算器に入力する。但し、レ
ジスタ６はＺｉの演算結果を＃ｌのＰＥから＃ｍのＰＥ
の分まで１周期分保存させる必要があるので、ｍ段必要
である。ｍ　＝　２　ｔの場合の信号の流れを第３図に
示す。

最初（ｉ＝１）、セレクタの選択信号Ｓｌ、　２はｒｎ
−１が入力されているときのみＳｌ、２＝１０となり、
Ｘ出力からはＣ入力であるＯが出力されｉ＝１のときの
演算結果であるＺＩ＝ｒｎ−＋が２を段のレジスタに順
次入力される。それ以後（ｉ　＝＝　２　、・・・、ｎ
）、Ｓｔ。

２墓００、とすることによってセレクタのＸ出力は六入
力を選択し、前演算の結果であるＺｌ−１が順次Ｘ出力
から出力され基本クロックＣＫ毎にα’（ｊ＝１゜・・
・、２ｔ）と乗算され、ｒｎ−ｉと加算されることによ
ってＺ＋＝Ｚ＋−＋＊α１＋「。−１（ｊ＝ｌｌ・・・
、２ｔ）が演算され、順次レジスタに入力される。従っ
て、２を段のレジスタはＳｔ−＋（ｊ＝１．・・・、２
ｔ）の演算の途中結果を一時保存して再びフィードバッ
クさせるためのメモリ部となっている。これによって、
２を個のＰＥの処理を１つのＰＥで実現できるが、レジ
スタ段数分だけ入力ｒｎ−１を保持する必要があるので
、処理速度は（１６／２ｔ）Ｍｗｐｓとなる。

ここでは、回路の小型化のために乗算器３は削り、５と
７のレジスタ列も省いている。従って、第２図のＰＨの
回路規模は（４００＋ｍ＊５０）ゲートとなり、処理速
度は（１６／ｍ）Ｍｗｐｓとなる。ｍはレジスタの段数
であるが、全処理をＩＰＥで行わせる場合ｍ＝２ｔとな
る。１例として、訂正能力ｔ＝８とした場合ＩＰＥの回
路規模は１２０ゲートとなり、処理速度はＩ　Ｍ　ｈ　
ｚ　＝　８　Ｍ　ｂ　ｐ　ｓとなる。

また、全処理をＩＰＥで構成せず、複数のＰＥに分けて
構成する場合、第２図のＰＥを第４図のように接続する
。このとき、受信シンボルをＩＰＥ毎に１周期単位で遅
らせるためにＣＫ２（１周期毎のクロック）で制御され
るレジスタが必要である。ＰＥの数をｋとすると全体の
処理は（２ｔ／ｋ）に分散されるので、ＩＰＥに必要な
レジスタの段数はｍ＝（２ｔ／ｋ）となる。従って、第
４図の回路規模は（２ｔ／　ｍ　）　＊　（４００＋　
ｍ　＊　５０　）ゲートとなる。第５図に２つのＰＥで
構成した場合の信号の流れを示す。

この場合αＪの割付は、＃１のＰＥがａＩ（ｊ＝１．・
・・。

ｔ）、＃２のＰＥがα’　（ｊ＝ｔ＋１．・・・、２ｔ
）となる。

この場合、レジスタ段数ｍ　＝　ｔであるので処理速度
は２　Ｍ　ｈ　ｚ　＝　１６　Ｍ　ｂ　ｐ　ｓとなり、
回路規模は８００　＊　２＝１６００ゲートとなる。

ｍ＝１としたとき必要なＰＥの数はに＝２ｔととなり、
ＣＫ２＝ＣＫとなるのでＣＫ２で制御されるレジスタは
レジスタ７と等価になり、処理速度も１６Ｍｗｐｓとな
る。従つて、これは第４２図の無駄な回路を省いた構成
になっている。また、セレクタのＢ入力が空りているこ
とを利用して、前ＰＨのＳ　（ｘ）出ノＪを入力するこ
とによって最後のＰＥからシンドローム多項式の係数（
Ｓ２１−１．　５２Ｌ−２，・＝、　Ｓ＋、　Ｓｏ）を
Ｓ’（ｘ）としてシリアルに出力することができる。

ＧＣＤ’ｒｒ、　＠ρ　胃　　エ　び；　　　　　ニス
テップ２の誤り位置多項式σ（ｘ）と誤り数値多項式ω
（Ｘ）の導出アルゴリズムは、拡張ＧＣＤ問題に帰着で
きる。第４３図の回路に於いて、各々のＰＥは１度のＰ
ｒｏｃｅｓｓ処理が終るとその出力を次のＰＥに渡し、
自らは次の入力を受は取り２を回のＰｒｏｃｅｓｓ処理
を行った。その２を回のＰｒｏｃｅｓｓ処理結果を次の
ＰＨに出力せず、自らのレジスタに蓄えシンドローム多
項式Ｓ　（ｘ）とＸ２Ｉの１連の入力が終った後、レジ
スタに蓄えた結果をフィードバックして、１つのＰＥで
全処理を行うことを考える。

そのときのＰＥの構成を第６図に示す。第４３図と同様
に５ｔａｔｅを設定する回路とα、βを保持するための
ＣＫ２とＣＬで制御されるレジスタと、ａＩ−１゜ｂ＋
−１を実現するためにレジスタ列５，７．の後にもう１
段レジスタを挿入する必要がある。従って、Ｐ°Ｅ内の
レジスタ段数をｍとしたとき、ＩＰＥにおいて必要な回
路規模（Ｓｔａｔｅ設定の回路はコントロール部である
ので除く）は、（７００＋　（３ｍ＋４）　＊５０３ゲ
ートとなる。（７００は演算部の回路規模であり、（３
ｍ＋４）はレジスタの総数である）１つのＰＥで全処理
を行う場合には、ｍ＝２ｔ（処理結果の多項式の次数は
２を以上にならないため）となり、第４０図に示す例に
ついてＡ　（Ｂ）を求める場合の信号の流れの初めの部
分を第７図に示し、Ｌ（Ｍ）を求める場合の信号の流れ
の初めの部分を第８図に示す。セレクタ選択信号の切り
替え、及びＣＫ２の制御は挿入したレジスタも考慮にい
れて、基本クロックＣＫが（ｍ　＋　１　）毎に行うこ
とによって第４４図、第４５図の動作が逐次的に１つの
ＰＥで行われることが分かる。

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

ここでは、シンドローム多項式Ｓ　（Ｘ）　（またはＭ
＝１）、及びＸ２′（またはＬ＝０）入力時のみセレク
タ選択信号Ｓｌ、２＝１１としてＸ、　Ｙ出力にり。

Ｅ入力が出力されるセレクタを用いる。（表にセレクタ
出力の組合せを示す）また、Ａ　（Ｂ）とＬ　（Ｍ）を
１つのＰｒｏｃｅｓｓ部で処理する場合、第９図に示す
ＰＥを用いて、第１Ｏ図のように５１．．４を制御する
ことによりＡ＝ｘ”、Ｂ＝Ｓ　（ｘ）、Ｌ＝０．Ｍ＝１
の入力を行うことも出来る。（セレクタ選択信号の組合
せを表に示す）但し、第４３図の＃２ｔ＋２のＰＥはセ
レクタによる信号選択のみ意味があるので、第９図のＰ
ＥのＷ出力を利用しＰＥによる処理回数を２ｔ＋１回と
する。（また第６図のＰＥでは別にセレクタを設けるこ
とによって処理回路を２ｔ＋１回に減らす。また、＃２
ｔ＋２の信号選択はｄｅｇＢ＜ｔの場合５４＝１とする
ことによってＢ入力がＷから構成される装置 従って、ここでの処理速度は第４３図の処理をし゛ジス
タ段数ｍ毎に行うので（１６／　２　ｔ　／　ｍ　）　
Ｍ　Ｉ　ｐ　ｓとなる。１例として、ｔ＝８としてｍ　
＝　２　ｔとしたときの回路規模は３３００ゲート、処
理速度は１７１６Ｍ１ｐｓ’＝ｎ／１６Ｍｗｐｓとなる
。

また全処理をＩＰＥで構成せず、複数のＰＥに分けて構
成する場合、第６図のＰＥを第１１図のように接続する
。このとき、係数データを各ＰＥで循環させながら動作
させるために、最後のＰＨの出力を最初のＰＥにフィー
ドバックさせる必要がある。ＰＥの数をｋとすると全体
の処理は（２ｔ／ｋ）に分散されるので、ＩＰＥに必要
なレジスタの段数はｍ＝（２ｔ／ｋ）となる。従って、
第１１図の回路規模は（２ｔ／ｍ）　＊　（７００＋　
（３ｍ＋４）　＋５０）ゲートとなる。

第１２図に２つのＰＥで構成した場合の信号の流れを示
す。この場合、レジスタの段数ｍ＝ｔであるので処理速
度は２　／　１６　Ｍ　ｌ　ｐ　ｓとなり、回路規模は
１９５０＊２＝３９００ゲートとなる。

ｍ＝１としたとき必要なＰＨの数はに＝２ｔとなり、処
理速μｓは１６　Ｍ　ｌ　ｐ　ｓとなる。この構成では
最後のＰＥから最初のＰＥヘフィードバックを行うので
、２ｔ＋１回の処理回数に対して１）Ｈの数は２ｔで済
む。

シストリックな接続にするためにＰＥの数を処理回数に
対応させて２ｔ＋１とすると、信号をフィードバックす
る必要がなくなるので第４３図と同じ構成になる。（こ
の場合＃２ｔ＋２のＰＥはセレクタとなる） モ　　　　　　び舌　　　　、　。

ステップ３もステップｌと同様に次の繰り返しアルゴリ
ズム、及び分解式を用いることが出来る。

ｆ　＝　（ｘ　）　＝　ｆ　Ｉ−＋　＊　ｘ’−’　＋
　ｆ　ｔ−２＊　ｘ’−２−＋　ｆ　Ｉ＊　ｘ　＋　ｆ
　。

＝（・・・（（ｆｔ−＋＊ｘ十ｆｔ−２）　＊ｘ＋ｆｔ
−３）　＊ｘ十・・・＋　ｆ　＋　）　＊　ｘ　＋　ｆ
　ｏ　）Ｚｏ＝Ｏ Ｚ＋＝Ｚ＋−＋＊ｘ＋ｆｔ−＋　　（ｊ＝ｉ、・・・、
１）ｆ（ｘ）＝Ｚｔ また、回路を小型化するためにステップｌと同様に乗算
器３とレジスタ５を削る。また第４６図の回路において
α−’　（ｔ＝ｎ−１，・・・、Ｏ）、の入力はステッ
プｌと同様に＃１のＰＥから＃ｔのＰＥまモ値を変える
こと無（送られるだけである。そこでｊ＝１からｍまで
を１周期としてα−１の１つの値が保持されるようにα
’　（ｉ＝ｎ−１，・・・、０）を入力する。

またｆｔ−１の係数はステップｌと同様に１周期毎にｆ
Ｉ−１（ｊ＝１．・・・、ｍ）の入力が繰り返されなけ
ればならない。ステップ２のＧＣＤ生成部からの出力を
考えた場合、係数ｆｔ−１（ｊ＝１．・・・、１）は１
度出力されるが、周期的に繰り返し出力されない。そこ
で、選択信号Ｓ１，２によって表のような組合せで出力
されるセレクタとｍ段のレジスタ列７を用いて、第１３
図のようにＰＥを構成し、第１４図のように信号を送る
。ＧＣＤ生成部から係数ｆｔ−＋（ｊ＝１．・・・。

ｔ）が出力されているときはセレクタ選択信号をＳｌ。

２＝１１（ｆｒ−ｔが入力されているときのみ）からＳ
ｌ。

２＝Ｏ１とすることによって、Ｙ出力から係数ｆ【−１
（ｊ＝１．・・・、１）が順次出力され、レジスタ列７
に入力される。

その出力をＢ入力にフィードバックしてセレクタ選択信
号をＳｌ、　２＝１０　（ｆｔ−＋が入力されていると
きのみ）からＳｌ、２＝ＯＯとすることによって、再び
Ｙ出力から係数ｆ＋−＋（ｊ＝１．・・・、１）が出力
され、レジスタ列７に入力される。以後その動作を繰り
返すことによって係数ｆｒ−ｔ（ｊ＝１．・・−，１）
の周期的な入力が実現される。これによってステップｌ
と同様にｍ個のＰＨの処理を１つのＰＥで実現できるが
、レジスタ段数分だけ入力α１を保持する必要があるの
で、処理速度は（１６／ｍ）Ｍｗｐｓとなる。（ｍはレ
ジスタ段数） またＩＰＥに必要な回路規模は（４００＋　（ｍ＋１）
＋５０）ゲートとなる。

ｍはレジスタ段数であるが、全処理をＩＰＥで行わせる
場合ｍ＝ｔとなる。但し、ω（Ｘ）、σ（Ｘ）。

σ′（Ｘ）の処理のためにＰＥは３セツト必要である。

１例として、訂正能力ｔ＝８とした場合回路規模は３＊
８５０＝２５５０ゲートとなり、処理速度は２　Ｍ　ｗ
　ｐ　ｓとなる。

また全処理をｌＰＥで構成せず、複数のＰＥに分けて構
成する場合、第１３図のＰＥを第１５図のように接続す
る。このとき、α１をＩＰＥ毎に１周期゛単位で遅らせ
るためにＣＫ２（１周期毎のクロック）で制御されるレ
ジスタが必要である。

ＰＥの数をｋとすると全体の処理は（ｔ／ｋ）に′分散
されるので、ＩＰＨに必要なレジスタ段数はｍ＝（ｔ／
ｋ）となる。従って、第１５図の回路規模は（ｔ／ｍ）
＊　（４００＋　（ｍ＋１）＋５０）ゲートとなる。第
１６図に２つのＰＥで構成した場合の信号の流れを示す
。この場合、ｔ＝８であるのでｍ＝　（ｔ／２）　＝４
として回路規模は３＊２＊６５０＝３９００ゲートとな
り、処理速度は４　Ｍ　ｗ　ｐ　ｓとなる。

ｍ　＝　１としたとき必要なＰＥの数はに＝ｔとなり、
ＣＫ２＝ＣＫとなるのでＣＫ２で制御されるレジスタは
レジスタ５と等価になり、ｆｌ−＋の割り付は部をのぞ
いて第４６図と同じ構成になり、処理速度も１６　Ｍ　
ｗ　ｐ　ｓとなる。

また、第１７図にｔｙ　（ｘ）、とｃｙ’（ｘ）を１つ
のＰＥで処理する場合ＰＥを示し、第１８図に信号の流
れを示す。ステップ３は１周期がｔであるのでＩＰＥを
２度用いることが出来、またσ′（Ｘ）の係数がσ（Ｘ
）の係数を用いることを利用する。これによって、ステ
ップ３が２セツトのＰＥで実現でき、第１８図に示すよ
うにσ（Ｘ）、σ′（Ｘ）の動作は２【毎となり、ω（
Ｘ）の出力も第１９図のようにすることによって２を毎
に動作させることが出来る。

ここでは出力の組合せが表のようになるセレクタを用い
てＹ出力がＯとなるときだけセレクタ選択信号を３１．
．３＝ＯＯ１とすればよい。この場合、処理速度は２　
Ｍ　ｗ　ｐ　ｓ　／　２　＝　Ｉ　Ｍ　ｗ　ｐ　ｓとな
り、必要なＰＥのセットも２セツトとなるので回路規模
は２　＊　８５０＝１７００ゲートとなる。

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

まず、消失位置多項式λ（Ｘ）を生成することを考える
。゛ λ（ｘ）　＝　（１−ＹＩ＊Ｘ）＊（１−Ｙ２＊Ｘ）・
・・（１−Ｙｓ＊ｘ）であり、前章と同様にλ（Ｘ）を
次のように分解する。

Ｚｏ＝１ Ｚ＋＝　　（Ｉ　　　Ｙ＋＊ｘ）＊Ｚ＋−１＝Ｙ＋＊Ｚ
＋−１　＊Ｘ＋Ｚ＋−Ｉ　（ｔ＝１．・・・、ｓ）λ　
（ｘ）＝Ｚｓ まず、回路を小型化するために乗算器３及びレジスタ６
を削る。ここでは処理クロック数またはレジスタ段数に
対応させる。またＺｌ−１人力をｌクロック遅らせるた
めのレジスタを１つ用意する。従って、ＰＥの構成は第
２２図のようになり、ＩＰＨに必要な回路規模は（４０
０＋（ｍ＋１）＋５０）ゲートとなる。（ｍはレジスタ
段数）第２３図に信号の流れを示す。

ＩＰＥ内のレジスタ段数ｍ（ここではｍ＝２ｔとする）
を１周期としてＹ、の１つの値が保持されるようにＹ＋
（＋＝１．・・・、Ｓ）を入力する。最初、（Ｙ＋入力
時）セレクタ選択信号をＳｌ、　２＝１１としＸにＤ入
力Ｚｏ＝１、ＹにＣ入力Ｏを入力し演算結果のＹ＋を次
のクロックでレジスタ列６に入力する。以降、Ｓｌ、　
２＝１０としてＸにＣ入力０、ＹにＺｏを１クロック遅
らせたＡ入力を出力し、演算結果Ｚｏ＝１を次の、クロ
ックでレジスタ列６に入力する。その次のクロック以降
は演算結果が０であるのでＯがレジスタ列６に入力され
る。１周期後、（Ｙ２２人力）レジスタ列６から前演算
結果Ｚ　＋　＝　Ｙ　＋　＊　ｘ　＋　１　（次数Ｘは
信号の順序を表す）が出力されるので、Ｓｌ。

２＝Ｏ１としＸに前演算結果の最高次係数ＹｌをＡ入力
から、ＹにＣ入力の０を出力し演算結果のＹ１＊Ｙ２を
次のクロックでレジスタ列６に入力する。

以降、Ｓｔ、２＝ＯＯとしてＸに２１の次の係数ｌをＡ
入力から、Ｙに１クロック遅らせたＺｌの最高次係数Ｙ
ｌをＢ入力から選択し、演算結果Ｙ　＋　＋　Ｙ　２を
次のクロックでレジスタ列６に入力する。このときＸか
らは０、ＹからはｚＩの次の係数１が出力され、次のク
ロックで演算結果ｌがレジスタ列６に入力され、以降演
算結果がＯであるので０が入力される。

Ｙ２２人力の動作をＹ３人力以降も繰り返すことによっ
てＹ５人力後にレジスタ列６からλ（Ｘ）が高次の係数
から出力される。

Ｓ≦２ｔであるので、Ｙ＋＝０　（ｊ＝ｓ＋１．・・・
、２ｔ）を入力すればよい。

従って、処理速度は（１６／　２　ｔ　／　ｍ　）　Ｍ
　Ｉ　ｐ　ｓとな゛る。１例として、ｔ＝８として全処
理をＩＰＥで行わせる場合、回路規模は１２５０ゲート
となり、処理速度は１　／　ｌ　６　Ｍ　ｌ　ｐ　ｓと
なる。

また、全処理をＩＰＥで構成せず、複数のＰＥに分けて
構成する場合、第２２図のＰＥを第２４図のように接続
する。このときＹｌの値を２ｔクロツクの間保持するた
めに各ＰＥ毎にＹ＋を設定するレジスタが必要である。

ＰＥの数をｋとすると全体の処理は（２ｔ／ｋ）に分散
されるので、ＩＰＨに必要なレジスタ段数はｍ＝（２ｔ
／ｋ）となる。従って、第２４図の回路規模は（２ｔ／
ｍ）＊　（４００＋　（ｍ＋１）＋５０）ゲートとなる
。第２５図に２つのＰＥで構成した場合の信号の流れを
示す。このときの回路規模は８５０＊２＝１７００ゲー
トとなり、処理速度は２／１６Ｍ１ｐｓとなる。

ｍ　＝　１としたとき必要なＰＥの数はに＝２ｔとなり
、処理速度も（１６／　２ｔ）　Ｍｌｐｓとなり、第４
７図の構成と等価になる。

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

Ａ（ｘ）　：３．、−ｌ　＊　Ｘ’−’＋ａｍ−２＊　
ｘｌ″”十−・・＋ａｒ＊ｘ＋ａ。

としたとき Ｃ（ｘ）　＝　ａｍ−１＊　Ｂ（ｘ）＊　ｘｌＮ−’　
＋　ａｍ−２＊　Ｂ（ｘ）＊　ｘ″−２＋・・−＋　ａ
　＋　＊　Ｂ（ｘ）＊　ｘ　十ａｏＢ（ｘ）となるので Ｚ　ｏ　＝　Ｏ Ｚ＋＝Ｚ＋−＋　＊Ｘ＋Ｂ（Ｘ）’ｋａｍ−ｉ　　０＝
ｌ、−、ｍ）Ｃ（ｘ）　＝Ｚ、、。

従って、Ｂ　（ｘ）が入力されている間ａｍ−ｉ′を保
持しＺ＋＝ＺＩ−＋＊ｘ＋Ｂ　（ｘ）　＊ａｍ−１を演
算した後レジスタ列６に挿入し、１周期後その演算結果
をＺ＋＝＋としてフィードバックすればよい。しかし、
入力Ｓ　（ｘ）及びλ（Ｘ）はステップｌのシンドロー
ム生成部、及び前述の誤り位置多項式生成部から１度基
本クロックＣＫの転送レートで入力されるだけである。

そこで、レジスタ列５．７を用いて繰り返し入力を実現
し、ＣＫ２で制御されるレジスタを用いて設定値を保持
する。また、レジスタ列７からの、Ｂ（ｘ）出力はレジ
スタ列６からの２１−１出力より１クロック遅れてフィ
ードバックされる必要があるのでＰＥの構成は第２６図
のようになる。Ｂ　（ｘ）　＝Ｓ　（ｘ）。

ａ　ｍ−４＝λ２１□（＋＝０．・・・、２ｔ）とした
場合の信号の流れを第２７図に示す。（ＩＰＥ内のレジ
スタ段数ｍ−１＝２ｔ−１とする） 先ず、セレクタ選択信号Ｓｌ、２＝０１としてλ（Ｘ）
をＦ入力からＷ出力を通してレジスタ列５に入力する。

そのときλ（Ｘ）の最高次係数λ２【をＣＫ２によって
制御されるレジスタに蓄え、乗算機３の入力に設定する
。またＳ　（ｘ）をλ（Ｘ）より１クロック遅らせてＥ
に入力し、Ｙに出力させレジスタ列７に入力する。その
間ＸはＣ入力Ｏを出力する。

これによってλ２Ｌ＊５（Ｘ）が演算され、レジスタ列
６に入力される。このときλ（ｘ）　＊Ｓ　（Ｘ）の最
高次係数λ２１　＊　Ｓ　２１−１は演算されているの
でＣＫＤによってラッチされ出力される。１周期をｍ（
ここではｍ　＝　２　ｔ　）として、１周期後セレクタ
選択信号Ｓｌ、２＝００とする。Ｂからはｍ段のレジス
タ列７によってフィードバックされたＳ　（ｘ）が入力
され、再びＹ、からレジスタ列７に入力される。Ｄから
はｍ段のレジスタ列５によって最高次係数がずれたλ（
Ｘ）がフィードバックされＷに出力される。

従って、ＣＫ２ではλ（Ｘ）の次の係数λ２【−１が蓄
えられ乗算器３に設定される。Ａからはｍ−１段のレジ
スタ列６によって全演算結果の最高次係数がずれたもの
がフィードバックされＢ　（ｘ）　＝Ｓ　（ｘ）に対し
１次係数がずれた形で入力される。これによって、Ｚ＋
＝Ｚ＋−＋＊ｘ＋Ｂ　（ｘ）　＊ａｍ−１が演算されレ
ジスタ列６に入力される。以降ＣＫ２にλ０が入力され
演算が終了するまで同様に演算が行われる。但し、答え
となる演算結果は入力にフィードバックするときずれて
しまうので、演算される度にＣＫ　Ｄによって出力され
る。またλ（Ｘ）の係数も入力にフィードバックすると
きずれてしまうので１次づつ係数が減ってしまう。ずら
された係数は必要ないのでフィードバックされるときセ
レクタ選択信号をＳｌ、２＝１０とすることによってＸ
、ＷにＯを出力する。

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

ＩＰＨに必要な回路規模はＰＥ内のレジスタ段数をｍ−
１とした場合（４００＋３ｍ＊５０）ゲート）となる。

また、処理速度は演算終了から出力終了まで考える必要
があるので（１６／　４　ｔ　／　ｍ　）　／　２とな
る。

全処理をＩＰＥで行う場合ＰＥ内のレジスタ段数ｍ−２
ｔとなり、１例として訂正能力ｔ＝８とした場合、回路
規模は２８００ゲートとなり、処理速度は（１／３２）
Ｍｌｐｓとなる。

また、全処理をＩＰＥで構成せず、複数のＰＥに分けて
構成する場合、第２６図のＰＥを第２８図のように接続
する。このときａｍ−ｉの値を２ｔクロツクの間保持す
るために各ＰＥ毎にａｌｌｌ−＋を設定するレジスタが
必要である。ＰＥの数をｋと、すると全体の処理は（２
ｔ／ｋ）に分散されるので、ＩＰＥに必要なレジスタ段
数はｍ＝（２ｔ／ｋ）となる。従って、第２８図の回路
規模は（２ｔ／ｍ）　＊　（４００＋３ｍ＊５０）ゲー
トとなる。第２９図に２つのＰＲで構成した場合の信号
の流れを示す。このときの回路規模１６００＊２＝３２
００ゲートとなり、処理速度は（１／１６）Ｍ　ｌ　ｐ
　ｓとなる。

ｍ＝１としたとき必要なＰＥの数はに＝２ｔとなり、処
理速度も（１／２）Ｍｌｐｓとなる。

Ｃｖ口し 符号化は情報Ｔ　（ｘ）　＝　（Ｉｋ−＋、Ｉｋ−ｚ、
−、Ｉｏ）からパリティＰ　（ｘ）　＝　（Ｐ２ｔ、Ｐ
２ｔ−＋、・・・、Ｐｌ）を生成する。符号化とは生成
多項式を ｇ（Ｘ）二りｆｎ＊Ｘ′″十ｇ　ｍ−１＊　Ｘ”−’　
＋　ｇ　ｍ　−２＊　Ｘ”−”・・・＋１＊ｘ＋ｇ。

とすると Ｐ　（ｘ）　＝４　（ｘ）　＊ｘ”　　ｍｏｄ　　ｇ　
（ｘ）を求めることであり、 ｇ’　（ｘ）　＝ｇｒｎ−＋＊ｘ′″−’＋ｇｍ−２＊
ｘ”−＝＋ｇ＋＊ｘ＋ｇ。

とすると この式は次のように分解される。

Ｚｏ＝Ｉ（ｘ） Ｚ　＋　”　ｇ　ｍ　＊　Ｚ’　ｌ−１＋　Ｚ　ｍ　＊
　ｇ’　（Ｘ）　　　　（’　＝１　＋　”・＋　ｋ　
）Ｐ（ｘ）　＝Ｚｋ ここてＺｍは多項式ｚＩ−１の最高次係数とし、Ｚ’＋
−ｌはＺｌ−１から最高次係数を除いた多項式とする。

Ｚｆｆｌをｇ’　（Ｘ）の入力中保持し、Ｚｍ＊ｇ’（
ｘ）の演算を行う。ここでは、ｇ　ｍ　＝　１とし、第
３０図のようにＰＥ”を構成する。

ｇｌからｇ’　（ｘ）の係数ｇｍ−１からｇｏがｍを１
周期として周期的に乗算器２に入力される。またＣ　Ｋ
　２（１周期毎のクロック）とＣＬによって制御される
レジスタによってＺｍを保持し、Ａに入力する。

Ｚ／　、−１は前演算結果Ｚ＋−＋を周期に対してｌク
ロック早（出力することによって実現する。従ってレジ
スタ列６の段数をｍ　−１とし、Ｂ入力にフィードバッ
クする。情報Ｉ　（ｘ）はＣから入力され１周期の間１
つの値が保持されるように入力する。

第３１図に符号化の様子を示す。先ずｉ＝１のときを考
える。初期状態としてＣＲ２で制御されるレジスタに情
報シンボルＩｋ−１が保持され、Ｃ入力からは情報Ｉ　
ｋ−ｍ−１が入力され、レジスタ列６に情報シンボルが
Ｉ　ｋ−２からＩｋ−ｍ迄蓄えられている場合を考える
。演算部ではＡ入力からのＩ　ｋ−＋にｇ’　（ｘ）を
乗じて１．Ｂ入力からのＩ　ｋ−２〜Ｉｋ−□、及びＣ
入力からのＴ　ｋ−ｍ−ｌと加算して、レジスタ列６に
入力する。

（Ｙ出力に対するＢ、　Ｃ入力の切り替えはセレクタ選
択信号Ｓ１，２によって行われ、Ｂ入力の時Ｓｌ。

２＝００、Ｃ入力の時Ｓｌ、２＝０１とする）その演算
結果を２１の高次の項から１’　ｋ＝　＝　Ｉ　ｋ−＋
　＊ｇｍ−ｉ　＋Ｉ　ｋ−＋−１とする。（ｊ＝１．・
・−、ｍ）ｉ＝２以降も１７に一ロ二対して同様の処理
をｉ＝ｋまで行うことにより符号化が行われる。

また、初期状態を実現するために第３２図（ｍ＝４の場
合）のようにする。情報入力はＩ　ｋ−＋〜ｒｏ迄１周
期の開鎖が保持されるように入力する。先ずセレクタ選
択信号Ｓｌ、２＝Ｏ１とし、最初の受信シンボルＩ　ｋ
−１をＣから入力しＹに出力する。Ａ入力へはＣＲ２で
制御されるレジスタのＣＬによってＯを入力し、Ｘに出
力させる。ＰＥ内のレジスタ段数がｍ−１であるので、
Ｂ入力には周期の１クロツク前にＩｋ−＋がフィードバ
ックされる。そのときＳｌ。

２＝００としｌクロック分だけＢ入力をＹに出力し８１
．２の設定を元に戻す。このときＣからは次の受信シン
ボルＩ　ｋ−２が入力されるのでレジスタ列６にはＩ　
ｋ−＋をｌクロ７２分入力した後、Ｉ　ｈ−ｚを入力す
ることになる。Ｉ　ｋ−２人力中、レジスタ列６からの
　フィードバック入力とのずれは２クロック分になるの
で、それに合わせてセレクタ選択信号をＳｌ、２＝００
とする。そのとき、１に−１の後にＩ　ｋ−２が１り　
ロック分選択される。以上の動作をＩｋ−□進行うこと
によってレジスタ列６に１に一１〜Ｉｋ−□が蓄えられ
ていく。Ｉｋ−ｍ−＋を入力するとき、１．に−１はレ
ジスタ列６からはみ出すがＣＫ２で制御されるレジスタ
にラッチされることによって初期状態が実現される。

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

従って、このときの回路規模、及び処理速度は（４００
＋ｍ＊５０）ゲート、及び（１６／　ｍ　）　Ｍ　ｗ　
ｐ　ｓである。全処理をＩＰＥで構成する場合、ｍ　＝
：２　ｔとなる。１例として訂正能力ｔ＝８とした場合
、ＩＰＥの回路規模は１２００ゲートとなり、処理速度
はＩ　Ｍ　ｗ　ｐ　ｓ　＝　８　Ｍ　ｂ　ｐ　ｓとなる
。

また、全処理をＩＰＥで構成せず、複数のＰＥに分けて
構成する場合、第３０図のＰＥを第３４図のように接続
する。ＰＥの数をｋとすると全体の処理は（２ｔ／ｋ）
に分散されるので、ｌＰＥに必要なレジスタの段数はｍ
＝（２ｔ／ｋ）となる。従って、第３４図の回路規模は
（２ｔ／ｍ）＊　（４００＋ｍ＊５０）ゲートとなる。

第３５図に２つのＰＥで構成した場合の信号の流れを示
す。この場合、レジスタ段数はｍ　＝　ｔであるので処
理速度は２Ｍｗｐｓ＝１６Ｍｂｐｓとなり、回路規模は
８００＊２＝１６００ゲートとなる。

ｍ＝１としたとき必要なＰＥの数はに＝２ｔとなるが、
＃にのＰＥから＃１のＰＥへのフィードバック、及び１
（ｘ）の同時入力は変わらないので、このアーキテクチ
ャにおいても符号器はやはりシストリックな構成になら
ない。

雷　；　　・−０びシステム ステップ３のｆ（α−１）出力は第１７図のＰＥを用い
た場合２を毎にＩＣＫ分だけ出力されるが、σ′（αり
とび（αＩ）、ω（α−″）ではタイミングが半周期ず
れるのでσ′（α−′）はＣＫ２　（２を毎のり、ロッ
ク）で制御されるレジスタでラッチさせ、σ（α−）。

ω（α−１）はＣＫ２’（ＣＫ２を半周期ずらしたクロ
ック）でラッチし、更にＣＫ２で制御されるレジスタで
ラッチすることによって第４８図と同様なステップ４の
誤り訂正が実現される。（タイミングは第２１図に示す
。但し、ＧＣＤ生成部においてはＡ　（Ｂ）。

Ｌ（Ｍ）の処理を１つのＰｒｏｃｅＳｓ部を２回用いて
いる場合は、ω（Ｘ）の係数が先に送られてくるのでバ
ッファを介する必要がある）ステップ４の誤り訂正の実
行部を最適化すると第２０図のようになる。

ω（α−′）、σ（α−１）、σ′（α″′）の出力の
タイミングを合、わせた後の動作は前章と同じである。

従って、ステップ４に於いて必要な回路規模はバッファ
と逆数生成用ＲＯＭを除いて、４５０＋５＊５０＝７０
０ゲートとなる。ステップ４の誤り訂正実行部はシスト
リックな構造を持たないので、レジスタ段数を増加して
も回路の小型化を行うことは出来ない。

従って、その状況に応じて最適な回路の簡単化を行えば
よい。またα″′（ｉ＝ｎ−１，・・・、Ｏ）発生回路
も同様である。

以上述べてきたように、Ｒ３符号の各復号ステラ　プは
高速性と引き替えに回路を小型化できる。

第４９図の復号器に於いて１例として次の組合せにする
ことよって、各ＰＥの制御をセレクタ選択信号とＣＫ２
のみで全体のシステムを動かすことが出来る。

ステップ１）ＳＹＮＤＨＯＭＥ：図６２ステップ２）　
ＧＣＤ　　　　　：図６９ステップ３）ＥＶＡＬＵＡＴ
Ｅ：図７７ステツプ４）ＣＯＲＲＥＣＴ　　：図８０符
号化復号器をシステムとして考えた場合、第５０図の消
失誤り訂正のための復号器を１例として、次の組合せに
することによって小型化された符号化復号器として実現
できる。

１）ＳＹＮＤＲＯＭＥ　　　：図６２ ２）　ＧＣＤ　　　　　　　：図６９ ３）ＥＶＡＬＵＡＴＥ　　　　：図７７４）　Ｃ０ＲＲ
ＥＣＴ　　　　：図８０５）ＥＲＡＳＵＲＥ　Ｉ　　　
：図８２６）　ＥＲＡＳＵＲＥ　ＩＩ　　　：図８にれ
はステップ４で示した復号器にＥＲＡＳＵＲＥＩとＥＲ
ＡＳＵＲＥ　　ＩＩを加えたものである。また、ステッ
プ４で示した復号器に第３０図の符号器を加えて符号化
復号器とすることも出来る。（符号化と復号を同時に行
わない場合には、ＰＥの接続、及びＰＨの制御を符号化
と復号で可変にすることによって第４９図の回路で回路
規模を変えることなく符号化復号器を実現できる） 各々の処理における回路規模（ゲート単位）、及び処理
速度（Ｍ　ｗ　ｐ　ｓ単位）は前述したように次の通り
である。（ｗｐｓ＝ｗｏｒｄ／　５ｅｃ）１）　　（２
ｔ／ｍ）　＊　（４００＋ｍ＋５０）、　１６／ｍ２）
　　（２ｔ／ｍ）＊（’７００＋　（３ｍ＋４）　＋５
０）、　ｎ＊（１６／２ｔ／ｍ）３）　　２＊（２ｔ／
ｍ）＊（４００＋（ｍ＋１）　＋５０）、　１６／ｍ５
）　　（２ｔ／ｍ）＊（４００＋（ｍ＋１）＋５０）、
ｎ＊（１６／２ｔ／ｍ）６）　　（２ｔ／ｍ）　＊　（
４００＊　（３ｍ＋２）　＋５０）、　ｎ＊　（１６／
４ｔ）　／ｍ）７）　　ＥＮＣＯＤＥ　　：図８９　　
；　　（２ｔ／ｍ）＊（４００＋ｍ＋５０）、　１６／
ｍ１例としてＲ３復号器がｔ＝８としたとき次のような
回路規模、及び処理速度で実現できる。（符号長ｎ≧４
ｔであり、またＩＰＥで実現するためにｍ＝２ｔとする
） １２００　＋　３３００　＋　２５００　＋　７００　
＝　７７００　ｇａｔｅＩ　Ｍ　ｗ　ｐ　ｓ　＝　８　
Ｍ　ｂ　ｐ　ｓまたｔ＝２の場合は ６００　＋１５００　＋　１３００　＋　７００　＋　
３１００ｇａｔｅ４　Ｍ　ｗ　ｐ　ｓ　＝　３２　Ｍ　
ｂ　ｐ　５（２１）の回路規模をＭゲートとすると、Ｇ
Ｆ　（２ゝ）の回路規模は約４Ｍゲートとなる。しかし
、ｌワードの構成がｍビットから２ｍビットとなること
を考えると、ＩＰＥ当りの処理速度は１０〜２０　Ｍ　
ｗ　ｐ　ｓ（ワード７秒）であるのでｍ・（！Ｏ〜２０
）Ｍｂｐｓから２ｍ　−（１０〜２０）　Ｍｂｐｓとな
り、２倍になる。

段数を２段とすればよい。すると、必要なＰＥの数は、
ｋ＝（２ｔ／ｍ）、ｍ　＝　２であるのでｔ個となる。

従って、ガロア体の構成をＧＦ（２’）からＧＦ（２”
）とした場合、同一処理速度での回路規模の増加は２倍
となる。一般的にガロア体の構成をＧＦ（２″）からＧ
Ｆ（２”−′）とした時、回路規模の増加は、ａ倍とな
る。

〔発明の効果〕

以上説明したように、前Ｒ３符号化復号器で用いたＰＥ
のレジスタ段数を増やすだけで、回路規模を小型化でき
るアーキテクチャを示した。

これによって、回路規模（ゲート単位）と処理速度（Ｍ
　ｗ　ｐ　ｓ単位）が訂正能力ｔと、レジスタ段数ｍに
よって関数的に示すことができ、実現可能な回路規模で
任意の処理能力、処理速度を実現できる。

【図面の簡単な説明】

第１図は本発明による小型化プロセッシング・エレメン
ト（ＰＥ）の構成図 第２図は本発明による第１図のＩ’Ｅを最適化したシン
ドローム生成回路の説明図 第３図は本発明による第２図のＰＨのタイミング図第４
図は本発明による第２図のＰＨの接続図第５図は本発明
による第２図のＰＥを２つ用いたシンドローム生成回路
のタイミング図 第６図は本発明による第１図のＰＥを用いたＧＣＤ生成
回路の説明図 第７図は本発明による第１図のＰＥを用いたＧＣＤ生成
回路のタイミング図 第８図は本発明による第１図のＰＥを用いたＧＣＤ生成
回路のタイミング図 第９図は本発明による第１図のＰＥを用いたＧＣＤ生成
回路の説明図 第１Ｏ図は第９図の入力タイミング図 第１１図は本発明による第１図のＰＥを最適化したＧＣ
Ｄ生成回路の説明図 第１２図は本発明による第１１図のＰＥを２つ用いたＧ
ＣＤ生成回路のタイミング図 第１３図は本発明による第１図のＰＥを最適化した誤り
評価回路の説明図 第１４図は本発明による第１３図のＰＥのタイミング図 第１５図は本発明による第１３図のＰＨの接続図第１６
図は本発明による第１３図のＰＥを２つ用いた場合のタ
イミング図 第１７図は本発明による第１３図のＰＥを最適化した誤
り評価回路の説明図 第１８図は本発明による第１７図のタイミング図第１９
図は本発明による第１７図のタイミング図第２０図は本
発明による最適化された誤り訂正実行部第２１図は本発
明による第２０図のタイミング図第２２図は本発明によ
る第１図のＰＥを最適化した消失１位置多項式生成回路
の説明図 第２３図は本発明による第２２図のＰＨのタイミング図
第２４図は本発明による第２２図のＰＥの接続図第２５
図は本発明による第２２図のＰＥを２つ用いた場合のタ
イミング図 第２６図は本発明による第１図のＰＥを最適化した乗算
回路の説明図 第２７図は本発明による第２６図のＰＨのタイミング図
第２８図は本発明による第２６図のＰＨの接続図第２９
図は本発明による第２６図のＰＥを２つ用いた場合のタ
イミング図 第３０図は本発明による第１図のＰＥを最適化した符号
器の説明図 第３１図は本発明による第３０図のＰＨのタイミング図
（処理中） 第３２図は本発明による第３０図のＰＥのタイミング図
（初期入力時） 第３３図は本発明による第３０図のＰＥのタイミング図
（数値出力時） 第３４図は本発明による第３０図のＰＥの接続図第３５
図は本発明によるＰＥを２つ用いた場合めタイミング図 第３６図は従来のプロセッシング・エレメント（ＰＥ）
の構成図 第３７図は従来のプロセッシング・エレメント（ＰＥ）
のセレクタの構成図 第３８図は従来のプロセッシング・エレメント（ＰＥ）
の乗算器の構成図 第３９図は従来のプロセッシング・エレメント（ＰＥ）
の加算器の構成図 第４０図はＧＣＤを求めるためのアルゴリズムを説明す
るための図 第４１図は従来のシンドローム生成用ＰＥを説明するた
めの図 第４２図は従来のシンドローム生成用ＰＥの接続図第４
３図は従来のＧＣＤ生成用ＰＥの接続図第４４図は従来
のＧＣＤ生成用ＰＥの動作タイミングを示す図 第４５図は従来のＧＣＤ生成用ＰＥの動作タイミングを
示す図 第４β図は従来の誤り評価用ＰＨの接続図第４７図は従
来の消失位置多項式生成用ＰＨの接続図 第４８図は従来の誤り訂正実行用ＰＥを説明するための
図 第４９図は従来の誤り訂正復号器をシステムを構成図 第５０図は消失誤り訂正復号器の例を示す図Ｏ・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・乗算器Φ　・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・加算器特許出願人　　キャノン株式会社 第２２ Ｇバ＋　　ｌ　　ｌ−ｔ　　ｔ　　ｌ　　＋　　＋−第
６目 ＣＫ１１ 男ＩＯ凶 ・１　　　　　　　　　ζ　ｋ 葛　　　ｏＡｘ 第４３　Ｘ つ　〜　＜　山　〜　こ　夕　３ ．　　　Ｘ ψ　具　ＦＯ か 特 躬４ｑ　図

Claims (1)

【特許請求の範囲】
1. （１）多入力多出力、または多入力−出力のセレクタと
   そのセレクタ出力の少なくとも一方を入力に持つガロア
   体上の乗算器と、その乗算器出力を少なくとも一方の入
   力に持つガロア体上の加算器と、その加算出力および前
   記セレクタ出力を蓄えるｍ段のレジスタ列から構成され
   る演算回路を複数同型に接続することによって受信語（
   ｒ＿ｎ＿−＿１、ｒ＿ｎ＿−＿２、…、ｒ＿０）からシ
   ンドロームＳ＿ｉ＿−＿１＝（…（ｒ＿ｎ＿−＿１・α
   ＾ｊ＋ｒ＿ｎ＿−＿２）・α＾ｊ＋ｒ＿ｎ＿−＿３）・
   α＾ｊ＋…＋ｒ＿１）・α＾ｊ＋ｒ＿０（ｊ＝ｌ、ｌ＋
   ２ｔ−１） （ただし、ｌは任意の整数、ｔは訂正能力、αはガロア
   体上の原始元） を生成するシンドローム生成回路。