FAILURE MAP
← Case archive

FA-72326 / Error-correcting codes / Open access

BCH cosets list a coset twice · case 01

The coset list repeats a coset reached from a later representative.

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

ROOT CAUSE

The already-seen check is missing, so a representative inside an earlier coset starts it again.

VERIFIED REPAIR

Skip representatives already contained in any earlier coset.

Unsuccessful approach: Checking only the most recent coset misses members of older 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):
        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]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]], ['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]], ['partial-repair [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['partial-repair [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [15, 0]', [15, 0], None], ['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]], ['control [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]]], [['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]], ['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 [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]]], [['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, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['partial-repair [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['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]]], [['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]], ['partial-repair [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['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]]]]
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], [1, 2, 4]], 3][[[1, 2, 4]], 3]Failed
regression [7, 2][[[1, 2, 4], [1, 2, 4], [3, 5, 6], [1, 2, 4]], 6][[[1, 2, 4], [3, 5, 6]], 6]Failed
partial-repair [15, 2][[[1, 2, 4, 8], [1, 2, 4, 8], [3, 6, 9, 12], [1, 2, 4, 8]], 8][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Failed
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
control [15, 1][[[1, 2, 4, 8], [1, 2, 4, 8]], 4][[[1, 2, 4, 8]], 4]Failed
control [15, 3][[[1, 2, 4, 8], [1, 2, 4, 8], [3, 6, 9, 12], [1, 2, 4, 8], [5, 10], [3, 6, 9, 12]], 10][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]Failed
control [15, 4][[[1, 2, 4, 8], [1, 2, 4, 8], [3, 6, 9, 12], [1, 2, 4, 8], [5, 10], [3, 6, 9, 12], [7, 11, 13, 14], [1, 2, 4, 8]], 14][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]Failed

SHA-256 / 2db9046131139d620a896751535a8b24dd310e75cdccdf307f9e4a623e01ab38

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 cosets and s % n in cosets[-1]:
            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]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]], ['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]], ['partial-repair [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['partial-repair [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [15, 0]', [15, 0], None], ['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]], ['control [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]]], [['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]], ['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 [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]]], [['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, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['partial-repair [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['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]]], [['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]], ['partial-repair [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['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]]]]
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], [1, 2, 4]], 6][[[1, 2, 4], [3, 5, 6]], 6]Failed
partial-repair [15, 2][[[1, 2, 4, 8], [3, 6, 9, 12], [1, 2, 4, 8]], 8][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]Failed
control [12, 2]NoneNonePassed
control [15, 0]NoneNonePassed
control [15, 1][[[1, 2, 4, 8]], 4][[[1, 2, 4, 8]], 4]Passed
control [15, 3][[[1, 2, 4, 8], [3, 6, 9, 12], [1, 2, 4, 8], [5, 10], [3, 6, 9, 12]], 10][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10]], 10]Failed
control [15, 4][[[1, 2, 4, 8], [3, 6, 9, 12], [1, 2, 4, 8], [5, 10], [3, 6, 9, 12], [7, 11, 13, 14], [1, 2, 4, 8]], 14][[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]Failed

SHA-256 / a6ed3afdd88122b7db48e85250cbd01283694c8739b6e4a7593ecb4db227a20f

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]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['control [12, 2]', [12, 2], None], ['control [15, 0]', [15, 0], None], ['control [15, 1]', [15, 1], [[[1, 2, 4, 8]], 4]], ['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]], ['partial-repair [15, 4]', [15, 4], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['partial-repair [31, 2]', [31, 2], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24]], 10]], ['control [15, 0]', [15, 0], None], ['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]], ['control [63, 2]', [63, 2], [[[1, 2, 4, 8, 16, 32], [3, 6, 12, 24, 33, 48]], 12]]], [['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]], ['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 [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]]], [['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, 5]', [31, 5], [[[1, 2, 4, 8, 16], [3, 6, 12, 17, 24], [5, 9, 10, 18, 20], [7, 14, 19, 25, 28]], 20]], ['partial-repair [15, 7]', [15, 7], [[[1, 2, 4, 8], [3, 6, 9, 12], [5, 10], [7, 11, 13, 14]], 14]], ['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]]], [['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]], ['partial-repair [7, 2]', [7, 2], [[[1, 2, 4], [3, 5, 6]], 6]], ['partial-repair [15, 2]', [15, 2], [[[1, 2, 4, 8], [3, 6, 9, 12]], 8]], ['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]]]]
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
partial-repair [15, 2][[[1, 2, 4, 8], [3, 6, 9, 12]], 8][[[1, 2, 4, 8], [3, 6, 9, 12]], 8]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, 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 / 42db29455cd1a9a2b178b08703d737e3c27d3ebe8c22a301e6bed90b83b93b22

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

Case digest / 36c03fa36815394386a5f66621cca88a369ec870b884a26ef3bfe8ff4a22212f