JPH0677844A - 誤り訂正装置 - Google Patents

Abstract

(57)【要約】 【目的】 リードソロモン符号等の誤り訂正符号を高速
に復号できる誤り訂正装置を提供する。 【構成】 ＲＡＭ１に蓄えられた再生データに含まれた
誤りを訂正する際に、シンドローム生成回路２と、誤り
位置多項式及び誤り数値多項式を算出するユークリッド
演算回路20と、誤り位置を算出するチェンサーチ回路21
との動作を並行して行う。ユークリッド互除過程に基づ
く除算を行う際に、被除多項式の係数データが記憶され
ているレジスタの内容を逐次シフトしながらガロア体上
の除算を実行する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は誤り訂正符号によって符
号化された情報中に発生する誤りを訂正する誤り訂正装
置に関し、特に、コンパクトディスクプレーヤ（以下、
ＣＤと記す）、ディジタルオーディオプレーヤ（以下、
ＤＡＴと記す）、ディジタル映像信号記録再生装置（以
下、ディジタルＶＴＲと記す）などで、再生または受信
ディジタル信号中に発生する誤りを高速で訂正処理する
誤り訂正装置に関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】ＣＤ，
ＤＡＴ，ディジタルＶＴＲなどに代表されるＰＣＭ（Pu
lse Code Modulation ）記録及び再生には誤り訂正符号
を用いた誤り訂正処理が用いられる。以下、上記ＣＤ、
ＤＡＴ及びディジタルＶＴＲに実際に用いられている誤
り訂正符号としてＧＦ（ｑ）上で定義されるリード・ソ
ロモン符号を用いて誤り訂正処理を行なう誤り訂正装置
について述べる。

【０００３】リード・ソロモン符号を用いて多数ワード
の誤り訂正を行なうには、受信データよりシンドローム
を生成して誤り位置多項式と誤り数値多項式との係数を
求める必要がある。このような多項式の係数を求める一
手法として、ユークリッドアルゴリズムまたはバーレカ
ンプアルゴリズム等が知られている。例えば、上述のユ
ークリッドアルゴリズムは与えられた２つの多項式の最
大公約多項式を求めるためのアルゴリズムであって、ガ
ロアフィールドＧＦ（ｑ）の元を係数とする多項式同士
の除算を行ない、誤り位置多項式と誤り数値多項式とを
求める。なお、ユークリッドアルゴリズムについての詳
しい説明は後述する。

【０００４】以下、リード・ソロモン符号による多数ワ
ードの誤り訂正の復号手順を示す。一般に、リード・ソ
ロモン符号の復号手順は次のようになる。 （１）受信データからシンドロームＳ_i を求める。（シ
ンドローム生成） （２）求めたシンドロームＳi から誤り位置多項式σ
（ｚ）及び誤り数値多項式ω（ｚ）を求める。（ユーク
リッドまたはバーレカンプアルゴリズム等） （３）誤り位置多項式σ（ｚ）より誤り位置を求める。
（チェンサーチ） （４）この誤り位置及び誤り数値多項式ω（ｚ）より誤
り数値を求める。 （５）誤り位置と誤り数値とから受信データの誤りを訂
正する。（誤り訂正）

【０００５】以下、ガロアフィールドＧＦ（２⁸ ）で定
義されるリード・ソロモン符号の復号方法について説明
する。

【０００６】シンドロームＳ_i は次式で与えられる。受
信多項式をＸ（ｚ）、生成多項式をＧ（ｚ）とすると、 Ｓ（ｚ）＝Ｘ（ｚ）ｍｏｄ Ｇ（ｚ） ＝Ｓ₀ ＋Ｓ₁ ×ｚ＋・・・＋Ｓ_k ×ｚ^k となる。なお、本従来例では符号長ｎのリード・ソロモ
ン符号を復号する場合について説明する。

【０００７】次に、シンドロームＳ_i （Ｓ（ｚ））より
誤り位置多項式σ（ｚ）及び誤り数値多項式ω（ｚ）を
求める。以下、ユークリッドアルゴリズムを用いた誤り
位置多項式及び誤り数値多項式の算出方法を簡単に説明
する。ユークリッドアルゴリズムとは、ガロア体上で定
義される多項式同士の除算の繰り返しであり、次のよう
に示される。すなわち、ユークリッドアルゴリズムと
は、ガロア体上で定義される２つの多項式をＡ（ｚ），
Ｂ（ｚ）とすると Ａ（ｚ） ／Ｂ（ｚ） ＝Ｑ₀ （ｚ）（商）・・・Ｒ₀
（ｚ）（余り） Ｂ（ｚ） ／Ｒ₀ （ｚ）＝Ｑ₁ （ｚ）（商）・・・Ｒ₁
（ｚ）（余り） Ｒ₀ （ｚ）／Ｒ₁ （ｚ）＝Ｑ₂ （ｚ）（商）・・・Ｒ₂
（ｚ）（余り） というガロア体上で定義される多項式同士の除算をある
一定の条件を満たすまで繰り返すものである。

【０００８】例えば、光ディスクに採用されている誤り
訂正符号の場合は最小ハミング距離が17のリード・ソロ
モン符号が採用されているので Ａ（ｚ）＝ｚ¹⁶ Ｂ（ｚ）＝Ｓ（ｚ） ＝Ｓ₀ ＋Ｓ₁ ×ｚ＋・・・＋Ｓ₁₅×ｚ¹⁵ と表わされ、上記割り算は余りの多項式の次数が７以下
になるまで繰り返される。（なお、本例では消失（イレ
ージャ）は考慮していない。）

【０００９】図25にユークリッドアルゴリズムによる基
本方程式の解（誤り位置多項式及び誤り数値多項式）を
求めるフローチャートを示す。まず始めにＳ１で各値の
初期値の設定を行なう。Ｓ２，Ｓ３で図示した演算を実
行し、Ｓ４でＮＯの場合は各多項式をＳ５に図示したよ
うに設定し再びＳ２へ戻る。Ｓ４でＹＥＳの場合は、Ｓ
６で誤り位置多項式σ（ｚ）及び誤り数値多項式ω
（ｚ）を求める。なお、図中＜ ＞はガウス記号を示
す。

【００１０】従って、ユークリッドアルゴリズムによる
誤り位置多項式σ（ｚ）及び誤り数値多項式ω（ｚ）の
算出は最小ハミング距離が17のリード・ソロモン符号の
場合、ガロア体上の多項式同士の除算を最大８回行なえ
ば良いことになる。

【００１１】ユークリッドアルゴリズムによって求めら
れた誤り位置多項式σ（ｚ）により誤り位置を求める。
これは、一般にチェンサーチという方法が用いられる。
この方法は、誤り位置多項式σ（ｚ）にα（αはガロア
体ＧＦ（２⁸ ）上の元）のべき乗であるαⁱ （ｉ＝０，
１，２，・・・，ｎ−１）を逐次代入して、σ（αⁱ）
が０となるσ（ｚ）の根αⁱ （誤り位置に相当する）を
求める。ただし、ｎは符号長である。

【００１２】上述の方法によると、誤り位置を演算する
ためには符号長に相当するＧＦ（２⁸ ）上のｎ個の元
（α⁰ 〜α^n-1 ）を逐次誤り位置多項式σ（ｚ）に代入
してσ（ｚ）＝０となるαⁱ （誤り位置に相当する）を
計算することになるので、演算のステップ数はｎ（符号
長）ステップとなる。

【００１３】以下、従来の誤り訂正装置について説明す
る。図26は従来のリード・ソロモン符号を復号する誤り
訂正装置の概略構成を示すブロック図である。図におい
て、１は誤り訂正の対象となるデータが格納されている
ＲＡＭ、２は受信語よりシンドロームを生成するシンド
ローム生成回路、３はシンドローム生成回路２より出力
される受信シンドロームをもとに誤り訂正を行なう誤り
訂正演算回路、４は誤り訂正装置全体の制御を行なう誤
り訂正装置制御回路である。

【００１４】図27にはシンドローム生成回路２の具体的
な回路構成図を示す。10は入力されたデータを一旦蓄え
るレジスタ、11はリード・ソロモン符号の生成多項式の
各係数を乗数とする乗算回路、12は加算回路である。以
上レジスタ10，乗算回路11及び加算回路12でシンドロー
ム生成回路２は構成されている。

【００１５】図28に誤り訂正演算回路３の具体的な回路
構成例を示す。20は図25に示すユークリッドアルゴリズ
ムにしたがって誤り位置多項式σ（ｚ）及び誤り数値多
項式ω（ｚ）を算出するユークリッド演算回路、21はユ
ークリッド演算回路20より出力される誤り位置多項式σ
（ｚ）の係数データより誤り位置を算出するチェンサー
チ回路、22はユークリッド演算回路20より出力される誤
り数値多項式ω（ｚ）の係数データ及びチェンサーチ回
路21より出力される誤り位置情報に基づき誤り数値を算
出するとともに、誤り訂正を行なう誤り訂正回路であ
る。以上、ユークリッド演算回路20，チェンサーチ回路
21及び誤り訂正回路22で誤り訂正演算回路３は構成され
ている。

【００１６】図29に、ユークリッド演算回路20の上記ガ
ロア体上の多項式の除算を行なう除算回路部分のブロッ
ク構成図を示す。50，51は入力端子、52a, 52bは除数,
被除数多項式の係数データを記憶しておくレジスタ、53
はセレクタ、54は乗算回路、55は加算回路である。以
上、レジスタ52a, 52b、セレクタ53、乗算回路54及び加
算回路55でユークリッド演算回路20のガロア体上の多項
式の除算回路部分は構成されている。

【００１７】図30にチェンサーチ回路21の具体的な回路
構成例を示す。31はチェンサーチ開始時に誤り位置多項
式σ（ｚ）の係数データをセットし、その後は逐次乗算
回路32の出力をセットする帰還レジスタ、32は乗算回
路、33は加算回路、34は加算回路33の出力が０であるか
を判定する判定回路、35は帰還レジスタ31の帰還回数を
カウントする係数カウンタ、36は判定回路34より出力さ
れる０判定結果に基づき係数カウンタ35のカウント値を
記憶するレジスタである。以上、帰還レジスタ31, 乗算
回路32, 加算回路33, 判定回路34, 係数カウンタ35及び
レジスタ36で、チェンサーチ回路21は構成されている。

【００１８】次に、図26, 図27, 図28, 図29及び図30を
用いて誤り訂正装置の動作について説明する。ＲＡＭ１
に格納されている受信または再生時に発生した誤りを含
む受信または再生データは、誤り訂正処理が開始される
とシンドローム生成回路２でシンドロームを生成するた
めにＲＡＭ１より読みだされる。シンドローム生成回路
２ではＲＡＭ１より読み出されたデータ（受信多項式形
式）を生成多項式で除算しシンドロームを生成する。な
お、ＲＡＭ１から再生データを読み出すための読み出し
アドレス、及び読み出し制御信号は誤り訂正装置制御回
路４より出力される。

【００１９】図27に回路構成を示すシンドローム生成回
路２はシフトレジスタ形式に配置されたレジスタ10と、
入力データ（帰還データ）に生成多項式の各項に対応す
る係数データを乗算する乗算回路11と、加算回路12とで
構成されている。シンドローム生成回路２では入力され
たデータを上記演算回路で逐次演算しながらシフトして
行くことによってガロア体上の多項式の除算を実行す
る。従って、演算を実行するに当たっては符号長分のス
テップ数（ｎステップ）を要する。なお、シンドローム
生成回路２の詳細は、今井秀樹著「符号理論」, 出版電
子情報通信学会,pp.115〜118 に記載されている。

【００２０】上記の要領で、シンドローム生成回路２で
生成されたシンドロームは、シンドローム生成終了信号
とともに、誤り訂正演算回路３及び誤り訂正装置制御回
路４へ出力される。誤り訂正装置制御回路４では、シン
ドローム生成終了信号をもとに誤り訂正演算回路３へユ
ークリッド演算開始信号を出力する。誤り訂正演算回路
３では、ユークリッド演算開始信号が入力されると、シ
ンドローム生成回路２より出力されたシンドロームをも
とに、ユークリッド演算回路20で誤り位置多項式σ
（ｚ）及び誤り数値多項式ω（ｚ）を算出する。

【００２１】以下、図29に示すユークリッド演算回路20
の除算部分の回路動作を説明する。シンドローム生成終
了信号が入力されると各レジスタ52には初期値がセット
される。具体的には上側のレジスタ52a 群にはＺ^2tがセ
ットされ、下側のレジスタ52b 群にはシンドローム生成
回路２により算出されたシンドローム多項式の係数がセ
ットされる。セットされたデータは被除数側（最初はＺ
^2tのデータがセットされた上側のレジスタ52a 群）のデ
ータをシフトしていくことによりガロア体上の多項式の
除算を実行する。除算は被除数側の多項式の次数が除数
側の多項式の次数より小さくなるまで繰り返す。図29に
おいて、被除数側のレジスタ52群に接続されているセレ
クタ53は加算回路55の出力を選択するように接続され、
除数側のレジスタ52群に接続されているセレクタ53はレ
ジスタ52の出力を選択するように構成する。この結果被
除数側のレジスタ52内のデータはシフトされ除算が実行
されることになる。

【００２２】除算の結果、被除数側のレジスタ群には上
記除算の余りが格納されることになる。次に除数レジス
タ群に格納されている多項式を被除数として、また上記
除算結果の余りを除数として除算を行なう。これは、セ
レクタ53の出力を切り換えることにより除数、被除数の
切り換えを実行する。この動作を図25に示すアルゴリズ
ムの終了条件が満たされるまで繰り返す。上記条件が満
たされると、ユークリッド演算回路20では誤り位置多項
式、及び誤り数値多項式の係数データを算出し、ユーク
リッド演算終了信号とともにチェンサーチ回路21、及び
誤り訂正制御回路４へ出力する。なお、ユークリッド演
算回路20の除算回路部分の説明は特開平1-276825号公報
に記載されている。

【００２３】誤り訂正装置制御回路４では、ユークリッ
ド演算回路20より出力されるユークリッド演算終了信号
をもとにチェンサーチ回路21の動作を開始させるチェン
サーチ開始信号を出力する。チェンサーチ回路21では、
チェンサーチ開始信号が入力されるとユークリッド演算
回路20で算出された誤り位置多項式σ（ｚ）の各係数を
もとに誤り位置を算出する。図30を用いてチェンサーチ
回路21の具体的な動作を説明する。チェンサーチ回路21
ではチェンサーチ開始信号が入力されると係数カウンタ
35に０がセットされるとともに、帰還レジスタ31内にユ
ークリッド演算回路20で演算された誤り位置多項式σ
（ｚ）の各係数データがセットされる。そして、帰還レ
ジスタ31の出力は乗算回路32にあらかじめセットされて
いる乗数と乗算され、再び帰還レジスタ31でラッチされ
る。

【００２４】加算回路33では、各帰還レジスタ31の出力
を加算する。判定回路34では、前記加算結果が０である
かを判定し、０であった場合係数カウンタ35のカウント
値をレジスタ36へ書き込む。（このカウント値が誤り位
置に対応する。）チェンサーチ終了にあたってはｎステ
ップ要することになる。なお、チェンサーチ回路21の詳
細は前述の「符号理論」, pp.165〜166 に記載されてい
る。

【００２５】誤り訂正回路22では、まずはじめにチェン
サーチ回路21より出力される誤り位置情報をもとにＲＡ
Ｍ１内に格納されている誤ったデータを読みだす。それ
と同時に誤り訂正回路22内では、ユークリッド演算回路
20より出力される誤り数値多項式ω（ｚ）、及びチェン
サーチ回路21より出力される誤り位置情報により誤り数
値を求める。ＲＡＭ１より読みだされた誤ったデータ
は、前述の誤り数値と加算され誤り訂正が施される。誤
り訂正が施されたデータはＲＡＭ１内の誤ったデータと
書き換えられる。

【００２６】上述のような誤り訂正装置を例えばディジ
タルＶＴＲに適用した場合の誤り訂正装置の符号、及び
復号の簡単なフローを図31に示す。図31において誤り訂
正装置に入力されたデータは複数個の単位情報ブロック
に分割される。一般に誤り訂正符号は２重符号化される
ことが多く、その場合、上記複数個に分割された単位情
報ブロックが複数個集められ図32に示すように２次元に
配置される。そして、誤り訂正符号化装置により、垂直
方向の誤り訂正符号（Ｃ２符号）が付加された後、記録
方向の誤り訂正符号（Ｃ１符号）が付加される。なお、
図32に示す符号構成は文献 ”AN EXPERIMENTAL HOME-US
E VCR WITH THREE DIMENSIONAL DCT ANDSUPERIMPOSED C
ORRECTION CODING”IEEE TRANSACTIONS ON CONSUMER EL
ECTRONICS AUG.1991 VOL.37 NUMBER3 に記載されている
家庭用ディジタルＶＴＲに用いられる誤り訂正符号の１
構成例である。また、図33には図32に示す記録方向の１
ラインの符号構成を示す。誤り訂正符号の付加されたデ
ータは、ディジタルＶＴＲの場合は記録媒体に記録さ
れ、通信の場合は通信路上へ送出される。記録媒体より
再生されたデータは、再生過程で発生する誤りを訂正す
るために誤り訂正処理が施される。誤り訂正処理過程で
は再生データ中に含まれる誤りを訂正、または検出す
る。誤り訂正が施された再生データは次のステップへ出
力される。

【００２７】次に、従来の誤り訂正装置で図33に示す１
ラインのデータを復号する場合の各部の信号処理タイミ
ングを図34に示すタイミングチャートを用いて説明す
る。図34には誤り訂正装置制御回路４より出力される各
種制御信号（シンドローム生成開始信号、ユークリッド
演算開始信号、チェンサーチ開始信号、及び誤り訂正開
始信号）、各回路の動作タイミング（シンドローム生成
回路２のシンドローム生成タイミング、ユークリッド演
算回路20の演算タイミング、チェンサーチ回路21の演算
タイミング、及び誤り訂正回路22の誤り訂正タイミン
グ）、及びＲＡＭ１のデータアクセス状態を示す。誤り
訂正装置制御回路４では誤り訂正が開始されるとシンド
ローム生成回路２へシンドローム生成開始信号を出力す
るとともにＲＡＭ１に格納されている再生時に発生した
誤りを含む再生データを読みだすための読みだしアドレ
ス、及び制御信号を出力する。シンドローム生成回路２
ではシンドローム生成開始信号にもとづきレジスタ10内
の値を０にセットするとともにＲＡＭ１より読みだされ
たデータに対して所定の演算（除算）処理を行う。な
お、上述のようにシンドローム生成にあたっては演算終
了まで符号長に相当する241 ステップを要する。この演
算時間を図34中のＳＹ部に示す。

【００２８】シンドローム生成が終了すると、シンドロ
ーム生成回路２よりシンドローム生成終了信号が出力さ
れる。誤り訂正装置制御回路４ではこのシンドローム生
成終了信号にもとづきユークリッド演算開始信号を出力
する。ユークリッド演算回路20ではユークリッド演算開
始信号にもとづき上述の要領でＧＦ（２⁸ ）上の多項式
の除算を行い、誤り位置多項式σ（ｚ）及び誤り数値多
項式ω（ｚ）を算出する。なお、ユークリッドアルゴリ
ズムを用いて、本従来例で示す最小距離17のリード・ソ
ロモン符号を復号（誤り位置多項式、及び誤り数値多項
式の算出）する場合、上述の多項式同士の除算を最大８
回繰り返すことにより算出できる。この演算時間を図34
中のＥＵ部に示す。この際のステップ数はユークリッド
演算回路20の全体の回路構成にもよるが、図33に示す最
小距離17のリード・ソロモン符号をユークリッドアルゴ
リズムを用いて誤り位置多項式σ（ｚ）、及び誤り数値
多項式ω（ｚ）を算出するために必要なステップ数は12
0 ステップ程度で実現できる。回路の詳細動作の説明は
省略するが、上記除算回路での除算動作と、データのセ
ット、制御信号の発生、誤り位置多項式σ（ｚ）及び誤
り数値多項式ω（ｚ）の算出、または本従来例では省略
したがイレージャがあった場合の修正シンドロームの算
出などにより約120 ステップ程度ユークリッド演算回路
20での復号時間が必要になる。

【００２９】ユークリッド演算が終了するとユークリッ
ド演算回路20よりユークリッド演算終了信号が出力され
る。誤り訂正装置制御回路４ではこのユークリッド終了
信号にもとづきチェンサーチ開始信号を出力する。チェ
ンサーチ回路21ではチェンサーチ開始信号に基づき係数
カウンタ35に０がセットされるとともに、ユークリッド
演算回路20で算出された誤り位置多項式の各係数データ
が各帰還レジスタ31にセットされる。そして帰還レジス
タ31の出力は乗算回路32にあらかじめセットされている
乗数と乗算され、再び帰還レジスタ31でラッチされる。
係数カウンタ35は帰還カウンタ31の帰還数をカウントす
る。加算回路33では各帰還レジスタ31の出力を加算す
る。判定回路34では前記加算結果が０であるかを判定
し、０であった場合には係数カウンタ35のカウント値を
レジスタ36へ書き込む。なお、上述のようにチェンサー
チ回路21では誤り位置を算出するために最大、符号長分
のステップ数すなわち241 ステップを必要とする。この
演算時間を図34中のＣＨ部に示す。

【００３０】チェンサーチが終了するとチェンサーチ回
路21よりチェンサーチ終了信号が出力される。誤り訂正
装置制御回路４ではこのチェンサーチ終了信号にもとづ
き誤り訂正開始信号を出力する。誤り訂正回路22の詳細
なタイミングチャートを図35に示す。誤り訂正回路22で
は誤り訂開始信号に基づき誤り数値多項式ω（ｚ）、及
びチェンサーチ回路21より出力される誤り位置情報を用
いて誤り数値を算出する。一方、誤り訂正装置制御回路
４では、上述の誤り位置情報にもとづきＲＡＭ１より誤
ったデータを読みだす。ＲＡＭ１より読みだされた誤っ
たデータは、次のクロックのタイミングで誤り数値と加
算され誤り訂正が施される。誤り訂正が施されたデータ
は次のクロックで再びＲＡＭ１へ書き込まれる。従っ
て、誤り訂正回路22で１シンボルの誤り訂正を実行する
ためには３クロックの期間を最低要することになる。よ
って、８シンボルの誤り訂正を行うためには最低24ステ
ップを必要とすることになる。

