Способы кодирования и декодирования с дифференцированной защитой
METHODS OF ENCODING AND DECODING WITH DIFFERENTIATED PROTECTION

Настоящее изобретение относится к технологии цифровых телекоммуникаций и, точнее, к технологии кодирования канала, которое предполагает использование корректирующих кодов с целью увеличения уровня избыточности передаваемой информации, так, чтобы иметь возможность восстановить изначально созданное сообщение, несмотря на ошибки, возникающие во время передачи этого сообщения через несовершенный канал распространения.
Более конкретно, изобретение относится к области корректирующих кодов, таких как коды LDPC (Low Density Parity Codes (Код с малой плотностью проверок на четность)), или корректирующие коды любого другого типа, которые могут быть представлены в виде двухдольного графа, называемого графом Таннера.
Изобретение относится к способу кодирования и к способу декодирования, позволяющему применить дифференцированную защиту к передаваемым данным в зависимости от различных уровней приоритета.
Изобретение преимущественно применимо к стандартам спутниковой радионавигации или стандартам GNSS (Глобальная Навигационная Спутниковая Система), таким как стандарты GPS или Галилео.
Стандарты GNSS задают характер сообщений GNSS, которые передаются посредством кадров данных. Такие сообщения включают в себя данные, относящиеся к информации позиционирования, например, координаты спутников, информацию о хронометрах спутника, служебные данные или данные о целостности. В существующих стандартах, эти данные защищены простым корректирующим кодом, который применяется непосредственно к целому кадру данных. Этот метод имеет неудобство в том, что не позволяет тонкую оптимизацию компромисса между пропускной способностью, ограничиваемой добавлением корректирующего кода, и уровнем необходимой защиты.
Действительно, данные, передаваемые в кадре GNSS, имеют различный характер и могут быть классифицированы в несколько групп, представляющих различные уровни приоритета. Под уровнем приоритета здесь подразумевается уровень приоритета в смысле критичности передаваемых данных. Некоторые данные оказываются важнее других и, таким образом, требуют больший уровень защиты корректирующим кодированием, чтобы обеспечить корректную их передачу с уровнем надежности, соответствующим уровню приоритета.
Изобретение может быть применено подобным же образом к другим системам передачи данных, для которых имеется возможность перегруппировать данные в некоторые совокупности, имеющие различные уровни приоритета.
Изобретение предлагает способ кодирования с дифференцированной защитой, которая позволяет защитить с различной степенью защиты некоторые группы данных в передаваемом кадре данных.
Изобретение в связи с этим базируется на применении корректирующего кода, типа кода LDPC, логически связанного с алгебраическим корректирующим кодом.
Изобретение предлагает также способ декодирования, совместимый со способом кодирования с дифференцированной защитой.
Способы в соответствии с изобретением преимущественно применимы к системам передачи данных, для которых данные форматируются в кадры малой длительности, обычно порядка нескольких сотен битов. В частности, изобретение применимо к защите данных, передаваемых в системе GNSS.
Изобретение имеет целью способ кодирования с дифференцированной защитой, применяемый к кадру, включающему в себя набор битов, кодирования, осуществляемого, по меньшей мере, начиная с первого систематического корректирующего кода, типа кода LDPC, представленный двудольным графом, называемым графом Таннера, включающим в себя множество первых вершин, называемых переменными вершинами, упомянутым графом, включающим в себя дополнительно множество вторых вершин, называемых проверочными вершинами, причем каждая переменная вершина соединяется, по меньшей мере, с одной проверочной вершиной посредством ребра, причем число ребер, связанных с переменной вершиной, называется степенью переменной вершины, в котором каждая переменная вершина связана с битом слова упомянутого первого кода, причем переменные вершины, связанные с систематическими битами слова первого кода называются систематическими переменными вершинами, причем упомянутый способ включает в себя следующие этапы:
- Разложение кадра на множество подкадров, каждый из которых имеет различный уровень приоритета,
- Применение к каждому полученному подкадру, исключая подкадр самого низкого уровня приоритета, второго алгебраического корректирующего кода заданной производительности, причем упомянутая производительность повышается с понижением уровня приоритета каждого подкадра, когда число подкадров, по меньшей мере, равно трем,
- Применение чередования битов всех подкадров, так, чтобы осуществить соответственное размещение между систематическими переменными вершинами упомянутого первого систематического корректирующего кода, располагаемыми в соответствии со значением их степени, и битами каждого подкадра, причем подкадры располагаются в соответствии с их уровнем приоритета,
- Кодирование, с помощью первого систематического корректирующего кода, кадра, составленного из чередующихся битов всех логически связанных подкадров.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, биты каждого подкадра поставлены в соответствие с систематическими переменными вершинами упомянутого первого систематического корректирующего кода, расположенными в порядке возрастания значения их степени в соответствии с порядком понижения уровней приоритета подкадров.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, биты каждого подкадра поставлены в соответствие с систематическими переменными вершинами упомянутого первого систематического корректирующего кода, расположенными в порядке возрастания значения их степени в соответствии с порядком возрастания уровней приоритета подкадров.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, первый систематический корректирующий код построен так, что пропорция систематических переменных вершин со степенью, равной максимальной степени, равна отношению между числом битов подкадра наиболее высокого уровня приоритета и числом битов слова упомянутого первого систематического корректирующего кода.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, разложение кадра на подкадры осуществляется переупорядочиванием битов кадра в соответствии с их уровнем приоритета.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, уровень приоритета бита определяют в зависимости от критичности информации, связанной с битом, веса бита или частоты обновления информации, связанной с битом.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, данные, передаваемые в кадре, представляют собой данные навигационного сообщения спутника, созданные системой спутниковой радионавигации.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, второй алгебраический корректирующий код представляет собой код BCH.
Изобретение также имеет целью способ декодирования с дифференцированной защитой, применяемый к кодированного кадру, включающему в себя набор битов, кодированных с помощью способа кодирования с дифференцированной защитой в соответствии с изобретением, причем способ декодирования включает в себя следующие этапы:
- Осуществление первого декодирования кадра, кодированного с помощью первого алгоритма декодирования первого систематического корректирующего кода, типа кода LDPC, на основании использования двухдольного графа, так, чтобы получить первый декодированный кадр,
- Разложение первого кадра, декодированного в подкадры, причем каждый подкадр содержит биты, соответствующие систематическим переменным вершинам, расположенным в соответствии со значением их степени, причем подкадры расположены в соответствии с их уровнем приоритета,
- Осуществление второго декодирования каждого полученного подкадра, за исключением кадра самого низкого уровня приоритета, с помощью второго алгоритма декодирования второго алгебраического корректирующего кода заданной производительности, упомянутой производительности, повышающейся с понижением уровня приоритета каждого подкадра, когда число подкадров, по меньшей мере, равно трем.
Способ декодирования с дифференцированной защитой в соответствии с изобретением может включать в себя дополнительно этап логической связи подкадров во втором декодированном кадре.
В соответствии с частным объектом способа декодирования в соответствии с изобретением, второй корректирующий код представляет собой корректирующий и обнаруживающий ошибки код, причем упомянутый способ декодирования включает в себя дополнительно следующие этапы:
- Во время второго декодирования каждого подкадра, обнаружение, корректно ли декодирован подкадр, или нет,
- Если подкадр декодирован корректно, то
i. Кодирование, с упомянутым вторым алгебраическим корректирующим кодом, каждого декодированного подкадра для получения кодированного подкадра,
ii. Применение второй итерации первого декодирования, указывая, в алгоритме декодирования упомянутого первого систематического корректирующего кода максимальное правдоподобие для битов каждого кодированного подкадра.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, второй алгебраический корректирующий код представляет собой код BCH.
В соответствии с частным объектом способа кодирования в соответствии с изобретением, декодирование первого систематического корректирующего кода и декодирование второго алгебраического корректирующего кода осуществляются совместно.
Изобретение также имеет целью предоставление кодирующего устройства, сконфигурированного для выполнения этапов способа кодирования с дифференцированной защитой в соответствии с изобретением, декодирующее устройство, сконфигурированное для выполнения этапов способа декодирования с дифференцированной защитой в соответствии с изобретением, передатчик сигналов спутниковой радионавигации, включающий в себя кодирующее устройство в соответствии с изобретением для кодирования дифференцированным образом сообщений спутниковой радионавигации, и приемник сигналов спутниковой радионавигации, включающий в себя декодирующее устройство в соответствии с изобретением для декодирования дифференцированным образом сообщений спутниковой радионавигации.
Другие характеристики и преимущества настоящего изобретения будут лучше видны из чтения нижеследующего описания, представленного в связи с приложенными чертежами, на которых представлено:
- Фиг. 1 изображает структурную схему, описывающую способ кодирования с дифференцированной защитой в соответствии с изобретением,
- Фиг. 2 - структурная схема, описывающая способ декодирования с дифференцированной защитой в соответствии с изобретением и в соответствии с первым вариантом реализации,
- Фиг. 3 - структурная схема, описывающая способ декодирования с дифференцированной защитой в соответствии с изобретением и в соответствии со вторым вариантом реализации,
- Фиг. 4 - диаграмма, иллюстрирующая показатели изобретения в долях ошибочных битов и долях ошибочных кадров зависимости от отношения сигнал-шум,
- Фиг. 5 - блок-схема, описывающая составляющие элементы кодера с дифференцированной защитой в соответствии с изобретением,
- Фиг. 6 - блок-схема, описывающая составляющие элементы декодера с дифференцированной защитой в соответствии с изобретением,
- Фиг. 7 - блок-схема передатчика, включающего в себя кодер с дифференцированной защитой в соответствии с изобретением,
- Фиг. 8 - блок-схема приемника, включающего в себя кодер с дифференцированной защитой в соответствии с изобретением.
На Фиг. 1 представлена блок-схема, иллюстрирующая последовательность этапов выполнения способа кодирования с дифференцированной защитой в соответствии с изобретением.
c
Способ принимает на входе кадр T, включающий в себя набор битов, и производит на своем выходе кодированный кадр T для его передачи по радиоканалу, например, по каналу спутниковой связи.
В соответствии с первым этапом 101, назначается уровень приоритета для данных, передаваемых в кадре T.
Уровень приоритета каждого бита выбирается в зависимости от значимости информации, содержащейся в этом бите. Иначе говоря, высокий уровень приоритета назначается для битов, которые должны быть получены в первую очередь. Высокий уровень приоритета означает, что соответственные биты должны быть защищены корректирующим кодом с меньшей производительностью защиты для увеличения уровня защиты этих битов, так, чтобы увеличить вероятность корректного их приема после передачи через радиоканал.
И наоборот, низкий уровень приоритета может быть присвоен битам, которые не требуют повышенной вероятности корректного их приема и которые могут быть переданы без добавления защиты корректирующим кодом или защиты с помощью корректирующего кода с высокой производительностью защиты.
В рамках применения изобретения к кадру данных GNSS, уровень приоритета может быть присвоен битам кадра с учетом следующих ограничений. Во-первых, уровень приоритета может быть зафиксирован в зависимости от типа передаваемой информации. Действительно, у всей передаваемой информации нет одинакового уровня критичности.
Во-вторых, можно назначить более высокий уровень приоритета для битов с большим весом данных, определяемых количественно для дифференциации применяемой защиты в зависимости от уровня количественного определения данных. И наоборот, биты малого веса могут быть связаны с низким уровнем приоритета, поскольку они менее значимы и, таким образом, не требуют высокой вероятности корректного приема.
Наконец, некоторая информация повторяется во времени с большей или меньшей частотой обновления. Высокий уровень приоритета может быть присвоен информации, которая никогда не повторяется, или которая повторяется с малой частотой. И наоборот, для информации, повторяющейся с большой частотой, можно присвоить низкий уровень приоритета.
Приведенные выше примеры присвоения уровней приоритета битам кадра T служат иллюстративным целям и не являются ограничительными. Специалист в данной области техники, желающий применить изобретение к конкретному стандарту, сможет выбрать другие методики определения уровней приоритета в зависимости от имеющихся потребностей. Общая идея в применении этапа 101 заключается в том, чтобы определить высокий уровень приоритета для битов, которые требуют большой вероятности корректного приема и определить низкий уровень приоритета для битов, которые предоставляют меньше ограничений для корректного их приема.
Уровень приоритета может быть целым значением, меняющимся в данном диапазоне, например между 0 и M - строго положительным целым числом, причем 0 будет наиболее низким уровнем приоритета, и M - наиболее высоким уровнем приоритета.
t
t
t
t
На втором этапе 102, кадр T разлагается на N подкадров, перегруппируя в каждом подкадре биты эквивалентного уровня приоритета. Например, если N равно двум, этап 102 заключается в том, чтобы перегруппировать в первый подкадр биты наиболее высокого уровня приоритета, и во второй подкадр - биты наиболее низкого уровня приоритета. Если N составляет более двух, биты располагаются в зависимости от их растущего уровня приоритета и строится N подкадров, включающих в себя каждый из битов, имеющих идентичные или близкие уровни приоритета. Разложение 102 кадра T на подкадры может быть выполнено, фиксируя идентичные длины подкадров или перегруппировывая в подкадре биты, имеющие один и тот же уровень приоритета, и в этом случае подкадры могут иметь различные длины.
На третьем этапе 103, полученные подкадры разуплотняются для обработки каждого из них посредством первой операции канального кодирования, различного для каждого подкадра. Пример на Фиг. 1 ограничен созданием двух подкадров, но легко может быть распространен на число подкадров, большее двух.
0
Подкадр ST, перегруппирующий биты наиболее низких уровней приоритета, изначально не подвергается операции канального кодирования и непосредственно передается на этап 106 мультиплексирования.
1
1
Подкадр ST, перегруппирующий биты наиболее высоких уровней приоритета, передается на этап 104 канального кодирования, которое заключается в применении к подкадру ST алгебраического корректирующего кода, например, корректирующего кода BCH.
t
t
Если число N более двух, создаются подкадры, алгебраический корректирующий код, такой как код BCH, применяется к N-1 подкадрам, включающим в себя биты наиболее высоких уровней приоритета. Каждый корректирующий код применяется с различной и возрастающей степенью защиты с понижением среднего уровня приоритета каждого подкадра. Подкадр наиболее низкого среднего уровня приоритета передается без кодирования непосредственно на этап 106 мультиплексирования.
В качестве примера, если рассматривать три подкадра, использованные производительности кодирования могут быть равными, например, 0, 2/3 и 3/4 соответственно.
Совокупность подкадров затем мультиплексируются, на этапе 105, для восстановления кадра такого же формата, как и кадр T, принятый на входе первого этапа 101. Этот восстановленный кадр затем кодируется, на этапе 106, вторым корректирующим кодом. Второй корректирующий код представляет собой такой корректирующий код как код LDPC (Low Density Parity Code), или любой корректирующий код, который может быть представлен с помощью двухдольного графа, называемого графом Таннера.
Издание [1] по ссылке и, в частности, глава 5, озаглавленная "Low-density parity-check codes", подробно описывает конструирование и представление корректирующего кода, типа LDPC, с помощью двухдольного графа, называемого графом Таннера.
Граф Таннера составлен из двух типов вершин. Вершина первого типа называется переменной вершиной или, на английском языке "variable node", или также "code-bit node" в соответствии с применением. Переменные вершины, каждая, связаны с битом кодового слова. Таким образом, имеется столько же переменных вершин сколько битов в декодируемом кодовом слове. Каждая переменная вершина соединяется с одним или несколькими проверочными вершинами, называемыми на английском языке "check nodes" или "constraint nodes". Число проверочных вершин равно числу строк матрицы паритета корректирующего кода. Число переменных вершин равно числу столбцов матрицы паритета. Проверочная вершина с индексом i соединяется с переменной вершиной с индексом j, если, и только если, элемент строки i и столбца j матрицы паритета кода равен 1. Соединение между переменной вершиной и проверочным вершиной называется ребром. Число соединений, начинающихся от вершины - это степень вершины.
U
P
P
U
P
U
P
P
U
P
U
Корректирующий код, используемый на этапе 106 для кодирования мультиплексированного кадра, также должен быть систематическим корректирующим кодом. Код этого типа описан, например, в главе 6.5.2 издания [1], которая относится к кодам, называемым "Irregular Repeat-Accumulate Codes", также называемыми кодами IRA. Такие коды обычно создаются исходя из матрицы паритета в виде H=[H H]. Матрица H - это квадратная матрица размерности m×m, где m - число вершин проверочного кода. Матрица H - это матрица с m строками и n-m столбцами, с R=m/n производительностью кода. Матрица H - это так называемая би-диагональная матрица, форма которой дана на странице 269, соотношение (6.4) издания [1]. Как указано выше, число переменных вершин равно числу столбцов матрицы паритета H. В случае систематических кодов IRA, можно различать переменные вершины, связанные со столбцами матрицы H, и переменные вершины, связанные со столбцами матрицы H. Эти последние соответствуют систематическим битам кодового слова и далее называются систематическими переменными вершинами. Систематические биты - это полезные биты на входе операции кодирования, в противоположность битам паритета, которые являются избыточными битами, добавляемыми операцией кодирования. Альтернативно, матрица паритета H может также иметь вид H=[H H], при этом выбор порядка между матрицами H и H определяется соглашением.
Снова переходим к описанию способа кодирования в соответствии с изобретением. На дополнительном этапе 105, выполняемом после этапа 104 и до этапа 106, подкадры, кодированные применением алгебраического корректирующего кода на этапе 104, чередуются с помощью устройства организации чередования, которое имеет в качестве функции помещение в соответствие битов кодированных подкадров с систематическими переменными вершинами двухдольного графа систематического корректирующего кода LDPC. Помещение в соответствие зависит, с одной стороны, от среднего уровня приоритета подкадра и, с другой стороны, от степени систематических переменных вершин.
Введение этапа 105 основано на положении о том, что переменные вершины, наиболее задействованные в графе Таннера, то есть вершины наиболее высокой степени, - это те, для которых биты кодового слова, связанные с этими вершинами, имеют наибольшую вероятность оказаться ошибочными после декодирования кодового слова.
c
Изобретение извлекает выгоду из этого положения для помещения в соответствие битов кодированных подкадров и систематических переменных вершин графа Таннера кода LDPC так, чтобы оптимизировать общие показатели декодирования кодированного кадра T на выходе операции кодирования 106 посредством систематического корректирующего кода, типа кода LDPC.
Таким образом, этап 105 заключается, прежде всего, в том, чтобы расположить систематические переменные вершины графа Таннера кода LDPC, использованного на этапе 106, в соответствии с порядком по возрастанию или убыванию их степеней. Этот этап может быть осуществлен, начиная с матрицы паритета H кода, поскольку систематические переменные вершины соответствуют n-m первым (или последним) столбцам матрицы H и степень каждой переменной вершины дается суммой значений столбцов матрицы H, связанной с переменной вершиной.
Затем, кодированные подкадры и не кодированные подкадры помещаются в соответствие с систематическими переменными вершинами кода LDPC в зависимости от среднего уровня приоритета подкадра и степеней переменных вершин.
При этом первая методология заключается в том, чтобы связать подкадры наиболее высоких уровней приоритета с систематическими переменными вершинами наиболее низких степеней. Таким образом, создаются благоприятные условия для более высокой вероятности корректного декодирования наиболее приоритетных подкадров.
1
0
В примере на Фиг. 1, кодированные 104 алгебраическим корректирующим кодом BCH биты подкадра ST поставлены в соответствие с систематическими переменными вершинами наиболее низких степеней. Не кодированные биты подкадра ST поставлены в соответствие с систематическими переменными вершинами наиболее высоких степеней. Постановка в соответствие может быть реализована операцией чередования, которая заключается в расположении битов каждого подкадра в кадре T’, произведенном на входе этапа кодирования 106. Индексы битов кадра T’ соответствуют индексам систематических переменных вершин матрицы паритета корректирующего кода, типа LDPC. Операция чередования, или постановки в соответствие, может быть выполнена с помощью вектора того же формата, что и кадр T’, который содержит индексы систематических переменных вершин, расположенных в порядке возрастания или убывания значений их степеней. Любое другое эквивалентное осуществление этапа 105 также предполагается.
Для лучшего разъяснения операции, осуществляемой на этапе 105, описывается цифровой пример, который не обязательно отражает реальную ситуацию, но который позволяет понять - как осуществить этап 105.
1
0
deg
deg
deg
deg
1
deg
0
Предположим, что кодируемый кадр T демультиплексируется в два подкадра. Наиболее приоритетный подкадр ST содержит, после кодирования 104, 10 битов, и наименее приоритетный подкадр ST содержит 5 битов. Определяется вектор V того же формата, что и подкадр T’ на входе этапа кодирования LDPC 106. Формат вектора V и кадра T’ в этом примере равен 15. Вектор V содержит индексы систематических переменных вершин, сортируемых в порядке возрастания их степеней. Например, вектор V равен [5; 1; 15; 6; 12; 8; 14; 3; 7; 11; 2; 4; 9; 13; 10]. Операция постановки в соответствие 105 заключается тогда в присвоении 10 битов наиболее приоритетного подкадра ST первым 10 систематическим переменным вершинам, идентифицированным в векторе V, а именно, вершинам с индексами [5; 1; 15; 6; 12; 8; 14; 3; 7; 11]. 5 битов наименее приоритетного подкадра ST присваиваются переменным вершинам с индексами [2; 4; 9; 13; 10].
Приведенное выше описание этапа 105 может быть легко распространено на число подкадров, большее двух.
0
Другая методология использования этапа 105, напротив, заключается в связывании подкадров наиболее высоких уровней приоритета с систематическими переменными вершинами наиболее высоких степеней. В соответствии с этой другой методологией считается, что подкадры наиболее высоких уровней приоритета уже защищены добавлением алгебраического корректирующего кода (этап 104), и в этом случае предпочтительным оказывается, на втором этапе кодирования 106, подкадр ST наиболее низкого уровня приоритета, который не был защищен алгебраическим корректирующим кодом.
Кроме того, эта вторая методология дает преимущество в случае, если декодирование осуществляется в двух итерациях, как это будет объяснено более подробно ниже, в связанном с Фиг. 3 параграфе.
max
В соответствии с вариантом второй методологии использования этапа 105, оказывается возможным конструировать корректирующий код LDPC, фиксируя число систематических переменных вершин, степень которых равна максимальной степени среди совокупности всех переменных вершин. Для этого сначала фиксируется максимальное значение степени, d, причем возможное типичное максимальное значение степени равно десяти. Этот параметр оказывает влияние на уровень минимальной ошибки во время декодирования кода LDPC, а также на отношение сигнал-шум, полученное для заданной алгоритмом декодирования частоты появления ошибки. Чем больше максимальная степень, тем меньше будет минимальная ошибка, но в большей степени будет важным отношение сигнал-шум, начиная с которого алгоритм декодирования начинает декодировать.
max
Затем фиксируется пропорция вершин степени d, которая точно равна отношению между числом битов подкадра, кодированного с наиболее высоким уровнем приоритета, и числом битов кодового слова LDPC. Пропорция других переменных вершин задается в соответствии с принципами, хорошо известными Специалисту в данной области техники и соответственно описанными в справочном издании [1] в главах 5 и 6. С помощью известных методик можно создать матрицу паритета кода, который совместим с отмеченными выше ограничениями. Таким образом, биты подкадра наиболее высокого уровня приоритета будут привязаны только к систематическим переменным вершинам степеней, равных максимальной степени.
Преимущество этого варианта заключается в том, что он позволяет ограничить пропорцию переменных вершин максимальных степеней, что позволяет улучшить минимальную ошибку на кривой частоты появления ошибки, полученной после декодирования. Действительно, в соответствии с этим вариантом, ограничивается пропорция переменных вершин максимальных степеней пропорцией числа битов подкадра, кодированного с наиболее высоким уровнем приоритета, среди совокупности всех битов.
Описанный выше вариант также допускает и фиксацию числа систематических переменных вершин, степень которых равна наименьшей степени вершин среди всех переменных вершин.
Этап постановки в соответствие 105 позволяет создать кадр T’, начиная с различных подкадров. Кадр T’ затем кодируется 106 систематическим корректирующим кодом LDPC IRA в соответствии с методом кодирования, известном Специалисту в данной области техники, например, описанным в главе 6.5.2 издания [1] по ссылке.
c
Выбор производительностей кодирования для алгебраического корректирующего кода BCH, или кодов, и корректирующего кода LDPC, может быть сделан так, чтобы получить производительность общего кодирования между входным кадром T и выходным кадром T, которая была бы равна данной производительности.
c
На Фиг. 2 посредством блок-схемы показана последовательность этапов использования способа декодирования в соответствии с первым вариантом реализации изобретения, приспособленного для декодирования кадра T, кодированного с помощью способа кодирования, показанного на Фиг. 1.
c
c
Кадр T принимается на входе способа декодирования в соответствии с изобретением после его передачи через не совершенный канал распространения, например, канал передачи спутником или посредством радиоканала, который потенциально порождает ошибки на битах кадра T, когда он принимается приемником.
На первом этапе 201 способа декодирования, принятый кадр декодируется с помощью алгоритма декодирования кода, типа LDPC. Алгоритм декодирования основывается на графе Таннера, создаваемом исходя из матрицы паритета кода LDPC, выбранного для осуществления способа кодирования. Алгоритм возможного декодирования может быть одним из тех, что описаны в главе 5 издания [1] по ссылке, или любым другим эквивалентным алгоритмом, основанным на двухдольном графе Таннера. Такой алгоритм подробно не описывается в настоящем документе, поскольку Специалист в данной области техники, специалист по корректирующим кодам, сможет обратиться к изданию [1] или к любому другому справочному изданию из данной области для осуществления этого алгоритма.
На втором этапе 202, операция снятия чередования осуществляется на декодированном кадре, полученном на выходе из первого этапа декодирования 201. Операция снятия чередования заключается в противоположной операции, относительно осуществленной на этапе 105 способа кодирования. Иначе говоря, на этапе 105 способа кодирования, функция чередования, осуществляемая для помещения в соответствие битов подкадров, согласно их уровням приоритета, с систематическими переменными вершинами кода LDPC, согласно их степеням, защищена и передается на приемник с целью выполнения способа декодирования в соответствии с изобретением.
t
t
t
t
Операция снятия чередования, выполняемая на этапе 202, производит на выходе N подкадров различных уровней приоритета, которые соответствуют N подкадрам, созданным во время выполнения способа кодирования. На Фиг. 2 показан пример сценария, для которого N равно двум, но читатель сумеет без затруднений распространить использование этого примера для значения N, большего двух.
1
0
1
0
Снова обращаясь к цифровому примеру, описываемому для иллюстрации этапа 105 способа кодирования в соответствии с изобретением, этап 202 заключается в том, чтобы создать подкадры ST и ST следующим образом. Подкадр ST содержит биты, которые имеют следующие индексы в кадре на выходе из этапа декодирования 201: [5; 1; 15; 6; 12; 8; 14; 3; 7; 11]. Подкадр ST содержит биты, которые имеют следующие индексы: [2; 4; 9; 13; 10].
0
Каждый подкадр, произведенный на выходе из этапа 202, передается затем, за исключением подкадра ST самого низкого уровня приоритета, на этап 203 декодирования с помощью алгоритма декодирования алгебраического корректирующего кода, типа кода BCH, который заключается в противоположной операции относительно операции кодирования, осуществленной на этапе 104 способа кодирования в соответствии с изобретением. Алгоритм возможного декодирования представляет собой, например, алгоритм Berlekamp-Massey, описанный в параграфе 3.3.2 издания [1] по ссылке.
1
0
Декодированные подкадры ST, так же, как подкадр ST самого низкого уровня приоритета, затем логически связываются 204 для создания единственного кадра, затем применяется последний этап 205 снятия чередования для реализации противоположной операции для операции чередования, выполненной на этапе 101 способа кодирования в соответствии с изобретением, которая призвана упорядочить биты кадра T, кодированного в зависимости от их уровня приоритета.
На Фиг. 3 посредством блок-схемы показан вариант использования способа декодирования в соответствии с изобретением.
В соответствии с этим вариантом, этапы 201-205 способа декодирования, показанного на Фиг. 2, взяты как подобные же. Алгебраический корректирующий код, использованный для кодирования некоторых подкадров, в случае этого варианта представляет собой корректирующий и обнаруживающий ошибки код, который позволяет обнаружить, корректно ли декодирован подкадр, то есть, что он не содержит уже ошибок, или напротив, что ошибки имеются. Обозначим как P указатель корректного или некорректного декодирования, получаемый в результате этапа декодирования 203. Если указатель P корректного декодирования положителен, то выполняется вторая итерация декодирования. В этой второй итерации, один или несколько этапов кодирования 213 алгебраическим корректирующим кодом одного или нескольких подкадров высоких уровней приоритета повторяются подобно этапу кодирования 104 способа, описанного в связи с Фиг. 1.
0
На дополнительном этапе 211, указатель P корректного декодирования, предоставляемый алгоритмом декодирования 203 кода BCH, используется для предоставления дополнительной информации в алгоритме декодирования 201 кода LDPC. Эта информация заключается в обеспечении достаточной надежности при второй итерации декодирования 201 кода LDPC, для битов, которые корректно декодированы кодом BCH. Достаточная надежность может быть введена, насыщая, в графе Таннера кода LDPC, максимальным значением информацию правдоподобия, связанную с битами, которые корректно декодированы алгоритмом декодирования кода BCH 203. Таким образом, эта вторая итерация позволяет улучшить возможность коррекции алгоритма декодирования кода LDPC 201 и, в частности, на битах подкадра ST, не защищенного кодом BCH.
Иначе говоря, этап 211 заключается в том, чтобы предоставить алгоритму декодирования кода LDPC 201 вектор правдоподобия битов, произведенных на выходе из этапа кодирования BCH 213, в котором значения насыщаются максимальными значениями. Например, если возможное максимальное значение правдоподобия равно 50, правдоподобия, предоставленные на этапе 211, равны +50 для бита, равного 1, и -50 для бита, равного 0. Термин правдоподобие хорошо известен в области алгоритмов декодирования корректирующих кодов, он обозначает гибкую информацию, связанную с битом, иначе говоря, информацию о правдоподобии его значения. Например, если значения правдоподобия меняются между -50 и +50. Значение-50 соответствует высокой достоверности того, что бит равен 0, значение +50 соответствует высокой достоверности того, что бит равен 1, и промежуточные значения соответствуют меньшим вероятностям. Значение 0 соответствует вероятности, означающей, что бит имеет значение 0 или 1. Вследствие корректной информации декодирования, известно, что биты на выходе из этапа кодирования BCH 213 корректны и, таким образом, можно насытить их значения правдоподобия максимальными абсолютными значениями.
Когда декодер BCH 203 не декодирует корректно подкадр в 1-й итерации, иначе говоря, когда указатель P указывает на плохое декодирование, 2-я итерация алгоритма не осуществляется.
Этап 212 чередования и постановки в соответствие вектора правдоподобия (связанного с битами, произведенными этапом кодирования BCH 213) с систематическими переменными вершинами кода LDPC подобен этапу 105 способа кодирования, показанного на Фиг. 1, с тем различием, что этап 212 ограничивается заменой, в кодовом слове на входе этапа декодирования LDPC 201, значений битов, соответствующих подкадрам, кодированным алгебраическим кодом BCH, значениями битов, полученных на выходе из этапа кодирования BCH 213. Также значения правдоподобия, связанные с этими битами, заменяются насыщенными значениями правдоподобия, рассчитанными на дополнительном этапе 211.
Второй вариант способа декодирования в соответствии с изобретением, который включает в себя вторую итерацию декодирования, особенно преимущественен, когда биты подкадров наиболее высоких уровней приоритета привязаны к систематическим переменным вершинам наиболее высоких степеней. Действительно, при второй итерации, биты наиболее приоритетных подкадров, которые защищены кодом BCH, получают большую надежность вследствие корректной информации декодирования, предоставляемой декодером BCH при первой итерации декодирования. Поскольку эти биты привязаны к переменным вершинам наиболее высоких степеней, которые являются вершинами, представляющими наибольшую вероятность ошибки вследствие их многочисленных соединений, вторая итерация декодирования значительно улучшит декодирование наименее приоритетного подкадра (того, который не защищен кодом BCH), поскольку он привязан к переменным вершинам наиболее низких степеней.
Если наоборот, то привязываются биты наименее приоритетного подкадра к переменным вершинам наиболее высоких степеней, и биты подкадров, защищенных кодом BCH, к переменным вершинам наиболее низких степеней, и информация корректного декодирования, предоставленная декодером BCH, будет улучшать надежность на переменных вершинах наиболее низких степеней, что менее преимущественно, поскольку, естественно, переменные вершины наиболее низких степеней менее связаны и имеют меньшую вероятность ошибки, чем переменные вершины наиболее высоких степеней.
В соответствии с еще одним вариантом (не показанном на чертежах), алгоритм декодирования 203 кода BCH может быть непосредственно интегрирован и объединен с алгоритмом декодирования 201 кода LDPC.
Для этого, создается матрица общего паритета, связанная со способом кодирования в соответствии с изобретением, начиная с соответствующих матриц паритета кода BCH и кода LDPC. Первые строки матрицы общего паритета соответствуют уравнениям паритета кода BCH. Алгоритм общего декодирования 201 может быть выполнен тогда непосредственно в виде алгоритма декодирования кода LDPC.
Когда способ декодирования функционирует в двух итерациях, в результате 1-й итерации проверяются уравнения паритета на стороне матрицы паритета, которая соответствует коду BCH, и рассчитываются синдромы, связанные с этими уравнениями, в соответствии с известным принципом в области алгоритмов декодирования кодов BCH. Если синдромы нулевые, осуществляется вторая итерация декодирования таким же образом, что и показанная на Фиг. 3. То есть применяются этапы 213,211,212, до второго прохода декодирования LDPC. Если синдромы не нулевые, вторая итерация не запускается.
Осуществляя совместное декодирование LDPC и декодирование BCH с помощью единственного алгоритма декодирования, этап 203 специального декодирования BCH устраняется.
b
0
1
i
1
2
4
7
10
1
На Фиг. 4 показаны показатели, полученные благодаря изобретению, на диаграмме, представляющей по ординате частоту появления ошибок в зависимости от отношения сигнал-шум E/N, выраженного в децибелах. Канал распространения - это модельный канал, основанный на модели дополнительного белого Гауссова шума. Результаты измерений частоты появления ошибок получены для моделирования, осуществленного на большом числе кадров T, кодированных с помощью способа кодирования в соответствии с изобретением, подвергнутых добавлению ошибок, типичных для порождаемых каналом распространения, затем декодированных с помощью способа декодирования в соответствии с изобретением. Кривые показателей на Фиг. 4 получены для кадров T, включающих в себя 300 битов, разложенных на два подкадра. Наиболее приоритетный подкадр ST защищен корректирующим кодом BCH с параметрами (K,N)=(40,64), с R=K/N - производительностью кода BCH. Код LDPC задан порождающей матрицей H с 300-ю строками и с 600-ю столбцами. Параметры кода LDPC даны пропорциями λ переменных вершин степеней i: {λ=0,0004; λ=0,2546; λ=0,0899; λ=0,2097; λ=0,4455}. Максимальная степень равна десяти. Этот цифровой пример дан с целью иллюстрации, а не для ограничения. В этом примере, биты наиболее приоритетного подкадра ST поставлены в соответствие с систематическими переменными вершинами максимальной степени.
1
Кривая 401 представляет частоту появления ошибок битов, измеренную после декодирования на наиболее приоритетном подкадре ST.
0
Кривая 402 представляет частоту появления ошибок битов, измеренную после декодирования на наименее приоритетном подкадре ST.
0
Кривая 403 представляет частоту появления ошибок кадров, измеренную только на наименее приоритетных подкадрах ST.
1
Кривая 404 представляет частоту появления ошибок кадров, измеренную только на наиболее приоритетных подкадрах ST.
0
Кривая 405 представляет частоту появления ошибок кадров, измеренную только на наименее приоритетных подкадрах ST с декодированием, проведенным в соответствии с вариантом реализации, показанном на Фиг. 3, в котором реализуется вторая итерация декодирования.
Различные кривые, представленные на Фиг. 4, позволяют оценить вклад изобретения в смысле выигрыша в отношении сигнал-шум, полученного для данной частоты появления ошибок. В частности, можно отметить, что частота появления ошибок (битов или кадров) на наиболее приоритетных подкадрах улучшена в отношении частоты появления ошибок на наименее приоритетных подкадрах. Кроме того, добавление второй итерации декодирования позволяет привести частоту появления ошибок для класса менее приоритетных битов по существу к тому же уровню, что и частота появления ошибок, полученная для класса наиболее приоритетных битов.
На Фиг. 5 схематично показана блок-схема кодера с дифференцированной защитой в соответствии с изобретением, пригодного для осуществления способа кодирования, показанного на Фиг. 1.
0
1
Кодер 500 в соответствии с изобретением принимает на входе кадр T кодируемых битов и производит на выходе кадр Tc кодированных битов. Кодер 500 включает в себя различные модули, сконфигурированные для выполнения этапов способа кодирования, показанного на Фиг. 1. В частности, кодер 500 включает в себя первый модуль 501 присвоения уровня приоритета битам кадра T, второй модуль 502 чередования для перегруппировки битов в группы эквивалентных или близких уровней приоритета, демультиплексор 503 для разделения кадра T на несколько подкадров ST, ST, по меньшей мере, алгебраический кодер 504, такой как кодер BCH, третий модуль 505 чередования и мультиплексирования подкадров, и систематический кодер 506, такой как кодер LDPC.
На Фиг. 6 схематично представлена блок-схема декодера в соответствии с изобретением, приспособленного для декодирования кадров, кодированных кодером в соответствии с изобретением, показанным на Фиг. 5.
c
Декодер 600 в соответствии с изобретением принимает на входе кадр T кодированных битов и производит на выходе кадр T декодированных битов. Декодер 600 включает в себя различные модули, сконфигурированные для выполнения этапов способа декодирования, показанного на Фиг. 2 и 3. В частности, декодер 600 включает в себя декодер 601 для декодирования слова кода LDPC, модуль 602 снятия чередования и демультиплексирования для создания подкадров, связанных с уровнями приоритета, по меньшей мере, декодер 603 для декодирования слова алгебраического кода, типа кода BCH, мультиплексор 604 для логического связывания некоторых подкадров в единственный кадр, и устройство 605 организации чередования для восстановления первоначального порядка битов в исходном кадре.
Декодер 600 может включать в себя другие модули для выполнения дополнительных этапов, описанных в варианте способа декодирования, показанного на Фиг. 3.
Различные модули, показанные на Фиг. 5 и 6, даны в качестве примеров реализации. Не выходя за рамки изобретения, другие архитектуры также предполагаются, например, перегруппировка некоторых этапов способа в пределах одного и того же модуля, или, напротив, выполнение одного этапа несколькими модулями.
c
На Фиг. 7 представлена блок-схема передатчика 700, включающий в себя кодер 702 в соответствии с изобретением. Передатчик 700 может содержать дополнительно прикладной модуль 701 для создания кадров T битов и радиомодуль 703 для модуляции, фильтрации, формирования и преобразования аналогичным образом кодированного кадра T битов перед его передачей на антенну 704 для его испускания по радиоканалу. Передатчик 700 может, например, быть передатчиком, совместимым с системой спутниковой радионавигации. В этом случае передатчик 700 может быть загружен как полезный груз спутника.
На Фиг. 8 представлена блок-схема приемника 800, включающего в себя декодер 803 в соответствии с изобретением. Приемник 800 дополнительно содержит антенну 801 для приема сигнала, радио-модуль 802 для численного преобразования, фильтрации и демодуляции сигнала и прикладной модуль 804, который принимает декодированные кадры. Приемник 800 может, например, быть приемником, совместимым с системой спутниковой радионавигации. В этом случае, приемник 800 может быть приемником GNSS.
Модули кодера и декодера в соответствии с изобретением могут быть осуществлены исходя из аппаратных и/или программных элементов. В этом случае, изобретение может быть осуществлено именно в качестве компьютерной программы, содержащей команды для своего выполнения. Компьютерная программа может быть записана на носителе записи, считываемой процессором. Носитель может быть электронным, магнитным, оптическим или электромагнитным.
В частности, изобретение в целом, или каждый модуль кодера или декодера в соответствии с изобретением, может быть осуществлено устройством, включающим в себя процессор и память. Процессор может быть процессором общего типа, специальным процессором, прикладной интегральной схемой (известной также под английским обозначением ASIC для "Проблемно-ориентированной интегральной микросхемы"), или сетью программируемых в реальном времени вентилей (известных также под английским обозначением FPGA для "Программируемой вентильной матрицы").
Устройство может использовать одну или несколько специальных электронных схем или схему общего использования. Метод по изобретению может быть реализован на программируемой вычислительной машине (процессор или микроконтроллер, например), выполняющей программу, включающую в себя последовательность инструкций, или на специальной вычислительной машине (например, блок логических вентилей, как FPGA или ASIC, или любой другой аппаратный модуль).
В соответствии с вариантом реализации, устройство включает в себя, по меньшей мере, читаемый компьютером носитель памяти (RAM, ROM, EEPROM, флэш-память или другая технология памяти, CD-ROM, DVD или другой носитель на оптическом диске, магнитной кассете, магнитной ленте, диске с магнитной памятью или другое устройство хранения, или другой читаемый компьютером долговременный носитель), кодированный компьютерной программой (то есть некоторые выполняемые команды), которая, когда она выполняется на процессоре или на нескольких процессорах, осуществляет функции способов реализации изобретения, описанных выше.
В качестве примера аппаратной архитектуры, приспособленной для осуществления изобретения, устройство в соответствии с изобретением может содержать шину связи, с которой связаны центральный блок обработки или микропроцессор (CPU, аббревиатура "Central Processing Unit" на английском языке), постоянная память (ROM, аббревиатура "Read OnIy Memory" на английском языке), который может содержать программы, необходимые для использования изобретения; оперативная память, или кэш-память (RAM, аббревиатура "Random Access Memory" на английском языке), содержащая регистры, приспособленные для записи переменных величин и параметров, созданных и модифицированных во время выполнения упомянутых программ; и интерфейс связи или E/S (I/O аббревиатура "Input/Ouput " на английском языке), приспособленный для передачи и для приема данных.
Ссылка на компьютерную программу, которая, когда она выполняется, осуществляет какую-то одну из описанных выше функций, не ограничивается прикладной программой, выполняющейся на единственном главном компьютере. Напротив, программные инструкции для компьютера и программное обеспечение используются здесь в общем смысле, имея ввиду информационный код любого типа (например, прикладное программное обеспечение, микро программное обеспечение, микрокод, или любая другая форма компьютерной команды), который может быть использован для программирования одного или нескольких процессоров для осуществления объектов методов, описанных здесь. Средства, или информационные ресурсы, могут быть распределенными именно ("Cloud computing"), в случае необходимости - в соответствии с технологиями pair-à-pair. Программный код может быть выполнен на любом соответствующем процессоре (например, микропроцессоре), или ядре процессора, или совокупностью процессоров, если они предусмотрены в единственном вычислительном устройстве, или распределен между несколькими вычислительными устройствами (например, такими, как возможно доступные в окружении устройства). Исполняемый код каждой программы, позволяющий программируемому устройству осуществить процессы в соответствии с изобретением, может быть сохранен, например, на жестком диске или в постоянной памяти. В целом, одна или несколько программ могут быть загружены в одно из средств сохранения устройства, прежде чем быть выполненными. Центральный процессор может командовать и управлять выполнением инструкций или участков программного кода или программами в соответствии с изобретением, инструкциями, которые сохраняются на жестком диске или в постоянной памяти, или в других упомянутых элементах хранения.
ССЫЛКИ
[1] "Channel codes, classical and modern", William E. Ryan, Shu Lin, Cambridge university press.