Зразки розв'язування задач до розділу 12

 

Приклад 1  Поліноміальний код заданий твірним многочленом g(x)=1+x4+x5. Закодувати двійкові комбінації 1011, 11001100. Побудувати твірну матрицю для кожного з одержаних кодів.

 

Розв'язання

1) Закодуємо повідомлення 1011 довжиною k=4 символи.

                Цій послідовності відповідає многочлен степеня k-1 m(x)=1x0+0x1+1x2+1x3=1+x2+x3.

                Поліноміальний код повідомлення утворюється множенням многочлена інформаційної послідовності на твірний поліном коду. 

                За умовою задачі використовується поліноміальний код з твірним многочленом 5-го степеня і кодується повідомлення, якому відповідає многочлен 3-го степеня. У результаті одержуємо кодовий поліном u(x) степеня n-1 – у даному випадку 8-го степеня, що визначає послідовність довжиною n=9 бітів:

                u(x)=m(x)g(x)= (1+x2+x3)(1+x4+x5)= 1+ x2+ x3+ x4+ x5+ x6+

+ (1+1)x7+ x8= 1+ x2+ x3+ x4+ x5+ x6+ x8.

                Отриманому многочлену u(x)= 1+x2+x3+x4+x5+x6+x8= = 1x0 +0x1+1x2+1x3 +1x4+1x5+1x6+0x7+1x8 відповідає вектор u=(101111101), отже, задане інформаційне повідомлення кодується так: (1011)  (101111101).

                Твірна матриця коду має розмірність (n-k)n і таку структуру:

,

де через g0, g1, …, gn-k-1 позначені коефіцієнти твірного многочлена коду.

                У даному випадку маємо (4, 9)- код, твірна матриця якого має вигляд

.

                Закодуємо задане повідомлення за допомогою твірної матриці:

                u=mG= (1011) =(101111101).

                Одержали кодову послідовність (1011)  (101111101).

2) Закодуємо повідомлення m=(11001100).

                Кількість інформаційних елементів у повідомленні k=8.

                Кількість перевірних елементів r=n-k визначається степенем твірного полінома коду – у даному випадку r=5.

                Довжина кодового слова n=k+r=8+5=13. 

                Многочлен інформаційного повідомлення m= (11001100) такий: m(x)= 1x0+1x1+0x2+0x3+1x4+1x5+0x6+0x7= 1+x+x4+x5.

Його кодовий поліном u(x) має степінь n-1=12 і визначається так:

                u(x)=m(x)g(x)=(1+x+x4+x5)( 1+x4+x5)= 1+x+x5+x6+x8+x10.

Отриманий многочлен u(x)=1x0+1x1+0x2+0x3 +0x4+1x5+1x6+ +0x7+1x8+0x9+1x10 +0x11+0x12 визначає кодове слово u=(1100011010100).

                Отже, задане інформаційне повідомлення кодується так:

                               (11001100) (1100011010100).         

                Твірна матриця даного (8, 13)- коду має вигляд

                                               .

Відповідь: (1011) (101111101); (11001100)  (1100011010100).

Приклад 2  Циклічний код заданий твірним поліномом g(x)=1+x+x3. Закодувати цим кодом комбінацію 0111. Виправити помилку в комбінаціях коду 0110111, 1101010.

Розв'язання

                Кількість інформаційних елементів заданого інформаційного повідомлення m= (0111) k=4. Кількість перевірних елементів коду визначається степенем твірного полінома g(x) – у даному випадку кількість перевірних елементів r=3. Тоді довжина кодового слова n=k+r=4+3=7.

                Подамо задану інформаційну послідовність m=(0111) у вигляді многочлена  m(x)=0x0+1x1+1x2+1x3=x+ x2+ x3.

                Закодуємо задане повідомлення за таким алгоритмом:

1) многочлен інформаційного повідомлення m(x) множимо на xn-k:

                               xn-k m(x)= x3 (x+x2+x3)= x4 +x5 +x6;

