비이진 LDPC 부호를 위한 저복잡도 다중투표 심볼반전 복호 알고리즘

MasterLDPC 부호는 1962년에 Gallager에 의해 제안되었으나, 높은 복잡도로 인해 많은 관심을 받지는 못했다. 하지만 최근에 컴퓨팅 기술이 발달함에 따라 다시 많은 사람들의 관심을 받고 있다. 따라서 이진 LDPC 부호의 설계, 디코딩, 성능 분석 등 활발한 연구가 진행되어왔다. 이진 LDPC 부호가 Shannon의 채널 용량에 근접 하기 위해서는 부호의 길이가 길어야 한다. 그러나 비이진 유한체 GF(q)에서 LDPC 부호를 설계할 경우, 비교적 작은 길이에서 이진 LDPC 부호보다 우수한 성능을 가진다. GF(q) 상의 비이진 LDPC 부호는 한번에 2개가 아니라 q개의 메시지를 계산하고 전송 하다보니 이진 LDPC보다 복호하는데 훨씬 복잡해서 실제 시스템에 적용하기에는 많은 어려움이 있다. 비이진 LDPC 부호의 대표적인 복호 알고리즘은 q진 합곱 알고리즘(q-ary sum-product algorithm, QSPA)이다. 하지만 이 복호 알고리즘은 높은 복잡도를 가져서 FFT-QSPA가 제안되었다. FFT-QSPA 알고리즘은 QSPA보다 복잡도는 낮지만 여전히 많은 양의 연산이 필요하다. 이를 해결하기 위해서 이진 LDPC 부호에 적용된 최소합 알고리즘을 변형하여 확장된 최소합(extended min-sum, EMS) 알고리즘이 제안되었다. 위의 알고리즘들은 모두 연판정 복호 알고리즘이어서 계산량이 복잡하다는 단점이 있다. 그래서 경판정 복호 알고리즘 방식도 많이 제안되어왔다. 그 중 하나가 이진 LDPC 부호의 가중치 비트 반전 알고리즘을 확장한 가중치 심볼 반전 복호 알고리즘이다. 그리고 다수결 논리 복호 알고리즘 유형의 복호 방식도 제안 되어왔다. 하지만 위의 알고리즘은 가장 신뢰도가 높은 심볼들의 조합으로만 복호에 사용된다는 단점이 있다. 따라서 이를 개선한게 다중 투표 심볼 반전 알고리즘(Multiple-Vote Symbol-Flipping, MVSF) 이다. 본 논문에서는 MVSF 알고리즘에서 두 번째로 신뢰도가 높은 심볼까지 전송하는 변수 노드 개수를 적응적으로 적용한 알고리즘을 제안 하였다. 본 논문의 구성은 다음과 같다. Ⅱ장에서는 이진 LDPC 부호의 기본 기념에 대해 알아본다. Ⅲ장에서는 비이진 LDPC 부호의 기본 개념과 복호 알고리즘에 대해 알아본다. Ⅳ장에서는 기존의 MVSF 알고리즘에 대해 간단히 설명하고 이를 개선한 알고리즘을 제시한다. 마지막으로 Ⅴ장에서는 결론을 제시한다.Low-density parity-check (LDPC) codes have been shown to have near Shannon-limit performance when a probabilistic decoding is used and the code length goes to infinity. On the other hand, non-binary low-density parity-check (NB-LDPC) codes outperform binary LDPC codes for short code lengths. However, computational complexity is higher than binary LDPC codes. Thus, many researchers are developing low-complexity decoding algorithms of NB-LDPC codes. In this thesis, we first introduce the existing decoding algorithms of binary and nonbinary LDPC codes and compare with them. Second, We propose an improved multiple-vote symbol-flipping algorithm to decrease decoding complexity of nonbinary LDPC codes. The proposed algorithm can reduce computational complextiy by adaptively changing the number of variable nodes sending the second most reliable symbol for each check node. The proposed algorithms provide good trade-off between complexity and error performance