FA-72025 / Error-correcting codes / Member archive

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

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

Member previewVariant 5 · 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 [[234, 110, 32, 238, 251, 206, 1, 255, 255, 76, 117]]	`[[234, 41, 32, 238, 251, 206, 1, 255, 255, 76, 117], "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.