JP2010041628A - 符号化装置、符号化方法および符号化プログラム - Google Patents

Abstract

【課題】計算量を削減することができる符号化装置を提供する。
【解決手段】符号化装置であって、メモリ１２と、データをｃ個のシンボルずつの部分データに区切り、部分データと要素が全て零となる全零以外の係数とから、全ての要素の組み合わせの係数について中間データを生成し、メモリ１２に記憶する中間データ生成部１１と、線形符号の生成行列のパリティの位置にあたる部分をｃ行ごとの部分行列に分割し、部分行列の列の値と同一の要素の組み合わせの係数に基づいて生成される中間データをメモリ１２から読み出して、パリティを生成するパリティ生成部１３とを備え、中間データ生成部１１は、全ての部分データに対して中間データを生成してメモリ１２に記憶し、パリティ生成部１３は、全ての部分行列に対して中間データをメモリ１２から読み出して、列ごとに全ての読み出された中間データを累積することでそれぞれの列に対応するパリティを生成する。
【選択図】図１

Description

本発明は、ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号等の線形符号の符号化方法および符号化装置に関するものである。

近年、訂正能力に優れた符号として、ＬＤＰＣ符号が有力視されている（例えば、非特許文献１〜３）。

ＩＰネットワークで、映像や音声のストリーミング伝送を行なう場合、リアルタイム性を維持するためにロストしたパケットを再送しないＵＤＰ（Ｕｓｅｒ Ｄａｔａｇｒａｍ Ｐｒｏｔｏｃｏｌ）で送るケースがある。そのような場合に、伝送経路に無線で伝送する区間があれば、ロストするパケットへの対策が必要になる。この対策としては、パケットをインターリーブして誤り訂正符号化することが考えられる。使用する誤り訂正符号としては、インターリーブ長を長くしやすいＬＤＰＣ符号も有力な候補である。

例えば、図６に示すように、ｐ×ｋビットのデータをｐビットずつのブロックとし、各ブロックから１ビットずつ得たｋビットのデータを符号化して、（ｎ−ｋ）ビットのパリティをつけていくと、トータルでｐ×（ｎ−ｋ）ビットのパリティが付加されることになり、これらのパリティで（ｎ−ｋ）ブロックとなる。伝送する時には、１個のブロックを１個のパケットのデータとして、それぞれヘッダ情報（ＵＤＰヘッダ／ＩＰヘッダなど）を付加し、ＩＰパケットを構成する。インターリーブは、１個のブロックから１ビットではなく複数のビットを集めて１個の符号語に符号化しても構わないし、複数のブロックから１ビットずつ集めて符号化しても構わない。

ここで、データは変形せずに、パリティを付加するだけの組織符号（Ｓｙｓｔｅｍａｔｉｃ ｃｏｄｅ）として説明している。組織符号は、データが変換される非組織符号と比較すると、消失したパケットを訂正復元できなかった場合にも、受信できたパケットはそのまま使えるという利点がある。

伝送後に、ｎ個のパケットが揃わなくても、失われたパケットのデータを消失として、ｐ個の符号語の全てに誤り訂正処理を行なって、１ビットずつ復元していけば、元のブロックを復元することが可能である。ＩＰパケットはイーサネット（登録商標）ではパケット長の最大値が１，５００バイトとなっており、ＩＰヘッダ長は標準で２０バイト、ＵＤＰヘッダ長は８バイトであるので、データは最大１，４７２バイト＝１１，７７６ビットまで使用可能である。ストリーミング伝送を行なう場合は、１個のパケットに載せるデータはできるだけ多くし、ヘッダにより増加する伝送レートをできるだけ少なくして効率よく伝送することが要求されるので、１個のＩＰパケットに載せるデータは１０，０００ビット程度にはなると考えられる。１個のＩＰパケットから１ビットずつ集めてインターリーブするものとして、ＩＰパケットを符号の１個のシンボルとしてみなすと、シンボル同士の加算は、１０，０００ビット程度の排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）を実行することになる。

以下に、ＬＤＰＣ符号の符号化について、説明する。

ＬＤＰＣ符号は、線形符号（Ｌｉｎｅａｒ Ｃｏｄｅ）の１種であるが、線形符号は、ｋ行ｎ列の生成行列Ｇと、Ｇ・Ｈ^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)

