Генератор комбинаций двоичного эквивалентного кода

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

 

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

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

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

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

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

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

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

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

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

Структурная схема генератора комбинаций двоичного эквивалентного кода представлена на фигуре, где:

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

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

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

4 - блок упорядоченных оценок;

5 - блок отрицательных решений;

6 - блок нумераторов;

7 - блок когнитивной карты;

8 - блок перестановок эталонной матрицы;

9 - блок сложения;

10 - блок жестких решений;

11 - блок информационных разрядов;

12 - накопитель комбинации.

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

Вход блока приема 1 является общим входом генератора комбинаций двоичного эквивалентного кода, а выход накопителя комбинаций 12 является общим выходом устройства.

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

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

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

МРС вектор V_мpc преобразуется к виду:

Блок упорядоченных оценок 4 выделяет из переставленного вектора V_пpc нумераторы первых k символов, формируя последовательность 1 7 2 5, которая затем приводится к упорядоченному виду: 1 7 2 5 1 2 5 7. Упорядоченная последовательность 1 2 5 7 направляется в блок отрицательных решений 5, где лексикографически сравнивается с образцами запрещенных перестановок, приводящих к формированию вырожденных матриц, что однозначно не позволяет получить эквивалентный код. Перечень таких перестановок для кода (7, 4, 3) приведен в таблице 1.

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

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

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

Извлечение и последовательность преобразования шаблона в соответствии с данными из блока нумераторов 6.

К моменту завершения операции перестановок эталонной матрицы в блоке 8 из блока упорядоченных оценок 4 в блок жестких решений 10 поступает комбинация переставленных информационных битов 1 1 0 0 0 0 0. Этот блок выделяет информационные разряды из полученной последовательности направляет их в блок информационных разрядов 11. Таким образом блок 11 получит данные из блока 10 в виде последовательности бит 110 0, которые направляются в блок сложения 9 для формирования проверочной части кодового вектора за счет сложения данных первой и второй строки матрицы H₂. Следовательно, 101⊕011=110. Эти данные направляются в накопитель комбинации 12, где объединяются информационные и проверочные разряды и в результате этого формируется вектор переставленного кода вида

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

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

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

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