Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 47
Текст из файла (страница 47)
Справедливы слодующио утверждения. Теорема 1 (Ал.А. Марков). Алфавитный код С(Х) является однозначно декодируемым тогда и только тогдц когда в графе Сг. отсутствуют кон(ауры и петли, проходяи(ие через вершину Л. Теорема 2 (неравенство Макмиллана). л(ля всякого однозначно декодируемого кода в а-буквенном коднрующем алфави(ле с набором длин кодовых слов 1(, 1з, ..., 1„выполнено неравенство ь ~1 <1. ,=1 Теорема 3. Для всякого однозначно декодаруемого кода С(Х) в кодируюи(ем алфавите З с набором длин кодовых слов !(, 1з....., 1„ можно построить префиксный код С(Х') с тем же набором длин кодовых слов и в том же кодирующем алфавите.
Следствие. Пусть 1(, 1з, ..., 1, натуральные числа п(акие, лпо ~~(( * < 1. Тогда существует префиксный код в ((-буквенном кок — л 1=1 дирующем алфавите с набором длин кодовых слов вида (1(,1з, ..., 1,). Пример !. Выяснить, является ли кодирование Рв взаимно однозначным, если С(Х) = (а, аЬ, саЬ, Ьаас). Если да, то указать слово, декодируемое двумя способами. 232 Гл.
И1. Элементы теории кодирования а Ьс е Ь л'~ Л аЬ Ь еа аЬ в Рне. 7.1 Решение. Граф Сх показан на рис. 7.1, а. Существует контур, проходящий через вершину Л. Выписывая слова, приписанные вершинам и дугам контура, получаем слово, декодируемое неоднозначно: г1 г — 1 г — 1 а баас аЬ = аЬ а а саЬ. е лел еле Пример 2.
Та же задача для кода С(Е) = (а, Ь, аглЬ). Решение. Граф Св показан на рис. 7.1, б. Граф содержит петлю )Л, Л). Код не является однозначно декодируемым. Слово, декодируемое неоднозначно, есть: ааЬ = а а Ь. ел гл ел Пример 3. Та же задача для кода С(Е) = (саЬ, аЬс, Ьсс, аЬса, аЬсЬ). Решение.
Граф Св показан на рис. 7.1, в. Контуров и петель, проходящих через Л, нет. Код является однозначно декодируемым. 1.1. Выяснить, обладает ли код С свойством префикса: 1) С = (а, Ьа, ЬЬ, ЬЬЬа); 2) С = (аЬ, ЬЬ, Ьа, ааЬ); 3) С = (ас, с, ЬЬ, аЬс, Ьас, аЬЬ, аЬсЬ); 4) С = (а, Ьа, саЬ, асЬ); 5) С = (а, Ьа, ЬЬа, ..., (Ь)на, ...); 6) С = (а„Ьае ..., с(а)".....). 1.2. Выяснить, является ли код С с кодирующим алфавитом (О, 1, 2) однозначно декодирусмым: Ц С = (01, 201, 112, 122, 0112); 2) С' = (001,. 021, 102, 201, 001121, 0101210Ц; 3) С = (О, 01, 0010001001); 4) С = (20, 0Р202, 22, 2001, 2012010, 1020ПЛ, П12); 5) С = 01,. 011, 100, 2100, 101210, 001210); 6) С = (01, 011, 100, 2100, 10110, 00112); 7) С = (01г 12, 021, 0102, 10112); 8) С = (01, 12, 012, 111, 0102, 10112, 01112); 9) С = (01, 12, 012, 0102, 020112); 10) С = (01, 1О, 210, 121, 0210, 0112); 11) С = (01, 10, 210, 201, 0210, 011022, 2221); 12) С = (01г 10, 210, 201, 0210, 011022, 221); 13) С = (01, 10, 210, 201, 0210, 011022); у' 1.
Аафавипи~ое кодирование 233 14) С = (01, 12, 011, 01210, 20120, 2011220); 15) С = (01, 12, 011, 01210, 201120, 2011220); 16) С = (000, 0100, 10, 1001, 0010010); 17) С = (01, 12, 01121, 21201). 1.3. Выяснить, является ли слово Р в алфавите (О, 1, 2) кодом сообщения в кодировании, задаваемом схемой 1 — > 10 2 — > 12 Е: 3 -+ 012 4 †> 101 5 о 2100 Если да,то выяснить, является ли Р кодом ровно одного сообщения: Ц Р = 10120121012100; 2) Р = 1012101201210012; 3) Р = 0121001210201; 4) Р = 120120121001210: 5) Р = 1010122100; 6) Р = 12101210012; 7) Р = 101212101012; 8) Р = 1010012100101. 1А.
Выбрать максимальное по числу элементов подмножество В множества А с условием, что двоичные разложения наименьшей длины чисел из В представляют собой а) префиксный код; б) однозначно декодируемый код: Ц А = (1, 5, 6, 7, 12, 13, 17): 2) А = (1, 3, 6,8,10,13,19,33,37); 3) А = (2, 6, 7, 9, 12, 15, 18, 35, 36, 37); 4) А = (1, 2, 5, 8, 9, 10, 13, 15); 5) А = (2, 3, 7, 8, 11, 12, 13, 14): 6) А = (3, 5, 6, 9, 10, 13, 17), :7) А = (1, 2, 5, 8, 9, 12, 13, 14); 8) А = (5, 6, 7, 8, 9, 10, 11, 12, 13); 9) А = (4, 6,. 7, 10, 13., 15, 20, 23, 25); 10) А = (5, 7, 9, 10, 12, 14, 17, 23, 24).
1.5. Лля кода С найти слово минимальной длины, декодируемое неоднозначно; Ц С = (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)-кодов опирается на следукьщие утверждения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
