(57)【特許請求の範囲】
【請求項１】
入力データからシンドローム多項式を求める第１のステップと、
前記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３のステップと、
前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４のステップと、
前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５のステップと、
前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６のステップと、
を有する消失のみ訂正方法。
【請求項２】
前記第５のステップは、前記修正シンドローム多項式の消失個数ε次以上の係数が０以外の場合、デコードの失敗を出力する
請求項１に記載の消失のみ訂正方法。
【請求項３】
入力データからシンドローム多項式を求める第１のステップと、
前記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３のステップと、
前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４のステップと、
前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５のステップと、
前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６のステップと、
を有する消失のみ訂正方法のプログラム。
【請求項４】
入力データからシンドローム多項式を求める第１のステップと、
前記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、
前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３のステップと、
前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４のステップと、
前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５のステップと、
前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６のステップと、
を有する消失のみ訂正方法のプログラムを記録した記録媒体。
【請求項５】
入力データからシンドローム多項式を求める第１の演算手段と、
前記入力データに対応した消失フラグから消失位置多項式を求める第２の演算手段と、
前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３の演算手段と、
前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４の演算手段と、
前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５の演算手段と、
前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６の演算手段と、
を有する消失訂正専用回路。
【請求項６】
前記第４の演算手段は、
ガロア体加算器、ガロア体乗算器、レジスタによるユニットのカスケード接続により形成された
請求項５に記載の消失訂正専用回路。
【請求項７】
前記第４の演算手段は、
前記消失位置多項式の０次の項が必ず１であるように設定して、前記消失位置多項式の係数の最大値ｐ＋１個に対して、前記ユニットの数が２×ｐ個に設定された
請求項６に記載の消失訂正専用回路。
【請求項８】
前記第５の演算手段は、
前記修正シンドローム多項式の消失個数ε次以上の係数が０以外の場合、デコードの失敗を出力する
請求項５に記載の消失訂正専用回路。
【請求項９】
前記第４の演算手段は、
１つのガロア体演算器を複数の係数の演算に時分割により使用して前記複数の係数の演算で共用する
請求項５に記載の消失訂正専用回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、消失のみ訂正方法、消失のみ訂正方法のプログラム、消失のみ訂正方法のプログラムを記録した記録媒体及び消失訂正専用回路に関し、例えばデータの記録再生装置、データの送受信装置における誤り訂正処理に適用することができ、より具体的にはデータレコーダー、データ伝送装置等に適用することができる。本発明は、消失訂正のみを実行する場合に不要となるユークリッド演算機能を削除し、この削除に対応する構成とすることにより、簡易な構成により消失訂正に特化して消失訂正することができるようにする。
【０００２】
【従来の技術】
従来、各種のデータ処理装置においては、通常訂正と消失訂正との繰り返しによりエラー訂正するようになされている。すなわち図４７は、この一連のエラー訂正処理の処理手順を示すフローチャートである。
【０００３】
なお以下の説明においては、元が２m であるガロア体ＧＦ（２m ）上で定義される有限体を用いて、ｐ個のパリティが付加された符号長ｎのＲＳ（Reed-Solomon）符号を用いた場合の復号手順を示す。また符号全体にε個の消失シンボル（消失誤り）と、消失位置以外にν個の誤り（通常誤り）が存在する場合を考える。但し、εとνとは、次式の関係式を満たすものとする。
【０００４】
【数１】
0004595238.tif 000002
【０００５】
またそれぞれ符号の先頭より数えた消失位置をＵi （１≦ｉ≦ε）とし、この消失位置の消失パターンをＶi （１≦ｉ≦ε）とする。また同様にして示す消失シンボル以外の誤り位置をＸi （１≦ｉ≦ν）とし、この誤り位置の誤りパターンをＹi （１≦ｉ≦ν）とする。またシンドローム多項式の係数は、シンドローム多項式Ｓ（ｘ）の最高次の係数Ｓp-1 を最低次の係数に設定し、以下、最低次の係数Ｓ0 が最高次の係数になる迄、順次、係数の順序を入れ換えてなる逆順シンドローム多項式（（４）式））を用いて復号することとする。なおこの逆順シンドローム多項式は、元のシンドローム多項式Ｓ（ｘ）の根の逆数を根として持つ多項式であり、以下、適宜、単にシンドローム多項式と呼ぶ。
【０００６】
このような前提において、エラー訂正処理においては、図４７の処理により、消失シンボル以外の誤り位置Ｘi と、全ての誤りパターンＶi 及びＹi とを求める。すなわちエラー訂正処理においては、ステップＳＰ１からステップＳＰ２に移り、シンドロームの算出処理と消失位置多項式の算出処理を実行する。
【０００７】
（シンドロームの算出）
ここでシンドロームの算出処理においては、受信信号である受信データｒとパリティ検査行列Ｈとの積として、次式の演算処理によりｐ個のシンドロームＳj （０≦ｊ≦ｐ−１）を求める。但しここで、Ｓはシンドローム、ｃは送信データ、ｅは誤りデータである。
【０００８】
【数２】
0004595238.tif 000003
【０００９】
シンドロームＳは、誤りデータｅが０の場合には、０となる。また符号長ｎ、パリティ数ｐの場合のパリティ検査行列Ｈは、次式により表される。
【００１０】
【数３】
0004595238.tif 000004
このようにして得られるシンドロームＳj を係数に持つｐ−１次の多項式がシンドローム多項式であり、次式により表される。
【００１１】
【数４】
0004595238.tif 000005
【００１２】
ここで（数３）式より、消失位置Ｕi がαm の場合、パリティ検査行列Ｈにおける誤り位置のｊ行目の要素が（αm ）j ＝Ｕi j と表されることにより、シンドローム多項式の各係数Ｓj は、消失位置Ｕi 、誤り位置Ｘi 、消失パターンＶi 、誤りパターンＹi を用いて次式により表される。
【００１３】
【数５】
0004595238.tif 000006
【００１４】
従って、シンドローム多項式は、（数４）式及び（数５）式から、次式により表すことができ、これによりエラー訂正においては、シンドローム多項式Ｓ（ｘ）を計算するようになされている。
【００１５】
【数６】
0004595238.tif 000007
【００１６】
（消失位置多項式の算出）
これに対して消失位置多項式の算出処理においては、上述したと同様にして定義する既知のε個の消失位置Ｕs からε次の消失位置多項式を定義する。消失位置多項式は、ｘ＝Ｕs （１≦ｓ≦ε）において、値が０となる多項式で、次式のように設定することができる。
【００１７】
【数７】
0004595238.tif 000008
【００１８】
（修正シンドローム多項式の算出）
エラー訂正処理においては、続いてステップＳＰ３に移り、修正シンドローム多項式の算出処理を実行する。ここでこの修正シンドローム多項式の算出処理は、消失位置多項式とシンドローム多項式の積のｘp に対する剰余として、次式により修正シンドローム多項式を定義する。
【００１９】
【数８】
0004595238.tif 000009
【００２０】
（誤り位置多項式、誤り評価多項式の導出）
続いてエラー訂正処理においては、ステップＳＰ４に移り、ユークリッド互除演算の処理により、誤り位置多項式、誤り評価多項式が導出される。すなわち誤り位置多項式は、消失位置多項式と同様に、ｘ＝Ｘt （１≦ｔ≦ν）において、（数７）式が値０となる多項式であり、次式のように設定することができる。
【００２１】
【数９】
0004595238.tif 000010
【００２２】
誤り評価多項式は、Ｋｅｙ  ｅｑｕａｔｉｏｎを用いて次式のように表されるｐ−１次の多項式であり、（数８）式について上述した修正シンドローム多項式Ｔ（ｘ）と、（数９）式により表される誤り位置多項式から求めることができる。
【００２３】
【数１０】
0004595238.tif 000011
【００２４】
（誤りパターン、消失パターンの算出）
続いてエラー訂正処理は、ステップＳＰ５に移り、誤り位置が検出され、誤りパターンが検出される。すなわちエラー訂正処理では、（数９）式による誤り位置多項式、（数７）式による消失位置多項式、（数１０）式による誤り評価多項式が求まると、Ｆｏｒｎｅｙ  ａｌｇｏｒｉｔｈｍによって、誤りパターンＹi （１≦ｉ≦ε）、消失パターンＶi （１≦ｉ≦ν）を求めることが出来る。
【００２５】
すなわちＦｏｒｎｅｙ  ａｌｇｏｒｉｔｈｍによる処理においては、誤り位置多項式と消失位置多項式を掛けた積多項式を次式により定義する。
【００２６】
【数１１】
0004595238.tif 000012
【００２７】
先ず、誤りパターンＹi を求める場合、次式により示すように、（数１１）式により表される積多項式を一次微分し、求めたい誤りパターンＹi の誤り位置Ｘi を代入する。
【００２８】
【数１２】
0004595238.tif 000013
【００２９】
【数１３】
0004595238.tif 000014
【００３０】
ここで（数１０）式により示される誤り評価多項式にｘ＝Ｘi を代入し、（数１３）式を変形すると、次式を求めることができる。
【００３１】
【数１４】
0004595238.tif 000015
【００３２】
この（数１４）式は、次式のように変形することができ、これにより誤りパターンＹi を求めることができる。
【００３３】
【数１５】
0004595238.tif 000016
【００３４】
これに対して消失パターンＶi を求める場合、次式により示すように、（数１２）式により表される積多項式の一次微分に、求めたい消失パターンＶi の誤り位置Ｕi を代入する。
【００３５】
【数１６】
0004595238.tif 000017
【００３６】
ここで（数１０）式により表される誤り評価多項式にｘ＝Ｕi を代入し、（数１６）式を用いて変形すると、次式を求めることができる。
【００３７】
【数１７】
0004595238.tif 000018
【００３８】
この（数１７）式は、次式に示すように変形することができ、これにより消失パターンＶi を求めることができる。
【００３９】
【数１８】
0004595238.tif 000019
【００４０】
（データの訂正）
エラー訂正処理においては、このようにして誤りパターン及び消失パターンを検出すると、続くステップＳＰ６において、受信信号である受信データｒに対して、誤り位置Ｘi において、誤りパターンＹi （１≦ｉ≦ｖ）を加えることにより、また消失位置Ｕi において、消失パターンＶi （１≦ｉ≦ε）を加えることにより、受信データｒを訂正した後、ステップＳＰ７に移って誤り訂正したデータを出力する。
【００４１】
図４８は、このようなエラー訂正処理を実行する消失訂正回路を示すブロック図である。この消失訂正回路１において、ＳＹＮブロック２は、受信信号ｒからシンドロームを算出してシンドローム多項式の生成し、また消失フラグＵから消失位置多項式を生成する。また続くＥＵＣブロック３は、ＳＹＮブロック２による処理結果Ｄ０２であるシンドローム多項式、消失位置多項式から修正シンドローム多項式を生成し、またこの修正シンドローム多項式と消失位置多項式からユークリッド互除演算処理によって誤り評価多項式、誤り位置多項式を生成する。続くＣＨＳブロック４は、ＥＵＣブロック３の処理結果Ｄ０３である誤り評価多項式、誤り位置多項式から誤り位置、誤りパターンを求め、さらに受信信号ｒを訂正して出力信号ｃを出力する。
【００４２】
これらのブロック２〜４のうち、ＥＵＣブロック３は、Ａ列及びＢ列による２つのシフトレジスタと、ガロア体割算器、ガロア体乗算器、ガロア体加算器により構成され、この２つのシフトレジスタにユークリッド互除演算を実行する２つの多項式の係数を格納し、多項式同士の割算処理を繰り返す。
【００４３】
図４９〜図５３は、このＥＵＣブロック３を示す接続図である。ＥＵＣブロック３は、図４９〜図５３により示す各部を順次縦続接続して構成される。なお図４９〜図５３においては、信号線に付した符号により相互の接続関係を示す。すなわちＥＵＣブロック３は、図４９により示す割算ユニットＤＩＶと、図５０〜図５３により示すと乗算加算ユニットＭＬＴとにより構成される。このうち割算ユニットＤＩＶ（図４９）は、ユークリッド互除演算における最上位の係数の割算を実行する割算器１１、この割算器１１に各種係数を設定する切替器１２、最上位の係数を格納するレジスタ１３Ａ０、１３Ｂ０、これらのレジスタ１３Ａ０、１３Ｂ０を初期化し、さらには係数を格納する切替器１４Ａ０、１４Ｂ０１により構成される。
【００４４】
これに対して乗算加算ユニットＭＬＴ（図５０〜図５３）は、各係数に対応する乗算器１５Ｂ１〜１５Ｂ１２及び加算器１６Ａ１〜１６Ａ１２、これら乗算器１５Ｂ１〜１５Ｂ１２及び加算器１６Ａ１〜１６Ａ１２への入力をそれぞれ切り替える切替器１７ＡＢ１〜１７ＡＢ１２、各切替器１７ＡＢ１〜１７ＡＢ１２の入力である係数をそれぞれセットするレジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１〜１８Ｂ１２、各レジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１〜１８Ｂ１２の入力を切り替える切替器１９Ａ１〜１９Ａ１２、１９Ｂ１〜１９Ｂ１２により構成される。
【００４５】
これらのうちＡ列の切替器１９Ａ１〜１９Ａ１２は、ＳＹＮブロック２からの対応する出力、対応する加算器１６Ａ１〜１６Ａ１２の出力、Ａ列の対応するレジスタ１８Ａ１〜１８Ａ１２の出力、後段の加算器出力、論理０のプリセット値をＡ列のレジスタ１８Ａ１〜１８Ａ１２に選択出力できるように構成され、またＢ列の切替器１９Ｂ１〜１９Ｂ１２は、対応する加算器１６Ａ１〜１６Ａ１２の出力、切替器１７ＡＢ１〜１７ＡＢ１２の出力、論理０のプリセット値をＢ列のレジスタ１８Ｂ１〜１８Ｂ１２に選択出力できるように構成される。なお最後段の切替器１９Ａ１２においては、後段の加算器出力に対応する入力に、論理０のプリセット値が入力される。
【００４６】
また切替器１７ＡＢ１〜１７ＡＢ１２は、それぞれ対応するＡ列及びＢ列のレジスタ１８Ａ１〜１８Ａ１２及び１８Ｂ１〜１８Ｂ１２の出力を選択して対応する加算器１６Ａ１〜１６Ａ１２に出力できるように構成され、また同様にしてＡ列及びＢ列のレジスタ１８Ａ１〜１８Ａ１２及び１８Ｂ１〜１８Ｂ１２の出力を乗算器１５Ｂ１〜１５Ｂ１２に選択的に出力できるように構成される。これに対して乗算器１５Ｂ１〜１５Ｂ１２は、割算器１１の出力と切替器１７ＡＢ１〜１７ＡＢ１２の出力とによる乗算値を出力し、加算器１６Ａ１〜１６Ａ１２は、この乗算器１５Ｂ１〜１５Ｂ１２の出力と切替器１７ＡＢ１〜１７ＡＢ１２の出力とによる加算値を出力する。
【００４７】
これにより乗算加算ユニットＭＬＴにおいては、これら切替器１７ＡＢ１〜１７ＡＢ１２、１９Ａ１〜１９Ａ１２、１９Ｂ１〜１９Ｂ１２の切替え制御により、Ａ列及びＢ列のレジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１〜１８Ｂ１２にそれぞれ２つの多項式の係数をセットし、このセットした係数と割算器１１の出力とを用いて加算器１６Ａ１〜１６Ａ１２及び乗算器１５Ｂ１〜１５Ｂ１２により演算処理して、その結果得られる演算結果を、それぞれＡ列及びＢ列のレジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１〜１８Ｂ１２にセットし、さらにはこの演算結果を続くＡ列のレジスタ１８Ａ１〜１８Ａ１２にセットすることができるようになされている。
【００４８】
これに対して割算ユニットＤＩＶにおいて、Ａ列の切替器１４Ａ０は、ＳＹＮブロック２からの対応する出力、レジスタ１３Ａ０の出力、後段である乗算加算ユニットＭＬＴの加算器１６Ａ９の出力、論理０のプリセット値をＡ列のレジスタ１８Ａ１〜１８Ａ１２に選択出力できるように構成され、またＢ列の切替器１４Ｂ０は、切替器１２の出力、論理１のプリセット値、乗算加算ユニットＭＬＴにおけるレジスタ１８Ａ７の出力、レジスタ１３Ｂ０の出力をレジスタ１３Ｂ０に選択出力できるように構成される。これに対して切替器１２は、レジスタ１３Ａ０及び１３Ｂ０の選択出力をそれぞれ割算器１１の分母側入力、分子側入力に切替えて出力するように構成され、割算器１１は、割算結果を乗算加算ユニットＭＬＴの切替え器１９Ｂ１〜１９Ｂ１２に出力するようになされている。
【００４９】
これらにより割り算ユニットＤＩＶにおいても、最上位の係数をＡ列及びＢ列、さらには割算ユニットＤＩＶにおける中間出力をレジスタ１３Ａ０、１３Ｂ０にセットすることができるようになされ、このセットした係数により割算の処理を実行して、その結果得られる演算結果を割算ユニットＤＩＶのＢ列のレジスタにセットできるようになされている。これらによりＥＵＣブロック３は、所定の制御機構による切替器の制御により、２つの多項式から所望する多項式の係数を計算できるようになされている。
【００５０】
これによりＥＵＣブロック２は、１個の割算器１１、２×ｐ個（ｐ：パリティ数）の乗算器１５Ｂ１〜１５Ｂ１２、２×ｐ個の加算器１６Ａ１〜１６Ａ１２、多項式の係数を格納する４×ｐ＋２個のレジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１〜１８Ｂ１２等により構成される。なおこの図５０〜図５３に示す構成においては、パリティー数ｐが６個の場合である。
【００５１】
このような消失訂正回路においては、１つの演算器を時分割で使用することにより、回路構成を低減する構成が提案されるようになされている。すなわちこの構成の場合、例えばこのような時分割による多重度をＬと置くと、乗算器及び乗算器の数をそれぞれ（２×ｐ）／Ｌ個に少なくすることができる。なおこの場合、多項式の係数を格納するレジスタについては、２×Ｌ×（２×ｐ）／Ｌ＋３個となる。
【００５２】
図５４〜図５９は、多重度Ｌ＝３によるＥＵＣブロックを示す接続図である。なおこの図５４〜図５９において、上述した図４８〜図５３のＥＵＣブロック３と同一の構成は、対応する符号を付して示し、重複した説明は省略する。このＥＵＣブロック２３の乗算加算ユニットＭＬＴにおいては（図５６〜図５９）、パリティー数ｐの２倍の段数によるＡ列及びＢ列のレジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１／１８Ｂ１２にそれぞれ係数等を保持できるように構成される。乗算加算ユニットＭＬＴは、これらＡ列及びＢ列のレジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１／１８Ｂ１２が３個単位でグループ化され、各グループの先頭に配置されるＡ列及びＢ列のレジスタに対して、上述したＥＵＣブロック３と同様に、加算器１６Ａ１〜１６Ａ１０、乗算器１５Ｂ１〜１５Ｂ１０、切替器１７ＡＢ１〜１７ＡＢ１０が配置される。また各グループの最後尾に配置されるＡ列及びＢ列のレジスタに対しても、それぞれ上述したＥＵＣブロック３と同様に、切替器１９Ａ３〜１９Ａ１２、１９Ｂ３〜１９Ｂ１２が配置される。なお切替器１９Ａ３〜１９Ａ１２、１９Ｂ３〜１９Ｂ１２においては、選択出力を供給するレジスタに代えて、各グループの先頭に配置されたレジスタ出力が供給されるようになされている。
【００５３】
各グループにおいて、Ｂ系列は、各レジスタが直列に接続される。これに対してＡ系列は、それぞれ切替器２４Ａ１〜２４Ａ１０、２５Ａ２、２５Ａ１１を間に挟んで、レジスタが直列に接続される。ここで切替器２４Ａ１〜２４Ａ１０は、係数の入力と、後段のレジスタ出力との選択出力を続くレジスタに出力できるように構成される。これに対して切替器２５Ａ２、２５Ａ１１は、係数の入力と、後段のレジスタ出力と、論理０のプリセット値と、各グループに割り当てられた加算器１６Ａ１〜１６Ａ１０の出力との選択出力を続くレジスタに出力できるようになされている。
【００５４】
これらによりこの乗算加算ユニットＭＬＴにおいては、切替器１９Ａ３〜１９Ａ１２、２４Ａ１〜２４Ａ１０、２５Ａ２、２５Ａ１１を介して、各グループを構成するＡ列のレジスタに多項式の係数をセットした後、これらの係数を各グループ内で転送してＢ系列のレジスタにセットできるようになされ、さらに加算器１６Ａ１〜１６Ａ１０、乗算器１５Ｂ１〜１５Ｂ１０による演算結果をレジスタ１８Ａ１〜１８Ａ１２、１８Ｂ１〜１８Ｂ１２にセットできるようになされ、これらにより各グループ毎に加算器１６Ａ１〜１６Ａ１０、乗算器１５Ｂ１〜１５Ｂ１０を共用できるようになされている。
【００５５】
このようなグループを単位にした乗算加算ユニットＭＬＴの処理に対応するように、割算ユニットＤＩＶ（図５５）は、切替器２７を介して割算器１１の出力を乗算加算ユニットＭＬＴに出力するように構成される。ここで切替器２７は、割算器１１の出力を乗算加算ユニットＭＬＴに出力し、またまたレジスタ２８により割算器１１の出力を保持して乗算加算ユニットＭＬＴに出力し直し、さらにはこれらに代えて論理０のリセット値を出力できるようになされている。
【００５６】
またＥＵＣブロックでは、ＥＬＬユニット（図５４）において、乗算加算ユニットＭＬＴの最上位であるレジスタ１３Ａ０の出力を０検出回路２９に受け、ここでこのレジスタ１３Ａ０の出力に論理０が発生するタイミングを検出する。またＡ列及びＢ列に対応する２つのレジスタＤＲ及びＤｇの値を切替器３０により切替え、このレジスタＤＲ及びＤｇの値と、０検出回路２９とによりステータスとをコントローラ２５で判定して乗算加算ユニットＭＬＴに配置した各切替器の動作を制御する。なお切替器３０においては、Ａ列に対応するレジスタＤＲに対して、所定の設定値ｐ、レジスタＤｇの出力値、極性判定器（−１）を介して極性を判定してなるレジスタＤＲの出力値、極性判定器（−１）を介して極性を判定してなるレジスタＤｇの出力値の何れかを設定できるように構成される。またＢ列に対応するレジスタＤｇに対して、所定の設定値ｐ＋１、レジスタＤＲの出力値、レジスタＤｇの出力値の何れかを設定できるように構成される。
【００５７】
【発明が解決しようとする課題】
ところで近年、種々のディジタル機器が開発されており、このようなディジタル機器においては、一般に、通常訂正と消失訂正との繰り返しによりエラー訂正するようになされている。しかしながら消失訂正のみ実行するシステムも近年提案されるようになされており、このようなシステムにおいては、通常訂正と消失訂正との双方を実行可能な消失訂正回路を用いて、消失訂正のみ実行するようになされていた。
【００５８】
しかしながらこのように通常訂正と消失訂正との双方を実行可能な消失訂正回路を用いて、消失訂正のみ実行する場合、本来不必要である機能を無駄に含むことになり、その分、回路規模が無駄に増加することになり、特に、小型化が必要な機器においては、十分に改善の余地が残れていると考えられる。
【００５９】
本発明は以上の点を考慮してなされたもので、簡易な構成により消失訂正に特化して消失訂正することができる消失訂正方法、消失訂正方法のプログラム、消失訂正方法のプログラムを記録した記録媒体及び消失訂正回路を提案しようとするものである。
【００６０】
本発明の消失のみ訂正方法は、入力データからシンドローム多項式を求める第１のステップと、前記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３のステップと、前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４のステップと、前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５のステップと、前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６のステップと、を有する。
【００６１】
本発明の消失のみ訂正方法のプログラムは、入力データからシンドローム多項式を求める第１のステップと、前記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３のステップと、前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４のステップと、前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５のステップと、前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６のステップと、を有する。
【００６２】
本発明の消失のみ訂正方法のプログラムを記録した記録媒体は、入力データからシンドローム多項式を求める第１のステップと、前記入力データに対応した消失フラグから消失位置多項式を求める第２のステップと、前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３のステップと、前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４のステップと、前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５のステップと、前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６のステップと、を有する。
【００６３】
本発明の消失訂正専用回路は、入力データからシンドローム多項式を求める第１の演算手段と、前記入力データに対応した消失フラグから消失位置多項式を求める第２の演算手段と、前記シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３の演算手段と、前記消失位置多項式から誤り位置多項式を求めると共に、前記誤り位置多項式の値を１とすることにより、前記修正シンドローム多項式から誤り評価多項式を求める第４の演算手段と、前記誤り位置多項式及び前記誤り評価多項式から誤り位置及び誤り値を求める第５の演算手段と、前記誤り位置及び前記誤り値を用いて前記入力データの誤りを訂正する第６の演算手段と、を有する。
【００６６】
【発明の実施の形態】
以下、適宜図面を参照しながら本発明の実施の形態を詳述する。
【００６７】
（１）第１の実施の形態
（１−１）第１の実施の形態の構成
図１は、図４７との対比により本発明の実施の形態に係る消失訂正のみの処理手順を示すフローチャートである。この実施の形態においては、ユークリッド互除演算処理を省略して、修正シンドローム多項式算出処理の後、誤り位置検出処理を実行する。さらにこの誤り位置検出処理においては、消失訂正のみ実行し、これらにより簡易な処理により消失訂正に特化して消失訂正することができるようになされている。
【００６８】
なお以下の説明においては、元が２m であるガロア体ＧＦ（２m ）上で定義される有限体を用いて、ｐ個のパリティが付加された符号長ｎのＲＳ符号を用いた場合の復号手順を示す。また符号全体にε個の消失シンボル（消失誤り）が存在する場合を考える。但し、εは、次式の関係式を満たすものとする。
【００６９】
【数１９】
0004595238.tif 000020
【００７０】
またそれぞれ符号の先頭より数えた消失位置をＵi （１≦ｉ≦ε）とし、この消失位置の消失パターンをＶi （１≦ｉ≦ε）とする。またシンドローム多項式の係数は、シンドローム多項式Ｓ（ｘ）の最高次の係数Ｓp-1 を最低次の係数に設定し、以下、最低次の係数Ｓ0 が最高次の係数になる迄、順次、係数の順序を入れ換えてなる逆順シンドローム多項式（（２２）式））を用いて復号することとする。なおこの逆順シンドローム多項式は、元のシンドローム多項式Ｓ（ｘ）の根の逆数を根として持つ多項式であり、以下、適宜、単にシンドローム多項式と呼ぶ。
【００７１】
このような前提において、エラー訂正処理においては、図１のステップＳＰ１１からステップＳＰ１２に移り、シンドロームの算出処理と消失位置多項式の算出処理を実行する。
【００７２】
（シンドロームの算出）
ここでシンドロームの算出処理においては、受信信号である受信データｒとパリティ検査行列Ｈとの積として、次式の演算処理によりｐ個のシンドロームＳj （０≦ｊ≦ｐ−１）を求める。但しここで、Ｓはシンドローム、ｃは送信データ、ｅは誤りデータである。
【００７３】
【数２０】
0004595238.tif 000021
【００７４】
シンドロームＳは、誤りデータｅが０の場合には、０となる。また符号長ｎ、パリティ数ｐの場合のパリティ検査行列Ｈは、次式により表される。
【００７５】
【数２１】
0004595238.tif 000022
このようにして得られるシンドロームＳj を係数に持つｐ−１次の多項式がシンドローム多項式であり、次式により表される。
【００７６】
【数２２】
0004595238.tif 000023
【００７７】
ここで（数２１）式より、消失位置Ｕi がαm の場合、パリティ検査行列Ｈにおける誤り位置のｊ行目の要素が（αm ）j ＝Ｕi j と表されることにより、シンドローム多項式の各係数Ｓj は、消失位置Ｕi 、消失パターンＶi 、を用いて次式により表される。
【００７８】
【数２３】
0004595238.tif 000024
【００７９】
従って、シンドローム多項式は、（数２２）式及び（数２３）式から、次式により表すことができ、これによりエラー訂正においては、入力データからシンドローム多項式を計算するようになされている。
【００８０】
【数２４】
0004595238.tif 000025
【００８１】
（消失位置多項式の算出）
これに対して消失位置多項式の算出処理においては、上述したと同様にして定義する既知のε個の消失位置Ｕk からε次の消失位置多項式を定義する。消失位置多項式は、ｘ＝Ｕk （１≦ｋ≦ε）において、値が０となる多項式で、次式のように設定することができ、これにより入力データに対応した消失フラグから消失位置多項式を求めるようになされている。
【００８２】
【数２５】
0004595238.tif 000026
【００８３】
（修正シンドローム多項式の算出）
エラー訂正処理においては、このようにしてシンドローム多項式、消失位置多項式を計算すると、続くステップＳＰ１３において、修正シンドローム多項式の算出処理を実行する。ここでこの修正シンドローム多項式の算出処理は、消失位置多項式とシンドローム多項式の積のｘp に対する剰余として、次式により修正シンドローム多項式を定義する。
【００８４】
【数２６】
0004595238.tif 000027
【００８５】
ここでシンドローム多項式Ｓ（ｘ）のｊ−ｋ次の係数がＳp-j-1+k で表されることにより、この修正シンドローム多項式においては、各次数の係数Ｔj （０≦ｊ≦ｐ−１）を次式で表すことができる。
【００８６】
【数２７】
0004595238.tif 000028
【００８７】
【数２８】
0004595238.tif 000029
【００８８】
従ってこれらより修正シンドローム多項式のε次以上の項Ｔj （ε≦ｊ）が値０でなければ、デコードすることが困難であることが判る。また、これらの修正シンドローム多項式の各係数から、修正シンドローム多項式は、次式により表すことができる。
【００８９】
【数２９】
0004595238.tif 000030
【００９０】
これによりこの実施の形態によるエラー訂正処理においては、この演算処理によりシンドローム多項式及び消失位置多項式から修正シンドローム多項式を計算する。
【００９１】
（誤り評価多項式の導出）
この実施の形態では、続くステップＳＰ１４において、誤り評価多項式を導出し、誤りパターンＶを検出する。ここで誤り評価多項式は、Ｋｅｙ  ｅｑｕａｔｉｏｎを用いて次式により示すｐ−１次の多項式により表すことができる。なおここで消失誤りのみの処理であることにより、誤り位置多項式は、誤り位置多項式の値を１とおく。この演算処理により、この実施の形態では、誤り評価多項式を修正シンドローム多項式より導出するようになされている。なお誤り位置多項式については、消失位置多項式より求めるようになされている。
【００９２】
【数３０】
0004595238.tif 000031
【００９３】
（消失パターンの算出）
このようにして消失位置多項式、誤り評価多項式が求まると、Ｆｏｒｎｅｙａｌｇｏｒｉｔｈｍにより、消失パターンＶi （１≦ｉ≦ν）を求めることができる。すなわち（数３０）式による誤り評価多項式においては、次式に示すように変形することができる。
【００９４】
【数３１】
0004595238.tif 000032
【００９５】
これに対して（数２５）式による消失位置多項式を一次微分し、求めたい消失パターンＶi の消失位置Ｕi を代入すると、次式の関係式を得ることができる。
【００９６】
【数３２】
0004595238.tif 000033
【００９７】
【数３３】
0004595238.tif 000034
【００９８】
またこの消失位置多項式に、消失位置Ｕk （１≦ｋ≦ε）のうちの任意の２つの消失位置Ｕi とＵl （ｉ≠ｌ）を代入した場合、次式の関係式が成立する。
【００９９】
【数３４】
0004595238.tif 000035
【０１００】
さらにこの（数３４）式から次式の関係式を得ることができる。
【０１０１】
【数３５】
0004595238.tif 000036
【０１０２】
従って、Ｕi ≠Ｕl の場合には、次式の関係式を得ることができる。
【０１０３】
【数３６】
0004595238.tif 000037
【０１０４】
これらにより（数３１）式による誤り評価多項式にｘ＝Ｕi を代入し、（数３３式）と（数３６）式を用いて変形すると、次式の関係式を求めることができる。
【０１０５】
【数３７】
0004595238.tif 000038
【０１０６】
これによりこの（数３７）式より消失パターンＶi を求めると、次式により消失パターンＶi を求めることができる。
【０１０７】
【数３８】
0004595238.tif 000039
【０１０８】
これによりこの実施の形態では、このステップＳＰ１４において、誤り位置多項式及び誤り評価多項式から誤り位置及び誤り値を求めるようになされている。
【０１０９】
（データの訂正）
このようにして消失パターンＶi を求めると、続くステップＳＰ１５においてデータを訂正し、その後、ステップＳＰ１６でこの訂正したデータを出力する。このデータの訂正においては、受信信号ｒに対して、消失位置Ｕi において、消失パターンＶi （１≦ｉ≦ε）を加えることにより、受信信号の訂正を行う。
【０１１０】
図２は、図４８との対比によりこの消失訂正処理手順による消失訂正専用回路を示すブロック図である。この消失訂正専用回路３１は、ＥＵＣブロック３３及びＣＨＳブロック３４の構成が異なる点を除いて、消失訂正回路１と同一に構成される。これによりこの実施の形態では、ＳＹＮブロック２が、入力データからシンドローム多項式を求める第１の演算手段と、入力データに対応した消失フラグから消失位置多項式を求める第２の演算手段とを構成するのに対し、ＥＵＣブロック３３が、シンドローム多項式及び消失位置多項式から修正シンドローム多項式を求める第３の演算手段と、この修正シンドローム多項式及び消失位置多項式から誤り評価多項式及び誤り位置多項式を求める第４の演算手段を構成する。また続くＣＨＳブロック３４が、誤り位置多項式及び誤り評価多項式から誤り位置及び誤り値を求める第５の演算手段と、誤り位置及び誤り値を用いて入力データの誤りを訂正する第６の演算手段を構成するようになされている。
【０１１１】
かくするにつき図３は、この実施の形態に係る処理手順を図４８について上述した処理手順との比較により示す図表である。消失のみ訂正の処理手順においては、消失訂正処理と異なり、修正シンドローム多項式が誤り評価多項式と等しく、また消失位置多項式が誤り位置多項式と等しくなることにより、ユークリッド互除演算を行なう必要がなくなるのである。これによりこの実施の形態では、消失訂正専用回路におけるＥＵＣブロックの構造を簡略化することができ、簡易な処理により消失訂正に特化して消失訂正することができるようになされている。
【０１１２】
図４〜図８は、この実施の形態に係る消失訂正専用回路のＥＵＣブロック３３を示す接続図である。ＥＵＣブロック３３は、修正シンドローム多項式と消失位置多項式とを演算する為に、１列のシフトレジスタ、ガロア体割算器、ガロア体乗算器、ガロア体加算器等により構成される。
【０１１３】
このうちガロア体割算器は、消失位置の逆数Ｕi -1を求めるために設けられ、このためＥＵＣブロック３３の内部に１つだけ配置されて割算ユニットＤＩＶ（図４）を構成するようになされている。すなわち消失フラグの位置情報は、図９に示されるように、入力時、符号の最後尾αn-1 から符号の先頭α0 の順で入力される。これによりここで検出される消失位置は、本来の消失位置Ｕi ではなく、符号を逆順にカウントしたものとなる。これにより（数２５）式により表される消失位置多項式に適用する場合、本来の消失位置Ｕi の逆数Ｕi -1が必要となる。
【０１１４】
このため割算ユニットＤＩＶにおいては、切替器３５及び３６を介してレジスタ３７及び３８に消失フラグの位置情報をセットし、割算器３９によりレジスタ３７及び３８に格納したデータを割算することにより、次式の演算式によりこのＵi -1による消失位置を計算するようになされている。
【０１１５】
【数３９】
0004595238.tif 000040
【０１１６】
乗算加算ユニットＭＬＴ（図５〜図８）は、レジスタ、ガロア体乗算器及びガロア体加算器によるユニットをパリティー数に応じた所定個数だけカスケード接続して構成される。ここで１つのユニットは、図１０に示すように、この乗算加算ユニットＭＬＴにおける１列のシフトレジスタを構成するレジスタ４１に対して、切替器４０により係数等をセットできるように構成される。このユニットは、切替器４２の選択出力と、後段側ユニットに配置されたレジスタ４１の出力とを乗算器（ガロア体乗算器）４３により乗算し、この乗算器４３の乗算結果とレジスタ４１の出力とを加算器４４で加算するように構成される。
【０１１７】
レジスタ４１の入力を切り替える切替器４０においては、この乗算加算ユニットＭＬＴのモードに応じて接点を切り替えるように制御される。すなわちレジスタ４１の内容をクリアする場合、図１１に示すように、論理０のリセット入力が選択されるようになされている。これに対して係数をレジスタにロードする場合、図１２に示すように、ＳＹＮブロック２の対応する出力に接点が切替えられる。また図１３に示すように、後段ユニットによる出力値をシフトさせる場合、この後段ユニットにおけるレジスタ４１の出力を選択するように制御される。またこの後段のさらに後段ユニットによる出力値をシフトさせる場合、対応する後段ユニットにおけるレジスタ４１の出力を選択するように制御される（符号３により示す接点である）。
【０１１８】
これに対して演算等の処理においては、加算器４４の出力が選択される。すなわち図１４に示すように、乗算器４３の入力を切替える切替器４２で値０の設定値を選択して乗算器４３の出力を値０に設定し、加算器４４の出力を切替器４０により選択することにより、レジスタ４１の出力をそのままレジスタ４１にセットし直し、これによりホールドの処理が実行される。またこのホールドの設定において、図１５に示すように、切替器４２で割算ユニットＤＩＶの出力を選択することにより、演算結果をレジスタ４１に格納し、さらには続くユニットに出力できるようになされている。
【０１１９】
なお図５〜図８においては、この図１０の各部に付した符号に添え字を付して各ユニットの対応する構成を示す。各ユニットにおいては、求められる動作に応じてこの図１０に示す基本的な構成に対して、切替器４０における入力が省略され、また乗算器４３、加算器４４が省略されるようになされている。
【０１２０】
ここでこの実施の形態では、修正シンドローム多項式の係数が最大でｐ個であり、また消失位置多項式の係数は最大ｐ＋１個であるのに対し、消失位置多項式の０次の係数は必ず１になる。これによりこの乗算加算ユニットＭＬＴでは、修正シンドローム多項式及び消失位置多項式に対して、それぞれｐ個のユニット数である全体で２×ｐ個のユニット数によりこのカスケード接続が構成され、これによりシフトレジスタの段数が２×ｐ段に設定されるようになされている。これによりこの実施の形態においては、消失位置多項式の０次の係数は必ず１であることを有効に利用してシフトレジスタの段数を低減するようになされている。
【０１２１】
これらによりこのＥＵＣブロック３３では、修正シンドローム多項式と消失位置多項式とを格納するためのレジスタが２×ｐ個必要となり、ＥＵＣブロック３３全体では、１個のガロア体割算器、２×ｐ個のガロア体乗算器、２×ｐ個のガロア体加算器、２×ｐ＋２個のレジスタが必要となる。これによりこの実施の形態では、従来の消失訂正回路に比してレジスタを２×ｐ個の削減し、さらにその分、制御回路の構成を簡略化できるようになされている。
【０１２２】
具体的には、パリティ数が６の場合（図４〜図８）、ガロア体割算器１個、ガロア体乗算器１２個、ガロア体加算器１２個、演算結果を格納するレジスタが１４個が必要となる。
【０１２３】
図１６は、このＥＵＣブロック３３のモードを示す図表である。ＥＵＣブロック３３の動作は、この図表によるモードに区分される。ここでＰＩモードは、シンドロームと消失位置の係数を対応するレジスタにロードするモードであり、ＰＭモードは、修正シンドローム多項式と消失位置多項式を求める演算を実行するモードである。またＳＩモードは、０次の係数を値１に設定して、レジスタに保持した演算結果をシフトアップするモードであり、ＳＭモードは、最下位レジスタを０に設定してレジスタに保持した演算結果をシフトアップするモードである。
【０１２４】
図１７は、ＥＵＣブロック３３におけるモードの切替えを示すフローチャートであり、この図１７に示すように、ＥＵＣブロック３３は、ＰＩモードより順次、ＰＭモード、ＳＩモード、ＳＭモードにモードを切り替えて一連の処理を実行する。
【０１２５】
すなわちＥＵＣブロック３３は、図１８に示すように、ステージ＝０において、ＰＩモードに設定され、まず初期値として、Ａ1 〜Ａp のレジスタに対してシンドロームＳ0 〜Ｓp-1 が格納され、Ａp+1 〜Ａ2pのレジスタに対して消失位置Ｕ1 〜Ｕp が格納される。なお以下において、シフトレジスタを構成する各レジスタを、割算ユニットＤＩＶから順次Ａ0 〜Ａ2pの符号により示す。
【０１２６】
さらに続くステージ（０＜ＳＴＡＧＥ≦ε）においては、ＰＭモードに設定され、消失位置Ｕ1 〜Ｕp をシフトアップしつつ、シンドロームＳ0 〜Ｓp-1 と消失位置（１−Ｕi -1ｘ）［１≦ｉ≦ε］を順次乗算することにより、修正シンドローム多項式の係数Ｔp-1 〜Ｔ0 と消失位置多項式の係数ｕε〜ｕ1 を求める。
【０１２７】
また続くステージ（ε＜ＳＴＡＧＥ≦Ｐ）においては、ＳＩモード、ＳＭモードに設定され、各々の係数をｐ−ε回シフトアップして出力する。このときレジスタＡ1 の値が０かどうかをチェックし、Ａ1 ＝０であれば正復号し、Ａ1 ≠０であればデコードｆａｉｌｒであること（信号誤り）を上位のコントローラに通知する。なおＳＩモードにおいては、事前に、Ｕ0 ＝１をＡ2Pに設定する。
【０１２８】
より具体的に、図４〜図８との対比により図１９及び図２０に示すように、ｐ＝６、ε＝６の場合、ＥＵＣブロック３３は、ステージ０において、レジスタＡ0 〜Ａ6 にシンドロームＳ0 〜Ｓ6 が格納され、またレジスタＡ7 〜Ａ12に消失位置Ｕ1 〜Ｕ6 が格納される。さらに最上位のレジスタＡ0 と、レジスタＡ7 〜Ａ12の間でシフトの処理が実行されると共に、最下位のレジスタＡ12が値０にリセットされ、ステージ１の状態が形成される。さらにＰＭモードにより、同様の、レジスタＡ0 とＡ7 〜Ａ12の間でシフトの処理が実行されると共に、レジスタＡ1 〜Ａ5 において、下位側のレジスタＡ2 〜Ａ6 の内容との間でガロア演算して演算結果をセットし直すことにより、ステージ２の状態が形成される。なおここでシンドロームＳ6 を保持したレジスタＡ6 がホールドの状態に保持され、最下位のレジスタＡ12は、ガロア割算器（ＤＩＶ）の演算結果がセットされる。
【０１２９】
また続いて、同様に、レジスタＡ0 とＡ7 〜Ａ11の間でシフトの処理が実行され、またレジスタＡ1 〜Ａ5 において、下位側のレジスタＡ2 〜Ａ6 の内容との間でガロア演算して演算結果をセットし直すことにより、ステージ３の状態が形成される。なおここでシンドロームＳ6 を保持したレジスタＡ6 がホールドの状態に保持され、最下位レジスタＡ12は、ガロア割算器（ＤＩＶ）の演算結果、続くレジスタＡ11は、最下位レジスタＡ12との間のガロア演算結果がセットされる。
【０１３０】
このようにレジスタを順次切り替えて、ホールド、シフト、演算の処理が繰り返されることにより、ＥＵＣブロック３３は、順次ステージを切り替えるようになされている。なお図２２及び図２３は、図２０及び図２１との対比により示すｐ＝６、ε＝２の場合の状態遷移である。
【０１３１】
このような演算結果により、修正シンドローム多項式Ｔ及び消失位置多項式の係数は、図２３に示すように表される。修正シンドローム多項式の最高時の係数が常にレジスタＡ1 に格納され、また消失位置多項式の最高次係数が常にレジスタＡP+1 に格納されることになる。ただし、ｐ＝εの場合には、消失位置多項式の０次の係数が省略され、消失位置多項式のε次〜１次の係数のみがレジスタＡP+1 〜Ａ2Pに格納される。これによりレジスタを２ｐ段により構成した場合でも、ｐ≦εを条件に、デコードできるようになされている。
【０１３２】
（１−２）第１の実施の形態の効果
以上の構成によれば、消失訂正のみを実行する場合に不要となるユークリッド演算機能を削除し、この削除に対応する構成とすることにより、簡易な構成により消失訂正に特化して消失訂正することができる。
【０１３３】
すなわちガロア体加算器、ガロア体乗算器、レジスタによるユニットのカスケード接続による構成によって、修正シンドローム多項式及び消失位置多項式から誤り評価多項式及び誤り位置多項式を求めることにより、ユークリッド演算によらないで誤り評価多項式及び誤り位置多項式を求めることができ、簡易な構成により消失訂正に特化して消失訂正することができる。
【０１３４】
またこのとき消失位置多項式の０次の項が必ず１であるように設定して、消失位置多項式の係数の最大値ｐ＋１個に対して、ユニットの数を２×ｐ個に設定することにより、全体構成を簡略化することができる。
【０１３５】
また修正シンドローム多項式の消失個数ε次以上の係数が０以外の場合、デコードｆａｉｌｅｒであることを出力することによっても、全体構成を簡略化することができる。
【０１３６】
（２）第２の実施の形態
この実施の形態においては、ＥＵＣブロックにいわゆる多重化の構成を適用する。すなわちＥＵＣブロックにおいて、１つのガロア体演算器を複数の係数の演算に時分割により使用することにより、これら複数の係数の演算でガロア体演算器を共用し、その分、ＥＵＣブロックの回路構成を簡略化する。
【０１３７】
すなわち時分割による多重度をＬと置くと、多重化による構成においては、１個のガロア体割算器、（２×ｐ）／Ｌ個のガロア体乗算器、（２×ｐ）／Ｌ個のガロア体加算器、（（Ｌ＋１）×（２×ｐ）／Ｌ）＋３個のレジスタによりＥＵＣブロックを構成することができ、その分、回路構成を簡略化することができる。これにより従来の消失訂正との比較により、（（Ｌ−１）×（２×ｐ）／Ｌ）個、レジスタを削減することができ、またその分、制御回路の構成を簡略化することができる。
【０１３８】
図２４〜図２８は、この実施の形態に係る消失訂正専用回路に適用されるＥＵＣブロックを示す接続図である。この実施の形態において、割算ユニットＤＩＶは、切替器５４により乗算加算ユニットＭＬＴに割り当てられた所定のレジスタ出力（図２７）又はレジスタ３７の出力を選択的にレジスタ３７にセットできるように構成される。また切替器３６により、レジスタ３８の出力、論理１のリセット値を選択的にレジスタ３８にセットできるように構成される。また切替器５５、レジスタ５６を介して、割算器３９の出力を乗算加算ユニットＭＬＴに出力できるようになされ、さらにはこの出力を保持できるようになされている。
【０１３９】
これに対して乗算加算ユニットＭＬＴは、図２９に示す基本的な構成によるユニットのカスケード接続により形成される。ここでこのユニットにおいては、それぞれ入力側に切替器６０、６１、６２を多重度Ｌに対応する３段のレジスタ５７、５８、５９が直列に接続されて配置される。このユニットは、割算ユニットＤＩＶの出力、論理０のリセット値、論理１のリセット値を切替器６３により選択して乗算器６４に入力し、この乗算器６４により切替器６３の出力と真ん中に配置したレジスタ５８の出力とを乗算する。また最上段のレジスタ５７の出力、論理０のリセット値を切替器６６により選択して加算器６７に入力し、この加算器６７で乗算器６４の出力と乗算して最下段の切替器６２に入力する。
【０１４０】
各レジスタ５７、５８、５９の切替器６０、６１、６２は、対応する多項式の係数、後段のレジスタ出力を選択できるように構成される。また最後段の切替器６２においては、論理１のリセット値、加算器６７の出力値を選択できるように構成される。また最上段の切替器６０は、切替器７３、レジスタ７４を介して加算器６７の出力、さらにはこの出力の保持値を選択できるようになされている。
【０１４１】
これらによりユニットにおいては、図３０に示すように切替器６０〜６２を設定することにより、シンドローム多項式の係数、消失位置多項式の係数を対応するレジスタに設定できるようになされている。ＥＵＣブロック５３は、第１の実施の形態について上述したと同一のモードの切替えにより動作するように構成され、この図３０に示す設定が、第１の実施の形態について上述したＰＩモード等におけるロードの処理に対応するようになされている。
【０１４２】
またＳＩ、ＳＭモードに対応するホールドの処理においては、図３１に示すように、各ユニットのレジスタ５７〜５９、７４間でデータを転送して実行される。なおこの図３１における各サイクルＳＹＣに対応する切替器６０〜６２、６３、７３の設定を図３２〜図３５に示す。またＰＩモードにおけるシフトにおいては、図３６に示す繰り返しの処理により実行される。なおこの図３６における各サイクルＳＹＣに対応する切替器６０〜６２、６３、７３の設定を図３７〜図４０に示す。
【０１４３】
またＰＭモードにおける演算の処理においては、図４１に示す繰り返しの処理により実行される。なおこの図４１における各サイクルＳＹＣに対応する切替器６０〜６２、６３、７３の設定を図４２〜図４５に示す。またこれらより演算処理を伴うシフトの処理においては、図４６に示す繰り返しの処理により実行される。
【０１４４】
この実施の形態によれば、１つのガロア体演算器を複数の係数の演算に時分割により使用して、複数の係数の演算で共用することにより、その分、さらに一段と全体構成を簡略化することができる。
【０１４５】
（３）他の実施の形態
なお上述の実施の形態においては、パリティー数ｐ＝６の場合について述べたが、本発明はこれに限らず、種々のパリティー数の場合に広く適用することができる。
【０１４６】
さらに上述の実施の形態においては、多重度を３に設定する場合について述べたが、本発明はこれに限らず、種々の多重度による場合に広く適用することができる。
【０１４７】
【発明の効果】
上述のように本発明によれば、消失訂正のみを実行する場合に不要となるユークリッド演算機能を削除し、この削除に対応する構成とすることにより、簡易な構成により消失訂正に特化して消失訂正することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係る消失訂正の処理手順を示すフローチャートである。
【図２】図１の処理手順による消失訂正専用回路を示すブロック図である。
【図３】従来の処理手順との比較により図１の処理手順を示すタイムチャートである。
【図４】図２の消失訂正専用回路におけるＥＵＣブロックを示す接続図である。
【図５】図４の続きを示す接続図である。
【図６】図５の続きを示す接続図である。
【図７】図６の続きを示す接続図である。
【図８】図７の続きを示す接続図である。
【図９】図４のＥＵＣブロックにおける消失位置の説明に供する図表である。
【図１０】図３のＥＵＣブロックにおけるユニットの基本的な構成を示す接続図である。
【図１１】図１０のユニットのクリアの処理における接続を示す図である。
【図１２】図１０のユニットのロードの処理における接続を示す図である。
【図１３】図１０のユニットのシフトの処理における接続を示す図である。
【図１４】図１０のユニットのホールドの処理における接続を示す図である。
【図１５】図１０のユニットの演算処理における接続を示す図である。
【図１６】図４のＥＵＣブロックにおけるモードの説明に供する図表である。
【図１７】図４のＥＵＣブロックにおけるモードの遷移の説明に供するフローチャートである。
【図１８】図１７のモードの遷移の説明に供する略線図である。
【図１９】図１７のモードの遷移に対応するレジスタの変化を示す略線図である。
【図２０】図１９の続きを示す略線図である。
【図２１】図１９との対比によりε＝２の場合を示す略線図である。
【図２２】図２１の続きを示す略線図である。
【図２３】図４のＥＵＣブロックにおけるレジスタの内容を示す図表である。
【図２４】本発明の第２の実施の形態に係る消失訂正専用回路に適用されるＥＵＣブロックを示す接続図である。
【図２５】図２４の続きを示す接続図である。
【図２６】図２５の続きを示す接続図である。
【図２７】図２６の続きを示す接続図である。
【図２８】図２７の続きを示す接続図である。
【図２９】図２４のＥＵＣブロックにおけるユニットの基本的な構成を示す接続図である。
【図３０】図２９のユニットのロードの処理における接続を示す図である。
【図３１】図２９のユニットのホールド処理におけるレジスタの内容の変化を示す図である。
【図３２】図２９のユニットのホールドの処理における接続を示す図である。
【図３３】図３２の続きを示す接続図である。
【図３４】図３３の続きを示す接続図である。
【図３５】図３４の続きを示す接続図である。
【図３６】図２９のユニットのシフトの処理におけるレジスタの内容の変化を示す図である。
【図３７】図２９のユニットのシフトの処理における接続を示す図である。
【図３８】図３７の続きを示す接続図である。
【図３９】図３８の続きを示す接続図である。
【図４０】図３９の続きを示す接続図である。
【図４１】図２９のユニットの演算処理におけるレジスタの内容の変化を示す図である。
【図４２】図２９のユニットの演算処理における接続を示す図である。
【図４３】図４２の続きを示す接続図である。
【図４４】図４３の続きを示す接続図である。
【図４５】図４４の続きを示す接続図である。
【図４６】図２９のユニットのシフトの処理を伴う演算処理におけるレジスタの内容の変化を示す図である。
【図４７】従来の消失訂正処理の処理手順を示すフローチャートである。
【図４８】図４７の処理手順による消失訂正回路を示すブロック図である。
【図４９】図４８の消失訂正回路に適用されるＥＵＣブロックを示す接続図である。
【図５０】図４９の続きを示す接続図である。
【図５１】図５０の続きを示す接続図である。
【図５２】図５１の続きを示す接続図である。
【図５３】図５２の続きを示す接続図である。
【図５４】多重化に係るＥＵＣブロックを示す接続図である。
【図５５】図５４の続きを示す接続図である。
【図５６】図５５の続きを示す接続図である。
【図５７】図５６の続きを示す接続図である。
【図５８】図５７の続きを示す接続図である。
【図５９】図５８の続きを示す接続図である。
【符号の説明】
１……消失訂正回路、２……ＳＹＮブロック、３、３３、５３……ＥＵＣブロック、４、３４……ＣＨＳブロック
【図１】
0004595238.tif 000041
【図２】
0004595238.tif 000042
【図３】
0004595238.tif 000043
【図４】
0004595238.tif 000044
【図５】
0004595238.tif 000045
【図６】
0004595238.tif 000046
【図７】
0004595238.tif 000047
【図８】
0004595238.tif 000048
【図９】
0004595238.tif 000049
【図１０】
0004595238.tif 000050
【図１１】
0004595238.tif 000051
【図１２】
0004595238.tif 000052
【図１３】
0004595238.tif 000053
【図１４】
0004595238.tif 000054
【図１５】
0004595238.tif 000055
【図１６】
0004595238.tif 000056
【図１７】
0004595238.tif 000057
【図１８】
0004595238.tif 000058
【図１９】
0004595238.tif 000059
【図２０】
0004595238.tif 000060
【図２１】
0004595238.tif 000061
【図２２】
0004595238.tif 000062
【図２３】
0004595238.tif 000063
【図２４】
0004595238.tif 000064
【図２５】
0004595238.tif 000065
【図２６】
0004595238.tif 000066
【図２７】
0004595238.tif 000067
【図２８】
0004595238.tif 000068
【図２９】
0004595238.tif 000069
【図３０】
0004595238.tif 000070
【図３１】
0004595238.tif 000071
【図３２】
0004595238.tif 000072
【図３３】
0004595238.tif 000073
【図３４】
0004595238.tif 000074
【図３５】
0004595238.tif 000075
【図３６】
0004595238.tif 000076
【図３７】
0004595238.tif 000077
【図３８】
0004595238.tif 000078
【図３９】
0004595238.tif 000079
【図４０】
0004595238.tif 000080
【図４１】
0004595238.tif 000081
【図４２】
0004595238.tif 000082
【図４３】
0004595238.tif 000083
【図４４】
0004595238.tif 000084
【図４５】
0004595238.tif 000085
【図４６】
0004595238.tif 000086
【図４７】
0004595238.tif 000087
【図４８】
0004595238.tif 000088
【図４９】
0004595238.tif 000089
【図５０】
0004595238.tif 000090
【図５１】
0004595238.tif 000091
【図５２】
0004595238.tif 000092
【図５３】
0004595238.tif 000093
【図５４】
0004595238.tif 000094
【図５５】
0004595238.tif 000095
【図５６】
0004595238.tif 000096
【図５７】
0004595238.tif 000097
【図５８】
0004595238.tif 000098
【図５９】
0004595238.tif 000099