Помехоустойчивое кодирование

Организационные моменты
Дополнительные задания (СНО, github, OCW).
«Критерий бабушки» vs «Критерий Пушкина».
Рубежное тестирование 24 октября (взять с собой только две ручки).

Причины сбоев памяти
Причины единичных битовых ошибок:
Альфа-частицы от примесей в чипе микросхемы.
Нейтроны из фонового космического излучения.
Частота единичных битовых ошибок (на 1 GB):
От 1 раза в час до 1 раза в тысячелетие (по данным исследования Google получилось 1 раз в сутки)
Как бороться:
Бит чётности.
Тройная модульная избыточность.
Код Хэмминга.
Одновременно 1 и 3 (SECDED).

Вспомним прошлую лекцию…
Код Хэмминга (КХ) – блочный равномерный разделимый самокорректирующийся код.
Назначение КХ – исправление одиночных битовых ошибок, возникших при передаче или хранении данных.
На каждые i информационных бит используется r проверочных.
Ричард Уэсли
Хэмминг
(1915-1998)

Рассмотрим все возможные варианты попарных сумм
Синдром последовательности S (s1, s2)
– набор контрольных сумм
информационных и проверочных разрядов
r1 – бит чётности, проверочный разряд №1
r2 – проверочный разряд №2
Пример КХ для r = 2

Пример КХ для r = 3

Пример КХ для r = 3

КХ для r = 3. Пояснения

КХ для r = 3. Подробно

По таблице видно, за какие информационные биты отвечает каждый проверочный бит: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N
Аналогично с ошибочным битом.
Пример №1: Имеем синдром S (0,0,1,1). Проверяем, за какой бит отвечают только r3 и r4. Ответ: i8 (12-й символ сообщения).
Пример КХ для r = 4

15
11
13
14
7
6
9
3
12
2
1
4
8
5?
10?
Диаграмма Венна для КХ для r = 4

Определение минимального количества контрольных разрядов:
Классические коды
Хэмминга
с маркировкой (n, i):
(7, 4); (15, 11); (31, 26)
r
Коэффициент избыточности = --------------------------------
i + r

Схема кодирования КХ

Схема декодирования КХ

Расстояние Хэмминга
Расстояние Хэмминга (РХ) – количество символов, которое надо изменить в одном слове, чтобы получить другое (применяется к измерению расстояния между двумя словами в коде постоянной длины).
Кодовое расстояние (d) – минимальное РХ среди всех слов алфавита в коде постоянной длины.
Количество обнаруживаемых ошибок = (d - 1).
Количество исправляемых ошибок = floor((d - 1)/2).