FAILURE MAP
← Case archive

FA-72321 / Error-correcting codes / Open access

BCH cosets cover only 1..t · case 01

Codes correct fewer errors than requested.

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

ROOT CAUSE

Roots are gathered for 1..t instead of 1..2t (designed distance 2t + 1).

VERIFIED REPAIR

Include cosets of 1 through 2t.

Unsuccessful approach: Stopping the loop at 2t - 2 drops the coset of the largest odd representative 2t - 1.

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, 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, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['regression [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['partial-repair [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['control [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]]], [['regression [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['regression [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['partial-repair [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 0]', [15, 0], None], ['control [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 [31, 3]', [31, 3], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20]], 15]]], [['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]], ['partial-repair [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['partial-repair [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 [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]]], [['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 [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['partial-repair [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['partial-repair [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, 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 [7, 1]', [7, 1], [[[1, 2, 4]], 3]]], [['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]], ['partial-repair [3, 1]', [3, 1], [[[1, 2]], 2]], ['partial-repair [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['control [15, 0]', [15, 0], None], ['control [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, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]]]]
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, 2][[[1, 2, 4]], 3][[[1, 2, 4], [3, 5, 6]], 6]Failed
regression [15, 2][[[1, 2, 4, 8]], 4][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Failed
partial-repair [7, 1][[[1, 2, 4]], 3][[[1, 2, 4]], 3]Passed
control [15, 7][[[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
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
control [15, 3][[[1, 2, 4, 8], [3, 6, 9, 12]], 8][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]Failed
control [15, 4][[[1, 2, 4, 8], [3, 6, 9, 12]], 8][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]Failed

SHA-256 / a29ecb7f475eb9094bd7b09f413a05e0813290088d778a17da1b845abd6462df

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, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['regression [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['partial-repair [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['control [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]]], [['regression [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['regression [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['partial-repair [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 0]', [15, 0], None], ['control [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 [31, 3]', [31, 3], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20]], 15]]], [['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]], ['partial-repair [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['partial-repair [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 [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]]], [['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 [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['partial-repair [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['partial-repair [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, 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 [7, 1]', [7, 1], [[[1, 2, 4]], 3]]], [['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]], ['partial-repair [3, 1]', [3, 1], [[[1, 2]], 2]], ['partial-repair [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['control [15, 0]', [15, 0], None], ['control [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, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]]]]
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, 2][[[1, 2, 4]], 3][[[1, 2, 4], [3, 5, 6]], 6]Failed
regression [15, 2][[[1, 2, 4, 8]], 4][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Failed
partial-repair [7, 1][[], 0][[[1, 2, 4]], 3]Failed
control [15, 7][[[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
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
control [15, 3][[[1, 2, 4, 8], [3, 6, 9, 12]], 8][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]Failed
control [15, 4][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]Failed

SHA-256 / b3965f0f046741d483ca6e3c9070795be9f9daac56cfed049b071540187a4fba

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, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['regression [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['partial-repair [7, 1]', [7, 1], [[[1, 2, 4]], 3]], ['control [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]]], [['regression [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['regression [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['partial-repair [15, 3]', [15, 3], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]], ['control [15, 0]', [15, 0], None], ['control [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 [31, 3]', [31, 3], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20]], 15]]], [['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]], ['partial-repair [31, 1]', [31, 1], [[[1, 2, 4, 8, 16]], 5]], ['partial-repair [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 [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]]], [['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 [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['partial-repair [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]], ['partial-repair [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, 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 [7, 1]', [7, 1], [[[1, 2, 4]], 3]]], [['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]], ['partial-repair [3, 1]', [3, 1], [[[1, 2]], 2]], ['partial-repair [127, 2]', [127, 2], [[[1, 2, 4, 8, 16, 32, 64], [3, 6, 12, 24, 48, 65, 96]], 14]], ['control [15, 0]', [15, 0], None], ['control [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, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]]]]
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, 2][[[1, 2, 4], [3, 5, 6]], 6][[[1, 2, 4], [3, 5, 6]], 6]Passed
regression [15, 2][[[1, 2, 4, 8], [3, 6, 9, 12]], 8][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Passed
partial-repair [7, 1][[[1, 2, 4]], 3][[[1, 2, 4]], 3]Passed
control [15, 7][[[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
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
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 / ce889c67fc8449e3d81d64317a2cd6a00c1b7c3e3796b1159e37c5de34acac4a

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

Case digest / 4eef9b9863b99a292c9e7c8576e0dedd56449fb0e15b9df89bd11aacff379ba0