🔢 mathematics

A Tutorial on Weight Structure of Polar Codes

This tutorial provides an accessible introduction to the algebraic foundations of polar code weight structures by utilizing a monomial-based polynomial formalism to characterize and enumerate low-weight codewords through affine automorphisms and orbit-based descriptions.

Original authors: Mohamamd Rowshan, Vlad-Florin Dragoi

Published 2026-08-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohamamd Rowshan, Vlad-Florin Dragoi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the invisible architecture of modern communication, where data streams across satellites, undersea cables, and cell towers, there exists a constant battle against noise. To keep a message clear, engineers wrap information in protective layers called error-correcting codes. These codes add redundant bits to a message, allowing the receiver to detect and fix errors caused by interference without asking for a retransmission. Among the most powerful of these tools are polar codes, a relatively new invention that has become a standard for 5G wireless networks. They work by splitting a communication channel into many smaller, virtual channels, some of which are nearly perfect and others that are hopelessly noisy. The code sends the actual message only through the perfect channels, leaving the noisy ones empty. However, to design the most efficient version of these codes, engineers need to understand their internal structure with extreme precision. Specifically, they need to know exactly how many "weak" messages exist within the code—messages that are so close to being corrupted that the receiver might mistake one for another. This is a question of weight: how many bits in a valid message are actually turned on, and how many of these low-weight messages are there?

A recent tutorial by researchers Mohammad Rowshan and Vlad-Florin Drăgoi offers a clear map to this complex landscape. Rather than introducing a new invention, their work acts as a guidebook, organizing the scattered mathematical insights about polar codes into a single, understandable framework. They focus on a specific property of these codes: their weight structure. In simple terms, every valid message in a polar code can be thought of as a unique pattern of zeros and ones. Some patterns are very sparse, containing only a few ones, while others are dense. The sparse patterns are the most dangerous because they are easily confused with a completely empty message or with each other. The researchers explain that these codes, along with a related family called Reed-Muller codes, can be described using a system of algebraic building blocks called monomials. Think of these monomials not as abstract symbols, but as fundamental switches that can be flipped on or off to construct the entire code. By arranging these switches in a specific order, the researchers show that the entire code can be viewed as a collection of decreasing patterns, where the rules for building the code are strictly defined by the order of these switches.

The core of the researchers' explanation lies in how these codes behave when their underlying variables are shifted or transformed. They describe a set of rules, known as affine transformations, which act like a rigid set of moves that can rearrange the positions of the bits without breaking the code's fundamental structure. When these moves are applied to a specific building block, they generate a family of related patterns called an orbit. The researchers demonstrate that the most dangerous, low-weight messages in the code are found within these orbits. They break down the problem into two main categories. The first category involves messages formed by combining two of these orbits. The second involves combining three or more. By carefully counting how these orbits overlap and interact, the authors provide a method to calculate exactly how many messages of a specific weight exist. For instance, they show how to determine the number of messages that are just slightly heavier than the absolute minimum possible weight, a calculation that was previously difficult or required complex simulations.

What makes this work particularly valuable is its ability to turn a chaotic counting problem into a systematic process. The researchers show that for a code of a certain size, the number of these weak messages can be calculated using a specific formula based on the geometry of the orbits. They illustrate this with concrete examples, such as a code with a length of 64 bits. In this specific case, they calculate that there are 920 messages with the minimum possible weight of 8 bits. They then show that there are 25,472 messages with a weight of 12 bits, and 32,768 messages with a weight of 14 bits. These numbers are not guesses; they are derived from the algebraic rules governing the code's construction. The authors also explain how these methods apply when parts of the code are shortened or removed, a common practice in real-world applications to fit data into specific packet sizes. They show that even when bits are removed, the underlying algebraic structure allows for precise predictions of how the number of weak messages changes.

The paper does not claim to have solved every problem in the field. The authors are careful to note that while they have provided closed-form formulas for messages with weights up to twice the minimum distance, calculating the exact number of messages with even higher weights remains a challenge, especially for codes with different rates. They also point out that their current formulas apply to the basic structure of polar codes and do not yet cover more complex, pre-transformed versions used in advanced systems. However, by providing a unified language and a clear roadmap, this tutorial prepares engineers and researchers to tackle these harder problems. It transforms the weight distribution of polar codes from a black box of complex computations into a transparent system where the number of weak messages can be understood, counted, and ultimately optimized. This clarity is essential for the next generation of communication systems, where every bit of efficiency counts.

Technical Summary: A Tutorial on Weight Structure of Polar Codes

Problem Statement

The weight distribution of polar codes and Reed–Muller (RM) codes is a critical factor in determining their error correction performance, particularly for short to moderate block lengths. While recent research has successfully characterized the minimum-weight codewords and those with weights up to $2w_{min}$ using algebraic methods, the literature remains fragmented. Existing approaches often rely on high computational complexity, and the theoretical underpinnings—specifically the relationship between monomial structures, affine automorphisms, and low-weight codeword enumeration—are not always presented in a unified, accessible manner. Furthermore, closed-form enumeration for weights beyond $2w_{min}$ and for pre-transformed polar codes (e.g., CRC-polar, PAC) remains an open challenge.

Methodology