2) знаходимо остачу (x) від ділення добутку xn-k m(x) на твірний поліном коду g(x):

                x6 + x5 + x4              x3 +x +1

  +  x6 + x4 + x3       x3 +x2

          x5 + x3

      +  x5 + x3 + x2

            (x)= x2 = 0x0 +0x1 +1x2 (001);

3) кодовий поліном заданого інформаційного повідомлення знаходимо так:

                u(x)=(x)+xn-km(x)= x2+x4+x5+x6=0x0+0x1+1x2+0x3+1x4+

                +1x5 +1x6,

йому відповідає кодове слово u=(0010111).

                Даний лінійний завадостійкий код, твірний поліном якого g(x) має степінь r=n-k=3, здатний виправляти помилки кратності l=1.

                Виправимо помилку в комбінаціях коду 0110111, 1101010.

1) Прийнятій комбінації y= (0110111) відповідає многочлен y(x)= x+ x2 + x4 + x5+ x6.

                Перевіримо дану комбінацію на наявність помилки: для цього розділимо її многочлен на твірний поліном коду:

        x6 + x5 + x4   + x2 + x    x3 +x +1

                    + x6 + x4 + x3               x3 +x2 +1

                      x5+ x3 + x2 + x

         + x5+ x3 + x2

               s(x)= x – поліном остачі не дорівнює нулю, відтак, у заданій комбінації є помилка.

                Поліном остачі s(x)=x=0x0+1x1+0x2 має степінь n-k-1 – у даному випадку 2 (оскільки степінь многочлена дільника n-k=3), і йому відповідає вектор (010) 0.

                               Вага Хеммінга вектора остачі визначається кількістю одиниць в ньому: (010)= 1  l, де l=1 – кратність помилок, що виправляються кодом.

                               Вага остачі  ≤ l, тому виправлену комбінацію одержуємо додаванням многочленів прийнятої послідовності і остачі від її ділення на твірний поліном коду:

                               y(x) + s(x)= x6 + x5 + x4 + x2 + x + x= x6 + x5 + x4 + x2 =

                 = 0x0 + 0x1 + 1x2 + 0x3 + 1x4 +1x5 +1x6  (0010111).

                Одержана у такий спосіб комбінація декодируется так:

                               (0110111)  (0010111) (0111).

2) Прийнятій комбінації y= (1101010) відповідає многочлен y(x)= 1+ x+ x3+ x5.

                Перевіримо дану комбінацію на наявність помилки. Для цього розділимо її на твірний поліном коду:

                                x5+ x3 + x + 1     x3 +x +1

                   + x5+ x3 + x2          x2

s(x)= x2 + x + 1 0.

                Многочлен остачі s(x)=1+x+x2  визначає вектор s=(111), вага якогого (111)= 3 > l, де l – кратність помилок, що виправляються кодом.

                Вага остачі більше кратності помилок l=1, тому необхідно виконати циклічний зсув кодованої послідовності (1101010) на 1 розряд вправо: (1101010)  (0110101).

                Одержаній комбінації відповідає многочлен

                y(x)=0x0+1x1+1x2+0x3+1x4+ 0x5+ 1x6=x+x2+x4+x6.

                               Знайдемо остачу від ділення даного многочлена на твірний поліном коду:

     x6+ x4+ x2+ x     x3 +x +1

                  + x6+ x4+ x3        x3 +1

                     x3+ x2 + x

                  + x3 + x  + 1

                                    s(x)= x2 +1  (101).

                               Вага остачі (101)= 2 > l.

                Вага остачі більше l=1, тому знову виконуємо циклічний зсув кодованої послідовності на 1 розряд вправо: (0110101) (1011010).                Одержаній комбінації відповідає многочлен 

                               y(x)=1x0+0x1+1x2+1x3+0x4+1x5 +0x6 =1+x2+x3+x5.

                               Розділимо даний многочлен на твірний поліном коду:

     x5+ x3+ x2+ 1    x3 +x +1

                  + x5+ x3 + x2          x2 +1

                                    s(x)= 1  (100).

                               Вага вектора остачі (100)= 1  l – кратності помилок, що виправляються кодом. Таким чином одержуємо кодовий поліном u (x) додаванням останнього многочлена і многочлена його остачі від ділення на твірний поліном коду:

                u(x)= x5+ x3+ x2+ 1+ 1 =  x2+ x3+ x5= 0x0+ 0x1+ 1x2+ 1x3+ 

                +0x4+ 1x5+ 0x6  (0011010).

                Для того щоб одержати закодовану послідовність, виконуємо циклічний зсув кодового слова u (x) назад (вліво) на 2 розряди:

                               (0011010)  (1101000).

                               Таким чином, одержуємо виправлену кодову комбінацію u= (1101000), в якій контрольним сумам відповідають молодші розряди в лівій частині кодового слова.

                               Отже, повідомлення декодуємо так:

                                (1101010)  (1101000)  (1000).

                               Відповідь:  (0111) (0010111); (0110111)  (0010111) (0111),  (1101010) (1101000) (1110).

 

