1 Тетрада 2 тетрада 3 тетрада

Подати вісімкове число 415₈ в двійково-десятковому коді

4 1 5

0100 0001 0101

1 Тетрада 2 тетрада 3 тетрада

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

1.2. Код з надлишковістю три

Код з надлишковістю 3 не використовує перших три і останніх три тет­ради з 16. Ці шість тетрад є псевдотетрадами рис. 3.

Дес-ва цифра	Д	С	В	А
	0	0	0	0	псевдотетради
	0	0	0	1
	0	0	1	0
0	0	0	1	1
1	0	1	0	0
2	0	1	0	1
3	0	1	1	0
4	0	1	1	1
5	1	0	0	0
6	1	0	0	1
7	1	0	1	0
8	1	0	1	1
9	1	1	0	0
	1	1	0	1	псевдотетради
	1	1	1	0
	1	1	1	1

Рис. 3. Код з надлишковістю три

Якщо розглядати тетради коду з надлишковістю 3 у вигляді двійкових чисел, то бачимо, що їх значення весь час більше на три, чим значення відпові­дної десяткової цифри десяткове число 2 подається як 0101, тобто двійковим числом п’ять. З рис. 3. видно, що даний код є симетричним. Як і в двійково-деся­тковому коді, кожна цифра подається тетрадами.

Приклад: Подати число 473 в коді з надлишковістю три

4	7	3
0111	1010	0110

Переваги коду з надлишковістю 3 є відсутність тетради 0000. Оскільки значення логічного 0 відповідає 0 В напруги і логічна 1 – U¹, то тетрада 0000 виникає при випадковому зникненні напруги. Ще однією перевагою даного коду є просте отримання доповнення до 9.

Доповнення до дев’яти в коді з надлишковістю 3 отримуємо прос­тою інверсією.

Приклад: Найти доповнення до 9 до 3₁₀ = 0110

0	1	1	0
				Інверсія
1	0	0	1	= 610

Для додавання в коді з надлишковістю 3 діють такі правила коре­к­ції.

Якщо при додаванні двох тетрад не виникає переносу в 5-тий розряд, то від результату необхідно відняти число 0011.

Якщо при додаванні двох тетрад виникає перенесення в 5-тий розряд, то до кожної тетради результату необхідно додати число 0011.

Приклад: Додати два числа 1₁₀ = 0100 та 3₁₀ = 0110

	0	1	0	0		1
	0	1	1	0		+ 3
	1	0	1	0		4
	1	0	1	0
-	0	0	1	1
	0	1	1	1		= 4

Приклад: Додати два числа 5₁₀ = 1000 та 8₁₀ = 1011

					1	0	0	0		5
					1	0	1	1		+ 8
				1	0	0	1	1		13
			1		0	0	1	1
0	0	1	1	+	0	0	1	1
0	1	0	0		0	1	1	0		= 13

Корекція відбувається за рахунок перенесення в п’ятий розряд. Ця опе­рація легко реалізується в сучасних пристроях цифрової техніки.

1.3. Код Айкена

В коді Айкена використовуються перші і останні п’ять з 16 можливих тетрад. Псевдотетради знаходяться в середині рис. 4. Отримуємо симетричний код, в якому легко знайти доповнення до 9.

Дес-ва цифра	2 Д	4 С	2 В	1 А
0	0	0	0	0
1	0	0	0	1
2	0	0	1	0
3	0	0	1	1
4	0	1	0	0
Псевдо тетради	0	1	0	1
	0	1	1	0
	0	1	1	1
	1	0	0	0
	1	0	0	1
	1	0	1	0
5	1	0	1	1
6	1	1	0	0
7	1	1	0	1
8	1	1	1	0
9	1	1	1	1

Рис. 4. Код Айкена

Доповнення до 9 в колі Айкена отримуємо простою інверсією.

Кожна десяткова цифра подається тетрадою. Для окремих позицій в тет­радах виконується наступне співвідношення:

Д	С	В	А
22	24	22	21

Приклад: Записати число 2007₁₀ за допомогою коду Айкена

2	5	0	7
0010	1011	0000	1101

При додаванні корекція необхідна тільки тоді, коли виникає псевдотет­рада. Тоді використовують наступні правила.

Якщо при додавання двох тетрад в коді Айкена виникає псевдотет­ра­да з переносом в п’ятий розряд, то від результату необхідно відняти число 0110.

