(57)【要約】【課題】  誤り訂正符号成功確率を向上させ、暗号化などの機能を追加し、演算負荷の増加無しに高効率な誤り訂正を実現するパケット伝送における低負荷通信路符号化を実現する。【解決手段】  本発明は、パケットロスが発生し得る消失通信路における情報パケットの符号化において、入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割し、該誤り訂正シンボルを復号で用いられる疎行列に対応する行列に基づいて符号化し、符号化されたデータをパケット化し、誤り訂正シンボルのブロックパケット全て、または、該誤り訂正シンボル中の誤り訂正情報のパケットの並び順を組み替えるインターリーブを行い、送信する。【選択図】  図１
2011259506.tif 000002
【特許請求の範囲】
【請求項１】
入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割するサブブロック化手段と、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化する符号化手段と、
符号化されたデータをパケット化するパケット化手段と、
前記誤り訂正シンボルのブロックパケット全て、または、該誤り訂正シンボル中の誤り訂正情報の並び順を組み替えるインターリーブを行い、送信するインターリーブ手段と、
を有することを特徴とする符号化装置。
【請求項２】
入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割するサブブロック化手段と、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行うインターリーブ手段と、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化する符号化手段と、
符号化されたデータをパケット化して送信するパケット化手段と、
を有することを特徴とする符号化装置。
【請求項３】
入力された符号長の入力データを誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割するサブパケット化手段と、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行うインターリーブ手段と、
前記誤り訂正シンボル中の送信情報を逆インターリーブし、該誤り訂正シンボル中の誤り訂正情報をインターリーブするインターリーブ・逆インターリーブ手段と、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化する符号化手段と、
符号化されたデータをパケット化して送信するパケット化手段と、
を有することを特徴とする符号化装置。
【請求項４】
請求項１乃至３のいずれかに記載の符号化装置と、
前記符号化装置から受信した誤りを含むデータに対して、前記符号化装置で用いられた前記行列に対応する疎行列を用いて前記誤り訂正シンボルのサイズ単位に復号する復号化装置と、
を有することを特徴とする符号・復号化システム。
【請求項５】
入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割し、
該誤り訂正シンボルを復号で用いられる疎行列に対応する行列に基づいて符号化し、
符号化されたデータをパケット化し、
前記誤り訂正シンボルのブロックパケット全て、または、該誤り訂正シンボル中の誤り訂正情報のパケットの並び順を組み替えるインターリーブを行い、送信する
ことを特徴とする符号化方法。
【請求項６】
入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割し、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行い、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化し、
符号化されたデータをパケット化して送信する
ことを特徴とする符号化方法。
【請求項７】
入力された符号長の入力データを誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正
シンボルに分割し、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行い、
前記誤り訂正シンボル中の送信情報を逆インターリーブし、該誤り訂正シンボル中の誤り訂正情報をインターリーブし、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化し、
符号化されたデータをパケット化して送信する
ことを特徴とする符号化方法。
【請求項８】
請求項５乃至７のいずれかに記載の符号化方法により符号化したデータに対して、前記符号化装置で用いられた前記行列に対応する疎行列を用いて前記誤り訂正シンボルのサイズ単位に復号する
ことを特徴とする復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置及び方法及び符号化・復号化システム及び復号化方法に係り、特に、パケット伝送において、ブロック長の短い疎グラフ符号を対象とする誤り訂正技術における符号化装置及び方法及び符号化・復号化システム及び復号化方法に関する。
【背景技術】
【０００２】
現在、誤り訂正技術は衛星ディジタル放送やインターネットでの通信、モバイル端末での通信など、各種通信システムで広く用いられている。とりわけ、近年のブロードバンド環境の発展に伴い、インターネットを用いた動画配信サービスなどが期待されており、インターネット網に対する誤り訂正技術は重要なものになっている。以下、インターネット網を例に説明する。
【０００３】
インターネットを用いてサービスを行う側から通信路を見ると、インターネット網はパケット消失通信路（PEC: Packet Erasure Channel）と捉えることができる。これは、図１２に示すような２元消失通信路(BEC：Binary Erasure Channel)がパケットの単位としてグループ化されたものであり、通信路出力は正しい情報で出力されるか、回線中の何らかの障害によって不明として出力されるかのどちらかの場合となる通信路である。この通信系においては、FEC(Forward Error Correction)やARQ（Automatic Repeat reQuest）と呼ばれる誤り訂正符号が用いられるか、再送制御にてエラーから保護される。一般的なIPベースのサービスでは、TCP/IP(Transmission Control Protocol/Internet Protocol)プロトコルが用いられ、デコーダ側では誤り検出のみに留め、誤りが発生した場合は再送制御などで誤りを訂正する方法が用いられている（ARQ方式）。しかし、マルチキャスト配信のような大規模なサービスを想定した場合、受信側が受け取ったデータを元に誤り訂正をすることが求められ、帰還通信路を必要とせず受信側のみで誤りを訂正できる方法が用いられる（FEC方式）。このFEC方式は再送制御等を行わないことから遅延が少なく、リアルタイム性が重要となるテレビ会議システム等でもFEC方式が用いられる。以下、FEC方式について説明する。
【０００４】
FEC方式として、ディジタル放送などではリードソロモン符号（RS符号）が広く用いられている。日本のディジタル放送では符号長２０４バイトと定義されており、元データ１８８バイトに対しておよそ１０％のパリティバイトを付加することで誤りに対して耐性を持たせている。しかし、一般に誤り訂正符号として符号長の長い符号を利用すれば性能がよくなることが知られているが、符号長が長くなると復号が複雑になり計算量が膨大になってしまうという弊害も知られている。そのため、RS符号では、符号長を２５６バイト以下として扱うことが一般的とされている。また、RS符号をIPベースのパケットレベルFECと呼ばれるパケットに適合する場合、上記の理由から２５６パケットを１ブロックとして扱う必要が生じる。
【０００５】
これに対して、疎グラフと確率伝搬アルゴリズム(Belief propagation algorithm)に基づいた復号法を組み合わせた符号は符号長が長い場合に実用的な演算量で優れた復号特性を持つことが知られており、疎グラフにより定義される線形符号である低密度パリティ検査符号（Low density parity check code: LDPC符号）は、Shannonにより定義された通信路容量に迫る現実的な誤り訂正方法として注目されている（例えば、非特許文献１参照）。また、疎グラフに基づく消失訂正符号としては、Digital Fountain社のLT code（例えば、非特許文献２参照）や、Raptor code（例えば、非特許文献３参照）が知られており、符号化効率を大きく劣化させずに任意の符号データを受信しただけで復号できる符号特性を現実的な演算量で達成することが知られている。この性質はインターネットマルチキャストプロトコルであるALC(Asynchronous Layered Coding)（例えば、非特許文献４参照）と適合するためにレイヤード構成されたマルチキャスト通信などで広く用いられている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】R. C. Gallager, "Low density parity check codes", in Research Monograph series.  Cambridge, MIT Press, 1963.
【非特許文献２】M. Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.
【非特許文献３】Shokrollahi, A, "Raptor code", Information Theory , IEEE Transactions on Volume 52, Issue 6, 2006.
【非特許文献４】"Asynchronous Layered coding protocol instantiation", IETF RFC 3450, Dec. 2002.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記で述べたように、疎グラフと確率伝搬アルゴリズムに基づく誤り訂正符号は従来達成できなかった符号化特性を達成する。しかし、従来の技術では符号長の長い場合は優れた特性を発揮するものの、短い符号長の場合は高い誤り訂正能力を発揮することができないという問題がある。
【０００８】
特に、一般的な映像配信サービス等の帯域（1.5Mbps等）に用いる場合、IPパケット（１シンボル）当たりのバイト数が1500byte程度と見積もると、１秒のデータにてブロックに分割して誤り訂正を実施した場合も、符号長は８０程度にしかならない。これは、伝送レート1Mbpsの場合、１秒間に1Mbitの情報量を伝送する。これを１シンボル当たりのバイト数1500byteで割ると８３となる。つまり、シンボル数（＝IPパケット数）が８３パケット程度になることを意味する。
【０００９】
このような状況では疎グラフと確率伝搬アルゴリズムに基づく誤り訂正符号を適用して効率的な誤り訂正が実施できない問題があった。
【００１０】
本発明は上記の点に鑑みなされたもので、誤り訂正シンボルのサイズを変更することにより誤り訂正ブロック長を長くし、線形符号に適した生成行列及び検査行列に変更することにより、誤り訂正符号成功確率を向上させ、演算負荷の増加無しに高効率な誤り訂正を実現するパケット伝送における符号化装置及び方法及び符号化・復号化システム及び復号化方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明（請求項１）は、入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割するサブブロック化手段と、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化する符号化手段と、
符号化されたデータをパケット化するパケット化手段と、
前記誤り訂正シンボルのブロックパケット全て、または、該誤り訂正シンボル中の誤り訂正情報の並び順を組み替えるインターリーブを行い、送信するインターリーブ手段と、
を有することを特徴とする符号化装置である。
【００１２】
本発明（請求項２）は、入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割するサブブロック化手段と、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行うインターリーブ手段と、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化する符号化手段と、
符号化されたデータをパケット化して送信するパケット化手段と、
を有することを特徴とする符号化装置である。
【００１３】
本発明（請求項３）は、入力された符号長の入力データを誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割するサブパケット化手段と、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行うインターリーブ手段と、
前記誤り訂正シンボル中の送信情報を逆インターリーブし、該誤り訂正シンボル中の誤り訂正情報をインターリーブするインターリーブ・逆インターリーブ手段と、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化する符号化手段と、
符号化されたデータをパケット化して送信するパケット化手段と、
を有することを特徴とする符号化装置である。
【００１４】
本発明（請求項４）は、請求項１乃至３のいずれかに記載の符号化装置と、
前記符号化装置から受信した誤りを含むデータに対して、前記符号化装置で用いられた前記行列に対応する疎行列を用いて前記誤り訂正シンボルのサイズ単位に復号する復号化装置と、
を有することを特徴とする符号・復号化システムである。
【００１５】
本発明（請求項５）は、入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割し、
該誤り訂正シンボルを復号で用いられる疎行列に対応する行列に基づいて符号化し、
符号化されたデータをパケット化し、
前記誤り訂正シンボルのブロックパケット全て、または、該誤り訂正シンボル中の誤り訂正情報のパケットの並び順を組み替えるインターリーブを行い、送信する
ことを特徴とする符号化方法である。
【００１６】
本発明（請求項６）は、入力された符号長の入力データを、誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割し、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行い、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化し、
符号化されたデータをパケット化して送信する
ことを特徴とする符号化方法である。
【００１７】
本発明（請求項７）は、入力された符号長の入力データを誤り訂正符号が取り扱う最小のサイズ単位の誤り訂正シンボルに分割し、
前記誤り訂正シンボルの並び順を組み替えるインターリーブを行い、
前記誤り訂正シンボル中の送信情報を逆インターリーブし、該誤り訂正シンボル中の誤り訂正情報をインターリーブし、
前記誤り訂正シンボルの数に対応する、復号で用いられる疎行列に対応する行列に基づいて前記誤り訂正シンボルを符号化し、
符号化されたデータをパケット化して送信する
ことを特徴とする符号化方法である。
【００１８】
本発明（請求項８）は、請求項５乃至７のいずれかに記載の符号化方法により符号化したデータに対して、前記符号化装置で用いられた前記行列に対応する疎行列を用いて前記誤り訂正シンボルのサイズ単位に復号する
ことを特徴とする復号化方法である。
【発明の効果】
【００１９】
上記のように本発明によれば、ＩＰパケット数が少ない場合もメッセージパッシングアルゴリズムを用いた効率的な誤り訂正符号を実施することが可能であり、かつ、誤り訂正器を持たない映像受信機と互換性を保つことができる特徴を持つ。
【００２０】
詳しくは、図１に示す本発明と従来の技術の実験結果による符号化特性を用いて説明する。同図の縦軸は復号成功確率で、復号が成功すればするほどよいことを表している。横軸はPacket Error Rateで、右に行くほど通信路の状態が悪い（パケットロス率が大きい）状態になる。実験条件として、パケット数２００個、FECパケット数５０個のＲＳ符号及びLDGM(Low-Density Generator Matrix)符号と、サブパケット数２０００個、FECサブパケット５００個にサブパケット化した場合を比較した。本発明の方法はサブパケット化を行わない従来のLDGM符号よりも符号化率に換算して１０％改善し、互換性の保てないインターリーブを施した場合と同等の性能を有することがわかる。
【００２１】
RS符号はパケットロス率が大きい場合でも復号成功確率が一番高いので最も強い符号といえる。RS符号は符号化効率が最大なので、これが理論限界ということができる。本発明では、符号長が長くなった場合にRS符号の性能を凌ぎ、符号長が短い場合でもRS符号に迫る性能を有する。
【図面の簡単な説明】
【００２２】
【図１】符号化特性の比較である。
【図２】本発明のシステム構成図である。
【図３】本発明の全体工程を示す図である。
【図４】本発明の一実施の形態における符号化／復号プロセスの概要を示す図である。
【図５】本発明の第１の実施例における通信路符号化システムの構成図である。
【図６】本発明の第２の実施例における通信路符号化システムの構成図である。
【図７】本発明の第２の実施例におけるインターリーブ方法を説明するための図である。
【図８】本発明の第３の実施例における通信路符号化システムの構成図である。
【図９】本発明の第３の実施例におけるインターリーブ方法を説明するための図である。
【図１０】本発明の第４の実施例における通信路符号化システムの構成図である。
【図１１】本発明の第４の実施例におけるインターリーブ方法を説明するための図である。
【図１２】２元消失通信路である。
【発明を実施するための形態】
【００２３】
以下、図面と共に本発明の実施の形態を説明する。
【００２４】
まず、以下で用いられる「インターリーブ」とは、パケットかサブパケット単位でこれらを並び替えることを指す。
【００２５】
図２は、本発明のシステム構成図であり、本発明により実現可能なパケットレベルFECに対する誤り訂正機能を示す。同図に示すシステムは、通信路復号手段を有する通信路符号化装置１００と、パケット伝送手段を有するパケットベース伝送装置１５０と、受信データ解析手段を有するパケットベース受信装置１７０と、通信路復号手段を有する通信路復号装置２００から構成される。
【００２６】
本発明はパケットの種類に依存せずに実施できるが、一例としてマルチキャスト配信で用いられるUDPプロトコルを用いた配信を例として説明する。
【００２７】
UDPプロトコルを用いるとUDPパケットがロスした場合、TCPプロトコルとは異なり再送処理は行われないが、図１２に示すように受信パケットは正しいか、ロスしたパケットの位置が正確にわかる消失通信路として見える特徴がある。これは、受信語が"０"であった場合は、絶対に"０"で正しい（つまり"１"が間違って"０"として届くことはない）という意味を表す。また、受信語が"１"であった場合も同様である。但し、これはBEC（Bit Erasure Channel）の場合である。上記記載においては、ビットではなく、パケット単位になるとPEC(Packet Erasure Channel)となり、例えば、"０００１００１０"というパケットが届いたら、それが正しいという意味を表す。
【００２８】
本発明は、このUDPパケット等として伝送されるデータに対して、誤り訂正シンボルを小さくすることにより誤り訂正ブロック長を長くし、ブロック復号成功確率を向上させることにより符号化効率の改善を行う。
【００２９】
さらに、インターリーブを組み合わせることにより、誤り訂正シンボルがバースト的にロスすることを防ぎブロック復号率を向上させる機能や、軽度の暗号化の機能、誤り訂正符号を持たない受信器でも再生が可能な互換性を持つ機能を持つよう符号化を実施することができる。つまり、１ブロックに含まれるパケットの個数が少ない場合にも、効率的な誤り訂正を実施することができ、かつ、軽度の暗号化の機能や、誤り訂正符号を持たない受信器でも再生が可能な互換性を持つ機能を持つ符号化が実現される。なお、上記の「インターリーブを組み合わせることにより誤り訂正シンボルがバースト的にロスを防ぐ」とは、図３において、例えば、インターリーブ処理を行った[ｐ１,ｐ４,ｐ６,ｐ８]パケットをロスしたとすると、インターリーブが解かれると、飛び飛びの値になっており、受信後、復元されたソースシンボル列のｓ５,ｓ６,ｓ７,ｓ８はバースト的に連続し（図３（８））、パリティシンボル列ｐ１,ｐ４,ｐ６,ｐ８は連続していない（非連続になる）ことを意味する。
【００３０】
図４は、本発明の一実施の形態における符号化及び復号プロセスの概要を示す。
【００３１】
符号化側では、まず、パケットにサブパケットへと分割する（図４（１））。次に、サブパケットに対してインターリーブを行った後に、次式に従いｍ個のＦＥＣサブパケットＣｍを作成する（図４（２））。
【００３２】
【数１】
2011259506.tif 000003
但し、Ｓｋはｋ個のインターリーブされたサブパケットであり、Pｍ,ｋはｍ行ｋ列の文献１「Xiao-Yu Hu, et al. "Regular and irregular Progressive Edge-Growth Tanner Graphs", IEEE Trans. Inform. Theory, vol.51, no.1, January, 2005」の方法に基づいて作成される疎行列、Ｔｍはｍ行ｍ列の階段行列である。
【００３３】
最後に、インターリーブされたサブパケットＳｋはインターリーブを解いてパケット化され、ＦＥＣサブパケットＣｍはインターリーブをかけてパケット化された後に、それぞれネットワークへと送信される（図４（３））。
【００３４】
復号側では、消失したパケットがある場合、サブパケット化を行った後にバースト的に発生しているロスをインターリーブによりランダムエラーへと変換する（図４（４））。次に、上記の式から導出される次式を満たすように、メッセージパッシングアルゴリズムにより一次方程式を解くことで消失サブパケットを復号する（図４（５））。
【００３５】
【数２】
2011259506.tif 000004
最後に復号されたサブパケットのインターリーブを解いて復号側の処理を終了する。
【実施例】
【００３６】
以下、図面と共に本発明の実施例を説明する。
【００３７】
［第１の実施例］
図５は、本発明の第１の実施例における通信路符号化システムの構成図であり、誤り訂正シンボルのサイズを変更することにより符号長の短い（パケット数の少ない）データに対して効率的な誤り訂正を実施することが可能なシステムを示している。
【００３８】
同図に示すシステムは、通信路符号化装置１００、パケット化部１０４で作成されたパケットデータを通信する通信モジュール１５０、インターネット等の回線である消失通信路であるチャンネル１６０、通信モジュール１５０により送信されるデータを受け取る受信モジュール１７０、通信路復号装置２００から構成される。
【００３９】
通信路符号化装置１００は、サブパケット化部１０１、符号化部１０２、行列読み出し部１０３、パケット化部１０４から構成される。
【００４０】
サブパケット化部１０１は、送信データを誤り訂正シンボル毎に分割する。行列読み出し部１０３は、通信路復号装置２００の疎行列読み出し部２０２で読み出される疎行列に対する行列を読み出す。符号化部１０２は、行列読み出し部１０３で読み出された行列に基づいてパリティ情報を生成する。パケット化部１０４は、パケットベースの通信を行うためのパケットを生成する。
【００４１】
通信路復号装置２００は、サブパケット化部２０１、疎行列読み出し部２０２、復号部２０３から構成される。
【００４２】
通信路復号装置２００のサブパケット化部２０１は、パケット化されたデータを訂正シンボルに戻す。疎行列読み出し部２０２は、疎行列を読み出す。復号部２０３は、疎行列に基づいて誤りを訂正する。
【００４３】
以下、それぞれの構成要素について説明する。
【００４４】
本システムは、パケット伝送システムの符号長が短い場合にも効率的な誤り訂正を実施することが可能な通信路符号化システムであるが、簡単化のために、以下では、インターネットのようなIPパケット伝送を想定して通信路符号化方法を述べる。しかし、通信路は消失パケット通信路のみならず、パケットベースの通信路を対象とすることが可能である。
【００４５】
入力データが通信路符号化装置１００に入力されると、サブパケット化部１０１に送られ、誤り訂正符号が取り扱う最小単位（以下、誤り訂正シンボル）に分割される。RS符号等の代数的構造（例えば、Vandermonde行列）を有する誤り訂正符号を用いる場合、消失パケット通信路では通信モジュール１５０が取り扱うパケットサイズを誤り訂正シンボルとして取り扱うことが最大の効率をもたらす。なお、RS符号はVandermonde行列などを用いて構成されているために、符号化効率がいつも最大になるが、復号にかかる演算量が大きくなってしまうため、符号長を伸ばすことができない。
【００４６】
しかし、本発明のサブパケット化部１０１では、通信モジュール１５０が取り扱うパケットサイズ以下の誤り訂正シンボルへと分割する。サブパケット化する場合に、実験的に２０００程度のシンボル数（サブパケット数）になるように分割することで良好な結果を得た。なお、この例に限定されることなく、ソフトウェアが扱い易い単位（バイト単位）で分割すればよい。
【００４７】
分割された誤り訂正シンボルは、符号化部１０２に送られ、そのシンボル数に対応した行列Gが行列読み出し部１０３から読み出される。読み出された行列との積（但し、この場合はXOR演算）により符号語が作成される。読み出される行列Gは復号で用いられる疎行列読み出し部２０２の疎行列Hとの積がゼロ行列のものを満たすもの、すなわち、
ＧＨT＝０
の形に変形可能であれば適用される。これは、線形符号の定義を満たす符号という意味であり、本方式は線形符号の一形態である。
【００４８】
以下に線形符号の一形態であるLDPC符号に適用した場合の例を示す。本発明は、LDPC符号に限定されず、様々なクラスの確率伝搬アルゴリズムを伴った符号に適用されるが、データをある単位毎に誤り訂正シンボルとして扱う場合に有効な方法である。すなわち、インターネット等のパケット単位でデータを扱う際に特に有意性が生じる本実施例の最善の一形態であるLDPC符号を例に説明する。なお、その他の場合も容易に拡張可能であるのでその他の例については説明を省略する。LDPC符号に適用した場合のパリティ誤り訂正シンボルＣｍは次式により生成される。
【００４９】
【数３】
2011259506.tif 000005
但し、Sｋはｋ個の誤り訂正シンボルであり、Gｍ,ｋはｍ行ｋ列の行列であり、ＧＨT=０を満たすものであり、パリティ検査行列Ｈにできるだけループが含まれないように構成される。具体的には、文献１「Xiao-Yu Hu, et al. "Regular and irregular Progressive Edge-Growth Tanner Graphs", IEEE Trans. Inform. Theory, vol.51, no.1, January, 2005」に記載の方法を用いるものとする。
【００５０】
符号化部１０２にて符号化されたデータ（上記の例では、誤り訂正シンボルＳｋとパリティ誤り訂正シンボルＣｍ）は、パケット化部１０４に送られる。なお、非組織符号のLDPC符号で構成する場合も上記の式にて符号化が行われる。
【００５１】
次に、送信ソース情報と生成された誤り訂正情報を含む誤り訂正シンボルｎ個はパケット化部１０４にて通信モジュール１５０に適したパケットのパケット化が行われる。パケット化されたそれぞれのパケットは通信モジュール１５０に送られ、ネットワークチャンネル１６０を通じて伝送される。
【００５２】
受信モジュール１７０では、ネットワークチャンネル１６０を通じてパケットを受け取る。受信パケットはサブパケット化部２０１に送られ、パケットをサブパケット単位に分割することで誤り訂正シンボルが生成される。生成された誤り訂正シンボルは復号部２０３に送られ、疎行列読み出し部２０２から読み出されるパリティ検査行列Ｈにより次式を満たすように送信ソース情報を復号する。この際、メッセージパッシングアルゴリズムにより一次方程式を解くことで消失サブパケットを復号する。
【００５３】
【数４】
2011259506.tif 000006
復号された送信ソース情報は出力データとして映像受信機などに送られる。
【００５４】
［第２の実施例］
図６は、本発明の第２の実施例における通信路符号化システムの構成図であり、誤り訂正シンボルのサイズを変更することにより符号長の短い（パケット数の少ない）データに対して効率的な誤り訂正を実施することが可能な通信路符号化システムを示す。
【００５５】
同図に示すシステムは、第１の実施例と同様に、通信路符号化装置１００、通信路符号化装置１００のパケット化部１０４で作成されたパケットデータを通信する通信モジュール１５０、インターネット等の回線である消失通信路であるチャンネル１６０、通信モジュール１５０から送信されるデータを受け取る受信モジュール１７０、通信路復号装置２００から構成されるが、通信路符号化装置１００と通信路復号装置２００の構成が異なる。
【００５６】
本実施例の通信路符号化装置１００は、サブパケット化部１０１、符号化部１０２、パケット化部１０４、疎行列読み出し部１１１、インターリーブ部１１２を有する。
【００５７】
サブパケット化部１０１は、送信データを誤り訂正シンボル毎に分割する。疎行列読み出し部１１１は、ランダムな信号に基づいて生成された疎行列を読み出す。符号化部１０２は、疎行列読み出し部１１１で読み出された疎行列に基づいてパリティ情報を生成する。インターリーブ部１１２は、誤り訂正シンボルをインターリーブする。パケット化部１０４は、パケットベースの通信を行うためのパケットを生成する。
【００５８】
また、通信路復号装置２００は、サブパケット化部２０１、逆インターリーブ部２１１、疎行列読み出し部２０２、復号部２０３を有する。
【００５９】
以下、それぞれの構成要素について説明する。
【００６０】
下記に線形符号の一形態であるLDGM符号に適用した場合の構成要素を説明する。本発明は、第１の実施例におけるLDPC符号、または、本実施例のLDGM符号に限定されず、様々なクラスの確率伝搬アルゴリズムを伴った符号に適用される。また、データをある単位毎に誤り訂正シンボルとして扱う場合に有効な方法であることも同じである。但し、本実施例はインターネット等のパケット単位でデータを扱う際に特に優位性が生じる本発明の最善の一形態であるLDGM符号を例に説明する。これは、LDGM符号の場合にインターリーブを導入する効果が大きいからである。なお、その他の場合も容易に拡張可能であるのでその他の例については説明を省略する。
【００６１】
入力データが通信路符号化装置１００に入力されると、サブパケット化部１０１に送られ、誤り訂正符号が取り扱う最小単位（以下、誤り訂正シンボル）に分割される。本サブパケット化部１０１では、通信モジュール１５０が取り扱うパケットサイズ以下の誤り訂正シンボルへと分割する。
【００６２】
分割された誤り訂正シンボルは符号化部１０２に送られ、そのシンボル数に対応した行列Ｇが疎行列読み出し部１１１から読み出される。読み出された行列Ｇとの積（但し、この場合はＸＯＲ演算）により符号語が作成される。すなわち、LDGM符号に適用した場合のパリティ誤り訂正シンボルＣｍは次式により生成される。
【００６３】
【数５】
2011259506.tif 000007
但し、Sｋはｋ個の誤り訂正シンボルであり、Pｍ,ｋはｍ行ｋ列の疎行列、Ｔｍはｍ行ｍ列の階段行列であり、Ｇm,kはｍ行ｋ列のＰ及びＴ-1から構成される行列であり、ＧＴT＝０を満たすものであり、パリティ検査行列Ｈにできるループが含まれないように構成される。
【００６４】
但し、Ｓkはｋ個のインターリーブされたサブパケットであり、Pｍ,ｋはｍ行ｋ列の前述の文献１の方法に基づいて作成される疎行列、Ｔｍはｍ行ｍ列の階段行列である。
【００６５】
このように、LDGM符号に適用すると符号化部１０２にて用いる行列を疎行列にすることができ、低負荷に誤り訂正符号を作成できる。また、同時に組織符号となるため互換性等の観点から優れた符号化が実施できる。さらに、サブパケット化を行っていない場合と演算量は用いる疎行列のdistribution pairが変更されない限り一定である（増加しない）という特徴を持っている。
【００６６】
次に、符号化部１０２は、送信ソース情報と生成された誤り訂正情報を含む誤り訂正シンボルｎ個をインターリーブ部１１２に送る。インターリーブ部１１２では、誤り訂正シンボルのｎ個のサブパケット全てか、誤り訂正シンボル中のパリティ情報ｍ個のサブパケットをインターリーブする。
【００６７】
図７にパリティ情報のみをインターリーブする際のFECインターリーブ法の概要を示す。同図に示すインターリーブ法は、送信データ中のある一部の情報がブロックとして切り出され（同図ａの送信データ）、当該ブロックがｓ１からｓ１２までのサブパケットに分割される。サブパケット化された情報は、疎行列によりｃ１からｃ８の誤り訂正情報が作成される。FECインターリーブ処理（同図ｂ）では、誤り訂正情報のサブパケットのみがインターリーブされ、パケット化されネットワークへと送信される。なお、インターリーブの順番の決定方法は様々なバリエーションが考えられるが、図示したものは、隣り合うサブパケット同士が同一パケットに入らないようにするインターリーブである。また、全体インターリーブは送信情報全てｓ１からｓ１６、ｃ１からｃ８の全てをインターリーブする処理に相当する。この場合、インターリーブに乱数を使うことで、軽度の暗号化機能を持たせることもできる。
【００６８】
インターリーブされたサブパケットはパケット化部１０４にて通信モジュール１５０に適したパケットにパケット化が行われる。パケット化されたそれぞれのパケットは通信モジュール１５０に送られ、ネットワークチャンネル１６０を通じて伝送される。受信モジュール１７０では、ネットワークチャンネル１６０を通じてパケットを受け取る。受信パケットはサブパケット化部２０１に送られ、パケット単位をサブパケット単位に分割することで誤り訂正シンボルが生成される。生成された誤り訂正シンボルは逆インターリーブ部２１１に送られ、インターリーブが解かれる。インターリーブが解かれた誤り訂正シンボルは復号部２０３に送られ、疎行列読み出し部２０２から読み出されるパリティ検査行列Ｈにより次式を満たすように送信ソース情報を復号する。この際、メッセージパッシングアルゴリズムにより一次方程式を解くことで消失サブパケットを復号する。
【００６９】
【数６】
2011259506.tif 000008
復号された送信ソース情報は出力データとして、映像受信機などに送られる。
【００７０】
［第３の実施例］
図８は、本発明の第３の実施例における通信路符号化システムの構成図であり、誤り訂正シンボルのサイズを変更することにより符号長の短い（パケット数の少ない）データに対して効率的な誤り訂正を実施することが可能な通信路符号化システムを示している。
【００７１】
同図に示すシステムは、第１、第２の実施例と同様に、通信路符号化装置１００、通信路符号化装置１００のパケット化部１０４で作成されたパケットデータを送信する通信モジュール１５０、インターネット等の回線である消失通信路であるチャンネル１６０、通信モジュール１５０により送信されるデータを受け取る受信モジュール１７０、通信路復号装置２００から構成されるが、通信路符号化装置１００と通信路復号装置２００の構成が異なる。
【００７２】
本実施例の通信路符号化装置１００は、サブパケット化部１０１、符号化部１０２、パケット化部１０４、疎行列読み出し部１１１、インターリーブ部１１２、インターリーブ／逆インターリーブ部１１３を有する。
【００７３】
サブパケット化部１０１は、送信データを誤り訂正シンボル毎に分割する。疎行列読み出し部１１１は、ランダムな信号に基づいて生成された疎行列を読み出す。インターリーブ部１１２は、誤り訂正シンボルをインターリーブする。符号化部１０２は、疎行列読み出し部１１１で読み出された疎行列に基づいてパリティ情報を生成する。インターリーブ／逆インターリーブ部１１３は、誤り訂正シンボル中の送信情報を逆インターリーブし、誤り訂正シンボル中の誤り訂正情報をインターリーブする。パケット化部１０４は、パケットベースの通信を行うためのパケットを生成する。
【００７４】
また、通信路復号装置２００は、サブパケット化部２０１、逆インターリーブ／インターリーブ部２１２、疎行列読み出し部２０２、復号部２０３を有する。
【００７５】
サブパケット化部２０１は、パケット化されたデータを訂正シンボルに戻す。インターリーブ部１１２では、誤り訂正シンボルのｎ個のサブパケット全てか、誤り訂正シンボル中のパリティ情報ｍ個のサブパケットをインターリーブする。逆インターリーブ／インターリーブ部２１２は、インターリーブ／逆インターリーブ部１１３の逆処理を行う。復号部２０３は、疎行列読み出し部２０２で読み出された疎行列に基づいて誤りを訂正する。
【００７６】
以下に、LDGM符号の一形態であるArray型のLDGM符号に適用した場合の構成要素を説明する。本発明は、第１の実施例のLDPC符号、第２の実施例のLDGM符号、本実施例のArray型LDGM符号に限定されず、様々なクラスの確率伝搬アルゴリズムを伴った符号に適用される。また、データをある単位毎に誤り訂正シンボルとして扱う場合に有効な方法であることも同じである。但し、本実施例はインターネット等のパケット単位でデータを扱う際に特に優位性が生じる本発明の最善の一形態であるArray型のLDGM符号を例に説明する。これは、第２の実施例と同様にLDGM符号の場合にインターリーブを導入する効果が大きく、さらに、行列がある決まりに従うタイプのLDGM符号で効果を有するためである。なお、その他の場合も容易に拡張可能であるので、その他の例については説明を省略する。
【００７７】
入力データが通信路符号化装置１００に入力されると、サブパケット化部１０１に送られ、誤り訂正符号が取り扱う最小単位（以下、誤り訂正シンボル）に分割される。本サブパケット化部１０１では、通信モジュール１５０が取り扱うパケットサイズ以下の誤り訂正シンボルへと分割する。インターリーブ部１１２では、誤り訂正シンボルのｎ個のサブパケット全てか、誤り訂正シンボル中のパリティ情報ｍ個のサブパケットをインターリーブする。なお、本実施例におけるインターリーブの方法は前述の第２の実施例と同様であるので、詳細な説明は省略する。
【００７８】
分割され、インターリーブされた誤り訂正シンボルは符号化部１０２に送られ、そのシンボル数に対応した行列Ｇが疎行列読み出し部１１１から読み出される。読み出された行列Ｇとの積（但し、この場合はＸＯＲ演算）により符号語が作成される。すなわち、LDGM符号に適用した場合のパリティ誤り訂正シンボルＣｍは次式により生成される。
【００７９】
【数７】
2011259506.tif 000009
但し、Gm,kはｍ行ｋ列のＰ及びＴ−１から構成される行列であり、Pｍ,ｋはｍ行ｋ列の次式で与えられるArray型の疎行列、Ｔｍはｍ行ｍ列の階段行列である。
【００８０】
【数８】
2011259506.tif 000010
但し、Ｉはｑ×ｑ（ｑは素数）の行列であり、ｃとｒは２つの独立したｃ，ｒ≦ｑを満たす整数、αは順列行列と呼ばれる次式で定義される。
【００８１】
【数９】
2011259506.tif 000011
このように、Array型のLDGM符号に適用すると符号化部１０２にて用いる行列を疎行列にすることができ、低負荷に誤り訂正符号を作成でき、組織符号となるため互換性等の観点から優れ、サブパケット化を行っていない場合と演算量は用いる疎行列のdistribution pairが変更されない限り一定である（増加しない）という特徴を持っているほか、単純なLDGM符号とは異なり、Array型であるために様々な符号化に柔軟に対応できる、バーストエラーに強い符号となる、ハードウェア実装が容易などの効果が期待できる。
【００８２】
次に、送信ソース情報と生成された誤り訂正情報を含む誤り訂正シンボルｎ個はインターリーブ／逆インターリーブ部１１３では、誤り訂正シンボルのｎ個の誤り訂正シンボル中のパリティ情報ｍ個のサブパケットをインターリーブし、送信情報を逆インターリーブする。図９にパリティ情報のみをインターリーブする際のインターリーブ法の概要を示す。同図に示すFECインターリーブ法は、送信データ中にある一部の情報がブロックとして切り出され（同図中ａの送信データ）、それがｓ１からｓ１６までのサブパケットに分割される。サブパケット化された情報がインターリーブされ、疎行列によりｃ１からｃ８の誤り訂正情報が作成される。インターリーブ／逆インターリーブ処理では、誤り訂正情報のサブパケットのみがインターリーブされ、送信情報は逆インターリーブされ、その後、パケット化されネットワークへと送信される。なお、インターリーブの順番の決定方法は様々なバリエーションが考えられるが、図示したものは、隣り合うサブパケットが同一パケットに入らないようにするインターリーブである。
【００８３】
インターリーブされたサブパケットは、パケット化部１０４にて通信モジュール１５０に適したパケットにパケット化される。パケット化されたそれぞれのパケットは通信モジュール１５０に送られ、ネットワークチャンネル１６０を通じて伝送される。
【００８４】
受信モジュール１７０では、ネットワークチャンネル１６０を通じてパケットを受け取る。受信パケットはサブパケット化部２０１に送られ、パケット単位をサブパケット単位に分割することで誤り訂正シンボルが生成される。生成された誤り訂正シンボルは逆インターリーブ／インターリーブ部２１２に送られ、誤り訂正情報のインターリーブが解かれ、送信情報のインターリーブがかけられる。符号化時と同じ配列になった誤り訂正シンボルは復号部２０３に送られ、疎行列読み出し部２０２から読み出されるパリティ検査行列Ｈにより次式を満たすように送信ソース情報を復号する。この際、メッセージパッシングアルゴリズムにより一次方程式を解くことで消失サブパケットを復号する。
【００８５】
【数１０】
2011259506.tif 000012
復号された送信ソース情報は出力データとして映像受信機などに送られる。
【００８６】
［第４の実施例］
図１０は、本発明の第４の実施例における通信路符号化システムの構成図であり、有色性雑音下においても効率的な誤り訂正を実施することが可能な通信路符号化システムを示している。
【００８７】
同図に示すシステムは、第１〜第３の実施例と同様に、通信路符号化装置１００、通信路符号化装置１００のパケット化部１０４で作成されたパケットデータを通信する通信モジュール１５０、インターネット等の回線である消失通信路であるチャンネル１６０、通信モジュール１５０により送信されるデータを受け取る受信モジュール１７０、通信路復号装置２００から構成されるが、通信路符号化装置１００と通信路復号装置２００の構成が異なる。
【００８８】
本実施例の通信路符号化装置１００は、符号化部１０２、パケット化部１０４、疎行列読み出し部１１１、インターリーブ部１１２を有する。
【００８９】
疎行列読み出し部１１１は、ランダムな信号に基づいて生成された疎行列を読み出す。インターリーブ部１１２は、誤り訂正シンボルをインターリーブする。符号化部１０２は、疎行列読み出し部１１１で読み出された疎行列に基づいてパリティ情報を生成する。パケット化部１０４は、パケットベースの通信を行うためのパケットを生成する。
【００９０】
また、通信路復号装置２００は、疎行列読み出し部２０２、逆インターリーブ部２１１、復号部２０３を有する。
【００９１】
逆インターリーブ部２１１は、通信路符号化装置１００のインターリーブ部１１２の逆処理を行う。疎行列読み出し部２０２は、疎行列を読み出す。復号部２０３は、疎行列読み出し部２０２で読み出された疎行列に基づいて誤りを訂正する。
【００９２】
以下、それぞれの構成要素について説明する。
【００９３】
以下に線形符号の一形態であるLDGM符号に適用した場合の構成要素について説明する。
【００９４】
本発明は、第１の実施例のLDPC符号、または、第２の実施例のLDGM符号に限定されず、様々なクラスの確率伝搬アルゴリズムを伴った符号に適用される。また、データをある単位毎に誤り訂正シンボルとして扱う場合に有効な方法であることも同じである。但し、本実施例はインターネット等のパケット単位でデータを扱う際に特に有意性が生じる最善の一形態であるLDGM符号を例に説明する。これは、LDGM符号の場合にインターリーブを導入する効果が大きいからである。なお、その他の場合も容易に拡張可能であるので、その他の例については省略する。
【００９５】
入力データが通信路符号化装置に入力されると、符号化部１０２に送られ、誤り訂正符号が取り扱う最小単位で符号化される。本実施例では、通信モジュール１５０が取り扱うパケットサイズと同じか、または、若干小さい誤り訂正シンボル単位で符号化を行う。
【００９６】
符号化部１０２では、行列Ｇが疎行列読み出し部１１１から読み出され、読み出された行列Ｇとの積（ただし、この場合はＸＯＲ演算）により符号語が作成される。すなわち、LDGM符号に適用した場合のパリティ誤り訂正シンボルＣｍは次式により生成される。
【００９７】
【数１１】
2011259506.tif 000013
但し、Ｓkはｋ個の誤り訂正シンボルであり、Ｐm,kはｍ行ｋ列の疎行列、Ｔｍはｍ行ｍ列の階段行列であり、Ｇm,kはｍ行ｋ列のＰ及びＴ−１から構成される行列であり、ＧＨＴ＝０を満たすものであり、パリティ検査行列Ｈにできるだけループが含まれないように構成される。
【００９８】
ただし、Pm,kはm行ｋ列の文献１の方法に基づいて作成される疎行列、Ｔｍはm行ｍ列の階段行列である。
【００９９】
このように、LDGM符号に適用すると符号化部１０２にて用いる行列を疎行列にすることができ、低負荷に誤り訂正符号を作成できる。また、同時に組織符号となるとめ互換性等の観点から優れた符号化が実施できる。
【０１００】
次に、送信ソース情報と生成された誤り訂正情報を含む誤り訂正シンボルｎ個はパケット化部１０４に送られる。パケット化部１０４では、通信モジュール１５０に適したパケットにパケット化される。パケットはその後インターリーブ部１１２に送られ、誤り訂正シンボルのｎ個のブロックパケット全てか、パリティ情報ｍ個のパケットをインターリーブする。図１１にパリティ情報のみをインターリーブする際のFECインターリーブ法の概要を示す。同図のFECインターリーブ処理では、誤り訂正情報のパケットのみがインターリーブされ、パケットネットワークへと送信される。なお、インターリーブの順番の決定方法は様々なバリエーションが考えられるが、図示したものは、隣り合うサブパケットが同一パケットに入らないようにするインターリーブであり、インターリーバによりインデクシングされたｉ'は
【０１０１】
【数１２】
2011259506.tif 000014
にてインデックスされる。但し、［・］ｑはｑのモジュール演算であり、
【０１０２】
【数１３】
2011259506.tif 000015
は整数への切捨て演算、ｇはブロック中にあるパリティパケットの数、ｄは隣り合うパケットをいくつにするかユーザが選択する数、をそれぞれ表す。図１１はｇ＝８、ｄ＝４でインデクシングした例である。
【０１０３】
また、全体インターリーブは送信情報全てｓ１からｓ１６、ｃ１からｃ８の全てをインターリーブする処理に相当する。この場合、インターリーブに乱数を使うことで、経度の暗号化機能を持たせることもできる。
【０１０４】
インターリーブされたパケットは通信モジュール１５０に送られ、ネットワークチャンネル１６０を通じて伝送される。
【０１０５】
受信モジュール１７０ではネットワークチャンネル１６０を通じてパケットを受け取る。受信パケットは逆インターリーブ部２１１に送られ、インターリーブが解かれる。インターリーブが解かれた誤り訂正シンボルは復号部２０３に送られ、疎行列読み出し部２０２から読み出されるパリティ検査行列Ｈにより次式を満たすように送信ソース情報を復号する。この際、メッセージパッシングアルゴリズムにより一次方程式を解くことで消失サブパケットを復号する。
【０１０６】
【数１４】
2011259506.tif 000016
復号された送信ソース情報は出力データとして映像受信機などに送られる。
【０１０７】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１０８】
１００  通信路符号化装置
１０１  サブパケット化部
１０２  符号化部
１０３  行列読み出し部
１０４  パケット化部
１１１  疎行列読み出し部
１１２  インターリーブ部
１１３  インターリーブ／逆インターリーブ部
１５０  パケットベース伝送装置、通信モジュール
１６０  ネットワークチャンネル
１７０  パケットベース受信装置、受信モジュール
２００  通信路復号装置
２０１  サブパケット化部
２０２  疎行列読み出し部
２０３  復号部
２１１  逆インターリーブ部
２１２  逆インターリーブ／インターリーブ部
【図１】
2011259506.tif 000017
【図２】
2011259506.tif 000018
【図３】
2011259506.tif 000019
【図４】
2011259506.tif 000020
【図５】
2011259506.tif 000021
【図６】
2011259506.tif 000022
【図７】
2011259506.tif 000023
【図８】
2011259506.tif 000024
【図９】
2011259506.tif 000025
【図１０】
2011259506.tif 000026
【図１１】
2011259506.tif 000027
【図１２】
2011259506.tif 000028