Расстояние кода: обнаружение и исправление ошибок

Если различаешь проверку принадлежности коду и исправление по ближайшему слову, а условие 2t < d можешь вывести через расстояние, переходи к «Теперь сам».

Как думаешь, достаточно ли заметить неверное слово

Устройство передаёт один бит. Вместо 0 оно отправляет 000, вместо 1 - 111. Получатель увидел 001. Словарь такого слова не содержит: помеха обнаружена. Но почему надо восстановить именно 000? Оно отличается в одной позиции, а 111 - в двух. Ответ опирается на предположение: изменился не больше чем один бит.

Теперь представь, что устройство отправило 111, а два бита изменились. Получатель опять увидел 001. Если он применит прежнее правило, получится неправильный исходный бит. Само наблюдение не сообщает, насколько сильной была помеха. Код даёт гарантию только для оговорённого класса ошибок; нарушение условия нельзя всегда распознать постфактум.

На что это похоже

В справочнике оставили только адреса домов с номерами 000 и 111. Курьер получил адрес с одной испорченной цифрой и знает, что ошиблась максимум одна цифра. Он может сравнить полученную запись с обеими допустимыми: один адрес окажется ближе.

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

Механизм: кодовый словарь и расстояние

Бинарный блочный код - множество C различных двоичных слов одной длины n. Допустимое слово называют кодовым. Обозначим число слов через M. При передаче одного из них получатель знает словарь, но не знает, какую запись выбрал отправитель.

Расстояние Хэмминга d(x,y) равно числу отличающихся позиций. Для целых чисел той же фиксированной ширины это число единиц в x ^ y: XOR отмечает ровно несовпавшие разряды. Числовая разность не подходит: 0111 и 1000 отличаются на единицу как числа, но во всех четырёх позициях как битовые слова.

Минимальное расстояние кода d - наименьшее расстояние между двумя различными словами словаря. Если допустимых слов хотя бы два, минимум определён. Важна самая тесная пара: хорошие расстояния между остальными словами не спасают её от неоднозначности.

Если изменились от одного до d−1 битов, новое слово не может стать другим кодовым. Иначе расстояние между этими двумя словами было бы меньше d. Поэтому проверка принадлежности C обнаруживает все такие ошибки. Пока она ничего не исправляет.

Для исправления рассмотрим шар Хэмминга радиуса t вокруг кодового слова: все записи, получаемые изменением не более t битов. Общая точка двух шаров означала бы два возможных исходных сообщения. По неравенству треугольника расстояние между центрами тогда не больше t+t. При d>2t такого пересечения нет. В обратную сторону: если расстояние двух центров не больше 2t, отличающиеся позиции можно распределить между двумя путями длины не больше t; на этих путях найдётся общая полученная запись. Неоднозначность неизбежна.

Правило

Для кода с минимальным расстоянием d проверка принадлежности словарю обнаруживает любые d−1 изменённых битов. Восстановление по ближайшему кодовому слову гарантированно исправляет любые ⌊(d−1)/2⌋ ошибок. Эти обещания относятся к разным процедурам.

Если словарь представляет все 2^k сообщений из k информационных битов, его кодовая скорость равна k/n. Для произвольного числа сообщений она равна log₂(M)/n: логарифм измеряет количество информации, которое различает M вариантов. Размер словаря не обязан быть степенью двойки. Например, постоянный вес слова может задавать другое число вариантов.

Разбор: повтор, чётность и пятнадцать сообщений

Посчитаем расстояния перебором пар. Во втором словаре находятся все трёхбитные слова с чётным числом единиц. В третьем - все шестибитные слова, в которых ровно две единицы. Их число определяется выбором двух позиций из шести. Здесь перебор нужен для проверки маленького примера; настоящий декодер не обязан перебирать весь словарь.

from math import comb, log2


def rasstoyanie(c):
    return min((a ^ b).bit_count()
               for i, a in enumerate(c) for b in c[i + 1:])


