One way to calculate base 2 logarithms

Computing logarithms is a fairly common operation in digital signal processing. Most often, only convolutions (multiplication with accumulation) and amplitudes with phases have to be considered. As a rule, to calculate the logarithms on an FPGA, the CORDIC algorithm is used in a hyperbolic version, requiring only tables and simple arithmetic operations. However, this is not always convenient, especially if the project is large, the crystal is small and dances with optimization begin. It was with such a situation that I had to face one day. Both ports of the RAM block (Cyclone IV) were already working tightly, leaving no free windows. I did not want to use another block for hyperbolic CORDIC. But there was a multiplier, for which a decent free window appeared in the time diagram. After thinking a day, I composed the following algorithm, in which tables are not used, but there is multiplication, more precisely squaring. And since circuit squaring is simpler than the general case of multiplication, perhaps this algorithm is of interest to specialized microcircuits, although of course there is no difference for FPGAs. More details under the cut.

Explaining what's what, it's easier for real numbers. Let's start with them. We proceed to the integer implementation later.

Let there be a number X. Find the number Y such that $$$X = 2 ^ Y$ .
We also assume that X lies in the range from 1 to 2. This does not limit the generality too much, since X can always be transferred to this interval by multiplication or division by a power of two. For Y, this will mean adding or subtracting an integer, which is easy. So X lies in the interval from 1 to 2. Then Y will lie in the interval from 0 to 1. We write Y as an infinite binary fraction:

$$

$$Y = {b_0} 2 ^ 0 + {b_1} 2 ^ {- 1} + ... + {b_n} 2 ^ {- n} + ...$$

Odds $$${b_i}$ there is nothing else in this record than just the bits of the binary representation of the number Y. Moreover, since Y is less than 1, it is obvious that $$${b_0}$ = 0.

Let's square our first equation: $$$X ^ 2 = 2 ^ {2Y}$ and as before, we write the binary representation of 2Y . It's obvious that

$$

$$2Y = {b_1} 2 ^ 0 + {b_2} 2 ^ {- 1} + ... + {b_n} 2 ^ {- (n-1)} + ...$$

Those. bits $$${b_i}$ remained the same, just the powers of two moved. Bat $$${b_0}$ not present in the view because it is zero.

Two cases are possible:

one) $$$X ^ 2> 2$ , 2Y> 1, $$${b_1} = 1$

2) $$$X ^ 2 <2$ , 2Y <1, $$${b_1} = 0$

In the first case, we take as the new value of X $$$X ^ 2/2$ in the second - $$$X ^ 2$ .

As a result, the task was reduced to the former. The new X again lies in the range from 1 to 2, the new Y from 0 to 1. But we learned one bit of the result. Taking the same steps in the future, we can get as many bits of Y as possible.

Let's see how it works in a C program:

#include <stdio.h> #include <math.h> int main() { double w=1.4; double s=0.0; double a=0.5; double u=w; for(int i=0; i<16; i++) { u=u*u; if(u>2) { u=u/2; s+=a; } a*=0.5; } w=log2(w); double err=100*abs(2*(sw)/(s+w)); printf("res=%f, log=%f, err=%f%c\n",s,w,err,'%'); return 0; } 

We calculated the logarithm with an accuracy of 16 bits and compared with what the mathematical library gives. The program brought:

res = 0.485413, log = 0.485427, err = 0.002931%

The result coincided with the library with an accuracy of 0.003%, which shows the efficiency of our algorithm.

Let's move on to an integer implementation.

Let N-bit binary unsigned numbers represent the interval [0, 1]. For convenience, we consider the unit number $$$2 ^ N$ , but not $$$2 ^ N-1$ , and accordingly a deuce number $$$2 ^ {N + 1}$ . We will write a program in the image and likeness of the previous one, but working with integers:

 #include <stdio.h> #include <math.h> #define DIG 18 //  #define N_BITS 16 //    unsigned ONE=1<<(DIG-1); // unsigned TWO=ONE<<1; // unsigned SCALE=1<<(N_BITS+1); //  unsigned myLog(unsigned w) { unsigned s=0; unsigned long long u=w; for(int i=0; i<N_BITS+1; i++) { s<<=1; u=(u*u)>>(DIG-1); //    ! if(u&TWO) //      { u>>=1; s+=1; } printf("%X\n", (int)u); } return s; } int main() { double w=1.2345678; unsigned iw=(unsigned)(ONE*w); double dlog=log2(w); unsigned ilog=myLog(iw); unsigned test=(unsigned)(SCALE*dlog); int err=abs((int)(ilog-test)); printf("val=0x%X, res=0x%X, log=0x%X, err=%d\n",iw,ilog,test,err); return 0; } 

Having played in a program with different bit depths (DIG), calculation accuracy (N_BITS), and logarithm arguments (w), we see that everything is calculated correctly. In particular, with those parameters that are specified in this source, the program produces:

val = 0x27819, res = 0x9BA5, log = 0x9BA6, err = 1

Now everything is ready in order to implement a piece of iron on veril, doing exactly the same thing as the myLog function in C. The variables s and u in our function can be printed in a loop and compared with what the verilog simulator produces. The correspondence of these variables to the iron implementation is very transparent and understandable. u is a working register that takes new values ​​of X during iterations. s is a shift register in which the result is accumulated. The interface of our module will look like this:

 module logarithm( input clk, // input wr, //   input[17:0] din, //   output[nbits-1:0] dout, //   output rdy //  ); parameter nbits=16; //  

The input bus is adopted 18-bit, respectively, the width of the multipliers in Cyclone IV. The numbers on our module should come normalized. Those. with high bit equal to one. In my project, this was done automatically. But in which case to implement the normalizer, I think it’s not difficult for anyone. The accuracy of the calculations is set by the nbits parameter, by default equal to 16. The module counts one bit per cycle, and for 16 cycles it calculates the logarithm with an accuracy of 16 bits. If you need faster with the same accuracy or more precisely with the same speed, I hope it will not be difficult for anyone to divide the module into several devices and convey.


Run the test with this script:

 #!/bin/sh rm -f *.vvp rm -f *.vcd iverilog -o testbench.vvp logarithm.v testbench.v vvp testbench.vvp gtkwave testbench.vcd testbench.gtkw 

Running the test, we see the final output of the simulator - value = 27819, result = 9ba5. Verilog gave the same thing as C. The timing diagram here is quite trivial and is not of particular interest. Therefore, I do not bring it.


Make sure they match bit by bit. In total, the implementation on a verilo repeats the model on C up to a bit. This is the result that should be achieved by implementing algorithms in hardware.

That’s probably all. I hope someone will find this my experience useful.