FA-72024 / Error-correcting codes / Member archive

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

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

Member previewVariant 4 · 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 [[178, 163, 216, 203, 246, 61, 83, 52, 85, 245, 59, 90, 113, 95]]	`[[178, 226, 216, 203, 246, 61, 83, 52, 85, 245, 59, 90, 113, 95], "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.