[Yaffs] bit error rates --> a vendor speaks

Thomas Gleixner tglx at linutronix.de
Thu Feb 23 07:36:31 GMT 2006


On Wed, 2006-02-22 at 17:46 -0700, Russ Dill wrote:
> > Depends. The 1bit correction/ 2bit detection Hamming ECC algorithm found
> > in the kernel is not too bad, but Reed Solomon is a quite conmputation
> > expensive algorithm. Look into the encoder / decoder code in
> > lib/reed_solomon.
> 
> 
> Do NAND errors tend to clump in sequences of bits (ie, something reed
> solomon is paticularly good at)?

In tests with AG-AND, which is known to be less reliable, I saw the bits
flip randomly in several consecutive bytes.

> > In general you have to iterate over the data buffer and compute on each
> > step. The performance penalty depends on the complexitiy of the
> > algortihm. If you have enough space in your FPGA then its definitely a
> > good idea to put some ECC calculation mechanism into it. There are
> > implementations for both ECC and Reed Solomon available.
> 
> Care to recommend any?

I dont remember where the Hamming ECC was from, but a Reed Solomon
encoder is available on opencores.org. And there are several generators
out there which produce RS encoder VHDL code from the given parameters.
Someone used this one with success
http://home.arcor.de/christianschuler/software/genenc_v1_2_tar.gz
You need to build the interfaces around though.

Parameters used back then:

-b 10	data width
-n 518	total length of code word
-k 512  number of information words
-m 10	symbol width
-p 10000001001	polynomial

Result below.

Some hints:

Expand the 8 bit data bus to 10 bits by setting the bit 8/9 hard to 1.
Before feeding the resulting 10 bit word into the generator invert them.
Also invert the resulting RS code. The reason is:
code for all data 0x00 is 0 0 0 0 0 0. Empty flash (0xff) expanded with
bit 8/9 feeds 0x3ff to the inverter, which results in 0x000 for the
generator input. Now you invert the resulting code and get 6 words of
0x3ff. That way you need no special checking for all empty flash as the
resulting code will be correct.

	tglx

-------------------------------------------------------------------------------
-- Parallel Reed-Solomon Encoder (ENTITY)
-- automatically generated by program 'genenc_solaris'
-- ./genenc_solaris -e 2 -b 10 -n 518 -k 512 -m 10 -p 10000001001 >
rs_ecc_nand1.vhdl
-- 
-- Date Thu Jun 23 08:07:57 2005
-- 
-------------------------------------------------------------------------------

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;

ENTITY rs_enc IS
    PORT (
        clk     : IN    STD_LOGIC;
        enable  : IN    STD_LOGIC;
        reset   : IN    STD_LOGIC;
        out_enb : OUT   STD_LOGIC;
        d_in    : IN    STD_LOGIC_VECTOR(9 DOWNTO 0);
        d_out   : OUT   STD_LOGIC_VECTOR(9 DOWNTO 0)
    );
END rs_enc;
-------------------------------------------------------------------------------
-- Parallel Reed-Solomon Encoder (ARCHITECTURE)
-- automatically generated by program 'genenc_solaris'
-- 
-- Date Thu Jun 23 08:07:57 2005
-- 
-------------------------------------------------------------------------------

ARCHITECTURE rtl OF rs_enc IS

    CONSTANT nn:     INTEGER := 518;
        -- Number of code symbols

    CONSTANT kk:     INTEGER := 512;
        -- Number of information symbols

    CONSTANT bw:     INTEGER := 10;
        -- Bussize in bits

    CONSTANT mm:     INTEGER := 10;
        -- symbol size in bits

    CONSTANT last_in:  INTEGER := 512;
        -- Last input clock cycle

    CONSTANT last_out: INTEGER := 518;
        -- Last output clock cycle


-------------------------------------------------------------------------------

-- Galois field multiplier functions for Generator Polynomial
-- RS(518,512) encoder:

