🔢 mathematics

Minimum distances of LDPC codes in 5G standard

This paper proposes methods to bound the minimum distances of specific 5G NR quasi-cyclic LDPC codes, determining ranges for high-rate and low-rate BG1 codes, while introducing a new early termination technique based on circulant modular reduction to reduce decoder syndrome calculation complexity.

Original authors: V. R. Danilko, I. Yu. Mogilnykh, Ya. A. Tikhomolov

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: V. R. Danilko, I. Yu. Mogilnykh, Ya. A. Tikhomolov

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 are sending a very long, important letter through a noisy, chaotic postal system. To make sure the letter arrives intact, you wrap it in a special, mathematically generated "security blanket" called an LDPC code. This blanket has a specific pattern that allows the receiver to spot and fix errors caused by the noise.

The paper you are asking about is a technical investigation into the strength of these specific security blankets used in the 5G mobile network standard. The authors are essentially asking: "How many holes can this blanket have before it fails to protect the letter?"

Here is a breakdown of their findings using simple analogies:

1. The "Hole" Problem (Minimum Distance)

In the world of error-correcting codes, the "minimum distance" is like the minimum number of holes a security blanket must have before it stops working.

High Distance: The blanket is very strong. It can survive many holes (errors) and still be recognized as valid.
Low Distance: The blanket is weak. Even a few small holes can make it look like a different, valid blanket, causing the receiver to accept a corrupted letter without realizing it.

The authors found that the 5G standard uses two main types of these blankets:

The "High-Rate" Blanket (Shorter, denser): This one is surprisingly fragile. The authors proved it has a minimum distance between 8 and 14. Think of this as a blanket that might start falling apart if you poke it just a dozen times.
The "Low-Rate" Blanket (Longer, more redundant): This one is much sturdier, with a minimum distance between 22 and 57. It can take a much bigger beating.

2. The "Weak Spot" Discovery

The paper reveals a specific design quirk in the 5G standard. The security blanket is built in layers. The authors focused on the first few layers (called the "4-layer" and "6-layer" codes).

They discovered that because of how the blanket is constructed (specifically, having some very "dense" columns at the start), the high-rate blankets are prone to undetected errors.

The Analogy: Imagine a security guard checking a list. If the list has a very specific, short pattern of errors, the guard might think, "Oh, this looks like a valid list!" even though it's actually wrong.
The Result: In high-speed 5G transmissions, the decoder (the guard) sometimes stops early, thinking it found the perfect letter, but it actually found a corrupted one that looks perfect. This is why the paper notes that 5G relies heavily on a secondary check (a CRC, or a "seal") to catch these specific mistakes.

3. The "Shortcut" Method (Modular Reduction)

Calculating the strength of these blankets is incredibly hard for computers, like trying to count every single grain of sand on a beach to find a specific one. The authors developed a clever shortcut.

The Analogy: Instead of counting every grain of sand on the whole beach (the full, massive code), they looked at a tiny, scaled-down version of the beach (a "modular reduction").
How it works: They proved that if you shrink the problem down (like looking at a map instead of the terrain), the rules still hold. If the tiny map shows a weak spot, the big beach definitely has a weak spot there too. This allowed them to calculate the strength of the massive 5G codes much faster than previous methods.

4. The "Early Exit" Strategy (Decoder Efficiency)

The paper also suggests a way to make the "guard" (the decoder) work faster.

The Problem: Usually, the guard checks the entire security blanket (all layers) to see if it's valid. This takes time and computing power.
The Proposal: The authors suggest checking just the first few layers or a simplified version of the layers.
The Trade-off: It's like a security guard checking just the front door and the first hallway instead of the whole mansion.
- Pros: It's much faster and uses less energy (great for battery-powered phones).
- Cons: It slightly increases the chance of missing a very specific type of error.
- The Verdict: The authors found that for 5G, this "shortcut" is safe because the system has a "retransmission" feature. If the guard misses a mistake, the system just asks for the letter to be sent again. The speed gain is worth the tiny risk.

Summary

The paper is a mix of mathematical detective work and engineering optimization:

Detective Work: They proved that some 5G codes are weaker (have smaller minimum distances) than we might hope, explaining why they sometimes make "silent" mistakes.
Engineering: They created a faster way to calculate these strengths and proposed a "shortcut" for the decoder to save time and battery, knowing that the 5G system's "re-send" feature will catch the rare mistakes the shortcut misses.

In short: The 5G security blankets are strong enough for the job, but they have some known weak spots. The authors found a faster way to check them and showed that a "quick check" is safe enough because the system has a backup plan.

Technical Summary: Minimum Distances of LDPC Codes in 5G Standard

