On Computation of Performance Bounds of Optimal Index Assignment

X. Wu(xwuece.mcmaster.ca)
H.D. Mittelmann(mittelmannasu.edu)
X. Wang(wangxiaohangmail.com)
J. Wang(jiawangsjtu.edu.cn)

Abstract: Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in- stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a progress in the research of index assignment optimization. We apply some recent results of QAP research to compute the strongest lower bounds so far for channel distor- tion of BSC among all index assignments. The strength of the resulting lower bounds is validated by comparing them against the upper bounds produced by heuristic index assignment algorithms.

Keywords: Index assignment, quantization, error resilience, quadratic assign- ment, semide¯nite programming, relaxation.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Applications -- Science and Engineering (Other )

Citation:

Download: [PDF]

Entry Submitted: 02/18/2010
Entry Accepted: 02/18/2010
Entry Last Modified: 02/18/2010

Modify/Update this entry