JPH1075181A - ハフマン・デコーダ - Google Patents

Abstract

(57)【要約】 【課題】 ハフマン符号化により圧縮されたデータの伸
張に適したデコーダ。 【解決手段】 データ・ストリーム中の係数のランレン
グス、係数のサイズ、及び係数の長さと符号語の長さの
和が得られるようにし、この値により、次の符号語に着
手するためにレジスタ内のビットをシフトするシフト量
を求められる。これにより、新しいデータを受け取りな
がら復号動作を行うようにして、デコーダはハフマン符
号化ビット・ストリームを高速に復号することができ
る。また、ＲＬＬ検出器２０３及びヘッダ/マーカ検出
器２０５が、デコーダ２０１でのデータ処理を同じクロ
ック・サイクルで模倣することによって、バイト境界お
よびヘッダ／マーカが適切に追従するので、１クロック
・サイクルで復号することができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は一般に、ハフマン符
号化を使用するデータ圧縮および伸張に関し、特に静止
画像（JPEG）への応用例およびビデオ画像（MPEG）への
応用例でのハフマン符号化に関し、具体的には高ビット
伝送速度ハフマン復号に関する。

【０００２】

【従来の技術】伝送や長期間にわたる記憶を行う場合の
データのコンパクト化はデータ圧縮とも呼ばれ、可変長
符号化技法を使用して行うことができる。固定長のデー
タ・ビット・ストリングが可変長のビット・ストリング
として符号化され、より頻繁に発生するデータ・ビット
・ストリングまたは文字がより短い長さの符号語で表さ
れ、それによって伝送時間が短縮され、あるいはその記
憶機構に対する要件が低減される。データ・プロセッサ
では、圧縮済みデータをこの圧縮形で使用することはで
きない。したがってこのデータは、固定長形式に復号さ
れる。これはデータ伸張とも呼ばれる。

【０００３】冗長度が最小の可変長符号の一形態は、
「A Method for the Construction ofMinimum Redundan
cy Codes」（Proceedings of the IEEE、IRE、第40(9)
巻、1098ページないし1101ページ、1952年）と題する論
文でD.A. Huffmanによって提案されている。ハフマン符
号化および復号では、発生率の高い記号はより短いビッ
ト長符号を有する。ハフマン符号化は、簡単な順方向の
２分木構造と最適符号化（平均符号長が最小となる符号
化）手順を備えているので、広く使用されている。

【０００４】ハフマン符号を復号する様々な技法が開発
されている。基本的にハフマン符号のストリームの復号
は、２分デコーダ木（binary decoder tree)に従うこと
によって行われる。一般に、このようなデータ伸張エン
ジンは、順次論理を使用して一度に１ビットまたは２ビ
ットずつハフマン符号を反復的に復号するか、あるいは
組合せ論理を使用して符号全体を１クロック・サイクル
で並行して復号する。

【０００５】ディジタル・ハード・コピー再生の分野で
は、データ圧縮にハフマン符号を使用する規格が採用さ
れている。この規格はANSI X3L2.8委員会のJoint Pictu
re Expert Group（JPEG）によって提案され、「JPEG Di
gital Compression and Coding of Continuous-tone St
ill Images」（Draft ISO 10918、1991年）として発表
された。同様な規格がMoving Picture Expert Group
（「MPEG」）によって提案され、ISO/IEC JTC1 CD 1117
2「Coding of Moving Pictures and AssociatedAudio f
or Digital Storage Media Up to 1.5 Mbits/second」
（InternationalOrganization for Standardization、1
992年（「MPEG-1」とも呼ばれる））として発表され
た。

【０００６】フル・カラー・ハード・コピー・プリンタ
や、ファックスでのカラー画像伝送や、ディジタル・ビ
デオ伝送などの高ビット伝送速度応用例では、適当なハ
フマン・デコーダの設計が重大である。ビット・ストリ
ームを再位置合わせするために必要なフィードバック・
ループが必要であるため、パイプラインとそれと並列し
て行う復号化は共に困難なものになる。可変長符号は、
プログラム可能な符号参照テーブルを使用して固定長の
最初のデータストリングに復号しなければならない。こ
の操作を好ましくは１サイクルで完了しておかないかぎ
り、次の符号語を復号することはできない。このタスク
は、各連続符号語の可変長の性質により複雑になってし
まう。その上、高クロック周波数で動作するには、クリ
ティカル・パスにおけるロジックの数を最小限に抑えな
ければならない。

