FAILURE MAP
← Case archive

FA-72081 / Error-correcting codes / Open access

Reed-Muller transform butterfly subtracts in the wrong order · case 01

Correlations for odd u come out negated or misplaced.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The butterfly computes b - a for the lower output.

THE FAILURE

The butterfly computes b - a for the lower output.

Unsuccessful approach: Swapping the two outputs moves the sum to the upper half.

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.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(r):
    if len(r) != 8 or any(b not in (0, 1) for b in r):
        return None
    W = [1 - 2 * b for b in r]
    h = 1
    while h < 8:
        for i in range(0, 8, 2 * h):
            for j in range(i, i + h):
                a, b = W[j], W[j + h]
                W[j], W[j + h] = a + b, b - a
        h *= 2
    best = 0
    for u in range(1, 8):
        if abs(W[u]) > abs(W[best]):
            best = u
    m0 = 0 if W[best] > 0 else 1
    return [[m0, (best >> 2) & 1, (best >> 1) & 1, best & 1], abs(W[best])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[0, 1, 0, 1, 0, 1, 0, 1]]', [[0, 1, 0, 1, 0, 1, 0, 1]], [[0, 0, 0, 1], 8]], ['regression [[0, 1, 0, 1, 0, 1, 0, 0]]', [[0, 1, 0, 1, 0, 1, 0, 0]], [[0, 0, 0, 1], 6]], ['partial-repair [[0, 0, 0, 0, 0, 0, 0, 0]]', [[0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0], 8]], ['partial-repair [[0, 0, 0, 0, 0, 0, 1, 0]]', [[0, 0, 0, 0, 0, 0, 1, 0]], [[0, 0, 0, 0], 6]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 0, 1, 1, 0, 0, 1, 1]]', [[0, 0, 1, 1, 0, 0, 1, 1]], [[0, 0, 1, 0], 8]], ['control [[0, 0, 1, 1, 0, 0, 0, 1]]', [[0, 0, 1, 1, 0, 0, 0, 1]], [[0, 0, 1, 0], 6]], ['control [[0, 1, 1, 0, 0, 1, 1, 0]]', [[0, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 8]]], [['regression [[0, 0, 1, 1, 0, 0, 0, 1]]', [[0, 0, 1, 1, 0, 0, 0, 1]], [[0, 0, 1, 0], 6]], ['regression [[0, 0, 0, 0, 1, 1, 1, 1]]', [[0, 0, 0, 0, 1, 1, 1, 1]], [[0, 1, 0, 0], 8]], ['partial-repair [[0, 1, 0, 1, 0, 1, 0, 0]]', [[0, 1, 0, 1, 0, 1, 0, 0]], [[0, 0, 0, 1], 6]], ['partial-repair [[0, 0, 1, 1, 0, 0, 1, 1]]', [[0, 0, 1, 1, 0, 0, 1, 1]], [[0, 0, 1, 0], 8]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 1, 1, 0, 0, 1, 1, 0]]', [[0, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 8]], ['control [[1, 1, 1, 0, 0, 1, 1, 0]]', [[1, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 6]], ['control [[0, 0, 0, 1, 1, 1, 1, 1]]', [[0, 0, 0, 1, 1, 1, 1, 1]], [[0, 1, 0, 0], 6]]], [['regression [[0, 1, 1, 0, 1, 0, 0, 1]]', [[0, 1, 1, 0, 1, 0, 0, 1]], [[0, 1, 1, 1], 8]], ['regression [[0, 1, 1, 0, 1, 0, 1, 1]]', [[0, 1, 1, 0, 1, 0, 1, 1]], [[0, 1, 1, 1], 6]], ['partial-repair [[0, 1, 1, 0, 0, 1, 1, 0]]', [[0, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 8]], ['partial-repair [[1, 1, 1, 0, 0, 1, 1, 0]]', [[1, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 6]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 1, 0, 0, 1, 0, 1, 0]]', [[0, 1, 0, 0, 1, 0, 1, 0]], [[0, 1, 0, 1], 6]], ['control [[0, 0, 1, 1, 1, 1, 0, 0]]', [[0, 0, 1, 1, 1, 1, 0, 0]], [[0, 1, 1, 0], 8]], ['control [[0, 0, 1, 1, 1, 1, 1, 0]]', [[0, 0, 1, 1, 1, 1, 1, 0]], [[0, 1, 1, 0], 6]]], [['regression [[0, 0, 1, 0, 1, 0, 1, 0]]', [[0, 0, 1, 0, 1, 0, 1, 0]], [[1, 0, 0, 1], 6]], ['regression [[1, 1, 0, 0, 1, 1, 0, 0]]', [[1, 1, 0, 0, 1, 1, 0, 0]], [[1, 0, 1, 0], 8]], ['partial-repair [[0, 0, 0, 1, 1, 1, 1, 1]]', [[0, 0, 0, 1, 1, 1, 1, 1]], [[0, 1, 0, 0], 6]], ['partial-repair [[0, 1, 0, 1, 1, 0, 1, 0]]', [[0, 1, 0, 1, 1, 0, 1, 0]], [[0, 1, 0, 1], 8]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[1, 1, 1, 1, 1, 1, 1, 1]]', [[1, 1, 1, 1, 1, 1, 1, 1]], [[1, 0, 0, 0], 8]], ['control [[1, 1, 0, 1, 1, 1, 1, 1]]', [[1, 1, 0, 1, 1, 1, 1, 1]], [[1, 0, 0, 0], 6]], ['control [[1, 0, 1, 0, 1, 0, 1, 0]]', [[1, 0, 1, 0, 1, 0, 1, 0]], [[1, 0, 0, 1], 8]]], [['regression [[1, 1, 1, 1, 0, 0, 0, 0]]', [[1, 1, 1, 1, 0, 0, 0, 0]], [[1, 1, 0, 0], 8]], ['regression [[0, 1, 1, 1, 0, 0, 0, 0]]', [[0, 1, 1, 1, 0, 0, 0, 0]], [[1, 1, 0, 0], 6]], ['partial-repair [[0, 0, 1, 1, 1, 1, 0, 0]]', [[0, 0, 1, 1, 1, 1, 0, 0]], [[0, 1, 1, 0], 8]], ['partial-repair [[0, 0, 1, 1, 1, 1, 1, 0]]', [[0, 0, 1, 1, 1, 1, 1, 0]], [[0, 1, 1, 0], 6]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 1, 0, 0, 1, 1, 0, 0]]', [[0, 1, 0, 0, 1, 1, 0, 0]], [[1, 0, 1, 0], 6]], ['control [[1, 0, 0, 1, 1, 0, 0, 1]]', [[1, 0, 0, 1, 1, 0, 0, 1]], [[1, 0, 1, 1], 8]], ['control [[1, 0, 0, 1, 1, 1, 0, 1]]', [[1, 0, 0, 1, 1, 1, 0, 1]], [[1, 0, 1, 1], 6]]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
