Тема 12-13. Двійкові  коди

 

ПЛАН

1.    Двійкові  коди, що виявляють помилки

2.    Двійкові  коди,  що  виправляють однократні  помилки

3.    Циклічні коди

 

 

1.    ДВІЙКОВІ  КОДИ, ЩО ВИЯВЛЯЮТЬ ПОМИЛКИ

 

Особливість кодів, що виявляють помилки, полягає у тому, що кодові комбінації, які входять до складу таких кодів,  відрізняються одна від одної кодовою відстанню не меншою  за  d _min  = 2.

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

До першої групи кодів, що виявляють помилки,  відносяться  такі лінійні коди:  з перевіркою на парність, з простим повторенням, інверсний ( Бауера ), кореляційний; нелінійні коди: з перевіркою на непарність, код Бергера.  Прикладом  коду  другої групи є  код  з  постійною вагою. Код  з  числом одиниць в комбінації, кратним трьом, може належати до першої або до другої групи кодів у залежності від методики його побудови.

Код  з  перевіркою  на  парність  є найбільш поширеним кодом, який використовується для виявлення поодиноких помилок  і  всіх помилок непарної кратності.  Код містить  ( n – 1 )  інформаційних  та  один перевірочний елемент  і  позначається  як  ( n , n – 1 ) - код.

Перевірочний елемент визначається як сума за модулем 2 всіх інформаційних елементів:     тобто кодова комбінація коду утворюється  доповненням комбінації  k - елементного первинного коду одним елементом таким чином,  щоб кількість одиниць у новому  n - розрядному  ( n = k + 1 )  коді була парною. Код має  кодову відстань   d_min = 2.

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

Вважається, що при  s₁ = 0  помилки в комбінації нема, при  s₁ = 1  –  помилка є.  Код виявляє всі помилки непарної кратності.

Надмірність коду  R  = 1 – k / ( k + 1 )  = 1 / ( k + 1 ).

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

Код  з  простим  повторенням   ( з  повторенням без інверсії )  є  роздільним лінійним кодом.  Код містить  k  інформаційних та  r = k перевірочних елементів. У цьому коді  r  перевірочних елементів  є  простим повторенням  k  інформаційних  елементів  первинної  кодової  комбінації:  b _i  =  a _i ,  де    i  =  1 . . . k . Через те, що код має  d _min = 2,  він може бути використаний для виявлення поодиноких помилок.  Процедура виявлення помилок у прийнятій кодовій комбінації полягає у порівнянні однойменних інформаційних  і  перевірочних елементів.  Їх  незбіг говорить про наявність помилок у прийнятій комбінації.  Код дозволяє виявити не тільки однократні помилки, а  й  деякі помилки більшої кратності,  за винятком   так званих “дзеркальних” помилок,  коли в інформаційній і перевірочній послідовностях кодової комбінації в результаті дії завад спотворюються елементи,  які знаходяться на однакових за номером розрядах.

Надмірність  коду   R  =  1 –  k / ( 2 k )  = 1 / 2.

Інверсний  код  ( код  Бауера ) є  роздільним лінійним кодом  з повторенням  з  інверсією,  який має  k  інформаційних  та  k  перевірочних елементів.  Його відмінність від коду з  простим повторенням полягає у тому, що значення перевірочних елементів у ньому залежать від значення суми за модулем  2  всіх  інформаційних елементів. При тобто при парному числі одиниць у первинній кодовій комбінації перевірочні елементи просто повторюють інформаційні  ( b _i  =  a _i ,  де  i  = 1 . . . k ). При   тобто при непарному числі одиниць у первинній кодовій комбінації, перевірочні елементи повторюють інформаційні в інвертованому вигляді  ( у  зворотному  коді ):  b _i  =  a _i Å 1,   де  i = 1 . . . k.

