On the pseudocodeword weight and parity-check matrix redundancy of linear codes

The minimum pseudocodeword weight w _min of 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 distance d _min under 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 of pseudoweight redundancy for 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 have d _min = w _min. 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.