Jay Taylor's notes

back to listing index

Reed-Solomon error-correcting code decoder

[web search]
Original source (www.nayuki.io)
Tags: algorithms reed-solomon error-correction www.nayuki.io
Clipped on: 2017-02-04


Image (Asset 1/8) alt=

Preliminaries

  1. The Reed-Solomon procedures take place within the framework of a user-chosen field FF. The field is usually GF(28)GF(28) for convenient byte-oriented processing on computers, but it could instead be GF(24)GF(24), GF(212)GF(212), Z73Z73, etc. We need a primitive element / generator αα for the field. The generator must be such that the values {α0,α1,α2,...,α|F|2}{α0,α1,α2,...,α|F|2} are all unique and non-zero; hence the powers of αα generate all the non-zero elements of the field FF. (|F||F| is the size of the field, i.e. the total number of distinct elements/values.)

  2. We choose kk to be the message length. kk is an integer such that 1k<|F|1k<|F|. Each message to be encoded is a sequence/block of kk values from the field FF. For example we might choose k=25k=25 so that each codeword conveys 2525 payload (non-redundant) values. (The case k=0k=0 is obviously degenerate because it means there is no useful information to convey.)

  3. We choose mm to be the number of error correction values by which to expand the message. mm is an integer such that 1m<|F|k1m<|F|k. (The case m=0m=0 is degenerate because it means no RS ECC is added, so the entire message has no protection whatsoever.) Note that when a message is expanded with mm error correction values, the expanded message (a.k.a. codeword) can tolerate up to m/2m/2 errors and still be decoded perfectly. For example, adding 6 EC values will allow us to fix any codeword with up to 3 erroneous values.

  4. We define n=k+mn=k+m to be the block size / codeword length after encoding. Note that nn is a positive integer that satisfies 2n<|F|2n<|F|. So if we want big blocks with a lot of error-correcting capability, then we need a sufficiently large field as the foundation.

Systematic encoder

  1. Reed-Solomon error-correcting codes come in a number of flavors, of equivalent error-correcting power but different pragmatic handling. The variant that we use is the BCH view with systematic encoding, which means that the original message is treated as a sequence of coefficients for a polynomial, and the codeword after encoding is equal to the message with some error-correcting data appended to it.

  2. Define the generator polynomial based on mm and αα:

    g(x)=i=0m1(xαi)=(xα0)(xα1)(xαm1).g(x)=i=0m1(xαi)=(xα0)(xα1)(xαm1).

    This polynomial has degree mm, and its leading coefficient is equal to 11.

  3. Suppose the original message is the sequence of kk values (M0,M1,...,Mk1)(M0,M1,...,Mk1), where each MiMi is an element of field FF. Define the original message polynomial by simply using the values as monomial coefficients:

    M(x)=i=0k1Mixi=M0x0+M1x1++Mk1xk1.M(x)=i=0k1Mixi=M0x0+M1x1++Mk1xk1.

  4. Define and calculate the Reed-Solomon codeword being sent as the message shifted up minus the message polynomial modulo the generator polynomial:

    s(x)=M(x)xm[(M(x)xm) mod g(x)].s(x)=M(x)xm[(M(x)xm) mod g(x)].

    Note that the remainder polynomial [(M(x)xm) mod g(x)][(M(x)xm) mod g(x)] has a degree of m1m1 or less, so the monomial terms of the remainder don’t interact with the terms of (M(x)xm)(M(x)xm). Overall, s(x)s(x) has degree n1n1 or less.

    By construction, the sent codeword polynomial s(x)s(x) has the property that s(x)0 mod g(x)s(x)0 mod g(x); this will be useful shortly in the decoder.

  5. We encode s(x)s(x) into a sequence of values in the straightforward way by breaking it up into nn monomial coefficients:

    s(x)=i=0n1sixi=s0x0+s1x1++sn1xn1.s(x)=i=0n1sixi=s0x0+s1x1++sn1xn1.

    The codeword we transmit is simply the sequence of nn values (s0,s1,,sn1)(s0,s1,,sn1), where each value sisi is an element of the field FF.

Peterson-Gorenstein-Zierler decoder

