JP2006126810A - 後方適応規則を用いた整数データの無損失適応Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化および復号化 - Google Patents

Abstract

【課題】 整数データの無損失適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化を新規な適応規則を有する新規な後方適応技法を用いて行う方法およびシステムを提供すること。
【解決手段】 この適応Ｇ／Ｒ符号化器および復号化器（コーデック）および方法では、Ｇ／Ｒパラメータｋの調整をコードワードの生成が済むごとに行う適応規則を使用する。こうした適応規則は、適応値を定義することおよびＧ／Ｒパラメータを適応値に基づいて調整することを含む。適応値が０に等しい場合は、Ｇ／Ｒパラメータを整数定数だけ減らす。適応値が１に等しい場合は、Ｇ／Ｒパラメータを変えずにおく。適応値が１より大きい場合は、Ｇ／Ｒパラメータを適応値だけ増やす。さらに、適応Ｇ／Ｒ符号化器および方法は、分数適応を含み、これにより、スケーリングしたＧ／ＲパラメータをＧ／Ｒパラメータによって定義し、そのスケーリングしたＧ／Ｒパラメータを更新および改造して適応のレートを遅くする。
【選択図】 図４

Description

本発明は、一般には、デジタルデータの処理に関し、より詳細には、新規な後方適応規則（ｂａｃｋｗａｒｄ−ａｄａｐｔｉｖｅ ｒｕｌｅｓ）を有するＧｏｌｏｍｂ−Ｒｉｃｅ符号化を用いた整数データの無損失（ｌｏｓｓｌｅｓｓ）符号化および復号化の改善された方法およびシステムに関する。

データ圧縮は、（テキスト、オーディオ、ビデオ、画像、プログラムファイルなどの）コンピュータデータのサイズが増え続けるにつれて、ますます重要になってきている。データ圧縮は、デジタルデータを、元のデータよりも少ないビットを使用して符号化した表現へと符号化する一手法である。データをより少ないビットで表現すると、データの占めるストレージ空間はより小さくなり、必要な伝送バンド幅はより狭くなる。

一般に、データ圧縮では、最も頻繁に生起するデータを予測し、それをより小さな空間に格納することによってデータの圧縮を行う。具体的には、データ圧縮は、少なくとも異なる２つのタスクを含む。すなわち、（１）データモデルを定義して、入力データの確率を予測すること、および、（２）符号器（ｃｏｄｅｒ）を使用してそうした確率から符号を生成することである。さらに、一部のデータ圧縮技法では、データを数学的に変換し量子化してさらに高度な圧縮を達成している。

圧縮技法は、無損失であることもあれば、ロッシー（ｌｏｓｓｙ）であることもある。無損失圧縮技法は、符号化前の元のデータと復号化後の伸張したデータが、ビット対ビットで同一になるような可逆性をもつ。ロッシー圧縮では、データには、品質での損失を大きくすると捨ててしまえる重複部分がかなりあるという事実を利用している。ロッシー圧縮では、元のデータの一部の損失を容認することによって、より高度な圧縮を達成している。

無損失圧縮は、通常、テキストまたはバイナリデータを圧縮するのに使用され、ロッシー圧縮は、通常、オーディオ、画像、およびビデオデータに使用される。しかし、ロッシー圧縮の技法でも、ときおり無損失圧縮の技法を使用することができる。例えば、一般に使用される種類の圧縮（またはコーディング）技法に、変換符号化および予測符号化がある。そのような種類の圧縮システムでは、元のデータを変換し、次いで量子化する（一番近い整数に丸める）か、または、（固定のまたは適応的な）信号モデルに基づいて予測し、次いで、予測誤差（元のデータと予測したデータの間の差）を量子化する。どちらの場合にも、量子化後のデータは整数の形である。こうした整数を得た後で、無損失圧縮技法を使用して量子化した値の符号化を、データを表現するのに必要なビット数を減らすために行う。

こうした整数値の組には、普通、それに結び付く確率分布関数（ＰＤＦ、ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ ｆｕｎｃｔｉｏｎ）がある。こうしたＰＤＦには、予測符号化では、予測器（ｐｒｅｄｉｃｔｏｒ）によってデータの特徴のモデル化がうまく行われた場合、予測誤差がほとんどの場合に０に近くなるような分布がある。同様に、変換符号化では、量子化した変換係数のほとんどが０となる。図１に、こうした整数値に関する典型的な確率分布を示している。０が最も尤度の高い値であり、０以外の値の確率は、大きさが増加するにつれてほとんど指数関数的な速さで減少する。データが図１に示す確率分布をもつ理由は、無損失圧縮技法を用いて符号化されているデータが元のデータではないためである。図１は、変換係数または予測誤差を量子化した結果できた整数データである。

数学的には、この問題は、Ｎ個の整数を含むベクトルｘを符号化するための効率的な解を見出すことである。要素のそれぞれｘ（ｎ）、ｎ＝０、１、．．．、Ｎ−１の値は、図１の確率分布に類似の確率分布に従い、その結果、最も確率の高い値は０であり、０から遠ざかるところの値の確率は急速に減少する。

図１の確率分布に似た確率分布に関する単純な数学的モデルは、パラメータθで特徴付けられる、ラプラス分布、または両側幾何（ＴＳＧ、ｔｗｏ−ｓｉｄｅｄ ｇｅｏｍｅｔｒｉｃ）分布、すなわち

である。パラメータθにより、確率で｜ｘ｜が大きくなるときの減衰のレートが制御されることに注意されたい。θの値が大きいほど、減衰は速くなる。パラメータθは、ｘ＝０である確率と直接に関係づけることができる。すなわち、Ｐ（０，θ）＝（１−θ）／（１＋θ）である。また、情報源記号（ｓｏｕｒｃｅ ｓｙｍｂｏｌ）の大きさの期待値は、

である。情報源のエントロピーは、記号あたりのビット数（ｂｉｔｓ／ｓｙｍｂｏｌ）として

によって与えられる。

したがって、よい符号化器であれば、ｘのＮ個の値からなるベクトルが、ＮＨ（ｘ）という理論上の最小値よりも、あまり多くないビット数を含むビットストリームへと写像されるはずである。

ラプラス分布は、メディア圧縮システムでは、（たいていの無損失オーディオおよび画像符号化器のような）予測符号化器での予測誤差でも、（たいていのロッシーなオーディオ、画像、およびビデオ符号化器のような）量子化した変換係数でも、一般的なモデルである。

ラプラス／ＴＳＧ分布をもつ情報源用に提案された符号化器は、数多くある。単純であるが効率的な符号化器は、Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化器である。まず、ＴＳＧ情報源の値ｘの非負の値ｕへの写像を、単純な可逆写像

によって行う。これは、ｕを並べ替えられたアルファベット｛０，−１，＋１，−２，＋２，．．．｝とみることと等価である。新しい情報源ｕは、幾何分布情報源の確率分布を近似する確率分布をもつが、これに対してＧｏｌｏｍｂ符号は最適である。その理由は、Ｇｏｌｏｍｂ符号は、Ｇｏｌｏｍｂパラメータを適切に選ぶ限り、幾何分布情報源に対するハフマン符号となっているためである。

Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号の例を、表１に、パラメータｍのいくつかの値に関して示している。ｍが２の累乗に等しいときには、ｍとｍ＝２^ｋの関係にあるパラメータｋが使用されていることに注意されたい。Ｇ／Ｒ符号のハフマン符号にまさる一番の利点は、２進コードワードの計算が、どのような入力値に対しても、単純な規則で行えることにある。このため、テーブルを格納しておく必要がない。これは、テーブルのエントリが格納してあるメモリロケーションからの読み出しに、命令をいくつか実行するよりも時間のかかる、最新型のプロセッサでは特に有用である。同じビット数をもつコードワードが何個連続するかが、パラメータｍで決まっていることが、容易に理解されよう。このことは、コードワードを計算することは、ｕを入力値として、ｕ／ｍを計算するものであることも示している。ほとんどのプロセッサでは、整数の除算には多くのサイクルがかかり、このためＧ／Ｒ符号は一般のｍに対しては魅力的ではない。ｍ＝２^ｋを選ぶ場合、これはＲｉｃｅ符号に対応しており、このとき除算ｕ／ｍは、ｕ／ｍ＝ｕ＞＞ｋであるため、シフトで置き換えることができる（ここで、＞＞は右シフト演算子を表す）。したがって、Ｇ／Ｒ符号の計算をどのような入力ｕに対しても行うことは容易である。単に、ｐ＝ｕ＞＞ｋおよびｖ＝ｕ−（ｐ＜＜ｋ）を計算すればよい。すると、符号が、ｐ個の１をもつストリングを、ｖのｋビットの２進表現と連結することによって作られる。

表１から明らかなことは、Ｇ／Ｒパラメータｋの選択は、情報源の統計に依存しなければならないということである。ｕが増加するにつれての確率の減衰が遅いほど、大きなｋを選ぶべきである。そうでない場合、コードワード長があまりにも急速に大きくなる。ｋを選ぶための簡単なルールは、所与の入力値ｕに対するコードワード長は、およそその値の生起の確率の２を底とする対数とすべきだというものである。

Ｇ／Ｒ符号は、幾何分布の情報源に対しては最適であるが、ラプラス／ＴＳＧ情報源からの記号を式４の写像によって符号化するのには最適ではない。これは、ＴＳＧ分布をもつ入力変数ｘでは、式４からの変数ｕの確率分布が、幾何分布に近いが厳密に幾何分布であるわけではないためである。実際には、パフォーマンスは十分最適に近く（例えば、レートがエントロピーを通常５％未満しか上回らない）、このため、Ｇ／Ｒ符号は非常に人気がある。ＴＳＧ情報源に対する最適な符号は、４つの符号バリアントからなる組を含み、これは実装するにはより複雑であり、圧縮の改善はほとんどの場合５％以下である。したがって、Ｇ／Ｒコーダはほとんどの場合、パフォーマンスと平易さに最良のトレードオフを提供する。

図１では、確率分布を、指数関数の減衰のレートである単一のパラメータで表している。減衰のレートが速いほど、０の値を確率が高くなる。これは、多くの場合に、０となる尤度が非常に高いため、０からなる連続の尤度が非常に高くなることを意味する。言い換えると、減衰の確率分布のレートが十分に速い場合には、連続を符号化するのはよい考えである。０の連続を符号化することは、ほんの数ビットを使用して入力データ中の多くのエントリを処理することになる。