primery = [
    ("повтор", 3, [0, 7]),
    ("чётность", 3, [0, 3, 5, 6]),
    ("два из шести", 6,
     [x for x in range(64) if x.bit_count() == 2]),
]
for imya, n, c in primery:
    print(imya, "слов", len(c), "d", rasstoyanie(c),
          "скорость", round(log2(len(c)) / n, 3))

c = [0b00000, 0b11100, 0b10011, 0b01111]
print("четыре пятибитных слова: d =", rasstoyanie(c))
print("исправить один:", len(c) * (1 + 5), "<=", 2 ** 5)
print("исправить два:", len(c) * sum(comb(5, i)
                                     for i in range(3)), ">", 2 ** 5)

повтор слов 2 d 3 скорость 0.333
чётность слов 4 d 2 скорость 0.667
два из шести слов 15 d 2 скорость 0.651
четыре пятибитных слова: d = 3
исправить один: 24 <= 32
исправить два: 64 > 32

Повтор имеет расстояние 3 и исправляет одну ошибку. Проверка чётности имеет расстояние 2: она обнаруживает одну ошибку, но общего способа исправить её нет. Словарь «два из шести» содержит 15 сообщений, а не целую степень двойки. Две перестановки единицы в соседнюю нулевую позицию уже превращают его слово в другое допустимое, поэтому расстояние тоже равно 2.

Последние строки считают количество записей вокруг четырёх пятибитных слов. Для одной ошибки вокруг каждого центра есть центр и пять соседей. Всего 24 записи помещаются среди 32 возможных. Для двух ошибок пришлось бы выделить 64 записи: это невозможно. Сами границы числа слов и вопрос достижимости подробно разберём в конце главы.

Разбор: обнаруживать две ошибки и исправлять одну

Возьми словарь 000 и 111, расстояние 3. Проверка принадлежности обнаружит запись 001: она не входит в словарь. При этом получатель ещё не выбрал исправление.

Если он обязан исправлять все одиночные ошибки, запись 001 должна стать 000. Но она же получается двумя изменениями из 111. Декодер уже не может объявить её ошибкой, не нарушив обещание исправить одиночную помеху от 000. Поэтому из одного расстояния 3 нельзя заключить, что конкретный исправляющий декодер ещё и надёжно отклоняет все двойные ошибки. Именно эту границу устранит дополнительный бит в SEC-DED.

Что ломается без этого

Если считать любой принятый набор битов сообщением, контроль исчезает: помеха переводит одну разрешённую запись в другую. Если же выбирать ближайшую запись без ограничения на число ошибок, уверенный ответ может быть неверным. Декодер исполняет своё правило правильно, но реальный канал уже вышел за условия, для которых правило доказано.

Расстояние считают между словами одинаковой длины. Пропуск или добавление разряда требует другой модели: изменятся границы блока. Ошибки подстановки битов и потеря синхронизации - разные задачи. Сначала установи, какие повреждения вообще допустимы.

Зачем это в работе

Контроллер памяти хранит рядом с данными проверочные биты. При чтении он должен решить, можно ли исправить слово или нужно сообщить о повреждении. Для проектирования важны обе цены: дополнительные разряды и последствия ошибки за пределами гарантии.

В канале связи код позволяет восстановить данные без повторного запроса. Если повторная передача разрешена и дёшева, иногда достаточно обнаружения ошибки и повторного чтения. Выбор зависит от модели отказов и стоимости повторения; одна только длина контрольной суммы не отвечает на вопрос, какая процедура подходит системе.

Теперь сам

Код содержит десять шестибитных слов. Может ли он исправлять любую одиночную ошибку? Вокруг каждого слова при таком обещании должны помещаться центр и шесть соседей.

Вторая задача: допустимы 0000 и 1110, принято 0110. Можно ли уверенно восстановить 1110, если допускаются не больше двух ошибок?