[Moved] VHDL log base 2 function

shaiko · Feb 29, 2012

Hello,

I use this VHDL log function for vector length sizing.

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
function log2_unsigned ( x : natural ) return natural is
        variable temp : natural := x ;
        variable n : natural := 0 ;
    begin
        while temp > 1 loop
            temp := temp / 2 ;
            n := n + 1 ;
        end loop ;
        return n ;
    end function log2_unsigned ;

The problem is that is rounds down results.
For example:

log2 of 50,000,000 is 25.575

However the output of my function rounds it down to 25.
I want, to round it up to 26 instead. How should I modify it ?

K-J · Feb 29, 2012

shaiko said:
Hello,

I use this VHDL log function for vector length sizing.

function log2_unsigned ( x : natural ) return natural is
variable temp : natural := x ;
variable n : natural := 0 ;
begin
while temp > 1 loop
temp := temp / 2 ;
n := n + 1 ;
end loop ;
return n ;
end function log2_unsigned ;

The problem is that is rounds down results.
For example:

log2 of 50,000,000 is 25.575

However the output of my function rounds it down to 25.
I want, to round it up to 26 instead. How should I modify it ?

Code:

    -----------------------------------------------------------------------------------
    -- Combine the ceil and log2 functions.  ceil_log2(x) then gives the minimum number
    -- of bits required to represent 'x'.  ceil_log2(4) = 2, ceil_log2(5) = 3, etc.
    -----------------------------------------------------------------------------------
    function ceil_log2 (Arg : positive) return natural is
        variable RetVal:    natural;
    begin
        RetVal := log2(Arg);
        if (Arg > (2**RetVal)) then
            return(RetVal + 1); -- RetVal is too small, so bump it up by 1 and return
        else
            return(RetVal); -- Just right
        end if;
    end function ceil_log2;

Kevin Jennings

shaiko · Feb 29, 2012

Hello Kevin,

Combine how ?
Please elaborate

---------- Post added at 20:14 ---------- Previous post was at 19:34 ----------

Do you mean like this

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function log2_unsigned ( x : natural ) return natural is
        variable temp : natural := x ;
        variable n : natural := 0 ;
    begin
        while temp > 1 loop
            temp := temp / 2 ;
            n := n + 1 ;
        end loop ;
        if x > 2 ** n then
            return ( n + 1 ) ; 
        else
            return ( n ) ; 
        end if ;
    end function log2_unsigned ;

K-J · Feb 29, 2012

shaiko said:
Hello Kevin,

Combine how ?
Please elaborate

---------- Post added at 20:14 ---------- Previous post was at 19:34 ----------

Do you mean like this

No, I mean exactly how I posted it.

Kevin Jennings

shaiko · Feb 29, 2012

Kevin,

Can you explain please how what I wrote is different then combining the 2 functions ?

FvM · Feb 29, 2012

I assume, that the log2 problem is related to compile time calculations? Instead of writing your own integer log2() or ceil(log2()) functions, you can also utilize ieee.math real for the calculation.

USE ieee.math_real.log2;
USE ieee.math_real.ceil;

CONSTANT vector_length: integer = integer(ceil(log2(1.0*highest_value)));

shaiko · Feb 29, 2012

sure,
this is for compile time.

Are these standart packages ?

K-J · Feb 29, 2012

shaiko said:
Kevin,

Can you explain please how what I wrote is different then combining the 2 functions ?

I simply showed how I took my own log2 function (which appears to be similar to yours) and combined that with a simple ceiling function to solve the same problem that you are trying to solve. Whether or not yours is equivalent or not is up to you to check.

Kevin Jennings

---------- Post added at 17:11 ---------- Previous post was at 17:09 ----------

FvM said:
I assume, that the log2 problem is related to compile time calculations? Instead of writing your own integer log2() or ceil(log2()) functions, you can also utilize ieee.math real for the calculation.

Even though these functions are used to compute constants and therefore could be synthesizable, support for anything having to do with 'real' type by a synthesis tool should be checked first.

What I posted will be accepted by any synthesis tool.

Kevin Jennings

FvM · Feb 29, 2012

I used the term "compile time calculation" to clarify that I'm referring to a case, where the functions are not actually synthesized, just compiled in an early stage of code evaluation by a synthesis tool.

The power of HDL reveals e.g. in features like calculating a lengthy look-up table from a few lines of code. The present problem can be still solved by simple integer arithmetics, as you have shown. But once you get used to math.real capabilities, you realize, that they offer convenient ways to do the simple stuff as well.

