Re: [ecc] Reed Solomon decoder

[Duane Clark <dclark@akamail.com>]

inada@singnet.com.sg wrote:
> Hi Duane,
> Thanks for ur reply. Its interesting and exciting to know that 
> implementation of RS 255,223 on XCV600 Fpga is a reality. I've done 
> some research on the GF or the finite field multiplier, but there are some
> parts which i'm not sure about. How does the multiplier replace the 
> exponential/Binary LUT? Does it mean the multiplier includes the 
> multiplications of any two alphas exponentials, mod, and XOR? And is 
> there any docs or website that u recommend on the GF multiplier? Really 
> appreciative if u can help... Thanks!!


The place I learned about about GF multipliers, and by far the best I
have seen so far, is Lin and Costello, Error Control Coding. Kind of
old, but well worth having. In particular, the XOR implementation of a 
fixed GF is covered in section 6.3.

There are two common ways to do GF multiplication. One is to do the exp
conversion, then add the exponents, then convert back. The other is to 
implement the multiplication directly. For a fixed multiplier (the input 
is multiplied by a fixed element) the multiplier is a very simple 
circuit of XOR gates.

For example, here is the start of one table I have. As previously 
mentioned, I generate this table with C code:

    -- SMULT is the array of of bitmasks for the multipliers used
    -- for calculating the syndrome.
    -- Calculated for the roots of G(X).
    constant SMULT    : smult_array := (
          (X"31",X"52",X"95",X"2A",X"55",X"AA",X"54",X"98"), -- @212
          (X"C4",X"4C",X"5D",X"BA",X"74",X"E9",X"D3",X"62"), -- @223

Here is the beginning of where I use it:

    -- Calculate the syndromes.
    -- @i is one of the roots of G(X), and rNNN is an
    -- input byte from the uncorrected data r(X), implementing:
    -- ...(((((r255*@i+r254)*@i+r253)*@i+r252)*@i+r251)...
    -- The result is (r255*@i^254)+(r254*@i^253)+(r253*@i^252)...+(r1*@i^0)
    syndrome_struct: for i in 1 to RS_R generate

       smultiplier: fixed_mult
          generic map (MULT_BY => SMULT(i))
          port map (
             XIN => SYNDRME(i),
--            MULT_BY => SYNM(i),
             POUT => SYNM_RES(i)
          );

And here is the fixed multiplier:

-- Multiply a byte by a fixed alpha.
entity fixed_mult is
    generic ( MULT_BY : mult_array );
    port (
       XIN      : in symbol_word;
--      MULT_BY  : in mult_array;
       POUT     : out symbol_word
    );
end entity fixed_mult;

architecture synthesis of fixed_mult is
begin
    -- Generate an array of XOR gates that makes up one fixed GF multiplier
    multarray: for j in 0 to RS_M-1 generate
       -- Generate an XOR gate for one bit of the multiplier
       xor_bits: process (XIN)
          variable gfmm : symbol_word;
          variable gfmxor : std_logic;
       begin
          -- Get the bit mask for the current bit.
          gfmm := XIN and MULT_BY(j);
          -- XOR the unmasked bits. Masked bits should be optimized out
          -- by the place and route.
          gfmxor :=  gfmm(0);
          for k in 1 to RS_M-1 loop
             gfmxor := gfmxor xor gfmm(k);
          end loop;
          POUT(j) <= gfmxor;
       end process xor_bits;
    end generate multarray;
end architecture synthesis;

General GF multipliers, where both inputs are variables, are just a 
generalization of the above. Hmm, don't know if I really want to say how 
I did that :-) I have not actually seen the technique I used mentioned 
anywhere.

I will just say that I exploit the structure of the LUT in the Xilinx 
Virtex chips, and can make a very compact multiplier that can do a GF 
multiplication in 2 clocks at over 100MHz. It turns out that the Virtex 
LUT structure is ideally suited to this operation. The 2 clocks are 
because I pipeline the circuitry, so there are FFs in the middle and at 
the end of the multiplier (FFs are basically free anyway). All the 
actual logic is purely combinatorial, without feedback, and without 
lookup tables. The actual implementation is left as an exercise for the 
reader:-)


--
To unsubscribe from ecc mailing list please visit http://www.opencores.org/mailinglists.shtml