How to define a counter whose width is big enough to hold in

[Weng Tianxiang]

On Monday, March 7, 2016 at 1:43:59 PM UTC-8, Weng Tianxiang wrote:

On Friday, March 4, 2016 at 10:48:11 PM UTC-8, rickman wrote:
On 3/5/2016 12:23 AM, rickman wrote:
On 3/4/2016 8:01 PM, Weng Tianxiang wrote:
On Friday, March 4, 2016 at 2:27:55 PM UTC-8, rickman wrote:
On 3/4/2016 5:03 PM, Mark Curry wrote:
In article <nbcq1j$i1q$1@dont-email.me>, rickman <gnuarm@gmail.com
wrote:
On 3/4/2016 1:20 PM, Weng Tianxiang wrote:
On Friday, March 4, 2016 at 5:34:42 AM UTC-8, Gabor wrote:
Weng Tianxiang wrote:
Hi,

I have a constant N = 27, how to define a counter whose width is
big enough to hold integer 27?

Or how to get a constant = log N? Where "log" is a logarithm
with base 2.

Thank you.

Weng

The function you want is the ceiling of log base 2. In Verilog
this is $clog2(). If you don't have a similar function it's quite
easy to make, since it's generally accomplished by shifting the
input value right until it becomes zero and counting the shifts
required to get there.

--
Gabor

Hi Gabor,

I want to use the (log N) to be the width of a counter:

signal Count : unsigned((log N)-1 downto 0); -- it can hold a
known largest number N

I don't think you need a ceiling function. I think you need a floor
function and add 1. log2(8) = 3.0, log2(9) = 3.17, both need 4
bits to
represent them in binary. A ceiling function will return 3 for 8
and 4
for 9. So it would be

ceiling(log2(8+1)) = 4;

What's the trouble?

This can work if you add the 1 first, but the number you want is 3. So
you have to subtract 1 from this result. Which is simpler?

Personally I prefer the simpler approach of flog2(N) rather than
clog2(N+1)-1 to get where this needs to go. flog2 is a very simple
function to write. If you use floating point routines for log2 and
ceiling you need to then convert to integer. Are there integer
functions for these routines or do you need to write them? I guess that
wouldn't make sense since log2 either returns a floating point number or
does some form of truncation or rounding.

--

Rick

Hi Gabor, KJ, Rich and Mark,

After your posts, I realized that a user-defined function's returned
integer value can be used as boundary limit!!! Before the post I
didn't know it.

So I decided to accept Gabor's method to write an integer function
log2(integer N) in my design so that it can be repeatedly used later
for my life.

Thank you.

Weng

Here is the code:

-- = floor of log2(); log2(27) = 5.

function log2(integer: N) return integer is
variable K : integer;
variable M : integer; -- = M mod 2
begin
K := 0;
M := N;
loop1: while M /= 0 loop
M := M mod 2; -- it cannot use M := M srl 2, because N is an
integer
K := K+1;
end loop;

return K;
end log2;

-- to be debugged

I can't recall the last time I wrote even a simple program that was 100%
correct the first time. I think when you debug your program it will
need to be M := M / 2;

You might want to make your comment, "it cannot use M := M srl 1,
because N is an integer"

Oh yeah, you also need to change "while M /= 0" to "while M > 1".
Otherwise you will get a return value of 1 for 1, 2 for 2, 3 for 4, 4
for 8, etc, which are all 1 more than the correct value and not optimal
for your use.

--

Rick

Hi Rick,
I just want to 1 for 1, 2 for 2, 3 for 4, 4 for 8, the bit count that is big enough to hold N.

signal Counter : unsigned(log2(N)-1 downto 0);

I don't want to skip "-1", because all unsigned() expressions in my design uses format name(xxx-1 downto 0);

for all integer M mod 2 == M / 2, but latter is better than former.

So actually my design has no error at all!!!

Weng

Hi,
Sorry, everyone who participate in this discussion.

After finishing my code, I wrote log2() function and finally found that I didn't use it at all and actually use the following format before having read Rick suggestions.

