Раздел 2. Сжатие информации.

Кодирование информации. Количество информации. Сжатие информации.

Большая часть раздела посвящена понятию количества информации (энтропии) и теореме Шеннона. Но вначале приведем несколько известных способов преобразования информации с целью обеспечения ее дешифруемости и сжатия, не использующих понятия энтропия.

Сериальное кодирование

Здесь А = (0,1) иB = (0,1,…,9,*). Символ * играет роль разделителя.

В данном примере битовые последовательности кодируются натуральными числами. Как это следует из свойств данного кодирование, оно дает эффект сжатия, когда битовые последовательности представляют собой чередование сравнительно больших блоков нулей и единиц.

Алгоритм кодирования. Пусть дана битовая последовательность α и а (0,1) ее первый символ. Блоком назовем часть последовательности, состоящую из одинаковых символов. Тогда любую битовую последовательность можно представить как чередование блоков из нулей и единиц. Пусть в последовательности α всегоS блоков, длина первого x₁, длина второго - x₂,…, длинаS –го -x_S.Тогда кодом α будет слово β=φ(α)=а*x₁*x₂*…*x_S.

Алгоритм декодирования очевиден.

Определение. Длиной сериального кода назовем число где [ log x]*=1 при x=1 и [ log x] при x>1.

Определение. Средней длиной кода для n-последовательностей назовем число

,

Где сумма берется по всем двоичным последовательностям длины n.

Свойства такого кодирования иллюстрируются следующими двумя утверждениями.

Утверждение. Если все x_i=1, то l(α)=|α|.

Утверждение. Если все x_i>1, то .

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

.

Из этих утверждений следует.

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

Если серии короткие и их много, например: и , то эффекта сжатия не возникает.

Для полноты картины приведем два утверждения, доказанные в [7].

Утв. Средняя длина слова с S сериями в сериальном кодировании
.

Утв. Справедлива асимптотическая оценка

Алфавитное кодирование.

Если пренебречь разделителями, то в качестве двух алфавитов возьмем алфавиты

А = (а ₁, …, а_n) иB = (b ₁, …, b_q).

Алгоритм кодирования. Каждой букве a_i алфавита A ставится в соответствие B_i=φ(a_i) – словов алфавите Bдлины l_i.

Алфавитное кодирование будет дешифруемым, если отображение таково, что для .

 

Заметим, что в приведенном определении термин дешифруемость используется в другом смысле, нежели выше при описании основных свойств кодирования (дешифруемость – неизбыточность-разумность). Поэтому в других учебниках по теории информации используются иные термины, например, разделимость.

Обратим внимание на следующий важнейший факт, который, по сути дела, и оправдывает интерес к такому виду кодирования. Очевидно, что ограничение на вид отображения φ сразу влечет дешифруемость однобуквенных (в алфавите А) слов. Но из дешифруемости однобуквенных слов сразу следует дешифруемость слов (в алфавитеA) любой длины.

Заметим также, что в случае дешифруемого кодирования все слова B_i=φ(a_i) обязательно различны.

Оказывается, что дешифруемость накладывает ограничение на набор длин кодовых слов. Об этом говорит утверждение, известное как неравенство Крафта.

Неравенство Крафта.

Теорема. Если алфавитное кодирование с длиной кодов l ₁, …, l_n дешифруемо, то выполняется неравенство:

Доказательство. Пусть А = (а ₁, …, а_n) иB = (b ₁, …, b_q). Каждой букве a_i алфавита A ставится в соответствие B_i=φ(a_i) – словов алфавите Bдлины l_i. Положим

Пусть . ВозведемZ в некоторую степень m, тогда

.

Здесь введено обозначение S (n, t) – числословдлиныtивида B_{i 1} B_{i 2} …B_in. Из дешифруемости следует, что все такие слова различны, но число различных слов длины tв алфавите из qбукв не превосходит q^t, поэтому

S (n, t) q^t.

Тогда , где m – натуральное, а l ≥ 0, целое. Это неравенство должно выполняться для любого m, но это возможно только тогда, когда Z не превосходит единицы, т.е.

