We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine a generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which Are typically smaller than trellis representations and have enjoyed Much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm has been proven to converge always to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tannergraphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.
We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine a generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which Are typically smaller than trellis representations and have enjoyed Much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm has been proven to converge always to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tannergraphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.
We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which are smaller than trellis representations and have enjoyed much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm is proven to always converge to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tanner graphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.
Iterative decoding techniques have become a viable alternative for constructing high performance coding systems. In particular, the recent success of turbo codes indicates that performance close to the Shannon limit may be achieved. In this thesis, it is showed that many iterative decoding algorithms are special cases of two generic algorithms, the min-sum and sum-product algorithms, which also include non-iterative algorithms such as Viterbi decoding. The min-sum and sum-product algorithms are developed and presented as generalized trellis algorithms, where the time axis of the trellis is replaced by an arbitrary graph, the "Tanner graph". With cycle-free Tanner graphs, the resulting decoding algorithms (e.g., Viterbi decoding) are maximum-likelihood but suffer from an exponentially increasing complexity. Iterative decoding occurs when the Tanner graph has cycles (e.g., turbo codes); the resulting algorithms are in general suboptimal, but significant complexity reductions are possible compared to the cycle-free case. Several performance estimates for iterative decoding are developed, including a generalization of the union bound used with Viterbi decoding and a characterization of errors that are uncorrectable after infinitely many decoding iterations.
Abstract A general framework, based on ideas of Tanner, for the description of codes and iterative decoding (“turbo coding”) is developed. Just like trellis‐based code descriptions are naturally matched to Viterbi decoding, code descriptions based on Tanner graphs (which may be viewed as generalized trellises) are naturally matched to iterative decoding. Two basic iterative decoding algorithms (which are versions of the algorithms of Berrou et al. and of Hagenauer, respectively) are shown to be natural generalizations of the forward‐backward algorithm (Bahl et al.) and the Viterbi algorithm, respectively, to arbitrary Tanner graphs. The careful derivation of these algorithms clarifies, in particular, which a priori probabilities are admissible and how they are properly dealt with. For cycle codes (a class of binary linear block codes), a complete characterization is given of the error patterns that are corrected by the generalized Viterbi algorithm after infinitely many iterations.
Until recently, most known decoding procedures for error-correcting codes were based either on algebraically calculating the error pattern or on some sort of tree or trellis search. With the advent of turbo coding, a third decoding principle has finally had its breakthrough: iterative decoding. With respect to Viterbi decoding, a code is most naturally described by means of a trellis diagram. The main thesis of the present paper is that, with respect to iterative decoding, the natural way of describing a code is by means of a Tanner graph, which may be viewed as a generalized trellis. More precisely, it is the "time axis" of a trellis that is generalized to a Tanner graph.
This dissertation presents a systematic exposition on finite-block-length coding theory and practice. We begin with the task of identifying the maximum achievable rates over noisy, finite-block-length constrained channels, referred to as (ε, n)-capacity Cεn, with ε denoting target block-error probability and n the block length. We characterize how the optimum codes look like over finite-block-length constrained channels. Constructing good, short-block-length error-correcting codes defined on sparse graphs is the focus of the thesis. We propose a new, general method for constructing Tanner graphs having a large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. The PEG construction attains essentially the same girth as Gallager's explicit construction for regular graphs, both of which meet or exceed an extension of the Erdös-Sachs bound. The PEG construction proves to be powerful for generating good, short-block-length binary LDPC codes. Furthermore, we show that the binary interpretation of GF(2b) codes on the cycle Tanner graph TG(2, dc), if b grows sufficiently large, can be used over the binary-input additive white Gaussian noise (AWGN) channel as "good code for optimum decoding" and "good code for iterative decoding". Codes on sparse graphs are often decoded iteratively by a sum-product algorithm (SPA) with low complexity. We investigate efficient digital implementations of the SPA for decoding binary LDPC codes from both the architectural and algorithmic point of view, and describe new reduced-complexity derivatives thereof. The unified treatment of decoding techniques for LDPC codes provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency, and computational complexity perspective.
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.