Лабораторна робота №19-20

Тема: Двійкові циклічні коди

Мета: вивчити визначення штрихового коду. Його призначення. Визначити справжність товарів за допомогою штрих коду.

 

Теоретичні відомості

 

Подання кодових комбінацій у циклічних кодах виконують у вигляді поліномів від формальної змінної  х, що дозволяє звести дії над кодовими комбінаціями до дій над поліномами. Так, сума двох двій-кових поліномів виконується додаванням за модулем 2 ко­ефіцієнтів за рівних степенів змінної  х. Наприклад, отримаємо суму за модулем 2 двох поліномів: ( х 4 Å х 3   х Å1 ) Å x 3 Å x 2 Å ) = x 4 Å x 2 Å 1. Множення виконується за звичай­ними правилами множення степеневих функцій, але коефіцієнти однакових степенів додаються за модулем 2. Так, ( x 4 Å x 3 Å x  Å 1 ) x Å 1 )  =  x 5 Å x 4 Å x 2 Å x Å Å x 3 Å  x Å 1 =  =  x 5 Å  x 3 Å  x 2 Å 1.

Ділення також виконується як звичайне ділення поліномів, при цьому операція віднімання співпадає з операцією додавання  Å. Наприклад,   x 5 Å x 3 Å  x 2  Å 1 ) / ( x Å 1 )  =  х 4 Å  х 3  Å х  Å 1.

До циклічних належать лінійні блокові ( n, ) - коди, у яких циклічний зсув елементів будь-якої дозволеної комбінації призводить до виникнення також дозволеної комбінації, що належить до даного коду. Така циклічна перестановка з’являється завдяки помноженню полінома даної комбінації на  x . Щоб степінь полінома не перевищував  n – 1, член  n замінюється одиницею.

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

Циклічні коди з  d min  = 3 . Розрізняють алгебраїчні та матричні способи побудови циклічних кодів. Існують три алгебраїчні спо­соби  побудови кодових комбінацій циклічного коду, які випливають з виразу

                              ,                              ( 9.1 )

де  r – кількість перевірочних розрядів у комбінації циклічного коду; Q ( x ) – поліном первинної кодової комбінації; P x ) – твірний полі-ном; C ( x ) – частка від ділення того степеня, що і Q ( x );  R ( x ) – ос­тача від ділення, яка має степінь, не більший за  r – 1. З виразу  ( 9.1 )  можна одержати три способи побудови циклічного коду :

