JPS63314974A - 復号化装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 この発明は、高速ファクシミリの分野で国際標阜規格と
されている画像信号の一次元または二次元圧縮符号（Ｍ
Ｈ符号、ＭＲ符号、Ｍ　Ｍ　Ｒ符号など）を復号するた
めの復号化装置に関する。

従来の技術 従来の復号化装置は、符号データをシリアルなビットデ
ータとして取込んだり、あるいはワードデータとしてパ
ラレルに取込んだ符号データをシリアルデータに変換し
、ビット単位で復号テーブルを検索するようになってい
る。そのような従来装置の概略構成を第１０図に示して
いる。

第１０図において、符号データはＦＩＦＯ（ファースト
イン・ファーストアウト）メモリ１に記憶され、ここか
ら１ワ一ド単位で読み出され、そのワードデータがＰ／
Ｓ　（直並列）変換器２によってビット単位のシリアル
データに変換される。アドレス発生回路３は、Ｐ／Ｓ変
換器２から出力される符号データの１ビットと、復号テ
ーブルＲＯＭ４から出力されてランチ回路５に保持され
ている次テーブルのアドレス情報とに基づいて、復号テ
ーブルＲＯＭ４に与える検索用アドレス情報を発生する
。ＲＯＭ４にはツリーサーチ方式の復号テーブルが格納
されていて、Ｒ／Ｓ変換器２から１ビットずつシリアル
に出力される符号データに従って当該復号テーブルの検
索を行ない、該当の復号データを得る。

発明が解決しようとする問題点 上述した従来の復号化装置では、１つの符号を復号する
ために、その符号のビット数に等しい回数だけ復号テー
ブルの検索を繰り返さなければならず、そのため復号化
処理の高速化が困難だという問題があった。

符号のビット長が一定であれば、１符号を１ワードとし
てワード単位で復号テーブルの検索処理を行なえ、処理
の高速化を達成できる。しかし、ＭＨ符号やＭＲ符号は
可変長の符号で、その符号長は１ビットから１３ピノト
マで変化する。そのために従来はビット単位で復号テー
ブルを検索する構成になっていた訳で、このことが処理
速度を上げる際の大きな障害になっている。

本発明は上述した従来の問題点に鑑みなされたもので、
その目的は、復号データを得るまでの復号テーブルの検
索回数が少なり、シたがって復号化処理の高速化を実現
できるようにした復号化装置を提供することにある。

問題点を解決するための手段 本発明は上述の問題点を解決するために、符号データの
１ワ一ド分を検索アドレス情報とするワード検索用復号
テーブルと、符号データの１ビットと前回の検索結果を
検索アドレス情報とするビット検索用復号テーブルとを
用い、符号データ１ワード中で１つの符号を識別できる
ときには、ワード検索用復号テーブルを検索して復号デ
ータと符号長を得、このときの符号長に従って次の符号
データのワード揃えを行ない、ここで揃った１ワード中
から１つの符号を識別できないときには、ビット検索用
復号テーブルを複数回検索して復号データを得るという
構成を備えたものである。

作用 上記ワード揃えによって揃った符号データ１ワード中に
識別可能な１つの符号（この符号のビット長は短く、統
計的に発生頻度の高い符号である）が含まれていると、
上記ワード検索用復号テーブルを１回検索することで該
当の復号データと符号長とが求まる。この符号長分だけ
を除いた新たな符号データの１ワードが揃えられる。

また、１ワード内で識別できないビット長の長い符号（
統計的に発生頻度の低い符号である）については、上記
ビット検索用復号テーブルを用い、従来と同様なビット
単位の検索によって復号データが求まる。

実施例 第１図は本発明の一実施例による復号化装置の概略構成
を示すもので、２４は当該装置の各部を以下のように制
御する制御回路、５は当該装置から出力される復号デー
タに従って画像信号を生成するデータ生成回路である。

