stringtranslate.com

Вес Хэмминга

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

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

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

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

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

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

Проблема его эффективной реализации широко изучена. На некоторых процессорах доступна отдельная операция вычисления или параллельные операции над битовыми векторами. Для процессоров, лишенных этих функций, лучшие известные решения основаны на добавлении счетчиков в древовидную структуру. Например, чтобы подсчитать количество 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 = 0x3333333333333333 ; //двоичный: 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 году, [14] побитовое И для x с x  - 1 отличается от x только обнулением младшего ненулевого бита: вычитание 1 изменяет самую правую строку из 0 на 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 ; счетчик возврата ; }

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

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

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

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

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

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

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

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

В стандартной библиотеке 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 года. [19]

В Common Lisp функция logcount, учитывая неотрицательное целое число, возвращает количество 1 бит. (Для отрицательных целых чисел возвращается количество нулевых битов в записи дополнения до 2.) В любом случае целое число может быть БОЛЬШИМ ЧИСЛОМ.

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

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

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

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

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

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

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

Рекомендации

  1. ^ abcdefg Уоррен младший, Генри С. (2013) [2002]. Хакерское наслаждение (2-е изд.). Аддисон Уэсли - 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.(Примечание. Черновой вариант главы 1b доступен для скачивания.)
  3. ^ ab Руководство пользователя Hewlett-Packard HP-16C для компьютерных специалистов (PDF) . Компания Хьюлетт-Паккард . Апрель 1982 г. 00016-90001. Архивировано (PDF) из оригинала 28 марта 2017 г. Проверено 28 марта 2017 г.
  4. ^ [1], написано в Формулах. Вики-сайт Формулы . Проверено 30 сентября 2019 г.
  5. ^ Решение задачи Подсчет населения. Проверено 30 сентября 2019 г.
  6. ^ Розеттский кодекс. Проверено 30 сентября 2019 г.
  7. ^ Томпсон, Томас М. (1983). От кодов, исправляющих ошибки, через сферические упаковки к простым группам . Математические монографии Каруса № 21. Математическая ассоциация Америки . п. 33.
  8. ^ Глейшер, Джеймс Уитбред Ли (1899). «О вычете коэффициента биномиальной теоремы по простому модулю». Ежеквартальный журнал чистой и прикладной математики . 30 : 150–156.(Примечание. См., в частности, последний абзац стр. 156.)
  9. ^ Рид, Ирвинг Стой (1954). «Класс кодов, исправляющих множественные ошибки, и схема декодирования». Профессиональная группа IRE по теории информации . Институт радиоинженеров (ИРЭ). ПГИТ-4: 38–49.
  10. ^ Коэн, Жерар Д .; Лобштейн, Антуан; Наккеш, Дэвид; Земор, Жиль (1998). «Как улучшить черный ящик возведения в степень». В Нюберге, Кайса (ред.). Достижения в криптологии – EUROCRYPT '98, Международная конференция по теории и применению криптографических методов, Эспоо, Финляндия, 31 мая – 4 июня 1998 г., Текущие материалы . Конспекты лекций по информатике. Том. 1403. Спрингер. стр. 211–220. дои : 10.1007/BFb0054128 .
  11. ^ Стойка, И.; Моррис, Р.; Либен-Ноуэлл, Д.; Каргер, доктор медицинских наук; Каашук, МФ; Дабек, Ф.; Балакришнан, Х. (февраль 2003 г.). «Chord: масштабируемый протокол однорангового поиска для интернет-приложений». Транзакции IEEE/ACM в сети . 11 (1): 17–32. дои : 10.1109/TNET.2002.808407. S2CID  221276912. Раздел 6.3: «В общем, количество пальцев, за которыми нам нужно следовать, будет количеством единиц в двоичном представлении расстояния от узла до запроса».
  12. ^ ab SPARC International, Inc. (1992). «A.41: Подсчет населения. Примечание по программированию» . Руководство по архитектуре SPARC: версия 8 (изд. версии 8). Энглвуд Клиффс, Нью-Джерси, США: Прентис Холл . стр. 231. ISBN 0-13-825001-4.
  13. ^ Блэкселл, Дэвид (1978). Хогбен, Дэвид; Файф, Деннис В. (ред.). «Связывание записей путем сопоставления битовых шаблонов». Информатика и статистика — Десятый ежегодный симпозиум по интерфейсу . Специальное издание НБС. Министерство торговли США / Национальное бюро стандартов . 503 : 146–156.
  14. ^ Вегнер, Питер (май 1960 г.). «Техника счета единиц в двоичном компьютере». Коммуникации АКМ . 3 (5): 322. дои : 10.1145/367236.367286 . S2CID  31683715.
  15. ^ Мула, Войцех; Курц, Натан; Лемир, Дэниел (январь 2018 г.). «Более быстрый подсчет населения с использованием инструкций AVX2». Компьютерный журнал . 61 (1): 111–120. arXiv : 1611.07612 . doi : 10.1093/comjnl/bxx046. S2CID  540973.
  16. ^ Стерн и Махмуд, Проектирование систем связи , Prentice Hall , 2004, стр. 477 и далее.
  17. ^ «Примечания к выпуску GCC 3.4» . Проект ГНУ .
  18. ^ «Примечания к выпуску LLVM 1.5» . Проект ЛЛВМ .
  19. ^ «Что нового в Python 3.10» . python.org .
  20. ^ «Примечания к выпуску GHC 7.4.1» .Документация ГХК.
  21. ^ «Глава 12.11. Битовые функции — Справочное руководство MySQL 5.0» .
  22. ^ Меткалф, Майкл; Рид, Джон; Коэн, Малькольм (2011). Объяснение современного Фортрана . Издательство Оксфордского университета . п. 380. ИСБН 978-0-19-960142-4.
  23. ^ Шварц, Джейк; Гревель, Рик (20 октября 2003 г.) [1993]. Библиотека эмулятора HP16C для HP48S/SX. 1.20 (1-е изд.) . Проверено 15 августа 2015 г.(Примечание. Эта библиотека также работает на HP 48G / GX / G+ . Помимо набора функций HP-16C , этот пакет также поддерживает вычисления для двоичных, восьмеричных и шестнадцатеричных чисел с плавающей запятой в экспоненциальном представлении в дополнение к обычным десятичным числам. числа с плавающей запятой.)
  24. ^ Бонин, Уолтер (2019) [2015]. Руководство пользователя WP 43S (PDF) . 0,12 (проект ред.). п. 135. ИСБН 978-1-72950098-9. Проверено 5 августа 2019 г.[2] [3] (314 страниц)
  25. ^ Бонин, Уолтер (2019) [2015]. Справочное руководство WP 43S (PDF) . 0,12 (проект ред.). стр. XIII, 104, 115, 120, 188. ISBN . 978-1-72950106-1. Проверено 5 августа 2019 г.[4] [5] (271 страница)
  26. ^ Мартин, Анхель М.; МакКлюр, Грег Дж. (5 сентября 2015 г.). «Модуль эмулятора HP16C для HP-41CX — Руководство пользователя и QRG» (PDF) . Архивировано (PDF) из оригинала 27 апреля 2017 г. Проверено 27 апреля 2017 г.(Примечание. Помимо набора функций HP-16C , эта специальная библиотека для HP-41CX расширяет функциональность калькулятора примерно на 50 дополнительных функций.)
  27. ^ Мартин, Анхель М. (07 сентября 2015 г.). «HP-41: доступен новый эмулятор HP-16C». Архивировано из оригинала 27 апреля 2017 г. Проверено 27 апреля 2017 г.
  28. ^ Торнгрен, Хокан (10 января 2017 г.). «Документация по божьей коровке» (выпуск 0А изд.) . Проверено 29 января 2017 г.[6]
  29. ^ «Доступен новый модуль HP-41: Божья коровка» . 10 января 2017 г. Архивировано из оригинала 29 января 2017 г. Проверено 29 января 2017 г.
  30. ^ Дейл, Пол; Бонин, Уолтер (2012) [2008]. «Руководство пользователя WP 34S» (PDF) (изд. 3.1) . Проверено 27 апреля 2017 г.
  31. ^ Бонин, Уолтер (2015) [2008]. Руководство пользователя WP 34S (изд. 3.3). Независимая издательская платформа CreateSpace. ISBN 978-1-5078-9107-0.
  32. ^ «Документация по Free Pascal popcnt» . Проверено 7 декабря 2019 г.
  33. ^ «JDK-6378821: bitCount() должен использовать POPC на процессорах SPARC и AMD+10h». База данных ошибок Java . 30 января 2006 г.
  34. ^ Справочник по набору инструкций Blackfin (предварительная редакция). Аналоговые устройства . 2001. стр. 8–24. Номер детали 82-000410-14.
  35. ^ Вольф, Клэр (22 марта 2019 г.). Расширение битовых манипуляций «RISC-V «B» для RISC-V, черновик v0.37» (PDF) . Гитхаб .

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

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