Energy-proportional polar decoders

Abstract

Polar codes are a class of linear error-correction codes that have received a lot of attention due to their ability to achieve channel capacity in an arbitrary binary discrete memoryless channel (B-DMC) with low-complexity successive-cancellation (SC) decoding. However, practical implementations often require better error-correction performance than what SC decoding provides, particularly at shorter code lengths. As a result, the successivecancellation list (SCL) decoder has become the reference algorithm for many practical applications, such as 3GPP’s next-generation mobile-communication standard (5G). The SCL decoder improves error-correction performance by generating a list of candidate codewords from the noisy received message. However, the hardware implementation of SCL decoder tends to be less energy- and area-efficient than that of a SC decoder. Successive-cancellation flip (SCF) decoder involves multiple decoding trials, where at each additional trial, the decision bit estimated as the least reliable is flipped before resuming the standard SC decoding. The successivecancellation list flip (SCLF) decoder combines the SCL and SCF decoding strategies. Variations of these decoders, such as dynamic successive-cancellation flip (DSCF) and dynamic successive-cancellation list flip (DSCLF), further improve the error-correction performance. Despite their advantages in error correction, the flip decoders (SCF and SCLF) have variable execution times, which can lead to high average execution time and latency. Nevertheless, existing architectural designs demonstrate that flip decoders are more efficient in area and energy requirements compared to the SCL decoder. The contributions of this doctoral study are focused on the design of energy-efficient decoders for polar codes. The flip decoding algorithms based on SCF and their variations can achieve the error-correction performance of the state-of-the-art SCL decoders while resulting in more efficient hardware implementations. However, variable execution time poses a challenge for realization in receivers. This doctoral study proposes mechanisms to improve the execution-time characteristics of flip decoders while minimizing the impact on error-correction performance and hardware resources. Among hardware resources, the primary focus is on the decoder memory, which occupies the largest part of the decoder area. The first contribution of this thesis is the generalized restart mechanism (GRM) for the flip decoder based on SCF. By applying the GRM, a portion of the decoding tree can be skipped. This portion corresponds to parts of the tree to estimate the bit-flipping candidate and all the previous bits in each additional decoding trial. The GRM reduces the average execution time of the DSCF-3 decoder by 26% to 60% without any negative effect on the error-correction performance. The GRM results in approximately 4% of additional memory for this decoder. The second contribution is the modified GRM for flip decoders with fast decoding techniques. Existing fast decoding techniques improve the execution-time characteristics of the flip decoders. Our proposed GRM is designed to be adaptable to these fast decoders. As a result of this combination, the average execution time of the flip decoders is further reduced while maintaining the original error-correction performance. The third contribution is the limited-locations restart mechanism (LLRM) for the list-flip decoder (SCLF and its variations). Applying our proposed GRM to list-flip decoders results in enormous memory overhead. To overcome this issue, the LLRM, a modification of the GRM, is proposed. The probability-based method for selecting restart locations is proposed, which aims to maximize the execution-time reduction while minimizing the memory overhead. The LLRM reduces the average execution time by 10% to 40% when applied to DSCLF-3 decoder. For this decoder, the LLRM requires approximately 2% of additional memory. The LLRM does not modify original error-correction performance. The fourth contribution is the early-termination mechanism for flip decoders. This contribution consists of two mechanisms. First, the early-stopping mechanism is introduced to differentiate undecodable codewords from decodable ones by using our proposed early-stopping metric. If the metric suggests that a codeword is likely undecodable, the decoder attempts a reduced maximum number of trials, much smaller than the initial maximum number of trials. The early-stopping mechanism reduces the average execution time of the DSCF-1 decoder by 22% at the cost of minor error-correction loss of 0.05 dB. Second, the multi-threshold mechanism is proposed. This mechanism restrains the delay of a flip decoder depending on the state of the buffer to prevent overflow. This mechanism is implemented in the system where the channel produces data with a fixed rate. When applied to the DSCF-1 decoder, the multi-threshold mechanism allows to operate in a system with a fixed channel-production rate 1.13 times lower than the rate associated with a single decoding trial. This results in a minor in a minor error-correction loss of 0.06 dB.

Date	29 Nov 2024
Original language	American English
Awarding Institution	École de technologie supérieure
Supervisor	Pascal Giard (Supervisor)