Построение циклических кодов

Построение циклических кодов 1 Введение Код ,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим полиномиальным, кодом с циклическими избыточными проверками-ЦИП. Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации. Циклический код относится к линейным, блочным, корректирующим, равномерным кодам.

В циклических кодах кодовые комбинации представляются в виде многочленов, что позволяет свести действия над кодовыми комбинациями к действием над многочленами используя аппарат полиномиальной алгебры. Циклические коды являются разновидностью систематических кодов и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффективность при обнаружении и исправлении ошибок обеспечила им широкое применение на практике.

Циклические коды используются в ЭВМ при последовательной передаче данных . 2 Постановка задачи Построить циклический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки n31 ,s1 двумя способами. Показать процесс обнаружения и исправления однократной ошибки в передаваемой кодовой комбинации. Составить программу, реализующую алгоритм кодирования, декодирования и исправления ошибки при передаче данных с использованием циклического кода.

3 Операции над циклическими кодами 1. Сдвиг справа налево осуществляется путем умножения полинома на x Gxx4x21 0010101 Gxxx5x3x 2. Операции сложения и вычитания выполняются по модулю 2 . Они являются эквивалентными и ассоциативными G1xG2x G3x G1x -G2x G3x G2xG1x G3x Пример G1x x5 x3x G2xx4 x3 1 G3xG1x G2x x5 x4x3. Операция деления является обычным делением многочленов, только вместо вычитания

используется сложеное по модулю 2 G1xx6x4x3 G2xx3x21 . 4 Принцип построения циклических кодов Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется многочлен, который не может быть представлен в виде произведения многочленов низших степеней ,т.е. такой многочлен делиться только на самого себя или на единицу и не делиться ни на какой другой многочлен.

На такой многочлен делиться без остатка двучлен xn1.Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов. Чтобы понять принцип построения циклического кода, умножаем комбинацию простого k-значного кода Qx на одночлен xr ,а затем делим на образующий полином Px , степень которого равна r. В результате умножения Qx на xr степень каждого одночлена, входящего в Qx, повышается на r.

При делении произведения xrQx на образующий полином получается частное Cx такой же степени, как и Qx. Частное Cx имеет такую же степень, как и кодовая комбинация Qx простого кода, поэтому Cx является кодовой комбинацией этого же простого k-значного кода. Следует заметить, что степень остатка не может быть больше степени образующего полинома, т.е. его наивысшая степень может быть равна r-1. Следовательно, наибольшее число разрядов остатка

Rx не превышает числа r. Умножая обе части равенства 1 на Px и произведя некоторые перестановки получаем Fx Cx Px Qx xr Rx 2 Таким образом, кодовая комбинация циклического n-значного кода может быть получена двумя способами 1 умножение кодовой комбинации Qx простого кода на одночлен xr и добавление к этому произведению остатка Rx , полученного в результате деления произведения

Qx xr на образующий полином Px 2 умножения кодовой комбинации Cx простого k-значного на образующий полином Px. При построении циклических кодов первым способом расположение информационных символов во всех комбинациях строго упорядочено - они занимают k старших разрядов комбинации, а остальные n-k разрядов отводятся под контрольные. При втором способе образования циклических кодов информационные и контрольные символы в комбинациях

циклического кода не отделены друг от друга, что затрудняет процесс декодирования. 6. Разработка текста программы Для представления информационного слова в памяти используется массив. В состав программы входит основная программа и два модуля, реализующие алгоритм кодирования и декодирования информационных слов и диалога с пользователем соответственно. Program CyclicCode Uses Crt,CC31,Serv Var m,mmMovecode pPolinom rRest i,

Mainflag,From,Errorinteger Switchbyte Keyboolean begin Repeat Keytrue TextColor11 TextBackGround7 Clrscr SetWindow24,10,45,14,2, Главное меню SwitchGetMainMenuChoice case Switch of 1begin About Readln KeyFalse end 2 begin TextColor0 ClrScr SetWindow25,10,40,13,1, Образовать SwitchGetSubMenuChoice case

Switch of 1begin TextBackGround0 TextColor15 ClrScr SetWindow1,1,79,24,2, Демонстрация TextColor14 GotoXY2,2 Initm,p,r,MainFlag Write Информационный полином TextColor2 for in downto 0 do begin ifi n-n11then Textcolor9 Writemi end TextColor14 GotoXY2,3 WriteОбразующий полином TextColor13 for in1 downto 0 do Writepi TextColor14

GotoXY2,4 WriteСложение по модулю 2 FxPx FxPxm TextColor9 for in downto 0 do begin ifi n1then TextColor2 Writemi end TextColor14 GotoXY2,5 WriteОстаток Divizionm,r,p,Mainflag TextColor11 for in1 downto Mainflag do Writeri GotoXY2,6 TextColor14 WriteПередаваемый полином BildMoveCodem,r,Mainflag TextColor9 for in downto 0 do begin ifi n1 then

