(57)【特許請求の範囲】
【請求項１】
入力データについてシンドローム計算を行うシンドローム計算手段と、
入力された消失フラグから、消失位置のガロア体の冪表現である消失位置情報を計算する消失位置情報計算手段と、
処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つバッファ部と、処理ステップ数と消失データ数との比較結果に基づいて、上記バッファ部と演算器の結合を切り替えるセレクタとを有し、上記消失位置情報及び上記シンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める構成である誤り位置多項式計算手段と、
上記誤り位置多項式から誤り数値多項式を計算する誤り数値多項式計算手段と、
上記誤り位置多項式及び誤り数値多項式から誤り数値を算出し、入力データについて訂正処理を行う訂正処理手段と
を備えたことを特徴とする復号装置。
【請求項２】
入力データから計算されたシンドロームと、入力された消失フラグから計算された、消失位置のガロア体の冪表現である消失位置情報とを用いて、誤り位置多項式を計算する誤り位置多項式計算方法であって、
処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つバッファと演算器の結合の切り替えを、処理ステップ数と消失データ数との比較結果に基づいて、制御することで、上記消失位置情報及び上記シンドロームから、誤り位置情報を解として持つ誤り位置多項式を求めることを特徴とする誤り位置多項式計算方法。
【請求項３】
入力データから計算されたシンドロームと、入力された消失フラグから計算された、消失位置のガロア体の冪表現である消失位置情報とを用いて、誤り位置多項式を計算する処理を実行させるプログラムであって、
処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つバッファと演算器の結合の切り替えを、処理ステップ数と消失データ数との比較結果に基づいて、制御することで、上記消失位置情報及び上記シンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める処理を実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はリードソロモン符号の復号装置、及び誤り位置多項式計算方法、さらには誤り位置多項式計算方法を実行させるプログラムに関するものである。
【０００２】
【従来の技術】
【非特許文献１】
A (208,192;8) Reed-Solomon decoder for DVD applicationRsie-Chia Chang; Shung, C.B.Communications, 1998. ICC 98. Conference Record. 1998 IEEE International Conference on , Volume: 2 , 1998Page(s): 957 -960 vol.2
【非特許文献２】
On decoding of both errors and erasures of a Reed-Solomon code using an inverse-free Berlekamp-Massey algorithmJyh-Horng Jeng; Trieu-Kien TruongCommunications, IEEE Transactions on , Volume: 47 Issue: 10 , Oct. 1999Page(s): 1488 -1494
【０００３】
リードソロモン符号の復号において、伝送経路における受信語の欠落の位置が与えられた場合、その情報に基づくことによって、通常に訂正を行うよりも多くの誤りの訂正が可能となる復号方法が存在する。
この手法は、通常の復号時に受信語より計算して求めるシンドロームという数値群に加え、消失位置をその解として持つ消失位置多項式を利用することによって、最大でパリティ数に等しいデーターの欠落を補うことができ、インターリーブといわれる手法と組み合わせて使用することによって、記録メディアの欠損に依存するような大きな受信データーの欠落に対応することができる。
【０００４】
リードソロモン符号の復号法にそった形で説明を続ける。
リードソロモンの復号において、通常に訂正を行う場合には、最大訂正可能数ｔと符号パラメータ（Ｎ，Ｋ）との間には、
Ｎ−Ｋ＝２ｔ−１
という関係がある。
【０００５】
まず、受信したデータから、シンドローム計算回路により、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1を計算する。
シンドローム多項式は次の（数１）の形であらわされる。
【数１】
0003843952.tif 000002
【０００６】
また、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1から、誤り位置多項式計算回路を用いて誤り位置多項式を求める。誤り位置多項式とは、誤りの位置をＺ0、Ｚ1、・・・、Ｚ2t-1とした場合に、次の（数２）として表される多項式である。
【数２】
0003843952.tif 000003
【０００７】
さらに、誤り数値多項式Ω(x)は、上記の誤り位置多項式σ(x)とシンドロームから以下の（数３）で求められる。
【数３】
0003843952.tif 000004
これらの式から実際の誤りの位置と数値を導くことが出来る。
【０００８】
リードソロモン符号の復号を行う回路を構成する際には、誤り位置多項式σ(x)を導出する回路が、最も回路規模や演算ステップ数に影響を及ぼす。この誤り位置多項式σ(x)を導出する回路として、バーレカンプアルゴリズムを実装した回路が、上記非特許文献１にて紹介されている。この回路を図７に示す。
この図７の回路では、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1についての入力レジスタｒｇ１４、及び入力レジスタｒｇ１４を選択するセレクタＳＥＬ１４が設けられる。また変数σ系列のシフトレジスタＳＲ１，変数λ系列のシフトレジスタＳＲ２が設けられる。さらに加算器１１，１２、乗算器ＭＬ１１，ＭＬ１２，ＭＬ１３、レジスタｒｇ１１，ｒｇ１２，ｒｇ１３、セレクタＳＥＬ１１，ＳＥＬ１２が設けられる。
この回路の場合、回路規模の大きなガロア体演算回路（乗算器ＭＬ１１，ＭＬ１２，ＭＬ１３）が３つのみで構成され、回路規模の面で優れている。但し次に述べる消失訂正はサポートされていない。
【０００９】
【発明が解決しようとする課題】
リードソロモン符号の訂正処理において、あらかじめ符号語中のシンボルの誤り位置を示す消失位置のガロア体表現が得られた場合には、訂正可能数をＮ−Ｋまで引き上げる事が出来る。これを消失訂正という。消失位置符号の数、Neras（消失誤りの数）とNerr（誤りの数）には次の（数４）のような関係が成り立つ。
【数４】
0003843952.tif 000005
【００１０】
消失訂正のみを行うには、まず次の（数５）のような消失位置多項式Λ(x)を消失位置のガロア体表現から計算する。
【数５】
0003843952.tif 000006
消失訂正のみを行う場合は、これを上記（数２）のσ(x)に置き換えて誤り数値多項式を導けばよい。
【００１１】
通常の誤り訂正と消失訂正を同時に行う場合には、シンドロームと消失位置多項式Λから誤り位置多項式σを導出する。
上記非特許文献２には、従来のアルゴリズムにあまり変更が加えられない形で消失訂正も行うことの出来る、修正バーレカンプアルゴリズムが提示されている。
上記非特許文献２に示されている、通常の誤り訂正と消失訂正を同時に行うの場合の復号装置全体の構成は図８のようになる。
シンドローム計算部３１は、入力データｃからシンドロームＳ0、Ｓ1、・・・、Ｓ2t-1の計算を行う。
消失位置多項式計算部３２は、入力される消失フラグｅ0、ｅ1、・・・、ｅ2t-1から上記（数５）により消失位置多項式Λ(x)を得る。
誤り位置多項式計算部３３は、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置多項式Λ(x)から誤り位置多項式σ(x)を導出する。
誤り数値多項式計算部３４は、誤り位置多項式σを用いて上記（数３）により誤り数値多項式Ω(x)を得る。
チェンサーチ部３５は、誤り位置多項式σと誤り数値多項式Ω(x)から誤り数値を得る。そして入力データｃは遅延バッファ３６により所定タイミング遅延されて演算器３７に入力されるが、この演算器３７においてチェンサーチ部３５による誤り数値との演算が行われ、復号データｃ’として出力される。
【００１２】
このような構成で通常の誤り訂正と消失訂正が同時に行われる。ところが、このような構成では、誤り位置多項式σ(x)の導出以前に、消失フラグｅ0、ｅ1、・・・、ｅ2t-1から消失位置多項式Λ(x)を導出する必要がある。また消失位置多項式Λ(x)は消失フラグが全て入力されてからでなければ計算できないため、シンドローム計算後の処理となる。従って、この図８の構成をとると、シンドローム計算終了後に消失位置多項式を計算する演算ステップが必要になり、必要な演算ステップ数が増大してしまうという問題が生ずる。
【００１３】
【課題を解決するための手段】
本発明はこのような問題点に鑑みてなされたもので、従来のBerlekamp-Masseyアルゴリズムの計算回路から少ない変更により、消失訂正を行うことのできる復号装置、及び誤り位置多項式計算方法を実現することを目的とする。
【００１４】
このため本発明の復号装置は、入力データについてシンドローム計算を行うシンドローム計算手段と、入力された消失フラグから、消失位置のガロア体の冪表現である消失位置情報を計算する消失位置情報計算手段と、処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つバッファ部と、処理ステップ数と消失データ数との比較結果に基づいて、上記バッファ部と演算器の結合を切り替えるセレクタとを有し、上記消失位置情報及び上記シンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める構成である誤り位置多項式計算手段と、上記誤り位置多項式から誤り数値多項式を計算する誤り数値多項式計算手段と、上記誤り位置多項式及び誤り数値多項式から誤り数値を算出し、入力データについて訂正処理を行う訂正処理手段とを備える。
【００１５】
本発明の誤り位置多項式計算方法は、入力データから計算されたシンドロームと、入力された消失フラグから計算された、消失位置のガロア体の冪表現である消失位置情報とを用いて、誤り位置多項式を計算する誤り位置多項式計算方法であって、処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つバッファと演算器の結合の切り替えを、処理ステップ数と消失データ数との比較結果に基づいて、制御することで、上記消失位置情報及び上記シンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める。
本発明のプログラムは、このような誤り位置多項式計算方法を実現するプログラムである。
【００１６】
即ち、従来、消失訂正をサポートした場合において、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置多項式Λ(x)に基づいて誤り位置多項式σ(x)を計算していたところ、上記本発明によれば、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置情報Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1に基づいて誤り位置多項式σ(x)を計算するものとなる。
また、演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づき制御することによって、消失位置情報からの消失位置多項式の導出と誤り位置多項式の導出について、同一の回路（誤り位置多項式計算手段）において実現する。
【００１７】
【発明の実施の形態】
以下、本発明の実施の形態の復号装置及び誤り位置多項式計算方法について、図１〜図６を参照しながら説明する。
本実施の形態の復号装置は、回路規模や演算ステップ数を抑えながらも、消失位置訂正をサポートできるものである。
【００１８】
図１は、本例のリードソロモン符号の復号装置の全体を示している。
シンドローム計算部１は、入力データｃからシンドロームＳ0、Ｓ1、・・・、Ｓ2t-1の計算を行う。
消失位置情報計算部２は、入力される消失フラグｅ0、ｅ1、・・・、ｅ2t-1から消失位置情報をＥｒ0、Ｅｒ1、・・・、Ｅｒ2t-1を計算する。
誤り位置多項式計算部３は、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置情報をＥｒ0、Ｅｒ1、・・・、Ｅｒ2t-1から誤り位置多項式σ(x)を導出する。
誤り数値多項式計算部４は、誤り位置多項式σを用いて上記（数３）により誤り数値多項式Ω(x)を得る。
チェンサーチ部５は、誤り位置多項式σと誤り数値多項式Ω(x)から誤り数値を得る。そして入力データｃは遅延バッファ６により所定タイミング遅延されて演算器７に入力されるが、この演算器７においてチェンサーチ部５による誤り数値との演算が行われ、復号データｃ’として出力される。
【００１９】
このような本例の復号装置において、上述した図８の復号装置と異なる点は次の▲１▼、▲２▼の２つの点である。
▲１▼  図８ではシンドロームの計算と並行して消失位置多項式計算部３２で消失位置多項式Λ(x)を求めていたところ、本例の図１においては、消失位置情報計算部２として、消失フラグｅ0、ｅ1、・・・、ｅ2t-1を、消失位置をガロア体の冪表現である消失位置情報Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1に変換するモジュールが設けられている。
▲２▼  図８では誤り位置多項式計算部３３で、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置多項式Λ(x)から誤り位置多項式σ(x)を導出したが、本例の図１においては、誤り位置多項式計算部３では、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置情報をＥｒ0、Ｅｒ1、・・・、Ｅｒ2t-1から誤り位置多項式σ(x)を導出する。
【００２０】
まず▲１▼に挙げた消失位置情報計算部２は、このモジュールで得られた消失位置のガロア体表現（Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1）を、▲２▼に挙げた誤り位置多項式計算部３、即ち今回改良された修正バーレカンプアルゴリズムを実行するモジュールに送るものである。
消失位置情報計算部２は、消失位置多項式を計算する代わりに、消失フラグ（消失位置）ｅ0、ｅ1、・・・、ｅ2t-1から、消失位置のガロア体表現である消失位置情報Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1を、
【数６】
0003843952.tif 000007
と計算する。ここでαはガロア体の原始元（primitive element）である。消失位置多項式の計算には多くの演算ステップを要するが、各消失位置のガロア体表現は、消失位置より１演算ステップで計算することができ、従って消失位置情報計算部２は簡便な回路になる。
【００２１】
▲２▼として挙げた誤り位置多項式計算部３では、入力として、シンドロームと消失位置情報が与えられた場合に、バーレカンプアルゴリズムを基にして改善された図４〜図６のアルゴリズムで誤り位置多項式σ(x)を導出する。またそれを実現する回路構成は図２のようになる。
まず図２の構成を説明する。
【００２２】
図２の回路は、以下のような部分より構成される。
・処理ステップ数により更新される2つのカウンタ値（Ｃ１，Ｃ２）
・カウンタ値により制御されたバッファ
・ガロア体乗算器
・ガロア体乗算器の切り替え回路
・シンドローム選択回路
これら各部について説明する。
【００２３】
＜処理ステップ数により更新される2つのカウンタ値（Ｃ１，Ｃ２）＞
このカウンタ値Ｃ１，Ｃ２は、図２の回路上に現れるものではないが、この回路の動作を制御する値とされるものである。後述する図４〜図６のアルゴリズムにおいて、変数ｊ，ｉとしてカウンタ値Ｃ１，Ｃ２が設定される。Ｃ１＝ｊ、Ｃ２＝ｉとなる。
【００２４】
このカウンタ値Ｃ１，Ｃ２という2つのカウンタ値は以下のＩ，II，III，IVのような処理を行う。Ｃ１ｎ，Ｃ２ｎをカウンタ値を保持するためのレジスタとする。
Ｉ．Ｃ１ｎ＝０、Ｃ２ｎ＝０
II．Ｃ１＝Ｃ１ｎ、Ｃ２＝Ｃ２ｎ
III．Ｃ１＝Ｃ２ならＣ１ｎ＝Ｃ１＋１、Ｃ２ｎ＝０
Ｃ１＝Ｃ２でなければＣ１ｎ＝Ｃ１、Ｃ２ｎ＝Ｃ２＋１
IV．IIへ
このＩ〜IVについて、処理開始時にＩを実行し、１処理ステップ毎にII〜IVの動作を繰り返す。
【００２５】
これにより具体的には、各カウンタ値「Ｃ１，Ｃ２」は処理ステップ毎に次の各値に遷移する。
「Ｃ１，Ｃ２」＝「０，０」→「１，０」→「１，１」→「２，０」→「２，１」→「２，２」→「３，０」→・・・
但しこれは一例であり、カウンタ値Ｃ１、Ｃ２は後述する図４から図６で説明するように、変数ｊ，ｉとしてカウントする値の範囲が設定される。
【００２６】
＜カウンタ値により制御されたバッファ＞
カウンタ値により制御されたバッファとは、図２のバッファ部Ｂｆ１，Ｂｆ２のことである。
バッファ部Ｂｆ１、Ｂｆ２はそれぞれ、処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つシフトレジスタとして構成される。
即ちバッファ部Ｂｆ１は、レジスタσrg(0)〜σrg(2t-1)によりシフトレジスタが構成されるとともに、各レジスタσrg(0)〜σrg(2t-2)に対して、その前段のレジスタの出力と、バッファ部Ｂｆ１に入力される演算結果とを選択して入力するセレクタＳＬσ(0)〜ＳＬσ(2t-2)が設けられる。
またバッファ部Ｂｆ２は、レジスタλrg(0)〜λrg(2t-1)によりシフトレジスタが構成されるとともに、各レジスタλrg(1)〜σrg(2t-2)に対して、その前段のレジスタの出力と、バッファ部Ｂｆ２に入力される演算結果とを選択して入力するセレクタＳＬλ(1)〜ＳＬλ(2t-2)が設けられる。
【００２７】
またバッファ部Ｂｆ１には、加算器ＡＤ１の演算結果σiterが入力される。
バッファ部Ｂｆ２に対しては、入力段にセレクタＳＥＬ０、ＳＥＬ２が設けられる。セレクタＳＥＬ０は、バッファ部Ｂｆ１のレジスタσrg(0)の値σregと、バッファ部Ｂｆ２のレジスタλrg(0)の値λregとを選択する。セレクタＳＥＬ２は、加算器ＡＤ１の演算結果σiterと、セレクタＳＥＬ０の選択値とを選択して値λiter+1としてバッファ部Ｂｆ２に入力する。
【００２８】
各シフトレジスタレジスタ（σrg(0)〜σrg(2t-1)、λrg(0)〜λrg(2t-1)）は、カウンタ値Ｃ２の値により、入力を前段のレジスタと、バッファに入力される演算結果（σiter、λiter+1）とから選択することになる。つまりセレクタＳＬσ(0)〜ＳＬσ(2t-2)及びセレクタＳＬλ(1)〜ＳＬλ(2t-2)はカウンタ値Ｃ２によってその選択状態が制御される。
なお、このような構成は、上記図７の回路に比べ必要な処理ステップ数を削減するものとなる。
【００２９】
＜ガロア体乗算器＞
ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３が設けられる。これらガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３は、２個の任意のガロア体の元を乗算する。
【００３０】
＜ガロア体乗算器切り替え回路＞
まずガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３を含む回路系は次のように構成されている。
ガロア体乗算器ＭＬ３はセレクタＳＥＬ６によって選択されたシンドロームＳと加算器ＡＤ１の演算結果σiterを乗算して乗算結果MUL3を出力する。ガロア体乗算器ＭＬ３の出力MUL3は加算器ＡＤ２に供給される。
加算器ＡＤ２はレジスタｒｇ６とガロア体乗算器ＭＬ３の出力を加算して出力する（δk+1）。またこの加算器ＡＤ２の出力δk+1はレジスタｒｇ６に保持される。つまりレジスタｒｇ６は値δk+1を保持するレジスタとなる。
加算器ＡＤ２の出力δk+1はセレクタＳＥＬ３に供給される。セレクタＳＥＬ３は、出力δk+1と、レジスタｒｇ５の値を選択してレジスタｒｇ５に入力する。このレジスタｒｇ５は値δを保持するレジスタとなる。
レジスタｒｇ５の値δはセレクタＳＥＬ１，ＳＥＬ４に供給される。
セレクタＳＥＬ４は、値δと消失位置の値Ｅｒを選択してガロア体乗算器ＭＬ２に供給する。ガロア体乗算器ＭＬ２では、セレクタＳＥＬ４からの値とバッファ部Ｂｆ２からの値λregを乗算し、乗算結果MUL2を加算器ＡＤ１に供給する。
セレクタＳＥＬ１は、レジスタｒｇ５からの値δと、レジスタｒｇ７に保持された値γを選択して、レジスタｒｇ７に入力する。レジスタｒｇ７は値γを保持するレジスタとなる。
レジスタｒｇ７の値γはセレクタＳＥＬ５に供給される。セレクタＳＥＬ５は値γと、値「１」を選択してガロア体乗算器ＭＬ１に出力する。
ガロア体乗算器ＭＬ１では、セレクタＳＥＬ５からの値とバッファ部Ｂｆ１からの値σregを乗算し、乗算結果MUL1を加算器ＡＤ１に供給する。
【００３１】
このような回路系において、ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３の入出力の切り替えはカウンタ値Ｃ１と、消失フラグの立っているデータの数Eras_numを比較することによって行われる。
３つの各ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３については、それぞれ上記セレクタＳＥＬ５，ＳＥＬ４，ＳＥＬ６によって図３に示すように接続の切り替えが行われる。
【００３２】
まずカウンタ値Ｃ１と、消失フラグの立っているデータの数Eras_numの比較結果がＣ１＜Eras_numの場合は、図３（ａ）のようになる。
ガロア体乗算器ＭＬ１には、値「１」とバッファ部Ｂｆ１からの値σ（σreg）が入力され、その乗算結果MUL1を出力する。
ガロア体乗算器ＭＬ２には、カウンタ値Ｃ１に基づく消失位置情報の値ＥｒC1とバッファ部Ｂｆ２からの値λ（λreg）が入力され、その乗算結果MUL2を出力する。
ガロア体乗算器ＭＬ３には、シンドロームＳと加算器ＡＤ１の演算結果（σiter＝MUL1＋MUL2）が入力され、その乗算結果MUL3を出力する。
【００３３】
カウンタ値Ｃ１と、消失フラグの立っているデータの数Eras_numの比較結果がＣ１≧Eras_numの場合は、図３（ｂ）のようになる。
ガロア体乗算器ＭＬ１には、値γとバッファ部Ｂｆ１からの値σ（σreg）が入力され、その乗算結果MUL1を出力する。
ガロア体乗算器ＭＬ２には、値δとバッファ部Ｂｆ２からの値λ（λreg）が入力され、その乗算結果MUL2を出力する。
ガロア体乗算器ＭＬ３には、シンドロームＳと加算器ＡＤ１の演算結果（σiter＝MUL1＋MUL2）が入力され、その乗算結果MUL3を出力する。
このようにガロア体乗算器切り替え回路が構成される。
【００３４】
＜シンドローム選択回路＞
シンドローム選択回路は、入力されるシンドロームＳ0、Ｓ1、・・・、Ｓ2t-1を保持するレジスタｒｇ８と、レジスタｒｇ８の値（Ｓ0、Ｓ1、・・・、Ｓ2t-1）を選択したシンドロームＳをガロア体乗算器ＭＬ３に供給するセレクタＳＥＬ６により構成される。
セレクタＳＥＬ６は、カウンタ値Ｃ２、Ｃ１の値から計算した値をインデックスとして、そのインデックスに対応したシンドロームＳを出力する。つまりインデックスとしてｉが与えられた場合は、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1のうちでＳｉを出力する回路である。
【００３５】
以下、このような図２の回路で実現できる本例のアルゴリズムを図４〜図６で説明する。
図１で説明したように、図２の回路とされる誤り位置多項式計算部３には、入力としては、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置情報Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1が与えられる。
その場合に、誤り位置多項式σ(x)を導出するアルゴリズムが図４〜図６のようになる。
なお上記もしたが、Eras_numは前段の消失位置計算ブロックより与えられる消失の起こった位置の数である。
またｔは先の説明にあるように、符号長をＮ、送信情報語長をＫとした場合に、Ｎ−Ｋ＝２ｔ−１で与えられる。
σregはσを保存するパラメータであり、λregはλを保存するパラメータである。σiter、λiterは繰り返し回数の変数iterの値に応じ、それぞれσ0〜σ2t-1、λ0〜λ2t-1から選択される値である。
【００３６】
図５のステップＦ１０１では初期化が行われる。即ちσ0〜σ2t-1、λ0〜λ2t-1は全て「０」にセットされる。また処理に用いる内部変数Ｌ＝０とされる。さらにσ0＝λ0＝γ＝１とされ、δ＝Ｓ0とされる。具体的には図２のバッファ部Ｂｆ１，Ｂｆ２の各レジスタ、及び値δを保持するレジスタｒｇ５，値γを保持するレジスタｒｇ７の値がこのように初期化される。
【００３７】
ステップＦ１０２で、カウント値Ｃ１に相当する変数ｊとして、０から消失位置の数Eras_numをセットし、変数ｊのループ回数、つまりカウント値Ｃ１のカウント範囲を規定する。
ステップＦ１０３では、繰り返し回数の変数iterにｊ＋１の値をセットし、またレジスタｒｇ６における値δk+1を「０」とする。
またＦ１０４で、カウント値Ｃ２に相当する変数ｉとして、０から値iterをセットし、変数ｉのループ回数、つまりカウント値Ｃ２のカウント範囲を規定する。
【００３８】
ステップＦ１０５では、値σregとして値σ0を設定する。また値λregとして値λ0を設定する。
そしてステップＦ１０６で変数ｋについて０から２ｔ−１をセットし、変数ｋのループ回数を規定する。
そしてステップＦ１０７で、値σkを値σk+1とし、値λkを値λk+1とする。これをステップＦ１０８でｋのループ終了とされるまで実行する。
つまり、この処理により、バッファ部Ｂｆ１，Ｂｆ２の各シフトレジスタの値が値ｋのループ回数だけシフトされるものとなる。
【００３９】
ステップＦ１０９では、ガロア体乗算器ＭＬ１，ＭＬ２の乗算と、その乗算結果MUL1、MUL2の加算器ＡＤ１での加算が行われて演算結果σiterが得られる。
このときステップＦ１０２でのカウント値Ｃ１（＝ｊの値）の設定により、Ｃ１＜Eras_num、つまり図３（ａ）の切換状態であることで、ガロア体乗算器ＭＬ１ではMUL1＝１×σreg、ガロア体乗算器ＭＬ２ではMUL2＝Ｅｒj×λregの乗算が行われ、加算器ＡＤ１での演算結果σiterは、σiter＝１×σreg＋Ｅｒj×λregとなる。
【００４０】
ステップＦ１１０では値λiter+1が上記演算結果σiterとされる。つまり値σiterは、バッファ部Ｂｆ１に入力されるとともに、セレクタＳＥＬ２が値σiterを選択することで、バッファ部Ｂｆ２にも値σiterが入力される。
ステップＦ１１１では、ガロア体乗算器ＭＬ３の乗算及び加算器ＡＤ２の加算が行われ、レジスタｒｇ６の値δk+1が更新される。
即ちガロア体乗算器ＭＬ３では、上記演算結果σiterと、セレクタＳＥＬ６で選択されたシンドロームＳj+1-iについて乗算を行って乗算結果MUL3（＝σiter×Ｓj+1-i）を出力し、加算器ＡＤ２では、乗算結果MUL3とレジスタｒｇ６の値δk+1を加算する。そしてこの加算結果（δk+1＋σiter×Ｓj+1-i）がレジスタｒｇ６の値δk+1とされる。
【００４１】
以上の処理は変数ｉのループ終了まで行われ、終了したらステップＦ１１２からＦ１１３に進み、値δが値δk+1に更新される。即ちセレクタＳＥＬ３が値δk+1を選択してレジスタｒｇ５の値δを更新する。
変数ｊのループが終了したら、ステップＦ１１４から図５のステップＦ１１５に進む。
【００４２】
ステップＦ１１５では、カウント値Ｃ１に相当する変数ｊとして、消失位置の数Eras_numから２ｔ−１をセットし、変数ｊのループ処理を規定する。
ステップＦ１１６では、繰り返し回数の変数iterにｊ＋１の値をセットし、またレジスタｒｇ６における値δk+1を「０」とする。
またＦ１１７で、カウント値Ｃ２に相当する変数ｉとして、０から値iterをセットし、変数ｉのループ処理を規定する。
【００４３】
ステップＦ１１８では、値σregとして値σ0を設定する。また値λregとして値λ0を設定する。
そしてステップＦ１１９で変数ｋについて０から２ｔ−１をセットし、変数ｋのループ処理を規定する。
そしてステップＦ１２０で、値σkを値σk+1とし、値λkを値λk+1とする。これをステップＦ１２１でｋのループ終了とされるまで実行する。
つまり、この処理により、バッファ部Ｂｆ１，Ｂｆ２の各シフトレジスタの値が値ｋのループ回数だけシフトされるものとなる。
【００４４】
ステップＦ１２２では、ガロア体乗算器ＭＬ１，ＭＬ２の乗算と、その乗算結果MUL1、MUL2の加算器ＡＤ１での加算が行われて演算結果σiterが得られる。
このときはステップＦ１１５でのカウント値Ｃ１（＝ｊの値）の設定により、Ｃ１≧Eras_num、つまり図３（ｂ）の切換状態となっているため、ガロア体乗算器ＭＬ１ではMUL1＝γ×σreg、ガロア体乗算器ＭＬ２ではMUL2＝δ×λregの乗算が行われ、加算器ＡＤ１の演算結果σiterは、σiter＝γ×σreg＋δ×λregとなる。
【００４５】
ステップＦ１２３では、δ＝０であるか、或いは制御変数Ｌについて２Ｌ＞ｊ−Eras_numであるかを判別する。
このいずれかの条件が満たされていれば、ステップＦ１２４で値λiter+1が値σregとされる。
この場合、上記演算結果σiterは、バッファ部Ｂｆ１に入力される。またセレクタＳＥＬ０、ＳＥＬ２がバッファ部Ｂｆ１の値σregを選択することで、バッファ部Ｂｆ２に値σregが入力される。
【００４６】
一方、ステップＦ１２３の条件が満たされていない場合は、ステップＦ１２５で値λiter+1が値λregとされる。
この場合、上記演算結果σiterは、バッファ部Ｂｆ１に入力される。またセレクタＳＥＬ０、ＳＥＬ２がバッファ部Ｂｆ２の値λregを選択することで、バッファ部Ｂｆ２に値λregが入力される。
【００４７】
ステップＦ１２６では、ガロア体乗算器ＭＬ３の乗算及び加算器ＡＤ２の加算が行われ、レジスタｒｇ６の値δk+1が更新される。
即ちガロア体乗算器ＭＬ３では、上記演算結果σiterと、セレクタＳＥＬ６で選択されたシンドロームＳj+1-iについて乗算を行って乗算結果MUL3（＝σiter×Ｓj+1-i）を出力し、加算器ＡＤ２では、乗算結果MUL3とレジスタｒｇ６の値δk+1を加算する。そしてこの加算結果（δk+1＋σiter×Ｓj+1-i）がレジスタｒｇ６の値δk+1とされる。
【００４８】
以上の処理は変数ｉのループ終了まで行われ、終了したらステップＦ１２７から図６のステップＦ１２８に進む。そして、δ＝０であるか、或いは２Ｌ＞ｊ−Eras_numであるかを判別する。
いずれかの条件が満たされていればステップＦ１３０に進む。
条件が満たされていなければ、ステップＦ１２９で、変数Ｌを、ｊ−Eras_num＋１−Ｌの値とし、また値γを値δに更新する。値γについては、セレクタＳＥＬ１がレジスタｒｇ５の値δを選択し、レジスタｒｇ７を更新することになる。
【００４９】
ステップＦ１３０では、値δが値δk+1に更新される。即ちセレクタＳＥＬ３が値δk+1を選択してレジスタｒｇ５の値δを更新する。
このステップＦ１１６〜Ｆ１３１の処理を変数ｊのループ終了まで実行し、終了したらステップＦ１３２に進む。この時点でバッファ部Ｂｆ１としてのシフトレジスタσrg(0)〜σrg(2t-1)に保持されている値として、値σ0〜σ2t-1を出力して処理が終了される。
以上の処理で誤り位置多項式計算部３から誤り位置多項式σ(x)が出力されるものとなる。
【００５０】
即ち本実施の形態によれば、、従来、消失訂正をサポートした場合において、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置多項式Λ(x)に基づいて誤り位置多項式σ(x)を計算していたところを、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置情報Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1に基づいて誤り位置多項式σ(x)を計算するものとなる。
また、演算の途中結果を保持するバッファＢｆ１，Ｂｆ２と演算器（ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３）の結合の切り替えを、消失した受信語の数（Eras_num）と処理ステップ数（カウント値Ｃ１）に基づき制御することによって、消失位置情報からの誤り位置多項式の導出について、図２の回路のみで実現できる。
【００５１】
このような手法により、Berlekamp-Masseyアルゴリズムの計算回路から少ない変更で消失訂正を行うことのできる復号装置を構成することができる。
またガロア体乗算器の増加を伴わず、回路規模の増大も最小限に抑えることができる。
また、受信符号語における消失数に関わらず、必要最小限かつ固定のステップ数での処理が実現でき、復号遅延を最小限に抑えることができる。
【００５２】
本発明の復号装置は、例えば図２の回路構成により例えば図４〜図６のアルゴリズムで誤り位置多項式σ(x)を得る誤り位置多項式計算部３を用いた図１の構成の復号装置である。
また本発明の誤り位置多項式計算方法或いはプログラムは、一例として上記図４〜図６のようなアルゴリズムによる計算方法、或いはその計算方法を実行させるプログラムである。
即ち上記実施の形態は、本発明の復号装置、誤り位置多項式計算方法、及びプログラムに相当するものであるが、本発明はこの実施の形態の例に限定されず、その要旨の範囲内で各種の変形例が考えられる。
【００５３】
本発明のプログラムについては、復号装置含む電子機器（例えばディスクドライブ装置、テープ記録再生装置、通信装置その他）内のＲＯＭ、不揮発性メモリ、又はＲＡＭに一時的あるいは永続的に格納（記録）しておくことができる。また、フレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)、ＭＯ(Magnet Optical)ディスク、ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくこともできる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウェアとして提供することができ、上記ディスクドライブ装置等の電子機器の設計／製造などにも利用できる。
なお、プログラムは、上記のようなリムーバブルな記録媒体からインストールする他、プログラムを記憶しているサーバなどから、ＬＡＮ(Local Area Network)、インターネットなどのネットワークを介してダウンロードすることもできる。
【００５４】
【発明の効果】
以上の説明からわかるように本発明によれば、シンドロームＳ0、Ｓ1、・・・、Ｓ2t-1と消失位置情報Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1に基づいて誤り位置多項式σ(x)を計算する。また消失位置情報計算手段においては、消失位置のガロア体表現である消失位置情報Ｅｒ0、Ｅｒ1、・・・、Ｅｒ2t-1は消失フラグｅ0、ｅ1、・・・、ｅ2t-1から簡単な計算で求められる。また誤り位置多項式計算手段では、演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づき制御することによって、消失位置情報からの消失位置多項式の導出と誤り位置多項式の導出を実現できる。
これによって、従来のBerlekamp-Masseyアルゴリズムの計算回路から少ない変更により、消失訂正を行うことのできる復号装置を構成できるという効果がある。またこれは、ガロア体乗算器の増加を伴わず、回路規模の増大も最小限に抑えることができる。
さらに受信符号語における消失数に関わらず、必要最小限かつ固定のステップ数での処理が実現でき、復号遅延を最小限に抑えることができる。
【図面の簡単な説明】
【図１】本発明の実施の形態の復号装置のブロック図である。
【図２】実施の形態の誤り位置多項式計算部の回路図である。
【図３】実施の形態のガロア体乗算器の切換動作の説明図である。
【図４】実施の形態の誤り位置多項式計算処理のフローチャートである。
【図５】実施の形態の誤り位置多項式計算処理のフローチャートである。
【図６】実施の形態の誤り位置多項式計算処理のフローチャートである。
【図７】バーレカンプアルゴリズム実装回路の回路図である。
【図８】消失訂正をサポートした復号装置のブロック図である。
【符号の説明】
１  シンドローム計算部、２  消失位置情報計算部、３  誤り位置多項式計算部、４  誤り数値多項式計算部、５  チェンサーチ部、６  遅延バッファ、７  演算部、ＭＬ１，ＭＬ２，ＭＬ３  ガロア体乗算器
【図１】
0003843952.tif 000008
【図２】
0003843952.tif 000009
【図３】
0003843952.tif 000010
【図４】
0003843952.tif 000011
【図５】
0003843952.tif 000012
【図６】
0003843952.tif 000013
【図７】
0003843952.tif 000014
【図８】
0003843952.tif 000015