JPS6051077A - モデイフアイド・ハフマン符号の復号化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の属する技術分野〕 本発明はファクシミリ通信に使用されるモデイファイド
・ハフマン符号（以下ｒＭＨ符号」という。）の復号化
に関する。

ここでハフマン符号の変形であって、符号の種類を減ら
すためにランレングス符号をメイクアップ符号とターミ
ネイト符号の組合せで表現したものである。ターミネイ
ト符号はＯビットから６３ビツトまでのランレングス符
号を表す。０ビツトから６３ビツトまでのランレングス
はターミネイト符号のみで表され、６４ビツト以上のラ
ンレングスはメイクアップ符号の後にターミネイト符号
を続けた形で表すように構成される。

〔従来技術の説明〕

従来、ＭＨ符号の復号化方式として線形探索法が用いら
れた。この従来方式は、ＭＨ符号のｔｒｅｅ構造を１ビ
ツトづつ状態遷移しながら探索する方式で、１つのＭＨ
符号を復号するのに、ＭＨ符号を先頭から順番に１ビツ
トずつ得て、ランレングス情報または次テーブルアドレ
ス情報が書かれた復号化テーブルを参照し、そこに次テ
ーブルアドレス情報が書かれていればその情報と次の１
ビツトを演算して次の復号化テーブルアドレスをめ、再
び復号化テーブルを参照して、ランレングスを得るまで
、すなわちｌ符号が終結するまで、上記のテーブル参照
を多数回くり返す方式であった。

従って所要のランレングスを得るまでに長い時間が必要
であり入力されるＭＨ符号に対して復号化システムが速
く動作しなければ復号化処理が間に合わなくなり、復号
化できなくなる場合があるなどの欠点があった。

〔発明の目的〕

本発明は上記の欠点を解決するものであり、復号化テー
ブルを１回だけ参照することによりｌ符号の復号化を完
了させるようにして、復号化処理速度を高め、速い回線
速度で送られてくるＭＨ符号の復号化を可能にしたファ
クシミリ通信方式を提供することを目的とする。

〔発明の特徴〕

本発明は、 （１１人力されるＭＨ符号を一時蓄える入力用バッファ
と、 （２）白ラン用符号については先頭から８ビツト、黒ラ
ン用符号については先頭から４ビツトが全て「０」であ
る符号はその４ビツトを除去し、その次からの８ビツト
、それ以外の黒ラン用符合は先頭からの８ビツトを引用
できる機能を備えた部分と、 （３）１バイトの中に、（ア）ターミネイト（主走査）
符号の場合はその符号長を表す情報およびランレングス
の値とを表す情報と、（イ）メイクアップ（副走査）符
号の場合はメイクアップ符号であることを示す情報およ
びランレングスの値を表す情報（但し上記第（２）項で
引用した８ビツトで１符号が終結しない場合は次ビット
を「０」と仮定した場合のランレングスの値を表す情報
）とを含む白符号および黒符号用のそれぞれ２５６バイ
トよりなる復号化テーブルと、（４）　メイクアップ符
号の符号長をランレングスの小さい順に書き込んだ符号
長テーブルと、（５）記録部へ出力するまで一時データ
を蓄える出力用バッファと を備え、前記第（２）頂部分で引用されたデータによっ
て、前記第（３）項で定義された復号化テーブルを１回
だけ参照することにより、１つのＭＨ符号の復号化が達
成されることを特徴とする。

〔実施例の説明〕

次に本発明の実施例方式について添付図面を参照して説
明する。

図は本発明実施に最小限必要な構成を示すブロック構成
図である。

図中１は入力されたＭＨ（Ｍｏｄｉｆｉｅｄ　Ｈｕｆｆ
ｍａｎ）符号を処理が済むまで一時蓄えるための入力用
バッファである。２は制御プログラムおよび復号化テー
ブルと符号長テーブルとが書込まれている続出専用メモ
リ　（ＲＯＭ）である。３は記録部などへ出力するまで
一時データを蓄えておくための出力用バッファである。

本システム制御用のマイクロプロセッサ４は上記１．２
．３各構成部分とバス結合されている。

まず続出専用メモリ　（ＲＯＭ）２に書き込まれティる
復号化テーブルについて説明する。

