А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями, страница 5

Выяснить, является ли код C с кодирующим алфавитом {0, 1, 2} однозначно декодируемым:1) C = {01, 201, 112, 122, 0112};3) C = {0, 01, 0010001001}.J1) Пусть кодирование задается схемой Σ. Начнём строить графGΣ :120101ΛΛ12Существует контур, проходящий через вершину Λ. При обходеконтура получим слово, декодируемое неоднозначно:z}|{ z }| { z}|{0 1.}|0 1{z1 2} |2 {z33z}|{3) Слово |{z}0 |{z}01 |{z}0 |{z}0 |{z}01 |{z}0 |{z}01 декодируется неоднозначно.Значит, весь код не является однозначно декодируемым.IVII.1.6(1, 3). Построить двоичный префиксный код C с заданнойпоследовательностью L длин кодовых слов:1) L = (1, 2, 3, 3) ;3) L = (2, 2, 3, 3, 4, 4, 4, 4) .J Построим двоичные префиксные коды в алфавите {a, b}.1) Пусть слово длины 1 — a.

Тогда a не должно быть префиксом никакого другого слова. Пусть слово длины 2 — ba; ba в этом случаетакже не может быть префиксом никакого другого слова. Далеерассуждаем аналогично. В результате код может быть, например,таким:C = {a, ba, bba, bbb}.Возможны и другие варианты, например:C = {a, bb, baa, bab}.3) Рассуждаем точно так же, как в предыдущем пункте. Результатможет быть таким:C = {aa, bb, aba, abb, baaa, baab, baba, babb}. IVII.1.7(1, 4). С помощью неравенства Макмиллана выяснить, можетли набор чисел L быть набором длин кодовых слов однозначно декодируемого кода в q−значном алфавите:1) L = (1, 2, 2, 3), q = 2;4) L = (1, 2, 2, 2, 3, 3, 3, 3), q = 3.J Неравенство Макмиллана выглядит так:rX16 1,liqi=1где q — количество букв в кодирующем алфавите, l1 , l2 , .

. . , lr — длиныкодовых слов однозначно декодируемого кода.Подставляя в эту формулу числа, получаем:1) 21 + 41 + 14 + 18 = 98 > 1, значит, набор чисел L = (1, 2, 2, 3) не можетбыть набором длин кодовых слов однозначно декодируемого кодав 2−значном алфавите;4) 31 +3· 312 +4· 313 = 2227 < 1, значит, набор чисел L = (1, 2, 2, 2, 3, 3, 3, 3)может быть набором длин кодовых слов однозначно декодируемого кода в 3−значном алфавите.I34VII.1.5(1, 2). Для кода C найти слово минимальной длины, декодируемое неоднозначно:1) C = {10, 01, 12, 012, 2100, 12011, 12010};2) C = {0, 101010, 01010101}.J1) Пусть кодирование задается схемой Σ. Построим граф GΣ :Выпишем слова, приписанные вершинам и дугам различных контуров, проходящих через вершину Λ: 12011012, 01210012, 1201012.Из них минимальную длину имеет словоz}|{ z}|{120101 2.}|{z} | {z } | {z2) Наименьшее общее кратное 6 и 8 — 24.

Значит, для того, чтобы быть неоднозначно декодируемым, слово должно содержать 4кодовых слова 101010 и одновременно 3 кодовых слова 01010101.Легко заметить, что искомым словом минимальной длины являетсяz}|{ z}|{ z}|{ z}|{010101010101010101010101|{z} | {z } | {z } | {z } |{z 0.}IVII.2.1(4, 6). С помощью процедуры Хаффмена построить двоичныйкод с минимальной избыточностью для набора вероятностей P :4) P = (0.5, 0.2, 0.1, 0.09, 0.08, 0.03) ;6) P = (0.3, 0.3, 0.2, 0.04, 0.03, 0.03, 0.03, 0.03, 0.03, 0.01) .J4) P = (0.5, 0.2, 0.1, 0.09, 0.08, 0.03). Построим дерево кода C:35Спускаясь от корня к вершинам, получим кодовые слова, соответствующие указанным вероятностям:C = {0, 10, 1100, 1101, 1110, 1111}.6) P = (0.3, 0.3, 0.2, 0.04, 0.03, 0.03, 0.03, 0.03, 0.03, 0.01) .Построим дерево кода C:1.0010.4100.2010.08000.6010.3 0.30.060110.1210.040.0601010.2 0.04 0.03 0.03 0.03 0.03 0.03 0.01Спускаясь от корня к вершинам, получим кодовые слова, соответствующие указанным вероятностям:C = {00, 01, 10, 1110, 11000, 11001, 11010, 11011, 11110, 11111}.IVII.2.10(4, 5, 10).

