Reed Solomon Encoder

[sai]

Hello all,

I have been trying to find an algorithm for reed solomon encoder. I
have written code for this in C which is pretty straight forward.
However, I would like to implement this in hardware and I do not want
to use the look up tables (for multiplying galois field elements)
which is inefficient in hardware (FPGA). I understand that there are
several algorithms for RS encoder to implement in hardware but I am
not sure as to where to find them. I have looked at some IEEE papers
but there are so many of them that I am not sure which is the best/
appropriate one. I was wondering if anyone could point out a paper or
perhaps better yet, a book that I can refer for this. I have google'd
enough to find some hdl code but not the actual algorithm. Some links
given in this group don't work anymore either (ex:
http://www.fokus.gmd.de/research/cc/mobis/products/fec_old/content.html)
. Any help is appreciated.

Thanks,
Sai

 

[Duane Clark]

sai wrote:

Hello all,

I have been trying to find an algorithm for reed solomon encoder. I
have written code for this in C which is pretty straight forward.
However, I would like to implement this in hardware and I do not want
to use the look up tables (for multiplying galois field elements)
which is inefficient in hardware (FPGA). I understand that there are
several algorithms for RS encoder to implement in hardware but I am
not sure as to where to find them. I have looked at some IEEE papers
but there are so many of them that I am not sure which is the best/
appropriate one. I was wondering if anyone could point out a paper or
perhaps better yet, a book that I can refer for this. I have google'd
enough to find some hdl code but not the actual algorithm. Some links
given in this group don't work anymore either (ex:
http://www.fokus.gmd.de/research/cc/mobis/products/fec_old/content.html)
. Any help is appreciated.

For encoding, all the Galois field multipliers are fixed multipliers to
the best of my recollection (it has been awhile since I looked at this).
A fixed multiplier is just an array of XOR gates. I do it like this for
a CCSDS standard 255,223 code; which is a bit weird in how the roots
increment if you are not familiar with CCSDS. The input data is MULTIN.

constant RS_M : integer := 8; -- bits per symbol
constant RS_R : integer := 32; -- Check symbols in code word

parity_struct: for i in 0 to RS_R-1 generate
signal mresult : symbol_word;
begin
-- Generate an array of XOR gates that make up onefixed multiplier
smultiplier: for j in 0 to (RS_M-1) generate
signal sma : mult_array;
signal smm : symbol_word;
begin
sma <= PARMULT(i);
smm <= MULTIN and sma(j);
xor_bits: process (smm)
variable smxor : std_logic;
begin
smxor := smm(0);
for k in 1 to RS_M-1 loop
smxor := smxor xor smm(k);
end loop;
mresult(j) <= smxor;
end process xor_bits;
end generate smultiplier;
...

The fixed values we are multiplying by is "PARMULT", and is declared in
a package file:

type parity_array is array (0 to RS_R-1) of symbol_word;
type parmult_array is array (0 to RS_R-1) of mult_array;
-- Constants for a RS encoder
-- g(X) = CCSDS. This is a palindromic code, so
-- PARMULT(31) = PARMULT(1), etc.
-- PARMULT(32) is not used. It should always be 1.
constant PARMULT : parmult_array := (
(X"01",X"02",X"04",X"08",X"10",X"20",X"40",X"80"), -- @0
(X"6D",X"B7",X"02",X"05",X"0B",X"16",X"2D",X"36"), -- @249
(X"55",X"FF",X"AB",X"57",X"AF",X"5F",X"BF",X"2A"), -- @59
(X"4C",X"D5",X"E7",X"CE",X"9D",X"3A",X"75",X"A6"), -- @66
(X"F0",X"10",X"D0",X"A0",X"41",X"82",X"04",X"F8"), -- @4
(X"50",X"F1",X"B3",X"67",X"CF",X"9E",X"3C",X"28"), -- @43
(X"21",X"62",X"E5",X"CB",X"96",X"2C",X"58",X"90"), -- @126
(X"1B",X"2D",X"40",X"81",X"02",X"05",X"0B",X"0D"), -- @251
(X"05",X"0E",X"18",X"30",X"60",X"C1",X"83",X"02"), -- @97
(X"47",X"C8",X"D7",X"AE",X"5C",X"B9",X"72",X"A3"), -- @30
(X"E0",X"20",X"A0",X"41",X"82",X"04",X"08",X"F0"), -- @3
(X"98",X"A9",X"CA",X"95",X"2A",X"55",X"AA",X"CC"), -- @213
(X"48",X"D9",X"FB",X"F6",X"ED",X"DB",X"B6",X"24"), -- @50
(X"4C",X"D5",X"E7",X"CE",X"9D",X"3A",X"75",X"A6"), -- @66
(X"E7",X"29",X"B4",X"69",X"D2",X"A5",X"4A",X"73"), -- @170
(X"F8",X"08",X"E8",X"D0",X"A0",X"41",X"82",X"FC"), -- @5
(X"F5",X"1E",X"C8",X"90",X"21",X"43",X"87",X"FA"), -- @24
(X"F8",X"08",X"E8",X"D0",X"A0",X"41",X"82",X"FC"), -- @5
(X"E7",X"29",X"B4",X"69",X"D2",X"A5",X"4A",X"73"), -- @170
(X"4C",X"D5",X"E7",X"CE",X"9D",X"3A",X"75",X"A6"), -- @66
(X"48",X"D9",X"FB",X"F6",X"ED",X"DB",X"B6",X"24"), -- @50
(X"98",X"A9",X"CA",X"95",X"2A",X"55",X"AA",X"CC"), -- @213
(X"E0",X"20",X"A0",X"41",X"82",X"04",X"08",X"F0"), -- @3
(X"47",X"C8",X"D7",X"AE",X"5C",X"B9",X"72",X"A3"), -- @30
(X"05",X"0E",X"18",X"30",X"60",X"C1",X"83",X"02"), -- @97
(X"1B",X"2D",X"40",X"81",X"02",X"05",X"0B",X"0D"), -- @251
(X"21",X"62",X"E5",X"CB",X"96",X"2C",X"58",X"90"), -- @126
(X"50",X"F1",X"B3",X"67",X"CF",X"9E",X"3C",X"28"), -- @43
(X"F0",X"10",X"D0",X"A0",X"41",X"82",X"04",X"F8"), -- @4
(X"4C",X"D5",X"E7",X"CE",X"9D",X"3A",X"75",X"A6"), -- @66
(X"55",X"FF",X"AB",X"57",X"AF",X"5F",X"BF",X"2A"), -- @59
(X"6D",X"B7",X"02",X"05",X"0B",X"16",X"2D",X"36") -- @249
);

