§ 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<n-n1+1)then Textcolor(9);
Write(m[i]);
end;
TextColor(14);
GotoXY(2,3);
Write('Образующий полином ');
TextColor(13);
for i:=n1 downto 0 do
Write(p[i]);
TextColor(14);
GotoXY(2,4);
Write('Сложение по модулю 2 (F(x)+P(x)): ');
FxPx(m);
TextColor(9);
for i:=n downto 0 do
begin
if(i<n1)then TextColor(2);
Write(m[i]);
end;
TextColor(14);
GotoXY(2,5);
Write('Остаток: ');
Divizion(m,r,p,Mainflag);
TextColor(11);
for i:=n1 downto Mainflag do
Write(r[i]);
GotoXY(2,6);
TextColor(14);
Write('Передаваемый полином: ');
BildMoveCode(m,r,Mainflag);
TextColor(9);
for i:=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);
for i:=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);
for i:=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);
for i:=n downto 0 do
begin
if(i<n-n1+1)then Textcolor(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);
for i:=n downto 0 do
begin
if(i<n-n1+1)then Textcolor(9);
Write(m[i]);
end;
TextColor(14);
GotoXY(2,3);
Write('Образующий полином: ');
TextColor(13);
for i:=n1 downto 0 do
Write(p[i]);
TextColor(14);
GotoXY(2,4);
Write('Результат умножения: ');
BildMoveCodeMultiplication(m);
TextColor(9);
for i:=n downto 0 do
Write(m[i]);
GotoXY(2,5);
TextColor(14);
Write('Произошла ошибка ... ');
MakeError(m,Error);
TextColor(9);
for i:=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);
for i:=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;
Until Key;
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) }
Procedure Init(var m1:Move_code;var p1:Polinom;
var r1:Rest;var flag:integer);
Procedure FxPx(var m6:Move_Code);
Procedure Divizion(var m2:Move_code;var r2:Rest;
p2:Polinom;var flag:integer);
Procedure BildMoveCode(var m3:Move_code;r3:Rest;var flag:integer);
Procedure Decoder(var m6:Move_Code);
Procedure MakeError(var m4:Move_code;var err:integer);
Procedure BildMoveCodeMultiplication(var m7:Move_Code);
Procedure Correction(var m5:Move_code;p5:Polinom;var r5:Rest);
Implementation
Procedure Init;
var
i:integer;
begin
p1[5]:=1;
p1[4]:=1;
p1[3]:=1;
p1[2]:=1;
p1[1]:=0;
p1[0]:=1;
flag:=0;
for i:=n1 downto 0 do
r1[i]:=0;
Randomize;
for i:=n-n1 downto 0 do
m1[i]:=random(2);
end;
Procedure FxPx(var m6:Move_Code);
var
i:integer;
k:byte;
begin
k:=5;
while(k>0) do
begin
for i:=n downto 1 do
m6[i]:=m6[i-1];
dec(k);
end;
for i:=n1-1 downto 0 do
m6[i]:=0;
end;
Procedure Divizion(var m2:Move_code;var r2:Rest;
p2:Polinom;var flag:integer);
label
RETURN;
var
i,j,i1,kol,Countzero:integer;