第1页 / 共710页
第2页 / 共710页
第3页 / 共710页
第4页 / 共710页
第5页 / 共710页
第6页 / 共710页
第7页 / 共710页
第8页 / 共710页
Channel Codes.pdf
Half-Title
Title
Copyright
Contents
Preface
1 Coding and Capacity
1.1 Digital Data Communication and Storage
1.2 Channel-Coding Overview
1.3 Channel-Code Archetype: The (7,4) Hamming Code
1.4 Design Criteria and Performance Measures
1.5 Channel-Capacity Formulas for Common Channel Models
1.5.1 Capacity for Binary-Input Memoryless Channels
1.5.1.1 The BEC and the BSC
1.5.1.2 The Z Channel
1.5.1.3 The Binary-Input AWGN Channel
1.5.2 Coding Limits for M-ary-Input Memoryless Channels
1.5.2.1 The Unconstrained-Input AWGN Channel
1.5.2.2 M-ary AWGN Channel
1.5.2.3 M-ary Symmetric Channel
1.5.3 Coding Limits for Channels with Memory
1.5.3.1 Gilbert-Elliott Channels
1.5.3.2 Computing Achievable Rates for ISI Channels
Problems
References
2 Finite Fields, Vector Spaces, Finite Geometries, and Graphs
2.1 Sets and Binary Operations
2.2 Groups
2.2.1 Basic Concepts of Groups
2.2.2 Finite Groups
2.2.3 Subgroups and Cosets
2.3 Fields
2.3.1 Definitions and Basic Concepts
2.3.2 Finite Fields
2.4 Vector Spaces
2.4.1 Basic Definitions and Properties
2.4.2 Linear Independence and Dimension
2.4.3 Finite Vector Spaces over Finite Fields
2.4.4 Inner Products and Dual Spaces
2.5 Polynomials over Finite Fields
2.6 Construction and Properties of Galois Fields
2.6.1 Construction of Galois Fields
2.6.2 Some Fundamental Properties of Finite Fields
2.6.3 Additive and Cyclic Subgroups
2.7 Finite Geometries
2.7.1 Euclidean Geometries
2.7.2 Projective Geometries
2.8 Graphs
2.8.1 Basic concepts
2.8.2 Paths and Cycles
2.8.3 Bipartite Graphs
Problems
References
Appendix A Table of Primitive Polynomials
3 Linear Block Codes
3.1 Introduction to Linear Block Codes
3.1.1 Generator and Parity-Check Matrices
3.1.2 Error Detection with Linear Block Codes
3.1.3 Weight Distribution and Minimum Hamming Distance of A Linear Block Code
3.1.4 Decoding of Linear Block Codes
3.2 Cyclic Codes
3.3 BCH Codes
3.3.1 Code Construction
3.3.2 Decoding
3.4 Nonbinary Linear Block Codes and Reed-Solomon Codes
3.5 Product, Interleaved, and Concatenated Codes
3.5.1 Product Codes
3.5.2 Interleaved Codes
3.5.3 Concatenated Codes
3.6 Quasi-Cyclic Codes
3.7 Repetition and Single-Parity-Check Codes
Problems
References
4 Convolutional Codes
4.1 The Convolutional Code Archetype
4.2 Algebraic Description of Convolutional Codes
4.3 Encoder Realizations and Classifications
4.3.1 Choice of Encoder Class
4.3.2 Catastrophic Encoders
4.3.3 Minimal Encoders
4.3.4 Design of Convolutional Codes
4.4 Alternative Convolutional Code Representations
4.4.1 Convolutional Codes as Semi-Infinite Linear Codes
4.4.2 Graphical Representations for Convolutional Code Encoders
4.5 Trellis-Based Decoders
4.5.1 MLSD and the Viterbi Algorithm
4.5.2 Difierential Viterbi Decoding
4.5.3 Bit-wise MAP Decoding and the BCJR Algorithm
4.6 Performance Estimates for Trellis-Based Decoders
4.6.1 ML Decoder Performance for Block Codes
4.6.2 Weight Enumerators for Convolutional Codes
4.6.3 ML Decoder Performance for Convolutional Codes
Problems
References
5 Low-Density Parity-Check Codes
5.1 Representations of LDPC Codes
5.1.1 Matrix Representation
5.1.2 Graphical Representation
5.2 Classifications of LDPC Codes
5.2.1 Generalized LDPC Codes
5.3 Message Passing and the Turbo Principle
5.4 The Sum-Product Algorithm
5.4.1 Overview
5.4.2 Repetition Code MAP Decoder and APP Processor
5.4.3 Single-Parity-Check Code MAP Decoder and APP Processor
5.4.4 The Gallager SPA Decoder
5.4.5 The Box-Plus SPA Decoder
5.4.6 Comments on the Performance of the SPA Decoder
5.5 Reduced-Complexity SPA Approximations
5.5.1 The Min-Sum Decoder
5.5.2 The Attenuated and Offset Min-Sum Decoders
5.5.3 The Min-Sum-with-Correction Decoder
5.5.4 The Approximate min Decoder
5.5.5 The Richardson/Novichkov Decoder
5.5.6 The Reduced-Complexity Box-Plus Decoder
5.6 Iterative Decoders for Generalized LDPC Codes
5.7 Decoding Algorithms for the BEC and the BSC
5.7.1 Iterative Erasure Filling for the BEC
5.7.2 ML Decoder for the BEC
5.7.3 Gallager's Algorithm A and Algorithm B for the BSC
5.7.4 The Bit-Flipping Algorithm for the BSC
5.8 Concluding Remarks
Problems
References
6 Computer-Based Design of
6.1 The Original LDPC Codes
6.1.1 Gallager Codes
6.1.2 MacKay Codes
6.2 The PEG and ACE Code-Design Algorithms
6.2.1 The PEG Algorithm
6.2.2 The ACE Algorithm
6.3 Protograph LDPC Codes
6.3.1 Decoding Architectures for Protograph Codes
6.4 Multi-Edge-Type LDPC Codes
6.5 Single-Accumulator-Based LDPC Codes
6.5.1 Repeat-Accumulate Codes
6.5.2 Irregular Repeat-Accumulate Codes
6.5.2.1 Quasi-Cyclic IRA Code Design
6.5.3 Generalized Accumulator LDPC Codes
6.6 Double-Accumulator-Based LDPC Codes
6.6.1 Irregular Repeat-Accumulate-Accumulate Codes
6.6.2 Accumulate-Repeat-Accumulate Codes
6.6.2.1 Protograph-Based ARA Code Design
6.7 Accumulator-Based Codes in Standards
6.8 Generalized LDPC Codes
6.8.1 Rate-1/2 G-LDPCA Code
Problems
References
7 Turbo Codes
7.1 Parallel-Concatenated Convolutional Codes
7.1.1 Critical Properties of RSC Codes
7.1.2 Critical Properties of the Interleaver
7.1.3 The Puncturer
7.1.4 Performance Estimate on the BI-AWGNC
7.2 The PCCC Iterative Decoder
7.2.1 Overview of the Iterative Decoder
7.2.2 Decoder Details
7.2.3 Summary of the PCCC Iterative Decoder
7.2.4 Lower-Complexity Approximations
7.3 Serial-Concatenated Convolutional Codes
7.3.1 Performance Estimate on the BI-AWGNC
7.3.2 The SCCC Iterative Decoder
7.3.3 Summary of the SCCC Iterative Decoder
7.4 Turbo Product Codes
7.4.1 Turbo Decoding of Product Codes
7.4.1.1 Obtaining the List of Candidate Codewords
7.4.1.2 The Codeword Decision
7.4.1.3 Computing Soft Outputs and Extrinsic Information
7.4.1.4 The Turbo Decoder
Problems
References
8 Ensemble Enumerators for Turbo and LDPC Codes
8.1 Notation
8.2 Ensemble Enumerators for Parallel-Concatenated Codes
8.2.1 Preliminaries
8.2.2 PCCC Ensemble Enumerators
8.2.2.1 PCCCs with Non-Recursive Constituent Encoders
8.2.2.2 PCCCs with Recursive Constituent Encoders
8.2.2.3 PCCC Design Principles
8.2.2.4 Example Performance Bounds
8.3 Ensemble Enumerators for Serial-Concatenated Codes
8.3.1 Preliminaries
8.3.2 SCCC Ensemble Enumerators
8.3.2.1 High-SNR Region: The Exponent kappaomega for omega = omegamin
8.3.2.2 Low-SNR Region: The Maximum Exponent of K2
8.4 Enumerators for Selected Accumulator-Based Codes
8.4.1 Enumerators for Repeat-Accumulate Codes
8.4.2 Enumerators for Irregular Repeat-Accumulate Codes
8.5 Enumerators for Protograph-Based LDPC Codes
8.5.1 Finite-Length Ensemble Weight Enumerators
8.5.2 Asymptotic Ensemble Weight Enumerators
8.5.3 On the Complexity of Computing Asymptotic Ensemble Enumerators
8.5.4 Ensemble Trapping-Set Enumerators
8.5.4.1 Finite-size Trapping-Set Enumerators
8.5.4.2 Elementary Trapping-Set Enumerators
8.5.4.3 Asymptotic Trapping-Set Enumerators
8.5.5 Ensemble Stopping-Set Enumerators
Problems
References
9 Ensemble Decoding Thresholds for LDPC and Turbo Codes
9.1 Density Evolution for Regular LDPC Codes
9.2 Density Evolution for Irregular LDPC Codes
9.3 Quantized Density Evolution
9.4 The Gaussian Approximation
9.4.1 GA for Regular LDPC Codes
9.4.2 GA for Irregular LDPC Codes
9.5 On the Universality of LDPC Codes
9.6 EXIT Charts for LDPC Codes
9.6.1 EXIT Charts for Regular LDPC Codes
9.6.2 EXIT Charts for Irregular LDPC Codes
9.6.3 EXIT Technique for Protograph-Based Codes
9.7 EXIT Charts for Turbo Codes
9.8 The Area Property for EXIT Charts
9.8.1 Serial-Concatenated Codes
9.8.2 LDPC Codes
Problems
References
10 Finite-Geometry LDPC Codes
10.1 Construction of LDPC Codes Based on Lines of Euclidean Geometries
10.1.1 A Class of Cyclic EG-LDPC Codes
10.1.2 A Class of Quasi-Cyclic EG-LDPC Codes
10.2 Construction of LDPC Codes Based on the Parallel Bundles of Lines in Euclidean Geometries
10.3 Construction of LDPC Codes Based on Decomposition of Euclidean Geometries
10.4 Construction of EG-LDPC Codes by Masking
10.4.1 Masking
10.4.2 Regular Masking
10.4.3 Irregular Masking
10.5 Construction of QC-EG-LDPC Codes by Circulant Decomposition
10.6 Construction of Cyclic and QC-LDPC Codes Based on Projective Geometries
10.6.1 Cyclic PG-LDPC Codes
10.6.2 Quasi-Cyclic PG-LDPC Codes
10.7 One-Step Majority-Logic and Bit-Flipping Decoding Algorithms for FG-LDPC Codes
10.7.1 The OSMLG Decoding Algorithm for LDPC Codes over the BSC
10.7.2 The BF Algorithm for Decoding LDPC Codes over the BSC
10.8 Weighted BF Decoding: Algorithm 1
10.9 Weighted BF Decoding: Algorithms 2 and 3
10.10 Concluding Remarks
Problems
References
11 Constructions of LDPC Codes Based on Finite Fields
11.1 Matrix Dispersions of Elements of a Finite Field
11.2 A General Construction of QC-LDPC Codes Based on Finite Fields
11.3 Construction of QC-LDPC Codes Based on the Minimum-Weight Codewords of an RS Code with Two Information Symbols
11.4 Construction of QC-LDPC Codes Based on the Universal Parity-Check Matrices of a Special Subclass of RS Codes
11.5 Construction of QC-LDPC Codes Based on Subgroups of a Finite Field
11.5.1 Construction of QC-LDPC Codes Based on Subgroups of the Additive Group of a Finite Field
11.5.2 Construction of QC-LDPC Codes Based on Subgroups of the Multiplicative Group of a Finite Field
11.6 Construction of QC-LDPC Code Based on the Additive Group of a Prime Field
11.7 Construction of QC-LDPC Codes Based on Primitive Elements of a Field
11.8 Construction of QC-LDPC Codes Based on the Intersecting Bundles of Lines of Euclidean Geometries
11.9 A Class of Structured RS-Based LDPC Codes
Problems
References
12 LDPC Codes Based on Combinatorial Designs, Graphs, and Superposition
12.1 Balanced Incomplete Block Designs and LDPC Codes
12.2 Class-I Bose BIBDs and QC-LDPC Codes
12.2.1 Class-I Bose BIBDs
12.2.2 Type-I Class-I Bose BIBD-LDPC Codes
12.2.3 Type-II Class-I Bose BIBD-LDPC Codes
12.3 Class-II Bose BIBDs and QC-LDPC Codes
12.3.1 Class-II Bose BIBDs
12.3.2 Type-I Class-II Bose BIBD-LDPC Codes
12.3.3 Type-IIClass-IIQC-BIBD-LDPC Codes
12.4 Construction of Type-II Bose BIBD-LDPC Codes by Dispersion
12.5 A Trellis-Based Construction of LDPC Codes
12.5.1 A Trellis-Based Method for Removing Short Cycles from a Bipartite Graph
12.5.2 Code Construction
12.6 Construction of LDPC Codes Based on Progressive Edge-Growth Tanner Graphs
12.7 Construction of LDPC Codes by Superposition
12.7.1 A General Superposition Construction of LDPC Codes
12.7.2 Construction of Base and Constituent Matrices
12.7.3 Superposition Construction of Product LDPC Codes
12.8 Two Classes of LDPC Codes with Girth 8
Problems
References
13 LDPC Codes for Binary Erasure Channels
13.1 Iterative Decoding of LDPC Codes for the BEC
13.2 Random-Erasure-Correction Capability
13.3 Good LDPC Codes for the BEC
13.4 Correction of Erasure-Bursts
13.5 Erasure-Burst-Correction Capabilities of Cyclic Finite-Geometry and Superposition LDPC Codes
13.5.1 Erasure-Burst-Correction with Cyclic Finite-Geometry LDPC Codes
13.5.2 Erasure-Burst-Correction with Superposition LDPC Codes
13.6 Asymptotically Optimal Erasure-Burst-Correction QC-LDPC Codes
13.7 Construction of QC-LDPC Codes by Array Dispersion
13.8 Cyclic Codes for Correcting Bursts of Erasures
Problems
References
14 Nonbinary LDPC Codes
14.1 Definitions
14.2 Decoding of Nonbinary LDPC Codes
14.2.1 The QSPA (Davey and MacKay [1])
14.2.2 The FFT-QSPA
14.3 Construction of Nonbinary LDPC Codes Based on Finite Geometries
14.3.1 A Class of qm-ary Cyclic EG-LDPC Codes
14.3.2 A Class of Nonbinary Quasi-Cyclic EG-LDPC Codes
14.3.3 A Class of Nonbinary Regular EG-LDPC Codes
14.3.4 Nonbinary LDPC Code Constructions Based on Projective Geometries
14.4 Constructions of Nonbinary QC-LDPC Codes Based on Finite Fields
14.4.1 Dispersion of Field Elements into Nonbinary Circulant Permutation Matrices
14.4.2 Construction of Nonbinary QC-LDPC Codes Based on Finite Fields
14.4.3 Construction of Nonbinary QC-LDPC Codes by Masking
14.4.4 Construction of Nonbinary QC-LDPC Codes by Array Dispersion
14.5 Construction of QC-EG-LDPC Codes Based on Parallel Flats in Euclidean Geometries and Matrix Dispersion
14.6 Construction of Nonbinary QC-EG-LDPC Codes Based on Intersecting Flats in Euclidean Geometries and Matrix Dispersion
14.7 Superposition–Dispersion Construction of Nonbinary QC-LDPC Codes
Problems
References
QC-LDPC Codes
15 LDPC Code Applications and Advanced Topics
15.1 LDPC-Coded Modulation
15.1.1 Design Based on EXIT Charts
15.2 Turbo Equalization and LDPC Code Design for ISI Channels
15.2.1 Turbo Equalization
15.2.2 LDPC Code Design for ISI Channels
15.3 Estimation of LDPC Error Floors
15.3.1 The Error-Floor Phenomenon and Trapping Sets
15.3.2 Error-Floor Estimation
15.4 LDPC Decoder Design for Low Error Floors
15.4.1 Codes under Study
15.4.1.1 The Short QC Code
15.4.1.2 The Margulis Code
15.4.2 The Bi-Mode Decoder
15.4.2.1 Short-QC-Code Solution
15.4.2.2 Margulis-Code Solution
15.4.2.3 Bi-Mode-Decoder Extension
15.4.3 Concatenation and Bit-Pinning
15.4.3.1 Short-QC-Code Solution
15.4.3.2 Margulis-Code Solution
15.4.4 Generalized-LDPC Decoder
15.4.4.1 Short-QC-Code Solution
15.4.4.2 Margulis-Code Solution
15.4.5 Remarks
15.5 LDPC Convolutional Codes
15.6 Fountain Codes
15.6.1 Tornado Codes
15.6.2 Luby Transform Codes
15.6.3 Raptor Codes
Problems
References
Index
This page intentionally left blank
Channel Codes
Channel coding lies at the heart of digital communication and data storage, and
this detailed introduction describes the core theory as well as decoding algorithms,
implementation details, and performance analyses.
Professors Ryan and Lin, known for the clarity of their writing, provide the
latest information on modern channel codes, including turbo and low-density
parity-check (LDPC) codes. They also present detailed coverage of BCH codes,
Reed–Solomon codes, convolutional codes, finite-geometry codes, and product
codes, providing a one-stop resource for both classical and modern coding
techniques.
The opening chapters begin with basic theory to introduce newcomers to the
subject, assuming no prior knowledge in the field of channel coding. Subsequent
chapters cover the encoding and decoding of the most widely used codes and extend
to advanced topics such as code ensemble performance analyses and algebraic code
design. Numerous varied and stimulating end-of-chapter problems, 250 in total,
are also included to test and enhance learning, making this an essential resource
for students and practitioners alike.
William E. Ryan is a Professor in the Department of Electrical and Computer Engi-
neering at the University of Arizona, where he has been a faculty member since
1998. Before moving to academia, he held positions in industry for five years. He
has published over 100 technical papers and his research interests include coding
and signal processing with applications to data storage and data communications.
Shu Lin is an Adjunct Professor in the Department of Electrical and Computer
Engineering, University of California, Davis. He has authored and co-authored
numerous technical papers and several books, including the successful Error Con-
trol Coding (with Daniel J. Costello). He is an IEEE Life Fellow and has received
several awards, including the Alexander von Humboldt Research Prize for US
Senior Scientists (1996) and the IEEE Third-Millenium Medal (2000).
Channel Codes
Classical and Modern
WILLIAM E. RYAN
University of Arizona
SHU LIN
University of California, Davis
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore,
São Paulo, Delhi, Dubai, Tokyo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
Information on this title: www.cambridge.org/9780521848688
© Cambridge University Press 2009
This publication is in copyright. Subject to statutory exception and to the
provision of relevant collective licensing agreements, no reproduction of any part
may take place without the written permission of Cambridge University Press.
First published in print format
2009
ISBN-13 978-0-511-64182-4
eBook (NetLibrary)
ISBN-13 978-0-521-84868-8
Hardback
Cambridge University Press has no responsibility for the persistence or accuracy
of urls for external or third-party internet websites referred to in this publication,
and does not guarantee that any content on such websites is, or will remain,
accurate or appropriate.
Contents
Preface
page xiii
1
2
Coding and Capacity
1.1 Digital Data Communication and Storage
1.2 Channel-Coding Overview
1.3 Channel-Code Archetype: The (7,4) Hamming Code
1.4 Design Criteria and Performance Measures
1.5 Channel-Capacity Formulas for Common Channel Models
1.5.1 Capacity for Binary-Input Memoryless Channels
1.5.2 Coding Limits for M-ary-Input Memoryless Channels
1.5.3 Coding Limits for Channels with Memory
Problems
References
Finite Fields, Vector Spaces, Finite Geometries, and Graphs
2.1 Sets and Binary Operations
2.2 Groups
2.2.1 Basic Concepts of Groups
2.2.2 Finite Groups
2.2.3 Subgroups and Cosets
2.3 Fields
2.3.1 Definitions and Basic Concepts
2.3.2 Finite Fields
2.4 Vector Spaces
2.4.1 Basic Definitions and Properties
2.4.2 Linear Independence and Dimension
2.4.3 Finite Vector Spaces over Finite Fields
2.4.4
Inner Products and Dual Spaces
2.5 Polynomials over Finite Fields
2.6 Construction and Properties of Galois Fields
2.6.1 Construction of Galois Fields
2.6.2 Some Fundamental Properties of Finite Fields
2.6.3 Additive and Cyclic Subgroups
1
1
3
4
7
10
11
18
21
24
26
28
28
30
30
32
35
38
38
41
45
45
46
48
50
51
56
56
64
69
vi
Contents
2.7 Finite Geometries
2.7.1 Euclidean Geometries
2.7.2 Projective Geometries
2.8 Graphs
2.8.1 Basic Concepts
2.8.2 Paths and Cycles
2.8.3 Bipartite Graphs
Problems
References
Appendix A
3
Linear Block Codes
3.1 Introduction to Linear Block Codes
3.1.1 Generator and Parity-Check Matrices
3.1.2 Error Detection with Linear Block Codes
3.1.3 Weight Distribution and Minimum Hamming Distance of a
Linear Block Code
3.1.4 Decoding of Linear Block Codes
3.2 Cyclic Codes
3.3 BCH Codes
3.3.1 Code Construction
3.3.2 Decoding
3.4 Nonbinary Linear Block Codes and Reed–Solomon Codes
3.5 Product, Interleaved, and Concatenated Codes
3.5.1 Product Codes
3.5.2
3.5.3 Concatenated Codes
Interleaved Codes
3.6 Quasi-Cyclic Codes
3.7 Repetition and Single-Parity-Check Codes
Problems
References
4
Convolutional Codes
4.1 The Convolutional Code Archetype
4.2 Algebraic Description of Convolutional Codes
4.3 Encoder Realizations and Classifications
4.3.1 Choice of Encoder Class
4.3.2 Catastrophic Encoders
4.3.3 Minimal Encoders
4.3.4 Design of Convolutional Codes
4.4 Alternative Convolutional Code Representations
4.4.1 Convolutional Codes as Semi-Infinite Linear Codes
4.4.2 Graphical Representations for Convolutional Code Encoders
70
70
76
80
80
84
86
88
90
92
94
94
95
98
99
102
106
111
111
114
121
129
129
130
131
133
142
143
145
147
147
149
152
157
158
159
163
163
164
170
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
