JPH03131176A - 木構造可変長符号の復号方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、画像データ圧縮・音声データ圧縮などに使用
して好適な復号方式に係り、特にハフマン符号などの木
構造可変長符号の復号方式に関するものである。

（技術的背景） 一般に、ｍｂｌｔの固定長バイナリ−符号では、一１ ２　　＋１（個）かり２　（個）の状態（画像・音声な
どの量子化データなど）を表現することができる。例え
ば、第６図（Ｂ）に示すように、Ａ。

Ｂ、Ｃ，Ｄの４−２２　（個）の状態は、［ｌＯＪ。

ｒｏｌＪ、ｒｌＯＪ、ｒｌｌＪの２　ｂｉｔの固定長バ
イナリ−符号で表現できる。

しかし、上記の各状態の出現数（出現確率）に差異があ
る場合、すなわち、各状態の出現数が均一でない場合に
は、ハフマン符号などの可変長符号を利用すれば、全体
のデータ量を圧縮することができる。

すなわち、出現数が多い状態（データ）には短い符号を
割り当て、出現数が少ない状態（データ）には長い符号
を割当てる。

例えば、第６図（Ａ）に示す木構造（バイナリ−ツリー
構造）のハフマン符号を利用して、Ａ。

Ｂ、Ｃ，Ｄの状態（データ）をそれぞれ「１」。

ｒｏＩＪ、ｒｏｏｌＪ、ｒｏｏｏＪのハフマン符号で表
現する。

この時、各状態Ａ、Ｂ、Ｃ，Ｄの出現数（出現確率）が
第６図（Ｂ）のようであれば、固定長バイナリ−符号で
表現した全情報量（ｂｉｔ数）をＦとした時、各状態に
対して２　ｂｉｔの符号が必要であるので Ｆ−２Ｘ　（７０＋２０＋６＋４） −２００（ｂｉｔ） となる。

これに対して、ハフマン符号で表現した全情報ｚ（ｂｉ
ｔ数）をＨとした時、出現数（出現確率）が高い状態に
は１　ｂｉｔの短い符号が割り当てられ、出現数（出現
確率）が低い状態には３　ｂｉｔの長い符号が割当てら
れているので、 Ｈ−１ｘ７０＋２ｘ２０＋３ｘ６＋３ｘ４−１４０　（
ｂｉｔ） となる。

ハフマン符号などの可変長符号では、全体の情報量が圧
縮減少する反面、状態（データ）に応じて符号長が異な
り、連続した任意長の可変長符号列を符号化・復号化す
るためには、全状態数がＹ個ある場合、最も短い符号長
である１　ｂｉｔから最も長い符号長であるＹから１　
ｔ）Ｉｔ減じたＹ−１ｂＩｔ長の符号が必要となること
が生じる。

このため、ハフマン符号などの可変長符号では固定長バ
イナリ−符号より長い符号長となって、復号装置が大規
模なものとなりやすい。

（従来の技術） 第７図は従来のハフマン符号の復号装置の構成図である
。これは、最大符号長が１３ｂｉｔのハフマン符号の符
号列を復号し、例えば８　ｂｉｔの復号データとして出
力する例である。

２０はシリアルデータであるハフマン符号列を入力し、
シリアル／パラレル変換して出力するシフトレジスタで
ある。このシフトレジスタ２０はハフマン符号の最大符
号長である１３ｂｉｔパラレル出力を有するシフトレジ
スタであり、入力されるハフマン符号列と同期したシフ
トクロックでシフト動作をする。

２１は、前記シフトレジスタ２０の１３ｂｉｔのパラレ
ル出力をアドレス入力とするＲＯＭ　（変換用テーブル
である読み出し専用メモリ）であり、１３ｂｉｔアドレ
ス入力に対応した８　ｂｉｔの復号データと、有効な可
変長符号であることを示す１ｂｔｔのフラグデータ（可
変長符号の有効な符号データである場合は「１」となる
フラグビット）とをデータ出力するものである。

２２は前記ＲＯＭ２１からの８　ｂｉｔの復号データを
ラッチする８　ｂｉｔのラッチである。このラッチ２２
は後述するＲＯＭ２１からフラグビットをラッチパルス
として動作し、前記ＲＯＭ２１からの復号データをラッ
チして最終的な復号データとして出力する。また、ＲＯ
Ｍ２１からフラグビットにより前記シフトレジスタ２０
が初期設定され、シフトレジスタ２０内のデータがすべ
て「１」となるように構成されているものである。

なお、入力される可変長符号は、総桁数が１３ｂｔｔと
なるよう、その符号長に応じて、上位桁にダミービット
（シフトレジスタ２０からのアドレス出力時に付加され
る「１」）を付加しても、その符号長よりも長い符号と
はｂｉｔ内容が重複しないように構成されている。

