Принцип (кратко)
- Хэмминговский код добавляет $r$ контрольных бит в позиции степеней двойки (1,2,4,…). При кодировании каждый контрольный бит вычисляет чётность подмножеств битов, у которых соответствующий бит индекса равен 1.
- При приёме вычисляется синдром $s$ (вектор чётностей); ненулевой синдром указывает позицию ошибочного бита (в двоичной форме — его индекс). Таким образом код корректирует любую одиночную ошибку.
- Число контрольных бит $r$ выбирают так, чтобы выполнялось: $$2^r\ge k+r+1,$$ где $k$ — число информационных бит, $n=k+r$ — длина кодового слова. Код Хэмминга — SEC (single-error-correcting). Добавлением ещё одного глобального бита чётности получают SECDED (single-error-correcting, double-error-detecting).
Пример реализации (Hamming(7,4), легко обобщить)
```python
# Простая реализация Hamming(7,4). Биты — списки 0/1, индексирование 1-based логика реализована через сдвиг.
def _is_power_of_two(x):
return (x & (x - 1)) == 0
def encode_7_4(data): # data: list of 4 bits [d3,d2,d1,d0] (MSB->LSB or любая договорённость)
if len(data) != 4:
raise ValueError("Expect 4 bits")
# Собираем 7 позиций; индекс 1..7 (будем игнорировать позицию 0)
cw = [0] * 8
# Заполняем информационные биты в оставшиеся позиции (не степени двойки)
di = 0
for i in range(1, 8):
if not _is_power_of_two(i):
cw[i] = data[di]
di += 1
# Вычисляем контрольные биты: для каждой позиции 1,2,4 считаем чётность
for p in (1, 2, 4):
parity = 0
for i in range(1, 8):
if i & p:
parity ^= cw[i]
cw[p] = parity
return cw[1:] # возвращаем 7 бит как список
def decode_7_4(received):
if len(received) != 7:
raise ValueError("Expect 7 bits")
r = [0] + received
received[2] ^= 1
print("received:", received)
decoded, corrected, syn = decode_7_4(received)
print("decoded:", decoded, "corrected:", corrected, "syndrome:", syn)
```
Оценка эффективности и ограничения
- Способность исправлять/обнаруживать: стандартный Хэмминг — корректирует любую одиночную ошибку (SEC). Без дополнительного бита чётности не гарантирует обнаружение всех двойных ошибок. Расширённый Hamming (добавлен бит глобальной чётности) — SECDED (исправление 1 бита, обнаружение 2 бит).
- Избыточность и скорость: для Hamming(7,4) $k=4,n=7$, скорость $R=k/n=4/7\approx 0.571$. В общем $R=k/(k+r)$. Вычисление паритетов и синдрома — линейно по $n$ (эффективность $O(n)$).
- Ограничения: не подходит, если в канале часто возникают многобитовые ошибки (требуются более мощные коды: BCH, Reed–Solomon, LDPC). Хэмминг чувствителен к синхронизации и всплескам ошибок (burst errors) — нужны интерливинг или другие техники.
- Применимость: простота реализации, малые накладные расходы — хорош для аппаратных/встраиваемых систем и каналов с редкими одноразовыми ошибками.