JPH0525224B2

JPH0525224B2 -

Info

Publication number: JPH0525224B2
Application number: JP59258476A
Authority: JP
Inventors: Furasaa Rosu Piitaa; Uiriamu Rojaazu Ian; Resurii Arekisandaa Gutsudeinguzu Rupaato
Original assignee: Crosfield Electronics Ltd
Current assignee: Crosfield Electronics Ltd
Priority date: 1983-12-08
Filing date: 1984-12-08
Publication date: 1993-04-12
Also published as: JPS60140981A; DE3481885D1; EP0145396B1; EP0145396A2; EP0145396A3; US4647908A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、符号語システムのデジタル符号語を
復号する方法および装置に関する。

〔従来技術〕

画（文章を含む）の記憶および伝送の分野にお
いては、従来から、行ごとに画を走査し、各行の
色素のランレングスを決定し、この情報を符号化
して記憶空間や伝送時間を最小にしていた。記憶
空間と伝送を最適にするための試みとして工夫さ
れた符号システムの一つがモデイフアイドハフマ
ン（MH）符号システム（modificd Huffman
（MH）code system）であり、これは国際電信
電話諮問委員会（CCITT）が発刊した勧告T.4
「グルーム文書伝送用フアクシミリ装置の標準
化」に説明されている。このシステムの主要な欠
点の一つは、該符号システムの符号語が必ず服従
せねばならぬ規則が、比較的ひんぱんに使用され
ねばならぬ比較的長い符号語の発生を余儀ないも
のとすることである。

〔発明が解決しようとする課題〕

前記の事項は特に、短い符号語が同一システム
のより長い符号語の接頭部（prefix）を形成する
ことがないという規則に関連している。この規則
は、このような符号語の連続する流れの復号を援
助するためのものである。これは、該符号システ
ムの全符号語を復号するために、通常PROM等
の大型の復号マトリツクスを設ける必要があると
いう実用上の問題を生じさせる。高速度の記憶装
置にとつては、このことは高価なかつ大容積のも
のになることである。

米国特許第3701111号は、この問題に対して一
つの提案をしている。これは「制約されたハフマ
ン符号」として知られる特別な符号システムを開
示しており、このシステムにおいて、Ｎに等しい
またはそれより大なる長さを有する符号語は、当
該符号語の長さを示す接頭部を有する。これは遂
行されるべき処理を減る程度簡単化することを可
能にするが、既に使用されている従来のモデイフ
アイドハウマン符号システムを扱うことができる
ような復号システムを提供することがないという
主要な不利益点を有する。この従来技術において
は、符号化システムがまた、制約されたハフマン
符号を発生するように特別に適合されることが必
要になる。

本発明の１つの目的は、相異なる長さのデジタ
ル符号語からなり、短い符号語が同一システムに
おけるより長い符号語の接頭部を形成することが
ない符号語システムのデジタル符号語を復号する
方法において、前記符号語が予め定められた接頭
部を含む符号語のいずれよりも短い該予め定めら
れた接頭部を有するか否かを検出すること；およ
び前記予め定められた接頭部が検出されたか否か
に応じて、それぞれ符号語の接尾部（suffix）の
みを復号するか、または全符号語を復号すること
からなる前記の方法を提供することである。

前記のように、符号語システムの特徴的な性質
として、すべての長い符号語は同一の接頭部を有
することがしばしば認められる。例えば、前記モ
デイフアイドハフマン符号システムにおいて、多
くの長い符号語は、同一の接頭部「0000000」を
有する。

本発明の主な利点の一つは、この発明が、符号
システムまたは符号化回路において変更が要求さ
れることなく、現在の符号システムの符号語を復
号するために使用できることである。さらに、本
発明による方法は、相異なる長さの符号語の少く
とも一つの群が同一の接頭部を有するような符号
システムの符号語を復号するために使用されるこ
とが可能である。従来技術においては、同一の接
頭部は、必ず同一の長さの符号語と共に使用しな
ければならない。このこと自体は、符号システム
の複雑性を増大させる可能性があり、本発明にお
いては不必要なことである。

本発明の他の重要な利点は、復号が２段階で遂
行されることにある。長い符号語が復号されるべ
きときは、接頭部が検出され、次いで接頭部がそ
れ自体により復号される。その代りとして、接頭
部が検出されないときは符号語全体がただちに復
号される。その結果として、復号システムの記憶
装置に対する要求の著しい減少と処理の速度の相
当の増大がもたらされる。

幾つかの例においては、本発明の方法は、さら
に、符号語が予め定められた多数の接頭部の一つ
を有するか否かを検出することに関する。

本発明の方法は、さらに、接尾部が予め定めら
れた接頭部を有するか否かを検出すること、およ
び予め定められた接頭部が検出されたか否かに応
じて、それぞれ符号語の接尾部のサブ接尾部
（sub−suffix）のみを復号するか、または符号語
の全接尾部を復号することに関する。

この手順は、必要に応じ、復号のさらなる層へ
と延長されることができる。この技術は、符号語
長さが領域として発生させられその場合に符号語
長さの各領域について一つのレベルの接尾部をと
もなうときに非常に有効である。

本発明の他の目的は、短い符号語が同一システ
ムにおけるより長い符号語の接頭部を形成するこ
とがない符号語システムの原の符号語を復号する
装置において、前記符号語が予め定められた接頭
部を含む符号語のいずれよりも短い該予め定めら
れた接頭部を有するか否かを検出する手段；およ
び前記予め定められた接頭部が検出されたか否か
に応じて、それぞれ符号語の接尾部のみを復号す
るか、または全符号語を復号する手段からなる前
記装置を提供することにある。

前記復号手段は、必要に応じて全符号語の接頭
部を復号するための第１の手段、および接尾部を
復号するための第２の手段からなることが望まし
い。

通常、前記復号手段には、PROMが設けられ
る。

本発明のシステムのさらに重要な利点は、一般
に前記の符号システムにおいては、より長い符号
語はより短い符号語より、より小なる頻度で発生
することである。従つて接尾部を復号する手段は
ひんぱんに使用されることがないので、接尾部復
号用手段に接頭部復号用手段より、より低速のよ
り安価の要素を使用しても、システム特性には小
なる損失を生ずるのみである。

本発明により達成される相当の単純化の例は、
16ビツトの符号語を復号するについての要求を考
えることにより評価されることができる。従来の
システムにおいては、直接復号用に 2¹⁶×ｍ＝64K×ｍビツトのPROMが必要とされる。しかし本発明による
装置においては、符号語は８ビツトの接尾部とし
再編成され、 2⁸×ｍ＋2⁸×ｍビツトすなわち512×ｍビツトPROMが必要とされる
のみである。

本発明は、「データ符号化」および「符号語検
出」に関するヨーロツパ特許出願公開EP−Ａ−
0149893およびEP−Ａ−0145397において説明さ
れる特許請求された発明と共に使用するに特に適
している。

〔課題を解決するための手段〕

本発明においては、変化する長さをもつデジタ
ルの符号語を有する符号語システムのデジタルの
符号語を復号し、その場合に符号語が同じシステ
ムにおけるより長い符号語の接頭部を形成するこ
とがなく、相異なる長さをもつ符号語の少くとも
１つの群が同じ接頭部を有する符号語システムの
デジタルの符号語を復号する符号語復号方法であ
つて、該方法が、下記の各過程、すなわち、 (i) シフトレジスタ２１に符号語の最初のビツト
が到着したとき、最長の符号語または検出され
るべき所定の符号語部分より少くとも１ビツト
多い長さを有するシフトレジスタ２１は、符号
語の最初のビツトの相補論理をシフトレジスタ
２１の１つの並列入力に印加し、それによりシ
フトレジスタのすべての位置に該相補論理がロ
ードされる過程、 (ii) データを直列的にシフトすることにより第１
の記憶装置２１への流れを形成する過程、 (iii) １つの形式の第１の記憶装置におけるデータ
と、相補の形式の第１の記憶装置におけるデー
タの間の最初の変化の上流にある第１の記憶装
置２１におけるデータが符号語を具備するか、
所定の符号語部分を具備するかを、ロードされ
たビツトに第２の記憶装置２６の１つの位置を
アドレスさせることにより決定する過程であつ
て、該第２の記憶装置が、１つの完全な符号語
データに対応するアドレスをもつ各位置に、復
号された符号語をあらわすデータを包含し、接
頭部に対応するアドレスをもつ各位置に、接頭
部を規定するデータを包含するようになつてい
るもの、 (iv) (a) １つの完全な符号語が第１の記憶装置２
１にロードされたとき第２の記憶装置２６の
アドレスされた位置の内容を読み取り、 (b) １つ接頭部が第１の記憶装置にロードされ
たとき、過程(i)から(iii)までを反復し、ただし
過程(iii)において、書き込まれたビツトが、ア
ドレスが接尾部に対応する各位置において復
号された符号語をあらわすデータを包含する
第２の記憶装置２６の他の部分をアドレスす
るようになつている点でのみ相違し、そし
て、第２の記憶装置２６の該他の部分のアド
レスされた位置における内容を読み取る過
程、を具備することを特徴とする符号語復号方法、
および、変化する長さをもつデジタルの符号語を有す
る符号語システムのデジタルの符号語を復号
し、その場合に符号語が同じシステムにおける
より長い符号語の接頭部を形成することがな
く、相異なる長さをもつ符号語の少くとも１つ
の群が同じ接頭部を有する符号語システムのデ
ジタルの符号語を復号する方法を実行する符号
語装置であつて、該装置が、シフトレジスタ２１であつて、最長の符号語
または検出されるべき所定の符号語部分の長さ
より少くとも１ビツト多い長さを有し、直列お
よび並列入力ポートを有するもの、第１の記憶装置に符号語の最初のビツトが到
着したとき、第１の記憶装置の並列入力ポート
に、符号語の流れの最初のビツトの相補論理を
ロードするロード手段２３，２４、データ流れのなかのデータを第１の記憶装置
２１の直列入力ポートへ直列にシフトされるよ
うに記録させる第１の制御手段２５、１つの完全な符号語データに対応するアドレ
スをもつ各位置において復号された符号語をあ
らわすデータを包含させ接頭部に対応するアド
レスをもつ各位置において接頭部をあらわすデ
ータを包含させるに適合した第２の記憶装置２
６であつて、第２の記憶装置２６の他の部分が
接尾部に対応するアドレスをもつ各位置におい
て復号された符号語を包含させるに適合してい
るもの、および、第１の記憶装置２１にロードされたビツトに
第２の記憶装置２６の１つの位置をアドレスさ
せる第２の制御手段２８であつて、第２の記憶
装置２６のアドレスされた位置における内容に
応答し読み取られるべき内容を復号された符号
語をあらわすものとして読み取らせ、また符号
語の残りのビツトを第１の記憶装置２１にロー
ドさせ、その後に、ロードされたビツトに第２
の記憶装置２６の他の部分をアドレスさせ、該
制御手段２８が接尾部によりアドレスされた第
２の記憶装置の位置における内容を読み取るに
適合しているもの、を具備することを特徴とする符号語復号装置、が
提供される。

〔実施例〕

第１図に基づいて本発明による方法および装置
の実施例を以下に説明する。

第１図は、ハフマン形式の符号語、特に下記の
表に示される符号システムを形成する符号語を復
号するための回路を示す。

〔表〕符号語形式ラン接頭部接尾部Ｔ０ 00001Ｔ１
01Ｔ２ 001Ｔ
３ 100Ｔ４ 110
Ｔ５ 0001Ｔ６
1110Ｔ７ 1111Ｍ
０ 0000000 0001 Ｍ１ 101Ｍ２
000001Ｍ３ 0000001Ｍ
４ 0000000 １Ｍ５ 0000000 01 Ｍ６ 0000000 0000 Ｍ７ 0000000 001 ＭおよびＴは符号語がメークアツプ符号語
（make−up codeword）または終末子符号語
（terminator codeword）であることを示す。

電気的表示を容易にするために、符号語自体は
２進形式であり、すべての終末子符号語は接頭部
のみからなつているが、一部のメークアツプ符号
語は付加的に接尾語を含むことがわかる。

符号システムのいかなる符号語の接頭部も１つ
の完全なより短い符号語と同一ではなく、それに
より、連続的なビツト流れのなかにおいて符号語
が特定的に識別されることが可能になることに、
注意すべきである。

この符号システムは、８の増倍変更子
（mutiplicative modifier）を基礎としている。
本発明は、MHシステムのような付加変更子
（additive modifier）を基礎とする符号システム
と共に使用されるためにも適している。

