Fundamentals of Codes, Graphs, and Iterative Decoding (eBook)

Contents 6
List of Figures 9
List of Tables 11
Preface 13
Chapter 1 DIGITAL COMMUNICATION 20
1. Basics 20
2. Algorithms and Complexity 24
3. Encoding and Decoding 25
4. Bounds 27
5. Overview of the Text 31
Chapter 2 ABSTRACT ALGEBRA 32
1. Sets and Groups 32
2. Rings, Domains, and Fields 35
3. Vector Spaces and GF 42
4. Polynomials over Galois Fields 47
5. Frequency Domain Analysis of Polynomials over GF(q) 53
6. Ideals in the Ring 56
Chapter 3 LINEAR BLOCK CODES 58
1. Basic Structure of Linear Codes 59
2. Repetition and Parity Check Codes 62
3. Hamming Codes 63
4. Reed-Muller Codes 64
5. Cyclic Codes 68
6. Quadratic Residue Codes 69
7. Golay Codes 70
8. BCH and Reed-Solomon Codes 72
9. Product Codes 77
Chapter 4 CONVOLUTIONAL AND CONCATENATED CODES 80
1. Convolutional Encoders 81
2. Analysis of Component Codes 84
3. Concatenated Codes 87
4. Analysis of Parallel Concatenated Codes 90
Chapter 5 ELEMENTS OF GRAPH THEORY 98
1. Introduction 99
2. Martingales 102
3. Expansion 105
Chapter 6 ALGORITHMS ON GRAPHS 112
1. Probability Models and Bayesian Networks 113
2. Belief Propagation Algorithm 118
3. Junction Tree Propagation Algorithm 123
4. Message Passing and Error Control Decoding 128
5. Message Passing in Loops 134
Chapter 7 TURBO DECODING 140
1. Turbo Decoding 140
2. Parallel Decoding 145
3. Notes 151
Chapter 8 LOW-DENSITY PARITY-CHECK CODES 156
1. Basic Properties 156
2. Simple Decoding Algorithms 162
3. Explicit Construction 166
4. Gallager’s Decoding Algorithms 170
5. Belief Propagation Decoding 181
6. Notes 191
Chapter 9 LOW-DENSITY GENERATOR CODES 196
1. Introduction 196
2. Decoding Analyses 200
3. Good Degree Sequences 207
4. Irregular Repeat-Accumulate Codes 215
5. Cascaded Codes 219
6. Notes 226
References 228
Index 236
More eBooks at www.ciando.com 0

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.