Материал: 636_Nosov_V.I._Seti_radiodostupa_CH.1_

где t – количество ошибочных бит в символе, которые может исправить код, а n

–k = 2t – число контрольных символов. Расширенный код Рида-Соломона можно получить только при n = 2m или n = 2m + 1.

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

Код, который исправляет все искаженные символы, содержащие ошибки в t или меньшем числе бит, t можно выразить следующим образом

Здесь x означает наибольшее целое, не превышающее х. Из (4.25) видно, что

коды Рида-Соломона, исправляющие t символьных ошибок, требуют не более 2t контрольных символов. Следовательно, декодер имеет n – k «используемых» избыточных символов, количество которых вдвое превышает количество исправляемых ошибок. Для каждой ошибки один избыточный символ используется для обнаружения ошибки и один для определения правильного значения.

Преимущества недвоичных кодов, подобных кодам Рида-Соломона, можно показать следующим образом. Рассмотрим двоичный код (n, k) = (7, 3). Полное количество кодовых слов в нем равно 2n = 27 = 128, из которых 2k = 23 = 8 (или 1/16 часть всех кодовых слов) являются разрешенными кодовыми словами.

Теперь рассмотрим недвоичный код (n, k) = (7,3), где каждый символ состоит из m =3 бит. Полное количество кодовых слов в таком коде равно 2nm = 221 = 2 097 152 , из которых 2km =29 = 512 (или 1/4096 часть всех кодовых слов, т.е очень небольшая часть) являются разрешенными кодовыми словами.

Из сравнения двоичных и недвоичных кодов следует, что в последних используется только незначительная часть полного количества кодовых слов, и это дает возможность достичь большего значения dmin.

Рассмотрим на примере способность кода Рида-Соломона исправлять пакеты ошибок, которые могут быть вызваны либо импульсными помехами, либо глубокими замираниями сигнала в радиотракте. [18].

Возьмем для примера код (n, k) = (255,247), в котором каждый символ состоит из т = 8 бит (такие символы принято называть байтами). Поскольку п - k= 8, из уравнений (4.24) и (4.25) можно видеть, что этот код может исправлять любые 4-символьные ошибки в блоке длиной до 255

126

символов. Пусть блок длительностью 25 бит в ходе передачи поражается помехами, как показано на рисунке 4.12. В этом примере импульсная помеха или глубокое замирание сигнала попадает на 25 последовательных битов и исказит точно 4 символа. Декодер для кода (255, 247) исправит любые 4-символьные ошибки без учета характера повреждений, причиненных символу. Другими словами, если декодер исправляет байт (заменяет неправильный правильным), то ошибка может быть вызвана искажением одного или всех восьми битов. Поэтому, если символ неправильный, он может быть искажен на всех двоичных позициях.

Это дает коду Рида-Соломона огромное преимущество при наличии импульсных помех или замираний сигнала по сравнению с двоичными кодами (даже при использовании в двоичном коде чередования).

25-битовый пакет ошибок

Рис. 4.12 Блок данных, искаженный 25-битовым пакетом ошибок

В этом примере, если будет наблюдаться воздействие аддитивного белого гауссовского шума, 25-битовая случайная ошибка может исказить более чем 4 символа (искаженными могут оказаться до 25 символов). Конечно, исправление такого числа ошибочных символов окажется вне возможностей кода (255, 247).

4.6.1 Конечные поля

Для понимания принципов кодирования и декодирования недвоичных кодов, таких как коды Рида-Соломона, нужно сделать экскурс в понятие конечных полей, известных как поля Галу a (Galois fields — GF). Для любого простого числа р существует конечное поле, которое обозначается GF(p) и содержит р элементов. Понятие GF(p) можно обобщить на поле из рт элементов, именуемое полем расширения GF(p); это поле обозначается GF(pm), где m — положительное целое число. Заметим, что GF(pm) содержит в качестве подмножества все элементы GF(p). Символы из поля расширения GF(2m) используются при построении кодов Рида-Соломона.

Двоичное поле GF(2) является подполем поля расширения GF(2m), точно так же как поле вещественных чисел является подполем поля комплексных чисел. Кроме чисел 0 и 1, в поле расширения существуют дополнительные однозначные элементы, которые будут представлены новым символом . Каждый ненулевой элемент в GF(2m) можно представить как степень . Бесконечное множество элементов, F, образуется из стартового множества

127

Для вычисления из F конечного множества элементов GF(2m) на F нужно наложить условия: оно может содержать только 2m элемента и быть замкнутым относительно операции умножения. Условие замыкания множества элементов поля по отношению к операции умножения имеет вид нередуцируемого полинома

С помощью полиномиального ограничения любой элемент со степенью, большей или равной 2m-1, можно следующим образом понизить до элемента со степенью, меньшей 2m-1:

Таким образом, как показано ниже, уравнение (4.27) можно использовать для формирования конечной последовательности F* из бесконечной последовательности

F.

Операция сложения в поле расширения GF(2m).

Каждый из 2т элементов конечного поля GF(2m) можно представить как отдельный полином степени (т - 1) или меньше. Степенью полинома называется степень члена максимального порядка. Обозначим каждый ненулевой элемент

128

GF(2m) полиномом аi(Х), в котором по крайней мере т коэффициентов аi (Х) ненулевые. Для i = 0, 1, 2, ..., 2 m - 2 получим

элементов или всего восемь элементов. Каждая строка на рис. 4.13 содержит последовательность двоичных величин, представляющих коэффициенты ai,0 ,ai,1,ai,2 из уравнения (4.31).

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

Описание конечного поля с помощью примитивного полинома.

Класс полиномов, называемых примитивными полиномами, интересует нас, поскольку такие объекты определяют конечные поля GF(2m), которые, в свою очередь, нужны для описания кодов Рида-Соломона. Следующее утверждение является необходимым и достаточным условием примитивности полинома. Нередуцируемый полином f(X) порядка т будет примитивным, если наименьшим положительным целым числом n, для которого Xm + 1 делится на f(X), будет п = 2т- 1. Заметим, что нередуцируемый полином – это такой полином, который нельзя представить в виде произведения полиномов меньшего порядка; делимость А на В означает, что А делится на В с нулевым остатком и ненулевым частным.

Поле расширения GF(23).

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

там полиномов, f (X ) 1 X X 3 , который определяет конечное поле GF(2m), где степень полинома равна m = 3. Таким образом, в поле, определяемом полиномом f ( X ) , имеется 2m 23 8 элементов.

129

Рис. 4. 13 Отображение элементов поля в базисные элементы GF(8) с помощью f(X) = 1 + X + X2

Кроме того, основная теорема алгебры утверждает, что полином порядка m должен иметь в точности m корней. Следовательно, в этом примере выражение f ( X ) должно иметь три корня. Возникает определенная проблема,

поскольку 3 корня не лежат в том же конечном поле, что и коэффициенты f ( X ) . Исходя из сказанного, для рассматриваемого примера можно записать

f ( ) 0

3 1

Поскольку при операциях над двоичным полем +1 = -1, то 3 можно представить следующим образом

130