Enumerative Algebraic Coding for ACELP

Tom Bäckström

Abstract: Algebraic Code Excited Linear Prediction (ACELP) is a cornerstone of modern speech coding standards, yet traditional methods for encoding pulse positions often fail to reach theoretical efficiency limits. This paper introduces an enumerative algebraic coding approach that maps unique pulse constellations to a single state index. By employing recursive partitioning and joint track encoding, the method achieves the theoretical minimum bit consumption for a given codebook. Evaluation against the AMR-WB standard shows bit-rate reductions of up to 8.8% at high bit-rates, offering a path toward more efficient mobile communications without sacrificing audio fidelity.

Introduction

Modern voice communication relies heavily on speech codecs like AMR-WB and G.718. These systems utilize ACELP to model the residual speech signal—the stochastic component remaining after linear prediction. In ACELP, this residual is represented by a set of signed pulses placed on a fixed grid, known as a codebook.

A critical challenge in codec design is the efficient encoding of these pulse positions and signs. As audio quality requirements increase, so does the number of pulses, making traditional ad-hoc encoding methods increasingly suboptimal. These methods often waste bits by implicitly encoding the order of pulses or failing to provide a strictly constant bit-rate. This paper proposes a mathematically rigorous enumerative approach to address these inefficiencies.

Methodology: Enumerative Algebraic Coding

The core innovation lies in treating the entire arrangement of pulses as a single "state" within the set of all possible valid configurations. Instead of encoding each pulse individually, the algorithm calculates a unique index for the specific constellation.

State Enumeration

The algorithm uses a recursive formula to determine the total number of unique ways to place $p$ pulses in a vector of length $N$. This approach naturally ignores the order of pulses, which is irrelevant to the final signal, thereby eliminating redundant information.

Table illustrating the mapping of specific pulse configurations at positions 1 and 2 to unique state numbers.

As shown in the table above, different combinations of pulse magnitudes and signs at specific positions are assigned distinct state numbers. This ensures that every valid configuration has a unique, compact representation.

Recursive Partitioning

To efficiently find the state number for a complex constellation, the paper employs a "divide and conquer" strategy. The vector is split into smaller segments, and the algorithm recursively determines how many pulses fall into each part.

Table showing the hierarchical state enumeration based on pulse distribution across different positions.

This hierarchical approach allows the codec to handle large codebooks with minimal computational overhead, as the state can be calculated or decoded using a limited number of operations.

Joint Track Encoding

ACELP pulses are typically organized into interlaced tracks. When a track's total number of states is not a power of two, encoding it in isolation results in "fractional bits" being wasted. The author proposes encoding multiple tracks together. By combining the state spaces of several tracks, the total number of states moves closer to a power of two, minimizing overhead and bringing bit consumption closer to the theoretical entropy limit.

Performance Evaluation

The proposed method was evaluated against the specifications of the AMR-WB standard. Because the underlying codebook remains identical, the audio quality is preserved perfectly; the gains are purely in transmission efficiency.

Key findings include:

  • Per-Track Efficiency: For a track of length 16 with 6 pulses, the enumerative method requires only 20.56 bits, a significant improvement over the 22 bits used in the AMR-WB standard.
  • System-Wide Bit-rate Reduction: When applied to a 23.85 kbit/s AMR-WB stream, the algebraic codebook payload can be reduced by 20 bits per frame. This translates to an overall saving of approximately 1 kbit/s, reducing the total bit-rate to 22.85 kbit/s.

Conclusion and Future Directions

Enumerative algebraic coding provides a robust framework for maximizing the efficiency of ACELP-based speech codecs. While the implementation requires handling large integer arithmetic for joint track encoding, the computational cost remains low enough for mobile hardware. Future work may explore flexible pulse allocation between tracks to further optimize bit distribution in varying acoustic environments.

Summary updated

Abstract

Speech coding algorithms based on Algebraic Code Excited Linear Prediction (ACELP) quantize and code the residual signal with a fixed algebraic codebook. This paper generalizes the conventional encoding to provide optimal bit consumption for all codebook designs by enumerating all possible states. The codebook designed is aimed for constant bit-rate applications applied on mobile devices.
BibTeX
@inproceedings{backstrom2012enumerative,
  author = {Tom Bäckström},
  title = {{Enumerative Algebraic Coding for ACELP}},
  booktitle = {Interspeech},
  year = {2012},
  doi = {10.21437/interspeech.2012-279},
}
Figure