Построение кодовой комбинации путем умножения
СОДЕРЖАНИЕ
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.
x5 + x4 Å x5 + x4 +x2
то же в двоичном коде:
1100
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)
x5 + x3 +x2 +x 101110
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
111010
111000
101000 111101
101110
100110
110110
101100 111101
111110 111101
111111 111101
11110 Сравниваем вес полученного остатка w с числом исправляемых ошибок w>s.
10. Производим циклический сдвиг принятой кодовой комбинации на один разряд влево и повторяем п.9 пока w £ s.
100011
111101 111101
Складываем по модулю 2 последнее делимое с последним остатком: 0000000000000000000000101100111
0000000000000000000000101100110
Осуществляем обратный сдвиг на 1 разряд полученной комбинации 0000000000000000000000010110011 Отбросив контрольные разряды, получаем переданное информацинное слово.
Построение кодовой комбинации путем умножения
на образующий полином
Построить циклический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки (n=31, s=1) путем умножения образующего многочлена на многочлен полного 31 разрядного кода. Решение.
1. Строим информационный полином,сответствующий информационному слову длиной k-бит: G(x)=00000000000000000000000101= x2 +2. 2. Строим передаваемый кодовый полином 00000000000000000000000101 111101
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
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|