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

§ 1 Введение

Код ,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим ( полиномиальным, кодом с циклическими избыточными проверками-ЦИП).

Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации.

Циклический код относится к линейным, блочным, корректирующим, равномерным кодам.

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

Циклические коды являются разновидностью систематических кодов и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффективность при обнаружении и исправлении ошибок обеспечила им широкое применение на практике.

Циклические коды используются в ЭВМ при последовательной передаче данных .

§ 2 Постановка задачи

Построить циклический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки ( n=31 ,s=1) двумя

способами.

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

§ 3 Операции над циклическими кодами

1. Сдвиг справа налево осуществляется путем умножения полинома на x:

G(x)=x⁴+x²+1  0010101;

G(x)x=x⁵+x³+x  0101010.

2. Операции сложения и вычитания выполняются по модулю 2 .

Они являются эквивалентными и ассоциативными :

G₁(x)+G₂(x)=>G₃(x);

G₁(x) -G₂(x)=>G₃(x);

G₂(x)+G₁(x)=>G₃(x);

Пример:

G₁(x)= x⁵ +x³+x;

G₂(x)=x⁴ +x³ +1;

G₃(x)=G₁(x)  G₂(x) = x⁵ +x⁴+x+1.

3. Операция деления является обычным делением многочленов, только вместо вычитания используется сложеное по модулю 2 :

G₁(x)=x⁶+x⁴+x³ ;

G₂(x)=x³+x²+1 .

§ 4 Принцип построения циклических кодов

Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется многочлен, который не может быть представлен в виде произведения многочленов низших степеней ,т.е. такой многочлен делиться только на самого себя или на единицу и не делиться ни на какой другой многочлен. На такой многочлен делиться без остатка двучлен xⁿ+1.Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.

Чтобы понять принцип построения циклического кода, умножаем комбинацию простого k-значного кода Q(x) на одночлен x^r ,а затем делим на образующий полином P(x) , степень которого равна r. В результате умножения Q(x) на x^r степень каждого одночлена, входящего в Q(x), повышается на r. При делении произведения x^rQ(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) x^r + R(x) (2)

Таким образом, кодовая комбинация циклического n-значного кода может

быть получена двумя способами:

1) умножение кодовой комбинации Q(x) простого кода на одночлен x^r

и добавление к этому произведению остатка R(x) , полученного в результате деления произведения Q(x) x^r на образующий полином P(x);

2) умножения кодовой комбинации C(x) простого k-значного на образующий полином P(x).

При построении циклических кодов первым способом расположение информационных символов во всех комбинациях строго упорядочено - они занимают k старших разрядов комбинации, а остальные (n-k) разрядов отводятся под контрольные.

При втором способе образования циклических кодов информационные и контрольные символы в комбинациях циклического кода не отделены друг от друга, что затрудняет процесс декодирования.

§ 6. Разработка текста программы

Для представления информационного слова в памяти используется

массив. В состав программы входит основная программа и два модуля,

реализующие алгоритм кодирования и декодирования информационных слов и диалога с пользователем соответственно.

Program Cyclic_Code;

Uses

Crt,_CC31,_Serv;

Var

m,mm:Move_code;

p:Polinom;

r:Rest;

i,Mainflag,From,Error:integer;

Switch:byte;

Key:boolean;

begin

Repeat

Key:=true;

TextColor(11);

TextBackGround(7);

Clrscr;

SetWindow(24,10,45,14,2,' Главное меню ');

Switch:=GetMainMenuChoice;

case Switch of

1:begin

About;

Readln;

Key:=False;

end;

2: begin

TextColor(0);

ClrScr;

SetWindow(25,10,40,13,1,' Образовать ');

Switch:=GetSubMenuChoice;

case Switch of

1:begin

TextBackGround(0);

TextColor(15);

ClrScr;

SetWindow(1,1,79,24,2,' Демонстрация');

TextColor(14);

GotoXY(2,2);

Init(m,p,r,MainFlag);

Write(‘Информационный полином ');

TextColor(2);

for i:=n downto 0 do

begin

if(i