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)
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
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
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 =
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_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); %#ok<*NOPTS>