Надлишкові коди

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

Надлишкові коди, що дозволяють виявляти і виправляти помилки, називаються завадостійкими.

Основні характеристики надлишкових кодів:

• Вага коду по mod2 - кількість одиниць у коді, B = {0, 1}

Приклад:

Вага коду 01011101010 дорівнює w=6;

• Кодова відстань за mod2 між двома кодами k₁ і k₂ (позначається d₀(k₁, k) дорівнює вазі коду k₃ = k₁  k₂

Приклад:

k ₁ = 01011101010

k ₂ = 00110110111

k ₃ = 01101011101

d₀ (k₁,k₂) = 7

• Вектор помилки коду k₁. Нехай k₂ - код помилково прийнятий замість k₁, тоді вектор помилки є p(k₁, k₂)= k₁  k₂.

Приклад:

k ₁ = 01011101010

k ₂ = 00110110111

p(k₁, k₂)= 01101011101

• Кратність помилки - вага вектора помилки.

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

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

Для двійкових кодів лінійною операцією є додавання по модулю 2 (позначається знаком  ), яке характеризується наступними рівняннями:

0  0 = 0; 1  1 = 0; 0  1 = 1; 1  0 = 1.

Приклад:

Сума по mod2 комбінацій систематичного коду є комбінацією цього жкоду.

Декодування систематичних кодів основане на перевірці лінійних співвідношень між символами на коригуючих позиціях. У випадку двійкового коду перевірка зводиться до перевірки на парність. При парній кількості одиниць додавання по модулю 2 дає в сумі 0, інакше - 1.

Систематичні коди зручно отримувати з допомогою породжуючої та перевірочної матриць.

Породжуючоюназивається матриця, при допомозі якої будується код.

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

Маючи n_i розрядів, можна утворити кодових комбінацій. З них ненульовими будутькомбінацій.

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

, (2)

де - задумане число,

,

або ,(3)

де n - загальна кількість розрядів.

Оскільки

, то

(4)

Формули (3) і (4) встановлюють співвідношення між числом інформаційних n_i та коригуючих n_k розрядів.

Число рядків породжуючої матриці і її ранг дорівнюють n_i, а кількість стовпчиків n = n_i + n_k.

Кодові комбінації находяться шляхом додавання по mod2 всіх можливих сполучень рядків по 2, 3 і т.д. до суми всіх рядків. Нульова комбінація також включається до числа кодових.

Наприклад, для d₀ = 2 породжуюча, інформаційна та перевірочна матриці можуть мати такий вигляд:

інформаційна

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1

перевірочна

1

1

1

1

породжуюча

1	0	0	0	1
0	1	0	0	1
0	0	1	0	1
0	0	0	1	1

Для наведених матриць кілька комбінацій коду, що виявляє одну помилку знаходяться так:

№ кодової	Кодові комбінації		Номери
комбінації	інформаційні розряди	Коригуючі розряди	рядків, що додаються
1	0000	0	0
2	1000	1	1
3	0100	1	2
4	0010	1	3
……	…….	…….	…….
6	1100	0	1  2
……	…….	…….	…….
12	1110	1	1  2  3

Для кодів з d₀  3 параметри породжуючої матриці визначаються, виходячи з кількості інформаційних розрядів та заданих коригуючих властивостей коду.

Приклад:

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

Число інформаційних розрядів матриці n_i = 4 оскільки 16 = 2⁴ . Відповідно і число рядків матриці дорівнює 4. Найпростішою інформаційною матрицею є одинична.

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1

Число коригуючих розрядів для коду з d₀ = 3 дорівнює

n_k = log₂ [ 5 + ( log₂ 5 )] = log₂ 8 = 3 (5)

Таким чином, загальна кількість стовпчиків матриці дорівнює n = n_i + n_k = 4+3=7.

Оскільки вага кожного рядка перевірочної матриці повинна бути w_kd₀-w_i , то рядками перевірочної матриці можуть бути вибрані тризначні двійкові комбінації з числом одиниць, більшим чи дорівнюючим 2 (d₀ = 3 , w_i = 1 ), наприклад:

0	1	1
1	0	1
1	1	0
1	1	1

Остаточний вигляд породжуючої матриці

1	0	0	0	0	1	1
0	1	0	0	1	0	1
0	0	1	0	1	1	0
0	0	0	1	1	1	1

Згенеровані на основі цієї матриці інформаційні частини кодових комбінацій мають такий вигляд:

№ кодової комбінації	інформаційні розряди кодової комбінації	Номери рядків, що додаються
1	0000	0
2	1000	1
3	0100	2
4	0010	3
5	0001	4
6	1100	1  2
7	1010	1  3
8	1001	1  4
9	0110	2  3
10	0101	2  4
11	0011	3  4
12	1110	1  2  3
13	0111	2  3  4
14	1011	1  3  4
15	1101	1  2  4
16	1111	1  2  3  4

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

№ кодової	Кодові комбінації		Номери
Комбінації	інформаційні розряди	Коригуючі розряди	рядків, що додаються
1	0000	000	0
2	1000	011	1
3	0100	101	2
4	0010	110	3
5	0001	111	4
6	1100	110	1  2
7	1010	101	1  3
8	1001	100	1  4
9	0110	011	2  3
10	0101	010	2  4
11	0011	001	3  4
12	1110	000	1  2  3
13	0111	100	2  3  4
14	1011	010	1  3  4
15	1101	001	1  2  4
16	1111	111	1  2  3  4

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

• в першу перевірку разом з перевірочним розрядом p₁ входятьінформаційні розряди, які відповідають одиницям першого стовпчика перевірочної матриці;

• в другу перевірку входитьперевірочний розряд p₂ і інформаційні розряди, які відповідають одиницям другого стовпчика перевірочної матриці і т.д.;

• число перевірок дорівнює числу розрядів корегуючого коду.

В результаті перевірок утворюється перевірочний вектор s ( s₁, s₂ , … ,s_nk ),що називається синдромом. Якщо число одиниць розрядів, що перевіряються – парне, то значення відповідного розряду синдрому дорівнює 0, інакше - 1. Комбінація прийнята безпомилково, якщо вага синдрому дорівнює нулю.

Помилка виправляється за виглядом синдрому ( кожному помилковому розряду відповідає один єдиний перевірочний вектор ).

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

Приклад:

Для розглянутого раніше коду система перевірок має вигляд:

p₁  a₂  a₃  a₄ = s₁

p₂  a₁  a₃  a₄ = s₂

p₃  a₁  a₂  a₄ = s₃

Контрольна матриця має вигляд:

	a1	a2	a3	a4	p1	p2	p3
s1	0	1	1	1	1	0	0
s2	1	0	1	1	0	1	0
s3	1	1	0	1	0	0	1

Якщо синдром має вигляд s=011, то помилка в першому розряді, приs=101 – в другому, і т.д.

Нехай передана комбінація

a1	a2	a3	a4	p1	p2	p3
0	0	0	1	1	1	1

а прийнята комбінація

a1	a2	a3	a4	p1	p2	p3
1	0	0	1	1	1	1

тоді

p₁  a₂  a₃  a₄ = 1  0  0  1 = 0 = s₁

p₂  a₁  a₃  a₄ = 1  1  0  1 = 1 = s ₂

p₃  a₁  a₂  a₄ = 1  1  0  1 = 1 = s₃

Тобто s = 011 – перший стовпчик контрольної матриці – помилка в першому розряді.

Тепер, нехай передана та сама комбінація, а прийнята

a1	a2	a3	a4	p1	p2	p3
0	0	0	1	1	1	0

Тоді

p₁  a₂  a₃  a₄ = 1  0  0  1 = 0 = s₁

p₂  a₁  a₃  a₄ = 1  0  0  1 = 0 = s ₂

p₃  a₁  a₂  a₄ = 0  0  0  1 = 1 = s₃

Тобто s = 001 – сьомий стовпчик контрольної матриці – помилка в сьомому розряді.

Код Хеммінга.Одним з найбільш поширених систематичних кодів з простим механізмом знаходження виправлення помилок є код Хеммінга.

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

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

,(6)

але

,(7)

або

,

де - нове число комбінацій коду.

Алгоритм побудови коду Хеммінга такий:

• Задається кількість інформаційних символів n_i ;

• При допомозі формул (6) і (7) обчислюють n і n_k (співвідношення міжn, n_iтаn_kнаведені в табл. 4.);

Табл. 4. Співвідношення між кількістю інформаційних та контрольних символів в коді Хеммінга.

n	nі	nк	n	nі	nк
1	0	1	9	5	4
2	0	2	10	6	4
3	1	2	11	7	4
4	1	3	12	8	4
5	2	3	13	9	4
6	3	3	14	10	4
7	4	3	15	11	4
8	4	4	16	11	5

• визначають інформаційні та коригуючі позиції кодових комбінацій.

(практично номери коригуючих символів зручно вибирати за законом 2ⁱ де i = 0, 1, 2, 3, тобто 1, 2, 4, 8, 16 ...);

• визначають контрольні суми (0 чи 1) за правилом - сума одиниць на контрольних позиціях повинна бути парною (якщо сума парна - значення контрольного коефіцієнта 0, інакше 1).

Номери позицій, що входять у контрольні суми, вибирають так: складають таблицю для ряду натуральних чисел в двійковому коді ( кількість розрядів дорівнює числу інформаційних символів). Число рядків n = n_i + n_k

0001	a1
0010	a2
0011	a3
0100	a4
0101	a5
0110	a6
0111	a7
1000	a8

Першому рядку відповідає коефіцієнт а₁, другому а₂ і т.д.

- в першу перевірку входять коефіцієнти, що містять 1 в молодшому розряді, тобто

s₁ = а ₁  a₃  a₅  a₇ …= 0,

- в другу перевірку входять коефіцієнти, що містять 1 в другому розряді

s₂ = а ₂  a₃  a₆  a₇ …= 0

і т.д.

Табл. 5. Номери контрольних позицій коду Хеммінга

№ перевірки	Перевірочні позиції (П)	№ коригуючого символу
1	1, 3, 5, 7, 11, ...	1
2	2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 24, ...	2
3	4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, ...	4
4	8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, ...	8

Табл. 6. Побудова коду Хеммінга

Позиція символів	Кодове слово
коду	без значень коригуючих символів	зі значеннями коригуючих символів
1	a1	0
2	a2	1
3	0	0
4	a3	0
5	1	1
6	0	0
7	1	1

Приклад: Нехай требавиправити будь-яку одиночну помилкупри передачі кодової комбінації 0101.

• Кількість інформаційних символів n_k = 4;

• Згідно з таблицею кількість корегуючих символів n_k = 3;

• Загальна кількість символів n = 7;

• Коригуючі символи розміщені на позиціях 1,2,4 , тобто кодова комбінація має вигляд:

a₁ a₂ 0 a₄ 1 0 1

• Невідомі a₁ , a₂ , a₄ знаходять з умови, що контрольні суми дорівнюють нулю

s₁ = а ₁  a₃  a₅  a₇ = 0

s₂ = а ₂  a₃  a₆  a₇ = 0

s₃ = а ₄  a₅  a₆  a₇ = 0,

звідки :

a₁ = a₃  a₅  a₇ = 0  1  1 = 0;

a₂ = a₃  a₆  a₇ = 0  0  1 = 1;

a₄ = a₅  a₆  a₇ = 1  0  1 = 0,

тобто кодова комбінація має вигляд:

0 1 0 0 1 0 1

(в двійковій арифметиці 1 1= 0, значить, -1 =1, тобто доданки можна переносити з одної частини рівності в іншу без зміни знаку).

• Нехай замість 0 1 0 0 1 0 1 було прийнято 0 1 0 0 1 1 1.

Знайдемо контрольні суми:

s₁ = а ₁  a₃  a₅  a₇ = 0  0  1  1= 0

s₂ = а ₂  a₃  a₆  a₇ = 1  0  1  1= 1

s₃ = а ₄  a₅  a₆  a₇ = 0  1  1  1 = 1

Таким чином номер помилкової позиції s₃ s₂ s₁ = 110₂= 6₁₀, і в шостій позиції символ 1 треба замінити на 0.

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

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

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

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

0 0 0 1 0 1 0  x⁵ + 0  x⁴ + 0  x³ + 1  x² + 0  x¹ + 1  x⁰ = x² + 1;

0 0 1 0 1 0 0  x⁵ + 0  x⁴ + 1  x³ + 0  x² + 1  x¹ + 0  x⁰ = x³ + x;

0 1 0 1 0 0 0  x⁵ + 1  x⁴ + 0  x³ + 1  x² + 0  x¹ + 0  x⁰ = x⁴ + x²;

1 0 1 0 0 0 1  x⁵ + 0  x⁴ + 1  x³ + 0  x² + 0  x¹ + 0  x⁰ = x⁵ + x³;

Циклічні коди значності n утворюються з кодів значності n_i шляхом множення деякого основного коду значності n_i на утворюючий поліном ступеня n-n_i і наступною циклічною перестановкою символів у отриманому коді.

Алгоритм побудови циклічного коду такий.

1. Вибрати початкову кодову комбінацію значності n_i.

2. За заданими кратностями помилок, що виявляються і виправляються, визначити за формулою (5) кількість коригуючих розрядів, а потім значність n надлишкового коду.

3. З табл. 7 для n - n_i вибрати породжуючий многочлен P_k (x) .

Табл. 7.

n - ni	Многочлен	Двійковий код
2	x^2+ x + 1	111
3	x^3 + x + 1	1011
4	x^4 + x + 1	10011
5	x^5+ x2 + 1	100101
6	x^6 + x + 1	1000011
7	x^7 + x+ 1	10000011
8	x^8+ x^4 + x^3 + x + 1	100011011

4. Для початкової кодової комбінації записати поліном I(x).

5. Отримати код значності n з коефіцієнтів результату множення

F(x)=P_k (x)  I(x).

6. Побудувати всі інші дозволені коди з початкової кодової комбінації циклічними перестановками символів з наступним виконанням пунктів 4 та 5.

Приклад.

Нехай є початкова кодова комбінація 1010 (n_i = 4), а код повинен виявляти двократну помилку і виправляти однократну (n_k = 3; n = 7). Згідно з табл. 7 для n - n_i = 3 породжуючим буде поліном P₃(x) = x³ + x + 1. Початкова кодова комбінація представляється поліномом I(x) = x³ + x.

Тоді

F(x)= I(x)  P₃(x) = x⁶ + x⁴ + x³ + x⁴ + x² + x = x⁶ + x³ + x² + x  1001110 ,

оскільки x⁴ + x⁴ = 0 при додаванні по mod2 ).

