You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 

488 lines
19 KiB

"""Forward error correction: QC-LDPC (IRA structure), CRC, interleaver.
LDPC code
---------
Quasi-cyclic, rate-1/2 base graph of mb x nb = 12 x 24 blocks, lifted by Z.
Columns 0..11 carry information, 12..23 parity. The parity part has the
802.11n / 5G-NR shape: a weight-3 first column (shifts 1, 0, 1 at the top,
middle and bottom rows) followed by a dual-diagonal staircase of identity
circulants. Every parity column has weight >= 2; a plain staircase ends in a
weight-1 column, which creates codewords of weight ~7 whenever an info column's
checks sit near the bottom. Encoding stays linear time (running XOR):
S_i = XOR_c rot(u_c, s_ic) (row-block syndrome of the info part)
P_0 = XOR_i S_i (the two shift-1 terms cancel)
P_1 = S_0 ^ rot(P_0, 1)
P_{i+1} = S_i ^ P_i ^ [i == MID] P_0
Info-column degrees are irregular (a few heavy columns pull the threshold in),
row placement is balanced, and circulant shifts are drawn from a seeded PRNG,
rejecting 4-cycles (girth >= 6). The shift tables are deterministic for a
given (Z, seed); format v1 freezes them as tables (ldpc_tables.py, generated
by tools/export_tables.py), which is what get_code() uses.
Short payloads are *shortened*: unused info bits are known zeros that are not
transmitted, and the decoder pins them with a large LLR. Decoding is layered
normalized min-sum with early stop on a zero syndrome.
LLR convention everywhere: L = log P(b=0)/P(b=1) (positive -> bit 0).
"""
import numpy as np
MB, NB = 12, 24
KB = NB - MB
MID = 5 # middle row of the weight-3 parity column
# info-column degrees (sum = 50 edges); heavy columns first
INFO_DEG = [8, 8, 6, 4, 3, 3, 3, 3, 3, 3, 3, 3]
# lift sizes a * 2**j, a in 8..15 (fine steps, like 5G NR's lifting sets), up to 384
Z_SET = tuple(sorted({a << j for a in range(8, 16) for j in range(6) if (a << j) <= 384}))
BIG = 1e3
# ------------------------------------------------------------------ CRC
def _crc_table(poly, width):
top = 1 << (width - 1)
mask = (1 << width) - 1
tab = []
for b in range(256):
c = b << (width - 8)
for _ in range(8):
c = ((c << 1) ^ poly) & mask if c & top else (c << 1) & mask
tab.append(c)
return tab
_CRC16_TAB = _crc_table(0x1021, 16) # CRC-16/CCITT-FALSE
_CRC32_TAB = _crc_table(0x04C11DB7, 32) # CRC-32/MPEG-2 (non-reflected)
def crc16(data: bytes) -> int:
c = 0xFFFF
for b in data:
c = ((c << 8) & 0xFFFF) ^ _CRC16_TAB[((c >> 8) ^ b) & 0xFF]
return c
def crc32(data: bytes) -> int:
c = 0xFFFFFFFF
for b in data:
c = ((c << 8) & 0xFFFFFFFF) ^ _CRC32_TAB[((c >> 24) ^ b) & 0xFF]
return c
def bytes_to_bits(b: bytes) -> np.ndarray:
return np.unpackbits(np.frombuffer(bytes(b), np.uint8))
def bits_to_bytes(bits) -> bytes:
return np.packbits(np.asarray(bits, np.uint8)).tobytes()
# ------------------------------------------------------------------ LDPC
class QCLDPC:
def __init__(self, Z, seed=0x5EED, max_tries=20000, base="frozen"):
"""``base``: "frozen" = the format-v1 table (ldpc_tables.py) when it
has this Z, None = run the construction, or a 12 x 24 shift matrix."""
self.Z = Z
self.k = KB * Z
self.n = NB * Z
if isinstance(base, str):
base = _FROZEN.get(Z)
if base is None:
rng = np.random.default_rng(seed + 7919 * Z)
base = self._build_base(rng, max_tries)
self.base = np.asarray(base, dtype=np.int64) # -1 = zero block
self._build_edges()
# ---- construction
def _build_base(self, rng, max_tries):
Z = self.Z
B = -np.ones((MB, NB), dtype=np.int64)
B[0, KB], B[MID, KB], B[MB - 1, KB] = 1, 0, 1 # weight-3 parity column
for j in range(1, MB): # dual-diagonal staircase
B[j - 1, KB + j] = 0
B[j, KB + j] = 0
rows_w = np.zeros(MB, int)
for c, d in enumerate(INFO_DEG):
# balanced row choice: prefer lightest rows, random tie-break
order = np.lexsort((rng.random(MB), rows_w))
rows = np.sort(order[:min(d, MB)])
rows_w[rows] += 1
for r in rows:
for _ in range(max_tries):
s = int(rng.integers(Z))
B[r, c] = s
if not self._has_4cycle(B, r, c):
break
else:
raise RuntimeError(f"no 4-cycle-free shift for Z={Z} at ({r},{c})")
return B
def _has_4cycle(self, B, r, c):
Z = self.Z
for r2 in range(MB):
if r2 == r or B[r2, c] < 0:
continue
for c2 in range(NB):
if c2 == c or B[r, c2] < 0 or B[r2, c2] < 0:
continue
if (B[r, c] - B[r, c2] + B[r2, c2] - B[r2, c]) % Z == 0:
return True
return False
def _build_edges(self):
Z = self.Z
r = np.arange(Z)
self.layers = [] # per block-row: (Z, d) variable indices
for i in range(MB):
cols = [c * Z + (r + self.base[i, c]) % Z
for c in range(NB) if self.base[i, c] >= 0]
self.layers.append(np.stack(cols, axis=1))
# ---- encode
def encode(self, u):
"""u: k info bits -> n-bit codeword [u | p]."""
Z = self.Z
U = np.asarray(u, np.uint8).reshape(KB, Z)
S = np.zeros((MB, Z), np.uint8)
for i in range(MB):
for c in range(KB):
sh = self.base[i, c]
if sh >= 0:
S[i] ^= np.roll(U[c], -sh)
P = np.zeros((MB, Z), np.uint8)
P[0] = np.bitwise_xor.reduce(S, axis=0)
P[1] = S[0] ^ np.roll(P[0], -1)
for i in range(1, MB - 1):
P[i + 1] = S[i] ^ P[i] ^ (P[0] if i == MID else 0)
return np.concatenate([U.reshape(-1), P.reshape(-1)])
def syndrome_ok(self, cw):
cw = np.asarray(cw, np.uint8)
return all(not np.any(np.bitwise_xor.reduce(cw[V], axis=1)) for V in self.layers)
# ---- decode
def decode(self, llr, max_iter=50, alpha=0.8, state=None):
"""Layered normalized min-sum. Returns (hard codeword, ok, iterations).
With ``state`` (a dict, initially empty) the decoder warm-starts from its
previous check messages: the posterior is shifted by the change in channel
LLRs, and on return state['L'] holds the posterior, so the extrinsic
output is state['L'] - llr.
"""
llr = np.asarray(llr, np.float64)
if state is not None and "R" in state:
R = state["R"]
L = state["L"] - state["Lch"] + llr
else:
R = [np.zeros(V.shape) for V in self.layers]
L = llr.copy()
if state is not None:
state["R"], state["Lch"] = R, llr.copy()
result = None
for it in range(1, max_iter + 1):
for V, Ri in zip(self.layers, R):
T = L[V] - Ri
a = np.abs(T)
sgn = np.where(T < 0, -1.0, 1.0)
sp = np.prod(sgn, axis=1, keepdims=True)
i1 = np.argmin(a, axis=1)
m1 = a[np.arange(len(a)), i1]
a2 = a.copy()
a2[np.arange(len(a)), i1] = np.inf
m2 = a2.min(axis=1)
mag = np.where(np.arange(a.shape[1])[None, :] == i1[:, None],
m2[:, None], m1[:, None])
Rn = alpha * sp * sgn * mag
L[V] = T + Rn
Ri[...] = Rn
hard = (L < 0).astype(np.uint8)
if self.syndrome_ok(hard):
result = (hard, True, it)
break
if result is None:
result = ((L < 0).astype(np.uint8), False, max_iter)
if state is not None:
state["L"] = L
return result
def low_weight_profile(code):
"""Exact weights of all codewords generated by 1 or 2 information bits.
QC structure: the codeword for info bit (c, t) is the codeword for (c, 0)
with every block cyclically rolled by t, so for a pair of columns the
weights over all relative offsets come from one circular correlation per
block: w(t) = |A| + |B| - 2 * sum_b corr(A_b, B_b)(t).
Returns (min weight, number of patterns at that weight).
"""
Z = code.Z
base = []
for c in range(KB):
u = np.zeros(code.k, np.uint8)
u[c * Z] = 1
base.append(code.encode(u).reshape(NB, Z).astype(np.float64))
F = [np.fft.rfft(b, axis=1) for b in base]
wts = [b.sum() for b in base]
best, count = int(min(wts)), int(sum(w == min(wts) for w in wts))
for c1 in range(KB):
for c2 in range(c1, KB):
corr = np.fft.irfft(np.conj(F[c1]) * F[c2], n=Z, axis=1).sum(axis=0)
w = np.rint(wts[c1] + wts[c2] - 2 * corr).astype(int)
if c1 == c2:
w = w[1:]
m = int(w.min())
if m < best:
best, count = m, int((w == m).sum())
elif m == best:
count += int((w == m).sum())
return best, count
# Construction seed per lift size, chosen offline by tools/ldpc_search.py
# (largest minimum weight over 1- and 2-info-bit codewords). Lift sizes not
# listed fall back to DEFAULT_SEED.
DEFAULT_SEED = 0x5EED
SEED_TABLE = {
8: 27, 9: 30, 10: 4, 11: 15, 12: 16, 13: 9,
14: 11, 15: 27, 16: 28, 18: 26, 20: 4, 22: 11,
24: 20, 26: 10, 28: 19, 30: 13, 32: 20, 36: 20,
40: 4, 44: 24, 48: 10, 52: 6, 56: 15, 60: 10,
64: 22, 72: 3, 80: 9, 88: 7, 96: 24, 104: 19,
112: 0, 120: 31, 128: 23, 144: 7, 160: 1, 176: 10,
192: 9, 208: 8, 224: 25, 240: 14, 256: 6, 288: 18,
320: 24, 352: 11, 384: 5,
}
try:
from ldpc_tables import BASE as _FROZEN # normative tables (format v1)
except ImportError:
_FROZEN = {}
_CODES = {}
def get_code(Z):
if Z not in _CODES:
_CODES[Z] = QCLDPC(Z, seed=SEED_TABLE.get(Z, DEFAULT_SEED))
return _CODES[Z]
# ------------------------------------------------------------------ payload codec
def choose_Z(n_info_bits):
for Z in Z_SET:
if KB * Z >= n_info_bits:
return Z
raise ValueError("payload too large for one codeword (SegmentedCodec splits it)")
MAX_SEG_BYTES = (KB * Z_SET[-1] - 32) // 8 # 572: largest one-codeword payload
def segment_sizes(n_bytes):
"""Split n_bytes into the fewest near-equal segments of <= MAX_SEG_BYTES
(earlier segments get the extra byte)."""
c = -(-n_bytes // MAX_SEG_BYTES)
return [n_bytes // c + (1 if i < n_bytes % c else 0) for i in range(c)]
def segment_seed(i):
"""Whitening seed of segment i (segment 0 uses the single-codeword seed)."""
return (0x1FF - 0x2B * i) & 0x1FF or 0x1FF
class SegmentedCodec:
"""A payload of any length up to 2047 B as consecutive codewords.
Payloads up to MAX_SEG_BYTES are exactly one PayloadCodec (identical
on air). Longer ones are split into near-equal segments, each a
PayloadCodec with its own CRC, interleaver and whitening seed, sent one
after another in whole symbols. A frame is delivered only if every
segment's CRC passes.
"""
def __init__(self, n_bytes, bits_per_symbol, rate=0.5):
self.n_bytes, self.bps = n_bytes, bits_per_symbol
self.segs = [PayloadCodec(n, bits_per_symbol, rate=rate, whiten_seed=segment_seed(i))
for i, n in enumerate(segment_sizes(n_bytes))]
self.rows = np.cumsum([0] + [c.n_sym for c in self.segs]) # symbol offsets
self.n_sym = int(self.rows[-1])
@property
def rate(self):
return 8 * self.n_bytes / (self.n_sym * self.bps)
def encode(self, data: bytes):
out, o = [], 0
for c in self.segs:
out.append(c.encode(data[o:o + c.n_bytes]))
o += c.n_bytes
return np.concatenate(out)
def _join(self, results):
ok = all(r[0] is not None for r in results)
info = dict(crc_ok=ok, ldpc_ok=all(r[1]["ldpc_ok"] for r in results),
iters=sum(r[1]["iters"] for r in results),
segments_ok=sum(r[0] is not None for r in results),
post=np.concatenate([r[1]["post"] for r in results]))
return (b"".join(r[0] for r in results) if ok else None), info
def decode(self, llr):
b = self.bps
return self._join([c.decode(llr[self.rows[i] * b:self.rows[i + 1] * b])
for i, c in enumerate(self.segs)])
def decode_iterative(self, demap_rows, **kw):
"""demap_rows(La, a, b): extrinsic LLRs of data symbols a..b-1 (rows
relative to this payload) given their a-priori LLRs."""
res = []
for i, c in enumerate(self.segs):
a, b = int(self.rows[i]), int(self.rows[i + 1])
res.append(c.decode_iterative(lambda La, a=a, b=b: demap_rows(La, a, b), **kw))
return self._join(res)
def pn9(n, seed=0x1FF):
"""PN9 whitening sequence, x^9 + x^5 + 1 (Fibonacci LFSR, 9-bit nonzero seed)."""
state = seed & 0x1FF
out = np.empty(n, np.uint8)
for i in range(n):
b = ((state >> 8) ^ (state >> 4)) & 1
out[i] = state & 1
state = ((state << 1) | b) & 0x1FF
return out
def interleave_index(n_sym, bps):
"""Codeword-slot order: slot i -> (symbol i % n_sym, bit i // n_sym).
Returns perm such that sym_bits.reshape(-1)[perm[i]] = slot i."""
i = np.arange(n_sym * bps)
return (i % n_sym) * bps + (i // n_sym)
class PayloadCodec:
"""Bytes <-> modulator bits: CRC, shortened + punctured QC-LDPC, interleaver.
Rate matching: unused info bits are shortened (known zeros, not sent) and,
when ``rate`` is given, surplus parity is punctured (evenly spread) so the
transmitted rate is ``rate`` regardless of where the payload falls between
lift sizes. ``rate=None`` sends all parity (used for the header, which wants
the extra protection).
Whitening: the modulator bits are XORed with a PN9 sequence, so the symbols
look random whatever the data. Without it a run of zero bits is a run of
plain up-chirps, i.e. a fake preamble.
"""
def __init__(self, n_bytes, bits_per_symbol, crc_bits=None, sym_multiple=1,
rate=0.5, whiten_seed=0x1FF):
self.n_bytes = n_bytes
self.crc_bits = crc_bits or (16 if n_bytes <= 32 else 32)
self.n_info = 8 * n_bytes + self.crc_bits
self.Z = choose_Z(self.n_info)
self.code = get_code(self.Z)
k, n = self.code.k, self.code.n
self.n_short = k - self.n_info # filler zeros, not sent
n_par = n - k
if rate is not None:
n_par = min(n_par, int(np.ceil(self.n_info / rate)) - self.n_info)
self.n_par = n_par # parity bits sent
self.n_punct = (n - k) - n_par
# puncture evenly across the parity block (a contiguous run of punctured
# staircase bits leaves unresolvable chains); par_keep indexes cw[k:]
# drop_j = floor((2j + 1) (n - k) / (2 n_punct)), exact integer arithmetic
drop = ((2 * np.arange(self.n_punct) + 1) * (n - k)) // max(2 * self.n_punct, 1)
keep = np.ones(n - k, bool)
keep[drop] = False
self.par_keep = np.where(keep)[0]
self.n_tx = self.n_info + n_par
self.bps = bits_per_symbol
n_sym = -(-self.n_tx // bits_per_symbol)
self.n_sym = -(-n_sym // sym_multiple) * sym_multiple
self.n_pad = self.n_sym * bits_per_symbol - self.n_tx
self.perm = interleave_index(self.n_sym, bits_per_symbol)
self.pn = pn9(self.n_sym * bits_per_symbol, whiten_seed)
self.wsgn = 1.0 - 2.0 * self.pn # LLR sign flips
@property
def rate(self):
return 8 * self.n_bytes / (self.n_sym * self.bps)
def _crc(self, data):
return crc16(data) if self.crc_bits == 16 else crc32(data)
def encode(self, data: bytes) -> np.ndarray:
assert len(data) == self.n_bytes
crc = self._crc(data).to_bytes(self.crc_bits // 8, "big")
u = np.concatenate([bytes_to_bits(data + crc),
np.zeros(self.n_short, np.uint8)])
cw = self.code.encode(u)
k = self.code.k
tx = np.concatenate([cw[:self.n_info], cw[k:][self.par_keep],
np.zeros(self.n_pad, np.uint8)])
out = np.empty_like(tx)
out[self.perm] = tx
return out ^ self.pn
# ---- slot <-> codeword mapping
def _slots_to_cw(self, slot):
par = np.zeros(self.code.n - self.code.k)
par[self.par_keep] = slot[self.n_info:self.n_tx]
return np.concatenate([slot[:self.n_info], np.full(self.n_short, BIG), par])
def _cw_to_mod(self, cw_vals, pad_val):
k = self.code.k
slot = np.concatenate([cw_vals[:self.n_info], cw_vals[k:][self.par_keep],
np.full(self.n_pad, pad_val)])
out = np.empty_like(slot)
out[self.perm] = slot
return out
def _finish(self, hard, ok, it):
payload = bits_to_bytes(hard[:8 * self.n_bytes])
crc_rx = int.from_bytes(bits_to_bytes(hard[8 * self.n_bytes:self.n_info]), "big")
crc_ok = ok and crc_rx == self._crc(payload)
return (payload if crc_ok else None), dict(ldpc_ok=ok, crc_ok=crc_ok, iters=it)
def decode_iterative(self, demap, outer=10, inner=5, prior_clip=20.0):
"""Iterative demapping and decoding (BICM-ID).
demap(La) -> extrinsic channel LLRs in modulator order, given a-priori
LLRs La in modulator order (zeros on the first pass). Known pad bits
get a strong prior. The LDPC decoder warm-starts between passes and
hands back only its extrinsic information.
"""
n_mod = self.n_sym * self.bps
La = np.zeros(n_mod)
La[self.perm[self.n_tx:]] = prior_clip # pad bits are zeros
state, total = {}, 0
for o in range(outer):
Le = demap(La * self.wsgn) * self.wsgn # de-whiten around demap
Lch = self._slots_to_cw(Le[self.perm])
hard, ok, it = self.code.decode(Lch, max_iter=inner, state=state)
total += it
if ok:
payload, info = self._finish(hard, ok, total)
if info["crc_ok"]:
info["outer"] = o + 1
info["post"] = self.posterior(state["L"])
return payload, info
Ext = np.clip(state["L"] - Lch, -prior_clip, prior_clip)
La = self._cw_to_mod(Ext, prior_clip)
payload, info = self._finish(hard, ok, total)
info["outer"] = outer
info["post"] = self.posterior(state["L"])
return payload, info
def posterior(self, L_cw):
"""Decoder posterior (codeword order) -> LLRs of the on-air bits, in
modulator order: the same domain as the demapper's output."""
return self._cw_to_mod(np.asarray(L_cw, np.float64), BIG) * self.wsgn
def decode(self, sym_llr: np.ndarray):
"""sym_llr: LLRs in modulator bit order (n_sym*bps). -> (bytes|None, info)"""
state = {}
hard, ok, it = self.code.decode(self._slots_to_cw((sym_llr * self.wsgn)[self.perm]),
state=state)
payload, info = self._finish(hard, ok, it)
info["post"] = self.posterior(state["L"])
return payload, info