FA-72171 / Error-correcting codes / Open access

QR format BCH division skips the lowest step · case 01

Remainders are left unreduced for some data values.

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

ROOT CAUSE

The polynomial division loop stops before bit 10.

VERIFIED REPAIR

Reduce for every bit from 14 down to 10.

Unsuccessful approach: Starting the loop at bit 13 leaves the top bit unreduced.

Case contract

QR code format information, a BCH(15,5) code. "encode" takes [level, mask] with level bits L=01, M=00, Q=11, H=10 and mask 0..7 (else None): data = level<<3 | mask, append the 10-bit remainder of data*x^10 modulo 0x537, then XOR 0x5412. "decode" takes a 15-bit integer and returns [level, mask, distance] for the unique format word within Hamming distance 3, else None.

Why this case matters

QR readers must recover the error-correction level and mask pattern before decoding any data module.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(op, x):
    EC = {'L': 1, 'M': 0, 'Q': 3, 'H': 2}
    def enc(level, mask):
        data = (EC[level] << 3) | mask
        rem = data << 10
        for i in range(14, 10, -1):
            if rem & (1 << i):
                rem ^= 0x537 << (i - 10)
        return ((data << 10) | rem) ^ 0x5412
    if op == 'encode':
        level, mask = x
        if level not in EC or not 0 <= mask <= 7:
            return None
        return enc(level, mask)
    best = None
    for level in 'LMQH':
        for mask in range(8):
            dist = bin(enc(level, mask) ^ x).count('1')
            if dist <= 3 and (best is None or dist < best[2]):
                best = [level, mask, dist]
    return best
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression ["encode", ["L", 3]]', ['encode', ['L', 3]], 30877], ['regression ["encode", ["M", 3]]', ['encode', ['M', 3]], 23371], ['partial-repair ["encode", ["Q", 0]]', ['encode', ['Q', 0]], 13663], ['partial-repair ["encode", ["Q", 3]]', ['encode', ['Q', 3]], 14854], ['control ["encode", ["L", 0]]', ['encode', ['L', 0]], 30660], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368], ['control ["encode", ["L", 7]]', ['encode', ['L', 7]], 26998], ['control ["encode", ["M", 0]]', ['encode', ['M', 0]], 21522]], [['regression ["encode", ["Q", 5]]', ['encode', ['Q', 5]], 8579], ['regression ["encode", ["Q", 7]]', ['encode', ['Q', 7]], 11245], ['partial-repair ["encode", ["H", 0]]', ['encode', ['H', 0]], 5769], ['control ["encode", ["M", 7]]', ['encode', ['M', 7]], 19104], ['control ["decode", 30660]', ['decode', 30660], ['L', 0, 0]], ['control ["encode", ["X", 1]]', ['encode', ['X', 1]], None], ['control ["encode", ["L", 8]]', ['encode', ['L', 8]], None], ['control ["decode", 0]', ['decode', 0], None]], [['regression ["encode", ["H", 5]]', ['encode', ['H', 5]], 597], ['regression ["encode", ["H", 7]]', ['encode', ['H', 7]], 2107], ['control ["decode", 32767]', ['decode', 32767], None], ['control ["decode", 21522]', ['decode', 21522], ['M', 0, 0]], ['control ["decode", 21525]', ['decode', 21525], ['M', 0, 3]], ['control ["decode", 21533]', ['decode', 21533], None], ['control ["encode", ["L", 0]]', ['encode', ['L', 0]], 30660], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368]], [['regression ["decode", 6616]', ['decode', 6616], ['H', 3, 1]], ['regression ["decode", 20345]', ['decode', 20345], ['M', 4, 3]], ['partial-repair ["decode", 19724]', ['decode', 19724], ['H', 6, 1]], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368], ['control ["encode", ["L", 7]]', ['encode', ['L', 7]], 26998], ['control ["encode", ["M", 0]]', ['encode', ['M', 0]], 21522], ['control ["encode", ["M", 5]]', ['encode', ['M', 5]], 16590], ['control ["encode", ["M", 7]]', ['encode', ['M', 7]], 19104]], [['regression ["decode", 2309]', ['decode', 2309], ['H', 6, 3]], ['regression ["decode", 2099]', ['decode', 2099], ['H', 7, 1]], ['partial-repair ["encode", ["Q", 0]]', ['encode', ['Q', 0]], 13663], ['control ["decode", 30660]', ['decode', 30660], ['L', 0, 0]], ['control ["encode", ["X", 1]]', ['encode', ['X', 1]], None], ['control ["encode", ["L", 8]]', ['encode', ['L', 8]], None], ['control ["decode", 0]', ['decode', 0], None], ['control ["decode", 32767]', ['decode', 32767], None]]]
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 fixture	Actual	Expected	Outcome
regression ["encode", ["L", 3]]	`31146`	`30877`	Failed
regression ["encode", ["M", 3]]	`23164`	`23371`	Failed
partial-repair ["encode", ["Q", 0]]	`12392`	`13663`	Failed
partial-repair ["encode", ["Q", 3]]	`14854`	`14854`	Passed
control ["encode", ["L", 0]]	`30660`	`30660`	Passed
control ["encode", ["L", 5]]	`25368`	`25368`	Passed
control ["encode", ["L", 7]]	`26998`	`26998`	Passed
control ["encode", ["M", 0]]	`21522`	`21522`	Passed

