FA-72080 / Error-correcting codes / Member archive

Reed-Muller decoder ignores negative correlation peaks · case 05

Messages with m0 = 1 decode to the wrong linear part.

Member previewVariant 5 · 3 implementations · 8 checks per implementation

Case contract

Maximum-likelihood decoding of the first-order Reed-Muller code RM(1,3) by fast Hadamard transform. Codeword bit x (0..7) is m0 ^ m1*x2 ^ m2*x1 ^ m3*x0 where x2 x1 x0 are the bits of x. Map bit b to 1 - 2b, transform, pick u with the largest |W[u]| (smallest u on ties); m1 m2 m3 are the bits of u from the top, m0 = 0 when W[u] > 0 else 1. Return [[m0, m1, m2, m3], |W[u]|]; invalid input returns None.

Why this case matters

Deep-space and control channels use RM(1,m) codes decoded with the Hadamard transform.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
regression [[1, 1, 0, 0, 0, 0, 1, 1]]	`[[1, 0, 0, 0], 0]`	`[[1, 1, 1, 0], 8]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.