GPS är ett av de mest använda trådlösa systemen. En GPS-mottagare måste låsa satellitsignalerna för att beräkna sin position. Processen att låsa på satelliterna är ganska kostsam och kräver hundratals miljoner hårdvarumultiplikationer, vilket leder till hög strömförbrukning. Den snabbaste kända algoritmen för detta problem är baserad på Fouriertransform och har en komplexitet av O(n log n), där n är antalet signalprov. Detta dokument presenterar den snabbaste GPS-låsningsalgoritmen hittills. Algoritmen minskar låsets komplexitet till O(n ε log n). Om SNR överstiger ett tröskelvärde blir algoritmen dessutom linjär, dvs. O(n). Vår algoritm bygger på den senaste utvecklingen inom det växande området av sparsam återhämtning. Den utnyttjar synkroniseringsproblemets glesa natur, där endast den korrekta anpassningen mellan den mottagna GPS-signalen och satellitkoden gör att deras korskorrelering ökar. Vi visar vidare att den teoretiska vinsten leder till empiriska vinster för GPS-mottagare. Speciellt byggde vi en prototyp av designen med programvaruradio och testade den på två GPS-dataset som samlats in i USA och Europa. Resultaten visar att den nya algoritmen minskar medianantalet multiplikationer med 2,2× i jämförelse med toppmodern design, för verkliga GPS-signaler.
Hassanieh REF presenterar en gles Fourier Transform för att minska komplexiteten från O(n log n) till O(n) log n).
Faster GPS via the sparse fourier transform
{'venue': "Mobicom '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}