Transforming vector position to binary value

V

Vazquez

Guest
Hi @all,

I have a vector with 32 bit [31 downto 0].


After some calculations the vector could look like that:

a)0000 0000 0000 0000 0000 0000 1000 0000
or
b)0000 0000 1000 0000 0000 0100 0000 0000


How can I transform the position(s) of the one(s) in the
vector to a corresponding binary value?

for example in a) '1' at position 7 of the vector =>
binary value would be: b111

Is there some simple and fast possibility to make this transformation?

Thanks a lot.

Best regards
 
"Vazquez" <andres.vazquez@gmx.de> wrote in message
news:eee19a7a.0311110102.5b8b5e35@posting.google.com...
.
After some calculations the vector could look like that:

a)0000 0000 0000 0000 0000 0000 1000 0000
or
b)0000 0000 1000 0000 0000 0100 0000 0000

How can I transform the position(s) of the one(s) in the
vector to a corresponding binary value?
for example in a) '1' at position 7 of the vector =
binary value would be: b111

Is there some simple and fast possibility to make this transformation?
Click to expand...
How do you create a "binary value" representing the word that
has more than one bit set?

My favourite onehot-to-binary recoder is:

variable onehot: std_logic_vector(LOTS downto 0);
variable binary: std_logic_vector(FEWER downto 0);
...
binary := (others => '0');
for i in onehot'range loop
binary := binary or std_logic_vector(to_unsigned(i));
end loop;

Verilog version available at extra cost :)

This optimises well (to a collection of wide OR gates) in
every synthesis tool I've tried. But it will fail horribly
if more than one bit of the input "onehot" word is set.
What do you expect to happen, in case (b)?
--

Jonathan Bromley, Consultant

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

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail: jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
If i understand you correctly, you request for a feature called priority
encoding. It also resolves cases with two or more 1s using priority.
 
"Jonathan Bromley" <jonathan.bromley@doulos.com> wrote

[Before checking his response!]

in message news:boq9r6$t2l$1$8302bc10@news.demon.co.uk...

[...]

My favourite onehot-to-binary recoder is:
[...]
binary := (others => '0');
for i in onehot'range loop
binary := binary or std_logic_vector(to_unsigned(i));
end loop;
Click to expand...
Whoops. That should have been...

binary := (others => '0');
for i in onehot'range loop
if onehot(i) = '1' then
binary := binary or std_logic_vector(to_unsigned(i));
end if;
end loop;

It's usually a good idea to make the output somewhat
dependent on the input ;-) Sorry.

--

Jonathan Bromley, Consultant

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

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail: jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

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

it is the following background:

The 32-bit vector can have up to 4 locations with '1', for example

0000 1000 0000 0000 0101 0000 0000 0100

The ones indicate that a data packet has been found at the different
write-address-positions of a cam.
In a second step I have to fulfill a second check in a separate
RAM structure. For this purpose
I want to create out of the 32-bit-HIT-vector 4 addresses.
In the example shown that would mean that I have to create the
following
addresses (for the second check step):
1. b00010
2. b01010
3. b01110
4. b11011
These addresses will then be assigned sequentially to the RAM
wraddress port.
So is there a possibility to get these four addresses out of the
32-bit-vector within one clock cycle?

Thanks a lot.

Best Regards
Andres V.
 
"Vazquez" <andres.vazquez@gmx.de> wrote in message
news:eee19a7a.0311110648.5e79e75c@posting.google.com...

The 32-bit vector can have up to 4 locations with '1', for example

0000 1000 0000 0000 0101 0000 0000 0100

I want to create out of the 32-bit-HIT-vector 4 addresses.
In the example shown that would mean that I have to create the
following
addresses (for the second check step):
1. b00010
2. b01010
3. b01110
4. b11011
Click to expand...
That is a VERY different problem from the one you first posted!

So is there a possibility to get these four addresses out of the
32-bit-vector within one clock cycle?
Click to expand...
I'm sure it is possible, but it is certainly difficult and I
cannot see a clean solution right now. However...

