Fundamentals of Codes, Graphs, and Iterative Decoding
1st Edition
Published on 18. April 2006
XIX, 224 pages
978-0-306-47794-2 (ISBN)
Description
Fundamentals of Codes, Graphs, and Iterative Decoding
is an explanation of how to introduce local connectivity, and how to exploit simple structural descriptions. Chapter 1 provides an overview of Shannon theory and the basic tools of complexity theory, communication theory, and bounds on code construction. Chapters 2 - 4 provide an overview of "classical" error control coding, with an introduction to abstract algebra, and block and convolutional codes. Chapters 5 - 9 then proceed to systematically develop the key research results of the 1990s and early 2000s with an introduction to graph theory, followed by chapters on algorithms on graphs, turbo error control, low density parity check codes, and low density generator codes.
More details
Other editions
Additional editions
Stephen B. Wicker | Saejoon Kim
Fundamentals of Codes, Graphs, and Iterative Decoding
Book
10/2002
Kluwer Academic Publishers
€53.49
Shipment within 15-20 days
Content
Digital Communication.- Abstract Algebra.- Linear Block Codes.- Convolutional and Concatenated Codes.- Elements of Graph Theory.- Algorithms on Graphs.- Turbo Decoding.- Low-Density Parity-Check Codes.- Low-Density Generator Codes.
Chapter 5
ELEMENTS OF GRAPH THEORY (p. 79-80)
The graph-theoretic interpretation of error control codes has led to construction techniques for codes whose performance is extremely close to the Shannon limit. The next several chapters discuss these constructions techniques. In this chapter we consider several basic results that will be used throughout the rest of the book.
We begin with a basic definition for graphs, and then proceed to a discussion of the important class of bipartite graphs. A method is presented for transforming a non-bipartite graph into a bipartite graph through the use of edge-vertex incidence graphs. The powerful probabilistic technique of martingales is then introduced as a tool for use in bounding the deviation of a random variable from its expected value. Using this technique, many properties of a graph can be bounded exponentially around their respective expected values. A definition is then given for an expander graph, a graph in which each vertex has a large number of neighbors, where a neighbor is a node to which the first node is directly connected by an edge.
The properties of such graphs will prove useful in that they are natural analogs of codes in which the value of an information bit is spread across several codeword bits. Intuitively, such a situation provides a large number of options for recovering the value of an information bit in the presence of noise. We derive a lower bound on the expansion of a randomly chosen graph.
This result shows that a randomly chosen graph will be an expander with high probability. One important consequence of the proof of this result is that a regular graph is a good expander if and only if the eigenvalue of the graph with the second largest magnitude is well separated from the eigenvalue with the largest magnitude. We provide a lower bound on the second largest eigenvalue of a regular graph and describe an explicit construction for a regular graph that achieves the lower bound. This gives the best explicit expander known.
1. Introduction
We begin with a basic definition for a "graph".
Definition 145 A graph G is an ordered pair (V, E) of a set of vertices V and a set of edges E. An edge is a pair of distinct vertices from V. In a simple example below, the graph consists of the vertex set V = {A, B, C, D, E, F} and the edge set E = {(A, D), (B, D), (C, E), (D, E)}. This particular graph is disconnected in that paths do not exist between arbitrary pairs of vertices in the graph. In this case the vertex F is not connected by an edge to any other vertex. This graph is also undirected in that there is no directionality associated with the edges. In a directed graph, the edges are ordered pairs of vertices, with the first vertex being the originating vertex and the second the terminating vertex.
ELEMENTS OF GRAPH THEORY (p. 79-80)
The graph-theoretic interpretation of error control codes has led to construction techniques for codes whose performance is extremely close to the Shannon limit. The next several chapters discuss these constructions techniques. In this chapter we consider several basic results that will be used throughout the rest of the book.
We begin with a basic definition for graphs, and then proceed to a discussion of the important class of bipartite graphs. A method is presented for transforming a non-bipartite graph into a bipartite graph through the use of edge-vertex incidence graphs. The powerful probabilistic technique of martingales is then introduced as a tool for use in bounding the deviation of a random variable from its expected value. Using this technique, many properties of a graph can be bounded exponentially around their respective expected values. A definition is then given for an expander graph, a graph in which each vertex has a large number of neighbors, where a neighbor is a node to which the first node is directly connected by an edge.
The properties of such graphs will prove useful in that they are natural analogs of codes in which the value of an information bit is spread across several codeword bits. Intuitively, such a situation provides a large number of options for recovering the value of an information bit in the presence of noise. We derive a lower bound on the expansion of a randomly chosen graph.
This result shows that a randomly chosen graph will be an expander with high probability. One important consequence of the proof of this result is that a regular graph is a good expander if and only if the eigenvalue of the graph with the second largest magnitude is well separated from the eigenvalue with the largest magnitude. We provide a lower bound on the second largest eigenvalue of a regular graph and describe an explicit construction for a regular graph that achieves the lower bound. This gives the best explicit expander known.
1. Introduction
We begin with a basic definition for a "graph".
Definition 145 A graph G is an ordered pair (V, E) of a set of vertices V and a set of edges E. An edge is a pair of distinct vertices from V. In a simple example below, the graph consists of the vertex set V = {A, B, C, D, E, F} and the edge set E = {(A, D), (B, D), (C, E), (D, E)}. This particular graph is disconnected in that paths do not exist between arbitrary pairs of vertices in the graph. In this case the vertex F is not connected by an edge to any other vertex. This graph is also undirected in that there is no directionality associated with the edges. In a directed graph, the edges are ordered pairs of vertices, with the first vertex being the originating vertex and the second the terminating vertex.