Приклад 3  Циклічний (4, 7)- код заданий твірним поліномом g(x)=1+x+x3. Визначити синдром виправлення поодиноких помилок цим кодом. Побудувати перевірну й твірну матриці коду. Декодувати повідомлення (1001110).

Розв'язання

                Синдром виправлення поодиноких помилок циклічним кодом визначається діленням многочлена вектора помилок на твірний поліном коду.

                               Припустимо, що кодується повідомлення m довжиною k символів – йому відповідає многочлен m(x) степеня k-1.

                               Кодовим словом на виході кодера буде послідовність u довжиною n символів, якій відповідає многочлен u(x) степеня n-1.

                               Позначимо через e= (e0, e1, …, en-1) – вектор помилок в двійковому каналі зв'язку; s=(s0, s1, …, sn-k-1) – кодовий синдром, що визначається вектором помилок.      

                               Вектор помилок подається многочленом вигляду e(x)=e0+e1x+…+en-1xn-1, а синдром – многочленом s(x)=s0+s1x+…+sn-k-1xn-k-1.

                               Знайдемо значення синдрому виправлення поодиноких помилок заданим циклічним (4, 7)- кодом:

е=(1000000)  e(x)=1,

 1    x3 +x +1

                       

                   s(x)= 1  (100);

е=(0100000)  e(x)=x,

 x     x3 +x +1

                       

                   s(x)= x  (010);

е=(0010000)  e(x)=x2,

 x2     x3 +x +1

     

                   s(x)= x2  (001);

e=(0001000)  e(x)=x3,

x3                 x3 +x +1

                  + x3 + x+ 1      1

                           x + 1

                   s(x)= 1+ x  (110);

e=(0000100)  e(x)=x4,

x4                  x3 +x +1

        + x4 +x2 +x      x

                         x2 + x

                     s(x)= x + x2  (011);

e=(0000010)  e(x)=x5,

 x5                  x3 + x +1

         +  x5 +x3 +x2    x2 +1

               x3+ x2

                      + x3+ x+ 1

                        x2+ x + 1

                     s(x)= 1+x+x2  (111);

e=(0000001)  e(x)=x6,

x6                   x3 + x + 1

        +x6 +x4 +x3      x3+ x + 1

                 x4 + x3

                        + x4 + x2 + x

                                        x3 + x2 +x

                                     +x3 + x + 1

                                               x2 + 1

                     s(x)= 1+x2  (101).

                               Знайдені комбінації синдрому є стовпцями перевірної матриці:

.

   

                                                             

               

З перевірної матриці знаходимо твірну матрицю коду

.

 

 

                Кодове слово утворюється послідовністю u=(0, 1, 2, m0, m1, m2,m3), де 0, 1, 2 – перевірочні символи.

                Декодуємо задане повідомлення y=(1001110).

                Даній послідовності відповідає поліном

                y(x)=1x0+ 0x1+ 0x2+ 1x3+ 1x4+ 1x5+ 0x6=1+x3+ x4+ x5.

                Скористаємося алгоритмом декодування циклічних кодів:

