Polar codes are a class of error-correcting codes that provably achieve the channel capacity with the low-complexity encoding and decoding algorithms. Traditionally, successive-cancellation decoding is widely to decode polar codes. However, the serial nature of SC decoding leads to a long latency for long polar codes. This thesis proposes an improved method for the successive-cancellation decoding of polar codes to reduce the long latency. To avoid computations associated with redundant tree-traversals and syndrome calculations, recursive properties of polar codes are newly exploited in the proposed algorithm. Instead of computing a syndrome vector at every node, some syndrome vectors are directly obtained by recursively decomposing the syndrome vector computed previously. Furthermore, a modified syndrome check rule is proposed to prune unnecessary sub-trees efficiently. Compared to the latest pruning method, the proposed pruning method reduces the latency by 23% for a (2048, 1024) polar code without sacrificing the error-correcting performance. Moreover, the thesis proposes an efficient hardware architecture implementing the proposed SC decoding algorithm. A depth-constraint and a hardware sharing scheme are adopted to increase the hardware efficiency. As a result, the throughput of the polar decoder increases significantly at the cost of small amount of the additional hardware.
극 부호는 오류 정정 부호의 한 종류로 낮은 복잡도의 부호 및 복호 방법으로 채널 용량을 달성한다. 전통적으로, 극 부호를 복호하기 위해서 연속 제거 복호 방법이 널리 사용된다. 하지만 연속 제거 복호의 순차적인 특성은 길이가 긴 극 부호를 복호할 때 긴 복호 지연 시간을 야기한다. 이 학위 논문은 긴 지연 시간을 줄이기 위한 향상된 연속 제거 복호 방법을 제안한다. 불필요한 syndrome 계산과 tree-traversal을 피하기 위해서, 제안한 방법에서는 극 부호의 반복적인 특성이 새롭게 이용되었다. 모든 node마다 syndrome vector를 계산하는 대신, 이전 node에서 이미 계산된 syndrome vector로부터 현재 node의 syndrome vector를 바로 구할 수 있다. 추가적으로, 불필요한 sub-tree를 효율적으로 가지치기 위해서 syndrome check 규칙을 변경하였다. 가장 최근의 가지치기 방법과 비교했을 때, (2048, 1024) 극 부호에 대해서 제안한 가지치기 방법은 오류 정정 성능의 희생 없이 지연 시간을 23% 감소시켰다. 또한 본 논문은 제안한 연속 제거 복호 방법을 구현하는 효율적인 하드웨어 구조를 제안한다. 하드웨어 효율성을 높이기 위해서 깊이 제한 및 하드웨어 공유 기법이 적용되었다. 그 결과, 작은 크기의 하드웨어만을 추가하여 극 부호 복호기의 throughput이 크게 증가하였다.
