Вес Хэмминга

Вес Хэмминга (также известный как расстояние Хэмминга от нуля, весовая функция, popcount) — это количество ненулевых символов в строке фиксированной длины, чаще всего в двоичном представлении числа. В теории информации и кодирования вес Хэмминга является фундаментальной характеристикой, определяющей количество единиц в двоичном слове. Понятие введено американским математиком Ричардом Уэсли Хэммингом в 1950 году в контексте разработки кодов, исправляющих ошибки.

Определение и основные понятия

Для двоичного вектора x длины n, состоящего из символов 0 и 1, вес Хэмминга w(x) определяется как число позиций, на которых стоит единица:

\[ w(\mathbf{x}) = \sum_{i=1}^{n} x_i \]

Например, для двоичного слова 101101 вес Хэмминга равен 4, так как в нём четыре единицы. Для нулевого вектора (000000) вес равен 0.

Вес Хэмминга тесно связан с расстоянием Хэмминга — метрикой, показывающей количество позиций, в которых различаются два слова одинаковой длины. Расстояние Хэмминга между двумя словами a и b равно весу их поразрядной суммы по модулю 2 (XOR):

\[ d(\mathbf{a}, \mathbf{b}) = w(\mathbf{a} \oplus \mathbf{b}) \]

Свойства

Вес Хэмминга обладает рядом важных свойств, используемых в теории кодирования:

• Неотрицательность: \( w(\mathbf{x}) \ge 0 \), причём равенство нулю достигается только для нулевого слова.
• Симметричность: для двоичного слова вес не меняется при инверсии всех битов (замене 0 на 1 и наоборот) только если длина слова чётна.
• Субмультипликативность: для двух слов a и b выполняется \( w(\mathbf{a} \oplus \mathbf{b}) \le w(\mathbf{a}) + w(\mathbf{b}) \).
• Связь с чётностью: чётность веса слова определяет его бит чётности (parity bit). Если вес чётен, бит чётности равен 0; если нечётен — 1.

История

Понятие веса Хэмминга возникло в 1950 году, когда Ричард Хэмминг опубликовал работу «Error Detecting and Error Correcting Codes» в журнале Bell System Technical Journal. В этой работе он ввёл понятие расстояния между кодовыми словами, которое позже стало называться расстоянием Хэмминга. Вес Хэмминга как частный случай расстояния от нулевого вектора стал ключевым инструментом для анализа помехоустойчивых кодов.

Хэмминг работал в Bell Labs, где занимался проблемами передачи данных по телефонным линиям. Его коды, основанные на минимальном расстоянии между словами, позволили обнаруживать и исправлять одиночные ошибки. Вес Хэмминга стал мерой «тяжести» ошибки — чем больше единиц в слове, тем больше битов искажено.

Применение

Теория кодирования

Вес Хэмминга является основой для построения помехоустойчивых кодов. Минимальное расстояние кода — наименьший вес ненулевого кодового слова — определяет его корректирующую способность. Например, код с минимальным расстоянием 3 может исправлять одну ошибку или обнаруживать две. Коды Хэмминга, коды Боуза — Чоудхури — Хоквингема (БЧХ) и свёрточные коды используют вес Хэмминга для оценки надёжности передачи.

Криптография

В криптографии вес Хэмминга применяется для анализа стойкости шифров. Например, в алгоритме DES (Data Encryption Standard) вес Хэмминга S-блоков используется для оценки их нелинейности. В атаках по сторонним каналам (side-channel attacks) вес Хэмминга может быть коррелирован с потребляемой мощностью устройства, что позволяет извлечь секретные ключи. В частности, атака по мощности (power analysis) использует тот факт, что количество переключаемых битов (вес Хэмминга обрабатываемых данных) влияет на энергопотребление.

Информатика и программирование

Вычисление веса Хэмминга (popcount) — одна из базовых операций в программировании. Современные процессоры (например, архитектуры x86-64 с инструкцией POPCNT, ARM с VCNT) имеют аппаратную поддержку этой операции. В языках программирования высокого уровня (C++, Python, Java) существуют встроенные функции или библиотеки для вычисления popcount. Операция используется в:

• Хэш-таблицах: для оценки плотности заполнения.
• Графовых алгоритмах: для подсчёта рёбер в разреженных графах, представленных битовыми масками.
• Компьютерном зрении: для сравнения бинарных дескрипторов изображений (например, BRIEF, ORB).
• Генетических алгоритмах: для оценки разнообразия популяции.

Комбинаторика

В комбинаторике вес Хэмминга связан с биномиальными коэффициентами. Количество двоичных слов длины n с весом k равно числу сочетаний \( C(n, k) \). Это используется в задачах подсчёта подмножеств, анализа кодов и теории графов.

Алгоритмы вычисления

Существует несколько способов вычисления веса Хэмминга:

Наивный метод

Последовательный перебор всех битов числа с подсчётом единиц. Сложность O(n), где n — количество битов.

Метод сдвигов и маскирования

Использование битовых операций для параллельного подсчёта. Например, алгоритм Брайана Кернигана (Brian Kernighan) работает за время O(k), где k — количество единиц:

``c int popcount(unsigned int x) { int count = 0; while (x) { x &= (x - 1); // обнуляет младший единичный бит count++; } return count; } ``

Метод таблиц

Предварительное вычисление popcount для всех возможных значений байта (256 значений) и последующее суммирование для каждого байта числа. Этот метод эффективен для чисел с фиксированной длиной.

Аппаратная поддержка

Современные процессоры имеют инструкцию POPCNT, которая выполняет подсчёт за один такт. В языке C можно использовать встроенные функции компилятора, например __builtin_popcount в GCC.

Интересные факты

• Вес Хэмминга используется в алгоритме сжатия данных LZW (Lempel-Ziv-Welch) для оценки энтропии.
• В криптоанализе атака «по весу Хэмминга» (Hamming weight attack) применяется для взлома RSA и AES.
• В квантовых вычислениях вес Хэмминга связан с понятием «квантового расстояния» для кодов, исправляющих ошибки.
• В математике вес Хэмминга обобщается на недвоичные алфавиты — для строк над конечным полем GF(q) вес определяется как количество ненулевых символов.
• В 2008 году компания Intel ввела инструкцию POPCNT в процессорах Nehalem, что значительно ускорило вычисления в криптографии и обработке данных.

Критика и ограничения

Вес Хэмминга не учитывает позиционный вес битов (значимость разрядов). Например, для чисел 1000 (8) и 0001 (1) вес одинаков (1), хотя числовые значения различаются. Это ограничение делает его непригодным для задач, где важна арифметическая величина, а не только количество единиц. В таких случаях используется расстояние Левенштейна или другие метрики.

Кроме того, для длинных строк (например, геномных последовательностей) вычисление веса Хэмминга может быть ресурсоёмким, если не использовать аппаратную поддержку. В некоторых приложениях (например, в биоинформатике) применяются приближённые методы, такие как MinHash, для оценки сходства последовательностей.

Источники

• Хэмминг Р. У. «Error Detecting and Error Correcting Codes» // Bell System Technical Journal, 1950, Vol. 29, No. 2, pp. 147–160.
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. «Теория кодов, исправляющих ошибки» — М.: Связь, 1979.
• Кнут Д. Э. «Искусство программирования. Том 2. Получисленные алгоритмы» — М.: Вильямс, 2007.
• Паттерсон Д., Хеннесси Дж. «Архитектура компьютера и проектирование компьютерных систем» — М.: Питер, 2012.
• Menezes A. J., van Oorschot P. C., Vanstone S. A. «Handbook of Applied Cryptography» — CRC Press, 1996.