(57)【要約】【課題】  本発明は、リードソロモン復号器と、リードソロモン符号の軟判定復号法に関する。【解決手段】  シンドローム多項式と、消失多項式と、修正シンドローム多項式が、これら多項式の係数を繰り返し更新することにより、並行して計算される。
2005525040.tif 000002
【特許請求の範囲】
【請求項１】
リードソロモン符号の軟判定復号方法において、
シンドローム多項式、消失多項式及び修正シンドローム多項式を、その場で計算することを特徴とする方法。
【請求項２】
シンドローム多項式
【数１】
2005525040.tif 000022
を計算するステップと、
消失多項式
【数２】
2005525040.tif 000023
を計算するステップと、
修正シンドローム多項式を
T(x)=Γ(x)S(x) mod xM
により作成するステップと、
鍵方程式
Λ(x)T(x)=Ω(x) mod xM
を、バーレカンプ・マッシイ法又はユークリッド法により解くステップと、
フォーニー多項式
ψ(x)=Λ(x)Γ(x)
を計算するステップと、
誤り及び消失値を、フォーニー方程式に基づき計算するステップとを有することを特徴とする請求項１に記載の方法。
【請求項３】
消失多項式及び修正シンドローム多項式の計算は、データシンボルvN-1,…v1,v0の入力と共に、その場で実行されることを特徴とする請求項２に記載の方法。
【請求項４】
シンドローム多項式は、
【数３】
2005525040.tif 000024
の形式で、係数Si, i=0,1,…,M-1を繰り返し更新することにより計算され、
係数は、各シンボルクロックjで新しいシンボルvnが到着したときに、位置ｎのべき乗αnを計算し、
Si,j=Si,j-1+vnαin, i=0,1,…,M-1、ここでSi,-1=0
で更新されることを特徴とする請求項１から３のいずれか１項に記載の方法。
【請求項５】
消失多項式は、多項式
【数４】
2005525040.tif 000025
を繰り返し更新することにより、その場で計算され、
更新は、各タイミングjで、新しい消失vnが生じたとき、消失位置ｎのべき乗αnを計算し、多項式を
Γj(x)=Γj-1(x)(1-αnx)=(Γ0,j-1+Γ1,j-1x+…+Γp,j-1xp)(1-αnx)
と更新することで実行されることを特徴とする請求項１から４のいずれか１項に記載の方法。
【請求項６】
修正シンドローム多項式の計算は、
【数５】
2005525040.tif 000026
を更新することで実行されることを特徴とする請求項１から５のいずれか１項に記載の方法。
【請求項７】
修正シンドローム多項式の、その場での計算は、
多項式Γ-1(x)=1; T-1(x)=0と予め設定するステップと、
各シンボルクロックで１のシンボルvnを得るステップと、
第１のシステムクロックで、
【数６】
2005525040.tif 000027
を計算するステップと、
vnが消失であるか否かを判定するステップと、
消失であれば、第２のシステムクロックで
Tj(x)=T*(x)(1-αnx)
Γj(x)=Γj-1(x)(1-αnx)
を計算し、消失でなければ、
Tj(x)=T*(x)
Γj(x)=Γ*(x)
とするステップとにより実行されることを特徴とする請求項１から６のいずれか１項に記載の方法。
【請求項８】
修正シンドローム多項式は、
Tn(x)=Tn-1(x)(1-αnx)+vnΓn-1(x)、ここでΓ-1(x)=1
の形式で、その場で計算されることを特徴とする請求項１から７いずれか１項に記載の方法。
【請求項９】
修正シンドローム多項式は、
多項式Γ-1(x)=1; T-1(x)=0と予め設定するステップと、
各シンボルクロックで１のシンボルvnを得るステップと、
vnが消失であるか否かを判定するステップと、
消失であれば、
Tj(x)=Tj-1(x)(1-αnx)+vnΓj-1(x)
Γj(x)=Γj-1(x)(1-αnx)
を計算し、消失でなければ、
【数７】
2005525040.tif 000028
を計算するステップとにより、その場で計算されることを特徴とする請求項１から８のいずれか１項に記載の方法。
【請求項１０】
リードソロモン符号の軟判定復号のためのプログラム手段を含み、前記プログラム手段は、シンドローム多項式、消失多項式及び修正シンドローム多項式の、その場での計算に適用される、デジタル記憶媒体のような、コンピュータプログラム製品。
【請求項１１】
シンドローム多項式、消失多項式及び修正シンドローム多項式の、その場での計算のための手段を含むリードソロモン復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り検出／訂正符号に関する。より詳細には、リードソロモン復号器で使用されるシステム及び方法に関する。
【背景技術】
【０００２】
一般的に用いられる誤り訂正手法としては、リードソロモン誤り訂正符号がある。リードソロモン符号の概要及びその応用については、例えば非特許文献１や、非特許文献２に記載されている。
【０００３】
特許文献１は、非除多項式と除多項式との除算の剰余の次数が所定の条件を満足するまで、前記剰余で除多項式を繰り返し除算するユークリッド互助回路の形式によるリードソロモン復号器を開示している。
【０００４】
ユークリッド互助回路は、非除多項式と除多項式を、それぞれ保存するレジスタグループと、非除多項式を除多項式で除算することにより生ずる剰余を保存するためのフィードバックループと、レジスタの内容をシフトするシフト器と、非除多項式の係数と、除多項式の係数を交換する交換器とを有する。
【０００５】
復号器は、受信符号語からシンドロームを計算するシンドローム計算器と、受信符号語に同期した消失位置フラグから消失位置データを生成する消失位置生成器と、修正シンドロームを生成する修正シンドローム生成器と、前記消失位置データから消失位置多項式を生成する消失位置多項式生成器と、誤り位置多項式及び誤り評価多項式を求めるユークリッド互助回路と、誤り位置及び誤りの値を得るチェン探索器と、受信符号語の誤りを訂正する訂正処理器とを有する。修正シンドローム生成器と消失位置多項式生成器は、ユークリッド互助回路と共用となっている。
【０００６】
リードソロモン復号器を実現する他のアプローチは、それぞれ、特許文献２から特許文献７に開示されている。
【０００７】
【特許文献１】米国特許第５５１７５０９号明細書
【特許文献２】米国特許第５９９１９１１号明細書
【特許文献３】米国特許第６０３２２８３号明細書
【特許文献４】米国特許第６３０４９９４Ｂ１号明細書
【特許文献５】米国特許第５５３７４２６号明細書
【特許文献６】欧州特許出願公開第０８２１４９３Ａ１号明細書
【特許文献７】欧州特許出願公開第０９４２４２１Ａ１号明細書
【非特許文献１】Stephen B.Wicker, Vijay K. Bhargava, “Reed-Solomon Codes and Their Applications”, IEEE Press, 1994年
【非特許文献２】Bernard Sklar, “Digital Communications, Fundamentals and Applications”, Second Edition, Prentice Hall PTR, 2001年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
一般的に、修正シンドローム多項式の計算は、シンドロームと消失多項式の積の計算により行われる。修正シンドローム多項式を得るためのこの計算には、追加のサイクルと計算時間が必要となる。
【０００９】
従って、本発明は、修正シンドローム多項式の計算に付加的なサイクルを必要としないリードソロモン符号の軟判定復号方法を提供することを目的とする。
【００１０】
本発明の目的は、独立請求項の特徴により解決される。本発明の好ましい形態は、従属請求項に記載される。
【課題を解決するための手段】
【００１１】
本発明は、シンドローム及び消失多項式と同様に、修正シンドローム多項式の、その場での計算を並行して行うことにより、リードソロモン符号の軟判定復号の計算時間を最小とすることを可能としている。つまり、本発明は、シンドロームと消失多項式の計算が完了する前に、修正シンドローム多項式の計算を実行することを可能としている。
【００１２】
本発明は、特に、入力シンボルを得たその場で、修正シンドローム多項式を計算することを可能とする点で有利である。よって、多項式の拡張として一般的に参照される、別の計算ステップを省略することができる。
【００１３】
シンボル受信後、シンドロームと消失多項式の積の計算を行うことなく、直接、修正シンドロームを更新することができる更なる利点がある。これは、全体の計算時間とハードウェアへの要求を削減する結果となる。
【００１４】
本発明の一般的概念は、修正シンドロームを計算するために必要なサイクル数を削減することである。修正シンドローム多項式を得るために、消失多項式とシンドローム多項式の乗算を行う必要がある。修正シンドローム多項式を得るための、従来からある直列アルゴリズムの複雑さは、
c=r(l+1)-l(l+1)/2
である。ここでrはＲＳ符号語のパリティシンボル数であり、lは符号語内の消失数である。従来からある直列―並列アルゴリズムの複雑さは、
c=1+1
である。本発明の一般概念は、修正シンドロームを、その場で計算することである。よって、本方法は、修正シンドロームの計算に付加的なサイクルを必要とせず、計算パワーと時間を削減する。
【発明を実施するための最良の形態】
【００１５】
軟判定復号において、受信器は、
２e+f<dmin                                                                （１）
である限り訂正が可能である。ここで、eは誤り数であり、fは消失数であり、dminはハミング距離である。
【００１６】
エラー計算のために以下のステップが行われる。
１．シンドローム多項式を計算する。
【００１７】
【数８】
2005525040.tif 000003
２．消失多項式を計算する。
【００１８】
【数９】
2005525040.tif 000004
３．修正シンドローム多項式を
T(x)=Γ(x)S(x) mod xM                                                    （４）
により作成する。
４．鍵となる方程式
Λ(x)T(x)=Ω(x) mod xM                                                    （５）
を、バーレカンプ・マッシイ法又はユークリッド法により解く。
５．フォーニー多項式
ψ(x)=Λ(x)Γ(x)                                                          （６）
を計算する。
６．誤り及び消失値を、フォーニー方程式に基づき計算する。
【００１９】
式（２）及び（３）から明らかなように、それらは、データシンボルvN-1,…,v1,v0の入力と共に、その場で計算ができる。
【００２０】
以下に上記ステップ１、つまり式（２）についてのより詳しい説明を行う。
【００２１】
エラーベクトル
【００２２】
【数１０】
2005525040.tif 000005
を多項式
e(x)=e0+e1x+…+eN-1xN-1, ei∈GF(28)                                      （７）
で表現する。復号器の入力での受信多項式は、
v(x)=c(x)+e(x)=v0＋v1x+…+vN-1xN-1, vi∈GF(28)                            （８）
である。ここで、多項式の係数は、受信ベクトル
【００２３】
【数１１】
2005525040.tif 000006
の要素である。符号語多項式c(x)は生成多項式g(x)で割り切ることができ、また、i=0,1,…,M-1に対してg(αi)=0であるため、生成多項式の根、つまり、α0,α1,…,αM-1により、
【００２４】
【数１２】
2005525040.tif 000007
を求めて多項式v(x)を評価する。
上記は、最後の式の集合が、誤りパターン成分を伴うことのみを意味し、符号語の誤りを示してはいない。上記は、シンドロームと呼ばれ、Sj、j=0,1,…,M-1は、
【００２５】
【数１３】
2005525040.tif 000008
である。上記シンドロームは、以下の形式のシンドローム多項式を形成するために使用される。
【００２６】
【数１４】
2005525040.tif 000009
式（１１）の、その場での計算は、係数Si,i=0,1,…,M-1を、繰り返し更新することにより達成できる。各シンボルクロックjで、新しいシンボルvnが到着し、位置nのべき乗αnが計算され、係数は以下の通り更新される。
Ｓi,j=Ｓi,j-1+vnαin、i=0,1,…M-1、ここでSi,-1=0                        （１２）
【００２７】
図１に、その場でシンドローム計算を実行するハードウェアを示す。新しい符号列の開始時に、レジスタ１は、第１シンボルの位置のべき乗で初期化される。レジスタ２は０で初期化される。新しいシンボルが到着するたびに、レジスタ１及び２は動作し、シンドロームが式（１２）のとおりに更新され、レジスタ１のべき乗は１減らされる。
【００２８】
以下にステップ２、つまり式（３）についてのより詳細な説明を行う。
【００２９】
p個の消失が、位置j0,j1,…jp-1で生じたものとすると、消失多項式は、以下の方法で計算される。
【００３０】
【数１５】
2005525040.tif 000010
上記式の、その場での計算は、多項式を繰り返し更新することで達成できる。各ｊにおいて、新しい消失vnが生じたとき、消失位置nのべき乗αnが計算され、多項式が以下のように更新される。
Γj(x)=Γj-1(x)*(1-αnx)=(Γ0,j-1+Γ1,j-1x+…+Γp,j-1xp)*(1-αnx)      （１４）
式（１４）の最後の多項式を検査すると、係数は、
【００３１】
【数１６】
2005525040.tif 000011
と記述できる。
【００３２】
式（１５）による、消失多項式の、その場での計算を実行するハードウェアを図２に示す。入力シンボルが消失である場合、図のスイッチが切り替えられ、回路は式（１５）に従った計算を実行する。
【００３３】
シンボルが消失ではない場合は、スイッチは、図の位置のままである。スイッチは、組合せ論理で実現される。よって、余分なクロックディレイの原因とはならない。回路は、シンボル情報と共に消失信号に直接接続される。新しい符号列の開始時において、レジスタ１は、第１シンボルの位置のべき乗、例えば、ＤＶＤのインナー符号に対してはα181で初期化される。
【００３４】
レジスタ２は、０で初期化される。新しいシンボルが到着するたびに、レジスタ１及びレジスタ２が動作し、シンドロームが式（１５）に従い更新され、レジスタ１のべき乗項は１減らされる。
【００３５】
修正シンドローム多項式は、式（２）のシンドローム多項式を、式（３）の消失多項式で乗算することにより
T(x)=S(x)Γ(x)  mod  xM
=(S0+S1x+S2ｘ2+…+SM-1xM-1)(Γ0+Γ1x+Γ2x2+…+Γpxp)  mod  xM    （１６）
と得られる。結果は、２つの多項式の巡回畳み込み
【００３６】
【数１７】
2005525040.tif 000012
となる。
【００３７】
本発明によると、式（２）の代わりに式（１７）を使用し、
【００３８】
【数１８】
2005525040.tif 000013
又はよりよい表現として
【００３９】
【数１９】
2005525040.tif 000014
が求められる。
【００４０】
この式は、前の消失を考慮して、多項式の係数をどのように更新すべきかを指示しているものと解釈できる。現時点がステップj-1で、レジスタTi、i=0,1,…,M-1が正しい修正シンドロームを保持しているものとすると、ステップjで新たなデータシンボルを受信して、単に修正シンドローム多項式を式（１９）に従って更新すればよい。
【００４１】
以上の情報に基づき、修正シンドロームの、その場での計算を行う、アルゴリズムＡについて説明する。入力シンボルが消失と示されているか否かにより、アルゴリズムＡは、それぞれ、２又は１の連続する計算を必要とする。しかし、修正シンドロームの、その場での計算のための、代替のアルゴリズムＢも使用可能である。アルゴリズムＢは、２つの代替ブランチから成り、入力シンボルが消失と示されているか否かにより、そのうちの１つが選択され実行され、各ブランチは、問題となっている場合に必要な総ての計算を１のシステムクロックで実行する。
【００４２】
アルゴリズムＡ
式（１９）を用いることで、シンドロームの計算を行うことなしに、修正シンドロームを直接計算することが可能となる。図３は、その場での計算の第一実施形態を示すフローチャートである。フローチャートは、２つの補助的な項T*(x)及びΓ*(x)を計算する式（２０）と、入力シンボルvnが消失である場合に、補助的な項より反復結果Tj(x)及びΓj(x)を計算する式（２１）とからなる。各シンボルクロックで、新しいシンボルを得たときに、修正シンドロームは、式（２０）に基づき更新される。各計算ステップで得られた修正シンドロームは、最新の受信シンボルまでにおいては正確である。
【００４３】
このアルゴリズムにおいて、システムクロックレートは、少なくともシンボルクロックレートの２倍である必要がある。最後のシンボルの計算後にアルゴリズムは終了し、正しい修正シンドロームが得られる。
【００４４】
消失が起こった場合は、式（２０）による更新と、式（２１）で示されているように多項式を根で乗ずるために、２システムクロックが必要となる。消失の場合に、式（２０）及び(２１)の順序は交換可能である。その場合、ストリームの第1シンボルが消失した場合は、レジスタＴ０は１に予めロードしておく必要があり、他の場合は、式（２１）の前半部分は、０にしておく必要があることに注意する。
【００４５】
式（２０）の計算は、式（１９）で示した巡回畳み込みから直接導ける。よって、以下に、消失シンボルを得た際のアルゴリズムについて記載する。現時点をステップn-1とすると、式（１９）の線形畳み込みである、以下に示す修正シンドロームがメモリに得られる。
【００４６】
【数２０】
2005525040.tif 000015
そして、消失多項式は、
Γn-1(x)=1+Γ1,n-1x+Γ2,n-1x2+…+Γp,n-1xp                            （２３）
である。
【００４７】
次に、ステップnで、消失シンボルvnが到着したとすると、式（２０）の計算は、
【００４８】
【数２１】
2005525040.tif 000016
となり、式（２１）が
【００４９】
【数２２】
2005525040.tif 000017
で計算される。
【００５０】
巡回畳み込みにより、以下の式が導かれ、
【００５１】
【数２３】
2005525040.tif 000018
上式は、
【００５２】
【数２４】
2005525040.tif 000019
と書き換えることができる。
実際に、これは、式（１９）による、シンドロームと消失多項式の線形畳み込みである。
【００５３】
修正シンドロームの、その場での計算を行うアルゴリズムＡの実施形態を、図４に示す。スイッチが図示された位置あれば、式（２０）による計算を実行する。スイッチが切り替えられると、式（２１）による計算を実行する。
【００５４】
スイッチは、組合せ論理で実現され、よって、余分なクロック遅延をもたらさない。図１及び図２の実施形態と比較して、セル又はレジスタ毎に加算器を１つ付加することのみが必要であることがわかる。これは、付加的な多項式の乗算は必要でないため、ハードウェアの削減ができることを意味する。
【００５５】
新しい符号例の始まりにおいて、図４のレジスタ１は、例えばＤＶＤのインナー符号の場合はα181といった、第１シンボルの位置のべき乗で初期化される。レジスタ２及び３は、0で初期化される。シンボルクロックの立ち上がり毎に、新しいシンボルが到着し、べき乗を１減らすように、レジスタ１が更新される。その後、シンボルクロックの立ち下りでレジスタ２が動作し、式（２０）によりシンドロームを更新する。
【００５６】
到着シンボルが消失と示されている場合、スイッチが切り替えられ、レジスタ２及びレジスタ３が再度動作し、式（２１）を計算する。符号列の最終シンボルの終わりで、最後の計算が行われた後、レジスタ２は完全な符号列の修正シンドロームを保持し、レジスタ３は、消失多項式を保持する。
【００５７】
図５に示す、図３の方法のタイミング動作例について以下に説明を行う。
【００５８】
ＤＶＤのインナー符号のように、Ｍ＝１０で、次数が下がる順番であるものとする。シンボルの次数は、１８１で始まり０で終わる。レジスタにはT(x)=0で、Γ-1(x)=１が予め設定されている。以下のデータ列を受信したものとする。
v181=α6, v*180=α9, v179=α10, v*178=α12, v177=α15, v176=…,…, v0＝α…
ここで、v*iは、消失と示されているシンボルを表す。図５に示すように、シンボルクロックの立ち上がりで、新しいシンボルvnを、消失情報と共に得て、図４に示す回路のレジスタ１はシンボルの正確なべき乗項αnに更新される。シンボルクロックの立ち上がり後で、図５において１と示されている第１のシステムクロックで、図４に示す回路のレジスタ２は、図示された位置で動作し、式（２０）が計算される。
【００５９】
消失信号が真であれば、図４のスイッチは切り替えられ、回路のレジスタ２及びレジスタ３は、図５において２と示されている、システムクロックの次の立ち上がりで再度動作し、式（２１）の計算を行う。第１８２番目のシンボルでの最後の計算後、完全な符号語の正しい修正シンドロームを得る。現在の例で、第５番目の入力シンボルまでの中間結果の詳細を以下に説明する。
【００６０】
従来の方法
まず第１に、以下に説明する本発明のアルゴリズムの結果の検証のため、従来の方法で中間の修正シンドロームを計算する。式（２）により、データストリームのシンドローム
S(x)=(α6+α9+α10+α12+α15)+(α6α181+α9α180+α10α179+α12α178+α15α177)x+…+(α6α9*181+α9α9*180+α10α9*179+α12α9*178+α15α9*177)x9
=α169+α79x+α113x2+α37x3+α194x4+α112x5+α239x6+α168x7+α174x8+α240x9                                                                      （２８）
Γ(x)=(1-α180x) (1-α178x)=1+α228x+α103x2                        （２９）
が得られる。
【００６１】
２つの多項式を乗算することで、現在のシンボルまでの修正シンドローム多項式が、
T(x)=S(x)Γ(x) mod xM =α169+(α79+α169α228)x+(α113+α79α228+α169α103)x2+…+(α240+α174α228+α168α103)x9
=α169+α134x+α119x2+α68x3+α128x4+α172x5+α21x6+α40x7+α217x8+α152x9                                                                      （３０）
として得られる。
【００６２】
その場で計算するアルゴリズム
計算は、入力シンボル順で行われる。各ステップの後において、修正シンドロームの結果は、最新の受信シンボルまでにおいて正確である。
【００６３】
１．データシンボルv181=α6を得て、１番目のシステムクロック１で、式（２０）を計算する。
T0(x)=α6(1+α181x+α2*181x2+…+α9*181x9)
=α6+α187x+α113x2+α39x3+α220x4+α146x5+α72x6+253x7+α179x8+α105x9                                                                        （３１）
Γ0=1                                                                （３２）
【００６４】
２．消失シンボルv*180=α9を得て、１番目のシステムクロック１で式（２０）を計算する。
T*(x)=(α6+α9)+(α187+α9α180)x+(α113+α9α2*180)x2+…+(α105+α9α9*180)x9
=α229+α237x+α138x2+0*x3+α244x4+α194x5+α37x6+α94x7+α57x8+α35x9                                                                          （３３）
２番目のシステムクロック２で、式（２１）を計算する。
T1(x)=α229+(α237+α180α229)x+(α138+α180α237)x2+…+(α35+α180α57)x9
=α229+α211x+α137x2+α63x3+α244x4+α170x5+α96x6+α22x7+α203x8+α129x9                                                                      （３４）
及び
Γ1(x)=1+α180x                                                        （３５）
【００６５】
３．データシンボルv179=α10を得て、１番目のシステムクロック１で、方程式（２０）を計算する。
T2(x)=(α229+α10)+(α211+α10(α179+α180))x+(α137+α10(α2*179+α179α180))x2+…+(α129+α10(α9*179+α8*179α180))x9
=α199+α179x+α162x2+α87x3+α209x4+α48x5+α201x6+133x7+α182x8+α215x9                                                                        （３６）
Γ2(x)=1+α180x                                                        （３７）
【００６６】
４．消失シンボルv*178=α12を得て、１番目のシステムクロック１で式（２０）を計算する。
T*(x)=(α199+α12)+(α179+α12(α178+α180))x+(α162+α12(α2*178+α178α180))x2+…+(α215+α12(α9*178+α8*178α180))x9
=α216+α110x+α187x2+α111x3+α17x4+α146x5+α64x6+37x7+α108x8+α39x9                                                                          （３８）
２番目のシステムクロック２で、方程式（２１）を計算する。
T3(x)=α216+(α110+α178α216)x+(α187+α178α110)x2+…+(α39+α178α108)x9
=α216+α36x+α234x2+α135x3+α85x4+α88x5+α202x6+α244x7+α166x8+α231x9                                                                      （３９）
及び
Γ3(x)=1+(α180+α178)x+α180α178x2=1+α228x+α103x2                （４０）
【００６７】
５．データシンボルv177=α15を得て、１番目のシステムクロック１で、式（２０）を計算する。
T4(x)=(α216+α15)+(α36+α15(α177+α228))x+(α234+α15(α2*177+α177α228+α103))x2+…+(α231+α15(α9*177+α8*177α228+α7*177α103))x9
=α169+α134x+α119x2+α68x3+α128x4+α172x5+α21x6+α40x7+α217x8+α152x9                                                                      （４１）
Γ4(x)=1+(α180+α178)x+α180α178x2=1+α228x+α103x2                （４２）
【００６８】
式（４２）と（２９）を、及び式（４１）と（３０）の比較で、アルゴリズムを検証する。この結果は、最終的な修正シンドロームの結果ではなく、単に５つの受信シンボルまでの修正シンドロームの中間結果である。完全な符号列の修正シンドロームは、第１８２番目の計算後に得られる。
【００６９】
アルゴリズムＢ
以下に、修正シンドローム多項式の計算のための代替アルゴリズムＢの詳細について説明する。
式（２１）に式（２０）を代入することで、
【００７０】
【数２５】
2005525040.tif 000020
より良くは
【００７１】
【数２６】
2005525040.tif 000021
が求められ、消失シンボルを得たときの、２番目のシステムクロックでの計算を回避できる。
【００７２】
よって式は、
Tn(x)=Tn-1(x)(1-αnx)+vnΓn-1(x), ここでΓ-1(x)=1                      （４５）
と書くことができる。
【００７３】
これで、入力シンボル毎に１システムクロックのみを必要とする、第２のアルゴリズムＢが表現できる。
【００７４】
図６に示すフローチャートは、その場での計算の第２実施形態を示す。１つの繰り返し結果Tj(x)及びΓj(x)を計算するために、フローチャートは、入力シンボルvnが消失である場合に使用される式（４６）と、他の場合に使用される式（４７）とからなる。
【００７５】
各シンボルクロックで、入力シンボルを得たとき、修正シンドロームが更新される。各計算ステップで、結果として得られる修正シンドロームは、最新の受信シンボルまでにおいて正確である。アルゴリズムＢでは、システムクロックレートは、シンボルクロックレートと同じであり、速い計算が行われる。最後のシンボル後にアルゴリズムは終了し、正しい修正シンドロームが得られる。
【００７６】
図７は、修正シンドロームの、その場での計算の第２実施形態である。スイッチが図示する位置にある場合、回路は、式（４７）に従った計算を行う。スイッチが切り替えられた場合、回路は、式（４６）に従った計算を実現する。
【００７７】
スイッチは、組合せ論理で実現され、よって、余分なクロック遅延をもたらさない。図４の構成と比較すると、セル又はレジスタ毎に、乗算器及び加算器を１つ付加することが必要である。ハードウェアの構成が増加することによる遅延の増加が、計算時間を削減する。
【００７８】
新しい符号例の始まりにおいて、図７のレジスタ１は、例えばＤＶＤのインナー符号の場合はα181といった、第１シンボルの位置のべき乗で初期化される。レジスタ２及び３は、０で初期化される。スイッチは、消失信号に直接接続されている。総てのレジスタ１、２及び３は、シンボルクロックの立ち上がりで動作し、消失信号に応じて、式（４６）又は（４７）によりシンドロームを更新する。
【００７９】
次のシンボルのため、クロックにより、べき乗を１減らすようにレジスタ１が更新される。符号列の最終シンボルの終わりで、最後の計算が行われた後、レジスタ２は完全な符号列の修正シンドロームを保持し、レジスタ３は、消失多項式を保持する。
【００８０】
タイミング動作及びアルゴリズム例について以下に説明を行う。ＤＶＤのインナー符号のように、Ｍ＝１０で、次数が下がる順番であるものとする。シンボルの次数は、１８１で始まり０で終わる。レジスタにはT(x)=0で、Γ-1(x)=１が予め設定されている。以下のデータ列を受信したものとする。
v181=α6, v*180=α9, v179=α10, v*178=α12, v177=α15, v176=…,…, v0＝α…
ここで、v*iは、消失と示されているシンボルを表す。図８に示すように、システムクロックの立ち上がり毎に、新しいシンボルvn及び消失情報が得られる。
【００８１】
消失信号は、図７の回路のスイッチに供給される。消失信号が偽であれば、スイッチは、図示する位置のままであり、消失信号が真であれば、スイッチは切り替えられる。図８において１と示されているシステムクロックの立ち上がりで、図７に示す回路が動作し、式（４６）又は（４７）が計算される。最後に、つまり第１８２番目のシンボルクロック後に、完全な符号語の正しい修正シンドロームを得る。現在の例で、第５番目の入力シンボルまでの中間結果の詳細を以下に説明する。
【００８２】
計算は、入力シンボル順の行われ、各ステップ後において、結果として得られる修正シンドロームは、最新の受信シンボルまでにおいては正確である。
【００８３】
１．データシンボルv181=α6を得て、式（４７）を計算する。
T0(x)=α6(1+α181x+α2*181x2+…+α9*181x9)
=α6+α187x+α113x2+α39x3+α220x4+α146x5+α72x6+253x7+α179x8+α105x9                                                                          （４８）
Γ0=1                                                                  （４９）
【００８４】
２．消失シンボルv*180=α9を得て、式（４６）を計算する。
T1(x)=α6+(α187+α180α6)x+(α113+α180*187)x2+…+(α105+α180*179)x9+α9
=α229+α211x+α137x2+α63x3+α244x4+α170x5+α96x6+α22x7+α203x8+α129x9                                                                      （５０）
及び
Γ1(x)=1+α180x                                                        （５１）
【００８５】
３．データシンボルv179=α10を得て、式（４７）を計算する。
T2(x)=(α229+α10)+(α211+α10(α179+α180))x+(α137+α10(α2*179+α179α180))x2+…+(α129+α10(α9*179+α8*179α180))x9
=α199+α179x+α162x2+α87x3+α209x4+α48x5+α201x6+133x7+α182x8+α215x9                                                                        （５２）
Γ2(x)=1+α180x                                                      （５３）
【００８６】
４．消失シンボルv*178=α12を得て、式（４６）を計算する。
T3(x)=α199+(α179+α178α199)x+(α162+α178α179)x2+…+(α215+α178α182)x9+α12+α12α180x
=α216+α36x+α234x2+α135x3+α85x4+α88x5+α202x6+α244x7+α166x8+α231x9                                                                      （５４）
及び
Γ3(x)=1+(α180+α178)x+α180α178x2=1+α228x+α103x2                （５５）
【００８７】
５．データシンボルv177=α15を得て、式（４７）を計算する。
T4(x)=(α216+α15)+(α36+α15(α177+α228))x+(α234+α15(α2*177+α177α228+α103))x2+…+(α231+α15(α9*177+α8*177α228+α7*177α103))x9
=α169+α134x+α119x2+α68x3+α128x4+α172x5+α21x6+α40x7+α217x8+α152x9                                                                      （５６）
Γ4(x)=1+(α180+α178)x+α180α178x2=1+α228x+α103x2                （５７）
【００８８】
式（５６）と（２９）を、及び式（５７）と（３０）の比較で、アルゴリズムを検証する。この結果は、最終的な修正シンドロームの結果ではなく、単に５つの受信シンボルまでの修正シンドロームの中間結果である。完全な符号列の修正シンドロームは、第１８２番目の計算後に得られる。
【図面の簡単な説明】
【００８９】
【図１】公知の、その場でのシンドローム計算を実行するハードウェアのブロックダイアグラムである。
【図２】公知の、その場での消失多項式の計算を実行するハードウェアのブロックダイアグラムである。
【図３】本発明による修正シンドローム多項式の、その場での計算の実施形態のフローチャートである。
【図４】本発明による修正シンドローム多項式の、その場での計算を実行するハードウェアのブロックダイアグラムである。
【図５】図３のフローチャートに関するタイミングダイアグラムである。
【図６】修正シンドローム多項式の、その場での計算の、他の方法を説明する図である。
【図７】図６の方法を実行するハードウェアのブロックダイアグラムである。
【図８】図６の方法についてのタイミングダイアグラムである。
【符号の説明】
【００９０】
１、２、３  レジスタ
【図１】
2005525040.tif 000029
【図２】
2005525040.tif 000030
【図３】
2005525040.tif 000031
【図４】
2005525040.tif 000032
【図５】
2005525040.tif 000033
【図６】
2005525040.tif 000034
【図７】
2005525040.tif 000035
【図８】
2005525040.tif 000036
【手続補正書】
【提出日】平成16年6月19日(2004.6.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Ｎシンボルからなり、ＮシンボルのうちＭシンボルが検査シンボルであるリードソロモン符号の軟判定復号方法において、
シンドローム多項式、消失多項式及び修正シンドローム多項式を、新しいデータシンボルが到着したときに、各シンボルクロックで、前記多項式のそれぞれの係数を、繰り返し更新することにより並行して計算し、符号語の最後のシンボルでの係数の更新が実行された後、符号語のための多項式を直接得ることを特徴とする方法。
【請求項２】
シンドローム多項式S(x)を
【数１】
2005525040.tif 000037
ここで、viは、入力データシンボル
として計算するステップと、
消失多項式Γ(x)を
【数２】
2005525040.tif 000038
として計算するステップと、
修正シンドローム多項式を
T(x)=Γ(x)S(x) mod xM
により作成するステップと、
間接的な鍵方程式
Λ(x)T(x)=Ω(x) mod xM
を、バーレカンプ・マッシイ法又はユークリッド法により解き、多項式Λ(x)とΩ(x)を決定するステップと、
フォーニー多項式
ψ(x)=Λ(x)Γ(x)
を計算するステップと、
誤り及び消失値を、フォーニー方程式に基づき計算するステップとを有することを特徴とする請求項１に記載の方法。
【請求項３】
消失多項式及び修正シンドローム多項式の計算は、データシンボルvN-1,…v1,v0の入力と共に、その場で実行されることを特徴とする請求項２に記載の方法。
【請求項４】
シンドローム多項式は、
【数３】
2005525040.tif 000039
の形式で、係数Si, i=0,1,…,M-1を繰り返し更新することにより計算され、
係数は、各シンボルクロックjで新しいシンボルvnが到着したときに、位置ｎのべき乗αnを計算し、
Si,j=Si,j-1+vnαin, i=0,1,…,M-1、ここでSi,-1=0
で更新されることを特徴とする請求項１から３のいずれか１項に記載の方法。
【請求項５】
消失多項式は、多項式
【数４】
2005525040.tif 000040
を繰り返し更新することにより、その場で計算され、
更新は、各シンボルクロックjiで、新しく到着したシンボルが消失と示されたとき、消失位置jiのべき乗
【数５】
2005525040.tif 000041
を計算し、多項式を
【数６】
2005525040.tif 000042
と更新することで実行されることを特徴とする請求項１から４のいずれか１項に記載の方法。
【請求項６】
修正シンドローム多項式の、その場での計算は、
多項式Γ-1(x)=1; T-1(x)=0と予め設定するステップと、
各シンボルクロックで１のシンボルvnを得るステップと、
シンボルクロック内の、第１のシステムクロックで、
【数７】
2005525040.tif 000043
を計算するステップと、
vnが消失であるか否かを判定するステップと、
消失であれば、シンボルクロック内の、第２のシステムクロックで
Tj(x)=T*(x)(1-αnx)
Γj(x)=Γj-1(x)(1-αnx)
を計算し、消失でなければ、
Tj(x)=T*(x)
Γj(x)=Γ*(x)
とするステップとにより実行されることを特徴とする請求項１から５のいずれか１項に記載の方法。
【請求項７】
修正シンドローム多項式は、入力シンボルが消失と示されている場合に、
Tn(x)=Tn-1(x)(1-αnx)+vnΓn-1(x)、ここでΓ-1(x)=1
の形式で、その場で更新するステップを含むことを特徴とする請求項１から５のいずれか１項に記載の方法。
【請求項８】
修正シンドローム多項式は、
多項式Γ-1(x)=1; T-1(x)=0と予め設定するステップと、
各シンボルクロックで１のシンボルvnを得るステップと、
vnが消失であるか否かを判定するステップと、
消失であれば、
Tj(x)=Tj-1(x)(1-αnx)+vnΓj-1(x)
Γj(x)=Γj-1(x)(1-αnx)
を計算し、消失でなければ、
【数８】
2005525040.tif 000044
を計算するステップとにより、その場で計算されることを特徴とする請求項１から５のいずれか１項に記載の方法。
【請求項９】
リードソロモン符号の軟判定復号のためのプログラム手段を含み、前記プログラム手段は、シンドローム多項式、消失多項式及び修正シンドローム多項式を、新しいデータシンボルが到着したときに、各シンボルクロックで、前記多項式のそれぞれの係数を、繰り返し更新することにより、並行して計算することに適用され、
符号語の最後のシンボルでの係数の更新が実行された後、符号語のための多項式を直接得る、デジタル記憶媒体のような、コンピュータプログラム製品。
【請求項１０】
シンドローム多項式、消失多項式及び修正シンドローム多項式を、新しいデータシンボルが到着したときに、各シンボルクロックで、前記多項式のそれぞれの係数を、繰り返し更新することにより、並行して計算する手段を含み、符号語の最後のシンボルでの係数の更新が実行された後、符号語のための多項式を直接得るリードソロモン符号語の復号器。
【国際調査報告】
2005525040.tif 000045
2005525040.tif 000046
2005525040.tif 000047