Для виявлення помилок декодером  у послідовності, що складається  з  2 k  елементів,  спочатку підсумовують одиниці,  які знаходяться у перших  k  елементах.  Якщо їх кількість парна,  решта  k  елементів приймається у позитиві. Обидві зареєстровані частини  кодової комбінації поелементно порівнюються ( перший елемент з першим, другий – з другим  і т.д.).  При наявності хоча б одного незбігу  вся послідовність  елементів бракується.  Якщо кількість одиниць серед перших  k  елементів прийнятої комбінації непарна,  решта  k  елементів  приймається у негативі ( інвертуються ).  Після чого виконується поелементне порівняння.  Наявність незбігу призводить до відбракування кодової комбінації.  Така побудова коду дозволяє виявити  дуже багато варіантів спотворення елементів. 

Надмірність  коду  R  =  1 –  k / ( 2 k )  = 1 / 2.

Кореляційний  код  передбачає кодування кожного елемента первинної кодової комбінації. При цьому "0"  записується як  "01",  а  "1" – як  "10".  Так, наприклад, первинній кодовій комбінації  100101  буде відповідати комбінація  100101100110  кореляційного коду.  В технічній літературі такий двійковий запис дуже часто називають  Манчестер - код.  Приймальний пристрій на кожному такті,  який складається  з  двох сусідніх елементів кореляційного коду,  повинен зафіксувати перехід  0 ® 1  або  1 ® 0. У разі  прийняття двох нулів або двох одиниць приймальний пристрій фіксує наявність помилки.

Такий код дозволяє виявляти  помилки будь-якої кратності у кожній парі елементів одного такту, але не здатний виявити так звані "дзеркальні" двократні помилки, коли сусідні елементи одного такту під впливом завад змінюються на протилежні.

Надмірність  коду   R  = 1 –  k / ( 2 k )  = 1 / 2.

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

Код  Бергера  є найбільш поширеним  з  несистематичних кодів. У такому коді перевірочні елементи, які дописуються у кінці первинної кодової комбінації, – це  інвертований запис двійкового чис-ла, яким записується сума одиниць у кодовій комбінації k – елемент-ного первинного коду, що кодується кодом  Бергера. При цьому число r  перевірочних елементів визначається як найменше ціле, для якого виконуються умови  r ³  log ₂ ( k + 1 ).  Так, наприклад,  при  k = 8, отри-маємо  log ₂ ( 8 + 1 )  =  log ₂ 9  =  3,16993,   тобто   r  =  4.

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

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

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

 ,

де  m  –  число одиниць у комбінації  довжини  n.

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

Код з постійною вагою має мінімальну кодову відстань  d _min = 2  і  виявляє всі помилки непарної кратності,  а  також всі помилки  пар-ної кратності, які призводять до порушення умови   m = const.

Надмірність  коду   R  = 1 – ( log ₂ C) / n. 

Код  з  числом  одиниць  у  комбінації,  кратним  трьом, можна утворити або шляхом додавання до кожної комбінації первинного коду  двох перевірочних елементів, або зменшенням кількості дозволених кодових комбінацій первинного коду за допомогою накладання додаткової  умови – кількість одиниць у кожній комбінації повинна бути кратною трьом  ( 0, 3, 6, . . . )

У першому випадку до первинної кодової комбінації додаються два перевірочні розряди,  які мають такі значення, що сума одиниць у кодовій комбінації стає кратною трьом. Так, наприклад, комбінація первинного коду  01100  закодована кодом з числом одиниць, кратним трьом,   буде  мати   вигляд  0110010,   комбінація   01000  0100011,  1010  101010,   101100  10110000,   101110  10111011, 0111110  011111010   тощо.

У другому випадку з усіх кодових комбінацій первинного коду вибирають тільки ті комбінації, які мають вагу w = 0, 3, 6, 9, . . . Всі інші комбінації заборонені для вживання.

Код дозволяє виявити всі поодинокі помилки та деякі помилки більшої кратності.

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

Надмірність коду з доповненням до необхідної кількості одиниць ( кратності ):  R  =  1 –  k / ( k + 2 ),  а  для коду, який утворюється шляхом відбору комбінацій з відповідною кількістю одиниць  з   повного числа комбінацій простого коду:

    R = 1 – [ log ₂ ( C+ C+ C+ . . . + C) ] / n , 

