Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

Real vector length of an unsinged number

Status
Not open for further replies.
S

shaiko

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,302
Hello,

Please help me write a function that receives an unsigned vector of an unconstraid lengh and returns the position of the first '1' from the right.
For example :

Code: 
constant x unsigned ( 7 downto 0 ) := "000[COLOR="#FF0000"]1[/COLOR]010" ; -- for x the function shall return the integer 3.
constant y unsigned ( 7 downto 0 ) := "00[COLOR="#FF0000"]1[/COLOR]1010" ; -- for y the function shall return the integer 4.
constant z unsigned ( 7 downto 0 ) := "0000000" ; -- for z the function shall return the integer 0.
 

shaiko said:
Hello,

Please help me write a function that receives an unsigned vector of an unconstraid lengh and returns the position of the first '1' from the right.
For example :

Code: 
constant x unsigned ( 7 downto 0 ) := "000[COLOR=#ff0000]1[/COLOR]010" ; -- for x the function shall return the integer 3.
constant y unsigned ( 7 downto 0 ) := "00[COLOR=#ff0000]1[/COLOR]1010" ; -- for y the function shall return the integer 4.
constant z unsigned ( 7 downto 0 ) := "0000000" ; -- for z the function shall return the integer 0.
Click to expand...

Your examples don't demonstrate what you say you want. The rightmost 1 for 'x' and 'y' is bit 1, not 3 and 4 as you listed.

Untested, not compiled but believed to be close enough for you to finish it off. Also assuming that you really do mean rightmost bit and not the leftmost bit.

Code: 
function Whats_The_Right_Bit(Arg: unsigned) return integer is
begin
   if Arg'right < Arg'left then
      for i in Arg'right to Arg'left loop
         if Arg(i) = '1' then
            return(i);
         end if;
      end loop;
      return(0);
   else
      for i in Arg'right downto Arg'left loop
         if Arg(i) = '1' then
            return(i);
         end if;
      end loop;
      return(0);
   end if;
end function Whats_The_Right_Bit;

Lastly, if you really are looking for the leftmost bit, then one way is to change the function above to flip the usage of 'left and 'right. However, a better way that builds on working tested code is to recognize that if you're looking to return the index of the leftmost bit of an unsigned number, then this is equivalent to the base 2 log of that number. Use the 'log2' function instead (Google for something like 'log2 VHDL FAQ' and you should run across it).

Kevin Jennings
 
Last edited:
  • Like
Reactions: shaiko

    S

    shaiko

    Points: 2
    Helpful Answer Positive Rating
Kevin,

You were right correcting me.
What I want the function to return is the position of the leftmost '1' of the unsigned vector.

What's the correct function for it ?

I know I can do it with log2 for integers - but I want to be able to do it with unsigned (without converting it to integers)
 

shaiko said:
Kevin,

You were right correcting me.
What I want the function to return is the position of the leftmost '1' of the unsigned vector.

What's the correct function for it ?

I know I can do it with log2 for integers - but I want to be able to do it with unsigned (without converting it to integers)
Click to expand...

Refer to http://www.eda.org/comp.lang.vhdl/FAQ1.html

Search for log2 function. Although that function works with integers, it can be easily modified to work with unsigned. I haven't tried it but I don't see any reason why you should have to do anything more than simply alter the I/O type to 'unsigned', the only math that gets done is divide by 2 and add 1. Even if you need log2 at run time and not just to compute constants, the function as written does work even though it is written as a recursive function. That I have tried (albeit with integers not unsigned).

Kevin Jennings
 
  • Like
Reactions: shaiko

    S

    shaiko

    Points: 2
    Helpful Answer Positive Rating
Lastly, if you really are looking for the leftmost bit, then one way is to change the function above to flip the usage of 'left and 'right.
Click to expand...

So the function should look like this ?

Code: 
function Whats_The_Left_Bit(Arg: unsigned) return integer is
begin
   if Arg'left < Arg'right then
      for i in Arg'left to Arg'right loop
         if Arg(i) = '1' then
            return(i);
         end if;
      end loop;
      return(0);
   else
      for i in Arg'left downto Arg'right loop
         if Arg(i) = '1' then
            return(i);
         end if;
      end loop;
      return(0);
   end if;
