# 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