Optimal index assignment for multiple description lattice vector quantization

Optimal index assignment of multiple description lattice vector quantizer (MDLVQ) can be posed as a large-scale linear assignment problem. But is this expensive algorithmic approach necessary? This paper presents a simple index assignment algorithm for high-resolution MDLVQ of K ≥ 2 balanced descriptions in any dimensions. Despite its simplicity, the new algorithm is optimal for a large family of lattices encountered in theory and practice, in terms of minimizing the expected distortion for any side description loss rate and any side entropy rate. This work offers exact combinatoric constructions of optimal index assignments, rather than arguing for the optimality asymptotically. Consequently, the optimality holds for all values of sublattice index N (i.e., over all trade-offs between the central and side distortions), rather than for very large N only. Furthermore, the time complexity of the new algorithm is O(N) as opposed to O(N⁶) for a current linear assignment-based method. New and improved closed form expressions of the expected distortion as the function of N and K are also presented. Thus the optimal values of N and K can be computed.