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