(57)【要約】本発明は、ソフト出力ビット系列（ＬＶ［１：Ｔ］）に可変長ソフト入力符号語系列（ｙ［１：Ｔ］）をソフト復号化するための方法であって、ＶＬＣ符号語テーブルに従って前記可変長ソフト入力符号語系列（ｙ［１：Ｔ］）が符号化される、方法に関する。本発明は、前記可変長ソフト入力符号語系列のハード出力ビット系列の順次予測のためのスタック復号化アルゴリズムを実行する第１ステージ（１００）であって、前記スタック復号化アルゴリズムにより生成され、前記スタックに含まれる中間データの記憶を有する、第１ステージと、前記ソフト出力ビット系列（ＬＶ［１：Ｔ］）を生成するために前記の記憶された中間データを後処理する、続く第２ステージ（１０２）であって、ソフト出力（Ｌ（ｘ［ｔ］））は各々のビットに対して提供される、第２ステージと、を有する。
2005538640.tif 000002
【特許請求の範囲】
【請求項１】
ソフト出力ビット系列に可変長ソフト入力符号語系列をソフト復号化するための方法であって：
ＶＬＣ符号語テーブルに従って前記可変長ソフト入力符号語系列が符号化される；
方法であり、
前記可変長ソフト入力符号語系列のハード出力ビット系列の順次予測のためのスタック復号化アルゴリズムを実行する第１ステージであって、前記スタック復号化アルゴリズムにより生成され、前記スタックに含まれる中間データの記憶を有する、第１ステージ；及び
前記ソフト出力ビット系列を生成するために前記の記憶された中間データを後処理する、続く第２ステージであって、ソフト出力は各々のビットに対して提供される、第２ステージ；
を有することを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記スタック復号化アルゴリズムを実行する前記第１ステージは；
前記ＶＬＣ符号語テーブルに関連付けられた一元的なツリーを生成する段階であって、前記一元的なツリーはブランチにより結合されたノードを有し、パスは初期ノードから前記ツリーの各々のノードへのブランチにより規定される、段階；
パスのスタックを用いることにより前記の一元的なツリーの初期ノードから続く副段階を実行する段階であって、前記スタックは現時点の先頭パスを有し、各々のパスは累積メトリックに関連付けられ、前記実行は、停止状態の集合が確認されるまで、実行される、段階であり、
現時点の先頭パスの現時点のノードの後に続く各々のブランチに対してメトリックを計算し、
前記の現時点の先頭パスの最終ノードが符号語に対応する場合、前記の現時点の先頭パスの少なくとも前記最終ノードに前記の一元的ツリーの前記処理ノードを置き換えることにより前記の現時点のツリーと前記一元的ツリーを連結し、
前記スタックから前記の現時点の先頭パスを削除し、
前記スタックにおいて、前記の現時点の先頭パスと前記の続くブランチとから成る新しい拡張パスを挿入し、前記の新しい拡張パスの前記累積メトリックは、関連付けられた続くブランチのメトリックにより増加された現時点の先頭パスのメトリックとしての各々の拡張パスに対して計算され、並びに
前記パスに関連付けられた前記累積メトリクスに従って新しい現時点の先頭パスを選択する、
段階；
を有する、ことを特徴とする方法。
【請求項３】
請求項２に記載の方法であって、時間ｔにおいてノードｌに繋がるブランチに関連付けられた前記メトリックは次式により定義され、
ｍ（ｌ，ｙ［ｔ］）＝−ｌｏｇＰ（ｙ［ｔ］｜ｖ（ｌ））−ｌｏｇｐｔ（ｌ）＋ｌｏｇＰ０（ｙ［ｔ］）
ここで、
Ｎｐは、前身を有するノードの集合であり；
ｐｔ（ｌ）（１∈Ｎｐ）は、時間ｔに前記ノードｌに達する前記ブランチの推測的頻度であり；
ｖ（ｌ）（１∈Ｎｐ）は、前記ノードｌに達する前記ブランチの値であって、ｖ（ｌ）∈｛０，ｌ｝であり、
Ｐ（ｙ［ｔ］）は、異なる長さの系列を適正に比較するようにするＦａｎｏ−Ｍａｓｓｅｙメトリックである、
ことを特徴とする方法。
【請求項４】
請求項２又は３に記載の方法であって、前記の選択された新しい現時点の先頭パスは、前記スタックにおいて挿入された前記パスの間の最小累積メトリックを有する、ことを特徴とする方法。
【請求項５】
請求項２乃至４のいずれ一項に記載の方法であって、前記の停止状態の集合は、前記の現時点の先頭パスが前記可変長ソフト入力符号語系列の符号語数とビット数とを有するということを有する、ことを特徴とする方法。
【請求項６】
請求項２乃至５のいずれ一項に記載の方法であって、前記の記憶された中間データを後処理する前記の続く第２ステージは、次式
Λ（ｘ［ｔ］）＝μ（ｔ，０）−μ（ｔ，１）
により各々のビットに対して各々のソフト出力Λ（ｘ［ｔ］）を近似する段階を有し；
ここで、ｔ番目の予測ビットは１であり、μ（ｔ，０）はｔ番目の予測ビットが０であるスタックにおけるパス全部に対する最小累積メトリックであるように、前記スタックにおける前記パス全てに対して、μ（ｔ，１）は最小累積メトリックである、
ことを特徴とする方法。
【請求項７】
請求項２乃至５のいずれ一項に記載の方法であって、前記の記憶された中間データを後処理する前記の続く第２ステージは、次式
【数１】
2005538640.tif 000035
により、各々のビットに対して各々のソフト出力Λ（ｘ［ｔ］）を近似する段階を有し；
ここで、Ｐｉ（ｉ∈［１，．．．，ｒ］）は前記スタックにおいて記憶されたｒ番目の検査されたパスであり、μＰｉはパスＰｉの累積メトリックであり、ＴＰｉはパスＰｉの長さであり、
【数２】
2005538640.tif 000036
はパスＰｉに対応するハードビット系列のｔ番目のハードビットである、
ことを特徴とする方法。
【請求項８】
復号化器にロードされるとき、前記復号化器が請求項１乃至７いずれ一項に記載の方法を実行するようにする命令の集合を有する、前記復号化器のためのコンピュータプログラムプロダクト。
【請求項９】
コンピュータにロードされるとき、前記コンピュータが請求項１乃至７いずれ一項に記載の方法を実行するようにする命令の集合を有する、前記コンピュータのためのコンピュータプロダクト。
【請求項１０】
ＶＬＣ符号語テーブルに従って前記可変長ソフト入力符号語系列が符号化される；
復号化器であり、
前記可変長ソフト入力符号語系列のハード出力ビット系列の順次予測のためのスタック復号化アルゴリズムを実行するための手段であって、前記スタック復号化アルゴリズムにより生成され、前記スタックに含まれる中間データの記憶を有する、手段；及び
前記ソフト出力ビット系列を生成するために前記の記憶された中間データを後処理するための手段であって、ソフト出力は各々のビットに対して提供される、手段；
を有することを特徴とする復号化器。
【請求項１１】
各々の繰り返しに対して繰り返される続く段階を有するＴｘｎ／ｋ個のビットの可変長ソフト入力系列を繰り返し復号化するための方法であって：
前の繰り返しに対して計算される推測的頻度比と前記可変長ソフト入力系列とを入力して用いるチャネル復号化法を適用することにより可変長ソフト出力ビット系列を計算する段階；
前記チャネル復号化法を適用することにより提供される前記可変長ソフト出力ビット系列に依存する可変長ソフト入力符号後系列を計算する段階；
前記チャネル復号化法を適用することにより提供される前記可変長ソフト出力ビット系列に依存する前記可変長ソフト入力符号後系列を入力として用いる請求項１乃至７のいずれ一項に従ってソース復号化するための方法を適用することにより可変長ソフト出力ビット系列を計算する段階；並びに
ソース復号化のための前記方法により適用される前記可変長ソフト出力ビット系列に依存する前記推測的頻度比を計算する段階；
を有し、それらの段階は各々の繰り返しに対して繰り返される、ことを特徴とする方法。
【請求項１２】
各々の繰り返しに対して繰り返される続く段階を実行するための手段を有する可変長ソフト入力系列を繰り返し復号化するための受信器であって：
前の繰り返しに対して計算される推測的頻度比と前記可変長ソフト入力系列とを入力して用いるチャネル復号化法を適用することにより可変長ソフト出力ビット系列を計算し；
前記チャネル復号化法を適用することにより提供される前記可変長ソフト出力ビット系列に依存する可変長ソフト入力符号後系列を計算し；
前記チャネル復号化法を適用することにより提供される前記可変長ソフト出力ビット系列に依存する前記可変長ソフト入力符号後系列を入力として用いる請求項１乃至７のいずれ一項に従ってソース復号化するための方法を適用することにより可変長ソフト出力ビット系列を計算し；並びに
ソース復号化のための前記方法により適用される前記可変長ソフト出力ビット系列に依存する前記推測的頻度比を計算する；
ことを特徴とする受信器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可変長ソフト入力符号語系列をソフト出力ビット系列にソース復号化する方法に関する。
【０００２】
例えば、映像又は音声通信システムのような可変長符号を使用するいずれのシステムにそのような方法を使用することが可能である。
【背景技術】
【０００３】
映像通信システムは、典型的には、ソース符合化システムと、チャネルと、ソース復号化システムを有する。ソース符合化システムは可変長符号語系列を生成し、共有符号のために、それらを復号化するソース復号化システムにそのチャネルに対して伝送する。
【０００４】
可変長符号は、それらの圧縮能力に対する映像符合化基準に広く使用されており、チャネルエラーに非常に敏感に反応する。実際には、一部のビットがチャネルにより変えられるとき、同期化損失が受信器側で生じ、劇的なシンボルエラーレートに繋がる可能性がある。この現象は、例えば、自己同期化ハフマン符号、可逆可変長符号のような変形された可変長符号の導入に導いた。
【０００５】
他の解決方法は、チェーンにエラー補正符号を挿入することによりビットストリームに冗長性を再導入することである。後者の解決方法の重要な点は、復号化側で残りのソースの冗長性を適切に使用することである。復号化器により暗黙のチャネル保護としてみなされる場合、この冗長性は、可変長符合化ソースのエラー補正能力を与えるために利用されることができる。
【０００６】
最近の研究は、複雑性の低い近似の最大事後（ＭＡＰ：Ｍａｘｉｍｕｍ  Ａ  Ｐｏｓｔｅｒｉｏｒｉ）復号化器を使用することが可能であることを示したが、既存のソフト復号化アルゴリズム全てと同様の性能を近似的に提供しつつ、困難な復号化の場合に近い複雑性を示すものである。そのような復号化器については、文献、Ｌ．Ｐｅｒｒｏｓ−Ｍｅｉｌｈａｃ  ａｎｄ  Ｃ．Ｌａｍｙ，”Ｈｕｆｆｍａｎ  ｔｒｅｅ  ｂａｓｅｄ  ｍｅｔｒｉｃ  ｄｅｒｉｖａｔｉｏｎ  ｆｏｒ  ａ  ｌｏｗ−ｃｏｍｌｌｅｘｉｔｙ  ｓｅｑｕｅｎｔｉｑｌ  ｓｏｆｔ  ＶＬＣ  ｄｅｃｏｄｉｎｇ”，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＣＣ‘０２，ｖｏｌｕｍｅ  ２，ｐｐ  ７８３−７８７，Ｎｅｗ  Ｙｏｒｋ，ＵＳＡ，Ａｐｒｉｌ−Ｍａｙ  ２００２、に開示されている。
【０００７】
たとえ、ＭＡＰアルゴリズムが存在し、エラー補正に関して非常に良好な結果を与えるとしても、それらのアルゴリズムは非常に複雑である。他方、文献、Ｂｕｔｔｉｇｉｅｇ：”Ｖａｒｉａｂｌｅ−ｌｅｎｇｔｈ  ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ  ｃｏｄｅｓ”ＰｈＤ  ｔｈｅｓｉｓ，Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｍｎｃｈｅｓｔｅｒ，Ｕｎｉｔｅｄ  Ｋｉｎｇｄｏｍ，１９９５、に開示されたようなスタックアルゴリズムは、それ程複雑でなく、類似した性能に到達することができる。しかしながら、そのようなスタックアルゴリズムは、主に、シンボルレベルの復号化アルゴリズムであり、それ故、ビットに関する信頼性高い情報を提供するようにうまく適合しない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、ＶＬＣ符号に対して複雑性が小さく、ビットレベルで機能する可変長ソフト入力符号語系列をソース復号化するための方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明の主題は、請求項１に記載の可変長ソフト入力符号語系列をソース復号化するための方法である。
【００１０】
更に、請求項１０に記載の可変長ソフト入力符号語系列をソース復号化するためのソース復号化器について提供する。
【００１１】
他の請求項において付加的特徴について開示している。
【００１２】
更に詳細について理解できるであろうように、そのような方法は、メトリック値の昇順にツリーにおける経路を選択することが可能である符合化系列に関する高信頼性の情報を提供する利点を有する。それ故、有用な符号語のみを検索することにより、提案している方法は、復号化ツリーにおいて他の多くの経路をそれ以上考慮する必要がないため、ＣＰＵコスト、複雑性及び時間において非常に効率的である。ＶＬＣ符号化器が他と連結されるとき、構成におけるソフト出力は、次いで、インタラクティブジョイント復号化を実行することが可能である。
【発明を実施するための最良の形態】
【００１３】
従来の符号と可変長符号との間のジョイント符合化のための伝送チェーンについて、図１に示す。
【００１４】
この伝送チェーンは送信器１及び受信器２を有する。
【００１５】
可変長符号（ＶＬＣ）は、送信ビットストリームの長さを減少させるために伝送チェーンにおいて使用される。
【００１６】
送信器１は、選択されたＶＬＣ符号語確率に従ってランダムなＶＬＣシンボル系列ｓを出力するように適合された可変長ソース１０を有する。
【００１７】
ＶＬＣソースの出力において、送信器１は、可変長符号化器１２と、擬似ランダムインタリーバ１４と、組織的畳み込み（ＣＣ）符号化器１６と、パンクチュラ（ｐｕｎｃｔｕｒｅｒ）１８と、ＢＰＳＫモジュレータ２０とを有する。
【００１８】
ランダムＶＬＣシンボル系列ｓは、ｘ［１：Ｔ］で表されるＴビットＶＬＣ系列に、時受信されたシンボルであって、グループ化されたＲ個のシンボルのパケットをマッピングするように適合された、ＶＬＣ符号化器１２において符合化される。ビット系列ｘ［１：Ｔ］は、それ自体、知られているように、ＶＬＣテーブルにより命令されたルールに従って生成される。ＶＬＣテーブルの例を図２に示している。
【００１９】
ＶＬＣテーブルにおいて、符号Ｃは次のように規定される。符号語はシンボルＳｉと関連付けられ、符号語は所定の長さを有する。符号語の値は、関連付けられたシンボルＳｉによりとることができる値を又、表す。更に、各々の符号語に対して、出現頻度Ｐ（Ｓｋ）が関連付けられる。
【００２０】
各々の系列ｘ［１：Ｔ］は、このとき、インターリーブされた系列ｘ［１：Ｔ］を得るためにインタリーバ１４により順番が入れ替えられる。
【００２１】
このインターリーブされた系列
【００２２】
【数３】
2005538640.tif 000003
は、組織的畳み込み符号化器１６への入力として与えられる。ＣＣ符号化器１６の出力においてｖ［１：Ｔｘｎ／ｋ］で表される符合化系列は、望まれる送信速度を達成するようにパンクチュラ１８により実際にパンクチャされ（ｐｕｎｃｔｕｒｅｄ）、ＢＰＳＫモジュレータ２０により調節され、ばらつきα２を有するチャネルに対して伝送される。
【００２３】
受信器２は、復調器３０と、最終デパンクチュラ３２と、インタラクティブ復号化器又はジョイント復号化器３４とを有する。
【００２４】
デパンクチュラ３２は、パンクチャ動作により符合化系列から取り除かれたサンプルを置き換えるための０値サンプルを、受信された系列に導入するように適合される。ｚ［１：Ｔｘｎ／ｋ］で表されるデパンクチャド（ｄｅｐｕｎｃｔｕｒｅｄ）系列は、このとき、繰り返し復号化器３４により復号化され、その繰り返し復号化器３４のフローチャートを図４に示す。
【００２５】
図３に示すように、繰り返し復号化器３４は、ソフト入力ソフト出力（ＳＩＳＯ）ＣＣ復号化器４２と本発明に従ったソフト入力ソフト出力（ＳＩＳＯ）ＶＬＣ復号化器４２とを有する。ＣＣ（又は、ＶＬＣ）復号化器により提供される高信頼性の情報は参照番号４６（又は、４８）においてインターリーブされ、ＶＬＣ（又は、ＣＣ）復号化器の復号化を改善するために使用される。
【００２６】
ＳＩＳＯ  ＣＣ復号化器４２については、例えば、文献、Ｌ．Ｂａｈｌ，Ｊ．Ｃｏｃｋｅ，Ｆ．Ｊｅｌｉｎｅｋ  ａｎｄ  Ｊ．Ｒａｖｉｖ，“Ｏｐｔｉｏｎａｌ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｌｉｎｅａｒ  ｃｏｄｅｓ  ｆｏｒ  ｍｉｎｉｍｉｚｉｎｇ  ｓｙｍｂｏｌ  ｅｒｒｏｒ  ｒａｔｅ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，２０，ｐｐ２８４−２８７，Ｎａｒｃｈ，１９７４、に開示されている。
【００２７】
系列ｙ［１：Ｔ］を復号化することに対しては、それ自体知られているように、ＳＩＳＯ  ＶＬＣ復号化器４４は、次式により、ｌｏｇ事後比Λ（ｘ［ｔ］）のフォームでソフト出力を計算するように適合され、
Λ（ｘ［ｔ］）＝ｌｏｇ（（Ｐ（ｘ［ｔ］＝１｜ｙ［１：Ｔ］））／（Ｐ（ｘ［ｔ］＝０｜ｙ［１：Ｔ］）））  （１≦ｔ≦Ｔ）
ハードビット推定系列は
【００２８】
【数４】
2005538640.tif 000004
で表され、ハードシンボル推定系列は
【００２９】
【数５】
2005538640.tif 000005
で表される。ハードシンボル推定系列は、ＶＬＣテーブルを提供することにより、ハードビット推定系列から導き出される。
【００３０】
ＶＬＣ  ＳＩＳＯ復号化器４４は、ＶＬＣ符号化器において得た推測的な知識を考慮することにより、ビットのΛ（ｘ［ｔ］）に関する高信頼性の情報を導き出す。この場合、
推測的な知識は、ＶＬＣテーブルと、シンボルＰ（Ｓｋ）の出現頻度と、対象系列のシンボル数のようなＳＳＩで表されるいずれの他のソース側情報とから導き出されたＶＬＣツリー構造に存在する。
【００３１】
繰り返し復号化方法の要約は次のように与えられる。
１．初期化Φ（０）［ｔ］＝０
２．繰り返しに対して、ｒ＝１，２，．．．，Ｉであり、ここで、Ｉは全繰り返し数である。
●  推測的な頻度比としてのΦ（ｒ−１）［１：Ｔ］と観測値としてのデパンクチャド（ｄｅｐｕｎｃｔｕｒｅｄ）受信系列ｚ［１：Ｔｘｎ／ｋ］とを用いてＳＩＳＯ  ＣＣ復号化器に適用する
【００３２】
【数６】
2005538640.tif 000006
を計算する。
●
【００３３】
【数７】
2005538640.tif 000007
を計算する。
●
【００３４】
【数８】
2005538640.tif 000008
を計算する。
●  観測値としてｙ（ｒ）［１：Ｔ］を用いてＳＩＳＯ  ＣＣ復号化器４４に適用する
【００３５】
【数９】
2005538640.tif 000009
を計算する。
●
【００３６】
【数１０】
2005538640.tif 000010
を計算する。
●
【００３７】
【数１１】
2005538640.tif 000011
を計算する。
【００３８】
更に正確には、繰り返し復号化プロセスは次のように行われる。即ち、ｒ番目の繰り返しにおいて、ＣＣ復号化器の入力は、デパンクチャド系列ｚ［１：Ｔｘｎ／ｋ］と、前の繰り返しにおいて得られた
【００３９】
【数１２】
2005538640.tif 000012
で表される繰り返し系列の推測的な頻度比Φ（ｒ−１）［１：Ｔ］とにある。ＣＣ復号化器４２は
【００４０】
【数１３】
2005538640.tif 000013
出力系列を提供する。
【００４１】
この同じｒ番目の繰り返しにおいて、ＶｌＣ復号化器４４は、入力として、ＣＣ復号化器出力系列の導き出された観測系列ｙ（ｒ）［１：Ｔ］と、ＶＬＣシンボルの推測的な頻度と、いずれの他の利用可能なソース側情報ＳＳＩとをとり、
【００４２】
【数１４】
2005538640.tif 000014
出力系列を提供する。
【００４３】
繰り返しプロセスの優位性を各々の復号化器がうまく利用するように、所謂、外部情報である独立した情報は、それら２つの復号化器間で交換される必要がある。
【００４４】
【数１５】
2005538640.tif 000015
及び
【００４５】
【数１６】
2005538640.tif 000016
は、ＣＣ復号化器４２及びＶＬＣ復号化器４４それぞれにより提供されるビットについての外部情報として、ｒ≧１に対して、次の式のように定義される。
【００４６】
【数１７】
2005538640.tif 000017
【００４７】
【数１８】
2005538640.tif 000018
ここで、
【００４８】
【数１９】
2005538640.tif 000019
は０に等しい集合である。
【００４９】
σ２／２によりスケーリングされたＣＣの外部情報
【００５０】
【数２０】
2005538640.tif 000020
系列は、ＶＬＣ復号化器のｒ番目の繰り返し、それ故、
【００５１】
【数２１】
2005538640.tif 000021
に対する観測値として用いられる。
【００５２】
インターリーブされたＶＬＣ外部情報
【００５３】
【数２２】
2005538640.tif 000022
は、ＣＣ復号化器４２のｒ＋１番目の繰り返しに対する推測的な頻度比の推定値
【００５４】
【数２３】
2005538640.tif 000023
として用いられる。
【００５５】
ＳＩＳＯ  ＶＬＣ復号化器４４はソフト入力ソフト出力（ＳＩＳＯ）スタック法
を実施し、そのアルゴリズムを図４に開示している。
【００５６】
その方法は、次のような２つの主ステージを行う。即ち、
−  ハード伝送ＶＬＣ系列を推定するためのハード復号化ステージ１００；及び
−  ソフト値を導き出すための後処理ステージ１０２；
である。
【００５７】
この方法の第１種段階１００は、例えば、考慮されている系列におけるシンボル数及びビット数に達するまで、考慮されているハフマンツリーを数倍連結することにより構成される“大きい”ツリーに関するスタック系列復号化アルゴリズムを適用することにある。
【００５８】
ハード復号化ステージ１００の第１段階１１１は、ツリーの各々のブランチに関連付けられた推測的な頻度を計算し、ノード間の関係を規定することにより構造ツリーを生成することにある。図２のＶＬＣ符号に対応する一元的なハフマンツリーを図５に示す。
【００５９】
そのようなツリーは次のような複数のものを有する。
−  ノードＮであって、複数のノードは有効な符号語又はシンボルＳｉに対応する、ノードＮ。
−  ブランチＢであって、メトリックＭが各々のブランチＢに関連付けられる、ブランチＢ。ブランチＢは２つのノードＮを有し、換言すれば、ノードＮから、１つ又は２つのブランチ、即ち、“左”ブランチ及び“右”ブランチが生成される。ブランチは関連付けられたビット値０又は１を有する。
−  パスであって、復号化ビット系列を表す、パス。
【００６０】
パスは複数のブランチを有し、初期ノードからシンボルＳｉであることが可能である後継ノードに進む。
【００６１】
更に、ツリーは異なるレベルを有し、第１レベルはレベル０である。
【００６２】
段階１１２において、スタックが定義される。このスタックは、次の処理段階１０２中、後に用いられるように、ハード復号化ステージ１００の各々の段階において記憶される。
【００６３】
スタックは、次のようなものを有する。即ち、
−  選択された“パス”を有するマトリクス、即ち、これらのパスを構成するノードインデックスの系列、
−  現時点まで復号化されたビットの数をスタックの各々のパスに対して記憶する整数ベクトル、
−  現時点まで復号化されたシンボルの数をスタックの各々のパスに対して記憶する整数ベクトル、及び
−  関連付けられた累積メトリックをスタックの各々のパスに対して記憶するフロートベクトル
である。
【００６４】
スタックは、スタックにおいて初期ノードＮ００をメトリック０で置き換えることにより初期化される。初期ノードＮ００は、復号化スタックにおいて先頭パスであるとみなされる。
【００６５】
段階１１３において、先頭パスの最終ノードの続くブランチのメトリックが計算される。
【００６６】
系列復号化法箱となる長さの系列を比較するため、特定のメトリックが用いられる。集合Ｎｐにおける各々のノードに対して、同時に、このノードに繋がるブランチに関連付けられるメトリックは次のように定義される。
【００６７】
ｍ（ｌ，ｙ［ｔ］）＝−ｌｏｇＰ（ｙ［ｔ］｜ｖ（ｌ））−ｌｏｇｐｔ（ｌ）＋ｌｏｇＰ０（ｙ［ｔ］）
ここで、
●  Ｎｐ：  前身を有するノードの集合
●  ｐｔ（ｌ）（１∈Ｎｐ）：  時間ｔにノード１に達するブランチの推測的頻度
●  ｖ（ｌ）（１∈Ｎｐ）：  ノード１に達するブランチの値、即ち、ｖ（ｌ）∈｛０，１｝
●  Ｐ（ｙ［ｔ］）：  異なる長さの系列を適正に比較するようにするＦａｎｏ−Ｍａｓｓｅｙメトリック
である。
【００６８】
実際には、簡単化のために、項ｐｔ（ｌ）を、ブランチｐ（ｌ）の推測的頻度により近似することができる。この最後の量は、文献、Ｌ．Ｇｕｉｖａｒｃｈ，Ｊ．−Ｃ．Ｃａｒｌａｃｈ  ａｎｄ  Ｐ．Ｓｉｏｈａｎ，”Ｊｏｉｎｔ  ｓｏｕｒｃｅ−ｃｈａｎｎｅｌ  ｓｏｆｔ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｈｕｆｆｍａｎ  ｃｏｄｅｓ  ｗｉｔｈ  ｔｕｒｂｏ−ｃｏｄｅｓ”，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ（ＤＣＣ‘００），ｐｐ．８３−９１，Ｓｎｏｗｂｉｒｄ，Ｕｔａｈ，ＵＳＡ，Ｍａｒｃｈ  ２０００、に記載されている復号化器により周知であると仮定される符号語の頻度とＶＬＣのツリー表現から、直接得られる。
【００６９】
段階１１４において、拡張パスがシンボルノードに達するかどうかを決定するために、テストが実効される。拡張パスは、有効な続くブランチと連結された現時点のパスにある。
【００７０】
拡張パスによりそのようなシンボルノードに達する場合、このパスに関連付けられるシンボル数は段階１１５において増加される。
【００７１】
増加したシンボル数は、拡張パスにより達せられるシンボルノードにおいて初期ノードとＶＬＣ符号に対応する、考慮されている一元的なハフマンツリーに連結することにある。
【００７２】
先頭パスは、段階１１６においてスタックから削除される。先頭パスは、スタックの第１行に記述されたパスである。それは又、最小の累積メトリックを有するスタックのパスである。
【００７３】
拡張パスは、次いで、段階１１７においてスタックに挿入される。
【００７４】
各々の新しい先頭パスの累積メトリックが計算され、スタックに記憶される。累積メトリックは、拡張パスをえるために加えられたブランチのメトリックにより増加された前の先頭パスの累積メトリックに等しい。
【００７５】
段階１１８において、先頭パスが選択される。選択された新しい先頭パスは、スタックに挿入されたパスの間で最小の累積メトリックを有するスタックのパスである。
【００７６】
次に、段階１２１において、停止状態が確認されたかどうか、チェックされる。停止状態は、例えば、先頭パスがオリジナルの系列のシンボル数及びビット数を有することである。
【００７７】
段階１２１において、停止状態が確認された場合、段階１２２が実行される。そうでなければ、段階１１４及び続く段階が繰り返される。
【００７８】
ハード復号化段階１００中、スタックのコンテンツは各々の段階で記憶される。
【００７９】
後処理段階１０２に対応する段階１２２において、ソフト出力値は、ハード復号化段階１００において考慮されたパスの累積メトリックから導き出され、スタックに記憶される。後処理段階のアルゴリズムについては、下で説明する。
【００８０】
ハード復号化段階１００の例示としての例について、次に説明する。
【００８１】
段階１１１：  各々のブランチに関連付けられた推測的頻度を計算して、ノード間の関係を規定する構造ツリーの生成
段階１１２：  スタックの初期化
【００８２】
【表１】
2005538640.tif 000024
段階１１３：  最終ノードＮ００の続くブランチのメトリックの計算
それらは、次のように計算される。
【００８３】
Ｍ（Ｎ００−Ｎ１０）＝Ｍ１０
Ｍ（Ｎ００−Ｎ１１）＝Ｍ１１
段階１１４：  ノードＮ１０に達する拡張パスはシンボルノードに達する。それ故、段階１１５がノードＮ１０に対して実行される。
【００８４】
段階１１５：  到達されたシンボルノードＮ１０において初期ノードと考慮されている一元的なハフマンツリーとの連結
段階１１６及び１１７：  スタックから先頭パスＰＴＨ００の削除とスタックにおける拡張パスの挿入
【００８５】
【表２】
2005538640.tif 000025
段階１１８：  新しい先頭パス、即ち、最小累積メトリックの選択
（最小累積メトリックはＭ１１であると仮定する）
【００８６】
【表３】
2005538640.tif 000026
段階１２１：  停止状態は確認されないと仮定される。
【００８７】
段階１１３：  先頭パスの最終ノードはＮ１１である。
【００８８】
先頭パスの最終ノードの続くブランチのメトリックは次のように計算される。
【００８９】
Ｍ（Ｎ１１−Ｎ２０）＝Ｍ２０
Ｍ（Ｎ１１−Ｎ２１）＝Ｍ２１
段階１１４：  ノードＮ２０及びＮ２１に達した拡張パスはシンボルノードに達し、それ故、段階１１５はノードＮ２０及びＮ２１に対して実行される。
【００９０】
段階１１５：  到達されたシンボルノードＮ２０及びＮ２１において初期ノードと考慮されている一元化されたハフマンツリーとの連結。結果的に得られるツリーについて、図７に示す。
【００９１】
段階１１６及び１１７：
【００９２】
【表４】
2005538640.tif 000027
段階１１８：  新しい先頭パス、即ち、最小累積メトリックを有するパスの選択
（最小累積メトリックはＭ１１＋Ｍ２１であると仮定する）
【００９３】
【表５】
2005538640.tif 000028
段階１２１：  停止状態は確認されないと仮定される。
【００９４】
段階１１３：  先頭パスの最終ノードはＮ２１＝Ｎ００である。先頭パスの最終ノードの続くブランチのメトリックは次のように計算される。
【００９５】
Ｍ（Ｎ２１−Ｎ３４）＝Ｍ´１０
Ｍ（Ｎ２１−Ｎ３５）＝Ｍ´１１
段階１１４：  ノードＮ３４に達した拡張パスはシンボルノードに達し、それ故、段階１１５はノードＮ３４に対して実行される。
【００９６】
段階１１５：  図８に示すような、到達されたノードＮ３４において初期ノードＮ００と考慮されている一元化されたハフマンツリーとの連結。
【００９７】
段階１１６及び１１７：  スタックからの先頭パスＰＴＨ２１の削除と拡張パスの挿入
【００９８】
【表６】
2005538640.tif 000029
段階１１８：  新しい先頭パス、即ち、最小累積メトリックを有するパスの選択
（最小累積メトリックはＭ１１＋Ｍ２０であると仮定する）
【００９９】
【表７】
2005538640.tif 000030
開示した上記の段階は、段階１２１において、停止所状態が確認されるまで繰り返される。
【０１００】
一旦、系列復号化処理が終了すると、後処理が行われ、ソフト出力が生成される。このようなソフト出力は、それ故、スタック復号化アルゴリズムにより検査され、記憶されたパスから抽出されなければならない。
【０１０１】
｛Ｐ１，．．．，Ｐｒ｝をスタックにおいて記憶されたｒ個の検査済みパスとする。所定のパスＰｉ（１≦ｉ≦ｒ）は、ビットの長さＴＰｉ、ビット系列
【０１０２】
【数２４】
2005538640.tif 000031
及び累積メトリックμＰｉにより特徴付けられる。
【０１０３】
第１の解決方法は、次式により、対数尤度比Λ（ｘ［ｔ］）を近似することを提案する。
【０１０４】
Λ（ｘ［ｔ］）＝μ（ｔ，０）−μ（ｔ，１）
ここで、μ（ｔ，１）（又は、μ（ｔ，０））は、ｔ番目の予測ビットが１（又は、０）であるスタックにおけるパス全てに対する最小累積メトリックである。
【０１０５】
Ｐ＊が復号化処理により選択されたパスである場合、それ故、
【０１０６】
【数２５】
2005538640.tif 000032
が成立する場合、次式のようになる。
【０１０７】
μ（ｔ，ｉ）＝μＰ＊
結果として、各々の時間に対して、予測系列への相補ビットを有するパスの最少累積メトリックのみが決定される必要がある。
【０１０８】
第２の解決方法においては、ｔ番目の予測ビットに対する値０及び１の両方に対する最もよいパスが考慮されるばかりでなく、スタックアルゴリズムにより記憶されたパスにおけるメトリック全ても考慮される。従って、対数尤度比Λ（ｘ［ｔ］）が次式により近似される。
【０１０９】
【数２６】
2005538640.tif 000033
図９及び１０は、可変長系列のソース復号化のための他の方法と比較された、本発明に従った方法の性能を示している。
●  考慮される次の方法：いずれの推測的知識を用いない、従来のハード入力ＶＬＣアルゴリズムであるハードアルゴリズム。
●  ＫＭＡＰ、即ち、フレームによりシンボル数に関する正確な推測的な知識を有するＶＬＣ符号の最大事後復号化にあるＭＡＰアルゴリズム。
●  ＳＯＳＡ１は、ソフト出力値を生成するために第１解決法を用いて、ソフト出力スタックアルゴリズム（Ｓｏｆｔ  Ｏｕｔｐｕｔ  Ｓｔａｃｋ  Ａｌｇｏｒｉｔｈｍ）を表す。
●  ＳＯＳＡ２は、ソフト出力値を生成するために第２解決法を用いて、ソフト出力スタックアルゴリズム（Ｓｏｆｔ  Ｏｕｔｐｕｔ  Ｓｔａｃｋ  Ａｌｇｏｒｉｔｈｍ）を表す。
【０１１０】
次の符号が通信チェーンにおいて考慮される。表１に与えられているＶＬＣ符号Ｃは、表２において定義されているパンクチャリングテーブルを用いてパンクチャされた符合化ビットを有する畳み込み符号ＣＣＡにより後継される。得られる結果はフレームエラーレート（ＦＥＲ）及び信号対ノイズ比（ＳＮＲ）の表現で与えられる。
【０１１１】
【表８】
2005538640.tif 000034
表１：シミュレーションで用いる短いＶＬＣ符号
１１１１１１１１１
１１０１１０１１１
表２：シミュレーションで用いられるパンクチャリングテーブル：パンクチャリングレートＲ＝８／９
図９は、先ず、種々の繰り返しに対するＶＬＣ復号化器４４の出力における同じチェーンのためのＳＯＳＡ１アルゴリズム及びＳＯＳＡ２アルゴリズム両方の性能を示している。スタックのサイズは２０に設定されている。与えられた２つの異なる解は略同一であり、ＳＯＳＡ２において非常に僅かではあるが優位性がある。
【０１１２】
図１０は、種々の繰り返しに対するＶＬＣ復号化器４４の出力における同じチェーンのためのＫＭＡＰアルゴリズムとＳＯＳＡ２アルゴリズムとの間の性能比較を示している。特に、文献、Ｌ．Ｐｅｒｒｏｓ−Ｍｅｉｌｈａｃ  ａｎｄ  Ｃ．Ｌａｍｙ，”Ｈｕｆｆｍａｎ  ｔｒｅｅ  ｂａｓｅｄ  ｍｅｔｒｉｃ  ｄｅｒｉｖａｔｉｏｎ  ｆｏｒ  ａ  ｌｏｗ−ｃｏｍｌｌｅｘｉｔｙ  ｓｅｑｕｅｎｔｉｑｌ  ｓｏｆｔ  ＶＬＣ  ｄｅｃｏｄｉｎｇ”，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＣＣ‘０２，ｖｏｌｕｍｅ  ２，ｐｐ  ７８３−７８７，Ｎｅｗ  Ｙｏｒｋ，ＵＳＡ，Ａｐｒｉｌ−Ｍａｙ  ２００２、において、これらのアルゴリズムのハード出力のバージョンに関する従来の研究として上で述べたように、両者は最初の繰り返しに対しては類似した性能を示す。しかしながら、４回の繰り返しの後、ＦＥＲ＝１０−３に対してＫＭＡＰアルゴリズムを用いて得られる約０．８ｄＢの利得は、ＳＯＳＡ２アルゴリズムを用いる場合、完全に到達することができず、ＳＯＳＡ２アルゴリズムは約０．３ｄＢを与えるだけである。
【０１１３】
約０．５ｄＢのみの状態におけるスタックアルゴリズムは、非常に低い複雑性に対してはＫＭＡＰアルゴリズムより悪い。
【０１１４】
しかし、古典的なハードＶＬＣ復号化器（それ故、繰り返しを伴わない）により受信器にすることにより、繰り返し操作により与えられる利得は価値があるものであると判明した。
【図面の簡単な説明】
【０１１５】
【図１】本発明に従った復号化器と符号化器とを有する伝送チェーンの一般的な模式図である。
【図２】図１の復号化器と符号化器において使用される可変長符号語系列に関連付けられたＶＬＣ符号語テーブルである。
【図３】本発明に従った復号化器を有する、図１のジョイント復号化器の詳細図ある。
【図４】本発明に従ったソフト入力ソフト出力可変長符号語系列復号化法のフローチャートである。
【図５】図２のＶＬＣテーブルと関連付けられたツリー表現を表す図である。
【図６】本発明に従った復号化法の実行中、生成される図２のＶＬＣテーブルに関連付けられた、連結された符号ツリー表現を表す図である。
【図７】本発明に従った復号化法の実行中、生成される図２のＶＬＣテーブルに関連付けられた、連結された符号ツリー表現を表す図である。
【図８】本発明に従った復号化法の実行中、生成される図２のＶＬＣテーブルに関連付けられた、連結された符号ツリー表現を表す図である。
【図９】他の方法と比較して、本発明に従った方法の性能を示すグラフである。
【図１０】他の方法と比較して、本発明に従った方法の性能を示すグラフである。
【図１】
2005538640.tif 000037
【図２】
2005538640.tif 000038
【図３】
2005538640.tif 000039
【図４】
2005538640.tif 000040
【図５】
2005538640.tif 000041
【図６】
2005538640.tif 000042
【図７】
2005538640.tif 000043
【図８】
2005538640.tif 000044
【図９】
2005538640.tif 000045
【図１０】
2005538640.tif 000046
【国際調査報告】
2005538640.tif 000047
2005538640.tif 000048
2005538640.tif 000049
2005538640.tif 000050