A quasi-dyadic (QD) parity check code is a code whose parity check matrix representation is block structured with dyadic matrices as blocks. Depending on the number of nonzero positions in the leading row of each block, these codes may be either low density or moderate density. Moreover, each block is reproducible, giving QD codes advantages similar to quasi-cyclic (QC) codes. In this paper we examine basic code properties of QD-LDPC and QD-MDPC codes. These codes have potential to be of use in standard error correction applications as well as code-based cryptography due to their smaller key size.

In this paper, we define a window code to be the portion of an SC-LDPC code seen by a single iteration of a windowed decoder. We consider the design of SC-LDPC codes for windowed decoding via optimization of the window code. In particular, because iterative decoding is optimal on codes with cycle-free graph representations, we ask fundamental questions about the construction and parameters of cycle-free window codes. Further, we show that it is possible to have an SC-LDPC code with cycles and with cycle-free window codes.

Absorbing sets are combinatorial structures in a Tanner graph that have been shown to characterize iterative decoder failure, and particularly error floor behavior, of LDPC codes. In this paper, we examine the connection between absorbing sets and the syndromes of their support vectors. Using this framework, we provide a new characterization of fully absorbing sets, which have been considered the most harmful for iterative decoders. We also show how the sets of absorbing set support vectors appear as translates of codewords in subspaces of the code. These techniques are used to derive new search methods for absorbing sets.

LT codes are a class of rateless codes designed for data dissemination on erasure channels. In this paper, we present a decoder for LT codes on partial erasure channels, which were recently introduced for multi-level read storage channel applications. We compare the efficiency of LT codes on these channels to those on the q-ary Erasure Channel (QEC).

Due to a structural feature in the programming process of MLC (two bits per cell) and TLC (three bits per cell) flash memory, the majority of errors that occur are single-bit errors. Moreover, the voltages used to store the bits typically result in different bit error probabilities for the two or three types of bits. In this work we analyze binary regular LDPC codes in the standard bit-interleaved coded modulation implementation, assuming different probabilities on the bits, to determine what ratio of each type of bit should be connected at the check nodes to improve the decoding threshold. We then propose a construction of nonbinary LDPC codes using their binary images, resulting in check node types that come close to these optimal ratios.

Random lifts of graphs, or equivalently, random permutation matrices, have been used to construct good families of codes known as protograph codes. An algebraic analog of this approach was recently presented using voltage graphs, and it was shown that many existing algebraic constructions of graph-based codes that use commuting permutation matrices may be seen as special cases of voltage graph codes. Voltage graphs are graphs that have an element of a finite group assigned to each edge, and the assignment determines a specific lift of the graph. In this paper we discuss how assignments of permutation group elements to the edges of a base graph affect the properties of the lifted graph and corresponding codes, and present a construction method of LDPC code ensembles based on non-commuting permutation matrices. We also show encoder and decoder implementations for these codes.

Nested codes have been employed in a large number of communication applications as a specific case of superposition codes, for example to implement binning schemes in the presence of noise, in joint network-channel coding, or in physical-layer secrecy. Whereas nested lattice codes have been proposed recently for continuous-input channels, in this paper we focus on the construction of nested linear codes for joint channel-network coding problems based on algebraic photograph LDPC codes. In particular, over the past few years several constructions of codes have been proposed that are based on random lifts of suitably chosen base graphs. More recently, an algebraic analog of this approach was introduced using the theory of voltage graphs. In this paper we illustrate how these methods can be used in the construction of nested codes from algebraic lifts of graphs.

Several well-known structure-based constructions of LDPC codes, for example codes based on permutation and circulant matrices and in particular, quasi-cyclic LDPC codes, can be interpreted via algebraic voltage assignments. We explain this connection and show how this idea from topological graph theory can be used to give simple proofs of many known properties of these codes. In addition, the notion of Abelian-inevitable cycle is introduced and the subgraphs giving rise to these cycles are classified. We also indicate how, by using more sophisticated voltage assignments, new classes of good LDPC codes may be obtained.

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

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.