Йэн Стюарт – Это база: Зачем нужна математика в повседневной жизни (страница 51)

В результате вашему GPS-приемнику достаточно систематически производить серию относительно простых геометрических расчетов, которая и приведет к наилучшей возможной для этого прибора оценке местоположения. Сравнивая полученный результат с детализированной формой Земли, прибор может определить даже, как высоко над уровнем моря вы находитесь. Как правило, высоты определяются менее точно, чем координаты по широте/долготе.

Спутник «рассылает дальномерные коды», или, говоря иначе, «рассылает сигналы с точной привязкой по времени». Звучит просто, но на самом деле это не так. Если вы слышите раскат грома, то понимаете, что начинается гроза, но сам по себе раскат грома не скажет вам, насколько она далека. Если же вы не только слышите гром, но и видите молнию, что происходит раньше, чем раздается гром, поскольку свет распространяется быстрее звука, то можно использовать разницу во времени прихода двух сигналов для оценки расстояния до молнии. Для прикидки достаточно знать, что три секунды запаздывания соответствуют примерно одному километру. Однако скорость звука зависит от состояния атмосферы, так что это правило нельзя считать точным.

GPS не может использовать в качестве второго сигнала звуковые волны по очевидным причинам – они слишком медленные, к тому же в космосе царит вакуум, так что звук там в любом случае не может распространяться. Но сама идея получения временно́й разницы между двумя разными, но взаимосвязанными сигналами верная. Каждый спутник рассылает последовательность импульсов 0/1, не содержащую повторений, – разве что вы будете ждать очень долго, чтобы последовательность повторилась целиком. GPS-приемник может сравнить строку из нулей и единиц, которую он получает со спутника, с той же строкой, получаемой от местного источника. Спутниковый сигнал приходит с задержкой, потому что ему приходится преодолевать расстояние между спутником и приемником, а время задержки можно определить, выровняв оба сигнала и посмотрев, насколько нужно сдвинуть один из них, чтобы он соответствовал второму.

Мы можем проиллюстрировать этот процесс, используя вместо нулей и единиц слова из этой книги.

Предположим, что сигнал, полученный со спутника, таков:

выровняв оба сигнала и посмотрев, насколько нужно,

тогда как опорный сигнал, получаемый одновременно практически с соседнего двора, таков:

посмотрев, насколько нужно сдвинуть один из них.

Тогда мы можем сдвинуть местный сигнал так, чтобы одинаковые слова совпали, примерно так:

Теперь мы видим, что сигнал со спутника приходит на четыре слова позже местного сигнала.

Остается только сгенерировать подходящие битовые строки. Простой способ генерирования строки из нулей и единиц с очень редкими повторениями состоит в подбрасывании монеты миллионы раз с записью 0 для орла и 1 для решки. Каждый бит возникает с вероятностью 1/2, так что строка из, скажем, 50 бит возникает с вероятностью 1/2⁵⁰, что соответствует примерно одному шансу на квадриллион. В среднем она повторится примерно через квадриллион знаков вдоль строки. Если сравнить такой сигнал с его вариантом, смещенным на гораздо меньшую величину, то «верное» смещение, дающее наилучшее совпадение строк, окажется единственным.

Компьютеры, однако, не сильны в подбрасывании монет. Они следуют конкретным инструкциям, и весь смысл их работы состоит в том, что они должны делать это точно и безошибочно. К счастью, существуют точные математические процессы, способные генерировать битовые строки, которые кажутся случайными в разумном статистическом смысле, хотя реальная процедура их создания носит детерминистский характер. Подобные методы известны как генераторы псевдослучайных чисел. Это третий крупный математический ингредиент системы GPS.

На практике поток битов из генератора псевдослучайных чисел объединяется с другими данными, которых требует GPS, – такой метод называется модуляцией. Спутник передает данные с относительно невысокой скоростью: 50 бит в секунду. Он соединяет этот сигнал с куда более быстрым потоком битов из генератора псевдослучайных чисел, скорость которого более миллиона чипов в секунду. Чип здесь – примерно то же, что и бит, но значения он принимает +1 или –1, а не 0 или 1. Физически это прямоугольный импульс с амплитудой либо +1, либо –1. «Модуляция» означает, что первоначальная строка данных умножается на значение чипа в каждое мгновение. Поскольку все другие данные меняются, по сравнению с этим, очень медленно, методика «сдвинуть и совместить» по-прежнему работает достаточно хорошо, но иногда сигналы совпадают полностью, а иногда они оказываются противоположными по знаку. Если воспользоваться статистическим методом корреляции, то получится, что вам нужно просто сдвигать сигналы друг относительно друга, пока их корреляция не станет достаточно высокой.

