Теория кодирования

Изучает свойства различных кодов и их применимость в конкретных задачах.

Код: Пусть \(S\) и \(T\) – конечные множества, называемые соответственно исходным и целевым алфавитами. Код \(C: S^* \to T^*\) есть всюду определённая функция, отображающая элементы \(S^*\) – слова (последовательностей символов) над исходным алфавитом – на элементы множества \(T^*\) – слова над целевым алфавитом.

Направления:

Кодирование источника (сжатие данных)
Кодирование канала (обнаружение и исправление ошибок)
Криптографическое кодирование
Физическое кодирование (модуляция)

Сжатие данных

Представление информации в меньшем информационном объёме, чем исходные данные.

Выделяют:

сжатие данных без потерь (lossless)
сжатие данных с потерями (lossy)

Модель сжатия без потерь

Коэффициент сжатия: \(r = \frac{I_S}{I_C},\)
\(I_S\) – информационный объем данных источника, \(I_C\) – информационный объём кодированных данных
В случае посимвольного кодирования, для сообщения длиной \(n\), \(I_S = n\log |A|,\) где \(A\) – алфавит источника.

Модель сжатия с потерями

перед кодером добавляется квантователь
понижает размерность алфавита источника
например, округление
искажение: \(D = \frac{1}{N} \sum_{i=1}^{N} (x_i - x^*_i)^2.\)

Требования:

однозначность декодирования
однозначность чтения кодовых слов
- Использование разделительных кодов
- Использование кодов одинаковой длины (равномерное кодирование)
- Использование префиксных кодов

энтропия кодированного сигнала должна быть максимальна (т.е. количество информации на символ кода – максимально), следовательно:

Символы целевого алфавита должны быть практически равновероятны
Последовательные символы на выходе кодера практически независимы

префиксные коды – наиболее экономные
Предел оптимального кодирования – из теорема о кодировании источника: математическое ожидание длины кодового слова не может быть меньше энтропии источника.

Посимвольное кодирование

кодирование без памяти
простейший метод кодирования

Посимвольный код: Пусть \(S\) и \(T\) – конечные множества, называемые соответственно исходным и целевым алфавитами. Посимвольный код \(C: S \to T^*\) есть всюду определённая функция, отображающая элементы \(S\) – символы исходного алфавита – на элементы \(T^*\) – слова над целевым алфавитом.

Расширение посимвольного кода: Обобщение посимвольного кода \(C: S \to T^*\) на код \(C^*: S^* \to T^*\), совершаемое конкатенацией посимвольных кодов.
Префиксный код: Такой код, в котором ни одно кодовое слово меньшей длины не является префиксом никакого кодового слова большей длины.

Однозначно декодируемый посимвольный код: Посимвольный код \(C: S \to T^*\) является однозначно декодируемым, если в расширенном коде \(C^*\), любые две различных исходных строки \(\vect{x}, \vect{y} \in S^*,\) \(\vect{x}\neq \vect{y}\), имеют различные коды: \(C^*(\vect{x}) \neq C^*(\vect{y})\)

Ожидаемая длина кодового слова (средняя длина кода): Математическое ожидание длины кодового слова из кода \(C\) над источником \(X\) обозначается \(L(C, X)\) и называется ожидаемой (средней) длиной кодового слова: \[L(C,X) = \sum_{x\in X} P(x) |C(x)|,\] где \(|C(x)|\) – длина кодового слова \(C(x).\)

Неравенство Крафта-МакМиллана

Необходимое и достаточное условие существования однозначно декодируемого расширения \(C^*\) посимвольного кода \(C\):

\[\sum_{i=1}^{|A|} r^{-|C(a_i)|} \le 1\]

\(|A|\) – мощность исходного алфавита \(A=\{a_1, \ldots, a_n\}\)
\(r\) – мощность целевого алфавита
\(|C(a_i)|\) – длины соответствующих кодовых слов.

Доказательство (необходимость)

Пусть \(S = \sum_i r^{-|C(a_i)|}\) – левая часть неравенства.

Рассмотрим число \(S^N\), \(N\in\mathbb N.\)

\[S^N = \paren{\sum_i r^{-|C(a_i)|}}^N\]

\[S^N = \sum_{i_1}\ldots\sum_{i_N} r^{-\paren{|C(a_{i_1})|+\ldots+|C(a_{i_N})|}}\]

