Построение циклических кодов § 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 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 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 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 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 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; 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 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]= (' Сложением' , ' Умножением');
Procedure SetWindow(x1, y1, x2, y2, Bord: byte; Header: string); Procedure CursorOff; Function GetMainMenuChoice: byte; Function GetSubMenuChoice: byte; Procedure About; Implementation
Procedure SetWindow(x1, y1, x2, y2, Bord: byte; Header: string); var i: integer; begin if not ((x1 (y1MaxChar) or (y2>MaxLine) or (Bord>2)) then begin GotoXY(x1, y1); Write(BorderChar[Bord, 1]); for i: =1 to x2-x1-1 do begin GotoXY(x1+i, y1); Write(BorderChar[Bord, 2]); end; GotoXY(x2, y1); Write(BorderChar[Bord, 3]); for i: =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]); for i: =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; Procedure CursorOff; begin asm mov ah, 1 mov ch, 20h int 10h end; end; Function GetMainMenuChoice: byte; var Count: byte; i: integer; ch, ch1: char; begin Count: =1; while KeyPressed do ch: =Readkey; repeat for i: =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; if KeyPressed then begin ch: =Readkey; if(ch=#0) then begin ch1: =Readkey; case ch1 of #72 : if(Count>1) then dec(Count); #80 : if(Count then inc(Count); end; end; end; until(ch=#13); GetMainMenuChoice: =Count; end; Function GetSubMenuChoice: byte; var Count: byte; i: integer; ch, ch1: char; begin Count: =1; while KeyPressed do ch: =Readkey; repeat for i: =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; if KeyPressed then begin ch: =Readkey; if(ch=#0) then begin ch1: =Readkey; case ch1 of #72 : if(Count>1) then dec(Count); #80 : if(Count then inc(Count); end; end; end; until(ch=#13); GetSubMenuChoice: =Count; end; Procedure About; begin TextColor(15); SetWindow(5, 1, 75, 3, 1, 'О программе'); TextColor(10); GotoXY(6, 2); TextColor(10+128); Write('Токарь Алексей Юрьевич АП-57. Курсовой проект. “Циклический код” '); end; end.