I'm not aware of a VHDL synthesis tool that doesn't support ieee.math.real for similar purposes. Do you know any?

shaiko · Feb 29, 2012

FvM,

Are these standart packages ?

ieee.math_real.log2
ieee.math_real.ceil

Does their use limit the use of other packages ?

TrickyDicky · Feb 29, 2012

There is a simple solution to this.
Initialise n to 1 instead of 0 in the origional function, and then you always get the correct number of bits. (and maybe rename it n_bits, because its not a real log2 anymore).

n_bits(0) = 1 (because you still need 1 bit to represent 0)
n_bits(1) = 1
n_bits(2) = 2
n_bits(4) = 3
n_bits(50000000) = 26

---------- Post added at 00:50 ---------- Previous post was at 00:47 ----------

And PS. ieee.math_real is an actual part of the IEEE standard. There is no problem using this package for initialisation of constants or generics (for any synthesisor Ive ever used, which only extends to ISE, Quartus and synplify 6 years ago)

shaiko · Feb 29, 2012

PHP:

function log2_unsigned ( x : natural ) return natural is
        variable temp : natural := x ;
        variable n : natural := 1 ;
    begin
        while temp > 1 loop
            temp := temp / 2 ;
            n := n + 1 ;
        end loop ;
    end function log2_unsigned ;

like that ?

TrickyDicky · Mar 1, 2012

yes.
Its exactly the same as the "log2" function Ive used for several years for sizing arrays.

copied and pasted from my "testbench_tools" package:

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
function log2( i : natural) return integer is
    variable temp    : integer := i;
    variable ret_val : integer := 1; --log2 of 0 should equal 1 because you still need 1 bit to represent 0
  begin                 
    while temp > 1 loop
      ret_val := ret_val + 1;
      temp    := temp / 2;     
    end loop;
    
    return ret_val;
  end function;

shaiko · Mar 1, 2012

TrickyDicky ,

Is your "testbench_tools" package openly available ?
If so, please link me to it.

Thanks again,
SK

K-J · Mar 2, 2012

shaiko said:

PHP:

function log2_unsigned ( x : natural ) return natural is
        variable temp : natural := x ;
        variable n : natural := 1 ;
    begin
        while temp > 1 loop
            temp := temp / 2 ;
            n := n + 1 ;
        end loop ;
    end function log2_unsigned ;

like that ?

Yes...you have the exact same error as pointed out in the reply to TrickyDicky

Kevin Jennings

---------- Post added at 19:11 ---------- Previous post was at 18:59 ----------

TrickyDicky said:

yes.
Its exactly the same as the "log2" function Ive used for several years for sizing arrays.

copied and pasted from my "testbench_tools" package:

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
function log2( i : natural) return integer is
    variable temp    : integer := i;
    variable ret_val : integer := 1; --log2 of 0 should equal 1 because you still need 1 bit to represent 0
  begin                 
    while temp > 1 loop
      ret_val := ret_val + 1;
      temp    := temp / 2;     
    end loop;
    
    return ret_val;
  end function;

And yet it isn't quite right...but you've worked around the shortcoming all these years. Below I've posted the code that validates the various log2 functions being discussed:
- log2 from Tuukka Toivonen posted in VHDL FAQ forum **broken link removed** helped by the code I posted for ceil_log2 which returns the ceiling function of the log2 function.
- log2_unsigned from shaiko based on direction from you
- td_log2 from your posted log2 function

Note: Not posting this as a slam against you or shaiko, just as open feedback on your implementation for the two of you (and others I suppose) to use (or not use) as you see fit. Thanks to both of you for posting code.

This also demonstrates how to go about testing new code that at first glance might appear to be correct.

Kevin Jennings

Code:

