JPH04219027A - モデファイドハフマン符号の復号化方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はモデファイドハフマン符
号の復号化方法に関するものである。

【０００２】

【従来の技術】モデファイドハフマン符号（以後ＭＨ符
号と呼称する）は、各符号毎にそのビット数が異なる可
変長符号である。このためＭＨ符号が連続して伝送され
ると受信側ではその符号長を予測できないため、記憶回
路中にＭＨ復号表を記憶させ、これを解読して復号する
方法がとられている。

【０００３】ＭＨ復号表の作成方法は、従来から復号化
の処理速度と記憶回路の容量に応じていくつか提案され
ている。例えば、入力されたＭＨ符号によって記憶回路
のアドレスを修飾する方法がある。この場合、記憶回路
のデータにはＭＨ符号に対応したランレングスが書き込
まれており、また対応するランレングスが存在しない場
合には意味のない内容が書き込まれている。しかし、上
記の例に示す方法によると、例えばファクシミリ通信の
場合ＭＨ符号の最長符号長１３ビットあるため、２１３
バイト（約８Ｋバイト）の記憶容量を有する記憶回路が
必要になる。

【０００４】そこで、ＭＨ符号の特徴に着目して記憶容
量を削減する方法がいくつか提案されている。例えば、
ファクシミリ通信の場合ＭＨ符号の９ビット目以上は全
て「０」の符号になっているため、入力符号の下位８ビ
ットだけを記憶回路のアドレスの下位バイトの修飾に使
用し、アドレスの上位バイトは符号長によって区別でき
る様に復号表を作成する。この方法によると、約３Ｋバ
イトの記憶容量を有する記憶回路でＭＨ復号表を作成す
ることができる。

【０００５】しかし、周知の様にファクシミリ通信にお
けるＭＨ符号は、白と黒のそれぞれについてターミネイ
ティングコード（Ｔｅｒｍｉｎａｔｉｎｇ　　Ｃｏｄｅ
）が６４個（ランレングス０，１，２，……，６３）で
あり、白と黒のそれぞれについてメイクアップコード（
Ｍａｋｅ　　Ｕｐ　　Ｃｏｄｅ）が４０個（ランレング
ス６４，１２８，１９２，……，２５６０）であり、全
て合計しても２０８個しかない。従って、従来のＭＨ符
号の復号化方式では、ＭＨ復号表を記憶する記憶回路に
まだ相当の無駄が存在していた。

【０００６】

【発明が解決しようとする課題】本発明は上記した従来
のＭＨ符号の復号化方式の欠点に鑑みなされたもので、
記憶容量の小さい記憶回路を用い、しかも復号化の処理
速度を低下させることのないＭＨ符号の復号化方式を提
供することを目的としている。

【０００７】

【課題を解決するための手段】本発明のＭＨ符号の復号
化方式は、ＭＨ符号を用いて情報伝送を行うシステムに
おいて、受信側で復号化する際に、入力されるＭＨ符号
を枝分かれ式に逆変換する為の復号表を記憶した記憶回
路を備え、入力されるＭＨ符号に応じて記憶回路に記憶
された復号表を順次参照し、復号化するものである。更
に詳しく説明すると、記憶回路の各アドレスには、ＭＨ
符号生成過程を示す木構造における一つの分枝点の下位
に位置する二つの分枝点を示すアドレスデータが記憶さ
れ、更に下位の分枝点が存在しない場合には該当するラ
ンレングスが記憶されている（前記復号表に該当する）
。又、入力されるＭＨ符号と、上記アドレスデータ（木
構造のトップの分枝点の次の二つの分枝点の場合は不用
）とを用いて二つの分枝点のうちの一つを示す読み出し
アドレス信号を形成する読み出しアドレス信号形成手段
が設けられている。

【０００８】

【作用】プロセッサ１はＭＨ符号Ｓが１ビット入力され
るたびに記憶回路２に記憶されているＭＨ復号表を参照
して復号化を実行する。初めにランレングス符号は必ず
白と黒の繰り返しであり、ＭＨ復号表の白または黒の上
位アドレスをレジスタＨにセットし、次に下位アドレス
の初期値（００）１６をレジスタＬにセットする。この
状態でＭＨ符号Ｓが１ビット入力されるとレジスタＬの
Ｄ０に加え、次にレジスタＨ，Ｌのデータをアドレス信
号としてＭＨ復号表のデータを読み出し分岐の最終か否
かを判定する。

