Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Полиномиальные коды

При полиномиальном кодировании каждое сообщение отождествляется с многочленом, а само кодирование состоит в умножении на фиксированный многочлен. Полиномиальные коды — блочные и отличаются от рассмотренных ранее только алгоритмами кодирования и декодирования.

Пусть 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(xml + 1), что означает, что xml + 1 должен делиться на g(x), а это невозможно по условию. Если предположить, что d = 1, то это приведет к утверждению о том, что xm должен делиться на g(x), что тоже противоречит условию. Итак, d ³ 3.

Кодирующий многочлен x11 + x9 + x7 + x6 + x5 + x + 1 определяет совершенный (12, 23)-код Голея (Golay) с минимальным расстоянием между кодовыми словами 7.

В 1971 году финскими и советскими математиками было доказано, что кроме кодов Хэмминга и Голея других совершенных кодов нет.

Наиболее интересными среди полиномиальных кодов являются циклические коды, в которых вместе с любым кодовым словом вида есть кодовое слово

<== предыдущая лекция | следующая лекция ==>
Совершенные и квазисовершенные коды | Понятие о кодах Боуза-Чоудхури-Хоккенгема
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 4862; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.