Метод Шеннона–Фано

При рівномірному коді всі повідомлення незалежно від імовірності їх появи являють собою кодові комбінації однакової довжини, тобто кількість двійкових символів, що припадає на одне повідомлення, суворо постійна.

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

Таким чином, облік статистичних закономірностей повідомлення дозволяє побудувати більш економічний код. Метод побудови таких кодів уперше запропонували К.Шеннон і Р.Фано.

Код Шеннона–Фано будується наступним чином:

1. Всі повідомлення (літери) записуються в таблицю в порядку зменшення ймовірності їх появи.

2. Всю послідовність повідомлень (букв) ділять на 2 групи так, щоб суми ймовірностей в кожній групі були б приблизно однаковими. Верхній групі повідомлень (букв) присвоюється цифра «0» (як перший символ коду), а нижній цифра «1».

3. Кожна група повідомлень (букв) ділиться на дві підгрупи із збереженням тоєї ж умови однакової суми ймовірностей. Верхнім підгрупами в обох групах знову присвоюється цифра «0» (як другий символ коду), а нижнім – цифра «1».

4. Такий розподіл продовжується до тих пір, поки в підгрупах не залишиться тільки по одному повідомленню (букві).

Приклад. Є 8 повідомлень (букв) з ймовірностями 0,3; 0,2; 0,1; 0,1; 0,1; 0,08; 0,07; 0,05. Побудувати код для даних повідомлень.

Рішення. Складаємо таблицю з 4–х стовпців. У першому стовпці вказуємо номер повідомлення, а в другому – ймовірності повідомлень у порядку їх зменшення:

№ сообщ., букв	Р сообщений		Кодовые комбинации
	0,3
	0,2
	0,1
	0,1
	0,1
	0,08
	0,07
	0,05

Об'єднаємо в першу групу дві перші літери, а в другу – всі інші. Буквам першої групи присвоюємо цифру «0», а другої групи – цифру «1». Далі першу групу і другу групу ділимо на дві підгрупи. Верхнім підгрупах присвоюємо цифру «0», а нижнім – цифру «1» і заносимо їх в стовпець «кодові комбінації». У першій і другій підгрупах першої групи поділ вже неможливо, тому в них залишилося по одній букві. Підгрупи другої групи знову ділимо на дві частини і присвоюємо їм відповідні цифри. У підсумку в четвертому стовпці отримуємо кодові комбінації, які відповідають кожній букві. З таблиці видно, що буквам з більшою ймовірністю відповідають короткі кодові комбінації, а з меншою ймовірністю– більш довгі кодові комбінації.

Середнє число символів на одну букву для розглянутого прикладу становитиме 2·0,3 + 2·0,2 + 3·0,1 + 4·0,1 + 4·0,1 + 3·0,08 + 4·0,07 + 4·0,05 =2,62.

У разі використання простого двійкового коду необхідне число символів склало б 3. З даних величин можна зробити висновок про те, що використання коду Шеннона–Фано ефективніше використання простого двійкового коду приблизно на 12,6%.

Дата добавления: 2014-01-04