(57)【要約】  本発明は、可変長コードワード・シーケンスを関連のコードワード・テーブルに基づいてソース・デコーディングする方法に関する。その特徴は、ａ）前記コードワード・テーブルに関連するツリーであって、複数のブランチを含むツリーパスT＿PTHを含むツリーを作成するステップと、ｂ）受信したシーケンスSQrをデコーディングするステップとを含み、該デコーディングステップが、１）前記ツリーのノードから、該ノードから派生する後続ブランチの第１の累積メトリックCM＿LPTHを計算することによって、最良のツリーパスBT＿PTHを拡張するサブステップと、２）前記最良のツリーパスに対応するコードワードを選択し、第２の累積メトリックCM＿STCKを含むパスPTH内の対応するデータを、記憶するサブステップと、３）記憶したパスを、その第２の累積メトリックに応じて再並び替えするサブステップと、４）トップ・パスTOP＿PTHに関してプライオリ条件を判断し、満たされた場合には、該トップ・パスを出力し、それ以外の場合は、上記拡張サブステップに戻るサブステップとを含む。
2005510113.tif 000002
【特許請求の範囲】
【請求項１】
可変長コードワード・シーケンスを関連のコードワード・テーブルに基づいてソース・デコーディングする方法であって、
前記コードワード・テーブルに関連するツリーであって、複数のブランチを含むツリーパスを含むツリーを作成するステップと、
受信したシーケンスをデコーディングするステップとを含み、
該デコーディングステップは、
前記ツリーのノードから、該ノードから派生する後続ブランチの第１の累積メトリックを計算することによって、最良のツリーパスを拡張する拡張サブステップと、
前記最良のツリーパスに対応するコードワードを選択し、第２の累積メトリックを含むパス内の対応するデータを、記憶する選択サブステップと、
記憶したパスを、その第２の累積メトリックに応じて再並び替えする再並び替えサブステップと、
トップ・パスに関してプライオリ条件を判断し、満たされた場合には、該トップ・パスを出力し、それ以外の場合は、上記拡張サブステップに戻るサブステップとを含むことを特徴とする、方法。
【請求項２】
各コードワードは、長さを有し、前記ツリーは、前記コードワード・テーブルで定義された最大コードワード長に等しい階層を含む、請求項１記載の方法。
【請求項３】
前記拡張サブステップは、停止メトリック計算条件の判断を含み、条件が満たされた場合、前記拡張が停止され、前記再並び替えサブステップが続いて実行される、請求項１記載の方法。
【請求項４】
前記停止メトリック計算条件判断は、前記最良のツリーパスの第１の累積メトリックと、前記最悪の記憶されたパスの第２の累積メトリックとの比較に基づく、請求項３記載の方法。
【請求項５】
プライオリ条件がシンボル基準に基づく場合、上記選択サブステップは、デコーディングステップ内で全ての以前に選択されたコードワード長とは異なる長さを有するコードワードのみを選択するように構成される、請求項１記載の方法。
【請求項６】
前記デコーディングステップは、更に、プライオリ条件を判断する前に前記トップ・パスに関して終了条件を判断するサブステップを含み、該トップ・パスが終了条件を満たした場合、プライオリ条件の判断のサブステップが実行され、その他の場合、停止デコーディング条件を判断するサブステップが実行され、該停止デコーディング条件が満たされない場合、前記拡張サブステップが生ずる、請求項１記載の方法。
【請求項７】
前記停止デコーディング条件は、デコーディングステップカウンタの増分、及び、該カウンタと設定閾値との比較に基づき、該カウンタが該閾値を上回った場合、デコーディングが停止される、請求項６記載の方法。
【請求項８】
前記パス内の対応するデータは、更に、累積ビット数を含み、前記終了条件は、トップ・パスの累積ビット数と、受信したコードワード・シーケンスの長さとの比較に基づく、請求項６記載の方法。
【請求項９】
前記コードワード・テーブルは、エスケープ・モード・コードワードを含む、請求項１記載の方法。
【請求項１０】
デコーダ用のコンピュータープログラム製品であって、該デコーダにロードされる時、該デコーダに請求項１乃至９の何れに記載の方法を実行させる、コンピュータープログラム製品。
【請求項１１】
コンピューター用のコンピュータープログラム製品であって、該コンピューターにロードされる時、該コンピューターに請求項１乃至９の何れに記載の方法を実行させる、コンピュータープログラム製品。
【請求項１２】
可変長コードワード・シーケンスを関連のコードワード・テーブルに基づいてソース・デコーディングするデコーダであって、
前記コードワード・テーブルに関連するツリーであって、複数のブランチを含むツリーパスを含むツリーを作成するツリー生成手段と、
受信したシーケンスをデコーディングするシーケンス・デコーディング手段とを含み、
該シーケンス・デコーディング手段は、
前記ツリーのノードから、該ノードから派生する後続ブランチの第１の累積メトリックを計算することによって、最良のツリーパスを拡張する最良ツリーパス拡張手段と、
前記最良のツリーパスに対応するコードワードを選択し、第２の累積メトリックを含むパス内の対応するデータを、記憶するコードワード選択手段と、
記憶したパスを、その第２の累積メトリックに応じて再並び替えするパス再並び替え手段と、
トップ・パスに関してプライオリ条件を判断し、満たされた場合には、該トップ・パスを出力するプライオリ条件判断手段とを含む、デコーダ。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
＜発明の分野＞
本発明は、可変長コードワード（符合語）・シーケンス（系列）を関連のコードワード・テーブルに基づいてソース・デコーディングする方法に関する。本発明は、また、この方法を利用するデコーダに関する。
【０００２】
かかる方法は、例えばビデオ若しくはオーディオ通信システムのような、可変長コードのようなものを使用する如何なるシステムにおいても使用できる。
【０００３】
＜発明の背景＞
ビデオ通信システムは、典型的には、ソース・エンコーディング・システム、チャンネル及びソース・デコーディング・システムを含む。ソース・エンコーディング・システムは、可変長コードワード・シーケンスを生成し、それらをチャンネルを介して送信し、ソース・デコーディング・システムは、共有コードによりそれらをデコードする。
【０００４】
チャンネルに乱れが存在するので、受信したコードワード・シーケンスは、誤りを含み、従って、複数の考えられ得るデコードされたコードワード・シーケンスが存在しうる。
【０００５】
この際、ソース・デコーダーは、これらの考えられ得るシーケンスに関連付けられた全てのメトリック間での最良なメトリックに基づいて、考えられ得るシーケンスのうちの１つを選択することで、受信したシーケンスの推定器として機能する。最良のメトリックの算出は、通常、メトリック導出と呼ばれる。かかる推定は、通常、Viterbi（ヴィタビ）アルゴリズム若しくはスタック（stack）アルゴリズムに基づき、当該スタックアルゴリズムは、参考文献“Buttigieg-Variable-length  error-correcting  codes-PhD  thesis,  University  of  Manchester,  United  Kingdom,  1995”に開示されている。
【０００６】
かかる推定の一の大きな問題は、当該推定が、各デコーディングステップで各コードワードに関連するメトリックの算出を要することである。従って、最良の部分的にデコードされたコードワードのシーケンスは、全てのコードワードにより拡張され、即ち、全てのコードワードの全てのメトリックが計算され、次いで、考慮時点での新たな最良のコードワードは、そのメトリックの関数として選択され、再び、全てのコードワードにより拡張され、受信コードワード・シーケンス長に多数の拡張コードワードが等しくなるようにする。この算出により、Viterbi若しくはスタックアルゴリズムで使用されるメトリック導出が、中央処理ユニット（cpu）要求の観点からデコーディングの最もコストの嵩む部分となる。
【０００７】
＜発明の目的及び概要＞
従って、本発明の目的は、理にかなったcpuコスト、時間及び複雑性で効率的なデコーディングを実現する、可変長コードワード・シーケンスを関連のコードワード・テーブルに基づいてソース・デコーディングする方法及びデコーダを提供することである。
【０００８】
この目的のため、請求項１に記載されるような可変長コードワード・シーケンスをデコーディングする方法が提供される。
【０００９】
また、請求項１に記載されるような可変長コードワード・シーケンスをデコーディングするデコーダが提供される。
【００１０】
更なる説明で詳細が分かるが、かかる方法は、コードワードが、そのメトリック値の昇順で選択されるという大きな利点を有する。従って、有用なコードワードのみを探すことによって、提案の方法は、他のコードワードがもはや考慮されないので、cpuコスト、時間及び複雑性の観点で非常に効率的である。
【００１１】
本発明のその他の目的は、デコーディングを複雑性及び迅速性の観点から更に低減することである。
【００１２】
従って、第１の好ましい実施例では、各コードワードは長さを有し、ツリーは、コードワード・テーブルに定義された最大のコードワード長に等しい数の階層を含む。ツリー内の階層数が理にかなった値を有するので、多くの計算を要せず結果が速やかに導かれる。
【００１３】
第２の好ましい実施例では、前記拡張サブステップは、停止メトリック計算条件の判断を含み、条件が満たされた場合、前記拡張が停止され、前記再並び替えサブステップが続いて実行され、該停止メトリック計算条件は、前記最良のツリーパスの第１の累積メトリックと、前記最悪の記憶されたパスの第２の累積メトリックとの比較に基づく。従って、有用な最良のツリーパスのみの拡張が許容され、その結果、有用な関連のコードワードのみの検査が可能となる。
【００１４】
システムらに、第３の好ましい実施例では、プライオリ条件がシンボル基準に基づく場合、上記選択サブステップは、デコーディングステップ内で全ての以前に選択されたコードワード長とは異なる長さを有するコードワードのみを選択するように構成される。従って、既に選択されたより悪いコードワードを検査するのが防止される。
【００１５】
第４の好ましい実施例では、前記デコーディングステップは、更に、プライオリ条件を判断する前に前記トップ・パスに関して終了条件を判断するサブステップを含み、該トップ・パスが終了条件を満たした場合、プライオリ条件の判断のサブステップが実行され、その他の場合、停止デコーディング条件を判断するサブステップが実行され、該停止デコーディング条件が満たされない場合、前記拡張サブステップが生ずる。終了条件は、受信したシーケンスに等しい特性を有する考えらうる結果に辿り着いたか否かの判断を可能とする。
【００１６】
好ましい実施例では、これらの特性は、受信したコードワード・シーケンスの長さであり、受信したコードワード・シーケンス内のビット数である。従って、前記パス内の対応するデータは、更に、累積ビット数を含み、前記終了条件は、トップ・パスの累積ビット数と、受信したコードワード・シーケンスの長さとの比較に基づく。
【００１７】
その他の好ましい実施例では、前記停止デコーディング条件は、デコーディングステップカウンタの増分、及び、該カウンタと設定閾値との比較に基づき、該カウンタが該閾値を上回った場合、デコーディングが停止される。従って、存在しないか若しくは見つけるのに理不尽な時間が掛かりうる、デコードされたシーケンスに対する結果を、探すために多くの時間を費やすのが防止される。
【００１８】
本発明の更なる目的、特徴及び利点は、添付図面を参照して以下の詳細な説明を読みことで明らかになるだろう。
【００１９】
＜発明の詳細な説明＞
次の説明において、公知の機能や構成は、不要な詳細により本発明を不明瞭にするので説明しない。
【００２０】
本発明は、通常ハフマン符号と称される関連のコードワード・テーブルに基づいて、可変長コードワード・シーケンスをソース・デコーディングする方法に関する。本方法は、特に、ビデオ通信システムVS内の図１に示すようなVLCと称される可変長コードデコーダー内で使用される。その他、ビデオ通信システムVSは、VLCエンコーダVLC-ENC、チャンネルCH、及び、VLCデコーダVLC-DECを含むソース・デコーディング・システムS-DECを含む。ソース・エンコーディング・システムS-ENCは、VLCエンコーダを介してコードワード・シーケンスSQにシンボル・シーケンスをエンコードし、ソース・デコーディング・システムS-DECにそれを複数のビット時間中にチャンネルCHを介して送信し、ソース・デコーディング・システムS-DECは、コードワード・テーブルに定義された共有コードCにより、それをVLCデコーダVLC-DECを介してデコードする。送信はビット毎に行われる。
【００２１】
コードワード・シーケンスSQは、可変長L_SQを有する。これは、送られるコードワード・シーケンスSQsが異なる長さを有してよいことを意味する。従って、ソース・デコーディング・システムS-DECにより受信される受信コードワード・シーケンスSQrは、異なる長さを有しうる。コードワード・シーケンスSQは、共有コードCにより定義された複数のシンボルSを含む。尚、一のシンボルSは、少なくとも１ビットを含む。
【００２２】
コードワード・テーブルの一例を図２に示す。共有コードCは、次のように定義される。コードワードCWDiは、長さLTHiを有し、シンボルSに関連付けられる。コードワードCWDiの値は、関連のシンボルSiにより取られてよい値を表わす。また、出現確率Piは、各コードワードCWDiに関連付けられる。
【００２３】
従って、共有コードCにより、送られるコードワード・シーケンスSQsは、次のように定義される。例えば、SQs＝100  0  110．このコードワード・シーケンスは、3つのシンボルS3,S1,S4を含み、7ビットを含む。この際、当業者に広く知られている、例えばBPSK変調のような、ソース・エンコーディング・システムS-ENCでの変調ステップ後、該シーケンスは、SQs’＝1；-1；-1；-1；1；1；-1となる。この際、チャンネルCHでのノイズにより、ソース・デコーディング・システムS-DECにより受信されるシーケンスは、例えば、SQr＝0.8-0.9-0.8-1.1  1.2-1.3。
【００２４】
これから、受信したSQrは、送られたSQsを回復するようにデコードされなければならない。即ち、我々は、送られたSQsであったシンボルSiを回復する必要がある。誤りをもたらす乱れにより、我々は、多くの考えられ得るコードワード・シーケンスSQdがデコードされることに気が付く。デコーディングは、VLCデコーダVLC-DECにより行われ、送られたSQsの推定に基づく。
【００２５】
VLCデコーダVLC-DECは、ツリーパスリストL_PTHと、スタックSTCKとを含み、
ツリーパスリストL_PTHは、ツリーパスT_PTHのセットを含み、各ツリーパスは、第1の累積メトリックCM_LPTH及びノードセットNSETを含み、ツリーパスリストは、前記累積メトリックにより最良のツリーパスである上部ツリーパスを含み、
スタックSTCKは、パスPTHのセットとシンボルSiのセットとを含み、各パスは、データを含み、該データは、第2の累積メトリックCM_STCK及びビットの累積数を含む。
【００２６】
ツリーパスの第1の累積メトリックCM_LPTHは、ツリーパスT_PTHを含むブランチ  (枝)Bのブランチメトリックに後述する初期累積メトリックを足した合計である。
【００２７】
パスの第2の累積メトリックCM_STCKは、パスPTHを含むシンボルSiの合計である。上述の如くシンボルSiは、コードワードCDWiに関連付けられている。
【００２８】
正確にデコードされたコードワード・シーケンスSQdを見つけるため、デコーディング方法は、考慮されるコードワード・テーブルのツリー表現、及び、メトリック導出アルゴリズムを用いる。ツリーは、後述の如く、ノードNとブランチBからなる。メトリックをツリーの各ブランチBに関連付けられることを考慮して、デコーディング方法は、考慮時刻ｔで最も小さいメトリックのコードワードCDWiを決定するために使用できるツリー内で最も可能性のあるツリーパスを探す。後で分かるように、提案方法の1つの大きな利点は、コードワードが、そのメトリック値の昇順に選択されることである。
【００２９】
１）メトリック導出アルゴリズム
メトリック導出アルゴリズムは、ビット単位のブランチメトリック反復形成及び上述のツリー表現を用いる。
【００３０】
[ビット単位のブランチメトリック反復形成]
メトリック計算は、マッセイのメトリック（参考文献、J.L.Massey“Variable-Length  codes  and  the  Fano  metric”  IEEE  Transactions  on  Information  Theory,  IT-18(1):196-198,January  1972）に従ってなされ、これは、当業者によく知られているような、コードワードの出現確率に依存する係数、及び、受信シーケンスｙ、ｘが送信シーケンスである尤度を近似する補正係数logP0(y)  による重み付けが後続する、部分的な受信シーケンスSQrと変調後(加法性白色ガウスノイズの場合)の部分的な送信シーケンスSQsとの間のユークリッド距離の算出に等価な、MAP基準と呼ばれる近似“Maximum  A  Posteriori”基準である。
【００３１】
メトリックMの公式は、以下のとおりである。
【００３２】
【数１】
2005510113.tif 000003
nb_bitは、シーケンスSQ内のビット数である。それ故に、ビット毎のブランチメトリック形成は次のように書ける。
【００３３】
【数２】
2005510113.tif 000004
ここで、m(CDWi[k],y[t+k])＝logP（y[t+k]|CDWi[k]）−logP（ｘ[t+k]＝CDWi[k]|x[t:t+k-1]）＋logP0（y[t+k]）は、コードワードCDWiに対応するツリーパスのｎ番目のブランチに関連するブランチメトリックである。CDWi[k]は、コードワードCDWiのｋ番目のビットである。
【００３４】
項logP（y[t+k]|CDWi[k]）は、距離を表わし、項logP（ｘ[t+k]＝CDWi[k]|x[t:t+k-1]）は、コードワードCDWiのｋ番目のビットに関連付けられるプライオリ確率であり、logP0（y[t+k]）は、補正係数である。
【００３５】
[コードワード・テーブルのツリー表現]
かかるツリーは、複数のノードNと、複数のブランチBと、複数のツリーパスT_PTHとを含む。複数のノードNは、考えられ得るコードワードCDWiに対応する。メトリックは、ブランチBに関連付けられる。ブランチBは、2つのノードNからなり、即ち、一のノードNから、一若しくは2のブランチ、“左”ブランチ及び“右”ブランチが生成できる。ブランチは、関連するビット値０又は１を有する。ツリーパスT_PTHは、デコードされるコードワード・シーケンスSQdを表わす。ツリーパスT_PTHは、複数のブランチBを含み、初期のノードN00から考えられ得るシンボルSiに行く。
【００３６】
尚、ツリーは、異なる階層(レベル)を有し、第1の階層は、階層０であり、ツリーは、初期のノードN00を含む。
【００３７】
[メトリックの計算]
メトリック導出アルゴリズムにおいて、我々は、初期ノードN00から出発し、シンボルSに至るまでツリーパスに従って、ツリー内のツリーパスを調べる。事前に調べられたツリーパスのリストは、記憶装置に保持される。リスト入力は、調べられるツリーパスの最後のノードを、その第1の累積メトリック、即ちそのツリーパスを含むブランチのブランチメトリックの合計と共に含む。各デコーディングステップは、当該最後のノード(構造により１つ若しくは２つ)の後続ブランチのブランチメトリックを計算し、次いで、それを上部ツリーパスの第1の累積メトリックに加えて後続（後任）を形成することで、ツリーパスリスト内の上部ツリーパス（最小の累積メトリックを有する最良のツリーパス）の拡張をもたらす。その上部ツリーパスは、ツリーパスリストから消去され、その後任が挿入される。リスト内の上部ツリーパスが、完全にコードワードCDWiに対応する一致する時、このコードワードは、主要な最良のコードワードのリストCWD_LISTに加えられる。この処理は、停止条件が確認されるまで繰り返される。
【００３８】
従って、メトリック導出アルゴリズムは、図4に示すように、次のようなステップを実行する。
【００３９】
第1ステップCREAT_TREE）では、我々は、コードワード・テーブルに関連するツリーを作成する。我々は、参照文献“L.Guivarch,  Carlach,  Siohan-Joint  Source  Channel  soft  decoding  of  Huffmann  codes  with  turbo-codes-In  Proceedings  of  the  Data  compression  Conference  DCC’00  pages  83-91,  Snowbird,  Utah,  USA,  March  2000”に開示されるように、各ブランチBに関連付けてプライオリ確率を計算するノードN間の関係を定義することで、テーブルを作成する。尚、好ましい実施例では、ツリーの階層の数は、コードワード・テーブルに定義された最大コードワード長LTHiに等しく、ここでは４である。
【００４０】
第２ステップINIT_L_PTH）では、我々は、メトリック０の初期ノードN00を上部ツリーパスL_PTH内に置くことで、ツリーパスリストL_PTHを初期化する。
【００４１】
第３ステップEXT_BEST_TPTH）では、我々は、ツリーパスリストL_PTH内の最良のツリーパスBT_PTHの後続のブランチのメトリックを算出する。我々は、ツリーパスリストL_PTHから最良のツリーパスBT_PTHを削除し、拡張されたツリーパスリストL_PTHをツリーパスリスト内に入れる。
【００４２】
第４ステップSEL_BEST_TPTH）では、我々は、新しい最良のツリーパスBT_PTH、即ち、最小の第１の累積メトリックを有するツリーパスリストL_PTH内のツリーパスを選択する。
【００４３】
第５ステップSTOP_METRIC_COND）では、我々は、幾つかの停止メトリック条件をテストする。停止条件の１つが確認された場合、我々は、停止し、それ以外の場合、第６ステップに進む。
【００４４】
幾つかの停止条件が定義できる。好ましい実施例では、次の停止条件が確認される。
−各ノードNの検査が完了した場合、停止する。
−十分な数のコードワードCWDiが選択された場合、停止する。
−最良のツリーパスに対応する第１の累積メトリックCM_LPTHが、ここでは最悪の第２の累積メトリックCM_STCKである、所定閾値を超えた場合、停止する。最後の条件が、好ましくは使用される。
【００４５】
第６ステップ）では、我々は、最良のツリーパスBT_PTHが完全なコードワードCWDiに対応するか否かをテストする。対応する（ＹＥＳ）場合、我々は、第７ステップに進み、その他の場合、第３ステップに戻る。
【００４６】
第７ステップ）では、我々は、コードワードリストCWD_LSTに、最良のツリーパスBT_PTHに対応する見出したコードワードCWDiを追加し、第４ステップに戻る。
【００４７】
尚、見出されたコードワードCWDiの幾つかが推定方法により使用されないことは、特に、同一長さ（コードワード内のビット数）の幾つかのコードワードCWDiが選択された場合、即ち、幾つかのプライオリ条件が後述するような記号基準に基づくときに、ありえる。
【００４８】
II）デコーディング若しくはVLCアルゴリズム
ここでは、図５ａ及び図５ｂに示すように、デコーディング方法、即ち所謂TREE_VLC−STACKアルゴリズムが、次のステップを実行することによってこのメトリック導出アルゴリズムをどのように使用するかがわかる。
【００４９】
第1ステップCREAT_TREE）では、我々は、上述のようなコードワード・テーブルに関連するツリーを作成する。ツリーは図３に示される。ここでは、ツリーの階層数は４である。
【００５０】
関連したツリーを作成した後、第２サブステップINIT_STCK）では、我々は、スタックSTCKの上部入口にゼロメトリックを置き、他の入口に無限大のメトリックを置くことによって、スタックSTCKを初期化する。
【００５１】
第３サブステップINIT_LPTH）では、我々は、スタックSTCKのトップ・パスの第２の累積メトリックCM_STCKである初期化累積メトリックを初期ノードN00に置くことにより、ツリーパスリストL_PTHを初期化する。
【００５２】
第４サブステップINIT_LPTH）では、我々は、最良のツリーパスBT_PTHからツリーパスT_PTHを拡張し、後続するブランチBの第１の累積メトリックCM_LPTHを計算する。次いで、我々は、ツリーパスリストL_PTH内の最良のツリーパスを削除し、ツリーパスリストL_PTH内に拡張したツリーパスを挿入する。
【００５３】
第５サブステップSEL_BEST_TPTH）では、我々は、新たな最良のツリーパスBT_PTH、即ち、ツリーパスリストL_PTH内で、最良の第１の累積メトリックCM_LPTH、即ち最小の累積メトリックを有するツリーパスを選択する。
【００５４】
第６サブステップSEL_CWD）では、ステップ３による最後の通過から、少なくとも１つの選択された最良のツリーパスBT_PTHがコードワードであった場合、ステップ１０に進み、そうでない場合、ステップ７に行く。
【００５５】
第７サブステップ＝CWD)では、我々は、最良のツリーパスBT_PTHが完全なコードワードに対応するか否かを判断する。従って、最良のツリーパスBT_PTHが完全なコードワードに対応する場合、我々は、ツリーパスリストL_PTHから最良のツリーパスBT_PTHを削除し、次いで、ステップ８に行き、その他の場合は、ステップ４に戻る。
【００５６】
尚、プライオリ基準がシンボル基準に基づく場合、我々は、好ましくは、この対応する完全なコードワードCWDiが、ステップ３の最後の通過から以前に選択されていたコードワード長の全てとは異なる長さLTHiを有するか否かを判断する。
【００５７】
それが同じ長さを有する場合、我々は、ツリーパスリストL_PTHから最良のツリーパスBT_PTHを削除し、ステップ５に戻る。これは、同一の長さを有し他のコードワードよりも悪いものが次々に選択されいるので、このコードワードCWDiは検査される価値が無いことを意味する。従って、この判断は、時間を得る利点がある。
【００５８】
それが異なる長さを有する場合、我々は、ツリーパスBT_PTHから最良のツリーパスBT_PTHを消去し、ステップ８に行く。
【００５９】
第８サブステップDEL_TOPTH_STCK）では、我々は、トップ・パスTOP_PTHをスタックSTCKから消去する。
【００６０】
第９サブステップINS_PTH_STCK）では、我々は、ステップ７で得られるコードワードCWDiを選択することによって、最良の拡張したパスから形成される新しいパスPTHを、スタックSTCK内に挿入する。
【００６１】
第１０サブステップCM_LPTH>CM_STCK）では、我々は、停止メトリック計算条件をテストする。従って、我々は、最良のツリーパスの第１の累積メトリックと、最悪の記憶されたパスの累積メトリックとを比較する。従って、ツリーパスリストL_PTH内の最良のツリーパスBT_PTHの第１の累積メトリックCM_LPTHが、スタックSTCK内の最悪パスPTHの第２の累積メトリックCM_STCKを超える場合、ステップ１４に行く。これは、最良のツリーパスBT_PTHの第１の累積メトリックが、最悪パスPTHの第２の累積メトリックよりも悪いこと意味する。その他の場合、ステップ１１に行く。
【００６２】
第１１サブステップ＝CWD）では、ツリーパスリストL_PTH内の最良のツリーパスBT_PTHが完全なコードワードCWDiに対応する場合、我々は、ツリーパスリストL_PTHから最良のツリーパスBT_PTHを消去し、ステップ１２に続く。その他の場合、ステップ４に戻る。即ち、我々は、対応するコードワードCWDiを見つけ続ける。
【００６３】
第１２サブステップDEL_WORSPTH_STK）では、我々は、スタックSTCK内の最悪のパスPTH、即ち最も大きな累積メトリックを有するパスを消去する。
【００６４】
第１３サブステップINS_PTH_STCK）では、我々は、ステップ１１で得られる選択されたコードワードCWDiにより、スタックSTCK内に、拡張した最良のパスから形成される新たなパスPTHを入れ、ステップ５に戻る。
【００６５】
第１４サブステップREORD_STCKでは、第２の累積メトリック値CM_STCKに従って最良から最悪にスタックSTCKを並び替えする。
【００６６】
第１５サブステップCBITS＝L_SQ）では、我々は、トップ・パスで終了条件をテストする。従って、トップ・パスのビットの累積数と、受信したコードワード・シーケンスの長さを比較する。トップ・パスのビットの累積数CBITSが受信したコードワード・シーケンスSQrの長さL_SQと等しい場合、我々は、ステップ１６に続く。その他の場合はステップ１８に行く。
【００６７】
第１６サブステップAP_COND）では、我々は、スタックSTCK内のトップ・パスTOP_PTHが、放出されたシーケンスに関するプライオリ条件を満たすかどうかを判断する。
【００６８】
プライオリ条件は、好ましくは、シーケンス内のシンボルＳiの数若しくはブロックの数である。この例では、プライオリ条件は、シンボルＳiの数である。それがプライオリ条件を満たす場合、停止され、我々は、受信したシーケンスSQsに対するデコードされた解である、TOP_PTHを出力する。
【００６９】
第１７サブステップDEL_TOPTH_STCK）では、我々は、トップ・パスTOP_PTHをスタックSTCKから消去し、スタックSTCKのトップ・パスの入口に無限大のメトリックを入れ、ステップ１４に行く。
【００７０】
第１８サブステップSTOP_COND）では、我々は、停止デコーディング条件を判断する。従って、我々は、デコーディングステップ数に対応するカウンタCPTをインクリメントし、我々は、当該カウンタCPTを設定閾値THと比較する。当該カウンタCPTが設定閾値THを超える場合、デコーディングが停止される。それは、解が見つけられなかったことを意味する。例えば、閾値THは、送信されるシーケンスSQs内のビット数に設定される。その他の場合、我々は、ステップ３に戻る。
【００７１】
III)具体例
第１ステップ：ツリーの生成
かかるツリーは、図３に示される。この図では、図２のコードワード・テーブルに関連したツリーは、６つのシンボルS1からS6を有する。例えば、それは、N00-N11-N20-S3を有し、これは、シンボルS３を形成する３つの中間ノードN00-N11-N20からなり、当該ノードは、３つのブランチB１（N00-N11），B２（N11-N20），B２（N20，N30）と等価である。３つのブランチは、関連するビット値“1”，“0”，“0”をそれぞれ有する。
【００７２】
尚、我々は、ツリーのｋ＝階層の添え字付きでノードを表わす。例えば、N２０は、このノードがツリーの第２層にあることを意味する。
【００７３】
ステップ２：スタックSTCKの初期化。ここでは、スタックは、２つのパスPTH：PTH1、PTH2を有する。
【００７４】
【表１】
2005510113.tif 000005
ステップ３：ツリーパスリストL_PTHの初期化。
【００７５】
【表２】
2005510113.tif 000006
ステップ４：拡張。ここで、我々は、２つの拡張したツリーパス：T_PTH10、T_PTH11を有する。
【００７６】
【表３】
2005510113.tif 000007
ステップ５：本例では、最良のツリーパスは、ツリーパスBT_PTH＝T_PTH11である。
【００７７】
ステップ６：前に如何なるコードワードも選択されていない。従って、ステップ７に行く。
【００７８】
ステップ７：ここでは、最良のツリーパスBT_PTH＝T_PTH11（N00-N11）は、如何なるコードワードにも一致しないので、ステップ４に戻る。
【００７９】
ステップ４：我々は、２つの拡張したツリーパスT_PTH20、T_PTH21を有する。
【００８０】
【表４】
2005510113.tif 000008
ステップ５：新たな最良のツリーパスは、BT_PTH＝T_PTH20。
【００８１】
ステップ６：前に如何なるコードワードも選択されていない。従って、ステップ７に行く。
【００８２】
ステップ７：ここでは、ここでは、最良のツリーパスBT_PTH＝T_PTH20（N00-N11-N20）は、如何なるコードワードにも一致しないので、ステップ４に戻る。
【００８３】
ステップ４：
【表５】
2005510113.tif 000009
【００８４】
ステップ５：我々は、第１の累積メトリックM11＋M20＋M30を持つ最良のツリーパスBT_PTH＝T_PTH30に到達する。
【００８５】
ステップ６：ステップ３を最後に通過して以来、如何なる選択されたツリーパスもコードワードでなく、ステップ７に行く。
【００８６】
ステップ７：最良のツリーパスBT_PTH＝T_PTH30は、完全なコードワード１００に対応するので、我々は、ツリーパスリストから最良のツリーパスBT_PTH＝T_PTH30を消去する。
【００８７】
ステップ８：スタックSTCK内のトップ・パスTOP_PTH＝PTH1を消去する。
【００８８】
ステップ９：我々は、ステップ７で得られたコードワードCWDiを選択することにより新しいパスPTHを入れる。当該コードワードCWDiは、３ビット100を含み、シンボルS３に一致する。従って、新しいパスPTH1は、次のデータ、即ち、第２の累積メトリックM11＋M20＋M30、３ビットの値、及びシンボルS３を含む。
【００８９】
【表６】
2005510113.tif 000010
ステップ５に戻る。
【００９０】
【表７】
2005510113.tif 000011
ステップ５：我々は、新しい最良のツリーパスBT_PTH＝T_PTH10を選択する。
【００９１】
ステップ６：選択された最良のツリーパスBT_PTHの少なくとも１つがコードワードであったので、ステップ１０へ行く。
【００９２】
ステップ１０：最良のツリーパスBT_PTH＝T_PTH10の第１の累積メトリックは、ここでは無限大である、スタックからの最悪なパスの第２の累積メトリックより小さい。
【００９３】
ステップ１１：新しい最良のツリーパスBT_PTH＝T_PTH10は、新しいコードワード０及びシンボルS１に対応するので、我々は、ツリーパスリストから最良のツリーパスBT_PTH＝T_PTH10を消去して、ステップ１２に行く。
【００９４】
ステップ１２：我々は、スタックから最悪のパスを消去する。
【００９５】
ステップ１３：我々は、ステップ１１で得られたコードワードをサンたくすることにより、新しいパスPTHをスタックSTCK内に挿入する。従って、スタックSTCK内には、我々は、以下のように、第２の累積メトリックM10及び１ビット及びシンボルS１を備えるパスPTH2を有する。
【００９６】
【表８】
2005510113.tif 000012
ステップ５に戻る。我々は、新しい最良のツリーパスBT_PTH＝T_PTH31を選択する。
【００９７】
ステップ６：最良のツリーパスBT_PTH＝T_PTH31の第１の累積メトリックは、スタックPTH2からの最悪パスの第2の累積メトリックよりも大きいので、即ち、MP2＜M11＋M20＋M31であるので、ステップ14に行く。
【００９８】
ステップ１４：我々は、スタックを再並び替えする。ここでは、パスPTH1は、パスPTH2よりも良い。
【００９９】
ステップ１５：ここでは、トップ・パスの累積ビットCBITSが、受信したシーケンスSQr長のビットと同一でない。従って、ステップ18に進む。
【０１００】
ステップ１８：CPT=１、ステップ３に戻る。
【０１０１】
ステップ３：ツリーパスリストL_PTHは全体的に消される。新しい上部ツリーパスT_PTHは、ノードN00を備えるMP1である。
【０１０２】
【表９】
2005510113.tif 000013
ステップ４：我々は、ノードN00からブランチを伸ばす。
【０１０３】
【表１０】
2005510113.tif 000014
ステップ5、ステップ6及びステップ７：T_PH10が最良のツリーパスBT_PTHであり、コードワードが選択されておらず、T_PH10は、シンボルS１に対応する。我々は、ツリーパスリスト内の最良のツリーパスBT_PTH＝T_PTH1を消去する。
【０１０４】
ステップ８：我々は、スタックSTCK  PTH1内のトップ・パスを消去する。
【０１０５】
ステップ９：次いで、我々は、スタックSTCK内で以下を得る。
【０１０６】
【表１１】
2005510113.tif 000015
ステップ５：我々は、新しい最良のツリーパスBT_PTH＝T_PTH11を選択する。
【０１０７】
ステップ６：前に選択されたコードワードが存在しないので、ステップ10に行く。
【０１０８】
ステップ１０：最良のツリーパスBT_PTH＝T_PTH11の第1の累積メトリックがスタックPTH２からの最悪パスの第2の累積メトリックよりも大きいので、即ち、MP2＜MP1＋M11であるので、ステップ14に行く。
【０１０９】
ステップ１４：我々は、スタックを再並び替えする。そのままである、即ち、パスPTH1がパスPTH2より良い。
【０１１０】
ステップ１５：ステップ１８：CPT＝２、ステップ3に戻る。
【０１１１】
ステップ３：ツリーパスリストL_PTHは全体的に消される。新しい上部ツリーパスT_PTHは、ノードN00を備えるMP1である。
【０１１２】
【表１２】
2005510113.tif 000016
ステップ４：拡張
【０１１３】
【表１３】
2005510113.tif 000017
ステップ5、ステップ6：次いで、我々は、新しい最良のツリーパスBT_PTH＝T_PTH11（N00-N11）を用いて続ける。
【０１１４】
ステップ７：それは、如何なるコードワードにも対応しない。ステップ4に戻る。
【０１１５】
ステップ４：拡張
【０１１６】
【表１４】
2005510113.tif 000018
ステップ5、ステップ6及びステップ７：T_PTH21（MP1+M11+M21、N00-N11-N21）は、対応するコードワードのない最良のツリーパスBT_PTHである。ステップ4に戻る。
【０１１７】
拡張
【０１１８】
【表１５】
2005510113.tif 000019
ステップ5、ステップ6及びステップ７：T_PTH32（MP1+M11+M21、N00-N11-N21）は、コードワード１１０、即ちシンボルS4に対応する新しい最良のツリーパスBT_PTHである。我々は、ツリーパスリストL_PTH内の最良のツリーパスBT_PTH＝T_PTH32を消去する。
【０１１９】
ステップ８，９：スタックSTCK内のトップ・パスTOP_PTHを消去し、スタックSTCK内は次のとおりとなる。
【０１２０】
【表１６】
2005510113.tif 000020
【０１２１】
【表１７】
2005510113.tif 000021
ステップ5に戻る：新しい最良のツリーパスBT_PTH＝T_PTH33
ステップ6、ステップ１０：新たな第1の累積メトリックMP1+M11+M21+M33は、MP2であるスタックSTCK内の第2の累積メトリックを超えるので、ステップ14に行く。
【０１２２】
ステップ１４：我々は、スタックを再並び替えする。ここでは、そのままである。
【０１２３】
【表１８】
2005510113.tif 000022
ステップ１５：スタックSTCK内のトップ・パスの累積ビットCBITSは、７である受信したシーケンスL_SQの長さに等しいので、ステップ16に行く。
【０１２４】
ステップ１６：プライオリ条件：シンボルSの数は、３である、放出されたシーケンスSQs内のシンボル数に等しい。従って、我々は、停止し、受信したシーケンスSQr＝0.8-0.9-0.8-1.1  1.2-1.3の解である、トップ・パスTOP_PTHを出力する。
【０１２５】
IV)性能
図６、図7及び図8は、本発明による方法の性能を、他の可変長コードワードのソース・デコーディング方法を比較して示す。次の方法が示されている。
【０１２６】
ハードVLCデコーディング“HARD”（ダイヤ）、
新しいシンボルトレリスアルゴリズム“TRELLIS”（円形）であって、“Joint  Source  Channel  coding  for  variable  length  codes”,Snowbird,  Utah,  USA,March30-April  1  1998  with  the  use  of  formula  [1]  for  the  metric  computationに参照されるDemir及びSayoudアルゴリズムに基づくアルゴリズム、
Buttigiegにより提案され、先行技術（参考文献“Variable-length  error-correcting  codes-PhD  thesis,  University  of  Manchester,  UK,  1995”）として上述したVLCスタックアルゴリズム“VLC-STACK”（上向き三角形）、及び
本発明による方法“TREE-VLC-STACK”（左向き三角形）である。
【０１２７】
ハードVLC方法は、VLCコードのプリフィックス特性を用いてビット毎に受信シーケンスSQrをデコーディングすることを含む。プリフィックス特性は、一のコードワードが他のコードワードの開始になりえないことを意味する。
【０１２８】
他の方法は、ソフトVLCデコーディング方法である。
【０１２９】
図６、図7及び図8のグラフは全て、コードワード・シーケンスSQに対応するパケットで、ノイズ比Eb/N0に対するパケットエラーレートPERの観点から、シミュレーションによる性能を示している。尚、信号対ノイズの算出は当業者には周知である。他言すると、我々は、コスト対性能を算出している。性能は、コードワード・シーケンスが正確にデコードされているかを示し、コストは、コードワード・シーケンスSQのビットを送信するために使用された電力（エネルギ／ノイズ）の量を示す。この際、我々が受け入れるべき誤り及び／又は我々が使用した電力に依存して、最も良い解決策が選ばれる。最適方法及びハード方法は、全ての性能を限度内にとどめる。
【０１３０】
シミュレーション特性は次のとおりである。
−コードワードは、１００のパケットで送信される
−シンボルは、所与のVLCテーブルで生成・VLCエンコードされる。
−チャンネルノイズは、加法性白色ガウスである。
−ソフトデコーディング方法で使用される残存パスの最大数は、１０にセットされる。
【０１３１】
図６は、BauerとHaugenauerにより紹介された２６コードワード・テーブル（参考文献“symbol  by  symbol  MAP  decoding  of  variable  length  codes”  in  Proceedings  of  third  ITG  Conference  on  Source  and  Channel  Coding  CSCC00,  pages  111-116,  Munich,  Germany,  January  2000）を用いたシミュレーション結果を示す。
【０１３２】
図７は、MPEG４標準により定義された２０８テーブル（参考文献：Rob  Koenen  “Overview  of  the  MPEG4  Standard”  ISO/IEC  JTC1/SC29/WG11  N3156,  International  organization  for  standardization,  http://drogo.cselt.stet.it/mpeg/standards/mpeg-r/Mpeg-4.htm,  March  2000）を用いたシミュレーション結果を示す。
【０１３３】
図８は、H.26L標準に関連した最大長１９の１０２３コードワードUVLCテーブル（参考文献：Gisle  Bjontegaad,  “H.26L  Test  Model  Long  Term  Number  6”  draft  0,  ITU,  Telecommunication  Standardization  Sector  Study  Group  16,  http://standard.pictel.com/ftp/video-site/h26L/tml6d0.doc,  march  2001）を用いたシミュレーション結果を示す。
【０１３４】
これらのシミュレーションは、関心の全てのソフトデコーディング方法は、PERの観点から略同一の性能を達成する。従って、選択の基準は、デコーディングの複雑性、速さ及び必要なメモリサイズとなるだろう。
【０１３５】
図９は、他の関心の方法と比較して複雑性の観点からの本発明によるTREE-VLC-STACK方法の性能を示す。Y軸は、秒当たりの動作の数NBOP/SECを示す。X軸は、パケット当たりのビット数NBITS/PACKを示す。
【０１３６】
分かるように、本発明による方法は、デコーディングの複雑性の観点から非常に効率的である。
【０１３７】
更に、図１０に示すように、提案された本発明によるTREE-VLC-STACK方法は、既存のVLC-STACK方法に比して約６倍コストが少ない。
【０１３８】
V）アプリケーション
提案された本発明によるVLCデコーディング方法は、好ましくは、雑音の多いMPEG４フレームをデコーディングするために使用される。
【０１３９】
MPEG-4ビデオ標準（（参考文献：Rob  Koenen  “Overview  of  the  MPEG4  Standard”  ISO/IEC  JTC1/SC29/WG11  N3156,  International  organization  for  standardization,  http://drogo.cselt.stet.it/mpeg/standards/mpeg-r/Mpeg-4.htm,  March  2000、及び、Soares  and  Pereira  “MPEG4:a  flexible  coding  standard  for  the  emerging  mobile  multimedia  applications”  in  proceedings  of  IEEE  International  Symposium  on  Personal  Indoor  and  Mobile  Radio  Communications,  Boston,  USA,  September  1998）では、画像シーンは、関連の対象の合成として構築される。各対象にたいして、形状、動き及びテクスチャーがコードされる。形状及び動きデータに対して、テクスチャーデータは、全体としてVLCエンコードされる。更に、MPEG-4は、MPEG-4データを送るパケット内部のデータを再並び替えするデータ区分モードを定義していた。このようにして、形状及び動きデータは、マーカーによりテクスチャーデータから分離される。提案されるソフトデコーディング技術は、データ区分モードでMPEG-4テクスチャー区分に対して満足できる態様で使用できる。
【０１４０】
テクスチャー・コーディングは、ブロックベースである。即ち、8×８ブロックが、離散コサイン変換（DCT）を用いてエンコードされ、量子化され、イベント（EVENTs）に関連する可変長コーディング及びランレングス・コーディングによりビットにマップされる。イベントは、最後のゼロでない係数指示（LASTが“０”にセットされた場合、このブロック内により多くのゼロでない係数があり、LASTが“１”にセットされた場合、これがこのブロック内最後のゼロでない係数であることを意味する）、第1のコードされた係数RUNに先行する連続のゼロの数、及び、第２のコードされた係数LEVELのゼロでない値、の組み合せである。
【０１４１】
考えられるイベントは、VLCコードにより表現できる。しかし、幾つかの考えられるイベントは、それらを表現するVLCコードを有さない。これらのイベントは、統計的に稀である。これらの稀な組み合せをエンコードするため、MPEG-4標準で広く知られている、エスケープ・モード・コードワードESCを用いたエスケープ・コーディング方法が使用される。これは、3つの種類のエスケープ・モード・コードワードESCからなる。
種類１：“０”が後続するエスケープ・モード・コードワードESC
種類２：“１０”が後続するエスケープ・モード・コードワードESC
種類３：“１１”及び長さ21の固定長コードが後続するエスケープ・モード・コードワードESC。
【０１４２】
これらの3つの種類は、Rob  Koenenによる参考文献“Overview  of  the  MPEG4  Standard”に記載されている。
【０１４３】
エスケープ・モード・コードワードに起因して、ソフトデコーディングアルゴリズムは、MPEG-4テクスチャー区分に直接適用できない。しかし、エスケープ・モード・コードワードの前2つの種類（種類１，２）に対しては、提案する解決策として、我々は、それぞれに添加されるビット“０”及び“１０”を備えるエスケープ・モード・コードワードESCをVLCコードワード・テーブル内に人工的に含ませる。従って、コードワード・テーブルは、エスケープ・モード・コードワードESCを含み、これらのエスケープ・モード・コードワードESCは、他のVLCコードワードと同様に使用される。
【０１４４】
種類３のエスケープ・モードESCに対しては、提案する解決策は次の通りである。第１４ステップREORDER_STCK）で、スタックSTCKを再並び替えするちょうど前に、我々は、種類３のエスケープ・モード・コードワードの問題を考慮する：我々は、後述する如く種類３のエスケープ・モード・コードワードのメトリックを算出する。我々は、このメトリックを、我々が作業しているパスPTH（スタック内の最良のパス）の第２の累積メトリックCM＿STCKに加える。次いで、我々は、それを、スタックSTCK内の最悪のパスPTHの第２の累積メトリックCM＿STCKと比較する。このCM＿STCKよりも良い場合、我々は、スタックSTCK内の最悪のパスPTHを、１１及び次の受信ビットに後続する２１のハード値が後続するエスケープ・モード・コードワードESCによりスタックSTCK内の最良のパスを拡張することによって新しいパスPTHにより置換する。尚、この拡張パスは、関心のトップ・パス＋３０の累積ビット数に等しい累積ビット数CBITS及び上述の累積メトリックにより特徴付けられる。
【０１４５】
何れの場合もステップ１４に行く。
【０１４６】
時刻ｔで固定長コードが後続する種類３のエスケープ・モード・コードワードのメトリックは、次のようになる。
【０１４７】
【数３】
2005510113.tif 000023
提案のVLCデコーディングアルゴリズムで使用されるプライオリ条件に関して、ソフトVLCデコーディングアルゴリズムは、しばしば、シーケンスによりシンボル数のプライオリ・ナレッジ（先見的知識）を使用して、送信シーケンスの推定をより正確なものにする。残念ながら、標準MPEG４では、各テクスチャー区分内に含まされるシンボル数の知識は、MPEG−４から知ることができない（当然、フレームを完全且つ正確にデコーディングすることによるのを除いて）。しかし、ヘッダー及び動き区分をデコーディングすることにより、テクスチャー区分に含まれるブロック数を知ることができる。
【０１４８】
それ故に、MPEG−４標準に対して、本発明による提案されるVLCデコーディングアルゴリズムにおいて、我々は、テクスチャー区分内のブロック数の先見的知識を用いてデコーディングを実行するだろう。
【０１４９】
実際に、１に等しいLASTパラメータに対応するコードワードの数をカウントすることによって所与のコードワードのシーケンスに含まれるブロック数を決定することは簡単である。従って、区分によるブロック数の知識は、正確なブロック数を含むという意味で、確からしいシーケンスを選択するためにシンボル数として使用できる先見的情報である。従って、提案VLCアルゴリズムの第１６ステップでは、我々は、既知の送信シーケンスSQsのブロック数と、デコードされたシーケンスのブロック数を比較する。
【０１５０】
尚、プライオリ条件がブロック基準に基づく場合、我々は、同一のLASTパラメータ値に対応する同一長さの２つのコードワードを選択しないことにより時間を稼げる。
【０１５１】
理解されるべきこととして、本発明は、上述の実施例に限定されず、請求の範囲内に定義した本発明の観点や精神から逸脱することなく変形や修正がなされうる。この点に関して、次の意見を述べて終わる。
【０１５２】
理解されるべきこととして、本発明は、上述のMPEG４アプリケーションに限定されない。本発明は、デコーディングのコストを支援できる可変長コーディングを用いた如何なるアプリケーションに使用できる。典型的には、これは、例えばビデオ、オーディオ若しくはテキスト圧縮に使用できる。
【０１５３】
また、理解されるべきこととして、本発明による方法は、如何なる実現にも限定されない。
【０１５４】
ハードウェア若しくはソフトウェアの単一のアイテムが幾つかの機能を実行できるとして、ハードウェア若しくはソフトウェア又はその双方により本発明による方法の機能を実現する方法は数多くある。ハードウェア若しくはソフトウェア又はその双方のアイテムの一アセンブリが、機能を実行することを除外しない。例えば、ツリーパス拡張ステップ４）は、新しい最良のツリーパスBT＿PTHの選択ステップ５）と組み合せて、本発明によるソース・デコーディングの方法を修正することなく単一の機能を形成できる。
【０１５５】
当該ハードウェア若しくはソフトウェアは、適切にプログラムされた集積回路により若しくは結線された電気回路によるといったように、幾つかの態様で実現できる。集積回路は、コンピューター若しくはデコーダ内に組み込まれてよい。デコーダは、上述の如く、拡張ステップ４）を実行するように適合されたツリーパス拡張手段と、選択ステップ５）を実行するように適合された選択手段とを含み、当該手段は、上述の如くハードウェア若しくはソフトウェアアイテムである。
【０１５６】
集積回路は、指令のセットを含む。従って、例えばコンピュータープログラミングメモリ若しくはデコーダメモリ内に、含まれる指令のセットは、コンピューター若しくはデコーダにVLCデコーディング方法の異なるステップを実行させてよい。
【０１５７】
指令のセットは、ディスクのようなデータ担体を読み出すことによりプログラミングメモリ内にロードされてよい。サービスプロバイダーが、インターネットのような通信ネットワークを介して指令のセットを利用可能として良い。
【０１５８】
請求の範囲内の符合は、クレームを制限するものとして解釈されるべきでない。明らかであるが、“含む”という動詞は、クレームに定義されている以外の要素やステップの存在を除外するものでない。要素やステップの前の冠詞も、複数の要素やステップの存在を除外するものでない。
【図面の簡単な説明】
【０１５９】
【図１】本発明によるエンコーダ及びデコーダを含む通信システムモデルを示す図である。
【図２】図１の可変長コードワード・シーケンス・デコーダに関連するコードワード・テーブルを示す図である。
【図３】図２のコードワード・テーブルに関連するコードツリー表現である。
【図４】図１の可変長コードワード・シーケンス・デコーダで使用されるメトリック派生計算を示す第１の状態図である。
【図５ａ】図１の可変長コードワード・シーケンス・デコーダで使用される可変コードシーケンス推定を示す第２の状態図である。
【図５ｂ】図１の可変長コードワード・シーケンス・デコーダで使用される可変コードシーケンス推定を示す第２の状態図の続きである。
【図６】他の方法と比較して図１に示す本発明による方法の第１の性能を示すグラフである。
【図７】他の方法と比較して図１に示す本発明による方法の第２の性能を示すグラフである。
【図８】他の方法と比較して図１に示す本発明による方法の第３の性能を示すグラフである。
【図９】他の方法と比較して図１に示す本発明による方法の複雑性の結果を示すグラフである。
【図１０】他の方法と比較して図１に示す本発明による方法の迅速性の結果を示すグラフである。
【図１】
2005510113.tif 000024
【図２】
2005510113.tif 000025
【図３】
2005510113.tif 000026
【図４】
2005510113.tif 000027
【図５ａ】
2005510113.tif 000028
【図５ｂ】
2005510113.tif 000029
【図６】
2005510113.tif 000030
【図７】
2005510113.tif 000031
【図８】
2005510113.tif 000032
【図９】
2005510113.tif 000033
【図１０】
2005510113.tif 000034
【国際調査報告】
2005510113.tif 000035
2005510113.tif 000036