Теория кодирования. Кодирование источника. Посимвольное кодирование

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

В рамках теории кодирования, кодом называется некое правило (алгоритм), которое однозначно ставит неким словам над исходным алфавитом некие новые кодовые слова, возможно над другим, целевым, алфавитом.

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

В соответствии с исследуемыми задачами, выделяют четыре различных направления в теории кодирования:

  1. Кодирование источника (сжатие данных)
  2. Кодирование канала (обнаружение и исправление ошибок)
  3. Криптографическое кодирование
  4. Физическое кодирование (модуляция)
Сжатие данных
Теорема Шеннона о кодировании источника говорит нам, что возможно кодирование без потерь, сколь угодно близкое по информационному объёму к энтропии источника. Доказательство, однако, не конструктивно: оно не говорит нам, как именно должен выглядеть оптимальный код, только что он существует. Задача сжатия данных собственно заключается в разработке оптимальных кодов – т.е. дающих максимально близкий к энтропии информационный объем.
Обнаружение и исправление ошибок
Теорема Шеннона о канале с шумом говорит нам, что для произвольного канала с шумом, возможно сконструировать такой код, который позволит передавать по нему данные с произвольно малой вероятностью ошибки. Доказательство, однако, не конструктивно: оно не говорит нам, как именно должен выглядеть оптимальный код, только что он существует. Задача кодирования канала собственно заключается в разработке оптимальных кодов – т.е. дающих максимальную пропускную способность при данной вероятности ошибки, либо минимальную вероятность ошибки при данной пропускной способности.
Криптографическое кодирование
Задача криптографического кодирования, в общем случае, заключается в разработке кодов, которые дают возможность безопасной (в разумных пределах) связи при использовании небезопасных каналов (прослушиваемых потенциально неограниченным кругом третьих лиц).
Модуляция
Задача модуляции заключается в разработке кодов, отображающих дискретный сигнал на непрерывный сигнал в некотором физическом канале. При физическом кодировании в основном решаются вопросы синхронизации приёмника и передатчика, управления частотной полосой пропускания, оптимизации мощности сигнала, и т.п.

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

Сжатие данных в общем случае – это представление информации в меньшем информационном объёме, чем исходные данные. Выделяют сжатие данных без потерь (lossless) и сжатие данных с потерями (lossy).

Сжатие данных без потерь позволяет в точности восстановить исходный сигнал. Сжатие данных с потерями позволяет восстановить некую “достаточно хорошую” аппроксимацию исходного сигнала.

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

В качестве меры “успешности” сжатия без потерь вводится коэффициент сжатия: \[r = \frac{I_S}{I_C},\] где \(I_S\) – информационный объем данных источника, \(I_C\) – информационный объём кодированных данных.

В случае посимвольного кодирования, для сообщения длиной \(n\), \(I_S = n\log |A|,\) где \(A\) – алфавит источника.

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

В модели сжатия с потерями перед кодером добавляется квантователь, задачей которого является понижение размерности алфавита источника таким образом, чтобы в итоге \(X^*\) являлся “достаточно близким” образом исходного сообщения \(X\). Например, в простейшем случае, квантователь может округлять значения. Среднеквадратичное отличие принятых сообщений \(X^*\) и отправленных сообщений \(X\) называется искажением: \[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^*\), любые две различных исходных строки \(\mathbf{x}, \mathbf{y} \in S^*,\) \(\mathbf{x}\neq \mathbf{y}\), имеют различные коды: \(C^*(\mathbf{x}) \neq C^*(\mathbf{y})\)

Мы так же хотим, чтобы средний (ожидаемый) информационный объем кода был минимальный.

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

Необходимое и достаточное условие существования однозначно декодируемых префиксных кодов (и вообще однозначно декодируемых кодов переменной длины) устанавливается неравенством Крафта-МакМиллана:

Теорема (неравенство Крафта-МакМиллана)
Пусть каждый символ исходного алфавита \(S=\{s_1, \ldots, s_n\}\) кодируется однозначно декодируемым кодом с кодовыми словами над алфавитом размерности \(r,\) имеющими длины соответственно \(\{l_1, \ldots, l_n\}.\) Тогда: \[\sum_{i=1}^{n} r^{-l_i} \le 1.\] Обратно, для последовательности чисел \(\{l_1, \ldots, l_n\},\) удовлетворяющей данному неравенству, существует однозначно декодируемый код.
Доказательство (прямая теорема)

