Minimax nonredundant channel coding

The distortion of a message due to channel noise can be alleviated significantly without redundant error control bits by judicious assignment of binary indices to message symbols. The nonredundant coding gain relies only on a notion of distance between symbols. In this paper, we consider the index assignment problem and adopt a minimax design criterion instead of the usual mean squared error (MSE) measure. The problem is found to be NP-hard, and an effective, heuristic, polynomial-time algorithm is presented for computing approximate solutions. The minimax criterion yields greatly improved worst case performance while maintaining good average performance. In addition, the familiar MSE criterion is shown likewise to yield an NP-hard index assignment task. The MSE problem is a special case of the classical quadratic assignment problem, for which computationally and theoretically useful results are available from the discrete mathematics literature.>