Error Correction Coding: Mathematical Methods and Algorithms

Cover
Title Page
Copyright
Contents
Preface
List of Program Files
List of Laboratory Exercises
List of Algorithms
List of Figures
List of Tables
List of Boxes
About the Companion Website
Part I Introduction and Foundations
Chapter 1 A Context for Error Correction Coding
	1.1 Purpose of This Book
	1.2 Introduction: Where Are Codes?
	1.3 The Communications System
	1.4 Basic Digital Communications
		1.4.1 Binary Phase‐Shift Keying
		1.4.2 More General Digital Modulation
	1.5 Signal Detection
		1.5.1 The Gaussian Channel
		1.5.2 MAP and ML Detection
		1.5.3 Special Case: Binary Detection
		1.5.4 Probability of Error for Binary Detection
		1.5.5 Bounds on Performance: The Union Bound
		1.5.6 The Binary Symmetric Channel
		1.5.7 The BSC and the Gaussian Channel Model
	1.6 Memoryless Channels
	1.7 Simulation and Energy Considerations for Coded Signals
	1.8 Some Important Definitions and a Trivial Code: Repetition Coding
		1.8.1 Detection of Repetition Codes Over a BSC
		1.8.2 Soft‐Decision Decoding of Repetition Codes Over the AWGN
		1.8.3 Simulation of Results
		1.8.4 Summary
	1.9 Hamming Codes
		1.9.1 Hard‐Input Decoding Hamming Codes
		1.9.2 Other Representations of the Hamming Code
			1.9.2.1 An Algebraic Representation
			1.9.2.2 A Polynomial Representation
			1.9.2.3 A Trellis Representation
			1.9.2.4 The Tanner Graph Representation
	1.10 The Basic Questions
	1.11 Historical Milestones of Coding Theory
	1.12 A Bit of Information Theory
		1.12.1 Information‐ Theoretic Definitions for Discrete Random Variables
			1.12.1.1 Entropy and Conditional Entropy
			1.12.1.2 Relative Entropy, Mutual Information, and Channel Capacity
		1.12.2 Data Processing Inequality
		1.12.3 Channels
			1.12.3.1 Binary Symmetric Channel
			1.12.3.2 Binary Erasure Channel
			1.12.3.3 Noisy Typewriter
			1.12.3.4 Symmetric Channels
		1.12.4 Channel Capacity
		1.12.5 Information Theoretic Definitions for Continuous Random Variables
		1.12.6 The Channel Coding Theorem
		1.12.7 “Proof” of the Channel Coding Theorem
		1.12.8 Capacity for the Continuous‐Time AWGN Channel
		1.12.9 Transmission at Capacity with Errors
		1.12.10 The Implication of the Channel Coding Theorem
		1.12.11 Non‐Asymptotic Information Theory
			1.12.11.1 Discrete Channels
			1.12.11.2 The AWGN Channel
			1.12.11.3 Comparison of Codes
	Programming Laboratory 1: Simulating a Communications Channel
		Objective
		Background
		Use of Coding in Conjunction with the BSC
		Assignment
			Preliminary Exercises
		Programming Part
			BPSK Simulation
		Resources and Implementation Suggestions
	1.13 Exercises
	1.14 References
Part II Block Codes
Chapter 2 Groups and Vector Spaces
	2.1 Introduction
	2.2 Groups
		2.2.1 Subgroups
		2.2.2 Cyclic Groups and the Order of an Element
		2.2.3 Cosets
		2.2.4 Lagrange's Theorem
		2.2.5 Induced Operations; Isomorphism
		2.2.6 Homomorphism
	2.3 Fields: A Prelude
	2.4 Review of Linear Algebra
	2.5 Exercises
	2.6 References
Chapter 3 Linear Block Codes
	3.1 Basic Definitions
	3.2 The Generator Matrix Description of Linear Block Codes
		3.2.1 Rudimentary Implementation
	3.3 The Parity Check Matrix and Dual Codes
		3.3.1 Some Simple Bounds on Block Codes
	3.4 Error Detection and Correction Over Hard‐Output Channels
		3.4.1 Error Detection
		3.4.2 Error Correction: The Standard Array
	3.5 Weight Distributions of Codes and Their Duals
	3.6 Binary Hamming Codes and Their Duals
	3.7 Performance of Linear Codes
		3.7.1 Error Detection Performance
		3.7.2 Error Correction Performance
		3.7.3 Performance for Soft‐Decision Decoding
	3.8 Erasure Decoding
		3.8.1 Binary Erasure Decoding
	3.9 Modifications to Linear Codes
	3.10 Best‐Known Linear Block Codes
	3.11 Exercises
	3.12 References
