符号化シンボルのパケット化方法及びその方法を用いる装置
【課題】伝達するパケット間の属性を減少させ、安定的にＱｏＳを満たすパケット化方法及び装置を提供する。
【解決手段】符号化対象である第１ソースシンボルを決定し、And-Orツリー構造を利用して生成した第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合、パケット化していない第１符号化シンボルとパケット化していない第１符号化シンボルを挿入する目標パケットを選択する符号化シンボル及び目標パケット選択段階と、And-Orツリー構造を用いて生成された第１符号化シンボルに基づく第２ソースシンボルの生成後、And-Orツリー構造を利用して第２ソースシンボルに基づいて第２符号化シンボルを生成し、第２符号化シンボルのうち少なくとも１つを目標パケットに第１符号化シンボルと共にパケット化するパケット化段階とを含む。
【解決手段】符号化対象である第１ソースシンボルを決定し、And-Orツリー構造を利用して生成した第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合、パケット化していない第１符号化シンボルとパケット化していない第１符号化シンボルを挿入する目標パケットを選択する符号化シンボル及び目標パケット選択段階と、And-Orツリー構造を用いて生成された第１符号化シンボルに基づく第２ソースシンボルの生成後、And-Orツリー構造を利用して第２ソースシンボルに基づいて第２符号化シンボルを生成し、第２符号化シンボルのうち少なくとも１つを目標パケットに第１符号化シンボルと共にパケット化するパケット化段階とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化シンボルのパケット化方法及びその方法を用いる装置に関し、より詳細には、シンボルをパケット化する方法及びその方法を用いる装置に関する。
【背景技術】
【０００２】
ネットワーク及びビデオコーディングを研究する分野においてビデオストリーミング技術は、重要に取り扱われている分野である。ビデオは、多量のデータを有しているだけでなく、データのＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）要求に起因して、実際ネットワーク環境でビデオストリーミングトラフィックを伝送することは難しい。
【０００３】
このようなビデオストリーミングにおいてビデオデータの量を減らすために効果的なビデオ圧縮アルゴリズムを用いることが必須である。
【０００４】
今まで効果的なビデオ圧縮アルゴリズムのためのデジタルビデオコーディング技術は、急速に発展した。ＭＰＥＧ−１、２、４、とＨ．２６１、Ｈ．２６３／＋／＋＋及びＨ．２６４のような国際的標準は、ＩＳＯ／ＩＥＣとＩＴＵ−Ｔの多様な要求事項を満足させるために提案されてきた。圧縮されたビデオデータは、エントロピーコーダーの特性とビデオの場面変換／不規則な動き変化に起因して、多様なビットレートを有する。高い圧縮率で圧縮されたビデオデータは、低い圧縮率で圧縮されたビデオデータより相対的に伝送エラーと損失に弱い。
【０００５】
無線ネットワークで高い品質の安定的なビデオストリーミングサービスを効果的に提供することは、解決すべき課題である。
【０００６】
ビデオデータを伝送するに際して、経路損失、フェーディング、マルチパス及び干渉現象は、無線リンクで受信されたビデオデータのＳＮＲ（Ｓｉｇｎａｌ ｔｏ Ｎｏｉｓｅ Ｒａｔｉｏ）で不規則な変化をもたらす。
【０００７】
低いＳＮＲで受信された信号をデコードすることは難しく、その結果として、ＢＥＲ（Ｂｉｔ Ｅｒｒｏｒ Ｒａｔｅ）を増加させる。無線ネットワークでデータ伝送エラーと損失を緩和させるためには、ＡＲＱ（Ａｕｔｏｍａｔｉｃ Ｒｅｐｅａｔｒｅ Ｑｕｅｓｔ）とＦＥＣ（Ｆｏｒｗａｒｄ Ｅｒｒｏｒ Ｃｏｒｒｅｃｔｉｏｎ）が広く使用される。
【０００８】
ＡＲＱは、フィードバック情報を受信した後、損失されたデータをさらに伝送しなければならないので、ディレイを増加させる。これによって、ＡＲＱは、ディレイに敏感なビデオストリーミングに適しないエラー防止方法になる。
【０００９】
しかしながら、ＦＥＣは、ネットワークでフィードバック情報が不要であり、データの損失とエラーを補償するための追加データを必要とする。このようなＦＥＣの特徴は、ＡＲＱ方法に比べてディレイに敏感なビデオストリーミングにおいて適している。
【００１０】
ルビー変換、ラプター、オンラインコードのようなファウンテン（Ｆｏｕｎｔａｉｎ）コードは、ブロック基盤のＦＥＣ技術である。このようなファウンテンコードは、高いコーディング効率、低いエンコード／デコード処理時間及び適応性のような特性を有しているので、エラーが発生しやすい無線ネットワークでディレイに敏感なデータを伝送するのに非常に有用である。
【００１１】
ファウンテンコードは、チャンネルコーディングのレートレスコード（Ｒａｔｅｌｅｓｓ ｃｏｄｅ）であって、送信端側で受信端に対する情報が足りないか、または受信端の数が非常に多い場合のように、双方向情報伝送が難しい時にも、単方向伝送だけでエラーなしで完全な受信を可能にするという長所を持つ。
【００１２】
これまでファウンテンコードは、消去チャンネル（Ｅｒａｓｕｒｅ Ｃｈａｎｎｅｌ）において研究されて来ており、その他のチャンネルにおける適用が活発に進んでいる。消去チャンネルは、どんな情報が送信されるかに関係なく、一定の確率でその情報が消去され、何が伝送されたか分からないチャンネルである。このチャンネルは、理論的な仮想チャンネルとして認識されてきたが、最近、インターネットの発展に伴い、消去チャンネルは、インターネットをモデリングすることができるチャンネルとして注目された。
【００１３】
インターネット上で各パケットは、正確に伝送されるか、どんなパケットが伝送されるかは関係なく、一定の確率で正確に受信、または消去される場合だけが適用されるので、インターネットチャンネルの環境は、消去チャンネルとしてモデリングされる。
【００１４】
ファウンテンコードは、様々な分野において標準化に対する論議がなされている。現在までは、２００５年ラプターコード（Ｒａｐｔｏｒ Ｃｏｄｅ）が３ＧＰＰ ＴＳ ２６．３４６ ＭＢＭＳとＤＶＢ−Ｈ ＩＰ Ｄａｔａｃａｓｔで使用される標準放送用チャンネル符号化アルゴリズムとして採択された。標準で使用されているラプターコードは、システマチック（Ｓｙｓｔｅｍａｔｉｃ）な特性をもつように定義された。３ＧＰＰ ＭＢＭＳとＤＶＢ−Ｈでは、このような特性のラプターコードを実現するために、プレコード（Ｐｒｅ−Ｃｏｄｅ）過程でＬＴデコードを用いる。すなわち、既存のソースシンボルをラプターコード内のＬＴコード部分のようなソースシンボル選択パターンで符号化されたシンボルとして仮定する。したがって、これをＬＴデコードして得た中間段階シンボルをＬＴ エンコードすれば、伝送すべきエンコードシンボル内には、ソースシンボルがそのまま含まれる。
【００１５】
ファウンテンコードは、基本的に消去チャンネルで動作するように設計されるので、有線ネットワーク上での通信においても適しているが、無線通信でもＭＡＣレイヤー（Ｌａｙｅｒ）上では、ＣＲＣが適用され、受信されたパケットが正しい情報であるか否かだけが決定されるので、消去チャンネルのような場合と見なしてファウンテンコードを適用することができる。ＭＡＣレイヤーで使用される他のコーディング技法であるＨ−ＡＲＱと比較してみると、ファウンテンコードは、送信端と受信端との間の相互作用がなくても、受信端でエラーなしに正確に情報を受信することができるという特徴がある。したがって、両端の間で情報を正確に受信するまで繰り返し相互作用によって通信するＨ−ＡＲＱ伝送技法に比べて長所を有する。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
安定的にＱｏＳを満足させるビデオストリーミングサービスを行うためには、無線ネットワークで発生するパケット損失により発生するデータの損失を最小化するために、伝達されるパケット間の従属性を減少させて、パケット損失を最小化しなければならない。また、エラーが発生しやすい無線ネットワークで十分な数の符号化シンボルを伝送することができるか否かを予想し、同じ数のパケットでＬＴデコード失敗率を低減しなければならない。
【００１７】
したがって、本発明の第１目的は、パケット損失を最小化するためのＡｎｄ−Ｏｒツリーを用いた符号化シンボルをパケット化する方法を提供することにある。
【００１８】
また、本発明の第２目的は、パケット損失を最小化するためのＡｎｄ−Ｏｒツリーを用いた符号化シンボルをパケット化する方法を用いる装置を提供することにある。
【課題を解決するための手段】
【００１９】
上記目的を達成するために、本発明の一態様による符号化シンボルのパケット化方法は、第１ソースシンボルを決定し、ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルと前記パケット化していない第１符号化シンボルを挿入する目標パケットを選択する符号化シンボル及び目標パケット選択段階と、前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づいて少なくとも１つの第２符号化シンボルを生成し、前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化するパケット化段階とを含む。前記符号化シンボルは、ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を利用して符号化したシンボルであってもよい。符号化シンボルのパケット化方法は、前記符号化シンボル及び目標パケット選択段階と前記パケット化段階でパケット化していない第１符号化シンボルが存在しない場合、前記第１ソースシンボルではなく、前記第１ソースシンボルと同じＡＮＤ−ＯＲツリー階層にあるソースシンボルを第１ソースシンボルとして前記符号化シンボル及び目標パケット選択段階とパケット化段階を進行することができる。
【００２０】
符号化シンボルのパケット化方法は、前記符号化シンボル及び目標パケット選択段階と前記パケット化段階でパケット化していない第１符号化シンボルが存在せず、前記他のソースシンボルを第１ソースシンボルとして選択することができない場合、まだパケット化していない第２符号化シンボルのうち少なくとも１つを前記目標パケットの残ったスペースに挿入することができる。前記パケット化段階で、前記第１符号化シンボルと共にパケット化される前記第２符号化シンボルが下記の数式１を満たせる値として決定される。
【００２１】
【数１】
【００２２】
前記符号化シンボル及び目標パケット選択段階で、前記目標パケットは、空きパケットが存在する場合には、前記空きパケットのうち少なくとも１つを目標パケットとし、
空きパケットが存在しない場合には、所定のパケットの使用可能なスペースがＲthr＋１より大きいければ、前記所定のパケットの使用可能なスペースがＲthr＋１より大きいパケットの１つを目標パケットとして決定し、前記所定のパケットの使用可能なスペースが前記Ｒthr＋１より大きくなければ、前記Ｒthr＋１が
（
は、第１符号化シンボルの次数を意味する。）より大きいか等しく、かつ、前記所定のパケットの使用可能なスペースが
より大きいか等しい場合に、前記所定のパケットのうち少なくとも１つとして選択される。
【００２３】
前記ＡＮＤ−ＯＲツリーは、前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が第１ソースシンボルの値として決定され、前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が第１符号化シンボルの値として決定され、前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が第２ソースシンボルの値として算出されることができる。前記符号化シンボルのパケット化方法は、ビデオストリーミングサービスでビデオデータを伝送するのに使用されてもよい。
【００２４】
また、本発明の他の態様による符号化シンボルのパケット化装置は、符号化対象であるソースシンボルに基づいてＡＮＤ−ＯＲツリーを用いて符号化シンボルを生成し、前記符号化シンボルに基づいて前記ＡＮＤ−ＯＲツリーを用いてソースシンボルを生成するツリー構造化部と、前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部とを含んでもよい。前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、第１ソースシンボルを決定し、前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルと前記パケット化していない第１符号化シンボルを挿入する目標パケットを選択し、前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づく少なくとも１つの第２符号化シンボルを生成し、前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化することができる。
【００２５】
前記ＡＮＤ−ＯＲツリーは、前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が第１ソースシンボルの値として決定される。また、前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が第１符号化シンボルの値として決定される。そして、前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が第２ソースシンボルの値として算出される。前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、パケット化していない第１符号化シンボルが存在しない場合には、前記第１ソースシンボルを除いた他の第１ソースシンボルを選択する。前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記他の第１ソースシンボルの符号化シンボルである第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合には、前記パケット化していない第１符号化シンボルを選択する。そして、前記パケット化していない第１符号化シンボルを挿入する目標パケットを決定して、前記第１符号化シンボルを前記目標パケットに挿入する。また、前記ＡＮＤ−ＯＲツリー構造を利用して、生成された前記第１符号化シンボルに基づく第２ソースシンボルを生成した後、前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づいて第２符号化シンボルを生成する。また、前記第２符号化シンボルを前記目標パケットに前記第１符号化シンボルと共にパケット化する。前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、パケット化していない第１符号化シンボルが存在せず、前記第１ソースシンボルを除いた他の第１ソースシンボルを選択することができない場合には、まだパケット化していない第２符号化シンボルのうち少なくとも１つを前記目標パケットの残ったスペースに挿入してもよい。前記符号化シンボルは、ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を利用して符号化したシンボルであってもよい。符号化シンボルのパケット化装置は、ビデオストリーミングサービスにおいて、ビデオデータを伝送するのに使用されることができる。
【発明の効果】
【００２６】
本発明の実施形態による符号化シンボルのパケット化方法及びこのような方法を用いる装置によれば、無線ネットワークにおいて、ビデオストリーミングサービスを助けるために、Ａｎｄ−Ｏｒツリーに基づく符号化シンボルのパケット化を行う。まず、エンコードされたシンボル間の関係は、Ａｎｄ−Ｏｒツリーを用いることによって分析される。分析された結果に基づいてエンコードされたシンボルは、パケット間に相関を減少させる方法を用いて、データ伝送の間に損失されたパケットの効果は地域的に限定される。
【００２７】
したがって、無線ネットワークで発生するパケット損失を最小化することができ、特に、ビデオストリーミングサービスの品質低下を最小化し、伝達するパケット間の従属性を減少させて、安定的にＱｏＳを満足させるビデオストリーミングサービスを提供することができる。
【図面の簡単な説明】
【００２８】
【図１】エラーが発生しやすい無線ネットワークでビデオストリーミングシステムを示す。
【図２】本発明の一実施形態によるＬＴ符号化シンボル間に繰り返し的な符号化過程を示すツリー構造である。
【図３】本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示す概念図である。
【図４】本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示すフローチャートである。
【図５】本発明の一実施形態による提案されたパケット化アルゴリズムの制御変数Ｒｔｈｒの条件をテストしたグラフである。
【図６】本発明の一実施形態による提案されたパケット化アルゴリズムの制御変数Ｒｔｈｒの条件をテストしたグラフである。
【図７】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図８】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図９】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図１０】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図１１】パケット損失パターンが集中されている場合、ケース１の遷移確率分布（Ｔｒａｎｓｉｔｉｏｎ Ｐｒｏｂａｂｉｌｉｔｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ）を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１２】パケット損失パターンが集中されている場合、ケース１の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１３】パケット損失パターンが集中されている場合、ケース１の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１４】パケット損失パターンが集中されている場合、ケース１の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１５】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１６】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１７】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１８】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１９】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２０】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２１】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２２】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２３】本発明の一実施形態による符号化シンボルをパケット化して伝送する装置を示す概念図である。
【発明を実施するための形態】
【００２９】
本発明は、多様な変更を加えることができ、様々な実施形態を有することができるため、その実施形態を図面に例示して詳細に説明する。これは、本発明を特定の実施形態に限定しようとするものではなく、本発明の思想及び技術範囲に含まれるすべての変更、均等物及び代替物を含むものと理解すべきである。なお、各図面を説明するに際して、同一の参照符号を同一の構成要素に用いる。
【００３０】
第１、第２などの用語は、多様な構成要素を説明するのに使用されることができるが、前記構成要素は、前記用語に限定されるわけではない。前記用語は、１つの構成要素を他の構成要素から区別する目的のみに使用される。例えば、本発明の権利範囲を逸脱しない範囲内で、第１構成要素は、第２構成要素として称することができ、同様に、第２構成要素も第１構成要素として称することができる。「及び／または」という用語は、複数の関連された記載項目の組み合わせまたは複数の関連された記載項目のうちいずれかの項目を含む。
【００３１】
任意の構成要素が他の構成要素に「連結されて」いるか、「接続されて」いると記述されたときには、他の構成要素に直接的に連結されているか、または接続されていることもあるが、間に他の構成要素が存在することも有り得ると理解すべきである。一方、任意の構成要素が他の構成要素に「直接連結されている」や、「直接接続されている」と記述されたときには、間に他の構成要素が存在しないものと理解すべきである。
【００３２】
本出願において用いた用語は、単に特定の実施形態を説明するために使用されたものであって、本発明を限定しようとする意図ではない。単数の表現は、文脈上、明白に異なったことを意味しない限り、複数の表現を含む。本出願において、「含む」または「有する」などの用語は、記述された特徴、数字、段階、動作、構成要素、部分品またはこれらを組み合わせたものが存在することを指すものであって、１つまたはそれ以上の他の特徴や、数字、段階、動作、構成要素、部分、またはこれらを組み合わせたものなどの存在または付加可能性をあらかじめ排除しないものと理解すべきである。
【００３３】
以下、添付の図面を参照して、本発明の好ましい実施形態をさらに詳細に説明する。以下、図面において、同一の構成要素については、同一の参照符号を使用し、同一の構成要素について重複説明は省略する。
【００３４】
以下、本発明の一実施形態による符号化シンボルのパケット化方法及びこのような方法を用いる装置では、ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を利用した符号化シンボルをパケット化する方法及びこのような方法を用いる装置について開示する。しかし、本発明の本質を逸脱しない範囲内で、ルビー変換コードだけでなく、他のコードにも本発明で開示された方法を適用することができ、これも、また本発明の権利範囲に属する。
【００３５】
以下、本発明の実施形態において用いるＬＴは、ルビー変換を意味し、以下の本発明の実施形態において同一の意味として使用されることができる。
【００３６】
図１は、エラーが発生しやすい無線ネットワークにおいてのビデオストリーミングシステムを示す。
【００３７】
図１を参照すれば、ビデオデータは、データの量を減少させるために、ビデオコーデックによって圧縮された形態で生成される。ビデオデータは、無線ネットワークで強靭な伝送のためにルビー変換を用いてエンコードされる。ＬＴエンコードプロセスを進行する間に、圧縮されたビデオデータストリームは、ソースブロックに分けられる。
【００３８】
ソースブロックは、あらかじめ定められたサイズのソースシンボルに分割される。ＬＴ符号化シンボルは、ソースシンボルの一部とマッピングされる。ＬＴ符号化シンボルは、ソースシンボルのＸＯＲ演算を行うことによって生成される。
【００３９】
このようなＬＴ符号化シンボルを生成するプロセスは、最後のＬＴ符号化シンボルが生成されるまで繰り返される。ソースシンボルとＬＴ符号化シンボルのマッピング手順は、生成多項式（Ｇｅｎｅｒａｔｏｒ Ｐｏｌｙｎｏｍｉａｌ）により制御できる。多くの無線ネットワークは、パケット交換方式を用いるので、ＬＴ符号化シンボルは、伝送前にパケット化されなければならない。
【００４０】
伝送途中に発生するパケット損失は、エラーが発生しやすい無線ネットワークで不可避な現象である。パケットが損失された場合、受信されたＬＴ符号化シンボルの数は、成功的なデコードのためには十分でないこともある。
【００４１】
仮に受信端が成功的なＬＴデコードのための十分なＬＴ符号化シンボルを得るまで持続的に多数のパケットが伝送できれば、エラーが発生しやすい無線ネットワークでは、エラーのないデコードが保証される。
【００４２】
しかしながら、ビデオストリーミングはディレイ制約があり、無線ネットワークは制限されたリソースなので、実際に、エラーのない成功的なデコードを保証することは難しい。このような問題を解決するために、エラーが発生しやすい無線ネットワークを介して十分な数の符号化シンボルを伝送することができるかを予想できることは重要である。
【００４３】
他に重要な問題としては、同じ数のパケットでどれほどＬＴデコード失敗率を低減できるかに関する。繰り返し的なデコードプロセスに存在する符号化シンボル間の従属性に起因して、ＬＴデコード性能は、符号化シンボルをどれほどパケット化するかによって変わる。それで、符号化シンボル間の従属性が考慮されていない場合、デコード性能は、著しく劣化される。例えば、ＬＴ符号化シンボルが不規則にパケットにグループ化される場合、損失されたパケットは、多くのソースシンボルが成功的にデコードされることを阻害することがある。
【００４４】
一般的にビデオストリーミングデータは、データの量を減らすために、高い圧縮率での圧縮を行うので、相対的にデータ損失にさらに脆弱である。それで、損失されたデータの小さい量は、重大なビデオ品質の低下を発生させることになる。
【００４５】
本発明の一実施形態によれば、データ損失を減らすために、ＬＴ符号化シンボルの間では、Ａｎｄ−Ｏｒツリーを用いる。このような分析に基づいて提案されたパケット化アルゴリズムは、各々のパケットでエンコードされたシンボル間に相関（Ｃｏｒｒｅｌａｔｉｏｎ）を増加させ、パケット間の相関を減少させる方向に設計される。
【００４６】
図２は、本発明の一実施形態によるＬＴ符号化シンボル間での繰り返し符号化する過程を示すツリー構造である。
【００４７】
図２を参照すれば、シンボル間の関係を誘導するための簡単なＡｎｄ−Ｏｒツリーが示されている。
【００４８】
Ａｎｄ−Ｏｒツリーは、符号化シンボル間の関係分析のための有用なツールであって、一般的に２ｌの深さを有するＡｎｄ−ＯｒツリーＴｌが存在する時、ルートノードの深さは、０を有し、ルートノードに直接連結された子ノードの深さは、１を有する。また、ツリーの下方に行きほど、ノードの深さは１ずつ増加するようになる。すべてのノードは、０または１の値を有する。また、深さ０、２、４、…、２ｌ−２に位置するノードは、Ｏｒ−ノードと言い、Ｏｒノードは、子ノードのＯｒ−演算を通じて値が決定される。１，３、５、…、２ｌ−２に位置するノードをＡｎｄ−ノードと言い、子ノードのＡｎｄ−演算を通じて値が決定される。このツリーにＬＴコードのシンボルをマッピングさせれば、ソースシンボルは、Ｏｒ−ノードとして、符号化シンボルは、Ａｎｄ−ノードとして見なされ、各々は、互いに親と子ノードで結ばれるようになる。
【００４９】
下記の表１は、本発明の一実施形態によるＡｎｄ−Ｏｒツリーに使用されるシンボルとシンボルの意味を示すものである。
【００５０】
【表１】
【００５１】
ｒｏｏｔはＯｒ−ノード、ＴＥＳiはＡｎｄ−ノードなので、他の目標符号化シンボルと関係なく、ＴＥＳiによってｒｏｏｔが復号化されるためには、
に属するソースシンボルが先行的にすべて復号化されなければならない。したがって、ＴＥＳiを利用してｒｏｏｔが成功的に復号化されるためには、深さ２に位置する符号化シンボルの影響を受けるようになる。すなわち、ＴＥＳiがｒｏｏｔの成功的な復号化に寄与するためには、
に属するソースシンボルが先行的に復号化されなければならない。
【００５２】
仮に受信端でＴＥＳiとさらに多い
に属する符号化シンボルを同時に受信する場合、
に属するソースシンボルをより多く復号化ができる。これにより、ｒｏｏｔの復号化成功率が高くなる。これは、ＴＥＳiと
に属する符号化シンボルが互いに強い依存性を有していることを意味する。
【００５３】
仮にＴＥＳiが伝送過程で損失されると、ツリー上で
に属する符号化シンボルとｒｏｏｔ間の繋がりが切れることになり、結局、
に属する符号化シンボルがｒｏｏｔの復号化に何ら寄与をすることができない。ＬＴ復号化成功率を高めるためには、このようなシンボル間の関係が考慮されるべきであり、この関係に基づいて下記のような３つの有用な属性を導き出せる。
【００５４】
属性１：ｒｏｏｔの復号化成功率は、
の各々を互いに異なるパケットに挿入することによって向上させることができる。
【００５５】
属性２：
に属する符号化シンボルがより多く利用可能であれば、
に属するソースシンボルの復号化成功率を向上させることができる。
【００５６】
属性３：ｒｏｏｔの復号化成功率は、ＴＥＳiと
に属する符号化シンボルを同じパケットに挿入することによって、向上させることができる。
【００５７】
但し、ｉ≠ｊ ｏｒ ｐ≠ｑであり、
と
とを、各々ソースシンボルｐとｑをｒｏｏｔとする時のＴＥＳiとＴＥＳjとの関連する符号化シンボルの集合であるとする時、
は、空集合ではないこともある。すなわち、一部のＬＴ符号化シンボルは、互いに異なる集合に同時に含まれることもある。
【００５８】
ＴＥＳiが属するパケットに一緒に挿入される
に属する符号化シンボルの数を調節することによって、このようなＡｎｄ−Ｏｒツリー間の依存性を間接的に考慮して、パケット化過程でツリー間の依存度を完全に制御するためには、非常に高い計算的な複雑度を要求する分析が必要である。
【００５９】
以下、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法では、説明の便宜上、Ａｎｄ−Ｏｒツリーの分析深さを３に制限して説明するが、Ａｎｄ−Ｏｒツリーは、３以上の深さを有することができ、このようなＬＴ符号化シンボルパケット化方法も本発明の権利範囲に属する。
【００６０】
以下、本発明の一実施形態によれば、ツリー構造で最も上端に位置するソースシンボルを第１ソースシンボル、第１ソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第１符号化シンボル、第１符号化シンボルをＡｎｄ−Ｏｒツリーを利用して生成したソースシンボルを第２ソースシンボル、第２ソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第２符号化シンボルという用語に定義して用いる。
【００６１】
すなわち、ツリーの深さが増加する場合、一般化してツリー構造で上端に位置するソースシンボルを第ｎソースシンボル、第ｎソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第ｎ符号化シンボル、第ｎ符号化シンボルをＡｎｄ−Ｏｒツリーを利用して生成したソースシンボルを第ｎ＋１ソースシンボル、第ｎ＋１ソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第ｎ＋１符号化シンボルという用語に定義して用いる。
【００６２】
図３は、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示す概念図である。
【００６３】
以下、本発明の実施形態では、ツリーの深さを３に限定して説明するが、これは、説明の便宜のためのものであって、本発明の本質を逸脱しない範囲内でツリーの深さは３を超える値になることもあり、このようなツリー構造を利用したパケット化方法も本発明の権利範囲に含まれる。
【００６４】
図３を参照すれば、ＴＥＳselを
のうちｒｏｏｔの復号化に寄与するために選択された目標符号化シンボルであるとすれば、前述した属性に基づいて本発明の一実施形態によるパケット化アルゴリズムは、
とＴＥＳselに属する、より多い符号化シンボルを同じパケットに挿入するように設計されなければならない。
を、ＴＥＳselと同じパケットに挿入される
に属する符号化シンボルであると定義することができる。ＴＥＳselが挿入されるパケットが目標パケットであるとすれば、
に属する符号化シンボルのうちいくつかの符号化シンボルが目標パケットにＴＥＳselと共に挿入されるべきかは、提案するパケット化アルゴリズムの制御変数Ｒthrによって決定される。 仮にＲthrが０の場合、提案するパケット化アルゴリズムは、既存のパケット化アルゴリズムと同一の動作を行う。提案するパケット化アルゴリズムの動作は、以下の段階を経て動作する。
【００６５】
段階０：ｒｏｏｔを決定する。
【００６６】
段階１：ｒｏｏｔの
において
であり、パケット化していないＴＥＳselを選択する。
（すべての
が既にパケット化されたら段階４を行う。）
【００６７】
段階２：ＴＥＳselを次のような規則により選択された目標パケットに挿入する（規則ｉは、規則（ｉ＋１）より優先順位が高い）。例えば、規則によって選択できる目標パケットがそれ以上存在しない場合は、段階４を行う。
【００６８】
規則１：仮に空きパケットが存在すれば、当該パケットを目標パケットとして決定する。
【００６９】
規則２：仮にパケットの使用可能なスペースがＲthr＋１より大きければ、当該パケットを目標パケットとして決定する。
【００７０】
規則３：仮にＲthrが
より大きいか等しく、パケットの使用可能なスペースが
より大きいか同一の場合、当該パケットを目標パケットとして決定する。
【００７１】
規則３は、パケットの残ったスペースを活用するためのものである。規則１、２の過程を経ると、パケットに実際のＲthr＋１より小さいスペースが残っていることもある。この場合、Ｒthr＋１の規則だけに従う場合、残ったスペースを活用することができない。
【００７２】
例えば、パケットに１０個の符号化シンボルが入れるとして、Ｒthrを５とすると、規則２に従う場合、パケットに６個のシンボル
が挿入される。すると、このパケットに４個の符号化シンボルが入ることのできるスペースが残るようになり、このパケットは、規則１と２を満たすことができない。この場合、規則３によって
を満たせる最小スペースが存在すれば、
個の
に属する符号化シンボルを挿入することができる。
【００７３】
段階３：
に属する符号化シンボルのうち、Ｒthr個を任意に選択して
を決定する（但し、
を集合Ａの大きさ（cardinality）とする時、
を満たす。）。そして、
を図３に示すように、目標パケットに挿入する。
【００７４】
すなわち、符号化対象である第１ソースシンボルを決定し、Ａｎｄ−Ｏｒツリー構造を利用して生成した第１ソースシンボルの符号化シンボルである第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、パケット化していない第１符号化シンボルを選択して、パケット化していない第１符号化シンボルを挿入する目標パケットを決定する。また、第１符号化シンボルを前記目標パケットに挿入する。Ａｎｄ−Ｏｒツリー構造を利用して、生成された前記第１符号化シンボルに基づく第２ソースシンボルを生成した後、Ａｎｄ−Ｏｒツリー構造を利用して第２ソースシンボルに基づいて第２符号化シンボルを生成する。前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化できる。
【００７５】
ツリーの深さが３以上の場合において、符号化対象である第ｎソースシンボルを決定し、Ａｎｄ−Ｏｒツリー構造を利用して生成した前記第ｎソースシンボルの符号化シンボルである第ｎ符号化シンボルのうちパケット化していない第ｎ符号化シンボルが存在する場合には前記パケット化していない第ｎ符号化シンボルを選択し、前記パケット化していない第ｎ符号化シンボルを挿入する目標パケットを決定して、前記第ｎ符号化シンボルを前記目標パケットに挿入することができる。また、Ａｎｄ−Ｏｒツリー構造を利用して、生成された第ｎ符号化シンボルに基づく第ｎ＋１ソースシンボルを生成した後、Ａｎｄ−Ｏｒツリー構造を利用して第ｎ＋１ソースシンボルに基づいて第ｎ＋１符号化シンボルを生成し、第ｎ＋１符号化シンボルのうち少なくとも１つを前記目標パケットに前記第ｎ符号化シンボルと共にパケット化することができる。
【００７６】
段階４：仮にこれ以上ｒｏｏｔを選択することができない場合は、段階５を行う。そうではない場合は、他のｒｏｏｔを選択して、段階１〜３を繰り返す。
【００７７】
段階５：残りのパケット化していない符号化シンボルをパケットの空きスペースに挿入する。
【００７８】
図４は、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示すフローチャートである。
【００７９】
図４を参照すれば、ｒｏｏｔを決定することができる（段階Ｓ４００）。
【００８０】
パケット化のためには、パケット化を行うｒｏｏｔを優先的に決定しなければならない。
【００８１】
パケット化していないＴＥＳselが存在するか否かを判断することができる（段階Ｓ４１０）。
【００８２】
パケット化していないＴＥＳselが存在しない場合、段階Ｓ４６０に進み、他のｒｏｏｔを選択することができるか否かを判断し、他のｒｏｏｔが選択できる場合、ルートを決定する段階Ｓ４００を繰り返す。
【００８３】
他のｒｏｏｔか存在しない場合、残った符号化シンボルをパケットの空きスペースに入れる段階Ｓ４７０を行う。
【００８４】
パケット化していないＴＥＳselが存在する場合、そのパケット化していないＴＥＳsel
を選択することができる（段階Ｓ４２０）。
【００８５】
ｒｏｏｔの
において
で、かつ、パケット化していないＴＥＳselを選択する。
【００８６】
ＴＥＳselを挿入する目標パケットを決定することができる（段階Ｓ４３０）。
【００８７】
ＴＥＳselを目標パケットに挿入するには、下記のような規則を用いて目標パケットを決定することができる。小さい番号の規則が大きい番号の規則より優先して適用される。
【００８８】
規則１：仮に空きパケットが存在すれば、当該パケットを目標パケットとして決定する。
【００８９】
規則２：仮にパケットの使用可能スペースがＲthr＋１より大きければ、当該パケットを目標パケットとして決定する。
【００９０】
規則３：仮にＲthrが
より大きいか等しく、パケットの使用可能なスペースが
より大きいか同一の場合、当該パケットを目標パケットとして決定する。
【００９１】
目標パケットを決定する上記規則は、小さい数字の規則１が最も優先順位が高く、規則３が最も優先順位が低い。すなわち、規則１を満足するパケットが優先的に目標パケットとして選択される。
【００９２】
ＴＥＳselを決定された目標パケットに挿入することができる（段階Ｓ４４０）。
【００９３】
段階Ｓ４３０によって決定された目標パケットにＴＥＳselを挿入する。
【００９４】
を決定し、目標パケットに挿入することができる（段階Ｓ４５０）。
【００９５】
に属する符号化シンボルのうちＲthr個を任意に選択し、
を決定する（但し、
を集合Ａの大きさとする時、
を満たす。）。そして、
を、図３に示すように目標パケットに挿入する。
【００９６】
ｒｏｏｔを選択することができるか否かを判断する（段階Ｓ４６０）。
【００９７】
パケット化が進んでいないｒｏｏｔが存在する場合、当該ｒｏｏｔを選択し、段階Ｓ４００から段階Ｓ４５０を繰り返し行う。
【００９８】
選択できるｒｏｏｔが存在しない場合、残りのパケット化していない符号化シンボルをパケットの残った空きスペースに挿入することができる（段階Ｓ４７０）。
【００９９】
本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化アルゴリズムの性能の尺度は、成功的に受信した
に属する符号化シンボルの数である。
と
を、各々提案されたパケット化アルゴリズムと既存のパケット化アルゴリズムを適用した時、エラーなく成功的に受信端で受信した
に属する符号化シンボルであると定義すると、
を満たす場合、提案されたパケット化アルゴリズムが既存のパケット化アルゴリズムよりさらに優れた性能を有すると判断することができる。
【０１００】
パケット化アルゴリズム適用による性能分析のために、ＴＥＳselが伝送過程で損失された場合と正常に受信端で利用可能な場合のような２つの状況が考えられる。まず、ＴＥＳselが伝送過程で損失された場合は、前述のように、ツリー上で
に属する符号化シンボルとｒｏｏｔ間の連結が切れるようになり、結局、
に属する符号化シンボルがｒｏｏｔの復号化に何ら寄与することができない。次は、ＴＥＳselが正常に受信端で受信された場合である。この場合、パケット損失がランダムに発生すると仮定すれば、下記の数式２のように、
と
を計算することができる。
【０１０１】
【数２】
【０１０２】
ここで、ｎsymは、生成された符号化シンボルの数、ｎpktは、伝送されるパケット数（すなわち、
より小さくない最小の整数）、αは、パケット化されず、残った符号化シンボルをパケットの残った空きスペースに挿入する過程で目標パケットに含まれている
に属する平均符号化シンボルの数を意味する。また、ＰＬＲは、パケット損失率を意味する。
【０１０３】
これに基づいて
を常に保障するために、Ｒthrは、下記の数式３を満さなければならない。
【０１０４】
【数３】
【０１０５】
数式２と数式３によって下記数式４が導かれる。
【０１０６】
【数４】
【０１０７】
一般的に、ＬＴ符号化シンボルの次数確率分布は、｛Ω１・・・・・Ωｋ｝で示し、ここで、ｋは、ソースシンボルの数、Ωｉは、符号化シンボルが次数ｉをもつ確率を意味する。ＬＴコードの次数確率分布を下記数式５の生成多項式で表すと、
【０１０８】
【数５】
【０１０９】
符号化シンボルの平均次数をΩ′(1)で示すことができる。したがって、
と
を下記数式６のように示すことができる。
【０１１０】
【数６】
【０１１１】
ここで、γは、ＬＴ符号化オーバーヘッドの割合（すなわち、
）を意味する。最終的に、本発明は、提案されたパケット化アルゴリズムが既存のパケット化アルゴリズムよりさらに優れた性能を有することを証明するためのＲthrの条件を下記数式７のように誘導することができる。
【０１１２】
【数７】
【０１１３】
図５及び図６は、本発明の一実施形態による提案されたパケット化アルゴリズムの制御変数Ｒthrの条件をテストしたグラフである。
【０１１４】
図５は、ｋ＝１０００であり、ｓpacket＝１０である場合、Ｒthrの下限（Ｌｏｗｅｒ Ｌｉｍｉｔ）を示すグラフである。
【０１１５】
図６は、ｋ＝２０００であり、ｓpacket＝１０である場合、Ｒthrの下限を示すグラフである。
【０１１６】
図５及び図６を参照すれば、数式７のｋとｓpacketが固定された場合、γが増加することが分かる。図４から分かるように、γの範囲でＲthrの下限が常に１より小さい。図３の段階３で述べたように、
Ｒthrは、１と
間の整数である。
【０１１７】
本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化アルゴリズムが広い範囲のγにおいて既存のパケット化アルゴリズムより高いＬＴデコード成功率を有することを示す。
【０１１８】
図７〜図１０及び表２は、パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【０１１９】
下記の表２は、ｋ＝１０００、γ＝１．２６である場合、
Ｒthrと
の関係を示すものである。
【０１２０】
【表２】
【０１２１】
ここで、目標パケットで
の元素の数を比較する。実験結果は、表２と図７〜図１０で示す。
【０１２２】
上記表２から分かるように、本発明の一実施形態によるパケット化アルゴリズムがＲthrの値に関係なく、既存のパケット化アルゴリズムより
の値が大きい。さらに、
の平均値は、Ｒthrが増加するほど大きくなる（例えば、既存のパケット化アルゴリズムに比べて、
の多くの元素がＴＥＳselと共にパケット化される）。
の標準偏差値も同一の現象を示す。
【０１２３】
増加された標準偏差は、デコード成功率がルートによって異なることができることを意味する。この差は、ツリー間の従属性によって起きる。事実上、標準偏差が相対的に小さくて、すべてのシンボルにおいて同一のデコード成功率を保障することは必要である。標準偏差を果たせる範囲に維持すると同時に、
の平均値を最大化するために、Ｒthrは、調節されなければならない。
【０１２４】
図７〜図１０は、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムとを比較し、ＴＥＳselと共にパケット化された
の数の差を示すグラフである。
【０１２５】
図７〜図１０のグラフは、ｓpacketが１０で、Ｒthrが５に固定された場合を仮定した。
【０１２６】
図７は、ｋ＝１０００及びγ＝１．２６の場合、本発明の一実施形態によるパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１２７】
図８は、ｋ＝１０００及びγ＝１．２６の場合、既存のパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１２８】
図９は、ｋ＝２０００及びγ＝１．２０の場合、本発明の一実施形態によるパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１２９】
図１０は、ｋ＝２０００及びγ＝１．２０の場合、既存のパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１３０】
図８及び図１０から分かるように、ＴＥＳselと共にパケット化された
の数が均一に分布している。
【０１３１】
また、図７及び図９から分かるように、Ａｎｄ−Ｏｒツリー間の従属性が考慮されていないため、提案されたパケット化アルゴリズムが進んでいる間に、ＴＥＳselと共にパケット化された
の数は減少するにもかかわらず、既存のパケット化アルゴリズムより好ましい性能を示す。
【０１３２】
無線ネットワークでパケット損失パターンは、任意的と言うよりも、集中的な形態を示す。実際的な無線環境で、提案されたパケット化性能を比較するために、２つの状態を有するマルコフチャンネルモデルが適用される。状態遷移確率は、ｐ（パケット損失がない状態からパケット損失がある状態に遷移する確率）とｑ（パケット損失がある状態からパケット損失がない状態に遷移する確率）を含む。
【０１３３】
様々な無線ネットワークを考慮するために、本発明は、下記の表３で示された３つの確率分布をテストする。
【０１３４】
【表３】
【０１３５】
ケース１とケース２では、大きいパケット損失率及び集中したパケット損失長さ（Ｂｕｒｓｔ Ｐａｃｋｅｔ Ｌｏｓｓ Ｌｅｎｇｔｈ）が非常に頻繁に発生するので、成功的なＬＴデコードのためのγは、パケット損失パターンが不規則な場合より増加する。
【０１３６】
ケース３で要求されるγは、相対的にパケット損失パターンが不規則な場合と近似の値を有する。
【０１３７】
図１１〜図１４は、パケット損失パターンが集中している場合、ケース１の遷移確率分布（Ｔｒａｎｓｉｔｉｏｎ Ｐｒｏｂａｂｉｌｉｔｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ）を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【０１３８】
一般的にパケット損失（Ｐａｃｋｅｔ ｌｏｓｓ）が発生する過程で、ファウンテンコードは、受信側で符号化シンボルをより多く受けるほど復号化成功率も高くなる。したがって、グラフを見れば、オーバーヘッド比率（ｏｖｅｒｈｅａｄ ｒａｔｉｏ）が増加するほど、受信側で受けられる符号化シンボルの数が上昇し、結果、平均ＬＴデコード失敗率（ａｖｅｒａｇｅ ＬＴ ｄｅｃｏｄｉｎｇ ｆａｉｌｕｒｅｒａｔｅ）が０に収斂される傾向が見られる（つまり、すべてのソースシンボルが復号化される方向に収斂するようにする）。
【０１３９】
ソースシンボルの復元失敗率が低くなるほど、映像のＰＳＮＲは上昇できる。この時、提案されたパケット化技法と既存のパケット化技法を適用した時、性能を比較すると、提案されたパケット化を適用した場合、さらに優れた復号化性能とＰＳＮＲ値を提供することが分かる。
【０１４０】
図１１及び図１２は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｈａｒｂｏｕｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１４１】
図１１を参照すれば、平均ＬＴデコード失敗率において既存のパケット化アルゴリズムより本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合２倍程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムとの差が少なくなり、デコード失敗率が０に近い値に収斂される。
【０１４２】
図１２を参照すれば、平均ＰＳＮＲにおいて本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約２ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１４３】
図１３及び図１４は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｓｏｃｃｅｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１４４】
図１３を参照すれば、平均ＬＴデコード失敗率における本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより０．０１程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１４５】
図１４を参照すれば、平均ＰＳＮＲにおける本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約２ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１４６】
図１５〜図１８は、パケット損失パターンが集中されている場合、ケース２の遷移確率分布（Ｔｒａｎｓｉｔｉｏｎ Ｐｒｏｂａｂｉｌｉｔｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ）を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【０１４７】
図１５及び図１６は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｈａｒｂｏｕｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１４８】
図１５を参照すれば、平均ＬＴデコード失敗率における本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより２倍程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１４９】
図１６を参照すれば、平均ＰＳＮＲにおける本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約５ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１５０】
図１７及び図１８は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｓｏｃｃｅｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１５１】
図１７を参照すれば、平均ＬＴデコード失敗率における本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより０．０２程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１５２】
図１８を参照すれば、平均ＰＳＮＲにおける本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約３ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１５３】
図１９〜図２２は、パケット損失パターンが集中している場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【０１５４】
図１９及び図２０は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｈａｒｂｏｕｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１５５】
図１９を参照すれば、平均ＬＴデコード失敗率において本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより２倍程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１５６】
図２０を参照すれば、平均ＰＳＮＲにおいて本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約４ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１５７】
図２１及び図２２は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｓｏｃｃｅｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１５８】
図２１を参照すれば、平均ＬＴデコード失敗率において本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより０．０１程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１５９】
図２２を参照すれば、平均ＰＳＮＲにおいて本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約３ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１６０】
図２３は、本発明の一実施形態による符号化シンボルをパケット化して伝送する装置を示す概念図である。
【０１６１】
図２３を参照すれば、符号化シンボルパケット化伝送装置は、ツリー構造化部２３００と、パケット化部２３１０と、伝送部２３２０とを含む。
【０１６２】
ツリー構造化部２３００は、ソースシンボルに基づいてＡｎｄ−Ｏｒツリーを用いてツリー構造を生成することができる。
【０１６３】
Ａｎｄ−Ｏｒツリーは、符号化シンボル間の関係分析のための有用なツールであって、一般的に２ｌの深さを有するＡｎｄ−ＯｒツリーＴｌが存在する時、ルートノードの深さは、０を有し、ルートノードに直接連結された子ノードの深さは、１を有する。また、ツリーの下方に行くほどノードの深さが１ずつ増加するようになる。すべてのノードは、０または１の値を有する。また、深さ０、２、４、…、２ｌ−２に位置するノードは、Ｏｒ−ノードと言い、Ｏｒノードは、子ノードのＯｒ−演算を通じて値が決定される。１、３、５、…、２ｌ−１に位置するノードをＡｎｄ−ノードと言い、子ノードのＡｎｄ−演算を通じて値が決定される。このツリーにＬＴコードのシンボルをマッピングさせれば、ソースシンボルはＯｒ−ノードとして見なされ、符号化シンボルはＡｎｄ−ノードとして見なされ、各々は互いに親と子ノードで結ばれるようになる。
【０１６４】
前述の図２に開示された本発明の一実施形態によるツリー構造を活用してソースシンボルを基礎にパケット化するためのツリー構造を生成することができる。
【０１６５】
本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法では、説明の便宜上、Ａｎｄ−Ｏｒツリーの分析深さを３に制限して説明するが、Ａｎｄ−Ｏｒツリーは、３以上の深さを有することもでき、このようなＬＴ符号化シンボルパケット化方法も本発明の権利範囲に属する。
【０１６６】
パケット化部２３１０は、ツリー構造化部２３００から提供されたツリー構造情報を基礎にして符号化シンボルをパケット化することができる。ＴＥＳｉが属するパケットに一緒に挿入される
に属する符号化シンボルの数を調節することによって、このようなＡｎｄ−Ｏｒツリー間の依存性を間接的に考慮してパケット化することができる。
【０１６７】
伝送部２３２０は、パケット化部で生成されたパケットを、通信チャンネルを利用して伝送することができる。
【０１６８】
ビデオストリーミングは、ディレイ制約があり、無線ネットワークは、制限されたリソースなので、実際に、エラーのない成功的なデコードを保証することは難しい。このような問題を解決するために、エラーが発生しやすい無線ネットワークを通じて十分な数の符号化シンボルを伝送することができるかどうかが予想できることは重要である。
【０１６９】
したがって、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたパケット化方法を用いる場合、特にパケット化を利用してビデオコーデックにより圧縮された形態であるビデオデータを伝送する方法において効果的に活用されることができる。
【０１７０】
以上、実施形態を参照して説明したが、当該技術分野の熟練した当業者は、下記の特許請求の範囲に記載された本発明の思想及び領域を逸脱しない範囲内で本発明を多様に修正及び変更できることは理解できることである。
【技術分野】
【０００１】
本発明は、符号化シンボルのパケット化方法及びその方法を用いる装置に関し、より詳細には、シンボルをパケット化する方法及びその方法を用いる装置に関する。
【背景技術】
【０００２】
ネットワーク及びビデオコーディングを研究する分野においてビデオストリーミング技術は、重要に取り扱われている分野である。ビデオは、多量のデータを有しているだけでなく、データのＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）要求に起因して、実際ネットワーク環境でビデオストリーミングトラフィックを伝送することは難しい。
【０００３】
このようなビデオストリーミングにおいてビデオデータの量を減らすために効果的なビデオ圧縮アルゴリズムを用いることが必須である。
【０００４】
今まで効果的なビデオ圧縮アルゴリズムのためのデジタルビデオコーディング技術は、急速に発展した。ＭＰＥＧ−１、２、４、とＨ．２６１、Ｈ．２６３／＋／＋＋及びＨ．２６４のような国際的標準は、ＩＳＯ／ＩＥＣとＩＴＵ−Ｔの多様な要求事項を満足させるために提案されてきた。圧縮されたビデオデータは、エントロピーコーダーの特性とビデオの場面変換／不規則な動き変化に起因して、多様なビットレートを有する。高い圧縮率で圧縮されたビデオデータは、低い圧縮率で圧縮されたビデオデータより相対的に伝送エラーと損失に弱い。
【０００５】
無線ネットワークで高い品質の安定的なビデオストリーミングサービスを効果的に提供することは、解決すべき課題である。
【０００６】
ビデオデータを伝送するに際して、経路損失、フェーディング、マルチパス及び干渉現象は、無線リンクで受信されたビデオデータのＳＮＲ（Ｓｉｇｎａｌ ｔｏ Ｎｏｉｓｅ Ｒａｔｉｏ）で不規則な変化をもたらす。
【０００７】
低いＳＮＲで受信された信号をデコードすることは難しく、その結果として、ＢＥＲ（Ｂｉｔ Ｅｒｒｏｒ Ｒａｔｅ）を増加させる。無線ネットワークでデータ伝送エラーと損失を緩和させるためには、ＡＲＱ（Ａｕｔｏｍａｔｉｃ Ｒｅｐｅａｔｒｅ Ｑｕｅｓｔ）とＦＥＣ（Ｆｏｒｗａｒｄ Ｅｒｒｏｒ Ｃｏｒｒｅｃｔｉｏｎ）が広く使用される。
【０００８】
ＡＲＱは、フィードバック情報を受信した後、損失されたデータをさらに伝送しなければならないので、ディレイを増加させる。これによって、ＡＲＱは、ディレイに敏感なビデオストリーミングに適しないエラー防止方法になる。
【０００９】
しかしながら、ＦＥＣは、ネットワークでフィードバック情報が不要であり、データの損失とエラーを補償するための追加データを必要とする。このようなＦＥＣの特徴は、ＡＲＱ方法に比べてディレイに敏感なビデオストリーミングにおいて適している。
【００１０】
ルビー変換、ラプター、オンラインコードのようなファウンテン（Ｆｏｕｎｔａｉｎ）コードは、ブロック基盤のＦＥＣ技術である。このようなファウンテンコードは、高いコーディング効率、低いエンコード／デコード処理時間及び適応性のような特性を有しているので、エラーが発生しやすい無線ネットワークでディレイに敏感なデータを伝送するのに非常に有用である。
【００１１】
ファウンテンコードは、チャンネルコーディングのレートレスコード（Ｒａｔｅｌｅｓｓ ｃｏｄｅ）であって、送信端側で受信端に対する情報が足りないか、または受信端の数が非常に多い場合のように、双方向情報伝送が難しい時にも、単方向伝送だけでエラーなしで完全な受信を可能にするという長所を持つ。
【００１２】
これまでファウンテンコードは、消去チャンネル（Ｅｒａｓｕｒｅ Ｃｈａｎｎｅｌ）において研究されて来ており、その他のチャンネルにおける適用が活発に進んでいる。消去チャンネルは、どんな情報が送信されるかに関係なく、一定の確率でその情報が消去され、何が伝送されたか分からないチャンネルである。このチャンネルは、理論的な仮想チャンネルとして認識されてきたが、最近、インターネットの発展に伴い、消去チャンネルは、インターネットをモデリングすることができるチャンネルとして注目された。
【００１３】
インターネット上で各パケットは、正確に伝送されるか、どんなパケットが伝送されるかは関係なく、一定の確率で正確に受信、または消去される場合だけが適用されるので、インターネットチャンネルの環境は、消去チャンネルとしてモデリングされる。
【００１４】
ファウンテンコードは、様々な分野において標準化に対する論議がなされている。現在までは、２００５年ラプターコード（Ｒａｐｔｏｒ Ｃｏｄｅ）が３ＧＰＰ ＴＳ ２６．３４６ ＭＢＭＳとＤＶＢ−Ｈ ＩＰ Ｄａｔａｃａｓｔで使用される標準放送用チャンネル符号化アルゴリズムとして採択された。標準で使用されているラプターコードは、システマチック（Ｓｙｓｔｅｍａｔｉｃ）な特性をもつように定義された。３ＧＰＰ ＭＢＭＳとＤＶＢ−Ｈでは、このような特性のラプターコードを実現するために、プレコード（Ｐｒｅ−Ｃｏｄｅ）過程でＬＴデコードを用いる。すなわち、既存のソースシンボルをラプターコード内のＬＴコード部分のようなソースシンボル選択パターンで符号化されたシンボルとして仮定する。したがって、これをＬＴデコードして得た中間段階シンボルをＬＴ エンコードすれば、伝送すべきエンコードシンボル内には、ソースシンボルがそのまま含まれる。
【００１５】
ファウンテンコードは、基本的に消去チャンネルで動作するように設計されるので、有線ネットワーク上での通信においても適しているが、無線通信でもＭＡＣレイヤー（Ｌａｙｅｒ）上では、ＣＲＣが適用され、受信されたパケットが正しい情報であるか否かだけが決定されるので、消去チャンネルのような場合と見なしてファウンテンコードを適用することができる。ＭＡＣレイヤーで使用される他のコーディング技法であるＨ−ＡＲＱと比較してみると、ファウンテンコードは、送信端と受信端との間の相互作用がなくても、受信端でエラーなしに正確に情報を受信することができるという特徴がある。したがって、両端の間で情報を正確に受信するまで繰り返し相互作用によって通信するＨ−ＡＲＱ伝送技法に比べて長所を有する。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
安定的にＱｏＳを満足させるビデオストリーミングサービスを行うためには、無線ネットワークで発生するパケット損失により発生するデータの損失を最小化するために、伝達されるパケット間の従属性を減少させて、パケット損失を最小化しなければならない。また、エラーが発生しやすい無線ネットワークで十分な数の符号化シンボルを伝送することができるか否かを予想し、同じ数のパケットでＬＴデコード失敗率を低減しなければならない。
【００１７】
したがって、本発明の第１目的は、パケット損失を最小化するためのＡｎｄ−Ｏｒツリーを用いた符号化シンボルをパケット化する方法を提供することにある。
【００１８】
また、本発明の第２目的は、パケット損失を最小化するためのＡｎｄ−Ｏｒツリーを用いた符号化シンボルをパケット化する方法を用いる装置を提供することにある。
【課題を解決するための手段】
【００１９】
上記目的を達成するために、本発明の一態様による符号化シンボルのパケット化方法は、第１ソースシンボルを決定し、ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルと前記パケット化していない第１符号化シンボルを挿入する目標パケットを選択する符号化シンボル及び目標パケット選択段階と、前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づいて少なくとも１つの第２符号化シンボルを生成し、前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化するパケット化段階とを含む。前記符号化シンボルは、ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を利用して符号化したシンボルであってもよい。符号化シンボルのパケット化方法は、前記符号化シンボル及び目標パケット選択段階と前記パケット化段階でパケット化していない第１符号化シンボルが存在しない場合、前記第１ソースシンボルではなく、前記第１ソースシンボルと同じＡＮＤ−ＯＲツリー階層にあるソースシンボルを第１ソースシンボルとして前記符号化シンボル及び目標パケット選択段階とパケット化段階を進行することができる。
【００２０】
符号化シンボルのパケット化方法は、前記符号化シンボル及び目標パケット選択段階と前記パケット化段階でパケット化していない第１符号化シンボルが存在せず、前記他のソースシンボルを第１ソースシンボルとして選択することができない場合、まだパケット化していない第２符号化シンボルのうち少なくとも１つを前記目標パケットの残ったスペースに挿入することができる。前記パケット化段階で、前記第１符号化シンボルと共にパケット化される前記第２符号化シンボルが下記の数式１を満たせる値として決定される。
【００２１】
【数１】
【００２２】
前記符号化シンボル及び目標パケット選択段階で、前記目標パケットは、空きパケットが存在する場合には、前記空きパケットのうち少なくとも１つを目標パケットとし、
空きパケットが存在しない場合には、所定のパケットの使用可能なスペースがＲthr＋１より大きいければ、前記所定のパケットの使用可能なスペースがＲthr＋１より大きいパケットの１つを目標パケットとして決定し、前記所定のパケットの使用可能なスペースが前記Ｒthr＋１より大きくなければ、前記Ｒthr＋１が
（
は、第１符号化シンボルの次数を意味する。）より大きいか等しく、かつ、前記所定のパケットの使用可能なスペースが
より大きいか等しい場合に、前記所定のパケットのうち少なくとも１つとして選択される。
【００２３】
前記ＡＮＤ−ＯＲツリーは、前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が第１ソースシンボルの値として決定され、前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が第１符号化シンボルの値として決定され、前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が第２ソースシンボルの値として算出されることができる。前記符号化シンボルのパケット化方法は、ビデオストリーミングサービスでビデオデータを伝送するのに使用されてもよい。
【００２４】
また、本発明の他の態様による符号化シンボルのパケット化装置は、符号化対象であるソースシンボルに基づいてＡＮＤ−ＯＲツリーを用いて符号化シンボルを生成し、前記符号化シンボルに基づいて前記ＡＮＤ−ＯＲツリーを用いてソースシンボルを生成するツリー構造化部と、前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部とを含んでもよい。前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、第１ソースシンボルを決定し、前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルと前記パケット化していない第１符号化シンボルを挿入する目標パケットを選択し、前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づく少なくとも１つの第２符号化シンボルを生成し、前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化することができる。
【００２５】
前記ＡＮＤ−ＯＲツリーは、前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が第１ソースシンボルの値として決定される。また、前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が第１符号化シンボルの値として決定される。そして、前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が第２ソースシンボルの値として算出される。前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、パケット化していない第１符号化シンボルが存在しない場合には、前記第１ソースシンボルを除いた他の第１ソースシンボルを選択する。前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記他の第１ソースシンボルの符号化シンボルである第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合には、前記パケット化していない第１符号化シンボルを選択する。そして、前記パケット化していない第１符号化シンボルを挿入する目標パケットを決定して、前記第１符号化シンボルを前記目標パケットに挿入する。また、前記ＡＮＤ−ＯＲツリー構造を利用して、生成された前記第１符号化シンボルに基づく第２ソースシンボルを生成した後、前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づいて第２符号化シンボルを生成する。また、前記第２符号化シンボルを前記目標パケットに前記第１符号化シンボルと共にパケット化する。前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、パケット化していない第１符号化シンボルが存在せず、前記第１ソースシンボルを除いた他の第１ソースシンボルを選択することができない場合には、まだパケット化していない第２符号化シンボルのうち少なくとも１つを前記目標パケットの残ったスペースに挿入してもよい。前記符号化シンボルは、ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を利用して符号化したシンボルであってもよい。符号化シンボルのパケット化装置は、ビデオストリーミングサービスにおいて、ビデオデータを伝送するのに使用されることができる。
【発明の効果】
【００２６】
本発明の実施形態による符号化シンボルのパケット化方法及びこのような方法を用いる装置によれば、無線ネットワークにおいて、ビデオストリーミングサービスを助けるために、Ａｎｄ−Ｏｒツリーに基づく符号化シンボルのパケット化を行う。まず、エンコードされたシンボル間の関係は、Ａｎｄ−Ｏｒツリーを用いることによって分析される。分析された結果に基づいてエンコードされたシンボルは、パケット間に相関を減少させる方法を用いて、データ伝送の間に損失されたパケットの効果は地域的に限定される。
【００２７】
したがって、無線ネットワークで発生するパケット損失を最小化することができ、特に、ビデオストリーミングサービスの品質低下を最小化し、伝達するパケット間の従属性を減少させて、安定的にＱｏＳを満足させるビデオストリーミングサービスを提供することができる。
【図面の簡単な説明】
【００２８】
【図１】エラーが発生しやすい無線ネットワークでビデオストリーミングシステムを示す。
【図２】本発明の一実施形態によるＬＴ符号化シンボル間に繰り返し的な符号化過程を示すツリー構造である。
【図３】本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示す概念図である。
【図４】本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示すフローチャートである。
【図５】本発明の一実施形態による提案されたパケット化アルゴリズムの制御変数Ｒｔｈｒの条件をテストしたグラフである。
【図６】本発明の一実施形態による提案されたパケット化アルゴリズムの制御変数Ｒｔｈｒの条件をテストしたグラフである。
【図７】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図８】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図９】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図１０】パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【図１１】パケット損失パターンが集中されている場合、ケース１の遷移確率分布（Ｔｒａｎｓｉｔｉｏｎ Ｐｒｏｂａｂｉｌｉｔｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ）を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１２】パケット損失パターンが集中されている場合、ケース１の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１３】パケット損失パターンが集中されている場合、ケース１の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１４】パケット損失パターンが集中されている場合、ケース１の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１５】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１６】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１７】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１８】パケット損失パターンが集中されている場合、ケース２の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図１９】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２０】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２１】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２２】パケット損失パターンが集中されている場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【図２３】本発明の一実施形態による符号化シンボルをパケット化して伝送する装置を示す概念図である。
【発明を実施するための形態】
【００２９】
本発明は、多様な変更を加えることができ、様々な実施形態を有することができるため、その実施形態を図面に例示して詳細に説明する。これは、本発明を特定の実施形態に限定しようとするものではなく、本発明の思想及び技術範囲に含まれるすべての変更、均等物及び代替物を含むものと理解すべきである。なお、各図面を説明するに際して、同一の参照符号を同一の構成要素に用いる。
【００３０】
第１、第２などの用語は、多様な構成要素を説明するのに使用されることができるが、前記構成要素は、前記用語に限定されるわけではない。前記用語は、１つの構成要素を他の構成要素から区別する目的のみに使用される。例えば、本発明の権利範囲を逸脱しない範囲内で、第１構成要素は、第２構成要素として称することができ、同様に、第２構成要素も第１構成要素として称することができる。「及び／または」という用語は、複数の関連された記載項目の組み合わせまたは複数の関連された記載項目のうちいずれかの項目を含む。
【００３１】
任意の構成要素が他の構成要素に「連結されて」いるか、「接続されて」いると記述されたときには、他の構成要素に直接的に連結されているか、または接続されていることもあるが、間に他の構成要素が存在することも有り得ると理解すべきである。一方、任意の構成要素が他の構成要素に「直接連結されている」や、「直接接続されている」と記述されたときには、間に他の構成要素が存在しないものと理解すべきである。
【００３２】
本出願において用いた用語は、単に特定の実施形態を説明するために使用されたものであって、本発明を限定しようとする意図ではない。単数の表現は、文脈上、明白に異なったことを意味しない限り、複数の表現を含む。本出願において、「含む」または「有する」などの用語は、記述された特徴、数字、段階、動作、構成要素、部分品またはこれらを組み合わせたものが存在することを指すものであって、１つまたはそれ以上の他の特徴や、数字、段階、動作、構成要素、部分、またはこれらを組み合わせたものなどの存在または付加可能性をあらかじめ排除しないものと理解すべきである。
【００３３】
以下、添付の図面を参照して、本発明の好ましい実施形態をさらに詳細に説明する。以下、図面において、同一の構成要素については、同一の参照符号を使用し、同一の構成要素について重複説明は省略する。
【００３４】
以下、本発明の一実施形態による符号化シンボルのパケット化方法及びこのような方法を用いる装置では、ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を利用した符号化シンボルをパケット化する方法及びこのような方法を用いる装置について開示する。しかし、本発明の本質を逸脱しない範囲内で、ルビー変換コードだけでなく、他のコードにも本発明で開示された方法を適用することができ、これも、また本発明の権利範囲に属する。
【００３５】
以下、本発明の実施形態において用いるＬＴは、ルビー変換を意味し、以下の本発明の実施形態において同一の意味として使用されることができる。
【００３６】
図１は、エラーが発生しやすい無線ネットワークにおいてのビデオストリーミングシステムを示す。
【００３７】
図１を参照すれば、ビデオデータは、データの量を減少させるために、ビデオコーデックによって圧縮された形態で生成される。ビデオデータは、無線ネットワークで強靭な伝送のためにルビー変換を用いてエンコードされる。ＬＴエンコードプロセスを進行する間に、圧縮されたビデオデータストリームは、ソースブロックに分けられる。
【００３８】
ソースブロックは、あらかじめ定められたサイズのソースシンボルに分割される。ＬＴ符号化シンボルは、ソースシンボルの一部とマッピングされる。ＬＴ符号化シンボルは、ソースシンボルのＸＯＲ演算を行うことによって生成される。
【００３９】
このようなＬＴ符号化シンボルを生成するプロセスは、最後のＬＴ符号化シンボルが生成されるまで繰り返される。ソースシンボルとＬＴ符号化シンボルのマッピング手順は、生成多項式（Ｇｅｎｅｒａｔｏｒ Ｐｏｌｙｎｏｍｉａｌ）により制御できる。多くの無線ネットワークは、パケット交換方式を用いるので、ＬＴ符号化シンボルは、伝送前にパケット化されなければならない。
【００４０】
伝送途中に発生するパケット損失は、エラーが発生しやすい無線ネットワークで不可避な現象である。パケットが損失された場合、受信されたＬＴ符号化シンボルの数は、成功的なデコードのためには十分でないこともある。
【００４１】
仮に受信端が成功的なＬＴデコードのための十分なＬＴ符号化シンボルを得るまで持続的に多数のパケットが伝送できれば、エラーが発生しやすい無線ネットワークでは、エラーのないデコードが保証される。
【００４２】
しかしながら、ビデオストリーミングはディレイ制約があり、無線ネットワークは制限されたリソースなので、実際に、エラーのない成功的なデコードを保証することは難しい。このような問題を解決するために、エラーが発生しやすい無線ネットワークを介して十分な数の符号化シンボルを伝送することができるかを予想できることは重要である。
【００４３】
他に重要な問題としては、同じ数のパケットでどれほどＬＴデコード失敗率を低減できるかに関する。繰り返し的なデコードプロセスに存在する符号化シンボル間の従属性に起因して、ＬＴデコード性能は、符号化シンボルをどれほどパケット化するかによって変わる。それで、符号化シンボル間の従属性が考慮されていない場合、デコード性能は、著しく劣化される。例えば、ＬＴ符号化シンボルが不規則にパケットにグループ化される場合、損失されたパケットは、多くのソースシンボルが成功的にデコードされることを阻害することがある。
【００４４】
一般的にビデオストリーミングデータは、データの量を減らすために、高い圧縮率での圧縮を行うので、相対的にデータ損失にさらに脆弱である。それで、損失されたデータの小さい量は、重大なビデオ品質の低下を発生させることになる。
【００４５】
本発明の一実施形態によれば、データ損失を減らすために、ＬＴ符号化シンボルの間では、Ａｎｄ−Ｏｒツリーを用いる。このような分析に基づいて提案されたパケット化アルゴリズムは、各々のパケットでエンコードされたシンボル間に相関（Ｃｏｒｒｅｌａｔｉｏｎ）を増加させ、パケット間の相関を減少させる方向に設計される。
【００４６】
図２は、本発明の一実施形態によるＬＴ符号化シンボル間での繰り返し符号化する過程を示すツリー構造である。
【００４７】
図２を参照すれば、シンボル間の関係を誘導するための簡単なＡｎｄ−Ｏｒツリーが示されている。
【００４８】
Ａｎｄ−Ｏｒツリーは、符号化シンボル間の関係分析のための有用なツールであって、一般的に２ｌの深さを有するＡｎｄ−ＯｒツリーＴｌが存在する時、ルートノードの深さは、０を有し、ルートノードに直接連結された子ノードの深さは、１を有する。また、ツリーの下方に行きほど、ノードの深さは１ずつ増加するようになる。すべてのノードは、０または１の値を有する。また、深さ０、２、４、…、２ｌ−２に位置するノードは、Ｏｒ−ノードと言い、Ｏｒノードは、子ノードのＯｒ−演算を通じて値が決定される。１，３、５、…、２ｌ−２に位置するノードをＡｎｄ−ノードと言い、子ノードのＡｎｄ−演算を通じて値が決定される。このツリーにＬＴコードのシンボルをマッピングさせれば、ソースシンボルは、Ｏｒ−ノードとして、符号化シンボルは、Ａｎｄ−ノードとして見なされ、各々は、互いに親と子ノードで結ばれるようになる。
【００４９】
下記の表１は、本発明の一実施形態によるＡｎｄ−Ｏｒツリーに使用されるシンボルとシンボルの意味を示すものである。
【００５０】
【表１】
【００５１】
ｒｏｏｔはＯｒ−ノード、ＴＥＳiはＡｎｄ−ノードなので、他の目標符号化シンボルと関係なく、ＴＥＳiによってｒｏｏｔが復号化されるためには、
に属するソースシンボルが先行的にすべて復号化されなければならない。したがって、ＴＥＳiを利用してｒｏｏｔが成功的に復号化されるためには、深さ２に位置する符号化シンボルの影響を受けるようになる。すなわち、ＴＥＳiがｒｏｏｔの成功的な復号化に寄与するためには、
に属するソースシンボルが先行的に復号化されなければならない。
【００５２】
仮に受信端でＴＥＳiとさらに多い
に属する符号化シンボルを同時に受信する場合、
に属するソースシンボルをより多く復号化ができる。これにより、ｒｏｏｔの復号化成功率が高くなる。これは、ＴＥＳiと
に属する符号化シンボルが互いに強い依存性を有していることを意味する。
【００５３】
仮にＴＥＳiが伝送過程で損失されると、ツリー上で
に属する符号化シンボルとｒｏｏｔ間の繋がりが切れることになり、結局、
に属する符号化シンボルがｒｏｏｔの復号化に何ら寄与をすることができない。ＬＴ復号化成功率を高めるためには、このようなシンボル間の関係が考慮されるべきであり、この関係に基づいて下記のような３つの有用な属性を導き出せる。
【００５４】
属性１：ｒｏｏｔの復号化成功率は、
の各々を互いに異なるパケットに挿入することによって向上させることができる。
【００５５】
属性２：
に属する符号化シンボルがより多く利用可能であれば、
に属するソースシンボルの復号化成功率を向上させることができる。
【００５６】
属性３：ｒｏｏｔの復号化成功率は、ＴＥＳiと
に属する符号化シンボルを同じパケットに挿入することによって、向上させることができる。
【００５７】
但し、ｉ≠ｊ ｏｒ ｐ≠ｑであり、
と
とを、各々ソースシンボルｐとｑをｒｏｏｔとする時のＴＥＳiとＴＥＳjとの関連する符号化シンボルの集合であるとする時、
は、空集合ではないこともある。すなわち、一部のＬＴ符号化シンボルは、互いに異なる集合に同時に含まれることもある。
【００５８】
ＴＥＳiが属するパケットに一緒に挿入される
に属する符号化シンボルの数を調節することによって、このようなＡｎｄ−Ｏｒツリー間の依存性を間接的に考慮して、パケット化過程でツリー間の依存度を完全に制御するためには、非常に高い計算的な複雑度を要求する分析が必要である。
【００５９】
以下、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法では、説明の便宜上、Ａｎｄ−Ｏｒツリーの分析深さを３に制限して説明するが、Ａｎｄ−Ｏｒツリーは、３以上の深さを有することができ、このようなＬＴ符号化シンボルパケット化方法も本発明の権利範囲に属する。
【００６０】
以下、本発明の一実施形態によれば、ツリー構造で最も上端に位置するソースシンボルを第１ソースシンボル、第１ソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第１符号化シンボル、第１符号化シンボルをＡｎｄ−Ｏｒツリーを利用して生成したソースシンボルを第２ソースシンボル、第２ソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第２符号化シンボルという用語に定義して用いる。
【００６１】
すなわち、ツリーの深さが増加する場合、一般化してツリー構造で上端に位置するソースシンボルを第ｎソースシンボル、第ｎソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第ｎ符号化シンボル、第ｎ符号化シンボルをＡｎｄ−Ｏｒツリーを利用して生成したソースシンボルを第ｎ＋１ソースシンボル、第ｎ＋１ソースシンボルをＡｎｄ−Ｏｒツリーを利用して生成した符号化シンボルを第ｎ＋１符号化シンボルという用語に定義して用いる。
【００６２】
図３は、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示す概念図である。
【００６３】
以下、本発明の実施形態では、ツリーの深さを３に限定して説明するが、これは、説明の便宜のためのものであって、本発明の本質を逸脱しない範囲内でツリーの深さは３を超える値になることもあり、このようなツリー構造を利用したパケット化方法も本発明の権利範囲に含まれる。
【００６４】
図３を参照すれば、ＴＥＳselを
のうちｒｏｏｔの復号化に寄与するために選択された目標符号化シンボルであるとすれば、前述した属性に基づいて本発明の一実施形態によるパケット化アルゴリズムは、
とＴＥＳselに属する、より多い符号化シンボルを同じパケットに挿入するように設計されなければならない。
を、ＴＥＳselと同じパケットに挿入される
に属する符号化シンボルであると定義することができる。ＴＥＳselが挿入されるパケットが目標パケットであるとすれば、
に属する符号化シンボルのうちいくつかの符号化シンボルが目標パケットにＴＥＳselと共に挿入されるべきかは、提案するパケット化アルゴリズムの制御変数Ｒthrによって決定される。 仮にＲthrが０の場合、提案するパケット化アルゴリズムは、既存のパケット化アルゴリズムと同一の動作を行う。提案するパケット化アルゴリズムの動作は、以下の段階を経て動作する。
【００６５】
段階０：ｒｏｏｔを決定する。
【００６６】
段階１：ｒｏｏｔの
において
であり、パケット化していないＴＥＳselを選択する。
（すべての
が既にパケット化されたら段階４を行う。）
【００６７】
段階２：ＴＥＳselを次のような規則により選択された目標パケットに挿入する（規則ｉは、規則（ｉ＋１）より優先順位が高い）。例えば、規則によって選択できる目標パケットがそれ以上存在しない場合は、段階４を行う。
【００６８】
規則１：仮に空きパケットが存在すれば、当該パケットを目標パケットとして決定する。
【００６９】
規則２：仮にパケットの使用可能なスペースがＲthr＋１より大きければ、当該パケットを目標パケットとして決定する。
【００７０】
規則３：仮にＲthrが
より大きいか等しく、パケットの使用可能なスペースが
より大きいか同一の場合、当該パケットを目標パケットとして決定する。
【００７１】
規則３は、パケットの残ったスペースを活用するためのものである。規則１、２の過程を経ると、パケットに実際のＲthr＋１より小さいスペースが残っていることもある。この場合、Ｒthr＋１の規則だけに従う場合、残ったスペースを活用することができない。
【００７２】
例えば、パケットに１０個の符号化シンボルが入れるとして、Ｒthrを５とすると、規則２に従う場合、パケットに６個のシンボル
が挿入される。すると、このパケットに４個の符号化シンボルが入ることのできるスペースが残るようになり、このパケットは、規則１と２を満たすことができない。この場合、規則３によって
を満たせる最小スペースが存在すれば、
個の
に属する符号化シンボルを挿入することができる。
【００７３】
段階３：
に属する符号化シンボルのうち、Ｒthr個を任意に選択して
を決定する（但し、
を集合Ａの大きさ（cardinality）とする時、
を満たす。）。そして、
を図３に示すように、目標パケットに挿入する。
【００７４】
すなわち、符号化対象である第１ソースシンボルを決定し、Ａｎｄ−Ｏｒツリー構造を利用して生成した第１ソースシンボルの符号化シンボルである第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、パケット化していない第１符号化シンボルを選択して、パケット化していない第１符号化シンボルを挿入する目標パケットを決定する。また、第１符号化シンボルを前記目標パケットに挿入する。Ａｎｄ−Ｏｒツリー構造を利用して、生成された前記第１符号化シンボルに基づく第２ソースシンボルを生成した後、Ａｎｄ−Ｏｒツリー構造を利用して第２ソースシンボルに基づいて第２符号化シンボルを生成する。前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化できる。
【００７５】
ツリーの深さが３以上の場合において、符号化対象である第ｎソースシンボルを決定し、Ａｎｄ−Ｏｒツリー構造を利用して生成した前記第ｎソースシンボルの符号化シンボルである第ｎ符号化シンボルのうちパケット化していない第ｎ符号化シンボルが存在する場合には前記パケット化していない第ｎ符号化シンボルを選択し、前記パケット化していない第ｎ符号化シンボルを挿入する目標パケットを決定して、前記第ｎ符号化シンボルを前記目標パケットに挿入することができる。また、Ａｎｄ−Ｏｒツリー構造を利用して、生成された第ｎ符号化シンボルに基づく第ｎ＋１ソースシンボルを生成した後、Ａｎｄ−Ｏｒツリー構造を利用して第ｎ＋１ソースシンボルに基づいて第ｎ＋１符号化シンボルを生成し、第ｎ＋１符号化シンボルのうち少なくとも１つを前記目標パケットに前記第ｎ符号化シンボルと共にパケット化することができる。
【００７６】
段階４：仮にこれ以上ｒｏｏｔを選択することができない場合は、段階５を行う。そうではない場合は、他のｒｏｏｔを選択して、段階１〜３を繰り返す。
【００７７】
段階５：残りのパケット化していない符号化シンボルをパケットの空きスペースに挿入する。
【００７８】
図４は、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法を示すフローチャートである。
【００７９】
図４を参照すれば、ｒｏｏｔを決定することができる（段階Ｓ４００）。
【００８０】
パケット化のためには、パケット化を行うｒｏｏｔを優先的に決定しなければならない。
【００８１】
パケット化していないＴＥＳselが存在するか否かを判断することができる（段階Ｓ４１０）。
【００８２】
パケット化していないＴＥＳselが存在しない場合、段階Ｓ４６０に進み、他のｒｏｏｔを選択することができるか否かを判断し、他のｒｏｏｔが選択できる場合、ルートを決定する段階Ｓ４００を繰り返す。
【００８３】
他のｒｏｏｔか存在しない場合、残った符号化シンボルをパケットの空きスペースに入れる段階Ｓ４７０を行う。
【００８４】
パケット化していないＴＥＳselが存在する場合、そのパケット化していないＴＥＳsel
を選択することができる（段階Ｓ４２０）。
【００８５】
ｒｏｏｔの
において
で、かつ、パケット化していないＴＥＳselを選択する。
【００８６】
ＴＥＳselを挿入する目標パケットを決定することができる（段階Ｓ４３０）。
【００８７】
ＴＥＳselを目標パケットに挿入するには、下記のような規則を用いて目標パケットを決定することができる。小さい番号の規則が大きい番号の規則より優先して適用される。
【００８８】
規則１：仮に空きパケットが存在すれば、当該パケットを目標パケットとして決定する。
【００８９】
規則２：仮にパケットの使用可能スペースがＲthr＋１より大きければ、当該パケットを目標パケットとして決定する。
【００９０】
規則３：仮にＲthrが
より大きいか等しく、パケットの使用可能なスペースが
より大きいか同一の場合、当該パケットを目標パケットとして決定する。
【００９１】
目標パケットを決定する上記規則は、小さい数字の規則１が最も優先順位が高く、規則３が最も優先順位が低い。すなわち、規則１を満足するパケットが優先的に目標パケットとして選択される。
【００９２】
ＴＥＳselを決定された目標パケットに挿入することができる（段階Ｓ４４０）。
【００９３】
段階Ｓ４３０によって決定された目標パケットにＴＥＳselを挿入する。
【００９４】
を決定し、目標パケットに挿入することができる（段階Ｓ４５０）。
【００９５】
に属する符号化シンボルのうちＲthr個を任意に選択し、
を決定する（但し、
を集合Ａの大きさとする時、
を満たす。）。そして、
を、図３に示すように目標パケットに挿入する。
【００９６】
ｒｏｏｔを選択することができるか否かを判断する（段階Ｓ４６０）。
【００９７】
パケット化が進んでいないｒｏｏｔが存在する場合、当該ｒｏｏｔを選択し、段階Ｓ４００から段階Ｓ４５０を繰り返し行う。
【００９８】
選択できるｒｏｏｔが存在しない場合、残りのパケット化していない符号化シンボルをパケットの残った空きスペースに挿入することができる（段階Ｓ４７０）。
【００９９】
本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化アルゴリズムの性能の尺度は、成功的に受信した
に属する符号化シンボルの数である。
と
を、各々提案されたパケット化アルゴリズムと既存のパケット化アルゴリズムを適用した時、エラーなく成功的に受信端で受信した
に属する符号化シンボルであると定義すると、
を満たす場合、提案されたパケット化アルゴリズムが既存のパケット化アルゴリズムよりさらに優れた性能を有すると判断することができる。
【０１００】
パケット化アルゴリズム適用による性能分析のために、ＴＥＳselが伝送過程で損失された場合と正常に受信端で利用可能な場合のような２つの状況が考えられる。まず、ＴＥＳselが伝送過程で損失された場合は、前述のように、ツリー上で
に属する符号化シンボルとｒｏｏｔ間の連結が切れるようになり、結局、
に属する符号化シンボルがｒｏｏｔの復号化に何ら寄与することができない。次は、ＴＥＳselが正常に受信端で受信された場合である。この場合、パケット損失がランダムに発生すると仮定すれば、下記の数式２のように、
と
を計算することができる。
【０１０１】
【数２】
【０１０２】
ここで、ｎsymは、生成された符号化シンボルの数、ｎpktは、伝送されるパケット数（すなわち、
より小さくない最小の整数）、αは、パケット化されず、残った符号化シンボルをパケットの残った空きスペースに挿入する過程で目標パケットに含まれている
に属する平均符号化シンボルの数を意味する。また、ＰＬＲは、パケット損失率を意味する。
【０１０３】
これに基づいて
を常に保障するために、Ｒthrは、下記の数式３を満さなければならない。
【０１０４】
【数３】
【０１０５】
数式２と数式３によって下記数式４が導かれる。
【０１０６】
【数４】
【０１０７】
一般的に、ＬＴ符号化シンボルの次数確率分布は、｛Ω１・・・・・Ωｋ｝で示し、ここで、ｋは、ソースシンボルの数、Ωｉは、符号化シンボルが次数ｉをもつ確率を意味する。ＬＴコードの次数確率分布を下記数式５の生成多項式で表すと、
【０１０８】
【数５】
【０１０９】
符号化シンボルの平均次数をΩ′(1)で示すことができる。したがって、
と
を下記数式６のように示すことができる。
【０１１０】
【数６】
【０１１１】
ここで、γは、ＬＴ符号化オーバーヘッドの割合（すなわち、
）を意味する。最終的に、本発明は、提案されたパケット化アルゴリズムが既存のパケット化アルゴリズムよりさらに優れた性能を有することを証明するためのＲthrの条件を下記数式７のように誘導することができる。
【０１１２】
【数７】
【０１１３】
図５及び図６は、本発明の一実施形態による提案されたパケット化アルゴリズムの制御変数Ｒthrの条件をテストしたグラフである。
【０１１４】
図５は、ｋ＝１０００であり、ｓpacket＝１０である場合、Ｒthrの下限（Ｌｏｗｅｒ Ｌｉｍｉｔ）を示すグラフである。
【０１１５】
図６は、ｋ＝２０００であり、ｓpacket＝１０である場合、Ｒthrの下限を示すグラフである。
【０１１６】
図５及び図６を参照すれば、数式７のｋとｓpacketが固定された場合、γが増加することが分かる。図４から分かるように、γの範囲でＲthrの下限が常に１より小さい。図３の段階３で述べたように、
Ｒthrは、１と
間の整数である。
【０１１７】
本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化アルゴリズムが広い範囲のγにおいて既存のパケット化アルゴリズムより高いＬＴデコード成功率を有することを示す。
【０１１８】
図７〜図１０及び表２は、パケット損失パターンが不規則な場合、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムをＬＴデコード失敗率の観点で比較したものである。
【０１１９】
下記の表２は、ｋ＝１０００、γ＝１．２６である場合、
Ｒthrと
の関係を示すものである。
【０１２０】
【表２】
【０１２１】
ここで、目標パケットで
の元素の数を比較する。実験結果は、表２と図７〜図１０で示す。
【０１２２】
上記表２から分かるように、本発明の一実施形態によるパケット化アルゴリズムがＲthrの値に関係なく、既存のパケット化アルゴリズムより
の値が大きい。さらに、
の平均値は、Ｒthrが増加するほど大きくなる（例えば、既存のパケット化アルゴリズムに比べて、
の多くの元素がＴＥＳselと共にパケット化される）。
の標準偏差値も同一の現象を示す。
【０１２３】
増加された標準偏差は、デコード成功率がルートによって異なることができることを意味する。この差は、ツリー間の従属性によって起きる。事実上、標準偏差が相対的に小さくて、すべてのシンボルにおいて同一のデコード成功率を保障することは必要である。標準偏差を果たせる範囲に維持すると同時に、
の平均値を最大化するために、Ｒthrは、調節されなければならない。
【０１２４】
図７〜図１０は、本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズムとを比較し、ＴＥＳselと共にパケット化された
の数の差を示すグラフである。
【０１２５】
図７〜図１０のグラフは、ｓpacketが１０で、Ｒthrが５に固定された場合を仮定した。
【０１２６】
図７は、ｋ＝１０００及びγ＝１．２６の場合、本発明の一実施形態によるパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１２７】
図８は、ｋ＝１０００及びγ＝１．２６の場合、既存のパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１２８】
図９は、ｋ＝２０００及びγ＝１．２０の場合、本発明の一実施形態によるパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１２９】
図１０は、ｋ＝２０００及びγ＝１．２０の場合、既存のパケット化アルゴリズムを適用した場合、ＴＥＳselと共にパケット化された
の数を示すグラフである。
【０１３０】
図８及び図１０から分かるように、ＴＥＳselと共にパケット化された
の数が均一に分布している。
【０１３１】
また、図７及び図９から分かるように、Ａｎｄ−Ｏｒツリー間の従属性が考慮されていないため、提案されたパケット化アルゴリズムが進んでいる間に、ＴＥＳselと共にパケット化された
の数は減少するにもかかわらず、既存のパケット化アルゴリズムより好ましい性能を示す。
【０１３２】
無線ネットワークでパケット損失パターンは、任意的と言うよりも、集中的な形態を示す。実際的な無線環境で、提案されたパケット化性能を比較するために、２つの状態を有するマルコフチャンネルモデルが適用される。状態遷移確率は、ｐ（パケット損失がない状態からパケット損失がある状態に遷移する確率）とｑ（パケット損失がある状態からパケット損失がない状態に遷移する確率）を含む。
【０１３３】
様々な無線ネットワークを考慮するために、本発明は、下記の表３で示された３つの確率分布をテストする。
【０１３４】
【表３】
【０１３５】
ケース１とケース２では、大きいパケット損失率及び集中したパケット損失長さ（Ｂｕｒｓｔ Ｐａｃｋｅｔ Ｌｏｓｓ Ｌｅｎｇｔｈ）が非常に頻繁に発生するので、成功的なＬＴデコードのためのγは、パケット損失パターンが不規則な場合より増加する。
【０１３６】
ケース３で要求されるγは、相対的にパケット損失パターンが不規則な場合と近似の値を有する。
【０１３７】
図１１〜図１４は、パケット損失パターンが集中している場合、ケース１の遷移確率分布（Ｔｒａｎｓｉｔｉｏｎ Ｐｒｏｂａｂｉｌｉｔｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ）を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【０１３８】
一般的にパケット損失（Ｐａｃｋｅｔ ｌｏｓｓ）が発生する過程で、ファウンテンコードは、受信側で符号化シンボルをより多く受けるほど復号化成功率も高くなる。したがって、グラフを見れば、オーバーヘッド比率（ｏｖｅｒｈｅａｄ ｒａｔｉｏ）が増加するほど、受信側で受けられる符号化シンボルの数が上昇し、結果、平均ＬＴデコード失敗率（ａｖｅｒａｇｅ ＬＴ ｄｅｃｏｄｉｎｇ ｆａｉｌｕｒｅｒａｔｅ）が０に収斂される傾向が見られる（つまり、すべてのソースシンボルが復号化される方向に収斂するようにする）。
【０１３９】
ソースシンボルの復元失敗率が低くなるほど、映像のＰＳＮＲは上昇できる。この時、提案されたパケット化技法と既存のパケット化技法を適用した時、性能を比較すると、提案されたパケット化を適用した場合、さらに優れた復号化性能とＰＳＮＲ値を提供することが分かる。
【０１４０】
図１１及び図１２は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｈａｒｂｏｕｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１４１】
図１１を参照すれば、平均ＬＴデコード失敗率において既存のパケット化アルゴリズムより本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合２倍程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムとの差が少なくなり、デコード失敗率が０に近い値に収斂される。
【０１４２】
図１２を参照すれば、平均ＰＳＮＲにおいて本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約２ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１４３】
図１３及び図１４は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｓｏｃｃｅｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１４４】
図１３を参照すれば、平均ＬＴデコード失敗率における本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより０．０１程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１４５】
図１４を参照すれば、平均ＰＳＮＲにおける本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約２ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１４６】
図１５〜図１８は、パケット損失パターンが集中されている場合、ケース２の遷移確率分布（Ｔｒａｎｓｉｔｉｏｎ Ｐｒｏｂａｂｉｌｉｔｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ）を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【０１４７】
図１５及び図１６は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｈａｒｂｏｕｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１４８】
図１５を参照すれば、平均ＬＴデコード失敗率における本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより２倍程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１４９】
図１６を参照すれば、平均ＰＳＮＲにおける本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約５ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１５０】
図１７及び図１８は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｓｏｃｃｅｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１５１】
図１７を参照すれば、平均ＬＴデコード失敗率における本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより０．０２程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１５２】
図１８を参照すれば、平均ＰＳＮＲにおける本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約３ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１５３】
図１９〜図２２は、パケット損失パターンが集中している場合、ケース３の遷移確率分布を有する時、本発明の一実施形態によるパケット化アルゴリズムと既存のアルゴリズムを比較したグラフである。
【０１５４】
図１９及び図２０は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｈａｒｂｏｕｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１５５】
図１９を参照すれば、平均ＬＴデコード失敗率において本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより２倍程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１５６】
図２０を参照すれば、平均ＰＳＮＲにおいて本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約４ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１５７】
図２１及び図２２は、ｓpacketが１０で、Ｒｔｈｒが５の場合、Ｓｏｃｃｅｒ映像において本発明の一実施形態によるパケット化アルゴリズムと既存のパケット化アルゴリズム間の平均ＬＴデコード失敗率と平均ＰＳＮＲをもって性能比較をしたものである。
【０１５８】
図２１を参照すれば、平均ＬＴデコード失敗率において本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより０．０１程度低いデコード失敗率を有し、γが増加するほど既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムの差が少なくなり、デコード失敗率が０に近い値に収斂する。
【０１５９】
図２２を参照すれば、平均ＰＳＮＲにおいて本発明によるパケット化アルゴリズムは、γが１に近い小さい値の場合、既存のパケット化アルゴリズムより約３ｄＢ程度高い値を有し、γが増加するにつれ既存のパケット化アルゴリズムと本発明によるパケット化アルゴリズムのＰＳＮＲ差が収斂することが分かる。
【０１６０】
図２３は、本発明の一実施形態による符号化シンボルをパケット化して伝送する装置を示す概念図である。
【０１６１】
図２３を参照すれば、符号化シンボルパケット化伝送装置は、ツリー構造化部２３００と、パケット化部２３１０と、伝送部２３２０とを含む。
【０１６２】
ツリー構造化部２３００は、ソースシンボルに基づいてＡｎｄ−Ｏｒツリーを用いてツリー構造を生成することができる。
【０１６３】
Ａｎｄ−Ｏｒツリーは、符号化シンボル間の関係分析のための有用なツールであって、一般的に２ｌの深さを有するＡｎｄ−ＯｒツリーＴｌが存在する時、ルートノードの深さは、０を有し、ルートノードに直接連結された子ノードの深さは、１を有する。また、ツリーの下方に行くほどノードの深さが１ずつ増加するようになる。すべてのノードは、０または１の値を有する。また、深さ０、２、４、…、２ｌ−２に位置するノードは、Ｏｒ−ノードと言い、Ｏｒノードは、子ノードのＯｒ−演算を通じて値が決定される。１、３、５、…、２ｌ−１に位置するノードをＡｎｄ−ノードと言い、子ノードのＡｎｄ−演算を通じて値が決定される。このツリーにＬＴコードのシンボルをマッピングさせれば、ソースシンボルはＯｒ−ノードとして見なされ、符号化シンボルはＡｎｄ−ノードとして見なされ、各々は互いに親と子ノードで結ばれるようになる。
【０１６４】
前述の図２に開示された本発明の一実施形態によるツリー構造を活用してソースシンボルを基礎にパケット化するためのツリー構造を生成することができる。
【０１６５】
本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたＬＴ符号化シンボルパケット化方法では、説明の便宜上、Ａｎｄ−Ｏｒツリーの分析深さを３に制限して説明するが、Ａｎｄ−Ｏｒツリーは、３以上の深さを有することもでき、このようなＬＴ符号化シンボルパケット化方法も本発明の権利範囲に属する。
【０１６６】
パケット化部２３１０は、ツリー構造化部２３００から提供されたツリー構造情報を基礎にして符号化シンボルをパケット化することができる。ＴＥＳｉが属するパケットに一緒に挿入される
に属する符号化シンボルの数を調節することによって、このようなＡｎｄ−Ｏｒツリー間の依存性を間接的に考慮してパケット化することができる。
【０１６７】
伝送部２３２０は、パケット化部で生成されたパケットを、通信チャンネルを利用して伝送することができる。
【０１６８】
ビデオストリーミングは、ディレイ制約があり、無線ネットワークは、制限されたリソースなので、実際に、エラーのない成功的なデコードを保証することは難しい。このような問題を解決するために、エラーが発生しやすい無線ネットワークを通じて十分な数の符号化シンボルを伝送することができるかどうかが予想できることは重要である。
【０１６９】
したがって、本発明の一実施形態によるＡｎｄ−Ｏｒツリーを用いたパケット化方法を用いる場合、特にパケット化を利用してビデオコーデックにより圧縮された形態であるビデオデータを伝送する方法において効果的に活用されることができる。
【０１７０】
以上、実施形態を参照して説明したが、当該技術分野の熟練した当業者は、下記の特許請求の範囲に記載された本発明の思想及び領域を逸脱しない範囲内で本発明を多様に修正及び変更できることは理解できることである。
【特許請求の範囲】
【請求項１】
第１ソースシンボルを決定し、
ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルと、前記パケット化していない第１符号化シンボルを挿入する目標パケットとを選択する符号化シンボル及び目標パケット選択段階と、
前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、
前記ＡＮＤ−ＯＲツリー構造を利用して、前記第２ソースシンボルに基づく少なくとも１つの第２符号化シンボルを生成し、前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化するパケット化段階と
を含む符号化シンボルのパケット化方法。
【請求項２】
前記符号化シンボルは、
ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を用いて符号化したシンボルであることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項３】
前記符号化シンボル及び目標パケット選択段階と、前記パケット化段階とにおいて、パケット化していない第１符号化シンボルが存在しない場合、前記第１ソースシンボルではなく、前記第１ソースシンボルと同じＡＮＤ−ＯＲツリー階層にあるソースシンボルを第１ソースシンボルとして、前記符号化シンボル及び目標パケット選択段階とパケット化段階とを進めすることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項４】
前記符号化シンボル及び目標パケット選択段階と前記パケット化段階において、パケット化していない第１符号化シンボルが存在せず、前記別のソースシンボルを第１ソースシンボルとして選択することができない場合には、まだパケット化していない第２符号化シンボルのうちの少なくとも１つを前記目標パケットの残りスペースに挿入することを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項５】
前記パケット化段階において、
前記第１符号化シンボルと共にパケット化される前記第２符号化シンボルが、下記の数式８を満足する値として決定されることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【数８】
【請求項６】
前記符号化シンボル及び目標パケット選択段階において、
前記目標パケットは、空きパケットが存在する場合には、前記空きパケットのうち少なくとも１つを目標パケットとし、
空きパケットが存在しない場合には、所定のパケットの使用可能なスペースがＲthr＋１より大きければ、前記所定のパケットの使用可能なスペースがＲthr＋１より大きいパケットのうちの１つを目標パケットとして決定し、
また、前記所定のパケットの使用可能なスペースが前記Ｒthr＋１より大きくなければ、前記Ｒthrが
（
は、第１符号化シンボルの次数を意味する。）より大きいか等しく、かつ、前記所定のパケットの使用可能なスペースが
より大きいか等しい場合に、前記所定のパケットのうちの少なくとも１つとして選択されること
を特徴とする請求項５に記載の符号化シンボルのパケット化方法。
【請求項７】
前記ＡＮＤ−ＯＲツリーは、
前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が第１ソースシンボルの値として決定され、
前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が第１符号化シンボルの値として決定され、
前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が第２ソースシンボルの値として算出されること
を特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項８】
前記符号化シンボルのパケット化方法は、
ビデオストリーミングサービスにおいてビデオデータを伝送するのに用いられることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項９】
符号化シンボルのパケット化装置において、
符号化対象であるソースシンボルに基づいてＡＮＤ−ＯＲツリーを用いて符号化シンボルを生成し、前記符号化シンボルに基づいて前記ＡＮＤ−ＯＲツリーを用いてソースシンボルを生成するツリー構造化部と、
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部と、を含む符号化シンボルのパケット化装置。
【請求項１０】
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、
第１ソースシンボルを決定して、前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、
前記パケット化していない第１符号化シンボルと前記パケット化していない第１符号化シンボルを挿入する目標パケットとを選択し、
前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、
前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づく少なくとも１つの第２符号化シンボルを生成し、
前記第２符号化シンボルのうちの少なくとも１つを前記第１符号化シンボルと共に前記目標パケットにパケット化すること
を特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１１】
前記ＡＮＤ−ＯＲツリーは、
前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が、第１ソースシンボルの値として決定され、
前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が、第１符号化シンボルの値として決定され、
前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が、第２ソースシンボルの値として算出されること
を特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１２】
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、
パケット化していない第１符号化シンボルが存在しない場合、前記第１ソースシンボルを除いた別の第１ソースシンボルを選択し、
前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記別の第１ソースシンボルの符号化シンボルである第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルを選択し、
前記パケット化していない第１符号化シンボルを挿入する目標パケットを決定して前記第１符号化シンボルを前記目標パケットに挿入し、
前記ＡＮＤ−ＯＲツリー構造を利用して、生成された前記第１符号化シンボルに基づく第２ソースシンボルを生成した後、
前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づく第２符号化シンボルを生成し、
前記第２符号化シンボルを前記第１符号化シンボルと共に前記目標パケットにパケット化すること
を特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１３】
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、
パケット化していない第１符号化シンボルが存在せず、前記第１ソースシンボルを除いた別の第１ソースシンボルを選択することができない場合、まだパケット化していない第２符号化シンボルのうちの少なくとも１つを前記目標パケットの残ったスペースに挿入することを特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１４】
前記符号化シンボルは、
ルビー変換を利用して符号化したシンボルであることを特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１５】
符号化シンボルのパケット化装置は、
ビデオストリーミングサービスにおいてビデオデータを伝送するのに使用されることを特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１】
第１ソースシンボルを決定し、
ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルと、前記パケット化していない第１符号化シンボルを挿入する目標パケットとを選択する符号化シンボル及び目標パケット選択段階と、
前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、
前記ＡＮＤ−ＯＲツリー構造を利用して、前記第２ソースシンボルに基づく少なくとも１つの第２符号化シンボルを生成し、前記第２符号化シンボルのうち少なくとも１つを前記目標パケットに前記第１符号化シンボルと共にパケット化するパケット化段階と
を含む符号化シンボルのパケット化方法。
【請求項２】
前記符号化シンボルは、
ルビー変換（Ｌｕｂｙ Ｔｒａｎｓｆｏｒｍ）を用いて符号化したシンボルであることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項３】
前記符号化シンボル及び目標パケット選択段階と、前記パケット化段階とにおいて、パケット化していない第１符号化シンボルが存在しない場合、前記第１ソースシンボルではなく、前記第１ソースシンボルと同じＡＮＤ−ＯＲツリー階層にあるソースシンボルを第１ソースシンボルとして、前記符号化シンボル及び目標パケット選択段階とパケット化段階とを進めすることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項４】
前記符号化シンボル及び目標パケット選択段階と前記パケット化段階において、パケット化していない第１符号化シンボルが存在せず、前記別のソースシンボルを第１ソースシンボルとして選択することができない場合には、まだパケット化していない第２符号化シンボルのうちの少なくとも１つを前記目標パケットの残りスペースに挿入することを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項５】
前記パケット化段階において、
前記第１符号化シンボルと共にパケット化される前記第２符号化シンボルが、下記の数式８を満足する値として決定されることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【数８】
【請求項６】
前記符号化シンボル及び目標パケット選択段階において、
前記目標パケットは、空きパケットが存在する場合には、前記空きパケットのうち少なくとも１つを目標パケットとし、
空きパケットが存在しない場合には、所定のパケットの使用可能なスペースがＲthr＋１より大きければ、前記所定のパケットの使用可能なスペースがＲthr＋１より大きいパケットのうちの１つを目標パケットとして決定し、
また、前記所定のパケットの使用可能なスペースが前記Ｒthr＋１より大きくなければ、前記Ｒthrが
（
は、第１符号化シンボルの次数を意味する。）より大きいか等しく、かつ、前記所定のパケットの使用可能なスペースが
より大きいか等しい場合に、前記所定のパケットのうちの少なくとも１つとして選択されること
を特徴とする請求項５に記載の符号化シンボルのパケット化方法。
【請求項７】
前記ＡＮＤ−ＯＲツリーは、
前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が第１ソースシンボルの値として決定され、
前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が第１符号化シンボルの値として決定され、
前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が第２ソースシンボルの値として算出されること
を特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項８】
前記符号化シンボルのパケット化方法は、
ビデオストリーミングサービスにおいてビデオデータを伝送するのに用いられることを特徴とする請求項１に記載の符号化シンボルのパケット化方法。
【請求項９】
符号化シンボルのパケット化装置において、
符号化対象であるソースシンボルに基づいてＡＮＤ−ＯＲツリーを用いて符号化シンボルを生成し、前記符号化シンボルに基づいて前記ＡＮＤ−ＯＲツリーを用いてソースシンボルを生成するツリー構造化部と、
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部と、を含む符号化シンボルのパケット化装置。
【請求項１０】
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、
第１ソースシンボルを決定して、前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記第１ソースシンボルの符号化シンボルである少なくとも１つの第１符号化シンボルのうちパケット化していない第１符号化シンボルが存在する場合、
前記パケット化していない第１符号化シンボルと前記パケット化していない第１符号化シンボルを挿入する目標パケットとを選択し、
前記ＡＮＤ−ＯＲツリー構造を利用して、前記パケット化していない少なくとも１つの第１符号化シンボルに基づく第２ソースシンボルを生成した後、
前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づく少なくとも１つの第２符号化シンボルを生成し、
前記第２符号化シンボルのうちの少なくとも１つを前記第１符号化シンボルと共に前記目標パケットにパケット化すること
を特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１１】
前記ＡＮＤ−ＯＲツリーは、
前記少なくとも１つの第１符号化シンボルをＡＮＤ演算した値が、第１ソースシンボルの値として決定され、
前記少なくとも１つの第２ソースシンボルをＯＲ演算した値が、第１符号化シンボルの値として決定され、
前記少なくとも１つの第２符号化シンボルをＡＮＤ演算した値が、第２ソースシンボルの値として算出されること
を特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１２】
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、
パケット化していない第１符号化シンボルが存在しない場合、前記第１ソースシンボルを除いた別の第１ソースシンボルを選択し、
前記ＡＮＤ−ＯＲツリー構造を利用して生成した前記別の第１ソースシンボルの符号化シンボルである第１符号化シンボルの中にパケット化していない第１符号化シンボルが存在する場合、前記パケット化していない第１符号化シンボルを選択し、
前記パケット化していない第１符号化シンボルを挿入する目標パケットを決定して前記第１符号化シンボルを前記目標パケットに挿入し、
前記ＡＮＤ−ＯＲツリー構造を利用して、生成された前記第１符号化シンボルに基づく第２ソースシンボルを生成した後、
前記ＡＮＤ−ＯＲツリー構造を利用して前記第２ソースシンボルに基づく第２符号化シンボルを生成し、
前記第２符号化シンボルを前記第１符号化シンボルと共に前記目標パケットにパケット化すること
を特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１３】
前記ＡＮＤ−ＯＲツリーを用いて生成された前記符号化シンボルのうち少なくとも１つをパケット化するパケット化部は、
パケット化していない第１符号化シンボルが存在せず、前記第１ソースシンボルを除いた別の第１ソースシンボルを選択することができない場合、まだパケット化していない第２符号化シンボルのうちの少なくとも１つを前記目標パケットの残ったスペースに挿入することを特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１４】
前記符号化シンボルは、
ルビー変換を利用して符号化したシンボルであることを特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【請求項１５】
符号化シンボルのパケット化装置は、
ビデオストリーミングサービスにおいてビデオデータを伝送するのに使用されることを特徴とする請求項９に記載の符号化シンボルのパケット化装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１２−１２０１６１（Ｐ２０１２−１２０１６１Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１１−２４８９６３（Ｐ２０１１−２４８９６３）
【出願日】平成２３年１１月１４日（２０１１．１１．１４）
【出願人】（５１１２５８４１１）ポハン工科大学校産学協力団 (3)
【氏名又は名称原語表記】ＰＯＳＴＥＣＨ ＡＣＡＤＥＭＹ−ＩＮＤＵＳＴＲＹ ＦＯＵＮＤＡＴＩＯＮ
【住所又は居所原語表記】Ｓａｎ ３１，Ｈｙｏｊａ−ｄｏｎｇ，Ｎａｍ−ｇｕ，Ｐｏｈａｎｇ−ｓｉ，Ｇｙｅｏｎｇｂｕｋ ７９０−７８４，Ｒｅｐｕｂｌｉｃ ｏｆ Ｋｏｒｅａ
【出願人】（５９６０９９８８２）エレクトロニクス アンド テレコミュニケーションズ リサーチ インスチチュート (179)
【氏名又は名称原語表記】ＥＬＥＣＴＲＯＮＩＣＳ ＡＮＤ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＲＥＳＥＡＲＣＨ ＩＮＳＴＩＴＵＴＥ
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２３年１１月１４日（２０１１．１１．１４）
【出願人】（５１１２５８４１１）ポハン工科大学校産学協力団 (3)
【氏名又は名称原語表記】ＰＯＳＴＥＣＨ ＡＣＡＤＥＭＹ−ＩＮＤＵＳＴＲＹ ＦＯＵＮＤＡＴＩＯＮ
【住所又は居所原語表記】Ｓａｎ ３１，Ｈｙｏｊａ−ｄｏｎｇ，Ｎａｍ−ｇｕ，Ｐｏｈａｎｇ−ｓｉ，Ｇｙｅｏｎｇｂｕｋ ７９０−７８４，Ｒｅｐｕｂｌｉｃ ｏｆ Ｋｏｒｅａ
【出願人】（５９６０９９８８２）エレクトロニクス アンド テレコミュニケーションズ リサーチ インスチチュート (179)
【氏名又は名称原語表記】ＥＬＥＣＴＲＯＮＩＣＳ ＡＮＤ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＲＥＳＥＡＲＣＨ ＩＮＳＴＩＴＵＴＥ
【Ｆターム（参考）】
[ Back to top ]