The paper adopts a monomial-based polynomial formalism to analyze the algebraic foundations of polar and RM codes. The methodology proceeds through the following logical steps:

Polynomial Representation: The authors map binary codewords to polynomials over the field $\mathbb{F}_2[x_0, \dots, x_{m-1}] / \langle x_i^2 - x_i \rangle$ . In this framework, codewords are generated by evaluating polynomials at all points in $\mathbb{F}_2^m$ .
Decreasing Monomial Codes: Both Polar and RM codes are unified under the class of Decreasing Monomial Codes. These are defined by a generating set of monomials that satisfies a specific partial order relation ( $\preceq$ ), known as the universal partial order, which is invariant under the action of the Lower Triangular Affine (LTA) group.
Orbit-Based Analysis: The core of the methodology utilizes the action of the LTA( $m, 2$ ) group (a subgroup of the affine automorphism group) on monomials. The authors define orbits as the set of images of a monomial under LTA transformations. Since LTA transformations preserve Hamming weight, the weight distribution can be analyzed by counting the sizes of these orbits.
Classification of Low-Weight Codewords: The paper categorizes codewords with weights below $2w_{min}$ $2 w_{min}$ into two distinct types based on the sum of orbits:
- Type-I: Codewords formed by the sum of two minimum-weight orbits ( $LTA \cdot f + LTA \cdot g$ ). The weight is determined by the number of common linear forms between the transformed polynomials.
- Type-II: Codewords formed by the sum of $\mu$ minimum-weight orbits, where $\mu \geq 2$ . These involve more complex interactions and potential collisions in the polynomial sums.
Recursive and Coset-Based Enumeration: For weights beyond the low-weight regime or for shortened codes, the paper employs recursive techniques based on the polar transform structure. This involves decomposing the code into cosets and utilizing the Weight Enumerating Function (WEF) as a product of sub-coset WEFs.

Key Contributions

The paper does not claim to derive new theoretical theorems but rather provides a unified exposition of recent advances. Its primary contributions include:

Unified Framework: It establishes a clear connection between Polar and RM codes as Decreasing Monomial Codes, facilitating a systematic characterization of their weight structures.
Systematic Enumeration of Low-Weight Codewords:
- It details the derivation of closed-form formulae for the number of minimum-weight codewords ( $w_{min}$ ) based on the cardinality of LTA orbits acting on maximum-degree monomials.
- It extends this to Type-I codewords (weights in $[1.5w_{min}, 2w_{min})$ ) by analyzing the intersection of two orbits, providing specific counting formulae for sub-cases (A1, A2, B1) based on the shared factors of the generating monomials.
- It outlines the structure and counting for Type-II codewords (sums of multiple orbits), addressing collision phenomena in the addition of degree-2 polynomials.
Handling Shortened Codes: The paper explains how to adapt the orbit-based enumeration for shortened polar codes by imposing constraints on the translation vectors and matrix entries to ensure the codewords evaluate to zero on the shortened coordinates.
Recursive Weight Structure: It provides a high-level overview of recursive algorithms for computing the full weight spectrum via coset decomposition, illustrating the process with concrete examples.
Accessibility and Reproducibility: The tutorial includes illustrative examples (e.g., for a (64, 32) polar code), Hasse diagrams for monomial ordering, and references to open-source code to help readers reproduce results and build familiarity with the algebraic objects.

Results

The paper demonstrates the application of these methods through specific examples:

Minimum Weight Enumeration: For a (64, 32) polar code, the paper calculates the total number of minimum-weight codewords ( $A_8 = 920$ ) by summing the sizes of orbits for all maximum-degree monomials in the information set.
Low-Weight Enumeration: It computes the number of codewords with weight $1.5w_{min}$ ( $A_{12} = 25,472$ ) and $1.75w_{min}$ ( $A_{14} = 32,768$ ) by applying the derived Type-I and Type-II counting formulae.
Symmetry: The paper confirms that polar codes containing the all-one vector (monomial 1) possess a symmetric weight distribution ( $A_w = A_{N-w}$ ).
Recursive Computation: An example of a (8, 6) polar code demonstrates the recursive calculation of the full Weight Enumerating Function, yielding the distribution $1 + 12X^2 + 38X^4 + 12X^6 + X^8$ .

Significance and Claims

The authors position this work as a tutorial intended to prepare readers for deeper engagement with technical literature (specifically citing works [2], [20], [22], [23], [24]).

Modest Scope: The paper explicitly states it does not introduce new theoretical results. Its value lies in providing a "clear, unified, and accessible exposition" of existing algebraic insights.
Bridging the Gap: It aims to demystify the role of affine automorphisms (specifically the LTA group) and orbit-based descriptions, which are essential for understanding recent advances in weight enumeration but are often presented in a highly technical manner.
Future Directions: The paper acknowledges that while closed-form formulae exist for weights up to $2w_{min}$ , deriving expressions for higher weights across all code rates remains an open problem. It also notes that the enumeration of pre-transformed polar codes (e.g., CRC-polar) is currently unaddressed by these closed-form methods. The paper suggests that understanding these weight structures is vital for optimizing monomial selection in code design to maximize minimum distance or reduce low-weight codewords without compromising reliability.