しかしながら、従来の符号化の処理では、計算量が膨大になるという課題がある。

つまり、実際の符号化の処理は、データ（ベクトル）Ｄ＝（ｄ₀，ｄ₁，…，ｄ_(k-1)）に、生成行列Ｇをかけて、符号語（ベクトル）Ｃ＝（ｃ₀，ｃ₁，…，ｃ_(n-1)）＝Ｄ・Ｇを得ることによりなされる。この構成では、要素がガロア体ＧＦ（２）の要素であったとしても、計算量はおおよそ（ｎ−ｋ）×（ｋ／２−１）回のシンボルの加算が必要である。１個のシンボルの加算が１０，０００ビット程度の排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）処理であり、膨大な計算量となるため、符号化の処理時間や処理のリソースが要求される。

そこで、本発明は、上記課題を解決するために、計算量を削減することができる符号化装置を提供することを目的とする。

上記目的を達成するために、本発明に係る符号化装置は、Ｋ個のシンボルのデータを、パリティを含む符号長がＮでありデータ数がＫである線形符号に符号化する符号化装置であって、データを記憶する記憶部と、前記Ｋ個のシンボルのデータをｃ個のシンボルずつに、ｋ個（ｋは、Ｋ／ｃを切り上げた整数）の部分データに区切り、（ｉ＋１）番目（ｉは、０から（ｋ−１）までの整数）の前記部分データ（ｄ₀，ｄ₁，…，ｄ_(c-1)）と要素が全て零となる全零以外の係数（ａ₀，ａ₁，…，ａ_(c-1)）とから、全ての要素の組み合わせの前記係数について中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(c-1)・ｄ_(c-1)）を生成し、前記中間データを前記記憶部に記憶する中間データ生成部と、前記線形符号の生成行列のパリティの位置にあたる部分をｃ行ごとの部分行列に分割し、（ｉ＋１）番目の前記部分行列の（ｊ＋１）番目（ｊは、０から（Ｎ−Ｋ−１）までの整数）の列の値と同一の要素の組み合わせの前記係数に基づいて生成される前記中間データを前記記憶部から読み出して、全ての列についての前記中間データからそれぞれの列に対応するパリティを生成するパリティ生成部とを備え、前記中間データ生成部は、全ての前記部分データに対して前記中間データを生成して前記記憶部に記憶し、前記パリティ生成部は、全ての前記部分行列に対して前記中間データを前記記憶部から読み出して、前記列ごとに全ての前記読み出された中間データを累積することでそれぞれの列に対応するパリティを生成する。

これによれば、データ及び生成行列を複数のグループに区切り、そのグループ単位で中間データを生成し、生成された中間データからパリティを生成する。これにより、同じ計算で生成される中間データが複数ある場合は、１回の計算のみで当該中間データを生成することができるので、重複して計算が行われるのを避けることができ、計算量の削減を図ることができる。

また、前記中間データ生成部は、中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(y-1)・ｄ_(y-1)）（ｙ＝１，２，…，（ｃ−１））が生成されており、ａ_yが零でない場合には、当該中間データにａ_y・ｄ_yを加算することで、中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(y-1)・ｄ_(y-1)＋ａ_y・ｄ_y）を生成することにしてもよい。

これによれば、既に計算され生成された中間データを利用して、新たに中間データを計算し生成することができるので、計算量の削減を図ることができる。

また、前記中間データ生成部は、（ｉ＋１）番目の部分データによる中間データをｉ番目の部分データによる中間データに上書きすることで、（ｉ＋１）番目の部分データによる中間データを前記記憶部に記憶することにしてもよい。

これによれば、記憶部の中間データ領域の必要量は、データ全体分の中間データの容量ではなく、1個の部分データによる中間データの容量で済ませることが可能となるため、中間データ領域を大幅に削減することが可能となる。

また、本発明は、このような符号化装置として実現できるだけでなく、その装置を構成する処理部をステップとする方法として実現したりすることができる。さらに、本発明は、それらステップをコンピュータに実行させるプログラムとして実現したり、そのプログラムを記録したコンピュータ読み取り可能なＣＤ−ＲＯＭなどの記録媒体として実現したり、そのプログラムを示す情報、データ又は信号として実現したりすることもできる。そして、それらプログラム、情報、データ及び信号は、インターネット等の通信ネットワークを介して配信してもよい。

