JPH0464211B2

JPH0464211B2 -

Info

Publication number: JPH0464211B2
Application number: JP59249424A
Authority: JP
Inventors: Robaato Furitsutsu Keisu
Original assignee: REIZAA MAGUNETEITSUKU SUTOREIJI INTERN CO
Current assignee: REIZAA MAGUNETEITSUKU SUTOREIJI INTERN CO
Priority date: 1983-12-22
Filing date: 1984-11-26
Publication date: 1992-10-14
Also published as: JPS60223230A; DE3484503D1; US4584686A; EP0147041A3; CA1222829A; EP0147041A2; EP0147041B1

Description

【発明の詳細な説明】

（産業上の利用分野）この発明は概して誤り訂正装置の分野に関し、
特にリード・ソロモン（Reed−Solomon）誤り
訂正装置に関する。（従来の技術）リード・ソロモン誤り訂正は当該技術分野では
知られているものである。バールカンプ（E.
Berlekamp）著、代数符号化理論（1968年）、第
10章；ピーターソン及びウエルドン（Peterson
and Weldon）著、誤り訂正符号、第２版（1972
年）；リン（S.Lin）著、誤り訂正符号（1974
年）；符号化理論の発展における主要論文（1974
年）（ピーターソン編集）；リン及びコステロ
（Costello）著、誤り制御符号：基礎と応用
（1983年）、278及び531−２を参照のこと。またこ
のような文献としてリード・ソロモン符号の高速
度複号処理と題し、チエン（Chien）他による米
国特許第4142174号（1977年８月15日出願）、及び
ガロワ・フイールド（Galois Field）コンピユー
タと題しバールカンプによる米国特許出願第
4162480号（1977年１月28日出願）も参照のこと。この技術によれば、リード・ソロモン誤り訂正
装置は一般的に汎用デイジタル・コンピユータを
用い、ガロワ・フイールド処理を実行する周辺演
算装置を制御するものであつた。 10誤り訂正符号のように大きな誤り訂正可能符
号においては、必要とする誤り訂正アルゴリズム
を全てハードウエア処理することは費用がかかり
過ぎるものと考えられている。しかし、誤り訂正
アルゴリズムを全てソフトウエア処理していたの
では余りにも低速のものとなつてしまうと思われ
る。（発明の要約）本発明は10誤り訂正リード・ソロモン符号を用
いるものである。本発明装置は符号化、シンドロ
ーム生成及びチエン検索を実行し、誤り位置付け
多項及び誤り値の係数をマイクロプロセツサにお
いてソフトウエアにより解く。更に、本発明装置
は誤り検出及びバースト誤り捕捉を実行すること
ができる。本発明の誤り訂正装置は共通な一組のレジスタ
と２組の固定フイールド乗算器とを用い、指定さ
れた全ての誤り訂正機能を実行する。このレジス
タ及び乗算器の構成はコントローラの制御のもと
に２組のマルチプレクサにより制御される。この
誤り訂正装置の機能はコントローラの制御を介
し、マイクロプロセツサによりプログラムされて
いる。（実施例）第１図は本発明による10誤り訂正リード・ソロ
モン誤り訂正装置のブロツク図である。符号化及
び復号化に用いる数式は他で説明されているが、
特にバールカンプ著、代数符号理論（1968年）の
第10章、リン及びコステロ著、誤り制御符号：基
礎と応用（1983年）の第６章、特に第６、５章及
び第278頁を参照のこと。しかし、簡単な要約が
適当である。誤り訂正は本質的に３ステツプの処理、即ち(a)
情報の符号化、(b)その復号化及び(c)誤りの訂正か
らなる。符号化情報はｎシンボルの符号ワードＣ(X)を形
成し、例えば光学デイスク記録装置にデータを転
送して記録するものからなる。符号ワードＣ(X)は
ｋ情報シンボルＩ(X)及びｎ−ｋパリテイ・チエツ
ク・シンボルＰ(X)からなる。各シンボルはｍビツ
トからなる。パリテイ・チエツク・シンボルは生
成多項式Ｇ(X)により情報シンボルX^n-kＩ(X)を割
算することにより得られる。割算の結果は無視さ
れるＱ(X)、及び余りｒ(X)からなる。この余りｒ(X)
はパリテイ・チエツク・シンボルを構成し、Ｃ(X)
の下位位置ｎ−ｋに付加される。（Ｉ(X)をX^n-kに
より乗算し、Ｃ(X)の上位位置ｋに情報シンボルを
設定する。）リード・ソロモン符号により、１つ
の誤りを訂正するパリテイ・チエツク・シンボル
の数は、訂正されるべき誤り数ｔの２倍でなけれ
ばならない。誤りの次数が除数の次数に対応する
ので、10誤り訂正符号のために用いられる生成多
項式は20の次数を有する。生成多項式それ自体は
それぞれＸ−αⁱ形式の20の根からなる。ただし、
αⁱは２進のｍ倍であり、 αⁱ＝A_n-1α^m-1＋A_n-2α^m-2＋…… ＋A₁α¹＋A₀α⁰ かつαは既約多項式Ｐ(X)の根である。この実施例
において、既約多項式はＰ(X)＝X⁸＋X⁴＋X³＋X²
＋１である。Ｐ（α）＝０であるので、 α⁸＝α⁴＋α³＋α²＋１この既約多項式により表わされたガロワ・フイ
ールド（2⁸）の要素の対数表（表１）は次のよう
になる。各フイールド要素は（X⁸＋X⁴＋X³＋X²
＋１）を法としてαⁱ（ただし、ｉ＝０、１、２…
…255）の冪（べき）である。左の数字はフイー
ルド要素のαのべきに対応するフイールド要素の
数である。表の始めにおいて、各ビツトはαⁱｍ倍
の係数A_iに対応し、右端の表はA₀、左端の表は
A₇である。

【表】

