Logarithm Computation

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 [1].

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 x² can be expressed in two cases:

equation (6)

According to equation (6) if the value x² >2, then the i-th bit of y_i is 1 at the i-th iteration and x should be divided by 2, otherwise, if x²<=2, y_i=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 log₂(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)₂ = 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,
             output logic iReady, oValid, 
             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
            iReady <= 0;
            logNumber <= 'x;
            oValid <= 0;
            state <= INIT;
        end
        else case(state)
                INIT: begin
                    logNumber <= '0;
                    iReady <= 1;
                    oValid <= 0;
                    count <= N-1;
                    index <= 0;
                    state <= WAIT_AND_PREPARE;
                end
                
                WAIT_AND_PREPARE: begin
                    if(iValid) begin
                        iReady <= 0;
                        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[0])?(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
                    if(oReady) 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 iReady, iValid, oReady, oValid;
    
    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;
            oReady <= 0;
        end
        else case(state)
            S1: begin
                number <= 15'b00011_0010010000;
                iValid <= 1;
                if(iReady)
                    state <= S2;
                    oReady <= 1;
            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: [1] A Fast Binary Logarithm Algorithm

Also available in GitHub.

Example: calculating log2(pi)

Example: calculating log₂(pi)