Exponentiation (exponentiation)

Pipelined exponentiation calculator.

Design

Exponentiation is the mathematical operation of raising one quantity to the power of another.

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

(118)\[y[n] = b^{x[n]}\]

In (118):

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

  • \(x[n]\) is the input values, known as the exponent or power.

  • \(b\) is the base.

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

(119)\[ \begin{align}\begin{aligned}b^y = x\\log_b(x) = y\end{aligned}\end{align} \]
Common exponentiation plots.

Figure 205: Exponentiation 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 an exponentiation. It is derived from the C implementation provided at https://quinapalus.com/efunc.html.

The base of the exponentiation is set using the generic base_g. A log table of power of two logarithm values is generated from base_g at build time and used throughout the implementation to avoid complex mathematical operations. Base values less than one are not supported.

The input and output bit widths are set using the generics input_size_g and output_size_g. The value assigned to output_size_g determines the size of the build time log table, which is equal to \(\log_2{( \texttt{output_size_g} )} + 7\).

data_in and data_out are both unsigned and 16-bit fixed point values.

The code below shows the equivalent C implementation of the algorithm for a base value of \(e\). The literal values assigned to y in the sample C implementation below come from the log table generated at build time.

In the C implementation y is initialised in line 3 to \(2^{16}\) (0x10000). This is the lowest value y will ever be since all subsequent operations increase its value closer to the resultant exponentiation value. As y iteratively converges on the resultant value, x is reduced as close to zero as possible without being less than zero. Each time x is reduced in value, y is correspondingly increased, such that the closer in value x is to zero the closer y is to the exponentiation result.

For each subtraction of a log table value from x, y is appropriately increased in value. The relationship is such that if \(k\) is subtracted from x, y is multiplied by \(e^k\). The log table values are calculated so every multiplication to y is no more computationally intensive than a shift or addition operation. For example, multiplying by \(2^n\) is achieved by a shift, and multiplication by \(\pm 2^n \pm 1\) is achieved by a shift and addition. Lines 4 to 8 below show multiplication by \(2^n\) values and lines 9 to 24 below show multiplication by \(2^{-n} + 1\).

 1int64_t fxexp(int64_t x) {
 2  int64_t t,y;
 3  y = 0x10000;                                  // 2^16
 4  t = x - 0xB1721; if(x >= 0) x = t, y <<= 16;  // log_e(2^16) * 2^16
 5  t = x - 0x58B91; if(x >= 0) x = t, y <<= 8;   // log_e(2^8) * 2^16
 6  t = x - 0x2C5C8; if(x >= 0) x = t, y <<= 4;   // log_e(2^4) * 2^16
 7  t = x - 0x162E4; if(x >= 0) x = t, y <<= 2;   // log_e(2^2) * 2^16
 8  t = x - 0x0B172; if(x >= 0) x = t, y <<= 1;   // log_e(2^1) * 2^16
 9  t = x - 0x067CD; if(x >= 0) x = t, y += y>>1; // log_e(1+2^(-1)) * 2^16
10  t = x - 0x03920; if(x >= 0) x = t, y += y>>2; // log_e(1+2^(-2)) * 2^16
11  t = x - 0x01E27; if(x >= 0) x = t, y += y>>3; // log_e(1+2^(-3)) * 2^16
12  t = x - 0x00F85; if(x >= 0) x = t, y += y>>4; // log_e(1+2^(-4)) * 2^16
13  t = x - 0x007E1; if(x >= 0) x = t, y += y>>5; // log_e(1+2^(-5)) * 2^16
14  t = x - 0x003F8; if(x >= 0) x = t, y += y>>6; // log_e(1+2^(-6)) * 2^16
15  t = x - 0x001FE; if(x >= 0) x = t, y += y>>7; // log_e(1+2^(-7)) * 2^16
16  if(x & 0x100) y += y>>8;
17  if(x & 0x080) y += y>>9;
18  if(x & 0x040) y += y>>10;
19  if(x & 0x020) y += y>>11;
20  if(x & 0x010) y += y>>12;
21  if(x & 0x008) y += y>>13;
22  if(x & 0x004) y += y>>14;
23  if(x & 0x002) y += y>>15;
24  if(x & 0x001) y += y>>16;
25  return y;
26}

The amount of error introduced by this iterative approximation depends on the residual value in x. Since \(e^x\) is approximately \(1+x\) it is possible to correct the final answer by multiplying it by \(1+x\). However, this operation requires a general multiplication and the additional accuracy is most likely not worthwhile for hardware implementations.

The clock cycle delay through this pipelined implementation is equal to \(23 + 2 \lceil \log_2{( \texttt{output_size_g} )} \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 exponentiation.

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 (unsigned(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 in exponentiation are:

  • Negative input and output values are not supported.

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