Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 50
Текст из файла (страница 50)
О на 1, а 1 на О. Если слово о при передаче по каналу преобразовывалось в слово г3, отличное от П, то говорят, что в канале произошли ошибки. Если г-я буква переданного слова й отличается от 1-й буквы полученного слова Д, то говорят, что произошла ошибка в 1-.м разряде. Если полученное слово отличается от переданного в 1 разрядах, то говорят, что произошло 1 ошибок. Ясно, что число ошибок, имевших место при передаче, равно расстоянию Хэмминга между переданным и принятым словами.
Пусть С С В" некоторый код. Произвольное однозначное отображение ~р множества В" на множество С называется декодированием. Пусть П е С, а уз з(П) — — множество тех Д б В", для которых ф(3) = П, Пусть В~" (В) - -- шар радиуса 1 с центром П в Вв. Говорят, что код С исправляет 1 ошибок, если существует такое декодирование ф, что Я,в(а) С ф '(П) для каждого П Е С.
Очевидно, что код С исправляет 1 ошибок тогда и только тогда, когда В,"(В) Г1 Вв(,3) = И для любых двух различных кодовых слов П, (3 из С. Говорят, что код С обнаруживает 1 ошибок, если любое слово, которое можно получить из произвольного кодового слова В в результате нс более 1 ошибок, отлично от любого слова С11Й). Таким образом, код С обнаруживает 1 ошибок, если С й В,"(В) = (П) для любого о е С.
Метод Хзмминга построения кодов, исправляющих одну ошибку, заключается в построении по произвольному двоичному набору а = оы пз, ..., о„„называемому в дальнейшем сообщением, кодирующего слова (3 = Д, (эю ..., 13„, где п и т связаны соотношением и = шш(1: 2о' < 2'Я + 1) ). Кодирующее слово (3 содержит все разряды набора В и, кроме того., й проверочных разрядов ро, ры, рь — ы При этом ~3з = ро если 3 = 2' (1 = О, 1, ...., й — 1), и Я = о П,я,я, если 3 не является степенью двойки. Значения проверочных разрядов рв, ..., рь.
1 определяя>тся из равенств вида Р; = )3з.е, Е А +, Е ..., ' = О, ..., й — 1, 246 Гл. И1. Эвеиеитм виеории кодирования где в правую часть входят все координаты 55 (2' < 5 < и), у которых двоичное разложение индекса у имеет коэффициент при 2', равный единице. Пример 1. Построим по методу Хэмминга кодовое слово для сообщения а = (1011). Имеем щ = 4, и = щ1п(1: 2'" < 2~Я + 1)) = 7, к = и — т = 3. Кодовое июво,З имеет вид Яцз55зДЯЯ75г —— = Рорд1рз011. Значения проверочных символов определяются из равенств Ро =55з 955з 955г =19091= 0, Рг = 55з 955в 96г = 19191 = 1, Рз = 55з 955в 955г = 09191 = О.
Таким образом, кодовым словом для И является вектор 55 = (0110011). Декодирование состоит в том, что по вектору 15 = (Ры ..., 55о), полученному из некоторого кодового слова путем искажения не бо- лее чем в одном разряде, восстанавливается исходное сообщение а = = (аы ..., о ).
Декодирование осуществляется следующим образом. ПУсть т = ~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 с С).
Наибольшее число й = й(С), для которого в группе (в линейном пространстве, которым также является группа в В") С существует к линейно независимых векторов, называется размерносглвго С. Совокупность из Й линейно независимых векторов пространства размерности Й называется базисом этого пространства. Если код С С В" образует группу, то он называется линейным или групповым. Если линейный код в В" имеет размерность к, то он называется (п,к)-кодом. Двоичный линейный код, исправляюший одну ошибку, называется кодом Хзмминеа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
