Тема 22. Кодування стійке до завад

В середині 40-х років 20 ст. Річард Геммінг працював у Лабораторіх Белла (Bell Labs) на обчислювальній машині Ball Model V. Це була електромеханічна машина, яка використовувала релейні блоки, швидкість яких була дуже низька: один оберт за декілька секунд. Дані вводились в машину за допомогою перфокарт і тому в процесі зчитування часто відбувались помилки. В робочі дні використовувались спеціальні коди, які виявляли та виправляли знайдені помилки, при цьому оператор дізнавався про помилку по спеціальному світовому сигналу, виправляв та запускав машину. У вихідні дні, коли не було операторів, при виникненні помилки машина автоматично виходила з програми та запускала іншу.

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

22.1. Коди стійкі до перешкод

Розглянемо один частковий випадок рівномірного двійкового кодування, коли А = В = {0, 1}. Розглянемо схему рівномірно кодування _k,n:

₁  ₁,

₂  ₂,

…

,

де _i, _i – відповідно слова довжиною k та n, n>k. Говорять, що схему _k,n задає код V = {₁, ₂,…, } .

Введемо додаткові позначення. Елементи множини (двійкові вектори довжиною n) позначатимемо великими латинськими буквами X, Y, Z,…, а їх компоненти – відповідними малими буквами з індексами. Зокрема, елементарні коди позначатимемо як традиційно (₁, ₂,…), так і X, Y, Z залежно від контексту.

Означення 22.1. Нормою двійкового вектора Х = x₁x₂…x_n називають число, яке дорівнює кількості його одиничних компонент. Отже:

Припустимо, що в каналі зв’язку діє джерело адитивних перешкод, яке описують множиною P(n, t). Її елементи – двійкові вектори-помилки. При чому на n переданих поспіль двійкових символів припадає не більше ніж t помилок. Це означає, що коли на вході каналу зв'язку передано повідомлення , то на виході можна отримати будь-яке слово з множини { | P(n, t), || = ||}, де  - поразрядне додавання за mod 2.

Позаяк проблема локалізації інформації (тобто розділення закодованого повідомлення на елементарні коди) у моделі рівномірного кодування тривіальна, то виявлення помилок полягає у відшуканні незбігу локалізованої групи n символів, яке не відповідає жодному з елементарних кодів. Якщо через помилку елементарний код перейде в інший елементарний код, то помилку не буде виявлено. Іноді можна виправити помилку. Якщо групу бітів локалізовано правильно, то для цього необхідно й достатньо, щоб помилкова група була «синонімом» єдиного елементарного коду.

---

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

Означення 22.2. Віддалю Геммінга називають функцію (X, Y) двох змінних, означену на множині :

.

Тобто, віддаль Геммінга дорівнює кількості розрядів, у яких вектори Х та Y не збігаються.

Означення 22.3. Скалярний добуток двійкових векторів X, Y означається як:

Відповідно він дорівнює кількості розрядів, у яких Х та Y збігаються й дорівнюють 1.

Легко перевірити таке співвідношення:

,

(22.1)

де 0 – n-вимірний вектор із нульовими компонентами;

,	(22.2)
,	(22.3)
.	(22.4)

Для віддалі Геммінга виконуються аксіоми метрики:

• (X, Y)  0, причому (X, Y) = 0 в тому лише випадку, коли X = Y;

• (X, Y) = (Y, X);

• (X, Y) + (Y, Z)  (X, Z) (нерівність трикутника).

Метрика Геммінга – зручне математичне поняття для формулювання умов надійності кодування в разі адитивних помилок.

Означення 22.4. Нехай систему _k,n задано кодом V = {₁, ₂, …,  }. Кодовою віддалю для коду V називають величину:

(V) = min {(X,Y) | X, Y  V, XY }.

Теорема 22.1. Якщо в каналі зв'язку діє джерело адитивних перешкод P(n, t), то правдиві такі твердження.

1. Для виявлення будь-яких помилок необхідно й достатньо, щоб (V) > t.

2. Для виправлення будь-яких помилок необхідно й достатньо, щоб (V) > 2t.

Доведення. 1. Нехай (V) > t. Якщо XV, ZP(n, t), Z0, то, використовуючи спочатку рівність (22.3), а потім – (22.1), можемо записати (X, XZ) = (XX, XXZ) = (0, Z) = ||Z||  t. Отже, XZV, і помилку виявлено.

Навпаки, нехай (X, Y)  t й X, YV, XY. Тоді, застосувавши рівність (22.2), маємо ||XY|| = (X, Y)  t; отже, Z = XY  P(n, t). Звідси випливає, що XZ = Y, тобто помилку в елементарному коді Y виявити не можна.

2. Нехай (V)>2t. Якщо XV, ZP(n, t), то X – єдиний елементарний код із V, який міг перейти внаслідок помилки в XZ. Справді, припустимо, що існує такий двійковий вектор YX, що YV та YZ₁ = XZ для якогось Z₁ P(n, t). Додавши до обох частин останньої рівності XZ₁, отримаємо YX = Z₁Z. Але, згідно з рівністю (22.2) можемо записати ||XY|| = (X, Y) > 2t, а ||Z₁Z||  ||Z₁|| + ||Z||  2t. Одержали суперечність.

Навпаки, нехай (X, Y)  2t для якихось різних X, Y V. Тоді ||XY||  2t, й існують такі двійкові вектори Z₁, Z₂, що ||Z₁||  t, ||Z₂||  t (тобто вони належать P(n, t)) та XY = Z₁Z₂. Додавши до обох частин останньої рівності YZ₁, одержимо XZ₁ = YZ₂ = W. Отже, у разі отримання спотвореного елементарного коду W неможливо виявити, що було передано насправді: X чи Y. ►

Доведене твердження має геометричну інтерпретацію.

Означення 22.5. Множину S_t(X) = {Z | (X, Z)  t} називають кулею радіусом t з центром у точці X.

Теорема 22.2 (без доведення). Якщо в каналі зв'язку діє джерело адитивних перешкод P(n, t), то правдиві такі твердження.

---

1. Для виявлення будь-яких помилок необхідно й достатньо, щоб для будь-якого XV куля S_t(X) не містила інших елементарних кодів, окрім X.

2. Для виправлення будь-яких помилок необхідно й достатньо, щоб для будь-яких X, Y V було виконано умову S_t(X)  S_t(Y) = .

Означення 22.6. Рівномірне кодування _k,n: _i  _i (i = 1, 2,…, 2^k) називають систематичним, якщо можна виділити множину k розрядів I = {i₁,…,i_k}{1,2,…,n}, які називаються інформаційними, так, що коли _i = x₁…x_n (i = 1, 2,…, 2^k), то _i = x_i1…x_ik. Решту розрядів у такому разі називають контрольними.

22.2. Коди з самоконтролем

Як було показано в теоремі 22.1 для автоматичного виявлення помилок достатньо, щоб кодова віддаль (V) була більша за кількість можливих помилок t на n переданих бітів інформації. Розглянемо кодування таблиці символів ASCII, в якій представлено 256 записів. Для кодування елементів таблиці використовується один байт – вісім бітів. Легко бачити, що кодова віддаль (V) для таблиці ASCII буде складати 1 (наприклад, відстань між кодом 00000000 та 00000001 складає якраз 1). Таким чином, якщо t = 1, то ми не зможемо автоматично виявляти помилки. Отже, (V) повинно бути не менше 2. Як цього можна досягнути?

На практиці використовується наступна схема. До кожного інформативного байту (8 розрядів) додається ще один розряд, який називається контрольним. Значення контрольного розряду встановлюється таким чином, щоб загальна кількість одиничних розрядів була парною (враховуючи як інформативні розряди, так і контрольні). Тоді, замість 8 розрядів буде передаватись 9. В попередньому прикладі ми отримуємо коди 000000000 та 000000011 (контрольний розряд позначений жирним). Як бачимо, в даному прикладі відстань між кодами вже становить 2, що призведе до автоматичного виявлення помилки.

Такий підхід дозволяє виявляти помилки, які відбулись в одному розряді, але не працює для помилок в більшій кількості розрядів. Наприклад, якщо ми хочемо передати код 00000000, то повинні додати ще контрольний розряд 0, і, зрештою, відправити повідомлення 000000000. Якщо помилки відбулись, припустимо, в двох розрядах і ми отримали, наприклад, код 100010000. В такому випадку кількість одиниць є парною і контрольний розряд містить 0, що є коректним з точки побудови коду. Отже, помилки не зможуть бути виявлені. Звісно, також даний підхід не дозволяє з’ясувати в якому саме розряді відбулась помилка.

22.3. Коди з самовиправленням

Нижче розглянемо коди, які дозволяють виправлення при одиничній помилці (тобто коли t = 1).Можна показати, що кількість контрольних розрядів k повинна бути обрана такою, щоб виконувалась рівність: або , де n – кількість інформативних розрядів. Мінімальні значення k для заданого n наведені в таблиці 22.1

Діапазон n	Мінімальне k
1	2
2 – 4	3
5 – 11	4
12 – 26	5
27 – 57	6

---

Табл. 22.1

Перевіримо справедливість наведеної кількості контрольних кодів для найпростіших випадків. Розглянемо n = 1. Зрозуміло, що можливі тільки два коди: X₁=0 та X₂=1. В даній системі кодова віддаль (V)=1. За теоремою 22.1 (V) повинно бути не менше 3 ((V)>2), щоб код дозволяв автоматичне виправлення одиничних помилок. Якщо до кодів X_i додати тільки один контрольний розряд, то відстань складатиме лише 2 (X₁=00 та X₂=11). Отже, необхідно додати мінімум 2 контрольних розряди, щоб уможливити автоматичну корекцію одиничних помилок: X₁=000 та X₂=111. Дійсно, припустимо ми передавали код X₁ і відбулась помилка в другому розряді – ми отримали код X´=010. Знаючи, що помилка можлива тільки в одному розряді, ми легко бачимо, що код X´ міг бути отриманий тільки з коду X₁, адже від коду X₂ його віддаляє дві помилки (потрібно змінити два розряди в X₂ щоб отримати X´).

