Čekám na signál: Nesourodé povídání o satelitních navigacích

Milý čtenářský ohlas na nedávný článek o tom, co se dá napáchat se satelitními navigacemi (GNSS), mi nedal jinou možnost než opětovně strávit několik večerů zíráním do zářícího obdélníku a se sklenkou dobrého pití se pokusit vzpomenout si na základní aspekty GNSS. Aniž bych se snažil stvořit nový titul nakladatelství Springer.

Vesmírný segment

Podívejme se tedy na první úkol, co musí vyřešit libovolný zájemce o vlastní modrou tečku na digitální mapě – vymyslet, jak to vlastně celé bude fungovat. Někde musí létat družice, ty musí vysílat nějaký nosný signál, na něm modulována nějaká data a z toho celého by mělo jít spočítat, kde příjemce je.

Stran družic se omezíme na konstatování, že většinou se používají střední orbity ve výšce cca dvaceti tisíc km nad zemským povrchem. GPS ji má zvolenou tak, že každých 24 hodin se jeho pozemní „stopa“ opakuje; Galileo je o něco výš a pozemní stopa se opakuje každých 10 dní. Ruský GLONASS pro změnu letí kousek pod GPS a pozemní stopu opakuje každých 8 dní. Čínské BeiDou jako jediné kombinuje několik typů orbit, kromě obvyklých středních používají také geostacionární a geosynchronní dráhy.

Různé požadavky na GNSS jsou taky trochu vidět ze sklonů jednotlivých drah vůči rovině rovníku – nejvyšší má GLONASS, takže jeho satelity „létají“ nejdále na sever (a analogicky i na jih) a lépe pokrývají i severní části ruské pevniny. Ne že by póly nebyly pokryté, tady mate projekce na 2D mapu, ale satelity nejsou tak vysoko nad obzorem a výsledná geometrie je o něco horší.

GPS ground track

Galileo ground track

Glonass ground track

BaiDou ground track

Abychom mohli určit, kdy bude mít přijímač možnost spočítat polohu, musíme definovat nějaké kritérium, kdy je poloha dostupná a kdy ne. První nástřel je jednoduchý – potřebujeme alespoň 4 satelity, neboť máme 4 neznámé (3D pozice + čas). Ano, teoreticky se může stát, že tři satelity budou v jedné rovině a matice bude singulární, ale to jsem v praxi nezažil. I kdyby to nastalo, poziční řešení se běžně počítá každou sekundu a v příští sekundě už ony satelity v rovině nebudou. Druhé, podstatně přesnější kritérium, souvisí s geometrií – podrobně si to vysvětlíme příště, prozatím bude stačit, že „nekvalita geometrie musí být menší než 6“. Ať už to znamená cokoliv. Proč zrovna šest? Upřímně nevím, ale někde se čára holt nakreslit musela. Pokud kombinujeme víc konstelací dohromady (třeba GPS+Galileo), za každou další konstelaci přidáme jednu neznámou, neboť časy konstelací obecně nejsou mezi sebou přesně synchronizované. Matematický fun fact: pokud přidáte přesně jeden satelit z nové konstelace, nijak si nepomůžete, výsledná geometrie pozice bude navlas stejná. (Zjednodušeně řečeno: extra měření „sežere“ extra neznámá.) Abyste si pomohli, potřebujete vždy aspoň dva.

Rádiové signály

Máme tedy kusy harampádí, co spořádaně létají desítky tisíc kilometrů nad zemským povrchem. My ovšem potřebujeme, aby něco vysílaly – přimontujeme jim tedy antény a zamyslíme se, co do nich pustit. Pro satelitní navigaci je rezervováno několik frekvenčních pásem, nicméně pro civilní užití je nejrozšířenější a nejdůležitější L1 – takže budeme vysílat na frekvenci 1575,42 MHz. Abychom pochopili, odkud toto číslo spadlo, vraťme se do 70. let minulého století.

Tím, že všechny satelitní signály se dohromady u příjemce „míchají“, musí být k dispozici nějaká metoda, jak mezi nimi rozlišovat. V zásadě byly k dispozici dvě – buď FDMA (Frequency Division Multiple Access), anebo CDMA (Code Division Multiple Access). První přístup zvolili Rusové a spočívá v tom, že v rámci celého pásma dostal každý satelit svou úzkou frekvenční „ulitu“, do které mu jiný satelit nemohl zasahovat. Signál se totiž u příjemce jen málokdy chytne na referenční hodnotě, většinou do toho hází vidle pan Doppler (satelitu i přijímače) a další vlivy. Satelity GLONASS tak můžou všechny vysílat totožný nosný signál a příjemce až z přesné frekvence určí, o který satelit tedy vlastně jde.