前記の表から明らかなような、符号語は可変の
長さを有しており、回路２０に沿つて連続形式で
８ビツト入力シフトレジスタ２１に供給される。
他のハフマン形式符号システムを復号することも
できる。唯一の必要条件は、短い符号語がより長
い符号語の接頭部を形成することがないことであ
る。符号語は、MH符号を発生するために従来形
式の遠隔装置から受信されたものであることがで
き、また「データ符号化」に関するヨーロツパ特
許出願（EP−Ａ−0149893）の第１図に示す符号
化装置から受信されたものであることができる。
図示の復号回路は、Crosfield DATRAX 760シ
ステムの一部でもよく、この場合符号は、例えば
文章の走査ランレングスを表す。復号装置の全体
動作は、制御論理２２の制御下にあるが、制御論
理２２と他の回路要素の大部分との接続は、明瞭
化のために、省略されている。

可変長さに符号語を復号することに伴う問題の
一つは、入力レジスタ２１に全体的に、または部
分的に含まれる符号語の開始を決定することにあ
る。この問題は、入力レジスタ２１に新しい符号
語をロードする直前に、先行的ロード制御ラツチ
２３を設定することによつて解決する。先行的ロ
ード制御ラツチ２３の設定は、入力レジスタ２１
の並列的入力を可能にする。符号語を表す入力デ
ータは、インバータ２４を経由して並列的に入力
レジスタ２１にも引火される。入力レジスタ２１
の並列的入力が可能となるので、レジスタ２１に
は、入力符号語の最初のビツトの相補論理
（logical complement）が事前ロードされる。こ
の直後に、つまり１クロツクサイクル後に、事前
制御ラツチ２３はリセツトされ、入力レジスタ２
１のシフト入力が可能となり、入力符号語はクロ
ツク発生器２５の制御の下に連続して入力レジス
タ２１にシフトされる。

入力レジスタ２１の先行的ロードは、入力符号
語の開始を位置決めする効果がある。これは、入
力符号語が入力レジスタ２１内の或る形式のデー
タと相補形式のデータの間の最初の転移において
発生するからである。

理論的には、16ビツトまでのハフマン符号語を
復号するために必要なPROMアドレス空間の量
は、約64Kである。しかしこれは実用的には作動
不可能であり、第１図に示す回路がこの問題に対
する解決策を与える。この解決策は、表に示され
る符号システムにおけるすべての符号語は７ビツ
ト以上の長さをもつており、同一の（予め定めら
れた）接頭部、この場合においては「0000000」
であるもの、を有するという事実を利用する。実
際に、符号システムは、このような特性を有する
ように設計されている。

一つのステツプで符号化される最も長い符号語
または符号語の部分（接頭部）は７ビツトであ
り、従つて入力レジスタは８ビツトの寸法をもつ
ことに注意すべきである。これは要求される最大
の寸法よりも１個だけ大であり、それにより、符
号語または符号語部分の開始の検出が可能になる
（前記したように）。

入力レジスタ２１へのデータのそれぞれのシフ
トの後、レジスタ２１内のデータは、接頭部およ
び接尾部復号PROM２６をアドレス指定するた
めに使用される。

実際には、復号PROMは、それぞれのアクセ
ス可能なアドレスが入力レジスタ２１の内容に対
応するようにプログラムされており、その場合
に、入力レジスタ２１の内容は、以下に述べるよ
うに、該入力レジスタ内の全有効符号語または接
頭部の存在に対応している。

接頭部PROMは最初に入力制御ラツチ２８に
よりエネイブルにされ、アドレスされる。入力レ
ジスタ２１の内容が復号PROM２６により接頭
部と認識されれば、復号PROM２６は、回路２
７上に入力制御ラツチ２８に対して適切な信号
（PREFIX）を送出する。これは順次設定されて、
先行的ロード制御ラツチ２３を設定し、前記した
ように入力レジスタ２１の並列的入力を可能にす
る。入力符号語の残りの部分は、次に、最初の先
行的ロードの後に先行ビツトの相補論理と共に入
力レジスタ２１にシフトされ、それぞれのシフト
の後にクロツク発生器２５によつて制御される。
これによつて入力レジスタ２１の内容は再び復号
PROM２６に印加される。しかし、この場合、
接頭部PROMは入力制御ラツチ２８の設定によ
りエネイブルにされ、一方接頭部PROMは不能
化される。全接頭部がまだ入力レジスタ２１にシ
フトされていないと、接尾部PROMは有効接尾
部を検出せず、シフトが続行する。有効な接尾部
がひとたび検出されると、対応する出力信号
（VALID）が回路２９に沿つて入力制御ラツチ２
８とシーケンス制御器３０に供給され、前記入力
制御ラツチ２８はリセツトされる。入力制御ラツ
チ２８のリセツトは、入力レジスタ２１へのデー
タのシフトを停止し、接頭部PROMをエネイブ
ルにする。

有効接尾部の検出は、全符号語がメークアツプ
符号語かまたは終末子符号語かを示すような信号
（Ｍ／Ｔ）の出力をともない、該信号はマーカ検
出ラツチ３１に送られる。検出された有効符号語
に対応するデータは、接尾部PROMからデータ
レジスタ３２およびマーカ検出ラツチ３１に並列
的に送られる。

接頭部が検出されずその代りにより短い符号語
が検出されると、直ちに接頭部PROMにより復
号され、接頭部PROMは入力制御ラツチ２８の
制御の下にエネイブルのままになり、接尾部の場
合と同様、入力符号語に対応するデータがデータ
レジスタ３２とマーカ検出ラツチ３１とに送ら
れ、「VALID」信号はシーケンス制御器３０と入
力制御２８とに供給され、入力制御２８は符号語
がさらに復号されるの一時的に阻止する。

データレジスタ３２に供給されたデータのそれ
ぞれの部分は、変更子（modifier）の長さに対応
する固定長さを有する。この場合、８の変更子が
使用されており、変更子長さは３である。変更子
長さは、変更子長さカウンタ３３に設定される。
前記変更子長さカウンタ３３は、データレジスタ
３２内のデータが出力レジスタ３４に連続してシ
フトするに従い、シーケンス制御器３０によつて
減少される。このシフトの実行中に、制御論理２
２は、入力制御ラツチ２８に対して入力レジスタ
２１に符号語の次の部分または次の符号語の初め
をロードする許可を与える。入符号語のそれぞれ
の部分が復号されてから、復号されたデータは、
出力レジスタ３４内に全16ビツトが存在するま
で、出力レジスタ３４に連続的にシフトされる。
これらは次に制御論理２２の制御の下に、出力ラ
ツチ３５に並列的にシフトされ、出力ラツチ３５
からデータは所望に応じて記憶装置に供給される
かまたは他の処理手段に供給される。

マーカ検出ラツチ３１は、メークアツプのゼロ
のランレングスの存在を検出し、特に、これがラ
ンの最初のワードとして発生したとき検出が行わ
れる。このことは、実際には発生することがな
く、符号化過程において用いられ、ランレングス
のブロツクの終末が表示される。このようなブロ
ツクマーカの終末が検出されると、シーケンス制
御器３０はマーカ検出ラツチ３１により不能化さ
れる。

【図面の簡単な説明】

第１図は本発明の一実施例としての符号語シス
テムのデジタル符号語を復号する方法を行う回路
のブロツク線図である。２０……符号語入力ライン、２１……入力レジ
スタ、２２……制御論理部、２３…先行的ロード
制御部、２４……インバータ、２５……クロツク
発生器、２６……復号PROM、２８……入力制
御部、３０……シーケンス制御部、３１……マー
カ検出ラツチ、３２……データレジスタ、３３…
…変更子長さのカウンタ、３４……出力レジス
タ、３５……出力ラツチ。

Claims

【特許請求の範囲】１変化する長さをもつデジタルの符号語を有す
る符号語システムのデジタル符号語を復号し、そ
の場合に符号語が同じシステムにおけるよるり長
い符号語の接頭部を形成することがなく、相異な
る長さをもつ符号語の少くとも１つの群が同じ接
頭部を有する符号語システムのデジタルの符号語
を復号する符号語復号方法であつて、該方法が、
下記の各過程、すなわち、 (i) シフトレジスタ２１に符号語の最初のビツト
が到着したとき、最長の符号語または検出され
るべき所定の符号語部分より少くとも１ビツト
多い長さを有するシフトレジスタ２１は、符号
語の最初のビツトの相補論理をシフトレジスタ
２１の１つの並列入力に印加し、それによりシ
フトレジスタのすべての位置に該相補論理がロ
ードされる過程、 (ii) データを直列的にシフトすることにより第１
の記憶装置２１への流れを形成する過程、 (iii) １つの形式の第１の記憶装置におけるデータ
と、相補の形式の第１の記憶装置におけるデー
タの間の最初の変化の上流にある第１の記憶装
置２１におけるデータが符号語を具備するか、
所定の符号語部分を具備するかを、ロードされ
たビツトに第２の記憶装置２６の１つの位置を
アドレスさせることにより決定する過程であつ
て、該第２の記憶装置が、１つの完全な符号語
データに対応するアドレスをもつ各位置に、復
号された符号語をあらわすデータを包含し、接
頭部に対応するアドレスをもつ各位置に、接頭
部を規定するデータを包含するようになつてい
るもの、 (iv)(a) １つの完全な符号語が第１の記憶装置２１
にロードされたとき第２の記憶装置２６のア
ドレスされた位置の内容を読み取り、 (b) １つの接頭部が第１の記憶装置にロードさ
れたとき、過程(i)から(iii)までを反復し、ただ
し過程(iii)において、書き込まれたビツトが、
アドレスが接尾部に対応する各位置において
復号された符号語をあらわすデータを包含す
る第２の記憶装置２６の他の部分をアドレス
するようになつている点でのみ相違し、そし
て、第２の記憶装置２６の該他の部分のアド
レスされた位置における内容を読み取る過
程、を具備することを特徴とする符号語復号方法。２該符号語が所定の接頭部の幾つかのうちの１
つを有するか否かを検出する過程を具備する、特
許請求の範囲第１項に記載の方法。３接尾部が所定の接頭部を有するか否かを検出
し、該所定の接頭部が検出されたか否かに従つて、
符号語の接尾部のサブ接尾部のみまたは符号語の
全接尾部を復号する過程を具備する特許請求の範
囲第１項または第２項に記載の方法。４変化する長さをもつデジタルの符号語を有す
る符号語システムのデジタルの符号語を復号し、
その場合に符号語が同じシステムにおけるより長
い符号語の接頭部を形成することがなく、相異な
る長さをもつ符号語の少くとも１つの群が同じ接
頭部を有する符号語システムのデジタルの符号語
を復号する方法を実行する符号語復号装置であつ
て、該装置が、シフトレジスタ２１であつて、最長の符号語ま
たは検出されるべき所定の符号語部分の長さより
少くとも１ビツト多い長さを有し、直列および並
列入力ポートを有するもの、第１の記憶装置に符号語の最初のビツトが到着
したとき、第１の記憶装置の並列入力ポートに、
符号語の流れの最初のビツトの相補論理をロード
するロード手段２３，２４、データ流れのなかのデータを第１の記憶装置２
１の直列入力ポートへ直列にシフトされるように
記録させる第１の制御手段２５、１つの完全な符号語データに対応するアドレス
をもつ各位置において復号された符号語をあらわ
すデータを包含させ接頭部に対応するアドレスを
もつ各位置において接頭部をあらわすデータを包
含させるに適合した第２の記憶装置２６であつ
て、第２の記憶装置２６の他の部分が接尾部に対
応するアドレスをもつ各位置において復号された
符号語を包含させるに適合しているもの、およ
び、第１の記憶装置２１にロードされたビツトに第
２の記憶装置２６の１つの位置をアドレスさせる
第２の制御手段２８であつて、第２の記憶装置２
６のアドレスされた位置における内容に応答し読
み取られるべき内容を復号された符号語をあらわ
すものとし読み取らさせ、または符号語の残りの
ビツトを第１の記憶装置２６にロードさせ、その
後に、ロードされたビツトに第２の記憶装置２６
の他の部分をアドレスさせ、該制御手段２８が接
尾部によりアドレスされた第２の記憶装置の位置
における内容を読み取るに適合しているもの、を具備することを特徴とする符号語復号装置。５該第２の記憶装置がPROM２６を具備する、
特許請求の範囲第４項記載の装置。