Programming problem

[Ralf]

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 Hildebrandt]

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

 

[Jerry Coffin]

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.