Løsning af et 50 år gammelt puslespil inden for signalbehandling, del to

Iowa State Universitys Alexander Stoytchev siger, at det er en af ​​de "mest populære og nyttige" algoritmer, der findes - selvom de fleste af os aldrig har hørt om det.

Men, hvis du har brugt en mobiltelefon, surfede på internettet eller havde brug for et medicinsk billede, du har nydt godt af den hurtige Fourier-transformation (FFT).

Transformationen og dens inverse (kendt som IFFT) har været i brug siden 1965. F.eks. i din mobiltelefon bruges FFT til at analysere signalet modtaget fra basestationen (eller mobiltårnet). IFFT løser det omvendte problem:det syntetiserer det signal, som din telefon sender til basestationen.

I 1969, forskere udviklet en mere nyttig, generaliseret version af FFT kendt som chirp z-transformen (CZT). Men ingen var kommet med en generaliseret version af IFFT. Det var et 50 år gammelt puslespil inden for signalbehandling.

Det er, indtil sidste efterår, da to Iowa State-ingeniører - Stoytchev og Vladimir Sukhoy - annoncerede i et forskningspapir, at de var kommet med en lukket-form løsning til den inverse chirp z-transform (ICZT) og en hurtig algoritme til at beregne den. (Avisen vakte stor interesse i signalbehandlingssamfundet, tal mere end 26, 000 adgange siden oktober.)

Nu rapporterer Stoytchev – en lektor i elektro- og computerteknik, som også er tilknyttet universitetets Virtual Reality Applications Center – og Sukhoy – en underviser i elektro- og computerteknik – nye forskningsresultater om deres algoritme.

I et papir, der netop er udgivet online af Videnskabelige rapporter , et Nature Research tidsskrift, de to viser, hvordan deres algoritme fungerer "på enhedscirklen, " som refererer til et særligt tilfælde af dets parametre. (Deres tidligere papir fremhævede kun operationer "uden for enhedscirklen").

Papiret beskriver, hvordan algoritmen kan arbejde med frekvenskomponenter, der genereres af prøvepunkter fra enhedscirklen i det komplekse plan. Disse punkter danner en kontur, der er kendt som chirp-konturen. I modsætning til IFFT, som kun kan arbejde med prøveudtagningspunkter med lige store afstande, der fuldt ud dækker enhedscirklen, ICZT-algoritmen kan arbejde med konturer, der kun dækker en brøkdel af enhedscirklen. Den kan også arbejde med konturer, der vikler sig rundt og udfører flere omdrejninger over cirklen. Dette muliggør brugen af ​​visse (ikke-ortogonale) frekvenskomponenter, som ophæver en af ​​IFFT's vigtigste restriktioner og kan føre til bedre frekvensudnyttelse.

Papiret identificerer de parameterværdier, som algoritmen er numerisk nøjagtig for, og som den ikke er for, og beskriver, hvordan man estimerer dens nøjagtighed som funktion af parametrene. (Teknisk note:Den viser, at singulariteterne af ICZT af størrelse n er relateret til elementerne i Farey-sekvensen af ​​orden n-1. Dette er en interessant sammenhæng, fordi Farey-sekvenser ofte optræder i talteorien.)

Avisen viser, at på enhedscirklen, ICZT-algoritmen opnår høj nøjagtighed med kun 64-bit flydende kommatal og kræver ikke yderligere numerisk præcision, gør det nemmere at implementere. Det rapporterer, at algoritmen godt kan parres med den eksisterende CZT-algoritme for at udføre back-to-back signalanalyse og signalsyntese. Og det viser, at algoritmen er hurtig (den fungerer i det, der er kendt som O(n log n) tid).

"Denne algoritme er mere generel end IFFT, men holder samme hastighed, " sagde Stoytchev.

Det er gode nyheder for de ingeniører, der arbejder på at løse alle former for signalbehandlingsudfordringer:

"Applikationsdomæner, der kunne drage fordel af dette, "Skrev Iowa State-ingeniørerne i avisen, "inkluder signalbehandling, elektronik, medicinsk billeddannelse, radar, sonar, trådløs kommunikation, og andre."