2.4 Алгоритм виправлення одиночних помилок

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

, (10)

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

У цьому випадку в результаті розподілу спотвореної кодової комбінації на утворюючий поліном одержимо:

(11)

де – залишок (синдром), обумовлений наявністю спотворень.

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

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

. (12)

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

Приклад. Синдроми всіх одиночних помилок коду (7,4) з утворюючим многочленом = 1101 наведені у таблиці 5.

Нехай прийнята комбінація , тоді залишок

Таблиця 5

1000000	110
0100000	011
0010000	111
0001000	101
0000100	100
0000010	010
0000001	001

= / 101.

З таблиці 5 маємо, що залишку = 101 відповідає вектор помилок 0001000. Отже, виправлена кодова комбінація

1000011 0001000 = 1001011.

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

2.5 Функціональні схеми пристроїв кодування

та декодування циклічних кодів

2.5.1 Функціональна схема пристрою кодування

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

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

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

На початку кодування ключ перебуває у верхньому положенні, а ключ – у нижньому. Інформаційна кодова комбінація з імпульсів подається безпосередньо на вихід й одночасно на схему множення-ділення. У схемі за = n – тактів формується залишок , що складається з контрольних символів. Після тактів ключ розмикається, а ключ переводиться в нижнє положення. За наступних тактів контрольні символи виводяться з регістра безпосередньо за інформаційними символами.

Рисунок 1

Приклад. На рисунку 2 наведена схема формування циклічного коду (7,4) для утворюючого многочлена . Робота схеми для інформаційного коду 1001 пояснюється за допомогою таблиці 6.

Рисунок 2

Таблиця 6 – Алгоритм формування циклічного коду

№ ТI	K1	K2	G		Вих. T1		Вих. T2	Вих. T3	F
1	↑	↓	1	1	0	1	0	0	1
2	↑	↓	0	0	1	1	1	0	0
3	↑	↓	0	1	0	1	1	1	0
4	↑	↓	1	0	1	1	1	1	1
5	↓	↑	0	0	0	0	1	1	1
6	↓	↑	0	0	0	0	0	1	1
7	↓	↑	0	0	0	0	0	0	0