(57)【特許請求の範囲】
【請求項１】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データ中の拡張シンボルの値は、拡張シンボル以外のシンボルの値を加算して得たものであり、
上記第８のステップは、上記誤り位置多項式の次数と、上記消失数および上記入力データのパリティシンボル数を使用して求められた数とを比較して訂正可能判定をする誤り訂正符号の復号方法。
【請求項２】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データ中の拡張シンボルの値は、拡張シンボル以外のシンボルの値を加算して得たものであり、
上記第８のステップは、上記入力データのパリティシンボル数と、上記誤り位置多項式の次数および上記消失数を使用して求められた数とを比較して訂正可能判定をする誤り訂正符号の復号方法。
【請求項３】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データ中の拡張シンボルの値は、拡張シンボル以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものであり、
上記第８のステップは、拡張シンボル位置の消失が存在するか否かを拡張シンボル位置の消失フラグから判定し、その後に上記拡張シンボル位置が誤り位置に含まれているか否かを判定し、その後にさらに上記誤り位置多項式の次数と、上記消失数および上記入力データのパリティシンボル数を使用して求められた数とを比較することで訂正可能判定をする誤り訂正符号の復号方法。
【請求項４】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データ中の拡張シンボルの値は、拡張シンボル以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものであり、
上記第８のステップは、上記拡張シンボル位置が誤り位置に含まれているか否かを判定し、その後に上記拡張シンボル位置の消失が存在するか否かを拡張シンボル位置の消失フラグから判定し、その後にさらに上記誤り位置多項式の次数と、上記消失数および上記入力データのパリティシンボル数を使用して求められた数とを比較することで訂正可能判定をする誤り訂正符号の復号方法。
【請求項５】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データは、上記拡張シンボルとして、第１拡張シンボルおよび第２拡張シンボルを含み、
上記第１拡張シンボルの値は、拡張シンボル以外のシンボルの値を加算して得たものであり、
上記第２拡張シンボルの値は、拡張シンボル以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものであり、
上記第８のステップは、上記誤り位置多項式の次数と、上記消失数および上記入力データのパリティシンボル数を使用して求められた数とを比較することで訂正可能判定をする誤り訂正符号の復号方法。
【請求項６】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データは、上記拡張シンボルとして、第１拡張シンボルおよび第２拡張シンボルを含み、
上記第１拡張シンボルの値は、拡張シンボル以外のシンボルの値を加算して得たものであり、
上記第２拡張シンボルの値は、拡張シンボル以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものであり、
上記第８のステップは、上記入力データのパリティシンボル数と、上記誤り位置多項式の次数および上記消失数を使用して求められた数とを比較することでて訂正可能判定をする誤り訂正符号の復号方法。
【請求項７】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データは、上記拡張シンボルとして、第１拡張シンボルおよび第２拡張シンボルを含み、
上記第１拡張シンボルの値は、拡張シンボル以外のシンボルの値を加算して得たものであり、
上記第２拡張シンボルの値は、拡張シンボル以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものであり、
上記第８のステップは、上記拡張シンボル位置の消失が存在するか否かを拡張シンボル位置の消失フラグから判定し、その後に上記拡張シンボル位置が誤り位置に含まれているか否かを判定し、その後にさらに上記誤り位置多項式の次数と、上記消失数および上記入力データのパリティシンボル数を使用して求められた数とを比較することで訂正可能判定をする誤り訂正符号の復号方法。
【請求項８】
拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、
上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
上記入力データに対応した消失フラグから消失数を求める第３のステップと、
上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、
上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、
上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、
上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、
上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、
上記入力データは、上記拡張シンボルとして、第１拡張シンボルおよび第２拡張シンボルを含み、
上記第１拡張シンボルの値は、拡張シンボル以外のシンボルの値を加算して得たものであり、
上記第２拡張シンボルの値は、拡張シンボル以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものであり、
上記第８のステップは、上記拡張シンボル位置が誤り位置に含まれているか否かを判定し、その後に上記拡張シンボル位置の消失が存在するか否かを拡張シンボル位置の消失フラグから判定し、その後にさらに上記誤り位置多項式の次数と、上記消失数および上記入力データのパリティシンボル数を使用して求められた数とを比較することで訂正可能判定をする誤り訂正符号の復号方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、１シンボルまたは２シンボル拡張した拡張リードソロモン符号等の誤り訂正符号を復号する復号方法に関する。詳しくは、拡張シンボルの通常訂正および消失訂正を行う手段を組み込むことによって、例えば１拡張リードソロモン符号、２拡張リードソロモン符号の１パスでの混合訂正を可能にした誤り訂正符号の復号方法に係るものである。
【０００２】
【従来の技術】
まず、図１９を使用して誤り訂正システムについて説明する。
【０００３】
付加するパリティのシンボル数をｐとして、ｋシンボルの情報Ｉ=（Ｉ0，Ｉ1，・・・，Ｉk-1）を送る場合を考える。ｋシンボルの情報をエンコーダ（符号化ブロック）によって符号化することで、ｐシンボルのパリティが付加されて、長さｎ＝ｋ＋ｐの符号語Ｃ＝（Ｃ0，Ｃ1，・・・，Ｃn-1）が得られる。
【０００４】
符号語はエラーのある伝送路を通り、誤りを含む受信語Ｒ＝（Ｒ0，Ｒ1，・・・，Ｒn-1）として受信される。ｉ番目の誤りをｅiとすれば、Ｒi＝Ｃi＋ｅiとなる。受信された受信語Ｒをデコーダ（復号化ブロック）によって復号化することで、推定された符号語Ｃp＝（Ｃp0，Ｃp1，・・・，Ｃpn-1）が得られ、この符号語Ｃpから推定された情報Ｉp＝（Ｉp0，Ｉp1，・・・，Ｉpk-1）が得られる。
【０００５】
誤り訂正符号として広く使用されている符号にリードソロモン符号がある。リードソロモン符号ではシンボルをｍビットで表現した場合、最大符号長ｎmaxは２m−１である。例えば、シンボルを８ビットで表現した場合、最大符号長ｎmaxは２５５となる。
【０００６】
また、リードソロモン符号の符号長を１シンボル延長する１拡張リードソロモン符号があり、最大符号長ｎmaxは２mとなる。例えば、シンボルを８ビットで表現した場合、最大符号長ｎmaxは２５６となる。１拡張リードソロモン符号ではパリティシンボル数ｐはそのままで、情報シンボルを、リードソロモン符号より１シンボル多く、ｋ＋１シンボルとすることができる。
【０００７】
また、リードソロモン符号の符号長を２シンボル延長する２拡張リードソロモン符号があり、最大符号長ｎmaxは２m＋１となる。例えば、シンボルを８ビットで表現した場合、最大符号長ｎmaxは２５７となる。２拡張リードソロモン符号ではパリティシンボル数ｐはそのままで、情報シンボルを、リードソロモン符号より２シンボル多く、ｋ＋２シンボルとすることができる。
【０００８】
次に、リードソロモン符号の復号方法について説明する。復号法には、受信語Ｒのみから復号化を行う通常訂正と、受信語Ｒと受信語中の誤りのあると思われる位置を示す消失フラグＦ＝（Ｆ0，Ｆ1，・・・，Ｆn-1）を用いて復号化を行う消失訂正と、通常訂正と消失訂正を同時に行う混合訂正の三通りがある。ここでは、図２０〜図２４を使用して、最も汎用的なリードソロモン符号の混合訂正の復号方法について説明する。
【０００９】
なおここで、体ＧＦ(２)＝{０，１}上の原始多項式ｆ(ｘ)に対して、ｆ(ｘ)＝０の根をαとし、ＧＦ(２)の拡大体を構成する。このとき、原始多項式ｆ(ｘ)の次数をｍとすると、１シンボルはｍビットとなり、拡大体ＧＦ(２m)は、（１）式で表される。
【００１０】
【数１】
0004423519.tif 000002
【００１１】
また、ここで使用するリードソロモン符号の生成多項式ｇ(ｘ)は、（２）式で表される。
【００１２】
【数２】
0004423519.tif 000003
【００１３】
図２０は、リードソロモン符号の復号化のフローチャートを示している。
【００１４】
まず、ステップ１００では、受信語Ｒ＝（Ｒ0，Ｒ1，・・・，Ｒn-1）と消失フラグＦ＝（Ｆ0，Ｆ1，・・・，Ｆn-1）が与えられる。消失フラグＦとは、受信語Ｒ中で誤りがあると予測される位置に対応しては１を、それ以外の誤りがないと予測される位置に対応しては０を設定したフラグである。
【００１５】
次に、ステップ１０１で、消失数εを、（３）式により求めると共に、消失位置多項式Ｅ(ｘ)を（４）式により求める。
【００１６】
【数３】
0004423519.tif 000004
【００１７】
次に、ステップ１０２で、（５）式に示すようなパリティ検査行列Ｈを用いて、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を、（６）式から求める。シンドロームＳの計算方法は、図２１を用いて後で説明する。そして、（７）式に示すようなシンドローム多項式Ｓ(ｘ)を求める。
【００１８】
【数４】
0004423519.tif 000005
【００１９】
次に、ステップ１０３で、消失位置多項式Ｅ(ｘ)およびシンドローム多項式Ｓ(ｘ)を用いて、（８）式に示すように、修正シンドローム多項式Ｓm(ｘ)を求める。
【００２０】
【数５】
0004423519.tif 000006
【００２１】
次に、ステップ１０４で、修正シンドローム多項式Ｓm(ｘ)を用いて、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を求める。誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)の計算方法は、図２２を用いて後で説明する。
【００２２】
次に、ステップ１０５で、degω(ｘ)＜degσ(ｘ)の条件を判定し、偽ならばステップ１１０に進んでエラー信号を出力して終了し、真ならばステップ１０６に進む。ここで、degω(ｘ)は誤り評価多項式ω(ｘ)の次数であり、degσ(ｘ)は誤り位置多項式σ(ｘ)の次数である。
【００２３】
ステップ１０６では、（９）式の条件を判定し、偽ならばステップ１１０に進んでエラー信号を出力して終了し、真ならばステップ１０７に進む。なお、（９）式の右辺のカッコは、小数部分を切り捨てることを意味している。以下の式においても同様である。
【００２４】
【数６】
0004423519.tif 000007
【００２５】
ステップ１０７では、誤り位置多項式σ(ｘ)を使用して誤り位置を検出する。誤り位置の計算方法は、図２３を用いて後で説明する。そして、ステップ１０８で、＃roots＝degσ(ｘ)の条件を判定し、偽ならばステップ１１０に進んでエラー信号を出力して終了し、真ならばステップ１０９に進む。ここで、＃rootsはステップ１０７で検出した誤り位置の数である。
【００２６】
ステップ１０９では、ステップ１０４で求められた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、ステップ１０７で検出した誤り位置ｉとから、位置ｉでの誤り値ｅiを計算し、受信語Ｒと誤り位置ｉ、誤り値ｅiから、推定された情報Ｉp＝（Ｃp0，Ｃp1，・・・，Ｃpk-1）を計算して出力する。推定された情報Ｉpの計算方法は、図２４を用いて後で説明する。
【００２７】
図２１のフローチャートを用いて、受信語ＲからシンドロームＳを計算する方法を説明する。
【００２８】
まず、ステップ１２０では、受信語Ｒ＝（Ｒ0，Ｒ1，・・・，Ｒn-1）を受け取る。そして、ステップ１２１で、シンドロームＳの各要素（Ｓ0，Ｓ1，・・・，Ｓp-1）を受信語Ｒの要素Ｒ0で初期化する。また、ステップ１２２で、カウンタｉを１に初期化する。
【００２９】
次に、ステップ１２３で、シンドロームＳの各要素を、（１０）式によって更新する。
【００３０】
【数７】
0004423519.tif 000008
【００３１】
次に、ステップ１２４で、カウンタｉの値を１だけ増加させる。そして、ステップ１２５で、ｉ＜ｎの条件を判定し、真ならばステップ１２３に戻ってシンドローム計算を繰り返し、偽ならばステップ１２６に進み、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を出力する。
【００３２】
図２２のフローチャートを用いて、修正シンドローム多項式Ｓm(ｘ)から、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を計算する方法（ユークリッドの互除法を用いたアルゴリズムによる方法）を説明する。
【００３３】
まず、ステップ１３０で、ｒ-1(ｘ)，ｒ0(ｘ)，ｕ-1(ｘ)，ｕ0(ｘ)，ｖ-1(ｘ)，ｖ0(ｘ)を、（１１）式に示すように、初期化する。
【００３４】
【数８】
0004423519.tif 000009
【００３５】
次に、ステップ１３１で、カウンタｉを０に初期化する。また、ステップ１３２で、カウンタｉの値を１だけ増加させる。そして、ステップ１３３で、除算をして、（１２）式を満足するｑi-1(ｘ)を見つける。ここで、degｒi(ｘ)はｒi(ｘ)の次数であり、degｒi-1(ｘ)はｒi-1(ｘ)の次数である。
【００３６】
【数９】
0004423519.tif 000010
【００３７】
次に、ステップ１３４で、ステップ１３３で見つけたｑi-1(ｘ)を用いて、（１３）式に示すように、ｕi(ｘ)，ｖi(ｘ)を更新する。
【００３８】
【数１０】
0004423519.tif 000011
【００３９】
次に、ステップ１３５で、（１４）式の条件（終了条件）を判定し、真であればステップ１３６に進み、偽であればステップ１３２に戻り、ステップ１３３で再び除算をする。ステップ１３６では、（１５）式に示すように、誤り評価多項式ω(ｘ)、誤り位置多項式σ(ｘ)を設定する。
【００４０】
【数１１】
0004423519.tif 000012
【００４１】
図２３のフローチャートを用いて、誤り位置多項式σ(ｘ)から、誤り位置を検出する方法を説明する。
【００４２】
まず、ステップ１４０で、カウンタｉを０に初期化する。そして、ステップ１４１で、σ（α-i）＝０の条件を判定し、真ならばカウンタｉの示す位置は誤り位置であるのでステップ１４２に進み、偽であればカウンタｉの示す位置は誤り位置ではないのでステップ１４３に進む。ステップ１４２では、検出された誤り位置を表すカウンタｉの値をメモリＡに登録し、その後にステップ１４３に進む。ステップ１４３では、カウンタｉの値を１だけ増加させる。
【００４３】
次に、ステップ１４４で、ｉ＜ｎの条件（終了条件）を判定し、真ならばステップ１４１に戻って誤り位置の検出を繰り返し、偽ならばステップ１４５に進む。ステップ１４５では、誤り位置としてメモリＡの登録内容を出力する。
【００４４】
図２４のフローチャートを用いて、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、検出した誤り位置ｉとから、受信語Ｒの誤りを訂正する方法を説明する。
【００４５】
まず、ステップ１５０で、カウンタｉを０に初期化する。そして、ステップ１５１で、ｉ∈Ａの条件を判定し、真ならばカウンタｉの値は誤り位置を表しているのでステップ１５２に進み、偽ならばカウンタｉの値は誤り位置ではないのでステップ１５４に進む。
【００４６】
ステップ１５２では、誤り評価多項式ω(ｘ)と、誤り位置多項式σ(ｘ)の微分σ′(ｘ)と、誤り位置ｉを用いて、（１６）式に示すように誤り値ｅiを計算し、ステップ１５３に進む。ステップ１５３では、推定符号語Ｃpのｉ番目の要素ＣpiをＲi−ｅiとして計算し、ステップ１５５に進む。ステップ１５４では、推定符号語Ｃpのｉ番目の要素ＣpiをＲiとして、ステップ１５５に進む。
【００４７】
【数１２】
0004423519.tif 000013
【００４８】
ステップ１５５では、カウンタｉの値を１だけ増加させる。そして、ステップ１５６で、ｉ＜ｎの条件（終了条件）を判定し、真ならばステップ１５１に戻って誤り値の計算を繰り返し、偽ならばステップ１５７に進む。ステップ１５７では、推定符号語Ｃp＝（Ｃp0，Ｃp1，・・・，Ｃpn-1）を得、そしてステップ１５８で、推定符号語Ｃpより推定情報Ｉp＝（Ｃp0，Ｃp1，・・・，Ｃpk-1）を得て出力する。
【００４９】
図２５は、上述したリードソロモン符号の復号方法を実施する復号装置１６０の構成を示している。
【００５０】
この復号装置１６０は、受信語（入力データ）Ｒを入力する入力端子１６１と、受信語Ｒに対応した消失フラグＦを入力する入力端子１６２とを有している。
【００５１】
また、復号装置１６０は、受信語Ｒからシンドローム多項式Ｓ(ｘ)を得るためのシンドローム多項式計算回路１６３（図２０のステップ１０２参照）と、消失フラグＦから消失位置多項式Ｅ(ｘ)を得るための消失位置多項式計算回路１６４（図２０のステップ１０１参照）と、消失フラグＦから消失数εを求めるための消失数計算回路１６５（図２０のステップ１０１参照）とを有している。
【００５２】
また、復号装置１６０は、シンドローム多項式Ｓ(ｘ)、消失位置多項式Ｅ(ｘ)から修正シンドローム多項式Ｓm(ｘ)を求め、この修正シンドローム多項式Ｓm(ｘ)と消失位置多項式Ｅ(ｘ)から誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)を求める誤り多項式計算回路１６６（図２０のステップ１０４参照）を有している。
【００５３】
また、復号装置１６０は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から受信語Ｒの各要素Ｒiの誤り値ｅiを求める誤り値計算回路１６７（図２４のステップ１５２参照）と、受信語Ｒの各要素Ｒｉのタイミングを、誤り値計算回路１６７より出力される誤り値ｅiのタイミングに合わせるための受信語遅延回路１６８と、受信語Ｒの各要素Ｒiより誤り値ｅiを減算する減算器１６９（図２４のステップ１５３参照）とを有している。
【００５４】
また、復号装置１６０は、減算器１６９の出力Ｒi−ｅiまたは受信語遅延回路１６８の出力Ｒiのいずれかを選択的に取り出す信号選択回路１７０と、誤り位置多項式σ(ｘ)から誤り位置ｉを検出し、誤り位置ｉに応じた選択信号ＳＥＬを出力すると共に、＃roots＝degσ(ｘ)の条件を判定し（図２０のステップ１０８参照）、偽であるときはエラー信号ＥＲを出力する誤り位置判定回路１７１と、信号選択回路１７０の出力を導出する出力端子１７２とを有している。
【００５５】
ここで、誤り位置判定回路１７１より出力される選択信号ＳＥＬは信号選択回路１７０に供給され、信号選択回路１７０では誤り位置ｉで減算器１６９の出力Ｒi−ｅiが取り出され、誤り位置ｉでない位置で受信語遅延回路１６８の出力Ｒiが取り出されるようになされている。
【００５６】
また、復号装置１６０は、degω(ｘ)＜degσ(ｘ)の条件や、（９）式の条件を判定し（図２０のステップ１０５，１０６参照）、偽であるときはエラー信号ＥＲを出力するエラー判定回路１７３と、誤り位置判定回路１７１より出力されるエラー信号ＥＲおよびエラー判定回路１７３より出力されるエラー信号ＥＲが入力されるオアゲート１７４と、このオアゲート１７４の出力を導出する出力端子１７５とを有している。
【００５７】
なお、オアゲート１７４の出力は信号選択回路１７０に供給され、オアゲート１７４の出力としてエラー信号ＥＲが得られる場合には、信号選択回路１７０では選択信号ＳＥＬの状態に依らずに、常に受信語遅延回路１６８の出力Ｒiを取り出すようにされている。
【００５８】
図２５に示す復号装置１６０の動作を説明する。
【００５９】
入力端子１６１に入力された受信語（入力データ）Ｒはシンドローム多項式計算回路１６３に供給される。そして、この計算回路１６３では、受信語ＲからシンドロームＳが計算され、シンドローム多項式Ｓ(ｘ)が求められる。一方、入力端子１６２に入力された消失フラグＦは消失位置多項式計算回路１６４に供給される。そして、この計算回路１６４では、消失フラグＦから消失位置多項式Ｅ(ｘ)が求められる。また、入力端子１６２に入力された消失フラグＦは消失数計算回路１６５に供給される。そして、この計算回路１６５では、消失フラグＦより消失数εが求められる。
【００６０】
計算回路１６３で得られたシンドローム多項式Ｓ(ｘ)と、計算回路１６４で得られた消失位置多項式Ｅ(ｘ)は、誤り多項式計算回路１６６に供給される。そして、この計算回路１６６では、シンドローム多項式Ｓ(ｘ)、消失位置多項式Ｅ(ｘ)から修正シンドローム多項式Ｓm(ｘ)が求められ、さらにこの修正シンドローム多項式Ｓm(ｘ)と消失位置多項式Ｅ(ｘ)から誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)が求められる。
【００６１】
計算回路１６６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は誤り値計算回路１６７に供給される。この計算回路１６７では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から、受信語Ｒの各要素Ｒiの誤り値ｅiが順次求められる。そして、この誤り値ｅiが減算器１６９に供給されて、受信語遅延回路１６８より出力される受信語Ｒの各要素Ｒiより減算される。
【００６２】
また、計算回路１６６で得られた誤り位置多項式σ(ｘ)は誤り位置判定回路１７１に供給される。そして、この誤り位置判定回路１７１では、誤り位置多項式σ(ｘ)から誤り位置ｉが検出され、誤り位置ｉに応じた選択信号ＳＥＬが出力される。この選択信号ＳＥＬは信号選択回路１７０に制御信号として供給される。そして、信号選択回路１７０では、誤り位置ｉで減算器１６９の出力Ｒi−ｅiが取り出され、誤り位置ｉでない位置で受信語遅延回路１６８の出力Ｒiが取り出される。
【００６３】
これにより、信号選択回路１７０からは誤り訂正された推定符号語Ｃpが取り出され、この推定符号語Ｃpが出力データとして出力端子１７２に導出される。推定符号語Ｃpよりパリティシンボル部分を除くことで、推定情報Ｉp＝（Ｃp0，Ｃp1，・・・，Ｃpk-1）が得られる。
【００６４】
なお、エラー判定回路１７３または誤り位置判定回路１７１よりエラー信号ＥＲが出力される場合、このエラー信号ＥＲが出力端子１７５に導出されると共に、このエラー信号ＥＲが信号選択回路１７０に供給される。そして、信号選択回路１７０では、選択信号ＳＥＬの状態に依らずに、常に受信語遅延回路１６８の出力Ｒiが取り出される。これにより、出力端子１７５にエラー信号ＥＲが導出される状態では、受信語Ｒが誤り訂正されず、出力端子１７２にそのまま出力されることとなる。
【００６５】
【発明が解決しようとする課題】
上述したように、通常のリードソロモン符号は、１パスでの混合訂正が可能であった。これに対して、１拡張リードソロモン符号および２拡張リードソロモン符号に関しては、２パスでの混合訂正の方法が提案されているが（Richard E. Blahut  ，″THEORY AND PRACTICE OF ERROR CONTOL CODES″，  ISBN：0-201-10102-5 ，p.260〜  ″9.3 DECODING OF EXTENDED REED-SOLOMON CODES″）、１パスでの混合訂正の方法は提案されていない。因に、拡張リードソロモン符号の２パスでの混合訂正においては、復号に時間がかかり、またハードウェア規模も大きくなるという不都合がある。
【００６６】
そこで、この発明では、例えば１拡張リードソロモン符号、２拡張リードソロモン符号の１パスでの混合訂正を可能にする誤り訂正符号の復号方法を提供することを目的とする。
【００６７】
【課題を解決するための手段】
この発明に係る誤り訂正符号の復号方法は、拡張シンボルを含む入力データから上記拡張シンボルを計算に入れてシンドローム多項式を求める第１のステップと、上記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、上記入力データに対応した消失フラグから消失数を求める第３のステップと、上記シンドローム多項式および消失位置多項式から誤り位置多項式および誤り評価多項式を求める第４のステップと、上記誤り位置多項式および誤り評価多項式から誤り位置を求める第５のステップと、上記誤り位置多項式および誤り評価多項式から上記拡張シンボルを含む誤り値を求める第６のステップと、上記誤り位置および上記誤り値を用いて上記入力データの誤りを訂正して出力データを得る第７のステップと、上記拡張シンボルの訂正可能判定を含めた訂正可能判定を行う第８のステップとを備え、上記入力データ中の拡張シンボルの値は、拡張シンボル以外のシンボルの値を加算して得たものであり、上記第８のステップは、上記誤り位置多項式の次数と、上記消失数および上記入力データのパリティシンボル数を使用して求められた数とを比較して訂正可能判定をするものである。
【００６８】
この発明においては、拡張シンボルの通常訂正および消失訂正を行う手段が組み込まれるため、例えば１拡張リードソロモン符号または２拡張リードソロモン符号の１パスでの混合訂正が可能となる。
【００６９】
【発明の実施の形態】
第１の実施の形態について説明する。この第１の実施の形態は、１拡張リードソロモン符号において通常訂正と消失訂正を同時に行う混合訂正の復号法である。
【００７０】
なおここで、体ＧＦ(２)＝{０，１}上の原始多項式ｆ(ｘ)に対して、ｆ(ｘ)＝０の根をαとし、ＧＦ(２)の拡大体を構成する。このとき、原始多項式ｆ(ｘ)の次数をｍとすると、１シンボルはｍビットとなり、拡大体ＧＦ(２m)は、上述の（１）式で表される。また、ここで使用するリードソロモン符号の生成多項式ｇ(ｘ)は、上述の（２）式で表される。
【００７１】
図１は、第１の実施の形態における１拡張リードソロモン符号の復号化のフローチャートを示している。
【００７２】
まず、ステップ２００では、受信語Ｒ＝（Ｒ-，Ｒ0，Ｒ1，・・・，Ｒn-1）と消失フラグＦ＝（Ｆ-，Ｆ0，Ｆ1，・・・，Ｆn-1）が与えられる。消失フラグＦとは、受信語Ｒ中で誤りがあると予測される位置に対応しては１を、それ以外の誤りがないと予測される位置に対応しては０を設定したフラグである。上述した従来のリードソロモン符号の復号法との違いは、拡張受信シンボルＲ-と、拡張消失フラグＦ-が追加されたことである。
【００７３】
次に、ステップ２０１で、消失数εを、（１７）式により求めると共に、消失位置多項式Ｅ(ｘ)を上述の（４）式により求める。上述した従来のリードソロモン符号の復号法との違いは、消失数εに拡張消失フラグＦ-を計算に入れたことである。
【００７４】
【数１３】
0004423519.tif 000014
【００７５】
次に、ステップ２０２で、（１８）式に示すようなパリティ検査行列Ｈを用いて、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を、上述の（６）式から求める。シンドロームＳの計算方法は、図２を用いて後で説明する。そして、上述の（７）式に示すようなシンドローム多項式Ｓ(ｘ)を求める。
【００７６】
【数１４】
0004423519.tif 000015
【００７７】
次に、ステップ２０３で、消失位置多項式Ｅ(ｘ)およびシンドローム多項式Ｓ(ｘ)を用いて、上述の（８）式に示すように、修正シンドローム多項式Ｓm(ｘ)を求める。
【００７８】
次に、ステップ２０４で、修正シンドローム多項式Ｓm(ｘ)を用いて、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を求める。誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)の計算方法は、図３を用いて後で説明する。
【００７９】
次に、ステップ２０５で、degω(ｘ)＜degσ(ｘ)の条件を判定し、偽ならばステップ２０６に進み、真ならばステップ２０８に進む。ここで、degω(ｘ)は誤り評価多項式ω(ｘ)の次数であり、degσ(ｘ)は誤り位置多項式σ(ｘ)の次数である。ステップ２０６では、degω(ｘ)＝degσ(ｘ)の条件を判定し、偽ならばステップ２１４に進んでエラー信号を出力して終了し、真ならばステップ２０７に進む。
【００８０】
ステップ２０７では、（１９）式の条件を判定し、偽ならばステップ２１４に進んでエラー信号を出力して終了し、真ならばステップ２０９に進む。ステップ２０９では、ステップ２０５，２０６の判定結果から拡張シンボル位置に誤りがあることが判明しているので、拡張誤りフラグｅ-flagを１に設定し、その後にステップ２１１に進む。
【００８１】
【数１５】
0004423519.tif 000016
【００８２】
ステップ２０８では、上述の（９）式の条件を判定し、偽ならばステップ２１４に進んでエラー信号を出力して終了し、真ならばステップ２１０に進む。ステップ２１０では、ステップ２０５の判定結果から拡張シンボル位置に誤りがないことが判明しているので、拡張誤りフラグｅ-flagを０に設定し、その後にステップ２１１に進む。
【００８３】
ステップ２１１では、誤り位置多項式σ(ｘ)を使用して誤り位置を検出する。このとき、Ｒ-に対する誤り位置の検出は行わない。誤り位置の計算方法は、図４を用いて後で説明する。そして、ステップ２１２で、＃roots＝degσ(ｘ)の条件を判定し、偽ならばステップ２１４に進んでエラー信号を出力して終了し、真ならばステップ２１３に進む。ここで、＃rootsはステップ２１１で検出した誤り位置の数である。
【００８４】
ステップ２１３では、ステップ２０４で求められた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、ステップ２１１で検出した誤り位置ｉとから、位置ｉでの誤り値ｅiを計算すると共に、この誤り値ｅｉとステップ２０２で得られたシンドロームＳの第０要素Ｓ0を用いて拡張誤り値ｅ-を計算し、さらに受信語Ｒと誤り位置ｉ、誤り値ｅi、拡張誤り値ｅ-から、推定情報Ｉp＝（Ｃp-，Ｃp0，Ｃp1，・・・，Ｃpk-1）を計算する。推定情報Ｉpの計算方法は、図５を用いて後で説明する。ここで、拡張シンボルＣp-は、拡張シンボルＣp-以外の値を全て加算して得たものである。つまり、Ｃp-＝Ｃp0＋Ｃp1＋・・・＋Ｃpn-1である。
【００８５】
次に、ステップ２１５で、ｅ-flag＝０の条件を判定し、偽ならばステップ２１６に進み、真ならばステップ２１７に進む。ステップ２１６では、ｅ-≠０の条件を判定し、偽ならばステップ２１４に進んでエラー信号を出力して終了し、真ならば推定情報Ｉpを出力して終了する。一方、ステップ２１７では、ｅ-＝０の条件を判定し、偽ならばステップ２１４に進んでエラー信号を出力して終了し、真ならば推定情報Ｉpを出力して終了する。
【００８６】
図２のフローチャートを用いて、受信語ＲからシンドロームＳを計算する方法を説明する。
【００８７】
まず、ステップ２２０では、受信語Ｒ＝（Ｒ-，Ｒ0，Ｒ1，・・・，Ｒn-1）を受け取る。そして、ステップ２２１で、シンドロームＳの各要素（Ｓ0，Ｓ1，・・・，Ｓp-1）を受信語Ｒの要素Ｒ0で初期化する。
【００８８】
次に、ステップ２２２で、シンドロームＳの第０要素Ｓ0から受信語Ｒの最初の要素Ｒ-を減算し、その減算結果をＳ0とする。また、ステップ２２３で、カウンタｉを１に初期化する。そして、ステップ２２４で、シンドロームＳの各要素を、上述の（１０）式によって更新する。
【００８９】
次に、ステップ２２５で、カウンタｉの値を１だけ増加させる。そして、ステップ２２６で、ｉ＜ｎの条件を判定し、真ならばステップ２２４に戻ってシンドローム計算を繰り返し、偽ならばステップ２２７に進み、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を出力する。
【００９０】
図３のフローチャートを用いて、修正シンドローム多項式Ｓm(ｘ)から、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を計算する方法（ユークリッドの互除法を用いたアルゴリズムによる方法）を説明する。
【００９１】
まず、ステップ２３０で、ｒ-1(ｘ)，ｒ0(ｘ)，ｕ-1(ｘ)，ｕ0(ｘ)，ｖ-1(ｘ)，ｖ0(ｘ)を、上述の（１１）式に示すように、初期化する。そして、ステップ２３１で、カウンタｉを０に初期化する。また、ステップ２３２で、カウンタｉの値を１だけ増加させる。そして、ステップ２３３で、除算をして、上述の（１２）式を満足するｑi-1(ｘ)を見つける。ここで、degｒi(ｘ)はｒi(ｘ)の次数であり、degｒi-1(ｘ)はｒi-1(ｘ)の次数である。
【００９２】
次に、ステップ２３４で、ステップ２３３で見つけたｑi-1(ｘ)を用いて、上述の（１３）式に示すように、ｕi(ｘ)，ｖi(ｘ)を更新する。
【００９３】
次に、ステップ２３５で、上述の（１４）式の条件（終了条件）を判定し、真であればステップ２３６に進み、偽であればステップ２３２に戻り、ステップ２３３で再び除算をする。ステップ２３６では、上述の（１５）式に示すように、誤り評価多項式ω(ｘ)、誤り位置多項式σ(ｘ)を設定する。
【００９４】
図４のフローチャートを用いて、誤り位置多項式σ(ｘ)から、誤り位置を検出する方法を説明する。
【００９５】
まず、ステップ２４０で、カウンタｉを０に初期化する。そして、ステップ２４１で、σ（α-i）＝０の条件を判定し、真ならばカウンタｉの示す位置は誤り位置であるのでステップ２４２に進み、偽であればカウンタｉの示す位置は誤り位置ではないのでステップ２４３に進む。ステップ２４２では、検出された誤り位置を表すカウンタｉの値をメモリＡに登録し、その後にステップ２４３に進む。ステップ２４３では、カウンタｉの値を１だけ増加させる。
【００９６】
次に、ステップ２４４で、ｉ＜ｎの条件（終了条件）を判定し、真ならばステップ２４１に戻って誤り位置の検出を繰り返し、偽ならばステップ２４５に進む。ステップ２４５では、誤り位置としてメモリＡの登録内容を出力する。
【００９７】
図５のフローチャートを用いて、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、検出した誤り位置ｉとから、受信語Ｒの誤り訂正をする方法を説明する。
【００９８】
まず、ステップ２５０で、変数ｗをシンドロームＳの第０要素Ｓ0でｗ＝−Ｓ0として初期化する。ｗは、拡張誤り値ｅ-を、（２０）式に示すように計算するために使用する。
【００９９】
【数１６】
0004423519.tif 000017
【０１００】
次に、ステップ２５１で、カウンタｉを０に初期化する。そして、ステップ２５２で、ｉ∈Ａの条件を判定し、真ならばカウンタｉの値は誤り位置を表しているのでステップ２５３に進み、偽ならばカウンタｉの値は誤り位置ではないのでステップ２５６に進む。
【０１０１】
ステップ２５３では、誤り評価多項式ω(ｘ)と、誤り位置多項式σ(ｘ)の微分σ′(ｘ)と、誤り位置ｉを用いて、上述の（１６）式に示すように誤り値ｅiを計算し、ステップ２５４に進む。ステップ２５４では、推定符号語Ｃpのｉ番目の要素ＣpiをＲi−ｅiとして計算し、ステップ２５５に進む。ステップ２５５では、ｗ＝ｗ＋ｅiとしてｗを更新し、ステップ２５７に進む。ステップ２５６では、推定符号語Ｃpのｉ番目の要素ＣpiをＲiとして、ステップ２５７に進む。
【０１０２】
ステップ２５７では、カウンタｉの値を１だけ増加させる。そして、ステップ２５８で、ｉ＜ｎの条件（終了条件）を判定し、真ならばステップ２５２に戻って誤り値の計算を繰り返し、偽ならばステップ２５９に進む。ステップ２５９では、拡張誤り値ｅ-にｗの値を代入する。
【０１０３】
次に、ステップ２６０で、推定拡張符号シンボルＣp-を、Ｃp-＝Ｒ-−ｅ-として設定する。そして、ステップ２６１で、推定符号語Ｃp＝（Ｃp-，Ｃp0，・・・，Ｃpn-1）を得、さらにステップ２６２で、推定符号語Ｃpより、推定情報Ｉp＝（Ｃp-，Ｃp0，Ｃp1，・・・，Ｃpk-1）を得る。
【０１０４】
図６は、図１のフローチャートに示す１拡張リードソロモン符号の復号方法を実施する復号装置２７０の構成を示している。
【０１０５】
この復号装置２７０は、受信語（入力データ）Ｒを入力する入力端子２７１と、受信語Ｒに対応した消失フラグＦを入力する入力端子２７２とを有している。
【０１０６】
また、復号装置２７０は、受信語Ｒからシンドローム多項式Ｓ(ｘ)を得るためのシンドローム多項式計算回路２７３（図１のステップ２０２参照）と、消失フラグＦから消失位置多項式Ｅ(ｘ)を得るための消失位置多項式計算回路２７４（図１のステップ２０１参照）と、消失フラグＦから消失数εを求めるための消失数計算回路２７５（図１のステップ２０１参照）とを有している。
【０１０７】
また、復号装置２７０は、シンドローム多項式Ｓ(ｘ)、消失位置多項式Ｅ(ｘ)から修正シンドローム多項式Ｓm(ｘ)を求め、この修正シンドローム多項式Ｓm(ｘ)と消失位置多項式Ｅ(ｘ)から誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)を求める誤り多項式計算回路２７６（図１のステップ２０４参照）を有している。
【０１０８】
また、復号装置２７０は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から受信語Ｒの各要素Ｒiの誤り値ｅiを求める誤り値計算回路２７７（図５のステップ２５３参照）と、受信語Ｒの各要素Ｒｉのタイミングを、誤り値計算回路２７７より出力される誤り値ｅiのタイミングに合わせるための受信語遅延回路２７８と、受信語Ｒの各要素Ｒiより誤り値ｅiを減算する減算器２７９（図５のステップ２５４参照）とを有している。
【０１０９】
また、復号装置２７０は、減算器２７９の出力Ｒi−ｅiまたは受信語遅延回路２７８の出力Ｒiのいずれかを選択的に取り出す信号選択回路２８０と、誤り位置多項式σ(ｘ)から誤り位置ｉを検出し、誤り位置ｉに応じた選択信号ＳＥＬを出力すると共に、＃roots＝degσ(ｘ)の条件を判定し（図１のステップ２１２参照）、偽であるときはエラー信号ＥＲを出力する誤り位置判定回路２８１とを有している。ここで、誤り位置判定回路２８１より出力される選択信号ＳＥＬは信号選択回路２８０に供給され、信号選択回路２８０では誤り位置ｉで減算器２７９の出力Ｒi−ｅiが取り出され、誤り位置ｉでない位置で受信語遅延回路２７８の出力Ｒiが取り出されるようになされている。
【０１１０】
また、復号装置２７０は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から拡張誤り値ｅ-を求める拡張誤り値計算回路２８２（図５のステップ２５９参照）と、信号選択回路２８０の出力より拡張誤り値ｅ-を減算する減算器２８３（図５のステップ２６０参照）と、減算器２８３の出力または信号選択回路２８０の出力のいずれかを選択的に取り出す信号選択回路２８４とを有している。
【０１１１】
また、復号装置２７０は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から拡張シンボル位置に誤りがあるか否かを判定し、拡張誤りフラグｅ-flagを設定する拡張誤りフラグ計算回路２８５（図１のステップ２０９，２１０参照）と、信号選択回路２８４の出力を導出する出力端子２８６とを有している。ここで、拡張シンボル位置に誤りがあると判定されるときはｅ-flag＝１とされ、拡張シンボル位置に誤りがないと判定されるときはｅ-flag＝０とされる。この計算回路２８５より出力される拡張誤りフラグｅ-flagは信号選択回路２８４に供給される。
【０１１２】
信号選択回路２８４では、信号選択回路２８０より拡張受信シンボルＲ-が出力される際には、ｅ-flag＝１であるときは減算器２８３の出力Ｒ-−ｅ-が推定拡張シンボルＣp-として取り出され、ｅ-flag＝０であるときは信号選択回路２８０の出力Ｒ-が推定拡張シンボルＣp-として取り出されるようになされている。また、信号選択回路２８４では、信号選択回路２８０より拡張受信シンボルＲ-以外のシンボルが出力される際には、信号選択回路２８０の出力のみが取り出される。
【０１１３】
また、復号装置２７０は、degω(ｘ)＜degσ(ｘ)が偽であればdegω(ｘ)＝degσ(ｘ)の条件や（１９）式の条件を判定し、一方degω(ｘ)＜degσ(ｘ)が真であれば（９）式の条件を判定し（図１のステップ２０５〜２０８参照）、偽であるときはエラー信号ＥＲを出力するエラー判定回路２８７と、ｅ-flag＝０が偽であればｅ-≠０の条件を判定し、一方ｅ-flag＝０が真であればｅ-＝０の条件を判定し（図１のステップ２１５〜２１７参照）、偽であるときはエラー信号ＥＲを出力する拡張エラー判定回路２８８とを有している。
【０１１４】
また、復号装置２７０は、誤り位置判定回路２８１より出力されるエラー信号ＥＲ、エラー判定回路２８７より出力されるエラー信号ＥＲおよび拡張エラー判定回路２８８より出力されるエラー信号ＥＲが入力されるオアゲート２８９と、このオアゲート２８９の出力を導出する出力端子２９０とを有している。
【０１１５】
なお、オアゲート２８９の出力は信号選択回路２８０，２８４に供給され、オアゲート２８９の出力としてエラー信号ＥＲが得られる場合には、信号選択回路２８０では選択信号ＳＥＬの状態に依らずに常に受信語遅延回路２７８の出力Ｒiが取り出され、信号選択回路２８４では拡張誤りフラグｅ-flagの状態に依らずに常に信号選択回路２８０の出力が取り出されるようにされている。
【０１１６】
図６に示す復号装置２７０の動作を説明する。
【０１１７】
入力端子２７１に入力された受信語（入力データ）Ｒはシンドローム多項式計算回路２７３に供給される。そして、この計算回路２７３では、受信語ＲからシンドロームＳが計算され、シンドローム多項式Ｓ(ｘ)が求められる。一方、入力端子２７２に入力された消失フラグＦは消失位置多項式計算回路２７４に供給される。そして、この計算回路２７４では、消失フラグＦから消失位置多項式Ｅ(ｘ)が求められる。また、入力端子２７２に入力された消失フラグＦは消失数計算回路２７５に供給される。そして、この計算回路２７５では、消失フラグＦより消失数εが求められる。
【０１１８】
計算回路２７３で得られたシンドローム多項式Ｓ(ｘ)と、計算回路２７４で得られた消失位置多項式Ｅ(ｘ)は、誤り多項式計算回路２７６に供給される。そして、この計算回路２７６では、シンドローム多項式Ｓ(ｘ)、消失位置多項式Ｅ(ｘ)から修正シンドローム多項式Ｓm(ｘ)が求められ、さらにこの修正シンドローム多項式Ｓm(ｘ)と消失位置多項式Ｅ(ｘ)から誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)を求められる。
【０１１９】
計算回路２７６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は誤り値計算回路２７７に供給される。この計算回路２７７では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から、受信語Ｒの各要素Ｒiの誤り値ｅiが順次求められる。そして、この誤り値ｅiが減算器２７９に供給されて、受信語遅延回路２７８より出力される受信語Ｒの各要素Ｒiより減算される。
【０１２０】
また、計算回路２７６で得られた誤り位置多項式σ(ｘ)は誤り位置判定回路２８１に供給される。この誤り位置判定回路２８１では、誤り位置多項式σ(ｘ)から誤り位置ｉが検出され、誤り位置ｉに応じた選択信号ＳＥＬが出力される。この選択信号ＳＥＬは信号選択回路２８０に制御信号として供給される。そして、信号選択回路２８０では、誤り位置ｉで減算器２７９の出力Ｒi−ｅiが推定符号語Ｃpの要素Ｃpiとして取り出され、誤り位置ｉでない位置で受信語遅延回路２７８の出力Ｒiが推定符号語Ｃpの要素Ｃpiとして取り出される。
【０１２１】
また、計算回路２７６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は拡張誤り値計算回路２８２に供給される。この計算回路２８２では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から、拡張受信シンボルＲ-の誤り値、つまり拡張誤り値ｅ-が求められる。そして、この拡張誤り値ｅ-が減算器２８３に供給されて、信号選択回路２８０の出力より減算される。
【０１２２】
また、計算回路２７６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は拡張誤りフラグ計算回路２８５に供給される。この計算回路２８５では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から拡張シンボル位置に誤りがあるか否かが判定され、拡張シンボル位置に誤りがあると判定されるときはｅ-flag＝１に設定され、拡張シンボル位置に誤りがないと判定されるときはｅ-flag＝０に設定される。
【０１２３】
この拡張誤りフラグｅ-flagは信号選択回路２８４に制御信号として供給される。信号選択回路２８４では、信号選択回路２８０より拡張受信シンボルＲ-が出力される際には、ｅ-flag＝１であるときは減算器２８３の出力Ｒ-−ｅ-が推定拡張シンボルＣp-として取り出され、ｅ-flag＝０であるときは信号選択回路２８０の出力Ｒ-が推定拡張シンボルＣp-として取り出される。また、信号選択回路２８４では、信号選択回路２８０より拡張受信シンボルＲ-以外のシンボルが出力される際には、信号選択回路２８０の出力のみが取り出される。
【０１２４】
これにより、信号選択回路２８４からは誤り訂正された推定符号語Ｃp（推定拡張シンボルＣp-を含む）が取り出され、この推定符号語Ｃpが出力データとして出力端子２８６に導出される。そして、推定符号語Ｃpよりパリティシンボル部分を除くことで、推定情報Ｉp＝（Ｃp-，Ｃp0，Ｃｐ1，・・・，Ｃpk-1）が得られる。
【０１２５】
なお、誤り位置判定回路２８１、エラー判定回路２８７または拡張エラー判定回路２８８よりエラー信号ＥＲが出力される場合、このエラー信号ＥＲが出力端子２９０に導出されると共に、このエラー信号ＥＲが信号選択回路２８０，２８４に供給される。そして、信号選択回路２８０では選択信号ＳＥＬの状態に依らずに常に受信語遅延回路２７８の出力Ｒiが取り出され、信号選択回路２８４では拡張誤りフラグｅ-flagの状態に依らずに常に信号選択回路２８０の出力が取り出される。これにより、出力端子２９０にエラー信号ＥＲが導出される状態では、受信語Ｒが誤り訂正されず、出力端子２８６にそのまま出力されることとなる。
【０１２６】
以上説明したように、第１の実施の形態においては、１拡張リードソロモン符号の１パスでの混合訂正が可能となる。したがって、１拡張リードソロモン符号の混合訂正を短時間で行うことが可能となり、またハードウェア規模も小さくできるという効果がある。
【０１２７】
次に、第２の実施の形態について説明する。この第２の実施の形態も、１拡張リードソロモン符号において通常訂正と消失訂正を同時に行う混合訂正の復号法に係るものである。図７は、第２の実施の形態における１拡張リードソロモン符号の復号化のフローチャートを示している。
【０１２８】
まず、ステップ３００〜３０４の処理をする。このステップ３００〜３０４では、図１のステップ２００〜２０４とそれぞれ同様の処理をする。
【０１２９】
次に、ステップ３０５で、訂正可能判定数ｈを、ｈ＝２degσ(ｘ)−εとして設定する。訂正可能判定数ｈは、後述するステップ３１１で使用するが、最終的には、（２１）式に示すようになる。
【０１３０】
【数１７】
0004423519.tif 000018
【０１３１】
次に、ステップ３０６で、degω(ｘ)＜degσ(ｘ)の条件を判定し、偽ならばステップ３０７に進み、真ならばステップ３１０に進む。ステップ３０７では、degω(ｘ)＝degσ(ｘ)の条件を判定し、偽ならばステップ３１５に進んでエラー信号を出力して終了し、真ならばステップ３０８に進む。ステップ３０８では、ｈ＝ｈ＋２として、訂正可能判定数ｈを更新し、ステップ３０９に進む。
【０１３２】
ステップ３０９では、ステップ３０６，３０７の判定結果から拡張シンボル位置に誤りがあることが判明しているので、拡張誤りフラグｅ-flagを１に設定し、その後にステップ３１１に進む。ステップ３１０では、ステップ３０６の判定結果から拡張シンボル位置に誤りがないことが判明しているので、拡張誤りフラグｅ-flagを０に設定し、その後にステップ３１１に進む。
【０１３３】
次に、ステップ３１１で、ｈ≦ｐの条件を判定し、偽ならばステップ３１５に進んでエラー信号を出力して終了し、真ならばステップ３１２に進む。そして、ステップ３１２〜３１８の処理をする。このステップ３１２〜３１８では、図１のステップ２１１〜２１７とそれぞれ同様の処理をする。
【０１３４】
すなわち、ステップ３１２では、誤り位置多項式σ(ｘ)を使用して誤り位置を検出する。そして、ステップ３１３で、＃roots＝degσ(ｘ)の条件を判定し、偽ならばステップ３１５に進んでエラー信号を出力して終了し、真ならばステップ３１４に進む。
【０１３５】
ステップ３１４では、ステップ３０４で求められた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、ステップ３１２で検出した誤り位置ｉとから、位置ｉでの誤り値ｅiを計算すると共に、この誤り値ｅｉとステップ３０２で得られたシンドロームＳの第０要素Ｓ0を用いて拡張誤り値ｅ-を計算し、さらに受信語Ｒと誤り位置ｉ、誤り値ｅi、拡張誤り値ｅ-から、推定情報Ｉp＝（Ｃp-，Ｃp0，Ｃp1，・・・，Ｃpk-1）を求める。
【０１３６】
次に、ステップ３１６で、ｅ-flag＝０の条件を判定し、偽ならばステップ３１７に進み、真ならばステップ３１８に進む。ステップ３１７では、ｅ-≠０の条件を判定し、偽ならばステップ３１５に進んでエラー信号を出力して終了し、真ならば推定情報Ｉpを出力して終了する。一方、ステップ３１８では、ｅ-＝０の条件を判定し、偽ならばステップ３１５に進んでエラー信号を出力して終了し、真ならば推定情報Ｉpを出力して終了する。
【０１３７】
図７のフローチャートに示す１拡張リードソロモン符号の復号方法を実施する復号装置は、エラー判定回路２８７の動作が異なる他は、図６に示す復号装置２７０と同様に構成される。すなわち、図６に示す復号装置２７０において、エラー判定回路２８７は、ステップ２０５〜２０８の判定処理によってエラー信号ＥＲを出力するが、図７のフローチャートに示す１拡張リードソロモン符号の復号方法を実施する復号装置において、エラー判定回路２８７は、ステップ３０６，３０７，３１１の判定処理によってエラー信号ＥＲを出力するように構成される。
【０１３８】
以上説明したように、第２の実施の形態においても、第１の実施の形態と同様に、１拡張リードソロモン符号の１パスでの混合訂正が可能となる。
【０１３９】
次に、第３の実施の形態について説明する。この第３の実施の形態も、１拡張リードソロモン符号において通常訂正と消失訂正を同時に行う混合訂正の復号法に係るものである。
【０１４０】
図８は、第３の実施の形態における１拡張リードソロモン符号の復号化のフローチャートを示している。
【０１４１】
まず、ステップ４００では、受信語Ｒ＝（Ｒ+，Ｒ0，Ｒ1，・・・，Ｒn-1）と消失フラグＦ＝（Ｆ+，Ｆ0，Ｆ1，・・・，Ｆn-1）が与えられる。消失フラグＦとは、受信語Ｒ中で誤りがあると予測される位置に対応しては１を、それ以外の誤りがないと予測される位置に対応しては０を設定したフラグである。上述した従来のリードソロモン符号の復号法との違いは、拡張受信シンボルＲ+と、拡張消失フラグＦ+が追加されたことである。
【０１４２】
次に、ステップ４０１で、消失数εを、（２２）式により求めると共に、Ｒ+，Ｒ0，Ｒ1，・・・，Ｒn-1に対する消失位置多項式Ｅ(ｘ)を（２３）式により求める。上述した従来のリードソロモン符号の復号法との違いは、消失数εに拡張消失フラグＦ+を計算に入れたこと、および消失位置多項式Ｅ(ｘ)にＦ+に対応したｘを追加したことである。
【０１４３】
【数１８】
0004423519.tif 000019
【０１４４】
次に、ステップ４０２で、（２４）式に示すようなパリティ検査行列Ｈを用いて、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を、上述の（６）式から求める。シンドロームＳの計算方法は、図９を用いて後で説明する。そして、上述の（７）式に示すようなシンドローム多項式Ｓ(ｘ)を求める。
【０１４５】
【数１９】
0004423519.tif 000020
【０１４６】
次に、ステップ４０３で、消失位置多項式Ｅ(ｘ)およびシンドローム多項式Ｓ(ｘ)を用いて、上述の（８）式に示すように、修正シンドローム多項式Ｓm(ｘ)を求める。
【０１４７】
次に、ステップ４０４で、修正シンドローム多項式Ｓm(ｘ)を用いて、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を求める。誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)の計算方法は、図１のフローチャートのステップ２０４における計算方法（図３参照）と同様である。
【０１４８】
次に、ステップ４０５で、degω(ｘ)＜degσ(ｘ)の条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力し、真ならばステップ４０６に進む。ここで、degω(ｘ)は誤り評価多項式ω(ｘ)の次数であり、degσ(ｘ)は誤り位置多項式σ(ｘ)の次数である。ステップ４０６では、Ｆ+＝０の条件を判定し、偽ならば拡張シンボル位置に消失があるのでステップ４０７に進み、真ならば拡張シンボル位置に消失がないのでステップ４０９に進む。
【０１４９】
ステップ４０７では、ｘ｜σ(ｘ)の条件を判定する。これは、σ(ｘ)がｘで割り切れるか否かを判定しており、割り切れる場合（拡張シンボル位置が誤り位置に含まれている）は真、割り切れない場合は偽となる。判定結果が、偽ならばステップ４１６に進んでエラー信号を出力して終了し、真ならばステップ４０８に進む。ステップ４０９では、ｘ｜σ(ｘ)の条件を判定し、真ならばステップ４０８に進み、偽ならばステップ４１１に進む。ステップ４１１では、ステップ４０５，４０６，４０９の判定結果から、拡張シンボル位置に誤りがないことが判明しているので、拡張誤りフラグｅ+flagを０に設定し、その後にステップ４１２に進む。
【０１５０】
ステップ４０８では、訂正可能ならばｘ｜σ(ｘ)のときは必ずｘ｜ω(ｘ)でなければならないので、ｘ｜ω(ｘ)の条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力して終了し、真ならばステップ４１０に進む。ステップ４１０では、ステップ４０５，４０６，４０７，４０９の判定結果から、拡張シンボル位置に誤りがあることが判明しているので、拡張誤りフラグｅ+flagを１に設定し、その後にステップ４１２に進む。そして、ステップ４１２では、上述の（９）式の条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力して終了し、真ならばステップ４１３に進む。
【０１５１】
ステップ４１３では、誤り位置多項式σ(ｘ)を使用して誤り位置を検出する。誤り位置の計算方法は、図１のフローチャートのステップ２１１における計算方法（図４参照）と同様である。このとき、Ｒ+に対する誤り位置の検出は行わない。そして、ステップ４１４で、＃roots＝degσ(ｘ)−ｅ+flagの条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力して終了し、真ならばステップ４１５に進む。ここで、＃rootsはステップ４１３で検出した誤り位置の数である。誤り位置多項式degσ(ｘ)の次数から拡張誤りフラグｅ+flagを減算しているのは、σ(ｘ)には拡張シンボルに対応する誤り位置が含まれているためである。
【０１５２】
ステップ４１５では、ステップ４０４で求められた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、ステップ４１３で検出した誤り位置ｉとから、位置ｉでの誤り値ｅiを計算すると共に、この誤り値ｅｉとステップ４０２で得られたシンドロームＳの第（ｐ−１）要素Ｓp-1を用いて拡張誤り値ｅ+を計算し、さらに受信語Ｒと誤り位置ｉ、誤り値ｅi、拡張誤り値ｅ+から、推定情報Ｉp＝（Ｃp+，Ｃp0，Ｃp1，・・・，Ｃpk-1）を求める。推定情報Ｉpの計算方法は、図１０を用いて後で説明する。ここで、拡張シンボルＣp+は、拡張シンボルＣp+以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものである。つまり、Ｃp+＝Ｃp0＋Ｃp1αp-1＋Ｃp2α2(p-1)＋・・・＋Ｃpn-1α(n-1)(p-1)である。
【０１５３】
次に、ステップ４１７で、ｅ+flag＝０の条件を判定し、偽ならば推定情報Ｉpを出力して終了し、真ならばステップ４１９に進む。ステップ４１９では、ｅ+＝０の条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力して終了し、真ならば推定情報Ｉpを出力して終了する。
【０１５４】
図９のフローチャートを用いて、受信語ＲからシンドロームＳを計算する方法を説明する。
【０１５５】
まず、ステップ４２０では、受信語Ｒ＝（Ｒ+，Ｒ0，Ｒ1，・・・，Ｒn-1）を受け取る。そして、ステップ４２１で、シンドロームＳの各要素（Ｓ0，Ｓ1，・・・，Ｓp-1）を受信語Ｒの要素Ｒ0で初期化する。
【０１５６】
次に、ステップ４２２で、シンドロームＳの第（ｐ−１）要素Ｓp-1から受信語Ｒの最初の要素Ｒ+を減算し、その減算結果をＳp-1とする。また、ステップ４２３で、カウンタｉを１に初期化する。そして、ステップ４２４で、シンドロームＳの各要素を、上述の（１０）式によって更新する。
【０１５７】
次に、ステップ４２５で、カウンタｉの値を１だけ増加させる。そして、ステップ４２６で、ｉ＜ｎの条件を判定し、真ならばステップ４２４に戻ってシンドローム計算を繰り返し、偽ならばステップ４２７に進み、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を出力する。
【０１５８】
図１０のフローチャートを用いて、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、検出した誤り位置ｉとから、受信語Ｒの誤りを訂正する方法を説明する。
【０１５９】
まず、ステップ４３０で、変数ｗをシンドロームＳの第（ｐ−１）要素Ｓp-1でｗ＝−Ｓp-1として初期化する。ｗは、拡張誤り値ｅ+を、（２５）式に示すように計算するために使用する。
【０１６０】
【数２０】
0004423519.tif 000021
【０１６１】
次に、ステップ４３１で、カウンタｉを０に初期化する。そして、ステップ４３２で、ｉ∈Ａの条件を判定し、真ならばカウンタｉの値は誤り位置を表しているのでステップ４３３に進み、偽ならばカウンタｉの値は誤り位置ではないのでステップ４３６に進む。
【０１６２】
ステップ４３３では、誤り評価多項式ω(ｘ)と、誤り位置多項式σ(ｘ)の微分σ′(ｘ)と、誤り位置ｉを用いて、上述の（１６）式に示すように誤り値ｅiを計算し、ステップ４３４に進む。ステップ４３４では、推定符号語Ｃpのｉ番目の要素ＣpiをＲi−ｅiとして計算し、ステップ４３５に進む。ステップ４３５では、（２６）式に示すようにｗを更新し、ステップ４３７に進む。ステップ４３６では、推定符号語Ｃpのｉ番目の要素ＣpiをＲiとして、ステップ４３７に進む。
【０１６３】
【数２１】
0004423519.tif 000022
【０１６４】
ステップ４３７では、カウンタｉの値を１だけ増加させる。そして、ステップ４３８で、ｉ＜ｎの条件（終了条件）を判定し、真ならばステップ４３２に戻って誤り値の計算を繰り返し、偽ならばステップ４３９に進む。ステップ４３９では、拡張誤り値ｅ+にｗの値を代入する。
【０１６５】
次に、ステップ４４０で、推定拡張符号シンボルＣp+を、Ｃp+＝Ｒ+−ｅ+として設定する。そして、ステップ４４１で、推定符号語Ｃp＝（Ｃp+，Ｃp0，・・・，Ｃpn-1）を得、さらにステップ４４２で、推定情報Ｉp＝（Ｃp+，Ｃp0，Ｃp1，・・・，Ｃpk-1）を得る。
【０１６６】
図８のフローチャートに示す１拡張リードソロモン符号の復号方法を実施する復号装置は、消失位置多項式計算回路２７４、誤り位置判定回路２８１、およびエラー判定回路２８７の動作が異なる他は、図６に示す復号装置２７０と同様に構成される。
【０１６７】
すなわち、図６に示す復号装置２７０において、消失位置多項式計算回路２７４で求める消失位置多項式Ｅ(ｘ)は拡張消失フラグＦ-が１であるか０であるかによって変化しないが（（４）式参照）、図８のフローチャートに示す１拡張リードソロモン符号の復号方法を実施する復号装置において、消失位置多項式計算回路２７４で求める消失位置多項式Ｅ(ｘ)は拡張消失フラグＦ+が１であるか０であるかによって変化する（（２３）式参照）。
【０１６８】
また、図６に示す復号装置２７０において、誤り位置判定回路２８１は、＃roots＝degσ(ｘ)の条件を判定してエラー信号ＥＲを出力するが、図８のフローチャートに示す１拡張リードソロモン符号の復号方法を実施する復号装置において、誤り位置判定回路２８１では、＃roots＝degσ(ｘ)−ｅ+flagの条件を判定してエラー信号ＥＲを出力するようになされている。
【０１６９】
また、図６に示す復号装置２７０において、エラー判定回路２８７は、ステップ２０５〜２０８の判定処理によってエラー信号ＥＲを出力するが、図８のフローチャートに示す１拡張リードソロモン符号の復号方法を実施する復号装置において、エラー判定回路２８７は、ステップ４０５〜４０９、４１２の判定処理によってエラー信号ＥＲを出力するように構成される。
【０１７０】
以上説明したように、第３の実施の形態においても、第１の実施の形態と同様に、１拡張リードソロモン符号の１パスでの混合訂正が可能となる。
【０１７１】
なお、上述した第３の実施の形態の図８のフローチャートにおける訂正判定可能ユニットＵ１（ステップ４０６〜４１２）の代わりに、図１１に示す訂正可能判定ユニットＵ２を用いてもよい。ユニットＵ２も、ユニットＵ１と同様に、σ(ｘ)，ω(ｘ)，Ｆ+，ｐ，εから訂正が可能であるか否かを判定する。
【０１７２】
まず、ステップ６００で、ｘ｜σ(ｘ)の条件を判定し、偽ならばステップ６０１に進み、真ならばステップ６０２に進む。ステップ６０１では、Ｆ+＝０の条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力し、真ならばステップ６０３に進む。一方、ステップ６０２では、ｘ｜ω(ｘ)の条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力し、真ならばステップ６０４に進む。
【０１７３】
ステップ６０３では、ステップ６００，６０１の判定結果から、拡張シンボル位置に誤りがないことが判明しているので、拡張誤りフラグｅ+flagを０に設定し、その後にステップ６０５に進む。また、ステップ６０４では、ステップ６００，６０２の判定結果から、拡張シンボル位置に誤りがあることが判明しているので、ｅ+flagを１に設定し、その後にステップ６０５に進む。
【０１７４】
ステップ６０５では、上述の（９）式の条件を判定し、偽ならばステップ４１６に進んでエラー信号を出力し、真ならばステップ４１３に進む。
【０１７５】
次に、第４の実施の形態について説明する。この第４の実施の形態は、２拡張リードソロモン符号において通常訂正と消失訂正を同時に行う混合訂正の復号法である。
【０１７６】
図１２は、第４の実施の形態における２拡張リードソロモン符号の復号化のフローチャートを示している。
【０１７７】
まず、ステップ４０００では、受信語Ｒ＝（Ｒ-，Ｒ+，Ｒ0，Ｒ1，・・・，Ｒn-1）と消失フラグＦ＝（Ｆ-，Ｆ+，Ｆ0，Ｆ1，・・・，Ｆn-1）が与えられる。上述した従来のリードソロモン符号の復号法との違いは、第１拡張受信シンボルＲ-と、第２拡張受信シンボルＲ+と、第１拡張消失フラグＦ-と、第２拡張消失フラグＦ+とが追加されたことである。
【０１７８】
次に、ステップ４００１で、消失数εを、（２７）式により求めると共に、消失位置多項式Ｅ(ｘ)を上述の（２３）式により求める。上述した従来のリードソロモン符号の復号法との違いは、消失数εに第１拡張消失フラグＦ-と第２拡張消失フラグＦ+を計算に入れたこと、および消失位置多項式にＦ+に対応したｘを追加したことである。
【０１７９】
【数２２】
0004423519.tif 000023
【０１８０】
次に、ステップ４００２で、（２８）式に示すようなパリティ検査行列Ｈを用いて、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を、上述の（６）式から求める。シンドロームＳの計算方法は、図１３を用いて後で説明する。そして、上述の（７）式に示すようなシンドローム多項式Ｓ(ｘ)を求める。
【０１８１】
【数２３】
0004423519.tif 000024
【０１８２】
次に、ステップ４００３で、消失位置多項式Ｅ(ｘ)およびシンドローム多項式Ｓ(ｘ)を用いて、上述の（８）式に示すように、修正シンドローム多項式Ｓm(ｘ)を求める。
【０１８３】
次に、ステップ４００４で、修正シンドローム多項式Ｓm(ｘ)を用いて、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を求める。誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)の計算方法は、図１のフローチャートのステップ２０４における計算方法（図３参照）と同様である。
【０１８４】
次に、ステップ４００５で、degω(ｘ)≦degσ(ｘ)の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４００６に進む。ここで、degω(ｘ)は誤り評価多項式ω(ｘ)の次数であり、degσ(ｘ)は誤り位置多項式σ(ｘ)の次数である。
【０１８５】
次に、ステップ４００６では、ｘ｜σ(ｘ)の条件を判定する。これは、σ(ｘ)がｘで割り切れるか否かを判定しており、割り切れる場合（拡張シンボル位置が誤り位置に含まれている）は真、割り切れない場合は偽となる。判定結果が真ならば第２拡張シンボル位置に誤りがあるのでステップ４００７に進み、偽ならば第２拡張シンボル位置に誤りがないのでステップ４０１３に進む。
【０１８６】
ステップ４００７では、ｘ｜ω(ｘ)の条件を判定する。これは、ω(ｘ)がｘで割り切れるか否かを判定しており、割り切れる場合は真、割り切れない場合は偽となる。判定結果が、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４００８に進む。このステップ４００８では、degω(ｘ)＝degσ(ｘ)の条件を判定し、真ならばステップ４００９に進み、偽ならばステップ４０１１に進む。
【０１８７】
ステップ４００９では、（２９）式の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４０１０に進む。このステップ４０１０では、ステップ４００５，４００８の判定結果から第１拡張シンボル位置に誤りがあることが判明しており、またステップ４００５，４００６の判定結果から第２拡張シンボル位置に誤りがあることが判明しているので、第１拡張誤りフラグｅ-flagを１、第２拡張誤りフラグｅ+flagを１に設定し、その後にステップ４０１８に進む。
【０１８８】
【数２４】
0004423519.tif 000025
【０１８９】
ステップ４０１１では、（１９）式の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４０１２に進む。このステップ４０１２では、ステップ４００５，４００８の判定結果から第１拡張シンボル位置に誤りがないことが判明しており、またステップ４００５，４００６の判定結果から第２拡張シンボル位置に誤りがあることが判明しているので、第１拡張誤りフラグｅ-flagを０、第２拡張誤りフラグｅ+flagを１に設定し、その後にステップ４０１８に進む。
【０１９０】
ステップ４０１３では、degω(ｘ)＝degσ(ｘ)の条件を判定し、真ならばステップ４０１４に進み、偽ならばステップ４０１６に進む。
【０１９１】
ステップ４０１４では、（１９）式の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４０１５に進む。このステップ４０１５では、ステップ４００５，４０１３の判定結果から第１拡張シンボル位置に誤りがあることが判明しており、またステップ４００５，４００６の判定結果から第２拡張シンボル位置に誤りがないことが判明しているので、第１拡張誤りフラグｅ-flagを１、第２拡張誤りフラグｅ+flagを０に設定し、その後にステップ４０１８に進む。
【０１９２】
ステップ４０１６では、（１４）式の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４０１７に進む。このステップ４０１７では、ステップ４００５，４０１３の判定結果から第１拡張シンボル位置に誤りがないことが判明しており、またステップ４００５，４００６の判定結果から第２拡張シンボル位置に誤りがないことが判明しているので、第１拡張誤りフラグｅ-flagを０、第２拡張誤りフラグｅ+flagを０に設定し、その後にステップ４０１８に進む。
【０１９３】
ステップ４０１８では、誤り位置多項式σ(ｘ)を使用して誤り位置を検出する。誤り位置の計算方法は、図１のフローチャートのステップ２１１における計算方法（図４参照）と同様である。このとき、第１拡張シンボルＲ-と第２拡張シンボルＲ+に対する誤り位置の検出は行わない。そして、ステップ４０１９で、ステップ４０１８で検出した誤りの数＃rootsと、誤り位置多項式σ（ｘ）の次数degσ(ｘ)から第２拡張誤りフラグｅ+flagを減算した数から、＃roots＝degσ(ｘ)−ｅ+flagの条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４０２０に進む。ここで、誤り位置多項式σ（ｘ）の次数degσ(ｘ)から第２拡張誤りフラグｅ+flagを減算しているのは、誤り位置多項式σ（ｘ）には第２拡張シンボルに対応する第２拡張誤りｅ+の位置を含むためである。
【０１９４】
次に、ステップ４０２０では、ステップ４００４で求められた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、ステップ４０１８で検出した誤り位置ｉとから、位置ｉでの誤り値ｅiを計算すると共に、この誤り値ｅｉとステップ４００２で得られたシンドロームＳの第０要素Ｓ0を用いて第１拡張誤り値ｅ-を計算し、この誤り値ｅｉとシンドロームＳの第（ｐ−１）要素Ｓp-1を用いて第２拡張誤り値ｅ+を計算し、さらに受信語Ｒと誤り位置ｉ、誤り値ｅi、第１拡張誤り値ｅ-、第２拡張誤り値ｅ+から、推定情報Ｉp＝（Ｃp-，Ｃp+，Ｃp0，Ｃp1，・・・，Ｃpk-1）を求める。推定情報Ｉpの計算方法は、図１４を用いて後で説明する。
【０１９５】
ここで、第１拡張シンボルＣp-は、拡張受信シンボルＣp-，Ｃp+以外の値を全て加算して得たものである。つまり、Ｃp-＝Ｃp0＋Ｃp1＋・・・＋Ｃpn-1である。一方、第２拡張シンボルＣp+は、拡張受信シンボルＣp-，Ｃp+以外のシンボルの値にシンボル位置に関係して値が決定される係数を乗算し、各乗算結果を加算して得たものである。つまり、Ｃp+＝Ｃp0＋Ｃp1αp-1＋Ｃp2α2(p-1)＋・・・＋Ｃpn-1α(n-1)(p-1)である。
【０１９６】
次に、ステップ４０２１で、ｅ-flag＝０の条件を判定し、偽ならばステップ４０２２に進み、真ならばステップ４０２３に進む。ステップ４０２２では、ｅ-≠０の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４０２４に進む。一方、ステップ４０２３では、ｅ-＝０の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならばステップ４０２４に進む。
【０１９７】
ステップ４０２４では、ｅ+flag＝０の条件を判定し、偽ならば推定情報Ｉpを出力して終了し、真ならばステップ４０２６に進む。ステップ４０２６では、ｅ+＝０の条件を判定し、偽ならばステップ４０２７に進んでエラー信号を出力して終了し、真ならば推定情報Ｉpを出力して終了する。
【０１９８】
図１３のフローチャートを用いて、受信語ＲからシンドロームＳを計算する方法を説明する。
【０１９９】
まず、ステップ４２００では、受信語Ｒ＝（Ｒ-，Ｒ+，Ｒ0，Ｒ1，・・・，Ｒn-1）を受け取る。そして、ステップ４２０１で、シンドロームＳの各要素（Ｓ0，Ｓ1，・・・，Ｓp-1）を受信語Ｒの要素Ｒ0で初期化する。
【０２００】
次に、ステップ４２０２で、シンドロームＳの第０要素Ｓ0から受信語Ｒの要素Ｒ-を減算し、その減算結果をＳ0とし、同様にシンドロームＳの第（ｐ−１）要素Ｓp-1から受信語Ｒの要素Ｒ+を減算し、その減算結果をＳp-1とする。また、ステップ４２０３で、カウンタｉを１に初期化する。そして、ステップ４２０４で、シンドロームＳの各要素を、上述の（１０）式によって更新する。
【０２０１】
次に、ステップ４２０５で、カウンタｉの値を１だけ増加させる。そして、ステップ４２０６で、ｉ＜ｎの条件を判定し、真ならばステップ４２０４に戻ってシンドローム計算を繰り返し、偽ならばステップ４２０７に進み、シンドロームＳ＝（Ｓ0，Ｓ1，・・・，Ｓp-1）を出力する。
【０２０２】
図１４のフローチャートを用いて、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、検出した誤り位置ｉとから、受信語Ｒの誤りを訂正する方法を説明する。
【０２０３】
まず、ステップ４３００で、変数ｗ-をシンドロームＳの第０要素Ｓ0でｗ-＝−Ｓ0として初期化する。同様に、変数ｗ+をシンドロームＳの第（ｐ−１）要素Ｓp-1でｗ+＝−Ｓp-1として初期化する。ｗ-は、第１拡張誤り値ｅ-を、上述した（２０）式に示すように計算するために使用する。ｗ+は、第２拡張誤り値ｅ+を、上述した（２５）式に示すように計算するために使用する。
【０２０４】
次に、ステップ４３０１で、カウンタｉを０に初期化する。そして、ステップ４３０２で、ｉ∈Ａの条件を判定し、真ならばカウンタｉの値は誤り位置を表しているのでステップ４３０３に進み、偽ならばカウンタｉの値は誤り位置ではないのでステップ４３０６に進む。
【０２０５】
ステップ４３０３では、誤り評価多項式ω(ｘ)と、誤り位置多項式σ(ｘ)の微分σ′(ｘ)と、誤り位置ｉを用いて、上述の（１６）式に示すように誤り値ｅiを計算し、ステップ４３０４に進む。このステップ４３０４では、推定符号語Ｃpのｉ番目の要素ＣpiをＲi−ｅiとして計算し、ステップ４３０５に進む。ステップ４３０５では、（３０）式、（３１）式に示すように、ｗ-，ｗ+を更新し、ステップ４３０７に進む。ステップ４３０６では、推定符号語Ｃpのｉ番目の要素ＣpiをＲiとして、ステップ４３０７に進む。
【０２０６】
【数２５】
0004423519.tif 000026
【０２０７】
ステップ４３０７では、カウンタｉの値を１だけ増加させる。そして、ステップ４３０８で、ｉ＜ｎの条件（終了条件）を判定し、真ならばステップ４３０２に戻って誤り値の計算を繰り返し、偽ならばステップ４３０９に進む。ステップ４３０９では、第１拡張誤り値ｅ-にｗ-の値を代入し、第２拡張誤り値ｅ+にｗ+の値を代入する。
【０２０８】
次に、ステップ４３１０で、推定第１拡張符号シンボルＣp-を、Ｃp-＝Ｒ-−ｅ-として設定し、第２推定拡張符号シンボルＣp+を、Ｃp+＝Ｒ+−ｅ+として設定する。そして、ステップ４３１１で、推定符号語Ｃpを、推定第１拡張符号シンボルＣp-、第２推定拡張符号シンボルＣp+および推定符号シンボルＣp0〜Ｃpn-1より、Ｃp＝（Ｃp-，Ｃp+，Ｃp0，・・・，Ｃpn-1）として設定する。
【０２０９】
次に、ステップ４３１２で、推定情報Ｉpを、推定符号語Ｃpより、Ｉp＝（Ｃp-，Ｃp+，Ｃp0，Ｃp1，・・・，Ｃpk-1）として設定して出力する。
【０２１０】
図１５は、図１２のフローチャートに示す２拡張リードソロモン符号の復号方法を実施する復号装置３４００の構成を示している。
【０２１１】
この復号装置３４００は、受信語（入力データ）Ｒを入力する入力端子３４０１と、受信語Ｒに対応した消失フラグＦを入力する入力端子３４０２とを有している。
【０２１２】
また、復号装置３４００は、受信語Ｒからシンドローム多項式Ｓ(ｘ)を得るためのシンドローム多項式計算回路３４０３（図１２のステップ４００２参照）と、消失フラグＦから消失位置多項式Ｅ(ｘ)を得るための消失位置多項式計算回路３４０４（図１２のステップ４００１参照）と、消失フラグＦから消失数εを求めるための消失数計算回路３４０５（図１２のステップ４００１参照）とを有している。
【０２１３】
また、復号装置３４００は、シンドローム多項式Ｓ(ｘ)、消失位置多項式Ｅ(ｘ)から修正シンドローム多項式Ｓm(ｘ)を求め、この修正シンドローム多項式Ｓm(ｘ)と消失位置多項式Ｅ(ｘ)から誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)を求める誤り多項式計算回路３４０６（図１２のステップ４００４参照）を有している。
【０２１４】
また、復号装置３４００は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から受信語Ｒの各要素Ｒiの誤り値ｅiを求める誤り値計算回路３４０７（図１４のステップ４３０３参照）と、受信語Ｒの各要素Ｒｉのタイミングを、誤り値計算回路３４０７より出力される誤り値ｅiのタイミングに合わせるための受信語遅延回路３４０８と、受信語Ｒの各要素Ｒiより誤り値ｅiを減算する減算器３４０９（図１４のステップ４３０４参照）とを有している。
【０２１５】
また、復号装置３４００は、減算器３４０９の出力Ｒi−ｅiまたは受信語遅延回路３４０８の出力Ｒiのいずれかを選択的に取り出す信号選択回路３４１０と、誤り位置多項式σ(ｘ)から誤り位置ｉを検出し、誤り位置ｉに応じた選択信号ＳＥＬを出力すると共に、＃roots＝degσ(ｘ)−ｅ+flagの条件を判定し（図１２のステップ４０１９参照）、偽であるときはエラー信号ＥＲを出力する誤り位置判定回路３４１１とを有している。ここで、誤り位置判定回路３４１１より出力される選択信号ＳＥＬは信号選択回路３４１０に供給され、信号選択回路３４１０では誤り位置ｉで減算器３４０９の出力Ｒi−ｅiが取り出され、誤り位置でない位置ｉで受信語遅延回路３４０８の出力Ｒiが取り出されるようになされている。
【０２１６】
また、復号装置３４００は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から第１拡張誤り値ｅ-を求める第１拡張誤り値計算回路３４１２（図１４のステップ４３０９参照）と、信号選択回路３４１０の出力より第１拡張誤り値ｅ-を減算する減算器３４１３（図１４のステップ４３１０参照）と、減算器３４１３の出力または信号選択回路３４１０の出力のいずれかを選択的に取り出す信号選択回路３４１４とを有している。
【０２１７】
また、復号装置３４００は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から第２拡張誤り値ｅ+を求める第２拡張誤り値計算回路３４１５（図１４のステップ４３０９参照）と、信号選択回路３４１４の出力より第２拡張誤り値ｅ+を減算する減算器３４１６（図１４のステップ４３１０参照）と、減算器３４１６の出力または信号選択回路３４１４の出力のいずれかを選択的に取り出す信号選択回路３４１７とを有している。
【０２１８】
また、復号装置３４００は、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から第１拡張シンボル位置に誤りがあるか否かを判定し、第１拡張誤りフラグｅ-flagを設定する第１拡張誤りフラグ計算回路３４１８および誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から第２拡張シンボル位置に誤りがあるか否かを判定し、第２拡張誤りフラグｅ+flagを設定する第２拡張誤りフラグ計算回路３４１９（図１２のステップ４０１０，４０１２，４０１５，４０１７参照）と、信号選択回路３４１７の出力を導出する出力端子３４２０とを有している。
【０２１９】
ここで、第１拡張シンボル位置に誤りがあると判定されるときはｅ-flag＝１とされ、第１拡張シンボル位置に誤りがないと判定されるときはｅ-flag＝０とされる。同様に、第２拡張シンボル位置に誤りがあると判定されるときはｅ+flag＝１とされ、第２拡張シンボル位置に誤りがないと判定されるときはｅ+flag＝０とされる。計算回路３４１８より出力される第１拡張誤りフラグｅ-flagは信号選択回路３４１４に供給される。計算回路３４１９より出力される第２拡張誤りフラグｅ+flagは信号選択回路３４１７に供給される。
【０２２０】
信号選択回路３４１４では、信号選択回路３４１０より第１拡張受信シンボルＲ-が出力される際には、ｅ-flag＝１であるときは減算器３４１３の出力Ｒ-−ｅ-が第１推定拡張シンボルＣp-として取り出され、ｅ-flag＝０であるときは信号選択回路３４１０の出力Ｒ-が第１推定拡張シンボルＣp-として取り出されるようになされている。また、信号選択回路３４１４では、信号選択回路３４１０より第１拡張受信シンボルＲ-以外のシンボルが出力される際には、信号選択回路３４１０の出力のみが取り出される。
【０２２１】
信号選択回路３４１７では、信号選択回路３４１４より第２拡張受信シンボルＲ+が出力される際には、ｅ+flag＝１であるときは減算器３４１６の出力Ｒ+−ｅ+が第２推定拡張シンボルＣp+として取り出され、ｅ+flag＝０であるときは信号選択回路３４１４の出力Ｒ+が第２推定拡張シンボルＣp+として取り出されるようになされている。また、信号選択回路３４１７では、信号選択回路３４１４より第２拡張受信シンボルＲ+以外のシンボルが出力される際には、信号選択回路３４１４の出力のみが取り出される。
【０２２２】
また、復号装置３４００は、誤り多項式計算回路３４０６からの誤り位置多項式σ（ｘ）および誤り評価多項式ω（ｘ）と、消失数計算回路３４０５からの消失数εとから、σ（ｘ）の次数degσ（ｘ）およびω（ｘ）の次数degω（ｘ）を評価して（図１２のステップ４００５〜４００９，４０１１，４０１３，４０１４，４０１６参照）、エラー信号ＥＲを出力するエラー判定回路３４２１を有している。
【０２２３】
また、復号装置３４００は、第１拡張誤り値計算回路３４１２からの第１拡張誤り値ｅ-と第１拡張誤りフラグ計算回路３４１８からの第１拡張誤りフラグｅ-flagとから、第１拡張誤りエラーを判定し（図１２のステップ４０２１〜４０２３参照）、エラー信号ＥＲを出力する第１拡張誤りエラー判定回路３４２２と、第２拡張誤り値計算回路３４１５からの第２拡張誤り値ｅ+と第２拡張誤りフラグ計算回路３４１９からの第２拡張誤りフラグｅ+flagとから、第２拡張誤りエラーを判定し（図１２のステップ４０２４，４０２６参照）、エラー信号ＥＲを出力する第２拡張誤りエラー判定回路３４２３とを有している。
【０２２４】
また、復号装置３４００は、誤り位置判定回路３４１１、エラー判定回路３４２１、第１拡張誤りエラー判定回路３４２２および第２拡張誤りエラー判定回路３４２３より出力されるエラー信号ＥＲが入力されるオアゲート３４２４と、このオアゲート３４２４の出力を導出する出力端子３４２５とを有している。
【０２２５】
なお、オアゲート３４２４の出力は信号選択回路３４１０，３４１４，３４１７に供給され、オアゲート３４２４の出力としてエラー信号ＥＲが得られる場合には、信号選択回路３４１０では選択信号ＳＥＬの状態に依らずに常に受信語遅延回路３４０８の出力Ｒiが取り出され、信号選択回路３４１４では第１拡張誤りフラグｅ-flagの状態に依らずに常に信号選択回路３４１０の出力が取り出され、さらに信号選択回路３４１７では第２拡張誤りフラグｅ+flagの状態に依らずに常に信号選択回路３４１４の出力が取り出されるようにされている。
【０２２６】
図１５に示す復号装置３４００の動作を説明する。
【０２２７】
入力端子３４０１に入力された受信語（入力データ）Ｒはシンドローム多項式計算回路３４０３に供給される。そして、この計算回路３４０３では、受信語ＲからシンドロームＳが計算され、シンドローム多項式Ｓ(ｘ)が求められる。一方、入力端子３４０２に入力された消失フラグＦは消失位置多項式計算回路３４０４に供給される。そして、この計算回路３４０４では、消失フラグＦから消失位置多項式Ｅ(ｘ)が求められる。また、入力端子３４０２に入力された消失フラグＦは消失数計算回路３４０５に供給される。そして、この計算回路３４０５では、消失フラグＦより消失数εが求められる。
【０２２８】
計算回路３４０３で得られたシンドローム多項式Ｓ(ｘ)と、計算回路３４０４で得られた消失位置多項式Ｅ(ｘ)は、誤り多項式計算回路３４０６に供給される。そして、この計算回路３４０６では、シンドローム多項式Ｓ(ｘ)、消失位置多項式Ｅ(ｘ)から修正シンドローム多項式Ｓm(ｘ)が求められ、さらにこの修正シンドローム多項式Ｓm(ｘ）と消失位置多項式Ｅ(ｘ)から誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)が求められる。
【０２２９】
計算回路３４０６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は誤り値計算回路３４０７に供給される。この計算回路３４０７では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から、受信語Ｒの各要素Ｒiの誤り値ｅiが順次求められる。そして、この誤り値ｅiが減算器３４０９に供給されて、受信語遅延回路３４０８より出力される受信語Ｒの各要素Ｒiより減算される。
【０２３０】
また、計算回路３４０６で得られた誤り位置多項式σ(ｘ)は誤り位置判定回路３４１１に供給される。この誤り位置判定回路３４１１では、誤り位置多項式σ(ｘ)から誤り位置ｉが検出され、誤り位置ｉに応じた選択信号ＳＥＬが出力される。この選択信号ＳＥＬは信号選択回路３４１０に制御信号として供給される。そして、信号選択回路３４１０では、誤り位置ｉで減算器３４０９の出力Ｒi−ｅiが推定符号語Ｃpの要素Ｃpiとして取り出され、誤り位置ｉでない位置で受信語遅延回路３４０８の出力Ｒiが推定符号語Ｃpの要素Ｃpiとして取り出される。
【０２３１】
また、計算回路３４０６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は第１拡張誤り値計算回路３４１２に供給される。この計算回路３４１２では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から、第１拡張受信シンボルＲ-の誤り値、つまり第１拡張誤り値ｅ-が求められる。そして、この第１拡張誤り値ｅ-が減算器３４１３に供給されて、信号選択回路３４１０の出力より減算される。
【０２３２】
また、計算回路３４０６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は第１拡張誤りフラグ計算回路３４１８に供給される。この計算回路３４１８では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から第１拡張シンボル位置に誤りがあるか否かが判定され、第１拡張シンボル位置に誤りがあると判定されるときはｅ-flag＝１に設定され、第１拡張シンボル位置に誤りがないと判定されるときはｅ-flag＝０に設定される。
【０２３３】
この第１拡張誤りフラグｅ-flagは信号選択回路３４１４に制御信号として供給される。信号選択回路３４１４では、信号選択回路３４１０より第１拡張受信シンボルＲ-が出力される際には、ｅ-flag＝１であるときは減算器３４１３の出力Ｒ-−ｅ-が第１推定拡張シンボルＣp-として取り出され、ｅ-flag＝０であるときは信号選択回路３４１０の出力Ｒ-が第１推定拡張シンボルＣp-として取り出される。また、信号選択回路３４１４では、信号選択回路３４１０より第１拡張受信シンボルＲ-以外のシンボルが出力される際には、信号選択回路３４１０の出力のみが取り出される。
【０２３４】
また、計算回路３４０６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は第２拡張誤り値計算回路３４１５に供給される。この計算回路３４１５では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から、第２拡張受信シンボルＲ+の誤り値、つまり第２拡張誤り値ｅ+が求められる。そして、この第２拡張誤り値ｅ+が減算器３４１６に供給されて、信号選択回路３４１４の出力より減算される。
【０２３５】
また、計算回路３４０６で得られた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)は第２拡張誤りフラグ計算回路３４１９に供給される。この計算回路３４１９では、誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)から第２拡張シンボル位置に誤りがあるか否かが判定され、第２拡張シンボル位置に誤りがあると判定されるときはｅ+flag＝１に設定され、第２拡張シンボル位置に誤りがないと判定されるときはｅ+flag＝０に設定される。
【０２３６】
この第２拡張誤りフラグｅ+flagは信号選択回路３４１７に制御信号として供給される。信号選択回路３４１７では、信号選択回路３４１４より第２拡張受信シンボルＲ+が出力される際には、ｅ+flag＝１であるときは減算器３４１６の出力Ｒ+−ｅ+が第２推定拡張シンボルＣp+として取り出され、ｅ+flag＝０であるときは信号選択回路３４１４の出力Ｒ+が第２推定拡張シンボルＣp+として取り出される。また、信号選択回路３４１７では、信号選択回路３４１４より第２拡張受信シンボルＲ+以外のシンボルが出力される際には、信号選択回路３４１４の出力のみが取り出される。
【０２３７】
これにより、信号選択回路３４１７からは誤り訂正された推定符号語Ｃp（第１推定拡張シンボルＣp-、第２推定拡張シンボルＣp+を含む）が取り出され、この推定符号語Ｃpが出力データとして出力端子３４２０に導出される。そして、推定符号語Ｃpよりパリティシンボル部分を除くことで、推定情報Ｉp＝（Ｃp-，Ｃp+，Ｃp0，Ｃｐ1，・・・，Ｃpk-1）が得られる。
【０２３８】
なお、誤り位置判定回路３４１１、エラー判定回路３４２１、第１拡張誤りエラー判定回路３４２２または第２拡張誤りエラー判定回路３４２３よりエラー信号ＥＲが出力される場合、このエラー信号ＥＲが出力端子３４２５に導出されると共に、このエラー信号ＥＲが信号選択回路３４１０，３４１４，３４１７に供給される。そして、信号選択回路３４１０では選択信号ＳＥＬの状態に依らずに常に受信語遅延回路３４０８の出力Ｒiが取り出され、信号選択回路３４１４では第１拡張誤りフラグｅ-flagの状態に依らずに常に信号選択回路３４１０の出力が取り出され、信号選択回路３４１７では第２拡張誤りフラグｅ+flagの状態に依らずに常に信号選択回路３４１４の出力が取り出される。これにより、出力端子３４２５にエラー信号ＥＲが導出される状態では、受信語Ｒが誤り訂正されず、出力端子３４２０にそのまま出力されることとなる。
【０２３９】
以上説明したように、第４の実施の形態においては、２拡張リードソロモン符号の１パスでの混合訂正が可能となる。したがって、２拡張リードソロモン符号の混合訂正を短時間で行うことが可能となり、またハードウェア規模も小さくできるという効果がある。
【０２４０】
次に、第５の実施の形態について説明する。この第５の実施の形態も、２拡張リードソロモン符号において通常訂正と消失訂正を同時に行う混合訂正の復号法に係るものである。図１６は、第５の実施の形態における２拡張リードソロモン符号の復号化のフローチャートを示している。
【０２４１】
まず、ステップ４１００〜４１０４の処理をする。このステップ４１００〜４１０４では、図１２のステップ４０００〜４００４とそれぞれ同様の処理をする。
【０２４２】
次に、ステップ４１３０で、訂正可能判定数ｈを、ｈ＝２degσ(ｘ)−εとして設定する。訂正可能判定数ｈは、後述するステップ４１４１で使用するが、最終的には、（３２）式に示すようになる。
【０２４３】
【数２６】
0004423519.tif 000027
【０２４４】
次に、ステップ４１３１で、degω(ｘ)≦degσ(ｘ)の条件を判定し、偽ならばステップ４１２７に進んでエラー信号を出力して終了し、真ならばステップ４１３２に進む。ステップ４１３２では、degω(ｘ)＝degσ(ｘ)の条件を判定し、偽ならばステップ４１３３に進み、真ならばステップ４１３５に進む。
【０２４５】
ステップ４１３３では、ステップ４１３１，４１３２の判定結果から、第１拡張シンボル位置に誤りがあることが判明しているので、第１拡張誤りフラグｅ-flagを１に設定し、その後にステップ４１３４で、ｈ＝ｈ＋２として訂正可能判定数ｈを更新し、ステップ４１３６に進む。ステップ４１３５では、ステップ４１３１，４１３２の判定結果から第１拡張シンボル位置に誤りがないことが判明しているので、第１拡張誤りフラグｅ-flagを０に設定し、その後にステップ４１３６に進む。
【０２４６】
ステップ４１３６では、ｘ｜σ(ｘ)の条件を判定する。これは、σ(ｘ)がｘで割り切れるか否かを判定しており、割り切れる場合は真、割り切れない場合は偽となる。判定の結果が真ならば第２拡張シンボル位置に誤りがあるのでステップ４１３７に進み、偽ならば第２拡張シンボル位置に誤りがないのでステップ４１４０に進む。
【０２４７】
ステップ４１３７では、ｘ｜ω(ｘ)の条件を判定する。これは、ω(ｘ)がｘで割り切れるか否かを判定しており、割り切れる場合は真、割り切れない場合は偽となる。判定の結果が偽ならば、ステップ４１２７に進んでエラー信号を出力して終了し、真ならばステップ４１３８に進む。
【０２４８】
ステップ４１３８では、ステップ４１３１，４１３６の判定結果から、第２拡張シンボル位置に誤りがあることが判明しているので、第２拡張誤りフラグｅ+flagを１に設定し、その後にステップ４１３９で、ｈ＝ｈ＋２として訂正可能判定数ｈを更新し、ステップ４１４１に進む。ステップ４１４０では、ステップ４１３１，４１３６の判定結果から第２拡張シンボル位置に誤りがないことが判明しているので、第２拡張誤りフラグｅ+flagを０に設定し、その後にステップ４１４１に進む。
【０２４９】
次に、ステップ４１４１で、ｈ≦ｐの条件を判定し、偽ならばステップ４１２７に進んでエラー信号を出力して終了し、真ならばステップ４１１８に進む。そして、ステップ４１１８〜４１２６の処理をする。このステップ４１１８〜４１２６では、図１２のステップ４０１８〜４０２６とそれぞれ同様の処理をする。
【０２５０】
すなわち、ステップ４１１８では、誤り位置多項式σ(ｘ)を使用して、シンボルＲ0〜Ｒn-1に対する誤り位置を検出する。そして、ステップ４１１９で、ステップ４１１８で検出した誤りの数＃rootsと、誤り位置多項式σ（ｘ）の次数degσ(ｘ)から第２拡張誤りフラグｅ+flagを減算した数とから、＃roots＝degσ(ｘ)−ｅ+flagの条件を判定し、偽ならばステップ４１２７に進んでエラー信号を出力して終了し、真ならばステップ４１２０に進む。
【０２５１】
ステップ４１２０では、ステップ４１０４で求められた誤り評価多項式ω(ｘ)および誤り位置多項式σ(ｘ)と、ステップ４１１８で検出した誤り位置ｉとから、位置ｉでの誤り値ｅiを計算すると共に、この誤り値ｅｉとステップ４１０２で得られたシンドロームＳの第０要素Ｓ0を用いて第１拡張誤り値ｅ-を計算し、この誤り値ｅｉとシンドロームＳの第（ｐ−１）要素Ｓp-1を用いて第２拡張誤り値ｅ+を計算し、さらに受信語Ｒと誤り位置ｉ、誤り値ｅi、第１拡張誤り値ｅ-、第２拡張誤り値ｅ+から、推定情報Ｉp＝（Ｃp-，Ｃp+，Ｃp0，Ｃp1，・・・，Ｃpk-1）を求める。
【０２５２】
そして、ステップ４１２１で、ｅ-flag＝０の条件を判定し、偽ならばステップ４１２２に進み、真ならばステップ４１２３に進む。ステップ４１２２では、ｅ-≠０の条件を判定し、偽ならばステップ４１２７に進んでエラー信号を出力して終了し、真ならばステップ４１２４に進む。一方、ステップ４１２３では、ｅ-＝０の条件を判定し、偽ならばステップ４１２７に進んでエラー信号を出力して終了し、真ならばステップ４１２４に進む。
【０２５３】
ステップ４１２４では、ｅ+flag＝０の条件を判定し、偽ならば推定情報Ｉpを出力して終了し、真ならばステップ４１２６に進む。ステップ４１２６では、ｅ+＝０の条件を判定し、偽ならばステップ４１２７に進んでエラー信号を出力して終了し、真ならば推定情報Ｉpを出力して終了する。
【０２５４】
図１６のフローチャートに示す２拡張リードソロモン符号の復号方法を実施する復号装置は、エラー判定回路３４２１の動作が異なる他は、図１５に示す復号装置３４００と同様に構成される。すなわち、図１５に示す復号装置３４００において、エラー判定回路３４２１は、ステップ４００５〜４００９，４０１１，４０１３，４０１４，４０１６の判定処理によってエラー信号ＥＲを出力するが、図１６のフローチャートに示す２拡張リードソロモン符号の復号方法を実施する復号装置において、エラー判定回路３４２１は、ステップ４１３１，４１３２，４１３６，４１３７，４１４１の判定処理によってエラー信号ＥＲを出力するように構成される。
【０２５５】
以上説明したように、第５の実施の形態においても、第４の実施の形態と同様に、２拡張リードソロモン符号の１パスでの混合訂正が可能となる。
【０２５６】
なお、上述第１〜第５の実施の形態において、修正シンドローム多項式Ｓm(ｘ)と消失位置多項式Ｅ(ｘ)から、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を計算する方法としてユークリッドの互除法を用いたアルゴリズムによる方法（図３参照）を採用したが、その他のアルゴリズム、例えば、バーレカンプ・マッシーアルゴリズムによる方法を採用してもよい。
【０２５７】
図１７のフローチャートを用いて、修正シンドローム多項式Ｓm(ｘ)から、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を計算する方法（バーレカンプ・マッシーアルゴリズムによる方法）を説明する。
【０２５８】
まず、ステップ５００で、ｋ，σ(0)(ｘ)，Ｌ，Ｔ(ｘ)を、ｋ＝０、σ(0)(ｘ)＝１、Ｌ＝０、Ｔ(ｘ)＝ｘとして初期化する。そして、ステップ５０１で、カウンタｋを１だけ増加させると共に、（３３）式に示すように誤差値Δ(k)を更新する。
【０２５９】
【数２７】
0004423519.tif 000028
【０２６０】
次に、ステップ５０２で、Δ(k)＝０の条件を判定し、真ならばステップ５０７に進み、偽ならばステップ５０３に進む。ステップ５０３では、（３４）式に示すようにσ(k)(ｘ)を更新する。
【０２６１】
【数２８】
0004423519.tif 000029
【０２６２】
次に、ステップ５０４で、２Ｌ≧ｋの条件を判定し、真ならばステップ５０７に進み、偽ならばステップ５０５に進む。そして、ステップ５０５では、Ｌ＝ｋ−ＬとしてＬを更新する。
【０２６３】
次に、ステップ５０６で、（３５）式に示すようにＴ(ｘ)を更新し、その後にステップ５０７に進む。ステップ５０７では、Ｔ(ｘ)＝ｘＴ(ｘ)としてＴ(ｘ)をシフトする。
【０２６４】
【数２９】
0004423519.tif 000030
【０２６５】
次に、ステップ５０８で、ｋ＜ｐの条件（終了条件）を判定し、真ならばステップ５０１に戻って計算を繰り返し、偽ならばステップ５０９に進む。ステップ５０９では、σ(ｘ)＝σ(p)(ｘ)として誤り位置多項式σ(ｘ)を設定する。そして、ステップ５１０で、（３６）式に示すように、誤り評価多項式ω(ｘ)を求める。
【０２６６】
【数３０】
0004423519.tif 000031
【０２６７】
また、上述実施の形態において、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を計算する方法として、図３のフローチャートに示す方法の代わりに、図１８のフローチャートに示す方法を用いてもよい。図１８のフローチャートに示す方法は、図３のフローチャートに示す方法と同様に、ユークリッドの互除法を用いたアルゴリズムによる方法であるが、設定される初期値が相違する。
【０２６８】
すなわち、ステップ７００で、ｒ-1(ｘ)，ｒ0(ｘ)，ｕ-1(ｘ)，ｕ0(ｘ)，ｖ-1(ｘ)，ｖ0(ｘ)を、（３７）式に示すように、初期化する。図３のステップ２３０では、ｖ0(ｘ)には定数１を設定しているが、ステップ７００では、ｖ0(ｘ)には消失位置多項式Ｅ(ｘ)を設定する。
【０２６９】
【数３１】
0004423519.tif 000032
【０２７０】
また、ステップ７００に続いて、ステップ７０１〜７０５の処理をする。このステップ７０１〜７０５では、詳細説明は省略するが、図３のステップ２３１〜２３５とそれぞれ同様の処理を行う。次に、ステップ７０６では、σ(ｘ)＝ｖi(ｘ)、ω(ｘ)＝ｒi(ｘ)として、誤り評価多項式ω(ｘ)と誤り位置多項式σ(ｘ)を計算する。
【０２７１】
また、図１のステップ２１１、図７のステップ３１２、図８のステップ４１３、図１２のステップ４０１８、図１６のステップ４１１８では、図４のフローチャートに示すように、昇順で誤り位置を検出しているが、これを例えば降順で行ってもよい。さらに、任意の順番で検出を行ってもよい。
【０２７２】
また、上述実施の形態においては、この発明を１拡張リードソロモン符号、２拡張リードソロモン符号の復号に適用したものであるが、この発明は拡張ＢＣＨ符号（Bose-Chaudhuri-Hocquenghem code）等の復号にも同様に適用できることは勿論である。
【０２７３】
【発明の効果】
この発明によれば、拡張シンボルの通常訂正および消失訂正を行う手段を組み込むものであり、例えば１拡張リードソロモン符号、２拡張リードソロモン符号の１パスでの混合訂正が可能となる。したがって、拡張リードソロモン符号の混合訂正を短時間で行うことが可能となり、またハードウェア規模も小さくできるという効果がある。
【図面の簡単な説明】
【図１】第１の実施の形態における１拡張リードソロモン符号の復号化のフローチャートである。
【図２】１拡張リードソロモン符号のシンドローム計算のフローチャートである。
【図３】誤り評価多項式ω(ｘ)、誤り位置多項式σ(ｘ)の計算（ユークリッドの互除法を用いたアルゴリズム）のフローチャートである。
【図４】１拡張リードソロモン符号の誤り位置検出のフローチャートである。
【図５】１拡張リードソロモン符号の誤り訂正実行のフローチャートである。
【図６】１拡張リードソロモン符号の復号装置の構成例を示すブロック図である。
【図７】第２の実施の形態における１拡張リードソロモン符号の復号化のフローチャートである。
【図８】第３の実施の形態における１拡張リードソロモン符号の復号化のフローチャートである。
【図９】１拡張リードソロモン符号のシンドローム計算のフローチャートである。
【図１０】１拡張リードソロモン符号の誤り訂正実行のフローチャートである。
【図１１】訂正可能判定ユニットの他の例を示すフローチャートである。
【図１２】第４の実施の形態における２拡張リードソロモン符号の復号化のフローチャートである。
【図１３】２拡張リードソロモン符号のシンドローム計算のフローチャートである。
【図１４】２拡張リードソロモン符号の誤り訂正実行のフローチャートである。
【図１５】２拡張リードソロモン符号の復号装置の構成例を示すブロック図である。
【図１６】第５の実施の形態における２拡張リードソロモン符号の復号化のフローチャートである。
【図１７】誤り評価多項式ω(ｘ)、誤り位置多項式σ(ｘ)の計算（バーレカンプ・マッシーアルゴリズム）のフローチャートである。
【図１８】誤り評価多項式ω(ｘ)、誤り位置多項式σ(ｘ)の計算（ユークリッドの互除法を用いたアルゴリズム）のフローチャートである。
【図１９】誤り訂正システムを説明するための図である。
【図２０】従来のリードソロモン符号の復号化のフローチャートである。
【図２１】リードソロモン符号のシンドローム計算のフローチャートである。
【図２２】誤り評価多項式ω(ｘ)、誤り位置多項式σ(ｘ)の計算（ユークリッドの互除法を用いたアルゴリズム）のフローチャートである。
【図２３】リードソロモン符号の誤り位置検出のフローチャートである。
【図２４】リードソロモン符号の誤り訂正実行のフローチャートである。
【図２５】リードソロモン符号の復号装置の構成例を示すブロック図である。
【符号の説明】
２７０・・・１拡張リードソロモン符号の復号装置、２７１，２７２・・・入力端子、２７３・・・シンドローム多項式計算回路、２７４・・・消失位置多項式計算回路、２７５・・・消失数計算回路、２７６・・・誤り多項式計算回路、２７７・・・誤り値計算回路、２７８・・・受信語遅延回路、２７９，２８３・・・減算器、２８０，２８４・・・信号選択回路、２８１・・・誤り位置判定回路、２８２・・・拡張誤り値計算回路、２８５・・・拡張誤りフラグ計算回路、２８６，２９０・・・出力端子、２８７・・・エラー判定回路、２８８・・・拡張エラー判定回路、２８９・・・オアゲート、３４００・・・２拡張リードソロモン符号の復号装置、３４０１，３４０２・・・入力端子、３４０３・・・シンドローム多項式計算回路、３４０４・・・消失位置多項式計算回路、３４０５・・・消失数計算回路、３４０６・・・誤り多項式計算回路、３４０７・・・誤り値計算回路、３４０８・・・受信語遅延回路、３４０９，３４１３，３４１６・・・減算器、３４１０，３４１４，３４１７・・・信号選択回路、３４１１・・・誤り位置判定回路、３４１２・・・第１拡張誤り値計算回路、３４１５・・・第２拡張誤り値計算回路、３４１８・・・第１拡張誤りフラグ計算回路、３４１９・・・第２拡張誤りフラグ計算回路、３４２０，３４２５・・・出力端子、３４２１・・・エラー判定回路、３４２２・・・第１拡張誤りエラー判定回路、３４２３・・・第２拡張誤りエラー判定回路、３４２４・・・オアゲート
【図１】
0004423519.tif 000033
【図２】
0004423519.tif 000034
【図３】
0004423519.tif 000035
【図４】
0004423519.tif 000036
【図５】
0004423519.tif 000037
【図６】
0004423519.tif 000038
【図７】
0004423519.tif 000039
【図８】
0004423519.tif 000040
【図９】
0004423519.tif 000041
【図１０】
0004423519.tif 000042
【図１１】
0004423519.tif 000043
【図１２】
0004423519.tif 000044
【図１３】
0004423519.tif 000045
【図１４】
0004423519.tif 000046
【図１５】
0004423519.tif 000047
【図１６】
0004423519.tif 000048
【図１７】
0004423519.tif 000049
【図１８】
0004423519.tif 000050
【図１９】
0004423519.tif 000051
【図２０】
0004423519.tif 000052
【図２１】
0004423519.tif 000053
【図２２】
0004423519.tif 000054
【図２３】
0004423519.tif 000055
【図２４】
0004423519.tif 000056
【図２５】
0004423519.tif 000057