【０００７】JPEG／MPEGデータの特定の応用例では、実
際のハフマン復号操作だけでなく他の複雑な問題があ
る。ハフマン符号語は、JPEG規格では最大で１６ビット
に限られ、「ランレングス制限（RLL: run-length limi
ted）／係数」データ対を表すために使用される。RLL
は、現係数の直前の連続する零係数の数を表し、実際の
係数データを符号化するために使用されるビットの数を
表すサイズを有する。したがって、図１に示したよう
に、各ハフマン可変長符号語１０３の後に可変長符号化
係数値１０５が続き、この場合、ハフマン符号語１０３
は、係数値を符号化するためにいくつのビットが使用さ
れるかを示す。たとえば、表されるデータは、符号付き
１２ビット係数値、たとえば８ビット×８ビットの画素
の色変換のための、赤、または緑、または青（「ＲＧ
Ｂ」）の色刺激値ベクトル、あるいはシアン色、マゼン
タ色、黄色、黒（「ＣＭＹＫ」）の色刺激値ベクトルで
あってもよい。各符号語は、画像中の画素から変換され
た１つの係数である（ＲＧＢまたはその他の三色システ
ムに関する三次元構造の基本は、「Principles of Colo
rTechnology」（BillmeyerおよびSaltzman著、John Wil
ey & Sons発行、NY、1981年（第２版））、「Color Sci
ence: Concepts and Methods, Quantitative Dataand F
ormulae」（WyszeckiおよびStiles著、John Wiley & So
ns発行、NY、1982年（第２版））において論じられてい
る。しかし、当業者が本発明を理解するうえでこれ以上
の説明は不要である）。

【０００８】場合によってはさらに問題を複雑にするこ
ととして、圧縮済みJPEG／MPEGデータ・ストリームには
一般に、ヘッダおよび制御マーカ１０７が埋め込まれ
る。このようなマーカは、予約データ・パターンであ
り、すなわちデータ・ストリーム中のバイト境界に埋め
込まれた、１と０からなる特定の予約ストリングであ
る。この例には、START OF SCANマーカ、START OF IMAG
Eマーカ、END OF IMAGEマーカ、RESTARTマーカがある。
したがって、JPEGハフマン・デコーダは、マーカの存在
を検出し、そのマーカとともに、そのマーカをバイト境
界に整列させるために付加されたパディング・ビットも
削除しなければならない。

【０００９】2¹⁶個のメモリ・ロケーションからなる参
照テーブルを使用する標準JPEGハフマン・デコーダで
は、受け取った特定の符号語のランおよびサイズを与え
る参照テーブルのアドレスとして、最大１６ビットが使
用される。しかし、これには大型で低速のメモリが必要
である。言い換えれば、ハフマン符号の位置および長さ
を求め、その後、参照テーブルまたは復号操作によっ
て、その後に続く係数のランレングスおよびサイズを求
め、その後、そのデータを抽出し、それに続いてシフト
を行い、次の符号語を見つけてこの操作を繰り返さなけ
ればならない。

【００１０】アドレス空間を減少させるために、Tong等
は米国特許第5,208,593号において開示されているよう
に、符号語中の一連の先頭の１を使用してより小型のメ
モリにインデックスさせる方法を開発した。しかし、ビ
ットを付加すると圧縮効率に悪影響を受けるので、Rett
er等は圧縮効率を高めるために、米国特許第5,379,070
号に開示された並列処理方法を開発した。しかしこの方
法では、高価なハードウェア構成要素が付加される。

【００１１】

【発明が解決しようとする課題】したがって、図１に示
したビット・データ・ストリームのような、JPEG／MPEG
方式で圧縮されたデータの伸張に適した高ビット伝送速
度ハフマン復号方法およびアーキテクチャが必要であ
る。

【００１２】

