JPH10308675A

JPH10308675A - リードソロモン復号装置

Info

Publication number: JPH10308675A
Application number: JP9116882A
Authority: JP
Inventors: Shigeru Okita; 茂沖田
Original assignee: Texas Instruments Japan Ltd
Current assignee: Texas Instruments Japan Ltd
Priority date: 1997-05-07
Filing date: 1997-05-07
Publication date: 1998-11-17
Anticipated expiration: 2017-05-07
Also published as: JP3850512B2; US6131179A

Abstract

(57)【要約】【課題】回路規模を大幅に増大させることなく、復号
演算を高速に行うことが可能なリードソロモン復号装置
を提供する。【解決手段】データ系列からシンドロームおよび消失
データを含む復号演算入力パラメータを生成する復号演
算入力パラメータ演算器３０９と、所定の復号演算操作
を示す命令コードに基づいて、復号演算入力パラメータ
を用いた復号演算を行い、誤り値データおよび誤り位置
データを含む復号演算出力パラメータを生成する復号演
算処理部３０４と、前記復号演算出力パラメータを用い
て訂正操作を行う訂正操作実行器３１２と、復号演算処
理部３０４に出力する復号演算入力パラメータと、訂正
操作実行器３１２に出力する復号演算出力パラメータと
を選択的に記憶するレジスタＢ３１３とを有する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、記録媒体やディジ
タル伝送の誤り訂正符号化として用いられるリードソロ
モン符号化された信号を復号するリードソロモン復号装
置に関する。

【０００２】

【従来の技術および発明が解決しようとする課題】リー
ド・ソロモン符号（以下ＲＳ符号）は、その符号化効率
の良さとバーストエラーに対する適正から、主に記録媒
体やディジタル伝送の外符号に用いられている。例えば
コンパクトディスクで採用されているエラー訂正符号
は、ＣＩＲＣ訂正符号（クロスインターリーブ・リード
・ソロモン符号）と称され、インターリーブの技法と組
み合わせた積符号である。その外符号としてＲＳ（２
８、２４）符号が、内符号としてＲＳ（３２、２８）符
号が採用されていて、それぞれＣ２符号及びＣ１符号と
呼ばれる。いずれの符号とも、ひとつのＲＳ符号化シン
ボルは１バイトで構成され、ひとつのＲＳ符号化ブロッ
クは４バイトのパリティ検査列を含んでいる。

【０００３】一般に、ＲＳ符号は２ｔシンボルの検査列
でｔシンボルの訂正が可能である。ｔシンボルの訂正に
はｔ個の誤り位置とそのそれぞれの誤りに対応したｔ個
の誤りの値を知る必要がある。ＲＳ符号はｔ個の誤りの
発生に対し、復号側でシンドローム演算をすることで２
ｔ個の線形独立な方程式を得る。この方程式を解くこと
で２ｔ個の未知数である、前記ｔ個の誤り位置とそのそ
れぞれの誤り位置に対応した前記ｔ個の誤りの値を求め
ることができる。

【０００４】一方、ＣＩＲＣ符号のように積符号の構成
を取っているものは、内符号に対する内側ＲＳ復号にお
いて訂正できなかったＲＳ符号化ブロックや誤訂正の可
能性の比較的高いＲＳ符号化ブロックに消失フラグを付
加することで、外符号に対応した外側ＲＳ復号において
消失エラー訂正が可能になる。消失フラグが付加された
内符号の消失シンボルはデ・インターリーブによって複
数の外側のＲＳ符号化ブロックに分散される。消失エラ
ー訂正では、前記消失シンボルに誤りが存在すると仮定
してシンドローム演算から得られる連立方程式を解く。
誤り位置を既知として解くので最大２ｔ個の誤りを値を
求めることができる。即ち、２ｔシンボルの検査列を持
つＲＳ符号に対しては、消失エラー訂正を実行すること
で最大２ｔシンボルの誤り訂正が可能である。

【０００５】ＣＩＲＣ符号を例に挙げて、消失エラー訂
正の手法を説明する。ＣＩＲＣ符号の場合、内符号であ
るＣ１符号のＲＳ復号（Ｃ１復号）において消失フラグ
を付加することで、外符号であるＣ２符号のＲＳ復号
（Ｃ２復号）で消失エラー訂正が可能である。Ｃ１符
号、Ｃ２符号ともにｔ＝２であるから、Ｃ１復号は最大
２バイトの訂正が、Ｃ２復号の消失エラー訂正では最大
４バイトの訂正がそれぞれ可能である。そのＣ２復号に
おけるシンドロームｓ₀〜ｓ₃と、誤り値ｅ₁〜ｅ₄が
次のようにして求められる。ＣＩＲＣ符号の符号生成多
項式Ｇｅ（ｘ）は、下記式（１）で示される。

【０００６】

【数１】

【０００７】ここでαはガロア体の原始元である。この
とき、入力系列からシンドローム演算により得たｓ₀〜
ｓ₃は、前記ｘ₁〜ｘ₄およびｅ₁〜ｅ₄との間に下記
式（２）で示される関係がある。

【０００８】

【数２】

【０００９】ここで記号‘・’はガロア体上の乗算を示
し、記号‘＋’はガロア体上の加算を示す。以下、ある
ガロア体の元同士の四則演算は、そのガロア体上での演
算を示すこととする。前記式（２）を連立方程式を解い
て、未知数である誤り値ｅ₁〜ｅ₄を求めると次のよう
になるまず、ｅ₄は、下記式（３）として得られる。

【００１０】

【数３】

【００１１】この得られたｅ₄を前記式（２）に代入し
て３つの等式から成る連立方程式を再構成する。即ち、
ＣＩＲＣ符号で用いられているガロア体は加算と減算が
同じであることに注意して下記式（４）のように修正す
ることで、前記式（２）の連立方程式は下記式（５）に
変形される。

【００１２】

