How best to find out minimum value among eight 10-bit unsign

[Mr. Ken]

Hello everybody,

Among eight 10 bit values, I need to select the smallest and return its
index.
This is basically to replace the MINMAX module in Synopsys designware.

64 comparisons is ok for me, but I don't want all the trouble.

How can I approach it?

 

[Jonathan Bromley]

On Wed, 20 Dec 2006 18:51:24 +0800, "Mr. Ken" <Mr. Ken@asdf> wrote:

Among eight 10 bit values, I need to select the smallest and return its
index.
How can I approach it?

Does the following do what you require?

min(
min(
min(v1, v2),
min(v3, v4)
),
min(
min(v5, v6),
min(v7, v8)
)
)

That looks like 7 comparisons and 7 multiplexers to me.
The multiplexers could easily steer the appropriate index
value to an auxiliary output, as well as steering the minimum
value to its output. Think of the index as three extra bits of
data that don't take part in the comparison.

In VHDL you could easily code this as a recursive function. In
Verilog that is less likely to be useful, since you can't pass
unconstrained arrays to functions.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Mr. Ken]

Yeah, basically that was what I did. With seven comparators and some
other logics I managed to get it right. It's a bit intriguing at first since
if
there were equal minimums, my code gave the larger index. It took one more
test to get it return the smaller index.

Thank you Jonathan.



"Jonathan Bromley" <jonathan.bromley@MYCOMPANY.com> wrote in message
news:d7aio2hn504e0d3vd34gqdlbevjh4mbl26@4ax.com...

On Wed, 20 Dec 2006 18:51:24 +0800, "Mr. Ken" <Mr. Ken@asdf> wrote:

Among eight 10 bit values, I need to select the smallest and return its
index.
How can I approach it?

Does the following do what you require?

min(
min(
min(v1, v2),
min(v3, v4)
),
min(
min(v5, v6),
min(v7, v8)
)
)

That looks like 7 comparisons and 7 multiplexers to me.
The multiplexers could easily steer the appropriate index
value to an auxiliary output, as well as steering the minimum
value to its output. Think of the index as three extra bits of
data that don't take part in the comparison.

In VHDL you could easily code this as a recursive function. In
Verilog that is less likely to be useful, since you can't pass
unconstrained arrays to functions.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Jonathan Bromley]

On Wed, 20 Dec 2006 23:35:15 +0800, "Mr. Ken" <Mr.Ken@novice.com>
wrote:

Yeah, basically that was what I did. With seven comparators and some
other logics I managed to get it right. It's a bit intriguing at first since
if
there were equal minimums, my code gave the larger index. It took one more
test to get it return the smaller index.

If you made the comparisons <= instead of <, would that
not preserve the index ordering??? (lots of question-marks
because I'm not sure without doing a bit more work)

However, you definitely COULD do it by concatenating the
index on to the end of the data word, and including it in
the test. The comparators would then be 3 bits wider,
but the sort would be stable.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Utku Özcan]

[Jonathan Bromley]

However, you definitely COULD do it by concatenating the
index on to the end of the data word, and including it in
the test. The comparators would then be 3 bits wider,
but the sort would be stable.

Supposing the codewords can be indexed, then 10 comparisons can be done
with one comparator and 10 clock cycles, which saves a lot of hardware
at expense of computation latency, but probably with a higher speed in
a given technology.

If the codewords are stored in a RAM, the design can be even much
easier, because you don't need to put additional design to handle
indices.

Utku.

 

[Mr. Ken]

"Jonathan Bromley" <jonathan.bromley@MYCOMPANY.com> wrote in message
news:einio2hnt65uaruh5ib9kkeiskfoou287d@4ax.com...

On Wed, 20 Dec 2006 23:35:15 +0800, "Mr. Ken" <Mr.Ken@novice.com
wrote:

Yeah, basically that was what I did. With seven comparators and some
other logics I managed to get it right. It's a bit intriguing at first
since
if
there were equal minimums, my code gave the larger index. It took one more
test to get it return the smaller index.

If you made the comparisons <= instead of <, would that
not preserve the index ordering??? (lots of question-marks
because I'm not sure without doing a bit more work)

In the priority encoding one I could preserve the index ordering. Basically
it's similar to <=.

However, you definitely COULD do it by concatenating the
index on to the end of the data word, and including it in
the test. The comparators would then be 3 bits wider,
but the sort would be stable.

Yeah, this is definitely an easy workaround.

--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Mr. Ken]

"Utku Özcan" <utku.ozcan@gmail.com> wrote in message
news:1166754159.414765.297230@79g2000cws.googlegroups.com...

Supposing the codewords can be indexed, then 10 comparisons can be done
with one comparator and 10 clock cycles, which saves a lot of hardware
at expense of computation latency, but probably with a higher speed in
a given technology.

If the codewords are stored in a RAM, the design can be even much
easier, because you don't need to put additional design to handle
indices.

Utku.

I could do that, but my requirement was single cycle, and clock is very
slow.
Thank you anyway.