Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- FPGAs and Programmable Solutions
- FPGA Intellectual Property
- Determining the index of the first 1 bit in a vector

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Highlighted
##

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-28-2012
03:03 PM

1,341 Views

Determining the index of the first 1 bit in a vector

Let's say I have a 64b wire, and I want to **efficiently** determine the index of the first 1 bit.

4 Replies

Highlighted
##

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-28-2012
03:33 PM

4 Views

You can use a function, like the one below and hope that Quartus synthesizes it efficiently.

It will produce a rather long combinational path, but I don't think that can be avoided. function [5:0] getIndex(input [63:0] data); integer i; for(i = 63; i >= 0; i = i - 1) begin if (data[63-i] == 1'b1) getIndex = i; end endfunction assign index = getIndex(sum);
Highlighted
##

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-28-2012
04:06 PM

4 Views

I think the most efficient solution involves dividing your 64bit vector in halves recursively.

So, ideally you get a minimum combinatorial path log2(64) long.
Highlighted
##

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-28-2012
05:30 PM

4 Views

There'a discussion about priority bit masking and priority encoding implementations in the Altera *advanced synthesis cookbook*. I previously did some own comparisions. A behavioral description as suggested by rbugalho doesn't result in a very fast implementation. The cookbook suggest an adder to utilize the carry chain which is quite fast. As discussed in a previous thread, Quartus has some problem to find a timing optimal carry chain solution for non-arithmetical problems. http://www.alteraforum.com/forum/showthread.php?t=28798

Highlighted
##

has anyone tried 3rd party synthesis targeting Altera to see if the carry chains are taken advantage of?

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-28-2012
06:26 PM

4 Views

For more complete information about compiler optimizations, see our Optimization Notice.