On the Non-Approximate Successive Cancellation Decoding of Binary Polar Codes With Medium Kernels

Abstract

Polar codes constructed by large kernels can attain better finite length performance than those originating from Arıkan’s $2\times 2$ kernel. However, the successive cancellation (SC) decoding for these polar codes is impractical even for relatively small kernel size of $m$ because complexity of the kernel computation grows exponentially with $m$ . This research shows when $m>2$ , there exists a large amount of like terms in the kernel computation which yields a ground for facilitating the decoding. By transferring the kernel computation from the probability domain to the likelihood ratio domain ( $l$ -domain), the so- called $l$ -formula method provides an efficient way to combine the like terms in the kernel computation for kernels up to size 11. However, the $l$ -formula method becomes intractable for kernel size beyond 11. To further reduce the computational complexity, this paper proposes a $W$ -formula method which transforms the kernel computation into the probability pair domain ( $W$ -domain). Advanced from the $l$ -domain, the numerator and denominator of the likelihood ratio are considered separately, which eases the restrictions of combining like terms. The $W$ -formula method can combine much more like terms resulting in a significant reduction on the number of sub-formulas for medium kernels ( $m\leq 16$ ). Furthermore, in the $W$ -domain, sub-formulas become regular and there exist many common sub-formulas whose computations can be shared. Being able to handle kernels of size up to 16, we show that the $W$ -formula based SC decoding achieves a significant complexity reduction over the existing non-approximate SC decoding (the $l$ -formula based SC decoding).

Keywords

• Large kernel
• medium kernel
• polar codes
• SC decoding
• W-formula