6.21: Теорема кодування джерела

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

• Теорема про кодування джерела стверджує, що ентропія алфавіту символів вказує в межах одного біта, скільки бітів в середньому потрібно використовувати для надсилання алфавіту.

Значення ентропії алфавіту полягає в тому, як ми можемо представляти його з послідовністю бітів. Бітові послідовності утворюють «монету царства» в цифрових комунікаціях: вони є універсальним способом подання символічних сигналів. Ми перетворюємо між символами в бітові послідовності з тим, що відомо як кодова книга: таблиця, яка асоціює символи з бітовими послідовностями. Створюючи цю таблицю, ми повинні мати можливість призначити унікальну бітову послідовність кожному символу, щоб ми могли без помилок переходити між послідовностями символів та бітів.

Примітка

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

Як ми детально вивчимо в іншому місці, цифровий зв'язок - це передача символічних сигналів з одного місця в інше. Зіткнувшись з проблемою, наприклад, відправки файлу через Інтернет, ми повинні спочатку представляти кожен символ бітовою послідовністю. Оскільки ми хочемо, щоб відправити файл швидко, ми хочемо використовувати якомога менше бітів. Однак ми не хочемо використовувати так мало бітів, що приймач не може визначити, що кожен символ був з бітової послідовності. Наприклад, ми могли б використовувати один біт для кожного символу: передача файлів була б швидкою, але марною, оскільки кодова книга створює помилки. Шеннон довів у своїй монументальній роботі те, що ми сьогодні називаємо теоремою кодування джерела. Нехай B (a _k) позначають кількість бітів, які використовуються для представлення символу a _k. Середня кількість бітів, $$\overline{B(A)} \nonumber$$ необхідних для представлення всього алфавіту, дорівнює

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

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

$$H(A)\leq \overline{B(A)}\leq H(A)+1 \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$$

і ентропія 1,75 біт. Давайте подивимося, чи зможемо ми знайти кодову книгу для цього чотирилітерного алфавіту, який задовольняє теоремі кодування джерела. Найпростіший код для спроби відомий як простий двійковий код: перетворіть індекс символу в двійкове число і використовуйте однакову кількість бітів для кожного символу, включивши провідні нулі, де це необхідно.

$$a_{0}\leftrightarrow 00a_{1}\leftrightarrow 01a_{2}\leftrightarrow 10a_{3}\leftrightarrow 11 \nonumber$$

Всякий раз, коли кількість символів в алфавіті дорівнює двом (як у цьому випадку), середня кількість бітів

$$\overline{B(A)}=\log_{2}K \nonumber$$

що дорівнює 2 в даному випадку. Оскільки ентропія дорівнює 1.75 біт, простий двійковий код дійсно задовольняє теорему про кодування джерела - ми знаходимося в межах одного біта межі ентропії - але ви можете задатися питанням, чи можете ви зробити краще. Якщо ми виберемо кодову книгу з різною кількістю бітів для символів, то дійсно можна отримати меншу середню кількість бітів. Ідея полягає у використанні коротших бітових послідовностей для символів, які зустрічаються частіше. Одна кодова книга, як це

$$a_{0}\leftrightarrow 0a_{1}\leftrightarrow 01a_{2}\leftrightarrow 110a_{3}\leftrightarrow 111 \nonumber$$

$$\overline{B(A)}=1\cdot \times \frac{1}{2}+2\cdot \times \frac{1}{4}+3\cdot \times \frac{1}{8}+3\cdot \times \frac{1}{8}=1.75 \nonumber$$

Ми можемо досягти межі ентропії! Простий двійковий код в даному випадку менш ефективний, ніж код нерівної довжини. Використовуючи ефективний код, ми можемо передати символічно-значний сигнал, який має цей алфавіт на 12,5% швидше. Крім того, ми знаємо, що не можна знайти більш ефективну кодову книгу через теорему Шеннона.