Archive for Август 2010

Некоторые факты о коде Адамара

Август 18, 2010

Пусть у нас есть строка x \in \{0, 1\}^n. Построим по нему код Адамара — строку C(x) длины 2^n, которая является конкатенацией скалярных произведений x со всеми строками длины n (то есть C(x)_y = (x, y)). Перечислим некоторые полезные свойства этого расточительного кода:

  1. Любые два кодовых слова отличаются в половине позиций.
  2. Код Адамара является линейным.
  3. Пусть z — строка длины 2^n. Тогда количество кодовых слов, расстояние от z до которых не превосходит (1/2 - \epsilon) 2^n, не превосходит 1 / 4\epsilon^2.
  4. Код Адамара позволяет производить локальное декодирование за 2 запроса. Более точно, пусть z — строка длины 2^n, которая отличается от C(x) в (1/4 - \epsilon) 2^n позициях. Тогда z_r \oplus z_{r \oplus e_i} = x_i с вероятностью не менее 1/2 + 2\epsilon (r — случайная строка длины n, e_i — строка с единственной единицей на позиции i).
  5. Код Адамара позволяет производить локальное вероятностное декодирование списком. Пусть z — строка длины 2^n. Тогда существует полиномиальный по n, 1 / \epsilon и 1 / \delta алгоритм, который с вероятностью не менее 1 - \delta выдает список, который содержит все слова, коды Адамара которых находятся на расстоянии не более (1/2 - \epsilon) 2^n от z (и может содержать еще что-то).
  6. Свойство «быть кодовым словом кода Адамара» является тестируемым. Если z = C(x), то z_u \oplus z_{v} = z_{u \oplus v} с вероятностью 1. Если z находится на расстоянии не менее \epsilon 2^n от всех кодовых слов, то z_u \oplus z_{v} = z_{u \oplus v} с вероятностью не более 1 - \epsilon.
Реклама