DocumentCode
3505701
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
fYear
2011
fDate
July 31 2011-Aug. 5 2011
Firstpage
1925
Lastpage
1929
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on
Conference_Location
St. Petersburg
ISSN
2157-8095
Print_ISBN
978-1-4577-0596-0
Electronic_ISBN
2157-8095
Type
conf
DOI
10.1109/ISIT.2011.6033887
Filename
6033887
Link To Document