АП-97161
                                                   АННОТАЦИЯ

        Документ содержит описание программы, которая строит  кодовые комбинации на основе циклических кодов. Программа кодирует и деко-дирует  информационные слова. Иммитируется работа источника, переда-ющего информационное слово, кодировщика, кодирующего данное слово, канала связи и декодировщика, обнаруживающего и исправляющего ошибки в информационном полиноме. Программа работает по принципу приёмник – источник, так ,как это реализовано в устройствах, передающих информацию или обыкновенных приводах для внешних носителей в PC.
АП-97161
СОДЕРЖАНИЕ
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   
§ 1 Введение
Код ,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим ( полиномиальным, кодом с циклическими избыточными проверками-ЦИП).

Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации.

 Циклический код относится к линейным,  блочным, корректирующим, равномерным кодам.

В  циклических кодах кодовые комбинации представляются в виде многочленов, что позволяет позволяет свести действия над кодовыми комбинациями  к  действием  над многочленами (используя аппарат полиномиальной алгебры).

Циклические коды являются разновидностью систематических кодов

и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффек-

тивность при обнаружении и исправлении ошибок обеспечила им широеое применение на практике.

Циклические коды  используются в ЭВМ при последовательной передаче данных .
§ 2 Постановка задачи
Построить циклический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки ( n=31 ,s=1) двумя

способами.

Показать процесс обнаружения и исправления однократной ошибки в передаваемой кодовой комбинации. Составить программу, реализующую алгоритм кодирования, декодирования и исправления ошибки при передаче данных с использованием циклического кода.
§ 3 Операции над циклическими кодами

     1. Сдвиг справа налево осуществляется путем умножения полинома на x:

                     G(x)=x⁴+x²+1  Û 0010101;

                     G(x)×x=x⁵+x³+x Û 0101010.

     2. Операции сложения и вычитания выполняются по модулю 2 .

Они  являются эквивалентними и  ассоциативными :     

                     G₁(x)+G₂(x)=>G₃(x);

                     G₁(x) -G₂(x)=>G₃(x);

                     G₂(x)+G₁(x)=>G₃(x);

Пример:

              G₁(x)= x⁵ +x³+x;

              G₂(x)=x⁴ +x³ +1;          

              G₃(x)=G₁(x) Å G₂(x) = x⁵ +x⁴+x+1.                              

       3. Операция деления является обычным делением многочленов, только вместо вычитания  используется сложеное по модулю 2 :
         G₁(x)=x⁶+x⁴+x³ ;          

         G₂(x)=x³+x²+1  .




                   x⁶+x⁴+x³                 x³+x²+1

                ^Å x⁶+x⁵+x³                          x³ +x²

                            x⁵ + x<sup>4

                    Å</sup>   x⁵ + x⁴ +x²

                                     x²

то же в двоичном коде:

                   

        1011000            1101                               

     Å1101                  1100                               

          1100                                            

       Å 1101                                     

            100                                      

        Все операции легко реализуются аппаратно на регистрах сдвига с обратными связям.
§ 4 Принцип построения циклических кодов
Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется много-член,который не может бять представлен в виде произведения многочленов низших степеней ,т.е. такой многочлен делиться только на самого себя или на единицу и не делиться ни на какой другой многочлен.  На такой многочлен делиться без остатка двучлен xⁿ+1.Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.

Чтобы понять принцип построения циклического кода,умножаем комбинацию простого k-значного кода Q(x) на  одночлен x^r ,а затем делина образующий полином P(x) , степень которого равна r. В результате умножения Q(x) на x^r степень каждого одночлена, входящего в Q(x), повы-шается на r. При делении произведения x^rQ(x) на образующий полином получается частное C(x) такой же степени, как и Q(x).Результат можно представить в вид

                    Q(x) x^r                     R(x)                                                                                                                                                                                                                                                                            

                   ¾¾¾¾ =   C(x) + ¾¾¾   ,               (1)                                                                             

                      P(x)                        P(x)

где R(x) - остаток от деления  Q(x) x^r на 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) x^r + R(x)               (2)

Таким образом, кодовая комбинация циклического n-значного кода может

