(57)【要約】【課題】固定サイズの符号語表を用いたＧＩＦ復元方法および装置。【解決手段】ＧＩＦ符号化データを復元するために固定サイズの符号語表が生成される。固定サイズの符号語表はいくつかの符号語各々に対し符号語列および符号語の長さを格納するよう定義される。符号語列は符号語表において前に表された符号語および１つの文字により定義される。符号語の長さは符号語列における文字の合計数を表す。ＧＩＦ符号化データにおける現在の符号語は符号語表に従い翻訳され、現在の符号語により表される一連の文字が生成される。生成された一連の文字はコンピュータのメモリ空間に格納される。【選択図】図９
2008199610.tif 000002
【特許請求の範囲】
【請求項１】
画像交換フォーマット（ＧＩＦ）符号化データを復元する方法であって、
いくつかの符号語各々に対する符号語列および符号語の長さを格納する符号語表を生成
することで、符号語列は符号語表において前に現される符号語におよび１つの文字により
定義され、符号語の長さは符号語列における文字の合計数を表すステップと、
ＧＩＦ符号化データにおける現在の符号語を符号語表に従い翻訳し、現在の符号語によ
り表される一連の文字を生成するステップと、
一連の文字をコンピュータのメモリ空間に格納するステップとを含むことを特徴とする
画像交換フォーマット（ＧＩＦ）符号化データを復元する方法。
【請求項２】
前記符号語表における各符号語列を定義する符号語および文字は各々第１のビット数お
よび第２のビット数で定義され、符号語表における各符号語の長さは第３のビット数で定
義されることを特徴とする請求項１に記載の画像交換フォーマット（ＧＩＦ）符号化デー
タを復元する方法。
【請求項３】
前記第１のビット数および第３のビット数は同じであることを特徴とする請求項２に記
載の画像交換フォーマット（ＧＩＦ）符号化データを復元する方法。
【請求項４】
前記第１のビット数は１２であり、前記第２のビット数は８であり、前記第３のビット
数は１２であることを特徴とする請求項２に記載の画像交換フォーマット（ＧＩＦ）符号
化データを復元する方法。
【請求項５】
前記符号語表において表される前記符号語の合計数は固定されていることを特徴とする
請求項２に記載の画像交換フォーマット（ＧＩＦ）符号化データを復元する方法。
【請求項６】
現在の符号語により表される一連の文字は現在の符号語に結び付いた文字列における文
字および現在の符号語により参照される符号語列を定義する文字を含むことを特徴とする
請求項１に記載の画像交換フォーマット（ＧＩＦ）符号化データを復元する方法。
【請求項７】
一連の文字をコンピュータのメモリ空間に格納することは現在の符号語により表される
一連の文字を、一連の文字の最後の文字から始まり一連の文字の最初の文字で終わる連続
順序で書き込むことを含むことを特徴とする請求項１に記載の画像交換フォーマット（Ｇ
ＩＦ）符号化データを復元する方法。
【請求項８】
画像交換フォーマット（ＧＩＦ）符号化データを復元するためのコンピュータ・プロセ
ッサであって、
メモリと、
いくつかの符号語各々に対する符号語列および符号語の長さを格納する符号語表を生成
するよう構成される回路で、符号語列は符号語表において前に現される符号語におよび１
つの文字により定義され、符号語の長さは符号語列における文字の合計数を表す回路と、
復元すべきＧＩＦ符号化データを表す符号語のストリームを受信するよう構成される回
路と、
符号語のストリームにおける現在の符号語を符号語表に従い翻訳し、現在の符号語によ
り表される一連の文字を生成するよう構成される回路と、
一連の文字をメモリに格納するよう構成される回路と、を含むことを特徴とする画像交
換フォーマット（ＧＩＦ）符号化データを復元するためのコンピュータ・プロセッサ。
【請求項９】
画像交換フォーマット（ＧＩＦ）符号化データを表示する装置であって、
ディスプレイと、
メモリと、
ＧＩＦ符号化データを復元するためのコンピュータ・プロセッサで、
いくつかの符号語各々に対する符号語列および符号語の長さを格納する符号語表を生成
するよう構成される回路で、符号語列は符号語表において前に現される符号語におよび１
つの文字により定義され、符号語の長さは符号語列における文字の合計数を表す回路と、
復元すべきＧＩＦ符号化データを表す符号語のストリームを受信するよう構成される回
路と、
符号語のストリームにおける現在の符号語を符号語表に従い翻訳し、現在の符号語によ
り表される一連の文字を生成するよう構成される回路と
一連の文字に対応する画像部分をディスプレイで表示するよう構成される回路と、を含
むコンピュータ・プロセッサ、を含むことを特徴とする画像交換フォーマット（ＧＩＦ）
符号化データを表示する装置。
【請求項１０】
符号化データを復元する方法であって、
１つの行に符号語アドレス、符号語列及び符号語長を含む複数の行を有する符号語表を
用意するステップと、
第１の符号語と、前記第１の符号語に続く第２の符号語と、前記第２の符号語に続く第
３の符号語と、を含む符号ストリームを受信するステップと、
前記第１の符号語を翻訳して第１の文字列を生成するステップと、
前記第１の文字列を出力するステップと、
前記符号語表に基づいて、前記第２の符号語を翻訳して第２の文字列を生成するステッ
プと、
前記第２の文字列を出力するステップと、
前記第２の符号語に基づいて、前記符号語表の前記符号語列及び前記符号語長の少なく
とも１行を更新し、第２の符号語表を生成するステップと、
前記第２の符号語表に基づいて、前記第３の符号語を翻訳して前記第３の文字列を生成
するステップと、
前記第３の文字列を出力するステップと、を含むことを特徴とする符号化データを復元
する方法。
【請求項１１】
前記複数の行に含まれる前記符号語列の各々は、符号語と文字を有し、
前記第２の文字列を生成するステップは、
前記符号語表が有する複数の行の中で、前記第２の符号語と等しい符号語アドレスを有
する第１の行を参照するステップと、
前記第１の行に含まれる複合語を参照するステップと、
前記符号語表が有する複数の行の中で、前記第１の行に含まれる複合語と等しい符号語
アドレスを有する第２の行を参照するステップと、を含み、
前記第２の文字列を出力するステップは、
前記第１の行に含まれる第１の文字を出力するステップと、
前記第２の行に含まれる第２の文字を出力するステップと、を含むことを特徴とする請
求項１１に記載の符号化データを復元する方法。
【請求項１２】
前記符号語表の前記複数の行は、第１の行と第２の行を含み、
前記第１の行の符号語列のビット数は、前記第２の行の符号語列のビット数と等しく、
前記第１の行の符号語アドレスのビット数は、前記第２の行の符号語アドレスのビット
数と等しく、
前記第１の行の符号語長のビット数は、前記第２の行の符号語長のビット数のビット数
と等しいことを特徴とする請求項１０に記載の符号化データを復元する方法。
【請求項１３】
前記第３の文字列を生成するステップは、
前記符号語表が有する複数の行の中で、前記第３の符号語と等しい符号語アドレスを有
する第３の行を参照するステップと、
前記第３の行に含まれる複合語を参照するステップと、
前記符号語表が有する複数の行の中で、前記第３の行に含まれる複合語と等しい符号語
アドレスを有する第４の行を参照するステップと、
前記第４の行に含まれる複合語を参照するステップと、
前記符号語表が有する複数の行の中で、前記第４の行に含まれる複合語と等しい符号語
アドレスを有する第５の行を参照するステップと、を含み、
前記第３の文字列を出力するステップは、
前記第３の行に含まれる第３の文字を出力するステップと、
前記第４の行に含まれる第４の文字を出力するステップと、
前記第５の行に含まれる第５の文字を出力するステップと、を含み、
前記第１の文字列、前記第１から第５の文字は、メモリに保存され、
前記メモリのアドレス上では、前記第１の文字列、前記第２の文字、前記第１の文字、
前記第５の文字、前記第４の文字、前記第３の文字の順で保存されていることを特徴とす
る請求項１１に記載の符号化データを復元する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は圧縮デジタル・データの復元に関する。
【背景技術】
【０００２】
デジタル・データの圧縮システムは、デジタル・データを符号化して圧縮デジタル・コ
ードにしたり、圧縮された圧縮デジタル・コードを復号化して元のデジタル・データに復
元したりするためにある。圧縮データ・コードはデジタル・データのストリームより少な
いビットで定義されるので、データ圧縮システムはデジタル・データを保持するのに必要
な記憶容量およびデジタル・データを伝送するのに要する時間を削減する効果がある。圧
縮率は、圧縮デジタル・コードを定義するのに用いられるビット数と元のデジタル・デー
タに存在するビット数との比率と定義される。圧縮率が小さければ小さいほど、記憶容量
や転送時間の削減が大きくなる。
【０００３】
デジタル・データ圧縮の一手法として、ＬＺＷ法（またはＬｅｍｐｅｌ−Ｚｉｖ−Ｗｅ
ｌｃｈ法）が知られており、米国特許第４５５８３０２号明細書において説明されている
。デジタル・データ圧縮の別の手法として、ＧＩＦ（画像交換フォーマット）法も知られ
ており、ＬＺＷ法を多少修正したものである。ＬＺＷ法およびＧＩＦ法は、ともに文字ス
トリームにおける文字列の繰り返しを利用してデータ文字のストリーム、すなわち文字ス
トリーム、を符号語(codeword)のストリームに圧縮する。
【０００４】
ＧＩＦ圧縮および復元の際、符号語表(codeword table)が動的に生成される。一般的に
符号語表は基本的に符号ストリームに存在する符号語のディクショナリ(dictionary)であ
る。圧縮の際、符号語表は文字ストリームの続く部分の符号化を促進するために文字スト
リームが符号化されるのに応じて生成される。このようにデータを圧縮する際、文字スト
リームは入力で、符号ストリームは出力であり、符号語表は符号ストリームの提供を助け
るために生成され、データが圧縮された後は廃棄される。圧縮されたデータを復元する際
は符号ストリームが入力で文字ストリームが出力となり、符号語表は文字ストリームの提
供を支援するために生成され、その後は廃棄される。符号表は符号ストリームに随伴しな
い。ビットという点で符号ストリームのサイズは文字ストリームのサイズより小さいこと
が理解されよう。符合ストリーム・サイズの文字ストリーム・サイズに対する比率が圧縮
率である。
【０００５】
【特許文献１】米国特許第４５５８３０２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来のＧＩＦ復元の際、符号語表はサイズが可変である。より具体的には、特定の符号
語に結び付いた文字列の長さは変化する。符号語表に存在しえる最大文字列長は元の非圧
縮データの関数である。例えば、元の非圧縮データにおいて文字の反復が少ない場合、符
号語表に格納する必要のある最大文字列長は非常に大きい。このように、従来のＧＩＦ復
元法を実施する際、任意の特定符号語に対し保存する必要があると予想される最大文字列
長に対応するために符号語表を保存するために必要なメモリ量を割り当てる必要がある。
メモリ容量が充分の場合、大きなメモリ空間を割り当てることは問題とならないかも知れ
ない。逆にメモリ容量が少ない場合、符号語格納のために大きなメモリ空間を割り当てる
ことはできないかもしれない。従って、従来のＧＩＦ復元法はメモリ容量が限られている
ような状況では、容易にまたは確実に実施できない可能性がある。
【０００７】
前述に鑑み、従来のＧＩＦ復元プロセスに結び付いた可変サイズの符号語表の格納がメ
モリの制限により妨げられるような状況であっても、ＧＩＦの符号ストリームの復元を可
能にするような方法が必要である。
【課題を解決するための手段】
【０００８】
一実施形態で、画像交換フォーマット（ＧＩＦ）の符号化データを復元する方法が開示
される。方法はいくつかの符号語各々に対し符号語列および符号語長を格納する符号語表
を生成する操作を含む。符号語列は符号語表に前以て表された符号語および１つの文字に
よって定義される。符号語長は符号語列における文字の合計数を表す。方法はさらにＧＩ
Ｆ符号化データの現在の符号語を符号語表に従って翻訳し、現在の符号語により表される
一連の文字を生成する操作を含む。方法はさらに生成された一連の文字をコンピュータの
メモリ空間に格納する操作を含む。
【０００９】
別の実施形態で、ＧＩＦ符号化データを復元するコンピュータ・プロセッサが開示され
る。コンピュータ・プロセッサはメモリおよびメモリ内に符号語表を生成するよう構成さ
れる回路を含む。符号語表はいくつかの符号語各々に対し符号語列および符号語長を格納
するよう定義される。符号語列は符号語表に前以て表された符号語および１つの文字によ
って定義される。符号語長は符号語列における文字の合計数を表す。コンピュータ・プロ
セッサはまたＧＩＦ符号化データを表す符号語のストリームを受信するよう構成される回
路を含む。コンピュータ・プロセッサはさらに復元するためにＧＩＦ符号化データを表す
符号語のストリームを受信する回路を含む。コンピュータ・プロセッサはさらに符号語の
ストリームにおける現在の符号語を符号語表に従って翻訳し、現在の符号語により表され
る一連の文字を生成する回路を含む。加えてコンピュータ・プロセッサは生成された一連
の文字をメモリに格納するよう構成される回路を含む。
【００１０】
別の実施形態で、ＧＩＦ符号化画像データを表示する装置が開示される。装置はディス
プレイ、メモリ、およびＧＩＦ符号化画像データを復元するコンピュータ・プロセッサを
含む。コンピュータ・プロセッサはメモリおよびメモリ内にいくつかの符号語各々に対し
符号語列および符号語長を格納する符号語表を生成するよう構成される回路を含む。符号
語列は符号語表に前以て表された符号語および１つの文字によって定義される。符号語長
は符号語列における文字の合計数を表す。コンピュータ・プロセッサはまたＧＩＦ符号化
画像データを表す符号語のストリームを受信するよう構成される回路を含む。コンピュー
タ・プロセッサはさらに符号語のストリームにおける現在の符号語を符号語表に従って翻
訳し、現在の符号語により表される一連の文字を生成する回路を含む。加えてコンピュー
タ・プロセッサは生成された一連の文字に対応する画像部分をディスプレイに表示するよ
う構成される回路を含む。
【００１１】
上記目的を解決するため、形態１の、画像交換フォーマット（ＧＩＦ）符号化データを
復元する方法は、いくつかの符号語各々に対する符号語列および符号語の長さを格納する
符号語表を生成することで、符号語列は符号語表において前に現される符号語におよび１
つの文字により定義され、符号語の長さは符号語列における文字の合計数を表すステップ
と、ＧＩＦ符号化データにおける現在の符号語を符号語表に従い翻訳し、現在の符号語に
より表される一連の文字を生成するステップと、一連の文字をコンピュータのメモリ空間
に格納するステップとを含むことをその要旨とする。
【００１２】
また、形態２の、画像交換フォーマット（ＧＩＦ）符号化データを復元する方法は、符
号語表における各符号語列を定義する符号語および文字は各々第１のビット数および第２
のビット数で定義され、符号語表における各符号語の長さは第３のビット数で定義される
ことをその要旨とする。
【００１３】
また、形態３の、画像交換フォーマット（ＧＩＦ）符号化データを復元する方法は第１
のビット数および第３のビット数は同じであることをその要旨とする。
【００１４】
また、形態４の、画像交換フォーマット（ＧＩＦ）符号化データを復元する方法は、第
１のビット数は１２であり、第２のビット数は８であり、第３のビット数は１２であるこ
とをその要旨とする。
【００１５】
また、形態５の、画像交換フォーマット（ＧＩＦ）符号化データを復元する方法は、符
号語表において表される符号語の合計数は固定されていることその要旨とする。
【００１６】
また、形態６の、画像交換フォーマット（ＧＩＦ）符号化データを復元する方法は、現
在の符号語により表される一連の文字は現在の符号語に結び付いた文字列における文字お
よび現在の符号語により参照される符号語列を定義する文字を含むことをその要旨とする
。
【００１７】
また、形態７の、画像交換フォーマット（ＧＩＦ）符号化データを復元する方法は、一
連の文字をコンピュータのメモリ空間に格納することは現在の符号語により表される一連
の文字を、一連の文字の最後の文字から始まり一連の文字の最初の文字で終わる連続順序
で書き込むことを含むことをその要旨とする。
【００１８】
また、形態８の、画像交換フォーマット（ＧＩＦ）符号化データを復元するためのコン
ピュータ・プロセッサは、メモリと、いくつかの符号語各々に対する符号語列および符号
語の長さを格納する符号語表を生成するよう構成される回路で、符号語列は符号語表にお
いて前に現される符号語におよび１つの文字により定義され、符号語の長さは符号語列に
おける文字の合計数を表す回路と、復元すべきＧＩＦ符号化データを表す符号語のストリ
ームを受信するよう構成される回路と、符号語のストリームにおける現在の符号語を符号
語表に従い翻訳し、現在の符号語により表される一連の文字を生成するよう構成される回
路と、一連の文字をメモリに格納するよう構成される回路と、を含むことをその要旨とす
る。
【００１９】
また、形態９の、コンピュータ・プロセッサは、符号語表における各符号語列を定義す
る符号語および文字は各々第１のビット数および第２のビット数で定義され、符号語表に
おける各符号語の長さは第３のビット数で定義されることをその要旨とする。
【００２０】
また、形態１０の、コンピュータ・プロセッサは、第１のビット数および第３のビット
数は同じであることをその要旨とする。
【００２１】
また、形態１１の、コンピュータ・プロセッサは、第１のビット数は１２であり、第２
のビット数は８であり、第３のビット数は１２であることをその要旨とする。
【００２２】
また、形態１２の、コンピュータ・プロセッサは、符号語表において表される符号語の
合計数は固定されていることをその要旨とする。
【００２３】
また、形態１３の、コンピュータ・プロセッサは、現在の符号語により表される一連の
文字は現在の符号語に結び付いた文字列における文字および現在の符号語により参照され
る符号語列を定義する文字を含むことをその要旨とする。
【００２４】
また、形態１４の、コンピュータ・プロセッサは、一連の文字をコンピュータのメモリ
空間に格納するよう構成される回路は現在の符号語により表される一連の文字を、一連の
文字の最後の文字から始まり一連の文字の最初の文字で終わる連続順序で書き込むよう構
成されることをその要旨とする。
【００２５】
また、形態１５の、画像交換フォーマット（ＧＩＦ）符号化データを表示する装置は、
ディスプレイと、メモリと、ＧＩＦ符号化データを復元するためのコンピュータ・プロセ
ッサで、いくつかの符号語各々に対する符号語列および符号語の長さを格納する符号語表
を生成するよう構成される回路で、符号語列は符号語表において前に現される符号語にお
よび１つの文字により定義され、符号語の長さは符号語列における文字の合計数を表す回
路と、復元すべきＧＩＦ符号化データを表す符号語のストリームを受信するよう構成され
る回路と、符号語のストリームにおける現在の符号語を符号語表に従い翻訳し、現在の符
号語により表される一連の文字を生成するよう構成される回路と一連の文字に対応する画
像部分をディスプレイで表示するよう構成される回路と、を含むコンピュータ・プロセッ
サ、を含むことをその要旨とする。
【００２６】
また、形態１６の、画像交換フォーマット（ＧＩＦ）符号化データを表示する装置は、
符号語表における各符号語列を定義する符号語および文字は各々第１のビット数および第
２のビット数で定義され、符号語表における各符号語の長さは第３のビット数で定義され
、符号語表において表される符号語の合計数は固定していることをその要旨とする。
【００２７】
また、形態１７の、画像交換フォーマット（ＧＩＦ）符号化データを表示する装置は、
第１のビット数および第３のビット数は同じであることをその要旨とする。
【００２８】
また、形態１８の、画像交換フォーマット（ＧＩＦ）符号化データを表示する装置は、
第１のビット数は１２であり、第２のビット数は８であり、第３のビット数は１２である
ことをその要旨とする。
【００２９】
また、形態１９の、画像交換フォーマット（ＧＩＦ）符号化データを表示する装置は、
現在の符号語により表される一連の文字は現在の符号語に結び付いた文字列における文字
および現在の符号語により参照される符号語列を定義する文字を含むことをその要旨とす
る。
【００３０】
また、形態２０の、画像交換フォーマット（ＧＩＦ）符号化データを表示する装置は、
ＧＩＦ符号化データを復元するためのコンピュータ・プロセッサはさらに一連の文字の最
後の文字から始まり一連の文字の最初の文字で終わる連続順序で一連の文字をコンピュー
タのメモリ空間に書き込むよう構成される回路を含むことをその要旨とする。
【００３１】
発明の他の態様は本発明を例示する添付図面と併せて以下の詳細な説明からより明らか
になるであろう。
【発明を実施するための最良の形態】
【００３２】
以下の説明において、本発明の充分な理解を提供するために具体的な実施形態が記述さ
れている。しかしこれらの具体的な実施例に記載されている構成の幾つか又は全てを備え
ていなくても、本発明は実施し得ることは当業者であれば明らかであろう。逆に本発明を
不必要に分かりにくくしないために周知のプロセス操作は詳細に説明されていない。
【００３３】
可変サイズ符号語表を用いたＧＩＦ復元法
ＧＩＦ（画像交換フォーマット）復元法は、符号ストリーム(code stream)を入力とし
て受け取り、符号ストリームから文字ストリーム(character stream)を出力として生成す
る。符号ストリームはＧＩＦ圧縮法で生成された符号語のシーケンスを表している。つま
り、符号ストリームは、ＧＩＦ圧縮法で圧縮される前の元データの符号化表現である。よ
って、ＧＩＦ復元法を用いて復元された文字ストリームの出力は、ＧＩＦ圧縮法によって
圧縮される前の元データと同一であるはずである。
【００３４】
ＧＩＦ復元法は、符号語表を生成することにより行われる。符号語表は、そのサイズが
可変である。符号語表には、複数の文字列とその文字列と同じ数の符号語とが含まれ、文
字列と符号語は１対１で対応している。複数の符号語の各々とそれに対応する文字列は符
号語表の一入力を表す。各文字列のサイズ、すなわち文字列内の文字数は可変であるため
、符号語表のサイズも変化することができる。符号語表の最終的なサイズは、符号ストリ
ーム内で符号化された圧縮前の元データの内容に依存する。
【００３５】
図１は可変サイズの符号語表を用いたＧＩＦ復元法の擬似コードを例示する図である。
説明しやすくするために、本実施例中において、可変サイズの符号語表を用いたＧＩＦ復
元法を「可変サイズＧＩＦ復元法」と呼ぶ。以下、可変サイズＧＩＦ復元法のプロセスに
ついて説明する。
【００３６】
可変サイズＧＩＦ復元法のプロセスは、第１のステップとして、符号語表における最初
の２５６個の入力を初期化することから始まる。より具体的には、符号語表における最初
の２５６個の入力は各々１つの文字を表す符号語列を有するように初期化される。
【００３７】
初期化が終了した後、第２のステップとして、符号ストリーム（すなわち復元すべき入
力符号ストリーム）において受信した最初の符号語を符号語保持変数ＯＬＤ_ＣＷに格納
する操作が行われる。ＧＩＦ圧縮プロセスにより符号ストリームにおける最初の符号語は
最初の２５６個の符号語表の入力内の符号語列として存在する１つの文字であることが保
証される。
【００３８】
次いで、第３のステップとして、最初の符号語を符号語保持変数ＯＬＤ_ＣＷに格納し
た後、可変サイズＧＩＦ復元法は符号語保持変数ＯＬＤ_ＣＷの最初の文字を文字保持変
数ＣＨＡＲに格納する、すなわち符号語保持変数ＯＬＤ_ＣＷに格納される符号語に結び
付いた符号語列における最初の文字が文字保持変数ＣＨＡＲに格納される。
【００３９】
次いで、第４のステップとして、出力アドレス変数ＯＵＴ_ＡＤＤＲが「０（ゼロ）」
に設定される。出力アドレス変数ＯＵＴ_ＡＤＤＲは文字ストリームにおけるある文字が
出力されるメモリ・アドレスのエイリアスを表す。文字ストリームは可変サイズＧＩＦ復
元法の出力、すなわち復元されたデータを表すので、出力アドレス変数ＯＵＴ_ＡＤＤＲ
は文字ストリーム出力における文字のシーケンスを表していることが理解されよう。
【００４０】
次いで、第５のステップとして、文字保持変数ＣＨＡＲの内容を出力アドレス変数ＯＵ
Ｔ_ＡＤＤＲに格納される文字ストリーム内のアドレスに出力する操作が行われる。この
ように、符号ストリームの最初の符号語に結び付いた文字列、すなわち１つの文字、が文
字ストリームのアドレス０（ゼロ）に出力される。
【００４１】
次いで、第６のステップとして、ＷＨＩＬＥループの実行により符号ストリームの残り
を処理する。より具体的には、ＷＨＩＬＥループの各パスにより符号ストリームにおける
１つの符号語が処理される。
【００４２】
ＷＨＩＬＥループの最初の操作で、符号ストリームにおける次の符号語を符号語保持変
数ＣＷに格納する。例えば、１回目のパスを実行する場合は、符号ストリームにおける符
号語保持変数ＯＬＤ_ＣＷの次の符号語を符号語保持変数ＣＷに格納し、２回目のパスを
実行する場合は、符号ストリームにおける符号語保持変数ＯＬＤ_ＣＷの２つ後ろの符号
語を符号語保持変数ＣＷに格納する。
【００４３】
次に、符号語保持変数ＣＷに格納された符号語が既に符号語表に存在するかを判定し、
その判定結果に応じた文字列を文字列保持変数ＳＴＲにロードする。符号語保持変数ＣＷ
に格納された符号語が既に符号語表に存在する場合は、符号語保持変数ＣＷに格納された
符号語に結び付いた符号語列を文字列保持変数ＳＴＲにロードする。逆に、符号語保持変
数ＣＷに格納された符号語が既に符号語表に存在しない場合は、符号語保持変数ＣＷに格
納された符号語に結び付いた符号語列に文字保持変数ＣＨＡＲの文字内容を加えて文字列
保持変数ＳＴＲにロードする。文字保持変数ＣＨＡＲの初期値は前述したとおり符号語保
持変数ＯＬＤ_ＣＷの最初の文字で、後述するようにＷＨＩＬＥループにおいて文字列保
持変数ＳＴＲ内に存在する最初の文字に更新される。
【００４４】
一旦、文字列保持変数ＳＴＲがロードされると、文字列保持変数ＳＴＲ内の文字列を文
字ストリームに出力するプロセスが行われる。図１の擬似コードにおいて、文字列保持変
数ＳＴＲの内容を出力するプロセスは、前述のＷＨＩＬＥループの内側に設けられた内部
ＷＨＩＬＥループにより実施される。内部ＷＨＩＬＥループの各パスで出力アドレス変数
ＯＵＴ_ＡＤＤＲは１増分され、文字列保持変数ＳＴＲ内に格納された文字列の文字が１
つずつ出力アドレス変数ＯＵＴ_ＡＤＤＲに格納される文字ストリームに出力される。こ
のようにして、文字列保持変数ＳＴＲの内容は文字列保持変数ＳＴＲに格納されている最
初の文字から文字列保持変数ＳＴＲに格納されている最後の文字まで順に文字ストリーム
に出力される。文字列保持変数ＳＴＲに格納されている最後の文字が出力されると、内部
ＷＨＩＬＥループが終了する。
【００４５】
文字列保持変数ＳＴＲの文字ストリームへの出力に続き、可変サイズＧＩＦ復元法は符
号語表を更新する。符号語表の更新は符号語表の最後の行に新しい入力を加えることに事
実上相当する。符号語表の更新プロセスは、文字列保持変数ＳＴＲ内に存在する最初の文
字を文字保持変数ＣＨＡＲに格納することで始まる。ここで文字保持変数ＣＨＡＲに格納
された文字はＷＨＩＬＥループの次のパスにおいて用いられる。前述したように、次のパ
スにおいて、処理する符号ストリームの符号語がまだ符号語表に存在していない場合、文
字列保持変数ＳＴＲをロードするのに文字保持変数ＣＨＡＲに格納された文字が使用され
る。
【００４６】
一旦、文字保持変数ＣＨＡＲが更新されると、符号語表に新しい入力が加えられ、符号
語表に存在する符号語のシーケンスにおける次の符号語が割り当てられる。符号語表の新
入力に対する符号語列は符号語保持変数ＯＬＤ_ＣＷに格納された符号語に対応する符号
語列に文字保持変数ＣＨＡＲの文字内容を加えたものと定義される。符号語列に文字保持
変数ＣＨＡＲの文字内容が加えられると符号語列のサイズが増加する。符号語列は文字の
列として符号語表に格納されることが理解されよう。従って、各符号語列のサイズ、すな
わち文字数、が増加するにつれ可変サイズ符号語表のサイズが増加する。
【００４７】
さらに、ＷＨＩＬＥループの次のパスに備え、符号語保持変数ＣＷに格納された符号語
は符号語保持変数ＯＬＤ_ＣＷに格納される。ファイル終端の符号語（２５７）がＷＨＩ
ＬＥループの初めに現れると、すなわち符号ストリームに２５７が現れると、ＷＨＩＬＥ
ループは終了する。ＷＨＩＬＥループの終了により、可変サイズＧＩＦ復元法は完了する
。
【００４８】
図２（Ａ）はＧＩＦ圧縮法により符号化される前の文字ストリームを例示する図である
。図２（Ｂ）は図２（Ａ）で例示されている文字ストリームを、ＧＩＦ圧縮法により圧縮
することで生成された符号ストリームを例示する図である。図２（Ｃ）は、前述の図１で
説明したように、可変サイズＧＩＦ復元法を用いて生成された符号語表を例示する図であ
る。図３は前述の図１で説明したように、可変サイズＧＩＦ復元法で復元された文字スト
リーム出力を例示する図である。
【００４９】
図２（Ｃ）の符号語表は可変サイズの符号語表で、符号語表のサイズは圧縮ファイルの
内容に依存することが分かる。例えば、符号語アドレス２５５までは、符号語列が１つの
文字内容で構成されているが、符号語アドレス２５８から符号語アドレス２６１は２つ、
符号語アドレス２６２から符号語アドレス２６４は３つ、符号語アドレス２６５は４つと
符号語列のビット数が変化している。可変サイズの符号語表のサイズは６４０ピクセル×
４８０ピクセルの画像の場合、通常２５キロバイト（ＫＢ）から４０ＫＢの範囲である。
可変サイズの符号語表のサイズが大きいことは図１に関し前述される可変サイズＧＩＦ復
元法のソフトウェア処理ではシステム・メモリが充分にあるので一般的に問題にならない
。しかし、ＧＩＦ復元プロセスのハードウェア処理のようにシステム・メモリが制限され
ている場合は、可変サイズの符号語表を格納するために充分なメモリが確保されていない
可能性もある。一方、ＧＩＦ復元プロセスのハードウェア処理において可変サイズの符号
語表を格納するために充分なメモリを用意するとメモリが大きくなるので、チップのコス
トが増大したりチップ面積が増加してしまったりする可能性がある。
【００５０】
固定サイズ符号語表を用いたＧＩＦ復元法
本発明の実施形態の一つとして、固定サイズの符号語表を生成し利用するＧＩＦ復元法
をについて説明する。説明しやすくするために、固定サイズの符号語表を用いたＧＩＦ復
元法を「固定サイズＧＩＦ復元法」と呼ぶ。固定サイズＧＩＦ復元法は符号ストリーム（
図５（Ａ））を入力として受け取り、文字ストリーム（図６）を出力として生成する。符
号ストリームはＧＩＦ圧縮法で生成された符号語のシーケンスを表している。つまり、符
号ストリームは、ＧＩＦ圧縮法を用いて圧縮される前の元のデータを符号化表現したデー
タである。固定サイズＧＩＦ復元法により復元された文字ストリームの出力は、ＧＩＦ圧
縮法をと用いて圧縮される前の元のデータと同一である。
【００５１】
固定サイズＧＩＦ復元法は、各符号語アドレスＣＷ_ＡＤＤＲに対し、符号語列ＳＴＲ_
ＩＮおよび符号語長さＬＥＮ_ＩＮが定義される固定サイズの符号語表ＣＷ_ＭＥＭ［ＣＷ
_ＡＤＤＲ］（図５（Ｂ））を生成することにより行われる。符号語表ＣＷ_ＭＥＭにおい
て、ある入力における符号語列ＳＴＲ_ＩＮは、ある入力より前に入力された符号語保持
変数ＯＬＤ_ＣＷおよび文字を示す文字保持変数ＣＨＡＲの組み合わせにより定義される
。特定の符号語に対し定義された符号語長さＬＥＮ_ＩＮは符号語列ＳＴＲ_ＩＮが完全に
文字レベルに拡張された場合の文字数を表す。各符号語列ＳＴＲ_ＩＮ入力の符号語部分
は固定ビット数により定義される。各符号語列ＳＴＲ_ＩＮ入力の文字部分も固定ビット
数により定義される。また、各符号語入力の符号語長さＬＥＮ_ＩＮ部分も固定ビット数
により定義される。従って、符号語表内の各符号語入力は固定ビット数により定義される
。このように、符号語表の幅は各符号語入力について固定ビット数で定義される。言い換
えると、固定サイズ符号表の各行において、符号語アドレスＣＷ_ＡＤＤＲも符号語列Ｓ
ＴＲ_ＩＮも符号語長さＬＥＮ_ＩＮもビット数が変化しない。それ故、固定サイズの符号
語表は許される符号語入力の数を設定することにより管理することができる。
【００５２】
図４は本発明の一実施形態における固定サイズＧＩＦ復元法の擬似コードを例示する図
である。
第１のステップとして、固定サイズの符号語表ＣＷ_ＭＥＭにおける最初から２５６個
の入力を初期化する。符号語アドレスＣＷ_ＡＤＤＲが０（ゼロ）から２５５の行に対応
する。この初期化プロセスはＦＯＲループを用いて実行され、ＦＯＲループの各パスは、
固定サイズの符号語表のうち、最初から２５６個の入力を順次初期化する。
【００５３】
まず、ここで用いる保持変数について説明する。符号語アドレスＣＷ_ＡＤＤＲには、
符号語表における符号語アドレスが格納される。ここでの符号語列ＳＴＲ_ＩＮには、入
力された符号ストリームに対応する符号語列の中の符号語部分が格納される。符号語長さ
ＬＥＮ_ＩＮは、符号語表入力に対応する符号語列の長さを定義するために用いられる。
固定サイズの符号語表は、アレイ構造ＣＷ_ＭＥＭ［ＣＷ_ＡＤＤＲ］＝｛ＳＴＲ_ＩＮ，
ＬＥＮ_ＩＮ｝で表される。符号語表ＣＷ_ＭＥＭ［ＣＷ_ＡＤＤＲ］には、符号語列ＳＴ
Ｒ_ＩＮおよび符号語長さＬＥＮ_ＩＮの内容が格納される。
【００５４】
次いで、ＦＯＲループの各パスについて説明する。ＦＯＲループの各パスの際、符号語
アドレスＣＷ_ＡＤＤＲおよび符号語列ＳＴＲ_ＩＮに格納される値は、ＦＯＲループのル
ープ・カウンタの「Ｉ」値が入力される。つまり、ＦＯＲループにおいて「Ｉ」値は「０
（ゼロ）」から「２５５」まで順にインクリメントするので、符号語アドレスＣＷ_ＡＤ
ＤＲおよび符号語列ＳＴＲ_ＩＮもＦＯＲループのパスで「Ｉ」値と同様に「０（ゼロ）
」から「２５５」まで順に増分される。符号語長さＬＥＮ_ＩＮは「１」に設定される。
符号語列ＳＴＲ_ＩＮおよび符号語長さＬＥＮ_ＩＮの内容は初期値として符号語表ＣＷ_
ＭＥＭ［ＣＷ_ＡＤＤＲ］に格納される。符号語列の文字部分はＮＵＬＬに設定される。
【００５５】
符号語表ＣＷ_ＭＥＭ［ＣＷ_ＡＤＤＲ］の最初ＣＷ_ＭＥＭ［０］から２５６個ＣＷ_Ｍ
ＥＭ［２５５］までの初期化が行われると、ＦＯＲループによる初期化が終了し、第２の
ステップを実行する。
【００５６】
第１のステップでＦＯＲループで符号語アドレスＣＷ_ＡＤＤＲの２５５まで初期化し
たので、第２のステップとして、次の符号語アドレスＣＷ_ＡＤＤＲの設定を行う。符号
語”２５６”は符号語表のリセット・フラグとして使用するための値に設定され、符号語
表リセット・フラグ２５６と称する。従って符号語アドレス２５６が符号ストリームに現
れると符号語表はリセット、すなわち再初期化される。符号語”２５７”はファイル終端
フラグとして使用するための値に設定され、ファイル終端フラグ２５７と称する。従って
符号語”２５７”が符号ストリームに現れると、固定サイズＧＩＦ復元法は符号ストリー
ムの復元を停止又は終了する。図５（Ｂ）の固定サイズ符号表の符号語アドレスＣＷ_Ａ
ＤＤＲでは、符号語アドレス２５６に対応する符号語列が符号語表リセット・フラグに設
定され、符号語アドレス２５７に対応する符号語列がファイル終端フラグに設定されてい
る。第２のステップでは、最初の２５６個の符号語表入力の初期化に続き、符号語アドレ
スＣＷ_ＡＤＤＲが符号語表の最後の入力となるように２５７に設定される。これにより
、符号語アドレスＣＷ_ＡＤＤＲの値が、固定サイズ符号語表において符号語列がファイ
ル終端フラグの行に対応する符号語アドレスの値に設定される。
【００５７】
第３のステップとして、固定サイズＧＩＦ復元法は符号ストリーム、すなわち復元すべ
き入力符号ストリームにおける最初の符号語を符号語保持変数ＯＬＤ_ＣＷに格納する。
ＧＩＦ圧縮プロセスでは、符号ストリームにおける最初の符号語は、最初の２５６個の符
号語表入力内の符号語列の符号語部分として存在する１つの文字であることが保証されて
いる。すなわち、符号ストリームにおいて受信した複数の符号語のうち、先頭の符号語に
ついては、符号語表ＣＭ_ＭＥＭの０行目から２５６行目までの間に同一の符号語が存在
することが保証されている。続いて、符号語保持変数ＯＬＤ_ＣＷに格納される符号語に
対応する符号語列における最初の文字を文字保持変数ＣＨＡＲ内に格納する。
【００５８】
第４のステップとして、アドレス保持変数ＡＤＤＲが「０（ゼロ）」に設定される。符
号語長さ保持変数ＬＥＮは「１」に設定される。また、出力アドレス変数ＯＵＴ_ＡＤＤ
Ｒが「０（ゼロ）」に設定される。出力アドレス変数ＯＵＴ_ＡＤＤＲは文字ストリーム
において文字が出力されるメモリ・アドレスのエイリアスを表す。すなわち、復元化され
た文字ストリームの文字はメモリ上に保存されるが、出力アドレス変数ＯＵＴ_ＡＤＤＲ
によって保存されるアドレスが決定する。文字ストリームは固定サイズＧＩＦ復元法の出
力、すなわち復元データであるから、出力アドレス変数ＯＵＴ_ＡＤＤＲは文字ストリー
ム出力における文字のシーケンスを表している。
【００５９】
次に、第５のステップとして、文字保持変数ＣＨＡＲの内容を出力アドレス変数ＯＵＴ
_ＡＤＤＲに格納される文字ストリーム内のアドレスに出力する。このように、符号スト
リームの最初の符号語に対応する文字列、すなわち１つの文字が文字ストリームのアドレ
ス０（ゼロ）に出力される。例えば、図６を用いて説明すると、文字保持変数ＣＨＡＲの
内容１が、文字ストリーム出力の出力アドレス０に対応する出力文字として出力される。
【００６０】
次に、第６のステップとして、ＷＨＩＬＥループの実行により、符号ストリームの残り
の部分を処理する。より具体的には、ＷＨＩＬＥループの各パスにより符号ストリームに
含まれる複数の符号語の各々が１つずつ処理される。
【００６１】
ＷＨＩＬＥループ内の最初の操作において、符号ストリームにおける次の符号語を符号
語保持変数ＣＷに格納する。例えば、図５（Ａ）及び図７を用いて説明すると、ＷＨＩＬ
Ｅループの１回目のパスでは、符号ストリームで符号語保持変数ＯＬＤ_ＣＷに格納した
符号語”１”の次の符号語”１”を符号語保持変数ＣＷに格納する。ＷＨＩＬＥループの
２回目のパスでは、前のパスで符号語保持変数ＣＷに格納した符号語”１”の次の符号語
”０”を符号語保持変数ＣＷに格納する。同様にしてＷＨＩＬＥループの３回目、４回目
、５回目のパスでは、それぞれ０（ゼロ）、２５９、２６１が符号語保持変数ＣＷに格納
される。
【００６２】
ＷＨＩＬＥループ内の次の操作では、符号語保持変数ＣＷに格納された符号語が既に符
号語表に存在するかを判定し、その判定結果に応じて、文字列保持変数ＳＴＲ、文字保持
変数ＣＨＡＲ及び符号語長さ保持変数ＬＥＮを設定する。
【００６３】
符号語保持変数ＣＷに格納された符号語が既に符号語表に存在する場合は、符号語保持
変数ＣＷに格納された符号語に対応する符号語列の符号語部分を文字列保持変数ＳＴＲに
ロードする。また、符号語保持変数ＣＷに格納された符号語に対応する符号語列の文字部
分を文字保持変数ＣＨＡＲにロードする。また、符号語保持変数ＣＷに格納された符号語
に対応する符号語列の符号語長さの値を符号語長さ保持変数ＬＥＮにロードする。例えば
、図５（Ａ）及び図７を用いて説明すると、ＷＨＩＬＥループの１回目のパスでは符号語
保持変数ＣＷが「１」で、符号語の”１”は既に図５（Ａ）の符号語表の２行目に存在す
るので、符号語が”１”に対応する符号語列の符号語部分である”１”を文字列保持変数
ＳＴＲにロードする。符号語が”１”に対応する符号語列の文字部分ＮＵＬＬを文字保持
変数ＣＨＡＲにロードする。符号語が”１”に対応する符号語長さの値「１」を符号語長
さ保持変数ＬＥＮにロードする。
【００６４】
逆に、符号語保持変数ＣＷに格納された符号語がまだ符号語表に存在しない場合は、符
号語保持変数ＯＬＤ_ＣＷに格納された符号語に対応する符号語列の符号語部分に、文字
保持変数ＣＨＡＲの文字内容を加えて文字列保持変数ＳＴＲにロードする。また、符号語
保持変数ＯＬＤ_ＣＷに格納された符号語に対応する符号語長さの値に「１」を加えて符
号語長さ保持変数ＬＥＮにロードする。例えば、図５（Ａ）及び図７を用いて説明すると
、ＷＨＩＬＥループの４回目のパスでは符号語保持変数ＣＷが２５９で、符号語の”２５
９”は、図５（Ａ）の固定サイズ符号語表が生成される前なので符号語表に存在していな
い。そこで、符号語保持変数ＯＬＤ_ＣＷに格納された符号語に対応する符号語列の符号
語部分”１”に、文字保持変数ＣＨＡＲの文字内容”０”を加えた値”０、１”を文字列
保持変数ＳＴＲにロードする。また、符号語に対応する符号語長さの値「１」に「１」を
加えた値「２」を符号語長さ保持変数ＬＥＮにロードする。
【００６５】
ＷＨＩＬＥループ内の次の操作では、一旦、符号語保持変数ＣＷに格納される符号語に
基づいて文字列保持変数ＳＴＲ、文字保持変数ＣＨＡＲ、および符号語長さ保持変数ＬＥ
Ｎが更新されると、文字列保持変数ＳＴＲの文字内容を文字ストリームに逆の順序、すな
わち最後の文字から出力し最初の文字で出力が終わる順番で出力するプロセスが内部ＷＨ
ＩＬＥループによって実施される。文字ストリーム出力プロセスは、まず、内部ＷＨＩＬ
Ｅループを実行する前に、現在のＷＨＩＬＥループで符号語長さ保持変数ＬＥＮに格納さ
れている長さ値を出力符号語長さ保持変数ＯＵＴ_ＬＥＮにロードすることで始まる。次
に、出力符号語長さ保持変数ＯＵＴ_ＬＥＮに格納される値が「１」に等しくない場合、
出力符号語長さ保持変数ＯＵＴ_ＬＥＮに格納される値が「１」に等しくなるまで内部Ｗ
ＨＩＬＥループを実施して、文字列保持変数ＳＴＲの文字内容を出力する。
【００６６】
内部ＷＨＩＬＥループの各パスで、出力アドレス変数ＯＵＴ_ＡＤＤＲは、現在のアド
レス保持変数ＡＤＤＲの値および現在の出力符号語長さ保持変数ＯＵＴ_ＬＥＮに格納さ
れている値の合計に設定される。次に文字保持変数ＣＨＡＲに現在格納されている文字が
、出力アドレス変数ＯＵＴ_ＡＤＤＲに格納される文字ストリーム内のアドレスに出力さ
れる。その後、内部ＷＨＩＬＥループの次のパスのために文字列保持変数ＳＴＲ、文字保
持変数ＣＨＡＲ、および出力符号語長さ保持変数ＯＵＴ_ＬＥＮが更新される。より具体
的には、文字列保持変数ＳＴＲに以前格納されていた符号語に結び付いた符号語列の符号
語部分を文字列保持変数ＳＴＲにロードする。次に、現在、文字列保持変数ＳＴＲに格納
された符号語に結び付いた符号語列の文字部分を文字保持変数ＣＨＡＲにロードする。次
に現在、文字列保持変数ＳＴＲに格納された符号語に結び付いた長さ値を出力符号語長さ
保持変数ＯＵＴ_ＬＥＮにロードする。例えば、ＷＨＩＬＥループの４回目のパスについ
て説明する。出力符号語長さ保持変数ＯＵＴ_ＬＥＮの値が「２」であるから、内部ＷＨ
ＩＬＥループは１回実行される。現在のアドレス保持変数ＡＤＤＲの値が「３」で、現在
の出力符号語長さ保持変数ＯＵＴ_ＬＥＮに格納されている値が「１」であるから、内部
ＷＨＩＬＥループ内では出力アドレス変数ＯＵＴ_ＡＤＤＲは「４」に設定される。内部
ＷＨＩＬＥループを１回実行して出力符号語長さ保持変数ＯＵＴ_ＬＥＮに格納されてい
る値が「１」に等しくなるので、内部ＷＨＩＬＥループは終了する。
【００６７】
内部ＷＨＩＬＥループの実行で出力符号語長さ保持変数ＯＵＴ_ＬＥＮに格納される値
が「１」に等しくなった場合、出力アドレス変数ＯＵＴ_ＡＤＤＲを設定する操作に進む
。又は、内部ＷＨＩＬＥループの実行前から出力符号語長さ保持変数ＯＵＴ_ＬＥＮに格
納される値が「１」に等しい場合は、内部ＷＨＩＬＥループは実施されず、出力アドレス
変数ＯＵＴ_ＡＤＤＲを設定する操作に進む。例えば、ＷＨＩＬＥループの１回目〜３回
目のパスでは、内部ＷＨＩＬＥループの実行前から出力符号語長さ保持変数ＯＵＴ_ＬＥ
Ｎに格納される値が「１」に等しいので、内部ＷＨＩＬＥループは実施されない。出力ア
ドレス変数ＯＵＴ_ＡＤＤＲは、アドレス保持変数ＡＤＤＲに現在格納されている値と出
力符号語長さ保持変数ＯＵＴ_ＬＥＮに現在格納される値の合計に設定される。次に、文
字保持変数ＣＨＡＲに現在格納される文字が、出力アドレス変数ＯＵＴ_ＡＤＤＲに格納
される文字ストリーム内のアドレスに出力される。
【００６８】
ＷＨＩＬＥループ内の次の操作では、符号語表の更新を行う。符号語表の更新は符号語
表の終端に新しい入力を加えることに事実上相当する。続いて、符号語表に追加する符号
語アドレスＣＷ_ＡＤＤＲ、符号語列ＳＴＲ_ＩＮ及び符号語長さＬＥＮ_ＩＮの設定方法
について説明する。
【００６９】
まず、符号語表の更新プロセスは、符号語アドレスＣＷ_ＡＤＤＲに現在格納されてい
る値に「１」を加えることから始まる。すなわち、符号語アドレスＣＷ_ＡＤＤＲをイン
クリメントする。この操作は、符号語アドレスＣＷ_ＡＤＤＲが事実上符号語表の次の行
に入力される符号語アドレスであることを示している。すなわち符号語表の更新プロセス
の結果、符号語表に作成される新規入力を指している。次に、符号語列ＳＴＲ_ＩＮに、
符号語保持変数ＯＬＤ_ＣＷの内容および文字保持変数ＣＨＡＲの内容がロードされる。
文字保持変数ＣＨＡＲの内容は文字ストリームへの最新文字出力を表している。
【００７０】
ここで、符号語列ＳＴＲ_ＩＮは、符号語部分と文字部分の２つに分離された部分を含
むことがわかる。符号語列ＳＴＲ_ＩＮの符号語部分は符号語保持変数ＯＬＤ_ＣＷの内容
に対応し、符号語列ＳＴＲ_ＩＮの文字部分は文字保持変数ＣＨＡＲの内容に対応する。
次に符号語長さＬＥＮ_ＩＮに、符号語保持変数ＯＬＤ_ＣＷに格納されている符号語に対
応する長さ値に「１」を加えた値がロードされる。次に符号語列ＳＴＲ_ＩＮおよび符号
語長さＬＥＮ_ＩＮの内容が符号語表ＣＷ_ＭＥＭ［ＣＷ_ＡＤＤＲ］に格納されることで
、符号語表が１行更新される。
【００７１】
例えば、図７の時間２の行に対応するＷＨＩＬＥループの１回目のパスについて説明す
ると、符号語アドレスＣＷ_ＡＤＤＲが「２５７」に設定されているので、インクリメン
トされて符号語アドレスＣＷ_ＡＤＤＲが「２５８」に設定される。よって、固定サイズ
符号語表で、符号語アドレスＣＷ_ＡＤＤＲが「２５８」の行が更新される。次に、符号
語列ＳＴＲ_ＩＮに、符号語保持変数ＯＬＤ_ＣＷの内容１と文字保持変数ＣＨＡＲの内容
１がロードされる。次に符号語長さＬＥＮ_ＩＮに、符号語保持変数ＯＬＤ_ＣＷに格納さ
れている符号語に対応する長さ値「１」に「１」を加えた値「２」がロードされる。次に
符号語列ＳＴＲ_ＩＮおよび符号語長さＬＥＮ_ＩＮの内容がアレイ構造にＣＷ_ＭＥＭ［
２５８］＝｛（１，１），２｝が格納され、固定サイズ符号語表の符号語アドレスＣＷ_
ＡＤＤＲが「２５８」に対応する行が更新される。
【００７２】
符号語表の更新に続き、ＷＨＩＬＥループの次のパスのためにアドレス保持変数ＡＤＤ
Ｒおよび符号語保持変数ＯＬＤ_ＣＷが更新される。より具体的には、アドレス保持変数
ＡＤＤＲが、今回のパスでアドレス保持変数ＡＤＤＲに格納されていた値および今回のパ
スで符号語長さ保持変数ＬＥＮに格納されていた値の合計に設定される。加えてＷＨＩＬ
Ｅループの次のパスに備え、今回のパスで符号語保持変数ＣＷに格納されている符号語が
、符号語保持変数ＯＬＤ_ＣＷに格納される。ここで設定されたアドレス保持変数ＡＤＤ
Ｒおよび符号語保持変数ＯＬＤ_ＣＷが、ＷＨＩＬＥループの次のパスで用いられる。
【００７３】
例えば、図７の時間２の行に対応するＷＨＩＬＥループの１回目のパスについて説明す
ると、アドレス保持変数ＡＤＤＲが、今回のパスのアドレス変数ＡＤＤＲの値「０（ゼロ
）」と今回のパスの符号語長さ保持変数ＬＥＮの値「１」との合計「１」に設定される。
符号語保持変数ＣＷに格納されている符号語”１”が保持変数に格納され、符号語保持変
数ＯＬＤ_ＣＷが「１」に設定される。ここで設定されたアドレス保持変数ＡＤＤＲおよ
び符号語保持変数ＯＬＤ_ＣＷが、図７の時間３の行に対応するＷＨＩＬＥループの２回
目のパスで使われる。
【００７４】
ＷＨＩＬＥループの終了について説明する。前述したように、固定サイズ符号語表の符
号語アドレス２５７の行はファイル終端フラグとして使用される。そのため、ＷＨＩＬＥ
ループの初めで、ファイル終端フラグ２５７が現れると、ＷＨＩＬＥループは終了し、固
定サイズＧＩＦ復元法は完了する。具体的には、後述の図５（Ａ）に示すように符号スト
リームにおける符号語に”２５７”が現れると、符号ストリームの終端と認識して、ＧＩ
Ｆ復元法の処理を終了する。
【００７５】
図５（Ａ）は図２（Ａ）の文字ストリームのＧＩＦ圧縮により生成される符号ストリー
ムを例示する図である。図５（Ｂ）は図４に関し前述された固定サイズＧＩＦ復元法を適
用して生成される固定サイズ符号語表を例示する図である。図６は図４に関し前述の固定
サイズの符号語表を用いた固定サイズＧＩＦ復元法により生み出される文字ストリーム出
力を例示する図である。図７は図５（Ａ）の符号ストリームが固定サイズＧＩＦ復元法に
より処理される際、図４の擬似コードで利用される変数の内容を例示する図である。
【００７６】
符号ストリームに適用される固定サイズ復元法を、図４から図７を用いてより具体的に
説明する。
まず、図７の時間０に対応する行について説明する。図５（Ａ）の符号ストリームが符
号語表生成モジュールに入力されると、図４の擬似コードにおいて、符号ストリームの最
初の符号語”１”が符号語保持変数ＯＬＤ_ＣＷに読み込まれ、文字ストリームに列”１
”として出力される。
【００７７】
次いで、図７の時間１に対応する行について説明する。ＷＨＩＬＥループで、文字スト
リームの２番目の符号語”１”が符号語保持変数ＣＷに読み込まれる。符号語”１”は既
に符号語表の符号語アドレスが１の行に対応する符号語に存在している。そのため、文字
列保持変数ＳＴＲは”１”に設定され、文字保持変数ＣＨＡＲは”１”に設定され、符号
語長さ保持変数ＬＥＮは、「１」に設定される。その後、文字保持変数ＣＨＡＲがＯｕｔ
ｐｕｔ  ＣＨＡＲに代入され、文字ストリームに出力される。
【００７８】
続いて、符号語表の更新が行われる。符号語アドレスＣＷ_ＡＤＤＲが「２５７」に設
定されているので、符号語アドレスＣＷ_ＡＤＤＲがインクリメントされて２５８の行に
ついて更新を行う。符号語”２５８”について、符号語列ＳＴＲ_ＩＮの符号語部分の文
字列保持変数ＳＴＲは”１”に設定され符号語列の文字部分である文字保持変数ＣＨＡＲ
は”１”に設定される。また符号語アドレス２５８のおける符号語長さＬＥＮ_ＩＮは、
「２」に設定される。次に、ＷＨＩＬＥループの最後で符号語保持変数ＯＬＤ_ＣＷが”
１”、すなわち符号語保持変数ＣＷの内容に設定される。これで、文字ストリームの２番
目の符号語に関する処理は終了する。
【００７９】
次に、図７の時間２に対応する行について説明する。文字ストリームの３番目の符号語
に関する処理を行うために、固定サイズＧＩＦ復元法は次にＷＨＩＬＥループの初めにジ
ャンプし、符号ストリームにおける次の符号語の処理に進む。符合ストリームにおける次
の符号語、すなわち符号語”０”および符号語”０”が対応する符号語表の符号語”２５
９”の入力作成で処理される。この時点で符号語保持変数ＯＬＤ_ＣＷは「０（ゼロ）」
に設定、文字保持変数ＣＨＡＲは「０（ゼロ）」に設定、アドレス保持変数ＡＤＤＲは「
２」に設定され、次に使用できる符号語入力は「２６０」である。
【００８０】
次に、図７の時間３に対応する行について説明する。文字ストリームの４番目の符号語
に関する処理を行うために、固定サイズＧＩＦ復元法は次にＷＨＩＬＥループの初めにジ
ャンプし、符号ストリームにおける次の符号語の処理に進む。符合ストリームにおける次
の２つの符号語、すなわち符号語”０”および符号語”０”が対応する符号語表の符号語
”２６０”の入力作成で処理される。この時点で符号語保持変数ＯＬＤ_ＣＷは”０”に
設定、文字保持変数ＣＨＡＲは”０”に設定、アドレス保持変数ＡＤＤＲは「３」に設定
され、次に使用できる符号語入力は「２６１」である。
【００８１】
次に、図７の時間４に対応する行について説明する。ここで文字ストリームの５番目の
符号語”２５９”が符号ストリームから読み込まれる。符号語”１”はまだ符号語表に存
在しないので、文字列保持変数ＳＴＲは”１”に設定、文字保持変数ＣＨＡＲは”０”に
設定、および符号語長さ保持変数ＬＥＮは「２」に設定される。内部ＷＨＩＬＥループが
実行される時、出力符号語長さ保持変数ＯＵＴ_ＬＥＮは「２」に設定され、文字”０”
が「５」に等しい出力アドレス変数ＯＵＴ_ＡＤＤＲに出力される。ここで文字列保持変
数ＳＴＲに新しい符号語”１”がロードされ、文字保持変数ＣＨＡＲに新しい文字”１”
がロードされ、出力符号語長さ保持変数ＯＵＴ_ＬＥＮに値「１」がロードされる。次に
、文字保持変数ＣＨＡＲの内容の符号語”１”が「４」に等しい出力アドレス変数ＯＵＴ
_ＡＤＤＲに出力される。符号語表は符号語”２６１”を含むように更新される。符号語
”２６１”について、符号語列の符号語部分は”０”に設定され、符号語列の文字部分は
”１”に設定される。また、符号語”２６１”について長さは「２」に設定される。次に
符号語保持変数ＯＬＤ_ＣＷが”２５９”に設定され、アドレス保持変数ＡＤＤＲは「５
」に更新される。固定サイズＧＩＦ復元法は次にＷＨＩＬＥループの初めにジャンプし、
ファイル終端が検出されるまで、すなわち符号語”２５７”が検出されるまで、符号スト
リームの残りの処理を続ける。
【００８２】
図４〜図７に関し上述のとおり、本発明はＧＩＦ符号化データを復元する方法として具
現されることができる。方法はいくつかの符号語各々に対する符号語列および符号語長さ
を格納する符号語表を生成する操作を含む。符号語列は符号語表に前に表された符号語お
よび１つの文字によって定義される。符号語の長さは符号語列における文字の合計数を表
す。方法はさらにＧＩＦ符号化データ、すなわち符号ストリーム、における現在の符号語
を復元プロセス中にそれまでに生成された符号語表に従い翻訳し、現在の符号語により表
される一連の文字を生成する操作も含む。現在の符号語の翻訳により生成された一連の文
字はコンピュータのメモリ空間に格納される。
【００８３】
現在の符号語の翻訳により生成された一連の文字は現在の符号語に結び付いた文字列に
おける文字、および現在の符号語により参照される符号語に結び付いた符号語列を定義す
る文字を含むことが理解されよう。例えば、図５（Ａ）の符号ストリームにおける８番目
の符号語”２６４”の翻訳により生成される文字ストリームについて説明する。図５（Ｂ
）の固定サイズ符号語表を使って翻訳を行う。符号語”２６４”に対応する行として、符
号語アドレス２６４の行の符号語を参照する。符号語は”２６０”で文字が”０”である
から、文字ストリームとして０が出力される。次いで符号語”２６０”に対応する行とし
て、符号語アドレス２６０の行の符号語を参照する。符号語は”０”で文字が”０”であ
るから、文字ストリームとして”０”が出力される。同様に、文字ストリームとして”０
”が出力される。よって、符号語”２６４”の翻訳により生成される文字ストリームは、
”０”、”０”、”０”である。これらの操作は、図７の時間１０から時間１２の操作に
対応する。同様に、図５（Ａ）の符号ストリームにおける９番目の符号語”２６３”の翻
訳により生成される文字ストリームについて説明する。例えば、現在の符号語”２６３”
の翻訳により生成された一連の文字は符号語”２６３”に結び付いた文字列における文字
”０”、現在の符号語”２６３”により参照される符号語”２６１”に結び付いた符号語
列における文字”１”、および符号語”２６１”により参照される符号語”０”に結び付
いた符号語列における文字”０”を含む。従って上述の例において、現在の符号語”２６
３”の翻訳により生成された一連の文字は”０”、”１”、”０”である。一連の文字は
”０”、”１”、”０”は符号語”２６３”を文字レベルに拡張したものを表す。
【００８４】
さらに一連の文字をコンピュータのメモリ空間に格納することは一連の文字の最後の文
字に始まり一連の文字の最初の文字で終わる連続順序で現在の符号語により表される一連
の文字をコンピュータのメモリ空間に書き込むことを含むことが理解されよう。例えば図
６に関し、現在の符号語”２６３”で表される一連の文字（”０”、”１”、”０”）は
時間１３、時間１４、および時間１５にわたりメモリ空間に書き込まれる。時間１３にお
いて、一連の文字の最後の文字”０”がメモリ・アドレス１５に書き込まれる。時間１４
において、一連の文字の最後から２番目の文字”１”がメモリ・アドレス１４に書き込ま
れる。時間１５において、一連の文字の最初の文字”０”がメモリ・アドレス１３に書き
込まれる。
【００８５】
一実施形態で、固定サイズの符号語表において、符号語列の符号語部分は１２ビット値
として格納され、符号語列の文字部分は８ビット値として格納され、符号語の長さは１２
ビット値として格納される。このように、符号語表の入力は各々合計３２ビット、すなわ
ち４バイトにより定義される。符号語表の入力は各々１つの４バイト長のワードを表すと
みなすことができる。符号語表が４０９６（２12）ワードを保有するよう設定されている
場合、符号語表の全体サイズは１６３８４バイト（４０９６ワード＊４バイト／ワード）
に固定される。場合により１．５メガバイト（ＭＢ）を越え得る可変サイズの符号語表に
比べ、１６３８４バイトの固定サイズの符号語表はＧＩＦ復元プロセスの実施に必要なメ
モリ空間の点で相当な節約を意味する。このように、１６ＫＢの固定サイズの符号語表は
ＧＩＦ復元プロセスのハードウェアによる実施を可能にし、関連するハードウェア実施の
コストを抑えることができる。加えて、固定サイズの符号語表における各入力は４バイト
の固定長を有するので（可変サイズの符号語表の場合の１から１７９１バイトの可変長に
対し）、固定サイズの符号語表はＧＩＦ復元プロセスの一部としての符号語表のハードウ
ェアによる実施に必要な制御論理を非常に単純化する。
【００８６】
図８は本発明の一実施形態により、コンピュータ・プロセッサ５０１として実施される
固定サイズＧＩＦ復元法を例示する図である。コンピュータ・プロセッサ５０１は復元す
べきＧＩＦ符号化データを表す符号語のストリーム５１１を受信するよう定義される回路
を有する入力モジュール５０９を含む。コンピュータ・プロセッサ５０１はさらに接続５
１５で示されるように入力モジュールから符号語のストリーム５１１を受信するよう定義
される符号語表生成モジュール５０５を含む。
【００８７】
符号語表生成モジュール５０５はメモリ５０３に符号語表を生成するよう定義される回
路を含む。符号語表はいくつかの符号語に対し符号語列および符号語の長さを格納するよ
う定義される。符号語列は以前に符号語表に表される符合語および１つの文字により定義
される。符号語の長さは符号語列における文字の合計数を表す。
【００８８】
一実施形態で、メモリ５０３はコンピュータ・プロセッサ５０１内で定義される。別の
実施形態で、メモリ５０３はコンピュータ・プロセッサ５０１外で定義され、コンピュー
タ・プロセッサ５０１によるアクセスが可能である。接続５０７で示されるように、符号
語表生成モジュール５０５は双方向の形でメモリ５０３と通信するように定義される。
【００８９】
コンピュータ・プロセッサ５０１はさらに接続５１７経由で符号語のストリーム５１１
から現在の符号語を受信するよう定義される符号語翻訳モジュール５１９を含む。符号語
翻訳モジュール５１９は符号語のストリーム５１１において受信された現在の符号語を符
号語表に従い翻訳し、現在の符号語により表される一連の文字を生成するよう定義される
回路を含む。符号語翻訳モジュール５１９はさらに生成された一連の文字をメモリ５０３
に格納するよう定義される回路を含む。接続５１３で示されるように、符号語翻訳モジュ
ール５１９は双方向の形でメモリ５０３と通信するよう定義される。
【００９０】
図９は本発明の一実施形態による、ＧＩＦ符号化画像データを表示する装置６０１を例
示する図である。装置６０１はデジタル画像データを表示するディスプレイ６０９および
図８に関し説明されたコンピュータ・プロセッサ５０１を含む。図９の実施形態で、コン
ピュータ・プロセッサ５０１はさらに固定サイズの符号語表を用いた符号語の翻訳により
生成された一連の文字に対応する画像部分をディスプレイ６０９に表示するよう定義され
る回路を有する表示モジュール６０３を含む。表示モジュール６０３は接続６０５経由で
メモリ５０３にアクセスし、接続６０７経由で信号をディスプレイ６０９に伝送するよう
定義される。
【００９１】
当業者であれば固定サイズＧＩＦ復元法をハードウェアで実施するために必要な回路は
必要な機能性を提供するよう構成される論理ゲートを用いた半導体チップ上に定義できる
ことを理解しよう。例えば、ハードウェア記述言語（ＨＤＬ）を用いハードウェアと論理
ゲートのレイアウトを合成して本明細書に記述される機能性を提供することができる。
【００９２】
上記実施形態を念頭に、本発明はコンピュータ・システムに格納されるデータに係わる
各種のコンピュータ実施操作を用い得ることが理解されよう。これらの操作は物理的な量
の物理的な操作を必要とするものである。必ずしもではないが、通常これらの量は格納、
移転、組み合わせ、比較および別途操作され得る電気または磁気信号の形を取る。さらに
、実施される操作は産出、識別、判定、または比較などの言葉で呼ばれる。
【００９３】
本明細書で記述され発明の一部を成すいずれの操作も有用な機械操作である。発明はさ
らにこれらの操作を実施するデバイスまたは装置に関する。装置は必要とされる目的用に
特別に構成されても良く、またはコンピュータ内に格納されるコンピュータ・プログラム
により選択的に駆動されまたは設定される汎用コンピュータであっても良い。特に本明細
書の教示に従い書かれたコンピュータ・プログラムを用いた各種汎用機を用いることがで
き、または必要な操作を実施するためにより専門化した装置を構築する方が便利かもしれ
ない。
【００９４】
この発明はいくつかの実施形態により説明されたが、当業者が前述の明細書を読み図面
を調べれば各種の変更、追加、置換、および同等物を実現できることを理解しよう。従っ
て本発明は発明の真の精神および範囲に入るこのような変更、追加、置換、および同等物
すべてを含むことを意図している。
【図面の簡単な説明】
【００９５】
【図１】可変サイズの符号語表を用いたＧＩＦ復元法の擬似コードを例示する図。
【図２】（Ａ）は、ＧＩＦ圧縮法による符号化前の典型的な文字ストリームを例示する図、（Ｂ）は、（Ａ）における文字ストリームのＧＩＦ圧縮により生成された符号ストリームを例示する図、（Ｃ）は、可変サイズＧＩＦ復元法の適用において生成された符号語表を例示する図。
【図３】可変サイズＧＩＦ復元法で生み出された文字ストリーム出力を例示する図。
【図４】本発明の一実施形態に従った固定サイズＧＩＦ復元法の擬似コードを例示する図。
【図５】（Ａ）は、図２（Ａ）の文字ストリームのＧＩＦ圧縮により生成される符号ストリームを例示する図、（Ｂ）は、固定サイズＧＩＦ復元法を適用して生成される固定サイズ符号語表を例示する図。
【図６】固定サイズＧＩＦ復元法により生み出される文字ストリーム出力を例示する図。
【図７】図５（Ａ）の符号ストリームが固定サイズＧＩＦ復元法により処理される際、図４の擬似コードで利用される変数の内容を例示する図。
【図８】コンピュータ・プロセッサとして実施される固定サイズＧＩＦ復元法を例示する図。
【図９】ＧＩＦ符号化画像データを表示する装置を例示する図。
【符号の説明】
【００９６】
２５６…符号語表リセット・フラグ、２５７…ファイル終端フラグ、５０３…メモリ、
５０５…符号語表生成モジュール、５０９…入力モジュール、５１９…符号語翻訳モジュ
ール、６０３…表示モジュール、６０９…ディスプレイ。
【図１】
2008199610.tif 000003
【図２】
2008199610.tif 000004
【図３】
2008199610.tif 000005
【図４】
2008199610.tif 000006
【図５】
2008199610.tif 000007
【図６】
2008199610.tif 000008
【図７】
2008199610.tif 000009
【図８】
2008199610.tif 000010
【図９】
2008199610.tif 000011