<< Предыдущая

стр. 49
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


члены V(X) образуют (п, к)-код Рида - Соломона с порождающим
многочленом
2
д(Х) = {Х + а){Х + а ) • • • (X


Спектральный подход позволяет легко доказать следующую теоре-
му.

Теорема 5.3.3. Любой код Рида - Соломона является МДР кодом.
Доказательство. Так как код Рида - Соломона является линей-
ным, <imin равно минимальному весу кодового слова. Любое кодовое
слово V = (Vo, Vi,.. .Vj,.. •, Ki-i) является прямым преобразовани-
ем Фурье некоторого вектора


n-k

В силу теоремы 5.2.2, j'-ая частотная компонента равна нулю тогда
и только тогда, когда а? является корнем многочлена v(X) = VQ +
h Vfc-iX*-1. Согласно основной теореме алгебры, которая
v\X +
справедлива и для конечных полей Галуа, многочлен v(X) степени
А —1 может иметь в поле GF(q) не более А —1 корней. Следовательно,
; ;
вес любого слова (п, к)-код& Рида - Соломона не может быть меньше,
чем п—(к— 1) = п—к+1 и, в силу границы Синглтона d m j n = п—к+1,
то есть код обладает максимальным расстоянием. Так как коды Рида
- Соломона линейны, они являются МДР кодами. •

Спектральный подход позволяет также достаточно просто интер-
претировать процедуру декодирования кодов Рида - Соломона.


5.4. Декодирование кодов Рида - Соломона
Не трудно заметить, что при образовании кодов Рида - Соломона
информационные символы можно размещать в любых к рядом стоя-
щих разрядах вектора v. Из методических соображений отведем под
информацию старшие компоненты V. В этом случае многочлен v(X)
будет иметь, вид

v(X) = Vn-iXn-l+vn-2Xn˜2+- • •+vn^kX"-k+0-Xn-k˜1+- • -+0-Х0,
а порождающий многочлен соответствующего крда Рида - Соломона
имеет вид

д{Х) = (Х + ак+1)(Х + ак+2) • • • (X + а").
Глава 5. Дискретные преобразования Фурье и коды PC

Как уже отмечалось ранее, слова рассматриваемого кода Рида Со-
ломона являются прямым преобразованием Фурье множества век-
торов V, то есть v т± V. В канале кодовому слову V добавляется
вектор ошибки Е кратности I < d — \.
Рассмотрим обратное преобразование Фурье принятого из канала
слова
R = V + Е, (5.8)

В силу свойства линейности обратного преобразования Фурье имеем

(« n _i +e n _i,...,w n _fc + en_fc,en_fc_i,en_ifc_2,...,eo) ^ V + Е, (5.9)

где v = (vn-k,vn-k-\, • • • ,vn-\) - информационный вектор, лежащий
во временной области, е = (eo,ei,... ,e n _i) - обратное преобразова-
ние вектора ошибок. Так как п — к правых компонент вектора обрат-
ного преобразования Фурье от V + E не зависят от кодового слова V,
эти компоненты образуют синдром ошибок. Запишем этот синдром
в виде
S d - 2 , S d - l , - - . ,Si,S0, (5.10)

где so = eo,Si = e i , . . . ,Sd-2 = en_fc_i. Заметим, что Синдром явля-
ется некоторым «окном», через которое можно наблюдать обратное
преоразование Фурье вектора ошибки Е.
Обозначим индексы I ненулевых компонент вектора Е через
JitJ2, • • • ,ji- Определим вектор во временной области, прямое преоб-
разование Фурье которого содержит нулевые компоненты для всех
частот j, для которых Ej ф 0. Проще всего такой вектор задать в
виде многочлена локаторов ошибок


... + atXl. (5.11)


Покомпонентное произведение прямого преобразования Фурье от
многочлена сг(Х) на вектор ошибки Е в частотной области рав-
но нулю, следовательно циклическая свертка во временной области
вектора а с векторм е также равна нулю '

<г*е = О. (5.12)

Из (5.9) и (5.10) следует, что для определения компонент (Ti,<T2, • • • ,<ri
5.4- Декодирование кодов Рида Соломона


(согласно (5.11) <т0 = 1), используя (5.12), мы можем составить си-
стему d — 1 — I линейных уравнений с 2 неизвестными
<TiS;_i + . . . + ffiso = О
=0
(5.13)
= 0.
-2-l

Сложность, возникающая при решении системы уравнений (5.13) со-
стоит в том, что кратность ошибки I нам заранее не известна. Таким
образом, в процессе решения должна еще осуществляться и миними-
зация значения /, при котором возможно выполнение всех d — 1 — /
уравнений из (5.13). Такой простой и эффективный алгоритм был
найден Берлекэмиом в 1967 г. Без преувеличения молено сказать, что
этот алгоритм произвел настоящую революцию в теории и практике
помехоустойчивого кодирования. Он будет рассмотрен в следующем
разделе этой главы.
Предположим, что все коэффициенты многочлена а{Х) опреде-
лены. В этом случае остальные к компонент вектора е, то есть ком-
поненты еп-к, e n _fc+i,..., e n _i во временной области, могут быть ре-
курентно определены, исходя из (5.12).
Для определения компоненты e^-i нам достаточно решить урав-
нение
_i_j =0
d



относительно e^-i, так как все остальные компоненты уже опреде-
лены.
На'втором шаге мы уже можем составить уравнение для опреде-
ления efc_2- Это уравнение имеет вид
a o e n _ f c + i + О\еп-к = 0.
+ <?2Sd-2 + ••• + <?iSd-l

Рекурентно продолжая описанную процедуру, мы найдем все остав-
шихся компоненты вектора е.
Для определения информационного вектора v нам достаточ-
но вычесть найденные компоненты en_fc,en_fc+i,... ,e n _i из полу-
ченных обратным преобразованием Фурье от R значений vn-k +
en-k,vn-k+i +e n _fc+i,... ,vn-i + e n _ i .
Самое замечательное в рассмотренном алгоритме состоит в том,
что при его реализации не приходится находить ни корни многочлена
а(Х) (локаторы ошибок), ни значения ошибок.
Теперь общая картина процедуры декодирования ясна и ее можно
сформулировать в виде пяти шагов.
i 278 Глава 5. Дискретные преобразования Фурье и коды PC

Шаг 1. Вычислить обратное преобразование Фурье принятого век-
тора R = V + Е. Выделить SQ, . . . , s^-2 во временной области
и зангумлениые компоненты информационного вектора v;

Шаг 2. Найти а(Х) из (5.13);

Шаг 3. С помощью рекурентной процедуры вычислить компонен-
ты e n _ f c ,e n _fc + b ..., e n _i;

Шаг 4. Найти информационный вектор v;

Замечание. Рассмотренный алгоритм всегда исправляет \^jr\ u
менее ошибок. В следующем разделе будет рассмотрен также слу-
чай, когда число канальных ошибок превышает L^pJ •
Для контроля правильности декодирования часто проводится
следующий шаг.

Шаг 5. Вычислить прямое преобразование Фурье вектора v, полу-
чив при этом кодовай вектор V (не всегда совнадаяющий с V).



5.5. Итеративный алгоритм для нахождения а(Х)

Будем руководствоваться блок-схемой алгоритма, приведенной на
рис. 5.1 ([10] стр. 271). Отметим, что эта блок-схема содержит всю
необходимую информацию для программной или схемной реализа-
ции алгоритма. Если число ошибок не превышает величины [^pj> т 0
алгоритм находит многочлен о˜(Х) минимальной степени I, при ко-
тором выполняется система уравнений (5.13). Доказательству этого
факта в [10] посвящено несколько довольно сложных теорем и заин-
тересованному читателю мы советуем обратится к [10]. Ограничимся
описанием основных принципов работы алгоритма.
В работе алгоритма используются три регистра. В регистре ди-
намических связей fti на каждом такте декодирования содержит-
ся очередное итеративное значение ап(Х). Компоненты многочлена
о-п(Х) на n-ом такте декодирования С п д, С„,2, • • •, Cnj, где j - сте-
пень многочлена.
Рассмотрим процесс вычисления сгп(Х) более подробно. В ре-
гистр сдвига Дг последовательно, на каждом такте декодирования
5.5. Итеративный алгоритм для нахождения а{Х)


Статический
регистр Я ,




Регистр
сдвига Я2


Регистр
сдвига R3

Замечания: при каждом я , Я, содержит С„ (X)
за исключением C B j =1
Rz содержит Ы0010
k
Я 3 содержит FfX)=X°" "C k i | W
Fo = О
rf*- злемент памяти,содержащий dk^
Функции управления

я,
00 . . . 0
«2
J00 • • • 0
*3
10 • • • 0
о -*-«;о
/»;
• -/„ * I -»- /•

Поменять местами
содержимое Л , и J f 3
Прибавить
1
Умножить Л , на --^J -
раз R3 К Я,
Прибавить Я , к Я , и
сумму поместить в Л { и результат
поместить в I
Сдвинуть вправо Я 3 ,
поместив 1 в крайний
Сдвинуть J
левый разряд
вправо

Сдвинуть Л 2
вправо
и в него
подать $„+(
я+1 - ^ - л




Р и с . 5.1. Алгоритм Берлекэмпа Месси [10].
Глава 5. Дискретные преобразования Фурье и коды PC

подаются компоненты синдрома .so, s\,..., s<j-2- Пусть ln - итератив-
ная длина регистра R\ на такте п, тогда на этом же такте на выходе
вычисляется

dn = C"n,i.sin 4- C n , 2 s (n _i H + Cnii,s-0
и декодер стремится так скорректировать ап(Х), чтобы реализовать
первое уравнение из системы (5.13). Далее декодер добивается вы-
полнения второго уравнения из (5.13) при сохранении первого и т.д.
Оказывается, что процесс коррекции можно начинать прямо с пер-
вого такта, то есть с CLQ = SQ. В результате мы получим а(Х) мини-
мальной степени, при котором выполняются все уравнения из (5.13).
Контроль правильности всего процесса декодирования происхо-
дит на пятом шаге декодирования. Пусть на этом шаге вычислен
кодовый вектор V . Сравнивая V с R = V + Е можно найти чис-
ло исправлений. Если в канале произошло не более [^j^-J ошибок, то
число исправлений должно совпадать со степенью многочлена <г{Х).
Если число канальных ошибок превышает L^i^Ji T O может про-
изойти одно из трех событий. Во-первых, степень многочлена о˜(Х)
может оказаться выше [^y^J. Тогда процесс декодирования преры-
вается уже на втором этапе декодирования. Во-вторых, число ис-
правлений может не совпадать со степенью а{Х), такая ошибка об-
наруживается в конце декодирования. И, наконец, вполне возможно,
что число исправлений совпадает со степенью о(Х) и не превышает
L˜3pJ- Здесь имеет место необнаружимая ошибка декодирования.
Заметим, что для реализации этого алгоритма требуются незна-
чительные технические затраты и в настоящее время декодеры кодов
Рида - Соломона работают на скоростях до 40 Гбит/сек.

<< Предыдущая

стр. 49
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>