(57)【要約】【課題】計算量を削減することができる符号化装置を提供する。【解決手段】線形符号の符号化装置であって、入力データである第１のデータから少なくとも１個のパリティを生成行列を用いて生成し第１の符号化データを出力するパリティ生成部１１と、線形符号の検査行列の全ての行の中から、行の非零の要素に対応する入力された第２のデータのパリティのうち生成されていないパリティが１個である行を選択する行選択部１３と、当該行に対応するパリティを消失訂正処理を行なって生成し第２の符号化データを出力する消失訂正部１４と、第１の符号化データ又は第２の符号化データを第２のデータとして出力する第１の選択部１５とを備え、消失訂正部１４は、線形符号化が終了するまで、出力された第２の符号化データを第１の選択部１５に出力し、線形符号化が終了した場合に、出力された第２の符号化データを符号語として出力することで、符号語を生成する。【選択図】図１
2010034887.tif 000002
【特許請求の範囲】
【請求項１】
入力データに対して線形符号化によって符号語を生成する符号化装置であって、
前記入力データが第１のデータとして入力され、前記第１のデータから少なくとも１個のパリティを前記線形符号の生成行列を用いて生成し、前記第１のデータに当該生成されたパリティが付加された第１の符号化データを出力するパリティ生成部と、
第２のデータが入力され、前記線形符号の検査行列の全ての行の中から、前記行の非零の要素に対応する前記第２のデータのパリティのうち生成されていないパリティが１個である行を選択する行選択部と、
前記行選択部が選択した行を用いて、前記生成されていないパリティを消失として訂正処理を行なって生成し、当該生成されたパリティを前記第２のデータに付加して第２の符号化データを出力する消失訂正部と、
前記第１の符号化データが入力された場合には前記第１の符号化データを前記第２のデータとして出力し、前記第２の符号化データが入力された場合には前記第２の符号化データを前記第２のデータとして出力する第１の選択部とを備え、
前記消失訂正部は、線形符号化が終了するまで、出力された前記第２の符号化データを前記第１の選択部に出力し、線形符号化が終了した場合に、出力された前記第２の符号化データを前記符号語として出力することで、前記符号語を生成する
ことを特徴とする符号化装置。
【請求項２】
さらに、
前記第２のデータが入力された場合には前記第２のデータを前記第１のデータとして前記パリティ生成部に出力する第２の選択部と、
前記行選択部が選択することができる前記検査行列の行が存在するか否かを判断する検査行列判断部と、
前記行選択部が選択する行が存在しないと判断された場合に、前記第１の選択部が前記第２の選択部に前記第２のデータを出力するように切り替える切替部とを備え、
前記パリティ生成部は、前記第２の選択部に前記第２のデータが入力された場合、前記第２の選択部から入力される前記第１のデータから少なくとも１個のパリティを生成し、前記第１のデータに当該生成されたパリティが付加された第１の符号化データを出力する
ことを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記パリティ生成部が生成するパリティは、前記行選択部が少なくとも１以上の前記検査行列の行を選択するように定められる
ことを特徴とする請求項１に記載の符号化装置。
【請求項４】
入力データに対して線形符号化によって符号語を生成する符号化方法であって、
コンピュータが、前記入力データを第１のデータとして入力し、前記第１のデータから少なくとも１個のパリティを前記線形符号の生成行列を用いて生成し、前記第１のデータに当該生成されたパリティが付加された第１の符号化データを出力するパリティ生成ステップと、
コンピュータが、前記線形符号の検査行列の全ての行の中から、前記行の非零の要素に対応する入力された第２のデータのパリティのうち生成されていないパリティが１個である行を選択する行選択ステップと、
コンピュータが、前記行選択ステップで選択された行を用いて、前記生成されていないパリティを消失として訂正処理を行なって生成し、当該生成されたパリティを前記第２のデータに付加して第２の符号化データを出力する消失訂正ステップと、
コンピュータが、前記第１の符号化データが入力された場合には前記第１の符号化データを前記第２のデータとして出力し、前記第２の符号化データが入力された場合には前記第２の符号化データを前記第２のデータとして出力する第１の選択ステップとを含み、
前記消失訂正ステップでは、線形符号化が終了するまで、出力された前記第２の符号化データを前記第１の選択部に出力し、線形符号化が終了した場合に、出力された前記第２の符号化データを前記符号語として出力することで、前記符号語を生成する
ことを特徴とする符号化方法。
【請求項５】
入力データに対して線形符号化によって符号語を生成するためのプログラムであって、
前記入力データが第１のデータとして入力され、前記第１のデータから少なくとも１個のパリティを前記線形符号の生成行列を用いて生成し、前記第１のデータに当該生成されたパリティが付加された第１の符号化データを出力するパリティ生成ステップと、
第２のデータが入力され、前記線形符号の検査行列の全ての行の中から、前記行の非零の要素に対応する前記第２のデータのパリティのうち生成されていないパリティが１個である行を選択する行選択ステップと、
前記行選択ステップで選択された行を用いて、前記生成されていないパリティを消失として訂正処理を行なって生成し、当該生成されたパリティを前記第２のデータに付加して第２の符号化データを出力する消失訂正ステップと、
前記第１の符号化データが入力された場合には前記第１の符号化データを前記第２のデータとして出力し、前記第２の符号化データが入力された場合には前記第２の符号化データを前記第２のデータとして出力する第１の選択ステップとをコンピュータに実行させ、
前記消失訂正ステップでは、線形符号化が終了するまで、出力された前記第２の符号化データを前記第１の選択部に出力し、線形符号化が終了した場合に、出力された前記第２の符号化データを前記符号語として出力することで、前記符号語を生成する
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号等の線形符号の符号化方法および符号化装置に関するものである。
【背景技術】
【０００２】
近年、訂正能力に優れた符号として、ＬＤＰＣ符号が有力視されている（例えば、非特許文献１〜３）。
【０００３】
ＩＰネットワークで、映像や音声のストリーミング伝送を行なう場合、リアルタイム性を維持するためにロストしたパケットを再送しないＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）で送るケースがある。そのような場合に、伝送経路に無線で伝送する区間があれば、ロストするパケットへの対策が必要になる。この対策としては、パケットをインターリーブして誤り訂正符号化することが考えられる。使用する誤り訂正符号としては、インターリーブ長を長くしやすいＬＤＰＣ符号も有力な候補である。
【０００４】
例えば、図５に示すように、ｐ×ｋビットのデータをｐビットずつのブロックとし、各ブロックから１ビットずつ得たｋビットのデータを符号化して、（ｎ−ｋ）ビットのパリティをつけていくと、トータルでｐ×（ｎ−ｋ）ビットのパリティが付加されることになり、これらのパリティで（ｎ−ｋ）ブロックとなる。伝送する時には、１個のブロックを１個のパケットのデータとして、それぞれヘッダ情報（ＵＤＰヘッダ／ＩＰヘッダなど）を付加し、ＩＰパケットを構成する。インターリーブは、１個のブロックから１ビットではなく複数のビットを集めて１個の符号語に符号化しても構わないし、複数のブロックから１ビットずつ集めて符号化しても構わない。
【０００５】
ここでは、使用する誤り訂正符号は、データは変形せずに、パリティを付加するだけの組織符号（Ｓｙｓｔｅｍａｔｉｃ  ｃｏｄｅ）として説明している。組織符号は、データが変換される非組織符号と比較すると、消失したパケットを訂正復元できなかった場合にも、受信できたパケットはそのまま使えるという利点がある。
【０００６】
伝送後に、ｎ個のパケットが揃わなくても、失われたパケットのデータを消失として、ｐ個の符号語の全てに誤り訂正処理を行なって、１ビットずつ復元していけば、元のブロックを復元することが可能である。ＩＰパケットはイーサネット（登録商標）ではパケット長の最大値が１，５００バイトとなっており、ＩＰヘッダ長は標準で２０バイト、ＵＤＰヘッダ長は８バイトであるので、データは最大１，４７２バイト＝１１，７７６ビットまで使用可能である。ストリーミング伝送を行なう場合は、１個のパケットに載せるデータはできるだけ多くし、ヘッダにより増加する伝送レートをできるだけ少なくして効率よく伝送することが要求されるので、１個のＩＰパケットに載せるデータは１０，０００ビット程度にはなると考えられる。１個のＩＰパケットが、符号の１個のシンボルにする場合、シンボル同士の加算は、１０，０００ビット程度の排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）を実行することになる。
【０００７】
線形符号は、ｋ行ｎ列の生成行列Ｇと、Ｇ・ＨT＝０となる（ｎ−ｋ）行ｎ列の検査行列Ｈにより、符号の構造を定義できる。Ｈ・ＧT＝０と記述しても良い。符号化の処理は、データ（ベクトル）Ｄ＝（ｄ0，ｄ1，…，ｄ(k-1)）に、生成行列Ｇをかけて、符号語（ベクトル）Ｃ＝（ｃ0，ｃ1，…，ｃ(n-1)）＝Ｄ・Ｇを得ることによりなされる。ここで、符号語についてＣ・ＨTを計算するとＣ・ＨT＝Ｄ・Ｇ・ＨT＝Ｄ・０＝０となる。
【０００８】
また、最大距離分離符号であり、記録装置などで良く用いられるＲｅｅｄ−Ｓｏｌｏｍｏｎ符号では、計算されていないパリティを消失として訂正処理を行なうことにより符号化する、という符号化手法が可能である。
【非特許文献１】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，…，ｄ(k-1)）から、ｒ個のシンボルのパリティを生成して、ｎ個のシンボルの符号語Ｃ＝（ｄ0，ｄ1，ｄ2，ｄ3，…，ｄ(k-2)，ｄ(k-1)，ｐ0，ｐ1，…，ｐ(r-2)，ｐ(r-1)）を出力する。なお、パリティシンボル数ｒは（ｎ−ｋ）である。
【００４８】
符号の生成行列Ｇは図３Ａに示すようにｋ行ｎ列の行列であり、符号語のデータ部を生成する左から１列目からｋ列目の部分（以下、データ位置部分と呼ぶ）は単位行列であり、符号語のパリティ部を生成する左から（ｋ＋１）列目からｎ列目の部分（以下、パリティ位置部分と呼ぶ）にあるｕ行ｖ列にある要素はｇ(u-1),(v-k-1)で表わしている。また、これに対応する検査行列Ｈは、図３Ｂに示すように（ｎ−ｋ）行ｎ列の行列である。なお、ここではデータＤ、生成行列Ｇ及び検査行列Ｈの各要素は２進数の値であり、計算においては排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）処理が行われる。
【００４９】
パリティ生成部１１は、図３Ａに示すような生成行列Ｇのパリティ位置部分からｑ列を選択し、ｊ＝０，１，…，（ｑ−１）として、パリティｐj＝ｇ0,j・ｄ0＋ｇ1,j・ｄ1＋ｇ2,j・ｄ2＋……＋ｇ(k-2),j・ｄ(k-2)＋ｇ(k-1),j・ｄ(k-1)を生成し、第１の符号化データとして出力する。ここで、生成行列Ｇのパリティ位置部分からのｑ列の選択は、行選択部１３が選択することができる検査行列Ｈの行が多く存在するように選択される。なお、このｑ列の選択は、任意の列が選択されることにしてもよい。
【００５０】
図３Ｂでは、検査行列Ｈにおいて、生成行列Ｇのデータ位置部分と生成済みのパリティの部分に対応する列を斜線部分で示している。
【００５１】
検査行列判断部１２は、まず、検査行列からデータ位置部分と、既に生成されたパリティに対応する列を除いた部分行列の行のうち、値が非零である要素の個数が１個である行が存在するかどうかを判断する。
【００５２】
値が非零である要素の個数が１個である行が１行でも存在すれば、切替部１７を行選択部１３側に切替えて、行選択部１３で、検査行列からデータ位置部分と、既に生成されたパリティに対応する列を除いた部分行列の行のうち、値が非零である要素の個数が１個である行を選択する。
【００５３】
選択された行が（ｉ＋１）行目であり、非零の要素がｈi,j（但しｊは（ｋ＋ｑ）〜（ｎ−１）のいずれかである）とすれば、Ｃ・ＨT＝０から（ｉ＋１）行目だけを抜き出した式
【数１】
2010034887.tif 000003
において、まだ生成されていないパリティｐq〜ｐ(r-1)の係数となるｈi,(k+q)〜ｈi,(n-1)のうち、ｈi,jのみが非零である。
【００５４】
消失訂正部１４は、行選択部１３で選択した行を指示する情報に基づき、パリティｐ(j-k)を
【数２】
2010034887.tif 000004
により計算し、第２の符号化データとして、第１の選択部１５を経由して、検査行列判断部１２と消失訂正部１４にフィードバックする。
【００５５】
また、検査行列判断部１２で、値が非零である要素の個数が１個である行が１行も存在しない場合には、切替部１７をパリティ生成部１１側に切替えて、パリティ生成部１１で、生成行列Ｇのパリティ位置部分からまだ生成していないパリティに対応する列を選択し、その列のパリティを生成し、再度第１の符号化データとして出力し、第１の選択部１５を経由して、検査行列判断部１２と消失訂正部１４にフィードバックする。
【００５６】
上記したように、消失訂正部１４もしくはパリティ生成部１１のどちらかで、パリティを１個生成できており、検査行列からデータ位置部分と、既に生成されたパリティに対応する列を除いた部分行列は、生成できたパリティに対応する列を除いておく。
【００５７】
このようにして、検査行列判断部１２と行選択部１３でパリティ生成方法を選択し、消失訂正部１４もしくはパリティ生成部１１のどちらかで、パリティを計算することを繰り返して、残りのパリティを全て生成する。
【００５８】
通常のｒｅｇｕｌａｒのＬＤＰＣ符号では、生成行列のパリティ位置部分では、非零の要素がほぼ半分と予想されるので、生成行列の列に基づいてパリティを生成すると、１個のパリティの生成につき、（ｋ／２）−１回のシンボル単位の加算が発生する。これに対し、検査行列の各行は（符号の次数）／（１−ｋ／ｎ）個の非零の要素があるので、検査行列の行に基づいてパリティを生成すると、１個のパリティの生成につき、（（符号の次数）／（１−ｋ／ｎ））−２回のシンボル単位の加算が発生する。ｋの値として数百から数千程度、ｋ／ｎの範囲としては１／２ないし１／１０程度、符号の次数は３ないし７程度を想定すると、生成行列の列に基づいてパリティを生成した場合のシンボル単位の加算回数は数百から数千のオーダ、検査行列の行に基づいてパリティを生成した場合のシンボル単位の加算回数は数十のオーダとなり、生成行列に基づいて計算していたパリティの一部を検査行列に基づいて計算することにより、大幅な計算量の削減が可能となった。
【００５９】
また、検査行列の各行において、非零の要素に対応する受信語の要素のうち、値が不明の要素が１個である場合に他の要素から計算するというのは、通常は消失誤りを訂正する時の手法である。そして、任意の位置に生起する消失誤りを訂正する場合、符号によって大きく異なるが、おおよそパリティシンボル数の５〜９割程度の消失誤りを訂正することが可能である。例えばパリティシンボル数の９割の消失誤りを訂正できる符号であれば、訂正できない１割に相当するシンボル数のパリティを、符号化開始時にパリティ生成部１１で生成しておけば、残りの９割のほぼ大部分（もしくは全て）のパリティは消失訂正部１４で生成することが可能である。
【００６０】
このように、消失訂正部１４が計算量の少ない消失訂正処理でパリティを生成することができる。また、消失訂正部１４が消失訂正処理を行うことができない場合に、パリティ生成部１１がパリティを生成する。これによって、消失訂正部１４が消失訂正処理を行うことができるようになり、計算量の削減を図ることができる。
【００６１】
なお、検査行列判断部１２で、値が非零である要素の個数が１個である行が１行でも存在すれば、その情報を行選択部１３に出力し、行選択部１３はその情報をそのまま使う（行選択部１３は実質的に存在しない）構成でも良い。
【００６２】
（実施の形態２）
次に、本発明の実施の形態２について説明する。上記実施の形態１では、行選択部１３が選択することができる検査行列Ｈの行が存在しなければ、パリティ生成部１１がパリティを生成することとした。しかし、本実施の形態２では、行選択部１３が少なくとも１以上の検査行列Ｈの行を選択するように構成される。
【００６３】
図４は、本発明の実施の形態２における符号化装置の機能的な構成の一例を示すブロック図である。
【００６４】
図４に示すように、実施の形態２の符号化装置１０は、パリティ生成部２１、検査行列に基づいたパリティ生成部２２、行選択部２３、消失訂正部２４、及び第１の選択部２５を備えている。実施の形態２の符号化装置１０は、実施の形態１の符号化装置１０と同様に、入力されたｋ個のシンボルのデータＤから、ｒ＝（ｎ−ｋ）個のシンボルのパリティを生成して、ｎ個のシンボルの符号語を出力する。生成行列及び検査行列も、実施の形態１と同様に、図３Ａ及び３Ｂに示す通りである。
【００６５】
パリティ生成部２１は、図３Ａに示すような生成行列Ｇのパリティ位置部分からｑ列を選択し、ｊ＝０，１，…，（ｑ−１）として、パリティｐj＝ｇ0,j・ｄ0＋ｇ1,j・ｄ1＋ｇ2,j・ｄ2＋……＋ｇ(k-2),j・ｄ(k-2)＋ｇ(k-1),j・ｄ(k-1)を生成し、第１の符号化データとして出力する。図３Ｂでは、検査行列Ｈにおいて、生成行列Ｇのデータ位置部分と生成済みのパリティの部分に対応する列を斜線部分で示している。
【００６６】
検査行列に基づいたパリティ生成部２２では、残りの未生成のパリティを１シンボルずつ生成していく。まず、行選択部２３で、検査行列からデータ位置部分と、既に生成されたパリティに対応する列を除いた（ｎ−ｋ−ｑ）列の部分行列Ｈ(n-k-q)の行のうち、値が非零である要素の個数が１個である行を選択する。
【００６７】
選択された行が（ｉ＋１）行目であり、非零の要素がｈi,j（但しｊは（ｋ＋ｑ）〜（ｎ−１）のいずれかである）とすれば、Ｃ・ＨT＝０から（ｉ＋１）行目だけを抜き出した式
【数３】
2010034887.tif 000005
において、まだ生成されていないパリティｐq〜ｐ(r-1)の係数となるｈi,(k+q)〜ｈi,(n-1)のうち、ｈi,jのみが非零である。
【００６８】
消失訂正部２４は、行選択部２３で選択した行を指示する情報に基づき、パリティｐ(j-k)を
【数４】
2010034887.tif 000006
により、計算する。
【００６９】
上記したように、パリティを１個生成できたので、第１の選択部２５を経由して第２の符号化データとして、行選択部２３と消失訂正部２４にフィードバックする。また検査行列からデータ位置部分と、既に生成されたパリティに対応する列を除いた部分行列は、さらに生成できたパリティに対応する列を除いて、（ｎ−ｋ−ｑ−１）列の部分行列Ｈ(n-k-q-1)とする。
【００７０】
このようにして、行選択部２３で、部分行列から値が非零である要素の個数が１個である行を選択し、消失訂正部２４で、検査行列の当該行の値を元に非零の要素に対応するパリティを計算することを繰り返して、パリティ生成部２１で生成しなかったパリティを全て生成する。
【００７１】
ここで、パリティ生成部２１が生成するパリティは、行選択部２３が少なくとも１以上の検査行列Ｈの行を選択するように定められる。つまり、パリティ生成部２１で生成するｑ個のパリティについては、残りのパリティに対応する検査行列の列から構成される部分行列Ｈx（但し、ｘ＝（ｎ−ｋ−ｑ），（ｎ−ｋ−ｑ−１），…，２，１）のそれぞれにおいて、値が非零である要素の個数が１個である行が少なくとも１行は存在するように、予め選択されているものとする。
【００７２】
上記の構成により、実施の形態１と同様に、一部のパリティシンボルの作成アルゴリズムを消失訂正処理に置き換えることが可能にしており、パリティシンボル１個の生成につき、シンボル単位の加算回数を、おおよそ（データシンボル数／２）−１回から（（符号の次数）／（１−符号化率））−２回に削減することができ、符号化処理全体の計算量を大幅に削減することが可能になった。
【００７３】
このように、行選択部２３が行の選択を行うことができるように、予めパリティ生成部２１が生成するパリティが定められる。これによって、消失訂正部２４が消失訂正処理を行うことができるようになり、計算量の削減を図ることができる。
【００７４】
以下の表は、従来の符号化装置と本発明の符号化装置のそれぞれにおいて、実際にどの程度の回数の加算を行なって符号化を行なっているのかを示す例である。パリティ生成部２１で生成するパリティ数ｑについては、従来比が最小となる値を選んでいる。この結果からも、本発明により、加算回数を削減し、符号化の処理速度を高速化することが可能であることは明確となっている。
【００７５】
符号は、それぞれ符号化率（データ長／符号長）は３／４として、検査行列を乱数で生成したものである。従って、同じパラメータ（符号長、符号化率、次数）であっても、異なる符号であれば、ｑの値や加算回数は異なるが、傾向としてはほぼ同じようになると考えられる。
【００７６】
【表１】
2010034887.tif 000007
【００７７】
なお、パリティ生成部２１は、部分行列において値が非零である要素の個数が１個である行を選択するとしているが、パリティ生成部２１で生成するパリティを予め選択した時点で、どのような順序で行を選択していくかも判明しているので、非零の要素の個数をチェックせずに既に判明している順序で行を指定していくようにしても良い。
【００７８】
また、図３Ａでは、ｑ列は検査行列のパリティ位置部分の左側にまとまっているが、実際にはパリティ生成部２１で生成するパリティを予め選択した時点では、パリティ位置部分のｒ列のあいだで散らばっており、検査行列と生成行列としては、そのまま使っても左側にまとめるように列を入れ替えて使っても良い。
【００７９】
また、本発明において演算を加算として説明しているが、これは符号の要素に応じた演算を意味している。例えば、符号がガロア体ＧＦ（ｑ）の要素で構成されていればａとｂの加算は（ａ＋ｂ）ｍｏｄ  ｑのことであり、ガロア体ＧＦ（２）の要素で構成されていれば、加算は排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）のことである。また、ｔビットのガロア体ＧＦ（２）の要素からなるブロックを符号の１シンボルとした場合は、ｔ個の排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）を並列して実行する演算を意味している。
【００８０】
また、生成行列Ｇや検査行列Ｈは、符号ごとに固有の行列であるので、使われている符号に合わせた生成行列Ｇや検査行列Ｈの情報を選択するもしくは入力する機能を備えれば、複数の符号を扱う符号化装置１０を構成できることは明らかである。
【００８１】
以上、本発明に係る符号化装置について、上記実施の形態を用いて説明したが、本発明は、これに限定されるものではない。
【００８２】
つまり、今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【００８３】
例えば、本実施の形態では、データＤ、生成行列Ｇ及び検査行列Ｈの各要素は２進数であることとしたが、データＤ、生成行列Ｇ及び検査行列Ｈの各要素は２進数に限定されず、３進数などであってもよい。
【００８４】
また、本実施の形態では、パリティ生成部１１などの各構成要素は、ソフトウェアにより構成されていることとしたが、専用のハードウェアにより構成されていてもよい。つまり、ブロック図（図１及び図４など）の各機能ブロックは、典型的には集積回路であるＬＳＩとして実現されていてもよい。なお、これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。
【産業上の利用可能性】
【００８５】
本発明に係る符号化装置、符号化方法、及び符号化プログラムは、処理速度を高速化することができ、ネットワーク伝送時のパケットロスのような消失訂正の用途に有用である。
【図面の簡単な説明】
【００８６】
【図１】本発明の実施の形態１の符号化装置の機能的な構成の一例を示すブロック図である。
【図２】符号化装置が実行する符号化の処理を示すフローチャートである。
【図３Ａ】符号化装置の符号化処理の一例を具体的に説明する図である。
【図３Ｂ】符号化装置の符号化処理の一例を具体的に説明する図である。
【図４】本発明の実施の形態２の符号化装置の機能的な構成の一例を示すブロック図である。
【図５】伝送パケット生成の説明図である。
【符号の説明】
【００８７】
１０  符号化装置
１１、２１  パリティ生成部
１２  検査行列判断部
１３、２３  行選択部
１４、２４  消失訂正部
１５、２５  第１の選択部
１６  第２の選択部
１７  切替部
２２  検査行列に基づいたパリティ生成部
【図１】
2010034887.tif 000008
【図２】
2010034887.tif 000009
【図３Ａ】
2010034887.tif 000010
【図３Ｂ】
2010034887.tif 000011
【図４】
2010034887.tif 000012
【図５】
2010034887.tif 000013