2011/02/14 by Navin Kashyap, Kashyap, Navin, Andrew Thangaraj +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Coding theory and cryptography #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Protein Degradation and Inhibitors
paper · doi:10.48550/arxiv.1102.2734
openalex publication_date 2011/02/14 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. 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 prove the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes.