Коди виявлення помилок

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

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

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

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

4.1.2 Код із перевіркою на непарність

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

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

4.1.3 Код із простим повторенням

Код із простим повторенням (без інверсії) є подільним ліній­ним кодом. Він містить k інформаційних І r = k перевірних еле­ментів. У цьому коді r перевірних елементів є простим повторен­ням k Інформаційних елементів первинної кодової комбінації: b_i = a_i:, де і =1…k.

Через те, що код має відстань d_min = 2, він може використовува­тися для виявлення поодиноких помилок. Ця процедура зво­диться до порівняння однойменних інформаційних і перевір­них елементів у прийнятій кодовій комбінації. Незбіг їх свід­чить про наявність помилок у ній. Код дає змогу виявити не тільки однократні помилки, а й деякі помилки більшої крат­ності, за винятком «дзеркальних», коли в інформаційній та пе­ревірній послідовностях кодової комбінації внаслідок дії завад спотворюються елементи, що знаходяться на однакових за но­мером розрядах.

Надмірність коду визначається виразом

R_над=1-k/(2k)=1/2.

4.1.4 Інверсний код

Інверсний код (із повторенням та інверсією) є подільним лі­нійним кодом, який має к ынформаційних і стільки ж перевір­них елементів. Його відмінність від попереднього коду полягає в тому, що значення перевірних елементів у ньому залежать від значення суми за модулем 2 всіх інформаційних елементів. За умови , тобто при парній кількості одиниць у почат­ковій кодовій комбінації, перевірні елементи просто повторюють інформаційні (b_i = a_i:, де і =1…k), а за умови , тоб­то при непарній кількості зазначених одиниць, перевірні еле­менти повторюють інформаційні в інвертованому вигляді (в оберненому коді): b_i = a_i 1, де i = 1 ...k.

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

Якшо кількість одиниць серед перших k елементів непарна, то решту к елементів приймають у негативі (інвертують), після чого поелементно порівнюють їх. Наявність незбігу призводить до відбраковування всіх 2k- елементів. Така побудова коду дас змогу виявляти майже всі випадки спотворення його елемен­тів, крім двократних «дзеркальних» помилок.

Надмірність коду визначається виразом

R_над=1-k/(2k)=1/2.

4.1.5 Кореляційний код

У цьому коді кожний розряд двійкового початкового коду за­писується у вигляді двох елементів: 0 – як 01, а 1 – як 10. Так, початковій кодовій комбінації 010011 відповідатиме комбінація 011001011010 кореляційного коду. В технічній літературі такий двійковий запис дуже часто називається Манчестер-кодом.

Приймальний пристрій в кожному такті, ще-складається з двох сусідніх елементів кореляційного коду, має зафіксувати перехід 0 →1 або 1 → 0. У разі прийняття двох нулів або оди­ниць приймальний пристрій фіксує наявність помилки.

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

Надмірність коду визначається виразом

R_над=1-k/(2k)=1/2.

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

4.1.6 Код зі сталою вагою

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

де m – кількість одиниць у кодовій комбінації завдовжки я.

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

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

Надмірність коду визначається виразом

R_над=1-(log )/n.

Порівняно з кодом із простим повторенням цей код при мен­шій його надмірності дає змогу виявляти помилки тієї самої кратності.

4.1.7 Код із кількістю одиниць у комбінації, кратною трьом

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

У першому випадку до початкової кодової комбінації дода­ються два перевірних розряди, які мають такі значення, що сума одиниць у кодовій комбінації стає кратною трьом. Так, якщо початкова кодова комбінація мас дві або п'ять одиниць, то для здобуття ваги w = 3 або 6 кодової комбінації треба доповнити її двома перевірними елементами 1 0. Якщо ж у початковій ком­бінації є одна або чотири одиниці, то вона доповнюється дво­ма перевірними елементами 11. Так, комбінація 01010 почат­кового коду, закодована кодом із кількістю одиниць, кратною трьом, матиме вигляд 0101010, а 10000 → 1000011,

0110→011010,101100→10110000,110110→11011011,0111011→011101110.

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

Код дає змогу виявити всі поодинокі помилки та деякі по­милки більшої кратності, що призводять до порушення умови w = 3 або 6, де w – кількість одиниць у кодовій комбінації. Здатність коду виявляти помилкові комбінації майже така сама, як і коду зі сталою вагою.

Надмірність коду з доповненням до необхідної кількості оди­ниць визначається виразом

R_над=1- ,

а коду, що утворюється відбором із загальної кількості комбі­націй з відповідною кількістю одиниць (3 або 6), - виразом

R_над= .

4.1.8 Зважений знаково-цифровий код

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

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

Людині, що обробляє дані, властиві помилки іншого типу, зв’язані із заміною одного знака іншим. Найбільш розповсюдженими із них є такі:

- перестановка сусідніх цифр при записуванні чисел; наприклад, 67 перетворюється в 76;

- дублювання неправильної цифри в числі, що має співпадаючі сусідні цифри; наприклад, 667 перетворюється 677;

- плутанина в буквенно-цифрових повідомленнях цифри «0» та букви «О»;

- плутанина однакових за контуром літер в повідомленнях, що сумісно використовують латиніцу та кириліцу.

Припустимо, що алфавіт кодованого повідомлення містить 37 знаків (10 цифр, 26 літер та пропуск). Знаки такого алфавіту вважаємо пронумерованими від 0 до 36. Оскільки 37 - просте число, то стає можливим кодування коротких повідомлень з використанням зваженої суми. Таке кодування дозволяє легко виявляти перестановки або заміни знаків повідомлення. Імовірність того, що випадкове повідомлення задовольнить такій перевірці, становить 1/37.

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

Властивість зваженої суми n чисел полягає в тому, що перший доданок входить в неї n раз, другий - n-1 раз і т.д. Останній доданок входить в зважену суму один раз. Найбільш просто процес «сумування сум» демонструється за допомогою таблиці для повідомлення «ABCD».

Приклад 1. Закодуємо повідомлення «AB 7».

Оскільки 31+x=37, то x = 6. Закодоване повідомлення має вигляд «AB 76». На приймальному кінці для перевірки правильності отриманого повідомлення поступаємо аналогічно.

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

Поиск по сайту: