Полиномиальные коды. Полиномиальные коды
 Скачать 51.92 Kb.
|
|
Полиномиальные коды При полиномиальном кодировании каждое сообщение отождествляется с многочленом, а само кодирование состоит в умножении на фиксированный многочлен. Полиномиальные коды — блочные и отличаются от рассмотренных ранее только алгоритмами кодирования и декодирования. Пусть a = a0 . . .am−1— двоичное сообщение. Тогда сопоставим ему многочлен a(x) = a0+ a1x + … + a m−1xm-1. Все вычисления происходят в поле классов вычетов по модулю 2, т. е. от результата любой арифметической операции берется остаток от его деления на 2. Например, последовательности 10011 при m = 5 соответствует многочлен 1 + x3+ x4. Зафиксируем некоторый многочлен степени k,  Полиномиальный код с кодирующим многочленом g(x) кодирует слово сообщения a(x) многочленом  или кодовым словом из коэффициентов этого многочлена b = b0 ... bn−1. Условия g 0 ¹ 0 и g k ¹ 0 необходимы, потому что в противном случае b0 и bn−1не будут нести никакой информации, т.к. они всегда будут нулями.Пример. Рассмотрим кодирующий многочлен  Сообщение 01011, отвечающее многочлену  будет закодировано коэффициентами многочлена т.е.b = 01000101. Полиномиальный код с кодирующим многочленом g (x) степени k является матричным кодом с кодирующей матрицей G размерности m × (m + k):  Т.е. ненулевые элементы в j-й строке — это последовательность коэффициентов кодирующего многочлена, расположенных с j-го по (j + k)-й столбцах. Например, (3, 6)-код с кодирующим многочленом 1+x+x3 отвечает матрице  или отображению: 000 → 000000; 001 → 001101; 010 → 011010; 011 → 010111; 100 → 110100; 101 → 111001; 110 → 101110; 111 → 100011. Полиномиальные коды являются групповыми. Это следует из того, что коды, получаемые матричным кодированием, — групповые. Рассмотрим (m,n)-код с кодирующим многочленом g (x). Строка ошибок e = e0 ... en−1 останется необнаруженной в том и только в том случае, если соответствующий ей многочлен e(x) = e0 + e1x + ∙ ∙ ∙ + en−1xn-1делится на g (x). Действительно, a(x)g(x) + e(x) делится на g(x) тогда и только тогда, когда e(x) делится на g(x). Поэтому любая ошибка, многочлен которой не делится на g(x), будет обнаружена и, соответственно, любая ошибка, многочлен которой делится на g(x), не может быть обнаружена. Таким образом, обнаружение ошибки при использовании полиномиального кода с кодирующим многочленом g(x) может быть реализовано при помощи алгоритма деления многочленов с остатком: если остаток ненулевой, то при передаче произошло искажение данных. Коды Хэмминга можно строить как полиномиальные, например, кодирующий многочлен x3+ x2 + 1 определяет совершенный (4, 7)-код, отличный от рассмотренного ранее. Вообще же, если кодирующий многочлен g(x), порождающий соответствующий (m, n)-код, не является делителем ни одного из многочленов вида xj + 1 при j < n, то минимальное расстояние между кодовыми словами порожденного им кода не меньше 3. Пусть d — минимальное расстояние между кодовыми словами, оно равно минимуму среди весов ненулевых кодовых слов. Предположим d = 2. Тогда существует a(x) такой, что  и степень b(x) не больше n. Вес b равен 2, поэтому Следовательно, b(x)=xl(xm−l +1), что означает, что xm−l + 1 должен делиться на g(x), а это невозможно по условию. Если предположить, что d = 1, то это приведет к утверждению о том, что xmдолжен делиться на g(x), что тоже противоречит условию. Итак, d ³ 3.Кодирующий многочлен x11+ x9+ x7+ x6+ x5+ x + 1 определяет совершенный (12, 23)-код Голея (Golay) с минимальным расстоянием между кодовыми словами 7. В 1971 году финскими и советскими математиками было доказано, что кроме кодов Хэмминга и Голея других совершенных кодов нет. Наиболее интересными среди полиномиальных кодов являются циклические коды, в которых вместе с любым кодовым словом вида  есть кодовое слово |