GPS (a vlastně i všichni ostatní, včetně nejnovější generace GLONASS) na to jde tou první cestou a všechny satelity vysílají na stejné frekvenci. O rozlišení signálů se starají tzv. spreading codes – tj. rodina kódů, které (v ideálním případě) mají nulovou kros-korelaci s jinými členy téže rodiny, a současně i nulovou auto-korelaci samy se sebou, pokud nejsou správně „zarovnány“. Příjemce si kakofonii přijatých signálů porovná s lokální kopií toho kódu, co čeká, a když trefí správnou frekvenci a správný offset kódu, tak se mu naakumuluje dostatečně vysoká hodnota přesahující předem zvolený práh – znamenající úspěch.

Tím, že GPS bylo navrhováno v 70. letech, kdy paměti byly malé a drahé, pro úlohu spreading code byly vybrány Gold kódy, mající vlastnosti nejbližší oněm žádaným. A hlavně byly extrémně jednoduché pro implementaci: šlo vlastně o LFSR (Linear Feedback Shift Register) o deseti bitech, který postupně projde všech 1023 nenulových hodnot. (Pro matematické nerdy: generující polynom je v GF(2^10) ireducibilní, takže je LFSR úplný, a naopak.). A číslo 1023 si zapamatujme.

Každou milisekundu se totiž musí celý spreading code zopakovat, tedy pokud bit onoho spreading code označíme v souladu s konvencemi za „chip“, dostaneme frekvenci spreading code 1,023 Mcps (megachip per second). Signál na L1 je tedy nakonec vysílán jako 1,023 MHz signál modulovaný pomocí BPSK na 1540 × 1,023 = 1575,42 MHz. (Protože už původně byl vysílán i vojenský signál na desetinásobné frekvenci, obyčejně se toto píše jako 154 × 10,23 MHz a vysvětluje to o řád nižší možnost volby konečné nominální frekvence.) Nominální frekvence pro signál v pásmu L5 je 1176,45 MHz, což je 115násobek 10,23 MHz.

Aby signál k něčemu byl, pošleme na něm i data, těch je v L1 C/A padesát za sekundu, tedy každý bit dat trvá 20 ms, což je také dvacet period spreading code. Na toto si vzpomeneme zase později.

Nebudu unavovat, jak to přesně vypadá pro každý možný signál, to si ctěný čtenář jistě rád dohledá sám, dodám jen zajímavosti u jiných.

Galileo pro spreading codes použilo tzv. memory codes – tj. náhodné bitové sekvence, které dohromady co nejlépe splňují požadavky. Jejich generování trvalo řádově několik měsíců, používaly se při tom genetické algoritmy a hřeší na to, že dnes je již paměť levná a chudáci programátoři holt těch několik desítek stránek hexadecimálních kódů do svého software překopírují.

Galileo také místo BPSK použilo pro jeden svůj signál BOC modulaci – ta má výhodu, že její špička je „užší“, takže její sledování je pak o něco přesnější; na druhou stranu se ta úzká špička hůř hledá.

Oproti původnímu L1 C/A používají moderní signály kvadratickou modulaci s fázovým posuvem, takže jeden signál vlastně obsahuje dva na sobě teoreticky nezávislé – nazvaná data a pilot. Úlohou datového signálu je nést data, kdežto pilot byl původně zamýšlen pro usnadnění akvizice, kde by se vysílal čistý primární spreading code bez překážejících modulovaných dat.

Protože kros-korelační vlastnosti původních Gold kódů nebyly ideální, u nové generace GPS i během tvorby Galilea přišla na svět myšlenka tzv. sekundárních kódů. To jsou krátké kódy, jejichž bity jsou modulovány na celé primární kódy – tj. jedna perioda primárního kódu je jeden bit sekundárního. Jejich úlohou je od sebe ještě víc „oddálit“ jednotlivé primární kódy. Většinou se používají jen na pilot, ale třeba E5 je má i na datech. Bohužel, praxe zde ukázala, že méně je někdy více a sekundární kódy nadělaly víc škody než užitku.