【課題を解決するための手段】本発明は、その基本態様
において、最大長「Ｑ」の符号語−係数対を有するハフ
マン符号化データ・ストリームを復号する方法を提供す
る。基本的にこの方法は、データ容量が少なくともＱの
２倍であるデータ・レジスタに、係数とハフマン符号語
の第１の対を備える、いくつかのビットを有する第１の
入力データ・セットを記憶するステップと、ストリーム
の第２の係数−ハフマン符号語対を備える次の逐次入力
データ・セットをシフト・レジスタにおいて受け取るス
テップと、前記次の逐次入力データ・セットを第１の入
力データ・セット内のビットの数だけ右シフトするステ
ップと、前記第１の入力データ・セットと前記次の逐次
入力データ・セットの論理和を実行し、結果をデータ・
レジスタに入れるステップと、データ・レジスタの
「Ｎ」個の上位ビットを復号済み係数値として抽出し、
データ・レジスタの次の上位ビット「Ｍ」個をハフマン
符号語として抽出するステップとを含む。

【００１３】本発明の他の態様では、JPEG標準データ・
ストリームを復号するハフマン復号化装置が提供され
る。該JPEG標準データ・ストリームは、ハフマン符号語
−係数対データ・フォーマットの最大１６ビットのハフ
マン符号語を有しており、さらにバイト境界情報符号と
ヘッダ／マーカ情報符号とを含んでいる。この装置は、
入力バスと、少なくとも２つの符号語−係数対を入力バ
スから受け取るために入力バスに接続された右シフト・
レジスタと、右シフト・レジスタから右シフト・レジス
タ・データ出力を受け取るためのビットＯＲ演算機構
と、前記ビットＯＲ演算機構から出力データを受け取る
ために前記ビットＯＲ演算機構に接続された入力データ
・レジスタと、前記入力データ・レジスタから出力デー
タを受け取るために前記入力データ・レジスタに接続さ
れた左シフト・レジスタと、係数のランレングスと、可
変長符号化係数の長さと、符号語の長さと符号化係数の
長さの和が得られるような符号語−係数対から復号され
る現符号語および係数を、左シフト・レジスタから抽出
する機構と、前記入力データ・レジスタを前記和の量だ
け左シフトさせ、復号される次の現符号語および係数を
得るためのフィードバック機構とを含む。

【００１４】本発明の利点は、復号クリティカル・パス
で必要とされるロジックの数が最小限に抑えられること
である。

【００１５】本発明の他の利点は、１クロック・サイク
ルごとに１つの符号−係数対が復号されることである。

【００１６】本発明の他の利点は、商用の実施態様のラ
ンダム・アクセス・メモリに対する要件が受け入れられ
るものであることである。

【００１７】本発明の他の利点は、JPEG規格およびMPEG
規格に適合する必要に応じて、制御マーカが適切に検出
され処理されることである。

【００１８】本発明の他の目的、特徴、利点は、下記の
説明および添付の図面を検討したときに明らかになろ
う。図面全体にわたって同じ参照符号のものは同じ構成
要素である。

【００１９】

【実施例】次に、本発明を実施するために本発明者によ
って現在企図されている最良の態様を示す本発明の特定
の実施形態を詳細に参照する。必要に応じて代替実施形
態も簡単に説明する。ここでは、JPEG規格に適用した場
合の例示的な実施形態を与える。しかし、当業者には、
本発明をMPEGまたはその他のデータ復号にも適用できる
ことが認識されよう。この例示的な実施態様を使用する
ことによって特許請求の範囲に記載された本発明の範囲
が制限されるようなことは企図しておらず、またそのよ
うな制限を暗示するわけでもない。

【００２０】本発明の特定の例示的な実施形態を図２に
示す。

【００２１】〔動作の概要〕概略的に言えば、圧縮済み
JPEGデータ・ストリームがバス２００を介して３２ビッ
ト・ストリング符号、すなわち単一の最大長ハフマン符
号語−係数対として係数デコーダ２０１に入力される。
バイト境界情報、すなわち４ビット・ストリング語が、
バス２０２を介してRLL検出器２０３に入力される。マ
ーカ検出器２０５で復号されるヘッダ／マーカ符号４ビ
ット・ストリング語がバス２０４を介して入力される。
入力データストリングに対して入力シフト・レジスタは
概して１つだけ使用される。