быть получена  двумя способами:

 1) умножение кодовой комбинации Q(x) простого кода на одночлен x^r

и добавление к этому произведению остатка R(x) , полученного в результате деления произведения Q(x) x^r на образующий полином P(x);

2) умножения кодовой комбинации C(x) простого k-значного на образующий полином P(x).

 При построении циклических кодов первым способом расроложение информационных символов во всех комбинациях строго упорядочено -

они занимают k старших разрядов комбинации, а остальные (n-k) разрядов

 отводятся под контрольные.

При втором способе  образования циклических кодов  информа-

ционные и контрольные символы в комбинациях циклического кода не отделены друг от друга, что затрудняет процесс декодирования.
 

 
§ 4.1 Получение кодовой комбинации добавлением остатка R(x)
Построить циклический код для передачи 31 разрядной кодовой

комбинации с исправлением однократной ошибки ( n=31, s=1)

        Решение.

1. Определим число контрольных разрядов - m :

 m = log₂ (n+1) = log₂ (31+1) = 5.

2. Определим количество информационных разрядов k :

 k = n-m = 26, 

т.е  получили (31, 26 ) - код .

3. Строим информационный полином,сответствующий информационному             слову длиной k-бит:

   G(x)=00000000000000000000000101= x² +1.

4. Осуществлям сдвиг  кода  влево на m=n-k=5 разрядов т.е  полином G(x) умножается на  x^m : 

 x^m G(x)= (x²+1) x⁵= x⁷+ x⁵ =0000000000000000000000010100000.

5. Выбирается образующий многочлен-P(x) по таблице неприводимых многочленов.  Для исправления одиночной ошибки (d₀=3) образующий полином P(x)  должен быть степени m=n-k=5 и количеством ненулевых членов  не меньше минимального кодового расстояния d₀ =3. Исходя из

этого образуюший полином P(x)  равен :

 P(x)= x⁵ + x⁴ +x³ +x ² +1 = 111101.

6.  Определим  остаток R(x) от  деления G(x)×x ^m  на  образующий по-

      лином P(x)                                  

  x⁷+ x⁵                                       x⁵ + x⁴ +x³ +x ² +1          10100000         111101

  x⁷ + x⁶ +x⁵ +x ⁴ +x²        x² +x +1                       111101              111

             x⁶ + x⁴ +x²                                                 101010

             x⁶ + x⁵ +x⁴ +x ³ +x                                     111101

                 x⁵ + x³ +x² +x                                              101110 

                 x⁵ + x⁴ +x³ +x ² +1                                   111101

                        x⁴ +x +1                                             10011
 Остаток R(x)= x⁴+x+1 =10011.

7. Строим передаваемый кодовый пролином F(x) :

  F(x)=x^m G(x)ÅR(x)= x⁷+ x⁵+ x⁴+x+1 =0000000000000000000000010110011.

8. Пусть в принятом сообщении произошла ошибка в тридцать первом разряде,при зтом принятое кодовое сообщение имеет вид :

     F¢(x)=F(x) Å E(x)= 1000000000000000000000010110011.

9.  Разделим многочлен F¹(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

Отбросив контрольные разряды , получаем переданное информацинное слово.
§ 4.2  Построение кодовой комбинации путем умножения

                на образующий полином
Построить циклический код для передачи 31 разрядной кодовой

комбинации с исправлением однократной ошибки ( n=31, s=1) путем умножения образующего многочлена на многочлен полного 31 разрядного кода.

      Решение.
1. Строим информационный полином,сответствующий информационному             слову длиной k-бит:

G(x)=00000000000000000000000101= x² +2.

2. Строим передаваемый кодовый полином

                00000000000000000000000101

                                                     111101        

                00000000000000000000000101

             00000000000000000000000101

           00000000000000000000000101

          00000000000000000000000101

        00000000000000000000000101

        0000000000000000000000011001001
  3.  Процесс исправления однократной ошибки аналогичен описанному

в  § 4.1.

Литература
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]=

                        ('  Сложением' , ' Умножением');

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<1) or (x2<=x1) or

              (y1<1) or (y2<=y1) or (x2>MaxChar) 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<MenuTop)

                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<SubMenuTop)

                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.