【表】ｎ＝2^m−１、ｍビツト・シンボル（ただし、実
施例ではｍ＝８である）をもつ10誤り訂正リー
ド・ソロモン・コードの生成多項式は次のようで
ある。Ｇ(x)＝_2t-1 πⁱ⁼⁰ （Ｘ−αⁱ）又はＧ(x)＝X²⁰＋α¹⁷X¹⁹＋α⁶⁰X¹⁸＋α⁷⁹X¹⁷ ＋α⁵⁰X¹⁶＋α⁶¹X¹⁵＋α¹⁶³X¹⁴ ＋α²⁶X¹³＋α¹⁸⁷X¹²＋α²⁰²X¹¹ ＋α¹⁸⁰X¹⁰＋α²²¹X⁹＋α²²⁵X⁸ ＋α⁸³X⁷＋α²³⁹X⁶＋α¹⁵⁶X⁵＋α¹⁶⁴X⁴ ＋α²¹²X³＋α²¹²X²＋α¹⁸⁸X＋α¹⁹⁰. このようにして伝送された符号ワードＣ(X)は共
に生成多項式と、その各因数又は根との倍数であ
る。従つて、受信ワードＲ(X)に誤りが含まれてい
ないときは、生成多項式又はその各根により受信
ワードＲ(X)を割算した結果は、ある商及び０の余
りとなる。受信ワードＲ(X)に誤りが含まれている
かについて調べるためには、受信ワードＲ(X)を生
成多項式又はその全ての根により割算した後、余
り又は複数の余りが全て０であるかについて調べ
ればよい。誤り訂正のためには、訂正されるべき誤り数の
２倍に等しいシンドローム数を発生することが必
要である。この実施例においては、10誤りを訂正
するので、20のシンドロームを生成しなければな
らない。このシンドロームは受信ワードＲ(X)を生
成多項式Ｇ(X)の根（Ｘ−αⁱ）により割算した後の
余りと定義することができる。これはαⁱ即ちＲ
（αⁱ）における受信ワードＲ(X)の多項知を評価す
ることに等しい。このような根は20あるので、20
のシンドロームがある。このシンドロームは誤り
位置及び誤り値に対して数学的に次の関係があ
る。 S_j＝〓ⁱ Y_iX^j _i ただし、X_iは誤り位置、Y_iは誤り値、S_j＝Ｒ
（^j）である。従つて、Ｒ（α^j）＝〓Y_iX^j _i X_iはGF（2⁸）の要素であり、αmod（X⁸＋X⁴＋X³
＋X²＋１）のべきである。αのべきは誤つたシ
ンボルの位置に対応する。即ちX_i＝α⁹⁵のときは、
Ｒの第95シンボルに誤がある。また、誤り値Y_iは
GF（2⁸）の要素であり、誤りパターンに直接対応
している。従つて、この符号は誤りのある１つの
シンボルにおける８ビツト誤りの全パターンの訂
正が可能である。誤り位置は次の方法によりシンドロームから導
き出すことができる。まず、誤り位置多項式の係
数をバールカンプの代数符号理論の第154頁に示
すバールカンプのアルゴリズムにより計算する。
リン及びコステロの第155頁〜第158頁も参照のこ
と。10誤り訂正符号の誤り位置項式 σ(X)＝σ₁₀X¹⁰＋σ₉X⁹＋σ₈X⁸＋…… ＋σ₂X²＋σ₁X＋１＝０は、誤り位置X_iに対して次のような関係がある。 σ(X)＝π（１−X_iＸ） −ｊが受信ワードの位置に対応し、多項式σ(X)
をα_jにて評価した場合に、α_-jがσ(X)の根、即ち
１−X_iα^j＝０のときは、誤り位置多項式の第１形
式の総和は０となる。これはX_j＝α^-jのときに生
ずる。誤り位置のチエン検索は、各α^jのべき（ｊ
＝０、１、２、３……ｋ、ｋは情報シンボルの数
である）に対する多項式σ(X)の第１形式を評価
し、その結果が０か０でないかを調べることから
なる。この検索はパリテイ・チエツク・シンボルの誤
りを無視し、かつパリテイ・チエツク・シンボル
の位置に対応するαのべきにおいて多項式を評価
しないことにより短縮される。誤り位置X_iがチエン検索により位置付けされる
と、誤り値Y_iを評価することができる。誤り多項
式Ｓ(z)はＳ(z)＝１＋（S₁＋σ₁）ｚ＋（S₂＋σ₁S₁ ＋σ₂）z²＋……（S〓＋σ₁S〓_-1 ＋σ₂〓_-2＋……σ〓）z〓ここでνは誤り（最大）数である。次の誤り評価
多項式において、ｚに対する誤り位置の逆数、即
ち、ｚ＝X^-1 _iを置換することにより、誤り値Y_iを
判断することができる。ハードウエタリード・ソロモン誤り訂正の数学的な背景を説
明したので、本発明による誤り訂正装置の種々の
要素を説明する。この誤り訂正装置の動作は後述
する。誤り訂正装置１０は２つの主要要素、即ちコン
トローラ１２及び誤り訂正（ECC）アレー部１
４から構成される。コントローラ１２は双方向デ
ータ伝送用のバス１６を介してマイクロプロセツ
サ（図示なし）に接続されている。また、コント
ローラ１２にはバス１６のデータ方向を制御する
読み出し／書き込み線１８及びクリア線２０が接
続されている。コントローラ１２にはECC入力
データ線２２、ECC出力データ線２４、チエン
検索出力データ線２６及び各種の制御信号線２８
も接続されている。双方向データ用のバス１６、
ECC入力データ線２２、ECC出力データ線２４
及びチエン検索出力データ線２６は全て８ビツト
を並列に伝送する８本線の接続である。 ECCアレー部１４に戻るが、ECCアレー部１
４は20個のレジスタ３０からなり、その入力はそ
れぞれ20の排他的論理和ゲート３２に接続されて
いる。排他的論理和ゲート３２の２組の入力のう
ち、１組を20個の上側マルチプレクサ３４の出力
に接続し、また他の組の組を20個の下側マルチプ
レクサ３６の出力に接続している。各レジスタ３
０の出力をそれぞれ逆方向に20個のガロワ・フイ
ールド乗算器S₀〜S₁₉にそれぞれ接続している。
各乗算器S₀〜S₁₉の出力は逆対応の上側マルチプ
レクサ３４のＡ入力として接続される。更に、レ
ジスタ３０の最上位レジスタ３８の出力は先頭排
他的論理和ゲート４０に接続されており、この排
他的論理和ゲート４０の出力はフイードバツク・
マルチプレクサ４２（の“Ｂ”入力）を介してガ
ロワ・フイールド並列乗算器アレー４４の各乗算
器G₀〜G₁₉にフイードバツク接続として接続され
ている。更に、この最上位レジスタ３８の出力は
フイードバツク・マルチプレクサ４２のＡ入力と
して直接供給される。ガロワ・フイールド並列乗
算器アレー４４の各乗算器G₀〜G₁₉の出力は、対
応する次数の下側マルチプレクサ３６にＡ入力と
して接続され、次いで下側マルチプレクサ３６の
出力は対応する次数の排他的論理和ゲート３２に
１組の入力として接続される。ECC入力データ
線２２は、第１に排他的論理和ゲート４０に、第
２に下側マルチプレクサ３６の各Ｂ入力に並列
に、第３に出力マルチプレクサ５０のＡ入力を介
してECC出力データ線に、第４に最下位の上側
マルチプレクサ４８のＢ入力に出力を接続してい
るアンド・ゲート４６の１組の入力として接続さ
れている。レジスタ３０（レジスタ３８を除く）
の出力は更に上側マルチプレクサ（マルチプレク
サ４８を除く）のＢ入力にそれぞれ接続されてい
る。レジスタ３０の出力はガロワ・フイールド乗
算器S₁，S₂，S₃，S₄，S₅，S₆，S₇，S₈，S₉及び
S₁₀に接続され、更に次のような方法にて９つの
排他的論理和ゲート５２の１組の入力としてそれ
ぞれ接続されている。即ちレジスタ３０の出力
（S₁₀及びS₉に関するもの）は初段の排他的論理和
ゲート７０（第２図を参照）の入力として接続さ
れている。この排他的論理和ゲート７０の出力は
次の排他的論理和ゲート７２（第２図を参照）の
第１入力組として接続されている。この排他的論
理和ゲート７２の他の入力はレジスタ３０（S₈に
関するもの）からのものである。この排他的論理
和ゲート７２の出力は次の排他的論理和ゲート７
４の第１入力組として接続され、この排他的論理
和ゲート７４の他の入力組はレジスタ３０（S₇に
関するもの）からの出力であり、以下排他的論理
和ゲート６４まで続く。その最後の排他的論理和
ゲート６４の出力はコントロール１２へのチエン
検索出力である。各レジスタ３０、マルチプレクサ３４，３６，
４２，５０、排他的論理和ゲート３２，５２及び
乗算器S₀〜S₁₉、G₀〜G₁₉の入力及び出力は全てαⁱ
（（ｉ＝０、１、２……７）のべきに各線が対応す
る８ビツト幅である。排他的論理和ゲート３２，
５２はこのビツトについて個々に動作し、即ち第
１入力組の最下位ビツトは他の入力組の最下位ビ
ツトと排他的論理和がとられる。これは、２つの
シンボルのガロワ・フイールド加算としてこの技
術分野で知られているものである。しかし、各乗
算器は８ビツトの全部が１つのグループにて動作
する。乗算器S₀〜S₁₉、G₀〜G₁₉の論理を次の表
に示す。

