(57)【要約】【課題】  大きなルックアップテーブルを使用せずに入力を指数ゴロムコードへとエンコードすることによりデータ圧縮を遂行する方法及びシステムを提供する。【解決手段】  請求の範囲に述べる要旨の実施形態は、入力を指数ゴロムコードへエンコードすることによりデータ圧縮を遂行する方法及びシステムを提供する。一実施形態において、データ入力のデータ圧縮は、アンサインド指数ゴロムコードとしてエンコードすることを経て達成される。この方法は、入力を変換し、非ゼロ値を有する変換された入力の最上位ビット（ＭＳＢ）の位置を決定し、ＭＳＢの位置から情報を導出し、その情報を演算的にエンコードして、圧縮された出力を導出することにより、達成される。【選択図】図２
2010141884.tif 000002
【特許請求の範囲】
【請求項１】
データのアンサインド入力をアンサインド指数ゴロムコードとして圧縮するための方法であって、
２進データを含む第１長さの入力を受け取るステップと、
前記入力をシフトされた入力へと変換するステップと、
前記シフトされた入力に対する最上位ビット（ＭＳＢ）位置を決定するステップと、
前記ＭＳＢ位置から前記入力に対応する複数の情報を導出するステップと、
前記複数の情報を演算的にエンコードし、前記第１長さ以下のコード長を有する圧縮された出力を導出するステップと
を備える方法。
【請求項２】
前記入力をシフトされた入力へと変換する前記ステップは、
前記入力に値を加算して、増分された入力を生成する工程と、
前記増分された入力の最下位ビットを破棄して、シフトされた入力を構成する工程と
を含む請求項１に記載の方法。
【請求項３】
最上位ビット（ＭＳＢ）位置を決定する前記ステップは、前記シフトされた入力における非ゼロ値をもつ最上位桁の位置に対応する値を決定する工程を含む、請求項１に記載の方法。
【請求項４】
複数の情報を導出する前記ステップは、前記シフトされた入力に対する前記ＭＳＢ位置に対応する複数の値についてデータのルックアップテーブルを参照する工程を含む、請求項１に記載の方法。
【請求項５】
前記入力は１６ビットの２進値であり、前記ルックアップテーブルは３２のエントリーを含む、請求項４に記載の方法。
【請求項６】
前記入力は１６ビットの２進値であり、
前記複数の情報を導出する前記ステップは、
前記ＭＳＢ位置に対応する前記コード長を導出する工程と、
前記ＭＳＢ位置に対応する３３ビットストリングを含むプレフィックスを導出する工程と、
前記ＭＳＢ位置に対応する可変桁値を含むプレフィックス値を導出する工程と、
予め定義された値から前記コード長を減算したものに等しい値を含むサフィックスシフト値を導出する工程と
を含む、請求項１に記載の方法。
【請求項７】
前記複数の情報を演算的にエンコードする前記ステップは、
前記サフィックスシフト値、前記増分された値、及び前記プレフィックス値から最終的サフィックスを導出する工程と、
前記最終的サフィックス値及び前記プレフィックスから前記入力を表す前記圧縮された出力を発生する工程と
を含む、請求項６に記載の方法。
【請求項８】
前記最終的サフィックスを導出する前記工程は、
前記プレフィックス値及び前記増分された値から、ビットのストリングを含むサフィックスを導出する工程と、
前記サフィックスを前記サフィックスシフト値でバレルシフトする工程と
を含む、請求項７に記載の方法。
【請求項９】
前記圧縮された出力を発生する工程は、前記最終的サフィックス及び前記プレフィックスに対してビット単位ＯＲを遂行する工程を含む、請求項８に記載の方法。
【請求項１０】
前記圧縮された出力は、コンテクスト適応可変長さコード（ＣＡＶＬＣ）である、請求項１に記載の方法。
【請求項１１】
前記ＣＢＡＶＬＣは、指数ゴロムコードである、請求項１０に記載の方法。
【請求項１２】
データのサインド入力を圧縮するための方法であって、
２進データを含む第１長さの入力を受け取るステップと、
前記入力を前記入力の絶対値へと変換するステップと、
ルックアップテーブルにおいて前記入力の前記絶対値を参照するステップと、
前記ルックアップテーブルから前記入力の前記絶対値に対応する複数の情報を導出するステップと、
前記複数の情報を演算的にエンコードし、前記第１長さ以下のコード長を有する圧縮された出力を導出するステップと
を備える方法。
【請求項１３】
前記入力は１６ビット値であり、前記ルックアップテーブルは３２のエントリーを含む、請求項１２に記載の方法。
【請求項１４】
前記複数の情報を導出する前記ステップは、
非ゼロ値を有する前記入力の前記絶対値におけるＭＳＢ位置に対応する値に対応する前記コード長を導出する工程と、
前記ＭＳＢ位置に対応するビットのストリングを含むプレフィックスを導出する工程と、
前記入力の桁に対応する修正されたプレフィックス値を導出する工程と、
予め定義された値から前記コード長を減算したものに等しい値を含むサフィックスシフト値を導出する工程と
を含む、請求項１２に記載の方法。
【請求項１５】
前記複数の情報を演算的にエンコードする前記ステップは、
前記入力の前記絶対値及び前記サフィックスシフトから、ビットのストリングを含むサフィックスを導出する工程と、
前記サフィックス、及び前記サフィックスシフト値から最終的サフィックスを導出する工程と、
前記最終的サフィックス値及び前記プレフィックスから前記入力を表す前記圧縮された出力を発生する工程と
を含む、請求項１４に記載の方法。
【請求項１６】
前記サフィックスを導出する前記工程は、
前記入力の前記絶対値を所定量だけ左にシフトすることによりシフトされた入力を導出する工程と、
前記シフトされた入力から前記修正されたプレフィックス値を減算する工程と
を含む、請求項１５に記載の方法。
【請求項１７】
データを変換する回路であって、
入力２進値を受け取ってそれに加算するように結合された増分器と、
前記増分器の出力に結合されてそれをシフトするシフタと、
前記シフタの出力に結合されて、コード長出力、第２出力、第３出力及び第４出力を発生するためのルックアップテーブルと、
前記増分器の前記出力、並びに前記ルックアップテーブルの前記第２出力、前記第３出力及び前記第４出力に結合されて、前記コード長出力に対応するコード出力値を発生するための減算器、バレルシフタ及びＯＲゲートと
を備える回路。
【請求項１８】
前記入力は、アンサインド２進データであり、
前記コード出力値は、アンサインド指数ゴロムコードとしてエンコードされる、請求項１７に記載の回路。
【請求項１９】
前記入力は、サインド２進データであり、
前記コード出力値は、サインド指数ゴロムコードとしてエンコードされる、請求項１７に記載の回路。
【請求項２０】
前記入力は１６ビット値であり、前記ルックアップテーブルは３２以下のエントリーを含む、請求項１８に記載の回路。
【発明の詳細な説明】
【背景技術】
【０００１】
[0001]データ圧縮は、ファイル又はオブジェクトを構成するデータの量（例えば、ビットの数）を減少するための良く知られた技術である。データ圧縮の使用は、送信及び記憶の両方の目的で普及している。典型的な具現化では、データを表すのに使用される情報をより小さな、より効率的な量のデータへエンコードすることによりデータの不必要な繰り返しを減少又は排除するアルゴリズムを使用することでデータ圧縮が達成される。
【０００２】
[0002]映像を表すのに必要なビットの数を減少するために、可変長さコーディング（ＶＬＣ）又はコンテクスト適応可変長さコーディング（ＣＡＶＬＣ）のようなアルゴリズムを使用することができる。典型的なデータ圧縮スキームでは、正の整数を２進コードワードへマップするプレフィックスコードが整数に対して使用される。一般的に、整数のためのほとんどのプレフィックスコードは、大きな整数に長いコードワードを指定する。このようなコードは、考えられるメッセージのセットから引き出されたメッセージを効率的に通信するのに使用することができ、これは、単に、それらメッセージのセットを低下する確率に従って順序付けし、次いで、意図されたメッセージのインデックスを送信することにより行われる。
【０００３】
[0003]指数ゴロム(Exp-Golomb)コーディングは、コンテクスト適応可変長さコーディングの一例である。指数ゴロムコードは、可変長さコードであり、アドバンスドビデオコーディング（ＡＶＣ）（例えば、Ｈ．２６４）に広く使用されている。しかしながら、他の可変長さコード（例えば、ハフマンコード）と同様に、指数ゴロムコードをデコードすることは、若干困難である。というのは、入力データ長さが変化して、予想できないからである。
【０００４】
[0004]典型的な指数ゴロムエンコーディングアルゴリズムでは、所与の指数ゴロムコードセットの全ての個々のコードワードが独特なものである。又、所与のコードワードのｎ個の最上位ビット（ＭＳＢ）は、長さｎの他のコードワードとは常に異なる。更に、指数ゴロムコードワードは、多数の「先導ビット」と、それに続く別の数の値ビットとで構成され、この値ビットは、特定コードワードの値を指定する上で役立つように使用される。値ビットの数は、（典型的に）先導ビットの数よりも１つ少ない。コードワードの先導ビットは、多数の先導０ビットと、それに続く１つの１ビットとを含む。先導０ビットの数は、そのコードワードに対する値ビットの数と同じである。短いコードワード（例えば、１桁のコードワード）の場合、先導ビットの長さが１であれば、そのコードワードに対して先導０ビット及び値ビットは存在しない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
[0005]指数ゴロムコードをエンコードするための従来の技術は、所与のコードワードに対応するコード番号をルックアップするためにテーブルマッピングを使用することをしばしば含む。このような技術では、デコーディングルックアップテーブルにおけるエントリーの数が２＾（考えられる最長のコード長）に等しい。例えば、最大コード長が８である場合には、テーブルは、２８（２５６）個のエントリーを有し、典型的に、コード長が長いほど、そのテーブルに対して指数関数的に大きなメモリサイズを必要とする。コード長は可変であり、１６ビットの長さ及び３２ビットの長さが典型的であるから、ルックアップテーブルに必要なメモリのサイズは、相当なものとなり、ハードウェアで具現化するのに大きなシリコンエリアを必要とする。加えて、大きなルックアップテーブルをシリアルに横断するのに必要な時間も、顕著なものであり、不必要な変換遅延を招く。
【０００６】
[0006]更に、これらの技術は、一般に、アンサインド入力のみに適用され、アンサインドの指数ゴロムコードを出力として発生する。従って、サインド（例えば、負の）入力をエンコードするには、典型的に、指数ゴロムコードへ変換する前にサインド入力から正の入力への余計な変換を必要とする。当然、この中間変換は、これを遂行するのに付加的なコンポーネントを必要とし、又は付加的な処理時間を費やすことがある。
【課題を解決するための手段】
【０００７】
[0007]本発明の実施形態は、大きなルックアップテーブルを使用せずに入力を指数ゴロムコードへとエンコードすることによりデータ圧縮を遂行するための方法及びシステムに向けられる。アンサインドデータ入力をアンサインド指数ゴロムへとエンコードできるようにする方法が提供される。
【０００８】
[0008]１つの新規な方法は、アンサインドデータ入力のデータ圧縮を、アンサインド指数ゴロムコードとしてエンコードすることにより達成する。この方法は、比較的小さなルックアップテーブルと、ここに述べる一連の演算オペレーションとの組合せにより達成される。別の新規な方法は、サインドデータを圧縮する能力を提供する。この方法は、アンサインドシンタックス値への初期変換を行わずに達成され、又、同様に、比較的小さなルックアップテーブルと、ここに述べる一連の演算オペレーションとの組合せにより達成される。
【０００９】
[0009]ここに述べる実施形態は、好都合にも、比較的小さなシリコンエリアを使用して高速データ変換を行うことができる。又、回路設計では、容易に合成できるコンポーネント、例えば、増分器、加算器／減算器、バレルシフタ等も使用される。アンサインド及びサインド入力値についての変換も説明する。
【００１０】
[0010]本明細書の一部分として含まれた添付図面は、本発明の実施形態を示し、そして以下の記述と共に、本発明の原理を説明する上で役立つ。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態によるアンサインド入力のための指数ゴロムエンコーディングプロセスを例示するフローチャートである。
【図２】本発明の実施形態によりアンサインド指数ゴロムコードをエンコードするためのハードウェア具現化を構成する論理的コンポーネントのコンフィギュレーションを例示するブロック図である。
【図３】本発明の実施形態によるサインド入力のための指数ゴロムエンコーディングプロセスを例示するフローチャートである。
【図４】本発明の実施形態によりサインド指数ゴロムコードをエンコードするためのハードウェア具現化を構成する論理的コンポーネントのコンフィギュレーションを例示するブロック図である。
【発明を実施するための形態】
【００１２】
[0015]以下、幾つかの実施形態を詳細に説明する。本発明の要旨は、それら実施形態に関連して説明するが、請求の範囲に述べる要旨は、それら実施形態に限定されるものでないことを理解されたい。逆に、請求項に述べる要旨は、特許請求の範囲で規定される要旨の精神及び範囲内に包含される代替物、変更及び等効物を網羅することが意図される。
【００１３】
[0016]更に、以下の詳細な説明において、請求項で述べる要旨を完全に理解するために多数の特定の細部について述べる。しかしながら、当業者であれば、これらの特定の細部又はその等効物がなくても、実施形態を具現化できることが理解されよう。他の点では、要旨の態様及び特徴を不必要に不明瞭にしないために、良く知られたプロセス、手順、コンポーネント、及び回路は、詳細に説明しない。
【００１４】
[0017]以下の詳細な説明の各部分は、あるプロセスに関して表現され説明される。ステップ及びそのシーケンスは、そのプロセスのオペレーションを示す図面（例えば、図１、３）に開示されるが、そのようなステップ及びシーケンスは、例示に過ぎない。これらの実施形態は、添付図面のフローチャートに示されたステップの変形、又は種々の他のステップを、そこに示された以外のシーケンスで遂行するのにも適している。
【００１５】
[0018]詳細な説明のある部分は、コンピュータメモリにおいて遂行できるデータビットに対するオペレーションの手順、ステップ、論理的ブロック、処理及び他の象徴的表示に関して表現される。これらの説明及び表示は、データ処理技術の当業者が彼らの仕事の実体を別の当業者へ最も効果的に伝達するために使用される手段である。手順、コンピュータ実行ステップ、論理的ブロック、プロセス、等は、ここでは、一般的に、望ましい結果を導くステップ又はインストラクションの自己矛盾のないシーケンスと考えられる。これらのステップは、物理的な量の物理的な操作を要求するものである。通常、必ずしもそうでないが、これらの量は、コンピュータシステムにおいて記憶、転送、合成、比較、及びその他、操作することのできる電気信号又は磁気信号の形態をとる。時々は、主として、通常の使い方の理由で、これらの信号を、ビット、値、エレメント、記号、キャラクタ、用語、数字、等と称するのが便利であると分かっている。
【００１６】
[0019]しかしながら、これらの用語及び同様の用語は、全て、適当な物理的量に関連付けされるべきであり、且つそれらの量に適用される便利な表示に過ぎないことを銘記されたい。特に指示のない限り、以下の説明から明らかなように、全体を通じて、「アクセス(accessing)」、「書き込む(writing)」、「含む(including)」、「記憶(storing)」、「送信(transmitting)」、「横断(traversing)」、「関連付け(associating)」、「「識別(identifying)」、等の用語を使用する説明は、コンピュータシステムのレジスタ及びメモリ内の物理的（電子的）量として表されたデータを、コンピュータシステムのメモリ又はレジスタ、或いは他のそのような情報記憶、送信又はディスプレイ装置内の物理的量として同様に表された他のデータへと操作及び変換するコンピュータシステム又は同様の電子的コンピューティング装置のアクション及びプロセスを指すものであることが明らかである。
【００１７】
[0020]以下の例示的コンフィギュレーションは、列挙される特定の特徴及び要素を組み込むものとして示されるが、このような描写は、例示に過ぎないことを理解されたい。従って、それらの実施形態は、異なる、付加的な又はより少数の要素、特徴又は構成を含む用途に良く適している。
【００１８】
例示的なアンサインド指数ゴロムエンコーディングプロセス
[0021]図１を参照すれば、本発明の種々の実施形態によりアンサインド(unsigned)入力をアンサインド指数ゴロム(Exp-Golomb)コードとしてエンコードするための例示的プロセス１００のフローチャートが示されている。このプロセス１００は、例えば、ビデオ処理装置のような処理システムのプロセッサにより遂行することができる。ステップ１０１−１０９は、図２を参照してここに述べる専用ロジックにより遂行されてもよい。
【００１９】
[0022]図１のステップ１０１において、アンサインド入力データが受け取られる。この入力は、例えば、指数ゴロムコードとしてエンコードされるべきアンサインド整数を含む。一実施形態では、この入力は、２進で受け取られ、種々のデータブロックからのシンタックスエレメントに対応する。更に別の実施形態では、この入力は、例えば、１６ビットバスを使用して受け取られる、１ビットと１６ビットとの間（それらを含めて）の長さを有する２進値でよい。
【００２０】
[0023]ステップ１０３において、ステップ１０１で受け取られた入力が、シフトされた入力へと変換される。受け取られた入力を変換することは、例えば、ある値を入力に加算し、その和をベクトルによって論理的にシフトすることを含む。一実施形態では、入力に加算される値は、１に等しい（演算的に）。入力に値を加算することは、例えば、増分器により遂行することができる。更に別の実施形態では、シフトベクトルの大きさは、右方向に１である。例えば、入力を変換することは、入力に１を加算し、それにより得られる和（２進）を１桁右へシフトして、最下位ビット（例えば、入力及び値の和の最も右のビット）が除去（例えば、破棄）されるようにすることを含む。典型的な実施形態では、最下位ビットを破棄するのに、付加的な論理ゲートが必要とされない。
【００２１】
[0024]ステップ１０５において、非ゼロ値（例えば、１）を有するシフトされた入力の最上位ビットの位置が決定される。最上位の非ゼロビットの位置（ＭＳＢ位置）を決定することは、例えば、最上位ビットからスタートして最下位ビットへ進むようにして、シフトされたデータのビットを通してシリアルにスイープし、第１の（最上位の）“１”値を検出することを含む。
【００２２】
[0025]ステップ１０７では、ステップ１０５で決定されたシフトされた入力の最上位非ゼロビットの位置から情報が導出される。一実施形態においては、最上位非ゼロビットの位置の値に対してルックアップテーブルを参照することにより情報が導出される。更に別の実施形態では、ルックアップテーブルは、（１６ビット入力の場合に）３２以下のエントリーを含む。
【００２３】
[0026]一実施形態では、ステップ１０７で導出された情報は、最上位の非ゼロビットの位置に対応する予め定義された数のビットを有する値より成るプレフィックスを含む。更に別の実施形態では、プレフィックスは、３３ビットの値であり、この値における全てのビットは、１の値にセットされた第ｎ番目のビットを除いて、０であり、ここで、ｎは、３３の値、即ちＭＳＢ位置である（考えられる最大サイズが１６ビットの入力の場合）。例えば、ステップ１０３で変換されたシフトされた入力において、非ゼロ値を有する最上位ビットが右から第３番目のビットである場合に、ＭＳＢ位置が３の値を有し、ｎが３０の値を有し、そしてプレフィックスが３３ビット値であり、この値の各ビットは、１にセットされた第３０番目のビットを除いて０である。
【００２４】
[0027]ある実施形態では、ステップ１０７で導出された情報は、可変数のビットを有する２進値であるプレフィックス値も含む。一実施形態では、プレフィックス値は、最上位非ゼロビットの値に等しい大きさだけ左にシフトされた１を含む。先の実施例を続けると、３の値を有するＭＳＢ位置に対するプレフィックス値は、１０００（１が３桁左にシフトされた）に等しい。
【００２５】
[0028]ある実施形態では、ステップ１０７で導出された情報は、プロセッサ１００により発生される指数ゴロムエンコードビットストリングの長さより成るコード長も含む。一実施形態では、コード長は、ＭＳＢ位置の値に２を乗算し、それによって生じる積に１を加算することにより導出される。
【００２６】
[0029]更に別の実施形態では、ステップ１０７で導出された情報は、サフィックスシフト値を含んでもよい。一実施形態では、サフィックスシフト値は、数字３３からコード長を減算することにより導出されてもよい。
【００２７】
[0030]最終的に、ステップ１０９において、ステップ１０７で導出された情報が演算的にエンコードされて、アンサインド出力を発生する。一実施形態では、この情報は、（予め定義された数のビットを有する値より成る）サフィックスを導出し、そしてサフィックスの値とステップ１０７で導出されたプレフィックスの値とのビット単位ＯＲを遂行することにより演算的にエンコードされる。一実施形態では、サフィックスは、ステップ１０７で導出されたプレフィックスの値を、ステップ１０１で受け取られた入力と、ステップ１０３で加算された値（例えば、１）との和から減算することにより、導出される。更に別の実施形態では、サフィックスは、ステップ１０７で導出されたプレフィックスの値とのビット単位ＯＲを実行する前に、ステップ１０７で導出されたサフィックスシフト値によりサフィックスをバレル左シフトすることで、最終的なサフィックス値へと先ず変換される。
【００２８】
[0031]それにより得られるデータストリング（例えば、３３ビットストリング）が出力され、そしてステップ１０７で導出されたコード長と合成されると、ステップ１０１で受け取られた入力に対するアンサインド指数ゴロムエンコーディングに対応する。一実施形態では、ビットストリング出力の最初のｍビットは、圧縮されたファイル又はオブジェクトを構成する指数ゴロムエンコーディングのビットストリームと合成され（例えば、それが添付され）、ここで、ｍは、コード長に等しい。従って、指数ゴロムエンコーディングを使用するデータ圧縮は、サイズが大幅に減少された参照として使用されるルックアップテーブルで達成することができ、参照のためにルックアップテーブルをシリアルに横断するのに要する遅延及び材料コストを節減し、且つエンコーディングを行うハードウェアプラットホームをより小さくすることができる。
【００２９】
[0032]プロセス１００のための例示的擬似コードが以下のテーブルＩに示されている。
テーブルＩ
assign data_in_plus1 = data_in +1;
assign data_in_plus1_div2 = data_in_plus1 >> 1;
always @ (data_in_plus1_div2) begin
if (data_in_plus1_div2[15]) begin
size_lz = 16;
prefix =000000000000000010000000000000000;
prefix_value = (1 << 16);
end
else if (data_in_plus1_div2[14]) begin
size_lz = 15;
prefix =000000000000000100000000000000000;
prefix_value = (1 << 15);
end
else if (data_in_plus1_div2[13]) begin
size_lz = 14;
prefix =000000000000001000000000000000000;
prefix_value = (1 << 14);
end
else if (data_in_plus1_div2[12]) begin
size_lz = 13;
prefix =000000000000010000000000000000000;
prefix_value = (1 << 13);
end
else if (data_in_plus1_div2[11]) begin
size_lz = 12;
prefix =000000000000100000000000000000000;
prefix_value = (1 << 12);
end
else if (data_in_plus1_div2[10]) begin
size_lz = 11;
prefix =000000000001000000000000000000000;
prefix_value = (1 << 11);
end
else if (data_in_plus1_div2[9]) begin
size_lz = 10;
prefix =000000000010000000000000000000000;
prefix_value = (1 << 10);
end
else if (data_in_plus1_div2[8]) begin
size_lz = 9;
prefix =000000000100000000000000000000000;
prefix_value = (1 << 9);
end
else if (data_in_plus1_div2[7]) begin
size_lz = 8;
prefix =000000001000000000000000000000000;
prefix_value = (1 << 8);
end
else if (data_in_plus1_div2[6]) begin
size_lz = 7;
prefix =000000010000000000000000000000000;
prefix_value = (1 << 7);
end
else if (data_in_plus1_div2[5]) begin
size_lz = 6;
prefix =000000100000000000000000000000000;
prefix_value = (1 << 6);
end
else if (data_in_plus1_div2[4]) begin
size_lz = 5;
prefix =000001000000000000000000000000000;
prefix_value = (1 << 5);
end
else if (data_in_plus1_div2[3]) begin
size_lz = 4;
prefix =000010000000000000000000000000000;
prefix_value = (1 << 4);
end
else if (data_in_plus1_div2[2]) begin
size_lz = 3;
prefix =000100000000000000000000000000000;
prefix_value = (1 << 3);
end
else if (data_in_plus1_div2[1]) begin
size_lz = 2;
prefix =001000000000000000000000000000000;
prefix_value = (1 << 2);
end
else if (data_in_plus1_div2[0]) begin
size_lz = 1;
prefix =010000000000000000000000000000000;
prefix_value = (1 << 1);
end
else begin
size_lz = 0;
prefix =100000000000000000000000000000000;
prefix_value = 1 << 0);
end
end
assign suffix = data_in_plus1 - prefix_value;
assign size_lz_m2 = (size_lz << 1);
assign codelength =  (size_lz_m2 + 1);
assign suffix_shift = (6 - codelength);
assign suffix_shifted = suffix << suffix_shift;
assign code_n_rev = prefix | suffix_shifted;
assign code = code_n_rev;
例示的アンサインド指数ゴロムエンコーディングハードウェアコンフィギュレーション
【００３０】
[0033]図２を参照すれば、本発明の実施形態により、アンサインド指数ゴロムコードをエンコーディングするためのハードウェア具現化を構成する論理回路コンポーネントの例示的ハードウェアコンフィギュレーション２００のブロック図が示されている。このコンフィギュレーション２００は、例えば、図１のプロセス１００のための例示的ハードウェア具現化を構成する。
【００３１】
[0034]典型的な構成において、図２のコンフィギュレーション２００は、増分回路２０１、ルックアップテーブルメモリ２０５、減算回路２０７、バレルシフタ回路２０９及び論理ゲート２１１を備えている。入力及び出力バスのビットサイズは、単なる例示に過ぎないことを理解されたい。一実施形態では、入力を指数ゴロムコードとしてエンコードするためのプロセスは、図１のステップ１０１を参照して述べたように、入力を変更することを含む。この実施例では、入力は、１６ビット値である。入力を変更することは、例えば、予め定義された値を入力に加算し、この値と入力との和を右へシフトすることを含む。一実施形態では、予め定義された値は、１であり、この値（１）を入力に加算することは、増分器２０１により遂行される。増分器２０１は、例えば、デジタル回路（例えば、加算器）として具現化することができる。状態２０３において、入力の増分された値は、１桁だけ右シフトされ、これにより、増分された値の最下位ビットを除去する。ある実施形態では、最下位ビットの除去は、演算で遂行することができ（例えば、演算論理ユニットにより）、これを遂行する専用の論理回路を必要としない。
【００３２】
[0035]プロセス１００では、シフトされた入力のＭＳＢ位置に対応する情報は、ルックアップテーブルメモリ２０５内のＭＳＢ位置を参照することによって導出することができる。一実施形態では、ルックアップテーブル２０５は、入力の最大長さに対応する。例えば、最大長さが１６ビットの入力に対するルックアップテーブル２０５は、３２以下のエントリーを含み、各エントリーは、ステップ１０７を参照して述べたように、プレフィックス（例えば、ｐｒｅｆｉｘ＿ｖａｌｕｅ、等）を導出するのに充分な情報を含む。
【００３３】
[0036]ルックアップテーブル２０５から導出された情報は、一連の演算及び論理オペレーションを遂行することにより入力をアンサインド指数ゴロムコードへ演算的にエンコードするのに使用される。一実施形態では、入力をアンサインド指数ゴロムコードへ演算的にエンコードすることは、サフィックスを導出し、サフィックスをバレルシフトし、そしてそのバレルシフトされたサフィックスと、ルックアップテーブル２０５から導出されたプレフィックスとのビット単位ＯＲを遂行することを含む。更に別の実施形態では、増分器２０１で増分された入力とルックアップテーブル２０５から導出されたプレフィックス値との減算によってサフィックスが導出される。入力を減算することは、例えば、減算器２０７により遂行することができる。一実施形態では、減算器２０７は、デジタル回路である。
【００３４】
[0037]一実施形態では、サフィックスは、（ルックアップテーブル２０５から得られた）サフィックスシフト値に等しいビット数だけバレルシフトされる。サフィックスシフト値だけサフィックスをバレルシフトすることは、例えば、バレルシフタ２０９において行うことができる。一実施形態では、バレルシフタ２０９は、複数のマルチプレクサを含むデジタル回路として具現化することができる。次いで、バレルシフタ２０９から得られた最終的なサフィックスと、ルックアップテーブル２０５から導出されたプレフィックスとに対してビット単位ＯＲが遂行される。ビット単位ＯＲは、例えば、デジタル回路の論理ゲートで遂行することができる。それにより得られる出力は、長さが入力に対応する３３ビットまでの長さのアンサインド指数ゴロムコードを含む。ルックアップテーブル２０５から発生される５ビット出力バス上のコード長値は、アンサインド指数ゴロムコードにおいて関連ビットを区別する。
【００３５】
例示的なサインド指数ゴロムエンコーディングプロセス
[0038]図３を参照すれば、種々の実施形態によりサインド入力をサインド指数ゴロムコードとしてエンコーディングするための例示的プロセス３００のフローチャートが示されている。このプロセス３００は、例えば、ビデオ処理装置のような処理システムのプロセッサ、又は図４のような専用ハードウェアによって遂行することができる。
【００３６】
[0039]ステップ３０１において、サインド入力値が受け取られる。この入力は、例えば、指数ゴロムコードとしてエンコードされるべきサインド整数を含む。一実施形態では、入力がサインド整数を受け取り、これは、種々のデータブロックからのシンタックスエレメントに対応する。更に別の実施形態では、入力は、１ビットと１６ビットとの間（それらを含めて）の長さを有する。
【００３７】
[0040]ステップ３０３において、ステップ３０１で受け取られた入力は、入力の絶対値へ変換される。受け取られた入力を絶対値へ変換することは、例えば、入力を、その入力の２進値の２の補数へ変換することを含む。入力を、その入力の２進値の２の補数へ変換することは、（ビット単位ＮＯＴオペレーションにより）２進値を反転し、そしてそれにより得られた値に１の値を加算することにより行われる。１の値を加算することは、例えば、増分器において遂行される。
【００３８】
[0041]ステップ３０５において、非ゼロ（例えば、１）値を有する入力の絶対値（例えば、２の補数）の最上位ビットの位置が決定される。最上位の非ゼロビットの位置（ＭＳＢ位置）を決定することは、例えば、最上位ビットからスタートして最下位ビットへ進むようにして、シフトされたデータのビットを通してシリアルにスイープし、第１の（最上位の）“１”値を検出することを含む。
【００３９】
[0042]ステップ３０７では、ステップ３０５で決定された入力の絶対値の最上位非ゼロビットの位置から情報が導出される。一実施形態においては、最上位非ゼロビットの位置の値に対してルックアップテーブルを参照することにより情報が導出される。更に別の実施形態では、ルックアップテーブルは、（１６ビット入力の場合に）３２以下のエントリーを含む。要求されるルックアップテーブルが３２以下のエントリーしかもたないことで、ルックアップテーブルをハードウェアで具現化するのに必要な１つ以上のシリコンエリアのサイズは、典型的に、２１６（６５，５３６）又は２３２（４，２９４，９６７，２９６）のエントリーを有するルックアップテーブルを含む従来の技術に対して、著しく減少される。
【００４０】
[0043]一実施形態では、ステップ３０７で導出された情報は、最上位の非ゼロビットの位置に対応する予め定義された数のビットを有する値より成るプレフィックスを含む。更に別の実施形態では、プレフィックスは、３３ビットの値であり、この値における全てのビットは、１の値にセットされた第ｎ番目のビットを除いて、０であり、ここで、ｎは、３３の値、即ちＭＳＢ位置である（考えられる最大サイズが１６ビットの入力の場合）。例えば、ステップ１０３で変換されたシフトされた入力において、非ゼロ値を有する最上位ビットが右から第３番目のビットである場合に、ＭＳＢ位置が３の値を有し、ｎが３０の値を有し、そしてプレフィックスが３３ビット値であり、この値の各ビットは、１にセットされた第３０番目のビットを除いて０である。
【００４１】
[0044]ある実施形態では、ステップ３０７で導出された情報は、可変数のビットを有する２進値であるプレフィックス値も含む。一実施形態では、プレフィックス値は、最上位非ゼロビットの値に等しい大きさだけ左にシフトされた１を含む。先の実施例を続けると、３の値を有するＭＳＢ位置に対するプレフィックス値は、１０００（１が３桁左にシフトされた）に等しい。更に別の実施形態では、プレフィックス値は、修正されたプレフィックス値を導出するように更に変更することができる。一実施形態では、修正されたプレフィックス値を導出することは、入力の第１６番目のビットの値にプレフィックス値を加算し、それにより得られる和を、ステップ３０１で受け取られた入力の逆数（例えば、ＮＯＴオペレーションを遂行した後に得られる値）に対して論理的ＯＲすることを含む。換言すれば、第１５番目のビットが１に等しいか、又はｄａｔａ＿ｉｎにおける全てのビットが０である場合には、プレフィックス値に１が加算される。さもなければ、修正されたプレフィックス値は、プレフィックス値と同じ値を有する。
【００４２】
[0045]ある実施形態では、ステップ３０７で導出された情報は、プロセッサ３００により発生される指数ゴロムエンコードビットストリングの長さより成るコード長も含む。一実施形態では、コード長は、ＭＳＢ位置の値に２を乗算し、それによって生じる積に１を加算することにより導出される。
【００４３】
[0046]更に別の実施形態では、ステップ３０７で導出された情報は、サフィックスシフト値を含んでもよい。一実施形態では、サフィックスシフト値は、数字３３からコード長を減算することにより導出されてもよい。
【００４４】
[0047]最終的に、ステップ３０９において、ステップ３０７で導出された情報が演算的にエンコードされて、サインド出力を発生する。一実施形態では、この情報は、（予め定義された数のビットを有する値より成る）サフィックスを導出し、そしてサフィックスの値とステップ３０７で導出されたプレフィックスの値とのビット単位ＯＲを遂行することにより演算的にエンコードされる。一実施形態では、サフィックスは、ステップ３０７で導出された修正されたプレフィックスの値を、ステップ３０１で受け取られた入力の絶対値と、ステップ３０３で加算された値（例えば、１）との和から減算することで、導出される。更に別の実施形態では、サフィックスは、ステップ３０７で導出されたプレフィックスの値とのビット単位ＯＲを実行する前に、ステップ３０７で導出されたサフィックスシフト値によりサフィックスをバレル左シフトすることで、最終的なサフィックス値へと先ず変換される。
【００４５】
[0048]それにより得られるデータストリング（例えば、３３ビットストリング）が出力され、そしてステップ３０７で導出されたコード長と合成されると、ステップ３０１で受け取られた入力に対するサインド指数ゴロムエンコーディングに対応する。一実施形態では、ビットストリング出力の最初のｍビットは、圧縮されたファイル又はオブジェクトを構成する指数ゴロムエンコーディングのビットストリームと合成され（例えば、それが添付され）、ここで、ｍは、コード長に等しい。上述されたコスト及び遅延を減少する利益に加えて、付加的なコンポーネントを必要としたり又は遂行するのに付加的な処理時間を費やしたりするアンサインドシンタックス値への変換を介在させずに、指数ゴロムコードを経て達成されるデータ圧縮を、サインド入力に対して直接遂行することができる。
【００４６】
[0049]プロセス３００のための例示的擬似コードが以下のテーブルIIに示されている。
テーブルII
assign data_abs =data_in[15] ? ((~data_in) + 1) : data_in;
always @(data_abs) begin
if (data_abs[15]) begin
size_lz = 16;
prefix =000000000000000030000000000000000;
prefix_value = (1 << 16);
end
else if (data_abs[14]) begin
size_lz = 15;
prefix =000000000000000300000000000000000;
prefix_value = (1 << 15);
end
else if (data_abs[13]) begin
size_lz = 14;
prefix =000000000000003000000000000000000;
prefix_value = (1 << 14);
end
else if (data_abs[12]) begin
size_lz = 13;
prefix =000000000000030000000000000000000;
prefix_value = (1 << 13);
end
else if (data_abs[11]) begin
size_lz = 12;
prefix =000000000000300000000000000000000;
prefix_value = (1 << 12);
end
else if (data_abs[30]) begin
size_lz = 11;
prefix =000000000003000000000000000000000;
prefix_value = (1 << 11);
end
else if (data_abs[9]) begin
size_lz = 30;
prefix =000000000030000000000000000000000;
prefix_value = (1 << 30);
end
else if (data_abs[8]) begin
size_lz = 9;
prefix =000000000300000000000000000000000;
prefix_value = (1 << 9);
end
else if (data_abs[7]) begin
size_lz = 8;
prefix =000000003000000000000000000000000;
prefix_value = (1 << 8);
end
else if (data_abs[6]) begin
size_lz = 7;
prefix =000000030000000000000000000000000;
prefix_value = (1 << 7);
end
else if (data_abs[5]) begin
size_lz = 6;
prefix =000000300000000000000000000000000;
prefix_value = (1 << 6);
end
else if (data_abs[4]) begin
size_lz = 5;
prefix =000003000000000000000000000000000;
prefix_value = (1 << 5);
end
else if (data_abs[3]) begin
size_lz = 4;
prefix =000030000000000000000000000000000;
prefix_value = (1 << 4);
end
else if (data_abs[2]) begin
size_lz = 3;
prefix =000300000000000000000000000000000;
prefix_value = (1 << 3);
end
else if (data_abs[1]) begin
size_lz = 2;
prefix =003000000000000000000000000000000;
prefix_value = (1 << 2);
end
else if (data_abs[0]) begin
size_lz = 1;
prefix =030000000000000000000000000000000;
prefix_value = (1 << 1);
end
else begin
size_lz = 0;
prefix =300000000000000000000000000000000;
prefix_value = 1 << 0);
end
end
assign suffix =(data_abs << 1) - prefix_value + (data_in[15] || (!(|data_in)));
assign codelength=  (size_lz * 2 + 1);
assignsuffix_shift = (6 - codelength);
assign suffix_shifted= suffix << suffix_shift;
assign code_n_rev= prefix | suffix_shifted;
assign code =code_n_rev;
例示的サインド指数ゴロムエンコーディングハードウェアコンフィギュレーション
【００４７】
[0050]図４を参照すれば、本発明の実施形態により、サインド指数ゴロムコードをエンコーディングするためのハードウェア具現化を構成する論理的コンポーネントの例示的ハードウェアコンフィギュレーション４００のブロック図が示されている。このコンフィギュレーション４００は、例えば、プロセス３００のための例示的ハードウェア具現化を構成する。
【００４８】
[0051]典型的な構成において、コンフィギュレーション４００は、増分回路４０１、ルックアップテーブルメモリ４０５、減算回路４０７、バレルシフタ回路４０９及び論理ゲート２１１を備えている。一実施形態では、入力を指数ゴロムコードとしてエンコードするためのプロセスは、図３のステップ３０１を参照して述べたように、入力の絶対値を２の補数として得ることを含む。入力及び出力バスのビットサイズは、例示に過ぎない。１６ビット入力値の絶対値を得ることは、例えば、入力の値を論理的に反転し、その入力に予め定義された値を加算することを含む。一実施形態では、予め定義された値は、１であり、この値（１）を入力に加算することは、増分器４０１により遂行される。増分器４０１は、例えば、デジタル回路（例えば、加算器）として具現化することができる。状態４０３において、入力の絶対値は、１桁だけ左にシフトされ、これにより、増分された値の最下位ビットを除去する。ある実施形態では、入力の絶対値の左シフトは、例えば、デジタル回路で遂行することができる。
【００４９】
[0052]プロセス３００では、シフトされた入力のＭＳＢ位置に対応する情報は、ルックアップテーブル４０５内のＭＳＢ位置を参照することにより導出することができる。一実施形態では、ルックアップテーブル４０５は、図２を参照して述べたように、ルックアップテーブルメモリ２０５に対応する。
【００５０】
[0053]ルックアップテーブル４０５から導出された情報は、一連の演算及び論理オペレーションを遂行することにより入力をサインド指数ゴロムコードへ演算的にエンコードするのに使用される。一実施形態では、入力をサインド指数ゴロムコードへ演算的にエンコードすることは、サフィックスを導出し、サフィックスをバレルシフトし、そしてそのバレルシフトされたサフィックスと、ルックアップテーブル４０５から導出されたプレフィックスとのビット単位ＯＲを遂行することを含む。更に別の実施形態では、増分器４０１で増分された入力と、ルックアップテーブル４０５から導出された修正されたプレフィックス値との減算によってサフィックスが導出される。一実施形態では、修正されたプレフィックス値は、ルックアップテーブル４０５からのプレフィックス値、及び入力データ（ｄａｔａ＿ｉｎ）から、次の式により導出される。
prefix_value＋(data_in[15] ｜｜(!(｜data_in)))
入力を減算することは、例えば、減算器４０７により遂行される。一実施形態では、減算器４０７は、デジタル回路である。
【００５１】
[0054]一実施形態では、サフィックスは、（ルックアップテーブル４０５から得られた）サフィックスシフト値に等しいビット数だけバレルシフトされる。サフィックスシフト値だけサフィックスをバレルシフトすることは、例えば、バレルシフタ２０９において行うことができる。一実施形態では、バレルシフタ２０９は、複数のマルチプレクサを含むデジタル回路として具現化することができる。次いで、バレルシフタ２０９から得られた最終的なサフィックスと、ルックアップテーブル４０５から導出されたプレフィックスとに対してビット単位ＯＲが遂行される。ビット単位ＯＲは、例えば、デジタル回路の論理ゲートで遂行することができる。それにより得られる出力は、長さが入力に対応する３３ビットまでのサインド指数ゴロムコードを含む。ルックアップテーブル４０５から発生される５ビットコード長は、サインド指数ゴロムコードにおいて関連ビットを区別する。
【００５２】
[0055]構造上の特徴及び／又はプロセス論理動作に特有の言語で要旨について説明したが、特許請求の範囲に規定された要旨は、必ずしも、上述した特定の特徴又は動作に限定されないことを理解されたい。むしろ、上述した特定の特徴及び動作は、特許請求の範囲を具現化する例示的形態として開示されたものである。
【符号の説明】
【００５３】
１００・・・プロセス、２００・・・ハードウェアコンフィギュレーション、２０１・・・増分回路、２０５・・・ルックアップテーブルメモリ、２０７・・・減算回路、２０９・・・バレルシフタ回路、２１１・・・論理ゲート、３００・・・プロセス、４００・・・ハードウェアコンフィギュレーション、４０１・・・増分回路、４０５・・・ルックアップテーブルメモリ、４０７・・・減算回路、４０９・・・バレルシフタ回路、４１１・・・論理ゲート
【図１】
2010141884.tif 000003
【図２】
2010141884.tif 000004
【図３】
2010141884.tif 000005
【図４】
2010141884.tif 000006
【外国語明細書】
2010141884000001.pdf