This paper presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite value$t$that is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.

We present a tree-based construction of low-density parity-check (LDPC) codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a$d$-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degrees$d=p^s$and$d = p^s+1$, for$p$a prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes; the other codes presented are new. We also present some bounds on pseudocodeword weight for$p$-ary LDPC codes. Treating these codes as$p$-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite-geometry LDPC codes where$p > 2$.

Pseudocodewords of q-ary LDPC codes are examined and the weight of a pseudocodeword on the q-ary symmetric channel is defined. The weight definition of a pseudocodeword on the AWGN channel is also extended to two-dimensional q-ary modulation such as q-PAM and q-PSK. The tree-based lower bounds on the minimum pseudocodeword weight are shown to also hold for q-ary LDPC codes on these channels

A three terminal erasure relay channel is considered. It has been shown that appropriately designed maximum distance separable codes achieve the cut-set upper bound on capacity of the three terminal erasure relay channel. This paper presents low-density parity-check (LDPC) coding alternatives for this channel. Design rules for constructing LDPC codes that perform close to the cut-set upper bound on capacity are provided for the general erasure relay channel and also the degraded erasure relay channel, wherein all the information available at the receiver are also available at the relay

We present a construction of LDPC codes that have minimum pseudocodeword weight equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a d-regular tree for a fixed number of layers and employing a connection algorithm based on mutually orthogonal Latin squares to close the tree. Methods are presented for degrees d = psand d = ps+ 1, for p a prime, one of which includes the well-known finite-geometry-based LDPC codes

This paper describes the design and analysis of low-density parity-check (LDPC) codes over rings and shows how these codes, when mapped onto appropriate signal constellations, can be used to effect bandwidth-efficient modulation. Specifically, LDPC codes are constructed over the integer rings /spl Zopf//sub m/ and G/sub m//sup 2/ and mapped onto phase-shift keying (PSK)-type signal sets to yield geometrically uniform signal space codes. This paper identifies and addresses the design issues that affect code performance. Examples of codes over /spl Zopf//sub 8/ and G/sub 64/ mapped onto 8-ary and 64-ary signal sets at a spectral efficiency of 1.5 and 2.0 bits per second per hertz (b/s/Hz) illustrate the approach; simulation of these codes over the additive white Gaussian noise (AWGN) channel demonstrates that this approach is a good alternative to bandwidth-efficient techniques based on binary LDPC codes-e.g., bit-interleaved coded modulation.

We examine the structure of pseudocodewords in Tanner graphs and derive lower bounds of pseudocodeword weights. The weight of a pseudocodeword is related to the size of its support set, which forms a stopping set in the Tanner graph.

A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.

The role of low density parity check principles in the design of group codes for coded modulation is examined. In this context, the structure of linear codes over certain rings /spl Zopf//sub m/ and G/sub m/ is discussed, and LDPC codes over these ring structures are designed.