Quantcast

Documentation Center

  • Trial Software
  • Product Updates

Normalize Data for Lookup Tables

This example shows how to normalize data for use in lookup tables.

Lookup tables are a very efficient way to write computationally-intense functions for fixed-point embedded devices. For example, you can efficiently implement logarithm, sine, cosine, tangent, and square-root using lookup tables. You normalize the inputs to these functions to produce a smaller lookup table, and then you scale the outputs by the normalization factor. This example shows how to implement the normalization function that is used in examples Implement Fixed-Point Square Root Using Lookup Table and Implement Fixed-Point Log2 Using Lookup Table.

Setup

To assure that this example does not change your preferences or settings, this code stores the original state, and you will restore it at the end.

originalFormat = get(0, 'format'); format long g
originalWarningState = warning('off','fixed:fi:underflow');
originalFiprefState = get(fipref); reset(fipref)

Function to Normalize Unsigned Data

This algorithm normalizes unsigned data with 8-bit bytes. Given input u > 0, the output x is normalized such that

u = x * 2^n

where 1 <= x < 2 and n is an integer. Note that n may be positive, negative, or zero.

Function fi_normalize_unsigned_8_bit_byte looks at the 8 most-significant-bits of the input at a time, and left shifts the bits until the most-significant bit is a 1. The number of bits to shift for each 8-bit byte is read from the number-of-leading-zeros lookup table, NLZLUT.

function [x,n] = fi_normalize_unsigned_8_bit_byte(u) %#codegen
    assert(isscalar(u),'Input must be scalar');
    assert(all(u>0),'Input must be positive.');
    assert(isfi(u) && isfixed(u),'Input must be a fi object with fixed-point data type.');
    u = removefimath(u);
    NLZLUT = number_of_leading_zeros_look_up_table();
    word_length = u.WordLength;
    u_fraction_length = u.FractionLength;
    B = 8;
    leftshifts=int8(0);
    % Reinterpret the input as an unsigned integer.
    T_unsigned_integer = numerictype(0, word_length, 0);
    v = reinterpretcast(u,T_unsigned_integer);
    F = fimath('OverflowAction','Wrap',...
               'RoundingMethod','Floor',...
               'SumMode','KeepLSB',...
               'SumWordLength',v.WordLength);
    v = setfimath(v,F);
    % Unroll the loop in generated code so there will be no branching.
    for k = coder.unroll(1:ceil(word_length/B))
        % For each iteration, see how many leading zeros are in the high
        % byte of V, and shift them out to the left. Continue with the
        % shifted V for as many bytes as it has.
        %
        % The index is the high byte of the input plus 1 to make it a
        % one-based index.
        index = int32(bitsra(v, word_length - B) + uint8(1));
        % Index into the number-of-leading-zeros lookup table.  This lookup
        % table takes in a byte and returns the number of leading zeros in the
        % binary representation.
        shiftamount = NLZLUT(index);
        % Left-shift out all the leading zeros in the high byte.
        v = bitsll(v,shiftamount);
        % Update the total number of left-shifts
        leftshifts = leftshifts+shiftamount;
    end
    % The input has been left-shifted so the most-significant-bit is a 1.
    % Reinterpret the output as unsigned with one integer bit, so
    % that 1 <= x < 2.
    T_x = numerictype(0,word_length,word_length-1);
    x = reinterpretcast(v, T_x);
    x = removefimath(x);
    % Let Q = int(u).  Then u = Q*2^(-u_fraction_length),
    % and x = Q*2^leftshifts * 2^(1-word_length).  Therefore,
    % u = x*2^n, where n is defined as:
    n = word_length -  u_fraction_length - leftshifts - 1;
end

Number-of-Leading-Zeros Lookup Table

Function number_of_leading_zeros_look_up_table is used by fi_normalize_unsigned_8_bit_byte and returns a table of the number of leading zero bits in an 8-bit word.

