Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes
Polar codes concatenated with a cyclic redundancy check (CRC) code have been selected in the 5G standard with the successive-cancellation list (SCL) of list size L = 8 as the baseline algorithm. Despite providing great error-correction performance, a large list size increases the hardware complexity...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/27/3/309 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850090584377655296 |
|---|---|
| author | Charles Pillet Ilshat Sagitov Alexios Balatsoukas-Stimming Pascal Giard |
| author_facet | Charles Pillet Ilshat Sagitov Alexios Balatsoukas-Stimming Pascal Giard |
| author_sort | Charles Pillet |
| collection | DOAJ |
| description | Polar codes concatenated with a cyclic redundancy check (CRC) code have been selected in the 5G standard with the successive-cancellation list (SCL) of list size L = 8 as the baseline algorithm. Despite providing great error-correction performance, a large list size increases the hardware complexity of the SCL decoder. Alternatively, flip decoding algorithms were proposed to improve the error-correction performance with a low-complexity hardware implementation. The combination of list and flip algorithms, the successive-cancellation list flip (SCLF) and dynamic SCLF (DSCLF) algorithms, provides error-correction performance close to SCL-32 with a list size L = 2 and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>T</mi><mi>max</mi></msub></semantics></math></inline-formula> = 300 maximum additional trials. However, these decoders have a variable execution time, a characteristic that poses a challenge to some practical applications. In this work, we propose a restart mechanism for list–flip algorithms that allows us to skip parts of the decoding computations without affecting the error-correction performance. We show that the restart location cannot realistically be allowed to occur at any location in a codeword as it would lead to an unreasonable memory overhead under DSCLF. Hence, we propose a mechanism where the possible restart locations are limited to a set and propose various construction methods for that set. The construction methods are compared, and the tradeoffs are discussed. For a polar code of length N = 1024 and rate ¼, under DSCLF decoding with a list size L = 2 and a maximum number of trials <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>T</mi><mi>max</mi></msub></semantics></math></inline-formula> = 300, our proposed approach is shown to reduce the average execution time by 41.7% with four restart locations at the cost of approximately 1.5% in memory overhead. |
| format | Article |
| id | doaj-art-79af332e9bff4bfbb2c5b0ed121c926b |
| institution | DOAJ |
| issn | 1099-4300 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj-art-79af332e9bff4bfbb2c5b0ed121c926b2025-08-20T02:42:32ZengMDPI AGEntropy1099-43002025-03-0127330910.3390/e27030309Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar CodesCharles Pillet0Ilshat Sagitov1Alexios Balatsoukas-Stimming2Pascal Giard3LaCIME, Department of Electrical Engineering, École de technologie supérieure (ÉTS), 1100 Notre-Dame St. West, Montréal, QC H3C 1K3, CanadaLaCIME, Department of Electrical Engineering, École de technologie supérieure (ÉTS), 1100 Notre-Dame St. West, Montréal, QC H3C 1K3, CanadaDepartment of Electrical Engineering, Eindhoven University of Technology, Groene Loper 19, 5600 MB Eindhoven, The NetherlandsLaCIME, Department of Electrical Engineering, École de technologie supérieure (ÉTS), 1100 Notre-Dame St. West, Montréal, QC H3C 1K3, CanadaPolar codes concatenated with a cyclic redundancy check (CRC) code have been selected in the 5G standard with the successive-cancellation list (SCL) of list size L = 8 as the baseline algorithm. Despite providing great error-correction performance, a large list size increases the hardware complexity of the SCL decoder. Alternatively, flip decoding algorithms were proposed to improve the error-correction performance with a low-complexity hardware implementation. The combination of list and flip algorithms, the successive-cancellation list flip (SCLF) and dynamic SCLF (DSCLF) algorithms, provides error-correction performance close to SCL-32 with a list size L = 2 and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>T</mi><mi>max</mi></msub></semantics></math></inline-formula> = 300 maximum additional trials. However, these decoders have a variable execution time, a characteristic that poses a challenge to some practical applications. In this work, we propose a restart mechanism for list–flip algorithms that allows us to skip parts of the decoding computations without affecting the error-correction performance. We show that the restart location cannot realistically be allowed to occur at any location in a codeword as it would lead to an unreasonable memory overhead under DSCLF. Hence, we propose a mechanism where the possible restart locations are limited to a set and propose various construction methods for that set. The construction methods are compared, and the tradeoffs are discussed. For a polar code of length N = 1024 and rate ¼, under DSCLF decoding with a list size L = 2 and a maximum number of trials <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>T</mi><mi>max</mi></msub></semantics></math></inline-formula> = 300, our proposed approach is shown to reduce the average execution time by 41.7% with four restart locations at the cost of approximately 1.5% in memory overhead.https://www.mdpi.com/1099-4300/27/3/309polar codesdecodingexecution timecomplexityenergy efficiency |
| spellingShingle | Charles Pillet Ilshat Sagitov Alexios Balatsoukas-Stimming Pascal Giard Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes Entropy polar codes decoding execution time complexity energy efficiency |
| title | Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes |
| title_full | Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes |
| title_fullStr | Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes |
| title_full_unstemmed | Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes |
| title_short | Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes |
| title_sort | restart mechanisms for the successive cancellation list flip decoding of polar codes |
| topic | polar codes decoding execution time complexity energy efficiency |
| url | https://www.mdpi.com/1099-4300/27/3/309 |
| work_keys_str_mv | AT charlespillet restartmechanismsforthesuccessivecancellationlistflipdecodingofpolarcodes AT ilshatsagitov restartmechanismsforthesuccessivecancellationlistflipdecodingofpolarcodes AT alexiosbalatsoukasstimming restartmechanismsforthesuccessivecancellationlistflipdecodingofpolarcodes AT pascalgiard restartmechanismsforthesuccessivecancellationlistflipdecodingofpolarcodes |