以上のように、本発明によれば、データ及び生成行列をグループ単位にまとめて中間データ生成し、当該中間データからパリティを生成することにより、計算量の削減を図ることができる。

以下に、本発明の実施の形態について、図面を参照しながら説明する。

（実施の形態１）
図１は、本発明の実施の形態１における符号化装置１０の機能的な構成の一例を示すブロック図である。

図１に示すように、実施の形態１の符号化装置１０は、中間データ生成部１１、メモリ１２、及びパリティ生成部１３を備えている。符号化装置１０は、ＣＰＵ（Central Processing Unit）等を備え、入力されたｋシンボルのデータを符号化して、ｎシンボルの符号語を出力するコンピュータである。

ここで、メモリ１２は、入力されるデータ、パリティ、及び後述する中間データテーブル１２ａなどを記憶している不揮発性メモリ等である。

中間データ生成部１１は、入力されたデータを複数の部分データに区切り、全ての部分データに対して中間データを生成し、中間データをメモリ１２に記憶する。

具体的には、中間データ生成部１１は、ｋ個のシンボルのデータをｃ個のシンボルずつに、ｘ個（ｘは、ｋ／ｃを切り上げた整数）の部分データに区切り、（ｉ＋１）番目（ｉは、０から（ｘ−１）までの整数）の部分データ（ｄ₀，ｄ₁，…，ｄ_(c-1)）と要素が全て零となる全零以外の係数（ｍ₀，ｍ₁，…，ｍ_(c-1)）とから、全ての要素の組み合わせの係数について中間データ（ｍ₀・ｄ₀＋ｍ₁・ｄ₁＋…＋ｍ_(c-1)・ｄ_(c-1)）を生成する。また、中間データ生成部１１は、生成された中間データをメモリ１２に記憶されている中間データテーブル１２ａに書き込み、中間データテーブル１２ａを更新していく。

図２Ａ及び図２Ｂは、中間データテーブル１２ａの一例を示す図である。

図２Ａに示すように、中間データテーブル１２ａは、部分データ、係数、及び中間データなどからなるテーブルであり、係数により、対応する中間データを参照できる。

部分データは、入力されたｋ個のシンボルのデータがｃ個のシンボルずつに区切られたデータの集まりである。例えば、入力されたデータＤ＝（ｄ₀，ｄ₁，…，ｄ_(k-1)）に対し、部分データＤ₀＝（ｄ₀，ｄ₁，…，ｄ_(c-1)）である。なお、ここでは、データＤの各要素は、２進数の値であり、０か１である。

係数は、ｃ個の要素で構成された、全零以外の全ての要素の組み合わせの係数（ｍ₀，ｍ₁，…，ｍ_(c-1)）である。なお、ここでは、係数の各要素は、２進数の値であり、０か１である。例えば、ｃが４の場合、係数は（１，０，０，０）、（０，１，０，０）、…、（１，１，１，１）の１５通りである。但し、1の要素が1個の組み合わせである（１，０、０、０）、（０，１，０，０）、（０，０，１，０）、（０，０，０，１）については、中間データを計算する必要がないので、中間データテーブル１２ａから省略することもできる。

中間データは、部分データと係数に対応して算出されるデータである。具体的には、データＤ₀＝（ｄ₀，ｄ₁，…，ｄ_(c-1)）及び係数（ｍ₀，ｍ₁，…，ｍ_(c-1)）に対して、中間データは、ｍ₀・ｄ₀＋ｍ₁・ｄ₁＋…＋ｍ_(c-1)・ｄ_(c-1)で算出される。

図１に戻り、パリティ生成部１３は、線形符号の生成行列のパリティの位置にあたる部分を複数の部分行列に分割し、全ての部分行列に対して中間データをメモリ１２から読み出して、部分行列の列ごとに全ての読み出された中間データを累積することでそれぞれの列に対応するパリティを計算し、生成する。