SHA-256 / 96722b624599513359fb6e5b442f0b3564cef04880f3414addfc275884fccf3c

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(op, x):
    EC = {'L': 1, 'M': 0, 'Q': 3, 'H': 2}
    def enc(level, mask):
        data = (EC[level] << 3) | mask
        rem = data << 10
        for i in range(13, 9, -1):
            if rem & (1 << i):
                rem ^= 0x537 << (i - 10)
        return ((data << 10) | rem) ^ 0x5412
    if op == 'encode':
        level, mask = x
        if level not in EC or not 0 <= mask <= 7:
            return None
        return enc(level, mask)
    best = None
    for level in 'LMQH':
        for mask in range(8):
            dist = bin(enc(level, mask) ^ x).count('1')
            if dist <= 3 and (best is None or dist < best[2]):
                best = [level, mask, dist]
    return best
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression ["encode", ["L", 3]]', ['encode', ['L', 3]], 30877], ['regression ["encode", ["M", 3]]', ['encode', ['M', 3]], 23371], ['partial-repair ["encode", ["Q", 0]]', ['encode', ['Q', 0]], 13663], ['partial-repair ["encode", ["Q", 3]]', ['encode', ['Q', 3]], 14854], ['control ["encode", ["L", 0]]', ['encode', ['L', 0]], 30660], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368], ['control ["encode", ["L", 7]]', ['encode', ['L', 7]], 26998], ['control ["encode", ["M", 0]]', ['encode', ['M', 0]], 21522]], [['regression ["encode", ["Q", 5]]', ['encode', ['Q', 5]], 8579], ['regression ["encode", ["Q", 7]]', ['encode', ['Q', 7]], 11245], ['partial-repair ["encode", ["H", 0]]', ['encode', ['H', 0]], 5769], ['control ["encode", ["M", 7]]', ['encode', ['M', 7]], 19104], ['control ["decode", 30660]', ['decode', 30660], ['L', 0, 0]], ['control ["encode", ["X", 1]]', ['encode', ['X', 1]], None], ['control ["encode", ["L", 8]]', ['encode', ['L', 8]], None], ['control ["decode", 0]', ['decode', 0], None]], [['regression ["encode", ["H", 5]]', ['encode', ['H', 5]], 597], ['regression ["encode", ["H", 7]]', ['encode', ['H', 7]], 2107], ['control ["decode", 32767]', ['decode', 32767], None], ['control ["decode", 21522]', ['decode', 21522], ['M', 0, 0]], ['control ["decode", 21525]', ['decode', 21525], ['M', 0, 3]], ['control ["decode", 21533]', ['decode', 21533], None], ['control ["encode", ["L", 0]]', ['encode', ['L', 0]], 30660], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368]], [['regression ["decode", 6616]', ['decode', 6616], ['H', 3, 1]], ['regression ["decode", 20345]', ['decode', 20345], ['M', 4, 3]], ['partial-repair ["decode", 19724]', ['decode', 19724], ['H', 6, 1]], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368], ['control ["encode", ["L", 7]]', ['encode', ['L', 7]], 26998], ['control ["encode", ["M", 0]]', ['encode', ['M', 0]], 21522], ['control ["encode", ["M", 5]]', ['encode', ['M', 5]], 16590], ['control ["encode", ["M", 7]]', ['encode', ['M', 7]], 19104]], [['regression ["decode", 2309]', ['decode', 2309], ['H', 6, 3]], ['regression ["decode", 2099]', ['decode', 2099], ['H', 7, 1]], ['partial-repair ["encode", ["Q", 0]]', ['encode', ['Q', 0]], 13663], ['control ["decode", 30660]', ['decode', 30660], ['L', 0, 0]], ['control ["encode", ["X", 1]]', ['encode', ['X', 1]], None], ['control ["encode", ["L", 8]]', ['encode', ['L', 8]], None], ['control ["decode", 0]', ['decode', 0], None], ['control ["decode", 32767]', ['decode', 32767], None]]]
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 fixture	Actual	Expected	Outcome
regression ["encode", ["L", 3]]	`30877`	`30877`	Passed
regression ["encode", ["M", 3]]	`23371`	`23371`	Passed
partial-repair ["encode", ["Q", 0]]	`14276`	`13663`	Failed
partial-repair ["encode", ["Q", 3]]	`14493`	`14854`	Failed
control ["encode", ["L", 0]]	`30660`	`30660`	Passed
control ["encode", ["L", 5]]	`25368`	`25368`	Passed
control ["encode", ["L", 7]]	`26998`	`26998`	Passed
control ["encode", ["M", 0]]	`21522`	`21522`	Passed

