Title :
On the treewidth of MDS and Reed-Muller codes
Author :
Kashyap, Navin ; Thangaraj, Andrew
Author_Institution :
Dept. of Electr. Commun. Eng., Indian Inst. of Sci., Bangalore, India
fDate :
July 31 2011-Aug. 5 2011
Abstract :
The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parametrization of the maximum-likelihood decoding complexity for linear codes. In this paper, we compute exact expressions for the treewidth of maximum distance separable codes, and first- and second-order Reed-Muller codes. These results constitute the only known explicit expressions for the treewidth of algebraic codes.
Keywords :
Reed-Muller codes; algebraic codes; maximum likelihood decoding; tree codes; MDS; Reed Muller codes; cycle free graphical realizations; least constraint complexity; linear codes; maximum distance separable codes; maximum likelihood decoding complexity; treewidth; Complexity theory; Hamming weight; Indexes; Linear code; Maximum likelihood decoding; Minimization; Particle separators;
Conference_Titel :
Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on
Conference_Location :
St. Petersburg
Print_ISBN :
978-1-4577-0596-0
Electronic_ISBN :
2157-8095
DOI :
10.1109/ISIT.2011.6033887
