Essentials of Error-Control Coding
暫譯: 錯誤控制編碼基礎

Jorge Castiñeira Moreira, Patrick Guy Farrell

Essentials of Error-Control Coding

買這商品的人也買了...

相關主題

商品描述

Description

Rapid advances in electronic and optical technology have enabled the implementation of powerful error-control codes, which are now used in almost the entire range of information systems with close to optimal performance. These codes and decoding methods are required for the detection and correction of the errors and erasures which inevitably occur in digital information during transmission, storage and processing because of noise, interference and other imperfections.

Error-control coding is a complex, novel and unfamiliar area, not yet widely understood and appreciated. This book sets out to provide a clear description of the essentials of the subject, with comprehensive and up-to-date coverage of the most useful codes and their decoding algorithms. A practical engineering and information technology emphasis, as well as relevant background material and fundamental theoretical aspects, provides an in-depth guide to the essentials of Error-Control Coding.

  • Provides extensive and detailed coverage of Block, Cyclic, BCH, Reed-Solomon, Convolutional, Turbo, and Low Density Parity Check (LDPC) codes, together with relevant aspects of Information Theory
  • EXIT chart performance analysis for iteratively decoded error-control techniques
  • Heavily illustrated with tables, diagrams, graphs, worked examples, and exercises
  • Invaluable companion website features slides of figures, algorithm software, updates and solutions to problems     

Offering a complete overview of Error Control Coding, this book is an indispensable resource for students, engineers and researchers in the areas of telecommunications engineering, communication networks, electronic engineering, computer science, information systems and technology, digital signal processing and applied mathematics.

 

Table of Contents

Preface & Acknowledgements.

Symbols & Abbreviations.

1 INFORMATION AND CODING THEORY.

1.1 Information.

1.1.1 Information measure.

1.2 Entropy and Information Rate.

1.3 Extended Discrete Memoryless Source.

1.4 Channels and Mutual Information.

1.4.1 Information transmission over discrete channels.

1.4.2 Information channels.

1.5 Channel Probability Relationships.

1.6 The a priori and a posteriori Entropies.

1.7 Mutual Information.

1.7.1 Mutual information: Definition.

1.7.2 Mutual information: Properties.

1.8 Capacity of a Discrete Channel.

1.9 Shannon’s Theorems.

1.9.1 Source coding theorem.

1.9.2 Channel capacity and coding.

1.9.3 Channel coding theorem.

1.10 Signal Spaces and the Channel Coding Theorem.

1.10.1 Capacity of the Gaussian Channel.

1.11 Error Control Coding.

1.12 Limits to Communication and their Consequences.

Bibliography and References.

Problems.

2. BLOCK CODES.

2.1 Error Control Coding.

2.2 Error Detection and Correction.

2.2.1 Simple codes: The repetition code.

2.3 Block Codes: Introduction and Parameters.

2.4 The Vector Space over the Binary Field.

2.4.1 Vector subspaces.

2.4.2 Dual subspaces.

2.4.3 Matrix form.

2.4.4 Dual subspace matrix.

2.5 Linear Block Codes.

2.5.1 Generator matrix G.

2.5.2 Block codes in systematic form.

2.5.3 Parity check matrix H.

2.6 Syndrome Error Detection.

2.7 Minimum Distance of a Block Code.

2.7.1 Minimum distance and the structure of the H matrix.

2.8 Error Correction Capability of a Block Code.

2.9 Syndrome Detection and the Standard Array.

2.10 Hamming Codes.

2.11 Forward Error Correction (FEC) and Automatic Repeat ReQuest (ARQ).

2.11.1 Forward error correction (FEC).

2.11.2 Automatic Repeat ReQuest (ARQ).

2.11.3 ARQ schemes.

2.11.3.1 Stop and Wait.

2.11.3.2 Go back N.

2.11.3.3 Selective Repeat.

2.11.4 ARQ scheme efficiencies.

2.11.5 Hybrid-ARQ schemes.

Bibliography and References.

Problems.

3 CYCLIC CODES.

3.1 Description.

3.2 Polynomial Representation of Codewords.

3.3 Generator Polynomial of a Cyclic Code.

3.4 Cyclic Codes in Systematic Form.

3.5 Generator Matrix of a Cyclic Code.

3.6 Syndrome Calculation and Error Detection.