.

Утверждение доказано.

Префиксные коды.

Опр. Слово α является подсловом слова β, если существуют слова γ и δ (возможно пустые) такие, что β=γαδ.

В общем случае из неравенства Крафта не следует дешифруемость.

Опр. Кодирование называется префиксным, если ни одно из кодовых слов не является началом другого.

Теорема. Префиксный код дешифруем.

Доказательство: Пусть есть α и β – два слова:

Покажем, что из равенства φ (α) = φ (β)следует равенство α = β.

Пусть

Поочередно слева направо сравниваем подслова слов α и β, используя знание функции ϕ, которая определяет наше побуквенное кодирование (эта функция позволяет находить B_i=φ(a_i) среди подсловслов α и β. Сначала сравниваем и , затем переходим к и и т.д.

Если длины слов и одинаковы, то сами слова должны быть одинаковыми из того, что Если длины слов разные, то одно из двух слов: или – начало другого, что противоречит определению префиксности.

Значит, α = β.

Теорема доказана.

Из теоремы сразу следует алгоритм декодирования префиксного кода.

Алгоритм декодирования. Берем первый символ слова φ (α)и ищем однобуквенное слово среди кодовых слов. Если находимтакое слово, например, B_i=φ(a_i), то декодируем словоB_i=φ(a_i) в букву a_i и продолжаем работать, начиная со следующего символа слова φ (α). Если не находим, то добавляем следующий символ и ищем среди кодовых слов уже двухбуквенное слово. И т.д.

В случае алфавитного кодирования можно ограничиться префиксными кодами, так как, в каком-то смысле, любой дешифруемый алфавитный (побуквенный) код можно «свести к префиксному». А существование префиксного кода полностью определяется неравенством Крафта.

Теорема (о существовании префиксного кода). Префиксный код с длинами кодов l ₁ … l_n существует тогда и только тогда, когда выполняется неравенство Крафта

.

Доказательство. Т.к. префиксный код дешифруем, то выполняется неравенство Крафта. С другой стороны, пусть выполняется неравенство Крафта. Покажем, что в этом случае существует префиксный код. Мы просто опишем алгоритм построения такого кода, т.е. построим отображениеB_i=φ(a_i).

Пусть . Пусть среди чисел l ₁ … l_n имеется S ₁единиц, S ₂ двоек, S ₃ троек и т.д. до S _lслов длиныl. При этом некоторые из S _iмогут быть нулями. Упорядочим B_i=φ(a_i) по возрастанию длины.

 

 

B ₁ = | l ₁| = 1

B ₂ = | l ₂| = 1 S ₁словдлины 1

…

B_{S 1}= | l_{S 1}| =1

B_{S 1+1} = | l_{S 1+1}| = 2 S ₂словдлины2

…

 

Тогда левую часть неравенства Крафта можно представить в виде:

S ₁ S ₂ S ₃

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

Первый шаг: Любые S ₁букв в B можно использовать для кодирования слов длины. Это следует из того, что при выполнении неравенства Крафта справедливо соотношение: S ₁/ q ≤ 1, из которого следует, что S ₁≤q. Таким образом мы получили первую группу однобуквенных слов.

Второйшаг: Аналогично из неравенства Крафта получаем S ₁/ q+ S ₂/ q ≤ 1. Отсюда S ₁ q + S ₂ ≤ q ², S ₂ ≤ q ² – s ₁ q. Поэтому можно взять S ₂ слов длины 2 в алфавите B так, что они не начинаются со слов первой группы.Таким образом мы получили вторую группу двухбуквенных слов.

Третийшаг: На этом шаге строим группу трехбуквенных слов так, чтобы они не начинались с ранее построенных слов. Такие трехбуквенные слова в нужном количестве существуют, так как вновь из неравенства Крафта следует, что S ₁ /q + S ₂ /q + S₃ / q ≤ 1. А это означает, что S₃ ≤ q³ – qS ₂ – q ² S ₁.

Таким образом проходим все lшагов и в результате получаем дешифруемый префиксный код.

Теорема доказана.