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

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

                                  АП-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 и количеством ненулевых  членов  не  меньше