【０００９】

【実施例】以下添付の図面によって更に詳細に本発明に
ついて説明する。

【００１０】図１は、ＭＨ符号の生成過程を木構造で示
す図である。即ち、ＭＨ符号の生成では全てのランレン
グスの中で最も出現確率の小さい二つのランレングスを
統合する方法がとられる。そして、統合によって形式的
に新しい確率要素が生まれ、その確率は統合された二つ
の確率要素の和として与えられる。１回の統合によって
見掛上ランレングスの数は１つ減り、ランレングス群は
新たに出現確率順に並び替えられる。ランレングス群の
統合を繰り返し実行し、最終的に全部のランレングスが
一つの確率要素に統合されるところでこの操作は終了す
る。ｎ個のランレングスは（ｎ−１）回の統合で一つの
確率要素に統合される。

【００１１】図１は上記ＭＨ符号生成過程を示すもので
、Ｐｎ（ｎ＝１，２，…，６）が各ランレングスを表わ
し、そのカッコ内の数字が出現確率を表わしている。 そして、箱形で囲んだ部分に各符号語が示されている。 例えばランレングスＰ１〜Ｐ６の中で最も確率の小さい
二つのランレングスはＰ４とＰ６であり、この二つのラ
ンレングスが先ず最初に統合されランレングスＧ１にな
る。 そしてランレングスＧ１の出現確率はランレングスＰ４
，Ｐ６の出現確率の和で表わされ、０．１７になる。続
いて、同様の処理がランレングスＰ１，Ｐ２，Ｐ３，Ｐ
５，Ｇ１において繰り返し実行され、最終的に一つのラ
ンレングスＧ５に統合される。

【００１２】本発明のＭＨ符号の復号化方式は、以上に
記載したＭＨ符号生成方法に着目して、復号化に際して
図１に示す様な木構造をＭＨ符号生成の場合と逆にたど
り、入力符号を各ランレングスに変換するものである。 更に詳しく説明すると、例えば入力された最初のＭＨ符
号が１の場合にはランレングスＧ５からランレングスＧ
３に分枝する。次に入力されたＭＨ符号が０の場合には
ランレングスＰ５に分枝し、１つのコードの復号化が終
了する。そして、前記復号化表は、この木構造における
各分枝点を示すアドレスデータから構成されるものであ
る。

【００１３】図２は本発明をファクシミリ通信に適用し
た場合の一実施例を示す復号化回路のブロック図である
。

【００１４】プロセッサ（ＣＰＵ）１には、アドレスバ
スとデータバスを介して記憶回路２が接続されている。 この記憶回路２にはＭＨ復号表の他に、復号化処理を実
施するためのプログラムが書き込まれている。尚、この
実施例ではプロセッサ１及び記憶回路２は８ビット単位
で構成されている。

【００１５】プロセッサ１はＭＨ符号Ｓが１ビット入力
されるたびに記憶回路２に記憶されているＭＨ復号表に
参照し、復号化を実行する。記憶回路２には白のランレ
ングスに対応する復号化表と黒のランレングスに対応す
る復号表は別のアドレスに割当てられている。

【００１６】図３は記憶回路２に記憶されたＭＨ復号表
のデータ構造である。ここで、例えばＤ０ビットを「Ｐ
ｏｌｅ／Ｆｉｎａｌ」ビットとし、Ｄ０が「０」の場合
に「Ｐｏｌｅ」、Ｄ０が「１」の場合に「Ｆｉｎａｌ」
と定義する。次に上記「Ｐｏｌｅ」と「Ｆｉｎａｌ」の
意味について説明する。

【００１７】（イ）「Ｐｏｌｅ」はプロセッサ１に入力
されたＭＨ符号Ｓがまだ完結していないことを意味する
。また、図３に示すＤ７〜Ｄ０が全て「０」の場合には
、ＭＨ符号として「０」符号が８個連続して入力された
ことを意味する。以後この様に８個のビットＤ７〜Ｄ０
が全て「０」のデータを（００）１６と表示する。この
ため、その後の処理はＥＯＬ（ＥＮＤ　　ＯＦ　　ＬＩ
ＮＥ）検出モードになる。

【００１８】「Ｐｏｌｅ」でかつ記憶回路２のＭＨ復号
表から読み出されるデータ（００）１６でない場合、図
３に示すデータＤ７〜Ｄ１を次に参照すべきＭＨ復号表
のアドレスビットＡ７〜Ａ１のアドレス信号に使用する
。このアドレスビットＡ７〜Ａ１は分枝点の次の二つの
分枝点を示すアドレス信号である。そして新たに入力さ
れたＭＨ符号Ｓ（「０」又は「１」の符号）をＭＨ復号
表のアドレスビットＡ０のアドレス信号として使用する
。そして、このアドレス信号Ａ７〜Ａ０により、次の二
つの分枝点のうちの一方の分枝点を示す読み出しアドレ
ス信号を形成し、新たにＭＨ復号表からデータを読み出
す。

【００１９】（ロ）「Ｆｉｎａｌ」は入力されたＭＨ符
号Ｓが完結したことを意味する。この場合、例えば図３
に示すデータＤ７ビットをＭＨ符号のターミネイティン
グコードとメイクアップコード区別のために割り付ける
。そして、残りのＤ６〜Ｄ１の６ビットでターミネイテ
ィングコード６４個とメイクアップコード４０個を表現
する。つまり、Ｄ６〜Ｄ１ビットでターミネイティング
コード又はメイクアップコードのランレングスを表わし
、ターミネイティングコードの場合には各々２５〜２０
ビットを意味し、メイクアップコードの場合には２１１
〜２６ビットを意味するものとなる。

【００２０】以上説明した様に、プロセッサ１に入力さ
れるＭＨ符号によって記憶回路２に記憶されたＭＨ復号
表のアドレス信号を順次修飾し、入力されるＭＨ符号Ｓ
が「Ｆｉｎａｌ」に行き着くまで、「Ｐｏｌｅ」のデー
タによって分枝を繰り返す。

【００２１】図４は図２に示す実施例の動作の概略を示
すフローチャートである。

【００２２】先ず初めに、ＥＯＬ検出後初めに入力され
るランレングスは必ず白であり、かつランレングスは必
ず白と黒の繰り返しであるため、ＭＨ復号表の白又は黒
の上位アドレスをレジスタＨにセットする。次に下位ア
ドレスの初期値（００）１６をレジスタＬにセットする
。 この状態でＭＨ符号Ｓが１ビット入力されると、これを
レジスタＬの最下位ビットに加える。次にレジスタＨ，
Ｌに収納されたデータをアドレス信号として記憶回路２
からＭＨ復号表のデータを読み出し、アキュームレータ
Ａに入力する。そして、該入力データの「Ｐｏｌｅ／Ｆ
ｉｎａｌ」の判定を実行する。

【００２３】「Ｐｏｌｅ／Ｆｉｎａｌ」の判定の結果、
「Ｆｉｎａｌ」の場合にはＤ６〜Ｄ１の内容をランレン
グスとして出力する。「Ｐｏｌｅ／Ｆｉｎａｌ」の判定
の結果、「Ｐｏｌｅ」でしかもデータが（００）１６の
場合、ＥＯＬ検出処理に移行する。「Ｐｏｌｅ」でしか
もデータが（００）１６でない場合には、アキュームレ
ータＡ内のデータをレジスタＬに移し、新たにプロセッ
サ１に入力されるＭＨ符号ＳをレジスタＬの最下位ビッ
トに加える。そして、上記の場合と全く同様にＭＨ復号
表の参照とそのデータの「Ｐｏｌｅ／Ｆｉｎａｌ」判定
を繰り返し実行する。

【００２４】尚、以上の説明ではプロセッサ１及び記憶
回路２を１ワード８ビット単位で構成したが、本発明は
これに限定されるものではなく、９ビット単位以上にし
ても全く同様に実施することができる。