【数４】

【００１３】

【数５】

【００１４】これは、連立方程式の解を、手計算で順に
求めるときによく用いられる手法である。次に、式
（５）の連立方程式を解いてｅ₃を求めると、下記式
（６）のようになる。

【００１５】

【数６】

【００１６】同様にして修正を施すことで、前記式
（５）の連立方程式は下記式（７），（８）のように変
形される。

【００１７】

【数７】

【００１８】

【数８】

【００１９】さらに、式（８）の連立方程式を解いてｅ
₂を求めると、下記式（９）となる。

【００２０】

【数９】

【００２１】次に、この求めたｅ₂を前記式（８）に代
入して下記式（１０）を得る。

【００２２】

【数１０】

【００２３】このようにして、誤り値ｅ₁〜ｅ₄を順次
求めることができる。上述した手法において、情報とし
て元来もっているものと、実際の復号の際に行われる演
算操作とを区別するために、記号‘＝’と‘←’とを使
い分けている。つまり、実際の復号演算に対応するの
は、式（３）、（４）、（６）、（７）、（９）および
（１０）であり、少なくとも、ガロア体上の加算が２３
回、乗算が１７回、除算が３回必要である。一方、消去
エラー訂正を行わない場合には、Ｃ２復号で最大２バイ
トまで訂正（２重エラー訂正）ができる。このときは、
シンドロームｓ₀〜ｓ₃から、誤り値ｅ₁，ｅ₂と誤り
位置ｘ’₁，ｘ’₂を求める。以上は、４重消去エラー
訂正、すなわち、消去位置の数が４の場合の復号演算処
理過程である。

【００２４】以下、従来のリードソロモン復号装置につ
いて説明する。図１０は、従来のリードソロモン復号装
置１の構成図である。図１０に示すように、リードソロ
モン復号装置１は、メモリブロック２、バスＩ／Ｆブロ
ック３および復号演算処理部４を備えている。メモリブ
ロック２は、スクラッチパッドメモリ５，６およびスイ
ッチ７，８を備えている。スイッチ７は、入力データを
選択的にスクラッチパッドメモリ５，６に出力する。ス
イッチ８は、スクラッチパッドメモリ５の記憶内容を選
択的に訂正操作実行器１２に出力する。

【００２５】バスＩ／Ｆブロック３は、入力パラメータ
演算器９、レジスタＢ_OUT１０、バイナリカウンタ１
１、訂正操作実行器１２およびレジスタＢ_IN１３を備え
ている。復号演算処理部４は、スイッチ１４、レジスタ
Ｇ_IN１５、レジスタＧ_OUT１６および復号演算器１７を
備えている。図１１は、リードソロモン復号装置１の動
作時におけるデータおよび構成要素の時系列的な状態を
示し、（Ａ）は入力データ、（Ｂ）は出力データ、
（Ｃ）はレジスタＢ_OUT１０の記憶状態、（Ｄ）はレジ
スタＢ_IN１３の記憶状態、（Ｅ）はレジスタＧ_OUT１６
の記憶状態、（Ｆ）はレジスタＧ_IN１５の記憶状態、
（Ｇ）は復号演算器１７の処理状態をそれぞれ示してい
る。

【００２６】図１１に示すように、メモリブロック２の
スクラッチパッドメモリ５においてＣ１符号に関する入
力データの入出力を行っているときには、バスＩ／Ｆブ
ロック３はＣ１符号に関する入力データ対して、入力パ
ラメータ演算器９において復号演算入力パラメータの計
算を行い、訂正操作実行器１２において訂正操作を行っ
ている。また、このとき、復号演算処理部４ではＣ２符
号に関する入力データについてＣ２復号処理が行われて
いる。

【００２７】また、スクラッチパッドメモリ６において
Ｃ２符号に関する入力データの入出力を行っているとき
には、バスＩ／Ｆブロック３はＣ２符号に関する入力デ
ータ対して、入力パラメータ演算器９において復号演算
入力パラメータの計算を行い、訂正操作実行器１２にお
いて訂正操作を行っている。また、このとき、復号演算
処理部４ではＣ１符号に関する入力データについてＣ１
復号処理が行われている。

【００２８】ここで、復号演算入力パラメータとは、具
体的には、シンドローム（Ｓ）および消失位置（Ｉ）で
ある。シンドローム（Ｓ）は、図１０に示す入力パラメ
ータ演算器９およびレジスタＢ_OUT１０の組み合わせに
よって演算される。図１２は、入力パラメータ演算器９
およびレジスタＢ_OUT１０の構成図である。図１２に示
すように、入力パラメータ演算器９は、乗算器２４〜２
７、加算器２０〜２３、消去フラグ検出器２８および分
配器２９を備えている。また、レジスタＢ_OUT１０は、
レジスタ３０〜３３およびレジスタ３４〜３７を備えて
いる。

【００２９】乗算器２４〜２７は、乗算係数が固定値の
ガロア体の乗算器であり、それぞれ×α⁰、×α¹、×
α²、×α³の乗算を行う。消去フラグ検出器２８は、
入力データに含まれる消去フラグが「１」であるか否か
を検出する。分配器２９は、入力データに含まれる各Ｒ
Ｓシンボル位置と対応して動作するバイナリカウンタ１
１の出力をレジスタＢ_OUT１０のレジスタ３４〜３７の
いずれかに出力して記憶させる。このレジスタ３４〜３
７の記憶結果が消失位置（Ｉ）を示す。

【００３０】消失位置（Ｉ）は、図１０に示す復号演算
器１７において、後述するコンバータにより、ガロア体
の表現に、すなわち「ｉ」から「αⁱ」に変換される。
具体的には、Ｉ＝｛ｉ₁，ｉ₂，ｉ₃，ｉ₄｝が、Ｘ＝
｛ｘ₁，ｘ₂，ｘ₃，ｘ₄｝に変換される。