具体的には、パリティ生成部１３は、線形符号の生成行列のパリティの位置にあたる部分をｃ行ごとの部分行列に分割し、（ｉ＋１）番目の部分行列の（ｊ＋１）番目（ｊは、０から（ｎ−ｋ−１）までの整数）の列の値と同一の要素の組み合わせの係数に基づいて生成された中間データをメモリ１２から読み出して、全ての列についての中間データからそれぞれの列に対応するパリティを計算し、生成する。

なお、部分データＤ₁による中間データの生成を、パリティの計算において、部分データＤ₀による中間データを用いた計算が終了した後に行なうように処理すれば、部分データＤ₁による中間データを、部分データＤ₀による中間データに上書きして中間データテーブルに記憶させることができる。部分データＤ_(i+1)による中間データと部分データＤ_iによる中間データに関しても同様であるので、中間データ領域の必要量は、データ全体分の中間データの容量ではなく、１個の部分データによる中間データの容量で済ませることが可能となる。

つまり、中間データ生成部１１は、（ｉ＋１）番目の部分データＤ_(i+1)による中間データをｉ番目の部分データＤ_iによる中間データに上書きすることで、（ｉ＋１）番目の部分データＤ_(i+1)による中間データをメモリ１２に記憶する。そして、この場合には、図２Ｂに示すように、中間データテーブル１２ａは、係数及び中間データなどからなるテーブルであればよく、係数により、対応する中間データを参照できる。

図３は、符号化装置１０が実行する符号化の処理を示すフローチャートである。

以下の処理が、ｉが０から（ｘ−１）まで繰り返される（Ｓ１０１、Ｓ１１１）。

まず、中間データ生成部１１は、入力されたデータを複数の部分データに区切ることで、（ｉ＋１）番目の部分データを選択する（Ｓ１０２）。

そして、中間データ生成部１１は、全ての部分データに対して（ｉ＋１）番目の中間データを生成し、生成された中間データをメモリ１２の中間データテーブル１２ａに書き込み、中間データテーブル１２ａを更新していくことで、当該中間データをメモリ１２に記憶する（Ｓ１０４）。

次に、パリティ生成部１３は、線形符号の生成行列のパリティの位置にあたる部分をｃ行ずつ区切った場合に、（ｉ＋１）番目となる部分行列の情報を選択する（Ｓ１０６）。

そして、パリティ生成部１３は、部分行列の各列に対応する中間データをメモリ１２から読み出す（Ｓ１０８）。具体的には、パリティ生成部１３は、部分行列の列の値をもとにして、中間データテーブル１２ａに記憶されている中間データを、読み出す。

そして、パリティ生成部１３は、部分行列の全ての列について読み出された中間データをそれぞれ累積することで、各列に対応するパリティを計算し生成する（Ｓ１１０）。

このように、ｉが０から（ｘ−１）まで繰り返す（Ｓ１０１、Ｓ１１１）ことにより、パリティが生成される。

なお、Ｓ１０４の処理で生成された中間データを記憶させる時に、直前のループで記憶させた領域に上書きして記憶させれば、中間データ領域を大幅に削減することが可能となる。

図４Ａ〜図４Ｃは、符号化装置１０の符号化処理の一例を具体的に説明する図である。

符号の生成行列Ｇは図４Ａに示すようにｋ行ｎ列の行列であり、符号語のデータ部を生成する左から１列目からｋ列目の部分（以下、データ位置部分と呼ぶ）は単位行列であり、符号語のパリティ部を生成する左から（ｋ＋１）列目からｎ列目の部分（以下、パリティ位置部分と呼ぶ）にあるｕ行ｖ列の要素はｇ_{(u-1),(v-k-1)}で表わしている。

本発明では、図４Ｂに示すように、パリティ位置部分をｃ行ずつに区切った部分行列を単位として処理を繰り返すことを特徴としている。部分行列は、ｘ＝ｃｅｉｌ（ｋ／ｃ）個になる。即ち、ｘはｋ／ｃを切り上げた値であり、ｋがｃで割り切れればｘ＝（ｋ／ｃ）、ｋがｃで割り切れなければｘ＝ｉｎｔ（ｋ／ｃ）＋１である。なお、ｉｎｔ関数は、与えられた数値以下の整数で一番大きいものを返す関数である。