-- G(0):
    FUNCTION gf_mul_21 ( 
        bb: STD_LOGIC_VECTOR(9 DOWNTO 0))
        RETURN STD_LOGIC_VECTOR IS
        VARIABLE cc_next: STD_LOGIC_VECTOR(9 DOWNTO 0);
            BEGIN
            cc_next(0) := bb(3) XOR bb(9);
            cc_next(1) := bb(0) XOR bb(4);
            cc_next(2) := bb(1) XOR bb(5);
            cc_next(3) := bb(2) XOR bb(3) XOR bb(6) XOR bb(9);
            cc_next(4) := bb(3) XOR bb(4) XOR bb(7);
            cc_next(5) := bb(4) XOR bb(5) XOR bb(8);
            cc_next(6) := bb(5) XOR bb(6) XOR bb(9);
            cc_next(7) := bb(0) XOR bb(6) XOR bb(7);
            cc_next(8) := bb(1) XOR bb(7) XOR bb(8);
            cc_next(9) := bb(2) XOR bb(8) XOR bb(9);
        RETURN cc_next;
    END gf_mul_21;

-- G(1):
    FUNCTION gf_mul_981 ( 
        bb: STD_LOGIC_VECTOR(9 DOWNTO 0))
        RETURN STD_LOGIC_VECTOR IS
        VARIABLE cc_next: STD_LOGIC_VECTOR(9 DOWNTO 0);
            BEGIN
            cc_next(0) := bb(3) XOR bb(6) XOR bb(7) XOR bb(8) XOR bb(9);
            cc_next(1) := bb(0) XOR bb(4) XOR bb(7) XOR bb(8) XOR bb(9);
            cc_next(2) := bb(0) XOR bb(1) XOR bb(5) XOR bb(8) XOR bb(9);
            cc_next(3) := bb(0) XOR bb(1) XOR bb(2) XOR bb(3) XOR bb(7)
XOR 
                bb(8);
            cc_next(4) := bb(0) XOR bb(1) XOR bb(2) XOR bb(3) XOR bb(4)
XOR 
                bb(8) XOR bb(9);
            cc_next(5) := bb(1) XOR bb(2) XOR bb(3) XOR bb(4) XOR bb(5)
XOR 
                bb(9);
            cc_next(6) := bb(2) XOR bb(3) XOR bb(4) XOR bb(5) XOR bb(6);
            cc_next(7) := bb(0) XOR bb(3) XOR bb(4) XOR bb(5) XOR bb(6)
XOR 
                bb(7);
            cc_next(8) := bb(1) XOR bb(4) XOR bb(5) XOR bb(6) XOR bb(7)
XOR 
                bb(8);
            cc_next(9) := bb(2) XOR bb(5) XOR bb(6) XOR bb(7) XOR bb(8)
XOR 
                bb(9);
        RETURN cc_next;
    END gf_mul_981;

-- G(2):
    FUNCTION gf_mul_312 ( 
        bb: STD_LOGIC_VECTOR(9 DOWNTO 0))
        RETURN STD_LOGIC_VECTOR IS
        VARIABLE cc_next: STD_LOGIC_VECTOR(9 DOWNTO 0);
            BEGIN
            cc_next(0) := bb(2) XOR bb(6) XOR bb(9);
            cc_next(1) := bb(3) XOR bb(7);
            cc_next(2) := bb(4) XOR bb(8);
            cc_next(3) := bb(2) XOR bb(5) XOR bb(6);
            cc_next(4) := bb(0) XOR bb(3) XOR bb(6) XOR bb(7);
            cc_next(5) := bb(1) XOR bb(4) XOR bb(7) XOR bb(8);
            cc_next(6) := bb(2) XOR bb(5) XOR bb(8) XOR bb(9);
            cc_next(7) := bb(3) XOR bb(6) XOR bb(9);
            cc_next(8) := bb(0) XOR bb(4) XOR bb(7);
            cc_next(9) := bb(1) XOR bb(5) XOR bb(8);
        RETURN cc_next;
    END gf_mul_312;

-- G(3):
    FUNCTION gf_mul_606 ( 
        bb: STD_LOGIC_VECTOR(9 DOWNTO 0))
        RETURN STD_LOGIC_VECTOR IS
        VARIABLE cc_next: STD_LOGIC_VECTOR(9 DOWNTO 0);
            BEGIN
            cc_next(0) := bb(0) XOR bb(1) XOR bb(2) XOR bb(4) XOR bb(7);
            cc_next(1) := bb(0) XOR bb(1) XOR bb(2) XOR bb(3) XOR bb(5)
XOR 
                bb(8);
            cc_next(2) := bb(0) XOR bb(1) XOR bb(2) XOR bb(3) XOR bb(4)
XOR 
                bb(6) XOR bb(9);
            cc_next(3) := bb(0) XOR bb(3) XOR bb(5);
            cc_next(4) := bb(1) XOR bb(4) XOR bb(6);
            cc_next(5) := bb(2) XOR bb(5) XOR bb(7);
            cc_next(6) := bb(0) XOR bb(3) XOR bb(6) XOR bb(8);
            cc_next(7) := bb(1) XOR bb(4) XOR bb(7) XOR bb(9);
            cc_next(8) := bb(0) XOR bb(2) XOR bb(5) XOR bb(8);
            cc_next(9) := bb(0) XOR bb(1) XOR bb(3) XOR bb(6) XOR bb(9);
        RETURN cc_next;
    END gf_mul_606;

-- G(4):
    FUNCTION gf_mul_305 ( 
        bb: STD_LOGIC_VECTOR(9 DOWNTO 0))
        RETURN STD_LOGIC_VECTOR IS
        VARIABLE cc_next: STD_LOGIC_VECTOR(9 DOWNTO 0);
            BEGIN
            cc_next(0) := bb(0) XOR bb(3) XOR bb(9);
            cc_next(1) := bb(0) XOR bb(1) XOR bb(4);
            cc_next(2) := bb(1) XOR bb(2) XOR bb(5);
            cc_next(3) := bb(2) XOR bb(6) XOR bb(9);
            cc_next(4) := bb(3) XOR bb(7);
            cc_next(5) := bb(4) XOR bb(8);
            cc_next(6) := bb(5) XOR bb(9);
            cc_next(7) := bb(0) XOR bb(6);
            cc_next(8) := bb(1) XOR bb(7);
            cc_next(9) := bb(2) XOR bb(8);
        RETURN cc_next;
    END gf_mul_305;

-- G(5):
    FUNCTION gf_mul_967 ( 
        bb: STD_LOGIC_VECTOR(9 DOWNTO 0))
        RETURN STD_LOGIC_VECTOR IS
        VARIABLE cc_next: STD_LOGIC_VECTOR(9 DOWNTO 0);
            BEGIN
            cc_next(0) := bb(4) XOR bb(5) XOR bb(6) XOR bb(7) XOR bb(8)
XOR 
                bb(9);
            cc_next(1) := bb(0) XOR bb(5) XOR bb(6) XOR bb(7) XOR bb(8)
XOR 
                bb(9);
            cc_next(2) := bb(0) XOR bb(1) XOR bb(6) XOR bb(7) XOR bb(8)
XOR 
                bb(9);
            cc_next(3) := bb(0) XOR bb(1) XOR bb(2) XOR bb(4) XOR bb(5)
XOR 
                bb(6);
            cc_next(4) := bb(0) XOR bb(1) XOR bb(2) XOR bb(3) XOR bb(5)
XOR 
                bb(6) XOR bb(7);
            cc_next(5) := bb(0) XOR bb(1) XOR bb(2) XOR bb(3) XOR bb(4)
XOR 
                bb(6) XOR bb(7) XOR bb(8);
            cc_next(6) := bb(0) XOR bb(1) XOR bb(2) XOR bb(3) XOR bb(4)
XOR 
                bb(5) XOR bb(7) XOR bb(8) XOR bb(9);
            cc_next(7) := bb(1) XOR bb(2) XOR bb(3) XOR bb(4) XOR bb(5)
