2.5. Кодирование и декодирование кодов Рида-Соломона

Одними из лучших блочных кодов считаются коды Рида-

Соломона (п, к), которые является кодами с максимальным расстоянием (d=n-k+l). Для этих недвоичных кодов, определенных над полем GF(q), длина блока составляет n = q - 1 (обычно q = 2-m и тогда код исправляет 2-т-ичные символы).

Вероятность ошибки двоичного символа на выходе декодера Рида-Соломона определяется выражением [27]:

^m-l п

Рь < уїгт Е Чг • Cn-Psim(l - Ps{m) -\ (2.9)

где Psim = 1 - (1 - Pc)m - вероятность ошибки 2 m-ичного символа, а Рс - вероятность битовой ошибки в канале.

Блочные коды Рида-Соломона (PC) являются особенно эффективными для каналов, содержащих как случайные ошибки, так и пакеты ошибок.

Рассмотрим алгоритмы кодирования и декодирования этих кодов.

Каждый символ кодового слова Рида-Соломона состоит из нескольких

„ ^ n-k

бит. При декодировании может быть исправлено t ~ ~~^~ символов,

пораженных ошибками, причем не имеет значения один бит или все биты символа являются ошибочными.

Широкое распространение получила байтовая структура, при которой символ состоит из восьми бит. Все операции связанные с процедурами кодирования и декодирования производятся в поле Галуа GF(24) по модулю примитивного полинома или при байтовой

о

структуре в поле GF(2 ).

Код Рида-Соломона полностью определяется порождающим многочленом, который записывается следующим образом [28]

G(x) - (х - Х)-(х - Х2)-(х - Х3)(х - X4) ... (х - X2' ), (2.10)

где X - примитивный элемент поля Галуа.

Раскрывая скобки в (2.10), получим

G(x) = х21 + Х*(,)-х21- + Ха(2)-х2 *"2 + . . .+ Х*<2 м)-х + Xtt(2 °. (2.1 1) По порождающему многочлену реализуется схема кодера рис. 2.10, где Р - регистры сдвига на один символ каждый; Пь П2 -

1. переключатели. Кодер представляет собой цифровой автомат, все операции в котором производятся в поле Галуа по модулю примитивного полинома.

На вход кодера поступает информация в байтовой структуре. Информационные символы без задержки следуют на выход кодера (переключатели Пь П2 в положении 1). После поступления к- информационных символов вход кодера отключается (переключатели Пь П2 в положении 2) и с выхода поступают (п-к)-проверочных символов, которые являются содержимым сдвиговых регистров.

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

Выход кодера

Рис. 2.10

Декодирование кода PC включает в себя следующие операции:

Вычисление многочлена синдрома принятого слова. (Если синдром равен нулю, то ошибки отсутствуют, и декодирование не требуется.)

Определение полинома локаторов ошибок (решение ключевого

уравнения).

Определение позиций и значений ошибок.

Вычисление синдрома исправленного слова (для исключения ошибочного декодирования).

Синдромный многочлен имеет вид:

2t-l

S(z) = Е Sj-zJ , (2.12)

j=0

где Sj - компоненты синдрома.

n-l

Для принятого слова V(x)= LVJ-X1 , где Vj - некоторый элемент

поля Галуа, компоненты синдрома вычисляются по формуле

Sj = У(а>+|). (2.13)

Например, второй компонент синдрома имеет вид S2 = V(a3) = vn-o?Q(z) = S(z)-A(z) mod(z2t), (2.15)

где 0(z) - многочлен значений ошибок, A(z) - многочлен локаторов ошибок.

В совокупности с условиями

deg[A(z)J < t, (2.16)

deg[0(z)] < t-1, (2.17)

где deg - максимальная степень z, равенство (2.15) представляет собой ключевое уравнение, которое решается по алгоритму Евклида.

Алгоритм Евклида является рекуррентным методом нахождения наибольшего общего делителя двух многочленов. Основное утверждение, лежащее в основе этого алгоритма, состоит в следующем. Пусть a(z) и b(z) два многочлена, причем deg[a(z)] > deg[b(z)]. Разделим a(z) на b(z) и если остаток r(z) при делении равен нулю, то d(z) = b(z) является наибольшим общим делителем. Если остаток не равен нулю, то a(z) заменяется на b(z), а b(z) на r(z) и деление повторяется снова.

При каждой итерации вычисляются многочлены f,(z) и gj(z) такие,

что

fi(z).a(z) + gi(z).b(z) = r;(z). (2.18)

Введем отношение

4-(z) = -^g. (2.19)

Следует отметить, что при делении рассматриваются лишь неотрицательные степени z. Каждое следующее уравнение получается из двух предыдущих:

Ti(z) = r,.2(z) - qs(z)- rM(z), (2.20)

fi(z) = fi.2(z) - qj(z)- fi.i(z), (2.21)

g,(z) = gi.2(z) - q,(z> gM(z). (2.22)

В нашем случае

ri(z) «0i(z)f gi(z) -A,(z). (2.23)

Зададим начальные значения

f.,(z) = g0(z) = A0(z) = 1, f0(z) = g-i(z) = A-i(z) - 0,

r.i(z) = a(z) - 72\ r0(z) = b(z) = S(z). (2.24)

Условие выхода из цикла

deg[rn(z)] < t. (2.25)

Степень полинома локаторов ошибок равна числу обнаруженных ошибок v и не может превышать величины t, равной корректирующей способности кода. Корни A(z) находятся путем перебора с подстановкой элементов поля Галуа и определяют позиции на которых произошли ошибки (і-й символ является ошибочным, если А(а"') = 0). Такая операция называется процедурой Ченя [16].

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

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

декодера следует направить недекодированные информационные символы, отбросив проверочные символы от кодового слова.

Приведенное выше выражение (2.9), определяющее вероятность битовой ошибки на выходе декодера кода PC, не учитывает повторной проверки синдрома. Выражение, определяющее вероятность битовой ошибки на выходе декодера кода PC, с учетом повторной проверки синдрома можно получить, умножив вероятность ошибки в канале на вероятность появления в одном кодовом слове более t символьных ошибок:

РЬ = Рс- Е CirPsim(l -Ps,m)n". 1=1-1

(2.26)

На рис. 2.11 приведены экспериментальные зависимости вероятности ошибки от отношения сигнал/шум для кодов PC, построенных в поле GF(2 ) и исправляющих 4, 8 и 11 байтовых ошибок (при декодировании использовалась повторная проверка синдрома) [54]. На рис. 2.12 приведены теоретические зависимости вероятности ошибки от отношения сигнал/шум для тех же кодов PC, вычисленные по формуле (2.9).

0,001

0,000

0,00001

Ю h0\ дБ

На рис. 2.13 приведены теоретические зависимости вероятности ошибки от отношения сигнал/шум для тех же кодов PC, вычисленные с помощью выражения (2.26) (с учетом повторной проверки синдрома).

PU255.233)
PU255.231)) Ь(Л дБ

14 (255.2-17)

— BPS к

Рис. 2.13

Как можно видеть, экспериментальные зависимости в области высоких значений Рош смещены в сторону меньших значений отношения сигнал/шум. Это объясняется тем, что при декодировании использовалась повторная проверка синдрома. В области низких

значений Р()Ш различие между экспериментальными и теоретическими (без учета повторной проверки синдрома) зависимостями проявляется в меньшей степени. Зависимости вероятности ошибки от отношения сигнал/шум, полученные экспериментальным путем, практически полностью совпадают с теоретическими зависимостями, вычисленными по (2.26).

Сравнительные характеристики кодов Рида-Соломона,

о

построенных в поле GF(2 ), приведены на рис 2.14 [55].

: (255,207) 1

0,01

0,0001

1Е-06 О Е
1Е-08 ш аз

1Е-10 ? I

1Е-12 ?

1Е-14 О хэ ф

1Е-16 "S 1Е-18 1Е-20

Анализ показывает, что применение кодов Рида-Соломона позволяет уменьшить вероятность ошибки на выходе декодера при входных значениях Рош < 5-Ю"3. При этом коды с большей избыточностью обеспечивают меньшую вероятность ошибки на выходе. Код РС(255,239) позволяет уменьшить вероятность ошибки от величины Рош = 10° до КГ6, а код РС(255,223) - от величины Рош - 10° до КГ12.

На рис. 2.15 - 2.19 приведены зависимости вероятности ошибки от скорости кодирования R для кодов Рида-Соломона, построенных в полях GF(28), GF(27), GF(26) и GF(25), при отношении сигнал/шум от 5 до 7 дБ в канале с BPSK.

I 10

0.4 0.5 0.6 0.7

0.1 0.2 0.3

- PC (255, 255/R), GF(28) •- PC (127, 127/R),GF(27)

PC (63.63/R). GF(26)

PC(3I,31/R),GF(2*)

0.8

0.9

R

Рис. 2.15

0.1

001

MO

ош і

I 10

h02 =5.5 дБ

• J<* г» 0 5 0 6 0 7 0.8

09

0.1 0.2 0.3 0 4

PC (255, 255/R), GF(2S) PC (127, 127/R), GF(27) PC (63,63/R), GF(2°) PC(31,31/R).GF(25)

R

PC (255,255/R). GF(2 ) PC (127, 127/R), GF(27) PC (63, 63/R), GF(26)

PC(31,3I/R).GF(25)

R

пні і

PC (255,255/R), GF(28)

PC (і27, I27/R),GF(27)

PC (63,63/R). GF(2")

PC(31.31/R),GF(2$)

Рис. 2.19

При построении зависимостей вероятности ошибки от скорости кодирования учитывалось влияние избыточности. Использовались формулы (2.9) и (2.6). Код, имеющий меньшую скорость, исправляет большее число ошибок, однако, за счет большей избыточности уменьшается энергия, приходящаяся на бит информации, и вероятность ошибки на выходе декодера кода PC увеличивается. Из приведенных графиков видно, что оптимальные значения скорости кодирования лежат в пределах R - 0.65 - 0.75.

Также следует отметить, что коды PC, построенные в полях GF(26) и GF(2:>), при низких значениях отношении сигнал/шум

обеспечивают меньшую вероятность ошибки по сравнению с кодами PC GF(27) и GF(28), однако, с увеличением отношения сигнал/шум ситуация меняется на обратную.

Рош

PC (255,191) t= 32
Па рис. 2.20 представлены зависимости вероятности ошибки от отношения сигнал-шум для кода PC и сверточного кода с декодированием по Витерби с мягкими решениями.

• СК (133,171) R = 1/2
Рис. 2.20

При малых отношениях сигнал/шум сверточный код имеет неоспоримое превосходство над кодом Рида-Соломона. При значениях вероятности ошибки Рош < 10~8 выгоднее использовать код Рида- Соломона.