List Sphere Decoding of Polar Codes

Polar codes have gained a lot of attention during the past few years, because they can provably achieve the capacity of a memoryless channel. The design of efficient polar code decoders has been an active topic of research. The simple Successive Cancellation (SC) decoding algorithm yields poor error correction performance on short polar codes: the SC-List (SCL) algorithm overcomes this problem, but its hardware implementation requires a large amount of memory. Sphere Decoding (SD) is an alternative decoding technique that has been shown to work well for short polar codes, but it is burdened by undesirable characteristics. The performance of SD strongly depends on the choice of a suitable sphere radius, whose value must be selected according to the conditions of the channel. Channel conditions also affect the algorithm's time complexity, that is consequently variable. In this paper, we introduce a List-SD algorithm for short polar codes. It has a fixed time complexity and does not make use of a radius: thus, no knowledge of the channel noise level is required. It is shown that the error correction performance of List-SD can match that of SC and SCL with as low as 72% of their memory requirements.