(57)【要約】ベクトル量子化器は、格子Λ0に属する格子ベクトルによりベクトルｘを近似する格子量子化器（１０）を含む。格子量子化器に接続される格子ベクトル分解器（１４）は、整数ｐi≧２の対応する所定のシーケンスによる格子分割により、連続する格子Λi-1上において格子ベクトルを商ベクトルｙのシーケンス及び剰余ベクトルｒiのシーケンスに逐次分解する。ここで、ｉ＝１……ｋであり、ｋは各シーケンス中の要素数を表す正の整数である。
2009509456.tif 000002
【特許請求の範囲】
【請求項１】
格子Λ0に属する格子ベクトルによりベクトルｘを近似する工程と、
ｉ＝１……ｋであり、且つｋが整数ｐi≧２の各シーケンス中の要素数を表す正の整数である場合、対応する所定のシーケンスからの整数による格子分割により、連続する格子Λi-1上において前記格子ベクトルを商ベクトルｙiのシーケンス及び剰余ベクトルｒiのシーケンスに逐次分解する工程とを有することを特徴とするベクトル量子化方法。
【請求項２】
連続する各分解は、
ｙi＝ＱΛi（ｙi−ａi+1）／ｐi+1
ｒi+1＝ｙi−ｐi+1ｙi+1
に従って取得され、ＱΛi（ｙi−ａi+1）／ｐi+1は格子Λiへのベクトル（ｙi−ａi+1）／ｐi+1の量子化を示すことを特徴とする請求項１に記載のベクトル量子化方法。
【請求項３】
全ての格子Λiが同一の格子Λであることを特徴とする請求項１又は２に記載のベクトル量子化方法。
【請求項４】
請求項１乃至３のいずれか１項に記載のベクトル量子化方法に従ってベクトルｘを量子化する工程と、
ａiが格子Λi-1のボロノイ領域ＶΛi-1（０）に属する所定の変位ベクトルである場合、対応するボロノイコードブックＶΛi-1（ｐi，ａi）中の各剰余ベクトルｒiを符号化する工程と、
前記符号化された剰余ベクトルｒi、そのような剰余ベクトルｒiの数ｋ、及び前記ボロノイコードブックＶΛi-1（ｐi，ａi）を規定する前記整数ｐi及び前記変位ベクトルａiの前記シーケンスを含むパラメータの集合により前記ベクトルｘを表す工程とを有することを特徴とする符号化方法。
【請求項５】
Ｇi-1が格子Λi-1の生成行列である場合、
ｎi＝［Ｇi-1-1ｒi］ｍｏｄｐi, ｉ＝１……ｋ
のように前記剰余ベクトルｒiを符号化する工程を含むことを特徴とする請求項４に記載の符号化方法。
【請求項６】
前記符号化された剰余ベクトルｒi及びそのような剰余ベクトルｒiの前記数ｋを復号化器に転送する工程を含むことを特徴とする請求項５に記載の符号化方法。
【請求項７】
最後の剰余ベクトルｒkの符号を表す符合ビットｂを前記復号化器に転送する工程を含むことを特徴とする請求項６に記載の符号化方法。
【請求項８】
請求項４に記載の符号化方法に従って符号化されるベクトルｘを表す符号化パラメータを受信する工程と、
2009509456.tif 000036
に従って、前記ベクトルｘの近似値ｙを再構成する工程とを有し、
ｌ≦ｋは欠けている符号化剰余ベクトルの数を表す正の整数であり、
2009509456.tif 000037
は対応するボロノイコードブックの平均ベクトルであることを特徴とする復号化方法。
【請求項９】
全てのｋ個の符号化された剰余ベクトルｒiが受信された場合、
前記近似値ｙは、
2009509456.tif 000038
により与えられることを特徴とする請求項７に記載の復号化方法。
【請求項１０】
符号化された剰余ベクトルｒiと、そのような剰余ベクトルｒiの数ｋのみを受信し、受信側において記憶装置から前記整数ｐi及び前記変位ベクトルａiの集合を検索する工程を含むことを特徴とする請求項８又は９に記載の記載の復号化方法。
【請求項１１】
格子Λ0に属する格子ベクトルによりベクトルｘを近似する格子量子化器（１０）と、
ｉ＝１……ｋであり、且つｋが整数ｐi≧２の各シーケンス中の要素数を表す正の整数である場合、対応する所定のシーケンスからの整数による格子分割により、連続する格子Λi-1上において前記格子ベクトルを商ベクトルｙiのシーケンス及び剰余ベクトルｒiのシーケンスに逐次分解する前記格子量子化器に接続される格子ベクトル分解器（１４）とを有することを特徴とするベクトル量子化器。
【請求項１２】
請求項１０に記載のベクトル量子化器と、
ａiが格子Λi-1のボロノイ領域ＶΛi-1（０）に属する所定のベクトルである場合に対応するボロノイコードブックＶΛi-1（ｐi，ａi）中の各剰余ベクトルｒiを符号化する前記ベクトル量子化器に接続されるボロノイ格子符号化器（１４）とを有することを特徴とする符号化器。
【請求項１３】
Ｇi-1が格子Λi-1の生成行列である場合、
ｎi＝［Ｇi-1-1ｒi］ｍｏｄｐi，ｉ＝１……ｋ
のように前記剰余ベクトルｒiを符号化するボロノイ格子符号化器（１４）を含むことを特徴とする請求項１２に記載の符号化器。
【請求項１４】
2009509456.tif 000039
のように、請求項１１乃至１３のいずれか１項に記載の符号化器により符号化される受信符号化パラメータにより表されるベクトルｘの近似値ｙを再構成するベクトル再構成ユニット（３６）とを有し、
ｌ≦ｋは欠けている符号化剰余ベクトルの数を表す正の整数であり、
2009509456.tif 000040
は対応するボロノイコードブックの平均ベクトルであることを特徴とする復号化器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、逐次改善可能な格子ベクトル量子化に関するものである。
【背景技術】
【０００２】
今日、高画質を維持しつつ低ビットレートでオーディオ及びビデオコンテンツを送信及び格納するという市場のニーズが高まっている。特に、伝送資源又は記憶容量が制限される場合、低ビットレートの動作は重要なコスト要因である。一般にこれは、例えば、ＧＳＭ、ＵＭＴＳ、又はＣＤＭＡ等の移動通信システムにおけるストリーミング及びメッセージングアプリケーションにおける場合である。一方、例えばインターネット上の殆どのコンテンツは、高ビットレートでのみ入手可能であり、高画質を保証するが移動体ネットワークを介して直接ストリーミングが行われない。コンテンツプロバイダが同報通信等の種々のネットワークを介してコンテンツを配信するために、コンテンツは、必要に応じて、種々のビットレート又はあるネットワークゲートウェイにおいてトランスコーディングされたレートでいくつかの形式で入手可能である必要がある。
【０００３】
この問題に対する従来技術の解決策はスケーラブルコーデックを使用することである。スケーラブルコーデックの基本概念は、符号化が１度のみ行なわれることにより、基本レイヤ及び１つ以上の拡張レイヤを含むスケーラブルビットストリームが得られることである。少なくとも１つの拡張レイヤを廃棄することにより、ビットストリームを切り捨てる場合、即ち、ビットレートを低くする場合に、復号化器はより低いレートでデータを復号化できる。この技術により、レートトランスコーディングは単純な切捨て動作となる。
【０００４】
スケーラブルコーデックの興味深い応用例は、モバイルテレビ、ビデオ放送、ビデオオンデマンド、コンサートストリーミング等の異種ネットワークを介する音声映像コンテンツの配信である。そのようなサービスが成功するために、コンテンツ配信が可能な限り広い範囲で容易に行なわれることが非常に望ましい。同時に、ある特定の最低サービス品質が最も不利なチャネルリンクに対して保証される必要がある。即ち、帯域の狭いリンクに対して受け入れられる最低の品質が保証される必要がある。
【０００５】
ＭＰＥＧ（Moving Picture Experts Group）のような標準化組織は、スケーラブルオーディオ／ビデオコーデックに益々興味を抱いている。実際には、ＭＰＥＧは、現在スケーラブル拡張を規格Ｈ２６４／ＡＶＣ（アドバンスド・ビデオ符号化：Advanced Video Coding、高度画像圧縮符号化）で標準化しており、スケーラブルオーディオ音声コーデックに関する情報要請（Call for Information）を発行している。ＤＶＢ（Digital Video Broadcasting）等の他の標準化組織もＳＶＣ（スケーラブルＡＶＣ）の使用を考慮している。
【０００６】
ＡＡＣ（アドバンスド・オーディオ符号化Advanced Audio Coding）に関連して使用されるＢＳＡＣ（Bit Sliced Arithmetic Coding：ビットスライス算術符号化）等のスケーラブルオーディオコーデックは、既に存在し且つ標準化されているが、専門化グループであるＭＰＥＧは、低ビットレートにおいて存在する差を埋めることができる新しい技術の必要性を依然として感じている。実際には、所定のビットレートにおける性能が非スケーラブルコーデックよりスケーラブルコーデックの方が常に悪いということは周知の問題である。
【０００７】
１つの従来の音声の符号化、一般には従来のオーディオ信号の符号化は、変換符号化に基づく。この方法によると、元の入力信号は、サンプル（フレーム）の連続するオーバラップしたブロックに分割される。ＤＦＴ（離散フーリエ変換）又はＭＤＣＴ（変形離散コサイン変換）等の線形変換が各フレームに適用され、変換係数を生成する。これら係数は量子化され、量子化係数が得られる。その結果、量子化係数は符号化され、ビットストリームの一部を形成する。ビットストリームは、要求される用途に応じて格納又は送信される。復号化器は、ビットストリームを受信すると、まず先に符号化された量子化係数を復号化し、ＩＤＦＴ又はＩＭＤＣＴ等の逆変換を実行して復号化フレームを得る。通常、復号化時間領域信号を生成するために、復号化フレームは、いわゆるオーバラップ／加算処理により組み合わされる。
【０００８】
ベクトル量子化（ＶＱ）は、いくつかの係数がベクトルにグループ化される周知の量子化技術である。結果として得られるベクトルは、コードブックのエントリにより近似される。使用される歪み測度に応じて、コードブック中の最も近接するものが係数の入力ベクトルに対する近似値として選択される。コードブックが大きい程、近似は適切になり、全体の歪みを小さくする。しかし、これにより、記憶容量、ビットレート及び計算上の複雑さは増加する。
【０００９】
ベクトル量子化に対するコードブックは異なる構成を有してもよく、いくつかの方法で設計される。
【００１０】
非構造化ベクトル量子化に対するコードブックを設計する１つの方法は、周知のＬＢＧ（Linde-Buzo-Gray）アルゴリズム（Ｋ平均法）を使用することである。非構造化コードブックは、データを学習しており、量子化されるベクトルの歪みに対して適応されるという点において最適である。しかし、この最適さは、最も近接するものを見つけるために全数探索が行なわれ、且つ非常に大きな記憶容量が要求されることにより得られる。全数探索の量及び記憶容量は、量子化器のビットレートに伴って指数関数的に増加する。
【００１１】
非構造化ベクトル量子化に対する別の方法は、構造的に制約されたベクトル量子化器である構造化ベクトル量子化器を使用することである。
【００１２】
多段ベクトル量子化は、算術及び記憶の複雑さを非常に減少した木構造量子化の形式である。所定のレートに対して大きなコードブックを有するのではなく、レートコードブックが縮小されたベクトルを量子化することにより多段ＶＱを開始する。第１の量子化段階の残差は第２段階に供給され、第２段階において、別の（又は同一の）コードブックが使用され、可能性として異なるレートでその残差を量子化する。この処理は全ての段階に対して繰り返され、最終的な量子化誤差が得られる。量子化器の総レートは、各量子化器段階のレートの合計である。
【００１３】
多段ベクトル量子化において、ソースベクトルｘが第１段階のコードブックＣＢ1により量子化されることにより、指標ｉ1のコードベクトルｃ1（ｉ1）が得られる。第１段階の残余誤差がｅ1 ＝ｘ−ｃ1(ｉ1)で算出され、且つコードブックＣＢ2を使用する第２段階により量子化されることにより、指標ｉ2のコードベクトルｃ2（ｉ2）が得られる。この処理は、残差ｅn-1＝ｅn-2−ｃn-1（ｉn-1）が最後の段階に入力され、且つコードブックＣＢnにより量子化されることにより、指標ｉnのコードベクトルｃn（ｉn）が得られるまで、後続する段階により何度も繰り返される。
【００１４】
ソースベクトルの再構成は、量子化器の逆演算を実行することから成る。復号化器は、指標ｉ1, ｉ2，……，ｉnを受信すると、以下の式により与えられる再構成ベクトルを算出する。
【００１５】
2009509456.tif 000003
【００１６】
ｘを符号化するのに使用される全体のビットレートは、各段階のビットレートの合計である。計算上の複雑さを軽減するのに加えて、多段ベクトル量子化器は逐次改善可能にベクトルを符号化する方法を提供する。
【００１７】
例えば、ｉ1，ｉ2，……，ik，ｋ＜ｎである指標の一部のみが受信される場合でも以下のベクトルを再構成できる。
【００１８】
2009509456.tif 000004
【００１９】
このベクトルは、より大きな量子化誤差を有する。即ち、性能が低い。しかし、より低いビットレートを必要とするだけである。従って、追加の受信指標の各々は再構成ベクトルを改善する。
【００２０】
多段ＶＱは、通常の非制約ＶＱと比較して利点を有するが、いくつかの制限がある。
【００２１】
・高レートの量子化ステップ（即ち、大きなコードブック）が要求された場合、多段ベクトル量子化は非常に複雑になる。
【００２２】
・コードブックの記憶容量は段階数に比例し、逐次改善の融通性を制限する。
【００２３】
・逐次改善の特性は連続する量子化ステップに対する制約を暗示し、任意のレートで達成可能な全体の性能を制限する。
【００２４】
別の種類の構造化ＶＱは、格子ベクトル量子化（ＬＶＱ）である。ＬＶＱにおいて、コードブックは、所定の格子中の点の部分集合を使用して形成される。格子は、基本ベクトルの集合の整数線形結合として構成される幾何学的なオブジェクトである。複雑さが少なくメモリ消費が小さいため、量子化に対して格子を使用することは非常に好ましい。しかし、性能及び複雑さに影響を及ぼすいくつかの問題が依然として存在する。
【００２５】
・可変レートの符号化の場合、所望の歪み及びレートを得るために格子（基本ベクトル）を変倍する必要があり、また結果として得られる指標を可逆符号化器により符号化する必要がある。
【００２６】
・固定レートの符号化の場合、殆どの入力ベクトル（サポートと呼ばれる）が規定された整形領域に入るように、ある特定のコードブックを規定し且つ格子を変倍するために整形が使用される必要がある。異常値とも呼ばれる整形領域外のベクトルは、非常に深刻な問題を引き起こす。その問題は、飽和又は変倍により解決されるかもしれない。双方の技術は、追加的な計算負荷を与え、特に大きな異常値の場合には画質を劣化させる可能性がある。
【００２７】
次元ｄの格子中の各点ｃは、ｃ＝Ｇｍと書ける。ここで、Ｇは生成行列と呼ばれ、ｍは整数のベクトルである。六方格子Ａ2、整数格子Ｚn、及びゴセット格子Ｅn等のいくつかの一般的な格子が存在する。
【００２８】
格子がある特定のレートの量子化器を設計するために選択される場合、ある特定のビット数を有するコードブックを形成するために、格子点の部分集合のみが保持される。周知の技術は、いわゆる格子の整形である。この技術は、形状境界に従って格子を切り捨てることから成る。形状境界は、ある点（原点）を中心とし、矩形、球形、角錐、ボロノイ等の任意の形状をとってもよい。
【００２９】
量子化に対して格子を使用することにより、非常に効率的な最近接探索アルゴリズムが可能になる。最も有用な格子に対するそのような探索アルゴリズムは、非特許文献１において見出される。一方、量子化に対して格子を使用する場合、格子点が生成行列から直接取得されるため、コードブックを実際に格納する必要はない。
【００３０】
格子点が見つけられる場合、更なるタスクは格子点に指標付けすることから成る。いくつかの指標付けアルゴリズムが考案されている。興味深い種類の指標付けアルゴリズムは、例えば、非特許文献２、非特許文献３で説明されるリーダーの概念を採用する。この種の指標付けは、球形の整形を使用する場合に最適に使用される。
【００３１】
別の種類の整形は、ボロノイ整形である。これは非特許文献４で説明され、ボロノイ領域の概念に依存する。
【００３２】
非特許文献４において説明されるように、ボロノイコードブック中のコードベクトルの指標付け及び回復は、整数モジュロ演算を使用して非常に効率的に行なわれる。
【特許文献１】国際公開第０３／１０３１５１号パンフレット
【特許文献２】米国特許第６，５１６，２９７号明細書
【非特許文献１】コンウェイ  Ｊ．Ｈ．及びスローアン  Ｎ．Ｊ．Ａ．（Conway J.H.、Sloane N.J.A.）著、「格子量子化器と符号のための高速量子化及び復号化アルゴリズム（Fast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes）」、ＩＥＥＥトランザクション情報理論（IEEE transactions on Information Theory）、VOL. IT-28、NO. 2、１９８２年３月、２２７〜２３２ページ
【非特許文献２】アドール  Ｊ．−Ｐ、ランブリン  Ｃ．、レグヤダル  Ａ．（Adoul J.-P.、Lamblin C.、Leguyader A.）著、「球ベクトル量子化を用いた２４００ｄｐｓでのベースバンド・スピーチ・コーディング（Baseband Speech Coding at 2400 bps using Spherical Vector Quantization）」、ＩＣＡＳＳＰ予稿集（Proc. ICASSP）、１９８４年、１．１２．１〜１．１２．４ページ
【非特許文献３】ラールト  Ｐ．、グレモット  Ｃ．（Rault P.、Guillemot C.）著、「Ｚｎ、Ａｎ、Ｄｎ、Ｄｎ＋＋格子ベクトル量子化器のための指標付けアルゴリズム（Indexing Algorithms for Zn, An, Dn and Dn++ Lattice Vector Quantizers）」、ＩＥＥＥトランザクションマルチメディア（IEEE transactions on Multimedia）、VOL. 3、NO. 4、２００１年１２月、３９５〜４０４ページ
【非特許文献４】コンウェイ  Ｊ．Ｈ．及びスローアン  Ｎ．Ｊ．Ａ．（Conway J.H.、Sloane N.J.A.）著、「格子符号と量子化器のための高速符号化方法（A Fast Encoding Method for Lattice Codes and Quantizers）」、ＩＥＥＥトランザクション情報理論（IEEE transactions on Information theory）、VOL. IT-29、NO. 6、１９８３年、８２０〜８２４ページ
【非特許文献５】Ｄ．ムクヘルリー、及びＳ．Ｋ．ミトラ（D. Mukherjee and S.K. Mitra）著、「逐次改善格子ベクトル量子化（Successive Refinement Lattice Vector Quantization）」、ＩＥＥＥトランザクション画像処理（IEEE transactions on Image Processing）、VOL. 11、NO. 12、２００２年１２月、１３３７〜１３４８ページ
【非特許文献６】Ｓ．Ｎ．ディガビ、Ｎ．Ｊ．Ａ．スローアン、Ｖ．Ａ．バイシャムパヤン（S.N. Diggavi、N.J.A. Sloane、V.A. Vaishampayan）著、「非対象マルチプル記述格子ベクトル量子化器（Asymmetric Multiple Description Lattice Vector Quantizers）」、ＩＥＥＥトランザクション情報理論（IEEE transactions on Information Theory）、VOL. 48、NO. 1、２００２年１月、１７４〜１９１ページ
【発明の開示】
【発明が解決しようとする課題】
【００３３】
非特許文献５において説明される技術は、逐次改善により格子量子化を拡張するためにボロノイ符号化を使用する。この技術は、従来のコードブックが格子コードブックにより置き換えられる多段ＶＱに非常に類似する。この技術の本質は、各々が以前のより大きな尺度で基本格子のボロノイ領域を範囲に含む一連の縮小尺度のボロノイ格子ＶＱを生成することに基づく。しかし、特に異常値が第１段階で発生する場合、この技術は異常値の問題の影響を受ける。実際には、連続する段階は、粒状性ノイズを減少するように設計されるため、効率的に異常値に対処できない。後続する段階のコードブックエントリが先行する段階の分布を効率的に範囲に含まないため、量子化器の効率によりこの技術の別の問題が発生する。
【００３４】
特許文献１において説明される技術は、格子点を符号化するマルチレート格子量子化方法を使用する。この技術は、コードブック拡張の概念に依存する。量子化ベクトルが基本コードブックに入らない場合は、量子化ベクトルに指標付けできるように、常に基本コードブック自体が拡張される。
【００３５】
特許文献２において、対称複数記述格子ベクトル量子化器が説明されている。ラベル付け機能は、２つの異なるストリームに格納される２つの冗長記述に量子化ベクトルを分割するために使用される。非対称格子ベクトル量子化に対して同様の技術が非特許文献６において開発された。これら技術は、以下のような欠点を有する。
【００３６】
・複数記述の目的が各記述を別個に復号化できることであるため、ある特定の量の冗長性が各記述において保持され、それにより逐次改善可能な量子化器における複数記述の使用は非常に非効率的になる。
【００３７】
・最適なラベル付け機能の設計は、時間のかかるタスクであり、線形計画法を必要とする。
【００３８】
・ラベル付け機能は、指標マッチングルックアップテーブルを格納する必要があり、いくつかのマッチング機能が必要とされる場合、必要とされるメモリは増加する。
【課題を解決するための手段】
【００３９】
本発明の目的は、改善された逐次改善可能な格子ベクトル量子化、並びに結果として得られる階層化コードを符号化及び復号化することにある。
【００４０】
この目的は、添付の請求の範囲に従って達成される。
【００４１】
簡単に説明すると、ベクトル量子化は、格子Λ0に属する格子ベクトルによりベクトルｘを近似することにより開始する。その後、格子ベクトルは、整数ｐi≧２の対応する所定のシーケンスによる格子分割により、連続する格子Λi-1において商ベクトルｙiのシーケンス及び剰余ベクトルｒiのシーケンスに逐次分解される。ここで、ｉ＝１……ｋであり、ｋは各シーケンス中の要素数を表す正の整数である。
【００４２】
符号化は、対応するボロノイコードブックＶΛi-1（ｐi，ａi）の各剰余ベクトルｒiを符号化することを含む。ここで、ａiは格子Λi-1のボロノイ領域ＶΛi-1（０） に属する所定の変位ベクトルであり、前記符号化された剰余ベクトルｒi、そのような剰余ベクトルｒiの数ｋ、及びボロノイコードブックＶΛi-1（ｐi，ａi）を規定する整数ｐi及び変位ベクトルａiのシーケンスによりベクトルｘを表す。
【００４３】
復号化は、以下の式に従ってベクトルxの近似値ｙを再構成することを含む。
【００４４】
2009509456.tif 000005
【００４５】
ここで、ｌ≦ｋは欠けている符号化剰余ベクトルの数を表す正の整数であり、 
【００４６】
2009509456.tif 000006
【００４７】
は対応するボロノイコードブックの平均ベクトルである。
【００４８】
添付図面と共に以下の説明を参照することにより、本発明は、その更なる目的及び利点と共に最もよく理解されるだろう。
【発明を実施するための最良の形態】
【００４９】
ボロノイコードブックの概念が本発明にとって重要であるため、図１及び図２を参照してボロノイコードブックについて詳細に説明する。ボロノイコードブックＣΛ（ｒ，ａ）は、変倍及び平行移動されたボロノイ領域に入る全ての格子点を得ることにより形成される。すなわち、以下の式が成り立つ。
【００５０】
ＣΛ（ｒ，ａ）＝Λ∩（ｒＶΛ（０）＋ａ）      （３）
ここで、
Λは、格子を示し、
ＶΛ（０）は、格子Λに関係する原点の周囲のボロノイ領域を示し、
ｒは、正の整数倍率を示し、
ａは、格子点がｒＶΛ（０）＋ａの境界線上にならないように選択されたベクトルを示す。
【００５１】
式（３）は、図１のシーケンス（ａ）〜（ｄ）により整数格子Ｚ2に対して図示される。図１（ａ）は、格子Λ全体を示す（格子が平面全体に広がるため、格子の一部のみを示す）。１つの格子点が原点として選択され、図１（ａ）において１つのリングで示される。更に、原点の周囲のボロノイ領域ＶΛ（０）が示される。変倍されたボロノイ領域rＶΛ（０）を図１（ｂ）に示す。この例においては、ｒ＝４である。尚、図１（ｂ）において、いくつかの格子点は４ＶΛ（０）の境界線上になる。このため、図１（ｃ）に示すように、変倍されたボロノイ領域は、ボロノイ領域ＶΛ（０）内にある変位ベクトルａにより移動される。その結果、変倍及び移動されたボロノイ領域４ＶΛ（０）＋ａが得られる。最後に、図１（ｄ）に示すように、ボロノイコードブックＣΛ（４，ａ）は、格子Λと変倍され変位したボロノイ領域４ＶΛ（０）＋ａとの交点を取得することにより形成される。尚、コードブック中の点は境界線上にはならない。
【００５２】
図２（ａ）〜図２（ｄ）は、六方格子Ａ2の同様のシーケンスを示す。他の高次元のボロノイコードブックに対して同一の原理が使用されてもよいことが理解される。
【００５３】
ボロノイコードブックＣΛ（ｒ，ａ）に属する点の総数はｒdであり、これは、コードブックがｌｏｇ2ｒビット／次元を有すると言うことと等価である。
【００５４】
本発明は、付録Ｉで説明する格子分割に基づく。格子ベクトルｙは、格子分割を使用して、式（４）に従ってｙを正の整数ｐで除算することにより商ベクトルｑ及び剰余ベクトルｒに分解されてもよい。
【００５５】
ｙ＝ｐｑ＋ｒ                              （４）
ここで、ｒ∈ＣΛ（ｐ，ａ）である。商ｑは、更なる商と剰余とに分解される可能性があるベクトルである。この手順は、更に小さな剰余を取得するために繰り返されてもよい。アルゴリズムは、以下の擬似コードにより要約されるかもしれない。
【００５６】
整数の集合ｐ1，ｐ2，……が全て正であり、且つ≧２であり、ベクトルの集合ａ1，ａ2，……∈ＶΛ（０）であると仮定すると、ｉ＝０，１，……、ｒi+1∈ＣΛ（ｐi+1，ａi+1）とすれば、ｙi＝ｐi+1ｙi+1＋ｒi+1である。
【００５７】
付録IIに示すように、このアルゴリズムはゼロか又は２ＶΛ（０）に含まれる別の格子点に常に収束する。アルゴリズムは、付録IIで説明される収束テストを使用することにより、以下のような擬似コードで実現されてもよい。
【００５８】
整数の集合ｐ1，ｐ2，……が全て正であり、且つ≧２であり、ベクトルの集合ａ1，ａ2，……∈ＶΛ（０）であると仮定すると、
for ｉ＝０，１，……、
ｙi＝ｐi+1ｙi+1＋ｒi+1 with ｒi+1∈ＣΛ（ｐi+1，ａi+1）、
if ｙiT＝０、or（ｐi+1＝２ and −ｙi∈Ｃ（２，ａi+1））、
stop、
endif
endfor
【００５９】
このアルゴリズムの埋め込みを示すフローチャートを図３に示す。アルゴリズムは、格子ベクトルｙ0を選択し、且つ指標ｉ＝０を設定することによりステップＳ１において開始する。ステップＳ２は以下の繰返しを実行する。
【００６０】
ｙi+1＝ＱΛ（ｙi−ａi+1）／ｐi+1）
ｒi+1＝ｙi−ｐi+1ｙi+1              （５）
【００６１】
ステップＳ３は、ｙi+1Tｙi+1＝０であるかどうかをテストする。この条件が成り立つ場合、アルゴリズムは収束し（付録IIを参照）、成り立たない場合、ステップＳ４に進む。ステップＳ４は、ｐi+1＝２、且つｒi+1＝−ｙiであるかどうかをテストする。この条件が成り立つ場合、アルゴリズムは収束し（付録IIを参照）、成り立たない場合、ステップＳ５に進む。ステップＳ５において、ｉは１増加され、その後ステップＳ２に戻る。収束に達する可能な方法が２つ存在するため（ステップＳ３及びステップＳ４）、最終的な符号化器の状態は符号ビットｂにより示されてもよい。符号ビットｂは、例えば、収束がステップＳ３において達成された場合は０に設定され、ステップＳ４において達成された場合は１に設定されてもよい。
【００６２】
図４は、図３の繰返しステップＳ２を示す図である。ボロノイ領域ＶΛ（０）内にある格子ベクトルｙi及びベクトルａi+1は、破線のベクトルｙi−ａi+1を形成する。このベクトルは、この例では２である整数ｐi+1により除算され、再度変倍されたベクトル（ｙi−ａi+1）／２を形成する。再度変倍されたベクトルは最も近接する格子点に量子化され、商ベクトルｙi+1を形成する。剰余ベクトルｒi+1は、この例ではｙi−２ｙi+1であるｙi−ｐi+1ｙi+1により形成される。剰余ｒi+1は、図４に示すようにこの例ではＣΛ（２，ａi+1）であるコードブックＣΛ（ｐi+1，ａi+1）に属する。この特徴は、実際の符号化に使用される。
【００６３】
次元ｄのベクトルｘの符号化は、最も近接する格子ベクトルｙ＝ＱΛ（ｘ）を選択することにより開始する。この格子ベクトルは、式（５）で定義される格子分割において初期ベクトルｙ0として使用される。各分割の結果、対応するボロノイコードブックＣΛ（ｐi，ａi）に属する剰余ｒiが得られる。ある特定の回数であるｋ回の繰返しの後、格子分割アルゴリズムが収束するため（付録II）、これは、格子ベクトルｙが式（６）に従って剰余ｒiの線形結合として表されてもよいことを意味する。
【００６４】
2009509456.tif 000007
【００６５】
式（６）は、ｋ回の繰返しに対してアルゴリズム（５）のループをアンロールすることにより取得される。ここで、λiは、剰余ベクトルｒiに対応する整数倍率、即ち、
【００６６】
2009509456.tif 000008
【００６７】
を表す。式（６）において、総和の第１項には以下の公式が使用される。
【００６８】
2009509456.tif 000009
【００６９】
付録IIIに示されるように、この手順により生成されたコードベクトルｒiは一意である。尚、レイヤは逆順になっている。復号化にとって最も重要な第１のレイヤは、最大の整数倍率λkを有するレイヤである。
【００７０】
図５は、格子Ｚ2に対するその処理を示す。図５（ａ）において、格子ベクトルｙ＝ｙ0は、整数ｐ1＝３により除算される格子である。その結果、ボロノイコードブックＣΛ（３，ａ）に属する商ベクトルｙ1及び剰余ベクトルｒ1が得られる（簡単にするために、この例において、ベクトルａが全てのコードブックにおいて使用される）。図５（ｂ）において、格子ベクトルｙ1は整数ｐ2＝２により除算される格子である。その結果、ボロノイコードブックＣΛ（２，ａ）に属する商ベクトルｙ2及び剰余ベクトルｒ2が得られる。図５（ｃ）において、格子ベクトルｙ2は、整数ｐ3＝２により除算される格子である。その結果、ボロノイコードブックＣΛ（２，ａ）に属する商ベクトルｙ3＝０及び剰余ベクトルｒ3＝ｙ2が得られる。ｙ3＝０であるため、図３の条件Ｓ３が満たされ、アルゴリズムは、ｋ＝３回の繰返しで収束した。図５（ｄ）に示されるように、この例に（６）を適用することにより、以下の式が得られる（基本レイヤｋ＝３で開始する）。
【００７１】
ｙ＝ｙ0＝ｐ1・ｐ2・ｒ3＋ｐ1ｒ2＋１・ｒ1＝３・２・ｒ3＋３・ｒ2＋ｒ1
【００７２】
コードベクトルｒ1，……ｒkの各々がボロノイコードブックに属するため、それらコードベクトルの指標は、非特許文献４において説明される周知のアルゴリズムを使用して、即ち、指標を導出することにより符号化されてもよい。
【００７３】
ｎi＝［Ｇ-1ｒi］ｍｏｄｐi，ｉ＝１……ｋ      （７）
ここで、Ｇは格子の生成行列であり、“ｍｏｄ”はモジュロ関数である。各指標ｎiは、符号化に対してｄｌｏｇ2（ｐi）ビットを必要とする。
【００７４】
指標ｎ1，……ｎk及びそれらの数ｋは、符号化器から復号化器に送信される主な符号化パラメータである。第１の（最上位）レイヤが指標ｉ＝ｋに対応するレイヤであり、最後の（最下位）レイヤが指標ｉ＝１に対応するレイヤであるため、レイヤ数の送信は重要である。更にレイヤ数は、ベクトルｙのエネルギーに関連するため、一種の利得形状符号化（gain-shape coding）と考えられる。
【００７５】
尚、格子分割アルゴリズムが停止された状態が送信される必要があることは重要である。図３を参照して説明されるように、この状態は、バイナリ変数ｂ＝０又はｂ＝１で表されてもよく、符号ビットと呼ばれる。復号化器において、符号ビットは、ｙk+1を表すコードベクトルの符号が変更される必要があることを示す。しかし、整数ｐi≧２のシーケンスが少なくとも１つのｐi＝２を含む場合にのみ、符号ビットが必要とされ、収束はステップＳ３ではなくステップＳ４を通して達成されてもよい。全てがｐi＞２であり、且つ復号化器においてそのことが認識されている場合、収束は常にステップＳ３を通して達成されるため、符号ビットは必要とされない。
【００７６】
変位ベクトルａ1，ａ2，……ａk及び各レイヤのビット割当てを制御するパラメータｐ1，……ｐkは、剰余ベクトルｒiを復号化し、且つベクトルｙを回復するのに必要とされる。しかし、それらは符号化器及び復号化器において前もって定められても良いし固定されてもよいため、送信される必要はない。一般に、パラメータｐ1，……ｐkは各レイヤの粒状度を表す。
【００７７】
各レイヤが同一ビット数を割り当てられるべきであると決定された場合、全てのｐiは等しい。この値は、変更されない場合には符号化器及び復号化器において固定されてもよく、変更される場合には１つの値のみが送信される必要がある。全てのレイヤがｄビットで符号化されるべきであると決定された場合、全てのｉに対してｐi＝２であり、ｐiは送信される必要がない。
【００７８】
上述したように、変位ベクトルａ1，ａ2，……ａkは、全てが原点の周囲のボロノイ領域に属するように選択される。それらは、格子点がｐiＶΛ（０）＋ａiの境界線上にならないように結び付きをなくすように選択される。更にそれらは、符号化器及び復号化器において事前に定められ、且つ固定されてもよい。それらベクトルの選択を最適化するために、各レイヤに関連する誤差を検査する必要がある。平均二乗誤差（ＭＳＥ）は以下の通りである。
【００７９】
2009509456.tif 000010
【００８０】
ここで、以下の式がコードの平均エネルギーに対応する。
【００８１】
2009509456.tif 000011
【００８２】
また、以下の式はボロノイコードブックＣΛ（ｐi, ａi）中のコードベクトルの平均を示す。
【００８３】
2009509456.tif 000012
ベクトルａ1，ａ2，……ａkの最適な選択は、誤差を可能な限り小さくすることである。ボロノイコードエネルギーの最適化に対する単純で一般的なアルゴリズムは、非特許文献４において説明され、この場合には各σi2を最適化するために使用される。
【００８４】
式（６）により示されるように、受信した量子化ベクトルｙは、以下のように復号化器において再構成される。
【００８５】
2009509456.tif 000013
【００８６】
指標ｎ1，……ｎkのコードベクトルｒ1，……ｒkへの復号化は、非特許文献４において説明される以下のアルゴリズムに従って実行される。
【００８７】
2009509456.tif 000014
【００８８】
ここで、Ｇは格子Λの生成行列である。
【００８９】
ここで、ｌ≦ｋ個のレイヤが欠けていると仮定すると、平均二乗誤差の最小化に関して最適な再構成は以下の式により与えられる。
【００９０】
2009509456.tif 000015
【００９１】
これは、欠けているコードベクトルｒi……ｒlがそれらの対応するコードブックの平均により置換されることを意味する（ｌ＝０の場合、即ち、全てのレイヤが受信された場合、式（１１）の右辺第１項の和はゼロであり、式（１１）は式（９）に単純化される）。
【００９２】
ここまで、平均二乗誤差は、コードベクトルｙの回復における誤差に対してのみ計算された。しかし、目標はベクトルｘの量子化であるため、欠けているレイヤによる誤差に加えて、量子化に関連する誤差を追加する必要がある。この誤差は、格子のボロノイ領域の形状に依存するが、ベクトルｘには依存せず、以下の式により与えられる。
【００９３】
2009509456.tif 000016
【００９４】
いくつかの周知の格子は、可能性として低次元の他の格子の組合せとして取得される。ここで提示される本発明は、それら格子に対しても同等に適用されることが明らかである。例えば、格子分割アルゴリズムの単純な変形により、各段階（レイヤ）において異なる格子に対処できる。
【００９５】
整数の集合ｐ1，ｐ2，……が全て正であり、且つ≧２であり、格子の集合Λ1，Λ2，……, ベクトルａ1，ａ2，……∈ＶΛ1（０），ＶΛ2（０），……であると仮定するなら、ｉ＝０，１，……として、ｒi+1∈ＶΛi（ｐi+1，ａi+1）なら、ｙi＝ｐi+1ｙi+1＋ｒi+1である。 
（５）をこの一般化に適応すると、以下の式が得られる。
【００９６】
ｙi+1＝ＱΛi（ｙi−ａi+1）／ｐi+1）
ｒi+1＝ｙi−ｐi+1ｙi+1              （１３）
ベクトルｒiは、以下のように符号化される。
【００９７】
ｎi＝［Ｇi-1-1ｒi］ｍｏｄｐi，ｉ＝１……ｋ          （１４）
ここで、Ｇi-1は格子Λi-1の生成行列である。
【００９８】
復号化器において、ベクトルｒiは受信指標ｎiから以下のように取得され、
【００９９】
2009509456.tif 000017
【０１００】
そして、再構成ベクトルｙは、全てのｋ個の指標（レイヤ）が受信された場合には（９）により取得され、いくつかの指標が切り捨てられた場合には（１１）により取得される。この場合、平均コードブックベクトルは以下の式により形成される。
【０１０１】
2009509456.tif 000018
【０１０２】
各格子Λiは、ｙi∈Λiとなるような格子である必要がある。しかし、その条件に当てはまらない場合、ｙiの平行移動と変倍との内の少なくともいずれかのようなある量の追加の副次的な情報が送信されるという条件で、ｙi∈Λiにすることができる。
【０１０３】
種々の格子を使用する利点は、それら格子が提供する融通性に加え、いくつかの格子が他の格子と比べてある特定の問題に適していることである。更に、種々の格子を使用することにより、１つの格子のみを使用することでは入手できないレート−歪み点を得ることができる（平均して、追加の各レイヤは量子化歪みの所定の減少量に対応する）。
【０１０４】
図６は、本発明のベクトル量子化方法を使用する符号化器の一実施例を示す。格子量子化器１０は、ベクトル量子化されるベクトルｘを受信する。格子量子化器１０は、記憶装置１２から取得される格子Λ0上の最も近接する格子点ｙ0にそのベクトルｘを量子化する（通常、格子点は格納された生成行列から取得される）。格子ベクトルｙ0は、格子量子化器１０に接続された格子ベクトル分解器１４に転送される。ここで、格子ベクトルｙ0は、記憶装置１２の格子のシーケンスΛ0，Λ1，……、変位ベクトルのシーケンスａ1，ａ2，……、及び正の整数のシーケンスｐ1，ｐ2，……を使用することにより、式（１３）において概略を示されるアルゴリズムに従って逐次改善される。最終的に、剰余ベクトルｒiはボロノイ格子符号化器１６に転送される。符号化器１６は、記憶装置１２から検索されるパラメータからコードブックを形成するボロノイコードブックビルダ１８の対応するボロノイコードブックＣΛi-1（ｐi，ａi） においてそれらベクトルを符号化する。対応するコードｎiは、式（１４）に従って形成される。この実施例において、それらコード及びそれらコードの数ｋは、復号化器に送出又は送信される（符号ビットｂは、使用されるシーケンスｐiに依存して要求されてもよい。上述を参照）。
【０１０５】
図７は、本発明の復号化方法を使用する復号化器の一実施例を示す。符号化パラメータｎi，ｋは、ボロノイ格子復号化器３０により受信され、復号化器３０は、式（１５）を使用して受信した指標ｎiを剰余ベクトルｒiに復号化する。生成行列Ｇi-1は、記憶装置３２から取得される。復号化ベクトルｒiは、ベクトル再構成ユニット３６に転送され、ベクトル再構成ユニット３６は、（１１）に従ってｌ≦ｋ個の剰余ベクトルｒiが欠けているという条件で近似値ｙを再構成する。再構成は２つのステップに分割される。第１のステップにおいて、（１１）の右辺第１項の和に従って部分的に再構成されたベクトルは、部分ベクトル再構成ユニット３６において形成される。第２のステップにおいて、（１１）の右辺第２項の和は、コードブック平均加算器３８において形成され、復号化ベクトルｙを形成するために右辺第１項の和に加算される。
【０１０６】
通常、説明した実施例の種々のブロックの機能性は、１つ以上のマイクロプロセッサ又はマイクロ／信号プロセッサの組合せ及び対応するソフトウェアにより達成される。
【０１０７】
通常、説明した実施例の種々のブロックの機能性は、１つ以上のマイクロプロセッサ又はマイクロ／信号プロセッサの組合せ及び対応するソフトウェアにより達成される。別の可能性は、ＡＳＩＣ（特定用途向け集積回路）又はＦＰＧＡ（フィールドプログラマブルゲートアレイ）として本発明を実現することである。
【０１０８】
各レイヤ指標ｎiの可逆符号化が上述の階層化符号化方式を更に効率的にできることは明らかである。ハフマン符号化又は算術符号化等の典型的な技術は、このタスクに特に適切である。
【０１０９】
ベクトルｘが格子点ｙ∈Λに量子化される場合、ベクトルｘのエネルギーが高くなると、符号化に必要とされる総ビット数は多くなる。全てのレイヤが受信される場合、ソースベクトルｘを事前に変倍することは、最終的なＭＳＥ（平均二乗誤差）に直接影響を及ぼす。ソースベクトルが上向きに変倍される場合、最終的なＭＳＥは減少し、ソースベクトルが下向きに変倍される場合、最終的なＭＳＥは増加する。しかし、高エネルギーのソースベクトルの場合、量子化ベクトルｙを表すのに必要とされる総ビット数は増加する。一般にこれは、応用例に依存する妥協点である。例えば、オーディオ符号化の場合、最終的なＭＳＥがマスクノイズ閾値に対応するため、全てのレイヤが受信される場合に透過的な符号化を行なうということが必要とされる場合がある。ソースベクトルが上向きに変倍される場合、最終的なＭＳＥは減少し、ソースベクトルが下向きに変倍される場合、最終的なＭＳＥは増加する。しかし、高エネルギーのソースベクトルの場合、量子化ベクトルｙを表すのに必要とされる総ビット数は増加する。一般にこれは、応用例に依存する妥協点である。例えば、オーディオ符号化の応用例において、マスキング閾値は、信号の音響心理解析の実行後に周波数領域において得られる。それらマスキング閾値は、人間の耳で認識可能な符号化ノイズのレベルを判定する。透過的な不可逆符号化の目的は、符号化ノイズレベルが認識可能なノイズレベルを下回るようにスペクトル係数を符号化することである。これは、認識可能なノイズレベルに合致する最終的な平均二乗誤差を導くスペクトル係数の適切な変倍（scaling）を選択することにより、全てのレイヤが受信される場合に透過的な符号化を行なうことであると言い換えられる。
【０１１０】
先に示されたように、本発明の基本概念は、可変レート格子ベクトルの量子化に関する。特に、本発明の概念は、ボロノイコードを使用することにより融通性をもって逐次改善可能にソースベクトルを符号化するために格子分割アルゴリズムを使用することである。各改善されたレイヤは、ある特定のボロノイコードブックに属するコードベクトルから構成される。各改善されたレイヤの大きさの選択は、各レイヤの各改善されたボロノイコードブックが動的に変化する大きさを有するように常に選択されてもよく、且つ異なる格子から得られてもよいという点で融通性がある。
【０１１１】
ボロノイコードブックの集合のエントリに対応する指標の集合を最適に復号化する方法を示した。ここで、各指標は既に符号化された指標を更に改善する。
【０１１２】
本発明は、いくつかの利点を有する。その一部は以下の通りである。即ち、
・複雑さが小さいこと、
・必要とされるメモリが少ないこと、
・実行中に指標付けすること、
・説明された方式により、量子化ソースベクトルｘの階層化表現の形成が可能になり、それにより復号化器は、送信情報の一部が復号化器に到達しない場合にソースベクトルの低品質バージョンを回復できること、
・階層化表現は、コードブックを再設計する必要なく又はテーブルを指標付けする必要なく常に変更可能であり、これにより符号化器は、要望に応じて特定の階層化構成を効率的に構成できること、
・格子の変倍と過負荷との内、少なくともいずれかの問題を軽減することである。
【０１１３】
添付の請求の範囲により定義される本発明の範囲から逸脱せずに、種々の変形及び変更が本発明に対して行なわれてもよいことが当業者には理解されるだろう。
【０１１４】
付  録  Ｉ
この付録においては、格子分割について、すなわち格子ベクトルを整数で除算することについて説明する。コンウェイ及びスローアンにおいて説明されるように、その技術の有用性は、最も近接するものを算出する高速アルゴリズムの存在に基づく。
【０１１５】
次元ｄの任意のベクトルｘに対して、ｙ＝ＱΛ（ｘ）は格子Λのｘの最も近接するものを示す。ベクトルｙ∈Λ及びボロノイコードブックＣΛ（ｐ，ａ）を考慮し、以下の式を仮定する：
ｑ＝ＱΛ（ｙ−ａ）／ｐ                              （１７）
これは、ｙ−ａ＝ｐｑ＋ｐεであることを意味し、εはボロノイ領域ＶΛ（０）に属する。
【０１１６】
これは、以下と同等である。
【０１１７】
ｙ＝ｐｑ＋ａ＋ｐε                                        （１８）
【０１１８】
ここで、ｙ及びｑの双方が格子Λに属し、且つｐが整数であるため、ａ＋ｐεは格子点となる必要があり、ε∈ＶΛ（０）であるため、ｒ＝ａ＋ｐε∈ＣΛ（ｐ，ａ）を有する必要がある。従って、以下の式が得られる。
ｙ＝ｐｑ＋ｒ、ただし、ｒ∈ＣΛ（ｐ，ａ）          （１９）
【０１１９】
このベクトルｙを分解する方法は、ユークリッド除法に類似しており、格子が次元ｄ＝１の格子である場合にはユークリッド除法と同等である。ｑを整数ｐによるｙの除算の商と呼び、ｒを剰余と呼ぶ。しかし、ｄ＞１の場合、ｑ及びｒの双方はベクトルである。
【０１２０】
ベクトルａを考慮すると、その機能は結び付きをなくすことであるが、通常、コードエネルギーが可能な限り小さくなるように最適化される。もし、
2009509456.tif 000019
の場合、単純な平行移動により、ａがＶΛ（０）に属するベクトル及び格子点の和であると書ける。従って、格子点は結果として平行移動されたボロノイコードとなり、ベクトルが原点０の周囲のボロノイ領域内になること、即ち、ａ∈ＶΛ（０）であることが一般性を失わずに仮定される。
【０１２１】
以下の段落において、格子分割の領域特性を考察する。
【０１２２】
ベクトルｙ∈Λと仮定し、ａ∈ＶΛ（０）とする。ｙ∈ＣΛ（ｋ，ａ）となるような全ての正の整数ｋの集合は、ｙ∈ＣΛ（ｎ，ａ）となるような可能な最小の正の整数ｎだけ低く制限される。ｎをｙの次数と呼び、ｎはｄｅｇa（ｙ）により示される。
【０１２３】
（１９）に従う格子分割を使用することにより、ｒ∈ＣΛ（ｐ，ａ）の時、ベクトルｙ∈Λはｙ＝ｐｑ＋ｒと表される。これは、ｄｅｇa（ｙ）がｐ以下である必要があることを示す。ここで、定義ｙ∈ＣΛ（ｄｅｇa'（ｙ），ａ’）により、ａ’∈ＶΛ（０）とする。ｙ−ｒがＣΛ（ｄｅｇa'（ｙ）＋ｐ，ａ’＋ａ）に属することが示されるため、以下のことを示すことができる。
【０１２４】
2009509456.tif 000020
【０１２５】
ここで、ｐ＝１の場合、すぐにｒ＝０及びｑ＝ｙとなるため、ｄｅｇa'（ｑ）＝ｄｅｇa'（ｙ）となる。次に、ｐ≧２と仮定する。ａ及びａ’がＶΛ（０）に属するため、ａ’＋ａ∈２ＶΛ（０）及びｂ＝（ａ＋ａ’）／ｐ∈（２／ｐ）ＶΛ（０）⊂ＶΛ（０）となる。従って、以下の式が得られる。
【０１２６】
2009509456.tif 000021
【０１２７】
これにより、全ての正の整数ｐ及び任意の格子ベクトルに対して、商ベクトルｑの次数は以下を満足する必要がある。
【０１２８】
2009509456.tif 000022
【０１２９】
付  録  II
初期ベクトルｙ0∈Λから開始する格子分割アルゴリズムは、正の整数の集合による先行する格子分割の商に対して連続する格子分割を適用する。ｐi＝１である任意のステップにより結果が変更されないため、整数ｐiが少なくとも２に等しいという仮定が必要とされる。
【０１３０】
適切に選択されたベクトルｂ1，ｂ2，……∈ＶΛ（０）の時にｍi＝ｄｅｇbi（ｙi）と書く場合、アルゴリズムの繰返しにより以下が得られる。
【０１３１】
2009509456.tif 000023
【０１３２】
仮定によりｐi≧２であるため、次数展開の上限境界が得られる。
【０１３３】
2009509456.tif 000024
【０１３４】
ここで、以下のことが示される。
【０１３５】
2009509456.tif 000025
【０１３６】
ｋがｍ0を表すのに使用されるビット数である場合、ｉ＞ｋに対してｍi≦２、即ち、あるｂiに対してｙi∈ＣΛ（２，ｂi）であることが必要である。これは、分割アルゴリズムがボロノイコードに属する点ｙi∈ＣΛ（２，ｂi）、ｉ＞ｋを常に導くことを示す。
【０１３７】
任意のｐi，ｉ＞ｋが厳密に２より大きい場合、アルゴリズムは一意のコードベクトルとして原点０を有するコードブックＣΛ（１，ｂi）に収束する。
【０１３８】
全てのｐiが、ｐi＝２，ｉ＞ｋである場合、アルゴリズムはｙk+1＝２ｙk+2＋ｒk+2を導く。ｙk+1∈Ｃ（２，ａk+2）の場合、必ずｙk+2＝０となり、アルゴリズムは収束する。さもなければ、
2009509456.tif 000026
【０１３９】
の場合、−ｙk+1∈Ｃ（２，ａk+2）を有する必要があり、すぐにｙk+2＝ｙk+1及びｒk+2＝−ｙk+1となり、アルゴリズムは収束する。
【０１４０】
このように、アルゴリズムはゼロか又は２ＶΛ（０）に含まれる別の格子点に常に収束する。
【０１４１】
付  録  III
生じる可能性のある疑問は、生成されたコードが一意であるかということである。この疑問に解答するために、以下のアルゴリズムを２回繰返すことを考慮する。
【０１４２】
ｙi＝ｐi+1ｙi+1＋ｒi+1、及び
ｙi+1＝ｐi+2ｙi+2＋ｒi+2  （２６）
【０１４３】
次に以下の式が書ける。
【０１４４】
2009509456.tif 000027
【０１４５】
式（２７）は、
2009509456.tif 000028
がボロノイコードである場合、アルゴリズムの２回の繰返しがｐi+1、ｐi+2の積である整数
2009509456.tif 000029
による１回の繰返しと等しいことを示す。しかし、一般にこれは当てはまらず、
2009509456.tif 000030
であることのみを示すことができるに過ぎない。しかし、これは境界コードのみであり、
2009509456.tif 000031
の全てのコードベクトルが使用されることはない。
【０１４６】
次に、コードベクトル
2009509456.tif 000032
と対（ｒi+1, ｒi+2）との間の１対１のマッピングがあることを示す。実際には、
2009509456.tif 000033
を有し、ｒi+1∈ＣΛ（ｐi+1, ａi+1）と仮定すると、ｒi+2は一意に判定されるためｒi+1である。
【０１４７】
１対１のマッピングが存在するということは、２つの（ｒi+1, ｒi+2）が同一の
2009509456.tif 000034
を導かず、従って生成されたコードが一意であり、且つその点で効率的であることを意味するため重要である。
2009509456.tif 000035
が必ずしもボロノイコードではないということにより、平均の平均二乗誤差に関して非効率的になるが、これは階層化符号化を有するために払われる周知の代償である。
【図面の簡単な説明】
【０１４８】
【図１】整数格子Ｚ2のボロノイコードブックの概念を示す図である。
【図２】六方格子Ａ2のボロノイコードブックの概念を示す図である。
【図３】本発明に従ってベクトル量子化方法の一実施例を示すフローチャートである。
【図４】図３のベクトル量子化方法の１回の繰返しを示す図である。
【図５】図３の方法に基づくベクトル量子化の一例を示す図である。
【図６】本発明のベクトル量子化方法を使用する符号化器の一実施例を示す図である。
【図７】本発明の復号化方法を使用する復号化器の一実施例を示す図である。
【図１】
2009509456.tif 000041
【図２】
2009509456.tif 000042
【図３】
2009509456.tif 000043
【図４】
2009509456.tif 000044
【図５】
2009509456.tif 000045
【図６】
2009509456.tif 000046
【図７】
2009509456.tif 000047
【手続補正書】
【提出日】平成19年7月2日(2007.7.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
格子Λ0に属する格子ベクトルによりベクトルｘを近似する工程と、
ｉ＝１……ｋであり、且つｋが整数ｐi≧２の各シーケンス中の要素数を表す正の整数である場合、対応する所定のシーケンスからの整数による格子分割により、連続する格子Λi-1上において前記格子ベクトルを商ベクトルｙiのシーケンス及び剰余ベクトルｒiのシーケンスに逐次分解する工程とを有し、
連続する各分解は、
ｙi＝ＱΛi（ｙi−ａi+1）／ｐi+1
ｒi+1＝ｙi−ｐi+1ｙi+1
に従って取得され、ＱΛi（ｙi−ａi+1）／ｐi+1は格子Λiへのベクトル（ｙi−ａi+1）／ｐi+1の量子化を示し、
ａiが格子Λi-1のボロノイ領域ＶΛi-1（０）に属する結びつきを解く所定の変位ベクトルであることを特徴とするベクトル量子化方法。
【請求項２】
全ての格子Λiが同一の格子Λであることを特徴とする請求項１に記載のベクトル量子化方法。
【請求項３】
請求項１又は２に記載のベクトル量子化方法に従ってベクトルｘを量子化する工程と、
対応するボロノイコードブックＶΛi-1（ｐi，ａi）中の各剰余ベクトルｒiを符号化する工程と、
前記符号化された剰余ベクトルｒi、そのような剰余ベクトルｒiの数ｋ、及び前記ボロノイコードブックＶΛi-1（ｐi，ａi）を規定する前記整数ｐi及び前記変位ベクトルａiの前記シーケンスを含むパラメータの集合により前記ベクトルｘを表す工程とを有することを特徴とする符号化方法。
【請求項４】
Ｇi-1が格子Λi-1の生成行列である場合、
ｎi＝［Ｇi-1-1ｒi］ｍｏｄｐi, ｉ＝１……ｋ
のように前記剰余ベクトルｒiを符号化する工程を含むことを特徴とする請求項３に記載の符号化方法。
【請求項５】
前記符号化された剰余ベクトルｒi及びそのような剰余ベクトルｒiの前記数ｋを復号化器に転送する工程を含むことを特徴とする請求項４に記載の符号化方法。
【請求項６】
最後の剰余ベクトルｒkの符号を表す符合ビットｂを前記復号化器に転送する工程を含むことを特徴とする請求項５に記載の符号化方法。
【請求項７】
請求項３に記載の符号化方法に従って符号化されるベクトルｘを表す符号化パラメータを受信する工程と、
2009509456.tif 000048
に従って、前記ベクトルｘの近似値ｙを再構成する工程とを有し、
ｌ≦ｋは欠けている符号化剰余ベクトルの数を表す正の整数であり、
2009509456.tif 000049
は対応するボロノイコードブックの平均ベクトルであることを特徴とする復号化方法。
【請求項８】
符号化された剰余ベクトルｒiと、そのような剰余ベクトルｒiの数ｋのみを受信し、受信側において記憶装置から前記整数ｐi及び前記変位ベクトルａiの集合を検索する工程を含むことを特徴とする請求項７に記載の記載の復号化方法。
【請求項９】
格子Λ0に属する格子ベクトルによりベクトルｘを近似する格子量子化器（１０）と、
ｉ＝１……ｋであり、且つｋが整数ｐi≧２の各シーケンス中の要素数を表す正の整数である場合、対応する所定のシーケンスからの整数による格子分割により、連続する格子Λi-1上において前記格子ベクトルを商ベクトルｙiのシーケンス及び剰余ベクトルｒiのシーケンスに逐次分解する前記格子量子化器に接続される格子ベクトル分解器（１４）とを有し、
連続する各分解は、
ｙi＝ＱΛi（ｙi−ａi+1）／ｐi+1
ｒi+1＝ｙi−ｐi+1ｙi+1
に従って取得され、ＱΛi（ｙi−ａi+1）／ｐi+1は格子Λiへのベクトル（ｙi−ａi+1）／ｐi+1の量子化を示し、
ａiが格子Λi-1のボロノイ領域ＶΛi-1（０）に属する結びつきを解く所定の変位ベクトルであることを特徴とするベクトル量子化器。
【請求項１０】
請求項９に記載のベクトル量子化器と、
対応するボロノイコードブック中の各剰余ベクトルｒiを符号化する前記ベクトル量子化器に接続されるボロノイ格子符号化器（１４）とを有することを特徴とする符号化器。
【請求項１１】
Ｇi-1が格子Λi-1の生成行列である場合、
ｎi＝［Ｇi-1-1ｒi］ｍｏｄｐi，ｉ＝１……ｋ
のように前記剰余ベクトルｒiを符号化するボロノイ格子符号化器（１４）を含むことを特徴とする請求項１０に記載の符号化器。
【請求項１２】
2009509456.tif 000050
のように、請求項９乃至１１のいずれか１項に記載の符号化器により符号化される受信符号化パラメータにより表されるベクトルｘの近似値ｙを再構成するベクトル再構成ユニット（３６）とを有し、
ｌ≦ｋは欠けている符号化剰余ベクトルの数を表す正の整数であり、
2009509456.tif 000051
は対応するボロノイコードブックの平均ベクトルであることを特徴とする復号化器。
【国際調査報告】
2009509456.tif 000052
2009509456.tif 000053
2009509456.tif 000054
2009509456.tif 000055