Logarithm (logarithm)

Pipelined logarithm calculator.

Design

The logarithm of a given number is the exponent to which another number, the base \(b\), must be raised to produce that number. For example, \(\log_{2}{(64)} = 6\) and \(2^6 = 64\).

The mathematical representation of the implementation is given in (96).

(96)\[y[n] = \log_{b}{( x[n] )}\]

In (96):

  • \(y[n]\) is the output values.

  • \(x[n]\) is the input values.

  • \(b\) is the base.

The relationship between an exponentiation and a logarithm is given in (97). Plots of three commonly used bases for logarithm are shown in Figure 80:.

(97)\[ \begin{align}\begin{aligned}b^y = x\\log_{b}{( x )} = y\end{aligned}\end{align} \]
Common logarithm plots.

Figure 80: Logarithm plots for bases \(2\), \(e\) and \(10\).

Implementation

This pipelined implementation avoids the use of multiplication and division operations. Instead it employs shifting and addition/subtraction to approximate the logarithm. It is derived from the C implementation provided at https://quinapalus.com/efunc.html.

The base of the logarithm is set using the generic base_g. A log table of power of two logarithm values is generated from this value. The table is used in the implementation to avoid complex mathematical operations.

The input and output bit widths are set using the generics input_size_g and output_size_g.

data_in is unsigned and data_out is signed. They are both 16-bit fixed point values so input_size_g and output_size_g must be at least 16-bits.

The code below shows the equivalent C implementation of the algorithm for a base value of \(e\). x and y in the below code sample are the input and output values to the algorithm, respectively, and therefore scaled up by a factor of \(2^{16}\). The literal values assigned to y in the implementation come from the log table generated at build time.

In the C implementation below y is initialised in line 3 to \(log_{e}{(2^{15})} \times 2^{16}\). This is the maximum value y can be since all subsequent operations on y are subtractions that lessen its value closer to the resultant logarithm value. Therefore, the input value x must not exceed \(2^{15} \times 2^{16}\) otherwise the algorithm will operate out of scope and return an incorrect result. In the implementation the initial value of y and the size of the log table is determined at build time using the generic input_size_g. This ensures the full range of input values can be utilised without ever operating the algorithm out of scope.

After y is initialised (line 3) the iterative portion of the algorithm begins. x’s value is compared against power of two values and if it is less, x is multiplied by the corresponding power of two and y is subtracted from by the corresponding value in the log table. For each multiplication of x by \(k\), \(log(k)\) is subtracted from y. This continues until y is a near approximation of the logarithm result and subsequently until x is a near approximation of 0x8000000 (\(2^{31}\)). 0x8000000 is obtained from \(2^{\texttt{input bits} + \texttt{fractional bits}}\) where input bits is equal to the supported input range of the algorithm, which as stated above for the example C implementation is up to \(2^{15} \times 2^{16}\). Finally in line 16 and line 17, the absolute error in x is subtracted from y. The implementation output value is equal to the logarithm of the input value scaled up by a factor of \(2^{16}\).

 1int64_t fxlog_e(int64_t x) {
 2  int64_t t,y;
 3  y = 0xA65AF;                                                       // log_e(2^15)*2^16
 4  if (x < 0x00008000) x <<= 16,                       y -= 0xB1721;  // log_e(2^16)*2^16
 5  if (x < 0x00800000) x <<= 8,                        y -= 0x58B91;  // log_e(2^8)*2^16
 6  if (x < 0x08000000) x <<= 4,                        y -= 0x2C5C8;  // log_e(2^4)*2^16
 7  if (x < 0x20000000) x <<= 2,                        y -= 0x162E4;  // log_e(2^2)*2^16
 8  if (x < 0x40000000) x <<= 1,                        y -= 0x0B172;  // log_e(2^1)*2^16
 9  t = x + (x >> 1); if ((t & 0x80000000) == 0) x = t, y -= 0x067CD;  // log_e(1+2^(-1))*2^16
10  t = x + (x >> 2); if ((t & 0x80000000) == 0) x = t, y -= 0x03920;  // log_e(1+2^(-2))*2^16
11  t = x + (x >> 3); if ((t & 0x80000000) == 0) x = t, y -= 0x01E27;  // log_e(1+2^(-3))*2^16
12  t = x + (x >> 4); if ((t & 0x80000000) == 0) x = t, y -= 0x00F85;  // log_e(1+2^(-4))*2^16
13  t = x + (x >> 5); if ((t & 0x80000000) == 0) x = t, y -= 0x007E1;  // log_e(1+2^(-5))*2^16
14  t = x + (x >> 6); if ((t & 0x80000000) == 0) x = t, y -= 0x003F8;  // log_e(1+2^(-6))*2^16
15  t = x + (x >> 7); if ((t & 0x80000000) == 0) x = t, y -= 0x001FE;  // log_e(1+2^(-7))*2^16
16  x = 0x80000000 - x; // Absolute error
17  y -= x >> 15;
18  return y;
19}

The clock cycle delay through this pipelined implementation is equal to \(19 + \lceil log_{2}{( \texttt{input_width_g} + 0.5)} \rceil\) clock cycles. The data_valid_out output indicates when a result is available.

Interface

Generics

  • input_size_g (integer): Input bit width.

  • output_size_g (integer): Output bit width.

  • base_g (real): Base value of logarithm.

Ports

  • clk (std_logic), in: Clock. Inputs and outputs registered on rising edge.

  • rst (std_logic), in: Reset. Active high, synchronous with rising edge of clock.

  • clk_en (std_logic), in: Enable. If clk_en is low the module will not operate.

  • data_valid_in (std_logic), in: Valid In. High when data on data_in port is available.

  • data_in (unsigned(input_size_g - 1 downto 0)), in: 16-bit fixed point input data.

  • data_valid_out (std_logic), out: High when data on data_out port is available.

  • data_out (signed(output_size_g - 1 downto 0)), out: 16-bit fixed point output data.

Dependencies

The dependencies to other elements in OpenCPI are:

  • None.

There is also a dependency on:

  • ieee.std_logic_1164

  • ieee.numeric_std

  • ieee.math_real

Limitations

Limitations of logarithm are:

  • Negative input values are not supported.

  • Base values less than or equal to one are not supported.