"LDGM符号化された通信情報の復号化方法であって、LDGM復号装置において、受信データの検査行列から、1行が1つの検査方程式に対応する要素数Mの構造体ROWと、1列が1シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成ステップと、前記検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査ステップと、誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正ステップと、シンボル受信状態に応じて前記検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定ステップと、依存関係がない検査方程式のシンボル回復を並行して処理する並行処理ステップと、を行うものとし、前記検査方程式走査ステップにおいて、メインルーチンから呼び出されるサブルーチン関数FPを、前記集合Pの全ての要素に対して、誤りを一つだけ含む行検査方程式を順に見つけ、見つかった各行検査方程式に対して、誤り訂正処理を行い、誤り訂正したシンボルを含む他の行の集合を集合Pとして定義し、FPを実行する操作を行うものと定義し、メインルーチンにおいて、前記集合Pに検査行列全体の要素を設定し、前記関数FPを実行することを特徴とする通信情報の復号化方法。LDGM符号化された通信情報の復号化装置であって、受信データの検査行列から、1行が1つの検査方程式に対応する要素数Mの構造体ROWと、1列が1シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成手段と、前記検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査手段と誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正手段と、シンボル受信状態に応じて前記検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定手段と、依存関係がない検査方程式のシンボル回復を並行して処理する並行処理手段と、を有し、前記検査方程式走査手段は、メインルーチンから呼び出されるサブルーチン関数FPを、前記集合Pの全ての要素に対して、誤りを一つだけ含む行検査方程式を順に見つけ、見つかった各行検査方程式に対して、誤り訂正処理を行い、誤り訂正したシンボルを含む他の行の集合を集合Pとして定義し、FPを実行する操作を行うものと定義し、メインルーチンにおいて、集合Pに検査行列全体の要素を設定し、関数FPを実行する手段を含むことを特徴とする通信情報の復号化装置。上述したLDGM復号アルゴリズムでは、一つの検査方程式が解決し、すなわち、1つの消失したシンボルが回復できた場合、その回復したシンボルを含み、かつ、まだ解決していない行の検査方程式の未知シンボルは一つ減ることになる。このため、一つのシンボルが解決した後、再度全ての未決の方程式を走査し、解決可能な方程式を検出する必要がある。これにはONの計算時間が必要である。すなわち、ブロック長を大きくする場合、パケットロスが増えた場合には爆発的に計算量が増加する。ゆえに、ブロック長を大きくすることができない。本発明は、上記の点に鑑みなされたもので、LDGM復号処理の計算量と計算時間を小さくし、巨大ブロック長を用いた場合でも、ライブストリーミング伝送に使用しうるリアルタイム処理を実現することが可能な通信情報の復号化方法及び復号化装置を提供することを目的とする。図1は、本発明の原理を説明するための図である。本発明請求項1は、LDGM符号化された通信情報の復号化方法であって、LDGM復号装置において、受信データの検査行列から、1行が1つの検査方程式に対応する要素数Mの構造体ROWと、1列が1シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成ステップステップ1と、検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査ステップステップ2と、誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正ステップステップ3と、シンボル受信状態に応じて検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定ステップステップ4と、依存関係がない検査方程式のシンボル回復を並行して処理する並行処理ステップステップ5と、を行うものとし、検査方程式走査ステップステップ2において、メインルーチンから呼び出されるサブルーチン関数FPを、集合Pの全ての要素に対して、誤りを一つだけ含む行検査方程式を順に見つけ、見つかった各行検査方程式に対して、誤り訂正処理を行い、誤り訂正したシンボルを含む他の行の集合を集合Pとして定義し、FPを実行する操作を行うものと定義し、メインルーチンにおいて、集合Pに検査行列全体の要素を設定し、関数FPを実行する。図2は、本発明の原理構成図である。本発明請求項2は、LDGM符号化された通信情報の復号化装置であって、受信データの検査行列から、1行が1つの検査方程式に対応する要素数Mの構造体ROWと、1列が1シンボルに相当する要素数NのCOLUMNの構造表現形式を生成して記憶手段に格納する構造表現形式生成手段110と、検査行列の誤りシンボルを回復後に全ての検査方程式を走査する検査方程式走査手段121と誤り訂正可能な検査方程式の行走査完了後に誤り訂正処理を行う誤り訂正手段122と、シンボル受信状態に応じて検査方程式を分類し、該検査方程式の一上位、一下位の依存関係を確定する依存関係確定手段123と、依存関係がない検査方程式のシンボル回復を並行して処理する並行処理手段130と、を有し、検査方程式走査手段121は、メインルーチンから呼び出されるサブルーチン関数FPを、前記集合Pの全ての要素に対して、誤りを一つだけ含む行検査方程式を順に見つけ、見つかった各行検査方程式に対して、誤り訂正処理を行い、誤り訂正したシンボルを含む他の行の集合を集合Pとして定義し、FPを実行する操作を行うものと定義し、メインルーチンにおいて、集合Pに検査行列全体の要素を設定し、関数FPを実行する手段を含む。上記のように本発明によれば、LDGM符号の検査行列において、行列の要素が2元、かつ、疎行列である場合、疎の行列表現を非零の場所のみを行と列のリンク関係性で表現させることで、メモリ使用効率と非零要素へのアクセス速度が向上する。また、LDGM復号過程において、誤り訂正可能なシンボルを含む検査方程式、すなわち、検査行列の行を開始点として、その回復されたシンボルに関係する他の業のみを順次走査することで、誤り訂正可能な全ての方程式を一巡回のみで全て見つけることができる。これにより、マルチキャストによる大容量データストリーム転送における誤り回復処理を高速化でき、従来不可能であった長ブロック長のパケットデータを処理することが可能となる。以下、図面と共に本発明の実施の形態を説明する。図3は、本発明の一実施の形態におけるLDGM復号装置の構成図である。当該LDGM復号装置100には、受信データと誤り位置情報が入力され、復号データが出力される。同図に示すLDGM復号装置100は、2元疎行列リンク型表現生成部110、一巡回解決検査方程式走査部120、並列復号演算部130から構成される。2元疎行列リンク方表現生成部110は、検査行列が2元疎行列である特性を利用してM×N個の要素数をMN個の変数に低減する構造表現形式2元疎行列の双方向リンク型表現に変換する。一巡回解決検査方程式走査部120は、誤り訂正可能な方程式の走査部121、走査方程式解決キュー122、検査方程式解決依存グループラベリング部123から構成される。誤り訂正可能な方程式の走査部121は、検査行列の誤りシンボルを回復後に全ての検査方程式を走査して解決可能な方程式を抽出して検査方程式解決キュー122に出力する。誤り訂正可能な検査方程式の行走査完了後に誤り訂正を行う。走査方程式解決キュー122は、計算量の少ない全検査方程式を走査する処理と計算量の多い誤りシンボル回復処理とを分離処理する。検査方程式解決依存グループラベリング部123は、シンボル受信状態に応じて検査方程式を分類し、当該検査方程式の一上位、一下位の依存関係を確定する。並列復号演算部130は、依存グループ計算並列分類部131、並列計算キュー132、検査方程式計算部133、直列計算キュー134、検査方程式計算部135から構成される。依存グループ計算並列分類部131は、並列計算キュー132を利用して依存関係がない検査方程式のシンボル回復を並行して処理する。以下に、上記の各構成要素について詳細に説明する。●2元疎行列リンク型表現生成部110:まず、2元疎行列リンク型表現生成部110について説明する。LDGMを含む疎行列を用いたブロック符号では、一般に2元疎行列を用いる。LDGM符号では、この2元疎行列の1行が1つの検査方程式、1列がシンボルに相当する。LDGM符号の復号過程では検査行列を解き、シンボルを回復させ、さらにそれによって解決可能になった別の検査行列を解くことを繰り返す。このため、2元疎行列は非零の要素を基準にして行と列の両方向に走査を行うことが主な処理になる。これらの計算を効率的に行うには、方程式を解く順序、方程式間の依存関係を調べ、並列的に行う必要がある。これは行を表す要素数Mの構造体ROW、及び列を表す要素Nの構造体COLUMNである。構造体ROW、及び、構造体COLUMNは以下の要素を持つ。ROW-自行を示す行番号:i-検査行列Hの第i行で非零の列番号を保持するリスト:Lcol-自行が回復させたシンボルの列番号:RcolCOLUMN-自列を示す列番号:j-検査行列Hの第j列で非零の行番号を保持するリスト:Lrow-自列のシンボルを回復した検査方程式のRrow-自列の示すシンボルの誤り状態を示すフラグ:F誤りなく受信、検査方程式によって回復、誤っている以上の表現を用いると、管理すべき資源は、検査行列HがM×N行列の場合、MN個の変数のみである。上記のように生成されたROWとCOLUMNをメモリに格納する。●一巡回解決検査方程式走査部120:<誤り訂正可能な方程式の走査部121>LDGM符号の復号過程では、ある行の検査方程式によって回復されたシンボルの列が、さらに他の行の検査方程式に影響を与える。このため、誤り訂正可能な方程式の走査部121において、回復されたシンボルに関係する検査方程式を順次走査することで、走査回数を大きく削減できる。逆に、未解決の検査方程式の解決可能な状態は、その検査行列が含むシンボルが他の方程式によって回復された場合にのみ変化する。ゆえに、回復されたシンボルを軸にして、そのシンボルを含む全ての検査方程式を順次走査することで解決可能な検査方程式をもれなく見つけ出すことが可能になる。さらに、LDGM符号は検査行列Hが疎行列であるため、あるシンボルを含む検査行列の数は検査行列Hの行数Mに対して十分小さい。これにより、1巡回で検査行列の解く順序が決定できる。以下に提案手法のアルゴリズムである一巡回LDGM復号法を示す。関数サブルーチンFPの定義1.集合Pが空き集合であればこの関数を終了する。相でなければ以下の処理を行う。2.集合Pの全ての要素に対して、誤りを一つだけ含む行検査方程式を順に見つける。ここで見つかった各行検査方程式に対して以下の操作を行う。a誤り訂正処理を行う。b2aで訂正したシンボルを含むほかの行の集合を集合Pとして定義する。cFPを実行する。再帰呼び出し3.関数Fの終了。手順メインルーチン1.集合Pに検査行列全体の要素を設定する。2.FPを実行する。3.終了。<検査方程式解決キュー122>IP伝送において、誤り訂正の対象にするシンボルは、ビットとしてではなく、複数のビットを一まとめにしたパケット単位で扱う。このとき、一つの検査方程式を用いてシンボル、すなわち、パケットを回復させる計算は多ビット間のベクトル演算であるため、解決可能な検査方程式の走査に比べて計算量が大きい。ここで、一つの検査行列のシンボルパケット回復のための計算量Nrecoverを評価するために、1ビット当たりのXOR計算回数をNxor、M×Nの検査行列Hの第i行内の列重みDi、パケット長をPビットとする。さらに列重みDiは、一般に検査行列Hの列数に単調増加的に依存するので、Di=DiNとする。このときのNrecoverは、以下の式で与えられる。NrecoverNxor×P×DiNxor×P×DiN7このため、検査行列のシンボル回復の計算回数Nrecoverは、パケット長及びブロック長に依存して大きくなる。一方で、回復処理可能な検査方程式の行走査の単位行あたりの計算回数Nscanについては、その行内に含まれるシンボルの列の受信状態のみを見ればよい。この単位シンボルあたりの受信状態検査の計算量をNflagとすれば、Nscanは以下で与えられる。NscanNflag×DiN8また、実際にNflag≪Nxorより、Nscan≪Nrecoverとなり、これは誤り訂正可能な検査方程式の行の走査時間よりも、誤り可能な検査方程式の回復処理の方が圧倒的に計算量が多いことを意味している。さらに、ブロック長が固定されている場合には、パケット長に関係なく、誤り訂正可能な検査方程式の行の走査処理は一定になる。以上の理由により、この2つの処理を分割することで、計算量の大きい誤り訂正処理を行う以前に、伝送路でロスしたシンボル数とその位置、及び、復号処理によって回復可能なシンボル数とその位置を知ることができる。これらの伝送路でロスしたシンボルの総数とその位置及び、復号処理並列復号演算部130の処理によって回復可能なシンボルの総数とその位置を誤り訂正の統計的結果として出力することが可能である。よって回復できないシンボル数が多い場合などには、FECではなく送信ホストに向けての再送信要求など、他のシンボル回復方法などと組み合わせることが極めて容易になる。また、キューと回復処理演算実行を分別することによって、検査方程式の解決可能順序が分かるため、後に述べる並列化処理が可能なる。<検査方程式解決依存グループラベリング部123>既存のLDGM復号では、一つの検査方程式の結果が他の方程式に影響を及ぼすため、逐次的に検査方程式を解く方法が用いられる。一方、本発明の一巡回LDGM復号順序決定走査では、解決可能検査方程式を見つけ、これを根にして逐次的に別の解決可能検査方程式を走査する。このため、ひとつの検査方程式がどの他の検査方程式に依存しているかが容易にわかる。依存する方程式同士を一つのグループと識別できれば、依存関係で独立したグループ分けが可能になる。これは、LDGM復号において、並列処理が可能であることを意味する。図4は、本発明の一実施の形態における検査方程式解決依存グループラベリングを示す図である。構成要素は以下の通りである。1.シンボルの受信状態の属性;2.シンボル回復時の上位依存の検査方程式の識別;3.検査方程式の依存木の作成;以下に、上記の各内容について説明する。1.シンボルの受信状態の属性;シンボルの受信状態を次の3つに分類する。完全受信:誤りなく受信した。回復受信:誤って受信したが、他の検査方程式により回復された。回復方程式番号を記録。消失受信:誤って受信した。また、回復受信の場合には、どの検査方程式によって回復されたのかを記録しておく。この方程式を回復方程式と呼ぶことにする。この3状態をシンボルの属性として持たせる。2.シンボル回復時の依存検査方程式の記録;一つの検査方程式がシンボルを回復するのは、その検査方程式内のシンボル状態が唯一の消失受信、それ以外は完全受信または回復受信の場合がある。この、今注目する検査方程式を解決方程式と呼ぶことにする。このとき、解決方程式内のシンボル状態を調べ、回復受信シンボルの回復方程式を記録する。さらに、回復方程式へ解決方程式を記録させる。これにより、検査方程式の一上位、一下位の依存関係が確定する。以上の過程をまとめると次のようになる。1検査方程式内の全てのシンボルの受信状態を調べる。2もしシンボル状態が回復受信であれば以下の操作を実行する。a注目しているシンボルの回復方程式を解決方程式に記録する。b注目しているシンボルの回復方程式に解決方程式を記録する。3.検査方程式の依存木の作成;上記の2.で行った一上位、一下位の依存方程式の記録を基に検査方程式全体の依存関係の木をつくる。まずは、根となる検査方程式から走査を行い、順次に一下位の検査方程式を辿りつつ、根となる検査方程式ラベルを付加していく。但し、一上位の依存方程式は一つではない。これにより、一上位の依存方程式が複数の場合には、マージして根の検査方程式リストとして記録していく。以下にそのアルゴリズムを示す。1全ての根検査方程式に一意名ラベルを付加する。2全ての根検査方程式からはじめ、一下位方程式がなくなるまで以下の操作を実行する。a根検査方程式からはじめ、一下位方程式がなくなるまで以下の操作を実行する。-一上位の依存方程式の根検査方程式ラベルをリストにマージして追加する。以上の過程により、全ての解決方程式には一つ以上の根検査方程式ラベルが割り当てられる。●並列復号演算部130<依存グループ計算並列分割部131>上記の検査方程式解決依存グループラベリング部123により、全ての解決方程式にグループラベルが付加される。この情報を基に並列計算可能なタスクに振り分ける。この振り分けは、2段階に分けられる。まず、検査方程式をみて、所属する根方程式のグループが単一の場合、それらは完全並列化可能である。これらを並列処理並列計算キュー132に割り当て、並列計算ができないものは直列計算キュー134に割り当てる。次に、残りの検査方程式検査方程式計算133を逐次的に解決する。検査方程式計算部135では、検査方程式計算部133と直列計算キュー134の演算結果が入力されると最終となる検査方程式の計算を行う。以上で、全ての解決可能な検査方程式の処理が終了し、復号されたパケットが出力される。[1]最初に、2元祖行列リンク型表現生成部110における2元疎行列の双方向リンク方表現の例を説明する。図5は、本発明の一実施例の検査行列を2元疎行列の双方向リンク方表現で表す例を示す。同図は、図11の検査行列Hを2元疎行列の双方向リンク表現で表す例を示す。検査行列Hは6×14行列であるため、行を示す構造体変数ROWの数は6、列を示す構造体変数COLUMNの数は14である。それぞれを、ROWii0,1,2,...,5,COLUMNjj0,1,2,...,13と表すことにする。また、各構造体変数の持つ要素には、演算子.で参照するとする。例えば、ROWiの要素である行番号iはROWiiで表す。このとき、Hの第0行,第5行を表すROW0,ROW5及び、第0列,第2列,第13列を表すCOLUMN0,COLUMN2,COLUMN13は図5の通りである。ここで実際に、2元疎行列の双方向リンク型表現を用いて、図11のシンボル受信側の場合に、一巡回LDGM復号行順決定走査を行うことを説明する。はじめに文章による処理過程の説明は以下の通りである。1第0行に注目する。この行が示す検査方程式は、第0列が示すシンボルのみを消失シンボルとして含むので回復可能である。このとき、第0行の検査方程式が第0列のシンボルを回復したことを記録する。2続いて、この回復シンボルを含む別の行を走査すると第2行、第5行が該当する。3第2行が回復可能であるかを調べると第10列のシンボルのみ消失受信であるため、回復可能である。続いて、上記の過程を2元疎行列の双方向リンク型表現を用いて表すと以下のようになる。1ROW0.Lcolの全てを順次変数jに代入しつまり、j=0,5,7,8である、COLUMN0.Fが消失受信である列を調べる。COLUMN0.Fのみ消失受信であるため、ROW0は回復可能である。さらに、ROW0.Rcol=0とする。2続いて、COLUMN0.Lrowの全てをiに代入する。つまりi=2,5である。3COLUMN2に注目し、ROW2.Lcolの全てをjに代入し、COLUMNj.Fが消失受信である列を調べる。COLUMNj0.Fのみ消失受信であるため回復可能である。このように、2元疎行列の双方向リンク型表現を用いると、メモリ効率を非常に高め、巨大な検査行列Hを持つブロック符号であっても実現可能である。さらに、一巡回LDGM復号行順決定走査で頻繁に行われる検査行列Hの行と列の間に交互走査を高速に行える。[2]一巡回解決検査方程式走査部120における、一巡回LDGM復号行順決定走査と依存木について説明する。図11の検査行列Hを用いて復号化したシンボルの復号過程を以下に示す。1第0行より走査して回復可能なシンボルを含む行の有無を調べる。2第0行より第1列のシンボルを回復可能。a第0行のシンボルを回復。b第0行を走査して回復可能な行の有無を調べる。c第2行より第10列のシンボルが回復可能。i.第10列のシンボルを回復。ii.第10列を走査して回復可能な行の有無を調べる。A.該当なしiii.該当なし。d該当なし。3第4行より第4列のシンボルが回復可能。a第4列のシンボルを回復。b第4列を走査して回復可能な行の有無を調べる。c第3行より第6列のシンボルが回復可能とする。i.第6列のシンボルを回復。ii.第6列を走査して回復可能な行の有無を調べる。iii.該当なし。d該当なし。4該当なし5終了。実際に、受信されたシンボルは検査行列Hの各列に対応する。はじめに、検査行列の列方向に走査して、誤りシンボルをただ一つ含む行、すなわち、誤りシンボルを回復可能な検査方程式を示す行を見つける。続いて、その回復可能な誤りシンボルを検査方程式より回復させる。図11の例では、第0行の検査方程式より第0列のシンボルが回復できる。次に、ここで回復できた第0列のシンボルを検査方程式に含む列に注目する。このとき、第2行の検査方程式より第10列のシンボルを回復可能である。これを繰り返すことで、図11の場合にはわずか6回の行走査のみでLDGM復号処理が完了できる。[3]次に、検査方程式解決依存グループラベリング部123におけるLDGM復号の依存グループラベリングと依存グループ計算並列分割部131における並列分割について説明する。図11の例において、LDGM復号の並列化を行う過程を説明する。図6は、本発明の一実施例の検査方程式の依存木とグループラベリングの例を示す。上記の[2]の過程により、以下に示すようにグループラベルが付加されている。第0行:グループ0第1行:グループ1第2行:グループ0第3行:グループ0、グループ1第4行:グループ0第5行:グループ0よって単一のグループラベルが付加されている行の検査方程式、すなわち、第0行、第2行と第1行は並列計算キューに割り当てることが可能であり、複数のグループラベルが付加されている第3行の検査方程式は直列計算キューに割り当てられ並列計算キューが終了した後に実行される。[4]次に、超高精細映像伝送における高速LDGM符号を使用したロバスト伝送について説明する。図7は、本発明の一実施例のLDGM符号を用いたJPEG2000ロバスト伝送の例を示す。ここでは、JPEG2000を用いた映像符号化を行いステップ101、それをパケット分割しステップ102、イーサネットフレーム長に適応するブロック長を決定する。そのブロック長を元に検査行列Hを生成し、LDGM符号化を行うステップ103。図8は、本発明の一実施例のUDPIP通信路におけるLDGM符号のパケット分割を示す。このとき、受信時に消失したパケットを同定するためにLDGMブロック番号、及び、パケット番号をヘッダとして送信シンボルに付加するステップ104。その後、UDPIPを用いて受信側に渡るステップ105。伝送路中の送信データの誤りに関しては、イーサネット以下で誤り検出が保証されており、この段階で誤りを含むパケットは排除される。つまり、UDPIPで受信処理されるパケットは誤りを含まない。このため、送信時に付加したヘッダから消失したパケット位置が同定できるステップ108。この同定された消失位置を基にLDGM復号を行うステップ109。その後、JPEG2000符号単位でパケットを合成しステップ110、JPEG2000復号を行うステップ111。上記のように、本発明によれば、ブロック長NシンボルのLDGM符号の復号処理を考えた場合、本発明で2種類の高速が実現された。行列表現による行及び列の走査の高速化、及び、誤り訂正可能判別の行操作の高速化である。行列表現による高速化について、従来手法では、列重みd≪Mの列内を走査する場合にM時間が必要であったが、本発明の2元疎行列リンク型表現を用いた場合では、d時間で操作可能になった。行内の走査も同様である。また、実装段階で管理すべきメモリ使用量変数オブジェクトの数についても、従来手法では要素数がM×Nの配列を用意する必要があったが、本発明では、要素数MNの配列のみで可能になった。また、一つの誤りシンボルが訂正できた後の、誤り訂正可能な行を走査する場合の高速化について、従来の手法はONの計算時間を要した。それに対して、本発明ではONの線形計算時間でこれが可能になった。したがって、大きいブロック長を持つLDGM符号が実現可能になった。なお、上記の図3に示すLDGM復号装置の構成要素の動作をプログラムとして構築し、LDGM復号装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。また、構築されたプログラムをハードディスクや、フレキシブルディスクCD-ROM等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"