Calculating syndromes

  1. Suppose the codeword we received is (r0,r1,,rn1)(r0,r1,,rn1), where each value is an element of the field FF. This is known. We defined the received codeword polynomial straightforwardly:

    r(x)=i=0n1rixi=r0x0+r1x1++rn1xn1.r(x)=i=0n1rixi=r0x0+r1x1++rn1xn1.

  2. On the receiving side here, we don’t know the sent values s0,s1,,sn1s0,s1,,sn1, but will go ahead and define the error values anyway. Let e0=r0s0e0=r0s0, e1=r1s1e1=r1s1, , en1=rn1sn1en1=rn1sn1. Define the error polynomial straightforwardly (again, we don’t know its value right now):

    e(x)=r(x)s(x)=i=0n1eixi=e0x0+e1x1++en1xn1.e(x)=r(x)s(x)=i=0n1eixi=e0x0+e1x1++en1xn1.

  3. Now for some actual math: Define the mm syndrome values for 0i<m0i<m, by evaluating the received codeword polynomial at various powers of the generator:

    Si=r(αi)=s(αi)+e(αi)=0+e(αi)=e(αi)=e0α0i+e1α1i++en1α(n1)i.Si=r(αi)=s(αi)+e(αi)=0+e(αi)=e(αi)=e0α0i+e1α1i++en1α(n1)i.

    This works because by construction, s(αi)=0s(αi)=0 for 0i<m0i<m, which is because s(x)s(x) is divisible by (xα0)(xα1)(xαm1)(xα0)(xα1)(xαm1). Thus we see that the syndromes only depend on the errors that were added to the transmitted codeword, and don’t depend at all on the value of the transmitted codeword or the original message.

    If all the syndrome values are zero, then the codeword is already correct, there is nothing to fix, and we are done.

  4. We can show all of these mm syndrome equations explicitly:

    S0S1Sm1=e0α0×0+e1α1×0++en1α(n1)×0.=e0α0×1+e1α1×1++en1α(n1)×1.=e0α0(m1)+e1α1(m1)++en1α(n1)(m1).{S0=e0α0×0+e1α1×0++en1α(n1)×0.S1=e0α0×1+e1α1×1++en1α(n1)×1.Sm1=e0α0(m1)+e1α1(m1)++en1α(n1)(m1).

  5. And rewrite this linear system as a matrix:

    e0α0×0+e1α1×0++en1α(n1)×0e0α0×1+e1α1×1++en1α(n1)×1e0α0(m1)+e1α1(m1)++en1α(n1)(m1)=S0S1Sm1[e0α0×0+e1α1×0++en1α(n1)×0e0α0×1+e1α1×1++en1α(n1)×1e0α0(m1)+e1α1(m1)++en1α(n1)(m1)]=[S0S1Sm1].

  6. And factorize the matrix:

    α0×0α0×1α0(m1)α1×0α1×1α1(m1)α(n1)×0α(n1)×1α(n1)(m1)e0e1en1=S0S1Sm1[α0×0α1×0α(n1)×0α0×1α1×1α(n1)×1α0(m1)α1(m1)α(n1)(m1)][e0e1en1]=[S0S1Sm1].

Finding error locations

  1. Choose νν (Greek lowercase nu) as the number of errors to try to find. We require 1νm/21νm/2. Unless there are time or space constraints, it is best to set νν as large as possible to catch as many errors as the error-correcting code allows.

  2. Let’s pretend we know the νν error locations as I0,I1,,Iν1I0,I1,,Iν1. This is an orderless set of unique indexes into the received codeword of nn values, so each element satisfies 0Ii<n0Ii<n.

    The significance of this set/sequence of indexes IiIi is that the error values at these indexes may be non-zero, but all other error values must be zero. In other words, eI0eI0, eI1eI1, , eIν1eIν1 can each be any value (possibly zero), but the eiei values at other indexes must be zero.

  3. Define some new variables for old values, but based on the error location indexes IiIi, for 0i<ν0i<ν:

    XiYi=αIi.=eIi.Xi=αIi.Yi=eIi.

  4. Because we know all other eiei values are zero, we can substitute the new variables and rewrite the system of syndrome equations as follows:

    X00X10Xm10X01X11Xm11X0ν1X1ν1Xm1ν1Y0Y1Yν1=S0S1Sm1[X00X10Xν10X01X11Xν11X0m1X1m1Xν1m1][Y0Y1Yν1]=[S0S1Sm1].

    (At this point we still don’t know any of the XiXi or YiYi values. However there is a clever multi-step procedure that will reveal them.)

  5. Define the error locator polynomial based on the unknown XiXi variables:

    Λ(x)=i=0ν1(1Xix)=1+Λ1x+Λ2x2++Λνxν.Λ(x)=i=0ν1(1Xix)=1+Λ1x+Λ2x2++Λνxν.

    (In other words, after all the factors are multiplied and expanded, the polynomial Λ(x)Λ(x) has the sequence of ν+1ν+1 monomial coefficients (1,Λ1,Λ2,,Λν)(1,Λ1,Λ2,,Λν).)

  6. By construction we know that for each 0i<ν0i<ν, we have:

    0=Λ(X1i)=1+Λ1X1i+Λ2X2i++ΛνXνi.0=Λ(Xi1)=1+Λ1Xi1+Λ2Xi2++ΛνXiν.

    The polynomial is zero at these points because the product contains the factor (1XiX1i)=11=0(1XiXi1)=11=0.

  7. For 0i<ν0i<ν and arbitrary jZjZ, let’s multiply all sides of the equation by YiXj+νiYiXij+ν:

    (YiXj+νi)0=(Yi