Зависимость между n, m и k

n	3	5	6	7	9...15	17…31	33…63	65…127
m	1	2	3	4	5…11	12…26	27…57	28…120
k	2	3	3	3	4	5	6	7

Таблица 16.3

Неприводимые полиномы p(X)

Неприводимые многочлены	Их эквиваленты
q(x) = x + 1	11
q(x^2) = x^2 + x + 1	111
q(x^3) = x^3 + x + 1	1011
q(x^3) = x^3 + x^2 + 1	1101
q(x^4) = x^4 + x + 1	10011
q(x^4) = x^4 + x^3 + 1	11001
q(x^4) = x^4 + x^3 + x^2 + x + 1	11111
q(x^5) = x^5 + x^2 + 1	100101
q(x^5) = x^5 + x^3 + 1	101001
q(x^5) = x^5 + x^3+ x^2 + x + 1	101111
q(x^5) = x^5 + x^4+ x^2 + x + 1	110111
q(x^5) = x^5 + x^4+ x^3 + x + 1	111011
q(x^5) = x^5 + x^4+ x^3 + x^2 + 1	111101
q(x^6) = x^6 + x + 1	1000011
q(x^7) = x^8	10001001
q(x^8) = x^8 + x^4+ x^3 + x^2 + 1	100011101
q(x^9) = x^9 + x^4 + 1	1000010001
q(x^10) = x^10 + x^3 + 1	10000001001

Если число проверочных символов меньше числа информационных символов, то проще комбинации циклического кода получить и с помощью образующей матрицы.

Образующая матрица состоит из двух подматриц – основной и дополнительной.

Основная матрица – это единичная транспортированная матрица Im. Она содержит m столбцов и m строк (по числу информационных разрядов кода).

Дополнительная матрица – матрица остатков. Она образуется путем деления на образующий полином P(x) многочлена в виде единицы с рядом нулей и выписыванием всех промежуточных остатков. Эта матрица содержит k столбцов и m строк.

С помощью образующей матрицы можно получить любую из N = 2^m-1 разрешенных комбинаций циклического кода. Каждая из строк образующей матрицы – это уже комбинация циклического кода. Остальные N-m комбинаций можно получить сложением по модулю 2 строк матрицы.

Пример:

Кодеры и декодеры циклических кодов в основном выполняют операции умножения и деления многочленов.

Операция деления на образующий полином P(x) осуществляется также с помощью регистра сдвига, но в этом случае регистр имеет обратные связи, включенные через сумматоры по модулю 2. Деление многочленов – это операция сложения по модулю 2 делителя с разрядами делимого, начиная со старшего разряда.

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

Рис. 16.3. Структурная схема кодирующего устройства

Схема работает следующим образом. В начальном состоянии ключ П2 замкнут, ключ П1 находится в положении «1». Информационная кодовая комбинация а(x), имеющая m разрядов (символов) подается на вход через «1» П1 и одновременно в регистр сдвига Р1. За k тактов работы регистра Р1 в нем формируется остаток r(x), который представляет собой контрольные разряды (символы) циклического кода. После этого ключ П2 размыкается, ключ П1 переводится в положение «2» и контрольные символы за k тактов работы регистра Р1 выводятся из него, следуя за информационными символами.

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

Схема декодирования (образуется с помощью деления на образующий многочлен):

Рис. 16.4. Схема декодирования циклического кода. АО - анализатор ошибок.

Исходная комбинация подается в буферный регистр и одновременно через ключ в декодирующий регистр. Если с приходом последнего символа, зафиксирован нулевой остаток, то ошибок нет, и, если не нулевой, то есть ошибка. Принятая комбинация подается через выходной сумматор, и искаженный сигнал исправляется анализатором ошибок (АО).

Рис. 16.5. Пример схемы декодирования методом деления на полином P(x) = x³+x+1

Коды Рида-Соломона. Коды Рида-Соломона являются субнабором циклических кодов и представляют собой линейные блочные коды. Код Рида-Соломона специфицируются как RS(n,m) s-битных символов.

Это означает, что кодировщик воспринимает m информационных символов по s бит каждый и добавляет символы четности для формирования n символьного кодового слова. Имеется n-m символов четности по s бит каждый. Декодер Рида-Соломона может корректировать до k / 2 символов, которые содержат ошибки в кодовом слове, где k = n - m.

Рис. 16.6. Структура кодового слова R-S

Пример. Популярным кодом Рида-Соломона является RS(255,223) с 8-битными символами. Каждое кодовое слово содержит 255 байт, из которых 223 являются информационными и 32 байтами четности. Для этого кода: n = 255, m = 223, s = 8, k = 32, k / 2 = 16.

Декодер может исправить любые 16 символов с ошибками в кодовом слове: то есть, ошибки могут быть исправлены, если число искаженных байт не превышает 16.

Коды Рида-Соломона базируются на специальном разделе математики – полях Галуа (GF), или конечных полях. Арифметические действия (+, -, x, / и др.) над элементами конечного поля дают результат, который также является элементом этого поля. Для реализации этих арифметических операций требуется специальное оборудование и/или специализированное программное обеспечение.

Общая форма образующего полинома имеет вид:

P(x) = (x-aⁱ)(x-aⁱ⁺¹)…(x-a^i+k),

кодовое слово формируется с помощью операции:

F(x) = P(x).i(x),

где P(x) – образующий полином, i(x) представляет собой информационныйблок, F(x) – кодовое слово, называемое простым элементом поля.