Мало того, GPS проделывает то же самое и с другим псевдослучайным числом, модулирующим сигнал на вдесятеро большей скорости. Более медленный сигнал называется «код грубого определения местоположения объектов» и предназначен для гражданского использования. Более быстрый – «точный код» – зарезервирован для военных. Он, кроме того, зашифрован и повторяется не чаще чем раз в семь суток.

Генераторы псевдослучайных чисел, как правило, основаны на абстрактной алгебре, такой как многочлены над конечными полями, или на теории чисел, такой как целые числа по некоторому модулю. Простой пример последнего – линейный конгруэнтный генератор. Выберем модуль m, два числа a и b (mod m) и начальное число x₁ (mod m). Затем определим последовательные числа x₂, x₃, x₄ и т. д., вычисляемые по формуле

x_n+1 = ax_n + b (mod m),

где a играет роль постоянного множителя текущего числа x_n, а b сдвигает полученное значение на постоянную величину. Это дает следующее число последовательности, после чего операция повторяется. Например, если m = 17, a = 3, b = 5 и x₁ = 1, то мы получаем последовательность

1 8 12 7 9 15 16 2 11 4 0 5 3 14 13 10,

которая затем повторяется бесконечно. Никаких явных закономерностей, заметных глазу, здесь нет. На практике, разумеется, m намного больше. Существуют математические условия, которые гарантируют, что последовательность повторяется очень и очень редко и при этом удовлетворяет разумным статистическим тестам на случайность. Например, после превращения выходной последовательности в двоичную, каждое число (по модулю m) должно появляться в ней с равной частотой в среднем. То же можно сказать и о каждой строке из нулей и единиц заданной длины, вплоть до некоторого разумного размера.

Линейные конгруэнтные генераторы слишком просты, чтобы быть надежными, поэтому были разработаны более сложные варианты. В качестве примера можно назвать вихрь Мерсенна, который придумал Макото Мацумото в 1997 году. Такой генератор наверняка есть у многих из вас, потому что он используется в десятках стандартных программных пакетов, в том числе в Microsoft Excel. В вихре Мерсенна сочетаются простые числа, благодаря которым математика упрощается, и симпатичные двоичные выражения, упрощающие вычисления. Простое число Мерсенна – это число вида 2^p – 1 (где p – простое число), такое как 31 = 2⁵–1 или 131 071 = 2¹⁷–1. Простые числа Мерсенна встречаются редко, и мы даже не знаем, бесконечно ли их количество. В январе 2021 года было известно ровно 51 простое число Мерсенна, самое большое из которых равно 2^82 589 933–1.

В двоичном виде два простых числа Мерсенна выглядят так:

31 = 11111

131 071 = 11111111111111111

и представляют собой 5 и 17 единиц соответственно. Это позволяет цифровому компьютеру легко оперировать ими при вычислениях. Вихрь Мерсенна основан на каком-нибудь очень большом простом числе Мерсенна, обычно 2^19 937–1, и он заменяет числа в сравнениях матрицами над полем с элементами 0 и 1. Этот метод удовлетворяет тестам для подстрок длиной вплоть до 623 бит.

Сигнал GPS включает в себя также сигнал гораздо более низкой частоты, несущий информацию об орбите спутника, его временны́х поправках и других факторах, влияющих на статус системы. Возможно, это кажется сложным – так оно и есть на самом деле, – но современная электроника способна безошибочно выполнять чрезвычайно сложные инструкции. Для такой сложности существуют серьезные причины. Она помогает приемнику не захватить случайно какой-то другой сигнал, поскольку крайне маловероятно, что он воспроизведет такую сложную закономерность. Каждому спутнику присваивается собственный псевдослучайный код, и та же сложность гарантирует, что приемник не спутает сигнал одного спутника с сигналом другого. Помимо прочего, все спутники могут работать на одной и той же частоте, не глуша друг друга, что позволяет высвободить дополнительные частоты в нашем все более забитом радиодиапазоне. К тому же, что особенно важно для военных, противник не может вмешаться в работу системы или организовать передачу ложных сигналов. В целом псевдослучайным кодом распоряжается Министерство обороны США, так что оно может контролировать доступ к GPS.

Помимо постепенного дрейфа атомных часов, существуют и другие источники временны́х погрешностей, например небольшие отклонения формы и размера орбит спутников от расчетных. Наземная станция передает связанные с этим поправки на спутник, который в свою очередь раздает их пользователям, обеспечивая синхронность с эталонными часами Военно-морской обсерватории США. Однако наибольшую погрешность вносят релятивистские эффекты, так что вместо доброй старой ньютоновской физики нам здесь не обойтись без эйнштейновских теорий относительности{61}.