Pre-transformed polar codes (PTPCs) form a class of codes that perform close to the finite-length capacity bounds. The minimum distance and the number of minimum weight codewords are two decisive properties for their performance. In this work, we propose an efficient algorithm for determining the number of minimum weight codewords of general PTPCs that eliminates all redundant visits to nodes of the search tree, thus reducing the computational complexity typically by several orders of magnitude compared to state-of-the-art algorithms. This reduction in complexity allows, for the first time, the minimum distance properties to be directly considered in the code design of PTPCs. The algorithm is demonstrated for randomly pre-transformed Reed-Muller (RM) codes and polarization-adjusted convolutional (PAC) codes. Furthermore, we design optimal polynomials for PAC codes with this algorithm, minimizing the number of minimum weight codewords.
Description
Enumeration of Minimum Weight Codewords of Pre-Transformed Polar Codes by Tree Intersection | IEEE Conference Publication | IEEE Xplore
%0 Conference Paper
%1 10480163
%A Zunker, Andreas
%A Geiselhart, Marvin
%A Ten Brink, Stephan
%B 2024 58th Annual Conference on Information Sciences and Systems (CISS)
%D 2024
%K myown
%P 1-6
%R 10.1109/CISS59072.2024.10480163
%T Enumeration of Minimum Weight Codewords of Pre-Transformed Polar Codes by Tree Intersection
%X Pre-transformed polar codes (PTPCs) form a class of codes that perform close to the finite-length capacity bounds. The minimum distance and the number of minimum weight codewords are two decisive properties for their performance. In this work, we propose an efficient algorithm for determining the number of minimum weight codewords of general PTPCs that eliminates all redundant visits to nodes of the search tree, thus reducing the computational complexity typically by several orders of magnitude compared to state-of-the-art algorithms. This reduction in complexity allows, for the first time, the minimum distance properties to be directly considered in the code design of PTPCs. The algorithm is demonstrated for randomly pre-transformed Reed-Muller (RM) codes and polarization-adjusted convolutional (PAC) codes. Furthermore, we design optimal polynomials for PAC codes with this algorithm, minimizing the number of minimum weight codewords.
@inproceedings{10480163,
abstract = {Pre-transformed polar codes (PTPCs) form a class of codes that perform close to the finite-length capacity bounds. The minimum distance and the number of minimum weight codewords are two decisive properties for their performance. In this work, we propose an efficient algorithm for determining the number of minimum weight codewords of general PTPCs that eliminates all redundant visits to nodes of the search tree, thus reducing the computational complexity typically by several orders of magnitude compared to state-of-the-art algorithms. This reduction in complexity allows, for the first time, the minimum distance properties to be directly considered in the code design of PTPCs. The algorithm is demonstrated for randomly pre-transformed Reed-Muller (RM) codes and polarization-adjusted convolutional (PAC) codes. Furthermore, we design optimal polynomials for PAC codes with this algorithm, minimizing the number of minimum weight codewords.},
added-at = {2025-05-14T15:19:51.000+0200},
author = {Zunker, Andreas and Geiselhart, Marvin and Ten Brink, Stephan},
biburl = {https://puma.ub.uni-stuttgart.de/bibtex/2f2e2c7cc09c5c255a2c9bbb31a52a9f2/mgeiselhart},
booktitle = {2024 58th Annual Conference on Information Sciences and Systems (CISS)},
description = {Enumeration of Minimum Weight Codewords of Pre-Transformed Polar Codes by Tree Intersection | IEEE Conference Publication | IEEE Xplore},
doi = {10.1109/CISS59072.2024.10480163},
interhash = {029af214147128b252a0435b7ecd04c0},
intrahash = {f2e2c7cc09c5c255a2c9bbb31a52a9f2},
issn = {2837-178X},
keywords = {myown},
month = {March},
pages = {1-6},
timestamp = {2025-05-14T15:19:51.000+0200},
title = {Enumeration of Minimum Weight Codewords of Pre-Transformed Polar Codes by Tree Intersection},
year = 2024
}
