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):

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

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

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

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:

An analysis of equation (5) states that the value of *x ^{2}* can be expressed in two cases:

According to equation (6) if the value *x ^{2} >2*, then the

*i-th*bit of

*y*is 1 at the

_{i}*i-th*iteration and

*x*should be divided by 2, otherwise, if

*x*,

^{2}<=2*y*.

_{i}=0Since the binary algorithm works for 0<=*x*<=1, if *x* is greater than 1, *x* should be scaled as can be seen below:

## Example: calculating *log*_{2}(pi)

_{2}(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 |

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 |

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.

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

`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

References: [1] A Fast Binary Logarithm Algorithm

Also available in GitHub.