Show HN: GPS受信機を作るプロジェクト
(axleos.com)- gypsum は、GPS信号をゼロからデコードして位置を得る受信機制作プロジェクトで、全4部作の第1部は雑音の下に埋もれた衛星信号を見つけることに焦点を当てている
- GPSは約30基の衛星が地球全体に送る放送型信号なので、衛星側は誰が聞いているかを知ることができず、データセンターがユーザーの電波受信を代行することもできない
- 地上アンテナに到達したGPS信号は周囲の雑音より100,000倍低い電力であることがあり、一般的なセルラー信号より1億倍弱いため、そのままではほとんど見えない
- 受信機は衛星と受信機の両方が知っているC/Aコードを繰り返し比較することでランダム雑音を平均化し、1MbpsのPRNコード上に載った50bpsのデータ信号を見つけ出す
- 取得（acquisition）は、衛星ごとのPRN、±5kHzのDoppler shift、コード位相を同時に探索し、見えている衛星とおおまかな時間遅延・相対速度を見つける計算集約型の段階である
GPS信号を直接聞くプロジェクト
- gypsum は、ゼロから作るGPS受信機プロジェクトである
- 全4部作のシリーズでは、GPS信号をデコードして位置を得る過程を扱っており、第1部は信号を見つけて衛星を取得する段階に当たる
- GPSは約30基の衛星が地球全体に信号を送っており、この信号は高度や天候に関係なく常に周囲に存在している
- GPSは1978年に始まり、記事執筆時点で45年が経っている
静かなビーコンとサーバーで代替できない位置計算
- GPS衛星信号は送信時には家庭用電球に近い強さだが、地上に到達する頃には極端に弱くなる
- GPSはsend-and-forget方式に近く、衛星側は誰が聞いているかを知ることができない
- FMラジオや地上波テレビも似た性質を持つ
- この構造のため、誰もGPSへのアクセス自体に課金しにくい
- 位置計算は、Webサービスが代わりに処理して結果を返すような構造には適していない
- GPSはユーザーのいる場所に届いた電波を直接聞く必要がある
- データセンターはユーザーの位置に届く電波を代わりに受信できない
SDRでGPS周波数を探る
- GPS信号をソフトウェアで受信し後処理するには、調整可能なRF受信機が必要であり、この装置が**ソフトウェア定義無線（SDR）**である
- SDR++ を使ってスペクトルを探索する
- SDRを使ううえではいくつかの概念が必要になる
- bias tee: SDR内部回路がSMAで接続されたアンテナにDC電源を供給する。使用したSDRではデフォルトで無効になっており、手動で有効にする必要があった
- automatic gain control(AGC): 弱い信号を増幅して受信データの信号対雑音比（SNR）を改善しようとするハードウェア回路、またはソフトウェア機能である
- IQ samples: Iはin-phase、Qはquadratureまたはimaginary成分で、時間・振幅・極性の観点からの処理を可能にする
- SDRでは、設定した中心周波数に大きなスパイクが現れる
- 初心者には、どこを見ても強い信号があるように見えることがある
- 中心周波数から少しずらして調整するか、ソフトウェアのIQ correctionでこのスパイクを減らせる
雑音の下に埋もれた信号を見つける方法
- 地上アンテナでは、GPS信号は周囲のエネルギーや他の信号より100,000倍低い電力で到達する
- GPS信号はthermal noise floorより最大50dB低いことがある
- 最新のGPS衛星は、受信機に約**-130dBm**レベルで届く信号を送るよう設計されている
- C/A帯域幅における一般的な住宅環境のthermal noise floorは約**-110dBm**である
- 比較対象としてセルラー信号は約**-50dBmで、GPS信号より1億倍**強い
- GPSはこのように雑音の下に埋もれた信号を識別しデコードするために、**拡散スペクトラム（spread-spectrum）**技術を使っている
C/AコードとPRNで聞こえない信号を聞く
- GPS衛星は、受信者が知らないデータとともに、衛星と受信機の両方が知っている信号を送る
- この信号はC/A code、PRN code、chipping codeと呼ばれ、衛星が1秒あたり1,000回繰り返している
- C/Aはcoarse acquisitionの略である
- もともと軍用として構想されたGPSでは、C/Aコードはより高精度なP codeにロックするための低解像度段階だった
- 現在のC/Aコードは大半の民生GPSの基盤であり、P codeは今でも軍用にしか使えない
- 民生受信機がP codeを使えない理由は、chipping sequenceの値を知らないためである
- P code生成式が公開されていれば、C/Aコードと同じ手法でロックできる
- P codeの方が高精度なのは、より高いchipping rateで動作するためである
- 受信機は予想したPRNと実際の受信信号を繰り返し加算・比較する
- ランダム雑音は時間とともに0へ平均化される
- PRN信号は継続的に蓄積されて大きくなる
- GPSは複数の衛星を同時に扱うためにcode-division multiple access(CDMA) を使っている
- 実際のデータ信号はPRNコードに混ぜて送信される
- PRNコードは1Mbpsで動作する
- データ信号ははるかに遅い50bpsで送信される
- この低いデータ速度のおかげで、PRNコードは比較的長時間にわたって安定した基準信号であり続ける
衛星ごとのC/Aコード生成
- 衛星は複数あるため、受信機はどの衛星が見えているかを知る必要がある
- 各GPS衛星は固有で安定したPRNコードを持つ
- このコードは、民生GPS仕様である IS-GPS-200L の
Table 3-I (Code Phase Assignments)に定義されている - オンラインにはPRNコード生成法を説明する資料は多いが、完全なPRNコードを照合できる再現資料はあまり多くなかった
取得段階: 見えている衛星を探す
- GPS受信機は、空に見えている衛星を探すために、各衛星が送るPRNの複製を生成し、アンテナで収集したデータの中からそのPRNを探す
- この段階がacquisitionであり、目標はユーザー上空にある衛星にロックすることだ
- 受信機は約1秒ほどの短いアンテナデータのスナップショットを取り、各複製PRNとの**相関（correlation）**を計算する
- 複製PRNと実データの間に強い相関があれば、そのPRNを持つ衛星が上空から信号を送っていると分かる
- 実際の受信信号は理想的なPRNとは異なる
- GPS信号は地球大気を通過する間に弱まる
- 衛星は高速で移動しているため、受信信号にはDoppler-shiftedが生じる
- GPS衛星の軌道速度はよく分かっているため、想定されるDoppler shiftの範囲も決まっている
- 近づく衛星では最大**+5kHz**の周波数上昇
- 遠ざかる衛星では**-5kHz**の周波数低下
- 受信開始時刻は任意なので、PRN送信の途中から聞き始めることもある
- 取得段階では3つの軸を同時に探索する
- 各衛星のPRNコード
- 想定されるDoppler shiftの範囲
- 受信PRNに合わせるために複製PRNをずらす位相
- 計算量は大きいが、正しいパラメータが見つかると相関スパイクがはっきり現れる
実装方式と第1部の結果
- 実装では、各PRNを時間領域から周波数領域へ変換し、入力される衛星データの周波数と各PRNコードのスペクトルを相関させる
- この方式は周波数領域 cross correlationに当たる
- 時間領域の位相オフセットは周波数成分の移動になるため、Doppler shift探索と位相探索を同じ計算で処理できる
- Doppler shiftは、各可視衛星について最も強い相関スパイクが出る値を見つけるよう、binary searchに似た方法で収束させる
- 第1部の結果として、現在ユーザー上空にあるGPS衛星を判定し、各衛星のおおよそのphase/time delayとDoppler shift/relative velocityを得る
- 次の段階は Part 2: Tracking Pinpricks へ続く
1件のコメント
Hacker News のコメント
GPS に十分な速さの直接 RF サンプリングまたは直接 RF 変換受信機は入手できる。例: Xilinx RFSoc https://www.mouser.com/datasheet/2/903/ds889_zynq_usp_rfsoc_...、National Instruments の記事 https://www.ni.com/en/solutions/aerospace-defense/radar-elec...、関連する既製ハードウェア https://www.ni.com/en-us/shop/category/flexrio-custom-instru...
NI が直接 RF 変換を費用対効果が高いと見ている一方で、機器を3万ドルで売っているのは少し不思議だが、3GHz 付近で位相コヒーレントな広帯域受信をプロトタイピングしていて、ちゃんとした研究室と予算があるなら何台か買う価値はある。量産なら、自作ボードのコストがもっと下がるのを待つか、従来のヘテロダイン受信機で可能かを検討すると思う
軍事用途で高度な RF 追跡兵器が心配なら、直接変換受信機がよい場合がある。敵の装備が検出できる局部発振器漏れがないため
「from scratch」という表現を見ると、実際にどれほどゼロからやったのか気になるが、ハードウェアが RTL-SDR だと知って少し残念だった。それでもプロトコルのデコードは非常に興味深く、結果も素晴らしい
GPS は1978年に始まったが、2000年までは「選択利用性」という仕組みで意図的に信号が劣化されていた。そのため多くの用途では GPS は事実上役に立たず、道路ナビゲーションには明らかに不向きで、僻地の探索や海上ナビゲーションには限定的に有用だった
gypsum がアンテナ信号を1分も聞かずにコールドスタートから位置と正確な時刻まで取得するのは非常に印象的で、現在の市販受信機よりも優れているように見える。2000年代初めの車での旅行では、出発前に路肩で GPS 受信機が測位するまで15〜20分待たなければならず、うまくいかなければ紙の地図を見ながら出発していた
46年が経った今でも無線レイヤは完全な上位・下位互換性を維持しており、初回測位時間やユーザー等価距離誤差のような主要指標は、プロトコル非互換の変更なしに10〜1000倍改善された
地球全体にサービスを提供する総 RF 送信電力は、一般的な米国家庭の消費電力より小さく、5G やテレビ、AM/FM ラジオよりはるかに低く、ノイズフロア以下だ。これは積み重ねた Gold コードの活用によって可能になっている
Galileo のような競合システムとの周波数共有も可能になるよう設計されているが、これはモバイル通信網ではなかなか見られないことだ。変調データと搬送波の位相が固定されているため、搬送波位相のデコードのようなことも可能になり、そのおかげでより良い疑似距離と精度が得られる
全体として、設計者たちに途方もない先見性があったか、ものすごく運がよかったか、あるいはその両方だったように思う
ここで意味したのは、GPS をまったく知らないハードウェア、つまり電磁場をサンプリングできるだけの装置から出発して受信機を組み上げたということだ
昔のハードウェアの初回測位時間が遅かった理由は、本質的には処理能力の進歩に関係している。従来の GPS 受信機はすべての衛星の「アルマナック」をダウンロードする必要があり、GPS データの伝送形式と速度のため、条件がそろっていても最低12.5分かかった
現代の処理能力なら、gypsum を含む受信機は、空から降ってくるヒントを待つ代わりに探索空間を総当たりして見える衛星を見つけられる。この手法は第1部の終わりで説明した方法だ
1999年に Delorme Earthmate Hyperformance GPS 受信機の RS-232 版を Toughbook に接続し、Delorme Street Atlas USA 6.0 あたりを動かして車で旅行した
国を横断する間、十分に使える道案内を提供してくれた。車線案内はなかったが、曲がるたびに事前に道路名まで含めて曲がる場所を知らせてくれた
そのバージョンには音声認識もあり、「まだ遠い？」のようなことを言うと、次の経由地と最終目的地までの到着予想時刻、現在位置を教えてくれて、かなり楽しかった
選択利用性の下で一般的な最悪の円形公算誤差が30m程度なら、非常に密集した地域を除けば道路ナビゲーションには十分な精度だ。そういう場所でも地図を一度見ればよく、開けた道路では素晴らしかった
昔の GPS 受信機は追跡チャネル数をマーケティング上の売りにしており、低価格受信機には6〜8基の衛星を追跡するハードウェアしかなかった一方で、高価格受信機は12基を追跡できた
したがって、このソフトウェア定義受信機は、本来ハードウェアが担っていたかなり多くの部分を実装しており、見えているすべての衛星を追跡できる
ソフトウェア定義方式には強力な利点がある。たとえば初期の衛星捕捉では、受信信号と複数の Gold コード間の相互相関を計算するが、これをフーリエ領域で処理すると信号をかなり高速に捕捉できる
トランジスタレベルまで踏み込むハードコアなDIY GPS受信機が欲しいなら、https://lea.hamradio.si/~s53mv/navsats/theory.html は面白く読めると思う。1990年代風のDIY GPS受信機で、手描きの回路図、手描きのPCB、自作アンテナまで備えている
さらに1990年代末には、密集した都市環境では理想的ではなかったものの、現代の受信機もしばしば苦労する領域であり、車載向けのディファレンシャルGPS補正も可能だった。ニューヨーク市のような沿岸部の大都市の人口密集地域で使えた
古いカーナビは無骨で、地図データも全般的にひどいものだったが、選択利用性のために「確実に役に立たなかった」と見るのは難しい
もちろん、かなり悪かったことは認める。ただ、選択利用性は一要因にすぎず、今日の処理能力とより良い地図があれば、選択利用性による位置誤差があっても、より簡単に補正できたはずだ
更新された規則 https://www.space.commerce.gov/itar-controls-on-gps-gnss-rec... の法的文言は複雑すぎて、今も適用されるのかさえ理解しにくい
SDRの話で言えば、ITARはKraken RFチームが作ったパッシブレーダーGNU Radioモジュールが削除された理由でもある
この説明と併せて見るのに良い、素晴らしいビジュアル資料がある https://ciechanow.ski/gps/ も気に入っている
あのインタラクティブなグラフィックには勝てない
解析を助け、最終的な解法を実装するソフトウェアまで作り上げた能力と相まって、見事なプロジェクトになっている。GPSを学び、数年間仕事として扱ってきたが、それでもまだすべてを知っているわけではない。コードを覗くのが楽しみだ
振り返ると、本当にやってよかったと思う。今ではRFという領域をずっと手触りのあるものとして理解し、道具のように使えるようになった気がする。コンピュータそのものの好きな部分を思い出す
Pコードを生成する公式が公開されているなら、民間GPS受信機もC/Aコードとまったく同じ手法でロックできるはずだ
全部は読めていないが気になる。より高精度なGPSのために、Pコードのチッピングシーケンスを総当たりしたり、別の手で得たりする方法はあるのだろうか？
GPS開発の話に興味があるなら、Richard Eastonの「GPS Declassified」は興味深く解説した本だった
GPSは機内モードでも、文字どおり飛行機の中でも動作する。携帯電話サービスやWi-Fiがなくても動く。米国はGPS衛星群を管理しており、必要なときに特定地域のGPSを止めることができ、実際にそうしたこともある。だから他国が自前のGNSS衛星群を打ち上げるようになった
GPS衛星は位置を送っているのではなく、時刻だけを送っているという点も面白い。携帯電話で受け取ったデータでこれを試すのは本当に面白い練習で、携帯電話は衛星と直接つながっている
付け加えると、最近、星を使った航法の基本原理を学んだが、まったく別のメカニズムでありながら、やはり正確な時刻を保つことに大きく依存しているという対称性が面白かった
私が最初に使った数台のGPS受信機は、データ接続がまったくないスタンドアロン機器だったので、GPSにデータが不要だというのは当然に感じられる
ただし携帯電話のような機器は、GPSのデータ伝送を待つよりはるかに速いので、通常は別のソースからそのデータを受け取る
特定地域のGPSを任意に止められるという機能は、私の理解では、より新しいGPS衛星にはもうなく、もしかすると現在運用中のすべての衛星にもないかもしれない
iPhoneを使っていると、着陸後にそれらの写真が撮影時の位置情報と紐づけられます。おかげで、偶然目にした興味深い地形を後から見つけられます。
使った検索語や内省的な独り言まで含まれています。単に魚の釣り方を教えるのではなく、自分で釣り機械を作るための部品をどう手に入れるかを見せてくれるようなもので、私がいちばん好きなタイプのチュートリアルです。
それでも、そのアプローチを好意的に見てくれたとのこと、本当にありがとうございます。