Papers › List Decoding of Polar Codes
List Decoding of Polar Codes
Ido Tal, Alexander Vardy
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We describe a successive-cancellation \emph{list} decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Ar{\i}kan. In the proposed list decoder, up to L decoding paths are considered concurrently at each decoding stage. Then, a single codeword is selected from the list as output. If the most likely codeword is selected, simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of L. Alternatively, if a "genie" is allowed to pick the codeword from the list, the results are comparable to the current state of the art LDPC codes. Luckily, implementing such a helpful genie is easy. Our list decoder doubles the number of decoding paths at each decoding step, and then uses a pruning procedure to discard all but the L "best" paths. %In order to implement this algorithm, we introduce a natural pruning criterion that can be easily evaluated. Nevertheless, a straightforward implementation still requires Ω(L ·n²) time, which is in stark contrast with the O(n logn) complexity of the original successive-cancellation decoder. We utilize the structure of polar codes to overcome this problem. Specifically, we devise an efficient, numerically stable, implementation taking only O(L ·n logn) time and O(L ·n) space.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections