«

Hi,

I have the following problem in vhdl:

There are 256 parallel incoming 16-bit-values to compare and at the
end i want to give out the maximum value and the minimum value.

I think to be economical it is not the best way to install a row of
comparators so im searching for a more efficient way.

Maybe it is clever to serialise data and compare them consecutively
but im not sure about how to do that or if there is a better solution.

If anyone has a suggestion I would be very happy.

Cheers
Ralf

Ralf wrote:

> There are 256 parallel incoming 16-bit-values to compare and at the
> end i want to give out the maximum value and the minimum value.

So many inputs? Think about serializing them. Otherwise this may lead to a lot of logic gates.


> I think to be economical it is not the best way to install a row of
> comparators so im searching for a more efficient way.

Yes.

> Maybe it is clever to serialise data and compare them consecutively
> but im not sure about how to do that or if there is a better solution.

I wll give you some (incomplete) ideas:

process(reset, clk)
begin
if (reset='1') then
counter<=0;
max_value<=(others => '0')
elsif rising_edge(clk) then
if ( input_data(counter*16+15 downto counter*16) > max_value) then
max_value<=input_data(counter*16+15 downto counter*16);
endif;
counter<=counter+1;
-- test, if counter = 15 (hint: carry out will be 1) -> stop comparisons
endif;
end process;

Results in
* a 4 bit counter (flipflops) plus incrementer
* 16 bit subtractor (comparator)
* 16 flipflops storage for max_value
* plus start / stop logic
* plus logic / flipflops for a minimum value

As you can see, this simple solution does not need the input data in parallel.

Furthermore: Think about a syncronous reset.

Ralf

Ralf wrote:

[ ... ]

> There are 256 parallel incoming 16-bit-values to compare and at the
> end i want to give out the maximum value and the minimum value.

A little multiplication shows that 256 16-bit inputs will consume 4096
pins -- which will generally rule this if those were coming from the
outside world.

> I think to be economical it is not the best way to install a row of
> comparators so im searching for a more efficient way.

Probably correct -- especially since you'd need more than a row of
compraators. At least as far as I can see, you'd end up with something
like two trees of comparators. If I'm not mistaken, you'd end up with
something like 255 2-input comparators of 16-bits each. It's possible,
but not exactly economical.

> Maybe it is clever to serialise data and compare them consecutively
> but im not sure about how to do that or if there is a better
solution.

I would definitely tend toward this if you have a choice. One
possibility might look vaguely like this:

entity extremes is
generic(size : integer := 16);
port(
reset : in std_logic;
input : in std_logic_vector(size-1 downto 0);
in_stb : in std_logic;
max : out std_logic_vector(size-1 downto 0);
min : out std_logic_vector(size-1 downto 0));
end extremes;

architecture behavioral of extremes is
begin
compare : process(reset, in_stb) is
variable current_min, current_max :
std_logic_vector(size-1 downto 0);
constant smallest : std_logic_vector(size-1 downto 0)
:= (others=>'0');
constant largest : std_logic_vector(size-1 downto 0)
:= (others=>'1');
begin
if reset = '1' then
current_max := smallest;
current_min := largest;
elsif in_stb = '1' and in_stb'event then
if input < current_min then
current_min := input;
end if;
if input > current_max then
current_max := input;
end if;
end if;
min <= current_min;
max <= current_max;
end process;
end behavioral;

For the moment, this assumes you're dealing with unsigned numbers (0-N)
but the change for signed numbers is trivial (the values of smallest
and largest).

--
Later,
Jerry.

The universe is a figment of its own imagination.