6.20: Ентропія

Цілі навчання

• Шеннон показав силу ймовірнісних моделей для символічних сигналів. Суха величина, що характеризує такий сигнал, - це ентропія його алфавіту.

Теорія зв'язку була сформульована найкраще для символічних сигналів. Клод Шеннон опублікував у 1948 році «Математичну теорію спілкування», яка стала наріжним каменем цифрової комунікації. Він показав силу ймовірнісних моделей для символічно-значущих сигналів, що дозволило йому кількісно оцінити інформацію, присутню в сигналі. У найпростішій моделі сигналу кожен символ може зустрічатися за індексом n з ймовірністю Pr [a _k], k= {1,... , К}. Ця модель говорить про те, що для кожного значення сигналу K -sided монета перевертається (зверніть увагу, що монета не повинна бути справедливою). Щоб ця модель мала сенс, ймовірності повинні бути числами від нуля до одиниці і повинні сумувати одиницю.

$$0\leq Pr[a_{k}]\leq 1 \nonumber$$

$$\sum_{k=1}^{K}Pr[a_{k}]=1 \nonumber$$

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

$$H(A)=-\sum_{kK}Pr[a_{k}]\log_{2}Pr[a_{k}] \nonumber$$

Оскільки ми використовуємо логарифм base-2, ентропія має одиниці бітів. Щоб це визначення мало сенс, ми повинні взяти до уваги символи, що мають нульову ймовірність виникнення. Символ нульової ймовірності ніколи не виникає; таким чином, ми визначаємо

$$0\log_{2}0=0 \nonumber$$

щоб такі символи не впливали на ентропію. Максимальне значення, яке досягається ентропією алфавіту, виникає, коли символи однаково вірогідні.

$$Pr[a_{k}]=Pr[a_{l}] \nonumber$$

При цьому ентропія дорівнює log ₂ K. Мінімальне значення виникає, коли виникає лише один символ; він має ймовірність одного, а решта мають нуль ймовірності.

Вправа$\PageIndex{1}$

Вивести результати максимальної ентропії, як числовий аспект (ентропія дорівнює журналу ₂ K), так і теоретичний (однаково ймовірні символи максимізують ентропію). Вивести значення мінімальної ентропії алфавіту.

Рішення

Однаково ймовірні символи мають ймовірність 1/K. Таким чином,

$$H(A)=-\sum_{kK}\frac{1}{K}\log_{2}\frac{1}{K}=\log_{2}K \nonumber$$

Щоб довести, що це привласнення ймовірності максимальної ентропії, треба явно враховувати, що ймовірності сумуються одиниці. Орієнтуйтеся на конкретний символ, скажімо перший. Pr [a ₀] з'являється двічі у формулі ентропії: терміни

$$Pr[a_{0}]\log_{2}Pr[a_{0}]\; and\; (1-Pr[a_{0}]+...+Pr[a_{K-2}])\log_{2}(1-Pr[a_{0}]+...+Pr[a_{K-2}]) \nonumber$$

Похідна щодо цієї ймовірності (і всіх інших) повинна дорівнювати нулю. Похідна дорівнює

$$\log_{2}Pr[a_{0}]- \log_{2}(1-Pr[a_{0}]+...+Pr[a_{K-2}]) \nonumber$$

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

$$1\log_{2}1=0 \nonumber$$

а інші

$$0\log_{2}0 \nonumber$$

який ми визначаємо як нуль також. Мінімальне значення ентропії дорівнює нулю.

Приклад$\PageIndex{1}$:

Чотирисимвольний алфавіт має такі ймовірності.

$$Pr[a_{0}]=\frac{1}{2} \nonumber$$

$$Pr[a_{1}]=\frac{1}{4} \nonumber$$

$$Pr[a_{2}]=\frac{1}{8} \nonumber$$

$$Pr[a_{3}]=\frac{1}{8} \nonumber$$

Зауважте, що ці ймовірності складають одну, як слід. Як

$$\frac{1}{2}=2^{-1},\log_{2}\frac{1}{2}=-1 \nonumber$$

Ентропія цього алфавіту дорівнює

$$H(A)=-\left ( \frac{1}{2} \log_{2}\frac{1}{2}+\frac{1}{4} \log_{2}\frac{1}{4}+\frac{1}{8} \log_{2}\frac{1}{8}+\frac{1}{8} \log_{2}\frac{1}{8}\right ) \nonumber$$

$$H(A)=-\left ( \frac{1}{2} -1+\frac{1}{4} -2+\frac{1}{8} -3+\frac{1}{8} -3\right ) \nonumber$$

$$H(A)=1.75\; bits \nonumber$$