Основи економного кодування

Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Основи економного кодування»
МІНСЬК, 2009

Повідомлення, передані з використанням РТС ПІ (мова, музика, телевізійні зображення і т.д.) в більшості своїй призначені для безпосереднього сприйняття органами почуттів людини і зазвичай погано пристосовані для їх ефективної передачі по каналах зв'язку. Тому вони в процесі передачі, як правило, піддаються кодуванню.
Що таке кодування і навіщо воно використовується?
Під кодуванням в загальному випадку розуміють перетворення алфавіту повідомлення A {λ _i }, (I = 1,2 ... K ) В алфавіт деяким чином вибраних кодових символів  {x _j }, ( j = 1,2 ... N ). Зазвичай (але не обов'язково) розмір алфавіту кодових символів dim  {x _j } Менше або набагато менше розміру алфавіту джерела dim A {λ _i }.
Кодування повідомлень може переслідувати різні цілі. Наприклад, це кодування з метою засекречування переданої інформації. При цьому елементарним повідомленнями l _i з алфавіту A {λ _i } Ставляться у відповідність послідовності, наприклад, цифр або букв із спеціальних кодових таблиць, відомих лише відправнику і одержувачу інформації.
Іншим прикладом кодування може служити перетворення дискретних повідомлень l _i з одних систем числення в інші (з десяткової в двійкову, вісімкову і т. п., з непозиційній на позиційну, перетворення літерного алфавіту в цифровій і т. д.).
Кодування в каналі, або завадостійке кодування інформації, може бути використано для зменшення кількості помилок, що виникають при передачі по каналу з перешкодами.
Нарешті, кодування повідомлень може здійснюватися з метою скорочення обсягу інформації та підвищення швидкості її передачі та скорочення смуги частот, необхідних для передачі. Таке до одірованіе називають економним, безнадлишкових, або ефективним кодуванням, а також стисненням даних. У даному розділі буде йти мова саме про такого роду кодування. Процедурі кодування зазвичай передують (і включаються до неї) дискретизація і квантування безперервного повідомлення λ (t), тобто його перетворення в послідовність елементарних дискретних повідомлень {λ _iq}.
Перш ніж перейти до питання економного кодування, коротко пояснимо суть самої процедури кодування.
Будь-яке дискретне повідомлення l _i з алфавіту джерела A {λ _i } Об'ємом в K символів можна закодувати послідовністю відповідним чином вибраних кодових символів x _j з алфавіту Â {x _j}.
Наприклад, будь-яке число (а l _i можна вважати числом) можна записати в заданій позиційній системі числення наступним чином:
l _i = M = x _{n - 1} × m ^n-1 + x _n-2 × m ^n-2 + ... + x ₀ × m ^0, (1)
де m - основа системи числення; x ₀ ... x _n-1 - Коефіцієнти при ступенях m; x Ì 0, m - 1.
Нехай, наприклад, значення l _i = M = 59, тоді його код по підставі m = 8, буде мати вигляд
M = 59 = 7.8 ¹ + 3.8 ⁰ = 73 _8.
Код того ж числа, але по підставі m = 4 буде виглядати наступним чином:
M = 59 = 3 × 4 ² + 2 × 4 ¹ + 3 × 4 ⁰ = 323 _4.
Нарешті, якщо підстава коду m = 2, то
M = 59 = 1 × 2 ⁵ + 1 × 2 ⁴ + 1 × 2 ³ + 0 × 2 ² + 1 × 2 ¹ + 1 × 2 ⁰ = 111011 _2.
Таким чином, числа 73, 323 і 111011 можна вважати, відповідно, восьмеричним, четверичная й двійковим кодами числа M = 59.
У принципі підставу коду може бути будь-яким, проте найбільшого поширення набули двійкові коди, або коди з підставою 2, для яких розмір алфавіту кодових символів Â {x _j } Дорівнює двом, x _j Ì 0,1. Двійкові коди, тобто коди, що містять лише нулі і одиниці, дуже просто формуються і передаються по каналах зв'язку і, головне, є внутрішньою мовою цифрових ЕОМ, тобто без будь-яких перетворень можуть оброблятися цифровими засобами. Тому, коли мова йде про кодування і кодах, найчастіше мають на увазі саме двійкові коди. Надалі будемо розглядати в основному двійкове кодування.
Найпростішим способом представлення або завдання кодів є кодові таблиці, що ставлять у відповідність повідомленнями l _i відповідні їм коди (табл. 1).

Буква l i	Число l i	Код з основою 10	Код з основою 4	Код з основою 2
А	0	0	00	000
Б	1	1	01	001
У	2	2	02	010
Г	3	3	03	011
Д	4	4	10	100
Е	5	5	11	101
Ж	6	6	12	110
З	7	7	13	111

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

Рис. 1
Для того, щоб побудувати кодове дерево для даного коду, починаючи з деякої точки - кореня кодового дерева - проводяться гілки - 0 або 1. На вершинах кодового дерева знаходяться букви алфавіту джерела, причому кожній букві відповідають своя вершина і свій шлях від кореня до вершини. Приміром, букві А відповідає код 000, букві В - 010, букві Е - 101 і т.д.
Код, отриманий з використанням кодового дерева, зображеного на рис. 1, є рівномірним трехразрядного кодом.
Рівномірні коди дуже широко використовуються в силу своєї простоти і зручності процедур кодування-декодування: кожній букві - однакове число біт; прийняв задане число біт - шукай в кодової таблиці відповідну літеру.
Поряд з рівномірними кодами можуть застосовуватися і нерівномірні коди, коли кожна літера з алфавіту джерела кодується різною кількістю символів, наприклад, А - 10, Б - 110, У - 1110 і т.д.
Кодове дерево для нерівномірного кодування може виглядати, наприклад, так, як показано на рис. 2.

А

З

0

0

0

0

1

1

1

1

Б

У

Г

Д

Е

Ж

Рис. 2
При використанні цього коду буква А буде кодуватися, як 1, Б - як 0, В - як 11 і т.д. Однак можна помітити, що, закодувавши, наприклад, текст АББА = 1001, ми не зможемо його однозначно декодувати, оскільки такий самий код дають фрази: ЖА = 1001, АЄА = 1001 і ГД = 1001. Такі коди, що не забезпечують однозначного декодування, називаються приводяться, або непрефікснимі, кодами і не можуть на практиці застосовуватися без спеціальних поділяють символів. Прикладом застосування такого типу кодів може служити азбука Морзе, в якій окрім крапок і тире є спеціальні символи поділу букв і слів. Але це вже не двійковий код.
Проте можна побудувати нерівномірні Непріводімие коди, що допускають однозначне декодування. Для цього необхідно, щоб всім буквам алфавіту відповідали лише вершини кодового дерева, наприклад, такого, як показано на рис. 3. Тут жодна кодова комбінація не є початком іншої, більш довгою, тому неоднозначності декодування не буде. Такі нерівномірні коди називаються префіксним.

1

1

0

0

А

Б

У

1

0

Г

0

Д

1

Рис .. 3
Прийом і декодування нерівномірних кодів - процедура набагато складніша, ніж для рівномірних. При цьому ускладнюється апаратура декодування і синхронізації, оскільки надходження елементів повідомлення (букв) стає нерегулярним. Так, наприклад, прийнявши перший 0, декодер повинен подивитися в кодову таблицю і з'ясувати, який букві відповідає ухвалена послідовність. Оскільки такої літери немає, він повинен чекати приходу наступного символу. Якщо наступним символом буде 1, тоді декодування першої літери завершиться - це буде Б, якщо ж друга прийнятим символом знову буде 0, доведеться чекати третього символу і т.д.
Навіщо ж використовуються нерівномірні коди, якщо вони настільки незручні?
Розглянемо приклад кодування повідомлень l _i з алфавіту обсягом K = 8 за допомогою довільного n-розрядного двійкового коду.
Нехай джерело повідомлення видає деякий текст з алфавітом від А до З і однаковою ймовірністю літер Р (l _i) = 1 / 8.
Кодує пристрій кодує ці літери рівномірним трехразрядного кодом (див. табл. 1).
Визначимо основні інформаційні характеристики джерела з таким абеткою:
- Ентропія джерела , ;
- Надмірність джерела ;
- Середнє число символів в коді ;
- Надмірність коду .
Таким чином, при кодуванні повідомлень з рівноімовірними літерами надмірність обраного (рівномірного) коду виявилася рівною нулю.
Нехай тепер ймовірності появи в тексті різних букв будуть різними (табл. 2).
Таблиця 2

А	Б	У	Г	Д	Е	Ж	З
Ра = 0.6	Рб = 0.2	Рв = 0.1	Рг = 0.04	Рд = 0.025	Ре = 0.015	Рж = 0.01	Рз = 0.01

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

Надмірність коду в цьому випадку буде
,
або досить значною величиною (в середньому 4 символу з 10 не несуть ніякої інформації).
У зв'язку з тим, що при кодуванні неравновероятних повідомлень рівномірні коди мають великий надмірністю, було запропоновано використовувати нерівномірні коди, тривалість кодових комбінацій яких була б погоджена з імовірністю випадання різних букв.
Таке кодування називається статистичним.
Нерівномірний код при статистичному кодуванні вибирають так, щоб більш ймовірні букви передавалися за допомогою більш коротких комбінацій коду, менш імовірні - за допомогою більш довгих. У результаті зменшується середня довжина кодової групи в порівнянні з випадком рівномірного кодування.
Один із способів такого кодування запропонований Хаффмену. Побудова кодового дерева нерівномірного коду Хаффмена для передачі одного з восьми повідомлень l _i з різними імовірностями ілюструється табл. 3.
Таблиця 3

Буква	Імовірність Р i	Кодове дерево	Код	n i	n i × P i
А Б У Г Д Е Ж З	0.6 0.2 0.1 0.04 0.025 0.015 0.01 0.01		1 01 001 0001 00001 000001 0000001 00000001	1 2 3 4 5 6 7 8	0.6 0.4 0.3 0.16 0.125 0.08 0.07 0.08

Середнє число символів для такого коду складе

а надмірність коду

тобто на порядок менше, ніж при рівномірному кодуванні.
Іншим найпростішим способом статистичного кодування є кодування за методом Шеннона-Фано. Кодування у відповідності з цим алгоритмом проводиться так:
- Спочатку всі букви з абетки повідомлення записують в порядку убування їх вірогідності;
- Потім всю сукупність літер розбивають на дві приблизно рівні за сумою ймовірностей групи; однієї з них (у групі може бути будь-яке число символів, в тому числі - один) присвоюють символ " 1 " , Інший - " 0 " ;
- Кожну з цих груп знову розбивають (якщо це можливо) на дві частини і кожній із частин присвоюють " 1 " і " 0 " і т.д.
Процедура кодування за методом Шеннона-Фано ілюструється табл. 4.
Таблиця 4

Буква	Р (l i)	I	II	III	IV	V	Kод	n i × P i
А	0.6	1					1	0.6
Б	0.2	0	1	1			011	0.6
У	0.1			0			010	0.3
Г	0.04		0	1			001	0.12
Д	0.025			0	1		0001	0.1
Е	0.015				0		00001	0.075
Ж	0.01					1	000001	0.06
З	0.01					0	000000	0.06

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

тобто також істотно меншу величину, ніж для рівномірного коду.
Звернемо увагу на той факт, що як для коду Хаффмена, так і для коду Шеннона-Фано середня кількість двійкових символів, що припадає на символ джерела, наближається до ентропії джерела, але не дорівнює їй. Даний результат є наслідком теореми кодування без шуму для джерела (першої теореми Шеннона), яка стверджує:
Будь-яке джерело можна закодувати двійковій послідовністю при середній кількості двійкових символів на символ джерела l _i, як завгодно близькому до ентропії, і неможливо домогтися середньої довжини коду, меншою, ніж ентропія H (λ).
Значення цієї теореми для сучасної радіотехніки важко переоцінити - вона встановлює ті кордону в компактності представлення інформації, яких можна досягти при правильному її кодуванні.

ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для вузів. / В.І. Нефедов, В.І. Халкин, Є.В. Федоров та ін - М.: вища школа, 2001 р. - 383с.
3. Цапенко М.П. вимірювальні інформаційні системи .- М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г., Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.