Код Адамара

Код Адамара
Названный в честь	Жак Адамар
Классификация
Тип	Линейный блочный код
Длина блока	$n=2^{k}$
Длина сообщения	$k$
Ставка	$k/2^{k}$
Расстояние	$d=2^{k-1}$
Размер алфавита	$2$
Обозначения	$[2^{k},k,2^{k-1}]_{2}$-код

Расширенный код Адамара
Названный в честь	Жак Адамар
Классификация
Тип	Линейный блочный код
Длина блока	$n=2^{k}$
Длина сообщения	$k+1$
Ставка	$(k+1)/2^{k}$
Расстояние	$d=2^{k-1}$
Размер алфавита	$2$
Обозначения	$[2^{k},k+1,2^{k-1}]_{2}$-код

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

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

Код Адамара — это код исправления ошибок , названный в честь Жака Адамара , который используется для обнаружения и исправления ошибок при передаче сообщений по очень шумным или ненадежным каналам. В 1971 году код использовался для передачи фотографий Марса обратно на Землю с космического зонда НАСА « Маринер-9» . Благодаря своим уникальным математическим свойствам код Адамара не только используется инженерами, но и интенсивно изучается в теории кодирования , математике и теоретической информатике . Код Адамара известен также под названиями код Уолша , семейство Уолша , и код Уолша – Адамара в знак признания американского математика Джозефа Леонарда Уолша .

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

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

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

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

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

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

История

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

Для этого есть причина:

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

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

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

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

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

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

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

Конструкции

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

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

внутренних

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

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

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

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

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

Построение с использованием порождающей матрицы

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

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

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

$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}}.$

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

Генераторная матрица расширенного кода Адамара получается ограничением матрицы $G$к столбцам, первая запись которых равна единице. Например, порождающая матрица расширенного кода Адамара размерности $k=3$ является:

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

Затем ${\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}$ является линейным отображением с ${\text{pHad}}(x)=x\cdot G'$.

Для общего $k$, порождающая матрица расширенного кода Адамара является матрицей проверки четности расширенного кода Хэмминга длины $2^{k-1}$ и размер $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 позициям.

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

Расстояние

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

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

$\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 ]}\,.$

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

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

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

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

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

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

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

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

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

---

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

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

По определению, $c_{i}=x\cdot g_{i}$. Из этого, $c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})$. По строительству $G$, $g_{i}+g_{j}=g_{i+j}$. Следовательно, путем замены $c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}$.

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

---

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

См. также

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

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

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