Декодирование полярных кодов в декодере Арикана на базе индексов мягких решений

Современный этап развития сетевых технологий характеризуется постоянным поиском новых решений для повышения пропускной способности каналов связи сетевых структур с выполнением заданных требований по достоверности. Одним из предложений в этой предметной области явились полярные коды (ПК), которые способны в каналах с гауссовским шумом до стигать пропускной способности двоичных симметричных каналов (ДСК) без памяти [1].

Технология обработки ПК опирается на преобразование непрерывного канала связи в систему векторных каналов с перекрестными связями и полным исключение из анализа принятой последовательности тех каналов, в которых передача битов оказывается заведомо ненадежной. Пропускную способность таких каналов принято считать равной нулю (каналы считаются «замороженными»), а восстановление данных осуществляется за счет информации, полученной из надежных каналов. Путем использования ПК достигается повышение энергетической эффективности системы связи в целом. Однако структура ПК не лишена недо статков: результат каждого шага декодирования полностью зависит от достоверности оценок информационных битов предшествующих шагов [2].

Полярное кодирование

Положительную роль в преодолении этой зависимости играют мягкие методы обработки данных [3]. Рассматриваемая структура ПК является типичным представителем класса блоковых кодов. Для определения возможностей таких кодов по коррекции ошибок необходимо оценить их граничные параметры. В случае линейного кода при фиксированных длине комбинации N и числе информационных разрядов K можно получить верхнюю и нижнюю границы для наибольшего минимального расстояния. В качестве верхней границы целесообразно использовать границу Бхаттачария, которая определяется на основе знания условных выходных распределений. Граница Бхаттачария является мерой вероятности ошибки и определяется как:

где                – условные распределения, имеющие равновероятностный характер. В работе [4] было показано, что в случаи ДСК граница Бхаттачария равна:

Применив неравенство Шварца к выражению (2), получим верхнюю и нижнюю границы для параметра Бхаттачария, которые равны        .

Для канала с двоичным входом выражение примет вид [4]:

где M – число кодовых векторов в ансамбле. При этом для линейных кодов, используемых в этом классе каналов, вероятность ошибки определена без учета ансамбля сигналов (использовано в качестве ограничения по сумме):

м

К где          – веса ненулевых кодовых слов.

При        для всех        существует ортогональный код, такой, что            при всех

. В этом случае получаем границу [4]:

P_E exp(-7V(-O,5 In Z)).        (5)

Легко заметить, что показатель экспоненты в выражении (5) больше, чем в (3), то есть -0,5 InZ > ln2-ln(l + Z); 0

Целью применения ПК является создание такой решающей схемы, при котором Z^P) -> 0, тем самым вероятность ошибочного приема так- же стремится к нулю, как было сказано ранее.

Концепция формирования ПК построена на базе ядра Арикана. Ядром Арикана называют матрицу

r? ®m а через величину обозначают ее m-ую кронекеровскую степень, в основе которой лежит кронекеровское (прямое) произведение матриц [1]. Для получения требуемого выходного вектора необходимо произвести преобразование последовательности таким образом, чтобы номер новой позиции i-го элемента получился как обратная запись числа i, то есть полярное представление. Например, 1 = (0 0 0 1) ^ (1 0 0 0) = 8 [2]. Таким образом, для получения соответствующей матрицы необходимо ввести матрицу перестановок В "

Результирующая матрица G®"* определяется следующим выражением:

_pi 0m g                     (6)

Для осуществления операции поляризации необходимо произвести трансформацию скалярного канала в векторный канал, отождествляя его с функцией плотности условной вероятности выходного символа [2]. Это достигается за счет создания копий ДСК рекурсивным способом, как представлено на рис. 1. Рекурсия начинается с 0-го уровня (n = 0) посредством применения только одного экземпляра P , и ему ставится в соответствие P1 — P.

На первом уровне рекурсии схема сочетает в себе две независимых копии P^ тем самым мы получаем канал P, с вероятностью переходов P₂ (y, |y₂ |w!, Z./₂ ) = p(y, \ll_v ® И₂ ) • p(y ₂ |w₂ ). Схема построения такой системы кратна степени 2 начиная с нуля. На рис. 1 матрица перестановок B_N имеет входы (/] ,1_г,1₃,...l_N_^ )■

Рис. 1. Рекурсивный способ формирования кодового вектора

Общая форма рекурсивной зависимости равна ^PN tr |^МГ )= ^pN (у^ |^МГ^GN )■ Стоит отметить, что процесс формирования матрицы перестановок ^PN удовлетворяет следующим соотношениям (для случая, когда m = 2):

Очевидно, что связи между входами и выходами формируются исходя из правила: входы ранжируются по четным и нечетным номерам (зависит от нулевой точки – нумерация с нуля или единицы), им ставятся в соответствие выходы, нумерация которых осуществляется строго по порядку с нулевой точки.

Матрица G , как отмечалось ранее, получается посредством прямого произведения матриц F. Длина блока N определяется кронекеровской степенью m^>N = 2 . То есть при m = 1 матрица G равна ядру Арикана, при m = 2 и m = 3 имеем G®" и G соответственно. При N ^ co каналы Pj будут либо полностью бесшумные, либо полностью ненадежные. В связи с этим информационные символы U •, передаваемые по каналам с низким уровнем достоверности, можно считать всегда фиксированными («замороженными»). Рассмотрим принцип фиксации каналов на основе матрицы G . Строкам матрицы G®3 с весом w< 4 поставим в соответствие каналы с фиксированными значениями равными нулю на основе правила Рида-Маллера, как представлено на рис. 2. Необходимо обратить внимание, что модифицированная матрица G,®3 степени m = 3, образуется из строк матрицы G®3 с весом w> 4.

Таким образом, мы переходим из пространства 2M в пространство M, поставив данным каналам в соответствие нулевое значение (коды с выбрасыванием).

1 о о о о о 0 o' 11OOOOOO 1 0  1  0  0 0  00

G.3_ 1 1  1  1  О О  00 ,

“ 1 0 0  0  1 0  00

110 0 1100

10 10 1010

J 1 1 1 1 1 1 1^

X = [uq Ul ^u2 Uj «4 U5 Ug U?]G®³ , x = [000U30u₃ Us u?]G®³

замороженные uo  —----► Уо u замороженные ^ u замороженные ^

,,       данные

°3 --- ► y3

u замороженные ^

данные

«5 -----------► У3

u6    да11™ , Уб u7    да1™ r y?

Рис. 2. Принцип фиксации зашумленных каналов

Это позволяет уменьшить вероятность ошибки для систем передачи данных. Однако стоит отметить, что для корректной оценки кодового вектора, как отмечалось ранее, целесообразно использовать границу Бхаттачария. Ранговый вектор ^Z N-V (^jV-1.0 ’ ^jV-1,1 ^Z N-Y.N-Y ) определяется через рекурсивное соотношение по четным и нечетным каналам [5-6]:

Для матрицы G ранговый вектор равен ^ZN-Y = (0,996; 0,88; 0,81; 0,32; 0,68; 0,191; 0,121; 0,004).

При сопоставлении двух векторов X N И ^^ (первый представлен на рис. 2.) можно заметить, что высказанная теория об оценки канала связи посредством параметра Бхаттачария дает идентичные результаты по отношению к правилу Ри-да-Маллера. Данное сопоставление представлено в таблице 1.

Из таблицы 1 видно, что «замороженным» каналам ставится в соответствие параметр Бхат-тачария Z(P)^1. Как отмечалось ранее, при z = \ мы получим полностью зашумленные каналы, передача по которым нецелесообразна. В связи с этим данные, полученные из источника сообщений, передаются через каналы с номерами (3, 5-7). Введем множество A , элементы которого полностью идентичны номерам каналов связи и равны A* = {0, 1,.....^-l}. При применении правила Рида-Маллера или оценки по параметру Бхаттачария множество A распадается на два подмножества А и A ^f, где A – множество номеров «незамороженных» каналов связи, а A- – множество «замороженных» каналов.

Матрица G также распадается на две под-z~i®3    z~i®3     /^03

матрицы nf ^ ^ frozen ^? ^nf – матрица, строки которой имеют вес w> 4, а ^frozen – матрица, где w<4.

Общий вид выражения для получения выходного вектора определяется следующим соотношением:

N-\ ^ A ^nf ^ A^ ^frozen ⁵(8)

где ¹¹A – символы, соответствующие «незамороженным» каналам связи, a и^_f – «замороженным».

Пропускная способность канала со стираниями

Применение мягких методов обработки принятых данных позволяет добиться дополнительного энергетического выигрыша, а применение ПК является новым развитием системы комбинации кодовых методов обработки информации. В [7] было показано, что пропускная способность ДСК определяется соотношением С, где 8 – вероятность ошибки на бит. В случае применения двоичного стирающего канала связи (ДСКС) про-

Таблица 1. Сопоставление векторов ^XN-Y ^{И Z}N-\

пускная способность равна с, где q – вероятность стирания, а p – вероятность ошибки нестертого символа.

Очевидно, что С дек— С деке ’ причем равенство достигается при р,£^0. Обозначим через С мд пропускную способность канала связи при мягких методах (МД) обработки символов, тогда С дек— С МД — С деке ■ В случае формирования индексов мягких решений (ИМР) на основе стирающего канала связи значения С мд при разных интервалах стирания у могут быть представлены кривыми на рис. 3.

Рис. 3. Зависимость пропускной способности от ширины интервала стирания при разных отношениях «сигнал/шум»

