y">/b j ) = p (a i , b j )/p (b j ) В
Частина 2. Теорія кодування
6. Оптимальне кодування. Ідея стиснення
Основною характеристикою дискретного каналу зв'язку є швидкість передачі даних. При надмірності надісланого повідомлення швидкість передачі зменшується. Для виключення надмірності повідомлення використовують математичні та програмні засоби компресії даних без втрати змісту інформації, в тому числі оптимальне кодування. p align="justify"> Оптимальне кодування застосовують для того, щоб:
В· стискати дані (компресія);
В· знижувати час передачі даних при тій же швидкості передачі;
В· зменшити можливі втрати і спотворення даних;
В· архівувати дані, ефективно використовувати пам'ять.
Основна ідея оптимального кодування лежить в тому, що символам повідомлення, які мають велику ймовірність, привласнюють короткі бінарні коди, тобто утворюються бінарні кодові слова різної довжини - нерівномірні коди. Оптимальним нерівномірним кодом (ОНК) називається такий код, для якого середня довжина коду є мінімальною. p align="justify"> Така ідея стиснення була застосована в абетці Морзе, де найбільш зустрічається символам відповідали найбільш короткі коди. Сам алфавіт складався з крапок і тире. br/>
6.1 Рівномірний двійковий код (РДК), кореневе бінарне дерево РДК, довжина коду РДК, повідомлення в РДК
Складання повідомлення
Нам дано повідомлення:
Х = "Зупиніть землю, я зійду"
Довжина повідомлення L x = 24 [символу]
Алфавіт повідомлення
Знайдемо алфавіт нашого повідомлення:
= {о, з, т, а, н, в, і, е, з, м, л, ю, я, с, ї, д, у, _. } br/>
Довжина алфавіту L a = 21 [символ]
Ймовірності
На даному етапі обчислення РДК нам потрібно обчислити Веро-ності появи кожного символу в алфавіті повідомлення. Для цього ми скористаємося формулою:
p i = v i < span align = "justify">/l s
де v i - кількість разів, яке символ зустрічається в повідомленні.
Сума v i повинна відповідати довжині вихідного повідомлення.
Таблиця даних, РДК
В
Таким чином, наше повідомлення буде виглядати:
S РДК В
6.1.6 Довжина повідомлення
Довжина повідомлення, записаного в РДК дорівнює:
l sрдк = l s В· l РДК
де l РДК = 5 біт.
Таким чином, довжина повідомлення:
l sрдк = 24.5 = 120 біт
6.2 Оптимальний нерівномірний код ОНК Шеннона-Фано, алгоритм розрахунку ОНК, середня довжина, ентропія, коефіцієнт стиснення, коефіцієнт ефективності, повідомлення в ОНК, критерій Фано, кореневе бінарне дерево ОНК Шеннона-Фано
Розрахунок ОНК
Оптимальний нерівномірний код (ОНК) ми будемо розраховувати за методом Шеннона-Фано, який ще називають методом бисекции.
Для обчислення ОНК вся робота розбивається на кілька етапів.
Попередній крок: ймовірності появи символу в повідомленні ранжуються за спаданням.
Крок перший: всі ймовірності розбиваються на дві рівноімовірні групи. Символам верхньої секції призначимо 0, символам нижньої секції - 1. Перший біт ОНК обчислений. p align="justify"> Крок другий: кожну групу ділимо на дві рівноімо...
