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