The Complete LDPC Learning Guide

From Shannon to 5G — Intuition,

Mathematics, and Every Optimization

Who this is for: Engineers and practitioners who want to

understand channel coding deeply — not just "what" but "why",
at every level from intuition to equations to silicon.

PART I: THE FUNDAMENTAL

PROBLEM — WHY CHANNEL CODING
EXISTS

1.1 Shannon's Bombshell (1948)

In 1948, Claude Shannon proved something that shocked

everyone: it is possible to communicate arbitrarily reliably over a
noisy channel, at any rate up to a specific limit — the channel
capacity C. Below capacity, you can make error probability as
small as you want. Above capacity, errors are unavoidable.

The capacity of an AWGN (Additive White Gaussian Noise)

channel is:

C = B · log₂(1 + S/N) [bits/second]

Or in normalized form (bits per channel use):

 C = ½ · log₂(1 + SNR) [for real-valued channel]
C = log₂(1 + SNR) [for complex-valued
channel, relevant in 5G]

The catch: Shannon's proof was existential — random codes of

infinite length would achieve it. He gave no construction. The
engineering challenge for 70 years after 1948 was: how do you
build practical codes that actually approach capacity?

1.2 The Intuition Behind Shannon

Think of it this way. If you want to communicate 1 bit per second

reliably, you don't have to send just one signal. You can send a
long sequence of 1s or 0s — a codeword. Two codewords that
are "far apart" in Hamming distance are unlikely to be confused,
even in noise.

Shannon said: pick codewords at random from a large space.

With high probability, random codewords are "spread out" enough
that noise can't flip one into another. The problem? With a random
code of length n, decoding requires checking all 2^k possible
codewords — exponential complexity. Shannon cared about
existence, not complexity.

The entire history of coding theory after 1948 is: find structured
codes that are random enough to approach capacity, but
structured enough to decode efficiently.

1.3 Key Definitions

Code Rate: R = k/n, where k = information bits, n = codeword bits.

Rate tells you the fraction of bits that carry real information. R =
1/2 means half your bits are redundancy.
Hamming Distance d(x,y) = number of positions where
codewords x and y differ.

Minimum Distance d_min = minimum distance between any two

distinct codewords.

Error Correction Capability: A code with minimum distance

d_min can correct t errors where t = ⌊(d_min - 1)/2⌋ and detect
d_min - 1 errors.

Eb/N0 (Energy per Bit over Noise Spectral Density): The "SNR per
bit" — the most common axis on BER plots. The Shannon limit at
a given code rate tells you the minimum Eb/N0 needed for
reliable communication. For rate 1/2, the Shannon limit is about
-0.19 dB.

BER waterfall: the curve of Bit Error Rate vs Eb/N0. Good codes
have a steep waterfall that starts close to the Shannon limit.

PART II: LINEAR BLOCK CODES

2.1 What Makes a Code "Linear"?

A binary code C is linear if and only if: the sum (XOR) of any two
codewords is also a codeword. This means the codewords form
a vector subspace of GF(2)^n.

Why does linearity matter? Because:

The minimum distance = minimum Hamming weight of any

non-zero codeword (simpler to analyze)

Encoding is a matrix multiply: c = m·G

Decoding uses a parity check matrix: H·c^T = 0 for all valid

codewords
2.2 The Generator Matrix G and Parity Check
Matrix H

An (n, k) linear block code is defined by:

Generator Matrix G (k × n): Every codeword c is a linear

combination of rows of G:

c = m · G

where m is the k-bit message vector. The rows of G span the

code space.

Parity Check Matrix H (m × n, where m = n - k): A codeword c is

valid if and only if:

H · c^T = 0 (mod 2)

H encodes the parity constraints. Every row of H is a parity

equation that all valid codewords must satisfy.

Relationship: G and H are orthogonal complements. H · G^T = 0.

Systematic Form

In systematic form, the first k columns of G form an identity

matrix:

G = [I_k | P]

Then H = [-P^T | I_m] (or just [P^T | I_m] over GF(2) since -1 = 1).

The codeword structure is: [message bits | parity bits]. Encoding

is just: send the message, then append parity bits computed from
P.
2.3 Syndrome Decoding

When you receive vector r = c + e (codeword plus error pattern),

compute the syndrome:

s = H · r^T = H · (c + e)^T = H · c^T + H · e^T = 0 +

H · e^T = H · e^T

The syndrome depends only on the error pattern e, not on which

codeword was sent. This is the key insight: different error
patterns have different syndromes (unless errors are
indistinguishable, i.e., differ by a codeword).

Syndrome decoding: pre-compute a lookup table mapping each

syndrome to the most likely error pattern. Then correct: ĉ = r + ê.

Complexity: The table has 2^(n-k) entries (one per syndrome). For
small codes this is fine. For large codes, it explodes — this is the
fundamental problem with classical codes.

2.4 Hamming Codes

The simplest family of perfect single-error-correcting codes.

An (n, k) Hamming code has n = 2^r - 1, k = 2^r - 1 - r for integer r.

The parity check matrix H has all non-zero binary vectors of
length r as its columns (in any order).

Example: r=3 gives (7,4) Hamming code, corrects 1 error.

H = [0 0 0 1 1 1 1]
[0 1 1 0 0 1 1]
[1 0 1 0 1 0 1]

The syndrome of a single-bit error in position i is just the binary

representation of i. Elegant!
Key lesson: Hamming codes are "perfect" in the sphere-packing
sense but have fixed rate ~1 - r/2^r → 1 as r → ∞. They can only
correct 1 error, so they're weak for noisy channels.

2.5 Beyond Hamming: Reed-Solomon, BCH,

Reed-Muller

BCH Codes: Bose-Chaudhuri-Hocquenghem codes. Algebraic

codes that can correct multiple errors with bounded complexity.
Parity matrix built from roots of a generator polynomial over
GF(2^m). Efficient decoding via Berlekamp-Massey algorithm.
Used in CDs, DVDs, storage. Performance: good for short blocks,
significantly below capacity.

Reed-Solomon Codes: Operate over GF(2^m) symbols rather than

bits. Extremely popular in practice (QR codes, RAID, satellite).
Optimal minimum distance (MDS codes). But algebraic structure
limits performance in AWGN.

The ceiling problem: All of these algebraic codes hit a ceiling well
below the Shannon limit. Their structured algebraic constraints
that enable efficient decoding also limit their distance spectrum.
To approach Shannon, you need codes with randomness — and
that's exactly what LDPC and turbo codes provide.

PART III: CONVOLUTIONAL CODES

3.1 The Key Difference from Block Codes

Block codes encode k bits into n bits — done, next block.