Chapter 4 Cyclic Codes, Rings, and Polynomials
	4.1 Introduction
	4.2 Basic Definitions
	4.3 Rings
		4.3.1 Rings of Polynomials
	4.4 Quotient Rings
	4.5 Ideals in Rings
	4.6 Algebraic Description of Cyclic Codes
	4.7 Nonsystematic Encoding and Parity Check
	4.8 Systematic Encoding
	4.9 Some Hardware Background
		4.9.1 Computational Building Blocks
		4.9.2 Sequences and Power Series
		4.9.3 Polynomial Multiplication
			4.9.3.1 Last‐Element‐First Processing
			4.9.3.2 First‐Element‐First Processing
		4.9.4 Polynomial Division
			4.9.4.1 Last‐Element‐First Processing
		4.9.5 Simultaneous Polynomial Division and Multiplication
			4.9.5.1 First‐Element‐First Processing
	4.10 Cyclic Encoding
	4.11 Syndrome Decoding
	4.12 Shortened Cyclic Codes
		4.12.1 Method 1: Simulating the Extra Clock Shifts
		4.12.2 Method 2: Changing the Error Pattern Detection Circuit
	4.13 Binary CRC Codes
		4.13.1 Byte‐Oriented Encoding and Decoding Algorithms
		4.13.2 CRC Protecting Data Files or Data Packets
	4.A Linear Feedback Shift Registers
		4.A.1 Basic Concepts
		Appendix 4.A.2 Connection With Polynomial Division
		Appendix 4.A.3 Some Algebraic Properties of Shift Sequences
	Programming Laboratory 2: Polynomial Division and Linear Feedback Shift Registers
		4.14.3 Objective
		4.14.3 Preliminary Exercises
		4.14.3 Programming Part: BinLFSR
		4.14.3 Resources and Implementation Suggestions
		4.14.3 Programming Part: BinPolyDiv
		4.14.3 Follow‐On Ideas and Problems
	Programming Laboratory 3: CRC Encoding and Decoding
		4.14.3 Objective
		4.14.3 Preliminary
		4.14.3 Programming Part
		4.14.3 Resources and Implementation Suggestions
	4.14 Exercise
	4.15 References
Chapter 5 Rudiments of Number Theory and Algebra
	5.1 Motivation
	5.2 Number Theoretic Preliminaries
		5.2.1 Divisibility
		5.2.2 The Euclidean Algorithm and Euclidean Domains
		5.2.3 An Application of the Euclidean Algorithm: The Sugiyama Algorithm
		5.2.4 Congruence
		5.2.5 The ϕ Function
		5.2.6 Some Cryptographic Payoff
			5.2.6.1 Fermat's Little Theorem
			5.2.6.2 RSA Encryption
	5.3 The Chinese Remainder Theorem
		5.3.1 The CRT and Interpolation
			5.3.1.1 The Evaluation Homomorphism
			5.3.1.2 The Interpolation Problem
	5.4 Fields
		5.4.1 An Examination of R and C
		5.4.2 Galois Field Construction: An Example
		5.4.3 Connection with Linear Feedback Shift Registers
	5.5 Galois Fields: Mathematical Facts
	5.6 Implementing Galois Field Arithmetic
		5.6.1 Zech Logarithms
		5.6.2 Hardware Implementations
	5.7 Subfields of Galois Fields
	5.8 Irreducible and Primitive Polynomials
	5.9 Conjugate Elements and Minimal Polynomials
		5.9.1 Minimal Polynomials
	5.10 Factoring xn−1
	5.11 Cyclotomic Cosets
	5.A How Many Irreducible Polynomials Are There?
		5.A.1 Solving for Im Explicitly: The Moebius Function
	Programming Laboratory 4: Programming the Euclidean Algorithm
		5.12.1 Objective
		5.12.1 Preliminary Exercises
		5.12.1 Background
		5.12.1 Programming Part
	Programming Laboratory 5: Programming Galois Field Arithmetic
		5.12.1 Objective
		5.12.1 Preliminary Exercises
		5.12.1 Programming Part
	5.12 Exercise
	5.13 References
