(57)【要約】【課題】LDGM復号処理の計算量と計算時間を小さくし、巨大ブロック長を用いた場合でも、ライブストリーミング伝送に使用し得るリアルタイム処理を実現する。【解決手段】本発明は、検査行列から、行を表す要素数Mの構造体ROWと列を表す要素数NのCOLUMNの構造表現形式（２元疎行列の双方向リンク型表現）を生成して記憶手段に格納し、検査行列の誤りシンボルを回復後に全ての検査方程式を走査し、誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行い、シンボル受信状態に応じて前記検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定し、依存関係がない検査方程式のシンボル回復を並行して処理する。【選択図】図１
2010081105.tif 000002
【特許請求の範囲】
【請求項１】
LDGM(Low-Density Generator Matrix)符号化された通信情報の復号化方法であって、
LDGM復号装置において、
受信データの検査行列から、１行が１つの検査方程式に対応する要素数Mの構造体ROWと、１列が１シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成ステップと、
前記検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査ステップと、
誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正ステップと、
シンボル受信状態に応じて前記検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定ステップと、
依存関係がない検査方程式のシンボル回復を並行して処理する並行処理ステップと、
の少なくとも１つのステップを行うことを特徴とする通信情報の復号化方法。
【請求項２】
前記構造表現形式生成ステップにおいて、
前記構造体ROWを、
自行を示す行番号：ｉ；
検査行列Hの第ｉ行で非零の列番号を保持するリストLcol；
自行が回復させたシンボルの列番号：Rcol；
の要素からなるものとし、
前記構造体COLUMNを、
自列を示す列番号：ｊ；
検査行列Ｈの第ｊ列で非零の行番号を保持するリスト：Ｌrow；
自列のシンボルを回復した検査方程式の行番号：Ｒrow；
自列の示すシンボルの誤り状態を示すフラグ：Ｆ（誤りなく受信／検査方程式によって回復／誤っている）；
の要素からなるものとする請求項１記載の通信情報の復号化方法。
【請求項３】
前記検査方程式走査ステップにおいて、
メインルーチンから呼び出されるサブルーチン（関数Ｆ（Ｐ））を、
前記集合Ｐの全ての要素に対して、誤りを一つだけ含む行（検査方程式）を順に見つけ、見つかった各行（検査方程式）に対して、
誤り訂正処理を行い、
誤り訂正したシンボルを含む他の行の集合を集合Ｐ'として定義し、
Ｆ（Ｐ'）を実行する操作を行うものと定義し、
メインルーチンにおいて、
前記集合Ｐに検査行列全体の要素を設定し、
前記関数Ｆ（Ｐ）を実行する
請求項１記載の通信情報の復号化方法。
【請求項４】
誤り訂正ステップにおいて、
前記回復できない誤りシンボル数が所定の値を超えた場合に、送信ホストに向けた再送要求、または、代替回復処理を行う
請求項１記載の通信情報の復号化方法。
【請求項５】
前記依存関係確定ステップにおいて、
シンボル受信状態に応じて前記検査方程式を分類する際に、
シンボルの受信状態が、誤りなく受信した完全受信、または、誤って受信したが、他の検査方程式により回復された回復受信、または、誤って受信した消失受信のいずれであるかを判定し、
回復受信の場合は、シンボル回復時の検査方程式を記録して一上位、一下位の依存関係を確定し、
検査方程式の依存木を作成する
請求項１記載の通信情報の復号方法。
【請求項６】
前記検査方程式の依存木を作成する際に、
根となる検査方程式から走査を行い、順に一回の検査方式を辿り、根となる検査方程式ラベルを付与する、
請求項５記載の通信情報の復号化方法。
【請求項７】
一上位の依存検査方程式が複数の場合には、該依存検査方程式のラベルをマージして根の検査方程式リストに追加する
請求項６記載の通信情報の復号化方法。
【請求項８】
LDGM符号化された通信情報の復号化装置であって、
受信データの検査行列から、１行が１つの検査方程式に対応する要素数Mの構造体ROWと、１列が１シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成手段と、
前記検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査手段と
誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正手段と、
シンボル受信状態に応じて前記検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定手段と、
依存関係がない検査方程式のシンボル回復を並行して処理する並行処理手段と、
を有することを特徴とする通信情報の復号化装置。
【請求項９】
前記構造表現形式生成手段は、
自行を示す行番号：ｉ；
検査行列Hの第ｉ行で非零の列番号を保持するリストLcol；
自行が回復させたシンボルの列番号：Rcol；
の要素を有する前記構造体ROWを生成し、
自列を示す列番号：ｊ；
検査行列Ｈの第ｊ列で非零の行番号を保持するリスト：Ｌrow；
自列のシンボルを回復した検査方程式の行番号：Ｒrow；
自列の示すシンボルの誤り状態を示すフラグ：Ｆ（誤りなく受信／検査方程式によって回復／誤っている）；
の要素を有する前記構造体COLUMNを生成する手段を含む請求項８記載の通信情報の復号化装置。
【請求項１０】
前記検査方程式走査手段は、
メインルーチンから呼び出されるサブルーチン（関数Ｆ（Ｐ））を、
前記集合Ｐの全ての要素に対して、誤りを一つだけ含む行（検査方程式）を順に見つけ、見つかった各行（検査方程式）に対して、
誤り訂正処理を行い、
誤り訂正したシンボルを含む他の行の集合を集合Ｐ'として定義し、
Ｆ（Ｐ'）を実行する操作を行うものと定義し、
メインルーチンにおいて、
集合Ｐに検査行列全体の要素を設定し、関数Ｆ（Ｐ）を実行する手段を含む
請求項８記載の通信情報の復号化装置。
【請求項１１】
誤り訂正手段は、
前記回復できない誤りシンボル数が所定の値を超えた場合に、送信ホストに向けた再送要求、または、代替回復処理を行う手段を含む
請求項８記載の通信情報の復号化装置。
【請求項１２】
前記依存関係確定手段は、
シンボルの受信状態が、誤りなく受信した完全受信、または、誤って受信したが、他の検査方程式により回復された回復受信、または、誤って受信した消失受信のいずれであるかを判定し、回復受信の場合は、シンボル回復時の検査方程式を記録して一上位、一下位の依存関係を確定し、検査方程式の依存木を作成する手段を含む
請求項８記載の通信情報の復号装置。
【請求項１３】
前記依存関係確定手段は、
前記検査方程式の依存木を作成する際に、根となる検査方程式から走査を行い、順に一回の検査方式を辿り、根となる検査方程式ラベルを付与する手段を含む
請求項１２記載の通信情報の復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信情報の復号化方法及び復号化システムに係り、特に、ＩＰネットワーク上で機能する誤り訂正ブロック符号であるLDGM(Low-Density Generator Matrix)符号の復号過程における処理の効率化を行うための通信情報の復号化方法及び復号化装置に関する。
【０００２】
特に、通信路符号限界（シャノン限界）まで迫る誤り検出・訂正能力を持つＬＤＰＣ符号の一つであるＬＤＧＭ符号の復号の効率化及び高速化を行うための通信情報の復号化方法及び復号化装置に関する。
【背景技術】
【０００３】
ＩＰ網上でデータを多地点に伝送する場合、トラヒックの効率的な利用のためにマルチキャストが広く用いられる。現在主に用いられるＩＰ網はパケットデータを帯域補償指向ではなく、ベストエフォート指向で伝送するため、伝送途中でパケットデータ消失することが避けられない。そのため、消失したパケットデータを補償する機構である消失訂正の必要がある。マルチキャストトポロジを考えた場合のパケットデータの誤り訂正に求められる要求条件は、処理コストが受信ノード数に存在しないこと、及び、実時間で回復できることである。このため、図９に示すように、受信ノード側でパケットデータの消失を検知し、訂正することができる前方誤り訂正（ＦＥＣ：Forward Error Correction）の技術が広く用いられている。
【０００４】
現在、ＦＥＣの方式としてディジタル放送や物理記録媒体の分野ではリード・ソロモン符号法（ＲＳ符号）が用いられている。ＲＳ符号はブロック符号の一つで、ある程度のシンボルを一まとめにして（これをブロック長と呼ぶ）、それに対するパリティシンボルを生成し、オリジナルシンボルとパリティシンボルを一緒に伝送する。ＲＳ符号はガロア体上の演算を行う必要があるため、ブロック長を長くすることが実質的に難しい点とブロック長の細かい調整が難しい点が欠点である。
【０００５】
一方で、シャノン限界に迫る通信路符号方式であるＬＤＰＣ(Low Density Parity Check)が知られている。ＬＤＰＣは検査行列として、疎なランダム行列を用い、タナーグラフを用いたBelief Propagation法による最尤法が知られている。検査行列の行数がパリティシンボル数に対応し、列数がブロック長に対応している。そのため、ブロック長を細かく調整することが可能である。また、２を法とする２元の排他的論理演算のみで完結するため、ブロック長が大きい場合でも実時間内で誤り検出と訂正が可能である。
【０００６】
さらに、ＵＤＰ／ＩＰプロトコル上での伝送を考える場合、伝送過程で誤りが生じたパケットは下位のデータリンク層のプロトコルによって破棄、または完全回復される。このため上位層で消失パケットの検出をする必要がない。すなわち、消失パケットの位置が検出された状態以後の消失訂正のみを行うＦＥＣ方式（図１０）で十分である。
【０００７】
ＬＤＧＭ符号方法は、ＬＤＰＣ符号の部分集合で、消失パケットの位置情報を予め外部から与えることで消失訂正を高速に計算できるＦＥＣ符号方式である（例えば、非特許文献１参照）。このため、マルチキャストを考えたＵＤＰ／ＩＰ伝送における消失訂正機構に適している。
【０００８】
ここで具体的なＬＤＧＭ符号の符号過程と復号過程を簡単に触れることにする。ＬＤＧＭ符号では、図１１に示すように、検査行列Ｈの検査シンボル部分が階段行列である特徴を持つ。この検査行列ＨをもつＬＤＧＭ符号を考えて、検査方程式より送信するシンボル列ｘ=（ｘ０ｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｘ７）からパリティシンボル列ｐ=（ｐ０ｐ１ｐ２ｐ３ｐ４ｐ５）を以下のように生成する。
【０００９】
ｐ０＝ｘ０＋ｘ５＋ｘ７                          （１）
ｐ０＋ｐ１＝ｘ１＋ｘ２＋ｘ６                          （２）
ｐ１＋ｐ２＝ｘ０＋ｘ３＋ｘ５                          （３）
ｐ２＋ｐ３＝ｘ１＋ｘ４＋ｘ６                          （４）
ｐ３＋ｐ４＝ｘ２＋ｘ４＋ｘ７                          （５）
ｐ４＋ｐ５＝ｘ０＋ｘ２＋ｘ３                          （６）
ここでは、シンボル間は２を法とする加法演算"＋"、すなわち、ＸＯＲが定義されていると仮定する。実際には、ここで生成されたパリティシンボルを付加して伝送路へ送信され、伝送路で消失などのシンボルロスが発生した場合に、受信ノードではこのパリティシンボルを用いて誤り回復が行われる。
【００１０】
次に、この伝送路で誤りが発生した場合のＬＤＧＭ復号によるシンボル回復の過程を説明する。
【００１１】
消失した誤りシンボルの位置は伝送路から与えられるので、既知である。例としてｘ０とｘ４ｐ２のシンボルが誤って受信された場合を考える。このとき、検査方程式を用いて、
・式（１）からｘ０＝ｐ０＋ｘ５＋ｘ７
・式（５）からｘ４＝ｐ３＋ｐ４＋ｘ２＋ｘ７
・式（３）からｐ２＝ｐ１＋ｘ０＋ｘ３＋ｘ５
としてそれぞれの誤り受信したシンボルを回復することが可能である。ここで問題になるのは、どの方程式をどの順序で解くかという点にある。
【００１２】
ＬＤＧＭ符号法の符号過程では、並列化アルゴリズムが実現されている（例えば、非特許文献２参照）。このため、符号化時には高速に一定時間内で計算可能である。一方で、同符号法の復号過程では、誤りシンボルの数や位置によって計算時間が異なる。このため、復号過程での一定時間内でのアルゴリズムが必要とされている。
【００１３】
次に、検査行列ＨがＭ×Ｎ行列のＬＤＧＭ符号を考える。このＬＤＧＭ復号法は基本的に２を法に持つ素体上のＭ元１次方程式を解く過程である。未知変数は消失したシンボルである。検査行列の１行は１検査方程式に、１列は１シンボルに対応する。ＬＤＧＭ符号では一つの検査方程式の中にただ一つのみ誤りが発生したシンボルを含むときに限り誤り訂正が可能である。このため、図１２に示すように、一般的なＬＤＧＭ復号の誤り訂正過程は単一誤りを含む検査方程式を探して、誤りを一つずつ訂正することになる。すなわち、以下が従来のＬＤＧＭ復号の方法である。
【００１４】
１．検査行列Ｈを行の方向に走査し、誤りをただ一つのみ含む行がなくなるまで以下の作業を続ける。
【００１５】
２．見つかった行より、１つのシンボルを訂正する。
【００１６】
３．上記１．に戻る。
【００１７】
また、ＬＤＧＭ符号法で用いられる検査行列Ｈを実装上での表現について考える。誤り訂正符号の検査行列Ｈを表現する場合に、一般的に、プログラムでは同じ行数と列数の積の分の配列を用意する。しかし、ＬＤＧＭ符号法の検査行列Ｈは非常に疎で、かつ要素も零と非零の２値しかないため（これを２元という）、メモリを効率的にかつ高速に走査できる行列表現が必要である。例えば、各列に非零が３要素（列重みが３）である１０００×２０００の検査行列Ｈの場合、列方向には非零が３要素しかなく、その他の９９７要素は零である。この情報をメモリ上に持っておくのは非常に非効率である。さらに、列方向に走査する場合にも、非零の場所を探すのに時間がかかることになるため、非効率である。
【００１８】
さらに、ＬＤＧＭ復号法では、一つの検査方程式を解き、一つのシンボル誤りを回復した場合に、今回復したシンボルを含む検査行列への影響を及ぼす。このため、検査行列Ｈ内において、あるシンボル（列）を固定して、その列内の非零の行（検査方程式）を走査し、さらに、その行内の非零の列を走査する、というような列と行の非零要素を交互に走査することが主な処理になる。このため、検査行列Ｈ内の非零の要素を軸として列と行を高速に相互に走査できる必要がある。
【非特許文献１】Vincent ROCA at el.: "Design, Evaluation and comparison of Four Large Block FEC Codecs, LDPC, LDGM, LDGM Staircase and LDGM Triangle, plus a Reed-Solomon Small Block FEC Codec", INRIA (2004)
【非特許文献２】北村、白井、外村、藤井："超高精細映像のロバスト伝送に向けた並列化ＬＤＧＭ符号による高速誤り訂正の検討"、信学技報、 vol. 107, no.244, CS2007-28, pp.37-42, 2007年10月
【発明の開示】
【発明が解決しようとする課題】
【００１９】
上述したＬＤＧＭ復号アルゴリズムでは、一つの検査方程式が解決し、すなわち、１つの消失したシンボルが回復できた場合、その回復したシンボルを含み、かつ、まだ解決していない行の検査方程式の未知シンボルは一つ減ることになる。このため、一つのシンボルが解決した後、再度全ての未決の方程式を走査し、解決可能な方程式を検出する必要がある。これにはO（N！）の計算時間が必要である。すなわち、ブロック長を大きくする場合、パケットロスが増えた場合には爆発的に計算量が増加する。ゆえに、ブロック長を大きくすることができない。
【００２０】
本発明は、上記の点に鑑みなされたもので、ＬＤＧＭ復号処理の計算量と計算時間を小さくし、巨大ブロック長を用いた場合でも、ライブストリーミング伝送に使用しうるリアルタイム処理を実現することが可能な通信情報の復号化方法及び復号化装置を提供することを目的とする。
【課題を解決するための手段】
【００２１】
図１は、本発明の原理を説明するための図である。
【００２２】
本発明（請求項１）は、LDGM符号化された通信情報の復号化方法であって、
LDGM復号装置において、
受信データの検査行列から、１行が１つの検査方程式に対応する要素数Mの構造体ROWと、１列が１シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成ステップ（ステップ１）と、
検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査ステップ（ステップ２）と、
誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正ステップ（ステップ３）と、
シンボル受信状態に応じて検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定ステップ（ステップ４）と、
依存関係がない検査方程式のシンボル回復を並行して処理する並行処理ステップ（ステップ５）と、の少なくとも１つのステップを行う。
【００２３】
また、本発明（請求項２）は、構造表現形式生成ステップにおいて、
構造体ROWを、
自行を示す行番号：ｉ；
検査行列Hの第ｉ行で非零の列番号を保持するリストLcol；
自行が回復させたシンボルの列番号：Rcol；
の要素からなるものとし、
構造体COLUMNを、
自列を示す列番号：ｊ；
検査行列Ｈの第ｊ列で非零の行番号を保持するリスト：Ｌrow；
自列のシンボルを回復した検査方程式の行番号：Ｒrow；
自列の示すシンボルの誤り状態を示すフラグ：Ｆ（誤りなく受信／検査方程式によって回復／誤っている）；
の要素からなるものとする。
【００２４】
また、本発明（請求項３）は、検査方程式走査ステップにおいて、
検査方程式走査ステップにおいて、
メインルーチンから呼び出されるサブルーチン（関数Ｆ（Ｐ））を、
集合Ｐの全ての要素に対して、誤りを一つだけ含む行（検査方程式）を順に見つけ、見つかった各行（検査方程式）に対して、
誤り訂正処理を行い、
誤り訂正したシンボルを含む他の行の集合を集合Ｐ'として定義し、
Ｆ（Ｐ'）を実行する操作を行うものと定義し、
メインルーチンにおいて、
集合Ｐに検査行列全体の要素を設定し、
関数Ｆ（Ｐ）を実行する。
【００２５】
また、本発明（請求項４）は、誤り訂正ステップにおいて、
回復できない誤りシンボル数が所定の値を超えた場合に、送信ホストに向けた再送要求、または、代替回復処理を行う。
【００２６】
また、本発明（請求項５）は、依存関係確定ステップにおいて、
シンボル受信状態に応じて検査方程式を分類する際に、
シンボルの受信状態が、誤りなく受信した完全受信、または、誤って受信したが、他の検査方程式により回復された回復受信、または、誤って受信した消失受信のいずれであるかを判定し、
回復受信の場合は、シンボル回復時の検査方程式を記録して一上位、一下位の依存関係を確定し、
検査方程式の依存木を作成する。
【００２７】
また、本発明（請求項６）は、請求項５において検査方程式の依存木を作成する際に、
根となる検査方程式から走査を行い、順に一回の検査方式を辿り、根となる検査方程式ラベルを付与する。
【００２８】
また、本発明（請求項７）は、請求項６において、一上位の依存検査方程式が複数の場合には、該依存検査方程式のラベルをマージして根の検査方程式リストに追加する。
【００２９】
図２は、本発明の原理構成図である。
【００３０】
本発明（請求項８）は、LDGM符号化された通信情報の復号化装置であって、
受信データの検査行列から、１行が１つの検査方程式に対応する要素数Mの構造体ROWと、１列が１シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成手段１１０と、
検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査手段１２１と
誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正手段１２２と、
シンボル受信状態に応じて検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定手段１２３と、
依存関係がない検査方程式のシンボル回復を並行して処理する並行処理手段１３０と、を有する。
【００３１】
また、本発明（請求項９）は、構造表現形式生成手段１１０において、
自行を示す行番号：ｉ；
検査行列Hの第ｉ行で非零の列番号を保持するリストLcol；
自行が回復させたシンボルの列番号：Rcol；
の要素を有する構造体ROWを生成し、
自列を示す列番号：ｊ；
検査行列Ｈの第ｊ列で非零の行番号を保持するリスト：Ｌrow；
自列のシンボルを回復した検査方程式の行番号：Ｒrow；
自列の示すシンボルの誤り状態を示すフラグ：Ｆ（誤りなく受信／検査方程式によって回復／誤っている）；
の要素を有する構造体COLUMNを生成する手段を含む。
【００３２】
また、本発明（請求項１０）は、検査方程式走査手段１２１において、
メインルーチンから呼び出されるサブルーチン（関数Ｆ（Ｐ））を、
前記集合Ｐの全ての要素に対して、誤りを一つだけ含む行（検査方程式）を順に見つけ、見つかった各行（検査方程式）に対して、
誤り訂正処理を行い、
誤り訂正したシンボルを含む他の行の集合を集合Ｐ'として定義し、
Ｆ（Ｐ'）を実行する操作を行うものと定義し、
メインルーチンにおいて、
集合Ｐに検査行列全体の要素を設定し、関数Ｆ（Ｐ）を実行する手段を含む。
【００３３】
また、本発明（請求項１１）は、誤り訂正手段１２２において、
回復できない誤りシンボル数が所定の値を超えた場合に、送信ホストに向けた再送要求、または、代替回復処理を行う手段を含む。
【００３４】
また、本発明（請求項１２）は、依存関係確定手段１２３において、
シンボルの受信状態が、誤りなく受信した完全受信、または、誤って受信したが、他の検査方程式により回復された回復受信、または、誤って受信した消失受信のいずれであるかを判定し、回復受信の場合は、シンボル回復時の検査方程式を記録して一上位、一下位の依存関係を確定し、検査方程式の依存木を作成する手段を含む。
【００３５】
また、本発明（請求項１３）は、請求項１２の依存関係確定手段１２３において、
検査方程式の依存木を作成する際に、根となる検査方程式から走査を行い、順に一回の検査方式を辿り、根となる検査方程式ラベルを付与する手段を含む。
【発明の効果】
【００３６】
上記のように本発明によれば、ＬＤＧＭ符号の検査行列において、行列の要素が２元、かつ、疎行列である場合、疎の行列表現を非零の場所のみを行と列のリンク（関係性）で表現させることで、メモリ使用効率と非零要素へのアクセス速度が向上する。
【００３７】
また、ＬＤＧＭ復号過程において、誤り訂正可能なシンボルを含む検査方程式、すなわち、検査行列の行を開始点として、その回復されたシンボルに関係する他の業のみを順次走査することで、誤り訂正可能な全ての方程式を一巡回のみで全て見つけることができる。
【００３８】
これにより、マルチキャストによる大容量データストリーム転送における誤り回復処理を高速化でき、従来不可能であった長ブロック長のパケットデータを処理することが可能となる。
【発明を実施するための最良の形態】
【００３９】
以下、図面と共に本発明の実施の形態を説明する。
【００４０】
図３は、本発明の一実施の形態におけるＬＤＧＭ復号装置の構成図である。
【００４１】
当該ＬＤＧＭ復号装置１００には、受信データと誤り位置情報が入力され、復号データが出力される。
【００４２】
同図に示すＬＤＧＭ復号装置１００は、２元疎行列リンク型表現生成部１１０、一巡回解決検査方程式走査部１２０、並列復号演算部１３０から構成される。
【００４３】
２元疎行列リンク方表現生成部１１０は、検査行列が２元疎行列である特性を利用してＭ×Ｎ個の要素数をＭ＋Ｎ個の変数に低減する構造表現形式（２元疎行列の双方向リンク型表現）に変換する。
【００４４】
一巡回解決検査方程式走査部１２０は、誤り訂正可能な方程式の走査部１２１、走査方程式解決キュー１２２、検査方程式解決依存グループラベリング部１２３から構成される。
【００４５】
誤り訂正可能な方程式の走査部１２１は、検査行列の誤りシンボルを回復後に全ての検査方程式を走査して解決可能な方程式を抽出して検査方程式解決キュー１２２に出力する。誤り訂正可能な検査方程式の行走査完了後に誤り訂正を行う。
【００４６】
走査方程式解決キュー１２２は、計算量の少ない全検査方程式を走査する処理と計算量の多い誤りシンボル回復処理とを分離処理する。
【００４７】
検査方程式解決依存グループラベリング部１２３は、シンボル受信状態に応じて検査方程式を分類し、当該検査方程式の一上位、一下位の依存関係を確定する。
【００４８】
並列復号演算部１３０は、依存グループ計算並列分類部１３１、並列計算キュー１３２、検査方程式計算部１３３、直列計算キュー１３４、検査方程式計算部１３５から構成される。
【００４９】
依存グループ計算並列分類部１３１は、並列計算キュー１３２を利用して依存関係がない検査方程式のシンボル回復を並行して処理する。
【００５０】
以下に、上記の各構成要素について詳細に説明する。
【００５１】
●２元疎行列リンク型表現生成部１１０：
まず、２元疎行列リンク型表現生成部１１０について説明する。
【００５２】
ＬＤＧＭを含む疎行列を用いたブロック符号では、一般に２元疎行列を用いる。ＬＤＧＭ符号では、この２元疎行列の１行が１つの検査方程式、１列がシンボルに相当する。ＬＤＧＭ符号の復号過程では検査行列を解き、シンボルを回復させ、さらにそれによって解決可能になった別の検査行列を解くことを繰り返す。このため、２元疎行列は非零の要素を基準にして行と列の両方向に走査を行うことが主な処理になる。これらの計算を効率的に行うには、方程式を解く順序、方程式間の依存関係を調べ、並列的に行う必要がある。
【００５３】
これは行を表す要素数Ｍの構造体ROW、及び列を表す要素Ｎの構造体COLUMNである。構造体ROW、及び、構造体COLUMNは以下の要素を持つ。
【００５４】
・ROW
−自行を示す行番号：ｉ
−検査行列Ｈの第ｉ行で非零の列番号を保持するリスト：Ｌcol
−自行が回復させたシンボルの列番号：Ｒcol
・COLUMN
−自列を示す列番号：ｊ
−検査行列Hの第ｊ列で非零の行番号を保持するリスト：Lrow
−自列のシンボルを回復した検査方程式のＲrow
−自列の示すシンボルの誤り状態を示すフラグ：Ｆ（誤りなく受信、検査方程式によって回復、誤っている）
以上の表現を用いると、管理すべき資源は、検査行列ＨがＭ×Ｎ行列の場合、（Ｍ＋Ｎ）個の変数のみである。
【００５５】
上記のように生成されたROWとCOLUMNをメモリに格納する。
【００５６】
●一巡回解決検査方程式走査部１２０：
＜誤り訂正可能な方程式の走査部１２１＞
ＬＤＧＭ符号の復号過程では、ある行の検査方程式によって回復されたシンボルの列が、さらに他の行の検査方程式に影響を与える。このため、誤り訂正可能な方程式の走査部１２１において、回復されたシンボルに関係する検査方程式を順次走査することで、走査回数を大きく削減できる。逆に、未解決の検査方程式の解決可能な状態は、その検査行列が含むシンボルが他の方程式によって回復された場合にのみ変化する。ゆえに、回復されたシンボルを軸にして、そのシンボルを含む全ての検査方程式を順次走査することで解決可能な検査方程式をもれなく見つけ出すことが可能になる。さらに、ＬＤＧＭ符号は検査行列Ｈが疎行列であるため、あるシンボルを含む検査行列の数は検査行列Ｈの行数Ｍに対して十分小さい。これにより、１巡回で検査行列の解く順序が決定できる。
【００５７】
以下に提案手法のアルゴリズムである一巡回ＬＤＧＭ復号法を示す。
【００５８】
・関数（サブルーチン）Ｆ（Ｐ）の定義
１．集合Ｐが空き集合であればこの関数を終了する。相でなければ以下の処理を行う。
【００５９】
２．集合Ｐの全ての要素に対して、誤りを一つだけ含む行（検査方程式）を順に見つける。ここで見つかった各行（検査方程式）に対して以下の操作を行う。
【００６０】
（ａ）誤り訂正処理を行う。
【００６１】
（ｂ）２ａで訂正したシンボルを含むほかの行の集合を集合Ｐ'として定義する。
【００６２】
（ｃ）Ｆ（Ｐ'）を実行する。（再帰呼び出し）
３．関数Ｆの終了。
【００６３】
・手順（メインルーチン）
１．集合Ｐに検査行列全体の要素を設定する。
【００６４】
２．Ｆ（Ｐ）を実行する。
【００６５】
３．終了。
【００６６】
＜検査方程式解決キュー１２２＞
ＩＰ伝送において、誤り訂正の対象にするシンボルは、ビットとしてではなく、複数のビットを一まとめにしたパケット単位で扱う。このとき、一つの検査方程式を用いてシンボル、すなわち、パケットを回復させる計算は多ビット間のベクトル演算であるため、解決可能な検査方程式の走査に比べて計算量が大きい。ここで、一つの検査行列のシンボル（パケット）回復のための計算量Ｎrecoverを評価するために、１ビット当たりのＸＯＲ計算回数をNxor、Ｍ×Ｎの検査行列Hの第ｉ行内の列重みＤi、パケット長をPビットとする。さらに列重みＤiは、一般に検査行列Ｈの列数に単調増加的に依存するので、Ｄi＝Ｄi（Ｎ）とする。このときのＮrecoverは、以下の式で与えられる。
【００６７】
Ｎrecover=Ｎxor×Ｐ×Ｄi= Nxor×Ｐ×Ｄi（Ｎ）                  （７）
このため、検査行列のシンボル回復の計算回数Ｎrecoverは、パケット長及びブロック長に依存して大きくなる。
【００６８】
一方で、回復処理可能な検査方程式の行走査の単位行あたりの計算回数Nscanについては、その行内に含まれるシンボルの列の受信状態のみを見ればよい。この単位シンボルあたりの受信状態検査の計算量をNflagとすれば、Nscanは以下で与えられる。
【００６９】
Nscan= Nflag×Ｄi（Ｎ）                                      （８）
また、実際にNflag≪Ｎxorより、Nscan≪Ｎrecoverとなり、これは誤り訂正可能な検査方程式の行の走査時間よりも、誤り可能な検査方程式の回復処理の方が圧倒的に計算量が多いことを意味している。さらに、ブロック長が固定されている場合には、パケット長に関係なく、誤り訂正可能な検査方程式の行の走査処理は一定になる。
【００７０】
以上の理由により、この２つの処理を分割することで、計算量の大きい誤り訂正処理を行う以前に、伝送路でロスしたシンボル数とその位置、及び、復号処理によって回復可能なシンボル数とその位置を知ることができる。これらの伝送路でロスしたシンボルの総数とその位置及び、復号処理（並列復号演算部１３０の処理）によって回復可能なシンボルの総数とその位置を誤り訂正の統計的結果として出力することが可能である。よって回復できないシンボル数が多い場合などには、FECではなく送信ホストに向けての再送信要求など、他のシンボル回復方法などと組み合わせることが極めて容易になる。
【００７１】
また、キューと回復処理演算実行を分別することによって、検査方程式の解決可能順序が分かるため、後に述べる並列化処理が可能なる。
【００７２】
＜検査方程式解決依存グループラベリング部１２３＞
既存のLDGM復号では、一つの検査方程式の結果が他の方程式に影響を及ぼすため、逐次的に検査方程式を解く方法が用いられる。一方、本発明の一巡回LDGM復号順序決定走査では、解決可能検査方程式を見つけ、これを根にして逐次的に別の解決可能検査方程式を走査する。このため、ひとつの検査方程式がどの他の検査方程式に依存しているかが容易にわかる。依存する方程式同士を一つのグループと識別できれば、依存関係で独立したグループ分けが可能になる。これは、LDGM復号において、並列処理が可能であることを意味する。
【００７３】
図４は、本発明の一実施の形態における検査方程式解決依存グループラベリングを示す図である。構成要素は以下の通りである。
【００７４】
１．シンボルの受信状態の属性；
２．シンボル回復時の上位依存の検査方程式の識別；
３．検査方程式の依存木の作成；
以下に、上記の各内容について説明する。
【００７５】
１．シンボルの受信状態の属性；
シンボルの受信状態を次の３つに分類する。
【００７６】
・完全受信：誤りなく受信した。
【００７７】
・回復受信：誤って受信したが、他の検査方程式により回復された。回復方程式番号を記録。
【００７８】
・消失受信：誤って受信した。
【００７９】
また、「回復受信」の場合には、どの検査方程式によって回復されたのかを記録しておく。この方程式を回復方程式と呼ぶことにする。この３状態をシンボルの属性として持たせる。
【００８０】
２．シンボル回復時の依存検査方程式の記録；
一つの検査方程式がシンボルを回復するのは、その検査方程式内のシンボル状態が唯一の消失受信、それ以外は完全受信または回復受信の場合がある。この、今注目する検査方程式を解決方程式と呼ぶことにする。このとき、解決方程式内のシンボル状態を調べ、回復受信シンボルの回復方程式を記録する。さらに、回復方程式へ解決方程式を記録させる。これにより、検査方程式の一上位、一下位の依存関係が確定する。
【００８１】
以上の過程をまとめると次のようになる。
【００８２】
（１）検査方程式内の全てのシンボルの受信状態を調べる。
【００８３】
（２）もしシンボル状態が「回復受信」であれば以下の操作を実行する。
【００８４】
（ａ）注目しているシンボルの回復方程式を解決方程式に記録する。
【００８５】
（ｂ）注目しているシンボルの回復方程式に解決方程式を記録する。
【００８６】
３．検査方程式の依存木の作成；
上記の２．で行った一上位、一下位の依存方程式の記録を基に検査方程式全体の依存関係の木をつくる。まずは、根となる検査方程式から走査を行い、順次に一下位の検査方程式を辿りつつ、根となる検査方程式ラベルを付加していく。但し、一上位の依存方程式は一つではない。これにより、一上位の依存方程式が複数の場合には、マージして根の検査方程式リストとして記録していく。
【００８７】
以下にそのアルゴリズムを示す。
【００８８】
（１）全ての根検査方程式に一意名ラベルを付加する。
【００８９】
（２）全ての根検査方程式からはじめ、一下位方程式がなくなるまで以下の操作を実行する。
【００９０】
（ａ）根検査方程式からはじめ、一下位方程式がなくなるまで以下の操作を実行する。
【００９１】
−一上位の依存方程式の根検査方程式ラベルをリストにマージして追加する。
【００９２】
以上の過程により、全ての解決方程式には一つ以上の根検査方程式ラベルが割り当てられる。
【００９３】
●並列復号演算部１３０
＜依存グループ計算並列分割部１３１＞
上記の検査方程式解決依存グループラベリング部１２３により、全ての解決方程式にグループラベルが付加される。この情報を基に並列計算可能なタスクに振り分ける。この振り分けは、２段階に分けられる。まず、検査方程式をみて、所属する根方程式のグループが単一の場合、それらは完全並列化可能である。これらを並列処理（並列計算キュー１３２）に割り当て、並列計算ができないものは直列計算キュー１３４に割り当てる。次に、残りの検査方程式（検査方程式計算１３３）を逐次的に解決する。検査方程式計算部１３５では、検査方程式計算部１３３と直列計算キュー１３４の演算結果が入力されると最終となる検査方程式の計算を行う。以上で、全ての解決可能な検査方程式の処理が終了し、復号されたパケットが出力される。
【実施例】
【００９４】
［１］  最初に、２元祖行列リンク型表現生成部１１０における２元疎行列の双方向リンク方表現の例を説明する。
【００９５】
図５は、本発明の一実施例の検査行列を２元疎行列の双方向リンク方表現で表す例を示す。同図は、図１１の検査行列Ｈを２元疎行列の双方向リンク表現で表す例を示す。検査行列Ｈは（６×１４）行列であるため、行を示す構造体変数ROWの数は６、列を示す構造体変数COLUMNの数は１４である。それぞれを、
ROWi  （ｉ=０，１，２，…，５），  COLUMNj  （ｊ=０，１，２，…，１３）
と表すことにする。また、各構造体変数の持つ要素には、演算子"．"で参照するとする。例えば、ROWiの要素である行番号ｉはROWi.iで表す。このとき、Ｈの第０行，第５行を表すROW０，ROW５及び、第０列，第２列，第１３列を表すCOLUMN０，COLUMN２，COLUMN１３は図５の通りである。
【００９６】
ここで実際に、２元疎行列の双方向リンク型表現を用いて、図１１のシンボル受信側の場合に、一巡回ＬＤＧＭ復号行順決定走査を行うことを説明する。
【００９７】
はじめに文章による処理過程の説明は以下の通りである。
【００９８】
１）第０行に注目する。この行が示す検査方程式は、第０列が示すシンボルのみを消失シンボルとして含むので回復可能である。このとき、第０行の検査方程式が第０列のシンボルを回復したことを記録する。
【００９９】
２）続いて、この回復シンボルを含む別の行を走査すると第２行、第５行が該当する。
【０１００】
３）第２行が回復可能であるかを調べると第１０列のシンボルのみ消失受信であるため、回復可能である。
【０１０１】
続いて、上記の過程を２元疎行列の双方向リンク型表現を用いて表すと以下のようになる。
【０１０２】
１）ROW０．Ｌcolの全てを順次変数ｊに代入し（つまり、ｊ＝０，５，７，８である）、COLUMN０．Ｆが消失受信である列を調べる。COLUMN０．Fのみ消失受信であるため、ROW０は回復可能である。さらに、ROW０．Ｒcol＝０とする。
【０１０３】
２）続いて、COLUMN０．Ｌrowの全てをｉに代入する。つまりｉ＝２，５である。
【０１０４】
３）COLUMN２に注目し、ROW２．Ｌcolの全てをｊに代入し、COLUMNｊ．Fが消失受信である列を調べる。COLUMNｊ0．Fのみ消失受信であるため回復可能である。
【０１０５】
このように、２元疎行列の双方向リンク型表現を用いると、メモリ効率を非常に高め、巨大な検査行列Ｈを持つブロック符号であっても実現可能である。さらに、一巡回ＬＤＧＭ復号行順決定走査で頻繁に行われる検査行列Ｈの行と列の間に交互走査を高速に行える。
【０１０６】
［２］一巡回解決検査方程式走査部１２０における、一巡回ＬＤＧＭ復号行順決定走査と依存木について説明する。
【０１０７】
図１１の検査行列Ｈを用いて復号化したシンボルの復号過程を以下に示す。
【０１０８】
１）第０行より走査して回復可能なシンボルを含む行の有無を調べる。
【０１０９】
２）第０行より第１列のシンボルを回復可能。
【０１１０】
（ａ）第０行のシンボルを回復。
【０１１１】
（ｂ）第０行を走査して回復可能な行の有無を調べる。
【０１１２】
（ｃ）第２行より第１０列のシンボルが回復可能。
【０１１３】
i．第１０列のシンボルを回復。
【０１１４】
ii．第１０列を走査して回復可能な行の有無を調べる。
【０１１５】
Ａ．該当なし
iii．該当なし。
【０１１６】
（ｄ）該当なし。
【０１１７】
３）第４行より第４列のシンボルが回復可能。
【０１１８】
（ａ）第４列のシンボルを回復。
【０１１９】
（ｂ）第４列を走査して回復可能な行の有無を調べる。
【０１２０】
（ｃ）第３行より第６列のシンボルが回復可能とする。
【０１２１】
i．第６列のシンボルを回復。
【０１２２】
ii．第６列を走査して回復可能な行の有無を調べる。
【０１２３】
iii．該当なし。
【０１２４】
（ｄ）該当なし。
【０１２５】
４）該当なし
５）終了。
【０１２６】
実際に、受信されたシンボルは検査行列Ｈの各列に対応する。はじめに、検査行列の列方向に走査して、誤りシンボルをただ一つ含む行、すなわち、誤りシンボルを回復可能な検査方程式を示す行を見つける。続いて、その回復可能な誤りシンボルを検査方程式より回復させる。図１１の例では、第０行の検査方程式より第０列のシンボルが回復できる。次に、ここで回復できた第０列のシンボルを検査方程式に含む列に注目する。このとき、第２行の検査方程式より第１０列のシンボルを回復可能である。これを繰り返すことで、図１１の場合にはわずか６回の行走査のみでＬＤＧＭ復号処理が完了できる。
【０１２７】
［３］次に、検査方程式解決依存グループラベリング部１２３におけるＬＤＧＭ復号の依存グループラベリングと依存グループ計算並列分割部１３１における並列分割について説明する。
【０１２８】
図１１の例において、ＬＤＧＭ復号の並列化を行う過程を説明する。図６は、本発明の一実施例の検査方程式の依存木とグループラベリングの例を示す。上記の［２］の過程により、以下に示すようにグループラベルが付加されている。
【０１２９】
・第０行：グループ０
・第１行：グループ１
・第２行：グループ０
・第３行：グループ０、グループ１
・第４行：（グループ０）
・第５行：（グループ０）
よって単一のグループラベルが付加されている行の検査方程式、すなわち、第０行、第２行と第１行は並列計算キューに割り当てることが可能であり、複数のグループラベルが付加されている第３行の検査方程式は直列計算キューに割り当てられ並列計算キューが終了した後に実行される。
【０１３０】
［４］次に、超高精細映像伝送における高速LDGM符号を使用したロバスト伝送について説明する。
【０１３１】
図７は、本発明の一実施例のLDGM符号を用いたJPEG2000ロバスト伝送の例を示す。ここでは、JPEG2000を用いた映像符号化を行い（ステップ１０１）、それをパケット分割し（ステップ１０２）、イーサネットフレーム長に適応するブロック長を決定する。そのブロック長を元に検査行列Hを生成し、LDGM符号化を行う（ステップ１０３）。図８は、本発明の一実施例のUDP/IP通信路におけるLDGM符号のパケット分割を示す。このとき、受信時に消失したパケットを同定するためにLDGMブロック番号、及び、パケット番号をヘッダとして送信シンボル(分割されたJPEG2000データ)に付加する（ステップ１０４）。その後、UDP/IPを用いて受信側に渡る（ステップ１０５）。
【０１３２】
伝送路中の送信データの誤りに関しては、イーサネット以下で誤り検出が保証されており、この段階で誤りを含むパケットは排除される。つまり、UDP/IPで受信処理されるパケットは誤りを含まない。このため、送信時に付加したヘッダから消失したパケット位置が同定できる（ステップ１０８）。この同定された消失位置を基にLDGM復号を行う（ステップ１０９）。その後、JPEG2000符号単位でパケットを合成し（ステップ１１０）、JPEG2000復号を行う（ステップ１１１）。
【０１３３】
上記のように、本発明によれば、ブロック長NシンボルのLDGM符号の復号処理を考えた場合、本発明で２種類の高速が実現された。行列表現による行及び列の走査の高速化、及び、誤り訂正可能判別の行操作の高速化である。
【０１３４】
行列表現による高速化について、従来手法では、列重みｄ（≪M）の列内を走査する場合にM時間が必要であったが、本発明の２元疎行列リンク型表現を用いた場合では、d時間で操作可能になった。行内の走査も同様である。また、実装段階で管理すべきメモリ使用量（変数・オブジェクトの数）についても、従来手法では要素数がM×Nの配列を用意する必要があったが、本発明では、要素数M+Nの配列のみで可能になった。
【０１３５】
また、一つの誤りシンボルが訂正できた後の、誤り訂正可能な行を走査する場合の高速化について、従来の手法はO（N！）の計算時間を要した。それに対して、本発明ではO（N）の線形計算時間でこれが可能になった。したがって、大きいブロック長を持つLDGM符号が実現可能になった。
【０１３６】
なお、上記の図３に示すLDGM復号装置の構成要素の動作をプログラムとして構築し、LDGM復号装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１３７】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１３８】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１３９】
本発明は、ＩＰネットワークにおけるLDGM符号システムの復号処理に適用可能である。
【図面の簡単な説明】
【０１４０】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態におけるLDGM復号装置の構成図である。
【図４】本発明の一実施の形態における検査方程式解決依存グループラベリングを示す図である。
【図５】本発明の一実施例の検査行列を２元疎行列の双方向リンク型表現で表す例である。
【図６】本発明の一実施例の検査方程式と依存木とグループラベリングの例である。
【図７】本発明の一実施例のLDGM符号を用いたJPEG2000のロバスト伝送の例である。
【図８】本発明の一実施例のUDP/IP通信路におけるLDGM符号のパケット分割を示す図である。
【図９】通信路と従来の誤り訂正スキームを示す図である。
【図１０】イーサネット通信を用いた誤り訂正機構を示す図である。
【図１１】検査行列と受信状態の簡易例である。
【図１２】従来のLDGM符号の復号方式を示す図である。
【符号の説明】
【０１４１】
１００  LDGM復号装置
１１０  構造表現形式生成手段、２元疎行列リンク型表現生成部
１２０  一巡回解決検査方程式走査部
１２１  検査方程式走査手段、誤り訂正可能な方程式の走査部
１２２  誤り訂正手段、検査方程式解決キュー
１２３  依存関係確定手段、検査方程式解決依存グループラベリング部
１３０  並行処理手段、並列復号演算部
１３１  依存グループ計算並列分割部
１３２  並列計算キュー
１３３  検査方程式計算部
１３４  直列計算キュー
１３５  検査方程式計算部
【図１】
2010081105.tif 000003
【図２】
2010081105.tif 000004
【図３】
2010081105.tif 000005
【図４】
2010081105.tif 000006
【図５】
2010081105.tif 000007
【図６】
2010081105.tif 000008
【図７】
2010081105.tif 000009
【図８】
2010081105.tif 000010
【図９】
2010081105.tif 000011
【図１０】
2010081105.tif 000012
【図１１】
2010081105.tif 000013
【図１２】
2010081105.tif 000014