DECODING POLAR CODES IN DECODER OF ARIKAN ON BASED INDEXES SOFT-DECISIONS

Full Text

Введение. Современный этап развития сетевых технологий характеризуется постоянным поиском новых решений для повышения пропускной способности каналов связи сетевых структур с выполнением заданных требований по достоверности. Одним из предложений в этой предметной области явились полярные коды (ПК), которые способны в каналах с гауссовским шумом достигать пропускной способности двоичных симметричных каналов (ДСК) без памяти [1]. Технология обработки ПК опирается на преобразование непрерывного канала связи в систему векторных каналов с перекрестными связями и полным исключение из анализа принятой последовательности тех каналов, в которых передача битов оказывается заведомо ненадежной. Пропускную способность таких каналов принято считать равной нулю (каналы считаются «замороженными»), а восстановление данных осуществляется за счет информации, полученной из надежных каналов. Путем использования ПК достигается повышение энергетической эффективности системы связи в целом. Однако структура ПК не лишена недостатков: результат каждого шага декодирования полностью зависит от достоверности оценок информационных битов предшествующих шагов [2]. Полярное кодирование Положительную роль в преодолении этой зависимости играют мягкие методы обработки данных [3]. Рассматриваемая структура ПК является типичным представителем класса блоковых кодов. Для определения возможностей таких кодов по коррекции ошибок необходимо оценить их граничные параметры. В случае линейного кода при фиксированных длине комбинации N и числе информационных разрядов K можно получить верхнюю и нижнюю границы для наибольшего минимального расстояния. В качестве верхней границы целесообразно использовать границу Бхаттачария, которая определяется на основе знания условных выходных распределений. Граница Бхаттачария является мерой вероятности ошибки и определяется как: Z = ^|0) P^l), (1) где Р(у\0) и Р(у\1) - условные распределения, имеющие равновероятностный характер. В работе [4] было показано, что в случаи ДСК граница Бхаттачария равна: z = 4ap (1-Р). (2) Применив неравенство Шварца к выражению (2), получим верхнюю и нижнюю границы для параметра Бхаттачария, которые равны 0 < Z < 1. Для канала с двоичным входом выражение примет вид [4]: РЕ <М exp(-iV[ln2-ln{l + Z}]), (3) где M - число кодовых векторов в ансамбле. При этом для линейных кодов, используемых в этом классе каналов, вероятность ошибки определена без учета ансамбля сигналов (использовано в качестве ограничения по сумме): м РЕ ^ZexP(w* lnZ)’ (4) к где wK WM - веса ненулевых кодовых слов. При M = N для всех N = 2К существует ортогональный код, такой, что wK = N12 при всех К Ф 1. В этом случае получаем границу [4]: «Инфокоммуникационные технологии» Том 12, № 3, 2014 12 Гладких А.А., Чилихин Н.Ю. РЕ<М ехр(-АГ(-0,5 ln Z)). (5) Легко заметить, что показатель экспоненты в выражении (5) больше, чем в (3), то есть - 0,5 ln Z > ln 2 - ln(l + Z); 0 <Z<\, причем равенство выполняется тогда и только тогда, когда Z - 1. Из выражений (1) и (2) видно, что случай z = o описывает каналы без шума и что с увеличением шума Z растет монотонно так, что канал становится бесполезным при Z - 1 [4]. Таким образом, при конструировании линейных кодов целесообразно рассматривать ансамбль кодовых векторов, вычленяя «плохие» кодовые комбинации. Подобная задача формулировалась в [4]. В ней оценивалась вероятность ошибки по ансамблю кодовых векторов с выбрасыванием тех, для которых М = N. Однако широкое применение и развитие данная концепция получила в работах Э. Арикана [1]. Целью применения ПК является создание такой решающей схемы, при котором z(p)-> о, тем самым вероятность ошибочного приема также стремится к нулю, как было сказано ранее. Концепция формирования ПК построена на базе ядра Арикана. Ядром Арикана называют матрицу F = а через величину с обозначают ее m-ую кронекеровскую степень, в основе которой лежит кронекеровское ( прямое) произведение матриц [1]. Для получения требуемого выходного вектора необходимо произвести преобразование последовательности таким образом, чтобы номер новой позиции 7-го элемента получился как обратная запись числа 7, то есть полярное представление. Например, 1 = (0 0 0 1) -> (1 0 0 0) = 8 [2]. Таким образом, для получения соответствующей матрицы необходимо ввести матрицу перестановок В Результирующая матрица G®m определяется следующим выражением: N (6) Для осуществления операции поляризации необходимо произвести трансформацию скалярного канала в векторный канал, отождествляя его с функцией плотности условной вероятности выходного символа [2]. Это достигается за счет создания копий ДСК рекурсивным способом, как представлено на рис. 1. Рекурсия начинается с 0-го уровня (п = 0) посредством применения только одного экземпляра Р, и ему ставится в соответствие Р\ = р. На первом уровне рекурсии схема сочетает в себе две независимых копии Р1, тем самым мы получаем канал Р2 с вероятностью переходов Р(Уі\иі ®и2)-р{У2\иг)- Схема построения такой системы кратна степени 2 начиная с нуля. На рис. 1 матрица перестановок BN имеет входы (/j, 12, 1Ъ,... lN1 ). Рис. 1. Рекурсивный способ формирования кодового вектора Общая форма рекурсивной зависимости равна PN (рГ )= pN (рГ \U1 Gn )• Стоит отметить, что процесс формирования матрицы перестановок BN удовлетворяет следующим соотношениям (для случая, когда m = 2): А) so > h ’2 ’ и Очевидно, что связи между входами и выходами формируются исходя из правила: входы ранжируются по четным и нечетным номерам (зависит от нулевой точки - нумерация с нуля или единицы), им ставятся в соответствие выходы, нумерация которых осуществляется строго по порядку с нулевой точки. Матрица G®т, как отмечалось ранее, получается посредством прямого произведения матриц F. Длина блока N определяется кронекеровской степенью т->N = 2m . То есть при m = 1 матрица G равна ядру Арикана, при m = 2 и m = 3 имеем Gm и G®3 соответственно. При N ->оо каналы PtN будут либо полностью бесшумные, либо полностью ненадежные. В связи с этим информационные символы ui, передаваемые по каналам с низким уровнем достоверности, можно считать всегда фиксированными («замороженными»). Рассмотрим принцип фиксации каналов на основе матрицы G ®3. Строкам матрицы G®3 с весом ®з «Инфокоммуникационные технологии» Том 12, № 3, 2014 Гладких А. А., Чилихин Н.Ю. 13 w<4 поставим в соответствие каналы с фиксированными значениями равными нулю на основе правила Рида-Маллера, как представлено на рис. 2. Необходимо обратить внимание, что модифицированная матрица G^ степени т = 3, образуется из строк матрицы G80 с весом w > 4. Таким образом, мы переходим из пространства 2M в пространство M, поставив данным каналам в соответствие нулевое значение (коды с выбрасыванием). Рис. 2. Принцип фиксации зашумленных каналов Это позволяет уменьшить вероятность ошибки для систем передачи данных. Однако стоит отметить, что для корректной оценки кодового вектора, как отмечалось ранее, целесообразно использовать границу Бхаттачария. Ранговый вектор Zn-\ {ZN_10 , ZN_X^ ZN_XN_X ) определяется через рекурсивное соотношение по четным и нечетным каналам [5-6]: ZN-1 “• 2 Z N-1J - Z N-\,j Z2 (7) Для матрицы G ранговый вектор равен ZN_X = (0,996; 0,88; 0,81; 0,32; 0,68; 0,191; 0,121; 0,004). При сопоставлении двух векторов XN и ZN (первый представлен на рис. 2.) можно заметить, что высказанная теория об оценки канала связи посредством параметра Бхаттачария дает идентичные результаты по отношению к правилу Ри-да-Маллера. Данное сопоставление представлено в таблице 1. Из таблицы 1 видно, что «замороженным» каналам ставится в соответствие параметр Бхат-тачария Z{P)->1. Как отмечалось ранее, при Z- \ мы получим полностью зашумленные каналы, передача по которым нецелесообразна. В связи с этим данные, полученные из источника сообщений, передаются через каналы с номерами Л* (3, 5-7). Введем множество А , элементы которого полностью идентичны номерам каналов связи и равны А* = {О, 1, iV-l}. При применении правила Рида-Маллера или оценки по параметру Бхаттачария множество А* распадается на два подмножества А и А^, где А - множество номеров «незамороженных» каналов связи, а Af -множество «замороженных» каналов. Матрица G®3 также распадается на две под- G®3 ®3 /л ®3 . и/ и Gfrozen , Gnf - матрица, строки которой имеют вес w>4, а G®3zen - матрица, где W < 4. Общий вид выражения для получения выходного вектора XN_x определяется следующим соотношением: XN_x=uA-G*?®uAf у-т®т frozen (8) где иА - символы, соответствующие «незамороженным» каналам связи, a uAf - «замороженным». Пропускная способность канала со стираниями Применение мягких методов обработки принятых данных позволяет добиться дополнительного энергетического выигрыша, а применение ПК является новым развитием системы комбинации кодовых методов обработки информации. В [7] было показано, что пропускная способность ДСК определяется соотношением С, где Є - вероятность ошибки на бит. В случае применения двоичного стирающего канала связи (ДСКС) про- Таблица 1. Сопоставление векторов XN_x и ZN_j XN-, 0 0 0 иъ 0 Щ и6 щ Zff-i 0,996 0,88 0,81 0,32 0,68 0,19 0,12 0,004 «Инфокоммуникационные технологии» Том 12, № 3, 2014 14 Гладких А.А., Чилихин Н.Ю. пускная способность равна с, где q - вероятность стирания, а p - вероятность ошибки нестертого символа. Очевидно, что Сдск< Сдскс , причем равенство достигается при р,Е -> 0 . Обозначим через Сщ пропускную способность канала связи при мягких методах (МД) обработки символов, тогда Сдск< Ст< Сдскс. В случае формирования индексов мягких решений (ИМР) на основе стирающего канала связи значения сщ при разных интервалах стирания у могут быть представлены кривыми на рис. 3. Рис. 3. Зависимость пропускной способности от ширины интервала стирания при разных отношениях «сигнал/шум» Величина h = 101og(iiÄ /N0) определяется в дБ, где Еь - энергия сигнала на бит, а N0 - спектральная мощность белого гауссовского шума. Под ИМР понимается мягкая оценка жесткого решения, вырабатываемая демодулятором. Как показано в [3], подобная оценка в целочисленном формате без знания статистических характеристик канала связи определяется следующим соотношением: L(u{ I z) = L (и. I z ) max \ i I / r мл z, (8) где Ммп - математическое ожидание модулируемого параметра. Подобный подход полезен в условиях быстрого переключения в процессе передачи с одного канала на другой. Доказано, что пропускная способность ДСК может достигать значения 1 за счет применения схемы полярного кодирования, а применение мягких методов обработки символов способствует более быстрому достижению этого предела [1; 8]. В процедуре декодирования ПК была установлена целесообразность применения целочисленных ИМР [2], а их применение способствует уменьшению вероятности ошибки в последовательном декодере Арикана. Подобные оценки могут быть сформированы в стирающем канале связи без знания статистических характеристик этого канала [3]. Последовательный декодер Арикана В основе построения последовательного декодера Арикана лежит подсчет логарифмического отношения правдоподобия (ЛОП) с учетом оценок предыдущих символов. При поступлении кодового вектора декодер производит оценку и принимает решение на основании алгоритма, указанного ниже. Для каждого і - 0, 1,......N - 1. Если є , тогда ut = 0. Иначе вычислим оценку - = 10, если \и10х)> 0 ; 1, в противном случае. Стоит отметить, что декодер принимает жесткое решение, что приводит к возникновению лавинообразного распространения ошибок в случае появления таковых на более ранних шагах декодирования. Последовательный декодер Арикана производит вычисление и выносит решение путем сравнения с пороговым значением, которое равно нулю. Вычисление осуществляется по формуле: >(0 JV-1 ,.N-2 |0) рР(уГ,<-‘ И) ff-1 ..ff-2 (9) В данной работе предложено, что декодер производит не просто вычисление N-1 . JV-1 ) для оценки символа по отношению к пороговому значению, а дополнительно для каждого бита сообщения производит вычисление ИМР с целью оценки надежности. В большинстве аналитических оценок эффективности процедуры мягкого декодирования помехоустойчивых кодов в качестве ИМР символов принимается значение ЛОП. Этот параметр для двоичных систем модуляции определяется как: L(ut I z)- ln P{ui = +11 z) P{ui = -11 z) (10) где ui = +1 - возможные значения переданного бита; z - принятый уровень сигнала. Для одного принятого символа z;. = ±1 , а значение ЛОП для канала с независимым потоком ошибок в усло- «Инфокоммуникационные технологии» Том 12, № 3, 2014 Гладких А. А., Чилихин Н.Ю. 15 виях применения двоичной фазовой модуляции определятся выражением [9]: L(u, \zt) = ln p(ut I z, = +l) P(Ui I zt =-l)_ 2 4Ë~bZt (11) где <г - дисперсия шума. В случае применения каналов с общими замираниями и коэффициентом затухания к выражение для ЛОП принимает вид т ( , ^ 2 *jEb zt L{ut I zt) =---xtc;. (12) o\ В выражении (10) отсутствует параметр а2 . Проведенными статистическими испытаниями показано, что знание параметра с2 необходимо при больших отношениях «сигнал/шум», а при малых отношениях «сигнал/шум» ИМР [10] определяется с некоторой погрешностью, характер которой выявлен с помощью метода по соотношению *1 1 2> ^ (я,(;)+я2(;)) где H,(i) - 7-ый интервал гистограммы, определенный методом логарифмического отношения правдоподобия, а Н2(і) - интервал гистограммы, вычисленный по методу стирающего канала связи. В результате сравнения указанных гистограмм были получены результаты, приведенные на рис. 4. Рис. 4. Зависимость яг2 от соотношения «сигнал/шум» При реализации подобного решения необходимо учитывать тот факт, что при получении ИМР для каждого бита сообщения значения ряда из них будут находиться в зоне неопределенности, что будет служить сигналом для декодера о низкой степени достоверности. Таким образом, необходимо дополнительно реализовать блок буферизации, в котором будут храниться номер позиции символа и номер шага декодирования. Подобный подход увеличивает список декодирования, однако позволяет уменьшить вероятность ошибки при последовательной обработке входного вектора. Будем считать, что на длине кодовой комбинации канал является локально стационарным, тогда вероятность резкого увеличения количества списков сравнительно мала. Вычисление исходного кодового вектора по разным спискам приводит к получению ряда кодовых конструкций, выбор из которых осуществляется по принципу максимального правдоподобия. на основе графа Декодирование Таннера Построение двудольного графа Таннера для последовательности N = 8 позволяет установить связи между исходными символами кодовой последовательности и символами выходного вектора после преобразования через матрицу G. Данная зависимость представлена на рис. 5. Подобный подход не имеет такого недостатка, как лавинообразное распространение ошибок, в силу наличия проверочных уравнений. Кроме того, применения ИМР также снижает вероятность ошибки декодирования. і t/Ji - О J1 In Jl 2 lÿ Рис. 5. Связи векторов UN_j и XN_3 Запишем уравнения связи: х0 = их 0 и2 © и3 © и0 ; хх = и3 ® и5 ® Mj ; х2 = и3 'и6 ®м2; х3 = н7 @и3; х4 = и5 © и6 0 и4 ; х5 = и7 0 и5 ; х6 =и7 0«6; х7 =м7. Для осуществления декодирования необходимо произвести процедуру, представленную на рис. 6. Применение процедуры списочного «Инфокоммуникационные технологии» Том 12, № 3, 2014 16 Гладких А.А., Чилихин Н.Ю. декодирования позволяет использовать метод разбиения пространства кодовых комбинаций на кластеры [3]. Поскольку номера кластера могут определяться любой позицией кодовой комбинации, целесообразно в последующем ограничивать список кодовых комбинаций группой комбинаций кластера. Разбиение на кластеры обеспечивает повышение скорости процедуры декодирования. из Хт = U-7, 1 'е ^ а = {3,5,6,7} ■'... u« О = Uj © u 2 © u3 © х0 0 = Uj©u,@x1 д.,(„д,2,4} О = u3 © ис © х 2 О = ©u6@x4 U0 = U1 = U2 = U4 = 0 Рис. 6. Декодирование на основе графа Таннера Заключение Применение принципа выбрасывания «плохих» кодовых векторов позволяет сформировать ансамбль сигналов из наиболее разнесенных кодовых последовательностей. Использование границы Бхаттачария обеспечивает возможность получить оценку кодового ансамбля до процесса передачи закодированного сообщения, что подчеркивает целесообразность его применения в рамках поставленной задачи. Универсальность метода формирования целочисленных ИМР обеспечивает снижение вероятности ошибки в декодере Арикана за счет сопровождения каждого принятого символа соответствующим мягким решением. Это позволяет декодеру целенаправленно выполнять процедуру рекурсии с меньшим риском размножения ошибок. Расширение списка декодирования в классической процедуре декодирования по Арикану увели чивает вычислительные затраты декодера, а также требует дополнительной оперативной памяти и, как следствие, повышение сложности процессора декодера. Применение кластерного подхода позволяет повысить скорость составления списка, ограничив его степенью двойки, зависящей от числа битов, входящих в номер кластера.

About the authors

A. A Gladkikh

Email: a.gladkikh@ulstu.ru

N. Y Chilikhin

Email: n.chilikhin@gmail.com

References

Supplementary files