Title :
On the intractability of permuting a block code to minimize trellis complexity
Author :
Horn, Gavin B. ; Kschischang, Frank R.
Author_Institution :
Dept. of Electr. & Comput. Eng., Toronto Univ., Ont., Canada
fDate :
11/1/1996 12:00:00 AM
Abstract :
An important problem in the theory and application of block code trellises is to find a coordinate permutation of a given code to minimize the trellis complexity. We show that the problem of finding a coordinate permutation that minimizes the number of vertices at a given depth in the minimal trellis for a binary linear block code is NP-complete
Keywords :
binary sequences; block codes; combinatorial mathematics; computational complexity; linear codes; trellis codes; NP-complete problem; binary linear block code; block code trellises; optimal coordinate permutation; trellis complexity minimisation; vertices; Art; Block codes; Communication system control; Decoding; Error analysis; Helium; Informatics; Lattices; Linear code; NP-complete problem;
Journal_Title :
Information Theory, IEEE Transactions on
