On the pseudocodeword weight and parity-check matrix redundancy of linear codes
Christine A. Kelley, Deepak Sridhara · 2007
The minimum pseudocodeword weightwminof a linear graph-based code is more influential in determining decoding performance when decoded via iterative and linear programming decoding algorithms than the classical minimum distancedminunder standard maximum-likelihood decoding Moreover, unlike the minimum distance which is unique to the code regardless of representation, the set of pseudocodewords, and therefore also the minimum pseudocodeword weight, depends on the graph representation used in decoding as well as on the communication channel. This means that a judicious choice of parity-check matrix is crucial for realizing the best potential of any graph-based code. In this paper, we introduce the notion ofpseudoweightredundancyfor the memoryless binary symmetric channel (BSC). Analogous to the stopping redundancy in the literature, this parameter gives the smallest number of rows needed for a parity-check matrix to havedmin=wmin. We provide some upper bounds on the BSC-pseudoweight redundancy and illustrate the concept with some results for Hamming codes, tree-based and finite geometry LDPC codes, Reed-Muller codes and Hadamard codes.