signal Count : integer range 0 to N;

instead of

signal Count : unsigned(log2(N)-1 downto 0);

KJ: he says that "M := M mod 2;" is not equal to: "M := M/2;" I don't know why? Can you list a digital example to show your point?

Thank you.

Weng

 

[Rob Gaddi]

Weng Tianxiang wrote:

KJ: he says that "M := M mod 2;" is not equal to: "M := M/2;" I don't know why? Can you list a digital example to show your point?

No example required; they're completely different operators. mod is the
remainder. / is the quotient.

That's like asking for an example to prove that / and + are different.

--
Rob Gaddi, Highland Technology -- www.highlandtechnology.com
Email address domain is currently out of order. See above to fix.

 

[KJ]

On Monday, March 7, 2016 at 4:43:59 PM UTC-5, Weng Tianxiang wrote:

I just want to 1 for 1, 2 for 2, 3 for 4, 4 for 8, the bit count that is big enough to hold N.

signal Counter : unsigned(log2(N)-1 downto 0);

I don't want to skip "-1", because all unsigned() expressions in my design uses format name(xxx-1 downto 0);

for all integer M mod 2 == M / 2, but latter is better than former.

So actually my design has no error at all!!!

There are three errors in your design, all of which have been pointed out:
1. ceil(log2()) is needed, not log2().
2. To include N, you need to use ceil(log2(N+1))-1 down to 0, not ceil(log2(N))-1 downto 0. Example: N=8 will require four bits to represent 8, not 3 bits
3. M/2 is not equal to M mod 2 for integers. Example: int(5/2) = int(2.5) = 2; 5 mod 2 = 1. The mod operator gives you the remainder of the division, not the quotient

Kevin Jennings

 

[Jon Elson]

Weng Tianxiang wrote:

Hi,

I have a constant N = 27, how to define a counter whose width is big
enough to hold integer 27?

Or how to get a constant = log N? Where "log" is a logarithm with base 2.

Thank you.

Weng

And, of course, in VHDL, you can say :
signal blat : integer range 0 to 27;

And VHDL figures out that you need 5 bits to represent that. You can use
this in the port definitions between modules, too. Such as :

entity blah is
port (
state : out integer range 0 to 27
);

One thing you have to keep in mind is what the logic might do if some value
comes in from outside which exceeds the declared range but fits in the
number of bits required to represent that. I'm assuming that synthesis
tools don't protect against that.

Jon

 

[rickman]

On 3/7/2016 4:43 PM, Weng Tianxiang wrote:

On Friday, March 4, 2016 at 10:48:11 PM UTC-8, rickman wrote:
On 3/5/2016 12:23 AM, rickman wrote:
On 3/4/2016 8:01 PM, Weng Tianxiang wrote:
On Friday, March 4, 2016 at 2:27:55 PM UTC-8, rickman wrote:
On 3/4/2016 5:03 PM, Mark Curry wrote:
In article <nbcq1j$i1q$1@dont-email.me>, rickman <gnuarm@gmail.com
wrote:
On 3/4/2016 1:20 PM, Weng Tianxiang wrote:
On Friday, March 4, 2016 at 5:34:42 AM UTC-8, Gabor wrote:
Weng Tianxiang wrote:
Hi,

I have a constant N = 27, how to define a counter whose width is
big enough to hold integer 27?

Or how to get a constant = log N? Where "log" is a logarithm
with base 2.

Thank you.

Weng

The function you want is the ceiling of log base 2. In Verilog
this is $clog2(). If you don't have a similar function it's quite
easy to make, since it's generally accomplished by shifting the
input value right until it becomes zero and counting the shifts
required to get there.

--
Gabor

Hi Gabor,

I want to use the (log N) to be the width of a counter:

signal Count : unsigned((log N)-1 downto 0); -- it can hold a
known largest number N

I don't think you need a ceiling function. I think you need a floor
function and add 1. log2(8) = 3.0, log2(9) = 3.17, both need 4
bits to
represent them in binary. A ceiling function will return 3 for 8
and 4
for 9. So it would be