Якщо при додавання двох тетрад в коді Айкена виникає псевдотет­рада без переносу в п’ятий розряд, то до результату необхідно додати чис­ло 0110.

Приклад: Додати два десяткових числа в коді Айкена 4₁₀ = 9₁₀.

					0	1	0	0		4
					1	1	1	1		+ 9
	0	0	0	1	0	0	1	1		13

Оскільки при додавання не виникло псевдотетрад - корекція не потрібна.

Приклад: Додати два десяткових числа в коді Айкена 4₁₀ = 3₁₀.

0	1	0	0		4
0	0	1	1		+ 3
0	1	1	1		7

Отримали псевдотетраду, без переносу в п’ятий розряд.

	0	1	1	1
Корекція	0	1	1	0
	1	1	0	1	=	7

Приклад: Додати два десяткових числа в коді Айкена 5₁₀ = 7₁₀.

	1	0	1	1		5
	1	1	0	1	+	7
1	1	0	0	0		12

Псевдотетрада з переносом в п’ятий розряд

				1		1	0	0	0
Корекція					-	0	1	1	0
	0	0	0	1		0	0	1	0	=	12

1.4. Код Грея

Код Грея розроблявся не з точки зору зручності для кодування. Його особливістю є те, що при послідовному переході від тетради до тетради зміню­ється завжди тільки один розряд з 0 на 1 або з 1 на 0. Тобто змінюється тільки один біт тетради рис. 4.

Коди в яких при переході від однієї декади до наступної змінюється лише тільки один біт, називаються однокроковими кодами. Код Грея є од­но­кровковим кодом.

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

дес.-ва цифра	G	R	A	Y		дес.-ва цифра	G	R	A	Y
0	0	0	0	0		0	0	0	0	0
1	0	0	0	1		1	0	0	0	1
2	0	0	1	1		2	0	0	1	1
3	0	0	1	0		3	0	0	1	0
4	0	1	1	0		4	0	1	1	0
5	0	1	1	1		5	0	1	1	1
6	0	1	0	1		6	0	1	0	1
7	0	1	0	0		7	0	1	0	0
8	1	1	0	0		8	1	1	0	0
9	1	1	0	1		9	1	1	0	1
						10	1	1	1	1
						11	1	1	1	0
						12	1	0	1	0
						13	1	0	1	1
						14	1	0	0	1
						15	1	0	0	0

Рис. 4. Код Грея (не циклічний) Рис. 5. Розширений код Грея (циклічний)

Коди Грея дозволяють виключити появу таких помилок. Як правило вони використовуються для задач керування і особливо часто – при зчитування кодуючи дисків. Зображений на рис.4. код Грея має один недолік: при переході від 9₁₀ = 1101 до 0₁₀ = 0000 повинні змінитись три бінарних розряди. В даному випадку говорять – даний код Грея не є циклічним.

Якщо код Грея розширити до всіх можливих 16 тетрад (рис. 5), то отри­маємо код в якому перехід від 15₁₀ = 1000 до 0₁₀ = 0000 також змінюється тільки на один біт. Тоді розширений код Грея буде циклічним.

1.5. Коди, які виявляють помилки

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

Наша мова і писемність містить доволі велику надлишковість. Тільки завдяки надлишковостi можемо ідентифікувати орфографічні помилки та опис­ки. Це можемо пояснити на прикладі інформації без надлишковостi. Цифра 7 подається в двійково-десятковому коді як 0111. Якщо в процесі передачі інфор­мації в другому розряді 1помилково передається як 0, то отримуємо код 0101 – який відповідає цифрі 5. Отже без додаткової інформації ми не дізнаємося, що отримана інформація – 5 є помилковою.

Якщо цифра 7 буде передаватися словом «сім» і в процесі передачі буде змінена одна буква, то помилка буде відразу помітна (наприклад, «сін» - «сім»). Тобто словесна форма містить надлишкову інформацію.

Надлишковість завжди існує в тому випадку, коли крім власне інфор­мації передається додаткове повідомлення, яке допомагає виявити або вип­равити помилку.

Для визначення помилки в багатьох випадках достатньо незначної над­ли­шковостi. Якщо помилка повинна бути не тільки ідентифікована, але і випра­влена, необхідно більше повідомлень – більша надлишковість.

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

