1.7.3. Коди, що коригують одиночні помилки і виявляють помилки більшої кратності

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

Старші два біти b₆ b₅ розділяють всі коди на дві групи: молодших десяткових чисел 0 – 4, які кодуються однаково b₆ b₅ = 01; старших десяткових чисел 5 – 9, які мають код b₆ b₅ = 10.

Молодші 5 розрядів формують коди 1 з 5. Як видно з таблиці, поява помилки в будь-якому біті такого коду легко може бути виявлена, а інформація буде визнана помилковою.

Табл.1.8

N	b6	b5	b4	b3	b2	b1	b0
0 1 2 3 4 5 6 7 8 9	0 0 0 0 0 1 1 1 1 1	1 1 1 1 1 0 0 0 0 0	0 0 0 0 1 0 0 0 0 1	0 0 0 1 0 0 0 0 1 0	0 0 1 0 0 0 0 1 0 0	0 1 0 0 0 0 1 0 0 0	1 0 0 0 0 1 0 0 0 0

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

Допустимо, що код має мінімальну кодову відстань 3.

Рис. 1.27 показує фрагмент n-вимірного кубу для такого коду з кодовими словами 0000 і 0111. При відстані 3 маємо три біти різниці між двома сусідніми вершинами кубу. Допустимо тепер, що передається інформація і при її передачі має місце помилка в одному біті. Якщо передається кодове слово 0000, то з помилкою можуть біти отримані слова, які на рис. 1.27 оточують вказане кодове слово. У такому випадку при появі одиночної помилки з’являються позакодові слова, які відрізняються від кодового слова лише на один біт. Вони не тільки легко можуть бути виявлені, а й виправлені, що відображено стрілками на рис. 1.27. Аналогічна картина має місце і стосовно другого кодового слова. Наприклад, створення позакодового слова 0101 з більшою ймовірністю відповідає кодовому слову 0111, ніж 0000.

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

У загальному плані, якщо код має відстань d = 2b + 1, то він може бути використаним для корекції помилок, що впливають на b бітів. Якщо ж коди мають мінімальну відстань d = 2b + c + 1, то вони можуть бути використані для корекції помилок у b бітах і виявляти помилки в c бітах.

Прикладом такого коду є код Хемінга. Він може бути створений для будь-якого цілого числа і, яке визначає код довжиною (2^і – 1) біт з і розрядів парності і (2^і – 1 – і) інформаційних розрядів з відстанню між кодовими словами 3.

Положення кожного розряду слова коду Хемінга нумерується від 1 до (2^і – 1). Будь-який розряд з номером розміщення в слові, кратний 2, є бітом парності, решта – інформаційні. Кожен біт парності об’єднаний у групу з підконтрольними йому інформаційними бітами. Таке об’єднання зроблено в табл.1.9.

Табл.1.9

Номер розряду	7	6	5	4	3	2	1	Контрольний розряд
Код розряду	111	110	101	100	011	010	001
Група А	Х		Х		Х		Х	20 ( 0 )
Група В	Х	Х			Х	Х		21 ( 1 )
Група С	Х	Х	Х	Х				22 ( 1 )
Біти парності				22		21	20

З табл. 1.9 бачимо, що бітами парності є розряди 1, 2, 4.

У коді кожного біта парності має місце лише одна одиниця, причому її місця у коді розряду різні – відповідно, у першому; другому; третьому. Одиниця біту парності об’єднує в групу ті розряди кодового слова, які мають одиниці у відповідному біті. Наприклад, до групи А об’єднані розряди кодового слова 1, 3, 5, 7, у яких містяться одиниці в першому коді розряду. Оскільки перший біт у цій групі є бітом парності, то решта – підлеглі йому біти, в яких забезпечується перевірка парності. Сформована таким шляхом таблиця, яка доповнена стовбцем контрольного розряду, називається матрицею перевірки парності.

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

У табл. 1.10 приводиться перелік кодових слів для відстані 3 коду Хемінга з чотирма інформаційними бітами.

Табл. 1.10

Інформаційні біти	Біти парності	Інформаційні біти	Біти парності	Інформаційні біти	Біти парності	Інформаційні біти	Біти парності
0000	000	0100	110	1000	111	1100	001
0001	011	0101	101	1001	100	1101	010
0010	101	0110	011	1010	010	1110	100
0011	110	0111	000	1011	001	1111	111

Якщо при передачі інформації в j-му розряді кодового слова зміниться значення біта, то, відповідно, зміниться парність у кожній групі, що містить розряд j. Оскільки кожен інформаційний біт міститься по крайній мірі в одній групі, то по крайній мірі в одній групі буде порушена парність і визначена наявність позакодового слова.

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

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

Допустимо, що на приймальній стороні системи передачі інформації прийнято слово 0100111. Перевіримо це слово, в якому 7-й, 5-й і 4-й розряди мають нульові значення, за допомогою таблиці парності. Результати перевірки заносяться у контрольний розряд. Для групи А 7-й і 5-й розряди мають нульові значення, а 1-й і 3-й – одиниці. Тобто в групі маємо парну кількість одиниць і в контрольний розряд у відповідності з контролем парності заноситься нуль. Аналогічно, в групі В маємо одиниці в розрядах 6, 3, 2, тобто непарну їх кількість, і в контрольний розряд заноситься одиниця. Для групи С у розрядах 7, 6, 5, 4 маємо лише одну одиницю, і в контрольний розряд теж записуємо “1”.

У відповідності до вагових коефіцієнтів груп, у контрольному розряді записано в двійковому коді число 6, якому відповідає біт кодового слова з прийнятою помилкою. У шостому розряді кодового слова стоїть “1”, а повинен бути “0”. Апаратними засобами така помилка може бути виправлена.

Коди Хемінга з кодовою відстанню 3 і 4 знаходять широке використання для визначення і виправлення помилок у модулях пам’яті комп’ютерних систем великої ємності – наприклад, в мультипроцесорних системах і мейнфреймах. Привабливість їх використання в таких модулях обумовлена тим, що кількість бітів парності при зростанні розрядності довжини слова зростає в меншій мірі. Наприклад, при кількості інформаційних біт 4 кількість біт парності дорівнює 3, а при кількості інформаційних біт 26 кількість біт парності зростає до 5.