Код Адамара

Код Адамара строится из строк матрицы Адамара — таблицы из ±1, строки которой попарно ортогональны. Его кодовые слова очень далеки друг от друга, поэтому код исправляет много ошибок в блоке, расплачиваясь большой избыточностью. Такой код передавал на Землю снимки Марса с зонда Mariner 9.

Матрицы Адамара

Ортогональность двух строк из ±1 означает, что их скалярное произведение равно 0: строки совпадают ровно в n/2 позициях и различаются в остальных n/2. Перестановка строк или столбцов и умножение строки на −1 сохраняют это свойство.

Доказательство. Умножим столбцы на ±1 так, чтобы первая строка состояла из единиц. Пусть среди первых трёх строк a, b, c, d — число столбцов вида (+,+,+), (+,+,−), (+,−,+), (+,−,−). Ортогональность строк 1–2, 1–3, 2–3 и равенство a + b + c + d = n дают a = b = c = d = n/4.

Верно ли обратное — что для каждого n, кратного 4, матрица существует, — неизвестно: это знаменитая гипотеза Адамара. Наименьший порядок, для которого матрица до сих пор не найдена, — 668.

Конструкция Сильвестра

Для порядков n = 2^r матрицы строятся удвоением:

Если строки H_n ортогональны, то и строки H_(2n) тоже. Строки вида (u, u) и (v, v) при u ≠ v дают u·v + u·v = 0 (так же для (u, −u) и (v, −v)), а строки (u, u) и (v, −v) — u·v − u·v = 0 при любых u, v. Элемент матрицы Сильвестра: H[i][j] = (−1)^⟨i, j⟩, где ⟨i, j⟩ — скалярное произведение двоичных записей номеров по модулю 2.

Код Адамара

Заменим +1 на бит 0, а −1 — на бит 1. Кодовыми словами объявим все строки H_n и их инверсии (строки −H_n) — всего 2n слов длины n. При n = 2^r одно слово несёт k = log₂(2n) = r + 1 бит данных:

• первый бит данных — бит знака: брать строку как есть (0) или инвертированной (1);
• остальные r бит — номер строки i.

Бит j кодового слова равен знак ⊕ ⟨i, j⟩. Это код Рида–Маллера первого порядка RM(1, r): значения аффинной функции знак ⊕ i_1·j_1 ⊕ … ⊕ i_r·j_r во всех 2^r точках.

Две разные строки различаются в n/2 позициях (ортогональность). Строка и инверсия другой строки — тоже в n/2. Строка и её собственная инверсия — во всех n.

Сравните с кодом Хэмминга (15,11): скорость 0,73, но исправляется только одна ошибка. Выбор кода — компромисс между надёжностью и объёмом передаваемых данных.

Декодирование по максимуму корреляции

Принятый блок переводим обратно в ±1 (0 → +1, 1 → −1) и вычисляем его скалярное произведение (корреляцию) с каждой строкой H:

• строка с наибольшей по модулю корреляцией — номер переданной строки;
• знак корреляции — бит знака (минус — строка была инвертирована);
• число ошибок в блоке равно (n − |корреляция|)/2.

Каждая ошибка уменьшает корреляцию с правильной строкой на 2 и меняет корреляцию с другими строками не больше чем на 2. Пока ошибок не больше t, правильная строка остаётся «победителем». Все корреляции сразу можно вычислить быстрым преобразованием Адамара за O(n log n) операций вместо O(n²).

Применение

• Космическая связь: код (32,6) с расстоянием 16 использовался на зондах программы «Маринер», в частности Mariner 9 (1971–1972) при передаче снимков Марса, — канал был очень зашумлён, а скорость не критична.
• Последовательности Уолша (строки матрицы Сильвестра) разделяют каналы в сотовой связи CDMA.
• Матрицы Адамара применяются в планировании экспериментов, обработке сигналов и сжатии изображений.

Вопросы для самопроверки

1. Постройте H_4 по конструкции Сильвестра и проверьте ортогональность строк 1 и 2.
   Ответ

   Строки: (+ + + +), (+ − + −), (+ + − −), (+ − − +). Строки 1 и 2: 1 − 1 − 1 + 1 = 0.
2. Сколько ошибок исправляет код Адамара порядка 64?
   Ответ

   d = 32, t = ⌊31/2⌋ = 15.
3. Принятый блок дал максимальную по модулю корреляцию −4 при n = 8. Что передано и сколько ошибок?
   Ответ

   Инвертированная строка (бит знака 1); ошибок (8 − 4)/2 = 2 — больше, чем t = 1, поэтому результат ненадёжен (возможна ничья с другими строками).