【００３１】誤り訂正装置は、ＣＤ, ＤＡＴまたはディ
ジタルＶＴＲ等において再生、または受信信号中に発生
する誤りを訂正するためには無くてはならない装置では
あるが従来の誤り訂正装置は以下の問題点を有する。問
題点の１つは、従来の誤り訂正装置は１ラインの誤り訂
正を行う際に必要とする復号時間が、図34に示すように
非常に長くなってしまうという点にある。本従来例の場
合、ユークリッド演算回路20の除算回路部分で高速演算
のための回路アーキテクチャーを採用し高速化を図った
にも係わらず図33に示す１ラインのＣ１ブロックを復号
するのに626 ステップ（241+120+241+24=626）の復号時
間を要する。図29に示すような、ユークリッド演算回路
20の高速化のための回路アーキテクチャはいくつか公開
特許公報等で紹介されている。しかしながら、ユークリ
ッド演算回路20での演算時間が短縮されても、シンドロ
ーム生成またはチェンサーチ等の処理時間が短縮され
ず、ディジタルＶＴＲのようにリアルタイムでかつ、高
速信号処理を要求される場合には必要な処理速度が維持
できない場合が生じる。

【００３２】誤り訂正装置の高速化に関する回路構成が
特開平3-63973 号公報で紹介されている。これは、図28
に示すシンドローム生成回路２及び誤り訂正演算回路３
を並行動作させるものである。図36に示すタイミングチ
ャートを用いてこの誤り訂正装置の回路動作を説明す
る。並行動作開始信号をもとにシンドローム生成回路２
はシンドローム生成を開始する。それと同時に誤り訂正
演算回路３中のユークリッド演算回路20が上述の要領で
ユークリッドアルゴリズムにしたがい誤り位置多項式σ
（ｚ）及び誤り数値多項式ω（ｚ）を算出する。ユーク
リッド演算回路20での演算が終了すると誤り位置多項式
の係数データをもとにチェンサーチ回路21で誤り位置の
算出が行なわれる。チェンサーチ回路21で誤り位置が算
出されると誤り訂正回路22で誤り訂正が施される。な
お、シンドローム生成回路２、ユークリッド演算回路2
0、チェンサーチ回路21、及び誤り訂正回路22の動作は
上記従来例と同一であるので詳細動作は説明は省略す
る。図36に各回路での演算ステップ数を示す。なお、図
36には上記従来例と同様に誤り訂正装置制御回路４より
出力される各種制御信号の出力タイミング、各回路の動
作タイミング、及びＲＡＭ１のデータアクセス状態を示
す。シンドローム生成回路２、及び誤り訂正演算回路３
を並行動作させることにより、図33に示す１ラインのＣ
１ブロックの誤り訂正を行なうために必要なステップ数
は最低385 ステップ必要になる。

【００３３】しかしながら、この従来例でも図32に示す
ような積符号形式のリード・ソロモン符号を復号するに
あたってはＣ１符号による誤り訂正終了後に、Ｃ２符号
による誤り訂正を施すため復号ステップ数が非常に大き
くなってしまいリアルタイムで復号できない。また、Ｃ
２復号はＣ１復号が施されたデータに対して行なわれる
ため再度同一のＲＡＭからデータを読み出さなければな
らない。その結果、誤り訂正装置を並列に配置し並行処
理を行うなどの対策を講じなければならず回路規模が増
大してしまう等の問題点があった。

【００３４】また、図27，図30に示すように、シンドロ
ーム生成回路２及びチェンサーチ回路21はレジスタの出
力にガロア体上の定数値との乗算回路と、加算回路とが
直列または並列に配置されている。この際、ハードウェ
ア上では最大で４段のＥＸ−ＯＲゲートを通ることにな
る。それに対してユークリッド演算回路20上ではハード
ウェア構成にもよるが、ＥＸ−ＯＲゲートを７段程度
と、数個のセレクタを通るため高速化がシンドローム生
成回路２及びチェンサーチ回路21に比べて困難であると
いう問題点があった。また、図29に示すユークリッド演
算回路20の回路規模が必要以上に大きいという問題点が
あった。また、誤り訂正回路22での１シンボルの誤り訂
正を行うためには最低３ステップを必要とし高速化にお
いて問題があった。

【００３５】最近になりディジタルＶＴＲの開発が各社
で進められており、誤り訂正装置の高速化が重要な課題
となってきた。図37に特開平3-172027号公報に記載され
ている、従来のユークリッド演算を行なう際のガロア体
上で定義される多項式同士の除算回路部（以下、コア回
路と記す）のブロック構成図を示す。なお、以下に説明
する加算回路, 乗算回路及び除算回路はガロア体上の加
算, 乗算及び除算演算を実行するものとして説明を続け
る。

【００３６】図において、81a, 81bは被除多項式, 除多
項式の係数データを記憶するレジスタ、82, 83はレジス
タ81a とレジスタ81b とのどちらかの出力を選択するセ
レクタ、84は除算回路、85は乗算回路、86は加算回路、
95は入力端子、87, 88は次数検出回路でレジスタ81a, 8
1bに記憶されている多項式の次数を検出する。89は全体
の動作の制御を行うユークリッド演算制御回路であり、
セレクタ82, 83の制御を行うとともに次数検出回路87,
88より出力される次数判定結果によりユークリッドアル
ゴリズムの終了条件の判定等を行う。以上、レジスタ81
a, 81b、セレクタ82, 83、除算回路84、乗算回路85、加
算回路86、次数検出回路87, 88、及びユークリッド演算
制御回路89で上記ユークリッド演算回路中のガロア体上
の多項式同士の除算回路部（コア回路）は構成されてい
る。なお、本従来例では右側に配置されているレジスタ
に各多項式の高次の係数を記憶するように構成されてい
る。

【００３７】次に、上記回路構成で除算を実行する際の
除算回路の動作原理を簡単に説明する。いま、被除多項
式及び除多項式をそれぞれ 被除多項式：Ｍ１（Ｚ）＝Ａ_n Ｚⁿ ＋Ａ_n-1 Ｚ^n-1 ＋・
・・＋Ａ₁ Ｚ¹ ＋Ａ₀ 除多項式：Ｍ２（Ｚ）＝Ｂ_m Ｚ^m ＋Ｂ_m-1 Ｚ^m-1 ＋・・
・＋Ｂ₁ Ｚ¹ ＋Ｂ₀ とする。なお、ｎ＞ｍとする。以下、筆算により上記除
算を行った場合の計算手順を数１に示す。

【００３８】

【数１】

【００３９】数１に示すように計算は被除多項式の剰余
の次数が除多項式の次数よりも小さくなるまで繰り返
す。なお、数１では最終の剰余多項式の各係数データを
Ｃ_i （ｉ＝０, １, ２, ・・・・, ｍ−１）で表わす。

【００４０】図25に示すユークリッドアルゴリズムに従
うと剰余多項式： Ｒ（Ｚ）＝Ｃ_m-1 Ｚ^m-1 ＋Ｃ_m-2 Ｚ^m-2 ＋・・・＋Ｃ₁
Ｚ＋Ｃ₀ の次数が予め定められた条件を満たしていない場合は上
記除多項式Ｍ２（Ｚ）を被除多項式とし、また上記剰余
多項式Ｒ（Ｚ）を除多項式として、除算を繰り返す。そ
の際、詳細は後述するが図37に示す除算回路ではセレク
タ82, 83を切り換えて除多項式と被除多項式との交換を
行う。

【００４１】同様に、数２にＭ２（Ｚ）をＲ（Ｚ）で除
算した場合の計算手順を示す。

【００４２】

【数２】

【００４３】なお、本筆算では便宜上、上記剰余多項式
Ｒ（Ｚ）の最大次数Ｃ_m-1 は０でないものとする。（一
般に、０であった場合は図37に示す次数検出回路87, 88
で上記被除多項式、及び除多項式の次数を判定して被除
多項式、及び除多項式の最大次数が０でなくなるまで被
除多項式、及び除多項式の係数データをシフトした後、
除算を実行する。また、除算演算中の剰余多項式の最大
次数が０に成った場合も同様に剰余多項式の最大次数が
０でなくなるまで剰余多項式の係数データをシフトした
後に、除算動作を行なう。）数１と同様に被除多項式の
剰余の係数が除多項式の次数よりも小さくなるまで除算
動作を繰り返す。

【００４４】その結果の剰余多項式（Ｒ’（Ｚ）とす
る）の各係数データをＤ_i （ｉ＝０、１，２，・・・，
ｍ−２）で表わす。そして、Ｒ’（Ｚ）の次数が図25に
示した条件を満たしていない場合上記Ｒ（Ｚ）を被除多
項式として、Ｒ’（Ｚ）を除多項式として除算を繰り返
す。その際、図37の除算回路では先ほどと同様にセレク
タ82, 83を切り換えて除多項式と被除多項式の交換を行
う。そして、この動作をユークリッドアルゴリズムの終
了条件を満たすまで実行する。

【００４５】また、図38, 39には従来例のガロア体上の
多項式同士の除算回路動作を説明するための原理図を示
す。図38, 39において90は被除多項式の係数データを記
憶するレジスタ、91は除多項式の係数データを記憶する
レジスタ、92は除算回路、93は乗算回路、94は加算回
路、95は入力端子である。以上、レジスタ90, 91、除算
回路92、乗算回路93、及び加算回路94でガロア体上の多
項式同士の除算回路は構成されている。なお、図38, 39
はガロア体上の多項式同士の除算の動作を説明するため
の図であるため、ユークリッドアルゴリズムによる交換
手段などは省略している。また、説明を簡単にするため
次数検出回路は省略してある。

【００４６】以下、図38, 39に示すシフトレジスタ構成
でガロア体上の多項式同士の除算を行なう場合の回路動
作を説明する。図38, 39に示す除算回路の構成で、 被除多項式：Ａ（Ｚ）＝Ｚ⁸ ＋Ｚ⁷ ＋Ｚ⁵ ＋Ｚ² ＋１ 除多項式：Ｂ（Ｚ）＝Ｚ⁶ ＋Ｚ³ ＋Ｚ² ＋１ の割り算を行なう場合について説明する。

【００４７】本従来例では、被除多項式Ａ（Ｚ）の各係
数がレジスタ90に、除多項式Ｂ（Ｚ）の各係数データが
レジスタ91にセットされる。ガロア体上の多項式同士の
除算は被除多項式Ａ（Ｚ）の各係数データが記憶されて
いるシフトレジスタ状に配置されたレジスタ90の内容を
逐次右側にシフトしながら演算する事により実行する。
図38, 39には上記被除多項式Ａ（Ｚ）を除多項式Ｂ
（Ｚ）で除算する場合の各レジスタ内の係数データの内
容を示す。

【００４８】まず始めに、図38(a) に示すようにレジス
タ10に被除多項式Ａ（Ｚ）の係数がセットされ、レジス
タ91に除多項式Ｂ（Ｚ）の各係数データがセットされ
る。なお、本従来例では右端のレジスタより高次の項の
係数がセットされているものとする。図中レジスタ内に
記した数字は、各レジスタにセットされた係数データを
示す。図38(a) に示す状態より除算回路92, 乗算回路93
及び加算回路94で演算を各係数毎に行ないながら、被除
多項式の係数を右へ１つだけシフトすると結果は14(b)
に示すようになる。なお、除算回路92は被除多項式側の
最高次数の係数を除多項式側の最高次数の係数で除算す
るように構成されている。

【００４９】各係数の状態をレジスタ内の数字で示す。
すなわち、被除多項式の各係数データを記憶するレジス
タ90には被除多項式を除多項式で除算を行ない被除多項
式の次数を１次減らした時の剰余が自動的にセットされ
ることになり、これが次回の除算で被除多項式となる。
同様にして２回目の除算を行なうと、図39(a) に示すよ
うに剰余がレジスタ90にセットされる。同様に３回目の
除算を行なった結果を図39(b) に示す。この除算動作は
被除多項式の次数が除多項式の次数より小さくなるまで
繰り返される。本従来例では被除多項式Ａ（Ｚ）と除多
項式Ｂ（Ｚ）との次数差が２次であるので、上記除算動
作を３回繰り返せばよい。

【００５０】以上の処理を筆算により確認する。数３に
筆算でガロア体上の多項式同士の除算（上記Ａ（Ｚ）／
Ｂ（Ｚ））を行なった場合の計算過程を示す。

【００５１】

【数３】

【００５２】各段階の剰余は数３に示すように図38(a),
(b),図39(a),(b) の状態に対応したものとなっている。
このとき、レジスタ90に格納されているデータは被除多
項式を除多項式で除算した時の剰余多項式の係数データ
が記憶されている。よって、図38, 39に示すようなシフ
トレジスタ構成の除算回路を用いることによりガロア体
上の多項式同士の除算を１多項式毎に行えることにな
る。

【００５３】以下、図25に示すユークリッドアルゴリズ
ムに従い、リード・ソロモン符号を復号する誤り訂正装
置のユークリッド演算の除算回路部の動作を図37を用い
て説明する。本従来例では、光ディスク等に採用されて
いる最小ハミング距離が17のリード・ソロモン符号を復
号する場合について説明する。いま、再生信号より生成
したシンドローム多項式Ｓ（Ｚ）を Ｓ（Ｚ）＝Ｓ₁₅Ｚ¹⁵＋Ｓ₁₄Ｚ¹⁴＋Ｓ₁₃Ｚ¹³＋・・・Ｓ₁
Ｚ＋Ｓ₀ とする。

【００５４】ユークリッド演算が開始されるとまず始
め、ユークリッド演算制御回路89より出力されるユーク
リッド演算開始信号をもとにレジスタ81a に初期値であ
る被除多項式Ｚ^2t（本従来例では最小距離が17の符号で
あるのでＺ¹⁶）の係数が記憶されるとともに、レジスタ
81b に除多項式であるシンドローム多項式Ｓ（Ｚ）の係
数データが記憶される。また、次数検出回路87, 88のカ
ウンタにはそれぞれ次数の初期値である16と15とがセッ
トされる。次数検出回路87, 88内のカウンタは被除多項
式の係数データを記憶しているレジスタ81a, 81bが１回
シフトされるたびにカウント値が１つ下がるように構成
されている。

【００５５】なお、本従来例では右側に配置されている
レジスタに高次の次数の係数データが記憶される。それ
と同時に、除多項式であるシンドローム多項式は次数検
出回路88で最高次数の係数データが０であるか判定され
る。ユークリッド演算制御回路89では、次数検出回路88
で検出された除多項式（シンドローム多項式）の最大次
数の係数データの値が０の場合、除多項式の係数データ
が記憶されているレジスタ81b の内容をシフトし最大次
数のデータが０でなくなるまでシフト動作を繰り返す。
その際、次数検出回路88内の次数カウンタのカウント値
が減らされていく。この動作が終了すると、セレクタ82
はレジスタ81a の出力を選択するように制御され、セレ
クタ83はレジスタ81b の出力を選択するように制御す
る。

【００５６】また、被除多項式の係数データが記憶され
ているレジスタ81a はクロックが入力されると加算回路
86の出力がラッチされるように構成されており、除多項
式の係数データが記憶されているレジスタ81b は係数デ
ータが保持されるように構成されている。図37には、具
体的な制御回路は省略したが、上記レジスタ81a, 81bに
入力されるクロック１, ２を除数側の係数データが記憶
されているレジスタについてのみ供給しないという方法
で除多項式の係数データをレジスタ内に保持する構成を
取っている。または、レジスタ81a, 81bの前段にセレク
タを設け、被除数側の係数の記憶されているレジスタに
ついては加算回路86の出力を選択するように、また除数
側の係数が記憶されているレジスタについては自分自身
の出力をラッチするように構成することにより実現する
こともできる。なお、図中に記した各演算回路（除算回
路84, 乗算回路85及び加算回路86）はガロア体上で定義
された各演算を行うものとする。

【００５７】以下、図40, 41を用いて上記従来のユーク
リッド演算回路中の除算回路の回路動作を説明する。図
40(a) にレジスタ81a に被除多項式として初期値である
Ｚ¹⁶がセットされ、レジスタ81b に除多項式としてシン
ドローム多項式Ｓ（Ｚ）がセットされた状態を示す。な
お、レジスタ中に記した数字及び記号はレジスタに格納
されている係数データを示すものとする。本従来例では
説明を簡単にするためシンドローム多項式の最高次の係
数は０でないものとする。また、レジスタに記憶される
各多項式の高次の次数の係数データは右端に配置される
ものとする。そして、この図においては動作の説明をす
るため、各々のレジスタ81a, 81bの出力はセレクタ82,
83が選択している除算回路84, 乗算回路85及び加算回路
86に直接接続してある。

【００５８】図40, 41に示す除算回路は図38, 39で示し
た除算回路と同一の構成をとっており、被除多項式の剰
余の次数が、除多項式の次数より小さくなるところまで
シフト動作を繰り返すことにより除算を実行する。除算
の終了判定は次数検出回路87, 88より出力される次数情
報をもとにユークリッド演算制御回路89で行う。図40
(b) に上記除算が終了した際に、各レジスタ81a, 81bに
記憶されている係数データの状態を示す。なお、レジス
タ81a に記憶されているＨ₁₄〜Ｈ₀ は剰余多項式の係数
データである。

【００５９】次に、ユークリッド演算制御回路89では、
次数検出回路87（または88）より出力される上記剰余多
項式の次数をもとに、剰余の次数がユークリッド演算の
終了条件（本従来例では次数が７以下）を満たしていれ
ばユークリッド演算を終了し、終了条件を満たしていな
ければ前回の演算で除多項式であった多項式を被除多項
式として、また上記剰余多項式を除多項式として演算を
実行する。その際、図37に示すユークリッド演算回路中
の除算部回路（コア回路）では、除多項式（剰余多項
式）の最大次数が０であるかを判定し０であった場合は
除多項式（剰余多項式）の最大次数が０でなくなるまで
レジスタ81a の内容をシフトした後、セレクタ82, 83の
選択出力を切り換えてセレクタ82はレジスタ81b の出力
を選択し、セレクタ83はレジスタ81a の出力を選択する
ように制御信号を出力する。

【００６０】図41(a) に上記の接続状態を示す。図に示
すようにセレクタ82, 83で各演算回路への接続を切り換
えることにより被除多項式と除多項式の交換が実行され
ている。（なお、回路構成は図38, 39に示す除算回路と
同一の構成となっている。）除算は、上記例と同様に被
除多項式の剰余の次数が除多項式の次数より小さくなる
まで被除多項式の係数データを記憶しているレジスタの
内容を演算しながらシフト動作を繰り返すことにより除
算を実行する。図41(b) に上記除算が終了した際に、各
レジスタ81a, 81bに記憶されている係数データの状態を
示す。なお、レジスタ81b に記憶されているＩ₁₃〜Ｉ₀
は剰余多項式の係数データである。

【００６１】そして、上記剰余多項式の次数を判定し所
定の条件を満たしていなければセレクタ82, 83の接続を
切り換えてユークリッドアルゴリズムに基づく除算動作
を再び行う。この除算動作を剰余多項式の次数が７次以
下になるまで繰り返す。これにより、リード・ソロモン
符号を復号する際に、ユークリッドアルゴリズムに基づ
くガロア体上の多項式同士の除算を１多項式毎に行うこ
とができ、誤り訂正処理速度を向上させることが出来
る。

【００６２】従来の誤り訂正装置のユークリッド演算回
路中のガロア体上の多項式同士の除算部回路（コア回
路）はユークリッド演算を高速化するため上記のように
構成されているが、ユークリッド演算を行う時、多項式
同士の交換を行うために各レジスタの出力がセレクタに
接続されており、例えば上記従来例に示す光ディスクの
誤り訂正符号として採用されている最小ハミング距離が
17の符号を復号する際はセレクタが各レジスタ毎に必要
となり、セレクタの制御も必要となる。このため、回路
規模が必要以上に大きくなってしまい、また、これらの
セレクタを制御するためセレクタ制御回路、及び制御信
号用バスが必要となってくる。すなわち、特開平3-1720
27号公報で紹介されているユークリッド演算過程におけ
るガロア体上の多項式の除算部回路（コア回路）は、上
記多項式の除算を高速に行うことが出来るが不必要に回
路規模が大きくなり、また制御も複雑になるという問題
点があった。

【００６３】本発明は斯かる事情に鑑みてなされたもの
であり、本発明の１つの目的は、高速動作が可能である
誤り訂正装置を提供することにある。

【００６４】本発明の他の目的は、回路規模を大きくす
ることなく高速動作を可能とした誤り訂正装置を提供す
ることにある。

【００６５】本発明の更に他の目的は、不必要な制御を
必要としない誤り訂正装置を提供することにある。

【００６６】

【課題を解決するための手段】本願の第１発明に係る誤
り訂正装置は、入力信号に付加されている線形符号であ
る誤り訂正符号を用いて誤り訂正を行なう誤り訂正装置
であって、入力信号からシンドロームを生成するための
シンドローム生成手段と、生成されたシンドロームをも
とに誤り位置多項式σ（ｚ）及び誤り数値多項式ω
（ｚ）を算出する誤り位置・数値多項式演算手段と、算
出された誤り位置多項式σ（ｚ）を基に誤り位置を算出
する誤り位置算出手段と、算出された誤り数値多項式ω
（ｚ）及び誤り位置情報を基にＲＡＭ内に格納されてい
る誤ったデータの誤り訂正を行う誤り訂正手段とを有
し、誤り訂正時に、少なくともシンドローム生成手段，
誤り位置・数値多項式演算手段及び誤り位置算出手段の
３つの処理動作を並行して行うように構成したものであ
る。

【００６７】本願の第２発明に係る誤り訂正装置は、第
１発明にあって、シンドローム生成手段及び誤り位置算
出手段を駆動するクロックを、誤り位置・数値多項式演
算手段を駆動するクロックより高い周波数のクロックと
するように構成する。

【００６８】本願の第３発明に係る誤り訂正装置は、第
１発明にあって、回路規模が復号時のステップ数でほぼ
決定する誤り位置・数値多項式演算手段の復号ステップ
数をシンドローム生成手段及び誤り位置算出手段の復号
ステップ数とほぼ等しくなるように増加させるように構
成する。

【００６９】本願の第４発明に係る誤り訂正装置は、第
１発明にあって、誤り訂正手段によりＲＡＭ内のデータ
に誤り訂正を施す際に誤り位置算出手段より出力される
誤り位置情報に基づく誤ったデータを少なくとも２つ以
上を連続してＲＡＭより読み出した後に、誤り訂正を施
したデータを逐次ＲＡＭ内の誤ったデータとに書き換
え、この動作を誤り位置検出されたデータがすべて訂正
されるまで繰り返すように構成する。

【００７０】本願の第５発明に係る誤り訂正装置は、所
定の被除多項式を除多項式で除算し、さらにその剰余を
除多項式として、また除多項式を被除多項式として除算
して剰余の多項式の次数がある条件を満たすまで上記動
作を繰り返すユークリッド互除の処理過程を含んでリー
ド・ソロモン符号による誤り訂正処理を行う誤り訂正装
置であって、被除多項式及び除多項式の各係数データを
記憶しておくレジスタをシフトレジスタ状に配置し、そ
して、この２つの多項式の最大次数の係数同士を除算す
る除算回路と、除算回路の除数側に設定された多項式の
係数データと除算回路の出力とを乗算する乗算回路と、
乗算回路の出力と除算回路の被除数側に設定された多項
式の係数データとを加算する加算回路とを配置し、ガロ
ア体上の除算を実行する際に被除多項式の係数データが
記憶されているレジスタの内容を逐次シフトすることに
よりユークリッド互除過程に基づく除算を実行するよう
に構成する。

【００７１】本願の第６発明に係る誤り訂正装置は、第
５発明において、乗算回路をユークリッド互除過程にお
ける初期値Ｚ^2tをセットするレジスタ群に配置するよう
に構成する。

【００７２】本願の第７発明に係る誤り訂正装置は、第
５または第６発明において、除算回路において、除数と
して入力される多項式の最大次数の係数が０であった場
合、除算回路の出力を１として出力するように構成す
る。

【００７３】本願の第８発明に係る誤り訂正装置は、第
５または第６または第７発明において、除算回路より出
力される除算結果を用いて誤り位置多項式σ（Ｚ）を算
出する際、除算回路に入力される被除多項式の最大次数
の係数データが除数として扱われる場合と被除数として
扱われる場合とで算出方法を切り換えるように構成す
る。

【００７４】本願の第９発明に係る誤り訂正装置は、第
５または第７または第８発明において、除算回路の出力
と誤り位置情報とを選択する第１の選択手段と、除算回
路の除数側の多項式の係数を記憶しておく記憶手段の出
力と、除算回路の被除数側の多項式の係数データを記憶
しておく記憶手段の出力とを選択する第２の選択手段
と、除算回路の除数側の多項式の係数とそれより１次次
数が高い除算回路の除数側の多項式の係数とを選択する
第３の選択手段と、第１の選択手段の出力と第３の選択
手段の出力とを乗算する乗算手段と、この乗算手段の出
力と第２の選択手段の出力とを加算する加算手段とを有
し、消失訂正時に修正シンドローム多項式を演算する
際、第１，第２及び第３の選択手段でそれぞれ誤り位置
情報，除算回路の除数側の多項式の係数データ及び１次
次数が高い多項式の係数を選択するように構成する。

【００７５】

【作用】第１発明の誤り訂正装置は、再生または受信信
号中の誤りを訂正する際、シンドローム生成手段，誤り
位置・数値多項式演算手段及び誤り位置算出手段の３つ
の処理手段を並行して動作するように構成したので、図
33に示す１誤り訂正ブロックに誤り訂正を行なう際の復
号時間を半分以下にすることができる。また、復号時に
高速化のネックとなる誤り訂正装置とＲＡＭとのデータ
のアクセスを常に行なうように構成したので、最も短い
復号時間で復号できる誤り訂正装置を得ることができ
る。（これは、先ほども述べたように図32に示すような
積符号形式の誤り訂正符号の復号を行なう場合、まずは
じめに受信データをＲＡＭ内に書き込み、Ｃ１及びＣ２
符号による誤り訂正を施す。このときＲＡＭ１ではシン
ドローム生成のためのデータの読み出し、誤り訂正を行
なうための誤りが検出されたデータの読み出し及び誤り
訂正が施されたデータの書き込みを行なう必要がある。
誤り訂正装置の高速化を考える際、ＲＡＭと誤り訂正装
置とのデータアクセスが非常に問題となっていた。）

【００７６】第２発明の誤り訂正装置は、比較的高速化
が図れるシンドローム生成手段と誤り位置算出手段との
クロック周波数を誤り位置・数値多項式演算手段のクロ
ックの周波数に比べて高くすることにより、１誤り訂正
ブロックを復号するのに要する復号時間を短縮すること
ができ処理速度を上げることが可能となる。

【００７７】第３発明の誤り訂正装置は、誤り位置・数
値多項式演算手段の復号ステップ数をシンドローム生成
手段または誤り位置算出手段の復号ステップ数と誤り訂
正回路の復号ステップ数とほぼ等しくなるように増加さ
せることにより、誤り位置・数値多項式演算手段の回路
規模を小さくするので、誤り位置・数値多項式演算手段
の復号ステップ数は増加するものの誤り訂正装置の復号
ステップ数は変化しないので誤り訂正装置の高速化を実
現することができる。

【００７８】第４発明の誤り訂正装置は、誤り訂正回路
の処理動作を誤り位置情報に基づきＲＡＭ内の誤ったデ
ータを逐次読み出した後に、誤り訂正が施されたデータ
をＲＡＭに書き込むので、通常１シンボルの誤り訂正を
行う際、ＲＡＭからのデータの読み出し、誤り訂正、Ｒ
ＡＭへのデータの書き込みと最低３ステップかかってい
た動作を、ＲＡＭよりのデータの読み出し、誤り訂正及
びＲＡＭへのデータの書き込みを平行動作させるので２
ステップで行うことが可能となり、誤り訂正装置の高速
化が図れる。特にＲＡＭとのアクセス時間が問題となる
場合にＲＡＭ１とのアクセス時間が減少するので高速化
が図れる。

【００７９】第５発明の誤り訂正装置は、ユークリッド
互除過程におけるガロア体上の多項式同士の除算を実行
する際、各多項式の係数データを交換するためのセレク
タをもたずにユークリッド互除過程中の除算を実行する
ので、回路規模の縮小を図れるとともにセレクタ制御が
不必要になり回路の簡素化が図れる。

【００８０】第６発明の誤り訂正装置は、乗算回路をユ
ークリッド互除過程における初期値Ｚ^2tをセットするレ
ジスタ群に配置して除算動作を行うので、除算動作を行
うため乗算回路の数を１つ削減して回路規模の縮小を図
れる。

【００８１】第７発明の誤り訂正装置は、ユークリッド
演算を行う際の除算回路中に配置されている除算回路の
出力を、除数として入力される多項式の最大次数の係数
が０であった場合、１とするように構成されているの
で、ユークリッド演算制御回路で被除多項式または除多
項式の最大次数が０であった場合でも、回路規模を増大
させることなくユークリッドアルゴリズムにおけるガロ
ア体上の多項式同士の演算を実行できる。

【００８２】第８発明の誤り訂正装置は、除算回路の出
力を用いて誤り位置多項式σ（Ｚ）を算出する際、除算
回路に入力される被除多項式の最大次数の係数データが
除数として扱われる場合と被除数として扱われる場合と
で算出方法を切り換えるので、誤り位置多項式が正確に
算出されるとともに、復号ステップ数を削減できる。

【００８３】第９発明の誤り訂正装置は、イレージャ訂
正を行う際に算出する修正シンドローム多項式の算出を
セレクタ回路を付加するだけで構成できるので、回路規
模の増大を極力抑えてイレージャ訂正にも対応できる。

【００８４】

【実施例】以下、本発明をその実施例を示す図面に基づ
いて詳述する。

【００８５】第１実施例．図１に本発明の第１実施例で
ある誤り訂正装置のブロック構成図を示す。図において
１, ２及び20〜22は図26及び図28に示したものと同一で
あるので説明は省略する。40はユークリッド演算回路20
より出力される誤り位置多項式及び誤り数値多項式の各
係数データを記憶するレジスタ、41はシンドローム生成
回路２，ユークリッド演算回路20，レジスタ40，チェン
サーチ回路21及び誤り訂正回路22を制御するとともに、
ＲＡＭ１の書き込み及び読み出し制御も行う誤り訂正装
置制御回路である。なお、シンドローム生成回路２、ユ
ークリッド演算回路20のガロア体上の多項式の除算回路
部分、及びチェンサーチ回路21の回路構成は図27，図29
及び図30に示すものと同一の構成であるので説明は省略
する。

【００８６】次に、本発明の第１実施例である誤り訂正
装置の動作を説明する。なお、本実施例では従来例と同
様に図33に示す最小距離17の記録方向のＣ１符号を復号
する場合について説明する。ＲＡＭ１に格納されている
再生または受信時に発生した誤りを含む再生または受信
データは、誤り訂正処理が開始されるとＣ１ブロック
（単位情報ブロック）を単位にＲＡＭ１より読みだされ
る。なお、ＲＡＭ１からの再生データの読みだしは、誤
り訂正装置制御回路41より出力されるシステムスタート
信号に同期して発生する読みだしアドレス、及び読みだ
し制御信号に基づき行われる。ＲＡＭ１より読みだされ
たデータはシンドローム生成回路２へ出力される。シン
ドローム生成回路２では誤り訂正装置制御回路41より出
力されるシステムスタート信号に基づきシフトレジスタ
形式に配置された各レジスタ10に０をセットする。そし
て、ＲＡＭ１より読みだされたデータを従来例と同様に
逐次演算を行いながらシフトすることにより除算動作を
実行する。シンドローム生成に当たっては従来例と同様
に符号長分の241 ステップを必要とする。シンドローム
生成回路２で生成されたシンドロームはシンドローム生
成終了信号とともにユークリッド演算回路20に出力され
る。シンドローム生成終了信号は誤り訂正装置制御回路
41へも出力される。ユークリッド演算回路20ではシンド
ローム生成回路２より出力されるシンドローム生成終了
信号に基づきユークリッド演算回路20での演算処理の初
期値をセットする。なお、ユークリッド演算回路20の演
算動作が終了していない場合にはユークリッド演算が終
了と同時に演算処理の初期値をセットする。

【００８７】一方、ユークリッド演算回路20では、誤り
訂正装置制御回路41より出力されるシステムスタート信
号に基づきシンドローム生成終了時にあらかじめセット
された初期値を元にユークリッド演算を開始する。ユー
クリッド演算回路20は、従来例と同様に図25に示すアル
ゴリズムに従いガロア体上の多項式の除算を繰り返し行
うことにより、誤り位置多項式σ（ｚ）及び誤り数値多
項式ω（ｚ）の算出を行う。図29を用いてユークリッド
演算回路20の回路動作を説明する。シンドローム生成終
了信号が入力されると各レジスタ52a, 52bには初期値が
セットされる。具体的には上側のレジスタ52a 群にはＺ
^2tがセットされ、下側のレジスタ52b 群には上記シンド
ローム生成回路２により算出されたシンドローム多項式
の係数データがセットされる。セットされたデータはシ
ステムスタート信号に基づき被除数側（最初はＺ^2tのデ
ータがセットされた上側のレジスタ52a 群）のデータを
シフトしていくことによりガロア体上の多項式の除算を
実行する。除算は被除数側の多項式の次数が除数側の多
項式の次数より小さくなるまで繰り返す。除算動作を具
体的に示すと次のようになる。図29において、被除数側
のレジスタ52群に接続されているセレクタ53は加算器55
の出力を選択するように接続され、除数側のレジスタ52
群に接続されているセレクタ53はレジスタ52の出力を選
択するように構成する。この結果、除数側のデータはレ
ジスタ52内に維持され、被除数側のレジスタ52内のデー
タはシフトされ除算が実行されることになる。

【００８８】除算の結果、被除数側のレジスタ群には上
記除算の余りが格納されることになる。次に除数レジス
タ群に格納されている多項式を被除数として、また上記
除算結果の余りを除数として除算を行なう。これは、セ
レクタ53の出力を切り換えることにより除数、被除数の
切り換えを実行する。この動作を図25に示すユークリッ
ドアルゴリズムの終了条件が満たされるまで繰り返す。
上記、条件が満たされるとユークリッド演算回路20では
誤り位置多項式及び誤り数値多項式の各係数データを算
出する。算出された各係数データは一旦レジスタ40に格
納される。なお、ユークリッド演算回路20は、ユークリ
ッド演算が終了すると誤り訂正装置制御回路41へユーク
リッド演算終了信号を出力する。

【００８９】同様にチェンサーチ回路21では誤り訂正装
置制御回路41より出力されたシステムスタート信号を基
準にしてレジスタ40に記憶されている誤り位置多項式の
係数データを帰還レジスタ31にセットするとともに、係
数カウンタ35のカウント値を０にセットする。そして、
従来例と同様に帰還レジスタ31の出力は乗算器32にあら
かじめセットされている乗数と乗算され、再び帰還レジ
スタ31でラッチされる。また、係数カウンタ35は帰還レ
ジスタ31の帰還回数をカウントする。

【００９０】帰還レジスタ31の出力は加算回路33で加算
される。判定回路34では、前記加算結果が０であるかを
判定し、０であった場合係数カウンタ35の値をレジスタ
36へ書き込む。従来例と同様にこのカウント値が誤り位
置に対応する。チェンサーチは符号長に相当する241 回
帰還レジスタ31を動作させ誤り位置を算出する。チェン
サーチが終了するとチェンサーチ終了信号が誤り訂正装
置制御回路41へ出力される。誤り訂正装置制御回路41で
はチェンサーチ終了信号，ユークリッド演算終了信号及
びシンドローム生成終了信号にもとづき誤り訂正開始信
号を誤り訂正回路22に出力する。

【００９１】誤り訂正装置制御回路41では、誤り訂正開
始信号を出力すると同時に、チェンサーチ回路21より出
力される誤り位置情報をもとにＲＡＭ１内に格納されて
いる誤ったデータを逐次読みだすための読み出しアドレ
ス及び読み出し制御信号を出力する。例えば、８誤り訂
正の場合８個の誤り位置情報に相当する８個の誤った情
報をＲＡＭ１より読み出す。一方、誤り訂正回路22で
は、入力された誤り訂正開始信号を基準にして誤り訂正
を開始する。まず始めに、誤り訂正回路22内では、ユー
クリッド演算回路20より出力される誤り数値多項式ω
（ｚ）、及びチェンサーチ回路21より出力される誤り位
置情報により誤り数値を求める。ＲＡＭ１より読みださ
れた誤ったデータは、誤り数値と加算され誤り訂正が逐
次施される。ＲＡＭ１からの誤った情報の読みだしが終
了すると、上記誤り訂正が施されたデータがＲＡＭ１内
の誤ったデータと逐次書き換えられる。図９に誤り訂正
回路22のタイミングチャートを示す。

【００９２】次に、第１実施例を用いて誤り訂正を施す
場合の、各回路部の信号処理タイミングを図２を用いて
説明する。図２には、誤り訂正装置制御回路41より出力
される各種制御信号の出力タイミング，各回路の動作タ
イミング及びＲＡＭ１のデータアクセス状態を示す。誤
り訂正装置制御回路41では誤り訂正が開始されるとシス
テムスタート信号をシンドローム生成回路２、ユークリ
ッド演算回路20、及びチェンサーチ回路21へ出力すると
ともにＲＡＭ１に格納されている再生データを読みだす
ための読みだしアドレス、及び制御信号を出力する。

【００９３】シンドローム生成回路２ではシステムスタ
ート信号にもとづきレジスタ10内の値を０にセットする
とともにＲＡＭ１より読みだされたデータに対して所定
の演算（除算）処理を行う。なお、上述のようにシンド
ローム生成にあたっては演算終了まで符号長に相当する
241 ステップを要する。この演算時間を図２中のＳＹ部
に示す。

【００９４】シンドローム生成が終了すると、シンドロ
ーム生成回路２より生成されたシンドロームデータとと
もにシンドローム生成終了信号が出力される。ユークリ
ッド演算回路20では、シンドローム生成終了信号に基づ
きユークリッド演算のための初期値をセットする。な
お、ユークリッド演算回路20の演算が終了していない場
合は、ユークリッド演算が終了しだい初期値をセットす
る。

【００９５】ユークリッド演算回路20ではシステムスタ
ート信号にもとづき上述の要領でＧＦ（２⁸ ）上の多項
式の除算を行い、誤り位置多項式σ（ｚ）及び誤り数値
多項式ω（ｚ）を算出する。なお、ユークリッド演算回
路20で図33に示す最小距離17のリード・ソロモン符号を
復号する場合、従来例と同様に約120 ステップ程度必要
とする。この演算時間を図２中のＥＵ部に示す。

【００９６】ユークリッド演算回路20によって算出され
た誤り位置多項式σ（ｚ）及び誤り数値多項式ω（ｚ）
の各係数データはレジスタ40に一旦記憶される。なお、
ユークリッド演算が終了するとユークリッド演算回路20
よりユークリッド演算終了信号が出力される。

【００９７】チェンサーチ回路21ではシステムスタート
信号に基づき係数カウンタ35に０がセットされるととも
に、ユークリッド演算回路20で算出された誤り位置多項
式の各係数データが各帰還レジスタ31にセットされる。
そして帰還レジスタ31の出力は乗算回路32にあらかじめ
セットされている乗数と乗算され、再び帰還レジスタ31
でラッチされる。係数カウンタ35は帰還カウンタ31の帰
還数をカウントする。加算回路33では各帰還レジスタ31
の出力を加算する。判定回路34では前記加算結果が０で
あるかを判定し、０であった場合には係数カウンタ35の
カウント値をレジスタ36へ書き込む。なお、上述のよう
にチェンサーチ回路21では誤り位置を算出するために最
大、符号長分のステップ数すなわち241 ステップを必要
とする。この演算時間を図２中のＣＨ部に示す。

【００９８】チェンサーチが終了するとチェンサーチ回
路21よりチェンサーチ終了信号が出力される。誤り訂正
装置制御回路41ではチェンサーチ終了信号，ユークリッ
ド演算終了信号及びシンドローム生成終了信号にもとづ
き誤り訂正開始信号を出力する。誤り訂正回路22では誤
り訂正開始信号に基づき誤り数値多項式ω（ｚ）、及び
チェンサーチ回路21より出力される誤り位置情報を用い
て誤り数値を算出する。そして、ＲＡＭ１より読み出さ
れた誤り位置を算出されたデータに誤り数値を加算する
ことにより誤り訂正を施す。誤り訂正が施されたデータ
は、ＲＡＭ１からの誤ったデータの読み出しが終了する
と同時にＲＡＭ１へ書き込まれる。図９に誤り訂正回路
22のタイミングチャートを示す。本実施例では８シンボ
ルの誤りを訂正するために16ステップを要する。なお、
図９に示す誤り訂正回路のタイミングチャートについて
の詳しい説明は後述する。

【００９９】誤り訂正装置制御回路41では、ＲＡＭ１，
シンドローム生成回路２，ユークリッド演算回路20，レ
ジスタ40，チェンサーチ回路21及び誤り訂正回路22の上
記動作を制御する。その際、シンドローム生成回路２，
ユークリッド演算回路20及びチェンサーチ回路21の３つ
の回路の並行動作を管理するため、誤り訂正装置制御回
路41では、システムスタート信号で各々の回路の動作フ
ラグをセットし、各々の回路より出力される演算終了信
号に基づき上記動作フラグをリセットする動作フラグ生
成回路を内部に持っており、このフラグの状態により各
回路を制御する。具体的には、この動作フラグの状態に
より、ＲＡＭ１のアドレス制御、各々の回路で算出され
たデータの転送、または各々の回路の初期値のセット等
の制御を行うための信号を各回路へ出力する。また、こ
の動作フラグは各回路へも出力される。

【０１００】誤り訂正開始信号はシンドローム生成回路
２とＲＡＭ１とのアクセス、及びチェンサーチ回路21で
の誤り位置の計算が終了すると同時に出力される。それ
と同時にチェンサーチ回路21で算出された誤り位置情報
を基に、ＲＡＭ１より誤ったデータを読み出すための読
みだしアドレス及び読みだし制御信号を発生する。

【０１０１】本実施例に示すように誤り訂正装置におい
て、シンドローム生成回路２，ユークリッド演算回路20
及びチェンサーチ回路21の３つの回路を並行動作するこ
とにより、図２に示すように１誤り訂正ブロックを復号
するステップ数を257 ステップとすることができ、従来
の誤り訂正装置に比べて約2.4 倍（626 /257）に復号速
度を上げることが可能である。また、シンドローム生成
回路２と誤り訂正演算回路３とを並行に動作せる場合に
比べても1.5 倍（386 /257）に復号速度を上げることが
可能である。よって、誤り訂正装置を並列に配置するこ
となく回路の高速化をはかることができ、並列に誤り訂
正装置を配置した場合に比べて回路規模の大幅な縮小を
図れる。