第２図と第３図は上記ＲＯＭ２に格納されている復号化
情報の形式を示す。第２図はメイクアップ（主走査）符
号の場合である。第３図はターミネイト（副走査）符号
の場合である。第３図において黒符号テーブルの場合の
符号長は実際より４ビツト小さい形で格納されている。

メイクアップ符号で９ビット符号（黒符号の場合は先頭
の４ビツトを除く）の場合はランレングス（ラン長）情
報として９ビツト目を“０”と仮定した形で格納されて
いる。

ここでアドレスとの対応について述べると下記（ｉ）、
（ｉｉ）のとおりである。

（１）白ラン用符号の復号化情報はその符号の先頭から
８ビツトのデータに相当するアドレスに格納されている
。

（ｉｉ）黒ラン用符号の復号化情報は、その符号の先９
４ビットが全て「０」の場合はその４ビツトを除去した
続く８ビツトのデータに相当するアドレスに格納されて
いる。それ以外の黒ラン用符号の復号化情報は本テーブ
ルには含まれない。

次に上記復号化テーブルを用いてＭＨ符号の復号化を行
う手順（１１〜（１２）項に示す。

（１）　ライン終端（ＥＯＬ）のサーチ。前記入力用バ
ッファ１の先頭から１バイトずつデータを読出しＥＯＬ
パターンをサーチする。ＥＯＬのパターンは「１」を見
つけるまでに１１ビット以上の連続した「０」があった
かどうかによる。

（２）　ラインの最初は白符号から始まるから、まず白
符号の復号化処理について説明する。

（２−１）白ラン用符号として処理の済んでいないビッ
トを先頭に８ビツト分入力用バッファ１がら引用する。

（２−２）上記（２−１）項の８ビツトデークに相当す
るアドレスの内容を読出す。

（２−３）上記（２−２＞　で得た内容の上位３ビツト
が全て「０」かどうか、すなわちメイクアップ符号かタ
ーミネイト符号がチェックする。

（３）メイクアップ符号処理は、上記（２−２）項で得
た内容の下位５ビツトによって示されたランレングスの
１／６４の値をとり出しこれをＡと表示すると、その植
入によってアドレスされる符号長テーブルを参照して符
号長を得る。また、Ａが１０以下であるか、すなわち符
号長が８以下か９かをチェックする。

（４）上記（３）項で１０以下の場合すなわち符号長が
８以下の場合には、Ａ値を６４倍して出力用バッファ３
に渡し、（３）項で得た符号長の次からのビットを先頭
に続く８ビツト分を入力用バッファ１から引用して白タ
ーミネイト符号処理を行う。

（５）　上記（３）項で１１の場合すなわち符号長が９
の場合には、 （５−’１　）　Ａ　＝２６の場合、すなわちランレン
グスが１６６４の場合、Ａを６４倍して、出力用バッフ
ァ３に渡し、前記（３）項で得た符号長の次からのビッ
トを先頭に続く８ビツト分を入力用バッファ１から引用
し白ターミネイト符号処理を行う。

（５−２）　Ａ　’ｒ２６の場合、入力用バッファｌか
ら次ビットを得てそれが「１」の場合はＡに１を加える
。またこのときＡ＝２６となれば、すなわちラン長が１
７２８の場合はさらにＡに１を加え、このＡを６４倍し
て出力用バッファ３に渡し、次のビットを先頭に続く８
ビツト分を入力用バッファ１から引用し、白ターミネイ
ト符号処理を行う。

（６）白ターミネイト符号処理は、復号化情報の下位５
ビツトまたは６ビツトの値を出力用バッファ３に渡し上
位３ビツトまたは２ビツトで表された符号長の次からの
ビットを先頭に続く８ビツト分を入力用バッファ１から
引用し、次に黒符号復号化処理を行う。（ランレングス
が下位５ビツトで表されているか、６ビツトで表わされ
ているかは上位３ビツトがｒｏｏｌＪかまたはｌ”０１
０．Ｊか、それ以外かによる。） （７）次に黒符号の復号化処理は、 （７−１）引用されたデータの上位４ビツトが全て「０
」かどうかチェックする。

（７−２）上記（７４）でｒｏ　Ｏ００」の場合、その
４ビツトを捨て、続く８ビツトを引用し、その８ビツト
でアドレスされる内容を読出す。

（７−３）上記（７−２）で得た内容の上位３ビツトが
全て「０」かどうか、すなわちメイクアップ符合かター
ミネイト符号かチェックする。

（８）　メイクアップ符号処理は、上記（７−２＞　で
得た内容の下位５ビツトによって示されたランレングス
のｌ／６４の値をとり出しこの値をＢによってアドレス
される符号長テーブルを参照して符号長を得る。また上
記Ｂが７以下であるか８以上であるか、すなわち符号長
が１２以下か１３かチェックする。

（９）上記（８）でＢが７以下の場合、すなわち符号長
が１２以下の場合。前記Ｂを６４倍して出力用バッファ
３に渡し、（８）で得た符号長の次からのビットを先頭
に続く８ビツト分を入力用バソフプ１から引用し黒ター
ミネイト符号処理を行う。

叫　前記（８）で８以上の場合、すなわち符号長が１３
の場合。入力用バッファ１から次ビットを得て、それが
１１」の場合は前記Ｂに１を加えて、Ｂを６４倍して出
力用バッファ３に渡し、次のビットを先頭に続く８ビツ
ト分を入力用バッファ１から引用し、黒ターミネイト符
号の処理を行う。

（１１）黒ターミネイト符号処理は、復号化情報の下位
５ビツトまたは６ビツトの値を出力用バッファ３に渡し
、上位３ビツトまたは２ビツトで表わされた符号長の次
からのビットを先頭に続く８ビツト分を入力用バッファ
１から引用し次に白符号復号化処理を行う。

（１２）前記（７−１）においてｒｏ　０００Ｊでない
場合は９通りしかないのでその上位ビットから逐次チェ
ックし、ランレングスと符号長を得て、ランレングス出
力用バッファ３に渡し、符号長の次からのビットを先頭
に８ビツト分を入力用ノＮ・ノファｌから引用して白符
号復号化処理を行う。

以上のように白符号復号化処理、（２）〜（６）、黒符
号復号化処理（７）〜（１２）、をライン終結ＥＯＬが
見つかるまで交互にくり返し、１ラインの復号化処理を
行う。

（発明の効果） 本発明は以上説明したように、復号化テーブルを１回だ
け参照するだけで迅速にＭＨ符号の復号化を完了するこ
とができ、速い回線速度で送られてくるＭＨ符号の復号
化を可能にする効果がある。

【図面の簡単な説明】

第１図は本発明に最少限必要な部分よりなる実施例のブ
ロック構成図。 第２図は続出専用メモリに格納されてし）るメイクアン
プ符号の復号化情報の形式図。Ｘｔま「０」または「１
」である。 第３図は続出専用メモリに格納されてしするターミネイ
ト符号の復号化情報の形式図。（）内むま黒符号テーブ
ルのときの実際の符号長を示す。Ｘは「０」または「１
」である。 １゛・・入力用バッファ、２・・・ＲＯＭ、３・・・出
力用バッファ、４・・・マイクロプロセツサ。 特許出願人　日本電気株式会社 代理人　弁理士　井　出　直　孝

Claims (1)

1. 【特許請求の範囲】 （１１マイクロプロセッサと、 このマイクロプロセッサにより制御され入力されるモデ
   ィファイド・ハフマン符号を一時蓄積する大カバソファ
   回路と、 上記マイクロプロセッサに接続されこのモディファイド
   ・ハフマン符号を復号化するために必要なテーブルが記
   憶された続出専用メモリと、上記マイクロプロセッサに
   より制御され復号化された符号を一時蓄積する出方バッ
   ファ回路とを備え、 上記続出専用メモリには、 ターミネイト符号の場合にはその符号長を表す情報およ
   びランレングスを表す情報を、メイクアップ符号の場合
   にはその符号がメイクアップ符号であることを示す情報
   およびランレングスを表す情報をそれぞれ１バイト中に
   含む白符号および黒符号用の復号化テーブルと、 メイクアップ符号の符号長がランレングスの小さい順に
   書き込まれた符号長テーブルとが記憶され、 上記マイクロプロセッサは、 白ラン用符号については先頭から８ビツトを除去し、黒
   ラン用符号については先頭から４ビツトが「０」である
   符号はその４ビツトを除去して８ビツトのデータの引用
   を行い、 このデータによって上記復号化テーブルを１回だけ参照
   することにより１つのデモイファイド・ハフマン符号を
   復号化するように構成されたことを特徴とするモディフ
   ァイド・ハフマン符号の復号化方式。