Convolutional codes have memory — the encoder keeps a state,
and each output symbol depends on the current input and the
encoder's history. This enables sequences that are "spread out" in
time, giving better performance for sequential transmission.

3.2 Convolutional Encoder Structure

A rate-1/n convolutional code with constraint length K:

Has K-1 shift register stages (memory elements)

At each clock cycle: shift in 1 new bit, shift out n encoded bits

Each output is an XOR of specific shift register contents

(defined by generator polynomials g₁, g₂, ..., gₙ)

Example: Rate 1/2, constraint length 3 (K=3), memory m=2:

Register: [u_t, u_{t-1}, u_{t-2}]

g₁ = [1,0,1] → v₁_t = u_t ⊕ u_{t-2}
g₂ = [1,1,1] → v₂_t = u_t ⊕ u_{t-1} ⊕ u_{t-2}

The state of the encoder is the memory contents [u_{t-1}, u_{t-2}].

With m=2 memory bits, there are 4 possible states.

3.3 The Trellis

The beauty of convolutional codes is visualized in the trellis

diagram:

Left column: encoder states at time t

Right column: states at time t+1

Branches: one branch per possible input bit, labeled with

(input bit / output bits)

Every valid codeword sequence corresponds to a path through

the trellis starting at state 0.

This transforms decoding into a shortest-path problem: find the

path through the trellis that is closest (in Hamming distance or
log-likelihood) to the received sequence.

3.4 The Viterbi Algorithm — Hard and Soft

Decision

The Viterbi algorithm is the classic dynamic programming

solution to finding the ML path through the trellis.

Hard-decision Viterbi:

Received bits are sliced to 0/1 before decoding

Metric = Hamming distance between received bits and

branch label

At each trellis step: for each state, keep only the survivor path
(minimum cumulative metric)

Complexity: O(n · 2^m) — linear in block length, exponential in

memory

Soft-decision Viterbi:

Received channel output (real-valued, after matched filter) is

fed directly

Metric = Euclidean distance or log-likelihood ratio

~3dB gain over hard-decision for AWGN

Same complexity structure

Key insight: Soft-decision means preserving the receiver's

uncertainty. A bit received with LLR = 0.1 (barely positive) is very
different from LLR = 5.0 (very confident). Throwing this away
(hard decision) wastes information.

3.5 The BCJR / MAP Algorithm

The BCJR algorithm (Bahl, Cocke, Jelinek, Raviv, 1974) computes

for each bit position t:
 P(u_t = 1 | received sequence) and P(u_t = 0 |
received sequence)

It computes the a posteriori probability (APP) of each bit, giving

a soft output — not just a hard decision, but a confidence.

Why does this matter? Viterbi gives you the MAP sequence — the
most likely overall sequence. BCJR gives you the MAP symbol —
the most likely bit at each position. For iterative decoding, you
need soft outputs that can be fed to a second decoder. Viterbi
can't provide this in a useful way; BCJR can.

BCJR in Detail (Forward-Backward Algorithm)

The algorithm works in three passes:

Forward pass: Compute α_t(s) = P(state at time t is s, and

received sequence y_1...y_t)