ceiling(log2(8+1)) = 4;

What's the trouble?

This can work if you add the 1 first, but the number you want is 3. So
you have to subtract 1 from this result. Which is simpler?

Personally I prefer the simpler approach of flog2(N) rather than
clog2(N+1)-1 to get where this needs to go. flog2 is a very simple
function to write. If you use floating point routines for log2 and
ceiling you need to then convert to integer. Are there integer
functions for these routines or do you need to write them? I guess that
wouldn't make sense since log2 either returns a floating point number or
does some form of truncation or rounding.

--

Rick

Hi Gabor, KJ, Rich and Mark,

After your posts, I realized that a user-defined function's returned
integer value can be used as boundary limit!!! Before the post I
didn't know it.

So I decided to accept Gabor's method to write an integer function
log2(integer N) in my design so that it can be repeatedly used later
for my life.

Thank you.

Weng

Here is the code:

-- = floor of log2(); log2(27) = 5.

function log2(integer: N) return integer is
variable K : integer;
variable M : integer; -- = M mod 2
begin
K := 0;
M := N;
loop1: while M /= 0 loop
M := M mod 2; -- it cannot use M := M srl 2, because N is an
integer
K := K+1;
end loop;

return K;
end log2;

-- to be debugged

I can't recall the last time I wrote even a simple program that was 100%
correct the first time. I think when you debug your program it will
need to be M := M / 2;

You might want to make your comment, "it cannot use M := M srl 1,
because N is an integer"

Oh yeah, you also need to change "while M /= 0" to "while M > 1".
Otherwise you will get a return value of 1 for 1, 2 for 2, 3 for 4, 4
for 8, etc, which are all 1 more than the correct value and not optimal
for your use.

--

Rick

Hi Rick,
I just want to 1 for 1, 2 for 2, 3 for 4, 4 for 8, the bit count that is big enough to hold N.

signal Counter : unsigned(log2(N)-1 downto 0);

I don't want to skip "-1", because all unsigned() expressions in my design uses format name(xxx-1 downto 0);

for all integer M mod 2 == M / 2, but latter is better than former.

So actually my design has no error at all!!!

What???!!! You are thinking of operations on... no, that's not
right.... I don't know what you are thinking of.

You can define your function any way you want. You can redefine the mod
operator to be the same as the divide operator. But if you do that I
can't help you.

Try coding this up and see if it works.

--

Rick

 

[rickman]

On 3/7/2016 5:37 PM, Jon Elson wrote:

Weng Tianxiang wrote:

Hi,

I have a constant N = 27, how to define a counter whose width is big
enough to hold integer 27?

Or how to get a constant = log N? Where "log" is a logarithm with base 2.

Thank you.

Weng
And, of course, in VHDL, you can say :
signal blat : integer range 0 to 27;

And VHDL figures out that you need 5 bits to represent that. You can use
this in the port definitions between modules, too. Such as :

entity blah is
port (
state : out integer range 0 to 27
);

One thing you have to keep in mind is what the logic might do if some value
comes in from outside which exceeds the declared range but fits in the
number of bits required to represent that. I'm assuming that synthesis
tools don't protect against that.

No, but if you use the integer type simulation will catch it.
Interesting point though. Something to be careful about in the system
design. I seem to recall a rocket falling from the sky from a system
design issue because of module reuse without catching an incompatible
requirement.

--

Rick

 

[rickman]

On 3/7/2016 10:16 PM, KJ wrote:

On Monday, March 7, 2016 at 4:43:59 PM UTC-5, Weng Tianxiang wrote:
I just want to 1 for 1, 2 for 2, 3 for 4, 4 for 8, the bit count that is big enough to hold N.

signal Counter : unsigned(log2(N)-1 downto 0);

I don't want to skip "-1", because all unsigned() expressions in my design uses format name(xxx-1 downto 0);

for all integer M mod 2 == M / 2, but latter is better than former.

So actually my design has no error at all!!!