図４Ｃにこの部分行列の詳細を示す。上から（ｉ＋１）個目の部分行列Ｇ_i＝（Ｑ_i,0，Ｑ_i,1，…，Ｑ_i,(n-k-1)）の、（ｊ＋１）番目の列はＱ_i,j＝（ｇ_c×_i,j，ｇ_c×_i+1,j，…，ｇ_c×_i+(c-1),j）^Tとなる。記号^Tは、転置行列を表わす。

中間データ生成部１１は、データＤ＝（ｄ₀，ｄ₁，…，ｄ_(k-1)）をｃシンボルずつに区切った部分データＤ_i＝（ｄ_c×_i，ｄ_c×_i+1，…，ｄ_c×_i+(c-1)）から、全零以外の全ての係数（ｍ₀，ｍ₁，…，ｍ_(c-1)）について中間データＭ_i［ｍ₀，ｍ₁，…，ｍ_(c-1)］＝ｍ₀・ｄ_c×_i＋ｍ₁・ｄ_c×_i+1＋…＋ｍ_(c-1)・ｄ_c×_i+(c-1)を生成し、メモリ１２の中間データ領域の中間データテーブル１２ａに書込む。

パリティ生成部１３は、部分データＤ_iに対応する部分行列Ｇ_iのそれぞれの列データに基づいて計算されている中間データＭ_i［Ｑ_i,j ^T］を、メモリ１２の中間データ領域の中間データテーブル１２ａから読み出す。また、メモリ１２のパリティ領域からパリティｐ_jを読み出して、中間データＭ_i［Ｑ_i,j ^T］を加算し、加算した結果をパリティ領域に書き戻す。これをｊ＝０，１，…，（ｎ−ｋ−１）について実行する。

上記の、中間データ生成部１１による中間データＭ_iの生成と、パリティ生成部１３によるパリティｐ_j（ｊ＝０，１，…，（ｎ−ｋ−１））の計算を、ｉ＝０，１，…，（ｘ−１）について繰り返し実行する。

これらの計算の間、必要に応じて、入力されたデータはメモリ１２のデータ領域で保持しておき、パリティ計算のタイミングと合わせて、符号語としてデータとパリティを出力する。

従来のように生成行列ＧとデータＤを乗算して符号化する構成では、要素がガロア体ＧＦ（２）の要素であったとしても、計算量はおおよそ（ｎ−ｋ）×（ｋ／２−１）回のシンボルの加算が必要であるとしたが、本発明では、パリティ生成部１３での計算量は（ｎ−ｋ）×（ｘ−１）回のシンボルの加算に減らしており、中間データ生成部１１で（２^c−１）個の中間データをｘ回計算するために必要なシンボルの加算回数が（ｎ−ｋ）×ｋ×（ｃ−２）／２／ｃより少なければ、符号化装置全体での計算量を削減することが可能である。ＬＤＰＣ符号は、通常データシンボル数ｋは数百〜数千以上のオーダであり、パリティシンボル数（ｎ−ｋ）も数百以上のオーダであるので、ｃが３〜１０程度の値であれば、計算量削減が可能である。

このように、データ及び生成行列を複数のグループに区切り、そのグループ単位で中間データを生成し、生成された中間データからパリティを生成する。これにより、同じ計算で生成される中間データが複数ある場合は、１回の計算のみで当該中間データを生成することができるので、重複して計算が行われるのを避けることができ、計算量の削減を図ることができる。

なお、中間データ生成部１１は、ｉの値が変わる都度に、変わる前の処理で生成された中間データを、変わった後の処理で生成された中間データで上書きすることが可能である。

また、全零の係数から生成される中間データについての領域は不要としているが、それだけでなく、１個の要素が‘１’で残りの要素が‘０’である係数により生成される中間データは、それと全く同じ値がデータ領域に存在するので、これらを記憶する領域も省略しても良い。

なお、初期値の処理方法は、符号化開始時にメモリ１２のパリティ領域に全て０を書込むか、パリティの最初の項の計算時にメモリ１２に書込むのみの処理を行なうなどいくつか考えられるが、いずれであっても上記の加算回数の概算には影響しない。

なお、生成行列Ｇの情報は、パリティ生成部１３が保持する構成としているが、メモリ１２に生成行列Ｇの情報のための領域を設けて、パリティ生成部１３がその領域にアクセスするという構成であっても、本発明は適用可能である。

