Реферат: Построение циклических кодов

 

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

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

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

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

ProgramCyclic_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;

 caseSwitch of

 1:begin

 About;

 Readln;

 Key:=False;

 end;

 2:begin

 TextColor(0);

 ClrScr;

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

 Switch:=GetSubMenuChoice;

 caseSwitch 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);

fori:=n downto 0 do

begin

 if(i<n-n1+1)thenTextcolor(9);

 Write(m[i]);

end;

TextColor(14);

GotoXY(2,3);

Write('Образующийполином ');

TextColor(13);

fori:=n1 downto 0 do

Write(p[i]);

TextColor(14);

GotoXY(2,4);

Write('Сложениепо модулю 2 (F(x)+P(x)): ');

FxPx(m);

TextColor(9);

fori:=n downto 0 do

begin

 if(i<n1)thenTextColor(2);

 Write(m[i]);

end;

TextColor(14);

GotoXY(2,5);

Write('Остаток:');

Divizion(m,r,p,Mainflag);

TextColor(11);

fori:=n1 downto Mainflag do

 Write(r[i]);

GotoXY(2,6);

TextColor(14);

Write('Передаваемыйполином: ');

BildMoveCode(m,r,Mainflag);

TextColor(9);

fori:=n downto 0 do

begin

 if(i<n1)then TextColor(11);

 Write(m[i]);

end;

GotoXY(2,7);

TextColor(14);

Write('Произошлаошибка… ');

MakeError(m,Error);

TextColor(9);

fori:=n downto 0 do

begin

 if(i=Error)then

 TextColor(12)

 else

 TextColor(9);

 write(m[i]);

end;

GotoXY(2,8);

TextColor(14);

Write('Ошибкаисправлена! ');

TextColor(9);

Correction(m,p,r);

fori:=n downto 0 do

begin

 if(i=Error)then

 TextColor(10)

 else

 TextColor(9);

 write(m[i]);

 end;

 TextColor(14);

 GotoXY(2,9);

 Write('Исходныйполином: ');

 Decoder(m);

 TextColor(2);

 fori:=n downto 0 do

 begin

 if(i<n-n1+1)thenTextcolor(9);

 Write(m[i]);

end;

 Key:=false;

 end;

 2: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);

fori:=n downto 0 do

begin

 if(i<n-n1+1)thenTextcolor(9);

 Write(m[i]);

end;

TextColor(14);

GotoXY(2,3);

Write('Образующийполином: ');

TextColor(13);

fori:=n1 downto 0 do

Write(p[i]);

TextColor(14);

GotoXY(2,4);

Write('Результатумножения: ');

BildMoveCodeMultiplication(m);

TextColor(9);

fori:=n downto 0 do

 Write(m[i]);

GotoXY(2,5);

TextColor(14);

Write('Произошлаошибка … ');

MakeError(m,Error);

TextColor(9);

fori:=n downto 0 do

begin

 if(i=Error)then

 TextColor(12)

 else

 TextColor(9);

 write(m[i]);

end;

GotoXY(2,6);

TextColor(14);

Write('Ошибкаисправлена ! ');

TextColor(9);

Correction(m,p,r);

fori:=n downto 0 do

begin

 if(i=Error)then

 TextColor(10)

 else

 TextColor(9);

 write(m[i]);

 end;

Key:=false;

end;

 end;

 TextColor(14);

 GotoXY(2,22);

 Write('Нажмителюбую клавишу...');

 Readln;

 end;

 3:begin

 ClrScr;

 GotoXY(1,24);

 TextColor(14);

 Writeln('Работапрограммы завершена ...');

 Readln;

 TextBackGround(0);

 TextColor(15);

 ClrScr;

 Key:=true;

 end;

 end;

 UntilKey;

end.

 

§7.Результатыработы программы

Результатработы программы при образовании кода добавлением остатка

Демонстрация

 Информационныйполином: 0000011010111110011110110110110

 Образующийполином: 111101

Cложениeпо модулю 2 (F(x)+P(x)): 1101011111001111011011011000000

 Остаток:010101

 Передаваемыйполином: 1101011111001111011011011010101

 Произошлаошибка… 1101011111001110011011011010101

 Ошибкаисправлена! 1101011111001111011011011010101

 Исходныйполином: 0000011010111110011110110110110

Нажмителюбую клавишу…

Результатработы при образовании кода умножением

Демонстрация

 Информационныйполином: 0000001010110000011111010001011

 Образующийполином: 111101

 Результатумножения: 0110000011111010000100100101111

 Произошлаошибка… 0110000011111010000100100101101

 Ошибкаисправлена! 0110000011111010000100100101111

Нажмителюбую клавишу...

Выводы:

 Даннаяпрограмма кодирует сообщения используя циклический код.

Приэтом она имитирует работу канала для передачи информации.

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

 Кромеэтого, программа случайным образом, «при прохождении

информационногослова через канал» допускает в слове однократную ошибку, затем исправляетее, декодирует информационное слово и передаёт результат пользователю.


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

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

Unit_CC31;

Interface

Uses

 Crt;

Const

 n=30;{ Информация+код }

 n1=5; { Размер контрольных разрядов }

 Type

 Move_code=array[0..n]of byte; { Передаваемый полином F(x) }

 Rest=array[0..n1]of byte; { Остаток }

 Polinom=array[0..n1]of byte; { Образующий полином P(x) }

ProcedureInit(var m1:Move_code;var p1:Polinom;

 varr1:Rest;var flag:integer);

ProcedureFxPx(var m6:Move_Code);

ProcedureDivizion(var m2:Move_code;var r2:Rest;

 p2:Polinom;varflag:integer);

ProcedureBildMoveCode(var m3:Move_code;r3:Rest;var flag:integer);

ProcedureDecoder(var m6:Move_Code);

ProcedureMakeError(var m4:Move_code;var err:integer);

ProcedureBildMoveCodeMultiplication(var m7:Move_Code);

ProcedureCorrection(var m5:Move_code;p5:Polinom;var r5:Rest);

Implementation

ProcedureInit;

var

 i:integer;

begin

 p1[5]:=1;

 p1[4]:=1;

 p1[3]:=1;

 p1[2]:=1;

 p1[1]:=0;

 p1[0]:=1;

 flag:=0;

 fori:=n1 downto 0 do

 r1[i]:=0;

 Randomize;

 fori:=n-n1 downto 0 do

 m1[i]:=random(2);

 end;

ProcedureFxPx(var m6:Move_Code);

var

 i:integer;

 k:byte;

begin

 k:=5;

 while(k>0)do

 begin

 fori:=n downto 1 do

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

 dec(k);

 end;

 fori:=n1-1 downto 0 do

m6[i]:=0;

end;

ProcedureDivizion(var m2:Move_code;var r2:Rest;

 p2:Polinom;varflag:integer);

label

 RETURN;

var

 i,j,i1,kol,Countzero:integer;

begin

 j:=n;

RETURN:while((j>=0)and(m2[j]=0))dodec(j);

 if(j>n1)

 thenbegin

 fori:=n1 downto 0 do

 begin

 r2[i]:=m2[j];

 dec(j);

 end;

 while(j>=0)do

 begin

 fori:=n1 downto 0 do

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

 i1:=n1;

 while((i1>=0)and(r2[i1]=0))dodec(i1);

 if(i1=-1)thengoto RETURN;

 Kol:=n1-i1;

 while(Kol>0)do

 begin

 fori:=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))

 thenbegin

 fori:=n1 downto 0 do

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

end

 elseflag:=Kol;

 end;

 end

 elseif(n1=j)

 thenbegin

 fori:=n1 downto 0 do

 begin

 r2[i]:=m2[j];

 dec(j);

 end;

 fori:=n1 downto 0 do

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

 end

 elseif(j<n1)

 thenbegin

fori:=j downto 0 do

 r2[i]:=m2[i]

 end;

end;

ProcedureBildMoveCode(var m3:Move_code;r3:Rest;var flag:integer);

var

 i,k:integer;

begin

 if(flag>0)then

 begin

 k:=n1-flag;

 fori:=n1 downto flag do

 begin

 m3[k]:=r3[i];

 dec(k);

 end;

 end

 elsebegin

 fori:=n1-1 downto 0 do

 m3[i]:=r3[i];

end;

end;

ProcedureMakeError(var m4:Move_code;var err:integer);

begin

 Randomize;

 err:=Random(n);

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

end;

ProcedureDecoder(var m6:Move_Code);

var

 i:integer;

 k:byte;

begin

 k:=5;

 while(k>0)do

 begin

 fori:=0 to n-1 do

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

 dec(k);

 end;

 fori:=n downto n-n1+1 do

m6[i]:=0;

end;

ProcedureBildMoveCodeMultiplication(var m7:Move_Code);

var

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

 i,j:integer;

begin

 mm:=m7;

 m1:=m7;

 forj:=0 to 1 do

 begin

 fori:=n downto 1 do

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

 m1[j]:=0;

 end;

 m2:=m7;

 forj:=0 to 2 do

 begin

 fori:=n downto 1 do

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

 m2[j]:=0;

 end;

 m3:=m7;

 forj:=0 to 3 do

 begin

 fori:=n downto 1 do

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

 m3[j]:=0;

 end;

 m4:=m7;

 forj:=0 to 4 do

 begin

 fori:=n downto 1 do

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

 m4[j]:=0;

 end;

 fori:=n downto 0 do

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

end;

ProcedureCorrection(var m5:Move_code;p5:Polinom;var r5:Rest);

var

 i,Correctflag,i1:integer;

 Count,Countcarry,Carryflag:byte;

begin

 Correctflag:=0;

 Countcarry:=0;

 repeat

 fori:=n1 downto 0 do

 r5[i]:=0;

 Count:=0;

 Divizion(m5,r5,p5,Correctflag);

 i1:=n1;

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

 if({(i1=Correctflag-1)or

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

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

 elsebegin

 Carryflag:=m5[n];

 fori:=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];

 fori:=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]=

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

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

ProcedureCursorOff;

FunctionGetMainMenuChoice:byte;

FunctionGetSubMenuChoice:byte;

ProcedureAbout;

Implementation

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

var

 i:integer;

begin

 ifnot ((x1<1) or (x2<=x1) or

 (y1<1)or (y2<=y1) or (x2>MaxChar) or

 (y2>MaxLine)or (Bord>2)) then

 begin

 GotoXY(x1,y1);

 Write(BorderChar[Bord,1]);

 fori:=1 to x2-x1-1 do

begin

 GotoXY(x1+i,y1);

 Write(BorderChar[Bord,2]);

end;

 GotoXY(x2,y1);

 Write(BorderChar[Bord,3]);

 fori:=1 to y2-y1-1 do

begin

 GotoXY(x1,y1+i);

 Write(BorderChar[Bord,4]);

 GotoXY(x2,y1+i);

 Write(BorderChar[Bord,4]);

end;

 GotoXY(x1,y2);

 Write(BorderChar[Bord,5]);

 fori:=1 to x2-x1-1 do

begin

 GotoXY(x1+i,y2);

 Write(BorderChar[Bord,2]);

end;

 GotoXY(x2,y2);

 Write(BorderChar[Bord,6]);

 end;

 GotoXY((x2-x1-ord(Header[0]))div 2+x1,y1);

 Write(Header)

end;

ProcedureCursorOff;

begin

 asm

 movah,1

 movch,20h

 int10h

 end;

end;

FunctionGetMainMenuChoice:byte;

var

 Count:byte;

 i:integer;

 ch,ch1:char;

begin

 Count:=1;

 whileKeyPressed do

 ch:=Readkey;

 repeat

 fori:=1 to MenuTop do

 begin

 if(i=Count)then

begin

 HighVideo;

 TextColor(0);

end

 else

 begin

 LowVideo;

 TextColor(8);

 end;

 GotoXY(25,10+i);

 Writeln(MenuLine[i]);

 CursorOff;

 end;

 ifKeyPressed

 thenbegin

ch:=Readkey;

 if(ch=#0)

 thenbegin

 ch1:=Readkey;

 casech1 of

 #72: if(Count>1)

 thendec(Count);

 #80: if(Count<MenuTop)

 theninc(Count);

 end;

 end;

 end;

 until(ch=#13);

 GetMainMenuChoice:=Count;

end;

FunctionGetSubMenuChoice:byte;

var

 Count:byte;

 i:integer;

 ch,ch1:char;

begin

 Count:=1;

 whileKeyPressed do

 ch:=Readkey;

 repeat

 fori:=1 to SubMenuTop do

 begin

 if(i=Count)then

begin

 HighVideo;

 TextColor(9);

end

 else

 begin

 LowVideo;

 TextColor(1);

 end;

 GotoXY(26,10+i);

 Writeln(SubMenuLine[i]);

 CursorOff;

 end;

 ifKeyPressed

 thenbegin

ch:=Readkey;

 if(ch=#0)

 thenbegin

 ch1:=Readkey;

 casech1 of

 #72: if(Count>1)

 thendec(Count);

 #80: if(Count<SubMenuTop)

 theninc(Count);

 end;

 end;

 end;

 until(ch=#13);

 GetSubMenuChoice:=Count;

end;

ProcedureAbout;

begin

 TextColor(15);

 SetWindow(5,1,75,3,1,'Опрограмме');

 TextColor(10);

 GotoXY(6,2);

 TextColor(10+128);

 Write('ТокарьАлексей Юрьевич АП-57.Курсовой проект.

 “Циклическийкод” ');

end;

end.

еще рефераты
Еще работы по информатике, программированию