Euclidean Multiplier (RS CODEC)

[Patrick]

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

 

[Jezwold]

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

 

[Pieter Hulshoff]

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

 

[Patrick]

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...

 

[Patrick]

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;

 

[Patrick]

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;

 

[Pieter Hulshoff]

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