The first element of NLZLUT is 8 and corresponds to u=0. In 8-bit value u = 00000000_2, where subscript 2 indicates base-2, there are 8 leading zero bits.

The second element of NLZLUT is 7 and corresponds to u=1. There are 7 leading zero bits in 8-bit value u = 00000001_2.

And so forth, until the last element of NLZLUT is 0 and corresponds to u=255. There are 0 leading zero bits in the 8-bit value u=11111111_2.

The NLZLUT table was generated by:

>> B = 8;  % Number of bits in a byte
>> NLZLUT = int8(B-ceil(log2((1:2^B))))
function NLZLUT = number_of_leading_zeros_look_up_table()
%   B = 8;  % Number of bits in a byte
%   NLZLUT = int8(B-ceil(log2((1:2^B))))
    NLZLUT = int8([8    7    6    6    5    5    5    5 ...
                   4    4    4    4    4    4    4    4 ...
                   3    3    3    3    3    3    3    3 ...
                   3    3    3    3    3    3    3    3 ...
                   2    2    2    2    2    2    2    2 ...
                   2    2    2    2    2    2    2    2 ...
                   2    2    2    2    2    2    2    2 ...
                   2    2    2    2    2    2    2    2 ...
                   1    1    1    1    1    1    1    1 ...
                   1    1    1    1    1    1    1    1 ...
                   1    1    1    1    1    1    1    1 ...
                   1    1    1    1    1    1    1    1 ...
                   1    1    1    1    1    1    1    1 ...
                   1    1    1    1    1    1    1    1 ...
                   1    1    1    1    1    1    1    1 ...
                   1    1    1    1    1    1    1    1 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0 ...
                   0    0    0    0    0    0    0    0]);
end

Example

For example, let

u = fi(0.3, 1, 16, 8);

In binary, u = 00000000.01001101_2 = 0.30078125 (the fixed-point value is not exactly 0.3 because of roundoff to 8 bits). The goal is to normalize such that

u = 1.001101000000000_2 * 2^(-2) = x * 2^n.

Start with u represented as an unsigned integer.

   High byte  Low byte
    00000000  01001101  Start: u as unsigned integer.

The high byte is 0 = 00000000_2. Add 1 to make an index out of it: index = 0 + 1 = 1. The number-of-leading-zeros lookup table at index 1 indicates that there are 8 leading zeros: NLZLUT(1) = 8. Left shift by this many bits.

  High byte  Low byte
   01001101  00000000   Left-shifted by 8 bits.

Iterate once more to remove the leading zeros from the next byte.

The high byte is 77 = 01001101_2. Add 1 to make an index out of it: index = 77 + 1 = 78. The number-of-leading-zeros lookup table at index 78 indicates that there is 1 leading zero: NLZLUT(78) = 1. Left shift by this many bits.

  High byte  Low byte
  100110100  0000000    Left-shifted by 1 additional bit, for a total of 9.

Reinterpret these bits as unsigned fixed-point with 15 fractional bits.

x = 1.001101000000000_2 = 1.203125

The value for n is the word-length of u, minus the fraction length of u, minus the number of left shifts, minus 1.

n = 16 - 8 - 9 - 1 = -2.

And so your result is:

[x,n] = fi_normalize_unsigned_8_bit_byte(u)
x = 

                  1.203125

          DataTypeMode: Fixed-point: binary point scaling
            Signedness: Unsigned
            WordLength: 16
        FractionLength: 15

n =

   -2

Comparing binary values, you can see that x has the same bits as u, left-shifted by 9 bits.

binary_representation_of_u = bin(u)
binary_representation_of_x = bin(x)
binary_representation_of_u =

0000000001001101


binary_representation_of_x =

1001101000000000

Cleanup

Restore original state.

set(0, 'format', originalFormat);
warning(originalWarningState);
fipref(originalFiprefState);
Was this topic helpful?