FPGA Central

Hello everybody,

I have implanted the Key Equation Solver for a Reed Solomon Decoder
with the Extended Euclidean Algorithm.

The circuit is explained in this Paper : "An area-efficient Euclidean
Algorithm
block for Reed-Solomon decoder" by Hanho Lee

I have implanted these two circuit (euclidean divider and euclidean
multiplier)

The euclidean divider performs well the quotient Q(x)

But I don't know how to send this quotient to the euclidean multiplier
part ?

Is there anyone who have implanted this structure ?

Thanks... and sorry if I don't put the VHDL code to this message

define a generic in the entity and use that to pass the quotient to the
instantiation.

Patrick wrote:
> I have implanted the Key Equation Solver for a Reed Solomon Decoder
> with the Extended Euclidean Algorithm.
>
> The circuit is explained in this Paper : "An area-efficient Euclidean
> Algorithm
> block for Reed-Solomon decoder" by Hanho Lee

It's been a while since we implemented this for the OTN standard, though I
believe we worked from a better mathematical setup than this one. Can't
seem to find my papers on this topic anywhere though, but I remember our
implementation ran at 330 MHz for 40 Gb/s data processing rate, and it was
quite small.

> But I don't know how to send this quotient to the euclidean multiplier
> part ?

I don't exactly understand what you mean by 'sending' in this regard, but
what I understand from the paper, a simple FIFO should be usable, depending
a bit on your implementation.

Regards,

Pieter Hulshoff

hi,

In fact, I don't know how to pass the Q(x) result from the euclidean
divider to the euclidean multiplier.

I've got Q(x) = [41,167],[42,20],etc...

The multiplier model show that coefficient of Q(x) are input
sequentially...

The first stage PE0 compute the good locator : 47, 179, 255, etc which
correspond to the zero degree of the polynome

But the second stage never have the degree 1 of the polynome

I don't understand what is the signal gamma beetween the different PEs
elements...

Thanks...

And so I don't know exactly the CT0, CT1, SFC signal

I implant this FSM :

--------------------
-- ETAT : "INIT"
--------------------
when INIT =>
CT0 <= '0';
CT1 <= '1';
SFC <= '0';
ETAT <= CK_1;

---------------------
-- ETAT : "CK_1"
---------------------
when CK_1 =>
CT0 <= '1';
CT1 <= '1';
SFC <= '1';
ETAT <= CK_2;

---------------------
-- ETAT : "CK_2"
---------------------
when CK_2 =>
CT0 <= '1';
CT1 <= '1';
SFC <= '1';
ETAT <= CK_3;

---------------------
-- ETAT : "CK_3"
---------------------
when CK_3 =>
CT0 <= '1';
CT1 <= '1';
SFC <= '0';
ETAT <= CK_4;

---------------------
-- ETAT : "CK_4"
---------------------
when CK_4 =>
CT0 <= '1';
CT1 <= '0';
SFC <= '1';
ETAT <= CK_1;

AND THIS IS MY IMPLANTATION OF THE PE0 element for the euclidean multiplier


-- Mux M0
with CT0 select
M0 <=
E when '0',
add_2 when '1',
E when others;

-- Mux M1
with SFC select
M1 <=
M0 when '0',
Bi1 when '1',
M0 when others;

-- Mux M2
with SFC select
M2 <=
Bi1 when '0',
Bi2 when '1',
Bi1 when others;

-- Bascule Bi1
RA1 : process (clock,reset)
begin
if reset = '1' then
Bi1 <= X"00";
elsif (clock'event and clock='1') then
Bi1 <= M1;
end if;
end process RA1;

--Bascule Bi2
RA2 : process (clock,CT0)
begin
if (clock'event and clock='1') then
if CT0 = '0' then
Bi2 <= X"00";
else
Bi2 <= M2;
end if;
end if;
end process RA2;

-- Multiplieur de Galois
MULTIPLIE : galoismult port map (Q_in,Bi1,mult);

-- Additionneur N°1 de Galois
ADDITIONNE_1 : addgalois port map (gamma_in,mult,add_1); --Bi2 - gamma_in

-- Latch sur la sortie de l'additionneur 1
LATCH : process (clock,reset)
begin
if reset='1' then
gamma_in_smp <= (others=>'0');
elsif (clock'event and clock='1') then
gamma_in_smp <= gamma_in;
end if;
end process LATCH;

-- Clock RBi
RAZ_RBi <= CT0 NAND CT1;

-- Bascule RBi
RBi_LATCH : process (clock,RAZ_RBi)
begin
if (clock'event and clock='1') then
if RAZ_RBi = '1' then
RBi <= X"00";
else
RBi <= add_1;

end if;

end if;
end process RBi_LATCH;

-- Additionneur N°2 de Galois
ADDITIONNE_2 : addgalois port map (RBi,Bi2,add_2);

---- Signal de sortie : "delta"
-- LATCH_OUT : process (clock,reset)
-- begin
-- if reset='1' then
-- gamma_out <= (others=>'0');
-- sigma_out <= (others=>'0');
-- elsif (clock'event and clock='0') then
gamma_out <= RBi;
sigma_out <= Bi1;
--end if;
-- end process LATCH_OUT;

Patrick wrote:
> I've got Q(x) = [41,167],[42,20],etc...

Ok, you've already lost me here. Why are there 2 numbers for each
coefficient? I would expect one for each.

> The multiplier model show that coefficient of Q(x) are input
> sequentially...

That is correct, starting with the highest coefficient, and going down the
line. Basically you've got one 8 bit value per multiplier cycle.

Unfortunately I've still been unable to find the paper I worked from back
then. It contained examples and everything of the intermediate calculations
involved. You may want to have a closer look around the web for Euclidean
Algorithms w.r.t. Reed-Solomon decoders. I'll continue to search through my
papers, and let you know. It's just been a tad too long since I worked on
this stuff.

Regards,

Pieter Hulshoff