(57)【特許請求の範囲】
【請求項１】
階層的通信路符号化装置と階層的通信路復号装置からなるシステムにおいて、階層符号化されたデータを誤りから保護する通信路符号方法であって、
前記階層的通信路符号化装置において、
対象データをスケーラビリティ機能毎に分割した複数の階層データに対して、それぞれ１つの階層データのデータサイズと該階層データに付加されるパリティデータのサイズとに対応したサイズを有する疎行列を生成し、該生成した複数の疎行列を部分行列とする階層的疎行列を生成する階層的疎行列生成ステップと、
前記複数の階層データを部分行列とする行列に対して、前記階層的疎行列との排他的論理和演算を行うことにより前記階層データのそれぞれに対応するパリティデータを求める階層的符号化ステップと、
前記階層データ、前記パリティデータ及び前記階層的疎行列を前記階層的通信路復号装置に送信する送信ステップと、を行い、
前記階層的通信路復号装置において、
前記階層的通信路符号化装置から送信された前記階層データを、当該階層データに対応する受信した前記パリティデータが受信した前記階層的疎行列の部分行列と受信した当該階層データを含む１以上の前記階層データとの排他的論理和演算を行った結果に等しいとして求めた方程式を解くことによって復号する階層的復号ステップ、
を行うことを特徴とする通信路符号化方法。
【請求項２】
前記階層的疎行列生成ステップにおいて、
１つの階層データに対して、１つのパリティデータが生成されるよう前記階層的疎行列を生成するステップを行い、
前記階層的復号ステップにおいて、
前記階層的疎行列を用いて前記階層データと前記パリティデータを１対１で復号するステップを行う
請求項１記載の通信路符号化方法。
【請求項３】
前記階層的疎行列生成ステップにおいて、
前記階層的疎行列を、該階層的疎行列の１部分または全てを１つのランダムな疎なグラフにより定義される行列を用いて生成し、
前記階層的復号ステップにおいて、
前記パリティデータを、１部分または全てを１つのランダムな疎なグラフにより定義された前記階層的疎行列の行列を用いて復号する
請求項１または２記載の通信路符号化方法。
【請求項４】
前記階層的復号ステップにおいて、
受信した前記データを選択的に復号する
請求項２記載の通信路符号化方法。
【請求項５】
階層符号化されたデータを誤りから保護するための階層的通信路符号化装置と階層的通信路復号装置からなるシステムであって、
前記階層的通信路符号化装置は、
対象データをスケーラビリティ機能毎に分割した複数の階層データに対して、それぞれ１つの階層データのデータサイズと該階層データに付加されるパリティデータのサイズとに対応したサイズを有する疎行列を生成し、該生成した複数の疎行列を部分行列とする階層的疎行列を生成す階層的疎行列生成手段と、
前記複数の階層データを部分行列とする行列に対して、前記階層的疎行列との排他的論理和演算を行うことにより前記階層データのそれぞれに対応するパリティデータを求める階層的符号化手段と、
前記階層データ、前記パリティデータ及び前記階層的疎行列を前記階層的通信路復号装置に送信する送信手段と、を有し、
前記階層的通信路復号装置は、
前記階層的通信路符号化装置から送信された前記階層データを、当該階層データに対応する受信した前記パリティデータが受信した前記階層的疎行列の部分行列と受信した当該階層データを含む１以上の前記階層データとの排他的論理和演算を行った結果に等しいとして求めた方程式を解くことによって復号する階層的復号手段を
有することを特徴とする階層的通信路符号化システム。
【請求項６】
前記階層的通信路符号化装置の前記階層的疎行列生成手段は、
１つの階層データに対して、１つのパリティデータが生成されるよう前記階層的疎行列を生成する手段を含み、
前記階層的通信路復号装置の前記階層的復号手段は、
前記階層的疎行列を用いて前記階層データと前記パリティデータを１対１で復号する手段を含む
請求項５記載の通信路符号化システム。
【請求項７】
前記階層的通信路符号化装置の前記階層的疎行列生成手段は、
前記階層的疎行列を、該階層的疎行列の１部分または全てを１つのランダムな疎なグラフにより定義される行列を用いて生成する手段を含み、
前記階層的通信路復号装置の前記階層的復号手段は、
前記パリティデータを、１部分または全てを１つのランダムな疎なグラフにより定義された前記階層的疎行列の行列を用いて復号する手段を含む
請求項５または６記載の通信路符号化システム。
【請求項８】
前記階層的通信路復号装置の前記階層的復号手段は、
受信した前記データを選択的に復号する手段を含む
請求項６記載の通信路符号化システム。
【請求項９】
請求項５乃至7のいずれか1項に記載の通信路符号化システムの階層的通信路符号化装置を構成する各手段としてコンピュータを機能させることを特徴とする階層的通信路符号化プログラム。
【請求項１０】
請求項５乃至8のいずれか1項に記載の通信路符号化システムの階層的通信路復号装置を構成する手段としてコンピュータを機能させることを特徴とする階層的通信路復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信路符号化方法及び通信路符号化システム及び階層的通信路符号化プログラム及び階層的通信路復号プログラムに係り、特に、関連性のある階層データに対して、線形符号に用いる生成行列及び検査行列のタナーグラフの構成を変更することにより、任意の強度と任意の関係を保ち効率的にデータの誤りから保護するための階層符号化データに対する通信路符号化方法及び通信路符号化システム及び階層的通信路符号化プログラム及び階層的通信路復号プログラムに関する。
【背景技術】
【０００２】
現在、誤り訂正技術は衛星ディジタル放送やインターネットでの通信、モバイル端末での通信など、各種通信システムで広く用いられている。とりわけ、近年のブロードバンド環境の発展に伴い、インターネットを用いた動画配信サービスなどが期待されており、インターネット網に対する誤り訂正技術は重要なものになっている。以下、インターネット網を例に話を進める。
【０００３】
インターネットを用いてサービスを行う側から通信路を見ると、インターネット網は消失通信路（ＰＥＣ：Packet Erasure Channel）と捉えることができる。これは、図９に示すような２元消失通信路がパケットの単位としてグループ化されたものであり、通信路出力は正しい情報で出力されるか回線中の何らかの障害によって不明"＃"として出力されるかのどちらかの場合となる通信路である。この通信系においては、ＦＥＣ(Forward Error Correction)や、ＡＲＱ（Automatic Recovery Quotiet）と呼ばれる誤り訂正符号が用いられる。一般的なインターネットサービスでは、ＴＣＰ／ＩＰプロトコルが用いられ、デコーダ側では誤り検出のみに留め、誤りが発生した場合は再送制御などで誤りを訂正する方法が用いられている（ＡＲＱ方式）。しかし、マルチキャスト配信のような大規模なサービスを想定した場合、受信側で受け取ったデータを元に誤り訂正をすることが求められ、帰還通信路を必要とせず受信側のみで誤りを訂正できる方法が用いられる（ＦＥＣ方式）。このＦＥＣ方式は再送制御等を行わないことから遅延が少なく、リアルタイム性が重要となるテレビ会議システムでもＦＥＣ方式が用いられる。以下、ＦＥＣ方式について話を進める。
【０００４】
ＦＥＣ方式として、ディジタル放送などではリードソロモン符号（ＲＳ符号）が広く用いられている。日本のディジタル放送では符号長２０４バイトと定義されており、元データ１８８バイトに対しておよそ１０（％）のパリティバイトを付加することで誤りに対して耐性を持たせている。しかし、一般に誤り訂正符号として符号長の長い符号を利用すれば性能がよくなることが知られているが、符号長が長くなると復号が複雑になり計算量が膨大になってしまうという弊害も知られている。そのため、ＲＳ符号では大抵、最大符号長を２５５バイトとして扱うことが前提とされている。
【０００５】
これに対して、確率伝搬アルゴリズム（Belif propagation algorithm）に基づいた復号法は符号長が長い場合に実用的な演算量で優れた復号特性を持つことが知られており、非常に疎グラフにより定義される線形符号である低密度パリティ検査符号（Low density parity check code:ＬＤＰＣ符号）（例えば、非特許文献１参照）は、shannonにより定義された通信路容量に迫る現実的な誤り訂正方法として注目されている。また、疎グラフに基づく消失訂正符号としては、Digital Fountain社のＬＴcode（例えば、非特許文献２参照）や、Raptor code（例えば、非特許文献３参照）が知られており、符号化効率を大きく劣化させずに、任意の符号データを受信しただけで復号できる符号特性を実現的な演算量で達成することが知られている。この性質はインターネットマルチキャストプロトコルであるALC(Asynchronous Layered Coding）と適合するためにレイヤード構成されたマルチキャスト通信などで広く用いられている。
【非特許文献１】R.G.Gallager, "Low density parity check codes," in Research Monograph series. Cambridge, MIT Press, 1963
【非特許文献２】M.Luby, "LT Codes", The 49rd Annual IEEE Symposium on Foundations of Computer Science, 2002.
【非特許文献３】Shokrollahi, A, "Raptor codes," Information Theory, IEEE Transactions on Volume 52, Issue 6, 2006
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述のように、疎グラフと確率伝搬アルゴリズムに基づく誤り訂正符号は従来達成できなかった符号化特性を達成する。しかしながら、従来の技術では、保護対象データと保護するデータ（パリティデータ）が１対１の関係に限定されている。特に、近年では保護されるデータは段階的に符号化されるなどしてスケーラビリティを有しているが、従来の技術ではこの階層符号化データに対して統一的に誤りからデータを保護する誤り訂正符号を付加することはできない。
【０００７】
本発明は、上記の点に鑑みなされたもので、階層的に符号化されたデータに対して統一的に任意の誤り訂正符号を付加し、スケーラビリティ機能を損なわずに高品質な階層符号化データを提供可能な階層符号化データに対する通信路符号化方法及び通信路符号化システム及び階層的通信路符号化プログラム及び階層的通信路復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
図１は、本発明の原理を説明するための図である。
【０００９】
本発明（請求項１）は、階層的通信路符号化装置と階層的通信路復号装置からなるシステムにおいて、階層符号化されたデータを誤りから保護する通信路符号方法であって、
階層的通信路符号化装置において、
対象データをスケーラビリティ機能毎に分割した複数の階層データに対して、それぞれ１つの階層データのデータサイズと該階層データに付加されるパリティデータのサイズとに対応したサイズを有する疎行列を生成し、該生成した複数の疎行列を部分行列とする階層的疎行列を生成す階層的疎行列生成ステップ（ステップ１）と、
複数の階層データを部分行列とする行列に対して、階層的疎行列との排他的論理和演算を行うことにより階層データのそれぞれに対応するパリティデータを求める階層的符号化ステップ（ステップ２）と、
階層データ、パリティデータ及び階層的疎行列を階層的通信路復号装置に送信する送信ステップ（ステップ３）と、を行い、
階層的通信路復号装置において、
階層的通信路符号化装置から送信された階層データを、当該階層データに対応する受信したパリティデータが受信した階層的疎行列の部分行列と受信した当該階層データを含む１以上の階層データとの排他的論理和演算を行った結果に等しいとして求めた方程式を解くことによって復号する階層的復号ステップ（ステップ４）、を行う。
【００１０】
また、本発明（請求項２）は、階層的疎行列生成ステップ（ステップ１）において、
１つの階層データに対して、１つのパリティデータが生成されるよう階層的疎行列を生成するステップを行い、
階層的復号ステップ（ステップ４）において、
階層的疎行列を用いて階層データとパリティデータを１対１で復号するステップを行う。
【００１１】
また、本発明（請求項３）は、階層的疎行列生成ステップ（ステップ１）において、
階層的疎行列を、該階層的疎行列の１部分または全てを１つのランダムな疎なグラフにより定義される行列を用いて生成し、
階層的復号ステップ（ステップ４）において、
パリティデータを、１部分または全てを１つのランダムな疎なグラフにより定義された階層的疎行列の行列を用いて復号する。
【００１２】
また、本発明（請求項４）は、階層的復号ステップ（ステップ４）において、
受信したデータを選択的に復号する。
【００１３】
図２は、本発明の原理構成図である。
【００１４】
本発明（請求項５）は、階層符号化されたデータを誤りから保護するための階層的通信路符号化装置２０と階層的通信路復号装置３０からなるシステムであって、
階層的通信路符号化装置２０は、
対象データをスケーラビリティ機能毎に分割した複数の階層データに対して、それぞれ１つの階層データのデータサイズと該階層データに付加されるパリティデータのサイズとに対応したサイズを有する疎行列を生成し、該生成した複数の疎行列を部分行列とする階層的疎行列を生成す階層的疎行列生成手段１０４と、
複数の階層データを部分行列とする行列に対して、階層的疎行列との排他的論理和演算を行うことにより階層データのそれぞれに対応するパリティデータを求める階層的符号化手段１０２と、
階層データ、パリティデータ及び階層的疎行列を階層的通信路復号装置３０に送信する送信手段と、を有し、
階層的通信路復号装置３０は、
階層的通信路符号化装置２０から送信された階層データを、当該階層データに対応する受信したパリティデータが受信した階層的疎行列の部分行列と受信した当該階層データを含む１以上の前記階層データとの排他的論理和演算を行った結果に等しいとして求めた方程式を解くことによって復号する階層的復号手段１０８を有する。
【００１５】
また、本発明（請求項６）は、階層的通信路符号化装置２０の階層的疎行列生成手段１０４において、
１つの階層データに対して、１つのパリティデータが生成されるよう階層的疎行列を生成する手段を含み、
階層的通信路復号装置３０の階層的復号手段１０８において、
階層的疎行列を用いて階層データとパリティデータを１対１で復号する手段を含む。
【００１６】
また、本発明（請求項７）は、階層的通信路符号化装置２０の階層的疎行列生成手段１０４において、
階層的疎行列を、該階層的疎行列の１部分または全てを１つのランダムな疎なグラフにより定義される行列を用いて生成する手段を含み、
階層的通信路復号装置３０の階層的復号手段１０８において、
パリティデータを、１部分または全てを１つのランダムな疎なグラフにより定義された階層的疎行列の行列を用いて復号する手段を含む。
【００１７】
また、本発明（請求項８）は、階層的通信路復号装置３０の階層的復号手段１０８において、受信したデータを選択的に復号する手段を含む。
【００１８】
本発明（請求項９）は、請求項５乃至7のいずれか1項に記載の通信路符号化システムの階層的通信路符号化装置を構成する各手段としてコンピュータを機能させる階層的通信路符号化プログラムである。
【００１９】
本発明（請求項１０）は、請求項５乃至8のいずれか1項に記載の通信路符号化システムの階層的通信路復号装置を構成する手段としてコンピュータを機能させる階層的通信路復号プログラムである。
【発明の効果】
【００２０】
本発明によれば、階層符号化されたデータに対して任意の関係を考慮した誤り訂正符号を実施することが可能であり、受信ユーザの要求に沿った階層符号化データのスケーラビリティ機能を損なうことなく誤り訂正符号を統一的に付加することができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
図３は、本発明により実現可能な階層符号化データに対する誤り訂正機能を示している。本発明は、入力データに依存せずに実施できるが、一例として画像の符号化に応用した場合について説明する。
【００２３】
画像を入力信号とすると、情報源符号化装置１０では、階層的情報源符号化手段において、JPEG2000（ISO/IEC 15444-2. "JPEG2000 image coding system," 2000）やMPEG SVC(Scalable video coding)(J.Reichel, H. Schwarz and M. Wien:"Joint Scalable Video Model JSVM-6," ISO/IEC JTC1/SC29/Wg11,N8015, Montreux, April, 2006)といった階層符号化方式により階層的にデータ圧縮が行われ、階層データが通信路符号化装置２０に出力される。本発明は、通信路符号化装置２０において、この階層データに対してデータの階層間の関係に基づいて任意の誤り訂正データを付加することができ、また、任意の要求条件（例えば、復号処理量や帯域幅）に応じて階層データを保護／復号することができる。つまり、階層に符号化されたスケーラビリティを有した圧縮データに対して、任意の要求に沿った階層的な誤り訂正データを付加することができるスケーラビリティを有した誤り訂正が実現される。
【００２４】
図４は、本発明の一実施の形態における階層的通信路符号化システムの構成を示す。
【００２５】
同図に示す階層的通信路符号化システム１００は、階層データ分割部１０１、階層的符号化部１０２、乱数信号生成部１０３、階層的疎行列生成部１０４からなる階層的通信路符号化装置２０と、送信モジュール１０５と、チャネル１０６と、受信モジュール１０７と、階層的復号部１０８を有する階層的通信路復号装置３０と、データ並べ替え部１０９とヘッダ書き換え部１１０を有する階層データ合成装置５０から構成される。
【００２６】
階層的通信路符号化装置２０は、階層データ分割部１０１、階層的符号化部１０２、乱数信号生成部１０３、階層的疎行列生成部１０４を有する。
【００２７】
階層的通信路符号化装置２０の階層データ分割部１０１は、入力された階層符号化データを任意の階層毎に分割する。なお、階層毎に分割されたデータは内部のメモリ（図示せず）や、階層データ分割部１０１に接続されている記憶手段（図示せず）等に一時的に格納しておくものとする。
【００２８】
乱数信号生成部１０３は、ランダムな信号を発生させ、階層的疎行列生成部１０４に出力する。
【００２９】
階層的疎行列生成部１０４は、乱数信号生成部１０３で発生させたランダムな信号を用いて階層的な符号化を可能にする疎行列を生成する。なお、生成された疎行列（階層的疎行列）を内部のメモリ（図示せず）または、階層的疎行列生成部１０４に接続される記憶手段（図示せず）に一時的に格納しておくものとする。
【００３０】
階層的符号化部１０２は、階層データ分割部１０１により分割された階層に対して階層的疎行列生成部１０４で作成された疎行列を用いて階層的な誤り訂正データを作成する。なお、生成された誤り訂正データを内部のメモリ（図示せず）または、階層的符号化部１０２に接続される記憶手段（図示せず）に一時的に格納しておくものとする。
【００３１】
送信モジュール１０５は、階層的符号化部１０２、階層的疎行列生成部１０４から出力されたデータを送信する。
【００３２】
チャネル１０６は、インターネット等の回線であるチャネルである。
【００３３】
受信モジュール１０７は、送信モジュール１０５により送信されるデータを受け取る。
【００３４】
階層的通信路復号装置３０の階層的復号部１０８は、階層的に誤り訂正符号を復号する。なお、復号されたデータを内部のメモリ（図示せず）または、階層的復号部１０８に接続される記憶手段（図示せず）等に格納しておくものとする。
【００３５】
階層データ合成装置５０は、データ並べ替え部１０９とヘッダ書き換え部１１０を有する。
【００３６】
データ並べ替え部１０９は、階層的復号部１０８で復号されたデータをデコード可能なデータに変換する。
【００３７】
ヘッダ書き換え部１１０は、データ並べ替え部１０９で並べ替えられたデータのヘッダを書き換える。
【００３８】
図４に示すシステムは、入力された階層符号化データから１つの階層のみならず、任意の階層に対して誤り訂正を実施することが可能な階層的通信路符号化システムであるが、簡単化のために以下ではインターネットでの映像配信を想定して階層化符号化データに対する階層的通信路符号化方法を述べる。しかし、入力データは映像信号のみならず、階層的符号化されるあらゆるデータを対象とすることが可能である。
【００３９】
入力される画像の多くはスケーラビリティ機能を有した国際標準規格のJPEG2000で符号化が行われているとする。JPEG2000データは、プログレッションオーダにより様々な階層をもつことができる。図５に、RLCPと呼ばれるプログレッションオーダ順序を有したJPEG2000のデータ構造を示す。
【００４０】
図６は、本発明の一実施の形態における概要動作のフローチャートである。
【００４１】
ステップ１０）  階層的通信路符号化装置２０の乱数信号生成部１０３において、乱数（ランダム信号）を発生させ、階層的疎行列生成部１０４に出力する。
【００４２】
ステップ２０）  階層的疎行列生成部１０４では、乱数信号生成部１０３により生成されたランダム信号を元に疎行列Ｐを生成し、疎行列Ｐを複数組み合わせて階層的疎行列Ｇを生成し、メモリ等の記憶手段（図示せず）に格納する。
【００４３】
まず、疎行列Ｐの作成方法について説明する。
【００４４】
疎行列の作成方法は様々な方法が提案されているが、その中で、非特許文献１、文献１「David J. C. MacKay, "Good Error-Correcting Codes Based on Very Sparse Matrices". IEEE Transaction on Information Theory, Vol. 45, No.2, March, 1999」に述べられている乱数を用いる方法が簡単に効率よく疎行列を作成することができる。以下では、文献１に記載されている方法を説明する。
【００４５】
図７は、本発明の一実施の形態における階層的疎行列生成部の疎行列Ｐの作成処理のフローチャートである。但し、以下のmは疎行列Ｐの行数を示し、ｋは列数を示す。
【００４６】
ステップ２０１）  全て０の行列Ｐ（ｍ×ｋ）を作成する。
【００４７】
ステップ２０２）  カウントｉ＝０，ｊ＝０とする。
【００４８】
ステップ２０３）  乱数信号生成部１０３から入力された乱数に基づいて各列ビットを反転させる。乱数信号生成部１０３における反転確率は、各列がｔビット程度反転する程度とする。
【００４９】
ステップ２０４）  ｉ＝ｉ＋１とする。
【００５０】
ステップ２０５）  ｍ＜ｉであればステップ２０６に移行し、そうでなければステップ２０３に戻る。
【００５１】
ステップ２０６）  ｊ＝ｊ＋１とする。
【００５２】
ステップ２０７）  ｋ＜ｊであればステップ１０８に移行し、そうでなければステップ２０３に戻る。
【００５３】
ステップ２０８）  上記で生成された疎行列Ｐについて以下の処理を行う。
【００５４】
上記の処理により構成された疎行列Ｐに対して、できる限り全ての列（ｍ）の"１"の立つ数をｔ個とし、できる限り全ての列の"１"の立つ行（ｋ）の数も均等(具体的な平均ビット数は行列の大きさに依存するが、２ｍ＝ｋの関係がある場合、行のビット数は２ｔ個となる)にする。ここで、「できる限り」とは、乱数に基づいて確率的に不安定であることを意味する。これにより構成された行列Ｐを可能な限り短いループが生じないようにする。
【００５５】
上記の方法は、一つの疎行列Ｐの作成方法であり、符号化に用いる階層的疎行列Ｇは、疎行列Ｐを組み合わせて様々なバリエーションが考えられる。
【００５６】
以下の式（１）中のＰｍ１，ｋｌを上記の方法で作成することも可能であるし、式（１）中のＰｍ１，ｋｌとＰｍ２，ｋ１をＰｍ１＋ｍ２、ｋ１として上記の方法で作成することも可能である。なお、符号化の強度はｍを変化させることにより変わるが、符号化効率は、上記の図７のフローチャートの処理が進むにつれて高くなる。
【００５７】
今、保護したい階層データは（ｕｋ１，ｕｋ２）であり、階層データ（ｕｋ２）は階層データ（ｕｋ１）が無いと意味をなさない信号であったとする。これは、JPEG2000の低周波数成分（ＬＬ）と高周波成分（ＨＨ）の関係や、品質成分レイヤ１とレイヤ２の関係など、階層符号化データではこのような関係を持つことが多い。本発明はこのような場合に、階層データの関係に基づいて誤り訂正符号を統一的に付加することができるように階層的疎行列Ｇを生成する。すなわち、上記の例であれば、階層的疎行列Ｇを、
【００５８】
【数１】
0004674226.tif 000002
として生成する。但し、Ｐｍ，ｋはｋの疎行列である。そうすることにより、階層的符号化部１０２では、次式の演算でパリティビット（ｃｍ１、ｃｍ２）が生成できる。
【００５９】
【数２】
0004674226.tif 000003
なお、ｃｍ１は階層データｕｋ１に対するパリティビットであり、ｃｍ２は階層データｕｋ１及びｕｋ２に対するパリティビットである。また、式（２）はＧが疎行列であることと、exclusive OR(XOR)演算であることから、高速に少ない演算量でパリティビットを作成することができる。符号化は式（２）によってｃを生成することで行われる。
【００６０】
ステップ３０）  、階層的通信路符号化装置１００に入力されたデータを、階層データ分割部１０１において、このスケーラビリティ機能毎に分割したい単位に分割する。
【００６１】
図８は、本発明の一実施の形態における階層データ分割部の動作のフローチャートである。
【００６２】
ステップ３０１）  以下に示すｋは階層数（レイヤ数）であり、初期値としてｋ＝１とする。なお、階層数の最大数をＬとする。
【００６３】
ステップ３０２）  階層符号化データを分割するにあたり、以下のように初期化を行う。
【００６４】
【数３】
0004674226.tif 000004
ステップ３０３）  階層データ分割部１０１は、入力された階層符号化データｕｋを以下のように分割し、階層データ分割部１０１内のメモリ等の記憶手段（図示せず）に格納する。
【００６５】
【数４】
0004674226.tif 000005
ステップ３０４）
【００６６】
【数５】
0004674226.tif 000006
には、処理を終了し、それまではステップ３０５に移行する。
【００６７】
ステップ３０５）  ｋの値を１インクリメント（ｋ＝ｋ＋１）してステップ３０３に戻る。
【００６８】
つまり、JPEG２０００の場合では解像度や品質、色フォーマット、位置情報等の階層データを任意の階層として分割される。便宜上ここでは、２つの階層（ｕｋ１，ｕｋ２）のベクトルデータに分割されたとする。ｋ１，ｋ２はそれぞれ階層数である。分割されたデータは、メモリ（図示せず）に一時的に格納された後、階層的符号化部１０２に送られる。
【００６９】
ステップ４０）  階層的符号化部１０２は、後述する階層的疎行列生成部１０４で生成される疎行列を用いて１つの階層及び任意の階層に対して任意の誤り訂正符号を付加する。
【００７０】
図９は、本発明の一実施の形態における階層的符号化部の動作のフローチャートである。
【００７１】
ステップ４０１）  初期値としてパリティデータの個数ｍをｍ＝１とする。
【００７２】
ステップ４０２）  階層的疎行列生成部１０４で生成された階層的疎行列Ｇに基づいて、パリティデータＣｍを生成し、当該階層的符号化部１０２内のメモリ等の記憶手段（図示せず）に格納する。
【００７３】
ステップ４０３）
【００７４】
【数６】
0004674226.tif 000007
であればステップ４０４に移行し、そうでなければ処理を終了する。
【００７５】
ステップ４０４）  カウントｍを１インクリメント（ｍ＝ｍ＋１）し、ステップ４０２に移行する。
【００７６】
ステップ５０）  階層データｕ及びパリティデータｃと符号化に用いた階層的疎行列Ｇは、通信モジュール１０５に送られ、チャンネル１０６を通じて受信モジュール１０７に配信される。
【００７７】
ステップ６０）  受信モジュール１０７は、チャネル１０６から受信したデータを階層的通信路復号装置３０に送信する。
【００７８】
ステップ７０）  配信されたデータは、階層的通信路復号装置３０に送られ、一旦、メモリ等の記憶手段（図示せず）に格納され、階層的復号部１０８によりスケーラビリティに応じた復号を行う。
【００７９】
図１０は、本発明の一実施の形態における階層的復号部の動作のフローチャートである。
【００８０】
ステップ７０１）  レイヤのカウントを初期化（Ｌ＝１）する。
【００８１】
ステップ７０２）  受信データ（ｎ，ｃ）の数を初期化（ｄ＝１)する。
【００８２】
ステップ７０３）  階層的疎行列Ｇ、受信データｕ，ｃに基づいて上記の式（２）の連立方程式を解く。
【００８３】
ステップ７０４）
【００８４】
【数７】
0004674226.tif 000008
であればステップ７０６に移行し、そうでなければステップ７０５に移行する。
【００８５】
ステップ７０５）  Ｌ＜ｍａｘ（Ｌ）であるかを判定し、そうであればステップ７０７に移行し、そうでなければ処理を終了する。
【００８６】
ステップ７０６）  ｄを１インクリメント（ｄ＝ｄ＋１）し、ステップ７０３に移行する。
【００８７】
ステップ７０７）  Ｌを１インクリメント（Ｌ=Ｌ＋１）し、次のレイヤの処理（ステップ７０２）に移行する。
【００８８】
すなわち、本発明の階層的復号部１０８では、デコーダの解像度や品質要求、また、処理速度などの要求に従って選択的に誤り訂正復号を行うことが可能となる。上記の２階層の例では、階層的行列Ｇを用いて式（２）を満たすように連立方程式を解くことにより復号が行われる。復号の手順は、一般的なＬＤＰＣ（Low Density Parity Check）の消失訂正符号のデコードと同じ動作で実行され、行毎に１次連立方程式を解いていく動作を繰り返し行うことで実行される。但し、例えば、受信端末の要求からある階層データ、ここでは階層データ（ｕｋ１）のみを復号、すなわち、部分復号をしたい場合は、次式を１次連立方程式として解いて復号を実施すればよい。
【００８９】
【数８】
0004674226.tif 000009
この機能により、従来技術では実現不可能であった階層符号化データの選択的誤り訂正復号が可能となり、プログレッション機能を損なうことなく誤り訂正符号を付加することが可能である。
【００９０】
ステップ８０）  選択的に復号されたデータは、一時的にメモリ（図示せず）に格納され、データ並べ替え部１０９によりデータの並べ替えを行う。
【００９１】
ステップ９０）  ヘッダ書き換え部１１０は、演算処理無しにヘッダ書き換え操作が行われ、JPEG2000等の一般的なデコーダで復号できるように変換される。
【００９２】
以上のようにして階層符号化データに対する階層的通信路符号化及び復号が行われる。
【００９３】
なお、本発明では、階層が二つの場合を例に説明を行ったが、階層多数の場合に用意に拡張され、例えば、階層データが（ｕｋ１，ｕｋ２，ｕｋ３）、階層データ（ｕｋ１）と階層データ（ｕｋ２）の関係及び階層データ（ｕｋ１）と階層データ（ｕｋ３）の関係がそれぞれ強く階層データ（ｕｋ２）と階層データ（ｕｋ３）に関連性がない場合などは、下記の疎行列を用いて符号化及び復号が行われる。
【００９４】
説明のために、次のような疎行列を考える。
【００９５】
【数９】
0004674226.tif 000010
従って、Ａ，Ｇ，Ｄはｕ１（Layer1）に、Ｂ，Ｅ，Ｈはu2（Layer2）に、Ｃ，Ｆ，Ｉはｕ３（Layer3）にそれぞれ対応することがわかる。ここで、０行列の挿入位置は、どのパリティデータにどのレイヤを保護する機能を持たせるかによって決定される。以下の式（４）は、ｃ１にｕ１を保護するように、ｃ２にｕ１及びｕ２を保護するように、ｃ３にｕ１及びｕ３を保護するようにそれぞれデータを付加した例である。
【００９６】
【数１０】
0004674226.tif 000011
（４）
上記のように、送信側の階層的通信路符号化装置２０では、乱数に基づき生成した複数の疎行列Ｐからなる式（１）、（４）等で示される階層的疎行列Ｇを生成し、対象データを分割して生成した階層データｕと階層的疎行列Ｇとの間で式（２）で表される排他的論理和演算を行うことにより、パリティデータｃを求め、階層データｕ、パリティデータｃ、及び階層的疎行列Ｇを送信する。
【００９７】
受信側の階層的通信路復号装置３０では、受信した階層データｕ、パリティデータｃ、及び階層的疎行列Ｇを用いて、式（２）を満たすように連立方程式を解くことにより、エラー訂正及び復号を行う。
【００９８】
また、階層データの部分復号を行う場合には、受信側では、受信した階層データｕ、パリティデータｃ、及び階層的疎行列Ｇのそれぞれ一部分を用いて、式（３）を満たすように連立方程式を解くことにより、エラー訂正及び復号を行う。
【００９９】
このように、本発明の疎行列は階層データにより様々なバリエーションを持ち、その疎行列の作成方法はＬＤＰＣ符号（非特許文献１）等の方法で作成される疎行列を用いることができる。
【０１００】
なお、上記の階層的通信路符号化装置及び階層的通信路復号装置の動作をプログラムとして構築し、階層的通信路符号化装置、階層的通信路復号装置として利用されるコンピュータにインストールして実行する、または、ネットワークを介して流通させることが可能である。
【０１０１】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１０２】
本発明は、衛星ディジタル放送、インターネットでの通信、モバイル端末での通信等における誤り訂正技術に適用可能である。
【図面の簡単な説明】
【０１０３】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明により実現可能な階層符号化データに対する誤り訂正機能を示す図である。
【図４】本発明の一実施の形態における階層的通信路符号化システムの基本構成図である。
【図５】プログレッションオーダがＲＬＣＰのＪＰＥＧ２０００データ構造を示す図である。
【図６】本発明の実施の形態における概要動作のフローチャートである。
【図７】本発明の一実施の形態における階層的疎行列生成部の疎行列Ｐの作成処理のフローチャートである。
【図８】本発明の一実施の形態における階層データ分割部の動作のフローチャートである。
【図９】本発明の一実施の形態における階層的符号化部の動作のフローチャートである。
【図１０】本発明の一実施の形態における階層的復号化部の動作のフローチャートである。
【図１１】２元消失通信路を示す図である。
【符号の説明】
【０１０４】
１０  情報源符号化装置
２０  階層的符号化装置
３０  階層的復号装置
４０  情報源復号装置
５０  階層データ合成装置
１００  階層的通信路符号化システム
１０１  階層データ分割部
１０２  階層的符号化手段、階層的符号化部
１０３  乱数信号生成部
１０４  階層的疎行列生成手段、階層的符号化部
１０５  送信手段、送信モジュール
１０６  チャンネル
１０７  受信手段、受信モジュール
１０８  階層的復号手段、階層的復号部
１０９  データ並べ替え部
１１０  ヘッダ書き換え部
【図１】
0004674226.tif 000012
【図２】
0004674226.tif 000013
【図３】
0004674226.tif 000014
【図４】
0004674226.tif 000015
【図５】
0004674226.tif 000016
【図６】
0004674226.tif 000017
【図７】
0004674226.tif 000018
【図８】
0004674226.tif 000019
【図９】
0004674226.tif 000020
【図１０】
0004674226.tif 000021
【図１１】
0004674226.tif 000022