Title :
On the trellis structure of block codes
Author :
Kschischang, Frank R. ; Sorokine, Vladislav
Author_Institution :
Dept. of Electr. & Comput. Eng., Toronto Univ., Ont., Canada
fDate :
27 Jun-1 Jul 1994
Abstract :
Two main results will be presented: 1. The problem of minimizing the number of states in the trellis for a general (nonlinear) code at a given time index is NP-complete, and thus apparently computationally infeasible for large codes. 2. Minimal linear block code trellises correspond to configurations of non-attacking rooks on a triangular chess board. This correspondence can be used to enumerate the minimal trellises, and also to obtain insight into various bounds on the size of the trellises
Keywords :
block codes; computational complexity; linear codes; minimisation; trellis codes; block codes; bounds; minimal linear block code trellises; nonattacking rooks; nonlinear code; number of states minimization; trellis structure; triangular chess board; Automata; Bipartite graph; Block codes; Galois fields; Linear code; Radio access networks;
Conference_Titel :
Information Theory, 1994. Proceedings., 1994 IEEE International Symposium on
Conference_Location :
Trondheim
Print_ISBN :
0-7803-2015-8
DOI :
10.1109/ISIT.1994.394681
