[Moved] VHDL log base 2 function

Yes, it is now completely clear where the confusion comes from.
We are discussing the answers to 2 different questions:

1. How many bits do I need to represent the number N
2. How many bits do I need to address N different values?


I prefer a function that gives the answer to question 1 (TrickyDicky's function).

The reason is that for question 2 I am already used to see it as a range (0 to N-1) or (N-1 downto 0).
It is then clear that the highest index is N-1, and TrickyDicky's function can be used to calculate how many bits are needed to represent it.

Yes, it is now completely clear where the confusion comes from.
We are discussing the answers to 2 different questions:

1. How many bits do I need to represent the number N
2. How many bits do I need to address N different values?

I prefer a function that gives the answer to question 1 (TrickyDicky's function).

Click to expand...

I think, the question isn't which answer you prefer, but which value a specific problem needs. I came across the first variant in most cases.

Altough most contributors are talking about a numeric range 0..N respectively N+1 elements, Shaiko didn't explicitely tell about his intention. So I don't understand why Kevin claims, the original question would refer to N elements (range 0..N-1).

FvM said:

Shaiko didn't explicitely tell about his intention.

Click to expand...

Shaiko's intention is to generically set a vector length according to it's integer value (during compilation).
For example :

generic memory_depth : positive range 1 to 1000 := 15 ;
memory_address : in unsigned ( our_function ( memory_depth ) - 1 downto 0 ) ;

Still not exactly clear, I fear. Memory depth usually counts the memory cells, they can be enumerated 0.. memory_depth-1. Then Kevin's interpretation applies.

FvM said:

Memory depth usually counts the memory cells.

Click to expand...

That's what I meant also!
I don't understand the unclarity here.
If the address vector is (memory_depth - 1 downto 0 ) then, the number of cells equals "memory_depth".

If the memory is single cell deep - then I expect our_function ( memory_depth ) to output 1 and the address vector ( memory_depth - 1 downto 0 ) will be in this case ( 0 downto 0 ).

std_match said:

Yes, it is now completely clear where the confusion comes from.
We are discussing the answers to 2 different questions:

1. How many bits do I need to represent the number N
2. How many bits do I need to address N different values?

Click to expand...

There is also a third question
3. What should one reasonably expect as the result of calling a function called "log2(x)" that admittedly returns an integer approximation? Should the function return
- The integer representation of the mathematical 'log2(x)'?
- The integer representation of the mathematical 'log2(x+1)?

Try to answer that question from the point of view of someone trying to use the function, not someone who knows how or has access to the actual implementation of that function.

I don't want to belabor the point too much since I was getting mildly dissed earlier in the thread (so feel free to jump to the next paragraph), but I would think most would consider 'log2(x)' to be the expected response. As I mentioned in an earlier post, 'log2' (both forms being discussed) is synthesizable and can be used to take the log base 2 of an input signal as well. Since people are so ingrained to their preferred usage of the 'log2' function, for those using Tricky's version, based on the responses in this forum it suggest to me that people have forgotten that this function they called 'log2' has this anomaly built right in.

Maybe some would consider all of this pedantic, but good designs are based on solid building blocks and a designer uses building blocks that others have created and generally appreciates when a design that purports to do 'x' does what is commonly expected of 'x'. In this case, I don't think it's unreasonable for someone first stumbling across this need to expect that the synthesizable version of the building block 'log2(x)' is based on the mathematical representation of 'log2(x)', not 'log2(x+1)'. Having to remember that to take the log2 of a number x really means that I have to say 'log2(x-1)' is problematic because if you remember that rule, you're also likely to mis-remember it and write 'log2(x+1)' by mistake. Even Tricky admitted this when he suggested the function should really be called "n_bits, because its not a real log2 anymore". That just moves the problem in my opinion since now one needs to look at the documentation or code for 'n_bits' in order to figure out what it does (Tricky's posted code didn't show the documentation so one would have to likely sim it first in order to discern precisely what it is implementing). The log2 code I posted from Tuukka Toivonen on the VHDL FAQ page is based on the mathematical building block of the 'log' function in base 2...pretty solid foundation, should be little need for explanation of function beyond the 'truncation to an integer' portion of the function.

I prefer a function that gives the answer to question 1 (TrickyDicky's function).

The reason is that for question 2 I am already used to see it as a range (0 to N-1) or (N-1 downto 0).
It is then clear that the highest index is N-1, and TrickyDicky's function can be used to calculate how many bits are needed to represent it.

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

Click to expand...

And that's fine if that's your preference. I suspect that the most common use case for most folks with whichever form of log2 function that they prefer is for defining the number of bits in the address input to a memory of a generic size. In that situation, my form is the more useful form if you prefer to specify the actual depth of the memory (i.e. 256, 512); Tricky's form is the more useful form if you prefer to specify the highest addressable memory address (255, 511). I'll end this by simply noting that memory is generally specified by size, not by highest address and leave it at that.

Kevin Jennings

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

FvM said:

I think, the question isn't which answer you prefer, but which value a specific problem needs. I came across the first variant in most cases.

Click to expand...

Just curious, can you elaborate a bit on what those cases are? I would guess that the most common use case for log2 of all people that run across a need for this function is for computing the range of the address bits in a memory of depth 'N' entries (which would lend itself to using my version). I was just wondering about the cases you've run across.

Maybe it simply comes down to whether you like to declare the signal first or the length first? In order to define the range of the signal without calculating the length you would likely want to use my ceil_log2 rather than Tricky's log2 and then simply get the length of the vector (if you even need it) using the 'length VHDL attribute. If you come from the perspective of wanting to define the length of the vector first and then base the vector range on the calculated length then you might prefer Tricky's form (and live with the anomaly regarding log2(x+1) if you call your function 'log2').

So on the assumption that the preference for declaring a length or the vector range first is the deciding factor, the question you should ask yourself is where do you really use this computed length other than to declare the vector range? Then ask yourself if it isn't clearer to refer to my_signal'length rather than your computed constant in those other situations? (Rhetorical questions here meant only to stimulate thought not argument...good discussion, even though it is on seemingly minor points, these can ripple into strange anomolies down the road if one forgets about 'x-1'...or was it 'x+1')

Kevin Jennings

---------- Post added at 09:42 ---------- Previous post was at 09:38 ----------

shaiko said:

Shaiko's intention is to generically set a vector length according to it's integer value (during compilation).
For example :

generic memory_depth : positive range 1 to 1000 := 15 ;
memory_address : in unsigned ( our_function ( memory_depth ) - 1 downto 0 ) ;

Click to expand...

Actually, if you look at what you just posted here, it appears that your true intention is to define the address range of the signal. In a sense you don't care what the length is as long as the vector is defined to be the correct size. If inside the design you happened to need the length of memory_address for some reason you could use memory_address'length.

Kevin Jennings

If the address vector is (memory_depth - 1 downto 0 ) then, the number of cells equals "memory_depth".

Click to expand...

No, the number of memory cells is two raised memory_depth in this case.

Kevin, just a short comment. If you review my posts, you'll notice that I didn't express any doubts about the result of log2(x). I was talking about the bit number for a vector representing a range 0..N. I also mentioned, that I often needed this kind of function. I think, the statement is pretty clear and shouldn't bring up a lengthy discussion.

I agree however, that the function ceil(log2(x+1)) shouldn't be named log2().