Minimum Of N Numbers using verilog or VHDL

[kalyansumankv]

Minimum Of N Numbers

Is there any way that i can found out the minimum of N-Numbers with minimum effort using verilog or VHDL

 

[mostafa_amer]

Re: Minimum Of N Numbers

It could be done
BUT
[1] Is N fixed or variable?
[2] What is the bit length of the numbers?
[3] How are they represented?signed or unsigned?
[4] Is there any constraints on the number of clock cycles needed to compute the minimum?
[5] Are the numbers stored in a memory (register file, or BlockRAM) or they are introduced sequentially to the core?

best regards,
Mostafa m. Amer

 

[kalyansumankv]

Re: Minimum Of N Numbers

[1] Is N fixed or variable?
-- N is Fixed let say 64

[2] What is the bit length of the numbers?
--It is a 8-bit Value

[3] How are they represented?signed or unsigned?
--It is an unsigned number

[4] Is there any constraints on the number of clock cycles needed to compute the minimum?
-- Minimum number of cycles


[5] Are the numbers stored in a memory (register file, or BlockRAM) or they are introduced sequentially to the core?
-- No they are not stored in a memory

 

[mostafa_amer]

Re: Minimum Of N Numbers

HI,
below is a VHDL code that accepts a stream of 8-bit unsigned numbers and output the minimum of the introduced stream.

It contains a register (min) to hold the minimum value. This register is initialized to the maximum possible value ,255, when the ENA input is active min is compared to the introduced number (NO_IN) and using an 8-bit LT comparator decides whther to store NO_IN in min or keep the previous value of min untouched.

the value of min is always outed @ MIN_OUT
each compare will take a single clock cycle.

----------------------------------------------------------------------------------
-- Engineer: Eng. Mostafa M. Amer
-- 
-- Create Date:    10:28:31 11/17/2008 
-- Design Name: Minimum of N 8-bit unsigned numbers
-- Module Name:    minimum_N - Behavioral 
----------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;


entity minimum_N is
    Port ( NO_IN : in  STD_LOGIC_VECTOR (7 downto 0); 	-- Input stream
			  ENA : in STD_LOGIC;									-- Enable
           CLK : in  STD_LOGIC;									-- Clock
           MIN_OUT : out  STD_LOGIC_VECTOR (7 downto 0));-- The minimum of the stream
end minimum_N;

architecture Behavioral of minimum_N is
	signal min : std_logic_vector(7 downto 0):="11111111"; -- Initial min to the maximum possible number
begin


comparator:
process(CLK)
begin
if (ENA='1') then 
   if (CLK'event and CLK ='1') then   
      if ( NO_IN < min ) then 
			min <= NO_IN;
      else 
         min <= min;
      end if;
   end if; 
else
	min <= min;
end if;
end process; 
    
MIN_OUT <= min;
				

end Behavioral;

Hope it helped you. If you have any questions plz ask

Best regards,
Mostafa M. Amer

 

[kalyansumankv]

Re: Minimum Of N Numbers

Dear Mostafa,

Thanks for the code,
to the best of my understanding,
the code given by you will take N-number of cycles,
to output the minimum of N- Numbers...

Anyways i came up with a design that will take far less than N cycles
to compute a minimum of N - numbers.,
This can be done with a small parallel processing...

 

[mostafa_amer]

Re: Minimum Of N Numbers

Dear kalyansumankv ,

You said Numbers are not saved in memory => They are introduced to the core sequentially => I assumed that they will be introduced a number at each cycle => Introduction of numbers will take N cycles => If getting the minimum took less than N cycles (BTW I am very interested to see your design,plz share) still the introduction of inputs will take N => I concluded that there'll be no need for the extra hardware if there will not be a speed gain.

Am I right? That's how I thought abot it :$:$ but I might be wrong


Best regards,
Mostafa M. Amer

 

[kalyansumankv]

Re: Minimum Of N Numbers

Dear Mustafa,

Yeah i did say that the numbers are not stored in a memory,
but i ll be having N-numbers of modules which runs in paralle(As shown in fig)l and
i need to find the min of those numbers..

And the approach i followed is as follows,
say the N is 64,
divide the numbers as a group of 8 each and find the min of them,
which needs 8 cycles,
and after 8 cycles you ll be left with 8 numbers again and
repeat the aboce process to find the min of tht 8 numbers.
on a whole you ll be required with 8+8 cycles to find the min of the 64-numbers

 

[mostafa_amer]

Re: Minimum Of N Numbers

hmmm
in such a case u may consider the other extreme; do not use resource sharing at all and build a comparator tree with (log2 N) levels and (N-1) 8-bit LT comparators. a pure combinatorial circuit . and if multiple N-numbers sets are applied you may use pipelined architecture.

Best regards,
Mostafa M. Amer

 

[kalyansumankv]

Re: Minimum Of N Numbers

I think i may be done,
but i need to do a synchrous design,
so i did this way,

anyways thanks a lot for the replyy

 

[mostafa_amer]

Re: Minimum Of N Numbers

u r wellcome

ps: the whole tree may be synchronized but that'll affect the overall clock speed, u may consider the pipelined architecture
BUT
if ur solution works fine, hold for it

 

[kalyansumankv]

Re: Minimum Of N Numbers

Yeah my design too works fine,
thanks a lot for your help...

 

[Nir Dahan]

Re: Minimum Of N Numbers

The complexity of the problem is (compare delay)*log2(N)
you are basically performing a binary tree (hence log2(N) ) of compare operations (each costing a "compare delay")

I have no idea how much of the logic you can compress into a single clock cycle.
but make a combo cloud that does this, synthesize and watch your slack - then decide where and how many registers to use in order to pipeline. That is of course given the fact you want high throughput.
If not just use a multi cycle path on the logic.

ND.

https://asicdigitaldesign.wordpress.com/

 

[kalyansumankv]

Re: Minimum Of N Numbers

Dear Nir Dahan,

Thanks for the advice of going for a Combo Cloud,
i ll try the same....

Regards
Kalyan Suman