(57)【要約】【課題】シンドロームの算出を必要とぜず、速やかに元の情報語を復元可能なリード・ソロモン符号のｔ誤り訂正ｅ復元復号アルゴリズムを確立する。【解決手段】  補間部２２は、受信された受信語に基づき１変数多項式ｌ（ｘ）をする。１変数多項式生成部２３は、１変数多項式ｌ（ｘ）に基づき、所定の条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズムを用いて算出する。判定部２４は、１変数多項式ａ（ｘ），ｂ（ｘ）が、条件「ａ（ｘ）がｂ（ｘ）で割り切れ、且つ、deg（ｆ~（ｘ））≦ｋ−１」（ｆ~（ｘ）＝ａ（ｘ）／ｂ（ｘ））を満たすか否か判定する。評価部２５は、ｆ~（ｘ）を符号位置で評価することにより、復号語を算出する。本発明は、リード・ソロモン符号を用いた信号を受信する受信装置等に適用することができる。【選択図】図２
2006222679.tif 000002
【特許請求の範囲】
【請求項１】
リード・ソロモン符号に生じている誤りを訂正するとともに消失を復元する復号装置において、
送信されたリード・ソロモン符号に対応する受信語を受信する受信手段と、
前記受信手段によって受信された前記受信語に基づく補間演算により、第１の１変数多項式を生成する補間手段と、
前記第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成手段と、
前記第２および第３の１変数多項式に基づき、前記リード・ソロモン符号を復号する復号手段と
を含むことを特徴とする復号装置。
【請求項２】
前記第２および第３の１変数多項式が所定の条件を満たしているか否かを判定する判定手段と、
前記判定手段による判定結果をユーザに通知する通知手段と
をさらに含むことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記生成手段は、拡張ユークリッドアルゴリズムを適用して、前記第１の１変数多項式と所定の関係を満たす前記第２および第３の１変数多項式を生成する
ことを特徴とする請求項１に記載の復号装置。
【請求項４】
前記生成手段は、変形した拡張ユークリッドアルゴリズムを適用して、前記第１の１変数多項式と所定の関係を満たす前記第２および第３の１変数多項式を生成する
ことを特徴とする請求項３に記載の復号装置。
【請求項５】
送信された前記リード・ソロモン符号は、有限体Ｆqの原始元をβとするとき、符号位置（β0，β0，…，βn-1）の評価によって符号化された符号長ｎ、情報長ｋのリード・ソロモン符号（ｋ＜ｎ≦ｑ）であり、
前記補間手段は、前記受信手段によって受信された前記受信語に基づく補間演算により、前記第１の１変数多項式として、（ｎ−ｅ−１）次１変数多項式ｌ（ｘ）を生成し、
前記生成手段は、以下の条件
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod Π（ｘ−βi）
deg ａ（ｘ）≦raise（（（ｎ＋ｋ−ｅ）／２）−１）
deg ｂ（ｘ）≦deduce（（ｎ−ｋ−ｅ）／２））
（Πはｉ＝０，１，…，ｎ−１（ただし、消失している符号位置は除外する）の相乗積、degは次数、raiseは切り上げ演算、deduceは切り下げ演算を意味する）
を満たす前記第２の１変数多項式ａ（ｘ）および前記第３の１変数多項式ｂ（ｘ）を生成し、
前記復号手段は、前記第２の１変数多項式ａ（ｘ）および前記第３の１変数多項式ｂ（ｘ）に基づき、前記リード・ソロモン符号に生じているｔ個の誤りを訂正し、ｅ個の消失を復元する
ことを特徴とする請求項１に記載の復号装置。
【請求項６】
送信された前記リード・ソロモン符号は、有限体Ｆq上の任意の符号長（ｑ−１）、情報長ｋであって、生成多項式Π（ｘ−αi）（Πはｉ＝ｂ，ｂ＋１，…，ｂ＋ｑ−ｋ−２の相乗積）によって与えられるリード・ソロモン符号（ｋ＜ｑ−１）であり、
前記補間手段は、前記受信手段によって受信された前記受信語に基づく補間演算により、前記第１の１変数多項式として、（ｑ−２−ｅ）次１変数多項式ｌ（ｘ）を生成し、
前記生成手段は、以下の条件
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod Π（ｘ−αi）
deg ａ（ｘ）≦raise（（（ｑ−ｅ−１＋ｋ）／２）−１）
deg ｂ（ｘ）≦deduce（（ｑ−ｅ−１−ｋ）／２））
（Πはｉ＝０，１，…，ｑ−２（ただし、消失している符号位置は除外する）の相乗積、degは次数、raiseは切り上げ演算、deduceは切り下げ演算を意味する）
を満たす前記第２の１変数多項式ａ（ｘ）および前記第３の１変数多項式ｂ（ｘ）を生成し、
前記復号手段は、前記第２の１変数多項式ａ（ｘ）および前記第３の１変数多項式ｂ（ｘ）に基づき、前記リード・ソロモン符号に生じているｔ個の誤りを訂正し、ｅ個の消失を復元する
ことを特徴とする請求項１に記載の復号装置。
【請求項７】
リード・ソロモン符号に生じている誤りを訂正するとともに消失を復元する復号方法において、
送信されたリード・ソロモン符号に対応する受信語を受信する受信ステップと、
前記受信ステップの処理で受信された前記受信語に基づく補間演算により、第１の１変数多項式を生成する補間ステップと、
前記第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成ステップと、
前記第２および第３の１変数多項式に基づき、前記リード・ソロモン符号を復号する復号ステップと
を含むことを特徴とする復号方法。
【請求項８】
リード・ソロモン符号に生じている誤りを訂正するとともに消失を復元するためのプログラムであって、
送信されたリード・ソロモン符号に対応する受信語を受信する受信ステップと、
前記受信ステップの処理で受信された前記受信語に基づく補間演算により、第１の１変数多項式を生成する補間ステップと、
前記第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成ステップと、
前記第２および第３の１変数多項式に基づき、前記リード・ソロモン符号を復号する復号ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および方法、並びにプログラムに関し、特に、例えば、代数的手法によって、符号の誤りや消失が生じているリード・ソロモン符号を復号する場合に用いて好適な復号装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
ディジタル信号を通信したり記録したりする場合において用いられる符号化の一手法として、リード・ソロモン符号化が知られている（例えば、非特許文献１参照）。
【０００３】
送信側において、情報長ｋのディジタル信号（情報語）を符号長ｎの符号語（［ｎ，ｋ］リード・ソロモン符号）に符号化して送信した場合、受信側で受信される受信語にｔ個の誤りやｅ個の消失が生じていたとしても、条件２ｔ＋ｅ≦ｎ−ｋが満たされているならば、誤りを訂正し、消失を復元して元の情報語を復号することが可能である。ただし、ｅ，ｋ，ｎ，ｔは非負整数である。
【０００４】
上述したｔ誤り訂正ｅ復元復号アルゴリズムとしては、例えば、Peterson-Gorenstein-Zierler法、Berlkamp-massey法、ユークリッド法等が知られている。これ等の復号アルゴリズムでは、シンドロームを算出し、鍵方程式を解くことにより復号が行われる。なお、このシンドロームの算出には、多くの演算が必要である。
【０００５】
【特許文献１】「誤り訂正符号とその応用」、著者：日立電子  江藤 良純  東京理科大学  金子 敏信、監修、映像情報メディア学会  編、１９９６年２月出版
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、これらの復号アルゴリズムをソフトウェアによって実施した場合、演算に多くの時間を要してしまうという課題があった。また、ハードウェアによって実施した場合、回路規模が大きくなってしまうという課題があった。
【０００７】
なお、例えば、Berlkamp-welch法等のようにシンドロームの算出を必要としないｔ誤り訂正ｅ復元復号アルゴリズムも存在するが、その処理過程における演算量がシンドロームの算出と同様に膨大であって元の情報語を復元できるまでに多くの時間を要してしまうという課題があった。
【０００８】
本発明はこのような状況に鑑みてなされたものであり、リード・ソロモン符号のｔ誤り訂正ｅ復元復号において、シンドロームを算出することなく、速やかに元の情報語を復号できるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の復号装置は、送信されたリード・ソロモン符号に対応する受信語を受信する受信手段と、受信手段によって受信された受信語に基づく補間演算により、第１の１変数多項式を生成する補間手段と、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成手段と、第２および第３の１変数多項式に基づき、リード・ソロモン符号を復号する復号手段とを含むことを特徴とする。
【００１０】
本発明の復号装置は、第２および第３の１変数多項式が所定の条件を満たしているか否かを判定する判定手段と、判定手段による判定結果をユーザに通知する通知手段とをさらに含むことができる。
【００１１】
前記生成手段は、拡張ユークリッドアルゴリズムを適用して、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成するようにすることができる。
【００１２】
前記生成手段は、変形した拡張ユークリッドアルゴリズムを適用して、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成するようにすることができる。
【００１３】
前記送信されたリード・ソロモン符号は、有限体Ｆqの原始元をβとするとき、符号位置（β0，β0，…，βn-1）の評価によって符号化された符号長ｎ、情報長ｋのリード・ソロモン符号（ｋ＜ｎ≦ｑ）であり、前記補間手段は、受信手段によって受信された受信語に基づく補間演算により、第１の１変数多項式として、（ｎ−ｅ−１）次１変数多項式ｌ（ｘ）を生成し、
生成手段は、以下の条件
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod Π（ｘ−βi）
deg ａ（ｘ）≦raise（（（ｎ＋ｋ−ｅ）／２）−１）
deg ｂ（ｘ）≦deduce（（ｎ−ｋ−ｅ）／２））
（Πはｉ＝０，１，…，ｎ−１（ただし、消失している符号位置は除外する）の相乗積、degは次数、raiseは切り上げ演算、deduceは切り下げ演算を意味する）
を満たす第２の１変数多項式ａ（ｘ）および第３の１変数多項式ｂ（ｘ）を生成し、前記復号手段は、第２の１変数多項式ａ（ｘ）および第３の１変数多項式ｂ（ｘ）に基づき、リード・ソロモン符号に生じているｔ個の誤りを訂正し、ｅ個の消失を復元するようにすることができる。
【００１４】
前記送信されたリード・ソロモン符号は、有限体Ｆq上の任意の符号長（ｑ−１）、情報長ｋであって、生成多項式Π（ｘ−αi）（Πはｉ＝ｂ，ｂ＋１，…，ｂ＋ｑ−ｋ−２の相乗積）によって与えられるリード・ソロモン符号（ｋ＜ｑ−１）であり、前記補間手段は、受信手段によって受信された受信語に基づく補間演算により、第１の１変数多項式として、（ｑ−２−ｅ）次１変数多項式ｌ（ｘ）を生成し、前記生成手段は、以下の条件
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod Π（ｘ−αi）
deg ａ（ｘ）≦raise（（（ｑ−ｅ−１＋ｋ）／２）−１）
deg ｂ（ｘ）≦deduce（（ｑ−ｅ−１−ｋ）／２））
（Πはｉ＝０，１，…，ｑ−２（ただし、消失している符号位置は除外する）の相乗積、degは次数、raiseは切り上げ演算、deduceは切り下げ演算を意味する）
を満たす第２の１変数多項式ａ（ｘ）および第３の１変数多項式ｂ（ｘ）を生成し、前記復号手段は、第２の１変数多項式ａ（ｘ）および第３の１変数多項式ｂ（ｘ）に基づき、リード・ソロモン符号に生じているｔ個の誤りを訂正し、ｅ個の消失を復元するようにすることができる。
【００１５】
本発明の復号方法は、送信されたリード・ソロモン符号に対応する受信語を受信する受信ステップと、受信ステップの処理で受信された受信語に基づく補間演算により、第１の１変数多項式を生成する補間ステップと、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成ステップと、第２および第３の１変数多項式に基づき、リード・ソロモン符号を復号する復号ステップとを含むことを特徴とする。
【００１６】
本発明のプログラムは、送信されたリード・ソロモン符号に対応する受信語を受信する受信ステップと、受信ステップの処理で受信された受信語に基づく補間演算により、第１の１変数多項式を生成する補間ステップと、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成ステップと、第２および第３の１変数多項式に基づき、リード・ソロモン符号を復号する復号ステップとを含む処理をコンピュータに実行させることを特徴とする。
【００１７】
本発明の復号装置および方法、並びにプログラムにおいては、受信された受信語に基づく補間演算により、第１の１変数多項式が生成され、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式が生成され、第２および第３の１変数多項式に基づきリード・ソロモン符号が復号される。
【発明の効果】
【００１８】
本発明によれば、リード・ソロモン符号のｔ誤り訂正ｅ復元復号において、シンドロームを算出することなく、速やかに元の情報語を復号することが可能となる。
【発明を実施するための最良の形態】
【００１９】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００２０】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加されたりする発明の存在を否定するものではない。
【００２１】
請求項１に記載の復号装置（例えば、図１の復号装置１４）は、送信されたリード・ソロモン符号に対応する受信語を受信する受信手段（例えば、図２の受信部２１）と、受信手段によって受信された受信語に基づく補間演算により、第１の１変数多項式を生成する補間手段（例えば、図２の補間部２２）と、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成手段（例えば、図２の１変数多項式生成部２３）と、第２および第３の１変数多項式に基づき、リード・ソロモン符号を復号する復号手段（例えば、図２の評価部２５）とを含む。
【００２２】
請求項２に記載の復号装置は、第２および第３の１変数多項式が所定の条件を満たしているか否かを判定する判定手段（例えば、図２の判定部２４）と、判定手段による判定結果をユーザに通知する通知手段（例えば、図２の出力部２６）とをさらに含む。
【００２３】
請求項７に記載の復号方法は、送信されたリード・ソロモン符号に対応する受信語を受信する受信ステップ（例えば、図３のステップＳ１）と、受信ステップの処理で受信された受信語に基づく補間演算により、第１の１変数多項式を生成する補間ステップ（例えば、図３のステップＳ２）と、第１の１変数多項式と所定の関係を満たす第２および第３の１変数多項式を生成する生成ステップ（例えば、図３のステップＳ３）と、第２および第３の１変数多項式に基づき、リード・ソロモン符号を復号する復号ステップ（例えば、図３のステップＳ６）とを含む。
【００２４】
なお、本発明のプログラムの請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係は、上述した本発明の復号方法のものと同様であるので、その記載は省略する。
【００２５】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００２６】
図１は、本発明を適用した情報通信システムの構成例を示している。この情報通信システム１は、情報生成装置１１、符号化装置１２、復号装置１４、および情報処理装置１５から構成される。
【００２７】
情報生成装置１１は、送信対象である情報語長ｋの情報語（ｆ0，ｆ1，…，ｆk-1）を生成して符号化装置１２に出力する。符号化装置１２は、情報語（ｆ0，ｆ1，…，ｆk-1）を、以下に説明する第１または第２の符号化方法によってリード・ソロモン符号（符号語）に変換し、通信路１３を介して復号装置１４に送信する。
【００２８】
符号化装置１２による第１の符号化方法は、情報語（ｆ0，ｆ1，…，ｆk-1）を、有限体Ｆq上の［ｎ，ｋ］リード・ソロモン符号（ｋ＜ｎ≦ｑ）に変換する符号化であって、次式（１）を符号位置（β0，β1，…，βn-1）（βiは有限体Ｆqの相異なる元）で評価することにより、符号語（ｆ（β0），ｆ（β1），…，ｆ（βn-1））を生成するものである。ｎは符号長、ｋは情報長である。
ｆ（ｘ）＝Σｆiｘi  （Σはｉ＝０，１，…，ｋ−１の総和）        …（１）
【００２９】
符号化装置１２による第２の符号化方法は、情報語（ｆ0，ｆ1，…，ｆk-1）を、次式（２）に示す生成多項式に基づいて有限体Ｆｑ上の［ｑ−１，ｋ］リード・ソロモン符号（ｋ＜ｑ−１）に変換する。ｑ−１は符号長、ｋは情報長である。
Π（ｘ−αｉ）  （Πはｉ＝ｂ，ｂ＋１，…，ｂ＋ｑ−ｋ−２の相乗積）  …（２）
【００３０】
復号装置１４は、符号化装置１２によって送信された符号語に通信路１３を介して受信する。ただし、復号装置１４によって受信された符号語には、通信路１３におけるノイズ等の影響によって誤りや消失が発生している可能性がある。復号装置１４によって受信された符号語を受信語と称する。さらに、復号装置１４は、受信語を復号し、復号結果の復号語（情報語）を情報処理装置１５に出力する。また、復号装置１４は、受信した受信語を復号できなかった場合、その旨を示す情報を情報処理装置１５に出力する。このとき、受信語も出力するようにしてもよい。
【００３１】
情報処理装置１５は、復号装置１４から入力される情報語に対して所定の処理を実行する。また、情報処理装置１５は、復号装置１４から受信語が復号できなかった旨を示す情報が入力された場合、復号できなかった旨をユーザに通知する。
【００３２】
図２は、復号装置１４の構成例を示している。復号装置１４は、受信部２１、補間部２２、１変数多項式生成部２３、判定部２４、評価部２５、および出力部２６から構成される。
【００３３】
受信部２１は、符号化装置１２から送信された符号語を、通信路１３を介して受信し、受信語として補間部２２に出力する。
【００３４】
補間部２２、１変数多項式生成部２３、判定部２４、および評価部２５は、符号化装置１２において第１の符号化方法が採用されている場合には、後述する第１の復号方式で動作する。また、符号化装置１２において第２の符号方法が採用されている場合には、後述する第２の復号化方式で動作する。
【００３５】
まず、符号化装置１２において第１の符号化方法が採用されている場合に対応する第１の符号化方式について説明する。補間部２２は、受信部２１によって受信された受信語（ｒ0，ｒ1，…，ｒn-1）に基づき、ｌ（βi）＝ｒiとなる有限体Ｆq上の（ｎ−ｅ−１）次１変数多項式ｌ（ｘ）をLagrange補間法、またはNewton補間法等を用いて算出し、１変数多項式生成部２３に出力する。
ｌ（ｘ）＝Σｌiｘi                                            …（３）
ここで、Σはｉ＝０，１，…，ｎ−ｅ−１の総和である。
【００３６】
１変数多項式生成部２３は、補間部２２から入力された１変数多項式ｌ（ｘ）に基づき、次式（４）乃至（６）に示す条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズム（後述）を用いて算出し、判定部２４に出力する。
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod Π（ｘ−βi）                  …（４）
deg ａ（ｘ）≦raise（（（ｎ＋ｋ−ｅ）／２）−１）             …（５）
deg ｂ（ｘ）≦deduce（（ｎ−ｋ−ｅ）／２））                  …（６）
ここで、Πはｉ＝０，１，…，ｎ−１（ただし、消失している符号位置は除外する）の相乗積である。degは次数を示す。raiseは（）内部の切り上げ演算である。deduceは（）内部の切り下げ演算である。
【００３７】
判定部２４は、１変数多項式生成部２３で算出された１変数多項式ａ（ｘ），ｂ（ｘ）が以下の条件を満たしているか否かを判定し、条件を満たしている場合、１変数多項式ａ（ｘ），ｂ（ｘ）を評価部２５に出力し、条件を満たしていない場合、復号できない旨を示す情報を生成して出力部２６に出力する。
ａ（ｘ）がｂ（ｘ）で割り切れ、且つ、deg（ｆ~（ｘ））≦ｋ−１
ただし、ｆ~（ｘ）＝ａ（ｘ）／ｂ（ｘ）
【００３８】
評価部２５は、ｆ~（ｘ）を符号位置βiで評価することにより、復号語（ｆ~（β0），ｆ~（β1），…，ｆ~（βn-1））を算出し、出力部２６に供給する。出力部２６は、評価部２５から供給される復号語、または判定部２４から供給される復号できない旨を示す情報を後段に出力する。なお、復号失敗の旨を示す情報とともに、復号することができなかった受信語も後段に出力するようにしてもよい。
【００３９】
符号化装置１２において第２の符号化方法が採用されている場合に対応する第２の復号方法について説明する。補間部２２は、受信部２１によって受信された受信語（ｒ0，ｒ1，…，ｒq-2）∈Ｆqq-2に基づき、ｌ（αi）＝αi(b-1)ｒiとなる有限体Ｆｑ上の（ｑ−２−ｅ）次１変数多項式ｌ（ｘ）をLagrange補間法、またはNewton補間法等を用いて算出し、１変数多項式生成部２３に出力する。
ｌ（ｘ）＝Σｌiｘi                                          …（７）
ここで、Σはｉ＝０，１，…，ｑ−２−ｅの総和である。
【００４０】
１変数多項式生成部２３は、補間部２２から入力された１変数多項式ｌ（ｘ）に基づき、次式（８）乃至（１０）に示す条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズム（後述）を用いて算出し、判定部２４に出力する。
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod Π（ｘ−αi）                  …（８）
deg ａ（ｘ）≦raise（（（ｑ−１＋ｋ−ｅ）／２）−１）         …（９）
deg ｂ（ｘ）≦deduce（（ｑ−１−ｋ−ｅ）／２））              …（１０）
ここで、Πはｉ＝０，１，…，ｑ−２（ただし、消失している符号位置は除外する）の相乗積である。
【００４１】
判定部２４は、第１の復号方法と同様に、１変数多項式生成部２３で算出された１変数多項式ａ（ｘ），ｂ（ｘ）が条件（ａ（ｘ）がｂ（ｘ）で割り切れ、且つ、deg（ｆ~（ｘ））≦ｋ−１）満たしているか否かを判定し、条件を満たしている場合、１変数多項式ａ（ｘ），ｂ（ｘ）を評価部２５に出力し、条件を満たしていない場合、復号できない旨を示す情報を生成して出力部２６に出力する。
【００４２】
評価部２５は、ｆ~（ｘ）を符号位置αｉで評価することにより、復号語（ｆ~（１），α1-bｆ~（α），…，α(q-2)(1-b)ｆ~（αq-2））を算出し、出力部２６に供給する。
【００４３】
出力部２６は、符号化装置１２において第１の符号化方法が採用されている場合と同様、評価部２５から供給される復号語、または判定部２４から供給される復号できない旨を示す情報を後段に出力する。なお、復号失敗の旨を示す情報とともに、復号することができなかった受信語も後段に出力するようにしてもよい。
【００４４】
次に、復号装置１４によって実行される第１の復号方法について、以下の３通りの例を図３および図４のフローチャートを参照して説明する。
【００４５】
第１の例について説明する。符号化装置１２で第１の符号化方法が採用され、情報語（ｆ0，ｆ1）＝（１，２）が有限体Ｆ5上の［５，２］リード・ソロモン符号に符号位置β0，β1，β2，β3，β4＝０，１，２，３，４で符号化されて送信された場合を考える。この場合、送信される符号語は、ｆ（ｘ）＝１＋２ｘが符号位置で評価された（１＋２・０，１＋２・１，１＋２・２，１＋２・３，１＋２・４）＝（１，３，０，２，４）である。
【００４６】
ステップＳ１において、受信部２１が、送信された符号語（１，３，０，２，４）を、通信路１３を介して取得し、受信語として補間部２２に出力する。ここで、受信語には、通信路１３におけるノイズ等の影響によって誤りや消失が発生しており、例えば、誤り数ｔ＝１、消失数ｅ＝０の受信語（ｒ0，ｒ1，ｒ2，ｒ3，ｒ4）＝（１，３，３，２，４）が取得されたと仮定する。この場合、条件２ｔ＋ｅ≦ｎ−ｋが満たされているので、受信語が正確に復号されることを以下において確認する。
【００４７】
ステップＳ２において、補間部２２が、ｌ（０）＝１，ｌ（１）＝３，ｌ（２）＝３，ｌ（３）＝２，ｌ（４）＝４となる有限体Ｆ5上の４次１変数多項式ｌ（ｘ）＝Σｌiｘiを、Lagrange補間法等を用いて算出し、１変数多項式生成部２３に出力する。算出される４次１変数多項式は、次式（１１）に示されるとおりとなる。
ｌ（ｘ）＝２ｘ4＋４ｘ3＋３ｘ2＋３ｘ＋１                    …（１１）
【００４８】
ステップＳ３において、１変数多項式生成部２３が、補間部２２から入力された１変数多項式ｌ（ｘ）に基づき、次式（１２）乃至（１４）に示される条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズムを用いて算出し、判定部２４に出力する。
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod x(x-1)(x-2)(x-3)(x-4)        …（１２）
deg ａ（ｘ）≦raise（２．５）＝３                           …（１３）
deg ｂ（ｘ）≦deduce（１．５）＝１                          …（１４）
【００４９】
１変数多項式生成部２３によるステップＳ３の処理について、図４のフローチャートを参照して詳述する。なお、以下においては、
ａ（ｘ）＝ｂ（ｘ）ｑ（ｘ）＋ｒ（ｘ）
０＜deg ｒ（ｘ）＜deg ｂ（ｘ）
と定義する。
【００５０】
ステップＳ２１において、１変数多項式生成部２３が、ρ0，ρ1，ｒ0，ｒ1，ｓ0，ｓ1，ｔ0，ｔ1を以下の定義に従って算出または初期化する。
ρ0＝ｌｃ（Π（ｘ−βi））
＝ｌｃ（x(x-1)(x-2)(x-3)(x-4)）＝ｌｃ（ｘ5＋４ｘ）＝１
ρ1＝ｌｃ（ｌ（ｘ））＝２
ｒ0＝normal（Π（ｘ−βi））＝ｘ5＋４ｘ
ｒ1＝normal（ｌ（ｘ））＝ｘ4＋２ｘ3＋（３／２）ｘ2＋（３／２）ｘ＋１／２
ｓ0＝ρ0-1
ｓ1＝０
ｔ0＝０
ｔ1＝ρ1-1
【００５１】
ここで、ｌｃは、（）内の最高次数項の係数を示す。normalは、（）内部を（）内の最高次数項の係数で正規化した値である。Πはｉ＝０，１，…，ｎ−１（ただし、消失している符号位置に対応するｉは除外する）の相乗積である。
【００５２】
ステップＳ２２において、１変数多項式生成部２３が、パラメータｊに１を代入する。ステップＳ２３において、次式（１５）に示される条件が満たされているか否かを判定し、満たされていると判定した場合、ステップＳ２４の処理に進む。
deg ｒj＞raise（（ｎ−ｅ＋ｋ）／２）−１）＝３              …（１５）
【００５３】
なお、当該ステップＳ２３の処理を含むことが、拡張ユークリッドアルゴリズムを変形した箇所に相当する。ステップＳ２３の処理を含むことにより、単に拡張ユークリッドアルゴリズムを適用する場合に比較して、より速やかに１変数多項式ａ（ｘ），ｂ（ｘ）を算出することができる。
【００５４】
ステップＳ２４において、ｑjにｒj-1 quo ｒjを代入する。ｒj-1 quo ｒjは、ｒj-1をｒjで除算したときの商である。ステップＳ２５において、ρj+1にｌｃ（ｒj-1 rem ｒj）を代入する。ｒj-1 rem ｒjは、ｒj-1をｒjで除算したときの剰余である。ステップＳ２６において、ｒj+1にnormal（ｒj-1 rem ｒj）を代入する。ステップＳ２７において、ｓj+1に（ｓj-1−ｑjｓj）／ρj+1を代入する。ステップＳ２８において、ｔj+1に（ｔj-1−ｑjｔj）／ρj+1を代入する。ステップＳ２９において、パラメータｊを１だけインクリメントする。
【００５５】
この後、処理はステップＳ２３に戻り、ステップＳ２３において、式（１５）に示された条件が満たされていないと判定するまで、すなわち、次式（１６）に示される条件が満たされたと判定するまで、ステップＳ２３乃至Ｓ２９の処理を繰り返す。
deg ｒj≦３                                                …（１６）
【００５６】
そして、ステップＳ２３において、式（１６）に示された条件が満たされたと判定した場合、処理はステップＳ３０に進む。ステップＳ３０において、ｔjをｂ（ｘ）に設定し、ｒjをａ（ｘ）に設定する。以上で、１変数多項式ａ（ｘ），ｂ（ｘ）を算出する処理が終了される。
【００５７】
いまの場合、ステップＳ２３乃至Ｓ２９の処理において、
ｊ＝０のとき、
ρ0＝１
ｒ0＝ｘ5＋４ｘ
ｓ0＝１
ｔ0＝０
ｊ＝１のとき、
ｑ1＝ｘ＋３
ρ1＝２
ｒ1＝ｘ4＋２ｘ3＋４ｘ2＋４ｘ＋３
ｓ1＝０
ｔ1＝３
ｊ＝２のとき、
ｑ2＝ｘ＋３
ρ2＝４
ｒ2＝ｘ2＋ｘ＋４
ｓ2＝４
ｔ2＝３ｘ＋４
である。
【００５８】
上記のように、ｊ＝２のときに式（１６）に示された条件が満たされるので、
ａ（ｘ）＝ｘ2＋ｘ＋４
ｂ（ｘ）＝３ｘ＋４
となる。
【００５９】
図３に戻る。ステップＳ４において、判定部２４が、１変数多項式生成部２３によって算出された１変数多項式ａ（ｘ）をｂ（ｘ）で除算してｆ〜（ｘ）を算出することにより、ａ（ｘ）がｂ（ｘ）で割り切れるか否かを判定する。割り切れると判定された場合、処理はステップＳ５に進む。反対に、ａ（ｘ）がｂ（ｘ）で割り切れないと判定された場合、処理はステップＳ７に進む。
【００６０】
いまの場合、ｆ〜（ｘ）＝ａ（ｘ）／ｂ（ｘ）＝２ｘ＋１であって、ａ（ｘ）がｂ（ｘ）で割り切れるので、処理はステップＳ５に進む。
【００６１】
ステップＳ５において、判定部２４が、次式（１７）が満たされているか否かを判定し、条件を満たしていると判定した場合にはステップＳ６に進み、条件を満たしていないと判定した場合にはステップＳ７に進む。
deg（ｆ~（ｘ））≦ｋ−１＝１                                  …（１７）
【００６２】
いまの場合、ｆ~（ｘ）の次数は１であるので、式（１７）の条件は満たされている。従って、処理はステップＳ６に進む。ステップＳ６において、判定部２４が、１変数多項式ａ（ｘ），ｂ（ｘ）を評価部２５に出力する。評価部２５が、ｆ~（ｘ）＝２ｘ＋１を符号位置（０，１，２，３，４）で評価することにより、復号語（２・０＋１，２・１＋１，２・２＋１，２・３＋１，２・４＋１）＝（１，３，０，２，４）を算出し、出力部２６に供給する。そして、出力部２６が、評価部２５から供給された復号語（１，３，０，２，４）を後段に出力する。以上説明したように、送信された符号語と復号語が等しいので、誤り数ｔ＝１、消失数ｅ＝０の受信語を正確に復号できることが確認された。
【００６３】
なお、ステップＳ４またはステップＳ５の処理からステップＳ７に進んだ場合、受信語の復号が不可能であるので、判定部２４が、復号できない旨を示す情報を出力部２６に通知し、出力部２６が当該情報を後段に出力する。以上で、第１の例の説明を終了する。
【００６４】
第２の例について説明する。送信される符号語は、第１の例と同様とする。ステップＳ１において、受信部２１が、送信された符号語（１，３，０，２，４）を、通信路１３を介して取得し、受信語として補間部２２に出力する。ここで、受信語には、通信路１３におけるノイズ等の影響によって誤りや消失が発生しており、例えば、誤り数ｔ＝２、消失数ｅ＝０の受信語（ｒ0，ｒ1，ｒ2，ｒ3，ｒ4）＝（１，３，３，３，４）が取得されたと仮定する。この場合、条件２ｔ＋ｅ≦ｎ−ｋが満たされていないので、受信語が復号できないことを以下において確認する。
【００６５】
ステップＳ２において、補間部２２が、ｌ（０）＝１，ｌ（１）＝３，ｌ（２）＝３，ｌ（３）＝３，ｌ（４）＝４となる有限体Ｆ5上の４次１変数多項式ｌ（ｘ）＝Σｌiｘiを、Lagrange補間法等を用いて算出し、１変数多項式生成部２３に出力する。算出される４次１変数多項式は、次式（１８）に示されるとおりとなる。
ｌ（ｘ）＝３ｘ4＋３ｘ2＋ｘ＋１                              …（１８）
【００６６】
ステップＳ３において、１変数多項式生成部２３が、補間部２２から入力された１変数多項式ｌ（ｘ）に基づき、式（１２）乃至（１４）に示された条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズムを用いて算出し、判定部２４に出力する。具体的には、ステップＳ２１において、１変数多項式生成部２３は、ρ0，ρ1，ｒ0，ｒ1，ｓ0，ｓ1，ｔ0，ｔ1を以下の定義に従って算出または初期化する。
ρ0＝ｌｃ（Π（ｘ−βi））
＝ｌｃ（x(x-1)(x-2)(x-3)(x-4)）＝ｌｃ（ｘ5＋４ｘ）＝１
ρ1＝ｌｃ（ｌ（ｘ））＝３
ｒ0＝normal（Π（ｘ−βi））＝ｘ5＋４ｘ
ｒ1＝normal（ｌ（ｘ））＝ｘ4＋ｘ2＋（１／３）ｘ＋１／３
ｓ0＝ρ0-1
ｓ1＝０
ｔ0＝０
ｔ1＝ρ1-1
【００６７】
ステップＳ２２において、１変数多項式生成部２３が、パラメータｊに１を代入する。ステップＳ２３において、次式（１９）に示される条件が満たされているか否かを判定する。
deg ｒj＞raise（（ｎ−ｅ＋ｋ）／２）−１）＝３              …（１９）
【００６８】
いまの場合、式（１９）が満たされているので、ステップＳ２４乃至Ｓ２９の処理が行われる。この後、処理はステップＳ２３に戻り、ステップＳ２３において、式（１９）に示された条件が満たされていないと判定するまで、すなわち、次式（２０）に示される条件が満たされたと判定するまで、ステップＳ２３乃至Ｓ２９の処理を繰り返す。
deg ｒj≦３                                                 …（２０）
【００６９】
そして、ステップＳ２３において、式（２０）に示された条件が満たされたと判定した場合、処理はステップＳ３０に進む。ステップＳ３０において、ｔjをｂ（ｘ）に設定し、ｒjをａ（ｘ）に設定する。以上で、１変数多項式ａ（ｘ），ｂ（ｘ）を算出する処理が終了される。
【００７０】
いまの場合、ステップＳ２３乃至Ｓ２９の処理において、
ｊ＝０のとき、
ρ0＝１
ｒ0＝ｘ5＋４ｘ
ｓ0＝１
ｔ0＝０
ｊ＝１のとき、
ｑ1＝ｘ
ρ1＝３
ｒ1＝ｘ4＋ｘ2＋２ｘ＋２
ｓ1＝０
ｔ1＝２
ｊ＝２のとき、
ｑ2＝ｘ＋３
ρ2＝４
ｒ2＝ｘ3＋２ｘ2＋３ｘ
ｓ2＝４
ｔ2＝２ｘ
である。
【００７１】
上記のように、ｊ＝２のときに式（２０）に示された条件が満たされるので、
ａ（ｘ）＝ｘ3＋２ｘ2＋３ｘ
ｂ（ｘ）＝２ｘ
となる。
【００７２】
図３に戻る。ステップＳ４において、判定部２４が、１変数多項式生成部２３によって算出された１変数多項式ａ（ｘ）をｂ（ｘ）で除算してｆ〜（ｘ）を算出することにより、ａ（ｘ）がｂ（ｘ）で割り切れるか否かを判定する。いまの場合、ｆ〜（ｘ）＝ａ（ｘ）／ｂ（ｘ）＝３ｘ2＋ｘ＋４であって、ａ（ｘ）がｂ（ｘ）で割り切れるので、処理はステップＳ５に進む。
【００７３】
ステップＳ５において、判定部２４が、次式（２１）が満たされているか否かを判定する。
deg（ｆ~（ｘ））≦ｋ−１＝１                                  …（２１）
【００７４】
いまの場合、ｆ~（ｘ）の次数は３であるので、式（２１）の条件は満たされていない。従って、処理はステップＳ７に進む。ステップＳ７において、判定部２４が、復号できない旨を示す情報を出力部２６に通知し、出力部２６が当該情報を後段に出力する。以上説明したように、第２の例の場合、誤り数ｔ＝２、消失数ｅ＝０の受信語を復号できないことが確認された。
【００７５】
第３の例について説明する。送信される符号語は、第１の例と同様とする。ステップＳ１において、受信部２１が、送信された符号語（１，３，０，２，４）を、通信路１３を介して取得し、受信語として補間部２２に出力する。ここで、受信語には、通信路１３におけるノイズ等の影響によって誤りや消失が発生しており、例えば、誤り数ｔ＝１、消失数ｅ＝１の受信語（ｒ0，ｒ1，ｒ2，ｒ3，ｒ4）＝（１，２，＊，２，４）（＊は消失を示す）が取得されたと仮定する。この場合、条件２ｔ＋ｅ≦ｎ−ｋが満たされているので、受信語が復号できることを以下において確認する。
【００７６】
ステップＳ２において、補間部２２が、ｌ（０）＝１，ｌ（１）＝２，ｌ（３）＝２，ｌ（４）＝４となる有限体Ｆ5上の４次１変数多項式ｌ（ｘ）＝Σｌiｘiを、Lagrange補間法等を用いて算出し、１変数多項式生成部２３に出力する。算出される４次１変数多項式は、次式（２２）に示されるとおりとなる。
ｌ（ｘ）＝ｘ3＋３ｘ2＋ｘ＋２                                …（２２）
【００７７】
ステップＳ３において、１変数多項式生成部２３が、補間部２２から入力された１変数多項式ｌ（ｘ）に基づき、式（１２）乃至（１４）に示された条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズムを用いて算出し、判定部２４に出力する。具体的には、ステップＳ２１において、１変数多項式生成部２３が、ρ0，ρ1，ｒ0，ｒ1，ｓ0，ｓ1，ｔ0，ｔ1を以下の定義に従って算出または初期化する。
ρ0＝ｌｃ（Π（ｘ−βi））
＝ｌｃ（x(x-1)(x-3)(x-4)）＝ｌｃ（ｘ4＋２ｘ3＋４ｘ2＋３ｘ）＝１
ρ1＝ｌｃ（ｌ（ｘ））＝１
ｒ0＝normal（Π（ｘ−βi））＝ｘ4＋２ｘ3＋４ｘ2＋３ｘ
ｒ1＝normal（ｌ（ｘ））＝ｘ3＋３ｘ2＋ｘ＋２
ｓ0＝ρ0-1
ｓ1＝０
ｔ0＝０
ｔ1＝ρ1-1
【００７８】
ステップＳ２２において、１変数多項式生成部２３が、パラメータｊに１を代入する。ステップＳ２３において、次式（２３）に示される条件が満たされているか否かを判定する。
deg ｒj＞raise（（ｎ−ｅ＋ｋ）／２）−１）＝２              …（２３）
【００７９】
いまの場合、式（２３）が満たされているので、ステップＳ２４乃至Ｓ２９の処理が行われる。この後、処理はステップＳ２３に戻り、ステップＳ２３において、式（２３）に示された条件が満たされていないと判定するまで、すなわち、次式（２４）に示される条件が満たされたと判定するまで、ステップＳ２３乃至Ｓ２９の処理を繰り返す。
deg ｒj≦２                                                …（２４）
【００８０】
そして、ステップＳ２３において、式（２４）に示された条件が満たされていると判定した場合、処理はステップＳ３０に進む。ステップＳ３０において、ｔjをｂ（ｘ）に設定し、ｒjをａ（ｘ）に設定する。以上で、１変数多項式ａ（ｘ），ｂ（ｘ）を算出する処理が終了される。
【００８１】
いまの場合、ステップＳ２３乃至Ｓ２９の処理において、
ｊ＝０のとき、
ρ0＝１
ｒ0＝ｘ4＋２ｘ3＋４ｘ2＋３ｘ
ｓ0＝１
ｔ0＝０
ｊ＝１のとき、
ｑ1＝ｘ＋４
ρ1＝３
ｒ1＝ｘ3＋３ｘ2＋ｘ＋２
ｓ1＝０
ｔ1＝２
ｊ＝２のとき、
ｑ2＝ｘ＋１
ρ2＝１
ｒ2＝ｘ2＋２ｘ＋２
ｓ2＝１
ｔ2＝３ｘ＋２
である。
【００８２】
上記のように、ｊ＝２のときに式（２４）に示された条件が満たされるので、
ａ（ｘ）＝ｘ2＋２ｘ＋２
ｂ（ｘ）＝３ｘ＋２
となる。
【００８３】
図３に戻る。ステップＳ４において、判定部２４が、１変数多項式生成部２３によって算出された１変数多項式ａ（ｘ）をｂ（ｘ）で除算してｆ〜（ｘ）を算出することにより、ａ（ｘ）がｂ（ｘ）で割り切れるか否かを判定する。いまの場合、ｆ〜（ｘ）＝ａ（ｘ）／ｂ（ｘ）＝２ｘ＋１であって、ａ（ｘ）がｂ（ｘ）で割り切れるので、処理はステップＳ５に進む。
【００８４】
ステップＳ５において、判定部２４が、次式（２５）が満たされているか否かを判定する。
deg（ｆ~（ｘ））≦ｋ−１＝１                                  …（２５）
【００８５】
いまの場合、ｆ~（ｘ）の次数は１であるので、式（２５）の条件は満たされている。従って、処理はステップＳ６に進む。ステップＳ６において、判定部２４が、１変数多項式ａ（ｘ），ｂ（ｘ）を評価部２５に出力する。そして、評価部２５が、ｆ~（ｘ）＝２ｘ＋１を符号位置（０，１，２，３，４）で評価することにより、復号語（２・０＋１，２・１＋１，２・２＋１，２・３＋１，２・４＋１）＝（１，３，０，２，４）を算出して出力部２６に供給し、出力部２６が、評価部２５から供給された復号語（１，３，０，２，４）を後段に出力する。以上説明したように、送信された符号語と復号語が等しいので、誤り数ｔ＝１、消失数ｅ＝１の受信語を正確に復号できることが確認された。
【００８６】
次に、復号装置１４によって実行される第２の復号方法について、以下の２通りの例を図５および図６のフローチャートを参照して説明する。
【００８７】
第１の例について説明する。符号化装置１２で第２の符号化方法が採用され、次式（２６）に示す生成多項式によって、情報語（ｆ0，ｆ1）＝（１，１）が、有限体Ｆ5上の［４，２］リード・ソロモン符号に符号化されて送信される場合を考える。
Π（ｘ−２i）＝ｘ2＋２ｘ＋２  （Πはｉ＝０，１の相乗積）    …（２６）
ここで、２は有限体Ｆ5の原始元である。
【００８８】
情報語に対応する情報多項式は１＋ｘであり、
ｘ2（ｘ＋１）＝（ｘ＋４）（ｘ2＋２ｘ＋２）＋２
であるから、組織符号化した符号多項式は、
ｘ2（ｘ＋１）−２＝ｘ3＋ｘ2＋３
となり、送信される符号語は（３，０，１，１）である。
【００８９】
ステップＳ４１において、受信部２１が、送信された符号語（３，０，１，１）を、通信路１３を介して取得し、受信語として補間部２２に出力する。ここで、受信語には、通信路１３におけるノイズ等の影響によって誤りや消失が発生しており、例えば、誤り数ｔ＝１、消失数ｅ＝０の受信語（ｒ0，ｒ1，ｒ2，ｒ3）＝（３，０，２，１）が取得されたと仮定する。この場合、条件２ｔ＋ｅ≦ｑ−１−ｋが満たされているので、受信語が正確に復号されることを以下において確認する。
【００９０】
ステップＳ４２において、補間部２２が、ｌ（２0）＝２0×-1×３＝３，ｌ（２1）＝２1×-1×０＝０，ｌ（２2）＝２2×-1＝３，ｌ（２3）＝２3×-1×１＝２となる有限体Ｆ5上の３次１変数多項式ｌ（ｘ）＝Σｌiｘiを、Lagrange補間法等を用いて算出し、１変数多項式生成部２３に出力する。算出される３次１変数多項式は、次式（２７）に示されるとおりとなる。
ｌ（ｘ）＝４ｘ3＋ｘ2＋ｘ＋２                                …（２７）
【００９１】
ステップＳ４３において、１変数多項式生成部２３が、補間部２２から入力された１変数多項式ｌ（ｘ）に基づき、次式（２８）乃至（３０）に示される条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズムを用いて算出し、判定部２４に出力する。
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod (x-20)(x-21)(x-22)(x-23)    …（２８）
deg ａ（ｘ）≦raise（（（５−１＋２−０）／２）−１）＝２  …（２９）
deg ｂ（ｘ）≦deduce（（５−１−２−０）／２））＝１       …（３０）
【００９２】
１変数多項式生成部２３によるステップＳ４３の処理について、図６のフローチャートを参照して詳述する。なお、以下においては、
ａ（ｘ）＝ｂ（ｘ）ｑ（ｘ）＋ｒ（ｘ）
０＜deg ｒ（ｘ）＜deg ｂ（ｘ）
と定義する。
【００９３】
ステップＳ５１において、１変数多項式生成部２３が、ρ0，ρ1，ｒ0，ｒ1，ｓ0，ｓ1，ｔ0，ｔ1を以下の定義に従って算出または初期化する。
ρ0＝ｌｃ（Π（ｘ−αi））
＝ｌｃ（ｘ2＋２ｘ＋２）＝１
ρ1＝ｌｃ（ｌ（ｘ））＝ｌｃ（４ｘ3＋ｘ2＋ｘ＋２）＝４
ｒ0＝normal（Π（ｘ−αi））＝ｘ2＋２ｘ＋２
ｒ1＝normal（ｌ（ｘ））＝ｘ3＋（１／４）ｘ2＋（１／４）ｘ＋１／２
ｓ0＝ρ0-1
ｓ1＝０
ｔ0＝０
ｔ1＝ρ1-1
【００９４】
ステップＳ５２において、１変数多項式生成部２３が、パラメータｊに１を代入する。ステップＳ５３において、次式（３１）に示される条件が満たされているか否かを判定し、満たされていると判定した場合、ステップＳ５４の処理に進む。
deg ｒj＞raise（（ｑ−１−ｅ＋ｋ）／２）−１）＝２          …（３１）
【００９５】
ステップＳ５４において、ｑjにｒj-1 quo ｒjを代入する。ここで、ｒj-1 quo ｒjは、ｒj-1をｒjで除算したときの商である。ステップＳ５５において、ρj+1にｌｃ（ｒj-1 rem ｒj）を代入する。ここで、ｒj-1 rem ｒjは、ｒj-1をｒjで除算したときの剰余である。ステップＳ５６において、ｒj+1にnormal（ｒj-1 rem ｒj）を代入する。ステップＳ５７において、ｓj+1に（ｓj-1−ｑjｓj）／ρj+1を代入する。ステップＳ５８において、ｔj+1に（ｔj-1−ｑjｔj）／ρj+1を代入する。ステップＳ５９において、パラメータｊを１だけインクリメントする。
【００９６】
この後、処理はステップＳ５３に戻り、ステップＳ５３において、式（３１）に示された条件が満たされていないと判定するまで、すなわち、次式（３２）に示される条件が満たされたと判定するまで、ステップＳ５３乃至Ｓ５９の処理を繰り返す。
deg ｒj≦２                                                …（３２）
【００９７】
そして、ステップＳ５３において、式（３２）に示された条件が満たされたと判定した場合、処理はステップＳ６０に進む。ステップＳ６０において、ｔjをｂ（ｘ）に設定し、ｒjをａ（ｘ）に設定する。以上で、１変数多項式ａ（ｘ），ｂ（ｘ）を算出する処理が終了される。
【００９８】
いまの場合、ステップＳ５３乃至Ｓ５９の処理において、
ｊ＝０のとき、
ρ0＝１
ｒ0＝ｘ4＋４
ｓ0＝１
ｔ0＝０
ｊ＝１のとき、
ｑ1＝ｘ＋１
ρ1＝４
ｒ1＝ｘ3＋４ｘ2＋４ｘ＋３
ｓ1＝０
ｔ1＝４
ｊ＝２のとき、
ｑ2＝ｘ
ρ2＝２
ｒ2＝ｘ2＋４ｘ＋３
ｓ2＝３
ｔ2＝３ｘ＋３
である。
【００９９】
上記のように、ｊ＝２のときに式（３２）に示された条件が満たされるので、
ａ（ｘ）＝ｘ2＋４ｘ＋３
ｂ（ｘ）＝３ｘ＋３
となる。
【０１００】
図５に戻る。ステップＳ４４において、判定部２４が、１変数多項式生成部２３によって算出された１変数多項式ａ（ｘ）をｂ（ｘ）で除算してｆ〜（ｘ）を算出することにより、ａ（ｘ）がｂ（ｘ）で割り切れるか否かを判定し、割り切れると判定した場合、ステップＳ４５に進む。反対に、ａ（ｘ）がｂ（ｘ）で割り切れないと判定した場合、ステップＳ４７に進む。
【０１０１】
いまの場合、ｆ〜（ｘ）＝ａ（ｘ）／ｂ（ｘ）＝２ｘ＋１であって、ａ（ｘ）がｂ（ｘ）で割り切れるので、処理はステップＳ４５に進む。
【０１０２】
ステップＳ４５において、判定部２４が、次式（３３）が満たされているか否かを判定し、条件を満たしていると判定した場合にはステップＳ４６に進み、条件を満たしていないと判定した場合にはステップＳ４７に進む。
deg（ｆ~（ｘ））≦ｋ−１＝１                                  …（３３）
【０１０３】
いまの場合、ｆ~（ｘ）の次数は１であるので、式（３３）の条件は満たされる。従って、処理はステップＳ４６に進む。ステップＳ４６において、判定部２４が、１変数多項式ａ（ｘ），ｂ（ｘ）を評価部２５に出力する。評価部２５が、ｆ~（ｘ）＝２ｘ＋１を符号位置で評価することにより、復号語（ｆ〜（１），α1-bｆ〜（α），…，α(q-2)(1-b)ｆ〜（αq-2））＝（２・１＋１，２1-0・（２・２1＋１），２2・(1-0)・（２・２2＋１），２3・(1-0)・（２・２3＋１））＝（３，０，１，１）を算出し、出力部２６に供給する。
【０１０４】
そして、出力部２６が、評価部２５から供給された復号語（３，０，１，１）を後段に出力する。以上説明したように、送信された符号語と復号語が等しいので、誤り数ｔ＝１、消失数ｅ＝０の受信語を正確に復号できることが確認された。
【０１０５】
なお、ステップＳ４４またはステップＳ４５の処理からステップＳ４７に進んだ場合、受信語の復号が不可能であるので、判定部２４が、復号できない旨を示す情報を出力部２６に通知し、出力部２６が当該情報を後段に出力する。以上で、第１の例の説明を終了する。
【０１０６】
第２の例について説明する。ステップＳ４１において、受信部２１が、送信された符号語（３，０，１，１）を、通信路１３を介して取得し、受信語として補間部２２に出力する。ここで、受信語には、通信路１３におけるノイズ等の影響によって誤りや消失が発生しており、例えば、誤り数ｔ＝０、消失数ｅ＝２の受信語（ｒ0，ｒ1，ｒ2，ｒ3）＝（＊，０，＊，１）が取得されたと仮定する。この場合、条件２ｔ＋ｅ≦ｑ−１−ｋが満たされているので、受信語が正確に復号されることを以下において確認する。
【０１０７】
ステップＳ４２において、補間部２２が、ｌ（２1）＝２1×-1×０＝０，ｌ（２3）＝２3×-1×１＝２となる有限体Ｆ5上の１次１変数多項式ｌ（ｘ）＝Σｌiｘiを、Lagrange補間法等を用いて算出し、１変数多項式生成部２３に出力する。算出される１次１変数多項式は、次式（３４）に示されるとおりとなる。
ｌ（ｘ）＝２ｘ＋１                                          …（３４）
【０１０８】
ステップＳ４３において、１変数多項式生成部２３が、補間部２２から入力された１変数多項式ｌ（ｘ）に基づき、次式（３５）乃至（３７）に示される条件を満たす１変数多項式ａ（ｘ），ｂ（ｘ）を、変形した拡張ユークリッドアルゴリズムを用いて算出し、判定部２４に出力する。
ｌ（ｘ）ｂ（ｘ）≡ａ（ｘ） mod （ｘ−２1）（ｘ−２3）      …（３５）
deg ａ（ｘ）≦raise（（（５−１＋２−２）／２）−１）＝１  …（３６）
deg ｂ（ｘ）≦deduce（（５−１−２−２）／２））＝０       …（３７）
【０１０９】
具体的には、ステップＳ５１において、１変数多項式生成部２３が、ρ0，ρ1，ｒ0，ｒ1，ｓ0，ｓ1，ｔ0，ｔ1を以下の定義に従って算出または初期化する。
ρ0＝ｌｃ（Π（ｘ−αi））
＝ｌｃ（ｘ2＋２ｘ＋２）＝１
ρ1＝ｌｃ（ｌ（ｘ））＝ｌｃ（２ｘ＋１）＝２
ｒ0＝normal（Π（ｘ−αi））＝ｘ2＋２ｘ＋２
ｒ1＝normal（ｌ（ｘ））＝ｘ＋１／２
ｓ0＝ρ0-1
ｓ1＝０
ｔ0＝０
ｔ1＝ρ1-1
【０１１０】
ステップＳ５２において、１変数多項式生成部２３が、パラメータｊに１を代入する。ステップＳ５３において、次式（３８）に示される条件が満たされているか否かを判定し、満たされていると判定した場合、ステップＳ５４の処理に進む。
deg ｒj＞raise（（ｑ−１−ｅ＋ｋ）／２）−１）＝１            …（３８）
【０１１１】
いまの場合、式（３８）が満たされているので、ステップＳ５４乃至Ｓ５９の処理が行われる。この後、処理はステップＳ５３に戻り、ステップＳ５３において、式（３８）に示された条件が満たされていないと判定するまで、すなわち、次式（３９）に示される条件が満たされたと判定するまで、ステップＳ５３乃至Ｓ５９の処理を繰り返す。
deg ｒj≦１                                                   …（３９）
【０１１２】
そして、ステップＳ５３において、式（３９）に示された条件が満たされたと判定した場合、処理はステップＳ６０に進む。ステップＳ６０において、ｔjをｂ（ｘ）に設定し、ｒjをａ（ｘ）に設定する。以上で、１変数多項式ａ（ｘ），ｂ（ｘ）を算出する処理が終了される。
【０１１３】
いまの場合、ステップＳ５３乃至Ｓ５９の処理において、
ｊ＝０のとき、
ρ0＝１
ｒ0＝ｘ2＋１
ｓ0＝１
ｔ0＝０
ｊ＝１のとき、
ｑ1＝ｘ＋２
ρ1＝２
ｒ1＝ｘ＋３
ｓ1＝０
ｔ1＝３
である。
【０１１４】
上記のように、ｊ＝１のときに式（３９）に示された条件が満たされるので、
ａ（ｘ）＝ｘ＋３
ｂ（ｘ）＝３
となる。
【０１１５】
図５に戻る。ステップＳ４４において、判定部２４が、１変数多項式生成部２３によって算出された１変数多項式ａ（ｘ）をｂ（ｘ）で除算してｆ〜（ｘ）を算出することにより、ａ（ｘ）がｂ（ｘ）で割り切れるか否かを判定する。いまの場合、ｆ〜（ｘ）＝ａ（ｘ）／ｂ（ｘ）＝２ｘ＋１であって、ａ（ｘ）がｂ（ｘ）で割り切れるので、処理はステップＳ４５に進む。
【０１１６】
ステップＳ４５において、判定部２４が、次式（４０）が満たされているか否かを判定する。
deg（ｆ~（ｘ））≦ｋ−１＝１                                  …（４０）
【０１１７】
いまの場合、ｆ~（ｘ）の次数は１であるので、式（４０）の条件は満たされる。従って、処理はステップＳ４６に進む。ステップＳ４６において、判定部２４が、１変数多項式ａ（ｘ），ｂ（ｘ）を評価部２５に出力する。評価部２５が、ｆ~（ｘ）＝２ｘ＋１を符号位置で評価することにより、復号語（ｆ〜（１），α1-bｆ〜（α），…，α(q-2)(1-b)ｆ〜（αq-2））＝（２・１＋１，２1-0・（２・２1＋１），２2・(1-0)・（２・２2＋１），２3・(1-0)・（２・２3＋１））＝（３，０，１，１）を算出し、出力部２６に供給する。
【０１１８】
そして、出力部２６が、評価部２５から供給された復号語（３，０，１，１）を後段に出力する。以上説明したように、送信された符号語と復号語が等しいので、誤り数ｔ＝１、消失数ｅ＝０の受信語を正確に復号できることが確認された。以上で、第２の例の説明を終了する。
【０１１９】
以上説明したように、復号装置１４による第１または第２の復号方法のいずれにおいても、リード・ソロモン符号のｔ誤り訂正ｅ復元復号において、シンドロームを算出することなく、速やかに元の情報語を復号することができる。
【０１２０】
ところで、上述した復号装置１４による一連の処理は、図２に示されたように構成されるハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば図７に示されるように構成された汎用のパーソナルコンピュータ等に、記録媒体からインストールされる。
【０１２１】
このパーソナルコンピュータ５０は、CPU(Central Processing Unit)５１を内蔵している。CPU５１にはバス５４を介して、入出力インタフェース５５が接続されている。バス５４には、ROM(Read Only Memory)５２およびRAM(Random Access Memory)５３が接続されている。
【０１２２】
入出力インタフェース５５には、ユーザが操作コマンドを入力するキーボード、マウス、等の入力デバイスよりなる入力部５６、合成された映像信号を表示するCRT(Cathode Ray Tube)またはLCD(Liquid Crystal Display)等のディスプレイよりなる出力部５７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部５８、およびモデム、LAN（Local Area Network）アダプタなどよりなり、インタネットに代表されるネットワークを介した通信処理を実行する通信部５９が接続されている。また、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory)、DVD(Digital Versatile Disc)を含む）、光磁気ディスク（ＭＤ(Mini Disc)を含む）、もしくは半導体メモリなどの記録媒体５１に対してデータを読み書きするドライブ６０が接続されている。
【０１２３】
このパーソナルコンピュータ５０に上述した一連の処理を実行させるプログラムは、記録媒体６１に格納された状態でパーソナルコンピュータ５０に供給され、ドライブ６０によって読み出されて記憶部５８に内蔵されるハードディスクドライブにインストールされている。記憶部５８にインストールされているプログラムは、入力部５６に入力されるユーザからのコマンドに対応するCPU５１の指令によって、記憶部５８からRAM５３にロードされて実行される。
【０１２４】
なお、本明細書において、プログラムに基づいて実行されるステップは、記載された順序に従って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１２５】
また、プログラムは、１台のコンピュータにより処理されるものであってもよいし、複数のコンピュータによって分散処理されるものであってもよい。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであってもよい。
【０１２６】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【図面の簡単な説明】
【０１２７】
【図１】本発明を適用した情報通信システムの構成例を示すブロック図である。
【図２】図１の復号装置の構成例を示すブロック図である。
【図３】図３の復号装置による第１の符号化方法を説明するフローチャートである。
【図４】図３のステップＳ３の処理を説明するフローチャートである。
【図５】図３の復号装置による第２の符号化方法を説明するフローチャートである。
【図６】図５のステップＳ４３の処理を説明するフローチャートである。
【図７】本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【０１２８】
１  情報通信システム，  １１  情報生成装置，  １２  符号化装置，  １３  通信路，  １４  復号装置，  １５  情報処理装置，  ２１  受信部，  ２２  補間部，  ２３  １変数多項式生成部，  ２４  判定部，  ２５  評価部，  ２６  出力部，  ５１  CPU，  ６１  記録媒体
【図１】
2006222679.tif 000003
【図２】
2006222679.tif 000004
【図３】
2006222679.tif 000005
【図４】
2006222679.tif 000006
【図５】
2006222679.tif 000007
【図６】
2006222679.tif 000008
【図７】
2006222679.tif 000009