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 MHz
Link Copied
