Знайти надмірність коду
Ентропія коду ближче до максимуму ніж незакодованої послідовності і дуже близька до максимального значення, отже, кодування є оптимальним. Символи отриманого алфавіту m2 ділять на дві частини, сумарні ймовірності символів яких максимально близькі один одному. Отримані частини рекурсивно діляться і їх частинам призначаються відповідні виконавчі цифри в префіксной коді. Де — кількість символів коду… Читати ще >
Знайти надмірність коду (реферат, курсова, диплом, контрольна)
Для джерела повідомлень (задача 1) побудувати код Шенона-Фано, знайти надмірність коду.
Кодування Шеннона — Фано — алгоритм префіксного неоднорідного кодування. Відноситься до імовірнісних методів стиснення. Використовує надмірність повідомлення, тобто замінює коди частіших символів короткими двійковими послідовностями, а коди більш рідких символів — довшими послідовностями.
Основні етапи[3]:
- — Символи первинного алфавіту m1 виписують в порядку збування ймовірностей.
- — Символи отриманого алфавіту m2 ділять на дві частини, сумарні ймовірності символів яких максимально близькі один одному.
- — В префіксному коді для першої частини алфавіту присвоюється двійкова цифра «0», другої частини — «1».
- — Отримані частини рекурсивно діляться і їх частинам призначаються відповідні виконавчі цифри в префіксной коді.
Коли розмір підалфавіта стає рівним нулю або одиниці, то подальшого подовження префікснго коду не відбувається. На кроці поділу алфавіту існує неоднозначність, так як різниця сумарних ймовірностей може бути однакова для двох варіантів поділу (враховуючи, що всі символи первинного алфавіту мають ймовірність більше нуля).
На таблиці 2.1 представлено код для данного по задачі джерела.
Таблиця 2.1 — Код Шеннона фано для данного джерела
Індекс символу аі | Імовірність. | Код. | |||
0.35. | |||||
0.3. | |||||
0.2. | |||||
0.1. | |||||
0.05. |
Вираховуємо максимальну ентропію коду:
Hmax= log 2=1.
Для обрахування ентропії H треба знайти ймовірності появи символів 1 та 0 в коді для елементів, скориставшись формулами частоти появи символу[1]:
P (xk)=,.
де — кількість символів коду що відповідають символу , — повна кількість символів кодової комбінації.
p (1)= =.
p (0)= 1-p (1)=1- =.
H.
Знаходимо абсолютну та відносну надмірність:
Висновок.
Задане джерело повідомлення було закодовано кодом за методом Шенона-Фано. Символи джерела можуть приймати значення 1 та 0, утворюючи дві групи коду відповідно.
Ентропія коду ближче до максимуму ніж незакодованої послідовності і дуже близька до максимального значення, отже, кодування є оптимальним.
Для отримання ймовірностей появи 1 та 0 тип повідомлення прийнято за типовий, в якому ймовірність появи елемента рівна частоті появи елемента.