【００２２】１つの画像情報の入力の始めに、まず２つ
の３２ビットの入力語がロードされる。シフトすべきビ
ット数は始めに零にクリアされ、したがって第１のサイ
クルではシフト動作は実行されない。その後は各クロッ
ク・サイクルごとに、ひとつ前のハフマン符号語−係数
対中のビットの数だけデータがシフトされる。

【００２３】次いで、復号にＯＲ演算が使用される。こ
れは、データ・サブセットにおいて次の符号語がどこか
ら始まるかを指し示すことを不要にし、それによりクリ
ティカル・パスを短縮するので比較的高速な演算であ
る。しかし、既存の入力データを用いたシフト演算およ
びＯＲ演算が実行されるときはいつでもバイト境界情報
の位置が失われるので、このバイト境界情報をどのよう
に保持するかが問題になる。RESTARTやEND_OF_IMAGE JP
EGマーカなどのデータ・ストリーム・ヘッダ／マーカに
出会ったときにバイト境界情報が重大であることは明ら
かである。したがって、これは並列RLL検出器２０２お
よびマーカ検出器２０４を使った実施態様で対処され
る。

【００２４】〔入力データ−ローディング〕図３および
図３を参照すると、バイト境界情報とデータ・ストリー
ム・マーカ情報を的確な記録でもって維持する際の問題
の解決策を含む、本発明による高速ハフマン・デコーダ
３００の特定の実施形態が示されている。ここでは、当
業者に認識されるであろう標準的なロジックが示されて
いる。ハフマン復号技術自体は、ハフマン符号語中の先
頭の１の数に基づいて参照テーブルにアクセスする方式
を使用する。この復号方法は、米国特許第4,899,149号
（Kahan）および米国特許第5,208,593号（Tong）におい
て開示されている。したがって、下記の説明では、本明
細書の特許請求の範囲に記載された本発明の説明に焦点
を当てる。

【００２５】バス２００上で受け取った３２ビット入力
データ語は、データ・レジスタ「Ｑ」３０１、すなわち
現在復号中の入力データ・ストリームのセグメント用の
７５ビット・データ・レジスタにロードされる。７５ビ
ットが必要であるのは、シフト後に一つ前の符号語−係
数対から得た符号なし係数（ここでの「符号」は正負を
表すコード（sign）のことを表す）を保持する最も左側
の１１ビットと、現入力データ・ストリームから得た２
つのフルの３２ビットを必要とするからである。「次
の」ハフマン符号語を復号する場合、Ｑ＿レジスタ３０
１内のデータ・ストリームから符号語を抽出する必要が
ある。JPEG規格では、この符号語の長さは最大１６ビッ
トでよい。前の符号語−係数対の長さは最大２７ビット
でよい（すなわち、符号語用の１６ビットおよび符号化
係数用の１１ビット）。したがって、所与のサイクルで
は、Ｑ＿レジスタ３０１内で最小で４３ビット（１６ビ
ット＋２７ビット）を有する必要がある。４３ビット
は、３２ビット入力データ語長よりも長いので、２つの
３２ビット語をキューにした、高速実施態様として決定
されている。

【００２６】〔ヘッダ／マーカ／バイト境界情報ビット
−ロード〕入力データ・ストリーム中の３２ビット語間
のヘッダ／マーカおよびバイト境界情報は、当技術分野
で知られているように標準的に検出され、それぞれ、バ
ス２０４、２０２上に４ビット語として分離される。次
いで、RLL検出器２０３およびヘッダ／マーカ検出器２
０５はそれぞれ、「ゼロ挿入」ハードウェア３０３、３
０５によって、４つのビットの各ビット間に７つの0
（ゼロ）を挿入することによって、それぞれの４ビット
入力語を３２ビットに拡張させる。

【００２７】例示的な実施形態では、圧縮JPEGデータ・
ストリームのバイト境界に、JPEG規格で定義されたREST
ARTマーカおよびEND_OF_IMAGE（「EOI」）マーカが挿入
される。これらのJPEGマーカはマーカ検出器２０５によ
って検出され、３２ビット入力語中のどのバイト境界で
マーカが検出されたかを示す４ビットが出力される。こ
のマーカ自体は、入力データ・ストリームから除去され
る。この４ビット・マーカＩＤは、４つのビットの各ビ
ット間に７つの零を挿入することによって、入力データ
語に合致するようにフルの３２ビットに拡張される。し
たがって、マーカ識別子ビットのビット位置は、マーカ
が検出され削除された入力データ語中のその位置と正確
に一致する。

