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
(text/plain)