【表】

【表】以上の表において、符号の左の数は出力数を表
わし、一方等号の右の数は入力数を表わす。プラ
ス符号は排他的論理和に等価なモジロ（modulo）
２の加算を表わす。上記表の数学的意味は、例により説明するのが
最良である。GF（2^m）の２要素、Ｙ（α）及びＡ
（α）の乗算は、Ｙ（α）＝Y_n-1α^m-1 ＋Y_n-2α^m-2＋……Y₀α⁰、Ａ（α）＝A_n-1α^m-1 ＋A_n-2α^m-2＋……A₀α⁰ としたときはＹ（α）Ａ（α）＝Y_n-1α^m-2（A_n-1α^m-1 ＋A_n-2α^m-2……A₀α⁰）Y_n-2α^m-2 （A_n-1α^m-1＋A_n-2α^m-2……A₀α⁰）＊＊＊＋Y₀α⁰（A_n-1α^m-1＋A_n-2α^m-2 ＋……A₀α⁰）．と表わすことができる。このことからＹ（α）Ａ（α）＝Y_n-1（A_n-1α^m-1α^m-1 ＋A_n-2α^m-2α^m-1＋……A₀α⁰α^m-1）＋Y_n-2（A_n-1α^m-1α^m-2 ＋A_n-2α^m-2α^m-2＋……A₀α⁰α^m-2 ＊＊＊＋Y₀（A_n-1α^m-1α⁰ ＋A_n-2α^m-2α⁰＋……A₀α⁰α⁰ ＝Y_n-1Ａ（α^m-1）＋Y_n-2Ａ（α^m-2）＊＊＊＋Y₀A（α⁰）となる。生成多項式Ｇ(X)のG₀の係数であるＡ（α）＝α¹⁹⁰とすると、Ａ（α⁰）＝α¹⁹⁰ Ａ（α¹）＝α¹⁹¹ Ａ（α²）＝α¹⁹² ＊＊＊Ａ（α⁷）＝α¹⁹⁷、and Ｙ（α）α¹⁹⁰＝Y₇α¹⁹⁷＋Y₆α¹⁹⁶ ＋Y₅α¹⁹⁵＋……Y₀α¹⁹⁰. 第１表から α¹⁹⁰＝α⁷＋α⁵＋α³＋α²＋α¹ α¹⁹¹＝α⁶＋α⁰ α¹⁹²＝α⁷＋α¹ α¹⁹³＝α⁴＋α³＋α⁰ α¹⁹⁴＝α⁵＋α⁴＋α¹ α¹⁹⁵＝α⁶＋α⁵＋α² α¹⁹⁶＝α⁷＋α⁶＋α³ α¹⁹⁷＝α⁷＋α³＋α²＋α⁰ 各α_iは、積Ｙ（α）α¹⁹⁰からなる８項であり、
Ｚ（α）により表わすことができる。Ｚ（α）＝Y₁α⁰＋Y₃α⁰＋Y₇α⁰ ＋Y₀α¹＋Y₂α¹＋Y₄α¹＋Y₆α¹ ＋Y₁α²＋Y₂α²＋Y₃α²＋Y₇α² ＋Y₂α³＋Y₅α³ ＋Y₁α⁴＋Y₅α⁴＋Y₆α⁴ ＋Y₀α⁵＋Y₂α⁵＋Y₆α⁵＋Y₇α⁵ ＋Y₁α⁶＋Y₃α⁶＋Y₇α⁶ ＋Y₀α⁷＋Y₂α⁷＋Y₄α⁷ Ｚ（α）がＺ（α）＝Z₇α⁷＋Z₆α⁶＋……Z₀α⁰、により表わされるときは、 Z₀＝Y₄＋Y₂＋Y⁷ Z₁＝Y₀＋Y₂＋Y₄＋Y₆ Z₂＝Y₁＋Y₂＋Y₃＋Y₇ Z₃＝Y₂＋Y₅ Z₄＝Y₁＋Y₅＋Y₆ Z₅＝Y₀＋Y₂＋Y₆＋Y₇ Z₆＝Y₁＋Y₃＋Y₇ Z₇＝Y₀＋Y₃＋Y₄ となる。視察からZ_iのこれら最終式はG₀＝α¹⁹⁰の第２表
に対応することが明らかである。上記の表から乗算器S₀〜S₁₉は固定された定数
α⁰〜α¹⁹により入力をそれぞれ乗算し、一方乗算
器G₀〜G₁₉は生成多項式Ｇ(X)の対応係数、即ち
α¹⁹⁰，α¹⁸⁸……α¹⁷により入力を乗算する。乗算器S₀〜S₁₉の各入力は関連するレジスタ３
０から供給される。これに対し乗算器G₀〜G₁₉に
対する各入力は単一信号源である。マルチプレク
サ４２から供給される。この結果、同一シンボル
が並列に20の定数G₀〜G₁₉により乗算される。上記の乗算論理を実際に実行することにより、
回路を簡単にし、また反復される論理パターンを
共用することにより冗長性を少なくしようとする
ものである。例えば、乗算器S₂において、パター
ン“６＋７”は式“３”及び“４”において反復
される。“６＋７”の１回路のみを実行する必要
があり、かつその出力を“３”及“４”回路の両
方に入力として供給することが必要である。乗算
器G₀〜G₁₉と関連する論理は、異なる多数の乗算
器に現われる項を全体に共通する作成することに
より大幅に簡単化することが可能なものであるこ
とが理解できる。論理式を実行する実際の回路を
選択することは当該技術に習熟した者の範囲に含
まれるものとみなされている。以上に付け加えるに、次の制御線をコントロー
ラ１２とECCアレー部１４との間に接続する。
即ち、初期化設定線５６をコトローラ１２と各レ
ジスタ３０のクリア入力との間に接続する。初期
化設定線５６を付勢すると、各レジスタ３０はク
リアされる。マスタ・クロロツク線５８も同様に
コントローラ１２と各レジスタ３０との間に接続
する。10個のσエネーブル・クロツク信号６０
を、第１図に示すように乗算器Ｓ１に接続されて
いるレジスタ６２を先頭にして10個のレジスタ３
０にそれぞれ供給する。第２図を参照する。マル
チプレクサ選択線１を上側マルチプレクサ３４の
マルチプレクサ選択入力に接続する。マルチプレ
クサ選択線２を下側マルチプレクサ３６の選択入
力に接続する。エネーブル検出線をアンド・ゲー
ト４６及びフイードバツク・マルチプレクサ４２
の選択入力Ｓに接続する。パリテイ・シンドロー
ム読み込み選択線をフイードバツク・マルチプレ
クサ４２のエネーブル入力EN及び出力マルチプ
レクサ５０の選択入力Ｓに接続し、これが「オ
フ」のときは出力マルチプレクサ５０のＢ入力を
選択し、かつフイードバツク・マルチプレクサ４
２を減勢する。これが減勢されたときは、フイー
ドバツク・マルチプレクサ４２は全て零を出力す
る。符号化誤り訂正装置を簡単に説明したので、その符号
化動作をここで説明する。伝送した符号ワードは２つの部分、即ち第１部
分のｋ情報シンボル及び第２部分の2tパリテイ・
チエツク・シンボルに分割可能であり、各シンボ
ルは長さが８ビツトである。一つの符号ワードに
おけるシンボルの最大数は255（2^m−１、ｍ＝８）
である。10誤り訂正リード・ソロモン符号のパリ
テイ・チエツク・シンボル数は20（ｔ＝10）であ
る。以下において、ｎは伝送すべき符号ワードの
長さに等しとみなし、ｎ−ｋはパリテイ・チエツ
ク・シンボル数に等しい。多項式で表わす伝送し
た符号ワードＣ(X)はＣ(X)＝_o-K-1 〓ⁱ⁼⁰ C_iXⁱ＋_o-1 〓ⁱ⁼⁰ C_iXⁱ Where_o-1 〓ⁱ⁼⁰ C_iXⁱ＝X^n-kＩ(X)、 and_o-k-1 〓ⁱ⁼⁰ C_iXⁱ＝ｒ(X)、である。ただし、ｒ(X)はＧ(X)によりX^n-kＩ(X)を
割算した結果の剰余である。即ち生成多項式は X^n-kＩ(X)＋ｒ(X)＝Ｑ(X)Ｇ(X)、又はＣ(X)＝Ｑ(X)Ｇ(X)、であり、Ｑ(X)は不使用の商であり、ｒ(X)はｎ−ｋ
パリテイ・チエツク・シンボルを構成する。符号化装置は、Ｇ(X)によりX^n-kＩ(X)を割算し、
X^n-kＩ(X)に付加できるように剰余ｒ(X)を伝送す
る。誤り訂正装置１０は情報シンボルを次のように
符号化する。マルチプレクサ５０の出力は最初は
ECC入力データをECC出力データ線２４上に出
力するように設定される。上側マルチプレクサ３
４はＡ入力を通過させるように設定される。フイ
ードバツク・マルチプレクサ４２はＢ入力を通過
させるように設定させる。アンド・ゲート４６は
デイスエーブルされる。このように設定される
と、ECCアレー部１４は第３図に示すような等
価回路で動作する。情報シンボルはECC入力データ線２２を介し
て１つずつ上位のものを先にして伝送される。各
情報シンボルはECC入力データ線２２を介して
先頭排他的論理和ゲート４０に、次いでフイード
バツク・マルチプレクサ４２を介して乗算器アレ
ー４４に送られ、そこで生成多項式Ｇ(X)の係数で
あるシンボルが20個の乗算器G₀〜G₁₉により乗算
される。その乗算出力は直接、線５４から得ら
れ、下側マルチプレクサ３６を介して排他的論理
和ゲート３２の１組の入力に渡す。マスタ・クロ
ツクは各情報シンボルに対して１回のクロツク動
作をすることにより、排他的論理和ゲート３２に
現われる情報をレジスタ３０に書き込む。これにより書き込まれた情報はレジスタ３０の
出力から得ることができる。この出力は前述のよ
うに上側マルチプレクサ３４（Ｂ入力）を介して
排他的論理和ゲート３２の第２組の入力と乗算さ
れる。第２情報シンボルがECC入力データ線２
２に出力されたときは、乗算器G₀〜G₁₉により乗
算された第１情報シンボルの結果は、排他的論理
和ゲート３２にて乗算された第２情報シンボルの
結果と排他的論理和がとられる。レジスタ３０
は、第２のマスタ・クロツクが入力されると、こ
の排他的論理和の結果を記憶する。この処理は、
全情報シンボルが乗算器アレー４４を介してクロ
ツク駆動されるまで続く。当該技術分野で知られているように、以上の一
連の動作により生成多項式Ｇ(X)によりX^n-kを乗
算した情報シンボルを割算する。割算すると、20
シンボルからなる剰余がレジスタ３０内に剰余と
して残る。パリテイ・チエツク・シンボルである
剰余を取り出すため、コントローラ１２は、出力
マルチプレクサ５０のＢ入力を選択してレジスタ
３８の出力とECC出力データ線２４とを接続し、
更にフイードバツク・マルチプレクサ４２をデイ
スエーブルする。これにより全て０を排他的論理
ゲート３２に送る。上側マルチプレクサ３４の設
定は変更することなく保持される。これにより排
他的論理和ゲート３２の論理機能を論理和機能に
変換することになり、シンボルを１のレジスタか
ら他のレジスタに修飾することなく転送させる。このように接続されると、ECCアレー部１４
は第４図に示す等価回路として機能する。まず、
出力マルチプレクサ５０のＢ入力が選択される
と、レジスタ３８の第１パリテイ・シンボルが得
られる。マスタ・クロツクがレジスタ３０をクロ
ツク駆動すると、前段のレジスタのシンボルが次
のレジスタに読み込まれ、第２パリテイ・シンボ
ルがレジスタ３８の出力から得られる。19以上即
ち総計20回のマスタ・クロツクのパルスにより各
パリテイ・シンボルがECC出力データ線２４に
クロツク出力される。全てのパリテイ・シンボル
がクロツク出力されると、符号ワードＣ(X)の終り
となる。情報シンボルＩ(X)は最上位が最初に得られるも
のであることに注意すべきである。ｋ個の情報シ
ンボルが存在するものとすると、I₀＋I₁X＋I₂X²
＋……I_k-1X^k-1、シンボルI_k-1X^k-1がECC入力デ
ータ線２２に現われる。このシンボルはECCア
レー部１４に供給されて割算される。また、これ
によりＩ(X)多項式においてｎ−ｋより大きい次数
の最上位の符号ワードＣ(X)を出力することにな
る。この変換により情報シンボルI_k-1X^k-1をX^n-k
により乗算することになるので、 C₁X^n-1＝X^n-1I_k-1X^k-1 又は C₁X^n-1＝I_k-1X^n-1 となる。剰余ｒ(X)もECC出力データ線２４に、
最上位を最初にして供給される。従つて、 C_o-k-1X^n-k-1＝r₁₉X¹⁹ かつ C₀＝r₀X⁰ となる。最上位のレジスタ３８の後に右端からＩ(X)を供
給することは、X^n-kＩ(X)をＧ(X)により割算する
ことと等価であるが、これは当業者に明らかなこ
とであり、下記に説明する通常の割算回路を考慮
すれば明らかになるであろう。誤り検出符号化処理から符号ワードＣ(X)は生成多項式Ｇ
(X)の倍数、即ちＣ(X)＝Ｇ(X)Ｑ(X) であることを知る。符号ワードを誤りなく受信したときは、生成多
項式Ｇ(X)により符号Ｃ(X)を割算した結果は、剰余
ｒ(X)が０値となる。従つて、当該装置は、誤り検
出において生成多項式Ｇ(X)により符号ワードＣ(X)
を割算し、マイクロプロセツサに対してレジスタ
３０の内容をシフト出力して剰余ｒ(X)が０となる
ことを調べるように設定し、マイクロプロセツサ
により０についての試験を実行させることができ
る。動作において、回路はやや変わつた方法にて設
定され、割算及び試験を実行する。コントローラ
１２はコントローラ１２からのエネーブル検出線
を付勢することによりアンド・ゲート４６をエネ
ーブルする。コントローラ１２は下側マルチプレ
クサ３６のＡ入力、上側マルチプレクサ３４のＢ
入力及びフイードバツク・マルチプレクサ４２の
Ａ入力を選択する。このように設定されたとき
は、ECCアレー部１４は第５図に示すようにな
る。符号ワードはECC入力データ線２２にシンボ
ル毎に、最上位を最初にして供給する。シンボル
はレジスタ３０を介して最下位レジスタから最上
位レジスタへとクロツク入力され、次いでフイー
ドバツク・マルチプレクサ４２を介して乗算器ア
レー４４にフイードバツクされ、ここで最上位シ
ンボルは乗算器G₀〜G₁₉により、生成多項式の係
数に対して乗算される。この処理は、各符号ワー
ド・シンボルが最下位レジスタ３９にクロツク入
力されるまで続き、その時点では割算の剰余がレ
ジスタ３０に存在している。その後、マルチプレクサ５０のＢ入力が選択さ
れ、レジスタ３８をECC出力データ線２４に接
続する。フイードバツク・マルチプレクサ４２が
デイセーブルされ、０がシンボルとして排他的論
理和ゲート３２に入力される。ここで、この回路
は第３図に等価のものとなる。レジスタ３０は20
回クロツク駆動され、マイクロプロセツサに剰余
を入力して０値について試験させる。剰余のシン
ボルに０でないものがあつたときは、符号ワード
Ｃ(X)に誤りが発生していることになる。シンドロームの生成符号ワードＣ(X)が伝送され、ワードＲ(X)＝Ｃ(X)
＋Ｅ(X)を受信ワードとし、Ｅ(X)を誤りワードとす
ると、Ｒ(X)＝Ｃ(X)＋Ｅ(X) Ｃ(X)は生成多項式Ｇ(X)の倍数であるから、Ｇ(X)＝_2t-1 πⁱ⁼⁰ （Ｘ−αⁱ）Ｃ(X)＝Ｑ(X)（Ｘ−α⁰）（Ｘ−α¹） ……（Ｘ−α^2t-1）以上のことから、αⁱ＝α⁰、
α¹、α²……α^2t-1のときは、符号ワードＣ（α^j）＝
０であることが解る。従つて、Ｒ（αⁱ）＝０＋Ｅ（（αⁱ）更に、各αⁱ、ｉ＝０、１、２……2t−１にて評
価した受信ワードＲ(X)が０のときにのみ、受信ワ
ードＲ(X)は送信した符号ワードＣ(X)であることも
解る。もし何らかの誤りが発生すると、αⁱ（ｉ＝
０、１、２……2t−１）におけるＲ(X)の評価の１
つ以上が０値とならない。誤りの位置及びその値
は０でない値から計算することができる（シンド
ロームとして知られている）。この実施例における2tシンドロームはS_i＝Ｒ
（αⁱ）（ｉ＝０、１、２……19、ｔ＝10）である。シンドロームS_iはＸ−α_iによりＲ(X)を割算する
ことにより算出することができる。この割算によ
り次式の結果を得る。Ｒ(X)＝Ｃ(X)（Ｘ−α_i）＋B_i、ただし、剰余B_iは、GF（2^m）における定数であ
る。この等式の両辺におけるＸをαⁱにより置換す
ると、Ｒ（αⁱ）＝Ｃ（αⁱ）（αⁱ−αⁱ）＋B_i、 S_i＝０＋B_i＝B_i 受信ワードＲ(X)を排他的論理和ゲート３２の１
組の入力としてシンボル毎に供給する第６図に示
すような回路により割算を実行することができ
る。この排他的論理和ゲート３２では排他的論理
和をその２つの入力組における対応する次数の各
ビツトについてビツト毎に行なう。排他的論理和
ゲート３２の出力はビツト毎にレジスタ３０に記
憶される。レジスタ３０の出力はビツト毎にαⁱに
り乗算回路６２に供給される。乗算回路６２の８
次の出力は排他的論理和ゲート３２の第２入力セ
ツトとして供給される。受信ワードＲ(X)の各シンボルがαⁱの乗算回路６
２を介してクロツク駆動されると、シンドローム
S_iからなる剰余即ち余りがレジスタ３０に残る。
このレジスタ３０の内容はECCアレー部１４か
らマイクロプロセツサにクロツクにより転送さ
れ、マイクロプロセツサにおいてシンドロームS_i
を他の19シンドロームと関連させて誤り位置多項
式の係数を計算するのに用いることができる。第１図を参照すると、制御回路は、上側マルチ
プレクサ３４のＡ入力を選択し、かつ下側マルチ
プレクサ３６のＢ入力を選択することにより、シ
ンドロームS_i（ｉ＝０、１、２……19）を計算す
るようにECCアレー部１４を設定する。上側マ
ルチプレクサ３４のＡ入力を選択することによ
り、第６図に示すように乗算器S₀，S₁，……S₁₉
を排他的論理和ゲート３２に接続させる。下側マ
ルチプレクサ３６のＢ入力を選択することによ
り、ECC入力データ線２２を排他的論理和ゲー
ト３２の他の入力に接続させる。これらは第６図
のＲ(X)入力に等価である。受信ワードＲ(X)は
ECC入力データ線２２を介して最上位を最初に
してシンボル毎に供給される。その後、ECCア
レー部１４はｎ回クロツク駆動され、並列に20シ
ンドロームS₀，S₁，……S₁₉を算出する。シンドロームS₀，S₁，……S₁₉は、算出された
後、レジスタ３０に入力される。次いでコントロ
ーラ１２は上側マルチプレクサ３４のＢ入力及び
下側マルチプレクサ３６のＡ入力を選択し、フイ
ードバツク・マルチプレクサ４２をデイスエーブ
ルして０シンボル・データを排他的論理和ゲート
３２に供給し、ECCアレー部１４を20回クロツ
ク駆動することにより、ECCアレー部１４から
ECC出力データ線２４に20個の全シンドローム
を読み出す。チエン検索マイクロプロセツサがシンドロームS_i（ｉ＝０、
１、２……19）を受け取つた後、バールカンプの
アルゴリズムを用いてこのシンドロームから誤り
位置多項式σ(X)の係数を計算する。σ(X)の係数が
解ると、αⁱにおける多項式 σ(X)＝σ₁₀X¹⁰＋σ₉X＋σ₈X⁸ ＋……σ₂X²＋σ₁X＋１、の評価により、σ（αⁱ）＝０のときは、α^-iにて１
つの誤り位置を導き出す。これは、 σ₁₀（αⁱ）＋σ₉（αⁱ）⁹＋……＋σ₂（αⁱ）² ＋σ₁（αⁱ）＝１に等しい。第２図に示すような回路は、チエン検索機能を
実行する。この回路は、10個のレジスタ３０と、
対応するべきαによりレジスタ３０の内容を乗算
してレジスタ３０にフイードバツクする乗算器
S₁，S₂，S₃……S₁₀と、互に直列に接続されると
共にレジスタ３０の出力に接続された９個のモジ
ユロ２の加算ゲート５２とからなる。レジスタ３
０の他の入力は、誤り位置多項式の係数σ₁，σ₂，
……σ₁₀からなる。これらの入力はレジスタ３０
に初期設定される。その後、レジスタ３０内に値
σ₁₀α¹⁰、σ₉α⁹、σ₈α⁸……σ₁α¹を形成するように
レ
ジスタ３０は１回クロツク駆動される。加算器５
２によりこれらレジスタ３０をモジユロ２の加算
をすることにより、チエン検索出力データ線２６
にα、即ちσ（α）−１における誤り位置多項式の
評価を得る。このチエン検索出力はコントローラ
１２により評価される。この評価の結果が１に等
しいとき、即ちチエン検索出力データ線２６上の
８ビツト出力の最小位ビツトのみが０値でないと
きは、１つの誤り位置が検出されたことになる。
誤りの位置はα^-1である。位置α^-1は、α^-1＝
α^255-1＝α²⁵⁴であるので、受信ワードＲ(X)におけ
るX²⁵⁴に対応し、その符号は循環的な乗算のもで
ある。コントローラ１２がチエン検索出力のシンボル
が１の値であることを判断すると、このことをマ
イクロプロセツサに通知する。誤りの実際の位置
はマイクロプロセツサ内のカウンタに設定され
る。 α²における誤り位置多項式を評価するため、レ
ジスタ３０をもう１回クロツク駆動することによ
り、再度αⁱ（ｉ＝１、２、……10）のべき数によ
りレジスタ３０の内容を乗算する。もし、誤りが
検出されると、位置X²⁵³には誤りがある。受信ワ
ードＲ(X)の可能とする各位置における誤り多項式
を評価するため、レジスタ３０を符号ワードの最
大長に対応した総計255回だけクロツク駆動しな
ければならない。しかし、パリテイ・チエツク・
シンボルに発生する誤りについては通常問題とす
るものではない。従つて、パリテイ・チエツク・
シンボルは受信ワードＲ(X)、即ち R₀、R₁X、R₂X²……R_2t-1X^2t-1 の最下位置に発生するので、ｔを誤り数とすると
きは、レジスタ３０は255−2t回だけクロツク駆
動させればよい。第１図を参照するに、コントローラ１２は以下
のようにECCアレー部１４を条件設定して乗算
器S₁〜乗算器S₁₀に対応するレジスタ３０に誤り
位置多項式σ(X)の係数を最初に設定することによ
り、チエン検索機能を実行する。即ち、レジスタ
３０をまず０に初期設定して下側マルチプレクサ
のＢ入力を選択することにより、ECC入力入力
データ線２２を排他的論理和ゲート３２に接続す
る。レジスタ３０の内容が０であるので、レジス
タ３０に図に示す右から左へ情報をロードしたと
きは、排他的論理和ゲート３２は情報を変化させ
ることなく、ECC入力データ線２２を介してレ
ジスタ３０に転送する。従つて、誤り位置多項式
σ(X)の係数は、最下位の係数σ₁を最初に、かつ最
上位の係数を最後にして得られる。σ₁がマイクロ
プロセツサによりECCアレー部１４に送られる
と、コントローラ１２はσ₁エネーブル信号６０を
介してレジスタ６２をエネーブルしてクロツク駆
動する。同じような処理をσ₁〜σ₁₀について実行
し、誤り位置多項知の各係数をレジスタ３０に個
別的にクロツク入力する。これらの係数がロード
されると、コントローラ１２はECC入力データ
線２２に０値のシンボルを出力するので、排他的
論理和ゲート３２は論理和ゲートに変化すること
になり、上側マルチプレクサ３４から出力された
情報を変化させることなくレジスタ３０に渡す。
コントローラ１２は上側マルチプレクサ３４のＡ
入力を選択し、乗算器S₁，S₂……S₁₀を排他的論
理和ゲート３２に接続する。次にレジスタ３０は
１回クロツク駆動され、α¹における誤り位置多項
式を評価する。レジスタ３０の出力“S₁”〜
“S₁₀”は第２図に示すように接続された排他的論
理和ゲート５２に入力されるので、レジスタ３０
のモジユロ２の和がチエン検索出力データ線２６
に得られる。チエン検索出力はフイードバツクと
してコントローラ１２に供給され、更にコントロ
ーラ１２はこの出力をフイードバツクとしてマイ
クロプロセツサに供給する。チエン検索出力が以
上で述べたように１に等しいときは、１つの誤り
位置を検出したことになる。コントローラ１２は
レジスタ３０を2^m−2t−１回クロツク駆動する。
ただし、ｍは符号シンボルの長さであり、2tはパ
リテイ・チエツク・シンボルの数である。誤り位置が検出された後、その位置の誤りの値
は以上述べたようにY_iについて誤り値の式を解く
ことにより検出することができる。バースト誤りの捕捉本発明の回路はバースト誤りの捕捉も実行でき
る。リード・ソロモン符号はサイクリツクなもの
であるから、最大長ｔの単一バーストの誤りを捕
捉するのに用いられる。ただし、ｔは、誤りを１
符号ワード内の連続的なシンボルに限定したとき
の符号の誤り訂正能力である。コントローラ１２は、バースト誤りを捕捉する
ために、上側マルチプレクサ３４のＢ入力、下側
マルチプレクサ３６のＡ入力及びマルチプレクサ
４２のＢ入力を選択する。この構成の回路は生成
多項式Ｇ(X)により受信ワードX^n-kＲ(X)を割算す
るようにセツトされる。入来する受信ワードＲ(X)
は最上位を最初にしてECCアレー部１４にシン
ボル毎に巡還される。ECCアレー部１４は受信
ワードＲ(X)のｎシンボルに対してｎ回クロツク駆
動される。受信ワードＲ(X)の全シンボルがECC
アレー部１４にクロツク入力された後、コントロ
ーラ１２はECC入力データ線２２をデイスエー
ブルし、全て０のシンボルを出力する。次にコン
トローラ１２はレジスタ３０を更にｎ−2t回又は
ECC出力データ線２４にｔ以上の０が検出され
るまで、クロツク駆動する。ただし、ｔは符号の
長さである。この時点でバースト誤りの大きさは
次のｔ以下のレジスタ３０に存在し、対応してシ
フトされた受信ワードＲ(X)のシンボルに対して次
のｔ以下の０でないシンボルの内容を直接モジユ
ロ２で加算することによつてバースト誤りを訂正
するのに用いられる。ピータソン及びウエルドン
著、誤り訂正符号、第２刷（1972年）、第11章、
特に第11.3章を参照のこと。実施例における要素数は特許請求の範囲を限定
するものでないと解釈されるべきである。

