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