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