Конспект: коды с исправлением ошибок

Понятия

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

Расстояние Хэмминга - число единиц в x ^ y. Минимальное расстояние d берётся по различным парам кодовых слов.

Синдром - результаты проверок чётности. В коде Хэмминга при одной ошибке его значение равно номеру изменённого бита.

SEC-DED - исправить любую одну ошибку и обнаружить любые две. К проверкам Хэмминга добавляется общая чётность слова.

A(n,d) - наибольший размер бинарного кода данной длины и расстояния. Линейный код замкнут относительно XOR.

Что унести

Только проверка принадлежности словарю:
    обнаруживает любые d−1 изменений
Исправление до ближайшего допустимого слова:
    гарантирует t ошибок, если 2t < d
Обещание о числе ошибок - часть контракта декодера.

Позиции Хэмминга нумеруются от 1. Проверки занимают 1,2,4,…. Группа проверки 2^i содержит номера с установленным битом i. Для правильного слова XOR номеров единичных позиций равен нулю.

SEC-DED, модель: не больше двух изменённых битов
S=0,  P=0  принять
S≠0, P=1  исправить позицию S
S=0,  P=1  исправить дополнительный бит чётности
S≠0, P=0  обнаружить двойную ошибку, не исправлять
S считается по первой части, P - по всему принятому слову.

При k информационных битах минимальное число проверок Хэмминга r удовлетворяет 2^r ≥ k+r+1. SEC-DED добавляет ещё одну проверку. Для 32 данных: шесть адресных проверок и одна общая, всего 39 битов. Для 64 данных: семь адресных и одна общая, всего 72 бита.

V(n,t) = C(n,0) + ... + C(n,t)
Хэмминг:   A(n,d) ≤ floor(2^n / V(n,floor((d−1)/2)))
Слабая GV: A(n,d) ≥ ceil(2^n / V(n,d−1))
Линейная GV:
    2^r > сумма C(n−1,i), i=0…d−2  => A(n,d) ≥ 2^(n−r)
    Здесь d≥2, знак строгий.
Для чётного d: A(n,d) = A(n−1,d−1).

Ловушки джокера

Обнаружение и исправление перепутаны. Расстояние 3 позволяет проверкой словаря обнаруживать две ошибки; декодер, исправляющий одну, может принять двойную за одиночную и выдать другое сообщение.

Ненулевой синдром всегда исправляют. В SEC-DED сначала нужны оба признака; при чётном слове и ненулевом синдроме исправление запрещено моделью.

Три ошибки считают обнаружимыми автоматически. Они могут выглядеть как одна ошибка другого сообщения; четыре изменения могут дать допустимое слово.

Верхнюю границу принимают за конструкцию. Для A(4,3) упаковка даёт ≤3, но точный максимум равен 2. Свободное место в подсчёте ещё не строит код.