Расстояние хемминга. Большая энциклопедия нефти и газа

На множестве двоичных слов длины m расстоянием d(a,b) между словами a и b называют число несовпадающих позиций этих слов, например: расстояние между словами a = 01101 и b = 00111 равно 2.

Определенное таким образом понятие называется расстоянием Хемминга.

Оно удовлетворяет следующим аксиомам расстояний:

1) d(a,b)  0 и d(a,b)=0 тогда и только тогда, когда a = b;

2) d(a,b) = d(b,a) ;

3) d(a,b) + d(b,c)  d(a,c) (неравенство треугольника).

Весом w(a) слова a называют число единиц среди его координат. Тогда расстояние между словами a и b есть вес их суммы a b: d(a,b)=w(a b) , где символом  обозначена операция покоординатного сложения по модулю 2. Интуитивно понятно, что код тем лучше приспособлен к обнаружению и исправлению ошибок, чем больше различаются кодовые слова. Понятие расстояния Хемминга позволяет это уточнить.

Теорема Для того, чтобы код позволял обнаруживать ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было  k + 1.

Доказательство этой теоремы аналогично доказательству следующего утверждения.

Теорема. Для того, чтобы код позволял исправлять все ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было  2k + 1.

32. Теорема о корректирующей способности кодов.

Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенство 2k≥k+m+1или k≥log2(k+m+1), где m - количество основных двоичных разрядов кодового слова. В настоящее время наибольший интерес представляют двоичные блочные корректирующие коды. При использовании таких кодов информация передаётся в виде блоков одинаковой длины и каждый блок кодируется и декодируется независимо друг от друга. Почти во всех блочных кодах символы можно разделить на информационные и проверочные.

Основными характеристиками самокорректирующихся кодов являются:

1. Число разрешенных и запрещенных комбинаций. Если n - число символов в блоке, r - число проверочных символов в блоке, k - число информационных символов, то 2n - число возможных кодовых комбинаций, 2k - число разрешенных кодовых комбинаций, 2n−2k - число запрещенных комбинаций.

2. Избыточность кода. Величину rn называют избыточностью корректирующего кода.

3. Минимальное кодовое расстояние. Минимальным кодовым расстоянием d называется минимальное число искаженных символов, необходимое для перехода одной разрешенной комбинации в другую.

4. Число обнаруживаемых и исправляемых ошибок. Если g - количество ошибок, которое код способен исправить, то необходимо и достаточно, чтобы d≥2g+1

5. Корректирующие возможности кодов.

33. Матричное кодирование. Групповые коды.

При явном задании схемы кодирования в ( m, n)-коде следует указать 2 m кодовых слов, что весьма неэффективно.

Одним из экономных способов описания схемы кодирования является методика матричного кодирования.

Ранее каждая схема кодирования описывалась таблицами, задающими кодовое слово длины n для каждого исходного слова длины m. Для блоков большой длины этот способ требует большого объема памяти и поэтому непрактичен. Например, для (16, 33 )-кода потребуется 33 * 2 16 = 2 162 688 бит.

Гораздо меньшего объема памяти требует матричное кодирование. Пусть E матрица размерности m × n , состоящая из элементов e ij , где i - это номер строки, а j - номер столбца. Каждый из элементов матрицы e ij может быть либо 0, либо 1. Кодирование реализуется операцией b = аЕ или где кодовые слова рассматриваются как векторы, т.е как матрицы-строки размера 1 × n.

Кодирование не должно приписывать одно и то же кодовое слово разным исходным сообщениям. Простой способ добиться этого состоит в том, чтобы m столбцов матрицы образовывали единичную матрицу. При умножении любого вектора на единичную матрицу получается этот же самый вектор, следовательно, разным векторам-сообщениям будут соответствовать разные вектора систематического кода.

Матричные коды называют также линейными кодами. Для линейных (n − r, n )-кодов с минимальным расстоянием Хэмминга d существует нижняя граница Плоткина (Plotkin) для минимального количества контрольных разрядов r при n³ 2d − 1 ,

Двоичный ( m, n)-код называется групповым, если его кодовые слова образуют группу.

Заметим, что множество всех двоичных слов длины m образует коммутативную группу с операцией покоординатного сложения по модулю 2, в которой выполняется соотношение a a. Следовательно, множество слов-сообщений a длины m есть коммутативная группа.

Блочный код называется групповым, если его кодовые слова образуют группу.

Если код является групповым, то наименьшее расстояние между двумя кодовыми словами равно наименьшему весу ненулевого слова.

Это следует из соотношения d(b i , b j ) = w(b i + b j ).

При использовании группового кода незамеченными остаются те и только те ошибки, которые отвечают строкам ошибок, в точности равным кодовым словам.

Такие строки ошибок переводят одно кодовое слово в другое.

Следовательно, вероятность того, что ошибка останется необнаруженной, равна сумме вероятностей всех строк ошибок, равных кодовым словам.

Множество всех двоичных слов a = a 1 ... a m длины m образует абелеву (коммутативную) группу относительно поразрядного сложения.

Пусть E - кодирующая m × n -матрица, у которой есть m ×m- подматрица с отличным от нуля определителем, например, единичная. Тогда отображение a → a E переводит группу всех двоичных слов длины m в группу кодовых слов длины n.

Предположим, что Тогда для получаем

т. е.Следовательно, взаимно-однозначное отображение группы двоичных слов длины m при помощи заданной матрицы E сохраняет свойства групповой операции, что означает, что кодовые слова образуют группу.

Свойство группового кода: минимальное кодовое расстояние между кодовыми векторами равно минимальному весу ненулевых векторов. Вес кодового вектора равен числу единиц в кодовой комбинации.

Групповые коды удобно задавать при помощи матриц, размерность которых определяется параметрами k и n. Число строк равно k, а число столбцов равно n = k+m.

Коды, порождаемые этими матрицами, называются (n, k)-кодами, а соответствующие им матрицы порождающими (образующими, производящими).

Cтраница 1

Расстояние Хемминга между двумя последовательностями равной длины соответствует числу позиций, занятых несовпадающими элементами. В случае последовательностей различной длины расстояние Хэмминга определяется как минимальное число позиций, занятых несовпадающими элементами при.

Расстояние Хемминга d (u, v) между двумя словами и и v одинаковой длины равно числу несовпадающих разрядов этих слов. Оно используется в теории блочных кодов (В.

С использованием метрических свойств расстояния Хемминга непосредственно проверяется, что / л является метрикой на Хц, но не является метрикой на множестве смешанно-периодических последовательностей.

Эта функция близости эквивалентна расстоянию Хемминга.

Метрика р в алгоритме KLOP задана расстоянием Хемминга.

Если процедура поиска сможет найти положение, где расстояние Хемминга равно нулю, задача будет решена.

Сопоставление нечетких подмножеств В и В3, степеней нечеткости, а также расстояния Хемминга показывает, что рассматриваемые нечеткие подмножества отличаются. Однако если в качестве рассчитанного значения принимать элемент м2 G Uz, степень принадлежности которого полученному нечеткому подмножеству максимальна, то применение нечеткого отношения R, вычисленного таким способом, может быть оправдано. Наряду с тем, что при данном подходе удается описать нелинейность связи между максимальной температурой во второй зоне реактора и показателем текучести расплава полиэтилена, этот способ не учитывает нестационарность процесса получения ПЭВД, которая связана с изменением характеристик технологического процесса.

Передаточная функция этого кода указывает на то, что имеется единственный путь с расстоянием Хемминга d - от пути из одних нулей, который сливается с путем из одних нулей при данном узле. Из диаграммы состояний, показанной на рис. 8.2.6, или решетчатой диаграммы, показанной на рис. 8.2.5, видно, что путь с d6 это acbe. Снова из диаграммы состояний или решетки мы видим, что этими путями являются acdbe и acbcbe. Третье слагаемое в (8.1.2) указывает, что есть четыре пути с расстоянием d 0 и так далее. Таким образом, передаточная функция дает нам дистанционные свойства сверточного кода.

Этот результат согласуется с наблюдением, что путь из одних нулей (/ 0) имеет расстояние Хемминга d3 от принимаемой последовательности, в то время как путь с / 1 имеет расстояние Хемминга d5 от принимаемого пути. Таким образом, расстояние Хемминга является эквивалентной метрикой для декодирования с жестким решением.

В книге Стефана Цвейга “Звездные часы человечества” есть замечательный рассказ “Гений одной ночи” об офицере французской армии Руже де Лиле, написавшем в течение одной ночи в пылу охватившего его вдохновения знаменитую “Марсельезу”. Это было в 1792 г. в революционном Марселе. Песня в течение нескольких дней распространилась по Франции, быстро приобрела колоссальную популярность во всём мире и впоследствии стала национальным гимном Французской республики. История сохранила имя Руже в памяти потомства благодаря этой единственной песне.

По аналогии Ричарда Хэмминга можно назвать “гением одной идеи”. Он сформулировал ее в 1950 г. в своей единственной научной статье, посвящённой кодам для коррекции ошибок. Статья содержала конструкцию блочного кода, корректирующего одиночные ошибки, которые возникают при передаче сообщений.

Ричард Хэмминг постоянно вел активные научные исследования, однако знаменитой стала его единственная работа в области теории информации, составляющая по своему объему ничтожный процент его научного творчества. Эта статья быстро получила мировую известность и принесла ему заслуженную славу.

Подобно тому, как вслед за открытиями Фарадея и Максвелла последовали многочисленные изобретения в области электросвязи, изменившие нашу жизнь, так и после создания Клодом Шенноном теории информации и Владимиром Котельниковым теории потенциальной помехоустойчивости открылись новые возможности для развития телекоммуникаций. Одним из важнейших разделов теории информации является теория кодирования, основы которой были заложены Хэммингом.

Шеннон установил, что по каналу связи информация может передаваться безошибочно в том случае, если скорость передачи не превышает его пропускной способности. Однако доказательство Шеннона носило неконструктивный характер. Более поздние его исследования и другого американского ученого С. О. Райса показали, что практически любой случайно выбранный код позволяет достичь теоретического предела помехоустойчивости приёма сообщений. Однако такой код имел высокую сложность декодирования: число операций, необходимых для декодирования принятой кодовой комбинации, возрастал экспоненциально росту его длины.

Хэмминг был первым, кто предложил конструктивный метод построения кодов с избыточностью и простым декодированием. Его труд предопределил направление большинства работ в этой области, последовавших позже.

В его честь Институт инженеров по электротехнике и электронике учредил медаль, которой награждаются ученые, внесшие значительный вклад в теорию информации.

Коды, способные корректировать ошибки (в каналах связи в цифровых вычислительных машинах и т. п.) при обработке сигналов, были предложены Хэммингом еще до 1948 г., когда была опубликована знаменитая статья Шеннона “Математическая теория связи”, заложившая прочную основу теории в данной области.

В этой статье Шеннон, ссылаясь на исследование, выполненное в 1947 г. его сослуживцем по лаборатории Белла Ричардом Хэммингом, описал в качестве примера простой код длины 7, корректирующий все одиночные ошибки. Публикация же оригинального материала Хэмминга по патентным соображениям была задержана до апреля 1950-го. Следует отметить, что пример корректирующего ошибки кода, приведенный в упомянутой статье Шеннона, инициировал исследование другого американского ученого, М. Е. Голея. Голей независимо от Хэмминга открыл коды, корректирующие одиночные ошибки. В 1949 г. (т. е. раньше Хэмминга) он опубликовал короткую заметку (всего на полстраницы) о своих результатах в Трудах IЕЕE. В этой заметке он рассмотрел не только бинарные коды, но и коды общего вида, комбинации которых принадлежат конечному полю (математическому множеству элементов с определенными операциями сложения, вычитания, деления и умножения) с рn элементами (р – простое, а n – целое число).

Надо отметить, что ряд основополагающих идей теории связи был известен в качестве частных математических результатов ещё до того, как их начали применять учёные, решающие проблемы передачи сообщений по каналам связи. В своей книге “Алгебраическая теория кодирования” крупный американский специалист в области теории кодирования Э. Берлекамп сделал весьма интересное замечание. Он отметил, что конструкция кодов Хэмминга была описана в ином контексте ещё в 1942 г. известным американским математиком Р. А. Фишером, в работе посвященной теории факторного анализа (одного из разделов математической статистики) и её связи с математической теорией групп. Кстати, теорема В. А. Котельникова, указывающая на возможность представления аналоговых сигналов в цифровом виде, тоже была открыта как один из частных математических результатов теории интерполяции функции ещё в начале ХХ века английскими математиками Е. Т. и Дж. М. Уиткерами. Следует подчеркнуть, что ни Фишер, ни упомянутые английские ученые не связывали свои результаты с важнейшими для современного мира проблемами передачи информации по каналам связи.

Вольфганг Гёте говорил: “Недостаточно только получить знание; надо найти ему приложение. Недостаточно только желать; надо делать”. Для теории и техники... связи теорема Котельникова и коды Хэмминга имеют исключительное значение, поскольку именно благодаря им перед инженерами открылась ясная перспектива создания цифровых систем, которые в конце ХХ века произвели революцию в электросвязи и поэтому их с полным основанием называют именами этих учёных.

Став катализатором, ускорившим развитие теории кодирования, статья Хэмминга обратила на себя внимание научной общественности. Во всех учебниках этот класс кодов называют кодами Хэмминга и изложение теории кодирования начинают с описания их конструкции. По-видимому, всё же было бы справедливее эти коды называть кодами Хэмминга – Голея, учитывая, что Голей пришёл к тем же идеям, что и Хэмминг, независимо и опубликовал их раньше. То, что его статья не вызвала к себе должного внимания, скорее всего, является волей случая.

По сравнению с теорией Шеннона коды, введенные Хэммингом, были разочаровывающе слабы. Однако предложенные Хэммингом регулярные методы построения кодов, корректирующих ошибки, имели фундаментальное значение. Они продемонстрировали инженерам практическую возможность достижения тех пределов, на которую указывали законы теории информации. Эти коды нашли практическое применение при создании компьютерных систем. Статья Хэмминга привела также к решению проблемы более плотной упаковки для конечных полей. Он ввел в научный обиход важнейшие понятия теории кодирования – расстояние Хэмминга между кодовыми комбинациями в векторном пространстве, определяемом для двоичных кодов как количество позиций этих комбинаций с различными символами, и границы Хэмминга для исправляющей способности блочных корректирующих кодов. Граница Хэмминга для двоичных кодов рассчитывается по следующей формуле:

В этом выражении число ошибок e может быть исправлено корректирующим блочным кодом длиной N, имеющим М кодовых комбинаций (CjN – биномиальный коэффициент).

Работа Хэмминга сыграла ключевую роль в последующем развитии теории кодирования и стимулировала обширные исследования, выполненные в последующие годы. В 1956 г. Давид Слепян первым изложил теорию кодов с проверкой четности на серьезной математической основе. Главный сдвиг в области теории кодирования произошел, когда французский ученый А. Хоквингем (1959 г.) и американцы Р. К. Боуз и Д. К. Рой-Чоудхури (1960 г.) нашли большой класс кодов (коды БЧХ), исправляющих кратные ошибки. Американские исследователи И. С. Рид и Г. Соломон (1960 г.) нашли связанный с кодами БЧХ класс кодов для недвоичных каналов.

В 1980 г. Хэмминг написал блестящий учебник “Теория кодирования и теория информации”, который в 1983 г. был переведен на русский язык. Эту книгу, как и другие его труды, отличает оригинальность постановки вопросов, популярность изложения, глубокое понимание практических задач, корректность и разумная степень строгости математической трактовки затронутых вопросов. Изложение материала построено таким образом, что читателю интуитивно понятно, почему справедлива та или иная теорема

) в векторном пространстве кодовых последовательностей, в этом случае расстоянием Хэмминга между двумя двоичными последовательностями (векторами) и длины называется число позиций, в которых они различны - в такой формулировке расстояние Хэмминга вошло в Словарь алгоритмов и структур данных Национального Института Стандартов США (англ. NIST Dictionary of Algorithms and Data Structures ).

