clogb2

D

davew

Guest
Would someone please perform a sanity check on my logic regarding this
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.
 
On Tue, 25 Sep 2007 08:55:01 -0700,
davew <David.Wooff@gmail.com> wrote:

Surely, ceil(log2(8)) = 3?
and ceil(log2(9)) = 4?
Click to expand...
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.bromley@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.
 
On Tue, 25 Sep 2007 17:04:23 +0100, Jonathan Bromley
<jonathan.bromley@MYCOMPANY.com> wrote:

On Tue, 25 Sep 2007 08:55:01 -0700,
davew <David.Wooff@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.
Click to expand...
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
 
davew wrote:
Would someone please perform a sanity check on my logic regarding this
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.
Click to expand...
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
 
On Tue, 25 Sep 2007 17:36:31 +0100,
Evan Lavelle <nospam@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.
Click to expand...
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.
--
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.bromley@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.
 
Kevin Neilson wrote:
davew wrote:
Would someone please perform a sanity check on my logic regarding this
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.


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
Click to expand...
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
 
Thanks everyone.

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.
 
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.
Click to expand...
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.
 
<sharp@cadence.com> wrote in message
news:1190911742.556630.61000@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.
Click to expand...

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.
 
John_H wrote:
So does the Verilog-2005 built-in function return $clog2(8)==3 or ==4?
Click to expand...
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.
Click to expand...
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.
 
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.
Click to expand...
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.
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top