【図面の簡単な説明】

第１図はこの発明の好ましい実施例による
ECCアレー部及びコントローラのブロツク図、
第２図はチエン検索機能を実行するように接続さ
れたECCアレー部のブロツク図、第３図は符号
化機能を実行するように接続されたECCアレー
部のブロツク図、第４図はシフト・レジスタ機能
を実行するように接続されたECCアレー部のブ
ロツク図、第５図は誤り検出機能を実行するよう
に接続されたECCアレー部のブロツク図、およ
び第６図はシンドロームS_iの生成を実行するよう
に接続されたECCアレー部のブロツク図である。１０……誤り訂正装置、１２……コントロー
ラ、１４……ECCアレー部、１６……バス、２
２……ECC入力データ線、２４……ECC出力デ
ータ線、３０……レジスタ、３２，５２，６４，
７０，７２……排他的論理和ゲート、３４……上
側マルチプレクサ、３６……下側マルチプレク
サ、４４……ガロワ・フイールド並列乗算器アレ
ー、５０……出力マルチプレクサ、G₀〜G₁₉……
乗算器、S₀〜S₁₉……ガロワ・フイールド乗算器。

Claims

【特許請求の範囲】１訂正すべき誤りの数をｔとし、ｍを任意の数
とするときに、ｍビツトをそれぞれ保持するよう
にされた2t組のレジスタと、次数によりそれぞれ順序付けされたｍビツト２
組の入力の排他的論理和をとり、かつ順序付けさ
れた１組の出力をするようにされると共に、各出
力を対応する次数の前記レジスタの入力に接続し
た2t組の排他的論理和ゲートと、順序付けされたｍビツトの２入力間でそれぞれ
選択をして順序付けされたｍ個の出力に選択した
組を設定するようにされると共に、第１組の入力
をＡ組、第２組の入力をＢ組とし、各出力を対応
する次数の排他的論理和ゲートの順序付けされた
第１組の入力に接続した2t組の上側マルチプレク
サと、順序付けされたｍビツト２組の入力間でそれぞ
れ選択をして順序付けられた出力に選択した組を
設定するようにされると共に、第１組の入力をＡ
組、第２組の入力をＢ組とし、各出力を対応する
次数の排他的論理ゲートの順序付けされた第２組
の入力に接続した2t組の下側マルチプレクサと、
ｉ（ｉ＝０、１、２……2t−１）がその次数に対
応し、αⁱがガロワ・フイールド（2^m）のｍ項であ
るときに、順序付けされたｍビツト入力をαⁱによ
りそれぞれ乗算するようにした2t組の第１ガロ
ワ・フイールド乗算器であつて、順序付けされた
前記乗算器の入力をそれぞれ逆に順序付けされた
前記レジスタの入力に接続し、かつ順序付けされ
た前記乗算器の出力をそれぞれ逆に順序付けされ
た上側マルチプレクサのＡ入力組に接続した前記
第１ガロワ・フイールド乗算器と、順序付けされたｍビツト入力をＧ(X)＝_2t-1 πⁱ⁼⁰ （Ｘ−αⁱ）から得た生成多項式Ｇ(X)の対応する次数の係数に
より乗算するようにそれぞれ順序付けされた2t組
の第２ガロワ・フイールド乗算器と、順序付けされたｍビツト２組の入力間で選択を
して順序付けされたｍ個の出力に選択した組を設
定するようにされると共に、第１組の入力をＡ
組、第２組の入力をＢ組とし、前記出力を前記各
第２ガロワ・フイールド乗算器の入力に接続し、
前記レジスタの最上位の出力を前記Ａ組に接続さ
せたフイードバツク・マルチプレクサと、次数により順序付けされたｍビツト２組の入力
の排他的論理和をとつて順序付けされた１組出力
に供給するようにされると共に、第１組の各入力
を前記レジスタの最上位の出力に接続し、かつ各
出力を前記フイードバツク・マルチプレクサのＢ
入力組に接続した先頭排他的論理和ゲートと、前記レジスタの最上位の出力に接続した誤り訂
正出力データ線と、前記先頭排他的論理和ゲートの第２組の入力及
び前記各下側マルチプレクサのＢ入力組に接続さ
れ、順序付けされたｍビツトからなる誤り訂正入
力データ線と、エネーブル検出信号と順序付けされたｍビツト
の前記誤り訂正入力データ線との論理積をとり、
順序付けされている結果を前記上側マルチプレク
サの最下位のＢ入力組に供給するアンド・ゲート
と、対応する次数の前記第１組のガロワ・フイール
ド乗算器に接続された前記レジスタに接続され、
順序付けされたｔ個のσエネーブル信号σ_i（ｉ＝
１、２、３……ｔ）と、次数により順序付けされたｍビツト２組の入力
の排他的論理和をそれぞれとり、順序付けされた
１組の出力を供給すると共に、第１組の入力を対
応する次数の前記第１ガロワ・フイールド乗算器
に接続された前記レジスタの出力に接続し、第２
組の入力を、次に上位の前記ガロワ・フイールド
乗算器に接続された前記レジスタの出力に第２組
の入力を接続した最上位ゲートを除く、次に上位
のチエン排他的論理和ゲートの出力に接続し、最
下位の出力をチエン検索出力データ線に導くｔ−
１次のチエン排他的論理和ゲートと、前記各マルチプレクサのＡ又はＢ入力組を選択
し、前記エネーブル検出信号を供給し、前記σエ
ネーブル信号を選択的に供給し、前記各レジスタ
をクリアする信号を供給し、かつ前記各レジスタ
をクロツク駆動する信号を供給する手段を含む制
御手段と、を備えた誤り訂正装置。２特許請求の範囲第１項記載の誤り訂正装置に
おいて、前記制御手段は、前記上側マルチプレクサのＢ入力組を選択する
手段と、前記下側マルチプレクサのＡ入力組を選択する
手段と、前記フイードバツク・マルチプレクサのＢ入力
組を選択する手段と、からなり、データを符号化させる手段を備えるこ
とを特徴とする誤り訂正装置。３特許請求の範囲第１項記載の誤り訂正装置に
おいて、前記制御手段は、前記上側マルチプレクサのＢ入力組を選択する
手段と、前記下側マルチプレクサのＡ入力組を選択する
手段と、前記フイードバツク・マルチプレクサのＡ入力
組を選択する手段と、エネーブル検出信号を前記アンド・ゲートに供
給する手段と、からなり、符号化したデータにおける誤りを検出
するようにした手段を備えることを特徴とする誤
り訂正装置。４特許請求の範囲第１項記載の誤り訂正装置に
おいて、前記制御手段は前記上側マルチプレクサのＢ入力組を選択する
手段と、前記各排他的論理和ゲートにｍ個の零ビツトを
供給する手段と、からなり、前記レジスタからデータを修飾するこ
となくシフトさせる手段を含むことを特徴とする
誤り訂正装置。５特許請求の範囲第１項記載の誤り訂正装置に
おいて、前記制御手段は、前記上側マルチプレクサのＡ入力組を選択する
手段と、前記下側マルチプレクサのＢ入力組を選択する
手段と、からなり、符号化したデータからシンドロームS_i
（ｉ＝０、１、２……2t−１）を発生する手段を
含むことを特徴とする誤り訂正装置。６特許請求の範囲第１項記載の誤り訂正装置に
おいて、前記制御手段は前記レジスタを零を内容とした初期化設定をす
る手段と、前記下側マルチプレクサのＢ入力組を選択する
手段と、ガロワ・フイールド乗算器S_i（ｉ＝１、２、…
…2t）の第１組の対応する次数に接続したレジス
タを順次最下位から最上位へ選択的にエネーブル
してクロツク駆動する手段と、からなり、チエン検索誤り位置多項式の係数σ_i
（ｉ＝１、２……ｔ）をガロワ・フイールド乗算
器の前記第１組の対応する次数に接続された前記
レジスタにロードする手段を含むことを特徴とす
る誤り訂正装置。７特許請求の範囲第６項記載の誤り訂正装置に
おいて、前記制御手段は、前記上側マルチプレクサのＡ入力組を選択する
手段と、前記レジスタを少なくともｎ−ｋ回クロツク駆
動する手段と、チエン検出出力データ線を符号ワードにおける
シンボルに対応してそれぞれクロツク駆動した後
に１に等しい値について監視する手段と、からなり、ｎを符号ワードの長さとし、かつｋを
情報シンボルの数としたときに、αⁱ（ｉ＝１、２
……ｎ−ｋ）における誤り位置多項式を評価する
手段を含むようにしたことを特徴とする誤り訂正
装置。８特許請求の範囲第１項記載の誤り訂正装置に
おいて、前記制御手段は、前記上側マルチプレクサのＢ入力組を選択する
手段と、前記下側マルチプレクサのＡ入力組を選択する
手段と、前記フイードバツク・マルチプレクサのＢ入力
組を選択する手段と、前記レジスタをｎ−ｋ回クロツク駆動して前記
誤り訂正入力データ線の入力データを前記生成多
項式Ｇ(X)により割算する手段と、前記レジスタをｎ−ｋ回又は前記誤り訂正出力
データ線にｔ以上の零値のシンボルが現われるま
でクロツク駆動する手段と、からなり、符号化したデータにおけるバースト誤
りを捕捉する手段を含むことを特徴とする誤り訂
正装置。９特許請求の範囲第１項記載の誤り訂正装置に
おいて、前記ガロワ・フイールド（2^m）はｍ＝８
としたときに、ガロワ・フイールド（2⁸）であ
り、αは既約多項式Ｐ(X)＝X⁸＋X⁴＋X³＋X²＋１の根であることを特徴とする誤り訂正装置。