[syntax=vhdl]library ieee;
use ieee.std_logic_1164.all;
use ieee.math_real.all;
entity tb_log2 is
end tb_log2;
architecture rtl of tb_log2 is
    ----------------------------------------------------------------------------------------
    -- A synthesizable function that returns the integer part of the base 2 logarithm for a 
    -- positive number (posted by Tuukka Toivonen) to VHDL FAQ forum
    -- http://www.vhdl.org/comp.lang.vhdl/FAQ1.html
    ----------------------------------------------------------------------------------------
    function log2 (x : natural) return natural is 
    begin
        if x <= 1 then
            return 0;
        else
            return log2 (x / 2) + 1;
        end if;
    end function log2;

    -----------------------------------------------------------------------------------
    -- Combine the ceil and log2 functions.  ceil_log2(x) then gives the minimum number
    -- of bits required to represent 'x'.  ceil_log2(4) = 2, ceil_log2(5) = 3, etc.
    -----------------------------------------------------------------------------------
    function ceil_log2 (Arg : positive) return natural is
        variable RetVal:    natural;
    begin
        RetVal := log2(Arg);
        if (Arg > (2**RetVal)) then
            return(RetVal + 1); -- RetVal is too small, so bump it up by 1 and return
        else
            return(RetVal); -- Just right
        end if;
    end function ceil_log2;

    function log2_unsigned ( x : natural ) return natural is 
        variable temp : natural := x ; 
        variable n : natural := 1 ; 
    begin 
        while temp > 1 loop 
            temp := temp / 2 ; 
            n := n + 1 ; 
        end loop ; 
        return(n);  -- KJ added
    end function log2_unsigned ;

    function td_log2( i : natural) return integer is
        variable temp    : integer := i;
        variable ret_val : integer := 1; --log2 of 0 should equal 1 because you still need 1 bit to represent 0
      begin                 
        while temp > 1 loop
          ret_val := ret_val + 1;
          temp    := temp / 2;     
        end loop;
    
        return ret_val;
      end function; 
begin
    process
    begin
        report  LF &
                "------------------------------------" & LF &
                "Testing TrickyDicky's implementation" & LF &
                "------------------------------------";
        for i in 1 to 31 loop
            assert real(ceil_log2(i)) = ceil(log2(real(i)))
                report  "OOPS!  Log2 mismatch for i =" & integer'image(i) & LF &
                        "ceil_log2(i)=" & integer'image(ceil_log2(i)) & LF &
                        "ieee.math_real.log2(i)=" & real'image(ceil(log2(real(i))))
                severity ERROR;
            assert ceil_log2(i) = td_log2(i)
                report  "OOPS!  Log2 mismatch for i =" & integer'image(i) & LF &
                        "ceil_log2(i)=" & integer'image(ceil_log2(i)) & LF &
                        "td_log2(i)=" & integer'image(td_log2(i))
                severity ERROR;
        end loop;
        report  LF &
                "-------------------------------" & LF &
                "Testing shaiko's implementation" & LF &
                "-------------------------------";
        for i in 1 to 31 loop
            assert ceil_log2(i) = log2_unsigned(i)
                report  "OOPS!  Log2 mismatch for i =" & integer'image(i) & LF &
                        "ceil_log2(i)=" & integer'image(ceil_log2(i)) & LF &
                        "log2_unsigned(i)=" & integer'image(log2_unsigned(i))
                severity ERROR;
        end loop;
        report "Simulation completed";
        wait;
    end process;
end rtl;[/syntax]

Simulation output
# vsim tb_log2
# Loading std.standard
# Loading ieee.std_logic_1164(body)
# Loading ieee.math_real(body)
# Loading work.tb_log2(rtl)
# ** Note:
# ------------------------------------
# Testing TrickyDicky's implementation
# ------------------------------------
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =1
# ceil_log2(i)=0
# td_log2(i)=1
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =2
# ceil_log2(i)=1
# td_log2(i)=2
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =4
# ceil_log2(i)=2
# td_log2(i)=3
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =8
# ceil_log2(i)=3
# td_log2(i)=4
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =16
# ceil_log2(i)=4
# td_log2(i)=5
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Note:
# -------------------------------
# Testing shaiko's implementation
# -------------------------------
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =1
# ceil_log2(i)=0
# log2_unsigned(i)=1
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =2
# ceil_log2(i)=1
# log2_unsigned(i)=2
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =4
# ceil_log2(i)=2
# log2_unsigned(i)=3
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =8
# ceil_log2(i)=3
# log2_unsigned(i)=4
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =16
# ceil_log2(i)=4
# log2_unsigned(i)=5
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Note: Simulation completed
# Time: 0 ns Iteration: 0 Instance: /tb_log2

shaiko · Mar 2, 2012

Thanks for the post K-J
Can you give a specific example when TrickyDick's suggestion (to Initialise n to 1) won't work ?
I couldn't find an exception

std_match · Mar 2, 2012

K-J, look at the first posting in the thread. The goal is not a true log2 function, but a way to find the number of bits needed to represent a number.
TrickyDicky's function does this correctly.

K-J · Mar 2, 2012

shaiko said:
Thanks for the post K-J
Can you give a specific example when TrickyDick's suggestion (to Initialise n to 1) won't work ?
I couldn't find an exception

Read the simulation output that I posted, sample posted below.