予測誤差が０になる尤度がずっと高くなるのは、例えば、データが、予測符号化における予測器の使用するモデルに合う場合である。しかし、よいモデルがある場合でも、たまには大きな値がある可能性がある。これが起こり得るのは、ピクセルの値がバックグラウンドの値からフォアグラウンドの値に移るなど、境界に達した場合である。ときおり、大きな数は生じ得る。これが起きる場合に、ランレングス符号化よりも有用な符号化技法の１つのタイプが、「ランレングスＧｏｌｏｍｂ−Ｒｉｃｅ（ＲＬＧＲ）」（Ｒｕｎ−Ｌｅｎｇｔｈ Ｇｏｌｏｍｂ／Ｒｉｃｅ）符号化技法である。そのような１つの符号化技法が開示されている（例えば、特許文献１および特許文献２参照）。

現実には、データの情報源が変動しているので、確率は、一定のままではなく、時間とともに変動する。これは、例えば、画像およびオーディオに当てはまる。通常、こうした入力データにおける確率変動は、様々な異なる手法で取り扱われる。例えば、ＪＰＥＧでは、符号化すべき異なる値に対して長さが異なるコードワードを使用するエントロピー符号器（ハフマン符号器）がある。ハフマンテーブルは、普通、あらかじめ設計されている。すなわち、典型的には、いくつもの画像を取得し、その確率を計測し、画像すべてに使用する平均のモデルを構築する。このアプローチの１つの問題点は、ある画像のどの部分でも必ず、符号化効率の点で損失があることであり、この理由は、エントロピー符号器で使用している確率モデルは、平均してよいが、その画像のその部分に関しては必ずしもよいわけではないためである。

表１から、Ｇｏｌｏｍｂ−Ｒｉｃｅ符号に関して主な問題が２つあることが理解されよう。すなわち、（１）確率減衰パラメータθ、またはこれと等価な確率Ｐ（ｘ＝０）が、適切なｋの値を決めることができるためには、知られていなければならないこと、および、（２）減衰パラメータが小さすぎる場合、エントロピーＨ（ｘ）が１未満となり、このため、Ｇｏｌｏｍｂ−Ｒｉｃｅ符号は、その平均のコードワード長が１ビット／記号を下回ることがあり得ない以上、準最適（ｓｕｂｏｐｔｉｍａｌ）となることである。

実際には、第１の問題（最適なＧｏｌｏｍｂ−Ｒｉｃｅパラメータの推定）は、普通、入力ベクトルを所定の長さのブロックへと分割することによって対処している。ブロックごとに、符号化器はデータ全体にわたって２回のパスを行う。第１のパスでは、入力値の平均の大きさを計算する。このために、パラメータθは式２から推定することができ、これに対応する最適なｋを決定することができる。第２のパスでは、符号化器は、そのブロックに対するビットストリームを生成するのに、まずｋの値を２進形式で、続いて、そのブロック内部のデータの値に対するＧｏｌｏｍｂ−Ｒｉｃｅ符号からなる連接したストリングを出力する。これは、無損失画像圧縮用のＪＰＥＧ−ＬＳや無損失オーディオ圧縮用のＳＨＯＲＴＥＮなど、本質的にすべてのＧｏｌｏｍｂ−Ｒｉｃｅ符号を使用する無損失圧縮システムで使用しているアプローチである。これは、「ブロック指向適応」（ｂｌｏｃｋｗｉｓｅ ａｄａｐｔａｔｉｏｎ）または「前方適応（ｆｏｒｗａｒｄ ａｄａｐｔａｔｉｏｎ）」モデルと呼ばれる。前方適応モデルは、符号化器が、符号化の前にまずデータを見て、統計的パラメータを計測し（普通、平均の大きさ）、次いで、そのパラメータに基づいて符号化し、データを符号化するのに使用したパラメータの値を、復号化器での使用のために、ヘッダ内に入れる、という意味で前方である。データを一度に符号にしようとするのではなく、データを小さな部分、すなわちブロックへと分割する。ブロックごとに、そのブロックの統計量を計測し、統計的パラメータを、バッファ内にあるものに合うデータのその部分に対して計測し、エントロピー符号器をそのパラメータに調整する。エンコードしたファイルには、データのそのブロックをエンコードするのに使用したパラメータの値を示すヘッダを挿入する。

実際上の第２の問題、すなわち、エントロピーが非常に低い情報源の符号化への取り組みは、普通、ブロック指向適応または前方適応のモデルを用いて行われ、そのブロック内の入力記号の平均の大きさの値が、推定したエントロピーＨ（ｘ）が１より小さくなるだけ十分小さい場合、符号化器では、Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化ではなく、ランレングス符号化を使用する。

こうしたアプローチは、実際にはうまく働くが、大きな欠点が２つある。欠点の１つは、符号化器が各入力ブロックを２回読み取る必要があり、その結果データに対して２回パスが行われる。すなわち、１回目は平均の大きさを計算してＧｏｌｏｍｂ−Ｒｉｃｅパラメータを決定するためであり、２回目は実際の符号化を行うためである。このため、符号化器はよぶんな仕事を行う必要があり、複雑さが増す。一部の応用では符号化時間は問題とならないが、例えば、デジタルカメラでは、このために符号化プロセスが遅くなり、またはＲＡＭ（ｒａｎｄｏｍ−ａｃｃｅｓｓ ｍｅｍｏｒｙ）のコストが増大する。特に、前方適応モデルでは、まずデータを見て統計量を測定し、モデルのパラメータを求め、そして符号化する。これは、符号化器が、大きな処理パワーをもつパーソナルコンピュータ上で動作している場合には、問題とならない。しかし、写真を携帯電話で撮っている場合には、写真は携帯電話自体で符号化されるので、そこでは処理パワーはずっと限定される。

第２の、最も重要な欠点は、ブロックサイズを選ぶことの困難に関わっている。ブロックサイズが大きすぎる場合には、統計量がブロック内部で劇的に変化する可能性もある。他方、ブロックサイズが小さすぎる場合には、どのパラメータを使用してデータのそのブロックを符号化したかを復号化器に伝えなければならないというオーバーヘッドが負担となる。符号化器は、どのブロックについても必ず、どのようなパラメータを使用してそのブロックを符号化しているかを保存しておかなければならない。あるところでは、小さなブロックを符号化するのに必要なオーバーヘッドが、達成される圧縮に値しない。ここからトレードオフが生じる。一方で、小さいブロックを使用した場合には、そのブロックの統計量を合わせることができるが、この統計量の測定は、数字の数が少なく、符号化のオーバーヘッドが大きいために、困難となる。他方、大きなブロックを使用した場合には、問題は統計量がブロック内部で非常に変動する可能性があることである。実際には、この２つの矛盾する要因の間で妥協点を見出すことは難しく、その結果、ブロックサイズは、普通、１２８から２０４８サンプルの間で、符号化すべきデータのタイプに応じて選ばれている。

１つの解決策は、符号化器内で後方適応技法を使用することである。後方適応では、符号化は、復号化器と符号化器がブロックごとに初期状態について合意するところから始まる。言い換えると、各パラメータを所定の値に初期化し、それから符号化が始まる。符号化器では、出力記号を作り出するたびに、直ちにその記号を復号化器に送ることができるが、これは、復号化器では、それを符号化するのに使用したパラメータの値がわかっているためである。符号化器は、記号を出力した後、今度は符号化パラメータの新しい値の計算を、出力された記号に応じて、所定の適応規則に従って行う。復号化器では、パラメータ適応規則がわかっており、したがって、符号化パラメータの新しい値の計算も行うことができる。こうして、符号化パラメータの調整は、記号の符号化が済むたびに行われ、符号化器と復号化器は常に同期している、すなわち、復号化器は符号化パラメータの変化を追跡している。これは、符号化器から復号化器へは、どのようなパラメータの値を使用してデータを符号化したかに関してどのようなオーバーヘッド情報も送る必要がないことを意味している。

米国特許第６７７１８２８号明細書 米国特許第６４７７２８０号明細書

したがって、無損失Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化器および復号化器（コーデック）、および、効率のよい圧縮を提供し、現れる可能性のあるどのような入力の整数の数字も取り扱い符号化する能力のある方法が必要とされている。しかも、適応Ｇ／Ｒコーデック、および、前方適応に関する前述の諸問題を、後方適応技法を使用することによって回避して、入力データの高速な追跡および効率のよい圧縮を提供する方法もまた必要とされている。

本明細書で開示する発明は、適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化器および復号化器（コーデック）および整数データの無損失符号化および復号化のための方法を含む。適応Ｇ／Ｒコーデックおよび方法では、新規な適応規則を有する新規な後方適応技法を使用している。適応Ｇ／Ｒコーデックおよび方法では、後方適応を用いて、入力データの統計量のどのような変化も迅速に学習する。さらに、適応Ｇ／Ｒコーデックおよび方法は、どのような入力の整数値も符号化する能力をもつ。

また、適応Ｇ／Ｒコーデックおよび方法では、符号化パラメータの調整を、記号の符号化が済むたびに行う、新規な適応規則を使用している。確率テーブルまたはコードワードテーブルは必要なく、このため、適応Ｇ／Ｒコーデックおよび方法は、少ないメモリ領域（ｆｏｏｔｐｒｉｎｔ）の範囲内に納めることが可能である。したがって、適応Ｇ／Ｒコーデックおよび方法は、普通、メモリアクセスに命令のフェッチおよび実行よりもずっとサイクルのかかる、最新型のプロセッサに好適である。また、適応Ｇ／Ｒコーデックおよび方法は、入力データをブロックでバッファリングする必要がなく、データの値をそれぞれ２度処理する必要がないため、メモリが限られ、処理パワーが限られた小さな装置に好適である。

適応Ｇ／Ｒコーデックおよび方法の大きな利点の１つは、Ｇ／Ｒパラメータ（ｋ）の調整および更新が、コードワードの生成が済むたびに行われることである。これにより、入力データの統計量のどのような変化も、迅速に追跡することができるようになる。Ｇ／Ｒパラメータを復号化器に送信する際、その変化は復号化器が追跡しているため、オーバーヘッドが必要とならない。適応規則が単純であるため、後方適応を使用することの計算量（ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ）は低い。したがって、適応Ｇ／Ｒコーデックおよび方法は、多くの実際の適用例にとって魅力的である。

