Efficient Min-Sum decoding algorithms for low-complexity LDPC decoders

국문 초록 (Abstract)

저밀도 패리티검사 (low-density parity check, LDPC) 부호는 우수한 성능과 더불어 그 복호 과정이 병렬화하기에 적합하여 지난 십여 년 간 집중적으로 연구되어왔으며, 오늘날 위성, 지상파 방송, 무선 인터넷 등 통신 시스템의 표준으로 채택되었으며, 광디스크나 하드디스크, 낸드플래시 메모리 기반의 저장장치의 오류 정정 부호로도 고려되고 있다.
본 학위논문에서는 LDPC 부호의 복호 방법 중 낮은 복잡도와 상대적으로 우수한 복호 성능으로 가장 널리 쓰이는 최소합 복호 방법의 성능 개선에 대해 연구를 진행하였다. 본 논문의 주 목표는 LDPC 복호기의 하드웨어 구현을 고려한 최소합 알고리즘의 개선 방안 제안으로, 외부의 정보에 의존하거나 복잡한 계산 과정을 요구하는 기존 알고리즘들과는 달리 복호기의 내부 정보만을 이용해 전력 소모 감소 및 복호 성능을 높이는 방안을 제안한다.
본 논문에서 첫 번째로 제안하는 알고리즘은 LDPC 복호기의 조건적 종료 검사 스케줄링 방안으로, LDPC 복호 과정 중 종료 검사 과정의 진행 여부를 디코더 내의 검사 노드 메시지를 이용하여 동적으로 결정하는 알고리즘이다. 검사 노드 메시지 구성 방법 중 최소값 두 개의 차를 이용한 Δmin 을 내부 정보로 선택하였으며, 본 논문에서는 이에 대한 분석을 통해 Δmin이 채널의 상태 및 수신된 메시지의 수렴 여부를 결정할 수 있는 지표로 사용될 수 있음을 증명하였다. Δmin의 평균이 임계값 이하일 경우 종료 검사를 생략함으로써 복호 속도를 개선하고 전력소모를 줄일 수 있음을 확인하였다.
두 번째로 제안된 자가 적응적 크기 조정 최소합 알고리즘 (Δmin based adaptive scaled min-sum algorithm, DAS-MSA) 은 역시 Δmin의 채널 상황을 반영하는 특성을 이용하여 검사 노드 메시지의 크기를 조절하는 알고리즘이다. 채널 상황이 좋다고 판단이 될 경우에는 1에 가까운 값을 검사노드 메시지에 곱해주고, 반대의 경우는 곱해주는 값을 0.5에 가깝게 낮추어 그 영향을 최소화 한다. 이 곱해주는 값들은 비트 시프트와 덧셈으로 구현할 수 있도록 선택하였다. 시뮬레이션 결과 적은 하드웨어 비용으로 복호 성능을 기존 알고리즘들 보다 개선하였으며, 오류 마루 현상에도 강한 것을 확인할 수 있었다.
마지막으로 제안된 간소화된 이차원 크기 조정 최소합 알고리즘 (simplified 2-dimensional scaled min-sum algorithm, S2DS) 은 첫 번째 최소값과 두 번째 최소값에 서로 다른 계수를 곱할 때 복호 성능이 좋아진다는 연구결과를 활용한 알고리즘이다. 하드웨어로 구현하기 용이하고 좋은 성능을 내는 계수 쌍을 시뮬레이션을 통해 선택하였으며, Δmin 값의 분석을 통해 이 중 한 계수에 대한 연산을 Δmin을 이용해 근사화 함으로써 연산량을 대폭 줄였다. 기존 알고리즘들과 비교하여 S2DS 알고리즘의 연산량은 가장 낮지만, 오류 정정 성능은 양자화를 진행한 후에도 가장 뛰어난 것을 확인할 수 있었다.

다국어 초록 (Multilingual Abstract)

