Виявлення і виправлення помилок

Виявлення і виправлення помилок. Декодер.

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

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

Мал. 7.1 Кодер коду (7,4)

Мал. 7.2. Декодування з виявленням помилок для коду (7,4)

Вони будуть збігатися також і в тому випадку, якщо передана (дозволена) кодова комбінація перейшла в іншу раз вирішену.

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

Приклад 7.4. Нехай код (6,3) заданий системою перевірок (7.4) - (7 6) і при передачі кодової комбінації 101 100 на прийомі отримали 001 101, т. Е. Спотворені елементи Обчислимо елементи синдрому

Так як синдром відрізняється від нуля, то помилка виявлена.

Декодер для коду (7,4), що працює в режимі виявлення помилок, представлений на рис. 7.2.

Виходи сумматоров, в яких формуються елементи синдрому, подаються на схему АБО З виходу останньої знімається одиниця (сигнал «помилка») при виявленні помилок. При цьому приймач відкидає прийняте кодове слово. Така відмова від прийнятого кодового слова називається стиранням і зазвичай передбачає повторення кодового слова заново.

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

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

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

так як де Е - вектор помилок, то

Розглянутий в прикладі (7.4) код (6,3) має кодове відстань і здатний виправляти одноразові помилки. Якщо неправильно прийнятий елемент із системи рівнянь

отримуємо так як входить в (7.9) і (7 10) і не входить в (7.8). Значення синдромів для випадку, коли є одиночна помилка в тому чи іншому елементі, наведені в табл 7.1.

Мал. 7.3 Декодування з виправленням помилок для коду (7,4)

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

для випадку, коли Е = 100000. Неважко здогадатися, що якщо мала місце дворазова помилка, наприклад в елементах, то синдром був би рівний сумі стовпців матриці Н. Так, якщо, то, т. е. буде зроблений неправильний висновок про те, що спотворений елемент, так як код дворазові помилки не виправляє.

Структурна схема декодера з виправленням одиночних помилок для коду (6,3) приведена на рис. 7.3. На вхід декодера надходить кодова комбінація, сформована кодером, зображеним на рис. 7.1. За прийнятою комбінації обчислюється синдром, який подається на дешифратор «синдром-помилка». При одиночній помилку на одному з виходів дешифратора з'являється (елемент вектора помилки). Додавання вектора помилки з прийнятою комбінацією призводить до виправлення помилки.