Of course, I don't generate those by hand. I write a small program in C
which generates this:

/* All parameters should be configurable within these defines, except
for the dual basis conversion matrices if used (only in CCSDS),
which are manually entered near the bottom of this file. */
#define CCSDS 1 /* 1=CCSDS (dual basis conversions , 0=not CCSDS */
#define M 8 /* bits per symbol */
#define SYMS 255 /* 2**M-1 symbols in table (excluding zero) */
#define FILL 3 /* Bytes of fill for shortened codes */
#define MMASK 0xFF /* a mask for M bits */
#define N 255 /* symbols per code word */
#define T 16 /* correctable symbols */
#define R 2*T /* number of parity symbols */
#define P 11 /* the G(X) roots increment by P */
#define J 112 /* the initial root is P*J%SYMS */
/* For the field generator polynomial F(X) = X8 + X7 + X2 + X + 1 */
#define FIELDPOLY 0x187

....
printf("\n ");
printf("\n type parity_array is array (0 to RS_R-1) of
symbol_word;");
printf("\n type parmult_array is array (0 to RS_R-1) of
mult_array;");
printf("\n -- Constants for a RS encoder");
printf("\n -- g(X) = CCSDS. This is a palindromic code, so");
printf("\n -- PARMULT(31) = PARMULT(1), etc.");
printf("\n -- PARMULT(32) is not used. It should always be 1.");
printf("\n constant PARMULT : parmult_array := (\n");
for (i=0; i<R; i++) {
mult_by = exp[g];
poly = alpha[mult_by+1];
if (i==R-1)
end = 1;
else
end = 0;
print_mult(poly, mult_by, end);
}
....

print_mult(poly, mult_by, end)
int poly;
int mult_by;
int end;
{
int exp[256], alpha[256], mpoly;
int bit[M], mbit[M], mask;
int j, k;

/* break out the bits for printing */
mask = 1;
for (j=0; j<M; j++) {
if (poly & mask)
bit[j] = 1;
else
bit[j] = 0;
mask = mask * 2;
}
for (j=0; j<M; j++)
mbit[j] = bit[j];
mpoly = poly;
/* Now let's multiply by mult_by */
/* get B*mult_by in terms of b7(a7+a5+a2)+b6(a6+a4+a1)... */
for (j=0; j<M; j++) {
mbit[j] = mpoly;
mpoly = mpoly*2;
if (mpoly > MMASK)
mpoly = mpoly ^ FIELDPOLY;
}


/* Now rearrange into (b7+b4+b3)a7+(b6+b4+b2)a6... */
mask = 1;
for (k=0; k<M; k++) {
malpha[k] = 0;
for (j=0; j<M; j++) {
if (mbit[j] & mask) {
malpha[k] += MMASK+1;
bit[j] = 1;
}
else
bit[j] = 0;
malpha[k] = malpha[k] >> 1;
}
if (k==0)
if (M==8)
printf(" (X\"");
else
printf(" (\"");
else
if (M==8)
printf("\",X\"");
else
printf("\",\"");
if (M==8)
printf("%02X", malpha[k]);
else {
for (j=M-1; j>=0; j--) {
if (malpha[k] & (1<<j))
printf("1");
else
printf("0");
}
}
mask = mask * 2;
}
if (end>0)
printf("\") -- @%d\n );\n", mult_by);
else
printf("\"), -- @%d\n", mult_by);
}