F( x )  =  x r Q ( x Å R ( x ) ;

F( x )  =  C ( x P ( x ) ;

F( x )  =  Q ( x P ( x ) ,

де  F ( x )  –  комбінація циклічного коду.

Перші два способи дають один і той же роздільний циклічний код, тобто  F( x )  =  F( x ), у якому розташування інформаційних і перевірочних елементів буде підпорядковано правилу:  k  старших роз-рядів комбінації  –  інформаційні, решта  n – r  розрядів  –  пере-вірочні. Третій спосіб використовується для побудови нероздільного циклічного коду, де інформаційні і перевірочні елементи в комбінаціях не відокремлені одні від одних, що ускладнює процес декодування.

Деякі твірні поліноми для циклічних кодів наведені у табл. 9.1.

                                                                                   

Таблиця 9.1

Кількість

перевірочних

еле­ментів  r

 

Твірний    поліном    P ( x )

Двійковий

за­пис

полінома

3

x3x1

1011

3

x3x21

1101

4

x4x1

10011

4

x4x31

11001

5

x5x21

100101

5

x5x31

101001

5

x5x3x2x1

101111

5

x5x4x2x1

110111

6

x6x5x41

1110001

8

x8x7x6x5x2x1

111100111

9

x9x5x31

1000101001

Очевидно, що  F(x) повинен  ділитися на  P(x)  без остачі. На цьому і грунтується перевірка кодової комбінації на наявність помилок при прийомі. Якщо прийнята комбінація  F*(x)  ділиться на  P(x)  без ос­тачі, вона визнається безпомилковою. Якщо після ділення залишається ненульова остача, це свідчить про наявність помилки у прийнятій комбінації циклічного коду.

Для виправлення помилки можна скористатися методом гіпотез. Цей метод грунтується на послідовній побудові гіпотез про помилки у молодшому розряді прийнятої кодової комбінації, потім, якщо гіпотеза не підтверджується, у другому розряді і так далі, поки гіпотеза не підтвердиться і остача від ділення  F*(x)ÅE(x), де E(x) – поліном по­милки, на  P(x)  не дасть нульовий результат. Це означає, що F(x) = F*(x)ÅE(x)  і  помилка виправлена.

Розрізняють три матричні способи одержання циклічного коду, два з яких грунтуються на побудові твірної матриці, і один – пе­ревірочної.

За першим способом будується твірна матриця

G   .

За другим способом також будується твірна матриця циклічного коду, але на відміну від першого, у якості рядків такої матриці викори­стовують усі можливі комбінації коду, що мають тільки одну одиницю в інформаційній частині; перевірочні елементи для таких комбінацій можна ви­значити за допомогою першого алгеб­раїчного способу побудови коду.

Третій матричний спосіб побудови циклічного коду грун­тується на одержанні перевірочної матриці за допомогою викори­стання перевірочного полінома, який визначається за формулою:

Н(х)=(xn1)/P(x),

де  n=2r–1. При цьому, перевірочна матриця має вигляд:

H  =     .

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

Циклічні  коди з  d min 4  можуть виявляти одно-, дво- і три­кратні помилки. Для збільшення кодової відстані до d min = 4 кількість перевірочних елементів у кодовій комбінації такого коду має бути на один більшою, ніж у коді  з  d min = 3. Твірний поліном  P(x)(d=4) такого коду визначається як добуток твірного поліному  P(x)(d=3) циклічного коду,  який має  d min = 3,  на поліном  xÅ1), тобто :

P(x)(d=4)= P(x)(d=3)(x1).

Процедура кодування  і  декоду­вання залишається такою ж,  як і для циклічного коду  з  d min = 3.

Вкорочені  циклічні  коди  будуються за аналогією з двійковими груповими кодами на основі побудови твірної або перевірочної матриць  ( див. розділ  8 ).

Коди Боуза-Чоудхурі-Хоквінгема  ( БЧХ ) є різновидом циклічних кодів з кодовою відстанню  d min  3. Коди БЧХ дозволяють виявляти і виправляти будь-яку кількість помилок у залежності від мінімальної кодової відстані. При кодуванні задаються кількістю по­милок, яку слід виправити, або кодовою відстанню і загальною кількістю елементів у кодовій комбінації n. Кількість інформаційних елементів  k  та перевірочних елементів  r  визначається при побудові коду.

Так  довжина кодової комбінації  n  у  кодах  БЧХ  визначається  з виразів  [24]:

   = 2h–1,   або   = (2h–1)/g,            ( 9.2 )

де  h – ціле число;   g  – непарне додатне число, при діленні на яке одержуємо  n  цілим непарним числом. Таким чином,  n  може бути тільки непарним числом. Тобто, керуючись виразом ( 9.2 ), визначаємо, що кількість елементів у комбінаціях коду БЧХ може дорівнювати 3, 7, 15, 31, 63, 127, 255, 511, 1023  тощо.

Кількість перевірочних елементів коду відповідає співвідношенню

£  h d min – 1 ) / 2 ,                                   ( 9.3 )

звідки кількість інформаційних елементів

         k ³ ( 2 h – 1 ) – h d min – 1) / 2 .                         ( 9.4 )

Твірний поліном коду БЧХ визначається як добуток так званих мінімальних поліномів  Мi(x),  із непарними індексами:

           P(x) = M1(x)M3(x)...MV(x),                       ( 9.5 )

де   =  d min – 2 . Можна пересвідчитись, що кількість мінімальних поліномів  у  добутку  ( 9.5 )  дорівнює максимальній кількості  s  помилок,  які  гарантовано  виправляються  кодом .

У таблиці  9.2  наведені основні параметри деяких кодів  БЧХ .

                                                                       Таблиця  9.2

n

k

r

d min

Твірний  поліном  Р8

7

4

3

3

13

15

11

4

3

23

 

7

8

5

721

 

5

10

7

2467

31

26

5

3

45

 

21

10

5

3551

 

16

15

7

107657

 

11

20

11

5423325

 

6

25

15

