Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Примеры расстояния Хэмминга 3-битного двоичного куба
Два примера расстояний: 100 → 011 имеет расстояние 3; 010 → 111 имеет расстояние 2
Минимальное расстояние между любыми двумя вершинами - это расстояние Хэмминга между двумя двоичными строками.
4-битный двоичный тессеракт
4-битный двоичный тессеракт для определения расстояния Хэмминга.
Примеры расстояния Хэмминга 4-битного двоичного тессеракта
Два примера расстояний: 0100 → 1001 имеет расстояние 3; 0110 → 1110 имеет расстояние 1

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

Основное приложение - теория кодирования , в частности, блочные коды , в которых строки одинаковой длины являются векторами над конечным полем .

Определение [ править ]

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

Примеры [ править ]

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

  • « Ка рол в » и « ка Чет в » является 3.
  • « k a r ol in » и « k e r st in » равны 3.
  • « k athr in » и « k erst in » - 4.
  • 10 1 1 1 01 и 10 0 1 0 01 равно 2.
  • 2 17 3 8 96 и 2 23 3 7 96 равно 3.

Свойства [ править ]

Для фиксированной длины n расстояние Хэмминга является метрикой на множестве слов длины n (также известное как пространство Хэмминга ), поскольку оно удовлетворяет условиям неотрицательности, симметрии, расстояние Хэмминга двух слов равно 0 тогда и только тогда, когда два слова идентичны, и это также удовлетворяет неравенству треугольника : [2] Действительно, если мы зафиксируем три слова a , b и c , то всякий раз, когда есть разница между i- й буквой a и i- я буква c, тогда должна быть разница между i- й буквой a и i- й буквой b , или между i- й буквой b и i- й буквой c . Следовательно, расстояние Хэмминга между a и c не больше суммы расстояний Хэмминга между a и b и между b и c . Расстояние Хэмминга между двумя словами через и Ь также можно рассматривать как вес Хэмминга из в - бпри соответствующем выборе оператора -, так же как разницу между двумя целыми числами можно рассматривать как расстояние от нуля на числовой строке. [ требуется разъяснение ]

Для двоичных строк и б расстояние Хэмминга равно числу единиц ( количества населения ) в виде XOR б . [3] Метрическое пространство двоичных строк длиной n с расстоянием Хэмминга известно как куб Хэмминга ; как метрическое пространство оно эквивалентно множеству расстояний между вершинами в графе гиперкуба . Можно также рассматривать двоичную строку длины n как вектор в , рассматривая каждый символ в строке как действительную координату; с этим вложением струны образуют вершины n- мерного гиперкуба , а расстояние Хэмминга струн эквивалентно манхэттенскому расстоянию между вершинами.

Обнаружение и исправление ошибок [ править ]

Минимальное расстояние Хэмминга используется для определения некоторых существенных понятий в теории кодирования , такие как ошибки обнаружения и коды с исправлением ошибок . В частности, код C называется обнаруживающим k ошибок тогда и только тогда, когда минимальное расстояние Хэмминга между любыми двумя его кодовыми словами составляет не менее k +1. [2]

Например, рассмотрим код, состоящий из двух кодовых слов «000» и «111». Расстояние Хэмминга между этими двумя словами равно 3, и, следовательно, это k = 2 обнаружения ошибок. Это означает, что если один или два бита перевернуты, ошибка может быть обнаружена. Если три бита перевернуты, то «000» становится «111», и ошибка не может быть обнаружена.

Код C называется исправляющим k ошибок, если для каждого слова w в базовом пространстве Хэмминга H существует не более одного кодового слова c (из C ) такое, что расстояние Хэмминга между w и c не превышает k . Другими словами, код исправляет k- ошибки тогда и только тогда, когда минимальное расстояние Хэмминга между любыми двумя его кодовыми словами составляет по крайней мере 2 k +1. Это легче понять геометрически, поскольку любые замкнутые шары радиуса k с центрами на различных кодовых словах не пересекаются. [2]В этом контексте эти шары также называют сферами Хэмминга . [4]

Например, рассмотрим один и тот же 3-битовый код, состоящий из двух кодовых слов «000» и «111». Пространство Хэмминга состоит из 8 слов 000, 001, 010, 011, 100, 101, 110 и 111. Кодовое слово «000» и слова однобитовой ошибки «001», «010», «100» меньше или равно расстоянию Хэмминга от 1 до «000». Аналогично, кодовое слово «111» и его слова с одиночной битовой ошибкой «110», «101» и «011» находятся в пределах 1 расстояния Хэмминга от исходного «111». В этом коде ошибка на один бит всегда находится в пределах 1 расстояния Хэмминга от исходных кодов, и код может быть исправляющим на 1 ошибку , то есть k = 1 . Минимальное расстояние Хэмминга между «000» и «111» равно 3,что удовлетворяет 2k + 1 = 3 .

Таким образом, код с минимальным расстоянием Хэмминга d между своими кодовыми словами может обнаруживать не более d -1 ошибок и может исправлять ошибки ⌊ ( d -1) / 2⌋. [2] Последнее число также называется радиусом упаковки или способностью кода исправлять ошибки . [4]

История и приложения [ править ]

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

Он используется в телекоммуникациях для подсчета количества перевернутых битов в двоичном слове фиксированной длины в качестве оценки ошибки, и поэтому иногда его называют расстоянием до сигнала . [6] Для q- мерных строк в алфавите размера q  ≥ 2 расстояние Хэмминга применяется в случае q-арного симметричного канала , в то время как расстояние Ли используется для фазовой манипуляции или, в более общем смысле, каналов, подверженных ошибкам синхронизации. потому что расстояние Ли учитывает ошибки ± 1. [7] Если илиоба расстояния совпадают, потому что любая пара элементов от или отличается на 1, но расстояния разные для больших .

Расстояние Хэмминга также используется в систематике как мера генетического расстояния. [8]

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

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

Пример алгоритма [ править ]

Следующая функция, написанная на Python 3, возвращает расстояние Хэмминга между двумя строками:

def  hamming_distance ( string1 ,  string2 ): dist_counter  =  0 для  n  в  диапазоне ( len ( string1 )): if  string1 [ n ]  ! =  string2 [ n ]: dist_counter  + =  1 return  dist_counter

Или, короче:

sum ( xi  ! =  yi  для  xi ,  yi  в  zip ( x ,  y ))

Функция hamming_distance(), реализованная в Python 2.3+ , вычисляет расстояние Хэмминга между двумя строками (или другими повторяемыми объектами) равной длины, создавая последовательность логических значений, указывающих несоответствия и совпадения между соответствующими позициями в двух входах, а затем суммируя последовательность с False. и Истинные значения интерпретируются как ноль и единица.

def  hamming_distance ( s1 ,  s2 )  ->  int :  "" "Возвращает расстояние Хэмминга между последовательностями одинаковой длины." ""  if  len ( s1 )  ! =  len ( s2 ):  raise  ValueError ( "Не определено для последовательностей неравной длины. " )  вернуть  сумму ( el1  ! =  el2  для  el1 ,  el2  в  zip ( s1 ,  s2 ))

где функция zip () объединяет две коллекции одинаковой длины попарно.

Следующая функция C будет вычислять расстояние Хэмминга двух целых чисел (рассматриваемых как двоичные значения, то есть как последовательности битов). Время выполнения этой процедуры пропорционально расстоянию Хэмминга, а не количеству битов на входах. Он вычисляет поразрядное исключающее или двух входов, а затем находит вес Хэмминга результата (количество ненулевых битов), используя алгоритм Вегнера (1960), который неоднократно находит и очищает ненулевой бит младшего порядка. Некоторые компиляторы поддерживают функцию __builtin_popcount, которая может вычислить это, используя специализированное аппаратное обеспечение процессора, если оно доступно.