# ------------------------------------
# Testing TrickyDicky's implementation
# ------------------------------------
# Time: 0 ns Iteration: 0 Instance: /tb_log2
# ** Error: OOPS! Log2 mismatch for i =1
# ceil_log2(i)=0
# td_log2(i)=1
...

Kevin Jennings

---------- Post added at 07:47 ---------- Previous post was at 07:36 ----------

std_match said:
K-J, look at the first posting in the thread. The goal is not a true log2 function, but a way to find the number of bits needed to represent a number.
TrickyDicky's function does this correctly.

I understand the goal completely. TrickyDicky, when posting a sketch of his code even suggested calling it something else rather than log2 when he said "and maybe rename it n_bits, because its not a real log2 anymore", but then we he posted his real code he did call it log2.

What is needed to solve the original posting is to implement the ceiling function on the log base 2 of a number. What I posted accomplishes that goal, the other posting doesn't quite do that under all conditions (as indicated by the places where the assertions fail). Remember the synthesizable log2 function is not restricted to use for computing the number of bits in a constant sized vector (although that is the primary usage); it can be used in 'live' code to compute the log base2 of an input signal. What TrickyDicky posted implied that he computed the log2 of some number, although in words he implied that it was the ceiling of the log base 2...my point was that it doesn't do either one and that as shown by the actual simulation output. Not a slam, take it for what it's worth.

Kevin Jennings

FvM · Mar 2, 2012

There can be no doubt, that log2(1) as well as ceil(log2(1)) are 0. But it's not the correct bit count of an array to represent the numbers 0..N, which must be ceil(log2(N+1)). Kevin's code is already accounting for the +1.

K-J · Mar 3, 2012

FvM said:
There can be no doubt, that log2(1) as well as ceil(log2(1)) are 0. But it's not the correct bit count of an array to represent the numbers 0..N, which must be ceil(log2(N+1)). Kevin's code is already accounting for the +1.

Not really, my code computes ceil(log2(N)), TrickyDicky's code compute ceil(log2(N+1). But that's all beside the point. What somebody using the function wants (and was the question posed by shaiko to start the thread) is something to compute the proper vector range needed to represent a range of numbers. My function does that, the other does not. But don't take my word for it, simply try to represent a set of vectors. Presumably the representation is one of the following:

1. my_vector(xx_log2(N) - 1 downto 0)
2. my_vector(xx_log2(N) downto 0)
3. my_vector(xx_log2(N) - 2 downto 0)

If 'xx' is 'ceil' (i.e. my function), then #1 works for any n. If 'xx' is 'td' (Tricky's function), then sometimes #1 works, other times #3 works. Which one is the correct to use depends on the value of n...which kind of makes it not so useful unless you only happen to use only those certain values of 'n'. The table below shows values for a length, the range that corresponds to that length, and the output of the two log2 functions being discussed for a range of n from 2 to 16. Take a look at lengths 4 and 5 and evaluate using Tricky's function. For length 4, you would need to use form #3 to declare your vector; for length 5, you would need to use form #1. Using my function form #1 would always be used...for any value of n

I guess I've beaten this one enough, hopefully the point has gotten across.

Kevin Jennings

Code:

x   Range  Ceil(log2(x))   ceil_log2(x)   td_log2(x)
2   0..1   1.000000e+000   1              2  -- OOPS
3   0..2   2.000000e+000   2              2
4   0..3   2.000000e+000   2              3  -- OOPS
5   0..4   3.000000e+000   3              3
6   0..5   3.000000e+000   3              3
7   0..6   3.000000e+000   3              3
8   0..7   3.000000e+000   3              4  -- OOPS
9   0..8   4.000000e+000   4              4
10  0..9   4.000000e+000   4              4
11  0..10  4.000000e+000   4              4
12  0..11  4.000000e+000   4              4
13  0..12  4.000000e+000   4              4
14  0..13  4.000000e+000   4              4
15  0..14  4.000000e+000   4              4
16  0..15  4.000000e+000   4              5  -- OOPS

Welcome to EDAboard.com

[Moved] VHDL log base 2 function

Advanced Member level 5

Advanced Member level 2

Advanced Member level 5

Advanced Member level 2

Advanced Member level 5

Super Moderator

Advanced Member level 5

Advanced Member level 2

Super Moderator

Advanced Member level 5

Advanced Member level 7

Advanced Member level 5

Advanced Member level 7

Advanced Member level 5

Advanced Member level 2

Advanced Member level 5

Advanced Member level 4

Advanced Member level 2

Super Moderator

Advanced Member level 2

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor