Fix Point Implementation of ClAlihControl Algorithms

1 Fix Point Implementation of ClAlihControl AlgorithmsAntonCer inAnton CervinLund UniversityOutline A-D and D-A Quantization Computer arithmetic Floating- Point arithmetic Fixed- Point arithmetic Controller realizationsGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Finite-Wordlength ImplementationControl analysis and design usually assumes infinite-precisionarithmetic, parameters/variables are assumed to be real numbersError sources in a digital Implementation with finite wordlength: Quantization in A-D converters Quantization of parameters (controller coefficients) Round-off and overflow in addition, subtraction, multiplication,division, function evaluation and other operations Quantization in D-A convertersGraduate Course on Embedded Control Systems Pisa 8-12 June2009 The magnitude of the problems depends on The wordlength The type of arithmetic used (fixed or floating Point ) The controller realizationGraduate Course on Embedded Control Systems Pisa 8-12 June2009A-D and D-A QuantizationA-D and D-A converters often have quite poor resolution, A-D: 10 16 bits D-A: 8 12 bitsQuantization is a nonlinear phenomenon.

2 Can lead to limit cyclesand bias. Analysis approaches: Nonlinear analysis Describing function approximation Theory of relay oscillations Linear analysis Model quantization as a stochastic disturbanceGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Example: Control of the Double IntegratorProcess:P(s) =1/s2 Sampling period:h=1 Controller (PID):C(z) = + (z 1)(z+ )Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Simulation with Quantized A-D Converter ( y= ) cycle in process output with period 28 s, amplitude Course on Embedded Control Systems Pisa 8-12 June2009 Simulation with Quantized D-A Converter ( u= )05010015001 Output050100150 cycle in controller output with period 39 s, Course on Embedded Control Systems Pisa 8-12 June2009 Describing Function Analysis NL 1H z( )ImReH ei h() 1/Yc(A)(a)(b)Limit cycle with frequency 1and amplitudeA1predicted ifH(ei 1h) = 1Yc(A1)

3 Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Describing Function of Roundoff QuantizerYc(A) = 00<A< 24 AnXi=1s1 2i 12A 22n 12 <A<2n+12 02401A/ Yc(A)Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Nyquist Curve of Sampled Loop Transfer Function 6 4 20 202 Imaginary axisReal axisFirst crossing at 1= Predicts limit cycle with period39 s and amplitudeA1= Course on Embedded Control Systems Pisa 8-12 June2009 Linear Analysis of Quantization Noiseya QyaeaRoundoff quantization:eauniformly distributed over[ /2, /2],V(ea) = 2/12 Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Pulse-Width Modulation (PWM)Poor D-A resolution ( 1 bit) can often be handled by fastswitching between levels + low-pass filteringThe new control variable is the duty-cycle of the switched signal02468101214161820 1 OutputFiltered PWM OutputDesired OutputGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Floating- Point ArithmeticHardware-supported on modern high-end processors (FPUs)Number representation: f$2 e f: mantissa, significand, fraction 2: base e.

4 ExponentThe binary Point is variable (floating) and depends on the value ofthe exponentDynamic range and resolutionFixed number of significant digitsGraduate Course on Embedded Control Systems Pisa 8-12 June2009 IEEE 754 Binary Floating- Point StandardUsed by almost all FPUs; implemented in software librariesSingle precision (Java/Cfloat): 32-bit word divided into 1 sign bit, 8-bit biased exponent, and23-bit mantissa ((7decimal digits) Range:2 126 2128 Double precision (Java/Cdouble): 64-bit word divided into 1 sign bit, 11-bit biased exponent,and52-bit mantissa ((15decimal digits) Range:2 1022 21024 Supports Inf and NaNGraduate Course on Embedded Control Systems Pisa 8-12 June2009 What is the output of this program?))

5 #include < >main() {float a[] = { , , };float b[] = { , , };float sum = ;int i;for (i=0; i<3; i++)sum += a[i]*b[i];printf("sum = %f\n", sum);}Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Remarks: The result depends on the order of the operations Finite-wordlength operations are neither associative nordistributiveGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Arithmetic in Embedded SystemsSmall microprocessors used in embedded systems typically do nothave hardware support for floating- Point arithmeticOptions: Software emulation of floating- Point arithmetic compiler/library supported large code size, slow Fixed- Point arithmetic often manual Implementation fast and compactGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Fixed- Point ArithmeticRepresent all numbers (parameters, variables) usingintegersUsebinary scalingto make all numbers fit into one of the integerdata types, 8 bits (char, int8_t):[ 128, 127] 16 bits (short, int16_t):[ 32768, 32767] 32 bits (long, int32_t).