Так, расстояние Хэмминга между векторами 0 011 1 и 1 010 1 равно 2 (красным отмечены различающиеся биты). В дальнейшем метрика была обобщена на q-ичные последовательности: для пары строк «вы боры » и «за бора » расстояние Хэмминга равно трём.

В общем виде расстояние Хэмминга для объектов и размерности задаётся функцией:

Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:

Расстояние Хэмминга в биоинформатике и геномике

Литература

Richard W. Hamming . Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.
Ричард Блейхут . Теория и практика кодов, контролирующих ошибки. М., «Мир», 1986

Ссылки

Ричард Хэмминг и начало теории кодирования // Виртуальный компьютерный музей

Wikimedia Foundation . 2010 .

Смотреть что такое "Расстояние Хемминга" в других словарях:

расстояние Хемминга - хемминговское расстояние Расстояние d (u,v) между двумя кодовыми последовательноаями u и v одинаковой длины, равное числу символов, в которых они отличаются. Блочный код с минимальным хемминговским расстоянием d позволяет обнаружить (d 1) и… …

кодовое расстояние - Минимум расстояния Хемминга, взятый по всем ларам различных кодовых слов в равномерном коде. [Сборник рекомендуемых терминов. Выпуск 94. Теория передачи информации. Академия наук СССР. Комитет технической терминологии. 1979 г.] Тематики теория… … Справочник технического переводчика

В области математики и теории информации линейный код это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы… … Википедия

Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления… … Википедия