【００２８】同様に拡張された３２ビットRLL語がレジ
スタＲ３０７にロードされる。拡張された３２ビットRE
STARTマーカ語またはＥＯＩマーカ語はレジスタ「Ｅ」
３０９にロードされる。次に、バイト境界位置およびヘ
ッダ・マーカ位置が、最初に入力データとして符号化さ
れたときと同じ順序で保存されるように、Ｑ＿レジスタ
３０１、Ｒ＿レジスタ３０７、Ｅ＿レジスタ３０９を同
期的にシフトすることができる。すなわち、下記で説明
するその後のシフト演算が行われたときに、Ｑ＿レジス
タ３０１内の入力データ・ストリーム、Ｒ＿レジスタ３
０７内のRLL語、Ｅ＿レジスタ３０９内のRESTARTまたは
ＥＯＩマーカ語がまとめてシフトされ、互いに同期した
ままになる。

【００２９】〔入力データ−復号〕バス２００から得た
入力データ・ストリームの「次の」３２ビット・データ
語が、「現在の」左シフト演算が処理された後に７５ビ
ット・データ・レジスタ３０１に存在しているデータ・
ビットの数に等しい量だけ右シフトされる（３１３）。
これは、Ｑ＿レジスタ３０１へのビットＯＲ演算（３１
５）に備えて行われる。右シフト３１３演算とビットＯ
Ｒ演算（３１５）は、現在Ｑ＿レジスタ３０１内に存在
するデータ・ビットのすぐ右側の適切な位置に新しい３
２ビット・データ語をロードするという効果を有する。

【００３０】次いで、その「次の」語にビットＯＲ演算
３１５が施され、結果がＱ＿レジスタ３０１に入れられ
る。

【００３１】Ｑ＿レジスタ３０１を占めていた７５ビッ
トが、レジスタ３１７内で、第１の符号語と係数の和の
サイズだけ左シフトされる。

【００３２】次いで、左シフトされたデータ・ストリー
ム中の最も左の２７ビットが調べられる。この２７ビッ
トのうちで、レジスタ３１９中の最も左側の１１ビット
は、第１の符号語−係数対の係数である。レジスタの最
も左側のビットがビット７４であり、最も右側のビット
がビット０であると仮定すると、ビット６３〜４８は、
JPEG規格当たりの長さが最大１６ビットまで許される可
変長ハフマン符号を含んでいる。

【００３３】参照テーブルを使用してハフマン符号を復
号すると、ハフマン符号語と符号なし係数の組み合わせ
の長さが生成される。次のクロック・サイクルでは、Ｑ
＿レジスタ３０１がこの長さ分だけ左シフトされる。

【００３４】左シフトの後、Ｑ＿レジスタ３０１の最も
左側の１１ビットは、前の符号語−係数部から得た可変
長の符号なし係数を含む。可変長の符号なし係数は、０
〜１１ビットの任意の長さであってよく、係数サイズＡ
レジスタ３２７はこの係数の長さを含む。係数復号装置
３３１は、符号なし係数および係数長を取り出し、CODE
_DECODE_HUFFMAN装置３３３への１２ビット符号付き数
量出力として、復元済み係数値を生成する。

【００３５】係数の長さが１１ビットよりも短い場合、
情報がＱ＿レジスタ３０１の最も左側の１１ビットのう
ちの最も右側のビットに含まれることに留意されたい。
したがって、標準のブール論理を介して、符号化係数お
よび係数サイズ・データを使用してこの符号化係数が１
２ビット符号付き数量３３１として復元され、この数量
３３１がJPEGデコーダ（図示せず）の次の段に出力され
る（３３３）。

【００３６】最も右側の１６ビットは現ハフマン符号語
であり、アドレス生成装置３２１へ送られ、ハフマン参
照テーブル３２３においてアクセスすべきアドレスが算
出される。参照テーブル３２３は次いで、ゼロ・ランレ
ングス３２５（復号済みデータに再挿入しなければなら
ない係数に挿入されているゼロの数）および係数サイズ
・データ３２７と、次の左シフト量３２９に等しい現符
号語−係数対の全体的な長さ、すなわち、次の検査サイ
クルで左シフト・レジスタ３１７をシフトすべき位置の
数を与える。

【００３７】参照テーブルは、入力データ・ストリーム
からハフマン符号語を復号し、下記の３つの値を与え
る。 （１）ゼロ係数のランレングス （２）可変長符号化係数の長さ （３）ハフマン符号語の長さと符号化係数の長さの和 ただちに、最後の値を使用してＱ＿レジスタ３０１が左
シフトされる。可変長符号化係数の長さを使用して、係
数がその１２ビット符号付き値に復元される。パイプラ
イン式実施態様では、CODE_DECODE_HUFFMANレジスタ３
３３からの正しい係数に合致するようにランレングス情
報と係数サイズ情報を遅延させなければならないので、
ランレングス情報は、ランレングスＡレジスタ３２５お
よびランレングスＢレジスタ３２６によって遅延される
ランレングス・デコーダ３６３に直接出力される。

【００３８】入力データが可変長のものなので、Ｑ＿レ
ジスタ３０１のデータ、Ｒ＿レジスタ３０７のバイト境
界情報、およびＥ＿レジスタ３０９のヘッダ／マーカの
それぞれにいくつの有効ビットが存在するかを追跡する
ために、有効ビット・レジスタ３１１を使用する。レジ
スタ３０１、３０７、３０９からビットがシフトされる
につれて、各サイクルで参照テーブルから与えられるシ
フトの値を有効ビット・レジスタのカウントから減じな
ければならない。

【００３９】新しい３２ビット語の入力データがロード
されると、３１２によって有効ビット・カウントに３２
が加えられる。ロード制御機構３１４は、Ｑ＿レジスタ
３０１内の有効データ・ビットの数と、次のクロック・
サイクルで適用される左シフトの量をモニタする。ロー
ド制御機構３１４は、Ｑ＿レジスタ３０１内の有効デー
タ・ビットの数が４３よりも小さくなると判定すると、
Ｑ＿レジスタに新しいデータ語をロードすることを求め
る信号を発する（すなわち、有効データ・ビットの数か
らシフトの量を減じた値が４３よりも小さい場合は、新
しいデータ語をロードする）。

【００４０】〔ヘッダ／マーカ／バイト境界情報ビット
−復号〕次に、前の説明から、拡張された３２ビットの
ヘッダ／マーカおよびバイト境界語がそれぞれ、Ｅ＿レ
ジスタ３０９およびＲ＿レジスタ３０７に作成されたこ
とを想起されたい。これらの３２ビットはそれぞれ、Ｑ
＿レジスタ３０１内の関連する入力データ語と全く同様
にかつ同じクロック・サイクルで、シフト・レジスタ３
４５、３４３によって右シフトされ、ビットＯＲ演算回
路３４７、３４９によってビットＯＲ演算される。次い
で３１７で、データが左シフトされると、ヘッダ／制御
マーカおよびバイト境界語がそれぞれのレジスタ３５
１、３５３内で同時に左シフトされ、これらの相対位置
が維持される。これらのレジスタ３５１、３５３の最も
左側のビットを調べることによって、Ｅ＿レジスタ３０
９およびＲ＿レジスタ３０７に挿入されたゼロを検出し
（３５５）、データ・ストリームから左シフトして抜き
出す（３５７）ことができ、ヘッダ／マーカ３６５およ
び境界語３６３を出力することができる。

【００４１】〔実施態様〕なお、本発明の実施態様の例
を以下に示す。

