А.А. Вороненко - Решение избранных задач по курсу дискретной математики (1115192), страница 6
Текст из файла (страница 6)
ч 1) с (х ) = хс ссс х2 сЭ ° ° ° Ю хи. Кодовое расстояние равно 2, так как на соседних наборах функция принимает различные значенси. Код обнаруживает 1 ошибку и исправляет 0 ошибок, 2) Дх ) = хс 4с хз 4с... й х„с с хс й х2 й... 4с х„. С = ((00...0),(11...1)). Кодовое расстояние равно р((00... О) „(11... 1)) = и. Код обнаруживает и - 1 ошибку и исправляет [к~1) ошибок.
УП.3.27. Показать, что мощность плотно упакованного (н,21+ 1)- кода равна 2" 2.',("с) ° я — (а,21+ 1) -код С = (ам ссз,..., аь) — плотно упакован =ь 1. И у1,1 =ь Вс'(ссс) 1'с Яс" (ст ) = Ы 2. ссд Е В" Ы б С: р (а, р) < г — Весь булев куб Вч разбивается на непересекающиеся шары радиуса 1 с центрами в кодовых словах. Посчитаем мощность шара Яс" (а). Число наборов В, отличающихся от ст и с позициях, равно (",.). с Значит, мощность всего шара равна 2 (',.') с=с Разделив мощность булева куба на мощность шара, получим число кодовых слов, то есть мощность кода: 2" Е (",) УП.4.9.
Доказать, что кодовое расстояние линейного кода С равно минимальному весу ненулевого кодового слова. ° Пусть Ы вЂ” кодовое расстояние линейного кода С Достаточно показать, что 50 1. Баб С: '9а~( = с( 2. суаЕС: (Щ =сс =ь ЪЗ,'уе:С: ~сз — 7~ =сс (1) Если с1 с- кодовое расстояние линейного кода С, то Вас, сь2 б С: )ссс — а2! = д. С вЂ” линейный код, следовательно, ас бс аз = а 6 С, причем !Н =4.
(2) сс б С, 9Щ = д, 0 е С, значит, )сх — 0~ = сс. и УП,4.7(г). 11001 1) По матрице Н =- 10101 найти кодовое расстояние с1(С(Н)) 01 ПО кода С(Н), порожденного матрицей Н, 2) Построить проверочную матрицу Н* для кода С(Н), порожденного матрицей Н. ° я 1) Обозначим ас = (11001), аз = (10101), аз = (01110). Заметим, что ас ссс сс2 с".9 стз = (00010) =ь сХ(С(Н)) = 1. (см. также (УП,4.9)) 2) В проверочной матрице должно быть 5 — 3 = 2 строки Д, сиз: ас ®)3, = (ООООО) УВ = 1,2,3, с = 1,2. Выполним элементарные преобразования строк матрицы Н: < 11001 11001 10101 — (прибавим ко 2-й строке 1-ю) — + 01100 01110 01110 — (прибавим к З-й строке 2-ю) — с 01100 00010 Проверочная матрица может иметь, например, такой вид: 10001 Ъ"П.3.21(б), Построить по методу Хэннинга кодовое слово для ссюбщения а = 10101011.
° я Для сообщения а = 10101011 имеем: ти = 8 и ппп(1, 2В ( ~2' ) 12 Огллвление 53 Кодовое слово д имеет вид: дтдгдзд4дздодтдздод одтьдтг = дтдг1дз010дз10П, дт =до Юдз Юд Юд Юд11 =190909191=-1 дг — дз 9 дз 9 дт Ю дто 9 дп = 1 9 1 9 О 9 О 9 1 = 1 дз=д ЮдоЮд Юдтг=0919091=0 дз = до 9 дто Ю ди 9 дтг = 1 9 0 Ю 1 Ю 1 = 1 ~ д = П1001011011. 7П.З.22(8), По каналу связи передавалось кодовое слово, постро- енное по методу Хзмминга для сообщения а.
После передачи по каналу связи, искажающему слово пе более чем в одном разряде, бьшо получено слово д = 110П100110, Восстановить исходное сообщение, ° п=П г" ~ т = ((од г ~ = [9 — 1од~З) = 7 й = и — тп = 4 д = ПОП100110 = дтдгагдзагазаздзазаоат Получим вектор ч = (соотг~со): со=дтЮдзЮдзЮдтЮдоЮдм =19091909190=1 тч =дт ЮдзЮдоЮдтЮдтоЮдм =19091909190=1 ттг = дз 9 дз Ю до 9 дт = 1 Ю 1 9 1 9 О = 1 сз=дз9дзЮдто9дм =0919190=0 Получаем, и = (П10) н с(ч) = 0 2з+ 1 ° 2г + 1 2' + 1.
2о = 7 =о ошибка в 7-м разряде, Неискаженный кодовый вектор имеет вид: д' = ПОППОПО. Вычер- кивая проверочные разряды (1-й, 2-й, 4-й и 8-й), получаем исходное со- общение: а = ОПП10, Занятие №1. Функции алгебры логики. Формулы. Существенные и фиктивные переменные .......,...........................,.....
3 Занятие № 2, ДНФ, КНФ, СФЭ ...,......,.......,...,..... „..... б Занятие №3. Полиномы и линейные функции ..........,......... 9 Занятие № 4. Замкнутые классы ..............,,................... 12 Занятие №5. Класс М. Подсчет числа функций ...,.....,......., 14 Занятие №6. Полнота в Рг ............,................,.......... 17 Занятие № 7, Контрольная работа Занятие №8, Графы: изоморфизм, связность .....................
19 Занятие №9. Графы: деревья, нзоморфизм ....................... 24 Занятие №10. Графы: планарность, раскраски, орграфы ......... 27 Занятие № П. Автоматы .......,,,................................ 30 Занятие № 12, Автоматы,............,.....,..............,....,., 35 Занятие №13. Алфавитное кодирование, Оптимальные коды ..... 44 Занятие №14. Коды„исправляющие ошибки ...,.....,..........,. 49 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