\(|C^*(\vect x)| = |C(a_{i_1})|+\ldots+|C(a_{i_N})|\) – длина кода \(C^*(\vect x)\) строки \(\vect{x} = \overline{a_{i_1}\ldots a_{i_N}}.\)
В \(S^N\) для каждой такой строки ровно один член \(r^{-\paren{|C(a_{i_1})|+\ldots+|C(a_{i_N})|}}\)

\[S^N = \sum_{i_1}\ldots\sum_{i_N} r^{-\paren{|C(a_{i_1})|+\ldots+|C(a_{i_N})|}}\]

\[S^N = \sum_{l=N l_{min}}^{N l_{max}}r^{-l} g_N(l)\]

\[g_N(l) = |\{ \vect x | \vect x \in A^*, |\vect x| = N, |C^*(\vect x)| = l\}|\]

\[l_{min} = \underset{a\in A} \min~|C(a)|\]

\[l_{max} = \underset{a\in A} \max~|C(a)|\]

\[S^N = \sum_{l=N l_{min}}^{N l_{max}}r^{-l} g_N(l)\]

Код \(C\) – однозначно декодируем

\[\forall \vect x \in A^*, \vect y \in A^*, \vect x \neq \vect y: C^*(\vect x) \neq C^*(\vect y)\]

Рассмотрим \(\vect x\), \(|C^*(\vect x)| = l\). \(\exists~r^l\) различных возможных кодов длины \(l\). Тогда

\[g_N(l) \leq r^l\]

\[S^N = \sum_{l=N l_{min}}^{N l_{max}}r^{-l} g_N(l)\]

\[g_N(l) \leq r^l\]

\[S^N\leq \sum_{l=N l_{min}}^{N l_{max}} r^{-l} r^l\]

\[~\]

\[S^N \leq \sum_{l=N l_{min}}^{N l_{max}} 1\]

\[~\]

\[S^N \leq N(l_{max}-l_{min})+1\]

\[~\]

\[\forall N\in \mathbb N :\]

\[S^N \leq N(l_{max}-l_{min})+1\]

\[\phantom{\sum_i r^{-|C(a_i)|}} S\le 1 \qquad\phantom\blacksquare\]

\[\phantom{S}{\sum_i r^{-|C(a_i)|}}\le 1\qquad\phantom\blacksquare\]

\[\phantom{S}{\sum_i r^{-|C(a_i)|}}\le 1\qquad\blacksquare\]

Доказательство (достаточность)

Пусть \(l_1 \le \ldots \le l_n\).

Пошагово построим префиксный код.

На каждом шаге \(i=\{1,\ldots, n\}\), выбираем код для \(a_i\), такой, что \(|C(a_i)| = l_i\).

Код – префиксный

Выбрав \(\vect c_i = C(a_i)\), \(|\vect c_i|=l_i,\) нельзя выбрать \(\vect c_j\), имеющий префикс \(\vect c_i\).

На каждом шаге исключается \(r^{l_m - l_i}\) кодовых слов длины \(l_m \ge l_i\) (считая присвоенный)

Всего \(r^{l_n}\) возможных кодов длины \(l_n\). Тогда на \(n\)-том шаге, когда мы должны выбрать код длины \(l_n\), должен быть хотя бы один свободный, т.е.

\[\sum_{i=1}^{n-1} r^{l_n - l_i} + 1 \le r^{l_n}\]

\[\sum_{i=1}^{n-1} r^{l_n - l_i} + r^{l_n-l_n} \le r^{l_n}\]

\[\sum_{i=1}^{n} r^{l_n - l_i} \le r^{l_n}\]

\[\sum_{i=1}^{n} r^{l_n} r^{- l_i} \le r^{l_n}\]

\[r^{l_n} \sum_{i=1}^{n} r^{- l_i} \le r^{l_n}\]

\[\sum_{i=1}^{n} r^{- l_i} \le 1\]

т.е. код можно построить, если \(l_i\) удволетворяют неравенству Крафта-МакМиллана.\(\blacksquare\)

Полный префиксный код: Если префиксный код удовлетворяет неравенству Крафта равенством, т.е. \[\sum_{i=1}^{n} r^{-l_i} = 1,\] такой код называется полным.

Теорема о кодировании источника ограничивает снизу максимально достижимое сжатие
Сохраняется ли это ограничение при посимвольном кодировании?
Поэтому, найдём нижнюю границу ожидаемой длины кода \(L(C, X).\)
Сперва докажем неравенство Гиббса.

Неравенство Гиббса

Расстояние Кульбака-Лейблера неотрицательно: \[D_{KL}(P||Q) = \sum_{x\in X} P(x) \log\left(\frac{P(x)}{Q(x)}\right) \ge 0\] где \(P,Q\) – распределения вероятностей случайной дискретной величины \(X\).

Пусть \(f(u) = -\log u\), \(u(x) = \frac{Q(x)}{P(x)}\).

\(f(u)\) – выпуклая вниз функция, т.к. \(f''(u) = u^{-2} > 0\).

Тогда из нер-ства Йенсена,

\[ \sum_{x\in X} P(x) f(u(x)) \ge f(\sum_{x\in X} P(x) u(x)) \]

\[ -\sum_{x\in X} P(x) \log u(x) \ge -\log\paren{\sum_{x\in X} P(x) u(x)} \]

\[ -\sum_{x\in X} P(x) \log \frac{Q(x)}{P(x)} \ge -\log\paren{\sum_{x\in X} P(x) \frac{Q(x)}{P(x)}} \]

\[ -\sum_{x\in X} P(x) \log \frac{Q(x)}{P(x)} \ge -\log\paren{\sum_{x\in X} Q(x)} \]

\[ -\sum_{x\in X} P(x) \log \frac{Q(x)}{P(x)} \ge -\log 1 \]

\[ -\sum_{x\in X} P(x) \log \frac{Q(x)}{P(x)} \ge 0 \]

\[ \phantom{D_{KL}(P||Q) =} \sum_{x\in X} P(x) \log \frac{P(x)}{Q(x)} \ge 0 \phantom{\qquad\blacksquare} \]

\[ D_{KL}(P||Q) = \sum_{x\in X} P(x) \log \frac{P(x)}{Q(x)} \ge 0 \phantom{\qquad\blacksquare} \]

\[ D_{KL}(P||Q) = \sum_{x\in X} P(x) \log \frac{P(x)}{Q(x)} \ge 0 \qquad\blacksquare \]

Следствие

\[\sum_{x\in X} P(x) \log\left(\frac{P(x)}{Q(x)}\right) \ge 0\]

\[\sum_{x\in X} P(x) \paren{\log{P(x)} - \log{Q(x)}} \ge 0\]

\[\sum_{x\in X} P(x) \log{P(x)} - \sum_{x\in X} P(x)\log{Q(x)} \ge 0\]

\[\sum_{x\in X} P(x) \log{P(x)} \ge \sum_{x\in X} P(x)\log{Q(x)}\phantom{\qquad(*)}\]

\[\sum_{x\in X} P(x) \log P(x) \ge \sum_{x\in X} P(x) \log Q(x)\qquad(*)\]

Ожидаемая длина кода

Положим двоичный целевой алфавит (длина кода равна информационному объёму в битах)

\[L(C,X) = \sum_{x\in X} P(x) |C(x)| \ge H(X)\]

\[\text{Let}~~ Q(x) = \frac{2^{-|C(x)|}}{\sum_{x\in X} 2^{-|C(x)|}} \Rightarrow\]

\[|C(x)| = |C(x)|\]

\[|C(x)| = \log_2 \paren{2^{|C(x)|}}\]

\[|C(x)| = -\log_2 \paren{2^{-|C(x)|}}\]

\[|C(x)| = - \log_2 \paren{Q(x) \sum_{x\in X} 2^{-|C(x)|}}\]

\[|C(x)| = - \log_2 Q(x) - \log_2 \sum_{x\in X} 2^{-|C(x)|}\]

\[L(C,X)\]

\[= \sum_{x\in X} P(x) |C(x)|\]

\[= \sum_{x\in X} P(x) \paren{- \log_2 Q(x) - \log_2 \sum_{x\in X} 2^{-|C(x)|}}\]

\[= -\sum_{x\in X} P(x) \log_2 Q(x) -\sum_{x\in X} P(x) \log_2 \sum_{x\in X} 2^{-|C(x)|}\]

\[= -\sum_{x\in X} P(x) \log_2 Q(x) -\paren{\log_2 \sum_{x\in X} 2^{-|C(x)|}}\paren{\sum_{x\in X} P(x)}\]

\[= -\sum_{x\in X} P(x) \log_2 Q(x) -\paren{\log_2 \sum_{x\in X} 2^{-|C(x)|}}\cancelto{1}{\paren{\sum_{x\in X} P(x)}}\]

