The problem of finding a low-complexity Tanner graph for a general lattice /spl Lambda/ is studied. The problem is divided into two subproblems: (1) Finding an orthogonal sublattice /spl Lambda/' of /spl Lambda/ which minimizes the complexity of the label code of the quotient group /spl Lambda///spl Lambda/'. (2) Constructing a simple Tanner graph for the label code obtained in part 1. The proposed approach for solving subproblem 2 can also be applied to any abelian group block code with arbitrary finite alphabets at different coordinates. The results of this work are useful in finding low-complexity graph representation of lattices and codes, which consequently results in efficient graph-based decoding algorithms.
The problem of finding a low-complexity Tanner graph for a general lattice /spl Lambda/ is studied. The problem is divided into two subproblems: (1) Finding an orthogonal sublattice /spl Lambda/' of /spl Lambda/ which minimizes the complexity of the label code of the quotient group /spl Lambda///spl Lambda/'. (2) Constructing a simple Tanner graph for the label code obtained in part 1. The proposed approach for solving subproblem 2 can also be applied to any abelian group block code with arbitrary finite alphabets at different coordinates. The results of this work are useful in finding low-complexity graph representation of lattices and codes, which consequently results in efficient graph-based decoding algorithms.
We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.
If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n,k,d) linear code of rate R=k/n that can be represented by a Tanner graph without cycles. We prove that if R/spl ges/0.5 then d/spl les/2, while if R<0.5 then C is obtained from a code of rate /spl ges/0.5 and distance /spl les/2 by simply repeating certain symbols. In the latter case, we prove that d/spl les/[n/k+1]+[n+1/k+1]<2/R. Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future research.
Abstract—In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method “label-and-decide. ” We prove that the “label-and-decide ” method is applicable to Tanner graphs with a hierarchical structure—pseudo-trees—and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs—the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm—the “label-decide-recompute.” Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than 4 1 M 1 (k 0 1), where M is the number of independent rows in the parity-check matrix and k represents the mean row weight of the parity-check matrix. Index Terms—Encoding stopping set, low-density parity-check (LDPC) codes, linear complexity encoding, pseudo-tree, Tanner graphs.
In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ¿label-and-decide.¿ We prove that the ¿label-and-decide¿ method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ¿label-decide-recompute.¿ Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than4 ·M·((k¿- 1), whereMis the number of independent rows in the parity-check matrix andk¿represents the mean row weight of the parity-check matrix.
The maximum-likelihood decoding of linear block codes by Wagner rule decoding is discussed. In this approach, the Wagner rule decoding, which has been primarily applied to single parity check codes, is employed on acyclic Tanner graphs. Accordingly, a coset decoding equipped with Wagner rule decoding is applied to the decoding of a code C having a Tanner graph with cycles. A subcode C1 of C with acyclic Tanner graph is chosen as the base subcode. All cosets of C1 have the same Tanner graph and are distinguished by their values of parity nodes in the graph. The acyclic Tanner graph of C1, together with a trellis representation of the space of the parity sequences, represent the code C. This graphical representation provides a unified and systematic approach to search for an efficient method for the maximum-likelihood decoding of a given linear block code. It is shown that the proposed method covers the most efficient techniques known for the decoding of some important block codes, including the hexacode H6, extended Golay codes, Reed–Muller codes, Hamming code and (32, 16, 8) quadratic residue codes. The generalisation to the decoding of lattices is briefly explained.
Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands