минимальное кодовое расстояние кода хэмминга

Подсчет расстояния Хэмминга на большом наборе данных

Введение

Расстояние Хэмминга — это количество различающихся позиций для строк с одинаковой длинной. Например, HD( 100, 001 ) = 2.

Впервые проблема подсчета расстояния Хэмминга была поставлена Minsky и Papert в 1969 году [1], где задача сводилась к поиску всех строк из базы данных, которые находятся в пределах заданного расстояния Хэмминга к запрашиваемой.

Подобная задача является необычайно простой, но поиск ее эффективного решения до сих пор остается на повестке дня.

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

Например, Manku и сотоварищи предложили решение проблемы кластеризации дубликатов при индексации веб документов на основе подсчета расстояния Хэмминга [2].
Также Miller и друзья предложили концепцию поиска песен по заданному аудио фрагменту [3], [4].
Подобные решения были использованы и для задачи поиска изображений и распознавание сетчатки [5], [6] и т.д.

Описание проблемы

Имеется база данных бинарных строк T, размером n, где длина каждой строки m. Запрашиваемая строка a и требуемое расстояние Хэмминга k.

Задача сводится к поиску всех строк, которые находятся в пределах расстояния k.

В оригинальной концепции алгоритма рассматривается два варианта задачи: статическая и динамическая.

— В статической задачи расстояние k предопределено заранее.
— В динамической, наоборот, требуемое расстояние заранее неизвестно.

В статье описывается решение только статической задачи.

Описание алгоритма HEngine для статической задачи

Данная реализация фокусируется на поиске строк в пределах k = ⌊k/2⌋ + 1
обязательно найдется, по крайней мере, q= r − ⌊k/2⌋ подстрок, когда их расстояние не будет превышать единицу, HD( ai, bi ) = ⌊k/2⌋ + 1

Длина первых r − (m mod r) подстрок будет иметь длину ⌊m / r⌋, а последние m mod r подстроки ⌈m/r⌉. Где m — это длина строки, ⌊ — округление до ближайшего снизу, а ⌉ округление до ближайшего сверху.

Теперь тоже самое, только на примере:

Даны две бинарные строки длиной m = 8 бит: A = 11110000 и B = 11010001, расстояние между ними k = 2.
Выбираем фактор сегментации r = 2 / 2 + 1 = 2, т. е. всего будет 2 подстроки длиной m/r = 4 бита.

a1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Если мы сейчас подсчитаем расстояние между соответствующими подстроками, то, по крайней мере, (q = 2 — 2/2 = 1) одна подстрока совпадет или их расстояние не будет превышать единицу.

Что и видим:
HD( a1, b1 ) = HD( 1111, 1101 ) = 1
и
HD( a2, b2 ) = HD( 0000, 0001 ) = 1

Подстроки базовой строки были названы сигнатурами.
Сигнатуры или подстроки a1 и b1 (a2 и b2, a3 и b3 …, ar и br) называются совместимыми с друг другом, а если их количество отличающихся битов не больше единицы, то эти сигнатуры называются совпадающими.

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

Предварительная обработка базы данных

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

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

Но как производить поиск по подстрокам?

Метод двоичного поиска должен неплохо с этим справляться. Но он требует, чтобы список строк был отсортирован. Но у нас получается несколько подстрок из одной строки. Что бы произвести двоичный поиск по списку подстрок, надо чтобы каждый такой список был отсортирован заранее.
Поэтому здесь напрашивается метод расширения базы данных, т. е. созданию нескольких таблиц, каждая для своей подстроки или сигнатуры. (Такая таблица называется таблицей сигнатур. А совокупность таких таблиц — набор сигнатур).

В оригинальной версии алгоритма еще описывается перестановка подстрок таким образом, чтобы выбранные подстроки были на первом месте. Это делается больше для удобства реализации и для дальнейших оптимизаций алгоритма:

Имеется строка A, которая делится на 3 подстроки, a1, a2, a3, полный список перестановок будет соответственно:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Затем эти таблицы сигнатур сортируются.

Реализация поиска

На этом этапе, после предварительной обработки базы данных мы имеем несколько копий отсортированных таблиц, каждая для своей подстроки.

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

Так же нам известно, что необходимые подстроки отличаются максимум на один элемент. И чтобы найти их потребуется воспользоваться методом расширения запроса (query expansion).

Другими словами требуется для выбранной подстроки сгенерировать все комбинации включая саму эту подстроку, при которых различие будет максимум на один элемент. Количество таких комбинаций будет равна длине подстроки + 1.

А дальше производить двоичный поиск в соответствующей таблице сигнатур на полное совпадение.

Такие действия надо произвести для всех подстрок и для всех таблиц.

И в самом конце потребуется отфильтровать те строки, которые не вмещаются в заданный предел расстояния Хэмминга. Т.е. произвести линейный поиск по найденным строкам и оставить только те строки, которые отвечают условию HD( a, b ) 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Сортируем таблицы. Каждую в отдельности.
Т1
0011 => 00111110
1000 => 10000001
1111 => 11111111

Т2
0001 => 10000001
1110 => 00111110
1111=> 11111111

На этом предварительная обработка закончена. И приступаем к поиску.

1. Получаем сигнатуры запрашиваемой строки.
Искомая строка 10111110 разбивается на сигнатуры. Получается 1011 и 1100, соответственно первая для первой таблицы, а вторая для второй.

2. Генерируем все комбинации отличающихся на единицу.
Количество вариантов будет 5.

2.1 Для первой подстроки 1011:
1011
0011
1111
1001
1010

2.2 Для второй подстроки 1100:
1100
0100
1000
1110
1101

3.1 Для всех сгенерированных вариантов первой подстроки 1011 производим двоичный поиск в первой таблице на полное совпадение.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

Найдено две подстроки.

3.2 Теперь для всех вариантов второй подстроки 1100 производим двоичный поиск во второй таблице.

1100
0100
1000
1110 == 1110 => 00111110
1101

Найдена одна подстрока.

4. Объедением результаты в один список:
00111110
11111111

5. Линейно проверяем на соответствие и отфильтровываем неподходящие по условию

Источник

Помехоустойчивое кодирование. Часть 1: код Хэмминга

Код Хэмминга – не цель этой статьи. Я лишь хочу на его примере познакомить вас с самими принципами кодирования. Но здесь не будет строгих определений, математических формулировок и т.д. Эта просто неплохой трамплин для понимания более сложных блочных кодов.

Самый, пожалуй, известный код Хэмминга (7,4). Что значат эти цифры? Вторая – число бит информационного слова — то, что мы хотим передать в целости и сохранности. А первое – размер кодового слова: информация удобренная избыточностью. Кстати термины «информационное слово» и «кодовое слово», употребляются во всех 7-ми книгах по теории помехоустойчивого кодирования, которые мне довелось бегло пролистать.

Такой код исправляет 1 ошибку. И не важно где она возникла. Избыточность несёт в себе 3 бита информации, этого достаточно, чтобы указать на одно из 7 положений ошибки или показать, что её нет. То есть ровно 8 вариантов ответов мы ждём. А 8 = 2^3, вот как всё совпало.

Чтобы получить кодовое слово, нужно информационное слово представить в виде полинома и умножить его на порождающий полином g(x). Любое число, переведя в двоичный вид, можно представить в виде полинома. Это может показаться странным и у не подготовленного читателя сразу встаёт только один вопрос «да зачем же так усложнять?». Уверяю вас, он отпадёт сам собой, когда мы получим первые результаты.

К примеру информационное слово 1010, значение каждого его разряда это коэффициент в полиноме:

Во многих книгах пишут наоборот x+x^3. Не поддавайтесь на провокацию, это вносит только путаницу, ведь в записи числа 2-ичного, 16-ричного, младшие разряды идут справа, и сдвиги мы делаем влево/вправо ориентируясь на это. А теперь давайте умножим этот полином на порождающий полином. Порождающий полином специально для Хэмминга (7,4), встречайте: g(x)=x^3+x+1. Откуда он взялся? Ну пока считайте что он дан человечеству свыше, богами (объясню позже).

Если нужно складывать коэффициенты, то делаем по модулю 2: операция сложения заменяется на логическое исключающее или (XOR), то есть x^4+x^4=0. И в конечном итоге результат перемножения как видите из 4х членов. В двоичном виде это 1001110. Итак, получили кодовое слово, которое будем передавать на сторону по зашумлённому каналу. Замете, что перемножив информационное слово (1010) на порождающий полином (1011) как обычные числа – получим другой результат 1101110. Этого нам не надо, требуется именно «полиномиальное» перемножение. Программная реализация такого умножения очень простая. Нам потребуется 2 операции XOR и 2 сдвига влево (1й из которых на один разряд, второй на два, в соответствии с g(x)=1011):

Давайте теперь специально внесём ошибку в полученное кодовое слово. Например в 3-й разряд. Получиться повреждённое слово: 1000110.

Как расшифровать сообщение и исправить ошибку? Разумеется надо «полиномиально» разделить кодовое слово на g(x). Тут я уже не буду писать иксы. Помните что вычитание по модулю 2 — это то же самое что сложение, что в свою очередь, тоже самое что исключающее или. Поехали:

Нацело разделить не получилось, значит у нас есть ошибка (ну конечно же). Результат деления в таком случае нам без надобности. Остаток от деления является синдром, его размер равен размеру избыточности, поэтому мы дописали там ноль. В данном случае содержание синдрома нам никак не помогает найти местоположение повреждения. А жаль. Но если мы возьмём любое другое информационное слово, к примеру 1100. Точно так же перемножим его на g(x), получим 1110100, внесём ошибку в тот же самый разряд 1111100. Разделим на g(x) и получим в остатке тот же самый синдром 011. И я гарантирую вам, что к такому синдрому мы придём в обще для всех кодовых слов с ошибкой в 3-м разряде. Вывод напрашивается сам собой: можно составить таблицу синдромов для всех 7 ошибок, делая каждую из них специально и считая синдром.

В результате собираем список синдромов, и то на какую болезнь он указывает:

Теперь у нас всё есть. Нашли синдром, исправили ошибку, ещё раз поделили в данном случае 1001110 на 1011 и получили в частном наше долгожданное информационное слово 1010. В остатке после исправления уже будет 000. Таблица синдромов имеет право на жизнь в случае маленьких кодов. Но для кодов, исправляющих несколько ошибок – там список синдромов разрастается как чума. Поэтому рассмотрим метод «вылавливания ошибок» не имея на руках таблицы.

Внимательный читатель заметит, что первые 3 синдрома вполне однозначно указывают на положение ошибки. Это касается только тех синдромов, где одна единица. Кол-во единиц в синдроме называют его «весом». Опять вернёмся к злосчастной ошибке в 3м разряде. Там, как вы помните был синдром 011, его вес 2, нам не повезло. Сделаем финт ушами — циклический сдвиг кодового слова вправо. Остаток от деления 0100011 / 1011 будет равен 100, это «хороший синдром», указывает что ошибка во втором разряде. Но поскольку мы сделали один сдвиг, значит и ошибка сдвинулась на 1. Вот собственно и вся хитрость. Даже в случае жуткого невезения, когда ошибка в 6м разряде, вы, обливаясь потом, после 3 мучительных делений, но всё таки находите ошибку – это победа, лишь потому, что вы не использовали таблицу синдромов.

А как насчёт других кодов Хэмминга? Я бы сказал кодов Хэмминга бесконечное множество: (7,4), (15,11), (31,26),… (2^m-1, 2^m-1-m). Размер избыточности – m. Все они исправляют 1 ошибку, с ростом информационного слова растёт избыточность. Помехоустойчивость слабеет, но в случае слабых помех код весьма экономный. Ну ладно, а как мне найти порождающую функцию например для (15,11)? Резонный вопрос. Есть теорема, гласящая: порождающий многочлен циклического кода g(x) делит (x^n+1) без остатка. Где n – нашем случае размер кодового слова. Кроме того порождающий полином должен быть простым (делиться только на 1 и на самого себя без остатка), а его степень равна размеру избыточности. Можно показать, что для Хэмминга (7,4):

Этот код имеет целых 2 порождающих полинома. Не будет ошибкой использовать любой из них. Для остальных «хэммингов» используйте вот эту таблицу примитивных полиномов:

Соответственно для (15,11) порождающий многочлен g(x)=x^4+x+1. Ну а теперь переходим к десерту – к матрицам. С этого обычно начинают, но мы этим закончим. Для начала преобразую g(x) в матрицу, на которую можно умножить информационное слово, получив кодовое слово. Если g = 1011, то:

Называют её «порождающей матрицей». Дадим обозначение информационному слову d = 1010, а кодовое обозначим k, тогда:

Это довольно изящная формулировка. По быстродействию ещё быстрее, чем перемножение полиномов. Там нужно было делать сдвиги, а тут уже всё сдвинуто. Вектор d указывает нам: какие строки брать в расчёт. Самая нижняя строка матрицы – нулевая, строки нумеруются снизу вверх. Да, да, всё потому что младшие разряды располагаются справа и от этого никуда не деться. Так как d=1010, то я беру 1ю и 3ю строки, произвожу над ними операцию XOR и вуаля. Но это ещё не всё, приготовьтесь удивляться, существует ещё проверочная матрица H. Теперь перемножением вектора на матрицу мы можем получить синдром и никаких делений полиномов делать не надо.

Посмотрите на проверочную матрицу и на список синдромов, который получили выше. Это ответ на вопрос откуда берётся эта матрица. Здесь я как обычно подпортил кодовое слово в 3м разряде, и получил тот самый синдром. Поскольку сама матрица – это и есть список синдромов, то мы тут же находим положение ошибки. Но в кодах, исправляющие несколько ошибок, такой метод не прокатит. Придётся вылавливать ошибки по методу, описанному выше.

Чтобы лучше понять саму природу исправления ошибок, сгенерируем в обще все 16 кодовых слов, ведь информационное слово состоит всего из 4х бит:

Посмотрите внимательно на кодовые слова, все они, отличаются друг от друга хотя бы на 3 бита. К примеру возьмёте слово 1011000, измените в нём любой бит, скажем первый, получиться 1011010. Вы не найдёте более на него похожего слова, чем 1011000. Как видите для формирования кодового слова не обязательно производить вычисления, достаточно иметь эту таблицу в памяти, если она мала. Показанное различие в 3 бита — называется минимальное «хэммингово расстояние», оно является характеристикой блокового кода, по нему судят сколько ошибок можно исправить, а именно (d-1)/2. В более общем виде код Хэмминга можно записать так (7,4,3). Отмечу только, что Хэммингово расстояние не является разностью между размерами кодового и информационного слов. Код Голея (23,12,7) исправляет 3 ошибки. Код (48, 36, 5) использовался в сотовой связи с временным разделением каналов (стандарт IS-54). Для кодов Рида-Соломона применима та же запись, но это уже недвоичные коды.

Список используемой литературы:

1. М. Вернер. Основы кодирования (Мир программирования) — 2004
2. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования (Мир связи) — 2006
3. Р. Блейхут. Теория и практика кодов, контролирующих ошибки — 1986

Источник

Вес и расстояние Хемминга. Способность кодов обнаруживать и исправлять ошибки

Поскольку

В дальнейшем мы еще вернемся к подробному рассмотрению вопросов оптимального приема сигналов и покажем, как определяется вид функции правдоподобия, сейчас же можно сказать, что значение P (U_k / S) будет масимально, если минимальна величина

если принятый сигнал дискретизован и S_i – i-й отсчет принятого сигнала.

Сумма квадратов разностей между значениями принятого сигнала S_i и символами k-го кодового слова называется невязкой, или евклидовым расстоянием между этим кодовым словом и принятым сигналом.

Если помех в канале связи нет или они невелики, то при передаче l-го кодового слова принятый сигнал S будет совпадать с этим кодовым словом или незначительно отличаться от него. Тогда невязка будет равна нулю или минимальна именно для l = k.

Структурная схема декодера максимального правдоподобия, реализующего правило декодирования (3.33) – (3.34), приведена на рис. 3.8.

Рассмотренный нами оптимальный декодер является так называемым мягким декодером, поскольку он выносит решения относительно U_l непосредственно на основе принятого сигнала.

На практике чаще применяется так называемое жесткое декодирование, когда в приемнике сначала принимается решение относительно значения символов принятой последовательности, а уже затем – относительно значения кодового слова.

В этом случае оптимальный декодер (жесткий декодер максимального правдоподобия) должен вычислить расстояния

между принятой последовательностью r и всеми возможными кодовыми словами U_k данного кода и принять решение в пользу кодового слова, в минимальной степени отличающегося от принятой последовательности.

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

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

Число единиц (ненулевых компонент) в этой последовательности называется весом Хемминга вектора U и обозначается w(U).

Например, вес Хемминга вектора U = ( 1001011 ) равен четырем, для вектора U = ( 1111111 ) величина w(U) составит 7 и т.д.

Таким образом, чем больше единиц в двоичной последовательности, тем больше ее вес Хемминга.

Далее, пусть U и V будут двоичными последовательностями длиной n.

Число разрядов, в которых эти последовательности различаются, называется расстоянием Хемминга между U и V и обозначается d( U, V).

Например, если U = ( 1001011 ), а V = ( 0100011 ), то d( U, V) = 3.

Задав линейный код, то есть определив все 2 k его кодовых слов, можно вычислить расстояние между всеми возможными парами кодовых слов. Минимальное из них называется минимальным кодовым расстоянием кода и обозначается d_min.

Можно проверить и убедиться, что минимальное кодовое расстояние для рассматриваемого нами в примерах (7,4)-кода равно трем: d_min(7,4) = 3. Для этого нужно записать все кодовые слова (7,4)-кода Хемминга (всего 16 слов), вычислить расстояния между их всеми парами и взять наименьшее значение. Однако можно определить d_min блочного кода и более простым способом.

Если при передаче кодового слова по каналу связи в нем произошла одиночная ошибка, то расстояние Хемминга между переданным словом U и принятым вектором r будет равно единице. Если при этом одно кодовое слово не перешло в другое (а при d_min > 1 и при одиночной ошибке это невозможно), то ошибка будет обнаружена при декодировании.

Но ошибки могут иметь кратность и большую, чем d_min— 1, и тогда они останутся необнаруженными.

При этом среднюю вероятность необнаруживаемой ошибки можно определить следующим образом.

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

А теперь определим, что такое необнаруживаемая ошибка. Обнаружение ошибки производится путем вычисления синдрома принятой последовательности. Если принятая последовательность не является кодовым словом ( тогда синдром не равен нулю), то считается, что ошибка есть. Если же синдром равен нулю, то полагаем, что ошибки нет (принятая последовательность является кодовым словом). Но тем ли, которое передавалось? Или же в результате действия ошибок переданное кодовое слово перешло в другое кодовое слово данного кода:

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

Тогда полная вероятность возникновения необнаруживаемой ошибки

. (3.40)

Пример: рассматриваемый нами (7,4)-код содержит по семь кодовых слов с весами w = 3 и w = 4 и одно кодовое слово с весом w = 7, тогда

(3.41)

Другими словами, если по каналу передается информация со скоростью V = 1кбит/с и в канале в среднем каждую секунду будет происходить искажение одного символа, то в среднем семь принятых слов на 10 9 переданных будут проходить через декодер без обнаружения ошибки (одна необнаруживаемая ошибка за 270 часов).

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

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

Рис. 3.9

Предположим, передано кодовое слово U, в канале произошла одиночная ошибка и принят вектор а (не принадлежащий коду).

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

Таковым в данном случае будет U, следовательно, ошибка будет устранена.

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

Тогда при декодировании по максимуму правдоподобия в качестве оценки будет выбрано ближайшее к b кодовое слово, и им будет V. Произойдет ошибка декодирования.

Продолжив рассуждения для d_min = 4, d_min = 5 и т.д., нетрудно сделать вывод, что ошибки будут устранены, если их кратность l не превышает величины

Р₃ = Р 3 _ош(1- Р_ош) n-3 и т.д. (3.46)

Декодер, как мы показали, исправляет все ошибки, кратность которых не превышает

, (3.47)

то есть все ошибки кратности J £ l будут исправлены.

. (3.48)

Для (7,4)-кода Хемминга минимальное расстояние d_min = 3, т.е. l = 1. Следовательно, ошибки кратности 2 и более исправлены не будут и

. (3.49)

Если Р_ош 3 _ош 2 _ош. Тогда

. (3.50)

Таким образом, выигрыш от помехоустойчивого кодирования (который можно определить как отношение числа ошибок в канале к числу оставшихся неисправленными ошибок) существенно зависит от свойств канала связи.

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

Другими словами, помехоустойчивое кодирование существенно улучшает свойства хороших каналов, в плохих же каналах оно большого эффекта не дает.

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник