JPH09511372A

JPH09511372A - 符号・復号器用圧縮ソースコーディング表

Info

Publication number: JPH09511372A
Application number: JP7525868A
Authority: JP
Inventors: トッド、グレイグ・キャンプベル
Original assignee: Dolby Laboratories Licensing Corp
Current assignee: Dolby Laboratories Licensing Corp
Priority date: 1994-04-01
Filing date: 1995-03-31
Publication date: 1997-11-11
Also published as: CN1144583A; KR100349447B1; EP0754374B1; US5550541A; AU684013B2; CN1119868C; ATE182041T1; DE69510662T2; EP0754374A1; KR970700957A; DE69510662D1; AU2203695A; WO1995027337A1; CA2183352A1

Abstract

(57)【要約】多次元ハフマンエンコーディングのようなデータ圧縮技術を応用する装置又は方法は、符号化に先だってメッセージ内の記号を順序づけしかつ結果的に得られるコードワードと共に順序情報を伝えることによって、従来のものより小さい圧縮された符号化表を用いる。データ圧縮を応用する装置又は方法は、コードワードに応答して圧縮された復号表からメッセージを回復させ、コードワードと共に受取った順序情報に従って記号を再順序づけする。

Description

【発明の詳細な説明】符号・復号器用圧縮ソースコーディング表技術分野概して本発明は、情報を符号化及び復号するために表又はマトリックスを用いる各種のソースコーディング技術に関する。特に本発明は、ハフマンコーディングのようなコーディング技術用の表を記憶するのに要する空間が小さい符号化・復号装置に関する。背景技術データ記憶及び通信システムではデータ圧縮技術がますます用いられている。データ圧縮は、記憶空間の量又は情報伝達に要する伝送帯域幅を最小にすることができるからである。「損失のある」技術で圧縮されたデータは、圧縮中に若干のデータが失われるので、いかなる技術によっても完全に回復することはできない。しかし、「損失のない」技術で圧縮されたデータは、完全に回復することができる。量子化は、良く知られた損失のある技術の１つである。ランレングス符号化（ＲＬＥ）は、良く知られた損失のない技術である。あるオーディオ及びビデオ用途では、しばしば損失のある技術及び損失のない技術の双方が用いられる。人の知覚を意図する信号の知覚的コーダの中には、心理知覚原理に従って損失のある技術を応用し、圧縮損失の影響が知覚されないようにすることを試みるものもある。概して損失の量は、損失のある圧縮のレベルが高くなるにつれて増大する。従って、結果的に生じる信号の主観的品質が劣化する前に、応用できる損失のある圧縮の大きさには限度がある。同様にある知覚的コーダの中には、知覚できる劣化を受けることなくさらに圧縮するために、損失のある技術に加えて損失のない技術を応用するものもある。量子化された情報に損失のない圧縮を応用する知覚的符号化標準は、ＩＳＯ／ＭＥＰＧ標準文書「約１．５Ｍｂｉｔ／ｓのデジタル記憶媒体用映画及び音声の符号化−−ＣＤ１１１７２−３（オーディオ第３部）」（ＩＳＯ／ＩＥＣＪＴＣＩ／ＳＣ２９，１９９２）に記載されており、参照により本明細書に組入れる。損失のない圧縮技術であるハフマンコーディングを応用して変換係数を量子化する変換コーダの例は、米国特許第５，２８５，４９８号に記載されている。同特許は参照により本明細書に組み入れる。ハフマンコーディング（符号化）は、よく知られた損失のない圧縮技術である。ハフマンコーディングの各種の実施例は、しばしば１以上の表又はマトリックスを用いる。圧縮中、１以上の圧縮すべき１以上のデータ記号が、適切な符号化表への鍵（キー）として用いられる。すなわち、符号化表は、適切な可変長コードワードを与える。圧縮解除中、可変長コードワードは、１以上の復号表に記憶された樹状構造を反転させるのに用いられ、圧縮された記号の最初の値を与えるようにされる。多くの実際的実施態様において符号化及び復号表は、読出し専用記憶素子（ＲＯＭ）又はランダムアクセス記憶装置（ＲＡＭ）に記憶される。不幸にして、これらの符号化表は非常に大きくかなりの記憶装置を要し、それによって実施コストが増大する。符号化表を記憶しかつ利用するために要する記憶装置の総数を最小にするのが望ましい。発明の開示圧縮性能上著しい不利益がなくデータ圧縮及びデータ圧縮解除と共に用いるために、従来の符号化表より小さい空間に記憶できる圧縮された符号化表を提供するのが本発明の目的である。符号化器の一実施態様に組入れられる本発明の教示によれば、記号対における記号の順序を表す順序情報が特殊な順序に関して発生され、特殊な順序に従って順序づけられた記号対に応答してコードワードを発生させるために符号化表が参照され、コードワード及び順序情報が次の処理、伝送又は記憶に適した形にアセンブルされる。復号器の一実施態様に組入れられる本発明の教示によれば、符号化された信号からコードワード及び順序情報が抽出され、コードワードに応答して順序づけられた記号対を発生させるために復号表が参照され、順序情報に応答して必要とされる記号対が再順序づけられる。多くの代替が可能である。例えば、記号は、３つ以上の記号からなる順序づけられた対にグループ化され、当該記号は本質的に任意の順序に従って対内で再順序づけられる。本発明は、多くの異なった実施態様で実施可能であると共に広範な種類の符号化器及び復号器に組込むことができる。本議論を通して、オーディオ符号化用途につき特に言及されている。しかし、本発明は、例えば、情報記憶及び検索等の広範囲な用途で用いることができることを理解されたい。本発明の各種の特徴及びその望ましい実施態様は、添付図と共に以下の議論を参照することによりよりよく理解し得るであろう。以下の議論及び図面の内容は、例としてのみ述べたもので、本発明の範囲に対する制限を表すものと理解すべきではない。図面の簡単な説明図１は、情報処理システムの基本的構成図を例示する。図２ａ及び２ｂは、分割帯域信号分析・合成システムの機能的構成図を例示する。図３ａ及び３ｂは、圧縮器及び圧縮解除器の機能的構成図を例示する。図４ａ及び４ｂは、本発明の教示による圧縮及び圧縮解除論理の流れ図を例示する。図５ａ及び５ｂは、２分木復号構成を例示する。図６ａ及び６ｂは、３次元符号化のための符号化表の概念図を例示する図表である。本発明の実施モード図１は、本発明を組込み得る情報処理システムを例示する。一実施態様において、処理装置２は、経路１から情報を伝達する入力信号を受取り、信号にデータ圧縮技術を応用し、圧縮結果を表す符号化された信号を経路３に沿って送る。記憶装置４は、データ圧縮中処理装置２により用いられる１以上の符号化表を記憶する。第２実施態様において、処理装置２は、経路１から圧縮されたデータを含む符号化された信号を受取り、信号にデータ圧縮解除技術を応用し、圧縮解除結果を表す出力信号を経路３に沿って送る。記憶装置４は、データ圧縮解除中処理装置２により用いられる１以上の復号表を記憶する。処理システムの特殊な具体化及びアーキテクチャは本発明の実施上決定的ではない。例えば、処理装置２は、記憶装置４に記憶されたソフトウェアを実行する処理装置によるか若しくは特殊アプリケーションハードウェアにより実施することもできる。記憶装置４は、読出し専用記憶素子（ＲＯＭ）及びランダムアクセス記憶装置（ＲＡＭ）のような読出し・書込み記憶装置の所望のあらゆる組合わせを含んでもよい。処理装置２及び記憶装置４は、マイクロコンピュータ集積回路のような単一成分により実施してもよい。図２ａ及び２ｂは、本発明の各種の面を組入れるのに適した分割帯域信号分析・合成システムの幾つかの特徴を例示する。図２ａを参照すると、分析フィルタ１０２は、経路１００から受取った入力信号に応答してスペクトル信号を発生させ、量子化装置１０４はスペクトル信号を量子化し、圧縮器１０６は量子化された信号に損失のない圧縮を加え、フォーマッタ１０８は、圧縮された信号を次の処理、伝送又は記憶に適した形を有する符号化された信号にアセンブルし、符号化された信号を経路１１０に沿って送る。知覚的符号化システムにおいて量子化装置１０４は、知覚的モデルに応答してその量子化を適応させる。図２ｂを参照すると、デフォーマッタ１２２は、経路１２０から受取った符号化された信号から圧縮されたスペクトル信号を抽出し、圧縮解除装置１２４は、圧縮されたスペクトル信号を圧縮解除することによって損失のない圧縮の効果を反転させ、量子化解除装置１２６は圧縮解除されたスペクトル信号を量子化解除し、逆フィルタ１２８は、量子化解除されたスペクトル信号に応答して経路１３０に沿って出力信号を発生させる。本発明の実施上重要ではない分割帯域分析・合成システムに対する実施の多くの詳細がここでは述べられている。追加の情報については、参照によりは本明細書に組入れた、米国特許第５，１０９，４１７を参照のこと。本発明は、信号分析・合成用途若しくはデータ圧縮の損失のある形に適用される用途にも限定されない。例えば、本発明はコンピュータディスク記憶システムに組入れてもよい。図２ａの領域１１２内の成分は、圧縮すべきデータソースの一例を表すものと理解すべきである。同様に、図２ｂの領域１２２内の成分は、宛先又は圧縮解除されたデータの用途の一例を表すものと理解すべきである。幾つかの実施例の構成図３ａに示す構成図は、圧縮装置１０６の一実施例に対する付加的詳細を与える。複数の記号が経路２００から受取られる。順序回路２０２は、経路２０４に沿って特殊な順序について該複数の記号の順序に関する情報を発生させ、特殊な順序に合致するように記号を再順序づけ、順序づけられた記号を符号器２０６へ送る。符号器２０６は、表３０８を参照し、順序づけられた記号に応答して経路２１０に沿ってコードワードを発生させる。代わりの実施態様において順序回路２０２は、特殊な順序について該複数の記号の順序に関する情報を発生させるが、記号を再順序づけしない。その代わりに、順序情報は、図に示されていない経路に沿って符号器２０６に送られる。符号器２０６は、記号及び順序情報に応答してコードワードを発生させる。デジタルシステムにおいて数値順序は、情報が数値で表されるので、特殊な順序に対して便利な選択である。例えば、アルファベット及び句読点記号のような非数値情報は、情報交換用米国標準コード（ＡＳＣＩＩ）による数値を有する記号で表すことができる。数値情報は本来定量的であるが、同様にある形式の符号化を通して数値化した記号で表すことができる。例えば、１９８０から始まる歴年は、ゼロで始まる正の整数の範囲内の数値を持つ記号に符号化できる。好ましい実施態様において、各記号ｘ_iは数量の大きさのみを表す。記号により表される数値情報が正又は負のいずれであるかを伝えるために追加の情報を要する。さらに、このような記号に応答して発生されるコードワードは、正及び負の数量間の区別をしない。従って、符号ビットは、非ゼロ数値情報を表すコードワードと共に含まれる。この符号化の例は、上記ＩＳＯ／ＭＰＥＧ標準書類に与えられる。記号の好都合な数値順序づけは、例えば、以下の順序で配列されたｎ記号ｘ_i の対ような一連の増加する数値である。すなわち、ｘ₁≦ｘ₂≦・・・ｘ_n。別な例として、３つの記号の対は次のように順序づけることができる。すなわち、ｘ₁ ≦ｘ₃≦ｘ₂。本発明の実施上決定的な特殊な順序づけはない。図４ａは、本発明による記号の対を圧縮するための圧縮器の一実施態様の論理を例示する流れ図である。ＥＮＴＲＹ（入口）３００は、記号（ｘ，ｙ）の対を受取る。ＯＲＤＥＲ（順序）は、３０２ｘ≦ｙかどうかを設定する。もしそうなら、ＣＬＥＡＲ（クリア）３０４は、「再順序フラグ」をゼロに設定する。さもなければ、ＳＷＡＰ（スワップ）３０６は、ｘ及びｙの数値を交換し、再順序フラグを１に設定する。ＣＯＤＥＲ（符号器）３０８は、適切に順序でけられた記号（ｘ，ｙ）の対に応答してコードワードを発生させる。ＥＸＩＴ（出口）３１０は、次の処理、伝送又は記憶のためにコードワード及び再順序フラグを与える。実質的に同等な処理が次のプログラム断片で表される。そこでは、ＣＷはコードワードで、ＯＩは再順序フラグで、ＴＥ（ｘ，ｙ）は符号化表を用いる符号化を表す。記号の再順序づけは、ライン６の引数の順序を反転することによって行われることに注目のこと。 (1) ｅｎｔｒｙ［ｘ，ｙ］ (2) ｉｆｘ≦ｙｔｈｅｎ (3) ＣＷ＝ＴＥ［ｘ，ｙ］ (4) ＯＩ＝０ (5) ｅｌｓｅ (6) ＣＷ＝ＴＥ［ｙ，ｘ］ (7) ＯＩ＝１ (8) ｅｎｄｉｆ (9) ｅｘｉｔ［ＣＷ，ＯＩ］図３ｂに示す構成図は、圧縮解除装置１２６の一実施例に対する付加的詳細を与える。復号器２２４は表２２６を参照し、経路２２０から受取るコードワードに応答して順序づけられた複数の記号を発生させる。順序回路２２８は経路２２２から最初の順序の表示を受取り、最初の順序を設定するのに要する複数の記号を再順序づけし、適切に順序づけられた記号を経路２３０に沿って送る。図４ｂは、本発明によるコードワードを記号の対に圧縮解除するための圧縮解除器の一実施態様の論理を例示する流れ図である。ＥＮＴＲＹ（入口）３２０は、コードワード及び最初の順序の表示を受取る。ＤＥＣＯＤＥＲ（復号器）３２２は、コードワードに応答して記号（ｘ，ｙ）の対を発生させる。ＯＲＤＥＲ（順序）３２４は、記号の対の最初の順序がｘ≦ｙであったかどうかを設定する。もしそうでなかったなら、ＳＷＡＰ（スワップ）３２６は、ｘ及びｙの数値を交換する。ＥＸＩＴ（出口）３２８は、次の用途のために適切に順序づけた記号（ｘ，ｙ）の対を与える。実質的に同等な処理が次のプログラム断片で表される。そこでは、ＣＷはコードワードで、０１は再順序表示で、ＴＤ［ＣＷ］は復号表を用いる復号を表す。記号の再順序づけは、プログラム断片からの出口に設けたライン６の記号の順序を反転することによって行われることに注目のこと。 (1) ｅｎｔｒｙ［ＣＷ，ＯＩ］ (2) （ｘ，ｙ）＝ＴＤ［ＣＷ］ (3) ｉｆＯＩ＝０ｔｈｅｎ (4) ｅｘｉｔ［ｘ，ｙ］ (5) ｅｌｓｅ (6) ｅｘｉｔ［ｙ，ｘ］ (7) ｅｎｄｉｆ従来の符号化表本発明の各種の面を組入れた符号器の幾つかの実施態様を考察することにより、基本概念はよりよく理解することができよう。ここで論じる実施態様は、ハフマンコーディング技術を記号ｘ及びｙの対に応用するが、原理及び概念は、他の次元及びシャノン・ファノコーディングのような他のコーディング技術に適用できることを理解されたい。一実施態様においてハフマンコーディングは、１６の異なったメッセージの各々に対するデータ圧縮を与え、そこでは各メッセージが記号（ｘ，ｙ）の対で表される。各メッセージに対する発生確率は以下のマトリックスＰ₀で与えられる。この例では、確率マトリックスは対称であり、従ってメッセージ（２，３）に対する．０７の発生確率Ｐ₀（２，３）は、メッセージ（３，２）に対する．０７の発生確率Ｐ₀（３，２）と等しい。メッセージ対の「エントロピ」は、対内の各メッセージの平均情報内容である。エントロピは、対内の各メッセージを表すのに要する平均ビット数に対する下限である。Ｎメッセージの任意の対に対して次式からエントロピを得ることができる。ここで、Ｈ＝メッセージ対｛ｉ｝のエントロピＰ_i＝メッセージｉの発生確率 log＝２を底とする対数関数付加的詳細は、Lynchの『データ圧縮及び応用』(1985，pp．1-60)及びBell,Clea ry及びWittenの『テキスト圧縮』(1990，pp．100-107)から得ることができる。両文献共に参照により本明細書に組入れる。上記確率マトリックスＰ₀で表されるメッセージ対｛ｘ，ｙ｝の対するエントロピは、次式から得られるエントロピＨ₀（約３．８１１４ビット）と等しい。ハフマンコーディング又はシャノン・ファノコーディングは、例えば、１６メッセージの各々に対する可変長２進コードワードの対を得るのに用いることができる。次の例は、ハフマンコーディング技術と共に本発明をどのように用いることができるかを示すが、同様な考察が他のコーディング技術にも適用される。以下のマトリックスは符号化表ＴＥ₀で、最高に起こりやすいメッセージに対する３ビットから最低に起こりやすいメッセージに対する６ビットまで可変長のコードワードの対を含む。２・記号メッセージを符号化若しくは圧縮する処理は、符号化表から適切なコードワードを参照するために２つの記号の数値を用いることができる。例えば、メッセージ（２，３）に対するコードワードは、ＣＷ＝ＴＥ₀［２，３］＝０１００である。特殊なコーディング技術に対する平均コードワード長は、特定なメッセージが確率真トリックスによる頻度で発生すると仮定すれば、次式から得ることができる。ここで、ｌ＝コードワードの平均長ｌｅｎ（ｉ）＝メッセージｉに対するコードワード長符号化表ＴＥ₀に対する平均コードワード長は、３．８５ビットであり、理論的な最低値又はエントロピより大きい。超過は符号化にいくらかの冗長があることを示す。ハフマンコーディングはあらゆる状況下で最適ではないが、計算的に有効なので広く用いられている。不幸にして符号化及び復号表は非常に大きくかつ記憶のためにかなりの記憶装置を要する。上記の例では、各記号は４つだけの数値の１つをとることができるので、符号化表の大きさは適切である。多くの実際的用途において各記号は、多数の数値の任意のものを取ることができる。多重記号メッセージ用の符号化表は、各記号に対する可能な数値の数の積として増加することは容易に理解すべきである。上記符号化表ＴＥ₀のような表は、ｘ及びｙに対する可能な記号数値の数の平方として増大する。図１に例示したような情報処理システムの多くの実施態様において、符号化表はＲＡＭ又はＲＯＭに記憶される。従って、符号化表の大きさを低減させることができる技術は、必要な記憶装置の総数を減らすことが可能で、それにより実施上のコストを低減させる。圧縮符号化表本発明の特徴を組入れた多重記号メッセージの符号器は、従来の符号化表より遥かに小さい符号化用を用いることができる。もし２・記号メッセージ内の各記号が、可能なＮ数値の任意の１つを取ることができるなら、従来の符号化表は、Ｎ²要素を含むであろう。本発明によるこのような２・記号メッセージ用の符号化表は、僅かに（Ｎ²＋Ｎ）／２の要素を含むに過ぎない。これはＮが大きく成るにつれて従来の符号化表の大きさの半分に近付く。上記の例を参照すると、符号化表ＴＥ₀は、可能なメッセージ（ｘ，ｙ）の各々に対して１コードワード、すなわち、１６コードワードを含む。記号ｘが常に記号ｙと等しいか又はそれ以下、すなわち、ｘ≦ｙであることを保証することによって、６つのメッセージがメッセージ対｛ｘ，ｙ｝から消去され、それによって符号化表の大きさを低減させる。この数値的関係は、符号化に先だって必要に応じてｘ及びｙ記号を再順序づけすることによって保証できる。再順序づけの効果は、対応する復号器によって記号の最初の順序に関する情報に応答して反転することができる。この順序情報は、単一ビットにより伝送できる。例えば、一実施態様において、符号器は必要な記号対を再順序づけし、順序づけした対に対するコードワードを発生させ、ｘ＝ｙでない場合のみ順序情報を発生させる。順序情報は単一ビットで伝達される。同ビットは、もし記号が最初順序通りでないなら１に等しく、またもし記号が最初順序通りなら０に等しい。ｘ＞ｙの場合記号の再順序づけは、ｘ＝ｙでない各メッセージ（ｘ，ｙ）に対する発生確率を効果的に倍増させる。この変化は、次の確率マトリックスＰ₁に反映される。以下の符号化表ＴＥ₁は、長さが３乃至４ビットで変わる、この修正されたメッセージ対に対するコードワードを含む。上記式２及び３から、対｛ｘ，ｙ｝内のあるメッセージの確率が現在ゼロであることを考慮して、修正されたメッセージ対のエントロピが約３．２３１４ビットであり、表ＴＥ₁に対する平均コードワード長が３．２７ビットであることが分かる。この減少は、順序情報を復号器に伝えるのに要する任意の付加的ビットにより相殺される。符号化表の大きさの低減と引換えに圧縮性能における不利益は受けない。その理由は、順序情報を伝えるのに要するビット数がメッセージエントロピにおける等しい減少により相殺されるからである。これは次式を計算することによって立証される。ｌ₀₁＋△Ｈ (4) ここで、ｌ₀₁＝順序情報を伝えるのに要する平均ビット数 △Ｈ＝修正されたメッセージ対に対するエントロピの変化上記の通り、２・記号メッセージに対する順序情報は、１ビットにより伝送可能で、ｘ＝ｙ以外のときにのみ伝送するだけでよい。この平均長は、次式で計算できる。ここで、Ａ＝ｘ＜ｙに対するメッセージ対Ｂ＝ｘ＞ｙに対するメッセージ対Ｐ_A＝対Ａ内の全メッセージの累積確率Ｐ_B＝対Ｂ内の全メッセージの累積確率確率マトリックスＰ₀は対称であり、従って、Ｐ_A＝Ｐ_Bであり、次式が成り立つ。ｌ₀₁＝Ｐ_A＋Ｐ_B＝２Ｐ_A (6) エントロピの変化は、確率マトリックスＰ₀の主対角線から逸れた要素から容易に計算できる。これは最初のメッセージ対のエントロピＨ₀が次式で与えられることを先ず認識することによって理解できる。ここで、Ｉ＝ｘ＝ｙに対するメッセージ対Ｈ_A＝Ａ対に対するエントロピＨ_I＝Ｉ対に対するエントロピＨ_B＝Ｂ対に対するエントロピ確率マトリックスＰ₁に相当する、修正されたメッセージ対のエントロピＨ₁は次式で与えられる。確率マトリックスＰ₀が対称なので、下式が得られる。Ｈ_A＝Ｈ_B (9a) Ｈ₀＝Ｈ_A＋Ｈ₁＋Ｈ_B＝Ｈ₁＋２Ｈ_A (9b) Ｈ₁＝−２Ｐ_A＋２Ｈ_A＋Ｈ₁＝−２Ｐ_A＋Ｈ₀ (9C) △Ｈ＝Ｈ₁−Ｈ₀＝−２Ｐ_A (9d) 従って、ｌ₀₁＋△Ｈ＝２Ｐ_A＋（−２Ｐ_A）＝０ (10) 順序情報を伝達するのに要する追加のビット数は、エントロピの減少によって正確に相殺される。従って、圧縮上の不利は受けない。従来の復号表図５ａは、２分木４００の形の復号構成を例示する。例示した特殊な２分木は、上記符号化表に相当する。木の各ノードは、それぞれが他のノードに接続される２つの枝を有するか、若しくは枝を持たずに特殊なメッセージを表す「葉」ノードである。木の「幹線」の「根」ノードから出発することにより、コードワード内の連続ビットの数値に従って枝を通り、最終的に当該コードワードによって表されるメッセージを与える適切な葉ノードに達する。図示の例では、「ゼロ」ビットに応答して左手枝を、また「１」ビット応答して右手枝を通過するようにされる。例えば、コードワード「１１０１」に対する木４００の横断は、根ノードで出発し、第１ビット「１」に応答して右手枝に沿って第１ノードへ進み、第２ビット「１」に応答して右手枝に沿って第２ノードへ進み、第３ビット「０」に応答して左手枝に沿って第３ノードへ進み、その後第４ビット「１」に応答して右手枝に沿って葉ノードへ進む。葉ノードは、対応するメッセージが（２，１）であることを示す。上記符号化表ＴＥ₀を参照すると、これが適切な結果であることが分かる。一実施態様においては、木はリンクされたリスト構造を用いて実施される。木ノードを表す記憶装置のブロックは、他のノードブロックを指す２つのリンクを含む。葉ノードを表す記憶装置のブロックは、メッセージ自体を記憶するか若しくはメッセージが記憶される場所を指すリンクを含むことができる。木を記憶するのに要する記憶装置の総数は、概して木のノード数が増増加すると共に増加する。概して、記憶装置の総数は、ノード及びメッセージの数に大体比例する。図示の例では、木は１５ノード及び１６メッセージを含む。圧縮復号表本発明の特徴を組入れた多重記号メッセージ復号器は、従来の復号表より遥かに小さい復号表を用いることができる。図５ｂは、上記符号化表ＴＥ₁に相当する、２分木４１０の形の復号構成を例示する。木４００とは対照的に、木４１０は、僅かに９ノード及び１０メッセージのみを含む。圧縮された木は、上記従来の木で説明したのと同一方法で通過できるが、コードワードを適切に復号するためには追加の段階を要する。例えば、図５ｂを参照すると、コードワード「０１１」はメッセージ（１，２）に相当する。しかし、ＴＥ₁符号化表を用いる符号器は、記号を再順序づけしてしまったかもしれない。コードワードを有する符号化された信号内の順序情報をを参照することによって、復号器は適切なメッセージを設定できる。一実施態様においてもし順序情報が「ゼロ」ビットなら、適切なメッセージは（１，２）であり、もし順序情報が「１」ビットなら、適切なメッセージは（２，１）である。他の例として、コードワード「０１０」はメッセージ（４，４）に相当する。復号器は、これが適切なメッセージであることを確認するための順序情報を要しない。復号表は、他の方法で用いてもよい。例えば、復号表は、あらゆる可能なコードワードを表す入口を含むことが可能で、復号は、コードワードを入口と整合させ、対応するメッセージを取出すことを含む。本発明は、符号化及び復号表の特定な実施には限定されないことを理解されたい。本明細書でのべた実施態様は例として提示したものに過ぎない。高次元符号化上記の通り、本発明は多重次元符号化の高順序にも適用できる。ｎ記号を含むメッセージ(ｘ1,ｘ2,...ｘn)に対したは、ｎ・次元符号化を用いてもよい。もしｎ記号の各々が異なったＮ数値をとるなら、確率マトリックス及び従来の符号化表は、それぞれＮ_n入口を取ることができる。符号化及び復号表の大きさは、次元と共に劇的に増大することが容易に理解されよう。以下に述べる例は、メッセージ内の各記号は、異なったＮ数値の任意のものをとれることを前提としている。ｎ記号のグループは、ｎ階乗（ｎ！）のことなった方法で配列できる。これは、ｎ！の異なった多くのメッセージがｎ記号の異なった順列によって表されることを意味する。記号がこれらの順列の１つのみによって配列されることを保証することにより、符号化マトリックスは、約Ｎ_n／ｎ！入口の大きさに減少される。３次元符号化においては、例えば、メッセージは３つの記号（ｘ，ｙ，ｚ）を含む。メッセージ対｛ｘ，ｙ，ｚ｝に対する従来の符号化表は、Ｎ³の入口を含み、図６ａに例示する通り、各接線に沿った長さＮの立方体５００として３次元空間で視覚化できる。本発明による圧縮された符号化表は、図６ｂに示す通り、わずかに（Ｎ³＋３Ｎ²＋２Ｎ）／６入口を含み、底辺が正三角形で長さＮの互いに直角な３接線の交点で底辺と対抗する頂点を有する３次元空間の４面体５１０として視覚化される。実際に、４面体５１０は、立方体５１２の隅を切取った結果である。Ｎが大きくなるにつれて、圧縮された符号化表の入口い数はＮ³／６に近付く。原則として、圧縮された表を用いることによって被る符号化上の不利益はない。しかし、特殊な実施態様においては、順序情報の冗長性により僅かに不利益を受けるかもしれない。この冗長性は、順序情報を伝えるためにメッセージ対エントロピの減少によって節約されるより以上のビットを要するであろう。例えば３次元符号化において順序情報は、６つの可能な順序の任意の１つを伝えなければならない。６つの可能な順序を伝えるために３ビットを用いる符号化計画は、実施上は簡単であるが冗長である。もし６つの順序の各々が等しく可能なら、順序情報は、約２．５８５（すなわち、ｌｏｇ₂６）ビットを要するに過ぎない。３ビット設計は、コードワード当り約．４１５ビットを浪費する。しかし、符号化表の大きさで約８０％の減少に対してバランスをとることができるので、この非効率的計画は魅力的である。

【手続補正書】特許法第１８４条の８【提出日】１９９５年１０月５日【補正内容】路のような単一成分により実施してもよい。図２ａ及び２ｂは、本発明の各種の面を組入れるのに適した分割帯域信号分析・合成システムの幾つかの特徴を例示する。図２ａを参照すると、分析フィルタ１０２は、経路１００から受取った入力信号に応答してスペクトル信号を発生させ、量子化装置１０４はスペクトル信号を量子化し、圧縮器１０６は量子化された信号に損失のない圧縮を加え、フォーマッタ１０８は、圧縮された信号を次の処理、伝送又は記憶に適した形を有する符号化された信号にアセンブルし、符号化された信号を経路１１０に沿って送る。知覚的符号化システムにおいて量子化装置１０４は、知覚的モデルに応答してその量子化を適応させる。図２ｂを参照すると、デフォーマッタ１２２は、経路１２０から受取った符号化された信号から圧縮されたスペクトル信号を抽出し、圧縮解除装置１２４は、圧縮されたスペクトル信号を圧縮解除することによって損失のない圧縮の効果を反転させ、量子化解除装置１２６は圧縮解除されたスペクトル信号を量子化解除し、逆フィルタ１２８は、量子化解除されたスペクトル信号に応答して経路１３０に沿って出力信号を発生させる。本発明の実施上重要ではない分割帯域分析・合成システムに対する実施の多くの詳細がここでは述べられている。追加の情報については、参照によりは本明細書に組入れた、米国特許第５，１０９，４１７を参照のこと。本発明は、信号分析・合成用途若しくはデータ圧縮の損失のある形に適用される用途にも限定されない。例えば、本発明はコンピュータディスク記憶システムに組入れてもよい。図２ａの領域１１２内の成分は、圧縮すべきデータソースの一例を表すものと理解すべきである。同様に、図２ｂの領域１２２内の成分は、宛先又は圧縮解除されたデータの用途の一例を表すものと理解すべきである。幾つかの実施例の構成図３ａに示す構成図は、圧縮装置１０６の一実施例に対する付加的詳細を与える。複数の記号が経路２００から受取られる。順序回路２０２は、経路２０４に沿って特殊な順序について該複数の記号の順序に関する情報を発生させ、特殊な順序に合致するように記号を再順序づけ、順序づけられた記号を符号器２０６へ送る。符号器２０６は、表２０８を参照し、順序づけられた記号に応答して経路【手続補正書】特許法第１８４条の８【提出日】１９９６年２月２６日【補正内容】れた樹状構造を反転させるのに用いられ、圧縮された記号の最初の値を与えるようにされる。多くの実際的実施態様において符号化及び復号表は、読出し専用記憶素子（ＲＯＭ）又はランダムアクセス記憶装置（ＲＡＭ）に記憶される。不幸にして、これらの符号化表は非常に大きくかなりの記憶装置を要し、それによって実施コストが増大する。符号化表を記憶しかつ利用するために要する記憶装置の総数を最小にするのが望ましい。米国特許第４，６４６，１４８号は、閾値を越えない連続画素値間の差にハフマンコーディングを選択的に応用する、画素値を圧縮及び記憶する技術を開示している。閾値を越える差に対しては、同技術は符号化された差よりはむしろ画素値を記憶する。ハフマンコーディングの利用を限られた数値に制限することによって、符号化表を記憶するのに要する記憶装置は低減される。しかし、同技術によって達成できる圧縮程度は、本来次善のものである。発明の開示より効率的に実施可能な符号化・複合装置を提供するのが本発明の目的である。好ましい実施態様において装置は、圧縮性能上著しい不利益がなくデータ圧縮及びデータ圧縮解除と共に用いるために、従来の符号化表より小さい空間に記憶できる圧縮された符号化表を用いる。符号器の一実施態様に組入れられる本発明の教示によれば、特殊な順序に関して複数の記号内の順序を表す順序情報が発生され、特殊な順序に従って順序づけられるように必要に応じて再順序づけされた記号又は記号及び順序情報に応答してコードワードが発生され、コードワード及び順序情報は、次の処理、伝送又は記憶に適した形にアセンンブルされる。復号器の一実施態様に組入れられる本発明の教示によれば、符号化された信号からコードワード及び順序情報が抽出され、コードワードに応答して順序づけられた複数の記号が発生され、順序情報に応答して複数の記号が必要に応じて再順序づけられる。多くの代替が可能である。例えば、記号は本質的に任意の順序に従って対内で再順序づけられ、コードワードは、従来の符号化表より著しく小さい符号化表を参照してコードワードが発生、復号される。請求の範囲１人の知覚を意図する信号を表す複数の記号を符号化する方法であって、特殊な順序に関して前記複数の記号内の記号順序を表す順序情報を発生させ、前記特殊な順序により順序づけられのに必要とされる再順序づけされた複数の記号又は前記複数の記号及び前記順序情報に応答してコードワードを発生させ、該特殊な順序により順序づけられた前記複数の記号が前記コードワードから回復できるようにし、前記コードワード及び前記順序情報を処理、伝送又は記憶に適した形にアセンブルすることから成る符号化方法。２前記特殊な順序が前記記号に相当する相対的数値に基づく、請求項１の方法。３前記複数の記号が記号ｘ及びｙの対であり、前記順序情報は、前記記号対が該記号対に相当する特殊な数値関係により順序づけられているかどうかを示し、前記特殊な数値関係が以下の一連の関係から選ばれる請求項１の方法。ｘ＜ｙ，ｘ≦ｙ，ｘ≧ｙ４前記コードワードが表入口を含む符号化表に応答して発生され、前記表入口が、前記特殊な順序で順序づけられる各種の複数の記号のみに対するコードワードを表す、請求項１乃至３のいずれか１つの方法。５前記コードワードが、前記特殊な順序により順序づけられた前記複数の記号の発生可能性とは逆に変化する長さを有する、請求項１乃至４のいずれか１つの方法。６前記コードワードが、ハフマン符号化又はシャノン符号化技術のいずれかにより発生される、請求項５の方法。７人の知覚を意図する信号を表す複数の記号に応答して調製された符号化された信号を復号する方法であって、前記符号化された信号から特殊な順序に関して前記複数の記号内の記号順序を表すコードワード及び順序情報を抽出し、前記コードワードを復号することによって一連の中間記号を発生（３２２）させ、前記一連の中間記号内の記号を前記順序情報に従って順序づけすることによって前記複数の記号を回復（３２４，３２６）させることから成る復号方法。８前記一連の中間記号が記号対を含み、前記順序情報は、前記複数記号内の記号が前記特殊な数値関係により順序づけられているかどうかを示す、請求項７の方法。９前記一連の中間記号が、表入口を含む復号表に応答して発生され、前記表入口は、記号が前記特殊な順序で順序づけられる一連の中記号のみを表す、請求項７またあ８の方法。 10 前記コードワードが、前記特殊な順序により順序づけられた前記複数の記号の発生可能性とは逆に変化する長さを有する、請求項７乃至９のいずれか１つの方法。 11 前記復号が、ハフマン符号化又はシャノン符号化技術のいずれかにより行われる、請求項１０の方法。 12 人の知覚を意図する信号を表す複数の記号を符号化する符号器であって、特殊な順序に関して前記複数の記号内の記号順序を表す順序情報を発生させる順序装置（２０２）と、前記特殊な順序により順序づけられのに必要とされる再順序づけされた複数の記号又は前記複数の記号及び前記順序情報に応答してコードワードを発生させる符号化装置（２０６）であって、該特殊な順序により順序づけられた前記複数の記号が前記コードワードから回復できるようにする符号化装置（２０６）と、前記コードワード及び前記順序情報を処理、伝送又は記憶に適した形にアセンブルするフォーマット装置とから成る符号器。 13 前記特殊な順序が前記記号に相当する相対的数値に基づく、請求項１２の符号器。 14 前記複数の記号が記号ｘ及びｙの対であり、前記順序装置（２０２）は、前記記号対が該記号対に相当する特殊な数値関係により順序づけられているかどうかを示す順序情報を発生させ、前記特殊な数値関係が以下の一連の関係から選ばれる請求項１２の符号器。ｘ＜ｙ，ｘ≦ｙ，ｘ≧ｙ 15 前記符号化装置（２０６）が表入口を含む１以上の符号化表（２０８）を記憶するＲＡＭ，ＲＯＭを有し、前記符号化装置が前記１以上の符号化表前に応答して前記コードワードを発生させ、前記表入口が、前記特殊な順序で順序づけられる各種の複数の記号のみに対するコードワードを表す、請求項１２乃至１４のいずれか１つの符号器。 16 前記符号化装置（２０６）が、前記特殊な順序により順序づけられた前記複数の記号の発生可能性と逆に変化する長さを有する、請求項１２乃至１５のいずれか１つの符号器。 17 前記符号化装置（２０６）が、ハフマン符号化又はシャノン符号化技術のいずれかにより前記コードワードを発生させる、請求項１６の符号器。 18 人の知覚を意図する信号を表す複数の記号に応答して調製された符号化された信号を復号する復号器であって、前記符号化された信号から特殊な順序に関して前記複数の記号内の記号順序を表すコードワード及び順序情報を抽出するデフォーマット装置（１２２）と、前記コードワードを復号することによって一連の中間記号を発生させる復号装置（２２４）と、前記順序情報に従って前記一連の中間記号内の記号を順序づけすることによって前記複数の記号を回復させる順序装置（２２８）とから成る復号器。 19 前記一連の中間記号が記号対を含み、前記順序情報は、前記複数記号内の記号が前記特殊な数値関係により順序づけられているかどうかを示す、請求項１８の復号器。 20 前記復号装置（２２４）が表入口を含む１以上の復号表を記憶するＲＡＭ，ＲＯＭを有し、前記復号装置が前記１以上の復号表（２２６）に応答して前記コードワードを発生させ、前記表入口が、前記特殊な順序で順序づけられる各種の複数の記号のみに対するコードワードを表す、請求項１８又は１９の復号器。 21 前記復号装置（２２４）が、前記特殊な順序により順序づけられた前記複数の記号の発生可能性とは逆に変化する長さを有する、請求項１８乃至２０のいずれか１つの復号器。 22 前記復号装置（２２４）が、ハフマン復号又はシャノン復号技術のいずれかにより前記コードワードを復号する、請求項２１の復号器。

