Перестановочный декодер с альтернативными решениями Российский патент 2024 года по МПК H04L1/20 

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

Заявленное устройство расширяет арсенал средств мягкого декодирования двоичных систематических избыточных блоковых кодов при использовании способа перестановочного декодирования. Для этого используются известные свойства эквивалентных кодов (см. У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. Ред. Р.Л. Добрушин и С.И. Самойленко. М.: Мир, 1976. - С. 76-78). Для двоичных кодов реализация подобных свойств может иметь как положительный, так и отрицательный исход, который зависит от конфигурации конкретных перестановок нумераторов принятых символов цифровых команд управления. Результативный итог в системе обмена данными формируется в том случае, когда выполненная перестановка нумераторов кодовой комбинации по результатам сортировки мягких решений не приводит к линейной зависимости столбцов адекватно переставленной порождающей матрицы избыточного кода. В противном случае, при вырожденной переставленной информационной части порождающей матрицы предполагаемого эквивалентного кода, перестановка нумераторов положительного результата не даст. При этом установлено, что количество положительных решений из общего множества возможных решений по перестановкам для конкретного избыточного кода зависит от соотношения числа информационных разрядов в кодовом векторе к общему числу бит в этом векторе (Оценка статистических характеристик перестановочного декодера методом его программной реализации (см. А.Л.Х. Аттаби, А.А. Брынза, Д.В. Ганин, А.А. Ничунаев, А.В. Новоселов // Автоматизация процессов управления. 2023. № 2 (72). С. 91–98).

Установлено, что при приближении относительной скорости кода к значению 0,5 объемы положительных и отрицательных перестановок в процентном отношении выравниваются. Этот факт снижает эффективность процедуры перестановочного декодирования. Целесообразно в условиях формирования отрицательного результата перестановки нумераторов символов кодового вектора в соответствующей когнитивной карте декодера указывать альтернативное решение, приводящее к положительному решению.

Известно устройство – Декодер с упорядоченной статистикой символов (см. патент РФ 2490804), в котором частично решается задача запоминания комбинаций именно тех номеров переставленных столбцов порождающей матрицы основного кода, определитель которых указывает на вырожденность переставленных матриц и невозможность реализовать декодирование с использованием эквивалентного кода.

Известно также устройство – декодер с повышенной корректирующей способностью (см. патент РФ 2438252), которое практически реализует устройство, описанное в работе Р. Морелос-Сарагосы с незначительным уточнением процедуры получения мягких решений символов(МРС). В таком декодере, по сути, сохраняются все недостатки, характерные для решений по патентам 2444127, 2490804 и 2580797.

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

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

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

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

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

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

Структурная схема перестановочного декодера с альтернативными решениями представлена на фиг. 1, где:

1- Блок приема;

2- Блок мягких решений символов;

3- Накопитель оценок;

4- Блок упорядочения оценок;

5- Блок интервальных оценок;

6- Формирователь образующей комбинации орбиты (ОКО);

7- Когнитивная карта результативных перестановок нумераторов (РПН);

8- Когнитивная карата непроизводительных перестановок нумераторов (НПН);

9- Блок альтернатив;

10- Корректор перестановки;

11- Блок эквивалентного кода;

12- Блок локаторов ошибок;

13- Блок исправления стираний.

Перестановочный декодер с альтернативными решениями содержит блок 1 приема, выход которого через блок 2 мягких решений символов подключен к входу блока 3 накопителя оценок, первый выход которого подключен к одному входу блока4 упорядочения оценок, второй выход которого подключён к первому входу блока 11 эквивалентного кода, выход которого подключен к первому входу блока12 локаторов ошибок, выход которого подключен к второму входу блока 13 исправления стираний, блок 5интервальных оценок, формирователь блока 6 образующей комбинации орбиты, когнитивная карта блока 7 результативных перестановок нумераторов, когнитивная карта блока 8 непроизводительных перестановок нумераторов, блок 9 альтернатив, корректор перестановки блока 10, при этом первый выход блока 4 упорядочения оценок через блок 5интервальных оценок подключен к входу блока 6 формирователя образующей комбинации орбиты, первый выход которого через когнитивную карту блока 8 непроизводителных перестановок нумераторов и блок 9 альтернатив подключен к другому входу блока 4 упорядочения оценок, третий выход которого подключен к второму входу блока 12 локаторов ошибок, а второй выход формирователя образующей комбинации орбиты блока 6 через когнитивную карту результативных перестановок нумераторов блока 7 и корректор перестановок и блок 10 подключен к второму входу блока 11 эквивалентного кода, при этом второй выход накопителя оценок блока 3 подключен к первому входу блока 13 исправления стираний.

Вход блока 1 приема является общим входом перестановочного декодера с альтернативными решениями. Выход этого блока подключен к входу блока мягких решений символов, в котором для каждого двоичного жесткого решения вырабатывается мягкое решение символа (МРС). Полученные данные о жёстких и мягких решениях накапливается в накопителе оценок блока 3.

Работа устройства рассматривается на примере кода БЧХ (15, 5, 7) с порождающей матрицей G вида

.

Столбцы матрицы нумеруются для удобства от 1 до 15 в терминах десятичной системы нумерации слева направо в виде верхних индексов (нумераторов) для символов жестких решений. Пусть источник информации передает информационный вектор тогда в канал связи будет отправлен вектор избыточного кода

=100100011110101.

Пусть вектор ошибок при передаче по каналу связи вектора имел вид =001110011000110. Тогда в ходе фиксации вектора приема в блоке приема 1 и последовательной выработки для каждого бита этого вектора мягких решений в блоке мягких решений 2 формируется совместная последовательность жестких решений символов и соответствующих им целочисленных МРС. В результате в накопителе оценок 3 фиксируется вектор вида:

Последовательность МРС в блоке мягких решений 2 формируется по правилу , где – интервал стирания; – энергия сигнала, приходящаяся на один бит; – уровень принятого сигнала (модулируемого параметра); – фиксированная целочисленная оценка МРС с максимальным значением, как правило, определяемая конструктором декодера (см. А.А. Гладких. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи, Ульяновск : – 2010 с. 211). Целесообразно, например, назначит , , . Тогда вектор для накопителя оценок 3 мог быть получен по результатам фиксации в блоке приема 1 параметра , как показано в таблице 1.

Таблица 1

Оценка мягких решений символов в блоке 2

№ символа 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1,4 -1,4 0,8 -0,6 1,1 -1,7 -1,7 -1,1 -1,4 1,9 1,9 -1,9 -1,4 1,1 1,7 5 5 3 2 4 6 6 4 5 7 7 7 5 4 6

Упорядоченный вектор имеет вид

Для дальнейшей организованной обработки вектор представляется в виде двух лексикографически упорядоченных кортежей последовательностей нумераторов: кортеж [k]= [6 7 10 11 12] (информационная часть) вектора и кортеж [n-k] = [1 2 3 4 5 8 9 13 14 15] (проверочная часть) этого вектора

[6 7 10 11 12] и [1 2 3 4 5 8 9 13 14 15].

Копия последовательности [k] поступает в блок интервальных оценок 5. В блоке 5 для нумераторов , формируется последовательность интервальных оценок вида , как расстояния между соседними нумераторами этой последовательности.

Установлено, что любые ОКО в лексикографическом формате начинаются с нумератора, равного единице (см. Гладких А.А., Овинников А.А., Пчелин Н.А., Брынза А.А. Перестановочное декодирование с системой адаптированных альтернативных решений / Цифровая обработка сигналов, М. : – 4/2023, С. 73-78).При этом для любой орбиты выявлена закономерность, которая заключается в том, что интервальные оценки для локальных орбит имеют значения, характеризующие свойства локальных орбит, как показано ниже:

Комбинация ОКО Разница соседних интервалов Тип ОКО 1 2 5 6 7 1 3 1 1 Сборная орбита 1 1 10 11 14 15 9 1 3 1 Локальная орбита 2 1 2 11 12 15 1 9 1 3 Локальная орбита 3 1 2 3 12 13 1 1 9 1 Локальная орбита 4 1 4 5 6 15 3 1 1 9 Локальная орбита 5

При этом кортеж [6 7 10 11 12] входит в орбиту 1, как циклический сдвиг ОКО [1 2 5 6 7].

Любая перестановка нумераторов может быть идентифицирована только в одном из двух блоков: либо в блоке 7, если определитель ОКО 1 не равен нулю, или в блоке 8, если определитель ОКО 1 напротив равен нулю. Если перестановка определена в блоке 7, то отсутствие сигналов коррекции на другом входе блока упорядочения оценок 4 приводит к передаче второй упорядоченной последовательности кортежа [n-k] из блока упорядочения оценок 4 через второй выход на второй вход блока эквивалентного кода 11. Вопрос формирования эквивалентного кода считается решенным. Для этого в блоке 7 восстанавливается последовательность вида 6 7 10 11 12 и в этом блоке по этим параметрам в когнитивной карте находится структура обратной матрицы которая является эталоном для формирования любых перестановок из лексикографически упорядоченной последовательности нумераторов 6 7 10 11 12.

Следует учесть, что упорядоченная последовательность порождает (5!–1) неупорядоченных последовательностей перестановок при нахождении для каждой из них обратной матрицы нет необходимости вычислять обратную матрицу традиционным способом с использованием системы алгебраических дополнений. Для конструирования таких матриц необходимо сохранить в произвольной обратной матрице ту последовательность строк, которая задана текущей выборкой . Например, задана последовательность вида 7 12 6 11 10. Тогда получаем:

= .

Таким образом, когнитивная карта РПН 7 должна хранить образцы строк обратных матриц, и конструктор обратных матриц собирает требуемую перестановку из тех записей, которые соответствуют текущему кортежу данных из [k] в лексикографически упорядоченной форме. Следующим этапом обработки данных будет получение порождающей матрицы ЭК. Для этого целесообразно использовать уже полученную ранее последовательность:

Таким образом, блок 7, когнитивная карта РПН, должен хранить только образцы строк обратных матриц, а блок 10, корректор перестановки, собирает требуемую перестановку из тех записей, которые соответствуют текущему кортежу данных в лексикографически не упорядоченной форме, отличной от эталона последовательностью строк. После чего откорректированная обратная матрица из блока 10 поступает на второй вход блока эквивалентного входа 11.

Следовательно, требуется использовать столбцы проверочной части порождающей матрицы основного кода в переставленном виде. В результате для последовательности столбцов из кортежа [n-k] вида [15 1 2 9 13 5 8 14 3 4], поступающей из блока упорядочения оценок 4 в блок эквивалентного кода формируется образ проверочной части порождающей матрицы ЭК с использованием данных из матрицы . Получаем:

После умножения получаем истинную проверочную часть порождающей матрицы ЭК:

Информационный кортеж [k] представлялся для обрабатываемого ЭК в виде вектора 1 1 0 0 0. Это означает, что безошибочный вариант проверочной части порождающей матрицы ЭК потребует обработки только первых двух строк. В результате такой обработки в блоке эквивалентного кода 11 будет получен вектор вида, который передается в блок локаторов ошибок 12.

Сравнивая проверочные части, поступившие из блока эквивалентного кода 11 и из блока упорядочения оценок 4 в блоке локаторов ошибок 12 будет получена последовательность нумераторов ошибочных символов, как показано ниже:

В нижней строке выделены номера позиций нумераторов, которые из блока локаторов ошибок 12 поступают на второй вход блока исправления стираний 13.Последовательность 9 13 5 8 14 3 4 соответствует указанному выше вектору помех в переставленном виде. Таким образом показана возможность перестановочного декодера исправлять ошибки за пределами границы Хэмминга.

В случае, если определитель переставленной матрицы предполагаемого ЭК равен нулю, что означает отсутствие сигналов по поиску такого кода в когнитивной карте РПН блока 7 и тогда обработка данных для такой последовательности осуществляется в блоке когнитивной карты НПН 8. В блоке альтернатив 9 определяется содержанием коррекции обеспечивающих получения ЭК за счет неиспользованных символов из кортежа [n-k], позволяющих адаптивно трансформировать перестановку НПН в перестановку РПН. Для этого правый разряд (нумератор символа) из кортежа [k] заменяется на левый незадействованный символ из кортежа [n-k]. Например, как показано ниже.

Комбинация ОКО Разница соседних интервалов Запрещенные нумераторы 1 2 3 4 6 1 1 2 2 8 9 12 2 12 13 14 15 10 1 1 1 3 4 7 1 3 13 14 15 2 10 1 1 ВСЕ 1 2 4 14 15 1 2 10 1 6 7 10 1 2 3 5 15 1 1 2 10 7 8 11

Заменяя в первой сроке последовательность 1 2 3 4 6 на последовательность 1 2 3 4 15 в блоке упорядочения оценок 4, получаем перестановку из множества РПН. ЭК может быть получен.

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

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

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