Community
cancel
Showing results for 
Search instead for 
Did you mean: 
GZlyd
Beginner
365 Views

Finding Common Items in a VHDL Array

Hello.

I can’t solve the following problem.

There are 25 numbers, each 8 bits. It is necessary to find the most common among them i.e. if the number occurs 13 or more times, this is what we are looking for. If this was not found, then you need to give out 8 zeros. When the algorithm has worked, you need an impulse that will report this.

 

I will describe what I did and how I solved this problem.

 

I tried to implement the Boyer-Moore Algorithm - the very Boyer and Moore that came up with a much more well-known substring search algorithm - it’s easiest to imagine as follows: N people gathered at the party, and each one has an element from the array. When two meet, whose elements are different, they sit down to discuss it. In the end, only people with the same elements will remain standing; obviously this is the same element that has occurred more than N / 2 times.

 

The implementation of the Boyer-Moore algorithm takes only a few lines

 

int* majority(int[] array, int N) {   int confidence = 0; // количество людей, не нашедших пары и оставшихся стоять   int* candidate = NULL; // последний человек, не нашедший пару --   // возможно, его элемент встречается чаще всего       // проходим по массиву и усаживаем пары с разными элементами   for (int i = 0; i<N; i++) {       // если до сих пор все сидят, то следующему пока придётся постоять   if (confidence == 0) {   candidate = array+i;   confidence++;   }       // иначе следующий либо садится с одним из стоящих,   // либо будет стоять вместе с ними, если у него такой же элемент   else if (*candidate == array[i]))   confidence++;   else   confidence--;   }       return confidence > 0 ? candidate : NULL;   }

 

 

2) In the Digital Design Using Diligilent FPGA Boards VHDL / Active-HDL Edition tutorial. Richard E. Haskell, Darrin M. Hanna 2010.

From page 278 there it is shown how to correctly implement such algorithms on the FPGA using the example of searching for the root and Euclidean GCD. Figures 1 and 2 are not synthesized code of these algorithms.

 

Figure 3 and 4 are synthesized on the plis implementation of these algorithms.

 

3) I tried to adapt this algorithm for synthesis.

 

It turned out the following, or rather, the original code was different, but I tried many times to fix it, but nothing really changed. And I don’t remember what it was originally.