また、生成行列Ｇは、符号ごとに固有の行列であるので、使われている符号に合わせた生成行列Ｇの情報を選択するもしくは入力する機能を備えれば、複数の符号を扱う符号化装置１０を構成できることは明らかである。

また、ｃが３〜１０程度の値としたが、上限とした値１０はｎやｋ、符号の符号化率の値によって変わるものである。

（実施の形態２）
次に、本発明の実施の形態２について説明する。上記実施の形態１では、中間データ生成部１１は、全零以外の全ての要素の組み合わせの係数について中間データを生成することとしたが、本実施の形態２では、中間データ生成部１１は、既に生成された中間データを利用して、新たに中間データを生成する。

図５は、本発明の実施の形態２における中間データ生成部１１の構成の一例を示すブロック図である。図５に示すように、中間データ生成部１１は、加算部２１、ｊ−ビットカウンタ２２、及び選択部２３を備えている。

本実施の形態２では、中間データ生成部１１は、中間データ（ｂ₀・ｄ₀＋ｂ₁・ｄ₁＋…＋ｂ_(j-1)・ｄ_(j-1)）（ｊ＝１，２，…，（ｃ−１））が生成されており、ｂ_jが零でない場合には、当該中間データにｂ_j・ｄ_jを加算することで、中間データ（ｂ₀・ｄ₀＋ｂ₁・ｄ₁＋…＋ｂ_(j-1)・ｄ_(j-1)＋ｂ_j・ｄ_j）を生成する。

以下に、中間データ生成部１１の中間データの生成について、具体的に説明する。

入力される部分データＤ_i＝（ｄ_c×_i，ｄ_c×_i+1，…，ｄ_c×_i+(c-1)）の最初の要素であるｄ_c×_iは、中間データＭ_i［１，０，０，…，０］として、そのまま選択部２３から出力される。

ｊ−ビットカウンタ２２は、入力されるＤ_i＝（ｄ_c×_i，ｄ_c×_i+1，…，ｄ_c×_i+(c-1)）の要素のそれぞれであるｄ_c×_i+jに対し、ｊ−ビットのカウンタとして、（ｂ₀，ｂ₁，…，ｂ_(j-1)）が（０，０，…，０）から（１，１，…，１）までをカウントアップする。

カウントアップに従って、（ｂ₀，ｂ₁，…，ｂ_(j-1)）＝（０，０，…，０）の時は、選択部２３はｄ_c×_i+jを中間データＭ_i［（ｊ個の０），１，（（ｃ−ｊ−１）個の０）］として出力する。（ｂ₀，ｂ₁，…，ｂ_(j-1)）が（１，０，…，０）〜（１，１，…，１）である時は、加算部２１は順次、メモリ１２から読み出したＭ_i［ｂ₀，ｂ₁，…，ｂ_(j-1)，０，０，…，０］の値を読み出し、ｄ_c×_i+jを加算した値Ｍ_i［ｂ₀，ｂ₁，…，ｂ_(j-1)，１，０，…，０］＝ｄ_c×_i+j＋Ｍ_i［ｂ₀，ｂ₁，…，ｂ_(j-1)，０，０，…，０］を選択部２３から出力する。

例えば、中間データテーブル１２ａにおいて、部分データＤ₀＝（ｄ₀，ｄ₁，ｄ₂，ｄ₃）での係数（１，０，１，１）に対する中間データは、部分データＤ₀＝（ｄ₀，ｄ₁，ｄ₂，ｄ₃）での係数（１，０，１，０）に対する中間データにｄ₃を加算した値である。

上記の構成により、（２^c−ｃ−１）回のシンボルの加算により、ｃシンボルの部分データから、（２^c−１）個の中間データを生成することを可能とした。

このように、既に計算され生成された中間データを利用して、新たに中間データを計算し生成することができるので、計算量の削減を図ることができる。

以下の表に、従来の符号化装置と本発明の符号化装置のそれぞれにおいて、実際にどの程度の回数の加算を行なって符号化を行なっているのかを示す。符号は、それぞれ符号化率（データ長／符号長）は３／４として、検査行列を乱数で生成したものである。処理をまとめた行数ｃについては、従来比が最小となる値を選んでいる。この結果からも、本発明により、加算回数を削減し、符号化の処理速度を高速化することが可能であることは明確となっている。

