Способ мягкого декодирования помехоустойчивого кода Российский патент 2024 года по МПК H03M13/13 

Изобретение относится к области техники связи и может быть использовано для мягкого декодирования линейного помехоустойчивого кода в каналах связи с высоким уровнем помех.

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

Помехоустойчивость в значительной степени определяется выбором способа декодирования кода. Известно жесткое и мягкое декодирование помехоустойчивого кода. Мягкое декодирование учитывает оценки досто-верностей принятых символов и обеспечивает большую помехоустойчивость, поскольку позволяет корректировать примерно вдвое большее число ошибок по сравнению с жестким декодированием. Однако, для мягкого декодирования требуется выполнять большой объем вычислений, что значительно усложняет декодирование кода. Сложность мягкого декодирования помехоустойчивого кода можно уменьшить, если максимально возможное число наименее достоверных символов кода стирать и декодировать код с исправлением стираний. При исправлении стираний одновременно исправляют и ошибки, попавшие на место стираний. Исправление стираний выполняют путем ортогонализации проверочной матрицы кода относительно позиций наименее достоверных символов. Это позволяет выразить стертые символы через нестертые наиболее достоверные символы и восстановить код. Такое декодирование исправляет стирания, кратность которых находится в пределах минимального кодового расстояния, а также исправляет довольно большую часть стираний большей кратности, вплоть до кратности стираний, равной избыточности кода.

Декодирование с исправлением стираний выполняют путем ортогонализации Грама-Шмидта проверочной матрицы кода относительно значений стираний. Сложность декодирования для двоичного кода с векторными арифметическими операциями оценивается величиной 0(n²), где n - блоковая длина помехоустойчивого кода.

Предлагаемый способ мягкого декодирования помехоустойчивого кода является универсальным и может использоваться для декодирования произвольных линейных помехоустойчивых кодов: Хемминга, Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Маллера, Голея, Рида-Соломона и многих других.

Известен способ мягкого декодирования помехоустойчивого кода, заключающийся в том, что на вход декодирующего устройства поступают n символов принятого помехоустойчивого кода с оценками достоверностей этих символов. В декодирующем устройстве помехоустойчивого кода эти символы сортируют по достоверности, выбирая сначала символы с наибольшей достоверностью, затем символы с меньшей, но следующей по величине достоверностью и так далее, пока не будет набрано n-s наиболее достоверных символов помехоустойчивого кода, где s есть число наименее достоверных символов помехоустойчивого кода. Затем формируют 2^s вариантов помехоустойчивого кода, в каждом из которых s наименее достоверных символов помехоустойчивого кода принимают всевозможные двоичные комбинации, начиная с комбинации из множества 0 и заканчивая комбинацией из множества 1, a n-s наиболее достоверных символов помехоустойчивого кода не изменяют. Далее выполняют жесткое декодирование всех 2^s вариантов помехоустойчивого кода и корректируют ошибки в каждом из этих вариантов. Затем каждый из 2^s вариантов декодированного помехоустойчивого кода сравнивают по расстоянию Хемминга с принятым помехоустойчивым кодом и получают совокупность 2^s расстояний Хемминга. На выход декодирующего устройства подают помехоустойчивый код, соответствующий минимальному кодовому расстоянию Хемминга из совокупности 2^s расстояний Хемминга. (Кларк Дж., мл. Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. - Пер. с англ. - Радио и связь. - 1987. - с. 160-165).

Недостатком этого способа является чрезмерно большая сложность, поскольку жесткое декодирование 2^s вариантов помехоустойчивого кода с исправлением ошибок в каждом из вариантов помехоустойчивого кода требует большого числа вычислений.

Наиболее близким к предлагаемому способу является способ (прототип) мягкого декодирования помехоустойчивого кода, заключающийся в том, что на вход декодирующего устройства подают n символов принятого помехоустойчивого кода с оценками достоверностей этих символов. В декодирующем устройстве помехоустойчивого кода сначала оценивают величину s числа наименее достоверных символов помехоустойчивого кода. Далее символы помехоустойчивого кода сортируют по достоверности, выбирая сначала символы с наибольшей достоверностью, затем символы с меньшей, но следующей по величине достоверностью и так далее, пока не будет набрано n-s наиболее достоверных символов помехоустойчивого кода. Затем выполняют ортогонализацию проверочной матрицы кода относительно позиций s наименее достоверных символов кода. Далее вычисляют значения этих s наименее достоверных символов кода через n-s наиболее достоверных символов помехоустойчивого кода и восстанавливают информационные символы кода. (Патент РФ №2738724 МПК Н03М 13/13 Квашенников В.В. Способ мягкого декодирования помехоустойчивого кода. - Приор. 02.06.2020. - Опубл. 16.12.2020. - Бюл. №35).

Недостатком этого способа является недостаточная помехоустойчивость из-за неоптимального выбора числа s наименее достоверных символов, а также большая сложность способа, поскольку при ортогонализации проверочной матрицы кода относительно позиций s наименее достоверных символов кода не учитывается ортогонализация проверочной матрицы кода с меньшим числом S наименее достоверных символов кода.

Целью изобретения является повышение помехоустойчивости способа за счет выбора максимально возможного числа s наименее достоверных символов кода и снижение сложности декодирования.

Для достижения цели предложен способ мягкого декодирования помехоустойчивого кода, заключающийся в том, что на вход декодирующего устройства подают n символов принятого помехоустойчивого кода с оценками достоверностей этих символов. В декодирующем устройстве помехоустойчивого кода сначала оценивают величину s числа наименее достоверных символов помехоустойчивого кода. Далее символы помехоустойчивого кода сортируют по достоверности, выбирая сначала символы с наибольшей достоверностью, затем символы с меньшей, но следующей по величине достоверностью и так далее, пока не будет набрано n-s наиболее достоверных символов помехоустойчивого кода. Затем выполняют ортогонализацию проверочной матрицы кода относительно позиций s наименее достоверных символов кода. Далее вычисляют значения этих s наименее достоверных символов кода через n-s наиболее достоверных символов помехоустойчивого кода и восстанавливают информационные символы кода. Новым является то, что сначала устанавливают начальное значение числа s=d наименее достоверных символов кода, где d - минимальное кодовое расстояние кода, и выполняют попытку ортогонализации проверочной матрицы кода относительно позиций этих s наименее достоверных символов кода. При успешной попытке ортогонализации число s наименее достоверных символов кода увеличивают на 1, и выполняют новую попытку ортогонализации проверочной матрицы кода относительно позиций наименее достоверных символов кода и так далее, до тех пор, пока ортогонализация не будет выполняться. Тогда возвращаются к предыдущему максимально возможному числу s наименее достоверных символов кода, при котором ортогонализация еще выполняется. Эти s наименее достоверных символов кода стирают, декодируют помехоустойчивый код с исправлением стираний, вычисляют значения s наименее достоверных символов кода через n-s наиболее достоверных символов помехоустойчивого кода и восстанавливают информационные символы кода. При этом ортогонализацию проверочной матрицы относительно s позиций наименее достоверных символов кода выполняют на основе предыдущей ортогонализации матрицы относительно s-1 позиций наименее достоверных символов кода. Причем декодирование помехоустойчивого кода с исправлением стираний выполняют путем ортогонализации Грама-Шмидта проверочной матрицы кода. При этом попытка ортогонализации выполняется относительно s позиций символов кода, если первые s строк проверочной матрицы отличны от нуля, и не выполняется, если хотя бы одна из первых s строк проверочной матрицы равна нулю.

Рассмотрим осуществление предлагаемого способа мягкого декодирования помехоустойчивого кода.

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

Проверочную матрицу помехоустойчивого кода запишем в виде

где h₁ - столбцы проверочной матрицы кода длины n-k символов, а k - информационная длина кода.

В проверочной матрице помехоустойчивого линейного кода любые d-1 столбцов являются линейно независимыми. Столбцы, число которых больше, чем d-1, могут быть как линейно независимыми, так и линейно зависимыми.

Проверочную матрицу помехоустойчивого кода запишем также в виде

где g₁ - строки проверочной матрицы кода длины n символов.

Линейно независимые столбцы матрицы можно путем тождественных преобразований привести к виду, при котором в этих столбцах будет только одна 1, а остальные - 0. Тождественными преобразованиями называют операции сложения строк матрицы между собой и перестановки строк матрицы. Приведение матрицы к описанному виду есть ортогонализация Грама-Шмидта матрицы.

