Дек
2

Код Шеннона-Фано, вирішення задачі

Задача

Побудувати код Шеннона-Фано для системи з семи літер: A, B, C, D, E, F, G, імовірність появи яких відповідно 0,10; 0,20; 0,05; 0,30; 0,05; 0,15; 0,15. Визначити середню кількість розрядів на одну літеру. Декодувати цим кодом послідовність: 10011101001000111101110101111000.

Розв’язання

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

Для кодування кодом Шеннона-Фано потрібно:

1) прості повідомлення від джерела записати у таблицю в порядку спадання ймовірностей їх появи;

2) загальний об’єм повідомлень поділити так, щоб сумарна ймовірність всіх повідомлень групи І дорівнювала сумі ймовірностей появи групи ІІ (в нашому випадку ймовірність появи літер D і В = 0,30 + 0,20 = 0,50 – якраз дорівнює половині). Якщо ймовірності груп І і ІІ не співпадають, то це не страшно;

3) першій підгрупі присвоюється значення «0», а другій підгрупі – «1»;

4) поділ треба вести до тих пір, поки в кожній підгрупі не буде по одному повідомленню.

код Шеннона-Фано

З таблиці видно, що наприклад, літері В відповідає код 01, а літері С – 1110.

Визначимо середню кількість розрядів на одну літеру:

Середня кількість розрядів на одну літеру

де N – кількість літер в алфавіті (1, 2, … і, …, N), Кі – кількість біт, які припадають на літеру і; р(хі)- ймовірність появи і-тої літери.

Якби ми кодували повідомлення простим кодом, то середня кількість розрядів на одну літеру була б Ксер = 3.
Тепер, згідно наведеної вище таблиці, декодуємо код Шеннона-Фано:

декодування коду Шеннона-фано

Думаю, особливих пояснень не потрібно – і так все видно. Шукаємо в таблиці потрібну комбінацію бітів, яким буде відповідати певна літера і послідовно записуємо результат.

Дуже поганоПоганоМоже бутиНормальноСупер Оцініть статтю, будь-ласка
Загрузка...
Сподобалася стаття, натисни кнопку!

Прокомментировать

Останні коментарі

Правила безпечної експлуатації електроустановок

Знайти публікацію по даті

Друзі сайту:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~