Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 134
Текст из файла (страница 134)
Код С называется линейным, если С— подгруппа группы В„. Если вспомнить линейную алгебру, то можно заметить, что в действительности С вЂ” линейное векторное пространство, и многие из свойств линейной алгебры могут оказаться здесь полезными. Однако, рассматривая код С, мы будем использовать здесь только те свойства, что С является группой и что элемент из С вЂ” вектор, поэтому может быть умножен на матрицу соответствующего размера. Будет использован также закон дистрибутивности для матриц, согласно которому А(В+ С) = АВ+ АС для любых матриц А, В и С, произведение которых определено. Читатель может вспомнить, что если и = (иы из, из,..., и„) и и = (иы из, из,..., и„), то скалЯРмое Т58 ГЛАВА 18.
Теория кодов произведение векторов и и о, обозначаемое и ° о, равно игОГ + и2О2+ иЗОЗ + ' ' '+ ипеп. Весом строки кода с, обозначаемым юг(с), называется количество единиц в строке. Например, если с = 1011010, то юг(с) = 4. Предположим, что имеется такая (йхп)-матрица С, что ее первые й столбцов и строк образуют единичную матрицу 1ь размера (к х й), все столбцы которой различны. Таким образом, матрица С имеет вид [1ь[Ао ь]. Например, 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 является такой матрицей. Матрица С называется порождающей магприг4ей. Рас- смотрим строки порождающей матрицы как векторы или строки кода. Обозначим это множество строк Я. Например, для матрицы, приведенной выше, Я = (100101, 0101 10, 001011). Если необходимо передать строки сообщения длины й, то мы кодируем их, УмножаЯ спРава на матРицУ С.
Таким обРазом, если ю = югюзюз юа или (юы ю2, юз,...,юь), то мы кодируем это строкой юС. В нашем примере закодируем 110 или (1,1, 0) как 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 (1,1,0) = (1,1,0,0,1,1) или 110011. Заметим, что строка сообщения совпадает с первыми тремя битами закодированной строки. В общем случае строка сообщения длины к будет Пусть С вЂ” код, образованный всеми векторами, которые являются конечными суммами строк из Я. Предлагаем читателю доказать, что С вЂ” подгруппа В„. В нашем примере получаем 110011, складывая первые две строки из Я, поэтому 110011 будет принадлежать С. Говорят, что группа С порождена множеством Я.
Это Я является также минимальным множеством, порождающим код С, поскольку никакие элементы из Я не являются суммами других элементов из Я. То, что группа С порождена множеством Я, обозначим С = Я'. Код С вида [1к[А„ ь[ (т.е. порожденный строками [1ь[Ао ь[) называется '[и й]-кодом.
ТЕОРЕМА 18.1. [и, й[-код С содержит 2ь строк. ДОКАЗАТЕЛЬСТВО. Первые й битов строки С определяют элементы С. Позиции, в которых находятся единицы в первых й битах строки из С, показывают, какие строки из Я были просуммированы. Например, если единицы находятся в первом и третьем битах строки из С, то эта строка получена в результате сложения первой и третьей строк кода С. Поскольку существует 2ь различных способов сформировать первые )с битов, то в коде С имеется 2ь строк. РКЗдЕЛ га.2.
Пороагдаюи4иа матрицы 759 совпадать с первыми к битами закодированной строки, поскольку единичная матрица 1ы образующая первые к столбцов матрицы С, просто повторяет исходную строку. Поэтому мы можем осуществлять декодирование, взяв первые 14 битов закодированной строки. Заметим также, что выше, при умножении (1,1, 0) на С, мы получили (1, 1, О, О, 1, 1) = 1 (1, О, О, 1, О, 1) + 1 (О, 1, О, 1, 1, 0) + 0 .(О, О, 1, О, 1, 1), так как для любого вектора и имеем 1 и = и и 0 и = (0,0,0,0,0,0).
Таким образом, закодированная строка является суммой векторов из множества Я и, следовательно, принадлежит С, поскольку С вЂ” группа. В общем случае, если Я = (а1,аг,зз,...,зь) — множество строк порождающей матрицы и ю = (юг,юг,юз,...,юь) — код сообщения, то закодированная строка имеет вид ю1з1 + югаг + юзаз +... + юьзь . Она представляет собой сумму строк из 5, так как каждое ю, равно либо 1, либо О и, следовательно, принадлежит С, поскольку С вЂ” группа, порожденная множеством Я.
Отметим, что С имеет вид ~1ь~А„ ь) и что 1ь передает сообщение. А что делает Ао ь? Рассмотрим тот же пример. Если (ю1,юг,юз) — строка сообщения, то закодированная строка имеет вид 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 (ю1~1и2 1из) (ю1 ~ юг~ юз, ю1 + юг~ ю2 + юз, ю1 + юз) Таким образом, четвертый бит закодированной строки должен быть равен ю1+юг, пятый бит должен быть равен юг+ юз и шестой бит должен быть равен ю1+ юз. следовательно, если закодированная строка имеет вид (юг,юг,юз, ю4,юз, юа), то ю4 = ю1 + юг, 1из = юг + юз и юа = ю1 + юз.
Если любаЯ закоДиРованнаЯ строка после передачи не удовлетворяет этим соотношениям, то понятно, что при передаче произошла ошибка. Например, если получена закодированная строка 101100, то, учитывая, что ю1 = 1, юг = 0 и юз = 1, должны иметь ю4 = 1 = 1+ О, юз = 0 = 0+ 1 и юа = 0 = 1+ 1. Поскольку соотношение для юз не выполняется, становится понятным, что имеется ошибка. Таким образом, матрица Аа ь служит для контроля точности передачи данных так же, как ранее это делал бит контроля четности. В общем случае, если имеется закодированная строка ю11о2юз юь 1 0 0 . 0 А1ь41 А1ьег . А1„ 0 1 0 .. 0 Аг,ь41 Аг,ь+г .
Аг, 0 0 1 ''.: Аз,а+1 Аз,ь+г Аз,о 0 0 0 0 0 1 Аь ье1 Аь,ь+г Ало то для 1 > к имеем ю, = ю1А1;+югА2,'+юзАз,'+' +юьАь.и и закодированная строка должна удовлетворять всем этим и — к соотношениям. 760 ГЛА8А 18. Теория кодов Следуюшая проблема — исправление ошибки, если известно, что произошла единственная ошибка. Изложенный ниже метод известен как использование лидеров смежных классов. Метод будет проиллюстрирован нашим примером, в котором 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 Известно, что я = (юо101, 01опо, 001ощ, так что С = (ОООООО, ЮОЮ1, ОЮПО, ООЮП, ПООП, ОШО1, 1ОШО, ШООО(.
Теперь, как это описано в разделе 9.4, сформируем для С смежные классы в В„. Первым смежным классом является сам С. Для формирования следуюшего смеж- ного класса выберем элемент из В„, который имеет минимальный вес и не при- надлежит С. Например, можно выбрать Ь1 = 100000. Смежный класс + с = (100000,000101, попо, 1010п,0100п, пп01, 001110, Оп0001. ь + с = (оюооо, пою1, ооопо, опоп, 1оооп, оопо1, ш по, 1оюоо) . Продолжая этот процесс, получаем следуюшую таблицу для В„, разделенного на смежные классы, где элемент с минимальным весом выписан первым. Элементы первого столбца называются лидерами смежных классов. 000000 100101 010110 001011 пооп ОП101 10П10 П1000 100000 000101 110ПО 101011 010011 ПП01 001ПО 011000 010000 001000 П 0101 000110 0110 П 10П01 ОП ПО ОООО П 1П ПО 101000 100110 ПОООО 100011 1ПОП ООП01 010101 000100 000010 100001 010010 001П1 100П1 010100 001001 ПОП1 П0001 ОП001 ОП111 101010 ППОО 10ПОО П1010 000001 100010 100100 0101П 001010 ОООП1 П0100 101001 П0010 010001 011100 ппп 101П1 П1001 ООПОО ОП010 В последнем смежном классе необходимо использовать строки веса 2.
Можно выбрать одну из строк 100010, 010001 или ООПОО. Откровенно говоря, нам повезло, что мы нашли хотя бы одну. Процесс работает следующим образом. Получив закодированную строку, ищем ее в таблице. Предположим, например, что получена строка ПОПО. Смотрим на первый столбец строки, содержашей ПОПО, и получаем 100000, поэтому предполагаем, что ошибка возникла в первом бите, Опять выбираем элемент из В„, который имеет минимальный вес и не принад- лежит ни одному из предыдущих смежных классов. Например, можно выбрать Ьз = 010000. Смежный класс РКЗДЕЛ 78.2 Порождающие мал!рицы 761 югз! + юззз + юзвз +... + юлаев, где каждое ю! равно 1 или О. Согласно свойству линейности матриц имеем г ° (югз! + юззз +...
+ юьвь) = юг(С ° з!) + юз(с ° вз) +... + юь(Г ° вь) = = О+ О+ О+... + 0 = =О. Вспомним, что в рассматриваемом примере 1 0 0 1 0 1 С = 0 1 0 1 1 0 = !1з(Аз) 0 0 1 0 1 1 Определим теперь 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 = [Аз!1з) поскольку 100000 была добавлена каждому элементу С при построении этого смежного класса. Смотрим на первую строку столбца, содержащего 110110, и получаем 010110, что, по нашему предположению, является правильной строкой кода С. Теперь предположим, что получена строка 001010. Смотрим на первый столбец строки, содержащей 001010, и получаем 000001, поэтому предполагаем, что ошибка возникла в шестом бите. Смотрим на первую строку столбца, содержащего 001010, и находим 001011, что, по нашему предположению, является правильной строкой кода С.
Теперь поищем более простой способ обнаружения ошибок. Пусть и и ю— векторы (или строки) длины н. Вектор о называется ортогональным вектору ю, если их скалярное произведение о ° ю = О. Пусть задан код С. Двойственным кодом к коду С, обозначаемым Сз-, называется множество всех строк из В„, ортогональных каждой строке из кода С. Предоставляем читателю доказать, что Сл — подгруппа группы В„. Если код С является (п,к]-кодом, так что он порожден й строками, то Сл порожден и — и строками.
Поскольку доказательство этого утверждения требует знания линейной алгебры, то доказывать его не будем, а просто примем на веру. Следующую теорему, однако, мы докажем. ТЕОРЕМА 18.2. Пусть С вЂ” групповой код, а Сл — двойственный ему код. Строка С принадлежит коду Сл тогда и только тогда, когда она ортогональна каждой строке из 5, множества порождающих элементов кода С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