TextColor11 Writemi end GotoXY2,7 TextColor14 WriteПроизошла ошибка MakeErrorm,Error TextColor9 for in downto 0 do begin ifiErrorthen TextColor12 else TextColor9 writemi end GotoXY2,8 TextColor14 WriteОшибка исправлена TextColor9 Correctionm,p,r for in downto 0 do begin ifiErrorthen TextColor10 else TextColor9 writemi end TextColor14

GotoXY2,9 WriteИсходный полином Decoderm TextColor2 for in downto 0 do begin ifi n-n11then Textcolor9 Writemi end Keyfalse end 2begin TextBackGround0 TextColor15 ClrScr SetWindow1,1,79,24,2,Демонстрация TextColor14 GotoXY2,2 Initm,p,r,MainFlag WriteИнформационный полином TextColor2 for in downto 0 do begin ifi n-n11then Textcolor9

Writemi end TextColor14 GotoXY2,3 WriteОбразующий полином TextColor13 for in1 downto 0 do Writepi TextColor14 GotoXY2,4 WriteРезультат умножения BildMoveCodeMultiplicationm TextColor9 for in downto 0 do Writemi GotoXY2,5 TextColor14 WriteПроизошла ошибка MakeErrorm,Error TextColor9 for in downto 0 do begin ifiErrorthen

TextColor12 else TextColor9 writemi end GotoXY2,6 TextColor14 WriteОшибка исправлена TextColor9 Correctionm,p,r for in downto 0 do begin ifiErrorthen TextColor10 else TextColor9 writemi end Keyfalse end end TextColor14 GotoXY2,22 WriteНажмите любую клавишу Readln end 3begin ClrScr GotoXY1,24 TextColor14 WritelnРабота программы завершена

Readln TextBackGround0 TextColor15 ClrScr Keytrue end end Until Key end. 7 .Результаты работы программы Результат работы программы при образовании кода добавлением остатка Демонстрация Информационный полином Образующий полином 111101 Cложениe по модулю 2 FxPx Остаток 010101 Передаваемый полином Произошла ошибка Ошибка исправлена Исходный полином

Нажмите любую клавишу Результат работы при образовании кода умножением Демонстрация Информационный полином Образующий полином 111101 Результат умножения Произошла ошибка Ошибка исправлена Нажмите любую клавишу Выводы Данная программа кодирует сообщения используя циклический код. При этом она имитирует работу канала для передачи информации.

При возникновении исключительных ситуаций, когда информационное слово по каким-либо причинам раскодировать не удатся, программа повторяет запрос на пересылку данных, как это делается в реальных ситуациях подобного рода. Кроме этого, программа случайным образом, при прохождении информационного слова через канал допускает в слове однократную ошибку, затем исправляет ее, декодирует информационное слово и передат результат пользователю. Приложение 1 Процедуры и функции модуля сс31.

Unit CC31 Interface Uses Crt Const n30 Информациякод n15 Размер контрольных разрядов Type Movecodearray0 n of byte Передаваемый полином Fx Restarray0 n1 of byte Остаток Polinomarray0 n1 of byte Образующий полином Px Procedure Initvar m1Movecodevar p1Polinom var r1Restvar flaginteger

Procedure FxPxvar m6MoveCode Procedure Divizionvar m2Movecodevar r2Rest p2Polinomvar flaginteger Procedure BildMoveCodevar m3Movecoder3Restvar flaginteger Procedure Decodervar m6MoveCode Procedure MakeErrorvar m4Movecodevar errinteger Procedure BildMoveCodeMultiplicationvar m7MoveCode Procedure Correctionvar m5Movecodep5Polinomvar r5Rest

Implementation Procedure Init var iinteger begin p151 p141 p131 p121 p110 p101 flag0 for in1 downto 0 do r1i0 Randomize for in-n1 downto 0 do m1irandom2 end Procedure FxPxvar m6MoveCode var iinteger kbyte begin k5 whilek 0 do begin for in downto 1 do m6im6i-1 deck end for in1-1 downto 0 do m6i0 end Procedure Divizionvar m2Movecodevar r2Rest p2Polinomvar flaginteger label RETURN var i,j,i1,kol,Countzerointeger begin jn

RETURNwhilej 0andm2j0do decj ifj n1 then begin for in1 downto 0 do begin r2im2j decj end whilej 0do begin for in1 downto 0 do r2ir2i xor p2i i1n1 whilei1 0andr2i10do deci1 ifi1-1then goto RETURN Koln1-i1 whileKol 0do begin for in1 downto 1 do r2ir2i-1 decKol end Koln1-i1 whileKol 0andj 0do begin r2Kol-1m2j decKol decj end ifj-1andKol0 then begin for in1 downto 0 do r2ir2i xor p2i end else flagKol end end else ifn1j then begin for in1 downto 0 do begin r2im2j decj