次に、以上のように構成された復号装置の動作について
説明する。最初に、シフトレジスタ２０が初期設定され
てデータがすべて「１」となる。

そして入力符号列の１　ｂｉｔ目がシフトレジスタ２０
に入力される。この時上位１２ｂｌｔは初期設定ビット
であるダミーデータ「１」が加されて、１３　ｂｉｔの
ｒｌ　１１１　１１１１　１１１１　１Ｊまたはｒｌ　
１１１　１１１１　１１１１　０ＪがＲＯＭ２１のアド
レスに入力される。

そして、アドレス入力に応じたデータ（Ｂ　ｂｔｔの復
号データと１　ｂｉｔのフラグビット）が出力される。

この時、入力符号列の１　ｂｉｔ目が、１　ｂｉｔの符
号長を有する可変長符号であると、データ内容としてｇ
　ｂｔｔの復号データとフラグビット「１」が出力され
る。フラグデータ「１」によりＲＯＭ２１の復号データ
がラッチ２２でラッチされ、最終出力されて復号される
。同時にフラグビット「１」によりシフトレジスタ２０
のデータがすべて「１」に初期設定される。

入力符号列の１　ｂｉｔ目が、１　ｂｉｔの符号長を有
する可変長符号でないと、フラグビット「０」が出力さ
れるので、ラッチ２２のラッチ動作、シフトレジスタ２
０の初期設定は行なわれない。そして人力符号の２　ｂ
ｉｔ目が入力され、シフトレジスタ２０が１　ｂｉｔシ
フトする。

すなわち、上位１１ｂｉｔにダミーデータ「１」が付与
され下位２　ｂｉｔが入力符号の１　ｂｉｔ目と２ｂｉ
ｔ目であるアドレスデータが、ＲＯＭ２１に入力されて
、このアドレスに対応したデータ内容がＲＯＭ２１から
出力される。そして、データ内容のフラグビットに応じ
た動作が前記１　ｂｉｔ目入力時と同じようになされて
、最大１３回の動作により最大符号長１３ｂｉｔの可変
長符号が復号される。

この復号装置による復号時、フラグビット「０」となる
場合、すなわち、入力された桁数（ｂｉｔ数）に等しい
符号長の可変長符号が存在しない場合、そのアドレスに
対応した８　ｂｌｔのデータは不意味である。

しかし、従来の復号方式による復号装置では、変換用Ｒ
ＯＭ２１のアドレス空間としては、可変長符号の最大符
号長ビット数が必要となってしまう。

例えば、第７図に示す最大符号長１３ｂｉｔの復号装置
では（１＋８）Ｘ２１３−８１９２０　（ｂｉｔ）のＲ
ＯＭが必要となる。

（発明が解決しようとする課題） 上述したように、従来の可変長符号の符号方式による符
号装置では、可変長符号の最大符号長に依存した変換用
テーブル（ＲＯＭなどのメモリ）が必要となり、符号装
置が大規模となり民生用機器として安価に構成すること
ができなかった。

また、出現数（出現確率）の低い状態に対しては、符号
長の長い符号が付与されるので、状態数が多い場合には
、特に変換用テーブル容量が大規模となったり、別途処
理する特別な回路構成が必要となった。

（課題を解決するための手段） 本考案は上記課題を解決するために、 第１図（Ａ）及び（Ｂ）、第２図に示すように、木構造
で符号構成された可変長符号の中間ノード及び終端ノー
ドに、Ｎデジットのアドレスを割当て、このアドレスに
データを対応させて木テーブルを構成した復号方式であ
って、 親ノードが共通である子ノードには、Ｎ−１デジットの
共通のアドレスと、分枝する子ノードを区別する１デジ
ットのアドレスとからなるＮデジットのアドレスを割当
て、 前記中間ノードに対しては、この中間ノードを親ノード
として分枝する次の子ノードに共通なＮ−１デジットの
アドレスデータと、中間ノードであることを示す１デジ
ットのフラグデータとを対応させ、 前記終端ノードに対しては、Ｍデジットの復号データと
、終端ノードであることを示す１デジットのフラグデー
タとを対応させると共に、入力された任意長のデジット
から成る可変長符号列により、前記木テーブルのノード
をトレースして、ノードに割当てられたアドレスのデー
タを読出して、ノードのアドレスに対応したフラグデー
タによって中間ノードであるか終端ノードであるかを判
別し、 中間ノードである時は、この中間ノードから分枝する子
ノードの組に共通なＮ−１デジットの前記アドレスデー
タと入力された可変長符号列の１デジットとからＮデジ
ットのアドレスを生成して、この生成されたＮデジット
のアドレスにより指定された前記データを読出して、前
記本テーブルのノードをトレースし続け、 終端ノードである時は、Ｍデジットの復号データを出力
して復号する木構造可変長符号の復号方式を提供すると
共に、 第３図（Ａ）及び（Ｂ）、第４図、第５図に示すように
、 例外コードに続いてｍデジットの固定長符号を有する可
変長符号列の復号に際しては、前記例外コードに対応し
た例外終端ノードと、この例外終端ノードに続くｍ段の
ダミーノードとを木テーブルに追加設定した木構造可変
長符号の復号方式を提供するものである。

