🔢 mathematics

Efficient LLR-Domain Decoding of ABS+ Polar Codes

This paper proposes an optimized LLR-domain Successive Cancellation List (SCL) decoder for ABS+ polar codes that reduces arithmetic complexity while achieving the same frame error rate as classical polar codes in the high-SNR region.

Original authors: Mikhail Chernikov, Peter Trifonov

Published 2026-04-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mikhail Chernikov, Peter Trifonov

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

The Big Picture: Fixing a Noisy Telephone Game

Imagine you are playing a game of "Telephone" (or "Broken Telephone") where you whisper a message down a long line of people. By the time the message reaches the end, it's often garbled because of background noise. In the world of digital communication, this is like sending data over a wireless channel.

Polar Codes are a special mathematical recipe invented to fix this. They arrange the message so that some parts of the line are super clear (like a direct line to the boss) and other parts are super noisy (like a crowded room). The trick is to only send the important message through the "super clear" parts and ignore the noisy ones.

However, there's a catch:

The Standard Recipe (Arikan Polar Codes): These work great if the line is infinitely long. But in the real world, our messages are short. When the line is short, the "clear" parts aren't that clear, and the message still gets messed up.
The New Recipe (ABS+ Polar Codes): The authors of this paper are using a newer, improved recipe called ABS+. Think of this as rearranging the people in the line and having them swap whispers or add extra context to each other before passing the message down. This makes the "clear" parts much clearer, much faster.

The Problem: The Decoder is Too Slow and Clunky

To get the message back out, you need a Decoder. The paper focuses on a specific type of decoder called SCL (Successive Cancellation List).

Imagine the decoder is a detective trying to solve a mystery.

The Old Way (Probability Domain): The detective calculates the exact probability (a percentage chance) that every possible suspect is guilty. "There is a 43.2% chance the butler did it, a 12.5% chance the gardener did it..." This is mathematically heavy. It requires complex multiplication and division, which is slow and hard to build into a computer chip.
The Paper's Innovation (LLR Domain): The authors realized the detective doesn't need exact percentages. They just need to know: "Is the suspect more likely to be guilty or innocent?" and "How much more?"
- Instead of percentages, they use Log-Likelihood Ratios (LLRs). Think of this as a simple scorecard: "+10" means very likely guilty, "-10" means very likely innocent, "0" means a coin flip.
- The Benefit: Calculating scores (+10, -10) only requires addition and subtraction. It's like switching from a complex calculator to a simple abacus. It's much faster and easier to build in hardware.

The Secret Sauce: Cutting Out the Waste

The paper doesn't just switch to the simpler math; it also realizes the original method was doing a lot of unnecessary work.

The Analogy of the Redundant Chef:
Imagine a chef who is making a sandwich.

The original recipe says: "Calculate the exact taste of the bread, the exact taste of the cheese, and the exact taste of the ham. Then, calculate the taste of the bread+cheese, the bread+ham, and the cheese+ham. Finally, decide if you want the sandwich."
The authors noticed: "Wait! You only need to decide if you want the sandwich. You don't need to calculate the taste of the ham after you've already decided to throw it away."

The original ABS+ decoder was calculating probabilities for bits it wasn't even going to use yet. The authors created a new algorithm that skips these calculations entirely. They only compute the numbers they absolutely need at that exact moment.

The Results: Faster and Smarter

The authors tested their new "Scorecard Decoder" (LLR-based) against the old "Percentage Decoder" (Probability-based) and the standard Polar Code decoder.

Better Performance: The new ABS+ decoder with the new math makes fewer mistakes (lower Frame Error Rate) than the standard Polar code decoder, especially when the signal is strong.
Same Speed, Better Results: If you give both decoders the same amount of "brain power" (arithmetic operations), the new ABS+ decoder wins. It gets a clearer message for the same effort.
Negligible Loss: The only downside is that the new "Scorecard" method is slightly less precise than the old "Percentage" method, but the difference is so tiny (less than 0.05 dB) that it doesn't matter in practice. It's like using a ruler with millimeter marks instead of micrometer marks; for building a house, the millimeter ruler is fine and much faster to use.

Summary

