Перестановочный декодер с режимом обучения Российский патент 2018 года по МПК H03M13/05 G06F11/10 

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

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

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

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

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

Близкими к указанным свойствам заявляемого устройства обладает известный способ мягкого декодирования блоковых кодов (см. патент РФ 2580797), в котором процедура вычисления определителя матрицы эквивалентного кода заменяется анализом структуры определенных бит комбинаций выделенного кластера. Эти биты должны образовывать двоичное поле Галуа заданной степени расширения. Недостатком способа является замена регулярного алгоритма вычисления определителя матрицы переставленного кода на выделение комбинаций поля Галуа и оценку их соответствия заданным степеням примитивного элемента, что не является простой и однозначной задачей.

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

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

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

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

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

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

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

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

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

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

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

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

3 - детектор режимов;

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

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

6 - датчик последовательностей столбцов;

7 - переключатель режимов;

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

9 - накопитель кодовой комбинации;

10 - блок эквивалентного кода;

11 - блок контроля линейности;

12 - блок исправления стираний;

13 - блок сравнения и обратных перестановок;

14 - блок положительных решений.

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

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

.

Столбцы матрицы G нумеруются от 1 до 7 слева направо. Декодер может работать в двух режимах: во-первых, в режиме оперативной работы, во-вторых, в режиме обучения при отсутствии передачи полезной информации. Режимы определяются командами передатчика и в устройстве определяются детектором режимов 3. В случае оперативного режима работы детектор режимов 3 передает необходимую информацию из блока приема 1 через свой первый выход на вход накопителя кодовой комбинации 9. При использовании режима обучения детектор режимов 3 через свой второй выход включает датчик последовательностей столбцов 6, который генерирует сочетания последовательностей номеров столбцов матрицы G из общего набора объемом в комбинаций, а применительно к коду (7, 4, 3) из набора последовательностей.

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

.

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

,

где ρ - интервал стирания;

Е_в - энергия сигнала, приходящаяся на один бит;

Z - уровень принятого модулируемого параметра (сигнала) (см. А.А. Гладких. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи, Ульяновск. – 2010, с. 211);

λ_max - фиксированная оценка МРС с максимальным значением, как правило, определяемая конструктором декодера.

Пусть λ_max=7. В блоке упорядочения оценок 4 вектор V₅ принимает вид V₄:

.

Детектор режимов 3 через второй выход и датчик последовательностей столбцов 6 дает команду переключателю режимов 7 проключить его другой вход на третий вход блока эквивалентного кода 10. При этом блок 10 из блока упорядочения оценок 4 через переключатель режимов 7 получает переставленную последовательность номеров столбцов матрицы G в порядке убывания значений МРС в виде V₁₀→6743251.

Поэтому в блоке эквивалентного кода 10 матрица G принимает вид:

.

Одновременно с этим в блоке 4 формируется матрица перестановок Р₄, которая через блоки 7 и 10 передается в блок сравнения и обратных перестановок 13. Матрица P₄ в соответствии с упорядочением оценок МРС принимает вид:

.

В блоке 10 из матрицы G₁₀ выделяются первые k=4 столбцов, образуя квадратную матрицу вида:

.

Матрица F₁₀ передается в блок контроля линейности 11, где вычисляется определитель А для F₁₀. Если Δ≠0, то в блоке 11 формируется команда в блок 10 на поиск матрицы эквивалентного кода и одновременно с этим в блок положительных решений 14 заносится сочетание номеров первых k столбцов, которые обеспечили Δ≠0. Поскольку для F₁₀ Δ≠0, в блоке 14 будет зафиксирована переставленная последовательность V_пер=6743 В последующем блок 11 не сразу вычисляет значение Δ, а проверяет наличие сочетаний номеров столбцов в блоке отрицательных решений 8 (для случаев, когда Δ=0) и в блоке положительных решений 14 (для случаев, когда Δ≠0).

Если Δ=0, то блок 11 заносит в память сочетание номеров столбцов матрицы G, которое обладает свойством вырожденности. Тогда дается команда в блок 10 поменять местами в матрице G₁₀ k-столбец с (k+1)-столбцом и вновь отыскивается значение Δ. Возможна последующая замена k-столбца на (k+2)-столбец. В любом случае сочетание номеров столбцов, которые обеспечивают Δ=0 заносятся в блок 8, а при Δ≠0 заносятся в блок 14. Таким образом, происходит пополнение данных в блоках 8 и 14.

При Δ*0 блок 10 приступает к гарантированному вычислению матрицы G_l0, приводя ее к систематической форме:

.

Значение матрицы G_10экв заносится в память блока 14 с соответствующим ей ярлыком 6743. Умножая V_пер на G_10экв, получают вектор эквивалентного кода V_экв=(1101)×G_10экв=1101001, который с высокой вероятностью является безошибочным. Выполняя умножение , в блоке 13 получают обратные перестановки

Далее в блоке 12 осуществляется поиск вектора ошибок , после чего осуществляется исправление стираний, а результат их исправления поступает на выход декодера. Таким образом, в ходе оперативной работы устройства происходит заполнение данных в блоках 8 и 14.

В случае применения режима обучения детектор режимов 3 через блок 9 блокирует выход блока исправления стираний 12 и дает команду датчику последовательностей столбцов 6 на формирование последовательностей номеров столбцов матрицы G, имитируя реальную картину получения подобных сочетаний в ходе оперативного режима. Все новые значения сочетаний номеров столбцов и соответствующие им новые матрицы G_10экв при Δ≠0 заносятся в блок положительных решений 14. При Δ=0 значения сочетаний заносятся в блок отрицательных решений 8.

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

Суммарный объем памяти блоков 8 и 14 определяется соотношением . В примере этот объем с учетом значений матриц и их ярлыков составляет около 27 Кбит, что вполне приемлемо для программируемых логических интегральных схем (ПЛИС) при обработке коротких кодов, например, внутренних кодов в системе с каскадным кодированием. При этом экономия вычислительного ресурса после завершения процедуры обучения очевидна и зависит от конкретных характеристик используемых ПЛИС.

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

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