（作用） 上記木構造可変長符号の復号方式によれば、入力された
任意長の可変長符号列の１デジットにより木テーブル（
木構造）のノードが順次トレースされ、終端ノードに達
すると復号データが出力される。

（実施例） 本発明になる木構造可変長符号の復号方式の一実施例を
以下、図面とともに詳細に説明する。第１図（Ａ）及び
（Ｂ）は本復号方式を説明するための図で、同図（Ａ）
は木構造（木テーブル）を示す図、同図（Ｂ）は論理テ
ーブルを示す図、第２図は復号装置の構成図である。

く復号方式の概略〉 本復号方式は、概略（イ）〜（ニ）のように構成されて
いる。

（イ）木構造の符号構成された符号の全ノードにはアド
レスが割当てられている。Ｎデジットのアドレスの割当
ては、１デジット上の親ノードが共通となる子ノードの
組（２進木の場合はペアとなる）では、Ｎ−１デジット
分は共通であり、残りの１デジットで分枝した子ノード
をアドレッシングできるように構成している。

（ロ）これら全ノード（のアドレス）にはデータが対応
しでいる。中間ノードのデータ内容は、分枝すべき次の
子ノードの共通アドレスＮ−１デジットと、中間ノード
であることを示す１デジットのフラグデジットとである
。終端ノードのデータ内容は、Ｍデジットの復号データ
と、中間ノードのフラグデジットと同一位置で終端ノー
ドであることを示す１デジットのフラグデジットとであ
る。

（ハ）任意長のデジットから成る可変長符号の復号に際
して、始端ノードから最初に分枝するノードの組の共通
なＮ−１デジットと可変長符号の第１デジットとからＮ
デジットのアドレスを生成し、このアドレスによって（
木テーブルの）ノードのデータを読み出す。

（ニ）読出したデータのフラグデジットによって終端ノ
ードか中間ノードかを判別する。

終端ノードならば、Ｍデジットで表わされた復号データ
を出力する。

中間ノードならば、Ｎ−１デジットで表わされた次のノ
ードのアドレスに可変長符号符号列の次の１デジットを
付は加えたＮデジットのアドレスを生成し、次のノード
をアドレッシングして、そのデータを読み出す。上記を
繰返して終端ノードに達するまで木テーブルをトレース
して復号する。

く復号方式の論理テーブルと木テーブル〉最初に、第１
図（Ａ）及び（Ｂ）を参照して、復号方式の木構造（木
テーブル）と論理テーブルを説明する。なお、本実施例
は各ノードが２つに分枝（枝分れ）する２進木（バイナ
リ−・ツリー）を例としている。よって、符号の１デジ
ット（１゜桁）は１ビツトのバイナリ−コードで表現さ
れている。また、復号される可変長符号は、最小符号長
が１ｂｉｔで最大符号長が６　ｂｉｔのバイナリ−コー
ドで、最終的な復号データは８　ｂｉｔのバイナリ−コ
ード出力であるとする。

同図（Ａ）に示すように、可変長符号は２進木構造で構
成されている。始端ノードからバイナリ−コード（０及
び１）により順次２つに枝分れしており、終端ノードが
可変長符号に対応している。

終端ノードＮ。１は可変長符号「１」に対応し、終端ノ
ードＮ　　　Ｎ　　、Ｎ　　、Ｎ　　、Ｎ　　、ＮＩＰ
　　　２１　　　３１　　　４０　　　５０　　　５１
は可変長符号ｒ０１Ｊ、ｒ００１Ｊ、ｒｏ００１Ｊｒ０
００ＱＯ］、　　ｒｏｏｏｏｌｏＪ、　　ｒｏｏｏｏｌ
ｌ」にそれぞれ対応している。

さらに、同図（Ｂ）に示すように、中間ノードＮ００”
　１０’　Ｎ２０”　３０”　４１及び前記した終端ノ
ードＮ０１・　Ｎ１１・　Ｎ２１・　Ｎ３１・　Ｎ４０
・　Ｎ５０・Ｎ５１には、固有のアドレス（４ｂｉｔ）
が割当てられている。

このアドレスは、共通な親ノードから枝分れした子ノー
ド（本実施例では２進木であるので、共通な親ノードを
もつ子ノードは２つ［ペア］である）では、最終の１　
ｂｉｔを除いた残余の上位アドレス３ｂｉｔが共通で、
最終の下位アドレス１　ｂｉｔで区別されるように構成
されている。なお、本実施例ではアドレスが割当てられ
る中間ノード及び最終ノードは総計１２個であるので、
アドレスは上位アドレス３　ｂｉｔと下位アドレス１　
ｂｉｔの４ｂｉｔで表現している。