де  b  –  ціла частина  n / 3.

 

2.    ДВІЙКОВІ  КОДИ,  ЩО  ВИПРАВЛЯЮТЬ ОДНОКРАТНІ  ПОМИЛКИ

 

Коди, що виправляють одну помилку, повинні мати мінімальну кодову відстань  d _min  3. Збільшення кодової відстані досягається збільшенням числа розрядів коду  n  при незмінній кількості дозволених кодових комбінацій або зменшенням числа дозволених кодових комбінацій, що використовуються для передачі повідомлень, тобто збільшенням надмірності коду.

Найбільшого  поширення серед двійкових  кодів, що виправляють однократні помилки, одержали систематичні  ( лінійні,  групові ) блокові коди:  Хеммінга, ітеративний ( Елайеса ), з багатократним повторенням, інверсний, та несистематичний код Бергера .

Систематичний  код   з  d _min = 3,  який  називають кодом   Хем-мінга,  використовується для виправлення однієї або виявлення двох помилок.

Систематичний  ( груповий, лінійний )  код довжиною  n  з кількістю інформаційних символів  k  позначають як  ( n, k ) - код. Для систематичного  ( n, k ) - коду з  d _min = 3  кількість перевірочних символів вибирають  як  найменше ціле  r,  що відповідає умовам

                                  2 n + 1 =  k + r + 1.                                   ( 8.1 )

Як відомо, у систематичних кодах перевірочні елементи можна одержати шляхом  додавання за модулем 2 визначених інформаційних елементів.

Систематичний код можна задавати твірною ( породжуваль-ною ) матрицею, якій притаманні такі особливості:

–  матриця  має  k  рядків  та  n  стовпців ;

–  кожний  елемент  матриці  є  або “0”,  або “1”;

–  кожний  рядок  матриці являє собою кодову комбінацію коду, що цією матрицею задається, і повинен мати не менше трьох одиниць ;

–  всі рядки матриці повинні бути лінійно незалежними ;

–  поелементна сума за модулем  2  будь - якої кількості рядків матриці  ( яка,  до речі,  завжди буде комбінацією коду )  повинна мати не менше трьох одиниць.

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

          G _n,k =   ,       ( 8.2) де  a _j i  та  b _j m  –  відповідно i - ий інформаційний та m - ий перевіроч-ний елементи  j - ої  базисної кодової комбінацій.

Твірну матрицю ( 8.2 ) можна подати у вигляді двох підматриць: інформаційної  ( Е _k )  та  перевірочної  ( С _r, k  ).

Інформаційну підматрицю зручно подати у канонічній формі як одиничну підматрицю розміром  k  k:

                                Е _k  =    .

Перевірочна підматриця  С _r,k  будується підбором  r - розрядних двійкових послідовностей  з  числом одиниць у кожному рядку не менше за  d _min – 1 = 2.  При цьому необхідно враховувати, що сума за модулем  2  будь-яких рядків цієї підматриці не повинна мати менше за  d_min – 2 = 1  одиниць, тобо однакові набори є неприпустимими.

Рядки у перевірочній підматриці можна міняти місцями. При цьому можна одержати декілька варіантів твірних матриць.

Твірна матриця дозволяє одержати всі кодові комбінації систематичного групового коду. Це досягається послідовним додаванням за модулем  2  рядків матриці у всіх можливих сполученнях ( тобто першого і другого рядків матриці;  першого і третього;  першого і четвертого; . . . ;  другого і третього;  другого і четвертого; . . .;  першого, другого і третього; першого, другого і четвертого; . . . , нарешті  усіх  k рядків ). Нульова комбінація дописується окремо.

Опираючись на твірну, матрицю можна побудувати перевірочну матрицю  Н _n,r ,  яка  налічує  r  рядків та  n  стовпців. Перевірочна матриця складається з двох підматриць: підматриці  D _k,r , яка має k  стовпців  та  r  рядків, кожний рядок якої відповідає транспонованому стовпцю перевірочної підматриці  С _r,k  твірної матриці  G _n,k ,  та одиничної підматриці   E _r   розміром  r ´ r :

    H _n,r  =  [ D _k,r ; E _r  ]  =   .   ( 8.3 ) 

