Коды Адамара

Определение

Код Адамара $H\colon \{0, 1\}^n \rightarrow \{0, 1\}^{2^n}$. $$H(x_1, \ldots, x_n) = (x_1y_1 + \ldots + x_ny_n)\vert_{(y_1, \ldots, y_n) \in \{0, 1\}^{n}}$$

Коды Адамара могут быть декодированы списком:

Если расстояние Хэминга $\rho_H(z, \bar{z}) \le \frac{1}{2} - \varepsilon$, то за время $poly(\frac{n}{\varepsilon})$ можно выдать полиномиальный список, содержащий прообраз $z$, где $z, \bar{z} \in \{0, 1\}^{2^n}, z \in \mathrm{Im} H$ (последнее означает, что $z$ - кодовое слово $H$).

Доказательство (существования декодирования)

Определение

Расстояние Хэмминга $\rho_H(t, t') = \frac{\#\{i\colon t_i \ne t_i'\}}{2^n}$

К $\bar{z}$ произвольный доступ: по $j$ за константное время можно найти $\bar{z}_j$

Без искажений достаточно запросить $n$ битов с номерами $(1, 0, \ldots, 0), \ldots, (0, \ldots, 0, 1)$

Обозначим $z(y)$ - соответствующий бит $z$.

Утверждение

$z(y + r) = z(y) + z(r)$

Из утверждения $z(y) = z(y + r) + z(r) = $ большинство из $\bar{z}(y + r) + z(r)$

Идея

Выберем специальным образом попарно независимые $r_1, \ldots, r_s$; выберем $z_y$ как большинство из $\bar{z}(y + r_i) + z(r_i)$

Выбор $r_1, \ldots, r_s$:

$A$ - матрица размера $(2^m - 1)\times m$, строки - ненулевые элементы $\{0, 1\}^m$. Пусть $s = 2^m - 1$.

Утверждение

$u$ - случайный вектор $m\times 1 \Rightarrow$ величины $Au$ попарно независимы.

Возьмем $u_1, \ldots, u_n$ - случайные векторы размера $m \times 1$. $U$ - случайная матрица размера $m \times n$.

$R = (r_1, \ldots, r_s)^T = AU$, матрица рамера $(2^m - 1)\times n$.
$$r_i = A_iU = (A_{i_1}e_1 + \ldots + A_{i_m}e_m)U = A_{i_1}e_1U + \ldots + A_{i_m}e_mU = A_{i_1}\bar{U}_1 + \ldots + A_{i_m}\bar{U}_m$$ $$z(r_i) = A_{i_1}z(\bar{U}_1) + \ldots + A_{i_m}z(\bar{U}_m)$$

То есть достаточно задать $z(\bar{U}_1),\ldots, z(\bar{U}_m)$ чтобы вычислить $z(r_i)$. Но все эти $2^m$ вариантов можно перебрать. Для каждого варианта вычисляем $z(r_i)$ и имея $\bar{z}$ с произвольным доступом, вычисляем значения по большинству.

Еще раз конструкция: для фиксированного набора $z(\bar{u}_1), \ldots, z(\bar{u}_m)$ при $j = 1, \ldots, n$. $z(e_j)$ выбирается как большинство из $\bar{z}(e_j + r_i) + z(r_i)$
$\xi_i$ - случайная величина равная $1$, если и только если $z(y) \ne \bar{z}(y + r_i) + z(r_i)$ $$Pr\{\xi_i = 1\} \le \frac{1}{2} - \varepsilon$$ Нужно посчитать вероятность $Pr\{\frac{1}{s}(\xi_1 + \ldots + \xi_s) \le \frac{1}{2}\}$ для попарно независимых $\xi_1, \ldots, \xi_s$