З початкової кодової комбінації 1010 шляхом циклічних перестановок отримаємо інші початкові комбінації, і аналогічно побудуємо на їх основі n-значні коди.

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

Наприклад, для утвореної раніше комбінації

x⁶+ 0* x⁵+0* x⁴+ x³ +x²+x + 0 \ x³ + x + 1

x⁶ + 0* x⁵ + x⁴ + x³ x³+ x

x⁴ + 0 + x² + x

x⁴ + 0 + x² + x ,

або безпосередньо через кодові комбінації

1001110 | 1011

1011 1010

1011

1011 .

Якщо є залишок, то комбінація має помилку.

Нехай замість правильної комбінації 1001110 було прийнято комбінацію 1001010 , тоді

x⁶+ 0* x⁵+0* x⁴+ x³ + 0*x²+x + 0 \ x³ + x + 1

x⁶ + 0* x⁵ + x⁴ + x³ x³+ x + x²/ (x³+ x+ 1)

x⁴ + 0 + 0 + x

x⁴ + 0 + x² + x

x²+ 0 + 0 ,

або

1001010 | 1011

1011 1010

1001

1011

100 .

Процедура виправлення помилки має такий вигляд:

1. Підраховується кількість одиниць у залишку ( вага залишку W).

2. Якщо W  S , де S - число помилок, що виправляються даним кодом, то виправлена комбінація отримується шляхом додавання по mod2 залишку до прийнятої комбінації;

3. Якщо W > S , виконується циклічний зсув прийнятої комбінації на один розряд вліво і знову знаходиться залишок від ділення отриманої комбінації на породжуючий многочлен до того часу, поки не буде отримано W  S, після чого виконується пункт 2 ;

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

Приклад:

У наведеному вище випадку W = S =1 і 1001010  100 = 1001110 – правильна комбінація.

Якщо ж було прийнято комбінацію 1101110, то виконуємо ділення многочленів

1101110 | 1011

1011. 1111

1101

1011

1101

1011

1100

1011

111 оскільки W = 3 > S =1 ,

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

1011101 | 1011

1011 1000

101 оскільки W = 2 > S =1 ,

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

0111011| 1011

0000 0110

1110

1011

1011

1011

1. і , оскільки W = 1 = S =1,

то додаємо по mod2 залишок до комбінації

0111011  1 = 0111010 ,

робимо першу циклічну перестановку вправо

0011101 ,

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

1001110 – правильна комбінація.