Алексеев В.Б. Лекции по дискретной математике, страница 9

Пустьri =1то естьl maxdk∑qk =1k1∑qli≤ 1 и для любого k существует ровно dk таких i, что li = k,≤ 1 . Тогда надо построить префиксный код, в котором ровно d1 слов длины 1, d2слов длины 2, и т. д., dl max слов длины lmax. Имеем ∀m (1 ≤ m ≤ lmax)mdk∑qk =1k≤ 1 , или, что то жесамое,()d1 d 2dd+ 2 + ! + mm−−11 + mm ≤ 1 ⇔ d m ≤ q m − d1q m−1 + d 2 q m−2 + ! + d m−1q .q qqqРассмотрим это неравенство для m = 1: d1 ≤ q. Для слов длины 1 всего предоставляется возможностей в алфавите мощности q — ровно q вариантов. После выбора d1 слов длины 1 рассмотрим неравенство для m = 2: d2 ≤ q2 – d1q.

Всего слов длины 2 — q2, однако все они могутначинаться лишь с тех букв, которые не были выбраны в качестве слов длины 1, следовательно, остаётся ровно q2 – d1q возможностей выбрать слова длины 2, что удовлетворяет условию d2 ≤ q2 – d1q. Пусть уже выбраны d1 слов длины 1, d2 слов длины 2, и т. д., dm – 1 словдлины m – 1. Тогда для слов длины m разрешено возможностей не меньше, чемqm – dm – 1q – dm – 2q2 – … – d2qm – 2 – d1qm – 1,что удовлетворяет условию. Теорема доказана.Следствие.

Если существует взаимно однозначное кодирование со спектром длин словl1, l2, …, lr в алфавите B, то в B существует префиксный код с тем же спектром длин слов.§31. Оптимальные коды, их свойства.Будем рассматривать кодирование A* → {0, 1}*. Пусть известны некоторые частоты p1,p2, …, pk появления символов кодируемого алфавита в тексте:p1 − a1 → B1 − l1p2 − a2 → B2 − l2, lj — длина j-го кодового слова, p1 + p2 + … + pk = 1, pj > 0.((( (pk − ak → Bk − lkОпределение 1. Ценой (стоимостью, избыточностью) кодирования ϕ называетсяkфункция c(ϕ ) = ∑ pili . При кодировании текста длины N его длина становится примерноi =1равнойkk∑ (Np )li =1ii= N ∑ pi li .i =1Определение 2.

Взаимно однозначное кодирование ϕ называется оптимальным, если нанём достигаетсяinfс(ϕ ).ϕ −взаимно однозначноеУтверждение 4. Если существует оптимальный код, то существует оптимальный префиксный код с тем же спектром длин слов.Лемма 1. Если ϕ — оптимальное кодирование и pi > pj, то li ≤ lj.Доказательство. Допустим, что pi > pj и li > lj. Рассмотрим кодирование ϕ и рассмотрим ai → Biai → B j, ϕ′ : .кодирование ϕ', в котором переставим кодовые слова Bi и Bj: ϕ : a j → B ja j → Bi34Тогда c (ϕ) – c (ϕ') = (pili + pjlj) – (pilj + pjli) = (pi – pj)(li – lj) > 0 ⇒ c (ϕ') < c (ϕ) ⇒ ϕ не являетсяоптимальным — противоречие.Лемма доказана.Лемма 2.

Если ϕ — оптимальное префиксное кодирование и lmax = max li , длина(Bj) =1≤i ≤k= lmax, Bj = Bj'α, где α ∈ {0, 1}, то в коде ϕ существует слово Br такое, что Br = B′jα .Доказательство. Допустим, что в ϕ нет слова B′jα . Тогда заменим в ϕ Bj'α на Bj'. Получим код ϕ', который является префиксным, ноc(ϕ ) − c(ϕ ′) = p j дл(B′jα )− p j дл(B′j ) = p j ⇒ c(ϕ ′) < c(ϕ ) ,следовательно, ϕ не является оптимальным — противоречие. Лемма доказана.Лемма 3. Если ϕ — оптимальное префиксное кодирование и p1 ≥ p2 ≥ … ≥ pk–1 ≥ pk, томожно так переставить слова в коде ϕ, что получится оптимальное префиксное кодированиеϕ' такое, что слова Bk′ −1 и Bk′ в нём будут различаться только в последнем разряде.Доказательство. Пусть p1 ≥ p2 ≥ … ≥ pk–1 ≥ pk.

По лемме 2 в коде ϕ есть слова B′0 и B′1максимальной длины. Поменяем их местами с Bk–1 и Bk. Так как pk–1 ≤ pi и pk ≤ pi для1 ≤ i ≤ k – 2, то цена кодирования не увеличится и код останется оптимальным (префиксным).Лемма доказана.p1 , p2 ,!, pkp1 , p2 ,!, pk −1 , p′, p′′Лемма 4. Рассмотрим кодирования ϕ :и ϕ′ :,B1 , B2 ,!, BkB1 , B2 ,!, Bk −1 , Bk 0, Bk 1где p' + p'' = pk. Если один из этих наборов префиксный, то второй также префиксный иc(ϕ') = c(ϕ) + pk.Доказательство. Рассмотримc(ϕ') – c(ϕ) = p' · дл(Bk0) + p'' · дл(Bk1) – pk · дл(Bk) = p'(lk + 1) + p''(lk + 1) – pklk == (p' + p'')lk + (p' + p'') – pklk = pk.Лемма доказана.§32.

Теорема редукции.Теорема 4 (теорема редукции). Пусть заданы 2 набора частот и 2 набора слов:ϕ:p1 , p2 ,!, pkp , p ,!, pk −1 , p′, p′′и ϕ′ : 1 2.B1 , B2 ,!, BkB1 , B2 ,!, Bk −1 , Bk 0, Bk 11) Тогда если ϕ′ — оптимальное префиксное кодирование, то и ϕ — оптимальное префиксное кодирование.2) Если же ϕ — оптимальное префиксное кодирование и p1 ≥ p2 ≥ … ≥ pk–1 ≥ p′ ≥ p″, то ϕ′— также оптимальное префиксное кодирование.Доказательство.

1) Очевидно, из префиксности ϕ′ следует префиксность ϕ. Допустим,что ϕ не оптимально. Тогда существует префиксный код ϕ1: c(ϕ1) < c(ϕ) для тех же распредеp , p , ! , pk. Рассмотрим новое кодированиелений частот. Пусть ϕ1 : 1 2D1 , D2 ,!, Dkϕ1′ :p1 , p2 ,!, pk −1 , p′, p′′.D1 , D2 ,!, Dk −1 , Dk 0, Dk 1Очевидно, кодирование ϕ1′ также является префиксным и35 c(ϕ ′) = c(ϕ ) + pk⇒ {c(ϕ1 ) < c(ϕ )} ⇒ c(ϕ1′ ) = c(ϕ1 ) + pk < c(ϕ ) + pk = c(ϕ ′).c(ϕ1′ ) = c(ϕ1 ) + pkСледовательно, ϕ′ не является оптимальным кодированием, что противоречит условию. Остаётся предположить, что ϕ оптимально.2) Пусть ϕ — оптимальное префиксное кодирование и p1 ≥ p2 ≥ … ≥ pk–1 ≥ p′ ≥ p′′.

