Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 50
Текст из файла (страница 50)
Декодирование осуществляется следующим образом. ПУсть т = ~1обз(2"/(и+ 1))), й = п — т. Вычислим по вектоРУ 55 = = (5ы ..., Д„) Й сумм вида и, = Я. 955з,в1 9..., 1 = О, ..., к — 1, где в ~,'-ю сумму включаются все координаты 55, (2' < у < н), у кото- рых двоичное разложение индекса 5 имеет коэффициент при 2', рав- ный единице. В результате получаем двоичный вектор и = (ио,... з) и число Р(и) = ~~~ е, 2'. Это число указывает номер о«ь разряда, в котором произошла ошибка. Если Р(ч) = О, то считаем, что ошибки при передаче не было.
Если Р(ч) > и, то считаем, что передавалось слово, которое нс является ни кодовым словом сообще- ния а, ни кодовым словом, искаженным в одном разряде. Пример 2. Декодировать вектор 55 = (1001110). Имеем п = 7, т = [!обз(2г/8)) = 4, к = п, — т = 3. Вычислим вектор и = (ио, оы из). Имеем 'оо = А 975з 955з 955г = 1909190 = О,. и1 = 55з 9дз 955в 9дг = 090919 0 = 1, из =554955з 955в 955г = 1919190 = 1.
Получаем, что о(ъ) = 1 2з+ 1. 2~+ 0 2" = 6. Следовательно, ошиб- ка произошла в шестом разряде. Неискаженный кодовый вектор имеет вид Д' = (1001100). Вычеркивая проверочные разряды с номерами 1, 2, 4, получаем исходное сообщение а = (0100). 3.17. 1) Показать, что код исправляет 1 ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше 21+ 1. й* о. Сомокорректируюгчиеся коды 247 2) Показать, что код обнаруживает е ошибок тогда и только тогда, когда расстояние между любыми двумя кодовыми словами не меньше 1+ 1. 3.18.
Лля данного множества С С В" найти кодовое расстояние: 1) С = (ПООО., 10101, ОП10); 2) С = (П1100, ПООП, ООП1Ц; 3) С = (00001, ПП1, 10100, 01010); 4) С = (101010, 010ПО, 000001): 5) С = (ОП01010, ПОООПО, ОООП001, 1010ПОО). 3.19. Для каждого из кодов С предыдущей задачи найти: а) число ошибок, нагорью код С обнаруживает; б) число ошибок, которые код С исправляет. 3.20. Булева функция Дхп) называется характеристической для подмножества С С В", если С = Ху. Определить, сколько ошибок обнаруживает и сколько исправляет код с характеристической функцией 7: 1) г'(х ) = хз Ю хг йг... Ю хп', 2) 7(хчп) = хгхг .
° хп Н хгхг...хп; 3) 1(х ") =х,хг...хзпбгх,...хпхп,,...хзпЕ5 ео хз ° хпхп-~-1 ° хгпхгпаг ° ° хзп ~Э х1 ° ° хгпхгпз-1 ° ° хзп ~ 4) 1(х ) = хгхг ° хп — г ег хгхг ° хп — гхп 6~ ° ег хгхз ° хп 3.21. Построить по методу Хзмминга кодовое слово для сообщения: 1)а=010; 2)а=011: 3)а=1001; 4)а=П01; 5) а = 10101011; 6) а = П100ПП; 7) а = 1000100П; 8) а = 01110111011. 3.22.
По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения а. После передачи по каналу связи, искажающему слово не более чем в одном разряде, было получено слово Д. Восстановить исходное сообщение; 1),В = ПО; 2) )д = 10П10; 3) )г = 011ПО: 4) )3 = 1001011; 5) Д = 010П01; 6) )1 = 10П101; 7) )1 = ПОООП; 8) )) =1пппоопо; 9) )) =1010101010100; 10) Д = 0010ППОППП.
3.23. Показать, что при кодировании сообщений по методу Хэмминга кодовые слова, сопоставленные двум различным сообщениям одинаковой длины, различаются по меньшей мере в трех разрядах. 3.24. Множество сообщений Л задано характеристической функцией Дхг'). Построить характеристическую функцию д(х") множества кодовых слов, соответствующих сообщениям из Л: 1) 7(х~) = хг хг, 2) Дх~) = х Ч х; 3) г'(х ) = хзхгхз''ч хзхгхз, 4) г'(х ) = хзхг Ч хгхгхз.
248 Гв. И1. Эвеленты еиеорни ноднроввния 3.25. Верно ли, что код С С В", исправляющий 1 ошибок, обнаруживает: 1) не менее 21+ 1 ошибок; 2) не менее 21 ошибок; 3) не более 21 ошибок? 3.26. Показать, что из всякого подмножества С С В" можно получить код, обнаруживающий одну ошибку, удалив из С не более половины верпеин, 3.27. Показать, что мощность плотно упакованного (п, 21+1)-кода е равна2" е~ (,). е=о 3.28. Показать, что мощность максимального (и, 21 + 1)-кода не меньша 2н/ ~ ( . ) .
е=о 3.29. Показать, что т(п,е1) = 2 прн 2п/3 < е1 < и. 3.30. Показать, что т(и, 2п/3) = 4 при и, кратных 3. 3.31. Показать, что не существует максимальных кодов мощности 3. 3.32. 1) Показать, что при любом натуральном и и и = 2" — 1 существует разбиение куба Во на непересекаквщиеся шары радиуса 1. 2) Показать, что при п = 2" существует разбиение куба В" на непересекающиеся сферы радиуса 1.
3.33*. Д 1) т(п + 1, е1) > т(п, с~); 2) т(п + е1, д) > 2т(п, е?); 3) т(2п, е1) > (т(п, е1))з; 4) т(п, д) < 2т(п — 1, е1); 5) т(п, е1) < 2е1?'(2е1 — п) при и < 2е1. 3.34. Пусть о(п., И) - — максимальное число вершин в В"', попарные расстояния между которыми не превосходят е1. Доказать, что т(лв е1+ 1)ц(п, е1) < 2". 3.35. Показать, что из всякого множества С С В" можно выделить множество В мощности, не меньшей 2 от~~С~, которое является (и, п)-кодом.
3.36. Доказать, что гп(п, 4) < 2" "ез. 3.37. 1) Показать, что максимальный (п, 2)-код имеет мощность 2" 2) Выяснить, сколько существует максимальных (п, 2)-кодов. 3.38. Найти максимальную мощность множества С С В", в котором расстояния между любыми двумя вершинами четны. 3.39. Выяснить, существует ли плотно упакованный (п, 3)-код при п = 147. 3.40.
Показать, что не существует плотно упакованных (15, 7)-кодов. 249 ('4. Пикейные коды 3.41. Показать, что мощность всякого эквидистантного кода с нечетным кодовым расстоянием не превосходит 2. 3.42. Показать, что при четном д существует эквидистантный код мощности (2п/4]. 3 43. Показать, что т(п, к, 24) < (у)/~ (.') (, ). г=в 3.44. Показать, что при 2кз — п(2Й вЂ” д) > 0 ~ [2кг — п(21г — 4)~ 3.45.
Показать, что при й < д < и — и: 1) т,(п, й, 24) < [ — т(гг — 1, й — 1, 2д)~; 2) пг(гг,к,24) < [ — [ [...[ !...~~~; 3) т(п, к, 2аг) < [ — т(п — 1, кц 24)~; 4)т(п,й,24)< [— 3 4. Линейные коды Выражение вида Лгпг гЭ Лзсгз ггг... чг Лкп„ (1) где Н, е В", Л, е (О, Ц (г' = 1, ..., з), .называется линейной комбинацией векторов Нг,..., сг,. Линейная комбинация (1) называется тривиальной, если Лг = Лз =... = Л, = О, и нетривиальной в противном случае. Всякая линейная комбинация векторов из В" является вектором из В". Векторы Нг, ..., Н, называются линейно независимыми, если любая их нетривиальная комбинация отлична от нулевого вектора.
В противном случае говорят, что векторы егг, ..., й, линейно зависимы. Подмножество С С В" называется группой, если С замкнуто относительно операции сложения по модулю 2, т. е. если для любых гэ, гг из С вектор гз бган принадлежит С. Из замкнутости С относительно операции гЭ вытекает, что всякая линейная комбинация векторов из С также принадлежит С (в частности, 0 с С). Наибольшее число й = й(С), для которого в группе (в линейном пространстве, которым также является группа в В") С существует к линейно независимых векторов, называется размерносглвго С. Совокупность из Й линейно независимых векторов пространства размерности Й называется базисом этого пространства. Если код С С В" образует группу, то он называется линейным или групповым. Если линейный код в В" имеет размерность к, то он называется (п,к)-кодом.
Двоичный линейный код, исправляюший одну ошибку, называется кодом Хзмминеа. 250 Гл. 'сН. Элементы теории кодирования Линейные коды удобно задавать с помощью матриц. Матрица Н(С), строками которой являются кодовые слова кода С С В", называется матриией кода С. Матрица М(С), строками которой являются векторы некоторого произвольного базиса (и, к)-кода С, называется порождаюсаей матриией кода С.
Если Н произвольная матрица, строками которой являются векторы из В", то множество С(Н)., составленное из всех попарно различных вершин куба В", являющихся линейными комбинациями строк матрицы Н, называется кодом, порожденным матриией Н. Векторы Н = (оз, ..., оы) и Д = 1)зы ..., Дь) называются ортогональными, если сьев 9... ...
Ю опдь = О. Множество $'(Н) всех векторов из В", ортогонапьных к каждой из строк матрицы Н, называется нулевым пространством матрицы Н. Пусть С - - двоичный код,. каждое слово которого ортогонапьно каждой строке некоторой матрицы Н. Если С является (и, й)-кодом, а матрица Н состоит из п — к линейно независимых строк, то Н называется проверочной, матрипей кода С. Множество С' всех векторов, представимых в виде линейной комбинации строк проверочной матрицы (и, к)-кода С, называется кодом, двойтпвеннь|м к коду С.
Через д(п, д) обозначается шах~С~, где максимум берется по всем линейным кодам С С Вь с кодовым расстоянием И. 4.1. Пусть векторы Н и В из В" являются кодовыми словами, построенными по методу Хэмминга. Показать, что Н 9 Д также является кодовым словом для некоторого сообщения. 4.2. 1) Выяснить, являются ли векторы множества А линейно зависимыми: а) А = 1010, 101); б) А = 1010, 011, 001); в) А = 1010, 101, 110); г) А = (101, 110, 011); д) А = 10110, 1011, 0100, 1001); е) А = 11011, 0100, 1111, 0101).
2) Найти множество векторов, являюгцихся линейными комбинациями векторов из А. 3) Найти множество всех ненулевых векторов, ортогональных каждому из векторов множества А. 4.3. Пусть множество С С В" состоит из к линейно независимых векторов. Показать, что любые две линейные комбинации векторов множества С, различающиеся коэффициентами,. представляют собой различные векторы. 4.4.
Показать, что всякий (и, к)-код имеет мощность 2в. 4.5. 1) Показать, что в двоичном линейном коде либо каждый кодовый вектор имеет четный вес, либо половина кодовых векторов имеет четные веса и половина --. нечетные. 2) Пусть Н(С) матрица (и, й)-кода С. Показать, что в каждом ненулевом столбце ее ровно 2~ ' единиц. 3) Если матрица Н(С) (и, й)-кода С не содержит ненулевых столбцов, то сумма весов матрицы Н(С) равна и . 2Я 251 1'о. Линейные коды (10110з с 11001) (0001111) д) Н= 01110 1010101 а)Н= г) Н= 1110110010 10101010 11000101 010100П ' ) Н 00111100 0111100101 1001101010 0010011111 1101011101 2) Для каждой из матриц Н задач 1) а) — д) построить проверочные матрицы Н* для кодов С(Н), порожденных матрицей Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
