Main Content

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.

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

You will restore this state at the end of the example.

Example

Use the normalization function fi_normalize_unsigned_8_bit_byte, defined below, to normalize the data in u.

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 = int8
   -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_u = 
'0000000001001101'
binary_representation_of_x = bin(x)
binary_representation_of_x = 
'1001101000000000'

Cleanup

Restore original state.

set(0,'format',originalFormat);
warning(originalWarningState);
fipref(originalFiprefState);
%#ok<*NOPTS>

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