5.7: Детально - Ефективний вихідний код

Last updated
Save as PDF

Page ID: 29799

Paul Penfield, Jr.
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Іноді кодування джерела та стиснення для систем зв'язку такого роду, як показано на малюнку 5.1, виконуються разом (це відкрите питання, чи є практичні переваги поєднання кодування джерела та каналу). Для джерел з кінцевим числом символів, але з неоднаковими ймовірностями появи у вхідному потоці існує елегантна, проста методика кодування джерела з мінімальною надмірністю.

Приклад скінченного джерела

Розглянемо джерело, який генерує символи, які є класами літер MIT, з можливими значеннями A, B, C, D і F. Вам пропонується розробити систему, яка може передавати потік таких класів, вироблений зі швидкістю одного символу в секунду, по каналу зв'язку, який може нести лише дві булеві цифри, кожен 0 або 1, в секунду. \(^3\)

По-перше, нічого не припускайте про розподіл сортів. Для передачі кожного символу окремо необхідно кодувати кожен у вигляді послідовності бітів (булевих цифр). Використання 7-бітного коду ASCII марнотратно; у нас є лише п'ять символів, а ASCII може обробляти 128. Оскільки існує лише п'ять можливих значень, оцінки можуть бути закодовані трьома бітами на символ. Але канал може обробляти тільки два біта в секунду.

Однак три біти - це більше, ніж потрібно. Ентропія, припускаючи, що немає інформації про ймовірності, становить максимум\(\log_2(5)\) = 2,32 біта. Це також там,\(\sum_{i} p(A_i) \log_2(1/p(A_i))\) де таких п'ять\(p_i\), кожен дорівнює 1/5. Навіщо нам знадобилося три біта в першому випадку? Тому що у нас не було можливості передати частковий біт. Щоб зробити краще, ми можемо використовувати «блокове кодування». Ми групуємо символи в блоки, скажімо, три. Інформація в кожному блоці втричі перевищує інформацію на символ, або 6,97 біт. Таким чином, блок може бути переданий за допомогою 7 булевих бітів (є 125 різних послідовностей трьох класів і 128 можливих шаблонів, доступних в 7 бітах). Звичайно, нам також потрібен спосіб позначення кінця та спосіб сказати, що останнє передане слово має лише один дійсний клас (або два), а не три.

Але це все ще занадто багато бітів в секунду для каналу, щоб обробляти. Отже, давайте розглянемо розподіл ймовірностей символів. У типовому курсі MIT з «B-центром» з хорошими учнями розподіл оцінок може бути таким, як показано в таблиці 5.3. Припускаючи це як розподіл ймовірностей, яка інформація на символ і яка середня інформація на символ? Цей розрахунок наведено в таблиці 5.4. Інформація на один символ становить 1.840 біт. Оскільки це менше двох бітів, можливо, символи можуть бути закодовані для використання цього каналу.

Таблиця 5.3: Розподіл оцінок для типового курсу MIT
A	Б	C	D	F
25%	50%	12,5%	10%	2,5%

\ [\ nonumber\ begin {масив} {cccc}
\ текст {Символ} &\ text {Ймовірність} &\ text {Інформація} &
\ begin {масив} {c}
\ text {до середнього}
\ end {масив}\\
& p &\ log\ left (\ frac {1} {p}\ праворуч) & p\ log\ left (\ frac {1} {p}\ праворуч)
\\ mathrm {A} & 0.25 & 2\ mathrm {\, біти} & 0.5\ mathrm {\, біти}
\\ mathrm {B} & 0.50 & 1\, біт} & 0.5\ mathrm {\, біти}\
\ mathrm {C} & 0,125 & 3\ mathrm {\, біти} & 0.375\ mathrm {\, біти}\\
\ математична {D} & 0.10 & 3.32\ математична {\, біти} & 0.332\ матрм {\, біти}\
\ матхм {F} & 0,025 & 5.32\ mathrm {\, біти} & 0.133\ mathrm {\, біти}\ [-20pt]
&\ overline {\ quad\ quad} &\ overline лінія {\ quad\ qquad}\\ [-10pt]
\ текст {Всього} & 1.00 & 1.840\ mathrm {\, біти}
\ кінець {масив}\ nonumber\]

