🔢 mathematics

Polar Complexity: A New Descriptive Complexity with Applications to Source and Joint Source-Channel Coding

This paper introduces "polar complexity" as a new metric for describing finite-length binary sequences and leverages it to develop a strictly lossless, adaptive source coding scheme and a joint source-channel coding framework that achieve near-optimal performance without prior knowledge of source statistics while offering flexible tradeoffs between error performance and decoding complexity.

Original authors: Xinyuanmeng Yao, Xiao Ma

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xinyuanmeng Yao, Xiao Ma

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

Imagine you have a giant library of unique stories (binary sequences). Your goal is to shrink these stories down to the smallest possible size so they can be sent over a noisy telephone line, but you must be able to reconstruct the exact original story at the other end, with no missing words.

This paper introduces a new way to measure how "compressible" a specific story is, and then uses that measurement to build a smarter, more flexible way of sending data. Here is the breakdown using simple analogies:

1. The New Ruler: "Polar Complexity"

Traditionally, data compression (like ZIP files) works by looking at the average behavior of a whole library of stories. It assumes all stories are generated by the same random process. But what if you have just one specific story, and you don't know the rules that created it?

The authors introduce a new concept called Polar Complexity. Think of this as a "difficulty score" for a specific story.

The Analogy: Imagine you are trying to rebuild a shattered vase. Some vases are simple; if you are given just a few key shards (bits of information), you can figure out the rest. Other vases are complex; you need almost every single shard to put it back together perfectly.
The Definition: The "Polar Complexity" of a sequence is the minimum number of shards (bits) you need to hand to a robot so it can perfectly rebuild the original vase using a specific set of rules (called Polar Coding and Successive Cancellation Decoding).
The Catch: If you give the robot fewer shards than its "complexity score," it will fail. If you give it more, it will succeed.

2. Measuring the Score: The "Bisection Search"

Calculating this score exactly is hard. It's like trying to find the exact weight of a rock by guessing.

The Old Way: Guess 1 shard, try to rebuild. Fail. Guess 2 shards, try again. Fail. This takes forever.
The New Way (Bisection Search): The authors created a smart "guess-and-check" game. You guess the middle number. If it works, you know the answer is lower; if it fails, you know it's higher. You cut the search space in half every time. This is incredibly fast.
The Shortcut: They also built a "crystal ball" (a low-complexity estimation method). It looks at the story and predicts, "This one looks tricky; you'll probably need about 50 shards." It's not always 100% perfect, but it's a very safe upper limit that saves time.

3. The Two-Stage Compression System

Now that they can measure the "difficulty" of any specific story, they built a new compression system.

The Analogy: Imagine sending a package. Instead of just stuffing the item in a box, you first attach a label that says, "This item needs a box of size 5." Then you put the item in that specific box.
How it works:
1. Stage 1: The computer calculates the "Polar Complexity" (the difficulty score) of the data. It writes this number down as a short header (like a label).
2. Stage 2: It compresses the data down to exactly that many bits (the "shards" needed for reconstruction).
The Result: The final message is the "Label" + the "Compressed Data."
- Why it's great: It works for any type of data without needing to know the rules beforehand. If the data is simple, the label says "Small Box," and the package is tiny. If the data is messy, the label says "Large Box," and the package is bigger. It adapts to the content.
- The Guarantee: The paper proves that for long enough data, this method gets as close to the theoretical limit of compression (called "Entropy") as possible.

4. The "Adaptive Double-Polar" System (Sending Data Over a Noisy Line)

The final part of the paper combines this new compression with a method to send data over a noisy channel (like a bad Wi-Fi connection). This is called Joint Source-Channel Coding (JSCC).

The Problem: Usually, you compress data first, then add error protection. But if the channel is very noisy, you might need to send more bits to protect the data. If the channel is clear, you need fewer.
The Solution: The authors created a "Menu of Box Sizes."
- The sender and receiver agree on a list of possible "difficulty scores" (e.g., Small, Medium, Large).
- The Sender: Looks at the data, calculates its complexity, picks the smallest "Box Size" from the menu that is big enough to hold the data, and sends it.
- The Receiver: Doesn't know which box size was picked! So, it tries to decode the message assuming it was a "Small Box." If that fails, it tries "Medium," then "Large." It uses a smart test (like a checksum) to see which guess works.
The Optimization: The authors figured out the best way to design this "Menu." They used a mathematical strategy (Dynamic Programming) to pick the perfect list of box sizes so that the system is fast but rarely makes mistakes.

Summary of Claims

New Metric: They defined "Polar Complexity" as the minimum bits needed to perfectly reconstruct a specific sequence.
Efficiency: They showed how to calculate this quickly using a "half-and-half" search method.
Compression: They built a system that compresses data based on this complexity, proving it works as well as the best possible theoretical limits for long data.
Transmission: They combined this with error correction to create a system that automatically adjusts to how "hard" the data is to compress and how "noisy" the channel is, outperforming existing methods in simulations.

The paper claims this is a self-contained, mathematically proven method for handling data that is both efficient and robust, without needing to know the statistical rules of the data beforehand.

Technical Summary: Polar Complexity and Adaptive Double-Polar Coding

Problem Statement
Efficiently describing individual finite-length binary sequences remains a fundamental challenge in information theory. While Shannon's framework optimizes average description lengths for stochastic sources with known statistics, it does not directly apply to individual sequences lacking a probabilistic model. Conversely, Kolmogorov complexity, which defines the complexity of a sequence by the length of the shortest program generating it, is theoretically universal but uncomputable. Existing computable approaches, such as Lempel-Ziv (LZ) complexity or linear complexity, rely on specific structural assumptions (e.g., repeated patterns or linear recurrences) that may not capture the full regularity of arbitrary sequences. Furthermore, conventional fixed-length polar source coding, while achieving entropy for stochastic sources, does not inherently provide a mechanism to determine the minimum compression length required for the exact reconstruction of a specific individual sequence.

