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

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

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

 

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

 

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

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

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

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

Циклічні коди з  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 – k = r  розрядів  –  пере-вірочні. Третій спосіб використовується для побудови нероздільного циклічного коду, де інформаційні і перевірочні елементи в комбінаціях не відокремлені одні від одних, що ускладнює процес декодування.

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

                                                                                   

Таблиця 9.1

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

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

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

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

G  =   .

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

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

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

де  n=2^r–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]:

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

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

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

r £  h ( d _min – 1 ) / 2 ,                                   ( 9.3 )

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

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

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

           P(x) = M₁(x)M₃(x)...M_V(x),                       ( 9.5 )

де  V  =  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

 

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

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

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

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

Приклад 1.

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

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

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

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

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

(x³Åx²Åx)x³ = x⁶Åx⁵Åx⁴;

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

 

Å	x6Åx5Åx4			x3ÅxÅ1
	x6Åx4Åx3			x3Åx2
Å		x5Åx3
		x5Åx3Åx2
		x2		.

 

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

Покажемо процес виправлення  однократної помилки. Для цього припустимо, що при передачі виникла однократна помилка, поліном та век­тор якої відповідно E(x) = x³ та  0001000. Тоді поліном F^*(x) прийнятої  комбінації  F^*(x) = F(x)ÅE(x) = x⁶Åx⁵Åx⁴ÅÅx³Åx²  ®  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), тобто вважаємо, що поліном та вектор помилки відповідно E₁(x) = 1  та  E₁= 0000001. Беремо суму за   модулем  2  F^*(x)ÅE₁(x):

    F^*(x)ÅE₁(x) = (x⁶Åx⁵Åх⁴Åx³Åx²)Å1= x⁶Åx⁵Åх⁴Åx³Åx²Å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), тобто вважаємо, що  E₂(x) = x ® E₂  =  0000010. Беремо суму за  модулем  2  F^*(x)ÅE₂(x):

F^*(x)E₂(x) = (x⁶Åx⁵Åx⁴Åx³Åx²)Åx = x⁶Åx⁵Åx⁴Åx³Åx²Å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), тобто вважаємо, що E₃(x) = x² ®  E₃ =  0000100. Беремо суму

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

  F^*(x)ÅE₃(x) = (x⁶Åx⁵Åx⁴Åx³Åx²)Åx² = x⁶Åx⁵Åx⁴Åx³;

ділимо цю сумму  на  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) = x²ÅxÅ1, тобто  R(x)0,  і  гіпотеза  відхиляється.

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

   F^*(x)ÅE₄(x) = (x⁶Åx⁵Åx⁴Åx³Åx²)x³ = x⁶Åx⁵Åx⁴Åx²;

ділимо отриману суму  на  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)ÅE₄(x)= x⁶Åx⁵Åх⁴Åx²  ®  F  = 1110100.

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

Приклад 2

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

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

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

           Q(x)x⁴ = (x⁵Åx²)x⁴ = x⁹Åx⁶.

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

Å	x9Åx6			x4ÅxÅ1
	x9Åx6Åx5			x5Åx
Å		x5
		x5Åx2Åx
		x2Åx		.

 

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

 F(x)=C(x)P(x)=(x⁵Åx)(x⁴ÅxÅ1)=x⁹Åx⁶Åx²Åx,

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

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

Припустимо, що при передачі по каналу зв’язку виникла од­нократна помилка, поліном якої  E(x) = 1. Тоді поліном прийнятої кодової комбінації циклічного коду   F^*(x) = x⁹Åx⁶Åx²Å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), тобто вважаємо, що поліном та вектор помилки відповідно E₁(x) = 1 та  E₁=  0000000001. Визначаємо суму за модулем   2  F^*(x)E₁(x) та ділимо цю суму на Р(х) з метою підтвердження або спростування гіпотези:

F^*(x)E₁(x) = (x⁹Åx⁶Åx²ÅxÅ1)Å1 = x⁹Åx⁶Åx²Å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) = x⁹Åx⁶Åx²Åx  ®   F  = 1001000110.

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

 

Приклад 3

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

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

Для визначення твірного полінома Р(х) коду БЧХ , що має d _min = 7  та  k = 5, скористаємося таблицею 9.2. Бачимо, що мінімальна довжина коду БЧХ з заданими параметрами  n = 15  ( k = 5, r = 10, d _min  = 7 ),  для якого твірний поліном у вісімковій системі числення P₈  = 2467, або у двійковій системі числення P₂  = 010100110111. Таким чином твірний поліном коду БЧХ буде мати вигляд P(x) = x¹⁰Åx⁸Åx⁵Åx⁴Åx²ÅxÅ1.

Приклад 4

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

Розв’язання. Поліном, який відповідає комбінації  10101 первинного коду, має вигляд  Q(x) = x⁴Åx²Å1. Для того,  щоб  код  БЧХ міг виявляти шість помилок, він повинен мати  d _min =  s + 1 = 6 + 1 = 7. Тому, користуючись таблицею 9.2, визначаємо параметри коду БЧХ, який має здатність виявляти шість помилок: n = 15, k = 5, r = 10, P₈ = 2467. Переводимо значення твірного поліному, що записане у вісімковій системі числення, у двійкову  P₂ = 010100110111,  і  далі за-писуємо його у вигляді поліному:  P(x) = x¹⁰Åx⁸Åx⁵Åx⁴Åx²ÅxÅ1.

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

–  помножимо Q(x) на х^r:  (x⁴Åx²Å1) x¹⁰ = x¹⁴Åx¹²Åx¹⁰;

–  поділимо  Q(x) x¹⁰  на  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)=x⁹Åx⁶Åx²ÅxÅ1;

–  визначаємо суму  Q(x)x¹⁰ ÅR(x)  і одержуємо поліном кодової комбінаціє коду БЧХ :  F(x) = x¹⁴Åx¹²Åx¹⁰Åx⁹Åx⁶Åx²ÅxÅ1; йому  відповідає  комбінація 101011001000111.

Покажемо процес виявлення шести помилок. Припустимо, що при передачі виникли  6 помилок. Нехай поліном шестикратної помилки E(x) = x¹² Åx¹⁰ Åx⁹Åx⁶Åx⁵Åx². Тоді поліном прий­нятої комбінації коду  БЧХ :   F^*(x) =  x¹⁴ Åx⁵Å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 ) не дозволяє виправити ці шість помилок.

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

 

 

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

Завдання 1.

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

Таблиця 9.3.1

Завдання 2.

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

Таблиця 9.3.2

Завдання 3.

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

Таблиця 9.3.3

Завдання 4.

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

Таблиця 9.3.4

 

Завдання 5.

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

 

Таблиця 9.3.5

Завдання 6.

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

Таблиця 9.3.6

 

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