А.А. Вороненко - Решение избранных задач по курсу дискретной математики, страница 5

Для нахождения веса функции хватит пяти ярусов. Изучив дерево, видим, что вес функции равен 3. О: 0,3,4,5,6,... 1: 1,7,9,11, 2: 2,3,10,12,... ?88У448 444%44 4848648 4888842 Я84%% УЗ%88 8188 О(О), 2(2) Ю, 2(1) ~((01) ) =О' н Д«(10) ) = (ООЦ У((01) ) = О. й«,0) ) =1 Затем по канонической таблице восстанавливаем канонические уравнения. р(») = а(») с» о1(» — 1) Н т(») (г о1(» — «) ег 12(» — 1) 1«1(») = ч1(» 1) ~(»Я2(» 1) 1» 2'(») ~»»»1(» 1) ЙЯ2(» 1) Я2(») И(») М: Ч1(» — 1) ~(~ Я2(» 1) ~» Й(» — 1) ес 1«2(» — 1) ((,(о) = о2(о) = о в 1«».2.5(1).

Для частично определенной д. функции у(~~): (О, Ц -+ (О, Ц, отоброжающей заданные последовательности в заданные, построить диаграмму Мура с возможно меньшим числом вершин; затем полученную диаграмму доопределить до диаграммы Мура всюду определенной о,-д. функции из Р2'„д, и для этой новой функции построить 1,1 каноническую таблицу н ка11опическне уравнения: У((У') =(01)" н 1((1,0) ) =1 л Используя описанные в условии формулы, восстановим диаграммы Мура У(0') = (01)' Объединяем диаграммы и доопределяем функции р(»), о1(») и о2(»); зз По диаграмме Мура мы восстанавливаем каноническую таблипу.

Затем, по канонической таблице восстанавливаем канонические урав- ПШ1ИЯ, ГЧ.2.5(2). Для частично определенной д. функции у(х ): 10, Ц -+ (О, Ц, отображающей заданные последовательности в заданные, построить диаграмму Мура с возможно меньшим числом вершин; затем полученную диаграмму доопределить до диаграмму Мура всюду определенной о,-Д. фУнкЦии из Р2'од, и Лла этой новой фУнкЦии постРоить 1Л каноническую таблицу и канонические уравнения: ~ Используя описанные в условии формулы, восстановим диаграммы Мура. ~(1(10) ) = (001] ' «ь ~(1[101010)") = 0(010010) 39 ~(0 Занятие № 13 АЛФАВИТНОЕ КОДИРОВАНИЕ. ОПТИМАЛЬНЫЕ КОДЫ УП.1.3(1).

Выяснить, является ли слою Р = 10120121012100 в алфавите (0,1„2) кодом сообщения в кодировании, задаваемом схемой 1- 10 2 -+ 12 3 -» 012 4 » 101 5 -+ 2100 Если да, то выяснить, является ли Р кодом ровно одного сообщения. «$ Слово Р является кодом единственного сообщения, поскольку — единственное кодовое слово, оканчивая»щееся двумя нулями — 2100, значит Р = 1012012101~10~ — единственное кодовое слово, оканчивающееся единицей -- 101, следовательно, Р = 1012012 101 ~100 — предположим, первое кодовое слово — 101. В этом случае оставшаяся часть слова не декодируется; Р = 101 2012 101 ~10Я. Следовательно, первое кодовое слово — 10, далее -- 12 и 012: Р = 10 12 012 101 ~100 Итак, Р является кодом единственного сообщения: 12345. в' ЪЧ1.1.2(1,3).

Выяснить, является ли код С с кодирующим алфавитом (О, 1, 2) однозначно декоднруеыым; 1) С = (01,201,112,122,0112) 3) С = (О» 01, 0010001001) ° и 1) Пусть кодирование задается некоторой схемой Е. Построим граф Существует контур, проходящий через вершину Л. При обходе контура получим слово, декодируемое неоднозначно: 0112 201 01 122 01 3) Буква 0 01 0 О 01 О 01 декоднруется неоднозначно.

~ ~«'»» ««'»~«»"» "~»»»»»"»" «»»» «г~ Значит, весь код пе является однозначно декодируемым. в" УП.1.6(1,3). Построить двоичный префиксный код С с заданной последовательностью Ь длин кодовых слов: 1) 1 = (1»2,3,3); 3) 1 = (2»2,3,3,4,4,4,4). а Построим двоичные префиксные коды в алфавите (а, Ь) 1) Пусть слово длины 1 — а.

Тогда а не должно быть префиксом нннкакого другого слова. Пусть слово длины 2 — Ьа; Ьа в этом случае также не может быть префиксом никакого другого слова. Далее рассуждаем аналогично. В результате код может быть, например, таким: С = (а, Ьа, ЬЬа, ЬЬЬ), Возможны и другие варианты, например: С = (а, ЬЬ, Ьаа, ЬаЬ1 3) Рассуждаем точно так же, как и в (1). Результат может быть таким: С = (аа, ЬЬ, аЬа, аЬЬ, Ьааа, ЬааЬ, ЬаЬа, ЬаЬЬ).

УП.1.7(1»4). С помощью неравенства Макмиллана выяснить, может ли набор чисел Ь быть набором длин кодовых слов однозначно декодируемого кода в ()-значном алфавите: 1) Х = (1, 2,2,3), о = 2; 4) 1 = (1,2,2,2,3»3,3,3). о = 3. ° Неравенство Макмиллана выглядит так: 1 <1 Я где д — количество букв в кодирующем алфавите, (м 4,..., 1,.

— длины кодовых слов однозначно декодируемого кода. Подставляя в эту формуву числа, получаем; 1) 1~ + «1 + 4 + ~1 = -" > 1, значит, набор чисел Ь = (1, 2, 2, 3) не может быть набором длин кодовых слов однозначно декодпруемого кода в 2-значном алфавите; 4) -'+ 3 ф+ 4 З~ = Я < 1, значит, набор чисел 1 = (1, 2, 2, 2, 3, 3, 3, 3) может быть набором длин кодовых слов однозначно декодируемого кода в 3 — значном алфавите, ЪЧ1.1.5(1,2). Для кода С найти слово мянимальной длины, декоди- руемое неоднозначно: Ц С = (10,01,12,012,2100,12ОП,12010); 2) С = (О, 101010,01010101).

