JP3974036B2

JP3974036B2 - How to perform Huffman decoding

Info

Publication number: JP3974036B2
Application number: JP2002540317A
Authority: JP
Inventors: アチャリャ，ティンク; ツァイ，ピン−シン
Original assignee: Intel Corp
Current assignee: Intel Corp
Priority date: 2000-10-31
Filing date: 2001-10-09
Publication date: 2007-09-12
Anticipated expiration: 2021-10-09
Also published as: TW538599B; WO2002037687A2; US6646577B2; GB2385759A; US6982661B2; DE10196890B4; US20030085821A1; CN1547805A; JP2004515096A; US6563439B1; KR20030040567A; AU2002211558A1; CN100417028C; WO2002037687A3; GB2385759B; US20030174077A1; GB0311329D0; DE10196890T1; KR100527891B1

Description

【０００１】
（関連出願）
本特許出願は、Ａｃｈａｒｙａらによる、同時出願された米国特許出願第０９／７０４，３９２号、「ＡＭｅｔｈｏｄｏｆＧｅｎｅｒａｔｉｎｇＨｕｆｆｍａｎＣｏｄｅＬｅｎｇｔｈＩｎｆｏｒｍａｔｉｏｎ」（代理人整理番号第０４２３９０号、Ｐ９８０４）に関するものであり、本発明の譲受人に譲受され、かつ参照により、本明細書に組み込んである。
【０００２】
（背景）
本開示は、ハフマン・デコーディングに関する。
【０００３】
周知のように、ハフマン・コーディングは、普及している可変長統計エンコーディング・スキームである。またこれも周知のように、ハフマン・コードの生成は、それぞれの個々のシンボルに対する統計的確率に依拠する。たとえば、Ｄ．Ａ．Ｈｕｆｆｍａｎによる、「ＡＭｅｔｈｏｄｆｏｒｔｈｅＲｅｃｏｎｓｔｒｕｃｔｉｏｎｏｆＭｉｎｉｍｕｍＲｅｄｕｎｄａｎｃｙＣｏｄｅｓ」（ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＲＥ、Ｖｏｌｕｍｅ４０、Ｎｏ．９、ｐａｇｅｓ１０９８〜１１０１，１９５２）を参照されたい。従来のテーブル・ルックアップ・ベースのエンコーディング・スキームが、少なくとも部分的に、効率性がよく、かつ比較的実装が簡単であるために、ハフマン・エンコーディングに広く使用されている。しかし、テーブル・サーチ・ベースのデコーディングは、通常、ソフトウェアとハードウェアの両方の実装の点において非効率的である。これは、実用的な応用例に典型的であるように、テーブル内のエントリの数がかなり高い場合に、特にそうである。ハフマン・デコーディングに用いられる別のアプローチが、「木をトラバースする技術」を用いるハフマン木の生成である。しかし、このデコーディング技術はまた欠点も有する。この特定の技術はビット・シーケンシャルであり、ハフマン木生成プロセスのためおよびデコーディング・プロセスのためのメモリ割当および計算の実行の両方で、余分な「オーバヘッド」を導入する。
【０００４】
本発明と考えられる主題については、本明細書の結論部分において、詳細に記載しかつ明確に特許請求することとする。しかし、本発明は、構成およびオペレーションの方法と、その目的、特徴、利点の両方に関して、以下の詳細な説明を添付図面と合わせて参照することにより、最も良く理解されるであろう。
【０００５】
（詳細な説明）
以下の詳細な説明において、本発明を完全に理解するために、多数の具体的な詳細事項を記載する。しかし、これらの具体的な詳細事項なしに本発明を実践できることを、当業者なら理解するであろう。他の例においては、本発明の意味が不明確とならないように、周知の方法、手順、構成要素、回路について詳細に記述していない。
【０００６】
上記に表示したように、１組のシンボルのハフマン・コードの生成が、ソース・シンボルの出現確率に基づく。通常、本状況下でハフマン木と呼ぶ２分木の構築が用いられる。上述の文書で、Ｄ．Ａ．Ｈｕｆｆｍａｎは、このようにプロセスを記述している。
・すべての可能なシンボルを、その確率とともに列挙する。
・最小の確率を有する２つのシンボルを見つける。
・これらを、その確率が個々の確率の合計である、両方のシンボルを含む単一の集合と置き換える。
・リストがただ１つのメンバしか含まなくなるまで繰り返す。
この手順により、複数の集合の再帰的に構造化された集合が作成され、そのそれぞれが正確に２つのメンバを含む。したがって、それは、「葉」としてのシンボルを有する２分木（「ハフマン木」）として表すことができる。次いで、特定のシンボルのコード（「ハフマン・コード」）を形成するために、２分木をルートからそのシンボルまでトラバースし、左の枝には「０」を、右の枝には「１」を記録する。しかし、この手順についての１つの問題点は、得られるハフマン木が一意ではないことである。このようなコードの応用例の一例が、ＧＺＩＰなどのテキスト圧縮である。ＧＺＩＰは、「無料の」または自由に使用可能なＵＮＩＸ（登録商標）のようなオペレーション・システムを開発するという目標を有するＧＮＵ（Ｇｎｕ’ｓＮｏｔＵｎｉｘ）プロジェクトの下で開発されたテキスト圧縮ユーティリティであり、ＵＮＩＸオペレーション・システム上で「ｃｏｍｐｒｅｓｓ」テキスト圧縮ユーティリティを置き換えるためのものである。たとえば、ウェブサイト「ｈｔｔｐ：／／ｗｗｗ．ｇｚｉｐ．ｏｒｈ／」のｇｚｉｐ−１．２．４．ｔａｒとして使用可能なＧａｉｌｌｙ，Ｊ．Ｌ．およびＡｄｌｅｒ，Ｍ．による「ＧＺＩＰｄｏｃｕｍｅｎｔａｔｉｏｎａｎｄｓｏｕｒｃｅｓ」を参照されたい。
【０００７】
周知のように、結果として生じるハフマン・コードはプリフィックス・コードであり、より頻繁に現れるシンボルに、より少ない数のビットが割り当てられて、可変長ハフマン・コードを形成する。その結果、シンボルの出現頻度を利用することから、最終的に平均コード長が減少される。
【０００８】
図１は、３つのソース・シンボルを有するハフマン木の簡単な一例を示す図である。異なる２値シンボルを木の縁に割り当てることにより、いくつかの２進コードを使用して、同じハフマン木を表すことができる。
【０００９】
このハフマン木のための可能な集合のハフマン・コードが、図２に例示してある。図２から、ハフマン・コードは一意ではないことが示されているが、この例からは、それぞれのシンボルの個々のコード長が一意であるように見える。
【００１０】
対応するハフマン木を構築することにより、ハフマン・コードの長さ情報を生成できる。しかし、上記に表示したように、ハフマン・コードはこの方式で生成された場合は一意ではない。しかし、２つの制約を課すことにより、ハフマン木を用いて作成されたハフマン・コードが一意であると保証できることが分かる。
これらの制約とは、
１．所与のビット長のすべてのコードが、それらが表すシンボルと同じ順序で、辞書式順序で連続した値を有する。
２．より短いコードが、より長いコードより辞書式順序で先行する。
【００１１】
これらの制約に基づいて、ハフマン・コードが一意的に判断できる。図３は、たとえば、これらの制約を用いる１９シンボルのハフマン・コード集合を示す図であり、ここで、コード長はハフマン木を使用して事前に判断されている。図３の表については、ハフマン・コード・テーブル内のエントリ内のダッシュが、シンボルおよび現在のソース・アルファベットによるコードが存在せず、その長さ情報がゼロであることを示している。
【００１２】
本発明の範囲がこの点に限定されるものではないが、上述した制約は、たとえば上記に記述したユーティリティ、ＧＺＩＰなどのさまざまな圧縮アプローチおよび標準において用いられてきた。通常このような応用例では、ハフマン木情報は、圧縮されたテキスト・データとともに１組のコード長情報で通過する。したがって、その集合のコード長情報は、一意のハフマン木を再構築するのに十分である。たとえば、図３に例示されているハフマン・コード・テーブルを、ＧＺＩＰで実施されるような以下のプロセスを使用して生成できる。
【００１３】
コード長は、最初、長さ［ｌ］である。
１）それぞれのコード長のためのコードの数をカウントする。
長さＮ（Ｎ＞＝１）のコードの数を「カウント［Ｎ］」とする。
２）それぞれのコード長のための最小コードの数値を見つける。