There are three errors in your design, all of which have been pointed out:
1. ceil(log2()) is needed, not log2().
2. To include N, you need to use ceil(log2(N+1))-1 down to 0, not ceil(log2(N))-1 downto 0. Example: N=8 will require four bits to represent 8, not 3 bits
3. M/2 is not equal to M mod 2 for integers. Example: int(5/2) = int(2.5) = 2; 5 mod 2 = 1. The mod operator gives you the remainder of the division, not the quotient

Why does everyone keep saying to use the ceiling function of log2(),
then they add 1 to N before computing it? Isn't it simpler to just
bloody take the floor of log2() and skip adding the 1?

Then Weng has a compulsion to calculate a result that he then has to
subtract 1 from before using just because that is what he is used to
seeing in array declarations.

Maybe I've had too much caffeine, but all this seems a bit absurd.

BTW, your first two points are based on using real functions, no? So it
would need to be to_integer(ceil(log2(real(N+1))))? This really pushes
it over the top for me.

Weng is not using real routines, but is writing his own log2() function
for an integer input and integer output. But in reality it is
ceil_log2_of_N+1() as it returns a value 1 too large to be log2.

--

Rick

 

[KJ]

On Monday, March 7, 2016 at 11:18:55 PM UTC-5, rickman wrote:

Isn't it simpler to just
bloody take the floor of log2() and skip adding the 1?

Different yes, not simpler or harder. Either way there is an addition and a log function to perform.

BTW, your first two points are based on using real functions, no?
No they are not.

So it
would need to be to_integer(ceil(log2(real(N+1))))? This really pushes
it over the top for me.

What I use is the recursive version of the log2 function from the VHDL FAQ that I posted earlier and I have a separate ceil_log2 function that returns ceil(log2(N)). Both the ceil_log2 and the log2 functions have natural arguments and return natural.

I use the log2 function from VHDL FAQ rather than ieee.math_real.log2 because I want something that is synthesizable and works with signals not just for computing constants. y <= log2(x) can be used to calculate the most significant bit that is a 1 is one example where log2 can be used with signal I/O.

Kevin

 

[rickman]

On 3/8/2016 7:11 AM, KJ wrote:

On Monday, March 7, 2016 at 11:18:55 PM UTC-5, rickman wrote:
Isn't it simpler to just bloody take the floor of log2() and skip
adding the 1?

Different yes, not simpler or harder. Either way there is an
addition and a log function to perform.

I don't follow what you are saying. Using a floor_log2() function means
you skip adding the 1 to the input parameter and also skip subtracting
the 1 to use it in the range specification. The point is the log2()
function is not really the correct function for calculating the range.
So why adjust it three ways when you can adjust it just once?

1st adjustment, use ceiling function. Second adjustment, add 1 to the
input value. Third adjustment, subtract 1 from the result to get the
range high value.

---or---

Just use the floored log2() function which is actually the same as the
integer version of log2(). So maybe that's no adjustment at all?

BTW, your first two points are based on using real functions, no?
No they are not.

So it would need to be to_integer(ceil(log2(real(N+1))))? This
really pushes it over the top for me.

What I use is the recursive version of the log2 function from the
VHDL FAQ that I posted earlier and I have a separate ceil_log2
function that returns ceil(log2(N)). Both the ceil_log2 and the log2
functions have natural arguments and return natural.

I'd like to see your ceil_log2 function. Is it just log2() with a 1
subtracted from the input and a 1 added to result?

I use the log2 function from VHDL FAQ rather than ieee.math_real.log2
because I want something that is synthesizable and works with signals
not just for computing constants. y <= log2(x) can be used to
calculate the most significant bit that is a 1 is one example where
log2 can be used with signal I/O.

Yes, an integer log2 function has been discussed here, it just wasn't
written 100% correctly.

--

Rick

 

[Weng Tianxiang]

On Tuesday, March 8, 2016 at 9:47:08 AM UTC-8, rickman wrote:

On 3/8/2016 7:11 AM, KJ wrote:
On Monday, March 7, 2016 at 11:18:55 PM UTC-5, rickman wrote:
Isn't it simpler to just bloody take the floor of log2() and skip
adding the 1?

