Fundamentals of Codes, Graphs, and Iterative Decoding

by Wicker, Stephen B.; Kim, Saejoon

• ISBN13: 9781402072642
• ISBN10: 1402072643
• Format: Hardcover
• Copyright: 2002-10-01
• Publisher: Kluwer Academic Pub

Summary

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.

Table of Contents

List of Figures	ix
List of Tables	xi
Preface	xiii
Digital Communication	1	(12)
Basics	1	(4)
Algorithms and Complexity	5	(1)
Encoding and Decoding	6	(2)
Bounds	8	(4)
Overview of the Text	12	(1)
Abstract Algebra	13	(26)
Sets and Groups	13	(3)
Rings, Domains, and Fields	16	(7)
Vector Spaces and GF(pm)	23	(5)
Polynomials over Galois Fields	28	(6)
Frequency Domain Analysis of Polynomials over GF(q)	34	(3)
Ideals in the Ring GF(q)[x]/(xn--1)	37	(2)
Linear Block Codes	39	(22)
Basic Structure of Linear Codes	40	(3)
Repetition and Parity Check Codes	43	(1)
Hamming Codes	44	(1)
Reed-Muller Codes	45	(4)
Cyclic Codes	49	(1)
Quadratic Residue Codes	50	(1)
Golay Codes	51	(2)
BCH and Reed-Solomon Codes	53	(5)
Product Codes	58	(3)
Convolutional and Concatenated Codes	61	(18)
Convolutional Encoders	62	(3)
Analysis of Component Codes	65	(3)
Concatenated Codes	68	(3)
Analysis of Parallel Concatenated Codes	71	(8)
Elements of Graph Theory	79	(14)
Introduction	80	(3)
Martingales	83	(3)
Expansion	86	(7)
Algorithms on Graphs	93	(28)
Probability Models and Bayesian Networks	94	(5)
Belief Propagation Algorithm	99	(5)
Junction Tree Propagation Algorithm	104	(5)
Message Passing and Error Control Decoding	109	(6)
Message Passing in Loops	115	(6)
Turbo Decoding	121	(16)
Turbo Decoding	121	(5)
Parallel Decoding	126	(6)
Notes	132	(5)
Low-Density Parity-Check Codes	137	(40)
Basic Properties	137	(6)
Simple Decoding Algorithms	143	(4)
Explicit Construction	147	(4)
Gallager's Decoding Algorithms	151	(11)
Belief Propagation Decoding	162	(10)
Notes	172	(5)
Low-Density Generator Codes	177	(32)
Introduction	177	(4)
Decoding Analyses	181	(7)
Good Degree Sequences	188	(8)
Irregular Repeat-Accumulate Codes	196	(4)
Cascaded Codes	200	(7)
Notes	207	(2)
References	209	(8)
Index	217