Chapter 6 BCH and Reed–Solomon Codes: Designer Cyclic Codes
	6.1 BCH Codes
		6.1.1 Designing BCH Codes
		6.1.2 The BCH Bound
		6.1.3 Weight Distributions for Some Binary BCH Codes
		6.1.4 Asymptotic Results for BCH Codes
	6.2 Reed–Solomon Codes
		6.2.1 Reed–Solomon Construction 1
		6.2.2 Reed–Solomon Construction 2
		6.2.3 Encoding Reed–Solomon Codes
		6.2.4 MDS Codes and Weight Distributions for RS Codes
	6.3 Decoding BCH and RS Codes: The General Outline
		6.3.1 Computation of the Syndrome
		6.3.2 The Error Locator Polynomial
		6.3.3 Chien Search
	6.4 Finding the Error Locator Polynomial
		6.4.1 Simplifications for Narrow‐Sense Binary Codes; Peterson's Algorithm
		6.4.2 Berlekamp–Massey Algorithm
		6.4.3 Characterization of LFSR Length in Massey's Algorithm
		6.4.4 Simplifications for Binary Codes
	6.5 Nonbinary BCH and RS Decoding
		6.5.1 Forney's Algorithm
	6.6 Euclidean Algorithm for the Error Locator Polynomial
	6.7 Erasure Decoding for Nonbinary BCH or RS Codes
	6.8 Galois Field Fourier Transform Methods
		6.8.1 Equivalence of the Two Reed–Solomon Code Constructions
		6.8.2 Frequency‐Domain Decoding
	6.9 Variations and Extensions of Reed–Solomon Codes
		6.9.1 Simple Modifications
		6.9.2 Generalized Reed–Solomon Codes and Alternant Codes
		6.9.3 Goppa Codes
		6.9.4 Decoding Alternant Codes
		6.9.5 Cryptographic Connections: The McEliece Public Key Cryptosystem
	Programming Laboratory 6: Programming the Berlekamp–Massey Algorithm
		6.9.5 Background
		6.9.5 Assignment
		6.9.5 Preliminary Exercises
		6.9.5 Programming Part
		6.9.5 Resources and Implementation Suggestions
	Programming Laboratory 7: Programming the BCH Decoder
		6.9.5 Objective
		6.9.5 Preliminary Exercises
		6.9.5 Programming Part
		6.9.5 Resources and Implementation Suggestions
		6.9.5 Follow‐On Ideas and Problems
	Programming Laboratory 8: Reed–Solomon Encoding and Decoding
		6.9.5 Objective
		6.9.5 Background
		6.9.5 Programming Part
	6.A Proof of Newton's Identities
	6.11 Exercise
	6.12 References
Chapter 7 Alternate Decoding Algorithms for Reed–Solomon Codes
	7.1 Introduction: Workload for Reed–Solomon Decoding
	7.2 Derivations of Welch–Berlekamp Key Equation
		7.2.1 The Welch–Berlekamp Derivation of the WB Key Equation
			7.2.1.1 Single error in a message location
			7.2.1.2 Multiple errors in message locations
			7.2.1.3 Errors in check locations
		7.2.2 Derivation from the Conventional Key Equation
	7.3 Finding the Error Values
	7.4 Methods of Solving the WB Key Equation
		7.4.1 Background: Modules
		7.4.2 The Welch–Berlekamp Algorithm
		7.4.3 A Modular Approach to the Solution of the WB Key Equation
	7.5 Erasure Decoding with the WB Key Equation
	7.6 The Guruswami–Sudan Decoding Algorithm and Soft RS Decoding
		7.6.1 Bounded Distance, ML, and List Decoding
		7.6.2 Error Correction by Interpolation
		7.6.3 Polynomials in Two Variables
			7.6.3.1 Degree and Monomial Order
			7.6.3.2 Zeros and Multiple Zeros
		7.6.4 The GS Decoder: The Main Theorems
			7.6.4.1 The Interpolation Theorem
			7.6.4.2 The Factorization Theorem
			7.6.4.3 The Correction Distance
			7.6.4.4 The Number of Polynomials in the Decoding List
		7.6.5 Algorithms for Computing the Interpolation Step
			7.6.5.1 Finding Linearly Dependent Columns: The Feng–Tzeng Algorithm
			7.6.5.2 Finding the Intersection of Kernels: The Kötter Algorithm
		7.6.6 A Special Case: m=1 and L=1
		7.6.7 An Algorithm for the Factorization Step: The Roth–Ruckenstein Algorithm
			7.6.7.1 What to Do with Lists of Factors?
		7.6.8 Soft‐Decision Decoding of Reed–Solomon Codes
			7.6.8.1 Notation
			7.6.8.2 A Factorization Theorem
			7.6.8.3 Mapping from Reliability to Multiplicity
			7.6.8.4 The Geometry of the Decoding Regions
			7.6.8.5 Computing the Reliability Matrix
	7.7 Exercises
	7.8 References