6 [ 2147483648, 2147483647]Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Challenges Must select data types to get sufficient numerical precision Must know (or estimate) the minimum and maximum value ofevery variable in order to select appropriate scaling factors Must keep track of the scaling factors in all arithmeticoperations Must handle potential arithmetic overflowsGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Fixed- Point RepresentationIn fixed- Point representation, a real numberxis represented by anintegerXwithN=m+n+1bits, where Nis the wordlength mis the number of integer bits (excluding the sign bit) nis the number of fractional bitsSign bitInteger bitsFractional bits00011111 Q-format :Xis sometimes called Course on Embedded Control Systems Pisa 8-12 June2009 Conversion to and from fixed pointConversion from real to fixed- Point number:X:=round(x 2n)Conversion from fixed- Point to real number:x:=X 2 nExample:Representx= ( 23) =107(=011010112)Graduate Course on Embedded Control Systems Pisa 8-12 June2009A Note on Negative NumbersIn almost all CPUs today, negative integers are handled usingtwo s complement: A 1 in the sign bit means that2 Nshould besubtractedExample (N=8).

7 Binary Course on Embedded Control Systems Pisa 8-12 June2009 Range vs Resolution for Fixed- Point number can represent real numbers in therange[ 2m, 2m 2n]while the resolution is2 nFixed range and resolution ntoo small[poor resolution ntoo large[risk of overflowGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Fixed- Point Addition/SubtractionTwo fixed- Point numbers in the can be addedor subtracted directlyThe result will have the same number of fractional bitsz=x+y\Z=X+Yz=x y\Z=X Y The result will in general requireN+1bits; risk of overflowGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Example: Addition with OverflowTwo numbers are added.]]

8 X= [X=98y= [Y=118Z=X+Y=216 This number is however out of range and will be interpreted as216 256= 40[z= Course on Embedded Control Systems Pisa 8-12 June200900 000000000011 1 111 111111+=Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Fixed- Point Multiplication and DivisionIf the operands and the result are in the same Q-format,multiplication and division are done asz=x y\Z= (X Y)/2nz=x/y\Z= (X 2n)/Y Double wordlength is needed for the intermediate result Division by2nis implemented as a right-shift bynbits Multiplication by2nis implemented as a left-shift bynbits The lowest bits in the result are truncated (round-off noise) Risk of overflowGraduate Course on Embedded Control Systems Pisa 8-12 June2009 Example: MultiplicationTwo numbers are multiplied:x= [X=25y= [Y=19 Intermediate result:X Y=475 Final result:Z=475/22=118[z= (exact result is )Graduate Course on Embedded Control Systems Pisa 8-12 June200900000000000000000000001111 111111 11 111111$=Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Multiplication of Operands with Different Q-formatIn general, multiplication of two fixed- Point an intermediate result in the formatQm1+ +n2which may then be right-shiftedn1+n2 n3steps and stored in case.]]]]]]

9 N2=n3=0(one real operand, one integeroperand, and integer result). ThenZ= (X Y)/2n1 Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Implementation of Multiplication in #include < >/* define int8_t, etc. (Linux only)*/#define n 3/* number of fractional bits*/int8_t X, Y, Z;/* operands and result*/int16_t temp;/* intermediate result*/..temp = (int16_t)X * Y; /* cast operands to 16 bits and multiply*/temp = temp >> n;/* divide by 2^n*/Z = temp;/* truncate and assign result*/Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Implementation of Multiplication in C with Roundingand Saturation#include < >/* defines int8_t, etc.

10 (Linux only)*/#define n 3/* number of fractional bits*/int8_t X, Y, Z;/* operands and result*/int16_t temp;/* intermediate result*/..temp = (int16_t)X * Y; /* cast operands to 16 bits and multiply*/temp = temp + (1 << n-1); /* add 1/2 to give correct rounding*/temp = temp >> n;/* divide by 2^n*/if (temp > INT8_MAX)/* saturate the result before assignment */Z = INT8_MAX;else if (temp < INT8_MIN)Z = INT8_MIN;elseZ = temp;Graduate Course on Embedded Control Systems Pisa 8-12 June2009 Implementation of Division in C with Rounding#include < >/* define int8_t, etc. (Linux only)*/#define n 3/* number of fractional bits*/int8_t X, Y, Z;/* operands and result*/int16_t temp;/* intermediate result*/.