(57)【特許請求の範囲】
【請求項１】
ｔ個以下の誤りを訂正可能な巡回符号の復号回路であって、受信多項式ｙ（ｘ）から算出された２ｔ個のシンドロームＳｉ（ｉ＝ｂ，ｂ＋１，…，ｂ＋２ｔ−１）に基づいて誤り位置多項式の係数Λｉ（ｉ＝１，２，…，ν；ν≦ｔ）を算出する誤り位置多項式係数計算回路を備え、前記誤り位置多項式の係数Λｉに基づいて復号を行う復号回路において、
前記誤り位置多項式係数計算回路は、前記シンドロームＳｉを所定の規則にしたがって並べたｔ行ｔ列のハンケル行列（Hankel matrix）に、シンドロームＳｉを所定の規則にしたがって並べた付加行［Ｕ］（＝［−Ｓｂ＋ｔ −Ｓｂ＋ｔ＋１ ・・・ −Ｓｂ＋２ｔ−１］）を（ｔ＋１）行目に付け加えた（ｔ＋１）行ｔ列の行列に、マトリクス−リダクション（matrix-reduction）アルゴリズムを適用した（ｔ＋１）行ｔ列の行列の（ｔ＋１）行目を誤り位置多項式の係数Λｉの解とすることを特徴とする復号回路。
【請求項２】
ｔ個以下の誤りを訂正可能な巡回符号の復号回路であって、
受信多項式ｙ（ｘ）から算出された２ｔ個のシンドロームＳｉ（ｉ＝ｂ，ｂ＋１，…，ｂ＋２ｔ−１）に基づいて誤り位置多項式Λ（Ｚ）の係数Λｉ（ｉ＝１，２，…，ν；ν≦ｔ）を算出する誤り位置多項式係数計算回路と、
前記シンドロームＳｉおよび誤り位置多項式Λ（Ｚ）の係数Λｉに基づいて誤り評価多項式の係数Ωｉを算出する誤り評価多項式係数計算回路と、
前記誤り位置多項式Λ（Ｚ）の係数Λｉおよび誤り評価多項式Ω（Ｚ）の係数Ωｉに基づいて推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を計算する計算回路と、
前記推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を逆フーリエ変換して推定誤り多項式ｅ（Ｘ）を計算する計算回路と、
を備え、
前記推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を計算する計算回路は、Λ（Ｚ）Γ（Ｚ）＝１−Ｚｎを満たす相補誤り位置多項式Γ（Ｚ）を計算し、誤り評価多項式Ω（Ｚ）と相補誤り位置多項式Γ（Ｚ）とを用いて該推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を算出することを特徴とする復号回路。
【請求項３】
ｔ個以下の誤りを訂正可能な巡回符号の復号方法であって、前記符号列の受信多項式ｙ（ｘ）から算出された２ｔ個のシンドロームＳｉ（ｉ＝ｂ，ｂ＋１，…，ｂ＋２ｔ−１）に基づいて誤り位置多項式の係数Λｉ（ｉ＝１，２，…，ν；ν≦ｔ）を算出するステップを含み、前記誤り位置多項式の係数Λｉに基づいて復号を行う復号方法において、
前記誤り位置多項式の係数を算出するステップは、
前記シンドロームＳｉを所定の規則にしたがって並べたｔ行ｔ列のハンケル行列（Hankel matrix）に、シンドロームＳｉを所定の規則にしたがって並べた付加行［Ｕ］（＝［−Ｓｂ＋ｔ −Ｓｂ＋ｔ＋１ ・・・ −Ｓｂ＋２ｔ−１］）を（ｔ＋１）行目に付け加えて（ｔ＋１）行ｔ列の行列を算出するステップと、
さらに前記（ｔ＋１）行ｔ列の行列に、マトリクス−リダクション（matrix-reduction）アルゴリズムを適用するステップと、
マトリクス−リダクションアルゴリズムを適用した（ｔ＋１）行ｔ列の行列の（ｔ＋１）行目を誤り位置多項式の係数Λｉの解とするステップと、
を含むことを特徴とする復号方法。
【請求項４】
ｔ個以下の誤りを訂正可能な巡回符号の復号方法であって、
巡回符号によって符号化された符号列の受信多項式ｙ（ｘ）から算出された２ｔ個のシンドロームＳｉ（ｉ＝ｂ，ｂ＋１，…，ｂ＋２ｔ−１）に基づいて誤り位置多項式Λ（Ｚ）の係数Λｉ（ｉ＝１，２，…，ν；ν≦ｔ）を算出するステップと、
前記シンドロームＳｉおよび誤り位置多項式Λ（Ｚ）の係数Λｉに基づいて誤り評価多項式Ω（Ｚ）の係数Ωｉを算出するステップと、
前記誤り位置多項式Λ（Ｚ）の係数Λｉおよび誤り評価多項式Ω（Ｚ）の係数Ωｉに基づいて推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を計算するステップと、
前記推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を逆フーリエ変換して推定誤り多項式ｅ（Ｘ）を計算するステップと、
を含み、
前記推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を計算するステップは、
Λ（Ｚ）Γ（Ｚ）＝１−Ｚｎを満たす相補誤り位置多項式Γ（Ｚ）を計算するステップと、
誤り評価多項式Ω（Ｚ）と相補誤り位置多項式Γ（Ｚ）とを用いて該推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を算出するステップと、
を含むことを特徴とする復号方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、巡回符号（例えば、リード・ソロモン（Reed-Solomon）符号（ＲＳ符号）、ＢＣＨ（Bose-Chaudhuri-Hocqenghem）符号等）によって符号化された符号系列を復号する復号回路および復号方法に関する。
【０００２】
【従来の技術および発明が解決しようとする課題】
従来の復号化の手法について説明する。巡回符号の符号化、及び復号化は有限体ＧＦ（ｑ）（＝ＧＦ（ｐi））の上の元を用いた多項式演算として定式化できる。ｐを素数、ｎをｐと互いに素な正整数、ｐi≡１ ｍｏｄ ｎなる関係を満たす最小の正整数ｉをｍとしたとき、位数ｎの元αがＧＦ（ｐm）に存在し、生成多項式が
【数１】
αb，αb+1，…，αb+2t-1
の２ｔ個の零点の連なりを持つＧＦ（ｑ）（＝ＧＦ（ｐi））の上の符号長ｎ、情報記号数ｋの巡回符号（ｑ元（ｎ，ｋ）巡回符号）とする。ただし、
【数２】
ｑ＝ｐi，ｉ｜ｍ（ｉはｍを割りきる）
である。この巡回符号は、連続した零点より定まる能力、すなわちＢＣＨ限界により定められる設計距離（２ｔ＋１）に基づくｔ個までの代数的誤り訂正が可能な符号である。生成多項式ｇ（Ｘ）に零点の連なりを持つことは、同時にこれらのＧＦ（ｐi）に関して共役な零点も有するが、連続した零点に属さないものは利用しない。
【０００３】
ｑ元（ｎ，ｋ）巡回符号の符号化は以下の符号多項式ｃ（Ｘ）の計算により行われる。
【数３】
ｃ（Ｘ）＝ｉ（Ｘ）ｇ（Ｘ）
この符号化であるが、復号化後の情報記号の抜き出し易さから、一般的には次のような組織符号化が行われる。
【数４】
ｃ（Ｘ）＝ｉ（Ｘ）Ｘn-k−ｒ（Ｘ）
ここで、
【数５】
ｉ（Ｘ）：情報シンボルを係数とする多項式
ｒ（Ｘ）：パリティ検査シンボルを係数とする多項式
ｒ（Ｘ）＝ｉ（Ｘ）Ｘn-k  ｍｏｄ  ｇ（Ｘ）
ｇ（Ｘ）：生成多項式
ｇ（Ｘ）＝ＬＣＭ（ｍb（Ｘ），ｍb+1（Ｘ），…，ｍb+2t-1（Ｘ））
である。ただし、ｍj（Ｘ）はＧＦ（ｐm）の元αjのＧＦ（ｐi）に関する共役元を全て零点として持つ多項式、すなわち最小多項式を表す。特に、リード・ソロモン符号の場合には、αjのＧＦ（ｐi）に関する共役元はαj自身となるため、
【数６】
ｇ（Ｘ）＝（Ｘ−αb）（Ｘ−αb+1）…（Ｘ−αb+2t-1）
となる。
【０００４】
ここで、復号化の説明のため、有限体上のフーリエ変換、逆フーリエ変換について説明する。ｐを素数とする。今、ｐと互いに素な正整数ｎに対して、
【数７】
ｐi≡１ ｍｏｄ ｎ
なる関係を満たす最小の正整数ｉをｍとしたとき、位数ｎの元αがＧＦ（ｐm）に存在する。ここで，ＧＦ（ｐm）上の長さｎの時間領域の系列
【数８】
0003860023.tif 000002
と、周波数領域の系列
【数９】
0003860023.tif 000003
を考える。それぞれの系列に対し、時間領域で未定元Ｘ、周波数領域で未定元Ｚを用いて、以下の式（１）および式（２）の多項式表現を与える。
【数１０】
0003860023.tif 000004
本明細書では、系列及びそれに対応する多項式を同じ意味で混用することがある。このとき、
【数１１】
0003860023.tif 000005
なる関係にあるとき、この二つの多項式（系列）は有限体上のフーリエ変換対である。時間領域から周波数領域への変換をフーリエ変換、周波数領域から時間領域への変換を逆フーリエ変換と呼ぶ。
【０００５】
巡回符号の復号化は，受信多項式
【数１２】
ｙ（Ｘ）＝ｃ（Ｘ）＋ｅ（Ｘ）
より、符号多項式ｃ（Ｘ）を推定する操作である。ただし、誤り多項式ｅ（Ｘ）は誤りシンボルを係数とする誤り多項式であり、誤り個数をν（≦ｔ）個として、その誤りの位置をｊ1，ｊ2，…，ｊνとし、それぞれの位置における誤り量をｅj1，ｅj2，…，ｅjνとしたとき未定元Ｘを用いて次の式（５）のように表される。
【数１３】
0003860023.tif 000006
また、同様にしてｙ（Ｘ）は次の式（６）のようにも表される。
【数１４】
0003860023.tif 000007
【０００６】
復号化の方法は大きく二つに分けられる。それは、
（１）受信多項式ｙ（Ｘ）に対応する系列と全ての符号多項式に対応する系列を比較し、最もハミング距離が近い符号多項式を推定符号多項式とする方法（最ゆう復号法）と、
（２）ｙ（Ｘ）を上述した有限体上のフーリエ変換により、周波数領域での２ｔ個の連続したスペクトル（このスペクトルは一般にシンドロームと呼ばれる）を計算し、この２ｔ個のスペクトル（シンドローム）を用いて推定誤り多項式を求め、受信多項式から推定誤り多項式を減じて符号多項式を求める方法（代数的復号法）、
である。このうち（１）の方法はメモリの規模等の点から、符号の持つ符号多項式の数（符号語の数）が小さい場合にしか使用されない。このため、一般的には（２）の代数的復号法が広く用いられている。以下、本発明に最も関係の深い代数的復号法について従来技術の説明を行う。
【０００７】
代数的復号法では、以下の６つのステップで復号化を行う。
ステップ１：有限体上のフーリエ変換により受信多項式ｙ（Ｘ）より２ｔ個のスペクトル（シンドローム）を計算する。
ステップ２：シンドロームが全て零であれば、誤り無しと判定する。そうでなければステップ３へ進む。
ステップ３：シンドロームから誤り位置多項式と誤り評価多項式を求める。
ステップ４：誤り位置多項式の零点を求め、誤り位置を推定する。
ステップ５：誤り位置多項式と誤り評価多項式とから誤り位置に対応する誤り量を推定し、推定誤り多項式ｅ（Ｘ）を計算する。
ステップ６：受信多項式ｙ（Ｘ）から推定誤り多項式ｅ（Ｘ）を減じ、誤り訂正を行う（推定符号多項式を計算する）。
【０００８】
上記各ステップは、例えば図６に示す復号回路５０によって実行される。図６に示す復号回路５０は、シンドローム計算回路５２、誤り位置多項式の係数計算回路５４、誤り評価多項式の係数計算回路５６、誤り位置の計算回路５８、誤り量の計算回路６０、誤り多項式の計算回路６２、出力回路６４および遅延回路６６を備える。
【０００９】
ステップ１のシンドロームの計算は、ＧＦ（ｐm）の上で受信多項式ｙ（Ｘ）にＧＦ（ｐm）の元αb，αb+1，…，αb+2t-1を代入すること（すなわち、有限体ＧＦ（ｐm）の上のフーリエ変換）により行われる。つまり、
【数１５】
0003860023.tif 000008
により計算される。ｂ≦ｉ≦ｂ＋２ｔ−１なるｉに対し、常に
【数１６】
ｃ（αi）＝０
であることより、
【数１７】
Ｓi＝ｙ（αi）＝ｃ（αi）＋ｅ（αi）＝ｅ（αi）
が成り立つので、ステップ２において２ｔ個のシンドロームすべてが０であれば誤り無し、一つでも０でないものがあれば誤り有りと判断される。
【００１０】
２ｔ個のシンドロームに非零なものが存在したとき、代数的復号法では２ｔ個のシンドロームＳiから誤り多項式を推定することで誤り訂正を行う。すなわち、誤り多項式ｅ（Ｘ）により生じた症状であるシンドロームを受信多項式ｙ（Ｘ）から得た後、このシンドロームを用いて対応する系列のハミング重みが最小の誤り多項式ｅ（Ｘ）を求める。ステップ３では，誤り位置ｊ1，ｊ2，…，ｊνを指し示すＧＦ（ｐm）の元αj1，αj2，…，αjνの逆元α-j1，α-j2，…，α-jνを零点として持つ次の式（７）の誤り位置多項式Λ（Ｚ）の係数の計算を行う。
【数１８】
0003860023.tif 000009
ただし、ν≦ｔである。ここで，Λ（Ｚ）の係数Λ1，Λ2，…，Λνは以下の式（８）を満たす値である。
【数１９】
0003860023.tif 000010
この式（８）を満たす係数Λ1，Λ2，…，Λνを多項式オーダーで求める代数的復号法として、ピーターソン（Perterson）法、ベールカンプ−マッシー（Berlekamp-Massey）法（ＢＭ法）、およびユークリッド（Euclid）法が提案されており、これらはそれぞれＯ（ｔ3），Ｏ（ｔ2），およびＯ（ｔ2）の乗算回数（計算量）で誤り位置多項式を求める。
【００１１】
誤り位置多項式Λ（Ｚ）の係数Λ1，Λ2，…，Λνが求められた後、ステップ４にて誤り位置多項式の零点を求め、誤り位置ｊiを求める。一般的には、α-iを誤り位置多項式Λ（Ｚ）に順次代入し、
【数２０】
Λ（α-i）＝０
を満たすα-iを探索するチェン（Chien）探索と呼ばれる手法が行われる。
【００１２】
ステップ５では、一般的に、誤り評価多項式
【数２１】
0003860023.tif 000011
と誤り位置多項式Λ（Ｚ）を形式微分（導関数）することで得られるΛ´（Ｚ）を用いたフォーニー（Forney）アルゴリズムにより、誤り量を求める。ただし、Ｓ（Ｚ）はシンドロームを係数としたシンドローム多項式
【数２２】
0003860023.tif 000012
である。誤り量ｅjiは、
【数２３】
0003860023.tif 000013
により求められる（フォーニーアルゴリズム）。
【００１３】
ステップ６では
【数２４】
ｃ（Ｘ）＝ｙ（Ｘ）−ｅ（Ｘ）
により誤り訂正を行う。
【００１４】
ここで、従来から知られている代数的復号法、およびその代数的復号法を回路化する際の問題点をまとめておく。
【００１５】
誤り位置多項式及び誤り評価多項式を求める際に良く用いられるピーターソン法、ベールカンプ−マッシー法、及びユークリッド法についてそれぞれ問題点を述べる。計算量がＯ（ｔ3）のピーターソン法により復号、及び復号回路を実現する時には、ｔ以下の全ての誤り数νに対応する誤り位置多項式Λ（Ｚ）の係数計算回路を用意する必要があり、回路規模は計算量のＯ（ｔ3）ではなく、Ｏ（ｔ3）の１からｔまでの総和を取った
【数２５】
0003860023.tif 000014
となるため、Ｏ（ｔ4）となる。計算量がＯ（ｔ2）のベールカンプ−マッシー法により復号、及び復号回路を実現する時には、一つの演算ループ中に条件判断が複数入るため、制御回路が複雑化し回路規模の増大を招く。同様に計算量がＯ（ｔ2）のユークリッド法により復号回路を実現する時には、多項式の割り算を行うため、多項式の次数判定が必要であり、この次数判定のために処理の複雑さが増大し、回路規模の増大を招くばかりか、制御の複雑さを増す要因となっていた。更に、ユークリッド法は計算量がＯ（ｔ2）であるが、演算ループの繰り返し回数が一定でないため、回路構造が規則的でなく回路化が困難である。
【００１６】
ここまで述べた誤り訂正を行う際、シンドローム演算に始まる推定誤り多項式を算出するまでの計算時間だけ受信多項式を遅延させる必要がある。一般的にデジタル通信システム及びデジタル記憶システムにおいて、通信路または記憶媒体を通して受信側が受け取る受信多項式は、一つではなく、連続的に複数個受信される。このような連続的なデジタル通信及びデジタル記憶システムにおいては、受信多項式を一定の時間で遅延させ、求めた推定誤り多項式を減じなければならない。しかしながら、ベールカンプ−マッシー法、およびユークリッド法では誤り個数により推定誤り多項式を求める時間が一定でないため、推定誤り多項式を求めるのに要した時間に応じた遅延時間で推定誤り多項式を遅延させる必要があった。更に、このため推定誤り多項式を求めるのに必要な最大の遅延時間だけ受信多項式を遅延させておく必要があり、条件判断を入れて計算量を抑えたにも関わらず、スループットは最大遅延時間により支配されている。以上のことから、誤り個数によらず、推定誤り多項式を求めるまでの時間が一定、且つ条件判断の条件が少ない方が回路化も容易となる。
【００１７】
誤り位置、及び誤り量の推定では、単純にチェン探索以降の演算を並列化すると、誤り量を求めるフォーニーアルゴリズムの段で、ｎ個の除算器を用意する必要がある。すなわち、フォーニーアルゴリズムの計算量はＯ（ｎｔ）であっても、用意する回路規模はＯ（ｎ2）となる。しかし、ｎ個の除算器の全てが常に使用されるのではなく、ｎ個のうち最大でも誤り訂正可能最大数ｔ個の除算器しか使用されていない。また、除算器の共有化を行っても、誤り位置に応じて除算器を割り振る回路が必要となるため、回路規模は殆ど改善されない。
【００１８】
また、生起したと推定される誤り多項式が復号可能か否か（復号可能・不可能）の判断は、ピーターソン法を用いて誤り位置多項式Λ（Ｚ）、誤り評価多項式Ω（Ｚ）を求めた場合には、行列式の正則性の判定により求めた誤り個数ν、誤り位置多項式Λ（Ｚ）、誤り評価多項式Ω（Ｚ）、およびチェン探索で求めた誤り位置多項式Λ（Ｚ）の零点の個数を用いて次の三つの条件により行う。
（１） ν≧１（但し、ν≦ｔ）
（２） ｄｅｇ（Λ（Ｚ））＞ｄｅｇ（Ω（Ｚ））
（３） ｄｅｇ（Λ（Ｚ））＝（Λ（Ｚ）のＧＦ（ｐm ）上の零点の個数）
以上の三つの条件すべてを満たせば復号可能（生起したと推定される誤り個数がｔ個以下であり、三つの条件のうちいずれか一つでも満たされない場合は復号不能（生起したと推定される誤り個数が（ｔ＋１）個以上）である。
【００１９】
同様に、ベールカンプ−マッシー法を用いて誤り位置多項式Λ（Ｚ）および誤り評価多項式Ω（Ｚ）を求めた場合には、誤り位置多項式Λ（Ｚ）、ＬＦＳＲのレジスタ長Ｌ、およびチェン探索で求めた誤り位置多項式Λ（Ｚ）の零点の個数を用いて次の三つの条件により行う。
（１） ｄｅｇ（Λ（Ｚ））≦ｔ
（２） Ｌ＝ｄｅｇ（Λ（Ｚ））
（３） ｄｅｇ（Λ（Ｚ））＝（Λ（Ｚ）のＧＦ（ｐm ）上の零点の個数）
以上の三つの条件すべてを満たせば復号可能（生起したと推定される誤り個数がｔ個以下）であり、三つの条件のいずれか一つでも満たされない場合は復号不能（生起したと推定される誤り個数が（ｔ＋１）個以上）である。
【００２０】
同様に、ユークリッド法を用いて誤り位置多項式Λ（Ｚ）および誤り評価多項式Ω（Ｚ）を求めた場合、誤り位置多項式Λ（Ｚ）、誤り評価多項式Ω（Ｚ）、およびチェン探索で求めたΛ（Ｚ）の零点の個数を用いて次の三つの条件により行う。
（１） ｄｅｇ（Λ（Ｚ））≦ｔ
（２） ｄｅｇ（Λ（Ｚ））＞ｄｅｇ（Ω（Ｚ））
（３） ｄｅｇ（Λ（Ｚ））＝（Λ（Ｚ）のＧＦ（ｐm ）上の零点の個数）
以上の三つの条件すべてを満たせば復号可能（生起したと推定される誤り個数がｔ個以下）であり、三つの条件のいずれか一つでも満たされない場合は復号不能（生起したと推定される誤り個数が（ｔ＋１）個以上）である。
【００２１】
また、代数的復号法の誤り多項式を求める操作（すなわちステップ４およびステップ５）を変更したトランスフォーム復号法と呼ばれる代数的復号法では、次のステップで復号化が実行される。
ステップ１：有限体上の逆フーリエ変換により受信多項式ｙ（Ｘ）より２ｔ個のスペクトル（シンドローム）を計算する。
ステップ２：シンドロームが全て零であれば、誤り無しと判定する。そうでなければ、ステップ３へ進む。
ステップ３：シンドロームから誤り位置多項式と誤り評価多項式を求める。
ステップ４：誤り位置多項式の係数とシンドロームの再帰関係を利用し、再帰的に推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）のｎ個の係数（スペクトル）のうちシンドローム以外の（ｎ−２ｔ）個の係数（スペクトル）を計算する。
ステップ５：Ｅ（Ｚ）を有限体上の逆フーリエ変換することにより、推定誤り多項式ｅ（Ｘ）を計算する。
ステップ６：受信多項式ｙ（Ｘ）から推定誤り多項式ｅ（Ｘ）を減じ、誤り訂正を行う（推定符号多項式を計算する。）。
【００２２】
ステップ１、ステップ２、およびステップ３については、通常の代数的復号法の方法と同じである。ステップ４では、推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）の係数（スペクトル）Ｅiを求める。Ｅiのうちの２ｔ個は
【数２６】
Ｅi＝ｅ（αi）＝Ｓi  （ｉ＝ｂ，ｂ＋１，…，ｂ＋２ｔ−１）
により明らかになっているので、この２ｔ個のシンドローム（スペクトル）を使い、他の（ｎ−２ｔ）個の係数Ｅiを
【数２７】
0003860023.tif 000015
（ｉ＝ｂ＋２ｔ，ｂ＋２ｔ＋１，…，ｎ−１，ｎ（＝０），ｎ＋１（＝１），ｎ＋２（＝２），…，ｎ＋ｂ−１（＝ｂ−１））
により求める。
【００２３】
ステップ５では
【数２８】
ｅi＝（１／ｎ）Ｅ（α-i）
により、すなわち、Ｅiを係数として持つ多項式Ｅ（Ｚ）にαi（ｉ＝０，１，…，ｎ−１）を代入（すなわち、有限体上の逆フーリエ変換）することにより推定誤り多項式ｅ（Ｘ）の係数ｅiを求める。ステップ６は、通常の代数的復号法の方法と同じである。
【００２４】
トランスフォーム復号法ではフォーニーアルゴリズムを必要としないため、通常の代数的復号法で問題となっていた除算器に起因する問題は存在しない。しかし、この方法でも通常の代数的復号法におけるΛ（Ｚ）の係数計算の問題の他に、以下の点で問題がある。
（１）Ｅiの全ての値を計算するにあたって、Ｅiの計算は再帰的であるため、低い次数のＥiを計算した後でないと更に高い次数のＥiが計算できず、計算速度が遅い。
（２）Ｅ（Ｚ）の全ての係数をシンドロームから求めた後、誤り多項式ｅ（Ｘ）を計算しているので、回路で実現しやすいアルゴリズムではあるが、Ｏ（ｎ2）の固定乗算回路が必要である。
この二つの問題のうち、（２）は代数的復号法におけるフォーニーアルゴリズムの回路規模Ｏ（ｎ2）の問題と同じ問題であり、通常の代数的復号法と比較した場合のトランスフォーム復号法の最大の問題点は（１）に限定される。
【００２５】
本発明はこのような事情に鑑みてなされたものであり、その目的は、誤り位置多項式Λ（Ｚ）の係数計算回路が同一、且つ推定誤り多項式を求める遅延時間が一定（すなわち演算ループの繰り返し回数が常に一定回数）、且つ条件判断が少ない巡回符号（リード・ソロモン符号、ＢＣＨ符号等）の復号法、および復号回路を提供することにある。すなわち、回路化が容易な復号法、その復号法を用いた復号回路を提供することにある。
【００２６】
【課題を解決するための手段】
本発明にかかる復号回路は、ｔ個以下の誤りを訂正可能な巡回符号の復号回路であって、受信多項式ｙ（ｘ）から算出された２ｔ個のシンドロームＳｉ（ｉ＝ｂ，ｂ＋１，…，ｂ＋２ｔ−１）に基づいて誤り位置多項式の係数Λｉ（ｉ＝１，２，…，ν；ν≦ｔ）を算出する誤り位置多項式係数計算回路を備え、前記誤り位置多項式の係数Λｉに基づいて復号を行う復号回路において、前記誤り位置多項式係数計算回路は、前記シンドロームＳｉを所定の規則にしたがって並べたｔ行ｔ列のハンケル行列（Hankel matrix）に、シンドロームＳｉを所定の規則にしたがって並べた付加行［Ｕ］（＝［−Ｓｂ＋ｔ −Ｓｂ＋ｔ＋１ ・・・ −Ｓｂ＋２ｔ−１］）を（ｔ＋１）行目に付け加えた（ｔ＋１）行ｔ列の行列に、マトリクス−リダクション（matrix-reduction）アルゴリズムを適用した（ｔ＋１）行ｔ列の行列の（ｔ＋１）行目を誤り位置多項式の係数Λｉの解とする。
【００２７】
また本発明にかかる復号回路は、ｔ個以下の誤りを訂正可能な巡回符号の復号回路であって、受信多項式ｙ（ｘ）から算出された２ｔ個のシンドロームＳｉ（ｉ＝ｂ，ｂ＋１，…，ｂ＋２ｔ−１）に基づいて誤り位置多項式の係数Λｉ（ｉ＝１，２，…，ν；ν≦ｔ）を算出する誤り位置多項式係数計算回路と、前記シンドロームＳｉおよび誤り位置多項式の係数Λｉに基づいて誤り評価多項式の係数Ωｉを算出する誤り評価多項式係数計算回路と、前記誤り位置多項式の係数Λｉおよび誤り評価多項式Ω（Ｚ）の係数Ωｉに基づいて推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を計算する計算回路と、前記推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を逆フーリエ変換して推定誤り多項式ｅ（Ｘ）を計算する計算回路と、を備え、前記推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を計算する計算回路は、Λ（Ｚ）Γ（Ｚ）＝１−Ｚnを満たす相補誤り位置多項式Γ（Ｚ）を計算し、誤り評価多項式Ω（Ｚ）と相補誤り位置多項式Γ（Ｚ）とを用いて該推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）を算出する。
【００２８】
誤り位置多項式の係数計算回路および誤り多項式の係数計算回路のうち少なくとも一つは、以下でも説明するように、係数計算回路が同一、かつ推定誤り多項式を求める遅延時間が一定（すなわち演算ループの繰り返し回数が常に一定回数）、かつ条件判断が少なく、並びに制御回路が不要となるため、その回路構成がより簡素化される。
【００２９】
誤り位置多項式の係数計算回路を、ｔ行ｔ列のハンケル行列に１行ｔ列の付加行を付け加えた（ｔ＋１）行ｔ列の行列にマトリクス−リダクションアルゴリズムを用いることで計算するように構成すれば、誤り位置多項式の係数計算回路が同一、かつ演算ループの繰り返し回数が常に一定回数（誤り訂正可能数：ｔ回）、かつ条件判断が少なくなり、回路サイズの増大を抑えることができる。なお、マトリクス−リダクションアルゴリズム自体は公知の技術であり、例えば、E.R.Berlekamp著，「Algebraic Coding Theory（代数符号理論）」，McGraw-Hill社刊（1968年）等に記載されている。
【００３０】
また、推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）の係数Ｅiを再帰的にではなく、シンドローム多項式Ｓ（Ｚ）と誤り位置多項式Λ（Ｚ）により計算される誤り評価多項式Ω（Ｚ）、およびΓ（Ｚ）の多項式乗算により直接求めることで、Ｅ（Ｚ）の計算を高速に処理することができる。
【００３１】
推定誤り多項式ｅ（Ｘ）の係数ｅiをＥ（Ｚ）の有限体上の逆フーリエ変換により求めることで、推定誤り多項式ｅ（Ｘ）を直接求めることで、誤り位置に応じて除算器を割り振る必要もないため複雑な制御回路が不要となる。
【００３２】
本発明は、デジタル通信システムおよびデジタル記憶システムにおいて巡回符号（リード・ソロモン符号、ＢＣＨ符号等）を採用したあらゆる誤り訂正回路に対して応用することが可能である。
【００３３】
【発明の実施の形態】
図１に本発明に係る巡回符号（例えば、リード・ソロモン（Reed-Solomon）符号（ＲＳ符号）、ＢＣＨ（Bose-Chaudhuri-Hocqenghem）符号等）の復号回路１０の機能ブロック図を示す。受信多項式ｙ（Ｘ）の係数ｙ0〜ｙn-1はシンドローム計算回路１２と出力回路１４に入力される。シンドローム計算回路１２は受信多項式ｙ（Ｘ）の係数ｙ0〜ｙn-1に基づいてシンドロームＳb〜Ｓb+2t-1を算出する。シンドローム計算回路１２は誤り位置多項式の係数計算回路１６に接続されており、誤り位置多項式の係数計算回路１６はシンドロームＳb〜Ｓb+2t-1に基づいて誤り位置多項式の係数Λ1〜Λνを算出する。なお、ν（ν≦ｔ）は推定される誤りの数である。また、シンドローム計算回路１２および誤り位置多項式の係数計算回路１６は、誤り評価多項式の係数計算回路１８に接続されており、誤り評価多項式の係数計算回路１８は、シンドロームＳb〜Ｓb+2t-1および誤り位置多項式の係数Λ1〜Λνに基づいて誤り評価多項式の係数Ω0〜Ων-1を算出する。誤り位置多項式の係数計算回路１６および誤り評価多項式の係数計算回路１８は誤り多項式のスペクトル（有限体上のフーリエ変換）計算回路２０に接続されており、誤り多項式のスペクトル計算回路２０は、誤り位置多項式の係数Λ1〜Λνおよび誤り評価多項式の係数Ω0〜Ων-1に基づいて誤り多項式のスペクトルＥ0〜Ｅn-1を算出する。誤り多項式のスペクトル計算回路２０は、誤り多項式の係数計算回路２２に接続されており、誤り多項式の係数計算回路２２は誤り多項式のスペクトルＥ0〜Ｅn-1に基づいて係数ｅ0〜ｅn-1を算出する。出力回路１４は入力された誤り多項式ｅ（Ｘ）の係数ｅ0〜ｅn-1を用いて、遅延回路２４を介して入力された受信多項式ｙ（Ｘ）の係数ｙ0〜ｙn-1の誤りを訂正した符号多項式ｃ（Ｘ）の係数ｃ0〜ｃn-1を出力する。
【００３４】
従来の復号法では、誤り訂正可能数ｔに比例して増大するループの繰り返し回数、および条件判断（分岐）の数にしたがって回路規模が増大する。誤り訂正可能数ｔは誤り訂正能力であり、これに起因する回路規模の増大は避けられない。このため、本発明では、条件判断（分岐）の数を減らすことにより回路規模の削減を図る。
【００３５】
また従来の復号法では、誤り位置多項式の係数の計算回路が同一であっても、演算ループの繰り返し回数が生起したとみなされる誤り（および誤り個数）により異なり、且つ条件判断が複数入る（または多項式除算を含む）ため回路規模の増大を招いていた。しかし、誤り位置多項式の係数の計算回路が同一、かつ演算ループの繰り返し回数が常に一定回数（誤り訂正可能数：ｔ回）、かつ条件判断が少ない巡回符号の復号回路の提供を目的とする本発明では、制御、および条件判断すべき項目が少なくなるため制御回路が単純化し、回路構成の単純化や回路規模の点で従来の復号法に比べ有利となる。また、本発明の復号回路のスループットは演算ループの回数を常に一定回数（誤り訂正可能数：ｔ回）として制御を単純化しているが、従来の復号法による復号回路のスループットも誤り訂正可能数ｔにより決定されるため、本発明の復号回路と従来の復号回路のスループットは同じである。
【００３６】
以下、各要素ごとに実行すべき計算内容について説明する。
【００３７】
＜シンドローム計算＞
シンドローム計算は上述した従来技術と同じである。
【００３８】
＜有限体上のフーリエ変換・逆フーリエ変換の再表現＞
まず、後の説明のために母関数を用いて有限体上のフーリエ変換を再表現する。多項式を一つのクラスとして含む母関数の概念において、０次係数が非零の母関数は常に通常の多項式の乗算に関する逆元を持つ。今、長さｎの時間領域の系列の要素ａi（ｉ＝０，１，２，…，ｎ−１）に対して、母関数（１−αiＺ）を考える。この母関数の逆元のａi倍はαn＝１ゆえ、以下の式（１３）のような係数が周期的な無限次の多項式となる。
【数２９】
0003860023.tif 000016
これは、無限等比級数における収束の条件等を必要としないという母関数の性質である。この式（１３）の母関数をｉについて０からｎ−１までの和を取ると以下の式（１４）が成立する。
【数３０】
0003860023.tif 000017
この式（１４）の両辺に（１−Ｚn）を乗じると、次の式（１５）が得られる。
【数３１】
0003860023.tif 000018
以上のように導出された周波数領域の多項式は明らかにａ（Ｘ）の有限体上のフーリエ変換Ａ（Ｚ）である。つまり、時間領域の多項式ａ（Ｘ）の係数ａiとＧＦ（ｐm）の元、周波数領域の未定元Ｚを用い、αiを関連させた母関数の和を取ることにより、ａ（Ｘ）の有限体上のフーリエ変換Ａ（Ｚ）を導出することができる。
【００３９】
同様にして、母関数を用いて有限体上の逆フーリエ変換を再表現する。有限体上のフーリエ変換のときと同様に、次の式（１６）の母関数に着目する。
【数３２】
0003860023.tif 000019
この式（１６）の母関数をｉについて０からｎ−１までの和を取ると次の式（１７）が成立する。
【数３３】
0003860023.tif 000020
すなわち、次の式（１８）が得られる。
【数３４】
0003860023.tif 000021
以上のようにして導出された時間領域の多項式ａ（Ｘ）はＡ（Ｚ）の有限体上の逆フーリエ変換である。
【００４０】
＜誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換＞
ここで、誤り多項式の有限体上のフーリエ変換を母関数により再表現する。誤り多項式は、誤っていない位置における誤り量が零であると考えることができる。したがって、誤り量ｅhの中で非零のものをν個、その誤り量をｅjiとしているので、長さｎのうちのν個の和をとり、次の式（１９）を得る。
【数３５】
0003860023.tif 000022
この式（１９）より、次の式（２０）が得られる。
【数３６】
0003860023.tif 000023
【００４１】
＜シンドロームの再表現＞
ここで、式（２０）の母関数の分子部分に
【数３７】
0003860023.tif 000024
を乗じた式（２１）について考える。
【数３８】
0003860023.tif 000025
この母関数は、周波数領域の低次部分にシンドローム系列を含み、周期的な無限周期系列をとる。次に、この母関数全体を２ｔシフトした式（２２）を考える。
【数３９】
0003860023.tif 000026
ここで、これら二つの母関数（式（２１）、式（２２））の差を取ると次の式（２３）が得られる。式（２３）では、２ｔ次以上の係数部分はそれぞれの母関数とも同じ値であり、打ち消し合い、０次から２ｔ−１次の部分だけが残っている。
【数４０】
0003860023.tif 000027
ここで重要なのが、母関数によるシンドロームの表現が剰余による合同関係でなく、等号によるストロンガー  アサーション（Stronger Assertion）であることである。従来のシンドローム表現は、合同関係によるウィーカー  アサーション（Weaker Assertion）に過ぎなかった。ここで、新たに示す母関数によるシンドロームの定め方は、０次係数から無限次係数まで全ての次数において等しいストロンガー  アサーションである。これによって、係数を零にするという連立方程式を定めることが出来る。
【００４２】
（１）誤り位置多項式の係数の計算：誤り位置多項式の係数計算回路１６の動作式（２３）の両辺に誤り位置多項式Λ（Ｚ）を乗じると、左辺の母関数表現部分の分母部分は、誤り位置多項式の因数のうちのいずれかであるので、誤り位置多項式と相殺され次の式（２４）が得られる。
【数４１】
0003860023.tif 000028
この式（２４）の両辺に関して、次数における関係を考える。式（２４）のそれぞれの項において次数を表記すると、
【数４２】
0003860023.tif 000029
となる。この両辺の係数比較を図２に示す。図２は、対応する次数の係数が非零であるか否かを示している。したがって、ν次から２ｔ−１次までの項が零の状態で等式が成立することを意味している。すなわち、Ｓ（Ｚ）Λ（Ｚ）のν次から２ｔ−１次までの範囲において、零である必要がある。しかし、誤り個数ν個が導出できていないとすると、誤り訂正可能な最大個数ｔ個を想定しておくことが妥当である。したがって、ｔ次から２ｔ−１次までの係数が零になるようにＳ（Ｚ）Λ（Ｚ）の係数を置くことを考える。そのようにすることで、Λ1，Λ2，…，Λtのｔ個の未知数に対して、ｔ個の連立方程式となる。このそれぞれの方程式が互いに独立である場合は、誤り位置多項式の係数が決定できることが保証される。しかし、誤りがν個発生している場合、１次独立な方程式の数はν個であるので、未知数νに対する連立方程式がν個であることが必要十分である。しかし、ここでは誤り訂正可能最大個数ｔにおいておくことで、未知数ΛiのうちΛν+1，…，Λtが零になることを許した解を求めることで問題を解決する。また、このν次方程式は求められた行列が表し得る最小次数の方程式でなければならない。ここで、式（２４）のｔ次から（２ｔ−１）次の両辺の各項の比較により、次の式（２６）が成り立つ。
【数４３】
0003860023.tif 000030
この式（２６）の連立方程式を行列の積の形を用い、ＳiとΛiの行列の積で表す。この際、連立方程式から行列の積の形への置き換えにおいては、項の並びによって、いくつかのパターンが考えられる。そのうち、Λ（Ｚ）の係数Λiの並び順の置き方は、最終的な解の決定において、多大な違いを生じさせる。特に、Λ（Ｚ）の係数を昇順（Λ1，Λ2，…，Λν）に並べるものと降順（Λν，Λν1，…，Λ1）に並べるものでは、解の最終決定の際に手間の量が異なる。本明細書では、降順に配置することで、最小次数の解Λ（Ｚ）が導出できることを示す。このため式（２７）の行列表現を用いることとする。
【数４４】
0003860023.tif 000031
この式（２７）を簡略的に
【数４５】
0003860023.tif 000032
と記すこととする。ただし、
【数４６】
0003860023.tif 000033
とする。特に行列［Ｓ］はハンケル（Hankel）行列と呼ばれる。
【００４３】
ここで、誤り個数と誤り位置を同時に決定する誤り位置多項式Λ（Ｚ）の係数Λiの計算法を与える。まず、式（２７）の行列を、後に述べるマトリクス−リダクションアルゴリズムを適用するのに適した形に変換する。具体的には、式（２７）の右辺をすべて左辺に移項することにより、１行ｔ列の行列［Λ］は新たに（１×（ｔ＋１））要素として−１が付け加えられ１行（ｔ＋１）列の行列に、またｔ行ｔ列の行列［Ｓ］は新たに（ｔ＋１）行目として［−Ｓb+t  −Ｓb+t+1  …  −Ｓb+2t-1］（＝付加行；augmented行）が加えられ（ｔ＋１）行ｔ列の行列になり、以下の式（２８）が得られる。
【数４７】
0003860023.tif 000034
この式（２８）は簡略的に
【数４８】
0003860023.tif 000035
のように表現できる。この行列
【数４９】
0003860023.tif 000036
の行列［Ｓ］の部分がリデュースド  トライアンギュラー  アイデンポテント  フォーム（reduced traiangular idempotent form）となるように次の４ステップからなる一連の操作をｔ回繰り返す。この操作はマトリクス−リダクションアルゴリズムと呼ばれる。
【００４４】
＜マトリクス−リダクションアルゴリズム＞
ステップ１：（１，１）要素が非零であれば、何もしない。（１，１）要素が零であれば、他の列と列置換する。第１列目と列置換が可能な列は、第１行目の要素が非零でかつ対角要素が零である列。そのような列が無ければ、第１行目の要素が非零でかつ対角要素が非零の列と列置換する。もし、第１行目の要素が全て零である場合は、何もしない。
ステップ２：第１列目の全ての要素を（１，１）要素で割る。もし、（１，１）要素が零である場合は、何もしない。
ステップ３：第１列目を各対象列の第１行要素倍した値をその対象列から引き、（１，１）要素以外の第１行目の要素を零にする。
ステップ４：行回転、列回転する。
【００４５】
以上のマトリクス−リダクションアルゴリズムにおける追加行［Ｕ］の操作に関しては、基本列操作が及ぼす処理については、行列全体が同様に影響を受けるが、行回転については正方行列［Ｓ］のみが操作対象となる。行列
【数５０】
0003860023.tif 000037
に対して以上のステップ１からステップ４の操作をｔ回繰り返すと、以下の式（２９）のように行列［Ｓ］の部分がリデュースド  トライアンギュラー  アイデンポテント  フォームと呼ばれる形の行列となる。ただし、Ｓi,jは行列のｉ行ｊ列要素を表すものとする。
【数５１】
0003860023.tif 000038
ここで、式（２９）の対角要素にあるδi（１≦ｉ≦ｔ）は０もしくは１であり、０の場合はその列の他の要素はすべて０となり、１の場合はその行の他の要素は全て０となる。得られた式（２９）の行列に対し、ｔ行ｔ列の行列［Ｓ］の部分からｔ行ｔ列の単位行列を引くことで、式（３０）の行列を得る。
【数５２】
0003860023.tif 000039
式（３０）の各行の１次結合とＵ´の和により表される行列は、式（２８）の連立方程式を満たす
【数５３】
0003860023.tif 000040
の解である。
【００４６】
ここで、
【数５４】
0003860023.tif 000041
のように、［Ｓ］のｉ行目の行ベクトルが示されたとすると、λi（Ｚ）は、
【数５５】
0003860023.tif 000042
と表される多項式に対応することにする。すると、これらのΛ（Ｚ），λi（Ｚ），Ｕ´（Ｚ）の間の関係として、不定な連立方程式の一般解は各行の一次結合の自由度をもつことから、多項式を用いた表現では次の式（３２）のようになる。
【数５６】
0003860023.tif 000043
ここで、ｋiはＧＦ（ｐm）の元であるとする。このとき、式（３２）が表す（ｐm）t-ν種類の多項式全てがΛ（Ｚ）の候補となりうる。また、式（３３）に示すように、λi（Ｚ）はΛ（Ｚ）により割り切られる。
【数５７】
0003860023.tif 000044
しかし、真のΛ（Ｚ）の係数は、式（３２）の一次結合の中で、最も次数の小さいものである。すなわち、λiの係数ｋiを全て零にした式（３２）が最小次数になり、Λ（Ｚ）の解になる。
【数５８】
0003860023.tif 000045
【００４７】
＜復号可能・不能の条件＞
以上のようにして得られた誤り位置多項式Λ（Ｚ）の次数は常にｔ次以下となるため、復号可能・不能の判断に必要な条件は、
（１） ｄｅｇ（Λ（Ｚ））＞ｄｅｇ（Ω（Ｚ））
（２） ｄｅｇ（Λ（Ｚ））＝（Λ（Ｚ）のＧＦ（ｐm）上の零点の個数）
（（２）は「１−ＺnをΛ（Ｚ）が割り切る」と等価）
の二つとなる。条件（１），（２）ともに満たすとき復号可能（生起したと推定される誤り個数がｔ個以下）であり、条件（１），（２）のいずれか一つでも満たされないときは復号不能（生起したと推定される誤り個数が（ｔ＋１）個以上）である。すなわち、従来法（ピーターソン法、ベールカンプ−マッシー法、ユークリッド法）に比べ条件判断の数が少なくなる。
【００４８】
ここまで述べたように、母関数によるシンドローム表現を定めることで、シンドローム多項式と誤り位置多項式との積をとったものの次数関係から不定な連立方程式をたてることができ、この連立方程式から構成される行列による関係は、ハンケル行列を構成する。その不定な連立方程式の解を導出するアルゴリズムから、真の誤り位置多項式となる解を決定できる方法を与えた。この方法は、連立方程式の解を求める方法に過ぎず、非常に理解が容易かつ、簡潔な誤り位置導出操作である。
【００４９】
なお、上記マトリクス−リダクションアルゴリズムのステップ１については、例えば図３に示される回路構成によって、またステップ３については、例えば図５に示される回路によって、それぞれ実現される。図３に示す回路は、ＯＲ回路（論理和）３０、ＡＮＤ回路（論理積）３２およびインバータ（否定）３４等を組み合わせて構成される。図４は、図３において省略記載した部分（Ｓi,jの記入された正方形部分３６）の詳細図である（Ｓi,jが有限体ＧＦ（２m）の元の場合の一例）。また図５において、４０は有限体ＧＦ（２m）上の乗算器、また４２は有限体ＧＦ（２m）上の加算器を示す。なお、誤り評価多項式の係数計算回路１８は、従来より公知の手法により、シンドロームＳb〜Ｓb+2t-1および誤り位置多項式の係数Λ1〜Λνに基づいて誤り評価多項式の係数Ω0〜Ων-1を算出する。
【００５０】
誤り位置（誤り位置多項式）が導出できたところで、誤り量の決定をしなければならないが、これについては、母関数を用いたフーリエ変換の考え方を適用して導出された誤り多項式導出法を用いると、個々の誤り量をそれぞれ導出することなく、誤り多項式そのものを導出することができる。以下、その手法について述べる。この手法について簡単に述べた後、復号回路について述べる。
【００５１】
（２）誤り多項式のスペクトルＥiの計算：誤り多項式のスペクトル計算回路２０の動作
本発明においては、推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）そのものが求まり、かつ代数的復号法の一つであるトランスフォーム復号法での問題（１）（Ｅiの計算は再帰的であるため低い次数のＥiを計算した後でないと更に高い次数のＥiが計算できないことから、計算速度が遅い。）を解決する方法を与える。具体的な原理、方法を以下に示す。今、次の式（３５）に示す多項式Ｓn（Ｚ）を考える。
【数５９】
0003860023.tif 000046
このＳn（Ｚ）の０次から２ｔ−１次係数は受信多項式より得られるシンドロームＳb，Ｓb+1，…，Ｓb+2t-1であるため、復号に際して、予め知ることができる多項式である。したがって、式（３５）のＳn（Ｚ）は、式（３６）のように表現することもできる。
【数６０】
0003860023.tif 000047
このとき、Ｓn（Ｚ）とＥ（Ｚ）の関係は、次の式（３７）のようになる。ただし、［ｆ（ｙ）］nは、ｆ（ｙ）  ｍｏｄ  （１−ｙn）を表すものとする。
【数６１】
0003860023.tif 000048
このＳn（Ｚ）を用いることにより、次の式（３８）が成立する。
【数６２】
0003860023.tif 000049
式（３８）の両辺に（１−Ｚn）を乗じることで、次の式（３９）を得る。
【数６３】
0003860023.tif 000050
この式（３９）により導出されたＳn（Ｚ）の系列を発生する無限周期系列に対して、Λ（Ｚ）と
【数６４】
0003860023.tif 000051
なる関係にある相補誤り位置多項式Γ（Ｚ）を考えると式（３９）は次の式（４１）で表現できる。
【数６５】
0003860023.tif 000052
更に、式（４１）の両辺にＺbを乗じ、（１−Ｚn）で剰余を取ることで、次の式（４２）を得る。
【数６６】
0003860023.tif 000053
この式（４２）の左辺には、式（４５）に示す誤り位置多項式Λ（Ｚ）と母関数の和の形との積の部分ができる。
【数６７】
0003860023.tif 000054
これは、
【数６８】
0003860023.tif 000055
により得られる式（４６）の誤り評価多項式Ω（Ｚ）そのものである。
【数６９】
0003860023.tif 000056
従って、式（４３）が成立する。
【数７０】
0003860023.tif 000057
この式（４３）は誤り位置多項式Λ（Ｚ）の係数を正しく導き出すことができれば、シンドロームの再帰関係を用いることなく誤り位置多項式Λ（Ｚ）と誤り評価多項式Ω（Ｚ）を用いて推定誤り多項式ｅ（Ｘ）のフーリエ変換Ｅ（Ｚ）が導出でき、その逆フーリエ変換をすることで、推定誤り多項式ｅ（Ｘ）を直接導出できることを示している。すなわち、トランスフォーム復号法の問題点の（１）（Ｅiの全ての値を計算するにあたって、Ｅiの計算は再帰的であるため、低い次数のＥiを計算した後でないと更に高い次数のＥiが計算できないことから、計算速度が遅い。）が、式（４３）の事実によりＥ（Ｚ）が即座に求まることで解決される。
【００５２】
ここで、相補誤り位置多項式Γ（Ｚ）の計算が必要となるが、Γ（Ｚ）の計算は１−ＺnをΛ（Ｚ）で割る多項式の割り算を行うことで行われる。この多項式の割り算は、余りが零多項式となる（１−ＺnをΛ（Ｚ）が割り切る）か否かの判断が、ピーターソン法、ペールカンプ−マッシー法、およびユークリッド法における生起したと推定される誤り多項式が復号可能な誤り多項式であるか否かの判断の条件（３）（ｄｅｇ（Λ（Ｚ））＝（Λ（Ｚ）のＧＦ（ｐm）零点の個数））に相当するため、ピーターソン法、ベールカンプ−マッシー法、およびユークリッド法により求めたΛ（Ｚ）に対して行っているチェン探索と同様の計算であり、チェン探索の代わりの計算である。ただし、ここでの多項式の割り算は、チェン探索のように誤り位置を探索するものではないため誤り位置が計算できないが、誤り多項式の有限体上のフーリエ変換が式（４３）により求まり、式（４３）のＥ（Ｚ）を有限体上の逆フーリエ変換することで誤り多項式ｅ（Ｘ）そのものが求まるため問題とはならない。また、ここでの多項式の割り算ではｔ個の固定乗算をｎ回繰り返し行っている（ｔ次の多項式除算）が、一般的に良く使われるチェン探索においてもｔ個の固定乗算をｎ回繰り返し行うことが必要であり、同様の計算量であるため計算量の観点からも問題とはならない。結果として、残る復号可能・不能の判断に必要な条件は一つの条件（１）（ｄｅｇ（Λ（Ｚ））＞ｄｅｇ（Ω（Ｚ）））のみとなる。
【００５３】
（３）誤り多項式の係数ｅiの計算：誤り多項式の係数計算回路２２の動作
先にも述べたように、推定誤り多項式ｅ（Ｘ）の有限体上のフーリエ変換Ｅ（Ｚ）が式（４３）により計算されるので、このＥ（Ｚ）の有限体上の逆フーリエ変換を計算すると推定誤り多項式ｅ（Ｘ）の係数が求まる。
【００５４】
また、以上の結果からフォーニーアルゴリズムで用いられているような、誤り位置それぞれの誤り量を逐次導出することも可能である。すなわち、式（４４）に示すように、誤り位置αjiの逆元α-jiを未定元に代入することで、その誤り位置での誤り量が導出される。
【数７１】
0003860023.tif 000058
このような逐次的な導出により、誤り位置を個々に導出することなしに、対応する誤り量を導出することも可能となる。すなわち、従来ではチェン探索とフォーニーアルゴリズムを用いて行っていた誤り位置の算出、および誤り位置に対応する誤り量を算出する過程を同時に解決している。この過程の計算量はＯ（ｎ2）に比例するが、誤り位置を指定する等の制御が不要となるため、回路が簡単化される。
【００５５】
（４）出力：出力回路１４の動作
出力回路は誤りを訂正した符号多項式の係数ｃ0及至ｃn-1を出力する。従来技術の説明で述べたが、
【数７２】
ｃ（Ｘ）＝ｙ（Ｘ）−ｅ（Ｘ）
であることから、推定誤り多項式ｅ（Ｘ）の係数ｅiをｙiから減算することにより、訂正された符号多項式の係数ｃiが得られる。
【００５６】
以上、好適な実施形態について説明したが、例示したに過ぎず、等価な範囲において種々の変形が可能である。例えば、従来の誤り位置多項式の係数計算回路のみを本発明にかかる誤り位置多項式の係数計算回路（１６）に代えることも可能である。また、従来の誤り位置、および誤り位置に対応する誤り量の計算回路、および誤り多項式の係数計算回路を、本発明にかかる誤り多項式のスペクトル計算回路（２０）、誤り多項式の係数計算回路（２２）に代えることも可能である。ただしこの場合、従来の誤り多項式の計算回路と本発明にかかる誤り多項式の計算回路（２２）とが異なるものとなることに注意されたい。
【００５７】
【発明の効果】
以上説明したように、誤り位置多項式Λ（Ｚ）の係数計算回路が同一、かつ演算ループの繰り返し回数が常に一定回数、かつ条件判断が少ない巡回符号の復号法、および復号回路が実現される。
【図面の簡単な説明】
【図１】  本発明に係る、巡回符号の復号回路の機能ブロック図である。
【図２】  式（２４）の両辺の係数比較を説明するための図である。
【図３】  マトリクス−リダクションアルゴリズムのステップ１を実現する回路図（論理回路）である。
【図４】  図３において省略記載した部分（Ｓi,jの記入された正方形部分）の詳細図である（Ｓi,jが有限体ＧＦ（２m）の元の場合の一例）。
【図５】  マトリクス−リダクションアルゴリズムのステップ３を実現する回路図（論理回路）である。
【図６】  巡回符号の従来の復号回路の機能ブロック図である。
【符号の説明】
１０  復号回路、１２  シンドローム計算回路、１４  出力回路、１６  誤り位置多項式の係数計算回路、１８  誤り評価多項式の係数計算回路、２０  誤り多項式のスペクトル計算回路、２２  誤り多項式の係数計算回路。
【図１】
0003860023.tif 000059
【図２】
0003860023.tif 000060
【図３】
0003860023.tif 000061
【図４】
0003860023.tif 000062
【図５】
0003860023.tif 000063
【図６】
0003860023.tif 000064