Основы теории передачи информации


Кодирование с использованием циклических кодов - часть 2


Проверочные символы являются коэффициентами полинома r(x), то есть остатка от деления m(x) × xn-k на порождающий полином g(x).

Чтобы полученный результат был понятнее, напомним, что умножению некоторого двоичного полинома на xn-k соответствует сдвиг двоичной последовательности m  =  (m0, m1 ... mk-1)  на  n-k  разрядов вправо.

 Рассмотрим пример. С использованием кода, задаваемого порождающим полиномом g(x) = 1 + x + x3, закодируем произвольную последовательность, например m = (0111).

Последовательности m =(0111) соответствует полином  m (x)=x+ x2 + x3.

Умножим m(x) на xn-k

:

m(x) × xn-k

=m(x) × x3 =(x + x2 + x3) × x3 = x4 + x5

+ x6 .                         (1.68)  

Разделим m(x) × xn-k на порождающий полином g(x)

:


 

X5 + 0  + X3

X5 + 0 + X3 +X2

                     X2=r(x).                                                      (1.69)  


Таким образом, кодовый полином, соответствующий  информационной последовательности m = (0111),

будет иметь следующий вид:

U(x) =   0*X0 + 0*X1 + 1*X2 +  0*X3 + 1*X4 + 1*X5 + 1*X6,                (1.70)  

а соответствующее кодовое слово  U = (0010111).

Итак, циклический (n,k)-код k-разрядной информационной последовательности m = (m0, m1 ... mk-1)

получают следующим образом:

-  информационную последовательность m умножают на xn-k, то есть сдвигают вправо на n-k разрядов;

полином полученной последовательности делят на порождающий полином кода g(x);

-  полученный  остаток  от деления  m(x) ×

xn-k на

g(x) прибавляют  к m(x) × xn-k,

то есть записывают в младших n-k разрядах кода.

Алгоритм кодирования, основанный на делении полиномов, можно реализовать, используя схему деления. Она представляет собой регистр сдвига, в котором цепи обратной связи замкнуты в соответствии c коэффициентами порождающего полинома g(x) (рис. 1.10).

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.10

Кодирование в схеме рис. 1.10   выполняется следующим образом:




Начало  Назад  Вперед