Algebraic Code Excited Linear Prediction

Algebraic Code Excited Linear Prediction（algebraic CELP、代数CELP、代数符号励振線形予測）あるいは ACELP とは、CELPを応用した音声符号化アルゴリズムである。効率が良いため、VoIPや携帯電話などの音声コーデックで広く用いられている。

ACELP はITU-T G.723.1（5.3kbps）、G.729（8kbps）、G.722.2（6.6-23.85kbps）、及び携帯電話用の GSM AMR（GSM/W-CDMA用）、AMR-WB（W-CDMA用、AMRのワイドバンド版）、EVRC（CDMA2000用）、VMR-WB（CDMA2000用のワイドバンド版）、SMV（CDMA2000用）、PDC-EFR（PDC用）などで使用されている。

概要

ACELP のベースである CELP は線形予測符号 (LPC) から派生した音声符号化アルゴリズムで、線形予測フィルターの入力として適応型と固定型のコードブックに登録された信号を使う。 ACELP は、代数的に決められた位置に配置した振幅が+1/-1のパルスの組み合わせからなる固定型コードブックと、この CELP のアルゴリズムとを組み合わせた方式である。以下の特徴がある。

代数的な性格よりコード探索の効率が良い。
コードブック全体をテーブルとして用意する必要が無いためメモリが削減できる。
柔軟性があり大きなサイズのコードブックを容易に実現できる。

ACELP の基本的なアイデアは1987年に発表され ^[1]、その後、疎な（スパース）代数コードを使うよう改良が加えられ ^[2]、計算量が低減された。 1990年代以降、その効率性のため ACELP のコードブックの表現方式は最もよく使われている ^[3]。

技術

ACELP アルゴリズムのベースである CELP は、「合成による分析」の手法を用い音声波形を再合成し聴感補正を行った後の信号と元の信号とを比較することで、コードブックから誤差が最小になるものを探索する。これを単純に実行すると探索に大きな計算量が必要で、計算量を減らすための工夫が必要になる。またコードブックのサイズが大きくなると多量のメモリも必要である。ACELP はこれらを改善するために考案された。

ACELP で使われているコードブックの基本的なアイデアは、ハミング符号など誤り訂正符号の考え方に近い^[3]。ハミング符号などでは符号空間内に特定の規則を用いて距離（たとえばハミング距離）が等しくなるよう符号を割り当て、誤ったビットパターンに対して最も距離が近い符号を正しい符号（訂正済み符号）と見なす。同様に、ACELP で使われているコードブックは振幅が+1/-1のパルスを一定の規則で割り当てたものを用い、その中で誤差が最小になるものを符号化結果とする。規則的に生成したコードブックはメモリを消費せず、誤差が最小になるものを探索するのにも合理的である。

ACELP では振幅が固定のパルスを使うため、1つのパルスでの線形予測フィルターの出力を求めておけば全てのパルスの和による出力はそれらの合成により求められ、計算量を削減できる。また、一般に誤差を最小にするために必要な+1/-1パルスは少数でよいことが分かっており、これを利用しさらにアルゴリズムを効率化している^[2]。

以下にITU G.722.2 コーデック（12.65kbpsモード時）の固定コードブックの例を示す ^[4]。 64 サンプルからなる処理単位（サブフレーム）を以下の 4 トラックに分け、それぞれに対して 2 ビット（全体で 8 ビット）の+1/-1パルスを割り当てる。

ACELP 固定コードブックの例　（ITU G.722.2（12.65kbpsモード時））
トラック	値	パルス	パルス位置
1	±1	i₀, i₄	0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60
2	±1	i₁, i₅	1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61
3	±1	i₂, i₆	2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62
4	±1	i₃, i₇	3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63

ITU G.722.2 は複数のビットレートをサポートするが、高ビットレートでは1トラックに割り当てるパルスの数を増やし、低ビットレートの場合は１トラックに割り当てるパルスの数を減らしたりトラックの数を減らしたりする。固定コードブックをこのように柔軟に再構成できるのは ACELP の特徴の1つである。

応用

以下ではACELP を応用したアルゴリズムについて述べる。

CS-ACELP

ACELP を応用したアルゴリズムの代表的なものとして、ITU-T G.729（8kbps）で使用されている CS-ACELP（conjugate structure - ACELP、共役構造ACELP）がある。

一般に、共役構造とはコードブックを以下のように2つのコードブックの線形結合で表すものでベクトル量子化のために使用され、最初は CELP の応用である CS-CELP で使用された。ここで c_i , c_j はそれぞれコードブックを、α は係数を表す。

c_{i,j}=\alpha _{1}c_{i}+\alpha _{2}c_{j}\

この方法は2ステージのベクトル量子化によく似た方法で、単純なベクトル量子化と比べビット誤りに強くなり、コードブックのために必要なメモリが減り、計算の複雑さを減らす効果がある^[5]。

CS-ACELP は ACELP に共役構造のコードブックを組み合わせたものである。ITU-T G.729 では2つのコードブックの単純な和の形で表されている。

c_{i,j}=c_{i}+c_{j}\

脚注

^ J.-P. Adoul, P. Mabilleau, M. Delprat, S. Morisette: Fast CELP coding based on algebraic codes, Proc. IEEE Int. Conf. Acoust. Speech Signal Process. pp.1957-1960, 1987.
^ ^a ^b C. Laflamme, J.-P. Adoul, H.Y. Su, S. Morisette: On reducing computational complexity of codebook search in CELP coder through the use of algebraic codes, Proc. IEEE Int. Conf. Acoust. Speech Signal Process, pp.177-180, 1990.
^ ^a ^b Jacob Benesty, M. M. Sondhi, Yiteng Huang (ed). Springer Handbook of Speech Processing. pp.371-377, Springer, 2007. ISBN 978-3540491255.
^ ITU-T. “G.722.2 : Wideband coding of speech at around 16 kbit/s using Adaptive Multi-Rate Wideband (AMR-WB)”. ITU-T. 2010年7月5日閲覧。
^ Jacob Benesty, M. M. Sondhi, Yiteng Huang (ed). Springer Handbook of Speech Processing. pp.377, Springer, 2007. ISBN 978-3540491255.

参考文献

Jacob Benesty, M. M. Sondhi, Yiteng Huang (ed). Springer Handbook of Speech Processing. Springer, 2007. ISBN 978-3540491255.
Mark Hasegawa-johnson, Abeer Alwan. Speech Coding: Fundamentals and Applications. 2003.