Код Адамара

Код, исправляющий ошибки

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

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

Код Адамара — это код исправления ошибок , названный в честь Жака Адамара , который используется для обнаружения и исправления ошибок при передаче сообщений по очень шумным или ненадежным каналам. В 1971 году код использовался для передачи обратно на Землю фотографий Марса с космического зонда НАСА « Маринер-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-х годов использование этого кода космическими программами более или менее прекратилось, а сеть дальнего космоса НАСА не поддерживает эту схему исправления ошибок для своих антенн, размер которых превышает 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}$

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

Коды Адамара получаются из n - n матрицы Адамара H . В частности, 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) 9 января 2020 г.
2. Амадей, М.; Манзоли, Умберто; Мерани, Мария Луиза (17 ноября 2002 г.). «О назначении кодов Уолша и квазиортогональных кодов в системе DS-CDMA с несколькими несущими и несколькими классами пользователей». Глобальная конференция по телекоммуникациям, 2002. GLOBECOM'02. ИИЭЭ . Том. 1. ИИЭР . стр. 841–845. дои : 10.1109/GLOCOM.2002.1188196. ISBN 0-7803-7632-3.
3. Арора, Санджив ; Барак, Вооз (2009). «Раздел 19.2.2». Вычислительная сложность: современный подход. Издательство Кембриджского университета . ISBN 978-0-521-42426-4.
4. Гурусвами, Венкатесан (2009). Список расшифровок двоичных кодов (PDF) . п. 3.
5. Бозе, Радж Чандра ; Шрикханде, Шарадчандра Шанкар (июнь 1959 г.). «Заметка о результате по теории построения кодов». Информация и контроль . 2 (2): 183–194. CiteSeerX 10.1.1.154.2879 . дои : 10.1016/S0019-9958(59)90376-6. 
6. Лэнгтон, Чаран [в Викиданных] (2002). «Учебное пособие по CDMA: интуитивное руководство по принципам связи» (PDF) . От сложного к реальному. Архивировано (PDF) из оригинала 20 июля 2011 г. Проверено 10 ноября 2017 г.
7. Джаффе, Дэвид Б.; Буюклиев, Илья. «Оптимальные двоичные линейные коды размерностью не более семи». Архивировано из оригинала 8 августа 2007 г. Проверено 21 августа 2007 г.

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

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