(57)【要約】1つの態様に従って、データ圧縮方法が開示される。2009542093.tif 000004
2009542093.tif 000002
【特許請求の範囲】
【請求項１】
（a）符号が指数値Eiおよび剰余値Riを含み、iが整数数字である、符号系列を形成する工程；および
（b）符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成する工程
を含む、データ記号の系列を符号化する方法。
【請求項２】
iが、位置の値に関連づけられた整数数字を含む、請求項1記載の方法。
【請求項３】
一つまたは複数の位置の値が後に続くようにおよび/または先行するように、一つまたは複数の剰余値が、系列内で一緒にグループ化される、請求項2記載の方法。
【請求項４】
位置の値および剰余値をストリングとして送信または記憶する工程を更に含む、請求項2記載の方法。
【請求項５】
ストリングが、エンド・オブ・グループ記号によって終了される、請求項5記載の方法。
【請求項６】
ストリングの長さを表現する情報が、該ストリングへ接頭語として付けられる、請求項5記載の方法。
【請求項７】
指数値の数を表現する情報が、ストリングへ接頭語として付けられる、請求項5記載の方法。
【請求項８】
ストリング内の最終の位置の値の後に、ノー・モア・グループ記号が続く、請求項5記載の方法。
【請求項９】
剰余値が、ストリング内で、対応する位置の値に具体的に関連づけられる、請求項5記載の方法。
【請求項１０】
符号系列がゴロム符号系列を含み、符号がゴロム符号を含む、請求項2記載の方法。
【請求項１１】
ゴロム符号および位置の値は2進形式の表現を含む、請求項10記載の方法。
【請求項１２】
一つまたは複数の位置の値がランレングス符号化される、請求項2記載の方法。
【請求項１３】
位置の値が、更なる系列として処理され、更に符号化される、請求項2記載の方法。
【請求項１４】
更なる系列がゴロム符号として符号化される、請求項13記載の方法。
【請求項１５】
データ記号はオーディオまたはビデオ・ストリームを表現する、請求項1記載の方法。
【請求項１６】
符号内で生じるEの選択された値について、Eの値を表現する該符号内の位置の値がiを含む、請求項1記載の方法。
【請求項１７】
（i）データ記号について、
（a）bが固定モジュロ値である場合、bEiがViを超過しない指数Eiの最大整数値を決定する工程；および
（b）剰余Ri = Vi - bEiを計算する工程；
（ii）該指数Eiを符号系列として取り、生じるEiの値について、Eiの該値を表現する符号系列内の位置の値を生成する工程；ならびに
（iii）該剰余RiをEiの該値に関連づける工程
を含む、データ記号の系列を数字Viによって数字形態で表現される記号に符号化する方法。
【請求項１８】
符号内の位置の値が、iの値に関連づけられた値を含む、請求項17記載の方法。
【請求項１９】
一つまたは複数の位置の値がランレングス符号化される、請求項18記載の方法。
【請求項２０】
データ記号がオーディオまたはビデオ・ストリームを表現する、請求項17記載の方法。
【請求項２１】
命令を実行すると、
（a）iが整数数字であるとしたとき、符号が指数値Eiおよび剰余値Riを含む符号系列を形成する工程、および
（b）符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成する工程
のようにデータ記号の系列を符号化する方法の遂行が更にもたらされる、
該命令を記憶した記憶メディアを含む物品。
【請求項２２】
命令を実行すると、位置の値に関連づけられた整数数字を含むiが更に生じる、請求項21記載の物品。
【請求項２３】
命令を実行すると、一つまたは複数の位置の値が後に続くようにおよび/または先行するように一つまたは複数の剰余値が系列内で一緒にグループ化される結果が更に生じる、請求項22記載の物品。
【請求項２４】
命令を実行すると、位置の値および剰余値をストリングとして送信または記憶する結果が更に生じる、請求項22記載の物品。
【請求項２５】
命令を実行すると、符号内で生じるEの選択された値について、Eの値を表現する該符号内の位置の値がiを含む結果を更に生じる、請求項21記載の物品。
【請求項２６】
iは整数数字であるとしたとき、指数値Eiおよび剰余値Riを含む符号の系列を形成する手段と、符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成する手段とを含む装置。
【請求項２７】
一つまたは複数の位置の値が後に続くようにおよび/または先行するように、系列内で一つまたは複数の剰余値を一緒にグループ化する手段を更に含む、請求項26記載の装置。
【請求項２８】
命令を実行すると、位置の値および剰余値をストリングとして送信または記憶する結果が更に生じる、請求項26記載の装置。
【請求項２９】
コンピューティング・プラットフォームが、符号が指数値Eiおよび剰余値Riを含み、iが整数数字である、符号系列を形成するように適用され、かつ符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成するように適応される、コンピューティング・プラットフォームを含む装置。
【請求項３０】
コンピューティング・プラットフォームが、整数数字iを位置の値に関連づけるように更に適応される、請求項29記載の装置。
【請求項３１】
一つまたは複数の位置の値が後に続くようにおよび/または先行するように、プラットフォームが、系列の中で一つまたは複数の剰余値を一緒にグループにするように更に適応される、請求項30記載の装置。
【請求項３２】
コンピューティング・プラットフォームは、位置の値および剰余値をストリングとして送信または記憶するように更に適応される、請求項30記載の装置。
【請求項３３】
コンピューティング・プラットフォームは、符号内で生じるEの選択された値について、Eの該値を表現する該符号内の位置の値をiとして割り当てるように更に適応される、請求項21記載の装置。
【請求項３４】
命令を実行すると、
（i）データ記号について、
（a）bが固定モジュロ値であるとしたとき、bEiがViを超過しない指数Eiの最大整数値を決定する工程、および
（b）剰余Ri = Vi - bEiを計算する工程；
（iv）該指数Eiを符号系列とし、かつ生じるEiの値について、Eiの該値を表現する符号系列内の位置の値を生成する工程、および
（v）該剰余RiをEiの該値に関連づける工程
のように、データ記号の系列を符号化し、記号が数字Viによって数字形態で表現される方法の遂行をもたらす、
命令を記憶された記憶メディアを含む物品。
【請求項３５】
命令を実行すると、符号内の位置の値が、iの値に関連づけられた値を含む結果が更に生じる、請求項34記載の物品。
【請求項３６】
命令を実行すると、一つまたは複数の位置の値がランレングス符号化される結果が更に生じる、請求項35記載の物品。
【請求項３７】
命令を実行すると、データ記号がオーディオまたはビデオ・ストリームを表現する結果が更に生じる、請求項35記載の物品。
【請求項３８】
bが固定モジュロ値であるとしたとき、データ記号について、bEiがViを超過しない指数Eiの最大整数値を決定して剰余Ri = Vi - bEiを計算し、
該指数Eiを符号系列として取り、生じるEiの値について、Eiの該値を表現する符号系列内の位置の値を生成し、かつ
該剰余RiをEiの該値に関連づける
ように適応されるコンピューティング・プラットフォームを含む装置。
【請求項３９】
コンピューティング・プラットフォームが、符号内の位置の値をiの値に関連づけられた値に割り当てるように適応される、請求項38に記載の装置。
【請求項４０】
コンピューティング・プラットフォームが、一つまたは複数の位置の値をランレングス符号化するように適応される、請求項35に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
分野
本特許出願は、データ圧縮に関する。
【背景技術】
【０００２】
背景
周知のように、記憶または送信のための効率的データ符号化は、引き続き新しいアプローチが探索される領域である。例えば、データが、例えば圧縮によって、より効率的に符号化されるならば、符号化されるべきデータを記憶するメモリ量は低減されうる。同様に、通信システムにおいて、データが、例えば所与の帯域幅の通信チャネルのために、効率的に符号化されるならば、潜在的に、より多くの情報が所与の時間単位で送信されうる。これらの目標および多くの他の目標は、データの効率的圧縮方法の目的となる可能性がある。
【発明の概要】
【０００３】
本発明は、（a）符号が指数値Eiおよび剰余値Riを含み、iが整数数字である、符号系列を形成する工程；および（b）符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成する工程を含む、データ記号の系列を符号化する方法、装置、および物品である。
【０００４】
対象は、本明細書の結末部分で特に指摘され、明確に主張される。しかしながら、特許請求される対象は、後記の詳細な説明を参照することによって、添付の図面と一緒に読まれる場合、機構および動作方法の双方について、対象の目的、特質、および利点と共に最良に理解されるかもしれない。
【図面の簡単な説明】
【０００５】
【図１】データ符号化手法の1つの態様を図解する略図である。
【発明を実施するための形態】
【０００６】
詳細な説明
後記の詳細な説明では、多くの具体的細部が記述され、特許請求される対象の徹底的理解を提供する。しかしながら、特許請求される対象は、これらの具体的細部なしに実施されてもよいことが、当業者によって理解される。他の場合には、特許請求される対象を不明瞭にしないように、周知の方法、手続き、コンポーネント、および/または回路は詳細に説明されていない。
【０００７】
後記の詳細な説明の幾つかの部分は、コンピューティング・システムの内部、例えば、コンピュータおよび/またはコンピューティング・システム・メモリの内部に記憶されたデータ・ビットおよび/または2進ディジタル信号に対する動作のアルゴリズムおよび/または記号表現の見地から提示される。アルゴリズムによるこれらの説明および/または表現は、データ処理技術の当業者によって使用される手法であり、それら当業者の作業の内容を他の当業者へ伝達する。アルゴリズムは、本明細書において、および一般的に、所望の結果につながる動作および/または同類の処理の首尾一貫した系列として考えられる。動作および/または処理は、物理量の物理的操作を伴ってもよい。典型的には、必ずというわけではないが、これらの量は、記憶、転送、結合、比較および/または操作することが可能な電気信号および/または磁気信号の形態を取ってもよい。時には、主に共通使用を理由として、これらの信号をビット、データ、値、要素、記号、文字、項、数、数字および/またはその他として参照することが便利であることが証明されている。しかしながら、これらおよび同類の用語の全ては、適切な物理量に関連づけられ、便利なラベルにすぎないことを理解すべきである。他に具体的に言明されない限り、後記の論議から明らかであるように、本明細書の全体を通して、「処理」、「コンピューティング」、「計算」、「決定」、および/またはその他のような用語を利用する論議は、コンピューティング・プラットフォーム、例えば、コンピュータまたは同類の電子コンピューティング・デバイスの行動および/またはプロセスを指すことが了解される。コンピューティング・プラットフォームは、コンピューティング・プラットフォームのプロセッサ、メモリ、レジスタ、および/または他の情報記憶、送信デバイス、および/または表示デバイスの内部で、物理電量および/もしくは磁気量ならびに/または他の物理量として表現されたデータを操作および/または変換する。
【０００８】
前述のように、本願発明の態様の、排他的でない1つの潜在的応用は、低ビットレートのオーディオおよび/またはビデオ符号化の分野であり得る。この特定の分野において、例えば、データを比較的に効率よく圧縮することが典型的に望まれる。この分野および類似の分野において、前に示唆されたように、通信チャネル、例えば、送信されるビットの数、またはビット送信レートの制限に供されるチャネル全体に情報を送信することも望まれるかもしれない。従って、比較的に効率のよい符号化は、例えば、より多くの情報が単位時間当たりに送信される結果となり得る。同じく前に示唆された他の応用は、例えば、データを記憶するための、電子デバイス上のデータ圧縮かもしれない。データ圧縮は、例えば、採用されるメモリの量を低減するかもしれず、または他の例として、電子メールの添付物のサイズを低減することによってデータ送信を容易にするかもしれない。もちろん、特許請求される対象は、これらの単純な例に限定されない。これらの例は、単に例証を目的として提供される。
【０００９】
ゴロム符号化は周知であり、Golomb, SW: 'Run-length encodings', IEEE Trans. Inf. Theory, 1966, 7, (12), pp. 399-401で説明されている。ゴロム 符号は、データ符号化の単なる1つの例である。従って、後で説明される例の多くはゴロム符号化の見地から提示されるが、特許請求される対象は、単にゴロム符号（GC）へ範囲を限定されるものではないことが意図されることを明らかにしておかなければならない。データ符号化の他のアプローチが採用され、満足な結果を提供してもよい。それにも拘わらず、ゴロム符号化を1つの例として続けると、GCは、しばしばランレングス符号化に使用されるが、原理的にはGCは汎用符号であり、任意の記号または記号系列を整数数字または整数数字系列としてエンコードするために使用されてもよい。1つの可能な態様において、一意の整数数字が記号へ割り当てられてもよく、次いで記号は、例えば、対応する数字をゴロム符号化することによって符号化されてもよい。GCは、数字の値域を前もって知るか制約する必要がないという利点を有する。
【００１０】
1つの特定の例において、数字I、モジュロK（ここで、Kはこの例では「基底」である）のゴロム符号は、次のように（S、E、R）によって定義されてもよい。
S = 適切な場合、数字Iの符号（数字が全て正または全て負であれば、省略されてもよい）
M = Iの大きさ
E = 指数fix(logK(M))、本願明細書ではfix()は打ち切り動作、即ち、次の最低整数数字へ丸めることを表す。
R = M - KE は、本願明細書では「剰余」と呼ばれる。
従って、Iの大きさは、M = KE + Rによって得られてもよい。
【００１１】
しかしながら、logK(0)は、任意の累乗されたKはゼロを提供すべきでないという点で、数学的奇抜さを提供し得ることが注意される。これに対処するために採用される1つのアプローチは、全ての非負の整数数字へ1を加え、logK(0)が生じないようにすることを含む。もっとも、もちろん、特許請求される対象は、この点に関して範囲を限定されない。
【００１２】
時には、便宜上、例えば、K = 2であり、例えば、ゴロム符号は、指数Eおよび可変長Eビットの剰余Rを有する可変長2進浮動小数点表現形態を提供することができる。このケースは、例えば、図1で図解される。もっとも、もちろん、特許請求される対象は、この点に関して範囲を限定されない。
【００１３】
「Data Coding」と題しMonroによって2006年6月5日に出願され、現在特許請求される対象の譲受人へ譲渡された同時係属中米国特許出願第11/422,316号で説明されるように、1つの態様において、ゴロム符号化を含むデータ記号の符号化方法が採用されてもよい。しかしながら、前に解明したように、特許請求される対象はゴロム符号化へ範囲を限定されない。そのような態様において、記号は指数値Eおよび剰余値Rによってゴロム符号化されてもよい。指数値は、再び下記で一層詳細に説明されるように、実質的に可変長符号に従って符号化される。
【００１４】
この特定の態様において、例えば、可変長符号（VLC）が採用され、記号と置き換わってもよい。その場合、短い符号は、より頻繁に生じる記号のために使用されてもよく、より長い符号は、より少ない頻度で生じる記号のために使用されてもよい。このようにして、符号の平均長が低減されてもよい。VLCの1つの周知の例は、Huffman符号化を含む。もっとも、多くの他の例が存在する。例えば、Fano/Shannon符号化はVLCを含む。Morse符号も同じであるが、Morse符号は、Eのように頻繁に生じる文字を短い符号（1つのドット）で置き換え、Xのような他の文字を、より長い符号（ダッシュ・ドット・ドット・ダッシュ）で置き換える。もちろん、特許請求される対象はこれらの例へ範囲を限定されない。これらは、単に例証を目的として提供される。
【００１５】
同様に、他の態様は、記号を、対応する正の非ゼロ数字Vによって符号化する方法を含みうる。bが整数数字モジュロ値であり、E = fix(logb(V))であるとき、bEがVを超えない指数Eの最大整数値が決定されうる。同様に、剰余R = V - bEが計算されうる。従って、可変長符号として符号化された指数の値および剰余値を含む記号符号が生成されてもよい。もちろん、特許請求される対象は、この特定の態様へ範囲を限定されない。これは、特許請求される対象の範囲の中に含まれる態様の1つの例にすぎない。
【００１６】
様々な修正が可能であり、全ての修正は、特許請求される対象の範囲内に含まれることを意図される。例えば、1つの代替の態様において、記号は記号アルファベットの中に任意で収容されてもよい。記号アルファベットは、期待された生じる確率によって記号を順位づけ、Vの値が記号の順位を表現する。
【００１７】
同様に、1つの態様において、記号のストリームを効率的に符号化および圧縮するため、可変長符号器（VLC）、例えば、Huffman符号器などが、ゴロム符号のような符号の指数をエンコードしてもよい。しかしながら、VLCは、例えば特定の態様に依存して、適応型であるか固定型であってもよい。
【００１８】
特許請求される対象は、この点に関して範囲を限定されないが、本明細書で説明される符号化手続きの態様は、現実の応用で時にはHuffman符号化よりも優れた性能であることが注意される。同様に、特許請求される対象は、この点に関して範囲を限定されないが、態様は、ランレングス符号化へ便利に適用され、および/または厄介な確率分布と一緒に使用されてもよい。もっとも、これらは単なる例であり、特許請求される対象は、この点に関して範囲を限定されない。
【００１９】
例示的な態様は、データ符号化方法の態様に加えて、そのような方法を組み込んでいるコンピュータ・プログラム、および/または符号器、例えば、ハードウェア、ファームウェア、ソフトウェア、またはこれらの組み合わせで実現される符号器を含んでもよい。態様は、そのような方法を体現するビデオおよび/またはオーディオ・コーデック、ビデオおよび/またはオーディオ圧縮システムも含んでもよい。これらのシステムによって、データはそのような方法に従ってエンコードされ、次いでそのようなデータは通信チャネル全体に送信され、復号器によって遠隔端で再構築されてもよい。あるいは、符号化されたデータは、送信されず記憶されうる。これらの態様および多くの他の態様は、特許請求される対象の範囲の中に含まれる。
【００２０】
図1は、例えば、符号および大きさの表現を使用するゴロム符号化Nビット固定小数点2進数字の態様を示す。先導ビットS（これは、代替の態様で省略されてもよい）は符号を表示する。符号の後に、或る数の非有意先導ゼロが続く。最初の有意ビット（FSB）は場所Eで生じ、それによってFSBの場所は指数値を表示する。残りのビットは後続のEビットによって表現される。これはこの文脈では「剰余」Rとして知られる。この表現における数字の大きさMは、単純に、0からN-1までのラベルを付けられたNビットによって表現される2進数字の値である。
ここで、符号 = 1または0
同様に、大きさ = M = Σ2nbn
ここでbnはビットnの値、即ち0または1であり、総和はn = 0からNまでである。
E = FSBの位置 = fix(log2M)、M >= 1について
R = 剰余 = M - 2E
剰余は、E >= 1およびM >= 2についてEビットを有する。
【００２１】
図1の表現が与えられたと仮定して、通信チャネル全体にデータを送信するため、この態様において、位置の値Eおよび剰余値Rと一緒に、（適切な場合）Sの値を送ってもよい。典型的には、剰余値はエンコードされず、ビットはそのとおりに単純に1つずつ送られる。しかしながら、もちろん、幾つかの態様で剰余のエントロピ符号化が採用されてもよい。
【００２２】
Eを送信するためのビット数は、剰余を送るためのビット数と同じように、典型的には可変である点において、Eの値の送信は、幾つかの状況において困難であるかもしれない。ゴロム符号器を実現する普通の方途は、Eの値を送信するのではなく、代わりに、送られた最後の値に関してEの変化を送信することである。例えば、第1の記号の送りは、Eの値が1だけ増加されたことを表示してもよく、第2の記号の送りは、値が1だけ減少されたことを表示してもよい。第3の記号の送りは、Eの値が同じままであることを表示してもよい。Eの連続する値の間の差は、実際には、連続するビットとして送信されてもよい。もっとも、特許請求される対象は、この点に関して範囲を限定されない。更なる詳細は、例えば、Rice, RF: 'Some practical universal noiseless coding techniques', Tech. Rep. JPL-79-22, Jet Propulsion Laboratory, Pasadena, CA, March 1979に見出される。Huffman符号化も、周知のデータ符号化方法である。Huffman符号化の詳細は、Huffman, D.: 'A method for the construction of minimum redundancy codes', Proc. Inst. Radio Eng., 1952, 9, (40), pp. 1098-1101の中に見出される。
【００２３】
2進の場合、生じるEの最大値がMax_Eであれば、0からMax_Eまでの全ての値の非符号化表現は、1 + fix(log2Max_E)ビットを採用する。数字の値域を知る必要がないことは、ゴロム符号の特質であるから、Max_Eのサイズを知る必要はないことになる。しかしながら、一度、特定の数字についてEが知られると、Rの値はEビットを採用することが知られる。
【００２４】
例示的な態様としてのゴロム符号化は、少なくとも部分的には良好に働く。なぜなら、Mの確率密度が一様でないか非対称であるケースでも、Rの確率密度は通常は比較的平坦だからである。分布の非対称は、一般的に良好な振る舞いである一様であっても、Eの分布で大きく表現される。Eの上には平滑効果が存在する。なぜなら、1よりも大きい任意のEの任意の値は、この特定の態様においてMの2Eの異なる値の値域をカバーするからである。Rの上には平坦化効果が存在する。なぜなら、Rの値の数は、Mの可能な値の数よりも小さいからである。この特定の態様の1つの局面は、符号器の効率的動作が、少なくとも部分的に、Eを符号化する「コスト」に依存することを認識することに関係する。従って、このコストの低減が望ましい。例えば、Eの値域が制約され、例えば、1 < E < Max_Eであれば、1 + fix(log2(Max_E-1))ビットの2進数字E-1によってEを符号化することが許容される。この文脈で、単純にEのビットによって生符号としてEを符号化する方法を定義する。更にまた、KおよびMax_Eの双方が2のベキであれば、これは良好な結果を産出することができる。もっとも、特許請求される対象は、もちろん、この点に関して範囲を限定されない。
【００２５】
生の符号、例えば生のゴロム符号の採用がデータを符号化する合理的手法を提供し得ることを示すため、比較の例が役立つかもしれない。数字の系列を送信したいものと想定し、1から8までの全ての数字は、連続する数字間で相関しないことが同程度に確からしいと想定する。実際上、これは8面のサイコロを投げる結末と似ている。そのようなデータを符号化および送信する1つの方途は、可変長符号器（VLC）、例えばHuffman符号器を使用することである。
【００２６】
周知のように、この数字系列の理論的符号化コスト、またはエントロピはlog28 = 3ビットであり、単純に値を3ビットとして送ることが最適符号である。理論では、良好に構築されたVLC、例えばHuffman符号器が、これを認識して最適符号も産出する。しかしながら実際には、これは起こりえない。例えば、VLCが適応型であり、観察された平坦生起ヒストグラムを有する可能性が高くない数字の実系列からVLC符号を形成しているような場合である。このようにして、例えば、VLCが、異なる確率を有するものとして記号に割り当て、最も普通であると符号器が決定する記号へ1ビット符号を割り当て、次の記号へ2ビット符号を割り当て、以下同様に割り当てることが可能であり得る。この例において、1から7までの数字は1から7までのビットを有すると想定でき、同じように値8を7ビットによって符号化してもよい。このケースにおいて、VLCは平均で1/8(1+2+3+4+5+6+7+7)ビットを使用する。ここで、35/8 = 4.375ビットであり、最適よりもほぼ46％大きい。Huffman符号器が、時にはそのように悪い性能であるとは、一般的に了解されない。
【００２７】
他方、生のゴロム符号は、同じ数字系列を送信するとき、より良好に働く。もっとも、これは単なる1つの可能な例である。このケースにおけるEの値域は0〜3であり、2ビットを用いて、これを通信してもよい。
【００２８】
8つの可能な数字に採用されるビットの数を列挙することができる。
2009542093.tif 000003
この符号は平均で26/8ビットを使用し、ここでは最適よりも約8％のオーバーである。8が最大数字であることを前もって知らないと言うならば、8が生じる場合の4ビット剰余を準備してもよい。従って、平均は30/8ビット、または最適よりも25％のオーバーである。それにも拘わらず、この例が実証するように、生のゴロム符号は、ここではHuffman符号よりも性能が良い。
【００２９】
この点において、送信されるべきデータが、例えば、一連のゴロム符号を含むならば、既存または最新技術のシステムまたはアプローチを用いて個々の符号を1つずつ送信するよりも、系列を全体として考慮することによって、更なる圧縮が達成されることが注意される。
【００３０】
図1の略図で図解されるように、ゴロム符号は典型的には形態（S、E、R）を含む。ここで、Sは符号を表現し、Eは指数を表現し、Rは剰余を表現する。従って、そのようなゴロム符号の系列を含むデータ・ストリームは、1つの例において、少なくとも、次の形態を取る。
S1 E1 R1 S2 E2 R2 S3 E3 R3 ...S8 E8 R8
【００３１】
8つの（または、どれほど多くが存在しても）ゴロム符号からなるこの系列を単一のストリングとして処理することによって、追加の圧縮が達成されてもよい。この特定の例において、これはEiの異なる値について達成されてもよい。ここで、Iは、Eiが生じる位置iを経由した整数数字を表現する。圧縮のためには、値Eiの系列が特定の関心をもつことができる。なぜなら、Riの値は典型的には有意の更なる圧縮を受け入れず、従って、単純な、即ち、圧縮されない値として送信されうるからである。同様に、符号Siが存在するならば、それらの符号は、符号ストリームの中へ便利に組み入れられうる。もちろん、全てのデータが同じ符号であれば、符号Siは省略されてもよい。
【００３２】
ここで、ゴロム符号の系列が単一のストリングとして処理されるべきであると仮定する。結果として、値は任意の便利な順序で送信されてもよい。一度、特定のEiの値が知られると、それは関連づけられたRiの中のビットの数を定義する。従って、幾つかの態様において、Eiの後に、その対応するRiが続くことが便利である。しかしながら、多くの他の配列が、もちろん可能である。例えば、ストリングの終端まで、幾つかまたは全てのRおよびS値を遅らせることである。特許請求される対象の範囲は、任意および全てのそのような可能な配列を含むことが意図される。
【００３３】
ストリング内のR値（および、もしあればS値）の場所は、圧縮の有意な劣化なしに変動されてもよいと仮定する。結果として、論議および図解を便利にする目的で、他の値を有しないEi値の系列を考慮する。即ち、図解のために、特定のストリング内のそれぞれのEi値の配列が、次のようであると仮定する。
E1    E2    E3    E4    E5    E6    E7    E8
1     4     2     1     3     2     4     4
【００３４】
この特定の態様において、必要に応じて、Eiの可能な値のストリング内の位置iを記録および同様に送信してもよい。したがって、上記の例において、値1はストリング内の位置1および4で発見され、値2は位置3および6で発見され、値3は位置5で発見され、値4は位置2、7、および8で発見される。この情報は、任意の便利なやり方でエンコードされてもよく、例えば、記憶または送信されてもよい。これを達成する1つの方途は、次の記号を通信することである。もっとも、これは単に1つの例であり、特許請求される対象の範囲を限定することを意図されない。
1 4 EOG 3 6 EOG 5 EOG 2 7 8 EOG
ここで、EOGは、グループの終わりを表現するために使用され、この例では、グループ化されたE値の系列の終わりを表現する。
【００３５】
より一般的な用語では、符号器はE値の値域を調べ、Eの値を含む系列内の、例えばゴロム符号の位置を表示してもよい。疑似コードにおいて、このアプローチの1つの潜在的な表現は、次のとおりである。もっとも、これは単なる例である。
For E = E値の値域
Eを収容するゴロム符号の位置を表示する
Eグループの終わりを表示する(EOG)
End
【００３６】
剰余Ri、および適切な場合、符号Siは、上記で言及されたように、任意の便利な場所、例えば、位置符号の後またはEOG記号の後でインタリーブされて通信されてもよい。Ei値が、例えば、復号器によって再構築されるのであれば、復号器は、追加のデータを受け取ることなく、関連づけられたRiの長さを決定してもよく、追加のデータを受け取ることなく、後に続くRiビットの期待数を決定してもよい。前記期待数は、上記で解明されたように、Ei >= 1およびMi >= 2についてEiビットである。ここで、Mi = 2E + Riである。
【００３７】
上記で論議された態様において、復号器は、例えば、グループの中のEの値を具体的に表現するデータを実際には送信されないことが注意される。その代わりに、そのような情報は暗黙的であり、位置情報、例えば、この特定の態様について記号の送信されたリスト内のグループの位置から誘導可能である。多くの他の異なる態様が、特許請求される対象の範囲内に含まれることも、もちろん注意される。例えば、特許請求される対象は、位置と、送信されている特定のデータ値との間の関連づけに関して、特定の約束へ範囲を限定されない。多数の可能な配列または関連づけの任意の1つが可能であり、主張される手段の範囲内に含まれる。
【００３８】
同様に、Eiの可能な値がストリングの中に存在しなければ、1つの例として、ヌルグループが送信されてもよい。例えば、1つの特定の態様において、これは、例えば、「EOGEOG」のように余分のEOG記号によって表示されてもよい。余分のEOG記号は、空虚なグループについて適切な位置にある。もちろん、これは再び単に1つの態様であり、値が存在しないことを通信するための多くの他のアプローチが、特許請求される対象の範囲内で採用されてもよい。
【００３９】
たった今説明された特定の態様は、従来のデータ圧縮アプローチに勝る効率を提供することが注意される。しかしながら、下記で説明されるように、追加の効率も達成されてもよく、そのような態様も、特許請求される対象の範囲内に含まれることが意図される。例えば、位置1〜8は一度生じる。従って、典型的には、記号当たり3ビットが採用されて、符号化方法によってこれを通信してもよい。しかしながら、その代わりに、圧縮を改善する任意の他のアプローチが、例えば、ランレングス・エンコーディングのように位置の間のギャップを表示する。この場合、その後に4が続く1を送ってE値1の位置を表示する代わりに、0を送ってEの最初の生起の前に位置がスキップされなかったことを表示し、2を追随させて2つの位置がスキップされ、位置1から位置4へ達したことを表示してもよい。以下同様である。
0 2 EOG 2 2 EOG 4 EOG 1 5 0 EOG
これは、記号が少なくなること、ここでは0、1、2、4、5、およびEOGによって、より効率的である。
【００４０】
しかしながら、効率は、特許請求される対象の範囲内の他の態様で更に改善されてもよい。送信が進行するにつれて、典型的には、ランレングス符号器の利用可能な空間は小さくなる。というのは、ますます多くの値が知られてくるからである。したがって、例えば、最初のEグループが通信されると、それだけでなくE=1の位置が知られる。加えて、これらの位置は、処理中に後のE値の可能な位置としては無視されてもよい。従って、ランレング符号は処理中にこれらの値を「無視」してもよく、次のようにスキップされるべき未知の位置を合図してもよい。
0 2 EOG 1 1 EOG 1 EOG 0 0 0 EOG
ここで、記号の数は0、1、2、およびEOGへ効果的に更に低減されている。
【００４１】
準備中の応用に少なくとも部分的に依存して、より複雑な符号化スキームも採用されてもよい。例えば、2003年9月18日に出願され、2005年3月24に公開された「Data Compression」という題名のMonroによるPCT特許出願WO 2005/027049 A1で説明されたアプローチが使用される。この特許出願は、同じ題名および同じ発明者によって2006年3月16日に米国特許出願第10/572121号としても出願された。もちろん、特許請求される対象は、前記のPCTおよび米国特許出願で説明されたアプローチへ範囲を限定されない。これは、特許請求される対象の範囲内にある潜在的態様の単なる他の例である。しかしながら、この文脈において、前記のPCTおよび米国特許出願で説明された符号化アプローチは、本願明細書では「合併符号器」と呼ばれる。
【００４２】
上述のように、上記で説明された態様の多くは、データのストリングを効率的にランレングス・エンコードする。それにも拘わらず、このストリングは、例えば、更なるゴロム符号化によって、同様に更なる圧縮を受け入れてもよい。このようにして、Eの所与の値について、ゴロム符号のストリーム内のE値の生起は、これ自身ゴロム符号化されてもよい。
【００４３】
一度、符号器が、符号化されるべき最終のE値に来ると、E値の位置の大部分は、通信されることなく知られるようになる。前の例において、8つのゴロム符号の存在が知られるとすれば、記号ストリームは、
0 2 EOG 1 1 EOG 1 EOG
へ短くされてもよい。
しかしながら、ここで、可能なE値の値域が知られるか、前もって決定され得ることが仮定されている。
【００４４】
幾つかの状況において、Eの値域が未知であり、記号ストリームの長さも未知である場合の方法を有することが望まれるかもしれない。ここで、そのような状況を取り扱うため、特許請求される対象の範囲内にある2つの可能な態様を論議する。もっとも、再び、これらの態様は例であり、これら2つの態様だけでなく、他のアプローチが、特許請求される対象の範囲内に含まれる。
【００４５】
記号ストリームの長さが知られていると仮定する。そうであれば、そのような記号ストリームは、例えば、
4 0 2 EOG 1 1 EOG 1 EOG
のように、Max_Eの値によって接頭語を付けられてもよい。
このケースでは、例えば、E値は昇順または降順で取られてもよい。Min_E値はより頻繁に生じるので、降順を採用することによって、記号数が低減される潜在的利点を取得することが可能である。Eの潜在的値の双方、即ち、Min_EまたはMax_Eが合図されることも可能である。1つのアプローチは、記号ストリームの終端にMax_Eおよび/またはMin_Eを接尾語として付けてもよい。しかしながら、接尾語の価を待機する復号器の遅延は、幾つかの状況で欠点となるかもしれない。
【００４６】
同様に、Eの最終値を合図する代替として、例えば次のように、「ノー・モア・グループ（No More Groups）」を合図または表現する記号が導入されてもよい。
0 2 EOG 1 1 EOG 1 EOG NoMoreGroups
しかしながら、Eの値域を表示することは、典型的には、知られたスタート点を伴い、値は、知られた順序で前進を伴うことができる。しかしながら、そうでなければ、多分、Eのスタート値が合図されてもよい。
【００４７】
1つの態様において、系列内のゴロム符号の数は、プロセスが始まる少なくとも直後には、復号器によって決定され得ないかもしれない。連続したE値の位置が識別されるようになっても、復号器は依然として符号の正確な数を決定できないかもしれない。もっとも、Eグループの終わりにおいて、復号器は利用可能なデータから下界を決定できるかもしれない。復号器は、最後のE値が到達された後では残りのE値は同じである事実を使用するように構築されてもよいが、一般的に値の数は、追加のアプローチが採用されて値の数を同じように決定しなければ、依然として確かでない。
【００４８】
記号ストリームの長さを決定するアプローチは可能である。このアプローチがないと、最後の知られた記号に続くことができる未知数の最終記号が存在するかもしれない。ここで、Eの値域は知られていると仮定する。例えば、上記の例において、値が4であったEの2つの値がストリングの終端に現れた。
【００４９】
1つの潜在的なアプローチは、ストリングまたは系列の長さを接頭語として付け、E位置の合図が始まる前に、特定のストリング内のゴロム符号の総数が表示されることを含み得る。このケースにおいて、最終のE値が到達された後、上記の例で論証されたように、E位置が知られる。このようにして、そのような態様では、完全なメッセージが送られる。
8 0 2 EOG 1 1 EOG 1 EOG
【００５０】
同様に、他の潜在的方法は、記号ストリームへ接尾語として付けられた最終記号数をランレングスとして含むことである。
0 2 EOG 1 1 EOG 1 EOG 2
E値の値域および記号ストリームの長さを接頭語または接尾語として付けるそのような方法は、任意の組み合わせで使用されてもよい。そのようなアプローチをどのように組み合わせて、より良好な結果を達成するかは、少なくとも部分的に、記号ストリームの特定の統計に依存することができる。
【００５１】
前に説明されたような態様の有用性は、特定の実現の論議から、より容易に明らかになるかもしれない。もちろん、特許請求される対象は、この点に関して範囲を限定されない。この説明は単に例証を目的とする。前に表示されたように、2003年9月18日に出願されて2005年3月24日に公開され、同じ題名および同じ発明者によって2006年3月16日に米国特許出願第10/572121号としても出願されたMonroによる「Data Compression」と題する前記のPCT出願WO 2005/027049 A1は、ここでは合併符号化手法と呼ばれる手法を開示した。この手法は、データ圧縮で使用される。
【００５２】
前記の出願において、データは一連の原子として特徴づけられる。従って、原子は一緒に加えられて、結果のデータを提供または産出する。この特徴づけにおいて、原子は基底関数の位置、符号、振幅、および索引として説明される。振幅は固定数ビットの精度を有するように制約されてもよい。この制約は、本願明細書ではPL（精度限界）と呼ばれる。この文脈において、同じ題名および同じ発明者によって米国特許出願第10/333,480号として出願され、2004年7月1日にUS 2004/0126018として公開された特許出願を参照されたい。前記出願の双方は、2000年8月3日に英国で出願された出願への優先権を主張することが注意される。もちろん、特許請求される対象は、PLまたはPLQの採用に範囲を限定されない。むしろ、これらは単に例証を目的とした例として提供される。
【００５３】
特許出願のアプローチは、最初の有意ビット（FSB）の位置を他の残りのPL-1ビットと共に採用して振幅を記述した。PLの精度限界が与えられるとすれば、プロセスは、例えば、次のように採用されてもよい。
最大から最小へのFSBについて
2PL-1から0までのRA（振幅剰余）について
使用される各基底関数Kについて
属性（FSB、RA、K）を有する各原子の位置をランレングス符号化によって合図する
原子の符号S（1ビット）を送る
基底関数グループの終わり
（PLQ剰余）グループの終わり
上記の太字で示されるサブプロセスは、この特定の態様について、主または中心「合併」ループを表現する。しかしながら、このサブプロセスは、ランレングス符号化によってゴロム符号の系列上で動作するように、前に説明された態様の局面に少なくとも部分的に基づいて修正されてもよい。ここで、そのようなアプローチを適用すると、次が提供される。
最大から最小へのFSBについて
2PL-1から0へのRA（振幅剰余）について
使用される各基底関数Kについて
属性（FSB、RA、K）を有する各原子の位置をランレングス符号化するゴロム符号（E、RA）のリストを作る
生じる各Eについて
E値の位置をランレングス符号化する
対応するRE値（Eビット）を送信する
原子の対応する符号S（1ビット）を送信する
Eグループの終わり
基底関数グループの終わり
（PLQ剰余）グループの終わり
前述のように、これは符号器の中の符号器として考えられてもよい。ここでは、ゴロム符号の指数Eに少なくとも部分的に基づく内部符号器が、原子のグループについて採用される。上記の説明では、原子の振幅の剰余RAを、ランレングスのE値の剰余REから区別するため、添え字が使用される。
【００５４】
上記の実現例が示唆するように、E位置を更にランレングス符号化して、それ自身がゴロム符号になるようにすることができる。従って、符号化の追加層が、1つの追加レベル、または幾つかの追加レベルで入れ子にされてもよい。位置に関する統計は、そのような符号化を入れ子にすることが有利な深さに、少なくとも部分的に影響を与え得る。最も深いレベル、または他のレベルにおいて、E値を符号化する他の方法が使用されてもよい。特許請求される対象は、全てのそのような潜在的変種を包容することを意図される。
【００５５】
同様に、幾つかの態様において、結果のストリームまたはストリングは、特定の応用で望まれる場合、エンコードされているデータ記号に関する多様な追加または「副次的」情報を含んでもよい。例えば、データ記号がテキスト文字を表現するならば、そのような副次的情報は属性、例えば、色、フォント、字幅などを含んでもよい。そのような情報は、系列のスタートおよび/または終端で送信されるか、より便利な場合には、特定のグループの一部分として送信されてもよい。情報は、エンコードされた位置の値と一緒に送信されることもできる。同類のアプローチは、剰余値へも適用されてもよい。もっとも、そのようなアプローチの望ましさは、特定の応用に、少なくとも部分的に依存することができる。
【００５６】
特許請求される対象に従った態様は、全ての型のデータの符号化に適用されてもよい。それらの型には、非数字データ、例えば、符号化の適用前に任意の便宜的マッピングによって数字形態へ変換される記号データが含まれる。注意したように、態様は、ランレングス符号化の適用を介して良好な性能を発揮する。もっとも、もちろん、特許請求される対象は、必ずしもそのような限定に限定されないことが理解される。特許請求される対象の態様は、多数の異なる型のデータ符号化の任意の1つへ適用されることが、同様に意図される。従って、特許請求される対象は、この対象が適用されるデータの型の見地から限定されることを意図されない。
【００５７】
特定の態様が説明されたばかりであるが、特許請求される対象は、特定の態様または実現へ範囲を限定されないことが、もちろん理解される。例えば、1つの態様はハードウェアであってもよく、例えば、デバイスの上またはデバイスの組み合わせの上で動作するように実現され、他の態様はソフトウェアであってもよい。同様に、態様はファームウェアで実現されるか、例えば、ハードウェア、ソフトウェア、および/またはファームウェアの任意の組み合わせとして実現されてもよい。同様に、特許請求される対象は、この点に関して範囲を限定されないが、1つの態様は一つまたは複数の物品、例えば、記憶メディアを含んでもよい。この記憶メディア、例えば、一つまたは複数のCD-ROMおよび/またはディスクは、これらの上に命令を記憶されていてもよく、該命令は、システム、例えば、コンピュータ・システム、コンピューティング・プラットフォーム、または他のシステムによって実行されるとき、特許請求される対象に従った方法の態様、例えば、前に説明された態様の1つが実行される結果となってもよい。1つの潜在的な例として、コンピューティング・プラットフォームは、一つまたは複数の処理ユニットまたはプロセッサ、一つまたは複数の入力/出力デバイス、例えば、ディスプレイ、キーボードおよび/またはマウス、および/または一つまたは複数のメモリ、例えば、スタティックRAM、ダイナミックRAM、フラッシュ・メモリ、および/またはハードドライブを含んでもよい。
【００５８】
先立つ説明では、特許請求される対象の様々な局面が説明された。解明を目的として、具体的な数、システム、および/または構成が記述され、特許請求される対象の徹底的理解を提供した。しかしながら、特許請求される対象は具体的細部なしに実施されてもよいことを、この開示の恩典を有する当業者に明らかにしなければならない。他の場合、周知の特質は省略および/または単純化され、特許請求される対象を不明瞭にしないようにした。或る一定の特質が本明細書で図解および/または説明されたが、多くの修正、置換、変更、および/または同等物が、今では当業者の念頭に生じる。従って、添付された特許請求の範囲は、本願発明の真の趣旨に入る全ての修正および/または変更をカバーするように意図されることを理解すべきである。
【図１】
2009542093.tif 000005
【手続補正書】
【提出日】平成21年6月10日(2009.6.10)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
対象は、本明細書の結末部分で特に指摘され、明確に主張される。しかしながら、特許請求される対象は、後記の詳細な説明を参照することによって、添付の図面と一緒に読まれる場合、機構および動作方法の双方について、対象の目的、特質、および利点と共に最良に理解されるかもしれない。
[請求項101]
(a)符号が指数値Eiおよび剰余値Riを含み、iが整数数字である、符号系列を形成する工程;および
(b)符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成する工程
を含む、データ記号の系列を符号化する方法。
[請求項102]
iが、位置の値に関連づけられた整数数字を含む、請求項101記載の方法。
[請求項103]
一つまたは複数の位置の値が後に続くようにおよび/または先行するように、一つまたは複数の剰余値が、系列内で一緒にグループ化される、請求項102記載の方法。
[請求項104]
位置の値および剰余値をストリングとして送信または記憶する工程を更に含む、請求項102記載の方法。
[請求項105]
ストリングが、エンド・オブ・グループ記号によって終了される、請求項105記載の方法。
[請求項106]
ストリングの長さを表現する情報が、該ストリングへ接頭語として付けられる、請求項105記載の方法。
[請求項107]
指数値の数を表現する情報が、ストリングへ接頭語として付けられる、請求項105記載の方法。
[請求項108]
ストリング内の最終の位置の値の後に、ノー・モア・グループ記号が続く、請求項105記載の方法。
[請求項109]
剰余値が、ストリング内で、対応する位置の値に具体的に関連づけられる、請求項105記載の方法。
[請求項110]
符号系列がゴロム符号系列を含み、符号がゴロム符号を含む、請求項102記載の方法。
[請求項111]
ゴロム符号および位置の値は2進形式の表現を含む、請求項110記載の方法。
[請求項112]
一つまたは複数の位置の値がランレングス符号化される、請求項102記載の方法。
[請求項113]
位置の値が、更なる系列として処理され、更に符号化される、請求項102記載の方法。
[請求項114]
更なる系列がゴロム符号として符号化される、請求項113記載の方法。
[請求項115]
データ記号はオーディオまたはビデオ・ストリームを表現する、請求項101記載の方法。
[請求項116]
符号内で生じるEの選択された値について、Eの値を表現する該符号内の位置の値がiを含む、請求項101記載の方法。
[請求項117]
(i)データ記号について、
(a)bが固定モジュロ値である場合、bEiがViを超過しない指数Eiの最大整数値を決定する工程;および
(b)剰余Ri = Vi - bEiを計算する工程;
(ii)該指数Eiを符号系列として取り、生じるEiの値について、Eiの該値を表現する符号系列内の位置の値を生成する工程;ならびに
(iii)該剰余RiをEiの該値に関連づける工程
を含む、データ記号の系列を数字Viによって数字形態で表現される記号に符号化する方法。
[請求項118]
符号内の位置の値が、iの値に関連づけられた値を含む、請求項117記載の方法。
[請求項119]
一つまたは複数の位置の値がランレングス符号化される、請求項118記載の方法。
[請求項120]
データ記号がオーディオまたはビデオ・ストリームを表現する、請求項117記載の方法。
[請求項121]
命令を実行すると、
(a)iが整数数字であるとしたとき、符号が指数値Eiおよび剰余値Riを含む符号系列を形成する工程、および
(b)符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成する工程
のようにデータ記号の系列を符号化する方法の遂行が更にもたらされる、
該命令を記憶した記憶メディアを含む物品。
[請求項122]
命令を実行すると、位置の値に関連づけられた整数数字を含むiが更に生じる、請求項121記載の物品。
[請求項123]
命令を実行すると、一つまたは複数の位置の値が後に続くようにおよび/または先行するように一つまたは複数の剰余値が系列内で一緒にグループ化される結果が更に生じる、請求項122記載の物品。
[請求項124]
命令を実行すると、位置の値および剰余値をストリングとして送信または記憶する結果が更に生じる、請求項122記載の物品。
[請求項125]
命令を実行すると、符号内で生じるEの選択された値について、Eの値を表現する該符号内の位置の値がiを含む結果を更に生じる、請求項121記載の物品。
[請求項126]
iは整数数字であるとしたとき、指数値Eiおよび剰余値Riを含む符号の系列を形成する手段と、符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成する手段とを含む装置。
[請求項127]
一つまたは複数の位置の値が後に続くようにおよび/または先行するように、系列内で一つまたは複数の剰余値を一緒にグループ化する手段を更に含む、請求項126記載の装置。
[請求項128]
命令を実行すると、位置の値および剰余値をストリングとして送信または記憶する結果が更に生じる、請求項126記載の装置。
[請求項129]
コンピューティング・プラットフォームが、符号が指数値Eiおよび剰余値Riを含み、iが整数数字である、符号系列を形成するように適用され、かつ符号内で生じるEiの値について、Eiの該値を表現する該符号系列内の位置の値を生成するように適応される、コンピューティング・プラットフォームを含む装置。
[請求項130]
コンピューティング・プラットフォームが、整数数字iを位置の値に関連づけるように更に適応される、請求項129記載の装置。
[請求項131]
一つまたは複数の位置の値が後に続くようにおよび/または先行するように、プラットフォームが、系列の中で一つまたは複数の剰余値を一緒にグループにするように更に適応される、請求項130記載の装置。
[請求項132]
コンピューティング・プラットフォームは、位置の値および剰余値をストリングとして送信または記憶するように更に適応される、請求項130記載の装置。
[請求項133]
コンピューティング・プラットフォームは、符号内で生じるEの選択された値について、Eの該値を表現する該符号内の位置の値をiとして割り当てるように更に適応される、請求項121記載の装置。
[請求項134]
命令を実行すると、
(i)データ記号について、
(a)bが固定モジュロ値であるとしたとき、bEiがViを超過しない指数Eiの最大整数値を決定する工程、および
(b)剰余Ri = Vi - bEiを計算する工程;
(iv)該指数Eiを符号系列とし、かつ生じるEiの値について、Eiの該値を表現する符号系列内の位置の値を生成する工程、および
(v)該剰余RiをEiの該値に関連づける工程
のように、データ記号の系列を符号化し、記号が数字Viによって数字形態で表現される方法の遂行をもたらす、
命令を記憶された記憶メディアを含む物品。
[請求項135]
命令を実行すると、符号内の位置の値が、iの値に関連づけられた値を含む結果が更に生じる、請求項134記載の物品。
[請求項136]
命令を実行すると、一つまたは複数の位置の値がランレングス符号化される結果が更に生じる、請求項135記載の物品。
[請求項137]
命令を実行すると、データ記号がオーディオまたはビデオ・ストリームを表現する結果が更に生じる、請求項135記載の物品。
[請求項138]
bが固定モジュロ値であるとしたとき、データ記号について、bEiがViを超過しない指数Eiの最大整数値を決定して剰余Ri = Vi - bEiを計算し、
該指数Eiを符号系列として取り、生じるEiの値について、Eiの該値を表現する符号系列内の位置の値を生成し、かつ
該剰余RiをEiの該値に関連づける
ように適応されるコンピューティング・プラットフォームを含む装置。
[請求項139]
コンピューティング・プラットフォームが、符号内の位置の値をiの値に関連づけられた値に割り当てるように適応される、請求項138に記載の装置。
[請求項140]
コンピューティング・プラットフォームが、一つまたは複数の位置の値をランレングス符号化するように適応される、請求項135に記載の装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
【図１】データ符号化手法の1つの態様を図解する略図である。
【図２】システム200の図である。システム200はデータセット204に連結したアナライザー202を備える。アナライザー202は、データセット204からデータ206を受け、そこから位置符号208を生じる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
8つの（または、どれほど多くが存在しても）ゴロム符号からなるこの系列を単一のストリングとして処置することによって、追加の圧縮が達成されてもよい。この特定の例において、これはEiの異なる値について達成されてもよい。ここで、iは、Eiが生じる位置iを経由した整数数字を表現する。圧縮のためには、値Eiの系列が特定の関心をもつことができる。なぜなら、Riの値は典型的には有意の更なる圧縮を受け入れず、従って、単純な、即ち、圧縮されない値として送信されうるからである。同様に、符号Siが存在するならば、それらの符号は、符号ストリームの中へ便利に組み入れられうる。もちろん、全てのデータが同じ符号であれば、符号Siは省略されてもよい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
剰余Ri、および適切な場合、符号Siは、上記で言及されたように、任意の便利な場所、例えば、位置符号の後またはEOG記号の後でインタリーブされて通信されてもよい。Ei値が、例えば、復号器によって再構築されるのであれば、復号器は、追加のデータを受け取ることなく、関連づけられたRiの長さを決定してもよく、追加のデータを受け取ることなく、後に続くRiビットの期待数を決定してもよい。前記期待数は、上記で解明されたように、Ei >= 1およびMi >= 2についてEiビットである。ここで、Mi = 2Ei + Riである。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３９
【補正方法】変更
【補正の内容】
【００３９】
たった今説明された特定の態様は、従来のデータ圧縮アプローチに勝る効率を提供することが注意される。しかしながら、下記で説明されるように、追加の効率も達成されてもよく、そのような態様も、特許請求される対象の範囲内に含まれることが意図される。例えば、位置1〜8は一度生じる。従って、典型的には、記号当たり3ビットが採用されて、符号化方法によってこれを通信してもよい。しかしながら、その代わりに、圧縮を改善する任意の他のアプローチが、例えば、ランレングス・エンコーディングのように位置の間のギャップを表示する。この場合、その後に4が続く1を送ってE値1の位置を表示する代わりに、0を送ってEの最初の生起の前に位置がスキップされなかったことを表示し、2を追随させて2つの位置がスキップされ、位置1から位置4へ達したことを表示してもよい。以下同様である。
0 2 EOG 2 2 EOG 4 EOG 1 4 0 EOG
これは、記号が少なくなること、ここでは0、1、2、4、およびEOGによって、より効率的である。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４０
【補正方法】変更
【補正の内容】
【００４０】
しかしながら、効率は、特許請求される対象の範囲内の他の態様で更に改善されてもよい。送信が進行するにつれて、典型的には、ランレングス符号器の利用可能な空間は小さくなる。というのは、ますます多くの値が知られてくるからである。したがって、例えば、最初のEグループが通信されると、E=1の位置が知られる。加えて、これらの位置は、処理中に後のE値の可能な位置としては無視されてもよい。従って、ランレング符号は処理中にこれらの値を「無視」してもよく、次のようにスキップされるべき未知の位置を合図してもよい。
0 2 EOG 1 1 EOG 1 EOG 0 0 0 EOG
ここで、記号の数は0、1、2、およびEOGへ効果的に更に低減されている。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００５０
【補正方法】変更
【補正の内容】
【００５０】
同様に、他の潜在的方法は、記号ストリームへ接尾語として付けられた最終記号数をランレングスとして含むことである。
0 2 EOG 1 1 EOG 1 EOG 3
E値の値域および記号ストリームの長さを接頭語または接尾語として付けるそのような方法は、任意の組み合わせで使用されてもよい。そのようなアプローチをどのように組み合わせて、より良好な結果を達成するかは、少なくとも部分的に、記号ストリームの特定の統計に依存することができる。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
前記の出願において、データは一連の原子として特徴づけられる。従って、原子は一緒に加えられて、結果のデータを提供または産出する。この特徴づけにおいて、原子は基底関数の位置、符号、振幅、および索引として説明される。振幅は固定数ビットの精度を有するように制約されてもよい。この制約は、本願明細書ではPL（精度限界）と呼ばれる。同じ題名および同じ発明者によって米国特許出願第10/333,480号として出願され、2004年7月1日にUS 2004/0126018として公開された特許出願を参照されたい。前記出願の双方は、2000年8月3日に英国で出願された出願への優先権を主張することが注意される。もちろん、特許請求される対象は、PLまたはPLQの採用に範囲を限定されない。むしろ、これらは単に例証を目的とした例として提供される。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
特定の態様が説明されたばかりであるが、特許請求される対象は、特定の態様または実現へ範囲を限定されないことが、もちろん理解される。例えば、1つの態様はハードウェアであってもよく、例えば、デバイスの上またはデバイスの組み合わせの上で動作するように実現され、他の態様はソフトウェアであってもよい。同様に、態様はファームウェアで実現されるか、例えば、ハードウェア、ソフトウェア、および/またはファームウェアの任意の組み合わせとして実現されてもよい。同様に、特許請求される対象は、この点に関して範囲を限定されないが、1つの態様は一つまたは複数の物品、例えば、記憶メディアを含んでもよい。この記憶メディア、例えば、一つまたは複数のCD-ROMおよび/またはディスクは、これらの上に命令を記憶されていてもよく、該命令は、システム、例えば、コンピュータ・システム、コンピューティング・プラットフォーム、または他のシステムによって実行されるとき、特許請求される対象に従った方法の態様、例えば、前に説明された態様の1つが実行される結果となってもよい。1つの潜在的な例として、コンピューティング・プラットフォームは、一つまたは複数の処理ユニットまたはプロセッサ、一つまたは複数の入力/出力デバイス、例えば、ディスプレイ、キーボードおよび/またはマウス、および/または一つまたは複数のメモリ、例えば、スタティックRAM、ダイナミックRAM、フラッシュ・メモリ、および/またはハードドライブを含んでもよい。
図２は、システム200の図である。システム200はデータセット204に連結したアナライザー202を備える。アナライザー202は、データセット204からデータ206を受け、そこから位置符号208を生じる。上述のとおり、アナライザー202はハードウェア、ソフトウェア、および／またはファームウェアの組み合わせであってもよい。
【手続補正１０】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
符号系列内の個々の符号がEiを含むようにデータをゴロム符号化するための処理デバイスを使用して符号系列を形成する工程であって、ここでiは1よりも大きいか等しい整数であり、符号系列内のそれぞれの1つの符号の位置を表現する、前記工程;および
i個の位置の同類のそれぞれの値の符号系列における位置が、位置符号の中で相互に隣接し、かつスペーサー符号によって分離される位置符号を、処理デバイスを使用して形成する工程
を含む方法。
【請求項２】
エンド・オブ・グループ（EOG）記号をスペーサー符号として使用する工程を更に含む、請求項1記載の方法。
【請求項３】
AおよびBが0よりも大きいか等しい整数であるように、E1＝A、E2＝Bを符号系列として使用する工程;および
EOGがスペーサー符号であるように、1EOG2EOGを位置符号として使用する工程
を更に含む、請求項1記載の方法。
【請求項４】
位置符号が12EOGを含むように、A＝Bを使用する工程を更に含む、請求項3記載の方法。
【請求項５】
符号系列内の各符号について剰余Riを使用する工程を更に含む、請求項1記載の方法。
【請求項６】
位置符号の中で剰余Riをインタリーブする工程を更に含む、請求項5記載の方法。
【請求項７】
Eiに対応するスペーサー符号の後で剰余Riをインタリーブする工程を更に含む、請求項6記載の方法。
【請求項８】
位置符号を形成する工程が、既に符号化されたi個の位置のそれぞれの値を省略する工程を更に含む、請求項6記載の方法。
【請求項９】
位置符号を形成する工程が、i個の位置の同類のそれぞれの値の符号系列における位置の間の差が、位置符号の中で相互に隣接し、スペーサー符号によって分離される位置符号を形成する工程を含む、請求項1記載の方法。
【請求項１０】
Eiの最大値を位置符号へ接頭語として付ける工程、Eiの最小値を位置符号へ接頭語として付ける工程、Eiの最大値を位置符号へ接尾語として付ける工程、またはEiの最小値を位置符号へ接尾語として付ける工程を更に含む、請求項1記載の方法。
【請求項１１】
Eiの最大値および最小値の双方を位置符号と組み合わせる工程を更に含む、請求項1記載の方法。
【請求項１２】
ノー・モア・グループ信号を使用して、位置符号の終端を表示する工程を更に含む、請求項1記載の方法。
【請求項１３】
符号系列の長さを位置符号へ接頭語として付ける工程を更に含む、請求項1記載の方法。
【請求項１４】
データについて非数字データ記号を使用する工程を更に含み、データのゴロム符号化を使用する前に、
マッピングによって非数字データ記号を数字データへ変換する工程を更に含む、請求項1記載の方法。
【請求項１５】
非数字データ記号について記号データを使用する工程を更に含む、請求項18記載の方法。
【請求項１６】
データは数字データ記号Viを含み、ゴロム符号化を使用する工程は、
bが固定モジュロ値であるとき、bEiがViを超過しない指数Eiの最大整数値を決定する工程;および
剰余Ri＝Vi-bEiを計算する工程
を含む、請求項1記載の方法。
【請求項１７】
符号系列内の個々の符号がEiを含むように、データのゴロム符号化を使用して符号系列を形成する手段であって、ここでiは、1よりも大きいか等しい整数であり、符号系列内のそれぞれの1つの符号の位置を表現する、前記手段と、
i個の位置の同類のそれぞれの値の符号系列における位置が、位置符号の中で相互に隣接し、スペーサー符号によって分離される位置符号を形成する手段と
を含むシステム。
【請求項１８】
コンピュータ実行可能命令を記憶されたコンピュータ読み取り可能メディアであって、前記コンピュータ実行可能命令は、コンピューティング・デバイスによって実行されるならば、
符号系列内の各符号がEiを含むように、データのゴロム符号化を使用して符号系列を形成する工程であって、ここでiは、1よりも大きいか等しい整数であり、符号系列内のそれぞれの1つの符号の位置を表現する、前記工程;および
i個の位置の同類のそれぞれの値の符号系列における位置が、位置符号の中で相互に隣接し、スペーサー符号によって分離される位置符号を形成する工程
を含む方法をコンピューティング・デバイスが遂行することを引き起こす、前記コンピュータ読み取り可能メディア。
【手続補正１１】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2009542093.tif 000006
【手続補正１２】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2009542093.tif 000007
【国際調査報告】
2009542093.tif 000008