Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 52
Текст из файла (страница 52)
Векторы Нг, ..., Н, называются линейно независимыми, если любая их нетривиальная комбинация отлична от нулевого вектора. В противном случае говорят, что векторы егг, ..., й, линейно зависимы. Подмножество С С В" называется группой, если С замкнуто относительно операции сложения по модулю 2, т. е. если для любых гэ, гг из С вектор гз бган принадлежит С. Из замкнутости С относительно операции гЭ вытекает, что всякая линейная комбинация векторов из С также принадлежит С (в частности, 0 с С).
Наибольшее число й = й(С), для которого в группе (в линейном пространстве, которым также является группа в В") С существует к линейно независимых векторов, называется размерносглвго С. Совокупность из Й линейно независимых векторов пространства размерности Й называется базисом этого пространства. Если код С С В" образует группу, то он называется линейным или групповым. Если линейный код в В" имеет размерность к, то он называется (п,к)-кодом.
Двоичный линейный код, исправляюший одну ошибку, называется кодом Хзмминеа. 250 Гл. 'сН. Элементы теории кодирования Линейные коды удобно задавать с помощью матриц. Матрица Н(С), строками которой являются кодовые слова кода С С В", называется матриией кода С. Матрица М(С), строками которой являются векторы некоторого произвольного базиса (и, к)-кода С, называется порождаюсаей матриией кода С. Если Н произвольная матрица, строками которой являются векторы из В", то множество С(Н)., составленное из всех попарно различных вершин куба В", являющихся линейными комбинациями строк матрицы Н, называется кодом, порожденным матриией Н.
Векторы Н = (оз, ..., оы) и Д = 1)зы ..., Дь) называются ортогональными, если сьев 9... ... Ю опдь = О. Множество $'(Н) всех векторов из В", ортогонапьных к каждой из строк матрицы Н, называется нулевым пространством матрицы Н. Пусть С - - двоичный код,. каждое слово которого ортогонапьно каждой строке некоторой матрицы Н. Если С является (и, й)-кодом, а матрица Н состоит из п — к линейно независимых строк, то Н называется проверочной, матрипей кода С. Множество С' всех векторов, представимых в виде линейной комбинации строк проверочной матрицы (и, к)-кода С, называется кодом, двойтпвеннь|м к коду С.
Через д(п, д) обозначается шах~С~, где максимум берется по всем линейным кодам С С Вь с кодовым расстоянием И. 4.1. Пусть векторы Н и В из В" являются кодовыми словами, построенными по методу Хэмминга. Показать, что Н 9 Д также является кодовым словом для некоторого сообщения. 4.2.
1) Выяснить, являются ли векторы множества А линейно зависимыми: а) А = 1010, 101); б) А = 1010, 011, 001); в) А = 1010, 101, 110); г) А = 1101, 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
