(57)【特許請求の範囲】
【請求項１】
多重サイクルを有するクロック信号に応じて可変長符号語を復号する復号器であって、
ランレングス符号化形式の符号語を表わす順次の可変長符号語の符号語ソースと、
上記符号語ソースに接続され、次に復号化されるべき少なくとも第１の可変長符号語と上記第１の可変長符号語の次に復号化されるべき第２の可変長符号語とを、前記クロック信号に応じて出力端子に生じさせるバレルシフタ回路と、
上記バレルシフタの上記出力端子に接続され、（ａ）の場合でも（ｂ）の場合でも前記クロック信号の単一サイクル内で復号する符号語復号化回路とを有し、
前記（ａ）は、第１及び第２の可変長符号語の各々が０のランのランレングス符号語を表わす場合であり、
前記（ｂ）は、第１の可変長符号語が０のランのランレングス符号語を表わし、第２の可変長符号語が１のランのランレングス符号語を表わす場合であり、
上記符号語復号化回路は、
上記バレルシフタ回路の上記出力端子に接続され、可変長符号語によって表わされるランレングス符号語を表現するデータを発生させる値用ルックアップテーブルと、
上記バレルシフタ回路の上記出力端子に接続され、可変長符号語の長さを表現するデータを発生させる長さ用ルックアップテーブルとを有し、
該長さ用ルックアップテーブルは、
０のランのランレングス符号語を表わす第１の可変長符号語の長さを表現するデータを発生させる第１のルックアップテーブルと、
上記第１の可変長符号語の次に続く、０のランのランレングス符号語と１のランのランレングス符号語の中の一方を表わす第２の可変長符号語の長さを表現するデータを発生させる第２のルックアップテーブルと、
上記の可変長符号語以外の符号語の長さを表現するデータを発生させる第３のルックアップテーブルとを含む、復号器。
【請求項２】
上記符号語復号回路は、０のランのランレングス符号語及び１のランのランレングス符号語以外の可変長符号語を、クロックサイクル毎に１つ復号する、請求項１記載の復号器。
【請求項３】
多重サイクルを有するクロック信号に応じて、ランレングス符号化形式の符号語を表わす順次の可変長符号語を処理する可変長符号語復号器において、可変長符号語を復号化する方法であって、
次に復号化されるべき少なくとも第１及び第２の可変長符号語を、前記クロック信号の単一クロックサイクルで獲得する工程と、
上記第１の可変長符号語が０のランのランレングス符号化された符号語を表わすか否かを、前記クロック信号の単一クロックサイクルで検出する工程と、
上記第１の可変長符号語が０のランのランレングス符号化された符号語を表わしていなかった場合、上記第１の可変長符号語によって表わされた上記ランレングス符号語の長さを第１のルックアップテーブル内で探すこと、及び上記第１の可変長符号語の長さだけ上記順次の可変長符号語をシフトすることにより、次に復号化されるべき少なくとも第１及び第２の可変長符号語を獲得することを、前記クロック信号の単一クロックサイクル内で行う工程と、
上記第１の可変長符号語が０のランのランレングス符号化された符号語を表わしていた場合、上記第１の可変長符号語によって表わされた上記ランレングス符号語の長さを第２のルックアップテーブル内で探すこと、及び上記第２の可変長符号語が０のランのランレングス符号化された符号語と１のランのランレングス符号化された符号語の内の一方の符号語を表わすか否かを検査することを、前記クロック信号の単一クロックサイクル内で行う工程と、
上記第２の可変長符号語が０のランのランレングス符号化された符号語と１のランのランレングス符号化された符号語の内の一方の符号語を表わしていなかった場合、上記第１の可変長符号語の長さだけ上記順次の可変長符号語をシフトすることにより、次に復号化されるべき少なくとも第１及び第２の可変長符号語を獲得する工程と、
上記第２の可変長符号語が０のランのランレングス符号化された符号語と１のランのランレングス符号化された符号語の内の一方の符号語を表わしていた場合、上記第２の可変長符号語によって表わされた上記ランレングス符号語の長さを第３のルックアップテーブル内で探し、上記第２の可変長符号語の長さと上記第１の可変長符号語の長さとを組み合わせ、上記第１及び第２の可変長符号語の組み合わされた長さだけ上記順次の可変長符号語をシフトすることにより、次に復号化されるべき少なくとも第１及び第２の可変長符号語を獲得する工程と
を有する方法。
【請求項４】
上記第１の可変長符号語が０のランのランレングス符号化された符号語を表わしていなかった場合、上記第１のランレングス符号化された符号語の値を、値用ルックアップテーブル内で探す工程と、
上記第１の可変長符号語が０のランのランレングス符号化された符号語を表わしていた場合、上記第１のランレングス符号化された符号語の値を、値用ルックアップテーブル内で探す工程と、
上記第２の可変長符号語が０のランのランレングス符号化された符号語と１のランのランレングス符号化された符号語の内の一方の符号語を表わしていた場合、上記第２のランレングス符号化された符号語の値を、値用ルックアップテーブル内で探す工程と
を更に有する請求項３記載の方法。
【請求項５】
上記第２の可変長符号語が、所定数個の長さの内の一つの長さを有し、
上記第２の可変長符号語の値を探すことが、上記第２の可変長符号語の上記所定数個の長さの内の上記一つの長さを表わすインデックスを探すことにより行われ、
上記第１及び第２の可変長符号語の組み合わされた長さだけ上記順次の可変長符号語をシフトすることにより、次に復号化されるべき少なくとも第１及び第２の可変長符号語を獲得する上記工程が、
上記第１の可変長符号語の長さ分だけ上記順次の可変長符号語を予めシフトする工程と、
予めシフトした順次の可変長符号語を、上記所定数個の上記第２の可変長符号語の長さ各々の分だけさらにシフトしたバージョンを所定数個生成する工程と、
上記インデックスに対応した可変長符号語のシフトしたバージョンを選択する工程と
を含む、請求項３記載の方法。
【請求項６】
上記第２の可変長符号語が、所定数個の長さの内の一つの長さを有し、
上記第２の可変長符号語の値を探すことが、上記第２の可変長符号語の上記所定数個の長さの内の上記一つの長さを表わすインデックスを探すことにより行われ、
上記第２の可変長符号語の長さと上記第１の可変長符号語の長さとを組み合わせる工程が、上記第１の可変長符号語の長さと、上記所定数個の長さの各々とを加算し、上記所定数個の和を求める工程と、上記第１及び第２の可変長符号語の組み合わされた長さとして、上記所定数個の和の中から上記インデックスに対応する一つの和を選択する工程とを含む、請求項３記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ランレングス符号化された係数を符号化する連続可変長符号語を復号化する復号器に関する。特に、本発明は、動画像専門家グループ（ＭＰＥＧ）国際標準に準拠して符号化された高精細テレビジョン（ＨＤＴＶ）ビデオデータ信号内の可変長符号語を復号化するため使用される可変長符号復号器（ＶＬＤ）に関する。
【０００２】
【従来の技術】
米国において、 高精細度テレビジョン信号をデジタル的に符号化する標準が提案されている。この標準は、本質的に、国際標準化機構（ＩＳＯ）の動画像専門家グループ（ＭＰＥＧ）によって提案されたＭＰＥＧ２標準と同一である。以下の説明では、 この標準をＭＰＥＧ標準と呼び、ＭＰＥＧ標準に準拠した信号をＭＰＥＧ又はＭＰＥＧ符号化信号と呼ぶ。 ＭＰＥＧ標準は、ＩＳＯから入手可能であり、参考のため引用された“Information Technology -  Generic Coding  of  Moving  Pictures  and Associated  Audio,  Recommendation  H.262 ISO/IEC 13818.2;  1995(E) ”という名称のドラフト国際標準（ＤＩＳ）刊行物に記載されている。
【０００３】
ＭＰＥＧ２ビデオ信号符号化標準は、画像を表現するビデオ信号を、大部分が離散コサイン変換（ＤＣＴ）係数のブロックから構成されるバイナリ（デジタル）信号に符号化する方式を規定する。これらの係数は、固定サイズのランレングス符号語にランレングス符号化される。各ランレングス符号化された符号語は、次に、可変長符号語にホフマン符号化される。ＭＰＥＧ符号化方式ＨＤＴＶ信号の場合に、ＤＣＴ係数のブロックは、伝送された画像を適切に復号化し表示するため、 所定のレートで復号化されるべきである。この瞬間的なレートは、画像のディテール及び動きに依存して変化し得る。しかし、ランレングス符号化された符号語、すなわち、可変長符号語が最悪ケースの画像に対し生ずる最大レートが存在する。このレートは毎秒１億符号語を上回る。このレートで符号語を復号化するため種々の方法が提案されている。
【０００４】
適当な条件下で複数の可変長符号語を単一のクロックサイクル中に同時に復号化する能力のある可変長復号器が提案されている。従来技術の可変長復号器の場合に、受信された符号化信号の多数のビットは、バレルシフタを介して可変長復号器の復号化部に並列に供給される。このような可変長復号器は並列復号器と呼ばれる。そのビット数は、最大サイズの可変長符号後内のビット数以上になるように選択される。これらのビットは、許容される可変長符号語毎にエントリーが設けられるように予め構成されたルックアップテーブル（ＬＵＰ）に供給される。ルックアップテーブルの各エントリーは、可変長符号語によって表わされたランレングス符号語の値と、可変長符号語の長さ（すなわち、ビット数）とを収容する。符号語が復号化されると共に、新たに復号化された可変長符号語内の並列ビット数は、バレルシフタからシフトされて押し出され、バレルシフタ内の残りのビットは、元の場所にシフトされる。必要ならば、デジタルビットストリーム内の次のビットがバレルシフタに挿入される。次に、バレルシフタ内の残りのビットは、次の符号語を復号化するため処理される。このような可変長復号器は、単一のクロックサイクル中に単一の可変長符号語を復号することができる。
【０００５】
しかし、上記の通り、ＭＰＥＧ符号化方式ＨＤＴＶ信号の場合に、可変長符号語が復号化されるべき最大レートは、毎秒１００万回を超える。このためには、１００ＭＨｚ以上のクロック周波数が必要とされる。この周波数での動作は、目下、消費者電子機器に実現されている集積回路の能力を上回る。かくして、１クロックサイクル毎に２個以上の符号語を復号することができる可変長復号器が提案されている。これにより、上記の回路で必要とされた１００ＭＨｚレート未満のクロック信号レートで動作する可変長復号器を実装することが可能になる。
【０００６】
１９９３年７月６日にWangほかに発行された名称が“High  Speed Variable  Length  Decoder ”である米国特許第５，２２５，８３２号には、並列可変長復号器が記載されている。Wangほかの特許では、可変長符号語は長さが変化するので、２個以上の可変長符号語が、最大サイズの可変長符号語中のビット数の範囲内に収まり得ることが認められている。復号化用ルックアップテーブルは、合成された短い符号語のためのエントリーを更に有する。かくして、２個の短い符号語がバレルシフタの出力に同時に現れるならば、この２個の符号語はルックアップテーブルによって識別され、同時に復号化される。その結果として、可変長復号器は１クロックサイクルあたり１符号語のレートよりも高いレートで復号化することができる。統計学的により短い符号語の方が長い符号語よりも出現する可能性が高いので、１クロックサイクルあたり１符号語を超えるレートの増加量は、さらに大きくなる。このよう復号化レートの増加は、復号化用ルックアップテーブルの複雑さが増大する代償として選られる。
【０００７】
また、２個の最大サイズの可変長符号語を同時に生成するためバレルシフタからの出力の幅を拡張することが提案されている。２倍幅のバレルシフタの出力は、２個の符号語を同時に認識するルックアップテーブルに供給される。ルックアップテーブルの第１部分は、第１の可変長符号語を認識し、ルックアップテーブルの第２部分は、第２の可変長符号語を認識する。ルックアップテーブルは３個の出力値を生成する。その中の第１の値は第１の可変長符号語を表わし、第２の値は第２の可変長符号語を表わし、第３の値は合成された２個の符号語の長さを表わす。このような構成によって、可変長復号器は、実際的な範囲内に巧く収まる約５０ＭＨｚのクロックレートで動作する。しかし、このような構成におけるルックアップテーブルは、１クロックサイクルあたり１個の可変長符号語のレートの場合のルックアップテーブルよりも非常に巨大である。ルックアップテーブルの第１の部分の符号語エントリー毎に、ルックアップテーブルは、第２の部分に対する符号語の完全な集合を調べる回路を含む必要がある。ｎ個の許容された符号語がある場合、ｎ2 個のエントリーが必要である。このため、ルックアップテーブルは大きくなり、動作が遅くなる。
【０００８】
文献：Bakhmutsky, “Pair−Match Huffman Transcoding to Achieve a Highly Parallel  Variable Length Decoder with Two-Word Bit Stream  Segmentation”, SPIE Proceedings, Volume3021，pages247-265には、上記のWangほかによる文献に開示された並列可変長復号器の改良タイプが記載されている。Bakhmutskyの可変長復号器は、１クロックサイクルあたり少なくとも 2個の離散コサイン変換係数を復号化することができる。Bakhmutskyの文献では、可変長復号器の出力が固定長ランレングス符号化方式符号語の系列であり、各符号語は受信された可変長符号語と対応していることが認識されている。各ランレングス符号語は 1個以上の離散コサイン変換（ＤＣＴ）係数を表現し、ラン部分と値部分とを含む。ラン部分は、現在の符号語によって表現された係数よりも前にある零の値を有するＤＣＴ係数の数を表わす。値部分は、零の値をもつ係数のランの後に続く非零のＤＣＴ係数の値を表現する。
【０００９】
単一の可変長符号語によって表わされた０が続くランレングス符号語は、１個の係数値だけ（すなわち、零個の値零の係数）を表現し、単一の可変等符号語によって表わされた１が続くランレングス符号語は、１個の値零の係数と１個の非零の係数からなる２個の係数を表現する。単一の係数を表わす２個の「０のラン」（すなわち、連続した０のつながり）のランレングス符号語を表現する２個の可変長符号語が順番に生起するとき、これらの２個の可変長符号語は、１クロックサイクルあたり２係数の復号化レートを維持するため、単一のクロックサイクル内で同時に復号化されるべきである。また、「０のラン」のランレングス符号（すなわち、１個の係数）を表現する可変長符号語と、その後に続く、「１のラン」（すなわち、連続した１のつながり）のランレングス符号語（すなわち、２個の係数）を表現する可変長符号語は、１クロックサイクルあたり２係数の復号化レートを維持するため、単一クロックサイクル中に同時に復号化されるべきである。このように復号化されない場合、すなわち、各可変長符号語が１クロックサイクル中に別々に復号化される場合、３個の係数（すなわち、１クロックサイクルあたり１．５個の係数）が２クロックサイクル中に復号化され、１クロックサイクルあたり２個の係数の目標には届かない。すべてのケースにおいて、単一の可変長符号語は単一のクロックサイクルで復号化され、１クロックサイクルあたり少なくとも２個の係数の目標は依然として維持され得る。
【００１０】
ＭＰＥＧ符号化方式の場合、任意のランレングス符号語は、最大２４ビット幅までのサイズを有する可変長符号語（たとえば、エスケープシーケンス）によって表現され得る。このサイズは、ＭＰＥＧ可変長符号語が取り得る最大サイズである。かくして、２個の順次の可変長符号語は、４８ビット幅になり得る。Bakhmutskyは、可変長復号器への入力を解析し、２個の順次のコード変換された符号語が可変長復号器のバレルシフタの出力で同時に現れるように、「０のラン」及び「１のラン」のランレングス符号を表現する可変長符号語を、より少ないビット数を有する別々の符号語で置き換えることを提案した。ルックアップテーブルは、コード変換された符号語を認識し、それらを同時に復号化するため修正される。このように、Bakhmutskyのシステムは、２個の順次の「０のラン」のランレングス符号語、又は、「０のラン」のランレングス符号語と後続する「１のラン」のランレングス符号語を表現する２個の可変長符号語を単一クロックサイクルで認識し、復号化し、１クロックサイクルあたり２個の係数の復号化レートを確保することができる。
【００１１】
【発明が解決しようとする課題】
しかし、Bakhmutskyによるシステムは、２個の順次のコード変換された符号語を同時に認識し処理するため、可変長復号器の前の信号路にコード変換器を追加し、可変長復号器のルックアップテーブルを修正することを必要とする。付加的な復号化回路又はコード変換回路を必要とすること無く、かつ、ｎ個の可変長符号語に対し２ｎ個のエントリーが要求されるルックアップテーブルを必要とすること無く、１クロックサイクルあたり少なくとも２個の係数の復号化レートを維持することができるシステムが望ましい。
【００１２】
【課題を解決するための手段】
本発明の原理によれば、可変長符号語の復号器は、多数のサイクルを含むクロック信号に応答し、個々にランレングス符号化された符号語を表現する順次の可変長符号語のソースを含む。バレルシフタ回路は、符号語ソースに接続され、次の未復号化可変長符号語をバレルシフタの出力端子の下位側ビットに供給する。符号語復号化回路は、バレルシフタの出力端子に接続され、「０のラン」のランレングス符号語を表現する２個の順次の可変長符号語を単一クロックサイクル中に復号するよう動作し、又は、「０のラン」のランレングス符号語を表現する第１の可変長符号語と「１のラン」のランレングスを表現する第２の可変長符号とからなる２個の順次の可変長符号語を単一クロックサイクル中に復号し、かつ、他の全ての可変長符号語を単一クロックサイクル中に復号するよう動作する。
【００１３】
【発明の実施の形態】
図１は、本発明による可変長復号器（ＶＬＤ）システム１００のブロック図である。同図には、本発明の実現法と動作を理解するために必要な構成要素だけが図示されている。当業者は、他の構成要素が必要であること、並びに、他の構成要素の設計法、実現法及び図示された構成要素との接続法が解るであろう。特に、多数のサイクルを有するクロック信号ソースは図示されていない。同図に示された実施例において、クロック信号は、公知の方法で図示された構成要素に供給され、約５０ＭＨｚのレートで繰り返すクロックサイクルの系列の形式である。以下に詳述するように、本発明によるこの復号器は、最低でもＭＰＥＧ２符号化標準に準拠する毎秒１００万回のレートで係数を復号することができる。
【００１４】
図１を参照するに、可変長符号語ソース１０は、可変長符号語の系列を生成する。符号語ソース１０は、従来の方法で構成された無線周波信号の受信及び処理回路と、デジタル信号処理回路とを含む。符号語ソースの出力には、先入れ先出し（ＦＩＦＯ）メモリ出力バッファ（図示しない）が従来通りに設けられる。符号語ソース１０の出力端子は、バレルシフタ回路２０のデータ入力端子に接続される。バレルシフタ回路２０は、たとえば、レジスタ装置、状態機械、順序回路、構成可能な論理アレイ、又は、バレルシフト機能を実行するようプログラムされたプロセッサのような従来の装置構成によって実現される。バレルシフタ回路２０の出力端子は、符号語長さ用ルックアップテーブル（ＬＵＴ）３０の入力端子と、符号語値用ルックアップテーブル（ＬＵＴ）４０の入力端子とに接続される。符号語長さ用ルックアップテーブル３０及び符号語値用ルックアップテーブル４０は、組み合わされて、符号語復号器を形成する。長さ用ルックアップテーブル３０の出力端子はバレルシフタ回路２０の制御入力端子に接続される。符号語値用ルックアップテーブル４０の出力端子は、固定長ランレングス符号化符号語のシーケンスを生成し、利用回路５０の入力端子に接続される。利用回路５０は、ランレングス符号復号器と、デジタル信号処理回路とを含む。利用回路５０は、画像表示装置と、スピーカーのようなオーディオ再生装置と、上記デジタル信号処理回路に応答する回路とを有し、この回路は、従来の方法で、画像表示装置に表示されるべき画像、及び、オーディオ再生装置で再生されるべきサウンドを表現する信号を発生する。
【００１５】
動作中に、図１に示された可変長復号器１００は、符号語ソース１０から可変長符号語の系列を受信する。バレルシフタ回路２０は、多数のビットを並列に受信する。図示された実施例の場合に、以下に詳述するような方法で、１５９ビットが符号語ソース１０からバレルシフタ回路に供給される。バレルシフタ２０の出力も並列した多数のビットである。このビット数は、次に復号化されるべき少なくとも第１の可変長符号語と、第１の可変長符号語の後に復号化されるべき第２の可変長符号語とを同時に収容するために十分な数である。図示された実施例の場合に、バレルシフタ２０は、以下に詳述するような方法で２４ビットずつの二つのエスケープシーケンスを同時に供給することができる４８ビットを生成する。
【００１６】
バレルシフタ回路２０は、次に復号化されるべき第１の可変長符号語をバレルシフタ回路２０の出力端子の一方端で常に保持し、第２の可変長符号語を第１の可変長符号語に隣接したバレルシフタ回路２０の出力端子内の場所で常に保持するよう動作する。バレルシフタ回路２０の端側の第１の符号語は、長さ用ルックアップテーブル３０及び値用ルックアップテーブル４０によって認識され、復号化される。長さ用ルックアップテーブル３０は、認識された符号語の長さを表わす出力を発生する。値用ルックアップテーブル４０は、認識された可変長符号語に対応した固定長のランレングス符号語を表わす出力を発生する。符号語が復号化されたとき、バレルシフタ回路２０は長さ用ルックアップテーブル３０からの長さ信号に応答し、復号化された符号語の長さ分だけバレルシフタ回路２０の出力をシフトさせるので、復号化されるべき次の符号語はバレルシフタ回路２０の出力端子の端側に発生される。
【００１７】
長さ用ルックアップテーブル３０及び値用ルックアップテーブル４０は、以下により詳細に説明されるような形で、第１の可変長符号語及び第２の可変長符号語が個々に「０のラン」のランレングス符号語を表わすときを認識するよう構成される。「０のラン」のランレングス符号語を表わすときが認識された場合に、長さ用ルックアップテーブル３０は、２個の可変長符号語の合成長を表わす信号を生成し、値用ルックアップテーブル４０は、２個の固定長の「０のラン」のランレングス符号語を表わす２個の連続した値を生成する。長さ用ルックアップテーブル３０及び値用ルックアップテーブル４０は、以下に詳述されるような形で、第１の可変長符号語が「０のラン」のランレングス符号語を表わし、第２の可変長符号語が「１のラン」のランレングス符号語を表わすときを認識するよう構成される。認識できたとき、長さ用ルックアップテーブル３０は２個の可変長符号語の合成長を表現する信号を生成し、値用ルックアップテーブル４０は、２個の固定長ランレングス符号語を表わす２個の連続した値を生成する。
【００１８】
上記の通り、「０のラン」の二つのランレングス符号語、又は、「０のラン」のランレングス符号語及び「１のラン」のランレングス符号語を表現する順次の可変長符号語を同時に認識することによって、１クロックサイクルあたり少なくとも２個のＤＣＴ係数のレートは、可変長復号器とランレングス復号器（図示しない）の組み合わせにより維持される。図１の可変長復号器１００は、１クロックサイクルあたり２個の係数の符号化レートを維持するので、１００ＭＨｚの符号語クロックレートの略半分のクロックレートで動作し得る。図示された実施例の場合に、可変長復号器１００は５４ＭＨｚのクロックレートで動作し、消費者電子機器に適切な集積回路技術の動作範囲内に巧く収まる。また、図示された実施例ではコード変換器は必要とされない。
【００１９】
図２は、図１に示された可変長復号器システムの一部分の詳細なブロック図である。図２において、図１の構成要素と同じ構成要素は同じ番号で参照され、これ以上の詳細な説明は行わない。また、図面を簡単化するため、本発明を理解するために必要な構成要素だけが図示されている。当業者には、図示された構成要素を相互接続し、それらの動作を同期させるために必要となる他の構成要素（たとえば、レジスタ、フリップフロップ、クロック信号など）と、これらの他の構成要素の実現法と、これらの他の構成要素を図示された構成要素に接続する方法が明らかである。
【００２０】
図２において、符号語ソース１０の出力端子は、レジスタセット２２の入力端子に接続される。レジスタ２２の出力端子は第１バレルシフタ２４の入力端子に接続される。第１バレルシフタ２４の出力端子は第２バレルシフタ２６の第１の入力端子に接続される。第２バレルシフタ２６の出力端子はレジスタ２７の出力端子に接続される。レジスタ２７の出力端子は、長さ用ルックアップテーブル３０の入力端子と、第２バレルシフタ２６の第２の入力端子とに接続される。長さ用ルックアップテーブル３０の出力端子は第２バレルシフタ２６の制御入力と、アキュムレータ２８の入力端子とに接続される。アキュムレータ２８の第１の出力端子は第１バレルシフタ２４の制御入力端子に接続され、アキュムレータ２８の第２の出力端子は、レジスタ２２の制御入力端子及び符号語ソース１０の制御入力端子に接続される。
【００２１】
動作時に、レジスタ２２は、符号語ソース１０からデータを受信するよう動作し、１５９ビットを並列的に第１バレルシフタ２４に供給する。本実施例の場合に、符号語ソース１０の先入れ先出しバッファ（図示しない）の出力端子は、並列に６４ビットを発生する。第１及び第２のカスケード型６４ビット並列レジスタ（図示しない）は、符号語ソース１０の出力に接続される。レジスタの合成出力は、最終的に１２８ビットを生ずる。レジスタ２２の範囲内で、符号語ソース１０の先入れ先出しバッファの出力に直結した付加的な３１ビットは、第１及び第２のレジスタからの１２８ビットと組み合わされ、レジスタ２２から第１バレルシフタ２４に向かう１５９ビットの並列信号が形成される。アキュムレータ２８（以下、詳述される）からの読み出し制御信号に応じて、第１のレジスタからの出力は第２のレジスタにラッチされ、符号語ソース１０の先入れ先出しバッファ（図示しない）からの６４ビットの完全な出力は第１のレジスタにラッチされ、これらの６４ビットは先入れ先出しバッファからシフトによって押し出され、先入れ先出しバッファの出力に次の６４ビットの可変長符号語を生成する。
【００２２】
第１バレルシフタ２４及び第２バレルシフタ２６は、一体的に動作して、次の未だ復号化されていないビットを長さ用ルックアップテーブル３０の入力端子の下位側ビットに供給する。より詳細には、第２バレルシフタ２６は、次の未だ復号化されていないビットが出力端子の下位側ビットに与えられるように制御される。第１バレルシフタ２４は、符号語ソース１０からの１５９ビットを、第２バレルシフタ２６内で未だ復号化されていないビットの後縁と整列させるように動作する。
【００２３】
本実施例において、第１バレルシフタ２４の出力端子は４８ビットを生成する。第１バレルシフタ２４からの４８ビットは第２バレルシフタ２６の第１入力端子に供給される。第２バレルシフタ２６の出力端子は４８ビットを生成する。上記の通り、この４８ビットは２個の最大可変長符号語を収容するために十分である。したがって、第２バレルシフタ２６は、第１の入力端子と第２の入力端子とを併せて９６ビットを受信する。
【００２４】
各クロックサイクルの最後に、第２バレルシフタ２６の出力端子からの４８ビットはレジスタ２７にラッチされる。各クロックサイクルの最初に、前のクロックサイクルからの第２バレルシフタ２６の内容を表現するレジスタ２７からのビットは、第２バレルシフタ２６の第２の入力端子にフィードバックされ、入力の下位側ビットを形成し、次のクロックサイクルで処理される。同時に、前のクロックサイクルで復号化された可変長符号語の長さは、長さ用ルックアップテーブル３０から第２バレルシフタ２６の制御入力端子に供給される。第２バレルシフタは、第１及び第２の入力端子で、制御入力端子で指定された量ずつビットをシフトさせ、先に復号化されたビットをシフトによって掃出し、次の未だ復号化されていないビットが出力端子の下位側ビットに残される。第２バレルシフタ２６への入力は、レジスタ２７からの４８ビットと第１バレルシフタ２４からの４８ビットとを併せた９６ビットであるため、第２バレルシフタ２６からの出力は常に少なくとも４８個の有効データビットを有する。
【００２５】
第１バレルシフタ２４は、レジスタ２２からの新しいデータを、第２バレルシフタ２６からの未だ復号化されていないデータの後方のビットと整列させるように動作する。可変長符号語が、長さ用ルックアップテーブル３０によって認識され、復号化されると共に、復号化された符号語の長さはアキュムレータ２８に供給され、アキュムレータは、従来の方法でその長さをすでに累算された長さに加算する。累算された長さデータは第１バレルシフタ２４の制御入力端子に供給される。第１バレルシフタ２４は、そのデータを累算された可変長符号語の長さの量だけシフトする。これにより、第１バレルシフタ２４からのデータは、第２バレルシフタ２６内の未だ復号化されていない後縁と整列される。レジスタセット２２の第２レジスタ（図示しない）からのビットが完全に復号化される毎に、アキュムレータ２８は、上記の方法で、符号語ソース１０から次の語をラッチするため、読み出し信号をレジスタ２２及び符号語ソース１０に送出する。
【００２６】
最悪ケースの状況は、レジスタセット２２の出力にただ一つの復号化されていないビットが残され、２４ビット長の２個の符号語が復号化されたときに生ずる。この場合、バレルシフタ２４は、１１１ビット、すなわち、第２のレジスタを埋めるための６３ビットと、復号化された符号語内の４８ビットとを加えたビット数だけ入力をシフトさせる必要がある。第１バレルシフタ２４が１１１ビットだけシフトしたとき、 有効な４８ビット出力が第２バレルシフタ２６に供給されるように上位側のビットに少なくとも４８ビットが必要である。このため、第１バレルシフタ２４への入力は、最悪ケースのシフト数１１１と、第２バレルシフタ２６への出力用の４８ビットを加えた１５９ビットである。
【００２７】
図３は、 図１に示された可変長復号器システムの一部分のより詳細なブロック図である。図３において、図１に示された構成要素と同一の構成要素は同じ番号で参照され、 ここでは、これ以上の説明を加えない。図３において、 長さ用ルックアップテーブル３０の出力端子は加算装置２８２の加数入力端子に接続される。加算装置２８２の加算出力端子は、Ｄフリップフロップ２８４のＤ入力に接続される。Ｄフリップフロップ２８４のＱ出力端子は、同期論理回路２８６の入力端子と、第１バレルシフタ２４の制御入力端子と、加算装置２８２の被加算数入力端子とに接続される。同期論理回路２８６の出力端子はレジスタセット２２の制御入力端子に接続される。
【００２８】
動作時に、加算装置２８２と、Ｄフリップフロップ２８４と、同期論理回路２８６の組み合わせは、図２に示されたアキュムレータ２８として動作する。第２バレルシフタ２６（図３には図示されない）は最大で４８ビットをシフトするので、制御入力は６ビットが必要であり、 その結果として、長さルックアップテーブル３０は、６ビットの長さ信号を生成する。６ビットの出力信号は、第２バレルシフタ２６（図２）及び加算装置２８２に供給される。加算装置２８２の加算出力端子は、７ビットの出力信号を生成する。この７ビットの出力信号は７ビット幅のＤフリップフロップ２８４に保存される。この信号は、加算装置２８２の被加算数入力端子に再び戻され、 ７ビットのアキュムレータを形成する。Ｄフリップフロップ２８４の出力は第１バレルシフタ２４の制御入力端子に接続され、最大１２８ビットまでのシフトされるビット数を制御する。なお、 すでに説明したとおり、１１１ビットを超えるシフトは必要とされない。Ｄフリップフロップ２８４からの最上位ビット（ＭＳＢ）は、第１バレルシフタ２４によってシフトされた量が６４を超えたときに活性化される。本例の場合に、レジスタセット２２及び符号語ソース１０（図３には図示されず）は、既に詳述したように、符号語ソースの先入れ先出しバッファから新しい値を取り出す。
【００２９】
もう一度図２を参照するに、 １クロックサイクル毎に２個の「０のラン」、又は、 １個の「０のラン」と１個の「１のラン」のランレングス符号語を表現する２個の順次的な可変長符号語を同時に復号化することによって、復号化の処理レートを１クロックサイクルあたり少なくとも２係数に維持するため、 １クロックサイクル内で処理を終了しなければならない図示された可変長復号器には、３本の重要なパスが示されている。第１のパスは、１５９ビットの入力端子から第２バレルシフタ２６と４８ビットのレジスタ２７とを経由して第１バレルシフタ２４に達するパスである。第２のパスは、４８ビットのレジスタ２７から、長さ用ルックアップテーブル３０と、加算装置２８２とを介して、７ビット・アキュムレータのＤフリップフロップ２８４に達するパスである。第３のパスは、４８ビットのレジスタ２７から、第２バレルシフタ２６を介して、４８ビットのレジスタ２７に戻るパスである。３本のパスが１クロックサイクル内で動作できるように、本発明は、以下に説明するような回路の最適化を提案する。
【００３０】
第１の最適化において、長さ用ルックアップテーブル３０は、図１に示されるように値ルックアップテーブル４０から分離される。この方法によれば、論理最適化は、可変長符号語をその長さに応じて分類するため、長さ用ルックアップテーブル３０に適用される。長さ用ルックアップテーブル３０内のエントリーの数は減少し、待ち時間は対応して減少する。
【００３１】
また、長さ用ルックアップテーブル３０は、２個の「０のラン」ランレングス符号語、又は、１個の「０のラン」ランレングス符号語と後続の１個の「１のラン」ランレングス符号語とを表す連続的な可変長符号語を認識し復号化する部分と、他のすべての可変長符号語を認識し復号化する部分とに分離される。このことが図４に示されている。
【００３２】
図４において、 レジスタ２７（図４には図示せず）の出力端子は長さ用ルックアップテーブル３０の入力端子３５に接続され、入力端子３５はレジスタ２７から可変長符号語（ＣＷ）を含むデータを受信する。入力端子３５は、単一符号語復号化用ルックアップテーブル３２に接続される。単一符号語復号化用ルックアップテーブル３２の出力端子は出力端子３１に接続される。入力端子３５は、「０のラン」符号語検出用ルックアップテーブル３４２と、「０のラン」符号語インデックス用ルックアップテーブル３４４と、「０のラン」符号語長さ用ルックアップテーブル３４６と、第３バレルシフタ３４８とに接続される。「０のラン」符号語検出用ルックアップテーブル３４２の出力端子及び「０のラン」符号語インデックス用ルックアップテーブル３４４の出力端子は、第３バレルシフタ３４８の制御入力端子に接続される。第３バレルシフタ３４８の出力端子は、「０のラン」及び「１のラン」符号語検出用ルックアップテーブル３５０の入力端子と、「０のラン」及び「１のラン」符号語インデックス用ルックアップテーブル３５２の入力端子とに接続される。「０のラン」及び「１のラン」符号語インデックス用ルックアップテーブル３５２の出力端子は、ゲート３５４のデータ入力端子に接続され、 「０のラン」及び「１のラン」符号語検出用ルックアップテーブル３５０の出力端子はゲート３５４の制御入力端子に接続される。ゲートの出力端子は長さ用ルックアップテーブル３０の出力端子３３に接続される。「０のラン」長さ用ルックアップテーブル３４６の出力端子は長さ用ルックアップテーブル３０の出力端子３７に接続される。
【００３３】
動作時に、単一符号語復号化用ルックアップテーブル３２は、従来より知られた方法で、１個以上のランを有する固定長ランレングス符号化方式符号語を表す入力端子３５からの可変長符号語ＣＷを復号化し、復号化された符号語の長さを表す信号を出力端子３１に発生させる。「０のラン」長さ用ルックアップテーブル３４６は、「０のラン」ランレングス符号語を表す入力端子３５からの可変長符号語を復号化し、その符号語の長さを表す信号を出力端子に発生させる。図５には、「０のラン」符号語長さ用ルックアップテーブル３４６の内容を表すテーブルが示されている。左側の欄は、レジスタ２７（図２）からの入力符号語ＣＷの内容を示す。記号ダッシュ（“−”）は“ドントケア”ビットを表す。右側の欄は認識された「０のラン」ランレングス符号語の長さを表す。このテーブルは比較的小さいので、 このデータはかなり短い待ち時間だけを生じ、クロックサイクルの早い段階で得られる。
【００３４】
「０のラン」又は「１のラン」ランレングス符号語を表す次の順番の符号語を復号化するため、入力端子からの符号語ＣＷは、「０のラン」符号語用ルックアップテーブル３４６によって認識された符号語の幅だけシフトされる必要があり、その結果として、 次の符号語は下位側ビットを使用する。第３バレルシフタ３４８はこのシフトを実行する。第３バレルシフタ３４８は、「０のラン」ランレングス符号語が「０のラン」符号語長さ用ルックアップテーブル３４６によって認識され、「０のラン」符号語が検出されたときに限り動作する。上記の通り、このような符号語の長さの種類の数は限られている。そのため、待ち時間を短縮するため、 第３バレルシフタ３４８はマルチプレクサとして実装される。例えば、 本例の場合に、「０のラン」ランレングス符号語を表現する符号語には１３種類の長さしか存在しないことが解った。したがって、第３バレルシフタ３４８を形成するマルチプレクサは、１３個の入力を有するマルチプレクサで十分である。「０のラン」符号語インデックス用ルックアップテーブル３４４は、「０のラン」符号語に対し起こり得る長さ毎に１ビットずつの合計１３ビットの出力信号を、すなわち、復号化されたフォーマットで出力信号を生成する。このテーブルの構造は図５に示されたテーブルの構造と類似している。テーブルからの出力は１３ビットであり、その中の１ビットは同じ長さを有するすべての符号を表す。当業者であれば、このような出力を得るために図５のテーブルを変更する方法が解るであろう。
【００３５】
さらに、「０のラン」符号語検出用ルックアップテーブル３４２は、入力端子３５の符号語が「０のラン」符号語であることを示すため、 １ビットの出力を生ずる。このテーブルの構造は、出力が１ビットであって、リストに掲載されたすべてのエントリーに対し“１”であり、その他の場合に“０”である点を除いて、 図５のテーブルの構造と類似している。当業者であれば、このような出力を得るため、図５のテーブルを変更する方法が解るであろう。「０のラン」インデックス用ルックアップテーブル３４４からの制御信号は復号化されたフォーマットであるため、第３バレルシフタ３４８を形成するマルチプレクサは、 １３バンクのＡＮＤゲートとして実装してもよい。ＡＮＤゲートの各バンクは、所定のビット数で入力をシフトさせるように構成され、「０のラン」符号語インデックス用ルックアップテーブル３４４からのビットの中の１ビット、及び、 「０のラン」符号語検出用ルックアップテーブル３４２からの「０のラン」符号語検出ビットによってイネーブル状態にされる。第３バレルシフタ３４８は、このように製作することによって短い待ち時間で動作する。
「０のラン」及び「１のラン」符号語インデックス用ルックアップテーブル３５２は、第３バレルシフタからのシフトされた符号語ＣＷにおいて「０のラン」又は「１のラン」のいずれかの第２の順番の符号語を検出する。また、第２の符号語は、起こり得る長さの種類の数に制限がある。そのため、「０のラン」及び「１のラン」符号語インデックス用ルックアップテーブル３５２は、復号化されたフォーマットでインデックス信号を発生し、インデックス信号の各ビットはこの第２の符号語のそれぞれの長さを表現する。図６は、「０のラン」及び「１のラン」インデックス用ルックアップテーブル３５２の内容を表現するテーブルである。図６において、記号ダッシュ“−”は「ドントケア」ビットを表わす。図示された実施例の場合に、１４通りの第２の符号語の長さが起こり得る。「０のラン」及び「１のラン」インデックス用ルックアップテーブル３５２からの出力信号は、１４ビットを含む。「０のラン」及び「１のラン」符号語検出用ルックアップテーブル３５０は、「０のラン」又は「１のラン」符号語の存在を示す１ビット信号を生成する。「０のラン」及び「１のラン」符号語検出用ルックアップテーブル３５０は、図６に示されたテーブルの構造と類似した構造を有するが、単一ビットは図示された各エントリーに対して活性化し、それ以外の場合には負活性である点で相違する。当業者であれば、この信号を生成するため図６に図示されたテーブルを変更する方法が解るであろう。ゲート３５４は、「０のラン」及び「１のラン」符号語検出用ルックアップテーブル３５０からの信号が符号語の存在を示すときに、「０のラン」及び「１のラン」インデックス用ルックアップテーブル３５２からのインデックス信号を通過させ、それ以外の場合には、ゲート３５４によって信号は伝達されない。図４に示された種々のルックアップテーブルに本質的な処理時間のため、ゲート３５４からの信号はクロックサイクルのかなり後の段階で現れる。
【００３６】
図３を参照するに、長さ用ルックアップテーブル３０からの長さ信号は、加算装置２８２において、Ｄフリップフロップ２８４からのアキュムレータの内容と加算される。同様に、長さ用ルックアップテーブル３０からの長さ信号は、第２バレルシフタ２６のシフト動作を制御するため使用される。加算処理及びシフト処理のための待ち時間を最小限に抑えるため、加算装置２８２及び第２バレルシフタの構造は、図４、５及び６を参照して説明したように長さ用ルックアップテーブル３０の構造に適合される。
【００３７】
図７は、図１及び３に図示された可変長復号器システムの一部分のより詳細なブロック図である。図７において、長さ用ルックアップテーブル３０内の「０のラン」符号語長さ用ルックアップテーブル３４６（図４）は、加算器２９２の第１の入力端子と、バレルシフトユニット３０２の制御入力端子とに接続される。加算器２９２の出力端子は、複数の加算器２９４：２９４Ａ、２９４Ｂ，．．．、２９４ｎの第１の入力端子に共通に接続される。複数の加算器２９４のそれぞれの出力端子は、第１のマルチプレクサ２９６の対応したデータ入力端子に接続される。マルチプレクサ２９６の出力端子はアキュムレータのＤフリップフロップ２８４の入力端子に接続される。アキュムレータのＤフリップフロップ２８４の出力端子は加算器２９２の第２の入力端子に接続される。固定長信号の複数のソースは、それぞれ、各加算器２９４のそれぞれの第２の入力端子に接続される。すなわち、第１の固定長信号のソースＬ１は、複数の加算器２９４の中の第１の加算器２９４Ａの第２の入力端子に接続され、第２の固定長信号のソースＬ２は、複数の加算器２９４の中の第２の加算器２９４Ｂの第２の入力端子に接続され、ｎ番目の固定長信号のソースＬｎは複数の加算器２９４の中のｎ番目の加算器の第２の入力端子に接続され、以下同様に続く。
【００３８】
バレルシフトユニット３０２の入力端子は、第１バレルシフタ２４（図２、但し、図７には図示されず）の出力端子に接続される。バレルシフトユニット３０２の出力端子は、第２のマルチプレクサ３０６のそれぞれの入力端子に共通して接続される。バレルシフタ３０２とマルチプレクサとの組み合わせは、第２バレルシフタ回路２６を形成する。第２のマルチプレクサ３０６の出力端子は、長さ用ルックアップテーブル３０の入力端子に接続される。長さ用ルックアップテーブル３０内のゲート３５４（図４）からの「０のラン」及び「１のラン」インデックスは、第１のマルチプレクサ２９６及び第２のマルチプレクサ３０６のそれぞれの制御入力端子に接続される。
【００３９】
動作時に、アキュムレータのＤフリップフロップ２８４の現在値は、加算器２９２の「０のラン」符号語長さに加算される。これら二つの値はクロックサイクルのかなり最初の段階で利用できるので、加算器２９２は、回路の残りの部分に伝播させるために十分な時間内に出力値を生成することができる。しかし、第２の連続的な「０のラン」又は「１のラン」符号語は、第３バレルシフタ３４７と、ルックアップテーブル３５０及び３５２に本質的に存在する待ち時間に起因して、クロックサイクルのかなり後の段階になるまで利用できないので、加算器におけるこれらの値の処理は十分な伝播時間を与えない。その代わりに、加算器２９２からの和は複数の加算器２９４に並列に供給される。
【００４０】
並列加算器２９４へのそれぞれの第２の入力Ｌ１乃至Ｌｎは、第２の連続的な「０のラン」又は「１のラン」に対し起こり得る一定の個数の長さの中の一つの長さを表現する。好ましい実施例の場合に、第２の符号語に対し１４個の起こり得る長さが存在し、１４個の並列加算器は、その加算器に対応した符号語の長さを表わす値をそれぞれの第２の入力端子に受信する。上記の通り、「０のラン」又は「１のラン」符号語インデックス信号は１４ビット信号であり、その中の各ビットは起こり得る長さの中の一つの長さを表現し、インデックス信号内の１ビットだけが同時に活性状態になる。この１４ビットのインデックス信号は、第１のマルチプレクサ２９６を制御する。第１のマルチプレクサ２９６は、１４バンクを有するＡＮＤゲートにより製作され、各ゲートは、複数の加算器２９４の中の対応した加算器からの信号を受信し、インデックス信号内の対応したビットによりイネーブル状態にされる。第１のマルチプレクサ２９６からの出力信号は、アキュムレータのＤフリップフロップ２８４に記憶される。第１のマルチプレクサ２９６と、１個の固定値が入力された１４個の各加算器２９４の動作は、第２の全加算器よりも高速であるので、このような構成によって、第２の「０のラン」又は「１のラン」のランレングス符号語の長さが単一の符号語の区間内でアキュムレータ値に加算され得る。
【００４１】
また、１４個の並列加算器２９４は多数の回路を必要とするように考えられるかもしれないが、各加算器が固定値である１個の入力をとるように並列加算器が実現されるならば、論理最小化が適用され、その結果として、例示された回路は全加算器の回路に対し最小限の回路構成を増加するだけで実現される。
同様に、第２のマルチプレクサ３０６のそれぞれの入力端子は、第１バレルシフタから与えられ、バレルシフトユニット３０２により認識された第１の「０のラン」符号語の長さ分だけシフトされた符号語を受信する。第２のマルチプレクサ３０６の各入力端子において、この信号は、第２の連続的な「０のラン」又は「１のラン」符号語の一定種類数の起こり得る長さの中の一つの長さを表現する量だけ更にシフトされる。上記の通り、第２の符号語には１４通りの起こり得る長さが存在するので、１４個の入力端子が存在し、各入力端子は、その入力端子に対応した第２の符号語の長さ分だけシフトされた符号語信号を受信する。このシフト動作は、バレルシフトユニット３０２の出力端子からの信号を、図７にラベル“Ｓ”で表示されているように適当なビット位置の数だけシフトされた第２のマルチプレクサ３０６の入力端子に配線することによって従来の方法で行われる。上記の通り、「０のラン」又は「１のラン」符号語インデックス信号は１４ビット信号であり、その信号の各ビットは起こり得る長さの中の一つの長さを表現し、インデックス信号の中の１ビットだけが同時に活性化する。１４ビットのインデックス信号は、第２のマルチプレクサ３０６を制御する。第２のマルチプレクサ３０６は１４バンクのＡＮＤゲートによって製作され、ＡＮＤゲートはインデックス信号内の対応したビットによってイネーブル状態にされる。第２のマルチプレクサ３０６からの出力信号は、次の未だ復号化されていない符号語を表現し、長さ用ルックアップテーブル３０に供給される。第２のマルチプレクサ３０６の動作はばれるシフタの動作よりも高速であるため、この構成によって、次の未だ復号化されていない符号語は、単一の符号語の区間内で長さ用ルックアップテーブル３０に供給され得る。
【図面の簡単な説明】
【図１】本発明による可変長復号器（ＶＬＤ）システムのブロック図である。
【図２】図１に示された可変長復号器の各部の詳細なブロック図である。
【図３】図１に示された可変長復号器の各部の詳細なブロック図である。
【図４】図１に示された可変長復号器の各部の詳細なブロック図である。
【図５】図１乃至４に示された可変長復号器内のルックアップテーブルの内容を表わすテーブルである。
【図６】図１乃至４に示された可変長復号器内のルックアップテーブルの内容を表わすテーブルである。
【図７】図１及び３に示された可変復号器の一部のより詳細なブロック図である。
【符号の説明】
１０    可変長符号語ソース
２０    バレルシフタ回路
２２    レジスタセット
２４    第１バレルシフタ
２６    第２バレルシフタ
２７    レジスタ
２８    アキュムレータ
３０    符号語長さ用ルックアップテーブル
３１    出力端子
３２    単一符号語復号化用ルックアップテーブル
３５    入力端子
４０    符号語値用ルックアップテーブル
５０    利用回路
１００    可変長復号器システム
２８２    加算装置
２８４    Ｄフリップフロップ
２８６    同期論理回路
２９２，２９４，２９４Ａ，２９４Ｂ，．．．，２９４ｎ    加算器
２９６    第１のマルチプレクサ
３０２    バレルシフトユニット
３０６    第２のマルチプレクサ
３４２    「０のラン」符号語検出用ルックアップテーブル
３４４    「０のラン」符号語インデックス用ルックアップテーブル
３４６    「０のラン」符号語長さ用ルックアップテーブル
３４８    第３バレルシフタ
３５０    「０のラン」及び「１のラン」符号語検出用ルックアップテーブル
３５２    「０のラン」及び「１のラン」符号語インデックス用ルックアップテーブル
３５４    ゲート
【図１】
0004422833.tif 000002
【図２】
0004422833.tif 000003
【図３】
0004422833.tif 000004
【図４】
0004422833.tif 000005
【図５】
0004422833.tif 000006
【図６】
0004422833.tif 000007
【図７】
0004422833.tif 000008