Циклические коды

минимального кодового расстояния 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

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

            § 4.2  Построение кодовой комбинации  путем умножения

                на образующий полином 

    Построить  циклический код для передачи 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(i0) 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(j0)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