例えば共通の親ノードである始端ノードから枝分れした
ノードＮ　　、Ｎ　　とは、共通の上位アト００　　　
０ル スｒ０００Ｊを有し、最終の下位アドレス１ｂｉｔで区
別されるように構成されており、ノードＮｏｏには、ア
ドレスｒ００００Ｊ、　　ノードＮｏ１には、アドレス
ｒ０００１Ｊが割当てられている。

そして、前記中間ノード及び最終ノードのアドレスには
データが対応し、対応するデータの内容は以下のように
設定されている。なお、各アドレスに対したデータ（内
容）とは後述するように、第２図の変換テーブル用ＲＯ
ＭＩに記憶されているデータである。

終端ノードのデータ内容は、最終的な復号データ（８ｂ
ｉｔ）と、終端ノードであることを示す１ｂｉｔのフラ
グデータ（フラグビット「１」）とである。

これに対して中間ノードのデータ内容は、当該中間ノー
ドを親ノードとする子ノード（すなわち、当該中間ノー
ドから枝分れする子ノード）の前記した共通の上位アド
レス（３ｂｉｔ）と、終端でなく中間ノードであること
を示すｉ　ｂｔｔのフラグデータ（フラグビット「０」
）とである。なお、中間ノードのデータ内容である上位
アドレス３　ｂｉｔは、終端ノードのデータ内容である
復号データ８　ｂｉｔとｂｔｔ数が合うように下位に５
　ｂｔｔのダミーデータが付加されている。

例えば、ノードＮ１ｏは中間ノードであるので、このノ
ードＮ１ｏのアドレスに対応したデータ内容は、このノ
ードＮ　を親ノードとするノードＮ２０’Ｏ Ｎ　　（ｎ進水の時はＮ２ｎ）の共通な上位アドレス１ である３　ｂｉｔのアドレスデータｒ０１０Ｊ　　（最
終的には、５ｂｉｔのダミーデータが付与された「０１
０・・・」）と、終端ノードでないことを示すフラグビ
ットｒＯＪとである。

例えば、ノードＮ２、は終端ノードであるので、このノ
ードＮ２１のアドレスに対応したデータ内容は最終的な
復号データであるｇ　ｂｔｔの例えばｒｏｌｏｌｏｌｏ
ｌＪと、終端ノードであることを示すフラグビット「１
」とである。

く復号装置の構成〉 次に復号装置について、第２図を参照して説明する。

１は入力された可変長符号列を復号する変換テーブルで
あり、４　ｂｉｔのアドレス空間と、各アドレスに対し
て８＋１−９ｂｉｔの出力データを持つ１４４ｂｉｔ　
　（−９Ｘ２’）容量のＲＯＭ　（読み出し専用メモリ
）である。

２はリセット端子を有する３　ｂｉｔのレジスタであり
、ＲＯＭＩの出力から新たに入力された３ｂｉｔの上位
アドレスデータを随時出力し、リセットパルスにより初
期の上位アドレスである「０００」を出力するものであ
る。レジスタ２の出力３　ｂｉｔは、前記ＲＯＭ１の上
位アドレス３ｂｉｔとされ、前記ＲＯＭＩの下位アドレ
ス１ｂｉｔ（最終アドレス１　ｂｉｔ）には、可変長符
号の入力列が入力されている。

３は、ＲＯＭＩからの８ｂｉｔの出力データ（これは、
終端ノードのデータ内容である前記復号データ）をラッ
チする８ｂｉｔパラレル入出力のラッチである。このラ
ッチ３の出力が最終的な復号データとなるように、ＲＯ
Ｍ１の８　ｂｉｔの出力データは前記ラッチ３に入力さ
れ、ＲＯＭ１の１　ｂｉｔのフラグデータ（フラグビッ
ト）がラッチ３のラッチパルスとして入力されている。

前述したように、ＲＯＭＩの８　ｂｉｔの出力データ中
、上位の３　ｂｉｔのデータ（これは中間ノードのデー
タ内容である前記した上位アドレス）が前記レジスタ２
に入力され、ＲＯＭ１の１　ｂｉｔのフラグデータ（フ
ラグビット）がレジスタ２のリセットパルスとなってい
る。

なお、すでに、第１図（Ａ）及び（Ｂ）により詳述した
ように、各ノードの固有のアドレス（４ｂｉｔ）に対応
したデータ内容（８＋１−９ｂｉｔ）が、前記ＲＯＭＩ
に記憶されている。

く復号方式の手順と復号装置の動作〉 可変長符号の連続した入力列は、１デジット（上述した
ように、本実施例は２進木であるので、ｔ　ｂｔｔであ
る）づつ、ＲＯＭ１の下位アドレス（１ｂｉｔ）として
入力される。この時、レジスタ２は初期リセットパルス
によりリセットされて、ＲＯＭＩの上位アドレス（３ｂ
ｉｔ）としてｒｏ　００Ｊが入力される。

この時、入力列の最初の１　ｂｉｔが例えば、「０」で
あればＲＯＭＩのアドレスはｒｏ　０００Ｊ　　（すな
わちノードＮ。。）となり、対応データとして８ｂｉｔ
の「００１・・・」　（・・・はダミーデータ）とフラ
グデータである１　ｂｉｔ　　ｒ　ＯＪが出力される。

８ｂｉｔデータ中（ダミノードを除く）上位の３　ｂｉ
ｔｒｏｏｌＪが、次のノード（すなわち、ノードＮ。。

を親ノードとする２つの子ノードＮ　　、Ｎ　　）１０
　　　　１１ の上位アドレスを示すアドレスデータとしてレジスタ２
に入力される。この時フラグビットは「０」であるので
、レジスタ２はリセットされることなく、またラッチ３
もラッチ動作をしない。

そして、人力列の２ｂｉｔ目として例えば、「０」が入
力されると、この２　ｂｉｔ目の「０」を下位アドレス
とし、レジスタ２の前記出力ｒ００１Ｊを上位アドレス
として、アドレスｒ００１０Ｊ　　（すなわち、中間ノ
ードＮ１ｏ）に対応するデータ「０１０・・・」とフラ
グデータである１　ｂｉｔ　　ｒ　ＯＪとが出力される
。１　ｂｉｔ目と同様に、８ｂｉｔのデータ中３ｂｉｔ
　　ｒｏｌｏＪが、次のノード（すなわち、中間ノード
Ｎ１ｏを親ノードとする２つの子ノードＮ　　、Ｎ　　
）の上位アドレスを示すアドレスデー０２１ 夕としてレジスタ２に入力される。この時もフラグビッ
トは「０」であるので、レジスタ２のリセット、ラッチ
３のラッチ動作は行なわれない。

さらに、人力列の３　ｂｉｔ目として例えば、「１」が
入力されると、この３　ｂｉｔ目の「１」を下位アドレ
スとし、レジスタ２の前記出力ｒ０１０Ｊを上位アドレ
スとする、アドレスｒ０１０１Ｊ　　（すなわち、終端
ノードＮ２、）がＲＯＭＩに入力されて、対応するデー
タ、例えば復号データとして８ｂｉｔのｒ　０ＩＯＩＯ
ＩＯＩＪと、フラグビットである１ｂ１ｔ　「１」が出
力される。この時、フラグビットが「１」となるので、
レジスタ２がリセットされるともに、ラッチ３がＲＯＭ
Ｉからの８　ｂｉｔのデータをラッチして出力する。

すなわち、入力列ｒｏｌｌ（・・・）」に対し、最初の
符号は、符号長３　ｂｉｔのｒｏｏＩＪであると復号さ
れて、それに対応する最終的な復号データｒｏ１０１０
１０１Ｊがラッチ３から出力される。

そして、入力列の４　ｂｉｔ目として入力された「０」
また「１」を下位アドレスとし、リセットされたレジス
タ２の出力ｒｏＯＯＪを上位アドレスとする、アドレス
ｒｏ　０００Ｊまたｒ０００１Ｊが再びアドレスされて
、前記復号動作が繰り返され、符号長の異なる可変長符
号が連続した入力列は順次符合される。

く復号装置の変換用ＲＯＭの容量〉 次に、本復号方式による復号装置の変換用ＲＯＭの容量
について説明する。

最初に、全ノード数ＮＴを求める。１ｂｔｔ長の終端ノ
ード数をｎ１＋　・・・ｋ　ｂｉｔ長の終端ノード数を
ｎｋとすると、 Ｎ　Ｔ−ｎ　ｋ ＋（ｎ　／２＋　　ｎｋ　１） ＋（（ｎ　　／２＋　　ｎ　　　　）／２＋ｎｋ−２）
ｋ　　　　　　　ｋｌ ＋（（（（（・・・　　　　　・・・）／２　＋　　ｎ
ｌ）となる。

そして、全ノード数ＮＴに対し、２”＜ＮＴ≦２ｘとな
る値Ｘを求める。そして、ｘ−１の値と復号データビッ
ト数との大きい値をｙとする。

すると、変換用ＲＯＭの容ｆｆ１ｃＦは、ＣＦ　−（ｙ
＋ｌ）　ｘ　２　　　（ｂｉｔ）となる。

したがって、最大符号長が１３ｂｉｔで、符号長２ｂｔ
の符号数（終端ノード数）が２個。

符号長４ｂｔの符号数（終端ノード数）が４個。

符号長６ｂｔの符号数（終端ノード数）が８個。

符号長７ｂｔの符号数（終端ノード数）が２個。

符号長８ｂｔの符号数（終端ノード数）が１０個。

符号長９ｂｔの符号数（終端ノード数）が１２個。

符号長１０ｂ　ｔの符号数（終端ノード数）が４個。

符号長ｆｉｂ　ｔの符号数（終端ノード数）が６個。

符号長１２ｂｉｔの符号数（終端ノード数）が２個。

符号長１３ｂ　ｔの符号数（終端ノード数）が２個の木
構造可変長符号では、 ＣＴ−１０３ で、２６く１０３く２７となり、復号データを８ｂｔｔ
とすると、 ＣＦ　−（ｍａｘ　（７−１，８）＋１）Ｘ２７＝１１
５２　（ｂｉ　ｔ） となる。

すなわち、最大符号長が１３ｂｌｔの本構造可変長符号
の復号に必要な変換用ＲＯＭの容量は、すでに説明した
従来の方式の８１９２０　（ｂ　ｉ　ｔ）と比較して大
幅に削減されることとなる。

（第２の実施例） この第２の実施例は、例外コード、例外終端ノードを使
用してエスケープシーケス動作を可能としたものである
。

可変長符号によるデータの符号化に際して、きわめて出
現数（出現確率）が低い状態も存在する。

この時、きわめて出現数が低い状態を可変長符号化する
と、符号長が従らに長くなり、好しくない。

そこで、きわめて出現数が低い状態については、例外コ
ードとともに固定長符号としてそのまま符号化するよう
に構成したものである。

く符号方式の概略〉 この復号方式は、例外コードに続いてｍデジットの固定
長符号を有する可変長符号列の復号に際しては、前記例
外コードに対応した例外終端ノードと、この例外終端ノ
ードに続くｍ段のダミーノードとを木テーブルに追加設
定して復号するようにしたものである。

く復号方式の論理テーブルと本構造テーブル〉第３図（
Ａ）及び（Ｂ）は前記した第１図（Ａ）及び（Ｂ）に対
応する図で、同図（Ａ）は木構造（木テーブル）を示す
図、同図（Ｂ）は論理テーブルを示す図である。また第
４図は復号装置の構成図である。なお、すでに説明した
実施例と異なる点である例外終端ノードを使用したエス
ケープシーケス動作を中心として説明する。

第５図は、例外コードとこの例外コードに続く固定長符
号を含む入力列である。Ｃ，Ｃ２゜Ｃ，Ｃ６・・・はす
でに説明して可変長符号部分である。Ｃ４は例外コード
であり、このＣ４に続く入力列の部分Ｃ５が固定長符号
である。この固定長符号Ｃ５は、例えば最終的な復号コ
ードそのものでよい。本実施例では、符号長８（すなわ
ち、ｍ　−Ｍ　−８）を例とする。

第３図（Ａ）において、ノードＮ２■が例外終端ノード
（すなわち、例外コードはｒｏｏｌＪ）であり、この例
外終端ノードに続くノードＮ　　、Ｎ０ ６１・　Ｎ７０・　Ｎ７１・　Ｎ８０・　Ｎ８１”　９
０”　９１””１３．Ｎ　　がダミノードである。２進
木の木構造１３１ である本実施例では、２個のダミーコードが１組となっ
て所定の段数が形成されている。すなわちＮ　とＮ　と
からの第１段、Ｎ７ｏとＮ７１とからの６０　　　６１ 第２段、Ｎ８ｏとＮ８１とからの第３段、”・Ｎ１３０
とＮ　　とからの第８段（最終段）の８つの段を３１ 有している。この段数は例外コードに続く固定長符号の
符号長に等しく設定されている。

なお、例外終端ノードＮ２１に続くダミーノードは、ダ
ミーノードの数を少なくするために木構造をとっていな
いが、８つの段を有する木構造としてもよい。例外終端
ノードに続くダミーノードは、その枝分れに意味がなく
、最終段のダミーノードに到るまでの段数を例外コード
に続く固定長符号の符号長に等しく構成しておけばよい
。

また、第３図（Ｂ）に示すように、例外終端ノードに続
くダミーノードにも対応した固有のアドレスが割当てら
れており、アドレスに応じたデータ内容を有している。

なお、本実施例では総計２８のノードがあるので、アド
レス値は上位アドレス４　ｂｉｔと下位アドレス１　ｂ
ｉｔの計５　ｂｉｔで表現されている。なお、最終的な
符号データは８ｂｉｔのバイナリ−コードである。

ダミーノード中、中間のダミーノードＮ６０’Ｎ　　　
、Ｎ　　　、Ｎ　　　、Ｎ　　　、Ｎ　　　・・・Ｎ　
　　　、Ｎ８１　　　７０　　　７１　　　８０　　　
８１　　　１２０　　　　１２１では、当該ノードを親
ノードとする子ノードの共通の上位アドレス４ｂｉｔ（
下位のアドレスである１　ｂｔｔ分を除＜４ｂｉｔ）と
、ダミーノードであることを示す例外ビット１　ｂｉｔ
との合計５　ｂｉｔとがデータ内容である。この上位５
　ｂｉｔの下位に３ｂｉｔのダミービットが付加されて
後述するＲＯＭ１１のｇ　ｂｉｔのデータとなっている
。なお、例外ビットは例えば「１」とする。よって、ダ
ミーノード以外のデータ内容中、ダミーノードに対応す
るｂｔｔ位置は「０」のダミーデータが入れられている
。

また、ダミーノード中、終端ノードには、前記実施例と
同様、８　ｂｉｔの符号データと終端ノードであること
を示すフラグビット「１」とがデータ内容として付与さ
れている。

く符号化装置の構成〉 次に復号装置について、第４図を参照して説明する。

同図中、１１は５　ｂｉｔの入力アドレス空間と、各ア
ドレスに対して（８＋　１−）　９ｂｉｔの出力データ
とを有するＲＯＭ　（読み出し専用メモリ）である。こ
のＲＯＭＩ　１に第３図（Ｂ）に示したアドレスに対応
したデータ（内容）が記憶されている。

１２は、４　ｂｉｔのレジスタで、前記ＲＯＭＩ　１か
らの８　ｂｉｔの出力データ中、上位の４　ｂｉｔが人
力されている。そしてこのレジスタ１２の出力が前記Ｒ
ＯＭＩ　１の上位アドレスの４　ｂｉｔとして入力され
ている。

なお、ＲＯＭ１１の下位アドレスの１　ｂｉｔには入力
列がシリアル入力されている。入力列はシフトレジスタ
１４にも入力されている。

１３は、データセレクタであり、ＲＯＭ１１のデータ出
力ｇ　ｂｉｔと、ｇ　ｂｉｔのシフトレジスタ１４によ
りシリアル／パラレル変換されたｇ　ｂｔｔ分の入力列
とを切り換えるものである。ＲＯＭ１１のフラグビット
出力と例外ビット出力との論理積がアンドゲート１５で
とられて、フラグビットが「１」で例外ビットが「１」
の時、すなわち、ダミーノード中の最終ノードに到った
時に、データセレクタ１３は、シフトレジスタ１４から
の８ｂｔｔデータを選択し、それ以外の時はＲＯＭＩＩ
からｇ　ｂｉｔデータ出力を選択して次段のラッチ１６
に出力する。

ラッチ１６はＲＯＭＩＩのフラグビットが「１」となっ
た時、すなわち、最終ノードに到った時にデータセレク
タ１３からのデータをラッチして最終的な復号データと
して出力する。この時、前記レジスタ１２がリセツトさ
れる。

く復号方式の手順と復号装置の動作〉 Ｃ，Ｃ，Ｃ３などの可変長符号が入力列と２ して入力された時は、すでに説明した第１の実施例と同
様に復号化されて、ＲＯＭＩ　１の８　ｂｉｔのデータ
出力が最終的な復号データとして出力される。

そして、Ｃ４の例外コードｒ００１Ｊ　　（これは、例
外終端ノードＮ２□に対応する）とこの例外コードに続
（８ｂｉｔの固定長符号が人力されると、例外コードに
より、始端ノード−中間ノードＮ。０＝巾間ノードＮ　
→例外終端ノードＮ２１の順で例外Ｏ 終端ノードＮ２□に到る。さらに、例外コード「００１
」に続＜８ｂｉｔの固定長符号により、例外終端ノード
Ｎ２ｌ−４−Ｎ６ｏ（Ｎ６１）−Ｎ７ｏ（Ｎ７１）→Ｎ
９０　９１　　　　　　（Ｎ　　）″′ｓｏ　（Ｎ８ｔ
）＝Ｎ（Ｎ）−Ｎｔｏｏ　　　　ｔｏｔＮ　　　（Ｎ　
　　）→Ｎ　　　（Ｎ　　　）　→Ｎ　ｔ３゜ｔｔｏ　
　　ｉｌｌ　　　　１２０　　１２１（Ｎ　　　）の順
で、８段目のダミーノードの最終３１ 段に到る。なお、ペアのダミーノードは、固定長符号の
データ内容により、その一方のみが選択される。

この間入力列はシフトレジスタ１４に人力されており、
最新の８　ｂｉｔ分の入力列が常時、パラレル出力され
ている。よって８段目のダミーノードＮ　　　（Ｎ　　
　）に到った時に、例外ビットが１３０　　１３１ 「１」で、かつ、フラグビットが「１」となって、アン
ドゲート１５のセレクト出力により、シフトレジスタ１
４の８　ｂｉｔのパラレル出力が選択される。そして、
ラッチ１６によりラッチ出力されて、例外コードに続＜
８ｂｉｔの固定長符号がそのまま最終的な復号データと
して出力される。

なお、本実施例ではノードＮ２□を例外終端ノードとし
、８段のダミーノードを構成して、８　ｂｉｔの固定長
符号をエスケープシーケンス処理した。

しかし、さらに、複数の例外終端ノードを設けて、固定
長符号の符号長に等しい段数のダミーノードそれぞれを
設ければ、異なる符号長の固定長符号を混在させてエス
ケープシーケンス処理できる。

また、以上の第１及び第２の実施例では、２進木（バイ
ナリ・ツリー）を例として１デジット（１桁）を１ｂｉ
ｔ（バイナリ−）で表現したものを説明したが、一般に
ｎ進水（ノードがｎ個に枝分れする）の可変長符号の符
号方式とすることができる。この時は、１デジット（１
桁）の構成としてｎ進の論理素子を使用すればよく、特
に２ｆｆｌ進木のときは、従来の（２進の）デジタル素
子を１デジットにつきｍ個パラレルに使用すれば容易に
実現できる。

（発明の効果） 以上詳述したように、本発明になる木構造可変長符号の
復号方式によれば、従来のように最大の符号長に依存し
た大容量の変換テーブルが不要となり、変換テーブル用
ＲＯＭの容量を小規模にすることができる。

したがって、復号装置を簡易な構成とすることができ、
安価な民生用機器として使用することが可能となる。

また、例外終端ノードとダミーノードを設けることによ
り、例外コードに続く固定長符号をエスケープシーケン
ス処理できるので、出現数のきわめて低い状態がある場
合でも効率よく可変長符号化し復号することができる。

【図面の簡単な説明】

第１図（Ａ）及び（Ｂ）、第２図は本発明になる復号方
式の第１の実施例を示す図で、第１図（Ａ）は本構造（
木テーブル）を示す図、第１図（Ｂ）は論理テーブルを
示す図、第２図は復号装置の構成図、第３図（Ａ）及び
（Ｂ）、第４図は本発明になる復号方式の第２の実施例
を示す図で、第３図（Ａ）は木構造（本テーブル）を示
す図、第３図（Ｂ）は論理テーブルを示す図、第４図は
復号装置の構成図、第５図は例外コードを含む入力列の
一例を示す図、第６図（Ａ）及び（Ｂ）は本構造の可変
長符号を説明するための図で、同図（Ａ）は木構造（木
テーブル）を示す図、同図（Ｂ）は論理テーブルを示す
図、第７図は従来の符号装置の構成図である。 １・・・変換テーブル用ＲＯＭ。 ２・・・レジスタ、 ３・・・ラッチ、 １１・・・変換テーブル用ＲＯＭ。 １２・・・レジスタ、 １３・・・データセレクタ、 １４・・・シフトレジスタ、 １５・・・アンドゲート、 １ ６・・・ラッチ。

Claims (2)

【特許請求の範囲】
1. （１）木構造で符号構成された可変長符号の中間ノード
   及び終端ノードに、Ｎデジットのアドレスを割当て、こ
   のアドレスにデータを対応させて木テーブルを構成した
   復号方式であって、 親ノードが共通である子ノードには、Ｎ−１デジットの
   共通のアドレスと、分枝する子ノードを区別する１デジ
   ットのアドレスとからなるＮデジットのアドレスを割当
   て、 前記中間ノードに対しては、この中間ノードを親ノード
   として分枝する次の子ノードに共通なＮ−１デジットの
   アドレスデータと、中間ノードであることを示す１デジ
   ットのフラグデータとを対応させ、 前記終端ノードに対しては、Ｍデジットの復号データと
   、終端ノードであることを示す１デジットのフラグデー
   タとを対応させると共に、 入力された任意長のデジットから成る可変長符号列によ
   り、前記木テーブルのノードをトレースして、ノードに
   割当てられたアドレスのデータを読出して、ノードのア
   ドレスに対応したフラグデータによって中間ノードであ
   るか終端ノードであるかを判別し、 中間ノードである時は、この中間ノードから分枝する子
   ノードの組に共通なＮ−１デジットの前記アドレスデー
   タと入力された可変長符号列の１デジットとからＮデジ
   ットのアドレスを生成して、この生成されたＮデジット
   のアドレスにより指定された前記データを読出して、前
   記木テーブルのノードをトレースし続け、 終端ノードである時は、Ｍデジットの復号データを出力
   して復号することを特徴とする木構造可変長符号の復号
   方式。
2. （２）請求項第１項記載の木構造可変長符号の復号方式
   において、 例外コードに続いてｍデジットの固定長符号を有する可
   変長符号列の復号に際しては、前記例外コードに対応し
   た例外終端ノードと、この例外終端ノードに続くｍ段の
   ダミーノードとを木テーブルに追加設定したことを特徴
   とする木構造可変長符号の復号方式。