(57)【特許請求の範囲】
【請求項１】
データ系列からシンドローム及び消失位置を含む復号演算入力パラメータを生成する復号演算パラメータ演算手段と、
所定の復号演算操作を示す命令コードに基づいて、復号演算入力パラメータを用いた復号演算を行ない、誤り値データ及び誤り位置データを含む復号演算出力パラメータを生成する復号演算手段と、
前記復号演算出力パラメータを用いて訂正操作を行なう訂正操作手段と、
前記復号演算手段に出力する復号演算入力パラメータと前記訂正操作手段に出力する復号演算出力パラメータとを選択的に記憶する記憶手段と、
入力されたデータ系列を切り替えて、C1符合のデータ語を第1の記憶部に記憶し、C2符合のデータ語を第2の記憶部に記憶する入出力手段と、
を有し、
前記入出力手段がC1符合のデータ語に関する入出力を実行中に、前記復号演算入力パラメータ演算手段がC1符合のデータ語に関する復号演算入力パラメータを生成し、前記復号演算手段がC2符合のデータ語に関する復号演算を行ない、
前記入出力手段がC2符合のデータ語に関する入出力を実行中に、前記符号演算入力パラメータ演算手段がC2符合のデータ語に関する復号演算入力パラメータを生成し、前記復号演算手段がC1符合のデータ語に関する復号演算を行なう、
リードソロモン復号装置。
【請求項２】
前記復号演算手段が、復号演算入力パラメータと前記訂正操作手段に出力する復号演算出力パラメータとを選択的に記憶する記憶部を備える、
請求項1に記載のリードソロモン復号装置。
【請求項３】
前記データ系列のシンボル位置を逐次的に前記訂正操作手段に出力するガロア体カウンタを更に有する、
請求項1又は2に記載のリードソロモン復号装置。
【請求項４】
前記復号演算手段が、
ガロア体GF(2i)の第1の元αW(AW, i-1, AW, i-2, AW, i-3, …, AW, 3, AW, 2, AW, 1, AW, 0)Tと第2の元αV(AV, i-1, AV, i-2, AV, i-3, …, AV, 3, AV, 2, AV, 1, AV, 0)Tとの乗算を行なう乗算器であって、
前記第1の元と前記ガロア体の原始元αのα0, α1, α2, α3, …, αi-3, αi-2, αi-1とのそれぞれの演算を並列に行なうi個の乗算部と、
前記i個の乗算部の乗算結果と前記AV, 0, AV, 1, AV, 2, AV, 3, …, AV, i-3, AV, i-2, AV, i-1とのそれぞれの論理積演算を並列に行なうi個の論理積演算部と、
前記i個の論理積演算部の演算結果を加算する加算部と、
を備える乗算器を有する、
請求項1乃至3の何れかに記載のリードソロモン復号装置。
【請求項５】
前記復号演算手段が、
ガロア体GF(2i)の第1の元αW(AW, i-1, AW, i-2, AW, i-3, …, AW, 3, AW, 2, AW, 1, AW, 0)Tと第2の元αV(AV, i-1, AV, i-2, AV, i-3, …, AV, 3, AV, 2, AV, 1, AV, 0)Tとの乗算を行なう乗算器であって、
前記第1の元と前記AV, 0, AV, 1, AV, 2, AV, 3, …, AV, i-3, AV, i-2, AV, i-1とのそれぞれの論理積演算を並列に行なうi個の論理積演算部と、
前記i個の論理積演算部の乗算結果と前記ガロア体の原始元αのα0, α1, α2, α3, …, αi-3, αi-2, αi-1とのそれぞれの乗算を並列に行なうi個の乗算部と、
前記i個の乗算部の乗算結果を加算する加算部と、
を備える乗算器を有する、
請求項1乃至3の何れかに記載のリードソロモン復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、記録媒体やディジタル伝送の誤り訂正符号化として用いられるリードソロモン符号化された信号を復号するリードソロモン復号装置に関する。
【０００２】
【従来の技術および発明が解決しようとする課題】
リード・ソロモン符号（以下ＲＳ符号）は、その符号化効率の良さとバーストエラーに対する適正から、主に記録媒体やディジタル伝送の外符号に用いられている。
例えばコンパクトディスクで採用されているエラー訂正符号は、ＣＩＲＣ訂正符号（クロスインターリーブ・リード・ソロモン符号）と称され、インターリーブの技法と組み合わせた積符号である。その外符号としてＲＳ（２８、２４）符号が、内符号としてＲＳ（３２、２８）符号が採用されていて、それぞれＣ２符号及びＣ１符号と呼ばれる。いずれの符号とも、ひとつのＲＳ符号化シンボルは１バイトで構成され、ひとつのＲＳ符号化ブロックは４バイトのパリティ検査列を含んでいる。
【０００３】
一般に、ＲＳ符号は２ｔシンボルの検査列でｔシンボルの訂正が可能である。ｔシンボルの訂正にはｔ個の誤り位置とそのそれぞれの誤りに対応したｔ個の誤りの値を知る必要がある。ＲＳ符号はｔ個の誤りの発生に対し、復号側でシンドローム演算をすることで２ｔ個の線形独立な方程式を得る。この方程式を解くことで２ｔ個の未知数である、前記ｔ個の誤り位置とそのそれぞれの誤り位置に対応した前記ｔ個の誤りの値を求めることができる。
【０００４】
一方、ＣＩＲＣ符号のように積符号の構成を取っているものは、内符号に対する内側ＲＳ復号において訂正できなかったＲＳ符号化ブロックや誤訂正の可能性の比較的高いＲＳ符号化ブロックに消失フラグを付加することで、外符号に対応した外側ＲＳ復号において消失エラー訂正が可能になる。消失フラグが付加された内符号の消失シンボルはデ・インターリーブによって複数の外側のＲＳ符号化ブロックに分散される。消失エラー訂正では、前記消失シンボルに誤りが存在すると仮定してシンドローム演算から得られる連立方程式を解く。誤り位置を既知として解くので最大２ｔ個の誤りを値を求めることができる。即ち、２ｔシンボルの検査列を持つＲＳ符号に対しては、消失エラー訂正を実行することで最大２ｔシンボルの誤り訂正が可能である。
【０００５】
ＣＩＲＣ符号を例に挙げて、消失エラー訂正の手法を説明する。
ＣＩＲＣ符号の場合、内符号であるＣ１符号のＲＳ復号（Ｃ１復号）において消失フラグを付加することで、外符号であるＣ２符号のＲＳ復号（Ｃ２復号）で消失エラー訂正が可能である。Ｃ１符号、Ｃ２符号ともにｔ＝２であるから、Ｃ１復号は最大２バイトの訂正が、Ｃ２復号の消失エラー訂正では最大４バイトの訂正がそれぞれ可能である。そのＣ２復号におけるシンドロームｓ0 〜ｓ3 と、誤り値ｅ1 〜ｅ4 が次のようにして求められる。
ＣＩＲＣ符号の符号生成多項式Ｇｅ（ｘ）は、下記式（１）で示される。
【０００６】
【数１】
0003850512.tif 000002
【０００７】
ここでαはガロア体の原始元である。このとき、入力系列からシンドローム演算により得たｓ0 〜ｓ3 は、前記ｘ1 〜ｘ4 およびｅ1 〜ｅ4 との間に下記式（２）で示される関係がある。
【０００８】
【数２】
0003850512.tif 000003
【０００９】
ここで記号‘・’はガロア体上の乗算を示し、記号‘＋’はガロア体上の加算を示す。以下、あるガロア体の元同士の四則演算は、そのガロア体上での演算を示すこととする。
前記式（２）を連立方程式を解いて、未知数である誤り値ｅ1 〜ｅ4 を求めると次のようになる
まず、ｅ4 は、下記式（３）として得られる。
【００１０】
【数３】
0003850512.tif 000004
【００１１】
この得られたｅ4 を前記式（２）に代入して３つの等式から成る連立方程式を再構成する。即ち、ＣＩＲＣ符号で用いられているガロア体は加算と減算が同じであることに注意して下記式（４）のように修正することで、前記式（２）の連立方程式は下記式（５）に変形される。
【００１２】
【数４】
0003850512.tif 000005
【００１３】
【数５】
0003850512.tif 000006
【００１４】
これは、連立方程式の解を、手計算で順に求めるときによく用いられる手法である。次に、式（５）の連立方程式を解いてｅ3 を求めると、下記式（６）のようになる。
【００１５】
【数６】
0003850512.tif 000007
【００１６】
同様にして修正を施すことで、前記式（５）の連立方程式は下記式（７），（８）のように変形される。
【００１７】
【数７】
0003850512.tif 000008
【００１８】
【数８】
0003850512.tif 000009
【００１９】
さらに、式（８）の連立方程式を解いてｅ2 を求めると、下記式（９）となる。
【００２０】
【数９】
0003850512.tif 000010
【００２１】
次に、この求めたｅ2 を前記式（８）に代入して下記式（１０）を得る。
【００２２】
【数１０】
0003850512.tif 000011
【００２３】
このようにして、誤り値ｅ1 〜ｅ4 を順次求めることができる。
上述した手法において、情報として元来もっているものと、実際の復号の際に行われる演算操作とを区別するために、記号‘＝’と‘←’とを使い分けている。つまり、実際の復号演算に対応するのは、式（３）、（４）、（６）、（７）、（９）および（１０）であり、少なくとも、ガロア体上の加算が２３回、乗算が１７回、除算が３回必要である。
一方、消去エラー訂正を行わない場合には、Ｃ２復号で最大２バイトまで訂正（２重エラー訂正）ができる。このときは、シンドロームｓ0 〜ｓ3 から、誤り値ｅ1 ，ｅ2 と誤り位置ｘ’1 ，ｘ’2 を求める。
以上は、４重消去エラー訂正、すなわち、消去位置の数が４の場合の復号演算処理過程である。
【００２４】
以下、従来のリードソロモン復号装置について説明する。
図１０は、従来のリードソロモン復号装置１の構成図である。
図１０に示すように、リードソロモン復号装置１は、メモリブロック２、バスＩ／Ｆブロック３および復号演算処理部４を備えている。
メモリブロック２は、スクラッチパッドメモリ５，６およびスイッチ７，８を備えている。
スイッチ７は、入力データを選択的にスクラッチパッドメモリ５，６に出力する。スイッチ８は、スクラッチパッドメモリ５の記憶内容を選択的に訂正操作実行器１２に出力する。
【００２５】
バスＩ／Ｆブロック３は、入力パラメータ演算器９、レジスタＢOUT １０、バイナリカウンタ１１、訂正操作実行器１２およびレジスタＢIN１３を備えている。
復号演算処理部４は、スイッチ１４、レジスタＧIN１５、レジスタＧOUT １６および復号演算器１７を備えている。
図１１は、リードソロモン復号装置１の動作時におけるデータおよび構成要素の時系列的な状態を示し、（Ａ）は入力データ、（Ｂ）は出力データ、（Ｃ）はレジスタＢOUT １０の記憶状態、（Ｄ）はレジスタＢIN１３の記憶状態、（Ｅ）はレジスタＧOUT １６の記憶状態、（Ｆ）はレジスタＧIN１５の記憶状態、（Ｇ）は復号演算器１７の処理状態をそれぞれ示している。
【００２６】
図１１に示すように、メモリブロック２のスクラッチパッドメモリ５においてＣ１符号に関する入力データの入出力を行っているときには、バスＩ／Ｆブロック３はＣ１符号に関する入力データ対して、入力パラメータ演算器９において復号演算入力パラメータの計算を行い、訂正操作実行器１２において訂正操作を行っている。また、このとき、復号演算処理部４ではＣ２符号に関する入力データについてＣ２復号処理が行われている。
【００２７】
また、スクラッチパッドメモリ６においてＣ２符号に関する入力データの入出力を行っているときには、バスＩ／Ｆブロック３はＣ２符号に関する入力データ対して、入力パラメータ演算器９において復号演算入力パラメータの計算を行い、訂正操作実行器１２において訂正操作を行っている。また、このとき、復号演算処理部４ではＣ１符号に関する入力データについてＣ１復号処理が行われている。
【００２８】
ここで、復号演算入力パラメータとは、具体的には、シンドローム（Ｓ）および消失位置（Ｉ）である。
シンドローム（Ｓ）は、図１０に示す入力パラメータ演算器９およびレジスタＢOUT １０の組み合わせによって演算される。
図１２は、入力パラメータ演算器９およびレジスタＢOUT １０の構成図である。
図１２に示すように、入力パラメータ演算器９は、乗算器２４〜２７、加算器２０〜２３、消去フラグ検出器２８および分配器２９を備えている。
また、レジスタＢOUT １０は、レジスタ３０〜３３およびレジスタ３４〜３７を備えている。
【００２９】
乗算器２４〜２７は、乗算係数が固定値のガロア体の乗算器であり、それぞれ×α0 、×α1 、×α2 、×α3 の乗算を行う。
消去フラグ検出器２８は、入力データに含まれる消去フラグが「１」であるか否かを検出する。
分配器２９は、入力データに含まれる各ＲＳシンボル位置と対応して動作するバイナリカウンタ１１の出力をレジスタＢOUT １０のレジスタ３４〜３７のいずれかに出力して記憶させる。
このレジスタ３４〜３７の記憶結果が消失位置（Ｉ）を示す。
【００３０】
消失位置（Ｉ）は、図１０に示す復号演算器１７において、後述するコンバータにより、ガロア体の表現に、すなわち「ｉ」から「αi 」に変換される。
具体的には、Ｉ＝｛ｉ1 ，ｉ2 ，ｉ3 ，ｉ4 ｝が、Ｘ＝｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝に変換される。
【００３１】
４重消失エラー訂正を実行する場合の前記式（３），（４），（６），（７）および（１０）に対応する復号演算は、復号演算処理部４において実行され、レジスタＢOUT １０からの復号演算入力パラメータＳ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3 ｝と、Ｉ＝｛ｉ1 ，ｉ2 ，ｉ3 ，ｉ4 ｝を変換して得られたＸ＝｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝とを用いて、復号演算出力パラメータＥ＝｛ｅ1 ，ｅ2 ，ｅ3 ，ｅ4 ｝およびＸ’＝Ｘ＝｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝を得る。消失エラー訂正を行わない場合には、前述した２重エラー訂正においては、復号演算入力パラメータＳ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3 ｝を用いて、復号演算出力パラメータＥ＝｛ｅ1 ，ｅ2 ｝およびＸ’＝｛ｘ’1 ，ｘ’2 ｝を得る。
【００３２】
誤り位置ＸあるいはＸ’は、復号演算処理部４において、後述するコンバータで、指数値に、すなわちαi からｉに変換される。具体的には、Ｘ’＝Ｘ＝｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝がＩ＝｛ｉ1 ，ｉ2 ，ｉ3 ，ｉ4 ｝に変換され、Ｘ’＝｛ｘ’1 ，ｘ’2 ｝がＩ’＝｛ｉ’1 ，ｉ’2 ｝に変換される。
【００３３】
図１３は、訂正操作実行器１２およびレジスタＢIN１３の構成図である。
図１３に示すように、訂正操作実行器１２は、比較器４０、加算器４５およびゲートロジック４６を備えている。
また、レジスタＢIN１３は、レジスタ４１〜４４およびレジスタ４７〜５０を備えている。
【００３４】
バスＩ／Ｆブロック３は、レジスタＧOUT １６から入力した誤り値（Ｅ）と誤り位置（Ｉ’）とを用いて、訂正操作を実行する。
バイナリカウンタ１１は、スイッチ７，８によるスクラッチパッドメモリ５，６からの出力の切り換わりに対応して動作し、バイナリカウンタ１１のバイナリカウンタ値が誤り位置（Ｉ’）の構成要素のいずれか（ｉ’n ）と一致したときに、ゲートロジック４６から対応する誤り値ｅn が加算器４５に出力される。そして、加算器４５において、誤り値ｅn と、スイッチ８からのメモリブロックのデータ出力とについて、ガロア体の加算が行われ、加算結果が出力データとなる。
【００３５】
次に、復号演算処理部４について説明する。
図１４は、復号演算処理部４の構成図である。
図１４に示すように、復号演算処理部４は、マイクロコードＲＯＭ５０、シーケンサ５１、デスティネイションコントローラ５２、ワーキングレジスタ５３、ＧＬＵ(Global Logic Unit) ５４、ポート選択器５５を備えている。
【００３６】
ＣＩＲＣ符号のようにｔが４より小さく、連立方程式から解が直接的に求められる場合で、かつ、処理スピードが比較的遅くても良いときには、復号演算処理部４としては、ＲＩＳＣ(Reduced Instruction Set Computer)型のものが用いられる。
復号演算処理部４では、各演算は逐次的に行われ、演算セットは、ＧＬＵ５４として時分割共有化される。、また、一連の演算処理は、マイクロコード化されて、インストラクションコードとしてマイクロコードＲＯＭ５０に格納され、シーケンサ５１からのＲＯＭアドレスによって、処理順序（メモリからの読み出し順序）が制御される。
【００３７】
また、途中の演算結果は、予め用意された複数のワーキングレジスタ５３に一時的に記憶されるが、どのワーキングレジスタ５３に記憶するかは、インストラクションコード内のデスティネイションコントロールコードに記述されている。この手法によれば、処理スピードの制限はあるものの、ＧＬＵ５４の時分割共有化による装置の縮小化ができると共に、演算処理のマイクロコード化により設計の自由度を高めることができる。
例えば、２つのガロア体の元同士の加算は、各ビットの排他的論理和に相当し、復号演算処理部４では１ステップで実現できる。すなわち、ＧＬＵ５４は、ビット毎の排他的論理和の機能を含んでいる。但し、ガロア体における乗算は、加算に比べてはるかに複雑であり、これをＲＯＭを用いて実現しようとすると、２バイトのアドレス入力に対して１バイトの出力を得ることになり、非常に規模が大きくなってしまう。
【００３８】
ＧＬＵ５４の構成について説明する。
図１５は、ＧＬＵ５４の構成図である。
図１５に示すように、ＧＬＵ５４は、オペレイションロジック６０，６１、コンバータ６２，６３およびオペレイションセレクタ６４を備えている。
ＧＬＵ５４では、２つの入力データａ，ｂのガロア体の元のそれぞれを、コンバータ６２において、対応する原始元の指数の値に変換、すなわちαi をｉに変換し、指数同士の加算を実行する。そして、その得られた加算結果を、コンバータ６３において、対応するガロア体の元に変換、すなわち、ｉをαi に変換する。
【００３９】
例えば、αv とαw の乗算を実行して、αV+W を得るには、ＧＬＵ５４において、下記式（１１）に示す４つの演算処理が必要で、少なくとも４ステップを要する。
【００４０】
【数１１】
0003850512.tif 000012
【００４１】
除算も同様で、乗算における加算の代わりに減算を実行する。
従って、上述した手法では、誤り値ｅ1 〜ｅ4 を求めるには、上記式（３），（４），（６），（７），（９）および（１０）における乗算・除算が２０回あるので、これだけでも８０ステップ以上必要となる。これに、２３回の加算を含めると、合計１０３ステップ以上必要となる。そのため、高速処理の要求に応えることができない。
なお、ｔが４より大きい場合には、前記式（２）に示したような連立方程式を解くことは非現実的であるため、ユークリッド復号法などの繰り返しアルゴリズムが採用される。
しかしながら、いずれにしても、ガロア体の乗算や除算に４ステップも必要となると、高速処理の実現は困難である。
【００４２】
一方、ＣＤ−ＲＯＭのデータ再生におけるスピードの要求は、現在、２倍速から１２倍速にまで高まっており、誤り訂正の処理ステップ数の制限が日増しに厳しくなってきている。さらには、光学系の読み取り誤差が、当然大きくなってくるわけで、前記消失エラー訂正による訂正能力の強化が強く望まれている。つまり、より高い機能を、より少ないステップ数で実現する必要がある。
【００４３】
１２倍速対応のＣ１復号およびＣ２復号を実現するには、例えば演算の１ステップを１６ＭＨｚの１クロック内で終了するとすれば、Ｃ１とＣ２の１回ずつの復号を、１９２ステップ以内で実行する必要がある。これには分岐処理等の周辺処理を含めての条件なので、Ｃ２復号のコアの処理はその１／４以内のステップ数で実現する必要がある。
しかしながら、従来の構成では、例えばＣ２復号で消失エラー訂正を行うときに、その訂正コアの処理だけで１０３ステップ以上の演算ステップ数を要し、高速処理の要求に答えることができない。
【００４４】
また、上述したリードソロモン復号装置１では、図１０に示すように、バスＩ／Ｆブロック３にはレジスタＢOUT １０およびレジスタＢIN１３の２個のレジスタが設けられていると共に、復号演算処理部４には、レジスタＧOUT １６およびレジスタＧIN１５の２個のレジスタが設けられている。また、リードソロモン復号装置１では、消失位置や誤り位置を用いた演算を、ガロア体の指数表現で行なっているため、図１５に示すように、復号演算処理部４のＧＬＵ５４には、ガロア体の元を対応する原始元の指数に変換するコンバータ６２と、その逆変換を行なうコンバータ６３とが必要になる。
そのため、リードソロモン復号装置１は、大規模なものになってしまうという問題がある。
【００４５】
本発明は、上述した従来技術に鑑みてなされ、本発明は、回路規模の縮小化を図れるリードソロモン復号装置を提供することを目的とする。
また、本発明は、高速処理が可能なリードソロモン復号装置を提供することを目的とする。
【００４６】
本発明によれば、
データ系列からシンドローム及び消失位置を含む復号演算入力パラメータを生成する復号演算パラメータ演算手段と、
所定の復号演算操作を示す命令コードに基づいて、復号演算入力パラメータを用いた復号演算を行ない、誤り値データ及び誤り位置データを含む復号演算出力パラメータを生成する復号演算手段と、
前記復号演算出力パラメータを用いて訂正操作を行なう訂正操作手段と、
前記復号演算手段に出力する復号演算入力パラメータと前記訂正操作手段に出力する復号演算出力パラメータとを選択的に記憶する記憶手段と、
入力されたデータ系列を切り替えて、C1符合のデータ語を第1の記憶部に記憶し、C2符合のデータ語を第2の記憶部に記憶する入出力手段と、
を有し、
前記入出力手段がC1符合のデータ語に関する入出力を実行中に、前記復号演算入力パラメータ演算手段がC1符合のデータ語に関する復号演算入力パラメータを生成し、前記復号演算手段がC2符合のデータ語に関する復号演算を行ない、
前記入出力手段がC2符合のデータ語に関する入出力を実行中に、前記符号演算入力パラメータ演算手段がC2符合のデータ語に関する復号演算入力パラメータを生成し、前記復号演算手段がC1符合のデータ語に関する復号演算を行なう、
リードソロモン復号装置。
【００４８】
好ましくは、前記復号演算手段が、復号演算入力パラメータと前記訂正操作手段に出力する復号演算出力パラメータとを選択的に記憶する記憶部を備える。
【００５１】
好ましくは、前記データ系列のシンボル位置を逐次的に前記訂正操作手段に出力するガロア体カウンタを更に有する。
【００５２】
好ましくは、前記復号演算手段が、ガロア体GF(2i)の第1の元αW(AW, i-1, AW, i-2, AW, i-3, …, AW, 3, AW, 2, AW, 1, AW, 0)Tと第2の元αV(AV, i-1, AV, i-2, AV, i-3, …, AV, 3, AV, 2, AV, 1, AV, 0)Tとの乗算を行なう乗算器であって、
前記第1の元と前記ガロア体の原始元αのα0, α1, α2, α3, …, αi-3, αi-2, αi-1とのそれぞれの演算を並列に行なうi個の乗算部と、
前記i個の乗算部の乗算結果と前記AV, 0, AV, 1, AV, 2, AV, 3, …, AV, i-3, AV, i-2, AV, i-1とのそれぞれの論理積演算を並列に行なうi個の論理積演算部と、
前記i個の論理積演算部の演算結果を加算する加算部と、
を備える乗算器を有する。
【００５３】
好ましくは、前記復号演算手段が、ガロア体GF(2i)の第1の元αW(AW, i-1, AW, i-2, AW, i-3, …, AW, 3, AW, 2, AW, 1, AW, 0)Tと第2の元αV(AV, i-1, AV, i-2, AV, i-3, …, AV, 3, AV, 2, AV, 1, AV, 0)Tとの乗算を行なう乗算器であって、
前記第1の元と前記AV, 0, AV, 1, AV, 2, AV, 3, …, AV, i-3, AV, i-2, AV, i-1とのそれぞれの論理積演算を並列に行なうi個の論理積演算部と、
前記i個の論理積演算部の乗算結果と前記ガロア体の原始元αのα0, α1, α2, α3, …, αi-3, αi-2, αi-1とのそれぞれの乗算を並列に行なうi個の乗算部と、
前記i個の乗算部の乗算結果を加算する加算部と、
を備える乗算器を有する。
【００５４】
【発明の実施の形態】
以下、本発明の実施形態に係わるリードソロモン復号装置について説明する。高速処理を実現するひとつの直接的な手法は、１ステップでガロア体の乗・除算を実現することである。これはＲＯＭで実現できるが、かなり大きなもの（それぞれ容量６４Ｋバイト）になることを先に述べた。ところが、乗算についてはその規則性を利用して、高速な乗算回路が３００ゲート程度で実現できる。
一例として、ガロア体ＧＦ（２i ）でｉ＝８の場合を示す。
まず、ガロア体ＧＦ（２8 ）の原始元をαとして、その任意の元αv は下記式（１２），（１３）のように表現できる。
【００５５】
【数１２】
0003850512.tif 000013
【００５６】
【数１３】
0003850512.tif 000014
【００５７】
ここで、Ａv,i ＝０あるいは１であり、v は任意の整数である。また、（αv ）は元αv の列ベクトル表現を示し、（…）T は転置行列を表す。
ここで前記ガロア体の任意の元αv とαw ：（Ａw ,7  Ａw ,6... Ａw ,1  Ａw ,0）T との乗算を考える。前記式（１３）から下記式（１４）が成り立つ。
【００５８】
【数１４】
0003850512.tif 000015
【００５９】
この式（１４）を列ベクトルで表現して、下記式（１５）を得る。
【００６０】
【数１５】
0003850512.tif 000016
【００６１】
ここで［×αi ］はαi を乗じることに相当する行列で８×８行列である。つまり、下記式（１６）が成り立つ。
【００６２】
【数１６】
0003850512.tif 000017
【００６３】
具体的には、ＣＩＲＣ符号のガロア体の下記式（１７）に示す体生成多項式から、下記式（１８），（１９）が成り立つ。
【００６４】
【数１７】
0003850512.tif 000018
【００６５】
【数１８】
0003850512.tif 000019
【００６６】
【数１９】
0003850512.tif 000020
【００６７】
前記式（１５）から、ガロア体の乗算回路は、図１に示すように、２つの入力（αw ，αv ）のうち、片方の元に乗算器１１１〜１１８によってα0 〜α7 を乗じたものを、もう片方の各ビットを一方の入力とするＡＮＤゲート１２１〜１２８によってゲートして、８個の８バイトの出力を得て、それらの加算（ビットごとの排他的論理和）をＧＦ加算器１２９によって演算する構成で実現できる。前記式（１８）、（１９）より［×α0 ］〜［×α7 ］のそれぞれに対応した乗算回路は、それぞれ３〜２１個の排他的論理和ゲートを施すとガロア体の乗算回路全体を３００ゲートくらいで実現できる。
この乗算回路単体の遅延量は、例えば１０ｎｓ以下であり、１６ＭＨZ の周期で１ステップでの処理が十分可能である。
【００６８】
なお、前記式（１５）は、下記式（２０）のように変形できる。
【００６９】
【数２０】
0003850512.tif 000021
【００７０】
これに対応して、ガロア体の乗算回路は、図２のようにＡＮＤゲートを入力側に配置することも可能である。すなわち、２つの入力（αw ，αv ）のＡＮＤをＡＮＤゲート１３１〜１３８によって求め、その結果に、乗算器１４１〜１４８によってα0 〜α7 を乗じたものを、ＧＦ加算器１２９によって加算する構成で実現できる。
【００７１】
ガロア体の除算については、まず、割る方の元の逆元を求めてから、割られる方の元との乗算を、前記乗算回路で実行する。つまり、２ステップを要することになる。前記逆元を求めるには、８ビットの入力に対し、８ビットの出力を得ればよいので、容量２５６バイトのＲＯＭで実現できる。これは、例えば５００ゲート相当であり、回路規模上もさほどインパクトがない。
【００７２】
以上より８００ゲートの回路でガロア体の乗算が１ステップで、除算が２ステップでそれぞれ実行可能となる。これにより、前記式（３）、（４）、（６）、（７）、（９）、及び（１０）の１７回の乗算は１７ステップで、３回の除算は６ステップで実現でき、２３回（２３ステップ）の加算を含めて合計４６ステップで実現できる。つまり、従来の半分以下のステップ数で実現できる。
【００７３】
本実施形態のリードソロモン復号装置では、図１示す乗算器１１０あるいは図２に示す乗算器１３０を、復号演算処理部のＧＬＵに用いている。
また、本実施形態のリードソロモン復号装置では、バイナリカウンタの代わりに、ガロア体の元を逐次的に出力するガロア体カウンタを用いることで、復号演算処理部のＧＬＵの構成を簡単化すると共に、バスＩ／Ｆブロックおよび復号演算処理部のレジスタの規模を縮小する。
【００７４】
以下、本実施形態に係わるリードソロモン復号装置の構成について詳細に説明する。
図３は、本実施形態に係わるリードソロモン復号装置３０１の構成図である。
図３に示すように、リードソロモン復号装置３０１は、メモリブロック３０２、バスＩ／Ｆブロック３０３および復号演算処理部３０４を備えている。
メモリブロック３０２は、スクラッチパッドメモリ３０５，３０６およびスイッチ３０７，３０８を備えている。
スイッチ３０７は、入力データを選択的にスクラッチパッドメモリ３０５，３０６に出力する。スイッチ３０８は、スクラッチパッドメモリ３０５の記憶内容を選択的に訂正操作実行器３１２に出力する。
【００７５】
バスＩ／Ｆブロック３０３は、入力パラメータ演算器３０９、スイッチ３１０、ＧＦカウンタ３１１、訂正操作実行器３１２およびレジスタ３１３を備えている。
ここで、ＧＦカウンタ３１１は、図３に示すバイナリカウンタ１１の代わりに設けられ、ガロア体の元を逐次的に出力するガロア体カウンタである。例えば、リードソロモン復号装置３０１に対する入出力が、ＲＳ符号のＭＳＢ(Most Significant Bit)からＬＳＢ(Least Significant Bit) の方向であるとき、ＧＦカウンタ３１１は、図４に示すように、α-1の係数乗算器４００とレジスタ４０１で構成できる。この場合には、初期値として例えばα31を与える。
また、リードソロモン復号装置３０１に対する入出力が、ＲＳ符号のＬＳＢからＭＳＢの方向であるとき、ＧＦカウンタ３１１は、図５に示すように、α1 の係数乗算器４０２とレジスタ４０３で構成できる。
【００７６】
復号演算処理部３０４は、レジスタ３１４、スイッチ３１５および復号演算器３１７を備えている。
【００７７】
図６は、リードソロモン復号装置３０１の動作時におけるデータおよび構成要素の時系列的な状態を示し、（Ａ）は入力データ、（Ｂ）は出力データ、（Ｃ）はレジスタＢ３１３の記憶状態、（Ｄ）はレジスタＧ３１４の記憶状態、（Ｅ）はは復号演算器３１７の処理状態をそれぞれ示している。
【００７８】
図６に示すように、メモリブロック３０２のスクラッチパッドメモリ３０５においてＣ１符号に関する入力データの入出力を行っているときに、そのシンドローム（Ｓ）と消失位置（Ｘ）が計算される。このとき、図３および図７に示すスイッチ３１０の選択は点線の矢印に示す位置なっている。また、このとき、復号演算処理部３０４は、Ｇ２復号を実行していて、図３に示すスイッチ３１５の選択は点線の矢印に示す位置になっている。また、レジスタ３１４は、ワーキングレジスタとして動作している。
【００７９】
Ｃ２復号が終了すると、Ｃ２符号の訂正操作のための復号演算出力パラメータである誤り値（Ｅ）と誤り位置（Ｘ’）がレジスタ３１４に入力される。前述したＣ１の復号演算入力パラメータの入力が終了し、かつ、Ｃ２復号が終了すると、図３のスイッチ３１０およびスイッチ３１５は、実線の矢印の位置に切り換わり、それぞれのデータを交換する。具体的には、Ｃ１の復号演算入力パラメータがレジスタ３１３から復号演算器３１７に出力され、レジスタ３１４からレジスタ３１３に、Ｃ２符号の誤り値（Ｅ）と誤り位置（Ｘ’）が入力され、Ｃ２符号の訂正が、訂正操作実行器３１２によって行われる。
このように、バスＩ／Ｆブロック３０３では、入力パラメータ演算器３０９および訂正操作実行器３１２における処理が同時に行われないことを利用して、復号演算入力パラメータ用および復号演算出力パラメータ用でレジスタ３１３を共用し、回路規模の縮小化を図っている。
【００８０】
ここで、復号演算入力パラメータとは、具体的には、シンドローム（Ｓ）および消失位置（Ｘ）である。
図７は、入力パラメータ演算器３０９、スイッチ３１０およびレジスタ３１３の構成図である。
図７に示すように、入力パラメータ演算器３０９は、乗算器３２４〜３２７、加算器３２０〜３２３、消去フラグ検出器３２８および分配器３２９を備えている。分配器３２９には、図３に示すＧＦカウンタ３１１からＧＦカウント値が入力される。
【００８１】
乗算器３２４〜３２７は、乗算係数が固定値のガロア体の乗算器であり、それぞれ×α0 、×α1 、×α2 、×α3 の乗算を行う。
消去フラグ検出器３２８は、入力データに含まれる消去フラグが「１」であるか否かを検出する。
分配器３２９は、入力データに含まれる各ＲＳシンボル位置と対応して動作するＧＦカウンタ３１１の出力をレジスタＢ３１３のレジスタ３３４〜３３７のいずれかに分配して出力し、記憶させる。
【００８２】
また、スイッチ３１０は、スイッチ３７０〜３７７を備えている。スイッチ３７０〜３７３は、復号演算器３１７からの誤り値（Ｅ）および誤り位置（Ｘ’）と、加算器３２０〜３２３からの出力とを選択的にレジスタ３３０〜３３３に出力する。スイッチ３７４〜３７７は、復号演算器３１７からのＥ，Ｘ’と、分配器３２９からの出力とを選択的にレジスタ３３４〜３３７に出力する。
【００８３】
レジスタ３１３は、レジスタ３３０〜３３３およびレジスタ３３４〜３３７を備えている。
【００８４】
消失位置（Ｘ）は、ガロア体の表現なので、復号演算処理部３０４はｉからαi に変換する変換器を設ける必要がない。
【００８５】
４重消失エラー訂正を実行する場合の前記式（３），（４），（６），（７）および（１０）に対応する復号演算は、復号演算処理部３０４において実行され、レジスタ３１３からの復号演算入力パラメータＳ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3 ｝と、Ｘ＝｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝とを用いて、復号演算出力パラメータＥ＝｛ｅ1 ，ｅ2 ，ｅ3 ，ｅ4 ｝およびＸ’＝Ｘ＝｛ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ｝を得る。消失エラー訂正を行わない場合には、前述した２重エラー訂正においては、復号演算入力パラメータＳ＝｛ｓ0 ，ｓ1 ，ｓ2 ，ｓ3 ｝を用いて、復号演算出力パラメータＥ＝｛ｅ1 ，ｅ2 ｝およびＸ’＝｛ｘ’1 ，ｘ’2 ｝を得る。
【００８６】
ここで、誤り位置ＸあるいはＸ’は、そのまま訂正操作に利用できる。従って、復号演算処理部３０４は、αi からｉに変換する変換器を備える必要がない。
【００８７】
図８は、訂正操作実行器３１２の構成図である。
図８に示すように、訂正操作実行器３１２は、比較器３４０、加算器３４５およびゲートロジック３４６を備えている。
図３に示すＧＦカウンタ３１１は、スイッチ３０７，３０８によるスクラッチパッドメモリ３０５，３０６からの出力の切り換わりに対応して動作し、ＧＦカウンタ３１１のＧＦカウンタ値が誤り位置（Ｘ’）の構成要素のいずれか（ｘ’n ）と一致したときに、ゲートロジック３４６から対応する誤り値ｅn が加算器３４５に出力される。そして、加算器３４５において、誤り値ｅn と、バスＩ／Ｆブロック３０３からの入力データとについて、ガロア体の加算が行われ、加算結果が出力データとなる（訂正が行われる）。
【００８８】
復号演算処理部３０４の構成は、図１４に示す復号演算処理部４の構成と同じである。但し、復号演算処理部３０４のＧＬＵの構成は、ＧＬＵ５４とは異なる。
図９は、復号演算処理部３０４のＧＬＵ４５４の構成図である。
図９に示すように、ＧＬＵ４５４は、オペレイションロジック４６０，４６１、ＧＦインバージョンＲＯＭ４６２、ＧＦ乗算加算ロジック４６３およびオペレイションセレクタ４６４を備えている。
ここで、ＧＦ乗算加算ロジック４６３には、図１に示す乗算器１１０あるいは図２に示す乗算器１３０が用いられている。そのため、復号演算処理のステップ数を大幅に減らすことができ、復号演算処理を短時間で行なうことができる。
また、図１５に示すようなコンバータ６２，６３を設ける必要がなくなり、回路規模の縮小化が図れる。
【００８９】
以上、ｔ＝２のＣＩＲＣ符号を例示して説明したが、ｔの値が大きくて、ユークリッド復号法やバーレカンプ・マッシイ法などを用いる場合にも、本発明を適用できる。
【００９０】
【発明の効果】
以上説明したように、本発明のリードソロモン復号装置によれば、装置規模の縮小化を図ることができる。
また、本発明のリードソロモン復号装置によれば、復号演算処理を短時間で行うことができる。
【図面の簡単な説明】
【図１】図１は、本発明の実施形態に係わるガロア体の乗算回路の構成図である。
【図２】図２は、本発明の実施形態に係わるガロア体のその他の乗算回路の構成図である。
【図３】図３は、本発明の実施形態に係わるリードソロモン復号装置の構成図である。
【図４】図４は、図３に示すＧＦカウンタの一例の構成図である。
【図５】図５は、図３に示すＧＦカウンタのその他の例の構成図である。
【図６】図６は、図３に示すリードソロモン復号装置の動作時におけるデータおよび構成要素の時系列的な状態を示す図である。
【図７】図７は、図３に示す入力パラメータ演算器、スイッチおよびレジスタの構成図である。
【図８】図８は、図３に示す訂正操作実行器の構成図である。
【図９】図９は、図３に示す復号演算処理部のＧＬＵの構成図である。
【図１０】図１０は、従来のリードソロモン復号装置の構成図である。
【図１１】図１１は、図１０に示すリードソロモン復号装置の動作時におけるデータおよび構成要素の時系列的な状態を示し、（Ａ）は入力データ、（Ｂ）は出力データ、（Ｃ）はレジスタＢOUT の記憶状態、（Ｄ）はレジスタＢINの記憶状態、（Ｅ）はレジスタＧOUT の記憶状態、（Ｆ）はレジスタＧINの記憶状態、（Ｇ）は復号演算器の処理状態をそれぞれ示している。
【図１２】図１２は、図１０に示す入力パラメータ演算器およびレジスタの構成図である。
【図１３】図１３は、図１０に示す訂正操作実行器およびレジスタの構成図である。
【図１４】図１４は、図１０に示す復号演算処理部の構成図である。
【図１５】図１５は、図１４に示すＧＬＵの構成図である。
【符号の説明】
１１０，１３０…乗算器、３０１…リードソロモン復号装置、３０２…メモリブロック、３０３…バスＩ／Ｆブロック、３０４…復号演算処理部、３０９…入力パラメータ演算器、３１１…ＧＦカウンタ、３１２…訂正操作実行器、３１４…レジスタ、３１７…復号演算器
【図１】
0003850512.tif 000022
【図２】
0003850512.tif 000023
【図３】
0003850512.tif 000024
【図４】
0003850512.tif 000025
【図５】
0003850512.tif 000026
【図６】
0003850512.tif 000027
【図７】
0003850512.tif 000028
【図８】
0003850512.tif 000029
【図９】
0003850512.tif 000030
【図１０】
0003850512.tif 000031
【図１１】
0003850512.tif 000032
【図１２】
0003850512.tif 000033
【図１３】
0003850512.tif 000034
【図１４】
0003850512.tif 000035
【図１５】
0003850512.tif 000036