313365047

63

57

6

3

103

 

51

12

5

12471

 

45

18

7

1701317

 

39

24

9

166623567

 

36

27

11

1033500423

 

30

33

13

1574641656547

 

24

39

15

17323260404441

 

18

45

21

1363026512351725

 

Подані в таблиці параметри були визначені у відповідності з вик­ладеною вище методикою. Для зручності запису твірні поліноми Р(х) подані у вісімковій системі числення  P8 ) . Щоб одержати твірний поліном у звичайному вигляді, тобто у тій формі, яка використовується для побудови кодів БЧХ, треба перевести кожну вісімкову цифру  у  двійковий трибіт. Так, наприклад,  Р8 =  45  запишеться двійковими числами: 4 – 100  та  5 – 101. Таким чином одержуємо двійкове число 100101, яке запи­сується поліномом    Р(х) = x5x21.

Як було показано вище, коди БЧХ мають непарне значення мінімальної кодової відстані  d min. Для того, щоб збільшити d min на оди­ницю, досить помножити твірний поліном коду БЧХ на двочлен (х1).

Кодування у кодах БЧХ виконується так само, як і у звичай­них циклічних кодах, у тому числі і за допомогою матричних способів ( див. вище ). Декодування кодів БЧХ ( виявлення та виправлення поми­лок ) також може виконуватися з використанням методики, викладеної для циклічних кодів  з  d min < 5.

Приклади розв’язання завдань

Приклад 1.

Закодувати двійковим циклічним кодом, що виправляє одно­кратні помилки, кодову комбінацію двійкового простого коду 1110  та показати процес виправлення будь-якої однократної помилки в одер­жаній комбінації циклічного коду. Визначити надмірність коду.

Розв’язання.  Для того, щоб закодувати комбінацію простого коду циклічним кодом, необхідно вибрати твірний поліном. Степінь твірного поліному Р(х)  визначається кількістю перевірочних еле­мен-тів  r  у комбінації циклічного коду, а величина  r  при d min = 3 ви­зна-чається  з  виразу  2r–1 n. Тобто, при  = 4  маємо  = 3. Таким чином з табл. 9.1 вибираємо  поліном степені  3:     Р(х)=x3ÅxÅ1.

Виконуємо кодування комбінації двійкового простого коду 1110. Для цього

– записуємо її у вигляді полінома:  Q(x)=x3Åx2Åx;

– помножимо   Q(xна   xr;  оскільки   r  = 3,   то    Q(x)x3 =

(x3Åx2Åx)xx6Åx5Åx4;

– поділимо  Q(x)x3  на  P(x) з метою визначення остачі  R(x), ко­ефіцієнти при степенях  x  якого є перевірочними елементами комбінації циклічного коду:

 

Å

 x6Åx5Åx4

 

   x3ÅxÅ1

 x6Åx4Åx3

 

   x3Åx2

           Å

 x5Åx3

 

 

 x5Åx3Åx2

 

 

 

          x2

 

                 .

 

Одержуємо остачу  R(x) = x2, якій відповідає трирозрядний век­тор  = 3 )  – 100 ;  додаємо  остачу  R(x)  до  Q(x)x3 і  отримуємо кодову комбінацію двійкового циклічного коду  F(x)= =Q(x)x3ÅR(x)= x6Åx5Åх4Åx2 ®  F = 1110100.

