Title :
Te “art of trellis decoding” is computationally hard-for large fields
Author :
Jain, Kamal ; Mandoin, I. ; Vazirani, Vijay V.
Author_Institution :
Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA, USA
fDate :
5/1/1998 12:00:00 AM
Abstract :
The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of trellis complexity are considered: the total number of states, the total number of edges, and the maximum state complexity of the trellis. The problem is proven NP-hard for all three measures, provided the field over which the code is specified is not fixed. We leave open the problem of dealing with the case of a fixed field, in particular GF(2)
Keywords :
combinatorial mathematics; computational complexity; decoding; minimisation; trellis codes; GF(2); MDS codes; NP-hard problem; code; coordinate permutation; fixed field; maximum distance separable codes; maximum state complexity; total edges number; total states number; trellis complexity; trellis decoding; AWGN; Decoding; Digital communication; Frequency shift keying; Rayleigh channels; Satellite broadcasting; Spread spectrum radar; Subspace constraints; Transponders; Viterbi algorithm;
Journal_Title :
Information Theory, IEEE Transactions on
