A Low Complexity Method for Fixed-rate Entropy-coded Vector Quantization based on Integer Programming

This paper describes a new approach to Fixed-rate Entropy-coded Vector Quantization (FEVQ) for stationary memoryless sources where the structure of code-words are derived from a variable-length scalar quantizer. We formulate the quantization search operation as a zero-one integer optimization problem [1], and show that the resulting integer program can be closely approximated by solving a simple linear program. The result is a Lagrangian formulation which adjoins the constraint on the entropy (codeword length) to the distortion. Unlike the previously known methods with a fixed Lagrangian multiplier (fixed-slope, and variable rate output), we use an iterative algorithm to optimize the underlying objective function while updating the Lagrange multiplier until the constraint on the overall rate is satisfied (ensured to be fixed-rate). This results in a chain of improving solutions which moves towards the optimum point as fast as possible (in the sense that the changes in the objective function value at each step is maximized). In order to achieve some packing gain, we combine the process of Trellis Coded Quantization (TCQ) with that of FEVQ. This results in an iterative application of the Viterbi algorithm on the underlying trellis for optimizing the Lagrangian multiplier. Numerical results are presented demonstrating substantial improvement in comparison with the alternative methods reported in the literature