Embedded C Bewegende Gemiddelde

Verbeter jou wortel-gemiddelde berekeninge Brian NeunaberFebruary 16, 2006 Real-time digitale stelsels vereis dikwels die berekening van 'n wortel-gemiddelde, soos 'n wortel-gemiddelde vierkante (RMS) vlak of gemiddelde grootte van 'n komplekse sein. Terwyl gemiddelde doeltreffend deur die meeste mikroverwerkers geïmplementeer kan word, kan die vierkantswortel nie - veral met 'n lae-koste hardeware. As die verwerker 'n vinnige vierkantswortelfunksie nie implementeer, moet dit in sagteware geïmplementeer; Alhoewel hierdie akkurate resultate lewer, kan dit nie doeltreffend wees. Een algemene metode vir die berekening van die vierkantswortel is Newton se metode, wat iteratief konvergeer op 'n oplossing met behulp van 'n aanvanklike skatting. Sedert ons die berekening van die vierkantswortel van 'n stadig wisselende gemiddelde waarde, die vorige wortel-gemiddelde waarde maak 'n goeie skatting. Verder kan ons die iteratiewe Newton se metode kombineer met 'n eerste-orde rekursiewe Averager, wat lei tot 'n super-doeltreffende metode vir die berekening van die wortel-gemiddelde van 'n sein. In hierdie artikel, ek sal ontwikkel en aan te bied drie doeltreffende rekursiewe algoritmes vir die berekening van die wortel-gemiddelde, elke metode met seinvloeidiagramme en voorbeeld kode illustreer. Tot 'n mate, elk van hierdie metodes ambagte hardeware kompleksiteit vir foute. Ek sal die computational prestasie en dwaling van elke metode te vergelyk en stel geskikte hardeware vir elke implementering. Die wortel-gemiddelde word bereken as die vierkantswortel van die gemiddelde oor 'n tydperk van sy insette. Dit gemiddelde mag rekursiewe of nie-rekursiewe wees, en Ek sal kortliks kyk na die algemene geval vir beide. Nie-rekursiewe gemiddelde Die nie-rekursiewe gemiddelde, of bewegende gemiddelde. is die geweegde som van N insette: die huidige insette en N -1 vorige insette. In digitale filter terminologie, dit is 'n eindige impulsrespons genoem. of FIR filter: Die mees algemene gebruik van die bewegende gemiddelde stel gewoonlik die gewigte so dat 'n n = 1 / N. As ons hierdie gewigte teenoor tyd te stip, sou ons die "venster" van die insetsein wat gemiddeld op 'n gegewe tydstip te sien. Dit 1 / N venster staan ​​bekend as 'n reghoekige venster omdat sy vorm 'n N - per-1 / N reghoek. Daar is 'n truuk vir die berekening van die 1 / N gemiddelde sodat almal N monsters hoef nie geweeg en opgesom met elke uitset berekening. Sedert die gewigte verander nie, kan jy net voeg die nuutste geweegde insette en trek die n de geweegde insette van die vorige som: Terwyl hierdie tegniek is computationeel doeltreffende, dit verg stoor en omsendbrief-buffer bestuur van N monsters. Natuurlik is daar baie ander venster vorms wat algemeen gebruik word. Tipies, hierdie venster vorms lyk, of is 'n variasie van 'n verhoogde kosinus tussen - & pi; / 2 en & pi; / 2. Hierdie vensters gewig van die monsters in die sentrum meer as die monsters naby die kante. Oor die algemeen, moet jy net een van hierdie vensters wanneer daar 'n spesifieke behoefte te, soos die toepassing van 'n spesifieke filter om die sein. Die nadeel van hierdie vensters is dat rekenkundige kompleksiteit en stoor vereistes verhoog met N. rekursiewe gemiddelde Die rekursiewe gemiddelde is die geweegde som van die insette, N vorige insette, en M vorige uitsette: Die eenvoudigste van hierdie in terme van rekenkundige kompleksiteit en stoor (terwyl hy nog nuttig om) is die eerste-orde rekursiewe gemiddelde. In hierdie geval, is die gemiddelde bereken as die geweegde som van die huidige insette en die vorige uitset. Die eerste-orde rekursiewe gemiddelde leen hom ook tot 'n optimalisering wanneer dit gekombineer met die berekening van die vierkantswortel, wat ons binnekort sal bespreek. In teenstelling met die nie-rekursiewe gemiddeld venster die eerste-orde rekursiewe gemiddelde is 'n vervalle eksponensiële (Figuur 1). Tegnies, die rekursiewe gemiddelde het 'n oneindige venster, aangesien dit nooit verval al die pad na nul. In digitale filter terminologie, staan ​​dit bekend as 'n oneindige impulsrespons, of IIR filter. Uit Figuur 1, sien ons dat vroeër monsters meer word geweeg as later monsters, wat ons toelaat om 'n bietjie arbitrêr definieer 'n gemiddelde tyd vir die rekursiewe gemiddelde. Vir die eerste-orde geval, ons definieer die gemiddelde tyd en wyl die tydstip waarop die impulsrespons het verval tot 'n faktor van 1 / e. of ongeveer 37%, van sy aanvanklike waarde. 'N ekwivalente definisie is die tydstip waarop die stap reaksie bereik 1- (1 / e), of ongeveer 63%, van sy finale waarde. Ander definisies is moontlik, maar sal nie hier gedek word. Die gewig van die som bepaal hierdie gemiddelde tyd; om eenheid gewin te verseker, moet die som van die gewigte een gelyk. As 'n gevolg, net een koëffisiënt moet vermeld om die gemiddelde tyd beskryf. Daarom, vir eerste-orde rekursiewe gemiddelde, bereken ons die gemiddelde vlak as: waar x (N) is die insette, m (N) is die gemiddelde waarde, en 'n is die gemiddelde koëffisiënt. Die gemiddelde koëffisiënt word gedefinieer as: waar t die gemiddelde tyd, en f S is die monsterfrekwensie. Die wortel-gemiddelde kan dan bereken word deur die neem van die vierkantswortel van vergelyking 4: waar y (N) is die wortel-gemiddelde. Doeltreffende berekening metodes Googlen "vinnige vierkantswortel" sal jy 'n oorvloed van inligting en stukkies kode op die implementering van 'n vinnige vierkante-wortel algoritmes. Terwyl hierdie metodes net mooi kan werk, het hulle nie rekening hou met die aansoek waarin die vierkantswortel word vereis. Dikwels kan jy nie presies presisie moet die laaste bietjie, of die algoritme self gemanipuleer kan word om die berekening van die vierkantswortel optimaliseer. Ek bied 'n paar basiese benaderings hier. Slegs bereken wanneer jy dit nodig het Waarskynlik die maklikste optimalisering is om net te bereken die vierkantswortel wanneer jy absoluut nodig het. Alhoewel hierdie voor die hand liggend mag lyk, kan dit maklik misgekyk word wanneer die berekening van die wortel-gemiddelde van alle insette monster. As jy nie 'n uitset waarde vir elke insette monster moet, maak dit meer sin om net die vierkantswortel bereken wanneer jy die uitset waarde te lees. Een voorbeeld van 'n aansoek toe hierdie tegniek kan gebruik word is RMS meting van 'n sein. 'N Meter waarde wat visueel vertoon mag slegs 'n update elke 50 tot 100ms, wat veel minder dikwels as die insetsein word getoets kan word vereis. Hou in gedagte, maar dat rekursiewe gemiddelde moet nog bereken word op die Nyquist tempo. logaritmes Onthou dat: As jy sal die berekening van die logaritme van 'n vierkantswortel, dit is veel minder bestryk duur om net halveer die resultaat in plaas. 'N Algemene voorbeeld van hierdie optimalisering is die berekening van 'n WGK vlak in dB, wat soos volg kan vereenvoudig word: Newton se Metode Newton se metode (ook bekend as die Newton-Rapson Metode) is 'n bekende iteratiewe metode vir die beraming van die wortel van 'n vergelyking. 1 Newton se metode kan baie doeltreffend wees wanneer jy 'n redelike raming van die resultaat. Verder, as die akkuraatheid van die laaste bietjie nie vereis word nie, die aantal iterasies kan vasgestel word om die algoritme deterministiese hou. Ons kan die wortel van f (x) benader deur iteratief bereken: (9) As ons wil om uit te vind, dan moet ons die wortel vind om die vergelyking f (y) = y 2 - m. Vervang f (y) in vergelyking 9, kry ons: Herrangskik vergelyking 9, kry ons: waar y (N) is die aanpassing van die vierkantswortel van m (N). Vergelyking 11 vereis 'n kloof operasie, wat ongerieflik vir 'n paar verwerkers kan wees. As 'n alternatief, kan ons bereken en vermenigvuldig die resultaat met m te kry. Weer met Newton se metode, vind ons dat ons iteratief kan bereken die wedersydse vierkantswortel as: en bereken die vierkantswortel as: Hoewel Newton se Metode vir die wedersydse vierkantswortel elimineer die kloof operasie, kan dit problematies vir vaste punt verwerkers wees. buite die omvang van verteenwoordiging vir heelgetalle - die veronderstelling dat m (n) 'n positiewe heelgetal groter as 1, sal jr (N) 'n positiewe getal minder as een wees. Implementering vervul moet word: die gebruik van swaai-punt of gemengde heelgetal / fraksionele aantal verteenwoordiging. Wortel-gemiddelde gebruik van Newton se Metode 'N subtiele verskil tussen Vergelykings 10 en 11 is dat m raak m (N), wat beteken dat ons probeer om die vierkantswortel van 'n bewegende teiken te vind. Maar sedert m (N) is 'n gemiddelde waarde, of stadig wissel, kan dit as byna konstante tussen iterasies beskou. Sedert y (N) ook stadig wisselende sal wees, y (N -1) sal 'n goeie benadering om y (n) en vereis minder iterasies - een, ons hoop - 'n goeie raming bereik. Om die wortel-gemiddelde te bereken, kan 'n mens net van toepassing Newton se Metode vir die berekening van die vierkantswortel van die gemiddelde waarde. Solank as wat die gemiddelde tyd lank in vergelyking met die monster tydperk (t & 62; & 62; 1 / f S), moet 'n mens iterasie van die vierkantswortel berekening genoeg vir redelike akkuraatheid. Dit lyk eenvoudig genoeg, maar ons kan eintlik die computational doeltreffendheid, wat in een van die volgende afdelings bespreek sal word verbeter. Die gebruik van wedersydse vierkantswortel In teenstelling met die iteratiewe vierkante-wortel metode egter die iteratiewe wedersydse vierkante-wortel vereis geen kloof. Hierdie implementering is die beste geskik is vir swaai-punt verwerking, wat doeltreffend kan hanteer getalle beide groter en minder as een. Ons bied hierdie implementering as 'n sein vloeidiagram in Figuur 2. Die gemiddelde koëffisiënt, a. gedefinieer deur vergelyking 5 en Z -1 verteenwoordig 'n eenheid monster vertraging. 'N Kode lys vir 'n C ++ klas wat die berekening in Figuur 2 implemente word in Listing 1. In hierdie voorbeeld klas, is inisialisering uitgevoer in die klas konstruktor, en elke oproep om CalcRootMean () voer een iterasie van gemiddelde en vierkante-wortel berekening . Notering 1. C ++ klas wat die wortel-gemiddelde gebruik van Newton se Metode vir die wedersydse vierkantswortel bere Die gebruik van direkte vierkantswortel Kom ons gaan terug en neem 'n nader kyk na vergelyking 11. Newton se metode konvergeer op die oplossing so gou as moontlik sonder ossillerende rondom dit, maar as ons hierdie koers van konvergensie stadig, sal die iteratiewe vergelyking konvergeer op die vierkantswortel van die gemiddelde van sy insette. Die toevoeging van die gemiddelde koëffisiënt resultate in die volgende wortel-gemiddelde vergelyking: waar 'n gedefinieer deur vergelyking 5. Nou y (N) konvergeer na die vierkantswortel van die gemiddelde van x (N). 'N ekwivalente sein-vloei voorstelling van vergelyking 14 word in Figuur 3. Hier is 'n bykomende y (N -1) term word opgesom sodat slegs een gemiddelde koëffisiënt word vereis. Let daarop dat x (N) en y (N -1) moet groter as nul wees. 'N Kode lys vir 'n C ++ klas wat die berekening getoon in figuur 3 implemente word in Listing 2. Soos in die vorige voorbeeld, is inisialisering uitgevoer in die klas konstruktor, en elke oproep om CalcRootMean () voer een iterasie van gemiddelde / vierkant - wortel berekening. Aanbieding 2. C ++ klas wat die swaai-punt weergawe van figuur 3 implemente Met 'n bietjie sorg, figuur 3 kan ook in vaste punt rekenkundige geïmplementeer soos in Listing 3. In hierdie voorbeeld is skalering geïmplementeer om te verseker geldige resultate. Wanneer voldoende woord grootte teenwoordig is, is x afgeskaal deur nAvgCoeff voor afdeling om die akkuraatheid van die resultaat te maksimeer. Aanbieding 3. C ++ klas wat die vaste punt weergawe van figuur 3 implemente Verdeel-vrye RMS met behulp van normalisering Nou sal ons kyk na die spesiale geval van die berekening van 'n WGK waarde op vaste punt hardeware wat nie 'n vinnige kloof operasie, wat tipies is vir lae-koste ingesluit verwerkers het nie. Hoewel baie van hierdie verwerkers afdeling kan verrig, doen hulle dit 'n bietjie op 'n tyd, wat ten minste een siklus vir elke bietjie woordlengte. Verder moet sorg gedra word om te verseker dat die RMS berekening geïmplementeer met voldoende numeriese presisie. Met vaste punt hardeware, die vierkant van 'n waarde vereis twee keer die aantal bisse presisie die oorspronklike data se behou. Met dit in gedagte, manipuleer ons Vergelyking 14 in die volgende: Hoewel die uitdrukking x (n) 2 - y (N -1) 2 moet bereken word met 'n dubbele presisie, hierdie implementering leen hom tot 'n beduidende optimalisering. Let daarop dat 'n / 2 y (N -1) tree op soos 'n vlak-afhanklike gemiddelde koëffisiënt. As 'n effense tydafhanklike variansie in die gemiddelde tyd geduld kan word nie - dit is dikwels die geval - 1 / y (N -1) erg kan benader. Op 'n swaai-punt verwerker, die verskuiwing van die gemiddelde koëffisiënt na links deur die negatiewe van die eksponent by benadering die kloof werking. Hierdie proses word algemeen na verwys as normalisering. Sommige vaste punt ADVs kan normalisering verrig deur die tel van die voorste stukkies van die akkumulator en die verskuiwing van die akkumulator deur dat die getal bisse. 2 In beide gevalle, sal die gemiddelde koëffisiënt word afgekap om die naaste krag van twee, sodat die koëffisiënt moet vermenigvuldig word met 3/2 die resultaat te rond. Dit implementering word in vergelyking 16. Figuur 4 is die sein-vloeidiagram wat Vergelyking 16. verteenwoordig Net soos in figuur 3, x (N) en y (N -1) moet groter as nul wees. 'N Monster-kode aanbieding wat implemente Figuur 4 word in Listing 4. Hierdie implementering vergadering-taal is vir die Freescale (voorheen Motorola) DSP563xx 24-bit vaste punt verwerker. Notering 4. Freescale DSP563xx vergadering implementering van verdeel-vrye RMS met behulp van normalisering Natuurlik, kan hierdie metode toegepas word, selfs sonder 'n vinnige normalisering. Jy kan 'n lus implementeer om x (n) 2 skuif - y (N -1) 2 aan die linkerkant vir elke voorste bietjie in y (N -1). Dit sal stadiger wees, maar geïmplementeer kan word met selfs die eenvoudigste van verwerkers. Hoërorde Berekening van gemiddelde Hoër orde rekursiewe gemiddelde kan bereik word deur die invoeging van addisionele gemiddelde filters voor die iteratiewe vierkantswortel. Hierdie filters kan net een of meer kaskade eerste-orde rekursiewe afdelings. Eerste-orde artikels het die voordeel van die vervaardiging geen oorskiet in die stap reaksie. Daarbenewens is daar is net een koëffisiënt te pas en kwantisering effekte (in die eerste plek van kommer vir vaste punt implementering) is veel minder as dié van hoër-orde filters. Die implementeerder moet bewus wees dat die waterval eerste-orde artikels verander die definisie van 'n gemiddelde tyd. 'N eenvoudige, maar bruto benadering wat die vorige definisie van stap reaksie handhaaf is om eenvoudig te verdeel die gemiddelde tyd van elke eerste-orde artikel deur die totale aantal afdelings. Dit is egter die verantwoordelikheid van die implementeerder se om te bevestig dat hierdie benadering is geskik vir die toepassing. Tweede-orde artikels kan ook gebruik word, as jy wil (byvoorbeeld) 'n Bessel-Thomson filter reaksie. As tweede-orde artikels word gebruik, is dit die beste om 'n vreemde-orde saamgestelde reaksie kies sedert die gemiddelde vierkante-wortel filter by benadering die finale eerste-orde filter met Q = 0,5. Sorg moet gedra word om die oorskiet van hierdie gemiddelde filter verminder. die gemiddelde tyd van die filter in real-time aanpassing sal bewys moeiliker, want daar is 'n aantal koëffisiënte wat in harmonie moet aangepas word om stabiliteit te verseker. Drie metodes van die berekening van die RMS vlak met mekaar vergelyk word in Figuur 5. Die gemiddelde tyd is ingestel op 100ms en die insette is 'n sekonde van 1 / f geraas met 'n 48kHz monsterfrekwensie. Die eerste spoor is die ware WGK waarde bereken word deur vergelyking 6. Die tweede spoor is die RMS berekening met behulp van vergelyking 14. Die derde spoor is die nie-kloof berekening van vergelyking 16. Die vierde spoor is die WGK waarde met behulp van die wedersydse vierkante-wortel metode van vergelyking 13. Vir die grootste deel, die vier spore line-up mooi. Al vier benaderings blyk te konvergeer teen dieselfde tempo as die ware WGK waarde. Soos verwag, het die grootste afwyking van die ware WGK waarde is die aanpassing van die vergelyking 16. Dit benadering sal die grootste fout tydens groot veranderinge in die vlak van die insetsein het, hoewel hierdie fout tydelike is: die optimale benadering sal konvergeer op die ware WGK waarde wanneer die vlak van die insetsein konstant. Die foute tussen die drie benaderings en die ware WGK waarde word in Figuur 6. Die fout van die RMS benadering met behulp van vergelyking 14 stadig afneem totdat dit onder 1A-7, wat voldoende is vir 24-bis akkuraatheid. Die optimale aanpassing van vergelyking 16 is aansienlik erger, omstreeks 1A-4, maar nog steeds goed genoeg vir baie toepassings. Die benadering wat die wedersydse vierkantswortel gebruik is "in die geraas" - minder as 1A-9. Vir baie krities swaai-punt aansoeke, dit is die doeltreffende metode van keuse. Soos jy sou verwag, sal die foute wat hierbo bespreek is erger met korter gemiddelde tye en beter met langer gemiddeld tye. Tabel 1 gee 'n opsomming van die geskatte fout teenoor gemiddeld tyd van hierdie drie metodes, saam met 'n geskikte hardeware argitektuur vereistes. Geskik vir die gemiddelde leser Deur die kombinasie van rekursiewe gemiddelde met Newton se metode vir die berekening van die vierkantswortel, sal jy 'n baie doeltreffende metode te verkry vir die berekening van die wortel-gemiddelde. Hoewel die drie metodes ek hier aangebied word ontwikkel vir verskillende hardeware en elk, tot 'n mate, handel dryf af hardeware vermoëns vir foute, moet die meeste van julle een van hierdie metodes wat geskik is vir jou aansoek te vind. Brian Neunaber is tans digitale stelsels argitek van sagteware en firmware op QSC klank produkte. Hy het real-time digitale klank algoritmes en stelsels wat ontwerp is vir QSC en St Louis Musiek en het 'n MSEE van Suider-Illinois University. Jy kan hom kontak by brian_neunaber@qscaudio. com. 1. D. G. Zill. Calculus met Analitiese Meetkunde, 2nd ed. . PWS-Kent, Boston, pp. 170-176, 1988. 2. Motorola. DSP56300 Familie Handleiding, ds 3, Motorola literatuur verspreiding, Denver, 2000. leser Response In 1996, 'n artikel in dr Dobbs tydskrif het 'n vierkantswortel algoritme wat net skofte gebruik en voeg - geen vermeerder en beslis nie verdeel. Dit kan hier gevind word: www. ddj. com/documents/s=962/ddj9604l/ (registrasie vereis). Ek het al met behulp van hierdie in elke werk en elke projek sedertdien - dit is by verre die vinnigste heelgetal vierkantswortel rondom, en Ek is verbaas dat dit nog so bietjie bekend staan. Probeer dit - materieel nooit terugkyk!