Код Адамара

Код исправления ошибок

Матрица расширенного кода Адамара [32, 6, 16] для кода Рида–Маллера (1, 5) космического зонда NASA Mariner 9

Операции XOR
Здесь белые поля обозначают 0
, а красные поля — 1.

Код Адамара — это код с исправлением ошибок, названный в честь французского математика Жака Адамара , который используется для обнаружения и исправления ошибок при передаче сообщений по очень шумным или ненадежным каналам. В 1971 году этот код использовался для передачи фотографий Марса обратно на Землю с космического зонда NASA Mariner 9. [ ^1] Благодаря своим уникальным математическим свойствам код Адамара не только используется инженерами, но и интенсивно изучается в теории кодирования , математике и теоретической информатике . Код Адамара также известен под названиями код Уолша , семейство Уолша [ ^2] и код Уолша–Адамара ^[3] в знак признания американского математика Джозефа Леонарда Уолша .

Код Адамара является примером линейного кода длины над двоичным алфавитом . К сожалению, этот термин несколько двусмыслен, поскольку некоторые источники предполагают длину сообщения , а другие предполагают длину сообщения . В этой статье первый случай называется кодом Адамара , а второй — расширенным кодом Адамара . ${\displaystyle 2^{m}}$ ${\displaystyle k=m}$ ${\displaystyle k=m+1}$

Код Адамара уникален тем, что каждое ненулевое кодовое слово имеет вес Хэмминга ровно , что подразумевает, что расстояние кода также равно . В стандартной нотации теории кодирования для блочных кодов код Адамара является -кодом, то есть это линейный код над двоичным алфавитом , имеет длину блока , длину сообщения (или размерность) и минимальное расстояние . Длина блока очень велика по сравнению с длиной сообщения, но, с другой стороны, ошибки могут быть исправлены даже в чрезвычайно шумных условиях. ${\displaystyle 2^{k-1}}$ ${\displaystyle 2^{k-1}}$ ${\displaystyle [2^{k},k,2^{k-1}]_{2}}$ ${\displaystyle 2^{k}}$ ${\displaystyle k}$ ${\displaystyle 2^{k}/2}$

Расширенный код Адамара — это немного улучшенная версия кода Адамара; это -код и, таким образом, имеет немного лучшую скорость при сохранении относительного расстояния , и, таким образом, является предпочтительным в практических приложениях. В теории связи это просто называется кодом Адамара, и это то же самое, что и код Рида-Маллера первого порядка над двоичным алфавитом. ^[4] ${\displaystyle [2^{k},k+1,2^{k-1}]_{2}}$ ${\displaystyle 1/2}$

Обычно коды Адамара основаны на конструкции Сильвестра матриц Адамара , но термин «код Адамара» также используется для обозначения кодов, построенных из произвольных матриц Адамара , которые не обязательно являются типами Сильвестра. В общем случае такой код не является линейным. Такие коды были впервые построены Раджем Чандрой Бозе и Шарадчандра Шанкаром Шрикханде в 1959 году. ^[5] Если n — размер матрицы Адамара, код имеет параметры , то есть это не обязательно линейный двоичный код с 2 n кодовыми словами длины блока n и минимальным расстоянием n /2. Схема построения и декодирования, описанная ниже, применима для общего n , но свойство линейности и идентификация с кодами Рида–Маллера требуют, чтобы n было степенью 2 и чтобы матрица Адамара была эквивалентна матрице, построенной методом Сильвестра. ${\displaystyle (n,2n,n/2)_{2}}$

Код Адамара — это локально декодируемый код, который позволяет восстанавливать части исходного сообщения с высокой вероятностью, рассматривая только небольшую часть полученного слова. Это приводит к приложениям в теории вычислительной сложности и, в частности, в разработке вероятностно проверяемых доказательств . Поскольку относительное расстояние кода Адамара составляет 1/2, обычно можно надеяться восстановить не более 1/4 части ошибки. Однако, используя декодирование списков , можно вычислить короткий список возможных сообщений-кандидатов, если повреждено менее битов в полученном слове. ${\displaystyle {\frac {1}{2}}-\epsilon }$

В кодовом разделении множественного доступа (CDMA) код Адамара называется кодом Уолша и используется для определения отдельных каналов связи . В литературе по CDMA кодовые слова обычно называют «кодами». Каждый пользователь будет использовать разное кодовое слово или «код» для модуляции своего сигнала. Поскольку кодовые слова Уолша математически ортогональны , сигнал, закодированный по Уолшу, отображается как случайный шум для мобильного терминала , поддерживающего CDMA , если только этот терминал не использует то же кодовое слово, что и для кодирования входящего сигнала . ^[6]

История

Код Адамара — это название, которое чаще всего используется для этого кода в литературе. Однако в современном использовании эти коды исправления ошибок называются кодами Уолша–Адамара.

На это есть причина:

Жак Адамар не изобрел этот код сам, но он определил матрицы Адамара около 1893 года, задолго до того, как в 1940-х годах был разработан первый код с исправлением ошибок — код Хэмминга .

Код Адамара основан на матрицах Адамара, и хотя существует множество различных матриц Адамара, которые можно здесь использовать, обычно для получения кодовых слов кода Адамара используется только конструкция матриц Адамара, предложенная Сильвестром .

Джеймс Джозеф Сильвестр разработал свою конструкцию матриц Адамара в 1867 году, что на самом деле предшествовало работе Адамара над матрицами Адамара. Поэтому название код Адамара оспаривается, и иногда код называют кодом Уолша , в честь американского математика Джозефа Леонарда Уолша .

Дополненный код Адамара использовался во время миссии Mariner 9 1971 года для исправления ошибок передачи изображений. Двоичные значения, используемые во время этой миссии, имели длину 6 бит, что представляло 64 значения в оттенках серого .

Из-за ограничений качества выравнивания передатчика в то время (из-за проблем с доплеровским следящим контуром) максимальная полезная длина данных составляла около 30 бит. Вместо использования кода повторения использовался код Адамара [32, 6, 16].

Ошибки до 7 бит на 32-битное слово можно было исправить с помощью этой схемы. По сравнению с кодом с 5 повторениями , свойства исправления ошибок этого кода Адамара намного лучше, но его скорость сопоставима. Эффективный алгоритм декодирования был важным фактором при решении использовать этот код.

Используемая схема получила название «Зеленая машина». Она использовала быстрое преобразование Фурье , которое может увеличить скорость декодирования в три раза. С 1990-х годов использование этого кода в космических программах более или менее прекратилось, и NASA Deep Space Network не поддерживает эту схему исправления ошибок для своих антенн, которые больше 26 м.

Конструкции

Хотя все коды Адамара основаны на матрицах Адамара, конструкции различаются тонкими способами для разных научных областей, авторов и применений. Инженеры, которые используют коды для передачи данных, и теоретики кодирования , которые анализируют экстремальные свойства кодов, обычно хотят, чтобы скорость кода была как можно выше, даже если это означает, что конструкция становится математически немного менее элегантной.

С другой стороны, для многих приложений кодов Адамара в теоретической информатике не так важно достичь оптимальной скорости, и поэтому более простые конструкции кодов Адамара являются предпочтительными, поскольку их можно анализировать более элегантно.

Строительство с использованием внутренних изделий

При наличии двоичного сообщения длины код Адамара кодирует сообщение в кодовое слово с помощью функции кодирования. Эта функция использует внутреннее произведение двух векторов , которое определяется следующим образом: ${\displaystyle x\in \{0,1\}^{k}}$ ${\displaystyle k}$ ${\displaystyle {\text{Had}}(x)}$ ${\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.}$ ${\displaystyle \langle x,y\rangle }$ ${\displaystyle x,y\in \{0,1\}^{k}}$

${\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.}$

Тогда кодировка Адамара определяется как последовательность всех внутренних произведений с : ${\displaystyle x}$ ${\displaystyle x}$

${\displaystyle {\text{Had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}}$

Как упоминалось выше, на практике используется расширенный код Адамара, поскольку сам код Адамара несколько расточителен. Это происходит потому, что если первый бит равен нулю, , то скалярное произведение не содержит никакой информации о , и, следовательно, невозможно полностью декодировать только из этих позиций кодового слова. С другой стороны, когда кодовое слово ограничено позициями, где , все еще возможно полностью декодировать . Следовательно, имеет смысл ограничить код Адамара этими позициями, что приводит к расширенному кодированию Адамара ; то есть . ${\displaystyle y}$ ${\displaystyle y_{1}=0}$ ${\displaystyle x_{1}}$ ${\displaystyle x}$ ${\displaystyle y_{1}=1}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}$

Построение с использованием матрицы-генератора

Код Адамара является линейным кодом, и все линейные коды могут быть сгенерированы матрицей- генератором . Это матрица, которая выполняется для всех , где сообщение рассматривается как вектор-строка, а произведение вектор-матрица понимается в векторном пространстве над конечным полем . В частности, эквивалентный способ записи определения внутреннего произведения для кода Адамара возникает при использовании матрицы-генератора, столбцы которой состоят из всех строк длины , то есть, ${\displaystyle G}$ ${\displaystyle {\text{Had}}(x)=x\cdot G}$ ${\displaystyle x\in \{0,1\}^{k}}$ ${\displaystyle x}$ ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle y}$ ${\displaystyle k}$

${\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,.}$

где - -й двоичный вектор в лексикографическом порядке . Например, матрица генератора для кода Адамара размерности : ${\displaystyle y_{i}\in \{0,1\}^{k}}$ ${\displaystyle i}$ ${\displaystyle k=3}$

${\displaystyle G={\begin{bmatrix}0&0&0&0&1&1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{bmatrix}}.}$

Матрица является -матрицей и порождает линейный оператор . ${\displaystyle G}$ ${\displaystyle (k\times 2^{k})}$ ${\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}$

Генераторная матрица расширенного кода Адамара получается путем ограничения матрицы столбцами, первый элемент которых равен единице. Например, генераторная матрица для расширенного кода Адамара размерности имеет вид: ${\displaystyle G}$ ${\displaystyle k=3}$

${\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1&1\\0&1&0&1\end{bmatrix}}.}$

Тогда — линейное отображение с . ${\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}}$ ${\displaystyle {\text{pHad}}(x)=x\cdot G'}$

Для общего случая матрица генератора расширенного кода Адамара является матрицей проверки на четность для расширенного кода Хэмминга длины и размерности , что делает расширенный код Адамара дуальным кодом расширенного кода Хэмминга. Следовательно, альтернативный способ определения кода Адамара заключается в терминах его матрицы проверки на четность: матрица проверки на четность кода Адамара равна матрице генератора кода Хэмминга. ${\displaystyle k}$ ${\displaystyle 2^{k-1}}$ ${\displaystyle 2^{k-1}-k}$

Построение с использованием общих матриц Адамара

Коды Адамара получаются из матрицы Адамара H размером n на n . В частности, 2 n кодовых слов кода являются строками H и строками − H. Чтобы получить код над алфавитом {0,1}, к элементам матрицы применяется отображение −1 ↦ 1, 1 ↦ 0 или, что эквивалентно, x  ↦ (1 −  x )/2. То, что минимальное расстояние кода равно n /2, следует из определяющего свойства матриц Адамара, а именно, что их строки взаимно ортогональны. Это означает, что две различные строки матрицы Адамара отличаются ровно на n /2 позиций, и, поскольку отрицание строки не влияет на ортогональность, что любая строка H отличается от любой строки − H также на n /2 позиций, за исключением случаев, когда строки соответствуют, в этом случае они отличаются на n позиций.

Чтобы получить расширенный код Адамара, представленный выше, с помощью , выбранная матрица Адамара H должна иметь тип Сильвестра, что приводит к длине сообщения . ${\displaystyle n=2^{k-1}}$ ${\displaystyle \log _{2}(2n)=k}$

Расстояние

Расстояние кода — это минимальное расстояние Хэмминга между любыми двумя различными кодовыми словами, т. е. минимальное количество позиций, в которых различаются два различных кодовых слова. Поскольку код Уолша–Адамара является линейным кодом , расстояние равно минимальному весу Хэмминга среди всех его ненулевых кодовых слов. Все ненулевые кодовые слова кода Уолша–Адамара имеют вес Хэмминга ровно по следующему аргументу. ${\displaystyle 2^{k-1}}$

Пусть будет ненулевым сообщением. Тогда следующее значение в точности равно доле позиций в кодовом слове, которые равны единице: ${\displaystyle x\in \{0,1\}^{k}}$

${\displaystyle \Pr _{y\in \{0,1\}^{k}}{\big [}({\text{Had}}(x))_{y}=1{\big ]}=\Pr _{y\in \{0,1\}^{k}}{\big [}\langle x,y\rangle =1{\big ]}\,.}$

Тот факт, что последнее значение равно в точности, называется принципом случайной подсуммы . Чтобы убедиться в его истинности, предположим без потери общности, что . Тогда при условии значений событие эквивалентно для некоторых в зависимости от и . Вероятность того, что произойдет, равна в точности . Таким образом, фактически все ненулевые кодовые слова кода Адамара имеют относительный вес Хэмминга , и, таким образом, его относительное расстояние равно . ${\displaystyle 1/2}$ ${\displaystyle x_{1}=1}$ ${\displaystyle y_{2},\dots ,y_{k}}$ ${\displaystyle y_{1}\cdot x_{1}=b}$ ${\displaystyle b\in \{0,1\}}$ ${\displaystyle x_{2},\dots ,x_{k}}$ ${\displaystyle y_{2},\dots ,y_{k}}$ ${\displaystyle y_{1}=b}$ ${\displaystyle 1/2}$ ${\displaystyle 1/2}$ ${\displaystyle 1/2}$

Относительное расстояние дополненного кода Адамара также равно , но оно больше не обладает свойством, что каждое ненулевое кодовое слово имеет вес точно, поскольку вектор all s является кодовым словом дополненного кода Адамара. Это происходит потому, что вектор кодирует в . Кроме того, всякий раз, когда не равно нулю и не является вектором , принцип случайной подсуммы применяется снова, и относительный вес равен точно . ${\displaystyle 1/2}$ ${\displaystyle 1/2}$ ${\displaystyle 1}$ ${\displaystyle 1^{2^{k-1}}}$ ${\displaystyle x=10^{k-1}}$ ${\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}}$ ${\displaystyle x}$ ${\displaystyle 10^{k-1}}$ ${\displaystyle {\text{Had}}(x)}$ ${\displaystyle 1/2}$

