EmbDev.net

Forum: FPGA, VHDL & Verilog Puzzle- Position of Most Signi '1' in an N-bit register


Author: Antony Mathew (antony_mat)
Posted on:

Rate this post
0 useful
not useful
Seems simple, but i am done with this question... May be smart guys here 
already have an answer...

I have an N bit Register with any one of the possible 2^N values.
Need to retrieve the position of Most Significant '1' in the register.

eg:-
Consider a 4 bit register reg <= '0101' . Output should be 2.

OR once again

reg <= '1101' . Output should be 3.

Need a hardware algorithm for this...
Cracks my head....

: Edited by User
Author: Klaus (Guest)
Posted on:

Rate this post
0 useful
not useful
There is no such thing like an 'hardware algorithm'. I think you meant 
an: 'algorithm, realized in hardware'.

What about porting a software solution into an hardware? There are 
plenty of results for the search term "most significant bit set". 
Probably some in pure hardware too.

A very famous hit, I assume one of the most often cited results, is: 
http://graphics.stanford.edu/~seander/bithacks.html

Author: Antony Mathew (antony_mat)
Posted on:

Rate this post
0 useful
not useful
There is no such thing like an 'hardware algorithm'. I think you meant
an: algorithm, realized in hardware'.

yep Klaus... thank you for the correction of context.

'algorithm, realized in hardware' seems the correct way of expressing 
it.

Author: Klaus (Guest)
Posted on:

Rate this post
0 useful
not useful
Was a pleasure. :-)

If you need help for transforming an algorithm expressed in an 
imperative language to a hardware description, feel free to ask here any 
further question, provided it is 'specific'.

It may help you, if you reconsider you basic knowledge about the 
hardware structure of a common cpu. This would lead to a merely 
over-engineered design, but is a good start for optimization.

But another solution came to my mind: What about the most simple 
solution? A look-up-table? Not realy educiational but easy. You question 
may be read like asking for a generic solution. So a look-up-table may 
be inefficient for greater bit counts, though.

Author: Klaus (Guest)
Posted on:

Rate this post
0 useful
not useful
And I need help with English. :-)

Should be: "If you need help with transforming ..."

Author: VHDL hotline (Guest)
Posted on:

Rate this post
0 useful
not useful
How much time do you have? N cycles? Make a shift register and a 
counter.

Author: antony mathew (Guest)
Posted on:

Rate this post
0 useful
not useful
No constraint on numb of cycles... method is the only concern. I tried 
with an up/down counter with shifter... But was no success... Can u 
elaborate on that ' VHDL hotline '

Author: helpend (Guest)
Posted on:

Rate this post
0 useful
not useful
antony mathew wrote:
> No constraint on numb of cycles... method is the only concern. I tried
> with an up/down counter with shifter... But was no success... Can u
> elaborate on that ' VHDL hotline '

"No constain on number of cycles"...where is the problem then? Just copy 
the register to a temporary one and shift left until the leftmost bit is 
1. Count the amount of necessary shifts.

Author: Lothar Miller (lkmiller) (Moderator)
Posted on:

Rate this post
0 useful
not useful
Try that:
http://www.lothar-miller.de/s9y/archives/55-Finde-...
You will see several solutions for that problem...

Reply

Entering an e-mail address is optional. If you want to receive reply notifications by e-mail, please log in.

Rules — please read before posting

  • Post long source code as attachment, not in the text
  • Posting advertisements is forbidden.

Formatting options

  • [c]C code[/c]
  • [avrasm]AVR assembler code[/avrasm]
  • [vhdl]VHDL code[/vhdl]
  • [code]code in other languages, ASCII drawings[/code]
  • [math]formula (LaTeX syntax)[/math]




Bild automatisch verkleinern, falls nötig
Note: the original post is older than 6 months. Please don't ask any new questions in this thread, but start a new one.