なお、実施の形態１の中間データ生成部１１は、中間データをメモリ１２に出力するだけになっている。これに対し、本実施例（実施の形態２）の中間データ生成部１１は、それと機能は全く同じであるが、中間データの生成に、先に計算した中間データを利用することにより、計算量を削減しようとしているため、メモリ１２へのデータの指示情報とメモリ１２からの中間データの読出しが存在する。

また、本発明において演算を加算として説明しているが、これは符号の要素に応じた演算を意味している。例えば、符号がガロア体ＧＦ（ｑ）の要素で構成されていればａとｂの加算は（ａ＋ｂ）ｍｏｄ ｑのことであり、ガロア体ＧＦ（２）の要素で構成されていれば、加算は排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）のことである。また、ｔビットのガロア体ＧＦ（２）の要素からなるブロックを符号の１シンボルとした場合は、ｔ個の排他的論理和（ｅｘｃｌｕｓｉｖｅ−ｏｒ）を並列して実行する演算を意味している。

以上、本発明に係る符号化装置について、上記実施の形態を用いて説明したが、本発明は、これに限定されるものではない。

つまり、今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。

例えば、本実施の形態では、データ及び係数の各要素は２進数であることとしたが、データ及び係数の各要素は２進数に限定されず、３進数などであってもよい。

また、本実施の形態では、中間データ生成部１１などの各構成要素は、ソフトウェアにより構成されていることとしたが、専用のハードウェアにより構成されていてもよい。つまり、ブロック図（図１及び図５など）の各機能ブロックは、典型的には集積回路であるＬＳＩとして実現されていてもよい。なお、これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。

本発明に係る符号化装置、符号化方法、及び符号化プログラムは、処理速度を高速化することができ、ネットワーク伝送時のパケットロスのような消失訂正の用途に有用である。

本発明の実施の形態１の符号化装置の機能的な構成の一例を示すブロック図である。 中間データテーブルの一例を示す図である。 中間データテーブルの一例を示す図である。 符号化装置が実行する符号化の処理を示すフローチャートである。 符号化装置の符号化処理の一例を具体的に説明する図である。 符号化装置の符号化処理の一例を具体的に説明する図である。 符号化装置の符号化処理の一例を具体的に説明する図である。 本発明の実施の形態２の中間データ生成部１１の構成の一例を示すブロック図である。 伝送パケット生成の説明図である。

符号の説明

１０ 符号化装置
１１ 中間データ生成部
１２ メモリ
１２ａ 中間データテーブル
１３ パリティ生成部
２１ 加算部
２２ ｊ−ビットカウンタ
２３ 選択部

Claims (5)

1. Ｋ個のシンボルのデータを、パリティを含む符号長がＮでありデータ数がＫである線形符号に符号化する符号化装置であって、
   データを記憶する記憶部と、
   前記Ｋ個のシンボルのデータをｃ個のシンボルずつに、ｋ個（ｋは、Ｋ／ｃを切り上げた整数）の部分データに区切り、（ｉ＋１）番目（ｉは、０から（ｋ−１）までの整数）の前記部分データ（ｄ₀，ｄ₁，…，ｄ_(c-1)）と要素が全て零となる全零以外の係数（ａ₀，ａ₁，…，ａ_(c-1)）とから、全ての要素の組み合わせの前記係数について中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(c-1)・ｄ_(c-1)）を生成し、前記中間データを前記記憶部に記憶する中間データ生成部と、
   前記線形符号の生成行列のパリティの位置にあたる部分をｃ行ごとの部分行列に分割し、（ｉ＋１）番目の前記部分行列の（ｊ＋１）番目（ｊは、０から（Ｎ−Ｋ−１）までの整数）の列の値と同一の要素の組み合わせの前記係数に基づいて生成される前記中間データを前記記憶部から読み出して、全ての列についての前記中間データからそれぞれの列に対応するパリティを生成するパリティ生成部とを備え、
   前記中間データ生成部は、全ての前記部分データに対して前記中間データを生成して前記記憶部に記憶し、
   前記パリティ生成部は、全ての前記部分行列に対して前記中間データを前記記憶部から読み出して、前記列ごとに全ての前記読み出された中間データを累積することでそれぞれの列に対応するパリティを生成する
   ことを特徴とする符号化装置。