Знайдемо остачу від ділення многочлена прийнятої комбінації на твірний поліном коду і тим самим перевіримо її на наявність помилки:

       x5+ x4+ x3+ 1    x3 +x +1

                    + x5+ x3+ x2           x2 +x

                                  x4+ x2+ 1

                   + x4+ x2+ x

                                         x+ 1

                     s(x)= 1+ x  (110).

                Ненульова остача s(x) свідчить про наявність помилки в прийнятій комбінації.

                Вага остачі (110)= 2 > l, де l= 1 – кратність помилок, що виправляються кодом, отже, необхідно виконати циклічний зсув кодованої послідовності на 1 розряд вправо:

                (1001110)  (0100111) y(x)=0x0+ 1x1+ 0x2+ 0x3+

                +1x4+ 1x5+ 1x6= x+ x4+ x5+ x6.

Розділимо отриманий у результаті циклічного зсуву многочлен на твірний поліном коду:

                     x6+ x5+ x4+ x     x3 +x +1

        +x6+ x4+ x3            x3 +x2

                                     x5 + x3 + x

                   +x5+ x3+ x2

                                          x2 +x

                     s(x)= x+ x2  (011).

                Вага остачі (011)= 2 > 1, отже, виконуємо циклічний зсув кодованої послідовності на 1 розряд вправо:

                (0100111) (1010011) y(x)=1x0 +0x1+1x2+ 0x3 + + 0x4+ 1x5+ 1x6= 1+ x2+ x5 + x6.

Розділимо отриманий у результаті циклічного зсуву многочлен на твірний поліном коду:

     x6+ x5+ x2+ 1      x3 +x +1

        +x6+ x4+ x3             x3 +x2+x

                  x5+ x4+ x3+ x2+ 1

     +x5+ x3+ x2

                                     x4+ 1

         +x4+ x2+ x

             x2+ x+ 1

                s(x)= 1+ x+ x2  (111).

                Вага остачі (111)= 3 > 1, знову виконуємо циклічний зсув кодованої послідовності й ділення її многочлена на твірний поліном коду:  (1010011)  (1101001) 

 y(x)=1x0+ 1x1+ 0x2+ 1x3+ 0x4+ 0x5+ 1x6= 1+ x+ x3+ x6.

Розділимо многочлен циклічно зсуненої послідовності на твірний поліном коду:

   x6 + x3+ x+ 1     x3+ x+ 1

     + x6+ x4 + x3           x3 +x

                       x4+ x +1

                    + x4+ x2+ x

                                            x2+ 1

                        s(x)= 1+ x2  (101).

                Вага остачі (101)= 2 > 1, виконуємо циклічний зсув й ділення на твірний поліном: (1101001)  (1110100)  y(x)= 1x0+ 1x1+ 1x2+ 0x3+ 1x4+ 0x5+ 0x6= 1+ x + x2 + x4.

Знову розділимо многочлен послідовності, отриманої у результаті останнього циклічного зсуву, на твірний поліном:

       x4+ x2+ x+1     x3 +x +1

          + x4 + x2 + x          x

                                    1

                         s(x)=1  (100).

                               Вага отриманої остачі (100)= 1  1, виконуємо дії з виправлення помилки.

                Для цього додаємо до останнього циклічно зсунутого многочлена його остачу від ділення на твірний поліном:

                x4+ x2+ x+ 1+ 1 = x+ x2+ x4  (0110100).

                               Виконуємо циклічний зсув отриманої кодової комбінації у зворотному напрямку на 4 розряди вліво:

                (0110100)  (1000110).

                Одержуємо виправлену кодову комбінацію u=(1000110).

                Декодуємо передану послідовність, вилучивши перевірні елементи в лівій частині кодового слова:       (1000110)(0110).