Comparator and minimum value address

[sunil]

Hi all,
I have 16 values. I ahve to compare those values and i have to
get minimum value and it's address. I am comparing those all 16 avlues
with by 8 comaprators, next the 8 output values by 4 comparator and so
on......
at last i am getting minimum value but how i can get address of
that value. I tried by moving back which means if output deciison is 0
,then previous decision's 0 bit.... and so on..
but VHDL program is giving error.

whether any other choice is there, please help me.
-sunil

 

[Ralf Hildebrandt]

I have 16 values. I ahve to compare those values and i have to
get minimum value and it's address. I am comparing those all 16 avlues
with by 8 comaprators, next the 8 output values by 4 comparator and so
on......

-> This leads to combinational logic (remember: every comparator is a
subtractor).

at last i am getting minimum value but how i can get address of
that value.

Everytime you compare two values A and B, set a bit, that indicates, if
A or B is bigger. Do it for every comparator. This will result in a tree
of comparison results, that can be evaluated back to the adress with the
minimum value.



Last of all: Think about a serialized approach (compare only two values
and do it step by step). This will result in a much smaller circuit, but
will lead to slower computing.

Ralf

 

[valentin tihomirov]

Do you know how associative memory, i.e. get address/value by key, works?
You have a mux that chooses between val1 and val2 basing on their values
(btw, what do you select if they are equal, both is not possible), in other
words, value selection by comparator's output. You should have a second
(address) parallel channel controlled by the same comparator. In associative
memory you have two channels: value and operation status success bit. BTW,
this is not VHDL issue.

 

[valentin tihomirov]

-> This leads to combinational logic (remember: every comparator is a
subtractor).

How do you perform calculations without using logic?

Last of all: Think about a serialized approach (compare only two values
and do it step by step). This will result in a much smaller circuit, but
will lead to slower computing.

x:= a + b + c + d -> x := ((a + b) + c) + d
means N adders and N adder delays

The original idea
x := (a+b) + (c+d)
requires N adders and takes log2(N) adder delays; therefore, is considered
better. This is what optimizers should do.

 

[Ralf Hildebrandt]

How do you perform calculations without using logic?

Maybe I am misunderstood.
Combinational logic is "just a buch of gates" without any memory element.
Sequential logic includes memory elements (latch, flipflops, RAM...)

x:= a + b + c + d -> x := ((a + b) + c) + d
means N adders and N adder delays

The original idea
x := (a+b) + (c+d)
requires N adders and takes log2(N) adder delays; therefore, is considered
better. This is what optimizers should do.

But what about using just *one* adder to compare two values step by
step? It takes N steps to compute the result and some registers are
needed to store some information (which operand was bigger during the
last comparison plus a simple state machine), but it could be much
smaller than using N adders.

-> It depends on the constraints, which way is the best (parallel or
serial). Therefor I said "think about".


Ralf