(57)【要約】本発明は、例えば、ティジタル伝送や記憶システムで使用される、送信信号からの１フレームを表す送信元ベクトルｘのマルチレートの格子ベクトル量子化のための方法とシステムに関する。マルチレートの格子量子化符号化方法には、格子点ｙをｘに無制限の格子Λ内で関連付ける段階と、ｙが格子Λから抽出された基本符号帳Ｃの中に含まれるかどうかを検証する段階と、もし含まれるならば、量子化指数を作り出すようにＣの中でｙを索引付けし、もし含まれないならば、基本符号帳を例えばボロノイを基にした拡張方法を用いて拡張し、拡張済み符号帳を作り出す段階と、拡張済み符号帳から符号ベクトルｃをｙに関連付ける段階と、ｙを拡張済み符号帳Ｃの中で索引付けする段階とを備える。拡張手法によって、従来技術による量子化方法とシステムに比して、基本符号帳から、より速いビットレートの符号帳を得ることができる。
2005528839.tif 000002
【特許請求の範囲】
【請求項１】
マルチレートの格子量子化符号化方法において、前記方法は、
ｉ）送信信号からの１フレームを表すソースベクトルｘを提供する段階と、
ii）格子Λから抽出した基本符号帳Ｃを提供する段階と、
iii）前記格子Λ内の格子点ｙをｘに関連付ける段階と、
iv）もしｙが前記基本符号帳Ｃに含まれるならば、前記基本符号帳Ｃ内でｙを索引付けすることで、量子化指数を作り出し、本方法を終了する段階とを備え、
もし含まれなければ、
v）基本符号帳を拡張し、拡張符号帳を作り出す段階と、
vi）前記拡張符号帳から符号ベクトルｃをｙに関連付ける段階と、
vii）前記拡張符号帳内でｙに索引付けをして、量子化指数を作り出す段階と
を備えることを特徴とする方法。
【請求項２】
前記拡張符号帳は、ｍＣ＋Ｖの式で表され、ここでＣは前記基本符号帳であり、Ｖは前記格子Λ内の点の適切な組であることを特徴とする請求項１記載の方法。
【請求項３】
前記段階iii）において、前記格子Λ内の前記格子点ｙは、前記格子Λ内のｘの最近接の隣点として選択されることを特徴とする請求項１記載の方法。
【請求項４】
前記段階v）には、整数の拡大係数ｍ＞＝２を提供する段階が含まれ、前記段階vi）には、ｍを用いて格子点ｙに対応するボロノイ符号ベクトルｖを計算し、オフセットを提供する段階が含まれ、前記段階vi）には、ｖとｍとを用いて前記符号ベクトルｃを計算する段階が含まれることを特徴とする請求項１記載の方法。
【請求項５】
前記段階v）において、前記拡大係数ｍは２ｒに設定され、前記段階v）には、ボロノイ指数ｋを計算する段階がさらに含まれ、前記段階vi）には、ｋとｍとを用いて前記格子点ｙに対応するボロノイ符号ベクトルｖを計算する段階が含まれることを特徴とする請求項４記載の方法。
【請求項６】
前記段階vi）において、前記符号ベクトルｃは、ｃ＝（ｙ−ｖ）／ｍとして計算され、ここでｍは２と等しいか、２より大きい整数であることを特徴とする請求項４記載の方法。
【請求項７】
前記段階vi）には、さらに、ｃが前記基本符号帳Ｃの中にあるかどうかを検証し、もしＣの中にあれば、
ａ）前記段階vii）は、さらに、ｙを基本符号ベクトルとして索引付けし、ｊとｋを多重化して量子化指数を作り出す段階を備え、ここで、ｊは基本符号帳Ｃの中のｃの指数であり、ｋは、ベクトルｖに対応するボロノイ指数であり、
もしＣの中に無ければ、
ｂ）前記ボロノイ拡張の前記係数と前記次数を増加させ、前記段階v）からvi）を繰り返す段階を備える
ことを特徴とする請求項４記載の方法。
【請求項８】
前記段階vii）において、さらに、前記基本符号帳の中の符号ベクトルｙの前記次数ｒと係数ｉとに対応する符号帳番号の無損失符号化を定義し、符号化済みの符号帳番号ｎＥと符号化済み指数ｉＥとを作り出し、ｎＥとｉＥを多重化する段階を備えることを特徴とする請求項４記載の方法。
【請求項９】
さらに、vii）前記量子化指数を記憶手段に記憶する段階を備えることを特徴とする請求項１記載の方法。
【請求項１０】
さらに、vii）通信チャネルを渡って、前記量子化指数を送信する段階を備えることを特徴とする請求項１記載の方法。
【請求項１１】
マルチレートの格子量子化符号化方法において、前記方法は、
送信信号からの１フレームを表すソースベクトルｘを提供する段階と、
点の無限格子Ｌの有限部分集合ＣとＶを提供する段階と、
ｘを前記格子Ｌ内の前記点の一つであるｙと関連付ける段階と、
ｙを整数の符号帳番号ｎと指数ｉとに、ｙ＝ｍｃ＋ｖと索引付けする段階と
を備え、ここで、ｃはＣの一要素であり、ｖはＶの一要素であり、ｍは２に等しいか２より大きい整数であり、前記格子Ｌの部分集合ＣとＶ、およびｍの値とｉの大きさは、ｎから一意的に定義されることを特徴とする方法。
【請求項１２】
ｎは単一要素からなる符号で表されることを特徴とする請求項１１記載の方法。
【請求項１３】
前記無限格子Ｌの部分集合Ｖはボロノイ符号帳であり、前記ｖの指数はボロノイ指数であることを特徴とする請求項１１記載の方法。
【請求項１４】
前記指数ｉは、ｃの指数とｖの指数との結合であることを特徴とする請求項１１記載の方法。
【請求項１５】
本方法を実施する際に使用可能な割り当てられたビット数が、前記無限格子Ｌの中の前記送信元ベクトルｘを表すのに十分でない時に、ｙ＝［０…０］であり、ｎは所定の値に設定されることを特徴とする請求項１１記載の方法。
【請求項１６】
ｍ＝２ｒであり、前記部分集合Ｃは予め定められており、前記符号帳番号ｎは、ｒに所定の整数を足したものに等しく、ｒは１に等しいか１より大きな整数であることを特徴とする請求項１１記載の方法。
【請求項１７】
マルチレートの格子量子化符号化方法において、前記方法は、
i）送信信号からの１フレームを表す８次元の送信元ベクトルｘを提供する段階と、
ii）ＲＥ８格子から抽出した低レートの格子基本符号帳Ｑ０とＱ２とＱ３とＱ４を提供する段階と、
iii）前記格子ＲＥ８内のｘの最近接の隣点である、前記格子ＲＥ８内の格子点ｙを決定する段階と、
iv）ｚが０或いは２或いは３或いは４に等しい時、もしｙがＱｚに含まれるならば、ａ）番号ｚと、Ｑｚを定義する絶対先導部の一つを識別する識別子ｋａを記憶し、ｂ）もしｚ＞０ならば、ｂ１）量子化指数を作り出すＱｚの中でｙを索引付けし、もしｍ＝０ならば、ｂ２）ｙがゼロベクトルとして出力され、ｃ）本方法を終了する段階と、
v）拡張次数ｒを提供し、拡大係数ｍを２ｒに設定する段階と、
vi）繰り返し回数iter＝０に設定する段階と、
vii）格子点ｙのボロノイ指数ｋを計算する段階と、
viii）前記格子点ｙに対応するボロノイ符号ベクトルｖをｋとｍを用いて計算する段階と、
ix）符号ベクトルｃをｃ＝（ｙ−ｖ）／ｍと計算する段階と、
x）ｚが０或いは２或いは３或いは４に等しい時、もしｃがＱｚに含まれるならば、
aa）ｚとｋａを提供し、もしｎ＝２ならばｎ＝３と設定し、ｎを２ｒだけ増加させ、ｋとｃとｚとｋａの値を記憶し、ｍを２で除算し、１からｒを減少させ、もし、ｎ＝２でない時は、
bb）ｍを２で乗算し、ｒを１だけ増加させる段階と、
xi）前記繰り返し回数を１だけ増加させる段階と、
xii）もし前記繰り返し回数＝２ならば、
aaa）前記ｋとｃとｚとｋａの値を読み出し、ｋａの時にＱ３あるいはＱ４の中でｃのｊを索引付けし、ｊとｋを多重化して指数ｉを作り、ここでｌは符号ベクトルｙの指数であり、ｊはｃの指数であり、もし、繰り返し回数＝２でなければ、
bbb）前記段階vii）からxii）を繰り返す段階と
を備えることを特徴とする方法。
【請求項１８】
前記段階vii）において、ｋは次の式で計算され、
【数１】
2005528839.tif 000015
ここで、ＧＲＥ８は、次の式で定義される生成器行列であり、
【数２】
2005528839.tif 000016
ここで、ｍｏｄｍ（・）は、成分に対するモジュロｍの演算であることを特徴とする請求項１７記載の方法。
【請求項１９】
さらに、前記段階iii）の前に、前記送信元ベクトルｘをｘ／ｇと縮小する段階を備え、ここで、ｇは、１より大きく、本方法を実施する際に使用されるメモリ内で超過しないように選ばれることを特徴とする請求項１７記載の方法。
【請求項２０】
マルチレートの格子量子化復号方法において、
i）格子Λから抽出した基本符号帳Ｃを提供する段階と、
ii）符号帳番号ｎと量子化指数ｉを提供する段階と、
iii）前記符号帳番号ｎを用いて前記量子化指数ｉを逆多重化する段階と、
iv）もしｎ＝０ならば、前記基本符号帳を用いて前記指数ｉを復号し、量子化したベクトルｙを作り出し、本方法を終了する段階と、
v）もしｎ＞０ならば、
ａ）予め選択されたボロノイ符号帳Ｖ（ｒ）を提供する段階と、
ｂ）拡張次数をｒ＝ｎに、また拡大係数をｍ＝２ｒに設定する段階と、
ｃ）指数ｊとｋとをｉから逆多重化する段階と、
ｄ）ｊを前記基本符号帳Ｃ内のｃへ復号する段階と、
ｅ）ｋを前記ボロノイ符号帳Ｖ（ｒ）内のｖへ復号する段階と、
ｆ）量子化ベクトルをｙ＝ｍｃ＋ｖと再構成する段階と
を備えることを特徴とする復号方法。
【請求項２１】
前記段階ii）において、符号化済み符号帳番号ｎＥと、符号化済み指数ｉＥが最初に提供され、その後に、予め定められた無損失符号化手法が前記符号化済み符号帳番号ｎＥに適用され、前記符号帳番号ｎと前記量子化指数ｉとを得ることを特徴とする請求項２１記載の方法。
【請求項２２】
前記符号帳番号ｎと前記指数ｉとは、通信チャネルから読み出されることを特徴とする請求項２０記載の復号方法。
【請求項２３】
前記符号帳番号ｎと前記指数ｉとは、記憶手段から読み出されることを特徴とする請求項２０記載の復号方法。
【請求項２４】
マルチレートの格子量子化復号方法において、
点の無限格子Ｌの有限部分集合ＣとＶを提供する段階と、
符号帳番号ｎと指数ｉとを提供する段階と、
ｎとｉとを用いて格子Ｌ内のベクトルｙをｙ＝ｍｃ＋ｖと再構成する段階と
を備え、
ここで、ｍは２に等しいか２より大きい整数であり、ｃとｖはＬに含まれる点であり、前記点ｃはＬの有限部分集合Ｃの一要素として再構成され、前記点ｖはＬの有限部分集合Ｖの一要素として再構成され、ｖの指数とｃの指数はｉを用いて計算され、格子Ｌの前記部分集合ＣとＶ、およびｍの値、およびｉの大きさは、ｎから一意的に定義されることを特徴とする方法。
【請求項２５】
ｎは単一要素からなる符号から再構成されることを特徴とする請求項２０記載の方法。
【請求項２６】
Ｌの前記部分集合Ｖは、ボロノイ符号であり、ｖの前記指数は、ボロノイ指数であることを特徴とする請求項２０記載の方法。
【請求項２７】
マルチレートの格子量子化復号方法において、
ＲＥ８格子から抽出した低レート格子基本符号帳Ｑ０とＱ２とＱ３とＱ４を提供する段階と、
符号帳番号ｎと指数ｉとを提供する段階と、
もしｎ＝０ならば、ｙをゼロベクトルとして再構成する段階と、
もし０＜ｎ≦４ならば、符号ベクトル指数ｉを逆多重化し、ｉを基本符号帳Ｑ０とＱ２とＱ３とＱ４の指数として復号する段階と、
もしｎ＞４ならば、前記符号ベクトル指数ｉを基本符号帳指数ｊとボロノイ指数ｋとにｉから逆多重化し、拡張次数ｒと拡大係数ｍとをｎから提供し、ｎを用いてＱ３あるいはＱ４のいずれかを識別して前記指数ｊを復号し、ｙ＝ｍｃ＋ｖを計算する段階を備え、
ここで、ｍ＝２ｒは拡張拡大係数であり、ｃは前記基本符号帳の符号ベクトルであり、ｖはボロノイ符号帳の符号ベクトルであることを特徴とする方法。
【請求項２８】
格子符号帳拡張のための方法において、
i）ベクトルの格子Ｌからベクトルの部分集合を提供し、基本符号帳を作り出す段階と、
ii）前記基本符号帳を、予め定めた拡大係数で拡大し、拡大した符号ベクトルを作り出す段階と、
iii）拡大した各符号ベクトルの周囲にボロノイ符号帳を挿入し、拡大した符号帳を作り出す段階と
を備えることを特徴とする方法。
【請求項２９】
ベクトルの前記部分集合は、ベクトルを境界内部に保持することによって選択されることを特徴とする請求項２８記載の方法。
【請求項３０】
前記段階ii）には、整数の拡大係数ｍ＞＝２を提供する段階が含まれることを特徴とする請求項２８記載の方法。
【請求項３１】
前記段階ii）では、前記拡大係数ｍが２ｒに設定されることを特徴とする請求項２８記載の方法。
【請求項３２】
ベクトルの前記部分集合は、ベクトルを境界内に保持することで選択されることを特徴とする請求項２８記載の方法。
【請求項３３】
送信元ベクトルｘの格子ベクトル量子化のための方法において、
i）次元Ｎのベクトルの格子からベクトルの部分集合を提供し、索引付けのために、Ｒを前記基本符号帳の次元当たりのビットレートとすると、ＮＲビットを要する基本符号帳を作り出す段階と、
ii）ベクトルの前記格子内のｘに最近接のベクトルｙを決定する段階と、
iii）もし、前記最近接のベクトルｙが前記符号帳の内部に備わっていれば、量子化指数を作り出す前記符号帳内のｙを索引付けし、前記量子化指数を出力し、本方法を終了する段階と、
もし、前記最近接のベクトルｙが前記符号帳の内部に備わっていなければ、
iv）予め定められた拡大率を提供する段階と、
v）前記基本符号帳を前記拡大率で拡大し、拡大された符号ベクトルを含んだ拡大済み符号帳を作り出す段階と、
vi）前記拡大済み符号ベクトルの周囲にボロノイ符号帳を挿入し、ｒを前記ボロノイ符号帳の次数とすると、索引付けのためにＮ（Ｒ＋ｒ）ビットを要する拡張符号帳を作り出す段階と、
vii）もし最近接の隣点ｙが前記拡張済み符号帳内に備わっていれば、量子化指数を作り出す前記拡張済み符号帳内でｙを索引付けし、前記量子化済み指数を出力し、本方法を終了する段階と、
もし最近接の隣点ｙが前記拡張済み符号帳内に備わっていなければ、
viii）もし前記拡大済み符号帳を索引付けするのに要するビット数が、予め定めた閾値を超えなければ、前記拡大率と前記ボロノイ符号帳の前記次数とを増加させ、前記段階v）からviii）を繰り返し、もしそうでなければ、前記最近接の隣点は遠隔の外れ値であると判断して、予め定めた対応する量子化指数を出力する段階と
を備えることを特徴とする方法。
【請求項３４】
前記iv）において、前記予め定めた拡大係数は２であり、前記viii）において、前記拡大係数は２だけ増加されることを特徴とする請求項３３記載の方法。
【請求項３５】
前記段階viii）において、前記ボロノイ符号帳の前記次数は１だけ増加されることを特徴とする請求項３３記載の方法。
【請求項３６】
マルチレートの格子量子化符号化器において、
送信信号から一つのフレームを表す送信ベクトルｘを提供するための受信手段と、
格子Λから抽出した基本符号帳Ｃを含む記憶手段と、
格子Λ内の格子点ｙをｘに関連付ける手段と、
ｙが前記基本符号帳Ｃ内に含まれることを確認して、基本符号帳Ｃ内でｙを符号付けし、量子化指数を作り出すための手段と、
前記基本符号帳を拡張して、拡張符号帳を作り出すための手段と、
前記拡張符号帳から符号ベクトルｃをｙに関連付けるための手段と、
拡張符号帳Ｃ内でｙを符号付けして、量子化指数を作り出すための手段と
を備えることを特徴とする符号化器。
【請求項３７】
マルチレートの格子量子化符号化器において、
送信信号から１つのフレームを表す送信元ベクトルｘを受信するための手段と、
点の無限格子Ｌの有限部分集合ＣとＶとを提供するための手段と、
ｘを前記格子Ｌ内の前記点の一つであるｙと関連付ける手段と、
ｙを整数の符号帳番号ｎと指数ｉとに、ｙ＝ｍｃ＋ｖと索引付けする手段と
を備え、ここで、ｃはＣの一要素であり、ｖはＶの一要素であり、ｍは２に等しいか２より大きい整数であり、前記格子Ｌの部分集合ＣとＶ、およびｍの値とｉの大きさは、ｎから一意的に定義されることを特徴とする方法。
【請求項３８】
マルチレートの格子量子化復号器において、
格子Λから抽出した基本符号帳Ｃを提供するための記憶手段と、
符号化済み符号帳番号ｎと符号化済み指数ｉとを提供するための受信手段と、
前記符号帳番号ｎを用いて、前記量子化指数ｉを逆多重化するための手段と、
ｎ＝０かどうかを検証し、ａ）前記基本符号帳を用いて前記指数ｉを復号して、量子化されたベクトルｙを作り出すための手段と
ｎ＞０かどうかを検証するための手段と、
予め選択されたボロノイ符号帳Ｖ（ｒ）を提供するための手段と、
拡張次数をｒ＝ｎに、拡大係数ｍ＝２ｒに設定する手段と、
指数ｊとｋをｉから逆多重化するための手段と、
ｊを前記基本符号帳Ｃの中のｃに復号するための手段と、
ｋを前記ボロノイ符号帳Ｖ（ｒ）の中のｖに復号するための手段と、
量子化済みベクトルをｙ＝ｍｃ＋ｖと再構成するための手段と
を備えることを特徴とする復号器。
【請求項３９】
マルチレートの格子量子化復号器において、
点の無限格子Ｌの有限部分集合ＣとＶを提供するための記憶手段と、
符号帳番号ｎと指数ｉとを提供するための受信手段と、
ｎとｉとを用いて格子Ｌ内のベクトルｙをｙ＝ｍｃ＋ｖと再構成するための手段と
を備え、
ここで、ｍは２に等しいか２より大きい整数であり、ｃとｖはＬに含まれる点であり、前記点ｃはＬの有限部分集合Ｃの一要素として再構成され、前記点ｖはＬの有限部分集合Ｖの一要素として再構成され、ｖの指数とｃの指数はｉを用いて計算され、格子Ｌの前記部分集合ＣとＶ、およびｍの値、およびｉの大きさは、ｎから一意的に定義されることを特徴とする復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、信号の符号化と復号に関する。より詳細には、本発明は、例えばディジタル伝送やデジタル記憶システムにおいて使用される信号の、マルチレート（multi-rate）による格子ベクトル量子化のための方法とシステムに関係する。
【背景技術】
【０００２】
ディジタル音声と音響信号の符号化に対する古典的な従来技術は、変換符号化であり、これによって符号化しようとする信号は、フレームと呼ばれるサンプルブロックに分割され、各フレームは、例えば離散型フーリエ変換あるいは離散型コサイン変換のような、線形直交変換によって処理されて、変換係数を作り出し、この係数は、その後に量子化される。
【０００３】
添付の図１は、変換符号化の高水準の構成を示している。この構成において、変換式Ｔが、符号化器において、変換係数を与える入力フレームに適用される。この変換係数は、量子化器Ｑで量子化されて、フレームの量子化済み変換係数を特徴付けるための一つあるいは一組の指数を得る。この指数は、一般的に、記憶媒体に２進数の形態で記憶するか、通信チャネルを通して送信するかが可能な２進符号に符号化される。復号器では、通信チャネルから受信されるか、記憶媒体から読み出される２進符号は、量子化器Ｑ−１の復号器で量子化される変換係数を再構成するのに使用される。逆変換式Ｔ−１は、その後、合成済みフレームを再構成するために、これら量子化済み変換係数に適用される。
【０００４】
ベクトル量子化（ＶＱ）において、いくつかのサンプルあるいは係数がベクトル内で互いに遮られ、各ベクトルは、符号帳（codebook）の記載事項によって近似され（量子化され）る。入力ベクトルを量子化するのに選ばれた記載事項は、典型的には、距離の基準からして、符号帳の中で最も近いものである。符号帳の中で記載事項をさらに加えることで、ビット速度と複雑さとを増すが、平均的歪みを減らす。符号帳の記載事項は、符号ベクトルとして参照される。
【０００５】
送信元の特性の変更に適応するために、適応的ビット割り当てが通常使用される。適応的ビット割り当てによって、異なる大きさの符号帳を、送信元ベクトルを量子化するのに用いることができる。変換符号化において、送信元ベクトルに割り当てられるビット数は、典型的には、全ての係数を量子化するのに使用可能なビット数の最大値の制約下で、同じフレーム内の他のベクトルに関連するベクトルのエネルギーによって決まる。図２Ａと２Ｂは、マルチレート量子化器の一般的な文脈内の図１の量子化ブロックの詳細を示している。このマルチレートの量子化器は、送信元ベクトルｘを量子化するのとは異なるビットレートを持ついくつかの符号帳を使用する。この送信元ベクトルは、典型的には、信号に変換を適用するか、変換係数の全て或いは部分集合を取ることによって得る。
【０００６】
図２Ａは、Ｑと表される多数レートの量子化器の符号化器を図示しており、これは、送信元ベクトルＸに対して、量子化済みの表記Ｙを特徴付けるために、符号帳番号ｎと符号ベクトルの指数ｉを選択する。符号帳番号ｎは、指数ｉがこの特定の符号帳内の選択された符号ベクトルを識別する間に、符号化器によって選択される符号帳を示す。一般的に、記憶のため或いは通信チャネルを通しての伝送のために多重化（ＭＵＸ）する前に、符号化済みの符号帳番号ｎＥと指数ｉＥの平均ビットレートを下げるために、適切な無損失の符号化技法をブロックＥｎとＥｉの中のｎとｉに適用することができる。
【０００７】
図２Ｂは、マルチレートの量子化器の復号動作を示している。最初に、２進符号ｎＥとｉＥが逆多重化（ＤＥＭＵＸ）され、その無損失の符号がブロックＤｎとＤｉにおいて、それぞれ復号される。読み出した符号帳番号ｎと指数ｉは、Ｑ−１と表記されて、マルチレートの量子化器の復号器に導かれ、そこでは、ｎとｉを用いて送信元ベクトルｘの量子化済み表記を復元する。異なる値のｎでは、通常、異なるビット割り当てとなり、同等に指数ｉに対して異なるビットレートになる。大きさ当たりのビット数で与えられる符号帳ビットレートは、発信元ベクトルに割り当てられるビット数と、発信元ベクトルの大きさの比として定義される。
【０００８】
符号帳は、いくつかの方法を用いて構成することができる。よくある方法は、練習用アルゴリズム（例えば、k-meansアルゴリズム）を適用して、発信元の配付によって符号帳の記載事項を最適化する。この方法により未構成の符号帳が作られ、これは通常、各ベクトルが量子化するために、記憶され徹底的に検索されなくてはならない。この方法の制約は、このように、メモリの要求と計算上の複雑さであり、これにより符号帳ビットレートと共に指数関数的に増加する。これらの制約は、もしマルチレートの量子化方法が未構成の符号帳に基づいていればさらに大きくなるが、これは一般的に特定の符号帳は、可能性のある各ビット割り当てに使用されるからである。
【０００９】
他の方法としては、限定されたあるいは構成された符号帳を使用するものがあり、これは、検索の複雑さや、さらに多くの場合、記憶の必要性を少なくする。
【００１０】
次に、構成ベクトル量子化の２つの例を詳細に説明する。複数ステージと格子ベクトル量子化である。
【００１１】
複数ステージのベクトル量子化において、発信元ベクトルｘは、第１ステージ符号帳Ｃ１を用いて符号ベクトルｙ１へ量子化される。量子化誤りを減らすために、入力ベクトルｘと選択された第１ステージの符号ベクトルｙ１の差である第１ステージの残差ｅ１＝ｘ−ｙ１が、第２ステージの符号帳Ｃ２を用いて量子化されて符号ベクトルｙ２になる。この処理は、続くステージで最終ステージまで繰り返されて、（ｎ−１）番目のステージの残差ｅｎ−１＝ｘ−ｙｎ−１は、ｎ番目のステージの符号帳Ｃｎで量子化されて符号ベクトルｙｎになる。
【００１２】
ｎ個のステージ（ｎ≧２）が使われる時、再構成は、符号ベクトルｙ＝ｙ１＋…＋ｙｎの総和として書かれ、ここでｙｌは、ｌ＝１，…，ｎにおいてｌ番目のステージの符号帳Ｃｌの記載事項である。全体を通してのビットレートは、全てのｎ個の符号帳のビットレートの総和である。
【００１３】
格子ベクトル量子化において、同様に格子ＶＱあるいは代数ＶＱと呼ぶが、符号帳は、所定の格子内の格子点の部分集合を選択することによって作られる。
【００１４】
一つの格子は、全ての点或いはベクトルがＮ個の基底ベクトルの整数結合によって、つまり、符号付きの整数の重みを伴う基底ベクトルの重み付け総和として得ることができるところの、Ｎ次元の線形構造である。図３は、２次元における例を示しており、ここでは、基底ベクトルは、ｖ１とｖ２である。本例で使用される格子は、Ａ２と表される六角格子として良く知られる。この図で十字の印の全ての点は、
ｙ＝ｋ１ｖ１＋ｋ２ｖ２      …（式１）
として得られる。ここで、ｙは格子点であり、ｋ１とｋ２は整数であってよい。図３は、格子自身は無限に伸びるものなので、格子の部分集合を示しているだけであることに注意したい。また、式１を行列で書くこともできる。
【数１】
2005528839.tif 000003
ここで、基底ベクトルｖ１＝［ｖ１１  ｖ１２］とｖ２＝［ｖ２１  ｖ２２］は、生成器行列の行を形成する。格子ベクトルは、これら行ベクトルの整数結合を取ることで得られる。
【００１５】
格子が、量子化符号帳を構築するのに選択される時、点の部分集合が、所定の（有限）ビット数を備えた符号帳を得るのに選択される。これは、通常、成形と呼ばれる技法を使用することで行われる。成形は、成形境界線によって格子を切ることで実行される。この成形境界線は、典型的には、原点に集められるが、そうでなくてはならない訳では無く、例えば矩形、球形、ピラミッド型でも良い。図３は、球形の成形境界線を持った例を示している。
【００１６】
格子を用いる利点は、高速符号帳検索アルゴリズムがあることであり、これは、符号帳内部の全ての格子点の間にある発信元ベクトルｘの最近接のものを決定する際に、未構成である符号帳に比べて、複雑さを著しく減らすことができる。また、実質的に、生成器行列から得ることができるので、格子点を記憶する必要は無い。高速検索アルゴリズムは、一般的に、四捨五入された要素全ての総和が奇数或いは偶数であるか、もしくはモジュロ演算内の或る整数に等しくなるような制約に従って、ｘの要素を最近接の整数に四捨五入することが含まれる。一旦ベクトルが量子化されると、すなわち、符号帳内部の最近接の格子点が決定されると、通常は、より複雑な処理が、選択された格子点に索引を付けることで構成される。
【００１７】
格子符号帳の高速検索と索引付けのアルゴリズムの特定の種類には、先導部（leader）の考え方が含まれており、それらの詳細は、非特許文献１、非特許文献２、非特許文献３に記載される。
【００１８】
先導部は、慣例により降順で並べた成分を備える格子点である。絶対先導部（absolute leader）は、全て負でない成分を備えた先導部である。符号付き先導部は、各成分に符号を備えた先導部である。通常は、格子構造は、格子点の符号に制約があり、従って先導部の符号にも制約がある。先導部の考え型は、以下に、より詳細に説明される。
【００１９】
しばしばベクトル量子化で使用される格子は、次元８のゴセット（Gosset）格子であり、ＲＥ８と表される。ＲＥ８内のいかなる８次元の格子点ｙも次の式で生成することができる。
【数２】
2005528839.tif 000004
ここで、ｋ１，ｋ２，…，ｋ８は、符号付き整数であり、ＧＲＥ８は、生成器行列であり、次の式で定義される。
【数３】
2005528839.tif 000005
【００２０】
行ベクトルＶ１，Ｖ２，…，Ｖ８は、格子の基本ベクトルである。生成器逆行列ＧＲＥ８の逆は、次の式５であることが、すぐに確認できる。
【数４】
2005528839.tif 000006
【００２１】
この逆行列は、ｙの基本的な拡張である式６を検索するのに有用である。
【数５】
2005528839.tif 000007
【００２２】
格子は、その上に全ての格子点が存在する、無限個数の組の埋め込まれた球体から成ることは、良く知られている。これらの球体は、しばしばシェルと呼ばれる。ＲＥ８内の球体上の格子点は、一つ或いは幾つかの先導部から、符号付き成分の置換によって生成することができる。先導部の成分の全ての置換は、同じ基準を備えた格子点であり、従って、同じ格子シェルのものとなる。それゆえ、先導部は、格子のシェルを要領よく数え上げるのに有用である。実際に、シェル上の原点に近く置かれた格子点は、非常に少数の先導部から得ることができる。絶対先導部と符号の制約のみが、シェル上に全ての格子点を生成するのに必要なものである。
【００２３】
ＲＥ８符号帳を設計するのに、格子点の有限の部分集合を、格子の固有な幾何学、特にそのシェル構造を有効に使うことで選択することができる。非特許文献１に記載されるように、ＲＥ８のｌ番目のシェルは、√（８ｌ）の半径を持ち、ここでｌは、負でない整数である。高位の半径のシェルは、低位の半径のシェルよりも多くの格子点を備える。所定のシェル上の全ての点を、絶対の符号付き先導部を用いて数え上げることは可能であり、シェル上には一定の数の先導部があり、シェル上に全ての他の格子点があり、符号付き先導部成分を、幾つかの符号上の制約のもとで、置換することによって得られる。
【００２４】
球形格子ＶＱにおいて、符号帳内の全ての格子点の間で最近接の発信元ベクトルｘを決定するために、成分ｘを降順で並べ直して、その後、符号帳を定義する先導部の中で最近接検索を実行することで十分である。最も接近している先導部の索引と、ｘに対して並べる処理から間接的に得られる置換の索引とが、復号器へ送られて、復号器は、この情報からｘの量子化された類似物を再構成することができる。結果として、先導部の考え方によって、便利な索引付けの方法が可能となり、そこで、格子点は、符号付き先導部を参照する濃度オフセットと、符号付き先導部の置換の相対索引を参照する置換指数とによって、表現することができる。
【００２５】
格子のシェル構造と、絶対先導部と符号付き先導部に関する格子の列挙とに基づいて、低位の半径のシェルのみを保持し、高位の半径のシェルのわずかな先導部を追加して符号帳を終了することで符号帳を構築することが可能である。この種の格子符号帳の生成を、近似球形格子成形と呼ぶ。この方法は、非特許文献４で使用されている。
【００２６】
ＲＥ８に関して、半径０と√８のシェル内の絶対先導部は、以下に示される。
半径０のシェルに関する絶対先導部
［００００００００］
半径√８のシェルに関する絶対先導部
［２２００００００］と［１１１１１１１１］
低位の半径のシェルに対して、より完全な一覧表を、特別なＲＥ８の場合には、非特許文献１に見出すことができる。
【００２７】
適応ビット割り当てを用いた変換符号化において使用される格子量子化にとって、マルチレートの格子符号種を構築するのが好ましい。可能性のある解決法は、先導部に関して、非特許文献４と同じ方法で、格子の置換を有効に使うことからなる。非特許文献４で記載されるように、マルチレートの先導部基準の格子量子化器は、例えば、以下のもので設計することができる。
・埋め込まれた幾何学符号帳。これによって、低レートの符号帳は、高レート符号帳の部分集合である。あるいは、
・入れ子になった幾何学符号帳。これによって、マルチレートの符号帳は、重ならないが、ロシア人形の巣（a nest of Russian dolls）と似たやり方で、相補的である。
【００２８】
非特許文献４の特別な場合、マルチレートの格子量子化は、Ｑ０，Ｑ１，Ｑ２，…，Ｑ５の６個の符号帳を用い、ここで、最後の５つの符号帳は、埋め込まれる、すなわちＱ１⊂Ｑ２⊂…⊂Ｑ５である。これらの符号帳は、基本的に８次元の格子のＲＥ８から引き出される。非特許文献４の表記にならって、Ｑｎは、ｎ番目のＲＥ８符号帳を参照する。符号帳ｎのビット割り当ては、２４ｎ個の記載事項に対応して４ｎビットである。符号帳のビットレートは、発信元ベクトルに割り当てられるビット数と発信元ベクトルの次元との間の比として定義され、またＲＥ８量子化において、発信元ベクトルの次元は８なので、Ｑｎの符号帳ビットレートは、次元当たり４ｎ／８＝ｎ／２ビットである。
【００２９】
非特許文献４の技法によれば、符号帳ビットレートは、次元当たり５／２ビットを超えることは無い。この制限によって、ある手順が、外れ値を飽和させるために適用されなくてはならない。外れ値は、マルチレートの符号帳Ｑｎの一つの中には無い、格子ＲＥ８内の最近接ｙを持つ空間内の点ｘとして定義される。非特許文献４において、そのような点は、因子ｇ＞１によって、ｘ／ｇが外れ値より大きくならない間、縮小される。明らかに、ｇを使用することで、大きな量子化誤りが生まれる。この問題を、非特許文献４では、発信元ベクトルを、マルチレートの格子量子化に先立って正規化することで解決している。
【００３０】
非特許文献４のマルチレート量子化技法には、欠点と限界とがある。その中には、以下のものが含まれる。
１．外れ値の飽和は、通常は、計算の重荷になる。さらに、飽和は、大きな外れ値の場合には、量子化の性能（従って品質）を著しく落とす。
２．この技法は、外れ値を飽和で扱っており、８次元ベクトル当たり２０ビット以上を割り当てることができない。これは、変換符号化には不利な点である、というのは、高エネルギーのベクトル（より、外れ値らしい）は、品質を最高にするのに少ない歪みで正常に量子化される、これが暗示するのは、特定のベクトルに割り当てられた十分なビットで符号帳を使用することができるということである。
３．それぞれ８，１２，１６，２０ビットの符号帳Ｑ２，Ｑ３，Ｑ４，Ｑ５は、３，８，２３，７３個の絶対先導部で定められる。記憶の必要条件および検索の複雑さは、絶対先導部の数に密接に関連しており、これら格子符号帳の複雑さは、増加する符号帳のビットレートによって爆発的に悪化する。
４．埋め込まれた符号帳の性能は、重ならない（すなわち入れ子になった）符号帳の場合に比べて、わずかに下がる。
【００３１】
近似球形成形に対抗する、格子成形の他の種類のものは、非特許文献５に記載される、ボロノイ（Voronoi）成形である。これは、例えば、非特許文献６に記載されるボロノイ領域の考え方に依っている。格子符号帳の特別な場合には、ボロノイ領域は、Ｎ次元の空間内の全ての点が、格子内の他の点よりも所定の格子点に近いような空間内の領域である。各格子点は、近接する格子点に等距離な境界点をも含む、関連する閉じたボロノイ領域を持っている。所定の格子において、全てのボロノイ領域はおなじ形状を持っており、すなわち合同である。これは、未構築の符号帳の場合ではない。
【００３２】
ボロノイ符号帳は、符号帳の全ての点が、適切に拡大され変換されて格子のボロノイ領域と同じ形状を持つ空間の領域に分類されるような格子の部分集合である。より詳細には、次元Ｎの格子Λから引き出されるボロノイ符号帳Ｖ（ｒ）は、次の式で定義される。
Ｖ（ｒ）＝Λ∩（２ｒＶΛ（０）＋ａ）      …（式７）
ここで、ｒは、後で詳しく説明する負でない整数のパラメータ、ＶΛ（０）は、原点の周囲のΛのボロノイ領域、ａは、適切なＮ次元のオフセットベクトルである。式７は、以下のように解される。“ボロノイ符号帳Ｖ（ｒ）は、拡大され変換されたボロノイ領域ＶΛ（０）内部のＮ次元空間の領域内に含まれる格子Λの全ての点であると定義され、ここで拡大係数ｍ＝２ｒ、またオフセットベクトルａ”である。ａの役割は、関係を固定することである、すなわち、格子点が全て成形領域２ｒＶΛ（０）＋ａになるのを防ぐことである。
【００３３】
図４は、ボロノイ符号化とボロノイ領域と２次元の六角格子Ａ２内のボロノイ領域のタイル貼りを示している。点ｏは、原点を意味している。ｏとｚの両方の点は、点線で示した同じ境界線の内部に収まっている。この境界は、実質的には、ｍ＝２の縮尺のＡ２のボロノイ領域であり、領域の境界上の格子点を避けるために、やや右に平行移動している。ｏとｚを備えた境界内部に３つの点（・）と１つのプラス（＋）の形の印が付いた、全部で４つの格子点がある。より一般化すると、そのような領域の各々は、ｍＮ個の点を含んでいる。図４では、ｍ＝２の縮尺のＡ２のボロノイ領域である同じパターンが、幾回か繰り返されている。この処理は、タイル貼りと呼ばれる。例えば、ｏ’とｚ’の点は、タイル貼りに関して、それぞれｏとｚに等しいことが分かる。点ｚ’は、ｚ’＝ｏ’＋ｚと書くことができ、ここでｏ’は、２Ａ２の点である。２Ａ２の点は、図４ではプラスの印が付いて示されている。より一般化すると、格子全体は、縮尺ｍの格子点だけ、ボロノイ符号帳を平行移動可能な全てをタイル貼りすることで生成される。
【００３４】
非特許文献７に記載されるように、ボロノイ符号化は、絶え間なく微調整することで格子量子化を拡張するのに使用することができる。非特許文献７の複数ステージ技法によって、各微調整の後に、より細かいマルチレートの量子化が生み出される。この手法は、変換符号化においてマルチレートの量子化に対して使用することができるものであるが、以下のいくつかの限界がある。
１．量子化の段階は、連続する各微調整の後で減少し、その結果、大きな外れ値を効果的に扱うことができない。実際、もし大きな外れ値が第１ステージで発生すると、連続するステージは粒状ノイズのみを減らすように設計されているので、結果としての誤りを効果的に減らすことができない。従って、第１ステージの性能は、重要な意味を持つ。
２．連続する微調整の特性は、連続する量子化段階上の制約を暗示している。これが量子化の性能に制限を与える。
【００３５】
【非特許文献１】C.Lamblin and J.-P.Adoul.Algorithme de quantification vectorielle spherique a partir du reseau de Gosset d'ordre 8.Ann. Telecommun., vol.43,no.3-4,pp.172-186, 1988(Lamblin, 1988)
【非特許文献２】J.-M. Moureaux, P. Loyer, and M. Antonini. Low-complexity indexing method for Zn and Dn lattice quantizers. IEEE Trans. Communications, vol. 46, no.12, Dec. 1998(Moureaux, 1998); and in
【非特許文献３】P.Rault and C.Guillemot. Indexing algorithms for Zn, An, Dn, and Dn++ lattice vector quantizers. IEEE Transctions on Multimedia, vol. 3, no.4, pp. 395-404, Dec. 2001(Rault, 2001).
【非特許文献４】M.Xie and J.-P.Adoul, Embedded algebraic vector quantization(EAVQ) with application to wiswband audio coding, IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Atlanta, GA, U.S.A., vol.1, pp. 240-243, 1996(Xie 1996)
【非特許文献５】J.H.Conway and N.J.A. Sloane, A fast encoding method for lattice codes and quantizers, IEEE Trans, Inform. Theory, vol.IT-29, no.6, pp.820-824, Nov.1983(Conway, 1983)
【非特許文献６】A.Gersho and R.M.Gray, Vector Quantization and Signal Compression, Kluwer Academic Publishers, 1992(Gersho, 1992)
【非特許文献７】D.Mukherjee and S.K.Mitra, Vector set-partitioning with successive refinement Voronoi lattice VQ for embedded wavelet image coding, Proc. ICIP, Part I, Chicago, IL, Oct. 1998, pp.107-111(Mukherjee, 1988)
【発明の開示】
【発明が解決しようとする課題】
【００３６】
本発明の目的は、マルチレートの格子ベクトル量子化器を構築し、検索し、索引を付けるための改良された方法とシステム提供することである。
【００３７】
本発明の他の目的は、格子符号帳に対して改良された検索と索引付けの方法を提供することである。
【課題を解決するための手段】
【００３８】
上記目的は、基本符号帳と呼ばれる、一組の格子符号帳、および、従来技術による量子化器に比べて高速のビットレートの符号帳を基本符号帳から得ることができる拡張機能を用いてマルチレート量子化によって達成される。
【００３９】
より詳細には、本発明の第１の特徴によって、以下を備えるマルチレート格子量子化符号化方法が提供される。
ｉ）送信信号からの１フレームを表すソースベクトルｘを提供する段階と、
ii）格子Λから抽出した基本符号帳Ｃを提供する段階と、
iii）格子Λ内の格子点ｙをｘに関連付ける段階と、
iv）もしｙが基本符号帳Ｃに含まれるならば、基本符号帳Ｃ内でｙを索引付けすることで、量子化指数を作り出し、終了する段階と、
v）もし含まれなければ、基本符号帳を拡張し、拡張符号帳を作り出す段階と、
vi）拡張符号帳から符号ベクトルｃをｙに関連付ける段階と、
vii）拡張符号帳内でｙに索引付けをして、量子化指数を作り出す段階。
【００４０】
本発明の第２の特徴により、マルチレート格子量子化復号方法が提供され、以下を備える。
ｉ）格子Λから抽出した基本符号帳Ｃを提供する段階と、
ii）符号帳番号ｎと量子化指数ｉとを提供する段階と、
iii）符号帳番号ｎを用いて、量子化指数ｉを逆多重化する段階と、
iv）もし、ｎ＝０ならば、基本符号帳を持ちいて指数ｉを復号して、量子化ベクトルｙを作り出し、終了する段階と、
v）もし、ｎ＞０ならば、
ａ）予め選んだボロノイ符号帳Ｖ（ｒ）を提供する段階と、
ｂ）拡張次数をｒ＝ｎに、拡大係数ｍ＝２ｒに設定する段階と、
ｃ）指数ｊとｋをｉから逆多重化する段階と、
ｄ）ｊを基本符号帳Ｃ内でｃに復号する段階と、
ｅ）ｋをボロノイ符号帳Ｖ（ｒ）内でｖに復号する段階と、
ｆ）量子化ベクトルをｙ＝ｍｃ＋ｖとして再構成する段階。
【００４１】
本発明の第３の特徴によって、以下を備える、格子符号帳拡張機能のための方法が提供される。
ｉ）ベクトルの格子Ｌからベクトルの部分集合を提供し、基本符号帳を作り出す段階と、
ii）所定の縮尺係数によって基本符号帳を拡大／縮小し、拡大／縮小した符号ベクトルを作り出す段階と、
iii）拡大／縮小した各符号ベクトルの周囲にボロノイ符号帳を挿入し、拡張符号帳を作り出す段階。
【００４２】
開示された拡張機能の方法は、如何なる次元の如何なる格子から抽出した符号帳とも共に使用することができる。しかし、本発明の実例を示した実施形態によると、８次元のゴセット格子ＲＥ８が、最適化された先導部の表によって示される近似球形の基本符号帳に沿って使用される。
【００４３】
マルチレート格子ベクトル量子化方法に加えて、絶対先導部の識別子を使用する、格子符号帳内を高速に検索し索引付けするための方法が、本発明の実例を示した他の実施形態に沿って提供される。これらの方法は、ＲＥ８格子に特定したものであり、如何なる格子の前後関係でも、あるいは拡張機能無しでも使用することができる。
【００４４】
本発明の第４の特徴によって、以下を備えた、マルチ格子量子化符号化器が提供される。
送信信号から一つのフレームを表す送信ベクトルを提供するための受信手段と、
格子Λから抽出した基本符号帳Ｃを含む記憶手段と、
格子Λ内の格子点ｙをｘに関連付ける手段と、
ｙが基本符号帳Ｃ内に含まれることを確認して、基本符号帳Ｃ内でｙを符号付けし、量子化指数を作り出すための手段と、
基本符号帳を拡張して、拡張符号帳を作り出すための手段と、
拡張符号帳から符号ベクトルｃをｙに関連付けるための手段と、
拡張符号帳Ｃ内でｙを符号付けして、量子化指数を作り出すための手段。
【００４５】
最後に、本発明の第５の特徴によると、以下を備えた、マルチレート格子量子化復号器が提供される。
格子Λから抽出した基本符号帳Ｃを提供するための記憶手段と、
符号化された符号帳番号ｎと符号化された指数ｉとを提供するための受信手段と、
符号帳番号ｎを使用して、量子化指数ｉを逆多重化するための手段と、
ｎ＝０であることを確認して、基本符号帳を用いて指数ｉを復号し、量子化ベクトルｙを作り出すための手段と、
ｎ＞０であることを確認ための手段と、
予め選択したボロノイ符号帳Ｖ（ｒ）を提供するための手段と、
拡張次数をｒ＝ｎに、拡大係数ｍ＝２ｒに設定するための手段と、
指数ｊとｋをｉから逆多重化するための手段と、
基本符号帳Ｃの中でｊをｃに復号するための手段と、
ボロノイ符号帳Ｖ（ｒ）の中でｋをｖに復号するための手段と、
量子化ベクトルをｙ＝ｍｃ＋ｖとして再構成するための手段。
【００４６】
本発明による方法とシステムによると、２次元基本符号帳Ｃは、一連の２の累乗で拡大されて拡張され、拡大された基本符号帳の各点の周囲にボロノイ符号帳Ｖ（ｒ）をタイル貼りする。従って、拡張方法は、ボロノイ拡張と呼ばれる。拡張次数ｒは、拡張が適用される回数である。拡張符号帳Ｃ（ｒ）は、より多くの点を備え、ベクトル空間捕獲外れ値の中でより高く拡張し、一方、基本符号帳と同じ細かさを保つ。これは、符号帳だけでなっくボロノイ符号帳をも符号付けし、拡張次数上に側面情報を送信するのに必要な、増大したビットレートの犠牲によって得られている。開示した手段により得られるマルチレート量子化器のビットレートは、送信元によって決まる。ボロノイ符号帳を索引付けするのに使用されるビット数は、オーバーヘッドとして参照される。
【００４７】
本発明の他の目的や利点や特徴は、例示として添付の図面を参照してのみ、その実例を示した実施形態の以下の非限定的記載を読むことによって、より明らかになるであろう。
【発明を実施するための最良の形態】
【００４８】
最初に、図５〜１４に戻ると、本発明の第１の特徴の第１の実例を示した実施形態による、マルチレート格子符号帳拡張機能のための方法を説明する。本発明による、この拡張機能による方法は、ここではボロノイ拡張方法と呼ぶ。
【００４９】
第１の実施形態を、六角格子Ａ２に基づいた２次元の例によって説明する。
【００５０】
説明を明瞭にするために、第１実施形態に関する重要な記号を表１に集める。
【００５１】
【表１】
2005528839.tif 000008
【００５２】
図５は、無限に拡張する六角格子Ａ２の一部を示している。基本符号帳は、一組の格子点を得るために、この格子を適切に成形することで得られる。これは、図６に示されており、ここでは、球形に作られた境界線が実線で示されており、図７では、成形境界線内部の格子点のみが残されている。成形境界内部の点は、基本符号帳Ｃを備えている。球形の成形が本実施形態で使用されていても、正方形やピラミッド形や長方形等の他の境界線を代わりに使用することも可能である。
【００５３】
この特定の実施形態において、基本符号帳Ｃは、３１個の格子点を備えており、簡潔さのために、５ビットの指数ｉを、この符号帳を分類するのに使用することにする。基本符号帳のボロノイ領域は、図８で点（・）で示される各格子点の周囲に集められた六角領域である。
【００５４】
図９は、２次元平面における送信元ベクトルｘを示している。この図の例から、格子内のｘに最近接の隣点ｙ（図示せず）は、基本符号帳Ｃの記載事項では無いことが分かる。最近接の隣点の検索は、基本符号帳Ｃに限定されないということに注意したい。最近接の隣点ｙは、格子Ａ２全体の中でｘに最も近い点として定義される。図９の特定の場合には、ｙは外れ値である。そのような外れ値ｙを扱う従来技術の方法は、所定の係数、例えば２の累乗によって符号帳を拡大／縮小し、図１０に示す拡大した符号帳となることを思い出したい。しかし、これによってボロノイ領域が、従って粒状の歪みが増大する。
【００５５】
外れ値を含むために符号帳を拡張する間、細かさを維持するために同じボロノイ領域を保持するのに、符号符号帳は２倍に拡大され、ボロノイ符号帳が図１１と１２に示されるように拡大された各符号帳の周囲に挿入される。この拡大処理によって、４つの格子点を備え、それを索引付けするのにオーバーヘッドとして２つの追加ビットを必要とする、２次元のボロノイ符号帳Ｖ（１）が作り出される。この結果として現れる拡張版符号帳Ｃ（１）が、図１３に示される。図１３から分かるように、ｘの隣点ｙは、拡張版符号帳に属するゆえに外れ値では無い。しかし、５＋２＝７ビットが拡張版符号帳にｙを記載するのに必要であり、比するに、基本符号帳では拡張無しで５ビットが必要である。図１４に示すように量子化ベクトルｙは、式８のように表すことができる。
ｙ＝ｍｃ＋ｖ      （式８）
ここで、ｍは、拡張拡大係数（ここでは、ｍ＝２）、ｃは、基本符号帳Ｃの符号ベクトルであり、ｖは、Ｃを拡張するのに使用するボロノイ符号帳に属する。
【００５６】
次に、飽和を防ぐのに格子符号帳を拡張する方法を示した、この最後の２次元の例に続いて、本発明の第１の特徴による格子符号帳拡張方法が、第２実施形態を参考に提示される。
【００５７】
次に、基本符号帳Ｃは、次元毎にＲビットのビットレートを持ち次元Ｎにおける格子Λから抽出されるものとする。言い換えると、Ｃは、２ＮＲ個のＮ次元の符号ベクトルを含み、索引付けのためにＮＲビットを必要とする。
【００５８】
拡張には、連続する２の累乗で基本符号帳を拡大することと、拡大した基本符号帳の各点の周囲にボロノイ符号帳をタイル貼りすることが含まれる。この理由から、この拡張方法は、ここではボロノイ拡張と呼ぶ。次数ｒの基本符号帳Ｃの拡張は、式９で定義される符号帳Ｃ（ｒ）であり、
【数６】
2005528839.tif 000009
ここで、ｍ＝２ｒであり、Ｖ（ｒ）は、同じ格子ΛからＣとして抽出される、大きさｍＮ＝２ｒＮのボロノイ符号帳である。拡張次数ｒによって、拡張が適用される回数が定義される。拡張符号帳には、より多くの符号ベクトルが備わり、その結果、基本符号帳Ｃより多くのビットを使用する。式９における定義は、拡張符号帳Ｃ（ｒ）が第１基本符号帳を索引付けするためにＮＲビットを、そしてボロノイ符号帳に対してＮｒビットを要し、結果として、Ｎ（Ｒ＋ｒ）ビットに拡張次数ｒ上の側面情報を足した総和となるという意味を含む。
【００５９】
連続する２の累乗による基本符号帳の拡大によって、正確なビット数（分数ではない）上に表されたボロノイ指数を持つことができる。しかし、一般的に、ｍは、２以上あるいは２に等しい整数であろう。
【００６０】
符号帳のビットレートにおける増加は、ｒ番目から（ｒ＋１）番目の拡張で、次元当たり１ビットであるので、ボロノイ拡張のこの基本的形式の細かさは、次元当たり１ビットであることに注意したい。
【００６１】
前の２次元の例は、格子Ａ２から抽出された特定の基本符号帳Ｃを使用した。図７の例では、Λ＝Ａ２，Ｎ＝２であり、基本符号帳のビットレートは、次元当たりＲ＝５／２ビットである。
【００６２】
本発明の第２の特徴の実例を示した第１実施形態による、マルチレート格子量子化符号方法１００が、次に、図１５を参照して説明される。
【００６３】
ｘを量子化しようとするＮ次元の送信元ベクトルとする。Ｃが格子Λから抽出された基本符号帳を表し、ｍΛがｍ＞０の整数係数で拡大した格子Λであると定義する。その後、方法１００によって、Ｃあるいは拡張の一つを用いてベクトルｘを符号化する段階は、以下のようである。
【００６４】
段階１０２において、ｘの最近接の隣点ｙは、無限格子Λ内で決定される。段階１０２によって、量子化ベクトルｙが作り出される。
【００６５】
その後、段階１０４において、ｙが基本符号帳Ｃの記載事項であるかどうかが決定される。もし、ｙがＣにあれば（段階１０６）、ｘを量子化するのに使用するビット数は、ＮＲであり、これは、基本符号帳で使用するビット数に対応する。符号帳番号ｎは、０に設定され、符号方法は、終了する。もしｙが基本符号帳Ｃの中になければ、ｙは、外れ値だると見なされ、方法１００は、段階１０８に進み、段階１１０−１１８で、本発明の第１の特徴による第３実施形態に従ったボロノイ拡張方法を作る。
【００６６】
後文に説明するように、ｙは外れ値なので、ｙが基本符号帳の一部である場合に比べて、ｘをｙで量子化するのに、より多くのビットが必要である。反復的である拡張処理は、最終的には、正しく索引付けできる格子ベクトルｙを含む、拡張版符号帳を生成する。
【００６７】
段階１０８は、反復的段階であり、拡張次数ｒは１に、拡大係数ｍは２ｒ＝２に設定される。
【００６８】
格子点ｙのボロノイ符号帳ｋは、計算される（段階１１０）が、これは、段階１０２で獲得した格子Λ内のベクトルｘの最近接の隣点である。ボロノイ符号帳ｋは、拡大次数ｒと拡大係数ｍとによって決まる。ボロノイ指数ｋは、拡大され変換されたボロノイ領域内で、ｙの相対位置だけで決まるように、次のモジュロ演算によって計算される。
ｋ＝ｍｏｄｍ（ｙＧΛ−１）      …（式１０）
ここで、ＧΛは、Λの生成器行列であり、ｍｏｄｍ（・）は、成分に対して（componentwise）モジュロ−ｍ演算である。従って、ボロノイ指数ｋは、各成分の間隔が０からｍ−１である、整数のベクトルである。
【００６９】
段階１１２において、ボロノイ符号帳ｖは、ｍを与えられてボロノイ指数ｋから計算される。これは、例えば、非特許文献５に記載されるアルゴリズムを用いて実行できる。
【００７０】
このｖの計算は、以下のように行うことができる。
１．ｚ＝ｋ＊Ｇを計算する（ＲＥ８）
２．ＲＥ８内で１／ｍ．（ｚ−ａ）の最近接の隣点ｗを見付ける
３．ｖ＝ｚ−ｍ＊ｗを計算する
【００７１】
段階１１４において、差分ベクトルｗ＝ｙ−ｖが最初に計算される。差分ベクトルｗは、常に拡大された格子ｍΛに属する。その後、ｃ＝ｗｌｍが、差分ベクトルｗに逆拡大を適用して計算される。ｗがｍΛに属するので、符号ベクトルｃは、格子Λに属する。
【００７２】
次に、ｃが基本帳Ｃの中にあるかどうかを検証する（段階１１６）。もし、ｃが基本符号帳Ｃの中になければ、拡張次数ｒは、１だけ増分されて、拡大係数ｍは２だけ乗算され（段階１１８）、ボロノイ拡張は新しい繰り返しを続ける（段階１１０）。しかし、もしｃがＣの中にあれば、拡張次数ｒと拡大係数ｍ＝２ｒは、飽和が見付からずに送信元ベクトルｘとｙを量子化するのに十分な大きさである。そしてｙは、非特許文献１におけるように、ｊへの基本符号ベクトルとして索引付けされる（段階１２０）。ｊとｋは、拡張指数ｉへと多重化され（段階１２２）、符号帳番号ｎは、段階１２４で拡張次数（ｎ＝ｒ）に設定され、符号化方法１００は終了する。当業者には良く知られたことだが、多重化の中には、ｊとｋの連結が含まれるが、これは、ｊのビットの後にｋのビットが続くことを意味している。
【００７３】
量子化方法の出力は、符号帳番号ｎと符号ベクトルｙの指数ｉからなる。もしボロノイ拡張が使用されれば、ｎ＞０である。さもないと、ｎ＝０である。指数ｉは、
・もしボロノイ拡張が使用されなければ、基本符号帳内のｙの指数＝ｃであり、
・ｊとｋの多重化、ここで基本符号帳の中でｊがｃの指数であり、ｋはベクトルｖに関連するボロノイ指数である。
【００７４】
式１０において、ボロノイ指数ｋは、ｋ＝ｍｏｄｍ（ｙＧΛ−１）と定義されることに注意したい、ここで、ｍ＝２ｒである。ｙはΛ内の格子点なので、ｙＧΛ−１は、実際にΛ内のｙの基本拡張に対応し、その結果、整数のＮ次元ベクトルである。従って、ｋは、またＮ個の整数のベクトルであり、成分に対するモジュロ演算ｍｏｄｍのせいで、ｋの各成分は０とｍ−１の間の整数である。ｍ＝２ｒなので、構成から、ｋは、Ｎ個の成分全ての指数に全部でＮｒビットを必要とする。
【００７５】
量子化方法１００は、符号帳番号ｎと指数ｉの無損失符号化を定義して、多重化しようとするｎＥとｉＥを得ることで終了し、図２に示される通信チャネルを通って記憶されるか送信される。
【００７６】
一般的に、マルチレートベクトル量子化の出力は、共に、統計的に冗長である、符号帳番号ｎと指数ｉから成る。本発明の範囲や一般性を制限することなく、ここに、量子化器の平均ビットレートを減らすために、符号帳番号ｎのエントロピー符号化のみを扱い、一方、ｉＥ＝ｉである指数ｉには符号化は行われない。算術符号化或いはハフマン符号化（非特許文献６）のような適切な従来技術による無損失符号化手法を、ｎに対して使用することができる。簡単な符号化方法は、単一要素から成る符号であり、そこでは、０に続いて正の整数ｎが２進数の形式でｎ−１個表されている。この符号化法は、以下でより詳細に説明される。
【００７７】
次に、添付の図１６に進んで、本発明の第４の特徴の実例を示した実施形態による、マルチレート格子量子化復号方法２００が説明される。符号化済み符号帳番号ｎＥが最初にチャネルから読み出され、方法１００でも使用された無損失符号化手法が、符号帳番号ｎを得るために反転される（段階２０２）。ｎは、マルチレート量子化器のビット割り当てを示し、段階２０４において量子化指数ｉを逆多重化するのに必要であることに注意することが重要である。
【００７８】
もしｎ＝０ならば（段階２０６）、ボロノイ拡張は使用されない。この場合、指数ｉは、非特許文献１あるいは非特許文献２あるいは非特許文献３に記載されるような従来技術の手法を用いて、基本符号帳Ｃの符号ベクトルｃから復号される（段階２０８）。量子化ベクトルは、次に、単純にｙ＝ｃとして再構成される。
【００７９】
もしｎ＞０ならは（段階２０６）、ボロノイ拡張が使用される。拡張次数と拡大係数は、それぞれｒ＝ｎとｍ＝２ｒに設定される（段階２１０）。指数ｊとｋは、逆多重化される（段階２１２）。指数ｊは、基本符号帳Ｃの中でｃに復号され（段階２１４）、一方、ｋはボロノイ符号帳Ｖ（ｒ）の中でｖに復号される（段階２１６）。量子化ベクトルは、段階２１８において次の式のように再構成される。
ｙ＝ｍｃ＋ｖ      …（式１１）
【００８０】
本発明の実例を示した実施形態で使用される拡張方法は、量子化しようとするベクトルｘへ最近接の格子点ｙが、基本符号帳の外にある場合にのみ必要であることに注意すべきである。従って、この拡張は、もしメモリ（使用可能なビット数）が十分ならば、飽和を抑える。拡張された符号帳は、Ｎ次元空間まで伸び、一方、基本符号帳と同じ格子の細かさを持つ（例えば、図５を参照）ことに注意することが重要である。しかし、拡張を使用する時は、より以上のビットが、必要である。
【００８１】
幾つかの例において、量子化器は、送信元ベクトルｚを捕まえることができずにビットが足りなくなることがある。言い換えると、送信元ベクトルを量子化することのできるビット数は、符号ベクトル指数ｉと符号帳番号ｎに必要なビット数よりも小さいことがある。この場合、量子化誤りは、基本符号帳の細かい構成によって制限されるのでなく、大きな誤りが起きるかも知れない。これは、典型的には、非常に大きな外れ値を持って発生する。
【００８２】
外れ値を扱うのに、マルチレート量子化の前に送信元ベクトルｘを縮小するなどの、いくつかの戦略が実現可能である。ｘにかけられる拡大係数は、割り当てあふれが無いような方法で可変である。
【００８３】
任意の外れ値ｘに対して、ｘに関わりなく、拡張は常にｒ＝０で始まり、繰り返しごとに１ずつ増加するため、前記したような拡張の複雑さは制限の無いものである。しかし、実際には、拡張次数ｒは、例えば１６ビットの符号無しの整数に対する１６のような、実行プラットフォームの整数に割り当てられる大きさのせいで限定される。この限定は、ボロノイ指数ｋの成分の最大値に関連している。
【００８４】
全ての格子点が、基本符号帳Ｃあるいは、ｒ＝１，２，…である、その拡張Ｃ（ｒ）の内のいずれかの記載事項であることが好ましいことが分かった。さもないと、格子点のいくつかは、索引付けすることが不可能である。例えば、原点の周囲に集められた非球形の成形で設計された基本符号帳Ｃは、この条件を満足する。また、集められた（凸状の）領域を持った格子を成形する（切り取る）ことによって得られた、殆どの符号帳は、この条件を満足するだろう。
【００８５】
本発明のそれぞれ第２および３の特徴の第３の実施形態による、マルチレート格子量子化符号化および復号方法を次に説明する。
【００８６】
本発明の、これら第３実施形態は、上で説明したＲＥ８格子に基づいている。
【００８７】
本発明によるマルチレート量子化符号化および復号方法の、実例を示した前の実施形態は、次元当たり１ビットのビットレートの細かさで拡張された格子Λから抽出される一つの基本符号帳に基づいていた。特に、使用した拡張方法は、次元当たり１／２ビット、次元８で４ビットのレートの細かさを得るように、幾つかの近似球形の基本符号帳を拡張するべく適用される。
【００８８】
明確にする目的で、８次元のマルチレート格子量子化方法に関する重要な記号を表２に集めた。
【表２】
2005528839.tif 000010
【００８９】
以下でさらに詳細に説明されるように、本発明の第２の特徴の実例を示した第３の実施形態による、符号化方法には、入力として８次元の送信元ベクトルｘを取り、指数ｉと符号帳番号ｎを出力することが含まれる。符号帳番号ｎは、Ｑｎと表される特定のＲＥ８符号帳を識別子、各Ｑｎは、ＲＥ８格子の部分集合であるものを識別する。Ｑｎの符号帳ビットレートは、次元当たり４ｎ／８ビットである。指数ｉ内のビット数は、従って４ｎである。復号器は、符号器と同じマルチレート符号帳Ｑｎを使用し、単純に、指数ｉと符号帳番号ｎから格子点を再構成する。
【００９０】
実例を示す第３の実施形態によると、ｎは、１以外のいずれかの負でない整数であって良く、｛０，２，３，４，５，６，…｝の組の中の値を取る。ｎ＝１の場合は、次元８の中で４ビットのビット割り当てに対応するため、有利ではない。実際に、そのような低ビットレートにおいて、格子量子化は、あまり効率的でなく、通常は、変換符号化に照らして、雑音充填（noise fill）技法を代わりに使用するのが良い。
【００９１】
本第３実施形態によると、マルチレート符号帳は、以下の２つの種類に分かれる。
【００９２】
低レート基本符号帳Ｑ０とＱ２とＱ３とＱ４は、古典的な近似球形格子符号帳である。本方法が機器内で実施される場合、これらの符号帳は、メモリ内で記憶された、あるいは機器内でハードコードされた表を用いて、使用可能となる。実施形態において、符号帳Ｑ２およびＱ３は埋め込まれる、すなわちＱ２はＱ３の部分集合である。
【００９３】
ｎ＞４に対して、高レートの拡張符号帳Ｑｎは、Ｑ５がＱ３の１次拡張として生成され、Ｑ６がＱ４の１次拡張として生成され、Ｑ７がＱ３の２次拡張として生成される等のように、本発明によるボロノイ拡張方法をＱ３とＱ４に交互に適用することによって、実質的に機器内で構成される。図１７で示されるように、より一般的には、ｎ’＝ｎ＋２ｒ＞４に対して拡張符号帳Ｑｎ’は、奇数ｎ’に対してｎ＝３、偶数ｎ’に対してｎ＝４となるように、Ｑｎのｒ次拡張として生成される。
【００９４】
Ｑ４において低レート拡張符号帳と高レート拡張符号帳の間で分離をすることによって、品質（性能）と複雑さとの間の妥協ができる。例えば、Ｑ５で分離を設定することによって、より大きな符号付け表が作り出され、一方、Ｑ３で分離を設定することによって、品質の低下を起こすが複雑さが減少する。
【００９５】
表３は、Ｑ０とＱ２とＱ３とＱ４に対する絶対先導部のマッピングを定義したものである。このマッピングによって、基本符号帳を明らかに定めることができる。これらの先導部に関連した記号の制限は、この表には表れていないが、当業者にとってＲＥ８の特性から探すことは、手の届く範囲内であることに注意したい（非特許文献１）。
【００９６】
【表３】
2005528839.tif 000011
【００９７】
さらに、ボロノイ成形を定義する８次元のオフセットは、a=[2 0 0 0 0 0 0 0 0]として設定される。
【００９８】
本発明の第２の特徴の第３の実施形態による、マルチレート格子符号化方法３００が、次に、図１８を参照して、より詳細に説明される。
【００９９】
ｘを、次元８で量子化すべき送信元ベクトルとする。段階３０２で、本方法は、最初に、無限格子ＲＥ８内の８次元入力ｘの最近接の隣点を探すことから始まる。次に、段階３０４において、ｙが基本符号帳Ｑ０あるいはＱ２あるいはＱ３あるいはＱ４の記載事項であるかどうかを検証する。この検証により、もしｎ＞０ならば、符号帳番号ｎと識別子ｋａが出力される。この検証の詳細は、以下で与えられる。この段階での符号帳番号ｎは、{0,2,3,4,out}の組の中から取られる。outの値は、任意にout=100に設定された整数である。n=outの値は、外れ値が検出されたことを示すのに使われ、これは、格子点ｙがいずれの基礎符号帳の中の記載事項でも無いことを示す。以下の２つの場合がある。
【０１００】
・もしｎ≦４ならば（段階３０４）、符号化は、段階３０６で完了する。もしｎ＝０ならば（段階３０６）、ｙはゼロベクトルであり、符号化は完了する。もしｎ＝２あるいは３あるいは４ならば、特別な情報ｋａがＱｎを定義する絶対先導部の一つを識別する。以下で、より詳細に説明されるように、ベクトルｙは、実際にはｋａを与えられたＱｎの中で索引付けされる。
・もしｎ＝ｏｕｔならば（段階３０４）、本発明によるボロノイ拡張方法が適用される。拡張方法の第１段階（段階３０８）は、拡張のパラメータを初期化することであり、次に、ｙが拡張符号帳内に含まれるまで、以下に記載するようにボロノイ拡張アルゴリズムを繰り返す。
【０１０１】
マルチレート格子ベクトル符号化および復号方法の第２実施形態において、ボロノイ拡張が、拡張次数ｒをｙになるまで増分して繰り返された。これによって、無制限の複雑さが生まれた。最悪の複雑さを抑えるために、ボロノイ拡張に対して最大２回繰り返して使用するのが有利であることが分かった。
【０１０２】
拡張方法の初期化の段階において、拡張次数ｒと拡張拡大係数ｍは、ｒ以上の繰り返し回数を最小化するように、格子ベクトルy=[y1...y8]として、いくつかの初期値に設定される。繰り返しカウンタiterは、ゼロに設定される。
【０１０３】
ｒとｍを予め選択することは、以下のように実行される。最初に、浮動小数点の値σ＝（ｙ１２＋．．．＋ｙ８２）／３２が計算され、ｒ＝１が設定され、ｍ＝２ｒ＝２となる。次に、σ＞１１の間、σ：＝σ／４，ｒ：＝ｒ＋１，ｍ：＝２ｍと更新しながら、σとｒとｍを繰り返す。この手続きの原理は、以下の２つの観察によって正当化される。
【０１０４】
・ｒ次の拡張から（ｒ＋１）次の拡張へ推移する時、基本符号帳Ｑ３とＱ４は、ｍ＝２ｒの代わりにｍ＝２ｒ＋１を乗算する。拡大された基本符号ベクトルの２乗した基準は、ｒ次の拡張に比べて、（ｒ＋１）次の拡張の後に、４を乗算される。これによって、ｒを超えた各繰り返しの後にσに与えられる係数１／４の説明がつく。
・基本符号帳の結合Ｑ０∪Ｑ２∪Ｑ３∪Ｑ４は、０から３２のＲＥ８シェル上の格子点を備える。Ｑ０∪Ｑ２∪Ｑ３∪Ｑ４内で最も外側の完全なシェルは、シェル５であることを確認できる。終了条件σ＞１１における定数１１は、実験的に５と３２の間で選択された。
【０１０５】
この初期化手続きの代替物は、σが何回１１になるかを直接計算して、それに従ってｒとｍを設定することからなっている。その結果は、自然なことであるが、先に説明した繰り返し手続きと同じになるであろう。
【０１０６】
もし、iter=2（段階３１０）ならば、本方法は、段階３１０〜３２６を備えるループを抜ける。
段階３１２において、格子点ｙのボロノイ指数ｋは、ｍを与えられてモジュロ演算を用いて計算される。ボロノイ指数ｋは、拡張次数ｒと拡大係数ｍによって決まる。ＲＥ８格子の特別な場合は、ボロノイ指数は、以下のように計算される。
【数７】
2005528839.tif 000012
ここで、ＧＲＥ８は、式４で定義される生成器行列であり、ｍｏｄｍ（・）は、成分に対するモジュロｍ演算である。よって、ボロノイ指数ｋは、８個の整数のベクトルであり、各成分は、０とｍ−１の間にある。従って、構成からｋは、全ての成分を索引付けするために全部で８ｒビットを必要とする。
【０１０７】
ボロノイ符号ベクトルｖは、ｍを与えられたボロノイ指数ｋから計算される（段階３１４）。非特許文献５に記載されるアルゴリズムを、この目的のために使用することができる。
【０１０８】
差分ベクトルｗ＝ｙ−ｖが計算される（段階３１６）。この差分ベクトルｗは、拡大された格子ｍＲＥ８内の点である。ｃ＝ｗ／ｍがその後計算され（段階３１６）、すなわち、逆拡大が差分ベクトルｗに適用される。ｗがｍＲＥ８に属するため、点ｃは、格子ｍＲＥ８に属する。
【０１０９】
ｃが基本符号帳Ｑ２あるいはＱ３あるいはＱ４の記載事項であるかどうかに応じて、拡張方法は、検証を進める（段階３１８）。この検証によって、符号帳番号ｎと識別子ｋａとが出力される。この検証の詳細については、以下で、より細かく説明される。開示されたマルチレート基本符号帳で、ｃは、この段階でＱ０の中には無い。結果として、ｎの実際の値は、２，３，４，outのいずれかであろう。
【０１１０】
もしn=outならば、拡張次数ｒは１だけ増加され、拡張率ｍは２で乗算される（段階３２０）。
【０１１１】
もし、ｃがＱ２の記載事項ならば、ｃはＱ３の記載事項でもある、なぜならＱ２はＱ３の中に埋め込まれているからである（Ｑ２⊂Ｑ３）。従って、もしｎ＝２ならば、ｎはｎ＝３に設定される（段階３２２）。拡張次数ｒと拡大係数ｍ＝２ｒは、ｎ＝３あるいはｎ＝４の時に飽和を発生させずに送信元ベクトルｘを量子化できるだけの十分な大きさがある。符号帳番号ｎは、拡張次数ｒを組み込むために更新される。これは、ｎに２ｒを加えることで達成される。次に、ｃとｋａとｎとｋは、メモリ内に記憶され（段階３２４）、拡張次数ｒは１だけ減少され、拡大係数ｒは２で除算される（段階３２６）。
【０１１２】
繰り返しカウンタiterの増加は、新しい繰り返しの開始（段階３１０）前に、１だけ増加される（段階３２８）。
【０１１３】
２回の繰り返しの後に、ループが終了する時、拡張の特徴を示すパラメータは、以下の値を含むメモリから読み出される（段階３３０）。
・Ｑ３あるいはＱ４の記載事項である、段階３１６で計算されるベクトルｃ。
・段階３１２で計算されるボロノイベクトル。ボロノイ指数ｋは、８次元ベクトルであり、ここで各成分は０とｍ−１の間の整数であり、ｒビットで索引付けできることに注意したい。
・段階３１８の副生物として計算される識別子ｋａ。
・段階３２０で計算されるような拡張次数ｒを組み込んだ符号帳番号ｎ。
【０１１４】
ｃの指数ｊは段階３２２で計算される。この指数は、指数ｉを形成するためにボロノイ指数ｋと多重化される（段階３３４）。符号化を完了するのに、符号帳番号ｎは、後に説明するように無損失符号化を受け、チャネルを渡って記憶あるいは伝送されるために指数ｉと多重化される。
【０１１５】
符号化方法３００は、格子点ｙを持った送信元ベクトルｘの特徴を記述するために、十分なメモリが使用可能であることを前提とすることに注意したい。従って、マルチレート量子化符化方法３００は、本方法３００を適用する前に、送信元ベクトルｘをｘ／ｇと縮小することによって、利得形成（gain-shape）の方法で適用されるのが好ましい。スカラー（scalar）パラメータｇ＞１は、メモリの超過を避けるように決定され、従来技術の手段を用いて量子化される。しかし、もし、ｇを正しく選択できなかった時にメモリの超過が発生すると、デフォルト設定でｎはゼロに設定され、再構成ｙはゼロベクトルになる。ｇの選択と量子化手法は、実際の応用によって決まるので、ここでは細かく述べない。
【０１１６】
さらに、方法３００はボロノイ指数ｋの成分は１６ビットの整数で表されるようなソフトウェアプラットフォーム上で実行されるとすると、ｒの最大値は、ｒ＝１６であり、符号帳番号に対して、結果として最大値ｎ＝４＋２×１６＝３６となる。
【０１１７】
絶対先導部の識別子を基本符号帳の中で探し、格子点が基本符号帳の中にあるかどうかを検証するための方法（段階３０４と３１８）を次に、より詳細に説明する。
【０１１８】
従来技術によるそのような方法によって、格子点ｙが近似球形格子符号帳Ｑ２或いはＱ３或いはＱ４内の記載事項にあるかどうかを検証するために、ｙの成分の絶対値が降順で記録され、成分毎に符号帳を定義している先導部と直接に比較される（非特許文献１）。本発明による方法は、識別子ｋａを使用することに基づいている。この方法は、以下の３つの段階で説明される。
【０１１９】
１）ｙから値ｓを計算する。ｙ成分に対してｙ＝［ｙ１．．．ｙ８］として書き込み、この値は次の様に計算される。
ｓ＝（ｙ１４＋…ｙ８４）／８      …（式１２）
２）基本符号帳を定義する絶対先導部ｙに対して計算したｓの値は、全て互いに異なる。さらに、ｙの全ての有効な符号付き置換は、同じ値ｓとなる。結果として、値ｓは、ここではキーとして参照される、なぜならば絶対先導部と全ての関連する符号付き置換を一意的に識別するからである。
【０１２０】
３）もしｓ＝０でありｙがゼロベクトルならば、ｋａを値３６に設定する。さもないと、０と３７の間の整数値に達する識別子ｋａにｓを変換するマッピング表において、キーｓを探す。表４で、表３から容易に計算できる、このマッピングが与えられる。もしキーｓが表４の記載事項ならば、識別子ｋａは０から３６の間の整数である（表４を参照）。さもないと、ｙはｋａを３７に設定して外れ値を宣言される。
【０１２１】
【表４】
2005528839.tif 000013
【０１２２】
表４の右側にある最後の列は単に参考のためであり、識別子ｋａとそれに関連する絶対先導部の間のマッピングを、曖昧さをなくして定義したものであることに注意したい。
【０１２３】
この段階では、識別子は、０≦ｋａ≦３７を検証する。実際に、もし０≦ｋａ≦３６であれば、ｙは、Ｑ２或いはＱ３或いはＱ４の中にある。もし、ｋａ＝３６ならば、ｙはＱ０の中にある。もしｋａ＝３７ならば、ｙは基本符号帳のいずれの中にも無い。次に、識別子ｋａは、表５で符号帳番号ｎにマップされる。
【０１２４】
【表５】
2005528839.tif 000014
【０１２５】
絶対先導部の識別子に基づいて基本符号帳Ｑ２とＱ３とＱ４内で索引付けするための方法（段階３０６と３３２）が、次に詳細に説明される。
【０１２６】
基本符号帳Ｑ２とＱ３とＱ４の記載事項ｙの指数は、近似球形符号帳に関する非特許文献１に記載される従来技術の索引付け手法を用いて計算される。より細かく述べると、例えばｙの指数は、ｊ＝濃度のオフセット＋置換の階数、のように計算される。置換の階数は、非特許文献１に記載される周知のSchalkwijkの公式によって計算される。濃度のオフセットは、ｙに対して符号付きの先導部を計算した後に、表索引によって見付ける。表索引は、関連する絶対先導部の識別子ｋａに基づく。
【０１２７】
本発明の実例を示した実施形態によって、符号帳番号ｎは、可変長２進数を用いて符号化され、これは単一要素の符号として従来技術に良く知られたものであり、以下のマッピングに基づく。
Ｑ０→０
Ｑ２→１０
Ｑ３→１１０
Ｑ４→１１１０
Ｑ５→１１１１０
…
【０１２８】
上のマッピングの右側から、符号ベクトル指数ｉで多重化される２進表記でのｎＥが与えられる。さらに、ボロノイ拡張が使われると（ｎ＞４）、符号ベクトル指数ｉには、２つの互いに多重化された副索引が備わる。
・奇数ｎに対して、１２ビットまた偶数ｎに対して１６ビットの、基本符号帳指数ｊ
・成分としてｒビットの整数を８個備えた、８ｒビットのボロノイ指数ｋ。
【０１２９】
ｉの構造は、２≦ｎ≦４に関して図１９Ａに示され、一方、図１９Ｂはｎ＞４の場合を検討している。多重化されたビットは、４ｎビットのブロック全体の内部で何らかのやり方で置換され得ることに注意したい。
【０１３０】
次に、本発明の第３の特徴の第３の実施形態によるマルチレート格子復号方法４００を、図２０を参照して、より詳細に説明する。
【０１３１】
符号済み符号帳番号ｎＥが最初にチャネルから読み出され、符号帳番号ｎを得るために復号される（段落４０２）。符号帳番号ｎは、方法３００に記載されるマッピングを逆にしてｎＥから読み出される。その後、復号器は、符号ベクトル指数ｉを、符号帳番号ｎによって別にインタープリットする。
【０１３２】
もしｎ＝０ならば（段階４０４）、ｙは基本符号帳Ｑ０の唯一の記載事項であるゼロベクトルとして再構成される（段階４０６）。
【０１３３】
もし０＜ｎ≦４ならば（段階４０４）、４ｎビットの大きさの符号ベクトル指数ｉが逆多重化される（段階４０８）。そしてｉは符号帳Ｑ２或いはＱ３或いはＱ４の指数として復号され、ｙは非特許文献１と２と３に記載されるもののような従来技術を用いて再構成される（段階４１０）。
【０１３４】
段階４０４における値ｎ＞４は、ボロノイ拡張が使用されることを示している。チャネルからの４ｎビットの大きさの符号ベクトル指数ｉ（段階４０８）は、基本符号帳指数ｊとボロノイ指数ｋとしてｉから逆多重化される（段階４１２）。拡張次数ｒも拡大係数ｍもｎから読み出される（段階４１４）。ｒの値は、（ｎ−３）／２の商として得られ、ｍ＝２ｒである。次に２ｒがｎから減じられ、Ｑ３あるいはＱ４のいずれであるかを検証し、指数ｊはｎの減算した値を用いてｃへ復号される（段階４１６）。ｊの復号は、非特許文献１と２と３に記載される、階数復号と表索引とを備える従来技術の方法に基づいている。ボロノイ指数ｋは、非特許文献５に記載される従来技術のアルゴリズムを用いて、ｍに基づいて、ｖへと復号される（段階４１８）。最後に段階４２０において、復号器は、ｙ＝ｍｃ＋ｖのように再構成を計算し、ここでｍ＝２ｒは拡大係数であり、ｃは基本符号帳の符号ベクトルであり、ｖはボロノイ符号帳の符号帳ベクトルである。ｒ＝０のとき、拡張は使用されず、ｖはゼロベクトルであり、ｍはゼロになる。
【０１３５】
ここまで本発明をその実例を示す実施形態によって説明してきたが、添付の特許請求の範囲に定義したような本発明の主題の趣旨と本質とから逸脱せずに変更することができる。
【図面の簡単な説明】
【０１３６】
【図１】従来技術による変換符号器を示すブロック図である。
【図２Ａ】従来技術の方法によるマルチレート量子化器の符号化器のブロック図である。
【図２Ｂ】従来技術の方法によるマルチレート量子化器の復号器のブロック図である。
【図３】従来技術の方法による２次元六角格子Ａ２上で成形する球形を示す図である。
【図４】従来技術の方法による２次元六角格子Ａ２内の、ボロノイ符号化、ボロノイ領域、ボロノイ領域のタイル貼りの図である。
【図５】六角格子Ａ２からの点を示したグラフである。
【図６】基本符号帳を定義するための成形境界を含む、図５のグラフである。
【図７】図６に示す成形境界に分類される格子点のみを保つことにより得られる基本符号帳Ｃを示すグラフである。
【図８】各符号ベクトルの周囲にボロノイ領域を持った、図７からの基本符号帳Ｃを示す図である。
【図９】送信元ベクトルの位置を示す、図８のグラフである。
【図１０】係数ｍ＝２で拡大した、図８からの基本符号帳Ｃを示すグラフである。
【図１１】シフトされ拡大されたボロノイ領域と、４点を備えるボロノイ符号帳を持った、図１０からの拡大された基本符号帳を示すグラフである。
【図１２】次数ｒ＝１の拡張符号帳を示す、図１１からのグラフである。
【図１３】関連するボロノイ領域を持つ、図１２からの拡張符号帳を示すグラフである。
【図１４】拡大された符号ベクトルｍｃと、ボロノイ符号帳の符号ベクトルの総和として再構成される、量子化済みベクトルｙを示す、図１３からのグラフである。
【図１５】本発明の第２の特徴の第１の実例を示した実施形態による、マルチレート格子量子化符号方法を示すフローチャートである。
【図１６】本発明の第３の特徴の第１の実例を示した実施形態による、マルチレート格子量子化符号方法を示すフローチャートである。
【図１７】本発明の一特徴による、拡張符号帳Ｑ５，Ｑ６の、また他の高レート符号帳の生成を示すフローチャートである。
【図１８】本発明の第２の特徴の第２の実例を示した実施形態による、マルチレート格子量子化符号方法を示すフローチャートである。
【図１９Ａ】拡張機能が使用されない場合における、図１８の符号化方法によって作られる符号ベクトル指数ｉの構造を示す概略図である。
【図１９Ｂ】拡張機能が使用される場合における、図１８の符号化方法によって作られる符号ベクトル指数ｉの構造を示す概略図である。
【図２０】本発明の第３の特徴の第２の実例を示した実施形態による、マルチレート格子量子化符号方法を示すフローチャートである。
【符号の説明】
【０１３７】
Ｔ…変換
Ｑ…量子化器
ＭＵＸ…多重化
ＤＥＭＵＸ…逆多重化
ｏ…原点
【図１】
2005528839.tif 000017
【図２Ａ】
2005528839.tif 000018
【図２Ｂ】
2005528839.tif 000019
【図３】
2005528839.tif 000020
【図４】
2005528839.tif 000021
【図５】
2005528839.tif 000022
【図６】
2005528839.tif 000023
【図７】
2005528839.tif 000024
【図８】
2005528839.tif 000025
【図９】
2005528839.tif 000026
【図１０】
2005528839.tif 000027
【図１１】
2005528839.tif 000028
【図１２】
2005528839.tif 000029
【図１３】
2005528839.tif 000030
【図１４】
2005528839.tif 000031
【図１５】
2005528839.tif 000032
【図１６】
2005528839.tif 000033
【図１７】
2005528839.tif 000034
【図１８】
2005528839.tif 000035
【図１９Ａ】
2005528839.tif 000036
【図１９Ｂ】
2005528839.tif 000037
【図２０】
2005528839.tif 000038
【国際調査報告】
2005528839.tif 000039
2005528839.tif 000040