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

 
 
 
 
 

     Реферат. Циклические коды. 
 
 
 
 
 
 
 
 
 
 
 

     Выполнили:

     .

     Проверил:  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СОДЕРЖАНИЕ 

1. Введение ........................................................................................... 3

2. Постановка  задачи .......................................................................... 4

3. Операции  над циклическими кодами ............................................. 5

4. Принцип  построения циклических кодов  ....................................... 6

4.1. Получение  кодовой комбинации добавлением остатка R(x) ...... 8

4.2. Получение  кодовой комбинации умножением  на образующий 

       полином .......................................................................................... 11 
 
 
 
 
 
 
 
 
 
 
 

§ 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⁴

                    ^Å   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) :