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

Кодування та стиснення інформації методом хаффмена та Шенона-Фано

Мета роботи: Вивчення принципів кодуванняпотоків символів з різною частотою появи символів у потоці, використовуючи метод кодування Хаффмена та Шенона-Фано.

Теоретичні відомості

Оптимальним кодуванням називається процедура перетворення символів первинного алфавіту А в кодові слова у вторинному алфавіті В, при якій середня довжина повідомлень у вторинному алфавіті має мінімально можливу для даного алфавіту В довжину.

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

У повідомленнях, складених з кодових слів оптимального коду, статистична надмірність зведена до мінімуму, в ідеальному випадку - до нуля.

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

З властивостей оптимальних кодів випливають принципи їх побудови.

1 - вибір кожного кодового слова необхідно проводити так, щоб кількість інформації, яка міститься в ньому, була максимальною;

2 - літерам первинного алфавіту, які мають велику ймовірність, присвоюються коротші кодові слова у вторинному алфавіті.

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

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

1. VII. Нахождение общего решения методом характеристик
2. Або зі зберігання інформації та забезпечення доступу до неї, за умови, що ця особа не могла знати про незаконність розповсюдження інформації.
3. Автоматичне кодування.
4. Алгоритм надання провізором належної інформації про безрецептурний ЛП під час здійснення фармацевтичної опіки при симптоматичному лікуванні уражень шкіри
5. Алгоритми захисту цифрової просторової інформації
6. Алфавітне кодування
7. Алфавітний підхід до вимірювання кількості інформації.
8. Аналіз зовнішньої інформації
9. Аналіз інформації та постановка задачі дослідження
10. Аналіз причин виникнення проблеми та обґрунтування її розв’язання програмним методом
11. Аналіз та інтерпретація інформації
12. Аналіз та компонування інформації для проекту

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