Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Теорема 3. Если |B| = q и натуральные числа l₁, l₂, …, l_r удовлетворяют неравенству

,

то существует префиксный код B₁, B₂, …, B_r (в алфавите B) такой, что

длина(B_i) = l_i (i = 1, 2, …, r).

Доказательство. Пусть и для любого k существует ровно d_k таких i, что l_i = k, то есть . Тогда надо построить префиксный код, в котором ровно d₁ слов длины 1, d₂ слов длины 2, и т. д., слов длины l_max. Имеем m (1  m  l_max) , или, что то же самое,

.

Рассмотрим это неравенство для m = 1: d₁  q. Для слов длины 1 всего предоставляется возможностей в алфавите мощности q — ровно q вариантов. После выбора d₁ слов длины 1 рассмотрим неравенство для m = 2: d₂  q² – d₁q. Всего слов длины 2 — q², однако все они могут начинаться лишь с тех букв, которые не были выбраны в качестве слов длины 1, следовательно, остаётся ровно q² – d₁q возможностей выбрать слова длины 2, что удовлетворяет условию d₂  q² – d₁q. Пусть уже выбраны d₁ слов длины 1, d₂ слов длины 2, и т. д., d_{m – 1} слов длины m – 1. Тогда для слов длины m разрешено возможностей не меньше, чем

q^m – d_{m – 1}q – d_{m – 2}q² – … – d₂q^{m – 2} – d₁q^{m – 1},

что удовлетворяет условию. Теорема доказана.

Следствие. Если существует взаимно однозначное кодирование со спектром длин слов l₁, l₂, …, l_r в алфавите B, то в B существует префиксный код с тем же спектром длин слов.

§31. Оптимальные коды, их свойства.

Будем рассматривать кодирование A^*  {0, 1}^*. Пусть известны некоторые частоты p₁, p₂, …, p_k появления символов кодируемого алфавита в тексте:

,

l_j — длина j-го кодового слова, p₁ + p₂ + … + p_k = 1, p_j > 0.

При кодировании текста длины N его длина становится примерно равной

.

Определение 1. Ценой (стоимостью, избыточностью) кодирования  называется функция .

Определение 2. Взаимно однозначное кодирование  называется оптимальным, если на нём достигается .

Утверждение 4. Если существует оптимальный код, то существует оптимальный префиксный код с тем же спектром длин слов.

Лемма 1. Если  — оптимальное кодирование и p_i > p_j, то l_i  l_j.

Доказательство. Допустим, что p_i > p_j и l_i > l_j. Рассмотрим кодирование  и рассмотрим кодирование ', в котором переставим кодовые слова B_i и B_j:

, .

Тогда

c () – c (') = (p_il_i + p_jl_j) – (p_il_j + p_jl_i) = (p_i – p_j)(l_i – l_j) > 0  c (') < c (),

следовательно,  не является оптимальным — противоречие.

Лемма доказана.

Лемма 2. Если  — оптимальное префиксное кодирование и , длина(B_j) = l_max, B_j = B_j', где   {0, 1}, то в коде  существует слово B_r такое, что .

Доказательство. Допустим, что в  нет слова . Тогда заменим в  B_j' на B_j'. Получим код ', который является префиксным, но

,

следовательно,  не является оптимальным — противоречие. Лемма доказана.

Лемма 3. Если  — оптимальное префиксное кодирование и
p₁  p₂  …  p_k–1  p_k, то можно так переставить слова в коде , что получится оптимальное префиксное кодирование ' такое, что слова и в нём будут различаться только в последнем разряде.

Доказательство. Пусть p₁  p₂  …  p_k–1  p_k. По лемме 2 в коде  есть слова B0 и B1 максимальной длины. Поменяем их местами с B_k–1 и B_k. Так как p_k–1  p_i и p_k  p_i для 1  i  k – 2, то цена кодирования не увеличится и код останется оптимальным (префиксным). Лемма доказана.

Лемма 4. Рассмотрим кодирования

и ,

где p' + p'' = p_k. Если один из этих наборов префиксный, то второй также префиксный и

c(') = c() + p_k.

Доказательство. Первое утверждение легко проверяется. Далее

c(') – c() = p' · дл(B_k0) + p'' · дл(B_k1) – p_k · дл(B_k) =
= p'(l_k + 1) + p''(l_k + 1) – p_kl_k = (p' + p'')l_k + (p' + p'') – p_kl_k = p_k.

Лемма доказана.

§32. Теорема редукции

Теорема 4 (теорема редукции). Пусть заданы 2 набора частот и 2 набора слов:

и .

1) Тогда если  — оптимальное префиксное кодирование, то и
 — оптимальное префиксное кодирование.

2) Если же  — оптимальное префиксное кодирование и p₁  p₂  …
…  p_k–1  p  p, то  — также оптимальное префиксное кодирование.