【００３１】４重消失エラー訂正を実行する場合の前記
式（３），（４），（６），（７）および（１０）に対
応する復号演算は、復号演算処理部４において実行さ
れ、レジスタＢ_OUT１０からの復号演算入力パラメータ
Ｓ＝｛ｓ₀，ｓ₁，ｓ₂，ｓ₃｝と、Ｉ＝｛ｉ₁，
ｉ₂，ｉ₃，ｉ₄｝を変換して得られたＸ＝｛ｘ₁，ｘ
₂，ｘ₃，ｘ₄｝とを用いて、復号演算出力パラメータ
Ｅ＝｛ｅ₁，ｅ₂，ｅ₃，ｅ ₄｝およびＸ’＝Ｘ＝｛ｘ
₁，ｘ₂，ｘ₃，ｘ₄｝を得る。消失エラー訂正を行わ
ない場合には、前述した２重エラー訂正においては、復
号演算入力パラメータＳ＝｛ｓ₀，ｓ₁，ｓ₂，ｓ₃｝
を用いて、復号演算出力パラメータＥ＝｛ｅ₁，ｅ₂｝
およびＸ’＝｛ｘ’₁，ｘ’₂｝を得る。

【００３２】誤り位置ＸあるいはＸ’は、復号演算処理
部４において、後述するコンバータで、指数値に、すな
わちαⁱからｉに変換される。具体的には、Ｘ’＝Ｘ＝
｛ｘ ₁，ｘ₂，ｘ₃，ｘ₄｝がＩ＝｛ｉ₁，ｉ₂，
ｉ₃，ｉ₄｝に変換され、Ｘ’＝｛ｘ’₁，ｘ’₂｝が
Ｉ’＝｛ｉ’₁，ｉ’₂｝に変換される。

【００３３】図１３は、訂正操作実行器１２およびレジ
スタＢ_IN１３の構成図である。図１３に示すように、訂
正操作実行器１２は、比較器４０、加算器４５およびゲ
ートロジック４６を備えている。また、レジスタＢ_IN１
３は、レジスタ４１〜４４およびレジスタ４７〜５０を
備えている。

【００３４】バスＩ／Ｆブロック３は、レジスタＧ_OUT
１６から入力した誤り値（Ｅ）と誤り位置（Ｉ’）とを
用いて、訂正操作を実行する。バイナリカウンタ１１
は、スイッチ７，８によるスクラッチパッドメモリ５，
６からの出力の切り換わりに対応して動作し、バイナリ
カウンタ１１のバイナリカウンタ値が誤り位置（Ｉ’）
の構成要素のいずれか（ｉ’_n）と一致したときに、ゲ
ートロジック４６から対応する誤り値ｅ_nが加算器４５
に出力される。そして、加算器４５において、誤り値ｅ
_nと、スイッチ８からのメモリブロックのデータ出力と
について、ガロア体の加算が行われ、加算結果が出力デ
ータとなる。

【００３５】次に、復号演算処理部４について説明す
る。図１４は、復号演算処理部４の構成図である。図１
４に示すように、復号演算処理部４は、マイクロコード
ＲＯＭ５０、シーケンサ５１、デスティネイションコン
トローラ５２、ワーキングレジスタ５３、ＧＬＵ(Globa
l Logic Unit) ５４、ポート選択器５５を備えている。

【００３６】ＣＩＲＣ符号のようにｔが４より小さく、
連立方程式から解が直接的に求められる場合で、かつ、
処理スピードが比較的遅くても良いときには、復号演算
処理部４としては、ＲＩＳＣ(Reduced Instruction Set
Computer)型のものが用いられる。復号演算処理部４で
は、各演算は逐次的に行われ、演算セットは、ＧＬＵ５
４として時分割共有化される。、また、一連の演算処理
は、マイクロコード化されて、インストラクションコー
ドとしてマイクロコードＲＯＭ５０に格納され、シーケ
ンサ５１からのＲＯＭアドレスによって、処理順序（メ
モリからの読み出し順序）が制御される。

【００３７】また、途中の演算結果は、予め用意された
複数のワーキングレジスタ５３に一時的に記憶される
が、どのワーキングレジスタ５３に記憶するかは、イン
ストラクションコード内のデスティネイションコントロ
ールコードに記述されている。この手法によれば、処理
スピードの制限はあるものの、ＧＬＵ５４の時分割共有
化による装置の縮小化ができると共に、演算処理のマイ
クロコード化により設計の自由度を高めることができ
る。例えば、２つのガロア体の元同士の加算は、各ビッ
トの排他的論理和に相当し、復号演算処理部４では１ス
テップで実現できる。すなわち、ＧＬＵ５４は、ビット
毎の排他的論理和の機能を含んでいる。但し、ガロア体
における乗算は、加算に比べてはるかに複雑であり、こ
れをＲＯＭを用いて実現しようとすると、２バイトのア
ドレス入力に対して１バイトの出力を得ることになり、
非常に規模が大きくなってしまう。

【００３８】ＧＬＵ５４の構成について説明する。図１
５は、ＧＬＵ５４の構成図である。図１５に示すよう
に、ＧＬＵ５４は、オペレイションロジック６０，６
１、コンバータ６２，６３およびオペレイションセレク
タ６４を備えている。ＧＬＵ５４では、２つの入力デー
タａ，ｂのガロア体の元のそれぞれを、コンバータ６２
において、対応する原始元の指数の値に変換、すなわち
αⁱをｉに変換し、指数同士の加算を実行する。そし
て、その得られた加算結果を、コンバータ６３におい
て、対応するガロア体の元に変換、すなわち、ｉをαⁱ
に変換する。

【００３９】例えば、α^vとα^wの乗算を実行して、α
^V+Wを得るには、ＧＬＵ５４において、下記式（１１）
に示す４つの演算処理が必要で、少なくとも４ステップ
を要する。

【００４０】

【数１１】

【００４１】除算も同様で、乗算における加算の代わり
に減算を実行する。従って、上述した手法では、誤り値
ｅ₁ 〜ｅ₄を求めるには、上記式（３），（４），
（６），（７），（９）および（１０）における乗算・
除算が２０回あるので、これだけでも８０ステップ以上
必要となる。これに、２３回の加算を含めると、合計１
０３ステップ以上必要となる。そのため、高速処理の要
求に応えることができない。なお、ｔが４より大きい場
合には、前記式（２）に示したような連立方程式を解く
ことは非現実的であるため、ユークリッド復号法などの
繰り返しアルゴリズムが採用される。しかしながら、い
ずれにしても、ガロア体の乗算や除算に４ステップも必
要となると、高速処理の実現は困難である。

【００４２】一方、ＣＤ−ＲＯＭのデータ再生における
スピードの要求は、現在、２倍速から１２倍速にまで高
まっており、誤り訂正の処理ステップ数の制限が日増し
に厳しくなってきている。さらには、光学系の読み取り
誤差が、当然大きくなってくるわけで、前記消失エラー
訂正による訂正能力の強化が強く望まれている。つま
り、より高い機能を、より少ないステップ数で実現する
必要がある。

【００４３】１２倍速対応のＣ１復号およびＣ２復号を
実現するには、例えば演算の１ステップを１６ＭＨｚの
１クロック内で終了するとすれば、Ｃ１とＣ２の１回ず
つの復号を、１９２ステップ以内で実行する必要があ
る。これには分岐処理等の周辺処理を含めての条件なの
で、Ｃ２復号のコアの処理はその１／４以内のステップ
数で実現する必要がある。しかしながら、従来の構成で
は、例えばＣ２復号で消失エラー訂正を行うときに、そ
の訂正コアの処理だけで１０３ステップ以上の演算ステ
ップ数を要し、高速処理の要求に答えることができな
い。

【００４４】また、上述したリードソロモン復号装置１
では、図１０に示すように、バスＩ／Ｆブロック３には
レジスタＢ_OUT１０およびレジスタＢ_IN１３の２個のレ
ジスタが設けられていると共に、復号演算処理部４に
は、レジスタＧ_OUT１６およびレジスタＧ_IN１５の２個
のレジスタが設けられている。また、リードソロモン復
号装置１では、消失位置や誤り位置を用いた演算を、ガ
ロア体の指数表現で行なっているため、図１５に示すよ
うに、復号演算処理部４のＧＬＵ５４には、ガロア体の
元を対応する原始元の指数に変換するコンバータ６２
と、その逆変換を行なうコンバータ６３とが必要にな
る。そのため、リードソロモン復号装置１は、大規模な
ものになってしまうという問題がある。

【００４５】本発明は、上述した従来技術に鑑みてなさ
れ、本発明は、回路規模の縮小化を図れるリードソロモ
ン復号装置を提供することを目的とする。また、本発明
は、高速処理が可能なリードソロモン復号装置を提供す
ることを目的とする。

【００４６】

【課題を解決するための手段】上述した従来技術の問題
点を解決し、上述した目的を達成するために、本発明の
リードソロモン復号装置は、データ系列からシンドロー
ムおよび消失位置を含む復号演算入力パラメータを生成
する復号演算入力パラメータ演算手段と、所定の復号演
算操作を示す命令コードに基づいて、復号演算入力パラ
メータを用いた復号演算を行い、誤り値データおよび誤
り位置データを含む復号演算出力パラメータを生成する
復号演算手段と、前記復号演算出力パラメータを用いて
訂正操作を行う訂正操作手段と、前記復号演算手段に出
力する復号演算入力パラメータと、前記訂正操作手段に
出力する復号演算出力パラメータとを選択的に記憶する
記憶手段とを有する。

【００４７】本発明のリードソロモン復号装置では、復
号演算入力パラメータ演算手段における処理と、訂正操
作手段における処理とが同時に行われない。このとき、
記憶手段に、復号演算入力パラメータが記憶されている
タイミングと、復号演算出力パラメータが記憶されてい
るタイミングとが重なり合うことがないため、記憶手段
に、復号演算入力パラメータと復号演算出力パラメータ
とを選択的に記憶させることができる。

【００４８】また、本発明のリードソロモン復号装置
は、好ましくは、前記復号演算手段は、復号演算入力パ
ラメータと、前記訂正操作手段に出力する復号演算出力
パラメータとを選択的に記憶する記憶部を備える。

【００４９】また、本発明のリードソロモン復号装置
は、好ましくは、入力されたデータ系列を切り換えて、
Ｃ１符号のデータ語を第１の記憶部に記憶し、Ｃ２符号
のデータ語を第２の記憶部に記憶する入出力手段をさら
に有する。

【００５０】また、本発明のリードソロモン復号装置
は、好ましくは、前記入出力手段がＣ１符号のデータ語
に関する入出力を実行中に、前記復号演算入力パラメー
タ演算手段はＣ１符号のデータ語に関する復号演算入力
パラメータを生成し、前記復号演算手段は、Ｃ２符号の
データ語に関する復号演算を行い、前記入出力手段がＣ
２符号のデータ語に関する入出力を実行中に、前記復号
演算入力パラメータ演算手段はＣ２符号のデータ語に関
する復号演算入力パラメータを生成し、前記復号演算手
段は、Ｃ１符号のデータ語に関する復号演算を行う。

【００５１】また、本発明のリードソロモン復号装置
は、好ましくは、前記データ系列のシンボル位置を逐次
的に前記訂正操作手段に出力するガロア体カウンタをさ
らに有する。