【００４２】〔実施態様１〕 ハフマン符号語−係数対
データ・フォーマット（１０３、１０５）の最大１６ビ
ットのハフマン符号語（１０３）とバイト境界情報符号
（１０７）とヘッダ／マーカ情報符号（１０７）とを含
むJPEG標準データ・ストリーム（１０３、１０５、１０
７）を復号するハフマン・デコーダであって、入力バス
（２００）と、少なくとも２つの符号語−係数対を入力
バスから受け取るために入力バスに接続された右シフト
・レジスタ（３１３）と、右シフト・レジスタから出力
データを受け取るビットＯＲ演算手段（３１５）と、前
記ビットＯＲ演算手段から出力データを受け取るために
前記ビットＯＲ演算手段に接続された入力データ・レジ
スタ（３０１）と、前記入力データ・レジスタから出力
データを受け取るために前記入力データ・レジスタに接
続された左シフト・レジスタ（３１７）と、係数のラン
レングスや、可変長符号化係数の長さや、符号語の長さ
と符号化係数の長さの和を得られるように、符号語−係
数対から復号すべき現符号語および係数を左シフト・レ
ジスタから抽出する手段（３３１、３３３、３６３）
と、前記入力データ・レジスタを前記和の量だけ左シフ
トさせ、復号すべき次の現符号語および係数を得るフィ
ードバック手段とを備えることを特徴とするハフマン・
デコーダ。

【００４３】〔実施態様２〕 バイト境界情報符号を符
号語−係数対と同じビット長になるまでパディングする
手段（３０３）を含む、バイト境界情報符号を受け取り
追跡する手段（２０３）と、符号語−係数対と同期させ
てバイト境界情報符号をシフトさせる手段（３５３）と
をさらに含むことを特徴とする、実施態様１に記載のデ
コーダ。

【００４４】〔実施態様３〕 ヘッダ／マーカ情報符号
を符号語−係数対と同じビット長になるまでパディング
する手段（３０５）を含む、ヘッダ／マーカ情報符号を
受け取り追跡する手段（２０５）と、符号語−係数対と
同期的にヘッダ／マーカ情報符号をシフトさせる手段
（３５１）とをさらに含むことを特徴とする、実施態様
１または実施態様２に記載のデコーダ。

【００４５】〔実施態様４〕 前記入力レジスタは、デ
ータ容量が入力バスのビット幅の少なくとも２倍である
レジスタを備えることを特徴とする、実施態様１ないし
実施態様３のいずれかに記載のデコーダ。

【００４６】〔実施態様５〕 最大長「Ｑ」の符号語−
係数対を有する符号化データ・ストリームを復号する方
法であって、データ容量が少なくともＱの２倍であるデ
ータ・レジスタに、係数とハフマン符号語の第１の対を
備えるいくつかのビットを有する第１の入力データ・セ
ットを記憶するステップと、ストリームの第２の係数−
ハフマン符号語対を備える次の逐次入力データ・セット
をシフト・レジスタで受け取るステップと、前記次の逐
次入力データ・セットを前記第１のデータ・セット内の
ビットの数だけ右シフトするステップと、前記第１の入
力データ・セットと前記次の逐次入力データ・セットの
論理和を実行し、結果をデータ・レジスタに入れるステ
ップと、データ・レジスタの最上位ビットＮ個を復号済
み係数値として抽出し、データ・レジスタの次の上位ビ
ットＭ個を符号語として抽出するステップとを含むこと
を特徴とする方法。

【００４７】〔実施態様６〕 ストリームが終了するま
で、データ・ストリームの次の各逐次入力データ・セッ
トごとに実施態様５のステップを繰り返すステップをさ
らに備えることを特徴とする、実施態様５に記載の方
法。

【００４８】〔実施態様７〕 関連するデータ・セット
と共にデータ・ストリームに埋め込まれたバイト境界情
報を受け取るステップと、バイト境界情報が、入力デー
タ・セット長に等しいビット長を有するように、バイト
境界情報の各ビット間に零のストリングをパディングす
るステップと、関連するデータ・セットと同時にバイト
境界情報を右シフトさせるステップと、各零ストリング
を抽出し、バイト境界情報を復号済みデータ・セットに
整列するように再形成するステップとをさらに含むこと
を特徴とする、実施態様５または実施態様６に記載の方
法。

【００４９】〔実施態様８〕 データ・ストリームに埋
め込まれた制御マーカ情報を関連するデータ・セットと
共に受け取るステップと、前記制御マーカ情報が入力デ
ータ・セット長に等しいビット長を有するように、前記
制御マーカ情報の各ビット間に零のストリングをパディ
ングするステップと、前記制御マーカ情報を、関連する
データ・セットと同時に右シフトさせるステップと、各
零ストリングを抽出し、前記制御マーカ情報を復号済み
データ・セットに整列するように再形成するステップと
をさらに含むことを特徴とする、実施態様５ないし実施
態様７のいずれか一項に記載の方法。

