Improved Belief Propagation Algorithm and its Hardware Architecture for Short Polar Codes

Abstract

This thesis has its focus on two topics: 1. Improvement of performance of polar codes using belief propagation (BP) decoding method, and 2. its hardware architecture. Polar codes were first introduced by Arikan [1] and are known for theoretically achieving Shannon’s capacity for discrete memory-less channels. The encoder and decoder for polar codes can be implemented with a complexity of O(NlogN)[1], where N is the code block-length. This complexity can be achieved by using the successive cancellation (SC) decoding algorithm. However, when compared to the other famous coding schemes, like low-density parity-check (LDPC) codes and turbo codes, the performance of polar codes is disappointing in the finite length regime[2], [3]. Thus in the first part of this thesis, we investigate the finite length performance of polar codes, over the additive white Gaussian noise channel (AWGN), while assuming BP decoding as the decoding method. It is suggested to run the BP decoder on the parity check matrix of polar codes. In addition to this, since BP is rather well-studied for LDPC codes, there are many proposed approaches to modify BP in order to obtain better BER performance. Therefore, we proposed a modified version of BP employing damped belief propagation algorithm [4]. Here we show that by modifying this algorithm for polar codes we can achieve significant improvement in BER. The BP algorithm is modified by changing the update equation of the variable nodes. The variable nodes are updated by multiplying them with their previous messages. It is found that the parity-check matrix based tanner graph can be used for the decoding of polar codes, and that the performance of short polar codes can be improved by 1-2 dB using the proposed BP decoder, while keeping the complexity of the original BP decoder. Furthermore, we show that the proposed decoder requires about 10-25 iterations less than the standard BP decoder. The second part of this thesis is devoted to the hardware architecture of polar codes, in which we discuss the various hardware architectures available for polar codes. We also provide the details of the hardware architecture based on the proposed BP decoder. |이 논문은 두 가지 주제에 관해 초점을 가지고 있다. 1. BP 복호 방법을 이용한 극 부호의 성능 개선, 2. 극 부호의 하드웨어 구조이다. 극 부호는 처음 Arikan에 의해 도입 된 것으로, 개별 메모리 없는 채널에서 Shannon 용량에 이론적으로 근접한다고 알려진다. 극 부호에 대한 부호기와 복호기 복잡도는 O(NlogN)로 구현된다. 여기서, N은 부호의 블록 길이이다. 이러한 복잡도는 연속 소거(SC) 복호 알고리즘을 사용함으로써 구현 될 수 있습니다. 저밀도 패리티-체크(LDPC)코드, 터보 부호와 같이 다른 유명한 코딩 형태와 비교할 때, 극 후보의 성능은 유한한 길이에서 실망스럽다. 그래서, 본 논문의 첫 번째 부분에서는, 백색 가우시안 잡음 채널(AWGN)상에 극 부호의 유한한 길이의 성능을 조사한다. 여기서, 복호 방식으로 BP 복호를 가정한다. BP코드는 LDPC코드에 비해 잘 연구되어 있고 더 나은 BER성능을 얻기 위해서는 BP를 수정하는 많은 제안들이 있습니다. 따라서 BP 논의 감쇠 신뢰도 전달 알고리즘을 이용하여 수정 한 버전을 제안합니다. 다음은 코드에 대한 극성이 알고리즘을 수정하여 우리가 BER에서 상당한 개선을 있음을 보여 줍니다. BP알고리즘은 변수 노드의 이전 메시지와 함께 그것들을 변수 노드의 갱신 방정식을 변경하여 수정됩니다다. 이 패리티 검사는 행렬을 기반으로 태너 그래프 극 부호의 복호를 위해 사용될 수 있다는 것을 알 수 있고, 복잡성을 유지하면서 짧은 극 부호의 성능이 본 논문에서 제안하고 있는 BP 디코더를 사용함으로써 1-2db 정도 개선 될 수 있다는 것입니다. 제안하는 복호는 표준 약 10~25번의 반복을 덜어 줍니다. 이 논문의 두번째 부분은 극 부호에 사용할 수 있는 다양한 하드웨어 구조를 다루며. 저희가 제안한 BP디코더를 기반으로 하드웨어 구조의 세부사항을 제공합니다.