1. 11 Mar, 2011 1 commit
    • Ivan Djelic's avatar
      lib: add shared BCH ECC library · 437aa565
      Ivan Djelic authored
      This is a new software BCH encoding/decoding library, similar to the shared
      Reed-Solomon library.
      
      Binary BCH (Bose-Chaudhuri-Hocquenghem) codes are widely used to correct
      errors in NAND flash devices requiring more than 1-bit ecc correction; they
      are generally better suited for NAND flash than RS codes because NAND bit
      errors do not occur in bursts. Latest SLC NAND devices typically require at
      least 4-bit ecc protection per 512 bytes block.
      
      This library provides software encoding/decoding, but may also be used with
      ASIC/SoC hardware BCH engines to perform error correction. It is being
      currently used for this purpose on an OMAP3630 board (4bit/8bit HW BCH). It
      has also been used to decode raw dumps of NAND devices with on-die BCH ecc
      engines (e.g. Micron 4bit ecc SLC devices).
      
      Latest NAND devices (including SLC) can exhibit high error rates (typically
      a dozen or more bitflips per hour during stress tests); in order to
      minimize the performance impact of error correction, this library
      implements recently developed algorithms for fast polynomial root finding
      (see bch.c header for details) instead of the traditional exhaustive Chien
      root search; a few performance figures are provided below:
      
      Platform: arm926ejs @ 468 MHz, 32 KiB icache, 16 KiB dcache
      BCH ecc : 4-bit per 512 bytes
      
      Encoding average throughput: 250 Mbits/s
      
      Error correction time (compared with Chien search):
      
              average   worst      average (Chien)  worst (Chien)
      ----------------------------------------------------------
      1 bit    8.5 µs   11 µs         200 µs           383 µs
      2 bit    9.7 µs   12.5 µs       477 µs           728 µs
      3 bit   18.1 µs   20.6 µs       758 µs          1010 µs
      4 bit   19.5 µs   23 µs        1028 µs          1280 µs
      
      In the above figures, "worst" is meant in terms of error pattern, not in
      terms of cache miss / page faults effects (not taken into account here).
      
      The library has been extensively tested on the following platforms: x86,
      x86_64, arm926ejs, omap3630, qemu-ppc64, qemu-mips.
      Signed-off-by: default avatarIvan Djelic <ivan.djelic@parrot.com>
      Signed-off-by: default avatarDavid Woodhouse <David.Woodhouse@intel.com>
      437aa565