Перевірочна  матриця  ( 8.3 ) дозволяє спростити операції кодування і декодування.

Запишемо  довільну  кодову  комбінацію  коду  у  вигляді

                      V  =  [ a₁a₂a₃ . . . a_k b₁b₂b₃ . . . b_r ] ,

де  a _i   та  b _m –  відповідно інформаційні та перевірочні елементи.

Позиції, які зайняті одиницями у  і - ому  рядку підматриці  D _k,r ,  визначають ті інформаційні елементи, які повинні брати участь у формуванні  і - ого перевірочного елемента   b _i :

 b₁  =  b₁₁ a₁ Å b₂₁ a₂ Å . . . b_k 1 a_k ,

 b₂  =  b₁₂ a₁ Å b₂₂ a₂ Å . . . Å b_k 2 a_k ,                                            ( 8.4 )

              

  b _r  =  b_1r a₁ Å b_2 r a₂ Å . . . Å b_k r a_k .

Існування співвідношень  ( 8.4 ), що пов’язують інформаційні та перевірочні елементи кодової комбінації, дає можливість при деко-дуванні виявляти та виправляти помилки в кодових комбінаціях, які можуть з’являтися через спотворення елементів у двійковому каналі під час їх передачі. Аналізуючи результати перевірки цих співвідношень у прийнятій кодовій комбінації, можна отримати певну ін-формацію  про  помилки.

Позначимо кодову комбінацію, яка пройшла через двійковий канал та підлягає декодуванню,

                   V ^* =  [ aaa . . .  abbb . . . b] ,

де  a  та   b –  відповідно інформаційні та перевірочні елементи кодової комбінації на виході каналу.

Для з’ясування питання, чи відповідає кодова комбінація V ^*  правилам побудови  коду, отримаємо набір  s _j ,   j = 1,2,3, . . . , r :

             s _j  =   b _1 j  a Å b _2 j  a Å b _3 j  a Å . . .  Å b _k j  a Å  b.

Кожний елемент  s _j  дає інформацію про те, задовольняють чи ні символи кодової кобінації  V ^* відповідному рівнянню системи  ( 8.4 ). 

Набір елементів ( s ₁, . . . , s _r  ) називається кодовим синдромом або пізнавачем  помилок .

Якщо синдром складається з одних нулів, кодова комбінація   V ^* є дозволеною, тобто задовольняє правилам побудови коду.Такий результат буде мати місце, якщо в кодовій комбінації немає помилок або конфігурація помилок є такою, що вона не може бути виявлена цим кодом. Присутність хоча б одного ненульового елемента в комбінації синдрому вказує на спотворення хоча б одного елемента у прийнятій кодовій комбінації.

Значення синдрому при однократній помилці у прийнятій кодовій комбінації збігаються із стовпцями перевірочної матриці. Порівнюючи кодовий синдром з стовпцями матриці  Н _n,r ,  можна знайти місце помилки у комбінації по їх збігу. У разі помилки виправляється той розряд кодової комбінації, який відповідає порядковому номеру стовпця матриці, що збігається  з синдромом.

Вкорочені систематичні ( групові ) коди  утворюються з  повних кодів, при цьому одержують  d _min  не меншу, ніж у повного систематичного коду зі збереженням такої ж кількості перевірочних елементів, тобто  r  =  ( n – i ) – ( k – i ) =  n – k .

Одержання вкороченого коду грунтується на тому, що через те що  з загального числа  2 ^k  комбінацій первинного коду, які потрібно закодувати, наприклад, систематичним ( n – 1,  k – 1 ) - кодом,  2 ^k – 1  ком-бінацій починаються з ” 0 ”,  а  2 ^k – 1  –  з  “ 1”, то  і  після кодування  2 ^k – 1  комбінацій систематичного групового ( n , k ) - коду   також будуть починатися  з  ” 0 ”.

