SC List-Flip Decoding of Polar Codes by Shifted Pruning: A General Approach

Area of Science:

• Coding Theory
• Information Theory
• Digital Communications

Background:

• Successive Cancellation (SC) list decoding uses tree pruning, retaining the L best paths.
• The correct decoding path can be erroneously pruned due to imposed penalties, leading to decoding failure.
• Shifted pruning (SP) schemes, including SCL-flip decoding, attempt to recover the correct path by shifting the pruning window.

Purpose of the Study:

• To propose a novel metric for SC list decoding that enhances performance, particularly for medium and long codes.
• To introduce nested shifted pruning schemes to improve the average complexity of the decoding process.
• To address the limitations of standard tree pruning in SC list decoding where the correct path may be discarded.

Main Methods:

• Development of a new performance metric for path selection in SC list decoding.
• Introduction and analysis of nested shifted pruning schemes.
• Evaluation of the proposed metric and schemes, particularly for medium and long code lengths.

Main Results:

• The proposed new metric demonstrates improved performance for medium and long codes compared to existing metrics.
• Nested shifted pruning schemes are suggested to optimize average decoding complexity.
• The study addresses scenarios where the correct path might be among the L worst paths, leading to failure in standard SC list decoding.

Conclusions:

• The novel metric and nested shifted pruning schemes offer a significant improvement for successive cancellation list decoding.
• These advancements enhance the reliability and efficiency of error correction codes, especially for longer data sequences.
• The proposed techniques mitigate the risk of decoding failure caused by aggressive tree pruning.