int  hamming_distance ( без знака  x ,  без знака  y ) {  int  dist  =  0 ; // Операторы ^ устанавливают в 1 только те биты, которые отличаются  для  ( unsigned  val  =  x  ^  y ;  val  >  0 ;  ++ dist )  {  // Затем мы подсчитываем бит, установленный в 1, используя метод Питера Вегнера  val  =  val  &  ( val  -  1 );  // Обнуляем самый низкий порядок val 1  } // Возвращаем количество различающихся битов  return  dist ; }

Более быстрой альтернативой является использование инструкции по сборке подсчета населения ( popcount ). Некоторые компиляторы, такие как GCC и Clang, делают его доступным через встроенную функцию:

// Расстояние Хэмминга для 32-битных целых чисел int  hamming_distance32 ( unsigned  int  x ,  unsigned  int  y ) {  return  __builtin_popcount ( x  ^  y ); }// Расстояние Хэмминга для 64-битных целых чисел int  hamming_distance64 ( unsigned  long  long  x ,  unsigned  long  long  y ) {  return  __builtin_popcountll ( x  ^  y ); }

См. Также [ править ]

  • Ближайшая строка
  • Расстояние Дамерау – Левенштейна
  • Евклидово расстояние
  • Проблема Гэпа-Хэмминга
  • Код Грея
  • Индекс Жаккара
  • Расстояние Левенштейна
  • Расстояние Махаланобиса
  • Мангеймское расстояние
  • Индекс сходства Соренсена
  • Редкая распределенная память
  • Лестница слов

Ссылки [ править ]

  1. ^ Waggener, Билл (1995). Методы импульсной кодовой модуляции . Springer. п. 206. ISBN. 9780442014360. Проверено 13 июня 2020 .
  2. ^ a b c d Робинсон, Дерек Дж. С. (2003). Введение в абстрактную алгебру . Вальтер де Грюйтер . С. 255–257. ISBN 978-3-11-019816-4.
  3. ^ Уоррен младший, Генри С. (2013) [2002]. Восторг хакера (2-е изд.). Эддисон Уэсли - Pearson Education, Inc., стр. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
  4. ^ a b Коэн, G .; Хонкала, I .; Лицын, С .; Лобштейн, А. (1997), Покрывающие коды , Математическая библиотека Северной Голландии, 54 , Elsevier , стр. 16–17, ISBN 9780080530079
  5. ^ Хэмминг, RW (апрель 1950). «Коды обнаружения и исправления ошибок» (PDF) . Технический журнал Bell System . 29 (2): 147–160. DOI : 10.1002 / j.1538-7305.1950.tb00463.x . ISSN 0005-8580 .  
  6. Перейти ↑ Ayala, Jose (2012). Интегральные схемы и системное проектирование . Springer . п. 62. ISBN 978-3-642-36156-2.
  7. ^ Рот, Рон (2006). Введение в теорию кодирования . Издательство Кембриджского университета . п. 298. ISBN 978-0-521-84504-5.
  8. ^ Пилчер, Кристофер Д .; Вонг, Джозеф К .; Пиллаи, Сатиш К. (18.03.2008). «Вывод динамики передачи ВИЧ из филогенетических отношений последовательности» . PLOS Medicine . 5 (3): e69. DOI : 10.1371 / journal.pmed.0050069 . ISSN 1549-1676 . PMC 2267810 . PMID 18351799 .   
  9. ^ " Обзор методов кодирования для уменьшения энергии движения данных ", JSA, 2018

Дальнейшее чтение [ править ]

  •  Эта статья включает  материалы, являющиеся общественным достоянием, из документа Управления общих служб : «Федеральный стандарт 1037C» .
  • Вегнер, Питер (1960). «Методика счета единиц в двоичном компьютере». Коммуникации ACM . 3 (5): 322. DOI : 10,1145 / 367236,367286 . S2CID  31683715 .
  • Маккей, Дэвид JC (2003). Теория информации, вывод и алгоритмы обучения . Кембридж: Издательство Кембриджского университета . ISBN 0-521-64298-1.