Given a Tanner graph H (M checks × N variables), integer channel LLRs, offset alpha, budget max_iter, and 6-bit signed quantization: run offset min-sum check updates, with a layered row-by-row schedule that writes each row's check messages back before the next row reads, take a hard decision after every layer, and stop the instant H·x = 0. Output the codeword, the layer where the syndrome first vanished (or -1), and the full final check-to-variable integer matrix — all integer-only, order-independent.
Implemented and verified. The self-contained solution is at ~/ldpc_solution/SOLUTION.md, with runnable code plus tests (ldpc.py, test_ldpc.py, diff_test.py, flooding.py, big_test.py). Full writeup below.
Given a Tanner graph H (M checks × N variables), integer channel LLRs, offset alpha, budget max_iter, and 6-bit signed quantization: run offset min-sum check updates, with a layered row-by-row schedule that writes each row's check messages back before the next row reads, take a hard decision after every layer, and stop the instant H·x = 0. Output the codeword, the layer where the syndrome first vanished (or -1), and the full final check-to-variable integer matrix — all integer-only, order-independent.
1. Offset applied once with one saturation. The correct order is: select the two participating minima → subtract alpha from the single excluded magnitude → floor at zero once → saturate once.
mag = min2 if n == idx else min1
mag -= alpha
if mag < 0: mag = 0
out = sat(signs * s * mag, MIN, MAX) # exactly one saturation
Double-clamping, subtracting alpha from both min1/min2, or subtracting before selecting the minima all corrupt messages.
2. Layered means write-back within the sweep. Update the running posterior immediately after row m:
L[n] += new_c2v[m][n] - old_c2v[m][n]
so row m+1's extrinsic inputs L[n] - c2v[m+1][n] already include row m's contribution. Collecting all row messages first (flooding/Jacobi) is a different algorithm.
3. Lowest-index tie-break. Scan neighbors in ascending order with a strict <. The first edge to attain the minimum owns min1 (and receives min2); all others receive min1. This pins idx deterministically.
Edge case: a degree-1 check has an empty "other edges" set ⇒ magnitude +∞ ⇒ saturates to MAX.
"""Quantized layered offset min-sum LDPC decoder (integer-exact)."""
def sat(x, lo, hi):
return lo if x < lo else (hi if x > hi else x)
def decode(H, channel_llr, alpha, max_iter, q_bits=6, saturate_posterior=False):
"""Layered (row-serial) offset min-sum decoder.
Returns: codeword, stop_layer (0-based global, -1 if never),
messages (full MxN c2v matrix, 0 off supports), iterations.
"""
M, N = len(H), (len(H[0]) if H else 0)
MAX = (1 << (q_bits - 1)) - 1 # symmetric 6-bit range [-31, +31]
MIN = -MAX
rows = [[n for n in range(N) if H[m][n]] for m in range(M)]
c2v = [[0] * N for _ in range(M)]
L = [sat(int(v), MIN, MAX) for v in channel_llr] # positive favors bit 0
def hard():
return [0 if L[n] >= 0 else 1 for n in range(N)]
def syndrome_ok():
for m in range(M):
p = 0
for n in rows[m]:
p ^= (1 if L[n] < 0 else 0)
if p:
return False
return True
layer = -1
for it in range(max_iter):
for m in range(M):
layer += 1
nbrs = rows[m]
if not nbrs:
continue
# 1) snapshot this row's extrinsic variable->check messages
v2c, signs = [], 1
min1 = min2 = None
idx = -1
for n in nbrs:
v = L[n] - c2v[m][n]
v2c.append((n, v))
if v < 0:
signs = -signs
a = -v if v < 0 else v
if min1 is None or a < min1: # strict '<' => lowest index
min2, min1, idx = min1, a, n
elif min2 is None or a < min2:
min2 = a
# 2) write check messages back immediately (layered)
for n, v in v2c:
s = -1 if v < 0 else 1
mag = min2 if n == idx else min1
if mag is None: # degree-1: min over empty set
mag = 1 << 30 # +inf -> saturates to MAX
mag -= alpha # offset ...
if mag < 0:
mag = 0 # ... floored once
new = sat(signs * s * mag, MIN, MAX) # ... one saturation
old = c2v[m][n]
c2v[m][n] = new
L[n] += new - old # visible to the next row
if saturate_posterior:
L[n] = sat(L[n], MIN, MAX)
# 3) hard decision after each layer
if syndrome_ok():
return {"codeword": hard(), "stop_layer": layer,
"messages": c2v, "iterations": it}
return {"codeword": hard(), "stop_layer": -1,
"messages": c2v, "iterations": max_iter}
Declared conventions used: x[n]=1 if L[n]<0; symmetric 6-bit [-31,+31]; saturation on emitted messages (and channel on entry); posterior kept wide unless saturate_posterior=True; stop_layer is the 0-based global layer counter it*M+m. For two's-complement hardware use MAX=(1<<(q_bits-1)), MIN=-(1<<(q_bits-1)).
Float channel input should be quantized first, in one round-then-clamp, so no float arithmetic reaches the message domain:
def quantize_channel(llr_float, scale, q_bits=6):
MAX = (1 << (q_bits - 1)) - 1
return [max(-MAX, min(MAX, int(round(v * scale)))) for v in llr_float]
$ python3 test_ldpc.py
test1 [1, 1, 1] 0 0
test2 [0, 0, 0] 0
tie messages [-4, -4, 4, -4]
alpha messages [0, 0, 0, 0]
range ok
non-convergent [0, 1] -1
degree1 [0] 0
ALL TESTS PASSED
$ python3 diff_test.py
2000 random differential cases match
$ python3 big_test.py
big decode valid, stop_layer 10 iters 0
cases where layered differs from flooding (codeword/stop): 230 /500
BIG TEST PASSED
tie messages [-4,-4,4,-4]: equal-magnitude minima handled with correct sign/offset.alpha messages [0,0,0,0]: offset larger than the minimum floors to 0 exactly once.range ok: all emitted messages remain in [-31,31].non-convergent ... -1: offset erases reliability, syndrome never zero ⇒ stop_layer == -1.# Evidence - Problem class: python-ldpc-sum-product-layered-tanner-schedule-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-01T16:05:52.639Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a quantized LDPC decoder for a supplied Tanner graph: use integer offset min-sum check-node updates with the specified 6-bit quantization, saturation and alpha offset, driven by a layered (serial, row-by-row) schedule where check messages are written back before the next row reads them. The decoder must run at most the given iteration budget, take a hard decision after each layer, and stop the moment the hard decision satisfies H*x=0. Output the exact decoded codeword bits, the layer index at which the syndrome first became zero (or -1 if unused), and the full final check-to-variable message matrix in the declared integer domain so that the result depends only on integer arithmetic and not on floating-point rounding or Python dict/iteration order.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-ldpc-sum-product-layered-tanner-schedule-exactness", "provider": "openrouter", "solved_at": "2026-10-01T16:05:52.640Z", "version": "3.11"}