(57)【要約】【課題】訂正能力を高く維持しつつ、計算量を低減することができる復号装置を提供する。【解決手段】復号装置１０であって、受信語と受信語の中で誤りがあるシンボルの位置を示す消失位置情報とが入力され、復号グラフに基づいてシンボルが訂正された第１の受信語と訂正されたシンボルが反映された第１の消失位置情報とを生成する第１の復号部１１と、消失ベクトルＺと係数行列Ｈ’とを抽出し、上三角行列Ｈ”へ係数行列Ｈ’を変換する変換行列Ｔと第１の受信語から第１のシンドロームとを生成する行列処理部１２と、誤りがあるシンボルが訂正された第２の受信語と訂正されたシンボルが反映された第２の消失位置情報とを生成し、訂正されたシンボルが反映された第２のシンドロームに補正する行列復号部１３と、復号グラフに基づいて訂正された第３の受信語と、訂正されたシンボルが反映された第３の消失位置情報とを生成する第２の復号部１４とを備える。【選択図】図１
2010041677.tif 000002
【特許請求の範囲】
【請求項１】
線形符号の誤りを前記線形符号に対応した検査行列を用いて訂正する復号装置であって、
複数のシンボルで構成された受信語と前記受信語の中で誤りがあるシンボルの位置を示す消失位置情報とが入力され、前記検査行列に対応した復号方法を示す復号グラフに基づいて、前記受信語の誤りがあるシンボルの中で訂正可能なシンボルが訂正された第１の受信語と、前記訂正されたシンボルの位置が前記消失位置情報に反映された第１の消失位置情報とを生成する第１の復号部と、
前記生成された第１の受信語と第１の消失位置情報と前記検査行列とから、誤りがあるシンボルで構成される消失ベクトルと前記消失ベクトルの係数となる係数行列とを抽出し、行を入れ替えれば三角行列になる入替三角行列へ前記係数行列を変換する処理を行う変換行列を生成し、前記検査行列に基づいて前記第１の受信語から第１のシンドロームを生成する行列処理部と、
前記生成された変換行列と第１のシンドロームとから、前記第１の受信語の誤りがあるシンボルが訂正された第２の受信語と、前記第１の消失位置情報に前記訂正されたシンボルの位置が反映された第２の消失位置情報とを生成し、前記第１のシンドロームを前記訂正されたシンボルが反映された第２のシンドロームに補正する行列復号部と、
前記生成された第２の受信語と第２の消失位置情報とから、前記第２の受信語の訂正可能なシンボルが前記復号グラフに基づいて訂正された第３の受信語と、前記訂正されたシンボルの位置が前記第２の消失位置情報に反映された第３の消失位置情報とを生成する第２の復号部と
を備えることを特徴とする復号装置。
【請求項２】
前記行列処理部は、
前記第１の消失位置情報に基づく誤りがあるシンボルで構成されるベクトルである前記消失ベクトルと、前記検査行列のうち前記消失ベクトルに対応する列で構成される係数行列とを抽出する係数抽出部と、
前記係数行列を前記入替三角行列へ変換する三角行列生成部と、
前記検査行列と前記第１の受信語とを乗じて算出される第１のシンドロームを生成するシンドローム生成部と、
前記消失ベクトルと前記入替三角行列とを乗じた値が前記第１のシンドロームと変換行列とを乗じた値と同じになるように算出される前記変換行列を生成する変換行列生成部とを備える
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記行列復号部は、
前記入替三角行列の行のうち零でない要素が１つのみの行を選択し、前記選択された行に対応する前記変換行列の行と前記第１のシンドロームとを乗じた値を計算することで、誤りがあるシンボルの値を算出するとともに、前記第２の消失位置情報を生成する消失値計算部と、
前記算出されたシンボルに基づいて、前記第２の受信語を生成する訂正部と、
前記算出されたシンボルに基づいて、前記第１のシンドロームを前記第２のシンドロームに補正するシンドローム補正部とを備える
ことを特徴とする請求項１又は請求項２に記載の復号装置。
【請求項４】
前記行列復号部は、生成された前記第２の受信語と前記第２の消失位置情報と前記第２のシンドロームとを、それぞれ、前記第１の受信語と前記第１の消失位置情報と前記第１のシンドロームとして入力する
ことを特徴とする請求項１〜請求項３のいずれか１項に記載の復号装置。
【請求項５】
前記第２の復号部は、前記第３の受信語に誤りがあるシンボルが存在している場合に、さらに、前記第２のシンドロームに誤りが訂正されたシンボルを反映することで、前記第２のシンドロームを第３のシンドロームに補正し、生成された前記第３の受信語と前記第３の消失位置情報と前記第３のシンドロームとを、それぞれ、前記第２の受信語と前記第２の消失位置情報と前記第２のシンドロームとして入力する
ことを特徴とする請求項１〜請求項４のいずれか１項に記載の復号装置。
【請求項６】
さらに、
前記線形符号の誤り訂正を終了するか否かを判断する終了判断部を備え、
前記第１の復号部は、前記第１の受信語に誤りがあるシンボルが存在するか否かを判定する第１のフラグを生成し、
前記行列処理部は、前記係数行列の前記入替三角行列への変換が可能であるか否かを判定する第２のフラグを生成し、
前記第２の復号部は、前記第３の受信語に誤りがあるシンボルが存在するか否かを判定する第３のフラグを生成するとともに、前記第３の受信語に誤りがあるシンボルが存在していると判定される場合に、前記第２のシンドロームに誤りが訂正されたシンボルを反映することで、前記第２のシンドロームを第３のシンドロームに補正し、
前記終了判断部は、
前記第１のフラグで前記第１の受信語に誤りが存在しないと判定された場合には、前記線形符号の誤り訂正の終了と判断して、前記第１の受信語を誤り訂正済みの受信語として出力し、
前記第２のフラグで前記入替三角行列への変換が不可であると判定された場合には、前記線形符号の誤り訂正の終了と判断して、前記第１の受信語と前記第１の消失位置情報とを誤りが残留している受信語と残留している誤りの位置情報として出力し、
前記第３のフラグで前記第３の受信語に誤りが存在しないと判定された場合には、前記線形符号の誤り訂正の終了と判断して、前記第３の受信語を誤り訂正済みの受信語として出力し、
前記第３のフラグで前記第３の受信語に誤りが存在すると判定された場合には、前記線形符号の誤り訂正が終了していないと判断し、前記第３の受信語と前記第３の消失位置情報と前記第３のシンドロームとを、それぞれ、前記第１の受信語と前記第１の消失位置情報と前記第１のシンドロームとして前記行列復号部に出力する
ことを特徴とする請求項１〜請求項５のいずれか１項に記載の復号装置。
【請求項７】
線形符号の誤りを前記線形符号に対応した検査行列を用いて訂正する復号方法であって、
コンピュータが、複数のシンボルで構成された受信語と前記受信語の中で誤りがあるシンボルの位置を示す消失位置情報とが入力されることにより、前記検査行列に対応した復号方法を示す復号グラフに基づいて、前記受信語の誤りがあるシンボルの中で訂正可能なシンボルが訂正された第１の受信語と、前記訂正されたシンボルの位置が前記消失位置情報に反映された第１の消失位置情報とを生成する第１の復号ステップと、
コンピュータが、前記生成された第１の受信語と第１の消失位置情報と前記検査行列とから、誤りがあるシンボルで構成される消失ベクトルと前記消失ベクトルの係数となる係数行列とを抽出し、行を入れ替えれば三角行列になる入替三角行列へ前記係数行列を変換する処理を行う変換行列を生成し、前記検査行列に基づいて前記第１の受信語から第１のシンドロームを生成する行列処理ステップと、
コンピュータが、前記生成された変換行列と第１のシンドロームとから、前記第１の受信語の誤りがあるシンボルが訂正された第２の受信語と、前記第１の消失位置情報に前記訂正されたシンボルの位置が反映された第２の消失位置情報とを生成し、前記第１のシンドロームを前記訂正されたシンボルが反映された第２のシンドロームに補正する行列復号ステップと、
コンピュータが、前記生成された第２の受信語と第２の消失位置情報とから、前記第２の受信語の訂正可能なシンボルが前記復号グラフに基づいて訂正された第３の受信語と、前記訂正されたシンボルの位置が前記第２の消失位置情報に反映された第３の消失位置情報とを生成する第２の復号ステップと
を含むことを特徴とする復号方法。
【請求項８】
線形符号の誤りを前記線形符号に対応した検査行列を用いて訂正するためのプログラムであって、
複数のシンボルで構成された受信語と前記受信語の中で誤りがあるシンボルの位置を示す消失位置情報とが入力され、前記検査行列に対応した復号方法を示す復号グラフに基づいて、前記受信語の誤りがあるシンボルの中で訂正可能なシンボルが訂正された第１の受信語と、前記訂正されたシンボルの位置が前記消失位置情報に反映された第１の消失位置情報とを生成する第１の復号ステップと、
前記生成された第１の受信語と第１の消失位置情報と前記検査行列とから、誤りがあるシンボルで構成される消失ベクトルと前記消失ベクトルの係数となる係数行列とを抽出し、行を入れ替えれば三角行列になる入替三角行列へ前記係数行列を変換する処理を行う変換行列を生成し、前記検査行列に基づいて前記第１の受信語から第１のシンドロームを生成する行列処理ステップと、
前記生成された変換行列と第１のシンドロームとから、前記第１の受信語の誤りがあるシンボルが訂正された第２の受信語と、前記第１の消失位置情報に前記訂正されたシンボルの位置が反映された第２の消失位置情報とを生成し、前記第１のシンドロームを前記訂正されたシンボルが反映された第２のシンドロームに補正する行列復号ステップと、
前記生成された第２の受信語と第２の消失位置情報とから、前記第２の受信語の訂正可能なシンボルが前記復号グラフに基づいて訂正された第３の受信語と、前記訂正されたシンボルの位置が前記第２の消失位置情報に反映された第３の消失位置情報とを生成する第２の復号ステップと
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号等の線形符号の復号方法および復号装置に関するものである。
【背景技術】
【０００２】
近年、訂正能力に優れた符号として、ＬＤＰＣ符号が有力視されている。そして、ＬＤＰＣ符号の復号アルゴリズムの一つにＳｕｍ−Ｐｒｏｄｕｃｔ法などがある（例えば、非特許文献１〜３）。
【０００３】
ＩＰネットワークで、映像や音声のストリーミング伝送を行なう場合、リアルタイム性を維持するためにロストしたパケットを再送しないＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）で送るケースがある。そのような場合に、伝送経路に無線で伝送する区間があれば、ロストするパケットへの対策が必要になる。この対策としては、パケットをインターリーブして誤り訂正符号化することが考えられる。使用する誤り訂正符号としては、インターリーブ長を長くしやすいＬＤＰＣ符号も有力な候補である。
【０００４】
例えば、図７に示すように、ｐ×ｋビットのデータをｐビットずつのブロックとし、各ブロックから１ビットずつ得たｋビットのデータを符号化して、（ｎ−ｋ）ビットのパリティをつけていくと、トータルでｐ×（ｎ−ｋ）ビットのパリティが付加されることになり、これらのパリティで（ｎ−ｋ）ブロックとなる。伝送する時には、１個のブロックを１個のパケットのデータとして、それぞれヘッダ情報（ＵＤＰヘッダ／ＩＰヘッダなど）を付加し、ＩＰパケットを構成する。インターリーブは、１個のブロックから１ビットではなく複数のビットを集めて１個の符号語に符号化しても構わないし、複数のブロックから１ビットずつ集めて符号化しても構わない。
【０００５】
伝送後に、ｎ個のパケットが揃わなくても、失われたパケットのデータを消失として、ｐ個の符号語の全てに誤り訂正処理を行なって、１ビットずつ復元していけば、元のブロックを復元することが可能である。ＩＰパケットはイーサネット（登録商標）ではパケット長の最大値が１，５００バイトとなっており、ＩＰヘッダ長は標準で２０バイト、ＵＤＰヘッダ長は８バイトであるので、データは最大１，４７２バイト＝１１，７７６ビットまで使用可能である。ストリーミング伝送を行なう場合は、１個のパケットに載せるデータはできるだけ多くし、ヘッダにより増加する伝送レートをできるだけ少なくして効率よく伝送することが要求されるので、１個のＩＰパケットに載せるデータは１０，０００ビット程度にはなると考えられる。１個のＩＰパケットが、符号の１個のシンボルにする場合、シンボル同士の加算は、１０，０００ビット程度の排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）を実行することになる。
【０００６】
以下に、ＬＤＰＣ符号の復号について、説明する。ＬＤＰＣ符号は、線形符号（Ｌｉｎｅａｒ  Ｃｏｄｅ）の１種であるが、線形符号は、ｋ行ｎ列の生成行列Ｇと、Ｇ・ＨT＝０となる（ｎ−ｋ）行ｎ列の検査行列Ｈにより、符号の構造を定義できる。Ｈ・ＧT＝０と記述しても良い。
【０００７】
データ（ベクトル）Ｄ＝（ｄ0，ｄ1，…，ｄ(k-1)）に、生成行列Ｇをかけて、符号語（ベクトル）Ｃ＝（ｃ0，ｃ1，…，ｃ(n-1)）＝Ｄ・Ｇを得ることにより、符号化はなされる。Ｈ・ＣT＝Ｈ・ＧT・ＤT＝０が成立する。伝送されて誤り（消失も含む）が生じた受信語（ベクトル）Ｒ＝（ｒ0，ｒ1，…，ｒ(n-1)）は、誤り（ベクトル）をＥ＝（ｅ0，ｅ1，…，ｅ(n-1)）として、Ｒ＝Ｃ＋Ｅである。
【０００８】
解法１）
シンドロームＳ＝（ｓ0，ｓ1，…，ｓ(n-k-1)）は、ＳT＝Ｈ・ＲT＝Ｈ・（Ｃ＋Ｅ）T＝Ｈ・ＣT＋Ｈ・ＥT＝Ｈ・ＥTにより得られる。ｘ個の消失（ｘ＜（ｎ−ｋ））が生じた場合、誤り（ベクトル）Ｅのｎ個のシンボルのうち、消失の位置以外にある（ｎ−ｘ）個のシンボルは０であるから、上記したＳ＝Ｈ・ＲT＝Ｈ・ＥTの式は、残りのｘ個の消失シンボルの値を変数とする１次ｘ元連立方程式となる。式の数は、（ｎ−ｋ）であるから、これを解いて、各シンボルの大きさを求めれば、誤りの訂正が可能になる。
【０００９】
解法２）
ＬＤＰＣ符号は、線形符号の中でも、検査行列Ｈにおいて０の要素が非常に多い。即ち、非零の要素が低密度であるという特徴を持つ符号である。ＢＣＨ符号では検査行列Ｈの要素のほぼ半分が‘１’であり、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号では検査行列Ｈの要素の全てが非零であるが、ＬＤＰＣ符号では検査行列Ｈの要素の数％のみが非零である。符号によっては、非零の要素が１％未満の符号もある。
【００１０】
０＝Ｈ・ＣT＝Ｈ・（Ｒ−Ｅ）Tになるように、Ｅを選ぶにあたって、検査行列Ｈの各行の非零の要素が非常に少ないので、導出される１次ｘ元連立方程式の各式は、
（０）非零の要素に相当する位置に、消失が１個もない式：連立方程式としては無意味
（１）非零の要素に相当する位置に、消失が１個だけある式：その式だけで、当該の消失の値を計算可能
（２）非零の要素に相当する位置に、消失が２個以上ある式
の３種類に分類される。
【００１１】
（１）のグループの式による訂正を行なえば、その式は（０）のグループの式になり、また訂正できた消失を含む（２）のグループの式の一部は、（１）のグループの式になる。（１）のグループの式の数が０個になるまで、これを繰り返して訂正する。
【００１２】
具体例を図８Ａに示す。符号長１２、データシンボル数６であり、図８Ａに示す２値の検査行列に基づく符号を例とする。
【００１３】
図８Ｂは、この検査行列に基づく受信語の各シンボルとシンドロームの各シンボルとの関係をグラフで表わしたものである。このグラフを復号グラフという。つまり、復号グラフは、受信語の各シンボルと、シンドロームの各シンボルとの関係を表わしたグラフである。シンドロームの左端のシンボルｓ0は、受信語のシンボルのうちのｒ0、ｒ1、ｒ2、ｒ3とつながっており、ｒ0、ｒ1、ｒ2、ｒ3が符号語通りの値を受信していれば、ｓ0＝ｒ0＋ｒ1＋ｒ2＋ｒ3＝０（＋は、排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）として使用している）となるべきことを示している。
【００１４】
図８Ｃは、受信語のｒ0、ｒ5が、消失となった例である。ｒ0を含むシンドロームはｓ0、ｓ3であり、ｒ5を含むシンドロームはｓ1、ｓ5である。また、シンドロームｓ0、ｓ1、ｓ3、ｓ5につながっている受信語のシンボルのうち、消失したシンボルは、それぞれ１個だけである。従って、ｓ0もしくはｓ3からはｒ0を、ｓ1もしくはｓ5からはｒ5を、復元して訂正することが可能である。上記の説明で言えば、（１）のグループの式が４個と、（０）のグループの式が２個存在しており、（１）のグループの式に基づいて訂正していけば、全て（０）のグループの式となっている。
【００１５】
図８Ｄは、受信語のｒ2、ｒ3が、消失となった例である。ｒ2を含むシンドロームはｓ0、ｓ5であり、ｒ5を含むシンドロームもまたｓ0、ｓ5である。また、シンドロームｓ0、ｓ5につながっている受信語のシンボルのうち、消失したシンボルは、どちらも２個である。ｒ2＋ｒ3がどのような値になるかは判明するが、それ以上は決められない。上記の説明で言えば、（０）のグループの式が４個と、（２）のグループの式が２個存在しており、最初から（１）のグループの式は存在しない。
【００１６】
図８Ｅ〜図８Ｇは、受信語のｒ1、ｒ3、ｒ6、ｒ7、ｒ9が、消失となった例である。最初に図８Ｅに示すように、シンドロームｓ0につながっている受信語のシンボルのうち、消失はｒ1、ｒ3の２個である。シンドロームｓ1では、消失はｒ6、ｒ7の２個である。シンドロームｓ2では、消失はｒ9の１個である。シンドロームｓ3では、消失はｒ1、ｒ7、ｒ9の３個である。シンドロームｓ4では、消失はｒ6の１個である。シンドロームｓ5では、消失はｒ3の１個である。
【００１７】
まず、図８Ｆに示すように、シンドロームｓ2、ｓ4、ｓ5から、消失ｒ3、ｒ6、ｒ9を復元し、他のシンドロームにこの結果をフィードバックすると、シンドロームｓ0につながっている受信語のシンボルのうち、消失はｒ1の１個となる。シンドロームｓ1では、消失はｒ7の１個になる。シンドロームｓ3では、消失はｒ1、ｒ7の２個になる。
【００１８】
そこで、図８Ｇに示すように、シンドロームｓ0、ｓ1から、消失ｒ1、ｒ7を復元することができ、このようにして全てのシンボルを正しく復号することができる。
【００１９】
符号の符号長をｎ、データ数をｋ、レートをＲ＝ｋ／ｎ、ｄｅｇｒｅｅ（検査行列の各列の“１”の数）をｄｅｇとし、ｘシンボルの消失を訂正する時、解法２）での計算量は、Ｏ（ｘ×ｄｅｇ／（１−Ｒ））である。これに対し、解法１）での計算量は、連立方程式を解く段階のシンドローム処理だけでＯ（ｘ2／２）であり、さらに連立方程式データの処理、シンドロームを求める処理がある。通常に使用されるＬＤＰＣ符号では、ｘが数百以上、ｄｅｇ／（１−Ｒ）が数十程度であることから、解法１）は解法２）の数倍〜数十倍の計算量を要することになる。計算量を要するということは、処理時間が掛かるか、あるいは処理時間を削減するための復号リソースが多く必要になるということである。
【００２０】
但し、解法１）であれば符号の能力に応じた訂正能力を得ることができるが、解法２）の訂正能力は解法１）と比較して劣っている。簡単な例を図９に示す。図９では、受信語のシンボルｒa、ｒb、ｒc、ｒdが消失であり、検査行列Ｈの行のそれぞれを個別にしか参照していない解法２）では、このようなケースは訂正できない。しかし、解法１）では、各行から計算されるシンドロームの値がｓw、ｓx、ｓy、ｓzであるとして、ｒa＝ｓw＋ｓy＋ｓz、ｒb＝ｓx＋ｓy＋ｓz、ｒc＝ｓw＋ｓx＋ｓy、ｒd＝ｓw＋ｓx＋ｓy＋ｓz、として各シンボルの値を復元することが可能である。このように解法１）では、解法２）とは異なって、行と行の関係も参照しているので、復号処理は非常に複雑になる。
【非特許文献１】R. G. Gallager, “Low density parity check codes”, in Research Monograph series. Cambridge, MIT Press (1963)
【非特許文献２】D. J. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Trans. Inform. Theory, vol.45, pp.399-431 (1999)
【非特許文献３】R. M. Tanner, “A recursive approach to low complexity codes”, IEEE Trans. Inform. Theory, vol.27, pp.533-547 (1981)
【発明の開示】
【発明が解決しようとする課題】
【００２１】
しかしながら、前記従来の２種類の解法は、解法１）は、訂正能力は優れているが、非常に計算量を要するし、復号グラフに基づいた解法２）は、計算量はあまり要しないが、訂正能力は解法１）と比較して劣っているという課題がある。
【００２２】
本発明は、上記課題を解決するために、訂正能力を高く維持しつつ、計算量を低減することができる復号装置を提供することを目的とする。
【課題を解決するための手段】
【００２３】
上記目的を達成するために、本発明に係る復号装置は、線形符号の誤りを前記線形符号に対応した検査行列を用いて訂正する復号装置であって、複数のシンボルで構成された受信語と前記受信語の中で誤りがあるシンボルの位置を示す消失位置情報とが入力され、前記検査行列に対応した復号方法を示す復号グラフに基づいて、前記受信語の誤りがあるシンボルの中で訂正可能なシンボルが訂正された第１の受信語と、前記訂正されたシンボルの位置が前記消失位置情報に反映された第１の消失位置情報とを生成する第１の復号部と、前記生成された第１の受信語と第１の消失位置情報と前記検査行列とから、誤りがあるシンボルで構成される消失ベクトルと前記消失ベクトルの係数となる係数行列とを抽出し、行を入れ替えれば三角行列になる入替三角行列へ前記係数行列を変換する処理を行う変換行列を生成し、前記検査行列に基づいて前記第１の受信語から第１のシンドロームを生成する行列処理部と、前記生成された変換行列と第１のシンドロームとから、前記第１の受信語の誤りがあるシンボルが訂正された第２の受信語と、前記第１の消失位置情報に前記訂正されたシンボルの位置が反映された第２の消失位置情報とを生成し、前記第１のシンドロームを前記訂正されたシンボルが反映された第２のシンドロームに補正する行列復号部と、前記生成された第２の受信語と第２の消失位置情報とから、前記第２の受信語の訂正可能なシンボルが前記復号グラフに基づいて訂正された第３の受信語と、前記訂正されたシンボルの位置が前記第２の消失位置情報に反映された第３の消失位置情報とを生成する第２の復号部とを備える。
【００２４】
これによれば、第１の復号部及び第２の復号部による誤りの訂正処理と、行列処理部及び行列復号部による誤りの訂正処理との２種類の訂正処理がなされる。ここで、第１の復号部及び第２の復号部による誤りの訂正処理は、計算量が少ない復号グラフに基づいた訂正処理方法である。また、行列処理部及び行列復号部による誤りの訂正処理は、復号グラフに基づいた訂正処理では訂正できない誤りを訂正することができる。このため、これら２種類の訂正処理を組み合わせて復号処理が行われることで、訂正能力を高く維持しつつ、計算量を低減することができる。
【００２５】
また、本発明は、このような復号装置として実現できるだけでなく、その装置を構成する処理部をステップとする方法として実現したりすることができる。さらに、本発明は、それらステップをコンピュータに実行させるプログラムとして実現したり、そのプログラムを記録したコンピュータ読み取り可能なＣＤ−ＲＯＭなどの記録媒体として実現したり、そのプログラムを示す情報、データ又は信号として実現したりすることもできる。そして、それらプログラム、情報、データ及び信号は、インターネット等の通信ネットワークを介して配信してもよい。
【発明の効果】
【００２６】
以上のように、本発明に係る復号装置によれば、復号グラフに基づいた訂正処理と復号グラフでは訂正することができない誤りを訂正することができる訂正処理とを組み合わせて復号処理が行われることで、訂正能力を高く維持しつつ、計算量を低減することができる。
【発明を実施するための最良の形態】
【００２７】
以下に、本発明の実施の形態について、図面を参照しながら説明する。
【００２８】
（実施の形態１）
図１は、本発明の実施の形態１における復号装置１０の機能的な構成の一例を示すブロック図である。図１に示すように、実施の形態１の復号装置１０は、第１の復号部１１、行列処理部１２、行列復号部１３、第２の復号部１４、終了判断部１５、及び選択部１６を備えている。復号装置１０は、ＣＰＵ（Central Processing Unit）等を備え、必要なデータをメモリに入力してプログラムを実行し、データを出力するコンピュータである。
【００２９】
第１の復号部１１は、複数のシンボルで構成された受信語と受信語の中で誤りがあるシンボルの位置を示す消失位置情報とが入力され、所定の検査行列に対応した復号方法を示す復号グラフに基づいて、受信語の誤りがあるシンボルの中で訂正可能なシンボルが訂正された第１の受信語と、訂正されたシンボルの位置が消失位置情報に反映された第１の消失位置情報とを生成する。また、第１の復号部１１は、第１の受信語に誤りがあるシンボルが存在するか否かを判定する第１のフラグを生成する。
【００３０】
行列処理部１２は、第１の復号部１１が生成した第１の受信語と第１の消失位置情報と、検査行列とから、誤りがあるシンボルで構成される消失ベクトルと消失ベクトルの係数となる係数行列とを抽出し、行を入れ替えれば三角行列になる入替三角行列へ係数行列を変換する処理を行う変換行列を生成し、検査行列に基づいて第１の受信語から第１のシンドロームを生成する。また、行列処理部１２は、係数行列の入替三角行列への変換が可能であるか否かを判定する第２のフラグを生成する。
【００３１】
行列復号部１３は、行列処理部１２が生成した変換行列と第１のシンドロームとから、第１の受信語の誤りがあるシンボルが訂正された第２の受信語と、第１の消失位置情報に訂正されたシンボルの位置が反映された第２の消失位置情報とを生成し、第１のシンドロームを訂正されたシンボルが反映された第２のシンドロームに補正する。
【００３２】
第２の復号部１４は、行列復号部１３が生成した第２の受信語と第２の消失位置情報とから、第２の受信語の訂正可能なシンボルが復号グラフに基づいて訂正された第３の受信語と、訂正されたシンボルの位置が第２の消失位置情報に反映された第３の消失位置情報とを生成する。また、第２の復号部１４は、第３の受信語に誤りがあるシンボルが存在するか否かを判定する第３のフラグを生成するとともに、第３の受信語に誤りがあるシンボルが存在していると判定される場合に、第２のシンドロームに誤りが訂正されたシンボルを反映することで、第２のシンドロームを第３のシンドロームに補正する。
【００３３】
終了判断部１５は、線形符号の誤り訂正を終了するか否かを判断する。
【００３４】
選択部１６は、第１の受信語と第１の消失位置情報と第１のシンドロームとを行列復号部１３に出力するか、第３の受信語と第３の消失位置情報と第３のシンドロームとを行列復号部１３に出力するかを選択する。
【００３５】
ここで、第１の受信語、第１の消失位置情報、第１のシンドローム、第２の受信語、第２の消失位置情報、第２のシンドローム、第３の受信語、第３の消失位置情報、及び第３のシンドロームなどの各データは、各処理部で生成された後にメモリに書き込まれ、各処理部は、必要なデータを当該メモリから読み出して、各処理を行う。
【００３６】
図２は、復号装置１０が実行する復号の処理を示すフローチャートである。
【００３７】
まず、第１の復号部１１に受信語と消失位置情報とが入力される（Ｓ１０２）。
【００３８】
次に、第１の復号部１１は、復号グラフに基づいて、受信語の誤りがあるシンボルの中で訂正可能な全てのシンボルを訂正し、第１の受信語を生成する（Ｓ１０４）。また、第１の復号部１１は、訂正されたシンボルの位置を消失位置情報に反映させて第１の消失位置情報を生成する（Ｓ１０４）。
【００３９】
そして、第１の復号部１１は、第１の受信語に誤りがあるシンボルが存在するか否かを判定する第１のフラグを生成する（Ｓ１０６）。
【００４０】
第１のフラグで第１の受信語に誤りが存在すると判定された場合（Ｓ１０６でＹＥＳ）、行列処理部１２は、第１の受信語と第１の消失位置情報と検査行列とから、誤りがあるシンボルで構成される消失ベクトルと消失ベクトルの係数となる係数行列とを抽出する（Ｓ１０８）。具体的には、行列処理部１２は、第１の消失位置情報に基づく誤りがあるシンボルで構成されるベクトルである消失ベクトルと、検査行列のうち消失ベクトルに対応する列で構成される係数行列とを抽出する。
【００４１】
そして、行列処理部１２は、係数行列の入替三角行列への変換が可能であるか否かを判定する第２のフラグを生成する（Ｓ１１０）。
【００４２】
具体的には、行列処理部１２は、係数行列の入替三角行列への変換の処理を行い、当該変換の処理が成功したか失敗したかを判断することによって、係数行列の入替三角行列への変換が可能であるか否かを判定する第２のフラグを生成する。
【００４３】
行列処理部１２は、第２のフラグで入替三角行列への変換が可能であると判定された場合（Ｓ１１０でＹＥＳ）、入替三角行列へ係数行列を変換する処理を行う変換行列を生成し、検査行列に基づいて第１の受信語から第１のシンドロームを生成する（Ｓ１１４）。具体的には、行列処理部１２は、検査行列と第１の受信語とを乗じて算出される第１のシンドロームを生成する。また、行列処理部１２は、消失ベクトルと入替三角行列とを乗じた値が第１のシンドロームと変換行列とを乗じた値と同じになるように算出される変換行列を生成する。
【００４４】
そして、行列復号部１３は、変換行列と第１のシンドロームとから、第２の受信語と第２の消失位置情報とを生成し、第１のシンドロームを第２のシンドロームに補正する（Ｓ１１６）。具体的には、行列復号部１３は、入替三角行列の行のうち零でない要素が１つのみの行を選択し、当該選択された行に対応する変換行列の行と第１のシンドロームとを乗じた値を計算することで、誤りがあるシンボルの値を算出するとともに、第２の受信語と第２の消失位置情報とを生成する。また、行列復号部１３は、第１のシンドロームに誤りが訂正されたシンボルを反映することで、第１のシンドロームを第２のシンドロームに補正する。
【００４５】
次に、第２の復号部１４は、第２の受信語と第２の消失位置情報とから、第２の受信語の訂正可能な全てのシンボルが復号グラフに基づいて訂正された第３の受信語と、訂正されたシンボルの位置が第２の消失位置情報に反映された第３の消失位置情報とを生成する（Ｓ１１８）。
【００４６】
次に、第２の復号部１４は、第３の受信語に誤りがあるシンボルが存在するか否かを判定する第３のフラグを生成する（Ｓ１２０）。
【００４７】
第２の復号部１４は、第３のフラグで第３の受信語に誤りが存在すると判定された場合（Ｓ１２０でＹＥＳ）、第２のシンドロームに誤りが訂正されたシンボルを反映することで、第２のシンドロームを第３のシンドロームに補正する（Ｓ１２２）。
【００４８】
そして、終了判断部１５は、線形符号の誤り訂正が終了していないと判断し、第３の受信語と第３の消失位置情報と第３のシンドロームとを、それぞれ、第１の受信語と第１の消失位置情報と第１のシンドロームとして行列復号部１３に出力する。これにより、行列復号部１３は、第２の受信語と第２の消失位置情報とを生成し、第１のシンドロームを第２のシンドロームに補正する（Ｓ１１６）。
【００４９】
また、終了判断部１５は、第１のフラグで第１の受信語に誤りが存在しないと判定された場合には（Ｓ１０６でＮＯ）、線形符号の誤り訂正の完了による終了と判断して、第１の受信語を誤り訂正済みの受信語として出力する（Ｓ１２４）。また、終了判断部１５は、第２のフラグで入替三角行列への変換が不可であると判定された場合には（Ｓ１１０でＮＯ）、線形符号の誤り訂正の中止による終了と判断して、第１の受信語と第１の消失位置情報とを誤りが残留している受信語と残留している誤りの位置情報として出力する（Ｓ１２６）。また、終了判断部１５は、第３のフラグで第３の受信語に誤りが存在しないと判定された場合には（Ｓ１２０でＮＯ）、線形符号の誤り訂正の完了による終了と判断して、第３の受信語を誤り訂正済みの受信語として出力する（Ｓ１２８）。このようにして、復号の処理が終了する。
【００５０】
図３Ａ〜図３Ｃは、復号装置１０の復号処理の一例を具体的に説明する図である。ここでは、復号する符号の符号長をｎ、データ数をｋとして説明する。また、入替三角行列は、上三角行列であるとする。
【００５１】
第１の復号部１１は、復号装置１０に入力される受信語の情報と、消失位置の情報から、従来例で解法２として説明したアルゴリズムで訂正し、訂正した結果として、第１の受信語、第１の受信語の消失位置情報、第１のフラグを出力する。この段階で、全ての消失が訂正できた場合には、第１の受信語はそのまま復号装置１０の出力となり、訂正できなかった消失が残った場合には、行列処理部１２や行列復号部１３が、第１の受信語、第１の受信語の消失位置情報を使用して、次の処理を実行する。第１のフラグは、全ての消失が訂正できたかどうかを示すフラグである。残った消失の個数をｘ個とする。
【００５２】
行列処理部１２は、図３Ａに示すように、入力される第１の受信語に、（ｎ−ｋ）行ｎ列の検査行列Ｈをかけて、第１のシンドロームＳ＝（ｓ0，ｓ1，…，ｓ(n-k-1)）を得て、これを出力する。なお、ここでは第１の受信語及び検査行列Ｈの各要素は２進数の値であり、計算においては排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）処理が行われる。符号語に検査行列Ｈをかけて得られるのは０（ベクトル）であり、第１のシンドロームは消失の大きさから得られるものであるから、第１のシンドロームの値は、検査行列Ｈから消失の位置に対応する列のみを残した係数行列Ｈ’と消失ベクトルＺ＝（ｚ0，ｚ1，…，ｚ(i-1)，ｚi，ｚ(i+1)，…，ｚ(x-1)）をかけて得られる値と一致する。
【００５３】
行列処理部１２は、消失の値を得るために、さらに、これらの消失の値をｘ個の変数とする１次ｘ元連立方程式Ｈ’・ＺT＝ＳTを変形する。具体的には、図３Ｂに示すように、方程式Ｈ’・ＺT＝ＳTをＨ’・ＺT＝Ｉ・ＳTと置き直し（Ｉは、（ｎ−ｋ）次の単位行列とする）、左辺の係数行列Ｈ’を変換して、上三角行列Ｈ”を生成する。変換は係数行列の行同士の加算と行の入替えで実行される。この左辺の変換と同時に、右辺の単位行列Ｉにも左辺の変換と同じ変換を行なって、変換行列Ｔを生成し、これを出力する。この変換行列Ｔは、Ｈ”・ＺT＝Ｔ・ＳTを満たしている。
【００５４】
第２のフラグは、三角行列化が可能であったかどうかを示すフラグである。三角行列化ができなかった場合は、この符号語の訂正は不可能である。第１の受信語と、第１の受信語の消失位置情報を、訂正終了後の受信語と消失位置情報として、復号装置１０からの出力とする。
【００５５】
選択部１６のそれぞれは、行列処理部１２の処理終了後には、行列処理部１２の出力である、第１の受信語、第１の受信語の消失位置情報、第１のシンドロームを出力し、それ以降は、第２の復号部１４からフィードバックされてくる第３の受信語、第３の受信語の消失位置情報、第３のシンドロームを出力する。
【００５６】
行列復号部１３は、まず上三角行列Ｈ”の行のうち、重みが１（要素が１つだけ非零で、残りが全て零）の行を選択する。既に三角行列化してあるので、右端の要素以外は全て零の行は存在する。図３Ｃに示しているが、上記の１次ｘ元連立方程式においてこの行に対応する式の左辺は、ｉ番目の要素が０である行の場合、ｚ(i-1)、即ちｉ番目の消失の値となり、対応する右辺の値を計算すれば消失の値が判明し、そのシンボルを訂正できる。受信語をＲ＝（ｒ0，ｒ1，…，ｒ(n-1)）として、訂正する消失がｘi番目のシンボルであれば、Ｒに訂正パターンＥi＝（［ｘi−１個の０］，ｚ(i-1)，［ｎ−ｘi個の０］）を加算して、訂正できる。
【００５７】
消失を訂正すれば、その消失の情報を上記の連立方程式から排除し、変数を１個少なくした連立方程式に変形する。左辺については、消失ベクトルＺからｚ(i-1)をなくして次元数を１減らし、上三角行列Ｈ”についても、ｚ(i-1)に対応する列を削除したと見なす。右辺については、検査行列ＨにＥiTを掛けた値をシンドロームＳに加算すれば、消失が減った状態のシンドロームに補正される。実際の処理としては、以降の処理には上三角行列Ｈ”の情報は使用しないので、上三角行列Ｈ”の情報を補正する必要はない。
【００５８】
行列復号部１３は、このように訂正された結果を、第２の受信語、第２の受信語の消失位置情報、第２のシンドロームとして出力する。
【００５９】
なお、行列復号部１３で訂正する消失は１個であっても複数個であっても構わない。また符号のパラメータである符号長やパリティ数や次数、その時点で訂正されていないパリティ数などで、訂正する消失の個数を設定することも可能である。
【００６０】
第２の復号部１４は、入力される第２の受信語の情報と、第２の受信語の消失位置情報の情報から、従来例で解法２として説明したアルゴリズムで訂正し、訂正した結果として、第３の受信語、第３の受信語の消失位置情報、第３のフラグを出力する。
【００６１】
また、第２の復号部１４においても、行列復号部１３での処理と同様に、受信語のｘi番目のシンボルが消失であり、その値がｚ(i-1)であったとして、訂正パターンをＥi＝（［ｘi−１個の０］，ｚ(i-1)，［ｎ−ｘi個の０］）として、検査行列ＨにＥiTを掛けた値をシンドロームＳに加算して、シンドロームを補正する。
【００６２】
第２の復号部１４で、複数の消失を訂正した場合に、シンドロームの補正は、消失１個を訂正する毎に行なっても、あるいは複数の消失を訂正した後にまとめて行なっても、どちらでも良い。
【００６３】
また、第２の復号部１４で、残っていた消失が全て訂正された場合には、シンドロームの補正を行なう必要はない。
【００６４】
全ての消失が訂正できた場合には、第３の受信語はそのまま復号装置１０の出力となり、訂正できなかった消失が残った場合には、行列復号部１３が、第３の受信語、第３の受信語の消失位置情報、第３のシンドロームをフィードバックして、次の処理を実行する。
【００６５】
第３のフラグは、全ての消失が訂正できたかどうかを示すフラグである。
【００６６】
制御信号は、復号装置１０そのものや各部での受信語情報・消失情報の入出力、選択の指示や、各部における処理実行の指示を行なう信号である。
【００６７】
終了判断部１５は、復号装置１０の入力指示、第１のフラグ、第２のフラグ、第３のフラグ、各部の状態に基づいて、制御信号とフラグ情報を生成する。
【００６８】
以上のように構成された復号装置１０において、第１の復号部１１及び第２の復号部１４による誤りの訂正処理と、行列処理部１２及び行列復号部１３による誤りの訂正処理との２種類の訂正処理がなされる。ここで、第１の復号部１１及び第２の復号部１４による誤りの訂正処理は、計算量が少ない復号グラフに基づいた訂正処理方法である。また、行列処理部１２及び行列復号部１３が復号グラフでは求められない消失の値のみを行列式による解法で計算することにより、復号に必要な計算量を削減することが可能になる。また、復号グラフによる訂正が破綻する回数は１度とは限らないが、最初に一度行列式の係数計算などを行なっておけば、２度目以降は最初に計算した値をそのまま利用できるような補正を行なうことにより、行列式による解法で必要な計算量を削減することが可能になる。これらの手法により、訂正能力を高く維持しつつ、計算量を低減することができ、復号の高速化を可能にした。
【００６９】
なお、検査行列Ｈは、符号ごとに固有の行列であるので、使われている符号に合わせた検査行列Ｈの情報を選択するもしくは入力する機能を備えれば、複数の符号を扱う復号装置１０を構成できることは明らかである。
【００７０】
また、上三角行列に変換するとしたが、下三角行列に変換しても、同様のアルゴリズムの適用が可能である。また、三角化した部分を、上詰めもしくは下詰めするなど、行列の一部分に集める処理があってもなくても、同等の効果が得られることは明らかである。つまり、上三角行列でなくても、行を入れ替えれば三角行列になる行列であればよい。
【００７１】
また、本発明の演算は、全て符号の定義に従った演算であり、例えばガロア体ＧＦ（２）やその拡大体上の符号であれば、加算は排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）演算のことである。
【００７２】
伝送されたパケット受信が遅れて、復号を始めてから到着した場合には、それも訂正できたパケット扱いで処理できる。
【００７３】
符号長、データ数や検査行列Ｈの情報などの符号に関するパラメータは、常に同じ符号を扱う復号装置１０では最初から各部に内蔵していても良いし、複数の符号を扱う復号装置１０では制御信号として符号の選択を指示する構成にすることも可能であるし、任意の符号を扱う復号装置１０であればこれらのパラメータを制御信号として外部から読み込む構成とすることも可能である。
【００７４】
（実施の形態２）
図４は、本発明の実施の形態２における行列処理部１２の機能的な構成の一例を示すブロック図である。図４に示すように、実施の形態２の行列処理部１２は、係数抽出部２１、三角行列生成部２２、変換行列生成部２３、及びシンドローム生成部２４を備えている。
【００７５】
係数抽出部２１は、第１の消失位置情報に基づく誤りがあるシンボルで構成されるベクトルである消失ベクトルＺと、検査行列Ｈのうち消失ベクトルＺに対応する列で構成される係数行列Ｈ’とを抽出する。
【００７６】
三角行列生成部２２は、係数行列Ｈ’を上三角行列Ｈ”へ変換する。
【００７７】
シンドローム生成部２４は、検査行列Ｈと第１の受信語とを乗じて算出される第１のシンドロームＳを生成する。
【００７８】
変換行列生成部２３は、消失ベクトルＺと上三角行列Ｈ”とを乗じた値が第１のシンドロームＳと変換行列Ｔとを乗じた値と同じになるように算出される変換行列Ｔを生成する。
【００７９】
この行列処理部１２が行う処理について、以下に詳細に説明する。
【００８０】
まず、係数抽出部２１は、消失の値をｘ個の変数とする１次ｘ元連立方程式の係数を、検査行列Ｈから消失の位置にある列以外の列を削除した係数行列Ｈ’として求めて、（ｎ−ｋ）行ｘ列の係数情報として出力する。
【００８１】
三角行列生成部２２は、入力された係数情報をから係数行列Ｈ’を上三角行列Ｈ”に変換する処理を行なう。また、三角行列化が可能であったかどうかを示す第２のフラグは、三角行列生成部２２から出力される。
【００８２】
変換行列生成部２３は、（ｎ−ｋ）次の単位行列Ｉ(n-k)に、係数行列Ｈ’を上三角行列Ｈ”に変換する処理と同じ処理を行なって変換行列Ｔを生成する。そのために、三角行列生成部２２は、変換処理に関する処理情報を、変換行列生成部２３に出力する。処理情報は、ａ行とｂ行の入替えや、ｃ行にｄ行を加算といった処理を逐一通知することも可能であるし、処理終了後に一括して通知することも可能である。
【００８３】
シンドローム生成部２４は、入力される第１の受信語に、（ｎ−ｋ）行ｎ列の検査行列Ｈをかけて、第１のシンドロームＳ＝（ｓ0，ｓ1，…，ｓ(n-k-1)）を得て、これを出力する。
【００８４】
以上のように構成された行列処理部１２において、三角行列化処理と並行して、変換処理を変換行列の形で保持することにより、シンドロームの値を変形せずに残しておき、後の処理でシンドロームの値を利用する必要が生じた時にシンドロームの値を再計算する必要がないようにすることが可能になった。
【００８５】
（実施の形態３）
図５Ａ及び図５Ｂは、本発明の実施の形態３における行列復号部１３の機能的な構成の一例を示すブロック図である。図５Ａ及び図５Ｂに示すように、実施の形態３の行列復号部１３は、消失値計算部３１、訂正部３２、及びシンドローム補正部３３を備えている。
【００８６】
消失値計算部３１は、上三角行列Ｈ”の行のうち零でない要素が１つのみの行を選択し、当該選択された行に対応する変換行列Ｔの行と第１のシンドロームＳとを乗じた値を計算することで、誤りがあるシンボルの値を算出するとともに、第２の消失位置情報を生成する。
【００８７】
訂正部３２は、算出されたシンボルに基づいて、第２の受信語を生成する。
【００８８】
シンドローム補正部３３は、算出されたシンボルに基づいて、第１のシンドロームＳを第２のシンドロームに補正する。
【００８９】
この行列復号部１３が行う処理について、以下に詳細に説明する。
【００９０】
消失値計算部３１は、上三角行列Ｈ”の行のうち、重みが１の行を選択し、当該選択された行に対応する変換行列Ｔの行と第１のシンドロームＳとを乗じた値を計算して、１個の消失の値を得る。また、行列復号部１３に入力される訂正途中の受信語の消失位置情報を修正しておく。なお、消失の値が訂正されれば、上三角行列Ｈ”の列のうち、訂正された消失の位置に対応する列の要素は全て０とみなすことができるので、重みが１である行は常に存在する。
【００９１】
訂正部３２は、行列復号部１３に入力される訂正途中の受信語の、求められた消失の位置にあるシンボルに、求められた消失の値を加算して、訂正を行なう。通常は、消失の位置にあるシンボルの値は、０として復号処理を開始するので、その場合は代入するだけでよい。
【００９２】
シンドローム補正部３３は、訂正パターンＥi＝（［ｘi−１個の０］，ｚ(i-1)，［ｎ−ｘi個の０］）によるシンドロームの値への影響を相殺するために、検査行列ＨにＥiTを掛けた値をシンドロームＳに加算し、補正したシンドロームを出力する。
【００９３】
図５Ａの構成は、１個の消失を訂正する手段のブロック図である。ここで、行列復号部１３は、生成された第２の受信語と第２の消失位置情報と第２のシンドロームとを、それぞれ、第１の受信語と第１の消失位置情報と第１のシンドロームとして入力することにしてもよい。
【００９４】
つまり、この消失値計算部３１で１個の消失の値を計算すれば、この後の第２の復号部１４で、必ず残りの消失を訂正できるとは限らないので、複数個の消失をまとめて訂正しようとする場合には、図５Ｂに示すように、選択部３４により、出力する各データ・情報を入力側にフィードバックして、消失値計算部３１、訂正部３２に入力するような構成が可能である。訂正する消失の数は、復号装置１０として固定値であっても可変であっても良い。また可変にする場合、訂正する個数を、制御信号を用いて指示することも可能である。
【００９５】
以上のように構成された行列復号部１３において、行列式を解く手法に基づく復号アルゴリズムを一部導入することにより、第１の復号部１１では、既に訂正できる消失は全て訂正されており、かつ訂正できない消失が残留していた状態であった受信語の消失訂正を続けることが可能になった。
【００９６】
（実施の形態４）
図６Ａ及び図６Ｂは、本発明の実施の形態４における第２の復号部１４の機能的な構成の一例を示すブロック図である。図６Ａに示すように、実施の形態４の第２の復号部１４は、第３の復号部４１、訂正した消失位置の記憶部４２、及びシンドローム補正部４３を備えている。
【００９７】
第３の復号部４１は、第２の復号部１４に入力される第２の受信語、第２の受信語の消失位置情報から、従来例で解法２として説明したアルゴリズムで訂正し、訂正した結果として、第３の受信語、第３の受信語の消失位置情報、第３のフラグを出力する。この段階で、全ての消失が訂正できた場合には、第３の受信語はそのまま復号装置１０の出力となり、訂正できなかった消失が残った場合には、行列復号部１３にフィードバックされる。第３のフラグは、全ての消失が訂正できたかどうかを示すフラグである。
【００９８】
第３の復号部４１で復号が終了しなかった場合に、引続き行列復号部１３による復号を実行するためには、今第３の復号部４１で訂正したシンボルに関してシンドロームを補正しておく必要がある。そこで、第３の復号部４１は、訂正できた全ての消失の位置の情報を訂正した消失位置の記憶部４２に出力し、訂正した消失位置の記憶部４２は、それらの位置の情報を記憶する。シンドローム補正部４３は、訂正した消失位置の記憶部４２に記憶された位置情報に基づき、入力された第２のシンドロームを補正して第３のシンドロームとして出力する。
【００９９】
図６Ａは、第３の復号部４１でａ個の消失を訂正した後に、ａ個の消失に関するシンドロームの補正をシンドローム補正部４３で行なう構成である。また、第３の復号部４１で全ての消失が訂正できれば、シンドロームの補正は不要であるので、実行しなければ復号処理全体としての高速化に寄与する。
【０１００】
また、図６Ｂに示すように、実施の形態４の第２の復号部１４は、グラフベースの１消失復号部４５、シンドローム補正部４３、及び選択部４６、４７を備えている。
【０１０１】
グラフベースの１消失復号部４５も、従来例で解法２として説明したアルゴリズムで消失を計算するが、訂正できる消失を全て訂正するのではなく、１個の消失を訂正する復号部である。
【０１０２】
図６Ｂは、グラフベースの１消失復号部４５で１個の消失を訂正し、その消失に関するシンドロームの補正をシンドローム補正部３３で行なうことを、選択部４６、４７で、入力されるデータ・情報とフィードバックされる出力データ・情報とを切り替えながら繰り返す構成である。
【０１０３】
つまり、第２の復号部１４は、生成された前記第３の受信語と第３の消失位置情報と第３のシンドロームとを、それぞれ、第２の受信語と第２の消失位置情報と第２のシンドロームとして入力する。
【０１０４】
なお、図６Ｂに示した復号部１４においても、図２に示された各ステップ（Ｓ１１８〜１２２）の処理が行われる。
【０１０５】
以上のように構成された第２の復号部１４において、復号グラフに基づいた復号をしながら行列式を解いて復号する手法に必要なシンドロームの補正を行なうことにより、ここで復号できなかった場合にシンドロームの計算と消失の値を変数とする連立方程式の係数行列を上三角行列に変換する処理を再度行なう必要をなくすかことが可能になった。
【０１０６】
以上、本発明に係る復号装置について、上記実施の形態を用いて説明したが、本発明は、これに限定されるものではない。
【０１０７】
つまり、今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【０１０８】
例えば、本実施の形態では、第１の受信語及び検査行列Ｈなどの各要素は２進数であることとしたが、３進数などであってもよい。
【０１０９】
また、本実施の形態では、第１の復号部１１などの各構成要素は、ソフトウェアにより構成されていることとしたが、専用のハードウェアにより構成されていてもよい。つまり、ブロック図（図１、図４〜図６Ｂなど）の各機能ブロックは、典型的には集積回路であるＬＳＩとして実現されていてもよい。なお、これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。
【産業上の利用可能性】
【０１１０】
本発明に係る復号装置、復号方法、及び復号プログラムは、訂正能力を損なわずに処理速度を高速化することができ、ネットワーク伝送時のパケットロスのような消失訂正の用途に有用である。
【図面の簡単な説明】
【０１１１】
【図１】本発明の実施の形態１における復号装置の機能的な構成の一例を示すブロック図である。
【図２】復号装置が実行する復号の処理を示すフローチャートである。
【図３Ａ】復号装置の復号処理の一例を具体的に説明する図である。
【図３Ｂ】復号装置の復号処理の一例を具体的に説明する図である。
【図３Ｃ】復号装置の復号処理の一例を具体的に説明する図である。
【図４】本発明の実施の形態２における行列処理部の機能的な構成の一例を示すブロック図である。
【図５Ａ】本発明の実施の形態３における行列復号部の機能的な構成の一例を示すブロック図である。
【図５Ｂ】本発明の実施の形態３における行列復号部の機能的な構成の一例を示すブロック図である。
【図６Ａ】本発明の実施の形態４における第２の復号部の機能的な構成の一例を示すブロック図である。
【図６Ｂ】本発明の実施の形態４における第２の復号部の機能的な構成の一例を示すブロック図である。
【図７】伝送パケット生成の説明図である。
【図８Ａ】復号グラフに基づく復号アルゴリズムの説明図である。
【図８Ｂ】復号グラフに基づく復号アルゴリズムの説明図である。
【図８Ｃ】復号グラフに基づく復号アルゴリズムの説明図である。
【図８Ｄ】復号グラフに基づく復号アルゴリズムの説明図である。
【図８Ｅ】復号グラフに基づく復号アルゴリズムの説明図である。
【図８Ｆ】復号グラフに基づく復号アルゴリズムの説明図である。
【図８Ｇ】復号グラフに基づく復号アルゴリズムの説明図である。
【図９】解法１と解法２の訂正能力の差の説明図である。
【符号の説明】
【０１１２】
１１  第１の復号部
１２  行列処理部
１３  行列復号部
１４  第２の復号部
１５  終了判断部
１６  選択部
２１  係数抽出部
２２  三角行列生成部
２３  変換行列生成部
２４  シンドローム生成部
３１  消失値計算部
３２  訂正部
３３  シンドローム補正部
３４  選択部
４１  第３の復号部
４２  訂正した消失位置の記憶部
４３  シンドローム補正部
４５  グラフベースの１消失復号部
４６、４７  選択部
【図１】
2010041677.tif 000003
【図２】
2010041677.tif 000004
【図３Ａ】
2010041677.tif 000005
【図３Ｂ】
2010041677.tif 000006
【図３Ｃ】
2010041677.tif 000007
【図４】
2010041677.tif 000008
【図５Ａ】
2010041677.tif 000009
【図５Ｂ】
2010041677.tif 000010
【図６Ａ】
2010041677.tif 000011
【図６Ｂ】
2010041677.tif 000012
【図７】
2010041677.tif 000013
【図８Ａ】
2010041677.tif 000014
【図８Ｂ】
2010041677.tif 000015
【図８Ｃ】
2010041677.tif 000016
【図８Ｄ】
2010041677.tif 000017
【図８Ｅ】
2010041677.tif 000018
【図８Ｆ】
2010041677.tif 000019
【図８Ｇ】
2010041677.tif 000020
【図９】
2010041677.tif 000021