Потреба у виявленні та виправленні помилок привела до створення спеціалізованих кодів.

1.6. Розширений двійковий код

Хорошим прикладом для пояснення надлишкового кодування може бу­ти розширений двійковий код. На рис. 6. зображено двійково-десятковий код. Але він містить додатковий 5-тий розряд позначений Е.

П’ятим бітом двійково-десятковий код доповнюється на «парність». Тобто код цифри доповнюється таким чином, щоб кількість бітів, які мають 1 в коді була парною.

Кожна десяткова цифра подається 5-бітовою кодовою комбінацією. 5-біт є додатковою інформацією, тобто надлишковим. Він називається контрольним розрядом або бітом.

Дес-ва цифра	23–8	22–4	21–2	20–1	Е
0	0	0	0	0	0
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	0
4	0	1	0	0	1
5	0	1	0	1	0
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	0

Рис. 6. Створення двійкового Рис. 7. Розпізнавання помилки при розширеного коду. контролі на парність.

Кожна 5-бітова кодова комбінація перевіряється особливою схемою, так званим контролером парності, на парність одиниць рис. 7. Якщо комбінація пар­на Z = 0, якщо не парна – Z = 1. При Z = 1 появляється повідомлення про помилку.

Якщо при передачі даних помилково замість 0 передано 1, або – 1 пере­дана як 0, то виводиться повідомлення про помилку. Визначається тільки те, переданий код десяткової цифри містить помилку. Невідомо, який код має бути насправді, тому помилка не може бути виправлена.

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

На практиці існує багато кодів для виявлення помилок. Прикладом мо­жуть бути: лексикографічний код, код Волкінга, код 7-4-2-1-0, код 8-4-2-1-0. В даних кодах виявлення помилки проходить так як і при двійковому розшире­ному коді, при допомозі на парність рис. 8.

Крім кодових таблиць з 0 і 1 також поширені таблиці переводу. В табли­цях переводу, де поле кожної 1 заштриховане, а поле 0 – порожнє рис 9.

Крім того з 5-бітових комбінацій можливо створити код 3 з 5. Викорис­товується також код 2 з 7, тобто кожна десяткова цифра подається 7 бі­тами. Надлишковість в даному випадку вища ніж в 5-бітових кодах.

	лексикографіч­- ний код					код Волкінга					код 7-4-2-1-0					код 8-4-2-1-0
Номер біта	5	4	3	2	1	5	4	3	2	1	5	4	3	2	1	5	4	3	2	1
Вага	Немає					Немає					7	4	2	1	0	8	4	2	1	0
Де-ва цифра
0	0	0	0	1	1	0	0	0	1	1	1	1	0	0	0	1	0	1	0	0
1	1	1	0	0	0	0	0	1	0	1	0	0	0	1	1	0	0	0	1	1
2	1	0	1	0	0	0	0	1	1	0	0	0	1	0	1	0	0	1	0	1
3	1	0	0	1	0	0	1	0	1	0	0	0	1	1	0	0	0	1	1	0
4	1	0	0	0	1	0	1	1	0	0	0	1	0	1	0	0	1	0	1	0
5	0	1	1	0	0	1	0	1	0	0	0	1	1	0	0	0	1	1	0	0
6	0	1	0	1	0	1	1	0	0	0	0	1	1	0	0	0	1	1	0	0
7	0	1	0	0	1	0	1	0	0	1	1	0	0	0	1	1	1	0	0	0
8	0	0	1	1	0	1	0	0	0	1	1	0	0	1	0	1	0	0	0	1
9	0	0	1	0	1	1	0	0	1	0	1	0	1	0	0	1	0	0	1	0

Рис. 8. Кодувальні таблиці деяких кодів 2 з 5.

	лексикографіч­- ний код					код Волкінга					код 7-4-2-1-0					код 8-4-2-1-0
Номер біта	5	4	3	2	1	5	4	3	2	1	5	4	3	2	1	5	4	3	2	1
Вага	Немає					Немає					7	4	2	1	0	8	4	2	1	0
Де-ва цифра
0
1
2
3
4
5
6
7
8
9

Рис. 9. Таблиці переводу кодів 2 з 5.

1.7. Коди, які виправляють помилки

Перш ніж виправити помилку вона повинна бути виявлена.

Код, який виправляє помилки, також є кодом, який виявляє помилки.

В порівнянні з кодом, який виявляє помилки, код з виправленням поми­лок має більшу надлишковість. Для передачі одного знаку необхідно на декілька біт більше. Наприклад, десяткова цифра подається 7-ма бітами, а не 5-ма – як у кодах, що виявляють помилки.

Більша надлишковість дозволяє виявити помилковий біт. Якщо виявле­но помилковий біт, то власне корекція помилкового біта відносно проста. Якщо помилковий біт містить 1, то виправлене значення – 0. Тобто, помилковий біт має бути інвертовано.

Код з виправлення помилок самостійно проводить корекцію помил­кового біта.

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

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

2.1. Код Хеммінга

Серед кодів, які виявляють помилки, частіше всього використовуються код Хеммінга. Для передачі одної десяткової цифри в коді Хеммінга необхідно 7 біт рис. 10.

По схемі кодування Хеммінга після кожних чотирьох біт даних добавля­ються три контрольних біти.

Кожна контрольна група коду Хеммінга складається з трьох інфор­маційних та одного контрольного біта.

За допомогою контрольного біта три інформаційних біти контрольної групи доповнюються до парного числа 1-стану.

Структура контрольної групи К₂ показана на рис. 11. Інформаційні бі­ти – 5, 6, 7. Контрольний біт – номер 4. при зображенні десяткової цифри 0 інфор­маційні біти не мають 1-станів. Тому контрольний біт також не отри­мує 1-ста­ну. При передачі десяткової цифри 1 інформаційні біти містять один 1-стан. Контрольний біт приймає в цьому випадку 1-стан.Тоді кількість 1-станів конт­рольної групи стане парною.

Номер біта		1	2	3	4	5	6	7
Вага		К0	К1	23	К2	22	21	20
Дес.-ва цифра	0	0	0	0	0	0	0	0
	1	1	1	0	1	0	0	1
	2	0	1	0	1	0	1	0
	3	1	0	0	0	0	1	1
	4	1	0	0	1	1	0	0
	5	0	1	0	0	1	0	1
	6	1	1	0	0	1	1	0
	7	0	0	0	1	1	1	1
	8	1	1	1	0	0	0	0
	9	0	0	1	1	0	0	1
Рис.10. Код Хеммінга

Така ж ситуація має місце при по­дан­ні десяткової цифри 2. При зоб­ра­женні десяткової цифри 3 інформа­ційні біти містять два 1-стани. Кіль­кість 1-станів парна. Контрольний біт приймає в цьому випадку 0-стан. Для десяткових цифр від 4 до 9 контроль­ний біт завжди рівний 1, якщо три ін­фо­рмаційних біти містять непарну кі­лькість 1-станів. Контроль­ний біт завжди рівний 0, якщо три інформаційних біта містіть парну кількість 1-станів.

Номер біта		1	2	3	4	5	6	7		Номер біта		1	2	3	4	5	6	7
Вага					К2	22	21	20		Вага			К1	23			21	20
Дес.-ва цифра	0				0	0	0	0		Дес.-ва цифра	0		0	0			0	0
	1				1	0	0	1			1		1	0			0	1
	2				1	0	1	0			2		1	0			1	0
	3				0	0	1	1			3		0	0			1	1
	4				1	1	0	0			4		0	0			0	0
	5				0	1	0	1			5		1	0			0	1
	6				0	1	1	0			6		1	0			1	0
	7				1	1	1	1			7		0	0			1	1
	8				0	0	0	0			8		1	1			0	0
	9				1	0	0	1			9		0	1			0	1
					Контрольна група К2
Рис. 11. Контрольна група К2										Рис. 12. Контрольна група К1

Структура контрольної групи К₁ складається з інформаційних бітів 3, 6, 7 та контрольного біта – 2 рис. 12. За допомогою контрольного біта К₁ три ін­фо­рмаційних біта контрольної групи доповнюються до парного числа 1-стану. Алгоритм – як у контрольної групи К₂.

Третя контрольна група К₀. Вона складається з інформаційних бітів 3, 5, 7. Контрольний біт К₀ має номер 1 рис. 13.

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

Виявлення помилки відбувається перевіркою на парність контрольних груп.

В коді Хеммінга кожна контрольна група перевіряється на парність.

Номер біта		1	2	3	4	5	6	7
Вага		К0		23		22		20
Дес-ва цифра	0	0		0		0		0
	1	1		0		0		1
	2	0		0		0		0
	3	1		0		0		1
	4	1		0		1		0
	5	0		0		1		1
	6	1		0		1		0
	7	0		0		1		1
	8	1		1		0		0
	9	0		1		0		1
Контрольна група К0
Рис. 12. Контрольна група К0

Для перевірки 7-бітової комбінації необхідні три контролери парності. Вони підключаються згідно рис. 13. При непарності контрольної групи на вихо­ді відповідного контролера появляється 1-стан. Даний стан визначає помилку.

7-бітова комбінація коду Хеммінга містить помилку, якщо хоча б один контролер парності повідомляє про помилку.

Тобто, розпізнавання помилки проходить без труднощів. Виправлення помилки проходить наступним чином. Якщо помилка виникає в біті номер 1, то контролер парності групи К₀ повідомляє про помилку. Вихід Z_А приймає стан 1. Помилка в біті номер 2 викликає повідомлення про помилку контролера парно­с­ті групи К₁ (Z_В = 1). У випадку помилки в біті номер 3 повідомлення про поми­лку видають контролери парності К₀ і К₁. На рис. 14 показано, які контролери парності видають повідомлення про помилку, і стани виходів Z_А, Z_В, Z_С у випа­дку помилок у окремих бітах.

При аналізі рис. 14 видно, що вихі­д­ні стани Z_А, Z_В, Z_С формують двій­ко­ве число, яке відповідає номеру помилково­го біта. Вихід Z_А відповідає 2⁰, Z_В – 2¹, Z_С – 2².

Вихідні стани контролерів парно­сті в коді Хеммінга вказують номер по­мил­ко­вого біта.

Помилка в ном. біта	Повід-ня про помилку	Вихідні стани
		К2 ZС	К1 ZВ	К0 ZА
1	К0	0	0	1
2	К1	0	1	0
3	К0 і К1	0	1	1
4	К2	1	0	0
5	К0 і К2	1	0	1
6	К1 і К2	1	1	0
7	К0 і К2	1	1	1
		22	21	20
Рис. 14. Відповідність повідомлень про помилки вихідним станам контролерів парності

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

В даному розділі розглянуто де­які підходи до створення системи контро­лю передачі даних в цифрових прис­т­роях, тобто виявлення та виправлення по­милок. При цьому необхідно пам’ята­ти, що розрізняють наступні види поми­лок:

1. що виникають в результаті помилки у вихідних даних;

2. обумовлені методичними похибками;

3. які виникають в результаті неправильної роботи пристою.

Перші два типи помилок не є предметом для роботи системи контролю. Перевірка правильності функціонування окремих цифрових пристроїв та вияв­лення помилок відбувається за двома напрямками:

• профілактичний контроль, завдання якого – попередження появи мож­ливих помилок в роботі;

• оперативний контроль, завдання якого – перевірка правильності вико­нання цифровим пристроєм всіх операцій.

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

2.2. Алгоритми ефективного кодування

Алгоритм ефективного кодування Шеннона – Фано формує двійкові ко­ди літер алфавіту за принципом «чим частіше зустрічається літера – тим корот­шим є її код». Послідовність виконання ефективного кодування наступна:

1. літери алфавіту вписуються у таблицю в порядку зменшення ймовір­ності їх появи в тексті;

2. таблиця ділиться на дві групи так, щоб суми ймовірностей у кожній з груп були приблизно однаковими;

3. всім літерам верхньої групи як перший символ коду призначається значення « 1 », а нижньої – « 0 ».

4. для визначення наступних символів дії двох попередніх пунктів (п.п. 2, 3) повторю для кожної групи, до тих пір, поки в групах не залишиться по одній літері.

Розглянемо алфавіт із восьми букв (табл. 2). Зрозуміло, що при звичай­ному (де не враховуються статистичні характеристики) кодуванні для подання кожної літери необхідно три символи.

Таблиця 2.				Таблиця 3.
Літери	Ймові­­­- р­ність	Кодові ком - ції		Літери	Ймові­­­- р­ність	Кодові ком - ції
z1	0,22	11		z1	0,22	11
z2	0,20	101		z2	0,20	10
z3	0,16	100		z3	0,16	011
z4	0,16	01		z4	0,16	010
z5	0,10	001		z5	0,10	001
z6	0,10	0001		z6	0,10	0001
z7	0,04	00001		z7	0,04	00001
z8	0,02	00000		z8	0,02	00000

Обчислимо ентропію набору літер:

(z) = -  2,76

і середня кількість символів на літеру

l_сер = -  2,84

де n(z_і) – кількість символів в кодовій комбінації, яка відповідає літері z_і.

Значення z та l_сер не дуже розрізняються за величиною.

Розглянута методика Шеннона – Фано не завжди приводить до однозна­чної побудови коду. Оскільки при розбитті на підгрупи можемо зробити біль­шою за ймовірністю як верхню, так і нижню підгрупи.

Множину ймовірностей з табл. 2 можемо поділити інакше табл.3.

При цьому середня кількість символів на літеру стає рівною 2,80. Таким чином, реалізований код може бути не найкращим. При побудові ефективних кодів з основою q > 2 невизначеність стає ще більшою.

Від вказаного недоліку вільна методика Д. Хаффмена. Вона гарантує однозначну побудову коду з найменшим для даного розподілу ймовірностей середньою кількістю символів на літеру.

Таблиця 4.
Літера	Ймові- рність	Допоміжні стовбці
		1	2	3	4	5	6	7
z1	0,22	0,22	0,22	0,26	0,32	0,42	0,58	1
z2	0,20	0,20	0,20	0,22	0,26	0,32	0,42
z3	0,16	0,16	0,16	0,20	0,22	0,26
z4	0,16	0,16	0,16	0,16	0,20
z5	0,10	0,10	0,16	0,16
z6	0,10	0,10	0,10
z7	0,04	0,06
z8	0,02

Для двійкового коду методика наступна. Букви алфавіту повідомлення вписуються в основний стовбець в порядку зменшення ймовірностей. Дві оста­нні літери об’єднуються в одну допоміжну літеру, якій призначається сумарна ймовірність. Ймовірність літер, які не приймають участь в об'єднанні, та отри­ма­на результуюча ймовірність розміщаються в порядку зменшення ймовірнос­тей в додатковому стовбці, а дві останні об’єднуються. Кроки повторюються до отримання однієї літери з ймовірністю рівною 1.

Для формування кодової комбінації, що відповідає даному повідомлен­ню, необхідно пройти шлях повідомлення по стрічках та стовбцях. Для наочно­сті будуємо кодове дерево. З точки, що відповідає ймовірності 1, розходяться дві гілки, при чому гілці з більшою ймовір­ні­стю присвоюється символ 1, а з меншою – 0. Така послідовність розгалудження продовжується до тих пір, доки не дійде­мо до кожної літери (рис. 15).

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

z1	z2	z3	z4	z5	z6	z7	z8
01	00	111	110	100	1011	10101	10100

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

Систематичний код – код, який містить в собі, крім інформаційних, кон­трольні розряди.

В контрольні розряди записується деяка інформація про вихідне число. Тому можемо твердити, що систематичний код володіє надлишковістю. При цьому абсолютна надлишковість буде визначатися кількістю контрольних роз­рядів k, а відносна надлишковість – відношенням k/n, де n = m + k – загальна кількість розрядів в кодовому слові (m – кількість інформаційних розрядів).

Поняття коректуючої здатності пов’язують з можливістю виявлення та виправлення помилок. Кількісно коректуючи здатність коду визначається ймо­вірністю виявлення та виправлення помилок. Якщо маємо n-розрядний код і ймовірність спотворення одного символу рівна р, то ймовірність того, що спот­ворено k символів, а інші n – k символів не спотворено, за теоремою перемно­ження ймовірностей визначимо

 = р^k(1 - р)^n-k

Кількість кодових комбінацій, кожна з яких містить k спотворених еле­ментів, рівна кількості комбінацій із n по k:

=

Тоді повна ймовірність спотворення інформації визначається

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

Вага кодової комбінації V(А) – кількість одиниць, які містяться в кодовій комбінації.

Приклад: Знайти вагу та кодову відстань для комбінації А = 011011100, В = 10011101.

Розв’язок. Вага для кодових комбінацій V(А) = V(А) = . Знаходимо кодову комбінацію С = А  В = 111100101, для якої визначається вага, рівна кодовій відстані для А і В: V(С) = d(А, В) = .

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