High Performance and Low Complexity Decoding Algorithms for Nonbinary LDPC codes

Abstract

Although nonbinary low-density parity-check (LDPC) codes was introduced along with binary LDPC codes, nonbinary LDPC codes did not receive much attention due to its high decoding complexity. However, after several studies have shown that the error correction performance of nonbinary LDPC codes exceeds that of binary LDPC codes, numerous studies have been conducted to overcome their high decoding complexity in recent decades. Based on these studies, many researchers have tried to adopt nonbinary LDPC codes in communication system or data storage. In this dissertation, we have studied both soft-decision and hard-decision based decoding algorithms of nonbinary LDPC codes. For soft-decision based decoding algorithm, we studied the methods that decrease the decoding complexity while maintaining the error rate performance of extended min-sum (EMS) algorithm. Unlike the original EMS algorithm, the proposed selection-based low-cost check node operation decreases decoding complexity by using quick selection algorithm. The experimental results show that the proposed check node operation is faster and achieves even better error rate performance than the original EMS algorithm. On the other hand, for hard-decision based decoding algorithm, we have studied the methods that increase the error correction performance. The iterative pseudo soft reliability-based majority logic decoding (IPSRB-MLGD) algorithm is modified algorithm of iterative hard-reliability based MLGD (IHRB-MLGD) algorithm. The IPSRB-MLGD algorithm utilizes the Hamming distance between hard-decision symbol and other Galois field elements at initialization. The experimental result show that the IPSRB-MLGD algorithm increases error rate performance and reduces average iteration count. For further improvement of IHRB-MLGD algorithm, we also proposed weighted IPSRB-MLGD (WIPSRB-MLGD) algorithm. In the WIPSRB-MLGD algorithm, weighted voting method is applied in IPSRB-MLGD algorithm and check node operation is modified to reduce the amount of computation. As a result, The WIPSRB-MLGD algorithm achieves better error rate performance with less amount of computation|비이진 저밀도 패리티 검사 부호는 이진 저밀도 패리티 검사부호와 함께 소개되었으나, 복호 복잡도가 매우 높아 주목을 받지 못하였다. 하지만 오류정정 성능이 이진 저밀도 패리티 검사 부호를 뛰어 넘는다는 것이 여러 연구들을 통해 밝혀진 후, 최근 수 십년 동안 해당 부호의 복호 알고리즘의 복잡도를 줄이기 위한 수많은 연구들이 진행되었다. 이러한 연구들을 기반으로 비이진 LDPC 부호를 통신 또는 데이터 저장장치에 적용시키고자 하는 연구들 또한 진행되고 있다. 본 학위 논문에서 우리는 비이진 LDPC 부호의 복호 알고리즘의 두 갈래인 경판정 기반 복호 알고리즘과 연판정 기반 복호 알고리즘 모두에 대한 연구를 진행하였다. 우선 연판정 기반 복호 알고리즘을 위한 연구로써 우리는 확장된 최소합 알고리즘의 오류정정 성능은 유지하면서 복호 복잡성을 줄이는 방법을 연구하였다. 기존 확장 최소합 알고리즘에서는 정렬 알고리즘을 사용하는 것과 달리 본 논문에서 제안된 선택 기반 저비용 검사노드 연산 기법은 퀵 선택 알고리즘을 이용하여 복호 복잡도를 줄였다. 실험 결과 제안된 검사노드 연산 기법은 기존의 확장된 최소합 알고리즘보다 뛰어난 오류율 성능을 보이면서 연산 속도는 빨라지는 것을 확인하였다. 한편, 경판정 기반 복호 알고리즘에 대해서 우리는 오류 정정 성능을 높이는 방법에 대해 연구하였다. 우리는 먼저 기존의 대표적인 경판정 복호 알고리즘인 반복 경판정 기반 다수결 알고리즘을 기반으로 반복 유사 연판정 기반 다수결 복호 알고리즘을 제안하였다. 제안한 알고리즘에서는 경판정 심볼과 다른 갈루아 체 원소들의 해밍 거리를 복호 초기화 단계에서 사용하였다. 실험 결과, 제안한 알고리즘은 기존 알고리즘에 비해 오류율 성능이 높으면서 평균 반복 횟수도 적은 것을 확인하였다. 두 번째로 우리는 반복 유사 연판정 기반 다수결 복호 알고리즘을 기반으로 비트 노드 연산의 다수결 투표 과정에 가중치를 도입하고, 신드롬 검사 결과를 기반으로 검사노드 연산양을 줄이는 방법을 제안하였다. 실험 결과 연산 양을 줄임과 동시에 오류율 성능이 개선되는 것을 확인하였다.