алфавіту;
букв верхньої групи привласнюють значення 1, а нижній - 0;
Процес продовжують до тих пір, поки не залишиться єдина допоміжна буква з вірогідністю, рівній одиниці.
Процес кодування зручно графічно ілюструвати за допомогою горизонтально розташованого дерева (ліворуч - гілки, праворуч - корінь, рисунок 2.4), у якого завжди дві гілки об'єднуються в одну, більш велику. Об'єднувані гілки позначаються двійковими цифрами: верхня - 1, нижня - 0. Щоб записати кодове слово, відповідне даній букві, потрібно рухатися до неї від кореня дерева і зчитувати ці двійкові цифри.
Малюнок 2.4 - Кодова дерево методу Хаффмана
. 2.2.3 Рівномірний код
Середня довжина кодового слова:
тобто
Таблиця 2.6 - Рівномірний кодування
КомбінаціяВероятностьКод
. 2.3 Порівняння кодів по ефективності
. 2.3.1 Аналіз коду Шеннона-Фано
Середня довжина коду:
Ефективність:
Отримані дані занесені в таблицю 2.7.
. 2.3.2 Аналіз коду Хаффмана
Середня довжина коду:
Ефективність:
Отримані дані занесені в таблицю 2.7.
. 2.3.3 Аналіз рівномірного коду
Середня довжина коду:
Ефективність:
Отримані дані занесені в таблицю 2.7.
. 2.4 Ймовірності появи «0» і «1»
. 2.4.1 Ймовірності появи на виході «0» і «1» у коду Шеннона-Фано
Середня довжина одиниць:
Імовірність появи «1»:
Імовірність появи «0»:
Отримані дані занесені в таблицю 2.7.
. 2.4.2 Ймовірності появи на виході «0» і «1» у коду Хаффмана
Середня довжина одиниць:
Імовірність появи «1»:
Імовірність появи «0»:
Отримані дані занесені в таблицю 2.7.
Шукати ймовірності появі нуля або одиниці у рівномірного кодування немає сенсу, так як здійснюється довільний вибір коду.
Таблиця 2.7 - Порівняння кодів
Код Шеннона-ФаноКод ХаффманаРавномерний код
Ефективність джерела:
Висновки:
Рівномірний кодування джерела знизило його ефективність. Коли в свою чергу у кодів Шеннона-Фано і Хаффмана спостерігається істотне збільшення.
Коди Шеннона-Фано і Хаффмана мають явні переваги перед рівномірним кодом по середній довжині коду (доходять майже до мінімальної довжини).
Середня довжина кодового слова у Шеннона-Фано і Хаффмана однакова, але враховуючи ймовірності появи «0» і «1», то останній є кращим. Тобто у коду Хаффмана ймовірності появи нуля і одиниці (приблизно) рівноімовірною, а це означає, що він носить більше інформації.
Алгоритми Хаффмана і Шеннона-Фано використовують надмірність повідомлення, укладену в неоднорідному розподілі частот символів його (первинного) алфавіту, тобто, замінюють коди більш частих символів короткими двійковими послідовностями, а коди більш рідкісних символів - більш довгими двійковими послідовностями.
Головний недолік кодів Шеннона-Фано і Хаффмана полягають в тому, що для їх застосування потрібно знати ймовірності появи букв (або їх комбінації при кодуванні блоками), а на практиці така сприятлива ситуація виникає надзвичайно рідко.
При використанні обох кодів будь-яка, навіть одиночна помилка в прийнятій послідовності позбавляє приймач можливості правильно декодувати її частину, що залишилася.
. 3 Завдання 3. Кодування і декодування кодом Лемпела-Зива
Задано ряд з 4-х десяткових чисел.
Уявити кожне число за допомогою 6 символів рівномірного двійкового коду
Закодувати отриману послідовність двійкових символів кодом Лемпела - Зива.
Провести декодування.
Теоретичні відомості:
На відміну від попередніх кодів (Шеннона-Фано і Хаффмана) в даному кодуванні не потрібно знати ймовірність появи букв. Тут кодова таблиця, спочатку майже порожня, заповнюється одночасно в пунктах передачі і пр...