適応Ｇ／Ｒ方法は、符号化規則と適応規則を使用することを含む。符号化規則では、次の入力値ｘの符号化を、まずそれから非負の値ｕへの写像を単純な１対１写像規則（ｘ＞０の場合ｕ＝２ｘ、ｘ＜０の場合ｕ＝−２ｘ−１）によって行い、次いで、ｕの符号化を、パラメータｋをもつＧｏｌｏｍｂ−Ｒｉｃｅ符号化器を用いて行い、このため、出力のコードワードはＧＲ（ｕ，ｋ）と表される。

ある記号を符号化した後、次いで、適応規則を適用する。適応Ｇ／Ｒ方法では、単純であるが新規な適応規則を使用している。ｋに関する適応規則は次の通りである。すなわち、入力値ｕから（Ｇ／Ｒ符号器は常にｕの値に対して働くことを想起されたい）、一時的な値ｐを、ｐ＝ｕ＞＞ｋによって計算する（ここで、＞＞は、右シフト演算子を表す）。ｐ＝０の場合は、スケーリングした形のｋ、すなわちＫを第５の整数定数Ｂ３だけ減らす。ｐ＝１の場合は、Ｋを変えない。Ｐ＞１の場合、Ｋをｐだけ増やす。このようにして、パラメータｋの更新を、Ｇ／Ｒ符号化器に対して、第１と第２のモードのどちらでも、各コードワードを生成した後で行う。次いで、次のコードワードを生成するのに使用することになるｋの値をｋ＝Ｋ／Ｌとして計算するが、ここで、Ｌは固定したパラメータである（Ｌによる除算は、Ｌを２の累乗として選んだ場合には単なるシフト演算子になることを想起されたい）。

上の適応規則の説明から、また、適応Ｇ／Ｒ方法は、「分数適応」（ｆｒａｃｔｉｏｎａｌ ａｄａｐｔａｔｉｏｎ）と呼ばれる特徴を含むことが理解されよう。分数適応により、適応のレートをより細かく制御することが可能になる。まず、スケーリングパラメータＬを定義するが、Ｌの値は、通常、２の累乗に設定する。次に、スケーリングしたＧ／Ｒパラメータ、Ｋ＝ｋ＊Ｌを定義する。ｋに関する適応規則を使用するときには、スケーリングしたパラメータの値Ｋのインクリメントまたはデクリメントを、整数定数だけ、生成したコードワードに応じて行う。Ｋの適応後、最終的なパラメータの値ｋをｋ＝Ｋ／Ｌによって計算する。このようにして、Ｋに関する整数インクリメントは、ｋに関する分数インクリメントとみることができ、これにより、ｋの値のより滑らかな制御が可能となり、したがって入力の統計量の変化をよりよく追跡することになる。ｋの調整を、記号の符号化が済むたびに整数インクリメントで行った場合には、その値がかなり変動する（ｆｌｕｃｔｕａｔｅ）はずである。パラメータの値にそのようなノイズがあると、圧縮率（入力データをただの２進フォーマットで格納するのに必要なビット数の符号化したビットストリームを格納するのに必要なビット数の比）の低下をもたらすはずである。試験済みの一実施形態では、スケーリングパラメータは１６に等しく、Ｇ／Ｒパラメータの値はデジタルデータの減衰パラメータに基づいている。

適応Ｇ／Ｒ符号化器は、上で説明した適応Ｇ／Ｒ方法を組み込むためのモジュールおよび手段を含む。

デジタル整数データは、値を有する整数ベクトルを含む。その値は、各値に対して最も確率の高い値を取るのは０のときであり、０以外の値は、その０以外の値が増加すると確率が減少するような値である。また、適応Ｇ／Ｒ方法は、データの符号化および復号化のためのプロセスを含む。このプロセスは、デジタル整数データの各値ｘの符号化を適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化およびＧ／Ｒパラメータｋを用いて行うこと、および、分数Ｇ／Ｒパラメータを、Ｋ＝ｋ＊Ｌとして定義することを含み、ここで、Ｌはスケーリングパラメータである。また、このプロセスは、適応規則を有する後方適応技法を使用して、分数Ｇ／ＲパラメータＫの更新を、デジタル整数データの各値ｘを符号化した後で行うこと、および、デジタル整数データの符号化した値をビットストリームに付加する（ａｐｐｅｎｄ）ことを含む。また、このプロセスは、ビットストリームの復号化をＧ／Ｒ復号化器を用いて行って、デジタル整数データの各値ｘを厳密に復元することを含む。

適応Ｇ／Ｒ復号化器および方法は、上記の符号化規則に対応する復号化規則を使用し、上で説明した同じ適応規則を使用することによって動作する。復号化器での復号化規則は、これまで説明した符号化器での符号化規則を反転させたものである。すなわち、復号化器では、入力ビットストリーム（またはファイル）から必要なだけのビットを、Ｇ／Ｒパラメータｋの現在の値に応じて読み取る。このようにして、復号化器では、表１による有効なＧｏｌｏｍｂ−Ｒｉｃｅ符号ＧＲ（ｕ，ｋ）に対応する完全なコードワードを読み取る。Ｇｏｌｏｍｂ−Ｒｉｃｅ符号は、どのパラメータｋでも必ず一意的に復号化可能である以上、今度は、復号化器がそのコードワードを復号化することができる。言い換えると、復号化器では、符号化器のところで存在していた記号ｕの値を決定することができる。復号化器は、ｕから、対応するデータの値ｘを、単に１対１の逆写像規則の使用によって決定することができる。特に、ｕが偶数の場合は、ｘ＝ｕ／２であり、ｕが奇数の場合は、ｘ＝−（ｕ＋１）／２である。上で説明した復号化プロセスを行って、入力のコードワードを、符号化器のところで見られたものと厳密に一致する出力の値または値からなるストリングへと復号化する。したがって、復号化プロセスは無損失である。

コードワードの復号化を、入力のビットストリームまたはファイルから上で説明したように行った後、今度は、復号化器では、上で符号化器について説明したのと同じ適応規則を計算する。このようにして、復号化器は、パラメータｋの値の調整を、符号化器が行うのと厳密におなじ形で行うことができる。したがって、このパラメータは、次のビットストリーム（またはファイル）のコードワードを復号化するための正しい値をもつことになる。

本発明のさらなる理解が、本発明の諸態様を例示する以下の説明および添付の図面を参照することによって可能である。他の特徴および利点は、本発明の諸原理を例として示す添付の説明と併せて解釈する、本発明の以下の詳細な説明から明らかであろう。

次に、同じ符号が一貫して対応する部分を表している、図面を参照する。

本発明の以下の説明では、添付の図面への参照を行うが、これは説明の一部をなしており、この中では例示として、本発明を実施することのできる特定のある例を示している。他の諸実施形態を利用することもでき、構成の変更を本発明の範囲から逸脱することなく行えることを理解されたい。

Ｉ．序論
本明細書で開示する適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）コーデックおよび方法は、非常に様々な圧縮の応用例で使用することができる。例えば、適応Ｇ／Ｒコーデックおよび方法は、データベースの応用例でインデックスの符号化に使用することができる。インデックスは、通常、正の整数であるが、確率分布は図１に類似しており、その理由は、インデックスでは小さな値が大きな値よりも尤度が高いためである。別の例は、適応Ｇ／Ｒコーデックおよび方法をハードディスクのヘッド位置を符号化するのに使用することである。ハードディスクが一杯になるまでは、データは、ハードディスクの末尾よりも先頭にある尤度が高い。したがって、小さなヘッドの値は大きなヘッドの値よりも尤度が高く、その結果、入力データの確率分布は図１に類似したものとなる。

本明細書で開示する適応Ｇ／Ｒコーデックおよび方法は、整数データの無損失圧縮のための改善された技法である。整数値を含むベクトルが、符号化器によってビットストリームへと写像され、後でこれが今度は復号化器によって厳密に再構成される。適応Ｇ／Ｒコーデックおよび方法は、後方適応をパフォーマンスの改善のために用いて、迅速に学習を行い、入力データの統計量の変化に適応する。

適応Ｇ／Ｒコーデックおよび方法では、Ｇ／Ｒパラメータの調整を符号化した記号それぞれに従って行う後方適応の方策を使用している。確率テーブルまたはコードワードテーブルは不必要であり、このため、適応Ｇ／Ｒコーデックおよび方法は、非常に小さなメモリ領域（ｆｏｏｔｐｒｉｎｔ）に納めることができるようになっている。したがって、適応Ｇ／Ｒコーデックおよび方法は、普通、メモリアクセスに命令のフェッチおよび実行よりもずっとサイクルのかかる、最新型のプロセッサに特に好適である。

適応Ｇ／Ｒコーデックおよび方法の、従来の種類のエントロピー符号器にまさる１つの重要な利点は、その後方適応の方策により、データの統計量の変化の学習が迅速に行われることである。したがって、実際には、適応Ｇ／Ｒコーデックおよび方法は、ハフマン符号器、ブロック適応Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化器、文脈適応算術符号化器（ｃｏｎｔｅｘｔ−ａｄａｐｔｉｖｅ ａｒｉｔｈｍｅｔｉｃ ｅｎｃｏｄｅｒｓ）などの、他の種類の符号化器よりも、よいパフォーマンスを示してきた。後方適応方策を符号化パラメータに使用することの別の利点は、確率の推定器（ｐｒｏｂａｂｉｌｉｔｙ ｅｓｔｉｍａｔｏｒ）が必要でないことである。適応Ｇ／Ｒコーデックおよび方法のまた別の利点は、適応が、記号の符号化が済むたびに、データにわたる単一のパスで行われることであり、このため、よりよい圧縮結果が得られ、符号化が、ブロック指向または前方適応を使用する符号化器よりも速く行われることになる。

ＩＩ．全体に関する概要
図２ＡおよびＢは、本明細書で開示する適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）コーデックおよび方法の例示的な実装形態を示す構成図である。図２Ａに、適応Ｇ／Ｒコーデックおよび方法の符号化器部分に関する構成図を示している。図２Ｂには、適応Ｇ／Ｒコーデックおよび方法の復号化器部分に関する構成図を示している。図２ＡおよびＢは、適応Ｇ／Ｒコーデックおよび方法を実装および使用できるいくつかの手法のうちの２つであるに過ぎないことに注意されたい。

図２Ａを参照すると、適応Ｇ／Ｒ符号化器２００が、第１のコンピューティング装置２１０上で動作している。適応Ｇ／Ｒ符号化器２００は、整数データ２２０の入力および処理を行う。一般に、整数値を含むベクトルなどの整数データ２２０を与えると、適応Ｇ／Ｒ符号化器２００では、整数データ２２０から符号化済みビットストリーム２３０への符号化または写像を行う。整数データ２２０が通常含む整数のベクトルは、最も確率の高い値を取るのは０のときであり、０以外の値はいずれも、その値が増加すると確率が減少するようなものである。このタイプの整数データは、通常、確率分布関数（ＰＤＦ、ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ ｆｕｎｃｔｉｏｎ）が図１に示すそれに類似している。整数データを符号化した後、符号化済みビットストリーム２３０は、格納または送信を行うことができる。

図２Ｂを参照すると、Ｇ／Ｒ復号化器２４０は、第２のコンピューティング装置２５０上に常駐している。第１のコンピューティング装置２１０と第２のコンピューティング装置２５０は、別々のコンピューティング装置として示しているが、同じコンピューティング装置であってもよいことに注意されたい。言い換えると、Ｇ／Ｒ符号化器２００と復号化器２４０は、同じコンピューティング装置上に常駐していてもよい。一般に、Ｇ／Ｒ復号化器２４０では、符号化済みビットストリーム２３０を処理し、再構成した整数データ２６０を出力する。適応Ｇ／Ｒ符号化器２００では、整数データ２２０の無損失符号化を行うため、Ｇ／Ｒ復号化器２４０は、符号化済みビットストリーム２３０を読み込み、整数データ２２０に含まれる元のデータベクトルを、厳密に再構成することができる。

実際の適用例では、装置または機器（ｅｑｕｉｐｍｅｎｔ）は、Ｇ／Ｒ符号化器は組み込むがＧ／Ｒ復号化器は組み込まなくてもよいことに注意されたい（例えば、デジタルカメラ）。同様に、装置または機器は、Ｇ／Ｒ復号化器は組み込むがＧ／Ｒ符号化器は組み込まなくてもよい（例えば、デジタルオーディオプレイヤやデジタル写真ビューア）。

ＩＩＩ．例示的な動作環境
適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）コーデックおよび方法は、図２に示す第１のコンピューティング装置２１０や第２のコンピューティング装置２５０などの、コンピューティング環境内、およびコンピューティング装置上で動作するように設計されている。適応Ｇ／Ｒコーデックおよび方法が動作するコンピューティング環境を次に論じる。以下の議論は、適応Ｇ／Ｒコーデックおよび方法を実装できる、適したコンピューティング環境の簡潔な、一般的説明を提供する。

図３は、図２に示す適応Ｇ／Ｒコーデックおよび方法を実装できる適切なコンピューティングシステム環境の一例を示す。コンピューティングシステム環境３００は、適切なコンピューティング環境の１つの例に過ぎず、本発明の使用または機能の範囲に関してどのような制限も示唆するものではない。また、コンピューティング環境３００は、例示的な動作環境３００に示すコンポーネントのどの１つまたは組合せに関しても、何らの依存性または要件があると解釈すべきでもない。

適応Ｇ／Ｒコーデックおよび方法は、数多くの他の汎用または専用のコンピューティングシステム環境または構成とともに動作可能である。適応Ｇ／Ｒコーデックおよび方法とともに使用するのに適する可能性のあるよく知られているコンピューティングシステム、環境、および／または構成の例としては、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルド、ラップトップ、またはモバイルコンピュータ、または携帯電話やＰＤＡなどの通信装置、マルチプロセッサシステム、マイクロコンピュータベースのシステム、セットトップボックス、プログラム可能な家電製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたは装置のうちのどのようなものも含む分散コンピューティング環境などがあるが、これに限定されるものではない。

適応Ｇ／Ｒコーデックおよび方法の説明を、あるコンピュータによって実行中の、プログラムモジュールなどのコンピュータ実行可能命令の一般的な状況で行うことができる。一般に、プログラムモジュールは、特定のタスクを実行しまたは特定の抽象データ型を実装する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。また、適応Ｇ／Ｒコーデックおよび方法は、タスクの実行を通信ネットワークを通してリンクされているリモート処理装置が行う、分散コンピューティング環境で実施することもできる。分散コンピューティング環境では、プログラムモジュールを、メモリストレージ装置を含むローカルとリモートのコンピュータストレージ媒体のどちらにも配置することができる。図３を参照すると、適応Ｇ／Ｒコーデックおよび方法を実装するための例示的なシステムは、コンピュータ３１０の形の汎用コンピューティング装置を含む。コンピュータ３１０は、図２に示した第１のコンピューティング装置２１０および第２のコンピューティング装置２５０の例である。

コンピュータ３１０のコンポーネントは、処理ユニット３２０、システムメモリ３３０、および、システムメモリを含む様々なシステムコンポーネントを処理ユニット３２０へと結合するシステムバス３２１を含むが、これに限定されるものではない。システムバス３２１は、様々なバスアーキテクチャのいずれかを用いた、メモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含むいくつかのタイプのバス構造のうちのどのようなものともすることができる。限定ではなく例として、そのようなアーキテクチャとしては、ＩＳＡ（Ｉｎｄｕｓｔｒｙ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ、業界標準アーキテクチャ）バス、ＭＣＡ（Ｍｉｃｒｏ Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ、マイクロチャネルアーキテクチャ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ ＩＳＡ、拡張ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄａｒｄｓ Ａｓｓｏｃｉａｔｉｏｎ、ビデオ電子標準協会）ローカルバス、および、Ｍｅｚｚａｎｉｎｅバスとしても知られるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ、周辺機器相互接続）バスがある。

コンピュータ３１０は、通常、様々なコンピュータ可読媒体を有する。コンピュータ可読媒体は、コンピュータ３１０のアクセスできるどのような利用可能な媒体とすることもでき、揮発性と不揮発性の媒体、リムーバブルと固定の媒体をどちらも含む。限定ではなく例として、コンピュータ可読媒体は、コンピュータストレージ媒体および通信媒体を含む。コンピュータストレージ媒体は、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータなどの情報の格納のためのどのような方法または技術でも実装される揮発性および不揮発性で、リムーバブルおよび固定の媒体を含む。

コンピュータストレージ媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（ｄｉｇｉｔａｌ ｖｅｒｓａｔｉｌｅ ｄｉｓｋ、デジタル多用途ディスク）または他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気ストレージ装置、または所望の情報を格納するのに使用でき、コンピュータ３１０のアクセスできる他のどのような媒体も含むが、それに限定されるものではない。通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータを、搬送波などの変調されたデータ信号（ｍｏｄｕｌａｔｅｄ ｄａｔａ ｓｉｇｎａｌ）または他の通信機構（ｔｒａｎｓｐｏｒｔ ｍｅｃｈａｎｉｓｍ）で実施し、どのような情報配信媒体（ｉｎｆｏｒｍａｔｉｏｎ ｄｅｌｉｖｅｒｙ ｍｅｄｉａ）も含む。

「変調されたデータ信号」という用語は、その特徴の１つまたは複数が情報をその信号の中にエンコードする形で設定または変更される信号を意味することに注意されたい。限定ではなく例として、通信媒体は、有線ネットワークや直接配線接続などの有線媒体、ならびに音響、赤外線などの無線媒体および他の無線媒体を含む。また、上記のどのようなものの組合せも、コンピュータ可読媒体の範囲内に含められる。

システムメモリ３３０は、コンピュータストレージ媒体を、ＲＯＭ（ｒｅａｄ ｏｎｌｙ ｍｅｍｏｒｙ、読み取り専用メモリ）３３１やＲＡＭ（ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ、ランダムアクセスメモリ）３３２などの揮発性および／または不揮発性のメモリの形で含む。起動（ｓｔａｒｔ−ｕｐ）時などにコンピュータ３１０内部の要素間で情報を転送するのに役立つ基本ルーチンを含む、ＢＩＯＳ（基本入出力システム）３３３は、通常、ＲＯＭ３３１に格納されている。ＲＡＭ３３２は、通常、処理ユニット３２０の直ちにアクセス可能なおよび／または目下動作対象としているデータおよび／またはプログラムモジュールを含む。限定ではなく例として、図３に、オペレーティングシステム３３４、アプリケーションプログラム３３５、他のプログラムモジュール３３６、およびプログラムデータ３３７を示している。

また、コンピュータ３１０は、他のリムーバブル／固定で揮発性／不揮発性のコンピュータストレージ媒体を含むこともできる。単に例として、図３に、固定で不揮発性の磁気媒体からの読み取りまたはそれへの書き込みを行うハードディスクドライブ３４１、リムーバブルで不揮発性の磁気ディスク３５２からの読み取りまたはそれへの書き込みを行う磁気ディスクドライブ３５１、および、ＣＤ−ＲＯＭや他の光学メディアなどのリムーバブルで不揮発性の光ディスク３５６からの読み取りまたはそれへの書き込みを行う光ディスクドライブ３５５を示している。

例示的な動作環境で使用できる他のリムーバブル／固定で揮発性／不揮発性のコンピュータストレージ媒体としては、磁気テープカセット、フラッシュメモリカード、ＤＶＤ（デジタル多用途ディスク）、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどがあるが、これに限定されるものではない。ハードディスクドライブ３４１は、通常、システムバス３２１にインターフェース３４０などの固定メモリインターフェースを通して接続され、磁気ディスクドライブ３５１および光ディスクドライブ３５５は、通常、システムバス３２１にインターフェース３５０などのリムーバブルメモリインターフェースを通して接続される。

上で論じ、図３に示したドライブおよびその関連するコンピュータストレージ媒体により、コンピュータ３１０用のコンピュータ可読命令、データ構造、プログラムモジュールおよび他のデータのストレージが提供される。図３で、例えば、ハードディスクドライブ３４１は、オペレーティングシステム３４４、アプリケーションプログラム３４５、他のプログラムモジュール３４６、およびプログラムデータ３４７を格納するものとして示している。こうした構成要素は、オペレーティングシステム３３４、アプリケーションプログラム３３５、他のプログラムモジュール３３６、およびプログラムデータ３３７と同じでも異なっていてもよいことに注意されたい。オペレーティングシステム３４４、アプリケーションプログラム３４５、他のプログラムモジュール３４６、およびプログラムデータ３４７には、本明細書では異なる符号を与えて、最小限、これらが異なるコピーであることを示している。ユーザは、コマンドおよび情報のコンピュータ３１０への入力を、キーボード３６２や、一般にマウス、トラックボール、またはタッチパッドと呼ばれるポインティング装置３６１などの入力装置によって行うことができる。

他の入力装置（図示せず）としては、ジョイスティック、ゲームパッド、衛星放送受信アンテナ（ｓａｔｅｌｌｉｔｅ ｄｉｓｈ）、スキャナ、ラジオ受信機、あるいはテレビまたはブロードキャストビデオ受信機などがあり得る。こうしたおよび他の入力装置の処理ユニット３２０への接続は、しばしば、システムバス３２１に結合されるユーザ入力インターフェース３６０を通して行われるが、例えば、パラレルポート、ゲームポート、またはＵＳＢ（ｕｎｉｖｅｒｓａｌ ｓｅｒｉａｌ ｂｕｓ、ユニバーサルシリアルバス）など、他のインターフェースおよびバス構造によって行うことも可能である。また、モニタ３９１または他のタイプのディスプレイ装置のシステムバス３２１への接続も、ビデオインターフェース３９０などのインターフェースを介して行うことができる。また、コンピュータは、モニタの他に、スピーカ３９７やプリンタ３９６など他の周辺出力装置を含むことができ、その接続は出力周辺インターフェース３９５を通して行うことができる。

コンピュータ３１０は、リモートコンピュータ３８０など、１つまたは複数のリモートコンピュータへの論理接続を用いてネットワーク化環境で動作することができる。リモートコンピュータ３８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置（ｐｅｅｒ ｄｅｖｉｃｅ）または他の一般的なネットワークノードとすることができ、通常、コンピュータ３１０に関して上で説明した要素の多くまたはすべてを含むが、図３にはメモリストレージ装置３８１だけが示されている。図３に示す論理接続は、ＬＡＮ（ｌｏｃａｌ ａｒｅａ ｎｅｔｗｏｒｋ、構内通信網）３７１およびＷＡＮ（ｗｉｄｅ ａｒｅａ ｎｅｔｗｏｒｋ、広域通信網）３７３を含むが、また他のネットワークを含んでもよい。そのようなネットワーキング環境は、オフィス、全社規模のコンピュータネットワーク、イントラネット、およびインターネットでは普通のものである。

コンピュータ３１０は、ＬＡＮネットワーキング環境で使用するときには、ＬＡＮ３７１にネットワークインターフェースまたはアダプタ３７０を通して接続する。ＷＡＮネットワーキング環境で使用するとき、コンピュータ３１０は通常モデム３７２、または、インターネットなどのＷＡＮ３７３を介して通信を確立するための他の手段を含む。モデム３７２は、内蔵でも外付けでもよいが、システムバス３２１にユーザ入力インターフェース３６０、または他の適当な機構を介して接続する。ネットワーク化環境では、コンピュータ３１０に関して示したプログラムモジュールまたはその部分は、リモートのメモリストレージ装置に格納することができる。限定ではなく例として、図３には、リモートのアプリケーションプログラム３８５を、メモリ装置３８１上にある（ｒｅｓｉｄｅ）ものとして示している。ここに示すネットワーク接続は例示的であり、コンピュータ間に通信リンクを確立する他の手段を使用してもよいことが理解されよう。

ＩＶ．システムコンポーネント
図４は、図２に示す適応Ｇ／Ｒ符号化器２００のコンポーネントを示す一般的な構成図である。適応Ｇ／Ｒ符号化器では、入力として、入力値（または値からなるストリング）４００を受け取る。Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）復号化モジュール４１０は、入力値（またはストリング）４００を符号化して、コードワード４２０を得るのに使用する。入力値（またはストリング）４００それぞれの符号化後に、符号化パラメータを適応させて入力データの統計量を追跡する。

Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータ適応モジュール４３０は、元のＧ／Ｒパラメータの更新を後方適応規則および新規な適応規則を用いて行うのに使用する。これから、更新済みＧ／Ｒパラメータ４４０が得られる。Ｇ／Ｒパラメータの適応については、下で詳細に論じることにする。パラメータの更新が済んだ後、次の入力値４５０をの処理を、適応Ｇ／Ｒ符号化器２００が、更新済みＧ／Ｒパラメータ４４０を用いて行う。

Ｖ．動作に関する概要
図２および４に示す適応Ｇ／Ｒ符号化器２００およびその中で使用する方法の動作を次に論じることにする。図５は、図２および４に示す適応Ｇ／Ｒ符号化器および方法の一般的な動作を示す一般的な流れ図である。方法は、符号化すべきデジタルデータを入力することによって始まる（囲み枠５００）。ある試験済みの実施形態では、入力デジタルデータは、要素が整数値であるベクトルの形式をした整数データである。各入力デジタルデータ値は、どのような整数値とすることもでき、特定の範囲に制限されない（例えば、他のエントロピー符号器では普通であるように、２進または符号付き２進）ことに注意されたい。次に、このデジタルデータをＧ／Ｒパラメータを用いて符号化する（囲み枠５１０）。

デジタルデータの符号化は、特定の値に初期化されたＧ／Ｒパラメータを用いて行われる。しかし、入力デジタルデータの統計量が変わる可能性があるため、Ｇ／Ｒ符号化器２００は適応的である。この適応により、適応Ｇ／Ｒ符号化器２００は、入力デジタルデータの統計量を追跡し、そうした統計量に迅速に適応することができ、より高い符号化の効率が提供される。適応Ｇ／Ｒ符号化器２００および方法では、Ｇ／Ｒパラメータの更新を、後方適応技法を用いて行う（囲み枠５２０）。このＧ／Ｒパラメータの更新は、入力デジタルデータの値または値からなるストリングの符号化が済むごとに行われる。しかも、この後方適応技法は、下で詳細に論じる、新規な適応規則を含む。次いで、符号化済みのデジタルデータを出力する（囲み枠５３０）。次に、入力デジタルデータの次の値またはストリングの処理を、先ほど説明した方法を用いて行う。この更新済みのＧ／Ｒパラメータの値は、その次の入力値またはストリングの符号化で使用する。このプロセスを、デジタルデータをすべて符号化して符号化済みのビットストリームにしてしまうまで繰り返す。

図６は、図５に示した適応Ｇ／Ｒ符号化器および方法のさらなる詳細を示す流れ図である。具体的には、デジタルデータの値またはストリングを入力として受け取る（囲み枠６００）。次に、入力値またはストリングの符号化を、Ｇ／Ｒパラメータを用いて行う（囲み枠６１０）。入力値またはストリングの符号化が済んだ後、Ｇ／Ｒパラメータを更新する。この適応プロセスは、スケーリングしたＧ／Ｒパラメータを定義することによって始まる（囲み枠６２０）。このスケーリングしたＧ／Ｒパラメータは、Ｇ／Ｒパラメータの適応を遅くし、最適なパラメータの値の追跡をより細かく行えるようにするのに使用する。スケーリングしたＧ／Ｒパラメータについては、下でより詳細に論じる。次に、スケーリングしたＧ／Ｒパラメータの更新を、後方適応技法および新規な適応規則を用いて行う（囲み枠６３０）。符号化済みの入力値またはストリングを符号化済みビットストリームに付加し、符号化すべきデジタルデータからの次の値またはストリングの入力を行う（囲み枠６４０）。プロセスは再び始まって、次の値またはストリングの符号化が、更新されたスケーリングしたＧ／Ｒパラメータを用いて行われる。

ＶＩ．動作の詳細
上で論じた図４、５、および６の適応Ｇ／Ｒ符号化器２００および方法の動作の詳細を、次に論じることにする。

Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータ適応モジュール
図７は、図４に示したＧ／Ｒ符号化器２００および方法のＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータ適応モジュール４３０の動作の詳細な流れ図である。一般に、Ｇ／Ｒパラメータ適応モジュール４３０では、初期Ｇ／Ｒパラメータの更新を、新規な適応規則を有する後方適応技法を用いて行う。この更新は、デジタルデータの値またはストリングの符号化が済むごとに行う。

動作は、初期Ｇ／Ｒパラメータ（囲み枠７０５）および適応値（囲み枠７１０）を入力として受け取ることから始まり、後者の計算は後で説明することにする。次いで、この適応値が０に等しいかどうかに関して判断が行う（囲み枠７１５）。そうである場合、適応規則は、スケーリングしたＧ／Ｒパラメータをある整数定数だけ減らすというものである（囲み枠７２０）。

適応値が０に等しくない場合、適応値が１に等しいかどうかの判断を行う（囲み枠７２５）。そうである場合、適応規則は、スケーリングしたＧ／Ｒパラメータを変えずにおくというものである（囲み枠７３０）。そうでない場合、適応規則は、スケーリングしたＧ／Ｒパラメータを適応値だけ増やすというものである（囲み枠７３５）。

Ｇ／Ｒパラメータの適応が済んだ後、現在のＧ／Ｒパラメータを更新したＧ／Ｒパラメータで置き換える（囲み枠７４０）。後者は、スケーリングしたＧ／Ｒモードパラメータを固定のスケーリング因子で割り、その結果の整数部分を取ることによって得られる。適応では、スケーリングしたＧ／Ｒモードパラメータを整数のきざみで調整しているため、実際のＧ／Ｒパラメータは、それを分数のきざみで適応させているのと同様に振る舞う。ここでも、これは「分数適応」の一例となっており、これにより、適応の早さのより細かな制御ができるようになっている。もちろん、Ｇ／Ｒパラメータを変えずにおく場合には（囲み枠７３０）、更新を行う必要はなく、現在のＧ／Ｒパラメータは同じである。最後に、更新したＧ／Ｒパラメータを出力する（囲み枠７４５）。

図８は、図７に示したＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータ適応モジュール４３０で使用する適応値の計算の詳細な流れ図である。図７および９も参照すると、適応値計算モジュール８００では、図７の流れ図への入力となる適応値を出力する（囲み枠７１０）。動作は、２つの入力、すなわち、現在のＧ／Ｒパラメータの値（囲み枠８０５）および入力値（囲み枠８１０）を受け取ることから始まる。次に、入力値を、Ｇ／Ｒパラメータの値の桁数だけ右へとシフトする（囲み枠８２０）。この結果の値が適応値であり、次いで、これを出力する（囲み枠８３０）。

ＶＩＩ．実施例
本明細書で開示する適応Ｇ／Ｒ符号化器および方法をより完全に理解するために、例示的な実施例（ｗｏｒｋｉｎｇ ｅｘａｍｐｌｅ）の動作の詳細を提示する。この実施例は、適応Ｇ／Ｒ符号化器および方法を実施できる一手法に過ぎないことに注意されたい。

