(57)【要約】【課題】新しい符号化／復号化。【解決手段】本発明は、第２のバイナリ要素（Ｙｄ）の符号化されたフローを受け取るための第1の入力を備えたデコーダ（２）に関する。それは、第１のバイナリ要素の送信時に第２のバイナリ要素を受信する確率を規定するように設計された受信チャンネル特性（Ｉｃ）を受け取るための第２の入力と、第１のモジュール（１２）と、処理モジュール（６）とからなる。第１のモジュールが、ソース状態図におけるソース状態間の遷移に関連されたｘに関する記号の確率を定義するように適応されたソースモデル（８）と、プロダクト状態図において作成されたｘに関する記号と第１のバイナリ要素との間の対応を規定するように適応されたいわゆるプロダクトモデル（７）とを規定する。処理モジュールが、ソースモデル（８）とプロダクトモデル（７）とのチャンネル特性（Ｉｃ）から第２のバイナリ要素の符号化されたフローのビットを知ってｘに関する記号を計算するように適応されるとともに、計算された確率からｘに関する記号の最も起こりそうなフローを再構築するように適応されている。
2005534241.tif 000002
【特許請求の範囲】
【請求項１】
復号化方法であって、
ａ．ソース状態図におけるソース状態（Ｃｋ）間の遷移に関連されるｘに関する記号（Ｓｋ）の確率を定義するように設計されたソースモデルと、ｘに関する記号と第１のバイナリ要素との間の対応を定義するように設計されたいわゆる「プロダクト」モデルとを定義し、「プロダクト」状態図のプロダクト状態に関してプロダクト状態がソース状態の関数であるようにし、
ｂ．第１のバイナリ要素の伝送時に、第２のバイナリ要素を受信する確率を定義するように設計された「チャンネル」特性を受け取り、
ｃ．第２のバイナリ要素の受信符号化されたフローについて、ソースモデルおよびプロダクトモデルのチャンネル特性から、第２のバイナリ要素のフローのビットを知ってｘに関する記号を復号化する確率、または第２のバイナリ要素のフローのビットを知ってプロダクト状態に到達する確率を計算し、
ｄ．ステップｃで計算された確率からｘに関する記号の最も起こりそうなフローを再構築することを特徴とする復号化方法。
【請求項２】
請求項１に記載の復号化方法において、
前記プロダクトモデルが、前記ソースモデルに基づくとともに、ｘに関する記号に関連される確率に関してｘに関する記号と第１のバイナリ要素との間での対応を確立するように設計された転送モデルに基づいて定義されることを特徴とする復号化方法。
【請求項３】
請求項２に記載の復号化方法において、
前記ソースモデルが、ソースのｍに関する記号（Ａｋ）と対象のｘに関する記号（Ｓｋ）との間での対応に関連される遷移を含み、特にｍ≧ｘかつｘ＝２を含むことを特徴とする復号化方法。
【請求項４】
請求項１〜３の何れか一項に記載の復号化方法において、
前記プロダクトモデルおよび転送モデルが算術型であり、前記転送モデルが符号化モデルまたは復号化モデルであることを特徴とする復号化方法。
【請求項５】
請求項１〜４の何れか一項に記載の復号化方法において、
ステップｃが、第２のバイナリ要素のフローのビットを知って、ｘに関する記号を復号化する確率の計算を複数のステップにおいて行うことを特徴とする復号化方法。
【請求項６】
請求項１〜５の何れか一項に記載の復号化方法において、
ステップｃが、一定数のステップからステップごとに一定の選択基準に基づいて、第２のバイナリ要素のフローのビットを知って１つのステップの間に計算されたｘに関する記号を復号化する確率のうち特定の確率の選択を行うことを特徴とする復号化方法。
【請求項７】
請求項６に記載の復号化方法において、
ステップｃで前記選択基準が、最大確率の中で保持される固定数の確率を含むことを特徴とする復号化方法。
【請求項８】
請求項６または７に記載の復号化方法において、
ステップｃでの前記選択基準が、第１のバイナリ要素の送信時に第２のバイナリ要素を受信する確率と比較される最小のしきい値を有し、前記最小のしきい値より高い第１のバイナリ要素の送信時に第２のバイナリ要素を受信する確率から計算された第２のバイナリ要素のフローのビットを知ってｘに関する記号を復号化する確率だけを各ステップで記憶するようにすることを特徴とする復号化方法。
【請求項９】
請求項５〜８の何れか一項に記載の復号化方法において、
ステップｃが、遷移によってリンクされた状態から構成されるツリーの構築を行い、各状態は確率の計算におけるステップに対応し、１つの状態から開始する各遷移は、計算された確率の１つに対応することを特徴とする復号化方法。
【請求項１０】
請求項１または９に記載の復号化方法において、
ステップｄが、前記ツリーの中の連続遷移に対応する確率の積の計算を行うとともに、最も起こりそうな連続遷移とｘに関する記号のうち最も起こりそうなフローとに対応する最大積の選択を行うことを特徴とする復号化方法。
【請求項１１】
請求項５または１０に記載の復号化方法において、
ステップｃが、復号化される一定数の連続的なｘに関する記号について、第２のバイナリ要素のフローのビットを知ってｘに関する記号のシーケンスを復号化する確率の計算を行うことを特徴とする復号化方法。
【請求項１２】
請求項５または１０の復号化方法において、
ステップｃが、第２のバイナリ要素のフローにおける一定数の連続的なビットについて、第２のバイナリ要素のフローのビットを知ってｘに関する記号のシーケンスを復号化する確率の計算を行うことを特徴とする復号化方法。
【請求項１３】
請求項１〜４の何れか一項に記載の復号化方法において、
前記対応を確立するプロダクトモデルに基づいてステップｃが、
ｃ１．初期状態から最終状態へプロダクト状態図の遷移によってリンクされた状態を連続的に構築し、各状態が前記初期状態からの第２のバイナリ要素のフローにおける一定数のビットについて予想数の復号化されたｘに関する記号を定義することを特徴とする復号化方法。
【請求項１４】
請求項１３に記載の復号化方法において、
ステップｃの構成が、
ｃ２．前記最終状態から前記初期状態へ前記プロダクト状態図からの状態の連続的な抑制を行い、前記プロダクト状態図に対して第２のバイナリ要素のフローにおける一定数のビットについてｘに関する記号の予想数がｘに関する記号の既知の最大数と異なっていることを特徴とする復号化方法。
【請求項１５】
請求項１３または１４に記載の復号化方法において、
ステップｃが、
ｃ１．第２のバイナリ要素のフロー内の過去のビットを知って、各状態の構築後に一定状態に到達した第１の連続的に可能な計算を行い、
ｃ２．前記一定状態を知って、前記最終状態から前記初期状態への状態ごとに、第２のバイナリ要素のフローにおいて次のビットを観察する第２の連続的な確率の計算を行うことを特徴とする復号化方法。
【請求項１６】
請求項１３または１４に記載の復号化方法において、
ステップｃが、
ｃ３．前記初期状態から前記最終状態への図の状態ごとに、第２のバイナリ要素のフローにおいて過去のビットを知ってその状態に到達する第１の連続的な確率と、前記最終状態から前記初期状態までの状態ごとに、一定状態を知って第２のバイナリ要素のフローにおいて次のビットを観察する第２の連続的な確率との計算を行うことを特徴とする復号化方法。
【請求項１７】
請求項１３〜１６の何れか一項に記載の復号化方法において、
ステップｃが、状態ごとに第１の確率と第２の確率の積を決定することにより第２のバイナリ要素のフローのビットを知って、前記一定状態に到達する確率の計算を行うことを特徴とする復号化方法。
【請求項１８】
請求項１または１７に記載の復号化方法において、
ステップｄが、最大積の選択に続いて、さまざまな可能な連続的な状態の確率の積の計算を行うことを特徴とする復号化方法。
【請求項１９】
請求項１３または１８に記載の復号化方法において、
ステップｄが、プロダクトモデルの対応を使用して、前記連続的な状態に対応するｘに関する記号のフローの確立を行うことを特徴とする復号化方法。
【請求項２０】
第２のバイナリ要素の符号化されたフローを受け取る第１の入力を有するデコーダであって、
第１のバイナリ要素の送信時に、第２のバイナリ要素を受信する確率を定義するように設計されチャンネル特性を受け取る第２の入力と、
第１のモジュールと、
処理モジュールとを備え、
前記第１のモジュールが、ソース状態図におけるソース状態間の遷移と関連されるｘに関する記号について確率を定義するように設計されたソースモデルと、「プロダクト」状態図においてソース状態の関数であるプロダクト状態に関して、ｘに関する記号と第１のバイナリ要素との間の対応を定義するように設計されたいわゆる「プロダクト」モデルとを規定し、
前記処理モジュールが、チャンネル特性に基づいてソースモデルおよびプロダクトモデルの第２のバイナリ要素の符号化されたフローのビットを知ってｘに関する記号を復号化する確率、または第２のバイナリ要素のフローのビットを知ってプロダクト状態に到達する確率を計算するように適応されるとともに、計算された確率からｘに関する記号の最も起こりそうなフローを再構築するように適応されたことを特徴とするデコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特にマルチメディア信号（オーディオ、音声、画像、ビデオ、音声）用のデジタルデータ圧縮／解凍に関し、および無線通信ネットワークと移動体通信ネットワークなどのノイズが多いネットワーク上でデータのロバスト伝送に関する。
【背景技術】
【０００２】
デジタルデータの伝送速度を低減するために、デジタルデータが圧縮され、それと同時に専門家が「信号エントロピー」と呼ぶ理論上の最大値が達成されるようにする。これを行うためには、多くの場合、可変長符号とも呼ばれる統計学的な符号、たとえばハフマン符号が利用される。しかしながら、これらの符号には伝送エラーにきわめて敏感であるという欠点がある。ビットの逆転はデコーダの脱同期化につながり、その結果誤りのあるビット位置の後のすべてのデータの復号化が間違ったものとなることがある。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ネットワーク上でのマルチメディア信号の圧縮、伝送、および解凍のための既存の解決策は、さらに言及されるが、データトランスポートサービスの一定品質が保証されているという仮説に基づいている。言い換えると、訂正符号の使用に依存することにより、トランスポート層とリンク層は（つまり、圧縮および解凍アプリケーションにより見られるように）擬似ヌルの残存誤り率を達成することを可能にしている。しかしながら、擬似ヌルの残存誤り率というこの仮定は、特に無線ネットワークと移動体ネットワークにおいておよびチャンネル符号の現実的な複雑さについて経時的にチャンネル特性が変わる（非静止チャンネル）時には、もはや当てはまらなくなる。さらに訂正符号による冗長性の付加は効果的な速度の低減につながる。
【０００４】
したがって、新しい符号化／復号化の解決策に対するニーズがある。
【０００５】
本発明はこの分野においてある程度の進展を提案するものである。
【課題を解決するための手段】
【０００６】
本発明は、以下のステップを有する復号化方法に関するものである：
ａ．ソース状態図におけるソース状態間の遷移に関連されるｘに関する記号（ｘ進法記号）の確率を定義するように設計されたソースモデルと、ｘに関する記号と第1のバイナリ要素（２進法要素）との間の対応を定義するように設計されたいわゆる「プロダクト」モデルとを定義し、「プロダクト」状態図のプロダクト状態に関してプロダクト状態がソース状態の関数であるようにし、
ｂ．第１のバイナリ要素の伝送時に、第２のバイナリ要素を受信する確率を定義するように設計された「チャンネル」特性を受け取り、
ｃ．第２のバイナリ要素の受信符号化されたフローについて、ソースモデルおよびプロダクトモデルのチャンネル特性から、第２のバイナリ要素のフローのビットを知ってｘに関する記号を復号化する確率、および、第２のバイナリ要素のフローのビットを知ってプロダクト状態に到達する確率をそれぞれ計算し、
ｄ．ステップｃで計算された確率からｘに関する記号の最も起こりそうなフローを再構築する。
【０００７】
有利なことには、プロダクトモデルが、ソースモデルに基づくとともに、ｘに関する記号に関連される確率に関してｘに関する記号と第１のバイナリ要素との間での対応を確立するように設計された転送モデルに基づいて定義される。ソースモデルが、ソースのｍに関する記号（ｍ進法記号）と対象のｘに関する記号との間での対応に関連される遷移を含み、特にｍ≧ｘかつｘ＝２を含む。
【０００８】
好適には、プロダクトモデルおよび転送モデルが算術型であり、転送モデルが符号化モデルまたは復号化モデルである。
【０００９】
さらに好適には、ステップｃが、第２のバイナリ要素のフローのビットを知って、ｘに関する記号を復号化する確率の計算を段階的に行う。
【００１０】
本発明の第１の態様では、ステップｃが、一定数のステップからステップごとに一定の選択基準に基づいて、第２のバイナリ要素のフローのビットを知って１つのステップの間に計算されたｘに関する記号を復号化する確率のうち特定の確率の選択を行う。
【００１１】
有利なことには、ステップｃで選択基準が、最大確率の中で保持される固定数の確率を含んでいる。有利または付加的には、ステップｃでの選択基準が、第１のバイナリ要素の送信時に第２のバイナリ要素を受信する確率と比較される最小のしきい値を有し、最小のしきい値より高い第１のバイナリ要素の送信時に第２のバイナリ要素を受信する確率から計算された第２のバイナリ要素のフローのビットを知ってｘに関する記号を復号化する確率だけを各ステップで記憶するようにしている。
【００１２】
好適には、ステップｃが、遷移によってリンクされた状態から構成されるツリーの構築を行い、各状態は確率の計算におけるステップに対応し、１つの状態から開始する各遷移は、計算された確率の１つに対応する。このように、第２のバイナリ要素のフローのビットを知って、ｘに関する記号を復号化する確率のうち特定の確率を選択することが、その特定の確率の関数としてのツリーにおいて遷移の部分集合に対応する状態を構築することに対応している。
【００１３】
加えて、ステップｄが、ツリーの中の連続的な遷移に対応する確率の積の計算を行うとともに、最も起こりそうな連続的な遷移とｘに関する記号のうち最も起こりそうなフローとに対応する最大積の選択を行う。
【００１４】
第１の動作では、ステップｃが、復号化される一定数の連続的なｘに関する記号について、第２のバイナリ要素のフローのビットを知ってｘに関する記号のシーケンスを復号化する確率の計算を行う。
【００１５】
第２の動作では、ステップｃが、第２のバイナリ要素のフローにおける一定数の連続的なビットについて、第２のバイナリ要素のフローのビットを知ってｘに関する記号のシーケンスを復号化する確率の計算を行う
本発明の第２の態様では、対応を確立したプロダクトモデルに基づいてステップｃが、
ｃ１．初期状態から最終状態へプロダクト状態図の遷移によってリンクされた状態を連続的に構築し、各状態が前記初期状態からの第２のバイナリ要素のフローにおける一定数のビットについて予想数の復号化されたｘに関する記号を定義する。
【００１６】
有利なことには、ステップｃの構成が、
ｃ２．前記最終状態から前記初期状態へ前記プロダクト状態図からの状態の連続的な抑制を行い、前記プロダクト状態図に対して第２のバイナリ要素のフローにおける一定数のビットについてｘに関する記号の予想数がｘに関する記号の既知の最大数と異なっている。
【００１７】
第１の動作では、ステップｃが、
ｃ１．第２のバイナリ要素のフロー内の過去のビットを知って、各状態の構築後に一定状態に到達した第１の連続的に可能な計算を行い、
ｃ２．最終状態から初期状態への状態ごとに、第２のバイナリ要素のフローにおいて次のビットを知って一定状態に到達する第２の連続的な確率の計算を行う。
【００１８】
第２の動作では、ステップｃが、
ｃ３．初期状態から最終状態への図の状態ごとに、第２のバイナリ要素のフローにおいて過去のビットを知ってその状態に到達する第１の連続的な確率と、最終状態から初期状態までの状態ごとに、第２のバイナリ要素のフローにおいて次のビットを知って一定状態に到達する第２の連続的な確率との計算を行う。
【００１９】
好適には、ステップｃが、状態ごとに第１の確率と第２の確率との積を決定することにより各状態の確率の計算を行い、そして、ステップｄが、最大積の選択に続いて、さまざまな可能な連続的な状態の確率の積の計算を行う。
【００２０】
有利なことには、ステップｄが、プロダクトモデルの対応を使用して、連続的な状態に対応するｘに関する記号のフローの確立を行う。
【００２１】
また、本発明は、第２のバイナリ要素の符号化されたフローを受け取る第１の入力を有するデコーダに関する。そのデコーダは、第１のバイナリ要素の送信時に、第２のバイナリ要素を受信する確率を定義するように設計されチャンネル特性を受け取る第２の入力と、
第１のモジュールを備え、
第１のモジュールが、ソース状態図におけるソース状態間の遷移と関連されるｘに関する記号について確率を定義するように設計されたソースモデルと、
「プロダクト」状態図においてソース状態の関数であるプロダクト状態に関して、ｘに関する記号と第１のバイナリ要素との間の対応を定義するように設計されたいわゆる「プロダクト」モデルと、
チャンネル特性に基づいてソースモデルおよびプロダクトモデルの第２のバイナリ要素の符号化されたフローのビットを知ってｘに関する記号を復号化する確率、または第２のバイナリ要素のフローのビットを知ってプロダクト状態に到達する確率を計算するように適応されるとともに、計算された確率からｘに関する記号の最も起こりそうなフローを再構築するように適応された処理モジュールとを規定する。
【００２２】
本発明の他の特徴および利点は、添付図面とともに以下の詳細な説明を検討する際に明らかになる。
【発明を実施するための最良の形態】
【００２３】
本明細書の記載に対しての図面および付属物には一定の文字の要素が本質的に含まれている。したがって、それらの要素は、明細書の記述の理解を助ける役割を果たすだけではなく、規定どおりに本発明の定義に貢献するものである。
【００２４】
一般的には、マルチメディア信号（画像、ビデオ、オーディオ、音声）用の圧縮システムは、可変長符号とも呼ばれる統計符号を使用している。これらにより、専門化が「信号エントロピー」と呼ぶものに近い速度を得ることが可能になる。既存のシステムにおいて（特に規格において）最も広範囲に使用されている符号は、以下の論文、つまり、「最小冗長性符号の構築方法（Ａ ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｍｉｎｉｍｕｍ ｒｅｄｕｎｄａｎｃｙ ｃｏｄｅｓ）」、Ｄ．Ａ．ハフマン、会報、ＩＲＥ、４０（１９５１年）、１０９８〜１１０１ページの中で説明されたハフマン符号である。
【００２５】
さらに最近では、圧縮に関して性能向上のために算術符号への関心が再び始まっている。実際には、これらの符号により、仮定されるソースモデルから符号化方法を切り離すことが可能になる。そのために、さらに高位の統計モデルの使用が容易になる。これらの算術符号は以下のような研究論文に記述され、すなわち、
［１］「一般化されたクラフト不同および算術（Ｇｅｎｅｒａｌｉｚｅｄ ｋｒａｆｔ ｉｎｅｑｕａｌｉｔｙ ａｎｄ ａｒｉｔｈｍｅｔｉｃ）」、Ｊ．Ｊ．Ｒｉｓｓａｎｅｎ、ＩＢＭ  Ｊ．Ｒｅｓ．Ｄｅｖｅｌｏｐ．、２０：１９８〜２０３、１９７６年５月、
［２］「数表現としての算術符号化（Ａｒｉｔｈｍｅｔｉｃ ｃｏｄｉｎｇ ａｓ ｎｕｍｂｅｒ ｒｅｐｒｓｅｎｔａｔｉｏｎｓ）」、Ｊ．Ｊ．Ｒｉｓｓａｎｅｎ、Ａｃｔａ Ｐｏｌｙｔｅｃｈ．Ｓｃａｎｄ．Ｍａｔｈ．、３１：４４〜５１、１９７９年１２月、
および以下のような米国特許に記述されている：
米国特許第４,２８６,２５６号、第４,４６７,３１７号、第４,６５２,８５６号。
【００２６】
最近まで、圧縮システムの設計は、トランスポートサービスの保証された品質を仮定して引き受けられてきている。実際に仮定されていることは、ＯＳＩモデルの下層が、本出願から理解されるように、擬似ヌルの残存誤り率を保証するエラー訂正符号を組み込んでいることである。
【００２７】
したがって、可変長符号は、それらの伝送ノイズに対してかなりの感度にも関わらず、幅広く使用可能である。このような擬似ヌルの残存誤り率の仮定は、チャンネル特性が経時的に変化する（非静止チャンネル）無線ネットワークおよび移動体ネットワークではもはや当てはまらない。ソース信号デコーダにより見られるこの残存誤り率は多くの場合決して無視できない。バイナリストリームにおけるエラーによって、デコーダの脱同期化、それ故に復号化された情報ストリームへのエラーの伝播が引き起こされ得る。
【００２８】
この伝播の問題を緩和するために、第１世代規格（Ｈ．２６１、Ｈ．２６３、ＭＰＥＧ−１、ＭＰＥＧ−２）は、送信されたバイナリストリームの構文中に同期マーカを組み込んでいる。これらは、他の符号語内で発生するエラーによってエミュレートされず、それ故に、「１」に近い確率でデコーダにより認識され得る長い符号語（「０」が後に続く「１」に設定された１５ビットまたは２１ビットの文字列から構成される１６ビットまたは２２ビット）である。
【００２９】
これにより、この同期マーカによって区切られるパケット内にバイナリストリームが構築されるようになる。そのために、エラーの伝播がパケット内で限定されるようになる。
【００３０】
しかしながら、エラーがパケットの開始時に発生した場合、パケットの残りが失われてしまう可能性がある。さらに、これらの同期マーカの頻度は、圧縮効率の不当な損失を回避するために制限されなければならない。
【００３１】
そこで、新しい規格（Ｈ．２６３＋とＭＰＥＧ−４）は可逆可変長符号（ＲＶＬＣ）を採用している。これらの符号の特別な特徴は、パケット内の最初のビットから最後のビットまで復号化可能であり、およびパケット内の最後のビットから最初のビットまで逆に復号化可能である。
【００３２】
エラーがパケットの真中で発生した場合、この符号の対称性により、同期マーカによって区切られたパケットの最後まで符号を伝播する代わりにパケットの真中のセグメントにエラー伝播を限定することが可能になる。しかしながら、符号対称性は、ハフマン符号と比較されると、１０％のオーダーで圧縮効率の損失を生じさせる結果となる。加えて、可逆可変長符号はエラー伝播の問題を完全に克服していない。つまり、エラーがパケットの開始時および終了時に発生すると、パケット全体が誤りとなる傾向がある。
【００３３】
伝送ノイズに関連して圧縮ターム（つまり、ソースのエントロピーに接近可能な圧縮ターム）での極めて効率的な符号のファミリ（集合）に基づいて、符号化方法／復号化方法ロバストの設計は、特に将来のマルチメディア（画像、ビデオ、オーディオ、音声）の移動体通信システムにとって重要な目標である。新しい規格が、ＩＴＴＵ（国際電気通信連合）およびＩＳＯ（国際標準化機構）の双方の中でそのようなシステムのために開発中である。
【００３４】
規格は電気通信業界部門において顕著な役割を果たしているけれども、そのような符号のファミリによっても独自仕様の解決策を求めるすき間産業において用途が見出され得る。
【００３５】
本明細書中で記述されている発明は、特に、算術符号および擬似算術符号を含む算術型符号などのような圧縮システムに幅広く使用されている符号のファミリ用のエンコーダ／デコーダに関する。
【００３６】
算術符号化および擬似算術符号化の原則は後述される。それらは、文献［２］と以下の論文との中でさらに詳細に説明される：
［３］「データ圧縮のための算術コード化（Ａｒｉｔｈｍｅｔｉｃ ｃｏｄｉｎｇ ｆｏｒ ｄａｔａ ｃｏｍｐｒｅｓｓｉｏｎ）」、Ｉ．Ｈ．Ｗｉｔｔｅｎ、Ｒ．Ｍ．Ｎｅａｌ、およびＪ．Ｇ．Ｃｌｅａｒｙ、ＡＣＭの通信（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ）、３０（６）：５２０〜５４０、１９８７年６月、
［４］「画像およびテキスト圧縮（Ｉｍａｇｅ ａｎｄ Ｔｅｘｔ Ｃｏｍｐｒｅｓｓｉｏｎ）」、Ｐ．Ｇ．ＨｏｗａｒｄおよびＪ．Ｓ．Ｖｉｔｔｅｒ、８５〜１１２ページ、クルワ・アカデミック・パブリッシャ（Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒ）、１９９２年。
【００３７】
本明細書の記述の残りにおいては、用語「シーケンス」の使用は要素のフロー、つまり一連の要素を指す。たとえば、記号のそれぞれのビットのシーケンスは、記号のそれぞれのビットのフロー、つまり記号のそれぞれの一連のビットを示すものである。
【００３８】
一般的には、符号化の原則には次のステップが含まれる：
Ａ＝Ａ１．．．ＡＩを定量化されたソース記号のシーケンスとし、定量化されたソース記号が、Ｍ＝２ｑ記号から構成される有限アルファベットＡすなわちＡ＝（Ａ１．．．ＡＭ）から当該ソース記号の値を取るものとする。このアルファベットは、記号ごとに関連付けられた定常確率を示す定常分布を有する。（ソースＡとも呼ばれる）Ｍに関する記号（Ｍ進法記号）のシーケンスは、（ｘ≦Ｍを使用して）ｘに関する記号のシーケンスに変換される。Ｍに関する記号のシーケンスが（ソースＳとも呼ばれる）バイナリ記号のシーケンスＳ＝Ｓ１．．．ＳＫに変換される場合には、ＫはＫ＝ｑｘＬによって定義される。変数Ｍおよびｘは２から始まる整数を定義する。したがって、この例の中ではｘ＝２およびＭ＝４である。
【００３９】
ほんの一例として本明細書中の記述の残りにおいては簡略のために、ｘ＝２であると仮定する。この変換は、Ｍに関するソースＡとバイナリソースＳとの間の対応を含めて、後述されるようなソースモデルを使用する。バイナリ記号Ｓのシーケンスは、精度Ｔの擬似算術エンコーダを介して第１のバイナリ情報要素のシーケンスＵ＝Ｕ１．．．ＵＮに順々に変換される。このバイナリストリームの長さＮは、Ｓのランダムな変数関数、すなわち、Ａの関数自身であるバイナリ記号のシーケンスとＭに関する記号のシーケンスとの関数である。第１のバイナリ要素Ｕのストリームは、ほんの一例として、メモリレス（ｍｅｍｏｒｙ−ｌｅｓｓ）チャンネルで送信される。第１のバイナリ要素Ｕのこのストリームは、通信チャンネルによる伝送中に生じるエラーのために、第２のバイナリ要素Ｙのストリームとして受け取られる。通信システムの下層によって、実際には、少なくとも通信チャンネルの現在の特性Ｉｃが決定可能になり、たとえばチャンネルにより通信されたビット中に生じた誤り率と受信されたビットの信頼測定値とが決定可能になる。このような後者の測定値により、チャンネル上で通信された第１のバイナリ要素を知る確率と第２のバイナリ要素を受け取る確率とが推定可能になる。これらの確率は、チャンネルの現在の特性Ｉｃの１つ、すなわちチャンネル上でのエラーの確率ｐに基づいて付属物（指数ｉが整数である式２１）の中で示されるように推定される。
【００４０】
復号化の原則は記号Ａのシーケンスの推定を伴い、以下のように「観察ｙ」のシーケンスとも呼ばれる第２のバイナリ要素を知るものである。本明細書の記述の残りでは、大文字はランダム変数を示すために使用され、小文字は表現、つまりこれらの変数の観察を示すために使用される。一連の連続変数を示すために、表記Ｘｕｖ＝（Ｘｕ，Ｘｕ＋１ ．．．Ｘｖ）が使用される。
【００４１】
符号化／復号化の原則は、Ｍ＞２でＭに関する記号（Ａ）に対応せずにＭ＝２でバイナリ記号（Ｓ）に対応するソースに直接的に適用することもできる。本明細書の記述の残りでは、それぞれｘに関する記号、Ｍに関する記号は、特に、バイナリ記号（それぞれｘ＝２、Ｍ＝２）の場合とそれぞれｘ＞２、Ｍ＞２の記号の場合とを含む。
【００４２】
図１は、組合されたエンコーダ１と、組合されたデコーダ２との例を示している。エンコーダおよびデコーダはそれぞれ入力Ｅｃ、Ｅｄと出力Ｗｃ、Ｗｄとを有する。符号化の間に、符号化されるｘに関する記号のフローはＥｃにおいてエンコーダ入力で受け取られる。エンコーダは、たとえば圧縮形式で、ｘに関する記号のフローを符号化することにより生成され第１のビットストリームＵｃと呼ばれる第１のバイナリ要素のフローをＷｃで出力する。この第１のビットストリームＵｃは、デコーダ２の入力Ｅｄにチャンネル１１を介して送信される。（たとえば第１のフローの中の特定のビットを反転させることによって）第１のビットストリームの中にエラーを生じさせる可能性のあるチャンネルは、デコーダ２の入力に、第２のビットストリームＹｄと呼ばれる第２のバイナリ要素のフローを送信する。本発明によれば、処理モジュール６は、デコーダの出力Ｗｄで記号Ｓｄのフローを得るために、チャンネルによって通信されるチャンネル特性Ｉｃとともに第２のビットストリームを受信し処理する。処理モジュール６は、モデルモジュール１２と動作するように設計されている。このモデルモジュールは、
後述されるソース状態図の中のソース状態間での遷移に関連付けられるｘに関する記号の確率を規定するように設計されたソースモデル８と、
ソース状態と転送モデル状態との関数である「プロダクト」状態の状態図に基づいて、ｘに関する記号と第１のバイナリ要素との間の対応を規定するために使用されるいわゆる「プロダクト（積）」モデル７とを備えている。
【００４３】
プロダクトモデル７は、ソースモデル８と転送モデル９または１０とに基づいて規定されている。プロダクトモデルはソースモデルと転送モデル９または１０とから動的に構築できる。別の考えられる実施の形態では、プロダクトモデルは、動的に構築されずに、モデルモジュール内で実現できる。転送モデルは符号化モデル９または復号化モデル１０を含む。この転送モデルは、バイナリ記号に関連付けられる確率の関数として、バイナリ記号と第１のバイナリ要素との間の対応を確立する働きをする。
【００４４】
ソースモデルを使用して圧縮される前に、ｘに関する記号のシーケンスに事前変換できるＭに関する記号のシーケンスから開始することも可能である。
【００４５】
考えられる（可能な）実施の形態では、これらのモデルは、事前計算されて（ｐｒｅ−ｃｏｍｐｕｔｅｄ）デコーダのモデルモジュールの外部のモジュール内のメモリに記憶可能である。また、モデルは、たとえばイーサネット型ローカルネットワークまたはインターネット型広域ネットワークを使用して遠隔的に使用することもできる。
【００４６】
処理モジュール６は、チャンネル、ソースモデル、およびプロダクトモデルの特性Ｉｃに基づいて、第２のバイナリ要素のフローのビットを知るｘに関する記号の確率を計算するように適応されている。処理モジュール６は、このように計算された確率からｘに関する記号の最も起こりそうなフローを再構築するように、および、Ｍに関する記号のフローが符号化された場合にソースモデルからＭに関する記号のフローを再構築するように適応されている。
【００４７】
本発明による装置から導出される方法は、本明細書の記述の残りで説明され、特にそのような装置の動作のより良い理解を容易にする。
【００４８】
図２は、同期マーカの挿入を使用できる符号化方法の一例を示す。このプロセスは、ソース（Ｍに関する）をその入力で受け取るエンコーダ、たとえば、データのシーケンスを受け取るエンコーダで実現される。
【００４９】
ステップ１００で、データのシーケンスがＭに関するマーカを必要としないとき、プロセスはステップ１０４で継続する。他方、Ｍに関するマーカがデータのシーケンスに挿入される必要がない場合には、これらのマーカの周波数、サイズ、および値がエンコーダにより供給されてステップ１０２でそのマーカの挿入が容易にされる。
【００５０】
ステップ１０４では、（同期マーカを含んでも良いしまたは含まなくても良い）データのシーケンスがＭに関する変換（Ｍ進法変換）／バイナリ変換（２進法変換）を必要とするかどうかのチェックが行われる。これが当てはまらない場合には、それ故にデータのシーケンスはバイナリであり、ステップ１１２で算術符号化（図の例では擬似算術）を受ける（経る）。それ以外の場合、そのシーケンスのＭに関する変換／バイナリ変換はステップ１０６で発生する。ステップ１０８では、バイナリマーカが挿入されなければならない場合には、これらのマーカの周波数、サイズ、および値がエンコーダにより供給されてステップ１１０でこれらのマーカの挿入が容易にされる。
【００５１】
ステップ１１２では、Ｍに関するデータまたはバイナリデータのシーケンスは擬似算術符号化を受け、その擬似算術符号化の複雑さはパラメータＴにより制御される。Ｔが大きい場合には、擬似算術符号化は算術符号化と同一になる。これにより、ビットのストリームへのバイナリデータのシーケンスの圧縮が最大になる。
【００５２】
図３は、挿入された同期マーカを考慮に入れた復号化方法の一例を示す。この方法は、その入力で、同期マーカの周波数、サイズ、および値とともに、Ｍに関するソースまたはｘに関するソース（特にバイナリ）に関連するバイナリストリームおよび情報を受け取るデコーダで実現される。
【００５３】
ステップ１２０では、以下のような復号化のさまざまなモード、すなわち
ステップ１２４での瞬間復号化と、
本明細書の記述の残りで詳述されるようにステップ１２２で本発明による連続復号化と、
本明細書の記述の残りで詳述されるようにステップ１２６で本発明による最適復号化とが選択可能である。
【００５４】
ステップ１２８では、復号化の後に得られたデータのシーケンスがバイナリ変換／Ｍに関する変換を必要とするかどうかを判断するためにチェックが行われる。
【００５５】
そのようなことが当てはまる場合には、それ故にデータのシーケンスはバイナリであり、データのシーケンスがバイナリマーカを含むかどうかを判断するためのチェックがステップ１３０で行われる。そのようなことが当てはまる場合には、これらのマーカは、その周波数とサイズに関する情報を使用してステップ１３２で削除される。ステップ１３０またはステップ１３２の後に、データのシーケンスはステップ１３４でバイナリ変換／Ｍに関する変換を受ける。
【００５６】
ステップ１２８またはステップ１３４の後、データのシーケンスがＭに関するマーカを含むかどうかのチェックがステップ１３６で行われる。これが当てはまらない場合には、データシーケンス（またはソース）の復号化が完了される。それ以外の場合、マーカはステップ１３８で削除されてデータシーケンス（またはソース）が得られる。
【００５７】
図４〜図５は、データシーケンス（またはソース）のＭに関する変換／バイナリ変換と、バイナリ変換／Ｍに関する変換とのためのソースモデルを示している。
【００５８】
図４Ａは、４に関するソース、つまり、４に関するアルファベットからその値を取るソースの４個の記号のバイナリ表現を示す。このソースモデルは、ｑ＝2およびＭ＝４について図４Ａに図示されるように、奥行ｑのバイナリ系図である場合がある。変形例では、この系図（ツリー）は対応表によって表すことができる。黒のノード（節点）は系図の根と呼ばれ、白のノードは中間ノードであり、灰色のノードは系図の葉と呼ばれる。それぞれのＭに関する記号の確率Ｐはソースの定常確率に対応する。このバイナリ系図の枝上の遷移（不図示）の確率は定常確率から計算される。
【００５９】
図４Ｂは、独立したＭに関する記号のシーケンスをバイナリ記号のシーケンスに変換することを可能にするオートマトンを示す。また、このソースモデルは３つの状態のオートマトンの形式で図４Ｂにおいて表現可能である。つまり、Ｃ＝０は初期状態であり、Ｃ＝１とＣ＝２は中間状態である。変形例として、このソースモデルは同じ状態のトレリスの形式で図４Ｃにおいて表現可能である。つまり、左側でＣ＝０、右側で初期状態が中間状態Ｃ＝１とＣ＝２に連結され、左側の中間状態は右側の状態Ｃ＝０に連結されている。また、この例では、それぞれのｘに関する記号（このケースではバイナリ記号）の確率が、対応する遷移で示されている。
【００６０】
幾つかの独立ではないＭに関する記号を含むデータフローに対して、ソースの完全なモデルが、図５Ａに図示されるような連続ローカルモデルを連結することにより得られる。ローカルモデルは図４Ａに示されているような記号を含むフローのソースモデルに対応する。図５を参照して、２つの独立したＭに関する記号のフローに対して、ソースの完全なモデルは、次に来る系図の根を使って、すなわち図５Ａおよび図５Ｂの黒のノードにより表現される根を使って第１のバイナリ系図の葉の特定を行っている。このように、図５Ａはバイナリ系図を互いに組合せている。変形例として、図５Ｂは、第１のバイナリ系図を、その初期状態およびその最終状態として取る対応オートマトンに組合せている。このオートマトンは、依存するＭに関する記号のシーケンスをバイナリ記号のシーケンスに変換する働きをする。
【００６１】
図５Ａに従って、状態Ｃｋは、オートマトンがｋ個のバイナリ記号の生成の後になることがあると考えられるノードを規定する。考えられる（可能な）ノードの集合は、同じ状態ｋのノードと連結する一点鎖線によって図中で記号により表される。シーケンスＣ０  ．．．ＣＫはマルコフ連鎖であり、バイナリ記号の対応フローはこの連鎖の遷移の関数である。そのような遷移は、バイナリ記号Ｓｋの伝送を引き起こすという点でＳｋと呼ばれ、ソースモデルの状態Ｃｋ−１の集合と状態Ｃｋの集合との間で考えられる（可能な）遷移の集合を表現する。
【００６２】
このような確率オートマトンから、バイナリ記号のフローは、隠れたマルコフモデルによってモデリングできる。
【００６３】
それぞれのバイナリ記号と関連付けられた各々の定常確率を知っているので、つまり単一間隔［０，１［のセグメントの１つに対応する確率のそれぞれを知っているので、算術符号化によってバイナリ記号のシーケンスがこのシーケンスの間隔を決定できるようになる。後者は単一間隔のセグメントを表し、その下限は、下位サブ間隔に対応する記号シーケンスの確率の合計から引き出される。この間隔の幅は、その間隔に対応する記号シーケンスの確率により与えられる。用語「現在の間隔」は、間隔の計算の間に、すなわち状態Ｃｋに対応するサブシーケンスと関連付けられたサブセグメントの計算の間にシーケンスの一部と、それ故にシーケンスのその一部における現在の状態Ｃｋとに対応する間隔を言う。
【００６４】
算術符号化を実際的に実行することは、文献［１］すなわち以下の論文、
［５］「高速データ圧縮のためのソースコード化アルゴリズム（Ｓｏｕｒｃｅ ｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｆａｓｔ ｄａｔａ ｃｏｍｐｒｅｓｓｉｏｎ）。カリフォルニア、スタンフォード（Ｓｔａｎｆｏｒｄ Ｃａｌｉｆ．）」、ＲＦ．Ｐａｓｃｏ、カリフォルニア州スタンフォード、スタンフォード大学電気工学部博士号学位論文、１９７６年、
で最初に紹介され、文献［２］で再び取り上げられている。そのような実行で発生する問題は、非常に小さい実数で間隔を表現するために、高い数値精度に対するニーズである。その難題は、文献［３］中で説明されている間隔［０，１［内の実数のバイナリ表現に依存することにより解決できる。間隔［０，０．５［に属する任意の数ではその第１のビットが０に等しいのに対し、間隔［０．５，１［に属する任意の数ではその第１のビットが１に等しい。その結果、符号化プロセスの間、現在の間隔が［０，０．５［または［０．５，１［に完全に含まれている時に、対応するビットが送信され間隔のサイズが二倍になる。特定の処理が、１／２にまたがる間隔のため必要とされる。現在の間隔が１／２にまたがり［０．２５，０．７５［に完全に含まれる場合には、その間隔は単一ビットで特定できない。そのサイズはビットを送信せずに依然として２倍にされ、ビットの送信前にそのような演算の実行される回数（ｎ）が記憶される。ｎは、ビットの最後の伝送以降に実行されたリスケーリングの数である。ビットＵｉ＝ｕｉが送信される間隔に到達した時に、このビットの後には反対の値のビットをｎ倍したシーケンスが続く。
【００６５】
この技法を使用することにより、現在の間隔が条件「low＜０．２５＜０．５≦high」または「low＜０．５＜０．７５≦high」を満たすことが確実にされる。ここに、「low（ロウ）」および「high（ハイ）」はそれぞれ現在の間隔の「下限」および「上限」である。
【００６６】
算術符号化の原則は、状態Ｅが３個の変数、つまりlow、up（アップ）、およびリスケーリング数ｎｓｃｌで定義される確率オートマトンによりモデリングできる。この符号化の欠点は、ソースの定常分布が先験的に既知ではない場合、またはフローが多数のｘに関する記号を有する場合に、非常に多数の状態が存在できることである。精度低減（ｒｅｄｕｃｅｄ−ｐｒｅｃｉｓｉｏｎ）算術符号化とも呼ばれる擬似算術符号化は、文献［４］に説明されるように、圧縮性能を大幅に低下させずに考えられる（可能な）状態の数を削減できる。擬似算術符号化を実行するためには、実際の間隔［０，１［が整数間隔［０，Ｔ［に置き換えられる。整数Ｔは、複雑さと圧縮効率との間のトレードオフを制御する働きをする。つまり、Ｔが大きい場合には、間隔再分割がソースの分布に密接に続く。それに対して、Ｔが小さい（１に近い）場合、すべての可能な間隔再分割は事前に計算でき、これらの再分割はソースの分布の近似を表現するにすぎない。
【００６７】
表１に示されるように、状態間の遷移とビットの対応放出とのすべては事前に計算できる。それから、算術演算は表索引に置き換えられる。
【００６８】
バイナリ記号のシーケンスＳ１Ｋは、バイナリ系図によりビットストリームＵ１Ｎに変換される。この系図は、バイナリストリームの分布をモデリングするオートマトンまたはエンコーダモデルとして見なされ得る。記号の符号化は、ビットの放出が関連付けられる系図の頂点の選択肢を決定する。各ノードは算術エンコーダの状態Ｅに対応する。これらの状態間の連続遷移は、オーダー１のマルコフソース用のソースＰ（Ｓｋ｜Ｓｋ・ｉ）の分布に従う。Ｅｋをそれぞれの「記号インスタント」ｋでのオートマトン状態であるとする。算術符号化の場合と同様に、擬似算術エンコーダの状態Ｅｋは３つの変数すなわちlowＳｋ、upＳｋ、およびｎｓｃｌｋによって規定される。用語「lowＳｋ」(ロウＳｋ)および「upＳｋ」（アップＳｋ）は、シーケンスＳ１Ｋの符号化に対応する［０，Ｔ［の連続再分割の結果生じる間隔の限界を示す。ビットが放出されるたびに量ｎｓｃｌｋはゼロにリセットされ、ビットを放出しないでリスケーリングが行われるたびにその量は増分される。したがって、その量は、最後に放出されたビット以降に実行されたスケーリングの数を示す。ビットが放出されると、その後には反対の値のｎｓｃｌｋビットが続く。
【００６９】
間隔［０，Ｔ［の考えられる再分割が有限数あるため、ソースの知識がなくても擬似算術エンコーダの状態のすべてを事前に計算することが可能でなければならない。
【００７０】
一例として、表１は、バイナリソースについて精度Ｔ＝４の擬似算術エンコーダの状態、出力、およびすべての可能な遷移を提示している。第１の例では、列グループＣ１、Ｃ２が言及される。変数ｎｓｃｌｋの値は状態モデルに含まれない。この変数の増分だけが文献［４］と同様に表中の文字ｆにより信号で伝えられる。
【００７１】
エンコーダは、現在の間隔［lowＳｋ,upＳｋ［により規定される間隔［０，４［の整数再分割に対応する３つの可能な状態を有する。これらの再分割の選択肢について以下の文献、すなわち、
［６］「擬似算術符号化に基づく高速テキスト圧縮の設計および分析（Ｄｅｓｉｇｎ ａｎｄ Ａｎａｌｙｓｉｓ ｏｆ ｆａｓｔ ｔｅｘｔ ｃｏｍｐｒｅｓｓｉｏｎ ｂａｓｅｄ ｏｎ ｑｕａｓｉ−ａｒｉｔｈｍｅｔｉｃ ｅｎｃｏｄｉｎｇ）」、Ｐ．Ｇ．ＨｏｗａｒｄおよびＪ．Ｓ．Ｖｉｔｔｅｒ、データ圧縮会議（Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ）に於いて、９８〜１０７ページ、ユタ州スノウバード、１９９３年３月〜４月、
を参照する。入力バイナリ記号０の確率に応じて、現在の間隔［lowＳｋ,upＳｋ［は整数間隔に再分割される。列Ｃ２では入力バイナリ記号が０または１であるのかに応じて、現在の間隔［lowＳｋ,upＳｋ［の可能な整数間隔への再分割は、示されたビットの放出を生じさせる結果、またはオートマトンの次の状態を決定する前の適切なリスケーリングを生じさせる結果となる。
【００７２】
入力記号がバイナリ記号である場合には、状態の数は、列Ｃ２での０および１としてよりむしろ、列Ｃ３でバイナリ記号を「起こりそうでない」（ＬＰＳ）および「さらに起こりそうである」（ＭＰＳ）として識別することによりさらに削減可能である。これは、バイナリ記号の値よりむしろ各バイナリ記号の確率を考慮することに対応しており、ＭＰＳとＬＰＳは０ビットまたは１ビットのどちらかに対応している。バイナリソース確率の可能な組合せの数は削減される。これにより、特定の遷移を組合せること、およびオートマトンの状態を排除することが可能になる。
【００７３】
擬似算術エンコーダの連続状態のシーケンスＥ０ ．．．Ｅｋはマルコフ連鎖を形成し、そのエンコーダの出力はこの連鎖における遷移の関数である。
【００７４】
擬似算術符号化と同様に、復号化は、表２に示されているような有限数の状態ＥＮを使用して確率オートマトンによりモデリングできる。
【００７５】
算術デコーダの状態は２つの間隔、すなわち［lowＵｎ，upＵｎ［および［lowＳｋｎ,upＳｋｎ［によって定義される。間隔［lowＵｎ，upＵｎ［は、ビットＵ１ｎのシーケンスの受信により規定される間隔［０，１［のセグメントに対応している。間隔［lowＳｋｎ,upＳｋｎ［は、記号Ｓ１Ｋｎのシーケンスが復号化された時に得られる間隔［０，１［のセグメントである。この間隔は、符号化された記号ごとの符号化と同様に、それぞれの復号化されたバイナリ記号の確率を累積することにより更新される。それはエンコーダの動作を再現する。
【００７６】
算術エンコーダおよび算術デコーダは同期されていない。実際には、符号化の時に、記号の受信が必ずしもビットの放出という結果にならない。同様に、復号化の時に、ビットの読み取りが必ずしも記号の生成という結果にならない。したがって、符号化されるシーケンス内の第１の記号を読み取った結果がビットの放出にならない場合には、復号化の時に第１のビットの読み取りが第１の記号を復号化するのに十分となることもある。両方の間隔が、数値精度の問題を回避するために、符号化の時のようにスケーリングされる。
【００７７】
表２の例では、確率オートマトンはＴ＝４という値について定義されている。表は、Ｔ＝４のバイナリソースの擬似算術デコーダとＭＰＳ／ＬＰＳの簡略化とのために状態、遷移、および出力を与える。
【００７８】
Ｅｎを「ビットインスタント」ｎの時に、つまり受信されたビットＵｎの処理の瞬間の時にオートマトンの状態とする。この状態は間隔［lowＵｎ,upＵｎ［および［lowＳｋｎ,upＳｋｎ［の値により定義される。（最も起こりそうなＭＰＳ記号の確率により列Ｋ１に示される）ソースの定常分布に応じて、現在の間隔［lowＳｋｎ,upＳｋｎ［は、整数間隔に再分割される。入力ビットが列Ｋ２でＵｎ＝０であるのかまたは列Ｋ３でＵｎ＝１であるのかに応じて、現在の間隔［lowＳｋｎ,upＳｋｎ［の整数間隔への可能な再分割の結果が、示されたＭＰＳ記号またはＬＰＳ記号の放出になり、またはオートマトンの次の状態を決定する前に適切なリスケーリングになる。
【００７９】
表１および表２の確率オートマトンを使用して、エンコーダは状態Ｅｋ＝１およびＥｎ＝１でそれぞれ開始する。
【００８０】
符号化方法／復号化方法で使用するために、および対応するエンコーダ／デコーダでの実行のために、さまざまなモデルが予想される。このようにして、ソースモデルとエンコーダの積から生じるモデル、またはソースモデルとデコーダとの積から生じるモデルであることがある、いわゆる「プロダクト」モデルが予想される。
【００８１】
一般的には、プロダクトモデルの状態は、２つのモデル（ソースとエンコーダまたはソースとデコーダ）のそれぞれの状態に含まれる情報を収集しなければならない。一般的な場合では、「プロダクト」モデルの状態−空間のサイズは先験的に知り得ない。それは、バイナリソースモデルとパラメータＴから計算可能である。
【００８２】
ソース／エンコーダのプロダクトモデルに関して、プロダクトモデルの各遷移により生成される各バイナリ要素の中のビット数はランダムであるので、第２のバイナリ要素のシーケンスとプロダクトモデルの状態との間の依存性の構造はランダムである。この依存性構造を「捕捉（キャプチャ）する」ために、プロダクトモデルによるエンコーダの状態Ｘｋによって表されるマルコフプロセスがカウンタＮｋにより増大されて、次の依存性構造（Ｘ，Ｎ）＝（Ｘ１，Ｎ１） ．．．（ＸＫ，ＮＫ）が得られる。プロダクトモデルの各状態Ｘｋは、エンコーダモデルの状態と、ソースモデルの状態と、第ｋ番目の記号すなわち（Ｘｋ，Ｎｋ）＝（lowＳｋ，upＳｋ，Ｃｋ，Ｎｋ）が符号化された時に放出されるビット数とによって定義される。これは、図８に図で描かれている依存性の構造をもたらす。この構造に従って、バイナリ記号Ｓ１ＫのシーケンスはビットＵ１ＮＫのシーケンスに変換される。ここに、Ｎｋは、Ｋ個の記号が符号化された時に放出されるビットの数である。状態Ｘｋ−１および入力記号Ｓｋを考えれば、プロダクトモデルは、放出されなければならないビットＵＮｋｌ＋１からＵＮｋを指定するとともに次の状態Ｘｋを指定する。ビットは特定の遷移により放出されなくてもよい。（Ｘｋ，Ｎｋ）＝（lowＳｋ，upＳｋ，Ｃｋ，Ｎｋ）と、トレリス（Ｘｋ＋１，Ｎｋ＋１）＝（lowＳｋ＋１，upＳｋ＋１，Ｃｋ＋１，Ｎｋ＋１）の次の状態との間での遷移の確率は、バイナリソースモデルＰ（Ｃｋ＋１｜Ｃｋ）＝Ｐ（Ｓｋ＋１｜Ｃｋ）により与えられる。第２のバイナリ要素ＹＮｋ−１＋ｌからＹＮｋは、第１のバイナリ要素ＵＮｋ−ｌ＋１からＵＮｋが放出された時に伝送チャンネルの出力で得られる。そのような第２のバイナリ要素は第１のバイナリ要素についての観察である。
【００８３】
ソースモデルとエンコーダモデルとから導かれるプロダクトモデルの一例は図６および図７で与えられる。図６Ａの表で規定されたプロダクトモデルの例は、図４Ｃのソースモデルと表１のエンコーダモデルとの積から導かれる。理論的には、この積から生じる状態−空間のサイズは、２つのモデル（ソースおよびエンコーダ）の状態−空間寸法の積により与えられる。しかしながら、より少ない数の状態を生じさせる簡略化が生じる。
【００８４】
列Ｃ３の簡略化された状態モデルを使用して表１（Ｔ＝４）の算術エンコーダモデルは、図７Ａおよび図７Ｂにトレリス形式で表現され、図７Ａは確率０．６３≦Ｐ（ＭＰＳ）に対応し、図７Ｂは確率０．３７≦Ｐ（ＭＰＳ）≦０．６３に対応する。これらの図のどちらかはバイナリソースの確率に依存して使用され得る。Ｍに関するソースに基づく変換から生じたバイナリソースの確率は、このバイナリソースのモデルの状態Ｃｋに依存する。このようにして、ソース／エンコーダのプロダクトモデルの遷移はソース分布の関数である。図６Ａの表は、図４Ｃのソースモデルの状態Ｃｋと、遷移Ｓｋの確率（図４Ｃの遷移Ｓｋ＝０およびＳｋ＝１はＳｋ＝ＬＰＳおよびＳｋ＝ＭＰＳとして変更されている）と、ソース確率の関数として図７Ａと図７Ｂに描かれているエンコーダモデルの遷移の確率との関数として構築されている。図６Ａの列Ｍ１だけが、ソースモデルおよび対応エンコーダの状態変数により、列Ｍ２で規定されたプロダクトモデルの４つの状態を含む。ソースモデルは３つの状態を有しエンコーダモデルは２つの状態を有するので、プロダクトモデルは最大６つの状態を有する。実際には、図７Ａと図７Ｂを用いて後述されるように簡略化が発生する。図７Ａは、エンコーダの状態Ｅｋ＝０に関してソースモデルの確率０．６３＜Ｐ（ＭＰＳ）に対しエンコーダの状態Ｅｋ＝１で継続できることを示している。しかしながら、図７Ｂは、エンコーダの状態Ｅｋ＝０から状態Ｅｋ＝１に達することは可能ではないことを示している。
【００８５】
したがって、図６Ａのプロダクトモデルでは、ソースモデルおよびエンコーダモデル（Ｅｋ＝１、Ｃｋ＝１）および（Ｅｋ＝１，Ｃｋ＝２）の状態のペア（対）に対応するプロダクトモデルＸｋ＝４およびＸｋ＝５の状態は、ソースモデルの確率が０．３７＜Ｐ（ＭＰＳ）＜０．６３になるような確率状態に対して存在する。列Ｍ３および列Ｍ４は、入力記号（ＭＰＳまたはＬＰＳ）に対して、放出されたビットとプロダクトモデルの次の状態とを示す。
【００８６】
図９Ａまたは図９Ｂによるソース／デコーダモデルに対して、このプロダクトモデルの状態は、ソースモデルおよびデコーダモデルの状態情報を収集しなければならない。したがって、このプロダクトモデルの状態Ｘｎは、Ｘｎ＝（lowＵｎ，upＵｎlowＳＫｎ，upＳＫｎ，ＣＫｎ）によって規定される。ここに、Ｋｎは、ｎ個のビットが受信された時に復号化される記号の数である。プロダクトモデルの各遷移によってもたらされた記号の数はランダム（任意）である。その結果、第２のバイナリ要素のシーケンスと復号化された記号との間の依存性構造はランダムである。ソース／デコーダのプロダクトモデルのマルコフ連鎖Ｘ１．．．Ｘｎは、カウンタ変数Ｋｎにより増加され、図１０に示されている依存性構造を生じさせるマルコフ連鎖（Ｘ，Ｋ）＝（Ｘ１，Ｋ１）．．．（Ｘｎ，Ｋｎ）を与えるようにしている。この構造に従って、ビットＵ１Ｎのシーケンスが記号Ｓ１ＫＮのシーケンスに変換される。ここに、Ｋｎは、Ｎ個のビットが受信された時に復号化される記号の数である。状態Ｘｎおよび入力ビットＵｎ＋１を考えれば、オートマトンは、バイナリ記号ＳＫｎ＋１Ｋｎ＋１のシーケンスをもたらし、次の状態Ｘｎ＋１を指定する。トレリスの（Ｘｎ，Ｋｎ）と（Ｘｎ＋１，Ｋｎ＋１）との間の遷移の確率はバイナリソースモデルに依存する。それらは添付の式（１７）により与えられる。ソース／エンコーダモデルの場合と同様に、このモデルの状態の簡略化は、使用されたデコーダモデルとソースモデルとに依存して可能である。図９Ａまたは図９Ｂの例では、使用されたソースモデルは図４Ｃのソースモデルであり、デコーダモデルは表２のデコーダモデルである。
【００８７】
算術符号用のロバスト復号化方法は、以前に説明された依存性モデルに基づいている。
【００８８】
ロバスト復号化方法の第１の実行が図１１に描かれている。
【００８９】
関連される数学的展開については付録１を参照する。
【００９０】
デコーダは、その入力で復号化されるビットのストリームを受け取る。ソースモデルと、復号化される受信済みのビットの数を表現する変数Ｎと、観察された第２のビット（すなわち第２のバイナリ要素）Ｙｎを知っている第１のビット（つまり第１のバイナリ要素）Ｕｎを放出した確率Ｐ（Ｕｎ／Ｙｎ）とはデコーダ用の入力データであり、すなわち、ほんの一例としては、これらのデータは、復号化されるビットストリームとともに入力で受信可能であり、または、デコーダによりアクセス可能なメモリから読み取り可能である。確率Ｐ（Ｕｎ／Ｙｎ）は、チャンネル特性から得ることができる。
【００９１】
ＭＡＰ（事後的な最大値Ａ）基準は、付録１の式（３）によって示されるように、使用可能な観察Ｙに基づいたプロセスＸの最適ベイジアン推定に対応している。最適化はすべての可能な「シーケンス」について実行される。この第１の実行では、この基準は、記号クロックプロセスと見なすことができるプロセス（Ｘ，Ｎ）の非表示状態と、観察されたビットシーケンスを考えればビットクロックプロセスと見なすことができるプロセス（Ｘ，Ｋ）の非表示状態との推定に適用される。推定は、ビットクロックプロセスまたは記号クロックプロセスのどちらかとして実行され得る。その実行が単純であることの理由から、ビットクロック推定が好まれる。
【００９２】
その場合には、非表示状態（Ｘ，Ｋ）＝（Ｘ１，Ｋ１） ．．．（ＸＮ，ＫＮ）の集合の推定は、チャンネル出力での観察Ｙ１Ｎを考えれば、復号化された記号Ｓ＝Ｓ１．．．ＳＫｎ．．．ＳＫＮの対応シーケンスの推定と同等である。最良のシーケンス（Ｘ，Ｋ）は、式（４）を使用してペア（Ｘｎ，Ｋｎ）での局所的な確率から獲得可能である。
【００９３】
Ｐ（Ｘｎ，Ｋｎ｜Ｙ）の計算は、解凍式（５）を使用して実行でき、αは正規化ファクタ（正規化係数）を示している。マルコフ連鎖の依存性によって、以下の文献、すなわち、
［７］「記号誤り率を最小にするための線形符号の最適復号化（Ｏｐｔｉｍａｌ ｄｅｃｏｄｉｎｇ ｏｆ ｌｉｎｅａｒ ｃｏｄｅｓ ｆｏｒ ｍｉｎｉｍｉｚｉｎｇ ｓｙｍｂｏｌ ｅｒｒｏｒ ｒａｔｅ）」、Ｌ．Ｒ．Ｂａｈｌ、Ｊ．Ｃｏｃｋｅ、Ｆ．Ｊｅｌｉｎｅｋ、およびJ．Ｒａｖｉｖ、ＩＥＥＥ変換理論に関する報告書（ＩＥＥＥ ｔｒａｎｓ．ｏｎ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｙ）、０２：２８４〜２８７、１９７４年３月、
の中で説明されたＢＣＪＲアルゴリズムに基づいて、上記の式の右辺における両方の項の帰納的な計算が可能となる。
【００９４】
したがって、ステップ３００では、トレリスが、たとえば図９Ａのソース／デコーダモデルを使用して最初に構築され、対応する確率がトレリスの遷移ごとに計算される。このように、プロダクトモデルに基づいて、順方向の掃引が、最初の状態から最後の状態へプロダクト状態図（積状態図）の遷移によって連結される状態の連続的な構築を可能にする。それぞれの状態は、初期状態からの第２のバイナリ要素のフローの中で過去のビットの一定数に対して予想される数の復号化された記号を規定する。この同じステップの間にＢＣＪＲアルゴリズムの順方向の掃引によって、３つの条件付き確率の積、すなわち、再帰的確率、（式１７で示されソースモデル内で過去に遷移確率Ｐ（Ｓｋ｜Ｃｋ・１）の積を表すような）プロダクトモデルにより与えられた状態（ｘｎ−１，ｋｎ−１）と状態（ｘｎ，ｋｎ）との間の遷移の確率、および、第２のバイナリ要素Ｙｎを与えられた状態（ｘｎ−１，ｋｎ−１）と状態（ｘｎ，ｋｎ）との間の遷移をトリガする（０または１であってもよい）ビットＵｎを放出した確率の積のｘｎ−１，ｋｎ−１の可能な値の集合の合計として分解項Ｐ（Ｘｎ＝ｘｎ，Ｋｎ＝ｋｎ｜Ｙ１ｎ）が計算可能になる（式（６））。後者の確率はチャンネル特性から得られる。再帰的計算は、開始状態（０，０）で初期化され、ビット−クロックのｎ＝１ ．．．Ｎを使用して任意の可能な状態（ｘｎ，ｋｎ）についてＰ（Ｘｎ，Ｋｎ｜Ｙｎ１）の計算を可能にする。このようにして、この順方向の掃引はモプロダクトデルのトレリスの構築と、連続的確率Ｐ（Ｘｎ，Ｋｎ｜Ｙｎ１）とを容易にし、インスタント（瞬間）ｎごとに第２のバイナリ要素ストリームＹ１ｎのビットを与えられた一定の状態（Ｘｎ，Ｋｎ）で終了の計算を容易にする。
【００９５】
ステップ３０２では、逆方向の掃引は、Ｎから１まで連続的なビットインスタントのそれぞれでの可能な状態（ｘｎ，ｋｎ）について分解項Ｐ（ＹＮｎ＋１｜Ｘｎ＝ｘｎ，Ｋｎ＝ｋｎ）を得る働きをする。その項は、３つの条件付き確率の積、つまり、すべての可能な「最後の状態」（ＸＮ，ＫＮ）について初期化された再帰的確率、プロダクトモデルにより与えられた状態（Ｘｎ＋１，Ｋｎ＋１）と状態（Ｘｎ，Ｋｎ）との間の遷移の確率，および、第２のバイナリ要素Ｙｎ＋１を与えられた状態（Ｘｎ＋１，Ｋｎ＋１）と状態（Ｘｎ，Ｋｎ）との間の遷移をトリガするビットＵｎ＋１を放出した確率の積の合計として計算される（式（７））。前記のように、後者の確率はチャンネルモデルから得られる。したがって、この逆方向の掃引によって、連続確率Ｐ（ＹＮｎ＋１｜Ｘｎ＝ｘｎ，Ｋｎ＝ｋｎ）の計算と、Ｎから１までのインスタントｎごとに一定の状態（Ｘｎ，Ｋｎ）を知って第２のバイナリ要素ストリームＹ１ｎのビットを観測する計算とが可能になる。
【００９６】
記号Ｋの数が既知であるとき、ステップ３０２で逆方向の掃引の間に終了制約が追加できる。したがって、記号ＫＮ＝Ｋの正しい数につながらないトレリスのすべての経路が抑制される。このように、逆方向の掃引は、最終の状態から最初の状態へプロダクト状態図からの状態の連続的な抑制を含んでおり、そのプロダクト状態図では第２のバイナリ要素のストリームにおけるビットの一定数に対して記号の予想数が記号の既知の最大数と異なっている。それ故に、ステップ３００での第１の掃引は、トレリスの最初の状態で開始し、トレリスのさまざまなセクションを連続的に構築する。この順方向の掃引の間に、どの経路が終了制約を満たさないのかを知ることはできない。いったん順方向の掃引が終了すると、制約を満たさないトレリスの最後のセクション（ｎ＝Ｎ）の状態が抑制される。次に、逆方向の掃引によって、終了しないすべての分岐の抑制が可能になる。
【００９７】
ステップ３０４では、順方向の掃引および逆方向の掃引の得られた確率が１からＮの範囲のｎの値ごとに積の形式で結合されて、状態ｎごとに確率Ｐ（Ｘｎ，Ｋｎ｜Ｙ）が得られる。このように、構築されたトレリスの遷移に関連付けられた確率が推定される。
【００９８】
ステップ３０６では、式（４）の積が１からＮの範囲のｎを使用して確率Ｐ（Ｘｎ，Ｋｎ｜Ｙ１ｎ）で実行される。この積はこれらの確率のさまざまな組合せに対して実行される。したがって、最大の確率Ｐ（Ｘ，Ｋ｜Ｙ）が保持され、その積を構成する確率Ｐ（Ｘｎ，Ｋｎ｜Ｙ）はトレリス内で最も起こりそうな経路を決定するために使用される。トレリスとソース／デコーダのプロダクトモデルの対応表とに基づいて、その経路に対応する記号を決定すること、および記号Ｓ１Ｋのシーケンスを再構築することが可能である。
【００９９】
別の可能な実行では、推定が行われたトレリスが、ソース／デコーダのプロダクトモデルと観察されたビットのシーケンスの長さＮとに基づいて事前に計算され記憶される。したがって、図１２を参照して、ソース／デコーダモデルとＫおよびＮの値とに基づいて、トレリスが単一の順方向の掃引においてステップ４００で構築され、ステップ４０２で逆方向の掃引によって簡略化される。このトレリスは、ソース／デコーダモデルと値Ｋおよび値Ｎとが同じであるビットストリームが出現するたびに、使用するメモリ内に記憶される。
【０１００】
Ｎ＝６ビットを含む受信ビットのストリームに対して、Ｋ＝７であることが判明した既知の数の記号と図９Ａで描かれるようなソース／デコーダモデルとについて、格子構築が図１３で図示される。格子は、それぞれの状態（Ｘｎ，Ｋｎ）で複数のペアの値（Ｘｎ，Ｋｎ）を含む。たとえば、ペア（Ｘ１，Ｋ１）は、放出されたビットＵ１が０または１の値を有するか否かに依存して、値（１，１）または値（２，１）を取ることができる。
【０１０１】
（トレリスと同じモデルを有し、トレリスと同じＫおよびＮの値を有する）ビットのストリームが出現するたびに、順方向の掃引と逆方向の掃引とが、たとえば平行で、ステップ４０４およびステップ４０６でのビットストリームで実行される。確率Ｐ（Ｘｎ，Ｋｎ｜Ｙｎ１）およびＰ（Ｙｎ＋１Ｎ｜Ｘｎ，Ｋｎ）は、式（６）および（７）で示されるように計算される。これらの確率の積は、ｎの値ごとにステップ４０８で得られ、トレリスのそれぞれの遷移に対応する。次に、ステップ４１０では１からＮの範囲のｎに対して確率の積が（４）に示されるように計算されて、確率Ｐ（Ｘ，Ｋ｜Ｙ）が得られる。トレリス上で最も起こりそうな経路と記号の対応シーケンスとを決定するために、これらの確率Ｐ（Ｘ，Ｋ｜Ｙ）のうち最大のものが保持される。
【０１０２】
図１３の例に従って、最大の確率Ｐ（Ｘ，Ｋ｜Ｙ）を得る最も起こりそうな経路は太字で記されている。状態（Ｘ０，Ｋ０） ．．．（ＸＮ，ＫＮ）のシーケンスは、表８Ａの読み取りによって、この経路に対応する記号シーケンスの決定を可能にする。
【０１０３】
擬似算術符号を復号化する最適な方法が与えられている。この方法は、たとえば図１３のような推定トレリスの作成および操作を必要とする。このトレリスのサイズは、ソース／デコーダのプロダクトモデルの状態の数（たとえば図９Ａのソース／デコーダのプロダクトモデルに対して４つの状態が可能である）と、それぞれのビットインスタントｎで変数Ｋｎが取ることができる値の振幅とに依存する。ソース／デコーダのプロダクトモデルの状態の数はそれ自体バイナリソースモデルと、擬似算術符号化精度パラメータＴとに依存する。したがって、擬似算術エンコーダの圧縮効率と推定方法の複雑さとの間でのトレードオフを制御するために、パラメータＴの値を制御することは十分である。４と同じように小さなＴの値は、たとえば、妥当な過剰率を生成する。しかしながら、最大圧縮が必要とされる場合には、Ｔははるかに大きな値を有さなければならず、Ｔの最小必須値はソースの分散に依存する。このような場合の大部分では、Ｔの値があまりにも大きすぎて前述された最適な推定方法を使用することができない。また、ソース／デコーダのプロダクトモデルの状態の数はあまりにも大きすぎてそれらの状態を事前に計算することもできない。
【０１０４】
算術符号化と擬似算術符号化とに適用可能な推定方法は、選択された精度Ｔに関わりなく、つまり選択された圧縮効率に関わりなく、ここで説明される。
【０１０５】
この方法は、過去に見られたものと同じソースモデル、エンコーダモデル、およびデコーダモデルに依存する。エンコーダモデルおよびデコーダモデルの状態の数があまりにも大きすぎてそれらを事前に計算できないので、対応する推定トレリスもまた構築できない。それ故に、以下に提案される推定方法は、系図と見なされる推定トレリスの部分集合の調査に基づいている。この方法は逐次推定法と呼ばれる。それは、ソース／エンコーダのモデルに基づいて適用可能であり、「記号クロック」を使って、つまり検出される記号の数に従って増分されるカウンタを使って逐次計算を実行できる。また、それは、ソース／デコーダのモデルに基づいて適用可能であり、「ビットクロック」を使用して、つまり復号化されるビットの数に従って増分されるカウンタを使用して逐次計算を実行できる。この第２の推定方法は、ほんの一例として、バイナリソースに対して提示される。また、それは、Ｍに関するソース（Ｍ＞２）にも適用可能である。
【０１０６】
図１４は、いわゆる記号クロックの逐次推定法を示し、すなわち、ソースモデル／エンコーダに基づいている。したがって、ソース／エンコーダモデルの依存性構造を示す図８に従って、ビットのストリームの状態（Ｘ，Ｎ）のシーケンスを推定することは、これらの状態の間の遷移のシーケンスを推定すること、つまり、チャンネル出力での観察Ｙを与えられたシーケンスＳを推定することと同等である。これは、（８）に提示される数学公式化によって表される。ここに、αは正規化係数を示す。（Ｔという大きな値に対して）最適な算術符号化の場合では、放出されたビットが均一かつ独立に分布されるので、この正規化係数はＰ（Ｕ１Ｎ）／Ｐ（Ｙ１Ｎ）＝１である。
【０１０７】
ステップ５００では、記号インスタントｋごとに第２のバイナリ要素Ｐ（Ｓ１ｋ／Ｙ１Ｎｋ）のフローのビットを知って記号のシーケンス（１からｋ）を復号化する確率は、式（９）の分解を使って単一順方向の掃引で計算可能である。ここに、Ｎｋは状態Ｘｋにあるときに放出されたビットの総数である。式（１）で定義されたバイナリソースモデルを考慮に入れメモリレスチャンネルを考えると、そのモデルの状態に対応する第２のバイナリ要素を観察する確率は、この状態に対して第１のバイナリ要素だけに依存し、その確率は式（１０）に示されるように書き換え可能である。
【０１０８】
計算は、バイナリソースの場合では２つの可能な値０または１を取ることができるＳ１＝ｓ１、とＭに関するソースの場合ではＭ個の可能な値を取ることができるＳ１＝ｓ１を使用して（１１）に示されるように初期化される。Ｃ１はソースモデルの初期状態である。考慮されるメモリレスチャンネルに対して、このチャンネルにより生じるノイズをモデリングする式の第２の項は、送信された第１のバイナリ要素Ｕｎについて第２のバイナリ要素Ｙｎを観察する確率の積として、ソース／エンコーダモデルの一定の状態Ｘｋについて式（１２）により与えられる。この初期化に基づいて、式（１０）を使って連続的な記号インスタントｋごとにＰ（Ｓ１ｋ／Ｙ１Ｎｋ）を計算する。
【０１０９】
すべての可能な記号シーケンスが考慮されると、推定トレリスのサイズが記号Ｋの数とともに急激に増加する。このように、ステップ５０２によって、１からｘ１までの範囲の記号Ｋの数について確率Ｐ（Ｓ１ｋ／Ｙ１Ｎｋ）の計算が許容される。値ｘ１以上からの記号に対して、所望レベルの複雑さで推定トレリスを維持するために、プルーニング（不要なものの削除）がステップ５０４で実行される。ｘ１は記号Ｋの数以下の整数である。
【０１１０】
ステップ５０４でのプルーニングにはさまざまな実行が含むことができる。一例として、２つの実行が後述される。その実行は組合せ可能であり、または別々に利用可能である。
【０１１１】
このように、ステップ５０４でのプルーニング動作の第１の実行では、状態（Ｘｋ，Ｎｋ）のＷ個の最も起こりそうなノードだけが数ｋ＝ｘ１から開始して選択され、計算された確率（尤度と呼ばれる）が顕著であることを確実にするようにしている。Ｗの値は、使用可能なメモリリソースに依存している。したがって、状態（Ｘｋ，Ｎｋ）ごとに、第２のバイナリ要素Ｐ（Ｓ１ｋ／Ｙ１Ｎｋ）のフローのビットを知って記号のシーケンス（１からｋまで）を復号化する計算済み確率のうちでＷ個の最大確率だけが選択され記憶される。変形例では、この制約を精緻化することにより推定の正しい終了を確実にすることができる。それ故に、（記号クロックに対応する）Ｎｋの可能な値ごとにｗ個の最も起こりそうなノードが選択され保持される。Ｎｋは、符号化の間に、符号化されるｋ個の記号のために放出されたビットの数である。Ｗとｗとの関係は、もっとも起こりそうなシーケンスおよび最も起こりそうもないシーケンスＳｌｋのそれぞれの確率に依存して、ＮｋｍａｘおよびＮｋｍｉｎとともに式（１９）で与えられる。
【０１１２】
ステップ５０４でのプルーニングにおける第２の実行では、プルーニング基準は経路の尤度に適用されるしきい値に基づいている。経路の尤度は式（８）（記号クロック）で与えられる。この式では、項Ｐ（Ｙ｜Ｕ）は式（１２）に示されるようにチャンネルモデルにリンクされている。Ｐ（Ｙｎ＝ｙｎ｜Ｕｎ＝ｕｎ）は、ビットｕｃが送信されたことを知ってビットｙｎが観察される確率を表し、またはビットｕｎが放出されたことを知って観察されたビットが誤りである確率と等価なビットｙｎを受信する確率を表している。ｐを、推定中にチャンネル上で許容されるように任意に決定されたバイナリエラーの平均確率とする。プルーニングは、チャンネル出力時のバイナリエラーの平均確率がｐより大きいすべての経路を抑制することを含んでいる。したがって、それぞれの記号インスタントＮｋで、プルーニング基準は、Ｐ（ＹＮｋ｜ＵＮｋ）＜（１−Ｐ）Ｎｋが確認された推定トレリス上のすべての経路が抑制されるように、確率Ｐ（ＹＮｋ｜ＵＮｋ）と比較されたしきい値ｐを含んでいる。第２のバイナリ要素Ｐ（Ｓ１ｋ／Ｙ１Ｎｋ）のフローのビットを知って最小しきい値ｐより高い確率Ｐ（ＹＮｋ｜ＵＮｋ）から計算された記号のシーケンス（１からｋ）を復号化する確率だけが記憶される。
【０１１３】
構成単位の値ｋを増分した後、記号Ｎｋ（ｋ＞ｘを満たす）の数に対する確率Ｐ（Ｓ１ｋ／Ｙ１Ｎｋ）がステップ５０６で計算される。ステップ５０４で実行されたプルーニングは、この新しい記号インスタントＮｋについて繰り返される。ステップ５０４およびステップ５０６は、値Ｋまで増分される値ｋについて実行される。ステップ５１０では、いったん値Ｋになると、限界に近い後天的な確率Ｐ（Ｓ１K／Ｙ１ＮK）はすべての可能なシーケンスｓ１Ｋについて知らされる。最も起こりそうなシーケンスｓ１Ｋ、つまり、得られた推定トレリスの可能なシーケンスの中で確率Ｐ（Ｓ１K／Ｙ１ＮK）が最高であるシーケンスが選択される。
【０１１４】
ビットＮの数が既知であるとき、それは推定トレリスの終了に対する制約を構成することができ、制約Ｎを満たさない経路は考慮されない。
【０１１５】
図１５は、いわゆるビットクロックの連続推定方法を示し、つまりソース／デコーダモデルに基づいている。したがって、ソース／デコーダモデルの依存性構造を示す図１０に従って、ビットのストリームを得るために状態（Ｘ，Ｋ）のシーケンスの推定は、これらの状態の間の遷移のシーケンスの推定、つまりチャンネル出力での観察Ｙを与えるシーケンスＳの推定と等価である。これは、（１３）で提示された数学公式化により表される。ここに、αは正規化係数を示す。（Ｔの大きな値に対して）最適な算術符号化の場合では、放出されるビットが一様かつ独立に分布されるので、この正規化係数はＰ（Ｕ１ｎ）／Ｐ（Ｙ１ｎ）＝１である。
【０１１６】
ステップ６００では、（後に定義される）ビットｎごとに第２のバイナリ要素Ｐ（Ｓ１K／Ｙ１ｎ）のフローのビットを知ってＫｎ個の記号のシーケンスを復号化する確率は、式（１３）の分解を使用して単一の順方向の掃引で計算され得る。ここに、Ｋｎは状態Ｘｎにおけるビットｎの受信時に復号化された記号の総数である。状態（Ｘｎ，Ｋｎ）と状態（Ｘｎ＋１，Ｋｎ＋１）との間の遷移の確率を（２）で定義するバイナリソースモデルを考慮に入れると、記号シーケンスＳ１Ｋｎを獲得する確率Ｐ（Ｓ１Ｋｎ）は式（１５）を使用して式（１４）に従って再帰的に表される。メモリレスチャンネルを考慮すること、つまりモデルの状態だけに対応する第２のバイナリ要素を観察する確率を考慮することは、この状態について送信された第１のバイナリ要素に依存し、確率Ｐ（Ｙ１ｎ／Ｕ１ｎ）は、（１６）に示されているような確率Ｐ（Ｓ１Ｋｎ／Ｙ１ｎ）を得るために書き換えて使用可能になる。
【０１１７】
図１４と同様に、式（１６）による確率Ｐ（Ｓ１Ｋｎ／Ｙ１ｎ）の計算は、バイナリソースの場合では２つの可能な値０または１を取り、および、Ｍに関するソースの場合ではＭ個の可能な値を取るｎ＝１、Ｓｌ＝ｓｌについて初期化される。Ｃ１はソースモデルの初期状態である。この初期化に基づいて、式（１６）を使って連続的なビットインスタントｎごとにＰ（Ｓ１ｋ／Ｙ１Ｎｋ）を計算する。
【０１１８】
記号の全ての可能なシーケンスが考えられるので、推定トレリスのサイズは、推定される記号Ｋの数とともに急激に増加する。このように、ステップ６０２は、１からｘ２の範囲のビットの数Ｎについてステップ６００で確率Ｐ（ＳｌＫｎ／ＹｌＮ）の計算を容易にする。ここに、ｘ２はビットのしきい値の数を示す整数である。値ｘ２以上からのビットに対して、所望なレベルで推定トレリスの複雑さを維持するために、プルーニングがステップ６０４で実行される。
【０１１９】
ステップ６０４でのプルーニングは、図１４のステップ５０４の実行に対応するさまざまな実行を含んでいる。そのような実行は組合せ可能であり、または別々に利用可能である。
【０１２０】
このように、ステップ６０４でのプルーニング動作の第１の実行では、状態（Ｘｎ，Ｋｎ）のＷ個の最も起こりそうなノードだけが、計算された確率（尤度と呼ばれる）が顕著であることを確実にするために、数ｎ＝ｘ２から開始して保持される。したがって、それぞれの状態（Ｘｎ，Ｋｎ）に対して、第２のバイナリ要素Ｐ（Ｓ１ｋ／Ｙ１Ｎｋ）のフローのビットを知ってＫｎ個の記号のシーケンスを復号化する計算済み確率のうちＷ個の最大確率だけが記憶される。
【０１２１】
変形例では、（ビットクロックに対応する）Ｋｎの可能な値ごとにｗ個の最も起こりそうなノードだけを保持することが可能である。Ｋｎは、復号化の間に受信されたｎ個のビットについて放出された記号の数である。Ｗとｗとの関係は、最も起こりそうなシーケンスおよび最も起こりそうもないシーケンスＳ１ｋの確率にそれぞれ依存して、ＫｎｍａｘおよびＫｎｍｉｎを使って（２０）で与えられる。
【０１２２】
ステップ６０４でのプルーニングの第２の実行では、プルーニング基準は経路の尤度に適用されたしきい値に基づいている。経路の尤度は式（１３）（ビットクロック）により与えられる。この式では、用語Ｐ（Ｙ｜Ｎ）は、式（１６）に示されるように、チャンネルモデルにリンクされている。図１３について提案されるように、プルーニングは、チャンネル出力でのバイナリエラーの平均確率がｐより大きいすべての経路を抑制することを含んでいる。したがって、それぞれのビットインスタントｎでのプルーニング基準は、Ｐ（Ｙｎ｜Ｕｎ）＜（１−ｐ）ｎが確認された推定トレリス上のすべての経路が抑制されるように、確率Ｐ（Ｙｎ｜Ｕｎ）に比較されたしきい値ｐを含んでいる。第２のバイナリ要素Ｐ（Ｓ１Ｋｎ／Ｙ１ｎ）のフローのビットを知って最小のしきい値ｐより高い確率Ｐ（Ｙｎ｜Ｕｎ）から計算された次の記号を復号化する確率だけが記憶される。それ故に、それぞれのビットインスタントｎｓで、プルーニング基準Ｐ（Ｙｎ｜Ｕｎ）＜（１−ｐ）ｎが満たされた推定トレリス上のすべての経路が抑制される。
【０１２３】
構成単位の値ｎを増分した後に、ビットｎ（ｎ＞ｘ２を満たす）の数についての確率Ｐ（Ｓ１Ｋｎ／Ｙ１ｎ）がステップ６０６で計算される。ステップ６０４で実行されるプルーニングはこの新しいビットインスタントＫｎについて繰り返される。ステップ６０４およびステップ６０６は、値Ｎまで増分された値ｎについて実行される。ステップ６１０では、いったん値Ｎに達すると、最も起こりそうなシーケンスＳ１Ｎが選択され、つまり、得られた推定トレリスの可能なシーケンスのうちで確率Ｐ（Ｓ１Ｋ／Ｙ１Ｎ）が最大であるシーケンスが選択される。
【０１２４】
推定の最後には、限界に近い後天的な確率Ｐ（Ｓ１ｋ／Ｙ１Ｎｋ）が、プルーニング後に残っているすべてのシーケンスｓ１Ｋについて知らされる。
【０１２５】
前記の終了制約は、記号のシーケンスの最後で同期を強制するための手段と見なすことができる。実際には、それらは、復号化された記号の数と観察されたビットの数との間で正しい対応を得るためにデコーダを制限している。しかしながら、それらの制限にはシーケンスの真中で同期を確実にする効果はない。
【０１２６】
記号シーケンスに余分な情報を追加すると、シーケンスの全体での再同期が容易になる。このように、余分な記号つまりマーカは、記号シーケンスにおける既知の位置に導入される。これらの記号の選択は任意であり、（２、４、１１、５、１４）において説明される技術原則に基づいている。ほんの一例として、アルファベット内の記号の１つが選択可能であり、または最後に符号化された記号が反復可能である。これらのマーカは既知の記号-クロック位置で挿入される。その結果、バイナリストリーム中で対応する余分なビットの位置が、符号化された記号のシーケンスに依存しランダムになる。
【０１２７】
明らかに、前述された方法はこの余分な情報を考慮に入れなければならない。この知識は推定プロセスによって生かされ得る。変数Ｋｎ（ｋ記号‐クロック）は、マーカがいつ予想されるのかを示す。それに対応して、推定トレリスにおいて対応する遷移確率が更新される。ヌルの確率は、予想されるマーカを放出しないすべての遷移に割り当てられ、その一方、１の確率は他に割り当てられる。それ故に、トレリス内の特定の経路が抑制可能になり、そのことが状態の数の低減と再同期能力の改善とにつながる。
【０１２８】
ロバスト復号化方法の例が実例として前述されている。他の変形例を想定することができる。さらに、他のプルーニング基準が提案可能であり、本発明の方法と組合せることが可能である。Ｍに関する変換／バイナリ変換は必須ではないが、Ｔの小さな値を使用可能にする。また、バイナリソースについて前記に提示された復号化方法は、Ｍに関するソースについて役に立つことがある。
【０１２９】
上記の説明で述べられているように、本発明は、擬似算術符号と呼ばれる低減精度の算術符号を含んだ算術型符号の使用に基づいて、算術符号を復号化するロバストな方法を提案している。これらの擬似算術符号の精度は、求められている効果に応じて調整可能なパラメータである。非常に高い精度により、算術符号の圧縮性能と同一の圧縮性能が達成可能になる。精度が低いと、圧縮での妥当な損失を犠牲にしてロバストネスを増大する効果がある。
【０１３０】
従来の「インスタントネス（瞬間的な）」復号化と比較すると、本発明はデコーダの非同期の現象を実質的に低減している。「逐次」復号化の他の従来の方法、またはツリー構造を使用する他の従来の方法と比較すると、本発明は、復号化の圧縮効率、ロバスト、および複雑さの間でのトレードオフを制御する際に、さらに大きな柔軟性を提供する。実際には、本発明は、チャンネル上で観察された誤り率に従って、端末により許容された複雑さに応じて選択可能な１セットの方法からなる。逐次復号化方法は、復号化プロセスの複雑さを制御することを可能にするプルーニング技術と結合される同期メカニズムを含んでいる。複雑さ／ロバストネス／圧縮トレードオフのパラメータ化を伴ったトレリスベースの復号化プロセスは、プロセスをチャンネルデコーダ（畳み込み符号デコーダ）と関連して使用できるようにし、従来の逐次プロセスを使ってそのような復号化プロセスを達成することは困難である。
【０１３１】
提案された発明において理解されるべきことは、数学的な性質のうち説明された要素がそれ自体重要ではないが、それらがハードウェア制約に被らされる情報（たとえばオーディオ信号またはビデオ信号）のフローに関係する程度までだけが重要であることである。
［表１］いわゆる「エンコーダ」モデルの表形式での表現を示す表である。
【０１３２】
【表１】
2005534241.tif 000003
［表２］いわゆる「デコーダ」モデルの表形式の表現を示す表である。
【０１３３】
【表２】
2005534241.tif 000004
［付録１］本明細書の記載おいて使用される数式を含む。
【付録１】
【０１３４】
2005534241.tif 000005
2005534241.tif 000006
2005534241.tif 000007
【図面の簡単な説明】
【０１３５】
【図１】本発明によるエンコーダおよびデコーダを備えた構成を示す図である。
【図２】本発明によるエンコーダ内で実現可能な符号化方法の全体図である。
【図３】本発明によるデコーダにおいて実現可能な復号方法の全体図を提供する図である。
【図４Ａ】ソース記号とビットのシーケンスとの間の対応を確立するいわゆる同一の「ソース」モデルの３つの異なる表現を示す図である。
【図４Ｂ】ソース記号とビットのシーケンスとの間の対応を確立するいわゆる同一の「ソース」モデルの３つの異なる表現を示す図である。
【図４Ｃ】ソース記号とビットのシーケンスとの間の対応を確立するいわゆる同一の「ソース」モデルの３つの異なる表現を示す図である。
【図５Ａ】図４Ａのいわゆる「ソース」モデルに基づいて記号のシーケンスとビットのシーケンスとの間での同じ対応の２つの異なる表現を示す図である。
【図５Ｂ】図４Ｂのいわゆる「ソース」モデルに基づいて記号のシーケンスとビットのシーケンスとの間での同じ対応の２つの異なる表現を示す図である。
【図６Ａ】本発明によるいわゆる「ソースエンコーダプロダクト」モデルの表形式の表現を示す図である。
【図６Ｂ】本発明による図６Ａのいわゆる「ソースエンコーダプロダクト」モデルのトレリス形式の表現を示す図である。
【図７Ａ】表１のいわゆる「エンコーダ」モデルのトレリス形式の２つの部分的な表現を示す図である。
【図７Ｂ】表１のいわゆる「エンコーダ」モデルのトレリス形式の２つの部分的な表現を示す図である。
【図８】本発明によるいわゆる「ソースエンコーダプロダクト」モデルの一般化された表現を示す図である。
【図９Ａ】本発明によるいわゆる「ソースデコーダプロダクト」モデルの表形式の表現を示す図である。
【図９Ｂ】本発明による図９Ａのいわゆる「ソースデコーダプロダクト」モデルのトレリス形式の表現を示す図である。
【図１０】本発明のいわゆる「ソースデコーダプロダクト」モデルの一般化された表現を示す図である。
【図１１】本発明の第１の実施の形態における復号化方法を示す図である。
【図１２】本発明の第２の実施の形態における復号化方法を示す図である。
【図１３】図１１または図１２の復号化方法に基づくトレリス形式の表現を示す図である。
【図１４】本発明の第３の実施の形態における復号化方法を示す図である。
【図１５】本発明の第４の実施の形態における復号化方法を示す図である。
【符号の説明】
【０１３６】
１      エンコーダ
２      デコーダ
６      処理モジュール
７      プロダクトモデル
８      ソースモジュール
９      エンコーダモデル
１０    デコーダモデル
１２    第１のモジュール（モデルモジュール）
Ｉｃ    チャンネル特性
【図１】
2005534241.tif 000008
【図２】
2005534241.tif 000009
【図３】
2005534241.tif 000010
【図４Ａ】
2005534241.tif 000011
【図４Ｂ】
2005534241.tif 000012
【図４Ｃ】
2005534241.tif 000013
【図５Ａ】
2005534241.tif 000014
【図５Ｂ】
2005534241.tif 000015
2005534241.tif 000016
【図６Ａ】
2005534241.tif 000017
【図６Ｂ】
2005534241.tif 000018
【図７Ａ】
2005534241.tif 000019
【図７Ｂ】
2005534241.tif 000020
【図８】
2005534241.tif 000021
【図９Ａ】
2005534241.tif 000022
【図９Ｂ】
2005534241.tif 000023
【図１０】
2005534241.tif 000024
【図１１】
2005534241.tif 000025
【図１２】
2005534241.tif 000026
【図１３】
2005534241.tif 000027
【図１４】
2005534241.tif 000028
【図１５】
2005534241.tif 000029
【国際調査報告】
2005534241.tif 000030
2005534241.tif 000031
2005534241.tif 000032
2005534241.tif 000033