Nyní máme ve vesmíru satelity, ty vysílají jakýsi signál a my můžeme hodit nohy na stůl a bouchat šampaňské… vlastně ne. Něco nám chybí. Uživatelé. Musíme postavit přijímač.

Akvizice a sledování signálu v přijímači

Spoustu HW věcí přeskočím a zaměřím se až na akvizici signálu v momentě, kdy algoritmus dostane na stříbrném podnose předložené vzorky. Přijímač si vybere satelit, který se snaží najít (buď náhodně, nebo nějak deterministicky – třeba odněkud ví, že by měl být viditelný), a vyrobí si lokální kopii kódu daného satelitu. Teď se do hry znovu připlete pak Doppler a jeho vliv – přijímač neví, na jaké frekvenci má satelit chytnout. Neví frekvenční posun kvůli pohybu satelitu ani kvůli vlastnímu pohybu. Neví ani, jestli jsou vůbec jeho vlastní hodiny přesné a umí bezchybně syntetizovat požadovanou frekvenci. Všechny tyto vlivy se sečtou a vytvoří jednu osu nejistoty – frekvenci.

Druhou osu nejistoty (čas) tvoří spreading code – nevíme, kdy během jedné milisekundy začít, abychom byli zarovnaní se satelitem. Tady si připomeneme BPSK a jak vypadá jeho ideální autokorelační funkce, a zjistíme, že hypotéz o časovém offsetu potřebujeme násobně víc než 1023, abychom se se slušnou šancí trefili do místa někde blízko špičky.

2D prostor různým pohledem – jak reálně akumulované hodnoty pro Galileo, tak simulovaný vzhled pro GPS:

Akvizice signálu GPS

Akvizice signálu Galileo

2D prostor různým pohledem – jak reálně akumulované hodnoty pro Galileo, tak simulovaný vzhled pro GPS

Akvizice signálu tak není nic jiného než bruteforce prohledávání 2D prostoru. Implementace bývá různá a počet hardwarových jednotek, které prohledávání realizují, bývá výsledkem kompromisu mezi časovou náročností (aby jednak splnil certifikační požadavky, jde-li o přijímač, který je má plnit, a jednak aby to uživatele neotravovalo), cenou a užitečností (od určitého počtu cena zrychlení neodpovídá užitku). Nejrychlejší je samozřejmě původní L1 C/A, neboť používá BPSK s kódem dlouhým 1023 chipů. Desetkrát pomalejší jsou L5 a E5a, které mají BPSK modulaci a kód dlouhý 10230 chipů. A ne zrovna intuitivně je nejpomalejší E1, který má sice jen 4096 chipů, ale kvůli úzké špičce BOC modulace musí být hledání natěsnáno ve zhruba třetinových rozestupech.

Softwarová stránka akvizice je ještě různorodější, existují různé metody s různými optimalizacemi, které záleží i na tom, s jakým prostředím počítáte – např. spotřební elektronika většinou přepokládá „rozumně“ silné signály, co se dají od šumu odlišit poměrně rychle. Ale třeba Safety-of-life užití podléhá certifikaci, která předepisuje časový limit na akvizici v extrémně tvrdých podmínkách (velmi slabý signál, do toho silný šum a cizí signál v pozadí), tady se hardwarová síla jednoznačně hodí. Vidle do celého procesu ještě hází modulovaná data, jejichž hrany změní fázi o 180° a efektivně tak „škodí“ akumulaci korelovaných hodnot. Nejlépe je na tom opět L1 C/A, neboť datové bity trvají 20 ms a tyto změny tak nastávají nejméně často. Pilot nám nepomůže, na něm jsou modulovány sekundární kódy, navíc mnohdy častěji než skutečná data – tady si poprvé drbeme hlavu, k čemu tedy vlastně jsou.

Dejme tomu, že akviziční jednotka našla kandidáta na signál – může to být duch (to když třeba chytáte slabý signál v přítomnosti silného a zafunguje kros-korelace), může to být vedlejší lalok ve frekvenčním spektru (takže stejně vždycky kontrolujete kandidáty na vedlejší laloky, jestli je ten nalezený skutečně největší), v případě BOC modulace kontrolujete i vedlejší špičky v čase. Ale pokud máte štěstí, máte v ruce správnou frekvenci i časový offset a akvizice má hotovo… eh, jde hledat další signál v řadě.