3.7 Decoding of Cyclic Codes.

3.8 An Application Example: CRC Code for the Ethernet Standard.

Bibliography and References.

Problems.

4 BCH CODES.

4.1 Introduction: The Minimal Polynomial.

4.2 Description of BCH Cyclic Codes.

4.2.1 Bounds on the error-correction capability of a BCH code: the Vandermonde determinant.

4.3 Decoding of BCH Codes.

4.4 Error Location and Error Evaluation Polynomials.

4.5 The Key Equation.

4.6 Decoding of BCH Codes using the Euclidean Algorithm.

4.6.1 The Euclidean algorithm.

Bibliography and References.

Problems.

5 REED-SOLOMON CODES.

5.1 Introduction.

5.2 Error Correction Capability of RS Codes: The Vandermonde Determinant.

5.3 RS Codes in Systematic Form.

5.4 Syndrome Decoding of RS Codes.

5.5 The Euclidean Algorithm. Error Location and Evaluation Polynomials.

5.6 Decoding of RS Codes using the Euclidean Algorithm.

5.6.1 Steps of the Euclidean algorithm.

5.7 Decoding of RS and BCH Codes using the Berlekamp- Massey Algorithm.

5.7.1 Berlekamp-Massey iterative algorithm for finding the error location polynomial.

5.7.2 Berlekamp-Massey decoding of RS codes.

5.7.3 Relationship between the error location polynomials of the Euclidean and Berlekamp-Massey algorithms.

5.8 A Practical Application: Error-Control Coding for the Compact Disc (CD).

5.8.1 CD Characteristics.

5.8.2 Channel characteristics.

5.8.3 Coding procedure.

5.9 Encoding for RS codes C(RS)(28,24), C(RS)(32,28) and C(RS)(255,251).

5.10 Decoding of RS Codes C(RS)(28,24) and  C(RS)(32,28).

5.10.1 Berlekamp-Massey decoding.

5.10.2 Alternative decoding methods.

5.10.3 Direct solution of syndrome equations.

5.11 Importance of Interleaving Bibliography and References Problems.

6 CONVOLUTIONAL CODES.

6.1 Linear Sequential Circuits.

6.2 Convolutional Codes and Encoders.

6.3 Description in the D-Transform Domain.

6.4 Convolutional Encoder Representations.

6.4.1 Representation of connections.

6.4.2 State diagram representation.

6.4.3 Trellis representation.

6.5 Convolutional Codes in Systematic Form.

6.6 General Structure of FIR and IIR Finite State Sequential Machines.

6.6.1 FIR FSSM.

6.6.2 IIR FSSM.

6.7 State Transfer Function Matrix: Calculation of the Transfer Function.

6.7.1 State transfer function for FIR FSSMs.

6.7.2 State transfer function for IIR FSSMs.

6.8 Relationship between the Systematic and Non-Systematic Forms.

6.9 Distance Properties of Convolutional Codes.

6.10 Minimum Free Distance of a Convolutional Code.

6.11 Maximum Likelihood Detection (MLD).

6.12 Decoding of Convolutional Codes: The Viterbi Algorithm.

6.13 Extended and Modified State Diagram.

6.14 Error Probability Analysis for Convolutional Codes.

6.15 Hard and soft Decisions.

6.15.1 Maximum likelihood criterion for the Gaussian channel.

6.15.2 Bounds for soft decision detection.

6.15.3 An example of soft decision decoding of convolutional codes.

6.16 Punctured Convolutional Codes and Rate Compatible Schemes.

Bibliography and References.

Problems.

7 TURBO CODES.

7.1 A Turbo Encoder.

7.2 Decoding of Turbo Codes.

7.2.1 Turbo decoder.

7.2.2 Probabilities and estimates.

7.2.3 Symbol detection.

7.2.4 The log likelihood ratio.

7.3 Markov Sources and Discrete Channels.

7.4 The BCJR Algorithm: Trellis Coding and Discrete Memoryless Channels.

7.5 Iterative Coefficient Calculation.

7.6 MAP BCJR Algorithm and the Log Likelihood Ratio.

7.6.1 The BCJR MAP algorithm: LLR calculation.

7.6.2 Calculation of coefficients γi(u′,u).

7.7 Turbo Decoding.

7.7.1 Initial conditions of coefficients αj-1(u′) and βj(u).