Chapter 8 Other Important Block Codes
	8.1 Introduction
	8.2 Hadamard Matrices, Codes, and Transforms
		8.2.1 Introduction to Hadamard Matrices
		8.2.2 The Paley Construction of Hadamard Matrices
		8.2.3 Hadamard Codes
	8.3 Reed–Muller Codes
		8.3.1 Boolean Functions
		8.3.2 Definition of the Reed–Muller Codes
		8.3.3 Encoding and Decoding Algorithms for First‐Order RM Codes
			8.3.3.1 Encoding RM(1,m) Codes
			8.3.3.2 Decoding RM(1,m) Codes
			8.3.3.3 Expediting Decoding Using the Fast Hadamard Transform
		8.3.4 The Reed Decoding Algorithm for RM(r,m) Codes, r≥1
			8.3.4.1 Details for an RM(2,4) Code
			8.3.4.2 A Geometric Viewpoint
		8.3.5 Other Constructions of Reed–Muller Codes
	8.4 Building Long Codes from Short Codes: The Squaring Construction
	8.5 Quadratic Residue Codes
	8.6 Golay Codes
		8.6.1 Decoding the Golay Code
			8.6.1.1 Algebraic Decoding of the ?23 Golay Code
			8.6.1.2 Arithmetic Decoding of the ?24 Code
	8.7 Exercises
	8.8 References
Chapter 9 Bounds on Codes
	9.1 The Gilbert–Varshamov Bound
	9.2 The Plotkin Bound
	9.3 The Griesmer Bound
	9.4 The Linear Programming and Related Bounds
		9.4.1 Krawtchouk Polynomials
		9.4.2 Character
		9.4.3 Krawtchouk Polynomials and Characters
	9.5 The McEliece–Rodemich–Rumsey–Welch Bound
	9.6 Exercises
	9.7 References
Chapter 10 Bursty Channels, Interleavers, and Concatenation
	10.1 Introduction to Bursty Channels
	10.2 Interleavers
	10.3 An Application of Interleaved RS Codes: Compact Discs
	10.4 Product Codes
	10.5 Reed–Solomon Codes
	10.6 Concatenated Codes
	10.7 Fire Codes
		10.7.1 Fire Code Definition
		10.7.2 Decoding Fire Codes: Error Trapping Decoding
	10.8 Exercises
	10.9 References
Chapter 11 Soft‐Decision Decoding Algorithms
	11.1 Introduction and General Notation
	11.2 Generalized Minimum Distance Decoding
		11.2.1 Distance Measures and Properties
	11.3 The Chase Decoding Algorithms
	11.4 Halting the Search: An Optimality Condition
	11.5 Ordered Statistic Decoding
	11.6 Soft Decoding Using the Dual Code: The Hartmann Rudolph Algorithm
	11.7 Exercises
	11.8 References