Покажемо процес виправлення  однократної помилки. Для цього припустимо, що при передачі виникла однократна помилка, поліном та век­тор якої відповідно E(x) x3 та  0001000. Тоді поліном F*(xприйнятої  комбінації  F*(x) = F(x)ÅE(x) = x6Åx5Åx4ÅÅx3Åx2  ®  1111100.

Декодер виконує перевірочне ділення F*(x) на той же твірний поліном P(x), який був використаний  при  кодуванні:


 

 

   Å

x6Åx5Åx4Åx3Åx2

 x3ÅxÅ1

x6Åx4Åx3

 x3Åx2Å1

 

   Å

x5Åx2

 

 

x5Åx3Åx2

 

 

 Å

x3

 

 

x3ÅxÅ1

 

 

 

     xÅ1

                    .

 

Отже, остача  R(x) =  xÅ1 або  R  =  011.   

Оскільки остача від ділення не дорівнює нулю, робимо висно­вок про наявність помилки у прийнятій комбінації  F*(x).

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

Крок 1. Висуваємо гіпотезу про помилку у молодшому роз­ряді комбінації циклічного коду  F*(x), тобто вважаємо, що поліном та вектор помилки відповідно E1(x) = 1  та  E10000001. Беремо суму за   модулем  2  F*(x)ÅE1(x):

    F*(x)ÅE1(x) = (x6Åx5Åх4Åx3Åx2)Å1= x6Åx5Åх4Åx3Åx2Å1;

ділимо отриману суму  на P(x) з метою підтвердження ( у разі нульової остачі ) або спростування  ( у разі ненульової остачі )  висунутої гіпотези:

      Å   

x6Åx5Åx4Åx3Åx2Å1

x3ÅxÅ1

x6Åx4Åx3

x3Åx2Å1

 

   Å

x5Åx2Å1

 

 

x5Åx3Åx2

 

 

         Å

x3Å1

 

 

x3ÅxÅ1

 

 

 

     x

                          .

Остача  R(x) = x,  тобто  R(x) ¹ 0, і гіпотеза  відхиляється.

Крок 2 . Висуваємо гіпотезу про помилку у другому розряді F*(x), тобто вважаємо, що  E2(x) = x ® E2  =  0000010. Беремо суму за  модулем  2  F*(x)ÅE2(x):

F*(x)E2(x) = (x6Åx5Åx4Åx3Åx2)Åx = x6Åx5Åx4Åx3Åx2Åx;

ділимо цю суму на  P(x)  з  метою підтвердження або спростування гі-потези:

      Å   

x6Åx5Åx4Åx3Åx2Åx

x3ÅxÅ1

x6Åx4Åx3

x3Åx2Å1

 

   Å

x5Åx2Åx

 

 

x5Åx3Åx2

 

 

         Å

x3Åx

 

 

x3ÅxÅ1

 

 

 

         1

                          .

Остача  R(x) = 1,  тобто  R(x)0,  і  гіпотеза  відхиляється.

Крок 3. Висуваємо гіпотезу про помилку у третьому розряді F*(x), тобто вважаємо, що E3(x) = x2 ®  E=  0000100. Беремо суму

му за  модулем  2   F*(x)ÅE3(x):

  F*(x)ÅE3(x) = (x6Åx5Åx4Åx3Åx2)Åxx6Åx5Åx4Åx3;

ділимо цю сумму  на  P(x)  з  метою підтвердження або спростування гіпотези:

      Å   

x6Åx5Åx4Åx3

 x3ÅxÅ1

x6Åx4Åx3

 x3Åx2Å1

 

   Å

x5

 

 

x5Åx3Åx2

 

 

         Å

x3Åx2

 

 

x3ÅxÅ1

 

 

 

     x2ÅxÅ1

                  .

Остача  R(x) = x2ÅxÅ1, тобто  R(x)0,  і  гіпотеза  відхиляється.

Крок 4. Висуваємо гіпотезу про помилку у четвертому роз­ряді F*(x), тобто вважаємо, що E4(x) = x3 ®  E=  0001000. Беремо суму за  модулем  2  F*(x)ÅE4(x):

   F*(x)ÅE4(x) = (x6Åx5Åx4Åx3Åx2)x= x6Åx5Åx4Åx2;

ділимо отриману суму  на  P(x)  з  метою підтвердження або спростування гіпотези:

    Å

 x6Åx5Åx4Åx2

 

   x3ÅxÅ1

 x6Åx4Åx3

 

   x3Åx2

           Å

 x5Åx3Åx2

 

 

 x5Åx3Åx2

 

 

 

           0

 

                  .

Остача  R(x) = 0, тобто помилка дійсно була у четвертому розряді, а вихідна комбінація циклічного коду має вигляд:

 F(x)=F*(x)ÅE4(x)= x6Åx5Åх4Åx2  ®  F  = 1110100.

Надмірність  коду   n  = 3 / 7.

Приклад 2

Закодувати двійковим циклічним кодом, що виправляє одно­кратні помилки, кодову комбінацію двійкового простого коду Q(x) = x5 Å  x2  і виправити будь-яку однократну помилку в одержаній комбінації циклічного коду. Визначити надмірність коду.

Розв’язання. Щоб закодувати задану кодову комбінацію Q(x) = x5Åx2  = 100100 ) циклічним кодом, що виправляє однократні помилки  d min = 3 )   необхідно вибрати твірний поліном. Степінь твірного поліному P(x) визначається кількістю перевірочних елементів r, яку визначаємо з виразу 2r–1n ( для d min = 3 ). При = 6  одержуємо  r = 4  та  вибираємо з таблиці 9.1 поліном четвертого степеня:  P(x) = x4ÅxÅ1.

Виконаємо кодування первинної кодової комбінації Q(x) = x5Åx2,  для чого знайдемо остачу C(x)  від  ділення  Q(x)x4  на P(x),  а  потім  помножимо її  на  P(x).Маємо

           Q(x)x= (x5Åx2)xx9Åx6.

Поділимо отриманий  добуток  на P(x) з метою визначення частки  C(x) від  ділення:

    Å

 x9Åx6

 

   x4ÅxÅ1

 x9Åx6Åx5

 

   x5Åx

           Å

 x5

 

 

 x5Åx2Åx

 

 

 

      x2Åx     

 

                  .

 

Тобто C(x) = x5Åx.Помножимо C(x) на P(x) і одержимо ко-дову комбінацію циклічного  коду:

 F(x)=C(x)P(x)=(x5Åx)(x4ÅxÅ1)=x9Åx6Åx2Åx,

або  у  двійковому  вигляді  = 1001000110.

Виправляємо однократну помилку.

Припустимо, що при передачі по каналу зв’язку виникла од­нократна помилка, поліном якої  E(x) = 1. Тоді поліном прийнятої кодової комбінації циклічного коду   F*(x) = x9Åx6Åx2ÅxÅ1.

  Декодер виконує перевірочне ділення  F*(x)  на твірний поліном  P(x):

    Å

 x9Åx6Åx2ÅxÅ1

 

   x4ÅxÅ1

 x9Åx6Åx5

 

   x5Åx

            Å

 x5Åx2ÅxÅ1

 

 

 x5Åx2Åx

 

 

 

              1

 

                   .

 

Тобто   R(x) = 1 ¹ 0.Це вказує на наявність помилки  у прийнятій кодовій комбінації.

Для визначення місця помилки скористуємося методом гіпотез, першим кроком якої є  гіпотеза про наявність помилки у мо­лодшому розряді прийнятої кодової комбінації F*(x), тобто вважаємо, що поліном та вектор помилки відповідно E1(x) = 1 та  E1=  0000000001. Визначаємо суму за модулем   2  F*(x)E1(x) та ділимо цю суму на Р(х) з метою підтвердження або спростування гіпотези:

F*(x)E1(x) = (x9Åx6Åx2ÅxÅ1)Å1 = x9Åx6Åx2Åx;

 

    Å

 x9Åx6Åx2Åx

 

   x4ÅxÅ1

 x9Åx6Åx5

 

   x5Åx

           Å

 x5Åx2Åx

 

 

 x5Åx2Åx

 

 

 

           0     

 

               .

 

  Тобто R(x) = 0, що вказує на те, що помилка дійсно була у першому розряді.

 

 

Таким чином, вихідна комбінація циклічного коду F(x) = x9Åx6Åx2Åx  ®   F  = 1001000110.

Надмірність  коду   R  = n  =  4 / 10  =  2 / 5.

 

Приклад 3

Знайти твірний поліном Р(х) двійкового коду БЧХ, здатного виправляти трикратні помилки та призначеного для передачі символів деякого алфавіту, потужність якого дорівнює 32.

Розв’язання. Мінімальна кодова відстань для коду БЧХ, здат­ного виправляти трикратні помилки,  d min = 2 + 1 = 2 ´ 3 + 1 = 7. Для пере­дачі символів алфавіту потужністю 32 повідомлень достатньо мати  = 5  двійкових  інформаційних  символів  (2= 32).

Для визначення твірного полінома Р(х) коду БЧХ , що має d min = 7  та  = 5, скористаємося таблицею 9.2. Бачимо, що мінімальна довжина коду БЧХ з заданими параметрами  = 15  ( = 5, = 10, d min  = 7 ),  для якого твірний поліном у вісімковій системі числення P8  2467, або у двійковій системі числення P2  = 010100110111. Таким чином твірний поліном коду БЧХ буде мати вигляд P(x) = x10Åx8Åx5Åx4Åx2ÅxÅ1.

Приклад 4

Закодувати двійковим кодом БЧХ , що виявляє до шести по­милок та має п’ять інформаційних символів, кодову комбінацію двійкового простого коду 10101. Показати процес виявлення шести помилок. Визначити надмірність коду.

Розв’язання. Поліном, який відповідає комбінації  10101 первинного коду, має вигляд  Q(x) = x4Åx2Å1. Для того,  щоб  код  БЧХ міг виявляти шість помилок, він повинен мати  d min =  + 1 = 6 + 1 = 7. Тому, користуючись таблицею 9.2, визначаємо параметри коду БЧХ, який має здатність виявляти шість помилок: = 15, = 5, = 10, P2467. Переводимо значення твірного поліному, що записане у вісімковій системі числення, у двійкову  P= 010100110111,  і  далі за-писуємо його у вигляді поліному:  P(x) = x10Åx8Åx5Åx4Åx2ÅxÅ1.

Закодуємо задану комбінацію двійкового простого коду кодом БЧХ ,  для чого :

–  помножимо Q(x) на хr:  (x4Åx2Å1) x10 = x14Åx12Åx10;

–  поділимо  Q(x) x10  на  P(x)  і  визначимо остачу  R(x):

 

Å

 x14 Åx12 Åx10

 

  x10 Åx8Åx5Åx4Åx2ÅxÅ1

 x14Åx12 Åx9Åx8Åx6Åx5Åx4

 

    x4Å1

    Å

 x10Åx9Åx8Åx6Åx5Åx4

 

 

 x10Åx8Åx5Åx4Åx2ÅxÅ1

 

 

 

       x9Åx6Åx2ÅxÅ1

 

                              ;

 

тобто остача   R(x)=x9Åx6Åx2ÅxÅ1;

–  визначаємо суму  Q(x)x10 ÅR(x)  і одержуємо поліном кодової комбінаціє коду БЧХ :  F(x) = x14Åx12Åx10Åx9Åx6Åx2ÅxÅ1; йому  відповідає  комбінація 101011001000111.

Покажемо процес виявлення шести помилок. Припустимо, що при передачі виникли  6 помилок. Нехай поліном шестикратної помилки E(x) = x12 Åx10 Åx9Åx6Åx5Åx2. Тоді поліном прий­нятої комбінації коду  БЧХ :   F*(x) =  x14 Åx5ÅxÅ1.

  Для виявлення помилок декодер виконує перевірочне ділення прийнятої комбінації  F*(x)  коду БЧХ на той же твірний поліном  P(x), який був використаний при кодуванні:

Å

 x14Åx5ÅxÅ1

 

  x10Åx8Åx5Åx4Åx2ÅxÅ1

 x14Åx12Åx9Åx8Åx6Åx5Åx4

 

    x4Åx2Å1

      Å

 x12Åx9Åx8Åx6Åx4ÅxÅ1

 

 

 x12Åx10Åx7Åx6Åx4Åx3Åx2

 

 

          Å

   x10Åx9Åx8x7Åx3Åx2ÅxÅ1

 

                             

   x10Åx8Åx5Åx4Åx2ÅxÅ1

 

 

 

         x9Åx7Åx5Åx4Åx3

 

                   .

 

Остача від ділення R(x) ¹ 0, що вказує на наявність помилок у прийнятій кодовій комбінації F*(x). Здатність побудованого коду БЧХ  виправляти помилки ( d min = 7 ) не дозволяє виправити ці шість помилок.

Надмірність коду   =  n  =  10 / 15  =  2 / 3.

 


 

Завдання на лабораторну роботу

Завдання 1.

Закодувати двійковим циклічним кодом з  d min = 3, що виправ­ляє однократні помилки, комбінацію двійкового простого коду Q(x) довжиною  k  інформаційних елементів згідно з варіантом, поданим в таблиці 9.3.1. Твірний поліном P(x)  визначити з таблиці 9.1. Показати процес виправлення будь-якої однократної помилки  і  визначити надмірність коду.