ＦＩＦＯメモリ８は外部データバス６から入力される符
号バイトデータ（符号データの１バイト分）７を順次格
納するためのメモリであって、外部制御バス９からの制
御信号１０によって書き込み制御が行なわれ、制御回路
２・】からの制御信号１１によって読み出し制御が行な
われる。

バッキング回路１３はシフトレジスタを中心にしだ回路
であって、制御回路２４からの制御信号１４（シフトパ
ルスおよびロードパルス）を受けて動作し、メモリ８か
らの符号バイトデータ１２を取り込み、前回の検索で使
用した符号データを除去し、次に復号化処理に供する新
しい１バイトの符号データを揃え、揃えた符号バイトデ
ータ１５をアドレス発生回路１６に与える。

アドレス発生回路１６は制御回路２４からの制御信号１
７　（テーブル選択信号およびイネーブル信号）を受け
て動作するが、テーブル選択信号に従ってバイト検索モ
ードとビット検索モードとの２種の動作のいずれかを実
行する。

復号テーブルＲＯＭ　１９には、第２図に示すバイト検
索用復号テーブルと、第３図に示すビット検索用復号テ
ーブルとの２つが格納されており、バイト検索モードと
ビット検索モードとで使い分けられる。ＲＯＭ　１９か
ら出力される検索結果加は、制御回路２４からのランチ
パルスｎに応動してランチ回路２１に保持され、その報
持データおは制御回路２１１、データ生成回路５、アド
レス発生回路１６に入力される。

バイト検索モードのときアドレス発生回路１６は、バッ
キング回路１３からの符号バイトデータ１５に制御回路
２４からのテーブル選択格報を加えた情報をアドレス情
報１８として出力し、それを復号テーブルＲＯＭ　１９
のアドレス入力として印加する。

ビット検索モードのときアドレス発生回路１６は、バン
キング回路１３からの符号バイトデータ１５の中の最位
上位１ビットと、前回検索時にＲＯＭ　１９から出力さ
れてラッチ回路２１に保持されている次テーブルアドレ
スと、テーブル選択情報とに基づいて新たなアドレス情
報１８を出力し、それをＲＯＭ１９のアドレス入力とし
て印加する。

バイト検索用復号テーブルは、第２図に示すように、テ
ーブル選択信号ｍ、　ｍ、　　（ＭＲ白がＯＯ１ＭＨ黒
が０１、ＭＲが１０となる）と１バイトの符号データと
をアドレス入力とし、復号完了時には、復号完了ビット
Ｐ＝１と、符号長、、ｅ２−ｅｌ−ｅ。

と、復号データとを出力する。また復号未完了時には、
復号完了ピットＰ＝０と、符号長−ｅ２ｆｆｌ、　ｆｆ
ｌ。

−（０１０）または（１００）（この値については後述
）と、次テーブルアドレスとを出カスる。

ビット検索用復号テーブルは、第３図に示すように、テ
ーブル選択信号ｍ＋ｍｏ−（ＩＢと、１ビットの符号デ
ータｄと、上述したラッチ回路２１を介してフィードバ
ックされた次テーブルアドレスａ６〜ａＯとをアドレス
入力とし、復号完了時には、復号完了ピットＰ＝１と、
符号長！□！、！。

−（００１）（この値については後述）と、復号データ
とを出力する。また復号未完了時には、復号完了ピット
ｐ＝ｏと、符号長ｐ、ｚ−ｅ＋　４０−（。

０１）と、次テーブルアドレスとを出力する。

ここで、ビット検索時の符号長出力１３２１３，１３゜
は、１回の検索で用いる符号データが１ビットであるた
め、常に（００１）となる。

また、バイト検索時の復号未完了の場合の符号長出力ｎ
２４．　Ａ、は、ＭＲ白で（０１０）、ＭＲ黒で（１０
０）となる。これは、１バイト内で識別できない符号は
９ビット以上の長さの符号であり、ＭＲ白の９ビット以
上の符号はすべて先頭２ビットが（０１）で、またＭＲ
黒の９ビット以上の符号はすべて先頭４ビットが（００
００）であることから、この部分を除外して検索する方
が効率的なためである。

