Reed Solomon FAQ

[Thomas Gleixner]

I got repeatedly questions like the following about Reed Solomon
codes:

> Say we have allocated 8bytes in spare area to store the ECC for 512
> bytes data. And we have to correct upto 4-bit in 512-byte data. And
> would you please let me know how to configure the rs-lib for the
> same? Say we are using the 8-bit data(symbol).

It's impossible to use 8bit symbol width for 512 byte data.

      m = number of bits per symbol
      n = code length in symbols up to 2^(m-1)
      k = original data length in symbols
      r = n - k = number of redundant symbols
      t = 1/2 (n-k) = error correction capability (number of symbols)

So for this use case we get for the kernel rs lib:

   k = 512

So for 512 byte data we need a symbol width of 10. The rs lib in the
kernel handles this in the encode/decode_rs8 functions by expanding
the 8 bit FLASH data to 10 bits internally.

   m = 10

If we can store 8 byte == 64bit of redundant symbols in the spare
area, so the number of redundant symbols is:

   r = 64/10 = 6

And the resulting code lenght is:

   n = k + r = 518

So the max. number of correctable symbols is:

   t = 1/2 * 6 = 3

That might be up to 24 bit of corrected data, when the errors are not
scattered over more than 3 bytes on FLASH.

If errors happen on 4 or more different FLASH bytes, they are
uncorrectable.

The 518/512 (10 bit symbol width) code is the optimum which can be
achieved for 512 byte FLASH read/write chunks with 8 byte of spare
area usage.

To correct 4 symbols in a 512 byte data chunk we need at least 8
redundant symbols, which means 80 bit == 10 bytes storage size in the
spare area.

> Is it possible to correct 4-symbols, by max 9-byte parity?

Yes, but that requires that the 512 byte data is converted into a
serialized bitstream w/o symbol width expansion so 9 bit symbol width
can be used.

    m = 9
    k = 456 [ 512 * 8 / 9 rounded up ]
    r = 8 [ 72 / 9 ]
    t = 4

Such modes are only useful when both the encoding and the decoding are
done in hardware, as serializing / deserializing for the software
en/decoder is making the already slow software RS even more horribly
slow.

As a side note: software RS encoding/decoding is performancewise a bad
idea in general.

Thanks,

	tglx