Part III Codes on Graphs
Chapter 12 Convolutional Codes
	12.1 Introduction and Basic Notation
		12.1.1 The State
	12.2 Definition of Codes and Equivalent Codes
		12.2.1 Catastrophic Encoders
		12.2.2 Polynomial and Rational Encoders
		12.2.3 Constraint Length and Minimal Encoders
		12.2.4 Systematic Encoders
	12.3 Decoding Convolutional Codes
		12.3.1 Introduction and Notation
		12.3.2 The Viterbi Algorithm
		12.3.3 Some Implementation Issues
			12.3.3.1 The Basic Operation: Add‐Compare‐Select
			12.3.3.2 Decoding Streams of Data: Windows on the Trellis
			12.3.3.3 Output Decisions
			12.3.3.4 Hard and Soft Decoding; Quantization
			12.3.3.5 Synchronization Issues
	12.4 Some Performance Results
	12.5 Error Analysis for Convolutional Codes
		12.5.1 Enumerating Paths Through the Trellis
			12.5.1.1 Enumerating on More Complicated Graphs: Mason's Rule
		12.5.2 Characterizing Node Error Probability Pe and Bit Error Rate Pb
		12.5.3 A Bound on Pd for Discrete Channels
			12.5.3.1 Performance Bound on the BSC
		12.5.4 A Bound on Pd for BPSK Signaling Over the AWGN Channel
		12.5.5 Asymptotic Coding Gain
	12.6 Tables of Good Codes
	12.7 Puncturing
		12.7.1 Puncturing to Achieve Variable Rate
	12.8 Suboptimal Decoding Algorithms for Convolutional Codes
		12.8.1 Tree Representations
		12.8.2 The Fano Metric
		12.8.3 The Stack Algorithm
		12.8.4 The Fano Algorithm
		12.8.5 Other Issues for Sequential Decoding
			12.8.5.1 Computational complexity
			12.8.5.2 Code design
			12.8.5.3 Variations on sequential decoding algorithms
		12.8.6 A Variation on the Viterbi Algorithm: The M Algorithm
	12.9 Convolutional Codes as Block Codes and Tailbiting Codes
	12.10 A Modified Expression for the Path Metric
	12.11 Soft Output Viterbi Algorithm (SOVA)
	12.12 Trellis Representations of Block and Cyclic Codes
		12.12.1 Block Codes
		12.12.2 Cyclic Codes
		12.12.3 Trellis Decoding of Block Codes
	Programming Laboratory 9: Programming Convolutional Encoders
		12.12.3 Objective
		12.12.3 Background
		12.12.3 Programming Part
	Programming Laboratory 10: Convolutional Decoders: The Viterbi Algorithm
		12.12.3 Objective
		12.12.3 Background
		12.12.3 Programming Part
	12.13 Exercises
	12.14 References
Chapter 13 Trellis‐Coded Modulation
	13.1 Adding Redundancy by Adding Signals
	13.2 Background on Signal Constellations
	13.3 TCM Example
		13.3.1 The General Ungerboeck Coding Framework
		13.3.2 The Set Partitioning Idea
	13.4 Some Error Analysis for TCM Codes
		13.4.1 General Considerations
		13.4.2 A Description of the Error Events
		13.4.3 Known Good TCM Codes
	13.5 Decoding TCM Codes
	13.6 Rotational Invariance
		13.6.1 Differential Encoding
		13.6.2 Constellation Labels and Partitions
	13.7 Multidimensional TCM
		13.7.1 Some Advantages of Multidimensional TCM
			13.7.1.1 Energy expansion advantage
			13.7.1.2 Sphere‐packing advantages
			13.7.1.3 Spectral efficiency
			13.7.1.4 Rotational invariance
			13.7.1.5 Signal shape
			13.7.1.6 Peak‐to‐average power ratio
			13.7.1.7 Decoding speed
		13.7.2 Lattices and Sublattices
			13.7.2.1 Basic Definitions
			13.7.2.2 Common Lattices
			13.7.2.3 Sublattices and Cosets
			13.7.2.4 The Lattice Code Idea
			13.7.2.5 Sources of Coding Gain in Lattice Codes
			13.7.2.6 Some Good Lattice Codes
	13.8 Multidimensional TCM Example: The V.34 Modem Standard
	13.9 Exercises
	Programming Laboratory 11: Trellis‐Coded Modulation Encoding and Decoding
	13.10 References
Part IV Iteratively Decoded Codes
Chapter 14 Turbo Codes
	14.1 Introduction
	14.2 Encoding Parallel Concatenated Codes
	14.3 Turbo Decoding Algorithms
		14.3.1 The MAP Decoding Algorithm
		14.3.2 Notation
		14.3.3 Posterior Probability
		14.3.4 Computing αt and βt
		14.3.5 Computing γt
		14.3.6 Normalization
		14.3.7 Summary of the BCJR Algorithm
		14.3.8 A Matrix/Vector Formulation
		14.3.9 Comparison of the Viterbi Algorithm and the BCJR Algorithm
		14.3.10 The BCJR Algorithm for Systematic Codes
		14.3.11 Turbo Decoding Using the BCJR Algorithm
			14.3.11.1 The Terminal State of the Encoders
		14.3.12 Likelihood Ratio Decoding
			14.3.12.1 Log Prior Ratio λp,t
			14.3.12.2 Log Posterior λs,t(0)
		14.3.13 Statement of the Turbo Decoding Algorithm
		14.3.14 Turbo Decoding Stopping Criteria
			14.3.14.1 The Cross Entropy Stopping Criterion
			14.3.14.2 The Sign Change Ratio (SCR) Criterion
			14.3.14.3 The Hard Decision Aided (HDA) Criterion
		14.3.15 Modifications of the MAP Algorithm
			14.3.15.1 The Max‐Log‐MAP Algorithm
		14.3.16 Corrections to the Max‐Log‐MAP Algorithm
		14.3.17 The Soft‐Output Viterbi Algorithm
	14.4 On the Error Floor and Weight Distributions
		14.4.1 The Error Floor
		14.4.2 Spectral Thinning and Random Permuters
		14.4.3 On Permuters
	14.5 EXIT Chart Analysis
		14.5.1 The EXIT Chart
	14.6 Block Turbo Coding
	14.7 Turbo Equalization
		14.7.1 Introduction to Turbo Equalization
		14.7.2 The Framework for Turbo Equalization
	Programming Laboratory 12: Turbo Code Decoding
		14.7.2 Objective
		14.7.2 Background
		14.7.2 Programming Part
	14.8 Exercise
	14.9 References
Chapter 15 Low‐Density Parity‐Check Codes: Introduction, Decoding, and Analysis
	15.1 Introduction
	15.2 LDPC Codes: Construction and Notation
	15.3 Tanner Graphs
	15.4 Decoding LDPC Codes
		15.4.1 Decoding Using Log‐Likelihood Ratios
			15.4.1.1 Log‐Likelihood Ratios
			15.4.1.2 Log‐Likelihood Ratio of the Sum of Bits
			15.4.1.3 Decoding: Message from a Check Node to a Variable Node
			15.4.1.4 Log Likelihood of Repeated Observations About a Bit
			15.4.1.5 Decoding: Message from a Variable Node to a Check Node
			15.4.1.6 Inputs to the LDPC Decoding Algorithm
			15.4.1.7 Terminating the Decoding Algorithm
			15.4.1.8 Summary of Decoding: The Belief Propagation Algorithm
			15.4.1.9 Messages on the Tanner Graph
		15.4.2 Decoding Using Probabilities
			15.4.2.1 Probability of Even Parity: Decoding at the Check Nodes
			15.4.2.2 Probability of Independent Observations Decoding at a Variable Node
			15.4.2.3 Computing the Leave‐One‐Out Product
			15.4.2.4 Sparse Memory Organization
		15.4.3 Variations on Decoding Algorithms: The Min‐Sum Decoder
			15.4.3.1 The ⊞ Operation and the ϕ(x) Function
			15.4.3.2 Attenuated and Offset Min‐Sum Decoders
		15.4.4 Variations on Decoding Algorithms: Min‐Sum with Correction
			15.4.4.1 Approximate min* Decoder
			15.4.4.2 The Reduced Complexity Box‐Plus Decoder
			15.4.4.3 The Richardson–Novichkov Decoder
		15.4.5 Hard‐Decision Decoding
			15.4.5.1 Bit Flipping
			15.4.5.2 Gallager's Algorithms A and B
			15.4.5.3 Weighted Bit Flipping
			15.4.5.4 Gradient Descent Bit Flipping
		15.4.6 Divide and Concur Decoding
			15.4.6.1 Summary of the Divide and Concur Algorithm
			15.4.6.2 DC Applied to LDPC Decoding
			15.4.6.3 The Divide Projections
			15.4.6.4 The Concur Projection
			15.4.6.5 A Message‐Passing Viewpoint of DC Decoding
		15.4.7 Difference Map Belief Propagation Decoding
		15.4.8 Linear Programming Decoding
			15.4.8.1 Background on Linear Programming
			15.4.8.2 Formulation of the Basic LP Decoding Algorithm
			15.4.8.3 LP Relaxation
			15.4.8.4 Examples and Discussion
		15.4.9 Decoding on the Binary Erasure Channel
		15.4.10 BEC Channels and Stopping Sets
	15.5 Why Low‐Density Parity‐Check Codes?
	15.6 The Iterative Decoder on General Block Codes
	15.7 Density Evolution
	15.8 EXIT Charts for LDPC Codes
	15.9 Irregular LDPC Codes
		15.9.1 Degree Distribution Pairs
		15.9.2 Density Evolution for Irregular Codes
		15.9.3 Computation and Optimization of Density Evolution
		15.9.4 Using Irregular Codes
	15.10 More on LDPC Code Construction
	15.11 Encoding LDPC Codes
	15.12 A Variation: Low‐Density Generator Matrix Codes
	Programming Laboratory 13: Programming an LDPC Decoder
	15.13 Exercise
	15.14 References