Тепер розглянемо n = 2. Тут можуть існувати чотири різні коди: X₁=00, X₂=01, X₃=10, X₄=11. За теоремою 22.1 (V) знову повинно бути не менше 3, тобто коди повинні відрізнятись як мінімум трьома розрядами. З табл. 22.1 видно, що кількість контрольних розрядів повинна дорівнювати 3, щоб дозволити автоматичну корекцію. Нижче наводиться одне з можливих приписувань значень контрольним розрядам, яка задовольняє умови теореми 22.1.

X1:	00000
X2:	01011
X3:	10101
X4:	11110

Відповідні значення відстаней між кодами становитимуть: (X₁,X₂) = 3, (X₁,X₃) = 3, (X₁,X₃) = 4, (X₂,X₃) = 4, (X₂,X₄) = 3, (X₃,X₄) = 3. Отже, (V) = 3.

Загалом можлива наступна схема визначення значень контрольних розрядів у випадку виправлення одиночних помилок. Припишемо кожному з розрядів (інформативним та контрольним) свій власний номер від 1 до n+k. Запишемо ці номери у двійковій системі. Оскільки 2^k > n+k, то кожний номер можна представити k-розрядним двійковим числом.

Припустимо далі, що всі n+k розрядів коду розбиті на контрольні групи, які частково перетинаються, причому так, що одиниці у двійковому представленні номеру розряду вказують на його приналежність до певної контрольної групи. Наприклад, розряд №5 належить до першої та третьої контрольним групами, тому що у двійковому представленні його номеру 5₁₀ = …000101₂ 1й та 3й розряди містять одиниці.

Серед n+k розрядів при цьому є k розрядів, кожний з яких належить тільки одній контрольній групі: 1₁₀ = …000001₂, 2₁₀ = …000010₂, 4₁₀ = …000100₂, … Ці k розрядів будемо вважати контрольними. Інші n розрядів, кожний з яких належить принаймні двом контрольним групам, будуть інформативними розрядами. В кожній контрольній групі буде по одному контрольному розряду. При цьому в кожний контрольний розряд помістимо таку цифру (0 або 1), щоб загальна кількість одиниць в його контрольній групі була парною.

Розглянемо випадок, коли n=8. За табл. 22.1 маємо, що k=4. Нехай початковий інформативний байт (без контрольних розрядів) є 01101011. Позначимо k_i i-й контрольний розряд та n_i i-й інформативний розряд.

---

№ розряду	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100
	k1	k2	n1	k3	n2	n3	n4	k4	n5	n6	n7	n8
Інформаційне кодове слово			0		1	1	0		1	0	1	1
k1	1		0		1		0		1		1
k2		0	0			1	0			0	1
k3				1	1	1	0					1
k4								1	1	0	1	1
Кодове слово з контрольними розрядами	1	0	0	1	1	1	0	1	1	0	1	1

Як видно, всі контрольні групи перекриваються між собою. Наприклад, перша група контролює розряди n₁, n₂, n₄, n₅ та n₇. Друга група – n₁, n₃, n₄, n₆ та n₇. Очевидно, що вони перетинаються.

Припустимо тепер, що при передачі даного коду 100111011011 відбулась помилка в 11-му розряді і ми отримали код 100111011001. Виконавши перевірку парності одиниць в кожній контрольній групі, ми виявили, що кількість одиниць стала непарною в групах №1, №2 та №4, а в групі №3 лишилась парною. Це, по-перше, вказує на наявність помилки, а, по-друге, означає, що номер помилкового розряду містить у двійковому представленні одиниці на першому, другому та четвертому місці та нуль на третьому місці, адже в третій групі помилку не виявлено (а тому помилковий розряд не входить у третю групу).

№ розряду	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	Парність
	k1	k2	n1	k3	n2	n3	n4	k4	n5	n6	n7	n8
Передане слово	1	0	0	1	1	1	0	1	1	0	1	1
Отримане слово	1	0	0	1	1	1	0	1	1	0	0	1
k1	1		0		1		0		1		0		Помилка
k2		0	0			1	0			0	0		Помилка
k3				1	1	1	0					1	Вірно
k4								1	1	0	0	1	Помилка

Побудований код, звісно, не спроможний виявляти подвійні помилки. Наприклад, якщо помилка при передачі відбудеться в розрядах №3 та №6, так що отримали слово 101110011011.

№ розряду	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	Парність
	k1	k2	n1	k3	n2	n3	n4	k4	n5	n6	n7	n8
Передане слово	1	0	0	1	1	1	0	1	1	0	1	1
Отримане слово	1	0	1	1	1	0	0	1	1	0	1	1
k1	1		1		1		0		1		1		Помилка
k2		0	1			0	0			0	1		Вірно
k3				1	1	0	0					1	Помилка
k4								1	1	0	1	1	Вірно

---

Смотрите также файлы

• 30_Algoritmi_poshuku_naykorotshikh_shlyakhiv.doc

• 35_Merezhi_ta_potoki.doc

• 37_Gramatiki.doc

• 38_Skinchenni_avtomati.doc

• dinamika.docx