Wicker Fundamentals of Codes, Graphs, and Iterative Decoding

1. Auflage 2006
ISBN: 978-0-306-47794-2
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 714, 243 Seiten

Reihe: The Springer International Series in Engineering and Computer Science

Fundamentals of Codes, Graphs, and Iterative Decoding contains need-to-know information for both professionals and academicians working in the field of communications.

Fifty years of learning how to design good codes can now be reduced to a single sentence: Good codes have a high degree of local connectivity, but must have simple structural descriptions to facilitate iterative decoding.

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.

Fundamentals of Codes, Graphs, and Iterative Decoding is intended as a synthesis of recent research results with a recognition of where these results fit into the bigger picture of error control coding.

Containing hundreds of theorems, proofs, and definitions, Fundamentals of Codes, Graphs, and Iterative Decoding is suitable for a graduate-level course in communications, as well as for a professional reference.

Autoren/Hrsg.

Wicker, Stephen B.

Inhaltsverzeichnis

1;Contents;6
2;List of Figures;9
3;List of Tables;11
4;Preface;13
5;Chapter 1 DIGITAL COMMUNICATION;20
5.1;1. Basics;20
5.2;2. Algorithms and Complexity;24
5.3;3. Encoding and Decoding;25
5.4;4. Bounds;27
5.5;5. Overview of the Text;31
6;Chapter 2 ABSTRACT ALGEBRA;32
6.1;1. Sets and Groups;32
6.2;2. Rings, Domains, and Fields;35
6.3;3. Vector Spaces and GF;42
6.4;4. Polynomials over Galois Fields;47
6.5;5. Frequency Domain Analysis of Polynomials over GF(q);53
6.6;6. Ideals in the Ring;56
7;Chapter 3 LINEAR BLOCK CODES;58
7.1;1. Basic Structure of Linear Codes;59
7.2;2. Repetition and Parity Check Codes;62
7.3;3. Hamming Codes;63
7.4;4. Reed-Muller Codes;64
7.5;5. Cyclic Codes;68
7.6;6. Quadratic Residue Codes;69
7.7;7. Golay Codes;70
7.8;8. BCH and Reed-Solomon Codes;72
7.9;9. Product Codes;77
8;Chapter 4 CONVOLUTIONAL AND CONCATENATED CODES;80
8.1;1. Convolutional Encoders;81
8.2;2. Analysis of Component Codes;84
8.3;3. Concatenated Codes;87
8.4;4. Analysis of Parallel Concatenated Codes;90
9;Chapter 5 ELEMENTS OF GRAPH THEORY;98
9.1;1. Introduction;99
9.2;2. Martingales;102
9.3;3. Expansion;105
10;Chapter 6 ALGORITHMS ON GRAPHS;112
10.1;1. Probability Models and Bayesian Networks;113
10.2;2. Belief Propagation Algorithm;118
10.3;3. Junction Tree Propagation Algorithm;123
10.4;4. Message Passing and Error Control Decoding;128
10.5;5. Message Passing in Loops;134
11;Chapter 7 TURBO DECODING;140
11.1;1. Turbo Decoding;140
11.2;2. Parallel Decoding;145
11.3;3. Notes;151
12;Chapter 8 LOW-DENSITY PARITY-CHECK CODES;156
12.1;1. Basic Properties;156
12.2;2. Simple Decoding Algorithms;162
12.3;3. Explicit Construction;166
12.4;4. Gallager’s Decoding Algorithms;170
12.5;5. Belief Propagation Decoding;181
12.6;6. Notes;191
13;Chapter 9 LOW-DENSITY GENERATOR CODES;196
13.1;1. Introduction;196
13.2;2. Decoding Analyses;200
13.3;3. Good Degree Sequences;207
13.4;4. Irregular Repeat-Accumulate Codes;215
13.5;5. Cascaded Codes;219
13.6;6. Notes;226
14;References;228
15;Index;236
16;More eBooks at www.ciando.com;0

Leseproben

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.