Локальная декодируемость

Локально декодируемый код — это код, который позволяет с высокой вероятностью восстановить один бит исходного сообщения, просматривая лишь небольшую часть полученного слова.

Код является -запросным локально декодируемым , если бит сообщения, , может быть восстановлен путем проверки битов полученного слова. Более формально, код, , является -локально декодируемым, если существует вероятностный декодер, , такой, что (Примечание: представляет расстояние Хэмминга между векторами и ) : ${\displaystyle q}$ ${\displaystyle x_{i}}$ ${\displaystyle q}$ ${\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}$ ${\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}$ ${\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}}$ ${\displaystyle \Delta (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}}$, подразумевает, что ${\displaystyle \Delta (y,C(x))\leq \delta n}$ ${\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}$

Теорема 1: Код Уолша–Адамара локально декодируем для всех . ${\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}$ ${\displaystyle 0\leq \delta \leq {\frac {1}{4}}}$

Лемма 1: Для всех кодовых слов в коде Уолша–Адамара, , , где представляют биты в позициях и соответственно, а представляет бит в позиции . ${\displaystyle c}$ ${\displaystyle C}$ ${\displaystyle c_{i}+c_{j}=c_{i+j}}$ ${\displaystyle c_{i},c_{j}}$ ${\displaystyle c}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle c_{i+j}}$ ${\displaystyle (i+j)}$

Доказательство леммы 1

Пусть будет кодовым словом, соответствующим сообщению . ${\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})}$ ${\displaystyle C}$ ${\displaystyle x}$

Пусть будет порождающей матрицей . ${\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}$ ${\displaystyle C}$

По определению, . Отсюда, . По построению , . Следовательно, подстановкой, . ${\displaystyle c_{i}=x\cdot g_{i}}$ ${\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})}$ ${\displaystyle G}$ ${\displaystyle g_{i}+g_{j}=g_{i+j}}$ ${\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}$

Доказательство теоремы 1

Для доказательства теоремы 1 построим алгоритм декодирования и докажем его корректность.

Алгоритм

Ввод: полученное слово ${\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}$

Для каждого : ${\displaystyle i\in \{1,\dots ,n\}}$

1. Выбирайте равномерно наугад. ${\displaystyle j\in \{0,\dots ,2^{n}-1\}}$
2. Выберите такой , что , где - -й стандартный базисный вектор , а - побитовое исключающее ИЛИ и . ${\displaystyle k\in \{0,\dots ,2^{n}-1\}}$ ${\displaystyle j+k=e_{i}}$ ${\displaystyle e_{i}}$ ${\displaystyle i}$ ${\displaystyle j+k}$ ${\displaystyle j}$ ${\displaystyle k}$
3. ${\displaystyle x_{i}\gets y_{j}+y_{k}}$.

Вывод: Сообщение ${\displaystyle x=(x_{1},\dots ,x_{n})}$

Доказательство правильности

Для любого сообщения, и принятое слово , которое отличается от не более чем на долю бит, может быть декодировано с вероятностью не менее . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle c=C(x)}$ ${\displaystyle \delta }$ ${\displaystyle x_{i}}$ ${\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}$

По лемме 1, . Поскольку и выбираются равномерно, вероятность того, что не более . Аналогично, вероятность того, что не более . По границе объединения вероятность того, что либо или не соответствуют соответствующим битам в , не более . Если и соответствуют , то будет применена лемма 1, и, следовательно, будет вычислено надлежащее значение . Следовательно, вероятность правильного декодирования не менее . Следовательно, и для того , чтобы быть положительным, . ${\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle y_{j}\not =c_{j}}$ ${\displaystyle \delta }$ ${\displaystyle y_{k}\not =c_{k}}$ ${\displaystyle \delta }$ ${\displaystyle y_{j}}$ ${\displaystyle y_{k}}$ ${\displaystyle c}$ ${\displaystyle 2\delta }$ ${\displaystyle y_{j}}$ ${\displaystyle y_{k}}$ ${\displaystyle c}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle 1-2\delta }$ ${\displaystyle \epsilon ={\frac {1}{2}}-2\delta }$ ${\displaystyle \epsilon }$ ${\displaystyle 0\leq \delta \leq {\frac {1}{4}}}$

Следовательно, код Уолша–Адамара локально декодируется для . ${\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}$ ${\displaystyle 0\leq \delta \leq {\frac {1}{4}}}$

Оптимальность

Для k  ≤ 7 линейные коды Адамара оказались оптимальными в смысле минимального расстояния. ^[7]

Смотрите также

• Последовательность Задова–Чу — улучшение по сравнению с кодами Уолша–Адамара

Ссылки

1. Малек, Массуд (2006). "Коды Хадармарка". Теория кодирования (PDF) . Архивировано из оригинала (PDF) 2020-01-09.
2. Амадей, М.; Манзоли, Умберто; Мерани, Мария Луиза (2002-11-17). «О назначении кодов Уолша и квазиортогональных кодов в системе DS-CDMA с несколькими несущими и несколькими классами пользователей». Глобальная конференция по телекоммуникациям, 2002. GLOBECOM'02. IEEE . Том 1. IEEE . С. 841–845. doi :10.1109/GLOCOM.2002.1188196. ISBN 0-7803-7632-3.
3. Арора, Санджив ; Барак, Боаз (2009). "Раздел 19.2.2". Вычислительная сложность: современный подход. Cambridge University Press . ISBN 978-0-521-42426-4.
4. Гурусвами, Венкатесан (2009). Список декодирования двоичных кодов (PDF) . стр. 3.
5. Бозе, Радж Чандра ; Шрикханде, Шарадчандра Шанкар (июнь 1959). «Заметка о результате в теории построения кода». Информация и управление . 2 (2): 183–194. CiteSeerX 10.1.1.154.2879 . doi :10.1016/S0019-9958(59)90376-6. 
6. Лэнгтон, Чаран [на Wikidata] (2002). "Учебник CDMA: Интуитивное руководство по принципам связи" (PDF) . От сложных к действительным. Архивировано (PDF) из оригинала 2011-07-20 . Получено 10.11.2017 .
7. Джаффе, Дэвид Б.; Буюклиев, Илья. "Оптимальные двоичные линейные коды размерности не более семи". Архивировано из оригинала 2007-08-08 . Получено 2007-08-21 .

Дальнейшее чтение

• Рудра, Атри. "Код Хэмминга и граница Хэмминга" (PDF) . Конспект лекций .
• Рудольф, Дитмар; Рудольф, Маттиас (12.04.2011). "46.4. Коды Адамара или Уолша". Modulationsverfahren (PDF) (на немецком языке). Котбус, Германия: Бранденбургский технический университет (BTU). стр. 214. Архивировано (PDF) из оригинала 16.06.2021 . Получено 14.06.2021 .(xiv+225 страниц)