(57)【要約】入力情報項目（２０）のシーケンスは、可変長の符号ビットグループに省スペース符号化される。各情報項目は、符号ビットグループの集合のうちの関連する符号ビットグループにマッピングされる。符号ビットグループは、その符号ビットグループの集合の中において、均一でない特定の長さを有する。符号ビットグループは、連続したビットグループのプログレッシブ区切りを可能にするとともに、ビットグループの連鎖コンフィギュレーションに連鎖されている。特に、連続するビットグループのリグレッシブ区切りを可能とするために、各ビットグループは、特定のサブグループのシーケンスに分割される。各シーケンスにおいて、サブグループは各サブ連鎖（２３，２４，２５）に割り当てられる。サブ連鎖は、関連する情報項目に関する種々のサブ連鎖コンフィグレーションの間で相互同期を保持するため、各サブ連鎖コンフィグレーションに関するポインタ情報を維持するしながら、各サブ連鎖コンフィグレーションに構成される。
2004515959.tif 000002
【特許請求の範囲】
【請求項１】
入力情報項目のシーケンスの省スペース符号化のための符号化方法であって、前記符号化方法が、
前記各情報項目を、可変長の符号ビットグループの集合のうちの関連する符号ビットグループにマッピングするステップと、
連続する前記符号ビットグループのプログレッシブ区切りを可能とするための手段を備えながら、前記符号ビットグループを前記符号ビットグループの連鎖コンフィギュレーションに連鎖するステップとを有し、
前記符号化方法が、前記各符号ビットグループを符号ビットサブグループのシーケンスに分割し、前記各シーケンスについて前記符号ビットサブグループを各サブ連鎖に割り当てることを通じて、連続する前記符号ビットグループのリグレッシブ区切りを可能とするステップと、
関連する前記情報項目に関する種々のサブ連鎖コンフィギュレーションの間の相互同期を保持するために、前記各サブ連鎖コンフィギュレーションに関するポインタ情報を維持しながら、前記サブ連鎖を前記各サブ連鎖コンフィギュレーションに構成するステップとを有する符号化方法。
【請求項２】
少なくとも１つの前記符号ビットサブグループが、単一ビットから成る請求項１に記載の方法。
【請求項３】
全ての前記符号ビットサブグループが、単一ビットから成る請求項１に記載の方法。
【請求項４】
前記各符号ビットグループが、一様に、前記符号ビットサブグループの特定のサブ連鎖に割り当てられる少なくとも１つのビットを有する請求項１に記載の方法。
【請求項５】
単一情報項目に関して、前記符号ビットグループの次のサブグループが、先行するサブグループよりも少ないビット数を有する請求項２に記載の方法。
【請求項６】
テキストインターフェースを有する埋込システム、プロセッサの命令の集合、解釈されるデータ、又は音声／ビデオ信号に適用される請求項１に記載の方法。
【請求項７】
前記符号化されるデータを、前記データに適切な前記ポインタ情報の集合を加えながら記憶又は伝送する請求項１に記載の方法。
【請求項８】
請求項１に記載された方法による入力情報項目のシーケンスの省スペース符号化のための符号化装置であって、前記符号化装置が、
前記各情報項目を、可変長の符号ビットグループの集合のうちの関連する符号ビットグループにマッピングするマッピング手段と、
連続する前記符号ビットグループのプログレッシブ区切りを可能とするための手段を備えながら、前記符号ビットグループを連鎖コンフィギュレーションに連鎖する連鎖手段とを有し、
前記符号化装置は、連続する前記符号ビットグループのリグレッシブ区切りを可能とするため、前記各符号ビットグループをサブグループのシーケンスに分割することによって連続する前記符号ビットグループのリグレッシブ区切りを可能とするための分割手段と、前記各シーケンスについて前記サブグループを各サブ連鎖に割り当てる割当手段と、関連する情報項目に関する種々のサブ連鎖コンフィギュレーションの間の相互同期を保持するために、前記各サブ連鎖コンフィギュレーションのためのポインタ情報を維持しながら、前記サブ連鎖を前記各サブ連鎖コンフィギュレーションに構成する構成手段とを有する符号化装置。
【請求項９】
少なくとも１つの符号ビットサブグループは、単一ビットから成る請求項８に記載の符号化装置。
【請求項１０】
前記各符号ビットグループは、一様に、前記符号ビットサブグループの特定のサブ連鎖に割り当てられる少なくとも１つのビットを有する請求項８に記載の符号化装置。
【請求項１１】
前記符号化されるデータを、前記データに適切な前記ポインタ情報の集合を加えながら記憶又は伝送する請求項８に記載の符号化装置。
【請求項１２】
請求項１に記載された方法により符号化される省スペース連鎖コンフィギュレーションのリグレッシブ復号のための装置であって、前記装置が、
前記連鎖コンフィグレーションのポインタを受け取るための受信手段と、
特定の符号ビットグループを区切るための区切り手段と、
区切られた符号ビットグループを出力するための関連する情報項目に復号するための復号手段とを有し、
前記区切り手段が、
第１のサブ連鎖コンフィグレーションに関連する第１のポインタ情報にアクセスするための第１のアクセス手段と、
前記第１のポインタ情報及び前記第１のサブ連鎖コンフィグレーションの符号ビットサブグループが供給され、前記符号化手段に送るための関連する符号ビットグループを再構成するために、先行ポインタ情報と先行サブ連鎖コンフィグレーションの符号ビットサブグループとに基づいて、任意の他のサブ連鎖コンフィグレーションに循環的にアクセスするための第２のアクセス手段と、
前記第１のポインタ情報を所定のステップへ進めるステップ手段とを有する装置。
【請求項１３】
請求項１に記載された方法の適用によって省スペース符号化された入力情報項目のシーケンスを有する記憶媒体であって、前記記憶媒体が、
可変長の符号ビットグループの集合のうちのマッピングされた符号ビットグループであって、連続する符号ビットグループのプログレッシブ区切りを可能とするための手段が備えられる前記符号ビットグループの連鎖コンフィギュレーションに連鎖されるマッピングされた符号ビットグループを有し、
前記記憶媒体が、連続する符号グループのリグレッシブ区切りを可能とすることによって、各符号ビットグループが符号ビットサブグループのシーケンスに分割され、前記各シーケンスが各サブ連鎖に割り当てられる符号ビットサブグループを有し、前記サブ連鎖が、関連する情報項目に関する種々のサブ連鎖コンフィギュレーションの間の相互同期を保持するために、各サブ連鎖コンフィギュレーションに関するポインタ情報に関連しながら、前記各サブ連鎖コンフィギュレーションに構成される記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、請求項１のプリアンブルに記載されたような方法に関する。
【０００２】
【従来の技術】
入力情報項目は、字、バイト、単語、マイクロプロセッサの命令等を表すことができる。それらの項目は、一定の長さ又は異なる長さを有することができる。符号化の原理は、特定の情報項目が他の項目よりもより頻繁に表れ、このため、元の情報に比較的短い符号ビットグループをマッピングすることが、符号ビットの全体的な量を減らすということである。このマッピング技術は、この分野ではよく知られている。プログレッシブ復号（ｐｒｏｇｒｅｓｓｉｖｅ ｄｅｃｏｄｉｎｇ）の場合、特定の符号ビットグループは符号化されたビットのストリームの中で区切られ、復号化され、そして次の符号ビットグループの開始が即座に明らかとなる。この復号は簡単なジョブになる。実際、種々の符号ビットグループの選択は、上記の区切りが常に簡単であるように設計される。普通は、これは、音声のような或る程度連続する信号を符号化するときの時間の流れの方向のように、最もあり得る符号化の方向に対して行われる。他方、リグレッシブ復号（Ｒｅｇｒｅｓｓｉｖｅ ｄｅｃｏｄｉｎｇ）は、選択している特別の戦略によって上記方向の単一符号ビットグループの区切りがしばしば不可能であるため、単純ではない。原理的には、試行錯誤によるリグレッシブ手続きは成功の確率が高いが、単一符号ビットグループを区切るときのいくつかの失敗により復号を戻してしまう。実際、長い復号遅延それ自体と復号遅延における拡散との両方が、復号プロセスの全体的な便宜を図るには不都合である。
【０００３】
【発明が解決しようとする課題】
結果として、とりわけ、本発明の目的は、リグレッシブ復号が次の適切な開始ポイントに瞬時に進むことができるように、ビットの各サブ連鎖に対して別々のポインタを使用することである。
【０００４】
【課題を解決するための手段】
本願発明者は、各サブ連鎖に対して個別のポインタ機構を維持しながら、符号ビットグループを各サブグループに分割すること及びこれら各サブグループを各サブ連鎖に割り当てることにより、試行錯誤の手続きで符号化されたビットグループを区切る必要なしで、復号プロセスがリグレッシブ復号を実行することが可能となることを認識した。従って、プログレッシブ復号と同じような迅速なやり方で、リグレッシブ復号を続行することができる。各符号ビットグループは、各符号ビットグループに対してコンテンツが常に同じである特有のやり方で分配されるが、種々の斯かる同一性の間で変化してもよい。
【０００５】
従って、本発明の態様の１つによれば、本発明は、請求項１の特徴部分によって特徴付けられる。
【０００６】
本発明は、入力情報項目のシーケンスを可変長の符号ビットグループに符号化し、符号ビットの各サブグループに対して別々のポインタを提供するための装置、斯かる可変長符号ビットグループのシーケンスを符号化するための装置、及びこのように符号化されたデータを有する媒体にも関する。本発明の他の有利な態様は、従属項に記載されている。
【０００７】
本発明のこれら及び他の態様並びに利点は、好適実施例の開示を基準にして、特に添付した図１乃至図６を基準にして、以下に更に詳細に記載されるだろう。
【０００８】
【発明の実施の形態】
図１は、符号ビットグループの集合を生成する一例を示す。この例では、左手側の列Ａは、各々が２ビットである４つの固有の情報項目を有する。各情報項目に対して、右手側の列Ｂは対応する符号ビットグループを含む。左側の連続する項目の発生確率をそれぞれ１／２、１／４、１／８及び１／８であると仮定すると、７／８の係数による符号化を通じてビット総数が減少することが示されている。他の確率分布及び符号マッピングにより、より大きな節約又はより小さな節約を生み出すことができる。左から右へのプログレッシブ方向（ｐｒｏｇｒｅｓｓｉｖｅ ｄｉｒｅｃｔｉｏｎ）の復号は、次の符号ビットグループが“０”ビットで終了するか又は３つの“１”ビットからなるかのいずれかの単純な方法で行われることができる。しかしながら、右から左のリグレッシブ方向（ｒｅｇｒｅｓｓｉｖｅ ｄｉｒｅｃｔｉｏｎ）の復号は必要によって最初の“０”ビットが表れるまで戻らなければならず、その“０”ビットから右に符号ビットグループを復号することしかできないため、右から左のリグレッシブ方向の復号はより複雑である。再度左に行くことは、再度同じ手続きを実行することを必要とする。多分もっと複雑な他のマッピングの場合、この問題はもっと悪化するかもしれない。更に基本的ないくつかの符号マッピングが図３及び図４に示されている。実際の多くのアプリケーションはさらに多くの情報グループの集合を使うため、複雑さの程度に応じて、ここで解決される問題を大きくしている。
【０００９】
図２は、本発明で使用するサブグループ及びポインタの構成を示す。行Ａは、図１を基準にして開示された原理に従って形成される符号ビットグループのシーケンスの一例である。図のパートＢは、概念的に単一の列に配された各符号ビットグループを有する。各符号ビットグループに対して、左端のビットは最下位行に入れられ、左から２番目にビットが存在するのであればその２番目のビットは中央の行に入れられ、左から３番目にビットが存在するのであればその３番目のビットは最上位行に入れられる。先頭ビットの最下位行への割当てによって、最下位行のビット位置を特別な符号ビットグループに割り当てることが簡単になる。しかしながら、同じ結果又はそれと同等の結果を達成するために、斯かる割当てに対して種々の他の戦略が実施可能である。
【００１０】
さらに、各行に対してビットの数が別々にカウントされ、右端の位置に最下位ビットを有する関連するポインタレジスタＰ１、Ｐ２、Ｐ３に記憶され、このため、この例では、カウントはそれぞれ５、２及び１である。復号（リグレッシブ復号のことである。ただしプログレッシブ復号も一般には同じ方法で行われなければならない）は、事実上符号ビットグループの数を示すポインタＰ１により示されるような最下位行の特別なビットにアクセスすることによって達成される。後のビットの値は、中間列からの符号ビットと最上位列からの他の符号ビットとが、復号に考慮されなければならないかどうかを示す。他の行のポインタは、どのアドレスにアクセスするべきかについて示す。ここで提示される特定の例に対して、左へ１０個の符号ビットグループだけ行くとき、Ｐ１：＝（Ｐ１−１０）であり、Ｐ２での減少分は一般にはＰ２：＝（Ｐ２−１０＋Ｎ０）よりも少ない。ここで、Ｎ０は、２つのＰ１の値の間の区間における最下位列のゼロの数である。Ｐ３に対しても同様の手続きを適用する。以下に記載されるような他の割当てパターン及び他の符号は、デクリメントするときに他の方式を必要とするが、全てのポインタは、該当するシンボルの最初の部分に基づいて規則的に進まなければならない。
【００１１】
明らかに、フルリグレッシブ復号（ｆｕｌｌ ｒｅｇｒｅｓｓｉｖｅ ｄｅｃｏｄｉｎｇ）は最下位列のビット位置を１つだけ戻ることが必要なだけである。原理的には、符号ビットグループの連続するビットに関して、図１の符号の各行への割当パターンは均一でなくてもよいが、この場合はアルゴリズムが複雑である。しかしながら、均一でない割当パターンを行っても、割当負荷をもっと均一なやり方で行に分配することができる。図２の同じ配列をプログレッシブ復号に対して用いることができる。行毎のポインタにより、関連する情報項目に関して、３つの行の種々のサブ連鎖コンフィギュレーション（ｓｕｂ−ｃｈａｉｎｉｎｇ ｃｏｎｆｉｇｕｒａｔｉｏｎ）の間の相互同期が維持される。２つの行が同一のポインタ値を有する場合、それら行のポインタは結合されてもよい。
【００１２】
図３は、プレンティスホールＰＴＲ、Ｅｎｇｌｅｗｏｏｄ Ｃｌｉｆｆｓ  ＮＪ  ０７６３２  ＵＳＡの１９９０年のＴｉｍｏｔｈｙ Ｃ． Ｂｅｌｌらによる“テキスト圧縮”という本、特に１０５−１０７ページから選ばれた符号ビットグループを形成する他の２つの例を示す。列Ａは、列Ｂの５つのシンボルの発生確率を有する。列Ｃは、シャノン／ファノ符号の符号ビットグループを有し、列Ｄはハフマン符号の符号ビットグループを有する。１０６ページには、検索木の使用によるハフマン符号のプログレッシブ復号が図示されている。情報項目が復号化されると、次の符号ビットグループの復号を、前もってその長さを知る必要無く、開始することができる。もちろん、プログレッシブ復号は、ルックアップテーブルの使用によっても行うことができる。対照的に、リグレッシブ復号は一般に符号ビットグループの左端の区切りを知らなければならず、実際、復号が実行された後にのみ知ることができる。
【００１３】
ここで、その復号を図２に関して説明された復号と比較する。シャノン／ファノでは、先行ビットの値は、上位のポインタに進まなければならない（最初のビットは１）のかどうか、又は上位ポインタに関連するビットは考慮する必要がないのかどうかを決定する。この例では、実際に、２つのポインタのみが必要である。ハフマンでは、始めの２つのビットに少なくとも１つの“１”ビットが存在することは、符号ビットグループが２つのビットしか持たないことを示す。両方のビットが“０”の場合、符号ビットグループはさらに長くなる。
【００１４】
図４は、列Ａの５つの情報ビットグループから、列Ｂの符号ビットグループを形成する更に他の例を示す。発生確率は列Ｃである。ここでも、リグレッシブ復号は、復号が開始する前に、符号ビットグループの左端を（符号ワードが示された形で）知らなければならない。これは、ポインタの使用によって簡単になる。第１のポインタが“１”を示すならば、符号ビットグループは３つのビットであり、そうでなければ、１つのビットのみである。
【００１５】
図５は、サブグループ及びポインタを形成するための概念装置構成を示す。入力部２０は、種々の情報項目を受け取る。構成要素２２は関連するレジストリ装置及び符号器を含み、各符号ビットをビット段２３、２４、２５それぞれに出力する。例えばビット段２３は図１の一番左側の符号ビットを常に受け取る。次に、種々の符号ビットは、ＲＡＭのような各記憶アレイ２６、２７、２８に記憶される。ハッチングによって示すように、これらのアレイは、部分的に書き込まれている。レジスタ２９、３０、３１は、書込みの量を示すために、種々の記憶アレイに関連している。装置の全体は、簡潔のため図示されていないクロック手段によって達成されるような同期領域３２に含まれる。
【００１６】
ほかの方法として、ブロック２２の割当ては、確率に基づいた方法（全ての情報項目の最初のパスは最適な割当てマップを作り、一方、二番目のパスは適切なマッピングを行う）で行うことができる。
【００１７】
図６は、本発明の復号フローチャートを示す。ブロック４０において、手続きが開始し、必要なハードウェア及びソフトウェア機能が割り当てられる。ブロック４２において、必要なポインタを図示されていない制御機構から受け取る。例えば、比較的大きな記憶スペースのブロックの各々に、種々のポインタの集合を供給することができる。ブロック４４において、最初の符号ビットグループが復号化される。ブロック４６において、システムは、現時点の符号ビットグループが最後のビットグループであるか否かを検出する。もし最後のビットグループでなければ、ブロック４８において、ポインタは、上述した原理に従ってステップバック又はデクリメントされる。これは、各ビットに対して別々に決定される。次に、システムはブロック４４に戻る。最後のビットグループが実際に符号化されると、システムはブロック５０に進み、任意の他のポインタの集合が待っているかどうかを決定する。待っているならば、システムはブロック４２に戻る。待っていなければ、システムはブロック５２に進み、ブロック４０で最初に割り当てられた機能を放棄し、手続きが終了する。
【００１８】
上述したように、特別のビットグループのサブグループは、均一なサイズを有する必要はない。図３Ｃでは、第１のサブグループは２つのビットを有し、第２のサブグループは１つのビットのみを有する。図３Ｄでは、第１のサブグループは２つのビットを有し、第２及び第３のサブグループの各々は、１つのビットのみを有する。図４では、第１のサブグループは１つのビットのみを有し、第２のサブグループは２ビットを有する。さらに、原則として、各ビットグループ内の同じ序列のサブグループは、同じ長さを有する必要はない。サブグループの特別なサブ連鎖（図２Ｂにおける行）の割当ては、固定する必要はない。例えば、図２Ｂの連続する符号ビットグループが第３、第２、第１、第３の行…に連続して割り当てられる第１のサブグループを有するように、割当てを循環させてもよい。
【００１９】
提案された本発明の戦略は、種々の異なるアプリケーションに役立つ。マイクロプロセッサの命令の集合を符号化する間、制御システムは、圧縮ストリームの中を、選択された数の命令だけ後方にジャンプすることが可能である。好ましくは、記憶媒体上に中間ポインタを別々に記憶することによってそれら中間ポインタを利用できるようにしてもよい。実際、必要なスペースは最小限度ですむ。情報項目は、有限状態機械で使われるような、解釈されるデータであってもよい。もう一つのアプリケーションは、逆再生、高速巻戻し等のようなリバース機能による処理を受ける音声／ビデオ信号の符号化だろう。さらに、この技術は、ポインタが前の圧縮データを示す“ポインタ＋長さ”戦略により、情報ストリングの圧縮が可能である。本発明の斯かる特徴は、テレビ、携帯電話、パーソナル携帯情報機器、オンラインヘルプ等のような、テキストのユーザインタフェースを有する又は解釈動作を受けるデータを使用する組込システムに関連させてもよい。
【００２０】
本発明は、次のように要約することができる。入力情報項目のシーケンスは、可変長の符号ビットグループに省スペース符号化される。各情報項目は、符号ビットグループの集合のうちの関連する符号ビットグループにマッピングされる。この符号ビットグループは、その符号ビットグループの集合の中において、均一ではない特定の長さを有する。次に、符号ビットグループは、連続するビットグループのプログレッシブ区切りを可能にするとともに、ビットグループの連鎖コンフィグレーションに連鎖される。特に、連続するビットグループのリグレッシブ区切りを可能とするために、各ビットグループは、特有のサブグループのシーケンスに分割される。各シーケンスにおいて、サブグループが各サブ連鎖に割り当てられる。サブ連鎖は、関連する情報項目に関する種々のサブ連鎖コンフィギュレーションの間で相互同期を保持するために、各サブ連鎖コンフィギュレーションに関するポインタ情報を維持しながら、各サブ連鎖コンフィギュレーションに構成される。
【図面の簡単な説明】
【図１】符号ビットグループの集合を生成する一例である。
【図２】サブグループ及びポインタの構成である。
【図３】符号ビットグループを形成する他の例である。
【図４】符号ビットグループを形成する更に他の例である。
【図５】サブグループ及びポインタを形成するための概念装置配列である。
【図６】復号フローチャートである。
【国際公開パンフレット】
2004515959.tif 000003
2004515959.tif 000004
2004515959.tif 000005
2004515959.tif 000006
2004515959.tif 000007
2004515959.tif 000008
2004515959.tif 000009
2004515959.tif 000010
2004515959.tif 000011
2004515959.tif 000012
2004515959.tif 000013
2004515959.tif 000014
2004515959.tif 000015
2004515959.tif 000016
【国際調査報告】
2004515959.tif 000017
2004515959.tif 000018
2004515959.tif 000019