SHA-256 / 2fe7f0dfcb8f810eb6b88bf97017f8257ebb9885d9726b7020cf3601f69b8c1f

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(op, x):
    EC = {'L': 1, 'M': 0, 'Q': 3, 'H': 2}
    def enc(level, mask):
        data = (EC[level] << 3) | mask
        rem = data << 10
        for i in range(14, 9, -1):
            if rem & (1 << i):
                rem ^= 0x537 << (i - 10)
        return ((data << 10) | rem) ^ 0x5412
    if op == 'encode':
        level, mask = x
        if level not in EC or not 0 <= mask <= 7:
            return None
        return enc(level, mask)
    best = None
    for level in 'LMQH':
        for mask in range(8):
            dist = bin(enc(level, mask) ^ x).count('1')
            if dist <= 3 and (best is None or dist < best[2]):
                best = [level, mask, dist]
    return best
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression ["encode", ["L", 3]]', ['encode', ['L', 3]], 30877], ['regression ["encode", ["M", 3]]', ['encode', ['M', 3]], 23371], ['partial-repair ["encode", ["Q", 0]]', ['encode', ['Q', 0]], 13663], ['partial-repair ["encode", ["Q", 3]]', ['encode', ['Q', 3]], 14854], ['control ["encode", ["L", 0]]', ['encode', ['L', 0]], 30660], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368], ['control ["encode", ["L", 7]]', ['encode', ['L', 7]], 26998], ['control ["encode", ["M", 0]]', ['encode', ['M', 0]], 21522]], [['regression ["encode", ["Q", 5]]', ['encode', ['Q', 5]], 8579], ['regression ["encode", ["Q", 7]]', ['encode', ['Q', 7]], 11245], ['partial-repair ["encode", ["H", 0]]', ['encode', ['H', 0]], 5769], ['control ["encode", ["M", 7]]', ['encode', ['M', 7]], 19104], ['control ["decode", 30660]', ['decode', 30660], ['L', 0, 0]], ['control ["encode", ["X", 1]]', ['encode', ['X', 1]], None], ['control ["encode", ["L", 8]]', ['encode', ['L', 8]], None], ['control ["decode", 0]', ['decode', 0], None]], [['regression ["encode", ["H", 5]]', ['encode', ['H', 5]], 597], ['regression ["encode", ["H", 7]]', ['encode', ['H', 7]], 2107], ['control ["decode", 32767]', ['decode', 32767], None], ['control ["decode", 21522]', ['decode', 21522], ['M', 0, 0]], ['control ["decode", 21525]', ['decode', 21525], ['M', 0, 3]], ['control ["decode", 21533]', ['decode', 21533], None], ['control ["encode", ["L", 0]]', ['encode', ['L', 0]], 30660], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368]], [['regression ["decode", 6616]', ['decode', 6616], ['H', 3, 1]], ['regression ["decode", 20345]', ['decode', 20345], ['M', 4, 3]], ['partial-repair ["decode", 19724]', ['decode', 19724], ['H', 6, 1]], ['control ["encode", ["L", 5]]', ['encode', ['L', 5]], 25368], ['control ["encode", ["L", 7]]', ['encode', ['L', 7]], 26998], ['control ["encode", ["M", 0]]', ['encode', ['M', 0]], 21522], ['control ["encode", ["M", 5]]', ['encode', ['M', 5]], 16590], ['control ["encode", ["M", 7]]', ['encode', ['M', 7]], 19104]], [['regression ["decode", 2309]', ['decode', 2309], ['H', 6, 3]], ['regression ["decode", 2099]', ['decode', 2099], ['H', 7, 1]], ['partial-repair ["encode", ["Q", 0]]', ['encode', ['Q', 0]], 13663], ['control ["decode", 30660]', ['decode', 30660], ['L', 0, 0]], ['control ["encode", ["X", 1]]', ['encode', ['X', 1]], None], ['control ["encode", ["L", 8]]', ['encode', ['L', 8]], None], ['control ["decode", 0]', ['decode', 0], None], ['control ["decode", 32767]', ['decode', 32767], None]]]
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 fixture	Actual	Expected	Outcome
regression ["encode", ["L", 3]]	`30877`	`30877`	Passed
regression ["encode", ["M", 3]]	`23371`	`23371`	Passed
partial-repair ["encode", ["Q", 0]]	`13663`	`13663`	Passed
partial-repair ["encode", ["Q", 3]]	`14854`	`14854`	Passed
control ["encode", ["L", 0]]	`30660`	`30660`	Passed
control ["encode", ["L", 5]]	`25368`	`25368`	Passed
control ["encode", ["L", 7]]	`26998`	`26998`	Passed
control ["encode", ["M", 0]]	`21522`	`21522`	Passed

SHA-256 / fa1e87db8c598305dd11d4909527e3e193d0b261d8b53696cdf15c91b554e876

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:36.038430+00:00.

Case digest / d40e3b14326a21f9e3429e0521b7a17e5c100eeb9d6385d7964478115ba5b90a