О.Б. Лупанов - Курс лекций по дискретной математике, страница 6

Обозначим эту величину через w.Утверждение 2.2. Максимальная длина самого короткого слова в алфавите A, порождающего (при указанной выше схеме кодирования) неприводимое слово над алфавитом B, не превосходит величиныN=(1 + l − r)(w + 1).2(3) Рассмотрим первое длинное (не содержащееся ни в каком другом) слово.

Все остальные длинные слованачинаются с отрезков второго рода. Обозначим число длинных слов через R, а число отрезков второго рода —через k. Получим R = 1+k. Общее число слов, лежащих внутри других, не превосходит Rw, а число не лежащихвнутри (то есть длинных) — в точности равно R. Значит, всего не более Rw + R = R(w + 1) = (1 + k)(w + 1) слов.Осталось оценить k. Заметим, что любой отрезок второго рода является началом некоторого длинного слова.Сколько может быть «начал»? Слово Bi длины li имеет li − 1 начало.

Если рассматриваемое декодируемое словонеприводимо, все отрезки второго рода должны быть различны, значит,k6rXi=1(li − 1) = l − r,(4)откуда получаем N 6 (1 + l − r)(w + 1). Здесь N = N1 + N2 — число слов в обоих декодированиях. Осталосьзаметить, чтоN1 + N2Nmin(N1 , N2 ) 6= ,(5)22и мы приходим к требуемой оценке. 192.1.4. Неравенство Мак-МилланаНапомним, что мы обозначаем через q количество букв в алфавите B.Утверждение 2.3 (Неравенство Мак-Миллана). Если кодирование допускает только однозначное декодирование, то11+ .

. . + lr 6 1.(6)q l1qОбозначим l := max li . Пусть Q(n, t) — число кодовых слов длины t, которые являются образами словiдлины n (вполне возможно, что какие-то Q(n, t) равны нулю). Рассмотрим11+ . . . + lrq l1qn=lnX(i1 ,...,in )q li1X Q(n, t)1!=.lqt· . . . · q int=1(7)Переход, отмеченный «!» следует в точности из того, что схема однозначно декодируется, и потому имеетсяинъективное соответствие(i1 , . . . , in ) 7→ ai1 .

. . ain 7→ Bi1 . . . Bin .(8)Всего имеется q t слов длины t, поэтому во всяком случае Q(n, t) 6 q t , следовательноn11+...+6 ln,q l1q lrоткуда√11n+ . . . + lr 6 ln.l1qq(9)(10)Переходя к пределу при n → ∞, получаем неравенство (6). Теорема 2.4. Для любой схемы кодирования B, имеющей однозначное декодирование, найдется префикснаяb имеющая тот же набор длин слов, что и схема B.схема B, Упорядочим по возрастанию длины li кодовых слов из B, то есть будем считать, что l1 6 . .

. 6 lr . Пустьнабор {λi } — это отсортированный по возрастанию набор {li }, из которого выкинуты дубликаты (и такимобразом, λ1 < . . . < λt ), а νi — количество дубликатов длины λi .В этих обозначениях (собирая одинаковые слагаемые) неравенство Мак-Миллана переписывается следующимобразом:ν1νr+ . . . + λr 6 1.(11)λ1qqБудем строить новую схему Bb последовательно. Для начала включим в неё ν1 различных слов длины λ1 .Это не противоречит её префиксности. В силу условия оптимальности, в ней должно быть ещё ν2 слов длиныλ2 . Чтобы префиксность не нарушилась, мы можем брать не любые слова длины λ2 , коих всего имеется q λ2штук, а только те, которые не начинаются с уже выбранных.

Таких имеется ν1 · q λ2 −λ1 штук, потому что каждоеиз первых ν1 кодовых слов можно расширить до слова длины λ2 именно q λ2 −λ1 способами. Таким образом,остаётся не более q λ2 − ν1 · q λ2 −λ1 кодовых слов. Но их хватит, потому что их нужно ν2 штук, то есть должнобыть выполнено неравенство ν2 6 q λ2 − ν1 · q λ2 −λ1 .

А его можно переписать по-другому:ν1ν2+ λ2 6 1.λ1qq(12)А это уже прямое следствие неравенства (11). Значит, нужное количество слов длины λ2 тоже найдётся. Далее,при выборе слов длины λ3 нам запрещено ν1 · q λ3 −λ1 + ν2 · q λ3 −λ2 слов, но, опять-таки в силу неравенства (11)мы их найдём, и так далее.b у которого набор длин кодовых слов тот же. В итоге мы получи префиксный код B,Следствие 2.1. При рассмотрении любой схемы кодирования всегда можно считать, что она префиксная.2.1.5. Оптимальные коды. Код ХаффманаКак и раньше, рассматриваем следующую схему кодирования: исходный алфавит A = {a1 , . . .

, ar }, конечныйалфавит B, состоящий из q символов, причем каждому символу ai ставится в соответствие слово Bi длины li .Теперь наша цель — построить в некотором смысле оптимальный код. Пусть мы кодируем некоторый текст(последовательность символов исходного алфавита). Ясно, что если какие-то символы очень часто встречаютсяв этом тексте, то будет хорошо, если кодовые слова, им соответствующие, будут иметь маленькую длину, инаоборот. Будем считать, что нам известны вероятности pi появления в тексте кодируемых символов ai .20Определение. Стоимостью схемы кодирования B назовём величинуL(B) :=rX(13)pi li .i=1Интуитивно ясно, что чем меньше «стоит» схема, тем она эффективнее.Обозначим l := min li .

