FA-72022 / Error-correcting codes / Member archive

RS single-error correction accepts a locator beyond the block · case 02

Multi-symbol errors are "corrected" at a wrapped position.

Member previewVariant 2 · 3 implementations · 8 checks per implementation

Case contract

Correct at most one symbol error in a Reed-Solomon codeword with two parity symbols over GF(2^8) (0x11D, roots alpha^0 and alpha^1, alpha = 2). msg lists coefficients highest degree first, so index n-1-i holds degree i. With S0 = msg(1) and S1 = msg(alpha): both zero -> clean; one zero -> uncorrectable; else the error degree is log(S1/S0), which must be < n, and the error value is S0. Return [corrected symbols or None, status].

Why this case matters

Short-block RS codes in barcodes and radio headers correct a single corrupted symbol cheaply.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
regression [[5, 251, 11, 179, 254, 41, 48, 5, 217, 18, 31]]	`[[5, 251, 11, 179, 254, 41, 48, 5, 169, 18, 31], "corrected"]`	`[null, "uncorrectable"]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

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