This paper presents a way to decode a new, powerful type of error-correcting code (ABS+ Polar Codes) using simpler math (addition/subtraction instead of complex multiplication) and less wasted effort (skipping calculations for bits we don't need yet).

The Takeaway: They found a way to make a high-performance communication system run faster and more efficiently on computer chips without sacrificing much accuracy. It's like upgrading a race car engine to be more fuel-efficient while keeping the same top speed.

1. Problem Statement

Polar Codes and Finite-Length Limitations:
While Arikan's polar codes theoretically achieve the capacity of binary memoryless channels under Successive Cancellation (SC) decoding as block length $n \to \infty$ , their performance in the finite-length regime is poor. To mitigate this, the Successive Cancellation List (SCL) decoder is used, often aided by a Cyclic Redundancy Check (CRC). However, the complexity of SCL grows exponentially with the required list size for large block lengths.

The Challenge of ABS+ Polar Codes:
Adjacent-Bit-Swapped (ABS) and ABS+ polar codes are a generalization of classical polar codes designed to achieve faster channel polarization in finite-length regimes. This results in significantly better error-correction performance compared to classical polar codes.

The Bottleneck: The existing decoding algorithms for ABS+ codes (specifically the SC and SCL decoders described in prior work [11]) operate in the probability domain. This requires complex multiplications and handling of transition probabilities, which is computationally expensive and difficult to implement efficiently in hardware.
Redundancy: The original probability-domain algorithms compute transition probabilities for two adjacent bits simultaneously but only decode one bit at a time, discarding the probability information for the second bit until the next phase. This leads to redundant calculations.

Goal: The authors aim to develop an LLR-domain (Log-Likelihood Ratio) version of the SCL decoder for ABS+ codes that reduces computational complexity (replacing multiplications with additions/comparisons) while maintaining near-optimal performance.

2. Methodology

The paper proposes a novel decoding framework that adapts the SCL algorithm to the LLR domain specifically for the unique encoding structure of ABS+ codes.

A. LLR Definitions for Virtual Subchannels

The authors define approximate LLRs for the virtual Double-Bit-Input (DBI) subchannels inherent to ABS+ encoding. Unlike classical polar codes which use single-bit subchannels, ABS+ decoding relies on a recursive tree of DBI channels $V^{(m)}_i$ .
They define two key LLR metrics for a DBI channel:

$L$ (LLR for the first bit): The log-ratio of the maximum likelihoods of the first bit being 0 or 1, marginalized over the second bit.
$R$ (LLR for the second bit): The log-ratio of the likelihoods of the second bit being 0 or 1, conditioned on the first bit.

B. Recursive Relations (Min-Sum Approximation)

The core of the methodology is establishing recursive relations (Lemma 2) to compute these LLRs ( $L$ and $R$ ) from the LLRs of the child nodes in the decoding tree.

The authors derive formulas (19a–19h) that express the LLRs of a parent node in terms of the LLRs of its children.
These formulas utilize standard min-sum operations ( $f_-$ and $f_+$ functions) and a specific function $g(a,b,c) = a - \max\{0, b\} + \max\{0, c\}$ .
This allows the decoder to operate entirely using additions, subtractions, and comparisons, avoiding the costly multiplications required in the probability domain.

C. Complexity Reduction Strategies

The paper introduces two critical optimizations to reduce the number of arithmetic operations:

Reusing Intermediate Values: The authors observe that the calculation of $R$ values for one phase often produces values needed for the next phase. Instead of recalculating, the algorithm stores and reuses these intermediate $R$ values.
Omitting Unused Computations (Right-Separated Nodes):
- In the original algorithm, the decoder computes $R$ values for all nodes.
- The authors identify that for certain nodes (called "right-separated" nodes), the $R$ values are not required to decode the current bit or subsequent bits in the specific decoding path.
- The proposed algorithm checks if a node is "right-separated." If so, it skips the calculation of the $R$ values entirely, significantly reducing the computational load.

D. Algorithm Structure

The proposed DecodeNode algorithm (Algorithm 2) performs a depth-first search on the decoding tree. It manages:

$B$ : Decoded bits.
$H$ : Stored bits needed for subsequent phases (due to bit-swapping transforms).
$L$ and $R$ : Arrays storing the computed LLRs.
$M$ : Intermediate values reused to avoid re-computation.

The SCL extension maintains these arrays for $L$ different paths, updating path metrics based on the computed LLRs.

3. Key Contributions

First LLR-Domain SCL Decoder for ABS+: The paper presents the first efficient SCL decoder for ABS+ polar codes that operates in the LLR domain, making it suitable for high-speed hardware implementation.
Optimized Recursive Formulas: Derivation of specific recursive relations (Lemma 2) that handle the complex adjacent-bit transforms ( $S_n$ and $A_n$ ) of ABS+ codes in the log-domain.
Redundancy Elimination: A novel method to identify and skip unnecessary LLR computations ("right-separated" nodes) and reuse intermediate values, reducing the arithmetic complexity compared to a naive LLR implementation.
Theoretical Guarantee: Proof that the proposed min-sum SCL decoder achieves Maximum Likelihood (ML) decoding performance when the list size $L$ is sufficiently large ( $L \ge 2^k$ for a $k$ -dimensional code).

4. Results

The authors validated their approach using simulations over an AWGN channel with BPSK modulation for a (1024, 512) code.

Performance vs. Classical Polar Codes:
- The proposed ABS+ SCL decoder significantly outperforms the standard SCL decoder for classical Arikan polar codes.
- At a Frame Error Rate (FER) of $10^{-4}$ , the ABS+ decoder provides a gain of up to 0.2 dB over classical polar codes.
Complexity vs. Performance:
- When comparing decoders with a fixed number of arithmetic operations, the ABS+ decoder consistently achieves a lower FER than the classical SCL decoder (especially for list sizes $L \ge 12$ ).
- To achieve the same FER, the ABS+ decoder requires a much smaller list size than the classical decoder.
LLR vs. Probability Domain:
- The performance loss of the proposed LLR-domain decoder compared to the original probability-domain decoder (from [11]) is negligible, less than 0.05 dB.

5. Significance

Hardware Feasibility: By converting the decoding process to the LLR domain (using only additions and comparisons), the paper makes ABS+ polar codes viable for practical hardware implementation, which was previously hindered by the complexity of probability-domain calculations.
Efficiency: The optimization techniques (reusing values and skipping redundant calculations) make the decoder more efficient than a direct translation of the probability algorithm, offering better performance-per-complexity ratios.
Future Applications: The min-sum approximation framework presented can be generalized to other polar decoding approaches (e.g., sequential decoding) and can be combined with fast SC/SCL techniques, paving the way for high-throughput, low-latency communication systems using advanced polar code variants.

In conclusion, this work bridges the gap between the theoretical performance advantages of ABS+ polar codes and the practical requirements of efficient hardware decoding, demonstrating that these advanced codes can be decoded with high efficiency and near-optimal performance.