Оценка средств перестановочного декодирования по критерию энергетического выигрыша кода

Развитие мобильных систем связи в первую очередь связывается с их совершенствованием в области достижения высоких скоростей обмена данными за счет расширения полосы пропускания каналов связи, а также обеспечения высокой надежности обработки данных за счет применения помехоустойчивого кодирования [1–5]. Такие системы получили наименование систем сверхнадежной связи с низкой задержкой (URLLC, Ultra-Reliable Low-latency Communications) [5; 6].

Разработка коротких кодов и связанных с ними алгоритмов декодирования в последнее время вновь вызвала большой интерес в сфере телекоммуникаций. Это явление обусловлено строгими требованиями к новым технологиям URLLC, например, применительно к технологии 5G, которые предполагают использование высокопроизводительных кодов с короткой длиной блока для снижения задержки передачи и декодирования с низкой сложностью для достижения низкой задержки обработки [5].

Чтобы удовлетворить требования URLLC к задержке, рассматриваются мягкие методы декодирования избыточных (n, k, d) кодов как подходящий инструмент декодирования для коротких двоичных блоковых BCH кодов (Боуза – Чоудхури – Хоквингема, БЧХ-коды) [7]. Здесь тра- диционно n – длина кодового вектора, k – число информационных разрядов, а d – метрика Хэмминга. Главным недостатком при этом является естественное уменьшение параметра d по мере уменьшения длины кодового вектора n.

Для достижения целей URLLC в работе [8] было предложено использовать метод перестановочного декодирования (ПД), который обеспечивает в системе мягкого декодирования наиболее полное использование введенной в код избыточности.

Метод достаточно подробно описан в работах [9–13]. При этом его преимущества для двоичных блоковых кодов заключаются не только в способности исправлять ошибки, кратность которых превосходит показатель метрики Хэмминга, а еще и в том, что все перестановки символов по их показателям мягких решений могут быть априори занесены в память процессора приемника. Это исключает применение алгебраических методов к матричным преобразованиям при вычислении эквивалентных кодов (ЭК) для сформированных приемником перестановок, но требует определенных вычислительных затрат для оперативного поиска комбинации нумераторов перестановки в памяти микроконтроллера.

С учетом требований URLLC метод поиска требуемых данных в массиве возможных перестановок символов кодовых векторов линейно-

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

Известная статистика перестановок коротких избыточных кодов

В работах [13] показано, что для двоичных кодов переставленные матрицы, объединяющие нумераторы наиболее надежных символов, могут оказаться вырожденными, что не позволяет получить ЭК, представляющий собой нежелательный исход процедуры формирования перестановки. В противном случае, переставленная матрица имеет определитель не равный нулю и ЭК код в системе может быть получен. Статистические данные, собранные в ходе математического моделирования системы формирования подобных матриц, показали, что с ростом длины кодовых векторов количество полезных перестановок сокращается, а число отрицательных решений увеличивается. Так для группового кода (7,4,3) доля производительных перестановок нумераторов (ППН), позволяющих без дополнительных вычислительных затрат сформировать ЭК, составляет 80%, а доля непроизводительных перестановок нумераторов (НПН) – 20%. При этом подмножество полезных перестановок и подмножество непродуктивных перестановок не пересекаются и составляют полное множество всех возможных перестановок нумераторов символов.

Для кода BCH (15,5,7) количество полезных перестановок уже оказывается на уровне 60%, а для кода (15,7,5) таких перестановок будет около 50%. Такое явление ставит под сомнение идею использования ПД для решения задач URLLC. В ряде работ [14–17] было предложено использовать две когнитивные карты: одну для хранения данных о ППН, а вторую для хранения данных о НПН. Но в отличие от известного метода псевдослучайной замены столбцов переставленной вырожденной матрицы размерности k х к , предлагалось сопровождать перестановку НПН сведениями о нерациональных заменах нумераторов, которые однозначно не изменяют эффекта линейной зависимости [2; 18; 19].

Подобный подход позволяет избежать метода перебора в процедуре поиска линейно независимого столбца для устранения свойства вырожденности переставленной матрицы. Это положительно сказывается не только на вре- менных показателях работы декодера в сторону их снижения. При этом повышается показатель ППН, например, для кода (15,5,7) он становится равным 90%. Подобную тенденцию в процентном соотношении показателей ППН и НПН повторяют коды Голея, но совершенно иная картина возникает при исследовании кодов с малой плотностью проверок на четность или хорошо известных кодовых конструкций с аббревиатурой LDPC.

Диаграмма процентного отношения ППН и НПН для LDPC кода (15,5,5) показана на рисунке 1.

Основной причиной такого явления считается низкая плотность единичных элементов, характерная для кодов LDPC. Изучение тонкой структуры перестановок представленного кода показывает, что полное множество образующих комбинаций циклов для данного кода оказывается равно 207. Из них ППН составляет всего 51 комбинацию или 25%, а НПН – 156 комбинаций или 75%, при этом одноразовых замен потребуется 61, а двойных замен потребуется 95. В качестве высоковероятного предположения следует указать, что подобная картина с доминирующим превосходством НПН относительно ППН будет сохраняться для любого кода из разряда LDPC.

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

Принцип оценки эффективности системы связи по параметру энергетического выигрыша кода

В ходе аналитического моделирования системы связи с различными методами защиты информации от ошибок и использованием критерия ЭВК в работе использовались аналитические выраже- ния, связанные с аддитивным белым гауссовским шумом (АБГШ), который порождает независимый поток битовых ошибок. При этом изменение дисперсии σ2 осуществлялось в пределах от 1 до значения 0,01, что обеспечило практически непрерывное изменение отношения сигнал/шум (ОСШ): E

h ( σ ²) = 10log ^b 2 [дБ],          (1)

2σ где Eb – энергия сигнала на бит [1; 4].

Вероятность ошибки на бит оценивалась по формуле:

1        0    - ( x - E b )²

p_b ( σ ²)=_т¹ ₂ ∫ e ^{- 2 σ 2} dx ,        (2)

V 2πσ2 -∞ а вероятность ошибки на комбинацию оценива- лась в соответствии с выражением: n n!

Pcom(σ2)=∑ pb(σ2)i(1-pb(σ2))n-i (3) i i!×(n-i) , при этом значение переменной i в зависимости от метода декодирования изменялось [1; 2]. В случае алгебраического метода исправления ошибок переменной присваивалось значение i= dmin , при использовании метода ПД i= (n- k). В ряде иных случаев значение переменной оговаривается в тексте [1; 8; 9; 20].

Для точного выявления особенностей вероятностных характеристик декодеров в работе принята концепция сравнения вероятностей ошибочных решений на бит. Поэтому по результатам работы декодера используется оценочное выражение вида:

^Pcom ^{( σ 2)} p db ≈

n

.

В этом случае сравнение выражений (2) и (4)

считается корректным.

Для дальнейшего описания реализации процедуры ПД и оценки получаемого ЭВК необходимо сформулировать и доказать ряд теоретических положений.

Утверждение 1. Для получения полной информации о переданном дискретном сообщении необходимо достоверно принять все без исключения комбинации цифровой последовательности, например, входящие в пакет.

Принципиально подобная задача в сетевых структурах решается на канальном уровне. Для этого используются алгебраические или алгоритмические методы повышения достоверности [1–3].

Утверждение 2. При использовании метода ПД в случае возникновения НПН параметр ЭВК снижается на величину обратно пропорциональной процентной доли таких перестановок.

Действительно: пусть декодер в ходе обработки данных затрачивает энергию на передачу комбинации длин n бит равную nEb . Пусть де- кодер выявил перестановку вида НПН и пусть виртуально вместо коррекции переставленной матрицы приемник посылает запрос на повторение принятой ранее комбинации с неудачной перестановкой. Без учета затрат энергии на сигнал запроса о повторе данных к передатчику в указанных условиях система связи увеличивает энергетические затраты ровно в два раза.

Следовательно, в описанных условиях при передаче двух комбинаций половина из них при повторе данных потребовала 100% дополнительной энергии. При удачном приеме повторной комбинации требуемый уровень достоверности достигнут при обработке указанных двух комбинаций с затратами энергии на бит равной E_b ^request = 1/ 2 = 0,5 . Но одна комбинация в указанном кортеже данных равна 50%, следовательно, переходя к процентным показателям НПН для конкретного кода логично указать, что относительный уровень энергии сигнала на бит составит E_b = 1 I 1,5 ≈ 0,67 .

Отсюда появляется возможность оценить энергетические потери при известных из статистических испытаний различных кодов по мощности множества комбинаций НПН. Если для кода (7,4,3) это множество составляет 20%, то в системе связи энергия на бит составит E b (7,4,3) = 1¹1,2 ≈ 0,83.

В случае использования процедуры коррекции значений НПН энергетические затраты на бит системы связи составят E_b ( _7,4,3 ) = 1 , которые будут обеспечиваться за счет внутренней работы декодера по коррекции перестановок НПН. На рисунке 2 представлены характеристики системы связи с помехоустойчивым кодированием при использовании двоичного кода (7,4,3) в условиях действия АБГШ. Характеристика с номером 1 представляет вероятность ошибки на бит без использования процедуры исправления ошибок, определяемой с использованием выражения (2). Нормативную прямую данная зависимость пересекает в точке с аргументом, равным 10,5 дБ.

Использование алгоритма с исправлением одной ошибки, характерного для данного кода, представляется на графике зависимостью с номером 2 и оценивается выражением (3), показывая изменение вероятности ошибки на комбинацию. Используя выражение (4) получаем характеристику 3 вероятности ошибки на бит в условиях исправления одной ошибки. В этом случае сравнение зависимостей 1 и 3 представляется корректным. Характеристика 3 пересекает нормативную прямую в точке с аргументом 8,0 дБ, что указывает на ЭВК кода, равный 2,5 дБ.

p1b(σ )

P1(σ )

p7(σ )

p9(σ )

h1(σ )

Отношение сигнал/шум [дБ]

Рисунок 2. Оценка ЭВК кода (7,4,3) в условиях традиционного алгебраического декодирования

В случае применения в системе связи метода ПД параметр i в выражении (3) увеличивается, что однозначно повышает ЭВК, используемого в системе избыточного кода. Это происходит по причине перемещения символов с низкими показателями надежности в зону проверочных разрядов, что в конечном итоге обеспечивает при декодировании большее значение ЭВК.

На рисунке 3 представлена сравнительная характеристики кода (7,4,3) в условиях алгебраического декодирования данных и в условиях ПД, когда значение равно E_{b (7,4,3)} = 1 . Характеристики 1 и 2 имеют одинаковое значение с аналогичными кривыми, представленными на рисунке 1, характеристика 4 представляет изменение вероятности ошибки на бит в условиях применения ПД.

h1(σ )

Отношение сигнал/шум [дБ]

Рисунок 3. Оценка ЭВК кода (7,4,3) в условиях алгебраического декодирования и ПД

Аргумент функции 4 при пересечении с нормативной прямой составляет 3,0 дБ, что обеспечивает асимптотическое значение ЭВК на уровне 7,5 дБ.

Вызывает интерес явление, которое возникает при обработке данных в системе ПД при гипотетическом повторе 20% данных и снижении при этом равнозначного значения параметра E b до 0,83. На рисунке 4 представлены две характеристики 5 и 6.

Зависимость 5 представляет вероятность ошибки на бит, когда E_b = 0,83 . Зависимость 6 определялась в условиях, когда E_b = 1 . Трассировка данных в точках пересечения характеристик с нормативной прямой показывает, что проигрыш функции 5 относительно кривой 6 составляет около 0,9 дБ. Исследования показали, что выявленное процентное превосходство подмножеств НПН над подмножествами ППН для кодов BCH не приводит к существенному проигрышу по параметру ЭВК. Но в любом случае отказ от коррекции перестановок НПН ухудшает показатель выигрыша кода примерно до 1 дБ. В этом случае сохраняется целесообразность коррекции перестановок из подмножества НПН для таких кодов.

Рисунок 4. Оценка проигрыша ЭВК при уменьшении значения E_b

На рисунке 5 показано поведение характеристик кода LDPC (15,5,5). При этом c учетом количества НПН значение энергии сигнала на бит принималось равным E_b = 0,63 .