Problem Statement
The paper addresses the challenge of determining the minimum distances of the quasi-cyclic Low-Density Parity-Check (LDPC) codes defined in the 5G New Radio (NR) standard. While these codes offer strong performance and efficient hardware implementation, their minimum distance is a critical parameter for error correction capability and the prevalence of undetected errors. Calculating the exact minimum distance for general linear codes is an NP-hard problem. Existing methods, such as the Brouwer–Zimmermann algorithm (implemented in MAGMA), are computationally prohibitive for the long code lengths found in 5G (up to 25,344 bits), while other estimation methods are limited to shorter lengths. Furthermore, the unique structure of 5G LDPC parity-check matrices—specifically the presence of weight-one columns in the lower-right identity matrix and dense columns in the upper layers—raises concerns about potential degradation in minimum distance and the resulting "error floor" behavior observed in high-rate codes.

Methodology
The authors employ a dual approach combining theoretical bounds and computational reduction techniques:

Upper Bounds via Vontobel–Smarandache Construction:
The paper adapts the classical Vontobel–Smarandache lemma, which constructs codewords using determinants of submatrices of the polynomial shift matrix. Direct application to the full 5G "all-layer" exponent matrices (46 rows for BG1) is computationally infeasible. To overcome this, the authors exploit the specific block decomposition of the 5G parity-check matrix. They propose a "4-layer approach," applying the lemma to the top 4 rows (the 4-layer code) to generate low-weight codewords. These are then extended to the full all-layer code by appending uniquely determined parity bits. This significantly reduces the computational complexity from calculating determinants of $46 \times 46$ matrices to $4 \times 4$ matrices.
Lower Bounds via Modular Reduction:
The authors utilize the relationship between a quasi-cyclic code with circulant size $q$ and its modular reduction with a smaller circulant size $q'$ (where $q' | q$ ). They establish that the minimum distance of the reduced code provides a lower bound for the original code. By computing the minimum distance of shorter codes (e.g., with $q=12$ or $q=24$ ) using the Brouwer–Zimmermann algorithm, they derive lower bounds for the much longer 5G codes ( $q=384$ ).
To refine these bounds for high-rate codes, they introduce an iterative algorithm (Algorithms 3 and 4) that tracks "block supports" (the set of non-zero circulant blocks) of low-weight codewords. By verifying that no codewords with specific block supports exist in the reduced codes, they eliminate potential low-weight candidates in the larger codes, thereby tightening the lower bounds.
Early Termination Analysis:
The paper investigates a practical engineering application: reducing the complexity of syndrome calculation for early decoding termination. Standard syndrome calculation requires shifting operations for every column in the parity-check matrix. The authors propose a method based on circulant modular reduction, where the syndrome is checked against a reduced parity-check matrix (modulo a smaller $q'$ ). This reduces the number of required shifters and computational operations.

Key Results

Minimum Distance Bounds: The study establishes specific ranges for the minimum distances of key 5G LDPC codes:
- The high-rate 6-layer code $[9984, 8448]$ (BG1, $q=384$ ) has a minimum distance in the range $\{8, \dots, 14\}$ .
- The low-rate 6-layer code $[25344, 8448]$ (BG1, $q=384$ ) has a minimum distance in the range $\{22, \dots, 57\}$ .
- Detailed bounds are provided for various layer configurations ( $j=4$ to $j=46$ ) and punctured versions of these codes.
Error Floor Correlation: The analysis confirms that the relatively small minimum distances of high-rate 5G codes correlate with the observed error floor and the occurrence of undetected errors (where the decoder converges to a wrong codeword). This explains the necessity of the 24-bit CRC in the 5G standard to catch these events.
Early Termination Efficiency: The proposed early termination approach based on modular reduction (e.g., checking syndromes modulo 16 instead of 384) significantly lowers the computational complexity of syndrome calculation. Simulations indicate that this reduction results in negligible degradation of the Information Block Error Rate (IBLER) and Undetected Information Block Error Rate (UIBLER) for 5G codes, particularly given the system's reliance on HARQ retransmissions.

Significance and Claims
The paper claims to provide the first rigorous bounds on the minimum distances of the specific 5G LDPC code families, filling a gap left by the computational limitations of existing algorithms for long codes. The authors assert that their "4-layer" adaptation of the Vontobel–Smarandache lemma and the modular reduction technique for lower bounds are effective tools for analyzing large quasi-cyclic codes.

From an engineering perspective, the paper highlights that while the minimum distance of high-rate 5G codes is small (leading to undetected errors), the system design (HARQ and CRC) effectively mitigates this risk. The proposed early termination method offers a practical pathway to reduce hardware complexity (specifically the number of shifters) in LDPC decoders without compromising performance, making it relevant for efficient hardware implementations of 5G decoders. The results are presented as theoretical bounds and engineering observations rather than proposals for new standard protocols.

1. The "Hole" Problem (Minimum Distance)

2. The "Weak Spot" Discovery

3. The "Shortcut" Method (Modular Reduction)

4. The "Early Exit" Strategy (Decoder Efficiency)

Summary

More like this