【０１０２】また、本実施例のように並行処理を行う誤
り訂正装置においては、ＲＡＭ１のデータアクセス時間
が誤り訂正装置の動作速度を決定する。特に図32に示す
積符号形式の誤り訂正符号を復号する際は、再生された
誤りを含むデータを一旦ＲＡＭ１内にデータを格納した
後に誤り訂正を施す。一般に、積符号形式の誤り訂正符
号の復号はＣ１符号により記録方向の誤り訂正を行なっ
た後にＣ２符号により垂直方向の誤り訂正を行ない、Ｃ
１符号により誤りを訂正できなかったデータに対してＣ
２符号により誤り訂正を行なう。（記録方向に付加され
たＣ１符号による誤り訂正を行なう場合は、ＲＡＭ１内
にデータを一旦格納せずに、再生データより直接シンド
ロームを生成して誤り訂正を施してもよいが、Ｃ２符号
による誤り訂正を行なう際は図32に示す誤り訂正ブロッ
クのデータを垂直方向に読み出す必要がある。よって、
Ｃ２符号による再生データの誤り訂正はＲＡＭ１内に一
旦蓄えられたデータに対して誤り訂正が施される。）

【０１０３】ＲＡＭ１内に一旦格納された再生データ
は、誤り訂正符号による誤り訂正を行なうためＲＡＭ１
より読み出される。ＲＡＭ１より読み出されたデータは
上述のように誤り訂正装置でシンドローム生成、誤り位
置の算出、及び誤り数値の算出が行なわれる。そして、
算出された誤り位置に相当するアドレスのデータがＲＡ
Ｍ１より読み出され、誤り数値と加算され誤り訂正が施
される。誤り訂正が施されたデータはＲＡＭ１内の誤り
位置に相当するアドレスへ書き込まれる。

【０１０４】この際使用されるＲＡＭ１は高速にデータ
をランダムにアクセスできるＳＲＡＭ、またはＤＲＡＭ
などが用いられる。一般に前述のようなＲＡＭはデータ
の入出力Ｉ／Ｏポート、及び書き込み及び読み出しのア
ドレスポートは別々には設けられていない。従って、誤
り訂正装置において最高速度の処理を実現するためには
ＲＡＭ１とのデータのアクセスがあるシンドローム生成
回路２及び誤り訂正回路22をそれぞれ独立に動作させ、
ＲＡＭ１とのアクセスがないユークリッド演算回路20及
びチェンサーチ回路21をシンドローム生成回路２と並行
動作させればよい。すなわち、シンドローム生成回路２
及び誤り訂正回路22が動作している間に、ユークリッド
演算回路20及びチェンサーチ回路21の演算を終了するよ
うに誤り訂正装置を動作させればよいことになる。この
ように誤り訂正装置を動作させればＲＡＭ１は、誤り訂
正動作が開始されると常にシンドローム生成回路２また
は誤り訂正回路22とアクセス状態にあり、最小の復号時
間で誤り訂正を施すことができる。なお、本実施例にお
けるＲＡＭ１の動作状態を示すＲＡＭアクセス信号を図
２に示す。従って、第１実施例の構成をとる誤り訂正装
置（すなわち、シンドローム生成回路２，ユークリッド
演算回路20及びチェンサーチ回路21の３つの回路を並行
動作させる構成）が最高速の復号速度を有することにな
る。

【０１０５】第２実施例．次に、本発明の第２実施例に
ついて説明する。図３は第２実施例である誤り訂正装置
のブロック構成図である。図において１, ２, 20〜22，
40, 41は第１実施例に示したものと同一のものであるの
で説明は省略する。本実施例では、図に示すようにシン
ドローム生成回路２，チェンサーチ回路21及び誤り訂正
回路22はクロック１で駆動するように構成されている。
また、ユークリッド演算回路20は上記クロック１と異な
る周波数のクロック２で駆動するように構成されてい
る。なお、誤り訂正装置制御回路41はクロック１及びク
ロック２をもとにＲＡＭ１，シンドローム生成回路２，
ユークリッド演算回路20，レジスタ40，チェンサーチ回
路21及び誤り訂正回路22を制御する。また、シンドロー
ム生成回路２、ユークリッド演算回路20のガロア体上の
多項式の除算回路、及びチェンサーチ回路21の回路構成
は図27, 図29及び図30に示すものと同一の構成であるの
で説明は省略する。

【０１０６】次に、本発明の第２実施例である誤り訂正
装置の動作を説明する。本実施例ではクロック１の周波
数をクロック２の周波数の２倍の周波数で制御した場合
について説明する。これは、図27及び図30に示すよう
に、シンドローム生成回路２及びチェンサーチ回路21は
レジスタの出力にガロア体上の定数値との乗算回路と、
加算回路が直列または並列に配置されている。この際、
ハードウェア上ではレジスタ間で最大で４段のＥＸ−Ｏ
Ｒゲートを通ることになる。それに対してユークリッド
演算回路20上ではハードウェア構成にもよるが、変数ど
うしの乗算回路と加算器で構成されているのでＥＸ−Ｏ
Ｒゲートを７段程度と、数個のセレクタを通って次のレ
ジスタにデータがラッチされる。従って、このシンドロ
ーム生成回路２及びチェンサーチ回路21はユークリッド
演算回路20に比べて高速化が比較的容易である。なお、
説明をわかりやすくするためクロック２の周波数は上記
実施例１で回路を駆動したクロックと同一の周波数であ
るとする。また、本実施例では第１実施例と同様に図33
に示す最小距離17の記録方向のＣ１符号を復号する場合
について説明する。

【０１０７】ＲＡＭ１に格納されている再生、または受
信データは誤り訂正処理が開始されるとＣ１ブロック
（単位情報ブロック）を単位にＲＡＭ１より読みだされ
る。なお、ＲＡＭ１からのデータの読みだしは、誤り訂
正装置制御回路41より出力されるシステムスタート信号
に基準にしてシンドローム生成回路２を駆動するクロッ
ク１に同期して発生する読みだしアドレス及び読みだし
制御信号に基づき行われる。ＲＡＭ１より読みだされた
データはシンドローム生成回路２へ出力される。

【０１０８】シンドローム生成回路２では、第１実施例
と同様に、シンドロームが生成されるが、この時の動作
は第１実施例と同じであるので説明は省略する。シンド
ローム生成に当たっては第１実施例と同様に符号長分の
241 ステップを必要とするが、シンドローム生成回路２
を駆動するクロックは第１実施例に比べて２倍の周波数
のクロックで駆動しているので、第１実施例の半分の時
間でシンドロームの生成は終了する。ユークリッド演算
回路20では、誤り訂正装置制御回路41より出力されるシ
ステムスタート信号に基づきシンドローム演算終了時に
あらかじめセットされた初期値を元にクロック２に同期
してユークリッド演算を開始する。ユークリッド演算回
路20の動作は、第１実施例と同様であり、その説明は省
略する。その後、第１実施例と同様に、チェンサーチ回
路21において誤り位置が算出される。なお、チェンサー
チ回路21を駆動するクロックは上述のように、第１実施
例に比べて２倍の周波数のクロックで駆動しているの
で、第１実施例の半分の時間で誤り位置の算出が終了す
る。その後、第１実施例と同様に、誤り訂正回路22で誤
り数値が求められ、誤り訂正が逐次施され、誤り訂正が
施されたデータがＲＡＭ１内の誤ったデータと逐次書き
換えられる。

【０１０９】次に、第２実施例を用いて図33に示す１ラ
インのデータを復号する場合の各回路部の信号処理タイ
ミングを図４に示す。図４において、図２と同一部分に
は同一符号を付している。

【０１１０】シンドローム生成にあたっては演算終了ま
で符号長に相当する241 ステップを要するが、シンドロ
ーム生成にあたってはクロック１の周波数が第１実施例
の場合と比べて２倍になっているのでシンドローム生成
にかかる時間（図４中のＳＹ部）は半分となる（241/２
ステップ程度）。なお、ユークリッド演算部分のクロッ
ク周波数は第１実施例と同じであるので、その演算時間
（図４中のＥＵ部）は第１実施例と同じである（120 ス
テップ程度）。一方、チェンサーチ回路21を駆動するク
ロックの周波数はシンドローム生成の場合と同様に第１
実施例の場合の２倍であるので、チェンサーチ回路21で
の演算時間（図４中のＣＨ部）は第１実施例に比べて半
分の時間となる（241/２ステップ程度）。また、第２実
施例では誤り訂正回路22をクロック１で駆動しているの
で、処理時間は第１実施例に比べて半分の処理時間で動
作は完了する（８ステップ程度）。

【０１１１】第２実施例では、シンドローム生成回路
２，ユークリッド演算回路20及びチェンサーチ回路21の
３つの回路の並行動作を、クロック１及びクロック２の
２系統で制御することとし、かつシンドローム生成回路
２及びチェンサーチ回路21を駆動するクロックの周波数
をユークリッド演算回路20を駆動するクロックの周波数
に対して２倍の周波数に設定する。従って、図４に示す
ように１誤り訂正ブロックを復号するステップ数を128.
5 ステップとすることができ、従来の誤り訂正装置に比
べて約4.8 倍（626 /128.5）に上げることが可能であ
る。また、シンドローム生成回路２と誤り訂正演算回路
３とを並行に動作せる場合に比べても約３倍（386 /12
8.5）に復号速度を上げることが可能である。よって、
誤り訂正装置を並列に配置することなく回路の高速化を
はかることができ、並列に誤り訂正装置を配置した場合
に比べて回路規模の大幅な縮小を図れる。

【０１１２】また、第１実施例と同様、本実施例でも、
ＲＡＭ１とのデータのアクセスがないユークリッド演算
回路20及びチェンサーチ回路21を、シンドローム生成回
路２と並行動作させ、シンドローム生成回路２及び誤り
訂正回路22が動作している間に、ユークリッド演算回路
20及びチェンサーチ回路21の演算が終了するように動作
させているので、最小の復号時間で誤り訂正を施すこと
ができる。更に、本実施例の誤り訂正装置では、比較的
高速化が可能なシンドローム生成回路２及びチェンサー
チ回路21を駆動するクロックを第１実施例に比べて２倍
の周波数のクロックにしたため、第１実施例に比べてお
よそ半分の復号時間で１ブロック当たりの誤り訂正動作
を行うことが可能となる。

【０１１３】なお、第２実施例では、クロック１の周波
数をクロック２の周波数の２倍の周波数に設定したが、
これに限るものではなく例えば３倍，４倍等の整数倍、
または1.5 倍，3.2 倍等の非整数倍に選んでも同様の効
果を奏する。また、シンドローム生成回路２及びチェン
サーチ回路21を同一周波数のクロックで駆動したがこれ
に限るものではなく、ユークリッド演算回路20を駆動す
るクロックの周波数より高いクロックで駆動すれば、シ
ンドローム生成回路２を駆動するクロックとチェンサー
チ回路21を駆動するクロックの周波数が異なってもよ
い。更に、誤り訂正回路22を駆動するクロックとしてク
ロック１を用いたがこれに限るものではなくクロック２
または他の周波数のクロックを用いてもよい。

【０１１４】第３実施例．次に、第３実施例について説
明する。なお、本発明の第３実施例である誤り訂正装置
のブロック構成は第１実施例（図１）と同様である。図
５に第３実施例におけるユークリッド演算回路20のガロ
ア体上の多項式の除算を実行する除算回路部分のブロッ
ク構成図を示す。

【０１１５】図５において、50及び51は図29に示すもの
と同一であるので説明は省略する。60，65及び66はレジ
スタ、61及び62はセレクタ、64は加算器、63は乗算回路
である。以上、レジスタ60，65及び66、セレクタ61及び
62、加算器64、及び乗算回路63でユークリッド演算回路
20は構成されている。なお、本実施例では、図29に示す
従来のユークリッド演算回路20の除算回路に比べて図５
に示すユークリッド演算回路20の除算回路は各レジスタ
毎に接続されていた乗算回路がレジスタ２個毎に１個接
続されており、回路規模の削減を図っている。具体的に
はセレクタ62及びレジスタ66は増えているが、例えば本
実施例のように最小距離17のリード・ソロモン符号を復
号する場合、乗算回路が16個(400×16＝6400ゲート) が
省略でき、増加するレジスタ66は８個（８×56＝448 ゲ
ート) 、及びセレクタ62が16個（24×16＝384 ゲート)
となり約5500ゲートの回路規模の縮小が図れる。

【０１１６】次に、第３実施例である誤り訂正装置の動
作を説明する。本実施例では第１実施例と同様に図33に
示す最小距離17の記録方向のＣ１符号を復号する場合に
ついて説明する。なお、第３実施例におけるシンドロー
ム生成回路２，チェンサーチ回路21及び誤り訂正回路22
の動作は第１実施例と同様であるのでその説明は省略
し、本実施例の特徴部分であるユークリッド演算回路20
の動作についてのみ図５を用いて詳述する。

【０１１７】シンドローム生成終了信号が入力されると
各レジスタ60, 65には初期値がセットされる。具体的に
は図５に示す上側２列のレジスタ群60a, 60bにはＺ^2tが
セットされ、下側２列のレジスタ群65a, 65bにはシンド
ローム生成回路２により算出されたシンドローム多項式
の係数がセットされる。セットされたデータはシステム
スタート信号に基づき被除数側（最初はＺ^2tのデータが
セットされた上側２列のレジスタ群60）のデータをシフ
トしていくことによりガロア体上の多項式の除算を実行
する。除算は被除数側の多項式の次数が除数側の多項式
の次数より小さくなるまで繰り返す。

【０１１８】除算動作を具体的に示すと次のようにな
る。図５において、被除数側のレジスタ60群に接続され
ているセレクタ61はレジスタ66の出力を選択するように
接続され、除数側のレジスタ65群に接続されているセレ
クタ61はレジスタ65の出力を選択するように構成する。
この結果、除数側のデータはレジスタ65内に維持され、
被除数側のレジスタ60内のデータはシフトされ除算が実
行されることになる。

【０１１９】この際、本実施例に示すユークリッド演算
回路20の除算回路は図に示すように乗算回路63がレジス
タ２個に１つ配置されているためセレクタ62を逐次切り
換えていくことにより除算を実行する。具体的には、被
除数側の一方のレジスタのデータが除算を行なっている
間、他方のレジスタはデータを保持するようにセレクタ
61を制御する。図６に被除数側の各レジスタ60, 除数側
の各レジスタ65, レジスタ66及び乗算回路63の動作を示
すタイミングチャートを示す。なお、本タイミングチャ
ートはレジスタ60に被除数が、レジスタ65に除数が記憶
されている場合のものである。なお、除数、被除数が入
れ替わっても制御のタイミング（演算順序、またはステ
ップ数）は変わらない。各レジスタ、及びセレクタの制
御は図６に示すタイミングチャートにしたがって実行さ
れる。図に示すように、ガロア体上の除算を実行するに
当たっては４ステップで被除数の次数を２次減らすよう
に構成されている。（従来例では２ステップで被除数の
次数を２次減らすように構成されている。）従って、本
実施例ではユークリッド演算回路20での復号ステップ数
は約240 ステップ程度になる。

【０１２０】除算の結果、被除数側のレジスタ群には上
記除算の余りが格納されることになる。次に除数レジス
タ群に格納されている多項式を被除数として、また上記
除算結果の余りを除数として除算を行なう。これは、セ
レクタ群61の制御を切り換えることにより除数、被除数
の切り換えを実行する。この動作を図25に示すユークリ
ッドアルゴリズムの終了条件が満たされるまで繰り返
す。上記、条件が満たされるとユークリッド演算回路20
では誤り位置多項式、及び誤り数値多項式の各係数デー
タを算出する。算出された各係数データは一旦レジスタ
40に格納される。なお、ユークリッド演算回路20は、ユ
ークリッド演算が終了すると誤り訂正装置制御回路41へ
ユークリッド演算終了信号を出力する。

【０１２１】次に、第３実施例を用いて図33に示す１ラ
インのデータを復号する場合の各回路部の信号処理タイ
ミングを図７に示す。図７において、図２と同一部分に
は同一符号を付している。本実施例では、ユークリッド
アルゴリズムを用いて、図33に示す最小距離17のリード
・ソロモン符号を復号する場合、ユークリッド演算回路
20における演算時間（図７中のＥＵ部）に約240 ステッ
プ程度必要とする。他の部分は第１実施例と同一であ
る。

【０１２２】本実施例では、第１実施例と同様に、従来
例に比べて復号速度を上げることができる。また、ユー
クリッド演算回路20の復号ステップ数をシンドローム生
成回路２及び誤り訂正回路22を動作させる際に必要なス
テップ数程度に増加させる（この際、シンドローム生
成、及び誤り訂正に必要となるステップ数とほぼ等しく
なるようにステップ数を決定する）ことにより、誤り訂
正装置の復号時間を遅くすることなく回路規模の削減が
図れる。本実施例では従来例に比べて約5500ゲートの回
路規模の縮小が図れる。よって、誤り訂正装置を並列に
配置することなく回路の高速化を図ることができ、並列
に誤り訂正装置を配置した場合に比べて回路規模の大幅
な縮小が図れる。

【０１２３】なお、本実施例ではユークリッド演算回路
20の回路規模を、最大復号ステップ数がほぼチェンーサ
ーチ、またはシンドローム生成とほぼ等しくなるように
決定したが、これに限るものではなく、復号時間に余裕
があればその分を更なる回路規模の削減に用いても良い
ことは言うまでもない。また、ＲＡＭ１とのデータのア
クセスがないユークリッド演算回路20及びチェンサーチ
回路21を、シンドローム生成回路２と並行動作させるこ
とにより、最小の復号時間で誤り訂正を施すことができ
る点は、第１，第２実施例と同様である。

【０１２４】第４実施例．次に、第４実施例について説
明する。なお、第４実施例は上記第３実施例である誤り
訂正装置中のユークリッド演算回路20のガロア体上の多
項式の除算を実行する除算回路の変形例に関するもので
ある。図８に第４実施例によるユークリッド演算回路20
の除算回路部分のブロック構成図を示す。なお、本実施
例の基本構成は図37に示すものである。

【０１２５】図８において、50及び51は図29に示すもの
と同一であるので説明は省略する。70及び71はレジス
タ、72，73及び74はセレクタ、75は乗算回路、76は加算
器、77はレジスタ、78は除算回路である。以上、レジス
タ70, 71、セレクタ72，73, 74、乗算回路75、加算器7
6、レジスタ77、及び除算回路78でユークリッド演算回
路20のガロア体上の多項式の除算回路は構成されてい
る。なお、本実施例では、被除数の最大次数の係数を、
除数の最大次数の係数で除算した結果を各除数の係数に
乗算することにより割り算を実行する。図８に示すユー
クリッド演算回路20の除算回路はセレクタ74で被除数、
及び除数を選択した後、除数側の各係数データに上記除
算回路78の出力を乗算し被除数側の各係数データを加算
することによりガロア体上の多項式の除算を実行する。

【０１２６】よって、第４実施例では、被除数側に接続
されていた乗算回路をすべて削除するとともに、除数側
のレジスタに接続されている乗算回路をレジスタ２個毎
に１個接続することにより第３実施例と同様に回路規模
の削減を図っている。具体的には第３実施例に比べて、
セレクタ74及び除算回路78が増えているが、最小距離17
のリード・ソロモン符号を復号する場合、乗算回路が７
個(400×７＝2800ゲート) が省略でき、増加するセレク
タ74は16個（24×16＝384 ゲート）、及び除算回路78が
１個（2000ゲート程度) となり約400 ゲート程度の回路
規模の縮小が図れる。

【０１２７】次に、本発明の第４実施例である誤り訂正
装置の動作を説明する。本実施例では第１実施例と同様
に図33に示す最小距離17の記録方向のＣ１符号を復号す
る場合について説明する。なお、第４実施例におけるシ
ンドローム生成回路２，チェンサーチ回路21及び誤り訂
正回路22の動作は第１実施例と同様であるのでその説明
は省略し、本実施例の特徴部分であるユークリッド演算
回路20の動作についてのみ図８を用いて詳述する。

【０１２８】シンドローム生成終了信号が入力されると
各レジスタ70, 71には初期値がセットされる。具体的に
は図８に示す上側２列のレジスタ群70a, 70bにはＺ^2tが
セットされ、下側２列のレジスタ群71a, 71bにはシンド
ローム生成回路２により算出されたシンドローム多項式
の係数がセットされる。セットされたデータはシステム
スタート信号に基づき被除数側（最初はＺ^2tのデータが
セットされた上側２列のレジスタ群70）のデータをシフ
トしていくことによりガロア体上の多項式の除算を実行
する。除算は被除数側の多項式の次数が除数側の多項式
の次数より小さくなるまで繰り返す。

【０１２９】除算動作を具体的に示すと次のようにな
る。図８において、被除数側のレジスタ70群に接続され
ているセレクタ72a はレジスタ77の出力を選択するよう
に接続され、除数側のレジスタ71群に接続されているセ
レクタ72b はレジスタ71の出力を選択するように構成す
る。この結果、除数側のデータはレジスタ71内に維持さ
れ、被除数側のレジスタ70内のデータは逐次シフトされ
除算が実行されることになる。

【０１３０】この際、本実施例に示すユークリッド演算
回路20の除算回路は、除数の各係数に除算回路78の出力
データを乗算するが、図に示すように乗算回路75はレジ
スタ２個に１つ配置されているためセレクタ73を逐次切
り換えていくことにより除算を実行する。具体的には、
被除数側の一方のレジスタのデータが除算を行なってい
る間、他方のレジスタはデータを保持するようにセレク
タ72を制御する。回路全体の制御は第３実施例と同様に
なされる（図６参照）。なお、本タイミングチャートは
レジスタ70に被除数が、レジスタ71に除数が記憶されて
いる場合のものである。

【０１３１】なお、第４実施例では誤り訂正装置の復号
時間を遅くすることなく回路規模の削減が図れるなど、
本実施例における他の動作，効果などは、前述の第３実
施例と同じであるので、その説明は省略する。

【０１３２】なお、第３実施例（第４実施例）ではレジ
スタ60, 65（70，71）内のデータを保持するためにレジ
スタ60, 65（70，71）の全段にセレクタ61（72）を設け
たがこれに限るものではなく、例えばデータを保持する
レジスタ60, 65（70，71）に入力されるクロックを止め
るなどの処理を施しても同様の効果を奏する。また、入
力端子50の出力に接続されている１段目の乗算回路63
（75）及びレジスタ66（77）は入力端子50より入力され
るデータが０であるので省略することができることはい
うまでもない。また、ユークリッド演算回路20のガロア
体上の多項式の復号ステップ数を２倍にした場合の回路
構成について述べたがこれに限るものではなく、シンド
ローム生成回路２及び誤り訂正回路22を動作させる際に
必要なステップ数とほぼ等しくなるような復号ステップ
数であれば３倍または４倍等のステップ数で復号できる
回路を用いてもよい。更に、ユークリッド演算回路20の
復号ステップ数をシンドローム生成回路２、及び誤り訂
正回路22を動作させる際に必要なステップ数とほぼ等し
くなるように設定したが、復号時間に余裕があればこれ
に限るものではなくもっと復号ステップ数を増やしても
同様の効果を奏する。

【０１３３】次に、上述の各実施例に共通である誤り訂
正回路22の回路動作について、図９及び図10を用いて説
明する。誤り訂正回路22では、上述のようにチェンサー
チ回路21より出力される誤り位置情報と、ユークリッド
演算回路20で算出された誤り数値多項式とをもとにＲＡ
Ｍ１内の誤り位置が算出されたデータに誤り訂正を施
す。図９に示すタイミングチャートをもとに誤り訂正回
路22の回路動作を説明する。チェンサーチ回路21より出
力された誤り位置情報に基づき誤り訂正装置制御回路41
はＲＡＭ１内の誤り位置の算出されたデータを読み出す
ための読みだしアドレス及び制御信号を出力する。この
際、ＲＡＭ１内の誤ったデータは図９に示すように逐次
８個連続して読み出される。

【０１３４】ＲＡＭ１より連続して読み出された誤った
データは、誤り訂正回路22で計算された誤り数値と図９
に示す誤り訂正タイミングで逐次加算される。誤り訂正
が施されたデータは、ＲＡＭ１からの誤り位置に算出さ
れたすべてのデータの読み出しが終了すると同時に誤っ
たデータが記憶されているアドレスへ逐次書き込まれ
る。８誤り訂正の場合、誤り訂正回路22の回路動作のス
テップ数は16となり従来最低24ステップ必要であったの
に対し８クロック分高速化が可能となる。

【０１３５】同様に図10のタイミングチャートを用いて
誤り訂正回路22の他の動作を説明する。この例では、チ
ェンサーチ回路21より出力された誤り位置情報に基づき
誤り訂正装置制御回路41はＲＡＭ１内の誤り位置の算出
されたデータを読み出すための読みだしアドレス、及び
制御信号を出力する。この際、ＲＡＭ１内の誤ったデー
タは図10に示すように２つ連続して読み出される。

【０１３６】ＲＡＭ１より２つ連続して読み出された誤
ったデータは、誤り訂正回路22で計算された誤り数値と
図10に示す誤り訂正タイミングで逐次加算される。誤り
訂正が施されたデータは、図10に示すタイミングで２つ
連続して誤り位置が算出されたデータが記憶されている
アドレスへ書き込まれる。以下、この動作を誤りを訂正
するデータの数だけ繰り返して誤り訂正を行う。図10に
示すような８誤り訂正の場合、誤り訂正回路22の回路動
作のステップ数は16となり従来最低24ステップ必要であ
ったのに対し８クロック分高速化が可能となる。

【０１３７】一般に誤り訂正装置の高速化を実現する
際、上記実施例でも述べたようにＲＡＭ１とのデータの
アクセス時間がいちばんネックとなる。これは、他の部
分は上記実施例に示すように各々の回路動作を並行化す
ることにより復号時間の短縮が図れるが、ＲＡＭ１との
データのアクセスは並行処理が出来ないため、高速化を
実現する際ＲＡＭ１とのアクセスがあるシンドローム生
成回路２及び誤り訂正回路22の計算ステップ数を如何に
減らすかがキーワードとなってくる。本実施例に示す誤
り訂正回路22を採用した場合、図33に示す最小距離17の
Ｃ１符号を誤り訂正する最低際に必要なステップ数は(2
41＋16) ステップ程度となる。なお、本実施例では８シ
ンボルの誤りを訂正する際の動作について説明したがこ
れに限るものではない。また、ＲＡＭ１より誤ったデー
タを、すべてまたは２つ連続して読み出したがこれに限
るものではなく、ＲＡＭ１より誤ったデータ３つを連続
して読み出した後に誤り訂正が施されたデータをＲＡＭ
１へ書き込む等、連続して読み出すデータの数が２以上
であれば同様の効果を奏することはいうまでもない。

【０１３８】なお、上記第１〜第４実施例では、シンド
ローム生成回路２で求められたシンドロームより誤り位
置多項式及び誤り数値多項式を求める方法としてユーク
リッドアルゴリズムを用いた場合について説明したがこ
れに限るものではなく、バーレカンプアルゴリズムのよ
うな他の方法により誤り位置多項式、及び誤り数値多項
式を求めても、シンドローム生成回路２，ユークリッド
演算回路20及びチェンサーチ回路21を並行動作させるこ
とにより高速に誤り訂正符号を復号できることはいうま
でもない。

【０１３９】また、誤り訂正符号としてリード・ソロモ
ン符号を用いたがこれに限るものではなく、ＢＣＨ符号
などの他の線形誤り訂正符号を復号する誤り訂正装置に
用いてもよい。

【０１４０】また、図33に示すＣ１符号の復号について
説明したがこれに限るものではなくＣ２符号の復号にも
同様の回路構成で復号すれば同様の効果を奏することは
いうまでもない。誤り訂正符号の構成は図32及び図33に
示すものに限るものではなく、また２重以上の積符号形
式の誤り訂正符号を復号する場合も同様の効果を奏す
る。また、積符号形式の誤り訂正符号としてリード・ソ
ロモン符号とＢＣＨ符号とを組み合わせた符号などでも
上記構成で復号回路の高速化が図れる。

【０１４１】また、シンドローム生成回路２，ユークリ
ッド演算回路20及びチェンサーチ回路21の３つの回路を
システムスタート信号に基づき同時に動作させるように
制御したが、並行動作を行うタイミングはこれに限るも
のではなく、例えばシンドローム生成後すぐにユークリ
ッド演算回路20の初期値をセットしユークリッド演算回
路20を動作させてもよい。また、チェンサーチ回路21を
ユークリッド演算終了後すぐに動作させてもよい。シン
ドローム生成回路２より出力されるシンドロームデータ
の出力タイミング、ユークリッド演算回路20での初期値
セットタイミング、レジスタ41への誤り位置多項式及び
誤り数値多項式の係数データの出力タイミング、チェン
サーチ回路21の初期値セットタイミング、誤り訂正回路
22での制御タイミングは前述したタイミングに限るもの
ではなく、シンドローム生成回路２，ユークリッド演算
回路20及びチェンサーチ回路21の３つの回路を並行動作
させることにより同様の効果を奏する。

【０１４２】また、シンドローム生成回路２，ユークリ
ッド演算回路20のガロア体上の除算回路及びチェンサー
チ回路21の回路構成を図27，図29及び図30に示したがこ
れに限るものではなく、例えば演算回路部分をマイコン
等の演算処理回路等で、または大容量のＲＯＭ等で構成
してもよい。

【０１４３】また、シンドローム生成回路２，ユークリ
ッド演算回路20及びチェンサーチ回路21の３つの回路を
並行動作させたがこれに限るものではなく、例えばこれ
らの３つの回路以外に誤り訂正回路22を含むて４つの回
路を並行動作させても同様の効果を奏する。

【０１４４】また、誤り訂正回路22の回路動作はこれに
限るものではなく、例えば、復号時間に余裕があれば従
来例に示すようにチェンサーチ回路21で検出された誤り
位置に基づく誤ったデータをＲＡＭ１より読みだし誤り
訂正を行い、再びＲＡＭ１へ書き込むといった動作を繰
り返してもよい。

【０１４５】また、ユークリッド演算回路20の出力を一
旦レジスタ40に蓄えたが誤り位置多項式、誤り数値多項
式の係数を蓄えるレジスタは必ずしも必要がなく、制御
方法によっては省略してもよい。

【０１４６】また、シンドローム生成回路２，ユークリ
ッド演算回路20及びチェンサーチ回路21の回路動作の開
始を同時に行っていたがこれに限るものではなく、開始
タイミングは上記３つの回路がバラバラであっても同様
の効果を奏する。

【０１４７】次に、ガロア体上で定義される多項式同士
の除算回路部の構成に特徴がある本発明の他の実施例
（第５〜第９実施例）について説明する。

【０１４８】第５実施例．図11に本発明の第５実施例で
ある誤り訂正装置のガロア体上で定義される多項式同士
の除算回路部のブロック構成図を示す。図において81a,
81b, 85〜88及び95は図37に示すものと同一であるので
説明は省略する。100 はレジスタ81a の出力を被除数と
して、またレジスタ81b の出力を除数として除算を行う
除算回路、101 はユークリッド演算の除算回路部の制御
を行うユークリッド演算制御回路である。

【０１４９】次に、図11に示す回路構成で除算を実行す
る際の除算回路の動作原理を簡単に説明する。いま、被
除多項式、及び除多項式を従来例と同様にそれぞれ 被除多項式：Ｍ１（Ｚ）＝Ａ_n Ｚⁿ ＋Ａ_n-1 Ｚ^n-1 ＋・
・・Ａ₁ Ｚ ＋Ａ₀ 除多項式：Ｍ２（Ｚ）＝Ｂ_m Ｚ^m ＋Ｂ_m-1 Ｚ^m-1 ＋・・
・Ｂ₁ Ｚ ＋Ｂ₀ とする。なお、ｎ＞ｍとする。以下、筆算により上記除
算を行った場合の計算手順を数４に示す。なお、本実施
例では初期値として、被除多項式の各係数データがレジ
スタ81a に、また除多項式の各係数データがレジスタ81
b に記憶されているものとする。数４に示すようにまず
始めは除多項式の各係数データに除算回路100 より出力
される除算結果を掛け合わせることにより除多項式の最
大次数の係数データを被除多項式の最大次数の係数デー
タと同一にして除算（被除多項式の次数を１次減らす動
作）を行う。この除算を従来例と同様に被除多項式の剰
余の次数が除多項式の次数よりも小さくなるまで繰り返
す。なお、数４では最終の剰余多項式の各係数データを
Ｃ_i （ｉ＝０, １, ２, ・・・・, ｍ−１）で表わす。

【０１５０】

【数４】

【０１５１】図25に示すユークリッドアルゴリズムに従
うと上記剰余多項式 剰余多項式：Ｒ（Ｚ）＝Ｃ_m-1 Ｚ^m-1 ＋Ｃ_m-2 Ｚ^m-2 ＋
・・・＋Ｃ₁ Ｚ＋Ｃ₀ の次数が予め定められた条件を満たしていない場合は上
記除多項式Ｍ２（Ｚ）を被除多項式として、また上記剰
余多項式Ｒ（Ｚ）を除多項式として除算を繰り返す。

【０１５２】数５にＭ２（Ｚ）をＲ（Ｚ）で除算した場
合の計算手順を示す。なお、本筆算では便宜上、上記剰
余多項式Ｒ（Ｚ）の最大次数Ｃ_m-1 は０でないものとす
る。一般に、０であった場合は従来例と同様に図11に示
す次数検出回路87，88で上記被除多項式及び除多項式の
次数を判定して被除多項式の最大次数が０でなくなるま
で被除多項式の係数データをシフトして除算を実行す
る。また、除算演算中の剰余多項式の最大次数が０にな
った場合も同様に剰余多項式の最大次数が０でなくなる
まで剰余多項式の係数データをシフトして除算を行う。

【０１５３】

【数５】

【０１５４】なお、これらの制御はユークリッド演算制
御回路101 で行う。図11に示す本実施例では、従来例で
示したような被除多項式の係数データと除多項式の係数
データとを交換するためのセレクタが配置されていな
い。従って、除算を実行する際は、数５に示すように被
除多項式の各係数データに除算回路100 より出力される
乗数を掛け合わせることにより被除多項式の最大次数の
係数データを除多項式の最大次数の係数データと同一に
して除算（被除多項式の次数を１次減らす動作）を行
う。この除算を従来例と同様に被除多項式の剰余の次数
が除多項式の次数よりも小さくなるまで繰り返す。その
結果、剰余多項式（Ｒ”（Ｚ）とする）の各係数データ
をＥ_i （ｉ＝０, １, ２, ・・・, ｍ−２）で表わす。

【０１５５】そして、剰余多項式Ｒ”（Ｚ）（Ｒ”
（Ｚ）＝Ｅ_m-2 Ｚ^m-2 ＋Ｅ_m-3 Ｚ^m-3 ＋・・・＋Ｅ₁ Ｚ
＋Ｅ₀ ）の次数が図25に示した条件を満たしていない場
合上記Ｒ（Ｚ）を被除多項式として、Ｒ”（Ｚ）を除多
項式として除算を繰り返す。数６に筆算手順を示す。な
お、この場合も説明を簡単にするため剰余多項式の最大
次数の係数であるＥ_m-2 は０でないものとする。先ほど
述べたように被除多項式と除多項式の係数データの交換
を行うためのセレクタが配置されていない。

【０１５６】

【数６】

【０１５７】従って、数４と同様に除算を実行する際
は、除多項式の各係数データに除算回路100 より出力さ
れる乗数を掛け合わせることにより除多項式の最大次数
の係数データを被除多項式の最大次数の係数データと同
一にして除算（被除多項式の次数を１次減らす動作）を
行う。

【０１５８】この除算を従来例と同様に被除多項式の剰
余の次数が除多項式の次数よりも小さくなるまで繰り返
す。その結果、剰余多項式（Ｒ■■■（Ｚ）とする）の
各係数データをＦ_i （ｉ＝０，１，２，・・・，ｍ−
３）で表わす。そして、この動作をユークリッドアルゴ
リズムの終了条件を満たすまで実行する。なお、この動
作の繰り返しで誤り数値多項式ω（Ｚ）と誤り位置多項
式σ（Ｚ）とが算出される理由は、誤り位置または誤り
数値を算出する際、上記多項式を各々の多項式の最大次
数で正規化するためである。（詳しくは前述した「符号
理論」，pp.169〜175 を参照）

【０１５９】以下、図25に示すユークリッドアルゴリズ
ムに従い、リード・ソロモン符号を復号する誤り訂正装
置のユークリッド演算の除算回路部の動作を図11を用い
て説明する。本実施例では、従来例と同様に光ディスク
等に採用されている最小ハミング距離が17のリード・ソ
ロモン符号を復号する場合について説明する。いま、再
生信号より生成したシンドローム多項式Ｓ（Ｚ）を Ｓ（Ｚ）＝Ｓ₁₅Ｚ¹⁵＋Ｓ₁₄Ｚ¹⁴＋Ｓ₁₃Ｚ¹³＋・・・＋Ｓ
₁ Ｚ＋Ｓ₀ とする。

【０１６０】ユークリッド演算が開始されるとまず始
め、ユークリッド演算制御回路101 より出力されるユー
クリッド演算開始信号をもとにレジスタ81a に初期値で
ある被除多項式Ｚ^2tの係数が記憶されるとともに、レジ
スタ81b に除多項式であるシンドローム多項式Ｓ（Ｚ）
の各係数データが記憶される。また、次数検出回路87,8
8のカウンタにはそれぞれ次数の初期値である16と15と
がセットされる。次数検出回路87, 88内のカウンタは被
除多項式の係数データを記憶しているレジスタ８１が１
回シフトされるたびにカウント値が１つ下がるように構
成されている。なお、本実施例では従来例と同様に右側
に配置されているレジスタに高次の次数の係数データが
記憶される。

【０１６１】それと同時に、除多項式であるシンドロー
ム多項式は次数検出回路８８で最高次数の係数データが
０であるか判定する。ユークリッド演算制御回路101 で
は、次数検出回路88で検出された除多項式（シンドロー
ム多項式）の最大次数の係数が０の場合、除多項式の係
数データが記憶されているレジスタ81b の内容をシフト
し（なお、この際加算回路86での加算動作を行わずレジ
スタ81b の内容をそのままシフトする構成に成ってい
る。）最大次数のデータが０でなくなるまでシフト動作
を繰り返す。その際、次数検出回路88中のカウンタはカ
ウント値をシフト動作が行われるたびに１づつ減らされ
る。

【０１６２】また、被除多項式の係数データが記憶され
ているレジスタ81a はクロックが入力されると加算回路
86の出力がラッチされるように構成されており、除多項
式の係数データが記憶されているレジスタ81b は係数デ
ータが保持されるように構成されている。（図11には、
具体的な制御回路は省略したが、レジスタ81a, 81bに入
力されるクロック（クロック１及びクロック２）を除数
側の係数データが記憶されているレジスタについては供
給しないという方法で除多項式の係数データをレジスタ
内に保持する構成を取っている。）なお、図中に記した
各演算回路（除算回路100,乗算回路85及び加算回路86）
はガロア体上で定義された各演算を行うものとする。

【０１６３】以下、図12, 13を用いて本実施例のユーク
リッド演算回路中の除算回路の回路動作を説明する。図
12(a) にレジスタ81a に被除多項式として初期値である
Ｚ¹⁶がセットされ、81b に除多項式としてシンドローム
多項式Ｓ（Ｚ）がセットされた状態を示す。なお、レジ
スタ中に記した数字、及び記号はレジスタに格納されて
いる係数データを示すものとする。本実施例では説明を
簡単にするためシンドローム多項式の最高次の係数は０
でないものとする。また、レジスタに記憶される各多項
式の高次の次数の係数データは右端に配置されるものと
する。除算回路100 はレジスタ81a の出力を被除数、レ
ジスタ81b の出力を除数として除算しその結果を出力す
る。このとき、被除数側の係数データが記憶されている
レジスタ81a 側にクロック１が供給される。

【０１６４】図12, 13に示す除算回路は図38, 39で説明
した除算回路と同一の構成をとっており、被除多項式の
剰余の次数が、除多項式の次数より小さくなるところま
でシフト動作を繰り返すことにより除算を実行する。除
算の終了判定は次数検出回路87, 88より出力される次数
情報をもとにユークリッド演算制御回路101 で判定を行
う。なお、除算演算実行中に剰余多項式の最大次数が次
数検出回路87（または88）により０と検出されるとユー
クリッド演算制御回路101 では剰余多項式の係数データ
が記憶されているレジスタ81a （または81b ）の内容を
そのまま１つシフトするように構成されている。その
際、次数検出回路87（または88）中のカウンタのカウン
ト値が１つ減らされる。

【０１６５】図12(b) に上記除算が終了した際に、各レ
ジスタ81に記憶されている係数データの状態を示す。な
お、レジスタ81a に記憶されているＨ₁₄〜Ｈ₀ は上記除
算を行った際の剰余多項式の係数データである。除算演
算が終了すると、次数検出回路87（または88）では剰余
多項式の最大次数を検出し最大次数が０であったなら、
ユークリッド演算制御回路101 より出力される制御信号
をもとに、剰余多項式の係数をそのまま１つシフトす
る。この動作を剰余多項式の最大次数の係数データが０
でなくなるまで繰り返す。その際、上述のように、次数
検出回路87（または88）中のカウンタのカウント値が１
つづつ減らされる。

【０１６６】ユークリッド演算制御回路101 では、次数
検出回路87（または88）より出力される上記剰余多項式
の次数をもとに、剰余の次数がユークリッド演算の終了
条件（本実施例では次数が７以下）を満たしていればユ
ークリッド演算を終了し、終了条件を満たしていなけれ
ば前回の演算で除多項式であった多項式を被除多項式と
して、また上記剰余多項式を除多項式として演算を実行
する。その際、レジスタ81に格納されている係数データ
を図13(a) に示す。従来例のように交換手段を有してい
ないので回路の接続状態は変わらないが、レジスタ81a
に供給されていたクロック１が止められて、反対にレジ
スタ81b にクロック２が供給される。よって、レジスタ
81a の内容が保持され、レジスタ81b に剰余多項式の係
数が逐次記憶される。

【０１６７】その際、ユークリッド演算回路中の除算回
路では、次数検出回路88により被除多項式（剰余多項
式）の最大次数が０であるかを判定し、０であった場合
レジスタ81b に記憶されている被除多項式（剰余多項
式）の内容をそのまま１つシフトするように制御信号を
出力する。これは、除算回路100 へ出力される除数と被
除数を格納するレジスタが決まっており被除多項式の係
数データが除数として用いられる場合、被除多項式の最
大次数の係数が０となってしまうと被除数（除多項式の
最大係数）を０で割ることになり、解（出力）が不定と
成ってしまう場合が生じるためである。

【０１６８】除算は、上記例と同様に被除多項式の剰余
の次数が除多項式の次数より小さくなるまで被除多項式
の係数データを記憶しているレジスタの内容を演算しな
がらシフト動作を繰り返すことにより除算を実行する。
図13(b) に上記除算が終了した際に、各レジスタ81a, 8
1bに記憶されている係数データの状態を示した。なお、
レジスタ81b に記憶されているＪ₁₃〜Ｊ₀ は剰余多項式
の係数データである。

【０１６９】そして、上記剰余多項式の次数を判定し所
定の条件を満たしていなければレジスタ81a, 81bに供給
するクロックを切り換えてユークリッドアルゴリズムに
基づく除算動作を再び行う。この除算動作を剰余多項式
の次数が７次以下になるまで繰り返す。これにより、リ
ード・ソロモン符号を復号する際に、ユークリッドアル
ゴリズムに基づくガロア体上の多項式同士の除算を１多
項式毎に行うことができ、誤り訂正処理速度を向上させ
ることが出来るとともに交換手段（セレクタ）を持たな
いため回路規模の縮小が図れ、またセレクタ制御も必要
なくなる。

【０１７０】第６実施例．図14に本発明の第６実施例を
示す。図14において回路構成は第５実施例（図11）と同
様であるので詳細な説明は省略する。なお、第６実施例
ではレジスタに接続されている乗算回路85の位置が第５
実施例とは異なる。ユークリッド演算開始時に初期値で
あるＺ^2tがセットされるレジスタ側に乗算回路85を接続
した点が第５実施例とは異なる。この構成により、第５
実施例に比べて乗算回路85を１つ省略でき回路規模の縮
小（約 400ゲート程度の縮小）が図れる。

【０１７１】以下、第５実施例と同様に図25に示すユー
クリッドアルゴリズムに従い、リード・ソロモン符号を
復号する誤り訂正装置のユークリッド演算の除算回路部
の動作を図14を用いて説明する。第６実施例では、第５
実施例と同様に光ディスク等に採用されている最小ハミ
ング距離が17のリード・ソロモン符号を復号する場合に
ついて説明する。いま、再生信号より生成したシンドロ
ーム多項式Ｓ（Ｚ）を Ｓ（Ｚ）＝Ｓ₁₅Ｚ¹⁵＋Ｓ₁₄Ｚ¹⁴＋Ｓ₁₃Ｚ¹³＋・・・＋Ｓ
₁ Ｚ＋Ｓ₀ とする。

【０１７２】ユークリッド演算が開始されるとまず始
め、ユークリッド演算制御回路101 より出力されるユー
クリッド演算開始信号をもとにレジスタ81a に初期値で
ある被除多項式Ｚ^2tの係数が記憶されるとともに、レジ
スタ81b に除多項式であるシンドローム多項式Ｓ（Ｚ）
の各係数データが記憶される。また、次数検出回路87,8
8のカウンタにはそれぞれ次数の初期値である15と16と
がセットされる。次数検出回路87, 88内のカウンタは被
除多項式の係数データを記憶しているレジスタ81a, 81b
が１回シフトされるたびにカウント値が１つ下がるよう
に構成されている。

【０１７３】それと同時に、除多項式であるシンドロー
ム多項式は次数検出回路88で最高次数の係数データが０
であるか判定する。ユークリッド演算制御回路101 で
は、次数検出回路88で検出された除多項式（シンドロー
ム多項式）の最大次数の係数データが０の場合、除多項
式の係数データが記憶されているレジスタ81b の内容を
シフトし（なお、この際加算回路86での加算動作を行わ
ずレジスタ81b の内容をそのままシフトする構成になっ
ている。）最大次数のデータが０でなくなるまでシフト
動作を繰り返す。その際、次数検出回路88中のカウンタ
はカウント値を１づつ減らされる。

【０１７４】また、被除多項式の係数データが記憶され
ているレジスタ81a はクロックが入力されると加算回路
86の出力がラッチされるように構成されており、除多項
式の係数データが記憶されているレジスタ81b は係数デ
ータが保持されるように構成されている。図14では、具
体的な制御回路は省略したが、第５実施例と同様にレジ
スタ81a, 81bに入力されるクロック１, ２をコントロー
ルすることにより除多項式の係数データをレジスタ内に
保持する構成を取っている。なお、図中に記した各演算
回路はガロア体上で定義された各演算を行うものとす
る。

【０１７５】以下、図15,16,17を用いて本実施例のユー
クリッド演算回路中の除算回路の回路動作を説明する。
図15(a) にレジスタ81a に被除多項式として初期値であ
るＺ¹⁶がセットされ、レジスタ81b に除多項式としてシ
ンドローム多項式Ｓ（Ｚ）がセットされた状態を示す。
なお、レジスタ中に記した数字、及び記号はレジスタに
格納されている係数データを示すものとする。本実施例
では説明を簡単にするためシンドローム多項式の最高次
の係数は０でないものとする。また、レジスタに記憶さ
れる各多項式の高次の次数の係数データは右端に配置さ
れるものとする。除算回路100 はレジスタ81a の出力を
除数、レジスタ81b の出力を被除数として除算しその結
果を出力する。このとき、除数側の係数データが記憶さ
れているレジスタ81a 側にクロック１が供給される。

【０１７６】図15(b) に図15(a) に示す状態より１回レ
ジスタ81a 側をシフトした状態を示した。被除数側の初
期値が図25に示すユークリッドアルゴリズムに示すよう
にＺ¹⁶であるので被除多項式の最小次数の係数が０とな
る。よって、図14に示す回路構成の場合、１回目の除算
によって求められる被除多項式側の剰余多項式の最小次
数の係数データは Ｓ₀ ＋０×Ｓ₁₅＝Ｓ₀ となり、乗算回路85を省略できる事がわかる。図15(b)
に上記１回目の除算後のレジスタ81a, 81bに記憶されて
いる各係数データを示す。図中に記したＫ₁₄〜Ｋ₁ 及び
Ｓ₀ は剰余多項式の各係数データである。

【０１７７】第５実施例同様、被除多項式の剰余の次数
が、除多項式の次数より小さくなるところまでシフト動
作を繰り返すことにより除算を実行する。除算の終了判
定は次数検出回路87, 88より出力される次数情報をもと
にユークリッド演算制御回路101 で判定を行う。なお、
除算演算実行中に剰余多項式の最大次数が次数検出回路
87（または88）により０と検出されるとユークリッド演
算制御回路101 では剰余多項式の係数データが記憶され
ているレジスタ81a （または81b ）の内容をそのまま１
つシフトするように構成されている。その際、次数検出
回路87（または88）中の次数カウンタのカウント値が１
つ減らされる。これは、除算回路100 へ出力される除数
と被除数を格納するレジスタが決まっており被除多項式
の係数データが除数として用いられる場合、被除多項式
の最大次数の係数が０となってしまうと被除数（除多項
式の最大係数）を０で割ることになり、解（出力）が不
定と成ってしまう場合が生じるためである。

【０１７８】図16(a) に上記除算が終了した際に、各レ
ジスタ81a, 81bに記憶されている係数データの状態を示
す。なお、レジスタ81a に記憶されているＬ₁₄〜Ｌ₀ は
上記除算を行った際の剰余多項式の係数データである。
なお、本実施例ではＬ₀ ＝Ｓ₀ である。除算演算が終了
すると、次数検出回路87（または88）では剰余多項式の
最大次数を検出し最大次数が０であったなら、ユークリ
ッド演算制御回路101より出力される制御信号をもと
に、剰余多項式の係数をそのまま１つシフトする。この
動作を剰余多項式の最大次数の係数データが０でなくな
るまで繰り返す。その際、上述のように、次数検出回路
87（または88）中の次数カウンタのカウント値が１つづ
つ減らされる。

【０１７９】ユークリッド演算制御回路101 では、次数
検出回路87（または88）より出力される上記剰余多項式
の次数をもとに、剰余の次数がユークリッド演算の終了
条件（本実施例では次数が７以下）を満たしていればユ
ークリッド演算を終了し、終了条件を満たしていなけれ
ば前回の演算で除多項式であった多項式を被除多項式と
して、また上記剰余多項式を除多項式として演算を実行
する。その際、レジスタ81a, 81bに格納されている係数
データを図16(b) に示す。従来例と同様に交換手段を有
していないので回路の接続状態は変わらないが、レジス
タ81a に供給されていたクロック１が止められて、反対
にレジスタ81b にクロック２が供給される。よって、レ
ジスタ81a の内容が保持され、レジスタ81b に剰余多項
式の係数が逐次記憶される。

【０１８０】その際、ユークリッド演算回路中の除算回
路では, 次数検出回路88により被除多項式（剰余多項
式）の最大次数が０であるかを判定し、０であった場合
レジスタ81b に記憶されている被除多項式（剰余多項
式）の内容をそのまま１つシフトするように制御信号を
出力する。

【０１８１】除算は、第５実施例と同様に被除多項式の
剰余の次数が除多項式の次数より小さくなるまで被除多
項式の係数データを記憶しているレジスタの内容を演算
しながらシフト動作を繰り返すことにより除算を実行す
る。図17に上記除算が終了した際に、各レジスタ81a, 8
1bに記憶されている係数データの状態を示す。なお、レ
ジスタ81b に記憶されているＭ₁₃〜Ｍ₀ は剰余多項式の
係数データである。

【０１８２】そして、上記剰余多項式の次数を判定し所
定の条件を満たしていなければレジスタ81a, 81bに供給
するクロックを切り換えてユークリッドアルゴリズムに
基づく除算動作を再び行う。この除算動作を剰余多項式
の次数が７次以下になるまで繰り返す。これにより、リ
ード・ソロモン符号を復号する際に、ユークリッドアル
ゴリズムに基づくガロア体上の多項式同士の除算を１多
項式毎に行うことができ、誤り訂正処理速度を向上させ
ることが出来るとともに交換手段（セレクタ）を持たな
いため回路規模の縮小が図れ、またセレクタ制御も必要
なくなる。また、第５実施例に比べて乗算回路85を１つ
省略でき回路規模の縮小を図れる。

【０１８３】第７実施例．本発明の第７実施例は、第
５，第６実施例で用いられた加算回路86及び除算回路10
0 の構成とユークリッド演算回路101 の制御方法とが異
なる。よって、第７実施例は図11に示すユークリッド演
算の除算回路を用いて説明する。図18に除算回路100 の
具体的な構成図を示す。110 は入力された係数の逆数を
出力する逆元ＲＯＭ、111 は乗算回路、112 はＯＲゲー
トである。逆元ＲＯＭ110 は入力されたガロア体上の元
の逆数を出力するように構成されている。図19には加算
回路86の構成を示す。図において、113 はＡＮＤゲー
ト、114 はＥＸＯＲゲートである。表１に本実施例の逆
元ＲＯＭ110 の内容を示す。なお、表中に記したαは原
始多項式Ｇ（Ｚ）のガロア体上の元である。表に示すよ
うに本実施例における逆元ＲＯＭ110 は０が入力される
と０が出力される構成になっている。また、表１に記し
たαはＧＦ（２⁸ ）で定義されるガロア体上の元であ
る。

【０１８４】

【表１】

【０１８５】以下、図11を用いて第７実施例の回路動作
を説明する。第５実施例と同様、再生信号より生成した
シンドローム多項式Ｓ（Ｚ）を Ｓ（Ｚ）＝Ｓ₁₅Ｚ¹⁵＋Ｓ₁₄Ｚ¹⁴＋Ｓ₁₃Ｚ¹³＋・・・＋Ｓ
₁ Ｚ＋Ｓ₀ とする。

【０１８６】ユークリッド演算が開始されるとまず始
め、ユークリッド演算制御回路101 より出力されるユー
クリッド演算開始信号をもとにレジスタ81a に初期値で
ある被除多項式Ｚ^2tの係数が記憶されるとともに、レジ
スタ81b に除多項式であるシンドローム多項式Ｓ（Ｚ）
の係数データが記憶される。また、次数検出回路87, 88
のカウンタにはそれぞれ次数の初期値である16と15とが
セットされる。

【０１８７】それと同時に、除多項式であるシンドロー
ム多項式は次数検出回路88で最高次数の係数データが検
出される。ユークリッド演算制御回路101 では、次数検
出回路88で検出された除多項式（シンドローム多項式）
の次数が０の場合、除多項式の係数データが記憶されて
いるレジスタ81b の内容をシフトし最大次数のデータが
０でなくなるまでシフト動作を繰り返す。その際、次数
検出回路88中の次数カウンタのカウント値は１づつ減ら
される。

【０１８８】この時、除算回路100 では除数側のデータ
として０が入力される。逆元ＲＯＭ110 では表１に示す
ように０が入力されると０が出力される構成になってい
る。逆元ＲＯＭ110 により出力されたデータは乗算回路
111 で被除数と乗算され出力される。この場合、逆元Ｒ
ＯＭ110 からの出力データが０であるので乗算回路111
の出力は０となる。ＯＲゲート112 は乗算回路111 より
出力されるＬＳＢデータとユークリッド演算制御回路10
1 より出力される制御信号との論理和をとる。ユークリ
ッド演算制御回路101 では次数検出回路88で検出された
多項式の最大次数の係数データが０である場合に”Ｈ”
を出力する構成になっている。よって、除算回路100 か
らは１が出力されることになる。

【０１８９】また、加算回路86中のＡＮＤゲート113 の
一方の入力端子には、除算回路100の被除数側の係数デ
ータが格納されているレジスタ81a より出力される係数
データの各ビットが入力されるように構成されており、
他方の入力には、ユークリッド演算制御回路101 より出
力される制御信号が入力される。この制御信号は、除算
回路100 の除数側の係数データが次数検出回路88で０と
検出された場合”Ｌ”を出力するように構成されてい
る。この構成により、除算回路100 へ入力される除数側
（レジスタ81b 側）の係数データは １×Ｓ_j ＋０＝Ｓ_j （ｊ＝０，１，・・・, 1
5） の演算が行われシフト動作が繰り返されることになる。
除数多項式の最大次数の係数データが０でなくなるまで
シフト動作を繰り返す。これにより、上記係数データを
シフトする際ユークリッド演算制御回路101 では特別な
制御を必要とせず、係数シフトを行うレジスタさえ意識
していればよいことになる。

【０１９０】シンドローム多項式の最大次数が検出され
るとユークリッドアルゴリズムに基づく除算が開始され
る。第５実施例と同様に、被除多項式の係数データが記
憶されているレジスタ81a はクロックが入力されると加
算回路86の出力がラッチされるように構成されており、
除多項式の係数データが記憶されているレジスタ81bは
係数データが保持されるように構成されている。

【０１９１】除算動作は、被除多項式の剰余の次数が、
除多項式の次数より小さくなるまで繰り返される。除算
の終了判定は次数検出回路87, 88より出力される次数情
報をもとにユークリッド演算制御回路101 で判定を行
う。なお、除算演算実行中に剰余多項式の最大次数が次
数検出回路87により０と検出された場合でも除算回路10
0 より０が出力されるので乗算回路85及び加算回路86で
は ０×Ｓ_i ＋Ｘ_i ＝Ｘ_i の計算が行われレジスタ81a にはＸ_i （Ｘ_i はレジスタ
81a に記憶されている係数データ）がそのままシフトさ
れ記憶されることになる。従って、ユークリッド演算制
御回路101 では特に制御を変えることなくシフト動作を
繰り返せばよい。

【０１９２】除算演算が終了すると、次数検出回路87
（または88）では剰余多項式の最大次数を検出し最大次
数が０であったなら、レジスタ81a の内容をそのままシ
フトする。その際、上述のように、次数検出回路87（ま
たは88）中のカウンタのカウント値が１つづつ減らされ
る。

【０１９３】ユークリッド演算制御回路101 では、次数
検出回路87（または88）より出力される上記剰余多項式
の次数をもとに、剰余の次数がユークリッド演算の終了
条件（本実施例では次数が７以下）を満たしていればユ
ークリッド演算を終了し、終了条件を満たしていなけれ
ば前回の演算で除多項式であった多項式を被除多項式と
して、また上記剰余多項式を除多項式として演算を実行
する。その際、従来例のように交換手段を有していない
ので回路の接続状態は変わらないが、レジスタ81a に供
給されていたクロック１が止められて、反対にレジスタ
81b にクロック２が供給される。よって、レジスタ81a
の内容が保持され、レジスタ81b に剰余多項式の係数が
逐次記憶される。

【０１９４】この時、ユークリッド演算回路中の除算回
路では、次数検出回路88により被除多項式（剰余多項
式）の最大次数（レジスタ81b の出力）が０であった場
合でも上述で述べた通りユークリッド演算制御回路101
では各加算回路86及び除算回路100 にそれぞれ”Ｌ”及
び”Ｈ”の制御信号を出力するだけでレジスタ81b の内
容がシフトされる構成になっており、０を意識した制御
を行わなくてもよい。すなわち、次数検出回路88により
レジスタ81b に記憶されている多項式の最大次の係数デ
ータが０と判断されると除算回路100 からは除算結果と
して１が出力される。一方、加算回路86ではユークリッ
ド演算制御回路101 より出力される制御信号によりＡＮ
Ｄゲート113 の出力が”Ｌ”となる。（すなわち、加算
回路86に０が入力されることになる。）従って、乗算回
路85及び加算回路86では １×Ｙ_i ＋０＝Ｙ_i の演算が実行される。よって、レジスタ81b にはＹ
_i （Ｙ_i はレジスタ81b に記憶されている係数データ）
がそのままシフトされ記憶されることになる。

【０１９５】除算は、上記例と同様に被除多項式の剰余
の次数が除多項式の次数より小さくなるまで被除多項式
の係数データを記憶しているレジスタの内容を演算しな
がらシフト動作を繰り返すことにより除算を実行する。
そして、上記剰余多項式の次数を判定し所定の条件を満
たしていなければレジスタ81a, 81bに供給するクロック
を切り換えてユークリッドアルゴリズムに基づく除算動
作を再び行う。この除算動作を剰余多項式の次数が７次
以下になるまで繰り返す。これにより、リード・ソロモ
ン符号を復号する際に、ユークリッドアルゴリズムに基
づくガロア体上の多項式同士の除算を１多項式毎に行う
ことができ、誤り訂正処理速度を向上させることが出来
るとともにユークリッド演算制御回路101 での制御も非
常に簡単になり回路規模の削減を図れる。

【０１９６】なお、第７実施例では除算回路100 を逆元
ＲＯＭ110 及び乗算回路111 で構成したがこれに限るも
のではなく、入力された除数が０である場合除算回路10
0 の出力を１と出力するように除算回路100 を構成すれ
ばロジックゲート、またはマイクロコンピュータ等で構
成しても同様の効果を奏する。また、第７実施例では入
力されたデータの逆元を求める際、ＲＯＭを使用したが
ＲＡＭでもよく、またロジックゲートで逆元を求めるよ
うに構成してもよいことはいうまでもない。また、加算
回路86の構成は図19に示す構成に限るものではなく、ユ
ークリッド演算回路101 より出力される制御信号に基づ
きレジスタ81b の出力をそのまま出力するように構成す
れば同様の効果を奏する。また、ＧＦ（２⁸ ）で定義さ
れる場合について述べたがこれに限るものではない。Ｇ
Ｆ（ｑ）（ｑは素数、または素数のべき表現）で定義さ
れるガロア体上の演算なら同様の効果を奏する。更に、
図11に示す除算回路の場合について述べたが図14に示す
回路構成でも同様の効果を奏する。また、第７実施例は
従来例に示す除算回路84及び加算回路86に適用しても同
様にユークリッド演算制御回路89の制御を簡略化できる
ことは言うまでもない。初期値を設定した際、シンドロ
ーム多項式の最大次の係数データが０であった場合、レ
ジスタ81b 内のデータを最大次の係数データが０でなく
なるまでシフトする時の回路構成及び制御を簡略化でき
る。

【０１９７】第８実施例．以下、本発明の第８実施例に
ついて説明する。本実施例では、図11に示す誤り訂正装
置で除算回路100 の構成を図18に示す構成のものを用い
た場合について説明する。図20は除算回路100 及びユー
クリッド演算制御回路101 より出力される除算結果、及
び制御信号を用いて誤り位置多項式を算出する誤り位置
算出回路の一部を示す。図において120 は逆元ＲＯＭ、
121 は乗算回路、122 はセレクタである。なお、第８実
施例では説明を簡単にするためガロア体上の除算を実行
する際、被除多項式と除多項式の次数差が１次の場合に
ついて説明する。

【０１９８】図11に示す誤り訂正装置で多項式同士の除
算を行った場合、商として除算回路100 より出力される
データは次の２通りのパターンがある。一方は、被除多
項式の係数データがレジスタ81a に記憶されている場
合、もう一方は、被除多項式の係数データがレジスタ81
b に記憶されている場合である。今、被除多項式及び除
多項式をそれぞれ、 被除多項式：Ｍ１（Ｚ）＝Ａ_n Ｚⁿ ＋Ａ_n-1 Ｚ^n-1 ＋・
・・＋Ａ₁ Ｚ＋Ａ₀ 除多項式：Ｍ２（Ｚ）＝Ｂ_n-1 Ｚ^n-1 ＋Ｂ_n-2 Ｚ^n-2 ＋
・・・＋Ｂ₁ Ｚ＋Ｂ₀ とする。数７に被除多項式の係数データがレジスタ81a
に記憶されている場合の除算結果を、数８に被除多項式
の係数データがレジスタ81b に記憶されている場合の除
算結果を示す。

【０１９９】

【数７】

【０２００】

【数８】

【０２０１】被除多項式の係数データがレジスタ81a に
記憶されている場合、除算は数７に示すように実行さ
れ、誤り位置多項式の係数データを算出する際は０次の
項を正規化（正規化して１にする）した後、図25に示す
アルゴリズムに従い誤り位置多項式の係数データを求め
る。この場合、除算回路100 より出力される除算結果は
そのまま商多項式の係数データに一致する。その結果を
正規化した場合の商多項式を数７の一番下の式に示す。
同様に、被除多項式の係数データがレジスタ81bに記憶
されている場合について数８を用いて説明する。数８に
は各ステップにおける演算過程を示す。右側には各々の
ステップにおける除算回路100 の出力を示す。この場
合、除算回路100 より出力される係数データは商多項式
の係数データとは一致しない。しかしながら、数８に示
す計算方法の場合、誤り位置多項式の係数データを算出
する際の正規化した式を求める場合商多項式が１次の多
項式の場合はステップ２の除算回路100 の出力がそのま
ま商多項式の１次の係数になっていることが数７と比較
するとわかる。これをもとに図20に示す回路の動作を説
明する。

【０２０２】図20において、逆元ＲＯＭ120 には、図11
に示す除算回路100 より出力される０次の商多項式の係
数が入力される。また、乗算回路121 の一方の入力には
逆元ＲＯＭ121 の出力が、もう一方の入力には除算回路
100 より出力される１次の商多項式の係数が入力され
る。セレクタ122 では、ユークリッド演算制御回路101
より出力される制御信号に基づき、被除多項式の係数が
レジスタ81a に記憶されている場合は乗算回路121 の出
力を選択し、被除多項式の係数データがレジスタ81b に
記憶されている場合は０次の商多項式の係数データが出
力されるように構成されている。

【０２０３】この構成によると、レジスタ81a に被除多
項式の係数データが記憶されている場合（数７に相当す
る）は除算結果が、誤り位置多項式を算出する際に用い
られる商多項式の１次の係数となり、レジスタ81b に被
除多項式の係数データが記憶されている場合（数８に相
当する）は、除算回路100 より出力される０次の係数デ
ータが上記商多項式の１次の係数データとして出力され
る。これにより、商多項式が正規化され、誤り位置多項
式を算出する際、セレクタ122 を追加するのみの簡単な
回路構成で誤り位置多項式を算出できる。また、数８に
示すように、レジスタ81b に被除多項式の係数データが
記憶されている場合は、除算演算を行う事なく係数デー
タが算出されるので復号ステップ数の削減が図れる。

【０２０４】なお、本実施例では商多項式として１次の
ものについて扱ったが、２次または３次等の場合につい
ても回路構成は少し複雑になるが、簡単な回路構成で実
現できる。以下、２次以上の場合について簡単に説明す
る。表２に被除多項式及び除多項式をそれぞれ、 被除多項式：Ｍ１（Ｚ）＝Ａ_n Ｚⁿ ＋Ａ_n-1 Ｚ^n-1 ＋・
・・＋Ａ₁ Ｚ＋Ａ₀ 除多項式：Ｍ２（Ｚ）＝Ｂ_n-2 Ｚ^n-2 ＋Ｂ_n-3 Ｚ^n-3 ＋
・・・＋Ｂ₁ Ｚ＋Ｂ₀ とした場合に、被除多項式の係数データがレジスタ81a
に記憶されている場合（除多項式の最大次数の係数デー
タが除算回路100 において除数として扱われている場
合、従来例に示す通常の除算の場合）の除算結果と、被
除多項式の係数データがレジスタ81b に記憶されている
場合（除多項式の最大次数の係数データが除算回路100
において被除数として扱われている場合）の計算結果を
示す。なお、本実施例においてもユークリッド演算を行
なう際の除算回路部の構成は図11に示す回路構成を採用
するものとする。

【０２０５】

【表２】

【０２０６】数９には上記通常の除算を行った商多項式
を正規化した場合の係数データを示す。これより、被除
多項式の係数データがレジスタ81b に記憶されている場
合（除多項式の最大次数の係数データが除算回路100 に
おいて被除数として扱われている場合）に、上記正規化
した商多項式を求める際は、除算回路100 より出力され
る商データをＰ_i （ｉ＝０，１，・・・，ｋ；ｋは商多
項式の次数）とし、商多項式の係数データをＱ_i （ｉ＝
０，１，・・・，ｋ；ｋは商多項式の次数）とすると、 Ｑ₀ ＝１ Ｑ₁ ＝Ｑ₀ ×Ｐ₀ Ｑ₂ ＝Ｑ₁ ×Ｐ₁ ・ ・ Ｑ_k ＝Ｑ_k-1 ×Ｐ_k-1 となる。数10に、商多項式が２次の場合の最大次数のデ
ータを計算した結果を示す。（除多項式の最大次数の係
数データが除算回路100 において被除数として扱われて
いる場合）

【０２０７】

【数９】

【０２０８】

【数１０】

【０２０９】図21に上記商多項式が２次以上の場合につ
いても考慮した、誤り位置多項式を算出する誤り位置算
出回路の一部を示す。120 〜122 は図20に示すものと同
一であるので詳細は省略する。123 はシフトレジスタで
除算回路100 より出力される商多項式の各係数データ
（除算結果）が次数の低い順に記憶される。124 はセレ
クタ、125 はレジスタである。逆元ＲＯＭ120 、乗算回
路121 、セレクタ122, 124、シフトレジスタ123 及びレ
ジスタ125 で誤り位置算出回路の一部は構成されてい
る。

【０２１０】次に、動作について説明する。図21におい
て、逆元ＲＯＭ120 には、図11に示す除算回路100 より
出力される０次の商多項式の係数が入力される。また、
シフトレジスタ123 には図11に示す除算回路100 より出
力される１次以上の商多項式の係数データが次数の低い
順に逐次記憶される。セレクタ124 は逆元ＲＯＭ120の
出力とレジスタ125 の出力をユークリッド演算回路101
より出力される制御信号に基づき切り換える。乗算回路
121 ではシフトレジスタ123 の出力とセレクタ124 の出
力を乗算する。なお、シフトレジスタ123 は乗算回路12
1 で乗算が実施されるたびにデータを逐次シフトする構
成になっている。

【０２１１】セレクタ122 では、ユークリッド演算回路
100 より出力される制御信号に基づき、被除多項式の係
数がレジスタ81a に記憶されている場合は乗算回路121
の出力を選択し、被除多項式の係数データがレジスタ81
b に記憶されている場合は、まづ初め０次の商多項式の
係数データがそのまま出力され、商多項式の２次以降の
係数を算出する際は乗算回路121 の出力を選択するよう
に制御するように構成されている。セレクタ122 の出力
はレジスタ125 に記憶される。セレクタ124 は図11に示
すレジスタ81a が被除多項式として扱われている場合は
逆元ＲＯＭ120の出力を選択し、レジスタ81b が被除多
項式として扱われている場合はレジスタ125 の出力を選
択するように構成されている。

【０２１２】この構成によると、レジスタ81a に被除多
項式の係数データが記憶されている場合は除算回路100
より出力される各商多項式の係数データを０次の係数デ
ータで正規化された除算結果が、誤り位置多項式を算出
する際に用いられる商多項式の係数データとなり、レジ
スタ81b に被除多項式の係数データが記憶されている場
合は、セレクタ122, 124を上述のように制御することに
より上述の演算を実行し商多項式の係数データを算出す
ることが可能となる。よって、セレクタ122, 124を追加
するのみの簡単な回路構成で誤り位置多項式を算出でき
る。

【０２１３】なお、上記実施例では商多項式として２次
または３次等の場合について述べたが、この場合商多項
式の各係数データに０が含まれている場合がある。この
ような場合も少し説明は複雑になるが、簡単な回路構成
で実現できる。以下、２次の商多項式中１次の項が０で
あった場合について簡単に説明する。表３に被除多項
式、及び除多項式をそれぞれ、 被除多項式：Ｍ１（Ｚ）＝Ａ_n Ｚⁿ ＋Ａ_n-1 Ｚ^n-1 ＋・
・・＋Ａ₁ Ｚ＋Ａ₀ 除多項式：Ｍ２（Ｚ）＝Ｂ_n-2 Ｚ^n-2 ＋Ｂ_n-3 Ｚ^n-3 ＋
・・・＋Ｂ₁ Ｚ＋Ｂ₀ とした場合に、被除多項式の係数データがレジスタ81a
に記憶されている場合（除多項式の最大次数の係数デー
タが除算回路100 において除数として扱われている場
合、従来例に示す通常の除算の場合）の除算結果と、被
除多項式の係数データがレジスタ81b に記憶されている
場合（除多項式の最大次数の係数データが除算回路100
において被除数として扱われている場合）の計算結果と
を示す。なお、本実施例においてもユークリッド演算を
行なう際の除算回路部の構成を図11に示す回路構成を採
用するものとする。また、本実施例を説明するため、商
多項式の１次の項を０とする。

【０２１４】

【表３】

【０２１５】数11には上記通常の除算を行った商多項式
を正規化した場合の係数データを示す。

【０２１６】

【数１１】

【０２１７】これより、被除多項式の係数データがレジ
スタ81b に記憶されている場合（除多項式の最大次数の
係数データが除算回路100 において被除数として扱われ
ている場合）に、上記正規化した商多項式を求める際
は、除算回路100 より出力される商データをＰ_i （ｉ＝
０，１，・・・，ｋ；ｋは商多項式の次数）とし、商多
項式の係数データをＱ_i （ｉ＝０，１，・・・，ｋ；ｋ
は商多項式の次数）とし、またＰ_j 〜Ｐ_m （０＜ｊ≦ｍ
＜ｋ）のデータを０とすると、 Ｑ₀ ＝１ Ｑ₁ ＝Ｑ₀ ×Ｐ₀ Q₂ ＝Ｑ₁ ×Ｐ₁ ・ ・ Ｑ_j ＝０ ・ ・ Ｑ_m+1 ＝Ｑ_j-1 ×Ｐ_j-1 ・ ・ Ｑ_k ＝Ｑ_k-1 ×Ｐ_k-1 となる。

【０２１８】図22に上記商多項式の係数中に０が存在し
た場合にも対応できる誤り位置多項式を算出する誤り位
置算出回路の一部の回路構成を示す。120 〜125 は図21
に示すものと同一であるので詳細は省略する。126 はレ
ジスタ81b に記憶されている係数データが被除多項式の
時に、次数検出回路88で検出された最大次の係数データ
が０であるかを識別するフラグデータを記憶するシフト
レジスタ、128 はシフトレジスタ126 の出力をラッチし
てデータとのタイミングを合わせるレジスタ、127 はレ
ジスタ128 より出力される信号をもとにレジスタ125 の
出力と０とを選択するセレクタである。逆元ＲＯＭ120
、乗算回路121 、セレクタ122,124,127、シフトレジス
タ123, 126及びレジスタ125, 128で誤り位置算出回路の
一部は構成されている。なお、本実施例で説明に用いる
図11に示す除算回路100 の構成は図18に示す構成を取っ
ているものとする。すなわち、除算回路100 の除数側の
データに０が入力された場合除算回路100 からは１が出
力されるものとする。

【０２１９】次に、動作について説明する。図22におい
て、逆元ＲＯＭ120 には、図11に示す除算回路100 より
出力される０次の商多項式の係数が入力される。また、
シフトレジスタ123 には図11に示す除算回路100 より出
力される１次以上の商多項式の係数データが次数の低い
順に逐次記憶される。なお、それと同時にシフトレジス
タ126 にレジスタ81b が被除多項式として扱われる際、
次数検出回路88で検出された０検出フラグ（本実施例で
は、０を検出すると”Ｈ”となるものとする）が記憶さ
れる。なお、０検出フラグデータはレジスタ81b に記憶
されている係数データが被除多項式として用いられてい
る場合、被除多項式の最大次数の係数が０であった場合
出力される。セレクタ124 は逆元ＲＯＭ120 の出力とレ
ジスタ125 の出力とをユークリッド演算制御回路101 よ
り出力される制御信号に基づき切り換える。乗算回路12
1 ではシフトレジスタ123 の出力とセレクタ124 の出力
とを乗算する。

【０２２０】なお、シフトレジスタ123, 126は乗算回路
121 で乗算が実施されるたびにデータを逐次シフトする
構成になっている。セレクタ122 では、ユークリッド演
算制御回路101 より出力される制御信号に基づき、被除
多項式の係数データがレジスタ81a に記憶されている場
合は乗算回路121 の出力を選択し、被除多項式の係数デ
ータがレジスタ81b に記憶されている場合は、まず初め
０次の商多項式の係数データがそのまま出力され、商多
項式の２次以降の係数を算出する際は乗算回路121 の出
力を選択するように制御するように構成されている。セ
レクタ122 の出力はレジスタ125 に記憶される。セレク
タ124 は図11に示すレジスタ81a が被除多項式として扱
われている場合は逆元ＲＯＭ120 の出力を選択し、レジ
スタ81bが被除多項式として扱われている場合はレジス
タ125 の出力を選択するように構成されている。また、
シフトレジスタ126 より出力された０フラグデータはレ
ジスタ128 で商多項式の係数データとタイミングが合わ
されて出力される。

【０２２１】いま、被除多項式の係数データがレジスタ
81a に記憶されている場合について説明する。除算回路
100 より出力された商データが０次のものは逆元ＲＯＭ
120及びセレクタ122 へ入力され１次以上の商データは
シフトレジスタ123 へ記憶される。なお、シフトレジス
タ126 へは”Ｌ”が記憶されるものとする。また、逆元
ＲＯＭ120 に入力されたデータが０の場合は本実施例で
は誤り検出として扱うように制御するものとする。（な
お、上述の実施例でも同様に扱うものとする。）セレク
タ124 は逆元ＲＯＭ120 の出力を、セレクタ122 は乗算
回路121 の出力を、セレクタ127 はレジスタ125 の出力
を選択するように構成されている。この場合、商多項式
の係数データに０が記憶されている場合でも、０／（逆
元ＲＯＭ120 の出力）が実行され特に何も操作せずに正
規化が実行される。これによりレジスタ81a に被除多項
式の係数データが記憶されている場合の商多項式の正規
化は実行される。

【０２２２】同様に、被除多項式の係数データがレジス
タ81b に記憶されている場合について説明する。除算回
路100 より出力された商データが０次のものは逆元ＲＯ
Ｍ120 及びセレクタ122 へ入力され、１次以上の商デー
タはシフトレジスタ123 へ記憶される。その際、シフト
レジスタ126 には次数検出回路88で検出された０フラグ
データが記憶される。なお、本実施例ではレジスタ81b
に記憶されている被除多項式の最大次数の係数データが
０の場合”Ｈ”を出力する構成になっている。また、商
多項式の０次の係数データが０の場合、本実施例では誤
り検出として扱うように誤り訂正装置を制御するものと
する。セレクタ124 はレジスタ125 の出力を選択するよ
うに制御される。セレクタ122 では、ユークリッド演算
制御回路101 より出力される制御信号に基づき、まず初
めは０次の商多項式の係数データがそのま出力され、そ
れ以降の商多項式の係数を算出する際は乗算回路121 の
出力を選択するように制御するように構成されている。
セレクタ122 の出力はレジスタ125 に記憶される。これ
により、初期値として商多項式の１次の係数データがセ
レクタ122 より出力された後、逐次乗算回路121 により
Ｑ_i ×Ｐ_i が実行され商多項式がもとめられる。

【０２２３】一方、商多項式の係数データが０の場合
（すなわち除算回路100 に除数として入力される被除多
項式の係数データが０の場合）、除算回路100 では先ほ
ども述べたように除算出力として１が出力され、それと
同時に次数検出回路88より０検出フラグが出力される。
よって、商多項式の係数データを求める際は、乗算回路
121 ではＱ_i ×１が実行されレジスタ125 にはＱ_i が記
憶されることになる。なお、シフトレジスタ126 より出
力された０フラグデータはレジスタ128 で商多項式の係
数データとタイミングが合わされてセレクタ127 に出力
される。また、シフトレジスタ126 からは０フラグデー
タが出力され、セレクタ127 で０が選択される。そし
て、次の商多項式を算出する際はＱ_i ×Ｐ_i+1 が実行さ
れる。

【０２２４】この構成によると、０フラグを記憶するシ
フトレジスタ126 とセレクタ122,124,127 とを上述のよ
うに制御することにより上述の演算を実行し商多項式の
係数データを算出することが可能となる。よって、シフ
トレジスタ126 とセレクタ122,124,127 とを追加するの
みの簡単な回路構成で誤り位置多項式を算出できる。

【０２２５】なお、第８実施例では、誤り位置多項式を
算出する際の誤り位置多項式算出回路の商多項式を正規
化する回路の構成を図20〜22に示したが、逆元ＲＯＭ12
0 及び乗算回路121 部分を図20に示す除算回路100 と兼
用し回路規模の縮小を図ってもよい。また、シフトレジ
スタ123 をレジスタ81a, 81bと兼用して回路規模の縮小
を図ってもよい。

【０２２６】また、第８実施例では、誤り位置多項式を
算出する際の誤り位置多項式算出回路の回路構成を図20
〜22に示す構成をとってきたがこの構成に限るものでは
なく、図11または図14に示す回路構成をとる誤り訂正装
置において、除算回路100 へ被除数として入力される多
項式が、除多項式であった場合と被除多項式であった場
合とで誤り位置多項式を算出する誤り位置算出回路での
演算方法を切り換えるように構成すれば同様の効果を奏
する。例えば、本実施例では商多項式の０次の係数デー
タを１に正規化したが、商多項式の最大次数の係数を１
に正規化する場合においても、商多項式の求め方の詳細
は省略するが上述のように誤り位置算出手段中の商多項
式を求める演算方法を切り換えれば同様に求められる。

【０２２７】また、第８実施例では、商多項式が２次の
場合または除算回路100 より出力される除算結果が０の
場合についても、図21または図22に示す回路構成により
商多項式を算出したが、商多項式がある次数以上の場合
または除算回路100 より出力された係数データに０の係
数データが含まれていた場合、商多項式を算出せず誤り
検出として処理し制御の簡略化及び回路規模の縮小を図
ってもよい。

【０２２８】第９実施例．以下、本発明の第９実施例に
ついて説明する。本実施例では図11に示す誤り訂正装置
を用いた場合について説明する。図23に第９実施例のブ
ロック構成図を示す。本実施例では図11に示す誤り訂正
装置のコア回路の構成にイレージャ訂正を行う際に必要
となる修正シンドロームを算出するためのセレクタを追
加した構成になっている。図において81a, 81b, 85〜8
8，95，100 及び101 は図11と同一であるので説明は省
略する。130,131,132 はセレクタ、133 はイレージャ位
置を入力する入力端子である。なお、イレージャ訂正を
行う際は、上記被除多項式及び除多項式を記憶するレジ
スタ81a, 81bの数は、修正シンドロームの各係数データ
を記憶するため、（修正シンドロームの最大次数＋１）
個のレジスタが被除数及び除数各々に必要となる。

【０２２９】イレージャ訂正とは誤りの位置はわかって
いるが誤り数値がわからないといった場合の誤り訂正に
用いられる方法で、簡単に述べると、誤り位置情報より
修正シンドロームを計算し、この修正シンドロームをも
とに図25に示すユークリッドアルゴリズムを実行し誤り
訂正を行う。その際、ユークリッドアルゴリズムにおい
ては終了条件を変えて、シンドローム多項式を修正シン
ドローム多項式に置き換えるだけで他は変わらない。
（イレージャがある場合のユークリッドアルゴリズムの
詳しい説明は前述の「符号理論」のpp.173〜175 を参
照）

【０２３０】上記修正シンドロームの算出方法を以下に
簡単に説明する。いま、再生または受信データより算出
されたシンドローム多項式Ｓ（Ｚ）を Ｓ（Ｚ）＝Ｓ₁₅Ｚ¹⁵＋Ｓ₁₄Ｚ¹⁴＋Ｓ₁₃Ｚ¹³＋・・・Ｓ₁
Ｚ＋Ｓ₀ とし、またイレージャの位置をα₀ ・・・α_k とする。
この際、修正シンドロームＳ（ｚ）’は Ｓ（ｚ）’＝Ｓ（ｚ）×｛（Ｚ＋α₀ ）×（Ｚ＋α₁ ）
×・・・×（Ｚ＋α_k ）｝ で算出される。

【０２３１】以下、図23を用いて修正シンドロームＳ
（Ｚ）’を求める際の回路動作を説明する。シンドロー
ム生成が終了するとユークリッド演算のコア回路ではレ
ジスタ81b にシンドローム多項式の各係数データがセッ
トされる。その際、イレージャ数によりシンドローム多
項式の最大次数の係数が記憶されるレジスタ位置が変わ
る。レジスタ81b にシンドローム多項式の係数データが
セットされるとユークリッド演算制御回路101 より出力
される制御信号によりセレクタ130 は誤り位置情報を、
セレクタ131 はレジスタ81b の出力を、セレクタ132 は
レジスタ81b に記憶されている１次次数が高いシンドロ
ーム多項式の係数データを選択するように制御される。
そして、レジスタ81b の内容を右側にシフトすることに
より Ｓ（Ｚ）×Ｚ＋Ｓ（Ｚ）×α₀ を実行する。（なお、α₀ はイレージャの位置情報を示
す。）数12に、具体的な筆算結果を示す。

【０２３２】

【数１２】

【０２３３】なお、最大次数Ｓ₁₅については演算が行わ
れても変わらないため係数をそのままシフトするように
構成するものとする。また、０次の係数はＳ₀ ×α₀ の
みを実行するように構成する。そして、この動作を、逐
次行うことにより修正シンドロームを算出する。図24に
修正シンドロームを算出する際のセレクタ131, 132の接
続状態を示す。なお、この図は図23に示す回路の１部の
接続状態を示したものである。図に示すように本実施例
では修正シンドロームを算出する際はレジスタ81a は動
作しない。

【０２３４】修正シンドロームの算出が終了すると図23
に示す誤り訂正装置のコア回路はセレクタ130 を除算回
路100 の出力を、セレクタ131 はレジスタ81a の出力を
選択するように切り換えられる。また、セレクタ132 は
同次数のレジスタ81b の出力を選択するように切り換え
られ、各構成要素の接続が図11に示すものと同一の構成
になる。一方、ユークリッド演算制御回路101 では、修
正シンドロームを求める際、イレージャ数により図25に
示す終了条件ｕを ｕ＝ｔ から ｕ＝（２×ｔ＋ｋ）／２ と設定する。なお、ｋはイレージャ訂正を行なうシンボ
ルの数である。