These addresses will then be assigned sequentially
to the RAM wraddress port.
Click to expand...
If the four RAM writes are to be sequential, why not
obtain the four addresses sequentially? That would be
much simpler. Use a priority encoder (as Valentin
suggested) to locate the first 1 bit. Then, while
you are writing to the chosen RAM location, clear that
first bit to 0 and use the same priority encoder again
to find the second 1 bit. Keep going like this until
you have cleared the whole 32-bit input word to zero.

A 32-to-5-bit priority encoder is not trivial, but it
should be OK unless your clock speed is very fast.
--
Jonathan Bromley, Consultant

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

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail: jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

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

"Jonathan Bromley" <jonathan.bromley@doulos.com> wrote in message
news:boqucv$8go$1$8300dec7@news.demon.co.uk...
"Vazquez" <andres.vazquez@gmx.de> wrote in message
news:eee19a7a.0311110648.5e79e75c@posting.google.com...

The 32-bit vector can have up to 4 locations with '1', for example

0000 1000 0000 0000 0101 0000 0000 0100

I want to create out of the 32-bit-HIT-vector 4 addresses.
In the example shown that would mean that I have to create the
following
addresses (for the second check step):
1. b00010
2. b01010
3. b01110
4. b11011

That is a VERY different problem from the one you first posted!

So is there a possibility to get these four addresses out of the
32-bit-vector within one clock cycle?

I'm sure it is possible, but it is certainly difficult and I
cannot see a clean solution right now. However...

These addresses will then be assigned sequentially
to the RAM wraddress port.

If the four RAM writes are to be sequential, why not
obtain the four addresses sequentially? That would be
much simpler. Use a priority encoder (as Valentin
suggested) to locate the first 1 bit. Then, while
you are writing to the chosen RAM location, clear that
first bit to 0 and use the same priority encoder again
to find the second 1 bit. Keep going like this until
you have cleared the whole 32-bit input word to zero.

A 32-to-5-bit priority encoder is not trivial, but it
should be OK unless your clock speed is very fast.
--
Jonathan Bromley, Consultant

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

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW,
UK
Tel: +44 (0)1425 471223 mail:
jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web:
http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Click to expand...
I missed the original postings but the sequential detection sounds like a
great approach from what I see above.

The 32-to-5-bit priority encoder is something I worked with just recently,
targeting the Virtex-II architecture with Synplify Verilog. The speeds I
was able to get were greater than 300 MHz. If you're working with these
tools or just want to see the approach, feel free to reply-email directly.
I could probably (suggest ways to) push the speed even further with some
tricks I have left.

- John_H
 
As I had posted a while ago, the Virtex-II BlockRAM is surprisingly
efficient as a priority encoder.
Use one BlockRAM as a dual-ported 4K x 4 ROM.
Feed 12 inputs as address to one port, and the next 12 bits as address
to the other port. That gives you two sets of 4 outputs defining the
priority-encoded position in the two 12-bit inputs separately.No problem
with multiple 1s! Should work at 200+ MHz, but note that the BlockROM
is a synchronous device, it operates on a clock edge!
The remaining 8 inputs and the combining of the eight BlockROM outputs
can be done the conventional way, but might also be done in another
BlockROM (generating a second clock latency!)
Peter Alfke, Xilinx Applications
 
Peter Alfke <peter@xilinx.com> wrote in message news:<3FB118A8.2B5D02BF@xilinx.com>...
As I had posted a while ago, the Virtex-II BlockRAM is surprisingly
efficient as a priority encoder.
Use one BlockRAM as a dual-ported 4K x 4 ROM.
Feed 12 inputs as address to one port, and the next 12 bits as address
to the other port. That gives you two sets of 4 outputs defining the
priority-encoded position in the two 12-bit inputs separately.No problem
with multiple 1s! Should work at 200+ MHz, but note that the BlockROM
is a synchronous device, it operates on a clock edge!
The remaining 8 inputs and the combining of the eight BlockROM outputs
can be done the conventional way, but might also be done in another
BlockROM (generating a second clock latency!)
Peter Alfke, Xilinx Applications
Click to expand...
Dear Mr Alfke,

