Fixed-Point Blockset

Determining Input Location

This section describes how the three fixed point lookup tables determine where the current input is relative to the breakpoints.

Uneven Case

Unevenly spaced breakpoints require a general-purpose algorithm such as a binary search to determine where the input lies in relation to the breakpoints. The following code provides an example:

• iLeft = 0;
  iRght = 7; /* number of breakpoints minus 1 */
  
  while ( ( iRght - iLeft ) > 1 )
  {
    i = ( iLeft + iRght ) >> 1;
  
  if ( uAngle < xuneven[i] )
    {
      iRght = i;
    }
    else
    {
      iLeft = i;
    }
  }
  

The while loop executes up to log2(N) times where N is number of breakpoints.

Even Case

Evenly spaced breakpoints require only one step to determine where the input lies in relation to the breakpoints:

• iLeft = uAngle / 455U;
  

The divisor 455U represents the spacing between breakpoints. In general, the dividend would be (uAngle - SmallestBreakPoint). In this example, the smallest breakpoint was zero, so the subtraction was optimized out.

Power of Two Case

Power of two spaced breakpoints require only one step to determine where the input lies in relation to the breakpoints:

• iLeft = uAngle >> 8;
  

The number of shifts is 8 because the breakpoints have spacing 2^8. The smallest breakpoint was zero, so uAngle replaced the general case of (uAngle - SmallestBreakPoint).

Comparison

To determine where the input is located with respect to the breakpoints, the unevenly spaced case clearly requires much more code than the other two cases. This code requires additional command ROM. This ROM penalty can be reduced if many lookup tables share the binary search algorithm as a function. Even if the code is shared, the number of clock cycles required to determine the location of the input is much higher for the unevenly spaced cases than the other two cases. If the code is shared, then function call overhead decreases the speed of execution a little more.

In the evenly spaced case and the power of two spaced case, you can determine the location of the input with a single line of code. The evenly spaced cased uses a general integer division. The power of two case uses a shift instead of general division because the divisor is an exact power of two. Without knowing the specific processor to be used, you cannot be certain that a shift is better than division.

Many processors can implement division with a single assembly language instruction, so the code will be small. However, this instruction often takes many clock cycles to complete. Quite a few processors do not provide a division instruction. Division on these processors is implemented via repeated subtractions. This is slow and requires a fair amount of machine code, but this code can be shared.

Most processors provide a way to do logical and arithmetic shifts left and right. A distinguishing difference is whether the processor can do N shifts in one instruction (barrel shift) or requires N instructions that shift one bit at a time. The barrel shift will require less code. Whether or not the barrel shift also increases speed depends on the hardware that supports the operation.

The compiler can also complicate the comparison. In the previous example, the command uAngle >> 8 essentially takes the upper 8 bits in a 16 bit word. The compiler may detect this and replace the bit shifts with an instruction that takes the bits directly. If the number of shifts is some other value, such as 7, this optimization would not occur.

Determining Out-of-Range Inputs

Interpolation