Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 136
Текст из файла (страница 136)
Функция расстояния Хемминга имеет следующие свойства: а) для строк с и с' расстояние б(с, с') = 0 тогда и только тогда, когда с = с', б) для строк с и с' расстояние б(с,с') = б(с',с); в) для строк с, с' и с" выполняется соотношение б(с,с") < б(с,с') + б(с',с"). ДОКАЗАТЕЛЬСТВО. Пункты (а) и (б) следуют непосредственно из определения, и их доказательство оставляем читателю. Для доказательства части (в) заметим, что для строк с и с" вес юг(с+ с") = б(с, с"), а также, что если с = сгсзсз... с„и с" = с",с"с"...
с'„', то с, + с," вносит 1 в вес ю1(с + с") тогда и только тогда, когда с, = 0 и с',,' = 1 или с, = 1 и с," = О. Но это верно в том и только том случае, если с; и с," различны, что вносит 1 в б(с, с"). Заметим также, что для любой строки с' строка с'+ с' состоит только из нулей. Назовем такую строку О. По определению сложения О+ с = с для каждой строки с. Следовательно, б(с, с") = юг(с + с") = ю1(с + 0 + с") = юг(с+ с + с' + с' ) < < юг(с + с') + юг(с' + с") = б(с, с') + б(с', с") . ° РАЗДЕЛ 16.3. Коды Хеммингв 769 Важно знать минимальное расстояние между двумя строками кода. Если С вЂ” код, то минимальное расстояние кода С, обозначаемое Р(С), равно наименьшему расстоянию между двумя строками из С.
В приведенной ниже теореме сформулирован важный критерий для определения числа ошибок, которые могут быть исправлены или обнаружены с использованием кода. ТЕОРЕМА 18.6. Для кода С, а) если Р(С) = й+ 1, то использование кода позволяет обнаружить вплоть до й ошибок; б) если Р(С) = 2й + 1, то использование кода позволяет исправить вплоть до (с ошибок.
ДОКАЗАТЕЛЬСТВО. (а) Если Р(С) = и+1, то для данной строки с Е С. Отсюда следует, что с отличается от любой другой строки кода по крайней мере в и+ 1 позициях. Поэтому, если переданная строка с имеет с или менее ошибок, то она не может быть другой строкой кода, и ошибка определена.
(б) Если строка с передана как с' с й нли менее ошибками, то для любой строки с Е С имеем б(с,с') < й. Если для некоторой строки с" из С расстояние б(с', с") < й, то б(с, с') + б(с', с") < 2й. Но б(с', с") < б(с, с') + б(с', с") и б(с, с") > 26+ 1, что приводит к противоречию. Следовательно, с' можно исправить на с, единственную строку, расстояние которой от с' меньше, чем й+ 1. Возникает проблема определения Р(С), наименьшего расстояния между любыми двумя строками из кода С.
Для решения задачи нам сначала потребуется следующая теорема. ТЕОРЕМА 18.6. Минимальное расстояние Р(С) кода С равно И"(С) = ппп(юг(с): сЕСисф0). ДОКАЗАТЕЛЬСТВО. По определению Р(С), существует ю,и' е С такое, что б(ю,ю') = Р(С). Но б(с,с") = юг(с+ с") и, поскольку с+ с" е С, то И'(С) < юг(с+ с"). Следовательно, И'(С) < Р(С). Обратно, для с Е С имеем юг(с) = юг(с+0) = б(с,0) > Р(С). Следовательно, И'(С) > Р(С). Отсюда И'(С) = Р(С). Покажем, что для кода Хемминга С выполняется соотношение И"(С) > 3. Прежде всего, не существует с Е С с весом 1. Если бы такая строка с существовала, то она содержала бы нули во всех позициях, за исключением позиции 1, в которой стояла бы единица; в силу ортогональности строки с к каждой строке матрицы Сй имели бы, что гчый столбец матрицы Сй содержит только О, что противоречит построению матрицы Сй.
Не существует также с е С с весом 2. Если бы такие с Е С существовали, то с была бы строкой, состоящей только из нулей, за исключением двух единиц, например, в позициях 1 и 11 Из ортогональности строки с к каждой строке матрицы Сна следует, что 1-ый и 1-ый столбцы каждой строки матрицы СД должны быть одновременно 1 или О. Но тогда 1-ый и чый столбцы матрицы Сй должны совпадать, что опять же противоречит построению матрицы С~~.
Следовательно, Иг(С) > 3, и код С можно использовать для исправления единственной ошибки. 770 ГЛАВА 18. Теория кодов Теперь необходимо показать, что в каждом смежном классе, за исключением самого С, имеется один элемент с весом 1. Доказательство этого факта значительно упростит проблему декодирования. По теореме 18.1, [и, к[-код С содержит 2" строк.
Поскольку Сн имеет вид [1„ „[А[, то код Хемминга С является (и, и — г[-кодом, поэтому код С содержит 2" " элементов. Множество В„содержит 2" элементов. Следовательно, сушествует 2" — = 2" 2л-г юг(о) < юФ(з) + ыФ(з') < 1 + 1 = 2 Но цч(с) > 3, что противоречит полученному. Поэтому каждый смежный класс содержит ровно одну строку с весом 1, за исключением С, который содержит строку с весом О. Вернемся к нашему примеру, в котором матрица С~ь имеет вид 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 Учитывая, что каждый смежный класс содержит лидера с весом 1, рассмотрим строку 0010000.
Если умножить ее на матрицу Сй, получим 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 '1 0 1, что совпадает с третьим столбцом матрицы С"г. 1 поэтому синдром равен По сути, если 1 встречается в 7'-ой позиции строки с весом 1, то синдром после умножения матрицы Сг~г на транспозицию строки становится ~-ым столбцом смежных классов, включая С. Строка из С имеет длину 2" — 1. Поэтому сушествует 2" — 1 строк с весом 1. Теперь нужно показать, что никакой смежный класс не содержит две строки с весом 1. Предположим, что строки з и з' принадлежат одному смежному классу, и каждая из них имеет вес 1.
Тогда, согласно определению смежного класса, з = з'+ с для некоторой строки с а С. Следовательно, с = з+ з', поэтому, по теореме 18.3, РАДЕЛ 18.3. Коды лемминга 771 матрицы Сй. Поэтому всякий раз, когда мы получаем правильную строку переданного сообщения, умножаем на ее транспозицию матрицу Сн~, то получаем синдром со всеми нулями. Если имеется единственная ошибка, то мы получим один из столбцов матрицы Сй, поскольку строка переданного сообщения должна быть в одном из смежных классов, поэтому существует лидер смежного класса с весом 1. Следовательно, если 1-ый столбец матрицы Сн~ является синдромом, это говорит о том, что лидер смежного класса имеет 1 в 1-ом столбце, поэтому ошибка имеется в 1-ом столбце или в 1-ом бите строки.
Например, предположим, получена строка 1110110 переданного сообщения. Умножение матрицы С" на транспозицию этой строки дает 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 что совпадает со второй строкой матрицы Сн~. Следовательно, ошибка во втором бите, и переданным сообщением должна быть строка 1010110. Оставшуюся часть этого раздела посвятим небольшому обзору других кодов.
Первый из них — код Голе. Коды Хемминга были открыты независимо Хеммингом в 1950 г. и Голе в 1949г. Не будем пытаться объяснить, почему они названы именно кодами Хемминга. Это длинная и запутанная история, о которой подробно можно прочитать у Томпсона (112]. Тем не менее, существует и код Голе. Он был описан в работе Голе в 1949 г.
Речь идет о разработанной им модели (23, 12, 7), где цифры означают, что используется порождающая матрица размерности (23,12) с минимальным расстоянием 7 между строками кода С. Этот код Голе имеет порождающую матрицу С = (Ты~А), где Эта матрица имеет геометрическую интерпретацию с использованием пяти прямых в плоскости (см. [112)). Код легче изучить, используя расширенную поро- 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 1 0 О 1 1 0 1 1 1 1 1 1 1 772 ГПАВА т8, теория «одое ждающую матрицу С = ]багз]А] с параметрами (24,12,8), где (см.
]44]). Матрица получена путем перестановок в порождающей матрице Голе и добавления бита четности. Симметричность матрицы упрощает ее изучение. Легко видеть, что С~- = [А]1гг], поскольку А = А'. Голе ввел еще несколько кодов, среди которых (4096,244,8)-код, использованный космическим кораблем "Ноуадег" для передачи изображений планет Юпитер, Уран и Нептун. Для заданной строки а длины и положим з = з+1, где 1 — строка длины п, состоящая только из единиц. Для заданной строки Я положим Р!о!(Я) = (зз: з е Я) с! (за: з е Я). Для заданного множества Я = (0000, 0011, 1100, 1111) положим: 81 = Р!от(Б), Яг = Р(от(51), оз = Р!от(Бг) и Я„= Р!ог($1).
Конструкция Р!о! названа в честь разработавшего ее М. Плоткина (см. ]88]). Коды, порождаемые множествами Яы Яг, Яз, ..., называются кодами Рида-Мюллера. Множество Яз — это (64,32,16)-код, который использовался для исправления ошибок на изображении, переданном космическим кораблем "Мампег 9". В частности, матрицу Рида-Мюллера часто называют матрицей Адамара, определение которой будет дано ниже. Рассмотрим матрицы, определенные рекурсивно следующим образом; А! = ]0]; Аго= А" А" где матрица А„определена соотношением А; = А, для 1 < !, г < п.
Следовательно, 4г= 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 О 1 1 0 0 0 1 РАЗДЕЛ 18.3. Коды Хвммингв 773 оооо 010 о о 0110 А,= [ ° УПРАЖНЕНИЯ 1. Пусть С~~ — матрица 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 0 1 Найдите Сн. 2. Пусть С~и — матрица Найдите матрицу Сн. 3. Найдите расстояние между строками 110010101 и 010101111.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