Будемо ці 2 ^k – 1 комбінацій розглядати як новий груповий код. Тоді, якщо вони належать вихідному  ( n , k ) - коду, d _min нового коду буде не меншою, ніж d _min вихідного. Нульовий символ на початку вихідної кодової комбінації зберігається і після кодування її груповим ( n , k ) - кодом. Зрозуміло, що він не впливає на  утворення переві-рочних елементів групового коду і його можна відкинути. При цьому одержимо груповий ( n – 1, k – 1 ) - код, тобто код, що містить  n – 1  елементів,  з яких  k – 1  інформаційних  та  r – перевірочних.

Вкорочений груповий код легко одержати з повного ( n, k ) - коду, який поданий у вигляді твірної матриці  G _n,k  розміру ( k ´ n ) вигляду ( 8.2 ), шляхом виключення з матриці першого рядка і першого стовпця. У результаті цього одержимо твірну матрицю  G _{n – 1, k – 1}  нового вкороченого коду розмірності ( k – 1 ) ´ ( n – 1 ), що утворює  2 ^k – 1  комбінацій вкороченого коду. Для одержання перевірочної матриці  H _{n – 1, r}   вкороченого коду досить виключити перший стовпець з матриці H _n, r  відповідного повного коду.

Після вкорочення на один символ групового ( n – 1, k – 1 ) - коду можна одержати вкорочений  ( n – 2, k – 2 ) ‑ код  тощо.

Наведена вище інтерпретація коду Хеммінга грунтується на сучасних уявленнях про цей код як різновид лінійних кодів. Згідно з цією теорією можна побудувати не менше, ніж  n!/r!  різноманітних лінійних кодів, що мають  d _min = 3 ,  тобто кодів  Хеммінга. Кожен із цих кодів задається  однією із перестановок стовпців перевірочної матриці. Всі ці коди еквівалентні за корегувальною здатністю;  відрізняються вони розташуванням перевірочних символів, співвідношеннями, яким відповідають символи, та, звичайно, наборами кодових комбінацій.

Код, запропонований  Р.В.Хеммінгом ще до формування теорії лінійних кодів, – це один із варіантів вищеозначених кодів, для якого перевірочна матриця будується так, що  i - ий  стовпець її є двійковим поданням числа  і. За такою умовою кодовий синдром, у разі виникнення однократної помилки, буде двійковим поданням номера спотвореного розряду кодової комбінації. Перевірочні розряди в такому коді розташовані на позиціях з номерами   2⁰,2¹,2², . . . ,2 ^r – 1; перевірочні розряди розміщуються між інформаційними.. Будемо називати такий код  традиційним кодом Хеммінга.

Розширений код Хеммінга використовується, головним чином, для виявлення помилок. Цей код має кодову відстань  d _min = 4  і забезпечує виявлення одно-, дво- і трикратних помилок завдяки введенню додаткового перевірочного елемента  b₀, який одержують за допомогою перевірки кодової комбінації коду Хеммінга на парність. При цьому перевірочний елемент, який розміщується, як правило, на початку кодової комбінації, дорівнює “ 0 ” при парній  кількості одиниць у кодовій комбінації  і  “ 1 ” – при непарній.

Декодування розширеного коду Хеммінга виконують у зворотній послідовності: спершу виконують загальну перевірку прийнятої кодової комбінації на парність, а потім – перевірку кодової комбінації без b₀. При цьому можуть виникнути ситуації, які показані у таблиці 8.1.

Для  одержання вкорочених кодів Хеммінга  з  d _min = 3  або  4  керуються правилами, що були викладені при побудові вкорочених систематичних кодів.

            

Таблиця  8.1

Кратність  помилки	Перевірка на парність ( b 0 )	Кодовий синдром
Помилка відсутня	=  0	=
Однократна помилка	=  1
Двократна помилка	=  0
Трикратна помилка	=  1	=

 

