СПОСОБ И СИСТЕМА ДЛЯ ОПТИМИЗИРОВАННОЙ ПЕРЕДАЧИ СООБЩЕНИЙ СПУТНИКОВОЙ НАВИГАЦИИ
METHOD AND SYSTEM FOR OPTIMIZED TRANSMISSION OF SATELLITE NAVIGATION MESSAGES

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ
Настоящее изобретение относится к способу и системе для оптимизированной передачи сообщений спутниковой навигации, и в частности относится к оптимизированным кодированию, передаче и декодированию цифрового сообщения от множества спутников на по меньшей мере один пользовательский приемник.
УРОВЕНЬ ТЕХНИКИ
Системы спутниковой навигации, например GPS, GLONASS или Galileo, обычно передают сообщения в несколько сотен битов с орбитами и смещениями часов передающих спутников, что позволяет пользовательскому приемнику вычислять свою позицию. Им также может потребоваться передавать более длинные сообщения, возможно, более тысячи битов, например, альманахи, цифровые подписи, спутниковые данные точное точечное позиционирование или точную ионосферную информацию. Битовая скорость, разрешенная навигационными спутниками, в общем случае, низка, поэтому передача длинного сообщения требует, чтобы пользовательский приемник принимал спутниковые сигналы без ошибочных битов в течение нескольких секунд, или даже минут. Это может быть невозможно в ухудшенных условиях приема и видимости, например, в городских ущельях или под кронами деревьев. Высокие здания в городах обычно приводят к ограничению количества спутников, в секторе обзора пользовательского приемника, и термин «городские ущелья» означает отсутствие сигнала вследствие таких высоких зданий, что приводит к нарушению приема данных.
Однако для улучшения приема данных на каналах с замиранием вследствие городских ущелий и крон деревьев, современные сообщения спутниковой навигации обычно кодируются посредством различных типов сверточных и блочных кодов.
В справочном документе “Quasi-Zenith Satellite System Interface Specification Centimeter-Level Augmentation Service (IS-QZSS-L6-001) Draft Edition, 2017” описана передача сообщения высокой точности 2000 битов в секунду. Такое сообщение содержит заголовок на 49 битов, часть данных на 1695 битов и код Рида-Соломона (RS), обеспечивающий 256 избыточных битов для независимой коррекции ошибок в каждом сообщении.
В справочном документе “European GNSS (Galileo) Open Service Signal In Space Interface Control Document, (OS SIS ICD V1.3)”, изданном Еврокомиссией, предлагается сверточное кодирование с прямой коррекцией ошибок со скоростью = ½ и длиной 7, которое применяется к каждой двухсекундной странице Galileo. На этом уровне кодирования, данные Galileo данного двухсекундного сообщения может демодулироваться даже если сообщение принимается с ошибками. В этом справочном документе также предлагаются передача длинного сообщения в пределах группировки, например сообщения типа альманах, разбиение на несколько более коротких фрагментов, где типы слова 7, 8, 9 и 10 подкадра I/NAV Galileo передают альманах для 3 спутников из полной группировки.
Хотя этот подход сравнительно прост в реализации, он обладает рядом недостатков, главный из которых состоит в том, что нарушение приема одного фрагмента угрожает приему полного сообщения.
В WO-A-2017/216058 раскрыт способ передачи навигационного сообщения, содержащего внешнее кодирование Рида-Соломона (RS) часов и эфемеридных данных (CED), что дополнительно предусматривает использование кода циклического контроля по избыточности (CRC). В этом документе единственный код RS применяется к сообщению CED в несколько сот битов, с низкой четностью. Таким образом, этот способ, будучи полезен для коротких сообщений от единственного спутника, не оптимален для длинных сообщений передаваемых от нескольких спутников, которые имеют высокие отношения четности/данных.
В статье “Packet transmission through navigation satellites: A preliminary analysis using Monte Carlo simulations” за авторством Fernández-Hernández I. и др., ENC 2017, предлагается смещать передачу страниц одного и того же сообщения спутниковой навигации от разных спутников. Однако смещение страницы не позволяет оптимально восстанавливать сообщение спутниковой навигации.
K
G’
K
N
N > K
G'
В статье “Fountain Codes for GNSS” за авторством  I. и др., Материалы 30-го международного технического совещания спутникового отдела Института навигации (ION GNSS+ 2017), страницы 1496-1507, описано использование фонтанных кодов для быстрой и надежной широковещательной передачи больших сообщений с использованием сигналов GNSS. Такие сообщения делятся на  пакетов, и каждый пакет кодируется элементом случайной двоичной матрицы , имеющей  строк и потенциально неограниченное количество столбцов. Приняв  пакетов, где во всех случаях, приемник строит матрицу , столбцы которой соответствуют принятым пакетам, для восстановления исходного сообщения.
В WO-A-2012/174933 раскрыт способ кодирования кодера RS, в котором входные данные распределяются по заранее определенному количеству параллельных каналов данных и кодируются путем одновременного осуществления параллелизм множества кодовых слов на заранее определенном количестве каналов данных. После кодирования определяется состояние разрешения входного сигнала управления, или если он разрешен, кодированные данные вставляются в указанные позиции прекодированного потока данных с использованием операции заполнения нулями. Обработка данных с устранением нулей осуществляется после последовательной обработки заранее определенного количества параллельных каналов данных.
В US-A-2016/0056920 раскрыт способ сетевого кодирования, который включает в себя кодирование множества пакетов сообщений для создания множества кодированных пакетов, которые включают в себя, например, пакеты сообщений и один или более пакетов четности. Каждый пакет сообщений и каждый кодированный пакет включает в себя множество символов, имеющих индекс, и каждый символ кодированных пакетов формируется путем применения кода Рида-Соломона к символам пакетов сообщений, имеющих тот же индекс, что и символ кодированных пакетов. Длина кодированных пакетов идентична длине пакетов сообщений. Раскрыто также устройство беспроводной связи, которое включает в себя сетевой кодер для кодирования множества пакетов сообщений для создания множества кодированных пакетов и физический уровень для передачи кодированных пакетов через беспроводную антенну.
Таким образом, в литературе не описан способ, позволяющий оптимально извлекать сообщения спутниковой навигации, состоящие из нескольких страниц, из нескольких источников, с полной возможностью взаимной замены и с приемлемой стоимостью декодирования на пользовательском приемнике.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
Таким образом, задача настоящего изобретения состоит в создании способа обеспечения оптимального извлечения кодированного сообщения спутниковой навигации, содержащего несколько страниц, принятых из нескольких источников, с полной возможностью взаимной замены.
Другая задача настоящего изобретения состоит в создании системы спутниковой навигации, в которой осуществляется способ оптимального извлечения кодированного сообщения спутниковой навигации, содержащего несколько страниц.
В соответствии с одним аспектом настоящего изобретения, предусмотрен способ формирования кодированного сообщения спутниковой навигации в форме множества страниц для передачи на по меньшей мере один пользовательский приемник через множество спутников, причем способ содержит этапы:
M
k
a) деления на наземной станции сообщения  спутниковой навигации на страниц;
j
M
k
j
b) деления на наземной станции каждой страницы на  символов, причем сообщение  спутниковой навигации делится на  ×  символов;
k
j
n
j
c) для каждой позиции символа, кодирования символов страниц на наземной станции путем кодирования каждого столбца символов страниц по отдельности для всех  блочных кодов, причем каждая из  страниц содержит символы из  параллельных кодов;
M’
n
d) формирования на наземной станции кодированного сообщения  спутниковой навигации для  страниц;
n
e) выделения на наземной станции по меньшей мере поднабора из  страниц кодированного сообщения спутниковой навигации каждому из множества спутников;
f) передачи с наземной станции выделенных страниц на соответствующие из множества спутников; и
g) передачи выделенных страниц с множества спутников на по меньшей мере один пользовательский приемник.
Таким образом можно добиться формирования кодированного сообщения спутниковой навигации в форме множества страниц, которые при передаче с множества спутников на пользовательский приемник можно декодировать с полной возможностью взаимной замены и с приемлемой стоимостью декодирования на пользовательском приемнике.
Согласно варианту осуществления, этап c) может дополнительно содержать использование схемы блочного кодирования, которая позволяет использовать любые k символов из n страниц для извлечения исходного сообщения спутниковой навигации.
Согласно варианту осуществления, блочные коды содержат коды Рида-Соломона.
Согласно варианту осуществления, этап d) может дополнительно содержать присоединение кода циклического контроля по избыточности к каждой странице для эмуляции двоичного канала со стиранием.
Это гарантирует, что прием страницы на пользовательском приемнике обрабатывается как на двоичном канале со стиранием.
В соответствии с другим аспектом настоящего изобретения, предусмотрен способ декодирования кодированного сообщения спутниковой навигации на по меньшей мере одном пользовательском приемнике, причем кодированное сообщение спутниковой навигации формируется и передаётся вышеописанным образом, причем способ содержит этапы:
i) приема на каждом из по меньшей мере одного пользовательского приемника страниц, передаваемых множеством спутников в поле зрения упомянутого каждого из по меньшей мере одного пользовательского приемника; и
j
ii) декодирования на упомянутом каждом из по меньшей мере одного пользовательского приемника кодированного сообщения спутниковой навигации из страниц принятых от множества спутников, посредством рекурсивного применения к ним процесса декодирования путем декодирования каждого столбца по отдельности для всех  блочных кодов.
Это позволяет декодировать кодированное сообщение спутниковой навигации с полной возможностью взаимной замены.
Согласно варианту осуществления, блочные коды содержат коды Рида-Соломона.
Согласно варианту осуществления, этап i) может дополнительно содержать прием разных страниц от разных из множества спутников.
Это дает преимущество в том, что сообщение может приниматься быстрее, чем в случае, когда все страницы принимаются от одного и того же спутника.
Согласно варианту осуществления, этап i) дополнительно содержит прием страниц последовательно по времени.
В соответствии с другим аспектом настоящего изобретения, предусмотрен пользовательский приемник, выполненный с возможностью декодирования кодированного сообщения спутниковой навигации, передаваемого в качестве разных страниц от множества спутников в его поле зрения, причем кодированное сообщение спутниковой навигации формируется и передается в соответствии с вышеописанным способом, причем пользовательский приемник содержит средства:
приема страниц, передаваемых множеством спутников в его поле зрения; и
j
декодирования кодированного сообщения спутниковой навигации из страниц, принятых от множества спутников, посредством рекурсивного применения к ним процесса декодирования путем декодирования каждого столбца по отдельности для всех  блочных кодов.
Такая конфигурация пользовательского приемника обеспечивает оптимальное извлечение кодированного сообщения спутниковой навигации с полной возможностью взаимной замены и с приемлемой стоимостью декодирования на пользовательский приемник.
Согласно варианту осуществления, блочные коды содержат коды Рида-Соломона.
В соответствии с еще одним аспектом настоящего изобретения, предусмотрена система спутниковой навигации для формирования, передачи и декодирования кодированного сообщения спутниковой навигации в форме множества страниц, причем система содержит:
множество спутников;
по меньшей мере один приёмник, как описано выше; и
наземную станцию, содержащую средство формирования кодированного сообщения спутниковой навигации в форме множества страниц для передачи на множество спутников, причем кодированное сообщение спутниковой навигации формируется путем:
M
k
деления сообщения  спутниковой навигации на страниц;
j
M
k
j
деления каждой страницы на  символов, причем сообщение  спутниковой навигации делится на  ×  символов;
k
j
для каждой позиции символа, кодирования символов страниц путем кодирования каждого столбца символов страниц по отдельности для всех  кодов Рида-Соломона;
M’
n
n
j
формирования кодированного сообщения  спутниковой навигации для  страниц, причем каждая из  страниц содержит символы из  параллельных кодов;
n
выделения по меньшей мере поднабора из  страниц кодированного сообщения спутниковой навигации каждому спутнику из множества спутников; и
передачи выделенных страниц на соответствующие спутники из множества спутников;
причём множество спутников содержит средства для передачи выделенных страниц на по меньшей мере один пользовательский приемник.
Такая система позволяет передавать сообщения или данные спутниковой навигации, которые имеют высокие отношения четности/данных.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Для лучшего понимания настоящего изобретения обратимся, в порядке примера, к сопровождающим чертежам, на которых:
фиг. 1 демонстрирует традиционную схему передачи сообщений спутниковой навигации, в которой данное сообщение спутниковой навигации делится на блоки (так называемое «разбиение сообщения»);
фиг. 2 демонстрирует традиционную схему передачи сообщений спутниковой навигации на основании смещения страницы, в которой каждый спутник передает одно и то же сообщение спутниковой навигации с разным смещением;
фиг. 3 демонстрирует способ передачи, в котором все символы в данной позиции на странице кодируются в отдельном коде;
фиг. 4 демонстрирует процесс приема на каналах с замиранием в котором 4-страничное сообщение спутниковой навигации кодируется в 12 страниц и передается 3 спутниками, и пользовательский приемник восстанавливает сообщение спутниковой навигации, принимая только 4 страницы.
Фиг. 5 демонстрирует реализации Рида-Соломона настоящего изобретения;
фиг. 6 демонстрирует сравнение между стоимостью декодирования способа настоящего изобретения и стоимостью декодирования традиционных способов;
фиг. 7a, 7b и 7c соответственно иллюстрируют сравнение между временем приема способа настоящего изобретения (указанным звездочками «*» черного цвета) и временем приема стандартного способа (указанным крестиками «+» серого цвета) для ситуации «открытого неба», ситуации «разреженной городской застройки» и ситуации «плотной городской застройки»; и
фиг. 8 демонстрирует схему для задания ID страницы сообщения спутниковой навигации на основании ID спутника передающего спутника и время, оба из которых заранее известны пользовательскому приемнику.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
Настоящее изобретение будет описано в отношении конкретных вариантов осуществления и со ссылкой на некоторый чертежи, но изобретение не ограничивается этим. Описанные чертежи являются лишь схематическими и неограничительными. В чертежах, в целях иллюстрации некоторые элементы могут быть изображены с нарушением масштабе в преувеличенном размере.
Следует отметить, что настоящее изобретение ставит перед собой задачу решения конкретных проблем, связанных с областью спутниковой навигации, которые могут не возникать в области спутниковой связи. В частности, данные спутниковой навигации, кодированные в соответствии с настоящим изобретением, в общем случае труднее принимать, чем сигналы чисто спутниковой связи. В общем случае, сигналы спутниковой связи принимаются на гораздо более высокой мощности (где сигналы спутниковой навигации принимаются на уровне примерно -155 дБ, то есть ниже уровня теплового шума). В результате, типичная скорость передачи данных сигналов спутниковой навигации составляет порядка 100 бит/с (50 бит/с для GPS L1C/A), что гораздо ниже обычный скорости передачи данных, используемой в системах спутниковой связи. Кроме того, сообщения спутниковой связи, в общем случае, передаются от единственного источника, и сигналы спутниковой навигации и данные должны быть доступны на упомянутой низкой мощности статическим и динамическим пользователям во всех окружениях, в том числе воздушном, морском и наземным, причем последнее включает в себя крону дерева и городские ущелья.
При низких скоростях приема данных в системах спутниковой навигации, настоящее изобретение решает проблему передачи длинных сообщений, например, порядка тысяч или десятков тысяч битов, причем эти сигналы должны приниматься в ухудшенных окружениях посредством очень высокой избыточности данных, но в отсутствие издержек и при низкой сложности декодирования, чего не позволяют достичь традиционные способы. Стандартные реализации кода RS (или аналогичные) обеспечивают очень низкую четность относительно необходимой для решения проблемы настоящего изобретения. Обычно настоящее изобретение требует отношения четности/данных от 1/10 до 1/6 для уже длинного сообщения. Хотя этого можно добиться с помощью кодов RS (или аналогичных) с более длинными символами, например, 16 битов, эти реализации не стандартны и труднее для декодирования на пользовательском приемнике. В частности, способ настоящего изобретения применяется к длинным сообщениям с высоким отношением четности/данных, необходимым для решения конкретной проблемы передачи длинных сообщений при спутниковой навигации со слабыми сигналами в ухудшенных окружениях, то есть с потенциально очень высокими коэффициентами ошибок.
Кроме того, фундаментальное отличие от уровня техники состоит в том, что способ настоящего изобретения предусматривает использование параллельной обработки на «межсимвольном»” уровне, то есть для нескольких символов, а не на «внутрисимвольном» уровне, то есть на уровне битов. Действуя на уровне полных символов, можно распараллеливать коды в необходимом количестве. Способ настоящего изобретения предусматривает распараллеливание 54, то есть (448-16)/8 векторов, чего не позволяют делать способы, известные из уровня техники.
Используя межсимвольное распараллеливание, можно сделать способ декодирования сообщений или сигналов спутниковой навигации более гибким.
Кроме того, по сравнению с системами спутниковой связи, системы спутниковой навигации должны передавать сообщения с очень высокой степенью избыточности, чтобы скомпенсировать высокие коэффициенты ошибок, и передавать эти сообщения от более чем одного источника или спутника.
Используемый здесь термин «открытое небо» означает окружение, где сигналы от четырех передающих спутников принимаются с коэффициентом ошибочных страниц 0,5% для каждого спутника.
Используемый здесь термин «разреженная городская застройка» означает окружение, в котором сигналы от четырех передающих спутников принимаются с коэффициентами ошибочных страниц 0,5%, 1%, 10% и 20% соответственно для четырех спутников.
Используемый здесь термин «плотная городская застройка» означает окружение, в котором сигналы от двух передающих спутников принимаются с коэффициентом ошибочных страниц 10% и 20% соответственно для двух спутников.
Термин «канал с замираниями» означает связь, испытывающую переменное ослабление сигнала в зависимости от ряда факторов, например, времени, географического положения и радиочастоты.
Термин “C/NAV” означает коммерческие навигационные сообщения, широковещательно передаваемые спутниками Galileo на частоте E6.
Термин “I/NAV” означает навигационные сообщения контроля целости, широковещательно передаваемые спутниками Galileo на частотах E1 и E5.
Термин «отношение четности/данных» означает отношение количества битов четности к количеству битов информации в кодированном сообщении.
Термины «блочные коды» или «схемы блочного кодирования» означают коды или схемы кодирования, позволяющие обеспечить распараллеливание. Настоящее изобретение описано в отношении кодов Рида-Соломона, но не ограничено этим. Например, также можно реализовать схему кодирования Боуза - Чоудхури - Хоквингема (BCH).
Термин «двоичный канал со стиранием» или “BEC” означает модель общего канала связи, в которой передатчик отправляет бит (“0” или “1”), и приемник принимает либо бит, либо сообщение о том, что бит не принят или «стерт». В действительности, пакеты битов передаются передатчиком, и приемник либо принимает пакет, либо пакет стирается. Согласно настоящему способу, страница C/NAV проверяется на CRC и отбрасывается, если не проходит CRC.
На фиг. 1 показан подход, предложенный в статье “European GNSS (Galileo) Open Service Signal In Space Interface Control Document, (OS SIS ICD V1.3)”. На фиг. 1 показана система 10 спутниковой навигации, содержащая пользовательский приемник 12 и три спутника 14, 16, 18. Как показано, каждый спутник 14, 16, 18 передает сообщение спутниковой навигации на пользовательский приемник 12 в двух четырехстраничных фрагментах. Это называется разбиением сообщения. Два четырехстраничных фрагмента обозначены 14a и 14b, 16a и 16b, и 18a и 18b от соответствующих спутников 14, 16 и 18. При этом блочные данные кодируются взаимозаменяемо, что позволяет любой странице вносить вклад в них; однако вследствие нарушений канала, пользовательский приемник 12 принимает только блоки, обозначенные серым цветом. В этом примере пользовательский приемник 12 не сможет принимать все фрагменты 14a, 14b, 16a 16b, 18a и 18b от любого из спутников 14, 16, 18, и таким образом, не сможет декодировать сообщение спутниковой навигации. Однако, если бы страницы были полностью взаимозаменяемыми, как описано ниже, можно было бы декодировать сообщение спутниковой навигации, как будет более подробно описано ниже.
Как описано выше, смещение страницы не позволяет оптимально восстанавливать сообщения спутниковой навигации. Фиг. 2 демонстрирует систему 20 спутниковой навигации, которая аналогична системе 10, показанной на фиг. 1, и содержит пользовательский приемник 22 и три спутника 24, 26, 28. Однако в этом случае каждый спутник 24, 26, 28 передает 4-страничное сообщение спутниковой навигации со смещением страницы 0, 1, 2 соответственно. В этом примере пользовательский приемник принимает только половину страниц (обозначенные серым цветом) от каждого из спутников, и таким образом не сможет принимать полное сообщение спутниковой навигации. Как упомянуто выше со ссылкой на фиг. 1, если все страницы взаимозаменяемы, сообщение спутниковой навигации может приниматься за 2 секунды.
Однако одного лишь смещения страницы мало для осуществления приема, поскольку пользовательскому приемнику приходится ожидать повторной широковещательной передачи сообщения спутниковой навигации, по возможности, с соответствующей задержкой. Системе неизвестно, какие спутники видны каждому пользовательскому приемнику, и всегда найдутся пользователи, принимающие комбинацию страниц, которая не позволяет успешно декодировать или демодулировать сообщение спутниковой навигации.
M
k
M
M
1
k
Проблему, которую призвано решать настоящее изобретение, можно математически определить следующим образом: пусть в услуге высокой точности предусмотрено сообщение  спутниковой навигации (HAS), состоящее из страниц (, …, ), подлежащее передаче несколькими навигационными спутниками в данный момент времени по двоичному каналу со стиранием, то есть каналу, на котором страница C/NAV либо принимается правильно, либо отбрасывается. BEC моделируется путем проверки CRC страницы C/NAV и отбрасывания страницы, не прошедшей проверку CRC.
M
C
n
C
C
n
k
C
M
1
n
Сообщение  спутниковой навигации кодируется в кодированное сообщение спутниковой навигации , состоящее из  страниц, (, …, ), где  > k, и передается одновременно множеством спутников, благодаря чему любые  извлеченных страниц , принятого от любого спутника, позволяют декодировать исходное сообщение  спутниковой навигации, обеспечивая полную взаимозаменяемость страниц при приеме сообщения спутниковой навигации. Способ должен быть применим для разных длин сообщения, и процесс декодирования должен быть приемлемый на пользовательском приемнике.
Способ настоящего изобретения базируется на следующих этапах и предусматривает использование параллельной обработки на межсимвольном уровне таким образом, что не существует ограничения:
M
k
M
M
1
k
- разделить сообщение  спутниковой навигации на страниц (, …, )
j
M
k
j
w
w
1,1
k
,
j
- разделить каждую страницу на  символов таким образом, что полное сообщение  спутниковой навигации делится на  ×  символов (, …, )
c
j
k
w
w
w'
w'
k
n
1,
c
k
,
c
1,
c
n
,
c
- для каждой позиции символа =1, …, , кодировать символы страниц (, …, ) в (, …, ) согласно схеме блочного кодирования, в которой любые  символов из  кодированных символов может использоваться для извлечения исходного сообщения спутниковой навигации
M'
w'
w'
n
j
1,1
n
,
j
- формировать полное кодированное сообщение спутниковой навигации (, …, ), состоящее из  страниц, где каждая страница состоит из символов из  параллельных кодов
- присоединить CRC или аналогичную проверку к каждой странице, чтобы прием страницы обрабатывался как на двоичном канале со стиранием
n
M'
- выделить  страниц из , или их поднабор, разным спутникам, и передавать сообщение спутниковой навигации через спутники, чтобы каждый спутник передавал разные страницы
k
M'
M
j
- на стороне пользовательского приемника, в случае успешного приема страниц из  от любого из видимых спутников, декодировать сообщение  спутниковой навигации посредством рекурсивного применения процесса декодирования  раз.
n
C
C
w
w
j
j
w
w
w
w
j
C
C
k
j
1
n
1,1
n
,
j
1,1
n
,1
1,2
n
,2
i
=1,
n
i
На фиг. 3 показан процесс кодирования и выделения сообщения на спутник, где  страниц (, …, ) кодируются в символах  - , где  - суммарное количество символов на странице C/NAV. Например,  может быть равно 52 для 448 битов за минусом 16-битового заголовка. Вместо использования одного и того же кода RS для всех символов в сообщении спутниковой навигации, каждый столбец (, …, ; , …, ; и т.д.) кодируется и декодируется по отдельности для всех  кодов RS. Страницы , или их поднабор, передаются последовательно по времени разными спутниками, что позволяет пользовательскому приемнику идентифицировать каждую . Когда пользовательский приемник принимает страниц,  кодов будут декодироваться для обеспечения сообщения спутниковой навигации с использованием распараллеливание на межсимвольном уровне.
На фиг. 4 показан процесс приема на каналах с замиранием, где 4-страничное сообщение спутниковой навигации кодируется в 12 страниц и передается 3 спутниками, и приемник восстанавливает сообщение спутниковой навигации, принимая только 4 страницы. На фиг. 4 показана система спутниковой навигации 100, которая содержит пользовательский приемник 110 и три спутника 120, 130, 140. Каждый спутник 120, 130, 140 передает четыре страницы на пользовательский приемник 110. Однако вследствие замирания на каналах, пользовательский приемник 110 принимает только страницы, обозначенные серым цветом, и эти страницы используются для декодирования и восстановления исходного 4-страничного сообщения спутниковой навигации.
k
n
n
k
Коды Рида-Соломона позволяют восстанавливать сообщения спутниковой навигации с любыми  символами из  переданных символов. Таким образом, один вариант осуществления настоящего изобретения базируется на кодировании Рида-Соломона. Для достижения полной взаимозаменяемости страниц с множеством спутников,  должно быть гораздо больше , то есть сообщение спутниковой навигации должно кодироваться большим объемом данных четности, поэтому разные спутники не передают одни и те же страницы. Это описано Весталлом и др. в “An introduction to Galois Fields and Reed-Solomon Coding”, School of Computing Clemson University, SC (2010): 29634-1906.
На основании современных оценок максимального размера сообщения для сообщения точного точечного позиционирования (PPP), передаваемого в сигналах E6B Galileo на 448 бит/с, можно предположить, что:
k
max
- максимальная длина сообщения спутниковой навигации () составляет 20 страниц или 8640 битов или 1080 байтов (например, ионо-сообщения), где каждая страница может обеспечивать 432 бита (54 байта), плюс 16 битов для заголовка, используемого для идентификации информации, содержащейся в странице, для всех 448 битов.
- возможности группировки Galileo предусматривают максимум 20 передающих спутников, для чего требуется отношение четности/данных 20/1.
m
m=
m=
m=
m
Однако для снижения величины отношения четности/данных 20/1, можно предположить, что спутники в противоположных положениях на орбите не могут наблюдаться одним и тем же пользовательским приемником. Это уже снижает избыточность наполовину (с 20 до 10). Другие предположения состоят в том, что спутники могут быть равномерно распределены в небе, и что, при чистом небе, приемник на Земле может видеть самое большее 1/3 20 соединенных спутников Galileo. В этом случае, сообщение RS может иметь отношение четности/данных 6/1 для всех (данные+четность) 7560 байтов. Однако большинство стандартных подходов к кодированию RS опирается на GF(2), где 8, и это означает, что может кодироваться не более 256 байтов. Возможны другие реализации с 16 или 32, но они усложняют арифметику поля Галуа (в особенности перемножение полиномов для =32), увеличивая стоимость декодирования на приемнике и требования к хранилищу.
На фиг. 5 приведены некоторые примеры сообщений разной длины, до 20 страниц. В первом примере, 20-страничное сообщение передается с кодовой скоростью 1/5, что гарантирует взаимозаменяемость страниц для до 5 спутников в секторе обзора пользовательского приемника. 100 сообщений из 8-битовых символов кодируется состоящих 20 символами данных и 80 символами четности, что хорошо согласуется со многими кодами RS, например, RS(255,161,8), как описано Чуном и др. в “End-to-end system consideration of the Galileo image compression system” (International Geoscience and Remote Sensing Symposium, Vol.2, Institute of Electrical & Electronics Engineers, INC (IEE), 1996). Избыточные информационные символы будут заполняться нулями (например, в 20-страничном примере, из 161 символов данных, будет использоваться только 20, и 141 будет заполняться нулями) как описано Б.Е. Шотшем в “Specification of Outer Reed-Solomon Encoding of the CED in the Galileo E1 I/NAV Message”, 2017.
Во втором примере, 16-страничное сообщение спутниковой навигации передается с кодовой скоростью 1/6. 96 сообщений из 8-битовых символов кодируются 16 символами данных и 80 символами четности, причем избыточные информационные символы заполняются нулями. В третьем примере, 10-страничное сообщение спутниковой навигации передается с кодовой скоростью 1/8. 80 сообщений из 8-битовых символов кодируются 10 символами данных и 70 символами четности, причем избыточные информационные символы заполняются нулями.
В четвертом примере с меньшей избыточностью, согласно вышеупомянутой статье Шотша, 18-страничное сообщение спутниковой навигации передается с кодовой скоростью 1/4 с кодом RS I/NAV, RS(255,195,8), которая обеспечивает 60-символьную четность.
j
k
k
k
k
k
k
3
2
Одним из преимущества способа настоящего изобретения, по сравнению со стандартным кодированием RS в единственном коде, является значительно более низкая стоимость декодирования. Повторение процесса декодирования  раз линейно увеличивает стоимость декодирования относительно одноитерационного декодера, но поскольку сообщение спутниковой навигации гораздо короче, стоимость декодирования экспоненциально снижается. Стоимость декодирования оценивается как стоимость инверсии матрицы × и стоимость решения линейной системы ×. Стоимость инверсии матрицы обычно оценивается как O(), что равно стоимости метода исключения Гаусса. Стоимость решения линейной системы оценивается как O().
k
k=
На фиг. 6 показано сравнение со стандартными способами. Сравнение базируется на длине страницы данных 432 бита и размерах сообщения =20 и 4. Выбраны три реализации:
m
n=
m
n
8
8
16
- единственный код RS для всего сообщения спутниковой навигации. =8 для короткого сообщения (216<2), и =16 для длинного сообщения (2< < 2). Это называется “Стандарт 1”.
- реализация на основе разбиения сообщения спутниковой навигации на 5 фрагментов по 4 страницы, где каждый фрагмент кодируется по отдельности. Это называется “Стандарт 2”.
- способ настоящего изобретения называется “MRSC” (множественное кодирование RS).
m
k
k
k
m
3
2
На фиг. 6  выражает размер символа (размер GF равен 2), «макс. страниц/код» выражает количество страниц C/NAV, которые кодируются (полностью или частично, в случае MRSC) кодом RS; «Парал. кодов/сообщ.» это количество кодов RS, которые параллельно кодируют данное сообщение спутниковой навигации; «фрагментов» - это количество кодов RS, которые кодируют данное сообщение спутниковой навигации; «кодов» - это суммарное количество кодов для сообщения спутниковой навигации, “” это суммарное количество байтов, кодированных одним кодом; и «Опер. декод./ код» - это количество операций декодирования на код (O()+ O()). Как показано, реализация настоящего изобретения (MRSC) имеет гораздо более низкую стоимость декодирования, чем другие реализации («Стандарт 1» и «Стандарт 2») для одного и того же сообщения спутниковой навигации.
Другим преимуществом способа настоящего изобретения является повышение возможностей приема в условиях замирания. На фиг. 7a - 7c показан прием 20-страничного сообщения спутниковой навигации посредством MRSC по сравнению с эквивалентным традиционным способом в пяти 4-страничных фрагментах. Каждую из фиг. 7a - 7c моделировали с использованием прогона по методу Монте-Карло для 5000 экземпляров, измеряя в каждом случае время на декодирование сообщения спутниковой навигации.
Фиг. 7a демонстрирует сравнение между временем приема согласно способу настоящего изобретения, указанным как «*» черного цвета, и временем приема согласно способу 4 страниц/5 фрагментов, указанным как «+» серого цвета, для случая «открытого неба» с четырьмя спутниками в секторе обзора пользовательского приемника. Согласно традиционному способу, последовательность фрагментов оптимизируется таким образом, что спутники передают дополняющие последовательности фрагментов для пользовательских приемников. Для каждого из четырех спутников был получен коэффициент ошибочных страниц 0,5%.
Фиг. 7b аналогична фиг. 7a, но иллюстрирует случай «разреженной городской застройки» с четырьмя спутниками в секторе обзора пользовательского приемника. Для соответствующих спутников были получены коэффициенты ошибочных страниц 1%, 5%, 10% и 20%.
Фиг. 7c аналогична фиг. 7a и 7b, но иллюстрирует случай «плотной городской застройки» только с двумя спутниками в секторе обзора пользовательского приемника. Для соответствующих спутников были получены коэффициенты ошибочных страниц 10% и 20%.
Как показано на фиг. 7a - 7c, способ по настоящему изобретению значительно повышает надежность приема сообщений, и сообщение спутниковой навигации принимается гораздо быстрее.
Конкретная реализация способа настоящего изобретения может опираться на тот факт, что каждая страница включает в себя заголовок, с полем ID сообщения, полем длины сообщения и полем ID страницы.
Другая конкретная реализация, в которой размер заголовка уменьшен, может опираться на задании матрицы спутник/время для данных количества спутников и времени, что позволяет задавать поле ID страницы из матрицы, вместо того, чтобы занимать место в заголовке, что дает возможность иметь длинные кодированные сообщения спутниковой навигации. Это проиллюстрировано на фиг. 8.
Фиг. 8 демонстрирует, как следует идентифицировать страницы сообщения, состоящего самое большее из (n+1)*T страниц, просто идентифицируя спутниковую идентификацию (n) и время (от 1 и T) без необходимости передавать эту информацию в заголовке.
Еще одна конкретная реализация может включать в себя заголовок страницы, где схема кодирования, согласно которой кодируется сообщение спутниковой навигации, задается в заголовке, что позволяет использовать множество схем.
Еще одна конкретная реализация включает в себя кодирование сообщения высокой точности на основании группирования подтипов сообщения в 3 сообщениях: одно сообщение для маски спутника, корректировок орбиты, смещений и точности определения дальности пользователя (URA); одно сообщение для ионосферных корректировок; и одно сообщение для корректировок часов спутника, состоящее из 1-3 страниц, в зависимости от количества спутников в маске спутника.
Другие реализации включают в себя другие блочные коды, отличные от RS, или другие длины символов, отличные от 8 битов (например, 16 битов или 32 бита, поскольку обе доступны для RS).
В другой реализации, кодированное сообщение спутниковой навигации является не сообщением высокой точности, а другим общим сообщением спутниковой навигации, передаваемым группировкой GNSS, например, цифровой подписью или альманахом.
Еще одна реализация позволяет перемежать несколько разных сообщений спутниковой навигации от разных спутников по времени. Это означает, что, вместо передачи одного сообщения в данный интервал времени, система может передавать множество сообщений в течение этого интервала времени, и заголовок конкретного сообщения идентифицирует это сообщение с помощью конкретного ID сообщения.