regression [[0, 1, 0, 1, 0, 1, 0, 1]][[1, 0, 0, 1], 8][[0, 0, 0, 1], 8]Failed
regression [[0, 1, 0, 1, 0, 1, 0, 0]][[1, 0, 0, 1], 6][[0, 0, 0, 1], 6]Failed
partial-repair [[0, 0, 0, 0, 0, 0, 0, 0]][[0, 0, 0, 0], 8][[0, 0, 0, 0], 8]Passed
partial-repair [[0, 0, 0, 0, 0, 0, 1, 0]][[0, 0, 0, 0], 6][[0, 0, 0, 0], 6]Passed
control [[0, 1, 2, 0, 0, 0, 0, 0]]NoneNonePassed
control [[0, 0, 1, 1, 0, 0, 1, 1]][[1, 0, 1, 0], 8][[0, 0, 1, 0], 8]Failed
control [[0, 0, 1, 1, 0, 0, 0, 1]][[1, 0, 1, 0], 6][[0, 0, 1, 0], 6]Failed
control [[0, 1, 1, 0, 0, 1, 1, 0]][[0, 0, 1, 1], 8][[0, 0, 1, 1], 8]Passed

SHA-256 / fbd27ec614cea15ab11da21d96a0266fdb0405a7bc3da699291c004c7abbc856

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(r):
    if len(r) != 8 or any(b not in (0, 1) for b in r):
        return None
    W = [1 - 2 * b for b in r]
    h = 1
    while h < 8:
        for i in range(0, 8, 2 * h):
            for j in range(i, i + h):
                a, b = W[j], W[j + h]
                W[j], W[j + h] = a - b, a + b
        h *= 2
    best = 0
    for u in range(1, 8):
        if abs(W[u]) > abs(W[best]):
            best = u
    m0 = 0 if W[best] > 0 else 1
    return [[m0, (best >> 2) & 1, (best >> 1) & 1, best & 1], abs(W[best])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[0, 1, 0, 1, 0, 1, 0, 1]]', [[0, 1, 0, 1, 0, 1, 0, 1]], [[0, 0, 0, 1], 8]], ['regression [[0, 1, 0, 1, 0, 1, 0, 0]]', [[0, 1, 0, 1, 0, 1, 0, 0]], [[0, 0, 0, 1], 6]], ['partial-repair [[0, 0, 0, 0, 0, 0, 0, 0]]', [[0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0], 8]], ['partial-repair [[0, 0, 0, 0, 0, 0, 1, 0]]', [[0, 0, 0, 0, 0, 0, 1, 0]], [[0, 0, 0, 0], 6]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 0, 1, 1, 0, 0, 1, 1]]', [[0, 0, 1, 1, 0, 0, 1, 1]], [[0, 0, 1, 0], 8]], ['control [[0, 0, 1, 1, 0, 0, 0, 1]]', [[0, 0, 1, 1, 0, 0, 0, 1]], [[0, 0, 1, 0], 6]], ['control [[0, 1, 1, 0, 0, 1, 1, 0]]', [[0, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 8]]], [['regression [[0, 0, 1, 1, 0, 0, 0, 1]]', [[0, 0, 1, 1, 0, 0, 0, 1]], [[0, 0, 1, 0], 6]], ['regression [[0, 0, 0, 0, 1, 1, 1, 1]]', [[0, 0, 0, 0, 1, 1, 1, 1]], [[0, 1, 0, 0], 8]], ['partial-repair [[0, 1, 0, 1, 0, 1, 0, 0]]', [[0, 1, 0, 1, 0, 1, 0, 0]], [[0, 0, 0, 1], 6]], ['partial-repair [[0, 0, 1, 1, 0, 0, 1, 1]]', [[0, 0, 1, 1, 0, 0, 1, 1]], [[0, 0, 1, 0], 8]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 1, 1, 0, 0, 1, 1, 0]]', [[0, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 8]], ['control [[1, 1, 1, 0, 0, 1, 1, 0]]', [[1, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 6]], ['control [[0, 0, 0, 1, 1, 1, 1, 1]]', [[0, 0, 0, 1, 1, 1, 1, 1]], [[0, 1, 0, 0], 6]]], [['regression [[0, 1, 1, 0, 1, 0, 0, 1]]', [[0, 1, 1, 0, 1, 0, 0, 1]], [[0, 1, 1, 1], 8]], ['regression [[0, 1, 1, 0, 1, 0, 1, 1]]', [[0, 1, 1, 0, 1, 0, 1, 1]], [[0, 1, 1, 1], 6]], ['partial-repair [[0, 1, 1, 0, 0, 1, 1, 0]]', [[0, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 8]], ['partial-repair [[1, 1, 1, 0, 0, 1, 1, 0]]', [[1, 1, 1, 0, 0, 1, 1, 0]], [[0, 0, 1, 1], 6]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 1, 0, 0, 1, 0, 1, 0]]', [[0, 1, 0, 0, 1, 0, 1, 0]], [[0, 1, 0, 1], 6]], ['control [[0, 0, 1, 1, 1, 1, 0, 0]]', [[0, 0, 1, 1, 1, 1, 0, 0]], [[0, 1, 1, 0], 8]], ['control [[0, 0, 1, 1, 1, 1, 1, 0]]', [[0, 0, 1, 1, 1, 1, 1, 0]], [[0, 1, 1, 0], 6]]], [['regression [[0, 0, 1, 0, 1, 0, 1, 0]]', [[0, 0, 1, 0, 1, 0, 1, 0]], [[1, 0, 0, 1], 6]], ['regression [[1, 1, 0, 0, 1, 1, 0, 0]]', [[1, 1, 0, 0, 1, 1, 0, 0]], [[1, 0, 1, 0], 8]], ['partial-repair [[0, 0, 0, 1, 1, 1, 1, 1]]', [[0, 0, 0, 1, 1, 1, 1, 1]], [[0, 1, 0, 0], 6]], ['partial-repair [[0, 1, 0, 1, 1, 0, 1, 0]]', [[0, 1, 0, 1, 1, 0, 1, 0]], [[0, 1, 0, 1], 8]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[1, 1, 1, 1, 1, 1, 1, 1]]', [[1, 1, 1, 1, 1, 1, 1, 1]], [[1, 0, 0, 0], 8]], ['control [[1, 1, 0, 1, 1, 1, 1, 1]]', [[1, 1, 0, 1, 1, 1, 1, 1]], [[1, 0, 0, 0], 6]], ['control [[1, 0, 1, 0, 1, 0, 1, 0]]', [[1, 0, 1, 0, 1, 0, 1, 0]], [[1, 0, 0, 1], 8]]], [['regression [[1, 1, 1, 1, 0, 0, 0, 0]]', [[1, 1, 1, 1, 0, 0, 0, 0]], [[1, 1, 0, 0], 8]], ['regression [[0, 1, 1, 1, 0, 0, 0, 0]]', [[0, 1, 1, 1, 0, 0, 0, 0]], [[1, 1, 0, 0], 6]], ['partial-repair [[0, 0, 1, 1, 1, 1, 0, 0]]', [[0, 0, 1, 1, 1, 1, 0, 0]], [[0, 1, 1, 0], 8]], ['partial-repair [[0, 0, 1, 1, 1, 1, 1, 0]]', [[0, 0, 1, 1, 1, 1, 1, 0]], [[0, 1, 1, 0], 6]], ['control [[0, 1, 2, 0, 0, 0, 0, 0]]', [[0, 1, 2, 0, 0, 0, 0, 0]], None], ['control [[0, 1, 0, 0, 1, 1, 0, 0]]', [[0, 1, 0, 0, 1, 1, 0, 0]], [[1, 0, 1, 0], 6]], ['control [[1, 0, 0, 1, 1, 0, 0, 1]]', [[1, 0, 0, 1, 1, 0, 0, 1]], [[1, 0, 1, 1], 8]], ['control [[1, 0, 0, 1, 1, 1, 0, 1]]', [[1, 0, 0, 1, 1, 1, 0, 1]], [[1, 0, 1, 1], 6]]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
regression [[0, 1, 0, 1, 0, 1, 0, 1]][[0, 1, 1, 0], 8][[0, 0, 0, 1], 8]Failed
regression [[0, 1, 0, 1, 0, 1, 0, 0]][[0, 1, 1, 0], 6][[0, 0, 0, 1], 6]Failed
partial-repair [[0, 0, 0, 0, 0, 0, 0, 0]][[0, 1, 1, 1], 8][[0, 0, 0, 0], 8]Failed
partial-repair [[0, 0, 0, 0, 0, 0, 1, 0]][[0, 1, 1, 1], 6][[0, 0, 0, 0], 6]Failed
control [[0, 1, 2, 0, 0, 0, 0, 0]]NoneNonePassed
control [[0, 0, 1, 1, 0, 0, 1, 1]][[0, 1, 0, 1], 8][[0, 0, 1, 0], 8]Failed
control [[0, 0, 1, 1, 0, 0, 0, 1]][[0, 1, 0, 1], 6][[0, 0, 1, 0], 6]Failed
control [[0, 1, 1, 0, 0, 1, 1, 0]][[0, 1, 0, 0], 8][[0, 0, 1, 1], 8]Failed

SHA-256 / 8696fcf24e74f9909537a011fd79ab3c80dede88fb4b1ca3bb27e4612e8e0e49

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

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

Sign in to the archive ↗

Verification & scope

A deterministic, bounded teaching model of the named code under the stated contract; not a production codec. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:35.305379+00:00.

Case digest / b28f1107ea0e781691fd8727ebd3eb6c98ff851370c46ec72ff7b1aa63bfdda2