7.8 Construction Methods for Turbo Codes.

7.8.1 Interleavers.

7.8.2 Block interleavers.

7.8.3 Convolutional interleavers.

7.8.4 Random interleavers.

7.8.5 Linear interleavers.

7.8.6 Code concatenation methods.

7.8.6.1 Serial concatenation.

7.8.6.2 Parallel concatenation.

7.8.7 Turbo code performance as a function of size and type of interleaver.

7.9 Other Decoding Algorithms for Turbo Codes.

7.10 EXIT Charts for Turbo Codes.

7.10.1 Introduction to EXIT charts.

7.10.2 Construction of the EXIT chart.

7.10.3 Extrinsic transfer characteristics of the constituent decoders.

Bibliography and References.

Problems.

8 LOW-DENSITY PARITY-CHECK (LDPC) CODES.

8.1 Different Systematic Forms of a Block Code.

8.2 Description of LDPC Codes.

8.3 Construction of LDPC Codes.

8.3.1 Regular LDPC codes.

8.3.2 Irregular LDPC codes.

8.3.3 Decoding of LDPC codes: the Tanner graph.

8.4 The Sum-Product Algorithm.

8.5 Sum-Product Algorithm for LDPC Codes: An Example.

8.6 Simplifications of the Sum-Product Algorithm.

8.7 A Logarithmic LDPC Decoder.

8.7.1 Initialization.

8.7.2 Horizontal step.

8.7.3 Vertical step.

8.7.4 Summary of the logarithmic decoding algorithm.

8.7.5 Construction of the lookup table.

8.8 EXIT Charts for LDPC Codes.

8.8.1 Introduction.

8.8.2 Iterative decoding of block codes.

8.8.3 EXIT chart construction for LDPC codes.

8.8.4 Mutual information function.

8.8.5 EXIT chart for the symbol node decoder (SND).

8.8.6 EXIT chart for the parity check node decoder (PCND).

8.9 Fountain and LT Codes.

8.9.1 Introduction.

8.9.2.Fountain codes.

8.9.3.Linear random codes.

8.9.4 LT codes.

8.9.4.1 LT encoder.

8.9.4.2 LT decoder.

8.10 LDPC and Turbo Codes.

Bibliography and References.

Problems.

APPENDIX A: Error Probability in the Transmission of Digital Signals.

A.1 Digital Signalling.

A.1.1 Pulse amplitude modulated digital signals.

A.2 Bit Error Rate (BER).

Bibliography.

APPENDIX B: Galois Fields GF(q).

B.1 Groups.

B.2 Addition and Multiplication modulo-2.

B.3 Fields.

B.4 Polynomials over Binary Fields.

B.5 Construction of a Galois Field GF(2m).

B.6 Properties of Extended Galois Fields GF(2m). 

B.7 Minimal Polynomials.

B.7.1 Properties of Minimal Polynomials.

Bibliography.

Answers to Problems.

Index.

商品描述(中文翻譯)

**描述**

電子和光學技術的快速進步使得強大的錯誤控制碼的實現成為可能，這些碼現在幾乎在所有信息系統中使用，並且接近最佳性能。這些碼和解碼方法是檢測和糾正數字信息在傳輸、存儲和處理過程中不可避免地發生的錯誤和擦除所必需的，這些錯誤和擦除是由於噪聲、干擾和其他不完美因素造成的。

錯誤控制編碼是一個複雜、新穎且不熟悉的領域，尚未被廣泛理解和重視。本書旨在提供該主題的清晰描述，全面且最新地涵蓋最有用的碼及其解碼算法。實用的工程和信息技術重點，以及相關的背景材料和基本理論方面，提供了對錯誤控制編碼基本要素的深入指導。

- 提供對區塊碼、循環碼、BCH碼、Reed-Solomon碼、卷積碼、Turbo碼和低密度奇偶檢查碼（LDPC）的廣泛和詳細覆蓋，並涉及信息理論的相關方面
- 針對迭代解碼的錯誤控制技術進行EXIT圖性能分析
- 以表格、圖示、圖表、實例和練習進行大量插圖
- 無價的伴隨網站提供圖形幻燈片、算法軟件、更新和問題解決方案

