Low-Complexity Soft-Output Decoding of Polar Codes

The state-of-the-art soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper, we propose a low-complexity alternative for soft-output decoding of polar codes that offers better performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is only 4% of the total complexity of the belief propagation decoder for a rate one-half polar code of dimension 4096 in the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.

I. Introduction

THE ERROR correcting code in a magnetic recording application must meet stringent error-floor and throughput requirements at a relatively large block length; the sector size for hard disk drives is typically 32768 bits, and the throughput can be 2 Gb/s or more. Regularity in the structure of the encoder/decoder facilitates hardware implementation by reducing interconnect congestion and processing requirements [1]. There has been significant research into finding regularly structured codes. For example, to avoid the high complexity of the early low-density parity check (LDPC) codes, which were random, different structured codes such as quasi-cyclic LDPC codes [2] emerged after their rediscovery in [3] and secured their place in different standards such as IEEE802.11n [4] and IEEE 802.16e [5].