Linear (zero-one) programming approach to fixed-rate entropy-coded vector quantisation

The problem of the decoding of a shaped set is formulated in terms of a zer o-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 applicat ions 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 fo r the quantisation of a memoryless Gaussian source demonstrating substantia l (of the order of a few tens to a few hundred times) reduction in the comp lexity with respect to the conventional methods based on dynamic programmin g. It is generally observed that the complexity of the proposed method has a linear increase with respect to the quantiser dimension. The correspondin g numerical results show that it is possible to get very close to the bound s determined by the rate-distortion theory, while keeping the complexity at a relatively low level.