Reed Solomon FAQ

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

RE: Reed Solomon FAQ

[Ghorai, Sukumar]

> -----Original Message-----
> From: Thomas Gleixner [mailto:tglx@linutronix.de]
> Sent: Monday, June 21, 2010 8:35 PM
> To: linux-mtd@lists.infradead.org
> Cc: Ghorai, Sukumar
> Subject: Reed Solomon FAQ
> 
> 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
[Ghorai] Thanks Gleixner,
It's a very informative email for me.