Nonergodic fading is a useful model for various wireless communication channels in both indoor and outdoor environments. With this model, a codeword is divided into multiple blocks such that fading is constant within a block and independent across blocks. Building on Poltyrev's work on infinite lattice constellations for the Gaussian channel, we derive a Poltyrev outage limit for lattice constellations transmitted over a block-faded channel. We prove that the diversity order of this Poltyrev outage limit is equal to the number of degrees of freedom in the channel. An important application is in decoding low-density lattice codes. With block fading, the presence of an outage may dramatically increase the runtime of both sphere and iterative decoders. Using our newly defined Poltyrev outage limit, decoding is not performed whenever an outage is declared, which drastically reduces the overall decoding time.

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z4, GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.

Linear Programming (LP) decoding is emerging as an attractive alternative to decode Low-Density Parity-Check (LDPC) codes. However, the earliest LP decoders proposed for binary and nonbinary LDPC codes are not suitable for use at moderate and large code lengths. To overcome this problem, Vontobel et al. developed an iterative Low-Complexity LP (LCLP) decoding algorithm for binary LDPC codes. The variable and check node calculations of binary LCLP decoding algorithm are related to those of binary Belief Propagation (BP). The present authors generalized this work to derive an iterative LCLP decoding algorithm for nonbinary linear codes. Contrary to binary LCLP, the variable and check node calculations of this algorithm are in general different from that of nonbinary BP. The overall complexity of nonbinary LCLP decoding is linear in block length; however the complexity of its check node calculations is exponential in the check node degree. In this paper, we propose a modified BCJR algorithm for efficient check node processing in the nonbinary LCLP decoding algorithm. The proposed algorithm has complexity linear in the check node degree. We also introduce an alternative state metric to improve the run time of the proposed algorithm. Simulation results are presented for (504, 252) and (1008, 504) nonbinary LDPC codes over ℤ4.

For binary linear codes with short and medium block length ML decoding can be achieved by solving the associated integer programming (IP) problem with a general purpose solver. IP also offers algorithms for computing the minimum distance. In this article, we present several IP formulations and computationally compare them on various LDPC and BCH codes. Most of these formulations are obtained by forcing integrality on linear programming (LP) decoding formulations proposed in the literature.

Maximum likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an integer programming (IP) problem. Feldman relaxed this IP problem and presented linear programming (LP) based decoding. In this paper, we propose a new separation algorithm to improve the error-correcting performance of LP decoding for binary linear block codes. We use an IP formulation with indicator variables that help in detecting the violated parity checks. We derive Gomory cuts from the IP and use them in our separation algorithm. An efficient method of finding cuts induced by redundant parity checks (RPC) is also proposed. Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. It is demonstrated on three LDPC codes and two BCH codes that our separation algorithm performs significantly better than LP decoding and belief propagation (BP) decoding.

We study an integer programming (IP) based separation approach to find the maximum likelihood (ML) codeword for binary linear codes. An algorithm introduced in Tanatmis et al. is extended and improved with respect to decoding performance without increasing the worst case complexity. This is demonstrated on the LDPC and the BCH code classes. Moreover, we propose an integer programming formulation to calculate the minimum distance of a binary linear code. We exemplarily compute the minimum distance of the (204, 102) LDPC code and the (576, 288) WIMAX code. Using the minimum distance of a code, a new class of valid inequalities is introduced.