３）２で判断された連続した値を使用して、すべてのコードに数値を割り当てる。
【００１４】
上記に表示したように、ハフマン・エンコーディングが、テーブル・ルックアップ技術を使用して比較的簡単に達成できる。しかし、ハフマン・コードのデコーディングは、通常はより計算集約的である。なぜなら、コード・ワードがデコードすべき圧縮されたビット・ストリーム内で受け取られた場合、コード・ワード間には定義済み境界がないからである。上記に記述したように、ハフマン・コードは可変長コードである。
【００１５】
一定入力レート・デコーダと呼ぶ１つのアプローチまたは技術が入力ビット・ストリームを一度に１ビットずつシリアルに処理する。この方法は、デコーディングまたはハフマン木の構築を用いる。したがって、ルートから開始し、その技術には、終端ノードに到達するまで、デコーディング木の枝をトラバースすることが必要となる。終端ノードでは、コード・ワードは完全にデコードされ、したがって、対応するシンボルを所望のように作成または出力できる。次いで、このプロセスは、再び木のルートから開始する。たとえば、Ｂ．ＢｈａｓｋａｒｉｎおよびＫ．Ｋｏｎｓｔａｎｔｉｎｉｄｅｓによる「ＩｍａｇｅａｎｄＶｉｄｅｏＣｏｍｐｒｅｓｓｉｏｎｓＳｔａｎｄａｒｄｓ：ＡｌｇｏｒｉｔｈｍｓａｎｄＡｒｃｈｉｔｅｃｔｕｒｅｓ」（ＫｌｕｗｅｒＡｃａｄｅｍｉｃＰｕｂｌｉｓｈｅｒｓ、１９９５）を参照されたい。
【００１６】
図４は、対応するデコーディング木を有するハフマン・エンコーディング・テーブルの一例を示す図である。ハードウェアまたはソフトウェアにおけるこのようなデコーダに関連する１つの問題が、どのようにしてデコーディング木をメモリに効率的にマッピングするかである。たとえば、図５は、図４のデコーディング木を使用するビット・シリアル・ハフマン・デコーディングのための読取専用メモリ（ＲＯＭ）エントリのテーブルを示す図である。メモリを効率的にマッピングするための１つのアプローチが、たとえば、Ｍｕｋｈｅｒｊｅｅらによる「ＭＡＲＶＬＥ：ａＶＬＳＩｃｈｉｐｆｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｕｓｉｎｇｔｒｅｅｂａｓｅｄｃｏｄｅｓ」（ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＶｅｒｙＬａｒｇｅＳｃａｌｅＩｎｔｅｇｒａｔｉｏｎ（ＶＬＳＩ）Ｓｙｓｔｅｍ、１（２）：２０３−２１４、Ｊｕｎｅ１９９３）に提案されている。
【００１７】
特に効率的というわけではないが、ハフマン・コードをデコードするための別のアプローチが、ハフマン・テーブルのそれぞれのエントリを入力バッファ内の入力ビットと比較することである。このアプローチでは、最悪の場合、エンコーディング・テーブル内のＮエントリが比較される。ここで、Ｎとはシンボルの総数である。その上、そのエントリのためのコード長情報は周知である。
【００１８】
データ構造を使用して一連のバイナリ・デジタル信号をデコードする方法の一実施形態では、以下のアプローチを用いることができる。データ構造を、デコードされているサブグループのバイナリ・デジタル信号の長さに少なくとも部分的に基づいてサーチできる。この特定の実施形態では、エンコードされるハフマンなどの一連のバイナリ・デジタル信号がエンコードされるが、本発明の範囲は、ハフマン・コーディングまたはデコーディングに限定されるものではない。この特定の実施形態では、本発明の範囲がこの点に限定されるものではないが、サーチする前に、系列内の第１のＮバイナリ・デジタル信号はサブグループとして選択される。ここで、Ｎとは最短コードの長さである。さらに、サブグループの長さが、長さＮを有するデータ構造内のコードがそのサブグループに一致しない場合は、系列内の次のバイナリ・デジタル信号によって増加される。同様に、このアプローチが用いられるこの特定の実施形態では、サブグループと同じ長さを有するデータ構造内の全コードが、一致するかどうかチェックされる。以下にさらに詳細に記述するが、データ構造は、少なくとも部分的に、コード長に基づいて構成されることに留意されたい。さらに、データ構造は、同じコード長を有するコードが順次に格納されるように構成される。
【００１９】
本発明の範囲がデータ構造のこの特定の実施形態に限定されるものではないが、この特定の実施形態は、テーブル内に冗長を示すためにいくつかのシンボルを再配置した後の、図３のハフマン・コード・テーブルに関係することがある。このことは、たとえば、図６に例示してある。たとえば、ハフマン・コード長ゼロを有するシンボルとは、これらのシンボルが用いられないということである。同様に、上記の第１の制約に基づき、所与のビット長のすべてのコードが、辞書式順序で連続した値を有する。したがって、長さ情報を追跡することにより、この長さのハフマン・コードを有する辞書式順序の第１のシンボルのハフマン・コード、および同じ長さを有する最後のシンボルまでのハフマン・コードの数のハフマン・コードが情報の冗長がほとんどない情報を提供する。
【００２０】
データ構造のこの特定の実施形態が、図７に示してある。図７は図６と同じ情報を有するが、話を簡単にするためおよび使用しやすくするために再配置してあることに留意されたい。したがって、図７はより少ないメモリを用いており、以下にさらに詳細に記述するように、ビット・パラレル・デコーディング・スキームが適用できる。
【００２１】
図７に例示したデータ構造の実施形態では、図７の実施形態で示したように、ハフマン・コードのデコーディングを、それぞれのコード長のためのハフマン・コードのコード長および範囲についての情報に少なくとも部分的に基づいて、ビット・パラレル・アプローチで実施できる。このことは、擬似コードの実施を使用して以下に例示し記述する。繰り返すが、本発明の範囲が提供される特定の擬似コードに限定されるものではない。
【００２２】
この状況では、合成データ構造をＮＤＳ（ＮＤＣ）と呼ぶ。これは、プログラミング言語Ｃのための合成データ構造の定義に対応するが、本発明の範囲がこのプログラミング言語または特定のプログラミング言語に限定されるものではない。この特定の実施形態では、繰り返すが、本発明の範囲がこの点に限定されるものではないが、この特定の実施形態では、ＮＤＳのそれぞれのエントリが、図７に示されているように、４つのフィールド、つまりそれぞれ、指定された長さ、開始コード、終了コード、ベース・インデックスを有する。もちろん、開始コードおよび終了コードではなく、開始コードおよび開始コードと終了コードとの差を用いることなどの、多くの均等データ構造が可能であることが理解されよう。
【００２３】
しかし、この特定の実施形態では、ＮＤＣは、互いに異なったコード長を有するエントリの数である。それぞれのエントリが、同じコード長を有する１グループの連続したハフマン・コードを表す。開始コードはこのグループの第１のハフマン・コードであり、終了コードはこのグループの最後のハフマン・コードである。図６に示されているように、ベース・インデックスは、対応するシンボルのためのハフマン・テーブル内の第１のハフマン・コードのインデックス値である。上記に表示したように、本発明の範囲は、この特定のデータ構造に限定されるものではないことに留意されたい。この特定のデータ構造に対する多くの修正形態が可能であり、上記に記述してきた内容の趣旨および範囲内に含まれることは明らかである。
【００２４】
図７に例示したデータ構造の実施形態を用いて、一連のバイナリ・デジタル信号をデコードするための本発明による一実施形態の擬似コード表示を以下に示す。

【００２５】
この特定の実施形態では、本発明の範囲がこの点に限定されるものではないが、データ構造をサーチする前に、系列内の第１のＮバイナリ・デジタル信号がサブグループとして選択されるが、ここでＮとは最短コードの長さである。次いで、その長さを有するすべてのコードを一致するかどうかチェックする。一致が出現しなかった場合は、サブグループの長さを系列内の次のバイナリ・デジタル信号によって増加させ、次いで、増加した長さを有するコードを一致するかどうかチェックする。このプロセスを一致が出現するまで続行する。上記に注記したように、データ構造が少なくとも部分的にコード長に基づいて構成され、データ構造は、同じコード長を有するコードが辞書式順序で順次格納されるよう構成される。このことにより、所望のままに効率的なオペレーションが可能となる。
【００２６】
一代替実施形態では、最長コードでサーチを開始し、一致が出現しなかった場合は、サブグループの長さを減少させることが可能であることに留意されたい。しかし、通常、より短いハフマン・コードがより高い出現確率を有するために、このような状況では最短コードからサーチを開始することがより効率的である。
【００２７】
一連のバイナリ・デジタル信号をデコードする方法のこの特定の実施形態は、メモリの利用、計算の複雑さおよび実施の面で、いくつかの利点を有する。上記に提案したように、データ構造のためのエントリの数は、シンボルの数ではなく、ハフマン・コードのための最大コード長に依存する。したがって、このことによりメモリが削減される。たとえば、ＧＺＩＰなどの固定限度コード長を用いる応用例の場合、代表的なハフマン木が２８５シンボルを有し、コード長は１５ビットに制限される。それと対称的に、この実施形態のために用いるエントリの数は、データによって異なるが、せいぜい１５エントリを有し、その結果この例では、１９ｘメモリ利用の削減が生じる。
【００２８】
同様に、ビット・シリアル・サーチ・プロセスではなく、ビット・パラレル・サーチ・プロセスを使用することにより、計算の複雑さが減少される。ここで、この実施形態は、少なくとも部分的にデータ構造内のコード長情報に基づく。そのコード長を有するグループのための開始および終了コードの範囲をチェックすることにより、既存アプローチに比べてサーチ手順が向上する。１９シンボルおよび７ビットの最大コード長を用いるこの実施形態の実験結果から、ハフマン・コード・テーブルのサーチを用いるデコーディングと比較して、複雑さの点で５．５倍削減される。同様に、ハフマン木が構築される場合に生じるような２分木の構築が起きないために、かつ動的なメモリ割当がほとんどまたは全くないために、ハードウェアとソフトウェアの両方で、本発明によるデコーディングの実施が比較的簡単となる。
【００２９】
特定の実施形態のみを記述してきたが、本発明の範囲が特定の実施形態または実装形態に限定されるものではないことが、もちろん、理解されるであろう。たとえば、一実施形態はハードウェアでなされ、別の実施形態はソフトウェアでなされるてもよい。同様に、一実施形態が、たとえば、ファームウェア、あるいはハードウェア、ソフトウェア、またはファームウェアの組合せでもよい。同様に、本発明の範囲がこの点に限定されるものではないが、一実施形態が、記憶媒体などの製品を備えることができる。たとえば、ＣＤ−ＲＯＭやディスクなどの記憶媒体が、それに命令を格納していることがあり、コンピュータ・システムやプラットフォームまたは画像作成システムなどのシステムによって実行された場合、その結果、たとえば、上記に記述したようなハフマン・デコーディングを実施する方法などの、本発明による方法の一実施形態を実行できる。同様に、データ構造を作成する方法の実施形態を、本発明に従って実行できる。
【００３０】
本発明のある特徴について、本明細書に例示し記述してきたが、当業者には、多くの修正形態、置換形態、変更形態、均等物が考えられるであろう。したがって、頭記の特許請求の範囲は、すべてのこのような修正形態および変更形態を、本発明の真の趣旨内に入るものとして、包含することを意図することを理解されるであろう。
【図面の簡単な説明】
【図１】ハフマン木構築および関連するハフマン木の一例を示す図である。
【図２】図１のハフマン木のための可能なハフマン・コードを示す表である。
【図３】選択されたルールを適用して、一意的にハフマン・コードを判断するハフマン・コードの一例を示す表である。
【図４】対応するデコーディング木を有するハフマン・エンコーディング・テーブルの一例を示す図である。
【図５】ビット・シリアル・ハフマン・デコーディングのための読取専用メモリ（ＲＯＭ）エントリを示す表である。
【図６】異なる構成が適用されている、図３の表からの情報を使用する表である。
【図７】本発明によるデータ構造の一実施形態を示す表である。[0001]
(Related application)
This patent application is related to co-filed US patent application 09 / 704,392, “A Method of Generating Huffman Code Length Information” (Attorney Docket No. 042390, P9804) by Acharya et al. Assigned to the assignee of the present invention and incorporated herein by reference.
[0002]
(background)
The present disclosure relates to Huffman decoding.
[0003]
As is well known, Huffman coding is a popular variable length statistical encoding scheme. As is also well known, the generation of Huffman codes relies on statistical probabilities for each individual symbol. For example, D.C. A. See “A Method for the Construction of Minimum Redundancy Codes” by Huffman (Proceedings of the IRE, Volume 40, No. 9, pages 1098 to 1101, 1952). Conventional table lookup-based encoding schemes are widely used for Huffman encoding because they are at least partially efficient and relatively easy to implement. However, table search based decoding is usually inefficient in terms of both software and hardware implementations. This is especially true when the number of entries in the table is quite high, as is typical for practical applications. Another approach used for Huffman decoding is the generation of a Huffman tree using a “tree traversal technique”. However, this decoding technique also has drawbacks. This particular technique is bit sequential and introduces extra “overhead” in both memory allocation and computation execution for the Huffman tree generation process and for the decoding process.
[0004]
The subject matter believed to be the invention will be described in detail and expressly claimed in the concluding portion of the specification. However, the present invention will be best understood by reference to the following detailed description taken in conjunction with the accompanying drawings, both in terms of methods of construction and operation, and their objects, features, and advantages.
[0005]
(Detailed explanation)
In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, one of ordinary skill in the art appreciates that the invention may be practiced without these specific details. In other instances, well known methods, procedures, components, and circuits have not been described in detail as not to obscure the meaning of the present invention.
[0006]
As indicated above, the generation of the Huffman code for a set of symbols is based on the appearance probability of the source symbols. Usually, a binary tree construction called a Huffman tree is used in this situation. In the above document, D.C. A. Huffman describes the process in this way.
• List all possible symbols along with their probabilities.
Find the two symbols with the lowest probability.
Replace these with a single set containing both symbols whose probability is the sum of the individual probabilities.
Repeat until the list contains only one member.
This procedure creates a recursively structured set of sets, each of which contains exactly two members. It can therefore be represented as a binary tree (“Huffman tree”) with the symbol as “leaf”. The binary tree is then traversed from the root to that symbol to form a code for a particular symbol (“Huffman code”), with “0” on the left branch and “1” on the right branch. Record. However, one problem with this procedure is that the resulting Huffman tree is not unique. An example of such a code application is text compression such as GZIP. GZIP is a text compression utility developed under the GNU (Gnu's Not Unix) project with the goal of developing an operating system such as "free" or freely available UNIX (R) Yes, to replace the “compress” text compression utility on the UNIX operating system. For example, gzip-1.2.4. On the website “http: //www.gzip.orh/”. Gary, J., available as tar. L. And Adler, M .; See "GZIP documentation and sources".
[0007]
As is well known, the resulting Huffman code is a prefix code, where fewer symbols are assigned to more frequently occurring symbols to form a variable length Huffman code. As a result, since the symbol appearance frequency is used, the average code length is finally reduced.
[0008]
FIG. 1 is a diagram illustrating a simple example of a Huffman tree having three source symbols. By assigning different binary symbols to the edge of the tree, several binary codes can be used to represent the same Huffman tree.
[0009]
A possible set of Huffman codes for this Huffman tree is illustrated in FIG. FIG. 2 shows that the Huffman code is not unique, but from this example, it appears that the individual code length of each symbol is unique.
[0010]
Huffman code length information can be generated by constructing a corresponding Huffman tree. However, as indicated above, Huffman codes are not unique when generated in this manner. However, it can be seen that by imposing two constraints, it is possible to guarantee that the Huffman code created using the Huffman tree is unique.
These constraints are
1. All codes of a given bit length have consecutive values in lexicographic order, in the same order as the symbols they represent.
2. Shorter codes precede lexicographic order than longer codes.
[0011]
Based on these constraints, the Huffman code can be uniquely determined. FIG. 3 shows, for example, a 19-symbol Huffman code set using these constraints, where the code length is pre-determined using a Huffman tree. For the table of FIG. 3, the dash in the entry in the Huffman code table indicates that there is no symbol and no code in the current source alphabet, and its length information is zero.
[0012]
Although the scope of the present invention is not limited in this respect, the constraints described above have been used in various compression approaches and standards such as the utilities described above, GZIP, and the like. Typically in such applications, the Huffman tree information is passed with a set of code length information along with the compressed text data. Therefore, the code length information of the set is sufficient to reconstruct a unique Huffman tree. For example, the Huffman code table illustrated in FIG. 3 can be generated using the following process as implemented in GZIP.
[0013]
The code length is initially length [l].
1) Count the number of codes for each code length.
The number of codes of length N (N> = 1) is “count [N]”.
2) Find the numerical value of the minimum code for each code length.

