EmbDev.net

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


von Antony M. (antony_mat)


Rate this post
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
von Klaus (Guest)


Rate this post
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

von Antony M. (antony_mat)


Rate this post
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.

von Klaus (Guest)


Rate this post
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.

von Klaus (Guest)


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

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

von VHDL hotline (Guest)


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

von antony mathew (Guest)


Rate this post
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 '

von helpend (Guest)


Rate this post
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.

von Lothar M. (Company: Titel) (lkmiller) (Moderator)


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

Please log in before posting. Registration is free and takes only a minute.
Existing account
Do you have a Google/GoogleMail account? No registration required!
Log in with Google account
No account? Register here.