Величинаh = lQ^E_b/N^ определяется в дБ, где Е_ь – энергия сигнала на бит, а NQ – спектральная мощность белого гауссовского шума. Под ИМР понимается мягкая оценка жесткого решения, вырабатываемая демодулятором. Как показано в [3], подобная оценка в целочисленном формате без знания статистических характеристик канала связи определяется следующим соотношением:

£(и, | z)

где М – математическое ожидание модули- руемого параметра. Подобный подход полезен в условиях быстрого переключения в процессе ных ИМР [2], а их применение способствует уменьшению вероятности ошибки в последовательном декодере Арикана. Подобные оценки могут быть сформированы в стирающем канале связи без знания статистических характеристик этого канала [3].

Последовательный декодер Арикана

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

Для каждого / = 0, 1,......^-l. Если Uj G A'f , тогда и, = О . Иначе вычислим оценку

если L^ (уо¹, w' ¹) > 0 ; в противном случае.

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

L^4yr,uD = tog

УЧуГа^З^ Р^ЧуГ,иГ\^

В данной работе предложено, что декодер производит не просто вычисление ^(yr,<"4 для оценки символа по отношению к пороговому значению, а дополнительно для каждого бита сообщения производит вычисление ИМР с целью оценки надежности. В большинстве аналитических оценок эффективности процедуры мягкого декодирования помехоустойчивых кодов в качестве ИМР символов принимается значение ЛОП. Этот параметр для двоичных систем модуляции определяется как:

передачи с одного канала на другой. Доказано, что пропускная способность ДСК может достигать значения 1 за счет применения схемы по-

L^u, | z) = In

P^i, = +11 z)

P^iy =-l|z)

лярного кодирования, а применение мягких методов обработки символов способствует более быстрому достижению этого предела [1; 8]. В процедуре декодирования ПК была установлена целесообразность применения целочислен- где Uj = ±1 – возможные значения переданного бита; z – принятый уровень сигнала. Для одного принятого символа Zj = +1 , а значение ЛОП для канала с независимым потоком ошибок в усло- виях применения двоичной фазовой модуляции определятся выражением [9]:

L^u, |z,.) = ln

P(z/_; I Zj = +1)

^"\l b Zi

где a – дисперсия шума. В случае применения каналов с общими замираниями и коэффициентом затухания к выражение для ЛОП принимает вид

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

В выражении (10) отсутствует параметр о¹ . Проведенными статистическими испытаниями показано, что знание параметра о необходимо при больших отношениях «сигнал/шум», а при малых отношениях «сигнал/шум» ИМР [10] определяется с некоторой погрешностью, характер которой выявлен с помощью метода по соотношению

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

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

Декодирование на основе графа Таннера

^ ^ (^1 , H 3 ) — ^

(Я.СО-Я^ (я^о+я^))

Построение двудольного графа Таннера для последовательности N = 8 позволяет установить связи между исходными символами кодовой по-

где Я, (z) – i-ый интервал гистограммы, определенный методом логарифмического отношения правдоподобия, а Я_э (z) – интервал гистограммы, вычисленный по методу стирающего канала связи. В результате сравнения указанных гистограмм были получены результаты, приведенные на рис. 4.

следовательности и символами выходного вектора после преобразования через матрицу G . Данная зависимость представлена на рис. 5. Подобный подход не имеет такого недостатка, как лавинообразное распространение ошибок, в силу наличия проверочных уравнений. Кроме того, применения ИМР также снижает вероятность ошибки декодирования.

Рис. 4. Зависимость % от соотношения «сигнал/шум»

Рис. 5. Связи векторов UN-\^И ^№-1

Запишем уравнения связи:

x₀ = u_x Ф zz₂ Ф zz₃ Ф zz₀; x, = z/₃ Ф z/₅ Ф u_x;

x₂ = u₃ Ф u₆ Ф u₂; x₃ = u₂ Ф u₃;

x₄ = u₅ Ф u₆ Ф z/₄; x₅ = i/₇ Ф u₅;

x₆ = i/₇ Ф u₆; x₇ = tz₇.

При реализации подобного решения необходимо учитывать тот факт, что при получении ИМР

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

Af = {0,1,2,4}

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

■ U3

X у = u 7

.         Uj A = {3,5,6,?}

' . ue

0 = U] © u2 © u3 © x0

0 - u3 © u5 © Xj

0 = u₃ © u₆ © X 2

0 = u5 © u6 © x4 u0 - u- - u 2 - u4 - 0

Рис. 6. Декодирование на основе графа Таннера

Заключение

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

Универсальность метода формирования целочисленных ИМР обеспечивает снижение вероятности ошибки в декодере Арикана за счет сопровождения каждого принятого символа соответствующим мягким решением. Это позволяет декодеру целенаправленно выполнять процедуру рекурсии с меньшим риском размножения ошибок.

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