Claims

【特許請求の範囲】１人の知覚を意図する信号を表す複数の記号を符号化する方法であって、特殊な順序に関して前記複数の記号内の記号順序を表す順序情報を発生させ、前記特殊な順序に従って順序づけられた前記複数の記号に応答してコードワードを発生させ、前記コードワード及び前記順序情報を処理、伝送又は記憶に適した形にアセンブルすることから成る符号化方法。２前記特殊な順序が前記記号に相当する相対的数値に基づく、請求項１の方法。３前記複数の記号が記号ｘ及びｙの対であり、前記順序情報は、前記記号対が該記号対に相当する特殊な数値関係により順序づけられているかどうかを示し、前記特殊な数値関係が以下の一連の関係から選ばれる請求項１の方法。ｘ＜ｙ，ｘ≦ｙ，ｘ≧ｙ４前記コードワードが表入口を含む符号化表に応答して発生され、前記表入口が、前記特殊な順序で順序づけられる各種の複数の記号のみに対するコードワードを表す、請求項１乃至３のいずれか１つの方法。５前記コードワードが、前記特殊な順序により順序づけられた前記複数の記号の発生可能性とは逆に変化する長さを有する、請求項１乃至４のいずれか１つの方法。６前記コードワードが、ハフマン符号化又はシャノン符号化技術のいずれかにより発生される、請求項５の方法。７人の知覚を意図する信号を表す複数の記号に応答して調製された符号化された信号を復号する方法であって、前記符号化された信号から特殊な順序に関して前記複数の記号内の記号順序を表すコードワード及び順序情報を抽出し、前記コードワードを復号することによって一連の中間記号を発生させ、前記一連の中間記号内の記号を前記順序情報に従って順序づけすることによって前記複数の記号を回復させることから成る復号方法。８前記一連の中間記号が記号対を含み、前記順序情報は、前記複数記号内の記号が前記特殊な数値関係により順序づけられているかどうかを示す、請求項７の方法。９前記一連の中間記号が、表入口を含む復号表に応答して発生され、前記表入口は、記号が前記特殊な順序で順序づけられる一連の中記号のみを表す、請求項７またあ８の方法。 10 前記コードワードが、前記特殊な順序により順序づけられた前記複数の記号の発生可能性とは逆に変化する長さを有する、請求項７乃至９のいずれか１つの方法。 11 前記復号が、ハフマン符号化又はシャノン符号化技術のいずれかにより行われる、請求項１０の方法。 12 人の知覚を意図する信号を表す複数の記号を符号化する符号器であって、特殊な順序に関して前記複数の記号内の記号順序を表す順序情報を発生させる順序装置と、前記特殊な順序に従って順序づけられた前記複数の記号に応答してコードワードを発生させる符号化装置と、前記コードワード及び前記順序情報を処理、伝送又は記憶に適した形にアセンブルするフォーマット装置とから成る符号器。 13 前記特殊な順序が前記記号に相当する相対的数値に基づく、請求項１２の符号器。 14 前記複数の記号が記号ｘ及びｙの対であり、前記順序情報は、前記記号対が該記号対に相当する特殊な数値関係により順序づけられているかどうかを示し、前記特殊な数値関係が以下の一連の関係から選ばれる請求項１２の符号器。ｘ＜ｙ，ｘ≦ｙ，ｘ≧ｙ 15 前記符号化装置が表入口を含む１以上の符号化表を記憶するＲＡＭ，ＲＯＭを有し、前記符号化装置が前記１以上の符号化表前に応答して前記コードワードを発生させ、前記表入口が、前記特殊な順序で順序づけられる各種の複数の記号のみに対するコードワードを表す、請求項１２乃至１４のいずれか１つの符号器。 16 前記符号化装置が、前記特殊な順序により順序づけられた前記複数の記号の発生可能性と逆に変化する長さを有する、請求項１２乃至１５のいずれか１つの符号器。 17 前記符号化装置が、ハフマン符号化又はシャノン符号化技術のいずれかにより前記コードワードを発生させる、請求項１６の符号器。 18 人の知覚を意図する信号を表す複数の記号に応答して調製された符号化された信号を復号する復号器であって、前記符号化された信号から特殊な順序に関して前記複数の記号内の記号順序を表すコードワード及び順序情報を抽出するデフォーマット装置と、前記コードワードを復号することによって一連の中間記号を発生させる復号装置と、前記順序情報に従って前記一連の中間記号内の記号を順序づけすることによって前記複数の記号を回復させる順序装置とから成る復号器。 19 前記一連の中間記号が記号対を含み、前記順序情報は、前記複数記号内の記号が前記特殊な数値関係により順序づけられているかどうかを示す、請求項１８の復号器。 20 前記復号装置が表入口を含む１以上の復号表を記憶するＲＡＭ，ＲＯＭを有し、前記復号装置が前記１以上の復号表に応答して前記コードワードを発生させ、前記表入口が、前記特殊な順序で順序づけられる各種の複数の記号のみに対するコードワードを表す、請求項１８又は１９の復号器。 21 前記復号装置が、前記特殊な順序により順序づけられた前記複数の記号の発生可能性とは逆に変化する長さを有する、請求項１８乃至２０のいずれか１つの復号器。 22 前記復号装置が、ハフマン復号又はシャノン復号技術のいずれかにより前記コードワードを復号する、請求項２１の復号器。