【００５０】〔実施態様９〕 各クロック・サイクル
で、データが前の符号語−係数対中のビットの総数だけ
シフトされることを特徴とする、実施態様５ないし実施
態様８のいずれか一項に記載の方法。

【００５１】

【発明の効果】要するに本発明は、ラン、係数のサイ
ズ、及び係数と符号語長の和を符号化する。この値は、
次の符号語に着手するためのシフトの量を示すシフト量
として与えられる。これは、新しいデータを受け取りな
がら復号動作を行うようにして、JPEGハフマン符号化ビ
ット・ストリームを高速に復号する方法を与える。同時
に、回路２０３、２０５がハフマン・デコーダ２０１で
のデータ処理を模倣することによってバイト境界および
ヘッダ／マーカが適切に追跡される。ＥＯＩマーカが検
出された後、デコーダは受け取ったデータがなくなるま
で処理を継続する。

【００５２】また、上記したように本発明は復号にＯＲ
演算を使用しており、これによって入力における次の符
号語がデータ・サブセット中のどこから始まるのかを指
し示すことを不要にしている。従って、クリティカル・
パスを短縮することができるので、比較的高速な演算を
実現することができる。

【００５３】本発明の好ましい実施形態の上記の説明
は、例示および説明のために与えたものである。上記の
説明は、網羅的なものでも、あるいは開示した厳密な形
態に本発明を制限するものでもない。当業者には多数の
修正形態および変形形態が明らかになろう。同様に、説
明したプロセス・ステップを他のステップと相互交換し
て同じ結果を達成することができる。実施形態は、本発
明の原則および最適な態様の実用例を最もうまく説明
し、それによって当業者が本発明を様々な実施形態に関
して、かつ企図される特定の用途に適した様々な修正形
態と共に理解することができるように選択され記載され
ている。本発明の範囲は、添付の請求の範囲およびその
等価物によって定義されるものである。

【図面の簡単な説明】

【図１】 圧縮JPEGデータ・ストリームの概略図であ
る。

【図２】 本発明によるハフマン・デコーダの概略ブロ
ック図である。

【図３】 図２に示した本発明によるハフマン・デコー
ダの詳細な概略論理図である。

【符号の説明】

２００：バス ２０１：デコーダ ２０２：バス ２０３：ＲＬＬ検出器 ２０４：バス ２０５：ヘッダ／マーカ検出器 ３０３：ゼロ挿入ハードウェア ３０５：ゼロ挿入ハードウェア ３１１：有効ビット・レジスタ ３１３：右シフト・レジスタ ３１４：ロード制御機構 ３１５：ビットＯＲ演算器 ３２１：アドレス生成装置 ３２３：参照テーブル ３５５：ゼロ検出器 ３５７：左シフト・レジスタ

Claims (1)

【特許請求の範囲】
1. 【請求項１】 ハフマン符号語−係数対データ・フォー
   マットの最大１６ビットのハフマン符号語とバイト境界
   情報符号とヘッダ／マーカ情報符号とを含むJPEG標準デ
   ータ・ストリーム復号するハフマン・デコーダであっ
   て、 入力バスと、 少なくとも２つの符号語−係数対を入力バスから受け取
   るために入力バスに接続された右シフト・レジスタと、 右シフト・レジスタから出力データを受け取るビットＯ
   Ｒ演算手段と、 前記ビットＯＲ演算手段から出力データを受け取るため
   に前記ビットＯＲ演算手段に接続された入力データ・レ
   ジスタと、 前記入力データ・レジスタから出力データを受け取るた
   めに前記入力データ・レジスタに接続された左シフト・
   レジスタと、 係数のランレングスや、可変長符号化係数の長さや、符
   号語の長さと符号化係数の長さの和を得られるように、
   符号語−係数対から復号すべき現符号語および係数を左
   シフト・レジスタから抽出する手段と、 前記入力データ・レジスタを前記和の量だけ左シフトさ
   せ、復号すべき次の現符号語および係数を得るフィード
   バック手段とを備えることを特徴とするハフマン・デコ
   ーダ。