(57)【要約】【課題】従来のバーレカンプアルゴリズム計算回路から少ない変更により、消失訂正を行うことのできる復号装置、及び誤り位置多項式計算方法を実現する【解決手段】シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置のガロア体表現である消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１に基づいて誤り位置多項式σ（ｘ）を計算する。また演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づき制御することによって、消失位置情報からの消失位置多項式の導出と誤り位置多項式の導出について、同一の回路（誤り位置多項式計算手段）において実現する。【選択図】        図１
2004260646.tif 000002
【特許請求の範囲】
【請求項１】
入力データについてシンドローム計算を行うシンドローム計算手段と、
入力された消失フラグから消失位置情報を計算する消失位置情報計算手段と、
上記シンドローム計算手段で得られたシンドロームと、上記消失位置情報計算手段で得られた消失位置情報に基づいて誤り位置多項式を計算する誤り位置多項式計算手段と、
上記誤り位置多項式から誤り数値多項式を計算する誤り数値多項式計算手段と、
上記誤り位置多項式及び誤り数値多項式から誤り数値を算出し、入力データについて訂正処理を行う訂正処理手段と、
を備えたことを特徴とする復号装置。
【請求項２】
上記誤り位置多項式計算手段は、
処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つバッファ部と、
処理ステップ数及び消失データ数により上記バッファ部と演算器の結合を切り替えるセレクタとを有し、
消失位置のガロア体表現及びシンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める構成とされたことを特徴とする請求項１に記載の復号装置。
【請求項３】
入力データから計算されたシンドロームと、入力された消失フラグから計算された消失位置情報とを用いて、誤り位置多項式を計算することを特徴とする誤り位置多項式計算方法。
【請求項４】
演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づいて制御することで、消失位置のガロア体表現及びシンドロームから、誤り位置情報を解として持つ誤り位置多項式を求めることを特徴とする請求項３に記載の誤り位置多項式計算方法。
【請求項５】
入力データから計算されたシンドロームと、入力された消失フラグから計算された消失位置情報とを用いて、誤り位置多項式を計算する処理を実行させるプログラム。
【請求項６】
演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づいて制御することで、消失位置のガロア体表現及びシンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める処理を実行させる請求項５に記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はリードソロモン符号の復号装置、及び誤り位置多項式計算方法、さらには誤り位置多項式計算方法を実行させるプログラムに関するものである。
【０００２】
【従来の技術】
【非特許文献１】
Ａ  （２０８，１９２；８）  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｄｅｃｏｄｅｒ  ｆｏｒ  ＤＶＤ  ａｐｐｌｉｃａｔｉｏｎＲｓｉｅ−Ｃｈｉａ  Ｃｈａｎｇ；  Ｓｈｕｎｇ，  Ｃ．Ｂ．
Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  １９９８．  ＩＣＣ  ９８．  Ｃｏｎｆｅｒｅｎｃｅ  Ｒｅｃｏｒｄ．  １９９８  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ，  Ｖｏｌｕｍｅ：  ２  ，  １９９８
Ｐａｇｅ（ｓ）：  ９５７  −９６０  ｖｏｌ．２
【非特許文献２】
Ｏｎ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｂｏｔｈ  ｅｒｒｏｒｓ  ａｎｄ  ｅｒａｓｕｒｅｓ  ｏｆ  ａ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅ  ｕｓｉｎｇ  ａｎ  ｉｎｖｅｒｓｅ−ｆｒｅｅ  Ｂｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙ  ａｌｇｏｒｉｔｈｍＪｙｈ−Ｈｏｒｎｇ  Ｊｅｎｇ；  Ｔｒｉｅｕ−Ｋｉｅｎ  Ｔｒｕｏｎｇ
Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ，  Ｖｏｌｕｍｅ：  ４７  Ｉｓｓｕｅ：  １０  ，  Ｏｃｔ．  １９９９Ｐａｇｅ（ｓ）：  １４８８  −１４９４
【０００３】
リードソロモン符号の復号において、伝送経路における受信語の欠落の位置が与えられた場合、その情報に基づくことによって、通常に訂正を行うよりも多くの誤りの訂正が可能となる復号方法が存在する。
この手法は、通常の復号時に受信語より計算して求めるシンドロームという数値群に加え、消失位置をその解として持つ消失位置多項式を利用することによって、最大でパリティ数に等しいデーターの欠落を補うことができ、インターリーブといわれる手法と組み合わせて使用することによって、記録メディアの欠損に依存するような大きな受信データーの欠落に対応することができる。
【０００４】
リードソロモン符号の復号法にそった形で説明を続ける。
リードソロモンの復号において、通常に訂正を行う場合には、最大訂正可能数ｔと符号パラメータ（Ｎ，Ｋ）との間には、
Ｎ−Ｋ＝２ｔ−１
という関係がある。
【０００５】
まず、受信したデータから、シンドローム計算回路により、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１を計算する。
シンドローム多項式は次の（数１）の形であらわされる。
【数１】
2004260646.tif 000003
【０００６】
また、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１から、誤り位置多項式計算回路を用いて誤り位置多項式を求める。誤り位置多項式とは、誤りの位置をＺ０、Ｚ１、・・・、Ｚ２ｔ−１とした場合に、次の（数２）として表される多項式である。
【数２】
2004260646.tif 000004
【０００７】
さらに、誤り数値多項式Ω（ｘ）は、上記の誤り位置多項式σ（ｘ）とシンドロームから以下の（数３）で求められる。
【数３】
2004260646.tif 000005
これらの式から実際の誤りの位置と数値を導くことが出来る。
【０００８】
リードソロモン符号の復号を行う回路を構成する際には、誤り位置多項式σ（ｘ）を導出する回路が、最も回路規模や演算ステップ数に影響を及ぼす。この誤り位置多項式σ（ｘ）を導出する回路として、バーレカンプアルゴリズムを実装した回路が、上記非特許文献１にて紹介されている。この回路を図７に示す。
この図７の回路では、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１についての入力レジスタｒｇ１４、及び入力レジスタｒｇ１４を選択するセレクタＳＥＬ１４が設けられる。また変数σ系列のシフトレジスタＳＲ１，変数λ系列のシフトレジスタＳＲ２が設けられる。さらに加算器１１，１２、乗算器ＭＬ１１，ＭＬ１２，ＭＬ１３、レジスタｒｇ１１，ｒｇ１２，ｒｇ１３、セレクタＳＥＬ１１，ＳＥＬ１２が設けられる。
この回路の場合、回路規模の大きなガロア体演算回路（乗算器ＭＬ１１，ＭＬ１２，ＭＬ１３）が３つのみで構成され、回路規模の面で優れている。但し次に述べる消失訂正はサポートされていない。
【０００９】
【発明が解決しようとする課題】
リードソロモン符号の訂正処理において、あらかじめ符号語中のシンボルの誤り位置を示す消失位置のガロア体表現が得られた場合には、訂正可能数をＮ−Ｋまで引き上げる事が出来る。これを消失訂正という。消失位置符号の数、Ｎｅｒａｓ（消失誤りの数）とＮｅｒｒ（誤りの数）には次の（数４）のような関係が成り立つ。
【数４】
2004260646.tif 000006
【００１０】
消失訂正のみを行うには、まず次の（数５）のような消失位置多項式Λ（ｘ）を消失位置のガロア体表現から計算する。
【数５】
2004260646.tif 000007
消失訂正のみを行う場合は、これを上記（数２）のσ（ｘ）に置き換えて誤り数値多項式を導けばよい。
【００１１】
通常の誤り訂正と消失訂正を同時に行う場合には、シンドロームと消失位置多項式Λから誤り位置多項式σを導出する。
上記非特許文献２には、従来のアルゴリズムにあまり変更が加えられない形で消失訂正も行うことの出来る、修正バーレカンプアルゴリズムが提示されている。
上記非特許文献２に示されている、通常の誤り訂正と消失訂正を同時に行うの場合の復号装置全体の構成は図８のようになる。
シンドローム計算部３１は、入力データｃからシンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１の計算を行う。
消失位置多項式計算部３２は、入力される消失フラグｅ０、ｅ１、・・・、ｅ２ｔ−１から上記（数５）により消失位置多項式Λ（ｘ）を得る。
誤り位置多項式計算部３３は、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置多項式Λ（ｘ）から誤り位置多項式σ（ｘ）を導出する。
誤り数値多項式計算部３４は、誤り位置多項式σを用いて上記（数３）により誤り数値多項式Ω（ｘ）を得る。
チェンサーチ部３５は、誤り位置多項式σと誤り数値多項式Ω（ｘ）から誤り数値を得る。そして入力データｃは遅延バッファ３６により所定タイミング遅延されて演算器３７に入力されるが、この演算器３７においてチェンサーチ部３５による誤り数値との演算が行われ、復号データｃ’として出力される。
【００１２】
このような構成で通常の誤り訂正と消失訂正が同時に行われる。ところが、このような構成では、誤り位置多項式σ（ｘ）の導出以前に、消失フラグｅ０、ｅ１、・・・、ｅ２ｔ−１から消失位置多項式Λ（ｘ）を導出する必要がある。また消失位置多項式Λ（ｘ）は消失フラグが全て入力されてからでなければ計算できないため、シンドローム計算後の処理となる。従って、この図８の構成をとると、シンドローム計算終了後に消失位置多項式を計算する演算ステップが必要になり、必要な演算ステップ数が増大してしまうという問題が生ずる。
【００１３】
【課題を解決するための手段】
本発明はこのような問題点に鑑みてなされたもので、従来のＢｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙアルゴリズムの計算回路から少ない変更により、消失訂正を行うことのできる復号装置、及び誤り位置多項式計算方法を実現することを目的とする。
【００１４】
このため本発明の復号装置は、入力データについてシンドローム計算を行うシンドローム計算手段と、入力された消失フラグから消失位置情報を計算する消失位置情報計算手段と、上記シンドローム計算手段で得られたシンドロームと、上記消失位置情報計算手段で得られた消失位置情報に基づいて誤り位置多項式を計算する誤り位置多項式計算手段と、上記誤り位置多項式から誤り数値多項式を計算する誤り数値多項式計算手段と、上記誤り位置多項式及び誤り数値多項式から誤り数値を算出し、入力データについて訂正処理を行う訂正処理手段とを備える。
また、上記誤り位置多項式計算手段は、処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つバッファ部と、処理ステップ数及び消失データ数により上記バッファ部と演算器の結合を切り替えるセレクタとを有し、消失位置のガロア体表現及びシンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める構成とされる。
【００１５】
本発明の誤り位置多項式計算方法は、入力データから計算されたシンドロームと、入力された消失フラグから計算された消失位置情報とを用いて、誤り位置多項式を計算する。
特に、演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づいて制御することで、消失位置のガロア体表現及びシンドロームから、誤り位置情報を解として持つ誤り位置多項式を求める。
本発明のプログラムは、このような誤り位置多項式計算方法を実現するプログラムである。
【００１６】
即ち、従来、消失訂正をサポートした場合において、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置多項式Λ（ｘ）に基づいて誤り位置多項式σ（ｘ）を計算していたところ、上記本発明によれば、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１に基づいて誤り位置多項式σ（ｘ）を計算するものとなる。
また、演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づき制御することによって、消失位置情報からの消失位置多項式の導出と誤り位置多項式の導出について、同一の回路（誤り位置多項式計算手段）において実現する。
【００１７】
【発明の実施の形態】
以下、本発明の実施の形態の復号装置及び誤り位置多項式計算方法について、図１〜図６を参照しながら説明する。
本実施の形態の復号装置は、回路規模や演算ステップ数を抑えながらも、消失位置訂正をサポートできるものである。
【００１８】
図１は、本例のリードソロモン符号の復号装置の全体を示している。
シンドローム計算部１は、入力データｃからシンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１の計算を行う。
消失位置情報計算部２は、入力される消失フラグｅ０、ｅ１、・・・、ｅ２ｔ−１から消失位置情報をＥｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１を計算する。
誤り位置多項式計算部３は、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置情報をＥｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１から誤り位置多項式σ（ｘ）を導出する。
誤り数値多項式計算部４は、誤り位置多項式σを用いて上記（数３）により誤り数値多項式Ω（ｘ）を得る。
チェンサーチ部５は、誤り位置多項式σと誤り数値多項式Ω（ｘ）から誤り数値を得る。そして入力データｃは遅延バッファ６により所定タイミング遅延されて演算器７に入力されるが、この演算器７においてチェンサーチ部５による誤り数値との演算が行われ、復号データｃ’として出力される。
【００１９】
このような本例の復号装置において、上述した図８の復号装置と異なる点は次の▲１▼、▲２▼の２つの点である。
▲１▼  図８ではシンドロームの計算と並行して消失位置多項式計算部３２で消失位置多項式Λ（ｘ）を求めていたところ、本例の図１においては、消失位置情報計算部２として、消失フラグｅ０、ｅ１、・・・、ｅ２ｔ−１を、消失位置をガロア体の冪表現である消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１に変換するモジュールが設けられている。
▲２▼  図８では誤り位置多項式計算部３３で、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置多項式Λ（ｘ）から誤り位置多項式σ（ｘ）を導出したが、本例の図１においては、誤り位置多項式計算部３では、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置情報をＥｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１から誤り位置多項式σ（ｘ）を導出する。
【００２０】
まず▲１▼に挙げた消失位置情報計算部２は、このモジュールで得られた消失位置のガロア体表現（Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１）を、▲２▼に挙げた誤り位置多項式計算部３、即ち今回改良された修正バーレカンプアルゴリズムを実行するモジュールに送るものである。
消失位置情報計算部２は、消失位置多項式を計算する代わりに、消失フラグ（消失位置）ｅ０、ｅ１、・・・、ｅ２ｔ−１から、消失位置のガロア体表現である消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１を、
【数６】
2004260646.tif 000008
と計算する。ここでαはガロア体の原始元（ｐｒｉｍｉｔｉｖｅ  ｅｌｅｍｅｎｔ）である。消失位置多項式の計算には多くの演算ステップを要するが、各消失位置のガロア体表現は、消失位置より１演算ステップで計算することができ、従って消失位置情報計算部２は簡便な回路になる。
【００２１】
▲２▼として挙げた誤り位置多項式計算部３では、入力として、シンドロームと消失位置情報が与えられた場合に、バーレカンプアルゴリズムを基にして改善された図４〜図６のアルゴリズムで誤り位置多項式σ（ｘ）を導出する。またそれを実現する回路構成は図２のようになる。
まず図２の構成を説明する。
【００２２】
図２の回路は、以下のような部分より構成される。
・処理ステップ数により更新される２つのカウンタ値（Ｃ１，Ｃ２）
・カウンタ値により制御されたバッファ
・ガロア体乗算器
・ガロア体乗算器の切り替え回路
・シンドローム選択回路
これら各部について説明する。
【００２３】
＜処理ステップ数により更新される２つのカウンタ値（Ｃ１，Ｃ２）＞
このカウンタ値Ｃ１，Ｃ２は、図２の回路上に現れるものではないが、この回路の動作を制御する値とされるものである。後述する図４〜図６のアルゴリズムにおいて、変数ｊ，ｉとしてカウンタ値Ｃ１，Ｃ２が設定される。Ｃ１＝ｊ、Ｃ２＝ｉとなる。
【００２４】
このカウンタ値Ｃ１，Ｃ２という２つのカウンタ値は以下のＩ，ＩＩ，ＩＩＩ，ＩＶのような処理を行う。Ｃ１ｎ，Ｃ２ｎをカウンタ値を保持するためのレジスタとする。
Ｉ．Ｃ１ｎ＝０、Ｃ２ｎ＝０
ＩＩ．Ｃ１＝Ｃ１ｎ、Ｃ２＝Ｃ２ｎ
ＩＩＩ．Ｃ１＝Ｃ２ならＣ１ｎ＝Ｃ１＋１、Ｃ２ｎ＝０
Ｃ１＝Ｃ２でなければＣ１ｎ＝Ｃ１、Ｃ２ｎ＝Ｃ２＋１
ＩＶ．ＩＩへ
このＩ〜ＩＶについて、処理開始時にＩを実行し、１処理ステップ毎にＩＩ〜ＩＶの動作を繰り返す。
【００２５】
これにより具体的には、各カウンタ値「Ｃ１，Ｃ２」は処理ステップ毎に次の各値に遷移する。
「Ｃ１，Ｃ２」＝「０，０」→「１，０」→「１，１」→「２，０」→「２，１」→「２，２」→「３，０」→・・・
但しこれは一例であり、カウンタ値Ｃ１、Ｃ２は後述する図４から図６で説明するように、変数ｊ，ｉとしてカウントする値の範囲が設定される。
【００２６】
＜カウンタ値により制御されたバッファ＞
カウンタ値により制御されたバッファとは、図２のバッファ部Ｂｆ１，Ｂｆ２のことである。
バッファ部Ｂｆ１、Ｂｆ２はそれぞれ、処理開始からの処理ステップ数を元に入力を切り替えるセレクタを持つシフトレジスタとして構成される。
即ちバッファ部Ｂｆ１は、レジスタσｒｇ（０）〜σｒｇ（２ｔ−１）によりシフトレジスタが構成されるとともに、各レジスタσｒｇ（０）〜σｒｇ（２ｔ−２）に対して、その前段のレジスタの出力と、バッファ部Ｂｆ１に入力される演算結果とを選択して入力するセレクタＳＬσ（０）〜ＳＬσ（２ｔ−２）が設けられる。
またバッファ部Ｂｆ２は、レジスタλｒｇ（０）〜λｒｇ（２ｔ−１）によりシフトレジスタが構成されるとともに、各レジスタλｒｇ（１）〜σｒｇ（２ｔ−２）に対して、その前段のレジスタの出力と、バッファ部Ｂｆ２に入力される演算結果とを選択して入力するセレクタＳＬλ（１）〜ＳＬλ（２ｔ−２）が設けられる。
【００２７】
またバッファ部Ｂｆ１には、加算器ＡＤ１の演算結果σｉｔｅｒが入力される。
バッファ部Ｂｆ２に対しては、入力段にセレクタＳＥＬ０、ＳＥＬ２が設けられる。セレクタＳＥＬ０は、バッファ部Ｂｆ１のレジスタσｒｇ（０）の値σｒｅｇと、バッファ部Ｂｆ２のレジスタλｒｇ（０）の値λｒｅｇとを選択する。セレクタＳＥＬ２は、加算器ＡＤ１の演算結果σｉｔｅｒと、セレクタＳＥＬ０の選択値とを選択して値λｉｔｅｒ＋１としてバッファ部Ｂｆ２に入力する。
【００２８】
各シフトレジスタレジスタ（σｒｇ（０）〜σｒｇ（２ｔ−１）、λｒｇ（０）〜λｒｇ（２ｔ−１））は、カウンタ値Ｃ２の値により、入力を前段のレジスタと、バッファに入力される演算結果（σｉｔｅｒ、λｉｔｅｒ＋１）とから選択することになる。つまりセレクタＳＬσ（０）〜ＳＬσ（２ｔ−２）及びセレクタＳＬλ（１）〜ＳＬλ（２ｔ−２）はカウンタ値Ｃ２によってその選択状態が制御される。
なお、このような構成は、上記図７の回路に比べ必要な処理ステップ数を削減するものとなる。
【００２９】
＜ガロア体乗算器＞
ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３が設けられる。これらガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３は、２個の任意のガロア体の元を乗算する。
【００３０】
＜ガロア体乗算器切り替え回路＞
まずガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３を含む回路系は次のように構成されている。
ガロア体乗算器ＭＬ３はセレクタＳＥＬ６によって選択されたシンドロームＳと加算器ＡＤ１の演算結果σｉｔｅｒを乗算して乗算結果ＭＵＬ３を出力する。ガロア体乗算器ＭＬ３の出力ＭＵＬ３は加算器ＡＤ２に供給される。
加算器ＡＤ２はレジスタｒｇ６とガロア体乗算器ＭＬ３の出力を加算して出力する（δｋ＋１）。またこの加算器ＡＤ２の出力δｋ＋１はレジスタｒｇ６に保持される。つまりレジスタｒｇ６は値δｋ＋１を保持するレジスタとなる。
加算器ＡＤ２の出力δｋ＋１はセレクタＳＥＬ３に供給される。セレクタＳＥＬ３は、出力δｋ＋１と、レジスタｒｇ５の値を選択してレジスタｒｇ５に入力する。このレジスタｒｇ５は値δを保持するレジスタとなる。
レジスタｒｇ５の値δはセレクタＳＥＬ１，ＳＥＬ４に供給される。
セレクタＳＥＬ４は、値δと消失位置の値Ｅｒを選択してガロア体乗算器ＭＬ２に供給する。ガロア体乗算器ＭＬ２では、セレクタＳＥＬ４からの値とバッファ部Ｂｆ２からの値λｒｅｇを乗算し、乗算結果ＭＵＬ２を加算器ＡＤ１に供給する。
セレクタＳＥＬ１は、レジスタｒｇ５からの値δと、レジスタｒｇ７に保持された値γを選択して、レジスタｒｇ７に入力する。レジスタｒｇ７は値γを保持するレジスタとなる。
レジスタｒｇ７の値γはセレクタＳＥＬ５に供給される。セレクタＳＥＬ５は値γと、値「１」を選択してガロア体乗算器ＭＬ１に出力する。
ガロア体乗算器ＭＬ１では、セレクタＳＥＬ５からの値とバッファ部Ｂｆ１からの値σｒｅｇを乗算し、乗算結果ＭＵＬ１を加算器ＡＤ１に供給する。
【００３１】
このような回路系において、ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３の入出力の切り替えはカウンタ値Ｃ１と、消失フラグの立っているデータの数Ｅｒａｓ＿ｎｕｍを比較することによって行われる。
３つの各ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３については、それぞれ上記セレクタＳＥＬ５，ＳＥＬ４，ＳＥＬ６によって図３に示すように接続の切り替えが行われる。
【００３２】
まずカウンタ値Ｃ１と、消失フラグの立っているデータの数Ｅｒａｓ＿ｎｕｍの比較結果がＣ１＜Ｅｒａｓ＿ｎｕｍの場合は、図３（ａ）のようになる。
ガロア体乗算器ＭＬ１には、値「１」とバッファ部Ｂｆ１からの値σ（σｒｅｇ）が入力され、その乗算結果ＭＵＬ１を出力する。
ガロア体乗算器ＭＬ２には、カウンタ値Ｃ１に基づく消失位置情報の値ＥｒＣ１とバッファ部Ｂｆ２からの値λ（λｒｅｇ）が入力され、その乗算結果ＭＵＬ２を出力する。
ガロア体乗算器ＭＬ３には、シンドロームＳと加算器ＡＤ１の演算結果（σｉｔｅｒ＝ＭＵＬ１＋ＭＵＬ２）が入力され、その乗算結果ＭＵＬ３を出力する。
【００３３】
カウンタ値Ｃ１と、消失フラグの立っているデータの数Ｅｒａｓ＿ｎｕｍの比較結果がＣ１≧Ｅｒａｓ＿ｎｕｍの場合は、図３（ｂ）のようになる。
ガロア体乗算器ＭＬ１には、値γとバッファ部Ｂｆ１からの値σ（σｒｅｇ）が入力され、その乗算結果ＭＵＬ１を出力する。
ガロア体乗算器ＭＬ２には、値δとバッファ部Ｂｆ２からの値λ（λｒｅｇ）が入力され、その乗算結果ＭＵＬ２を出力する。
ガロア体乗算器ＭＬ３には、シンドロームＳと加算器ＡＤ１の演算結果（σｉｔｅｒ＝ＭＵＬ１＋ＭＵＬ２）が入力され、その乗算結果ＭＵＬ３を出力する。
このようにガロア体乗算器切り替え回路が構成される。
【００３４】
＜シンドローム選択回路＞
シンドローム選択回路は、入力されるシンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１を保持するレジスタｒｇ８と、レジスタｒｇ８の値（Ｓ０、Ｓ１、・・・、Ｓ２ｔ−１）を選択したシンドロームＳをガロア体乗算器ＭＬ３に供給するセレクタＳＥＬ６により構成される。
セレクタＳＥＬ６は、カウンタ値Ｃ２、Ｃ１の値から計算した値をインデックスとして、そのインデックスに対応したシンドロームＳを出力する。つまりインデックスとしてｉが与えられた場合は、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１のうちでＳｉを出力する回路である。
【００３５】
以下、このような図２の回路で実現できる本例のアルゴリズムを図４〜図６で説明する。
図１で説明したように、図２の回路とされる誤り位置多項式計算部３には、入力としては、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１が与えられる。
その場合に、誤り位置多項式σ（ｘ）を導出するアルゴリズムが図４〜図６のようになる。
なお上記もしたが、Ｅｒａｓ＿ｎｕｍは前段の消失位置計算ブロックより与えられる消失の起こった位置の数である。
またｔは先の説明にあるように、符号長をＮ、送信情報語長をＫとした場合に、Ｎ−Ｋ＝２ｔ−１で与えられる。
σｒｅｇはσを保存するパラメータであり、λｒｅｇはλを保存するパラメータである。σｉｔｅｒ、λｉｔｅｒは繰り返し回数の変数ｉｔｅｒの値に応じ、それぞれσ０〜σ２ｔ−１、λ０〜λ２ｔ−１から選択される値である。
【００３６】
図５のステップＦ１０１では初期化が行われる。即ちσ０〜σ２ｔ−１、λ０〜λ２ｔ−１は全て「０」にセットされる。また処理に用いる内部変数Ｌ＝０とされる。さらにσ０＝λ０＝γ＝１とされ、δ＝Ｓ０とされる。具体的には図２のバッファ部Ｂｆ１，Ｂｆ２の各レジスタ、及び値δを保持するレジスタｒｇ５，値γを保持するレジスタｒｇ７の値がこのように初期化される。
【００３７】
ステップＦ１０２で、カウント値Ｃ１に相当する変数ｊとして、０から消失位置の数Ｅｒａｓ＿ｎｕｍをセットし、変数ｊのループ回数、つまりカウント値Ｃ１のカウント範囲を規定する。
ステップＦ１０３では、繰り返し回数の変数ｉｔｅｒにｊ＋１の値をセットし、またレジスタｒｇ６における値δｋ＋１を「０」とする。
またＦ１０４で、カウント値Ｃ２に相当する変数ｉとして、０から値ｉｔｅｒをセットし、変数ｉのループ回数、つまりカウント値Ｃ２のカウント範囲を規定する。
【００３８】
ステップＦ１０５では、値σｒｅｇとして値σ０を設定する。また値λｒｅｇとして値λ０を設定する。
そしてステップＦ１０６で変数ｋについて０から２ｔ−１をセットし、変数ｋのループ回数を規定する。
そしてステップＦ１０７で、値σｋを値σｋ＋１とし、値λｋを値λｋ＋１とする。これをステップＦ１０８でｋのループ終了とされるまで実行する。
つまり、この処理により、バッファ部Ｂｆ１，Ｂｆ２の各シフトレジスタの値が値ｋのループ回数だけシフトされるものとなる。
【００３９】
ステップＦ１０９では、ガロア体乗算器ＭＬ１，ＭＬ２の乗算と、その乗算結果ＭＵＬ１、ＭＵＬ２の加算器ＡＤ１での加算が行われて演算結果σｉｔｅｒが得られる。
このときステップＦ１０２でのカウント値Ｃ１（＝ｊの値）の設定により、Ｃ１＜Ｅｒａｓ＿ｎｕｍ、つまり図３（ａ）の切換状態であることで、ガロア体乗算器ＭＬ１ではＭＵＬ１＝１×σｒｅｇ、ガロア体乗算器ＭＬ２ではＭＵＬ２＝Ｅｒｊ×λｒｅｇの乗算が行われ、加算器ＡＤ１での演算結果σｉｔｅｒは、σｉｔｅｒ＝１×σｒｅｇ＋Ｅｒｊ×λｒｅｇとなる。
【００４０】
ステップＦ１１０では値λｉｔｅｒ＋１が上記演算結果σｉｔｅｒとされる。つまり値σｉｔｅｒは、バッファ部Ｂｆ１に入力されるとともに、セレクタＳＥＬ２が値σｉｔｅｒを選択することで、バッファ部Ｂｆ２にも値σｉｔｅｒが入力される。
ステップＦ１１１では、ガロア体乗算器ＭＬ３の乗算及び加算器ＡＤ２の加算が行われ、レジスタｒｇ６の値δｋ＋１が更新される。
即ちガロア体乗算器ＭＬ３では、上記演算結果σｉｔｅｒと、セレクタＳＥＬ６で選択されたシンドロームＳｊ＋１−ｉについて乗算を行って乗算結果ＭＵＬ３（＝σｉｔｅｒ×Ｓｊ＋１−ｉ）を出力し、加算器ＡＤ２では、乗算結果ＭＵＬ３とレジスタｒｇ６の値δｋ＋１を加算する。そしてこの加算結果（δｋ＋１＋σｉｔｅｒ×Ｓｊ＋１−ｉ）がレジスタｒｇ６の値δｋ＋１とされる。
【００４１】
以上の処理は変数ｉのループ終了まで行われ、終了したらステップＦ１１２からＦ１１３に進み、値δが値δｋ＋１に更新される。即ちセレクタＳＥＬ３が値δｋ＋１を選択してレジスタｒｇ５の値δを更新する。
変数ｊのループが終了したら、ステップＦ１１４から図５のステップＦ１１５に進む。
【００４２】
ステップＦ１１５では、カウント値Ｃ１に相当する変数ｊとして、消失位置の数Ｅｒａｓ＿ｎｕｍから２ｔ−１をセットし、変数ｊのループ処理を規定する。
ステップＦ１１６では、繰り返し回数の変数ｉｔｅｒにｊ＋１の値をセットし、またレジスタｒｇ６における値δｋ＋１を「０」とする。
またＦ１１７で、カウント値Ｃ２に相当する変数ｉとして、０から値ｉｔｅｒをセットし、変数ｉのループ処理を規定する。
【００４３】
ステップＦ１１８では、値σｒｅｇとして値σ０を設定する。また値λｒｅｇとして値λ０を設定する。
そしてステップＦ１１９で変数ｋについて０から２ｔ−１をセットし、変数ｋのループ処理を規定する。
そしてステップＦ１２０で、値σｋを値σｋ＋１とし、値λｋを値λｋ＋１とする。これをステップＦ１２１でｋのループ終了とされるまで実行する。
つまり、この処理により、バッファ部Ｂｆ１，Ｂｆ２の各シフトレジスタの値が値ｋのループ回数だけシフトされるものとなる。
【００４４】
ステップＦ１２２では、ガロア体乗算器ＭＬ１，ＭＬ２の乗算と、その乗算結果ＭＵＬ１、ＭＵＬ２の加算器ＡＤ１での加算が行われて演算結果σｉｔｅｒが得られる。
このときはステップＦ１１５でのカウント値Ｃ１（＝ｊの値）の設定により、Ｃ１≧Ｅｒａｓ＿ｎｕｍ、つまり図３（ｂ）の切換状態となっているため、ガロア体乗算器ＭＬ１ではＭＵＬ１＝γ×σｒｅｇ、ガロア体乗算器ＭＬ２ではＭＵＬ２＝δ×λｒｅｇの乗算が行われ、加算器ＡＤ１の演算結果σｉｔｅｒは、σｉｔｅｒ＝γ×σｒｅｇ＋δ×λｒｅｇとなる。
【００４５】
ステップＦ１２３では、δ＝０であるか、或いは制御変数Ｌについて２Ｌ＞ｊ−Ｅｒａｓ＿ｎｕｍであるかを判別する。
このいずれかの条件が満たされていれば、ステップＦ１２４で値λｉｔｅｒ＋１が値σｒｅｇとされる。
この場合、上記演算結果σｉｔｅｒは、バッファ部Ｂｆ１に入力される。またセレクタＳＥＬ０、ＳＥＬ２がバッファ部Ｂｆ１の値σｒｅｇを選択することで、バッファ部Ｂｆ２に値σｒｅｇが入力される。
【００４６】
一方、ステップＦ１２３の条件が満たされていない場合は、ステップＦ１２５で値λｉｔｅｒ＋１が値λｒｅｇとされる。
この場合、上記演算結果σｉｔｅｒは、バッファ部Ｂｆ１に入力される。またセレクタＳＥＬ０、ＳＥＬ２がバッファ部Ｂｆ２の値λｒｅｇを選択することで、バッファ部Ｂｆ２に値λｒｅｇが入力される。
【００４７】
ステップＦ１２６では、ガロア体乗算器ＭＬ３の乗算及び加算器ＡＤ２の加算が行われ、レジスタｒｇ６の値δｋ＋１が更新される。
即ちガロア体乗算器ＭＬ３では、上記演算結果σｉｔｅｒと、セレクタＳＥＬ６で選択されたシンドロームＳｊ＋１−ｉについて乗算を行って乗算結果ＭＵＬ３（＝σｉｔｅｒ×Ｓｊ＋１−ｉ）を出力し、加算器ＡＤ２では、乗算結果ＭＵＬ３とレジスタｒｇ６の値δｋ＋１を加算する。そしてこの加算結果（δｋ＋１＋σｉｔｅｒ×Ｓｊ＋１−ｉ）がレジスタｒｇ６の値δｋ＋１とされる。
【００４８】
以上の処理は変数ｉのループ終了まで行われ、終了したらステップＦ１２７から図６のステップＦ１２８に進む。そして、δ＝０であるか、或いは２Ｌ＞ｊ−Ｅｒａｓ＿ｎｕｍであるかを判別する。
いずれかの条件が満たされていればステップＦ１３０に進む。
条件が満たされていなければ、ステップＦ１２９で、変数Ｌを、ｊ−Ｅｒａｓ＿ｎｕｍ＋１−Ｌの値とし、また値γを値δに更新する。値γについては、セレクタＳＥＬ１がレジスタｒｇ５の値δを選択し、レジスタｒｇ７を更新することになる。
【００４９】
ステップＦ１３０では、値δが値δｋ＋１に更新される。即ちセレクタＳＥＬ３が値δｋ＋１を選択してレジスタｒｇ５の値δを更新する。
このステップＦ１１６〜Ｆ１３１の処理を変数ｊのループ終了まで実行し、終了したらステップＦ１３２に進む。この時点でバッファ部Ｂｆ１としてのシフトレジスタσｒｇ（０）〜σｒｇ（２ｔ−１）に保持されている値として、値σ０〜σ２ｔ−１を出力して処理が終了される。
以上の処理で誤り位置多項式計算部３から誤り位置多項式σ（ｘ）が出力されるものとなる。
【００５０】
即ち本実施の形態によれば、、従来、消失訂正をサポートした場合において、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置多項式Λ（ｘ）に基づいて誤り位置多項式σ（ｘ）を計算していたところを、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１に基づいて誤り位置多項式σ（ｘ）を計算するものとなる。
また、演算の途中結果を保持するバッファＢｆ１，Ｂｆ２と演算器（ガロア体乗算器ＭＬ１，ＭＬ２，ＭＬ３）の結合の切り替えを、消失した受信語の数（Ｅｒａｓ＿ｎｕｍ）と処理ステップ数（カウント値Ｃ１）に基づき制御することによって、消失位置情報からの消失位置多項式の導出と誤り位置多項式の導出について、図２の回路のみで実現できる。
【００５１】
このような手法により、Ｂｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙアルゴリズムの計算回路から少ない変更で消失訂正を行うことのできる復号装置を構成することができる。
またガロア体乗算器の増加を伴わず、回路規模の増大も最小限に抑えることができる。
また、受信符号語における消失数に関わらず、必要最小限かつ固定のステップ数での処理が実現でき、復号遅延を最小限に抑えることができる。
【００５２】
本発明の復号装置は、例えば図２の回路構成により例えば図４〜図６のアルゴリズムで誤り位置多項式σ（ｘ）を得る誤り位置多項式計算部３を用いた図１の構成の復号装置である。
また本発明の誤り位置多項式計算方法或いはプログラムは、一例として上記図４〜図６のようなアルゴリズムによる計算方法、或いはその計算方法を実行させるプログラムである。
即ち上記実施の形態は、本発明の復号装置、誤り位置多項式計算方法、及びプログラムに相当するものであるが、本発明はこの実施の形態の例に限定されず、その要旨の範囲内で各種の変形例が考えられる。
【００５３】
本発明のプログラムについては、復号装置含む電子機器（例えばディスクドライブ装置、テープ記録再生装置、通信装置その他）内のＲＯＭ、不揮発性メモリ、又はＲＡＭに一時的あるいは永続的に格納（記録）しておくことができる。また、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＭＯ（Ｍａｇｎｅｔ  Ｏｐｔｉｃａｌ）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくこともできる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウェアとして提供することができ、上記ディスクドライブ装置等の電子機器の設計／製造などにも利用できる。
なお、プログラムは、上記のようなリムーバブルな記録媒体からインストールする他、プログラムを記憶しているサーバなどから、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワークを介してダウンロードすることもできる。
【００５４】
【発明の効果】
以上の説明からわかるように本発明によれば、シンドロームＳ０、Ｓ１、・・・、Ｓ２ｔ−１と消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１に基づいて誤り位置多項式σ（ｘ）を計算する。また消失位置情報計算手段においては、消失位置のガロア体表現である消失位置情報Ｅｒ０、Ｅｒ１、・・・、Ｅｒ２ｔ−１は消失フラグｅ０、ｅ１、・・・、ｅ２ｔ−１から簡単な計算で求められる。また誤り位置多項式計算手段では、演算の途中結果を保持するバッファと演算器の結合の切り替えを、消失した受信語の数と処理ステップ数に基づき制御することによって、消失位置情報からの消失位置多項式の導出と誤り位置多項式の導出を実現できる。
これによって、従来のＢｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙアルゴリズムの計算回路から少ない変更により、消失訂正を行うことのできる復号装置を構成できるという効果がある。またこれは、ガロア体乗算器の増加を伴わず、回路規模の増大も最小限に抑えることができる。
さらに受信符号語における消失数に関わらず、必要最小限かつ固定のステップ数での処理が実現でき、復号遅延を最小限に抑えることができる。
【図面の簡単な説明】
【図１】本発明の実施の形態の復号装置のブロック図である。
【図２】実施の形態の誤り位置多項式計算部の回路図である。
【図３】実施の形態のガロア体乗算器の切換動作の説明図である。
【図４】実施の形態の誤り位置多項式計算処理のフローチャートである。
【図５】実施の形態の誤り位置多項式計算処理のフローチャートである。
【図６】実施の形態の誤り位置多項式計算処理のフローチャートである。
【図７】バーレカンプアルゴリズム実装回路の回路図である。
【図８】消失訂正をサポートした復号装置のブロック図である。
【符号の説明】
１  シンドローム計算部、２  消失位置情報計算部、３  誤り位置多項式計算部、４  誤り数値多項式計算部、５  チェンサーチ部、６  遅延バッファ、７  演算部、ＭＬ１，ＭＬ２，ＭＬ３  ガロア体乗算器
【図１】
2004260646.tif 000009
【図２】
2004260646.tif 000010
【図３】
2004260646.tif 000011
【図４】
2004260646.tif 000012
【図５】
2004260646.tif 000013
【図６】
2004260646.tif 000014
【図７】
2004260646.tif 000015
【図８】
2004260646.tif 000016