在小型嵌入式系统查找表优化传感器线性 Lookup Table Optimization for Sen.doc

在小型嵌入式系统查找表优化传感器线性 Lookup Table Optimization for Sen Lookup TableOptimization for Sensor Linearizationin SmallEmbedded SystemsLars E.Bengtsson PhysicsDepartment,University ofGothenburg,Gothenburg,Sweden Email:lars.bengtssonphysics.gu.se ReceivedOctober5,xx;revised November6,xx;aepted December6,xxABSTRACT Thispaper treatsthe problemof designingan optimalsize for a lookup table used for sensorlinearization.In smallem-bedded systemsthe lookup table must be reduced to a minimum in order to reduce the memory footprintand intermedi-ate tablevalues areestimated bylinear interpolation.Since interpolationintroduces anestimation uncertainty that in-creases withthe sparsenessof the lookup tablethere is a trade-off betweenlookuptablesize andestimation precision.This workwill presenta theory for findingthe minimumallowed size of alookuptablethat doesnot affect the overall precision,i.e.the overallprecision is determined by thelookuptable entriesprecision,not by the interpolation error.Keywords:Lookup Table;Sensor Linearization;Embedded Systems;Interpolation1.IntroductionLook-up tables(LUTs)are usedin awide varietyof puterand embeddedapplications;NASA useit toimprove the pointing precision of antennas1,CERN usesLUTs tocalibrate thebeam energyacquisition sys-tem of the LargeHadron Collider(LHC)2and it is oneof the most monmethods fordigital synthesis of ar-bitrary waveforms3.It isused extensively in numerialculations,for examplein divisionalgorithms4,square rootalgorithms5and evenfor fast evaluation ofgeneral functions6,7.In DataAcquisition Systems(DAQ)it isused tocorrect non-linearities andoffset errors in Analog-to-Digital Converters(ADCs)8-10or todesign non-uniform ADCs11.This workwill focusmainly on LUT applications in EmbeddedMeasurement Systems(EMS);linearizing sensor signal outputsis oneof themajor applicationsof LUTs12-18.A sensorconverts thephysical unit(the measurand)into someelectrical unit(preferably volt)and theem-bedded measurement system convertsthe sensoroutput into a digitalvalue(typically aninteger)19.The mainerrors inmost measurementsystems arerelated tothe transducers offset,gain andnon-linearities20,and forthat reason the process of sensorlinearization is a crucialstep in the designof anembedded measurementsystem21.The linearization process mustpensate for the non-linear relationship between the sensors inputand theoutput signals21,see Figure1.If the relationship between thesensors inputand its(digitalized)output y,is given by the non-linear functionf,i.e.y=f(x),then therelationshipbetween the lineari-zing blocks inputy and its outputz should be1f?22,i.e.?1z f y?,so that?11z fy f f xx? (1)Many DAQsand EMSsuse floating-point orfixed-point controllersthat canhandle real-numbers withoutany significantoverhead penalty23.However,in smaller,8-bit integersystems,the mainconcern is not necessarilyto reproducethe inputsignal exactly;they arededicated to linearizing the signal andany parameterestimations areperformed off-line in the hostputer.In thesecases,expression (1)changes toz kx? (2)where kis in general a real constanttransferring thein-teger xinto to arealnumber estimateof themeasurand.Consequently,these systemswork withintegers onlyand apartfrom generatingfaster putations,they alsotypically reduce the memory footprint of the LUTsince integersare storedin bytesor words(8or16bits)while real-numbers are stored as“floats”or“doubles”(24or32bits).Even if we woulduse alarger,32-bit systemwith areal-number putationalengine,and perhapsalso lotsof non-volatile memory for LUTstorage,it isstill important to keep the LUT size toa minimumsince eventhemostadvanced32-bit systemshave alimited size of cache memory;LUT sizesshould besmall enoughto fitinto level1cache sincea memoryfetch from level1cache rendera maximumpenalty oftwo lockcycles whilea fetchfromlevel2cache mayneed cCopyright?xxSciRes.JST L.E.BENGTSSON178Figure1.The linearizationprocess.as muchas15clock cycles24.Several otherlinearization methodshave beensug-gested inliterature.The mostmon linearizationme-thods can be classifiedas follows21,25,26:1)Analog hardware-based;2)Software-based;3)Analog hard-ware-software mixedapproach.Analog hardware-only solutions are frequentlyused27,28but the disadvantage is that theextra analog-ponents necessary increase bothcost andpower con-sumption and also,due toinherent variationsin thema-nufacturing processparameters,each sensoris likelyto needindividual trimmingand tailoredpensation29,30and thatmay beplicated(and expensive)in ana-log hardware-only solutions.Some sensorsare alsosen-sitive tosecondary parameters(typically temperature)31-34and this may bevery hardto pensatefor inhardware-only solutions.(The dependence on secondaryparameters issometimes referred to ascross-sensitivity22).However,for non-digital measurementsystems thesesolutionsareimportant andcould alsobe consi-dered fordigital measurementsystems with limited me-mory and/or limitedputing power27,28,34,35.This work is concerned with software-based solutions only,or rather,firmware-based solutions,since itfocuses onlin-earizing byusing embeddedcontrollers.The rest of thiswork isorganized asfollows;Section2presents somebasic theoryconcerning linearzingwith LUTsand interpolation.Section3presents thehypothe-sisofwhich thiswork isbased uponand Section4de-scribes the methods usedto verifythe hypothesis.Sec-tion5presents someresults and they arediscussed in Section6.The workis summarizedinSection7with someconclusions.2.Theory2.1.Linearization Theprocessofdesigning the linearization blockin Fig-ure1is typicallya multi-step process.First ofall the non-linear functionf,relating thesensor inputand output,Typically,this isdone by a calibrationprocess wherea is in generalnot knownand needsto bedetermined.have foundf,we cansolve for the inversefunumber ofx,y-pairs areregistered experimentallyand fisdeterminedby off-line curvefitting(using theMATLAB mandspolyfit()or nlinfit().This isillustrated in Figure2.Once wenction1f?that we need to implement intothelin-earizing binFigure1.There arebasically twodif-ferent waystoimplement1lockf?;if yourembedded mea-surementsystemhas aess32-bit floating-point pro-cessing(with hardwaremultiplication),then to?1z fy?canbecalculated inreal-time.In smallemb systemswithlimitedputational power,1edded8-bitf?is typi-cally implementedas a LUT inflash mem.In thiscase weassume thaty is then-bit integerproduced by the ADCand thisinteger issimply usedas apointer tothememorylocation where?1oryf y?is stored,see Figure3.(Notice thatFigure3ind hatthe resolution of thez-output(=m)ingeneraldiffers fromthe resolutionof they-input(=n).The disadvantaicatest?1fy?omplexge of the firstmethod,when iscalculated inreal-time,is thatit requiresa c(and expensive)floating-point orfixed-point processor.The advantageis thatit doesnot requiremuch program memory;only the function parameters for the1f?func-tion needsto bestored(=p+1parametersfora nomialof orderp).The advantageof the LUT methodis thatit canbe implementedeven inthe simplestcontroller butthedisadvantageis thatit oupiesa lotof program me-mory.So,the choicebetweenthetwo methodsisatrade-off betweenthe need for signal processing powerand memory space oupancy.Since memoryspace istypi-cally lessexpensive thana floating-point processingen-gine,aLUTis thedominating linearity method.However,a bination of theuse ofa(sparse)LUT andsome non-plex integersignal processingmay reducethe demandfor LUTspace andstill meetthe real-time dead-lines.The“non-plex integersignalprocessing”is typicallylimited tolinear interpolationin order tore-trieve the“missing”LUT elements.This workis con-cernedwiththe detailsof thisprocess and the questionpolyCopyright?xxSciRes.JST L.E.BENGTSSON179Figure2.Finding fby curvefitting.Figure3.Linearizing byLUT.fthenecessary precision of the LUT elementsand/orthe2.2Interpolation willassume that we need tolin-te LUTwT maybe implementedand thenwe can use interpolationto rene,themethodis referredtoomaximal sparsenessof the LUT entries.In the following weearize asensor signalusing a small embedded system,i.e.thenon-linear sensorsignal isdigitalized byan n-bit ADCand weare lookingforafirmware algorithmthat linearizes thesignalaording toexpression (2).The factthat we use a“small”(and inexpensive)system,indicates thatmemory isscarce and that theprocessing poweris limited;all signalprocessing will be onintegers.If theresolutionof the ADCisnbits,a pleouldoupy2n memorylocations.For example,a12-bit ADCwould need4kbyte of program memoryif weset-tle for“byte”resolution andtwice asmuch ifwe want“word”resolution.This isby nomeans aninsignificant amountofprogrammemoryfora generalpurpose micro-controller.For example,the PIC18F458RISC controllerfrom Microchiphas aflash memoryof32kbyte36.In order to savesome programmemory,a sparserLUtrieve intermediatevalues20.Considering ourassumed limitedputation capability,linear interpolationistheobvious choice,see Figure4.Since weapproximate eachinterval betweenLUT en-tries with a differentstraight lias Piece-wise LinearInterpolation(PwLI)37and thebination ofa sparseLUT andPwLI isreferredtoas polygoninterpolation32,33.Assume thaty isthe integeroutput froman n-bit ADCand that we use1f?to mapeach ytoa(linearized)z;thi iiswould require2nLUT entries.Since thiswould oc-cupy toomuch moryspacewe needto decimate the LUTtable and the decimation factor should be aneven multipleof2(in orderto simplifyinteger divisionlater).If thedecimation factoris2empn(np (3)ymrepresents themeasured(digital)value,thepointestimator ofour measurement.From Figure5wand z m isecan see thatthe errorof thisestimation(the remain-der term)is?1? (4)m mR yfy zmIn general,the remainder term ofproximation isgivenby38a firstorder ap-?12!mm i miR y y y y y? (5)3.Hypothesis lybe twocontributions tothe uncer-ationofx:the interpolationerror1f?There willbasicaltainty of the finalestimrepresented byexpression (5)and the precision teof the LUT entries themselves(truncation orrounding errors).The totaluncertainty of the estimationwillbepropor-tional tothe squareroot of the sumof thesquares:?22Uncertaintym eRyt? (6)We willassume thatwe workwith intethatLUT entries are storedeither as8-bit bytesor as16gers onlyand-bit words.That meansthat?te?is8323.90610? (7)16521.5210? (8)for the8-and16-bit cases,respectively.Our goalhere is to reducethe LUrallauracy ofthT size toaminimum(by decimation)without reducingthe oveeestimation.Aording toexpression (6)that meansthatwe have tomonitor the size of the remainder term andincrease thedecimation factorfor aslong as?m eRyt?39.Hence,we needto knowthe maximalvalue of there-maindertermnsider expressions (4)and (5).A in (5).Coording toexpression (4)the remainder term isthe differencebetweenthe linear interpolationzm and“true”function value?1mf y?.If weassume1f?to bea smoothcontinuous function,the maximumerror mustour where thefs curvinessismmum andthis agreeswith expression (5);the second derivative of1unction axif?represents the curviness.Hence,weneedto find the maximalvalue of?1mim iy y y y?inthesegment ofaximal curviness.First ofall weap derivative:mproximate the second?2121df122df? (9)We findthe maximum of thesecond ptingthe firstderivative equal to zero:f yyy?art in (5)by set-?1ddm im imy y y yy?21111ddxxmmi i i immi imi iyyyyyyyy yyy yy? (10)Hence,the maximumvalue of?1mim iyyyy?is?111122111222211221144i i i ii ii ii ii iyyyyyyy yyyyyy? (11)Inserting (11)and (9)into (5)gives us111?21max8mRyf?1 (12)Expression (12)shouldbecalculatedthe functioninthesegment of1f?dalsolikthat hasthe greatestcurviness.We wouletobe ableto calculatethe remain-Copyright?xxSciRes.JST L.E.BENGTSSON181de1.? (13)Hence,we canestimate the maximumoftterm fromthe LUT entries bythe followingexpression:rtermfrom data.Suppose we have implementedthe LUTin TableWecan see that?111112iiiiiiiii iz z zzz zz?2111fff?he remainder?11maxmax128mii iRy zzz? (14)4.Methods We will illustratethe ideassuggested abovewith acase linearizea thermistorwhose resistancetemperature asfollows40:study.We willdepends onthe2511exp298TR RT?wherethe temperature TisinKelvinK.Ina positivetemperature coefficientand tosignal,we use the simplesignal conditioningcircuit in? (15)orderto get geta voltageFigure6.This willproduce avoltage U(T)equalto?1U T111exp?298refUT? (16)and the ADC willproduce aninteger Naording to?212111exp298nrefUnU TNTfT? (17)We getthe inverse,linearizing functionby solvingfor T:?11KnT fN? (18)121ln1298N?In ordertogetsome numbersto workwith,assign?a typicalvalue of3000K40.Wewillalso assumethatweuse a16-bit ADC.Hence,expression (18)is we will?111655361T fN? (19)ln13000298N?Table1.Implemented LUT(y,z).y z=f1(y)?f1?2f1R TR25U refU refU(t)=x n-bit AD=y Figure6.Signal conditioningfor non-linear thermistor.Ideally,we shouldstore oneLUT valuefor eachvaluein thedomain ofN(0.65535),but wewant tosave me-r-mteory spaceand decimatethis table;we willestimate inmediatevalues bylinearinterpolation.Aording to (5),the interpolationerror isproportional tothesecond derivative ofexpression (19).The second derivative cor-responds tothe“curviness”of thefunction andsince weare lookingfor thesize of the maximuminterpolationerror,wewillfocus onthe segmentsof1f?that hasthe greatestcurviness.Also,we canestimate thesecondde-rivative fromdata byusing expression (13).In Figure7wehaveplotted bothexpression (19)and thesecondde-rivative fromexpression (13).As expected,themaximumofthesecond derivativeours atthe pointsof maximumcurviness.In Figure7wehaveonly plottedthetemperaturefor Nranging from13,602to57,889;this correspondsto anassumed temperaturerange of10?C to+100?C.5.rviness,and hencethe maximal interpolation errors,ours atthe Empiri/Results FromFigure7we canseethatthe maximalcuupper endofthe1f?function.Hence,we onlyneedtocalculate expression (12)forthelast Nvalues inordertofindthe maximalinterpolationerror forany decimationfactor.Table2lists thevalues ofthemaximalremaindertermfor differentdegrees ofdecimation.The remainderterm Copyright?xxSciRes.JST L.E.BENGTSSON Copyright?xxSciRes.JST182Figure7.The functionf1anditssecondderivative.Table2.Maximal remainderterm vsr.LUT decimationfac-toDecimation factorMaximal remainder11.289610725.15531042.059710688.2191106163.2720105321.2965104645.08101041282.00211032567.30081037was calculatom expressions (12)ble2shouldbepared tothe bytensinexpressions (7)and (8).ed frand (13).6.Discussion Thevalues inTaand wordprecisioIf weusetherestraint that?m eRyt?,we cansee fromTable2and expression (7)that ifwe storeLUTenuse a16-bit interpolation.If westore the LUT valuesas16-bit words,2and expression (8)that adeci-mationfactorof8will notaffectthe overallprecision.g anrsin everydigital systemthat rongor inaurateLUT entriesmay nctions.As amatter offact,it wasa linearinter-poLUT sizemustbereducedtoaminimuminorderto we canseefrom Tabletriesin8-bit byteformat and ADC,we candecimatetheLUT bya factorof64without reducingtheoverallprecision;the precisionofthemeasurement esti-mate isstill determinedbytheprecisionofthe stored LUT entries,not bythe errorsintroduced bythelinearFor the8-bit case,we reducethesizeoftheLUT from65kbyte toonly1kbyte which isasignificant(and ab-solutely necessary)reduction oftheLUT memoryfoot-print in asmall embeddedsystem.Of the16-bit integerproduced bytheADC,weuse10bits for LUT indexind6bits for(piece-wise)linearinterpolation.This isillustrated inFigure8.7.Conclusions LUTsare usedinavast varietyof applications1-18andtheprecisionofLUTentriesandthesizeoftheLUTare crucialdesign factorelieson LUTs.Wcause seriousmalfuLUT errorthat causedthe infamousmalfunction ofIn-tels Pentiumprocessor inthe mid90s41.This workhas suggesteda methodfor findingan op-timal LUT size whenlinearizing sensoroutputs in smallembedded systems.The ideaistouse someofthe(most significant)bits fromthe quantizerforLUTindex ingandtherestofthe(least significant)bits forlation.The allocationof bitsfor indexingand interpo-lation,respectively,dependsontheprecisionofthestoredLUTvalues.Since interpolationinherently introducesan errordue tothecurvinessofthemapped function,itisimportanttokeeptheLUTsizelarge enoughto makethe interpolationerrors insignificant.On theother hand,theL.E.BENGTSSON18310bits Usb15b14b13b12b11b10b8b7b6b5b4b3b2b1b0edforLUT indexing6bits Usedfor PwLIb916-bit ADC,y:Figure8.LUT indexingand piece-wise linearinterpolation.minimize theLUTmemoryfootprint,whichisabsolutely crucialinsmallembeddedsystems.This workhas pre-sented atheory forfinding themonstratedits usebyacase study.the originalsamvae optimalLUTsizeand dTheworkislimited tothe casewere LUTentriesarestored asintegers sincethis istypically thecase insmall(8-bit)microcontrollers;the controllerlinearizesthesen-sorsignalonly,it doesnot estimateple lue.We haveargued thatthe interpolationerror shouldbe muchless thantheprecisionoftheLUTentries.If theLUTentriesarestoredwith mbits resolutionwecanes-timate theirprecision tobe2mandifweuse expressions (12)and (13)to estimatethe interpolationerror,we getthefollowinggeneral conditionfor determiningtheLUTsize:11max1228mi iiz zz? (20)REFERENCES1W.Gawronski,F.Baher andE.Gama,“Track-Level-Compensation Look-Up TableImproves AntennaPoitingPrecision,”20ipnpr.jpl rt/42-164/164E.pdf eamDumping System”,The10th In-Vol.178,xx,pp.12-15.06.nasa/progress_repo2R.A.Barlow,P.Bobbio,E.Carlier,G.Gr?wer,N.Vou-mard andR.Gjelsvik,“The BeamEnergy TrackingSys-tem ofthe LHCBternational Conferenceson Aelerators&Large Expe-riment PhysicsControl Systems,Geneva,10-14October,xx,p.02.056-4.3P.Gaydecki,