(57)【要約】ラプターコードをデコードする方法及び装置が提供される。本装置は、符号化シンボルの系列を表すパケットの系列をデコードするデコーダ１４０を含む。デコーダ１４０は、ラプターコードを使用して系列の少なくとも幾つかの失われたパケット又は破壊されたパケットを少なくとも部分的に回復する。
2009526476.tif 000002
【特許請求の範囲】
【請求項１】
符号化シンボルの系列を表わすパケットの系列をデコードするデコーダを含む装置であって、
前記デコーダは、ラプターコードを使用して前記系列の少なくとも幾つかの失われたパケット又は破壊されたパケットを少なくとも部分的に回復する、
ことを特徴とする装置。
【請求項２】
前記デコーダは、前記符号化シンボルに基づいて式の線形システムを構築し、前記式の線形システムは、
【数１】
2009526476.tif 000019
により表わされ、Ｅはインデックス｛Ｉ0,Ｉ1,…,ＩM-1｝をもつ符号化シンボルを表わし、Ｍは符号化シンボルの数を表わし、Ｃ[0],Ｃ[1],…,Ｃ[L-1]はパケットの系列に符号化されるべき中間のシンボルを表わし、Ｋはシステマチックではないラプターコードを使用したときに中間のシンボルのサブセットに対応するか、システマチックなラプターコードを使用したときに符号化シンボルのサブセットに対応するソースシンボルの数を表わし、Ｓは中間のシンボルから生成される低密度パリティチェックシンボルを表わし、ＨLDPCは低密度パリティチェックシンボルを生成するために使用されるマトリクスを表わし、Ｈは中間のシンボルから生成されたハーフシンボルを表わし、ＨHalfはハーフシンボルを生成するために使用されるマトリクスを表わし、
（外１）
2009526476.tif 000020
は符号化シンボルを生成するマトリクスを表わし、ＩS×SはディメンジョンＳ×Ｓのアイデンティティマトリクスを表わし、０S×HはディメンジョンＳ×Ｈのゼロマトリクスを表わし、ＩH×HはディメンジョンＨ×Ｈのアイデンティティマトリクスを表わし、Ｂはあるマトリクスを表わし、Ｌは中間のシンボルの数を表わす、
請求項１記載の装置。
【請求項３】
前記デコーダは、前記マトリクスＢを上三角行列に変換する、
請求項２記載の装置。
【請求項４】
前記デコーダは、ガウス消去法を使用して前記マトリクスＢを前記上三角行列に変換する、
請求項３記載の装置。
【請求項５】
前記デコーダは、［Ｃ(ｐ0),Ｃ(ｐ1),．．．,Ｃ(ｐW-1)］Tにより表わされる中間シンボルの少なくとも幾つかを回復するためにトレースバック演算を実行し、ｐiは少なくとも幾つかのシンボルのうちの特定の１つのインデックスを示し、Ｗは少なくとも幾つかの中間のシンボルの数を示し、０≦ｐi≦Ｌ及びＷ＜Ｌであり、
前記デコーダは、前記マトリクスＢの前記上三角行列への変換が失敗したとき、
【数２】
2009526476.tif 000021
を使用して、少なくとも幾つかの中間のシンボルから、失われたパケット又は破壊されたパケットに対応する失われたソースシンボル又は破壊されたソースシンボルを計算する、
請求項３記載の装置。
【請求項６】
前記デコーダは、前記マトリクスＢのランクが予め指定された閾値よりも大きいときにのみ前記トレースバック演算を実行する、
請求項５記載の装置。
【請求項７】
前記デコーダは、トレースバック演算を実行して、前記符号化シンボルに対応する中間のシンボルのサブセットを取得し、前記中間のシンボルのサブセットから、少なくとも幾つかの失われたパケット又は破壊されたパケットに対応する、失われたソースシンボル又は破壊されたソースシンボルを計算する、
請求項１記載の装置。
【請求項８】
符号化シンボルの系列を表わすパケットの系列をデコードするステップを含む方法であって、
前記デコードするステップは、ラプターコードを使用して前記系列の少なくとも幾つかの失われたパケット又は破壊されたパケットを少なくとも部分的に回復する、
ことを特徴とする方法。
【請求項９】
前記デコードするステップは、前記符号化シンボルに基づいて式の線形システムを構築し、前記式の線形システムは、
【数３】
2009526476.tif 000022
により表わされ、Ｅはインデックス｛Ｉ0,Ｉ1,…,ＩM-1｝をもつ符号化シンボルを表わし、Ｍは符号化シンボルの数を表わし、Ｃ[0],Ｃ[1],…,Ｃ[L-1]はパケットの系列に符号化されるべきソースシンボルを表わし、Ｋはソースシンボルの数を表わし、Ｓはソースシンボルから生成される低密度パリティチェックシンボルを表わし、ＨLDPCは低密度パリティチェックシンボルを生成するために使用されるマトリクスを表わし、Ｈはソースシンボルから生成されたハーフシンボルを表わし、ＨHalfはハーフシンボルを生成するために使用されるマトリクスを表わし、
（外２）
2009526476.tif 000023
は符号化シンボルを生成するマトリクスを表わし、ＩS×SはディメンジョンＳ×Ｓのアイデンティティマトリクスを表わし、０S×HはディメンジョンＳ×Ｈのゼロマトリクスを表わし、ＩH×HはディメンジョンＨ×Ｈのアイデンティティマトリクスを表わし、Ｂはあるマトリクスを表わし、Ｌは中間のシンボルの数を表わす、
請求項８記載の方法。
【請求項１０】
前記デコードするステップは、前記マトリクスＢを上三角行列に変換する、
請求項９記載の方法。
【請求項１１】
前記デコードするステップは、ガウス消去法を使用して前記マトリクスＢを前記上三角行列に変換する、
請求項１０記載の方法。
【請求項１２】
前記デコードするステップは、［Ｃ(ｐ0),Ｃ(ｐ1),．．．,Ｃ(ｐW-1)］Tにより表わされる中間のシンボルの少なくとも幾つかを回復するためにトレースバック演算を実行し、ｐiは少なくとも幾つかのシンボルのうちの特定の１つのインデックスを示し、Ｗは少なくとも幾つかの中間のシンボルの数を示し、０≦ｐi≦Ｌ及びＷ＜Ｌであり、
前記デコードするステップは、前記マトリクスＢの前記上三角行列への変換が失敗したとき、
【数４】
2009526476.tif 000024
を使用して、少なくとも幾つかの中間のシンボルから、失われたパケット又は破壊されたパケットに対応する失われたソースシンボル又は破壊されたソースシンボルを計算する、
請求項１０記載の方法。
【請求項１３】
前記デコードするステップは、前記マトリクスＢのランクが予め指定された閾値よりも大きいときにのみ前記トレースバック演算を実行する、
請求項１２記載の方法。
【請求項１４】
前記デコードするステップは、トレースバック演算を実行して、前記符号化シンボルに対応する中間のシンボルのサブセットを取得し、前記中間のシンボルのサブセットから、少なくとも幾つかの失われたパケット又は破壊されたパケットに対応する、失われたソースシンボル又は破壊されたソースシンボルを計算する、
請求項８記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ファウンテンコード（fountain  codes）全般に関し、より詳細には、ラプターコード（raptor  code）をデコードする方法及び装置に関する。  
本出願は、２００６年２月８日に提出された米国仮出願シリアル番号６０／７７１３７７の利益を特許請求するものである。
【背景技術】
【０００２】
第三世代パートナーシッププロジェクト（３ＧＰＰ）は、１９９８年１２月に確立された提携契約である。この提携契約は、組織のパートナーとして知られる多数の電気通信規格の機関を集める。３ＧＰＰの本来の領域は、進化されるＧＳＭ（Global  System  for  Mobile  communication）コアネットワーク及び彼らがサポートする無線アクセス技術（すなわちＵＴＲＡ（Universal  Terrestrial  Radio  Access）、ＦＤＤ（Frequency  Division  Duplex）及びＴＤＤ（Time  Division  Duplex）モードの両者）に基づいて第三世代のモバイルシステムのグローバルに適用可能な技術仕様と技術報告を生成することである。この領域は、（たとえばＧＰＲＳ（General  Packet  Radio  Service）及びＥＤＧＥ（Enhanced  Data  rates  for  GSM  Evolution）といった）進化された無線アクセス技術を含むＧＳＭの技術仕様及び技術報告のメンテナンス及び開発を含むためにその後に補正された。
【０００３】
システマチックなラプターコードは、３ＧＰＰマルチメディアブロードキャスト／マルチキャストサービス（ＭＢＭＳ）のアプリケーションレイヤの順方向誤り訂正（ＦＥＣ）コードとして採用される。ラプターコードをデコードするため、デコーダは、典型的に、線形方程式のシステムを構築し、この式を解くためにガウス消去法を使用する。しかし、このシステムがフルランクから構成されないとき（すなわち、受信されたソース及びパリティパケットが完全なデコードのために適切ではないとき）、デコーダは、失敗を通常宣言し、受信されたソースパケットのみを出力する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来技術のこれらの課題及び問題、並びに他の課題及び問題は本発明により対処され、本発明は、ラプターコードをデコードする方法及び装置に向けられる。
【課題を解決するための手段】
【０００５】
本発明の態様によれば、装置が提供され、本装置は、符号化シンボルの系列を表すパケットの系列をデコードするデコーダを含む。このデコーダは、ラプターコードを使用して少なくとも幾つかの失われたパケット又は破壊されたパケットの系列を少なくとも部分的に回復する。
【０００６】
本発明の別の態様によれば、方法が提供され、本方法は、符号化シンボルの系列を表すパケットの系列をデコードするステップを含む。デコードするステップは、ラプターコードを使用して、少なくとも幾つかの失われたパケット又は破壊されたパケットを少なくとも部分的に回復する。
【０００７】
本発明のこれらの態様、特徴及び利点、並びに他の態様、特徴及び利点は、添付図面と共に読まれる、例示的な実施の形態の以下の詳細な説明から明らかとなるであろう。本発明は、以下の添付図面に従って良好に理解される。
【発明を実施するための最良の形態】
【０００８】
本発明は、ラプターコードをデコードする方法及び装置に向けられる。  
本実施の形態での説明は、本発明を例示するものである。したがって、本実施の形態で明示的に記載又は図示されていないが、当業者であれば、本発明を実施する様々なアレンジメントであって、本発明の精神及び範囲に含まれる様々なアレンジメントを考えることができるであろうことを理解されたい。
【０００９】
本実施の形態で引用される全ての例及び条件付き言語は、本発明の原理及び当該技術分野を促進するために本発明者により寄与される概念を理解することにおいて読者を支援する教育的な目的について意図され、係る特に引用された例及び条件への制限がないものとして解釈されるべきである。
【００１０】
さらに、本発明の特定の例と同様に、本発明の原理、態様及び実施の形態を引用する全ての記述は、本発明の構造的且つ機能的に等価なものを包含することが意図される。さらに、係る等価なものは、現在知られている等価なものと同様に、将来に開発される等価なもの、すなわち構造に関わらず、同じ機能を実行する開発されたエレメントを含むことが意図される。
【００１１】
したがって、たとえば、本実施の形態で与えられるブロック図は、本発明の原理を実施する例示的な回路の概念図を表わすことを当業者により理解されるであろう。同様に、任意のフローチャート、フローダイアグラム、状態遷移図、擬似コード等は、様々なプロセスを表わし、この様々なプロセスは、コンピュータ読取り可能な媒体で実質的に表わされ、コンピュータ又はプロセッサが明示的に示されるか否かに関わらず、コンピュータ又はプロセッサにより実行されることが理解される。
【００１２】
図示される様々なアレメントの機能は、専用ハードウェアの使用を通して、適切なソフトウェアに関連してソフトウェアを実行可能なハードウェアの使用を通して提供される。プロセッサにより提供されるとき、機能は、１つの専用のプロセッサにより、そのうちの幾つかが共有される複数の個々のプロセッサにより提供される。さらに、用語「プロセッサ」又は「コントローラ」の明示的な使用は、ソフトウェアを実行可能なハードウェアを排他的に示すために解釈されるべきではなく、制限されることなしに、デジタルシグナルプロセッサ（ＤＳＰ）ハードウェア、ソフトウェアを記憶するリードオンリメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）及び不揮発性ストレージを暗黙的に含む。
【００１３】
コンベンショナル及び／又はカスタムな他のハードウェアが含まれる場合もある。同様に、図示される任意のスイッチは、概念的なものである。それらの機能は、プログラムロジックの動作を通して、専用ロジックを通して、プログラム制御と専用ロジックのインタラクションを通して、或は更に手動的に実行され、特定の技術は、文脈から更に詳細に理解されるように実現者により選択可能である。
【００１４】
本発明の請求項では、特定の機能を実行する手段として表現されるエレメントは、たとえばａ）その機能を実行する回路素子の組み合わせ、又はｂ）その機能を実行するそのソフトウェアを実行する適切な回路と組み合わされる、ファームウェア、マイクロコード等を含む任意の形式に於けるソフトウェアを含む、その機能を実行する任意のやり方を包含することが意図される。係る請求項により定義される本発明は、様々な引用される手段により提供される機能が、請求項が求めるやり方で結合され一つにされるという事実にある。したがって、それらの機能を提供することができる任意の手段は本実施の形態で示される手段に等価であると考えられる。
【００１５】
本発明の「１実施の形態」又は「実施の形態」に対する明細書における引用は、実施の形態と共に記載される特定の特徴、構造、特性等が本発明の少なくとも１つの実施の形態に含まれることを意味する。したがって、明細書を通して様々な場所で現れるフレーズ「１実施の形態では」又は「実施の形態では」の出現は、必ずしも同じ実施の形態を全て言及するものではない。
【００１６】
図１を参照して、本発明が適用される場合がある例示的なビデオ符号化／復号化の環境は、参照符号１００により一般的に示される。ビデオ符号化／復号化の環境１００は、パケット化及びラプターエンコーダ１２０の入力と信号通信で接続される出力を有するビデオエンコーダ１１０を含む。パケット化及びラプターエンコーダ１２０の出力は、無線／有線ネットワーク１３０のアクセスポイントと信号通信で接続される。無線／有線ネットワーク１３０の別のアクセスポイントは、逆パケット化（de-packetization）及びラプターデコーダ１４０の入力と信号通信で接続される。逆パケット化及びラプターデコーダの出力は、ビデオデコーダ１５０の入力と信号通信で接続される。
【００１７】
ビデオエンコーダ１１０は、エンコードされるべき入力ビデオ信号を受け、エンコードされたビットストリームを出力する。パケット化及びラプターエンコーダ１２０は、ラプターコードを使用してビデオエンコーダから出力されたエンコードされたビットストリームをエンコードし、無線／有線ネットワーク１３０を通して送信のために結果的に得られるビットストリームをパケット化する。逆パケット化及びラプターデコーダ１４０は、ラプターコードのデコードのために送信されたビットストリームを逆パケット化して、ビデオデコーダ１５０による後のデコードのためにビットストリームを取得する。ラプターコードのエンコード及びデコードは、以下に本実施の形態において更に詳細に記載される。
【００１８】
実施の形態では、本発明は、たとえば逆パケット化及びラプターデコーダ１４０に関して実現されることが理解される。しかし、図１の例示的なビデオ符号化／復号化の環境１００は、本発明が適用される多数の環境及び用途のうちの１つであることを更に理解されたい。すなわち、本実施の形態で提供される本発明の教示が与えられると、当業者の１人であれば、本発明の範囲を保持しつつ、本発明に従うラプターコードのデコードが適用される、この及び他の様々な他の環境及び用途を考えるであろう。たとえば、本発明は、ファウンテンコード及び誤り訂正コードに関して利用される場合がある任意のタイプのデータに関して実現される。
【００１９】
本発明によれば、ラプターコードをデコードする方法及び装置が開示される。実施の形態では、本発明の実現は、受信されたソース及びパリティパケットが完全なデコードのために適切ではないときでさえ（すなわちシステムがフルランクからなるものではないときでさえ）、できるだけ多くのパケットを回復する。
【００２０】
実施の形態では、ラプターコードは、以下のようにエンコードされる。以下では、シンボルを使用して、ビット列であるパケットを符号化プロセスで表わす。システマチックなラプターコードは、システマチックではないラプターコードに基づいて生成される。したがって、システマチックではないラプターコードがはじめに導入される。
【００２１】
システマチックではないラプターコードは、たとえば３ＧＰＰのケースにおいて、３つのレイヤを含む場合がある階層型のコードである。勿論、異なる数の層が利用される場合もある。Ｋ個の中間的なシンボル［Ｃ(0),Ｃ(1),．．．,Ｃ(K-1)］Tを仮定すると（これらＫ個の中間的なシンボルはシステマチックではないラプターコードについて実際にＫ個のソースシンボルであり、システマチックなラプターコードについて、Ｋ個の中間的なシンボルは、以下に更に説明されるＫ個のソースシンボルを使用して得られる）、以下のように、高レートのＬＤＰＣコードを使用して、Ｓ個の低密度パリティチェック（ＬＤＰＣ）シンボルがはじめに生成される。
【００２２】
【数５】
2009526476.tif 000003
ここでＨLDPCはＳ×Ｋの低密度パリティマトリクスを表す。次いで、以下のように、グレイ系列を利用した高密度パリティチェックマトリクスを使用して、Ｈハーフシンボルが生成される。
【００２３】
【数６】
2009526476.tif 000004
ここでＨHalfはＨ×（Ｋ＋Ｓ）高密度マトリクスである。したがって、以下のように、Ｌ＝Ｋ＋Ｓ＋Ｈの中間のシンボルが得られる。
【００２４】
【数７】
2009526476.tif 000005
なお、ＨLDPC及びＨHalfは、エレメント０又は１をもつマトリクスである。ビット毎のＸＯＲ演算は、マトリクス−ベクトルの乗算における加算を実行するために使用される場合がある。
【００２５】
符号化シンボルは、以下のように、ＬＴ（Luby  Transform）マトリクスを使用して生成される。
【００２６】
【数８】
2009526476.tif 000006
なお、ＨLTはＬ列をもつ低密度パリティマトリクスであり、行数は、どの位多くの符号化シンボルを生成したいかに依存して変化することができる。理論的に、生成することができる符号化シンボルの数は無限である。さらに、ある行における１の数は、Ｌｕｂｙ変換分布に従う。Ｌｕｂｙ変換分布は、符号化シンボルの程度の分布であり、この程度とは、符号化シンボルを形成するために互いにＸＯＲされた中間のシンボルの数を意味する。Ｌｕｂｙ変換の分布は、表１に示される。
【００２７】
【表１】
2009526476.tif 000007
システマチックではないラプターコードについて、符号化シンボルは、エンコーダで生成され、受信機側に送信される。チャネルの実現のため、符号化シンボルの幾つかが失われる。デコーダのタスクは、受信された符号化シンボルが与えられる、ソースシンボル［Ｃ(0),Ｃ(1),．．．,Ｃ(K-1)］Tを回復することである。
【００２８】
システマチックなラプターコードについて、最初のＫ個の符号化シンボルは、典型的にソースシンボルである。符号化シンボルの残りを形成するため、Ｌ個の中間のシンボル［Ｃ(0),Ｃ(1),．．．,Ｃ(L-1)］Tが計算される。システマチックではないラプターコードの構築プロセスから、以下の関係を有する。
【００２９】
【数９】
2009526476.tif 000008
マトリクス(ＨLT)K×(K+S+H)、ＨLDPC及びＨHalfは、マトリクスＡがフルランク、すなわちＬからなるように構築される。次いで、中間シンボル［Ｃ(0),Ｃ(1),．．．,Ｃ(L-1)］Tは、上記式を解くことで計算することができる。なお、(ＨLT)K×(K+S+H)は、半無限のマトリクスＨLTの最初のＫ行を含む。全ての他の符号化シンボルは、マトリクスＨLTの他の行及びＬ個の中間のシンボルを使用して生成することができる。マトリクスＩS×S及びＩH×Hは、それぞれ、ディメンジョンＳ×Ｓ及びＨ×Ｈのアイデンティティマトリクスである。マトリクス０S×Hは、ディメンジョンＳ×Ｈの全てがゼロのマトリクスである。
【００３０】
したがって、上述されたように、システマチックラプターコードについて、符号化プロセスは、式（５）のような線形方程式のセットを解くことを含む。マトリクスＡは疎行列であるので、式（５）を解くことの複雑さは、比較的に低い。実際に、システマチックラプターコードについて、デコーダのタスクは、受信された符号化シンボルが与えられる、最初のＫ個の符号化シンボル［Ｅ(0),Ｅ(1),．．．,Ｅ(K-1)］Tを回復することである。
【００３１】
典型的に、ラプターコードは、以下のようにデコードされる。デコードプロセスは、エンコードプロセスに類似している。インデックス｛Ｉ0,Ｉ1,…,ＩM-1｝をもつＭ個の符号化シンボルを受信するものとする。Ｍ個の符号化シンボルに対応するＨLTマトリクスにおける行は、ディメンジョンＭ×Ｌの新たなマトリクス
（外３）
2009526476.tif 000009
を形成する。したがって、デコードプロセスは、以下の線形システムを解くことを含む。
【００３２】
【数１０】
2009526476.tif 000010
実際に、式（６）における線形システムは、マトリクスＢがランクＬからなるときに解くことができる。さもなければ、デコーダは、受信されたソースシンボル、すなわち受信された符号化シンボルのセット｛Ｅ［Ｉi］｜０≦Ｉi≦（Ｋ−１）｝を単に出力する。
【００３３】
実施の形態では、ラプターコードは、以下のようにデコードされる。この実施の形態は、できるだけ多くのソースシンボルの回復を可能にする。実施の形態は、最初に一般的に記載され、図２に関して別の記載が続く。
【００３４】
ラプターコードをデコードするため、式（６）における線形システムは、インデックス｛Ｉ0,Ｉ1,…,ＩM-1｝をもつ受信されたＭ個の符号化シンボルに基づいて構築される。ガウス消去法が使用され、マトリクスＢが上三角行列に変換される。勿論、本発明は、ガウス消去方法の使用にのみ限定されず、本発明の範囲を維持しつつ、他の方法を使用して、マトリクスＢが上三角行列に変換される場合がある。三角形の分割が成功した場合、すなわちマトリクスＢがランクＬからなる場合、トレースバックアプローチが使用され、中間のシンボル［Ｃ(0),Ｃ(1),．．．,Ｃ(L-1)］Tが取得される。失われたソースシンボルは、式（４）を使用して計算することができる。
【００３５】
三角形の分割が失敗した場合、すなわちマトリクスＢのランクがＬよりも小さい場合、典型的な結果はデコードプロセスが停止することである。しかし、本発明の実施の形態によれば、トレースバック動作が実行され、［Ｃ(ｐ0),Ｃ(ｐ1),．．．,Ｃ(ｐW-1)］Tとして表わされる中間シンボルのサブセットが取得され、ｐiは中間シンボルのインデックスを示し、Ｗは回復された中間シンボルの数を示し、０≦ｐi≦Ｌ及びＷ＜Ｌである。失われたソースシンボルのサブセットは、式（４）及び［Ｃ(ｐ0),Ｃ(ｐ1),．．．,Ｃ(ｐW-1)］Tを使用して計算することができる。
【００３６】
説明のため、トレースバック演算及び部分的に回復された中間シンボルを使用した失われたソースシンボルの回復に関する例を与える。はじめに、Ｌ＝３と想定して、三角形の分割の後、以下の線形システムが得られる。
【００３７】
【数１１】
2009526476.tif 000011
ここでマトリクスＢはフルランクからなる。従って、トレースバック演算は、首尾よく実行され、はじめに、システムの第三行から、Ｃ[2]＝１が取得され、次いで、第二行から、
（外４）
2009526476.tif 000012
であり、Ｃ[1]＝１が取得され、最後に、第一行から、
（外５）
2009526476.tif 000013
であり、Ｃ[0]＝０が取得される。全ての中間のシンボルが回復されるので、式（４）を使用して全ての失われたソースシンボルが計算される。
【００３８】
ここで、部分的に回復された中間シンボルを使用して失われたソースシンボルの回復を説明する。同様に、Ｌ＝３であるとし、ソースシンボルＥ[0]が失われ、Ｅ[0]＝Ｃ[0]である。三角形の分割の後、以下の線形システムを有する。
【００３９】
【数１２】
2009526476.tif 000014
ここでマトリクスＢのランクは２であり、フルランクからなるものではない。２つの中間のシンボルのみが回復される。はじめに、システムの第二行から、Ｃ[1]＝０が取得され、次いで、システムの第一行から、
（外６）
2009526476.tif 000015
であり、Ｃ[0]＝１が取得される。中間のシンボルＣ[2]が回復されない場合、Ｅ[0]＝Ｃ[0]であるので失われたシンボルＥ[0]＝１が計算される。
【００４０】
実施の形態では、上述されたトレーストラック演算は、マトリクスＢのランクが予め指定された閾値よりも大きいときにのみ実行される。これにより、たとえばマトリクスＢのランクが小さいときに、取得された中間シンボルのサブセットが小さなセットであるような、幾つらかの計算が節約される場合がある。幾らかのソースシンボルを回復する可能性はおそらく低い。
【００４１】
図２を参照して、ラプターコードをデコードする例示的な方法は、参照符号２００により一般的に示される。本方法２００は、機能ブロック２１０に制御を移す開始ブロック２０５を含む。機能ブロック２１０は、インデックス｛Ｉ0,Ｉ1,…,ＩM-1｝をもつ符号化シンボルを受信し、機能ブロック２１５に制御を移す。機能ブロック２１５は、式（６）を使用して受信された符号化シンボルに基づいて式の線形システムを構築し、機能ブロック２２０に制御を移す。機能ブロック２２０は、たとえばガウス消去法を使用して式（６）におけるマトリクスＢの上側の三角形分割を実行し、判定ブロック２２５に制御を移す。判定ブロック２２５は、マトリクスＢのランクがランクＬよりも小さいかを否かを判定する。マトリクスＢのランクがランクＬよりも小さい場合、制御は判定ブロック２３０に移される。さもなければ、制御は機能ブロック２５０に移される。
【００４２】
判定ブロック２３０は、マトリクスＢのランクが閾値よりも大きいか否かを判定する。マトリクスＢのランクが閾値よりも大きい場合、制御は機能ブロック２３５に通過される。さもなければ、制御は終了ブロック２９９に移される。
【００４３】
機能ブロック２３５は、トレースバック演算を使用して、インデックス｛ｐ(0),ｐ(1),…,ｐ(W-1)｝をもつ中間のシンボルが回復され、Ｗ＜Ｌであり、機能ブロック２４０に制御が移される。機能ブロック２４０は、インデックス｛ｐ(0),ｐ(1),…,ｐ(W-1)｝を持つ中間のシンボル及び式（４）を使用して失われたソースシンボルのサブセットを取得し、終了ブロック２９９に制御を移す。
【００４４】
機能ブロック２５０は、トレースバック演算を使用して、全ての中間シンボルを回復し、機能ブロック２５５に制御を移す。機能ブロック２５５は、式（４）を使用して全ての失われたソースシンボルを取得し、終了ブロック２９９に制御を移す。
【００４５】
本発明の多数の付随する利点／特徴の説明が与えられ、その幾つかは先に説明された。たとえば、１つの利点／特徴は、符号化シンボル系列を表わすパケットの系列をデコードするデコーダを含む装置である。このデコーダは、ラプターコードを使用して少なくとも幾つかの失われたパケット又は破壊されたパケットを少なくとも部分的に回復する。
【００４６】
別の利点／特徴は、上述されたデコーダを有する装置であり、デコーダは、符号化シンボルに基づいて式の線形システムを構築し、式の線形システムは、以下により表わされる。
【００４７】
【数１３】
2009526476.tif 000016
ここでＥはインデックス｛Ｉ0,Ｉ1,…,ＩM-1｝をもつ符号化シンボルを表わし、Ｍは符号化シンボル数を表わし、Ｃ[0],Ｃ[1],…,Ｃ[L-1]はパケットの系列に符号化されるべき中間シンボルを表し、Ｋはシステマチックではないラプターコードを使用したときに中間シンボルのサブセットに対応するか、システマチックなラプターコードを使用したときに符号化シンボルのサブセットに対応するソースシンボルの数を表わし、Ｓは中間シンボルから生成される低密度パリティチェックシンボルを表わし、ＨLDPCは、低密度パリティチェックシンボルを生成するために使用されるマトリクスを表わし、Ｈは中間シンボルから生成されたハーフシンボルを表わし、ＨHalfはハーフシンボルを生成するために使用されるマトリクスを表わし、
（外７）
2009526476.tif 000017
は符号化シンボルを生成するマトリクスを表わし、ＩS×SはディメンジョンＳ×Ｓのアイデンティティマトリクスを表わし、０S×HはディメンジョンＳ×Ｈのゼロマトリクスを表わし、ＩH×HはディメンジョンＨ×Ｈのアイデンティティマトリクスを表わし、Ｂはあるマトリクスを表わし、Ｌは中間のシンボルの数を表わす。
【００４８】
更に別の利点／特徴は、上述されたように式の線形システムを構築するデコーダを有する装置であり、デコーダは、上三角行列にマトリクスＢを変換する。
【００４９】
さらに、別の利点／特徴は、式の線形システムを構築し、上述のマトリクスＢを上三角行列に変換するデコーダを有する装置であり、デコーダは、ガウス消去法を使用して上三角行列にマトリクスＢを変換する
また、別の利点／特徴は、式の線形システムを構築し、上述されたように上三角行列にマトリクスＢを変換するデコーダを有する装置であり、デコーダは、［Ｃ(ｐ0),Ｃ(ｐ1),．．．,Ｃ(ｐW-1)］Tにより表わされる中間シンボルの少なくとも幾つかを回復するためにトレースバック演算を実行する。ｐiは少なくとも幾つかのシンボルのうちの特定の１つのインデックスを示し、Ｗは少なくとも幾つかの中間のシンボルの数を示し、０≦ｐi≦Ｌ及びＷ＜Ｌである。デコーダは、マトリクスＢの上三角行列への変換が失敗したとき、以下の式を使用して、少なくとも幾つかの中間のシンボルから、失われたパケット又は破壊されたパケットに対応する失われたソースシンボル又は破壊されたソースシンボルを計算する。
【００５０】
【数１４】
2009526476.tif 000018
さらに、別の利点／特徴は、式の線形システムを構築し、マトリクスＢを上三角行列に変換し、上述されたようにトレースバック演算を実行するデコーダを有する装置であり、デコーダは、マトリクスＢのランクが予め指定された閾値よりも大きいときにのみトレースバック演算を実行する。
【００５１】
さらに、別の利点／特徴は、上述されたようなデコーダを有する装置であり、デコーダは、トレースバック演算を実行して、符号化シンボルに対応する中間シンボルのサブセットを取得し、中間のシンボルのサブセットから、少なくとも幾つかの失われたパケット又は破壊されたパケットに対応する、失われたソースシンボル又は破壊されたソースシンボルを計算する。
【００５２】
本発明のこれら及び他の特徴及び利点は、本実施の形態での教示に基づいて当業者により容易に確認される場合がある。なお、本発明の教示はハードウェア、ソフトウェア、ファームウェア、特定用途向けプロセッサ、又はその組み合わせの様々な形式で実現される場合があることを理解されたい。
【００５３】
最も好ましくは、本発明の原理は、ハードウェア及びソフトウェアの組み合わせとして実現される。さらに、ソフトウェアは、プログラムストレージユニットに有形に実施されるアプリケーションプログラムとして実現される場合がある。アプリケーションプログラムは、適切なアーキテクチャを有するコンピュータにアップロードされるか、該コンピュータにより実行される。好ましくは、コンピュータは、１以上の中央処理ユニット（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）、及び入力／出力（Ｉ／Ｏ）インタフェースのようなハードウェアを有するコンピュータプラットフォームで実現される。コンピュータプラットフォームは、オペレーティングシステム及びマイクロ命令コードを含む場合がある。本実施の形態で記載される様々なプロセス及び機能は、ＣＰＵにより実行される場合がある、マイクロ命令コードの一部又はアプリケーションプログラムの一部の何れか、或いはその組み合わせである場合がある。さらに、様々な他の周辺装置は、更なるデータストレージユニット及びプリンティングユニットのようなコンピュータプラットフォームに接続される場合がある。
【００５４】
添付図面に示されるシステムコンポーネントの幾つか及び方法は、ソフトウェアで実現されるのが好ましいため、システムコンポーネント又はプロセス機能ブロック間の実際の接続は、本発明がプログラムされるやり方に依存して異なる場合があることを理解されたい。本実施の形態での教示が与えられると、当業者であれば、本発明のこれら及び類似の実現又は構成を考えることができるであろう。
【００５５】
例示的な実施の形態が添付図面を参照して記載されたが、本発明はそれら正確な実施の形態に限定されるものではなく、様々な変形及び変更が本発明の範囲又は精神から逸脱することなしに当業者により行われる場合があることを理解されたい。全ての係る変形及び変更は、特許請求の範囲に述べられる本発明の範囲に含まれることが意図される。
【図面の簡単な説明】
【００５６】
【図１】本発明の実施の形態に係る、本発明が適用される場合がある例示的なビデオ符号化／復号化の環境のブロック図である。
【図２】本発明の実施の形態に係る、ラプターコードをデコードする例示的な方法のフローチャートである。
【図１】
2009526476.tif 000025
【図２】
2009526476.tif 000026
【国際調査報告】
2009526476.tif 000027
2009526476.tif 000028
2009526476.tif 000029