本書提供了錯誤控制編碼的完整概述，是電信工程、通信網絡、電子工程、計算機科學、信息系統與技術、數字信號處理和應用數學領域的學生、工程師和研究人員不可或缺的資源。

**目錄**

前言與致謝。

符號與縮寫。

1 信息與編碼理論。
1.1 信息。
1.1.1 信息度量。
1.2 熵與信息速率。
1.3 擴展離散無記憶源。
1.4 通道與互信息。
1.4.1 通過離散通道的信息傳輸。
1.4.2 信息通道。
1.5 通道概率關係。
1.6 先驗熵與後驗熵。
1.7 互信息。
1.7.1 互信息：定義。
1.7.2 互信息：性質。
1.8 離散通道的容量。
1.9 香農定理。
1.9.1 源編碼定理。
1.9.2 通道容量與編碼。
1.9.3 通道編碼定理。
1.10 信號空間與通道編碼定理。
1.10.1 高斯通道的容量。
1.11 錯誤控制編碼。
1.12 通信的限制及其後果。
參考文獻。
問題。

2 區塊碼。
2.1 錯誤控制編碼。
2.2 錯誤檢測與糾正。
2.2.1 簡單碼：重複碼。
2.3 區塊碼：介紹與參數。
2.4 二進制域上的向量空間。
2.4.1 向量子空間。
2.4.2 對偶子空間。
2.4.3 矩陣形式。
2.4.4 對偶子空間矩陣。
2.5 線性區塊碼。
2.5.1 生成矩陣 G。
2.5.2 系統形式的區塊碼。
2.5.3 奇偶檢查矩陣 H。
2.6 短信檢測。
2.7 區塊碼的最小距離。
2.7.1 最小距離與 H 矩陣的結構。
2.8 區塊碼的錯誤糾正能力。
2.9 短信檢測與標準陣列。
2.10 哈明碼。
2.11 向前錯誤糾正（FEC）與自動重傳請求（ARQ）。
2.11.1 向前錯誤糾正（FEC）。
2.11.2 自動重傳請求（ARQ）。
2.11.3 ARQ方案。
2.11.3.1 停止與等待。
2.11.3.2 回退 N。
2.11.3.3 選擇性重傳。
2.11.4 ARQ方案效率。
2.11.5 混合 ARQ 方案。
參考文獻。
問題。

3 循環碼。
3.1 描述。
3.2 碼字的多項式表示。
3.3 循環碼的生成多項式。
3.4 系統形式的循環碼。
3.5 循環碼的生成矩陣。
3.6 短信計算與錯誤檢測。
3.7 循環碼的解碼。
3.8 應用示例：以太網標準的 CRC 碼。
參考文獻。
問題。

4 BCH 碼。
4.1 介紹：最小多項式。
4.2 BCH 循環碼的描述。
4.2.1 BCH 碼的錯誤糾正能力的界限：Vandermonde 行列式。
4.3 BCH 碼的解碼。
4.4 錯誤位置與錯誤評估多項式。
4.5 關鍵方程。
4.6 使用歐幾里得算法解碼 BCH 碼。
4.6.1 歐幾里得算法。
參考文獻。
問題。

5 Reed-Solomon 碼。
5.1 介紹。
5.2 RS 碼的錯誤糾正能力：Vandermonde 行列式。
5.3 系統形式的 RS 碼。
5.4 RS 碼的短訊解碼。
5.5 歐幾里得算法。錯誤位置與評估多項式。
5.6 使用歐幾里得算法解碼 RS 碼。
5.6.1 歐幾里得算法的步驟。
5.7 使用 Berlekamp-Massey 算法解碼 RS 和 BCH 碼。
5.7.1 Berlekamp-Massey 迭代算法尋找錯誤位置多項式。
5.7.2 Berlekamp-Massey 解碼 RS 碼。
5.7.3 歐幾里得與 Berlekamp-Massey 算法的錯誤位置多項式之間的關係。
5.8 實際應用：緊湊光碟（CD）的錯誤控制編碼。
5.8.1 CD 特性。
5.8.2 通道特性。
5.8.3 編碼過程。
5.9 RS 碼 C(RS)(28,24)、C(RS)(32,28) 和 C(RS)(255,251) 的編碼。
5.10 RS 碼 C(RS)(28,24) 和 C(RS)(32,28) 的解碼。
5.10.1 Berlekamp-Massey 解碼。
5.10.2 替代解碼方法。
5.10.3 短信方程的直接解。
5.11 交錯的重要性。
參考文獻。
問題。

6 卷積碼。
6.1 線性序列電路。
6.2 卷積碼與編碼器。
6.3 在 D 變換域中的描述。
6.4 卷積編碼器表示。
6.4.1 連接的表示。
6.4.2 狀態圖表示。
6.4.3 格子表示。
6.5 系統形式的卷積碼。
6.6 FIR 和 IIR 有限狀態序列機的通用結構。
6.6.1 FIR FSSM。
6.6.2 IIR FSSM。
6.7 狀態轉移函數矩陣：轉移函數的計算。
6.7.1 FIR FSSM 的狀態轉移函數。
6.7.2 IIR FSSM 的狀態轉移函數。
6.8 系統形式與非系統形式之間的關係。
6.9 卷積碼的距離性質。
6.10 卷積碼的最小自由距離。
6.11 最大似然檢測（MLD）。
6.12 卷積碼的解碼：Viterbi 算法。
6.13 擴展和修改的狀態圖。
6.14 卷積碼的錯誤概率分析。
6.15 硬決策與軟決策。
6.15.1 高斯通道的最大似然準則。
6.15.2 軟決策檢測的界限。
6.15.3 卷積碼的軟決策解碼示例。
6.16 切割卷積碼和速率相容方案。
參考文獻。
問題。

7 Turbo 碼。
7.1 Turbo 編碼器。
7.2 Turbo 碼的解碼。
7.2.1 Turbo 解碼器。
7.2.2 機率與估計。
7.2.3 符號檢測。
7.2.4 對數似然比。
7.3 馬可夫源與離散通道。
7.4 BCJR 算法：格子編碼與離散無記憶通道。
7.5 迭代係數計算。
7.6 MAP BCJR 算法與對數似然比。
7.6.1 BCJR MAP 算法：LLR 計算。
7.6.2 係數 γ_i(u′,u) 的計算。
7.7 Turbo 解碼。
7.7.1 係數 α_{j-1}(u′) 和 β_j(u) 的初始條件。
7.8 Turbo 碼的構造方法。
7.8.1 交錯器。
7.8.2 區塊交錯器。
7.8.3 卷積交錯器。
7.8.4 隨機交錯器。
7.8.5 線性交錯器。
7.8.6 碼的串聯方法。
7.8.6.1 串聯串接。
7.8.6.2 並聯串接。
7.8.7 Turbo 碼性能與交錯器的大小和類型的關係。

7.9 Turbo 碼的其他解碼算法。
7.10 Turbo 碼的 EXIT 圖。
7.10.1 EXIT 圖介紹。
7.10.2 EXIT 圖的構建。
7.10.3 組成解碼器的外部傳遞特性。
參考文獻。
問題。

8 低密度奇偶檢查碼（LDPC）。
8.1 區塊碼的不同系統形式。
8.2 LDPC 碼的描述。
8.3 LDPC 碼的構建。
8.3.1 正則 LDPC 碼。
8.3.2 不規則 LDPC 碼。
8.3.3 LDPC 碼的解碼：Tanner 圖。
8.4 和積算法。
8.5 LDPC 碼的和積算法：示例。
8.6 和積算法的簡化。
8.7 對數 LDPC 解碼器。
8.7.1 初始化。
8.7.2 水平步驟。
8.7.3 垂直步驟。
8.7.4 對數解碼算法的總結。
8.7.5 查找表的構建。

8.8 LDPC 碼的 EXIT 圖。
8.8.1 介紹。
8.8.2 區塊碼的迭代解碼。
8.8.3 LDPC 碼的 EXIT 圖構建。
8.8.4 互信息函數。
8.8.5 符號節點解碼器（SND）的 EXIT 圖。
8.8.6 奇偶檢查節點解碼器（PCND）的 EXIT 圖。
8.9 Fountain 碼和 LT 碼。
8.9.1 介紹。
8.9.2 Fountain 碼。
8.9.3 線性隨機碼。
8.9.4 LT 碼。
8.9.4.1 LT 編碼器。
8.9.4.2 LT 解碼器。
8.10 LDPC 碼與 Turbo 碼。
參考文獻。
問題。

附錄 A：數字信號傳輸中的錯誤概率。

類似商品