\[= -\sum_{x\in X} P(x) \log_2 Q(x) -\log_2 \sum_{x\in X} 2^{-|C(x)|}\]

\[L(C,X) = -\sum_{x\in X} P(x) \log_2 Q(x) -\log_2 \sum_{x\in X} 2^{-|C(x)|}\]

\[L(C,X) \ge -\sum_{x\in X} P(x) \log_2 Q(x) -\cancelto{0}{\log_2 \sum_{x\in X} 2^{-|C(x)|}}\]

\[L(C,X) \ge -\sum_{x\in X} P(x) \log_2 Q(x)\]

\[L(C,X) \ge -\sum_{x\in X} P(x) \log_2 P(x)\]

\[L(C,X) \ge H(X)\]

Н-во Крафта \[\sum_{x\in X} 2^{-|C(x)|} \le 1\]

Н-во Гиббса (сл-е) \[\sum_{x\in X} P(x) \log P(x) \ge \sum_{x\in X} P(x) \log Q(x)\]

Равенство только, если код – полный (\(\sum_{x\in X} 2^{-|C(x)|} = 1\)) и \(P(x) = Q(x) = 2^{-|C(x)|}\).

\(P(x) = 2^{-|C(x)|}\)
\(\log_2 P(x) = -|C(x)|\)
\(|C(x)| = -\log_2 P(x)\)
\(|C(x)| = I(x)\)

Оптимальные длины кодовых слов посимвольного префиксного кода: Ожидаемая длина посимвольного префиксного кода достигает минимума и равняется энтропии источника \(H(X)\) тогда и только тогда, когда длины кодовых слов соответствующих символов равны количеству собственной информации соответствующих символов \[|C(x)| = -\log_2 P(x)\]

Оптимальный источник для посимвольного кодера \(C\)

Определяется распределением вероятностей \[P(x) = \frac{2^{-|C(x)|}}{\sum_{x'\in X} 2^{-|C(x')|}}.\]

Если код полный, \(\sum_{x'\in X} 2^{-|C(x')|} = 1\) и \[P(x) = 2^{-|C(x)|}.\]

Верхняя граница длины оптимального кода

Для источника случайной переменной \(x\) из ансамбля \(X\) существует префиксный код \(C\), удовлетворяющий \[L(C,X) < H(X)+1\]

Выберем ближайшие возможные к оптимальным длины кодов:

\[|C(x)| = \ceil{-\log_2 P(x)}\]

Такой код существует (по н-ву Крафта): \[\sum_{x\in X} 2^{-|C(x)|}=\sum_{x\in X} 2^{-\ceil{-\log_2 P(x)}}\le \sum_{x\in X} 2^{\log_2 P(x)} = 1\]

\[L(C,X) = \sum_{x \in X} P(x) |C(x)|\]

\[L(C,X) = \sum_{x \in X} P(x) \ceil{-\log_2 P(x)}\]

\[L(C,X) < \sum_{x \in X} P(x) \paren{-\log_2 P(x) + 1}\]

\[L(C,X) < -\sum_{x \in X} P(x) \log_2 P(x) + \sum_{x \in X} P(x)\]

\[L(C,X) < -\sum_{x \in X} P(x) \log_2 P(x) + \cancelto{1}{\sum_{x \in X} P(x)}\]

\[L(C,X) < -\sum_{x \in X} P(x) \log_2 P(x) + 1\]

\[L(C,X) < \cancelto{H(X)}{-\sum_{x \in X} P(x) \log_2 P(x)} + 1\]

\[L(C,X) < H(x)+1\phantom{\qquad\blacksquare}\]

\[L(C,X) < H(X)+1\qquad\blacksquare\]

Замечание. Пусть \(C\) – полный код.

\(L(C,X) - H(X)\)

\[= \sum_{x\in X} P(x) |C(x)| + \sum_{x\in X} P(x) \log_2 P(x)\]

\[= \sum_{x\in X} P(x) \paren{|C(x)| + \log_2 P(x)}\]

\[= \sum_{x\in X} P(x) \paren{-\log_2 2^{-|C(x)|} + \log_2 P(x)}\]

\[= \sum_{x\in X} P(x) \log_2 \frac{P(x)}{2^{-|C(x)|}}\]

\[= D_{KL}(P||2^{-|C(x)|})\]

\(2^{-|C(x)|}\) – распределение вероятностей оптимального источника.

Алгоритм Хаффмана

Один из способов построить оптимальный посимвольный код

Алгоритм Хаффмана

