"""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