(57)【特許請求の範囲】
【請求項１】
記号をハフマン符号化するハフマン符号化法であって、
１つのテーブルにおける所定長の符号語の最初の出現に対するシード値を定義するステップと、
１つの符号語の長さを格納するステップと、
前記長さおよび前記符号語のビット数が所定ビット数以下の場合、前記長さおよび前記符号語を第１の形式で格納するステップと、
前記長さおよび前記符号語が前記所定ビット数を超えるビット数から成る場合、前記シード値への索引、オフセット、および前記符号語を第２の形式で格納するステップと
を備えたハフマン符号化法。
【請求項２】
前記記号がＪＰＥＧ Ｒ／Ｓバイトである、
請求項１に記載のハフマン符号化法。
【請求項３】
前記符号が圧縮された画像データを表す、
請求項１に記載のハフマン符号化法。
【請求項４】
前記圧縮された画像データがＪＰＥＧ画像データである、
請求項３に記載のハフマン符号化法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に様々な用途用の画像圧縮に関し、特に、パックした形式で離散コサイン変換（Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ：ＤＣＴ）  ブロックを格納するための構造と組み合わせた、ＪＰＥＧ（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）標準に従うハフマン（Ｈｕｆｆｍａｎ）エントロピー符号化と復号化に関する。
【０００２】
【従来の技術】
写実画像やグラフィックス画像には、極めて大量のデータが含まれている。したがって、ディジタル・データ・プロセッサで伝送したり処理したりすることができるようにディジタル化する場合、これらの画像を構成している画素を忠実度良く表現するには、数メガ・バイトを必要とする場合が多い。画像圧縮の目的は、記憶のコストや伝送の時間とコストを節約するために、より少ないデータで画像を表現することである。最も効率的な圧縮は、元の画像を正確に再現するのではなく、それを近似することにより達成される。ＪＰＥＧ標準を使うと、様々な用途の間で画像を交換するのが可能になると共に、マルチメディア用途においてディジタル連続色調カラー画像を提供する機能を実現することができる。ＪＰＥＧ標準については、ペネベーカーとミッチェル著『ＪＰＥＧ静止画像データ圧縮標準』（”ＪＰＥＧ  Ｓｔｉｌｌ  Ｉｍａｇｅ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｓｔａｎｄａｒｄ”  ｂｙ  Ｐｅｎｎｅｂａｋｅｒ  ａｎｄ  Ｍｉｔｃｈｅｌｌ，  ｐｕｂｌｉｓｈｅｄ  ｂｙ  Ｖａｎ  Ｎｏｓｔｒａｎｄ，  １９９３．）に詳細に説明されている。
【０００３】
ＪＰＥＧは、２つの空間次元を有し、グレー・スケール（白黒の階調）または色情報を備え、時間に依存しない画像を主として扱う。この点で、ＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）と区別される。ＪＰＥＧ圧縮を使うと、必要な記憶容量を１／１０以下にすることができると共に、プロセスにおけるシステムの応答時間を改善することができる。ＪＰＥＧ標準の主目的は、所定量のデータ、および／または、利用可能な伝送時間もしくは処理時間、に対して最大の画像忠実度を実現することである（「Ａおよび／またはＢ」は「ＡおよびＢ、Ａ、またはＢ」を表わす）。そして、これらデータ圧縮の尺度は、すべて達成されている。データを１／２０以下に圧縮しても（したがって伝送時間または処理時間を１／２０以下に減らしても）平均的な視聴者は気付かない、ということは多くの場合に正しい。
【０００４】
ＪＰＥＧ用の基本構成要素の１つに、離散コサイン変換（ＤＣＴ）  がある。この離散コサイン変換の重要な側面として、非相関係数を生成する点が挙げられる。係数が相関しないということは、圧縮にとって極めて重要である。なぜなら、各係数を独立に扱うことができるので、圧縮効率を損なうことがないからでる。ＤＣＴの別の重要な側面は、視覚的に重み付けられた量子化値を使ってＤＣＴ係数を量子化できる点である。人間の視覚系の応答は空間周波数に強く依存しているので、画像を、各々が特定の空間周波数を有する１組の波形に分解することにより、目で見える画像構造と認識できない画像構造とを分離することが可能になる。したがって、ＤＣＴを使うと、この分解にとって良好な近似を実現することができる。この結果、視聴者が認識する画像の忠実度に重大な影響を与えることなく、データを切り捨てるすなわち省略することが可能になる。
【０００５】
ＪＰＥＧ標準によると、元の白黒画像は、まず、目に見えるエイリアシング（曲線や斜線に生じるギザギザ）が生じないと思われる程度に高い任意の解像度で、８×８の格子中の６４画素から成るブロック群に分解する。（カラー画像は、まず各色素を８×８画素のブロックに別々に分解することにより、圧縮する）。この量子化した画像データに極めて迅速にＤＣＴを施して、６４個のＤＣＴ係数を得ることのできる手法とハードウェアは、公知である。これらのＤＣＴ係数の多くは、零またはほぼ零である。零のＤＣＴ係数は、画像に全く影響しない。ほぼ零のＤＣＴ係数は、比較的目に感じない空間周波数に対応させる場合、無視すなわち省略することができる。人間の目は極めて高い空間周波数と極めて低い空間周波数に対して感度が低いから、ＪＰＥＧ標準の一部として、水平方向と垂直方向の空間周波数の累積値にほぼ対応するいわゆるジグザグ・パターンでＤＣＴ係数を提供すると、重要度の低い空間周波数に対応するＤＣＴ係数をＤＣＴ係数のデータ・ストリームの最後にグループ化するようになる。これにより、多くの場合、これら重要度の低い空間周波数に対応するＤＣＴ係数を１つのグループとして効率的に圧縮することができる。
【０００６】
上述した離散コサイン変換（ＤＣＴ）  と符号化は実務で扱う大部分の画像に対して意味のあるデータ圧縮を実現しているけれども、実際のデータ削減量は保証されておらず、圧縮の程度は最適化されていない。これは、特に各ＤＣＴ係数の表現の精度が等しい場合には、同数のビットを伝送する必要があるからである（ただし、ＪＰＥＧ標準は、１つのテーブルで符号化されている複数の範囲によってＤＣＴ値を量子化するのを許している）。すなわち、ＤＣＴ符号化によって得られる圧縮利得は、主に、ＤＣＴ係数の零値とほぼ零値を処理することにより効率が増大することに由来する。ただし、精度を落とす量子化によっても圧縮を達成することができる。以上の点から、ＪＰＥＧ標準は、エントロピー符号化と呼ばれている第２段階の圧縮と符号化を規定している。
【０００７】
一般に、エントロピー符号化の概念は、なじみのある熱力学の分野におけるエントロピーの概念に類似している。熱力学では、エントロピーとは、物理系における「無秩序」の程度を数量化したものである。情報理論の分野では、エントロピーとは、任意の大きさの１団のデータから成る環境における任意の所定の情報量子（例えば記号）の内容の予測可能性の尺度のことである。この場合、エントロピーは、任意の所定の情報量子（例えば記号）の意味とは無関係である。この概念によって、所定のアルファベット記号に対して行ないうる圧縮の程度の達成可能な下限を決めることができる。より基礎的には、この概念によって、「予測可能の程度が比較的高いデータ（あるいは記号）は、予測可能の程度が低いデータ（あるいは記号）よりも情報量が少ない」という前提と、「予測可能の程度が比較的低いデータ（あるいは記号）は、予測可能の程度が高いデータ（あるいは記号）よりも情報量が多い」という換位命題とに基づいた圧縮手法が得られる（換位命題とは、ある命題の主部と述部の中の語を入れ替えた命題のことである）。したがって、説明のために適切な符号を１つ仮定すると、予測可能の程度が高い（すなわちデータ本体における出現頻度が高いが、情報量は少ない）記号（あるいは値）にはより少ないビット数を割り当てる一方、予測可能の程度が比較的低い記号（あるいは値）にはより長い符号（すなわちより多いビット数）を割り当てることにより、最適化された効率的な圧縮を行なうことができる。
【０００８】
実際問題として、ハフマン符号化と算術符号化は、エントロピー符号化に適している。そして、ＪＰＥＧ標準は、両者に適合している。ＪＰＥＧ標準における対象の操作に関する相違点の１つは、両符号化手法にとって符号に対応する値のテーブルが必要であるにもかかわらず、デフォルトのテーブルが算術符号化には用意されているが、ハフマン符号化には用意されていない、という点である。しかし、特定のハフマン・テーブルの中には、最大の符号化効率と再構成時における最大の画像忠実度とが得られるようにＪＰＥＧ標準の下で自由に指定できるものがある。けれども、それらは、特製のハフマン・テーブルを計算・作成する計算上のオーバーヘッドを避けようとして画像忠実度が過度に劣化しない限り、デフォルトのテーブルであるかのように見境なく使われる場合が多い。
【０００９】
ここで、次の点を認識する必要がある。すなわち、符号化テーブルあるいは条件付けテーブルが画像に合理的に良好に適している場合、特にハフマン符号化を使うエントロピー符号化がデータ圧縮を保証する程度は極めて大きい。けれども、符号化それ自体は、統計に基づいていると共に多数の画像値あるいは画像値を表わす多数の値に関する一団の統計情報を必要とするので、極めて多くの計算を必要とする、という点である。逆に、テーブルを作成する元になった画像において出現するのが比較的稀（まれ）である多くの値を符号化することを符号化中の画像が必要としている場合（たとえこのような環境が出現するのが稀であっても）、当該符号化中の画像を表していない確率を搭載したテーブルを使うと、圧縮ではなく展開が行なわれる可能性がある。
【００１０】
使用した圧縮の程度に対して、たとえ最適圧縮および／または最適忠実度が達成されなくとも、ある種のハフマン・テーブルが事実上標準的に使用されるようになったのは、この理由による。逆に、ハフマン符号化の圧縮効率は、通常、顕著に向上しうる。そして、問題の画像に対応する特製のハフマン・テーブルによって、所定ビット数のデータに対して画像忠実度を最適に維持しうる。しかし、これは、符号化するのに多大な計算負荷を負担しないかぎり達成できない。
【００１１】
符号化した各値にハフマン符号割り当てる手法の階層的性質と、最も出現頻度が高く最も予測可能性の高い値（たとえそこに含まれている情報が理想的には余り意味がないとしても）を表わすのに少なくとも１ビットを使う必要があるという事実とに起因して、符号化すべき特定の値すべての発生頻度が５０％に上昇すると、ハフマン符号化らしく別の非効率が発生する。例えば、ある単一の値の発生頻度が７５％に上昇すると、ハフマン符号化の効率は８６％に低下する。実際問題として、大多数のＤＣＴ係数は零である（あるいは零に量子化されている）。したがって、ＤＣＴ係数あるいはＤＣＴ係数の差分をハフマン符号化する際に、多大な非効率がしばしば発生する。ＡＣ係数の場合、ＪＰＥＧ委員会は、零値の係数群を１つにまとめて個々の零値の係数を符号化しないことにより、この問題を解決した。したがって、ハフマン記号が５０％以上発生する可能性は、著しく低い。
【００１２】
圧縮効率は、各値（あるいは記号）の終点を検出するのに余分の処理が必要な可変長符号によって主として決まる。したがって、ハフマン復号化も、多大な計算負荷を必要とする。さらに、このハフマン復号化処理は、エントロピー符号化した画像データと一緒に伝送する必要があると共に画像ごとに変化しうる符号化テーブルを使って行なう。テーブル中のデータにアクセスする複雑さは、ハフマン符号が可変長であるという事実によって累増する。ハフマン符号化では、特定の記号（あるいは値）に含まれている単一のデータあるいはある量のデータの予測可能性に従って異なった数のビットを割り当てる。したがって、ハフマン符号は可変長である。応答速度を速めるために、復号化時に使用可能なハフマン・テーブルから参照用テーブルを計算してそれを格納しておくのが実務になっいる。したがって、１つの符号語当り少なくとも２バイトのテーブル・データにアクセスする必要のあの場合が多い。
【００１３】
さらに、ハフマン符号長として１６ビットが許されているから、従来の復号化方法では、記号値ごとに２１６個のエントリと符号長ごとに２１６個のエントリを備えたハフマン・テーブルにアクセスすることになる。これらのエントリは、ハフマン・テーブルを指定するあるいは変更するごとに計算する必要がある。復号化のためには、最大４つのＤＣテーブルおよび４つのＡＣテーブルと交互に配置した最低限４要素の画像とが必要になる可能性がある。小さなオンチップのキャッシュ（あるいはＲＡＭ）を備えたハードウェアの場合、このようなテーブルを使うと、キャッシュ・ミスあるいはＲＡＭアクセスごとに余分の処理サイクルを必要とするので、性能が劣化することになる。
【００１４】
【発明が解決しようとする課題】
本発明の目的は、少ない処理資源とハードウェアを使い極めて短時間で達成できるハフマン符号化と復号化の方法を提供することである。
【００１５】
本発明の別の目的は、パックした中間データ形式を使って増強したハフマン符号化と復号化の方法を提供することである。
【００１６】
【課題を解決するための手段】
本発明に係るハフマン符号化法は、次のように構成する。
記号をハフマン符号化するハフマン符号化法であって、
１つのテーブルにおける所定長の符号の最初の出現に対するシード値を定義するステップと、
１つの符号語の長さを格納するステップと、
前記数および前記符号語のビット数が所定ビット数以下の場合、前記長さおよび前記符号語を第１の形式で格納するステップと、
前記数および前記画像データが前記所定ビット数を超えるビット数から成る場合、前記シード値への索引、オフセット、および前記符号語を第２の形式で格納するステップと
を備える。
【００１７】
本発明に係るハフマン復号化法は、次のように構成する。
圧縮データをハフマン復号化するハフマン復号化法であって、
有効なハフマン符号の長さを判断する複数の試験基準の各々を使ってデータ・ストリームのビットを試験するステップと、
前記長さに対応する複数のオフセットのうちの１つと前記有効なハフマン符号とを組み合わせて、索引を生成するステップと、
前記索引を使って、ハフマン・テーブル中の記号値にアクセスするステップとを備える。
【００１８】
【発明の実施の形態】
次に、図面を参照して本発明の一実施形態を説明する。図１は、ペネベーカーらの上掲書の３９３頁に記載されているＪＰＥＧ標準に従う、ハフマン・テーブル仕様の構文を示す図である。図１に示す構文は、マーカー・セグメントと呼ばれており、以下でハフマン・エントロピー符号化または復号化を実行するのに使用する少なくとも１つのハフマン符号化テーブルを定義するのに使う。新たなパラメータすなわちテーブル値を変更すべきときはいつでも、これと同じ構文を使う。マーカー・セグメントは、常に、累積バイト数を含んでいる（これは、セグメントの終わりに所定の論理値のビットを付加することにより行なう場合がある）。そして、符号のフレーム開始（ｓｔａｒｔ  ｏｆ  ｆｒａｍｅ：  ＳＯＦ）ブロックと走査開始（ｓｔａｒｔ  ｏｆ  ｓｃａｎ：ＳＯＳ）ブロックに適用されたマーカー・セグメントは、ヘッダと呼ばれている。
【００１９】
ＪＰＥＧ標準に従うマーカー・セグメントは、図１に示すように常に、２バイト符号で始まる。この２バイト符号は、１６進数の「ＦＦ」バイトで始まり、当該マーカー・セグメントの機能を指定する非零の１バイトが続く。例えば、「ＦＦＤＢ」は「量子化テーブルを定義する（ｄｅｆｉｎｅ  ｑｕａｎｔｉｚａｔｉｏｎ  ｔａｂｌｅ：ＤＱＴ）」を表し、「ＦＦＣ４」は「ハフマン・テーブルを定義する（ｄｅｆｉｎｅ  Ｈｕｆｆｍａｎ  ｔａｂｌｅ：  ＤＨＴ）」を表わす。特に、「ハフマン・テーブルを定義する（ＤＨＴ）」機能に適用する場合、続く２バイトは、マーカー・セグメントに設けられたパラメータ・フィールドの長さＬｈ  を指定している。続く１バイトのうちの第１のニブル中の１ビットＴｃは、ＤＣまたはＡＣ（「０」または「１」）として直ぐに続くテーブルを指定している。（１ニブル＝１バイトの半分＝４ビット）。次に続くニブル中のビット群Ｔｈは、当該テーブルの名前を指定している。ＤＣテーブルとＡＣテーブルの各々に対して最大４つのテーブルが許される。そして、これらのテーブルのうちの任意のものあるいは全部を定義または再定義するのに、マーカー・セグメントを使うことができる。
【００２０】
次の１６バイトは、各ビット長がＬｉの符号の個数を指定している。これらの符号は、ＪＰＥＧ標準下で許される最大ビット長（あるいは任意のビット長）に対応する引き続くテーブル中に含まれることになる。表記規則によると、１ビット符号の個数はＬ１であり、１６ビット符号の個数はＬ１６である。画像の精度が８ビットであると、量子化後に得られる係数は高々１１ビットである。したがって、特に画像の精度が８ビットである場合には、すべてのビット長が表現されるわけではない。画像データ中で表現されない符号長は、すべて、１６進数の「００」として符号化することになる。続くバイト群Ｖ１，１  〜Ｖ１，Ｌ１６  は、出現頻度（例えば所定の長さの符号が提示される回数など）の順に並べた各ハフマン符号に対応する実際の値である。
【００２１】
ここで、次の点を思い出す必要がある。すなわち、ハフマン符号化などのエントロピー符号化では、出現頻度すなわち出現可能性の高い値にはより少ないビットを割り当てる。そして、ＤＣＴ係数の多くは、零である可能性がある、という点である。したがって、ＪＰＥＧ標準は、各々が２５６ものエントリを有する８つものハフマン・テーブルを用意している（そして、特定のハフマン符号の特定のＤＣＴ係数へのマッピングは常に定義されている、ということを保証している）。このプロセスを速めるために、参照テーブルを用意して、ハフマン・テーブルのＶｉ，ｊ  フィールドを検索することもできる。これにより、特定のＶｉ，ｊ  値を捜し出す操作の回数を減らすことができる。しかし、余分のメモリ資源を必要とする。そして、上述したように、より多数のテーブル・エントリを展開するのに余分の計算負荷をもたらす。
【００２２】
次に、図３の典型的なハフマン・テーブルを用いて、マーカー・セグメントの応用を説明する。導入として、次の点を理解する必要がある。すなわち、圧縮プロセスにおける量子化と離散コサイン変換（ＤＣＴ）の結果は、ラスター走査順に並べた一連のＤＣＴ係数になっている（ラスター走査とは、ＣＲＴディスプレイの水平方向に左から右に走査しながら順次下方へ移動する走査方式のことである）。零値の係数は、それらにジクザク順にアクセスすることにより大雑把にグループ化されている。そして、さらなる圧縮（およびエントロピー符号化など他の変換プロセスから成る強化）は、本願の関連出願に開示されているラン・アンド・サイズ（Ｒ／Ｓ）データに従ってデータをパックすることにより得られる。ランとは、零値のＡＣ  ＤＣＴ係数から成る連続列の長さのことである。サイズとは、非零のＤＣＴ係数を指定するのに必要なビット数のことである。ランすなわちＲ値は、Ｒ／Ｓバイトの上位ニブル（＝４ビット）として符号化される。サイズすなわちＳ値は、Ｒ／Ｓバイトの下位ニブルとして符号化される。
【００２３】
ここで、ＤＣ  ＤＣＴ係数差分とＡＣ  ＤＣＴ係数値は、Ｒ／Ｓ値によって完全には指定できない、という点を認識すべきである。しかし、ＪＰＥＧ標準に従ってＲ／Ｓ値だけを符号化し、かつ、図２に示すように、各符号に、正のＡＣ  ＤＣＴ係数またはＤＣ  ＤＣＴ係数差分値から成る実際のビット、および負のＡＣ  ＤＣＴ係数またはＤＣ  ＤＣＴ係数差分値から成る実際のビットを付加すれば、後述するように極めて膨大なデータ圧縮をしながら、かつ、すべての細部にわたってＪＰＥＧ標準に準拠しながら、元のＤＣＴ係数の情報をすべて含めるのに十分である。
【００２４】
説明を明瞭にするために、図３は、２バイトのマーカーが左方に伸びるように、ちょうど１６列に示してある。各バイトは、当該各バイトの２ニブルを表わす２つの１６進数化ディジットによって表されている。
【００２５】
図３の第１のマーカーは、画像の開始（ｓｔａｒｔ  ｏｆ  ｉｍａｇｅ：  ＳＯＩ）を表わす「ＦＦＤ８」である。第２のマーカーは、量子化テーブルの仕様を表わす「ＦＦＤＢ」である。ここで、次の点を理解すべきである。すなわち、量子化したＤＣＴ係数の値は、大きさが固定された範囲の値を表わす必要はない。正確には、量子化したＤＣＴ係数の値は、各々、大きさが他のもの異なる範囲の値を表わすことができる、という点である。このテーブルは、元の画像に対応するＤＣＴ係数を、本発明を理解するのに重要でない方法で分析することにより得られる。そして、このテーブルは、後で画像を再構成する間にＤＣＴ係数を「逆量子化（ｄｅｑｕａｎｔｉｚｅ）」するのに使う。
【００２６】
第３のマーカーは、少なくとも１つのハフマン・テーブルを指定しているマーカー・セグメントの開始を表わす「ＦＦＣ４」である。次の２バイト「０１Ａ２」は１０進数「４１８」の１６進符号である。１０進数「４１８」は、走査開始（ＳＯＳ）を表わす次のマーカー「ＦＦＤＡ」までのバイト数である。「ＦＦＤＡ」では、構成要素（例えばＲ、Ｇ、Ｂ、グレースケール〔白黒の階調〕、輝度／クロミナンス〔参照色との色質の違い〕など）の個数で始まるパラメータ・リストの長さが指定されている。そして、模式的に「・・・」で表してある圧縮データが続く。
【００２７】
上記「ＦＦＣ４」の次のバイトは、ＴｃとＴｈを表わす２ニブルから成る。両ニブルとも零であるから、このテーブルをＤＣテーブル０として定義している。これらはＤＣテーブルであり、かつ、ブロック当り１つのＤＣ  ＤＣＴ係数しか用意されていないから、ラン長は存在しない。そして、各バイトの第１のニブルが零である一方、第２のニブルは各サイズの余分のビット数（圧縮データ・ストリーム中で次に続く余分のビット数）を指定している。符号中の特定の数は、図４に示すハフマン符号に対応している。これらのものは、３ビット長の符号５個を含めて１２個しかない。これら１２個の値は、次の１２バイトで指定されている。これで、ＤＣテーブル０は完了する。
【００２８】
この時点で、２９バイトしか使っていない。すなわち、Ｔｃ、Ｔｈに１バイト、Ｌｉに１６バイト、Ｖｉ，ｊ  に１２バイトである。この２９バイトという値は、マーカーの直後に指定されているパラメータ長の４１８バイトよりもはるかに小さい。したがって、次の１バイトの２ニブルは、このマーカー・セグメントで指定される第２のハフマン・テーブルのクラスと名前を定義している。この場合、Ｔｃ値とＴｈ値がそれぞれ「１」と「０」であるから、第２のハフマン・テーブルは、ＡＣテーブル０である。次の１６バイトは、各長さの符号数を示すＬｉ  値である。そして、次のバイト群（その数はＬｉ  中で列挙されている符号の合計数〔最大６４〕に等しい）は、出現頻度の降順のハフマン符号の各々に対するＶｉ，ｊ  記号値である。これで、ＡＣテーブル０は完了する。
【００２９】
「４１８」の残りは、上述したのと同じ形式で記載すると共に符号化したさらに２つのテーブル、ＤＣテーブル１とＡＣテーブル１から成る。ＤＣテーブル１用のハフマン符号を、図５に表として示す。
【００３０】
図４と図５とを比較すると、ハフマン符号の特徴がいくつか分かる。第１に、上述したように、ハフマン符号は可変長である。そして、その「カテゴリ」は、ビット数すなわちサイズすなわちＳ値である。このＳ値は、上述したＲ／Ｓバイトに含まれていると共に、図３などのハフマン・テーブルにＶｉ，ｊ  として記録されている。第２に、すべて「１」値のビットから成る符号は、許されない。第３に、所定長の複数の符号は、許される。上記「複数」は、当該所定長の符号によって表しうる値の個数よりも小さい。第４に、そして本発明を理解するのに最も重要なものとして、ＪＰＥＧハフマン符号を構築して、階層的に区別した値を表わしている。この制約すなわち特質は、より長い他の符号と接頭辞が同じになる符号は許されない、という特徴に現れている。
【００３１】
ここで、上述した事項から、ハフマン・テーブルの構造を使うことにより、特定のハフマン符号群と、それらにそれぞれ割り当てたＲ／Ｓ値との間の対応関係を再構築することができる、ということが想起される。しかし、上述したように、このような再構築は、複雑であると共に時間をくう。したがって、参照テーブルを使ってハフマン・テーブルの検索する方がずっと普通である。このプロセスは、ハフマン符号は可変長であるので、有効なハフマン符号に対応する連続ビット数（１６以下）をも認識している必要がある、という事実によって複雑になっている。
【００３２】
有効なハフマン符号を認識してハフマン・テーブルを検索する公知の方法は、圧縮データ中で（次に）続く１６ビットを取り上げ、（２１６個のエントリを有するテーブルで）検索対象符号のビット数を見つけ、（同様のサイズの）別のテーブルで検索対象符号に対応するＲ／Ｓバイトを捜し出すものであろう。しかし、この方法は、記憶空間の観点から無駄が多いと共に、メモリに多大な負荷をかける。例えば、検索対象符号が調べるべき１６ビットのうちの始めの１ビット符号であるとすると、各テーブルの半分は、同数ビット（１６ビット）が「１」であり、検索対象記号に対するＲ／Ｓ値バイトが同一になるであろう。公知の別の方法では、複数のテーブルを使うが、それに対応して多数の検索操作を必要とする。
【００３３】
本発明では、各符号は任意の所定数の２進ビットに対応する数値を有するものと考えることができると共に、所定数の２進ビットに対応する数値が大きすぎてもそれを算出できる、というハフマン符号の特徴を利用している。圧縮データのうちのｎビットが論理的にこの最大値（以下、ｍａｘ（ｎ）、ただしｎ＝ビット数）以上である場合、追加のビットを調べ、ｍａｘ（ｎ＋１）と比較する必要がある。また、本発明は、ハードウェア・アーキテクチャの観点から、正しいビット数を考察し、それより多いビット数に対する残りの試験が失敗するまで、すべての試験が合格するから（例えば論理値が有効なハフマン符号に対して大きすぎる）、これらの試験は並行して実行できる、という事実も利用している。
【００３４】
例えば、図６に示すように、この試験は、１６個の比較器を使って並行に実行することができる。図６では、１６個の比較器は、Ｃ［０・・・ｎ］≧ｍａｘ（ｎ）なる数式で表されている。各比較器は、バレル・シフタなどのＣレジスタの連続するステージに接続された１個から１６個の入力端子を備えている。これらの比較器は、ディジタルであり、論理ゲートアレイとして構成することができる。
【００３５】
すなわち、第１の試験では、Ｃレジスタの現在の最上位ビットＭＳＢ（Ｃ［０］）と１ビット値であるｍａｘ（１）とを比較する。１ビット符号がない場合、ｍａｘ（１）＝０である。１ビット符号がある場合、ｍａｘ（１）＝１である。（すべて「１」から成る符号は不許可であるから、１ビット符号がある場合、その１ビット符号は「０」である）。ｍａｘ（ｎ）の値は、ｍａｘ（ｎ）がｎビットのうちの第１の符号であり、より長い符号語の接頭辞であるように構築されているから、いくつかの符号を有する第１のＬｎ  に対する非零のｍａｘ（ｎ）が存在することになる。（例えば、ｍａｘ（２）＝“１０”であり、これは、図４のカテゴリ５の接頭辞である）。
【００３６】
図７は、別の実施形態を示す図である。図７では、圧縮データのだんだん多くなるビットとｍａｘ（ｎ）の値とを比較している。ｎの値は、比較が失敗する（すなわち「０」を生成する）最初の値に成るように決めてある。
【００３７】
図８は、ＡＬＵ（ａｒｉｔｈｍｅｔｉｃ  ｌｏｇｉｃ  ｕｎｉｔ：算術演算装置）への入力の１つとしてＣレジスタのｎ個のＭＳＢに付加した先行する「０」を示す図である。残りの入力は、事前算出したｏｆｆｓｅｔ（ｎ）である。加算後に得られる低位の結果は、参照テーブル（ＬＵＴ）／ハフマン・テーブルへの索引である（この索引は、ＡＣ符号化用の８ビットのうちのＤＣ差分用の４ビットから成っている）。参照テーブル（ＬＵＴ）／ハフマン・テーブルは、「ハフマン・テーブルを定義（Ｄｅｆｉｎｅ  Ｈｕｆｆｍａｎ  Ｔａｂｌｅ：  ＤＨＴ）」マーカー・セグメントで渡されたＶｉ，ｊ  記号値を含んでいる。このテーブルの出力は、Ｒ／Ｓバイトである。
【００３８】
図９は、ｍａｘ（ｎ）値を構築するためのフローチャートを示す図である。この方法論は、図３のＤＨＴマーカー・セグメントで指定されているＲ／Ｓバイトへのオフセット（ｏｆｆｓｅｔ）も構築する。ただし、ｏｆｆｓｅｔ（０）は、Ｒ／ＳリストまたはＲ／Ｓリストへのポインタの第１バイトから成る索引（例えば「０」）である。ステップ７１におけるｍａｘ（ｎ）とｏｆｆｓｅｔ（ｎ）の初期化は、ｉ、ｍａｘ（０）、ｏｆｆｓｅｔ（０）を「０」に設定することにより開始する（ステップ７２）。次いで、ステップ７３で、ｉをインクリメントし、ｏｆｆｓｅｔをｍａｘ（ｉ−１）未満の最後のｏｆｆｓｅｔに設定する。ｍａｘ（ｉ）の値は、Ｌｉ  ＋ｍａｘ（ｉ−１）として計算する。したがって、Ｌｉ  が非零になるまで、ｏｆｆｓｅｔ（ｎ）とｍａｘ（ｎ）は「０」のままである。それゆえ、図６または図７の最初の比較Ｃ［０・・・ｎ］は、常に合格する。なぜなら、（当該長さの少なくとも１つの符号が存在することを示す）非零のＬｉ  が出現するまで、第１ビットの論理値／数値は、常に「０」以上であるからである。ステップ７３に示すように、非零（すなわち「１」）のＬｉ  が出現した場合、それを「０」に付加すると、ｍａｘ（ｉ）は、より大きな符号の接頭辞をなす第１の符号に設定されることになる。このプロセスをｉ＜１６の間繰り返して、すべてのＬｎ  に対するすべてのｍａｘ（ｎ）を生成する。したがって、例えば、５個の３ビット符号（例えば０、１、２、３、４）が存在する場合、ｍａｘ（３）は５に設定される。この値５（２進数で「１０１」）は、より長い符号の一部である。ただし、これ以上符号が存在しなければ、この特定の符号は必ずしも使用されない。それゆえ、ｍａｘ（ｉ）は、大きすぎるｉビットの第１の符号（すなわちｉビットの最大符号よりも１つの値だけ大きい符号）を指し示している。Ｌ（ｉ＋１）がヌルでない（例えば１ビットだけ大きい符号が存在する）場合、当該符号の値は、ｍａｘ（ｉ）の２倍である。（ｉ＋１）符号は、２＊ｍａｘ（ｉ）で始まり、順番に番号付けされる。そして、ｍａｘ（ｉ＋１）は、この順番のの後の次の数（すなわち２＊ｍａｘ（ｉ）＋Ｌ（ｉ＋１））である。Ｌ（ｉ＋１）＝０の場合、ｍａｘ（ｉ＋１）は２＊ｍａｘ（ｉ）に等しい。そして、次の非零のＬｉ  が出現する前に、このような２倍項がいくつか存在しうる。
【００３９】
より一般に、ｍａｘ（ｉ）とｏｆｆｓｅｔ（ｉ）は、次に示すように、Ｌｉ  の項で計算する。
（ｉ＝０
（ｍａｘ（０）＝０
（ｏｆｆｓｅｔ（０）＝０
（ｉ＝１
（ｍａｘ（１）＝Ｌ１  ＋２＊０
（ｏｆｆｓｅｔ（１）＝０−０＝０
（ｉ＝２
（ｍａｘ（２）＝Ｌ２  ＋２＊Ｌ１
（ｏｆｆｓｅｔ（２）＝０−Ｌ１
・
・
・
【００４０】
ｏｆｆｓｅｔ（ｉ）は、検索対象符号に対応する復号化した値がＲ／Ｓ値のリスト中のどこに位置しているかを判断するのに使う。すなわち、ｏｆｆｓｅｔ（ｉ）にハフマン符号のｉビットを付加して得られる値は、対応するＲ／Ｓバイトが存在する、ハフマン・テーブル中のアドレスになる。これにより、本発明の文脈において極めて重要な利点がいくつか得られる。特に、各々が２１６個のエントリを有する複数の参照テーブルから成る関数群は、１６個のエントリに限られているｍａｘ（ｎ）値とｏｆｆｓｅｔ（ｎ）から成るテーブル群で置き換えることができる。このテーブルは、極めて迅速に計算して効率的に格納することができる。このテーブルは特異であると共に小さいから、その中のデータを極めて迅速に取り出して、ＪＰＥＧ標準構文によるデータ・ストリーム中にハフマン符号と共に含まれているＤＣＴ係数データとＤＣＴ係数差分データを評価するのに使うＲ／Ｓデータを取得するための、ハフマン・テーブルへの直接索引を作成することができる（これは、他の処理手法と一緒に利用できると共に、他の型のデータに対しても利用できる）。
【００４１】
まとめとして、圧縮データの復号化を図１０を用いて説明し、その好適で完全な機能を図１１〜図１３と共に後述する。プロセスがステップ８１で開始すると、復号化するＡＣ係数の個数ｋを零に初期化した後、ループに入って非零のＡＣ係数を各々順番に処理する。上述すると共にステップ８３に示すように、圧縮データの１６ビットの列を（例えば図６または図７の）Ｃレジスタにロードし、並列比較または逐次比較によって、有効なハフマン符号のビット数ｎを判断する。いったんｎが判明すると、ステップ８４に示すように、対応するｏｆｆｓｅｔ（ｎ）も判明し、ハフマン・テーブル・アドレスへのポインタＣ［０・・・ｎ−１］＋ｏｆｆｓｅｔ（ｎ）を計算した後（例えば図８）、Ｒ／Ｓ値を４ビット右にシフトすることにより、ハフマン・テーブルのＲ／ＳバイトからＳ値を抽出する。次いで、ステップ８５に示すように、圧縮データを（ハフマン符号の長さに対応する）ｎビットだけ（左に）シフトしてデータ・ストリーム中にＡＣ係数値を供給する。
【００４２】
次いで、ステップ８６に示すように、このデータを図１４の形式で供給するために、Ｒ／Ｓ値群のビット群と１６進の「０Ｆ」バイトとをＡＮＤしてＲ／Ｓ値からＲを取り除き、２つの追加のバイトにＲ／Ｓバイトを格納すると共に余分なＳビット群を格納する。そして、圧縮データを（左に）Ｓビットだけシフトして、Ｃレジスタの先頭に次のハフマン符号を供給する。次いで、次の非零のＡＣ係数を復号化するために、ｋ値をＲ＋１だけインクリメントする（ステップ８７）。パックしたデータ形式を完了させるために、ステップ８８でＲ／Ｓ値を試験する。Ｒ／Ｓ値が０である場合、ステップ９０に示すように、ブロックの終わり（ｅｎｄ−ｏｆ−ｂｌｏｃｋ：  ＥＯＢ）を示した後、当該長さバイトを格納する。Ｒ／Ｓ値が０でない場合、インクリメントしたｋ値を試験する（ステップ８９）。ｋ値が１つのブロック中のＡＣ係数の最大数である６３である場合、０のＲ／Ｓ値を格納してＥＯＢを示した後、当該長さバイトを格納する。ｋ値が６３未満の場合、プロセスはステップ８３にループして、ＡＣ係数をさらに処理する。
【００４３】
図１０のプロセスの完全な機能を図１１〜図１３に示す。本発明のこの機能は、ｍａｘ（ｎ）値群を５個のｘＣ＿ｍａｘ＜０・・・４＞なる３２ビット語にパックするものである。これらは、レジスタに格納して操作することができる。これにより、例えば図６または図７のハードウェア構成に従う比較のために、頻繁にメモリ・アクセスして値を取得する必要がなくなる。
【００４４】
ｍａｘ（ｎ）値は、次に示すように、語中に密にパックされている。
0003627016.tif 000002
これらの値は、図１０のステップ８３を実行する際に、図１１〜図１３に示すように操作する。特に、ハフマン符号中のビット数ｎを判断するために、ｎの値を１に初期化した後、圧縮データの次の３２ビットと共にレジスタすなわち変数ｃｏｍｐをロードする。ｃｏｍｐは、ｘＣ＿ｍａｘ＜０＞の最上位ビットと論理比較する。ｃｏｍｐが論理的にｘＣ＿ｍａｘ＜０＞の最上位ビット以上の場合、ハフマン符号は１ビットではないので、ｎを２にインクリメントする。次のｍａｘ（ｎ）値をレジスタの最上位ビットにシフトした後、もう１ビットとｃｏｍｐ値とを比較する手順を繰り返す。この際、アクセスするごとにｎをインクリメントする。ｃｏｍｐの比較が失敗したとき、求めるビット数が見つかっているので、比較の手順を完了する。ＲＩＳＣアーキテクチャの中には、レジスタへの複写、マスク、およびシフト命令を１サイクルで行なうものがある。この場合、ｎ値、ｃｏｍｐ値、ｘＣ＿ｍａｘ値がレジスタ中に存在するものと仮定すると、ｎ値がもっと大きい必要があるか否か、そして、記憶装置（メモリ）アクセスは必要ないか否かを判断するのに３サイクルしかかからない。したがって、特に、短いハフマン符号は長いものよりも出現頻度が高いから、上記比較試験は、極めて迅速に実行することができる。
【００４５】
本発明による復号化器と復号化方法に関する以上の説明から、ＪＰＥＧ標準に従って圧縮した画像データの再構成において、速度と応答性が顕著に向上しているのが分かる。その上、データ処理用のハードウェアおよび／またはソフトウェアに対する要件が顕著に低減していることも分かる。また、上掲した本願の関連出願に開示したパックしたデータの形式と組み合わせると、符号化プロセスにおいても顕著な利点が得られる。ここに開示した中間データ形式を、図１４に示す。
【００４６】
図１５は、パックしたＤＣＴブロックをエントロピー符号化したデータに符号化するフローチャートを示す図である。まず、ステップ１００１でＤＣＴ係数を符号化する。次いで、ループ１００２に入る。ループ１００２では、次のように各々実行する。すなわち、ステップ１００３でＲ／Ｓバイトの符号化を実行し、ステップ１００４でＳ値に従って余分のビットの符号化を実行し、ステップ１００５で両者の格納を実行する。次いで、ステップ１００６でＥＯＢ符号があるか否かを判断する。ＮＯならば、ステップ１００３に戻ってループ１００２を繰り返す。ＹＥＳならば、ステップ１００７に進む。ステップ１００７でｋ＝６３であるか否かを試験する。ＹＥＳならば、プロセスは完了する。なぜなら、ｋ＝６３は供給されうる値の最大数を表わしていると共に、ＥＯＢ記号は、これだけを取り出して符号化する必要がないからである。ＮＯすなわちｋ＜６３ならば、ステップ１００８でＥＯＢを符号化し、ステップ１００９で格納した後、プロセスを完了する。ここで、次の点に留意する必要がある。すなわち、各エントリはハフマン符号化したデータに必要な粗い形で既に存在しているので、プロセスは、ＥＯＢマーカーが出現するまで、最高速で各Ｒ／Ｓビットと余分のビットとの対を順番に符号化することができる。
【００４７】
符号化の間に、Ｒ／Ｓバイトをハフマン符号に変換する必要がある。Ｒ／Ｓ値にハフマン符号を割り当てる際に依拠する統計データを集めるのに、図１４のパックしたデータ形式は特に都合がよい。すなわち、データ・ブロックを走査する１回のパスで、各Ｒ／Ｓ値とハフマン符号の割り当てと伝送すべきＬｉ  値とが出現する回数を計数することができる。データ・ブロックを走査する２回目のパスの前に、伝送に使用する実際のＲ／Ｓ値は、図１の形式の一部としての伝送用のＶｉ，ｊ  記号値として組み立てる。各ハフマン符号長ｎ内のカテゴリは任意に割り当てることができるから、ｍａｘ（ｎ）を格納する代わりに、長さｎの第１のハフマン符号用にｓｅｅｄ（ｎ）なる値を定義する。
ｓｅｅｄ（ｎ）は、数値的に２＊ｍａｘ（ｎ−１）に等しい。
【００４８】
図１６は、Ｈ＿ｃｏｄｅテーブル、Ｈ＿ｏｆｆｓｅｔテーブル、Ｈ＿ｓｅｅｄテーブルを初期化するフローチャートを示す図である。まず、開始シード（ｓｅｅｄ）（すなわち所定のビット数に対応する数値が最小である最初の符号語）を零（０）に初期化する。当該符号語のビット数（すなわち符号語長）を零に初期化する。
【００４９】
次いで、ｉが１６未満である限り、ｉを１だけインクリメントした後、ｓｅｅｄを２倍にしてＨ＿ｓｅｅｄ（ｉ）に格納する。次いで、ｃｏｄｅをｓｅｅｄに設定した後、ｓｅｅｄをｉビット符号の数だけインクリメントする。次いで、ｊを零に初期化する。
【００５０】
ｊが符号Ｌｉ  の個数未満である限り、「ハフマン・テーブルを定義（ＤＨＴ）」マーカー・セグメントにおいて、Ｒ／Ｓを次のＶｉ，ｊ  記号値に設定する。当該符号のビット数（ｉ）が６未満の場合、当該ビット数と当該符号をＨ＿ｃｏｄｅ（ＲＳ）にパックする。このとき、当該バイトの上位３ビットを当該符号の当該ビット数を設定し、下位５ビットに当該符号を設定する。ｉが５よりも大きい場合、Ｈ＿ｃｏｄｅ（ＲＳ）を当該ビット数に設定する。次いで、Ｈ＿ｏｆｆｓｅｔ（ＲＳ）をｊに設定する。なぜなら、これはｉビット符号のうちのｊ＋１番目の符号だからである。次いで、両経路について、ｊとｃｏｄｅの双方をインクリメントする。
【００５１】
ソフトウェアで実現する場合、最長のｓｅｅｄが１６ビットだから、Ｈ＿ｓｅｅｄテーブルは、おそらく少なくとも１６ビットの整数として実現される。ハードウェアの場合、ｎ番目のエントリがｎビットの符号用のｓｅｅｄだから、ｎ番目のエントリしかｎビットである必要がない。説明を簡明にするために、図１６では、Ｈ＿ｓｅｅｄテーブルを１７エントリ（０〜１６）用に初期化している。図１７に示すフローチャートでは、６番目から１６番目のエントリしか使うことができない。ここでも、ハードウェアによる実施形態では、これを利用してロード可能なレジスタの数を減らしている。
【００５２】
ＤＣハフマン・テーブルとＡＣハフマン・テーブルは、各々、Ｈ＿ｓｅｅｄテーブル、Ｈ＿ｃｏｄｅテーブル、およびＨ＿ｏｆｆｓｅｔテーブルを１組必要とする。幸い、最低限の実現方法の場合、Ｒ＝０であり、Ｓの最大値が１１だから、ＤＣ  Ｈ＿ｃｏｄｅテーブルとＤＣ  Ｈ＿ｏｆｆｓｅｔテーブルは、１２エントリしか必要としない。一般的な実現方法の場合、Ｓの最大値が１６であるから、これらのテーブル用に最大１７エントリ作成する。
【００５３】
説明を簡明にすると、大部分のＲ／Ｓバイトを使うことができるから、Ｈ＿ｃｏｄｅテーブルとＨ＿ｏｆｆｓｅｔテーブルは、各々、おそらく２５６エントリ備えることになる。これらのテーブルのエントリは、高々１バイトである。したがって、１６ビット符号語のビット数を表わすのに当該符号語のエントリに加え余分のビットを必要とする代わりに、より長い符号語用に小さなＨ＿ｓｅｅｄテーブルを使う。それゆえ、当該サイズの最後の符号語を算出するのに、余分バイトは１バイトしか必要としない。短い符号（すなわち５ビット未満）は、すべて、Ｈ＿ｃｏｄｅバイトに含める。出現頻度の高い記号ほど符号が短いから、記憶装置に対する１バイト分のアクセスで、最も普通に符号化した記号に必要なものをすべて取得することができる。
【００５４】
図１７は、図１５のＲ／Ｓバイトの符号化を実行するステップ１００３をより詳細に示す図である。まず、一時変数または一時レジスタｔｅｍをＨ＿ｃｏｄｅ（ＲＳ）の内容に設定する。ｎの値を当該バイトの上位３ビットに設定する。ｎが零の場合、ｎをｔｅｍに設定する。そして、Ｈ＿ｓｅｅｄ（ｎ）にＨ＿ｏｆｆｓｅｔ（ＲＳ）を加算して当該符号を生成する。ｎが零でない場合、ｃｏｄｅをｔｅｍの下位５ビットに設定する。次いで、圧縮データを左にｎビットシフトさせた後、その下位ｎビットに当該符号を入れる。ｃｏｍｐは、連続バレル・シフタのように取り扱う。そして、３２ビット語を出力するプロセスは、当業者にとって周知である。
【００５５】
従来技術では、最大２５６個のＲ／Ｓ記号用に、ｎと最大１６ビットのビット・パターンを格納している。しかし、本発明によると、ｎと当該符号語は、合計８ビット以下の中に両者を格納できるときには、１バイトの中に格納する。これにより、ハフマン・テーブルを顕著に短くすることができる。そして、出現する符号の大部分はこの形式を使うのに十分なほどに短いから、このことは特に好都合である。この形式を使っていることは、当該バイトの上位３ビットの位置を非零値にすることにより示す。
【００５６】
すべての長いビット・パターンに対しては、長さの表示だけをＳとして格納する。そして、上位ニブルを「００００」に設定して異なった形式であることを表示する。これら長い符号の場合、ｓｅｅｄ（すなわち特定ビット長の最初の符号値）への索引として当該長さを使う。次いで、参照テーブルから対応するオフセットを決定し、それを当該ｓｅｅｄに付加して当該符号値を生成することができる（最大オフセットが２５５であるから、上記オフセットは１バイトの中に納まる）。Ｒ／Ｓバイトを符号化して格納した後、余分のＳビットを符号化する。この符号化は、図１４の中間データ形式の各ＡＣ係数値の２バイトから可変長を展開するようにシフトして行なうのが望ましい。
【００５７】
上述した点から、本発明によれば、符号化用のデータ処理の効率が向上すると共に、ハフマン・テーブルを検索ためのテーブルを計算して格納する効率が顕著に向上する。これらの利点は、ＪＰＥＧ標準に完全に準拠した方法でもたらされると共に、ハフマン符号化のすべての用途に適用可能である。
【００５８】
ＪＰＥＧ標準に関する好適な一実施形態の観点から本発明を説明したけれども、本発明は特許請求の範囲の本旨と範囲の内で変更して実施することができる、ということを当業者は認識できる。例えば、これら高速符号化法と高速復号化法は、昇順に並んだ各長さの多くの符号から構築されるすべてのハフマン・テーブルに適用できる。さらに、当業者は、本発明の上の説明から、上述した手法を降順に並べて構築したハフマン・テーブルに適用することができる。
【００５９】
まとめとして以下の事項を開示する。
（１）記号をハフマン符号化するハフマン符号化法であって、
１つのテーブルにおける所定長の符号の最初の出現に対するシード値を定義するステップと、
１つの符号語の長さを格納するステップと、
前記数および前記符号語のビット数が所定ビット数以下の場合、前記長さおよび前記符号語を第１の形式で格納するステップと、
前記数および前記画像データが前記所定ビット数を超えるビット数から成る場合、前記シード値への索引、オフセット、および前記符号語を第２の形式で格納するステップと
を備えたハフマン符号化法。
（２）前記記号がＪＰＥＧ  Ｒ／Ｓバイトである、
上記（１）に記載のハフマン符号化法。
（３）前記符号語が画像データである、
上記（１）に記載のハフマン符号化法。
（４）前記画像データがＪＰＥＧ画像データである、
上記（３）に記載のハフマン符号化法。
（５）圧縮データをハフマン復号化するハフマン復号化法であって、
複数の試験基準の各々を使ってデータ・ストリームのビットを試験して有効なハフマン符号の長さを判断するステップと、
前記長さに対応する複数のオフセットのうちの１つと前記有効なハフマン符号とを組み合わせて、索引を生成するステップと、
前記索引を使って、ハフマン・テーブル中の記号値にアクセスするステップとを備えたハフマン復号化法。
（６）さらに、
前記試験基準および前記複数のオフセットを、ハフマン・テーブルのデータから計算するステップ
を備えた、
上記（５）に記載のハフマン復号化法。
（７）前記圧縮データが画像データである、
上記（５）に記載のハフマン復号化法。
（８）前記画像データがＪＰＥＧ画像データである、
上記（７）に記載のハフマン復号化法。
【図面の簡単な説明】
【図１】ＪＰＥＧ標準によるハフマン・テーブル仕様の構文を示す図である。
【図２】ＡＣ  ＤＣＴ係数またはＤＣ  ＤＣＴ係数差分のハフマン符号化を示す図である。
【図３】ＪＰＥＧ標準による典型的なハフマン・テーブル仕様とエントロピー符号化した画像データを示す図である。
【図４】輝度ＤＣ  ＤＣＴ係数差分値に適したハフマン符号の典型的なテーブルを示す図である。
【図５】クロミナンスＤＣ  ＤＣＴ係数差分値に適したハフマン符号の典型的なテーブルを示す図である。
【図６】本発明の実施に使用可能な別のハードウェアの実施形態の概念図である。
【図７】本発明の実施に使用可能な別のハードウェアの実施形態の概念図である。
【図８】本発明の実施に使用可能なハードウェアの実施形態を幾分詳細に示す概念図である。
【図９】本発明による比較値とハフマン・テーブル・ポインタ・データの計算の好適な形態を示すフローチャートを示す図である。
【図１０】ハフマン符号化したＲ／Ｓ値を含む圧縮データの復号化における本発明の方法論を示すフローチャートを示す図である。
【図１１】図１０のプロセスの好適な機能を示すフローチャートを示す図である。
【図１２】図１０のプロセスの好適な機能を示すフローチャートを示す図である。
【図１３】図１０のプロセスの好適な機能を示すフローチャートを示す図である。
【図１４】ハフマン符号化を迅速に実行しうる元になるパックした中間データ形式を示す図である。
【図１５】本発明による符号化のフローチャートを示す図である。
【図１６】符号化テーブルの初期化を行なうフローチャートを示す図である。
【図１７】図１５の一部の好適な実現方法を示す図である。
【図１】
0003627016.tif 000003
【図２】
0003627016.tif 000004
【図３】
0003627016.tif 000005
【図４】
0003627016.tif 000006
【図５】
0003627016.tif 000007
【図６】
0003627016.tif 000008
【図７】
0003627016.tif 000009
【図８】
0003627016.tif 000010
【図９】
0003627016.tif 000011
【図１０】
0003627016.tif 000012
【図１１】
0003627016.tif 000013
【図１２】
0003627016.tif 000014
【図１３】
0003627016.tif 000015
【図１４】
0003627016.tif 000016
【図１５】
0003627016.tif 000017
【図１６】
0003627016.tif 000018
【図１７】
0003627016.tif 000019