第４図のフローチャートは制御回路Ｕが各部を制御して
復号処理を行なう手順を示している。以下このフローチ
ャートに従って本装置の動作を詳細に説明する。

まず処理１では、制御回路２４からアドレス発生回路１
６にバイト検索モードのテーブル選択信号１７（ｍ、　
ｍＱ　＝　Ｑ　Ｑまたは０１または１０）を与える。

これを受けてアドレス発生回路１６は、上記テーブル選
択値ｍ、　ｍｏと、バッキング回路１３からの符号バイ
トデータとからなるアドレス情報を生成する。

次に処理２でアドレス発生回路１６へのイネーブル信号
１７をＯＮにすると、当該回路１６から上記アドレス情
報が出力され、復号テーブルＲＯＭ　１９がアクセスさ
れる。ＪこのアクセスによってＲＯＭ　１９から読み出
されたデータは、処理３にてラッチ回路２１に保持され
る。

処理４では、ラッチ回路２１に保持されているデータ（
テーブル出力）のうちの上記復号完了ピットＰの値を調
べ、復号完了か未完了かを判定する。

復号完了の場合は処理５に進み、メモリ８とバッキング
回路１３を制御して、次回検索すべき符号データのバイ
−ト揃え（バッキング処理）を行なう。

このバッキング処理については後で詳述する０次の処理
６ではアドレス発生回路１６へのイネーブル信号をＯＦ
Ｆに戻す。次の処理７では、ラッチ回路２１から出力さ
れている復号データをデータ生成回路５に取り込ませて
、データ生成処理を実行させる。これで１つの符号に対
する復号処理が終わる。

まだ、処理４で復号未完了であった場合には処理８に進
み、後述するように次回検索のためのバッキング処理を
行ない、次の処理９で上記イネーブル信号をＯＦＦに戻
す。そして次の処理１０では、アドレス発生回路１６に
ビット検索モードのテーブル選択信号１７（ｍ４　ｍｏ
　−１１）を与える。これを受けてアドレス発生回路１
６は、上記テーブル選択値ｍ、ｍ（、＝１１と、バッキ
ング回路１３からの符号バイトデータの最上位の１ビッ
トと、ラッチ回路２１からの次テーブルアドレスとから
なるアドレス情報を生成する。このあと前述した処理２
に戻り、上記アドレス情報で復号テーブルＲＯＭ１９を
アクセスし、復号が完了するまで処理２から処理１０を
繰り返す。

第５図のフローチャートは第４図における処理５と処理
８のバッキング処理の詳細を示している。

バッキング処理を行なうために、制御回路路は内部にレ
ジスタしく初期値は８）とぐレジスタ２（初期値は０）
を持ち、以下のようにバイト管理および符号長管理に使
用する。

第５図において、処理１１では、ランチ回路２１に保持
されている符号長Ａ２ｆｆ１．　ｆｆ１ｏの値をレジス
タ２にセットする。処理１２では、バッキング回路１：
３にシフトパルス１４を印加して、すでに検索を行なっ
た符号バイトデータを１ビノトンフトして先頭１ビット
を除去する。処理１３では、レジスタしおよびレジスタ
沼の値を１ずつディクリメントする。

処理１４では、レジスタＬの値により１バイト分のシフ
トが行なわれたか否かを判定し、Ｌ＼０の場合は処理１
９へ、Ｌ−〇の場合には処理１５へ進む。

処理１５では、ＦＩＦＯメモリ８の出力レディ信号の値
を調べてメモリ８から符号データの次・くイトの読み出
しが可能かどうかを判定し、不可能な場合は可能になる
壕で待つ。処理１６では、ＦＩＦＯメモリ８にリード信
号を印加して符号データの次バイトを読み出す０処理１
７では、バッキング回路１３にロードパルスを印加して
、メモリ８から読み出された符号バイトデータをバッキ
ング回路１３にロードする。処理１８では、レジスタＬ
に初期値８をセットする。処理１９では、レジスタ２の
値が０になったか否か（つまり、レジスタ石に処理１１
でセットした符号長に相当する回数だけデータをシフト
したか否か）を判定し、沼−〇の場合は本バッキング処
理を終了し、＼０の場合は処理１２に戻って１＝０にな
るまで上記の処理を繰り返す。

以上のように、８ビット以下の短い符号については、バ
イト検索用復号テーブルを１回検索することで復号が完
了し、９ビット以上の長い符号については、その符号長
に対応した回数だけビット検索用復号テーブルの検索を
繰り返すことで復号が完了する。

次に、バイト検索の１例として第６図の符号例１を復号
する動作について、第８図を用いて説明する。

バイト検索モードで符号データの先頭バイト（００００
０１１０）がアドレス発生回路１６に入力されると、復
号テーブルの検索１の項がアクセスされ、復号が完了し
、復号データＶ、（３）と符号長７が得られる。このと
きの符号長７に従ってバッキング処理が行なわれ、バッ
キング回路１３が７ビノトンフトし、次に検索すべき符
号バイトデータ（００１１００１１）が揃う。すると復
号テーブルの検索２の項がアクセスされ、やはり復号が
完了し、復号データＨと符号長３が得られる。次は符号
長３に従ってバッキング処理が行なわれ、バッキング回
路１３が３ビットシフトし、メモリ８より次バイトの符
号データがロードされて、次に検索すべきデータ（１０
０１１００１）が揃う。順次この動作を繰り返し、検索
３、検索４の項がアクセスされる。バイト検索モードで
は、８ビット以下の長さの符号を１度に識別することが
できるので、第６図の例の各符号はそれぞれ１回のテー
ブル検索処理で復号される。

次に、ビット検索の１例として第７図の符号例２を復号
する動作について、第９図を用いて説明する。

符号データの先頭バイト（００１００００１）について
の検索は、バイト検索モードで検索１の項の結果を得る
。このあと３ビノトンフトして揃ったバイトデータ（０
０００１１００）については、バイト検索モードで検索
２の結果を得る。つまり、ＭＨ黒１５の符号長は９ピツ
トであるため、１回のバイト検索では復号は完了しない
。そうするとビット検索モードに移行する。

検索２の出力は、復号完了ピノ）Ｐ＝Ｏで、これがビッ
ト検索モードへの移行を指示する。またデータＤ６〜Ｄ
ｏで次の検索アドレス情報とすべき次テーブルアドレス
を指示している。次の検索３では、テーブル選択値ｍ、
ｍ、＝１１となり、アドレス発生回路１６はビット検索
モードで動作し、ＭＨ黒１５　（００００１１００００
）の４ビットシフト後のデータ（１１０００）の先頭ピ
ッド１″と、検索２によって得られた次テーブルアドレ
スとによってビット検索用復号テーブルの該当項（検索
３で示す）がアクセスされる。この検索３の結果を受け
てバッキング回路１３が１ピツトシフトされ、新たな先
頭１ピツトと次テーブルアドレスに従って検索４の項が
アクセスされる。以下同様にして、最後のビット１１０
″による検索が終了するまで上記の動作が繰り返される
。検索７はその結果を示す。このビット検索では、９ビ
ット以上の符号長をもつ１つの符号について復号を完了
するには、復号未完了を判定する検索と、符可のＭＨ黒
で４ビット、ＭＨ白で２ビットシフトした残υのビット
数分の検索が必要となる。

