FAILURE MAP
← Case archive

FA-72316 / Error-correcting codes / Open access

BCH cosets multiply modulo n plus one · case 01

Cosets collapse to zero and the parity count is wrong.

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

ROOT CAUSE

Successive coset members are computed as 2x mod (n + 1) instead of mod n.

VERIFIED REPAIR

Generate cosets with x -> 2x mod n.

Unsuccessful approach: Adding 2 instead of doubling builds arithmetic progressions, not cyclotomic cosets.

Case contract

Design a binary narrow-sense BCH code of length n = 2^m - 1 correcting t errors: its generator has as roots the union of the 2-cyclotomic cosets mod n of 1..2t. Return [distinct cosets in order of first representative, each sorted, number of parity bits n - k = size of the union]. Invalid n or t < 1 returns None.

Why this case matters

BCH codes in flash memory and satellite links are specified by their cyclotomic cosets.

1 / The failure

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

N = 1
observations = []
def solve(n, t):
    if n < 3 or n & (n + 1) or t < 1:
        return None
    seen, cosets = set(), []
    for s in range(1, 2 * t + 1):
        if s % n in seen:
            continue
        c, x = [], s % n
        while x not in c:
            c.append(x)
            x = x * 2 % (n + 1)
        seen.update(c)
        cosets.append(sorted(c))
    return [cosets, len(seen)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['regression [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]], ['control [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['control [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]]], [['regression [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['regression [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 0]', [15, 0], None], ['control [12, 2]', [12, 2], None], ['control [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [31, 3]', [31, 3], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20]], 15]], ['control [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['control [63, 3]', [63, 3], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48], [5, 10, 17, 20, 34, 40]], 18]]], [['regression [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['regression [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [31, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['control [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [3, 1]', [3, 1], [[[1, 2]], 2]], ['control [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]]], [['regression [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['regression [63, 3]', [63, 3], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48], [5, 10, 17, 20, 34, 40]], 18]], ['control [15, 0]', [15, 0], None], ['control [12, 2]', [12, 2], None], ['control [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['control [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['control [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]]], [['regression [31, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['regression [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['control [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]]]]
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 [7, 1][[[0, 1, 2, 4]], 4][[[1, 2, 4]], 3]Failed
regression [7, 2][[[0, 1, 2, 4], [0, 3, 4, 6]], 6][[[1, 2, 4], [3, 5, 6]], 6]Failed
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
control [15, 1][[[0, 1, 2, 4, 8]], 5][[[1, 2, 4, 8]], 4]Failed
control [15, 2][[[0, 1, 2, 4, 8], [0, 3, 6, 8, 12]], 8][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Failed
control [15, 3][[[0, 1, 2, 4, 8], [0, 3, 6, 8, 12], [0, 4, 5, 8, 10]], 10][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]Failed
control [15, 4][[[0, 1, 2, 4, 8], [0, 3, 6, 8, 12], [0, 4, 5, 8, 10], [0, 7, 8, 12, 14]], 12][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]Failed

SHA-256 / 751a7fb3350c0eb73a94ac02f48a2886d14c139dd38995969817048058dcd4c6

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(n, t):
    if n < 3 or n & (n + 1) or t < 1:
        return None
    seen, cosets = set(), []
    for s in range(1, 2 * t + 1):
        if s % n in seen:
            continue
        c, x = [], s % n
        while x not in c:
            c.append(x)
            x = (x + 2) % n
        seen.update(c)
        cosets.append(sorted(c))
    return [cosets, len(seen)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['regression [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]], ['control [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['control [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]]], [['regression [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['regression [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 0]', [15, 0], None], ['control [12, 2]', [12, 2], None], ['control [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [31, 3]', [31, 3], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20]], 15]], ['control [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['control [63, 3]', [63, 3], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48], [5, 10, 17, 20, 34, 40]], 18]]], [['regression [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['regression [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [31, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['control [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [3, 1]', [3, 1], [[[1, 2]], 2]], ['control [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]]], [['regression [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['regression [63, 3]', [63, 3], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48], [5, 10, 17, 20, 34, 40]], 18]], ['control [15, 0]', [15, 0], None], ['control [12, 2]', [12, 2], None], ['control [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['control [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['control [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]]], [['regression [31, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['regression [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['control [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]]]]
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 [7, 1][[[0, 1, 2, 3, 4, 5, 6]], 7][[[1, 2, 4]], 3]Failed
regression [7, 2][[[0, 1, 2, 3, 4, 5, 6]], 7][[[1, 2, 4], [3, 5, 6]], 6]Failed
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
control [15, 1][[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]], 15][[[1, 2, 4, 8]], 4]Failed
control [15, 2][[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]], 15][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Failed
control [15, 3][[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]], 15][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]Failed
control [15, 4][[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]], 15][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]Failed

SHA-256 / 9cfacaf3ee225d1eb7478e80fd67f94e4e5ff64a129181d4e274678c4ddd4b50

3 / The verified repair

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

N = 1
observations = []
def solve(n, t):
    if n < 3 or n & (n + 1) or t < 1:
        return None
    seen, cosets = set(), []
    for s in range(1, 2 * t + 1):
        if s % n in seen:
            continue
        c, x = [], s % n
        while x not in c:
            c.append(x)
            x = x * 2 % n
        seen.update(c)
        cosets.append(sorted(c))
    return [cosets, len(seen)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['regression [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]], ['control [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['control [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]]], [['regression [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['regression [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 0]', [15, 0], None], ['control [12, 2]', [12, 2], None], ['control [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [31, 3]', [31, 3], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20]], 15]], ['control [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['control [63, 3]', [63, 3], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48], [5, 10, 17, 20, 34, 40]], 18]]], [['regression [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['regression [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [31, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['control [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [3, 1]', [3, 1], [[[1, 2]], 2]], ['control [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]]], [['regression [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['regression [63, 3]', [63, 3], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48], [5, 10, 17, 20, 34, 40]], 18]], ['control [15, 0]', [15, 0], None], ['control [12, 2]', [12, 2], None], ['control [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['control [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['control [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]]], [['regression [31, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['regression [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['control [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['control [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]]]]
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 [7, 1][[[1, 2, 4]], 3][[[1, 2, 4]], 3]Passed
regression [7, 2][[[1, 2, 4], [3, 5, 6]], 6][[[1, 2, 4], [3, 5, 6]], 6]Passed
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
control [15, 1][[[1, 2, 4, 8]], 4][[[1, 2, 4, 8]], 4]Passed
control [15, 2][[[1, 2, 4, 8], [3, 6, 9, 12]], 8][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Passed
control [15, 3][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]Passed
control [15, 4][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]Passed

SHA-256 / c3d36f36f91b00ae275590d321329b59999c3bb83c57c6fa89e7d7151f4900e7

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

Case digest / a4b1055310b3e99efd3cb027fb5d602fb0f4ea76742d5a6209019c2826fb6687