Программирование и комп-ры

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

                                  АП-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)=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  .

                   x6+x4+x3                 x3+x2+1
                ( x6+x5+x3                          x3 +x2
                            x5 + x4
                    (   x5 + x4 +x2
                                     x2
то же в двоичном коде:

        1011000            1101
     (1101                  1100
          1100
       ( 1101
            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)
   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
    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(Count1)
          then dec(Count);
     #80 : if(Count

смотреть на рефераты похожие на "Циклические коды"