thank you for your proposal.
Do you have some application note in which the connection of the ROMs is explained?
How many ROMs are used at all? As I understand you there are used four ROMs?
Do you mean with "to one port" the write address port and with "to other port"
the read address port?

Thank you for your help.

Best regards
A. Vazquez
G&D System Development
 
Andres,
let me explain:

There is no app note, but it is really quite simple.

Any Virtex BlockRAM can be loaded with data contained in the
configuration bitstream. If you then never write again, you have a BlockROM.

Obviously, a 4K x 4 ROM can detect anything on its 12 address lines, and
describe it as a 4-bit output. This is all well-known.

The trick that makes this solution so efficient is the use of the other
port of the same BlockROM. The two ports are completely independent.
There is no read port or write port. That's just a typical use when
implementing FIFOs. You can use both ports to write, or - as in this
case - you use both ports to read. Since you use the same priority
encoding for both sets of 12 inputs, you can use the common ROM storage,
and thus handle 24 inputs, giving you two sets of 4 outputs.

It's the dual-ported nature of the ROM, and using the same encoding for
both sets of 12 address inputs, that makes this so efficient.

The rest of the logic, combining the two sets of 4-bit outputs, and
handling the additional 8 inputs ( for a 32-bit encoder), will be conventional.

I like using BlockRAMs for unconventional applications, especially since
that relieves the interconnect structure, and - if you have more
BlockRAMs than you need - its actually free (not just efficient) :)

Peter Alfke, Xilinx Applications
 
What's the clock frequency for this design?
At what rate are the 32 bit words generated?

Can you take 32 clocks to produce the desired results?
If not, if the frequency of operation is low enough, you could multiply it
by 32 and get your results within a clock or two.

If none of the above works, you could probably pipeline a solution. During
each stage a prioritized decoder would pick off the first "1" and give you a
result. At the same time, that "1" would be masked off so that it won't
appear in the next stage. Repeat four times and you have your solution. It
will probably take four to eight clocks depending on details (don't have my
thinking cap fully on).


--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_" = "martineu"
 
"Peter Alfke" wrote:

I like using BlockRAMs for unconventional applications
....
Click to expand...

Is there an app note or techxclusives article listing unconventional uses of
BlockRAM's and multipliers? That could be useful to trigger some creative
thinking.


--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_" = "martineu"
 
"Martin Euredjian" <0_0_0_0_@pacbell.net> wrote in message
news:%gKsb.733$Nw.45922360@newssvr21.news.prodigy.com...
"Peter Alfke" wrote:
I like using BlockRAMs for unconventional applications

Is there an app note or techxclusives article listing
unconventional uses of BlockRAM's and multipliers?
That could be useful to trigger some creative thinking.
Click to expand...
Don't be silly; if it's in a Xilinx appnote, it's _ipso facto_
conventional :)
--
Jonathan Bromley, Consultant

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

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail: jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
"Martin Euredjian" <0_0_0_0_@pacbell.net> wrote in message
news:%gKsb.733$Nw.45922360@newssvr21.news.prodigy.com...
"Peter Alfke" wrote:

I like using BlockRAMs for unconventional applications
...

Is there an app note or techxclusives article listing unconventional uses
of
BlockRAM's and multipliers? That could be useful to trigger some creative
thinking.
Click to expand...
The 234 character URL to the TechXclusives article is digested down to this:
http://tinyurl.com/uvf1

The title of the article is "Using Leftover Multipliers and Block RAM in
Your Design"


- John_H
 
Martin, there is, and has been for over 2 years:


Using Leftover Multipliers and Block RAM in your Design
04/23/2001

By yours truly

BTW, the search engine in the upper left corner of the xilinx.com


