ПЕРЕСТАНОВОЧНЫЙ ДЕКОДЕР С ПАМЯТЬЮ Российский патент 2018 года по МПК H03M13/05 

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

Заявленное устройство расширяет арсенал мягкого декодирования двоичных избыточных блоковых кодов за счет исправления доли стираний, кратность которых выходит за пределы минимального кодового расстояния. Для этого используются известные свойства эквивалентных кодов (см. У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. Ред. Р.Л. Добрушин и С.И. Самойленко. М.: Мир, 1976. - С. 76-78). Для двоичных кодов реализация подобных свойств может иметь как положительный, так и отрицательный исход, который зависит от конфигурации конкретных перестановок принятых символов. Положительный результат формируется в том случае, когда выполненная по результатам оценки мягких решений перестановка символов принятой кодовой комбинации не приводит к линейной зависимости столбцов адекватно переставленной порождающей матрицы. В противном случае формирование эквивалентного кода положительного результата не дает. Количество положительных решений из общего множества возможных решений составляет большую часть.

Близким по технической сущности к заявленному устройству является способ мягкого декодирования систематических блоковых кодов, в основе которого лежит процедура ранжирования мягких решений символов (МРС) принятой кодовой комбинации, выделения из них наиболее надежных символов по показателям МРС, переход к эквивалентному коду с последующим вычислением вектора ошибок, действовавшего на принятый кодовый вектор в процессе передачи его по каналу связи (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М., Техносфера, 2005, С. 213, …, 216). Достоинством способа является возможность исправления стираний не только кратности (d-1), но и большей доли стираний кратности (n-k), где d - метрика Хемминга, n - число символов в кодовом векторе, k - число информационных разрядов в нем.

Недостатком указанного способа является необходимость вычисления для каждой принятой кодовой комбинации определителя переставленной порождающей матрицы кода в соответствии с показателями МРС для ее первых k столбцов. При невырожденности указанной матрицы для нее выполняется поиск обратной матрицы и вычисление на этой основе порождающей матрицы эквивалентного кода в систематической форме (см. Гладких А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. Ульяновск: УлГТУ, 2010, С. 286-295).

Кроме того, известен способ мягкого декодирования систематических кодов (см. патент РФ 2444127), в котором с целью снижения вычислительных затрат в алгоритме поиска обратной матрицы вычисление матрицы эквивалентного кода при приведении ее к систематическому виду используют прием кластеризации множества разрешенных кодовых векторов, что позволяет обрабатывать определители матриц размерности не (k×k), а размерности (k-ƒ)×(k-ƒ), где ƒ - число бит, отводимых на нумерацию (в двоичной системе) формируемых в коде кластеров. Указанная процедура обеспечивает незначительное снижение вычислительных затрат, поскольку в значительной степени зависит от выбранного параметра ƒ, где 1≤ƒ<k.

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

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

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

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

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

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

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

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

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

Работу предлагаемого устройства рассмотрим на примере кода Хэмминга (7, 4, 3) с истиной порождающей матрицей G вида

Столбцы истиной матрицы G нумеруются от 1 до 7 слева направо. Пусть передатчик передает информационный вектор V_инф=1010, тогда в канал связи будет отправлен вектор V_кан=V_инф×G=1010011. Пусть вектор ошибок V_e имеет вид V_e=1100100. В ходе фиксации вектора приема V_пр в блоке приема 1 и выработки для каждого бита этого вектора мягких решений в блоке мягких решений символов 2 в накопителе оценок 3 фиксируется последовательность жестких решений символов и соответствующих им целочисленных МРС вида

Последовательность МРС в блоке 2 формируется по правилу

где ρ - интервал стирания; Е_в - энергия сигнала, приходящаяся на один информационный бит; Z - уровень принятого модулируемого параметра (сигнала); λ_mах - фиксированная оценка МРС с максимальным значением, как правило, определяемая конструктором декодера (см. А.А. Гладких. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи, Ульяновск. - 2010 с. 211). В примере λ_mах=7. В блоке упорядочения оценок 4 вектор V₃ после перестановок жестких решений по убыванию и соответствующих им МРС принимает вид

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

Одновременно с этим блок 5 получает переставленную последовательность номеров столбцов истиной матрицы G в порядке убывания значений МРС в виде V₅ → 6743251.

Для последующей обработки данных важны первые четыре номера этой последовательности (6 7 4 3). Для быстрого поиска положительного или отрицательного решения по данной перестановке в блоке 9 указанная последовательность ранжируется к виду (3 4 6 7). Все упорядоченные последовательности отрицательных решений хранятся в блоке 8, а упорядоченные значения ранжированных положительных решений хранятся в блоке 10. Упорядоченные последовательности могут быть подсчитаны заранее и введены соответственно в блоки 8 и 10. Для используемого в примере кода все сочетания номеров отрицательных решений представлены в таблице 1, а положительных решений - в таблице 2.

Для любого ранжированного сочетания решений из таблицы 1 справедливы будут всевозможные перестановки, общее число которых определяется как k!. Например, для первой позиции таблицы: 1253; 1325; 1352; …; 5123.

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

Сравнивая значения номеров столбцов, поступивших из блока 5 в виде (6 7 4 3) и приведенных в блоке 9 к виду (3 4 6 7), со значениями таблицы 1, декодер устанавливает отсутствие такой комбинации в отрицательных решениях. Сравнивая это же значение (3 4 6 7) с ранжированными положительными решениями, декодер находит аналогичную комбинацию в памяти блока 10 и приступает к формированию порождающей матрицы эквивалентного кода. На оставшихся (n-k) позициях обрабатываемого вектора могут быть только номера символов, не вошедшие в первые k номеров. Если их упорядочить по возрастанию, то получится эталонная переставленная матрица некоторого эквивалентного кода. Такими номерами в примере является последовательность (1 2 5). Образцы эталонных матриц в систематической форме для всех 28 элементов из таблицы 2 хранятся в блоке матричных преобразований. Для приведенного примера эталонная матрица G_3467125 в систематическом виде имеет вид

С учетом номеров строк и столбцов проверочной части матрицы.

В блок матричных преобразований 11 через третий выход блока ранжирования 9 поступают данные о текущей последовательности перестановок в виде (6743251). В блоке 11 по первым k элементам сортируются строки эталонной матрицы, по оставшимся (n-k) элементам сортируются столбцы проверочной части матрицы.

Умножая надежную часть вектора (1 1 0 1) из V₄ на , в блоке сравнения и обратных перестановок 7 получают вектор эквивалентного кода вида V_экв=1101101. Складывая и умножая результат сравнения на Р^T, в блоке 7 получают истинный вектор ошибок, действовавший в канале связи в момент передачи вектора V_кан или V_e=1100100. Значение этого вектора позволяет исправить стирания в блоке исправления стираний 6.

Предложенное устройство в полной мере использует свойство линейных преобразований матриц и сокращает объем памяти для хранения эталонных матриц в k!×(n-k)! раз. При этом максимально используется введенная в код избыточность и исключаются такие матричные операции, как вычисление определителей и последующий поиск порождающих матриц эквивалентных кодов и последующее приведение их к систематической форме.

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

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