stringtranslate.com

вес Хэмминга

Вес Хэмминга строки — это количество символов, отличных от нулевого символа используемого алфавита . Таким образом, он эквивалентен расстоянию Хэмминга от строки из всех нулей той же длины. Для наиболее типичного случая строки битов это количество единиц в строке или сумма цифр двоичного представления заданного числа и ℓ ₁ нормы битового вектора. В этом двоичном случае это также называется подсчетом популяции , [1] popcount , боковой суммой , [2] или суммированием битов . [3]

График веса Хэмминга для чисел от 0 до 256. [4]

История и использование

Вес Хэмминга назван в честь американского математика Ричарда Хэмминга , хотя он не был создателем этого понятия. [5] Вес Хэмминга двоичных чисел уже использовался в 1899 году Джеймсом У. Л. Глейшером для получения формулы для числа нечетных биномиальных коэффициентов в одной строке треугольника Паскаля . [6] Ирвинг С. Рид ввел концепцию, эквивалентную весу Хэмминга в двоичном случае, в 1954 году. [7]

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

Эффективная реализация

Подсчет популяции битовой строки часто требуется в криптографии и других приложениях. Расстояние Хэмминга двух слов A и B может быть рассчитано как вес Хэмминга A xor B . [1]

Проблема того, как реализовать это эффективно, широко изучалась. Отдельная операция для вычисления или параллельные операции над битовыми векторами доступны на некоторых процессорах. Для процессоров, не имеющих этих возможностей, лучшие известные решения основаны на добавлении счетчиков в древовидной схеме. Например, чтобы подсчитать количество единичных битов в 16-битном двоичном числе a = 0110 1100 1011 1010, можно выполнить следующие операции:

Здесь операции такие же, как в языке программирования C , поэтому X >> Yозначает сдвиг X вправо на Y бит, X & Y означает побитовое И X и Y, а + — обычное сложение. Лучшие известные алгоритмы для этой задачи основаны на концепции, проиллюстрированной выше, и приведены здесь: [1]

//типы и константы, используемые в функциях ниже //uint64_t — это беззнаковый 64-битный целочисленный тип переменной (определен в версии C99 языка C) const uint64_t m1 = 0x5555555555555555 ; //двоичный: 0101... const uint64_t m2 = 0x333333333333333 ; //двоичный: 00110011.. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f ; //двоичный: 4 нуля, 4 единицы ... const uint64_t m8 = 0x00ff00ff00ff00ff ; //двоичное: 8 нулей, 8 единиц ... const uint64_t m16 = 0x0000ffff0000ffff ; //двоичное: 16 нулей, 16 единиц ... const uint64_t m32 = 0x00000000ffffffff ; //двоичное: 32 нуля, 32 единицы const uint64_t h01 = 0x0101010101010101 ; //сумма 256 в степени 0,1,2,3...                                   //Это наивная реализация, показанная для сравнения, //и чтобы помочь понять лучшие функции. //Этот алгоритм использует 24 арифметические операции (сдвиг, сложение и). int popcount64a ( uint64_t x ) { x = ( x & m1 ) + (( x >> 1 ) & m1 ); //помещаем количество каждых 2 бит в эти 2 бита x = ( x & m2 ) + (( x >> 2 ) & m2 ); //помещаем количество каждых 4 бит в эти 4 бита x = ( x & m4 ) + (( x >> 4 ) & m4 ); //помещаем количество каждых 8 бит в эти 8 бит x = ( x & m8 ) + (( x >> 8 ) & m8 ); //помещаем количество каждых 16 бит в эти 16 бит x = ( x & m16 ) + (( x >> 16 ) & m16 ); //помещаем количество каждых 32 бит в эти 32 бита x = ( x & m32 ) + (( x >> 32 ) & m32 ); //помещаем количество каждых 64 бит в эти 64 бита return x ; }                                                                                    //Это использует меньше арифметических операций, чем любая другая известная //реализация на машинах с медленным умножением. //Этот алгоритм использует 17 арифметических операций. int popcount64b ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; //помещаем количество каждых 2 бит в эти 2 бита x = ( x & m2 ) + (( x >> 2 ) & m2 ); //помещаем количество каждых 4 бит в эти 4 бита x = ( x + ( x >> 4 )) & m4 ; //помещаем количество каждых 8 бит в эти 8 бит x += x >> 8 ; //помещаем количество каждых 16 бит в их младшие 8 бит x += x >> 16 ; //помещаем количество каждых 32 бит в их младшие 8 бит x += x >> 32 ; //помещаем количество каждых 64 бит в их младшие 8 бит return x & 0x7f ; }                                                      //Это использует меньше арифметических операций, чем любая другая известная //реализация на машинах с быстрым умножением. //Этот алгоритм использует 12 арифметических операций, одна из которых - умножение. int popcount64c ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; //помещает количество каждых 2 бит в эти 2 бита x = ( x & m2 ) + (( x >> 2 ) & m2 ); //помещает количество каждых 4 бит в эти 4 бита x = ( x + ( x >> 4 )) & m4 ; //помещает количество каждых 8 бит в эти 8 бит return ( x * h01 ) >> 56 ; //возвращает левые 8 бит x + (x<<8) + (x<<16) + (x<<24) + ... }