適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）コーデックおよび方法は、開示されているＰＴＣエントロピー符号化器の拡張である（例えば、特許文献２参照）。しかし、このＰＴＣエントロピー符号化器は、２進データ（通常、整数データのビットプレーン（ｂｉｔ−ｐｌａｎｅｓ））の符号化に使用される。本明細書で開示する適応Ｇ／Ｒコーデックおよび方法では、入力値がどのような整数データであっても符号化することができる。言い換えると、本明細書で開示する適応Ｇ／Ｒコーデックおよび方法では、どのようなアルファベットからなるデータでも符号化することができる。

本明細書で開示する適応Ｇ／Ｒ符号化器および方法の１つの利点は、ＰＴＣエントロピー符号化器とは異なり、入力データの可能な最大値を知る必要がないことである。それどころか、適応Ｇ／Ｒ符号化器および方法では、どのような大きさの入力値も、どんなに大きくても取り扱うことができる。これは、適応Ｇ／Ｒ符号化器では、入力データが図１に示すようなラプラス分布をもつものと仮定しており、突然大きな数が入力データ中に現れた場合、適応Ｇ／Ｒ符号化器および方法では、その大きな数を符号化できることを意味する。その大きな数の符号化には、より小さな数よりは多くのビットが使用されることになるとはいえ、その大きな数は符号化される。しかし、より多くのビットを使用するために不利になるのは、その大きな数が現れたとき、その数に対してだけであり、他のあらゆる値に対してはそうならない。これは、下で述べる新しいモード選択および適応規則によるものである。

ＰＴＣエントロピー符号化器の場合は、入力データを受け取り、ビットプレーンへと分割し、次いで、各ビットプレーンをＧ／Ｒ符号化器で符号化している。本明細書で開示する適応Ｇ／Ｒコーデックおよび方法では、適応Ｇ／Ｒコーデックおよび方法を、ラプラス分布のデータを直接取り扱うように拡張する。これには、適応Ｇ／Ｒコーデックおよび方法では、ＰＴＣエントロピー符号化器よりも著しく速い、単一パスの符号化を使用するという利点がある。

ＰＴＣエントロピー符号化器の入力データは、小さな数の尤度がより高い、ラプラス分布となっていた。時には、小さな数の尤度がずっと高いために、０からなる連続を符号化することが、ビットストリームの特定の部分に関してはより効率がよいことがある。しかし、ＰＴＣエントロピー符号化器では、データを取り込み、最上位ビットプレーンに対してパスを１回行い、戻って次のビットプレーンでパスを１回行っていたはずである。例えば、データが１６ビットであった場合、パスをまずビット番号１６に対して行い、符号化していた。もちろん、そのビットは、非常に大きな数のところに散らばるだけで、あとはずっと０である（ｇｏｉｎｇ ｄｏｗｎ）ため、データのほとんどは０であろう。ビット番号５、４、３、２、および１まで来ると、これらのビットには０と１がたくさんあるが、これは、それを符号化してもまったく役に立たないところまできたということを意味している。普通、最下位ビットは非常にランダムであるため、そのビットの符号化には１ビット分使用される。すなわち、入力のビットはそれぞれ直接に出力へとコピーされるのである。ＰＴＣエントロピー符号化器の問題は、ビットプレーンにおける符号化に、データに対するいくつかのパスが必要になることである。特に、ＰＴＣエントロピー符号化器では、符号化を、最上位ビット、次のビット、次いで、次のビット、という形で行う必要がある。明らかに、これには著しく時間が長くかかり、場合によってはＰＴＣエントロピー符号化器は、本明細書で開示する適応Ｇ／Ｒ符号化器および方法よりも１．５から３倍遅い。

符号化規則
適応Ｇ／Ｒコーデックおよび方法では、Ｇ／Ｒパラメータであるｋに基づく新規な符号化規則を使用している。表２に、整数値ｘを２進ビットストリームに写像するための適応Ｇ／Ｒコーデックおよび方法のための符号化規則（ｃｏｄｉｎｇ ｒｕｌｅｓ）を示している。

この実施例では、写像の値ｕを定義している。適応Ｇ／Ｒコーデックおよび方法の入力値ｘは、正でも負でもあり得る。入力値ｘは、ｕの値に写像されるが、ｕは正でしかない。したがって、符号付きの入力値ｘは、符号なしの同等な表現であるｕへと変換される。式４では、ｘからｕへの写像を述べている。特に、この写像では、０は０に写像され、１は１に写像され、−１は２に写像され、２は３に写像され、−２は４に写像され、など、ｕの値は常に正となるようなやり方で行うことを述べている。これは、Ｇ／Ｒテーブル（表１）を使用できるように行うが、その理由は、Ｇ／Ｒテーブルが非負の値専用であるためである。この写像により、適応Ｇ／Ｒコーデックおよび方法は、どのような入力アルファベットも取り扱えるようになる。言い換えると、Ｇ／Ｒテーブルを使用しているため（これはどのような入力の数も取り扱うことができる）、入力アルファベットを無限とすることができ、適応Ｇ／Ｒコーデックおよび方法は、どのような大きさの数の入力も取り扱うことができる。適応Ｇ／Ｒコーデックおよび方法は、オペレーティングシステムが取り扱える数の大きさによってのみ制限を受ける。実際には、Ｇ／Ｒ符号化である表１をメモリ内に格納する必要はないことに注意されたい。このテーブルのエントリは十分な構造をもっているため、コードワードの計算をｕの任意の値および符号化パラメータｋに対して容易に行えることが容易に理解されよう。

ｕのデータが与えられている状況で、表２が述べているのは、入力値ｘの写像の値ｕの符号化は、適応Ｇ／Ｒ符号化器、および、表１で例を示したＧ／Ｒ符号化規則を用いて行われるということである。したがって、ｘを符号化するのに使用するコードワードは、ｕおよびｋの値に基づくことになる。Ｇ／Ｒパラメータｋの更新は、後方適応技法および新規な符号化規則を用いて行い、これについては下で詳細に論じる通りである。表２の規則は、符号化器がどのように符号化を行うかを精確に定義しており、その意味は、復号化器が、表２にある同じ規則を使用して符号化されたデータを復元（すなわち復号化）できるということである。

分数適応
分数適応では、Ｇ／Ｒパラメータｋの代わりに、スケーリングしたＧ／ＲパラメータＫを使用する。分数適応は、適応を遅くする一手法である。適応Ｇ／Ｒコーデックおよび方法を、分数適応なしで使用することは可能である。しかし、分数適応なしでは、普通、適応があまりに速く変化しすぎ、通常、入力データに対する最適なパラメータを正しく追跡するのに失敗してしまう。

この実施例では、ｋパラメータの適応は、スケーリングしたＫパラメータを用いて行う。したがって、ｋの代わりにＫの更新を行う。ｋとＫの間の関係は次のようである。すなわち、ｋ＝Ｋ／Ｌであり、ここでＬは、上で説明したスケーリングパラメータである。したがって、適応を行う場合、Ｋの値を適応させ、ＫをＬで割ってｋの値を得る。値はすべて整数であり、このためｋ＝Ｋ／Ｌによって、その結果の整数部分を意味していることに注意されたい。固定のスケーリングパラメータＬは、２の累乗に等しい値に設定しておき（例えば、Ｌ＝１６）、そうするとＬによる除算がシフト演算子によって効率よく行えることも想起されたい。

分数適応が好ましいのは、適応Ｇ／Ｒコーデックおよび方法では、生成した符号ごとにＧ／Ｒパラメータｋの調整を行うためである。言い換えると、入力値またはストリングを符号化した後で、適応規則を実行する。ｋの適応を直接に整数値である変化量（ｃｈａｎｇｅｓ）によって行うと、それは整数であるために、可能な結果は、同じままであるか、少なくとも１だけ増えるか減るかに限られてしまう。しかし、入力データが大きくなっていく状態を考えてみると、これは、パラメータを増加させるべきであることを意味する。

分数適応により、ｋの分数インクリメントが可能になる。例えば、ｋを１の代わりに０．５だけ増やすことができる。しかし、ｋが整数パラメータであるために、これはできない。このため、分数適応では、整数インクリメントをＫにおいて行い、ＫをＬで割って、ｋの分数インクリメントを与えるのである。これにより、パラメータｋに振動が起きないことが保証される。

分数インクリメントを使用する代わりに、データに減少または増加が起きた場合には、パラメータを増加または減少させる前に、符号化サイクルをある回数進ませる（ｐａｓｓ）ようなフラグを定義することが可能である。符号化サイクルの数を把握しておく新しいパラメータを１つ定義できるはずである。言い換えると、そのパラメータは、諸パラメータを変更する前に、その状況（入力データの増加または減少）が何回起きるべきかを把握しておくことになるはずである。しかし、この技法は試みたが、分数適応からより優れた結果が得られたことに注意されたい。

Ｇｏｌｏｍｂ−Ｒｉｃｅ（ｋ）パラメータ適応
Ｇ／Ｒパラメータｋの適応は、入力値またはストリングの符号化が済むごとに行った。分数適応を使用する場合は、ｋを直接にではなく、実際にはスケーリングしたＧ／ＲパラメータＫを適応させる。表３に、Ｇ／Ｒパラメータｋに関する適応規則を述べている。値ｕの符号化の後、適応を制御するのはｐ＝ｕ＞＞ｋである適応値であり、これは、ｕを右にｋ桁シフトさせることを意味する。適応の後、ｋの値をｋ＝Ｋ／Ｌに設定するが、ここでＬは定数である。この実施例では、Ｌ＝１６である。

表１からのＧ／Ｒ符号は、パラメータｋに依存している。例えば、不完全な実行（ｒｕｎ）の後の値が１３である場合、１３に対するＧ／Ｒ符号は「１１１１１１１１１１１１０」（ｋ＝０の場合）であり、ｋ＝１の場合は「１１１１１１０１」である。ｋが大きいほど、１３を表す数は小さくなることになる。ｋが小さいほど、１３を表す数は大きくなることになる。したがって、パラメータｋがわかっていなければならない。これは、適応Ｇ／Ｒコーデックおよび方法では、ｋに対して値をうまく選んだ場合には、よい仕事ができることを意味している。しかし、大きなｋの値を使用すると、図１に示すように、入力データのより小さい値に対してより長いストリングを出力することになるため、これが常に有利なわけではない。言い換えると、ｋの値に関するよい選択は、入力データに依存するのである。値が１３の場合、大きなｋの値を使用するのはよい考えである。しかし、不完全な実行の後で値が「１」であるとする。今度は、より小さなｋの値が望ましい。したがって、不完全な実行の後の小さな値に対しては、小さなｋを使用するほうがよく、大きな値に対しては、大きなｋを使用するほうがよい。したがって、ｋの選択は、値の確率に関連している。従来技術では、この効果に対する一連の理論的研究がある。すなわち、入力データに対する確率がわかっている場合には（例えば、入力データが、減衰を制御する単一のパラメータのあるラプラス分布となっている場合）、その減衰パラメータから使用すべきパラメータｋの計算ができるよく知られた公式がある。これから、平均して、できるだけ少ないビット数を使用する写像が得られる。

したがって、ｋパラメータが適応的であることは重要である。そのため、入力データに大きな値が現れた場合には、大きな値に対しては大きなｋのほうがよいため、ｋを増やすべきである。他方、小さな値が現れた場合には、ｋを減らすべきである。直観的に、大きな値に対してはｋを増やすべきであり、小さな値に対してはｋを減らすべきであることが理解されよう。すると、ｋの変更を（分数適応を使用している場合のように）十分に小さなペースで行っている限り、入力データに対する最適パラメータを、常に正しく追跡することになる。

表３に示したｋに関する適応規則は、顕著に新しいものである。適応Ｇ／Ｒコーデックおよび方法では、どのような値も現れる可能性があり、そのため、その値を符号化しなければならない。符号化は、適応Ｇ／Ｒ符号化器およびＧ／Ｒパラメータｋを用いて行う。表３を参照すると、入力データはｘである。入力データｘは、どのような整数値である可能性もあるが、小さなｘの尤度がより高い（正でもあり得、負でもあり得る）。しかし、Ｇ／Ｒ符号化は、正の数専用である。ｘの簡単な写像を使用して（式４を参照されたい）ｘからｕへの写像を行う。ｋの適応は、適応値ｐによって行い、これは、ｕを右にｋ桁だけシフトしたものとして定義する。したがって、適応値ｐはｕをスケーリングして小さくした形になっている。あるいは、これと同等であるが、ｐパラメータは、ｕ／２^ｋに対する整数の近似である。ｋ桁だけ右にシフトすることは、その数を２^ｋで割ることと同等である。例えば、ある数を５ビット右にシフトさせた場合、これは、その数を３２（すなわち２^５）で割ることと同じである。余りは捨て、商だけを使用する。

表３を参照すると、適応値ｐが０に等しい場合は、Ｋを更新し、整数定数Ｂ３だけ減らしたＫで置き換える。適応値ｐが１に等しい場合は、Ｋを変えずにおく。適応パラメータｐが１より大きい場合は、Ｋを更新し、適応値ｐだけ減らしたＫで置き換える。

適応値であるｐが１に等しい場合、これは、ｕの値が２^ｋに近かったことを意味するが、これらは、パラメータｋが正しくなっているような値である。したがって、表３に示すように、変更を行わない。適応値ｐの値が０である場合は、これは、入力値が２^ｋよりも小さかったことを意味する。つまり、ｋを減らし始めるべき時だということである（入力値が２^ｋよりも小さいため）。適応値ｐが１より大きい場合は、尤度はずっと低いが、これは、入力値が非常に大きくことの尤度は高くないためである。しかし、その数が大きく、かつｐ＞１である場合には、ｋパラメータを増やし始めるべき時である。

適応Ｇ／Ｒ符号化器
図９は、図２および４に示した、適応Ｇ／Ｒ符号化器２００の符号化の詳細を、Ｇ／Ｒパラメータｋの適応規則を含めて示す一実施例である。プロセスが始まる（囲み枠９０５）のは、入力値ｕを読み込むこと（囲み枠９１０）からである。適応Ｇ／Ｒ符号化器２００の２つの主なプロセスは、Ｇ／Ｒ符号化（囲み枠９１５）およびＧ／Ｒパラメータ適応（囲み枠９２０）である。

Ｇ／Ｒ符号化９１５のプロセスは、適応値ｐおよびｖを計算することから始まる（囲み枠９２５）。ビットストリームの末尾に、１に等しいビットｐ個を付加する（囲み枠９３０）。次いで、ｋビットの２進の値であるｖをビットストリームに付加する（囲み枠９３５）。これらの動作は、表１に定義する適応Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化器を含む。

Ｇ／Ｒパラメータ適応９２０のプロセスは、適応値ｐが１に等しいかどうかを判断すること（囲み枠９４０）を含む。そうである場合、適応値ｐは変えずにおく（接点９４５）。そうである場合、適応値ｐが０に等しいかどうかという別の判断を行う（囲み枠９５０）。そうでない場合、Ｋを更新し、整数定数Ｂ３だけ減らしたＫで置き換える（囲み枠９５５）。他の場合、Ｋを更新し、適応値ｐだけ増やしたＫで置き換える（囲み枠９６０）。最後に、プロセスでは、ｋを、Ｌで割ったＫに設定し（囲み枠９６５）、プロセスは終了する（囲み枠９７０）。

結果
この実施例の適応Ｇ／Ｒコーデックおよび方法を、画像、オーディオ、および地図情報の圧縮用のアプリケーション内に実装している。こうしたアプリケーション内で適応Ｇ／Ｒコーデックおよび方法を使用したところ、圧縮率は最も高度なエントロピー符号化器に匹敵するという結果が得られているが、実装はより単純に行われている。

特に、整数データに対する既存のエントロピー符号化器に関しては、適応Ｇ／Ｒコーデックおよび方法では、図１の確率分布のような、情報源記号の確率分布の大きなクラスに対して、理論上の最大値（情報源エントロピーによって決まる）に近い圧縮率が達成されている。例としては、よく知られているＧｏｌｏｍｂ−Ｒｉｃｅおよびハフマン符号化器が効率的であるのは、記号あたり１ビット以上の情報源エントロピーに対してに限られる。

ＶＩＩＩ．復号化
また、適応Ｇ／Ｒコーデックおよび方法は、上の符号化器の説明に基づいて精確に実装することのできる復号化器を含む。図２Ｂを参照すると、コンピューティング装置（囲み枠２５０）が実装できるのは、Ｇ／Ｒ復号化器２４０だけである。適応Ｇ／Ｒ復号化器２４０および方法では、符号化済みビットストリームからコードワードを受け取る（囲み枠２３０）。次に、適応Ｇ／Ｒ復号化器２４０では、コードワードの復号化を、適応Ｇ／Ｒ符号化器２００に関して上で述べた逆の規則を適用することによって行う。次に、Ｇ／Ｒパラメータの適応を、適応Ｇ／Ｒ符号化器に関する規則と厳密に同じ規則を用いて行う。最後に、復号化した（すなわち、再構成した）整数データを出力する（囲み枠２６０）。

符号化規則は、一意的に復号化可能であり、復号化器に関する適応規則は、符号化器のそれと同一である以上、符号化規則および適応規則のこれまでの説明は、復号化器の動作を精確に記述するものである。

本発明の以上の説明は、例示および説明の目的で提示している。これは、網羅的であること、または、本発明を開示した精確な形に限定するものではない。多くの修正および変形が上記の教示を考慮して可能である。本発明の範囲を限定するのは、本発明の詳細な説明ではなく、本明細書に添付の特許請求の範囲であるものとする。

本明細書で開示する適応ランレングスＧｏｌｏｍｂ−Ｒｉｃｅ（ＲＬＧＲ）符号化器および方法とともにうまく動作する整数値に対する典型的な確率分布を示す図である。 本明細書で開示する適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）コーデックおよび方法の符号化器部分の例示的な実装形態を示す構成図である。 本明細書で開示する適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）コーデックおよび方法の復号化器部分の例示的な実装形態を示す構成図である。 図２に示す適応Ｇ／Ｒコーデックおよび方法を実装できる適切なコンピューティングシステム環境の一例を示す図である。 図２に示す適応Ｇ／Ｒ符号化器のコンポーネントを示す一般的な構成図である。 図２および４に示す適応Ｇ／Ｒ符号化器および方法の一般的な動作を示す一般的な流れ図である。 図５に示す適応Ｇ／Ｒ符号化器および方法のさらなる詳細を示す流れ図である。 図４に示す適応Ｇ／Ｒコーデックおよび方法のＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータ適応モジュールの動作の詳細な流れ図である。 図７に示すＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータ適応モジュールで使用する適応値の計算の詳細な流れ図である。 図２および４に示す適応Ｇ／Ｒ符号化器の符号化の詳細を、Ｇ／Ｒパラメータｋの適応規則を含めて示す実施例である。

符号の説明

２００ 適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化器
２１０ 第１のコンピューティング装置
２２０ 整数データ
２３０ 符号化済みビットストリーム
２３０ 符号化済みビットストリーム
２４０ Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）復号化器
２５０ 第２のコンピューティング装置
２６０ 再構成された整数データ
２００ 適応Ｇ／Ｒ符号化器
４００ 入力値
４１０ Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化モジュール
４２０ コードワード
４３０ Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータ適応モジュール
４４０ 更新したＧ／Ｒパラメータ
４５０ 次の入力値

Claims (40)

1. デジタルデータを処理する方法であって、
   前記デジタルデータの入力値の符号化をＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータを用いて行って、前記入力値に対するコードワードを生成すること、
   Ｇ／Ｒパラメータの更新を、適応規則を有する後方適応技法を用いて、前記コードワードを生成した後に行うこと、および
   前記符号化および更新を、前記デジタルデータの値ごとに繰り返すこと
   を備えることを特徴とする方法。
2. 適応値を定義すること、および
   前記適応値が０に等しい場合、前記Ｇ／Ｒパラメータを減らすこと
   をさらに備えることを特徴とする請求項１に記載の方法。
3. 前記適応値が０に等しい場合、前記Ｇ／Ｒパラメータを整数定数だけ減らすことをさらに備えることを特徴とする請求項２に記載の方法。
4. 前記適応値が１に等しい場合、前記Ｇ／Ｒパラメータを変えずにおくことをさらに備えることを特徴とする請求項２に記載の方法。
5. 前記適応値が１より大きい場合、前記Ｇ／Ｒパラメータを増やすことをさらに備えることを特徴とする請求項４に記載の方法。
6. 前記適応値が１より大きい場合、前記Ｇ／Ｒパラメータを前記適応値だけ増やすことをさらに備えることを特徴とする請求項５に記載の方法。
7. スケーリングパラメータを定義すること、および
   スケーリングしたＧ／Ｒパラメータを、前記Ｇ／Ｒパラメータに前記スケーリングパラメータを掛けたものと等しいと定義すること
   をさらに備えることを特徴とする請求項１に記載の方法。
