ЛЕКСИКОГРАФИЧЕСКИЙ ДЕКОДЕР КАСКАДНОГО КОДА

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

Известны устройства восстановления стираний и исправления ошибок, использующие индексы мягких решений (индекс достоверности символов, градации надежности символов) для повышения достоверности приема информации (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применения. М., Техносфера, 2005, С. 103, …, 105; а также устройства по патентам РФ на изобретения №№2166235; 2209519; 2209520; 2256294; 2344556; 2538331).

Кроме того, известны устройства декодирования недвоичных кодов Рида-Соломона (PC) (см. В.К. Конопелько, В.А. Липницкий. Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов. Изд. 3-е. - М., Едиториал УРСС, 2012. - С. 9-15; а также В.Г. Карташевский, Д.В. Мишин. Итерационное декодирование турбо-кодов в канале с памятью // 3-я Международная конференция и выставка «Цифровая обработка сигналов и ее применение». - М., 2000. - С. 65-68).

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

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

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

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

Работу декодера рассмотрим на примере использования в качестве внутреннего кода - кода с проверкой четности, а в качестве внешнего кода - код PC (7, 3, 5), построенного над полем GF(2³).

Порождающий полином такого кода PC g(х) определяется как

g(x)=(x-α)(x-α²)(x-α³)(x-α⁴)=x⁴+x³α³+x²+xα+α³.

Используя значение g(x), представим некоторые кластеры кода PC в виде таблиц 1-4. Номера кластеров формируются по любым двум элементам кодовой комбинации кода PC одинаковым для всего множества разрешенных кодовых векторов (см. Гладких, А.А. Обобщенный метод декодирования по списку на базе кластеризации пространства кодовых векторов. Радиотехника. - 2015. - №6. - С. 37-41) и упорядочиваются лексикографически. Пусть в качестве таких элементов для всех кодовых комбинаций выбраны первые два символа. Общее число комбинаций любого кода PC, рассматриваемого над двоичным полем Галуа степени расширения k₁, оценивается как , где k₁ - степень расширения двоичного поля, а k₂ - число информационных разрядов кода PC. В примере k₁=k₂=3, тогда для рассматриваемого кода может быть сформировано 64 кластера, каждый из которых содержит по 8 комбинаций. Базовым кластером считается кластер с номером 00.

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

Работа блока приема 1 организуется по принципу стирающего канала связи с симметричным интервалом стирания ρ, где 0≤ρ<1 и представляет долю расстояния в системе условных плотностей вероятностей в гауссовском канале связи между математическими ожиданиями и , соответствующих приему информационных нулей и единиц, где E_b - энергия сигнала, приходящаяся на бит. В целях повышения достоверности индексов мягких решений параметр ρ выбирают достаточно большим, например ρ=0,9. Зафиксированный в блоке приема 1 сигнал |z| и соответствующее ему жесткое решение 0 или 1 передаются в блок индексов 2.

В блоке индексов 2 оценивается влияние мешающих факторов на двоичные символы переданного вектора внутреннего кода в виде целочисленных мягких решений символов (MPC). Для вычисления MPC применяется линейная зависимость (см. Гладких, А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. Ульяновск: УлГТУ, - 2010. - 379 с., С. 211). Пусть выбрано максимальное значение MPC λ_max=7. Тогда минимальное значение MPC будет равно λ_min=0. Промежуточные оценки для i-го символа в блоке индексов 2 получают по правилу

где - z уровень сигнала после воздействия на него аддитивной помехи, символ ⎣•⎦ означает округление полученного значения λ_i до целочисленной величины в сторону уменьшения (расчет на наихудший случай), ρ=0,9. Таким образом, выражение (1) при заданных условиях упрощается и принимает вид λ_i≅5,5×z. Следовательно, если z≥1,27, то λ_i=λ_max.

На основе полученных данных для двоичных символов в блоке статистических решений 3, осуществляется интегрированная оценка надежности q-ичных символов кода PC. Для выполнения такой оценки в блоке статистических решений 3 решается задача поиска целевой функции для каждого q-ичного символа кода PC. Обозначим через (+pc) выполнение условия четности на приемной стороне для принятого кодового вектора внутреннего кода. В противном случае приемник фиксирует значение (-pc). Работу декодера с проверками на четность целесообразно описывать целевой функцией вида

где S - значение четности по всем информационным разрядам принятого вектора; параметр |M(λ)| - среднее значение кортежа модулей мягких решений символов; параметр σ(λ) является показателем разброса мягких решений, вычисляемого по правилу:

По отдельности представленные параметры не являются информативными и не позволяют взвешенно оценить приоритеты очередности обработки нескольких кодовых символов комбинации кода PC. В соответствии с Q{•} блок 3 выполняет проверку четности, на втором шаге обработки данных оценивает среднее значение принятых индексов MPC и в последнюю очередь определяет дисперсию для MPC кодовой комбинации внутреннего кода. Максимальное значение параметра |M(λ)| соответствует высокой достоверности принятых символов, но на длине кодовой комбинации кода PC может быть получено несколько одинаковых значений |M(λ)|. В подобной ситуации блок 3 дополнительно оценивает параметр σ(λ). Если возникает ситуация неопределенности, когда |M_i(λ)|=|M_j(λ)| при i≠j, то приоритетной для последующей обработки данных является комбинация, у которой разброс оценок оказывается меньше, т.е. при σ_i(λ)<σ_j(λ) приоритет отдается комбинации с номером i. Для символов кода PC назначается всего три приоритета недвоичных символов (ПНС): низкий - 0; средний - 1 и высокий - 2.

В случаях невыполнения условий четности в блоке итерации 4 осуществляется повышение значений MPC при условии, что проверочные символы комбинаций приняты надежно (см. Гладких, А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. Ульяновск: УлГТУ, - 2010. - 379 на С. 334). Обработанная подобным образом комбинация внутреннего кода хранится в блоке внутреннего кода 5, а ее значение Q{•} хранится в блоке приоритетов 6. Комбинация кода PC накапливается в буфере внешнего кода 7, а оценки ПНС комбинации кода PC накапливаются в блоке номера кластера 8, который оценивает надежность номинальных символов кластера, и в случае выполнения условий по надежности для этих символов (нумераторы кластера имеют высокие приоритеты) объединенные данные блока 7 и блока 8 передаются в блок циклических сдвигов 9 с указанием: «Δ=0», при этом значения кодовой комбинации кода PC передаются в блок обрабатываемой комбинации 11, а команда «Δ=0» транслируется в блок обратных сдвигов 15. Параметр Δ - указывает число циклических сдвигов элементов кодовой комбинации влево.

Пусть кодер канала связи сформировал вектор

V_пер=α⁰ α³ α⁶ α⁶ α⁵ α³ α⁵,

в котором для защиты номера кластера, содержащего первые два элемента α⁰ и α³, выполняется их поразрядное сложение по модулю два и результат сложения записывается на заранее обусловленное место в векторе V_пер (см. патент РФ №24444127). . Если результат фиксируется на последней позиции передаваемой комбинации, то вектор V_пер принимает вид

.

Пусть при передаче вектора по каналу связи вектор помех имел вид

V_пом=0 0 0 α³ α⁴ α⁵ 0.

В этом случае приемник получает вектор

,

где нижние индексы степеней примитивного элемента поля показывают значения ПНС, по результатам анализа которых в соответствии с Q{•} первые три символа кода PC α⁰α³α⁶ оказываются с наибольшим приоритетом. В блоке номера кластера 8 проверяется четность элементов (α⁰ α³). Используя эту информацию, блок ключевой комбинации 10 путем кодирования первых трех надежных символов α⁰α³0 формирует ключевую комбинацию по номеру кластера (α⁰ α³):

.

В блоке обрабатываемой комбинации 11 выполняется сложение (по правилу недвоичного поля) найденной ключевой комбинации из блока 10 с вектором, полученным из буфера внешнего кода 7, что соответствует одной из комбинаций базового кластера

.

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

,

которая априори известна приемнику и является безошибочной. Сложение этой комбинации с принятым вектором в блоке обрабатываемой комбинации 11 формирует истинный вектор ошибок, который передается в блок выделения ошибок 14:

V_пом=0 0 0 α³ α⁴ α⁵ 0

Значение этого вектора через блок обратных сдвигов 15, который получил команду «Δ=0», без изменений поступает в блок исправления ошибок 16, в котором устраняется действие мешающих факторов.

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

Пусть кодер канала связи сформировал вектор

V_пер=α³ α³ α⁰ α⁶ α⁰ α⁵ α⁶,

который по условию проверки номера кластера приводится к виду

Пусть при передаче вектора V_пер по каналу связи вектор помех имел вид

V_пом=α¹ α² 0 α⁴ 0 0 0.

В результате принятый вектор становится равным

.

Проверка четности элементов кластера в блоке номера кластера 8 дает отрицательный результата: , но имеются надежные элементы и . На основе анализа ПНС блок циклических сдвигов 9 выполняет сдвиг элементов комбинации из буфера внешнего кода 7 влево на Δ=4 шага, при этом ПНС примитивных элементов поля синхронно сопровождают элементы кодовой комбинации из блока номера кластера 8. При условии Δ=4 на третьей позиции оказывается проверочный символ, который не может быть использован для идентификации комбинации базового кластера, поэтому блок циклических сдвигов 9 передает эту информацию блоку ключевой комбинации 10.

.

Блок 10 путем кодирования комбинации вида (α⁰α⁵0) формирует ключевую комбинацию по надежным символам номера кластера (α⁰ α⁵)

.

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

,

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

Вектор нуждается только в обратных циклических перестановках, которые выполнятся в блоке 16.

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

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