3) Assign numerical values to all codes using the consecutive values determined in 2.
[0014]
As indicated above, Huffman encoding can be achieved relatively easily using table lookup techniques. However, decoding of Huffman codes is usually more computationally intensive. This is because when code words are received in a compressed bit stream to be decoded, there are no defined boundaries between the code words. As described above, the Huffman code is a variable length code.
[0015]
One approach or technique, called a constant input rate decoder, serially processes the input bit stream one bit at a time. This method uses decoding or Huffman tree construction. Thus, starting from the root, the technique requires traversing the branches of the decoding tree until the end node is reached. At the end node, the code word is fully decoded so that the corresponding symbol can be created or output as desired. The process then starts again from the tree root. For example, B.I. Bhaskarin and K.K. See "Image and Video Compression Standards: Algorithms and Architectures" (Kluwer Academic Publishers, 1995) by Konstantinides.
[0016]
FIG. 4 is a diagram illustrating an example of a Huffman encoding table having a corresponding decoding tree. One problem associated with such decoders in hardware or software is how to efficiently map the decoding tree to memory. For example, FIG. 5 shows a table of read only memory (ROM) entries for bit serial Huffman decoding using the decoding tree of FIG. One approach to efficiently mapping memory is, for example, “MARVLE: a VLSI chip for data compression used based codes (IEEE Transforms on Very Large Scale)” by Mukherje et al. : 203-214, June 1993).
[0017]
Although not particularly efficient, another approach to decoding the Huffman code is to compare each entry in the Huffman table with the input bits in the input buffer. In this approach, N entries in the encoding table are compared in the worst case. Here, N is the total number of symbols. Moreover, the code length information for that entry is well known.
[0018]
In one embodiment of a method for decoding a series of binary digital signals using a data structure, the following approach may be used. The data structure can be searched based at least in part on the length of the binary digital signal of the subgroup being decoded. In this particular embodiment, a series of binary digital signals, such as Huffman to be encoded, are encoded, but the scope of the present invention is not limited to Huffman coding or decoding. In this particular embodiment, the scope of the present invention is not limited in this regard, but the first N binary digital signals in the sequence are selected as a subgroup before searching. Here, N is the length of the shortest code. Further, the length of the subgroup is increased by the next binary digital signal in the sequence if the code in the data structure having length N does not match that subgroup. Similarly, in this particular embodiment where this approach is used, all codes in a data structure having the same length as the subgroup are checked for a match. Note that, as described in more detail below, the data structure is structured based at least in part on the code length. Further, the data structure is configured such that codes having the same code length are sequentially stored.
[0019]
Although the scope of the present invention is not limited to this particular embodiment of the data structure, this particular embodiment is shown in FIG. 3 after rearranging several symbols to indicate redundancy in the table. May be related to the Huffman code table. This is illustrated, for example, in FIG. For example, a symbol having a Huffman code length of zero means that these symbols are not used. Similarly, based on the first constraint above, all codes of a given bit length have consecutive values in lexicographic order. Thus, by tracking the length information, the Huffman code of the first symbol in the lexicographic order having this length of Huffman code, and the number of Huffman codes up to the last symbol having the same length Huffman code provides information with little information redundancy.
[0020]
This particular embodiment of the data structure is shown in FIG. Note that FIG. 7 has the same information as FIG. 6, but has been rearranged for simplicity and ease of use. Accordingly, FIG. 7 uses less memory and a bit parallel decoding scheme can be applied, as described in more detail below.
[0021]
In the embodiment of the data structure illustrated in FIG. 7, as shown in the embodiment of FIG. 7, the decoding of the Huffman code is converted into information on the code length and range of the Huffman code for each code length. Based at least in part, it can be implemented in a bit parallel approach. This is illustrated and described below using pseudo-code implementation. Again, the scope of the present invention is not limited to the specific pseudo code provided.
[0022]
In this situation, the composite data structure is called NDS (NDC). This corresponds to the definition of a composite data structure for programming language C, but the scope of the invention is not limited to this programming language or a particular programming language. In this particular embodiment, again, the scope of the present invention is not limited in this respect, but in this particular embodiment, each entry in the NDS, as shown in FIG. It has four fields: a specified length, a start code, an end code, and a base index, respectively. Of course, it will be appreciated that many equal data structures are possible, such as using the start code and the difference between the start code and the end code rather than the start code and end code.
[0023]
However, in this particular embodiment, NDC is the number of entries with different code lengths. Each entry represents a group of consecutive Huffman codes having the same code length. The start code is the first Huffman code for this group and the end code is the last Huffman code for this group. As shown in FIG. 6, the base index is the index value of the first Huffman code in the Huffman table for the corresponding symbol. As indicated above, it should be noted that the scope of the present invention is not limited to this particular data structure. Obviously, many modifications to this particular data structure are possible and fall within the spirit and scope of what has been described above.
[0024]
A pseudocode display of one embodiment according to the present invention for decoding a series of binary digital signals using the data structure embodiment illustrated in FIG. 7 is shown below.

[0025]
In this particular embodiment, the scope of the present invention is not limited in this respect, but the first N binary digital signals in the sequence are selected as a subgroup prior to searching the data structure. Here, N is the length of the shortest code. It then checks whether all codes with that length match. If no match appears, the length of the subgroup is increased by the next binary digital signal in the sequence, and then a check is made to see if the codes with the increased length match. Continue this process until a match appears. As noted above, the data structure is configured based at least in part on the code length, and the data structure is configured to sequentially store codes having the same code length in lexicographic order. This allows efficient operation as desired.
[0026]
Note that in an alternative embodiment, if the search is started with the longest code and no match appears, the length of the subgroup can be reduced. However, it is usually more efficient to start the search from the shortest code in this situation, since usually shorter Huffman codes have a higher probability of appearance.
[0027]
This particular embodiment of a method for decoding a series of binary digital signals has several advantages in terms of memory utilization, computational complexity and implementation. As suggested above, the number of entries for the data structure depends on the maximum code length for the Huffman code, not the number of symbols. This therefore reduces the memory. For example, for an application that uses a fixed limit code length such as GZIP, a typical Huffman tree has 285 symbols and the code length is limited to 15 bits. In contrast, the number of entries used for this embodiment depends on the data, but has at most 15 entries, resulting in a reduction in 19x memory utilization in this example.
[0028]
Similarly, computational complexity is reduced by using a bit parallel search process rather than a bit serial search process. Here, this embodiment is based at least in part on the code length information in the data structure. Checking the range of start and end codes for a group with that code length improves the search procedure compared to existing approaches. From the experimental results of this embodiment using 19 symbols and a maximum code length of 7 bits, the complexity is reduced by a factor of 5.5 compared to decoding using a Huffman code table search. Similarly, in accordance with the present invention, both in hardware and software, because there is no binary tree construction as occurs when a Huffman tree is constructed, and there is little or no dynamic memory allocation. Decoding is relatively easy to implement.
[0029]
While only specific embodiments have been described, it will be appreciated that the scope of the invention is not limited to any particular embodiment or implementation. For example, one embodiment may be made in hardware and another embodiment may be made in software. Similarly, an embodiment may be, for example, firmware or a combination of hardware, software, or firmware. Similarly, although the scope of the invention is not limited in this respect, one embodiment may comprise a product such as a storage medium. For example, a storage medium such as a CD-ROM or disk may store instructions on it, and when executed by a system such as a computer system, platform, or image creation system, the result is, for example, as described above. One embodiment of the method according to the present invention can be performed, such as a method of performing Huffman decoding as described above. Similarly, embodiments of a method for creating a data structure can be performed in accordance with the present invention.
[0030]
While certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes and equivalents will occur to those skilled in the art. Accordingly, it will be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating an example of Huffman tree construction and related Huffman trees.
FIG. 2 is a table illustrating possible Huffman codes for the Huffman tree of FIG.
FIG. 3 is a table showing an example of a Huffman code for uniquely determining a Huffman code by applying a selected rule.
FIG. 4 is a diagram illustrating an example of a Huffman encoding table having a corresponding decoding tree.
FIG. 5 is a table showing read only memory (ROM) entries for bit serial Huffman decoding.
FIG. 6 is a table using information from the table of FIG. 3, to which different configurations have been applied.
FIG. 7 is a table showing an embodiment of a data structure according to the present invention.