8. 前記Ｇ／Ｒパラメータの代わりにスケーリングしたＧ／Ｒパラメータの更新を、適応規則を有する後方適応技法を用いて、前記コードワードを生成した後に行うことをさらに備えることを特徴とする請求項７に記載の方法。
9. 前記スケーリングパラメータを１６に等しく設定すること、および
   前記Ｇ／Ｒパラメータの値を前記デジタルデータの減衰パラメータに基づいて決定すること
   をさらに備えることを特徴とする請求項８に記載の方法。
10. 前記デジタルデータは、（ａ）各値に対する最も確率の高い値は０であり、（ｂ）０以外の値の確率は、前記０以外の値が増加するにつれて減少するような値を有する整数ベクトルをさらに備えることを特徴とする請求項１に記載の方法。
11. 請求項１に記載の方法を実行するためのコンピュータ実行可能命令を有することを特徴とするコンピュータ可読媒体。
12. 整数値を有するデジタル整数データを符号化するためのコンピュータ実行可能命令を有するコンピュータ可読媒体であって、前記符号化することは、
    前記整数値のそれぞれの符号化を、適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化およびＧ／Ｒパラメータｋを用いて行って、前記整数値ごとにコードワードを生成すること、
    スケーリングしたＧ／ＲパラメータＫを前記Ｇ／Ｒパラメータｋを用いて定義すること、および
    前記スケーリングしたＧ／ＲパラメータＫの更新を、後方適応規則を用いてコードワードの生成が済むごとに行うこと
    を備えることを特徴とするコンピュータ可読媒体。
13. スケーリングパラメータＬを定義すること、および
    前記スケーリングしたＧ／ＲパラメータＫを、Ｋ＝ｋ掛けるＬと定義すること
    をさらに備えることを特徴とする請求項１２に記載のコンピュータ可読媒体。
14. 前記スケーリングパラメータを２の累乗である値に等しく設定することをさらに備えることを特徴とする請求項１３に記載のコンピュータ可読媒体。
15. 前記デジタル整数データは、Ｎ個の整数を含むベクトルｘをさらに備え、前記ベクトルｘの各要素ｘ（ｎ）は、ｎ＝０からＮ−１として、確率分布が、最も確率の高い値は０であり、０からはるかに離れたところの値の確率が急速に減少するようなものであることを特徴とする請求項１２に記載のコンピュータ可読媒体。
16. 前記確率分布は、式
    

    

    で与えられ、パラメータθにより、ｘの絶対値が増加する際の確率の減衰のレートが制御されることを特徴とする請求項１５に記載のコンピュータ可読媒体。
17. 適応値ｐを定義すること、および
    ｐ＝０である場合、Ｋを（Ｋ−Ｂ３）で置き換えること
    をさらに備え、Ｂ３は整数定数であることを特徴とする請求項１２に記載のコンピュータ可読媒体。
18. ｐ＝１である場合、Ｋを変えずにおくことをさらに備えることを特徴とする請求項１７に記載のコンピュータ可読媒体。
19. ｐ＞１である場合、Ｋを（Ｋ＋ｐ）で置き換えることをさらに備えることを特徴とする請求項１８に記載のコンピュータ可読媒体。
20. ｘ＞０である場合、パラメータｕを２ｘと定義すること、
    ｘ＜０である場合、ｕを−２ｘ−１と定義すること、および
    ｐ＝ｕ＞＞ｋ、すなわちｐは右にｋ桁シフトしたｕに等しいと定義すること
    をさらに備えることを特徴とする請求項１７に記載のコンピュータ可読媒体。
21. デジタル整数データを符号化および復号化するためのコンピュータ実装プロセスであって、
    前記デジタル整数データの各値ｘの符号化を、適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化およびＧ／Ｒパラメータｋを用いて行うこと、
    スケーリングしたＧ／Ｒパラメータを、Ｌをスケーリングパラメータとして、Ｋ＝ｋ＊Ｌと定義すること、
    適応規則を有する後方適応技法を使用して、前記スケーリングしたＧ／ＲパラメータＫの更新を、前記デジタル整数データの値ｘの符号化が済むごとに行うこと、
    前記デジタル整数データの前記符号化済みの値をビットストリームに付加すること、および
    前記ビットストリームの復号化を、Ｇ／Ｒ復号化器を用いて行って、前記デジタル整数データの各値ｘを厳密に復元すること
    を備えることを特徴とするコンピュータ実装プロセス。
22. ｘ＞０である場合、ｘを、写像パラメータｕ＝２ｘで置き換えること、
    ｘ＜０である場合、ｘを、ｕ＝−２ｘ−１で置き換えること、および
    適応パラメータｐを、右にｋ桁シフトしたｕ、すなわちｐ＝ｕ＞＞ｋと定義すること
    をさらに備えることを特徴とする請求項２１に記載のコンピュータ実装プロセス。
23. 前記適応規則は、ｐ＝０の場合、Ｋを（Ｋ−Ｂ３）で置き換えることをさらに備え、Ｂ３は整数定数であることを特徴とする請求項２２に記載のコンピュータ実装プロセス。
24. 前記適応規則は、ｐ＝１の場合、Ｋを変えずにおくことをさらに備えることを特徴とする請求項２３に記載のコンピュータ実装プロセス。
25. 前記適応規則は、ｐ＞１の場合、Ｋを（Ｋ＋ｐ）で置き換えることをさらに備えることを特徴とする請求項２４に記載のコンピュータ実装プロセス。
26. １つまたは複数のプロセッサによって実行されると、請求項２１に記載のコンピュータ実装プロセスを実施させる、コンピュータ可読命令をその上に有することを特徴とする１つまたは複数のコンピュータ可読媒体。
27. 整数値を含むデジタル整数データを符号化するための適応Ｇｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化器であって、
    Ｇ／Ｒパラメータｋを有する、前記整数値を符号化するためのＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）符号化器と、
    前記Ｇ／Ｒパラメータｋの更新を、前記整数値を符号化するごとに、適応規則を有する後方適応技法を用いて行う手段と
    を備えることを特徴とする適応Ｇ／Ｒ符号化器。
28. 前記適応規則は、前記Ｇ／Ｒパラメータｋの更新を次のように行う手段をさらに備えることを特徴とする請求項２７に記載の適応Ｇ／Ｒ符号化器：
    適応値ｐを定義すること、
    ｐ＝０である場合、ｋを、整数定数だけ減らすこと、
    ｐ＝１である場合、ｋを変えずにおくこと、および
    ｐ＞１である場合、ｋを、ｐだけ増やすこと。
29. スケーリングしたＧ／ＲパラメータＫを次のように定義する手段をさらに備えることを特徴とする請求項２８に記載の適応Ｇ／Ｒ符号化器：
    スケーリングパラメータを定義すること、
    Ｓ＝ｓ＊Ｌを定義すること、および
    Ｋ＝ｋ＊Ｌを定義すること。
30. ｋの代わりにＫの更新を、前記適応規則を用いて行う手段をさらに備えることを特徴とする請求項２９に記載の適応Ｇ／Ｒ符号化器。
31. 符号化済みのビットストリームを復号化するための方法であって、
    コードワードを前記符号化済みのビットストリームから受け取ること、
    前記コードワードの復号化をＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータを用いて行うこと、
    前記Ｇ／Ｒパラメータの更新を、適応規則を有する後方適応技法を用いて、前記コードワードを復号化した後に行うこと、および
    前記復号化および更新を、前記符号化済みのビットストリームのコードワードごとに繰り返して、再構成されたデジタルデータを復元すること
    を備えることを特徴とする方法。
32. 適応値を定義すること、
    前記適応値が０に等しい場合、前記Ｇ／Ｒパラメータを減らすこと、
    前記適応値が１に等しい場合、前記Ｇ／Ｒパラメータを変えずにおくこと、および
    前記適応値が１より大きい場合、前記Ｇ／Ｒパラメータを増やすこと
    をさらに備えることを特徴とする請求項３１に記載の方法。
33. 前記適応値が０に等しい場合、前記Ｇ／Ｒパラメータを整数定数だけ減らすことをさらに備えることを特徴とする請求項３２に記載の方法。
34. 前記適応値が１より大きい場合、前記Ｇ／Ｒパラメータを前記適応値だけ増やすことをさらに備えることを特徴とする請求項３２に記載の方法。
35. スケーリングパラメータを定義すること、および
    スケーリングしたＧ／Ｒパラメータを、前記Ｇ／Ｒパラメータ掛ける前記スケーリングパラメータに等しいと定義すること
    をさらに備えることを特徴とする請求項３１に記載の方法。
36. 請求項３１に記載の方法を実行するためのコンピュータ実行命令を有することを特徴とするコンピュータ可読媒体。
37. 符号化済みビットストリームへの符号化が、前記デジタル整数データの入力値の符号化をＧｏｌｏｍｂ−Ｒｉｃｅ（Ｇ／Ｒ）パラメータを用いて行って前記入力値に対するコードワードを生成し、前記Ｇ／Ｒパラメータの更新を適応規則を有する後方適応技法を用いて、前記コードワードを生成した後に行い、前記符号化および更新を、前記デジタル整数データの入力値ごとに繰り返す符号化プロセスによって行われた前記デジタル整数データを復号化するためのプロセスであって、
    一連のコードワードを前記符号化済みビットストリームから受け取ること、
    前記コードワードのそれぞれの復号化を、適応Ｇ／Ｒ復号化器およびＧ／Ｒパラメータｋを用いて行うこと、
    スケーリングしたＧ／ＲパラメータＫの定義を、前記Ｇ／Ｒパラメータｋを用いて行うこと、および
    前記スケーリングしたＧ／ＲパラメータＫの更新を、コードワードの復号化が済むごとに、適応規則を有する前記後方適応技法を用いて行うこと
    を備えることを特徴とするプロセス。
38. 適応値ｐを定義すること、および
    ｐ＝０である場合、前記スケーリングしたＧ／ＲパラメータＫを、Ｂ３を整数定数として、（Ｋ−Ｂ３）で置き換えること
    をさらに備えることを特徴とする請求項３７に記載のプロセス。
39. ｐ＝１である場合、前記スケーリングしたＧ／ＲパラメータＫを変えずにおくことをさらに備えることを特徴とする請求項３７に記載のプロセス。
40. ｐ＞１である場合、前記スケーリングしたＧ／ＲパラメータＫを（Ｋ＋ｐ）で置き換えることをさらに備えることを特徴とする請求項３７に記載のプロセス。
    

Images