Linear (zero–one) programming approach to fixed-rate entropy-coded vector quantisation
Amir Keyvan Khandani · IEE Proceedings - Communications · 1999
The problem of the decoding of a shaped set is formulated in terms of a zero–one linear program. Some special features of the problem are exploited to relax the zero–one constraint, and to substantially reduce the complexity of the underlying simplex search. The proposed decoding method has applications in fixed-rate entropy-coded vector quantisation of a memoryless source, in decoding of a shaped constellation, and in the bit allocation problem. The first application is considered and numerical results are presented for the quantisation of a memoryless Gaussian source demonstrating substantial (of the order of a few tens to a few hundred times) reduction in the complexity with respect to the conventional methods based on dynamic programming. It is generally observed that the complexity of the proposed method has a linear increase with respect to the quantiser dimension. The corresponding numerical results show that it is possible to get very close to the bounds determined by the rate-distortion theory, while keeping the complexity at a relatively low level.