Subcode graphs of linear block codes

Abstract

The Hamming-distance related lattice of subcodes of a linear code C is represented by a subcode graph. The dimensions of these subcodes and the dimensions of the subcodes of the dual are related by MacWilliams-like identities. The coordinate permutation problem for minimum trellis-complexity is approached by introducing suitable vertex functions on the subcode graph that reflects the trellis-complexity measure. This approach gives a simple new proof for well-known results on maximum-distance separable (MDS) codes and a slight sharpening of the Wolf bound for a large class of binary codes.