end for in1 downto 0 do r2ir2i xor p2i end else ifj n1 then begin for ij downto 0 do r2im2i end end Procedure BildMoveCodevar m3Movecoder3Restvar flaginteger var i,kinteger begin ifflag 0then begin kn1-flag for in1 downto flag do begin m3kr3i deck end end else begin for in1-1 downto 0 do m3ir3i end end Procedure MakeErrorvar m4Movecodevar errinteger begin Randomize errRandomn m4errm4err xor 1 end Procedure

Decodervar m6MoveCode var iinteger kbyte begin k5 whilek 0 do begin for i0 to n-1 do m6im6i1 deck end for in downto n-n11 do m6i0 end Procedure BildMoveCodeMultiplicationvar m7MoveCode var m1,m2,m3,m4,mmMoveCode i,jinteger begin mmm7 m1m7 for j0 to 1 do begin for in downto 1 do m1im1i-1 m1j0 end m2m7 for j0 to 2 do begin for in downto 1 do m2im2i-1 m2j0 end m3m7 for j0 to 3 do begin for in downto 1 do m3im3i-1 m3j0 end m4m7 for j0 to 4 do begin for in downto 1 do m4im4i-1 m4j0 end for in downto 0 do m7immi xor

m1ixor m2ixor m3i xor m4i end Procedure Correctionvar m5Movecodep5Polinomvar r5Rest var i,Correctflag,i1integer Count,Countcarry,Carryflagbyte begin Correctflag0 Countcarry0 repeat for in1 downto 0 do r5i0 Count0 Divizionm5,r5,p5,Correctflag i1n1 whilei1 Correctflagandr5i10do deci1 ifi1Correctflag-1 or i1Correctflagandr5Correctflag1 then m50m50 xor r5Correctflag else begin Carryflagm5n for in downto 1 do m5im5i-1 m50Carryflag incCountcarry

end until i1Correctflag-1 or i1Correctflagandr5Correctflag1 while Countcarry 0 do begin Carryflagm50 for i0 to n-1 do m5im5i1 m5nCarryflag decCountcarry end end end. Приложение 2 Процедуры и функции модуля Serv. Unit SERV Interface Uses Crt,Dos Const EmptyBorder 0 SingleBorder 1 DoubleBorder 2 BorderChararray0 2,1 6 of Char 32,32,32,32,32,32, 218,196,191,179,192,217, 201,205,187,186,200,188

MaxChar80 MaxLine25 MenuTop3 SubMenuTop 2 MenuLine array1 MenuTopof string20 О программе Демонстрация Выход SubMenuLine array1 SubMenuTopof string20 Сложением , Умножением Procedure SetWindowx1,y1,x2,y2,BordbyteHeaderstrin g Procedure CursorOff Function GetMainMenuChoicebyte Function GetSubMenuChoicebyte

Procedure About Implementation Procedure SetWindowx1,y1,x2,y2,BordbyteHeaderstrin g var iinteger begin if not x1 1 or x2 x1 or y1 1 or y2 y1 or x2 MaxChar or y2 MaxLine or Bord 2 then begin GotoXYx1,y1 WriteBorderCharBord,1 for i1 to x2-x1-1 do begin GotoXYx1i,y1 WriteBorderCharBord,2 end GotoXYx2,y1 WriteBorderCharBord,3 for i1 to y2-y1-1 do begin GotoXYx1,y1i

WriteBorderCharBord,4 GotoXYx2,y1i WriteBorderCharBord,4 end GotoXYx1,y2 WriteBorderCharBord,5 for i1 to x2-x1-1 do begin GotoXYx1i,y2 WriteBorderCharBord,2 end GotoXYx2,y2 WriteBorderCharBord,6 end GotoXYx2-x1-ordHeader0 div 2x1,y1 WriteHeader end Procedure CursorOff begin asm mov ah,1 mov ch,20h int 10h end end

Function GetMainMenuChoicebyte var Countbyte iinteger ch,ch1char begin Count1 while KeyPressed do chReadkey repeat for i1 to MenuTop do begin ifiCountthen begin HighVideo TextColor0 end else begin LowVideo TextColor8 end GotoXY25,10i WritelnMenuLinei CursorOff end if KeyPressed then begin chReadkey ifch0 then begin ch1Readkey case ch1 of 72 ifCount 1

then decCount 80 ifCount MenuTop then incCount end end end untilch13 GetMainMenuChoiceCount end Function GetSubMenuChoicebyte var Countbyte iinteger ch,ch1char begin Count1 while KeyPressed do chReadkey repeat for i1 to SubMenuTop do begin ifiCountthen begin HighVideo TextColor9 end else begin LowVideo TextColor1 end GotoXY26,10i WritelnSubMenuLinei

CursorOff end if KeyPressed then begin chReadkey ifch0 then begin ch1Readkey case ch1 of 72 ifCount 1 then decCount 80 ifCount SubMenuTop then incCount end end end untilch13 GetSubMenuChoiceCount end Procedure About begin TextColor15 SetWindow5,1,75,3,1,О программе TextColor10 GotoXY6,2 TextColor10128 WriteТокарь Алексей Юрьевич АП-57.Курсовой проект.

Циклический код end end.