Из неравенства Мак-Миллана следует, что q l > r.iРассмотрим равномерную схему кодирования, в которой все кодовые слова имеют одинаковую длину (то естьфактически просто занумеруем буквы исходного алфавита в q-ичной системе счисления). Ясно, что нам хватитдлины l = logq r . Такой код обозначим B0 . Этот код однозначно раскодируется, и, очевидно, L(B0 ) = l.Теорема 2.5 (О существовании оптимального кода). Пусть p := min pi . Если в коде B имеется словоBj длины lj > pl , то L(B) > L(B0 ).

В самом деле,XlL(B) =pi li > pj lj > pj > l = L(B0 ).(14)pТаким образом, не имеет смысла рассматривать коды с длинами слов больше p1 , так как равномерный кодбудет в этом случае оптимальнее. Но таких кодов (для данного алфавита) конечное число, а потому среди нихсуществует минимум. Определение. Оптимальный код — код с наименьшей стоимостью среди однозначно декодируемых.Как уже отмечалось в следствии 2.1, оптимальный код можно считать префиксным.Лемма 2.6. Если B — оптимальный код, то в нём li 6 lj при pi > pj . Докажем от противного.

Пусть в коде B нашлись i и j, для которых имеем pi > pj , но li > lj . Построимкод B ′ путём перестановки в коде B слов Bi и Bj , получим код с меньшей стоимостью. Противоречие. Далее будем считать, что q = 2. Иначе говоря, будем рассматривать только двоичные коды, и выходнойалфавит будет состоять из двух символов: B = {0, 1}.Лемма 2.7.

В оптимальном коде самое длинное слово не может быть единственным. Допустим, что существует единственное максимальное слово. Уберём из него последний символ. Кодпрефиксный, следовательно полученный код также будет однозначным и при этом более эффективным, чемисходный. Противоречие. Лемма 2.8. В оптимальном коде среди слов максимальной длины найдутся два, различающиеся только впоследнем (самом правом) разряде. Предположим, что все самые длинные слова различаются не только в последнем разряде. Это означает,что путём вычеркивания из самых длинных слов этого последнего разряда мы получим однозначный код,который будет эффективнее предыдущего.

Рассмотрим оптимальный код B и упорядочим вероятности pi : p1 > . . . > pr . В силу леммы 2.6 имеемl1 6 . . . 6 lr .b с наборомПусть pi = q ′ + q ′′ , причем pr > q ′ , pr > q ′′ , и для определённости, q ′ > q ′′ . Для алфавита Aвероятностей p1 > . . . > pbk > . . . > pr > q ′ > q ′′ построим кодck , . . . , Br , Bk 0, Bk 1 .Bb := B1 , .

. . , B(15)Здесь крышки в последовательности обозначают пропуск элемента, а черта сверху показывает, что слово полученное склейкой нескольких слов.Теорема 2.9. Bb является оптимальным кодом для заданного набора вероятностей. Будем доказывать от противного. Прежде всего заметим, чтоXXXb =pi li + pk = L(B) + pk .(16)L(B)pi li + q ′ (lk + 1) + q ′′ (lk + 1) =pi li + (q ′ + q ′′ )lk + (q ′ + q ′′ ) =i6=kii6=kb < L(B).b Выделим в нёмПусть Cb — оптимальный код, отличный от Bb и более эффективный, то есть L(C)два самых длинных слова, различающихся только в последнем разряде (такие найдутся в силу леммы 2.8) иобозначим их C ′ и C ′′ .

Можно считать, что C ′ = C0, C ′′ = C1. Восстановим по нему кодC := {C1 , . . . , Ck−1 , C, Ck+1 , . . . , Cr }b = L(C) + pk . Тогдадля исходного набора вероятностей. Тогда, очевидно, L(C)b < L(B)b = L(B) + pk ,L(C) + pk = L(C)21(17)(18)откуда получаем, что L(C) < L(B), что неверно, поскольку код B был оптимальным. Теперь ясно, как выглядит процесс построения оптимального кода. Упорядочиваем символы по вероятностиих появления в тексте (по убыванию). Далее берём два самых редких, складываем их вероятности, и полученнуюсумму вставляем в упорядоченный набор вероятностей без двух последних элементов.

Затем эту процедуруповторяем, пока не придём к двум вероятностям. Им соответствуют коды 0 и 1. А теперь идём назад: находимте две вероятности на предыдущем шаге, которые дали в сумме одну из вероятностей pi , им присваиваем кодыK0 и {K1} (добавляем 0 и 1 к уже имеющемуся коду K вероятности pi ). И так далее: находим на предыдущемшаге две вероятности, давшие в сумме одну из имеющихся на данном шаге вероятностей, и приписываем к ихкодам нуль и единицу. Остальные коды переносим в предыдущий шаг без изменений.Набор кодовых слов для исходного набора вероятностей (то есть то, что получится после возвращения кпервому шагу) и есть код Хаффмана.2.2.

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