(57)【要約】  音声符号化において、代数的符号帳に対して分割探索を行いつつ、符号化性能を向上することができる音声符号化装置。ＣＥＬＰ符号化装置の歪み最小化部（１１２）において、最大相関値算出部（２２１）は、固定符号帳を構成する４本のパルスに対して、各候補位置における各パルスとターゲット信号とを用いて相関値を算出し、パルス毎に相関値の最大値を求め、この相関値の最大値を用いた最大相関値を算出し、ソーティング部（２２２）は、４本のパルスを２本ずつ２つのサブセットに分割し、探索部（２２４）は、固定符号帳に対し分割探索を行い、符号化歪みが最小となる４本のパルスの位置および極性を示す符号を得る。
2009016816.tif 000002
【特許請求の範囲】
【請求項１】
固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出する算出手段と、
パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するソーティング手段と、
前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を得る探索手段と、
を具備する音声符号化装置。
【請求項２】
前記算出手段は、
前記各パルスの相関値の最大値を用いて算出された前記各パルスの最大相関値を、前記代表値として算出し、
前記ソーティング手段は、
前記最大相関値をソーティングする、
請求項１記載の音声符号化装置。
【請求項３】
前記ソーティング手段は、
パルス毎に得られた前記代表値のうち最大の代表値に対応するパルスを含むサブセットを前記第１のサブセットとする、
請求項１記載の音声符号化装置。
【請求項４】
前記ソーティング手段は、
ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットの複数の組み合わせそれぞれに対してグルーピングし、前記複数の組み合わせのそれぞれから、前記第１のサブセットをそれぞれ決定し、
前記探索手段は、
前記第１のサブセットそれぞれを用いて前記固定符号帳を探索し、そのうち符号化歪みが最小となる前記符号を得る、
請求項１記載の音声符号化装置。
【請求項５】
前記算出手段は、
パルス毎に、２番目に大きい前記相関値に所定の割合を乗じた値を、前記相関値の最大値に加算して、前記各パルスの最大相関値を算出する、
請求項２記載の音声符号化装置。
【請求項６】
前記ソーティング手段は、
グルーピングされたパルスに対応する前記代表値を用いて、前記第１のサブセットを決定する、
請求項１記載の音声符号化装置。
【請求項７】
前記ソーティング手段は、
グルーピングされたパルスに対応する前記代表値の組み合わせを複数生成し、前記組み合わせに予め設定した値を乗じて比較した結果に基づき、前記第１のサブセットを決定する、
請求項１記載の音声符号化装置。
【請求項８】
前記ソーティング手段は、
前記複数のサブセットにグルーピングするパルスを予め決められた順番に並び替える、
請求項１記載の音声符号化装置。
【請求項９】
固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出するステップと、
パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するステップと、
前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を生成するステップと、
を有する音声符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音声符号化装置および音声符号化方法に関し、特に固定符号帳探索を行う音声符号化装置および音声符号化方法に関する。
【背景技術】
【０００２】
移動体通信においては、伝送帯域の有効利用のために音声や画像のディジタル情報の圧縮符号化が必須である。その中でも携帯電話で広く利用される音声コーデック（符号化／復号）技術に対する期待は大きく、圧縮率の高い従来の高効率符号化に対してさらなる音質の要求が強まっている。【０００３】
近年、多層構造を有するスケーラブルコーデックの標準化がＩＴＵ−Ｔ(International Telecommunication Union Telecommunication Standardization Sector)、ＭＰＥＧ（Moving Picture Expert Group）等で検討されており、より効率的で高品質な音声コーデックが求められている。【０００４】
音声の発声機構をモデル化してベクトル量子化を巧みに応用した基本方式「ＣＥＬＰ」（Code Excited Linear Prediction）によって大きく性能を向上させた音声符号化技術は、非特許文献１に記載の代数的符号帳（Algebraic Codebook）のような少数パルスによる固定音源の技術により、一段とその性能を向上させた。ＩＴＵ−Ｔ標準Ｇ．７２９や、ＥＴＳＩ（European Telecommunications Standards Institute）標準ＡＭＲ（Adaptive Multi-Rate）は、代数的符号帳を用いたＣＥＬＰの代表的なコーデックであり、世界で広く使用されている。【０００５】
代数的符号帳を用いて音声符号化を行う場合、代数的符号帳を構成する１つ１つのパルスの相互の影響を考慮し、全てのパルスの組み合わせを探索する（以下、全探索と称す）ことが望ましい。しかし、パルス数が多くなると探索に必要な計算量が指数関数的に増加してしまう。これに対し、非特許文献２には、全探索の場合の性能をほぼ維持しながら計算量を大幅に低減できる代数的符号帳の探索方法として、分割探索、枝刈探索、ビタビ探索などを開示している。【０００６】
その中でも分割探索は最も簡単でかつ計算量削減の効果が大きい方法である。分割探索とは、１つの閉ループ探索を複数のより小さい閉ループに分割して、複数の閉ループ探索の開ループ探索にする方法である。分割探索においては、分割数に応じて大きく計算量を下げることが出来る。分割探索は国際標準方式でも使用されており、第３世代携帯電話の標準コーデックであるＥＴＳＩ標準ＡＭＲの代数的符号帳の探索においては、４本のパルスを２つのサブセットに分けて分割探索を行う。【０００７】
例えば、８つの位置候補を持つパルスが４本ある場合を考えると、４本のパルスをすべて１つの閉ループで探索するには、評価しなければならないパルスの組み合わせが８の４乗で４０９６通りとなる。これに対し、ＥＴＳＩ標準ＡＭＲは、４本のパルスを２本と２本の２つのサブセットに分割して、それぞれを閉ループで探索する。従って、ＥＴＳＩ標準ＡＭＲにおいて評価しなければならないパルスの組み合わせは８の２乗の２倍で１２８通りとなり、全探索の場合と比べて３２分の１の計算量となる。さらに、ＥＴＳＩ標準ＡＭＲにおける各評価は、４パルスよりも少ない２パルスに対して行われるため、計算量はさらに低減される。
【非特許文献１】Salami, Laflamme, Adoul,”8kbit/s ACELP Coding of Speech with 10ms Speech-Frame:aCandidate for CCITT Standardization”,IEEE Proc. ICASSP94,pp.II-97n
【非特許文献２】野村ほか、「ＣＥＬＰにおけるパルス励振源の効果的な探索法」、日本音響学会春季講演論文集２−Ｐ−５、平成８年３月、pp.311-312
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、代数的符号帳の分割探索による音声符号化の性能は、概して全探索の場合に比べ低い。なぜなら最初に決まる２本のパルスの位置が最適であるとは限らないからである。【０００９】
従って、分割探索では先に探索するサブセットを構成するパルスとして何を選ぶかによって、音声符号化の性能を改善する余地がある。例えば、４本のパルスの中でランダムに２つを選んで探索することを複数回行い、そのうち符号化性能が一番良い結果を得る方法が考えられる。例えば、サブセットのペアを４種類用意し、４種類のペアに対してそれぞれ探索を行うことによって、音声符号化の性能を全探索による符号化性能に近づけることが出来る。この場合、１２８（８の２乗の２倍）の４倍で５１２通りの計算が必要になるものの、それでも全探索の場合の計算量の１／８である。ただし、上記例ではサブセットを任意に構成しており、また４種類のペアのいずれにも特に先に探索する理由はない。従って、複数のケースについて探索を行う場合に得られる符号化性能はバラツキがあり、総合的に符号化性能は十分ではない。【００１０】
本発明の目的は、代数的符号帳に対して分割探索を行いつつ、符号化性能を向上することができる音声符号化装置および音声符号化方法を提供することである。
【課題を解決するための手段】
【００１１】
本発明の音声符号化装置は、固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出する算出手段と、パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するソーティング手段と、前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を得る探索手段と、を具備する構成をとる。【００１２】
本発明の音声符号化方法は、固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出するステップと、パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するステップと、前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を生成するステップと、を有するようにした。
【発明の効果】
【００１３】
本発明によれば、音声符号化において固定符号帳の分割探索を行う際、たとえば最大相関値のような、パルスに関する代表値を用いて、先に探索するサブセットを決定するため、代数的符号帳に対して分割探索を行いつつ、符号化性能を向上することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態１に係るＣＥＬＰ符号化装置の構成を示すブロック図
【図２】本発明の実施の形態１に係る歪み最小化部の内部構成を示すブロック図
【図３】本発明の実施の形態１に係る最大相関値算出部における各パルスの最大相関値の算出手順を示すフロー図
【図４】本発明の実施の形態１に係るソーティング部における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図
【図５】本発明の実施の形態１に係る探索部における固定符号帳の分割探索の手順を示すフロー図
【図６】本発明の実施の形態１に係る探索部における固定符号帳の分割探索の手順を示すフロー図
【図７】本発明の実施の形態２に係るソーティング部における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図
【図８】本発明の実施の形態３に係るソーティング部における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図
【図９】本発明の実施の形態３に係るソーティング部における、パルスの順番の並べ替え処理の手順を示すフロー図
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。【００１６】
（実施の形態１）
図１は、本発明の実施の形態１に係るＣＥＬＰ符号化装置１００の構成を示すブロック図である。ここでは、本発明に係る音声符号化装置としてＣＥＬＰ方式の符号化装置を例にとって説明する。【００１７】
図１において、ＣＥＬＰ符号化装置１００は、声道情報と音源情報とからなる音声信号Ｓ１１を、声道情報については、ＬＰＣパラメータ（線形予測係数）を求めることにより符号化し、音源情報については、予め記憶されている音声モデルのいずれを用いるかを特定するインデックスを求めることにより符号化する。すなわち、音源情報については、適応符号帳１０３および固定符号帳１０４でどのような音源ベクトル（コードベクトル）を生成するかを特定するインデックスを求めることにより符号化する。【００１８】
具体的には、ＣＥＬＰ符号化装置１００の各部は以下の動作を行う。【００１９】
ＬＰＣ分析部１０１は、音声信号Ｓ１１に対して線形予測分析を施し、スペクトル包絡情報であるＬＰＣパラメータを求め、求めたＬＰＣパラメータをＬＰＣ量子化部１０２および聴感重み付け部１１１に出力する。【００２０】
ＬＰＣ量子化部１０２は、ＬＰＣ分析部１０１から出力されたＬＰＣパラメータを量子化し、得られた量子化ＬＰＣパラメータをＬＰＣ合成フィルタ１０９に、量子化ＬＰＣパラメータのインデックスをＣＥＬＰ符号化装置１００の外部へ出力する。【００２１】
一方、適応符号帳１０３は、ＬＰＣ合成フィルタ１０９で使用された過去の駆動音源を記憶しており、後述する歪み最小化部１１２から指示されたインデックスに対応する適応符号帳ラグに従って、記憶している駆動音源から１サブフレーム分の音源ベクトルを生成する。この音源ベクトルは、適応符号帳ベクトルとして乗算器１０６に出力される。【００２２】
固定符号帳１０４は、所定形状の音源ベクトルを複数個予め記憶しており、歪み最小化部１１２から指示されたインデックスに対応する音源ベクトルを、固定符号帳ベクトルとして乗算器１０７に出力する。ここで、固定符号帳１０４は代数的音源であり、代数的符号帳を用いた場合について説明する。代数的音源とは、多くの標準コーデックに採用されている音源である。【００２３】
なお、上記の適応符号帳１０３は、有声音のように周期性の強い成分を表現するために使われ、一方、固定符号帳１０４は、白色雑音のように周期性の弱い成分を表現するために使われる。【００２４】
ゲイン符号帳１０５は、歪み最小化部１１２からの指示に従って、適応符号帳１０３から出力される適応符号帳ベクトル用のゲイン（適応符号帳ゲイン）、および固定符号帳１０４から出力される固定符号帳ベクトル用のゲイン（固定符号帳ゲイン）を生成し、それぞれ乗算器１０６、１０７に出力する。【００２５】
乗算器１０６は、ゲイン符号帳１０５から出力された適応符号帳ゲインを、適応符号帳１０３から出力された適応符号帳ベクトルに乗じ、加算器１０８に出力する。【００２６】
乗算器１０７は、ゲイン符号帳１０５から出力された固定符号帳ゲインを、固定符号帳１０４から出力された固定符号帳ベクトルに乗じ、加算器１０８に出力する。【００２７】
加算器１０８は、乗算器１０６から出力された適応符号帳ベクトルと、乗算器１０７から出力された固定符号帳ベクトルとを加算し、加算後の音源ベクトルを駆動音源としてＬＰＣ合成フィルタ１０９に出力する。【００２８】
ＬＰＣ合成フィルタ１０９は、ＬＰＣ量子化部１０２から出力された量子化ＬＰＣパラメータをフィルタ係数とし、適応符号帳１０３および固定符号帳１０４で生成される音源ベクトルを駆動音源としたフィルタ関数、すなわち、ＬＰＣ合成フィルタを用いて合成信号を生成する。この合成信号は、加算器１１０に出力される。【００２９】
加算器１１０は、ＬＰＣ合成フィルタ１０９で生成された合成信号を音声信号Ｓ１１から減算することによって誤差信号を算出し、この誤差信号を聴感重み付け部１１１に出力する。なお、この誤差信号が符号化歪みに相当する。【００３０】
聴感重み付け部１１１は、加算器１１０から出力された符号化歪みに対して聴感的な重み付けを施し、歪み最小化部１１２に出力する。【００３１】
歪み最小化部１１２は、聴感重み付け部１１１から出力された符号化歪みが最小となるような、適応符号帳１０３、固定符号帳１０４およびゲイン符号帳１０５の各インデックスをサブフレームごとに求め、これらのインデックスを符号化情報としてＣＥＬＰ符号化装置１００の外部に出力する。より詳細には、上記の適応符号帳１０３および固定符号帳１０４に基づいて合成信号を生成し、この信号の符号化歪みを求める一連の処理は閉ループ制御（帰還制御）となっており、歪み最小化部１１２は、各符号帳に指示するインデックスを１サブフレーム内において様々に変化させることによって各符号帳を探索し、最終的に得られる、符号化歪みを最小とする各符号帳のインデックスを出力する。【００３２】
なお、符号化歪みが最小となる際の駆動音源は、サブフレームごとに適応符号帳１０３へフィードバックされる。適応符号帳１０３は、このフィードバックにより、記憶されている駆動音源を更新する。【００３３】
ここで、固定符号帳１０４の探索方法について説明する。まず、音源ベクトルの探索と符号の導出は以下の式（１）の符号化歪を最小化する音源ベクトルを探索することにより行われる。
【数１】
2009016816.tif 000003
Ｅ：符号化歪、ｘ：符号化ターゲット、ｐ：適応符号帳ベクトルのゲイン、Ｈ：聴感重み付け合成フィルタ、ａ：適応符号帳ベクトル、ｑ：固定符号帳ベクトルのゲイン、ｓ：固定符号帳ベクトル【００３４】
一般的に、適応符号帳ベクトルと固定符号帳ベクトルとはオープンループで（別々のループで）探索されるので、固定符号帳１０４の符号の導出は以下の式（２）の符号化歪を最小化する固定符号帳ベクトルを探索することにより行われる。
【数２】
2009016816.tif 000004
Ｅ：符号化歪、ｘ：符号化ターゲット（聴感重み付け音声信号）、ｐ：適応符号帳ベクトルの最適ゲイン、Ｈ：聴感重み付け合成フィルタ、ａ：適応符号帳ベクトル、ｑ：固定符号帳ベクトルのゲイン、ｓ：固定符号帳ベクトル、ｙ：固定符号帳探索のターゲットベクトル【００３５】
ここで、ゲインｐ、ｑは音源の符号を探索した後で決定するので、ここでは最適ゲインで探索を進めることとする。すると、上式（２）は以下の式（３）と書ける。
【数３】
2009016816.tif 000005
【００３６】
そして、この歪の式を最小化することは、以下の式（４）の関数Ｃを最大化することと同値であることがわかる。
【数４】
2009016816.tif 000006
【００３７】
よって、代数的符号帳の音源のような少数パルスからなる音源の探索の場合は、ｙＨとＨＨを予め計算しておけば、少ない計算量で上記関数Ｃを算出できる。ここで、ベクトルｙＨの要素は、パルス単独の相関値に相当する。すなわち、ターゲットｙに対して時間逆順合成を施したｙＨの要素の１つはその位置に立つパルスの合成信号とターゲット信号との相関値と等しくなる。【００３８】
図２は、本実施の形態に係る歪み最小化部１１２の内部構成を示すブロック図である。ここでは、歪み最小化部１１２の固定符号帳探索において代数的符号帳を構成する４本のパルスを２本と２本のサブセットに分割して探索する場合を例にとって説明する。また、各パルスが８つの位置候補を備えるとする。【００３９】
図２において、歪み最小化部１１２は、適応符号帳探索部２０１、固定符号帳探索部２０２、およびゲイン符号帳探索部２０３を備える。固定符号帳探索部２０２は、最大相関値算出部２２１、ソーティング部２２２、前処理部２２３、および探索部２２４を備える。【００４０】
適応符号帳探索部２０１は、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪みを用いて、適応符号帳１０３の探索を行う。適応符号帳探索部２０１は、探索過程で得られる適応符号帳ベクトルの符号を適応符号帳１０３に出力し、探索結果として得られた適応符号帳ベクトルの符号を固定符号帳探索部２０２の最大相関値算出部２２１に出力するとともに、ＣＥＬＰ符号化装置１００の外部へ出力する。【００４１】
固定符号帳探索部２０２は、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪み、および適応符号帳探索部２０１から入力される適応符号帳ベクトルの符号を用いて固定符号帳の分割探索を行う。固定符号帳探索部２０２は、探索過程で得られる固定符号帳ベクトルの符号を固定符号帳１０４に出力し、探索結果として得られた固定符号帳ベクトルの符号をＣＥＬＰ符号化装置１００の外部に出力するとともにゲイン符号帳探索部２０３に出力する。【００４２】
ゲイン符号帳探索部２０３は、固定符号帳探索部２０２の探索部２２４から入力される固定符号帳ベクトルの符号、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪み、および適応符号帳探索部２０１から入力される適応符号帳ベクトルの符号に基づき、ゲイン符号帳を探索する。そして、ゲイン符号帳探索部２０３は、探索過程で得られる適応符号帳ゲインおよび固定符号帳ゲインをゲイン符号帳１０５に出力し、探索結果として得られた適応符号帳ゲインおよび固定符号帳ゲインをＣＥＬＰ符号化装置１００の外部に出力する。【００４３】
最大相関値算出部２２１は、適応符号帳探索部２０１から入力される適応符号帳ベクトルの符号を用いて適応符号帳ベクトルを求め、式（２）に示すターゲットベクトルｙを計算する。また、最大相関値算出部２２１は、聴感重み付け部１１１における合成フィルタの係数Ｈを用いて、各候補位置における各パルス単独の相関値ｙＨを算出して前処理部２２３に出力する。そして、最大相関値算出部２２１は、各候補位置における各パルス単独の相関値ｙＨを用いて、各パルスの最大相関値を求め、ソーティング部２２２に出力する。なお、最大相関値算出部２２１における最大相関値の算出の詳細については後述する。【００４４】
ソーティング部２２２は、最大相関値算出部２２１から入力される各パルスの最大相関値を大きい方から順番に並べる（以下、ソーティング処理と称す）。また、ソーティング部２２２は、ソーティング結果に基づき、４本のパルスを２本ずつの２つのサブセットに分割し、分割結果を探索部２２４に出力する。なお、ソーティング部２２２におけるソーティング処理の詳細については後述する。【００４５】
前処理部２２３は、聴感重み付け部１１１における合成フィルタの係数Ｈを用いてマトリクスＨＨを算出する。また、前処理部２２３は、最大相関値算出部２２１から入力されるベクトルｙＨの要素の極性（＋−）から、パルスの極性ｐｏｌを決めて、探索部２２４に出力する。具体的には、前処理部２２３は、各位置に立つパルスの極性をｙＨのその位置の値の極性に合わせることとし、ｙＨの値の極性を別の配列に格納しておく。前処理部２２３は、各位置の極性を別の配列に格納した後、ｙＨの値に対し全て絶対値をとり正の値に変換しておく。また、前処理部２２３は、格納した各位置の極性に合わせて、ＨＨの値に対しても極性を乗ずることによって変換しておく。求められたｙＨおよびＨＨは、探索部２２４に出力される。【００４６】
探索部２２４は、ソーティング部２２２から入力される分割結果、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪み、および前処理部２２３から入力されるｙＨおよびＨＨを用いて固定符号帳の分割探索を行う。探索部２２４は、探索過程で得られる固定符号帳ベクトルの符号を固定符号帳１０４に出力し、探索結果として得られた固定符号帳ベクトルの符号をＣＥＬＰ符号化装置１００の外部に出力するとともに、ゲイン符号帳探索部２０３に出力する。なお、探索部２２４における固定符号帳の分割探索の詳細については後述する。【００４７】
次いで、最大相関値算出部２２１において各パルスの最大相関値を算出する処理について詳細に説明する。【００４８】
図３は、最大相関値算出部２２１における各パルスの最大相関値の算出手順を示すフロー図である。ここでは、最大相関値算出部２２１においてパルス０の相関値（ｙＨ）の値が最も大きくなる２つの候補位置を求め、これに基づきパルス０の最大相関値を算出する処理を例にとって説明する。【００４９】
まず、最大相関値算出部２２１は、予め定められたパルス０の候補位置の配列ｉｃｉ０［８］、および探索に用いる相関値ｙＨを正値に変換して得られる配列ｙＨ［３２］を確保する（ＳＴ１０１０）。【００５０】
次いで、最大相関値算出部２２１は、最大値ｍａｘ００、準最大値（２番目に大きい値）ｍａｘ０１、およびカウンタｉの初期化を行い（ＳＴ１０２０）、ＳＴ１０３０〜ＳＴ１０８０からなるループに移行する。【００５１】
このループにおいて、最大相関値算出部２２１は、カウンタｉの値が「８」以上である場合（ＳＴ１０４０：「ＹＥＳ」）には、各候補位置に対応する全てのループ処理が終わったと判断し、処理を終了する。一方、カウンタｉの値が「８」より小さい場合（ＳＴ１０４０：「ＮＯ」）には、最大相関値算出部２２１は、全てのループ処理が終わっていないと判断し、処理をＳＴ１０５０に移行する。【００５２】
次いで、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が最大値ｍａｘ００より大きい場合（ＳＴ１０５０：「ＹＥＳ」）には、最大相関値算出部２２１は、最大値ｍａｘ００を準最大値ｍａｘ０１として保存し、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］を最大値ｍａｘ００に代入してから（ＳＴ１０６０）、処理をＳＴ１０３０に戻す。カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が最大値ｍａｘ００以下である場合（ＳＴ１０５０：「ＮＯ」）には、最大相関値算出部２２１は処理をＳＴ１０７０に移行する。【００５３】
次いで、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が準最大値ｍａｘ０１より大きい場合（ＳＴ１０７０：「ＹＥＳ」）には、最大相関値算出部２２１は、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］を準最大値ｍａｘ０１に代入し、処理をＳＴ１０３０に戻す（ＳＴ１０８０）。一方、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が準最大値ｍａｘ０１以下である場合（ＳＴ１０７０：「ＮＯ」）には、最大相関値算出部２２１は、処理をＳＴ１０３０に戻す。【００５４】
次いで、ＳＴ１０３０において、最大相関値算出部２２１は、カウンタｉを１インクリメントしてから、処理をＳＴ１０４０に戻す。【００５５】
このようにして、最大相関値算出部２２１は各候補位置におけるパルス０単独の相関値の最大値ｍａｘ００および準最大値ｍａｘ０１を求める。そして、最大相関値算出部２２１は、図３に示した手順を流用して、パルス１，２，３単独の相関値（ｙＨ）の値が最も大きくなる候補位置を２つずつ求める。すなわち、最大相関値算出部２２１は、パルス１，２，３それぞれの単独の相関値の最大値および準最大値ｍａｘ１０，ｍａｘ１１，ｍａｘ２０，ｍａｘ２１，ｍａｘ３０，ｍａｘ３１を求める。【００５６】
次いで、最大相関値算出部２２１は、パルス０，１，２，３それぞれの単独の相関値の最大値および準最大値を用いて下記の式（５）従い、各パルスの最大相関値Ｓ［０］，Ｓ［１］，Ｓ［２］，Ｓ［３］を求める。式（５）に示すように、最大相関値算出部２２１は、各パルス単独の相関値の最大値に準最大値を所定の割合で加算することにより、各パルスに対応する安定した最大相関値を得る。
Ｓ［０］＝ｍａｘ００＋ｍａｘ０１×０．０５
Ｓ［１］＝ｍａｘ１０＋ｍａｘ１１×０．０５
Ｓ［２］＝ｍａｘ２０＋ｍａｘ２１×０．０５
Ｓ［３］＝ｍａｘ３０＋ｍａｘ３１×０．０５  …（５）【００５７】
次いで、ソーティング部２２２における、各パルスの最大相関値に対するソーティング処理について詳細に説明する。【００５８】
図４は、ソーティング部２２２における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図である。【００５９】
まず、ソーティング部２２２は、最大相関値算出部２２１から各パルスの最大相関値Ｓ［ｊ］（ｊ＝０，１，２，３）を入力し、何位までソーティングしたかを示すカウンタｉを「０」にリセットする（ＳＴ２０１０）。【００６０】
次いで、ソーティング部２２２は、カウンタｉの値が「４」以上である場合（ＳＴ２０３０：「ＹＥＳ」）には、全てのソーティングが終ったと判断し、処理をＳＴ２１００に移行する。一方、カウンタｉの値が４より小さい場合（ＳＴ２０３０：「ＮＯ」）には、ソーティング部２２２は、パルス番号Ｎ［ｉ］に「０」を代入し、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を探索するためのループの回数をカウントするカウンタｊを「０」にリセットし、最大値を格納する変数ｍａｘを「０」にリセットする（ＳＴ２０４０）。【００６１】
次いで、カウンタｊが４より小さい場合（ＳＴ２０６０：「ＮＯ」）には、ソーティング部２２２は処理をＳＴ２０７０に移行する。【００６２】
次いで、最大相関値Ｓ［ｊ］が変数ｍａｘより大きい場合（ＳＴ２０７０：「ＹＥＳ」）には、ソーティング部２２２は、最大相関値Ｓ［ｊ］を変数ｍａｘに代入し、カウンタｊの値を、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］に対応するパルス番号Ｎ［ｉ］に代入し（ＳＴ２０８０）、処理をＳＴ２０５０に移行する。一方、最大相関値Ｓ［ｊ］が変数ｍａｘ以下である場合（ＳＴ２０７０：「ＮＯ」）には、ソーティング部２２２は処理をＳＴ２０５０に移行する。次いで、ＳＴ２０５０において、ソーティング部２２２はカウンタｊを１インクリメントし、処理をＳＴ２０６０に戻す。【００６３】
一方、ＳＴ２０６０においてカウンタｊが４以上である場合（ＳＴ２０６０：「ＹＥＳ」）には、ソーティング部２２２は、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を探索するための、ＳＴ２０５０〜ＳＴ２０８０からなるループが終わったと判断し、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］に「−１」を代入する（ＳＴ２０９０）。これにより、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を、ｉ＋１位の最大相関値Ｓ［Ｎ［ｉ＋１］］を探索するためのループ処理の対象から排除する。次いで、ソーティング部２２２は、ＳＴ２０２０において、カウンタｉを１インクリメントし、処理をＳＴ２０３０に戻す。【００６４】
このようにして、ソーティング部２２２は、各パルスの最大相関値Ｓ［０］、Ｓ［１］、Ｓ［２］、Ｓ［３］を大きい方から順番に並べ、ソーティング結果を示すＮ［ｉ］を得る。以下、ソーティング部２２２においてＮ［ｉ］＝｛２，０，３，１｝を得た場合を例にとって説明する。すなわち、１番大きい最大相関値Ｓ［Ｎ［０］］に対応するパルスの番号Ｎ［０］の値が２であり、次の値は順次０，３，１であると仮定する。【００６５】
次いで、ＳＴ２１００において、ソーティング部２２２は、ソーティングされた最大相関値に対応する４本のパルス番号Ｎ［ｉ］を、予め設定された２つのサブセットの分割パターンにグルーピングして、パルスの探索順序を決定し、得られた探索順序を探索部２２４に出力する。すなわち、ソーティング部２２２は、探索部２２４の固定符号帳の分割探索において、先に探索する２パルスの番号および後に探索する２パルスの番号を決める。ソーティング部２２２では、予め下記の式（６）に示す３通りの探索順の候補が設定されている。
｛  第１サブセット    ｝  ｛  第２サブセット    ｝
第１候補  ｛Ｎ［０］，  Ｎ［１］｝  ｛Ｎ［２］，  Ｎ［３］｝
第２候補  ｛Ｎ［０］，  Ｎ［２］｝  ｛Ｎ［３］，  Ｎ［１］｝
第３候補  ｛Ｎ［０］，  Ｎ［３］｝  ｛Ｎ［１］，  Ｎ［２］｝
…（６）【００６６】
分割探索において、先に探索するサブセット（第１サブセット）および後に探索するサブセット（第２サブセット）の分割パターンは、多種存在する。そのうち、式（６）に示すように、最大相関値が最も大きいパルスＮ［０］を、先に探索するサブセット（第１サブセット）に含ませる分割パターンを採用すると、良好な符号化性能が得られる。【００６７】
式（６）の各探索順候補においては、先に探索するサブセット（第１サブセット）、次に、後で探索するサブセット（第２サブセット）という順番で探索が行われる。【００６８】
式（６）中のＮ［ｉ］を、ソーティングにより得られた具体的な値で表すと、下記の式（７）が得られ、第１候補、第２候補、第３候補の順に探索が行われる。
｛第１サブセット｝  ｛第２サブセット｝
第１候補      {２, ０}        {３, １}
第２候補      {２, ３}        {１, ０}
第３候補      {２, １}        {０, ３}  …（７）【００６９】
式（７）に示す３つの探索順は、下記の式（８）に示すＭ［３］［４］にまとめることができる。ここでＭ［３］［４］は、パルス４本に対して分割探索を３回行う場合のパルスの探索順を示す。
Ｍ［３］［４］＝｛｛２，０，３，１｝，｛２，３，１，０｝，｛２，１，０，３｝｝  …（８）【００７０】
すなわちソーティング部２２２は、探索順序としてＭ［３］［４］を探索部２２４に出力する。【００７１】
次いで、探索部２２４における固定符号帳の分割探索について詳細に説明する。【００７２】
図５および図６は、探索部２２４における固定符号帳の分割探索の手順を示すフロー図である。ここでは、代数的符号帳の条件を以下に示す。
（１）ビット数：１６ビット
（２）処理単位（サブフレーム長）：３２
（３）パルス本数：４本【００７３】
この条件のもと、以下のような代数的符号帳が設計できる。ｉｃｉ０［８］＝｛０，４，８，１２，１６，２０，２４，２８｝ｉｃｉ１［８］＝｛１，５，９，１３，１７，２１，２５，２９｝ｉｃｉ２［８］＝｛２，６，１０，１４，１８，２２，２６，３０｝ｉｃｉ３［８］＝｛３，７，１１，１５，１９，２３，２７，３１｝【００７４】
まず、探索部２２４は、ＳＴ３０１０において、固定符号帳の４本のパルスそれぞれの候補位置を示す配列ｉｃｉ０［８］、ｉｃｉ１［８］、ｉｃｉ２［８］、ｉｃｉ３［８］を用意し、ｙＨを正値に変換して得られた配列ｙＨ［３２］、ＨＨの極性を調整して得られた配列ＨＨ［３２］［３２］、およびｙＨを正値に変換する前のｙＨの極性値（−１，＋１）を格納したベクトルｐｏｌ［３２］を作成する。次いで、ＳＴ３０２０において、後続の探索ループに用いる変数の初期化が行われる。【００７５】
探索部２２４は、ＳＴ３０３０においてｊと数値「３」とを比較し、ｊが３以上の場合は探索を終了するためにＳＴ３２５０の処理へ進み、ｊが３より小さい場合はＳＴ３０５０の初期化へ進む。ＳＴ３０４０においてはｊを１インクリメントする。これにより、探索部２２４は、ソーティング部２２２から入力される探索順Ｍ［３］［４］が示す３つの探索順に対応して、２つのサブセットからなる分割探索を３回行う。【００７６】
ＳＴ３０５０〜ＳＴ３１３０は、第１サブセットの探索ループ処理を示す。具体的には、ＳＴ３０５０においては、第１サブセットの探索ループの初期化が行われる。次いで、探索部２２４は、判定ＳＴ３０６０においてｉ０と数値「８」とを比較し、ｉ０が８以上の場合は次の探索ループの初期化ＳＴ３１４０へ進み、ｉ０が８より小さい場合は処理ＳＴ３０７０へ進む。ＳＴ３０７０においてＭ［ｊ］［０］（ｊ＝０，１，２）が示すパルスの相関値ｓｙ０および音源パワｓｈ０を算出する。また、カウンタｉ１を０に初期化する。また、ＳＴ３０８０においては、ｉ０を１インクリメントする。これにより、探索部２２４は、Ｍ［ｊ］［０］（ｊ＝０，１，２）が示すパルスの８つの候補位置に対応して、８回のループ処理を行う。同様に、ＳＴ３０９０〜ＳＴ３１３０において、探索部２２４は、Ｍ［ｊ］［１］（ｊ＝０，１，２）が示すパルスの８つの候補位置に対応して、８回のループ処理を行う。【００７７】
まず、判定ＳＴ３０９０においてｉ１と数値「８」とを比較し、ｉ１が８以上の場合はインクリメント処理ＳＴ３０８０へ進み、ｉ１が８より小さい場合は処理ＳＴ３１００へ進む。ＳＴ３１００においては、探索部２２４は、前処理部２２３から入力されるｙＨおよびＨＨに加え、ＳＴ３０７０において算出された相関値ｓｙ０および音源パワｓｈ０を用いて、Ｍ［ｊ］［１］（ｊ＝０，１，２）が示すパルスの相関値ｓｙ１および音源パワｓｈ１を算出する。【００７８】
ＳＴ３１２０において、探索部２２４は、第１サブセットの処理対象となる各パルスの相関値と音源パワとを用いて式（４）に従い関数Ｃの値を算出および比較し、より大きい関数値を示す場合のｉ０、ｉ１をｉｉ０、ｉｉ１に上書き格納し、また関数Ｃの分子項、分母項を上書き格納する（ＳＴ３１３０）。なお、ＳＴ３１２０においては計算量の多い除算を避け、分母項と分子項のたすき掛けの乗算により算出および比較を行っている。上記判定において、より小さい場合、またより大きい場合で処理ＳＴ３１３０を行った場合はインクリメント処理ＳＴ３１１０へ進む。インクリメント処理ＳＴ３１１０においては、ｉ１を１インクリメントする。【００７９】
ＳＴ３１４０〜ＳＴ３２２０は、第２サブセットの探索ループ処理を示す。なお、第２サブセットの探索ループ処理は、ＳＴ３０５０〜ＳＴ３１３０に示した第１サブセットの探索ループ処理と基本的に同様なステップを有する。ここでは、第１サブセットの探索ループ処理との相違点のみについて説明する。まず、ＳＴ３１４０における、第２サブセットの探索ループ処理の初期化は、第１サブセットの探索ループ処理の結果を用いて行われる。また、第２サブセットの探索ループ処理の処理対象は、Ｍ［ｊ］［２］（ｊ＝０，１，２）およびＭ［ｊ］［３］（ｊ＝０，１，２）それぞれが示すパルスである。また処理ＳＴ３１６０においては、第１サブセットの探索ループで探索され、格納されたカウンタ情報ｉｉ０、ｉｉ１を用いてパルス２に対する相関値ｓｙ２および音源パワｓｈ２を算出する。また、同様に、処理ＳＴ３１９０においては、第１サブセットの探索ループで探索され、格納されたカウンタ情報ｉｉ０、ｉｉ１を用いてパルス３に対する相関値ｓｙ３および音源パワｓｈ３を算出する。【００８０】
次いで、ＳＴ３２３０およびＳＴ３２４０において、探索部２２４は、分割探索全体において関数Ｃの値が最も大きくなるパルスの位置の組合せを求める。【００８１】
次いで、ＳＴ３２５０において、探索部２２４は、ｉｉ０、ｉｉ１、ｉｉ２、ｉｉ３を各パルスの位置情報とする。また、配列ｐｏｌの値が極性（±１）であり、探索部２２４は、極性ｐ０、ｐ１、ｐ２、ｐ３を下記の式（９）に従って０または１に変換して１ビットで符号化する。
ｐ０＝（ｐｏｌ［ｉｃｈｉ０［ｉｉ０］］＋１）／２
ｐ１＝（ｐｏｌ［ｉｃｈｉ１［ｉｉ１］］＋１）／２
ｐ２＝（ｐｏｌ［ｉｃｈｉ２［ｉｉ２］］＋１）／２
ｐ３＝（ｐｏｌ［ｉｃｈｉ３［ｉｉ３］］＋１）／２  …（９）【００８２】
ここで、位置情報および極性に対する復号方法としては、ｉｃｈｉ０［ｉｉ０］、ｉｃｈｉ１［ｉｉ１］、ｉｃｈｉ２［ｉｉ２］、ｉｃｈｉ３［ｉｉ３］によりパルスの位置が復号され、復号した位置と極性を用いて固定符号帳ベクトルが復号される。【００８３】
図５および図６に示すように、探索部２２４は、２つのサブセットからなる分割探索を行うため、全探索の場合に比べて計算量を大きく削減できる。具体的には、全探索においては８の４乗で４０９６回のループ処理を行うのに対し、図５および図６に示す方法によれば２つのサブセットの探索それぞれにおいては、８の２乗で６４回ずつのループ処理を行う。そして、Ｍ［３］［４］に対応して２つのサブセットからなる分割探索を３回行うため、６４×２サブセット×３倍で合計３８４回のループ処理を行う。これは全探索の約１／１０の計算量である。【００８４】
このように、本実施の形態によれば、固定符号帳に対して分割探索を行うため、固定符号帳に対して全探索を行う場合に比べ、計算量を削減することができる。【００８５】
さらに、本実施の形態によれば、分割探索において固定符号帳を構成するパルスを、先に探索するサブセットおよび後に探索するサブセットに分割する際に、最大相関値が最も大きいパルスを用いて先に探索するサブセットを構成するため、分割探索による符号化歪みを抑えることができる。すなわち、全探索を行う場合でも、最大相関値が高い位置のパルスは採用される可能性が高く、分割探索において先に探索することにより符号化歪みを抑えることができる。【００８６】
なお、本実施の形態ではパルス数が４であり、分割数が２である場合について説明したが、本発明はパルス数または分割数に依存せず、各パルスの最大相関値をソーティングした結果に基づいて探索するパルスの順番を決めれば、本実施の形態と同様な効果を得ることができる。【００８７】
また、本実施の形態では、最大相関値算出部２２１は、各パルス単独の相関値の最大値に準最大値を所定の割合で加算して最大相関値を算出する場合を例にとって説明した。しかし、本発明はこれに限定されず、さらに各パルスの３番目に大きい単独の相関値を所定の割合で加算して最大相関値を算出しても良く、または、各パルス単独の相関値の最大値をそのまま最大相関値としても良い。【００８８】
また、本実施の形態では各パルスの候補位置の予備選択を行わない場合を例にとって説明したが、本発明はこれに限定されず、各パルスの候補位置の予備選択を行ってからソーティングを行っても良い。これにより、ソーティングの効率を向上することができる。【００８９】
また、本実施の形態では固定符号帳として代数的符号帳を用いる場合を例にとって説明したが、本発明はこれに限定されず、固定符号帳としてマルチパルス符号帳を用いても良い。すなわち、マルチパルスの位置情報および極性情報を用いて本実施の形態に適用することが可能である。【００９０】
また、本実施の形態では音声符号化方法としてＣＥＬＰ符号化方式を用いる場合を例にとって説明したが、本発明はこれに限定されず、音声符号化方法として、本数が分かる音源ベクトルが格納されている符号帳を用いる符号化方式であれば良い。これは、本発明に係る分割探索は、固定符号帳の探索のみに対して行われ、適応符号帳の有無や、スペクトル包絡の分析方法がＬＰＣ、ＦＦＴ、またはフィルタバンクであるか否かに依存しないからである。【００９１】
（実施の形態２）
本発明の実施の形態２は、実施の形態１と基本的に同様であり、ソーティング部２２２におけるソーティング処理（図４参照）のみ実施の形態１と相違する。以下、図２において、ソーティング部２２２に代えて、本実施の形態に係るソーティング部を「４２２」という符号を付して配置し、ソーティング部４２２（図示せず）におけるソーティング処理のみについて説明する。【００９２】
図７は、本実施の形態に係るソーティング部４２２における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図である。なお、図７に示す手順は、図４に示した手順と基本的に同様なステップを有しており、同一のステップには同一の符号を付し、その説明を省略する。【００９３】
ＳＴ４０４０において、ソーティング部４２２は、パルス番号Ｎ［ｉ］に「０」を代入し、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を探索するためのループの回数をカウントするカウンタｊを「０」にリセットし、最大値を格納する変数ｍａｘを「０」にリセットし、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を保存するための変数Ｌ［ｉ］に「０」を代入する。【００９４】
ＳＴ４０９０において、ソーティング部４２２は、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］をＬ［ｉ］に代入し、Ｓ［Ｎ［ｉ］］に「−１」を代入する。これにより、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］をＬ［ｉ］に保存し、また、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を、ｉ＋１位の最大相関値Ｓ［Ｎ［ｉ＋１］］を探索するためのループ処理の対象から排除する。【００９５】
ＳＴ２０１０〜ＳＴ４０９０までの処理によって、ソーティング部４２２は、各パルスの最大相関値Ｓ［０］、Ｓ［１］、Ｓ［２］、Ｓ［３］を大きい方から順番に並べ、ソーティング結果を示すＮ［ｉ］、およびＬ［ｉ］を得る。【００９６】
ＳＴ４１００において、ソーティング部４２２は、ソーティングされた最大相関値に対応する４本のパルス番号Ｎ［ｉ］を、予め設定された２つのサブセットの分割パターンにグルーピングして、パルスの探索順序を決定し、得られた探索順序を探索部２２４に出力する。すなわち、ソーティング部４２２は、探索部２２４の固定符号帳の分割探索において、先に探索する２パルスの番号および後に探索する２パルスの番号を決める。ソーティング部４２２では、予め３通りの探索順の候補が設定されている。ここで実施の形態１のソーティング部２２２と異なるのは、第３候補において、最大相関値が格納されたＬ［ｉ］を用いて探索順を決定する点である。【００９７】
具体的には、ソーティング部４２２は、まず、ソーティング結果Ｎ［ｉ］を用いた、下記の式（１０）に示す第１候補と第２候補との２つの探索順候補が設定されている。すなわちソーティング部４２２は、式（１０）に示すように、第１候補と第２候補とにおいて最大相関値が最も大きいパルスを先に探索するサブセットに含ませ、符号化性能を向上する。
｛  第１サブセット    ｝  ｛  第２サブセット    ｝
第１候補  ｛Ｎ［０］，  Ｎ［１］｝  ｛Ｎ［２］，  Ｎ［３］｝
第２候補  ｛Ｎ［０］，  Ｎ［２］｝  ｛Ｎ［３］，  Ｎ［１］｝  …（１０）【００９８】
次いで、ソーティング部４２２は、以下のようにソーティング結果Ｎ［ｉ］およびＬ［ｉ］を用いて３つ目の探索順候補が設定されている。すなわち、ソーティング部４２２は、Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１以上であるか否かを判断し、Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１以上である場合には、第３候補として｛Ｎ［２］，  Ｎ［３］｝  ｛Ｎ［０］，  Ｎ［１］｝が適用される。Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１より小さい場合には、ソーティング部４２２は続けて、Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４以上であるか否かを判断する。Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４以上である場合には、ソーティング部４２２は、第３候補として｛Ｎ［１］，  Ｎ［３］｝  ｛Ｎ［２］，  Ｎ［０］｝が適用される。Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４より小さい場合には、ソーティング部４２２は続けて、Ｌ［０］＋Ｌ［３］がＬ［１］＋Ｌ［２］以上であるか否かを判断する。ソーティング部４２２は、Ｌ［０］＋Ｌ［３］がＬ［１］＋Ｌ［２］以上である場合に、第３候補として｛Ｎ［０］，  Ｎ［３］｝  ｛Ｎ［１］，  Ｎ［２］｝を生成し、Ｌ［０］＋Ｌ［３］がＬ［１］＋Ｌ［２］より小さい場合に、第３候補として｛Ｎ［１］，  Ｎ［２］｝  ｛Ｎ［３］，  Ｎ［０］｝が適用される。【００９９】
ソーティング部４２２は、第３候補の探索順を適用する際に、後程探索部２２４の探索における冗長性を低減するために、各パルスの最大相関値の差がわずかである場合には、必ずしも最大相関値が最も大きいパルスを含まず先に探索するサブセットを構成する。すなわち、ソーティング部４４２は、ソーティング結果Ｎ［ｉ］に基づき各パルスの最大相関値の組合せを複数個構成し、構成された複数個の組合せに係数を掛けて比較した結果に基づき、４つのパルスを２つずつのサブセットにグルーピングする。【０１００】
例えば、ソーティング結果としてＮ［ｉ］＝｛２，０，３，１｝、Ｌ［ｉ］＝｛９．５，  ９．０，  ８．５，  ８．０｝が得られた場合に、Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１より小さく、Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４以上となる。従って、ソーティング部４２２は、第３候補として｛Ｎ［１］，  Ｎ［３］｝  ｛Ｎ［２］，  Ｎ［０］｝を適用する。【０１０１】
Ｎ［ｉ］を具体的な値で表すと、第１候補、第２候補、第３候補は下記の式（１１）で表される。
｛第１サブセット｝｛第２サブセット｝
第１候補    {２，０}        {３，１}
第２候補    {２，３}        {１，０}
第３候補    {０，１}        {３，２}  …（１１）【０１０２】
式（１１）に示す３つの探索順候補を下記の式（１２）に示すＭ［３］［４］にまとめることができる。
Ｍ［３］［４］＝｛｛２，０，３，１｝，｛２，３，１，０｝，｛０，１，３，２｝｝  …（１２）【０１０３】
ソーティング部４２２は、探索順候補としてＭ［３］［４］を探索部２２４に出力する。【０１０４】
このように、本実施の形態によれば、分割探索において固定符号帳を構成するパルスを、先に探索するサブセットおよび後に探索するサブセットに分割する際に、各パルスの最大相関値の順位だけではなく、各パルスの最大相関値の値に基づき、必ずしも最大相関値が最も大きいパルスを含まず先に探索するサブセットを構成する。これにより、分割探索における探索の冗長性を低減することができる。【０１０５】
なお、本実施の形態では、３番目の探索順候補を適用する際に０．９１、０．９４などの係数を用いる場合を例にとって説明したが、本発明はこれに限定されず、統計により予め決められたほかの係数を用いても良い。【０１０６】
また、本実施の形態では、３番目の探索順候補を適用する際にＮ［ｉ］に加えＬ［ｉ］をさらに用いる場合を例にとって説明したが、本発明はこれに限定されず、１番目の探索順候補または２番目の探索順候補を適用する際でも、Ｎ［ｉ］およびＬ［ｉ］の両方を用いても良い。【０１０７】
（実施の形態３）
本発明の実施の形態３は、実施の形態１と基本的に同様であり、各サブセットにグルーピングしたパルスをさらに所定の順番に従って並び替える点のみが実施の形態１と相違する。すなわち、本実施の形態は、図４に示したソーティング処理の一部のみにおいて実施の形態１と相違する。以下、図２において、ソーティング部２２２に代えて、本実施の形態に係るソーティング部を「５２２」という符号を付して配置し、ソーティング部５２２（図示せず）におけるソーティング処理のみについて説明する。【０１０８】
図８は、本実施の形態に係るソーティング部５２２において各パルスの最大相関値に対してソーティング処理を行う手順を示すフロー図である。なお、図８に示す手順は、図４に示した手順と基本的に同様なステップを有しており、同一のステップには同一の符号を付し、その説明を省略する。【０１０９】
図８に示すＳＴ５１００においてソーティング部５２２は、実施の形態１に係るソーティング部２２２が図４に示したＳＴ２１００において行った処理と基本的に同様な処理を行うが、得られたＭ［３］［４］をすぐには探索部２２４に出力せず、以下のＳＴ５１１０の処理を行ってから、探索部２２４へ出力する点において相違する。【０１１０】
ＳＴ５１１０においてソーティング部５２２は、Ｍ［３］［４］に含まれる要素を２つずつまとめてＭ’［６］［２］を構成し、Ｍ’［６］［２］に含まれる２つずつのパルスの順番を｛０，１｝、｛１，２｝、｛２，３｝、｛３，０｝、｛０，２｝、｛１，３｝の何れかに並べ替えるという調整を行う。【０１１１】
図９は、図８に示したＳＴ５１１０におけるソーティング部５２２の処理手順を詳細に示すフロー図である。【０１１２】
まず、ＳＴ６０１０において、ソーティング部５２２は変数「ｉ」を「０」に初期化する。【０１１３】
次いで、ＳＴ６０２０において、ソーティング部５２２は「ｉ」が「６」に等しいか否かを判定する。【０１１４】
ＳＴ６０２０において「ｉ」が「６」と等しいと判定した場合（ＳＴ６０２０：「ＹＥＳ」）には、ソーティング部５２２は図９に示した処理（すなわちＳＴ５１１０の処理）を終了する。【０１１５】
一方、ＳＴ６０２０において「ｉ」が「６」と等しくないと判定した場合（ＳＴ６０２０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０３０に移行する。【０１１６】
ＳＴ６０３０において、ソーティング部５２２はＭ’［ｉ］［１］＝「２」であって、かつＭ’［ｉ］［２］＝「１」であるか否かを判定する。【０１１７】
ＳＴ６０３０において、Ｍ’［ｉ］［１］＝「２」であって、かつＭ’［ｉ］［２］＝「１」であると判定した場合（ＳＴ６０３０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６０４０においてＭ’［ｉ］［１］を「１」に設定し、Ｍ’［ｉ］［２］を「２」に設定してから処理をＳＴ６１５０に移行する。【０１１８】
一方、ＳＴ６０３０において、Ｍ’［ｉ］［１］＝「２」であって、かつＭ’［ｉ］［２］＝「１」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０３０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０５０に移行する。【０１１９】
ＳＴ６０５０において、ソーティング部５２２はＭ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「２」であるか否かを判定する。【０１２０】
ＳＴ６０５０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「２」であると判定した場合（ＳＴ６０５０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６０６０においてＭ’［ｉ］［１］を「２」に設定し、Ｍ’［ｉ］［２］を「３」に設定してから処理をＳＴ６１５０に移行する。【０１２１】
一方、ＳＴ６０５０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「２」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０５０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０７０に移行する。【０１２２】
ＳＴ６０７０において、ソーティング部５２２はＭ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「３」であるか否かを判定する。【０１２３】
ＳＴ６０７０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「３」であると判定した場合（ＳＴ６０７０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６０８０においてＭ’［ｉ］［１］を「３」に設定し、Ｍ’［ｉ］［２］を「４」に設定してから処理をＳＴ６１５０に移行する。【０１２４】
一方、ＳＴ６０７０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「３」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０７０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０９０に移行する。【０１２５】
ＳＴ６０９０において、ソーティング部５２２はＭ’［ｉ］［１］＝「１」であって、かつＭ’［ｉ］［２］＝「４」であるか否かを判定する。【０１２６】
ＳＴ６０９０において、Ｍ’［ｉ］［１］＝「１」であって、かつＭ’［ｉ］［２］＝「４」であると判定した場合（ＳＴ６０９０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６１００においてＭ’［ｉ］［１］を「４」に設定し、Ｍ’［ｉ］［２］を「１」に設定してから処理をＳＴ６１５０に移行する。【０１２７】
一方、ＳＴ６０９０において、Ｍ’［ｉ］［１］＝「１」であって、かつＭ’［ｉ］［２］＝「４」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０９０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６１１０に移行する。【０１２８】
ＳＴ６１１０において、ソーティング部５２２はＭ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「１」であるか否かを判定する。【０１２９】
ＳＴ６１１０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「１」であると判定した場合（ＳＴ６１１０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６１２０においてＭ’［ｉ］［１］を「１」に設定し、Ｍ’［ｉ］［２］を「３」に設定してから処理をＳＴ６１５０に移行する。【０１３０】
一方、ＳＴ６１１０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「１」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６１１０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６１３０に移行する。【０１３１】
ＳＴ６１３０において、ソーティング部５２２はＭ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「２」であるか否かを判定する。【０１３２】
ＳＴ６１３０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「２」であると判定した場合（ＳＴ６１３０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６１４０においてＭ’［ｉ］［１］を「２」に設定し、Ｍ’［ｉ］［２］を「４」に設定してから処理をＳＴ６１５０に移行する。【０１３３】
一方、ＳＴ６１３０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「２」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６１３０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６１５０に移行する。【０１３４】
ＳＴ６１５０において、ソーティング部５２２は、「ｉ」を１インクリメントしてから処理をＳＴ６０２０に移行する。【０１３５】
例えばソーティング部５２２は、Ｍ［３］［４］＝｛｛２，０，３，１｝，｛２，３，１，０｝，｛２，１，０，３｝｝を用いてＭ’［６］［２］＝｛｛２，０｝，｛３，１｝，｛２，３｝，｛１，０｝，｛２，１｝，｛０，３｝｝を構成した場合、さらに図９に示した手順に従ってＭ’［６］［２］に含まれる２つずつのパルスの順番を調整すると、Ｍ’［６］［２］＝｛｛０，２｝，｛１，３｝，｛２，３｝，｛０，１｝，｛１，２｝，｛３，０｝｝が得られる。ソーティング部５２２は、調整により得られたＭ’［６］［２］＝｛｛０，２｝，｛１，３｝，｛２，３｝，｛０，１｝，｛１，２｝，｛３，０｝｝を用いて再びＭ［３］［４］＝｛｛０，２，１，３｝，｛２，３，０，１｝，｛１，２，３，０｝｝を構成して探索部２２４に出力する。【０１３６】
以下、図９に示したソーティング部５２２における調整処理の効果について説明する。【０１３７】
固定符号帳を構成するパルスの探索は上記の式（４）の関数Ｃを最も大きくするパルス位置および極性を探索することにより行われる。従って、探索の際には式（４）の分母項の「ＨＨ」のマトリクスに対応するメモリ（ＲＡＭ：Random Access Memory）が必要になる。例えば音源ベクトルの長さが３２である場合には、３２×３２の対角ベクトルを含む半分のマトリクスに対応するメモリが必要になる。すなわち（３２×３２／２＋１６）バイト＝５２８バイトのメモリが必要になる。ただし、計算の際に指定のインデックスにアクセスする計算量を少なくするためにはフルマトリクス（３２×３２バイト＝１０２４バイト）に対応するメモリが必要になるため、さらに大きなメモリが必要になる。【０１３８】
これに対し、本発明のように、固定符号帳を構成するパルスを先に探索するサブセットおよび後に探索するサブセット（ペア）に分割し、ペア毎にパルスの探索を行うと、１ペア当たりのエントリ数の２乗である８×８のマトリクスがあれば良いため、メモリを８×８×６バイト＝３８４バイトに節約することができる。ただし、このマトリクスは対称行列ではないため、パルスの番号の順番が逆になるとマトリクスが異なるようになり、逆のマトリクスを別途用意する（メモリが倍になってしまう）か、探索の際のアクセス方法を変える（計算量が増えてしまう）か、ペアの組み合わせ毎にプログラムを用意する（メモリと計算量が増えてしまう）必要がある。そこで、本実施の形態においては、ペア毎の探索を行う際にパルスの順番を並べ替え、すべての探索を６つのペアに限定する。これにより、パルス探索に必要なメモリを上記３８４バイトに限定することができ、計算量も削減することができる。【０１３９】
このように、本実施の形態によれば、固定符号帳を構成するパルスをペアにグルーピングする際に、グルーピングされるパルスを所定の順番に並び替え、ペア毎にパルスの探索を行うため、固定符号帳の探索に必要なメモリと計算量を削減することができる。【０１４０】
なお、本実施の形態では、パルスを探索するペアを｛０，１｝、｛１，２｝、｛２，３｝、｛３，０｝、｛０，２｝、｛１，３｝の６通りに限定する場合を例にとって説明したが、本発明はこれに限定されず、上記の各ペアに含まれるパルスの順番を逆にしても良く、これによりパルス探索の平均的性能が変わることはない。【０１４１】
以上、本発明の各実施の形態について説明した。【０１４２】
なお、上記各実施の形態に係る固定符号帳は、雑音符号帳、確率符号帳（stochastic codebook）、または乱数符号帳（random codebook）と呼ばれることもある。【０１４３】
また、適応符号帳は、適応音源符号帳と呼ばれることもあり、固定符号帳は、固定音源符号帳と呼ばれることもある。【０１４４】
また、ＬＳＰは、ＬＳＦ（Line Spectral Frequency）と呼ばれることもあり、ＬＳＰをＬＳＦと読み替えてもよい。また、ＬＳＰの代わりにＩＳＰ（ImmittanceSpectrum Pairs）をスペクトルパラメータとして符号化する場合もあるが、この場合はＬＳＰをＩＳＰに読み替えればＩＳＰ符号化装置として上記各実施の形態を利用することができる。【０１４５】
また、上記各実施の形態では、本発明をハードウェアで構成する場合を例にとって説明したが、本発明はソフトウェアで実現することも可能である。【０１４６】
また、上記各実施の形態の説明に用いた各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部または全てを含むように１チップ化されてもよい。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。【０１４７】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用してもよい。【０１４８】
さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適用等が可能性としてありえる。【０１４９】
２００７年７月２７日出願の特願２００７−１９６７８２、２００７年１０月３日出願の特願２００７−２６０４２６および２００８年１月１６日出願の特願２００８−００７４１８の日本出願に含まれる明細書、図面および要約書の開示内容は、すべて本願に援用される。
【産業上の利用可能性】
【０１５０】
本発明にかかる音声符号化装置及び音声符号化方法は、ビットを有効に利用した固定符号帳により音声符号化を行うことができ、例えば、移動体通信システムにおける携帯電話等に適用できる。
【図１】
2009016816.tif 000007
【図２】
2009016816.tif 000008
【図３】
2009016816.tif 000009
【図４】
2009016816.tif 000010
【図５】
2009016816.tif 000011
【図６】
2009016816.tif 000012
【図７】
2009016816.tif 000013
【図８】
2009016816.tif 000014
【図９】
2009016816.tif 000015
【手続補正書】
【提出日】平成21年12月1日(2009.12.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出する算出手段と、
パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するソーティング手段と、
前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を得る探索手段と、
を具備する音声符号化装置。
【請求項２】
前記算出手段は、
前記各パルスの相関値の最大値を用いて算出された前記各パルスの最大相関値を、前記代表値として算出し、
前記ソーティング手段は、
前記最大相関値をソーティングする、
請求項１記載の音声符号化装置。
【請求項３】
前記ソーティング手段は、
パルス毎に得られた前記代表値のうち最大の代表値に対応するパルスを含むサブセットを前記第１のサブセットとする、
請求項１記載の音声符号化装置。
【請求項４】
前記ソーティング手段は、
ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットの複数の組み合わせそれぞれに対してグルーピングし、前記複数の組み合わせのそれぞれから、前記第１のサブセットをそれぞれ決定し、
前記探索手段は、
前記第１のサブセットそれぞれを用いて前記固定符号帳を探索し、そのうち符号化歪みが最小となる前記符号を得る、
請求項１記載の音声符号化装置。
【請求項５】
前記算出手段は、
パルス毎に、２番目に大きい前記相関値に所定の割合を乗じた値を、前記相関値の最大値に加算して、前記各パルスの最大相関値を算出する、
請求項２記載の音声符号化装置。
【請求項６】
前記ソーティング手段は、
グルーピングされたパルスに対応する前記代表値を用いて、前記第１のサブセットを決定する、
請求項１記載の音声符号化装置。
【請求項７】
前記ソーティング手段は、
グルーピングされたパルスに対応する前記代表値の組み合わせを複数生成し、前記組み合わせに予め設定した値を乗じて比較した結果に基づき、前記第１のサブセットを決定する、
請求項１記載の音声符号化装置。
【請求項８】
前記ソーティング手段は、
前記複数のサブセットにグルーピングするパルスを予め決められた順番に並び替える、
請求項１記載の音声符号化装置。
【請求項９】
固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出するステップと、
パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するステップと、
前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を生成するステップと、
を有する音声符号化方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音声符号化装置および音声符号化方法に関し、特に固定符号帳探索を行う音声符号化装置および音声符号化方法に関する。
【背景技術】
【０００２】
移動体通信においては、伝送帯域の有効利用のために音声や画像のディジタル情報の圧縮符号化が必須である。その中でも携帯電話で広く利用される音声コーデック（符号化／復号）技術に対する期待は大きく、圧縮率の高い従来の高効率符号化に対してさらなる音質の要求が強まっている。
【０００３】
近年、多層構造を有するスケーラブルコーデックの標準化がＩＴＵ−Ｔ(International
Telecommunication Union Telecommunication Standardization Sector)、ＭＰＥＧ（Moving Picture Expert Group）等で検討されており、より効率的で高品質な音声コーデックが求められている。
【０００４】
音声の発声機構をモデル化してベクトル量子化を巧みに応用した基本方式「ＣＥＬＰ」（Code Excited Linear Prediction）によって大きく性能を向上させた音声符号化技術は、非特許文献１に記載の代数的符号帳（Algebraic Codebook）のような少数パルスによる固定音源の技術により、一段とその性能を向上させた。ＩＴＵ−Ｔ標準Ｇ．７２９や、ＥＴＳＩ（European Telecommunications Standards Institute）標準ＡＭＲ（Adaptive Multi-Rate）は、代数的符号帳を用いたＣＥＬＰの代表的なコーデックであり、世界で広く使用されている。
【０００５】
代数的符号帳を用いて音声符号化を行う場合、代数的符号帳を構成する１つ１つのパルスの相互の影響を考慮し、全てのパルスの組み合わせを探索する（以下、全探索と称す）ことが望ましい。しかし、パルス数が多くなると探索に必要な計算量が指数関数的に増加してしまう。これに対し、非特許文献２には、全探索の場合の性能をほぼ維持しながら計算量を大幅に低減できる代数的符号帳の探索方法として、分割探索、枝刈探索、ビタビ探索などを開示している。
【０００６】
その中でも分割探索は最も簡単でかつ計算量削減の効果が大きい方法である。分割探索とは、１つの閉ループ探索を複数のより小さい閉ループに分割して、複数の閉ループ探索の開ループ探索にする方法である。分割探索においては、分割数に応じて大きく計算量を下げることが出来る。分割探索は国際標準方式でも使用されており、第３世代携帯電話の標準コーデックであるＥＴＳＩ標準ＡＭＲの代数的符号帳の探索においては、４本のパルスを２つのサブセットに分けて分割探索を行う。
【０００７】
例えば、８つの位置候補を持つパルスが４本ある場合を考えると、４本のパルスをすべて１つの閉ループで探索するには、評価しなければならないパルスの組み合わせが８の４乗で４０９６通りとなる。これに対し、ＥＴＳＩ標準ＡＭＲは、４本のパルスを２本と２本の２つのサブセットに分割して、それぞれを閉ループで探索する。従って、ＥＴＳＩ標準ＡＭＲにおいて評価しなければならないパルスの組み合わせは８の２乗の２倍で１２８通りとなり、全探索の場合と比べて３２分の１の計算量となる。さらに、ＥＴＳＩ標準ＡＭＲにおける各評価は、４パルスよりも少ない２パルスに対して行われるため、計算量はさらに低減される。
【非特許文献１】Salami, Laflamme, Adoul,”8kbit/s ACELP Coding of Speech with 10ms Speech-Frame:aCandidate for CCITT Standardization”,IEEE Proc. ICASSP94,pp.II-97n
【非特許文献２】野村ほか、「ＣＥＬＰにおけるパルス励振源の効果的な探索法」、日本音響学会春季講演論文集２−Ｐ−５、平成８年３月、pp.311-312
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、代数的符号帳の分割探索による音声符号化の性能は、概して全探索の場合に比べ低い。なぜなら最初に決まる２本のパルスの位置が最適であるとは限らないからである。
【０００９】
従って、分割探索では先に探索するサブセットを構成するパルスとして何を選ぶかによって、音声符号化の性能を改善する余地がある。例えば、４本のパルスの中でランダムに２つを選んで探索することを複数回行い、そのうち符号化性能が一番良い結果を得る方法が考えられる。例えば、サブセットのペアを４種類用意し、４種類のペアに対してそれぞれ探索を行うことによって、音声符号化の性能を全探索による符号化性能に近づけることが出来る。この場合、１２８（８の２乗の２倍）の４倍で５１２通りの計算が必要になるものの、それでも全探索の場合の計算量の１／８である。ただし、上記例ではサブセットを任意に構成しており、また４種類のペアのいずれにも特に先に探索する理由はない。従って、複数のケースについて探索を行う場合に得られる符号化性能はバラツキがあり、総合的に符号化性能は十分ではない。
【００１０】
本発明の目的は、代数的符号帳に対して分割探索を行いつつ、符号化性能を向上することができる音声符号化装置および音声符号化方法を提供することである。
【課題を解決するための手段】
【００１１】
本発明の音声符号化装置は、固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出する算出手段と、パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するソーティング手段と、前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を得る探索手段と、を具備する構成をとる。
【００１２】
本発明の音声符号化方法は、固定符号帳を構成する複数のパルスそれぞれとターゲット信号とを用いてパルス候補位置それぞれにおける相関値を算出し、パルス毎に、前記相関値の最大値を用いてパルスに関する代表値を算出するステップと、パルス毎に得られた前記代表値をソーティングし、ソーティングした前記代表値に対応するそれぞれのパルスを、予め設定された複数のサブセットにグルーピングし、前記複数のサブセットから、最初に探索する第１のサブセットを決定するステップと、前記第１のサブセットを用いて前記固定符号帳を探索し、符号化歪みが最小となる前記複数のパルスの位置および極性を示す符号を生成するステップと、を有するようにした。
【発明の効果】
【００１３】
本発明によれば、音声符号化において固定符号帳の分割探索を行う際、たとえば最大相関値のような、パルスに関する代表値を用いて、先に探索するサブセットを決定するため、代数的符号帳に対して分割探索を行いつつ、符号化性能を向上することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００１５】
（実施の形態１）
図１は、本発明の実施の形態１に係るＣＥＬＰ符号化装置１００の構成を示すブロック図である。ここでは、本発明に係る音声符号化装置としてＣＥＬＰ方式の符号化装置を例にとって説明する。
【００１６】
図１において、ＣＥＬＰ符号化装置１００は、声道情報と音源情報とからなる音声信号Ｓ１１を、声道情報については、ＬＰＣパラメータ（線形予測係数）を求めることにより符号化し、音源情報については、予め記憶されている音声モデルのいずれを用いるかを特定するインデックスを求めることにより符号化する。すなわち、音源情報については、適応符号帳１０３および固定符号帳１０４でどのような音源ベクトル（コードベクトル）を生成するかを特定するインデックスを求めることにより符号化する。
【００１７】
具体的には、ＣＥＬＰ符号化装置１００の各部は以下の動作を行う。
【００１８】
ＬＰＣ分析部１０１は、音声信号Ｓ１１に対して線形予測分析を施し、スペクトル包絡情報であるＬＰＣパラメータを求め、求めたＬＰＣパラメータをＬＰＣ量子化部１０２および聴感重み付け部１１１に出力する。
【００１９】
ＬＰＣ量子化部１０２は、ＬＰＣ分析部１０１から出力されたＬＰＣパラメータを量子化し、得られた量子化ＬＰＣパラメータをＬＰＣ合成フィルタ１０９に、量子化ＬＰＣパラメータのインデックスをＣＥＬＰ符号化装置１００の外部へ出力する。
【００２０】
一方、適応符号帳１０３は、ＬＰＣ合成フィルタ１０９で使用された過去の駆動音源を記憶しており、後述する歪み最小化部１１２から指示されたインデックスに対応する適応符号帳ラグに従って、記憶している駆動音源から１サブフレーム分の音源ベクトルを生成する。この音源ベクトルは、適応符号帳ベクトルとして乗算器１０６に出力される。
【００２１】
固定符号帳１０４は、所定形状の音源ベクトルを複数個予め記憶しており、歪み最小化部１１２から指示されたインデックスに対応する音源ベクトルを、固定符号帳ベクトルとして乗算器１０７に出力する。ここで、固定符号帳１０４は代数的音源であり、代数的符号帳を用いた場合について説明する。代数的音源とは、多くの標準コーデックに採用され
ている音源である。
【００２２】
なお、上記の適応符号帳１０３は、有声音のように周期性の強い成分を表現するために使われ、一方、固定符号帳１０４は、白色雑音のように周期性の弱い成分を表現するために使われる。
【００２３】
ゲイン符号帳１０５は、歪み最小化部１１２からの指示に従って、適応符号帳１０３から出力される適応符号帳ベクトル用のゲイン（適応符号帳ゲイン）、および固定符号帳１０４から出力される固定符号帳ベクトル用のゲイン（固定符号帳ゲイン）を生成し、それぞれ乗算器１０６、１０７に出力する。
【００２４】
乗算器１０６は、ゲイン符号帳１０５から出力された適応符号帳ゲインを、適応符号帳１０３から出力された適応符号帳ベクトルに乗じ、加算器１０８に出力する。
【００２５】
乗算器１０７は、ゲイン符号帳１０５から出力された固定符号帳ゲインを、固定符号帳１０４から出力された固定符号帳ベクトルに乗じ、加算器１０８に出力する。
【００２６】
加算器１０８は、乗算器１０６から出力された適応符号帳ベクトルと、乗算器１０７から出力された固定符号帳ベクトルとを加算し、加算後の音源ベクトルを駆動音源としてＬＰＣ合成フィルタ１０９に出力する。
【００２７】
ＬＰＣ合成フィルタ１０９は、ＬＰＣ量子化部１０２から出力された量子化ＬＰＣパラメータをフィルタ係数とし、適応符号帳１０３および固定符号帳１０４で生成される音源ベクトルを駆動音源としたフィルタ関数、すなわち、ＬＰＣ合成フィルタを用いて合成信号を生成する。この合成信号は、加算器１１０に出力される。
【００２８】
加算器１１０は、ＬＰＣ合成フィルタ１０９で生成された合成信号を音声信号Ｓ１１から減算することによって誤差信号を算出し、この誤差信号を聴感重み付け部１１１に出力する。なお、この誤差信号が符号化歪みに相当する。
【００２９】
聴感重み付け部１１１は、加算器１１０から出力された符号化歪みに対して聴感的な重み付けを施し、歪み最小化部１１２に出力する。
【００３０】
歪み最小化部１１２は、聴感重み付け部１１１から出力された符号化歪みが最小となるような、適応符号帳１０３、固定符号帳１０４およびゲイン符号帳１０５の各インデックスをサブフレームごとに求め、これらのインデックスを符号化情報としてＣＥＬＰ符号化装置１００の外部に出力する。より詳細には、上記の適応符号帳１０３および固定符号帳１０４に基づいて合成信号を生成し、この信号の符号化歪みを求める一連の処理は閉ループ制御（帰還制御）となっており、歪み最小化部１１２は、各符号帳に指示するインデックスを１サブフレーム内において様々に変化させることによって各符号帳を探索し、最終的に得られる、符号化歪みを最小とする各符号帳のインデックスを出力する。
【００３１】
なお、符号化歪みが最小となる際の駆動音源は、サブフレームごとに適応符号帳１０３へフィードバックされる。適応符号帳１０３は、このフィードバックにより、記憶されている駆動音源を更新する。
【００３２】
ここで、固定符号帳１０４の探索方法について説明する。まず、音源ベクトルの探索と符号の導出は以下の式（１）の符号化歪を最小化する音源ベクトルを探索することにより行われる。
【数１】
2009016816.tif 000016
Ｅ：符号化歪、ｘ：符号化ターゲット、ｐ：適応符号帳ベクトルのゲイン、Ｈ：聴感重み付け合成フィルタ、ａ：適応符号帳ベクトル、ｑ：固定符号帳ベクトルのゲイン、ｓ：固定符号帳ベクトル
【００３３】
一般的に、適応符号帳ベクトルと固定符号帳ベクトルとはオープンループで（別々のループで）探索されるので、固定符号帳１０４の符号の導出は以下の式（２）の符号化歪を最小化する固定符号帳ベクトルを探索することにより行われる。
【数２】
2009016816.tif 000017
Ｅ：符号化歪、ｘ：符号化ターゲット（聴感重み付け音声信号）、ｐ：適応符号帳ベクトルの最適ゲイン、Ｈ：聴感重み付け合成フィルタ、ａ：適応符号帳ベクトル、ｑ：固定符号帳ベクトルのゲイン、ｓ：固定符号帳ベクトル、ｙ：固定符号帳探索のターゲットベクトル
【００３４】
ここで、ゲインｐ、ｑは音源の符号を探索した後で決定するので、ここでは最適ゲインで探索を進めることとする。すると、上式（２）は以下の式（３）と書ける。
【数３】
2009016816.tif 000018
【００３５】
そして、この歪の式を最小化することは、以下の式（４）の関数Ｃを最大化することと同値であることがわかる。
【数４】
2009016816.tif 000019
【００３６】
よって、代数的符号帳の音源のような少数パルスからなる音源の探索の場合は、ｙＨとＨＨを予め計算しておけば、少ない計算量で上記関数Ｃを算出できる。ここで、ベクトルｙＨの要素は、パルス単独の相関値に相当する。すなわち、ターゲットｙに対して時間逆順合成を施したｙＨの要素の１つはその位置に立つパルスの合成信号とターゲット信号との相関値と等しくなる。
【００３７】
図２は、本実施の形態に係る歪み最小化部１１２の内部構成を示すブロック図である。ここでは、歪み最小化部１１２の固定符号帳探索において代数的符号帳を構成する４本のパルスを２本と２本のサブセットに分割して探索する場合を例にとって説明する。また、各パルスが８つの位置候補を備えるとする。
【００３８】
図２において、歪み最小化部１１２は、適応符号帳探索部２０１、固定符号帳探索部２０２、およびゲイン符号帳探索部２０３を備える。固定符号帳探索部２０２は、最大相関値算出部２２１、ソーティング部２２２、前処理部２２３、および探索部２２４を備える
。
【００３９】
適応符号帳探索部２０１は、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪みを用いて、適応符号帳１０３の探索を行う。適応符号帳探索部２０１は、探索過程で得られる適応符号帳ベクトルの符号を適応符号帳１０３に出力し、探索結果として得られた適応符号帳ベクトルの符号を固定符号帳探索部２０２の最大相関値算出部２２１に出力するとともに、ＣＥＬＰ符号化装置１００の外部へ出力する。
【００４０】
固定符号帳探索部２０２は、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪み、および適応符号帳探索部２０１から入力される適応符号帳ベクトルの符号を用いて固定符号帳の分割探索を行う。固定符号帳探索部２０２は、探索過程で得られる固定符号帳ベクトルの符号を固定符号帳１０４に出力し、探索結果として得られた固定符号帳ベクトルの符号をＣＥＬＰ符号化装置１００の外部に出力するとともにゲイン符号帳探索部２０３に出力する。
【００４１】
ゲイン符号帳探索部２０３は、固定符号帳探索部２０２の探索部２２４から入力される固定符号帳ベクトルの符号、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪み、および適応符号帳探索部２０１から入力される適応符号帳ベクトルの符号に基づき、ゲイン符号帳を探索する。そして、ゲイン符号帳探索部２０３は、探索過程で得られる適応符号帳ゲインおよび固定符号帳ゲインをゲイン符号帳１０５に出力し、探索結果として得られた適応符号帳ゲインおよび固定符号帳ゲインをＣＥＬＰ符号化装置１００の外部に出力する。
【００４２】
最大相関値算出部２２１は、適応符号帳探索部２０１から入力される適応符号帳ベクトルの符号を用いて適応符号帳ベクトルを求め、式（２）に示すターゲットベクトルｙを計算する。また、最大相関値算出部２２１は、聴感重み付け部１１１における合成フィルタの係数Ｈを用いて、各候補位置における各パルス単独の相関値ｙＨを算出して前処理部２２３に出力する。そして、最大相関値算出部２２１は、各候補位置における各パルス単独の相関値ｙＨを用いて、各パルスの最大相関値を求め、ソーティング部２２２に出力する。なお、最大相関値算出部２２１における最大相関値の算出の詳細については後述する。
【００４３】
ソーティング部２２２は、最大相関値算出部２２１から入力される各パルスの最大相関値を大きい方から順番に並べる（以下、ソーティング処理と称す）。また、ソーティング部２２２は、ソーティング結果に基づき、４本のパルスを２本ずつの２つのサブセットに分割し、分割結果を探索部２２４に出力する。なお、ソーティング部２２２におけるソーティング処理の詳細については後述する。
【００４４】
前処理部２２３は、聴感重み付け部１１１における合成フィルタの係数Ｈを用いてマトリクスＨＨを算出する。また、前処理部２２３は、最大相関値算出部２２１から入力されるベクトルｙＨの要素の極性（＋−）から、パルスの極性ｐｏｌを決めて、探索部２２４に出力する。具体的には、前処理部２２３は、各位置に立つパルスの極性をｙＨのその位置の値の極性に合わせることとし、ｙＨの値の極性を別の配列に格納しておく。前処理部２２３は、各位置の極性を別の配列に格納した後、ｙＨの値に対し全て絶対値をとり正の値に変換しておく。また、前処理部２２３は、格納した各位置の極性に合わせて、ＨＨの値に対しても極性を乗ずることによって変換しておく。求められたｙＨおよびＨＨは、探索部２２４に出力される。
【００４５】
探索部２２４は、ソーティング部２２２から入力される分割結果、聴感重み付け部１１１において聴感的な重み付けが施された符号化歪み、および前処理部２２３から入力されるｙＨおよびＨＨを用いて固定符号帳の分割探索を行う。探索部２２４は、探索過程で得
られる固定符号帳ベクトルの符号を固定符号帳１０４に出力し、探索結果として得られた固定符号帳ベクトルの符号をＣＥＬＰ符号化装置１００の外部に出力するとともに、ゲイン符号帳探索部２０３に出力する。なお、探索部２２４における固定符号帳の分割探索の詳細については後述する。
【００４６】
次いで、最大相関値算出部２２１において各パルスの最大相関値を算出する処理について詳細に説明する。
【００４７】
図３は、最大相関値算出部２２１における各パルスの最大相関値の算出手順を示すフロー図である。ここでは、最大相関値算出部２２１においてパルス０の相関値（ｙＨ）の値が最も大きくなる２つの候補位置を求め、これに基づきパルス０の最大相関値を算出する処理を例にとって説明する。
【００４８】
まず、最大相関値算出部２２１は、予め定められたパルス０の候補位置の配列ｉｃｉ０［８］、および探索に用いる相関値ｙＨを正値に変換して得られる配列ｙＨ［３２］を確保する（ＳＴ１０１０）。
【００４９】
次いで、最大相関値算出部２２１は、最大値ｍａｘ００、準最大値（２番目に大きい値）ｍａｘ０１、およびカウンタｉの初期化を行い（ＳＴ１０２０）、ＳＴ１０３０〜ＳＴ１０８０からなるループに移行する。
【００５０】
このループにおいて、最大相関値算出部２２１は、カウンタｉの値が「８」以上である場合（ＳＴ１０４０：「ＹＥＳ」）には、各候補位置に対応する全てのループ処理が終わったと判断し、処理を終了する。一方、カウンタｉの値が「８」より小さい場合（ＳＴ１０４０：「ＮＯ」）には、最大相関値算出部２２１は、全てのループ処理が終わっていないと判断し、処理をＳＴ１０５０に移行する。
【００５１】
次いで、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が最大値ｍａｘ００より大きい場合（ＳＴ１０５０：「ＹＥＳ」）には、最大相関値算出部２２１は、最大値ｍａｘ００を準最大値ｍａｘ０１として保存し、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］を最大値ｍａｘ００に代入してから（ＳＴ１０６０）、処理をＳＴ１０３０に戻す。カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が最大値ｍａｘ００以下である場合（ＳＴ１０５０：「ＮＯ」）には、最大相関値算出部２２１は処理をＳＴ１０７０に移行する。
【００５２】
次いで、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が準最大値ｍａｘ０１より大きい場合（ＳＴ１０７０：「ＹＥＳ」）には、最大相関値算出部２２１は、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］を準最大値ｍａｘ０１に代入し、処理をＳＴ１０３０に戻す（ＳＴ１０８０）。一方、カウンタｉが示す位置の相関値ｙＨ［ｉｃｉ０［ｉ］］が準最大値ｍａｘ０１以下である場合（ＳＴ１０７０：「ＮＯ」）には、最大相関値算出部２２１は、処理をＳＴ１０３０に戻す。
【００５３】
次いで、ＳＴ１０３０において、最大相関値算出部２２１は、カウンタｉを１インクリメントしてから、処理をＳＴ１０４０に戻す。
【００５４】
このようにして、最大相関値算出部２２１は各候補位置におけるパルス０単独の相関値の最大値ｍａｘ００および準最大値ｍａｘ０１を求める。そして、最大相関値算出部２２１は、図３に示した手順を流用して、パルス１，２，３単独の相関値（ｙＨ）の値が最も大きくなる候補位置を２つずつ求める。すなわち、最大相関値算出部２２１は、パルス１，２，３それぞれの単独の相関値の最大値および準最大値ｍａｘ１０，ｍａｘ１１，ｍａ
ｘ２０，ｍａｘ２１，ｍａｘ３０，ｍａｘ３１を求める。
【００５５】
次いで、最大相関値算出部２２１は、パルス０，１，２，３それぞれの単独の相関値の最大値および準最大値を用いて下記の式（５）従い、各パルスの最大相関値Ｓ［０］，Ｓ［１］，Ｓ［２］，Ｓ［３］を求める。式（５）に示すように、最大相関値算出部２２１は、各パルス単独の相関値の最大値に準最大値を所定の割合で加算することにより、各パルスに対応する安定した最大相関値を得る。
Ｓ［０］＝ｍａｘ００＋ｍａｘ０１×０．０５
Ｓ［１］＝ｍａｘ１０＋ｍａｘ１１×０．０５
Ｓ［２］＝ｍａｘ２０＋ｍａｘ２１×０．０５
Ｓ［３］＝ｍａｘ３０＋ｍａｘ３１×０．０５  …（５）
【００５６】
次いで、ソーティング部２２２における、各パルスの最大相関値に対するソーティング処理について詳細に説明する。
【００５７】
図４は、ソーティング部２２２における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図である。
【００５８】
まず、ソーティング部２２２は、最大相関値算出部２２１から各パルスの最大相関値Ｓ［ｊ］（ｊ＝０，１，２，３）を入力し、何位までソーティングしたかを示すカウンタｉを「０」にリセットする（ＳＴ２０１０）。
【００５９】
次いで、ソーティング部２２２は、カウンタｉの値が「４」以上である場合（ＳＴ２０３０：「ＹＥＳ」）には、全てのソーティングが終ったと判断し、処理をＳＴ２１００に移行する。一方、カウンタｉの値が４より小さい場合（ＳＴ２０３０：「ＮＯ」）には、ソーティング部２２２は、パルス番号Ｎ［ｉ］に「０」を代入し、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を探索するためのループの回数をカウントするカウンタｊを「０」にリセットし、最大値を格納する変数ｍａｘを「０」にリセットする（ＳＴ２０４０）。
【００６０】
次いで、カウンタｊが４より小さい場合（ＳＴ２０６０：「ＮＯ」）には、ソーティング部２２２は処理をＳＴ２０７０に移行する。
【００６１】
次いで、最大相関値Ｓ［ｊ］が変数ｍａｘより大きい場合（ＳＴ２０７０：「ＹＥＳ」）には、ソーティング部２２２は、最大相関値Ｓ［ｊ］を変数ｍａｘに代入し、カウンタｊの値を、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］に対応するパルス番号Ｎ［ｉ］に代入し（ＳＴ２０８０）、処理をＳＴ２０５０に移行する。一方、最大相関値Ｓ［ｊ］が変数ｍａｘ以下である場合（ＳＴ２０７０：「ＮＯ」）には、ソーティング部２２２は処理をＳＴ２０５０に移行する。次いで、ＳＴ２０５０において、ソーティング部２２２はカウンタｊを１インクリメントし、処理をＳＴ２０６０に戻す。
【００６２】
一方、ＳＴ２０６０においてカウンタｊが４以上である場合（ＳＴ２０６０：「ＹＥＳ」）には、ソーティング部２２２は、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を探索するための、ＳＴ２０５０〜ＳＴ２０８０からなるループが終わったと判断し、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］に「−１」を代入する（ＳＴ２０９０）。これにより、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を、ｉ＋１位の最大相関値Ｓ［Ｎ［ｉ＋１］］を探索するためのループ処理の対象から排除する。次いで、ソーティング部２２２は、ＳＴ２０２０において、カウンタｉを１インクリメントし、処理をＳＴ２０３０に戻す。
【００６３】
このようにして、ソーティング部２２２は、各パルスの最大相関値Ｓ［０］、Ｓ［１］、Ｓ［２］、Ｓ［３］を大きい方から順番に並べ、ソーティング結果を示すＮ［ｉ］を得
る。以下、ソーティング部２２２においてＮ［ｉ］＝｛２，０，３，１｝を得た場合を例にとって説明する。すなわち、１番大きい最大相関値Ｓ［Ｎ［０］］に対応するパルスの番号Ｎ［０］の値が２であり、次の値は順次０，３，１であると仮定する。
【００６４】
次いで、ＳＴ２１００において、ソーティング部２２２は、ソーティングされた最大相関値に対応する４本のパルス番号Ｎ［ｉ］を、予め設定された２つのサブセットの分割パターンにグルーピングして、パルスの探索順序を決定し、得られた探索順序を探索部２２４に出力する。すなわち、ソーティング部２２２は、探索部２２４の固定符号帳の分割探索において、先に探索する２パルスの番号および後に探索する２パルスの番号を決める。ソーティング部２２２では、予め下記の式（６）に示す３通りの探索順の候補が設定されている。
｛  第１サブセット    ｝  ｛  第２サブセット    ｝
第１候補  ｛Ｎ［０］，  Ｎ［１］｝  ｛Ｎ［２］，  Ｎ［３］｝
第２候補  ｛Ｎ［０］，  Ｎ［２］｝  ｛Ｎ［３］，  Ｎ［１］｝
第３候補  ｛Ｎ［０］，  Ｎ［３］｝  ｛Ｎ［１］，  Ｎ［２］｝  …（６）
【００６５】
分割探索において、先に探索するサブセット（第１サブセット）および後に探索するサブセット（第２サブセット）の分割パターンは、多種存在する。そのうち、式（６）に示すように、最大相関値が最も大きいパルスＮ［０］を、先に探索するサブセット（第１サブセット）に含ませる分割パターンを採用すると、良好な符号化性能が得られる。
【００６６】
式（６）の各探索順候補においては、先に探索するサブセット（第１サブセット）、次に、後で探索するサブセット（第２サブセット）という順番で探索が行われる。
【００６７】
式（６）中のＮ［ｉ］を、ソーティングにより得られた具体的な値で表すと、下記の式（７）が得られ、第１候補、第２候補、第３候補の順に探索が行われる。
｛第１サブセット｝  ｛第２サブセット｝
第１候補      {２, ０}        {３, １}
第２候補      {２, ３}        {１, ０}
第３候補      {２, １}        {０, ３}  …（７）
【００６８】
式（７）に示す３つの探索順は、下記の式（８）に示すＭ［３］［４］にまとめることができる。ここでＭ［３］［４］は、パルス４本に対して分割探索を３回行う場合のパルスの探索順を示す。
Ｍ［３］［４］＝｛｛２，０，３，１｝，｛２，３，１，０｝，｛２，１，０，３｝｝
…（８）
【００６９】
すなわちソーティング部２２２は、探索順序としてＭ［３］［４］を探索部２２４に出力する。
【００７０】
次いで、探索部２２４における固定符号帳の分割探索について詳細に説明する。
【００７１】
図５および図６は、探索部２２４における固定符号帳の分割探索の手順を示すフロー図である。ここでは、代数的符号帳の条件を以下に示す。
（１）ビット数：１６ビット
（２）処理単位（サブフレーム長）：３２
（３）パルス本数：４本
【００７２】
この条件のもと、以下のような代数的符号帳が設計できる。
ｉｃｉ０［８］＝｛０，４，８，１２，１６，２０，２４，２８｝
ｉｃｉ１［８］＝｛１，５，９，１３，１７，２１，２５，２９｝
ｉｃｉ２［８］＝｛２，６，１０，１４，１８，２２，２６，３０｝
ｉｃｉ３［８］＝｛３，７，１１，１５，１９，２３，２７，３１｝
【００７３】
まず、探索部２２４は、ＳＴ３０１０において、固定符号帳の４本のパルスそれぞれの候補位置を示す配列ｉｃｉ０［８］、ｉｃｉ１［８］、ｉｃｉ２［８］、ｉｃｉ３［８］を用意し、ｙＨを正値に変換して得られた配列ｙＨ［３２］、ＨＨの極性を調整して得られた配列ＨＨ［３２］［３２］、およびｙＨを正値に変換する前のｙＨの極性値（−１，＋１）を格納したベクトルｐｏｌ［３２］を作成する。次いで、ＳＴ３０２０において、後続の探索ループに用いる変数の初期化が行われる。
【００７４】
探索部２２４は、ＳＴ３０３０においてｊと数値「３」とを比較し、ｊが３以上の場合は探索を終了するためにＳＴ３２５０の処理へ進み、ｊが３より小さい場合はＳＴ３０５０の初期化へ進む。ＳＴ３０４０においてはｊを１インクリメントする。これにより、探索部２２４は、ソーティング部２２２から入力される探索順Ｍ［３］［４］が示す３つの探索順に対応して、２つのサブセットからなる分割探索を３回行う。
【００７５】
ＳＴ３０５０〜ＳＴ３１３０は、第１サブセットの探索ループ処理を示す。具体的には、ＳＴ３０５０においては、第１サブセットの探索ループの初期化が行われる。次いで、探索部２２４は、判定ＳＴ３０６０においてｉ０と数値「８」とを比較し、ｉ０が８以上の場合は次の探索ループの初期化ＳＴ３１４０へ進み、ｉ０が８より小さい場合は処理ＳＴ３０７０へ進む。ＳＴ３０７０においてＭ［ｊ］［０］（ｊ＝０，１，２）が示すパルスの相関値ｓｙ０および音源パワｓｈ０を算出する。また、カウンタｉ１を０に初期化する。また、ＳＴ３０８０においては、ｉ０を１インクリメントする。これにより、探索部２２４は、Ｍ［ｊ］［０］（ｊ＝０，１，２）が示すパルスの８つの候補位置に対応して、８回のループ処理を行う。同様に、ＳＴ３０９０〜ＳＴ３１３０において、探索部２２４は、Ｍ［ｊ］［１］（ｊ＝０，１，２）が示すパルスの８つの候補位置に対応して、８回のループ処理を行う。
【００７６】
まず、判定ＳＴ３０９０においてｉ１と数値「８」とを比較し、ｉ１が８以上の場合はインクリメント処理ＳＴ３０８０へ進み、ｉ１が８より小さい場合は処理ＳＴ３１００へ進む。ＳＴ３１００においては、探索部２２４は、前処理部２２３から入力されるｙＨおよびＨＨに加え、ＳＴ３０７０において算出された相関値ｓｙ０および音源パワｓｈ０を用いて、Ｍ［ｊ］［１］（ｊ＝０，１，２）が示すパルスの相関値ｓｙ１および音源パワｓｈ１を算出する。
【００７７】
ＳＴ３１２０において、探索部２２４は、第１サブセットの処理対象となる各パルスの相関値と音源パワとを用いて式（４）に従い関数Ｃの値を算出および比較し、より大きい関数値を示す場合のｉ０、ｉ１をｉｉ０、ｉｉ１に上書き格納し、また関数Ｃの分子項、分母項を上書き格納する（ＳＴ３１３０）。なお、ＳＴ３１２０においては計算量の多い除算を避け、分母項と分子項のたすき掛けの乗算により算出および比較を行っている。上記判定において、より小さい場合、またより大きい場合で処理ＳＴ３１３０を行った場合はインクリメント処理ＳＴ３１１０へ進む。インクリメント処理ＳＴ３１１０においては、ｉ１を１インクリメントする。
【００７８】
ＳＴ３１４０〜ＳＴ３２２０は、第２サブセットの探索ループ処理を示す。なお、第２サブセットの探索ループ処理は、ＳＴ３０５０〜ＳＴ３１３０に示した第１サブセットの探索ループ処理と基本的に同様なステップを有する。ここでは、第１サブセットの探索ループ処理との相違点のみについて説明する。まず、ＳＴ３１４０における、第２サブセットの探索ループ処理の初期化は、第１サブセットの探索ループ処理の結果を用いて行われ
る。また、第２サブセットの探索ループ処理の処理対象は、Ｍ［ｊ］［２］（ｊ＝０，１，２）およびＭ［ｊ］［３］（ｊ＝０，１，２）それぞれが示すパルスである。また処理ＳＴ３１６０においては、第１サブセットの探索ループで探索され、格納されたカウンタ情報ｉｉ０、ｉｉ１を用いてパルス２に対する相関値ｓｙ２および音源パワｓｈ２を算出する。また、同様に、処理ＳＴ３１９０においては、第１サブセットの探索ループで探索され、格納されたカウンタ情報ｉｉ０、ｉｉ１を用いてパルス３に対する相関値ｓｙ３および音源パワｓｈ３を算出する。
【００７９】
次いで、ＳＴ３２３０およびＳＴ３２４０において、探索部２２４は、分割探索全体において関数Ｃの値が最も大きくなるパルスの位置の組合せを求める。
【００８０】
次いで、ＳＴ３２５０において、探索部２２４は、ｉｉ０、ｉｉ１、ｉｉ２、ｉｉ３を各パルスの位置情報とする。また、配列ｐｏｌの値が極性（±１）であり、探索部２２４は、極性ｐ０、ｐ１、ｐ２、ｐ３を下記の式（９）に従って０または１に変換して１ビットで符号化する。
ｐ０＝（ｐｏｌ［ｉｃｈｉ０［ｉｉ０］］＋１）／２
ｐ１＝（ｐｏｌ［ｉｃｈｉ１［ｉｉ１］］＋１）／２
ｐ２＝（ｐｏｌ［ｉｃｈｉ２［ｉｉ２］］＋１）／２
ｐ３＝（ｐｏｌ［ｉｃｈｉ３［ｉｉ３］］＋１）／２  …（９）
【００８１】
ここで、位置情報および極性に対する復号方法としては、ｉｃｈｉ０［ｉｉ０］、ｉｃｈｉ１［ｉｉ１］、ｉｃｈｉ２［ｉｉ２］、ｉｃｈｉ３［ｉｉ３］によりパルスの位置が復号され、復号した位置と極性を用いて固定符号帳ベクトルが復号される。
【００８２】
図５および図６に示すように、探索部２２４は、２つのサブセットからなる分割探索を行うため、全探索の場合に比べて計算量を大きく削減できる。具体的には、全探索においては８の４乗で４０９６回のループ処理を行うのに対し、図５および図６に示す方法によれば２つのサブセットの探索それぞれにおいては、８の２乗で６４回ずつのループ処理を行う。そして、Ｍ［３］［４］に対応して２つのサブセットからなる分割探索を３回行うため、６４×２サブセット×３倍で合計３８４回のループ処理を行う。これは全探索の約１／１０の計算量である。
【００８３】
このように、本実施の形態によれば、固定符号帳に対して分割探索を行うため、固定符号帳に対して全探索を行う場合に比べ、計算量を削減することができる。
【００８４】
さらに、本実施の形態によれば、分割探索において固定符号帳を構成するパルスを、先に探索するサブセットおよび後に探索するサブセットに分割する際に、最大相関値が最も大きいパルスを用いて先に探索するサブセットを構成するため、分割探索による符号化歪みを抑えることができる。すなわち、全探索を行う場合でも、最大相関値が高い位置のパルスは採用される可能性が高く、分割探索において先に探索することにより符号化歪みを抑えることができる。
【００８５】
なお、本実施の形態ではパルス数が４であり、分割数が２である場合について説明したが、本発明はパルス数または分割数に依存せず、各パルスの最大相関値をソーティングした結果に基づいて探索するパルスの順番を決めれば、本実施の形態と同様な効果を得ることができる。
【００８６】
また、本実施の形態では、最大相関値算出部２２１は、各パルス単独の相関値の最大値に準最大値を所定の割合で加算して最大相関値を算出する場合を例にとって説明した。しかし、本発明はこれに限定されず、さらに各パルスの３番目に大きい単独の相関値を所定
の割合で加算して最大相関値を算出しても良く、または、各パルス単独の相関値の最大値をそのまま最大相関値としても良い。
【００８７】
また、本実施の形態では各パルスの候補位置の予備選択を行わない場合を例にとって説明したが、本発明はこれに限定されず、各パルスの候補位置の予備選択を行ってからソーティングを行っても良い。これにより、ソーティングの効率を向上することができる。
【００８８】
また、本実施の形態では固定符号帳として代数的符号帳を用いる場合を例にとって説明したが、本発明はこれに限定されず、固定符号帳としてマルチパルス符号帳を用いても良い。すなわち、マルチパルスの位置情報および極性情報を用いて本実施の形態に適用することが可能である。
【００８９】
また、本実施の形態では音声符号化方法としてＣＥＬＰ符号化方式を用いる場合を例にとって説明したが、本発明はこれに限定されず、音声符号化方法として、本数が分かる音源ベクトルが格納されている符号帳を用いる符号化方式であれば良い。これは、本発明に係る分割探索は、固定符号帳の探索のみに対して行われ、適応符号帳の有無や、スペクトル包絡の分析方法がＬＰＣ、ＦＦＴ、またはフィルタバンクであるか否かに依存しないからである。
【００９０】
（実施の形態２）
本発明の実施の形態２は、実施の形態１と基本的に同様であり、ソーティング部２２２におけるソーティング処理（図４参照）のみ実施の形態１と相違する。以下、図２において、ソーティング部２２２に代えて、本実施の形態に係るソーティング部を「４２２」という符号を付して配置し、ソーティング部４２２（図示せず）におけるソーティング処理のみについて説明する。
【００９１】
図７は、本実施の形態に係るソーティング部４２２における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図である。なお、図７に示す手順は、図４に示した手順と基本的に同様なステップを有しており、同一のステップには同一の符号を付し、その説明を省略する。
【００９２】
ＳＴ４０４０において、ソーティング部４２２は、パルス番号Ｎ［ｉ］に「０」を代入し、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を探索するためのループの回数をカウントするカウンタｊを「０」にリセットし、最大値を格納する変数ｍａｘを「０」にリセットし、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を保存するための変数Ｌ［ｉ］に「０」を代入する。
【００９３】
ＳＴ４０９０において、ソーティング部４２２は、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］をＬ［ｉ］に代入し、Ｓ［Ｎ［ｉ］］に「−１」を代入する。これにより、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］をＬ［ｉ］に保存し、また、ｉ位の最大相関値Ｓ［Ｎ［ｉ］］を、ｉ＋１位の最大相関値Ｓ［Ｎ［ｉ＋１］］を探索するためのループ処理の対象から排除する。
【００９４】
ＳＴ２０１０〜ＳＴ４０９０までの処理によって、ソーティング部４２２は、各パルスの最大相関値Ｓ［０］、Ｓ［１］、Ｓ［２］、Ｓ［３］を大きい方から順番に並べ、ソーティング結果を示すＮ［ｉ］、およびＬ［ｉ］を得る。
【００９５】
ＳＴ４１００において、ソーティング部４２２は、ソーティングされた最大相関値に対応する４本のパルス番号Ｎ［ｉ］を、予め設定された２つのサブセットの分割パターンにグルーピングして、パルスの探索順序を決定し、得られた探索順序を探索部２２４に出力する。すなわち、ソーティング部４２２は、探索部２２４の固定符号帳の分割探索において、先に探索する２パルスの番号および後に探索する２パルスの番号を決める。ソーティ
ング部４２２では、予め３通りの探索順の候補が設定されている。ここで実施の形態１のソーティング部２２２と異なるのは、第３候補において、最大相関値が格納されたＬ［ｉ］を用いて探索順を決定する点である。
【００９６】
具体的には、ソーティング部４２２は、まず、ソーティング結果Ｎ［ｉ］を用いた、下記の式（１０）に示す第１候補と第２候補との２つの探索順候補が設定されている。すなわちソーティング部４２２は、式（１０）に示すように、第１候補と第２候補とにおいて最大相関値が最も大きいパルスを先に探索するサブセットに含ませ、符号化性能を向上する。
｛  第１サブセット    ｝  ｛  第２サブセット    ｝
第１候補  ｛Ｎ［０］，  Ｎ［１］｝  ｛Ｎ［２］，  Ｎ［３］｝
第２候補  ｛Ｎ［０］，  Ｎ［２］｝  ｛Ｎ［３］，  Ｎ［１］｝  …（１０）
【００９７】
次いで、ソーティング部４２２は、以下のようにソーティング結果Ｎ［ｉ］およびＬ［ｉ］を用いて３つ目の探索順候補が設定されている。すなわち、ソーティング部４２２は、Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１以上であるか否かを判断し、Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１以上である場合には、第３候補として｛Ｎ［２］，  Ｎ［３］｝  ｛Ｎ［０］，  Ｎ［１］｝が適用される。Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１より小さい場合には、ソーティング部４２２は続けて、Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４以上であるか否かを判断する。Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４以上である場合には、ソーティング部４２２は、第３候補として｛Ｎ［１］，  Ｎ［３］｝  ｛Ｎ［２］，
Ｎ［０］｝が適用される。Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４より小さい場合には、ソーティング部４２２は続けて、Ｌ［０］＋Ｌ［３］がＬ［１］＋Ｌ［２］以上であるか否かを判断する。ソーティング部４２２は、Ｌ［０］＋Ｌ［３］がＬ［１］＋Ｌ［２］以上である場合に、第３候補として｛Ｎ［０］，  Ｎ［３］｝  ｛Ｎ［１］，  Ｎ［２］｝を生成し、Ｌ［０］＋Ｌ［３］がＬ［１］＋Ｌ［２］より小さい場合に、第３候補として｛Ｎ［１］，  Ｎ［２］｝  ｛Ｎ［３］，  Ｎ［０］｝が適用される。
【００９８】
ソーティング部４２２は、第３候補の探索順を適用する際に、後程探索部２２４の探索における冗長性を低減するために、各パルスの最大相関値の差がわずかである場合には、必ずしも最大相関値が最も大きいパルスを含まず先に探索するサブセットを構成する。すなわち、ソーティング部４４２は、ソーティング結果Ｎ［ｉ］に基づき各パルスの最大相関値の組合せを複数個構成し、構成された複数個の組合せに係数を掛けて比較した結果に基づき、４つのパルスを２つずつのサブセットにグルーピングする。
【００９９】
例えば、ソーティング結果としてＮ［ｉ］＝｛２，０，３，１｝、Ｌ［ｉ］＝｛９．５，  ９．０，  ８．５，  ８．０｝が得られた場合に、Ｌ［２］＋Ｌ［３］が（Ｌ［０］＋Ｌ［１］）×０．９１より小さく、Ｌ［１］＋Ｌ［３］が（Ｌ［０］＋Ｌ［２］）×０．９４以上となる。従って、ソーティング部４２２は、第３候補として｛Ｎ［１］，  Ｎ［３］｝  ｛Ｎ［２］，  Ｎ［０］｝を適用する。
【０１００】
Ｎ［ｉ］を具体的な値で表すと、第１候補、第２候補、第３候補は下記の式（１１）で表される。
｛第１サブセット｝｛第２サブセット｝
第１候補    {２，０}        {３，１}
第２候補    {２，３}        {１，０}
第３候補    {０，１}        {３，２}  …（１１）
【０１０１】
式（１１）に示す３つの探索順候補を下記の式（１２）に示すＭ［３］［４］にまとめることができる。
Ｍ［３］［４］＝｛｛２，０，３，１｝，｛２，３，１，０｝，｛０，１，３，２｝｝
…（１２）
【０１０２】
ソーティング部４２２は、探索順候補としてＭ［３］［４］を探索部２２４に出力する。
【０１０３】
このように、本実施の形態によれば、分割探索において固定符号帳を構成するパルスを、先に探索するサブセットおよび後に探索するサブセットに分割する際に、各パルスの最大相関値の順位だけではなく、各パルスの最大相関値の値に基づき、必ずしも最大相関値が最も大きいパルスを含まず先に探索するサブセットを構成する。これにより、分割探索における探索の冗長性を低減することができる。
【０１０４】
なお、本実施の形態では、３番目の探索順候補を適用する際に０．９１、０．９４などの係数を用いる場合を例にとって説明したが、本発明はこれに限定されず、統計により予め決められたほかの係数を用いても良い。
【０１０５】
また、本実施の形態では、３番目の探索順候補を適用する際にＮ［ｉ］に加えＬ［ｉ］をさらに用いる場合を例にとって説明したが、本発明はこれに限定されず、１番目の探索順候補または２番目の探索順候補を適用する際でも、Ｎ［ｉ］およびＬ［ｉ］の両方を用いても良い。
【０１０６】
（実施の形態３）
本発明の実施の形態３は、実施の形態１と基本的に同様であり、各サブセットにグルーピングしたパルスをさらに所定の順番に従って並び替える点のみが実施の形態１と相違する。すなわち、本実施の形態は、図４に示したソーティング処理の一部のみにおいて実施の形態１と相違する。以下、図２において、ソーティング部２２２に代えて、本実施の形態に係るソーティング部を「５２２」という符号を付して配置し、ソーティング部５２２（図示せず）におけるソーティング処理のみについて説明する。
【０１０７】
図８は、本実施の形態に係るソーティング部５２２において各パルスの最大相関値に対してソーティング処理を行う手順を示すフロー図である。なお、図８に示す手順は、図４に示した手順と基本的に同様なステップを有しており、同一のステップには同一の符号を付し、その説明を省略する。
【０１０８】
図８に示すＳＴ５１００においてソーティング部５２２は、実施の形態１に係るソーティング部２２２が図４に示したＳＴ２１００において行った処理と基本的に同様な処理を行うが、得られたＭ［３］［４］をすぐには探索部２２４に出力せず、以下のＳＴ５１１０の処理を行ってから、探索部２２４へ出力する点において相違する。
【０１０９】
ＳＴ５１１０においてソーティング部５２２は、Ｍ［３］［４］に含まれる要素を２つずつまとめてＭ’［６］［２］を構成し、Ｍ’［６］［２］に含まれる２つずつのパルスの順番を｛０，１｝、｛１，２｝、｛２，３｝、｛３，０｝、｛０，２｝、｛１，３｝の何れかに並べ替えるという調整を行う。
【０１１０】
図９は、図８に示したＳＴ５１１０におけるソーティング部５２２の処理手順を詳細に示すフロー図である。
【０１１１】
まず、ＳＴ６０１０において、ソーティング部５２２は変数「ｉ」を「０」に初期化す
る。
【０１１２】
次いで、ＳＴ６０２０において、ソーティング部５２２は「ｉ」が「６」に等しいか否かを判定する。
【０１１３】
ＳＴ６０２０において「ｉ」が「６」と等しいと判定した場合（ＳＴ６０２０：「ＹＥＳ」）には、ソーティング部５２２は図９に示した処理（すなわちＳＴ５１１０の処理）を終了する。
【０１１４】
一方、ＳＴ６０２０において「ｉ」が「６」と等しくないと判定した場合（ＳＴ６０２０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０３０に移行する。
【０１１５】
ＳＴ６０３０において、ソーティング部５２２はＭ’［ｉ］［１］＝「２」であって、かつＭ’［ｉ］［２］＝「１」であるか否かを判定する。
【０１１６】
ＳＴ６０３０において、Ｍ’［ｉ］［１］＝「２」であって、かつＭ’［ｉ］［２］＝「１」であると判定した場合（ＳＴ６０３０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６０４０においてＭ’［ｉ］［１］を「１」に設定し、Ｍ’［ｉ］［２］を「２」に設定してから処理をＳＴ６１５０に移行する。
【０１１７】
一方、ＳＴ６０３０において、Ｍ’［ｉ］［１］＝「２」であって、かつＭ’［ｉ］［２］＝「１」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０３０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０５０に移行する。
【０１１８】
ＳＴ６０５０において、ソーティング部５２２はＭ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「２」であるか否かを判定する。
【０１１９】
ＳＴ６０５０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「２」であると判定した場合（ＳＴ６０５０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６０６０においてＭ’［ｉ］［１］を「２」に設定し、Ｍ’［ｉ］［２］を「３」に設定してから処理をＳＴ６１５０に移行する。
【０１２０】
一方、ＳＴ６０５０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「２」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０５０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０７０に移行する。
【０１２１】
ＳＴ６０７０において、ソーティング部５２２はＭ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「３」であるか否かを判定する。
【０１２２】
ＳＴ６０７０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「３」であると判定した場合（ＳＴ６０７０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６０８０においてＭ’［ｉ］［１］を「３」に設定し、Ｍ’［ｉ］［２］を「４」に設定してから処理をＳＴ６１５０に移行する。
【０１２３】
一方、ＳＴ６０７０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「３」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０７０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６０９０に移行する。
【０１２４】
ＳＴ６０９０において、ソーティング部５２２はＭ’［ｉ］［１］＝「１」であって、かつＭ’［ｉ］［２］＝「４」であるか否かを判定する。
【０１２５】
ＳＴ６０９０において、Ｍ’［ｉ］［１］＝「１」であって、かつＭ’［ｉ］［２］＝「４」であると判定した場合（ＳＴ６０９０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６１００においてＭ’［ｉ］［１］を「４」に設定し、Ｍ’［ｉ］［２］を「１」に設定してから処理をＳＴ６１５０に移行する。
【０１２６】
一方、ＳＴ６０９０において、Ｍ’［ｉ］［１］＝「１」であって、かつＭ’［ｉ］［２］＝「４」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６０９０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６１１０に移行する。
【０１２７】
ＳＴ６１１０において、ソーティング部５２２はＭ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「１」であるか否かを判定する。
【０１２８】
ＳＴ６１１０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「１」であると判定した場合（ＳＴ６１１０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６１２０においてＭ’［ｉ］［１］を「１」に設定し、Ｍ’［ｉ］［２］を「３」に設定してから処理をＳＴ６１５０に移行する。
【０１２９】
一方、ＳＴ６１１０において、Ｍ’［ｉ］［１］＝「３」であって、かつＭ’［ｉ］［２］＝「１」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６１１０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６１３０に移行する。
【０１３０】
ＳＴ６１３０において、ソーティング部５２２はＭ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「２」であるか否かを判定する。
【０１３１】
ＳＴ６１３０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「２」であると判定した場合（ＳＴ６１３０：「ＹＥＳ」）には、ソーティング部５２２はＳＴ６１４０においてＭ’［ｉ］［１］を「２」に設定し、Ｍ’［ｉ］［２］を「４」に設定してから処理をＳＴ６１５０に移行する。
【０１３２】
一方、ＳＴ６１３０において、Ｍ’［ｉ］［１］＝「４」であって、かつＭ’［ｉ］［２］＝「２」であるという２つの条件が同時に成立しないと判定した場合（ＳＴ６１３０：「ＮＯ」）には、ソーティング部５２２は処理をＳＴ６１５０に移行する。
【０１３３】
ＳＴ６１５０において、ソーティング部５２２は、「ｉ」を１インクリメントしてから処理をＳＴ６０２０に移行する。
【０１３４】
例えばソーティング部５２２は、Ｍ［３］［４］＝｛｛２，０，３，１｝，｛２，３，１，０｝，｛２，１，０，３｝｝を用いてＭ’［６］［２］＝｛｛２，０｝，｛３，１｝，｛２，３｝，｛１，０｝，｛２，１｝，｛０，３｝｝を構成した場合、さらに図９に示した手順に従ってＭ’［６］［２］に含まれる２つずつのパルスの順番を調整すると、Ｍ’［６］［２］＝｛｛０，２｝，｛１，３｝，｛２，３｝，｛０，１｝，｛１，２｝，｛３，０｝｝が得られる。ソーティング部５２２は、調整により得られたＭ’［６］［２］＝｛｛０，２｝，｛１，３｝，｛２，３｝，｛０，１｝，｛１，２｝，｛３，０｝｝を用いて再びＭ［３］［４］＝｛｛０，２，１，３｝，｛２，３，０，１｝，｛１，２，３，０｝｝を構成して探索部２２４に出力する。
【０１３５】
以下、図９に示したソーティング部５２２における調整処理の効果について説明する。
【０１３６】
固定符号帳を構成するパルスの探索は上記の式（４）の関数Ｃを最も大きくするパルス
位置および極性を探索することにより行われる。従って、探索の際には式（４）の分母項の「ＨＨ」のマトリクスに対応するメモリ（ＲＡＭ：Random Access Memory）が必要になる。例えば音源ベクトルの長さが３２である場合には、３２×３２の対角ベクトルを含む半分のマトリクスに対応するメモリが必要になる。すなわち（３２×３２／２＋１６）バイト＝５２８バイトのメモリが必要になる。ただし、計算の際に指定のインデックスにアクセスする計算量を少なくするためにはフルマトリクス（３２×３２バイト＝１０２４バイト）に対応するメモリが必要になるため、さらに大きなメモリが必要になる。
【０１３７】
これに対し、本発明のように、固定符号帳を構成するパルスを先に探索するサブセットおよび後に探索するサブセット（ペア）に分割し、ペア毎にパルスの探索を行うと、１ペア当たりのエントリ数の２乗である８×８のマトリクスがあれば良いため、メモリを８×８×６バイト＝３８４バイトに節約することができる。ただし、このマトリクスは対称行列ではないため、パルスの番号の順番が逆になるとマトリクスが異なるようになり、逆のマトリクスを別途用意する（メモリが倍になってしまう）か、探索の際のアクセス方法を変える（計算量が増えてしまう）か、ペアの組み合わせ毎にプログラムを用意する（メモリと計算量が増えてしまう）必要がある。そこで、本実施の形態においては、ペア毎の探索を行う際にパルスの順番を並べ替え、すべての探索を６つのペアに限定する。これにより、パルス探索に必要なメモリを上記３８４バイトに限定することができ、計算量も削減することができる。
【０１３８】
このように、本実施の形態によれば、固定符号帳を構成するパルスをペアにグルーピングする際に、グルーピングされるパルスを所定の順番に並び替え、ペア毎にパルスの探索を行うため、固定符号帳の探索に必要なメモリと計算量を削減することができる。
【０１３９】
なお、本実施の形態では、パルスを探索するペアを｛０，１｝、｛１，２｝、｛２，３｝、｛３，０｝、｛０，２｝、｛１，３｝の６通りに限定する場合を例にとって説明したが、本発明はこれに限定されず、上記の各ペアに含まれるパルスの順番を逆にしても良く、これによりパルス探索の平均的性能が変わることはない。
【０１４０】
以上、本発明の各実施の形態について説明した。
【０１４１】
なお、上記各実施の形態に係る固定符号帳は、雑音符号帳、確率符号帳（stochastic codebook）、または乱数符号帳（random codebook）と呼ばれることもある。
【０１４２】
また、適応符号帳は、適応音源符号帳と呼ばれることもあり、固定符号帳は、固定音源符号帳と呼ばれることもある。
【０１４３】
また、ＬＳＰは、ＬＳＦ（Line Spectral Frequency）と呼ばれることもあり、ＬＳＰをＬＳＦと読み替えてもよい。また、ＬＳＰの代わりにＩＳＰ（ImmittanceSpectrum Pairs）をスペクトルパラメータとして符号化する場合もあるが、この場合はＬＳＰをＩＳＰに読み替えればＩＳＰ符号化装置として上記各実施の形態を利用することができる。
【０１４４】
また、上記各実施の形態では、本発明をハードウェアで構成する場合を例にとって説明したが、本発明はソフトウェアで実現することも可能である。
【０１４５】
また、上記各実施の形態の説明に用いた各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部または全てを含むように１チップ化されてもよい。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【０１４６】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用してもよい。
【０１４７】
さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適用等が可能性としてありえる。
【０１４８】
２００７年７月２７日出願の特願２００７−１９６７８２、２００７年１０月３日出願の特願２００７−２６０４２６および２００８年１月１６日出願の特願２００８−００７４１８の日本出願に含まれる明細書、図面および要約書の開示内容は、すべて本願に援用される。
【産業上の利用可能性】
【０１４９】
本発明にかかる音声符号化装置及び音声符号化方法は、ビットを有効に利用した固定符号帳により音声符号化を行うことができ、例えば、移動体通信システムにおける携帯電話等に適用できる。
【図面の簡単な説明】
【０１５０】
【図１】本発明の実施の形態１に係るＣＥＬＰ符号化装置の構成を示すブロック図
【図２】本発明の実施の形態１に係る歪み最小化部の内部構成を示すブロック図
【図３】本発明の実施の形態１に係る最大相関値算出部における各パルスの最大相関値の算出手順を示すフロー図
【図４】本発明の実施の形態１に係るソーティング部における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図
【図５】本発明の実施の形態１に係る探索部における固定符号帳の分割探索の手順を示すフロー図
【図６】本発明の実施の形態１に係る探索部における固定符号帳の分割探索の手順を示すフロー図
【図７】本発明の実施の形態２に係るソーティング部における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図
【図８】本発明の実施の形態３に係るソーティング部における、各パルスの最大相関値に対するソーティング処理の手順を示すフロー図
【図９】本発明の実施の形態３に係るソーティング部における、パルスの順番の並べ替え処理の手順を示すフロー図
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2009016816.tif 000020
【図２】
2009016816.tif 000021
【図３】
2009016816.tif 000022
【図４】
2009016816.tif 000023
【図５】
2009016816.tif 000024
【図６】
2009016816.tif 000025
【図７】
2009016816.tif 000026
【図８】
2009016816.tif 000027
【図９】
2009016816.tif 000028
【国際調査報告】
2009016816.tif 000029
2009016816.tif 000030
2009016816.tif 000031
2009016816.tif 000032