Вышеуказанные реализации имеют наилучшее поведение в худшем случае среди всех известных алгоритмов. Однако, когда ожидается, что значение будет иметь несколько ненулевых битов, может быть более эффективным использовать алгоритмы, которые подсчитывают эти биты по одному за раз. Как Вегнер описал в 1960 году [12] , побитовое И x с x − 1  отличается от x только обнулением младшего ненулевого бита: вычитание 1 изменяет самую правую строку нулей на 1 и изменяет самую правую 1 на 0. Если x изначально имел n битов, которые были 1, то после всего лишь n итераций этой операции x будет уменьшен до нуля. Следующая реализация основана на этом принципе.

//Это лучше, когда большинство бит в x равны 0 //Этот алгоритм работает одинаково для всех размеров данных. //Этот алгоритм использует 3 арифметические операции и 1 сравнение/ветвление на каждый бит "1" в x. int popcount64d ( uint64_t x ) { int count ; for ( count = 0 ; x ; count ++ ) x &= x - 1 ; return count ; }

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

static uint8_t wordbits [ 65536 ] = { /* количество бит целых чисел от 0 до 65535 включительно */ }; //Этот алгоритм использует 3 арифметические операции и 2 чтения памяти. int popcount32e ( uint32_t x ) { return wordbits [ x & 0xFFFF ] + wordbits [ x >> 16 ]; }                
// При желании таблицу wordbits[] можно заполнить с помощью этой функции int popcount32e_init ( void ) { uint32_t i ; uint16_t x ; int count ; for ( i = 0 ; i <= 0xFFFF ; i ++ ) { x = i ; for ( count = 0 ; x ; count ++ ) // заимствовано из popcount64d() выше x &= x - 1 ; wordbits [ i ] = count ; } }

Мула и др. [13] показали, что векторизованная версия popcount64b может работать быстрее, чем специализированные инструкции (например, popcnt на процессорах x64).

Минимальный вес

В кодировании с исправлением ошибок минимальный вес Хэмминга, обычно называемый минимальным весом w min кода, — это вес ненулевого кодового слова с наименьшим весом. Вес w кодового слова — это количество единиц в слове. Например, слово 11001010 имеет вес 4.

В линейном блочном коде минимальный вес также является минимальным расстоянием Хэмминга ( d min ) и определяет способность кода к исправлению ошибок. Если w min  =  n , то d min  =  n и код исправит до d min /2 ошибок. [14]

Языковая поддержка

Некоторые компиляторы C предоставляют встроенные функции, которые обеспечивают возможности подсчета битов. Например, GCC (начиная с версии 3.4 в апреле 2004 года) включает встроенную функцию __builtin_popcount, которая будет использовать инструкцию процессора, если она доступна, или эффективную реализацию библиотеки в противном случае. [15] LLVM-GCC включает эту функцию с версии 1.5 в июне 2005 года. [16]

В стандартной библиотеке C++ структура данных битового массива bitsetимеет count()метод, который подсчитывает количество установленных битов. В C++20 был добавлен новый заголовок <bit>, содержащий функции std::popcountи std::has_single_bit, принимающие аргументы беззнаковых целочисленных типов.

В Java структура данных растущего битового массива BitSetимеет BitSet.cardinality()метод, который подсчитывает количество установленных битов. Кроме того, существуют Integer.bitCount(int)и Long.bitCount(long)функции для подсчета битов в примитивных 32-битных и 64-битных целых числах соответственно. Кроме того, BigIntegerкласс целочисленных чисел произвольной точности также имеет BigInteger.bitCount()метод, который подсчитывает биты.

В Python тип intимеет bit_count()метод для подсчета количества установленных битов. Эта функциональность была введена в Python 3.10, выпущенном в октябре 2021 года. [17]