Допустим, что ϕ′ не оптимально. Тогда для частот p1, p2, …, pk–1, p′, p′′ существует оптимальноепрефиксное кодирование ϕ1′: D1, …, Dk–1, Dk0, Dk1 и c(ϕ1′) < c(ϕ). Тогда для частотp1, p2, …, pk рассмотрим кодирование ϕ1: D1, …, Dk–1, Dk. Получимc(ϕ1) = c(ϕ1′) – pk < c(ϕ′) – pk = c(ϕ) ⇒ c(ϕ1) < c(ϕ)и ϕ не оптимально, что противоречит условию. Теорема доказана.§33. Коды с исправлением r ошибок. Оценка функции Mr (n).Будем рассматривать равномерные коды, длины всех слов, равные n, и ошибки типа замещения, то есть вида 0 → 1 и 1 → 0.Определение 1. Код называется исправляющим r ошибок, если при наличии в любомкодовом слове не более r ошибок типа замещения можно восстановить исходное кодовоеслово.Определение 2.

Расстоянием Хэмминга (между 2 наборами длины n) называется числоразрядов, в которых эти наборы различаются.Определение 3. Шаром (сферой) радиуса r с центром в точке α~ = (α1 ,!,α n ) называется множество всех наборов длины n, расстояние от которых до α~ не превосходит r (в точности равно r).Определение 4. Кодовым расстоянием называется расстояние по Хэммингуρ =ρ (α~ ,α~ ) .minminα i ,α j из кода, α~i ≠α~ jijУтверждение 1.

Код K = {α~1 , α~2 ,!,α~m } исправляет r ошибок тогда и только тогда, когдаρ min (K ) ≥ 2r + 1 .Доказательство. Заметим, что условие утверждения эквивалентно тому, что расстояниемежду центрами шаров радиуса r (кодовыми словами) не меньше, чем 2r + 1, что эквивалентно тому, что эти шары не пересекаются. Таким образом, на выходе получится слово,принадлежащее единственному однозначно определённому шару (если в слове не более rошибок), что позволяет точно восстановить слово, так как известен центр этого шара. Утверждение доказано.Определение 5.

Код обнаруживает r ошибок, если при наличии в нём не более r ошибок типа замещения можно сказать, были ошибки, или их не было.Утверждение 2. Код K = {α~1 , α~2 ,!,α~m } обнаруживает r ошибок тогда и только тогда,когдаρ min (K) ≥ r + 1.Доказательство. Условие утверждения эквивалентно тому, что ни один из центров шаров (кодовое слово) не содержится в каком-либо другом шаре, то есть если произошло не более r ошибок, можно в точности установить, что полученное на выходе слово не совпадает сцентром одного из шаров. Утверждение доказано.Определение 6. Функция Mr (n) есть максимальное число слов длины n, образующих код,исправляющий r ошибок.

Sr (n) — число точек (наборов длины n) в шаре радиуса r.36n nnУтверждение 3. S r (n ) = 1 +   +   + ! +   .1  2rДоказательство. Точки шара радиуса r — это его центр, множество наборов, отличаюnщихся от центра в одной координате —   , множество наборов, отличающихся от центра в1n2 координатах —   , и т. д. Получаем утверждение. 22n.S 2 r (n )S r (n )Доказательство. Рассмотрим произвольный код K = {α~1 , α~2 ,!,α~m }, исправляющий rошибок.

Из утверждения 1 следует, что шары радиуса r не могут пересекаться, следовательно, число всех точек всех шаров не превосходит числа точек n-мерного куба иТеорема 5.2n≤ M r (n ) ≤2n2n⇒ M r (n ) ≤.S r (n )S r (n )m ⋅ S r (n ) ≤ 2 n ⇔ m ≤Теперь будем строить код K = {α~1 ,α~2 ,!}.

Выберем произвольно точку α~1 . Для выбораточки α~2 запрещено S2r(n) точек, так как запрещены все точки одного шара и все точки, расположенные от любой граничной точки на расстояние, не больше, чем r, то есть все точкишара радиуса 2r с центром в точке α~1 .