Chapter 16 Low‐Density Parity‐Check Codes: Designs and Variations
	16.1 Introduction
	16.2 Repeat‐Accumulate Codes
		16.2.1 Decoding RA Codes
		16.2.2 Irregular RA Codes
		16.2.3 RA Codes with Multiple Accumulators
	16.3 LDPC Convolutional Codes
	16.4 Quasi‐Cyclic Codes
		16.4.1 QC Generator Matrices
		16.4.2 Constructing QC Generator Matrices from QC Parity Check Matrices
			16.4.2.1 Full Rank Case
			16.4.2.2 Non‐Full Rank Case
	16.5 Construction of LDPC Codes Based on Finite Fields
		16.5.1 I. Construction of QC‐LDPC Codes Based on the Minimum‐Weight Codewords of a Reed–Solomon Code with Two Information Symbols
		16.5.2 II. Construction of QC‐LDPC Codes Based on a Special Subclass of RS Codes
		16.5.3 III. Construction of QC‐LDPC Codes Based on Subgroups of a Finite Field
		16.5.4 IV. Construction of QC‐LDPC Codes Based on Subgroups of the Multiplicative Group of a Finite Field
		16.5.5 Construction of QC‐LDPC Codes Based on Primitive Elements of a Field
	16.6 Code Design Based on Finite Geometries
		16.6.1 Rudiments of Euclidean Geometry
			16.6.1.1 Points in EG(m,q)
			16.6.1.2 Lines in EG(m,q)
			16.6.1.3 Incidence vectors in EG*(m,q)
		16.6.2 A Family of Cyclic EG‐LDPC Codes
		16.6.3 Construction of LDPC Codes Based on Parallel Bundles of Lines
		16.6.4 Constructions Based on Other Combinatoric Objects
	16.7 Ensembles of LDPC Codes
		16.7.1 Regular ensembles
		16.7.2 Irregular Ensembles
		16.7.3 Multi‐edge‐type Ensembles
	16.8 Constructing LDPC Codes by Progressive Edge Growth (PEG)
	16.9 Protograph and Multi‐Edge‐Type LDPC Codes
	16.10 Error Floors and Trapping Sets
	16.11 Importance Sampling
		16.11.1 Importance Sampling: General Principles
		16.11.2 Importance Sampling for Estimating Error Probability
		16.11.2 Conventional Sampling (MC)
		16.11.2 Importance Sampling (IS)
		16.11.3 Importance Sampling for Tanner Trees
			16.11.3.1 Single Parity‐Check Codes
			16.11.3.2 Symmetric Tanner Trees
			16.11.3.3 General Trees
			16.11.3.4 Importance Sampling for LDPC Codes
	16.12 Fountain Codes
		16.12.1 Conventional Erasure Correction Codes
		16.12.2 Tornado Codes
		16.12.3 Luby Transform Codes
		16.12.4 Raptor Codes
	16.13 References
