• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Задача 7.2.3

Побудувати ефективні нерівномірні коди Хаффмена та Шеннона-Фано для кодування символів немарковського джерела з алфавітом ; ймовірності виникнення символів мають такі значення:

Розв’язання.Спочатку побудуємо нерівномірний код за методикою Шеннона-Фано. Згідно з алгоритмом упорядковуємо символи по незростанню ймовірностей та виконуємо перший поділ множини символів на дві підмножини. Однак цей поділ не є однозначним: перший варіант поділу – на та , другий варіант – на та . Обидва варіанти дають однакові суми ймовірностей появи символів підмножин: 0,4 та 0,6. Таблиці 7.3 та 7.4 відображають побудову кодів Шеннона-Фано для двох варіантів.

Таблиця 7.3

		Кодова комбінація		Номер поділу
0,4
0,2
0,15
0,15
0,1

Таблиця 7.4

		Кодова комбінація		Номер поділу
0,4
0,2
0,15
0,15
0,1

Середня довжина кодової комбінації для першого варіанта

;

для другого

.

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

Для отримання коду Хаффмена будуємо кодове дерево (рис.7.4), приписуємо гілкам символи алфавіту двійкового коду та записуємо кодові комбінації: ; ; ; ; . Символи двійкового алфавіту приписувались гілкам дерева цілеспрямовано таким чином, щоб код цілком збігався з першим варіантом коду, побудованим за методикою Шеннона-Фано. Цей код є оптимальним з середньою довжиною кодової комбінації . Ентропія джерела H(X) = 2,146 біт. Відносна різниця середньої довжини оптимального ефективного коду та ентропії джерела дорівнює

[ ( 2,2 – 2,146 ) / 2,146 ] ´ 100% = 2,52%.

Рис. 2.4. Кодове дерево до задачі 2.2.3

Читайте також:

1. Б. Задача
2. Взаємне положення площин. Перша позиційна задача
3. Взаємне положення прямої і площини. Друга позиційна задача.
4. Вторая задача анализа на чувствительность
5. Головна задача м/н фінансового менеджменту полягає у оцінці короткострокових і довгострокових активів і зобов’язань фірми у часовому і просторовому використанні м/н ринків.
6. Двоїста задача
7. Двухмерная задача Коши
8. З праці В. Леніна «О задачах пролетариата в данной революции»
9. Загальна задача лінійного програмування (ЗЛТ)
10. Задача # 12 (з тих, що вона скидувала)
11. Задача 1
12. Задача 1

Переглядів: 328