Программная реализация декодера Судана для кодов Рида-Соломона

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ИНЖЕНЕРНЫЙ ВЕСТНИК ДОНА, № 2, 2007, стр. 95−102
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ДЕКОДЕРА СУДАНА ДЛЯ
КОДОВ РИДА-СОЛОМОНА
© 2007 г. Н.В. Ремизов
В настоящее время для повышения надежности передачи информации широко используются помехоустойчивые коды Рида-Соломона. Дальнейшее развитие этого направления привело к разработке списочного декодирования, основанного на работах Судана [1].
Целью данной работы является исследование возможности программной реализации декодера Судана для кодов Рида-Соломона и численный анализ полученных результатов.
Пусть GF (q) — поле Галуа, (а0,…, ап-1) — фиксированный набор различных элементов из GF (q), q — мощность поля, п & lt- q — 1. Будем называть его опорным множеством. Процесс кодирования заключается в следующем: на вход подается к-мерный вектор f = (fo, …, fk-1), f GF (q), далее происходит вычисление полинома p (x) — fo + fix + … + fk-iXk-i в точках ai, i — 0… п-1. На выходе получаем n-мерный вектор u-(p (a0), …, p (an. 1)).
Линейный Код Рида-Соломона является МДР-кодом, то есть достигает границы Синглтона d — п — k + 1, где d — минимальное кодовое расстояние. Поп _ k
этому код способен исправлять t =
ошибок.
2
Пусть С — кодирующее отображение, С: ^ ^ Г& quot-. Разобьем пространство на сферы с центрами в кодовых словах радиуса ґ. Эти сферы, очевидно, не
пересекаются. Обычный декодер анализирует пришедшее по каналу слово у и находит тот центр сферы радиуса ґ, в которую попало данное слово. И выдает соответствующее кодовое слово.
1. Списочный декодер Гурусвами-Судана.
Теоретические основы списочного С8-декодера
Будем следовать описанию списочного декодера, приведенного в [1]. Рассмотрим последовательные шаги алгоритма. Пусть ^ - поле Галуа, С: ^ Г& quot- - кодирующее отображение, (а0, …, ап. 1) — опорное множество кода
Рида-Соломона, у = (у0, уі, …, уп-і) — пришедшее по каналу слово.
Шаг 1. Строится полином от двух переменных Q (x, у) степени Б по переменной х и степени Ь по переменной у, удовлетворяющий следующим условиям:
— Q (ai, уі) = 0, і = 0 … п — 1.
— Q (x, у) ф 0.
Шаг 2. Находятся все делители полинома Q (x, у) вида
у — р (х), deg р (х)& lt- к, причем р (а) = у1 по крайней мере для п — ґ значений і =
0 … п — 1.
п
Параметры Ь и Х в [1] определяются следующим образом: Ь = Лк & gt-
Х = 4пк.
1.1. Интерполяция
В работе [1] М. Судан предлагает такой способ построения многочлена.
Представим полином Q (х, у) = ^а^х1 у] в виде:
і, і
^ х у) = Х к^к (х) ук =
= (Ч00 + 401х + … + 40 ох°) + (4ю + 411х + … + 4хвх°) у + - + (4ю + 4пх + - + 4 ХХ) У1
Подставляя вместо переменной х элементы опорного множества, а вместо переменной у — компоненты пришедшего по каналу слова, получаем однородную систему линейных алгебраических уравнений относительно 4іі.
4000 + 40101& quot-. + 40 ХZЪХ + 4100 + ^1111 + …
+ 41Х^1Х + … + 4ь 0 2Ь0 + Чы 2ы + … + 4ьх2ьх = 0
4000 + 4011 … + 40Х20Х + 4100 + 41111 + …
+ 41Х^1Х + … + 4Ь0 2ю + 4ы гы + … + 4югьХ = 0, где z, kJ = агкук, 0 & lt- к & lt- п — 1, 0 & lt- і & lt- Х, 0 & lt-і & lt- Ь.
Ненулевое решение существует, т.к. количество неизвестных, больше, чем количество уравнений. (Степень многочлена Q (x, у) по переменной х должна не
больше, чем П, и по переменной у — не больше, чем Ь, тогда количество неиз-
Ь
вестных (L +1)(
n
L
+1) & gt- n). Это один из вариантов. В работе [2] МакЭлиас
приводит альтернативный алгоритм решения проблемы интерполяции — алгоритм Кюттера. Приоритетом при выборе играет время — если метод Гаусса тре-
3 3 2 2
бует О (п) (порядка п) операций, то алгоритм Кюттера — О (п) (порядка п) операций.
1.2. Факторизация. Алгоритм Рота-Рукенштейна
Пусть ^ - поле, может быть, конечное, ^[х, у] - кольцо многочленов от 2-х переменных над полем Б. Каждый элемент Q (x, у) Г[х, у] можно представить в виде суммы
Q (x, y) = Х avxlyJ
] у]
i,]
где не все а] равны 0.
Определение. Пусть w = (u, v), u & gt- 0, v & gt- 0, u + v Ф 0. Взвешенной степенью монома Xy называется число degw xiy = iu + ]v.
Обозначим через XY = {xiy, i = 0, 1… n …, j =0, 1. .n…}. Используя понятие взвешенной степени, введем на множестве XY отношения порядка «& lt-wlex» и
(.с. ^
& lt-wrevlex.
Определение. Будем говорить, что мономы упорядочены согласно отношению w-lex (w-lexicographic order), если
xl1 y] & lt- xi2 y] ,
если ui1 + v]1 & lt- ui2 + v]2, или ui1 + v]1 = ui2 + v]2 и i1 & lt- i2.
Определение. Будем говорить, что мономы упорядочены согласно отношению w-revlex (w-reverse lexicographic order), т. е.
xi1 y]1 & lt- xi2 y]2,
если ui1 + vj & lt- ui2 + vj2, или ui1 + vj = ui2 + vj2 и i1 & gt- i
2 •
Пусть w = (u, v), «& lt- «- некоторое отношение порядка («& lt-wlex» или «& lt-wrevlex») на множестве XY. Следовательно, можно упорядочить элементы множества:
Const = фо^, у) & lt- ф^, у) & lt- ф2(т, у) & lt-. ,
где ф^, у) = xiyj XY.
Тогда каждый полином Q (x, y) можно записать в уникальной форме:
j
Q (x, y)=Еа]ф](x, y)
] =0
Число J называется рангом полинома Q (x, y), Rank (Q) = J. Моном ф/x, y) называется ведущим мономом и обозначается LM (Q).
Замечание. Рассмотрим F[x, y] - кольцо многочленов от двух переменных надо полем F. P, Q F[x, y]. Если LM (P)=LM (Q), то говорят, что P = Q.
Определение. Взвешенной степенью полинома Q (x, y) называется число
degwQ = max^deg,^^, y) | ai ф 0}.
Свойства взвешенной степени: w = (u, v),
1. degw0 = - да-
2. degw (PQ) = degwP + degwQ-
3. degw (P + Q) & lt- max (degwP, degwQ).
Напомним, на втором шаге GS-декодера необходимо найти все делители полинома Q (x, y) F[x, y] вида у — p (x), p (x) F[x], deg p (x) & lt- k-1.
Определение. Будем говорить, что полином Q (x, y) имеет ноль в точке (a, b), если
Q (a b) = 0.
Определение. Будем говорить, что полином Q (x, y) = ^ ai]xIyJ имеет ноль
i j
кратности, или порядка m в точке (0, 0), и писать
Ord (Q: 0, 0) = m, если в записи полинома все ai] = 0, i + ] & lt- m.
Теорема. Предположим, p (x) Fk-1[x], Q (x, y) F[x, y], w = (1, k-1)lex,
n = Xa ord (Q: a, p (a)). Если n & gt- degwQ, то (y — p (x)) | Q (x, y).
Лемма 1. Пусть w = (1, k-1). Если p (x) Fk-1[x], тогда
degQ (x, y) & lt- degwQ (x y).
Лемма 2. Q (x, p (x)) = 0 в том и только том случае, когда (y — p (x)) | Q (x, y).
Для удобства формулировок назовем p (x) y-корнем полинома Q (x, y).
Алгоритм Рота-Рукенштейна (РР-алгоритм) получает на вход полином от двух переменных Q (x, y) и выдает список y-корней этого полинома. Рассмотрим данный алгоритм подробнее.
Найдем такую наибольшую степень т переменной х так, что хт | Q (x, у), но хт+ / Q (x, у), и сократим. Получим полином
«0(Х, у)» =.
. х
Таким образом, если исходный полином Q (x, у) в точке (0,у) мог обращаться в 0, то & lt-^(0, у)» ф 0.
Покажем, процесс последовательного определения коэффициентов аг- полинома р (х).
р (х) = О) + агх + … + аыхы.
Лемма. Если (у — р (х)) | Q (x, у), тогда у = р (0) = а0 — решение уравнения:
Qo (x, у)=0,
где Qo (x, у) = «^х, у)».
Построим последовательность полиномов:
Р0(х) = р (х), Q0(x, у) = «Q (x, у)». ДляЦ & gt- 0 получаем:
Р](х) = (р]-(х) — р7ч (0))/х = а + а-+1х +. + ak. jxk. j- ,
Цх у) = Qj-l (x, ху + амХ (1)
Qj (x, у) = «Цх у)».
Теорема. Пусть дан полином р (х) = а0 + а1х + … + аk-1xk-1 ^ы[х], Q (x, у)
^[х, у]. Определим последовательности полиномов по формулам (1). Тогда VЦ & gt- 1 (у — р (х)) | Q (x, у) в том и только том случае, когда (у — р/х)) | Qj (x, у). Следствие. Если у | Qk (x, у), т. е. если Qk (x, 0) = 0, тогда р (х) = а0 + а1х + … + а^1х1 — у-корень полинома Q (x, у).
Алгоритм строит дерево коэффициентов. Каждый ярус дерева «символизирует» степень переменной х ((-1)-ярус введен для удобства). В вершинах /-го яруса находятся коэффициенты при степенях х1 возможных у-корней полинома Q (x, у). С помощью алгоритма «поиска в глубину» производится обход дерева.
2. Моделирование и численный анализ С8-декодера
Рассмотрим примеры работы декодера Судана. Пусть:
СДд) — поле Галуа, k — размерность кода- п — длина кода-
? — количество гарантировано исправляемых ошибок- х — информационный полином-
у — кодовое слово-
List — список _у-корней.
Так как мы будем работать над полями характеристики 2 (char (GF (g))=2), то для наглядности переводим двоичный формат в десятичный, т. е. все коэффициенты в приведенных ниже примерах следует рассматривать как двоичные числа в десятичной записи. (Пр.: f = (1, 3)10, что соответствует f=(001, 011)2.)
1. GF (23), k = 2, n = 5, t = 1-
f = (1, 3) —
x = (1, 2, 7, 4, 6) — список у-корней List: 1 3.
Вносим аддитивную ошибку:
1а. e = (0, 0, 2, 0, 0), тогда y = x + e, y = (1, 2, 5, 4, 6),
List: 1 3.
1б. e = (0, 0, 2, 0, 1), тогда y = x + e, y = (1, 2, 5, 4, 7)
List: пуст.
В 1а декодер выдал правильное кодовое слово, в 1 б — ошибок больше, чем может исправить декодер.
2. GF (23), k = 3, n = 5, t = 1-
f = (1, 3, 5) — x = (1, 7, 5, 3, 5) —
List: 1 3 5.
Вносим аддитивную ошибку
2а. e: = (0, 0, 0, 0, 5), тогда y = x +e, y = (1, 7, 5, 3, 5) —
f = (7, 7, 7) — x = (7, 7, 3, 3, 2) —
List: 7 7 7.
2б. e = (0, 0, 6, 0, 2), тогда у = x + e, y = (7, 7, 3, 5, 3, 0) —
List: 7 6 6.
Из чего можно сделать вывод, что декодер попал в сферу с центром в другом кодовом слове. Что вполне логично, так как количество исправляемых ошибок равно 1, а в данном примере их было внесено 2.
3. GF (25), k =8, n = 32, t =12- f = (29, 0, 2, 4, 6, 8, 10, 12) —
x = (29, 19, 23, 11, 9, 9, 5, 10, 3, 10, 1, 29, 23, 9, 11, 29, 4, 2, 22, 22, 5, 0, 18, 12, 22, 17, 14, 8, 1, 28, 4, 5) —
List: 29 0 2 4 6 8 10 12.
Вносим аддитивную ошибку:
3а. е = (20, 26, 30, 2, 0, 0, 12, 3, 10, 3, 8, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0), w (e) = 12, тогда y = x + e,
y = (9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 23, 9, 11, 29, 4, 2, 22, 22, 5, 0, 18, 12, 22, 17, 14, 8, 1, 28, 4, 5) —
List: 9 0 0 0 0 0 0 0 0-
29 0 2 4 6 8 10 12.
3б. е = (21, 27, 31, 3, 1, 1, 13, 2, 11, 2, 9, 21, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0), w (e) = 13- тогда y = x + e, y = (8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 11, 29, 4, 2, 22, 22, 5, 0, 18, 12,
22, 17, 14, 8, 1, 28, 4, 5) —
List: 8 0 0 0 0 0 0 0-
29 0 2 4 6 8 10 12.
3 В. е = (29, 0, 21, 0, 0, 0, 3, 0, 11, 0, 11, 0, 27, 0, 5, 0, 20, 0, 0, 0, 17, 0, 4, 0,
14, 0, 20, 0, 29, 0, 26, 0), w (e) = 14- тогда y = x + e-
y = (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 11, 29, 4, 2, 22,
22, 5, 0, 18, 12, 22, 17, 14, 8, 1, 28, 4, 5) —
List: 29 0 2 4 6 8 10 12.
3 г. e = (29, 0, 21, 0, 13, 0, 3, 0, 11, 0, 11, 0, 27, 0, 5, 0, 20, 0, 0, 0, 17, 0, 4,
0, 14, 0, 20, 0, 29, 0, 26, 0), w (e) = 15- тогда y = x + e-
y = (14, 19, 21, 11, 0, 9, 19, 10, 26, 10, 17, 29, 24, 9, 15, 29, 22, 2, 22, 22, 20, 0, 27, 12, 18, 17, 25, 8, 16, 28, 23, 5) —
List: пустой
Список пуст, декодер не выдал ни одного слова. Следовательно, можно заключить, что максимальное количество исправляемых ОБ-декодером ошибок для кода Рида-Соломона размерности 8 и длины 32 равно 14.
Заключение
Списочный декодер позволяет исправлять большее количество ошибок, составляя список, в котором обязательно присутствует истинное информационное слово. В случае большего числа ошибок, декодер выдает либо ошибочное кодовое слово, либо пустой список.
В результате проведенной работы был программно реализован списочный декодер Гурусвами-Судана, проведена численная проверка работы декодера. Как известно, обычный вероятностный декодер для кодов Рида-Соломона поп — к
зволяет исправлять t =
ошибок. Списочный GS-декодер исправляет
2
больше ошибок, в зависимости от размерности и длины кода.
Литература
1. Madhu Sudan, Lectures «Algorithmic Introduction to Coding Theory», 2001.
2. R.J. McEliece, The Guruswami-Sudan Decoding Algorithm for Reed-Solomon codes, May 15, 2003.
3. Лидл Р., Нидеррайер Г. Конечные поля, в 2-х т. / Пер. с англ. М.: Мир,
1988. — 430 с.
4. Берлекэмп Э. Алгебраическая теория кодирования / Пер. с англ. М.: Мир, 1971.

ПоказатьСвернуть
Заполнить форму текущей работой