α_t(s) = Σ_{s'} α_{t-1}(s') · γ_t(s', s)

Backward pass: Compute β_t(s) = P(received y_{t+1}...y_T | state

at time t is s)

β_t(s) = Σ_{s'} γ_{t+1}(s, s') · β_{t+1}(s')

Branch metric γ_t(s', s): probability of transitioning from s' to s at

time t, given received y_t.

γ_t(s', s) = P(y_t | transition s'→s) · P(u_t)

APP computation: The LLR of bit u_t:

L(u_t) = log [ Σ_{(s',s): u_t=1} α_{t-1}(s') ·

γ_t(s',s) · β_t(s) ]
 -
log [ Σ_{(s',s): u_t=0} α_{t-1}(s') ·
γ_t(s',s) · β_t(s) ]

BCJR complexity = O(n · 2^m) same as Viterbi. But it gives soft

outputs — the crucial ingredient for turbo decoding.

PART IV: TURBO CODES — THE 1993

REVOLUTION

4.1 The Idea That Changed Everything

In 1993, Berrou, Glavieux, and Thitimajshima presented a coding

scheme that achieved 0.5 dB from the Shannon limit at BER 10^-5
— previously unimaginable. The code, called a "Turbo code,"
worked on a radically different principle: iterate.

The Encoder

Two Recursive Systematic Convolutional (RSC) encoders

connected in parallel:

Input bits m
────────────────────────────────→ (systematic
bits: sent directly)
│
├──→ RSC Encoder 1 ──→ Parity
bits p₁
│
└──→ Interleaver (Π) ──→ RSC
Encoder 2 ──→ Parity bits p₂
You transmit: [m, p₁, p₂] (at rate 1/3, or puncture p₁ and p₂
alternately for rate ~1/2).

Why Recursive (vs non-recursive)? RSC encoders have feedback.

This means the encoder can produce high-weight codewords
even from low-weight inputs, dramatically improving minimum
distance. Non-recursive systematic convolutional codes have a
systematic weakness: a low-weight input always produces a low-
weight codeword.

Why two encoders? One encoder alone might have a "blind spot"
— certain input patterns that produce low-weight codewords
(these cause errors). The interleaver scrambles the input order, so
patterns that fool encoder 1 are unlikely to also fool encoder 2.
Together, they cover each other's weaknesses.

4.2 The Interleaver — The Key Ingredient

The interleaver Π is a permutation: it takes the input sequence

and reorders the bits before feeding them to encoder 2.

What interleaving does for performance:

1. Breaks the correlation between the two parity streams — they

provide "independent" error protection

2. The combined minimum distance grows with the interleaver

length N

3. Error events from encoder 1 are "spread" — an error burst in

one domain becomes scattered errors in the other, which
encoder 2 handles well

Effect on error floor: The interleaver gives pseudo-random

properties. For truly random interleavers of size N, the minimum
distance grows as √N — enough to make the error floor extremely
low in practice.
4.3 Iterative Decoding — The Turbo Principle

This is the heart of turbo codes, and it's the same principle LDPC
decoding uses.

The decoder has two SISO (Soft Input / Soft Output) decoders
(using BCJR):

Channel output y → Decoder 1 → Extrinsic LLR₁

→ Interleave → Decoder 2

│
←────────────── De-interleave
←──────────────── Extrinsic LLR₂ ←───┘

The critical concept: Extrinsic Information

At each decoder, the output LLR for bit u_t is:

L_out(u_t) = L_channel(u_t) + L_a_priori(u_t) +

L_extrinsic(u_t)

The extrinsic part L_extrinsic is what this decoder has learned

about u_t from the other bits (via the code constraints), excluding
what it already knew from the channel and what was fed in as a
priori. This is the new information this decoder contributes.

Why extrinsic, not the full output? If you fed the full posterior
output back as a priori, you'd be "double-counting" the channel
information — the decoder already used that when computing its
output. Feeding only extrinsic information prevents this.

One Iteration:

1. Decoder 1: Uses channel LLR(y_systematic), channel

LLR(y_parity_1), and a_priori from previous iteration (initially
zero). Computes extrinsic LLR₁ for each bit.
 2. Interleave LLR₁

3. Decoder 2: Uses channel LLR(y_systematic, interleaved),

channel LLR(y_parity_2), and interleaved LLR₁ as a priori.
Computes extrinsic LLR₂.

4. De-interleave LLR₂ → this becomes a priori for Decoder 1 in

next iteration.

Typically 6-18 iterations. Each iteration, the decoders' estimates

converge. At the end, hard decisions are made on the total
posterior LLR.

Intuition: It's like two people each with partial knowledge of a

puzzle, consulting each other iteratively. Each round, they
incorporate what the other learned, getting closer to the truth.
The "turbo" metaphor: extrinsic information is recycled like the
exhaust gases in a turbocharger — energy that would have been
wasted, fed back to improve the system.

4.4 Why Turbo Codes Approach Shannon —

EXIT Charts

EXIT (Extrinsic Information Transfer) charts visualize iterative

decoding convergence.

For each decoder, plot a curve: given input mutual information I_A
(how much a priori info the decoder receives), what is output
mutual information I_E (how much extrinsic info it produces)?

This curve is monotonically increasing (more a priori → better

extrinsic output)

For decoder 1: I_E₁ = T₁(I_A₁)

For decoder 2: I_E₂ = T₂(I_A₂), but since output of one feeds

into the other: I_A₂ = I_E₁, I_A₁ = I_E₂
If you plot both curves on the same axes (flipping the second),
you get two S-shaped curves. Iterative decoding converges if and
only if the two curves don't cross (except at (1,1)) — there must
be a "tunnel" between them for the decoder trajectories to pass
through to (1,1) (perfect decoding).

This gives a visual design criterion: choose code parameters so

that the EXIT curves form a tunnel at the smallest possible SNR.

4.5 Turbo Code Problems

1. Error floor: At high SNR, the BER curve flattens (a "floor") due
to low-weight codeword events. The floor is determined by
the minimum distance and weight enumerator.

2. Latency: Block length must be large for good performance

(long interleaver), causing encoding/decoding delay. Bad for
URLLC.

3. Parallelism: Trellis decoding has inherent sequential

dependencies. Hard to parallelize heavily.

4. For large block lengths: LDPC beats turbo. This was why 5G
NR chose LDPC for data channels.

PART V: LDPC CODES — GALLAGER'S

GENIUS

5.1 Historical Context

Robert Gallager invented LDPC codes in his 1960 MIT PhD thesis
(published 1963). He invented:

1. The code class (sparse parity check matrix)

 2. Iterative decoding algorithms (including the sum-product
algorithm!)

3. Proved that random regular LDPC codes have good distance

properties

Then the codes were forgotten for 35 years. Why? No computing

power to implement iterative decoding in real-time. No theory to
design good codes. The field moved to algebraic codes.

In 1993, Turbo codes appeared and showed that iterative

decoding on graphs could achieve near-Shannon performance.
This triggered a re-examination of everything. In 1995-1996,
MacKay and Neal independently rediscovered LDPC codes and
showed they were just as good, often better than turbo codes for
long blocks.

5.2 Gallager's Intuition — Why Sparse?

The core insight: If you have many parity checks, but each check
involves only a small number of bits, then:

1. Local decoding: Each check equation constrains only a small

subset of bits. This enables local, iterative inference — like
solving a very large crossword puzzle by focusing on
individual clues.

2. Independence: If the graph has few short cycles, then the bits
involved in different checks are "almost independent." This
lets you apply probabilistic reasoning without worrying about
correlations.

3. Complexity: The decoder only processes the non-zero entries

of H. If H has weight w per row, total complexity is O(n·w) —
linear in block length!

4. Distance: A random sparse code still has good minimum

distance (linear in n), because the graph's expansion
 properties prevent low-weight codewords.

The contrast with algebraic codes: In Hamming, BCH, etc., H is

highly structured (dense or with algebraic patterns). This
structure gives efficient decoding but limits the distance
distribution. A sparse but "random" H has the good distance
properties of random codes while allowing efficient local
decoding.

5.3 The Parity Check Matrix H

An (n, k) LDPC code is defined by its parity check matrix H (size

m × n, where m = n - k):

n = number of code bits (codeword length)

k = number of information bits

m = number of parity check equations

H is sparse: most entries are 0

A codeword c satisfies H·c^T = 0 (mod 2).

The term "low density" refers to the density (fraction of 1s) in H

being very small — typically a few percent or less.

Column weight d_v: number of 1s in each column of H = number

of parity checks involving each code bit.
Row weight d_c: number of 1s in each row of H = number of code
bits involved in each parity check.

Regular LDPC code: All columns have the same weight d_v
(called variable node degree), all rows have the same weight d_c
(check node degree). Rate R ≥ 1 - d_v/d_c.

Irregular LDPC code: Variable and check node degrees vary. The
degree distribution is described by polynomials:
 λ(x) = Σ_i λ_i · x^{i-1} [fraction of edges
connected to variable nodes of degree i]
ρ(x) = Σ_j ρ_j · x^{j-1} [fraction of edges
connected to check nodes of degree j]

Irregular codes, properly designed, can outperform regular codes

and approach capacity much more closely.

5.4 The Tanner Graph — Visualizing the Code

In 1981, Tanner introduced the bipartite graph representation of

LDPC codes (now called the Tanner graph):

Variable Nodes (circles): v₁ v₂ v₃ v₄ v₅ v₆

│╲ │╲ │ │ ╱│╲ │
│ ╲ │ ╲ │ │ ╱ │ ╲ │
Check Nodes (squares): c₁ c₂ c₃ c₄

Variable nodes (v-nodes or bit nodes): one per code bit. The
code bit value is associated with this node.

Check nodes (c-nodes): one per row of H (per parity

equation).

Edge between v_j and c_i: exists if and only if H[i,j] = 1.

Each check node c_i represents the equation: XOR of all variable
nodes connected to it = 0.

Cycles in the Tanner graph: The shortest cycle length is the girth
g. Short cycles (especially length 4, called "4-cycles") cause
correlations between messages in the belief propagation
algorithm, degrading performance. Good LDPC codes are
designed to have large girth (g ≥ 6, ideally g ≥ 8).

Why is the Tanner graph so powerful? It decomposes a global

constraint (H·c=0) into many local constraints. The decoder can
then do local computations at each node and pass messages
along edges — this is belief propagation.

PART VI: BELIEF PROPAGATION —

THE DECODER

6.1 The Big Picture

Belief propagation (also called message passing, sum-product

algorithm) is an algorithm for computing marginal distributions
on factor graphs. It was independently discovered multiple times:
Pearl (1982) in AI, Tanner (1981) in coding, Gallager (1963) in
LDPC, and formalized by Forney, Wiberg, and others.

For LDPC decoding, the goal is: given the received channel
output y, compute for each bit j:

P(c_j = 0 | y) and P(c_j = 1 | y)

and then make decisions based on which is larger.

Why not compute this directly? Because it requires summing

over all 2^k possible codewords — exponential complexity. BP
does it approximately (and exactly for tree graphs) in linear time.

6.2 Log-Likelihood Ratios (LLRs)

Working in the log domain is numerically better than working with

probabilities directly.

Channel LLR for received symbol y_j:

 L_ch(j) = log [ P(y_j | c_j = 0) / P(y_j | c_j = 1) ]

For AWGN with BPSK (0 → +1, 1 → -1), variance σ²:

L_ch(j) = 2 · y_j / σ²

The sign of LLR gives the hard decision; the magnitude gives the
confidence. LLR > 0 → decide c_j = 0; LLR < 0 → decide c_j = 1.

Total LLR (a posteriori):

L(c_j | y) = log [ P(c_j = 0 | y) / P(c_j = 1 | y) ]

6.3 The Sum-Product Algorithm (Belief

Propagation) in LLR Domain

Two types of messages flow along edges in the Tanner graph:

Variable → Check messages (what the bit thinks it is):

μ_{v→c}(x) = channel_LLR(v) + Σ_{c' ∈ N(v)\{c}}

μ_{c'→v}

A variable node sends to check c: my channel measurement plus

what all my OTHER check nodes told me.

Check → Variable messages (what the constraint "knows" about

the bit):

In the probability domain, the check node message is:

P(x_v = 0 | x_{v'} for v' ≠ v) = ½ + ½ · ∏_{v' ∈

N(c)\{v}} (1 - 2·P(x_v' = 1))
In the LLR domain, using the key identity tanh(L/2) = (1 -
P(x=1))/P(x=1):

μ_{c→v} = 2 · arctanh( ∏_{v' ∈ N(c)\{v}}

tanh(μ_{v'→c} / 2) )

Or equivalently, using the "box-plus" operation:

μ_{c→v} = (⊕_{v' ∈ N(c)\{v}}) μ_{v'→c}

where a ⊕ b = 2·arctanh(tanh(a/2)·tanh(b/2))
= sign(a)·sign(b) · min(|a|,|b|) +
correction_term

A check node update asks: "Assuming all OTHER bits connected

to me satisfy the parity check, what does that tell me about bit v?"

Posterior LLR for each variable node:

L(c_j) = L_ch(j) + Σ_{c ∈ N(v)} μ_{c→v}

Hard decision: c_j = 0 if L(c_j) > 0, else c_j = 1.

Stopping condition: Either syndrome H·ĉ^T = 0 (valid codeword

found), or maximum iterations reached.

6.4 Flooding vs Layered Scheduling

Flooding (parallel) scheduling:

All variable nodes update simultaneously using old check

messages

All check nodes update simultaneously using old variable

messages

Clean to implement, easy to analyze

 One iteration = one full round of both updates

Layered (sequential/turbo) scheduling:

Process rows of H one at a time (one "layer" at a time)

After updating check node i, immediately use the new

message for variable node updates

This creates a serial dependency that is more like the turbo

decoder

Converges ~2× faster than flooding (in terms of iterations

needed)

Requires updating variable node LLRs in-place between layer

updates

Standard in hardware implementations (including 5G NR

decoders)

Why layered converges faster: Information propagates through

the graph more quickly. Each bit gets updated more frequently
with more recent information.

6.5 The Algorithm in Practice

Input: channel LLRs L_ch[j] for j = 0..n-1

Initialize: μ_{v→c}[j,i] = L_ch[j] for all edges
(j,i)
μ_{c→v}[i,j] = 0 for all edges

For iteration t = 1, 2, ..., T_max:

// Check node update
For each check node i:
For each v ∈ N(c_i):
μ_{c→v}[i,v] = 2·arctanh( ∏_{v' ∈ N(c_i)\{v}}
tanh(μ_{v→c}[v',i] / 2) )

// Variable node update

For each variable node j:
 L_post[j] = L_ch[j] + Σ_{i ∈ N(v_j)} μ_{c→v}
[i,j]
For each i ∈ N(v_j):
μ_{v→c}[j,i] = L_post[j] - μ_{c→v}[i,j]

// Syndrome check / early termination

ĉ = hard_decision(L_post)
If H · ĉ^T == 0: CONVERGED, output ĉ

Output: hard_decision(L_post) at T_max

PART VII: WHY LDPC IS SO CLOSE TO

SHANNON

7.1 The Capacity-Achieving Property — What

It Means

Shannon showed: there exist codes that achieve capacity. LDPC

codes (properly designed) are provably capacity-achieving — for
appropriately chosen degree distributions, there exist sequences
of LDPC codes such that as block length → ∞, the decoding
threshold under BP approaches the Shannon capacity.

But we need to unpack this: capacity-achieving under what

decoder?

Under ML decoding: many codes achieve or approach

capacity (including simply random codes)

Under BP decoding: LDPC codes are unique — their sparse

structure allows BP, and BP on LDPC codes with good degree
distributions can achieve capacity
Key result (Luby, Mitzenmacher, Shokrollahi, Spielman, 1998): On
the Binary Erasure Channel (BEC), LDPC code ensembles with
optimized degree distributions achieve capacity under BP
decoding. Capacity-achieving sequences were constructed
explicitly.

For AWGN and other channels: the thresholds approach capacity,

with the gap depending on degree distribution design. Irregular
LDPC codes designed via density evolution can get within 0.04
dB of the Shannon limit.

7.2 Density Evolution — The Analytical Tool

Density evolution (DE) (Richardson, Urbanke, 2001) is the key tool

for analyzing and designing LDPC codes.

Setup: Assume infinite block length and tree-like Tanner graph

(no short cycles). Under these assumptions, the messages at
each iteration are independent.

Tracking: At each iteration t, track the probability distribution of

messages. For AWGN, track the mean and variance of LLR
messages (using Gaussian approximation) or the full distribution
(exact DE).

Decoding threshold: For a given channel (parameterized by SNR

or noise level σ²), there is a threshold σ*: if σ < σ* (less noise), BP
decoding succeeds as n → ∞; if σ > σ*, it fails. This threshold is
determined by whether the density evolution equations converge
to the "success" fixed point.

Design: Optimize the degree distribution (λ(x), ρ(x)) to maximize

the threshold σ* (or equivalently, minimize the SNR at which the
code operates reliably). This is a linear programming problem
over the degree distribution coefficients.
Result: Well-designed irregular LDPC codes have thresholds
within 0.04 dB of the Shannon limit for AWGN. Spatially coupled
LDPC codes (SC-LDPC) threshold-saturate to the MAP threshold,
which can equal the Shannon limit.

7.3 Why the Graph Structure Enables Near-

Capacity Performance

Think about what Shannon's random coding proof says: a

randomly chosen code achieves capacity (under ML decoding).
The key is that random codes have "good" distance properties —
most codewords are far apart.

An LDPC code defined by a random sparse H matrix is a random

code restricted to a subspace. For large n:

The minimum distance grows linearly with n (good!)

The weight distribution looks "random" (good!)

But we can decode it efficiently via the sparse structure

(good!)

The catch: BP decoding is NOT ML decoding. BP fails due to

cycles in the Tanner graph. Short cycles cause "message
confusion" — a message arriving at a node contains information
about itself (through a loop), violating the independence
assumption.

For long codes with good graph design (large girth), cycles are
long, and the "independence radius" (how far you can go before
hitting a cycle) grows as ~log(n). For finite block lengths, this
means BP is only approximately right, but the approximation
improves with block length.

The intuition for near-capacity performance:

 Long blocks → large girth → long cycles → BP ≈ ML on most
of the graph

Good degree distribution → "balanced" information flow →

efficient error correction

Irregular nodes (degree-2 variable nodes) create "degree-2

chains" that efficiently propagate reliable information into
uncertain bits

7.4 The Connection to Shannon's Random

Coding Argument

Shannon's proof: Pick a random code (random generator matrix).

For any rate R < C, the probability that a random code has bad
performance → 0 as n → ∞.

LDPC's genius: Use a random sparse H matrix. The code is

random, so it inherits the good distance properties. But the
sparsity allows efficient decoding.

The price paid: BP is not ML, so there's a gap. But for long codes,
this gap → 0. That's the content of density evolution: as n → ∞
with the right degree distribution, BP performance → MAP
performance → approaches Shannon.

PART VIII: LDPC ≈ ML DECODER —

THE DEEP CONNECTION

8.1 BP = ML on Trees

The most important fact about belief propagation:

 On a tree-structured Tanner graph (no cycles), BP is EXACT
and computes the correct MAP marginals. It IS the ML
decoder.

Proof sketch: On a tree, there are no cycles, so all messages

arriving at a node are independent (computed from disjoint
subtrees). The message-passing updates are exact — they
correctly compute the marginal probability of each bit given the
received sequence.

This is the fundamental theoretical justification for BP: it's not a

heuristic; it's the exact ML decoder for tree codes. We're
extending it heuristically to graphs with cycles.

8.2 Why Cycles Break Exactness

In a graph with cycles, consider a length-4 cycle: v₁ - c₁ - v₂ - c₂ -

v₁. When v₁ sends a message to c₁, it incorporates messages
from c₂. But c₂'s message was influenced by v₂, which was
influenced by c₁, which was influenced by v₁ — a circular
dependency.

This "message confusion" has two effects:

1. BP may not converge (oscillates between different estimates)

2. Even if it converges, it may converge to a wrong answer (a

"pseudocodeword")

Pseudocodewords: Fixed points of the BP equations that do not

correspond to valid codewords. At low SNR, BP may converge to
a pseudocodeword instead of the transmitted codeword, causing
a decoding failure.

The distance from the transmitted codeword to the nearest

pseudocodeword determines the effective minimum distance of
BP decoding — often lower than the true minimum distance.
8.3 Linear Programming (LP) Decoding —
The Bridge to ML

In 2002, Feldman showed that ML decoding of a linear code can

be written as an Integer Linear Program (ILP). The LP relaxation
(dropping the integer constraint) gives an algorithm called LP
decoding:

ML decoding as ILP:

minimize Σ_j (1 - L_ch(j)/2) · x_j (minimize

cost = correlation with channel)
subject to: x = valid codeword ∈ {0,1}^n

LP relaxation: Relax x to the "fundamental polytope" — convex

hull of all codewords, approximately.

Properties of LP decoding:

If LP finds a vertex of the polytope, it must be a codeword (LP

decoding = ML)

If LP finds a fractional solution (non-vertex, non-integer), LP

decoding "fails" but knows it failed

LP decoding dominates ML decoding over all channels

simultaneously (if LP fails, ML would also "fail" in a sense)

LP is closely related to BP: the fixed points of BP are

approximations to the LP solution

This establishes that BP, LP, and ML are all trying to solve the
same underlying optimization problem — ML being the ideal, LP
being its convex relaxation, and BP being an efficient iterative
approximation.
8.4 Ordered Statistics Decoding (OSD) —
Getting Closer to ML

OSD (Fossorier & Lin, 1995) is a post-processing technique that

can get arbitrarily close to ML decoding at the cost of extra
computation:

1. Find the k most reliable bit positions (highest |LLR| values) —

these are the "most reliable basis" (MRB)

2. Perform Gaussian elimination on H to express the code in

systematic form with the MRB columns first

3. Enumerate the 2^order combinations of flipping bits in the

MRB (starting from order 0)

4. For each flip pattern, solve for the remaining bits (parity bits)
and compute the total metric

5. Output the highest-metric valid codeword

At order 0: only try the hard-decision codeword. Very fast, but

suboptimal.
At order d: try all patterns with up to d errors in the MRB.
Approaches ML as d increases.

OSD can be used as a post-processor after BP failure to lower the

error floor.

8.5 The Practical Consequence

For long LDPC codes (n > 10,000) at rates used in 5G:

BP decoding with 20-50 iterations performs within < 0.1 dB of

ML decoding in the waterfall region

The error floor (caused by pseudocodewords and trapping

sets) is where BP diverges from ML
This is why 5G NR LDPC codes were carefully designed with large
girths and specific structure to push pseudocodewords away and
minimize the error floor.

PART IX: PRACTICAL

OPTIMIZATIONS — FROM SMALL
TRICKS TO BIG IDEAS

9.1 The Min-Sum Algorithm — First

Approximation

The exact check node update:

μ_{c→v} = 2·arctanh( ∏_{v' ∈ N(c)\{v}}

tanh(μ_{v'→c} / 2) )

Computing tanh and arctanh in hardware is expensive — requires

lookup tables or Taylor series approximations. The min-sum (MS)
algorithm replaces this with a simple approximation:

Using the identity:

2·arctanh(tanh(a/2)·tanh(b/2)) ≈
sign(a)·sign(b)·min(|a|,|b|)

(exact for |a|=|b|, approximate otherwise — the error is always

positive, meaning MS overestimates message magnitudes)

The check node update becomes:

 μ_{c→v} = (∏_{v' ∈ N(c)\{v}} sign(μ_{v'→c})) ·
min_{v' ∈ N(c)\{v}} |μ_{v'→c}|

What this is computationally: XOR of signs (super cheap, just

XOR the sign bits), and minimum of magnitudes (just find the
smallest absolute value).

Performance: 0.2-0.5 dB worse than full SPA for typical codes.

But the complexity reduction is enormous — no transcendental
functions needed.

Implementation trick: You don't need all minimum values — just

the first and second minimum. Store min₁, min₂, and the index
achieving min₁. For any message to v:

If v is the one achieving min₁: use min₂

Otherwise: use min₁

This requires only 2 comparators and minimal storage per check

node.

9.2 Normalized Min-Sum (NMS) —

Correcting the Bias

The min-sum algorithm overestimates message magnitudes

(because the approximation error is always positive). This means
the decoder is "overconfident," which causes degraded
performance.

Fix: Multiply the min-sum output by a correction factor α < 1:

μ_{c→v}^{NMS} = α · (∏ sign(μ_{v'→c})) · min_{v' ∈

N(c)\{v}} |μ_{v'→c}|
Where α comes from: Density evolution. For a given code and
channel, optimize α to maximize threshold. Typical values: α ≈
0.75 - 0.875.

Performance: Within 0.1-0.2 dB of full SPA. Near-SPA

performance at a fraction of the complexity. Used in almost all
practical LDPC decoders.

Implementation cost: One multiplication per check node update

(can be done with shift-add if α = 2^{-k}).

9.3 Offset Min-Sum (OMS) — Additive

Correction

Instead of scaling, subtract a constant β:

μ_{c→v}^{OMS} = (∏ sign(μ_{v'→c})) · max(0, min_{v'

∈ N(c)\{v}} |μ_{v'→c}| - β)

The max(0, ...) prevents negative values.

Comparison with NMS:

OMS: constant shift, works best in the mid-SNR range

NMS: proportional scaling, works well over wider SNR range

For finite-length codes, OMS with a well-chosen β can slightly

outperform NMS

OMS is easier in fixed-point arithmetic (just subtract a

constant)

In 5G NR implementations, both are used depending on

vendor choice

How to find optimal β: Density evolution or simulation. Typical

values: β ≈ 0.15 - 0.5.
9.4 Layered (Row-Layered) Scheduling — 2×
Speedup

As described earlier, process check node rows one at a time,

immediately updating the variable node LLRs in-place.

Algorithm: Store the "intrinsic LLR" for each variable node: L_v =
L_ch + Σ_{all c} μ_{c→v}

When processing row i:

1. For each v ∈ N(c_i):

Compute input to check: m_v = L_v - μ_{c_i→v} (remove

old message from c_i)

2. Compute new check node message μ_{c_i→v}^{new} using

inputs {m_v}

3. Update: L_v += μ_{c_i→v}^{new} - μ_{c_i→v}^{old}

4. Store μ_{c_i→v}^{new} for next iteration

Why faster convergence: At each layer, the variable nodes

immediately incorporate the new check node message. By the
time the next layer is processed, the variable nodes reflect the
most recent information. This creates an effect like serial
updates in iterative solvers — typically 2× faster in terms of
iterations needed for the same BER performance.

Memory implications: Store only one LLR per variable node (the
cumulative intrinsic LLR) plus one message per edge (the check-
to-variable message for the previous iteration). The variable-to-
check message is computed on-the-fly as (L_v - old_check_msg).

9.5 Early Termination — Saving Cycles

Many decoding instances converge well before the maximum

iteration count. Continuing to iterate wastes power and time.
Syndrome-based stopping: After each iteration (or each layer),
compute H·ĉ^T. If it's zero, we have a valid codeword — stop. This
is cheap for structured codes (exploit QC structure, or pipeline
the check).

LLR stability stopping: Stop if the change in all variable node

LLRs between iterations is below a threshold. Less rigorous (can
miss errors) but very simple.

Hybrid: Use syndrome check as primary criterion, with a max

iteration limit as backup.

Statistics: For a well-operating LDPC decoder at operating SNR,

~80% of blocks may converge in half the iterations. Early
termination can give 40-60% average power reduction while
maintaining the same BER.

9.6 The Error Floor Problem — Trapping Sets

At high SNR (well into the waterfall), the BER should decrease
exponentially. But many LDPC codes show an error floor: the BER
curve suddenly flattens and the rate of decrease slows
dramatically.

Cause: Trapping sets and absorbing sets — small subsets of

variable nodes that form "traps" for the BP decoder.

Formal definition: A (a, b) trapping set T is a set of a variable

nodes such that the induced subgraph has b odd-degree check
nodes (check nodes with an odd number of connections to T).
The odd-degree check nodes are called "unsatisfied checks" at
the error floor.

What happens: When error patterns hit these variable nodes, BP

gets "stuck" — it fails to satisfy the unsatisfied checks and
oscillates or converges to a wrong codeword. The trapping set
acts like an attractor for the decoder dynamics.
Example: A (5,3) trapping set means 5 variable nodes and 3 odd-
degree check nodes. These are particularly harmful.

Why low SNR doesn't matter: At low SNR, many bits are
unreliable, so errors are widespread and BP can escape trapping
sets. At high SNR, only a few bits are in error, and if those happen
to form a trapping set, BP fails.

Mitigation Strategies:

Code design level:

Use progressive edge growth (PEG) algorithm to construct

Tanner graphs with large girth and minimal harmful trapping
sets

Use structured codes (QC-LDPC) with carefully chosen

circulant shift values to avoid small trapping sets

Analyze the trapping set enumerator and design to eliminate

small ones

Decoder level:

Post-processing with noise injection: add controlled random

perturbations to LLRs and re-run BP (simulated annealing
approach). This can escape trapping sets.

Multi-pass decoding: Run BP, if syndrome check fails, perturb

and re-run

Ordered statistics post-processing: OSD-0 or OSD-1 on the

unsatisfied checks

9.7 Quantization and Fixed-Point Arithmetic

Real hardware uses fixed-point arithmetic with finite word

lengths. This introduces quantization error.
LLR clipping: LLRs beyond a threshold are clipped to ±LLR_max.
This prevents overflow and is benign for large LLRs (we're already
certain). Typical: 5-6 bits for LLR representation = 32-64 levels =
clip at ±LLR_max ≈ 5-10.

Message quantization: Internal messages (check-to-variable,

variable-to-check) typically use 4-6 bits. Going below 4 bits
causes significant performance loss (0.1-0.3 dB).

Non-uniform quantization: More quantization levels near zero

(uncertain bits need fine resolution), fewer levels at high
magnitudes (already certain). Typical: 6-bit uniform with
appropriate step size works well.

Log-likelihood initialization: From the channel, LLRs are

inherently continuous. The ADC (analog-to-digital converter)
quantizes the received signal. Using 4-5 bits per channel sample
is typical in 5G receivers.

Performance impact: A well-designed 6-bit fixed-point NMS

decoder typically performs within 0.1-0.15 dB of floating-point.
Going to 4 bits: ~0.3-0.5 dB loss.

9.8 Quasi-Cyclic (QC) LDPC Codes —

Hardware Efficiency

The Problem with Random LDPC: Truly random sparse H

matrices have no structure that enables efficient hardware
implementation. Memory addressing, parallelism, and routing are
all complex.

The QC Solution: Construct H as a block matrix of circulant

matrices (cyclic permutation matrices):

H = [P^{a_{00}} P^{a_{01}} ... P^{a_{0,n-1}}]

[P^{a_{10}} P^{a_{11}} ... P^{a_{1,n-1}}]
 [ ... ... ... ... ]

where P is the z×z "cyclic shift" (identity matrix shifted by one

position), and P^a means shifted by a positions (P^∞ = 0 matrix).

Hardware benefits:

1. Parallelism: z check nodes can be processed simultaneously

(they're independent within a "layer" of z rows)

2. Memory: The entire H is described by the shift values {a_{ij}}

— compact description

3. Routing: Barrel shifters implement the cyclic shift — regular,

efficient

4. Throughput: z-fold parallelism directly translates to z×

throughput

The "lifting factor" z is chosen based on throughput

requirements. In 5G NR, z ranges from 2 to 384.

Mathematical description: A QC-LDPC code can be described by

its "base graph" B (a smaller matrix where each entry is a
circulant shift value). The actual H is obtained by "lifting" —
replacing each entry a_{ij} with the z×z circulant P^{a_{ij}}.

9.9 Degree Distribution Optimization —

Capacity-Approaching Design

For irregular LDPC codes, the degree distribution (λ, ρ)

dramatically affects performance.

Key insights from density evolution:

Degree-2 variable nodes: very helpful for efficient propagation

(information flows cheaply), but too many cause error floors
(they can be in trapping sets)
 High-degree variable nodes: increase code distance but
reduce BP efficiency

Check node degree: higher degree → better minimum

distance, but more complex check nodes

Optimal trade-off: mix of degrees, with many degree-2 and

degree-3 variable nodes and some high-degree ones

Design procedure:

1. Fix the target rate R and code length n

2. Set up density evolution equations as a function of (λ, ρ)

3. Optimize (via linear programming or EXIT chart matching) to

maximize the decoding threshold

4. Verify by simulation for finite length

5. Check the error floor (analyze trapping sets)

The "capacity-approaching" intuition: Degree-2 variable nodes

form "chains" that very efficiently propagate certainty from more
reliable bits to less reliable ones. They're like a wire connecting a
reliable region to an uncertain one. But they have low minimum
distance contribution — so you can't have too many.

9.10 Puncturing and Rate-Compatible Codes

To support multiple code rates (for HARQ and adaptive MCS),

LDPC codes can be designed as rate-compatible:

Puncturing: Remove some parity bits from the codeword before

transmission. Increases rate but reduces redundancy. The
punctured bits are known to the decoder (as "erasures" with LLR
= 0).

Shortening: Set some information bits to zero and don't transmit

them. Decreases rate effectively.
Rate-compatible LDPC (RC-LDPC): A family of codes where
higher-rate codes are obtained by puncturing a mother code.
Designed so all rates in the family have good performance.

In 5G NR: The base graph gives a "base code" and then

puncturing/repetition via the rate matcher selects the actual code
rate for each transport block. The "circular buffer" approach
stores the encoded bits and the rate matcher reads from a
selected starting position.

PART X: 5G NR LDPC — SPECIFIC

DESIGN CHOICES

10.1 The Two Base Graphs

5G NR uses two base graphs:

Base Graph 1 (BG1): For high throughput, large code blocks

46 rows (m_b = 46), 68 columns (n_b = 68) → k_b = 22

information columns

Code rate from 1/3 to 22/24 (≈ 8/9)

Used for: code blocks > 3840 bits, or code rate ≥ 1/4 for
shorter blocks

Maximum code block size: 8448 bits

Base Graph 2 (BG2): For low throughput, small code blocks, low
rate

42 rows, 52 columns → k_b = 10 information columns

Code rate from 1/5 to 2/3

Used for: shorter blocks or lower rates

Why two base graphs: Different applications need different
performance profiles. Control channels (very small blocks, high
reliability) need BG2; data channels (large blocks, high
throughput) need BG1. One base graph optimized for both would
be a compromise.

10.2 The Lifting (Expansion) Process

Given a base graph with entries {a_{ij}} (shift values) and a lifting
factor z:

The actual H is size (m_b × z) × (n_b × z)

Each entry a_{ij} becomes a z×z cyclic permutation matrix

P^{a_{ij}}

Each -1 entry (null) becomes a z×z zero matrix

Lifting sets: 5G defines lifting factor z from a set of 51 possible

values from 2 to 384, organized in 8 "lifting sets" {z_0, 2z_0, 4z_0,
8z_0, ...}. The shift values in the base graph are specified modulo
each z in its set, so the same base graph works for many block
lengths.

Why this design:

Supports a wide range of transport block sizes without

redesigning the code

Enables the same hardware architecture to decode different

code sizes just by changing z

Different z values → different parallelism in hardware

10.3 HARQ Support and the Circular Buffer

LDPC in 5G is designed for Hybrid ARQ (HARQ):

After encoding with LDPC, all n codeword bits are written to a
"circular buffer." For the initial transmission, bits are read starting
from position 0 (or another "redundancy version" starting point).
If the receiver can't decode, the transmitter sends additional bits
(from a different position in the buffer). The receiver combines all
received signals using Chase combining or incremental
redundancy.

Redundancy Versions (RV): 5G defines 4 starting positions (RV0,

RV1, RV2, RV3) in the circular buffer. Each retransmission starts
from a different position, maximizing the new information
provided.

Design implication: The first ~20% of coded bits (the "systematic"

part) should always be sent first (RV0). The LDPC code is
designed with the systematic bits at the beginning of the
codeword, and the structure ensures that even with high
puncturing ratio, the systematic bits are protected.

10.4 The Encoding Algorithm

LDPC encoding requires finding x such that H·x^T = 0 and the first
k bits of x equal the information bits.

For a general H, this requires Gaussian elimination — O(n²)

complexity. For 5G LDPC codes, the structure of H is specially
designed for approximately lower-triangular encoding:

The H matrix, after separating systematic bits from parity bits:

H = [H_A | H_B]

where H_B has a specific structure that enables back-substitution

encoding in O(n) time.
The first m-z parity bits are computed by back-substitution (due
to the lower-triangular structure of H_B[0:m-z, :]). The last z parity
bits require one additional step (solving a small z×z system).

Overall encoding complexity: O(n) — linear in code length.

10.5 Performance Numbers

For 5G NR LDPC with BG1, code rate 1/2, block length n ≈ 4000:

Waterfall at Eb/N0 ≈ 0.8-1.0 dB (Shannon limit: 0 dB for rate

1/2 BPSK)

Gap to Shannon: ~0.8-1.0 dB at BER 10^-5

Error floor: below BER 10^-6 for standard puncturing patterns

At larger block lengths (n ≈ 8448), the gap shrinks to ~0.5 dB.

PART XI: THE FULL OPTIMIZATION

STACK — SUMMARY TABLE

Level Optimization Gain Cost

÷5
Algorithm Min-Sum vs SPA -0.3 dB
complexity

+0.2 dB vs ×1
Algorithm Normalized Min-Sum
MS multiplication

+0.2 dB vs + constant
Algorithm Offset Min-Sum
MS subtract
 Level Optimization Gain Cost

Sequential
~0 dB, 2×
Scheduling Layered vs Flooding layer
fewer iters
dependency

~40%
Syndrome
Stopping Early termination power
check per iter
savings

-0.1-0.15 Much smaller

Quantization 6-bit vs float
dB hardware

z×
Structure QC-LDPC ~0 dB
parallelism

Trapping set-free Eliminates Code design

Error floor
design floor complexity

+1-2
Extra
orders of
Post-proc Bit-flip / Noise inject decoder
magnitude
passes
BER

~0.5 dB ~k² Gaussian

Post-proc OSD-0 after BP
near floor elimination

Careful rate-
Flexible
Rate Puncturing/Shortening matching
rates
design

PART XII: FURTHER READING — THE

CANONICAL SOURCES
Primary References (Read in This Order)

Foundations

1. Shannon (1948): "A Mathematical Theory of Communication"

— The original. Read it.

2. Gallager (1963): "Low-Density Parity-Check Codes" — MIT

Press. The source. Gallager's iterative decoder is in here.

3. Berrou et al. (1993): "Near Shannon Limit Error-Correcting

Coding and Decoding: Turbo Codes" — ICC 1993.

LDPC Renaissance

4. MacKay & Neal (1996): "Near Shannon Limit Performance of

Low Density Parity Check Codes" — Electronics Letters.

5. Richardson & Urbanke (2001): "The Capacity of Low-Density

Parity-Check Codes Under Message-Passing Decoding" —
IEEE Trans. IT. The density evolution paper.

6. Richardson, Shokrollahi & Urbanke (2001): "Design of

Capacity-Approaching Irregular Low-Density Parity-Check
Codes" — IEEE Trans. IT.

Algorithms

7. Chen, Dholakia, Eleftheriou, Fossorier, Hu (2005): "Reduced-

Complexity Decoding of LDPC Codes" — IEEE Trans. Comms.
Covers NMS and OMS in detail.

8. Hocevar (2004): "A reduced complexity decoder architecture

via layered decoding of LDPC codes" — IEEE SIPS. The
definitive layered scheduling paper.

Theory

9. Forney (2001): "Codes on graphs: Normal realizations" —

IEEE Trans. IT. Connects everything.
10. Richardson & Urbanke: "Modern Coding Theory" —
Cambridge University Press 2008. The definitive textbook.
Free preprint available.

Practical

11. NPTEL — Andrew Thangaraj: "Error Correcting Codes" lecture

series (YouTube/NPTEL). Excellent, rigorous, free.

12. 3GPP TS 38.212: The actual 5G NR LDPC specification. Read

Sections 5.3 and 5.4.

Advanced

13. Fossorier, Mihaljevic, Imai (1999): "Reduced Complexity

Iterative Decoding of Low-Density Parity Check Codes Based
on Belief Propagation" — Min-Sum paper.

14. Feldman (2003): "Decoding Error-Correcting Codes via Linear

Programming" — PhD thesis, MIT. LP decoding.

15. Dolecek, Zhang, Anantharam, Wainwright, Nikolic: Various

papers on trapping sets and error floors (2008-2012).

APPENDIX: KEY FORMULAS CHEAT

SHEET

Channel Model (AWGN, BPSK)

Transmitted: x ∈ {+1, -1} (mapping: bit 0 → +1, bit 1 → -1)

Received: y = x + n, n ~ N(0, σ²)

Channel LLR: L_ch = 2y/σ² = 4E_s/N_0 · y (where E_s is

symbol energy)

σ² = N_0/2; E_b/N_0 = E_s/(R·N_0)

SPA Check Node Update (exact)

L_{c→v} = 2·arctanh( ∏_{v'≠v} tanh(L_{v'→c}/2) )

Min-Sum Check Node Update (approximate)

L_{c→v} = (∏_{v'≠v} sign(L_{v'→c})) · min_{v'≠v}

|L_{v'→c}|

Normalized Min-Sum

L_{c→v}^{NMS} = α · (∏ sign) · min |L|, α ≈ 0.75-

0.875

Offset Min-Sum

L_{c→v}^{OMS} = (∏ sign) · max(0, min |L| - β), β

≈ 0.15-0.5

Variable Node Update

L_{v→c} = L_ch(v) + Σ_{c'≠c} L_{c'→v}

L_post(v) = L_ch(v) + Σ_{all c} L_{c→v}

Shannon Capacity (AWGN, bits/channel use)

C = log₂(1 + E_s/N_0) [complex channel]

C = ½·log₂(1 + 2R·E_b/N_0) [at rate R, binary input]
Code Rate (QC-LDPC)

R ≈ 1 - m_b/n_b = k_b/n_b [approximately, ignoring

punctured bits]

For BG1: R_max = 22/24 ≈ 8/9; For BG2: R_max = 10/12 ≈ 5/6

Guide synthesized from: Richardson & Urbanke "Modern Coding

Theory," MacKay "Information Theory, Inference, and Learning
Algorithms" (free online), Chen et al. 2005 (NMS/OMS), Hocevar
2004 (layered decoding), NPTEL lecture series by Thangaraj and
Budhiraja, 3GPP TS 38.212 v18.x, "Channel Coding Toward 6G"
(Rowshan et al., arXiv 2405.07547), and "Demystifying 5G Polar and
LDPC Codes" (arXiv 2502.11053).