Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 47
Текст из файла (страница 47)
Лля кода С найти слово минимальной длины, декодируемое неоднозначно; Ц С = (10, 01, 12, 012, 2100, 12011, 12010); 2) С = (О, Ю1ОЮ, О1О1О1ОЦ; 3) С = (О, (10)ь ', 1ОЦь); 4) С = (010, .101, 01010, (ОЦ~), .й = Зв+ 1; 5) С = (О., (10)в, (ОЦео); 6) С (001 011 100 110 (1100)Я) й Зв 7) С (О 10 11 (10Ць), 8) С (01 10 11 (110)Й) й 2в. 9) С = (0~, 0 ):, 10) С = ((ОЦьо, 0110)ьо', 1(ОЦ 1Ц С = (О, О"1, 1(0)"'); 12) С = ((ОЦь, (10)"', (ОЦ'0); 13) С = ((ОЦь, (ОЦь"'О, 110)ьоз1, (10)ь1); 14) С (О Оь1(0)™ <1(0) )зц.
15) С (<ОЦЯ (10)в+и (ОЦЯО и) с = ((оц', (оц"- 'о, (ю)"+'). 234 Гл. И1. Элементы теории ив4ироввниа 1.6. Построить двоичный префиксный код С с заданной последо- вательностью Л длин кодовых слов: 1) Ь = (1, 2, 3, 3); 2) Ь = (1, 2, 4, 4, 4, 4); 3) Г, = (2, 2, 3, 3, 4, 4, 4, 4); 4) А = (2, 2, 2, 4, 4, 4); 5) Ь = (2, 2, 3, 4, 4); 6) Ь = (2, 3, 3, 3, 4, 4). 1.7.
С помощью неравенства Макмиллана выяснить, может ли набор чисел Ь быть набором длин кодовых слов однозначно декоди- руемого кода в д-значном алфавите; 1) Ь = (1, 2, 2, 3), д = 2; 2) Ь = (1, 2, 2, 3), д = 3, 3) Ь = (2, 2, 2, 4, 4, 4), д = 2; 4) Ь = (1,. 2, 2, 2, 3, 3, 3, 3), д = 3; 5) Ь = (1, 1, 2, 2, 3, 3, 3), д = 3; б) Ь = (1, 1, 1, 2, 2, 2, 2, 3), д = 4.
1.8. Пусть в алфавитом двоичном коде С таком, что ~С~ > 2"', каждое слово имеет длину, не превышающую п. 1) Может ли код С быть однозначно декодируемым? 2) Может ли код С быть префиксным? 1.9. Пусть С(Е) алфавитный код со схемой Е, ~С(Е)~ = г, сум- ма длин кодовых слов равна Х, а максимальная из длин кодовых слов равна й Доказать, что код С(Х) является однозначно декодируемым, если однозначно декодируются все коды сообщений, имеющие длину, не превышающую (1 — 1)(Х вЂ” г+ 1) + 1. 1.10. Пусть й . наименьшая, а 1 . наибольшая из длин кодовых слов алфавитного кода С(Е) и Х вЂ” сумма длин кодовых слов.
Пока- зать, что для установления однозначной декодируемости кода С(Е) достаточно исследовать на однозначную декодируемость все коды сообщений, имеющих длину не больше 4д1/й в алфавите сообщений. 1.11. Пусть М вЂ” множество, состоящее из г непустых слов в алфавите, имеющем д букв. Показать, что: 1) в М найдется слово длины нс меньше 1оя (д+ г(д — 1)) — 1; 2) для всякого е > 0 доля тех слов из М, длина которых не пре- восходит (1 — е) 1оя (1+ г(д — 1)), не больше (,) 4з~ -) (г(д — 1)) ' при г>2, д>2. 1.12. Доказать, что префиксный код С(Е) с д-буквенным кодирующим алфавитом тогда и только тогда является полным, когда выполнено равенство ~~ д '* = 1, где 1ы 1з, ..., 1„длины кодовых е=1 слов из С(Е).
1.13. Пусть |ы 1з, ..., 1„целые неотрицательные числа такие, что ~~ 2Ь ( 2". Доказать, что в кубе В" существуют попарно венею=.1 ресекающиеся грани ды дз, ..., де, размерности которых равны соот- 235 у Я. Коды с минимальной избьввочностью ветственно 1к, 1г, ..., 1„. Напомним,что И-мерной гранью куба В" называется всякое множество д, для которого сушествуют подмножество (1к, 1г, ...,. 1„я) множества (1, 2, ..., п) и набор ою ггг, ..., а, ь такие, что д = ((ак, оз, ..., о ) б В" ! гк,к. = о, з = 1, ..., п — й). 1.14. Пусть код С(к.) состоит из двух непустых слов и не является однозначно декодируемым. Доказать, что наименьшая длина декодируемого слова не превышает 21 — 1, где 1 наибольшая из длин кодовых слов.
Привести пример кода., для которого эта верхняя оценка достижима. 1.15. Пусть Х(С) . - наименьшая длина неоднозначно декодируемого слова в кодирующсм алфавите кода С. Положим Х(йг, г) = = шах Х(С), где максимум берется по всем неоднозначно декодируемым кодам С с г кодовыми словами и суммой длин кодовых слов, равной Я. Доказать, что: 1) сушествует положительная константа ск такая, что Х(йг, 3) ( ( сккк' 2) для всякого Ь существуют такие число йг > Ь и код С = (Вы Вг, Вз), что ~1(В,) = Х и Х(С) > сгйгз, где сг --. константа, ~=1 не зависящая от й. 3 2. Коды с минимальной избыточностью Пусть заданы алфавиты А = (ад, аз, ...; а ), В = (Ьм Ьг, . Ьч) и набор вероятностей Р = (рк, рг, ..., р ), Р' > 0; ~ Р' = 1 Пусть г=к С = (юк, игг, ..., юс) алфавитный префиксный код в алфавите В такой, что слово ю, Е С является кодом буквы а; Е А, и 1г -- длина слова ю; (1 = 1, ..., г).
Число 1,р(С, Р) = ~1;рг называется избыь=к точностью кода С или средней длиной кодового слова в коде С. Положим г*(Р) = ш(о Уьв(С, Р). Код С* такой, что 1, (С, Р) = Г(Р), называется д-ичнгям кодом с миниаальной избыточностью для набора верояптостей Р (или оптимальным (Р, д)-кодом). Метод Хаффмена для построения оптимальных (Р, 2)-кодов опирается на следукьщие утверждения. 1. Среди кодовых слов максимальной длины 1 оптимального (Р, 2)- кода найдутся два слова, имеющие один и тот же префикс длины 1 — 1. 2. Если слова юв го оптимального (Р, д)-кода соответствуют вероятностям р„р и р, > р, то длины 1(ю,) и г(игк) этих слов связаны неравенством 1(ю,) ( 1(ю ).
236 Гл. И1. Элементы теории кодирования 3. Теорема редукции. Пусть С = (юы юз, ..., юь) двоичныйкод,Р=(рырз, рс) рь3рз3...)рс,р;)О, ~ р,=1— распределешье вероятносгпей. Пус|аь ю,, и~ (слова, имеющие максимальную длину 1 и соотвепютвуюизие верояганосшям р„р ) обладают одинаковыми префиксами ю длины 1 — 1. Полозкам р' = р, + р и рассмоьприм распределение вероятностей Р' = (ры ..., рь — ы р', рь ы, р, „р,, ы ..., р „р +ы..., р„), в котором вероятности распологкены в порядке невоэрастания.
Код С' = (С С (юЯ(ю, и, ) является (Р', 2)-оптимальным тогда и люлько тогда, когда код С является (Р, 2)-оптимальным. Процедура Хоффмана для построения оптимального (Р, 2)-кода заключается в следующем. Пусть вероятности в распределении Р = = 1ры рз, ..., р„) расположены в порядке невозрастания. Исключим из Р вероятности р, з и р„, а их сумму р вставим в оставшийся набор таким образом, чтобы в получившемся новом наборе вероятности не возрастали. Эта процедура повторяется до тех пор, пока не получится набор из двух вероятностей. Зля такого набора вероятностей оптимальным является код, в котором каждой букве из алфавита сообщений А ставится в соответствие 0 или 1. Исходя из полученного на некотором шаге оптимального кода С' в соответствии с теоремой редукции можно перейти к расширенному оптимальному коду С, имеющему мощность, на единицу болыпую, чем код С'.
Продолжая этот процесс, придем к искомому оптимальному (Р, 2)-коду с г сообщениями. Пример 1. Пусть А = (1, 2, ..., 6), В = (О, 1) Р = (0,4; 0,3; 0,1; 0,1; 0,05; 0,06), г = 6. Схема построения оптимального (Р, 2)-кода выглядит следующим образом: Всякому префиксному коду С в о-ичном алфавите В с заданным набором вероятностей Р можно сопоставить помеченное дерево П(С, Р, у), называемое в дальнейшем деревом кода С, следующим образом. Сопоставим каждому кодовому слову висячую вершину, каждому собственному префиксу внутреннюю вершину, причем одинаковым префиксам разных кодовых слов сопоставим одну и ту 7 Я.
Коды с минимальной иэбытоиносшью 237 жо внутреннюю вершину. Пустому префиксу сопоставим вершину, называемую корнем дерева. Соединим две вершины, соответствующие префиксам о и иб ребром с пометкой Ь, если о = шЬ или о~ = оЬ, где Ь - буква алфавита В. Висячим вершинам припишем вероятности, с которыми встречаются соответствующие кодовые слова. Дерево Р(С, Р, д) устроено так, что последовательность пометок, приписанных ребрам цепи, соединяющей корень дерева с висячей вершиной, представляет собой соответствующее кодовое слово.
Непомеченное корневое дерево, полученное из Р(С, Р, д) путом отбрасывания пометок, будем называть осшовом дсрева Р(С, Р, 9). Пример 2. Пусть задан префиксный код С = (Ь, с, оа, аЬ, аса, асЬ, асс) и набор вероятностей, соответствующих кодовым словам, /1 1 1 1 1 1 11 есть Р = ( —, —, —, —, —, —, — ). Лере- (3' 9' 3' 27' 27' 27' 9) во .Р(С, Р, д) показано на рис. 7.2. Дерево Р(С, Р, д), соответствующее оп- 1 1 тимальному (Р, д)-коду С, будет назы- ' 3 ' 27 ваться оптимальным. Порядком ветвления Ь— 9 вершины и в дереве Р называется число ребер, инцидентных вершине о и не лежагцих Л на цепи, соединяющей вершину о с корнем.
Будем говорить, что вершина принадлежит Рис. 7.2 й-му ярусу дерева, если цепь, соединяющая эту вершину с корнем, содержит й ребер. Будем говорить, что ребро принадлажит Ь-му ярусу, если оно соединяет вершины й-го и (й + 1)-го ярусов. Дерево Р называется (г, г1)-насышенным, если порядки ветвления всех его вершин., за исключением, может быть, одной вершины, лежащей в последнем ярусе, равны 0 или 95 а поряцок ветвления этой исключительной вершины равен дв, где 1 1 асЬ,— 27 1 асс,— 9 у — 1, если — целое число, о — 1 з' г — ~ — ~ (д — 1) в остальных случаях. 1, 1~ Построение (Р., 9)-оптимальных кодов С, обладающих (г, 9)-насыщенными деревьями, производится аналогично построению (Р, 2)- оптимальных кодов.
Пример 3. Построить (Р, 3)-оптимальный код для Р = (0,4; О,З; 0.1; 0.,1; 0,05: 0,05) Решение. Поскольку з = 6, д = 3 и г)о — 1 целое число, то до = 9 — 1 = 2. Число 99 дает количество «склеиваемых» на первом шаге вероятностей. Построение кода проведем в два этапа, как и в примере 1. Сначала редуцируем распределение Р, а затем, построив оптимальный код для трех сообщений, расширим его до г = 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
