Computer Science – Information Theory
Scientific paper
2011-02-14
Computer Science
Information Theory
This constitutes a major upgrade of previous versions; submitted to IEEE Transactions on Information Theory
Scientific paper
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.
Kashyap Navin
Thangaraj Andrew
No associations
LandOfFree
The Treewidth of MDS and Reed-Muller Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Treewidth of MDS and Reed-Muller Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Treewidth of MDS and Reed-Muller Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-215585