# Binary Logarithm

## SystemVerilog implementation of the Hardware Algorithm

Posted by Nelson Campos on August 02, 2016

The logarithm operation is widely used in digital signal processing. There are many scientific applications that requieres logarithm computations and since it is computer expensive a hardware implementation may be used for acceleration purposes.

An algorithm for the base 2 logarithm can be seen in .

A binary logarithm may be defined according to equation (1): equation (1)

Inverting the equation (1) the equation (2) is obtained: equation (2)

y may be represented in the binary form as can be seen in equation (3): equation (3)

Putting equation (3) into equation (2) the equation (4) is obtained as follows: equation (4)

From equations (3) and (4) can be inferred that the maximum value of y is 1 (the sum of a geometric progression with common ratio 0.5 when all bits of y is 1) and consequently the maximum value of x is 2.

Squaring equation (4) gives the equation (5) as can be seen below: equation (5)

An analysis of equation (5) states that the value of x2 can be expressed in two cases: equation (6)

According to equation (6) if the value x2 >2, then the i-th bit of yi is 1 at the i-th iteration and x should be divided by 2, otherwise, if x2<=2, yi=0.

Since the binary algorithm works for 0<=x<=1, if x is greater than 1, x should be scaled as can be seen below: equation (7)

## Example: calculating log2(pi)

To illustrate the algorithm, the calculation of the logarithm of log2(pi) (pi is approximately 3.140625), pi is scaled according to table 1.

x k x scaled
3.140625 1 1.5703125
table (1)

The value k is the integer part of the logarithm. Now the scaled value of x will be computed using the algorithm. Table (2) gives the result of the scaled x using 7 bits of precision.

i x x^2 x^2>2 y
6 1.5707 2.46 yes 1
5 1.23 1.51 no 0
4 1.51 2.28 yes 1
3 1.14 1.29 no 0
2 1.29 1.69 no 0
1 1.69 2.86 yes 1
0 1.43 2.04 yes 1
table (2)

The value of y = (0.1010011)2 = 0.6484375 is the fractional part of the logarithm. Then, the approximate value of log2(pi) is k+y = 1.6484375

The flowchart of the logarithm algorithm can be seen in Figure (1). The square operation of x may be computed using the Peasant Multiplication. Figure (1): The Logarithm Algorithm

You want to practice? Check out the SystemVerilog implementation of Logarithm module and its testbench:

```module LOG #(parameter M=4,
N=10)
(output logic [M+N: 0] logNumber,
input logic [M+N: 0] number,
input logic reset, clock, oReady, iValid
);

logic signed [M+N: 0] floorNumber, index;
logic [M+M+N+N:0] x, a, b;
logic [5:0] count;
enum logic [2:0] {INIT,WAIT_AND_PREPARE,SCALE,PEASANT_PREP,PEASANT,CALC,SEND} state;

always_ff @(posedge clock)
if(reset) begin
logNumber <= 'x;
oValid <= 0;
state <= INIT;
end
else case(state)
INIT: begin
logNumber <= '0;
oValid <= 0;
count <= N-1;
index <= 0;
state <= WAIT_AND_PREPARE;
end

WAIT_AND_PREPARE: begin
if(iValid) begin
x <= number;
state <= SCALE;
end
else begin
state <= WAIT_AND_PREPARE;
end
end

SCALE: begin
if((x>>N) > 1) begin
x <= x >> 1;
index <= index+1;
end
else if(!(x>>N)) begin
x <= x << 1;
index <= index-1;
end
else begin
index <= index<<<N;
state <= PEASANT_PREP;
end
end

PEASANT_PREP: begin
a <= x;
b <= x;
x <= 0;
state <= PEASANT;
end

PEASANT: begin
if(a>=1) begin
x <= (a)?(x+b):x;
a <= a >> 1;
b <= b << 1;
end
else begin
x <= x>>N;
state <= CALC;
end
end

CALC: begin
if(count<=N-1) begin
if((x>>N) >= 2) begin
logNumber[count] <= 1;
x <= x>>1;
end
else logNumber[count] <= 0;

count <= count-1;
state <= PEASANT_PREP;
end
else begin
state <= SEND;
logNumber <= index+logNumber;
oValid <= 1;
end
end

SEND: begin
oValid <= 0;
state <= INIT;
end
else state <= SEND;
end
endcase
endmodule: LOG
```
SystemVerilog code for Logarithm Algorithm
````include "log2.sv"

parameter M = 4;
parameter N = 10;

module top;
logic clock;
logic reset;

logic signed [M+N: 0] number, logNumber;

enum logic {S1,S2} state;

initial begin
clock = 0;
reset = 1;
#22 reset = 0;
end

always #5 clock = !clock;

LOG#(M,N) myLog(.*);

always_ff @(posedge clock) begin
if(reset) begin
iValid <= 0;
state <= S1;
end
else case(state)
S1: begin
number <= 15'b00011_0010010000;
iValid <= 1;
state <= S2;
end
S2:
if(oValid) begin
if(logNumber[M+N])
\$display("%b", (~logNumber+15'd1));
else
\$display("%b", logNumber);

\$finish();
end
endcase
end
endmodule
```
SystemVerilog code for Logarithm testbench

References:  A Fast Binary Logarithm Algorithm

Also available in GitHub.