Design and Analysis of Low-Density Parity-Check Codes for Communication Systems

Abstract

Low-density parity-check (LDPC) codes achieve the performance near to the Shannon limit by iterative decoding. They are extensively employed in communication system standards such as DVB-S2, IEEE 802.16e, and IEEE 802.11n because of their capacity-approaching performance and low decoding complexity. The objective of this thesis is to develop schemes to design LDPC codes for communication systems for improving their performance and memory efficiency.It is well-known that the sum-product algorithm provides optimum decoding for LDPC codes with no cycles. However, short cycles in the Tanner graph of LDPC codes may induce a serious performance degradation. Hence, it is natural to try to minimize the influence of cycles on the decoding process. Several researchers made an effort to obtain the LDPC codes with no short cycles. Quasi-cyclic LDPC (QC-LDPC) code is an interesting type of LDPC codes, based on circulant permutation matrices (CPMs). It requires a smaller size of memory for encoding and/or decoding and are easier to analyze their algebraic properties than random LDPC codes. This motivates us to take an intensive interest in constructing QC-LDPC codes without short cycles. We first derive bounds which are necessary conditions for a QC-LDPC code to have a given girth in terms of its parameters. We also give a bound which is a sufficient condition for a QC-LDPC code of a given girth to be constructed by a greedy algorithm. Numerical results show that our bounds on the size of parity-check matrices for regular LDPC codes are tighter than any other known bounds. Furthermore, our results can be applied to any regular or irregular QC-LDPC codes.Our second consideration is to design QC-LDPC codes without short cycles. Lee {\it et al.} proposed an algorithm for detecting and counting cycles of LDPC codes based on message passing algorithm. In the case of QC-LDPC codes, if an edge $e$ is contained in a cycle of length $2l$, then each edge corresponding to the circulant permutation matrix (CPM) associated with $e$ are also contained in a cycle of length $2l$. Therefore, the complexity of detecting and counting cycles of QC-LDPC codes may be reduced by $1/L$ where the size of CPM is $L \times L$. This algorithm can be applicable to general QC-LDPC codes without additional complexity. Using this algorithm we detect the cycles of girth and propose a simple algorithm for removing them from QC-LDPC codes. AS a result, we present the constructing method for QC-LDPC codes without short cycles and show it performs well. Furthermore, we also give an improved upper bound on length of QC-LDPC codes. In the last part of this thesis, we propose an algorithm to generate a mother code for length-compatible LDPC (LC-LDPC) codes of a given rate such that their degree distributions are almost the same as the degree distribution of the mother code. Numerical results show that LC-LDPC codes constructed by our approach perform much better than those by the conventional approach.

LDPC (low-density parity-check) 부호는 반복 복호 방법을 통해 Shannon의 한계에 근접하는 성능을 가진다고 알려져 있다. 낮은 복호 복잡도를 가지면서 우수한 성능을 가지는 LDPC 부호의 장점 때문에 DVB-S2, IEEE 802.16e, IEEE 802.11n과 같은 다양한 통신 시스템의 FEC 기법으로 LDPC 부호가 채택되고 있다. 본 논문에서는 다양한 통신 시스템에서 우수한 성능 및 효율성을 가지는 LDPC 부호를 설계하는 방법에 대하여 연구한다.Cycle이 존재하지 않는 LDPC 부호는 합-곱 알고리즘을 통해 최적의 복호 성능을 얻을 수 있다는 사실이 알려져 있다. 하지만 짧은 길이를 가지는 LDPC 부호의 성능은 짧은 길이를 가지는 cycle들이나 stopping set들과 같은 대수적 특성의 영향을 크게 받을 수 있다. 특히 길이가 4인 cycle이나 매우 작은 stopping set은 치명적인 오류를 유발할 수 있다. 따라서 우수한 복호 성능을 얻기 위해 짧은 사이클을 피하는 방법을 개발하는 것은 중요한 문제이다. 순환 순열 행렬에 기반한 QC-LDPC (quasi-cyclic LDPC) 부호는 대수적인 구조를 가지기 때문에 메모리 효율성이 우수할 뿐만 아니라 shift 일반적인 LDPC 부호에 비하여 cycle 특성을 분석하기가 용이하다. 본 논문에서는 짧은 cycle을 가지지 않는 QC-LDPC 부호에 대해 주로 연구한다.본 논문에서는 우선 QC-LDPC 부호의 매개 변수를 이용해 QC-LDPC 부호에 특정 길이 이하의 cycle이 포함되어 있지 않기 위한 필요 조건을 유도한다. 또한 greedy 알고리즘을 사용하여 QC-LDPC 부호를 설계할 때, QC-LDPC 부호가 특정 길이 이하의 cycle을 포함하지 않기 위한 충분 조건을 유도한다. 전산 실험 결과를 통해 본 논문에서 유도한 필요 조건 및 충분 조건이 다른 조건들보다 더 우수한 bound임을 보인다. 또한 본 논문에서는 짧은 cycle을 가지지 않는 QC-LDPC 부호의 설계 방법에 대하여 연구한다. 기존에 알려져 있는 메시지 전달 복호 방법을 통한 LDPC 부호의 cycle 검출 방법을 응용하여 QC-LDPC 부호의 cycle 역시 검출이 가능하다. 이 경우 기존 알고리즘에 비하여 cycle을 검출하기 위한 복잡도가 큰 폭으로 감소한다. 또한 검출된 cycle에 대응하는 QC-LDPC 부호의 지수들의 값을 변경하거나 위치를 바꿔주는 작업을 통해 검출된 cycle을 제거할 수 있다. 이러한 작업의 반복을 통해 짧은 cycle이 없는 QC-LDPC 부호의 설계가 가능하다. 마지막으로 부호율이 주어져 있을 경우 다양한 길이를 지원할 수 있는 LC-LDPC (length-compatible LDPC) 부호의 설계 방법을 제안한다. 각각의 LC-LDPC 부호가 모부호와 동일한 차수 분포를 가지도록 설계함으로서 모든 길이에서 우수한 성능을 가지도록 할 수 있다. 전산 실험을 통해 제안된 방법으로 설계된 LC-LDPC 부호가 다른 방법으로 설계된 경우보다 우수하다는 것을 보인다.