(57)【特許請求の範囲】
【請求項１】
素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正回路において、
受信した符号化データに含まれている誤りの位置を検出する誤り検出手段と、
受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手段と、
検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な誤りパターンの成分をそれぞれ求める基底誤り計算手段と、
検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な消失パターンの成分をそれぞれ求める基底消失計算手段と、
検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手段と、
検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手段と、
基本指数ｋとは独立な誤りパターンの成分それぞれと対応する誤り補正値との積を求め、乗算結果を最終的な誤りパターンとして出力する誤り補正値乗算手段と、
基本指数ｋとは独立な消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正値乗算手段と
を備えたことを特徴とするエラー訂正回路。
【請求項２】
素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正回路において、
受信した符号化データに含まれている誤りの位置を検出する誤り検出手段と、
受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手段と、
検出された各消失位置について、その消失位置に関する誤り位置多項式σの値を計算する誤り多項式計算手段と、
検出された各誤り位置について、その誤り位置に関する誤り位置多項式σの形式的導関数σ'の値を計算する誤り導関数計算手段と、
検出された各誤り位置について、その誤り位置に関する消失位置多項式ｕの値を計算する消失多項式計算手段と、
検出された各消失位置について、その消失位置に関する消失位置多項式ｕの形式的導関数ｕ'の値を計算する消失導関数計算手段と、
検出された各誤り位置について、誤り評価多項式ωの値を計算する誤り評価手段と、
検出された各消失位置について、誤り評価多項式ωの値を計算する消失評価手段と、
検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手段と、
検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手段と、
検出された各誤り位置に対応する誤り評価多項式の値と誤り補正値との積を求める誤り補正手段と、
検出された各消失位置に対応する消失評価多項式の値と消失補正値との積を求める消失補正手段と、
誤り導関数計算手段と消失多項式計算手段とによってそれぞれ得られた計算結果の積を求める誤り分母項算出手段と、
誤り多項式計算手段と消失導関数計算手段とによってそれぞれ得られた計算結果の積を求める消失分母項算出手段と、
誤り分母項算出手段と誤り補正手段とによって得られた計算結果に基づいて、誤りパターンを求める誤りパターン算出手段と、
消失分母項算出手段と消失補正手段とによって得られた計算結果に基づいて、消失パターンを求める消失パターン算出手段と
を備えたことを特徴とするエラー訂正回路。
【請求項３】
素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正する処理をコンピュータに実行させるためのエラー訂正プログラムにおいて、
受信した符号化データに含まれている誤りの位置を検出する誤り検出手順と、
受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手順と、
検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な誤りパターンの成分をそれぞれ求める誤りパターン計算手順と、
検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な消失パターンの成分をそれぞれ求める消失パターン計算手順と、
検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手順と、
検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手順と、
基本指数ｋとは独立な誤りパターンの成分それぞれと対応する誤り補正値との積を求め、最終的な誤りパターンとして出力する誤り補正手順と、
基本指数ｋとは独立な消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正手順と
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、受信したデータの誤り訂正を行なうエラー訂正回路およびエラー訂正プログラムに関し、特に、例えば、ＡＴＭを適用した光ファイバネットワークを構成する伝送装置などに適用されるエラー訂正回路およびエラー訂正プログラムに関する。
エラー訂正技術は、様々なディジタルシステムに広く利用されており、データの信頼性を確保するうえで非常に重要な要素技術である。
【０００２】
中でも、リードソロモン（Reed-Solomon）符号に代表されるＢＣＨ符号による符号化と、復号化過程における誤り訂正とを組み合わせたエラー訂正技術は、有線および無線のデータ通信分野はもちろん、磁気記録や光磁気記録などのデータ記録技術の分野においても広く利用されている。
【０００３】
【従来の技術】
リードソロモン符号によって符号化された符号化データを復号するデコーダを開発する際に重要なポイントは、生成多項式からどのような誤り位置多項式および消失位置多項式を導くか、そして、導いた誤り位置多項式および消失位置多項式から誤りパターンおよび消失パターンを求める過程をいかにして装置化するかである。
リードソロモン符号に用いられる様々な生成多項式について、その解法が研究されており、それぞれの用途に合った誤り位置多項式および消失位置多項式が導かれている。
【０００４】
例えば、特開平６‐１９７０２６号公報は、式(１)のように表される生成多項式について、誤り位置多項式および消失位置多項式を導き、式(２)および式(３)によって誤りパターンＹiおよび消失パターンＶiをそれぞれ計算する方法を開示している。
【数１】
0003889988.tif 000002
なお、特開平６‐１９７０２６号公報で開示された誤りパターンＹiおよび消失パターンＶiを表す数式において誤り位置Ｘiの逆数を示すＸi-1および消失位置Ｕiの逆数を示すＵi-1は、式(２)および式(３)では、２進法の素多項式であるχ8＋χ7＋χ2＋χ＋１の根αを用いて表されている。
【０００５】
更に、特開平６‐１９７０２６号公報は、誤りパターンＹiおよび消失パターンＶiをシンドローム多項式から求める処理と、求めた誤りを訂正する処理とを実行するデータ消失訂正回路を開示している。
図６に、上述した公報で開示されたデータ消失訂正回路の概略構成を示す。
図６に示した誤り位置検出部４１１は、チェンサーチ(Chien search)によって、受信データに含まれているビット誤りおよび消失を検出し、検出したビット誤り位置α-iをそれぞれ誤り分母算出部４１２および誤り評価値算出部４１３に入力し、また、消失位置を消失分母算出部４１４および消失評価値算出部４１５に入力する。
【０００６】
図６に示した誤り分母算出部４１２において、微分値算出部４２１および消失多項式計算部４２２は、入力された誤り位置α-iにおける誤り多項式の導関数σ'(α-i) の値および消失多項式の値を算出し、得られた値を乗算器４２３に入力する。また、図６に示した消失分母算出部４１４において、微分値算出部４２４および誤り多項式計算部４２５は、入力された消失位置α-iにおける消失多項式の導関数ｕ'(α-i) の値および誤り多項式σ(α-i)の値を算出し、得られた値を乗算器４２６に入力する。これらの計算と並行して、誤り評価値算出部４１３により、ビット誤り位置α-iにおける誤り評価多項式ω(α-i)の値が計算され、消失評価値算出部４１５により、消失位置Ｕｉにおける誤り評価多項式ωの値が計算されて、それぞれ乗算器４１６，４１７に入力される。図６に示したデータ消失訂正回路においてＲＯＭ４２７には、上述した乗算器４２３，４２６によって得られることが想定される全ての値に対応して、その逆元値が格納されている。そして、誤り位置検出部４１１によってビット誤り位置α-iおよび消失位置α-iの検出タイミングに応じて、セレクタ４２８が、対応する乗算器４２３，４２６の出力を選択的にＲＯＭ４２７に入力し、これに応じて、ＲＯＭ４２７から読み出された逆元値が、対応する乗算器４１６，４１７に入力される。つまり、ビット誤り位置α-iの検出タイミングに応じてＲＯＭ４２７から読み出された逆元値は、誤り評価値算出部４１３による計算結果とともに乗算器４１６に入力され、この乗算器４１６による演算結果が誤りパターンとして出力される。一方、消失位置α-iの検出タイミングに応じてＲＯＭ４２７から読み出された逆元値は、消失評価値算出部４１５による計算結果とともに乗算器４１７に入力され、この乗算器４１７による演算結果が消失パターンとして出力される。
【０００７】
【発明が解決しようとする課題】
ところで、ＡＴＭアダプテーションレイヤ（ＡＡＬ）に関するＩＴＵ‐Ｔの勧告Ｉ．３６３．１では、コンバージェンスサブレイヤ(ＣＳ)において適用すべき誤り訂正方法として、式(４)のように、基本指数ｋを用いて表される生成多項式を用いたリードソロモン符号を利用した誤り訂正技術が推奨されている。
【数２】
0003889988.tif 000003
図６に示したデータ消失訂正回路は、式(１)に示した生成多項式に対応したものであり、そのままでは、式(４)に示した生成多項式から導かれる誤りパターン及び消失パターンを求めることはできない。しかしながら、式(４)に示した生成多項式から、上述した式(２)、(３)に類似した形式を持つ誤り多項式および消失多項式を導くことができれば、図６に示したデータ消失訂正回路に若干の変形を加えることによって、ＩＴＵ‐Ｔの勧告Ｉ．３６３．１に適合したエラー訂正回路を実現することができる。
【０００８】
本発明は、既存の誤りパターンおよび消失パターンの計算に用いられている回路の基本構造を利用しつつ、基本指数を用いて表された生成多項式に従って符号化された符号化データに、伝送過程において発生したエラーを訂正するための誤りパターンおよび消失パターンを求めることが可能なエラー訂正回路およびエラー訂正プログラムを提供することを目的とする。
【０００９】
【課題を解決するための手段】
図１に、本発明にかかわる第１のエラー訂正回路の原理ブロック図を示す。
請求項１の発明は、素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正回路において、受信した符号化データに含まれている誤りの位置を検出する誤り検出手段１１１と、受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手段１１２と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な誤りパターンの成分をそれぞれ求める基底誤り計算手段１１３と、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な消失パターンの成分をそれぞれ求める基底消失計算手段１１４と、検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手段１１５と、検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手段１１６と、基本指数ｋとは独立な誤りパターンの成分それぞれと対応する誤り補正値との積を求め、乗算結果を最終的な誤りパターンとして出力する誤り補正値乗算手段１１７と、基本指数ｋとは独立な消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正値乗算手段１１８とを備えたことを特徴とする。
【００１０】
請求項１の発明では、誤り検出手段１１１および消失検出手段１１２によってそれぞれ検出された誤り位置および消失位置に基づいて、基底誤り計算手段１１３および誤り補正値算出手段１１５により、基本指数ｋとは独立な誤りパターンの各成分および基本指数ｋに関する誤り補正値を算出し、また、基底消失計算手段１１４および消失補正値算出手段１１６により、基本指数ｋとは独立な消失パターンの各成分および基本指数ｋに関する消失補正値を算出する。そして、基底誤り計算手段１１３によって得られた誤りパターンの各成分と基本指数ｋに関する誤り補正値とを、誤り補正値乗算手段１１７によって乗算することにより、基本指数ｋとは独立な誤りパターンの各成分に基本指数による成分を合成し、最終的な誤りパターンを求める。同様に、基底消失計算手段１１４によって得られた消失パターンの各成分と基本指数ｋに関する消失補正値とを、消失補正値乗算手段１１８によって乗算することにより、基本指数ｋとは独立な消失パターンの各成分に基本指数による成分を合成し、最終的な消失パターンを求める。
【００１１】
このように、基本指数による影響を誤り補正値および消失補正値として分離しているので、誤りパターン計算手段１１３および消失パターン計算手段１１４に、既存の回路やアルゴリズムを利用することが可能である。
図２に、本発明にかかわる第２のエラー訂正回路の原理ブロック図を示す。
請求項２の発明は、素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正回路において、受信した符号化データに含まれている誤りの位置を検出する誤り検出手段１１１と、受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手段１１２と、検出された各消失位置について、その消失位置に関する誤り位置多項式σの値を計算する誤り多項式計算手段１２１と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式σの形式的導関数σ’の値を計算する誤り導関数計算手段１２２と、検出された各誤り位置について、その誤り位置に関する消失位置多項式ｕの値を計算する消失多項式計算手段１２３と、検出された各消失位置について、その消失位置に関する消失位置多項式ｕの形式的導関数ｕ'の値を計算する消失導関数計算手段１２４と、検出された各誤り位置について、誤り評価多項式ωの値を計算する誤り評価手段１２５と、検出された各消失位置について、誤り評価多項式ωの値を計算する消失評価手段１２６と、検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手段１１５と、検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手段１１６と、検出された各誤り位置に対応する誤り評価多項式の値と誤り補正値との積を求める誤り補正手段１２７と、検出された各消失位置に対応する消失評価多項式の値と消失補正値との積を求める消失補正手段１２８と、誤り導関数計算手段１２２と消失多項式計算手段１２３とによってそれぞれ得られた計算結果の積を求める誤り分母項算出手段１２９と、誤り多項式計算手段１２１と消失導関数計算手段１２４とによってそれぞれ得られた計算結果の積を求める消失分母項算出手段１３０と、誤り分母項算出手段１２９と誤り補正手段１２７とによって得られた計算結果に基づいて、誤りパターンを求める誤りパターン算出手段１３１と、消失分母項算出手段１３０と消失補正手段１２８とによって得られた計算結果に基づいて、消失パターンを求める消失パターン算出手段１３２とを備えたことを特徴とする。
【００１２】
請求項２の発明では、誤り検出手段１１１によって検出された各誤り位置について、誤り導関数計算手段１２２、消失多項式計算手段１２３および誤り評価手段１２５が実行する上述した式(２)の分母項を形成する各成分およびその分子項の計算と並行して、誤り補正値算出手段１１５が基本指数に関する誤り補正値を計算する。次いで、誤り分母項算出手段１２９による式(２)の分母項の計算と並行して、誤り補正手段１２７により、式(２)の分子項を誤り補正値を用いて補正する。このように、誤り補正値の計算処理およびこの誤り補正値の適用処理を、式(２)に現れる各項の計算手順に並行して実行することにより、式(２)に従って誤りパターンを計算する場合と同等のタイミングで、誤りパターン算出手段１３１に誤りパターンの算出に必要な計算結果を与えることができる。同様に、消失検出手段１１２によって検出された各消失位置について、消失導関数計算手段１２４、誤り多項式計算手段１２１および消失評価手段１２６が実行する上述した式(３)の分母項を形成する各成分およびその分子項の計算と並行して、消失補正値算出手段１１６が基本指数に関する消失補正値を計算する。次いで、消失分母項算出手段１３０による式(３)の分母項の計算と並行して、消失補正手段１２８により、式(３)の分子項を消失補正値を用いて補正する。このように、消失補正値の計算処理およびこの消失補正値の適用処理を、式(３)に現れる各項の計算手順に並行して実行することにより、式(３)に従って消失パターンを計算する場合と同等のタイミングで、消失パターン算出手段１３２に消失パターンの算出に必要な計算結果を与えることができる。
【００１３】
なお、本発明にかかわるエラー訂正回路を方法のカテゴリで捉えることも可能である。
図３に、本発明にかかわるエラー訂正方法の原理ブロック図を示す。
本発明にかかわるエラー訂正方法は、素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正方法において、受信した符号化データに含まれている誤りの位置および消失した符号の位置を検出する検出ステップと、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な基底誤りパターンを求める誤りパターン計算ステップと、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な基底消失パターンを求める消失パターン計算ステップと、検出された各誤り位置および各消失位置について、基本指数ｋに関する誤り補正値および消失補正値をそれぞれ計算する補正値算出ステップと、基底誤りパターンの成分それぞれおよび基底消失パターンの成分それぞれに、対応する誤り補正値および対応する消失補正値をそれぞれ乗じ、これらの乗算結果を最終的な誤りパターンおよび最終的な消失パターンとして出力する補正ステップとを備えたことを特徴とする。
【００１４】
本発明にかかわるエラー訂正方法は、検出された誤り位置および消失位置に基づいて、基本指数とは独立な誤りパターンの成分および消失パターンの成分を求めるとともに、各誤り位置および各消失位置に対応して、基本指数に関する誤り補正値および消失補正値を算出する。そして、基本指数とは独立な誤りパターンの成分それぞれおよび消失パターンの成分それぞれに、対応する誤り補正値および消失補正値を乗じることにより、基本指数とは独立な誤りパターンおよび消失パターンに基本指数に対応する成分を合成し、最終的な誤りパターンおよび消失パターンを得る。このように、基本指数による影響を誤り補正値および消失補正値として分離しているので、基本指数とは独立な誤りパターンおよび消失パターンの計算処理に、既存の回路やアルゴリズムを利用することが可能である。
【００１５】
このようなエラー訂正方法は、当然ながら、コンピュータに実行させるプログラムの概念で捉えることもできる。
請求項３の発明は、素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正する処理をコンピュータに実行させるためのエラー訂正プログラムにおいて、受信した符号化データに含まれている誤りの位置および消失した符号の位置を検出する検出手順と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な基底誤りパターンを求める誤りパターン計算手順と、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な基底消失パターンを求める消失パターン計算手順と、検出された各誤り位置および各消失位置について、基本指数ｋに関する誤り補正値および消失補正値をそれぞれ計算する補正値算出手順と、基底誤りパターンの成分それぞれと対応する誤り補正値との積を求め、最終的な誤りパターンとして出力する誤り補正手順と、基本指数ｋとは独立な基底消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正手順とをコンピュータに実行させることを特徴とする。
【００１６】
請求項３の発明では、検出手順によって検出された誤り位置に基づいて、誤りパターン計算手順および補正値算出手順により、基本指数ｋとは独立な誤りパターンの各成分および基本指数ｋに関する誤り補正値を算出する。また、検出手順によって検出された消失位置に基づいて、消失パターン計算手順および補正値算出手順により、基本指数ｋとは独立な基底消失パターンの各成分および基本指数ｋに関する消失補正値を算出する。そして、誤り補正手順において、基底誤りパターンの各成分に基本指数による成分を合成し、最終的な誤りパターンを求める。同様に、消失補正手順において、基底消失パターンの各成分に基本指数による成分を合成し、最終的な消失パターンを求める。
【００１７】
このように、基本指数による影響を誤り補正値および消失補正値として分離しているので、誤りパターン計算手順および消失パターン計算手順には、既存のアルゴリズムをそのまま利用することが可能である。
もちろん、上述したプログラムをＣＤ‐ＲＯＭなどの記憶媒体に記録して頒布することも可能である。
【００１８】
本発明にかかわるエラー訂正プログラムを記録した記憶媒体は、素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正する処理をコンピュータに実行させるためのエラー訂正プログラムを記録した記憶媒体において、受信した符号化データに含まれている誤りの位置および消失した符号の位置を検出する検出手順と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な基底誤りパターンを求める誤りパターン計算手順と、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な基底消失パターンを求める消失パターン計算手順と、検出された各誤り位置および各消失位置について、基本指数ｋに関する誤り補正値および消失補正値をそれぞれ計算する補正値算出手順と、基底誤りパターンの成分それぞれと対応する誤り補正値との積を求め、最終的な誤りパターンとして出力する誤り補正手順と、基本指数ｋとは独立な基底消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正手順とをコンピュータに実行させるプログラムを記録した記憶媒体である。
【００１９】
本発明にかかわるエラー訂正プログラムを記録した記憶媒体をコンピュータに読みこませることにより、上述したエラー訂正プログラムをコンピュータに実行させ、基底誤りパターンおよび基底消失パターンと誤り補正値および消失補正値を算出し、これらに基づいて、最終的な誤りパターンおよび最終的な消失パターンを求める。
【００２０】
上述したように、誤りパターン計算手順および消失パターン計算手順については、既存のアルゴリズムを利用して実現することが可能であるので、補正値算出手順、誤り補正手順および消失補正手順を、既存のプログラムとともに記憶媒体に記録することによって、本発明にかかわるエラー訂正プログラムを記録した記憶媒体を実現することができる。
【００２１】
【発明の実施の形態】
まず、本発明にかかわるエラー訂正方法、エラー訂正回路の原理を説明する。ここでは、ＩＴＵ‐Ｔによる勧告Ｉ．３６３．１で規定されたリードソロモン(１２８，１２４)に本発明のエラー訂正方法およびエラー訂正回路を適用することを前提として説明する。このため、以下の説明においては、式(４)における基本指数ｋの値は、固定値１２０とする。なお、以下に述べる式の導出過程においては、「先端技術の手ほどきシリーズ  誤り訂正符号とその応用」江藤良純、金子敏信著を参考にした。
【００２２】
式(５)に、２重誤りが発生した場合の４つのシンドローム演算の結果を示す。
【数３】
0003889988.tif 000004
この式(５)をシンドローム多項式で表すと、式(６)のようになる。
Ｓ（Ｘ）＝Ｓ0＋Ｓ1Ｘ＋Ｓ2Ｘ2＋Ｓ3Ｘ3    ・・・(６)
ここで、式(７)に示す無限級数展開が成り立つことが一般に知られている。
【００２３】
【数４】
0003889988.tif 000005
式(７)において、変数ｔにαiＸを代入し、式(７)の両辺にｅiα120iを乗算すると、αi番目の誤りｅiに関する式(８)が得られる。
【数５】
0003889988.tif 000006
同様にして、αj番目の誤りｅjに関する式(９)が得られる。
【００２４】
【数６】
0003889988.tif 000007
式(５)と式(８)および式(９)を見比べれば、シンドローム多項式Ｓ(Ｘ)は、式(８)の右辺と式(９)の右辺とを加え合わせて得られる展開式の４次以上の項を切り捨てたものに等しいことが分かる。したがって、シンドローム多項式Ｓ(Ｘ)を式(１０)のように、式(８)および式(９)の左辺の和を用いて表すことができる。
【００２５】
【数７】
0003889988.tif 000008
この式(１０)の両辺に、誤り位置多項式σ(Ｘ)の定義式である式(１１)の各辺を乗算すると、式(１２)を導くことができる。
σ(Ｘ)＝(１‐αiＸ)(１‐αjＸ)    ・・・（１１）
σ(Ｘ)Ｓ(Ｘ)＝ｅiα120i(１−αjＸ)＋ｅjα120j(１‐αiＸ) ・・(１２）
ここで、式(１２)の４次未満の項は、式(１３)に示す誤り評価多項式ω(Ｘ)の４次未満の項に一致している。
【００２６】
【数８】
0003889988.tif 000009
したがって、適切な関数Φ(Ｘ)を用いて、４次以上の高次項を表すことにより、誤り評価多項式ω(Ｘ)を式(１４)のように表すことができる。
ω(Ｘ)＝Φ(Ｘ)Ｘ4＋σ(Ｘ)Ｓ(Ｘ)    …(１４)
更に、式(８)、式(９)に示した級数展開を利用して、この式(１４)を書き換え、その４次未満の項に注目すれば、誤り評価多項式ω(Ｘ)を式(１５)のように表すことができる。
【００２７】
ω(Ｘ)＝ｅiα120i(１−αjＸ)＋ｅjα120j(１‐αiＸ) ・・・(１５)
ところで、上述した式(１１)の右辺を展開すれば、誤り位置多項式の形式的導関数σ'(Ｘ)が式(１６)のように表されることが分かる。
σ'(Ｘ)＝−(αi＋αj)             …(１６)
この式(１６)で表される関係を利用すれば、式(１７)に示すように、α‐i番目の誤りに対する誤り評価多項式ω(α‐i)を、α‐i番目の誤りに対する誤り位置多項式の導関数σ'(α‐i)を用いて表すことができる。
【００２８】
0003889988.tif 000010
したがって、誤りパターンｅiを、式(１８)のように表すことができる。
【数９】
0003889988.tif 000011
更に、この式(１８)に基づいて、消失および誤りが混在している場合の誤りパターンＹiおよび消失パターンＶiを、式(１９)、式(２０)のように表すことができる。
【００２９】
【数１０】
0003889988.tif 000012
式(１９)、式(２０)と上述した式(２)、式(３)とをそれぞれ見比べれば、生成多項式における基本指数の影響は、誤りパターンＹiおよび消失パターンＶiの分母項の差異として現れていることが分かる。
この差異は、素多項式の根αのべき乗(α119i)であり、この値は、当然ながら、誤り評価多項式ω(α‐i)や誤り多項式σ(α‐i)の値とは独立に計算可能である。したがって、基本指数による影響を、基本指数を含まない生成多項式に対応する誤りパターンおよび消失パターンの計算に必要な各項とは独立に計算可能な補正値として分離することができる。
【００３０】
すなわち、特開平６‐１９７０２６号公報で開示されたエラー訂正回路に、上述した補正値を計算する回路およびこの補正値によって誤りパターンおよび消失パターンを補正する回路を付加することにより、式(４)に示したような基本指数を用いて表される生成多項式に対応した誤りパターンおよび消失パターンを求めるエラー訂正回路を実現することができる。
【００３１】
以下、図面に基づいて、本発明の実施形態について詳細に説明する。
図４に、本発明にかかわるエラー訂正回路の実施形態を示す。
なお、図４に示した構成要素のうち、図６に示した構成要素と同等のものについては、図６に示した構成要素に付された符号と同一の符号を付して示し、説明を省略する。
【００３２】
図４に示したエラー訂正回路は、図６に示したデータ消失訂正回路に、誤り補正値算出部２１１と、消失補正値算出部２１２と、２つの乗算器２１３，２１４を付加して構成されている。
このエラー訂正回路において、誤り補正値算出部２１１は、誤り位置検出部４１１によって検出された誤り位置α-iについて、式(２１)に示す誤り補正値δyを算出する。
【００３３】
δ＝α-119i        ・・・（２１）
このようにして得られた誤り補正値δyは、誤り評価値算出部４１３によって算出された誤り位置α-iにおける誤り評価値ω(α-i)とともに、乗算器２１３による乗算処理に供される。そして、この乗算器２１３による乗算結果が、乗算器４１６に入力される。
【００３４】
同様に、このエラー訂正回路において、消失補正値算出部２１２は、誤り位置検出部４１１によって検出された消失位置α-iについて、上述した誤り補正値と同様に式(２１)で表される消失補正値δvを算出する。このようにして得られた消失補正値δvは、消失評価値算出部４１５によって算出された消失位置α-iにおける消失評価値ω(α-i)とともに、乗算器２１４による乗算処理に供される。そして、この乗算器２１４による乗算結果が、乗算器４１７に入力される。
【００３５】
以下に、図２および図３に示した各手段と、図４に示した各部との対応関係を示す。
図４に示した誤り位置検出部４１１は、図２および図３に示した誤り検出手段１１１および消失検出手段１１２に相当する。また、図４に示した誤り補正値算出部２１１および消失補正値算出部２１２は、それぞれ図２および図３に示した誤り補正値算出手段１１５および消失補正値算出手段１１６に相当する。一方、図４に示した誤り分母算出部４１２、誤り評価値算出部４１３、消失分母算出部４１４、消失評価値算出部４１５、乗算器４１６、４１７、セレクタ４２８およびＲＯＭ４２７は、図２に示した基底誤り計算手段１１３および基底消失計算手段１１４に相当する。また、図４に示した乗算器２１３は、図２に示した誤り補正値乗算手段１１７あるいは、図３に示した誤り補正手段１２７に相当する。同様に、図４に示した乗算器２１４は、図２に示した消失補正値乗算手段１１８あるいは、図３に示した消失補正手段１２８に相当する。更に、図４に示した誤り評価値算出部４１３および消失評価値算出部４１５は、図３に示した誤り評価手段１２５および消失評価手段１２６にそれぞれ相当する。また、図４に示した誤り分母算出部４１２は、図３に示した消失多項式計算手段１２３、誤り導関数計算手段１２２および誤り分母項算出手段１２９に相当する。同様に、図４に示した消失分母算出部４１２は、図３に示した誤り多項式計算手段１２１、消失導関数計算手段１２４および消失分母項算出手段１３０に相当する。
【００３６】
図４に示したエラー訂正回路では、誤り評価値算出部４１３および消失評価値算出部４１５による評価結果ωy，ωyに、それぞれ誤り補正値δyおよび消失補正値δvを乗じる。その後、これらの乗算結果に誤り分母算出部４１２および消失分母算出部４１４によって算出された値に応じてＲＯＭ４２７から読み出された逆元値を乗じる。
【００３７】
つまり、図４に示したエラー訂正回路では、上述した式(１９)、(２０)と同等な式(２２)、(２３)に従って誤りパターンＹiおよび消失パターンＶiを計算している。
【数１１】
0003889988.tif 000013
したがって、式(１９)で表される誤りパターンおよび式(２０)で表される消失パターンを、図６に示した従来の消失データ訂正回路を利用して算出している。
【００３８】
次に、誤り補正値δyおよび消失補正値δvを算出する方法について説明する。
図５に、誤り補正値算出部の詳細構成図を示す。
図５に示した誤り補正値算出部２１１は、演算回路２２１および演算回路２２２を備えている。これらの演算回路２２１、２２２は、誤り位置検出部４１１において並行して実行される２つのチェンサーチ処理、すなわち、符号位置１２７から符号位置６４までのチェンサーチ<１>と符号位置６３から符号位置０までのチェンサーチ<２>とに対応している。
【００３９】
図５に示した演算回路２２１，２２２は、いずれも、セレクタ２２３と乗算器２２４とフリップフロップ２２５とから形成されている。これらの演算回路２２１，２２２において、セレクタ２２３は、チェンサーチ開始信号に応じてそれぞれ対応する初期値Ｄ1および初期値Ｄ2を選択して乗算器２２４に入力し、以降は、フリップフロップ２２５の出力を選択して乗算器２２４に入力する。この乗算器２２４は、セレクタ２２３から入力された値に固定値α119を乗算し、得られた乗算結果をフリップフロップ２２５に入力する。
【００４０】
なお、初期値Ｄ1および初期値Ｄ2は、例えば、式(２４)、式(２５)に基づいて、予め計算しておけばよい。
Ｄ1＝α119*(255-128)mod255＝α68  ・・・（２４）
Ｄ2＝α119*(255-64)mod255 ＝α34    ・・・（２５）
このような初期値Ｄ1および初期値Ｄ2に、乗算器２２４により、チェンサーチに同期して固定値α119を乗算する演算を繰り返していくことにより、誤り位置α-iの検出タイミングに、それぞれ式(２１)で表される誤り補正値が演算回路２２１，２２２の出力として得られる。
【００４１】
図５に示したラッチ２２６，２２７は、それぞれ上述した２つのチェンサーチ<１>，<２>によって検出された誤り位置検出信号<１>，<２>に応じて、演算回路２２１および演算回路２２２の出力を保持し、後段の回路に出力する。
また、図５に示したラッチ２２６，２２７のトリガ信号として、上述した２つのチェンサーチ<１>，<２>によって検出された消失位置α-iの検出タイミングを示す消失位置検出信号<１>，<２>を入力することにより、同様にして、消失補正値算出部２１２を構成することができる。
【００４２】
図５に示した誤り補正値算出部２１１および消失補正値算出部２１２の構成から、誤り補正値δ(α‐i)および消失補正値δ(α‐i)は、図６において、チェンサーチに同期して計算されている各値と同様に、チェンサーチに同期して計算できることは明らかである。
また、式(２２)および式(２３)を採用したことにより、分子項と分母項とを算出するために必要とされる処理遅延が均等化されている。つまり、図６に示した消失訂正回路において、乗算器４２３および乗算器４２６による乗算処理と、誤り評価値ωyおよび消失評価値ωvと誤り補正値δyおよび消失補正値δvとの積をそれぞれ計算する処理とは、ほぼ同等の処理時間で実行することができる。
【００４３】
したがって、式(１９)および式(２０)で表される誤りパターンおよび消失パターンを、式(２)、(３)で表される誤りパターンおよび消失パターンの算出に要する時間と同等の処理時間で求めることができる。
なお、式(１９)、(２０)の導出過程と同様にして、基本指数ｋを用いて表された生成多項式について、式(２)、(３)を利用して誤りパターンおよび消失パターンを計算する式を導出することができる。したがって、生成多項式に現れる基本指数ｋがいかなる値を持っている場合においても、復号過程においてユークリッド互除法を適用可能な符号であれば、本発明にかかわるエラー訂正方法およびエラー訂正回路を適用することが可能である。
【００４４】
また、もちろん、図４、図５に示した各部は、ソフトウェアによって実現することが可能である。したがって、これらの各手順をコンピュータに実行させるエラー訂正プログラムを実現し、このエラー訂正プログラムをコンピュータに読み込ませて実行させれば、式(２２)、(２３)の計算をソフトウェアを用いて実現することができる。更に、このエラー訂正プログラムをＣＤ−ＲＯＭなどの記憶媒体に記録すれば、このエラー訂正プログラムの流通を簡易化することができる。
【００４５】
以上の説明に関して、更に、以下の各項を開示する。
（付記１）  素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正方法において、受信した符号化データに含まれている誤りの位置を検出する誤り検出ステップと、受信した符号化データに基づいて、消失した符号の位置を検出する消失検出ステップと、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な誤りパターンの成分をそれぞれ求める誤りパターン計算ステップと、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な消失パターンの成分をそれぞれ求める消失パターン計算ステップと、検出された各誤り位置および各消失位置について、基本指数ｋに関する誤り補正値および消失補正値をそれぞれ計算する補正値算出ステップと、基本指数ｋとは独立な誤りパターンの成分それぞれおよび基本指数ｋとは独立な消失パターンの成分それぞれに、対応する誤り補正値および対応する消失補正値をそれぞれ乗じ、これらの乗算結果を最終的な誤りパターンおよび最終的な消失パターンとして出力する補正ステップと、を備えたことを特徴とするエラー訂正方法。
【００４６】
（付記２）  素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正回路において、受信した符号化データに含まれている誤りの位置を検出する誤り検出手段と、受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手段と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な誤りパターンの成分をそれぞれ求める基底誤り計算手段と、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な消失パターンの成分をそれぞれ求める基底消失計算手段と、検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手段と、検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手段と、基本指数ｋとは独立な誤りパターンの成分それぞれと対応する誤り補正値との積を求め、乗算結果を最終的な誤りパターンとして出力する誤り補正値乗算手段と、基本指数ｋとは独立な消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正値乗算手段とを備えたことを特徴とするエラー訂正回路。
【００４７】
（付記３）  素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正するエラー訂正回路において、受信した符号化データに含まれている誤りの位置を検出する誤り検出手段と、受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手段と、検出された各消失位置について、その消失位置に関する誤り位置多項式σの値を計算する誤り多項式計算手段と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式σの形式的導関数σ'の値を計算する誤り導関数計算手段と、検出された各誤り位置について、その誤り位置に関する消失位置多項式ｕの値を計算する消失多項式計算手段と、検出された各消失位置について、その消失位置に関する消失位置多項式ｕの形式的導関数ｕ'の値を計算する消失導関数計算手段と、検出された各誤り位置について、誤り評価多項式ωの値を計算する誤り評価手段と、検出された各消失位置について、誤り評価多項式ωの値を計算する消失評価手段と、検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手段と、検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手段と、検出された各誤り位置に対応する誤り評価多項式の値と誤り補正値との積を求める誤り補正手段と、検出された各消失位置に対応する消失評価多項式の値と消失補正値との積を求める消失補正手段と、誤り導関数計算手段と消失多項式計算手段とによってそれぞれ得られた計算結果の積を求める誤り分母項算出手段と、誤り多項式計算手段と消失導関数計算手段とによってそれぞれ得られた計算結果の積を求める消失分母項算出手段と、誤り分母項算出手段と誤り補正手段とによって得られた計算結果に基づいて、誤りパターンを求める誤りパターン算出手段と、消失分母項算出手段と消失補正手段とによって得られた計算結果に基づいて、消失パターンを求める消失パターン算出手段とを備えたことを特徴とするエラー訂正回路。
【００４８】
（付記４）  素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正する処理をコンピュータに実行させるためのエラー訂正プログラムにおいて、受信した符号化データに含まれている誤りの位置を検出する誤り検出手順と、受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手順と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な誤りパターンの成分をそれぞれ求める誤りパターン計算手順と、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な消失パターンの成分をそれぞれ求める消失パターン計算手順と、検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手順と、検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手順と、基本指数ｋとは独立な誤りパターンの成分それぞれと対応する誤り補正値との積を求め、最終的な誤りパターンとして出力する誤り補正手順と、基本指数ｋとは独立な消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正手順とをコンピュータに実行させることを特徴とするプログラム。
【００４９】
（付記５）  素多項式の根αを用いて表されるＢＣＨ符号の生成多項式であって前記根αの指数部が基本指数ｋと変数ｉとの和で表される生成多項式に従って生成された符号化データに、伝送過程において発生したエラーを訂正する処理をコンピュータに実行させるためのエラー訂正プログラムを記録した記憶媒体において、受信した符号化データに含まれている誤りの位置を検出する誤り検出手順と、受信した符号化データに基づいて、消失した符号の位置を検出する消失検出手順と、検出された各誤り位置について、その誤り位置に関する誤り位置多項式の導関数、消失位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な誤りパターンの成分をそれぞれ求める誤りパターン計算手順と、検出された各消失位置について、その消失位置に関する消失位置多項式の導関数、誤り位置多項式および誤り評価多項式とに基づいて、基本指数ｋとは独立な消失パターンの成分をそれぞれ求める消失パターン計算手順と、検出された各誤り位置について、基本指数ｋに関する誤り補正値を計算する誤り補正値算出手順と、検出された各消失位置について、基本指数ｋに関する消失補正値を計算する消失補正値算出手順と、基本指数ｋとは独立な誤りパターンの成分それぞれと対応する誤り補正値との積を求め、最終的な誤りパターンとして出力する誤り補正手順と、基本指数ｋとは独立な消失パターンの成分それぞれと対応する消失補正値との積を求め、最終的な消失パターンとして出力する消失補正手順とをコンピュータに実行させるプログラムを記録した記憶媒体。
【００５０】
【発明の効果】
以上に説明したように、本発明にかかるエラー訂正方法およびエラー訂正回路は、基本指数を含む形式の生成多項式に適合する誤りパターンおよび消失パターンを、基本指数を含まない形式の生成多項式に基づいて導かれた誤りパターンおよび消失パターンと適切な補正値との積によって表す式に従って求めることにより、既存のデータ消失訂正回路のアルゴリズムおよびハードウェアを利用して、例えば、ＩＴＵ‐Ｔによる勧告Ｉ．３６３．１に規定されたエラー訂正技術を用いて符号化されたデータを復号する復号装置を実現することができる。これにより、復号装置の開発に要するコストを大幅に削減することが可能である。
【００５１】
特に、請求項２において述べたように、誤り評価値および消失評価値にそれぞれに対応する補正値を乗算する処理と、式(２)、(３)の分母項を計算する処理とを並行して実行することにより、被除数を求めるための処理遅延と除数を求めるための処理遅延とをほぼ均等にすることができる。したがって、本発明のエラー訂正方法およびエラー訂正回路によれば、従来のデータ消失訂正回路によって誤りパターンおよび消失パターンを求める処理に要する時間と同等の処理時間で、基本指数を含む生成多項式に適合する誤りパターンおよび消失パターンを求めることができる。
【００５２】
もちろん、本発明にかかわるエラー訂正プログラムをコンピュータによって実行させることにより、上述したエラー訂正回路と同等の効果を得ることができる。また、本発明にかかわるエラー訂正プログラムを記録した記憶媒体をコンピュータに読み込ませることにより、コンピュータに本発明にかかわるエラー訂正プログラムを実行させ、上述したエラー訂正回路と同等の効果を得ることができる。
【図面の簡単な説明】
【図１】本発明にかかわる第１のエラー訂正回路の原理ブロック図である。
【図２】本発明にかかわる第２のエラー訂正回路の原理ブロック図である。
【図３】本発明のエラー訂正方法の原理を示す図である。
【図４】本発明にかかわるエラー訂正回路の実施形態を示す図である。
【図５】誤り補正値算出部の詳細構成図である。
【図６】従来のデータ消失訂正回路の概略構成を示す図である。
【符号の説明】
１１１  誤り検出手段
１１２  消失検出手段
１１３  基底誤り計算手段
１１４  基底消失計算手段
１１５  誤り補正値算出手段
１１６  消失補正値算出手段
１１７  誤り補正値乗算手段
１１８  消失補正値乗算手段
１２１  誤り多項式計算手段
１２２  誤り導関数計算手段
１２３  消失多項式計算手段
１２４  消失導関数計算手段
１２５  誤り評価手段
１２６  消失評価手段
１２７  誤り補正手段
１２８  消失補正手段
１２９  誤り分母項算出手段
１３０  消失分母項算出手段
１３１  誤りパターン算出手段
１３２  消失パターン算出手段
２１１  誤り補正値算出部
２１２  消失補正値算出部
２１３、２１４、２２４、４１６，４１７、４２３，４２６  乗算器
２２１、２２２  演算回路
２２３、４２８  セレクタ
２２５  フリップフロップ
２２６  ラッチ
４１１  誤り位置検出部
４１２  誤り分母算出部
４１３  誤り評価値算出部
４１４  消失分母算出部
４１５  消失評価値算出部
４２１  微分値算出部
４２２  消失多項式計算部
４２５  誤り多項式計算部
４２７  ＲＯＭ
【図１】
0003889988.tif 000014
【図２】
0003889988.tif 000015
【図３】
0003889988.tif 000016
【図４】
0003889988.tif 000017
【図５】
0003889988.tif 000018
【図６】
0003889988.tif 000019