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

arXiv:1912.06359

On Pre-transformed Polar Codes

Bin Li, Huazi Zhang, Jiaqi Gu

Published Dec 13, 2019• 33 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1912.06359

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 the Equivalence between Pre-transformed and Parity-check Monomial Codes

Yuanxin Guo, Zihan Tang, Bin Li

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.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•1 citation

A Pre-Transformation Method to Increase the Minimum Distance of Polar-Like Codes

Samet Gelincik, Philippe Mary, Anne Savard +1 more

Reed Muller (RM) codes are known for their good minimum distance. One can use their structure to construct polar-like codes with good distance properties by choosing the information set as the rows of the polarization matrix with the highest Hamming weight, instead of the most reliable synthetic channels. However, the information length options of RM codes are quite limited due to their specific structure. In this work, we present sufficient conditions to increase the information length by at least one bit for some underlying RM codes and in order to obtain pre-transformed polar-like codes with the same minimum distance than lower rate codes.The proofs give a constructive method to choose the row triples to be merged together to increase the information length of the code and they follow from partitioning the row indices of the polar encoding matrix with respect to the recursive structure imposed by the binary representation of row indices. Moreover, our findings are combined with the method presented in [2] to further reduce the number of minimum weight codewords. Numerical results show that the designed codes perform close to the meta-converse bound at short blocklengths and better than the polarization-adjusted-convolutional polar codes with the same parameters.

arXiv:2202.04366•Feb 9, 2022•3 citations

On the Minimum Weight Codewords of PAC Codes: The Impact of Pre-Transformation

Mohammad Rowshan, Jinhong Yuan

The minimum Hamming distance of a linear block code is the smallest number of bit changes required to transform one valid codeword into another. The code’s minimum distance determines the code’s error-correcting capabilities. Furthermore, The number of minimum weight codewords, a.k.a. error coefficient, gives a good comparative measure for the block error rate (BLER) of linear block codes with identical minimum distance, in particular at a high SNR regime under maximum likelihood (ML) decoding. A code with a smaller error coefficient would give a lower BLER. Unlike polar codes, a closed-form expression for the enumeration of the error coefficient of polarization-adjusted convolutional (PAC) codes is yet unknown. As PAC codes are convolutionally pre-transformed polar codes, we study the impact of pre-transformation on polar codes in terms of minimum Hamming distance and error coefficient by partitioning the codewords into cosets. We show that the minimum distance of PAC codes does not decrease; however, the pre-transformation may reduce the error coefficient depending on the choice of convolutional polynomial. We recognize the properties of the cosets where pre-transformation is ineffective in decreasing the error coefficient, giving a lower bound for the error coefficient. Then, we propose a low-complexity enumeration method that determines the number of minimum weight codewords of PAC codes relying on the error coefficient of polar codes. That is, given the error coefficient Awmin of polar codes, we determine the reduction X in the error coefficient due to convolutional pre-transformation in PAC coding and subtract it from the error coefficient of polar codes, Awmin - X. Furthermore, we numerically analyze the tightness of the lower bound and the impact of the choice of the convolutional polynomial on the error coefficient based on the sub-patterns in the polynomial’s coefficients. Eventually, we show how we can further reduce the error coefficient in the cosets.

IEEE Journal on Selected Areas in Information Theory•Jan 1, 2023•22 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

Preserving the Minimum Distance of Polar-Like Codes while Increasing the Information Length

Samet Gelincik, Philippe Mary, Anne Savard +1 more

Reed Muller (RM) codes are known for their good minimum distance. One can use their structure to construct polar-like codes with good distance properties by choosing the information set as the rows of the polarization matrix with the highest Hamming weight, instead of the most reliable synthetic channels. However, the information length options of RM codes are quite limited due to their specific structure. In this work, we present sufficient conditions to increase the information length by at least one bit for some underlying RM codes and in order to obtain pre-transformed polar-like codes with the same minimum distance than lower rate codes. Moreover, our findings are combined with the method presented in [1] to further reduce the number of minimum weight codewords. Numerical results show that the designed codes perform close to the meta-converse bound at short blocklengths and better than the polarized adjusted convolutional polar codes with the same parameters.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•1 citation
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.
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.
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.
Reed Muller (RM) codes are known for their good minimum distance. One can use their structure to construct polar-like codes with good distance properties by choosing the information set as the rows of the polarization matrix with the highest Hamming weight, instead of the most reliable synthetic channels. However, the information length options of RM codes are quite limited due to their specific structure. In this work, we present sufficient conditions to increase the information length by at least one bit for some underlying RM codes and in order to obtain pre-transformed polar-like codes with the same minimum distance than lower rate codes.The proofs give a constructive method to choose the row triples to be merged together to increase the information length of the code and they follow from partitioning the row indices of the polar encoding matrix with respect to the recursive structure imposed by the binary representation of row indices. Moreover, our findings are combined with the method presented in [2] to further reduce the number of minimum weight codewords. Numerical results show that the designed codes perform close to the meta-converse bound at short blocklengths and better than the polarization-adjusted-convolutional polar codes with the same parameters.
The minimum Hamming distance of a linear block code is the smallest number of bit changes required to transform one valid codeword into another. The code’s minimum distance determines the code’s error-correcting capabilities. Furthermore, The number of minimum weight codewords, a.k.a. error coefficient, gives a good comparative measure for the block error rate (BLER) of linear block codes with identical minimum distance, in particular at a high SNR regime under maximum likelihood (ML) decoding. A code with a smaller error coefficient would give a lower BLER. Unlike polar codes, a closed-form expression for the enumeration of the error coefficient of polarization-adjusted convolutional (PAC) codes is yet unknown. As PAC codes are convolutionally pre-transformed polar codes, we study the impact of pre-transformation on polar codes in terms of minimum Hamming distance and error coefficient by partitioning the codewords into cosets. We show that the minimum distance of PAC codes does not decrease; however, the pre-transformation may reduce the error coefficient depending on the choice of convolutional polynomial. We recognize the properties of the cosets where pre-transformation is ineffective in decreasing the error coefficient, giving a lower bound for the error coefficient. Then, we propose a low-complexity enumeration method that determines the number of minimum weight codewords of PAC codes relying on the error coefficient of polar codes. That is, given the error coefficient Awmin of polar codes, we determine the reduction X in the error coefficient due to convolutional pre-transformation in PAC coding and subtract it from the error coefficient of polar codes, Awmin - X. Furthermore, we numerically analyze the tightness of the lower bound and the impact of the choice of the convolutional polynomial on the error coefficient based on the sub-patterns in the polynomial’s coefficients. Eventually, we show how we can further reduce the error coefficient in the cosets.
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.
Reed Muller (RM) codes are known for their good minimum distance. One can use their structure to construct polar-like codes with good distance properties by choosing the information set as the rows of the polarization matrix with the highest Hamming weight, instead of the most reliable synthetic channels. However, the information length options of RM codes are quite limited due to their specific structure. In this work, we present sufficient conditions to increase the information length by at least one bit for some underlying RM codes and in order to obtain pre-transformed polar-like codes with the same minimum distance than lower rate codes. Moreover, our findings are combined with the method presented in [1] to further reduce the number of minimum weight codewords. Numerical results show that the designed codes perform close to the meta-converse bound at short blocklengths and better than the polarized adjusted convolutional polar codes with the same parameters.