(57)【要約】      （修正有）【課題】ハフマン符号化されたデータの復号を、迅速かつ簡易に行うことのできるハフマン符号化／復号化装置を提供する。【解決手段】ハフマン符号化装置はハフマン木データを用いて符号化を行い、ハフマン復号装置は、ハフマン木データ取得手段と、符号化データ取得手段と、復号手段とを備え、復号語の中で最も大きい値よりも大きいアドレスに記憶されており、各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語が記憶されたハフマン木データに基づき、符号化データを復号する。【選択図】図４
2005252813.tif 000002
【特許請求の範囲】
【請求項１】
ハフマン符号化されたデータを復号する装置であって、
所定の値より大きいアドレスに記憶されるとともに、各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語が記憶されたハフマン木データを取得するハフマン木データ取得手段と、
符号化データを順次取得する符号化データ取得手段と、
前記符号化データ取得手段が取得した前記符号化データに基づき前記ハフマン木データを探索し、該当するデータが前記所定の値より大きければ、次の復号化データに基づきさらに前記ハフマン木データを探索し、該当するデータが前記所定の値以下であれば当該データを復号語として復号を行う復号手段と、
を含むことを特徴とするハフマン復号装置。
【請求項２】
請求項１に記載のハフマン復号装置において、
前記所定の値は、前記復号語の中で最も大きい数であることを特徴とするハフマン復号装置。
【請求項３】
請求項１または２に記載のハフマン復号装置において、
前記復号手段は、前記符号化データに基づき前記ハフマン木データを探索することにより得られたデータの値が前記所定の値以下か否かを判断する判断手段を含むことを特徴とするハフマン復号装置。
【請求項４】
データを、ハフマン木データを用いてハフマン符号化する装置であって、
前記ハフマン木データの各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語を記憶するとともに、当該ハフマン木データを前記復号語の中で最も大きい値よりも大きいアドレスに記憶するハフマン木データ作成手段を含むことを特徴とするハフマン符号化装置。
【請求項５】
ハフマン符号化に用いられるハフマン木データであって、
復号語の中で最も大きい値よりも大きいアドレスに記憶されており、各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語が記憶されたことを特徴とするハフマン木データ。
【請求項６】
コンピュータに、ハフマン符号化されたデータを復号させるためのプログラムであって、
コンピュータを、
所定の値より大きいアドレスに記憶されるとともに、各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語が記憶されたハフマン木データを取得するハフマン木データ取得手段、
符号化データを順次取得する符号化データ取得手段、
前記符号化データ取得手段が取得した前記符号化データに基づき前記ハフマン木データを探索し、該当するデータが前記所定の値より大きければ、次の復号化データに基づきさらに前記ハフマン木データを探索し、該当するデータが前記所定の値以下であれば当該データを復号語として復号を行う復号手段、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハフマン復号装置、ハフマン符号化装置、およびハフマン木データに関する。
【背景技術】
【０００２】
ＲＯＭ書換装置を用いて情報機器のフラッシュＲＯＭにプログラムを新規に書き込んだり書き換えたりする際に、ＲＯＭ書換装置の容量がプログラムの容量よりも小さい場合、従来は２回にわけて書き換えたり、２台のＲＯＭ書換装置を用いて書き換えたりする必要があった。このような場合に、プログラムを圧縮してＲＯＭ書換装置に記憶しておき、転送後に展開することにより、ＲＯＭ書換装置の容量が小さいままでも、複数回にわけて書き換えを行う手間を省くことができる。
【０００３】
ところで、データを圧縮するアルゴリズムとして、静的ハフマン符号が知られている。従来、ハフマン符号化された圧縮データを復号する際には、復号データ、符号長、および符号語を参照する必要があり、参照データの容量が大きくなってしまうという問題があった。また、静的ハフマン符号においては、ビット毎にハフマン木をたどって復号データを探し当てるため、復号に時間がかかるという問題もあった。
【０００４】
このような問題に鑑み、特許文献１には、二分木のリーフに格納されているデータに対応する復号データと、その出力を制御するフラグからなる語と、二分木のリーフが接続されていないノードに対応し、その下位に接続されるノードのうちの一方に対応する語のアドレスと該アドレスに分岐するか否かを制御するフラグからなる語が記憶されたテーブルを用いてハフマン符号を復号する方法が記載されている。
【特許文献１】特開２００２−２５２５６３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１に記載された方法でも、各アドレスのデータには、次の処理の内容を示すフラグが付され、フラグを参照することにより復号化が行われており、処理手順が複雑だという問題があった。
【０００６】
本発明はこうした点に鑑みてなされたもので、その目的は、ハフマン符号化されたデータの復号を迅速かつ簡易に行うことのできる技術を提供することにある。
【課題を解決するための手段】
【０００７】
本発明によれば、ハフマン符号化されたデータを復号する装置であって、所定の値より大きいアドレスに記憶されるとともに、各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語が記憶されたハフマン木データを取得するハフマン木データ取得手段と、符号化データを順次取得する符号化データ取得手段と、符号化データ取得手段が取得した符号化データに基づきハフマン木データを探索し、該当するデータが所定の値より大きければ、次の復号化データに基づきさらにハフマン木データを探索し、該当するデータが所定の値以下であれば当該データを復号語として復号を行う復号手段と、を含むことを特徴とするハフマン復号装置が提供される。
【０００８】
ここで、符号化データ取得手段は、符号化データを１ビットずつ取得することができる。復号手段は、符号化データ取得手段が取得した符号化データ１ビットに基づき、ハフマン木データを探索し、復号語にたどり着くまで同様の処理を繰り返す。復号語にたどり着いたら復号を行い、次の符号化データに基づき、ハフマン木データを再度探索する。
【０００９】
本発明のハフマン復号装置によれば、各ノードの分木データとして子ノードが記憶されたアドレスが記憶されているので、復号を迅速に行うことができる。また、ハフマン木データが所定の値より大きいアドレスに記憶されているので、データの大きさに基づき、該当するデータが復号語なのか子ノードのアドレスなのかを検知することができ、ハフマン木データを簡略化することもできる。
【００１０】
本発明のハフマン復号装置において、所定の値は、復号語の中で最も大きい数とすることができる。
本発明のハフマン復号装置において、復号手段は、符号化データに基づきハフマン木データを探索することにより得られたデータの値が所定の値以下か否かを判断する判断手段を含むことができる。
【００１１】
本発明によれば、データを、ハフマン木データを用いてハフマン符号化する装置であって、ハフマン木データの各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語を記憶するとともに、当該ハフマン木データを復号語の中で最も大きい値よりも大きいアドレスに記憶するハフマン木データ作成手段を含むことを特徴とするハフマン符号化装置が提供される。
【００１２】
本発明によれば、ハフマン符号化に用いられるハフマン木データであって、復号語の中で最も大きい値よりも大きいアドレスに記憶されており、ハフマン木データの各ノードの分木データとして、子ノードが記憶されたアドレスまたは復号語が記憶されたことを特徴とするハフマン木データが提供される。このようなハフマン木データを用いることにより、符号化データを迅速に復号することができる。
【００１３】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラム等の間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１４】
本発明によれば、ハフマン符号化されたデータの復号を迅速かつ簡易に行うことができる。
【発明を実施するための最良の形態】
【００１５】
本実施の形態において、ハフマン符号化装置およびハフマン復号装置は、ネットワークファクシミリ装置、ＭＦＰ（Multi Functional Peripheral）などのファクシミリ装置、およびファクシミリ装置に装着されたＲＯＭ書換装置により実現される。
【００１６】
図１は、本実施の形態におけるファクシミリ装置１０およびファクシミリ装置１０に装着されたＲＯＭ書換装置１１の構成を示すブロック図である。ここで、本発明の本質に関わらない部分の構成については省略してある。
【００１７】
ファクシミリ装置１０およびＲＯＭ書換装置１１の各構成要素は、ハードウエアコンポーネントでいえば、任意のコンピュータのＣＰＵ、メモリ、メモリにロードされた本図の構成要素を実現するプログラム、そのプログラムを格納するハードディスク等の記憶ユニット、ネットワーク接続用インターフェース、ファクシミリ通信用モデム等を中心に実現されるが、その実現方法、装置にはいろいろな変形例があることは、当業者には理解されるところである。これから説明する各図は、ハードウエア単位の構成ではなく、機能単位のブロックを示している。
【００１８】
本実施の形態において、ＲＯＭ書換装置１１は、ファクシミリ装置１０の被書換領域１８を書き換えるための書換プログラムコード、および書き換えるべきデータを記憶するデータ記憶領域１６を含む。ここで図示していないが、ファクシミリ装置１０のＣＰＵがデータ記憶領域１６に記憶された書換プログラムコードを実行することにより、ハフマン符号化装置１２およびハフマン復号装置１４の機能が実現される。
【００１９】
ハフマン符号化装置１２は、被書換領域１８を書き換えるべきデータを符号化する。データ記憶領域１６は、ハフマン符号化装置１２により符号化されたデータを記憶する。ハフマン復号装置１４は、ハフマン符号化装置１２により符号化されたデータを復号する。なお、他の例において、ハフマン符号化装置１２は、ファクシミリ装置１０およびＲＯＭ書換装置１１以外の装置に設けられ、ＲＯＭ書換装置１１には予め符号化された圧縮データが入力され、データ記憶領域１６に記憶するようにすることもできる。
【００２０】
図２は、ハフマン符号化装置１２により符号化された圧縮データの構造を示す図である。  本実施の形態において、圧縮データ（符号化データ）は、所定の値より大きいアドレスに記憶される。所定の値は、ハフマン符号化された圧縮データに含まれる復号データの中で最も大きい値とすることができる。ここでは、データ先頭アドレスが「８０００００００」、ＲＯＭサイズが４ＭＢ（４ＭビットＲＯＭ８個分）の機種で、圧縮データが２ＭＢ（４セクション×５１２ｋＢ）になる場合のアドレスマップを示す。
【００２１】
圧縮データは、圧縮データ識別マークと、データのサイズ（圧縮データセクション数）と、各圧縮データ末尾アドレスと、各チェックサムと、ハフマン木データと、および圧縮データとを含む。各圧縮データ末尾アドレスおよび各チェックサムは、符号化データを復号した後に、復号が正しく行われたか否かを判断するために用いられる。
【００２２】
ハフマン符号化された圧縮データには、データの先頭に識別マーク“ＳＨＣ”が付される。これにより、データがハフマン符号化されたものか否かを検知することができる。ハフマン復号装置１４は、入力されたデータに識別マーク“ＳＨＣ”が含まれる場合、ハフマン復号処理を開始する。
【００２３】
圧縮エリア末尾アドレスとしては、それぞれのセクションのデータを圧縮・パッケージング完了時に圧縮データ上で参照されていたアドレスが記録される。
【００２４】
チェックサムは、セクション毎の１６ビットビッグエンディアンのチェックサムである。このようなチェックサムをデータ内に組み込むことにより、書き換えコード自体がデータチェックを行うことができ、作業時間を大幅に短縮することができる。
【００２５】
図３は、ハフマン木データを示す図である。図３（ａ）はハフマン木データの構造、図３（ｂ）はハフマン木の一例を示す図である。
【００２６】
たとえば、８ビットコードのハフマン木の場合、ハフマン木は、２５５個のノードと２５６個の終端とにより構成される。
【００２７】
図３（ａ）に示すように、本実施の形態において、ハフマン木データは、各ノードのアドレスとそのノードから０（ゼロ）または１に枝分かれした後の分木データとが対応付けられている。ここで、分木データとしては、子ノードが記憶されたアドレスそのもの、または復号語が記憶される。
【００２８】
たとえば、アドレス「８０００００３４」のノードがゼロに枝分かれした分木データは「８０００００３８」、１に枝分かれした分木データは「８０００００３Ｃ」である。また、アドレス「８０００００３８」のノードがゼロに枝分かれした分木データは「００００００００」、１に枝分かれした分木データは「００００００ＦＦ」である。
【００２９】
本実施の形態において、復号語は、０〜２５５の整数である。ハフマン木データは、２５５より大きい値のアドレスに記憶されている。そのため、ハフマン復号装置１４は、分木データの大きさに基づき、そのデータが子ノードのアドレスであるか、復号語であるかを判断することができる。
【００３０】
たとえば、アドレス「８０００００３４」のノードの分木データ「８０００００３８」は、２５５より大きい値なので、ハフマン復号装置１４は、この分木データが子ノードのアドレスであると判断する。そこで、ハフマン復号装置１４は、次の圧縮データの値が「ゼロ」か「１」かによって、アドレス「８０００００３８」の分木データに進む。
【００３１】
ここで、たとえば次の圧縮データの値が「ゼロ」の場合、分木データは「００００００００」である。ここで、「００００００００」は２５５以下なので、ハフマン復号装置１４は、この分木データが復号語であると判断する。
【００３２】
図３（ｂ）は、図３（ａ）に示したハフマン木データに基づき形成されたハフマン木である。圧縮データが「００」の場合、分木データ「００ｈ（００００００００）」で終端する。また、圧縮データが「０１」の場合、分木データ「ＦＦｈ（００００００ＦＦ）」で終端する。
【００３３】
図８は、図１に示したハフマン復号装置１４およびデータ記憶領域１６の構成を詳細に示すブロック図である。ハフマン復号装置１４は、符号化データ取得部１４ａと、判断部１４ｂと、変換部１４ｃとを含む。データ記憶領域１６には、符号化データ１６ａおよびハフマン木データ１６ｂが記憶される。符号化データ取得部１４ａは、データ記憶領域１６から符号化データ１６ａを１ビットずつ順次取得する。判断部１４ｂは、符号化データ取得部１４ａが取得した符号化データに基づき、ハフマン木データ１６ｂを探索し、該当するデータが所定の値より大きいか否かを判断する。判断部１４ｂは、データが所定の値より大きい場合、そのデータは子ノードのアドレスを示していると判断して次の符号化データに基づき、さらにハフマン木データ１６ｂを探索する。判断部１４ｂは、該当するデータが所定の値以下となるまでこの処理を繰り返す。該当するデータが所定の値以下となると、判断部１４ｂは、そのデータが復号語であると判断する。変換部１４ｃは、復号を行い、復号データを被書換領域１８に転送する。
【００３４】
図４は、圧縮データの作成手順を示すフローチャートである。これらの処理はハフマン符号化装置１２が行う。
まず、ＲＯＭサイズからＲＯＭ個数Ｎを換算する（Ｓ１０）。つづいて、入力データに含まれる符号化要素の発生頻度に応じて符号語を決定する（Ｓ１２）。この手順は公知の方法であるので、詳細な説明を省略する。その後、ステップＳ１０で求めたＮに基づき、圧縮データ末尾アドレス格納領域、チェックサム格納領域、およびハフマン木データ格納領域を算出する（Ｓ１６）。つづいて、ハフマン木インデックスを作成する（Ｓ１８）。この処理については後述する。
【００３５】
その後以下の処理をＮ回繰り返す。まず、５１２ｋＢのデータについて、サムを積算しながらハフマン符号化する（Ｓ２０）。つづいて、５１２ｋＢのデータ終了時の圧縮データ格納先アドレスおよび圧縮元データのチェックサムを所定の領域に記録する（Ｓ２２）。その後、圧縮データ格納先アドレスが４バイトの倍数になるまでビット０（ゼロ）で埋める（Ｓ２４）。また、ここで、チェックサムもゼロクリアする。以上の処理をＮ回行った後、全データサイズが５１２ｋＢの倍数になるまで末尾を０（ゼロ）で埋める（Ｓ２６）。これにより、図２に示したような圧縮データが作成される。
【００３６】
図５は、図４のステップＳ１８に示したハフマン木インデックスの作成手順を詳細に示すフローチャートである。
まず、符号語の一部をなす二進数列である引数Ｃを取得する（Ｓ３０）。つづいて、ノード情報保持インデックスをｂに確保する（Ｓ３２）。つづいて、Ｃ＋’０’が符号語か否かを判断する（Ｓ３４）。符号語か否かの判断は、Ｃに’０’を加えた二進数列（たとえばＣ＝“０１０”の場合、“０１００”）について、２５６個のハフマン符号と総比較することにより行う。ここで、Ｃ＋’０’が符号語の場合（Ｓ３４のＹ）、アドレスｂに対応する復号語を格納する（Ｓ３６）。一方、ステップＳ３４において、Ｃ＋’０’が符号語でない場合（Ｓ３４のＮ）、Ｂ＋８をＢとして、未登録のノードインデックスのアドレスＢを獲得する（Ｓ３８）。つづいて、アドレスｂにＢを格納する（Ｓ４０）。つづいて、Ｃ＋’０’を引数にして自己呼び出しを行う（Ｓ４２）。
【００３７】
つづいて、Ｃ＋’１’が符号語か否かを判断する（Ｓ４４）。ここで、Ｃ＋’１’が符号語の場合（Ｓ４４のＹ）、アドレス（ｂ＋４）に対応する復号語を格納する（Ｓ４６）。一方、ステップＳ４４において、Ｃ＋’１’が符号語でない場合（Ｓ４４のＮ）、Ｂ＋８をＢとして、未登録のノードインデックスのアドレスＢを獲得する（Ｓ４８）。つづいて、アドレスｂ＋４にＢを格納する（Ｓ５０）。つづいて、Ｃ＋’１’を引数にして自己呼び出しを行う（Ｓ５２）。以上によりハフマン木インデックスが作成される。
【００３８】
図６は、図４および図５を参照して説明した手順により作成された圧縮データを復号する手順を示すフローチャートである。これらの処理は、ハフマン復号装置１４が行う。
ハフマン復号装置１４は、データを受け取ると、データの先頭に識別マーク”ＳＨＣ”が含まれるか否かを判断する（Ｓ６０）。ここで、識別マーク”ＳＨＣ”が含まれない場合（Ｓ６０のＮ）、通常の書き換え処理を行う。一方、ステップＳ６０で識別マーク”ＳＨＣ”が含まれる場合（Ｓ６０のＹ）、以下の復号化処理を行う。まず、４バイト目のデータをセクション数Ｎとして記憶する（Ｓ６２）。つづいて、Ｎに基づき、圧縮データ末尾アドレス格納領域、チェックサム格納領域、ハフマン木データ格納領域、を算出する（Ｓ６４）。つづいて、以下の処理をＮ回繰り返す。まず、５１２ｋＢのデータを展開する（Ｓ６８）。この処理については後述する。
【００３９】
展開後、圧縮データの末尾アドレスが一致するか否かを判断する（Ｓ７０）。図４のステップＳ２２で説明したように、圧縮時に５１２ｋＢ毎の圧縮データ格納先アドレスを所定の領域に記録しているので、展開後のデータの末尾アドレスと所定の領域に記録された圧縮データ格納先アドレスとを比較することにより、展開が正常に行われたか否かを判断することができる。つづいて、展開データサムをチェックすることにより、展開が正常に行われたか否かを判断する（Ｓ７２）。ステップＳ７０およびステップＳ７２において、アドレスが一致しなかった場合（Ｓ７０のＮ）、またはサムが一致しなかった場合（Ｓ７２のＮ）、データエラーが生じたと判断してたとえばエラーメッセージをユーザに提示する。エラーメッセージには、エラーの種類、エラー発生セクションが含まれる。一方、ステップＳ７０およびステップＳ７２において、アドレスが一致し（Ｓ７０のＹ）、およびサムが一致した場合（Ｓ７２のＹ）、同様の処理をＮ回行い、展開を終了する。この後、書き換え作業を行う。
【００４０】
図７は、図６のステップＳ６８に示したデータの復号化手順を詳細に示すフローチャートである。ここでは、以下の処理を５１２×１０２４回繰り返す。
まず、ハフマン木データ先頭アドレスをＡとする（Ｓ８０）。つづいて、圧縮データから１ビット取得する（Ｓ８２）。取得したビットが１の場合、ステップＳ８４に進み、Ａを４バイト進め、ステップＳ８６に進む。一方、ステップＳ８２において、取得したビットがゼロの場合、そのままステップＳ８６に進む。ステップＳ８６において、Ａに格納されたデータが２５６より小さいか否かを判断する。ここで、Ａに格納されたデータが２５６以上の場合（Ｓ８６のＮ）、Ａに格納されたデータでＡを上書きして（Ｓ８７）、ステップＳ８２に戻る。一方、ステップＳ８６において、Ａに格納されたデータが２５６より小さい場合（Ｓ８６のＹ）、Ａに格納されたデータを復号語として確定する（Ｓ８８）。その後、復号語をチェックサム加算する（Ｓ９０）。以上の処理を５１２×１０２４回行った後、圧縮データ末尾アドレス、チェックサムを上位ルーチンに返す（Ｓ９２）。これにより、展開処理を終了する。
【００４１】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【産業上の利用可能性】
【００４２】
本発明にかかるハフマン符号化装置およびハフマン復号装置は、符号化されたデータを効率よく復号することができるという効果を有し、有用である。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施の形態におけるファクシミリ装置およびファクシミリ装置に装着されたＲＯＭ書換装置の構成を示すブロック図である。
【図２】ハフマン符号化装置により符号化された圧縮データの構造を示す図である。
【図３】ハフマン木データを示す図である。
【図４】圧縮データの作成手順を示すフローチャートである。
【図５】図４のステップＳ１８に示したハフマン木インデックスの作成手順を詳細に示すフローチャートである。
【図６】図４および図５を参照して説明した手順により作成された圧縮データを復号する手順を示すフローチャートである。
【図７】図６のステップＳ６８に示したデータの復号化手順を詳細に示すフローチャートである。
【図８】図１に示したハフマン復号装置およびデータ記憶領域の構成を詳細に示すブロック図である。
【符号の説明】
【００４４】
１０  ファクシミリ装置
１１  ＲＯＭ書換装置
１２  ハフマン符号化装置
１４  ハフマン復号装置
１４ａ  符号化データ取得部
１４ｂ  判断部
１４ｃ  変換部
１６  データ記憶領域
１６ａ  符号化データ
１６ｂ  ハフマン木データ
１８  被書換領域
【図１】
2005252813.tif 000003
【図２】
2005252813.tif 000004
【図３】
2005252813.tif 000005
【図４】
2005252813.tif 000006
【図５】
2005252813.tif 000007
【図６】
2005252813.tif 000008
【図７】
2005252813.tif 000009
【図８】
2005252813.tif 000010