Due to their outstanding error correction performance and strong parallelism potential of the decoding process, low-density parity-check (LDPC) codes have received a great deal of attention in the past few decades. LDPC codes have been adopted in various communication systems and even adopted for error correction for solid-state disks based on NAND flash memory. Since these applications commonly require higher throughput with lower power consumption, implementing efficient LDPC decoders has been actively studied in various ways including scheduling schemes, decoding algorithms, and efficient hardware implementations of the decoder.
In this dissertation, we have studied efficient LDPC decoding algorithms that consider the hardware implementation of LDPC decoder. The main objectives of this dissertation are including a conditional scheduling approach of the min-sum algorithm using internal information, an adaptive scaled min-sum algorithm to enhance decoding performance, and a simplified 2-dimensional scaled min-sum algorithm with lowest computational complexity.
The adaptive termination check scheme using Δmin dynamically decides whether the termination checking step will be carried out based on the internal information that exchanged in the decoding process of LDPC codes. With this approach decoding speed is improved by 7% and the power consumption is reduced by 16.34%.
The self-adaptive scaled min-sum algorithm for LDPC decoder utilizes the difference between the first two minima of the check node messages (Δmin). Δmin of the check node is used for adjusting the scaling factor of the check node messages, and simulation results show that the proposed algorithm improves the error correcting performance compared to existing algorithms.
In the simplified 2-dimensional scaled (S2DS) min-sum algorithm, we figure out a pair of the most efficient scaling factors which multiplications can be replaced with combinations of addition and shift operations. Furthermore, one of the scaling operations can be approximated by the Δmin. As a result, the proposed algorithm shows the least computational complexity among the normalized min-sum algorithms, and its decoding performance is superior compared to the existing algorithms.

목차 (Table of Contents)

• List of Figures iv
• List of Tables vii
• 국문요약 viii
• 1. Introduction 1
• 1.1. Low-density parity-check codes 1
• 1.2. Dissertation goal 4
• 1.3. Dissertation organization 5
• 2. Background 6
• 2.1. Digital communication 6
• 2.2. Channel coding 7
• 2.2.1. Shannon theorem 7
• 2.2.2. Channel models 9
• 2.2.3. Linear block code 12
• 3. Low-Density Parity-Check Codes 18
• 3.1. A brief history of LDPC codes 18
• 3.2. Introduction to LDPC codes 19
• 3.2.1. Classes of LDPC codes 20
• 3.2.1.1. Regularity 20
• 3.2.1.2. Structure of H matrix 22
• 3.3. Decoding algorithms of LDPC codes 24
• 3.3.1. Belief propagation algorithm 25
• 3.3.2. Sum-product algorithm 27
• 3.3.3. Min-sum algorithm 30
• 3.4. Scheduling algorithms of LDPC codes 34
• 3.4.1. Flooding scheduling algorithm 34
• 3.4.2. Serial scheduling algorithm 36
• 4. Adaptive Termination Check Scheme Using Δmin for Efficient LDPC Decoders 39
• 4.1. Introduction 40
• 4.2. Hardware implementation of min-sum decoding algorithm 41
• 4.3. Analysis of Δmin 42
• 4.4. Proposed decoding method with experimental results 49
• 4.4.1. Adaptive termination check scheme for efficient LDPC decoders 49
• 4.4.2. Experimental results of termination check skipping 51
• 4.4.3. Error Correction Performance 52
• 4.5. Consideration of hardware implementation of the proposed algorithm 55
• 4.6. Conclusion 58
• 5. Self-Adaptive Scaled Min-Sum Algorithm for LDPC Decoders Based on Delta-Min 59
• 5.1. Introduction 59
• 5.2. Related works 60
• 5.3. Characteristic of Δmin 64
• 5.4. Δmin based self-adaptive MS algorithm 69
• 5.5. Simulation results 72
• 5.6. Conclusion 73
• 6. Simplified 2-Dimensional Scaled Min-Sum Algorithm for LDPC Decoder 74
• 6.1. Introduction 74
• 6.2. Related works 76
• 6.3. Hardware considered 2D scaling factors 78
• 6.4. Simplified 2D scaled min-sum algorithm 81
• 6.4.1. Simplified 2D scaling with Δmin 81
• 6.4.2. Fixed-point implementation 83
• 6.5. Simulation results 84
• 6.5.1. Decoding performance 85
• 6.5.2. Computational complexity 89
• 6.6. Conclusion 90
• 7. Conclusion 92
• References 94
• Appendix 104
• Abstract 114