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.

Polar codes can be viewed as decreasing monomial codes, revealing a rich algebraic structure governed by the lower-triangular affine (LTA) group. We develop a general framework to compute the Hamming weight of codewords generated by sums of monomials, express these weights in a canonical dyadic form, and derive closed expressions for key structural templates (disjoint sums, nested blocks, complementary flips) that generate the low and intermediate weight spectrum. Combining these templates with the LTA group action, we obtain explicit multiplicity formulas, yielding a unified algebraic method to characterize and enumerate codewords.

In this article, we provide a characterization of Type-I codewords with weight less than twice the minimum distance of polar codes, based on the action of the lower triangular affine group. We present a closed-form formula for the enumeration of such codewords. In addition, we propose an improved weight contribution partial order.

Polar codes are constructed based on the reliability of sub-channels resulting from the polarization effect. However, this information-theoretic construction approach leads to a poor weight distribution. To address this issue, pre-transformed polar codes, such as CRC-polar codes and PAC codes, have been employed. In this paper, we focus on the structure of polar codes without applying any pre-transformations and explore methods, guided by the weight-contribution partial order, to design polarlike codes with enhanced weight distribution, notably without employing any search or optimization algorithms. Numerical results demonstrate improvement over a range of codes both with and without pre-transformation.

The structure of a linear block code is pivotal in defining fundamental properties, particularly weight distribution, and code design. In this study, we characterize the Type II structure of polar codewords with weights less than twice the minimum weight wmin, using the lower triangular affine (LTA) transform. We present a closed-form formula for their enumeration. Leveraging this structure and additionally characterizing the structure of weight 2wmin, we ascertain the complete weight distribution of low-rate polar codes (with minimum distance dmin= 2m−2where code-length is 2m) and, through the utilization of dual codes properties, high-rate polar codes, subcodes of Reed–Muller (RM) codes, and RM–Polar codes. Furthermore, we introduce a new partial order based on the weight distribution and explore its properties and applications in code construction and analysis.

The structure of a linear block code is pivotal in defining fundamental properties, particularly weight distribution, and code design. In this study, we characterize the Type II structure of polar codewords with weights less than twice the minimum weight Wmin, utilizing the lower triangular affine (LTA) transform. We present a closed-form formula for their enumer-ation. Leveraging this structure and additionally characterizing the structure of weight 2 Wmin, we ascertain the complete weight distribution of low-rate and, through the utilization of dual codes properties, high-rate polar codes, subcodes of Reed-Muller (RM) codes, and RMxPolar codes. Furthermore, we introduce a partial order based on the weight distribution and briefly explore its properties and applications in code construction and analysis.

The weight distribution of an error correction code is a critical determinant of its error-correcting performance. In the case of polar codes, the minimum weight wmin(equal to the minimum distanced) is the only weight for which an explicit enumerator formula is currently available. Having closed-form weight enumerators for polar codewords with weights greater than the minimum weight not only simplifies the enumeration process but also provides valuable insights towards constructing better polar-like codes. In this paper, we contribute towards understanding the algebraic structure underlying higher weights by analyzing Minkowski sums of orbits. Our approach builds upon the lower triangular affine (LTA) group of decreasing monomial codes. Specifically, we propose a closed-form expression for the enumeration of codewords with weight 1.5wmin. The key insight for code design is that the enumeration of codewords with weight wmin and 1.5wminrelies on the set of maximum degree monomials. This set corresponds to the indices of minimum weight rows of the polar transformGNbelonging to the information setI. Consequently, reducing the cardinality of this set can lead to a reduction of the number of codewords in both weight categories.

Consecutive-$k$-out-of-$n$:F systems are one of the most well-studied types of networks when discussing reliability. They have been used from safety–critical environments, such as nuclear power plants or hospital's emergency backup power supplies, to classical transportation problems, such as public water systems and oil/gas pipelines. Exact formulae for the reliability polynomial of a consecutive system are known for quite a long time. In addition, several alternatives for computing exactly the reliability polynomial are also known. However, when dealing with large consecutive systems, exact calculations become prohibitive and approximations/bounds are the common route. We begin this article by providing an in-depth review of many known bounds. Next, we focus on the coefficients of the reliability polynomial of a consecutive system in its Bernstein form. By deriving shape properties of these coefficients, we are able to identify new bounds. Our approach is uncommon for this case, as none of the previously used bounding techniques has looked closely at each and every coefficient. This is probably the reason why we obtain tight bounds with low complexity costs. Finally, detailed simulations provide strong evidence of the fidelity of the proposed bounds.

