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

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

§ 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. Разработка текста программы

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

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

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

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=0)and(r2[i1]=0))do dec(i1);

if(i1=-1)then goto RETURN;

Kol:=n1-i1;

while(Kol>0)do

begin

for i:=n1 downto 1 do

r2[i]:=r2[i-1];

dec(Kol);

end;

Kol:=n1-i1;

while((Kol>0)and(j>=0))do

begin

r2[Kol-1]:=m2[j];

dec(Kol);

dec(j);

end;

if((j=-1)and(Kol=0))

then begin

for i:=n1 downto 0 do

r2[i]:=r2[i] xor p2[i];

end

else flag:=Kol;

end;

end

else if(n1=j)

then begin

for i:=n1 downto 0 do

begin

r2[i]:=m2[j];

dec(j);

end;

for i:=n1 downto 0 do

r2[i]:=r2[i] xor p2[i]

end

else if(j0)then

begin

k:=n1-flag;

for i:=n1 downto flag do

begin

m3[k]:=r3[i];

dec(k);

end;

end

else begin

for i:=n1-1 downto 0 do

m3[i]:=r3[i];

end;

end;

Procedure MakeError(var m4:Move_code;var err:integer);

begin

Randomize;

err:=Random(n);

m4[err]:=m4[err] xor 1;

end;

Procedure Decoder(var m6:Move_Code);

var

i:integer;

k:byte;

begin

k:=5;

while(k>0) do

begin

for i:=0 to n-1 do

m6[i]:=m6[i+1];

dec(k);

end;

for i:=n downto n-n1+1 do

m6[i]:=0;

end;

Procedure BildMoveCodeMultiplication(var m7:Move_Code);

var

m1,m2,m3,m4,mm:Move_Code;

i,j:integer;

begin

mm:=m7;

m1:=m7;

for j:=0 to 1 do

begin

for i:=n downto 1 do

m1[i]:=m1[i-1];

m1[j]:=0;

end;

m2:=m7;

for j:=0 to 2 do

begin

for i:=n downto 1 do

m2[i]:=m2[i-1];

m2[j]:=0;

end;

m3:=m7;

for j:=0 to 3 do

begin

for i:=n downto 1 do

m3[i]:=m3[i-1];

m3[j]:=0;

end;

m4:=m7;

for j:=0 to 4 do

begin

for i:=n downto 1 do

m4[i]:=m4[i-1];

m4[j]:=0;

end;

for i:=n downto 0 do

m7[i]:=mm[i] xor m1[i]xor m2[i]xor m3[i] xor m4[i];

end;

Procedure Correction(var m5:Move_code;p5:Polinom;var r5:Rest);

var

i,Correctflag,i1:integer;

Count,Countcarry,Carryflag:byte;

begin

Correctflag:=0;

Countcarry:=0;

repeat

for i:=n1 downto 0 do

r5[i]:=0;

Count:=0;

Divizion(m5,r5,p5,Correctflag);

i1:=n1;

while((i1>=Correctflag)and(r5[i1]=0))do dec(i1);

if({(i1=Correctflag-1) or

(}(i1=Correctflag)and(r5[Correctflag]=1)){)}

then m5[0]:=m5[0] xor r5[Correctflag]

else begin

Carryflag:=m5[n];

for i:=n downto 1 do

m5[i]:=m5[i-1];

m5[0]:=Carryflag;

inc(Countcarry);

end;

until ({(i1=Correctflag-1) or

(}(i1=Correctflag)and(r5[Correctflag]=1));{);}

while (Countcarry>0) do

begin

Carryflag:=m5[0];

for i:=0 to n-1 do

m5[i]:=m5[i+1];

m5[n]:=Carryflag;

dec(Countcarry);

end;

end;

end.

Приложение № 2

Процедуры и функции модуля _Serv.

Unit _SERV;

Interface

Uses

Crt,Dos;

Const

EmptyBorder =0;

SingleBorder =1;

DoubleBorder =2;

BorderChar:array[0..2,1..6] of Char=

((#32,#32,#32,#32,#32,#32),

(#218,#196,#191,#179,#192,#217),

(#201,#205,#187,#186,#200,#188));

MaxChar=80;

MaxLine=25;

MenuTop=3;

SubMenuTop =2;

MenuLine :array[1..MenuTop]of string[20]=

(' О программе...',' Демонстрация ' ‘Выход ');

SubMenuLine :array[1..SubMenuTop]of string[20]=

(' Сложением' , ' Умножением');

Procedure SetWindow(x1,y1,x2,y2,Bord:byte;Header:string);

Procedure CursorOff;

Function GetMainMenuChoice:byte;

Function GetSubMenuChoice:byte;

Procedure About;

Implementation

Procedure SetWindow(x1,y1,x2,y2,Bord:byte;Header:string);

var

i:integer;

begin

if not ((x11)

then dec(Count);

#80 : if(Count1)

then dec(Count);

#80 : if(Count