JPH0345093A - 可変長符号復号回路 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〈産業上の利用分野〉 本発明は、各情報源シンボル毎に長さが異なる符号で表
わされた可変長符号列を復号するための可変長復号回路
に関する。

〈従来の技術〉 一般に、入力情報量が非常に大きい画像符号化伝送装置
などにおいては、処理効率、伝送効率を向上させるため
の情報の圧縮符号化が行なわれるＺ例えば、ハフマン符
号化方式は、各情報源シンボルの生起確率がシンボル毎
に異なっていることに着目し、各情報源シンボルの情報
量（生起確率）の逆数と略等しい符号長を持った符号表
を作威し、この符号表に基づいて情報源から入力される
シンボルを符号語に置き換えていき、符号長の圧縮によ
り情報源の冗長度を抑圧した符号列を得るものである。

上記ハフマン方式による符号化回路は、情報源シンボル
をアドレスとしてＲＯＭに格納した符号表から符号語お
よび符号長を読み出すようにして構成される。一方、復
号化回路は、符号語を、ルートの０番ノードから１番、
２番、３番、・・・と枝線に向かって“Ｏ”、“１”に
よって放射状に分岐する第３図に示すような２進符号木
で表わし、この２進符号木を復号しようとする“０゛、
“Ｉ”からなる符号列に従ってルートから探索して、枝
線に復号結果たる情報源シンボルの情報源シンボルテー
ブルにおける格納番地Ａ、Ｂ、・・・を得るようにした
順序論理回路で構成できる。

従来、この種の可変長符号復号回路として、例えば第５
図に示す復号シーケンサ回路１１がある。

この復号シーケンサ回路１１は、復号結果たる情報源シ
ンボルを夫々の格納番地に格納した情報源シンボルテー
ブル２と、入力される可変長符号列Ｄｉの１ビットずつ
を逐次アドレス信号とし、その“０”、“ビによって分
岐方向が決まる２進符号木（第３図参照）を構成する状
態遷移テーブル１３とを有する復号テーブルＲＯＭ１４
と、上記２進符号木の現在進行中のノード番号を格納す
るとともに、このノード番号を上記状態遷移テーブルＩ
３に次に移行すべきノードを求めるためのアドレス信号
として出力する状態レジスタ５と、２進符号本が枝線に
達したとき、枝線の格納番地Ａ、Ｂ。

・・・（第３図参照）に基づき第２図の左列に示す情報
源シンボルテーブル２から出力される復号結果たる情報
源シンボルＤ。をラッチして出力するシンボルレジスタ
６を備え、タイミング制御回路１０からのタイミング信
号Ｓｔを受けて動作するようになっている。

そして、例えば第４図（ａ）に示す“０１１０・・・の
可変長符号列Ｄｉが状態遷移テーブルＩ３に入力される
と、第３図の２進符号木のルート（０番ノード）を指し
ている上記テーブル１３からは、入力符号列の最初のビ
ットが“０”なので、２番ノードが次のノードとして状
態レジスタ５に出力され、ラッチされる。次に、上記テ
ーブルには、ラッチされたノード番号２と次のビット“
Ｉ″が入力されるので、これにより２進符号本が１ノ一
ド進行して３番ノードが読み出されてラッチされる。さ
らに、ラッチされたノード番号３と次の入力ビット“ビ
により２進符号木は枝線Ｃに達し、この格納番地Ｃに基
づいて情報源シンボルテーブル２（第２図の左列参照）
から復号結果たる“００１０”が情報源シンボルＤ。と
じて読み出されて、シンボルレジスタ６にラッチされ、
出力されるとともに、復号が終了したことを表わす復号
終了信号Ｓｆが出力される。このとき、状態レジスタ５
は０番ノード番号にリセットされ、状態遷移テーブル１
３は再び２進符号木のルートを指す。このような処理を
ビットシリアルに入力される１ビット毎に繰り返すこと
によって、入力符号列が順次復号されていくのである。

〈発明が解決しようとする課題〉 さて、実際の可変長符号列を構成する符号語のうち符号
長の長いものは、初めの数ビットが可変長部分、大部分
を占める残りのビットが所定ビット数の固定長部分で構
成されている場合が多い。

ところが、上記従来の復号シーケンサ回路１１は、入力
される可変長符号列をＩビットずつビットシリアルに処
理する上うに構成されているため、上記符号長の長い符
号語を復号する場合、ビット数の多い固定長部分をも１
ビットずつ処理することになり、復号に長時間を要する
という欠点がある。加えて、短い符号語との間で復号時
間に大きな差が生じ、復号結果の出力が時間的にバラつ
いて次段での処理負荷が増大し、復号シーケンサ回路１
１自身の復号効率が著しく低下するのみならず、これを
用いた画像符号化伝送装置等の処理効率までもが低下す
るという欠点がある。

そこで、本発明の目的は、復号回路に１ビットずつシリ
アルに復号する機能に加えて数ビットをパラレルに復号
する機能を付与することによって、長、短符号語間の復
号時間の差を小さくし、復号効率ならびにこの復号回路
を用いたデータ処理装置の処理効率を向上させることが
できる可変長符号復号回路を提供することにある。

〈課題を解決するための手段〉 上記目的を達成するため、本発明の可変長符号復号回路
は、各情報源シンボルが異なった長さの符号で符号化さ
れている入力可変長符号列を、順次復号して原情報源シ
ンボルを出力するものにおいて、上記情報源シンボルを
夫々の格納番地に格納した情報源シンボルテーブルと、
入力されるルート側のノード番号と入力される符号の１
ビットにより指定されるアドレスに、次ｊこ移行すべき
枝端側のノード番号を格納し、枝線が復号結果たる情報
源シンボルの上記情報源シンボルテーブルにおける格納
番地になっており、特定のノード番号以下を、可変長デ
ータに所定ビットの固定長データを付加した入力符号の
ために割り付けた２進符号本を構成する状態遷移テーブ
ルと、上記２進符号木の現在進行中のノード番号を格納
するとともに、このノード番号を上記状態遷移テーブル
にルート側のノード番号として出力する状態レジスタと
、上記状態レジスタに格納されたノード番号が上記特定
のノード番号に達しないとき、ビットシリアルに入力さ
れる可変長符号列を上記状態遷移テーブルにシリアルに
出力する一方、上記ノード番号が上記特定のノード番号
に達したとき、ビットシリアルに入力される可変長符号
列を上記所定ビットずつパラレル変換して上記状態遷移
テーブルに出力するシフトレジスタを備えたことを特徴
とする。

〈作用〉 状態レジスタから入力される現在進行中のノード番号と
入力符号列のｌビットにより指定されるアドレスに、次
に移行すべき枝端側のノード番号を格納し、枝線が復号
結果たる情報源シンボルの情報源シンボルテーブルにお
ける格納番地になっている２進符号木は、その特定のノ
ード番号以下が可変長データに固定長データ（所定ビッ
ト）を付加した入力符号語のために割り付けられており
、状態遷移テーブルによって構成されている。いま、上
記可変長データと固定長データからなる符号語が、状態
遷移テーブルに入力されたとする。すると、２進符号木
のルート（０番ノード）を指していた状態遷移テーブル
は、上記符号語の最初の１ビット“０”または“１”が
指定するアドレスから棟端側の次のノード番号を読み出
して、これを状態レジスタに出力してラッチさせる。次
に、状態遷移テーブルは、符号語の次の１ビット“０”
または“■”および状態レジスタにラッチされた上記次
のノード番号によって指定されるアドレスからざらに枝
端側の次のノード番号を読み出し、これを状態レジスタ
に出力してラッチさせる。このような動作を入力符号語
の可変長データについて繰り返すと、２進符号木は上記
特定のノード番号に達し、このノード番号が状態レジス
タにラッチされる。すると、それまで入力符号語をその
ままビットシリアルに出力していたシフトレジスタは、
その後入力される所定ビットの固定長データを一括パラ
レル変換して状態遷移テーブルに出力する。パラレル入
力されたアドレスデータは、上記特定のノード番号と共
にＩＯ進デコーダ等で変換され、直ちに２進符号木の枝
線を指定し、枝線の格納番地に応じて情報源シンボルテ
ーブルから復号結果たる情報源シンボルが読み出され、
直ちに出力される。

そして、状態レジスタは、２進符号木のルートを指す０
番ノードにリセットされ、状態遷移テーブルは、続く符
号語の復号処理に移る。なお、符号語が可変長データの
みからなる場合は、２進符号木が１ビットずつ枝線に向
かって辿られることになる。

〈実施例〉 以下、本発明を図示の実施例により詳細に説明する。

第１図は、本発明の可変長符号復号回路の一実施例を示
すブロック図である。この復号回路Ｉは、第５図で述べ
た回路の状態遷移テーブル１３を第３図のような２進符
号木を構成する新たな状態遷移テーブル３にするととも
に、ビットシリアルに入力される符号列Ｄｉを３ビット
ずつパラレル変換しうるシフトレジスタ７と、２進符号
木が特定のノード番号（この場合５番ノード）に達した
とき状態遷移テーブル３から出力される制御信号Ｓｃを
受けて上記シフトレジスタ７をパラレル変換動作に切り
換えるシフトレジスタ制御回路８と、上記シフトレジス
タ７からビットシリアルあるいは３ビットパラレルに入
力されるデータと状態レジスタ５から入力される現在の
ノード番号をデコードして、状態遷移テーブル３に次に
移行すべき２進符号木のノード番号の格納場所を表わす
アドレス信号を出力するアドレスコンバータ９を追加し
てなり、第５図と同じブロックには同一番号を付してそ
の説明を省略する。

上記状態遷移テーブル３が構成する２進符号木は、第３
図に示すように、５番ノード以下が２ビットの可変長デ
ータ“００”とこれに続く３ビットの固定長データ“Ｏ
ＯＯ〜１１１”からなる符号長５ビットの入力符号語（
第２図参照）のために割り付けられており、５番ノード
から放射状に分岐する枝線Ｆ−Ｍは、可変長データと固
定長データからなる各入力符号Ｄｉに対応する復号結果
たる情報源シンボルＤ。を格納する情報源シンボルテー
ブル２の格納番地となっている。なお、２進符号木の他
の枝線Ａ−Ｅは、可変長データのみから入力符号語Ｄｉ
に対する復号結果り。の格納番地となる。

上記構成の復号回路ｌの動作について、次に述べる。

いま、シフトレジスタ７に第４図（ｂ）に示す可変長符
号列Ｄｉ“０００１０１０・・・”が入力されたとする
。

状態遷移テーブル３の２進符号木（第３図参照）は最初
ルートの０番ノードを指しており、テーブル３からは制
御信号Ｓｃが出力されないので、シフトレジスタ７は、
入力符号列をそのままビットシリアルでアドレスコンバ
ータ９に出力する。入力符号列Ｄｉの最初のビット“０
″によりアドレスコンバータ９から出力されるアドレス
信号で、状態遷移テーブル３から上記２進符号木に従っ
て２番ノードが読み出されて状態レジスタ５にラッチさ
れ、続いてこのラッチされたノード番号２と次の入力ビ
ット“０”により同様に出力されるアドレス信号で、さ
らに枝端側の５番ノードが読み出されて同様にラッチさ
れる。このとき、２進符号木が特定のノード番号たる５
番ノードに達したので、状態遷移テーブル３は制御信号
Ｓｃを出力し、これを受けたシフトレジスタ制御回路８
はシフトレジスタ７をパラレル変換動作に切り換える。

すると、シフトレジスタ７は、続いて入力される３ビッ
トの固定長データ“０１０”を−括パラレル変換してア
ドレスコンバータ９に出力する。アドレスコンバータ９
は、パラレルデータ“０１０”と状態レジスタ５にラッ
チされているノード番号５に基づいて、対応する枝線Ｆ
を６番、８番ノードを介さず直接指定するアドレス信号
を状態遷移テーブル３に出力し、これによってテーブル
３から読み出された格納番地Ｆに基づいて情報源シンボ
ルテーブル２から復号結果たる情報源シンボルＤ。“０
．１１ビが読み出される。かくて、復号テーブルＲＯＭ
４は、復号終了信号Ｓｆと共に入力符号語Ｄｉ“０００
１０”の復号結果である情報源シンボルＤ１０１１１”
をシンボルレジスタ６に出力し、これをラッチさせると
ともに外部へ出力させる。その後、状態レジスタ５は、
２進符号木のルートを指す０番ノードにリセットされ、
状態遷移テーブル３は、上記制御信号Ｓｃの出力を停止
して、続く入力符号列“ＩＯ・・・”の復号処理に移行
する。

なお、入力符号語Ｄｉが可変長データのみからなる場合
は、第３図の２進符号木が１ビットずつＡ−Ｅのいずれ
かの枝線に向かって辿られて、復号が行なわれることに
なる。

このように、上記実施例によれば、実際の可変長符号列
に多数含まれる可変長データと固定長データからなる符
号語Ｄｉを復号する際、ビット数の比較的多い固定長デ
ータ部については、シフトレジスタ７による一括パラレ
ル変換と、アドレスコンバータ９による状態遷移テーブ
ル３における２進符号木の枝線アドレスの直接指定によ
り、即座に対応する復号結果たる情報源シンボルＤ。を
得て、復号時間を大幅に短縮でき、可変長符号列に含ま
れる長、短符号語間の復号時間の差を小さくできて、復
号回路の復号効率ならびにこれを用いたデータ処理装置
の処理効率を著しく向上させることができる。

なお、本発明が図示の実施例に限られないのは言うまで
もない。

〈発明の効果〉 以上の説明で明らかなように、本発明の可変長符号復号
回路は、可変長データと固定長データからなる入力符号
語に特定のノード番号以下を割り付けた２進符号木を状
態遷移テーブルにより構成し、可変長データの１ビット
ずつの復号化が２進符号木のこの特定のノード番号に達
したとき、シフトレジスタをして続く固定長データを一
括パラレル変換させ、このパラレルデータと状態レジス
タに格納されたノード番号で状態遷移テーブルの２進符
号木の枝線のアドレスを直接指定し、このアドレスに格
納された格納番地に基づいて情報源シンボルテーブルか
ら直ちに復号結果たる情報源シンボルを読み出して出力
するようにしているので、実際の可変長符号列に多数含
まれる可変長データと固定長データからなる比較的長い
符号語の復号時間を大幅短縮でき、長、短符号語間の復
号時間の差を小さくできて、復号回路の復号効率ならび
にこれを用いたデータ処理装置の処理効率を著しく向上
させることができる。

【図面の簡単な説明】

第１図は本発明の可変長符号復号回路の一実施例を示す
ブロック図、第２図は上記実施例の符号表を示す図、第
３図は上記実施例の２進符号木を示す図、第４図は入力
される可変長符号列の一例を示す図、第５図は従来の可
変長符号復号回路を示す図である。 １・・・復号回路、２・・・情報源シンボルテーブル、
３・・・状態遷移テーブル、 ４・・・復号テーブルＲＯＭ、５・・・状態レジスタ、
７・・・シフトレジスタ、９・・・アドレスコンバータ
、Ｄｉ・・・入力符号列、Ｄｏ・・・情報源シンボル、
Ｓｃ・・・制御信号。 特 許 出 願 人 シャープ株式会社 代 理 人

Claims (1)

【特許請求の範囲】
1. （１）各情報源シンボルが異なった長さの符号で符号化
   されている入力可変長符号列を、順次復号して原情報源
   シンボルを出力する可変長符号復号回路において、 上記情報源シンボルを夫々の格納番地に格納した情報源
   シンボルテーブルと、 入力されるルート側のノード番号と入力される符号の１
   ビットにより指定されるアドレスに、次に移行すべき枝
   端側のノード番号を格納し、枝端が復号結果たる情報源
   シンボルの上記情報源シンボルテーブルにおける格納番
   地になっており、特定のノード番号以下を、可変長デー
   タに所定ビットの固定長データを付加した入力符号のた
   めに割り付けた２進符号木を構成する状態遷移テーブル
   と、 上記２進符号木の現在進行中のノード番号を格納すると
   ともに、このノード番号を上記状態遷移テーブルにルー
   ト側のノード番号として出力する状態レジスタと、 上記状態レジスタに格納されたノード番号が上記特定の
   ノード番号に達しないとき、ビットシリアルに入力され
   る可変長符号列を上記状態遷移テーブルにシリアルに出
   力する一方、上記ノード番号が上記特定のノード番号に
   達したとき、ビットシリアルに入力される可変長符号列
   を上記所定ビットずつパラレル変換して上記状態遷移テ
   ーブルに出力するシフトレジスタを備えたことを特徴と
   する可変長符号復号回路。