Пусть \(S = \sum_i r^{-l_i}.\) Рассмотрим число \[S^N = \sum_{i_1}\ldots\sum_{i_N} r^{-(l_{i_1}+\ldots+l_{i_N})},\] где \(N\in\mathbb N.\)

Число \((l_{i_1}+\ldots+l_{i_N})\) соответствует длине кода для строки длины \(N\) \(\mathbf{x} = a_{i_1}\ldots a_{i_N}.\) В сумме выше, для каждой возможной строки длины \(N\) имеется ровно один такой член. Введём дискретную функцию \(g_N(l),\) значением которой является количество строк \(\mathbf{x}\) длины \(N\), коды которых имеют длину \(l\). Тогда, определяя \(l_{min} = \underset i \min~l_i,\) \(l_{max} = \underset i \max~l_i,\) получаем: \[S^N = \sum_{l=N l_{min}}^{N l_{max}}r^{-l} g_N(l).\] Теперь положим, что код \(C\) является однозначно декодируемым, т.е. \(\forall \mathbf{x} \neq \mathbf{y}: C^*(\mathbf{x}) \neq C^*(\mathbf{y}).\) Рассмотрим \(\mathbf{x}\), имеющий длину кода \(l\). Всего существует \(r^l\) различных потенциально возможных кодов длины \(l\), следовательно, с необходимостью следует, что \(g_N(l) \leq r^l\). Тогда, \[S^N = \sum_{l=N l_{min}}^{N l_{max}}r^{-l} g_N(l) \leq \sum_{l=N l_{min}}^{N l_{max}} 1 = N(l_{max}-l_{min}).\] Отметим, что мы не накладывали ограничений на \(N\), т.е. \[\forall N\in \mathbb N: S^N \leq N(l_{max}-l_{min}).\] Это возможно только, когда \(S\le 1\). Действительно, если \(S>1\), то \(S^N\) является экспоненциальной функцией \(N\), в то время как правая часть \(N(l_{max}-l_{min})\) является линейной функцией \(N\). При \(S>1\), неизбежно \(\exists N_0 \in \mathbb N : \forall N > N_0, S^N > N(l_{max}-l_{min}).\) \(\not \Delta\)

Доказательство (обратная теорема)
Пусть \(l_1 \le \ldots \le l_n\) удовлетворяют неравенству Крафта. Тогда, можно составить однозначный префиксный код, выбирая на каждом шаге \(i=\{1,\ldots, n\}\) код длины \(l_i\) и исключая все коды длин \(l \ge l_i\) с префиксами, совпадающими с этим кодом. На каждом шаге таким образом исключается \(r^{l_n-l_i}\) из всех возможных кодовых слов. Тогда всего при построении кода исключается \(\sum_{i=1}^n r^{l_n-l_i}\) кодовых слов. Ясно, что такой код можно построить, если число исключённых кодовых слов не превышает число всех возможных кодовых слов \(r^{l_n}\). Из неравенства Крафта, \[\sum_{i=1}^{n} r^{-l_i} \le 1,\] \[\sum_{i=1}^{n} r^{l_n-l_i} \le r^{l_n},\] то есть это условие выполняется и код можно построить.
Полный префиксный код
Если префиксный код удовлетворяет неравенству Крафта равенством, т.е. \[\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\).

\(\Delta\):

Рассмотрим \(f(u) = -\log u\) и \(u(x) = \frac{Q(x)}{P(x)}\). \(f(u)\) – выпуклая вниз функция, т.к. \(f''(u) = u^{-2} > 0\). Тогда из нер-ства Йенсена, \[\begin{align} \sum_{x\in X} P(x) f(u(x)) & \ge f(\sum_{x\in X} P(x) u(x)) \\& = -\log {\sum_{x\in X} Q(x)} \\& = 0. \end{align}\] \(\not \Delta\)

Для упрощения выкладок, без ограничения общности, положим двоичный целевой алфавит. Упрощение достигается за счёт того, что информационный объем кодового слова в битах в таком случае численно совпадает с его длиной.

Пусть \(X=\{x_1, \ldots, x_n\}\), \(P(x_i) = p_i\), \(|C(x_i)| = l_i\), \(i=1, \ldots, n\). Тогда, \[L(C,X) = \sum_{i} p_i l_i.\]

Пусть \(q_i = \frac{2^{-l_i}}{z}\), где \(z = \sum_i 2^{-l_i}\). Тогда \(l_i = - \log_2 q_i - \log_2 z\), тогда \[\begin{align} L(C,X) & = -\sum_{i} p_i \log_2 q_i - \log_2 z & (\sum_i p_i = 1) \\& \ge -\sum_{i} p_i \log_2 p_i - \log_2 z & \text{(из н-ва Гиббса)} \\& \ge -\sum_{i} p_i \log_2 p_i - \log_2 1 & \text{(из н-ва Крафта)} \\& = H(X). \end{align}\]

Равенство соответственно достигается в случае \(p_i=q_i\) и \(z=1\), то есть, если \(l_i = - \log_2 p_i,\) т.е. длина двоичного кодового слова \(i\)-го символа равна количеству собственной информации этого символа, и код является полным.

Это важный результат, поэтому повторимся.

Оптимальные длины кодовых слов посимвольного префиксного кода
Ожидаемая длина посимвольного префиксного кода достигает минимума и равняется энтропии источника \(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\), удовлетворяющий неравенствам \[H(X) \le L(C,X) < H(X)+1\]

\(\Delta\): Первое неравенство \(L(C,X) \ge H(X)\) уже доказано выше.

Выберем длины кодовых слов, округлив теоретически оптимальные длины до ближайшего целого вверх: \[l(x) = \left\lceil -log_2 P(x) \right\rceil.\]

Покажем, что префиксный код с такими длинами кодовых слов существует (удовлетворяет нер-ству Крафта): \[\sum_{x\in X} 2^{-l(x)}=\sum_{x\in X} 2^{-\left\lceil -log_2 P(x) \right\rceil}\le \sum_{x\in X} 2^{log_2 P(x)} = 1.\]

Тогда, \[\begin{align} L(C,X) & = \sum_{x \in X} P(x) \left\lceil -log_2 P(x) \right\rceil \\& < \sum_{x \in X} P(x) \left( -log_2 P(x) + 1 \right) \\& = H(x)+1 \end{align}\]

Отметим, что если для кодирования источника с вероятностями \(p_i\) используется полный префиксный код с длинами кодов \(l_i\), то ожидаемая длина кода будет отличаться от энтропии на расстояние Кульбака-Лейблера от оптимального источника данного кода с вероятностями \(q_i = 2^{-l_i}\): \[\begin{align} L(C,X) - H(X) & = \sum_i p_i l_i + \sum_i p_i \log_2 p_i \\ & = -\sum_i p_i \log_2 q_i + \sum_i p_i \log_2 p_i \\ & = \sum_i p_i \log_2 \frac{p_i}{q_i} \\ & = D_{KL}(p||q) \end{align}\]

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

Один из способов построить оптимальный посимвольный код – алгоритм Хаффмана.

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

Более подробное описание доступно здесь

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

Теорема

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

\(\Delta\):

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

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

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

Тогда для алфавита \(A_X=\{x_1,\ldots, x_n\}\), без ограничения общности, положим, что \(P(x_i) \ge P(x_{n-1}) \ge P(x_n),\) \(i\in \{1,\ldots, n-2\}\).

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

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

Из нового префиксного кода с длиной \(\hat L\) мы можем построить код для \(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'\) является длиной оптимального кода, \(\hat L' \ge L'\), но тогда \(\hat L \ge L\), что противоречит \(\hat L \le \widetilde L < L\). Следовательно, код Хаффмана для алфавита размера \(|X|=n\) оптимален.

По индукции, код Хаффмана для любого алфавита размерности \(|X|\ge 2\) оптимален.

\(\not\Delta.\)

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

Код Шеннона

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

Код Шеннона использовался Шенноном при доказательстве теоремы о кодировании источника, однако он не является оптимальным, и никогда не лучше (но иногда эквивалентен) коду Шеннона-Фано.

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

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

Код Шеннона-Фано даёт оценку средней длины \(L(C,X) \le H(X)+2\). Понятно, что он не является оптимальным.

Следует отметить, что подход похож на подход Хаффмана, однако алгоритм Хаффмана строит дерево “снизу вверх”, от листьев, в то время как алгоритм Шеннона-Фано строит дерево “сверху вниз”, от корня.

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

Так же известен как код Гильберта-Мура1

Каждому символу ставится в соответствие число \[F_i = \frac{p_i}{2} + \sum_{j=1}^{i-1} p_j.\]

Кодовым словом \(i\)-го символа выбираются первые \(l_i = \left\lceil -\log_2 p_i \right\rceil + 1\) дробных разрядов двоичного представления числа \(F_i\).

Код Элиаса даёт оценку средней длины \(L(C,X) \le H(X)+2\).

  1. Gilbert E. N., Moore E. F. Variable‐Length Binary Encodings //Bell System Technical Journal. – 1959. – Т. 38. – №. 4. – С. 933-967.↩︎