Построение циклических кодов § 1 Введение Код ,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим ( полиномиальным, кодом с циклическими избыточными проверками-ЦИП). Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации. Циклический код относится к линейным, блочным, корректирующим, равномерным кодам. В циклических кодах кодовые комбинации представляются в виде многочленов, что позволяет свести действия над кодовыми комбинациями к действием над многочленами (используя аппарат полиномиальной алгебры). Циклические коды являются разновидностью систематических кодов и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффективность при обнаружении и исправлении ошибок обеспечила им широкое применение на практике. Циклические коды используются в ЭВМ при последовательной передаче данных . 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. При делении произведения xrQ(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. ............