Cycle Analysis of Low-Density Parity-Check Codes

摘要

具有强大纠错能力的低密度奇偶校验码已被广泛应用于卫星通信，无线通信和存储领域。在发现低密度奇偶校验码是一类接近Shannon限的好码以后，它就成了编码学家的研究热点之一。低密度奇偶校验码具有很多优点：接近Shannon限的纠错性能，描述简便，易于进行理论分析和研究，译码简单并且可进行并行操作，便于硬件实现等。 尽管低密度奇偶校验码有许多的优点，但它们却有较高的编码复杂度，且需要较大的存储空间。准循环的低密度奇偶校验码作为一类结构化的低密度奇偶校验码，具有线性时间的编码算法且所需存储空间较小，已成为当前的研究热点。 围长是评价低密度奇偶校验码性能的一个重要参数，迭代译码的初始迭代次数与围长呈线性关系。低密度奇偶校验码中的短环导致它的围长很小，研究表明，这些短环对低密度奇偶校验码的译码具有消极影响。因此，在构造好的低密度奇偶校验码时避免或消去短环来得到大围长的码是很有必要的。在构造结构化的具有较大围长的低密度奇偶校验码前，分析清楚环的性质和结构是很有帮助的。 本文的主要工作是讨论低密度奇偶校验码中的环的结构和性质。针对传统的准循环低密度奇偶校验码的围长无法超过12的情况，我们将着重讨论准循环低密度奇偶校验码中的环。 首先，我们给出了环的更一般的定义，研究了低密度奇偶校验码中的简单环。我们得到了任意长度的简单环的个数和它们的最小矩阵。 其次，为了消除准循环低密度奇偶校验码中一类特殊的环，我们把由循环置换矩阵扩张得到的准循环低密度奇偶校验码看做一类原图低密度奇偶校验码。我们揭示了原图低密度奇偶校验码中的环与该码母矩阵中环的关系。我们还得到了任意一个原图低密度奇偶校验码的围长不会小于它的母矩阵的围长的结论。 最后，我们研究了准循环低密度奇偶校验码中的不可避免环，即所谓的平衡环。我们分析了平衡环的结构，给出了平衡环存在的充要条件，得到了最短平衡环的所有B-最小矩阵。最终我们还给出了确定准循环低密度奇偶校验码母矩阵的B-围长的方法。

目录

文摘

英文文摘

声明

Chapter 1 Introduction

1.1 Digital Communication Systems

1.2 Error Control Coding

1.2.1 Types of Errors

1.2.2 Types of Codes

1.2.3 Error Control Strategies

1.3 Shannon Limit

1.4 Motivation and Outline of the Dissertation

Chapter 2 Linear Block Codes

2.1 Introduction to Linear Block Codes

2.1.1 Generator Matrix

2.1.2 Parity Check Matrix

2.2 Minimum Distance

2.3 Maximum-Likelihood Decoding

2.4 Cyclic Codes

2.5 Quasi-Cyclic Codes

Chapter 3 Low-Density Parity-Check Codes

3.1 Representations of LDPC Codes

3.1.1 Matrix Representation of LDPC Codes

3.1.2 Graphical Representation of LDPC Codes

3.2 Encoding of LDPC Codes

3.2.1 Systematic Encoding

3.2.2 Richardson's Efficient Encoding

3.3 Decoding of LDPC Codes

3.3.1 Majority-Logic Decoding

3.3.2 A Bit Flipping Algorithm

3.3.3 The Sum-Product Algorithm

3.4 Constructions of LDPC Codes

3.4.1 Constructions of Random LDPC codes

3.4.2 Constructions of Structured LDPC codes

Chapter 4 Cycles in LDPC Codes

4.1 Paths

4.2 Cycles

4.3 Cycle Effects on the Performance of LDPC Code

4.4 Determination of Minimal Matrices of Simple Cycles

Chapter 5 Cycles in Expanded LDPC Codes

5.1 Introduction

5.2 Expanded LDPC Codes

5.2.1 Permutation and Permutation Matrix

5.2.2 Expanded LDPC Codes

5.3 Cycle Relationships in Protograph LDPC Codes

5.4 Limitation of Lifting QC-LDPC Codes

5.4.1 Some Results of Lifting in QC-LDPC Codes

5.4.2 Limitation of QC-LDPC Codes

Chapter 6 Cycle Analysis of QC-LDPC Codes

6.1 Introduction

6.2 Necessary and Sufficient Conditions for the Existence of Balanced Cycles

6.3 Determination of Minimal Matrices of Balanced Cycles

6.4 Determination of the Shortest Balanced Cycles

Chapter 7 Conclusion and Future Work

7.1 Summary and Contributions

7.2 Future work

Appendix A

Bibfiography

Publications

Resume

Acknowledgements