Таблиця 9.3.1

    варіанта

k

Поліном  комбінації  двійкового

простого  коду  Q ( x )

1

4

x2ÅxÅ1

2

5

x4Åx2Åx

3

6

x5Åx2Å1

4

7

x6ÅxÅ1

5

8

x7Åx6Åx4Åx

6

9

x7Åx5Åx3Å1

7

10

x9Åx6Åx2ÅxÅ1

8

11

x10Åx9Åx8Åx4Åx

9

12

x11Åx10Åx7Åx6Åx3Å1

10

14

x13Åx12Åx10Åx9Åx3Åx2

Завдання 2.

Закодувати двійковим циклічним кодом, що виявляє три­кратні помилки ( d min = 4 ), кодову комбінацію двійкового простого коду  Q(x)  довжиною  k  інформаційних елементів згідно з варіантом, пода­ним в таблиці  9.3.2. Твірний поліном  P(x)  визначити з таблиці 9.1. Показати процес виявлення будь-якої  трикратної  помилки  і  визна­чити надмірність коду.

Таблиця 9.3.2

   варіанта

k

Поліном  комбінації  двійкового

простого  коду  Q ( x )

1

4

  x2ÅxÅ1

2

5

x4Åx2Åx

3

6

x5Åx4Åx2Å1

4

7

x6Åx4ÅxÅ1

5

8

x7Åx6Åx3Åx

6

9

x8Åx3ÅxÅ1

7

10

x9Åx6Åx2ÅxÅ1

8

11

x10Åx9Åx5Åx2Å1

9

12

x11Åx8Åx7Åx3Åx2

10

14

x13Åx11Åx10Åx7Åx3Åx

Завдання 3.

Побудувати твірну матрицю двійкового циклічного коду з мінімальною кодовою відстанню  d min = 3  ( здатного виправляти однократні помилки ),  твірний поліном  P(x)  якого  та  довжина  n  вибираються  згідно  з  варіантом,  поданим  в  таблиці  9.3.3.          

Таблиця 9.3.3

варіанта

Довжина

коду  n

Твірний  поліном  циклічного  коду  P(x)

1

7

x3Åx2Å1

2

9

x4ÅxÅ1

3

15

x4Åx3Å1

4

16

x5Åx2Å1

5

17

x5Åx3Åx2ÅxÅ1

Завдання 4.

Побудувати перевірочну матрицю двійкового циклічного коду з мінімальною кодовою відстанню  d min = 3  ( здатного виправляти однократні помилки ),  твірний поліном  P(x)  якого  та  довжина  n  вибираються  згідно  з  варіантом,  поданим  в  таблиці  9.3.4.

Таблиця 9.3.4

варіанта

Довжина коду  n

Твірний  поліном  циклічного коду  P(x)

1

7

x3ÅxÅ1

2

10

x4ÅxÅ1

3

12

x4Åx3Å1

4

18

x5Åx3Å1

5

20

x5Åx4Åx2ÅxÅ1

 

Завдання 5.

Згідно з варіантом, поданим в таблиці 9.3.5, знайти твірний поліном  P(x)  двійкового коду БЧХ , який має N0  дозволених кодових комбінацій та здатен виправляти по­милки кратності  s. Визначити надмірність коду.

 

Таблиця 9.3.5

   варіанта

Кратність помилки ,  s

N0

1

2

128

2

2

100

3

3

32

4

5

2048

5

7

64

Завдання 6.

Згідно з варіантом, поданим в таблиці 9.3.6, закодувати ко­дову комбінацію двійкового простого коду, якій відповідає поліном  Q(x),  двійковим кодом БЧХ , що виявляє  s  помилок. Показати процес виявлення будь-якої помилки кратності  s  і визначити надмірність коду.

Таблиця 9.3.6

   варіанта

Кратність  s  помилок,  що  виявляються

Поліном  комбінації  двійкового  простого  коду  Q ( x )

1

4

x6ÅxÅ1

2

6

x4Åx2Åx

3

4

x20Åx4Åx2Å1

4

6

x15Åx8ÅxÅ1

5

10

x10Åx6Åx3Åx

 

Після виконання завдань оформити та здати звіт викладачу.