Доказательство. 1) Очевидно, из префиксности  следует префиксность . Допустим, что  не оптимально. Тогда существует префиксный код ₁: c(₁) < c() для тех же распределений частот. Пусть

.

Рассмотрим новое кодирование

.

По лемме 4, кодирование ₁ также является префиксным и

.

Следовательно,  не является оптимальным кодированием, что противоречит условию. Остаётся предположить, что  оптимально.

2) Пусть  — оптимальное префиксное кодирование и p₁  p₂  …
…  p_k–1  p  p. Допустим, что  не оптимально. Тогда по лемме 3 для частот p₁, p₂, …, p_k–1, p, p существует оптимальное префиксное кодирование ₁: D₁, …, D_k–1, D_k0, D_k1 и c(₁) < c(). Тогда для частот p₁, p₂, …, p_k рассмотрим кодирование ₁: D₁, …, D_k–1, D_k. Получим

c(₁) = c(₁) – p_k < c() – p_k = c()  c(₁) < c()

и  не оптимально, что противоречит условию. Теорема доказана.

§33. Коды с исправлением r ошибок. Оценка функции M_r (n)

Будем рассматривать равномерные коды в алфавите {0, 1}, длины всех слов, равные n, и ошибки типа замещения, то есть изменение разрядов 0  1 и 1  0.

Определение 1. Код называется исправляющим r ошибок, если при наличии в любом кодовом слове не более r ошибок типа замещения можно восстановить исходное кодовое слово.

Определение 2. Расстоянием Хэмминга между 2 наборами длины n называется число разрядов, в которых эти наборы различаются.

Определение 3. Шаром (сферой) радиуса r с центром в точке называется множество всех наборов длины n, расстояние от которых до не превосходит r (в точности равно r).

Определение 4. Кодовым расстоянием называется расстояние по Хэммингу

.

Утверждение 1. Код исправляет r ошибок тогда и только тогда, когда

.

Доказательство. Заметим, что условие утверждения эквивалентно тому, что расстояние между центрами шаров радиуса r (кодовыми словами) не меньше, чем 2r + 1, что эквивалентно тому, что эти шары не пересекаются. Таким образом, на выходе получится слово, принадлежащее единственному однозначно определённому шару (если в слове не более r ошибок), что позволяет точно восстановить слово, так как известен центр этого шара. Утверждение доказано.

Определение 5. Код обнаруживает r ошибок, если при наличии в нём не более r ошибок типа замещения можно сказать, были ошибки, или их не было.

Утверждение 2. Код обнаруживает r ошибок тогда и только тогда, когда

 _min (K)  r + 1.

Доказательство. Условие утверждения эквивалентно тому, что ни один из центров шаров (кодовое слово) не содержится в каком-либо другом шаре, то есть если произошло не более r ошибок, можно в точности установить, что полученное на выходе слово не совпадает с центром одного из шаров. Утверждение доказано.

Определение 6. Функция M_r (n) есть максимальное число слов длины n, образующих код, исправляющий r ошибок. S_r (n) — число точек (наборов длины n) в шаре радиуса r.

Утверждение 3. .

Доказательство. Точки шара радиуса r — это его центр, множество наборов, отличающихся от центра в одной координате — , множество наборов, отличающихся от центра в 2 координатах — , и т. д. Получаем утверждение.

Теорема 5. .

Доказательство. Рассмотрим произвольный код , исправляющий r ошибок. Из утверждения 1 следует, что шары радиуса r с центрами в не пересекаются, следовательно, число всех точек всех шаров не превосходит числа точек n-мерного куба и

.

Теперь будем строить код , исправляющий r ошибок. Выберем произвольно точку . Для выбора точки запрещено S_2r(n) точек, так как запрещены все точки одного шара и все точки, расположенные от любой граничной точки на расстояние, не больше, чем r, то есть все точки шара радиуса 2r с центром в точке . Пусть уже выбраны наборы . Для выбора набора запрещено точек не больше, чем k·S_2r (n), то есть, если k·S_2r (n) < 2ⁿ, то можно выбрать . Если тупик наступит после выбора m-го набора, то

.

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

§34. Коды Хэмминга. Оценка функции M₁ (n).

Рассмотрим коды, исправляющие одну ошибку типа замещения в словах длины n. Выберем натуральное k таким, что

.

Разобьём номера всех разрядов исходного слова на k классов:

D_i = {m | m = (m_k–1m_k–2…m₀)₂, m_i = 1}, 1  m  n.

так, например, D₀ = {1, 3, 5, 7, …}, D₁ = {2, 3, 6, 7, …}, D₂ = {4, …}.

Определение. Кодом Хэмминга порядка n называется множество наборов

,

Характеристики

Список файлов лекций