Сначала устанавливают начальное значение числа s=d наименее достоверных символов кода, где d - минимальное кодовое расстояние кода. Затем символы кода сортируют по достоверности, выбирая сначала символы с наибольшей достоверностью, затем символы с меньшей, но следующей по величине достоверностью и так далее, пока не будет набрано n-s наиболее достоверных символов помехоустойчивого кода. Оставшиеся s символов кода будут наименее достоверными.

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

Ортогонализация Грама-Шмидта проверочной матрицы относительно столбцов, соответствующих s наименее достоверным символам кода, позволяет выразить значения этих s символов через остальные n-s символов кода. Наименее достоверные s символов кода стирают, а затем, после ортогонализации проверочной матрицы, восстанавливают информационные символы кода. Таким образом выполняют декодирование кода с исправлением стираний, в том числе за пределами минимального кодового расстояния. Для кода со спектром А₀, A₁, …, A_n нижняя оценка доли исправляемых стираний за пределами минимального кодового расстояния запишется в виде (Афанасьев В.Б., Давыдов А.А., Зигангиров Д.К. Оценка доли стираний, исправляемых линейными кодами. // Информационные процессы. - 2016. - т. 16. - №4. - с. 382-404):

Как показывают расчеты, доля исправимых стираний (доля линейно независимых столбцов проверочной матрицы) будет довольно большой. Например, для кода БЧХ(15, 7, 5) доля исправимых стираний P_s в зависимости от числа стираний s будет Р₅=0,9964, Р₆=0,9702, Р₇=0,8597, Р₈=0,5061. Поэтому декодирование с исправлением стираний за пределами минимального кодового расстояния существенно увеличивает вероятность правильного приема по сравнению с исправлением ошибок или стираний в пределах минимального кодового расстояния.

Рассмотрим мягкое декодирование двоичного помехоустойчивого кода БЧХ (15, 7, 5), блоковая длина которого n=15, информационная длина k=7, а минимальное кодовое расстояние d=5. Исправление за пределами минимального кодового расстояния соответствует s>4. Пусть передавался код БЧХ 5=100110111000010, а принят код с 6 ошибками A=101010010010011 на i=12,11,8,6,4,0 позициях кода. Достоверности символов кода D=0,8;0,5;0,l;0,4;0,7;0,6;0,2;0,8;0,2;0,7;0_,3;0,5;0,7;0,8;0,2.

Позиции символов кода в порядке возрастания достоверности i=0,4,6,8,12,11,3,13. Сначала стирают s=d=5 позиций кода, соответствующих символам кода с наименьшей достоверностью A=10a₁₂010a₈1a₆0a₄001a₀, где a_i - обозначены стирания на i месте. Проверочная матрица Н кода

Для ортогонализации столбца матрицы, соответствующего стиранию а₀, первую строку оставляют без изменений, а в пятой строке записывают поразрядную сумму первой и пятой строк матрицы. Затем для ортогонализации столбца, соответствующего стиранию а₄, вторую строку оставляют без изменений, а в первой, шестой, седьмой и восьмой строке записывают поразрядную сумму второй и перечисленных строк матрицы и так далее. В итоге получают проверочную матрицу H₁ с ортогональными проверками относительно позиций стертых символов а₀, а₄, а₆, а₈, a₁₂.

Нулевой строки не получили, значит, можно увеличить число стертых символов на 1. Далее добавляют к стертым символам новый символ а₁₁ с наименьшей достоверностью и выполняют ортогонализацию соответствующего столбца матрицы H₁. Ортогонализацию проверочной матрицы относительно уже 6 позиций наименее достоверных символов кода выполняют на основе предыдущей ортогонализации матрицы относительно 5 позиций наименее достоверных символов кода, что существенно сокращает объем вычислений. В результате получают матрицу H₂

_{Поскольку нулевой строки не получили, то можно продолжить ортогонализацию столбцов матрицы. Это позволяет большее число наименее достоверных символов выразить через меньшее число наиболее достоверных символов кода, что повышает помехоустойчивость декодирования. В результате ортогонализации веса строк проверочной матрицы уменьшаются. Далее добавляют к 6 стертым символам еще один стертый символ а3 с наименьшей достоверностью и выполняют ортогонализацию соответствующего столбца матрицы Н2. Получают следующую матрицу Н3}

Затем продолжают ортогонализацию проверочной матрицы относительно символа а₁₃

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

Из строк проверочной матрицы Н₄ получают значения символов

которые совпадают с исходным безошибочным кодом БЧХ.

Сложность декодирования равна сложности решения системы линейных уравнений порядка n-k и для двоичного кода с векторными операциями сложения строк проверочной матрицы будет оцениваться величиной 0((n-k)²). Верхняя асимптотическая оценка сложности декодирования 0(n)².

В данном примере исправлено 6 ошибочных символов кода, что за пределами минимального кодового расстояния s=d-1=4. При небольшом объеме вычислений удалось исправить 6 ошибок, хотя при жестком декодировании код исправляет только 2 ошибки, а при обычном мягком декодировании - 4 ошибки. Причем полученные проверочные соотношения позволяют исправить 8 наименее достоверных ошибочных символов.

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

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

Изобретение относится к области техники связи. Технический результат заключается в повышении помехоустойчивости и уменьшении сложности декодирования. Для этого на вход декодирующего устройства подают n символов принятого помехоустойчивого кода с оценками достоверностей этих символов. Устанавливают начальное значение числа s=d наименее достоверных символов кода, где d - минимальное кодовое расстояние кода, и выполняют попытку ортогонализации проверочной матрицы кода относительно позиций этих s наименее достоверных символов кода. При удачной попытке ортогонализации число s наименее достоверных символов кода увеличивают на 1 и выполняют новую попытку ортогонализации проверочной матрицы до тех пор, пока ортогонализация не будет выполняться. Тогда возвращаются к предыдущему максимально возможному числу s наименее достоверных символов кода, при котором ортогонализация еще выполняется. Эти s наименее достоверных символов кода стирают, декодируют помехоустойчивый код с исправлением стираний, вычисляют значения s наименее достоверных символов кода через n-s наиболее достоверных символов и восстанавливают информационные символы кода. 3 з.п. ф-лы.

1. Способ мягкого декодирования помехоустойчивого кода, заключающийся в том, что на вход декодирующего устройства подают n символов принятого помехоустойчивого кода с оценками достоверностей этих символов, в декодирующем устройстве помехоустойчивого кода сначала оценивают величину s числа наименее достоверных символов помехоустойчивого кода, далее символы помехоустойчивого кода сортируют по достоверности, выбирая сначала символы с наибольшей достоверностью, затем символы с меньшей, но следующей по величине достоверностью и так далее, пока не будет набрано n-s наиболее достоверных символов помехоустойчивого кода, затем выполняют ортогонализацию проверочной матрицы кода относительно позиций s наименее достоверных символов кода, далее вычисляют значения этих s наименее достоверных символов кода через n-s наиболее достоверных символов помехоустойчивого кода и восстанавливают информационные символы кода, отличающийся тем, что начальное значение числа наименее достоверных символов кода устанавливают равным s=d, где d - минимальное кодовое расстояние кода, и затем выполняют попытку ортогонализации проверочной матрицы кода относительно позиций этих s наименее достоверных символов кода, при успешной попытке ортогонализации число s наименее достоверных символов кода увеличивают на 1 и выполняют новую попытку ортогонализации проверочной матрицы кода относительно позиций наименее достоверных символов кода и так далее до тех пор, пока ортогонализация не будет выполняться, тогда возвращаются к предыдущему максимально возможному числу s наименее достоверных символов кода, при котором ортогонализация еще выполняется, эти s наименее достоверных символов кода стирают, декодируют помехоустойчивый код с исправлением стираний, вычисляют значения s наименее достоверных символов кода через n-s наиболее достоверных символов помехоустойчивого кода и восстанавливают информационные символы кода.

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

3. Способ по п. 1, отличающийся тем, что декодирование помехоустойчивого кода с исправлением стираний выполняют путем ортогонализации Грама-Шмидта проверочной матрицы кода относительно позиций стертых символов.

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