Реферат: Построение циклических кодов
§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.