;
3. КОДИРОВАНИЕ МЕТОДОМ Шеннон-Фано
Кодування Шеннона - Фано (англ. Shannon-Fano coding) - алгоритм префіксного неоднорідного кодування. Відноситься до імовірнісних методам стиснення (точніше, методам контекстного моделювання нульового порядку). Алгоритм Шеннона - Фано використовує надмірність повідомлення, укладену в неоднорідному розподілі частот символів його (первинного) алфавіту, тобто замінює коди більш частих символів короткими двійковими послідовностями, а коди більш рідкісних символів - більш довгими двійковими послідовностями. Алгоритм був незалежно один від одного розроблений Шенноном (публікація «Математична теорія зв'язку», 1948 рік) і, пізніше, Фано (опубліковано як технічний звіт).
Завдання: провести кодування за однією і блоками по дві букви, використовуючи метод Шеннона - Фано. Порівняти ефективності кодів (величина ентропії). Дані взяти із задачі 1.
Рішення. Проведемо кодування методом Шеннона - Фено і розрахуємо характеристики коду. Нехай вихідний алфавіт складається з трьох (по одній букві) і дев'яти (по дві букви) букв і задані їх ймовірності. Проведемо розбиття за алгоритмом Шеннона - Фено і складемо кодові комбінації.
xiP (xi) 1234P30.75001P20.130001P10.120000
Кодові комбінації по одній букві.
xiP(xi)12345p3p30.562511p3p20.097510p2p30.0975011p3p10.09010p1p30.090011p2p20.01690010p2p10.01560001p1p20.015600001p1p10.014400000
Кодові комбінації по дві букви.
Розрахуємо ентропію за формулою.
Розрахуємо середню довжину кодової комбінації за формулою.
Розрахуємо ефективність коду, згідно з формулою.
Ентропія джерела. По одній букві:
За дві букви:
Середня довжина кодової комбінації джерела. По одній букві:
За дві букви:
Ефективність коду. По одній букві:
За дві букви:
4. КОДИРОВАНИЕ алгоритму Гоффмана
Один з перших алгоритмів ефективного кодування інформації був запропонований Д.А. Хаффманом в 1952 році.
Ідея алгоритму полягає в наступному: знаючи ймовірності символів у повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів.
Символам з більшою ймовірністю ставляться у відповідність більш короткі коди.
Коди Хаффмана мають властивість Префіксний (тобто жодне кодове слово не є префіксом іншого), що дозволяє однозначно їх декодувати. Класичний алгоритм Хаффмана на вході отримує таблицю частот зустрічальності символів у повідомленні.
Далі на підставі цієї таблиці будується дерево кодування Хаффмана (Н-дерево).
Завдання: алфавіт переданих повідомлень складається з незалежних букв Si. Ймовірності появи кожної букви в повідомленні задані. Визначити і порівняти ефективність кодування повідомлень методом Хаффмена при побуквенном кодуванні і при кодуванні блоками по дві букви. Варіант №23: (0,8; 0,0; 0,08; 0,12).
Рішення. Проведемо кодування методом Шеннона-Фено.
xiP (xi) 123p10.81p40.1201p30.08001p20000
За однією букві.
xiP(xi)P1p10.64P4p10.096P1p40.096P3p10.064P1p30.064P4p40.0144P4p30.0096P3p40.0096P3p30.0064P4p20P2p40P3p20P2p30P2p10P1p20P2p20
За дві букви.
Проведемо кодування за методом Хаффмена. Вихідний алфавіт складається з кількох літер із заданими ймовірностями. Складемо таблицю.
xiP (xi) Допоміжний столбецp10.80.8p40.120.2p30.08p20
За однією букві
xiP (xi) Допоміжні столбцыP1p10.640.64P4p10.0960.0960.1920.36P1p40.0960.0960.168P3p10.0640.0640.128P1p30.0640.0640.040P4p40.01440.0144P4p30.00960.00960.0256P3p40.00960.0160P3p30.0064P4p20P2p40P3p20P2p30P2p10P1p20P2p20
За дві букви.
Характеристики коду розраховуються за тими ж формулами, що і для коду Шеннона-Фано.
Розрахуємо ентропію за формулою.
Розрахуємо мінімальну середню довжину кодової комбінації за формулою.
Розрахуємо ефективність коду, згідно з формулою.
Ентропія джерела. По одній букві:
За дві букви:
Середня довжина кодової комбінації джерела. По одній букві:
За дві букви:
Ефективність ко...