В Common Lisp функция logcountвозвращает количество единичных битов в неотрицательном целом числе. (Для отрицательных целых чисел она возвращает количество нулевых битов в дополнительном коде.) В любом случае целое число может быть BIGNUM.

Начиная с GHC 7.4, базовый пакет Haskell имеет popCountфункцию, доступную для всех типов, которые являются экземплярами класса Bits(доступную из Data.Bitsмодуля). [18]

Версия MySQL языка SQL предоставляет BIT_COUNT()стандартную функцию. [19]

В Fortran 2008 есть стандартная, встроенная, элементарная функция, popcntвозвращающая количество ненулевых битов в целом числе (или массиве целых чисел). [20]

Некоторые программируемые научные карманные калькуляторы имеют специальные команды для расчета количества установленных битов, например, #Bна HP-16C [3] [21] и WP 43S , [22] [23] #BITS[24] [25] или BITSUM[26] [27] на эмуляторах HP-16C, а также nBITSна WP 34S . [28] [29]

FreePascal реализует popcnt начиная с версии 3.0. [30]

Поддержка процессора

Смотрите также

Ссылки

  1. ^ abcdefg Уоррен младший, Генри С. (2013) [2002]. Hacker's Delight (2-е изд.). Addison Wesley - Pearson Education, Inc. стр. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
  2. ^ Кнут, Дональд Эрвин (2009). «Побитовые трюки и методы; Диаграммы двоичных решений». Искусство программирования . Том 4, выпуск 1. Addison–Wesley Professional . ISBN 978-0-321-58050-4.(Примечание. Черновик Fascicle 1b, архив 2016-03-12 на Wayback Machine , доступен для скачивания.)
  3. ^ ab Hewlett-Packard HP-16C Computer Scientist Owner's Handbook (PDF) . Hewlett-Packard Company . Апрель 1982 г. 00016-90001. Архивировано (PDF) из оригинала 2017-03-28 . Получено 2017-03-28 .
  4. ^ Р. Угальде, Лоренс. "Population count the Fōrmulæ programming language". Fōrmulæ . Получено 2024-06-02 .
  5. ^ Томпсон, Томас М. (1983). От кодов с исправлением ошибок через сферические упаковки к простым группам . Математические монографии Каруса № 21. Математическая ассоциация Америки . стр. 33.
  6. ^ Глейшер, Джеймс Уитбред Ли (1899). «О вычете коэффициента биномиальной теоремы относительно простого модуля». The Quarterly Journal of Pure and Applied Mathematics . 30 : 150–156.(Примечание. См., в частности, последний абзац на стр. 156.)
  7. ^ Рид, Ирвинг Стой (1954). «Класс кодов с исправлением множественных ошибок и схема декодирования». Профессиональная группа IRE по теории информации . PGIT-4. Институт радиоинженеров (IRE): 38–49.
  8. ^ Cohen, Gérard D. ; Lobstein, Antoine; Naccache, David; Zémor, Gilles (1998). "Как улучшить черный ящик возведения в степень". В Nyberg, Kaisa (ред.). Advances in Cryptology – EUROCRYPT '98, Международная конференция по теории и применению криптографических методов, Эспоо, Финляндия, 31 мая – 4 июня 1998 г., Труды . Lecture Notes in Computer Science. Vol. 1403. Springer. pp. 211–220. doi : 10.1007/BFb0054128 . ISBN 978-3-540-64518-4.
  9. ^ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, DR; Kaashoek, MF; Dabek, F.; Balakrishnan, H. (февраль 2003 г.). «Chord: масштабируемый протокол однорангового поиска для интернет-приложений». IEEE/ACM Transactions on Networking . 11 (1): 17–32. doi :10.1109/TNET.2002.808407. S2CID  221276912. Раздел 6.3: «В общем случае количество пальцев, по которым нам нужно следовать, будет равно количеству единиц в двоичном представлении расстояния от узла до запроса».
  10. ^ ab SPARC International, Inc. (1992). "A.41: Population Count. Programming Note" . Руководство по архитектуре SPARC: версия 8 (Version 8 ed.). Энглвуд Клиффс, Нью-Джерси, США: Prentice Hall . стр. 231. ISBN 0-13-825001-4.
  11. ^ Blaxell, David (1978). Hogben, David; Fife, Dennis W. (ред.). «Связывание записей с помощью сопоставления битовых шаблонов». Computer Science and Statistics — Tenth Annual Symposium on the Interface . NBS Special Publication. 503. Министерство торговли США / Национальное бюро стандартов : 146–156.
  12. ^ Вегнер, Питер (май 1960). «Метод подсчета единиц в двоичном компьютере». Сообщения ACM . 3 (5): 322. doi : 10.1145/367236.367286 . S2CID  31683715.
  13. ^ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (январь 2018 г.). «Быстрый подсчет населения с использованием инструкций AVX2». Computer Journal . 61 (1): 111–120. arXiv : 1611.07612 . doi :10.1093/comjnl/bxx046. S2CID  540973.
  14. ^ Стерн и Махмуд, Проектирование систем связи , Prentice Hall , 2004, стр. 477 и далее.
  15. ^ "Заметки о выпуске GCC 3.4". Проект GNU .
  16. ^ "Заметки о выпуске LLVM 1.5". Проект LLVM .
  17. ^ "Что нового в Python 3.10". python.org .
  18. ^ "Заметки о выпуске GHC 7.4.1".Документация GHC.
  19. ^ «Глава 12.11. Битовые функции — Справочное руководство MySQL 5.0».
  20. ^ Меткалф, Майкл; Рид, Джон; Коэн, Малкольм (2011). Современный Фортран Объясненный . Oxford University Press . стр. 380. ISBN 978-0-19-960142-4.
  21. ^ Шварц, Джейк; Гревелль, Рик (2003-10-20) [1993]. Библиотека эмулятора HP16C для HP48S/SX. 1.20 (1-е изд.) . Получено 15 августа 2015 г.(Примечание. Эта библиотека также работает на HP 48G / GX / G+ . Помимо набора функций HP-16C, этот пакет также поддерживает вычисления для двоичных, восьмеричных и шестнадцатеричных чисел с плавающей точкой в ​​научной нотации в дополнение к обычным десятичным числам с плавающей точкой.)
  22. ^ Бонин, Уолтер (2019) [2015]. Руководство пользователя WP 43S (PDF) . 0.12 (черновая редакция). стр. 135. ISBN 978-1-72950098-9. Получено 2019-08-05 .[ постоянная мертвая ссылка ] [1] [2] (314 страниц)
  23. ^ Бонин, Уолтер (2019) [2015]. Справочное руководство WP 43S (PDF) . 0.12 (черновое издание). стр. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. Получено 2019-08-05 .[ постоянная мертвая ссылка ] [3] [4] (271 страница)
  24. ^ Мартин, Анхель М.; МакКлур, Грег Дж. (2015-09-05). "Модуль эмулятора HP16C для HP-41CX - Руководство пользователя и QRG" (PDF) . Архивировано (PDF) из оригинала 2017-04-27 . Получено 2017-04-27 .(Примечание. Помимо набора функций HP-16C, эта пользовательская библиотека для HP-41CX расширяет функциональность калькулятора примерно на 50 дополнительных функций.)
  25. ^ Мартин, Анхель М. (2015-09-07). "HP-41: Доступен новый эмулятор HP-16C". Архивировано из оригинала 2017-04-27 . Получено 2017-04-27 .
  26. ^ Торнгрен, Хокан (10 января 2017 г.). «Документация по божьей коровке» (выпуск 0А изд.) . Проверено 29 января 2017 г.[5]
  27. ^ "Доступен новый модуль HP-41: Ladybug". 2017-01-10. Архивировано из оригинала 2017-01-29 . Получено 2017-01-29 .
  28. ^ Дейл, Пол; Бонин, Уолтер (2012) [2008]. "WP 34S Owner's Manual" (PDF) (3.1 ed.) . Получено 27.04.2017 .
  29. ^ Бонин, Уолтер (2015) [2008]. Руководство пользователя WP 34S (3.3 ред.). CreateSpace Independent Publishing Platform. ISBN 978-1-5078-9107-0.
  30. ^ "Free Pascal documentation popcnt" . Получено 2019-12-07 .
  31. ^ "JDK-6378821: bitCount() должен использовать POPC на процессорах SPARC и AMD+10h". База данных ошибок Java . 2006-01-30.
  32. ^ Справочник по набору инструкций Blackfin (предварительное издание). Analog Devices . 2001. С. 8–24. Номер детали 82-000410-14.
  33. ^ Вольф, Клэр (2019-03-22). "RISC-V "B" Bit Manipulation Extension для RISC-V, Draft v0.37" (PDF) . Github .

Дальнейшее чтение

Внешние ссылки