end function Whats_The_Left_Bit;
 

This is simpler, but I have not tested it:

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9

function Whats_The_Left_Bit(Arg: unsigned) return integer is
begin
  for i in Arg'range loop
    if Arg(i) = '1' then
      return i;
    end if;
  end loop;
  return 0;
end function Whats_The_Left_Bit;


The return value zero is ambiguous, so I think you should adjust the definition of the function.
You could return '-1' if no bit is set, or return i+1 when a '1' is found.
 
  • Like
Reactions: shaiko

    S

    shaiko

    Points: 2
    Helpful Answer Positive Rating
Kevin,

How is it possible to use the log2 function in the post for unsigned if it uses the division ("/") operator ?
Isn't this operator intended for integers only ??

- - - Updated - - -

You could return '-1' if no bit is set, or return i+1 when a '1' is found.
Click to expand...

std_match,
I understand the motivation behind returning '-1' (I suppose thats to indicate an error)
I didn't understand your note about returning i+1 though...if we are interested in the possition of the bit from the left - then we should return i and not i+1. Am I right?
 

shaiko said:
Kevin,

How is it possible to use the log2 function in the post for unsigned if it uses the division ("/") operator ?
Isn't this operator intended for integers only ??
Click to expand...

No, '/' is not just for integers. The ieee.numeric_std package defines the division operator for unsigned (as well as +, - and *). Synthesis tools are smart enough to figure out that divide by 2 is equivalent to right shifting by one bit so the implementation of x/2 is efficient. There is nothing restricting use of '/' for dividing any arbitrary unsigned signals, but the logic that results if you divide by a non-power-of-2 is something one is generally not happy about. Since log2 only does a divide by 2 though, this is not a concern in this case.

Kevin Jennings
 
  • Like
Reactions: shaiko

    S

    shaiko

    Points: 2
    Helpful Answer Positive Rating
I don't understand the recursion concept.
How can the log2 be used (marked in red) inside the same function prototype that defines it ?!

Code: 
       function log2 (x : positive) return natural is 
       begin
         if x <= 1 then
           return 0;
         else
           [COLOR="#FF0000"]return log2 (x / 2) + 1;[/COLOR]
         end if;
       end function log2;
 

shaiko said:
I don't understand the recursion concept.
How can the log2 be used (marked in red) inside the same function prototype that defines it ?!

Code: 
       function log2 (x : positive) return natural is 
       begin
         if x <= 1 then
           return 0;
         else
           [COLOR=#ff0000]return log2 (x / 2) + 1;[/COLOR]
         end if;
       end function log2;
Click to expand...

From a simulation and parsing perspective, the compiler knows the type of the argument and return value which is all it needs in order to call the function. The exit from the recursion occurs when log2 is eventually called with a value that is less than or equal to 1. No matter what you input on the original call to log2, the iterative dividing by 2 will eventually get to a number that is less than 1.

From a synthesis perspective, since the number of bits in the argument is known, the tool is able to unroll the recursion into the appropriate number of compares and generate the necessary logic. I would suggest you try the code out in simulation and synthesis to get a better feel. Recursion is synthesizable, but not necessarily easy to describe in this type of forum.

Kevin Jennings
 
Last edited:
  • Like
Reactions: shaiko

    S

    shaiko

    Points: 2
    Helpful Answer Positive Rating
K-J

What do you think about std_match's function.
It will do the same - right ?
 

shaiko said:
std_match,
I understand the motivation behind returning '-1' (I suppose thats to indicate an error)
I didn't understand your note about returning i+1 though...if we are interested in the possition of the bit from the left - then we should return i and not i+1. Am I right?
Click to expand...

You could also subtract 1 from the returned value :grin:

Your original requirements will give the same return value (zero) for input "0000000" and "0000001" (downto range). Is that what you want?

What we discuss now is very similar to the last lines in posting #22 in the following thread:

https://www.edaboard.com/threads/247443/
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top