clogb2
davew
function because it seems to be widely referenced/recommended:
document:
http://www.sunburst-design.com/papers/CummingsHDLCON2001_Verilog2001.pdf
recommends the following function to calculate ceil(log2(x)).
function integer clogb2;input [31:0] value;
for (clogb2=0; value>0; clogb2=clogb2+1)
value = value>>1;
endfunction
I tried to use this in my design (using Altera Quartus as it happens)
but I get an incorrect result for a value such as 8 i.e. where log2(x)
has a purely integer result.
As I see it, this function would return the same result for x=8 or x=9
i.e. 4.
Surely, ceil(log2(8)) = 3?
and ceil(log2(9)) = 4?
I used this modified version which works for me:
function integer clogb2;
input [31:0] value;
value=value-1;
<--------------------------------------------------------------added
for (clogb2=0; value>0; clogb2=clogb2+1)
value = value>>1;
endfunction
It wouldn't make any sense to call this function with a value of 0,
since this is not mathematically a good idea. If called with a value
of 1, then I think the result would be correct also, i.e. 0.
Jonathan Bromley
davew <David...@gmail.com> wrote:
>Surely, ceil(log2(8)) = 3?
>and ceil(log2(9)) = 4?
Nope. The binary representation of 8 is 1000,
which (unless my eyes deceive me) requires 4 bits
to avoid overflow.
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
http://www.MYCOMPANY.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Evan Lavelle
<jonathan...@MYCOMPANY.com> wrote:
>On Tue, 25 Sep 2007 08:55:01 -0700,
>davew <David...@gmail.com> wrote:
>
>>Surely, ceil(log2(8)) = 3?
>>and ceil(log2(9)) = 4?
>
>Nope. The binary representation of 8 is 1000,
>which (unless my eyes deceive me) requires 4 bits
>to avoid overflow.
True, but log2(8) = 3, and log2(9) = 3.17, so you might reasonably
expect clogb2(8) to return 3, and clogb2(9) to return 4.
The 2005 LRM shows a clogb2 implementation (p157) which includes the
"value = value - 1" line. My recollection is that the 95 LRM has an
incorrect clogb2 somewhere, but I can't check it because my pdf isn't
searchable (anyone know how to fix that? It's got a non-standard
encoding).
Evan
Kevin Neilson
I found that same function and use it in my fifo module and but I added
the following comments above the function:
/****************************************************************
* Log2 Function (taken from lecture of Juinn-Dar Huang)
* Note: This function actually yields ceil(log2(x+1))
*****************************************************************/
This is actually the logic I want in my fifo module, but it doesn't
technically work as was advertised when I found it.
-Kevin
Jonathan Bromley
Evan Lavelle <nos...@nospam.com> wrote:
>>Nope. The binary representation of 8 is 1000,
>>which (unless my eyes deceive me) requires 4 bits
>>to avoid overflow.
>
>True, but log2(8) = 3, and log2(9) = 3.17, so you might reasonably
>expect clogb2(8) to return 3, and clogb2(9) to return 4.
Which is why I have always avoided the faux-mathematical
certainty of clogb2, and instead written a function named
"bits_to_fit", since that's what I wanted it for anyhow.
Kevin Neilson
I was getting confused reading the other thread, so just to verify, I
ran the above function in Modelsim and verified that according to the
Verilog function, clogb2(8)=4, whereas in reality (and verified by
Matlab) ceil(log2(8))=3. Like the other thread pointed out, what you
usually want in Verilog is to know the number of bits required to
express a value, so ceil(log2(x+1)) is actually the behavior you want,
but it's not mathematically accurate to call it a clog2 function. -Kevin
davew
Well until now at least, I have used clogb2 to determine width
required based on some arbitrary quantity of something. For example,
say number_of_channels = 8.
How many bits required? Well since the variable "channel" would range
from 0..7, the answer I want is 3.
If I wanted to store the number "8" then yes, 4 bits; I hadn't really
thought of it like this.
sh...@cadence.com
davew wrote:
>
> Well until now at least, I have used clogb2 to determine width
> required based on some arbitrary quantity of something. For example,
> say number_of_channels = 8.
The most common use I have seen is determining the number of address
bits required, given the number of elements in a memory. That matches
what you are looking for, and is ceil(log2(x)).
The version of clogb2 used as an example in the Verilog-2001 LRM was
wrong in the printed version also. In that case, I am pretty certain
it was just a programming bug. So I am suspicious of claims that an
error in another version was intentional. People just seem to have
trouble writing a correct implementation of this function :-)
In Verilog-2005, we added a built-in system function $clog2 that can
be used in constant expressions, so that users wouldn't have to write
their own. I don't know that this has been widely implemented though,
with all the attention going to SystemVerilog features.
John_H
news:1190911742....@w3g2000hsg.googlegroups.com...
>
> The most common use I have seen is determining the number of address
> bits required, given the number of elements in a memory. That matches
> what you are looking for, and is ceil(log2(x)).
>
> The version of clogb2 used as an example in the Verilog-2001 LRM was
> wrong in the printed version also. In that case, I am pretty certain
> it was just a programming bug. So I am suspicious of claims that an
> error in another version was intentional. People just seem to have
> trouble writing a correct implementation of this function :-)
>
> In Verilog-2005, we added a built-in system function $clog2 that can
> be used in constant expressions, so that users wouldn't have to write
> their own. I don't know that this has been widely implemented though,
> with all the attention going to SystemVerilog features.
So does the Verilog-2005 built-in function return $clog2(8)==3 or ==4?
8 memory elements require 3 address bits but the number 8 requires 4 bits.
sh...@cadence.com
John_H wrote:
>
> So does the Verilog-2005 built-in function return $clog2(8)==3 or ==4?
The LRM says that it returns the ceiling of the log base 2, so that
would be 3.
> 8 memory elements require 3 address bits but the number 8 requires 4 bits.
The LRM goes on to say that it can be used to compute the minimum
address width necessary to address a memory of a given size or the
minimum vector width necessary to represent a given number of states.
If you want to represent the number 8, that would be a vector that can
represent 9 states (0:8), so it would take $clog2(8+1) bits.
Of course, if you want your address or state vector to be indexed from
zero, you get to subtract 1 from that for the upper bound. But
everyone is used to doing that. You just have to remember to do the
reverse and add one to include 0 when going the other way and
determining the number of states to represent up to a given number.
sh...@cadence.com
John_H wrote:
>
> So does the Verilog-2005 built-in function return $clog2(8)==3 or ==4?
>
> 8 memory elements require 3 address bits but the number 8 requires 4 bits.
Perhaps you are subtly pointing out that the user could still get an
off-by-one error even with the built-in version, because they could
assume that it computes one of these when it actually computes the
other.
I hope that the additional text that describes the most common uses
for it will help with that, even if the reader isn't sure what the
mathematical definition means.