Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Turbo Codes and Iterative Information Processing

On the Equivalence between Pre-transformed and Parity-check Monomial Codes

Yuanxin Guo, Zihan Tang, Bin Li

Published Aug 30, 2021• 1 citation
Publisher

Abstract

Polar codes and Reed-Muller codes belong to a family of codes called monomial codes. In this work, we study pre-transformed monomial codes, which cover several constructions including parity-check (PC) codes and PAC codes. We show that any pre-transformed monomial code can be transformed into a parity-check monomial code with the same codewords, and give an explicit algorithm for this transformation. We further prove that for certain monomial codes, the minimum weight is invariant under pre-transformation, but specific pre-transformation matrices can be constructed to reduce the number of minimum-weight codewords. These results offer theoretical support for the success of various heuristics, e.g., PAC codes attain dispersion bound, and provide guidance for designing short codes.

DOI
10.1109/istc49272.2021.9594246

Related papers

On the Weight Spectrum Improvement of Pre-transformed Reed-Muller Codes and Polar Codes

Yuan Li, Zicheng Ye, Huazi Zhang +3 more

Pre-transformation with an upper-triangular matrix (including cyclic redundancy check (CRC), parity-check (PC) and polarization-adjusted convolutional (PAC) codes) improves the weight spectrum of Reed-Muller (RM) codes and polar codes significantly. However, a theoretical analysis to quantify the improvement is missing. In this paper, we provide asymptotic analysis on the number of low-weight codewords of the original and pre-transformed RM codes respectively, and prove that pre-transformation significantly reduces low-weight codewords, even in the order sense. For polar codes, we prove that the average number of minimum-weight codewords does not increase after pre-transformation. Both results confirm the advantages of pre-transformation.

arXiv:2307.06599•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•8 citations

On Pre-transformed Polar Codes

Bin Li, Huazi Zhang, Jiaqi Gu

In this paper, we prove that any pre-transformation with an upper-triangular matrix (including cyclic redundancy check (CRC), parity-check (PC) and convolution code (CC) matrix) does not reduce the code minimum distance and an properly designed pre-transformation can reduce the number of codewords with the minimum distance. This explains that the pre-transformed polar codes can perform better than the Polar/RM codes.

arXiv:1912.06359•Dec 13, 2019•33 citations

Parity-Check Polarization-Adjusted Convolutional Coding

Qingping Yu, You ZHANG, Renze Luo +2 more

Polarization-adjusted convolutional (PAC) codes have better error-correcting performance than polar codes mostly because of the improved weight distribution brought by the convolutional pre-transformation. In this paper, we propose the parity check PAC (PC-PAC) codes to further improve error-correcting performance of PAC codes. The design principle is to establish parity check functions between bits with distinct row weights, such that information bits of lower reliability are re-protected by the PC relation. Moreover, an algorithm to select which bits to be involved in parity-check functions is also proposed to make sure that the constructed codes have fewer minimum-weight codewords. Simulation results show that the proposed PC-PAC codes can achieve nearly 0.2dB gain over PAC codes at frame error rate (FER) about 10-3 codes.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 26, 2023•2 citations

Algebraic Properties of PAC Codes

Vlad Drăgoi, Mohammad Rowshan

We analyze polarization-adjusted convolutional codes using the algebraic representation of polar and Reed-Muller codes. We define a large class of codes, called generalized polynomial polar codes which include PAC codes and Reverse PAC codes. We derive structural properties of generalized polynomial polar codes, such as duality, minimum distance. We also deduce some structural limits in terms of number of minimum weight codewords, and dimension of monomial sub-code.

arXiv:2601.10262•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•1 citation

Algebraic properties of polar codes from a new polynomial formalism

Magali Bardet, Vlad Drăgoi, Ayoub Otmani +1 more

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.

arXiv:1601.06215•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•155 citations

Enumeration of Minimum Weight Codewords of Pre-Transformed Polar Codes by Tree Intersection

Andreas Zunker, Marvin Geiselhart, Stephan ten Brink

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.

arXiv:2311.17774•Conference on Information Sciences and Systems•Mar 13, 2024•13 citations
Polar codes and Reed-Muller codes belong to a family of codes called monomial codes. In this work, we study pre-transformed monomial codes, which cover several constructions including parity-check (PC) codes and PAC codes. We show that any pre-transformed monomial code can be transformed into a parity-check monomial code with the same codewords, and give an explicit algorithm for this transformation. We further prove that for certain monomial codes, the minimum weight is invariant under pre-transformation, but specific pre-transformation matrices can be constructed to reduce the number of minimum-weight codewords. These results offer theoretical support for the success of various heuristics, e.g., PAC codes attain dispersion bound, and provide guidance for designing short codes.
Pre-transformation with an upper-triangular matrix (including cyclic redundancy check (CRC), parity-check (PC) and polarization-adjusted convolutional (PAC) codes) improves the weight spectrum of Reed-Muller (RM) codes and polar codes significantly. However, a theoretical analysis to quantify the improvement is missing. In this paper, we provide asymptotic analysis on the number of low-weight codewords of the original and pre-transformed RM codes respectively, and prove that pre-transformation significantly reduces low-weight codewords, even in the order sense. For polar codes, we prove that the average number of minimum-weight codewords does not increase after pre-transformation. Both results confirm the advantages of pre-transformation.
Polarization-adjusted convolutional (PAC) codes have better error-correcting performance than polar codes mostly because of the improved weight distribution brought by the convolutional pre-transformation. In this paper, we propose the parity check PAC (PC-PAC) codes to further improve error-correcting performance of PAC codes. The design principle is to establish parity check functions between bits with distinct row weights, such that information bits of lower reliability are re-protected by the PC relation. Moreover, an algorithm to select which bits to be involved in parity-check functions is also proposed to make sure that the constructed codes have fewer minimum-weight codewords. Simulation results show that the proposed PC-PAC codes can achieve nearly 0.2dB gain over PAC codes at frame error rate (FER) about 10-3 codes.
Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.
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.