Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 135
Текст из файла (страница 135)
ДОКАЗАТЕЛЬСТВО. Очевидно, что если строка С принадлежит коду С~, то она ортогональна каждой строке из множества Я, поскольку она ортогональна каждой строке из кода С и Я С С. Предположим, что Я = (вг, вз, вз,... зь), и строка Г ортогональна строке в, для всех в, Е Я, так что т ° з! — — 0 для всех в; Е 5. Каждый элемент из С имеет вид 762 ГллВА са теория кодов где А' — транспозиция матрицы Аз, полученная заменой строк матрицы Аз на столбцы.
Матрица С~ называется матрицей контроля четности. Перебирая все возможные варианты, можно показать, что скалярное произведение любой строки из С с любой строкой из Са равно О. Отсюда получаем, что Сз-7Л. = о, где т, '— транспозиция с-ой строки матрицы С. По определению транспозиции г,'. является с-ай строкой матрицы С, преобразованной в столбец.
Мы превращаем строку в столбец, чтобы на него можно было умножить матрицу Сзч С (си1г1 + сиггг + созга) = со1С Tс + сигС г2 + созС гав с с л с ц с д с =0+0+0= Таким образом, если умножить матрицу С~ на транспозицию любого элемента из С, то получим О. В общем случае, если 1 0 0 . 0 Асьес Асл+2 Асп 0 1 0 0 А2ь„.1 Ага,г .. А2,п С = [1ь[А„ь] = 0 0 1 ' : АЗЛ+1 АЗ,И-г . АЗ,п 0 0 0 0 0 1 АЬ А+1 АК а+г Ак,п то А1 к+1 Аг к+1 . Аьлес 1 0 0 . 0 Агл+г Агл+г Аьл--г А1 ьс з Агм+з Ак,а+3 О О 1 С-" = [А'„я[1„я~ = 0 Аь, О О О О А1,п Аг,п Скалярное произведение с-ой строки матрицы С на у-ю строку матрицы Са равно 0+0+ ..О+Ачу+О+ О+Асд+ +0+0=0, так что в общем случае С'с'=О, где г,' — транспозиция с-ой строки матрицы В.
Если умножить матрицу С~ на транспозицию любого элемента из С, то, используя те же самые рассуждения, имеем в результате О. Мы также получаем еще один замечательный результат. Если два элемента Ь, и Ьг из Вп принадлежат одному и тому же смежному классу, образованному в Вп с использованием группы С, как это было сделано выше, то С"-Ьс = Сг-Ь$, РАЗДЕП 18.2. Порождающие матрицы 763 Для доказательства воспользуемся тем фактом, что если 61 и Ьз принадлежат одному смежному классу, то 61 = Ьз + с для некоторого с Е С. Следовательно, Ь' = Ь' + с' и 1 2 т.к.
Со=О для всех с Е С. Поскольку САЬ' одно и то же для всех 6 из класса смежности, то можно выбрать любое 6 из класса смежности и определить это значение. Таким образом, в каждую строку приведенной выше таблицы можно добавить это общее значение образа С, т.к. элементы каждой строки определяют класс смежности. л Мы выбираем лидера смежного класса, потому что он простейший, и помещаем значение его образа во второй столбец. Эти значения называются синдромами.
Уже известно, что первый синдром есть Находим, что 1 поэтому 0 — второй синдром, и 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 есс, получаем следующую таблицу. С'-Ь', = С'-(6', + с') = 2 = Слб' + Слс' = = С" Ьс + О = з = С~Ь', 1 поэтому 1 — третий синдром. 0 Продолжая проц а) :1 764 ГЛАВА Г8.
Творил кодов юшо шооо ПООП ОШО1 ОО1ОП оюпо оооооо ЮОЮ1 ОООЮ1 оошо опооо О1ООП ППО1 1О1ОП 1ООООО попо шпо ююоо 1ОООП ООПО1 опоп оюооо ооопо ПОЮ1 юопо поооо ШОП ОЮЮ1 ооооп оппо ЮПО1 ооюоо ююю шюо ПОШ ОПОО1 оооюо ЮООО1 оопп оюою ООЮО1 ОЮ1ОО юош оооою юпоо шою ПООО1 ОШП ЮПП ШОО1 поою ошоо ОО1ОЮ юоюо ООООО1 оюш ОЮОО1 ППП Ю1ОО1 ПО1ОО ооош 1ООО1О оопоо опою Заполнив таблицу, предположим, что получена переданная строка 10ПОО.
Умножение матрицы Сц на транспозицию строки дает О1ОО О11О1О О1ОО Отсюда следует, что 10ПОО находится в строке 6. Лидер смежного класса— 000010, элемент крайнего левого столбца строки, содержащей 10ПОО. Элемент С, расположенный в верхней строке столбца, содержащего 10ПОО, равен 10П10. Согласно способу построения таблицы имеем 10ПОО = 10П10+ 000010, поэтому можем предположить, что переданная строка 101100 должна иметь вид 10П10, и в пятом бите была ошибка. Этот метод намного быстрее, поскольку требует только умножить матрицу С~ на транспозицию строки-сообщения, найти строку, содержащую синдром, рдЗдЕЛ та.2.
Порождающие матрицы 765 и найти переданное сообщение. Лидер для этого сообщения — индикатор ошибки, а элемент кода С, расположенный в первой строке столбца, содержащего переданное сообщение, есть исправленное сообщение. Заметим, однако, что процесс можно сделать еще быстрее. При этом потребуются только два первых столбца приведенной выше таблицы. Предположим, что получено сообщение 110000. Умножение матрицы Сл на его транспозицию дает '] поэтому синдром— указывает, что ошибка появилась в третьем бите, то, добавляя 001000 к 110000, получаем 111000, исправленный код. Таким образом, этот метод прост. Умножить транспозицию сообщения на матрицу С", чтобы найти синдром.
Для этого нужно найти лидера смежного класса и прибавить его к сообщению, чтобы получить исправленный код. Обратите внимание, что используются только первые два столбца таблицы. Однако, теперь возникла еще одна проблема. Если полученным 1 1, и в соответствующей 1 сообщением будет строка 101001, то синдром будет строке будет три элемента с весом 2. Вспомним, что строка 100010 была выбрана произвольно. Любая из таких строк равновероятно может содержать ошибку, поэтому в данном случае совершенно безнадежно использовать синдромы для исправления ошибки. Кроме того, мы пытаемся в данном случае исправить строку с двумя ошибками вместо одной.
° УПРАЖНЕНИЯ 1. Какие из приведенных ниже матриц в действительности являются порождающими? Если нет, то почему? 2. Для заданной порождающей матрицы 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0 '[ .[ 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 а лидер смежного класса — 001000. Поскольку лидер 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 766 ГЛАВА 18. Теория кодов а) найдите С~; б) закодируйте 111,011,101,110; в) декодируйте 111011,110100,010010,011110; г) используя С~-, определите, какие из строк пункта (с) являются правильными кодированными строками. 3. Для заданной порождающей матрицы а) найдите С."; б) закодируйте 1111,0101,1001,1010; в) декодируйте 1111110,0111010,0111101,1011110; г) используя С~, определите, какие строки из пункта (с) являются правильными закодированными строками.
4. Для заданной порождающей матрицы [!!!~!!!1 а) найдите С~-; 6) постройте таблицу смежных классов вместе с лидерами; в) используйте эту таблицу для исправления ошибок (если они имеются) в переданных строках 1111100, 1111000, 0110101 и 1011000. 5. Для заданной порождающей матрицы 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 а) найдите С~-; б) найдите синдромы для смежных классов; в) используйте эти синдромы для исправления ошибок (если они имеются) в переданных строках 111101, 111001, 110010, 101001. 6.
Для заданной порождающей матрицы а) найдите С~-; РАЗДЕЛ та.з. Коды Хеммингв 787 б) найдите синдромы для смежных классов; в) используйте эти синдромы для исправления ошибок (если они имеются) в переданных строках 111101, 111001, 110101, 101001. 7. Для заданной порождающей матрицы 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 а) найдите С~; б) постройте таблицу смежных классов вместе с лидерами; в) используйте эту таблицу для исправления ошибок (если они имеются) в переданных строках 1110011, 1111000, 1101001, 1011101. 8. Объясните, что случится при использовании порождающей матрицы в упражнении 7, если будут две или более ошибок.
9. Используя порождающую матрицу из упражнения 5, найдите другие строки, отличные от строк матрицы С", которые принадлежат С~, и, используя эти строки, постройте матрицу контроля четности. 10. Используя порождающую матрицу из упражнения 4, найдите другие строки, отличные от строк матрицы С~, которые принадлежат С, и, используя эти строки, постройте матрицу контроля четности.
11. Докажите, что В„, множество всех двоичных строк длины и, — группа относительно сложения, введенного в этой главе. 12. Пусть С вЂ” код, образованный с помощью всех векторов, которые являются конечными суммами строк из Я. Докажите, что С вЂ” подгруппа В„ относительно сложения. 13. Докажите, что двойственный код для кода С, обозначаемый С~, является подгруппой группы В„относительно сложения. 18.3. КОДЫ ХЕММИНГА В конце предыдущего раздела было показано, что существовали определенные трудности при попытке исправить код для некоторых строк, поскольку все лидеры имели вес 1.
Эти трудности устраняются путем использования матрицы, называемой матриг1ей Хеммиига, в качестве порождающей матрицы. Перед тем как перейти к рассмотрению матрицы Хемминга Сн, посмотрим на матрицу контроля четности Сй. Пусть Сй — матрица, в которой т таких строк, что столбцы состоят из всевозможных строк длины т, за исключением строки, состоящей только из нулей. Предположим, что т > 3. Существует 2" — 1 таких строк, поэтому Слц есть (т х и)-матрица, где и = 2" — 1. Будем использовать столбцы с весом 1 как последние т столбцов, формирующих единичную матрицу, так что матрица Сй имеет вид [А')Ц, где А' — (т х (и — т))-матрица. Матрица Хемминга Сл 788 ГЛАВА 18.
Теория кодов — это ((и — г) х и)-матрица вида (г„„)А], где А — ((п — г) х т)-матрица. Код, образованный строками матрицы Хемминга, называется кодом Хемминга. Например, пусть г = 3 и Сй — матрица 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 Тогда Сн — матрица 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 1 1 Для изучения матриц Хемминга необходимо понятие расстояния и его связь с весом каждой из строк.
Начнем с теоремы о весах строк. ТЕОРЕМА 18.3. Для строк с и с' вес юг(с+ с') < юг(с) + юг(с'). ДОКАЗАТЕЛЬСТВО. Пусть с = сгсзсз... с„и с' = сЩс~... с'„. Если с, + с', = 1, то либо с, = 1, либо с, '= 1. Поэтому существованию каждой единицы в с+ с' соответствует существование единицы либо в с, либо в с'. Расстояние Хемминга, или просто расстояние между двумя строками кода с и с', имеющими одинаковую длину, — это число соответствующих битов в строке, где одна строка имеет цифру 1, а другая имеет цифру О. Будем обозначать функцию расстояния через б(с, с').
Например, если с = 101011 и с' = 110010, то б(с, с') = 3, так как две строки отличаются во второй, третьей и шестой позициях. Очевидно, что чем больше расстояние между двумя строками кода, тем больше ошибок можно обнаружить. Поскольку б названа функцией расстояния, мы должны показать, что она обладает основными свойствами функции расстояния. ТЕОРЕМА 18.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