Claims

A method for decoding a first encoded binary digital signal using a data structure comprising a table having fields each holding a code length, a value representing a start code and an end code, and a base index Because
(A) One of a plurality of second binary digital signals from a start code to an end code obtained from a value representing a start code and an end code regarding the shortest code length of the table, and the first binary digital Determine if the signal matches,
(B) If there is a second binary digital signal that matches the first binary digital signal, it is determined from the matching second binary digital signal and the corresponding base index. Retrieve and store the data stored in the memory location as a decoded value of the first binary digital signal;
(C) If none of the second binary digital signals match the first binary digital signal, repeat steps (a)-(c) for the next short code length and repeat this step A method of outputting a decoded value of the first binary digital signal when a match is found in (1) .

Instructions for decoding a first binary digital signal that is encoded using a data structure with a table having fields each holding a code length, a value representing a start code and an end code, and a base index A storage medium storing
When the instruction is executed,
(A) One of a plurality of second binary digital signals from a start code to an end code obtained from a value representing a start code and an end code regarding the shortest code length of the table, and the first binary digital Let us determine if the signal matches,
(B) If there is a second binary digital signal that matches the first binary digital signal, it is determined from the matching second binary digital signal and the corresponding base index. Extracting and outputting data stored in a memory location as a decoded value of the first binary digital signal;
(C) If none of the second binary digital signals match the first binary digital signal, the process (a)-(c) is repeated for the next short code length, Output a decoded value of the first binary digital signal when a match is found in the process
A storage medium storing instructions for use .