-----Author: Zlydnev E.N.   -----function: vybiraem nomera   -- Revision history   -- Version 1.0 :   -- Date: 6/09/2019   -- Comments : Original   ----   library IEEE;-- vklychaem biblioteki   use IEEE.std_logic_1164.all;   use IEEE.std_logic_unsigned.all;   use IEEE.numeric_std.all;           entity chastye_elementy is -- vhodnie/vyhodnye signals       port( clk : in std_logic;   GO : in std_logic;   clr : in std_logic;   ------------------------------------------------   ------------------------------------------------   ------------------------------------------------     nomer : out std_logic_vector(7 downto 0);     ibn1 : in std_logic_vector(7 downto 0);-- nomer borta na pervom zaprose   ibn2 : in std_logic_vector(7 downto 0);-- nomer borta na vtorom zaprose   ibn3 : in std_logic_vector(7 downto 0);-- -//-   ibn4 : in std_logic_vector(7 downto 0);-- -//-   ibn5 : in std_logic_vector(7 downto 0);-- -//-   ibn6 : in std_logic_vector(7 downto 0);-- -//-   ibn7 : in std_logic_vector(7 downto 0);-- -//-   ibn8 : in std_logic_vector(7 downto 0);-- -//-   ibn9 : in std_logic_vector(7 downto 0);   ibn10 : in std_logic_vector(7 downto 0);-- -//-   ibn11 : in std_logic_vector(7 downto 0);--   ibn12 : in std_logic_vector(7 downto 0);--   ibn13 : in std_logic_vector(7 downto 0);--   ibn14 : in std_logic_vector(7 downto 0);--   ibn15 : in std_logic_vector(7 downto 0);--   ibn16 : in std_logic_vector(7 downto 0);--   ibn17 : in std_logic_vector(7 downto 0);--   ibn18 : in std_logic_vector(7 downto 0);--   ibn19 : in std_logic_vector(7 downto 0);--   ibn20 : in std_logic_vector(7 downto 0);--   ibn21 : in std_logic_vector(7 downto 0);--   ibn22 : in std_logic_vector(7 downto 0);--   ibn23 : in std_logic_vector(7 downto 0);--   ibn24 : in std_logic_vector(7 downto 0);--   ibn25 : in std_logic_vector(7 downto 0);-- nomer borta na 25 zaprose   ------------------------------------------         done : out std_logic --dalnostb po poslednemy impulsu     );   end chastye_elementy;       architecture rtl of chastye_elementy is           type reg is array (25 downto 1) of std_logic_vector(7 downto 0);--type danyx dlya xraneniya IBN   signal ibn :reg := (others => (others =>'0'));           signal i : integer range 0 to 25;   signal j : integer range -25 to 25;   signal temp_nomer : std_logic_vector(7 downto 0);               begin         G3: process(clr,clk)   variable calk,donev: std_logic;   begin   if clr = '1' then   ibn <= (others => (others =>'0'));   nomer <= (others =>'0');   temp_nomer <= (others =>'0');   i <= 1;   j <= 0;   calk := '0';   donev := '0';   elsif rising_edge(clk) then   donev := '0';   if go = '1' then   ibn(1) <= ibn1; ibn(2) <= ibn2; ibn(3) <= ibn3; ibn(4)<=ibn4 ;ibn(5)<= ibn5 ; ibn(6) <= ibn6;   ibn(7) <= ibn7; ibn(8) <= ibn8; ibn(9) <= ibn9; ibn(10)<= ibn10; ibn(11)<=ibn11 ; ibn(12)<=ibn12 ;   ibn(13) <= ibn13; ibn(14)<= ibn14; ibn(15)<= ibn15; ibn(16)<= ibn16; ibn(17)<= ibn17 ; ibn(18) <= ibn18;   ibn(19) <= ibn19; ibn(20)<= ibn20; ibn(21) <= ibn21; ibn(22)<=ibn22 ; ibn(23) <= ibn23; ibn(24) <= ibn24;ibn(25)<=ibn25 ;   i <= 1;   j <= 0;   temp_nomer <= (others =>'0');   nomer <= (others =>'0');   calk := '1';   elsif calk = '1' then   if i=24 then   if j > 0 then   nomer <= temp_nomer;   else nomer <= "00000001";   end if;   donev := '1';   calk := '0';   elsif j = 0 then   temp_nomer <= ibn(i+1);   j<= j + 1;   i<= i + 1;   elsif temp_nomer = ibn(i+1) then   i<= i + 1;   j<= j + 1;   temp_nomer <= temp_nomer;   else   i<=i + 1;   j<=j - 1;   temp_nomer <= ibn(i+1);   end if;   end if;   end if;   done <= donev;   end process;       end rtl;      

 

I'll tell you about the code

 

IBN 1-25 - input data.

 

number - output number, result.

 

Go-signal to start the algorithm

 

Done - the signal for the end of the algorithm

 

Сlk - frequency, clr - reset.

 

The rest was done by analogy with the example from the textbook.

 

Got bad results. The scheme has earned.

 

PROBLEMS are always the same:

 

1) The signal i does not increase at each step by 1, but for some reason, like a jay, it increases and increases. It also starts not with 0, but with 3. Although I registered that i = 0.

 

2) As a result (signal nomer), always simply the ibn25 value is returned

 

Please help me figure this out. A.

 

 

 

P.S Now the algorithm takes 270 LE. FPGA is tiny, as I said, I want it to take up all this as little space as possible. Speed ​​is not so important. My frequency is 37 MHz5.JPG4.jpg3.jpg2.jpg1109.JPG

Tags (1)
0 Kudos
2 Replies
MEIYAN_L_Intel
Employee
75 Views

Hi,

May I have the new screenshot of full waveform with "clr" state?

Also, may I know the function of signal j and why the the range from -25 to 25?

From the screenshot of the waveform given, I did not saw any integer "3" in the waveform.

May you attach testbench so that I further evaluate?

Also, may I know the design code as above is your design with problem mentioned. If no, can you attached design file?

Thanks

MEIYAN_L_Intel
Employee
75 Views

Hi,

May I know any update for this case?

Thanks

Reply