XOR 
                bb(6) XOR bb(8) XOR bb(9);
            cc_next(8) := bb(2) XOR bb(3) XOR bb(4) XOR bb(5) XOR bb(6)
XOR 
                bb(7) XOR bb(9);
            cc_next(9) := bb(3) XOR bb(4) XOR bb(5) XOR bb(6) XOR bb(7)
XOR 
                bb(8);
        RETURN cc_next;
    END gf_mul_967;

-- G(6): input equals output !

-------------------------------------------------------------------------------

    TYPE bb_t IS ARRAY (0 TO nn-kk-1) OF STD_LOGIC_VECTOR(mm-1 DOWNTO
0);

    TYPE prod_t IS ARRAY (0 TO nn-kk-1) OF STD_LOGIC_VECTOR(mm-1 DOWNTO
0);

-------------------------------------------------------------------------------

    SIGNAL bb: bb_t;


    SIGNAL rs_calc :  STD_LOGIC;

    SIGNAL rs_ins  :  STD_LOGIC;


    BEGIN

    main:
    PROCESS (clk,bb,d_in,reset)

    VARIABLE feedback: STD_LOGIC_VECTOR(mm-1 DOWNTO 0);
    VARIABLE product: bb_t;

    BEGIN

        FOR i IN 0 TO mm - 1 LOOP
            feedback:= bb(0) XOR d_in;
        END LOOP;

        product(0) := gf_mul_967(feedback);
        product(1) := gf_mul_305(feedback);
        product(2) := gf_mul_606(feedback);
        product(3) := gf_mul_312(feedback);
        product(4) := gf_mul_981(feedback);
        product(5) := gf_mul_21(feedback);

        IF reset = '1' THEN

            FOR i IN 0 TO nn-kk-1 LOOP
                bb(i)    <= (others => '0');
            END LOOP;  

            out_enb <= '0';

        ELSIF clk = '1' AND clk'EVENT THEN

            IF enable = '1' THEN

                    out_enb <= '1';

                IF rs_ins = '0' AND rs_calc = '1' THEN

                        -- calculate:

                    FOR i IN 0 TO 4 LOOP
                        bb(i) <= bb(i+1) XOR product(i);
                    END LOOP;

                    bb(5) <= product(5); 
                    d_out <= d_in;

                ELSIF rs_ins = '1' AND rs_calc = '0' THEN

                        -- insert and shift:

                    d_out <= bb(0);

                    FOR i IN 0 TO nn-kk-2  LOOP
                        bb(i) <= bb(i+1);
                    END LOOP;

                    bb(nn-kk-1) <= (others =>'0');

                ELSIF rs_ins = '0' AND rs_calc = '0' THEN

                        -- bypass:

                    d_out <= d_in;

                END IF;

            ELSE
                out_enb <= '0';
            END IF;
        END IF;
    END PROCESS;  --main


    control:
    PROCESS (clk,reset)
    VARIABLE b_cnt : INTEGER RANGE 0 TO 518;
    BEGIN
        IF reset = '1' THEN
            rs_calc <= '1';
            rs_ins  <= '0';
            b_cnt   :=  0;
        ELSE
            IF clk = '1' AND clk'EVENT THEN
                IF enable = '1' THEN
                    IF b_cnt = 0 THEN
                        rs_calc <= '1';
                        rs_ins  <= '0';
                        b_cnt   := b_cnt + 1;
                    ELSIF b_cnt =  last_in - 1 THEN
                        rs_calc <= '0';
                        rs_ins  <= '1';
                        b_cnt   := b_cnt + 1;
                    ELSIF b_cnt = last_out - 1 THEN
                        rs_calc <= '1';
                        rs_ins  <= '0';
                        b_cnt   :=  0;
                    ELSE
                        b_cnt := b_cnt + 1;
                    END IF;
                END IF;
            END IF;
        END IF;
    END PROCESS;  -- ctrl

END rtl;  -- rs_enc





More information about the yaffs mailing list