(57)【要約】本発明は、可変長コードワードシーケンスをソース復号化する方法に関し、前記復号化は複数の状態（Ｓ）から構成される関連状態図とコード（Ｃ）とに基づく。本発明は、ビット時間（Ｂｊ）において状態のグループ（Ｇ）における状態数Ｎのみが部分メトリック計算から導き出される基準に基づき且つそうでなければ前記コード（Ｃ）のアルファベットに独立して保存されるようなやり方で状態図における状態（Ｓ）を減少させる段階から構成されることを特徴とする。グループ（Ｇ）は各々のビット時間（Ｂｊ）に計算される全ての状態に対応する。
2004533766.tif 000002
【特許請求の範囲】
【請求項１】
可変長コードワードシーケンスをソース復号化する方法であって：
前記ソース復号化は複数の状態から構成される関連状態図とコードとに基づき、状態は可能な復号化コードワードシーケンスが通過することが可能であるグラフにおけるノードである方法であり；
ビット時間に状態のグループにおける状態数Ｎのみが部分メトリック計算から導き出される基準に基づき及びそうでなければ前記コードのアルファベットとは独立して保存されるようなやり方で状態図における状態を減少させる段階から構成され、グループはビット時間に関連する；
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、基準は、最良メトリック条件に従って、同じシンボル数を有するグループの全ての状態間に１つのみの状態が保存されるようなものである、ことを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、基準は、保存状態が状態のグループにおいて最良のメトリクスを有するようなものである、ことを特徴とする方法。
【請求項４】
請求項１に記載の方法であって、最良のメトリックをもつ状態であるように、保存された状態間で１つの最終で最良の状態を選択し且つ送信コードワードシーケンスとして同じシンボル数を有する最良の復号化コードワードシーケンスを決定する他の段階から構成される、ことを特徴とする方法。
【請求項５】
請求項１乃至４の何れかに記載の方法であって、復号器のためのコンピュータプログラムプロダクトは、前記復号器がロードされるときに、復号器が実行されるような命令のセットから構成される、ことを特徴とする方法。
【請求項６】
請求項１乃至４の何れかに記載の方法であって、コンピュータのためのコンピュータプログラムプロダクトは、前記コンピュータがロードされるときに、コンピュータが実行されるような命令のセットから構成される、ことを特徴とする方法。
【請求項７】
可変長コードワードシーケンスをソース復号化する復号器であって：
前記ソース復号化は複数の状態から構成される関連状態図とコードとに基づき、状態は可能な復号化コードワードシーケンスが通過することが可能であるグラフにおけるノードである、復号器であり；
ビット時間において部分メトリック計算から導き出される基準に基づき及びそうでなければ前記コードのアルファベットに独立して状態のグループにおける状態数Ｎのみを保存するように適応された状態減少手段から構成され、グループはビット時間に関連する；
ことを特徴とする復号器。
【請求項８】
請求項７に記載の復号器であって、基準は、最良メトリック条件に従って、同じシンボル数を有するグループの全ての状態の間に１つのみの状態が保存されるようなものである、ことを特徴とする復号器。
【請求項９】
請求項７に記載の復号器であって、基準は、保存状態が状態のグループにおいて最良のメトリクスを有するようなものである、ことを特徴とする復号器。
【請求項１０】
請求項７に記載の復号器であって、最良のメトリックをもつ状態であるように、保存された状態間で１つの最終で最良の状態を選択し且つ送信コードワードシーケンスとして同じシンボル数を有する最良の復号化コードワードシーケンスを決定するように適応された選択手段から構成される、ことを特徴とする復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可変長コードワードシーケンスをソース復号化する方法に関し、前記ソース復号化は、複数の状態から構成される関連状態図とコードとに基づき、状態は、可能な復号化コードワードシーケンスが通過することが可能であるグラフのノードである。本発明は又、復号器に関し、前記復号器は前記方法を用いる。
【０００２】
そのような方法は、例えば、ビデオ又はオーディオ通信システムのような可変長コードを用いる任意のシステムにおいて用いられることが可能である。
【背景技術】
【０００３】
ビデオ通信システムは、一般に、ソース符号化システム、チャンネル及びソース復号化システムから構成される。前記ソース符号化システムは、コードワードシーケンスを生成し、共有コードにより復号化する前記ソース復号化システムに前記チャンネルを経由してコードワードシーケンスを送信する。前記共有コードは複数のシンボルを規定する。コードワードシーケンスは複数のシンボルから構成される。復号化は、図１に示されるような状態図（伝統的には、ビット有向グラフとして知られている）によりなされる。
【０００４】
状態図は、値のセットから構成される、ビット時間を表すＸ軸と共有コードのアルファベットを表すＹ軸とから構成される。図１においては、アルファベットは３つの値、“１”、“０１”、“００”から構成される。ボックスは状態図の状態を表す。経路は異なる状態間の遷移により表され、復号化シーケンスは、経路、初めの状態（一般的に０）及び終わりの状態により表される。
【０００５】
チャンネルにより一部の摂動があるため、受信コードワードシーケンスはエラーを含む。従って、複数の可能な復号化コードワードシーケンスが存在する。前記状態図は可能な復号化コードワードシーケンスを与え、状態は、可能な復号化コードワードシーケンスが通過するグラフにおけるノードである。１つの最適な方法は、受信シーケンスに関係なくコードによる全体的に可能な復号化コードワードシーケンスを探すこと、及び状態図の構成の端部において最適な復号化コードワードシーケンスを選択することである。最適で完全な復号化コードワードシーケンスを探すための解決方法は、それ故、受信シーケンスから最も小さい距離をもつ１つのシーケンスを、これらのシーケンス間で探すことである。
【０００６】
この解決方法の１つの主要な問題は、送信コードワードシーケンスが長くなるにつれてグラフがより複雑になり、グラフがより複雑になると、探すべき復号化コードワードシーケンスの数が益々増加することである。従って、ＰａｒｋとＭｉｌｌｅｒにより発表された文献“Ｊｏｉｎｔ  ｓｏｕｒｃｅ−ｃｈａｎｎｅｌ  ｄｅｃｏｄｉｎｇ  ｆｏｒ  ｖａｒｉａｂｌｅ  ｌｅｎｇｔｈ  ｅｎｃｏｄｅｄ  ｄａｔａ  ｂｙ  ｅｘａｃｔ  ａｎｄ  ａｐｐｒｏｘｉｍａｔｅ  ｍａｐ  ｓｅｑｕｅｎｃｅ  ｅｓｔｉｍａｔｉｏｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｃｏｕｓｔｉｃｓ，  Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  ｒｅｆｅｒｅｎｃｅｄ  ＩＣＡＳＳＰ’９９  ｐｐ２４５１−２４５４，Ｍａｒｃｈ  １５−１９，１９９９に説明されているように、このような複雑さの問題に対して提案された解決方法は、共有コードのアルファベットにおける同じシンボルの値をもつ状態のセット間に最適なメトリックを有する復号化コードワードシーケンスを、各々のビット時間において、選択することにより、状態の数を減少させることである。しかしながら、この解決方法は、満足のいくパケットエラー率の性能をもたらさない。
【発明の開示】
【課題を解決するための手段】
【０００７】
したがって、本発明の目的は、ソース復号化可変長コードワードシーケンスのための方法及び復号器であって、前記ソース復号化は複数の状態から構成される関連状態図とコードとに基づき、状態は可能な復号化コードワードシーケンスが通過することが可能であるグラフにおけるノードであり、適度な複雑さをもつ効果的な復号化を達成する、方法及び復号器を提供することである。
【０００８】
この目的を達成するために、本発明に従った方法は、ビット時間に状態のグループにおける状態数Ｎのみが部分メトリック計算から導き出される基準に基づき及びそうでなければ前記コードのアルファベットとは独立して保存されるようなやり方で状態図における状態を減少させる段階から構成され、グループはビット時間に関連する、段階から構成される。
【０００９】
更に、本発明に従った復号器は、ビット時間において部分メトリック計算から導き出される基準に基づき及びそうでなければ前記コードのアルファベットに独立して状態のグループにおける状態数Ｎのみを保存するように適応された状態減少手段から構成され、グループはビット時間に関連する、復号器から構成される。
【００１０】
以下の詳細な説明において理解されるであろうように、そのような方法は、一方では、状態図構築の各々の段階の状態図における状態の減少と、他方では、部分メトリック計算から導き出される基準によるよりよい性能と、を可能にする。
【００１１】
第１実施形態においては、ソース復号化の方法は、基準は、最良メトリック条件に従って、同じシンボル数を有するグループの全ての状態間に１つのみの状態が保存されるようなものである、ことを特徴とする。
【００１２】
以下で理解されるであろうように、状態数Ｎはビット時間により上限化され、それ故、複雑さはそのような上限により制限される。従って、そのような基準は、複雑さの低減を伴う先行技術の最適方法に類似した性能に導く。
【００１３】
第２実施形態においては、ソース復号化の方法は、基準は、保存状態（Ｓ）が状態のグループ（Ｇ）において最良のメトリクスを有するようなものである、ことを特徴とする。
【００１４】
以下において明らかになるであろうように、この場合、状態数は固定されている。従って、そのような基準は、最適な場合とは対照的に、複雑さは安定していてビット時間に伴って増加しない状態図に導き、且つそのような基準は、送信コードワードシーケンスの長さにそれ以上依存しない状態図に導く。更に、それは先行技術のＰａｒｋ＆Ｍｉｌｌｅｒ法とは対照的な良好なＰａｃｋｅｔ  Ｅｒｒｏｒ  Ｒａｔｅ性能を与える。
【００１５】
本発明の目的、特徴及び優位性は、以下の添付図を参照する詳細説明を読むことにより明らかになるであろう。
【発明を実施するための最良の形態】
【００１６】
以下の説明においては、当業者に周知の機能又は構成については、不必要に詳細に説明することにより本発明を不明瞭にすることが考えられるため、詳細には説明しないこととする。
【００１７】
本発明は、複数の状態から構成される関連状態図に基づく可変長コードワードシーケンスをソース復号化する方法に関する。前記方法は、図２に示されるように、特に、ビデオ通信システムＶＳ内のＶＬＣと呼ばれる可変長コード復号器において用いられる。更に、前記ビデオ通信システムＶＳは、ＶＬＣ符号器ＶＬＣ−ＥＮＣから構成されるソース符号化システムＳ−ＥＮＣ、チャンネルＣＨ及び前記ＶＬＣ復号器から構成されるソース復号化システムＳ−ＤＥＣを備えている。ソース符号化システムＳ−ＥＮＣは、ＶＬＣ符号器によりコードワードシーケンスＳＱを符号化し、共有コードに基づきＶＬＣ復号器ＶＬＣ−ＤＥＣによりそれを復号化する前記ソース復号化システムＳ−ＤＥＣに複数のビット時間の間に前記チャンネルＣＨによりそれを送信する。その送信はビット毎になされる。コードワードシーケンスＳＱは可変長Ｌ＿ＳＱを有している。このことは、複数の送信コードワードシーケンスＳＱｓは異なる長さを有し、それ故、受信コードワードシーケンスＳＱｒは異なる長さを有することを意味している。コードワードシーケンスＳＱは、共有コードＣにより規定される複数のシンボルＳＹから構成される。１つのシンボルは少なくとも１ビットから構成されることに留意されたい。
【００１８】
図３に示した第１の例において、コードＣは次のように規定される。
−  最大長さＬ＿ＭＡＸは２に等しく、又、シンボル＝２で最大長さを表す
−  サイズＫは３に等しく、又シンボルの数を表す
−  値のセット［Ｃ１，Ｃ２，Ｃ３］からなるコードＣのアルファベットは、［０；１０；１１］に等しく、又それら３つのシンボルにより得られる値を表す。３つの現れる確率［ＰＣ１，ＰＣ２，ＰＣ３］はそれらコードの値に関連している。
【００１９】
送信コードワードシーケンスは次のように規定される。例えば、ＳＱｓ’＝００１１０１００である場合、ソース符号化システムにおける修正段階、例えば、当業者に周知のＢＰＳＫ修正段階の後、ＳＱｓ＝−１；−１；１；１；−１；１；−１；−１となる。次いで、チャンネルＣＨの摂動のために、ソース復号化システムにより受信されるシーケンスＳＱｒは、ＳＱｒ＝−０．８；−０．７；０．２；１．２；−０．５；０．６；−０．３；０．３となる。
【００２０】
今後、受信シーケンスＳＱｒは送信シーケンスＳＱｓを回復するために復号化されなければならない。換言すれば、前記送信シーケンスＳＱｓにおいて送信されたシンボルＳＹを回復しなければならない。エラーをもたらす摂動により、多くの可能な復号化コードワードシーケンスＳＱｄが存在し得ることに注意する必要がある。
【００２１】
状態図は、可能な復号化コードワードシーケンス全てを示すために用いられる。図３はそのような状態図を示している。Ｘ軸はビット時間を表す。Ｙ軸は用いられるコードＣのアルファベットを表し、そのアルファベットは、シンボルＳＹにより得られることが可能である値を表す値のセットから構成される。
【００２２】
図３の状態図は状態のグループＧ０乃至Ｇ５から構成され、それら各々は、ビット時間Ｂ０乃至Ｂ５それぞれに関連している。グループＧは、コードワードシーケンスＳＱｒが受信されたとき、コードＣのアルファベットが何であっても、各々のビット時間Ｂｊ（ｊ≧０）において計算された状態全てに対応する。シンボルの数Ｔは各々の状態ボックスに示されている。それは、特定のビット時間において部分的に受信されたシーケンスＳＱｒ内のシンボルの数ＳＹを表す。それは又、対応する可能な復号化コードワードシーケンスＳＱｄ内のシンボルの数を表す。
【００２３】
垂直ラインは状態のグループの範囲を定める一方、水平ラインは、シンボルにより得られることが可能である３つの値Ｃ１、Ｃ２、Ｃ３からなるコードＣのアルファベットの範囲を定める。
【００２４】
経路は復号化コードワードシーケンスＳＱｄを表す。それは、末端状態と中間状態からなる。例えば、経路Ｓ０１１−Ｓ１１１−Ｓ３２１−Ｓ４１２−Ｓ５１２は、末端状態Ｓ５１２と、シンボル“０”、“１０”、“０”及び“０”それぞれに対応する中間状態Ｓ１１１、Ｓ３２１及びＳ４１２から構成される。そのシンボルの総数は４に等しい。
【００２５】
状態Ｓは、ｋ＝グループ数と、ｌ＝コードＣのアルファベットにおける値と、ｍ＝グループとコード値における状態の次数とをもつインデックスＳｋｌｍにより表されることに留意されたい。例えば、Ｓ２１１ｈａ，状態ＳがグループＧ２、コード値Ｃ１に属し、コード値Ｃ１についてのグループＧ２における第１状態であることを意味する。
【００２６】
状態図から理解されるように、状態は末端状態又は異なる経路の中間状態であることが可能であり、それ故、ビット時間Ｂｊにおけるそのような状態Ｓは、復号化シンボルシーケンスとも呼ばれる可能な復号化コードワードシーケンスが通過するグラフにおけるノードを表す、ということができる。
【００２７】
送信コードワードシーケンスＳＱｓに最もよく適合する最良の復号化コードワードシーケンスＳＱｄを選択するために、状態図における状態を減少させる第１段階１）が実行される。ビット時間Ｂｊ（ｊ≧０）において、状態のグループＧにおける状態の数Ｎのみが、部分メトリック計算に基づく基準に関連して保存される。
【００２８】
更に説明を加えるように、状態数Ｎは、第１実施形態におけるビット時間により上限になるか、又は第２実施形態における所定の値ＮＢＭＡＸに等しくなる。
【００２９】
このように、減少する段階は２つのサブ段階から構成される。第１のサブ段階Ａ）においては、部分的なシーケンスに関する部分的なメトリクスの計算が実行される。形容詞“部分的な”は、全体的なシーケンスＳＱｒが受け入れられる最終の前に実行されたメトリクスの計算であることを意味する。メトリック計算は、当業者には周知であるＭＡＰ基準と呼ばれる“Ｍａｘｉｍｕｍ  Ａ  Ｐｏｓｔｅｒｉｏｒｉ”基準に従って実行され、ＭＡＰは、部分受信シーケンスＳＱｒと調節後の部分送信シーケンスＳＱｄとの間のユークリッド距離の計算値に等しく、その次にアピアランスのコードワードに依存する係数による重み付けが実行される。
【００３０】
全体的なメトリック計算のための式は、
ｍ（ｉ）＝Σｉ（‖ＳＱｒｉ−Ｃｉ‖２＋ｌｎ（ＰＣｉ））
であり、ここで、ＳＱｒｉはコードＣｉのエミッション（ｅｍｉｓｓｉｏｎ）に対応する送信シーケンスＳＱｒの一部である。部分メトリックは、この合計の第１項のみから構成されるものとして、この式から簡単に推測されることが可能である。
【００３１】
上述から理解できるように、状態図の構成は、先行技術において述べられているような最適な方法とは対象的に、受信シーケンスＳＱｒの関数として効果をもたらす。実際には、各々のビット時間において、部分受信シーケンスに依存する部分メトリック計算に基づいて削除される一部の状態が存在する一方、先行技術においては、削除される状態は存在せず、全てのメトリック計算は状態図の構成の最後に実行されるか又は状態の除去技術は最適な状態には十分近いものではない。
【００３２】
第２サブ状態Ｂ）においては、削除基準が適用される。第１実施形態においては、図３に示すように、基準は、最適なメトリック条件に従って、シンボルＳＹと同じ数をもつグループＧの全ての状態の間でただ１つの状態が保存されるようになっている。
【００３３】
考慮される状態Ｓに関連するメトリックは、前記考慮される状態Ｓに移行する部分シーケンスの第１サブ段階Ａ）において計算される部分メトリックの１つである。
【００３４】
このように、図３においては、例えば、ビット時間＝２で、Ｔ＝１のシンボルＳＹをもつ第３グループＧ２の全ての状態の間で最良のメトリックを有する状態Ｓを探す。第３グループＧ２における第２状態Ｓ２２１と第３状態Ｓ２３１はＴ−１のシンボルＳＹを有する。第２状態Ｓ２２１は、それが第３状態Ｓ２３１に比較して良好なメトリックを有するため、保存される。シンボルＴ＝２の数については、たった１つの状態Ｓ２１１が存在し、この状態は存続される。同様のやり方をビット時間＝３にも適用し、シンボルＴ＝２の数等の状態を探す。
【００３５】
この第１実施形態の１つの優位性は、状態図の複雑さが、境界付けされて、ここで簡単になることである。ビット時間値は、実際には、状態数Ｎの明らかな大多数である。しかしながら、前記状態数Ｎは固定されないため、それは送信コードワードシーケンスＳＱｓの長さに依存する。従って、その複雑さは、ビット時間と共に尚も増加することとなる。
【００３６】
第２の好適な実施形態においては、図４に示すように、シンボル又はビット値、又はシンボル又はビット数に拘わらず、保存状態Ｓは最良のメトリックを有する。保存状態数Ｎは所定の値ＮＢＭＡＸと定義され、達成することが求められる性能と存在することが求められる複雑さの関数として捉えられる。それ以上の条件は用いられない。従って、例えば、保存される状態数はＮＢＭＡＸ＝２である。図４においては、ビット時間＝１において、第１状態Ｓ４１１及び第６状態Ｓ４３２が、それらが最良のメトリクスであるため、保存される。他の状態は削除される。同じ数のシンボルＳＹをもつ全ての状態Ｓは、ここでは３であるが、削除される。
【００３７】
第２実施形態の優位性は、先行技術と比較すると、次のような項目である。
−  要求されるように、ＮＢＭＡＸが固定される
−  ＮＢＭＡＸは不変であるため、複雑さは、ビット時間と共に、即ち、先行技術の最適化法又はＰａｒｋ＆Ｍｉｌｌｅｒ法とは対象的に、送信コードワードシーケンスＳＱｓの長さと共に増加しない。
【００３８】
これら２つの実施形態について、状態Ｓが削除されたとき、その状態から派生するブランチはもはや有望な候補とはなり得ないことを意味していることに留意されたい。状態図における減少は明らかに注目に値する。ビット時間Ｂｊ（即ち、ｊビットの部分シーケンスのため）に状態図において存続する状態の数は第１実施形態に対してはｊにせいぜい等しく、及び第２実施形態に対してはせいぜいＮＢＭＡＸに等しい。更に、上述のように、この最後の状態図の複雑さは、送信コードワードシーケンスＳＱｓの長さにはもはや依存しないことは明らかである。
【００３９】
又、メトリックの派生の影響を除いて、減少の段階は、Ｐａｒｋ＆Ｍｉｌｌｅｒ法とは対象的に、コードＣのアルファベット又は要素のアピアランスの確率に依存しないで実行されることに留意されたい。
【００４０】
状態図の構成の最後において、コードワードシーケンス内に送信されるビットがもはやないとき、上述の両方の実施形態について同様である最終決定が下される。最良メトリックをもる状態であるとして、保存状態間で最終的な最良状態Ｓｆを選択し、且つ、送信コードワードシーケンスとして同じ数のシンボルＳＹを有する最良復号化コードワードシーケンスを決定する、第２段階２）からなる。
【００４１】
ＶＬＣ復号器は、一方で、送信シーケンスＳＱｓにおけるＶＬＣ復号器により送信されるシンボル数ＮＢ＿ＳＹを理解しており、他方で、状態図の構成の終了のための前記送信シーケンスＳＱｓのビットにおける長さＬ＿ＳＱｓを理解しているようになっていることに留意されたい。
【００４２】
伝統的に文献に発表されており、当業者に周知であるように、最良のメトリックは、最良であり、従って、ＭＡＰ基準という意味で最も高い確率であって、最良と同等でありそれ故上述で規定されたメトリックｍ（ｉ）の意味で最短距離である確率に到達するシーケンスを意味するとして理解される。
【００４３】
この最終にして最良の状態Ｓｆは、可能である復号化コードワードシーケンスを決定する全ての可能な状態において最良のメトリックを有するのとして考慮されているため、近似が実行されるが、それは保存された状態間においてのみ実行される。従って、本発明に従った方法は近似法と呼ばれる。
【００４４】
最終的に、第３段階３）においては、復号化は、送信シーケンスＳＱｓにより送信されたシンボルＳＹの値を回復するために、状態図において対応するシーケンスの経路に選択最終且つ最良状態Ｓｆから逆行することにより効果を発揮する。
【００４５】
本発明に従った第１及び第２実施形態の実行について、以下に示す。
他のソース復号化方法との性能の比較
図５及び図６は、本発明に従った方法の性能について、可変長コードワードシーケンスのソース復号化のための他の方法と比較して示している。次のような方法の性能が示されている。
−  ハードＶＬＤ復号化“ＨＡＲＤ”（円形）
−  最適化ソフトＶＬＣ復号化“ＯＰＴＩＭＡＬ”（四角形）
−  Ｐａｒｋ＆ＭｉｌｌｅｒＶＬＣ復号化“Ｐ＆Ｍ”（上向き三角形）及び
−  本発明に従って復号化する方法の第１実施形態“ＡＭＡＰ−１”（Ｘ）
−  本発明に従って復号化する方法の第２実施形態“ＡＭＡＰ−１”（右向き三角形）
ハードＶＬＣ方法は、通常、固定長コードワードシーケンスに適用される方法である。
【００４６】
先行技術において述べられたような最適化法は、状態の減少及び近似を伴わない方法である。他の方法は近似法である。
【００４７】
これら２つの図においては、“水平”条件（シンボルＳＹの値の関数として一部の状態を保つ）を用いるＰ＆Ｍ法の性能に対して、“垂直”条件（ビット時間に関連するグループの関数として一部の状態を保つ）を用いる本発明に従った方法の実施形態の性能について特に理解することができる。
【００４８】
図５及び図６の両方のグラフは、信号対雑音比Ｅｂ／Ｎ０に対するＰａｃｋｅｔ  Ｅｒｒｏｒ  Ｒａｔｅ（ＰＥＲ）についての性能であって、パケットがコードワードシーケンスに対応する、性能を示している。信号対雑音比の計算は当業者には周知であることに留意されたい。換言すれば、性能対コストについて計算することができる。その性能は、コードワードシーケンスが十分に復号化されたかどうかを示し、コストは、コードワードシーケンスＳＱのビットを送信するためにどれ位のパワー（エネルギー／ノイズ）が消費されたかを示す。それ故、用いるために所望されるパワー及び／又は存在することを受け入れられるエラーに依存して、最良の解決法を選択する。それらの最適な方法及びハードな方法は全ての性能を制限する。
【００４９】
第２の実施形態については、Ｐ＆Ｍ法との公平な比較を維持するために、保たれる状態の数ＮＢＭＡＸ＝３は、Ｐ＆Ｍ法について得られるものより優れているか又は同等であるように選択される。実際には、Ｐ＆Ｍ法は、シンボルが保たれる同様な値［Ｃ１，．．．，Ｃｉ，．．．，Ｃｋ］を有するような各々の状態のセットのための最良のメトリックを有する復号化コードワードシーケンスであるため、Ｐ＆Ｍ法に対しては、各々のビット時間において、Ｋ個の状態は保たれる。
【００５０】
図５における第１のグラフのために、コードＣＡが４つの上述の方法について考慮されている。
−  考慮される可変長コードサイズはＫ＝３であり、
−  最大長さはＬ＿ＭＡＸ＝２であり、
−  コードのアルファベットは値［Ｃ１；Ｃ２；Ｃ３］＝［０；１０；１１］から構成され、
−  関連するシンボルの確率［ＰＣ１（０），ＰＣ２（１０），ＰＣ３（１１）］は［０．５；０．２５；０．２５］に等しくなるように選択され、並びに
−  送信されたシンボルの数はＮＢ＿ＳＹ＝１００である。
【００５１】
この第１グラフにおいて理解されるように、本発明に従った方法の２つの実施形態はＰ＆Ｍ法に比べて良好な性能を示している。それらの性能は、Ｐ＆Ｍ法のそれらというより、最適化法に近い。
【００５２】
図６の第２グラフについては、コードＣＢは、上述の４つの方法に対して考慮されている。
−  考慮される可変長コードサイズはＫ＝６であり、
−  最大長さはＬ＿ＭＡＸ＝４であり、
−  コードのアルファベットは値［Ｃ１；Ｃ２；Ｃ３；Ｃ４；Ｃ５；Ｃ６］＝［０；１００；１０１；１１０；１１１０；１１１１］から構成され、
−  関連するシンボルの確率［ＰＣ１（０），ＰＣ２（１００），ＰＣ３（１０１），ＰＣ４（１１０），ＰＣ５（１１１０），ＰＣ６（１１１１）］は［０．５；０．１５；０．１７；０．０８；０．０６；０．０４］に等しくなるように選択され、並びに
−  送信されたシンボルの数はＮＢ＿ＳＹ＝１００である。
【００５３】
この第２グラフから理解できるように、本発明の方法に従った２つの実施形態は更にＰ＆Ｍ法に比べて良好な性能を示している。それらの性能は、それらの性能は、Ｐ＆Ｍ法のそれらというより、最適化法に近い。本発明に従った方法の異なる実施形態であっても類似した性能を示している。
【００５４】
最適な方法を適切に選択するために、これら方法の各々であってハードな方法について状態図の複雑さの検討については、第１コードＣＡに対して図７に与えられている。全体的な状態図における状態間の遷移の数ＮｂＴと状態の数ＮｂＳは複雑さを象徴的に表している。このように、複雑さはＮｂＴ＊ＮｂＳに関係している。コードの最大長さはＫ（コードＣＡの場合に、Ｋは３に等しい）であるため、各状態毎の遷移の数は全ての方法に対してＫである。従って、実際には、複雑さは状態数ＮｂＳに関係していることが理解できる。
【００５５】
図７において、Ｘ軸はビット時間を表し、Ｙ軸はビット時間当たりの状態数ＮｂＳを表している。これは、状態当たりの遷移数が上述のように各々の方法に対して同じであるため、全体的な方法の複雑さのよい評価法となっている。
【００５６】
最適化法とＡＭＡＰ−１法は複雑さが状態図のビット時間と線形の関係にあることを示している一方、Ｐ＆Ｍ法とＡＭＡＰ−２法は両方とも状態図のビット時間に依存していないようにみえる。
【００５７】
第２コードＣＢの場合を考慮するとき、同様の結果が得られる。
【００５８】
結論として、以上の図において示された結果から、全体的に最良の解決法は本発明の第２実施形態であるＡＭＡＰ−２法であることが分かるが、それは、ＡＭＡＰ−２法が、他の既存の近似法と比較して、低い状態図の複雑さをもつ良好なＰａｃｋｅｔ  Ｅｒｒｏｒ  Ｒａｔｅ  ＰＥＲを与えるためである。第２実施形態について保存される状態数ＮＢＭＡＸは、好適には、４乃至１０の間の数をとる。この間について、ＮＢＭＡＸが増加するにつれて増加する複雑さと、値ＮＢＭＡＸ＝１０の後にそれ以上改善されない性能との間の良好なバランスがみられる。
本発明に従った方法の実行
本発明に従った方法のソフトな実行の一例についてここで説明する。
【００５９】
実際には、本発明に従った方法は、第１段階における、前の状態を指すポインタが保存されるメトリック計算プロセスを用いる第１前進伝達と、第２段階における、全ての保存状態から選択された１つの状態に対応する最良の復号化コードワードシーケンスを確立するためのトレースバックプロセスとを含む。
【００６０】
本発明に従った方法の第１実施形態において、第１前進伝達は、各々のビット時間において、上述のように、同じシンボル数ＳＹを有するグループＧの全ての状態の間で最良のメトリックを有する状態Ｓのみを保つ。
【００６１】
状態図について、次のような構造の助けを借りて説明する。
【００６２】
“状態”と呼ばれるものは、次のようなものから構成される。
−  考慮される状態までのシンボル数（最終決定のための送信シーケンスのシンボルの数と比較される）
−  考慮される状態までのビット数（ビット時間の段階の数に対応する）
−  考慮される状態に導く遷移までの累積メトリック
−  前の状態を指す第１ポインタＰＳＴＡＴＥ＿ＰＲＥＶ
−  調査されるべき次の“垂直”状態を指す第２ポインタＰＳＴＡＴＥ＿ＶＥＲＴ＿ＮＥＸＴ
格子と呼ばれるものは、次のようなものから構成される。
−  各々のビット時間に対して存続する状態の数を記憶する整数のベクトル、状態図の状態のマトリクス
状態構造における２つのポインタは、本発明に従った方法のためには重要であることに留意されたい。第１ポインタＰＳＴＡＴＥ＿ＰＲＥＶは、トレースバック操作のために必要であり、第２ポインタＰＳＴＡＴＥ＿ＶＥＲＴ＿ＮＥＸＴは、“垂直な”状態、即ち同じビット時間Ｂｊについての全ての状態の走査を可能にする。このことを示すために、一例を図８に示している。
【００６３】
このように、第１実施形態のための前進プロセスは次のように効果が現れる。ビット時間Ｂｊにおいて、状態Ｓ１ｊから、
−  各々の新しい調査状態ＳＩ（ｊ＋１）の確率について：
−  状態ＳＥ（ｊ＋１）が、同じビット時間及び同じシンボル数をもつグラフにおいてすでに存在する場合、
＊この既存の状態ＳＥ（ｊ＋１）と調査状態ＳＩ（ｊ＋１）との間の部分累積メトリクスを比較する。
【００６４】
−  そうでないと、グラフにおいてその状態を生成し、調査状態ＳＩ（ｊ＋１）をそれにコピーする。
−  次の“垂直な”状態Ｓ２ｊ（特別なポインタＰＳＴＡＴＥ＿ＶＥＲＴ＿ＮＥＸＴに従って）を調査する、又は、それ以上“垂直な”状態（０に等しい第２ポインタＰＳＴＡＴＥ＿ＶＥＲＴ＿ＮＥＸＴ）が存在しない場合、次のビット時間Ｂｊ＋１に進める。
【００６５】
本発明に従った方法の第２実施形態において、第１前進伝達は、各々のビット上述のように、時間において、最良のメトリックを有するＮＢＭＡＸの状態を保つ。
【００６６】
用いられる構造は第１の実施形態についてのものと同様である。
【００６７】
このように、第２実施形態についての前進プロセスは、次のような効果を示す。ビット時間Ｂｊにおいて、状態Ｓ１ｊから、
−  各々の新しい調査状態ＳＩ（ｊ＋１）の確率について、
−  状態ＳＥ（ｊ＋１）が、同じビット時間及び同じシンボル数をもつグラフにおいてすでに存在する場合、
＊この既存の状態ＳＥ（ｊ＋１）と調査状態ＳＩ（ｊ＋１）との間の部分累積メトリクスを比較する。
【００６８】
−  そうでなければ、
−  次のビット時間Ｂｊ＋１における既存の状態数が保存された状態数ＮＢＭＡＸに比べて劣る場合、
グラフにおいてその状態を生成し、調査状態ＳＩ（ｊ＋１）をそれにコピーする。
【００６９】
−  そうでなければ、
＊より悪い部分累積メトリックを用いて既存状態ＳＥ（ｊ＋１）を決定し、
＊このより悪い既存の状態ＳＥ（ｊ＋１）と調査状態ＳＩ（ｊ＋１）とを比較する。最良のメトリックを用いて１つの状態を保つ。
−  次の“垂直な”状態Ｓ２ｊ（特別な第２ポインタＰＳＴＡＴＥ＿ＶＥＲＴ＿ＮＥＸＴに従って）を調査する、又は、それ以上“垂直な”状態（０に等しい第２ポインタＰＳＴＡＴＥ＿ＶＥＲＴ＿ＮＥＸＴ）が存在しない場合、次のビット時間Ｂｊ＋１に進める。
【００７０】
両方の実施形態についてのトレースバックプロセスは、次のような効果を示す。
【００７１】
シンボルのマッチングＮＢ＿ＳＹを用いてＬ＿ＳＱｓビットにおいて最良の状態に到達する。
【００７２】
−  シンボルの正しい数をもつ状態が見つからない場合、
＊マッチングが見つからなかった
−  そうでなければ、
＊１つのマッチングが見つかった
＊戻って、対応する遷移に関するシンボルを書き留める
＊復号化コードワードを得るためにシンボルの順序を逆にする
本発明は上述の実施形態及に限定されるものではなく、添付の請求項に規定されているような本発明の趣旨及び適用範囲から逸脱することなく変更及び変形を行うことが可能であることに留意されたい。この点に関して、次のような結言を記すものである。
【００７３】
本発明は上述のビデオの応用に限定されるものではない。本発明は、可変長コードを用いるあらゆる応用に利用することが可能であり、前記復号化のコストを支援することができる（計算の複雑さと時間遅延について、本発明に従った方法における前記時間遅延は、トレースバックプロセスのために全体的なシーケンスを受け入れの終了に依存する）。代表的には、本発明は、例えば、ビデオ、オーディオ又はテキスト圧縮に用いられることが可能である。
【００７４】
本発明に従った方法は上述の実行に限定されるものではないことに留意されたい。
【００７５】
ハードウェア又はソフトウェアの単一のアイテムが幾つかの機能を実行する場合、ハードウェア、ソフトウェア又はそれら両方のアイテムにより、本発明に従った方法の機能を実行する数多くの方法が存在する。本発明は、ハードウェア、ソフトウェア又はそれら両方のアイテムのアセンブリが機能を果たす事実を排除するものではない。例えば、減少段階は、最終にして裁量の状態の段階の選択と結合され、本発明に従ったソース復号化方法を変更することなく単一の機能を構成することが可能である。
【００７６】
前記ハードウェ又はソフトウェアのアイテムは、例えば、配線された電子回路により、又は、適切にプログラムされた集積回路による等、幾つかの方法において実行されることが可能である。集積回路はコンピュータ又は復号器に備えられることが可能である。第２には、復号器は、第１基準または第２基準に従った減少段階１）を生成するように適応された状態減少手段、及び上述のように選択段階２）を生成するように適応された選択手段から構成され、前記手段は上述のようにハードウェア又はソフトウェアからなる。
【００７７】
集積回路は命令のセットから構成される。従って、前記命令のセットは、例えば、コンピュータのプログラミングメモリ又は復号器メモリに含まれ、コンピュータ又は復号器がソース復号化方法の異なる段階を実行するようにすることが可能である。
【００７８】
命令のセットは、例えばディスクのようなデータ記憶媒体を読み出すことによりプログラミングメモリにロードされることが可能である。サービスプロバイダは又、インターネット等の通信ネットワークにより使用可能である命令のセットを作成することが可能である。
【００７９】
添付の請求項における参照符号は、請求項を限定するものとして解釈されるべきものではない。動詞“から構成される”及びこの動詞の語形変化は、請求項に規定されるもの以外のあらゆる段階又は要素の存在を排除するものではない。単数の要素又は段階はそのような要素又は段階の複数の存在を排除するものではない。
【図面の簡単な説明】
【００８０】
【図１】先行技術に従った可変長コードワードシーケンスのソース復号化の方法の状態図である。
【図２】本発明に従ったソース復号化方法が用いられるビデオ通信システムを示す概略図である。
【図３】本発明の第１実施形態に従ったか変調コードワードシーケンスのソース復号化方法の第１状態図である。
【図４】本発明の第２実施形態に従ったか変調コードワードシーケンスのソース復号化方法の第２状態図である。
【図５】図３及び図４に示された、本発明に従った方法の第１性能を示す第１グラフである。
【図６】図３及び図４に示された、本発明に従った方法の第２性能を示す第２グラフである。
【図７】図３及び図４に示された、本発明に従った方法の第３性能を示す第３グラフである。
【図８】図３及び図４に示された、本発明に従った方法の１つの実行を示す第３状態図である。
【国際公開パンフレット】
2004533766.tif 000003
2004533766.tif 000004
2004533766.tif 000005
2004533766.tif 000006
2004533766.tif 000007
2004533766.tif 000008
2004533766.tif 000009
2004533766.tif 000010
2004533766.tif 000011
2004533766.tif 000012
2004533766.tif 000013
2004533766.tif 000014
2004533766.tif 000015
2004533766.tif 000016
2004533766.tif 000017
2004533766.tif 000018
2004533766.tif 000019
2004533766.tif 000020
2004533766.tif 000021
2004533766.tif 000022
2004533766.tif 000023
2004533766.tif 000024
2004533766.tif 000025
2004533766.tif 000026
2004533766.tif 000027
【国際調査報告】
2004533766.tif 000028
2004533766.tif 000029