Практические аспекты алгоритма Тала-Варди списочного декодирования полярных кодов

СПИСОК Л

1. Додохов А.Л. Исследование применения СУБД Oracle для защиты персональных данных [Текст] / А.Л. Додохов, А.Г. Сабанов // Доклады Томского гос. ун-та систем управления и радиоэлектроники. -2011. -№ 2 (24). -С. 267-270.

2. Федеральный закон от 27 июля 2006 г. № 152-ФЗ «О персональных данных» (в ред. от 25 июля 2011 г).

3. Нормативно-методический документ ФСБ России «Методические рекомендации по обеспечению с помощью криптосредств безопасности персональных данных при их обработке в информационных системах персональных данных с использованием средств автоматизации» от 21 февраля 2008 г.

УДК 519.725.2

П.К. Семенов

ПРАКТИЧЕСКИЕ АСПЕКТЫ АЛГОРИТМА ТАЛА-ВАРДИ СПИСОЧНОГО ДЕКОДИРОВАНИЯ ПОЛЯРНЫХ КОДОВ

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

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

1) появляется зависимость по данным при обработке разных элементов списка в алгоритме Тала-Варди, хотя теоретически они могут быть обработаны независимо, параллельно;

2) становится невозможным получение хотя

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

Обе эти проблемы разрешаются переходом в логарифмическую область, однако хорошо известный для полярных кодов способ вычислений с большой точностью, основанный на логарифмических отношениях правдоподобия (ЛОПП), не применим в силу специфики алгоритма Тала-Варди. Решение этой задачи представляет существенный интерес в силу востребованости эффективной аппаратной реализации (см. [3, 4]).

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

Назовем ядром Арикана матрицу G =

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

„ 1 о)

а через ОХ5 обозначим 5-ю кронекеровскую степень - матрицу размера 2**2*. Пусть Вг - это 25*25-матрица такой перестановки для вектора длины 25, что номер новой позиции /-го элемента получается как обратная запись представленного в виде 5-битной последовательности числа /. Например, 2 = (1 0 0) (0 0 1) = 1, 3 = (0 1 1) ^ (1 1 0) = 6. Обозначим ска-

Рис. 1. Векторный канал Жы

лярный канал со входом и и выходом у как Ж(у|и), отождествляя его с функцией плотности условной вероятности выходного символа. В случае передачи последовательности данных иЦ-1 = (и0 и1 ... иИ-1) размера N через канал Ж(у\и) будем рассматривать эквивалентный векторный канал Жн (у0

УoN-1

1)=п :>

с выходом Уо^1 =(Уо У1 ... УN-1) (рис. 1).

В статье [1] предложен метод поляризации двоичного симметричного канала Жы (у01-1 | и^-1) без памяти с двоичным входом, где N = 2", при передаче через него преобразованного блока Метод заключается в пред-WN ( у5-1 I и5-1) как совокупности

N-1 л г^ "

данных и0 Вы О .

ставлении Жы (у^ -1 „ _

Ж = Ж) (уN-1, и0-1 I иг ),0 < г < N} двоичных каналов (рис. 2), обладающей следующими свойствами.

1. Эквивалентность Ж и Ж : суммарная про-

N-1

пускная способность V С (Ж!)) равна С(Ж) при

условии, что для каждого Ж^)(у0 -1, и0-1 | иг) известны точные значения информационных символов и0-1 (на рис. 2 это условие обозначено прерывистой линией).

2. Асимптотическая поляризация каналов из Ж : при N ^ да относительная доля Ж^) в Ж таких, что С Ж)) ^ 1, стремится к С(Ж), а пропускная способность остальных N(1 - С(Ж)) каналов стремится к нулю.

Поляризационный эффект достигается применением невырожденного преобразования ВмОк данным. Таким образом, поляризующее преобразование канала Ж2N(у^N-11 и™-1) основано на поляризации векторных каналов меньшей г_, . г-1- N N

размерности Ж1 (у0-

В [1] показано, что эта декомпозиция для

1), 1 = N, -, -, ..., 1.

-(г л-1 иг-1

плотностей ЖЦ)(у0 ражается как

Ж№( У02Д'-1,

| щ) вероятностей вы-

и021 -1 \ и2г

) =

= 2 VП)

-(г)/л,2 N-1 ,21-1

Ж()(, у

10,о

\ и2 г+1);

+1)

-(1)^.2 N-1 .21-1

Ж(\у

и9,+1);

Ж0(0)(у | и) = Ж(у | и),

где и21 1 и и21 1

'Л0,е '1-1

0,о

обозначают компоненты векто-

ра и0 только с четными и нечетными номерами соответственно. Вероятности передаваемых битов в каналах Ж()(у^ -1, и0-1 | щ) оцениваются через рекуррентные формулы (1), (2) с условиями выхода из рекурсии (3).

При N ^ да канал Ж^ будет либо абсолютно без шума, либо абсолютно ненадежным. Поэтому информационные символы и , передаваемые по каналам плохого качества, можно считать всегда фиксированными («замороженными»). И если сопоставить 1-ю строку матрицы О " каналу Ж<()(у^-1, и0-1 | щ ), то г наиболее надежным каналам из Ж соответствует линейный (2", г)-код длины 2" и размерности г, называемый полярным кодом. Таким образом, чтобы задать полярный

код порядка достаточно указать множество А

а "

.

<0)

•т

'

уГ

уГ

уГ

1

У

Л7-1

V-9

Рис. 2. Подканалы Ж^ -) достоверная передача через канал

х

-п

(

Списочный декодер Тала-Варди

Идея традиционного декодера [1] для полярных кодов заключается в последовательной оценке значений передаваемых битов по подканалам )(у^-1, <-1 | и.). При этом для (/+1)-го канала в качестве достоверных битов и0 используются оценки входов подканалов всех предшествующих номеров. Таким образом, если на какой-то стадии происходит ошибка, то и оценка всех оставшихся битов будет ошибочной. Алгоритм Тала-Варди позволяет исправить эту ситуацию. На рис. 3 представлено идеальное дерево всех различных вариантов значений передаваемых битов и. для полярного (4,3)-кода с множеством «замороженных» битов А = {0}. Количество ветвей в таком дереве равно 2Г, где г - размерность кода. Пусть I - желаемый размер списка наиболее правдоподобных ветвей этого дерева. Правило выбора I наиболее надежных ветвей при оценке бита и. соответствует выбору таких ветвей, отвечающих наиболее вероятным оценкам и. - рис. 4.

Вычисления в логарифмической области

Для реализации правила выбора на /-й ста-

U<

ил

и,

и.

/ \ : i * г

0 1 о

Су1-)

Рис. 4. Выбор только двух ветвей (непрерывная линия) на каждой стадии для полярного кода длины 4 и размерности 3

U,

U,

и.

и.

/

Г 1 Г 1 Г

О 1

1 о 1 0 1

Рис. 3. Идеальное дерево вариантов для полярного (4,3)-кода

дии декодировании необходимо иметь значения вероятностей обоих случайных событий: «передавался 0» и «передавалась 1». Таким образом, переход к хорошо известной для полярных кодов области логарифмических отношений правдоподобия (ЛОПП) невозможен. В связи с этим для реализации формулы (1) в логарифмической области требуется решение следующей задачи: имея log(a) = logЖЦ)(y0w-1,м2^ 0 и2,';1 11) и log(b) = log WtN) (y0 1, uf;1 1t) для t = 0,1, вычислить log w^'Cy2"-1, u2i-11M2,.) = log—(цА + ab) =

log

2

Не огра-

будем считать, что ^(а0) + log(b0) > log(al) + . Тогда иско-

мое выражение можно представить как 1о^— +

= log — )+log(b0) + е ничивая общности

+ log(a0) + ^(60) + log(1 + е^^^ъ^Ы) в случае, когда ^Ц) + log(bl) - ^(а0) - tog(b0) мало (например, меньше q = -70), то log(1 + е^ё(а1)+1оё(Ь1)-1оё(а0)-1оё(Ь0)^0.в итоге аппроксимация для формулы (1) представляется в следующем виде:

log )(у0" ', Щ

log ^ + ^(ао) + ), с < ^ 2 + ^^) + ^(¿0) + 1ов(1 + е),-д < с < д,

log 2 + ) + ), с > д

где с = ^(а) + ) - log(aо) - ).

Реализация формулы (2) проводится аналогично. Как было показано в [3], для традиционного декодера полярных кодов, работающего с ЛОПП, достаточно обеспечить 4-6 битов на дробную часть при использовании чисел с фиксированной запятой. На рис. 5 а, б представлены

а)

графики вероятности ошибки декодирования в зависимости от отношения сигнал/шум (в дБ) для полярных (256,37)- и (256,163)-кодов. Видно, что чем длиннее список, тем менее важна точность вычислений: так, для длины списка I = 8 вероятность ошибки декодирования для вычислений с плавающей запятой и для целочисленных вычис-

б)

Рис. 5. Вероятность ошибки декодирования: а - для

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

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

СПИСОК Л

1. Arikan, E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels [Text] / E. Arikan // IEEE Trans. on Inf. Th. -2009. -№ 7 (55). -P. 3051-3073.

2. Tal, I. List decoding of polar codes [Text] / I. Tal, A. Vardy // In proc. of the IEEE Int. Symp. on Inf. Th. (ISIT). - 2011. - P. 1-5.

3. Leroux, C. Hardware Implementation of Succes-

предоставляет возможность эффективной аппаратной реализации на платформах с целочисленной арифметикой.

Работа выполнена в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса РФ на 2007-2013 гг.» при финансовой поддержке Министерства образования и науки РФ, госконтракт 07.514.11.4101.

sive Cancellation Decoders for Polar Codes [Электронный ресурс] / C. Leroux, A. Raymond, G. Sarkis [et al.] // Submitted to J. Signal Process. Syst. -2011. -Режим доступа: http://arxiv.org/pdf/1111.4362.pdf

Leroux, C. Hardware Architectures for Successive Cancellation Decoding of Polar Codes [Text] / C. Leroux, I. Tal, A. Vardy [et al.] // In proc. of the IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP). -2011. -P. 1665-1668.