Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 49
Текст из файла (страница 49)
11оследовательность (ао, аы ..., аь) называется цепью в В ', если руст, ы сзь) = 1. Цепь (ао, аы ..., аь) такая, что р(аь, ао) = 1, называется циклом. Цепь (ао, Йы ..., аь) такая, что а, с < а, (ю = 1, ..., Й), называется возрас- тающей цепью. Число ь' называется длиной цепи (ао, аы ..., ая). Цикл С куба Во называется 2д-циклом, если ~СГ1 Влв(а)~ = 2И+ 1 для каждого а Е С. Через В","'"," обозначим множество всех набо- ров (соы аз, ..., а„) таких, что а, = и О = 1, ..., к).
Всякое такое множество называется (н — И)-мерной гранью направленно (П, ..., 1ь). 3.1. Показать, что для любых а, В, у из В" выполнены соотно- шения: 1) р(а, У3) = РАЯ, а); 2) РУа, у) < р(а, В) + РУВ, Я; 3) р(а, Й) = 0; 4) р(а. у) = р(а е с3, у е )3), тле (сз„..., .ав) е (Вй, ..., с3ь) = = (а, В )3„..., сц. Е ~3„); 5) р(а, с3) = )(а 6)3)), где Цаы ..., а„)(! = аз -ь... + аи; 6) РСа, )3) = ОЩ 9 (٠— 20а Г1 Я, где (аы ..., а„) П фы ..., Д„) = (аз Йуу~....., а„всрв).
3.2. 1) Найти число ребер в В". 2) Найти число неупорядоченных пар наборов а, В из В" таких, что р(а, )3) = к. 3.3. Найти число вершин в подмножестве: 1) А = Вс (а), 2) А = Яьв(а); 3) А = Вь'Уа) й В" (у3), где РУо, )3) = г; 4) А = Я"Са) Г1 Я„",(Д), где РСа, )3) = г. 3.4. Пусть а, )3 . вершины куба В", а р(а, 13) = т. Найти число вершин у, удовлетворяющих условию: 1) р(а, у) + РЯ, 13) = руа, )3); 2) р(а, у) + р(В, у) = г; 3) р(а, у) = й, р()3, у) = г; 4) р(а, у) < й, РУ)3, у) > г.
3.5. Показать несовместимость следующих систем соотношений дляа,у3, уизВ" (н>2): 1) Р(а Д)> 3 Р(3 7)> 3 Р(у а)> 3 2) и(а) < иф® у), оф) < и(а Ю у), иЯ < и(а св у3); 3) 'цй~ > Р Со 30., 'цй~ > !~а ьл 5ц, И > ~!а СЭ )3~~, !а Г (дсу у)~ = О. 3.6.
Множество А С В' называется полным в В", если лнзбой вектор 3 Е В" однозначно восстанавливается при условии, что для каждого Й Е А известно расстояние р(а,)3). Полное в В" множест- 6 Х Слглокорректируюгниеся коды 243 во А называется базисным, если для любого вектора а из А множество А~(а) не является полным. 1) Показать, что любая цепь Йо, а1, ..., ао 1 в Во образует базисное множество.
2) Показать, что множества В" и В,", 1 являются полными в В" при п > 2. Указать такое п > 2, что В" не является базисным. 3) При каких и и й множество В,'" не является полным в В" 2 4) Доказать, что всякое базисное множество А С В" удовлетво- ряст уиювию п!о82'(и — Ц < ~А~ < и,. 5) Доказать, что никакая грань размерности п — 2 не является полным в В" множеством. 6) Показать, что число 2?г„базисных множеств в В" удовлетворяет неравенствам 2((п — 1)!) < г?г„< ( ). ?2" 1 3.1. Пусть 1р — взаимно однозначное отображение В" на себя. Говорят, что 1р сохраняет рлсстояние, если р(а,?2) = Р(1р(а, 1р(гз)) для всех а,?д из В".
Доказать, что отображение сохраняет расстояние тогда и только тогда, когда оно может быть получено: а) с помощью некоторой перестановки координат во всех наборах из В"; б) заменой 0 на 1 и 1 на 0 в некоторых координатах всех векторов. 3.8. Отображение 02 множества В" в себя называется монотонным, если из и(а) < ггпу) вытекает, что о(1р(Н)) < о(1р(?1)). Найти число монотонных отображений куба из В". 3.9*. Пусть 1(А) число ребер и-мерного куба, соединяющих пары вершин подмножества А С В", а 1о(гп) = шах ~(А)~.
А С В ",. ( А ~ = ю 1 1) Доказать, что 1„(т) < — т 1оя2 т. 2 2) Доказать, что оценка и. 1) достигается при т = 2". 3) Пусть А С В", ~А( > 2" '. Доказать, что 1(А) > п. 4) Доказать, что 1(А) < 11~А~ — ш1п((А!., 2' — )АД. 3.10. Пусть Р„(п) семейство подмножеств А С В" таких, что р(а, ф < 2г для любых а,?д из А. Пусть 02„(и) = шах ~А~. АЕЕ Ггг1 1) Доказать, что максимум А по всем А Е г'„(п) не меньше ~~1 ( ).
0<г<г 2) Для нечетного и и 1 = (и — 1)/2 привести пример множества А Е Ег(п), не являющегося шаром радиуса т ни в одном из подкубов куба В" и такого, что (А! = ~ ~( ). 0<1< 3.11. Доказать по индукции, что наборы из В" можно расположить в цикл ао, а1,, аз — 1. 16* 244 Гл. 'гП. Элемвюаы творим кодирования 3.12. Лвоичный вектор (оо, оы ..., оз з) называется и-универсальным, если для всякого (Д, ..., Д,) из Во существует такой номер Й, что В,, = оьт, (1 = 1,..., и), где Й б1 = Й+1(шод2").
Например, вектор (0011) является 2-универсальным. 1) Выяснить, является ли и-универсальным вектор Н~: а) В4 = (0110); б) ггв = (0101); в) Вв = (0001 1101); г) о' = (0001 1010): д) о = (0100 0111); с) Н = (0100 1110); ж) Н'в = (0000111100101101); з) Н1в = (1100101101000011). 2) Локазать, что для всякого и существует и-универсальный вектор. 3.13. 1) Пусть 1(п) — — максимальная длина 2-цикла в В".
Найти 1(2), ЦЗ), Ц4). 2) Локазатгь что для всякого 2-цикла С С В" и любой грани С размерности 4 выполнено ~С й С~ < 8. 3) Показать, что максимальная длина 2-цикла в Ва не превосходит 2" ' (и, > 3). 3.14*. Пустыр(п)~(~р'(и)) --- максимальная мощность множества А С В" такого, что уНПЯ = 1 (соответственно уайЯ = 1) для любых двух различных векторов из А. Показать, что: 1) ~р(п) = и: 2) ьо'(п) = 2" 3.15*. Локазать, что куб В" можно представить в виде объединения попарно непересекающихся возрастающих цепей, обладающих следующими свойствами: Ц число цепей длины и, — 2Й равно ( Й) — ( Й 1), Й = 1, ..., [и/2); при этом минимальный набор каждой цепи длины и — 2Й имеет вес Й, а максимальный — вес и — Й; 2) если оо а,ты Н,тз .
три последовательные вершины цепи, имеющей длину и — 2Й, то вер|пина Д такая, что Н, < В < Ввез, В ф о, ы принадлежит цепи длины п — 2Й вЂ” 2. 3.16*. Пусть А С В" такое множество наборов, что не существует наборов Л, Д, 7 из А, для которых Н П В = 0 и о 0В = у. Пусть аь = ~А П В~",~. Показать, что а~„. ь„, аа а, + — + — ' < 2. Ь: ) (:) (.") 2. Коды, обнаруживающие и исправляющие ошибки.
Подмножество С С Во называется (двоичным) кодом с расстоянием д или, короче,. (и, а)-кодом, если шш р(Н,,З) = д. Число д называа,вес ется кодовым расстоянием множества С. Максимальная мощность (и, Щ-кода будет обозначаться через т(п, д). Если мощность (и, д)- кода равна т(гц а), то он называется максимальным. Плотно упакованным кодом называется (и, 2д+ 1)-код С, удовлетворяющий сле- З 3.
Самокорректируюыивсн коды 245 дующему условию: для всякого й Е В" существует )3 Е С такое, что р(а,,9) < д. Множество С С В" называется зквидистантным кодом, если величина р(Й, )3) постоянна для любой пары наборов П, )3 из С. Множество С С В" называется равновесным кодом, если существует целое число й (О < к < п), называемое весом кода, такое, что С С В". Положим т(п, д, к) = шах ~С~, где максимум берется по всем (и., д)-кодам веса Й.
Подмножества С С В" могут рассматриваться как множества двоичных слов, предназначенных для передачи по каналу связи, в котором могут происходить искажения передаваемых слов. Элементы множества С называются при этом кодовыми словами. Передача слова по каналу связи рассматривается здесь как преобразование, не меняющео длины передаваемого слова и состоящее в замене некоторых букв на противоположные, т.е. О на 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о), полученному из некоторого кодового слова путем искажения не бо- лее чем в одном разряде, восстанавливается исходное сообщение а = = (аы ..., о ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