Part V Polar Codes
Chapter 17 Polar Codes
	17.1 Introduction and Preview
	17.2 Notation and Channels
	17.3 Channel Polarization, N=2 Channel
		17.3.1 Encoding
		17.3.2 Synthetic Channels and Mutual Information
		17.3.3 Synthetic Channel Transition Probabilities
		17.3.4 An Example with N=2 Using the Binary Erasure Channel
		17.3.5 Successive Cancellation Decoding
			17.3.5.1 Log‐Likelihood Ratio Computations
			17.3.5.2 Computing the Log‐Likelihood Function with Lower Complexity
		17.3.6 Tree Representation
		17.3.7 The Polar Coding Idea
	17.4 Channel Polarization, N>2 Channels
		17.4.1 Channel Combining: Extension from N/2 to N channels.
		17.4.2 Pseudocode for Encoder for Arbitrary N
		17.4.3 Transition Probabilities and Channel Splitting
		17.4.4 Channel Polarization Demonstrated: An Example Using the Binary Erasure Channel for N>2
		17.4.5 Polar Coding
		17.4.6 Tree Representation
		17.4.7 Successive Cancellation Decoding
		17.4.8 SC Decoding from a Message Passing Point of View on the Tree
		17.4.9 A Decoding Example with N=4
		17.4.10 A Decoding Example with N=8
		17.4.11 Pseudo‐Code Description of Successive Cancellation Algorithm
	17.5 Some Theorems of Polar Coding Theory
		17.5.1 I(W) and Z(W) for general B‐DMCs
		17.5.2 Channel Polarization
		17.5.3 The Polarization Theorem
		17.5.4 A Few Facts About Martingales
		17.5.5 Proof of the Polarization Theorem
		17.5.6 Another Polarization Theorem
		17.5.7 Rate of Polarization
		17.5.8 Probability of Error Performance
	17.6 Designing Polar Codes
		17.6.1 Code Design by Battacharyya Bound
		17.6.2 Monte Carlo Estimation of Z(WN(i))
	17.7 Perspective: The Channel Coding Theorem
	17.8 Systematic Encoding of Polar Codes
		17.8.1 Polar Systematic Encoding via the Encoder Graph
		17.8.2 Polar Systematic Encoding via Arıkan's Method
		17.8.3 Systematic Encoding: The Bit Reverse Permutation
		17.8.4 Decoding Systematically Encoded Codes
		17.8.5 Flexible Systematic Encoding
		17.8.6 Involutions and Domination Contiguity
		17.8.7 Polar Codes and Domination Contiguity
		17.8.8 Modifications for Polar Codes with Bit‐Reverse Permutation
	17.9 List Decoding of Polar Codes
		17.9.1 The Likelihood Data Structure P
		17.9.2 Normalization
		17.9.3 Code to Compute P
		17.9.4 The Bits Data Structure C
		17.9.5 Code to Compute C
		17.9.6 Supporting Data Structures
		17.9.7 Code for Polar List Decoding
		17.9.8 An Example of List Decoding
		17.9.9 Computational Complexity
		17.9.10 Modified Polar Codes
	17.10 LLR‐Based Successive Cancellation List Decoding
		17.10.1 Implementation Considerations
	17.11 Simplified Successive Cancellation Decoding
		17.11.1 Modified SC Decoding
	17.12 Relations with Reed–Muller Codes
	17.13 Hardware and Throughput Performance Results
	17.14 Generalizations, Extensions, and Variations
	17.A BN is a Bit‐Reverse Permutation
	17.B The Relationship of the Battacharyya Parameter to Channel Capacity
		17.B.1 Error Probability for Two Codewords
		17.B.2 Proof of Inequality (17.59)
		17.B.3 Proof of Inequality (17.60) [16]
	17.C Proof of Theorem 17.12
	17.15 Exercises
	17.16 References
Part VI Applications
Chapter 18 Some Applications of Error Correction in Modern Communication Systems
	18.1 Introduction
	18.2 Digital Video Broadcast T2 (DVB‐T2)
		18.2.1 BCH Outer Encoding
		18.2.2 LDPC Inner Encoding
	18.3 Digital Cable Television
	18.4 E‐UTRA and Long‐Term Evolution
		18.4.1 LTE Rate 1/3 Convolutional Encoder
		18.4.2 LTE Turbo Code
	18.5 References
Part VII Space-Time Coding
Chapter 19 Fading Channels and Space‐Time Codes
	19.1 Introduction
	19.2 Fading Channels
		19.2.1 Rayleigh Fading
	19.3 Diversity Transmission and Reception: The MIMO Channel
		19.3.1 The Narrowband MIMO Channel
		19.3.2 Diversity Performance with Maximal‐Ratio Combining
	19.4 Space‐Time Block Codes
		19.4.1 The Alamouti Code
		19.4.2 A More General Formulation
		19.4.3 Performance Calculation
			19.4.3.1 Real Orthogonal Designs
			19.4.3.2 Encoding and Decoding Based on Orthogonal Designs
			19.4.3.3 Generalized Real Orthogonal Designs
		19.4.4 Complex Orthogonal Designs
			19.4.4.1 Future Work
	19.5 Space‐Time Trellis Codes
		19.5.1 Concatenation
	19.6 How Many Antennas?
	19.7 Estimating Channel Information
	19.8 Exercises
	19.9 References
References
Index
EULA