【００５２】また、本発明のリードソロモン復号装置
は、好ましくは、前記復号演算手段は、ガロア体ＧＦ
（２ⁱ）の第１の元α^w（Ａ_w,i-1,Ａ_w,i-2,Ａ_w,i-3,
…, Ａ_w,3,Ａ_w,2,Ａ_w,1,Ａ_w,0）^Tと第２の元α^v（Ａ
_v,i-1,Ａ_v,i-2,Ａ_v,i-3,…, Ａ_v,3,Ａ_v,2,Ａ_v,1,
Ａ_v,0）^Tとの乗算を行なう乗算器であって、前記第１
の元と前記ガロア体の原始元αのα^o，α¹，α²，α
³，…，α^i-3，α^i-2，α^i-1とのそれぞれの乗算を
並列に行なうｉ個の乗算部と、前記ｉ個の乗算部の乗算
結果と前記Ａ_v,0,Ａ_v,1,Ａ_v,2,Ａ_v,3,…, Ａ_v,i-3,Ａ
_v,i-2,Ａ_v,i-1とのそれぞれの論理積演算を並列に行な
うｉ個の論理積演算部と、前記ｉ個の論理積演算部の演
算結果を加算する加算部とを備える乗算器を有する。

【００５３】さらに、本発明のリードソロモン復号装置
は、好ましくは、前記復号演算手段は、ガロア体ＧＦ
（２ⁱ）の第１の元α^w（Ａ_w,i-1,Ａ_w,i-2,Ａ_w,i-3,
…, Ａ_w, ₃,Ａ_w,2,Ａ_w,1,Ａ_w,0）^Tと第２の元α^v（Ａ
_v,i-1,Ａ_v,i-2,Ａ_v,i-3,…, Ａ_v, ₃,Ａ_v,2,Ａ_v,1,
Ａ_v,0）^Tとの乗算を行なう乗算器であって、前記第１
の元と前記Ａ_v,0,Ａ_v,1,Ａ_v,2,Ａ_v,3,…, Ａ_v,i-3,Ａ
_v,i-2,Ａ_v,i-1とのそれぞれの論理積演算を並列に行な
うｉ個の論理積演算部と、前記論理積演算部のそれぞれ
の演算結果と前記ガロア体の原始元αのα⁰，α¹，α
²，α³，…, α^i-3，α^i- ²，α^i-1とのそれぞれの
乗算を並列に行なうｉ個の乗算部と、前記ｉ個の乗算部
の乗算結果を加算する加算部とを備える乗算器を有す
る。

【００５４】

【発明の実施の形態】以下、本発明の実施形態に係わる
リードソロモン復号装置について説明する。高速処理を
実現するひとつの直接的な手法は、１ステップでガロア
体の乗・除算を実現することである。これはＲＯＭで実
現できるが、かなり大きなもの（それぞれ容量６４Ｋバ
イト）になることを先に述べた。ところが、乗算につい
てはその規則性を利用して、高速な乗算回路が３００ゲ
ート程度で実現できる。一例として、ガロア体ＧＦ（２
ⁱ）でｉ＝８の場合を示す。まず、ガロア体ＧＦ
（２⁸）の原始元をαとして、その任意の元α^vは下記
式（１２），（１３）のように表現できる。

【００５５】

【数１２】

【００５６】

【数１３】

【００５７】ここで、Ａ_v,i＝０あるいは１であり、v
は任意の整数である。また、（α^v）は元α^vの列ベク
トル表現を示し、（…）^Tは転置行列を表す。ここで前
記ガロア体の任意の元α^vとα^w：（Ａ_{w ,7} Ａ
_{w ,6...}Ａ_{w ,1} Ａ _{w ,0}）^Tとの乗算を考える。前記式
（１３）から下記式（１４）が成り立つ。

【００５８】

【数１４】

【００５９】この式（１４）を列ベクトルで表現して、
下記式（１５）を得る。

【００６０】

【数１５】

【００６１】ここで［×αⁱ］はαⁱを乗じることに相
当する行列で８×８行列である。つまり、下記式（１
６）が成り立つ。

【００６２】

【数１６】

【００６３】具体的には、ＣＩＲＣ符号のガロア体の下
記式（１７）に示す体生成多項式から、下記式（１
８），（１９）が成り立つ。

【００６４】

【数１７】

【００６５】

【数１８】

【００６６】

【数１９】

【００６７】前記式（１５）から、ガロア体の乗算回路
は、図１に示すように、２つの入力（α^w，α^v）のう
ち、片方の元に乗算器１１１〜１１８によってα⁰〜α
⁷を乗じたものを、もう片方の各ビットを一方の入力と
するＡＮＤゲート１２１〜１２８によってゲートして、
８個の８バイトの出力を得て、それらの加算（ビットご
との排他的論理和）をＧＦ加算器１２９によって演算す
る構成で実現できる。前記式（１８）、（１９）より
［×α⁰］〜［×α⁷］のそれぞれに対応した乗算回路
は、それぞれ３〜２１個の排他的論理和ゲートを施すと
ガロア体の乗算回路全体を３００ゲートくらいで実現で
きる。この乗算回路単体の遅延量は、例えば１０ｎｓ以
下であり、１６ＭＨ_Zの周期で１ステップでの処理が十
分可能である。

【００６８】なお、前記式（１５）は、下記式（２０）
のように変形できる。

【００６９】

【数２０】

【００７０】これに対応して、ガロア体の乗算回路は、
図２のようにＡＮＤゲートを入力側に配置することも可
能である。すなわち、２つの入力（α^w，α^v）のＡＮ
ＤをＡＮＤゲート１３１〜１３８によって求め、その結
果に、乗算器１４１〜１４８によってα⁰〜α⁷を乗じ
たものを、ＧＦ加算器１２９によって加算する構成で実
現できる。

【００７１】ガロア体の除算については、まず、割る方
の元の逆元を求めてから、割られる方の元との乗算を、
前記乗算回路で実行する。つまり、２ステップを要する
ことになる。前記逆元を求めるには、８ビットの入力に
対し、８ビットの出力を得ればよいので、容量２５６バ
イトのＲＯＭで実現できる。これは、例えば５００ゲー
ト相当であり、回路規模上もさほどインパクトがない。