Different yes, not simpler or harder. Either way there is an
addition and a log function to perform.

I don't follow what you are saying. Using a floor_log2() function means
you skip adding the 1 to the input parameter and also skip subtracting
the 1 to use it in the range specification. The point is the log2()
function is not really the correct function for calculating the range.
So why adjust it three ways when you can adjust it just once?

1st adjustment, use ceiling function. Second adjustment, add 1 to the
input value. Third adjustment, subtract 1 from the result to get the
range high value.

---or---

Just use the floored log2() function which is actually the same as the
integer version of log2(). So maybe that's no adjustment at all?


BTW, your first two points are based on using real functions, no?
No they are not.

So it would need to be to_integer(ceil(log2(real(N+1))))? This
really pushes it over the top for me.

What I use is the recursive version of the log2 function from the
VHDL FAQ that I posted earlier and I have a separate ceil_log2
function that returns ceil(log2(N)). Both the ceil_log2 and the log2
functions have natural arguments and return natural.

I'd like to see your ceil_log2 function. Is it just log2() with a 1
subtracted from the input and a 1 added to result?


I use the log2 function from VHDL FAQ rather than ieee.math_real.log2
because I want something that is synthesizable and works with signals
not just for computing constants. y <= log2(x) can be used to
calculate the most significant bit that is a 1 is one example where
log2 can be used with signal I/O.

Yes, an integer log2 function has been discussed here, it just wasn't
written 100% correctly.

--

Rick

Hi Rick and KJ,

Yes, an integer log2 function has been discussed here, it just wasn't
written 100% correctly.

Your are right. The only error "M := M mod 2;" should be "M := M / 2;"

KJ saying that it has 3 errors doesn't make sense.

Weng

 

[Weng Tianxiang]

On Wednesday, March 9, 2016 at 7:26:39 AM UTC-8, Weng Tianxiang wrote:

On Tuesday, March 8, 2016 at 9:47:08 AM UTC-8, rickman wrote:
On 3/8/2016 7:11 AM, KJ wrote:
On Monday, March 7, 2016 at 11:18:55 PM UTC-5, rickman wrote:
Isn't it simpler to just bloody take the floor of log2() and skip
adding the 1?

Different yes, not simpler or harder. Either way there is an
addition and a log function to perform.

I don't follow what you are saying. Using a floor_log2() function means
you skip adding the 1 to the input parameter and also skip subtracting
the 1 to use it in the range specification. The point is the log2()
function is not really the correct function for calculating the range.
So why adjust it three ways when you can adjust it just once?

1st adjustment, use ceiling function. Second adjustment, add 1 to the
input value. Third adjustment, subtract 1 from the result to get the
range high value.

---or---

Just use the floored log2() function which is actually the same as the
integer version of log2(). So maybe that's no adjustment at all?


BTW, your first two points are based on using real functions, no?
No they are not.

So it would need to be to_integer(ceil(log2(real(N+1))))? This
really pushes it over the top for me.

What I use is the recursive version of the log2 function from the
VHDL FAQ that I posted earlier and I have a separate ceil_log2
function that returns ceil(log2(N)). Both the ceil_log2 and the log2
functions have natural arguments and return natural.

I'd like to see your ceil_log2 function. Is it just log2() with a 1
subtracted from the input and a 1 added to result?


I use the log2 function from VHDL FAQ rather than ieee.math_real.log2
because I want something that is synthesizable and works with signals
not just for computing constants. y <= log2(x) can be used to
calculate the most significant bit that is a 1 is one example where
log2 can be used with signal I/O.

Yes, an integer log2 function has been discussed here, it just wasn't
written 100% correctly.

--

Rick

Hi Rick and KJ,

Yes, an integer log2 function has been discussed here, it just wasn't
written 100% correctly.

Your are right. The only error "M := M mod 2;" should be "M := M / 2;"

KJ saying that it has 3 errors doesn't make sense.

Weng

Actually if i used integer_bit_width(N) instead of log2(N), there are no confusions here, no ceiling or floor.