以上説明したように、１ワードを１バイト（８ビット）
として、８ビット以下の長さの符号をバイト単位で検索
処理し、９ビット以上の長さの符号をビット単位で検索
処理することで、高速な復号処理を実現できるとともに
１テーブルの容量が小さい低コストの装置となる。これ
は、９ビット以上の長い符号は、ＭＨ白メークアップの
ランレングス７０４〜２５６０、ＭＨ黒ターミネイテイ
ングのランレングス１５〜６３、メークアップのランレ
ングス６４〜２５６０で、いずれも原稿画像中の白ラン
・黒ランの分布の統計的性質から発生頻度が非常に低く
、これらの符号に対する復号テーブル検索処理時間の全
体に占める割合いは小さいことと、これらの符号にバイ
ト検索を続けるようにすると、１回の検索では符号を識
別できず、検索結果情報を次テーブルアドレスとしてフ
ィードバックして複数回のバイト検索を行なう必要があ
り、そうするとテーブルの規模（ＲＯＭ容量）が非常に
大きくなってしまうこと等を考慮した結果であるＯ 発明の効果 以上の説明から明らかなように、本発明は、符号データ
１ワードを検索アドレス情報とするワード検索用復号テ
ーブルと、符号データ１ビットと前回の検索結果を検索
アドレス情報とするビット検索用復号テーブルとを用い
、符号データ１ワード中で１つの符号の識別が可能なも
のについては、ワード検索用復号テーブルを検索して復
号データと符号長を得、このときの符号長に従って次の
符号データのワード揃えを行ない、前記識別が不可能な
ものについては、ビット検索用復号テーブルを複数回検
索して復号データを得るという構成をとることによって
、統計的に発生頻度の高い１ワード以下の短い符号につ
いては１回のワード検索で復号化できるため、復号処理
の高速化が可能となり、また、統計的に発生頻度の低い
１ワードを超える長い符号については、ワード単位の検
索を複数回繰り返すのではなくて、ビット単位の検索を
行なうことから、テーブルの容量を小さくすることがで
きるという効果を有する。

【図面の簡単な説明】

第１図は本発明の一実施例による復号化装置の概略構成
図、第２図は同装置におけるワード検索用復号テーブル
の内容を示す概念図、第３図は同装置におけるビット検
索用復号テーブルの内容を示す概念図、第４図および第
５図は同装置の動作・制御手順を示すフローチャート、
第６図および第７図は処理に供される符号データの例を
示す図、第８図および第９図は上記符号データ例につい
ての復号処理の説明図、第１０図は従来の復号化装置の
概略構成図である。 ８・・・ＦＩＦＯメモリ、１３・・・バッキング回路’
１１６・・・アドレス発生回路、１９・・・復号テーブ
ルＲＯＭ　ｚ２１・・・ラッチ回路、２４・・・制御回
路、５・・・デー々生成回路。 代理人の氏名　弁理士　中　尾　敏　男　ほか１基筒　
２　図 り、符号ビ昇長 月３図 Ｌ−符号ビ・・セ 第４図 ′、　６　図 符号り１１ 第７図 苔号介１？ 第８図 第９図 一（

Claims (1)

【特許請求の範囲】
1. 符号データ１ワードの中から検索済みのビットを除去す
   るとともに新たな符号データを加えて１ワードに揃える
   ワード揃え手段と、このワード揃え手段の符号データ１
   ワードを検索アドレス情報とし、その中に識別可能な符
   号があればその符号長および復号データを出力し、識別
   可能な符号がなければ復号未完了情報出力するワード検
   索用復号テーブルと、上記ワード揃え手段の符号データ
   １ワードの先頭１ビットと前回のテーブル検索結果から
   フィードバックされる次テーブルアドレスとを検索アド
   レス情報とし、復号完了時には復号データを出力し、復
   号未完了時には復号未完了情報と次テーブルアドレスと
   を出力するビット検索用復号テーブルと、前回の検索で
   復号が完了すれば次回は上記ワード検索用復号テーブル
   により検索を行ない、前回の検索で復号が未完了であれ
   ば次回は上記ビット検索用復号テーブルにより検索を行
   なう制御手段とを有する復号化装置。