website has recently been dramatically improved. (But it seems to need
single ( ' not " ) quotes to AND multiple words together).

Peter
===================
Martin Euredjian wrote:
Is there an app note or techxclusives article listing unconventional uses of
BlockRAM's and multipliers? That could be useful to trigger some creative
thinking.
Click to expand...
 
Martin, there is, and has been for over 2 years:


Using Leftover Multipliers and Block RAM in your Design
04/23/2001 by yours truly

BTW, the search engine in the upper left corner of the xilinx.com

website has recently been vastly improved. (But it seems to need
single ( ' not " ) quotes to AND multiple words together).

Peter
===================
Martin Euredjian wrote:
Is there an app note or techxclusives article listing unconventional uses of
BlockRAM's and multipliers? That could be useful to trigger some creative
thinking.
Click to expand...
 
BTW, the search engine in the upper left corner of the xilinx.com
website has recently been dramatically improved. (But it seems to need
single ( ' not " ) quotes to AND multiple words together).
Click to expand...
Those hidden gems in the Xilinx website. It's kind of nice not being able
to find anything with ease sometimes 'cause every so often you run across
something interesting by sheer luck and it's like discovering a whole new
world. :)


--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_" = "martineu"
 
Martin,

When I first joined Xilinx, I spent hours going through the external web
site. I was amazed at just how much "stuff" there was out there. Often I
read a question here, and point people immediately to the online answer. I do
have to remember that it is is not as easy for others to find these gems
(hidden or not) as it is for me.

My favorite pitch to a prospective new customer is to ask them to go to our
website, and place a query for some kind of information (eg "Signal
Integrity"), and then do the same for the competition. Not only do we have
many more "hits" on just about any topic you can think of, the quality of the
information is vastly superior. The only problem we seem to have is how to
make it easier to get at all of it (which, as Peter points out, we are trying
constantly to improve).

Austin

Martin Euredjian wrote:

BTW, the search engine in the upper left corner of the xilinx.com
website has recently been dramatically improved. (But it seems to need
single ( ' not " ) quotes to AND multiple words together).

Those hidden gems in the Xilinx website. It's kind of nice not being able
to find anything with ease sometimes 'cause every so often you run across
something interesting by sheer luck and it's like discovering a whole new
world. :)

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_" = "martineu"
Click to expand...
 
Having had an occasional hand at doing web work for myself I wholy
appreciate how complex the problem can be. The quality of information on
the Xilinx site is definetly up there.

....now, if you could only switch from eight menus per page (or whatever it
is) to a more "linear" environment, that would be great.

There's a little gem out there in the Web design world called "Typo3"
(http://typo3.org/) that is, as I understand it, gaining momentum. The tool
builds fully database driven websites with very powerful back-end authoring
capabilities. The best thing is that the menu structure is maintained
automagically.


--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_" = "martineu"






"Austin Lesea" <Austin.Lesea@xilinx.com> wrote in message
news:3FB3D288.1F64DA29@xilinx.com...
Martin,

When I first joined Xilinx, I spent hours going through the external web
site. I was amazed at just how much "stuff" there was out there. Often I
read a question here, and point people immediately to the online answer.
I do
have to remember that it is is not as easy for others to find these gems
(hidden or not) as it is for me.

My favorite pitch to a prospective new customer is to ask them to go to
our
website, and place a query for some kind of information (eg "Signal
Integrity"), and then do the same for the competition. Not only do we
have
many more "hits" on just about any topic you can think of, the quality of
the
information is vastly superior. The only problem we seem to have is how
to
make it easier to get at all of it (which, as Peter points out, we are
trying
constantly to improve).

Austin

Martin Euredjian wrote:

BTW, the search engine in the upper left corner of the xilinx.com
website has recently been dramatically improved. (But it seems to
need
single ( ' not " ) quotes to AND multiple words together).

Those hidden gems in the Xilinx website. It's kind of nice not being
able
to find anything with ease sometimes 'cause every so often you run
across
something interesting by sheer luck and it's like discovering a whole
new
world. :)

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_" = "martineu"
Click to expand...
 
Off topic:
One of the nicest websites to navigate is the BBC's:
http://news.bbc.co.uk/
(If you are interested in world news, like I am...)
Peter Alfke
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top