【００２５】

【発明の効果】本発明のＭＨ符号の復号化方法によれば
、ファクシミリ通信の場合を例にして説明すると、ＭＨ
符号が白と黒の各々について１０４個存在し、更に白と
黒の夫々について木構造の分枝点に相当する次のアドレ
スに書き込まれたデータが１０３個（１０４−１＝１０
３）必要になる。そして、ＥＯＬ検出のためにデータ（
００）１６を記憶したアドレスが１個存在する。従って
、本発明のＭＨ符号の復号化方式によれば、ＭＨ復号表
を４１６バイトで実現でき、一般に従来のＭＨ符号の復
号化方式と比較して必要とされる記憶容量を大幅に削減
できる効果を有する。

【００２６】また、本発明のＭＨ符号の復号化方式によ
る復号化処理時間は、入力符号の数に比例し、従来方式
による復号化処理時間とほとんど同じであり、この点で
も優れた効果を有している。

【図面の簡単な説明】

【図１】ＭＨ符号の生成過程を示す木構造の説明図、

【
図２】本発明の一実施例を示すブロック図、

【図３】図
２に示す実施例における記憶回路内のデータ構成を示す
説明図、

【図４】図２に示す実施例の動作の概略を示すフローチ
ャートである。

【符号の説明】

１…プロセッサ（ＣＰＵ）、 ２…記憶回路、 Ａ…アキュームレータ、 Ｈ，Ｌ…レジスタ、 Ｓ…入力ＭＨ符号列。

Claims (1)

【特許請求の範囲】
1. 【請求項１】入力されるモデファイドハフマン符号を枝
   分かれ式に逆変換するための復号表及びモデファイドハ
   フマンの符号生成過程を示す木構造における一つの分枝
   点の下位に位置する二つの分枝点を示すアドレスデータ
   を各アドレスに記憶し、かつ一つの分枝点に下位の分枝
   点が存在しない場合には入力された一連のモデファイド
   ハフマン符号列に対応するランレングス及びターミネイ
   ティングコードかメイクアップコードかの区別を示すデ
   ータを当該アドレスに記憶した記憶回路と、上記入力さ
   れるモデファイドハフマン符号に応じて上記記憶回路に
   記憶された復号表を順次参照して復号化する復号化処理
   手段とを具えたモデファイドハフマン符号の復号化方法
   において、上記復号化処理手段が、レジスタＨ，Ｌ及び
   アキュームレータを含み、上記記憶回路のモデファイド
   ハフマン復号表の白又は黒の上位アドレスを上記レジス
   タＨにセットするステップと、上記モデファイドハフマ
   ン復号表の白又は黒の下位アドレスの初期値を上記レジ
   スタＬにセットするステップと、上記復号化処理手段に
   モデファイドハフマン信号が１ビット入力された時、こ
   れを上記レジスタＬの最下位ビットに加えるステップと
   、上記レジスタＨ，Ｌに収納されたデータをアドレス信
   号として、上記記憶回路からモデファイドハフマン復号
   表のデータを読み出し、該読み出しデータを上記アキュ
   ームレータＡに入力するステップと、該アキュームレー
   タに入力された入力データ（Ｄ０）のＰｏｌｅ／Ｆｏｎ
   ａｌの判定をするステップと、上記判定の結果、Ｐｏｌ
   ｅの時、上記入力データの一部（Ｄ６〜Ｄ１）をランレ
   ングスとして出力するステップと、Ｐｏｌｅでしかもデ
   ータが上記下位アドレスの初期値でない時、上記アキュ
   ームレータＡ内のデータを上記レジスタＬに移すステッ
   プと、上記復号化処理手段に新たに入力されるモデファ
   イドハフマン符号信号Ｓを上記レジスタＬの最下位ビッ
   トに加えるステップと、上記モデファイドハフマン復号
   表の参照及び上記記憶回路からのデータＰｏｌｅ／Ｆｉ
   ｎａｌの判定を繰り返すステップと、からなることを特
   徴とするモデファイドハフマン符号の復号化方法。