Дискретная математика
Данное учебное пособие является продолжением учебного пособия «Дискретная математика», Ч. I (авторы: Б. М. Веретенников, В. И. Белоусова). Работа включает в себя следующие разделы дискретной математики: многочлены над конечными полями, коды, исправляющие ошибки и элементы теории графов. Предлагаются упражнения для самостоятельного решения. Пособие предназначено для студентов инженерных направлений и специальностей ИРИТ–РтФ УрФУ.
часть 2
Содержание
Содержание книги "Дискретная математика "
Отрывок из книги
24Глава II. Коды, исправляющие ошибки В дальнейшем коды над F2 и F3 будем называть бинарными и тернарными соответственно.Определение. Проверочной матрицей линейного ()n,k-кода C над Fq при всех k n< называется матрица H размера (),n kn-ґ такая, что при x FqnО условие x СО равносильно условию Hxt=0, где xt — столбец, полученный транспонированием вектора x.Теорема 1.1. Если H — проверочная матрица ()n,k-кода C, то rank H n k= -.2. Пусть M — матрица размера (),n kn-ґ rank M n k= - и G — порождающая матрица ()n,k-кода C. Тогда M — проверочная матрица в том и только том случае, когда MGOt=, где О — ну-левая матрица.Доказательство. 1. По условию C — подпространство вектор-ных решений однородной линейной системы уравнений (ОЛСУ) с матрицей H. Тогда по известной теореме линейной алгебры kC nH== -dim,rank откуда rank.H n k= -2. Ввиду того, что строки G образуют базис C, заключаем, что условие MGOt= равносильно условию " О=c Mct0. (1)С другой стороны, пространство решений ОЛСУ с матрицей М имеет размерность n n kkC( )dim .= = Поэтому условие (1) равносильно тому, что это пространство совпадает с C, что рав-носильно, в свою очередь, тому, что М — проверочная матри-ца кода С.1.2. Вычисление проверочной матрицы с помощью систематической порождающей матрицыСделаем сначала ряд определений и замечаний.Определение. Порождающая матрица ()n,k-кода называется систематической, если она имеет вид E Bk|,() где Ek — единич-
Веретенников Б. М. другие книги автора
С книгой "Дискретная математика" читают
Внимание!
При обнаружении неточностей или ошибок в описании книги "Дискретная математика (автор Борис Веретенников, Вероника Белоусова, Александр Веретенников)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!
и мы свяжемся с вами в течение 15 минут
за оставленную заявку