JPS58145274A - モデイフアイド・ホフマン符号復号化方式 - Google Patents
モデイフアイド・ホフマン符号復号化方式Info
- Publication number
- JPS58145274A JPS58145274A JP2734082A JP2734082A JPS58145274A JP S58145274 A JPS58145274 A JP S58145274A JP 2734082 A JP2734082 A JP 2734082A JP 2734082 A JP2734082 A JP 2734082A JP S58145274 A JPS58145274 A JP S58145274A
- Authority
- JP
- Japan
- Prior art keywords
- code
- bit
- codes
- accessed
- decoding
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N1/00—Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof
- H04N1/41—Bandwidth or redundancy reduction
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
本発明は、ファクシミリ装着に利用されているモディフ
ァイド・ホフマン符号（以下Ｍ）（符号と略す）の復号
化方式に関するものである。
ァイド・ホフマン符号（以下Ｍ）（符号と略す）の復号
化方式に関するものである。
ＭＨ符号復号化方式として社、すニアサーチによる方式
、ハツシングによる方式、ツリーサーチによる方式の３
種類が一般的である。リニアサー −ｍ−２、チはテー
ブルアクセス回数が多くなる欠点を有し、〜−−ハツシ
ングはテーブルサイズが大きくなる欠点を有している。
、ハツシングによる方式、ツリーサーチによる方式の３
種類が一般的である。リニアサー −ｍ−２、チはテー
ブルアクセス回数が多くなる欠点を有し、〜−−ハツシ
ングはテーブルサイズが大きくなる欠点を有している。
ツリーサーチはテーブルアクセス回数も少なく、またテ
ーブルサイズの小さいすぐれ丸刃式で、これによるＭＨ
符号の復号化方式はすでに特許５５−１７４５９２で出
願している。しかし、ツリーサーチによるＭＨ符号復号
化方式は、ハツシングによるＭＨ符号復号化方式に比べ
、サーチ回数が多くなる欠点を有している。
ーブルサイズの小さいすぐれ丸刃式で、これによるＭＨ
符号の復号化方式はすでに特許５５−１７４５９２で出
願している。しかし、ツリーサーチによるＭＨ符号復号
化方式は、ハツシングによるＭＨ符号復号化方式に比べ
、サーチ回数が多くなる欠点を有している。
本発明の目的は、ＭＨ符号復号化に際し、テーブルアク
セス回数はハツシング方式による場合と同じで、テーブ
ルサイズはツリーサーチ方式による場合と同じとなるＭ
Ｈ符号復号化方式を提供することにある。
セス回数はハツシング方式による場合と同じで、テーブ
ルサイズはツリーサーチ方式による場合と同じとなるＭ
Ｈ符号復号化方式を提供することにある。
本発明の特徴は、白のＭＨ符号を復号化する場合におい
て、先頭のシンボルから４ビツト目までのシンボルで白
のＭＨ符号のハツシュテーブルをアクセスし、５ビツト
目以降は１ビツト受信する毎に白のＭＨ符号のツリーサ
ーチテーブルをアクセスすることによシ復号化し、黒の
ＭＨ符号を復号化する場合において、先頭のシンボルか
ら２ビツト目までのシンボルで黒のＭＨ符号のハツシュ
テーブルをアクセスし、３ビツト目以降Ｆｉ１ビツト受
信する毎に黒のＭ）ｌ符号のツリーサーチテーブルをア
クセスすることにより復号化したことにある。
て、先頭のシンボルから４ビツト目までのシンボルで白
のＭＨ符号のハツシュテーブルをアクセスし、５ビツト
目以降は１ビツト受信する毎に白のＭＨ符号のツリーサ
ーチテーブルをアクセスすることによシ復号化し、黒の
ＭＨ符号を復号化する場合において、先頭のシンボルか
ら２ビツト目までのシンボルで黒のＭＨ符号のハツシュ
テーブルをアクセスし、３ビツト目以降Ｆｉ１ビツト受
信する毎に黒のＭ）ｌ符号のツリーサーチテーブルをア
クセスすることにより復号化したことにある。
次に、本発明に係る一実施列を各図を参照して説明する
。
。
＠１図は、黒のＭＨ符号をバイナリ−ツリーに展開した
ものである。各校の上の１およびＯは受信した符号を表
す。ｏ＃−１ｔｉだ符号として完結していない中間節点
を表し、◎は符号として完結した終端節点を表す。この
バイナリ−ツリーを用い九Ｍ）（符号の復号化方法は、
特許５５−１７４５９２！に祥しく説明されているので
ここでは簡単に説明する。第１図のバイナリ−ツリーの
テーブルをメモリ上に実現するには、各節点にそれぞれ
アドレスを割ｇ当て、各アドレスが示すメモリには、そ
の節点が中間節点に属するのか終端節点に属するのかを
識別する情報と、中間節点に属する場合は次にアクセス
すべき節点に＃当するアドレス情報を、終端節点に属す
る場合はその符号が意味するランレングス（以下ＲＬと
略す）を記憶させればよい。以下、黒画素のランレング
スが３であることを意味する黒のＭＨ符号「１０」を復
号化する場合を的に説明する。「１」を受信し走時点に
おりて、■をアクセスし、［Ｆ］が中間節点であること
をＶ！識し、次にアクセスすべき節点■および■のアド
レス情報を得る。次に「０」を受信した時点において、
■をアクセスし走時点において得たアドレス情報を元に
、■をアクセスし、Ｒ，Ｌ＝３ｔ−得て復号化を終了す
る。仁のように、バイナリ−ツリーを用いた復号化方法
は、符号語長と等しい回数だけテーブルをアクセスする
と復号化できる。
ものである。各校の上の１およびＯは受信した符号を表
す。ｏ＃−１ｔｉだ符号として完結していない中間節点
を表し、◎は符号として完結した終端節点を表す。この
バイナリ−ツリーを用い九Ｍ）（符号の復号化方法は、
特許５５−１７４５９２！に祥しく説明されているので
ここでは簡単に説明する。第１図のバイナリ−ツリーの
テーブルをメモリ上に実現するには、各節点にそれぞれ
アドレスを割ｇ当て、各アドレスが示すメモリには、そ
の節点が中間節点に属するのか終端節点に属するのかを
識別する情報と、中間節点に属する場合は次にアクセス
すべき節点に＃当するアドレス情報を、終端節点に属す
る場合はその符号が意味するランレングス（以下ＲＬと
略す）を記憶させればよい。以下、黒画素のランレング
スが３であることを意味する黒のＭＨ符号「１０」を復
号化する場合を的に説明する。「１」を受信し走時点に
おりて、■をアクセスし、［Ｆ］が中間節点であること
をＶ！識し、次にアクセスすべき節点■および■のアド
レス情報を得る。次に「０」を受信した時点において、
■をアクセスし走時点において得たアドレス情報を元に
、■をアクセスし、Ｒ，Ｌ＝３ｔ−得て復号化を終了す
る。仁のように、バイナリ−ツリーを用いた復号化方法
は、符号語長と等しい回数だけテーブルをアクセスする
と復号化できる。
第２図は、黒のＭＨ符号のハツシュテーブルを表してい
る。黒のＭＨ符号の最小符号語長は２である。そこで、
黒のＭＨ符号の先頭と２ビツトのシンボルをアドレスと
し、各アドレスの示すメモリに第１図ｑｐ、■、■、■
に該当する情報を記憶させ友ハツシュテーブルを作成す
る。このハツシュテーブルを用いてＭＨ符号を復号化す
る方法を、黒のＭ）（符号「１０」を例に説明する。ま
ず続けて２ビット受信し、受信したシンボル列「１０」
を元に、ハツシュテーブルのアドレスｌＯをアクセスす
る。このアドレスの示すメモリには、終端節点であると
いう情報と、ＲＬ、、３という情報が記憶されておシ、
復号化が終了する。
る。黒のＭＨ符号の最小符号語長は２である。そこで、
黒のＭＨ符号の先頭と２ビツトのシンボルをアドレスと
し、各アドレスの示すメモリに第１図ｑｐ、■、■、■
に該当する情報を記憶させ友ハツシュテーブルを作成す
る。このハツシュテーブルを用いてＭＨ符号を復号化す
る方法を、黒のＭ）（符号「１０」を例に説明する。ま
ず続けて２ビット受信し、受信したシンボル列「１０」
を元に、ハツシュテーブルのアドレスｌＯをアクセスす
る。このアドレスの示すメモリには、終端節点であると
いう情報と、ＲＬ、、３という情報が記憶されておシ、
復号化が終了する。
符号語長が３ビツト以上の黒のＭＨ符号の場合は、３ビ
ツト目からは１ビツト受信することに第１図に示したバ
イナリ−ツリーのテーブルをアクセスすることによシ復
号化する。以上の説明から明らかなように、黒のＭＨ符
号の場合、ハツシュテーブルとバイナリ−ツリーテーブ
ルを用いた復号化方法では、符号語長よシ１少ないテー
ブルアクセス回数で復号化することができる。同様に、
白のＭＨ符号の場合は、最小符号語長が４ビツトである
丸め、符号の先頭から４ビツト目までのシンポ四列をア
ドレスとする白のハツシュテーブルを作成する。白のＭ
Ｈ符号を復号化する場合、続けて４ビット受信し、受信
し九シンボル列で白のハツシュテーブルをアクセスしす
る。符号語長が４ビツトの白のＭＨ符号の場合は、この
時点で復号化が終了する。符号語長が５ビツト以上の場
合は、５ビツト目からＦｉ１ビット受信する毎にバイナ
リ−ツリーのテーブルをアクセスすることにょシ復号化
する。よって白のＭＨ符号の場合、ハツシュテーブルと
バイナリ−ツリーテーブルを用かで復号すれば、符号語
長より３少ない回数だけテーブルをアクセスすると復号
化できる。
ツト目からは１ビツト受信することに第１図に示したバ
イナリ−ツリーのテーブルをアクセスすることによシ復
号化する。以上の説明から明らかなように、黒のＭＨ符
号の場合、ハツシュテーブルとバイナリ−ツリーテーブ
ルを用いた復号化方法では、符号語長よシ１少ないテー
ブルアクセス回数で復号化することができる。同様に、
白のＭＨ符号の場合は、最小符号語長が４ビツトである
丸め、符号の先頭から４ビツト目までのシンポ四列をア
ドレスとする白のハツシュテーブルを作成する。白のＭ
Ｈ符号を復号化する場合、続けて４ビット受信し、受信
し九シンボル列で白のハツシュテーブルをアクセスしす
る。符号語長が４ビツトの白のＭＨ符号の場合は、この
時点で復号化が終了する。符号語長が５ビツト以上の場
合は、５ビツト目からＦｉ１ビット受信する毎にバイナ
リ−ツリーのテーブルをアクセスすることにょシ復号化
する。よって白のＭＨ符号の場合、ハツシュテーブルと
バイナリ−ツリーテーブルを用かで復号すれば、符号語
長より３少ない回数だけテーブルをアクセスすると復号
化できる。
ま九、第２図に示すハツシュテーブルは、第１図で不用
となった節点■、■、■、■、■、■に該当するメモリ
で十分作成できる。よってハツシュテーブルによるメモ
リの増加は全くない。
となった節点■、■、■、■、■、■に該当するメモリ
で十分作成できる。よってハツシュテーブルによるメモ
リの増加は全くない。
第３図は、本発明を実現する復号器の構成列である。１
はＣＰ Ｕ （（：ｅｎｔｒａｌ Ｐｒｏｅｅｓｓｏｒ
ｕｎｉｔ）で、マイクロコンビエーメ尋から成る。２
はＦ Ｉ ＦＱ （Ｆｉｒｓｓｔ Ｉｎ Ｆｉｒｓｔ
Ｏｕｔ ） ｌモｌＪテ、受信したＭ）？符号を一時
記憶するものである。３および６はＩ ／ Ｏ（Ｉｎｐ
ｕｔ ／ ０ｕｔｐｕｔ）でＣＰＵＩの周辺装噴を結ぶ
入出力装置である。４は本発明の復号化方法を記憶した
プログラム用メモリで、５は本発明で用いたハツシュテ
ーブルとバイナリ−ツリーテーブルを記憶したテーブル
用メモリである。７はＲ，Ｌ回路で、カウンタ等から成
９、Ｒ，Ｌを人力するとＲＬと等しい数の書き込みクロ
ックを発生させる４のである。８はラインメモリで、ａ
ｔ勺化され九ｍｆｌｌ信号を記憶するものである。
はＣＰ Ｕ （（：ｅｎｔｒａｌ Ｐｒｏｅｅｓｓｏｒ
ｕｎｉｔ）で、マイクロコンビエーメ尋から成る。２
はＦ Ｉ ＦＱ （Ｆｉｒｓｓｔ Ｉｎ Ｆｉｒｓｔ
Ｏｕｔ ） ｌモｌＪテ、受信したＭ）？符号を一時
記憶するものである。３および６はＩ ／ Ｏ（Ｉｎｐ
ｕｔ ／ ０ｕｔｐｕｔ）でＣＰＵＩの周辺装噴を結ぶ
入出力装置である。４は本発明の復号化方法を記憶した
プログラム用メモリで、５は本発明で用いたハツシュテ
ーブルとバイナリ−ツリーテーブルを記憶したテーブル
用メモリである。７はＲ，Ｌ回路で、カウンタ等から成
９、Ｒ，Ｌを人力するとＲＬと等しい数の書き込みクロ
ックを発生させる４のである。８はラインメモリで、ａ
ｔ勺化され九ｍｆｌｌ信号を記憶するものである。
ＣＰＵＩはｌ１０３を通してＦＩＦｏ２からＭＨ符号を
受信し、第１図および第２図を用いて説明した方法でハ
ツシュ−テーブルとバイナリ−テーブルを記憶したテー
ブル用メモリ５をアクセスすることによりＢ、Ｌに復号
化し、Ｂ、Ｌ回路７にはｌ１０６を通じて復号化し九Ｒ
Ｌを出力し、ラインメモリ８には白か黒かの色信号を出
力する。これによりラインメモリ８には元の画偉信号が
復元できる。
受信し、第１図および第２図を用いて説明した方法でハ
ツシュ−テーブルとバイナリ−テーブルを記憶したテー
ブル用メモリ５をアクセスすることによりＢ、Ｌに復号
化し、Ｂ、Ｌ回路７にはｌ１０６を通じて復号化し九Ｒ
Ｌを出力し、ラインメモリ８には白か黒かの色信号を出
力する。これによりラインメモリ８には元の画偉信号が
復元できる。
本発明によれば、白のＭＨ符号の場合は符号語長より３
少ないアクセス回数で復号化でき、黒のＭＨ符号の場合
は符号語長よシ１少ないアクセス回数で復号化できるの
で、高速にＭＨ符号を復号化できるという効果がある。
少ないアクセス回数で復号化でき、黒のＭＨ符号の場合
は符号語長よシ１少ないアクセス回数で復号化できるの
で、高速にＭＨ符号を復号化できるという効果がある。
第１図は、黒のＭＨ符号をバイナリ−ツリ〜に展開し九
部分図、第２図は、黒のＭＨ符号のハツシュテーブルの
内容説明図、第３図は、本発明の一実施的に供されるＭ
）Ｉ符号の復号器の例示回路ブロック図である。 １・ＣＰＵ、 ２・ＦＩＦｏ、 ３・Ｉｌｏ、 ４・・
・プログラム用メモリ、訃・・テーブル用メモリ、６・
・・第１ 目 茅２日
部分図、第２図は、黒のＭＨ符号のハツシュテーブルの
内容説明図、第３図は、本発明の一実施的に供されるＭ
）Ｉ符号の復号器の例示回路ブロック図である。 １・ＣＰＵ、 ２・ＦＩＦｏ、 ３・Ｉｌｏ、 ４・・
・プログラム用メモリ、訃・・テーブル用メモリ、６・
・・第１ 目 茅２日
Claims (1)
- １、モディファイド・ホフマン符号（以下ＭＨ符号と略
す）復号化に際し、ハツシングテーブルとツリーサーチ
テーブルの２種類の復号化のためのテーブルを設け、白
のＭＨ符号の場合は符号の先頭から４ビツト目までのシ
ンボルでハツシングテーブルをアクセスし、５ビツト目
以降はツリーサーチテーブルをアクセスすることによシ
復号化し、黒のＭＨ符号の場合は符号の先頭から２ビツ
ト目までのシンボルでハツシングテーブルをアクセスし
、３ビツト目以降はツリーサーチテーブルをアクセスす
ることによシ復号化することを特徴とするモディファイ
ド・ホフマン符号復号化方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2734082A JPS58145274A (ja) | 1982-02-24 | 1982-02-24 | モデイフアイド・ホフマン符号復号化方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2734082A JPS58145274A (ja) | 1982-02-24 | 1982-02-24 | モデイフアイド・ホフマン符号復号化方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS58145274A true JPS58145274A (ja) | 1983-08-30 |
Family
ID=12218319
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2734082A Pending JPS58145274A (ja) | 1982-02-24 | 1982-02-24 | モデイフアイド・ホフマン符号復号化方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS58145274A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2002252563A (ja) * | 2001-02-23 | 2002-09-06 | Yamaha Corp | ハフマン符号の復号方法、復号装置、ハフマン符号復号用テーブルおよびその作成方法 |
-
1982
- 1982-02-24 JP JP2734082A patent/JPS58145274A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2002252563A (ja) * | 2001-02-23 | 2002-09-06 | Yamaha Corp | ハフマン符号の復号方法、復号装置、ハフマン符号復号用テーブルおよびその作成方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US3675211A (en) | Data compaction using modified variable-length coding | |
| US4099257A (en) | Markov processor for context encoding from given characters and for character decoding from given contexts | |
| KR940006020A (ko) | 가변장-코드로 엔코드된 신호의 디코딩 장치 | |
| KR930020997A (ko) | 디지탈 통신시스템용 가변길이 코드워드 디코드 | |
| US4896353A (en) | Apparatus for fast decoding of a non-linear code | |
| JPS60140981A (ja) | 符号語システムのデジタル符号語を復号する方法および装置 | |
| JPH0352268B2 (ja) | ||
| JPS60140982A (ja) | デジタル符号語を検出する方法および装置 | |
| EP0647034B1 (en) | A variable word length code decoding method, and a decoder for performing the same | |
| JPH033440B2 (ja) | ||
| JPS60105040A (ja) | 文章検索方式 | |
| JP3229690B2 (ja) | 可変長符号復号器 | |
| JPH0255987B2 (ja) | ||
| JP2000261803A (ja) | 画像情報の符号化方法及び復号化方法 | |
| JPH0377708B2 (ja) | ||
| JPS6345976A (ja) | 画像復号器 | |
| JP2757716B2 (ja) | ハフマン符号復号回路 | |
| JPH04100324A (ja) | 可変長符号の復号方式 | |
| JPH0490267A (ja) | 可変長符号の復号回路 | |
| JP2556160B2 (ja) | 圧縮符号伸長装置 | |
| JP3138342B2 (ja) | 可変長符号の復号装置 | |
| JP3009007B2 (ja) | ２元符号復号回路 | |
| JPS63269623A (ja) | 圧縮デ−タデコ−ド装置 | |
| JPH04358419A (ja) | 復号化装置 | |
| JPS5943863B2 (ja) | モデフアイドハフマン符号の復号化方式 |