 |
Построение кодовой комбинации путем умножения
|
|
|
|
СОДЕРЖАНИЕ
1. Введение........................................................................................... 6
2. Постановка задачи.......................................................................... 7
3. Операции над циклическими кодами............................................. 8
4. Принцип построения циклических кодов....................................... 9
4.1. Получение кодовой комбинации добавлением остатка R(x)...... 11
4.2. Получение кодовой комбинации умножением на образующий
полином.......................................................................................... 14
5. Разработка схемы алгоритма........................................................... 15
6. Разработка текста программы......................................................... 16
7. Результаты работы программы....................................................... 21
----------------------------------------------------------------------------------------------------
Литература........................................................................................ 23
Приложение № 1............................................................................... 24
Приложение № 2............................................................................... 30
Введение
Код,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим (полиномиальным, кодом с циклическими избыточными проверками-ЦИП).
Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации.
Циклический код относится к линейным, блочным, корректирующим, равномерным кодам.
В циклических кодах кодовые комбинации представляются в виде многочленов, что позволяет 
позволяет свести действия над кодовыми комбинациями к действием над многочленами (используя аппарат полиномиальной алгебры).
Циклические коды являются разновидностью систематических кодов
и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффек-
|
|
|
тивность при обнаружении и исправлении ошибок обеспечила им широеое применение на практике.
Циклические коды используются в ЭВМ при последовательной передаче данных.
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.
 |
x6+x4+x3 x3+x2+1
Å x6+x5+x3 x3 +x2
x5 + x4
Å x5 + x4 +x2
x2
то же в двоичном коде:
1011000 1101
Å1101 1100
1100
Å 1101
|
|
|
100
Все операции легко реализуются аппаратно на регистрах сдвига с обратными связям.
4 Принцип построения циклических кодов
Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется много-член,который не может бять представлен в виде произведения многочленов низших степеней,т.е. такой многочлен делиться только на самого себя или на единицу и не делиться ни на какой другой многочлен. На такой многочлен делиться без остатка двучлен xn+1.Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.
Чтобы понять принцип построения циклического кода,умножаем комбинацию простого k-значного кода Q(x) на одночлен xr ,а затем делина образующий полином P(x), степень которого равна r. В результате умножения Q(x) на xr степень каждого одночлена, входящего в Q(x), повы-шается на r. При делении произведения xrQ(x) на образующий полином получается частное C(x) такой же степени, как и Q(x).Результат можно представить в вид
Q(x) xr R(x)
¾¾¾¾ = C(x) + ¾¾¾, (1)
P(x) P(x)
где R(x) - остаток от деления Q(x) xr на P(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) разрядов
отводятся под контрольные.
При втором способе образования циклических кодов информа-
ционные и контрольные символы в комбинациях циклического кода не отделены друг от друга, что затрудняет процесс декодирования.
4.1 Получение кодовой комбинации добавлением остатка R(x)
Построить циклический код для передачи 31 разрядной кодовой
комбинации с исправлением однократной ошибки (n=31, s=1)
Решение.
1. Определим число контрольных разрядов - m:
m = log2 (n+1) = log2 (31+1) = 5.
2. Определим количество информационных разрядов k:
k = n-m = 26,
т.е получили (31, 26) - код.
3. Строим информационный полином,сответствующий информационному слову длиной k-бит:
G(x)=00000000000000000000000101= x2 +1.
4. Осуществлям сдвиг кода влево на m=n-k=5 разрядов т.е полином G(x) умножается на xm :
xm G(x)= (x2+1) x5= x7+ x5 =0000000000000000000000010100000.
5. Выбирается образующий многочлен-P(x) по таблице неприводимых многочленов. Для исправления одиночной ошибки (d0=3) образующий полином P(x) должен быть степени m=n-k=5 и количеством ненулевых членов не меньше минимального кодового расстояния d0 =3. Исходя из
этого образуюший полином P(x) равен:
P(x)= x5 + x4 +x3 +x 2 +1 = 111101.
6. Определим остаток R(x) от деления G(x)×x m на образующий по-
лином P(x)
x7+ x5 x5 + x4 +x3 +x 2 +1 10100000 111101
x7 + x6 +x5 +x 4 +x2 x2 +x +1 111101 111
x6 + x4 +x2 101010
x6 + x5 +x4 +x 3 +x 111101
|
|
|
x5 + x3 +x2 +x 101110
x5 + x4 +x3 +x 2 +1 111101
x4 +x +1 10011
Остаток R(x)= x4+x+1 =10011.
7. Строим передаваемый кодовый пролином F(x):
F(x)=xm G(x)ÅR(x)= x7+ x5+ x4+x+1 =0000000000000000000000010110011.
8. Пусть в принятом сообщении произошла ошибка в тридцать первом разряде,при зтом принятое кодовое сообщение имеет вид:
F¢(x)=F(x) Å E(x)= 1000000000000000000000010110011.
9. Разделим многочлен F1(x) соотвествующий полученной кодовой ком-бинации на образующий полином, при этом вес остатка (количество единиц в коде остатка) должен быть меньше или равен количеству ошибок W £S
1000000000000000000000010110011 111101
111101
111010
111101
111000
111101
101000
111101
101010
111101
101110
111101
100110
111101
110110
111101
101100
111101
100010
111101
111110
111101
110010
111101
111111
111101
100011
111101
11110
Сравниваем вес полученного остатка w с числом исправляемых ошибок
w>s.
10. Производим циклический сдвиг принятой кодовой комбинации на один
разряд влево и повторяем п.9 пока w £ s.
a) 0000000000000000000000101100111 111101
111101
100011
111101
111101
111101
1 Þ w=s.
Складываем по модулю 2 последнее делимое с последним остатком:
0000000000000000000000101100111
Å 1
0000000000000000000000101100110
Осуществляем обратный сдвиг на 1 разряд полученной комбинации
0000000000000000000000010110011
Отбросив контрольные разряды, получаем переданное информацинное слово.
Построение кодовой комбинации путем умножения
|
|
|
на образующий полином
Построить циклический код для передачи 31 разрядной кодовой
комбинации с исправлением однократной ошибки (n=31, s=1) путем умножения образующего многочлена на многочлен полного 31 разрядного кода.
Решение.
1. Строим информационный полином,сответствующий информационному слову длиной k-бит:
G(x)=00000000000000000000000101= x2 +2.
2. Строим передаваемый кодовый полином
00000000000000000000000101
111101
00000000000000000000000101
00000000000000000000000101
00000000000000000000000101
00000000000000000000000101
00000000000000000000000101
0000000000000000000000011001001
3. Процесс исправления однократной ошибки аналогичен описанному
в § 4.1.
5. Разработка схемы алгоритма
Ciclic code
 | |||
 | |||
нет
да
 |  | ||
 |
нет
да
Конец
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. “Кодирование информации (двоичные коды)”.Березюк Н.Т.,
Андрущенко А.Г., Мощицкий С.С. и др. Харьков,издательское объеди-
нение “Вища школа”,1978. 252 с.
2. “ Программирование в среде Turbo Pascal “. Марченко А.И., Марченко
Л.А. Москва,“Бином Универсал”.Киев,”Юниор”,1997.495 с.
Приложение № 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;
begin
j:=n;
RETURN:while((j>=0)and(m2[j]=0))do dec(j);
if(j>n1)
then begin
for i:=n1 downto 0 do
begin
r2[i]:=m2[j];
dec(j);
end;
while(j>=0)do
begin
for i:=n1 downto 0 do
r2[i]:=r2[i] xor p2[i];
i1:=n1;
while((i1>=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(j<n1)
then begin
for i:=j downto 0 do
r2[i]:=m2[i]
end;
end;
Procedure BildMoveCode(var m3:Move_code;r3:Rest;var flag:integer);
var
i,k:integer;
begin
if(flag>0)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]=
(' Сложением', ' Умножением');
Procedur
|
|
|