Methodology
This paper introduces a new descriptive complexity metric termed Polar Complexity, defined as the minimum Polar-Compression Length (PCL) required to guarantee the exact reconstruction of a specific binary sequence using Successive Cancellation Decoding (SCD). The methodology is built upon the Binary Balanced Tree (BBT) polar coding framework, which generalizes polar transforms to arbitrary block lengths.

Polar Complexity Definition and Computation:
- The authors define the polar complexity $L^\star(\mathbf{s})$ of a sequence $\mathbf{s}$ as the smallest PCL $L$ such that the sequence can be perfectly recovered from its polar-compressed representation under a canonical configuration (using the Polarization-Weight method for frozen-node selection and a deterministic SCD parameter $\tau=0$ ).
- Exact Computation: Leveraging the monotonicity of recoverability (if a sequence is recoverable at length $L$ , it is recoverable at any $L' > L$ ), the paper proposes a bisection-search algorithm to compute $L^\star(\mathbf{s})$ efficiently, reducing the number of SCD trials from linear to logarithmic in the sequence length.
- Low-Complexity Estimation: To avoid repeated decoding trials, a predicted polar complexity is introduced. This method utilizes Genie-Aided SCD (GA-SCD) to identify a "critical set" of leaf nodes that are locally ambiguous or prone to error. The predicted complexity is determined by the selection priority of the highest-priority node in this critical set, providing a conservative upper bound on the true polar complexity.
Polar-Based Two-Stage Source Coding:
- A new source coding scheme is proposed where each source sequence is encoded as a pair: a fixed-length header containing the binary representation of its polar complexity, followed by the variable-length polar-compressed sequence.
- The scheme is strictly lossless and prefix-free.
- Theoretical analysis proves that for Binary Memoryless Sources (BMS) with block lengths as powers of two, the normalized average compression length of this scheme asymptotically approaches the source entropy, provided the frozen-node selection and SCD parameters are optimized for the source distribution.
Adaptive Double-Polar Joint Source-Channel Coding (JSCC):
- The authors integrate the proposed source coding with polar channel coding to create an adaptive JSCC scheme.
- Mechanism: The encoder and decoder share a predefined finite set of candidate PCLs. For a given source sequence, the encoder selects the smallest candidate PCL that is greater than or equal to the sequence's predicted polar complexity. This selected PCL determines the allocation of active and frozen nodes in the channel encoder.
- Decoding: The decoder performs hypothesis testing over the candidate PCL set. It reconstructs candidate source sequences for each hypothesis and selects the final estimate based on the Maximum A Posteriori (MAP) criterion, utilizing CRC checks to filter invalid candidates.
- Optimization: The design of the candidate PCL set is formulated as an optimization problem to minimize the Frame Error Rate (FER). This is solved efficiently using dynamic programming, balancing the trade-off between performance (finer granularity) and complexity (size of the candidate set).

Key Contributions

Polar Complexity: The introduction of a new, computable descriptive complexity metric based on the minimum PCL for exact SCD reconstruction.
Efficient Algorithms: Development of a bisection-search algorithm for exact computation and a low-complexity GA-SCD-based prediction method for estimating polar complexity.
Two-Stage Source Coding: A strictly lossless, prefix-free coding scheme that achieves source entropy asymptotically without requiring prior knowledge of source statistics for operation (though entropy-achieving proofs assume knowledge of statistics for parameter tuning).
Adaptive JSCC: A unified double-polar JSCC framework that adapts the channel code rate to the compressibility of individual source realizations. The scheme includes a dynamic programming-based method to optimize the candidate PCL set for performance-complexity trade-offs.

Results

Source Coding Performance: Simulations demonstrate that the proposed two-stage scheme achieves compression performance comparable to enumerative coding for short block lengths ( $K=64$ ) but with significantly lower computational complexity ( $O(K \log K)$ vs. $O(K^2)$ ). The scheme remains robust across various source distributions and does not require prior statistical knowledge.
Complexity Estimation: The bisection search method significantly reduces the computational cost of determining polar complexity compared to sequential search. The predicted polar complexity consistently upper-bounds the true complexity with a small gap, validating its utility for JSCC design.
JSCC Performance: In adaptive double-polar JSCC simulations (for block lengths $N=128$ and $N=1024$ ), the proposed scheme outperforms existing polar-code-based JSCC baselines (including double-CRC-polar and joint SCLD schemes). The Frame Error Rate (FER) decreases monotonically as the cardinality of the candidate PCL set increases, approaching a theoretical lower bound where the true PCL is known to the decoder.

Significance
The paper claims that by shifting the focus from stochastic source properties to the recovery behavior of individual sequences under polar coding, it provides a practical and computable measure of descriptive complexity. This "polar complexity" enables a new class of coding schemes that are strictly lossless and adaptive. The proposed adaptive double-polar JSCC scheme offers a flexible performance-complexity trade-off, demonstrating that matching channel protection to the specific compressibility of individual source realizations can yield superior error-rate performance compared to static or non-adaptive joint coding approaches. The work bridges the gap between algorithmic complexity concepts and practical, capacity-approaching coding techniques.

1. The New Ruler: "Polar Complexity"

2. Measuring the Score: The "Bisection Search"

3. The Two-Stage Compression System

4. The "Adaptive Double-Polar" System (Sending Data Over a Noisy Line)

Summary of Claims

More like this