(57)【要約】データ符号化の方法、システム、および/またはデバイスの態様を開示する。2009540670.tif 000006
2009540670.tif 000002
【特許請求の範囲】
【請求項１】
指数値Eおよび剰余値Rによってデータ記号を符号化する工程を含む方法であって、指数値へ適用される符号化が可変長符号化を含む、方法。
【請求項２】
指数値へ適用される可変長符号化がHuffman符号化を含む、請求項1記載の方法。
【請求項３】
剰余値へ適用される符号化が固定長符号化を含む、請求項1記載の方法。
【請求項４】
固定長符号化が2進符号化を含む、請求項3記載の方法。
【請求項５】
データ記号が2進表現を含む、請求項1記載の方法。
【請求項６】
可変長符号化が適応型であり、かつ測定された生起頻度に従って符号を選択する、請求項1記載の方法。
【請求項７】
データ記号がランレングス・エンコードされる、請求項1記載の方法。
【請求項８】
追加のデータ記号を符号化して記号の系列を形成する工程をさらに含む方法であって、該記号が、期待された生起確率によって記号を順位づける記号アルファベットの中に含まれる、請求項1記載の方法。
【請求項９】
記号の系列がオーディオおよび/またはビデオ・ストリームを表現する、請求項8記載の方法。
【請求項１０】
データ記号の符号化が生Golomb符号化を含む、請求項1記載の方法。
【請求項１１】
実行される場合、結果として指数値Eおよび剰余値Rによってデータ記号を符号化するような方法を遂行する命令が記憶された記憶メディアを含む物品であって、指数値へ適用される符号化が可変長符号化を含む、物品。
【請求項１２】
命令が、実行される場合、結果としてHuffman符号化を含む指数値へ適用される可変長符号化をさらにもたらす、請求項11記載の物品。
【請求項１３】
命令が、実行される場合、結果として固定長符号化を含む剰余値へ適用される符号化をさらにもたらす、請求項11記載の物品。
【請求項１４】
命令が、実行される場合、結果として2進符号化を含む固定長符号化をさらにもたらす、請求項13記載の物品。
【請求項１５】
命令が、実行される場合、結果として2進表現を含むデータ記号をさらにもたらす、請求項11記載の物品。
【請求項１６】
命令が、実行される場合、結果として適応型の可変長符号化をさらにもたらし、測定された生起頻度に従った符号をさらにもたらす、請求項11記載の物品。
【請求項１７】
命令が、実行される場合、結果としてランレングス・エンコードされるデータ記号をさらにもたらす、請求項11記載の物品。
【請求項１８】
命令が、実行される場合、結果として追加のデータ記号を符号化して記号の系列を形成することをさらにもたらし、該記号が、期待された生起確率によって記号を順位づける記号アルファベットの中に含まれる、請求項11記載の物品。
【請求項１９】
命令が、実行される場合、結果として生Golomb符号化を含むデータ記号の符号化をさらにもたらす、請求項11記載の物品。
【請求項２０】
指数値Eおよび剰余値Rによってデータ記号を符号化するように適応されたコンピューティング・プラットフォームを含む装置であって、指数値へ適用されるべき符号が可変長符号を含む、装置。
【請求項２１】
指数値へ適用されるべき可変長符号がHuffman符号を含む、請求項20記載の装置。
【請求項２２】
剰余値へ適用されるべき符号が固定長符号を含む、請求項20記載の装置。
【請求項２３】
固定長符号が2進符号化を含む、請求項22記載の装置。
【請求項２４】
コンピューティング・プラットフォームが、2進表現を含むデータ記号を符号化するように適応される、請求項20記載の装置。
【請求項２５】
適用されるべき可変長符号が適応型であり、適用されるべき符号が、実質的に、測定された生起頻度に従って選択される、請求項20記載の装置。
【請求項２６】
コンピューティング・プラットフォームが、ランレングス・エンコードされるデータ記号を符号化するように適応される、請求項20記載の装置。
【請求項２７】
コンピューティング・プラットフォームが、追加のデータ記号を符号化して記号の系列を形成するようにさらに適応され、該記号が、期待される生起確率によって記号が順位づけられる記号アルファベットの中に含まれる、請求項20記載の装置。
【請求項２８】
コンピューティング・プラットフォームが、データ記号を生Golomb符号として符号化するようにさらに適応される、請求項20記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
分野
本特許出願は、データ符号化、例えば、Golomb符号化などに関する。
【背景技術】
【０００２】
背景
周知のように、記憶または送信のための効率的データ符号化は、新しいアプローチが探索される領域であり続けている。例えば、データが、例えば圧縮によって、より効率的に符号化されるならば、符号化されるべきデータを記憶するメモリ量は低減されるかもしれない。同様に、通信システムにおいて、データが、例えば所与の帯域幅の通信チャネルについて、効率的に符号化されるならば、潜在的により多くの情報が所与の時間単位で送信されるかもしれない。これらの目標および多くの他の目標は、データの効率的符号化方法の目的であってもよい。
【０００３】
主題は、本明細書の終結部分で具体的に指摘され、明確に特許請求される。しかしながら、特許請求の対象は、組織および動作方法の双方、並びに該主題の目的、特徴、および利点に関して、次の詳細な説明を参照することによって、添付の図面と一緒に読まれる場合、最良に理解されるだろう。
【発明の概要】
【０００４】
本発明は、指数値Eおよび剰余値Rによってデータ記号を符号化する工程を含む方法であって、指数値へ適用される符号化が可変長符号化を含む方法、およびその装置を提供する。
【図面の簡単な説明】
【０００５】
【図１】データ符号化手法の1つの態様を図解する略図である。
【発明を実施するための形態】
【０００６】
詳細な説明
次の詳細な説明で、多くの具体的細部を記載し、特許請求の対象の徹底的理解を提供する。しかしながら、特許請求の対象は、これらの具体的細部なしに実施されてもよいことが、当業者によって理解される。他の場合には、周知の方法、手続き、コンポーネントおよび/または回路は、特許請求の対象を不明瞭にすることがないように、詳細には説明されていない。
【０００７】
下記の詳細な説明の幾つかの部分は、コンピューティング・システムの中、例えば、コンピュータおよび/またはコンピューティング・システム・メモリの中に記憶されたデータ・ビットおよび/または2進ディジタル信号への動作のアルゴリズムおよび/または記号表現の見地から提示される。これらのアルゴリズムの説明および/または表現は、データ処理技術分野の当業者によって使用される手法であり、当業者の成果の実体を他の当業者へ伝達する。アルゴリズムは、本明細書において、および一般的に、所望の結果へつながる首尾一貫した動作の系列および/または類似の処理であると考えられる。動作および/または処理は、物理量の物理的操作を伴ってもよい。典型的には、必ずというわけではないが、これらの量は、記憶、転送、結合、比較、および/または操作され得る電気および/または磁気信号の形態を取ってもよい。時には、主として共通使用を理由として、これらの信号をビット、データ、値、要素、記号、文字、項、番号、数字、および/またはその他として参照することが便利であることが証明されている。しかしながら、これらおよび類似の用語の全ては、適当な物理量に関連づけられるべきであり、単に便宜的なラベルであることを理解すべきである。そうでないことを特に断らない限り、下記の検討から明らかであるように、本明細書の全体を通して、「処理」、「コンピューティング」、「計算」、「判定」、および/またはその他のような用語を利用する検討は、コンピューティング・プラットフォームのプロセッサ、メモリ、レジスタ、および/または他の情報記憶、送信、および/または表示デバイスの中で物理電子および/または磁気量および/または他の物理量として表現されたデータを操作および/または変換するコンピューティング・プラットフォーム、例えば、コンピュータまたは類似の電子コンピューティング・デバイスの行動および/または処理を指すことが了解される。
【０００８】
前に暗示したように、特許請求の対象の態様の、1つの可能な排他的でない応用は、低ビットレートのオーディオおよび/またはビデオ符号化の分野であるかもしれない。この特定の分野において、例えば、データを比較的効率的に圧縮することが典型的に望まれる。この分野および類似の分野において、前に示唆されたように、通信チャネル、例えば、送信され得るビットの数、またはビット送信レートの制限に供されるチャネルを横切って、情報を送信することも望まれるかもしれない。従って、比較的効率的な符号化は、例えば、より多くの情報が単位時間当たりに送信される結果となり得る。同じく前に示唆された他の応用は、例えば、ファイルに記憶するための電子デバイス上のデータ圧縮であってよい。これは、例えば、具体的データを記憶するためのメモリ量を低減するか、または他の例として、電子メールの添付物のサイズを低減することによってデータ送信を容易にする可能性がある。もちろん、特許請求の対象は、これらの単純な例に限定されない。これらは、単に例証を目的として提供される。
【０００９】
Golomb符号化は周知であり、Golomb, SW:‘Run-length encodings', IEEE Trans. Inf. Theory, 1966, 7, (12), pp. 399-401で説明されている。Golomb符号は、データ符号化の単なる1つの例である。従って、後に説明される例の多くはGolomb符号化の見地から提示されるが、特許請求の対象は、単にGolomb符号（GC）へ範囲を限定されるものではないことが意図されることを明らかにしておかなければならない。データ符号化への他のアプローチを採用して、満足な結果を提供する場合もある。それでも、Golomb符号化を1つの例として続けると、GCは、しばしば、ランレングス符号化に使用されるが、原理的にはGCは汎用符号であり、任意の記号または記号系列を整数数字または整数数字系列としてエンコードするために使用されてもよい。1つの可能な態様において、一意の整数数字が記号へ割り当てられてもよく、次に記号は、Golomb符号化によって、例えば、対応する数字へ符号化されてもよい。GCは、数字の値域を知る必要がないか、前もって制約する必要がないという利点を有する。
【００１０】
1つの具体的な例において、数字I、モジュロKのGolomb符号は、次のように（S、E、R）によって定義されてもよい（ここで、Kはこの例では「基数」である）。
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として、例えば、Golomb符号が、指数Eおよび可変長Eビットの剰余Rを有する可変長2進浮動小数点表現形態を提供するようにしてもよい。このケースは、例えば、図1で図解するが、もちろん、特許請求の対象は、この点に関して範囲を限定されない。
【００１３】
下記でより詳細に説明するように、1つの態様において、Golomb符号化を含むデータ記号符号化方法が採用されてもよいが、前に解明したように、特許請求の対象は範囲をGolomb符号化へ限定されない。そのような態様において、記号は指数値Eおよび剰余値RによってGolomb符号化されてもよい。指数値は、再び下記でより詳細に説明されるように、実質的に可変長符号に従って符号化される。
【００１４】
この特定の態様において、例えば、可変長符号（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符号器などが、符号、例えばGolomb符号などの指数をエンコードしてもよい。しかしながら、VLCは、例えば特定の態様に依存して、適応型であるか固定型であってもよい。
【００１８】
特許請求の対象は、この点に関して範囲を限定されないが、本明細書において説明される符号化手続きの態様は、現実の応用で時にはHuffman符号化よりも性能が優れていることに注意すべきである。同様に、特許請求の対象は、この点に関して範囲を限定されないが、態様は、ランレングス符号化へ便宜的に適用され、および/または厄介な確率分布と一緒に使用されてもよいが、これらは単なる例であり、特許請求の対象は、この点に関して範囲を限定されない。
【００１９】
データ符号化方法の態様に加えて、例示的な態様は、そのような方法を組み込んでいるコンピュータ・プログラム、および/または符号器、例えば、ハードウェア、ファームウェア、ソフトウェア、またはこれらの組み合わせで実現された符号器を含んでよい。態様は、そのような方法を体現するビデオおよび/またはオーディオ・コーデック、ビデオおよび/またはオーディオ圧縮システムも含んでよい。このシステムによって、データはそのような方法に従ってエンコードされ、そのようなデータは次に通信チャネルを横切って送信され、遠隔端でデコーダによって再構築されてもよい。あるいは、符号化されたデータは、送信されるのではなく記憶されてもよい。これらおよび多くの他の態様は、特許請求の対象の範囲の中に含まれる。
【００２０】
例えば、図1は、サインおよび大きさの表現を使用するGolomb符号化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の値の送信は、幾つかの状況では困難である場合がある。Golomb符号器を実現する通常の方法は、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)ビットを採用する。数字の値域を必ずしも知る必要がないことは、Golomb符号の特徴であるから、Max_Eのサイズを必ずしも知る必要はないことになる。しかしながら、一度、特定の数字についてEが知られると、Rの値はEビットを採用することが公知である。
【００２４】
例示的な態様としてのGolomb符号化は、少なくとも部分的には良好に働く。なぜなら、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のベキであれば、これは良好な結果を生成することができるが、特許請求の対象は、もちろん、この点に関して範囲を限定されない。
【００２５】
生符号、例えば生Golomb符号を採用することは、データを符号化する合理的手法を提供することを示すため、比較の例が役立つかもしれない。数字の系列を送信したいものと想定し、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符号器が時にはそのように悪い性能であるとは、一般的には了解されない。
【００２７】
他方では、生Golomb符号は、同じ数字系列を送信するとき、より良好に働く。このケースにおけるEの値域は、0〜3である。2ビットを用いて、これを通信してもよい。
【００２８】
8つの可能な数字に採用されるビットの数を列挙することができる。
2009540670.tif 000003
この符号は平均で26/8ビットを使用し、ここでは最適よりも約8％のオーバーである。8が最大数字であることを前もって知らないと言うならば、8が起こる場合の4ビット剰余を許してもよい。その時、平均は30/8個のビット、または最適よりも25％のオーバーである。それでも、この例が実証するように、生Golomb符号は、ここではHuffman符号よりも性能がよい。
【００２９】
生Golomb符号における或る非効率性は、Eの異なる値が同じ頻度で起こらない場合でも、2ビットを採用して値を符号化するやり方のEの符号化に帰してもよい。これに代わって、この特定の態様では、VLCを使用してEの値を符号化することが提案される。可変長符号器（VLC）は、典型的には、記号のアルファベットを使用し、その場合、記号の生起確率は数字順に順位づけられる。この型の1つの周知の符号器は、上記で言及されたHuffman符号器である。Huffmanとは別の他のVLCが、同様に使用されてもよい。
【００３０】
前の例を続けて、Eの最も普通の値は2である。したがって、最短符号、即ち、2進の1を使用する。同じく、E = 1の2進符号は01であり、E = 0およびE = 3の2進符号は001または000であり、どちらでもよい。Eの符号化において、2進値0および1の役割を切り替えることも可能である。これらは、Eについて値1および8を符号化するための000および001の選択が任意であるHuffman符号として認識されてもよい。
【００３１】
効率は、現在以下である。
2009540670.tif 000004
【００３２】
「混成Golomb符号器」（HGC）とは、Eの値について符号化するためHuffman VLCが使用されるGolomb符号であると定義される。上記の例は、このケースでHGCが最適であることを示す。この符号を形成するとき、0または8についてR値は採用されない事実が利用された。Eが0であれば、もちろん剰余は存在せず、Eが3であれば、送信されている数字は8であり、またしても剰余は存在しない。E = 0およびE = 3についてのHuffman符号が、正しく同値であると見なされたことも仮定された。
【００３３】
代わりに、適応型であってもよい実用的Huffman符号器と比較するため、0または8についてのE値の一方または他方が、4ビット符号を使用することを認識する。最大値が8であることも前もって知られず、1つの記号について4ビット符号を使用する他の理由である。これらのケースの双方において、平均で25/8ビットが使用される。これは最適よりも4％多いだけである。
【００３４】
Huffman符号器が最適であると知られるケース、例えば、該8つの記号の確率が1/2、1/4、...、1/128、1/128である場合と比較してもよい。最後の2つの確率は同じである。これは確率が1.0の合計になるようにするためである。そのような源からの記号ストリームの理論的エントロピは、記号当たり1.9844ビットであり、Huffman符号器は平均でこれを正確に達成する。
【００３５】
混成Golomb符号器（HGC）のこの態様について、確率を作表および適用して、平均性能を得る。E値の順位は適正に同定されることを仮定していることに留意されたい。
2009540670.tif 000005
使用されるビットの平均数は2.0078である。これは、Huffman符号が最適であっても、Huffman符号の1.9844ビットよりも1％悪くオーバーするだけである。
【００３６】
確率の値域にわたって、実験は、Huffman VLCを使用してEの値を符号化する混成Golomb符号器は、Huffman符号器よりも一貫して性能が優れていることを示す。例外は、Huffman符号器の理想的動作条件に比較的近い状況のときである。
【００３７】
上記で解明されたように、従来のGolomb符号器を実現する1つの通常の方法は、E自身の値を送信するのではなく、代わりにEの値への変化を送信することである。これは、連続する値が相関づけられる或る非常に狭い条件の下では好ましいが、理論および実験結果の双方は、混成Golomb符号器が、一般的に、そのような従来のGolomb符号器よりも性能で勝ることを示す。例えば、ランレングス符号化において、連続するE値は、しばしば、相関づけられず、例えば、大きなランは短いランによって追随され得る。したがって、従来のGolomb符号器はE値を「前後に」追跡することができるが、HGCは、大体の場合、Eのために、より良好な符号を選択することができる。
【００３８】
もちろん、Eの値をエンコードするとき、Huffmanプロセスの使用は必須でないことが理解される。任意の可変長符号、例えば固定（既定）符号または適応型符号が代わりに使用され得る。適応型符号では、送信されるべきデータの中で発見される数字または記号の測定確率に従って値が判定される。もちろん、これらは単なる例であり、特許請求の対象は、これらの例へ範囲を限定されない。
【００３９】
特許請求の対象に従った態様は、全ての型のデータの符号化に応用されてもよい。そのようなデータには、非数値データ、例えば、符号化を適用される前に任意の便利なマッピングによって数値形態へ変換される記号データが含まれる。注記するように、態様はランレングス符号化について良好な性能を発揮するが、もちろん、特許請求の対象は、この応用に限定されないことが理解される。特許請求の対象の態様は、多数の異なる型のデータ符号化の任意の1つに応用されることが意図される。従って、特許請求の対象は、それが応用され得るデータの型に関して限定されることを意図されない。
【００４０】
特定の態様だけが説明されたが、特許請求の対象は特定の態様または実現へ範囲を限定されるものではないことが、もちろん理解される。例えば、1つの態様はハードウェアであって、例えば、1つのデバイスまたは複数のデバイスの組み合わせで動作するように実現されてもよく、他の態様はソフトウェアであってもよい。同様に、態様はファームウェアで実現されるか、例えば、ハードウェア、ソフトウェア、および/またはファームウェアの任意の組み合わせで実現されてもよい。同様に、特許請求の対象は、この点に関して範囲を限定されないが、1つの態様は一つまたは複数の物品、例えば、記憶メディアを含んでよい。この記憶メディア、例えば、一つまたは複数のCD-ROMおよび/またはディスクは、それらの上に命令を記憶されていてもよい。これらの命令は、システム、例えば、コンピュータ・システム、コンピューティング・プラットフォーム、または他のシステムによって実行されたとき、例えば、特許請求の対象の実行に従った方法の態様、例えば、前に説明された態様の1つを結果としてもよい。1つの可能な例として、コンピューティング・プラットフォームは、一つまたは複数の処理ユニットまたはプロセッサ、一つまたは複数の入力/出力デバイス、例えば、ディスプレイ、キーボード、および/もしくはマウス、ならびに/または一つまたは複数のメモリ、例えば、静的ランダム・アクセス・メモリ、動的ランダム・アクセス・メモリ、フラッシュ・メモリ、および/もしくはハードドライブを含んでよい。
【００４１】
先行する説明において、特許請求の対象の様々な局面が説明された。解明を目的として、具体的な数、システムおよび/または構成を記載して、特許請求の対象の徹底的な理解を提供した。しかしながら、特許請求の対象は具体的細部なしに実施されてもよいことが、この開示の恩典を有する当業者へ明らかにされなければならない。他の場合には、特許請求の対象を不明瞭にしないように、周知の特徴は省略および/または簡略化された。本明細書において幾つかの特徴が例証および/または説明されたので、今では多くの改変、置換、変更および/または同等物が当業者の念頭に浮かぶ。従って、理解すべきことは、付加された特許請求の範囲が、全てのそのような改変および/または変更を、特許請求の対象の真の精神の中に入るものとしてカバーすることを意図されることである。
【図１】
2009540670.tif 000007
【手続補正書】
【提出日】平成21年3月13日(2009.3.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
指数値および剰余値を含む符号を用いてデータ記号を符号化する工程と、
固定長2進符号を用いて剰余値を符号化する工程と、
指数値の生起頻度に基づく可変長符号を用いて指数値を符号化する工程と
を含む、方法。
【請求項２】
指数値および剰余値を含む符号を用いてデータ記号を符号化する工程と、
エントロピエンコード化を用いて剰余値を符号化する工程と
を含む、方法。
【請求項３】
データ記号が2進表現を含む、請求項1または2記載の方法。
【請求項４】
データ記号がランレングス・エンコードされる、請求項1または2記載の方法。
【請求項５】
データ記号の系列からの追加のデータ記号を符号化する工程をさらに含む、請求項1または2記載の方法。
【請求項６】
データ記号の系列がオーディオおよび/またはビデオ・ストリームを表現する、請求項5記載の方法。
【請求項７】
データ記号の系列が、期待された生起確率によって系列内の各記号を順位づける記号アルファベットの中に含まれる、請求項5記載の方法。
【請求項８】
データ記号の符号化が生Golomb符号化を含む、請求項1または2記載の方法。
【請求項９】
データ記号が非数値データを含む、請求項1または2記載の方法。
【請求項１０】
データ記号が、オーディオ信号、ビデオ信号、データ信号、またはファイルである、請求項1または2記載の方法。
【請求項１１】
可変長符号を用いて指数値を符号化する工程をさらに含む、請求項2記載の方法。
【請求項１２】
可変長符号としてHuffman符号化、Fano-Shannon符号化、またはGolomb符号化の1つを用いる工程をさらに含む、請求項1または11記載の方法。
【請求項１３】
可変長符号が適応型である、請求項1または11記載の方法。
【請求項１４】
可変長符号が既定の符号を含む、請求項1または11記載の方法。
【請求項１５】
可変長符号の値が、データ記号の確率またはデータ記号の生起頻度に従い決定される、請求項1または11記載の方法。
【請求項１６】
コンピューティング・デバイスによって実行される場合、コンピューティング・デバイスに方法を遂行させるコンピュータ実行可能命令が内部に保存された、有形のコンピュータ可読メディアであって、方法が
指数値および剰余値を含む符号を用いてデータ記号を符号化する工程と、
固定長2進符号を用いて剰余値を符号化する工程と、
指数値の生起頻度に基づく可変長符号を用いて指数値を符号化する工程と
を含む、有形のコンピュータ可読メディア。
【請求項１７】
コンピューティング・デバイスによって実行される場合、コンピューティング・デバイスに方法を遂行させるコンピュータ実行可能命令が内部に保存された、有形のコンピュータ可読メディアであって、方法が
指数値および剰余値を含む符号を用いてデータ記号を符号化する工程と、
エントロピエンコード化を用いて剰余値を符号化する工程と
を含む、有形のコンピュータ可読メディア。
【請求項１８】
指数値および剰余値を含む符号を用いてデータ記号を符号化するよう構成された第一のアナライザーモジュールと、
固定長2進符号を用いて剰余値を符号化しかつ指数値の生起頻度に基づく可変長符号を用いて指数値を符号化するよう構成された第二のアナライザーモジュールと
を含むシステムであって、
第一および第二のアナライザーモジュールを1つまたは複数のコンピュータで実行する、システム。
【請求項１９】
指数値および剰余値を含む符号を用いてデータ記号を符号化するよう構成された第一のアナライザーモジュールと、
エントロピエンコード化を用いて剰余値を符号化するよう構成された第二のアナライザーモジュールと
を含むシステムであって、
第一および第二のアナライザーモジュールを1つまたは複数のコンピュータで実行する、システム。
【請求項２０】
指数値および剰余値を含む符号を用いてデータ記号を符号化するための手段と、
固定長2進符号を用いて剰余値を符号化するための手段と、
指数値の生起頻度に基づく可変長符号を用いて指数値を符号化するための手段と
を含むシステム。
【請求項２１】
指数値および剰余値を含む符号を用いてデータ記号を符号化するための手段と、
エントロピエンコード化を用いて剰余値を符号化するための手段と
を含むシステム。
【請求項２２】
指数値および剰余値を含む符号を用いてデータ記号を符号化する工程と、
可変長符号を用いて指数値を符号化する工程と、
エントロピエンコード化を用いて剰余値を符号化する工程と
を含む、方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
本発明は、指数値Eおよび剰余値Rによってデータ記号を符号化する工程を含む方法であって、指数値へ適用される符号化が可変長符号化を含む方法、およびその装置を提供する。
［請求項１０１］
指数値Eおよび剰余値Rによってデータ記号を符号化する工程を含む方法であって、指数値へ適用される符号化が可変長符号化を含む、方法。
［請求項１０２］
指数値へ適用される可変長符号化がHuffman符号化を含む、請求項101記載の方法。
［請求項１０３］
剰余値へ適用される符号化が固定長符号化を含む、請求項101記載の方法。
［請求項１０４］
固定長符号化が2進符号化を含む、請求項103記載の方法。
［請求項１０５］
データ記号が2進表現を含む、請求項101記載の方法。
［請求項１０６］
可変長符号化が適応型であり、かつ測定された生起頻度に従って符号を選択する、請求項101記載の方法。
［請求項１０７］
データ記号がランレングス・エンコードされる、請求項101記載の方法。
［請求項１０８］
追加のデータ記号を符号化して記号の系列を形成する工程をさらに含む方法であって、該記号が、期待された生起確率によって記号を順位づける記号アルファベットの中に含まれる、請求項101記載の方法。
［請求項１０９］
記号の系列がオーディオおよび/またはビデオ・ストリームを表現する、請求項108記載の方法。
［請求項１１０］
データ記号の符号化が生Golomb符号化を含む、請求項101記載の方法。
［請求項１１１］
実行される場合、結果として指数値Eおよび剰余値Rによってデータ記号を符号化するような方法を遂行する命令が記憶された記憶メディアを含む物品であって、指数値へ適用される符号化が可変長符号化を含む、物品。
［請求項１１２］
命令が、実行される場合、結果としてHuffman符号化を含む指数値へ適用される可変長符号化をさらにもたらす、請求項111記載の物品。
［請求項１１３］
命令が、実行される場合、結果として固定長符号化を含む剰余値へ適用される符号化をさらにもたらす、請求項111記載の物品。
［請求項１１４］
命令が、実行される場合、結果として2進符号化を含む固定長符号化をさらにもたらす、請求項113記載の物品。
［請求項１１５］
命令が、実行される場合、結果として2進表現を含むデータ記号をさらにもたらす、請求項111記載の物品。
［請求項１１６］
命令が、実行される場合、結果として適応型の可変長符号化をさらにもたらし、測定された生起頻度に従った符号をさらにもたらす、請求項111記載の物品。
［請求項１１７］
命令が、実行される場合、結果としてランレングス・エンコードされるデータ記号をさらにもたらす、請求項111記載の物品。
［請求項１１８］
命令が、実行される場合、結果として追加のデータ記号を符号化して記号の系列を形成することをさらにもたらし、該記号が、期待された生起確率によって記号を順位づける記号アルファベットの中に含まれる、請求項111記載の物品。
［請求項１１９］
命令が、実行される場合、結果として生Golomb符号化を含むデータ記号の符号化をさらにもたらす、請求項111記載の物品。
［請求項１２０］
指数値Eおよび剰余値Rによってデータ記号を符号化するように適応されたコンピューティング・プラットフォームを含む装置であって、指数値へ適用されるべき符号が可変長符号を含む、装置。
［請求項１２１］
指数値へ適用されるべき可変長符号がHuffman符号を含む、請求項120記載の装置。
［請求項１２２］
剰余値へ適用されるべき符号が固定長符号を含む、請求項120記載の装置。
［請求項１２３］
固定長符号が2進符号化を含む、請求項122記載の装置。
［請求項１２４］
コンピューティング・プラットフォームが、2進表現を含むデータ記号を符号化するように適応される、請求項120記載の装置。
［請求項１２５］
適用されるべき可変長符号が適応型であり、適用されるべき符号が、実質的に、測定された生起頻度に従って選択される、請求項120記載の装置。
［請求項１２６］
コンピューティング・プラットフォームが、ランレングス・エンコードされるデータ記号を符号化するように適応される、請求項120記載の装置。
［請求項１２７］
コンピューティング・プラットフォームが、追加のデータ記号を符号化して記号の系列を形成するようにさらに適応され、該記号が、期待される生起確率によって記号が順位づけられる記号アルファベットの中に含まれる、請求項120記載の装置。
［請求項１２８］
コンピューティング・プラットフォームが、データ記号を生Golomb符号として符号化するようにさらに適応される、請求項120記載の装置。
【国際調査報告】
2009540670.tif 000008
2009540670.tif 000009
2009540670.tif 000010
2009540670.tif 000011