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

Задача 4.2.2

Задача 4.2.1

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

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

Розв'язання.Для безнадмірного кодування 64 символів достатньо застосувати рівномірний двійковий код довжиною . Це число визначає кількість інформаційних елементів.

Тоді надмірність завадостійкого коду

.

Визначити кодову відстань між комбінаціями і двійкового коду та записати всі комбінації, які знаходяться від комбінації на кодовій відстані , якщо , .

Розв'язання.Щоб визначити кодову відстань між комбінаціями А та В знаходимо поелементну суму за модулем 2 цих комбінацій:

одержуємо комбінацію C =10100, вага якої w = 2. Тобто в комбінаціях А і В у трьох однойменних розрядах (на 1-му справа, 2-му і 4-му) знаходяться однакові символи, а на двох (на 3-му справа і 5-му) – різні, сукупність яких і визначає степінь різниці між комбінаціями А та В. Вага комбінації С є кодовою відстанню Хеммінга між комбінаціями А та В.

Будь-яка комбінація ваги w = 3, якщо її порозрядно додати за модулем 2 до комбінації A (такої ж довжини), дає нову комбінацію, яка буде знаходитися від комбінації A на кодовій відстані d=3. Кількість таких комбінацій буде дорівнювати кількості сполучень з n = 5 по d=3:

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

Таким чином одержуємо такі 10 комбінацій, які знаходяться від комбінації А на кодовій відстані d=3: 01110, 00010, 00100, 00111, 11010, 11100, 11111, 10000, 10011, 10101.

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

Такі коди умовно можна розділити на дві групи:

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

· та коди, які одержують шляхом зменшення кількості дозволених комбінацій.

До першої групи кодів, що виявляють помилки, відносяться такі лінійні коди:

· з перевіркою на парність,

· з простим повторенням,

· інверсний (Бауера),

· кореляційний;

нелінійні коди:

· з перевіркою на непарність,

· код Бергера.

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

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

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

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

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

Надмірність коду .

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

Код з простим повторенням (з повторенням без інверсії) є роздільним лінійним кодом. Код містить інформаційних та перевірочних елементів. У цьому коді перевірочних елементів є простим повторенням інформаційних елементів первинної кодової комбінації: b_i = a_i , де . Через те, що код має d_min = 2, він може бути використаний для виявлення поодиноких помилок. Процедура виявлення помилок у прийнятій кодовій комбінації полягає у порівнянні однойменних інформаційних і перевірочних елементів. Їх незбіг говорить про наявність помилок у прийнятій комбінації. Код дозволяє виявити не тільки однократні помилки, а й деякі помилки більшої кратності, за винятком так званих “дзеркальних” помилок, коли в інформаційній і перевірочній послідовностях кодової комбінації в результаті дії завад спотворюються елементи, які знаходяться на однакових за номером розрядах.

Надмірність коду .

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

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

Надмірність коду .

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

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

Надмірність коду .

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

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

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

Надмірність коду .

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

,

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

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

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

Надмірність коду .

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

або шляхом додавання до кожної комбінації первинного коду двох перевірочних елементів,

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

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

,

,

,

,

,

тощо.

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

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

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

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

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

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