MINIMAX NONREDUNDANT CHANNEL CODING

The distortion of a message due to channel noise can be alleviated sig nificantly without redundant error control bits by judicious assignmen t of binary indices to message symbols. The nonredundant coding gain r elies only on a notion of distance between symbols. In this paper, we consider the index assignment problem and adopt a minimax design crite rion instead of the usual mean squared error (MSE) measure. The proble m is found to be NP-hard, and an effective, heuristic, polynomial-time algorithm is presented for computing approximate solutions. The minim ax criterion yields greatly improved worst case performance while main taining good average performance. In addition, the familiar MSE criter ion is shown likewise to yield an NP-hard index assignment task. The M SE problem is a special case of the classical Quadratic Assignment Pro blem, for which computationally and theoretically useful results are a vailable from the discrete mathematics literature.