Образования циклического кода.

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

Затем произведение G (x)× x^k делится на образующий многочлен Р (x). В общем случае мы получаем в результате такого деления Q (x) той же степени, что и G (x) и остаток R (x). Остаток R (x) прибавляется к G (x)× x^k. Получаем многочлен F (x) = G (x)× x^k + R (x).

Так как в комбинациях, соответствующих многочлену G (x)× x^k, первые k младших разрядов – нули, а R (x) – многочлен степени не выше k -1, то операция получения многочлена соответствует приписыванию R (x) к G (x) со стороны младших разрядов.

Полученный таким образом многочлен F (x) будет делиться на образующий многочлен Р (x) без остатка.

Таким образом, циклический код можно получить, если к каждой кодовой комбинации безызбыточного кода приписывать остаток от деления многочлена, соответствующего этой кодовой комбинации на образующий многочлен.

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

Пример образования циклического кода.

Пусть информационный код содержит m = 4 разрядов. Одна из N = 2 ^m комбинаций этого кода: 1101 в виде многочлена запишется так: G (x) = x ³ + x ² + 1.

Если циклический код обнаруживает и исправляет одну ошибку, его минимальное кодовое расстояние равно: d_min = S + r + 1 = 3 (где r - число обнаруживаемых, а S - число исправляемых ошибок).

Выберем из Таблицы 3.2 значение k (для m = 4, k = 3).

Выберем из таблицы 3.3 полином P (x) для k = 3: P (x) = x ³ + x + 1 (т.е. 1011)

Умножим G (x) на x^k : G (x)× x ³ = (x ³ + x ² + 1)× x ³ = x ⁶ + x ⁵ + x ³ (т.е. 1101 × 1000 = 1101000)

Разделим G (x)× x^k на полином P (x):

В результате получаем: G (x)× x ³/ P (x) = (x ³ + x ² + x + 1) + 001/ (x ³ + x + 1) или: 1111 + 001 / 1011

В соответствии с n = m + k: (x ³ + x ² + x + 1) = Q (x) → 1111

1/(x ³ + x + 1) = R (x) / P (x) → 001 / 1011

R (x) = 001

Искомый многочлен F (x) равен:

F (x) = Q (x) × P (x) = G (x) × x ^k + R (x) = x ⁶ + x ⁵ + x ³ + 1 → 1101001

Для обнаружения и исправления ошибок принятая комбинация делится на образующий многочлен P (х). Если остаток R (х) = 0, значит, комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной.

Зависимость между n, m и k Таблица 16.2

n					9...15	17…31	33…63	65…127
m					5…11	12…26	27…57	28…120
k

Неприводимые полиномы P (x) Таблица 16.3

Неприводимые многочлены	Их эквиваленты
q (x) = x + 1
q (x ^2) = x ^2 + x + 1
q (x ^3) = x ^3 + x + 1
q (x ^3) = x ^3 + x ^2 + 1
q (x ^4) = x ^4 + x + 1
q (x ^4) = x ^4 + x ^3 + 1
q (x ^4) = x ^4 + x ^3 + x ^2 + x + 1
q (x ^5) = x ^5 + x ^2 + 1
q (x ^5) = x ^5 + x ^3 + 1
q (x ^5) = x ^5 + x ^3+ x ^2 + x + 1
q (x ^5) = x ^5 + x ^4+ x ^2 + x + 1
q (x ^5) = x ^5 + x ^4+ x ^3 + x + 1
q (x ^5) = x ^5 + x ^4+ x ^3 + x ^2 + 1
q (x ^6) = x ^6 + x + 1
q (x ^7) = x ^8
q (x ^8) = x ^8 + x ^4+ x ^3 + x ^2 + 1
q (x ^9) = x ^9 + x ^4 + 1
q (x ^10) = x ^10 + x ^3 + 1

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

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

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

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

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

Пример16.1.

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

Операция деления на образующий полином 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

Дата добавления: 2015-10-28