LabRab_po_TI
Лабораторна робота №2
Оптимальне кодування
1. Основні відомості про оптимальне кодування
Кодуванням інформації називається операція перетворення повідомлень, що складаються із символів первинного алфавіту, певну послідовність символів вторинного алфавіту (елементарних символів). Зворотна операція, що відновлює вихідне повідомлення за елементарними символами, називається декодуванням. Будь-якому дискретному повідомленню можна приписати деяке число – його код. Тоді передача повідомлень зводиться до передачі кодів. Вочевидь, що з відновлення за кодами повідомлень вони мають бути однозначно декодируемыми (разделимыми). Таку властивість мають префіксні коди.
Префіксні коди – це такі коди, в яких жодна більш коротка комбінація не є початком довшої комбінації, що дозволяє проводити однозначне декодування, навіть якщо послідовність кодів не містить роздільників між кодами.
Для існування двійкового коду, що міститьNкодових слів, що складаються із символів 0 і 1, з довжинамиn1,n2, …,nN, необхідно і достатньо, щоб виконувалася нерівність Крафта:
Дискретне джерело повідомлень, яке описується моделлю із незалежними символами повідомлень, називається дискретним джерелом без пам'яті. Для будь-якого дискретного джерела без пам'ятіXз кінцевим алфавітом та ентропієюH(X) існує двійковий код, у якому середня довжина кодового слова
,
тобто. середня довжина кодового слова не може бути меншою за ентропію джерела повідомлень. Крім того, доведено, що для блоку довжиниLіснує двійковий префіксний код, в якому середня кодова довжинаслова на один символ
,
де. Остання нерівність дозволяє стверджувати, що існують такі способи кодування для досить довгого повідомлення, що середня довжина кодового слова може бути зроблена скільки завгодно близькою до величиниH(X).
Оскільки мінімально досяжною довжиною кодового слова на символ є величина, що дорівнює значенню ентропіїH, надмірність коду можна визначити за формулою
Те саме повідомлення можна закодувати різними способами. Оптимальним вважається такий код, коли на передачу повідомлень витрачається мінімальний час. Якщо при цьому на передачу кожного елементарного символу коду витрачається той самий час, то оптимальним буде код, що має мінімально можливу довжину.
Принципи побудови оптимальних кодів:
кожен елементарний символ повинен переносити максимальну кількість інформації, цього необхідно, щоб елементарні символи в закодованому тексті зустрічалися у середньому однаково часто, т.к. ентропія у разі буде максимальної;
необхідно кодованим символам, що мають більшу ймовірність, присвоювати коротші кодові слова.
При рівномірному розподілі ймовірностей символів у повідомленні оптимальним буде рівномірний код. При рівномірному кодуванні кожному символу алфавіту повідомлень надається код, що складається з ]log2n[ двійкових значень, деn– число різних символів, що кодуються, а ]log2n[ - Найближче ціле, не меншеn. Це можна зробити, наприклад, зіставивши кожному символу число від 0 доn– 1 у двійковій системі числення.
Одним із способів оптимального кодування є метод Шеннона-Фано. Для створення коду Шеннона-Фано всі символи алфавіту повідомленьзаписують у порядку зменшення ймовірностей їх появи. Отриману ранжовану (упорядковану) послідовність символів розбивають на дві групи так, щоб суми ймовірностей були приблизно однаковими. Для символів першої групи як перший кодовий символ надають 0, а для символів другої групи – 1. Отримані групи символів повідомлень знову розбивають так само на дві підгрупи і знову кодують. Це продовжується доти, доки в останніх підгрупах не залишиться по одному символу повідомлень. Нехай, наприклад, є алфавіт повідомлень
із розподілом ймовірностей появи символів
.
В результаті кодування за методом Шеннона-Фано символів алфавітуXбудуть отримані коди таблиці 1.