Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 51
Текст из файла (страница 51)
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) а) — д) построить проверочные матрицы Н* для кодов С(Н), порожденных матрицей Н. 4.8. Пусть т = [1оя (2о((п+ 1)) и ~р: В" + В" отображение т-мерных векторов в и-мерные по методу Хэмминга (см, з 3).
Пусть к = п — т и Н матрица размера й х п, составленная из наборов (взятых в качестве столбцов) с номерами от 1 до и, расположенных в порядке возрастания номеров. Доказать, что матрица Н является проверочной для кода С = ~р(В'"). Например, матрица Н из задачи 4.7, 1), д) является проверочной для кода С = ~р(Ве). Пусть Я и Р матрицы размерности соответственно й х гл и к х п.
Тогда через ЯР) будем обозначать матрицу размерности Й х (ел+ и), в которой 1-я строка (1 < 1 < Й) получена приписыванием справа к 1-й строке матрицы Ц матрицы Р. 4.9. Доказать, что кодовое расстояние линейного кода С равно минимальному весу ненулевого кодового слова. 4.10. Пусть Н = (1яР), где 1 — - единичная матрица размерности к х й, а Р произвольная двоичная матрица размерности й х х (и, — к), каждая строка которой содержит по меньшей мере две единицы и все строки попарно различны.
Доказать, что код С(Н), порожденный матрицсй Н, является кодом Хэмминга. 4.11. Выяснить, каково кодовое расстояние И(С(М)) кода С(М), порожденного матрицей М = (1эН), где 1; единичная матрица размерности 5 х 5, а Н .- матрица из задачи 4.7, 1), д). 4.12. Пусть Г С В" пространство, состоящее из линейных комбинаций матрицы Н = (1еР), где 1ь -- единичная матрица размерности Й х Й, а Р --" матрица из нулей и единиц размерности й х (и — Й). Доказатгн что 1' является нулевым пространством для матрицы С = (Рт1„ь), где 1„ь единичная матрица размерности (н — й) х (ц — й), а Рт матрица, транспонированная к матрице Р.
4.6. Найти число векторов, ортогональных к данному ненулевому вектору Н из В". 4.7. 1) По матрице Н найти кодовое расстояние д(С(Н)) кода С(Н), порожденного матрицей Н: 252 Гл. еВ. Элементов теории новирования 4.13. Показать, что кодовое расстояние (и, к)-кода не превосходит (и. 2" ~/(2в — 1)). 4.14. Показать, что при и = 2е( — 1 мощность линейного (и, Щ- кода не превосходит 2е(. 4.15. 1) Показать, что максимально возможная мощность д(п, е() линейного (и, е()-кода удовлетворяет неравенству д(п, е() ( 2д(п — 1, е(). 2) С использованием утверждения задачи 4.14 показать, что д(п, е() ( е( 2и г"+г 4.16.
Пусть код С является нулевым пространством матрицы С. Показать, что кодовое расстояние кода С тогда и только тогда нс меньше е(, когда, любая совокупность из е( — 1 или меньшего числа столбцов матрицы Н является линейно независимой. е — г т-»еп — 11 4.17. Показать, что если ~ ~ . ) ( 2 — 1, то существует 1 матрица из нулей и единиц размерности Й х т, в которой любые е( — 1 столбцов линейно независимы и, следовательно, существует (и, п — Й)-код с кодовым расстоянием не меныпе е(. 4.18.
1) Показать, что д(9, 5) = 4. 2) Показать, что т(9, 5) 3 5, 4.19. Показать, что число различных базисов в В" равно (2" — 1)(2" — 2)... (2' — 2" ') и! 4.20. Показать, что число различных (п, й)-кодов в В" равно (2" — 1)(2" — 2)...(2в — 2" ' ) (2ь — 1)(2е - 2) (2и - 2и-г) ' Глава ЪтШ ЭЛЕМЕНТЫ КОМБИНАТОРИКИ З 1. Перестановки и сочетания Свойства биномиальных коэффициентов Набор элементов а„, ..., а,„из множества Ьт = (ам ..., ав1 называется выборкой объема т из и элементов или (и, г)-выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан.
Пвс упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной В выборках могут допускаться или не допускаться повторения элементов. Упорядоченная (и, г)-выборка, в которой элементы могут повторяться, называется перестпановкой с повторениями из п элементов по г или (и, т)-пересплаювкой с повторениями. Если элементы упорядоченной (и, т)-выборки попарно различны, то она называется (и, т)-перестановкой без повторений или просто (и, т)-перестановкой Число (п, т)-перестановок будет обозначаться символом Р(п, г), а число (п, г)-перестановок с повторениями символом Р(п., т).
Неупорядоченная (и, г)-выборка, в которой элементы могут повторяться, называется сочетпанием с повторениями из п, элементное по т или, короче, (и, т)-сочетонием с повторениями. Если элементы неупорядоченной выборки попарно различны, то она называется сочетанием (без повторений) из п элементов по т или (и, г)-сочетанием. Каждое такое сочетание представляет собой подмножество мощности т множества Ьт. Число сочетаний из и элементов по г будет обозначаться через С(п, г). Число сочетаний с повторениями из и элементов по т будет обозначаться через С(а, т). Пример 1. Пусть Ьт = (а, 6, с), г = 2.
Тогда имен~тел: девять перестановок с повторениями --. аа, а6, ас, Ьа, ЬЬ, Ьс, са, сЬ, сс; шесть перестановок без повторений аЬ, ас, Ьа, Ьс, са, сЬ; шесть сочетаний с повторениями аа, а6, ас, ЬЬ, Ьс, сс; три сочетания без повторений аЬ, ас, Ьс. 254 Гл. 7П1. Элементы комбинаторики Произведение п(п — 1)... 1т~ — т + 1), где п действительное, а т целое положительное, будет обозначаться через 1т1), По определению положим 1ие) = 1. Если п натуральное, то 1п)„обозначается символом и! и называется и-факториалом. При и = О полагаем О! = 1. Для любого действительного и и целого неотрицательного т величина — ' называется биномиальным коэффициентом и обознача1н),.
ется символом ) ~ ~. Пусть тю тз, ..., тя -- целые неотрицательные ?и'1 ~т~' п! числа и т з + тз +... + ть = п. Величина называется па- тП тИ т„! линомиальным коэффициентом и обозначается через ( ~ть тм ..., тяу ' При подсчете числа различных комбинаций используются следующие два правила. Правило произведения. Если объект А может быть выбран п способами и после каждого из таких выборов объект В в свою очередь может быть выбран и способами, то выбор «А и В» в указанном порядке может быть осуществлен т .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
