Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Циклічні коди. Згортальні коди



 

Циклические коды.

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

Циклические коды удобно описывать многочленами переменной X. При этом показатели степени соответствуют номерам разрядов, а коэффициентами этого многочлена являются 0 и 1 отображаемой кодовой комбинации. Например, комбинацию 1001101 можно записать в виде .

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

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

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

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

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

При таком методе построения коэффициенты при высших степенях являются обозначениями информационных символов, а коэффициенты при степенях порядка и ниже – проверочными.

Пример. Дано , , и Закодировать сообщение 1000100101. Для кодирования сообщения 1000100101, соответствующего многочлену разделим на :

 

В итоге этой операции получим остаток Суммируя произведение с полученным остатком, получим кодовый многочлен



В двоичном коде этому многочлену соответствует кодовая комбинация 100010010100011, в которой проверочные символы занимают 5 последних позиций.

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

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

 


Эта страница нарушает авторские права

allrefrs.ru - 2018 год. Все права принадлежат их авторам!