2. 前記中間データ生成部は、中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(y-1)・ｄ_(y-1)）（ｙ＝１，２，…，（ｃ−１））が生成されており、ａ_yが零でない場合には、当該中間データにａ_y・ｄ_yを加算することで、中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(y-1)・ｄ_(y-1)＋ａ_y・ｄ_y）を生成する
   ことを特徴とする請求項１に記載の符号化装置。
3. 前記中間データ生成部は、（ｉ＋１）番目の部分データによる中間データをｉ番目の部分データによる中間データに上書きすることで、（ｉ＋１）番目の部分データによる中間データを前記記憶部に記憶する
   ことを特徴とする請求項１に記載の符号化装置。
4. Ｋ個のシンボルのデータを、パリティを含む符号長がＮでありデータ数がＫである線形符号に符号化する符号化方法であって、
   コンピュータが、前記Ｋ個のシンボルのデータをｃ個のシンボルずつに、ｋ個（ｋは、Ｋ／ｃを切り上げた整数）の部分データに区切り、（ｉ＋１）番目（ｉは、０から（ｋ−１）までの整数）の前記部分データ（ｄ₀，ｄ₁，…，ｄ_(c-1)）と要素が全て零となる全零以外の係数（ａ₀，ａ₁，…，ａ_(c-1)）とから、全ての要素の組み合わせの前記係数について中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(c-1)・ｄ_(c-1)）を生成し、データを記憶するための記憶部に前記中間データを記憶する中間データ生成ステップと、
   コンピュータが、前記線形符号の生成行列のパリティの位置にあたる部分をｃ行ごとの部分行列に分割し、（ｉ＋１）番目の前記部分行列の（ｊ＋１）番目（ｊは、０から（Ｎ−Ｋ−１）までの整数）の列の値と同一の要素の組み合わせの前記係数に基づいて生成される前記中間データを前記記憶部から読み出して、全ての列についての前記中間データからそれぞれの列に対応するパリティを生成するパリティ生成ステップとを含み、
   前記中間データ生成ステップでは、コンピュータが、全ての前記部分データに対して前記中間データを生成して前記記憶部に記憶し、
   前記パリティ生成ステップでは、コンピュータが、全ての前記部分行列に対して前記中間データを前記記憶部から読み出して、前記列ごとに全ての前記読み出された中間データを累積することでそれぞれの列に対応するパリティを生成する
   ことを特徴とする符号化方法。
5. Ｋ個のシンボルのデータを、パリティを含む符号長がＮでありデータ数がＫである線形符号に符号化するためのプログラムであって、
   前記Ｋ個のシンボルのデータをｃ個のシンボルずつに、ｋ個（ｋは、Ｋ／ｃを切り上げた整数）の部分データに区切り、（ｉ＋１）番目（ｉは、０から（ｋ−１）までの整数）の前記部分データ（ｄ₀，ｄ₁，…，ｄ_(c-1)）と要素が全て零となる全零以外の係数（ａ₀，ａ₁，…，ａ_(c-1)）とから、全ての要素の組み合わせの前記係数について中間データ（ａ₀・ｄ₀＋ａ₁・ｄ₁＋…＋ａ_(c-1)・ｄ_(c-1)）を生成し、データを記憶するための記憶部に前記中間データを記憶する中間データ生成ステップと、
   前記線形符号の生成行列のパリティの位置にあたる部分をｃ行ごとの部分行列に分割し、（ｉ＋１）番目の前記部分行列の（ｊ＋１）番目（ｊは、０から（Ｎ−Ｋ−１）までの整数）の列の値と同一の要素の組み合わせの前記係数に基づいて生成される前記中間データを前記記憶部から読み出して、全ての列についての前記中間データからそれぞれの列に対応するパリティを生成するパリティ生成ステップとをコンピュータに実行させ、
   前記中間データ生成ステップでは、全ての前記部分データに対して前記中間データを生成して前記記憶部に記憶し、
   前記パリティ生成ステップでは、全ての前記部分行列に対して前記中間データを前記記憶部から読み出して、前記列ごとに全ての前記読み出された中間データを累積することでそれぞれの列に対応するパリティを生成する
   ことを特徴とするプログラム。

Images