Její práci převezme trackovací smyčka se zpětnou vazbou, která postupně zpřesní původně poměrně hrubý odhad frekvence a času a následně se „zamkne“ na velmi úzkém pásmu. To má sice výhodu, že pak je sledování signálu nejpřesnější, na druhou stranu při divočejších manévrech může rychlá změna Dopplera dostat signál mimo rozsah smyčky a vést k jeho dočasné ztrátě. Proto jsou omezeny možné manévry pro civilní GPS přijímače – všechny přijímače, co vydrží i vyšší než malé přetížení, jsou minimálně dual-use (v této souvislosti mě napadá, že nevím, jestli akrobatické speciály mají výjimku a vojenské GPS na palubě, anebo jim pravděpodobněji holt během vystoupení nefunguje navigace).

Poslední věc, kterou dnes do přijímače zamontujeme, bude dekódování navigační zprávy. Trackovací smyčka umí detekovat fázové posuny o 180°, což značí změnu bitu v datech. U signálů bez sekundárních kódů rovnou dostáváme data (resp. nevíme, co jsou 0 a co 1, udržujeme si obě hypotézy a snažíme se někde „zachytit“). K synchronizaci slouží pravidelně se opakující hlavička – u L1 C/A trvají základní jednotky (sub-frame) s touto hlavičkou 6 sekund, tedy 700 bitů. Nejpozději po 12 sekundách tedy máme potvrzeno, kde začíná každý sub-frame, a můžeme se je pokoušet identifikovat. Sub-frame je celkem pět typů, první tři obsahují parametry dráhy satelitu nutné k výpočtu polohy a opakují se v každém frame (tedy každých 30 sekund), poslední dva obsahují obecnější informace o konstelaci a postupně se obměňují, opakují se každých 12,5 minuty.

Struktura navigační zprávy GPS L1 C/A

Z toho je zřejmé, proč TTFF (Time To First Fix) při studeném startu je u přijímačů vždy lehce nad minutu: podle specifikace potřebujete dvakrát přijmout efemeridy (parametry drah), což zabere v nejhorším případě 60 sekund, plus čas na nalezení signálů a jejich tracking. Taky to vysvětluje, že nemá smysl mít mega akviziční jednotku, která třeba pokryje celý 2D prostor najednou – zrychlení by bylo max. pár sekund (spíš míň), což se v následném dekódování efemerid ztratí.

Pokud je k dispozici Assisted GPS (A-GPS), což je ve spotřební elektronice běžné, navigační čip dostane informaci o své hrubé poloze a času i kompletní aktuální navigační zprávu. Z toho určí, které satelity by měl vidět i na jaké přibližné frekvenci, výrazně si zmenší 2D prostor a hledání je pak o dost rychlejší. Tím, že má k dispozici i ověřené efemeridy, nemusí čekat na jejich úplné dekódování a může po zarovnání rovnou začít počítat polohu. To platí i pokud byl přijímač krátce vypnutý.

Vraťme se ale ještě na moment k dekódování dat a proč jsou sekundární kódy střílením se do vlastní nohy. Jednak zbytečně často (každou periodu primárního kódu) potenciálně mění polaritu, čímž škodí akumulaci korelovaných hodnot a snaze překonat předem určený práh; ale hlavně nijak nepomáhají určit zarovnání sub-frame. Než provádět akvizici na pilotovi a pak se „drbat“ se sekundárními kódy (ale k čemu vlastně?), rovnou můžeme přejít na data – tam jsou bitové změny méně časté a hlavně aspoň něco znamenají.

Spektakulární, epický fail je ovšem… drumroll, please… Galileo E5 – ten totiž sekundární kódy používá jak na pilotovi, tak na datech. Chudák přijímač tak musí nejprve signál najít, pak se zarovnat vůči sekundárnímu kódu (jeho perioda je stejná jako datový bit) a pak teprve začít dekódovat navigační zprávu. Místo aby si počkal na fázový posun o 180° a ihned poznal, kde je hrana datového bitu, takto minimálně první hranu mine. Gratulujeme a posíláme klíčenku.

Zkrátka: celá vtipná myšlenka pilot signálu pro usnadnění akvizice je nakonec dokonale zkurvená. Pardon my French.

Ale abych nekončil pesimisticky: máme v ruce signál, čteme z něj nějaká data, a tak se příště pokusíme spočítat polohu a určit, jak je asi tak přesná.

01.12.2024 Zajíc

Související články: