As an example, the well-known turbo codes and turbo decoding methods [6,11] constitute a special case of this general approach to the decoding problem. Factor-graph representations for turbo codes were introduced in [65,66], where it is also shown that turbo decoding is an instance of a general decoding procedure, known as the sum-product algorithm. Another extensively studied [22,62] special case is trellis decoding of block and convolutional codes. It is shown in [33,66] that the Viterbi algorithm on a trellis is an instance of the min-sum iterative decoding procedure, when applied to a simple factor graph. The forward-backward algorithm on a trellis, due to Bahl, Cocke, Jelinek, and Raviv [3], is again a special case of the sum-product decoding algorithm. More general iterative algorithms on factor graphs, collectively termed the ``generalized distributive law'' or GDL, were studied by Aji and McEliece [1,2]. These algorithms encompass maximum-likelihood decoding, belief propagation in Bayesian networks [23,47], and fast Fourier transforms as special cases.
It is proved in [1,55,66] that the min-sum, the sum-product, the GDL, and other versions of iterative decoding on factor graphs all converge to the optimal solution if the underlying factor graph is cycle-free. If the underlying factor graph has cycles, very little is known regarding the convergence of iterative decoding methods.
This work is concerned with an important special type of factor graphs, known as Tanner3.1 graphs. The subject dates back to the work of Gallager [25] on low-density parity-check codes in 1962. Some 20 years later, Tanner [55] extended the approach of Gallager [25,26] to codes defined by general bipartite graphs, with the two types of vertices representing code symbols and checks (or constraints), respectively. He also introduced the min-sum and the sum-product algorithms, and proved that they converge on cycle-free graphs. More recently, codes defined on sparse (regular) Tanner graphs were studied by Spielman [50,53], who showed that such codes become asymptotically good if the underlying Tanner graph is a sufficiently strong expander. These codes were studied in a different context by MacKay and Neal [40,41], who demonstrated by extensive experimentation that iterative decoding on Tanner graphs can approach channel capacity to within about 1dB. Latest variants [39] of these codes come within about 0.3db from capacity, and outperform turbo codes.
In general, a Tanner graph for a code
of
length n over an alphabet A is a pair
(
,
),
where
= (V, E) is a bipartite graph and
= {
1,
2,...,
r}
is a set of codes over A, called
behaviors or constraints.
We denote the two vertex classes of
by
and
, so that
V =
.
The vertices of
are called symbol vertices
and
|
| = n, while
the vertices of
are called check vertices
and
|
| = r.
There is a one-to-one correspondence between the
constraints
1,
2,...,
r in
and the check vertices
y1, y2,..., yr in
,
so that
the length of the code
i
is equal to the degree of the vertex
yi
,
for all
i = 1, 2,..., r.
A configuration is an assignment
of a value from A to each symbol vertex
x1, x2,..., xn in
. Thus
a configuration may be thought of
as a vector of length n over A.
Given a configuration
= (
,
,...,
)
and a vertex
y
of degree
,
we define the projection
of
on y as a vector of length
over A obtained from
by retaining
only those values that correspond to the
symbol vertices adjacent to y.
Specifically, if
{xi1, xi2,..., xi
}
is the neighborhood of y in
, then
= (
,
,...,
).
A configuration
is said to be valid if all the
constraints are satisfied, namely if
i
for all
i = 1, 2,..., r. The code
represented
by the Tanner graph
(
,
) is then the set of all valid configurations.
While the foregoing definition of Tanner graphs is quite general,
the theory and practice of the
subject [17,40,39,41,50,55]
is focused almost exclusively on the simple special
case where all the constraints are single-parity-check
codes over
IF2. This work is no exception,
although we will provide for the representation of
linear codes over arbitrary fields by considering
the zero-sum codes over
IFq rather than the binary
single-parity-check codes.
It seems appropriate to call the corresponding
Tanner graphs simple. Notice that
in the case of simple Tanner graphs, the
set of constraints is implied by definition,
so that one can identify a simple Tanner graph
with the underlying bipartite graph
.
All of the Tanner graphs considered in this
correspondence, except in Section5.3, are simple.
Thus, for the sake of brevity, we will henceforth
omit the quantifier ``simple.'' Instead, when
we consider the general case in Section5.3,
we will use the term general Tanner graphs.
We can think of a (simple) Tanner graph
for a binary linear code
of length n
as follows.
Let H be an
r×n parity-check matrix for
.
Then the corresponding Tanner graph for
is simply
the bipartite graph
having H as its
,
adjacency matrix.
It follows that the number of edges in any Tanner graph for a linear code
of length n is O(n2). Thus, if we can represent
by a Tanner graph without cycles, then maximum-likelihood decoding
of
can be achieved in time O(n2), using the min-sum algorithm
for instance.
However, both intuition and experimentation (cf.[40]) suggest that powerful codes cannot be represented by cycle-free Tanner graphs. The notion that cycle-free Tanner graphs can support only weak codes is, by now, widely accepted. Our goal in this correspondence is to make this ``folk knowledge'' more precise. We provide rigorous answers to the question: Which codes can have cycle-free Tanner graphs?
Our results in this regard are two-fold: we derive a characterization of the structure of such codes and an upper bound on their minimum distance. The upper bound (Theorem 3.6) shows that codes with cycle-free Tanner graphs provide extremely poor trade-off between rate and distance for each fixed length. This indicates that at very high signal-to-noise ratios these codes will perform badly. In general, however, the minimum distance of a code does not necessarily determine its performance at signal-to-noise ratios of practical interest. Indeed, there exist codes -- for example, the turbo codes of [6,11] -- that have low minimum distance, and yet perform very well at low signal-to-noise ratios. The development of analytic bounds on the performance of cycle-free Tanner graphs under iterative decoding is a challenging problem, which is beyond the scope of this work. Nevertheless, our results on the structure of the corresponding codes indicate that they are very likely to be weak: their parity-check matrix is much too sparse to allow for a reasonable performance even at low signal-to-noise ratios.
The rest of this chapter is organized as follows. We start with some
definitions and auxiliary observations in the next section. In Section3,
we show that if an (n, k, d ) linear code
can be represented by
a cycle-free Tanner graph and has rate
R = k/n
0.5, then d
2.
We furthermore prove that if R < 0.5, then
is necessarily obtained
from a code of rate
0.5 and minimum distance
2 by simply
repeating certain symbols in each codeword. Theorem 3.6 of Section 3.4
constitutes our main result: this theorem gives an upper bound on the
minimum distance of a general linear code that can be represented by
a cycle-free Tanner graph. Furthermore, the bound of Theorem 3.6
is exact. This is proved in Section 3.5 by means of an explicit
construction of a family of (n, k, d ) linear codes that attain
the bound of Theorem 3.6 for all values of n and k.
Asymptotically, for
n
, the upper bound
takes the form:
http://people.bu.edu/trachten