SEC-DED: исправить одну ошибку и обнаружить две

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

Как думаешь, чем две ошибки отличаются от одной

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

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

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

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

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

Механизм: ещё одна проверка всего слова

Возьмём семь позиций Хэмминга(7, 4) и добавим восьмую. Она содержит XOR первых семи битов, поэтому в правильном восьмибитном слове общее число единиц чётно. Обозначим общую чётность через P: 0 для чётного числа единиц, 1 для нечётного. Синдром S по-прежнему считается только по первой части - дополнительная позиция в него не входит.

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

При двух ошибках общая чётность снова чётная. Если дополнительный бит не затронут, в первой части изменились разные позиции i,j, и S=i^j≠0. Если дополнительный бит затронут, в первой части изменена ровно одна позиция, и синдром тоже ненулевой. Значит все двойные ошибки попадают в один и тот же класс решения: отказаться от ремонта.

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

Правило

SEC-DED проверяет два признака: синдром первой части и чётность всего слова. При не более чем двух изменённых битах нечётность разрешает исправление, а ненулевой синдром при сохранённой чётности требует отказа. Нулевой синдром при нечётности указывает на ошибку в самом дополнительном бите. Общее число проверок равно числу проверок Хэмминга плюс один.

Для 32 информационных битов нужно шесть адресных проверок: 2⁶≥32+6+1. Затем добавляют общую чётность. Всего получается 39 передаваемых битов, из них семь проверочных. Это укороченная конструкция: используются не все ненулевые шестибитные адреса.

Разбор: один алгоритм для четырёх и тридцати двух битов

Код ниже размещает адресные проверки в позициях степеней двойки. Данные идут в оставшихся, последняя позиция хранит общую чётность. Число k задаёт ширину полезного сообщения; перед кодированием предполагаем 0≤m<2^k. Перебор combinations проверяет пары различных искажённых позиций. Менять один и тот же бит дважды означает вообще не менять слово.

from itertools import combinations


def razmery(k):
    r = 0
    while 2 ** r < k + r + 1:
        r += 1
    return r, k + r


def kod(m, k):
    r, n = razmery(k)
    w = 0
    i = 0
    for p in range(1, n + 1):
        if p & (p - 1):
            w |= ((m >> i) & 1) << (p - 1)
            i += 1
    for j in range(r):
        q = 1 << j
        b = 0
        for p in range(1, n + 1):
            if p & q:
                b ^= (w >> (p - 1)) & 1
        w |= b << (q - 1)
    return w | ((w.bit_count() & 1) << n)


def chitat(w, k):
    _, n = razmery(k)
    s = 0
    for p in range(1, n + 1):
        if (w >> (p - 1)) & 1:
            s ^= p
    parity = w.bit_count() & 1
    if not parity and s:
        return "неисправимое", None
    status = "целое"
    if parity:
        if s > n:
            return "неисправимое", None
        position = s if s else n + 1
        w ^= 1 << (position - 1)
        status = "исправлено"
    m = 0
    i = 0
    for p in range(1, n + 1):
        if p & (p - 1):
            m |= ((w >> (p - 1)) & 1) << i
            i += 1
    return status, m


for k, m in [(4, 10), (32, 1234567890)]:
    r, n = razmery(k)
    w = kod(m, k)
    one = sum(chitat(w ^ (1 << j), k) == ("исправлено", m)
              for j in range(n + 1))
    two = sum(chitat(w ^ (1 << i) ^ (1 << j), k)[0]
              == "неисправимое"
              for i, j in combinations(range(n + 1), 2))
    print("данные", k, "проверки", r + 1, "всего", n + 1)
    print("одиночные исправлены", one, "двойные обнаружены", two)
print("сообщение 10:", f"{kod(10, 4):08b}")
print("три ошибки из нулевого слова:", chitat(0b00000111, 4))
print("четыре ошибки из нулевого слова:", chitat(0b10000111, 4))

данные 4 проверки 4 всего 8
одиночные исправлены 8 двойные обнаружены 28
данные 32 проверки 7 всего 39
одиночные исправлены 39 двойные обнаружены 741
сообщение 10: 11010010
три ошибки из нулевого слова: ('исправлено', 1)
четыре ошибки из нулевого слова: ('целое', 1)

Результат chitat - пара: статус и прочитанное сообщение. При отказе сообщения нет, поэтому второе значение равно None. Приложение отличает успешное чтение без изменения от коррекции, даже когда полезные данные совпадают. В счётчике two индекс [0] выбирает статус. Названия статусов описывают решение декодера при принятой модели; последние две строки показывают, как оно ошибается за её пределами.

Для четырёх информационных битов проверены все восемь одиночных повреждений одного сообщения и все 28 двойных. Для 32 битов -39 одиночных и 741 двойное. Эти числа относятся к показанным сообщениям; задача после теории проверит все возможные принятые восьмибитные слова. Ограниченные переборы подтверждают реализацию, а общая гарантия следует из таблицы и расстояния кода, не из выбранного сообщения.

В книге можно встретить другую упаковку: полезное машинное слово отдельно от группы проверочных битов. Тогда маски и физические номера другие, но каждый передаваемый бит по-прежнему имеет свой неповторяющийся столбец адресных проверок. Чтобы читать такой код, выпиши эту таблицу соответствия. Чётность группы удобно получать как (word & mask).bit_count() & 1. Переносы раскладки меняют маски, а не доказательство.

Разбор: три ошибки превращаются в успешный ремонт

Из нулевого слова изменим позиции 1, 2, 3. Синдром равен 1^2^3=0, общая чётность нечётна. Таблица, рассчитанная на не больше двух ошибок, велит изменить последний бит. Получится 10000111: допустимое кодовое слово сообщения 1. Декодер не просто пропустил повреждение, он добавил ещё одно изменение и выдал уверенный неверный результат.

Если сразу изменить позиции 1, 2, 3, 8, получится то же допустимое слово. Синдром и чётность будут нулевыми, поэтому ошибки не обнаружатся. Это согласуется с расстоянием 4: такое число изменений уже может связать два кодовых слова напрямую. Перебор внизу программы показывает оба случая. Нельзя расширить обещание SEC-DED простым переименованием статуса.

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

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

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

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

Контроллер памяти может прозрачно исправить одиночное повреждение, но двойное должен передать уровню, который решает, можно ли повторить чтение или завершить обработку. Три статуса - «целое», «исправлено», «обнаружено неисправимое» - несут разные сведения. Сводить их к одному успешному чтению опасно для приложения, которое хранит важные данные.

Модель должна соответствовать устройству. Если целый физический компонент может повредить несколько разрядов одного кодового слова, обещания на одну и две ошибки может не хватить. Код выбирают под характер повреждений; эта конструкция сама по себе не обещает защиту от любого отказа оборудования или намеренной подмены.

Теперь сам

Восьмибитный декодер получил S=0,P=1. Что он должен исправить при обещании не больше двух ошибок? Может ли это же наблюдение получиться после трёх ошибок? Затем найди число проверочных битов SEC-DED для 64 информационных битов.