【０２３５】ユークリッド演算が開始されるとまず始
め、ユークリッド演算制御回路101 より出力されるユー
クリッド演算開始信号をもとにレジスタ81a に初期値で
ある被除多項式Ｚ^2tの係数が記憶されるとともに、レジ
スタ81b に除多項式である修正シンドローム多項式Ｓ
（Ｚ）’の各係数データが記憶される。また、次数検出
回路87, 88のカウンタにはそれぞれ次数の初期値である
16と15とがセットされる。次数検出回路87, 88内のカウ
ンタは被除多項式の係数データを記憶しているレジスタ
81が１回シフトされるたびにカウント値が１つ下がるよ
うに構成されている。それと同時に、除多項式である修
正シンドローム多項式は次数検出回路88で最高次数の係
数データが０であるか判定する。ユークリッド演算制御
回路101 では、次数検出回路88で検出された除多項式
（修正シンドローム多項式）の最大次数の係数が０の場
合、除多項式の係数データが記憶されているレジスタ81
b の内容をシフトし（なお、この際加算回路86での加算
動作を行わずレジスタ81b の内容をそのままシフトする
構成になっている）最大次数のデータが０でなくなるま
でシフト動作を繰り返す。その際、次数検出回路88中の
カウンタはカウント値をシフト動作が行われるたびに１
づつ減らされる。

【０２３６】また、第５実施例と同様に、被除多項式の
係数データが記憶されているレジスタ81a はクロックが
入力されると加算回路86の出力がラッチされるように構
成されており、除多項式の係数データが記憶されている
レジスタ81b は係数データが保持されるように構成され
ている。この動作を、被除多項式の次数が除多項式の次
数より小さくなるまで繰り返す。

【０２３７】ユークリッド演算制御回路101 では、次数
検出回路87（または88）より出力される上記剰余多項式
の次数をもとに、剰余の次数が上記イレージャ訂正を行
なう際に新たに設定されたユークリッド演算の終了条件
を満たしていればユークリッド演算を終了し、終了条件
を満たしていなければ前回の演算で除多項式であった多
項式を被除多項式として、また上記剰余多項式を除多項
式として演算を実行する。従来例のように交換手段を有
していないので回路の接続状態は変わらないが、レジス
タ81a に供給されていたクロック１が止められて、反対
にレジスタ81bにクロック２が供給される。よって、レ
ジスタ81a の内容が保持され、レジスタ81b に剰余多項
式の係数が逐次記憶される。

【０２３８】その際、ユークリッド演算回路中の除算回
路では、次数検出回路88により被除多項式（剰余多項
式）の最大次数が０であるかを判定し、０であった場合
レジスタ81b に記憶されている被除多項式（剰余多項
式）の内容をそのまま１つシフトするように制御信号を
出力する。これは、除算回路100 へ出力される除数と被
除数を格納するレジスタが決まっており被除多項式の係
数データが除数として用いられる場合、被除多項式の最
大次数の係数が０と成ってしまうと被除数（除多項式の
最大係数）を０で割ることになり、解（出力）が不定と
なってしまう場合が生じるためである。なお、本実施例
では除算回路100 の構成を図18に示す構成としているの
で最大次数の係数データが０の場合もあまり気にせず除
算動作を行える。

【０２３９】上記例と同様に、被除多項式の剰余の次数
が除多項式次数より小さくなるまで被除多項式の係数デ
ータを記憶しているレジスタの内容を演算しながらシフ
ト動作を繰り返すことにより除算を実行する。そして、
上記剰余多項式の次数を判定し所定の条件を満たしてい
なければレジスタ81a, 81bに供給するクロックを切り換
えてユークリッドアルゴリズムに基づく除算動作を再び
行う。これにより、リード・ソロモン符号を復号する際
に、イレージャ訂正をも考慮したユークリッドアルゴリ
ズムに基づくガロア体上の多項式同士の除算を１多項式
毎に行うことができ、誤り訂正処理速度を向上させるこ
とが出来るとともに交換手段（セレクタ）を持たないた
め回路規模の縮小が図れ、またセレクタ制御も必要なく
なる。

【０２４０】上記実施例５〜９では光ディスク等に採用
されている最小ハミング距離17のリード・ソロモン符号
について述べたがこれに限るものではなく最小ハミング
距離が17以外の符号でも同様の効果を奏する。また、上
記実施例に示す回路構成にて、最小ハミング距離が異な
る２種類以上のリード・ソロモン符号も復号できる。例
えば、積符号形式のリード・ソロモン符号の復号も同一
の回路でユークリッドアルゴリズムの初期値及び終了条
件をかえるだけで復号することができる。

【０２４１】また、各実施例では誤り訂正符号としてリ
ード・ソロモン符号を用いた場合について説明したがＢ
ＣＨ符号などの他の線形誤り訂正符号の復号に上記除算
回路を用いて復号しても同様の効果を奏する。

【０２４２】また、各実施例では除算演算時、レジスタ
81a, 81bのシフト、及びデータの保持をクロック１, ２
を制御することにより実行したがこれに限るものではな
く、例えばレジスタ81a, 81bの入力にセレクタを設け、
セレクタにより除多項式側のレジスタは自分自身の出力
をラッチし、被除多項式側のレジスタは加算回路86の出
力をラッチする様に制御してもよい。

【０２４３】また、被除多項式と除多項式との交換判定
は次数検出回路87，88より出力される各多項式の次数差
を検出する方法に限るものではない。例えば、被除多項
式の次数と除多項式の次数との差を除算を始める前に予
め求めておき、この情報をもとに一義的に除算回路のシ
フト回数を決定し次数差を検出せず除算を行うなどの方
法を用いてもよい。

【０２４４】また、各実施例では、シンドローム多項
式, 剰余多項式等の次数を検出する際、レジスタ81a, 8
1bにおける最大次数の係数が記憶されているレジスタの
みに次数検出回路87, 88を接続し検出していたが、これ
に限るものではなく、例えば、各係数データを記憶する
レジスタ81に係数判定回路（係数データが０であるか否
かを判定する回路）を設けて次数判定を行ってもよい。

【０２４５】更に、詳細は省略するがユークリッドアル
ゴリズム以外、例えば剰余復号等にも上記回路構成を適
用できることは言うまでもない。

【０２４６】

【発明の効果】以上のように第１発明の誤り訂正装置
は、入力信号にあらかじめ付加されている線形符号であ
る誤り訂正符号によって符号化された信号中に発生する
誤りを訂正するための誤り訂正装置にあって、誤り訂正
符号が付加された単位情報ブロックより再生または受信
信号中に含まれる誤りにのみ依存するシンドロームを生
成するためのシンドローム生成手段と、生成されたシン
ドロームを基に誤り位置多項式σ（ｚ）及び誤り数値多
項式ω（ｚ）を算出する誤り位置・数値多項式演算手段
と、算出された誤り位置多項式σ（ｚ）を基に誤り位置
を算出する誤り位置算出手段と、上記算出された誤り数
値多項式ω（ｚ）及び誤り位置情報を基に誤り訂正を行
う誤り訂正手段とを有し、誤り訂正時に、少なくともシ
ンドローム生成手段、誤り位置・数値多項式演算手段及
び誤り位置算出手段の３つの処理動作を並行して動作す
るように構成されているので、例えば図33に示す１誤り
訂正ブロックに復号処理を施す際２倍以上のスピードで
処理を完了することが可能となる。

【０２４７】また第２発明の誤り訂正装置は、比較的高
速化が図れるシンドローム生成手段及び誤り位置算出手
段を駆動するクロックを、誤り位置・数値多項式演算手
段を駆動するクロックより高い周波数のクロックで駆動
するように構成したので、１誤り訂正ブロックを復号す
るのに要する復号時間を短縮することができ、処理速度
を上げることが可能となる。

【０２４８】また第３発明の誤り訂正装置は、比較的計
算にステップ数を要するシンドローム生成手段及び誤り
位置算出手段のステップ数にあわせて誤り位置・数値多
項式演算手段のステップ数を増やすことにより回路規模
を図ったので、誤り訂正装置全体の復号速度を損ねるこ
となく回路規模の削減を図れる。

【０２４９】また第４発明の誤り訂正装置は、誤り訂正
手段によりＲＡＭ内のデータに誤り訂正を施す際に誤り
位置算出手段より出力される誤り位置情報に基づく誤っ
たデータを逐次読み出した後に、誤り訂正を施したデー
タを逐次ＲＡＭに書き込むように構成したので、通常１
シンボルの誤り訂正を行う際、ＲＡＭからのデータの読
み出し、誤り訂正、ＲＡＭへのデータの書き込みと最低
３ステップかかっていた動作を２ステップで行うことが
可能となり、誤り訂正装置の高速化が図れる。よって、
高速化のネックとなるＲＡＭのデータのアクセスを常に
行うように構成されているので、回路規模の増大を極力
控えて最高速の誤り訂正装置を構成することが可能とな
る。

【０２５０】また第５発明の誤り訂正装置は、所定の被
除多項式を除多項式で除算し、さらにその剰余を除多項
式として、また前記除多項式を被除多項式として除算し
て剰余の多項式の次数がある条件を満たすまで上記動作
を繰り返すユークリッド互除の処理過程を含んでリード
・ソロモン符号による誤り訂正処理を行う誤り訂正装置
において、上記被除多項式及び除多項式の各係数データ
を記憶しておくレジスタをシフトレジスタ状に配置し、
そして、上記２つの多項式の最大次数の係数同士を除算
する除算回路と、除算回路の除数側に設定された多項式
の係数データと除算回路の出力を乗算する乗算回路と乗
算回路の出力と除算回路の被除数側に設定された多項式
の係数データを加算する加算回路とを配置し、ガロア体
上の除算を実行する際に被除多項式の係数データが記憶
されているレジスタの内容を逐次シフトすることにより
ユークリッド互除過程に基づく除算を実行するように構
成しているので、ユークリッド互除過程におけるガロア
体上の多項式同士の除算を実行する際、各多項式の係数
データを交換するためのセレクタをもたずにユークリッ
ド互除過程中の除算を実行するため、回路規模の縮小を
図れるとともにセレクタ制御が不必要になり回路の簡素
化が図れる。

【０２５１】また第６発明の誤り訂正装置は、乗算回路
をユークリッド互除過程における初期値Ｚ^2tをセットす
るレジスタ群に配置し乗算回路の数を削減するように構
成したので、除算動作を行うため乗算回路の数を１つ減
らすことができ、前述したように約 400ゲート程度の回
路規模の縮小が図れる。

【０２５２】また第７発明の誤り訂正装置は、除算回路
において、除数として入力される多項式の最大次数の係
数が０であった場合、除算回路の出力を１として出力す
るように構成したので、ユークリッド演算制御回路で被
除多項式または除多項式の最大次数が０であった場合で
も、特別な制御を加えることなくユークリッドアルゴリ
ズムにおけるガロア体上の多項式同士の演算を実行で
き、制御回路の簡素化が図れる。

【０２５３】また第８発明の誤り訂正装置は、除算回路
の出力を用いて誤り位置多項式σ（Ｚ）を算出する際、
除算回路に入力される被除多項式の最大次数の係数デー
タが除数として扱われる場合と被除数として扱われる場
合とで算出方法を切り換えるように構成されているの
で、誤り位置多項式が正確に算出されるとともに、復号
ステップ数を削減できる。

【０２５４】また第９発明の誤り訂正装置は、除算手段
の出力と誤り位置情報を選択する第１の選択手段と、除
算手段の除数側の多項式の係数を記憶しておく記憶手段
の出力と、除算手段の被除数側の多項式の係数データを
記憶しておく記憶手段の出力とを選択する第２の選択手
段と、除算手段の除数側の多項式の係数とそれより１次
次数が高い除算手段の除数側の多項式の係数とを選択す
る第３の選択手段と、第１の選択手段の出力と第３の選
択手段の出力とを乗算する乗算手段と、乗算手段の出力
と第２の選択手段の出力とを加算する加算手段とを有
し、消失訂正時に修正シンドローム多項式を演算する
際、第１，第２及び第３の選択手段でそれぞれ誤り位置
情報，上記除算手段の除数側の多項式の係数データ及び
１次次数が高い多項式の係数を選択するように構成して
いるので、イレージャ訂正を行う際に算出する修正シン
ドローム多項式の算出をセレクタ回路を付加するだけで
行うことができ、回路規模の増大を極力抑えてイレージ
ャ訂正にも対応できる。

【図面の簡単な説明】

【図１】本発明の誤り訂正装置のブロック構成図であ
る。

【図２】図１に示す誤り訂正装置の回路動作を説明する
ためのタイミングチャートである。

【図３】本発明の他の誤り訂正装置のブロック構成図で
ある。

【図４】図３に示す誤り訂正装置の回路動作を説明する
ためのタイミングチャートである。

【図５】ユークリッド演算回路のガロア体上の多項式の
除算回路のブロック構成図である。

【図６】図５に示す除算回路の回路動作を説明するため
のタイミングチャートである。

【図７】誤り訂正装置全体の動作を説明するためのタイ
ミングチャートである。

【図８】ユークリッド演算回路のガロア体上の多項式の
他の除算回路のブロック構成図である。

【図９】誤り訂正回路の回路動作を説明するためのタイ
ミングチャートである。

【図１０】誤り訂正回路の回路動作を説明するための他
のタイミングチャートである。

【図１１】本発明の誤り訂正装置のユークリッド演算を
行う際のガロア体上の多項式同士の除算を行う他の除算
回路のブロック構成図である。

【図１２】図１１に示す除算回路の回路動作を説明する
ための図である。

【図１３】図１１に示す除算回路の回路動作を説明する
ための図である。

【図１４】本発明の誤り訂正装置のユークリッド演算を
行う際のガロア体上の多項式同士の除算を行う他の除算
回路のブロック構成図である。

【図１５】図１４に示す除算回路の回路動作を説明する
ための図である。

【図１６】図１４に示す除算回路の回路動作を説明する
ための図である。

【図１７】図１４に示す除算回路の回路動作を説明する
ための図である。

【図１８】本発明の誤り訂正装置における除算回路のブ
ロック構成図である。

【図１９】本発明の誤り訂正装置における加算回路のブ
ロック構成図である。

【図２０】本発明の誤り訂正装置における誤り位置算出
手段の回路構成図である。

【図２１】本発明の誤り訂正装置における他の誤り位置
算出手段の回路構成図である。

【図２２】本発明の誤り訂正装置における更に他の誤り
位置算出手段の回路構成図である。

【図２３】イレージャ訂正を考慮した本発明の誤り訂正
装置のユークリッド演算を行う際のガロア体上の多項式
同士の除算を行う除算回路のブロック構成図である。

【図２４】本発明の誤り訂正装置の回路動作を説明する
ための回路接続図である。

【図２５】ユークリッドアルゴリズムの動作を説明する
フローチャートである。

【図２６】従来の誤り訂正装置のブロック構成図であ
る。

【図２７】シンドローム生成回路のブロック構成図であ
る。

【図２８】従来の誤り訂正演算回路のブロック構成図で
ある。

【図２９】従来のユークリッド演算回路のガロア体上の
多項式の除算回路のブロック構成図である。

【図３０】チェンサーチ回路のブロック構成図である。

【図３１】誤り訂正符号による符号化及び復号化の手順
を示すフローチャートである。

【図３２】家庭用ディジタルＶＴＲに採用されている誤
り訂正符号の構成図である。

【図３３】図３２に示す誤り訂正符号の記録方向の１ラ
インの構成図である。

【図３４】従来の誤り訂正装置の動作を説明するための
タイミングチャートである。

【図３５】従来の誤り訂正装置の回路動作を説明するた
めのタイミングチャートである。

【図３６】Fig.12は従来の誤り訂正装置の動作を説明す
るためのタイミングチャートである。

【図３７】従来の誤り訂正装置のユークリッド演算を行
う際のガロア体上の多項式同士の除算を行う除算回路の
ブロック構成図である。

【図３８】従来のガロア体上の多項式同士の除算を行な
うための除算回路動作を説明するための図である。

【図３９】従来のガロア体上の多項式同士の除算を行な
うための除算回路動作を説明するための図である。

【図４０】従来の誤り訂正装置のユークリッド演算を行
う際のガロア体上の多項式同士の除算を行う除算回路動
作を説明するための図である。

【図４１】従来の誤り訂正装置のユークリッド演算を行
う際のガロア体上の多項式同士の除算を行う除算回路動
作を説明するための図である。

【符号の説明】

１ ＲＡＭ ２ シンドローム生成回路 20 ユークリッド演算回路 21 チェンサーチ回路 22 誤り訂正回路 41 誤り訂正装置制御回路 81a, 81b レジスタ 85 乗算回路 86 加算回路 100 除算回路 101 ユークリッド演算制御回路 130 セレクタ 131 セレクタ 132 セレクタ

───────────────────────────────────────────────────── フロントページの続き (72)発明者 石本 順子 京都府長岡京市馬場図所１番地 三菱電機 株式会社電子商品開発研究所内

Claims (9)

【特許請求の範囲】
1. 【請求項１】 入力信号に付加されている線形符号であ
   る誤り訂正符号を用いて誤り訂正を行う誤り訂正装置に
   おいて、前記入力信号からシンドロームを生成するシン
   ドローム生成手段と、該シンドローム生成手段の出力に
   基づき誤り位置多項式と誤り数値多項式とを演算する演
   算手段と、該演算手段より導出された誤り位置多項式よ
   り誤り位置を算出する誤り位置算出手段と、該誤り位置
   算出手段より出力される誤り位置情報と前記誤り数値多
   項式とを用いて誤り数値を導出して、入力信号中の誤り
   位置が検出された誤ったデータに誤り訂正を施す訂正手
   段と、前記シンドローム生成手段，前記演算手段及び前
   記誤り位置算出手段の３つの手段を並行して動作させる
   制御手段とを備えることを特徴とする誤り訂正装置。
2. 【請求項２】 前記シンドローム生成手段及び前記誤り
   位置算出手段の駆動クロックの周波数を、前記演算手段
   を駆動するクロックの周波数より高くすることを特徴と
   する請求項１記載の誤り訂正装置。
3. 【請求項３】 前記演算手段の復号ステップ数が、前記
   シンドローム生成手段または前記誤り位置算出手段のス
   テップ数とほぼ等しいことを特徴とする請求項１記載の
   誤り訂正装置。
4. 【請求項４】 入力信号に付加されている線形符号であ
   る誤り訂正符号を用いて誤り訂正を行う誤り訂正装置に
   おいて、前記入力信号を一旦蓄える記憶手段と、前記入
   力信号からシンドロームを生成するシンドローム生成手
   段と、該シンドローム生成手段の出力に基づき誤り位置
   多項式と誤り数値多項式とを演算する演算手段と、該演
   算手段より導出された誤り位置多項式より誤り位置を算
   出する誤り位置算出手段と、該誤り位置算出手段より出
   力される誤り位置情報と前記誤り数値多項式とを用いて
   誤り数値を導出して、入力信号中の誤り位置が検出され
   た誤ったデータに誤り訂正を施す訂正手段と、該訂正手
   段が誤り訂正を行う際、前記誤り位置情報に基づく誤っ
   た情報を少なくとも２つ以上連続して前記記憶手段より
   読み出した後、誤り訂正が施されたデータを前記誤り位
   置情報に基づく誤ったデータと逐次書き換える動作を誤
   り位置が検出されたデータがすべて訂正されるまで繰り
   返すように、前記訂正手段を制御する制御手段とを備え
   ることを特徴とする誤り訂正装置。
5. 【請求項５】 所定の被除多項式を除多項式で除算し、
   その後その剰余を除多項式とし前記除算を行なった際の
   除多項式を被除多項式として除算する動作を、剰余の多
   項式の次数がある条件を満たすまで繰り返すユークリッ
   ド互除の処理過程を含んでリード・ソロモン符号による
   誤り訂正処理を行なう誤り訂正装置において、前記２つ
   の多項式の各々の係数を記憶する記憶手段と、該記憶手
   段に記憶されている２つの多項式の最大次数の係数同士
   のガロア体上の除算を行なう除算手段と、該除算手段の
   除数側の多項式の係数を記憶しておく前記記憶手段の出
   力と前記除算結果とをガロア体上で乗算する乗算手段
   と、該乗算手段の出力と、前記除算手段の被除数側の多
   項式の係数を記憶しておく前記記憶手段の出力とをガロ
   ア体上で加算する加算手段とを備え、前記記憶手段をそ
   れぞれシフトレジスタ状に配置してガロア体上の多項式
   同士の除算回路を構成し、被除多項式が記憶されている
   前記憶手段の内容を逐次シフトすることにより多項式同
   士の除算を実行するように構成したことを特徴とする誤
   り訂正装置。
6. 【請求項６】 前記乗算手段が、ユークリッド互除法に
   より多項式同士の除算を行なう際、初期値としてＺ^2tが
   セットされる前記記憶手段側に配置されることを特徴と
   する請求項５記載の誤り訂正装置。
7. 【請求項７】 前記除算手段において、除数として入力
   される多項式の最大次数の係数が０であった場合、前記
   除算手段の出力を１とすることを特徴とする請求項５ま
   たは６記載の誤り訂正装置。
8. 【請求項８】 前記除算手段の出力より誤り位置多項式
   を算出する際、前記除算手段に入力される被除多項式の
   係数が除数として扱われる場合と被除数として扱われる
   場合とで演算方法を切り換えることを特徴とする請求項
   ５，６または７記載の誤り訂正装置。
9. 【請求項９】 前記除算手段の出力と誤り位置情報とを
   選択する第１の選択手段と、前記２つの多項式の各々の
   係数を記憶しておく記憶手段の出力を選択する第２の選
   択手段と、前記除算手段の除数側の多項式の係数とそれ
   より１次次数が高い前記除算手段の除数側の多項式の係
   数とを選択する第３の選択手段と、前記第１の選択手段
   の出力と前記第３の選択手段の出力とを乗算する乗算手
   段と、該乗算手段の出力と前記第２の選択手段の出力と
   を加算する加算手段とを更に備え、消失訂正時に修正シ
   ンドローム多項式を演算する際、前記第１，第２及び第
   ３の選択手段は、それぞれ誤り位置情報，前記除算手段
   の除数側の多項式の係数及び１次次数が高い多項式の係
   数を選択するように構成したことを特徴とする請求項
   ５，７または８記載の誤り訂正装置。