【００７２】以上より８００ゲートの回路でガロア体の
乗算が１ステップで、除算が２ステップでそれぞれ実行
可能となる。これにより、前記式（３）、（４）、
（６）、（７）、（９）、及び（１０）の１７回の乗算
は１７ステップで、３回の除算は６ステップで実現で
き、２３回（２３ステップ）の加算を含めて合計４６ス
テップで実現できる。つまり、従来の半分以下のステッ
プ数で実現できる。

【００７３】本実施形態のリードソロモン復号装置で
は、図１示す乗算器１１０あるいは図２に示す乗算器１
３０を、復号演算処理部のＧＬＵに用いている。また、
本実施形態のリードソロモン復号装置では、バイナリカ
ウンタの代わりに、ガロア体の元を逐次的に出力するガ
ロア体カウンタを用いることで、復号演算処理部のＧＬ
Ｕの構成を簡単化すると共に、バスＩ／Ｆブロックおよ
び復号演算処理部のレジスタの規模を縮小する。

【００７４】以下、本実施形態に係わるリードソロモン
復号装置の構成について詳細に説明する。図３は、本実
施形態に係わるリードソロモン復号装置３０１の構成図
である。図３に示すように、リードソロモン復号装置３
０１は、メモリブロック３０２、バスＩ／Ｆブロック３
０３および復号演算処理部３０４を備えている。メモリ
ブロック３０２は、スクラッチパッドメモリ３０５，３
０６およびスイッチ３０７，３０８を備えている。スイ
ッチ３０７は、入力データを選択的にスクラッチパッド
メモリ３０５，３０６に出力する。スイッチ３０８は、
スクラッチパッドメモリ３０５の記憶内容を選択的に訂
正操作実行器３１２に出力する。

【００７５】バスＩ／Ｆブロック３０３は、入力パラメ
ータ演算器３０９、スイッチ３１０、ＧＦカウンタ３１
１、訂正操作実行器３１２およびレジスタ３１３を備え
ている。ここで、ＧＦカウンタ３１１は、図３に示すバ
イナリカウンタ１１の代わりに設けられ、ガロア体の元
を逐次的に出力するガロア体カウンタである。例えば、
リードソロモン復号装置３０１に対する入出力が、ＲＳ
符号のＭＳＢ(Most Significant Bit)からＬＳＢ(Least
Significant Bit) の方向であるとき、ＧＦカウンタ３
１１は、図４に示すように、α^-1の係数乗算器４００と
レジスタ４０１で構成できる。この場合には、初期値と
して例えばα³¹を与える。また、リードソロモン復号装
置３０１に対する入出力が、ＲＳ符号のＬＳＢからＭＳ
Ｂの方向であるとき、ＧＦカウンタ３１１は、図５に示
すように、α¹の係数乗算器４０２とレジスタ４０３で
構成できる。

【００７６】復号演算処理部３０４は、レジスタ３１
４、スイッチ３１５および復号演算器３１７を備えてい
る。

【００７７】図６は、リードソロモン復号装置３０１の
動作時におけるデータおよび構成要素の時系列的な状態
を示し、（Ａ）は入力データ、（Ｂ）は出力データ、
（Ｃ）はレジスタＢ３１３の記憶状態、（Ｄ）はレジス
タＧ３１４の記憶状態、（Ｅ）はは復号演算器３１７の
処理状態をそれぞれ示している。

【００７８】図６に示すように、メモリブロック３０２
のスクラッチパッドメモリ３０５においてＣ１符号に関
する入力データの入出力を行っているときに、そのシン
ドローム（Ｓ）と消失位置（Ｘ）が計算される。このと
き、図３および図７に示すスイッチ３１０の選択は点線
の矢印に示す位置なっている。また、このとき、復号演
算処理部３０４は、Ｇ２復号を実行していて、図３に示
すスイッチ３１５の選択は点線の矢印に示す位置になっ
ている。また、レジスタ３１４は、ワーキングレジスタ
として動作している。

【００７９】Ｃ２復号が終了すると、Ｃ２符号の訂正操
作のための復号演算出力パラメータである誤り値（Ｅ）
と誤り位置（Ｘ’）がレジスタ３１４に入力される。前
述したＣ１の復号演算入力パラメータの入力が終了し、
かつ、Ｃ２復号が終了すると、図３のスイッチ３１０お
よびスイッチ３１５は、実線の矢印の位置に切り換わ
り、それぞれのデータを交換する。具体的には、Ｃ１の
復号演算入力パラメータがレジスタ３１３から復号演算
器３１７に出力され、レジスタ３１４からレジスタ３１
３に、Ｃ２符号の誤り値（Ｅ）と誤り位置（Ｘ’）が入
力され、Ｃ２符号の訂正が、訂正操作実行器３１２によ
って行われる。このように、バスＩ／Ｆブロック３０３
では、入力パラメータ演算器３０９および訂正操作実行
器３１２における処理が同時に行われないことを利用し
て、復号演算入力パラメータ用および復号演算出力パラ
メータ用でレジスタ３１３を共用し、回路規模の縮小化
を図っている。

【００８０】ここで、復号演算入力パラメータとは、具
体的には、シンドローム（Ｓ）および消失位置（Ｘ）で
ある。図７は、入力パラメータ演算器３０９、スイッチ
３１０およびレジスタ３１３の構成図である。図７に示
すように、入力パラメータ演算器３０９は、乗算器３２
４〜３２７、加算器３２０〜３２３、消去フラグ検出器
３２８および分配器３２９を備えている。分配器３２９
には、図３に示すＧＦカウンタ３１１からＧＦカウント
値が入力される。

【００８１】乗算器３２４〜３２７は、乗算係数が固定
値のガロア体の乗算器であり、それぞれ×α⁰、×
α¹、×α²、×α³の乗算を行う。消去フラグ検出器
３２８は、入力データに含まれる消去フラグが「１」で
あるか否かを検出する。分配器３２９は、入力データに
含まれる各ＲＳシンボル位置と対応して動作するＧＦカ
ウンタ３１１の出力をレジスタＢ３１３のレジスタ３３
４〜３３７のいずれかに分配して出力し、記憶させる。

【００８２】また、スイッチ３１０は、スイッチ３７０
〜３７７を備えている。スイッチ３７０〜３７３は、復
号演算器３１７からの誤り値（Ｅ）および誤り位置
（Ｘ’）と、加算器３２０〜３２３からの出力とを選択
的にレジスタ３３０〜３３３に出力する。スイッチ３７
４〜３７７は、復号演算器３１７からのＥ，Ｘ’と、分
配器３２９からの出力とを選択的にレジスタ３３４〜３
３７に出力する。

【００８３】レジスタ３１３は、レジスタ３３０〜３３
３およびレジスタ３３４〜３３７を備えている。

【００８４】消失位置（Ｘ）は、ガロア体の表現なの
で、復号演算処理部３０４はｉからα ⁱに変換する変換
器を設ける必要がない。

【００８５】４重消失エラー訂正を実行する場合の前記
式（３），（４），（６），（７）および（１０）に対
応する復号演算は、復号演算処理部３０４において実行
され、レジスタ３１３からの復号演算入力パラメータＳ
＝｛ｓ₀，ｓ₁，ｓ₂，ｓ₃｝と、Ｘ＝｛ｘ₁，ｘ₂，
ｘ₃，ｘ₄｝とを用いて、復号演算出力パラメータＥ＝
｛ｅ₁，ｅ₂，ｅ₃，ｅ₄｝およびＸ’＝Ｘ＝｛ｘ₁，
ｘ₂，ｘ₃，ｘ₄｝を得る。消失エラー訂正を行わない
場合には、前述した２重エラー訂正においては、復号演
算入力パラメータＳ＝｛ｓ₀，ｓ₁，ｓ₂，ｓ₃｝を用
いて、復号演算出力パラメータＥ＝｛ｅ₁，ｅ₂｝およ
びＸ’＝｛ｘ’₁，ｘ’₂｝を得る。

【００８６】ここで、誤り位置ＸあるいはＸ’は、その
まま訂正操作に利用できる。従って、復号演算処理部３
０４は、αⁱからｉに変換する変換器を備える必要がな
い。

【００８７】図８は、訂正操作実行器３１２の構成図で
ある。図８に示すように、訂正操作実行器３１２は、比
較器３４０、加算器３４５およびゲートロジック３４６
を備えている。図３に示すＧＦカウンタ３１１は、スイ
ッチ３０７，３０８によるスクラッチパッドメモリ３０
５，３０６からの出力の切り換わりに対応して動作し、
ＧＦカウンタ３１１のＧＦカウンタ値が誤り位置
（Ｘ’）の構成要素のいずれか（ｘ’ _n）と一致したと
きに、ゲートロジック３４６から対応する誤り値ｅ_nが
加算器３４５に出力される。そして、加算器３４５にお
いて、誤り値ｅ_nと、バスＩ／Ｆブロック３０３からの
入力データとについて、ガロア体の加算が行われ、加算
結果が出力データとなる（訂正が行われる）。

【００８８】復号演算処理部３０４の構成は、図１４に
示す復号演算処理部４の構成と同じである。但し、復号
演算処理部３０４のＧＬＵの構成は、ＧＬＵ５４とは異
なる。図９は、復号演算処理部３０４のＧＬＵ４５４の
構成図である。図９に示すように、ＧＬＵ４５４は、オ
ペレイションロジック４６０，４６１、ＧＦインバージ
ョンＲＯＭ４６２、ＧＦ乗算加算ロジック４６３および
オペレイションセレクタ４６４を備えている。ここで、
ＧＦ乗算加算ロジック４６３には、図１に示す乗算器１
１０あるいは図２に示す乗算器１３０が用いられてい
る。そのため、復号演算処理のステップ数を大幅に減ら
すことができ、復号演算処理を短時間で行なうことがで
きる。また、図１５に示すようなコンバータ６２，６３
を設ける必要がなくなり、回路規模の縮小化が図れる。

【００８９】以上、ｔ＝２のＣＩＲＣ符号を例示して説
明したが、ｔの値が大きくて、ユークリッド復号法やバ
ーレカンプ・マッシイ法などを用いる場合にも、本発明
を適用できる。

【００９０】

【発明の効果】以上説明したように、本発明のリードソ
ロモン復号装置によれば、装置規模の縮小化を図ること
ができる。また、本発明のリードソロモン復号装置によ
れば、復号演算処理を短時間で行うことができる。

【図面の簡単な説明】

【図１】図１は、本発明の実施形態に係わるガロア体の
乗算回路の構成図である。

【図２】図２は、本発明の実施形態に係わるガロア体の
その他の乗算回路の構成図である。

【図３】図３は、本発明の実施形態に係わるリードソロ
モン復号装置の構成図である。

【図４】図４は、図３に示すＧＦカウンタの一例の構成
図である。

【図５】図５は、図３に示すＧＦカウンタのその他の例
の構成図である。

【図６】図６は、図３に示すリードソロモン復号装置の
動作時におけるデータおよび構成要素の時系列的な状態
を示す図である。

【図７】図７は、図３に示す入力パラメータ演算器、ス
イッチおよびレジスタの構成図である。

【図８】図８は、図３に示す訂正操作実行器の構成図で
ある。

【図９】図９は、図３に示す復号演算処理部のＧＬＵの
構成図である。

【図１０】図１０は、従来のリードソロモン復号装置の
構成図である。