Таблиця 5.4: Розподіл інформації для класів у середньому розподілі MIT

Кодекс Хаффмана

Девід Хаффман (9 серпня 1925 - 6 жовтня 1999) був аспірантом Массачусетського технологічного інституту. Щоб вирішити домашнє завдання для курсу, який він брав у професора Роберта М. Фано, він розробив спосіб кодування символів з різними ймовірностями, з мінімальною надмірністю і без спеціальних кадрів символів, а отже, найбільш компактно. Він описав його в Праці IRE, вересень 1962. Алгоритм його дуже простий. Мета полягає в тому, щоб придумати «кодову книгу» (рядок бітів для кожного символу), щоб середня довжина коду була зведена до мінімуму. Імовірно, нечасті символи отримають довгі коди, а загальні символи короткі коди, як і в коді Морзе. Алгоритм наступний (ви можете слідувати за допомогою таблиці 5.5):

Ініціалізувати: Нехай частковий код для кожного символу спочатку буде порожнім бітовим рядком. Визначте відповідний кожному символу «набір символів» з лише одним символом у ньому та ймовірністю, рівною ймовірності цього символу.
Loop-test: Якщо є рівно один набір символів (його ймовірність повинна бути 1), ви закінчите. Кодова книга складається з кодів, пов'язаних з кожним із символів у цьому наборі символів.
Loop-action: Якщо є два або більше наборів символів, візьміть два з найменшими ймовірностями (у випадку краватки, виберіть будь-які два). Додайте коди для тих, хто знаходиться в одному наборі символів з 0, а інший з 1. Визначте новий набір символів, який є об'єднанням двох щойно оброблених наборів символів, з імовірністю, рівною сумі двох ймовірностей. Замініть два набори символів на новий. Кількість наборів символів тим самим зменшується на одиницю. Повторюйте цей цикл, включаючи тест циклу, поки не залишиться лише один набір символів.

Зауважте, що ця процедура зазвичай створює код змінної довжини. Якщо є\(n\) різні символи, принаймні два з них мають коди з максимальною довжиною.

Для нашого прикладу ми починаємо з п'яти наборів символів і зменшуємо кількість наборів символів на один крок, поки ми не залишитеся лише з одним. Кроки наведені в таблиці 5.5, а остаточна кодова книга - в таблиці 5.6.

Таблиця 5.5: Кодування Хаффмана для розподілу класів курсу MIT, де '-' позначає порожній бітовий рядок
Початок:	(А = '-' р = 0,25) (Б = '-' р = 0,5) (C = '-' p = 0,125) (D = '-' p = 0,1) (F = '-' р = 0,025)
Наступний:	(А = '-' p = 0,25) (Б = '-' р = 0,5) (C = '-' p = 0,125) (D = '1' F = '0' р = 0,125)
Наступний:	(А = '-' p = 0,25) (Б = '-' р = 0,5) (C = '1' D = '01' F = '00' р = 0,25)
Наступний:	(Б = '-' p = 0,5) (А = '1' C = '01' D = '001' F = '000' р = 0,5)
Фінал:	(Б = '1' А = '01' C = '001' D = '0001' F'0000' р=1,0)

Таблиця 5.6: Кодова книга Хаффмана для типового розподілу класів MIT
Символ	Код
A	0 1
Б	1
C	0 0 1
D	0 0 0 1
F	0 0 0 0

Чи справді цей код компактний? Найбільш частим символом (B) дається найкоротший код, а найменш часті символи (D і F) - найдовші коди, тому в середньому кількість бітів, необхідних для вхідного потоку, який підпорядковується передбачуваному розподілу ймовірностей, дійсно коротка, як показано в таблиці 5.7.

Порівняйте цю таблицю з попередньою таблицею змісту інформації, табл. 5.4. Зверніть увагу, що середня закодована довжина на символ, 1.875 біт, більше, ніж інформація на символ, що становить 1.840 біт. Це пов'язано з тим, що символи D і F не можуть бути закодовані дробовими бітами. Якщо розглядався блок з декількох символів

\ [\ nonumber\ begin {масив} {cllll}
\ текст {Символ} &\ текст {Код} &\ текст {Ймовірність} &\ begin {масив} {c}
\ текст {код}\
\ текст {довжина}
\ кінець {масив} &\ begin {масив} {c}
\ текст {внесок}\\ текст}\
\ текст {до середнього}
\ кінець {масив}\
\ текст {A} & 01 & 0.25 & 2 & 0.5\\
\ текст {B} & 1 & 0.50 & 1 & 0.5\
\ текст {C} & 001 & 0.125 & 3 & 0.375\
\ текст {D} & 0001 & 0.1 & 3.32 & підсилювач; 0.4
\\ текст {F} & 0000 & 0,025 & 5.32 & 0.1\\ [-30pt]
& &\ overline {\ qquad\ quad\ quad} &\ overline {\ qquad\ quad}\
\ [-30pt]\ текст {Всього} & 1.875\ текст {біти}
\ кінець {масив}\ номер\]

Таблиця 5.7: Кодування Хаффмана типового розподілу класу MIT

разом середня довжина коду Хаффмана може бути ближче до фактичної інформації на символ, але не нижче нього.

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

Може статися сплеск D або F класів. Це необхідно, щоб кодер зберігав ці біти до тих пір, поки канал не зможе наздогнати згаяне. Наскільки великий буфер потрібен для зберігання? Що буде, якщо буфер переповнений?
Вивід може бути затриманий через резервну копію буфера. Час між входом і пов'язаним виходом називається «затримкою». Для інтерактивних систем ви хочете зберегти низьку затримку. Кількість оброблюваних бітів в секунду, «пропускна здатність», важливіше в інших додатках, які не є інтерактивними.
Вихід не відбуватиметься через регулярно віднесені проміжки часу, через затримки, викликані сплесками. У деяких додатках реального часу, таких як аудіо, це може бути важливим.
Що робити, якщо ми помиляємось у наших передбачуваних розподілах ймовірностей? Один великий курс може дати менше класів A і B і більше C і D. Наше кодування було б неефективним, і може бути переповнення буфера.
Декодер повинен знати, як розбити потік бітів на окремі коди. Правило в цьому випадку полягає в тому, що перерва після '1' або після '0000', залежно від того, що настане першим. Однак існує багато можливих кодів Хаффмана, що відповідають різним варіантам для 0 та 1, що додаються на кроці 3 алгоритму вище. У більшості немає таких простих правил. Це може бути важко (хоча це завжди можливо) знати, куди слід поставити міжсимвольні розриви.
Саму кодову книгу необхідно заздалегідь віддати як кодеру, так і декодеру. Це можна зробити, передавши кодову книгу по каналу один раз.

Інший приклад

Першокурсники в MIT перебувають на системі «пропуску/без запису» протягом першого семестру в кампусі. Класи A, B і C повідомляються на стенограмах як P (pass), а D і F не повідомляються (для наших цілей ми позначимо це як no-record, N). Давайте створимо систему для передачі цих P і N символів на принтер з найшвидшою середньою швидкістю. Без урахування ймовірностей потрібен 1 біт на символ. Але ймовірності (припускаючи типовий розподіл класу MIT в таблиці 5.3) є\(p(P) = p(A) + p(B) + p(C) = 0.875\), і\(p(N) = p(D) + p(F) = 0.125\). Таким чином, інформація на символ не 1 біт, а лише 0.875 ×\(\log_2(1/0.875)\) + 0,125 ×\(\log_2(1/0.125)\) = 0.544 біта. Кодування Хаффмана на одиночних символах не допомагає. Нам потрібно взяти групи бітів разом. Наприклад, одинадцять класів як блок матимуть 5.98 біт інформації і в принципі можуть бути закодовані, щоб вимагати лише 6 біт для надсилання на принтер.

\(^3\)Boolean digits, or binary digits, are usually called “bits.” The word “bit” also refers to a unit of information. When a boolean digit carries exactly one bit of information there may be no confusion. But inefficient codes or redundant codes may have boolean digit sequences that are longer than the minimum and therefore carry less than one bit of information per bit. This same confusion attends other units of measure, for example meter, second, etc.