Выяснить, существует ли двоичный код с минимальной избыточностью, обладающий заданной последовательностью Lдлин кодовых слов:4) L = (1, 2, 3, 4) ;5) L = (1, 2, 3, 4, 4) ;10) L = (3, 3, 3, 3, 3, 3) .36J Двоичный код с минимальной избыточностью и заданным наборомдлин кодовых слов существует в том и только том случае, когда неравенство Макмиллана выполнено как равенство:rX1= 1.li2i=1114) Нет, так как 12 + 14 + 18 + 16= 1 − 16< 1.11115) Да, так как 2 + 4 + 8 + 2 · 16 = 1.10) Нет, так как 6 · 18 < 1.IЗанятие № 1.11Коды, исправляющие ошибкиVII.3.17.1) Показать, что код исправляет t ошибок тогда и только тогда, когдарасстояние между любыми двумя кодовыми словами не меньше2t + 1.2) Показать, что код обнаруживает t ошибок тогда и только тогда,когда расстояние между любыми двумя кодовыми словами не меньше t + 1.J1) Код C исправляет t ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше 2t + 1.Это условие эквивалентно тому, что расстояние между центрами шаров радиуса t (кодовыми словами) не меньше, чем 2t + 1,что эквивалентно тому, что эти шары не пересекаются.

Таким образом, на выходе получится слово, принадлежащее единственномуоднозначно определённому шару (если в слове не более t ошибок),что позволяет точно восстановить слово, так как известен центрэтого шара.2) Код обнаруживает t ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше t + 1.Это условие эквивалентно тому, что ни один из центров шаров(кодовое слово) не содержится в каком-либо другом шаре, то естьесли произошло не более t ошибок, можно в точности установить,что полученное на выходе слово не совпадает с центром ни одногоиз шаров.I37VII.3.20(1, 2).

Булева функция f (exn ) называется характеристической для подмножества C ⊆ B n , если C = Nf .Определить, сколько ошибок обнаруживает и сколько исправляет кодс характеристической функцией f :1) f (exn ) = x1 ⊕ x2 ⊕ . . . ⊕ xn ;2) f (exn ) = x̄1 · x̄2 · . . .

· x̄n ∨ x1 · x2 · . . . · xn .J1) f (exn ) = x1 ⊕ x2 ⊕ . . . ⊕ xn .Кодовое расстояние равно 2, так как на соседних наборах функция принимает различные значения.Код обнаруживает 1 ошибку и исправляет 0 ошибок.2) f (exn ) = x̄1 · x̄2 · . . . · x̄n ∨ x1 · x2 · . . . · xn .Nf = C = {(00 . .

. 0), (11 . . . 1)}.Кодовое расстояние равно ρ((00 . . . 0), (11 . . . 1)) = n.Код обнаруживает n − 1 ошибку и исправляет [ n−12 ] ошибок. IVII.3.27. Показать, что мощность плотно упакованного hn, 2t + 1iкода равна2n.tPni=0iJ hn, 2t + 1i-код C = {eα1 , αe2 , . . . , αek } плотно упакован, поэтому справедливо:αi ) ∩ Stn (e1) ∀i 6= j Stn (eαj ) =∅;2) ∀βe ∈ B n ∃eα ∈ C: ρ αe, βe 6 t.Весь булев куб B n разбивается на непересекающиеся шары радиуса tα).

Числос центрами в кодовых словах. Посчитаем мощностьшара Stn (eneнаборов β, отличающихся от αe в i позициях, равно i . Значит, мощностьtPnвсего шара равнаi .i=0Разделив мощность булева куба на мощность шара, получим числокодовых слов, то есть искомую мощность кода.IVII.4.9. Доказать, что кодовое расстояние линейного кода C равноминимальному весу ненулевого кодового слова.J Пусть минимальный вес ненулевого кодового слова αe равен d: keαk =d.

Предположим, что кодовое расстояние s линейного кода C меньше d.Тогда ∃eα1 , αe2 ∈ C : ρ(eα1 , αe2 ) = s. Но по определению линейного кодаαe1 ⊕ αe2 = αe0 ∈ C, причем keα0 k = s < d — противоречие. Значит, кодовоерасстояние s > d.38Поскольку e0 ∈ C для любого линейного кода, ρ(eα, e0) = d. Значит,кодовое расстояние s линейного кода C в точности совпадает с d — минимальным весом ненулевого кодового слова.IVII.4.7(г).110011) По матрице H = 10101 найти кодовое расстояние d(C(H))01110кода C(H), порожденного матрицей H.2) Построить проверочную матрицу H ∗ для кода C(H), порожденного матрицей H.J1) Обозначим αe1 = (11001), αe2 = (10101), αe3 = (01110).

Заметим,что αe1 ⊕ αe2 ⊕ αe3 = (00010), поэтому, согласно утверждению задачиVII.4.9, d(C(H)) = 1.2) В проверочной матрице должно быть 5 − 3 = 2 строки βe1 , βe2 :5Mαeik & βejk = 0 i = 1, 2, 3; j = 1, 2.k=1Выполним элементарные преобразования строк матрицы H:110011100110101 −→ {прибавим ко 2-й строке 1-ю} −→ 01100 −→011100111011001−→ {прибавим к 3-й строке 2-ю} −→ 01100 .00010Проверочная матрица может иметь, например, такой вид:11100∗H =.10001IVII.3.21(5). Построить по методу Хэмминга кодовое слово для сообщения αe = 10101011.J Для сообщения αe = 10101011 имеем:m = 8,2l} = 12.n = min{l : 28 6 l+1Кодовое слово βe имеет вид:β1 β2 β3 β4 β5 β6 β7 β8 β9 β10 β11 β12 = β1 β2 1β4 010β8 1011,39гдеβ1β2β4β8= β3 ⊕ β5 ⊕ β7 ⊕ β9 ⊕ β11 = 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1,= β3 ⊕ β6 ⊕ β7 ⊕ β10 ⊕ β11 = 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 1,= β5 ⊕ β6 ⊕ β7 ⊕ β12 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0,= β9 ⊕ β10 ⊕ β11 ⊕ β12 = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1.Откуда βe = 111001011011.IVII.3.22(8).

По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения αe. После передачи по каналусвязи, искажающему слово не более чем в одном разряде, было полученослово βe = 11011100110. Восстановить исходное сообщение.J n = h11,i211m = log2 12 = [9 − log2 3] = 7,k = n − m = 4,βe = 11011100110 = β1 β2 β3 β4 β5 β6 β7 β8 β9 β10 β11 .Получим вектор v = (v3 v2 v1 v0 ):v0v1v2v3= β1 ⊕ β3 ⊕ β5 ⊕ β7 ⊕ β9 ⊕ β11 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 = 1,= β2 ⊕ β3 ⊕ β6 ⊕ β7 ⊕ β10 ⊕ β11 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 = 1,= β4 ⊕ β5 ⊕ β6 ⊕ β7 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1,= β8 ⊕ β9 ⊕ β10 ⊕ β11 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0.Получаем, v = (0111) и (0111)2 = 710 — ошибка в седьмом разряде.Неискажённый кодовый вектор имеет вид: βe0 = 11011110110.

Вычеркивая проверочные разряды (1-й, 2-й, 4-й и 8-й), получаем исходное сообщение: αe = 0111110.I40Занятие № 1.12Автоматы. Часть 11,1IV.2.13(1). Для функции f из P2,одпостроить схему над множеством,состоящим из элемента единичной задержки и функциональных элементов «дизъюнкция», «конъюнкция» и «отрицание»:y(t) = x(t) ∨ q(t − 1),f : q(t) = x(t) & q(t − 1),q(0) = 1.J Сначала построим схему из функциональных элементов над множеством, состоящим из дизъюнкции, конъюнкции и отрицания, для следующей совокупности булевых функций:y(t) = x(t) ∨ q(t − 1),q(t) = x(t) & q(t − 1).Такая схема из функциональных элементов будет состоять из двухвходных каналов (по переменным x(t), q(t − 1)) и двух выходных (попеременным y(t), q(t)):q(t-1)x(t)¬&y(t)q(t)Теперь замкнём выходной канал по переменной q(t) на входной каналq(t − 1).