【図１１】図１１は、図１０に示すリードソロモン復号
装置の動作時におけるデータおよび構成要素の時系列的
な状態を示し、（Ａ）は入力データ、（Ｂ）は出力デー
タ、（Ｃ）はレジスタＢ_OUTの記憶状態、（Ｄ）はレジ
スタＢ_INの記憶状態、（Ｅ）はレジスタＧ_OUTの記憶状
態、（Ｆ）はレジスタＧ_INの記憶状態、（Ｇ）は復号演
算器の処理状態をそれぞれ示している。

【図１２】図１２は、図１０に示す入力パラメータ演算
器およびレジスタの構成図である。

【図１３】図１３は、図１０に示す訂正操作実行器およ
びレジスタの構成図である。

【図１４】図１４は、図１０に示す復号演算処理部の構
成図である。

【図１５】図１５は、図１４に示すＧＬＵの構成図であ
る。

【符号の説明】

１１０，１３０…乗算器、３０１…リードソロモン復号
装置、３０２…メモリブロック、３０３…バスＩ／Ｆブ
ロック、３０４…復号演算処理部、３０９…入力パラメ
ータ演算器、３１１…ＧＦカウンタ、３１２…訂正操作
実行器、３１４…レジスタ、３１７…復号演算器

Claims

【特許請求の範囲】

【請求項１】データ系列からシンドロームおよび消失位
置を含む復号演算入力パラメータを生成する復号演算入
力パラメータ演算手段と、所定の復号演算操作を示す命令コードに基づいて、復号
演算入力パラメータを用いた復号演算を行い、誤り値デ
ータおよび誤り位置データを含む復号演算出力パラメー
タを生成する復号演算手段と、前記復号演算出力パラメータを用いて訂正操作を行う訂
正操作手段と、前記復号演算手段に出力する復号演算入力パラメータ
と、前記訂正操作手段に出力する復号演算出力パラメー
タとを選択的に記憶する記憶手段とを有するリードソロ
モン復号装置。
【請求項２】前記復号演算手段は、復号演算入力パラメ
ータと、前記訂正操作手段に出力する復号演算出力パラ
メータとを選択的に記憶する記憶部を備える請求項１に
記載のリードソロモン復号装置。
【請求項３】入力されたデータ系列を切り換えて、Ｃ１
符号のデータ語を第１の記憶部に記憶し、Ｃ２符号のデ
ータ語を第２の記憶部に記憶する入出力手段をさらに有
する請求項１または請求項２に記載のリードソロモン復
号装置。
【請求項４】前記入出力手段がＣ１符号のデータ語に関
する入出力を実行中に、前記復号演算入力パラメータ演
算手段はＣ１符号のデータ語に関する復号演算入力パラ
メータを生成し、前記復号演算手段は、Ｃ２符号のデー
タ語に関する復号演算を行い、前記入出力手段がＣ２符号のデータ語に関する入出力を
実行中に、前記復号演算入力パラメータ演算手段はＣ２
符号のデータ語に関する復号演算入力パラメータを生成
し、前記復号演算手段は、Ｃ１符号のデータ語に関する
復号演算を行う請求項３に記載のリードソロモン復号装
置。
【請求項５】前記データ系列のシンボル位置を逐次的に
前記訂正操作手段に出力するガロア体カウンタをさらに
有する請求項１〜４のいずれかに記載のリードソロモン
復号装置。
【請求項６】前記復号演算手段は、ガロア体ＧＦ（２ⁱ）の第１の元α^w（Ａ_w,i-1,Ａ
_w,i-2,Ａ_w,i-3,…, Ａ_w,3,Ａ_w,2,Ａ_w,1,Ａ_w,0）^Tと第
２の元α^v（Ａ_v,i-1,Ａ_v,i-2,Ａ_v,i-3,…, Ａ_v,3,Ａ
_v,2,Ａ_v,1,Ａ_v,0）^Tとの乗算を行なう乗算器であっ
て、前記第１の元と前記ガロア体の原始元αのα^o，α
¹，α²，α³，…，α^i-3，α^i-2，α^i-1とのそれ
ぞれの乗算を並列に行なうｉ個の乗算部と、前記ｉ個の
乗算部の乗算結果と前記Ａ_v,0,Ａ_v,1,Ａ_v,2,Ａ_v,3,…,
Ａ_v,i-3,Ａ_v,i-2,Ａ_v,i-1とのそれぞれの論理積演算を
並列に行なうｉ個の論理積演算部と、前記ｉ個の論理積
演算部の演算結果を加算する加算部とを備える乗算器を
有する請求項１〜５のいずれかに記載のリードソロモン
復号装置。
【請求項７】前記復号演算手段は、ガロア体ＧＦ（２ⁱ）の第１の元α^w（Ａ_w,i-1,Ａ
_w,i-2,Ａ_w,i-3,…, Ａ_w,3,Ａ_w,2,Ａ_w,1,Ａ_w,0）^Tと第
２の元α^v（Ａ_v,i-1,Ａ_v,i-2,Ａ_v,i-3,…, Ａ_v,3,Ａ
_v,2,Ａ_v,1,Ａ_v,0）^Tとの乗算を行なう乗算器であっ
て、前記第１の元と前記Ａ_v,0,Ａ_v,1,Ａ_v,2,Ａ_v,3,…,
Ａ_v,i-3,Ａ_v,i-2,Ａ_v,i-1とのそれぞれの論理積演算を
並列に行なうｉ個の論理積演算部と、前記論理積演算部
のそれぞれの演算結果と前記ガロア体の原始元αの
α⁰，α¹，α²，α³，…，α^i-3，α^i-2，α^i-1
とのそれぞれの乗算を並列に行なうｉ個の乗算部と、前
記ｉ個の乗算部の乗算結果を加算する加算部とを備える
乗算器を有する請求項１〜５のいずれかに記載のリード
ソロモン復号装置。