Код з багатократним повторенням ( з повторенням без інверсії )  є роздільним лінійним кодом. Код містить  k  інформаційних  та  mk  перевірочних елементів, де   m – число повторень первинної кодової комбінації. У цьому коді кожні  k  перевірочних елементів є просто повтореннями інформаційних елементів

b _j  =  b _j + k  =  b _{j + 2k}  = … =  b _{j + ( m – 1 )k}  =  a _j ,   j = 1 ... k .

 Кодова відстань коду з багатократним  повторенням    d _min =  m + 1, тому при  m ³ 2 код здатен не тільки виявляти, але і виправляти помилки. Процедура виявлення помилок у прийнятій кодовій комбінації полягає у порівнянні однойменних інформаційних і перевірочних розрядів. Їх незбіг говорить про наявність помилок у прийнятій комбінації. При виправленні помилок у комбінації застосовується мажоритарний принцип виправлення для кожного інформаційного елемента, тобто “ голосування за більшістю ”, коли за істинне значення приймається те, яке частіше зустрічається у цьому інформаційному і відповідних йому перевірочних елементах. Код дозволяє виправляти всі помилки кратності від 1 до цілої частини числа  m / 2  та деякі помилки більш високої кратності у залежності від розміщення помилок у комбінації.

Надмірність коду   R  =  m / ( m + 1 ).

Ітеративні коди (коди Елайеса), якщо вони орієнтовані на виправлення однократних помилок, являють собою, як правило, двомірні лінійні коди з кодуванням  рядків і стовпців завадостійкими кодами з перевіркою на парність ( див. розділ 7 ). Такі ітеративні коди мають мінімальну кодову відстань  d _min  = 4  і у режимі виправлення  помилок дозволяють виправити будь-які однократні помилки і деякі помилки більшої кратності.

Рекомендується на практиці використовувати коди з числом перевірочних елементів  8, 9 та 16. Для коду з  r = 8 використовують блок  інформаційних  елементів  розмірами  3 ´ 4 ( з  k ₁  = 3  рядками  та   k ₂   =  4 стовпцями  ). При  цьому число інформаційних елементів  k  =  k ₁ ´ k ₂  =  3 ´ 4  = 12,  число перевірочних  –  r  = 8, n = 20. Для коду з  r = 9  беруть  k = k ₁ ´ k ₂  = 4 ´ 4 = 16, n =  25;  для коду з  r = 16:   або k =  k ₁ ´ k ₂ = 8 ´ 7 = 56,  n = 72   або  k = k ₁ ´ k ₂ = 7 ´ 8 = 56,  n = 72.

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

Надмірність двомірних ітеративних кодів:

для  r  = 8    ®   R  = r / n  =  2 / 5;

для  r  =  9   ®   R  = 9 / 25;

для  r  = 16  ®   R  = 2 / 9.

Несистематичний код Бергера є найбільш поширеним  з  несистематичних кодів.  У такому коді перевірочні елементи, які дописуються у кінці первинної кодової комбінації,  –  це  інвертований за-пис двійкового числа, яке дорівнює сумі вагів тих елементів інфор-маційної частини  кодової комбінації, на яких розташовані одиниці. При цьому число r  перевірочних елементів визначається як найменше ціле, яке задовольняє нерівності    r ³  log ₂ ,  де  w _i – вага  i - ого інформаційного елемента  первинної кодової комбінації, яка кодується кодом Бергера, а ваги елементів первинної комбінації повинні приймати такі значення, починаючи з першого ( старшого ) розряду: 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18 тощо, тобто всі числа, крім тих, які дорівнюють значенням числа 2 у будь-якій цілій додатній степені ( 2⁰, 2¹, 2², ...  ). Так    наприклад,   при   k  =  8   маємо log ₂ =  log ₂  ( 3 + 5 + 6 + 7 + 9 + 10 + 11 + 12 )  =  log ₂ 63  = 5,977, тобто  r =  6. Таким чином перевірочна частина кодової комбінації буде мати 6 розрядів.

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

Надмірність  коду  R  = 1 –  k / n = 1 –  k / ( k + r ) = r / n.

 

3.    Циклічні коди

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

 

 

.