"木探索を用いて多段量子化を行う量子化装置であって、符号化対象の1つ以上のターゲットのそれぞれと符号帳に格納されたコードベクトルとのマッチングを行い、量子化歪の最も小さい方から1つ以上の候補を、前段において決定された、もしくは予め設定された候補数だけ求める探索手段と、前記候補について、前記ターゲットから前記コードベクトルを減算して量子化誤差ベクトルを算出する算出手段と、前記前段において決定された候補数に基づいて次段で用いる候補数を決定する候補数決定手段と、を具備する量子化装置。前記候補数決定手段は、前記前段において決定された候補数から1だけ減らした候補数を次段で用いることを決定する、請求項1記載の量子化装置。前記候補数決定手段は、前記前段において決定された候補数が予め指定された値P以下の場合、前記量子化歪が所定の閾値よりも大きい場合は候補数Pを次段で用いることを決定し、前記量子化歪が前記所定の閾値以下である場合は候補数として予め指定されたPより小さい値Qを次段で用いることを決定する、請求項1に記載の量子化装置。前記探索手段は、1段目である場合、予め指定された候補数だけ量子化歪の最も小さい方から候補を求める、請求項1に記載の量子化装置。前記候補数決定手段は、現在の段数が所定の段数以上であるか、または候補数が所定の候補数P以下であって、前記量子化歪が所定の閾値よりも大きく、かつ、所定の候補数Rより候補数が小さい場合、候補数Rを次段で用いることを決定し、前記量子化歪が前記所定の閾値以下であり、かつ、前記候補数Rより小さい所定の候補数Qより候補数が小さい場合、候補数Qを次段で用いることを決定する、請求項1に記載の量子化装置。木探索を用いて多段量子化を行う量子化方法であって、符号化対象の1つ以上のターゲットのそれぞれと符号帳に格納されたコードベクトルとのマッチングを行い、量子化歪の最も小さい方から1つ以上の候補を、1段目では、予め指定された候補数だけ求め、2段目以降では、前段において決定された候補数だけ求め、前記候補について、前記ターゲットから前記コードベクトルを減算して量子化誤差ベクトルを算出し、前記前段において決定された候補数に基づいて次段で用いる候補数を決定する、量子化方法。しかしながら、上述したN>1のNベストサーチを用いた多段ベクトル量子化は、各段の候補を1つに絞るN=1よりも最終的な符号化歪を小さくすることはできるが、計算量がN倍に増えてしまう。逆に、Nの数を少なく抑えると、今度は符号化歪が大きくなってしまう。このように、従来のNベストサーチを用いた多段ベクトル量子化では、より少ない計算量で符号化歪を小さくする工夫がなされておらず、十分な符号化性能を得ることができない。本発明の目的は、少ない計算量で符号化歪を小さくし、十分な符号化性能を得る量子化装置及び量子化方法を提供することである。本発明の量子化装置は、木探索を用いて多段量子化を行う量子化装置であって、符号化対象の1つ以上のターゲットのそれぞれと符号帳に格納されたコードベクトルとのマッチングを行い、量子化歪の最も小さい方から1つ以上の候補を、前段において決定された、もしくは予め設定された候補数だけ求める探索手段と、前記候補について、前記ターゲットから前記コードベクトルを減算して量子化誤差ベクトルを算出する算出手段と、前記前段において決定された候補数に基づいて次段で用いる候補数を決定する候補数決定手段と、を具備する構成を採る。本発明の量子化方法は、木探索を用いて多段量子化を行う量子化方法であって、符号化対象の1つ以上のターゲットのそれぞれと符号帳に格納されたコードベクトルとのマッチングを行い、量子化歪の最も小さい方から1つ以上の候補を、1段目では、予め指定された候補数だけ求め、2段目以降では、前段において決定された候補数だけ求め、前記候補について、前記ターゲットから前記コードベクトルを減算して量子化誤差ベクトルを算出し、前記前段において決定された候補数に基づいて次段で用いる候補数を決定するようにした。本発明によれば、少ない計算量で符号化歪を小さくし、十分な符号化性能を得ることができる。以下、本発明の実施の形態について、図面を参照して詳細に説明する。実施の形態1図1は、本発明の実施の形態1に係るCELP符号化装置100の構成を示すブロック図である。このCELP符号化装置100は、声道情報と音源情報とからなる音声信号S11のうち、声道情報については、LPCパラメータ線形予測係数を求めることにより符号化する。また、CELP符号化装置100は、音源情報については、予め記憶されている音声モデルのいずれを用いるかを特定する符号データ、すなわち、適応符号帳103および固定符号帳104でどのような音源ベクトルコードベクトルを生成するかを特定する符号データを求めることにより、音源情報を符号化する。具体的には、CELP符号化装置100の各部は以下の動作を行う。LPC分析部101は、音声信号S11に対して線形予測分析を施し、スペクトル包絡情報であるLPCパラメータを求め、多段ベクトル量子化部102及び聴感重み付け部111に出力する。多段ベクトル量子化部102は、LPC分析部101で得られるLPCパラメータを多段ベクトル量子化し、得られる量子化LPCパラメータをLPC合成フィルタ109に、量子化LPCパラメータの符号データをCELP符号化装置100の外部へ出力する。一方、適応符号帳103は、LPC合成フィルタ109で使用された過去の駆動音源を記憶しており、歪み最小化部112から指示された符号データに対応する適応符号帳ラグに従って、記憶している駆動音源から1サブフレーム分の音源ベクトルを生成する。この音源ベクトルは、適応符号帳ベクトルとして乗算器106に出力される。固定符号帳104は、所定形状の音源ベクトルを複数個予め記憶しており、歪み最小化部112から指示された符号データに対応する音源ベクトルを、固定符号帳ベクトルとして乗算器107に出力する。ここで、固定符号帳104は代数的符号帳であり、2種類の本数のパルスによる代数的符号帳を用いた場合の構成について、重み付けが加算によりなされる場合について説明する。代数的音源とは、多くの標準コーデックに採用されている音源であり、位置と極性-だけが情報の、大きさが1のインパルスを少数立てた音源である。例えば、ARIB規格書RCRSTD-27Kの5.3節のCS-ACELPでの5.3.1.9章、5.4節のACELPでの5.4.3.7章等に記載されている。なお、上記の適応符号帳103は、有声音のように周期性の強い成分を表現するために使われる。一方、固定符号帳104は、白色雑音のように周期性の弱い成分を表現するために使われる。ゲイン符号帳105は、歪み最小化部112からの指示に従って、適応符号帳103から出力される適応符号帳ベクトル用のゲイン適応符号帳ゲイン、および固定符号帳104から出力される固定符号帳ベクトル用のゲイン固定符号帳ゲインを生成し、それぞれ乗算器106、107に出力する。乗算器106は、ゲイン符号帳105から出力された適応符号帳ゲインを、適応符号帳103から出力された適応符号帳ベクトルに乗じ、加算器108に出力する。乗算器107は、ゲイン符号帳105から出力された固定符号帳ゲインを、固定符号帳104から出力された固定符号帳ベクトルに乗じ、加算器108に出力する。加算器108は、乗算器106から出力された適応符号帳ベクトルと、乗算器107から出力された固定符号帳ベクトルとを加算し、加算後の音源ベクトルを駆動音源としてLPC合成フィルタ109に出力する。LPC合成フィルタ109は、多段ベクトル量子化部102から出力された量子化LPCパラメータをフィルタ係数とし、適応符号帳103及び固定符号帳104で生成される音源ベクトルを駆動音源としたフィルタ関数、すなわち、LPC合成フィルタを用いて合成信号を生成する。この合成信号は、加算器110に出力される。加算器110は、LPC合成フィルタ109で生成された合成信号を音声信号S11から減算することによって誤差信号を算出し、この誤差信号を聴感重み付け部111に出力する。なお、この誤差信号が符号化歪みに相当する。聴感重み付け部111は、加算器110から出力された符号化歪みに対して聴感的な重み付けを施し、歪み最小化部112に出力する。歪み最小化部112は、聴感重み付け部111から出力された符号化歪みが最小となるような、適応符号帳103、固定符号帳104及びゲイン符号帳105の各インデックスをサブフレームごとに求め、これらのインデックスを符号データとしてCELP符号化装置100の外部に出力する。より詳細には、上記の適応符号帳103及び固定符号帳104に基づいて合成信号を生成し、この信号の符号化歪みを求める一連の処理は閉ループ制御帰還制御となっており、歪み最小化部112は、各符号帳に指示する符号データを1サブフレーム内において様々に変化させることによって各符号帳を探索し、最終的に得られる、符号化歪みを最小とする各符号帳の符号データを出力する。なお、符号化歪みが最小となる際の駆動音源は、サブフレームごとに適応符号帳103へフィードバックされる。適応符号帳103は、このフィードバックにより、記憶されている駆動音源を更新する。ここで、固定符号帳104の探索方法について説明する。まず、音源ベクトルの探索と符号データの導出は、以下の式1の符号化歪を最小化する音源ベクトルを探索することにより行われる。E:符号化歪、x:符号化ターゲット、p:適応符号帳ベクトルのゲイン、H:聴感重み付け合成フィルタ、a:適応符号帳ベクトル、q:固定符号帳ベクトルのゲイン、s:固定符号帳ベクトル一般的に、適応符号帳ベクトルと固定符号帳ベクトルとはオープンループで別々のループで探索されるので、固定符号帳104の符号の導出は、以下の式2の符号化歪を最小化する固定符号帳ベクトルを探索することにより行われる。E:符号化歪、x:符号化ターゲット聴感重み付け音声信号、p:適応符号帳ベクトルの最適ゲイン、H:聴感重み付け合成フィルタ、a:適応符号帳ベクトル、q:固定符号帳ベクトルのゲイン、s:固定符号帳ベクトル、y:固定符号帳探索のターゲットベクトルここで、ゲインp、qは音源の符号を探索した後で決定するので、ここでは最適ゲインで探索を進めることとする。すると、上式2は以下の式3と書ける。そして、この歪の式を最小化することは、以下の式4の関数Cを最大化することと同値であることがわかる。よって、代数的符号帳の音源のような少数パルスからなる音源の探索の場合は、yHとHHを予め計算しておけば、少ない計算量で上記関数Cを算出できる。図2は、図1に示した多段ベクトル量子化部102の内部構成を示すブロック図である。本実施の形態では、スペクトルパラメータLPCパラメータの量子化方法として多段ベクトル量子化多段VQを用いる。多段VQとは、複数段のVQを連続的に行うものであり、前の段の量子化歪を次の段で量子化する方法である。ここでは、量子化ビット数が比較的多く、段数も比較的多い6~10段以上を想定して、多段ベクトル量子化部102の内部構成について説明する。ベクトル量子化部201-1は、LPC分析部101によって得られたLPCパラメータ、すなわち、符号化対象ターゲットベクトルを量子化する。具体的には、符号帳に格納されたコードベクトルとの距離量子化歪を計算して、最も小さいものの番号を求めるというベクトル量子化を行う。木探索では、距離量子化歪が最も小さい方から数個の候補の番号を求めることになる。ベクトル量子化部201-1は、量子化歪として仮ターゲットベクトル、符号候補木探索では番号の列候補番号列になる及び候補数を求め、求めた仮ターゲットベクトル、符号候補及び候補数をベクトル量子化部201-2に出力し、符号候補を符号決定部202にも出力する。ベクトル量子化部201-2は、ベクトル量子化部201-1から出力された仮ターゲットベクトル木探索では複数存在することもあるに対して、ベクトル量子化部201-1と同様の量子化を行い、仮ターゲットベクトル、符号候補候補番号列及び候補数をベクトル量子化部201-3に出力し、符号候補を符号決定部202にも出力する。ベクトル量子化部201-3~201-Jは、それぞれベクトル量子化部201-1と同様の量子化を行い、ベクトル量子化部203-Jは仮ターゲットベクトル、符号候補候補番号列及び候補数を符号決定部202に出力する。符号決定部202は、ベクトル量子化部201-1~201-Jから出力された候補番号列のうち最も量子化歪が少ない候補番号列の番号を1つのデータ列に統合して、符号データとしてCELP符号化装置100の外部へ送る。また、多段ベクトル量子化部102の入力であるターゲットベクトルから最終的な歪を減算すると、符号データを用いて復号化した結果得られる復号化ベクトルになる。この復号化ベクトルから、LPC合成フィルタ109で使用する量子化LPCパラメータを求めて、LPC合成フィルタ109へ送る。図3は、図2に示したベクトル量子化部201-j1≦j≦Jの内部構成を示すブロック図である。以下、ベクトル量子化部201-j1≦j≦Jの内部構成について図3を用いて説明する。ベクトル量子化部201-jには、3つの信号が入力される。一つは、候補数jであり、これは、量子化部201-jで候補として残して次の段のベクトル量子化部201-j1に出力する、候補番号列及び仮ターゲットベクトルの数である。次に、ターゲットベクトル又は仮ターゲットベクトル以下、これらをまとめて仮ターゲットベクトルということがあるjであり、これは、最初の符号化対象ターゲットベクトル又は段の途中で前のベクトル量子化部201-j-1で得られた符号化歪ベクトルとしての仮ターゲットベクトルである。最後に、候補番号列jであり、これは、ベクトル量子化部201-jまでで最も歪の少ない各ベクトル量子化部の番号列である。なお、ターゲットベクトルは1つであるが、仮ターゲットベクトルjと候補番号列jは複数存在する場合がある。ここで、候補数jをKとおき、候補数j-1をMとおく。なお、ベクトル量子化部201-1では、ターゲットベクトルが1つなのでM=1である。また、最後の段のベクトル量子化部201-Jでは、1つの候補番号列を求めればよいのでK=1でよい。Mは入力されるターゲットベクトルと候補番号列jの数であり、Kは次の段のベクトル量子化部201-j1に出力する候補数を意味することに注意されたい。歪計算及び符号帳探索部301は、M個の仮ターゲットベクトルの全てと、符号帳302に格納された全てのコードベクトルとのマッチングユークリッド距離ベクトルとして要素毎に差分を取って2乗和を求めるによる距離計算が一般的であるを行い、距離量子化歪が最も小さい方からK個の候補を探索し、それらのコード番号を求める。その際、元になった番号列も決定される。そして、候補番号列jを参照して、元の番号列に候補のコード番号を接続してK個の候補番号列j1を算出し、次の段のベクトル量子化部201-j1に出力する。また、候補数j、候補のコード番号のコードベクトル、量子化対象のターゲットベクトルを仮ターゲット算出部304に出力する。また、候補数jと符号化歪の中から1つの値を候補数決定部303に出力する。なお、当該ベクトル量子化部201-jが最初の段のベクトル量子化部201-1である場合は、候補数j及び候補番号列jはベクトル量子化部201-1の内部に予め設定されており、ターゲットベクトルのみが入力される。また、当該ベクトル量子化部201-jが最後の段のベクトル量子化部201-Jである場合は、候補数は1であり、最も距離量子化歪が小さくなった番号をターゲットベクトルに対応する候補番号列に接続して、候補番号列j1として符号決定部202に出力するだけで、候補数決定部303及び仮ターゲット算出部304を機能させない。歪計算及び符号帳探索部301の具体的な処理例を以下に示す。j=4,M=4、K=3、ベクトル長をLとし、ターゲットここでは仮ターゲットベクトルはxi0,xi1,xi2,xi3、候補番号列は、j=4であることからこれまでにサイズ646ビットの符号帳を用いたベクトル量子化部が3段あったとして、5,12,315,12,4831,11,5731、3、18の4列とする。この4列の候補列のそれぞれが上記4つの仮ターゲットベクトルと1対1の関係にある。コードベクトルはCimとする。mはコードベクトルの番号とする。量子化歪En,mは、以下の式5で表される。そして、この量子化歪En,mが最も小さくなる上位3つのコード番号を求める。求めた結果、上位3つだったのは、1仮ターゲットベクトルが0の時のコード番号35、2仮ターゲットベクトルが0の時のコード番号8、3仮ターゲットベクトルが3の時のコード番号52、であったとする。上記候補番号列を参照して最後に前記コード番号をつけると、候補番号列j1として、次に送られる3つの番号列は、5,12,31,35、5,12,31,8、31,3,18,52となる。さらに、xi0,Ci35、xi0,Ci8、xi3,Ci52の3組の仮ターゲットベクトルとコードベクトルとを仮ターゲット算出部304に出力する。さらに、候補数3と上位3つの中から1つの距離量子化歪を候補数決定部303に出力する。なお、本実施の形態においては、3つの距離のいずれを出力してもよい。どれを出力しても性能に大きな差はないからである。候補数決定部303は、歪計算及び符号帳探索部301から出力された候補数jと距離量子化歪を参照して、次の段のベクトル量子化部201-j1で用いられる候補数j1を決定してベクトル量子化部201-j1に出力する。仮ターゲット算出部304は、歪計算及び符号帳探索部301から出力されたターゲットとコードベクトルの組を参照して、ターゲットベクトルからコードベクトルを減算してK個の仮ターゲットベクトルj1を算出する。上記具体例では、xi0-Ci35、xi0-Ci8、xi3-Ci52の3つのベクトルが仮ターゲットベクトルj1となる。次に、上述した候補数決定部303についてアルゴリズムの効果を含めて詳細に説明する。まず、木探索VQで用いられるNベストサーチにおいては、段数が多い場合、候補数Nに比例して計算量がN倍に増えてしまい、逆に、Nを小さくすると量子化性能が悪くなってしまう。そこで、本発明者は、木探索を用いた多段VQのシミュレーション実験を繰り返し行い、木探索の性能分析を行い、以下の4つの傾向を抽出した。すなわち、1Nベストサーチにおける候補数Nは段毎に増加又は不変としても計算量ほどの性能は得られない。候補を複数残すのが量子化性能に効果があるのは、多段量子化における最初の段においてである。2段が1つ進んだ際に、サーチの候補数を急激に下げると、量子化性能が大きく落ちる。3N=2とN=1は絶大な差があり、段数が多い場合はN=2でほぼ十分な量子化性能が得られる。4段数が複数進んだ後で符号化歪が小さくならない場合には、最終的なアウトライア量子化誤差がある値以上の割合が悪化する可能性が増加する。上記傾向に鑑み、本発明者は以下の3つのアルゴリズムを組み合わせることによる木探索を発案した。すなわち、以下の手順による。手順11段目は予め指定された候補数Nだけ残して次の段に進む。手順22段目からは段が進む毎に候補数をN-1、N-2と1つずつ減らしていく。手順3候補数が予め定められた値P以下になった場合、その都度、量子化歪を評価して、所定の閾値よりも大きい場合は次の段の候補数をP、閾値以下の場合は次の段の候補数を予め定められたPより小さい値Qとする。以下の説明においては、PとQとの例として、P=3、Q=2として説明を行う。なお、この数値は、計算量に余裕のある場合は、もっと大きな数値でも良い。その場合にはより符号化歪を小さくすることが出来る。このようなアルゴリズムを適用したのが候補数決定部303であり、この結果、最初は候補を多くして段が進む毎に1つずつ減らしていくことすなわち手順2により、最初の部分で的確な候補を選択することができ、また、量子化性能を悪化させることなく可能な限り早く最小限の候補数に辿り着くことができ、さらに、少ない計算量で十分な量子化性能を得ることができる。また、候補数が3=P以下になった場合には、その都度、量子化歪を評価して、大きければ候補数を3=Pに増やし、十分小さければ候補数を2=Qに減らすことすなわち手順3により、十分小さい符号化歪に最低限の計算量で辿り着くように制御することができ、少ない計算量で十分な量子化性能を得ることができる。次に、候補数決定部303における候補数決定手順について図4を用いて説明する。以下の説明では、候補数j1をKKで表す。候補数決定部303に入力されるのは、歪計算及び符号帳探索部301から得られる、候補数jK、距離量子化歪である。段数Jについては候補数決定部303で把握しているものとする。また、Kの初期値、距離の基準値は本量子化を始める前に予め定められていることとする。なお、図4においては距離の基準値として例えば50000とするが、これは他の値が適当な場合もあり得る。ベクトルの次元または要素の値の大きさなどにより適切な値を決めておけばよい。まず、ステップ以下、STと省略する401では、段番号j=1、すなわち、ベクトル量子化部201-1であるか否かが判定され、段番号j=1であるYES場合はST402に移行し、段番号j=1ではないNO場合はST405に移行する。ST402では、候補数Kこの場合、Kの初期値を入力とし、総段数が7より大きいか否かを判定し、総段数が7より大きい場合はST403に移行し、総段数が7より大きくない場合はST404に移行する。なお、この7という数値はもちろん条件次第で他の値が適切な場合もあり得る。総段数または候補数の初期値などに応じて適切な値を予め決めておけばよい。ST403では、KK=K-1とし、また、ST404では、KK=Kとする。ST405では、ST401において段番号j=1ではないベクトル量子化部201-1ではないと判定されたため、KK=K-1とし、ST406では、段番号j=4以上であり、かつ、距離量子化歪が基準値を超えているか否かを判定し、この条件を満たすYES場合はST407に移行し、この条件を満たさないNO場合はST409に移行する。なお、ここでは、段番号j=4以上と設定しているがこれも他の値が適切な場合もあり得る。ST407では、KKが3=Pより小さいか否かを判定し、KKが3=Pより小さいYES場合はST408に移行してKK=3とし、KKが3=Pより小さくないNO場合はST411に移行する。また、ST409では、KKが2=Qより小さいか否かを判定し、KKが2=Qより小さいYES場合はST410に移行してKK=2とし、KKが2=Qより小さくないNO場合はST411に移行する。このようにST406~ST410では、ある程度量子化が進んだ段階で距離量子化歪が十分小さければ候補数を小さく設定し、距離がまだ大きい場合には候補数をより大きくして総合的量子化歪をより小さくするという効果が得られるようにしたものである。最低候補数の2=Qを確保しながら候補数3=Pを使ってより総合的量子化歪を小さくするアルゴリズムである。本発明者の量子化実験においては、この距離の判定によりアウトライア量子化歪がある大きな値以上になる割合を低減できることを確認している。ST411では、段番号j=J、すなわち、最終段であるか否かを判定し、段番号j=JであるYES場合はST412に移行し、段番号j=JではないNO場合はこの段における候補数決定手順を終了する。ST412では、KK=1に設定し、最終段における候補数決定処理を終了する。ここで、本発明の有効性を示すために、CELPのISF量子化に適用した量子化実験について示す。符号器はCELPを基本としたもので、ビットレートは約24kbps、用いたデータは広帯域の周波数の日本語40サンプルである。量子化したのはISFImmittanceSpectralFrequencyの16次元のベクトルである。ベースとなる多段VQはNベースの木探索であり6段以上の段数がある。本発明は同じNを初期の候補数にしている。量子化実験結果を以下の表1に示す。上記表1から、最大フレームの計算量を約1.7wMOPSweitghedMegaOparationPerSecond削減することができ、計算量を大きく削減できることが分かる。また、S/N比SignalNoiseratioでは殆ど変わらず、客観値では合成音は殆ど劣化しないことが分かる。ISFの歪をSDSpectralDistanceで比較しても0.01dBという微量の劣化であり、2dB以上の割合を見るアウトライアでは劣化は0.2だけである。これは500フレームに1回という割合であり、殆ど劣化がないことを示している。しかも、本発明による処理の増加は、候補数の決定だけであり、その計算量は軽微であることから、アルゴリズム全体に与える影響も小さい。このように、実施の形態1によれば、木探索を用いた多段VQにおいて、1段目は予め指定された候補数Nとし、2段目以降では段が進む毎に候補数を1つずつ減らし、候補数が3以下になった場合は、その都度、量子化歪を評価し、所定の閾値よりも大きい場合は次の段の候補数を3=P、閾値以下の場合は次の段の候補数を2=Qとする。これにより、最初の部分で的確な候補を選択することができ、また、量子化性能を悪化させることなく可能な限り早く最小限の候補数に辿り着くことができ、さらに、少ない計算量で十分な量子化性能を得ることができる。また、最低限の計算量で十分小さい符号化歪に辿り着くように制御することができる。実施の形態2本発明の実施の形態2に係るCELP符号化装置の構成は、実施の形態1の図1に示した構成と同一であり、ベクトル量子化部201-jの候補数決定部303の機能が異なるのみなので、必要に応じて図1~図3を援用して説明する。図5は、本発明の実施の形態2に係る候補数決定部303における候補数決定手順を示すフロー図である。以下、候補数決定手順について図5を用いて説明する。ただし、図5において、図4と共通する部分には図4と同一の符号を付し、重複する説明は省略する。また、以下の説明では、実施の形態1の図4と同じ条件とする。すなわち、候補数j1をKKで表す。候補数決定部303に入力されるのは、歪計算及び符号帳探索部301から得られる、候補数jK、距離量子化歪である。また、段数Jについては候補数決定部303で把握しているものとする。また、Kの初期値、距離の基準値は本量子化を始める前に予め定められていることとする。なお、図5においては距離の基準値として例えば50000とするが、これは他の値が適当な場合もあり得る。ベクトルの次元または要素の値の大きさなどにより適切な値を決めておけばよい。ST501では、段番号j=3以上であるか、またはKK=3以下であるか否かを判定し、この条件を満たすYES場合はST502に移行し、この条件を満たさないNO場合はST411に移行する。ST502では、距離量子化歪が基準値を超えているか否かを判定し、超えているYES場合はST407に移行し、超えていないNO場合はST409に移行する。このように、実施の形態2によれば、量子化歪を評価する前に候補数KKが十分小さくなったことを確認することにより、候補数KKが十分小さくなれば量子化歪を用いた候補数制御をすぐに行うことができ、できるだけ少ない計算量で十分な量子化性能を得ることができる。なお、上記各実施の形態では、図3に示したように、候補数決定部303を歪計算及び符号帳探索部301の後段に設けているが、候補数決定部303を歪計算及び符号帳探索部301の前段に設けてもよい。この場合、候補数決定部303は、前の段のベクトル量子化部からの距離量子化歪及び候補数を使用でき、同様の効果が得られることは明らかである。また、上記各実施の形態では、CELPにおける例を示したが、本発明はベクトル量子化に利用できる発明であるので、CELPに限らないことは明らかである。例えば、MDCTModifiedDiscreteCosineTransformまたはQMFQuadratureMirrorFilterを利用したスペクトルの量子化にでも利用できるし、帯域拡張技術における低周波数領域のスペクトルの中から似たスペクトル形状を探索するアルゴリズムにも応用できる。さらに、本発明はLPC分析を用いる符号化方式の全てに適用することができる。また、上記各実施例の形態では、ISFを符号化する例を示したが、本発明はこれに限らず、ISPImmittanceSpectrumPairs、LSPLinSpectrumPairs、PARCORPARtialautoCORrelationなどのパラメータを量子化する場合に適用することができる。実施の形態におけるISF量子化の代わりに別の量子化法を用いれば良いからである。また、上記各実施の形態では、CELPのスペクトルパラメータの木探索VQに対して本発明を適用したが、別のパラメータベクトルの量子化でも本発明が有効であるのは明らかである。パラメータの性質が本発明に影響を与えないからである。また、上記各実施の形態では、歪計算及び符号帳探索部301にユークリッド距離を用いたが、これは重み付きユークリッド距離あるいは市街地距離絶対値の和など、他の距離尺度でもよい。本発明は、候補数決定部303のアルゴリズムにあり、距離尺度は本発明に無関係だからである。また、上記各実施の形態では、符号器に応用した場合を示したが、音声認識または画像認識などのパターンマッチングに用いられる木探索にも本発明は応用することができる。本発明は、木探索の候補数の決定に係り、アルゴリズム全体の目的に影響しないからである。また、上記各実施の形態で説明した符号化装置は、通信端末装置あるいは基地局装置に搭載して用いることが可能である。また、上記各実施の形態では、距離量子化歪と比較する基準値を予め決められた定数としているが、これは各段段番号によって異なる値でもよいことは明らかである。本発明は基準値を拘束するものではないからである。各段段番号において基準値を変えることによって、より効率的な探索を実現することができる。また、上記各実施の形態では、候補数の制御に3と2という予め定められた数値を用いているが、これも4と3、4と2などの数値を用いてもよい。また、この数値を各段段番号で異ならせてもよい。これらの数値は、計算量に余裕がある場合または、より高い性能が必要な場合など、場合に応じて設定すればよい。また、実施の形態2では、jとKKの判定にそれぞれ3と3という予め定められた数値定数を用いているが、これも2と2、2と3、4と3、2と4、4と4又は5と4などに変えてもよい。また各段段番号で異ならせてもよい。これらの数値は、計算量に余裕がある場合、より高い性能が必要な場合など、場合に応じて設定すればよい。また、上記各実施の形態では、本発明をハードウェアで構成する場合を例にとって説明したが、本発明はハードウェアとの連携においてソフトウェアによって実現することも可能である。また、上記各実施の形態の説明に用いた各機能ブロックは、典型的には集積回路であるLSIとして実現される。これらは個別に1チップ化されてもよいし、一部又は全てを含むように1チップ化されてもよい。ここでは、LSIとしたが、集積度の違いにより、IC、システムLSI、スーパーLSI、ウルトラLSIと呼称されることもある。また、集積回路化の手法はLSIに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。LSI製造後に、プログラムすることが可能なFPGAFieldProgrammableGateArrayまたは、LSI内部の回路セルの接続または設定を再構成可能なリコンフィギュラブルプロセッサを利用してもよい。さらには、半導体技術の進歩又は派生する別技術によりLSIに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適用等が可能性としてありえる。2010年9月17日出願の特願2010-210116及び2010年10月13日出願の特願2010-230537の日本出願に含まれる明細書、図面及び要約書の開示内容は、すべて本願に援用される。"