What I want is the bit width of an integer.

My only error "M := M mod 2;" should be "M := M / 2;"

for integer 8, return is 4; if 7, return is 3. Very simple.

Of cause I learn 2 things from this post:
1. A constant uplimit can be generated by a function with constant input parameters.

2. A void use operator mod that is more complex than what you think.

Thank you everyone.

Weng

The following first post by KJ causes Rick's doubt:

What exactly is the issue? ieee.MATH_REAL defines a log2 function that can be used to define the upper bound. Actually what you want is
ceil(log2(N))

Kevin

I jusu ignored KJ' above info.

 

[rickman]

On 3/9/2016 12:11 PM, Weng Tianxiang wrote:

On Wednesday, March 9, 2016 at 7:26:39 AM UTC-8, Weng Tianxiang wrote:
On Tuesday, March 8, 2016 at 9:47:08 AM UTC-8, rickman wrote:
On 3/8/2016 7:11 AM, KJ wrote:
On Monday, March 7, 2016 at 11:18:55 PM UTC-5, rickman wrote:
Isn't it simpler to just bloody take the floor of log2() and skip
adding the 1?

Different yes, not simpler or harder. Either way there is an
addition and a log function to perform.

I don't follow what you are saying. Using a floor_log2() function means
you skip adding the 1 to the input parameter and also skip subtracting
the 1 to use it in the range specification. The point is the log2()
function is not really the correct function for calculating the range.
So why adjust it three ways when you can adjust it just once?

1st adjustment, use ceiling function. Second adjustment, add 1 to the
input value. Third adjustment, subtract 1 from the result to get the
range high value.

---or---

Just use the floored log2() function which is actually the same as the
integer version of log2(). So maybe that's no adjustment at all?


BTW, your first two points are based on using real functions, no?
No they are not.

So it would need to be to_integer(ceil(log2(real(N+1))))? This
really pushes it over the top for me.

What I use is the recursive version of the log2 function from the
VHDL FAQ that I posted earlier and I have a separate ceil_log2
function that returns ceil(log2(N)). Both the ceil_log2 and the log2
functions have natural arguments and return natural.

I'd like to see your ceil_log2 function. Is it just log2() with a 1
subtracted from the input and a 1 added to result?


I use the log2 function from VHDL FAQ rather than ieee.math_real.log2
because I want something that is synthesizable and works with signals
not just for computing constants. y <= log2(x) can be used to
calculate the most significant bit that is a 1 is one example where
log2 can be used with signal I/O.

Yes, an integer log2 function has been discussed here, it just wasn't
written 100% correctly.

--

Rick

Hi Rick and KJ,

Yes, an integer log2 function has been discussed here, it just wasn't
written 100% correctly.

Your are right. The only error "M := M mod 2;" should be "M := M / 2;"

KJ saying that it has 3 errors doesn't make sense.

Weng

Actually if i used integer_bit_width(N) instead of log2(N), there are no confusions here, no ceiling or floor.

What I want is the bit width of an integer.

My only error "M := M mod 2;" should be "M := M / 2;"

for integer 8, return is 4; if 7, return is 3. Very simple.

Of cause I learn 2 things from this post:
1. A constant uplimit can be generated by a function with constant input parameters.

2. A void use operator mod that is more complex than what you think.

Thank you everyone.

Weng

The following first post by KJ causes Rick's doubt:

What exactly is the issue? ieee.MATH_REAL defines a log2 function that can be used to define the upper bound. Actually what you want is
ceil(log2(N))

Kevin

I jusu ignored KJ' above info.

Yes, you can invent an arbitrary function to return any value you want.
So why not write it as vector_high_bit and save the subtraction? It
then maps perfectly to the integer function log2(N) and you are done.

function vector_high_bit(integer: N) return integer is
begin
return log2(N);
end vector_high_bit;

Even that name it too wordy for me, but it helps to be descriptive. I
program software in Forth (very efficient and all about simplicity) and
hardware in VHDL (very wordy tending toward the complex). Sometimes the
contrast is very annoying.

--

Rick