(57)【要約】【課題】簡易な回路構成で誤り値を算出する。【解決手段】本発明のリード・ソロモン復号回路は、シンドローム生成回路と、誤り位置多項式生成回路と、誤り値算出回路とを備えている。誤り値算出回路では、誤り位置多項式の係数の順番が逆転した多項式Ｐ（ｘ）を算出し（ステップＳ１１）、多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ），（ｉ＝０，１，…，ｋ−１）で乗算したときの商として得られる多項式Ｐｉ（ｘ）の係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を求め（ステップＳ１２）、係数μｉｊを順次シンドロームｓに乗じて累加算し、累加算して得られた値をＰｉ（ｘｉ）で除算して、乗算して得られた値を誤り位置ｐ（ｊ｜ｊ＝０，１，…，ｋ−１）における誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）を算出する（ステップＳ１３）。【選択図】図１２
2006033233.tif 000002
【特許請求の範囲】
【請求項１】
ｔ（ｔは１以上の整数。）重誤り訂正が可能なリード・ソロモン符号が付加された情報系列に対して、誤り訂正を行うリード・ソロモン復号方法において、
シンドロームｓｊ（ｊ＝０，１，…，２ｔ−１）を生成し、
上記シンドロームｓｊ（ｊ＝０，１，…，２ｔ−１）に基づき誤り位置多項式を算出し、
算出した誤り位置多項式に基づき、上記情報系列の誤り位置ｐｊ（ｊ＝０，１，…，ｋ−１）を検出し、
上記誤り位置多項式の係数の順番が逆転した下記式（１）の多項式Ｐ（ｘ）を算出し、
上記多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ），（ｉ＝０，１，…，ｋ−１）で乗算したときの商として得られる多項式Ｐｉ（ｘ）の係数μｉｊ（ｉ,ｊ＝０，１，…，ｋ−１）を求め、
上記係数μｉｊ（ｉ,ｊ＝０，１，…，ｋ−１）を順次シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）に乗じて累加算し、累加算して得られた値をＰｉ（ｘｉ）で除算して、乗算して得られた値を誤り位置ｐｊ（ｊ＝０，１，…，ｋ−１）における誤り値ｅi（ｉ＝０，１，…，ｋ−１）とし、
上記誤り値ｅi（ｉ＝０，１，…，ｋ−１）に基づき上記情報系列を訂正すること
を特徴とするリード・ソロモン復号方法。
Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）  ，（ｊ＝０，１，…，ｋ−１）    …（１）
ただし、式（１）においてΠはｊ＝０，１，…，ｋ−１と変化させ、全てを乗算する演算を行う。
【請求項２】
上記多項式Ｐ（ｘ）のｘｊの項に対する係数は、誤り位置多項式のｘ（ｋ−ｊ）の項に対する係数λｊであること
を特徴とする請求項１記載のリード・ソロモン復号方法。
【請求項３】
上記多項式Ｐ（ｘ）の係数λｊ（ｊ＝０，１，…，ｋ−１）を最高次から順に上位に記憶されるｔ＋１個の係数レジスタを用い、
上記ｔ＋１個の係数レジスタに対して上記誤り位置ｐｊ（ｊ＝０，１，…，ｋ−１）に対する定数α＾ｐｊを順次入力していくことで値を更新し、
値が更新されたｔ＋１個の係数レジスタから上記誤り値を取得すること
を特徴とする請求項２記載のリード・ソロモン復号方法。
【請求項４】
上記ｔ＋１個の係数レジスタは、
最上位のレジスタの値を１に固定し、
各レジスタの値を下位に一つシフトして、各レジスタの値と、順次入力されてくる誤り位置ｐｊに対する定数α＾ｐｊ（ｊ＝０，１，…，ｋ−１）との積を演算し、その演算結果をもとのレジスタに加算することで更新が行われること
を特徴とする請求項３記載のリード・ソロモン復号方法。
【請求項５】
さらに、ｔ＋１個の補助レジスタλｊ´（ｊ＝０，１，…，ｔ）を用い、
上記係数レジスタλに格納された係数λｊを上記補助レジスタλｊ´（ｊ＝０，１，…，ｔ）にコピーし、
続いて、任意のｊ番目の係数μｉｊまでが求まっているときに、複製レジスタのｊ番目の値と定数α＾ｐｉとを乗算し、その乗算結果と複製レジスタのｊ＋１番目の値とを加算して、その加算値を複製レジスタのｊ＋１番目のレジスタに格納し、次に、そのｊ＋１番目のレジスタの値をｊ＋１番目の係数μｉｊ＋１として出力する処理を、ｊ＝０からｊ＝ｋまで行い、
以上の処理を、ｉ＝０からｉ＝ｋ−１まで繰り返すことにより、上記多項式Ｐｉ（ｘ）の係数μｉｊを求めること
を特徴とする請求項４記載のリード・ソロモン復号方法。
【請求項６】
任意のｉのときに、上記多項式Ｐｉ（ｘ）の係数μｉｊ（ｊ＝０，１，…，ｋ−１）と、シンドロームｓｊ（ｊ＝０，１，…，ｋ−１）とが順次入力され、ｊ＝０からｊ＝ｋ−１まで以下の式（２）、式（３）の演算を繰り返し行い、ｊ＝ｋ−１のときに得られたｅｎｉ、ｅｄｉから下記式（４）の演算を行い、任意のｉ番目の誤り値ｅｉを算出し、
以上の処理をｉ＝０からｉ＝ｋ−１まで行い、全ての誤り値ｅi（ｉ＝０，１，…，ｋ−１）を算出すること
を特徴とする請求項５記載のリード・ソロモン復号方法。
ｅｎｉ＝ｅｎ＋μｉｊ・ｓ（ｊ）  …（２）
ｅｄｉ＝μｉｊ＋ｅｄ・α＾ｐｉ   …（３）
ｅｉ＝ｅｎｉ／ｅｄｉ      （ｉ＝０,１,…,ｋ−１）  …（４）
【請求項７】
ｔ（ｔは１以上の整数。）重誤り訂正が可能なリード・ソロモン符号が付加された情報系列に対して、誤り訂正を行うリード・ソロモン復号装置において、
シンドロームｓｊ（ｊ＝０，１，…，２ｔ−１）を生成するシンドローム生成手段と、
上記シンドロームｓｊ（ｊ＝０，１，…，２ｔ−１）に基づき誤り位置多項式を算出する誤り位置多項式生成手段と、
誤り値ｅi（ｉ＝０，１，…，ｋ−１）を算出する誤り値算出手段と、
上記誤り値ｅi（ｉ＝０，１，…，ｋ−１）に基づき上記情報系列の誤り訂正を行う誤り訂正手段とを備え、
上記誤り値算出手段は、
算出した誤り位置多項式に基づき、上記情報系列の誤り位置ｐｊ（ｊ＝０，１，…，ｋ−１）を検出し、
上記誤り位置多項式の係数の順番が逆転した下記式（６）の多項式Ｐ（ｘ）を算出し、
上記多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ），（ｉ＝０，１，…，ｋ−１）で乗算したときの商として得られる多項式Ｐｉ（ｘ）の係数μｉｊ（ｉ,ｊ＝０，１，…，ｋ−１）を求め、
上記係数μｉｊ（ｉ,ｊ＝０，１，…，ｋ−１）を順次シンドロームｓｊ（ｊ＝０，１，…，２ｔ−１）に乗じて累加算し、累加算して得られた値をＰｉ（ｘｉ）で除算して、乗算して得られた値を誤り位置ｐｊ（ｊ＝０，１，…，ｋ−１）における誤り値ｅi（ｉ＝０，１，…，ｋ−１）とし、
上記誤り値ｅi（ｉ＝０，１，…，ｋ−１）に基づき上記情報系列を訂正すること
を特徴とするリード・ソロモン復号装置。
Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）  ，（ｊ＝０，１，…，ｋ−１）    …（６）
ただし、式（６）においてΠはｊ＝０，１，…，ｋ−１と変化させ、全てを乗算する演算を行う。
【請求項８】
上記多項式Ｐ（ｘ）のｘｊの項に対する係数は、誤り位置多項式のｘ（ｋ−ｊ）の項に対する係数λｊであること
を特徴とする請求項７記載のリード・ソロモン復号装置。
【請求項９】
上記誤り値算出手段は、
上記多項式Ｐ（ｘ）の係数λｊ（ｊ＝０，１，…，ｋ−１）を最高次から順に上位に記憶されるｔ＋１個の係数レジスタを有し、
上記ｔ＋１個の係数レジスタに対して上記誤り位置ｐｊ（ｊ＝０，１，…，ｋ−１）に対する定数α＾ｐｊを順次入力していくことで値を更新し、
値が更新されたｔ＋１個の係数レジスタから上記誤り値を取得すること
を特徴とする請求項８記載のリード・ソロモン復号装置。
【請求項１０】
上記ｔ＋１個の係数レジスタは、
最上位のレジスタの値を１に固定し、
各レジスタの値を下位に一つシフトして、各レジスタの値と、順次入力されてくる誤り位置ｐｊに対する定数α＾ｐｊ（ｊ＝０，１，…，ｋ−１）との積を演算し、その演算結果をもとのレジスタに加算することで更新が行われること
を特徴とする請求項９記載のリード・ソロモン復号装置。
【請求項１１】
上記誤り値算出手段は、
さらに、ｔ＋１個の補助レジスタλｊ´（ｊ＝０，１，…，ｔ）を有し、
上記係数レジスタλに格納された係数λｊを上記補助レジスタλｊ´（ｊ＝０，１，…，ｔ）にコピーし、
続いて、任意のｊ番目の係数μｉｊまでが求まっているときに、複製レジスタのｊ番目の値と定数α＾ｐｉとを乗算し、その乗算結果と複製レジスタのｊ＋１番目の値とを加算して、その加算値を複製レジスタのｊ＋１番目のレジスタに格納し、次に、そのｊ＋１番目のレジスタの値をｊ＋１番目の係数μｉｊ＋１として出力する処理を、ｊ＝０からｊ＝ｋまで行い、
以上の処理を、ｉ＝０からｉ＝ｋ−１まで繰り返すことにより、上記多項式Ｐｉ（ｘ）の係数μｉｊを求めること
を特徴とする請求項１０記載のリード・ソロモン復号装置。
【請求項１２】
上記誤り値算出手段は、
任意のｉのときに、上記多項式Ｐｉ（ｘ）の係数μｉｊ（ｊ＝０，１，…，ｋ−１）と、シンドロームｓｊ（ｊ＝０，１，…，ｋ−１）とが順次入力され、ｊ＝０からｊ＝ｋ−１まで以下の式（７）、式（８）の演算を繰り返し行い、ｊ＝ｋ−１のときに得られたｅｎｉ、ｅｄｉから下記式（９）の演算を行い、任意のｉ番目の誤り値ｅｉを算出し、
以上の処理をｉ＝０からｉ＝ｋ−１まで行い、全ての誤り値ｅi（ｉ＝０，１，…，ｋ−１）を算出すること
を特徴とする請求項１１記載のリード・ソロモン復号装置。
ｅｎｉ＝ｅｎ＋μｉｊ・ｓ（ｊ）  …（７）
ｅｄｉ＝μｉｊ＋ｅｄ・α＾ｐｉ   …（８）
ｅｉ＝ｅｎｉ／ｅｄｉ      （ｉ＝０,１,…,ｋ−１）  …（９）
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ｔ重誤り訂正が可能なリード・ソロモン符号が付加された情報系列に対して、誤り訂正を行うリード・ソロモン復号方法及び装置に関するものである。
【背景技術】
【０００２】
（リード・ソロモン符号について）
ＣＤやＤＶＤなど記録媒体に記録する情報の符号化方法として、リード・ソロモン符号がよく知られている。リード・ソロモン符号は、ガロア体上の原始多項式とその根の性質を使って構成される符号として知られる。このリード・ソロモン符号は、たとえば８ビット＝１バイトを単位として情報を表現して、また、その符号の構成も、上述の８ビット＝１バイトを単位とした情報系列に対して、誤り訂正符号も８ビット＝１バイトを単位として生成されるようになっている。
【０００３】
このように、情報と誤り訂正符号が８ビット＝１バイト単位で表されるリード・ソロモン符号では、符号を通信して再生し、これを復号する誤り訂正を行う際にも８ビット＝１バイト単位で処理がなされる。そのため、情報の誤りはバイト単位で認識され、ＣＤやＤＶＤなどのように媒体の特性や変復調の条件からバイト単位の中で複数の誤りが生じる通信系での誤り訂正に適しているとされている。また、ほかの誤り訂正符号よりも長い系列で同時に誤り訂正を行うため誤り訂正能力が高く、以上のような理由からＣＤやＤＶＤなどの符号化方式として広く採用されている。
【０００４】
ここでは簡単のため、ガロア体ＧＦ（２５６）の元を情報として用いるリード・ソロモン符号化を説明する。ガロア体ＧＦ（２５６）の元は、たとえば、原始多項式ｘ８＋ｘ４＋ｘ３＋ｘ２＋１の根をαとして、０，α０，α１，…，α２５４の２５６個の元で構成されている。このように根のべき乗で元を表現することはべき乗表示とよばれる。
【０００５】
一方、８ビット＝１バイトのビット列は、２５６個の元である。そこで、上記のガロア体上の元と８ビット＝１バイトのビット列が、一対一で対応する。たとえば、０＝００Ｈ（零元）、α０＝０１Ｈを（単位元）として、原始多項式が０となる条件で加算（排他論理和）と乗算（ビットシフト）の演算を定義すると、上記ガロア体上の２５６元に対応するビット表現を順次求めていくことができる。ガロア体ＧＦ（２５６）の元を情報として用いる場合は、ビット表示とともに、各ビット表示に対応して、このように原始多項式の根αをもちいたべき乗表現もよく用いられる。
【０００６】
次に、送信者が作成するリード・ソロモン符号を考える。
【０００７】
送信者の作成する情報がｋバイト（ｋは、自然数）であるとして、その情報を順に（ｉ０，ｉ１，…，ｉｋ−１）とする。一方、送信者の作成する情報は、次のような多項式を用いて表現することもできる。
ｉ（ｘ）＝Σｉｊ・ｘ（ｎ−ｊ）
ここで、Σは、Σ以降の部分のｊを０からｋ−１まで１ずつ変化させて加算することを表している。このとき、多項式の（ｎ−ｋ）次の係数は、ｋ番目の情報ｉｋをあらわしている。
【０００８】
ガロア体ＧＦ（２５６）の原始多項式ｘ８＋ｘ４＋ｘ３＋ｘ２＋１＝０の根をαとすると、
ｔ重誤り可能なリード・ソロモン符号の生成多項式は、
ｇ（ｘ）＝（ｘ―α０）（ｘ−α１）・・・・（ｘ−α２ｔ−１）
で与えられる。
【０００９】
リード・ソロモン符号による符号化では、誤り訂正符号は、情報多項式を生成多項式で除算（ｍｏｄ）した際の剰余として与えられる。すなわち、
ｒ（ｘ）＝ｉ（ｘ）ｍｏｄ  ｇ（ｘ）
である。ここで、誤り訂正符号は、上記剰余多項式の各係数を順に並べた情報である。情報多項式を生成多項式で除算した剰余の次数は、生成多項式の次数２ｔよりも小さいので、最大２ｔ−１次である。したがって、その誤り訂正符号を表す係数は全部で２ｔ個存在して、それを順に並べると（ｒ０，ｒ１，…，ｒ２ｔ−１）のようになる。
【００１０】
送信者は、情報ｉ（ｊ｜ｊ＝０，１，…，ｋ−１）とリード・ソロモン符号化で得られた誤り訂正情報ｒ（ｊ｜ｊ＝０，１，…，２ｔ−１）を順に並べて送信する。すなわち、送信者が送信する情報ｔ（ｊ｜ｊ＝０，１，…，ｋ＋２ｔ−１）は、（ｉ０，ｉ１，…，ｉｋ−１，ｒ０，ｒ１，…，ｒ２ｔ−１）となる。
【００１１】
また、送信者が送信する情報ｔ（ｊ｜ｊ＝０，１，…，ｎ−１、ただしｎはｋ＋２ｔ）を、各情報を係数とする情報多項式ｔ（ｘ）とすると、
ｔ（ｘ）＝Σｔ（ｊ）ｘ（ｎ−１−ｊ）
となる。ただし、Σはｊを０からｎ−１まで変化させた場合の和をあらわしている。
【００１２】
このとき、情報多項式は
ｔ（ｘ）＝ｉ（ｘ）・ｘ（２ｔ）−ｒ（ｘ）
と表すことができて、生成多項式ｇ（ｘ）で割り切ることができる。
【００１３】
以上のようにして、送信者は、得られたリード・ソロモン符号ｔ（ｉ｜ｉ＝０，１，…，ｎ−１）を送信するが、一方、受信者は、このようにして得られた符号に誤りが生じた送信系列ｒ（ｉ｜ｉ＝０，１，…，ｎ−１）を受信する。ここで、誤り系列をｅ（ｉ｜ｉ＝０，１，…，ｎ−１）とすると、
ｒ（ｉ）＝ｔ（ｉ）＋ｅ（ｉ）、（ｉ＝０，１，…，ｎ−１）
が成り立っている。
【００１４】
（受信系列の誤り訂正について）
受信者は、送信系列に誤り系列が重畳された受信系列を受信するため、リード・ソロモン符号又はＢＣＨ符号が付加された受信系列に対する誤り訂正を行う必要がある。
【００１５】
まず、前述のように送信系列を多項式で表した場合、この送信系列は、ｇ（ｘ）＝（ｘ―α０）（ｘ−α１）・・・・（ｘ−α２ｔ−１）で割り切ることができる。
【００１６】
したがって、送信系列は、２ｔ個の項（ｘ−αｉ）、（ただし、ｉ＝０，１，…，２ｔ−１）のいずれでも割り切れる、すなわち、剰余を０とすることができる。
【００１７】
一方、受信系列は、送信系列に誤り系列が重畳されている系列であるから、
２ｔ個の項（ｘ−αｉ）、（ただし、ｉ＝０，１，…，２ｔ−１）で割り切れない、すなわち、剰余が０になるとは限らない。
【００１８】
そこで、受信系列を２ｔ個の項（ｘ−αｉ）、（ただし、ｉ＝０，１，…，２ｔ−１）で割った際の剰余ｓ（ｉ｜ｉ＝０，１，…，２ｔ−１）を考える。
【００１９】
ここで、誤りがないときこの剰余は全て０になることと、受信系列が送信系列と誤り系列の線形結合であること、さらに、剰余の演算が線形であることから、剰余ｓ（ｉ｜ｉ＝０，１，…，２ｔ−１）は、もとの送信系列に依存せず一意に決まる。すなわち、受信系列に対する２ｔ個の各項（ｘ−αｉ）による剰余の値は、誤り系列のみに対する２ｔ個の各項（ｘ−αｉ）による剰余の値に等しいことを意味している。このようにして得られる剰余のことを一般にシンドロームと呼ぶ。
【００２０】
ここで、今度は、誤り系列ｅ（ｉ｜ｉ＝０，１，…，ｎ−１）とシンドロームｓ（ｉ｜ｉ＝０，１，…，２ｔ−１）の関係を書き下すと、
Σｅ（ｎ−ｊ−１）α（ｉ・ｊ）＝ｓ（ｉ）、（ｉ＝０，１，…，２ｔ−１）
なる２ｔ個の関係式を得ることができる。ただし、ここで、Σは、ｊ＝０，１，…，ｎ−１と変化させたときの和をあらわすものとする。
【００２１】
誤り訂正を実現するためには、誤り系列ｅ（ｉ｜ｉ＝０，１，…，ｎ−１）を求めればよい。
【００２２】
したがって上述の方程式をｎ個の未知数ｅ（ｉ｜ｉ＝０，１，…，ｎ−１）に対する連立方程式とみなして、これを解くことで誤り系列ｅ（ｉ｜ｉ＝０，１，…，ｎ−１）を求めることができる。
【００２３】
しかしながら、この方程式は、ｎ個の未知数に対して２ｔ個の方程式しか存在しない連立方程式であるから、自明な解が存在していない。したがって、これだけの条件では、ｅ（ｉ｜ｉ＝０，１，…，ｎ−１）を直接といて求めることは不可能である。
【００２４】
しかしながら、幸いにも、誤り訂正では、誤りの個数に対する限界を条件として仮定している。
【００２５】
すなわち、ｔ重誤り訂正可能の標記のとおり、誤りの個数はｔ個以下であるということが仮定できる。これは、誤り系列ｅ（ｉ｜ｉ＝０，１，…，ｎ−１）のうち、少なくともｔ個は０であるということを意味している。
【００２６】
このように、求めたい未知数ｅ（ｉ｜ｉ＝０，１，…，ｎ−１）のうち、０でない要素がｔ個以下＝ｋ個である場合に用いられる方法として、誤り位置多項式を用いる方法が知られている。
【００２７】
誤り位置多項式とは、誤りの個数をｋ個と仮定した場合にｋ次の多項式で表される多項式で、もしｋ個の誤りが実際に生じているのであれば、その誤り位置を誤り位置多項式の解から求めることができるという多項式である。
【００２８】
たとえば、後ろからｋ個の誤りの位置がうしろからｐｊ（ｊ＝０，１，…，ｋ−１）番目の位置にあるとする。
【００２９】
このとき、誤り位置多項式を
Λ（ｘ）＝Π（（α＾ｐｊ）・（ｘ−１））
で定義する。ただし、ここで、Πはｊを０からｋ−１まで１ずつ変化させて積をとることを示している。
【００３０】
この多項式では、もし多項式の係数が求められれば、その根として得られるα＾（−ｐｊ）から、誤り位置ｐｊ（ｊ＝０，１，…，ｋ−１）を求めることができる。
【００３１】
そこで、誤り位置を求めるためには、誤り位置多項式の係数を求めればよいことがわかる。
【００３２】
この誤り位置多項式の係数を求める方法としてピーターソン法、ＢＭ（バーレカンプ・マッシー）法、ユークリッド法などが知られている。
【００３３】
ピーターソンの方法は、ｋ重誤り位置多項式の係数λｋ（ｉ｜ｉ＝０，１，…，ｋ−１）に対するｋ個の連立方程式
Σｓ（ｋ＋ｉ−ｊ）λｋ（ｊ）＝ｓ（ｋ＋ｉ）  （ｉ＝０，１，…，ｋ−１）
が成立することを利用することである。
【００３４】
以上のようにして誤り位置多項式の係数を求めた後、この誤り位置多項式の解を求める。誤り位置多項式の解を求める方法は、チェン探索法とよばれる方法が一般的である。
【００３５】
誤り位置がわかったあとは、リード・ソロモン符号であれば、誤り値に対する方程式は正則化される。したがって、自明な解が存在するのでその方程式をとけばよい。これは、ｋ個の未知数に対するｋ個の連立方程式であるから一般的な連立方程式の解法を用いて容易に解くことができる。
【００３６】
以上のようにして誤り系列が得られるので、受信者は受信系列から誤り系列を減算することで元の送信系列をえることができる。
【００３７】
【非特許文献１】Ｗｉｌｌｉａｍ  Ｈ．Ｐｒｅｓｓ／（他）著  丹慶勝市／（他）訳  「ニューメリカルレシピ・イン・シー  Ｃ言語による数値計算のレシピ  日本語版  」（技術評論社）
【発明の開示】
【発明が解決しようとする課題】
【００３８】
ところで、上述のように、誤り位置がわかったあとの、誤り値に対する連立方程式は正則化されている。
【００３９】
具体的には、誤り位置が後ろから数えてｐ（ｊ｜ｊ＝０，１，…，ｋ−１）であると検出された際、
Σα＾（ｉ・ｐｊ）・ｅｊ＝ｓ（ｉ）  （ｉ＝０，１，…，ｋ−１）
なる連立方程式を解けばよいことがわかる。ただし、Σはｊが０からｋ−１まで変化するとき和をとるものとする。
【００４０】
ここで、ｋは誤りの個数に等しいので、一般的にはそれほど大きくない。
【００４１】
しかしながら、ｋ≦ｔであることからわかるように、誤り訂正の能力を強くしてｔを大きくすることで、この値は大きくなり、したがって、連立方程式の計算も複雑になる。
【００４２】
このように、従来の誤り値の算出方法では、誤りの個数に比例した個数の変数を連立する連立方程式を解かなければならないため、その処理に時間がかかるという問題があった。
【００４３】
このような再生処理は一般にＬＳＩなどの集積回路に組み込まれて処理がなされるが、処理が複雑となると回路も複雑になりＩＣの開発に高いコストを要することになる。それだけではなく、再生処理そのものの時間がかかることになり、昨今の情報の大容量化、情報伝達の高速化の状況を鑑みると、改善が期待される課題である。
【課題を解決するための手段】
【００４４】
本発明は、ｔ（ｔは１以上の整数。）重誤り訂正が可能なリード・ソロモン符号が付加された情報系列に対して、ｋ重誤り位置多項式を用いて誤り位置を検出するものである。
【００４５】
ここで、「ｔ重誤り訂正可能」とは、情報系列内に含まれている全ての符号のうち、誤っている符号の数がｔ個以下であれば、誤り訂正が可能であるという意味である。
【００４６】
また、「誤り位置の検出」とは、情報系列内に含まれている全ての符号のうち、誤りが生じている符号の位置を検出することである。
【００４７】
また、「ｋ重誤り位置多項式」とは、ｋ個（ｋは、０以上ｔ以下の整数。）の誤りがあった場合に、誤り位置を検出するための多項式である。
【００４８】
なお、本明細書では、関数ｘ（ｙ）の変数ｙの値が、ｙ＝０，１，２，…，ｎといったように複数の整数値となる場合、この関数をｘ（ｙ｜ｙ＝０，１，２，…，ｎ）と表記する。また、これを略してｘｙと表記する場合もある。
【００４９】
本発明が適用されたリード・ソロモン符号の誤り値生成のためのアルゴリズムについて説明をする。
【００５０】
本発明のリード・ソロモン符号の誤り値生成のためのアルゴリズムは、ファンデルモンデ行列を用いた連立方程式の解法を利用したものである（文献：Ｗｉｌｌｉａｍ  Ｈ．Ｐｒｅｓｓ／（他）著  丹慶勝市／（他）訳  「ニューメリカルレシピ・イン・シー  Ｃ言語による数値計算のレシピ  日本語版  」（技術評論社）参照。）。
【００５１】
まず、一般にファンデルモンデ行列は、ｋ個の定数ｃ（ｉ｜ｉ＝０，１，…，ｋ−１）を用いて、ｉｊ成分が、ｃｉ＾ｊ（ｊ｜ｊ＝０，１，…，ｋ−１）となる行列である。
【００５２】
一方、誤り値ｅ（ｊ｜ｊ＝０，１，…，ｋ−１）に対する連立方程式は、
Σα＾（ｉ・ｐｊ）・ｅｊ＝ｓ（ｉ）  （ｉ＝０，１，…，ｋ−１）
である。これは、ｋ個の定数α＾ｐｊ（ｊ＝０，１，…，ｋ−１）を用いて、ｉｊ成分がα＾（ｉ・ｐｊ）となる行列を用いた連立方程式である。すなわち、この連立方程式は、ファンデルモンデ行列の転置行列である。
【００５３】
ここで、このようなファンデルモンデ行列の転置行列には、高速な解法が存在している。
【００５４】
ファンデルモンデ行列を用いた連立方程式の高速解法では、まず、下記式（１００）に示す多項式Ｐ（ｘ）が用意される。
Ｐ（ｘ）＝Π（ｘ−ｃｎ）    …（１００）
ただし、式（１００）において、Πは、ｎを０からｋ−１まで変化させ、全て乗算する演算を表している。
【００５５】
リード・ソロモン符号の誤り値の算出には、式（１００）の多項式Ｐ（ｘ）の係数ｃｎとして、α＾ｐｎが用いられる。
【００５６】
Ｐ（ｘ）を項（ｘ−α＾ｐｊ）で割った商を、下式（１０１）に示すように多項式Ｐｊ（ｘ）とする。
Ｐｊ（ｘ）＝Π（（ｘ−α＾ｐｎ）／（α＾ｐｊ−α＾ｐｎ））  …（１０１）
ただし、式（１０１）において、Πは、ｎをｊ以外で０からｋ−１まで変化させ、全て乗算する演算を表している。
【００５７】
Ｐｊ（ｘ）にｘ＝α＾ｐｉを代入すると、Ｐｊ（α＾ｐｉ）＝δｉｊであることがわかる。
【００５８】
一方、多項式Ｐｉ（ｘ）のｘ＾ｊの係数をμｉｊ（ｊ｜ｊ＝０，１，…，ｋ−１）とおくと、
Ｐｉ（ｘ）＝Σμｉｊ・ｘ＾ｊ
である。ただし、Σはｊを０からｋ−１まで変化させたときの総和を表している。
このとき、
Ｐｉ（α＾ｐｊ）＝δｉｊ＝Σμｉｋ・α＾（ｋ・ｐｊ）
であるから、μｉｊは、行列α＾（ｉ・ｐｊ）の逆行列であることがわかる。
【００５９】
ここで、行列α＾（ｉ・ｐｊ）は、誤り値ｅ（ｊ｜ｊ＝０，１，…，ｋ−１）の連立方程式の係数行列であるから、誤り値ｅ（ｊ｜ｊ＝０，１，…，ｋ−１）は、その逆行列μｉｊをシンドロームｓ（ｊ｜ｊ＝０，１，…，ｋ−１）に乗ずることで得られる。
【００６０】
以上のように、リード・ソロモン符号の誤り値の算出に、ファンデルモンデ行列を用いた連立方程式に対する高速解法を用いることができる。そのため、複雑な連立方程式を解くことなく、多項式の除算という容易な演算によってリード・ソロモン符号の誤り値の算出を行うことができる。
【００６１】
さらに、ここで、ｋ重誤りで、誤り位置が後ろから数えてｐ（ｊ｜ｊ＝０，１，…，ｋ−１）の位置にある誤り位置多項式の定義に着目すると、
誤り位置多項式：Ｓ（ｘ）＝Π（１−α＾ｐｎ・ｘ）
である。ただし、Πは、ｎを０からｋ−１まで変化させ、全て乗算する演算を表している。
ここで、
Ｓ（ｘ−１）・ｘｋ    ＝Π（１−α＾ｐｎ・ｘ−１）・ｘｋ
＝Π（ｘ−α＾ｐｎ）
である。この式は、多項式Ｐ（ｘ）にほかならない。
【００６２】
したがって、誤り位置多項式Ｓ（ｘ）がわかったときに、
多項式：Ｐ（ｘ）＝Ｓ（ｘ−１）・ｘｋを用いることで、ファンデルモンデの行列を用いた連立方程式の形にすることができることがわかる。
【００６３】
また、Ｐ（ｘ）＝Ｓ（ｘ−１）・ｘｋについて詳しく見ると、この多項式は、誤り位置多項式Ｓ（ｘ）の係数の順序が反転している多項式であることがわかる。
【００６４】
以上のことを利用し、本発明では、誤り位置多項式の係数の順序が反転した多項式Ｐ（ｘ）を用いて、リード・ソロモン符号の復号の際の誤り値を求めている。
【００６５】
以上のようなアルゴリズムを用いた本発明に係る誤り位置検出方法及び装置は、次の通りである。
【００６６】
本発明に係るリード・ソロモン復号方法は、ｔ（ｔは１以上の整数。）重誤り訂正が可能なリード・ソロモン符号が付加された情報系列に対して、誤り訂正を行うリード・ソロモン復号方法において、シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）を生成し、上記シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）に基づき誤り位置多項式を算出し、
算出した誤り位置多項式に基づき、上記情報系列の誤り位置ｐ（ｊ｜ｊ＝０，１，…，ｋ−１）を検出し、
上記誤り位置多項式の係数の順番が逆転した下記式（１）の多項式Ｐ（ｘ）を算出し、
上記多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ），（ｉ＝０，１，…，ｋ−１）で乗算したときの商として得られる多項式Ｐｉ（ｘ）の係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を求め、
上記係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を順次シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）に乗じて累加算し、累加算して得られた値をＰｉ（ｘｉ）で除算して、乗算して得られた値を誤り位置ｐ（ｊ｜ｊ＝０，１，…，ｋ−１）における誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）とし、
上記誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）に基づき上記情報系列を訂正すること
を特徴とする。
Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）  ，（ｊ＝０，１，…，ｋ−１）    …（１）
ただし、式（１）においてΠはｊ＝０，１，…，ｋ−１と変化させ、全てを乗算する演算を行う。
【００６７】
本発明に係るリード・ソロモン復号装置は、ｔ（ｔは１以上の整数。）重誤り訂正が可能なリード・ソロモン符号が付加された情報系列に対して、誤り訂正を行うリード・ソロモン復号装置において、シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）を生成するシンドローム生成手段と、上記シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）に基づき誤り位置多項式を算出する誤り位置多項式生成手段と、誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）を算出する誤り値算出手段と、上記誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）に基づき上記情報系列の誤り訂正を行う誤り訂正手段とを備え、上記誤り値算出手段は、算出した誤り位置多項式に基づき、上記情報系列の誤り位置ｐ（ｊ｜ｊ＝０，１，…，ｋ−１）を検出し、上記誤り位置多項式の係数の順番が逆転した下記式（６）の多項式Ｐ（ｘ）を算出し、上記多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ），（ｉ＝０，１，…，ｋ−１）で乗算したときの商として得られる多項式Ｐｉ（ｘ）の係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を求め、上記係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を順次シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）に乗じて累加算し、累加算して得られた値をＰｉ（ｘｉ）で除算して、乗算して得られた値を誤り位置ｐ（ｊ｜ｊ＝０，１，…，ｋ−１）における誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）とし、上記誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）に基づき上記情報系列を訂正することを特徴とする。
【発明の効果】
【００６８】
本発明に係るリード・ソロモン復号方法及び装置では、誤り位置多項式の係数の順番が逆転した多項式Ｐ（ｘ）を算出し、当該多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ）で乗算したときの商として得られる多項式Ｐｉ（ｘ）の係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を求め、当該係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を順次シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）に乗じて累加算し、累加算して得られた値をＰｉ（ｘｉ）で除算することによって誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）を生成している。
【００６９】
このことにより、本発明に係るリード・ソロモン復号方法及び装置では、非常に簡単に誤り値の算出を行うことができる。
【発明を実施するための最良の形態】
【００７０】
以下、発明が適用された実施形態について説明する。
【００７１】
全体構成
本発明は、図１に示すような、リード・ソロモン符号を付加した情報を記録媒体に記録する記録システム、又は、リード・ソロモン符号を付加した情報を伝送媒体を介して伝送する伝送システムに適用することができる。
【００７２】
図１は、リード・ソロモン符号を利用した記録又は伝送システムを示している。
【００７３】
リード・ソロモン符号を利用した記録又は伝送システム１は、入力系列をリード・ソロモン符号化し、入力系列にリードソロモン符号を付加した系列である送信系列（ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）を出力するリード・ソロモン符号化回路１-１と、送信系列（ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）を変調して記録媒体に記録したり伝送媒体に伝送する変調回路１-２と、記録媒体又は伝送媒体から信号を再生及び復調して受信系列（ｒ（ｉ｜ｉ＝０,１,…,ｎ−１）を出力する復調回路１-３と、受信系列（ｒ（ｉ｜ｉ＝０,１,…,ｎ−１）に対して誤り訂正（リード・ソロモン符号の復号）をして元の送信系列（ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）を復元して出力するリード・ソロモン復号回路１-４とから構成される。
【００７４】
リード・ソロモン符号化回路１-１は、入力系列を表す情報多項式を生成多項式で除算することで誤り訂正符号を生成して、もとの入力系列とあわせてリード・ソロモン符号化された送信系列を生成している。
【００７５】
変調回路１-２は、記録媒体に記録する場合であれば、固有な符号間干渉ノイズなどに対応して、１７変調やＥＦＭ変調などの変調を施し、記録媒体に記録する。また、変調回路１-２は、伝送媒体に伝送する場合であれば、例えば、ＢＦＰ、ＱＦＰなどの通信で基本的な変調方式で情報に変調を施し、伝送媒体に伝送する。
【００７６】
復調回路１-３は、記録媒体から再生をする場合であれば、１７変調やＥＦＭ変調の復調をし、受信系列、すなわち、誤りを含んだ送信系列を生成する。また、復調回路１-３は、伝送媒体から再生をする場合であれば、ＢＦＰ、ＱＦＰなどの通信で基本的な変調方式の復調を行い、受信系列、すなわち、誤りを含んだ送信系列を生成する。
【００７７】
リード・ソロモン復号回路１-４は、シンドロームの生成、誤り位置検出多項式の計算、チェン探索、誤り値計算、誤り訂正といった処理を行い、誤りが含まれている受信情報に対して誤り訂正を行い、元の送信系列を出力する。
【００７８】
リード・ソロモン符号化回路
つぎに、リード・ソロモン符号化回路について更に詳細に説明をする。
【００７９】
図２は、ｔ重誤り訂正が可能なリード・ソロモン符号の符号化回路１-１の構成を示す図である。
【００８０】
ｔ重誤り訂正が可能なリード・ソロモン符号の生成多項式は、下記式（２０１）の２ｔ次の多項式で表すことができる。
ｇ（ｘ）＝（ｘ−α０）・（ｘ−α１），…，（ｘ−α２ｔ−１）
＝  Σ（ａｋｘ（２ｔ−ｋ））    …（２０１）
ただし、式（２０１）において、ａｋは、ｘの２ｔ−ｋ次の項の係数である。またΣは、ｋを０から２ｔまで１ずつ変化させて総和演算するものである。
【００８１】
リード・ソロモン符号では、誤り訂正符号として、入力系列を表す情報多項式を生成多項式で除算した剰余多項式の係数が用いられている。そこで、リード・ソロモン符号の符号化回路１-１では、情報多項式を生成多項式で除算して、その剰余多項式の係数を求めるような構成となっている。
【００８２】
リード・ソロモン符号の符号化回路１-１は、具体的には、図２に示すように、入力値に対してそれぞれ係数ｇ＿０，ｇ＿１，…，ｇ＿２ｔ−１を乗算する２ｔ個の乗算器３-０,３-１,…,３-（２ｔ-１）と、１クロック分入力値を遅延させる２ｔ個の遅延器４-０, ４-１,…,４-（２ｔ-１）と、２つの入力値を加算する２ｔ個の加算器５-０, ５-１,…,５-（２ｔ-１）と、第１のスイッチＳＷ１と、第２のスイッチＳＷ２とから構成されている。
【００８３】
リード・ソロモン符号の符号化回路１-１では、遅延器４-０の出力信号と入力系列ｉ（ｉ｜ｉ＝０,１,…,ｋ−１）とを加算器５-０が加算し、加算器５-０の出力値が全乗算器３-０,３-１,…,３-（２ｔ-１）に入力され、乗算器３-０の出力値が遅延器４-１に入力される。さらに、リード・ソロモン符号の符号化回路１-１では、乗算器３-１の出力値と遅延器４-１の出力値を加算器５-１が加算して遅延器４-２に入力し、乗算器３-２の出力値と遅延器４-２の出力値を加算器５-２が加算して遅延器４-３に入力し、…、乗算器３-（２ｔ−１）の出力値と遅延器４-（２ｔ−１）の出力値を加算器５-（２ｔ−１）が加算して遅延器４-０に入力するといった、巡回符号器が構成されている。
【００８４】
第１のスイッチＳＷ１は、送信系列ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）として、入力系列ｉ（ｉ｜ｉ＝０,１,…,ｋ−１）を選択するか、加算器５-０から出力される巡回符号（リード・ソロモン符号）を選択するか切り換える。また、第２のスイッチＳＷ２は、加算器５-０の出力値を各乗算器３-０,３-１,…,３-（２ｔ-１）に入力するか、入力停止するかを切り換える。
【００８５】
リード・ソロモン符号の符号化回路１-１では、最初に全ての遅延器４-０, ４-１,…,４-（２ｔ-１）の内部値が０とされる。入力系列ｉ（ｉ｜ｉ＝０,１,…,ｋ−１）が入力されると、最初は、第１のスイッチＳＷ１が入力系列側に切り換えられ、第２のスイッチＳＷ２が加算器５-０の出力値を各乗算器３-０,３-１,…,３-（２ｔ-１）に供給する。従って、リード・ソロモン符号の符号化回路１-１は、送信系列ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）として、まず、入力系列ｉ（ｉ｜ｉ＝０,１,…,ｋ−１）が出力される。その間、送信系列ｔが１データずつ入力される毎に、巡回符号器内でループが回される。この際、２ｔ−１個の乗算器は、図中左から順に生成多項式におけるｘの２ｔ−１次以下の項の係数に対応しており、入力系列が全て出力され終えた時点で、遅延器４-０, ４-１,…,４-（２ｔ-１）内に、リード・ソロモン符号が格納されている。
【００８６】
リード・ソロモン符号の符号化回路１-１は、入力系列ｉ（ｉ｜ｉ＝０,１,…,ｋ−１）を全て出力し終えると、第１のスイッチＳＷ１が加算器５-０側（巡回符号側）に切り換えられ、第２のスイッチＳＷ２は閉じて、各乗算器３-０,３-１,…,３-（２ｔ-１）に対して０を入力する。従って、リード・ソロモン符号の符号化回路１-１は、送信系列ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）として、入力系列ｉ（ｉ｜ｉ＝０,１,…,ｋ−１）の後に、生成したリード・ソロモン符号を付加して出力する。
【００８７】
リード・ソロモン復号回路
つぎに、リード・ソロモン復号回路の構成について説明をする。
【００８８】
リード・ソロモン復号回路１-４は、送信系列ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）に誤り系列ｅ（ｉ｜ｉ＝０,１,…,ｎ−１）が重畳された受信系列ｒ（ｉ｜ｉ＝０,１,…,ｎ−１）が入力され、受信系列ｒ（ｉ｜ｉ＝０,１,…,ｎ−１）に対して誤り訂正を行って送信系列ｔ（ｉ｜ｉ＝０,１,…,ｋ−１）を復元する回路である。
【００８９】
リード・ソロモン復号回路１-４は、図３に示すように、受信系列ｒ（ｉ｜ｉ＝０,１,…,ｎ−１）からシンドロームｓ（ｉ｜ｉ＝０，１，…，２ｔ−１）を計算するシンドローム計算回路９と、誤り位置多項式を生成する誤り位置多項式生成回路１０と、誤り位置生成多項式に基づき誤り位置を探索するチェン探索回路１１と、誤り系列ｅ（ｉ｜ｉ＝０,１,…,ｎ−１）を算出する誤り値計算回路１２と、受信系列ｒ（ｉ｜ｉ＝０,１,…,ｎ−１）を誤り系列ｅ（ｉ｜ｉ＝０,１,…,ｎ−１）により訂正することにより送信系列ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）を生成する誤り訂正回路１３とを備えている。
【００９０】
以下、リード・ソロモン復号回路１-４を構成するシンドローム計算回路９、誤り位置多項式生成回路１０、チェン探索回路１１、誤り値計算回路１２及び誤り訂正回路１３の各回路について、さらに、詳細に説明する。
【００９１】
（シンドローム計算回路）
図４は、シンドローム計算回路９のブロック図である。
【００９２】
シンドロームとは、前述のように、受信多項式ｒ（ｘ）を２ｔ個の項（ｘ−αｉ）  ,（ｉ＝０，１，…，２ｔ−１）でそれぞれ除算したときの２ｔ個の剰余に相当する。シンドローム計算回路９は、これら２ｔ個のシンドローム（＝剰余）を計算して出力する。
【００９３】
シンドローム計算回路９は、図４に示すように、入力値に対してα０，α１，…，α２ｔ−１を乗算する２ｔ個の乗算器１５-０,１５-１,…,１５-（２ｔ-１）と、２つの入力値を加算する２ｔ個の加算器１６-０,１６-１,…,１６-（２ｔ-１）と、１クロック入力値を遅延させる２ｔ個の遅延器１７-０,１７-１,…,１７-（２ｔ-１）とから構成されている。
【００９４】
シンドローム計算回路９では、受信系列ｒ（０）,ｒ（１）,…,ｒ（ｎ−１）が１クロック毎順次入力される。入力された受信系列ｒ（０）,ｒ（１）,…,ｒ（ｎ−１）は、全ての加算器１６-０,１６-１,…,１６-（２ｔ-１）に並列に入力される。各乗算器１５-０,１５-１,…,１５-（２ｔ-１）は、それぞれ対応する遅延器１７-０,１７-１,…,１７-（２ｔ-１）の出力値に係数（α０，α１，…，α２ｔ−１）を乗算する。各加算器１６-０,１６-１,…,１６-（２ｔ-１）は、受信系列ｒ（０）,ｒ（１）,…,ｒ（ｎ−１）の値と、それぞれ対応する乗算器１５-０,１５-１,…,１５-（２ｔ-１）から入力された値とを加算して、対応する遅延器１７-０,１７-１,…,１７-（２ｔ-１）に格納する。
【００９５】
シンドローム計算回路９では、受信系列ｒ（０）,ｒ（１）,…,ｒ（ｎ−１）の入力が全て終了した後、各遅延器１５-０,１５-１,…,１５-（２ｔ-１）に格納されている値を、シンドロームｓ（ｉ｜ｉ＝０,１,…２ｔ−１）として出力する。
【００９６】
（誤り訂正多項式生成回路）
誤り位置多項式生成回路１０は、シンドローム計算回路９により生成されたシンドロームｓ（ｉ｜ｉ＝０,１,…２ｔ−１）に基づき、誤り位置多項式の係数λ（０）, λ（１）,…, λ（ｋ−１）を生成する。
【００９７】
誤り位置多項式生成回路１０による誤り位置多項式の係数の生成アルゴリズムについて説明する。このアルゴリズムを説明するにあたり、以下、（１）ｋ重誤り位置多項式とシンドロームの関係、（２）誤り位置多項式係数の漸化式、（３）ｋ重誤り過程の検証方法、の説明を順次行う。
【００９８】
---（１）ｋ重誤り位置多項式と、シンドロームの関係---
まず、本発明者は、ｋ重誤り位置多項式のｊ＋１次の係数λｋ（ｊ）とシンドロームｓ（ｊ）が式（２１０）に示すピーターソンの方程式だけでなく、
Σｓ（ｋ−１＋ｉ−ｊ）λｋ（ｊ）＝ｓ（ｋ＋ｉ），（ｉ＝０，１，…，ｋ−１）
…（２１０）
下記の式（２１１）に示す連立方程式にも従うことに着目した。
Σｓ（ｃ−１＋ｉ−ｊ）λｋ（ｊ−１）＝ｓ（ｃ＋ｉ）  （ｉ＝０，１，…，ｋ−１）
…（２１１）
なお、式（２１１）において、ｃはｋ以外の整数であり、Σはｊ＝０，１，…，ｋ−１の総和演算を行う。
【００９９】
この式（２１１）の方程式は、ピーターソンの方程式を導出した過程を、そのまま用いることで導出することができる。
【０１００】
以上のような方程式を用いると、シンドローム部分はｋ重誤りのｋに依存しないため、新しいλｋ（ｊ）に対する係数をそのつど変更する必要がなくなる。
【０１０１】
---（２）誤り位置多項式係数の漸化式---
ｔ重誤り位置多項式のｊ＋１次の係数λｋ（ｊ＝０，１，…，ｔ）が満たす方程式は、下記式（２１３）のとおりである。
Σｓ（ｔ−１＋ｉ−ｊ）λｋ（ｊ）＝ｓ（ｔ＋ｉ），（ｉ＝０，１，…，ｋ−１）
…（２１３）
式（２１３）において、Σはｊ＝０，１，…，ｔ−１までの総和演算を行うものである。
【０１０２】
この式（２１３）の連立方程式は、対角成分と同じ方向に同一の係数がならぶ行列を用いて表現することができる。このように対角成分と同じ方向に同一の係数が並んでいる行列を用いる連立方程式は、テープリッツ型の連立方程式とよばれ、縁取り法（上記の文献「ニューメリカルレシピ・イン・シー」参照。）と呼ばれる方法によって逐次的に解を求める方法が知られている。
【０１０３】
この縁取り法とは、左上部ｋ次正則行列を用いた方程式
Σｓ（ｃ−１＋ｉ−ｊ）λｋ（ｊ）＝ｓ（ｃ＋ｉ）  （ｉ＝０，１，…，ｋ−１）
と、左上部ｋ＋１次正則行列を用いた方程式
Σｓ（ｃ−１＋ｉ−ｊ）λｋ＋１（ｊ）＝ｓ（ｃ＋ｉ）  （ｉ＝０，１，…，ｋ）
と、の間で、それぞれの方程式の解λｋ（ｊ＝０，１，…，ｋ−１）とλｋ＋１（ｊ＝０，１，…，ｋ）の間の漸化式を求めることで、左上部ｋ次正則行列を用いた方程式の解λｋ（ｊ＝０，１，…，ｋ−１）を逐次的に得る方法で、ｋ＝ｔになった時点で最終的な解が求まるという方法である。
【０１０４】
ここで、上記のｋ次、ｋ＋１次の２つの方程式に着目すると、これらの二つの方程式は、それぞれ式（２１１）で示した方法で生成されるｋ重誤り位置多項式、ｋ＋１重誤り位置多項式の新しい表現と同一であることがわかる。
【０１０５】
そこで、たとえば、ｋ１重誤りであった場合は、上記のｋを０からｋ１−１まで順に縁取り法を用いて計算することでその解を求めることができる。
【０１０６】
なお、この縁取り方法は、ピーターソンの方法でも用いることができるが、この場合は、ｋ＝０，１，…，２ｔ−１重誤りの位置多項式でそれぞれ別々の縁取り法を行わなければならず、逐次的な解法による利点がないため、大きな効果は得られない。
【０１０７】
一方、本アルゴリズムのように式（２１１）の方程式をもちいると、縁取り法の漸化式の導出過程と誤り位置多項式の漸化式の導出過程が全く同じ方程式で表現されているために、上記の無駄が生じず、非常に大きな効果を発揮すると考えられる。
【０１０８】
なお、漸化式の導出は、後述する。
【０１０９】
---（３）ｋ重誤りの仮定の検証方法---
以上のようにｋ重誤りを仮定して、ｋ重誤りに対する位置多項式を容易に求めることができても、誤りがｋ＋１個以上ないことが確認できなければ、この位置多項式には意味がない。
【０１１０】
本アルゴリズムでは、ｋ重誤り係数からｋ＋１重誤り位置多項式の係数までの処理は、逐次的に行われているので、ｋが更新されるたびに、その都度、最初から連立方程式を解く必要がない。
【０１１１】
そして、誤りの検証は残りの方程式（ｃ−ｋ）個の連立方程式（下記式（２１４））に対して、仮決定されている解λｋ（ｊ）の検算を行うことで求められる。
Σｓ（ｃ−１＋ｉ−ｊ）λｋ（ｊ）＝ｓ（ｃ＋ｉ），（ｉ＝ｋ，…，ｃ−１）
…（２１４）
式（２１４）において、Σはｊ＝０，１，…，ｋ−１の総和演算を行う。
【０１１２】
もし、この解の検算で、矛盾が生じている場合は、ｃをｔから順次１ずつ小さくしていくことで、計算をやり直すことができる。このような、処理は冗長性を増すものではあるが、実際には、このような矛盾が生じる頻度がそれほど多くないため、全体として、それほど処理時間を多くとるものではない。
【０１１３】
以上から、本アルゴリズムは、従来のピーターソン法で問題であった、連立方程式の困難さと、その都度、最初から連立方程式を解くという冗長さを減らして、従来よりも、高速で小規模な回路で誤り位置多項式の係数の導出を実現することができることがわかる。
【０１１４】
なお、本アルゴリズムにおけるテープリッツ法の漸化式は、上記の文献「ニューメリカルレシピ」を参考にしている。
【０１１５】
このテープリッツ法にもとづいて、上記の誤り位置多項式の係数の漸化式は以下のように求められる。
【０１１６】
まず、初期条件を、下記の式（２１５-１），（２１５-２），（２１５-３）のように設定する。
【０１１７】
λ０（ｊ＝０，１，…，ｔ−１）＝０  …（２１５-１）
ｕ０（ｊ＝０，１，…，ｔ−１）＝０  …（２１５-２）
ｖ０（ｊ＝０，１，…，ｔ−１）＝０  …（２１５-３）
ｕ０（ｊ）、ｖ０（ｊ）は後に補助的に用いられる補助係数ｕｋ（ｊ＝０，１，…，ｔ−１）、ｖｋ（ｊ＝０，１，…，ｔ−１）の初期状態である。なお、“／”は除算を表す。
【０１１８】
次に、ｋ次の係数がλｋ（ｊ＝０，１，…，ｋ−１）で、補助係数はｕｋ（ｊ＝０，１，…，ｋ−１）、ｖｋ（ｊ＝０，１，…，ｋ−１）と求まっている状態で、ｋ＋１次の誤り多項式の係数のうち、ｋ次の係数に対する漸化式を下記式（２１６-１），（２１６-２），（２１６-３）に基づき求める。
λｋ＋１（ｋ）＝（Σｓ（ｃ−１＋ｋ−ｊ＋１）λｋ（ｊ−１）＋ｓ（ｃ−１＋ｋ＋１））
／（Σｓ（ｃ−１＋ｋ−ｊ＋１）ｕｋ（ｊ−１）＋ｓ（ｃ−１））
…（２１６-１）
ｕｋ＋１（ｋ）＝（Σｓ（ｃ−１−ｋ＋ｊ−１）ｕｋ（ｊ−１）＋ｓ（ｃ−１−ｋ−１））
／（Σｓ（ｃ−１−ｋ＋ｊ−１）ｖｋ（ｊ−１）＋ｓ（ｃ−１））
…（２１６-２）
ｖｋ＋１（ｋ）＝（Σｓ（ｃ−１＋ｋ−ｊ＋１）ｖｋ（ｊ−１）＋ｓ（ｃ−１＋ｋ＋１））
／（Σｓ（ｃ−１＋ｋ−ｊ＋１）ｕｋ（ｊ−１）＋ｓ（ｃ−１））
…（２１６-３）
ただし、式（２１６-１），（２１６-２），（２１６-３）において、Σはｊを０からｋ−１まで１ずつ変化させて総和演算をとるものとする。
【０１１９】
次に誤り位置多項式の各次数の係数を、下記式（２１７-１），（２１７-２），（２１７-３）のようにもとめる。
λｋ＋１（ｊ）＝λｋ（ｊ）＋（λｋ＋１（ｋ）・ｕｋ（ｋ−ｊ−１））
…（２１７-１）
ｕｋ＋１（ｊ）＝ｕｋ（ｊ）＋（ｕｋ＋１（ｋ）・ｖｋ（ｋ−ｊ−１））
…（２１７-２）
ｖｋ＋１（ｊ）＝ｖｋ（ｊ）＋（ｖｋ＋１（ｋ）・ｕｋ（ｋ−ｊ−１））
…（２１７-３）
【０１２０】
誤り位置多項式の係数の仮決定は、ｕｋ＋１（ｋ）、ｖｋ＋１（ｋ）のいずれかの分母が０になった場合に、解が求まらないことを利用して、その前のステップで決定していた係数λｋ（ｊ）を係数として仮決定する。
【０１２１】
誤り位置多項式の係数の検算は、λｋ＋１（ｋ）の分子が、丁度、ｃ個の誤り位置多項式にのｋ＋１番目の方程式と一致しているのでこの値が０になっているかどうかが検算の一つに相当する。なお、ｋ番目までの方程式までは、検算をしなくても無矛盾であることが保証されている。ｋ＋２番目以降ｃ番目までの方程式は、かならずしも無矛盾ではないため、これも検算することが必要である。検算は、ｃ−ｋ個の検算用の出力として、下記式（２１８）を用いてｗ（ｉ）を算出し、ｗ（ｉ）が全て０であれば無矛盾、また、一つでも１であれば矛盾であるとすればよい。
ｗ（ｉ）＝Σｓ（ｃ−１＋ｉ−ｊ）λｋ（ｊ）−ｓ（ｃ＋ｉ）
，（ｉ＝ｋ，（ｋ＋１），…，ｃ−１）…（２１８）
なお、式（２１８）において、Σはｊ＝０，１，…，ｋ−１の総和演算を行う。
【０１２２】
検算の結果、得られた解λｋ（ｊ）がもとの方程式に対して無矛盾であった場合は、誤り位置多項式は求まったものとして、次の誤り位置探索に移る。一方、得られた解λｋ（ｊ）に矛盾があった場合は、誤り位置多項式は求まっていないと考えられる。この場合は、ｃを変更して再度上記のステップを繰り返す。
【０１２３】
以上のアルゴリズムを用いれば、誤り位置多項式の係数を、無駄なく、高速に計算することが可能となり、課題を解決することができる。
【０１２４】
つぎに、ｋ重誤り位置多項式を漸化式から誤り生成多項式を求める具体的な回路について説明する。
【０１２５】
誤り位置多項式生成回路１０の回路構成を図５に示す。
【０１２６】
誤り位置多項式生成回路１０は、図５に示すように、シンドローム生成回路９により生成されたシンドロームの系列Ｓ（ｉ｜ｉ＝０，１，…，２ｔ−１）を格納するシンドロームレジスタ群３１と、係数ベクトルλ（ｊ｜ｊ＝０，１，…，ｋ−１）の値を格納する係数レジスタ群３２と、多項式生成のための補助係数である補助係数ベクトルｕ（ｊ｜ｊ＝０，１，…，ｋ−１）の値を格納する第１の補助係数レジスタ群３３と、多項式生成のための補助係数である補助係数ベクトルｖ（ｊ｜ｊ＝０，１，…，ｋ−１）の値を格納する第２の補助係数レジスタ群３４と、各レジスタ群の個々のレジスタに対して値の書き込み及び読み出しを行うとともに、各種演算を行う演算器３５とを備えている。
【０１２７】
シンドローム系列の数は、“２ｔ”である。そのため、シンドロームレジスタ群３１は、１番目のレジスタＳ（０）から、２ｔ番目までのレジスタＳ（２ｔ-１）までの２ｔ個のレジスタから構成されている。
【０１２８】
係数ベクトルλｋ, 補助係数ベクトルｕｋ及び補助係数ベクトルｖｋの各要素の数は、最大でｔである。そのため、係数レジスタ群３２は、１番目のレジスタλ（０）からｔ番目のレジスタλ（ｔ−１）までのｔ個のレジスタから構成され、第１の補助係数レジスタ群３３は、１番目のレジスタｕ（０）からｔ番目のレジスタｕ（ｔ−１）までのｔ個のレジスタから構成され、第２の補助係数レジスタ群３４は、１番目のレジスタｖ（０）からｔ番目のレジスタｖ（ｔ−１）までのｔ個のレジスタから構成されている。
【０１２９】
なお、各レジスタ群３１，３２,３３及び３４は、バイト単位でデータを保持するものとする。
【０１３０】
つぎに、演算器３５による演算処理手順を説明する。
【０１３１】
演算器３５では、各レジスタ群に対する初期条件の入力処理と、ｋ次の多項式からｋ＋１次の多項式を導くループ演算処理と、検証処理とを行う。
【０１３２】
まず、演算器３０は、係数レジスタ群３２，第１の補助係数レジスタ群３３及び第２の補助係数レジスタ群３４に対して、下記式（２２１），式（２２２），式（２２３）の初期条件を入力する。
λ（ｊ＝０，１，…，ｔ−１）＝０  …（２２１）
ｕ（ｊ＝０，１，…，ｔ−１）＝０  …（２２２）
ｖ（ｊ＝０，１，…，ｔ−１）＝０  …（２２３）
すなわち、全てのレジスタに対して０を入力する。
【０１３３】
続いて、演算器３５は、以下のループ演算処理を行う。
【０１３４】
ループ演算では、まず、演算器３５は、図６に示すように、係数レジスタ群３２，第１の補助係数レジスタ群３３及び第２の補助係数レジスタ群３４におけるｋ＋１番目のレジスタλ（ｋ）、ｕ（ｋ）、ｖ（ｋ）の更新を行う。具体的には、演算器３５は、下記の（２２４），式（２２５），式（２２６）の演算を行い、レジスタλ（ｋ）、ｕ（ｋ）、ｖ（ｋ）に演算結果を格納する。
λ（ｋ）＝（Σｓ（ｃ−１＋ｋ−ｊ＋１）λ（ｊ−１）＋ｓ（ｃ−１＋ｋ＋１））
／（Σｓ（ｃ−１＋ｋ−ｊ＋１）ｕ（ｊ−１）＋ｓ（ｃ−１））  …（２２４）
ｕ（ｋ）＝（Σｓ（ｃ−１−ｋ＋ｊ−１）ｕ（ｊ−１）＋ｓ（ｃ−１−ｋ−１））
／（Σｓ（ｃ−１−ｋ＋ｊ−１）ｖ（ｊ−１）＋ｓ（ｃ−１））  …（２２５）
ｖ（ｋ）＝（Σｓ（ｃ−１＋ｋ−ｊ＋１）ｖ（ｊ−１）＋ｓ（ｃ−１＋ｋ＋１））
／（Σｓ（ｃ−１＋ｋ−ｊ＋１）ｕ（ｊ−１）＋ｓ（ｃ−１））  …（２２６）
なお、式（２２４）〜（２２６）においてのΣは、ｊを１からｋまで１ずつ変化させて総和演算をするものである。
【０１３５】
ここで、これらの計算は、λ＿ｎを計算するブロック、ｕ＿ｎを計算するブロック、ｕｄを計算するブロック、ｖ＿ｎを計算するブロック及びｖ＿ｄを計算するブロックと、除算を行うブロックと組み合わせることで算出することができる。
【０１３６】
各ブロックでは、下式の演算が行われる。
λ＿ｎ＝Σｓ（ｔ−１＋ｋ−ｊ＋１）λ（ｊ−１）＋ｓ（ｔ−１＋ｋ＋１）
ｕ＿ｎ＝Σｓ（ｔ−１−ｋ＋ｊ−１）ｕ（ｊ−１）＋ｓ（ｔ−１−ｋ−１）
ｕ＿ｄ＝Σｓ（ｔ−１−ｋ＋ｊ−１）ｖ（ｊ−１）＋ｓ（ｔ−１）
ｖ＿ｎ＝Σｓ（ｔ−１＋ｋ−ｊ＋１）ｖ（ｊ−１）＋ｓ（ｔ−１＋ｋ＋１）
ｖ＿ｄ＝Σｓ（ｔ−１＋ｋ−ｊ＋１）ｕ（ｊ−１）＋ｓ（ｔ−１）
なお、以上の５つの式のΣは、ｊを１からｋまで１ずつ変化させて総和演算をするものである。
【０１３７】
続いて、演算器３５は、各レジスタ群の１番目のレジスタからｋ番目のレジスタの値を更新する。具体的に、演算器３５は、１番目のレジスタλ（０），ｕ（０），ｖ（０）から、ｋ番目のレジスタλ（ｋ−１），ｕ（ｋ−１），ｖ（ｋ−１）の要素を、下記の式（２１７），式（２１８），式（２１９）の演算を行って求める。
λ（ｊ）＝λ（ｊ）＋（λ（ｋ）・ｕ（ｋ−ｊ−１））  …（２１７）
ｕ（ｊ）＝ｕ（ｊ）＋（ｕ（ｋ）・ｖ（ｋ−ｊ−１））  …（２１８）
ｖ（ｊ）＝ｖ（ｊ）＋（ｖ（ｋ）・ｕ（ｋ−ｊ−１））  …（２１９）
【０１３８】
演算器３５は、以上のループ演算を、ｋ＝０から順次行っていく。
【０１３９】
具体的には、第２の補助係数レジスタ群３４の更新は、図７に示すように、第１の補助係数レジスタ群３３を反転させることにより、第１の補助係数レジスタ群３３の内部をｕ（ｊ｜ｊ＝ｋ−１，ｋ−２，…，１，０）といったように並べかえ、並べ替えた値にｖλ（ｋ）を乗算し、乗算結果をｖ（ｊ｜ｊ＝０，１，…，ｋ−１）に加算すればよい。
【０１４０】
また、第１の補助係数レジスタ群３３の更新は、図８に示すように、第２の補助係数レジスタ群３４を反転させることにより、第２の補助係数レジスタ群３４の内部をｖ（ｊ｜ｊ＝ｋ−１，ｋ−２，…，１，０）といったように並べかえ、並べ替えた値にｕ（ｋ）を乗算し、乗算結果をｕ（ｊ｜ｊ＝０，１，…，ｋ−１）に加算すればよい。
【０１４１】
また、第係数レジスタ群３２の更新は、図９に示すように、第２の補助係数レジスタ群３４を反転させることにより、第２の補助係数レジスタ群３４の内部をｖ（ｊ｜ｊ＝ｋ−１，ｋ−２，…，１，０）といったように並べかえ、並べ替えた値にλ（ｋ）を乗算し、乗算結果をλ（ｊ｜ｊ＝０，１，…，ｋ−１）に加算すればよい。
【０１４２】
演算器３５は、以上のループ演算を、ｋ＝０から順次行っていく。
そして、上記のｕ＿ｄを計算するブロック又はｖ＿ｄを計算するブロックのいずれかの出力が０になった時点で、このループ演算を停止する。
【０１４３】
ループ演算が停止すると、次に、演算器３５は、検証処理を行う。
【０１４４】
検証処理では、ループ演算が終了した時点でのレジスタλの値を、誤り位置多項式の仮の係数とする。
【０１４５】
演算器３５は、このときのレジスタλｋの値である仮の係数に矛盾がないか否かを判断することにより、係数を検証する。係数の検証は、以下の式（２２０）に基づき行われる。また、式（２２０）の演算を行う回路例を図１０に示す。
ｗ（ｉ）＝Σｓ（ｃ＋ｉ−ｊ）λｋ（ｊ）−ｓ（ｃ＋ｉ）
，（ｉ＝０，１，…，ｃ−１）…  （２２０）
式（２２０）においてのΣは、ｊを１からｋまで１ずつ変化させて総和演算をするものである。
【０１４６】
演算器３５は、式（２２０）の値が全て０であれば矛盾がないと判断し、そうでなければ矛盾があると判断する。
【０１４７】
なお、式（２２０）の演算のうち、ｉ＝０からｋ−１までは、もともとｗ（ｉ）が０になるとの条件で漸化式をといて、λｋ（ｊ）を求めたものであるから、あえて確認する必要がない。
【０１４８】
また、ｉ＝ｋの場合は、上記漸化式が停止したときのレジスタλｎの値であるから、これが０であるかどうかをまず確認する。
【０１４９】
以降、ｉ＝ｃ−１までは、上記のｗ（ｊ）をきちんと計算して、これらが０になるかどうか調べる。
【０１５０】
もしこの検算の結果、ｗ（ｊ）＝０でないものがあれば、この係数は誤り位置係数ではないので、演算器３５は、ｃを変更して上記のループ演算から処理を再度繰り返す。ｃの変更は、丁度シンドロームレジスタ群３１のレジスタをシフトさせることに相当する。
【０１５１】
また、もし、ｗ（ｊ）がすべて０であれば、レジスタλに記憶されているレジスタ値が誤り位置多項式の係数として決定する。
【０１５２】
誤り位置多項式生成回路１０では、以上のように、誤り位置多項式の次数ｋと、係数λを決定することができる。
【０１５３】
（チェン探索回路）
図１１は、チェン探索回路１１のブロック図である。
【０１５４】
チェン探索回路１１には、誤り位置検出多項式計算回路１０により計算された誤り位置多項式の係数λ（０）, λ（１）,…, λ（ｋ−１）が入力される。チェン検索回路１１は、この多項式の係数λ（０）, λ（１）,…, λ（ｋ−１）に基づき、受信系列ｒ（０）,ｒ（１）,…,ｒ（ｎ−１）中の実際の誤り位置の特定を行う。
【０１５５】
チェン探索回路１１は、図１１に示すように、１クロック毎に内部格納値に対して係数を乗算していく多数の乗算ループ１８-０,１８-１,…と、各乗算ループ１８-０,１８-１,…の格納値を総和演算する加算回路１９と、加算回路１９の出力が０となったか否かを比較する比較回路２０と、カウンタ回路２１とを備えている。
【０１５６】
チェン探索回路１１には、まず、誤り位置検出多項式計算回路１０により計算された誤り位置多項式の各係数λ（０）, λ（１）,…, λ（ｋ−１）が入力される。誤り位置多項式が得られた時点で、多項式の次数から誤りの多重度ｋ（すなわち、誤りがあったワード数ｋ）が決定する。多重度をｋとしたとき、多数の乗算ループ１８のうち上位からｋ個の乗算ループ１８-０,１８-１,…１８-（ｋ-１）が選択される。選択された乗算ループ１８-０,１８-１,…１８-（ｋ-１）には、対応する係数λ（０）, λ（１）,…, λ（ｋ−１）がそれぞれ格納される。なお、乗算ループ１８-０,１８-１,…１８-（ｋ-１）には、上位から順番に係数としてα０，α１，…，αｋ−１が設定されている。
【０１５７】
各乗算ループ１８-０,１８-１,…１８-（ｋ-１）は、係数λ（０）, λ（１）,…, λ（ｋ−１）が入力されたのち、１クロック毎に、格納値と係数α０，α１，…，αｋ−１とを乗算し、乗算結果を内部に格納する。加算回路１９は、１クロック毎に、各乗算ループ１８-０,１８-１,…１８-（ｋ-１）の内部格納値の総和演算を行う。カウンタ回路２１は、１クロック毎に、内部カウント値をインクリメントしていくとともに、比較回路２０が加算回路１９からの総和出力が０となったか否かを判断し、０となった場合にはカウンタ回路２１がそのときのカウント値を出力する。
【０１５８】
ここで、加算回路１９の出力が０になったときの乗算ループ１８のクロック数は、受信系列を後ろから数えた際の位置を表している。従って、加算回路１９からの総和出力が０となったその時点におけるカウント値が、誤り位置となる。
【０１５９】
チェン探索回路１１では、乗算ループ１８の乗算演算及びカウンタ回路２１のカウント演算を、受信系列の情報数分のクロック数（ｎクロック数）だけ処理を行い、全ての誤り位置を出力する。
【０１６０】
（誤り値計算回路）
誤り値計算回路１２は、図１２に示すようなステップＳ１１からステップＳ１４の処理を行うことにより、誤り系列ｅ０，ｅ１，…，ｅｎ−１を算出する。
【０１６１】
誤り値計算回路１２は、まず、ステップＳ１１において、多項式Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）の係数λ（ｊ｜ｊ＝０，１，…，ｋ）を求める。
【０１６２】
続いて、誤り値計算回路１２は、ステップＳ１２において、多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ）を除算することにより得られる多項式Ｐｉ（ｘ）｛＝（Π（ｘ−α＾ｐｊ））／（ｘ−α＾ｐｉ）｝の係数μｉｊ（ｉ，ｊ＝０，１，…，ｋ−１）を求める。
【０１６３】
続いて、誤り値計算回路１２は、ステップＳ１３において、係数μｉｊ（ｉ,ｊ｜ｉ,ｊ＝０，１，…，ｋ−１）を順次シンドロームｓ（ｊ｜ｊ＝０，１，…，２ｔ−１）に乗じて累加算し、累加算して得られた値をＰｉ（ｘｉ）で除算することにより、誤り位置ｐ（ｊ｜ｊ＝０，１，…，ｋ−１）における誤り値ｅｉ＝（Σμｉｊ・ｓ（ｊ））／（Σμｉｊ・α＾（ｊ・ｐｉ））を計算する。
【０１６４】
続いて、誤り値計算回路１２は、ステップＳ１４において、算出した誤り値から、誤り系列ｅ０，ｅ１，…，ｅｎ−１を算出する。
【０１６５】
以下、それぞれのステップの処理内容を説明する。
【０１６６】
（ステップＳ１１）
ステップＳ１１では、多項式Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）の係数λ（ｊ｜ｊ＝０，１，…，ｋ）を求める。
【０１６７】
図１３は、多項式Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）の係数λ（ｊ｜ｊ＝０，１，…，ｋ）を求める回路のブロック図である。
【０１６８】
誤り値計算回路１２は、ステップＳ１１の処理を行う回路として、ガロア体上の２５６元に対応するビット表現を出力するガロア体ＲＯＭ４１と、係数レジスタ群４２と、演算部４３とを備えている。
【０１６９】
係数レジスタ群４２には、多項式Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）の係数λ（ｊ｜ｊ＝０，１，…，ｋ）が格納される。ｋは、ｔ次以下であるため、係数レジスタ群４２は、少なくともｔ＋１個のレジスタから構成されていれば充分である。なお、１つのレジスタには８ビットのデータが記憶される。
【０１７０】
ガロア体ＲＯＭ４１には、誤り位置ｐｊが順番に入力される。ガロア体ＲＯＭ４１は、誤り位置ｐｊが入力されると、その誤り位置をガロア体上の２５６元に対応するビット表現α＾ｐｊに変換する。
【０１７１】
演算部４２は、係数レジスタ群４２の最上位のレジスタに、常に１を格納しておく。
【０１７２】
演算部４２には、ガロア体ＲＯＭ４１から１つの誤り位置α＾ｐｊがｊ＝０からｋ−１まで１つずつ順次入力される。
【０１７３】
演算部４２は、誤り位置α＾ｐｊが１つ入力されると、その都度演算を行い、係数レジスタ群４２を更新する。具体的には、演算部４２は、α＾ｐｊと、係数レジスタ群４２の各レジスタの格納値とを乗算し、その乗算結果と元のレジスタの格納値とを加算し、そして、その加算結果を一つ下位にシフトして係数レジスタ群４２に格納する、という処理を行うことにより更新がされる。
【０１７４】
以上の更新処理がｊ＝０からｊ＝ｋ−１まで行われると、係数レジスタ群４２には、誤り位置多項式の係数λｉの順序を反転した多項式Ｐ（ｘ）（＝Π（ｘ−α＾ｐｊ））の係数λ（ｊ｜ｊ＝０，１，…，ｋ）が格納される。
【０１７５】
なお、多項式Ｐ（ｘ）＝Π（ｘ−α＾ｐｊ）の係数λ（ｊ｜ｊ＝０，１，…，ｋ）を求める処理は、以上のように誤り位置を示す系列ｐ（ｊ｜ｊ＝０，１，…，ｋ−１）から求めてもよいが、誤り位置多項式生成回路１０により生成された誤り位置多項式の係数λｉの順序を反転する処理により求めても良い。
【０１７６】
（ステップＳ１２）
ステップＳ１２では、多項式Ｐ（ｘ）を（ｘ−α＾ｐｉ）で割ったときの商として得られる多項式Ｐｉ（ｘ）｛＝（Π（ｘ−α＾ｐｊ））／（ｘ−α＾ｐｉ）｝の係数μｉｊ（ｉ，ｊ＝０，１，…，ｋ−１）を求める。
【０１７７】
図１４は、組み立て除法によって、係数μｉｊを求める回路である。
【０１７８】
誤り値計算回路１２は、ステップＳ１２の組み立て除法を行うための回路として、上述したガロア体ＲＯＭ４１、係数レジスタ群４２及び演算部４３の他に、補助レジスタ群４４を備えている。
【０１７９】
補助レジスタ群４４は、係数レジスタ群４２と同様に少なくともｔ＋１個のレジスタから構成されていれば充分である。なお、１つのレジスタには８ビットのデータが記憶される。
【０１８０】
最初に、演算部４３は、係数レジスタ群４２に格納されている係数λ（ｊ｜ｊ＝０，１，…，ｋ）を、補助レジスタ群４４にコピーする。従って、補助レジスタ群４４の１番目のレジスタには１が格納され、２番目のレジスタにはλ（ｋ−１）が格納され、３番目のレジスタにはλ（ｋ−２）が格納され、任意のｊ番目のレジスタにはλ（ｋ−ｊ−１）が格納されている。
【０１８１】
続いて、演算部４２は、補助レジスタ群４４の１番目のレジスタの値を、係数μｉ０として出力する。つまり、係数μｉ０として１を出力する。その後、補助レジスタ群４４の１番目のレジスタの値とα＾ｐｉとを乗算し、その乗算値と補助レジスタ群４４の２番目のレジスタの係数λ（ｋ−１）とを加算し、その加算結果を補助レジスタ群４４の２番目のレジスタに格納する。
【０１８２】
続いて、演算部４２は、補助レジスタ群４４の２番目のレジスタの値を、係数μｉ１として出力する。その後、補助レジスタ群４４の２番目のレジスタの値とα＾ｐｉとを乗算し、その乗算値と補助レジスタ群４４の３番目のレジスタの係数λ（ｋ−２）とを加算し、その加算結果を補助レジスタ群４４の３番目のレジスタに格納する。
【０１８３】
続いて、演算部４２は、補助レジスタ群４４の任意のｊ番目のレジスタの値を、係数μｉ，ｊ−１として出力する。その後、補助レジスタ群４４のｊ番目のレジスタの値とα＾ｐｉとを乗算し、その乗算値と補助レジスタ群４４のｊ＋１番目のレジスタの係数λ（ｋ−ｊ−２）とを加算し、その加算結果を補助レジスタ群４４のｊ＋１番目のレジスタに格納する。
【０１８４】
最後に、演算部４２は、補助レジスタ群４４の任意のｋ＋１番目のレジスタの値を、係数μｉ，ｋとして出力する。その後、補助レジスタ群４４のｋ＋１番目のレジスタの値とα＾ｐｉとを乗算し、その乗算値と補助レジスタ群４４のｋ＋２番目のレジスタの値とを加算し、その加算結果を補助レジスタ群４４のｋ＋２番目のレジスタに格納する。
【０１８５】
以上の処理を、演算部４２は、ｉ＝０から、ｉ＝ｋ−１まで繰り返して行う。
【０１８６】
このような処理を行うことにより、係数μｉｊが全て求められる。
【０１８７】
（ステップＳ１３）
ステップＳ１３では、具体的な誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）を算出する。
【０１８８】
図１５は、演算部４２による誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）を算出する演算処理を示した図である。
【０１８９】
演算部４２には、ｉ番目の誤り値ｅ（ｉ）を求める際に、ｋ個の係数μｉｊ（ｊ＝０，１，…，ｋ−１）と、ｋ個のシンドロームｓ（ｊ｜ｊ＝０，１,…,ｋ−１）とが順番に入力される。
【０１９０】
演算部４２は、ｊ＝０からｊ＝ｋ−１まで下記式（２２１）、及び式（２２２）の演算を行う。
【０１９１】
ｅｎｉ＝ｅｎｉ＋μｉｊ・ｓ（ｊ）    …（２２１）
ｅｄｉ＝μｉｊ＋ｅｄｉ・α＾ｐｉ    …（２２２）
演算部４２は、ｊ＝ｋ−１までこの演算を終えると、下記式（２２３）に示すようにｅｎｉをｅｄｉで除算する。
ｅｉ＝ｅｎｉ／ｅｄｉ    …（２２３）
このときの出力値が、ｉ番目の誤り値ｅｉである。
【０１９２】
演算部４２は、この誤り値をｉ＝０からｉ＝ｋ−１まで行い、全ての誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）を算出する。
【０１９３】
（ステップＳ１４）
ステップＳ１３では、算出した誤り値ｅ（ｉ｜ｉ＝０，１，…，ｋ−１）を、チェン探索回路１１によって探索された誤り位置に配置して、送信系列ｔ（０,１,…,ｎ−１）に対応した系列の誤り系列ｅ（ｉ｜ｉ＝０,１,…,ｎ−１）を生成する。
【０１９４】
（訂正回路）
図１６は、訂正回路１３のブロック図である。
【０１９５】
訂正回路１３は、加算器２７を備えている。訂正回路１３では、受信系列と誤り系列とを減算して、受信系列から送信系列を復元する。
【０１９６】
リード・ソロモン復号回路の場合であれば、加算器２７には、誤り値計算回路１２により計算された誤り系列ｅ０，ｅ１，…，ｅｎ−１と、受信系列ｒ０，ｒ１，…，ｒｎ−１とが入力され、これらを加算して出力する。
【０１９７】
訂正回路１３は、加算器２７の出力系列を、送信系列（ｔ（ｉ｜ｉ＝０,１,…,ｎ−１）として出力する。
【図面の簡単な説明】
【０１９８】
【図１】リード・ソロモン符号を付加した情報を記録媒体に記録する記録システムの構成を示す図である。
【図２】リード・ソロモン符号化回路の回路図である。
【図３】リード・ソロモン復号回路の回路図である。
【図４】シンドローム生成回路の回路図である。
【図５】誤り位置多項式生成回路の構成を示すブロック図である。
【図６】誤り位置多項式生成のためのループ演算の処理を示す図である。
【図７】誤り位置多項式生成のための補助係数ｖの更新処理を示す図である。
【図８】誤り位置多項式生成のための補助係数ｕの更新処理を示す図である。
【図９】誤り位置多項式生成のための補助係数λの更新処理を示す図である。
【図１０】誤り位置多項式生成のための検証の処理を示す図である。
【図１１】チェン探索回路の回路図である。
【図１２】誤り値計算回路の処理内容を示すフローチャートである。
【図１３】誤り値計算回路のステップＳ１１で用いられる処理回路を示す図である。
【図１４】誤り値計算回路のステップＳ１２で用いられる処理回路を示す図である。
【図１５】誤り値計算回路のステップＳ１３で用いられる処理回路を示す図である。
【図１６】誤り訂正回路の回路図である。
【符号の説明】
【０１９９】
１-４  リード・ソロモン復号回路、９  シンドローム計算回路、１０  誤り位置多項式生成回路、１１  チェン探索回路、１２  誤り値計算回路、１３  誤り訂正回路
【図１】
2006033233.tif 000003
【図２】
2006033233.tif 000004
【図３】
2006033233.tif 000005
【図４】
2006033233.tif 000006
【図５】
2006033233.tif 000007
【図６】
2006033233.tif 000008
【図７】
2006033233.tif 000009
【図８】
2006033233.tif 000010
【図９】
2006033233.tif 000011
【図１０】
2006033233.tif 000012
【図１１】
2006033233.tif 000013
【図１２】
2006033233.tif 000014
【図１３】
2006033233.tif 000015
【図１４】
2006033233.tif 000016
【図１５】
2006033233.tif 000017
【図１６】
2006033233.tif 000018