Возьмём два наименее вероятных символа исходного алфавита. Этим символам будут назначены кодовые слова максимальной (одинаковой) длины, и они будут отличаться только последним битом.
Отождествим эти символы.
Если в рассмотрении более 1 символа, перейдём к шагу 1.

каждая итерация уменьшает число рассматриваемых символов на 1,
алгоритм завершится за \(|X|-1\) итераций
\(|X|\) – размер алфавита источника \(X\).

Оптимальность алгоритма Хаффмана

Код, составленный по алгоритму Хаффмана, оптимален.

Доказательство

индукция по размеру алфавита \(|X|\).

База: \(|X| = 2\), ожидаемая длина кода Хаффмана \(L=1\). Код очевидно оптимален.

Шаг: Пусть алгоритм Хаффмана даёт оптимальный код для алфавита размера \(|X|=n-1\).

Рассмотрим алфавит \(A_X=\{x_1,\ldots, x_n\}\)
БОО пусть \(\forall i\in \{1,\ldots, n-2\} : P(x_i) \ge P(x_{n-1}) \ge P(x_n)\)

В процессе работы будет построен код для источника \(X'\) с алфавитом \(A_{X'}=\{x_1,\ldots,x_{n-2}, x'\},\)
\(P(x') = P(x_{n-1})+P(x_n)\)
\(L(\mathrm{Huf}(X'),X')=L'\)
По предположению индукции, этот код оптимален.

Пусть \(L(\mathrm{Huf}(X),X)=L\)
Допустим, такой код не оптимален
Тогда существует другой код \(\widetilde C: L(C,X) = \widetilde L < L\)
можем построить полный префиксный код \(\hat C\), такой, что коды для \(x_{n-1}\) и \(x_n\) отличаются только последним битом, а его средняя длина \(\hat L \le \widetilde L\).

Из \(\hat C\) построим код для \(X'\), сохранив коды для \(x_1,\ldots,x_{n-2}\) и назначив общий префикс кодов \(x_{n-1}\) и \(x_n\) в качестве кода \(x'\). Пусть его средняя длина \(\hat L'\)
два символа из \(X\) отождествляются в \(X'\)
отождествлённый символ \(x'\) имеет кодовое слово на 1 бит короче:
\(L = L' + P(x'),\)
\(\hat L = \hat L' + P(x').\)

\(L = L' + P(x'),\)
\(\hat L = \hat L' + P(x').\)

По предположению индукции \(L'\) оптимальна, значит \(\hat L' \ge L'\),
тогда \(\hat L \ge L\), что противоречит \(\hat L \le \widetilde L < L\).
код Хаффмана для алфавита размера \(|X|=n\) оптимален.
По индукции, верно для любого алфавита размерности \(|X|\ge 2\)

\(\qed\)

Другие алгоритмы посимвольного кодирования

Код Шеннона

Все символы алфавита источника упорядочиваются по убыванию вероятности.
Каждому символу ставится в соответствие “кумулятивная вероятность” \(q_i = \sum_{j=1}^{i-1} p_j\).
Кодовым словом для \(i\)-го символа являются \(l_i = \ceil{-log_2 p_i}\) разрядов дробной части из двоичного представления \(q_i\).
использовался Шенноном в наброске доказательства теоремы о кодировании источника
не является оптимальным
и никогда не лучше (но иногда эквивалентен) кода Шеннона-Фано.

Код Шеннона-Фано

Все символы алфавита источника упорядочиваются по убыванию вероятности
Полученный массив делится на две непрерывные части, максимально близкие по сумме вероятностей входящих в них символов
Одной из этих частей присваивается метка “0”, второй – метка “1”
Алгоритм рекурсивно повторяется для каждой из частей, пока не дойдёт до единственного символа
Кодом символа – последовательность меток

\(L(C,X) \le H(X)+2\) – не является оптимальным.
похож на подход Хаффмана
Хаффман строит дерево “снизу вверх”, от листьев
Шеннон-Фано – “сверху вниз”, от корня.

Код Элиаса (Шеннона-Фано-Элиаса)

Так же известен как код Гильберта-Мура
Каждому символу ставится в соответствие число \[F_i = \frac{p_i}{2} + \sum_{j=1}^{i-1} p_j.\]
Кодовым словом \(i\)-го символа выбираются первые \(l_i = \ceil{-\log_2 p_i} + 1\) дробных разрядов двоичного представления числа \(F_i\).
\(L(C,X) \le H(X)+2\).