Finding MSB in a std_logic_vector

A

Aiken

Guest
data_in : in std_logic_vector(data_size-1 downto 0)
data_out: out std_logic_vector((log2(data_size downto 0)

If the input vector is "000110101", then output is "101" = 5

I don't want to use one case statement to due with it (since it will
create not balance logic)
How can I code it to have balance combination logic and minimize the
level of logic.

p.s. no register in the desin
 
"Aiken" <aikenpang@gmail.com> wrote in message
news:ed8ab9d0-e91d-4a95-8222-73ff0e772759@f20g2000yqg.googlegroups.com...
data_in : in std_logic_vector(data_size-1 downto 0)
data_out: out std_logic_vector((log2(data_size downto 0)
Click to expand...
You're missing a couple of parentheses there, I'm guessing you mean
data_out: out std_logic_vector(log2(data_size) downto 0)

If the input vector is "000110101", then output is "101" = 5
Click to expand...
Hmmm....I guess you expect it to eminently clear what the function is based
on a single input/output vector description.

So, I'm assuming then that the output is just the lowermost bits of the
input...It's also possible to come up with a number of other transformations
that have the given input and output vector that you mentioned.

I don't want to use one case statement to due with it (since it will
create not balance logic)
How can I code it to have balance combination logic and minimize the
level of logic.
Click to expand...
The following would seem to do the trick...hard to tell though based on your
problem description since you didn't define what the function is that you're
trying to compute.
data_out <= data_in(data_out'range)

Kevin Jennings
 
Aiken wrote:
data_in : in std_logic_vector(data_size-1 downto 0)
data_out: out std_logic_vector((log2(data_size downto 0)

If the input vector is "000110101", then output is "101" = 5
Click to expand...
I would load a counter variable with 8
and a shifter variable with the input vector
then loop a shift left and a decrement until I saw a one.

I don't want to use one case statement to due with it (since it will
create not balance logic)
How can I code it to have balance combination logic and minimize the
level of logic.
Click to expand...
That is academic

p.s. no register in the design
Click to expand...
That is unfortunate.
The loop would have to be an unclocked FOR.

-- Mike Treseler
 
On Sat, 20 Dec 2008 12:05:52 -0800 (PST), Aiken <aikenpang@gmail.com>
wrote:

data_in : in std_logic_vector(data_size-1 downto 0)
data_out: out std_logic_vector((log2(data_size downto 0)

If the input vector is "000110101", then output is "101" = 5

I don't want to use one case statement to due with it (since it will
create not balance logic)
How can I code it to have balance combination logic and minimize the
level of logic.

p.s. no register in the desin
Click to expand...
You could use a SN74148.

They can even be cascaded for larger word widths.
I doubt you could do it with fewer levels of logic.

- Brian
 
"Aiken" <aikenpang@gmail.com> wrote in message
news:ed8ab9d0-e91d-4a95-8222-73ff0e772759@f20g2000yqg.googlegroups.com...
data_in : in std_logic_vector(data_size-1 downto 0)
data_out: out std_logic_vector((log2(data_size downto 0)

If the input vector is "000110101", then output is "101" = 5
Click to expand...
The MSB of a vector is equal to the log2 of that vector

data_out <= std_logic_vector(log2(unsigned(data_in)));

Google for the synthesizable code that implement log2.

Kevin Jennings
 
How about something like this?

function get_vector_msb(p1 : std_logic_vector) return natural is
variable v_search_vector : std_logic_vector(p1'length -1 downto 0);
begin
v_search_vector := p1;
for i in v_search_vector'left downto 0 loop
if (v_search_vector(i) = '1') then
return i;
end if;
end loop;
return 0;
end function;

and then in your code,
Use IEEE.numeric_std.all;
. . . . . .
sig_name <= std_logic_vector(to_unsigned(get_vector_msb(input_vector),
sig_name'length));

It should synthesise to an and-or array, boolean optimised by synthesis.

BTW as far as I'm aware there will be a function find_leftmost() in VHDL
2006 or sometime later.

Aiken schrieb:
data_in : in std_logic_vector(data_size-1 downto 0)
data_out: out std_logic_vector((log2(data_size downto 0)

If the input vector is "000110101", then output is "101" = 5

I don't want to use one case statement to due with it (since it will
create not balance logic)
How can I code it to have balance combination logic and minimize the
level of logic.

p.s. no register in the desin
Click to expand...
 
On Sat, 20 Dec 2008 12:05:52 -0800 (PST), Aiken wrote:

data_in : in std_logic_vector(data_size-1 downto 0)
data_out: out std_logic_vector((log2(data_size downto 0)

If the input vector is "000110101", then output is "101" = 5
Click to expand...
because the MSB is bit 5, right?

First, the obvious question of specification:
given input value "00000001", I guess you would expect
an output of "0000" because the MSB is bit 0. But what
is the correct output for an input of exactly 0?

Second, the solution: as has been discussed here many
times, the most efficient implementation is likely to
be based on a binary-chop search through the input
vector. As a side-effect, this also gives you the
input value left-shifted so that its most significant
1 bit is in the MSB (leftmost) bit position.

Note "likely to be" because synthesis can do pretty
clever optimizations on this kind of combinational
logic. However, for large input vectors (more than
about 16 bits), the binary-chop method is usually best.

Here's how it would work on your example, shrunk to 8 bits:

input 00110101 output xxx

step 1: are the 4 MSBs all zero?
- No, so...
- set the output 4s bit to 1
- do NOT left-shift the input by 4 bits

input 00110101 output 1xx

step 2: are the 2 MSBs all zero?
- Yes, so...
- set the output 2s bit to 0
- left-shift the input by 2 bits

input 11010100 output 10x

step 3: is the 1 MSB zero?
- No, so...
- set the output 1s bit to 1
- do NOT left-shift the input by 1 bit

input 11010100 output 101

There's your answer in only 3 rather simple levels of logic.
In general, input word width of 2**N costs you N levels.
Each level is only a compare-to-zero and a multiplexer
to do the optional left-shift. It's also very easy to
pipeline (but you say you don't want any registers).

With a bit of care you can easily write VHDL code to
generalize this for any bit width. (Another of those
"don't try this in Verilog, folks" examples.)
--
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.
 
p.s. no register in the desin
Click to expand...
It seems you should start with a row
of OR gates starting with the MSB and
serializing down to the LSB. The output
of those serial gates are easier to decode
into binary.

SERIAL GATE POSITION
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 1 1 0 1 0
0 0 0 0 1 1 1 0 1 1
0 0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1

I'm not sure how to code this in the generic
form but there is a relatively simple pattern.

POSITION(0)<= S(7) or
(S(5) and not S(6))or
(S(3) and not S(4))or
(S(1) and not S(2) ;

POSITION(1)<=
S(7) or S(6) or
((S(2) or S(3)) and not(S(5) or S(6))) ;

POSITION(2)<=
S(7) or S(6) or S(5) or S(4) ;

This logic creates a 000 output when the
input is all zeroes whereas your original
post is not clear how to distinguish a
0000000 from a 0000001 input.

Brad Smallridge
AiVision
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top