0.1

0.01

• 1 × 10

• 1 × 10

• 1 × 10

• 1 × 10

• 1 × 10

0               5              10               ¹⁵

h5(σ )

Отношение сигнал/шум [дБ]

Рисунок 5. Асимптотическая оценка ЭВК кода LDPC в условиях алгебраического декодирования (зависимость – 2) и с использованием ПД (зависимость 3)

На рисунке 5 кривая 1 соответствует вероятности ошибки в АБГШ. Зависимость 2 представляет процедуру алгебраического декодирования с исправлением ошибок в метрике Хэмминга, а зависимость 3 соответствует системе ПД с исправлением ошибок, кратных числу проверочных разрядов. Следует отметить, что корректировка переставленной матрицы кода LDPC требует, в основном, двойных подстановок, что однозначно увеличивает объем памяти когнитивной карты НПН и одновременно повышает сложность реализации декодера. Можно показать, что плотность единичных элементов в порождающей матрице кода LDPC (15,5,5) к общему числу элементов составляет значение 0,33, кода ВСН (15,7,5) – 0,35, а для кода ВСН (15,5,7) это значение будет равно 0,49.

Специфические особенности перестановок

Изучение тонкой структуры ППН и НПН для различных кодов выявило ряд их особенностей, которые потребовали внести изменения в основной алгоритм ПД. Экспериментально было установлено, что в условиях, когда значение n оказывалось кратным значению k , то в условиях равных значений интервалов между нумераторами невозможно указать однозначно структуру порождающей матрицы эквивалентного кода. На рисунке 6 показаны примеры периодических перестановок для двух кодов, причем для кода ВСН определитель переставленной матрицы не равен нулю, а для кода LDPC определитель такой ма-

Утверждение 3. Если значения основного избыточного кода n и k возможно представить кратным отношением, равным натуральному числу N, то невырожденная переставленная матрица потребует коррекции хотя бы одного столбца.

Действительно, в работе [20] установлено, что в алгоритме декодирования важно выполнить три шага: во-первых, по принятой приемником перестановке выявить ее состав, относящийся к образующей комбинации цикла (ОКЦ); во-вторых, оценить расстояние принятой перестановки от ОКЦ в цикле до принятой перестановки; в-третьих, трансформировать порождающую матрицу, связанную в когнитивной карте с ОКЦ.

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

Следствие: комбинация нумераторов с периодическим следованием межинтервальных оценок, равных N , должна размещаться в когнитивной карте НПН.

Принципиально нет необходимости ради единственной перестановки размещать в декодере специальную когнитивную карту, но поскольку подобная перестановка требует коррекции только одиночной подстановкой, то целесообразность включения указанной комбинации в когнитивную карту НПН очевидна.

В системах ПД для ускорения процедуры сортировки мягких решений символов рекомендуется формировать их в целочисленном формате. Для этого в работах [8; 10] предлагается использовать линейную функцию вида:

A ( Z i ) =

л

'.a xZ i

где A ( Z i ) - целочисленное мягкое решение сигнала (ЦМРС) его текущего значения Z i . В выражении (5) параметр A max обычно принимают равным семи [1; 8]. Тогда потребуется всего три бита для нумерации 8 значений ЦМРС от 0 до 7. Для выявления частоты формирования названных ЦМРС в канале с АБГШ была разработана имитационная модель подобного канала связи. Результаты испытаний модели и объем выборки приведены на рисунках 7 и 8.

На рисунке 7 показаны результаты испытания модели в условиях, кода ОСШ принималось равным 0 дБ, а на рисунке 8 это отношение принима- лось равным 10 дБ. При этом длина комбинации принималась равной 15 битам. Из графиков видно, что в указанных случаях при передаче цифровых данных формируется достаточное количество надежных ЦРМС.

Рисунок 7. Результаты испытаний модели при ОСШ, равном 0 дБ

Рисунок 8. Результаты испытаний модели при ОСШ, равном 10 дБ

Заключение

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

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

В качестве перспективы исследований следует указать оценку возможностей метода в системе LoRa (Long Range).