We gather existing methods that are used to compare and rank the BECs synthesized by a polar code constructor, compare them, and propose new methods that compare synthetic BECs more quickly.

Abstract This article studies the roots of the reliability polynomials of linear consecutive‐k‐out‐of‐n:Fsystems. We prove that these roots are unbounded in the complex plane, for any fixed . In the particular case , we show that the reliability polynomials have only real roots and highlight the closure of these roots by establishing their explicit formulas. We also point out that in this case, for any fixedn, the nonzero roots of the reliability polynomial are distinct numbers.

The concept of Generalized Inverse Decoding (GID) is introduced, as an algebraic framework for the syndrome decoding (SD) and low-weight codeword (LWC) problems. The framework has ground on two characterizations by generalized inverses, one for the null space of a matrix and the other for the solution space of a system of linear equations over a finite field. Generic GID solvers are proposed for the SD and LWC problems. It is shown that information set decoding (ISD) algorithms, such as Prange, Lee-Brickell, Leon, and Stern’s algorithms, are particular cases of GID solvers. All of them search generalized inverses or elements of the null space under various specific strategies. However, as the paper shows in the case of Prange’s algorithm, they do not search through the entire space, while our solvers do even when they use just one Gaussian elimination. Apart from these, our GID framework clearly shows how each ISD algorithm except for Prange’s can be used as an SD or LWC solver. Experimental results show a very good behavior of the GID solvers. The domain of easy weights can be reached by a very few iterations and even enlarged.

Code-based cryptography received attention after the NIST started the post-quantum cryptography standardization process in 2016. A central NP-hard problem is the binary syndrome decoding problem, on which the security of many code-based cryptosystems lies. The best known methods to solve this problem all stem from the information-set decoding strategy. A recent line of work considers augmented versions of this strategy, with hints provided by side-channel information. In this work, we consider the integer syndrome decoding problem, where the integer syndrome is available but might be noisy. We study how the performance of the decoder is affected by the noise. We provide experimental results on cryptographic parameters for the Classic McEliece and BIKE cryptosystems, which are in the fourth round of the NIST standardization process.

Abstract In this article, we take a closer look at the reliability of large minimal networks constructed by repeated compositions of the simplest possible networks. For a given number of devices we define the set of all the possible compositions of series and parallel networks of two devices. We then define several partial orders over this set and study their properties. As far as we know the ranking problem has not been addressed before in this context, and this article establishes the first results in this direction. The usual approach when dealing with reliability of two‐terminal networks is to determine existence or nonexistence of uniformly most reliable networks. The problem of ranking two‐terminal networks is thus more complex, but by restricting our study to the set of compositions we manage to determine and demonstrate the existence of at least a graded poset.

The NIST standardization process for post-quantum cryptography has been drawing the attention of researchers to the submitted candidates. One direction of research consists in implementing those candidates on embedded systems and that exposes them to physical attacks in return. TheClassic McEliececryptosystem, which is among the four finalists of round 3 in the Key Encapsulation Mechanism category, builds its security on the hardness of the syndrome decoding problem, which is a classic hard problem in code-based cryptography. This cryptosystem was recently targeted by a laser fault injection attack leading to message recovery. Regrettably, the attack setting is very restrictive and it does not tolerate any error in the faulty syndrome. Moreover, it depends on the very strong attacker model of laser fault injection, and does not apply to optimised implementations of the algorithm that make optimal usage of the machine words capacity. In this article, we propose a to change the angle and perform a message-recovery attack that relies on side-channel information only. We improve on the previously published work in several key aspects. First, we show that side-channel information, obtained with power consumption analysis, is sufficient to obtain an integer syndrome, as required by the attack framework. This is done by leveraging classic machine learning techniques that recover the Hamming weight information very accurately. Second, we put forward a computationally-efficient method, based on a simple dot product and information-set decoding algorithms, to recover the message from the, possibly inaccurate, recovered integer syndrome. Finally, we present a masking countermeasure against the proposed attack.

In this article, two new techniques of approximation of the reliability of a two-terminal network are developed based on the constructive theory of functions and related methods. Two methods of generating an approximation cubic spline are used: Lagrange-type interpolation procedures and Bernstein approximation operator. A possibility of minimizing the total error of approximation, based on keeping some properties invariant, is described in case of a large class of pairs of dual two-terminal networks. Simulations are included, showing that the error of approximation is negligible in case of some special initial data.

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.