Построение циклических кодов

Код ,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим ( полиномиальным, кодом с циклическими избыточными проверками-ЦИП).
Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации.
Циклический код относится к линейным, блочным, корректирующим, равномерным кодам.
В циклических кодах кодовые комбинации представляются в виде многочленов, что позволяет свести действия над кодовыми комбинациями к действием над многочленами (используя аппарат полиномиальной алгебры).
Циклические коды являются разновидностью систематических кодов и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффективность при обнаружении и исправлении ошибок обеспечила им широкое применение на практике.
Циклические коды используются в ЭВМ при последовательной передаче данных .
§ 2 Постановка задачи
Построить циклический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки ( n=31 ,s=1) двумя
способами.
Показать процесс обнаружения и исправления однократной ошибки в передаваемой кодовой комбинации. Составить программу, реализующую алгоритм кодирования, декодирования и исправления ошибки при передаче данных с использованием циклического кода.
§ 3 Операции над циклическими кодами
1. Сдвиг справа налево осуществляется путем умножения полинома на x:
G(x)=x4 +x2 +1 Û 0010101;
G(x)×x=x5 +x3 +x Û 0101010.
2. Операции сложения и вычитания выполняются по модулю 2 .
Они являются эквивалентными и ассоциативными :
G1 (x)+G2 (x)=>G3 (x);
G1 (x) -G2 (x)=>G3 (x);
G2 (x)+G1 (x)=>G3 (x);
Пример:
G1 (x)= x5 +x3 +x;
G2 (x)=x4 +x3 +1;
G3 (x)=G1 (x) Å G2 (x) = x5 +x4 +x+1.
3. Операция деления является обычным делением многочленов, только вместо вычитания используется сложеное по модулю 2 :
G1 (x)=x6 +x4 +x3 ;
G2 (x)=x3 +x2 +1 .
§ 4 Принцип построения циклических кодов
Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется многочлен, который не может быть представлен в виде произведения многочленов низших степеней ,т.е. такой многочлен делиться только на самого себя или на единицу и не делиться ни на какой другой многочлен. На такой многочлен делиться без остатка двучлен xn +1.Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.
Чтобы понять принцип построения циклического кода, умножаем комбинацию простого k-значного кода Q(x) на одночлен xr ,а затем делим на образующий полином P(x) , степень которого равна r. В результате умножения Q(x) на xr степень каждого одночлена, входящего в Q(x), повышается на r. При делении произведения xr Q(x) на образующий полином получается частное C(x) такой же степени, как и Q(x).
Частное C(x) имеет такую же степень, как и кодовая комбинация Q(x) простого кода, поэтому C(x) является кодовой комбинацией этого же простого k-значного кода. Следует заметить, что степень остатка не может быть больше степени образующего полинома, т.е. его наивысшая степень может быть равна (r-1). Следовательно, наибольшее число разрядов остатка R(x) не превышает числа r.
Умножая обе части равенства (1) на P(x) и произведя некоторые перестановки получаем :
F(x) = C(x) P(x) = Q(x) xr + R(x) (2)
Таким образом, кодовая комбинация циклического n-значного кода может
быть получена двумя способами:
1) умножение кодовой комбинации Q(x) простого кода на одночлен xr
и добавление к этому произведению остатка R(x) , полученного в результате деления произведения Q(x) xr на образующий полином P(x);
2) умножения кодовой комбинации C(x) простого k-значного на образующий полином P(x).
При построении циклических кодов первым способом расположение информационных символов во всех комбинациях строго упорядочено - они занимают k старших разрядов комбинации, а остальные (n-k) разрядов отводятся под контрольные.
При втором способе образования циклических кодов информационные и контрольные символы в комбинациях циклического кода не отделены друг от друга, что затрудняет процесс декодирования.
§ 6. Разработка текста программы
Для представления информационного слова в памяти используется
массив. В состав программы входит основная программа и два модуля,
реализующие алгоритм кодирования и декодирования информационных слов и диалога с пользователем соответственно.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию