Show HN: Projekt zum Bau eines GPS-Empfängers
(axleos.com)- gypsum ist ein Projekt zum Bau eines Empfängers, der GPS-Signale von Grund auf dekodiert, um eine Position zu bestimmen; Teil 1 der vierteiligen Reihe konzentriert sich darauf, unter Rauschen verborgene Satellitensignale zu finden
- GPS ist ein Broadcast-Signal, das von rund 30 Satelliten weltweit ausgesendet wird; die Satelliten wissen daher nicht, wer zuhört, und ein Rechenzentrum kann den Funkempfang der Nutzer nicht übernehmen
- Wenn GPS-Signale eine Bodenantenne erreichen, kann ihre Leistung 100.000-mal geringer sein als das Umgebungsrauschen und 100 Millionen Mal schwächer als ein typisches Mobilfunksignal, sodass sie direkt kaum sichtbar sind
- Der Empfänger vergleicht wiederholt den C/A-Code, den sowohl Satellit als auch Empfänger kennen, mittelt so zufälliges Rauschen heraus und findet das 50-bps-Datensignal auf dem 1-Mbps-PRN-Code
- Die Akquisition (acquisition) ist ein rechenintensiver Schritt, der pro Satellit PRN, ±5 kHz Doppler shift und Codephase gemeinsam durchsucht, um sichtbare Satelliten sowie grobe Zeitverzögerung und Relativgeschwindigkeit zu finden
Ein Projekt, das GPS-Signale direkt abhört
- gypsum ist ein Projekt für einen von Grund auf gebauten GPS-Empfänger
- Die vierteilige Reihe behandelt den Prozess, GPS-Signale zu dekodieren und daraus eine Position zu bestimmen; Teil 1 entspricht dem Schritt, Signale zu finden und Satelliten zu akquirieren
- GPS sendet mit rund 30 Satelliten Signale über die gesamte Erde; diese Signale sind unabhängig von Höhe oder Wetter ständig in der Umgebung vorhanden
- GPS begann 1978; zum Zeitpunkt der Erstellung des Artikels waren 45 Jahre vergangen
Leise Beacons und Positionsberechnung, die sich nicht durch Server ersetzen lässt
- Beim Senden ist das Signal eines GPS-Satelliten ungefähr so stark wie eine Haushaltsglühbirne, doch wenn es den Boden erreicht, ist es extrem schwach
- GPS funktioniert nahezu nach dem Prinzip send-and-forget: Der Satellit kann nicht wissen, wer zuhört
- FM-Radio und Broadcast-TV haben ähnliche Eigenschaften
- Wegen dieser Struktur ist es schwierig, den Zugang zu GPS selbst zu bepreisen
- Positionsberechnung passt nicht zu einer Architektur, bei der ein Webservice sie stellvertretend berechnet und ausliefert
- GPS erfordert, dass man die Funkwellen, die den Standort des Nutzers erreichen, direkt abhört
- Ein Rechenzentrum kann nicht stellvertretend die Funkwellen empfangen, die am Standort des Nutzers eintreffen
GPS-Frequenzen mit SDR erkunden
- Um GPS-Signale per Software zu empfangen und nachzuverarbeiten, braucht man einen abstimmbaren RF-Empfänger; dieses Gerät ist ein Software Defined Radio (SDR)
- Mit SDR++ wird das Spektrum erkundet
- Bei der Nutzung eines SDR sind einige Konzepte nötig
- bias tee: Die interne Schaltung des SDR versorgt die per SMA angeschlossene Antenne mit Gleichstrom. Das verwendete SDR war standardmäßig ausgeschaltet und musste manuell aktiviert werden
- automatic gain control (AGC): Eine Hardware-Schaltung oder Softwarefunktion, die schwache Signale verstärkt, um das Signal-Rausch-Verhältnis (SNR) der Empfangsdaten zu verbessern
- IQ samples: I steht für in-phase, Q für quadrature oder die imaginäre Komponente; sie ermöglichen Verarbeitung in Bezug auf Zeit, Amplitude und Polarität
- Ein SDR erzeugt bei der eingestellten Mittenfrequenz einen großen Spike
- Für Einsteiger kann es so aussehen, als gäbe es überall ein starkes Signal
- Man kann die Abstimmung leicht neben die Mittenfrequenz legen oder diesen Spike mit IQ correction in der Software reduzieren
Wie man ein unter Rauschen verborgenes Signal findet
- An einer Bodenantenne kommen GPS-Signale mit 100.000-mal geringerer Leistung an als die umgebende Energie und andere Signale
- GPS-Signale können bis zu 50 dB unter dem thermischen Rauschboden liegen
- Moderne GPS-Satelliten sind darauf ausgelegt, beim Empfänger Signale von etwa -130 dBm ankommen zu lassen
- In typischen Wohnumgebungen liegt der thermische Rauschboden im C/A-Band bei etwa -110 dBm
- Zum Vergleich: Mobilfunksignale liegen bei etwa -50 dBm und sind 100 Millionen Mal stärker als GPS-Signale
- Um solche unter dem Rauschen verborgenen Signale zu identifizieren und zu dekodieren, nutzt GPS Spread-Spectrum-Techniken
Mit C/A-Code und PRN ein unhörbares Signal hören
- GPS-Satelliten senden neben Daten, die der Empfänger nicht kennt, auch ein Signal, das sowohl Satellit als auch Empfänger kennen
- Dieses Signal heißt C/A code, PRN code oder chipping code und wird vom Satelliten 1.000-mal pro Sekunde wiederholt
- C/A steht für coarse acquisition
- Im ursprünglich militärisch gedachten GPS war der C/A-Code eine niedrig auflösende Stufe, um auf den präziseren P-Code einzurasten
- Heute bildet der C/A-Code die Grundlage der meisten zivilen GPS-Nutzung, während der P-Code weiterhin nur militärisch verfügbar ist
- Der Grund, warum zivile Empfänger den P-Code nicht nutzen können, ist, dass sie die Werte der Chipping Sequence nicht kennen
- Wäre die Formel zur Erzeugung des P-Codes öffentlich, könnte man mit derselben Technik wie beim C/A-Code darauf einrasten
- Der P-Code ist genauer, weil er mit einer höheren Chipping Rate arbeitet
- Der Empfänger summiert und vergleicht den erwarteten PRN wiederholt mit dem tatsächlich empfangenen Signal
- Zufälliges Rauschen mittelt sich mit der Zeit gegen 0 heraus
- Das PRN-Signal akkumuliert sich weiter und wird größer
- GPS verwendet code-division multiple access (CDMA), um mehrere Satelliten gleichzeitig zu verarbeiten
- Das eigentliche Datensignal wird in den PRN-Code eingebettet übertragen
- Der PRN-Code arbeitet mit 1 Mbps
- Das Datensignal wird mit den deutlich langsameren 50 bps übertragen
- Durch die niedrige Datenrate bleibt der PRN-Code über relativ lange Zeit ein stabiler Referenzsignal
Erzeugung des C/A-Codes pro Satellit
- Da es mehrere Satelliten gibt, muss der Empfänger wissen, welche Satelliten sichtbar sind
- Jeder GPS-Satellit besitzt einen eindeutigen und stabilen PRN-Code
- Dieser Code ist in der zivilen GPS-Spezifikation IS-GPS-200L in
Table 3-I (Code Phase Assignments)definiert - Online gibt es viele Materialien, die erklären, wie PRN-Codes erzeugt werden, aber nicht viele reproduzierbare Quellen, mit denen man vollständige PRN-Codes abgleichen kann
Akquisitionsphase: sichtbare Satelliten finden
- Ein GPS-Empfänger erzeugt Kopien der von jedem Satelliten ausgesendeten PRNs und sucht diese PRNs in den über die Antenne gesammelten Daten, um die am Himmel sichtbaren Satelliten zu finden
- Dieser Schritt ist die acquisition; Ziel ist es, auf die Satelliten über dem Nutzer einzurasten
- Der Empfänger nimmt einen kurzen Snapshot von etwa 1 Sekunde Antennendaten auf und berechnet die Korrelation (correlation) mit jedem replizierten PRN
- Wenn es eine starke Korrelation zwischen repliziertem PRN und tatsächlichen Daten gibt, weiß man, dass der Satellit dieses PRN von oben ein Signal sendet
- Das tatsächlich empfangene Signal unterscheidet sich vom idealen PRN
- GPS-Signale werden beim Durchqueren der Erdatmosphäre abgeschwächt
- Da sich Satelliten schnell bewegen, ist das empfangene Signal Doppler-verschoben
- Die Umlaufgeschwindigkeit von GPS-Satelliten ist gut bekannt, daher ist auch der erwartete Bereich des Doppler shift festgelegt
- Ein sich nähernder Satellit erzeugt eine Frequenzzunahme von bis zu +5 kHz
- Ein sich entfernender Satellit erzeugt eine Frequenzabnahme von -5 kHz
- Da der Zeitpunkt des Empfangsbeginns beliebig ist, kann man auch mitten in einer PRN-Übertragung zu hören beginnen
- Die Akquisitionsphase durchsucht gleichzeitig drei Achsen
- Den PRN-Code jedes Satelliten
- Den erwarteten Bereich des Doppler shift
- Die Phase, um die das replizierte PRN verschoben wird, damit es zum empfangenen PRN passt
- Der Rechenaufwand ist groß, doch wenn die richtigen Parameter gefunden sind, zeigt sich ein deutlicher Korrelations-Spike
Implementierung und Ergebnis von Teil 1
- Die Implementierung wandelt jedes PRN vom Zeitbereich in den Frequenzbereich um und korreliert die Frequenz der eingehenden Satellitendaten mit dem Spektrum jedes PRN-Codes
- Diese Methode entspricht Cross-Correlation im Frequenzbereich
- Ein Phasenoffset im Zeitbereich wird zu einer Verschiebung der Frequenzkomponenten; daher lassen sich Doppler-shift-Suche und Phasensuche in derselben Berechnung behandeln
- Der Doppler shift wird für jeden sichtbaren Satelliten in einem der Binary Search ähnlichen Verfahren auf den Wert konvergiert, bei dem der stärkste Korrelations-Spike auftritt
- Als Ergebnis von Teil 1 wird bestimmt, welche GPS-Satelliten sich aktuell über dem Nutzer befinden, und für jeden Satelliten werden eine grobe phase/time delay sowie ein grober Doppler shift/relative velocity erhalten
- Der nächste Schritt folgt in Part 2: Tracking Pinpricks
1 Kommentare
Hacker-News-Kommentare
Man kann Empfänger mit direktem RF-Sampling oder direkter RF-Umsetzung bekommen, die für GPS schnell genug sind. Beispiele: Xilinx RFSoc https://www.mouser.com/datasheet/2/903/ds889_zynq_usp_rfsoc_..., ein Artikel von National Instruments https://www.ni.com/en/solutions/aerospace-defense/radar-elec..., passende Standardhardware https://www.ni.com/en-us/shop/category/flexrio-custom-instru...
Etwas seltsam ist allerdings, dass NI direkte RF-Umsetzung als kosteneffizient betrachtet und die Geräte trotzdem für 30.000 Dollar verkauft. Wenn man aber breitbandigen Empfang mit Phasenkohärenz im Bereich um 3 GHz prototypisch aufbauen will und ein ordentliches Labor samt Budget hat, kann man durchaus ein paar davon kaufen. Für Serienfertigung würde ich eher darauf warten, dass die Kosten für ein eigenes Board weiter sinken, oder prüfen, ob ein traditioneller Heterodyn-Empfänger ausreicht
Wenn man sich im militärischen Kontext Sorgen über fortgeschrittene RF-verfolgende Waffen macht, kann ein Direktumsetzungsempfänger vorteilhaft sein. Es gibt nämlich keine Leckstrahlung des lokalen Oszillators, die gegnerische Ausrüstung erkennen könnte
Bei der Formulierung „from scratch“ fragt man sich natürlich, wie viel tatsächlich von Grund auf gemacht wurde, und als ich sah, dass die Hardware ein RTL-SDR ist, war ich etwas enttäuscht. Trotzdem ist die Protokolldekodierung sehr spannend und das Ergebnis hervorragend
GPS begann 1978, aber bis 2000 wurde das Signal absichtlich durch ein Verfahren namens „Selective Availability“ verschlechtert. Dadurch war GPS für viele Anwendungen praktisch nutzlos, für Straßennavigation definitiv ungeeignet und für Erkundungen in abgelegenen Gebieten oder für die Seefahrt nur eingeschränkt brauchbar
Dass gypsum aus einem Kaltstart schon mit weniger als einer Minute Antennensignal eine Position und die genaue Uhrzeit bestimmen kann, ist sehr beeindruckend und wirkt sogar besser als heutige kommerzielle Empfänger. Bei Autofahrten in den frühen 2000ern musste man vor der Abfahrt oft 15 bis 20 Minuten am Straßenrand warten, bis der GPS-Empfänger eine Position hatte, und wenn das nicht klappte, fuhr man eben mit Papierkarte los
Selbst 46 Jahre später ist die Funkschicht vollständig vorwärts- und rückwärtskompatibel, und wichtige Kennzahlen wie die Zeit bis zum ersten Fix und der User Equivalent Range Error wurden um das 10- bis 1000-Fache verbessert, ohne inkompatible Protokolländerungen
Die gesamte RF-Sendeleistung für den weltweiten Dienst ist kleiner als der Stromverbrauch eines typischen US-Haushalts, liegt weit unter 5G, TV oder AM/FM-Radio und sogar unter dem Rauschboden. Möglich wird das durch den Einsatz gestapelter Gold-Codes
Das System wurde sogar so entworfen, dass Frequenzteilung mit Konkurrenzsystemen wie Galileo möglich ist, was man bei Mobilfunknetzen kaum sieht. Die Phasen von Modulationsdaten und Träger sind fest gekoppelt, wodurch Dinge wie die Trägerphasendekodierung möglich werden und damit bessere Pseudostrecken und höhere Genauigkeit
Insgesamt hatten die Entwickler entweder enorm viel Weitblick, unglaublich viel Glück oder beides
Gemeint war hier, dass der Empfänger auf Hardware aufgebaut wurde, die nichts über GPS weiß, also auf einem Gerät, das nur elektromagnetische Felder sampeln kann
Der Grund für die lange Zeit bis zum ersten Fix bei älterer Hardware hing im Wesentlichen mit Fortschritten bei der Rechenleistung zusammen. Traditionelle GPS-Empfänger mussten den Almanach aller Satelliten herunterladen, und wegen Format und Datenrate der GPS-Übertragung dauerte das selbst unter guten Bedingungen mindestens 12,5 Minuten
Mit heutiger Rechenleistung können Empfänger, gypsum eingeschlossen, statt auf Hinweise aus der Luft zu warten den Suchraum per Brute Force durchsuchen und die sichtbaren Satelliten finden. Diese Technik wird am Ende von Teil 1 beschrieben
1999 habe ich die RS-232-Version eines Delorme Earthmate Hyperformance GPS-Empfängers an ein Toughbook angeschlossen und darauf etwa Delorme Street Atlas USA 6.0 für Autofahrten genutzt
Quer durchs ganze Land bot das eine durchaus brauchbare Navigation. Es gab keine Spurführung, aber vor jeder Abbiegung wurde die Anweisung inklusive Straßenname angesagt
Diese Version hatte sogar Spracherkennung: Wenn man etwas wie „Sind wir bald da?“ sagte, nannte sie die geschätzte Ankunftszeit bis zum nächsten Zwischenziel und bis zum Endziel sowie die aktuelle Position, was ziemlich unterhaltsam war
Wenn der typische schlechteste kreisförmige Fehler unter Selective Availability bei etwa 30 m lag, dann ist das für Straßennavigation außer in sehr dicht bebauten Gebieten genau genug. Selbst dort reichte ein kurzer Blick auf die Karte, und auf offenen Straßen funktionierte es hervorragend
Früher war die Zahl der Tracking-Kanäle bei GPS-Empfängern ein Marketingmerkmal, und günstige Empfänger hatten nur Hardware, um 6 bis 8 Satelliten zu verfolgen, während teurere 12 verfolgen konnten
Dieser softwaredefinierte Empfänger implementiert also ziemlich viele Teile, die ursprünglich von Hardware übernommen worden wären, und kann alle sichtbaren Satelliten verfolgen
Der softwaredefinierte Ansatz hat starke Vorteile. Zum Beispiel wird die anfängliche Satellitenakquisition durch Berechnung der Kreuzkorrelation zwischen dem empfangenen Signal und mehreren Gold-Codes durchgeführt; verarbeitet man das im Fourier-Bereich, kann man das Signal ziemlich schnell erfassen
Wenn man einen Hardcore-DIY-GPS-Empfänger will, der bis auf Transistorebene hinuntergeht, dürfte https://lea.hamradio.si/~s53mv/navsats/theory.html eine unterhaltsame Lektüre sein. Ein DIY-GPS-Empfänger im Stil der 1990er, komplett mit handgezeichneten Schaltplänen, handgezeichneten PCBs und sogar einer selbstgebauten Antenne
Außerdem war Ende der 1990er sogar differentielle GPS-Korrektur für Autos möglich, auch wenn das in dicht bebauten Innenstädten nicht ideal war — ein Bereich, mit dem selbst moderne Empfänger oft noch zu kämpfen haben. Man konnte es in dicht besiedelten Küstenmetropolen wie NYC verwenden.
Alte Auto-Navigationssysteme waren klobig und die Kartendaten insgesamt ziemlich miserabel, aber wegen der Selective Availability kann man kaum sagen, sie seien „völlig nutzlos“ gewesen.
Natürlich waren sie ziemlich schlecht. Aber Selective Availability war nur ein Faktor, und mit der heutigen Rechenleistung und besseren Karten hätte man Positionsfehler durch Selective Availability wohl deutlich leichter ausgleichen können.
Der Gesetzestext der aktualisierten Regeln https://www.space.commerce.gov/itar-controls-on-gps-gnss-rec... ist so kompliziert, dass schwer zu verstehen ist, ob das überhaupt noch gilt.
Apropos SDR: ITAR ist auch der Grund, warum das Passive-Radar-GNU-Radio-Modul des Kraken-RF-Teams entfernt wurde.
Ich mag dazu auch https://ciechanow.ski/gps/ mit den großartigen Visualisierungen, die sich zusammen mit dieser Erklärung gut ansehen lassen.
Diese interaktiven Grafiken sind einfach unschlagbar.
Zusammen mit der Fähigkeit, sogar Software zu schreiben, die bei der Analyse hilft und die endgültige Lösung implementiert, ist daraus ein tolles Projekt geworden. Ich habe GPS studiert und mich beruflich über Jahre damit beschäftigt, kenne aber trotzdem noch nicht alles. Ich freue mich darauf, in den Code zu schauen.
Rückblickend fühlt es sich wirklich wie etwas an, das ich gut gemacht habe. Ich glaube, ich verstehe den Bereich RF jetzt viel greifbarer und kann besser damit arbeiten wie mit einem Werkzeug. Es erinnert mich an die Dinge, die ich an Computern selbst mag.
Wenn die Formel zur Erzeugung des P-Codes öffentlich wäre, könnten zivile GPS-Empfänger ihn mit denselben Techniken wie beim C/A-Code locken.
Ich habe nicht alles gelesen, aber ich bin neugierig: Gibt es eine Möglichkeit, die P-Code-Chipping-Sequenz per Brute Force oder mit anderen Tricks zu gewinnen, um präziseres GPS zu bekommen?
Falls dich die Entstehungsgeschichte von GPS interessiert: Richard Eastons „GPS Declassified“ war ein spannend geschriebenes Buch.
GPS funktioniert auch im Flugmodus, sogar buchstäblich im Flugzeug. Es funktioniert ohne Mobilfunk oder Wi‑Fi. Die USA kontrollieren die GPS-Satellitenkonstellation, können GPS bei Bedarf in bestimmten Regionen abschalten und haben das tatsächlich auch schon getan. Deshalb haben andere Länder ihre eigenen GNSS-Konstellationen gestartet.
Interessant ist auch, dass GPS-Satelliten nicht den Standort herunterfunken, sondern nur Zeit. Das mit Daten vom Handy nachzuvollziehen, ist eine wirklich unterhaltsame Übung, und das Handy ist direkt mit den Satelliten verbunden.
Nebenbei: Vor Kurzem habe ich die Grundprinzipien der Navigation anhand von Sternen gelernt, und es ist interessant, dass sie trotz völlig anderer Mechanismen ebenfalls stark davon abhängt, präzise Zeit zu halten.
Die ersten GPS-Empfänger, die ich benutzt habe, waren eigenständige Geräte ganz ohne Datenverbindung, deshalb erschien es mir immer selbstverständlich, dass GPS keine Daten braucht.
Geräte wie Handys beziehen diese Daten aber meist aus anderen Quellen, weil das viel schneller geht, als auf die GPS-Datenübertragung zu warten.
Die Fähigkeit, GPS in einer bestimmten Region nach Belieben abzuschalten, gibt es meinem Verständnis nach auf neueren GPS-Satelliten nicht mehr, und vielleicht auch auf keinem derzeit betriebenen Satelliten.
Wenn ich ein iPhone benutze, werden diese Fotos nach der Landung mit dem Standort zum Zeitpunkt der Aufnahme verknüpft. Dadurch kann ich später interessante Geländeformen wiederfinden, die ich zufällig gesehen habe.
Sogar die verwendeten Suchbegriffe und der innere Monolog sind enthalten. Statt einfach nur zu zeigen, wie man fischt, zeigt er, wie man an die Teile kommt, um sich direkt selbst eine Angelmaschine zu bauen — genau meine liebste Art von Tutorial.
Umso dankbarer bin ich, dass du diesen Ansatz positiv gesehen hast.