3.5.2. Корекція помилок

Розглянутий спосіб оцінки достовірності передачі інформації по каналу зв’язку не дає можливості знайти похибку в інформаційному слові. Тому в складних комп’ютеризованих та мікропроцесорних схемах з розгалуженими каналами цифрового зв’язку використовують системи передачі з використанням таких кодів, які дозволяють як знаходити, так і виправляти випадкові похибки. До них відносяться, наприклад, код Хемінга, циклічні коди, які використовуються для виявлення та виправлення похибок не тільки при передачі, але й при зберіганні даних; код Ріда-Соломона, який широко використовується при записі та зчитуванні компакт-дисків, та інші.

Розглянемо ідеологію та принцип побудови цифрових кодерів з виправленням похибок на прикладі використання коду Хемінга.

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

.

(3.13)

При передачі кодів може бути спотвореним будь-який інформаційний сигнал. Але може виникнути й така ситуація, коли жоден з розрядів не буде спотворений, тобто, якщо в створеному коді маємо N розрядів, то за допомогою контрольних кодів, що входять, відповідно до (3.13), в це число, повинна бути створена така кількість комбінацій , щоб мати можливість закодувати будь-який з розрядів. Тому повинна виконуватись нерівність:

(3.14)

або відповідно до (3.13)

.

(3.15)

З (3.14) з врахуванням (3.15) знаходимо:

.

(3.16)

З (3.16) знаходиться кількість інформаційних розрядів у кодованому слові з N розрядами:

.

(3.17)

Критерій оптимальності коду Хемінга має вигляд:

,

(3.18)

де – кількість комбінацій з N по r ; r – кількість виявлених незалежних похибок.

При (тобто для одиничних похибок) формула (3.18) має вигляд:

.

(3.19)

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

Як приклад, розглянемо ситуацію, коли слово має 11 розрядів . У цьому випадку формула (3.17) перетворюється в рівність при . Тобто кількість коригуючих розрядів .

Пояснимо, що можливість виправлення похибки в коді Хемінга базується на повтореній k разів системі контролю парності, але не всього слова одночасно, а k окремих груп його розрядів. Слово розбивається на групи так, щоб номер кожного розряду визначався за його належністю до цих груп. Вказані групи називаються групами контролю парності і компонуються з розрядів кодового слова на основі наступних правил:

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

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

Рис. 3.48

Рис. 3.48 показує організацію кодованого блоку, який планується передавати по лінії зв’язку, – кодового слова. Воно має одинадцять розрядів інформаційного слова, розряди якого позначені малими латинськими літерами , та чотирьох контрольних розрядів, які позначені буквами грецького алфавіту , , , . Контрольні розряди розміщуються в масиві кодового слова, в клітках тих розрядів, в яких має місце одиниця тільки в одній позиції. Адресі вказаної одиниці i відповідає контрольний розряд.

Відповідно до вказаних правил формування контрольних груп, 4-й розряд входить всього до однієї – третьої – групи; розряд 6 – до другої та третьої; розряд 10 – до другої та четвертої, i т. д. Тому четверта група включає в себе лише розряди від 8-го по 15-й, а третя 4-7 та 12-15. Наймолодший розряд кожної групи є контрольним.

Рис. 3.49

На рис. 3.49 показана функціональна схема кодового перетворювача. За його допомогою семирозряднi сформовані групи інформаційного кодового слова подаються на схеми контролю парності M2₁ – M2₄. Результати контролю кожної групи записуються в контрольний розряд відповідної групи, створюючи на вихідному регістрі кодове слово, що передавалося.

Відповідно до відображеного на рис. 3.48 принципу формування кодового слова, в блоці формування груп створюються групи контролю, які подають свої сигнали разом з контрольним розрядом на схеми контролю парності М2. Виходи блоків M2₁ – M2₄ створюють керуючий код К. Якщо при передачі кодового слова в одному з його розрядів з’явилась похибка (на рис. 3.48 приведений приклад появи похибки в 5-му розряді, звідки виходять лінії), то буде зафіксовано порушення парності одиниць в розрядах коригуючого коду, відповідних контрольним групам з розрядом похибки. В результаті коригуючий код вказуватиме на номер того розряду кодового слова, в якому з’явилась похибка. Так, на рис. 3.48 контрольний код 0101 вказує на 5-й розряд.

Для відновлення інформації в слові, що передавалося, необхідно в визначеному розряді проiнвертувати його значення. Схема, яка вирішує цю задачу, приводиться на рис. 3.50. Кодове слово, що приймається вхідним регістром, перетворюється в чотири восьмирозряднi кодові групи, які контролюються на парність одиниць восьмирозрядними блоками M2₁ – M2₄. Входи блоків контролю парності дешифруються, i, якщо в i-му розряді має місце похибка, то одиничний сигнал подається на i-й керований інвертор i змінює стан розряду інформаційного слова. При відсутності збоїв в передачі інформації одиничний сигнал з’являється на нульовому вході дешифратора.

Рис. 3.50

Коди Хемiнга використовуються там, де вимоги до точності передачі даних досить високі.