° и 1) Пусть кодирование задается схемой Е. Построим граф Сш 1 то этот отрезок слова декодируется однозначно (сначала выделяем последовательность с 3 единицами: 10101, затем идут по крайней мере 2 нуля и последовательность с 4 единицами; 1010101). Аналогично, если кодовые слова 101010 и 01010101 находятся в конце слова, то этот отрезок также декодируется однозначно. Следовательно, слово, содержащее 7 = 3+ 4 = 4+ 3 единиц, декодируется однозначно. Слово, содержащее 10 = 3+ 3+ 4 (1а) = 3+ 4+ 3 (15) 4+3+3 (1с) илн 11 = 4+3+4 (2а) = 3+4+4 (25) = 4+4+3 (2с) единиц также декодируется однозначно (в двух случаях в начале (1а,2а), или в конце (15, 25) слова есть последовательность 40101Д 0101010:~, декодируемая, как мы только что 3 единицы4 единицы выяснилн, однозначно; случаи 1с и 2с выделяются методом исключения).

— Длина минимального неприводнмого слова равна 12: О 101010101010101010 010101010101010101010101 О 12 Выписывая слова, приписанные вершинам и дугам самого короткого контура, проходящего через вершину Л, получим слово минимальной длины, декодируемое неоднозначно: 420$ 012 12010 12 2) Имеют место следующие факты: — Если слово содержит 3 или 4 единицы, то оно декоднруется однозначно. — Если в начале слова находятся кодовые слова 101010 и 01010101 и, быть может, последовательность нулей (О... 0~0101ЯО... 00101010$0...

0), 46 УП.2.1(4,6). С помощью процедуры Хаффмена построить двоичный код с минимальной избыточностью для набора вероятностей Р: 4) Р= (0.5,0,2,0,1,0,09,0.08,0.03)," 6) Р = (03,03,02,004,003,003,003,003,003,001), 4) Р = (0.5, 0.2, 0.1,0.09,0,08, О.ОЗ); Построим дерево кода С. 1.0 0.5 0.2 0.1 0.09 О.й О.ОЗ Спускаясь от корня к вершинам, получим кодовые слова, соответствующие указанным вероятностям: С = (0,10,1100„1101,1110,1111). ) Я если Ча Е С р(а, р) > г ( а если р(а,,о) <1 б) Р = (О 3,0.3,0,2,0 04,0,03,0 03„0,03,0.03,0 03,0.01) .

Построим дерево кода С. 0.3 0.3 0,2 0.04 0.03 0.03 0.03 0,03 0.03 0.01 Опускаясь от корня к вершинам, получим кодовые слова, соответствующие указанным вероятностям: С = (00,01,10,1110,11000,11001,11010,11011,11110,1111Ц. УП,2.10(4,3,10). Выяснить, существует лн двоичный код с минимальной избыточностью, обладающий заданной последовательностью Ь ДЛИН КОДОВЫХ СЛОВ: 4) Ь= (1,2,3,4); 5) Ь = (1,2,3,4,4); 10) 1 = (3,3,3,3,3,3). ° двоичный код с минимальной избыточностью существует в том и только в том случае, когда выполнено равенство 1 ,"> — = 1. 2'* 1=1 4) Нет, так как 2+ 4 + е+ 1е — 1 — Б < 1.

10) Нет, так как б 1 < 8 е = 1. ° » Занятие № 14 Коды, испРАВляющие ошиВки ж.з.л, 1) Показать„что код исправляет г ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше 21+ 1. 2) Показать, что код обнаруживает г ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше с+1. 1) Код С исправляет 1 ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше 2г+ 1. Необходимость.

Если код С исправляет 1 ошибок, то для любых двух различных кодовых слов а и,8 шары с центрами в этих кодовых словах и радиусами 1 не пересекаются: Следовательно, р(а, р) 3, 2г+ 1 и д(С) > 2$+ 1. Достаточность. Рассмотрим отображение ф; 8" — С; Понятно, что шары радиуса г с центрами в двух различных кодовых словах не пересекаются, следовательно, если слово а существует, то опо единственно (то есть отображение ф является декодированием). 2) Код обнаруживает 1 ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше 1+ 1. НсоблкЪмость следует из того, что код С обнаруживает $ ошибок, если СПЯ~" (а) = Я) Уа Е С.

ДОСГПатОЧИОСтпь. Ч амат Е С =ь ~а1 — аз~ > Г+ 1 =ь одно кодовое слово не может быть получено из другого в результате не более чем $ ошибок. Ф» 'Л1.3.20(1,2). Булева функция 1'(хх) назьвается хараксиеристиичесхой для подмножества С С В", если С =: Дсу. Определить, сколько ошибок обнаруживает и сколько исправляет код с характеристической функцией 1: 1) с(х") = хс бс х2 сс ... 9 х... 2) у(х ) =хсйу2й...ссхчЧхсйх2й...сии.