Код Адамара

редактировать

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

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

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

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

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

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

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

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

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

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

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

Содержание

1 История
2 Конструкции
- 2.1 Построение с использованием внутренних произведений
- 2.2 Построение с использованием матрицы генератора
- 2.3 Построение с использованием общих матриц Адамара
3 Расстояние
4 Локальная декодируемость
- 4.1 Доказательство леммы 1
- 4.2 Доказательство теоремы 1
  - 4.2.1 Алгоритм
  - 4.2.2 Доказательство корректности
5 Оптимальность
6 См. Также
7 Примечания
8 Ссылки

История

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

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

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

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

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

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

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

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

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

Конструкции

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

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

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

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

⟨x, y⟩ = ∑ i = 1 kxiyi mod 2. {\ displaystyle \ langle x, y \ rangle = \ sum _ {i = 1} ^ {k} x_ {i} y_ {i} \ {\ bmod {\}} 2 \,.}

\ langle x, y \ rangle = \ sum_ {i = 1} ^ {k} x_i y_i \ \ bmod \ 2 \,.

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

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

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

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

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

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

G = (↑ ↑ ↑ y 1 y 2… y 2 k ↓ ↓ ↓). {\ displaystyle G = {\ begin {pmatrix} \ uparrow \ uparrow \ uparrow \\ y_ {1} y_ {2} \ dots y_ {2 ^ {k}} \\\ downarrow \ downarrow \ downarrow \ end {pmatrix}} \,.}

G = \ begin {pmatrix} \ uparrow \ uparrow \ uparrow \\ y_1 y_2 \ dots y_ {2 ^ k} \\ \ downarrow \ downarrow \ downarrow \ end {pmatrix} \,.

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

G = [0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1]. {\ displaystyle G = {\ begin {bmatrix} 0 0 0 0 1 1 1 1 \\ 0 0 1 1 0 0 1 1 1 \\ 0 1 0 1 0 1 0 1 \ end {bmatrix}}.}

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 {\ displaystyle G126}$ - это a>(k × 2 k) {\ displaystyle (k \ times 2 ^ {k})} $(k \ times 2 ^ k)$ -матрица и дает начало линейному оператору $Было: {0, 1} к → {0, 1} 2 к {\ displaystyle {\ text {Had}}: \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {2 ^ {k}} }$ $\ text {Had}: \ {0,1 \} ^ k \ to \ {0,1 \} ^ {2 ^ k}$ .

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

G ′ = [1 1 1 1 0 0 1 1 0 1 0 1]. {\ displaystyle G '= {\ begin {bmatrix} 1 1 1 1 \\ 0 0 1 1 \\ 0 1 0 1 \ end {bmatrix}}.}

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

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

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

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

Коды Адамара получаются из n × n матрицы Адамара H. В частности, 2n кодовых слов кода - это строки 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 {\ displaystyle n = 2 ^ {k-1}}$ $n = 2 ^ {k-1}$ , выбранная матрица Адамара H должна быть типа Сильвестра, что дает длину сообщения $log 2 ⁡ (2 n) = k {\ displaystyle \ log _ {2} (2n) = k}$ $\ log_2 (2n) = k$ .

Distance

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

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

Pr y ∈ {0, 1} k [(Had (x)) y = 1] = Pr y ∈ {0, 1} k [⟨x, y⟩ = 1]. {\ 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]} \,.}

\ 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 {\ displaystyle 1/2}$ $1/2$ и называется принципом случайной подсуммы. Чтобы убедиться, что это правда, предположим без ограничения общности, что $x 1 = 1 {\ displaystyle x_ {1} = 1}$ $x_ {1} = 1$ . Затем, когда обусловлено значениями $y 2,…, yk {\ displaystyle y_ {2}, \ dots, y_ {k}}$ $y_2, \ dots, y_k$ , событие эквивалентно $y 1 ⋅ Икс 1 знак равно b {\ displaystyle y_ {1} \ cdot x_ {1} = b}$ $y_1 \ cdot x_1 = b$ для некоторых $b ∈ {0, 1} {\ displaystyle b \ in \ {0,1 \}}$ $b \ in \ {0,1 \}$ в зависимости от $x 2,…, xk {\ displaystyle x_ {2}, \ dots, x_ {k}}$ $x_2, \ dots, x_k$ и $y 2,…, yk {\ displaystyle y_ {2}, \ dots, y_ {k}}$ $y_2, \ dots, y_k$ . Вероятность того, что произойдет $y 1 = b {\ displaystyle y_ {1} = b}$ $y_1 = b$ , равна точно $1/2 {\ displaystyle 1/2}$ $1/2$ . Таким образом, фактически все ненулевые кодовые слова кода Адамара имеют относительный вес Хэмминга $1/2 {\ displaystyle 1/2}$ $1/2$ , и, таким образом, их относительное расстояние составляет $1 / 2 {\ displaystyle 1/2}$ $1/2$ .

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

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

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

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

$∀ x ∈ { 0, 1} К, ∀ Y ∈ {0, 1} n {\ displaystyle \ forall x \ in \ {0,1 \} ^ {k}, \ forall y \ in \ {0,1 \} ^ {n }}$ $\ forall x \ in \ {0, 1 \} ^ k, \ forall y \ in \ {0,1 \} ^ n$ , $Δ (y, C (x)) ≤ δ n {\ displaystyle \ Delta (y, C (x)) \ leq \ delta n}$ $\ Delta (y, C ( x)) \ leq \ delta n$ означает, что $P r [ D (Y) я знак равно xi] ≥ 1 2 + ϵ, ∀ я ∈ [k] {\ displaystyle Pr [D (y) _ {i} = x_ {i}] \ geq {\ frac {1} {2} } + \ epsilon, \ forall i \ in [k]}$ $Pr [D (y) _i = x_i] \ geq \ frac {1} {2 } + \ epsilon, \ forall i \ in [k]$

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

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

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

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

Пусть $G = (↑ ↑ ↑ g 0 g 1… g 2 n - 1 ↓ ↓ ↓) {\ displaystyle G = {\ begin {p матрица} \ uparrow \ uparrow \ uparrow \\ g_ {0} g_ {1} \ dots g_ {2 ^ {n} -1} \\\ downarrow \ downarrow \ downarrow \ end {pmatrix}}}$ $G = \ begin {pmatrix} \ uparrow \ uparrow \ uparrow \\ g_0 g_1 \ dots g_ {2 ^ n-1} \\ \ downarrow \ downarrow \ downarrow \ end {pmatrix}$ быть образующей матрицей $C {\ displaystyle C}$ $C$ .

По определению, $ci = x ⋅ gi {\ displaystyle c_ {i} = x \ cdot g_ {i}}$ $c_i = x \ cdot g_i$ . Отсюда $ci + cj = x ⋅ gi + x ⋅ gj = x ⋅ (gi + gj) {\ displaystyle c_ {i} + c_ {j} = x \ cdot g_ {i} + x \ cdot g_ {j} = x \ cdot (g_ {i} + g_ {j})}$ $c_i + c_j = x \ cdot g_i + x \ cdot g_j = x \ cdot (g_i + g_j)$ . По построению $G {\ displaystyle G}$ $G$ , $g i + g j = g i + j {\ displaystyle g_ {i} + g_ {j} = g_ {i + j}}$ $g_i + g_j = g_ {i + j}$ . Следовательно, путем подстановки $ci + cj = x ⋅ gi + j = ci + j {\ displaystyle c_ {i} + c_ {j} = x \ cdot g_ {i + j} = c_ {i + j} }$ $c_i + c_j = x \ cdot g_ {i + j} = c_ {i + j}$ .

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

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

Алгоритм

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

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

Выберите $j ∈ {0,…, 2 n - 1} {\ displaystyle j \ in \ {0, \ dots, 2 ^ {n} -1 \}}$ $j \ in \ {0, \ dots, 2 ^ n-1 \}$ равномерно случайным образом
Выберите $k ∈ {0,…, 2 n - 1} {\ displaystyle k \ in \ {0, \ dots, 2 ^ {n} -1 \}}$ $k \ in \ {0, \ dots, 2 ^ n-1 \}$ так, чтобы $j + k = ei {\ displaystyle j + k = e_ {i}}$ $j + k = e_i$ где $j + k {\ displaystyle j + k}$ $j + k$ - побитовый xor для $j {\ displaystyle j}$ $j$ и $k {\ displaystyle k}$ $k$ .
$xi ← yj + yk {\ displaystyle x_ {i} \ получает y_ {j} + y_ {k} }$ $x_i \ получает y_j + y_k$

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

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

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

По лемме 1, $cj + ck = cj + k = x ⋅ gj + k = x ⋅ ei = xi {\ displaystyle c_ {j} + c_ {k} = c_ {j + k} = x \ cdot g_ {j + k} = x \ cdot e_ {i} = x_ {i}}$ $c_j + c_k = c_ {j + k} = x \ cdot g_ {j + k} = x \ cdot e_i = x_i$ . Поскольку $j {\ displaystyle j}$ $j$ и $k {\ displaystyle k}$ $k$ выбираются равномерно, вероятность того, что $yj ≠ cj {\ displaystyle y_ { j} \ not = c_ {j}}$ $y_j \ not = c_j$ не более $δ {\ displaystyle \ delta}$ $\ delta$ . Точно так же вероятность того, что $yk ≠ ck {\ displaystyle y_ {k} \ not = c_ {k}}$ $y_k \ not = c_k$ не превышает $δ {\ displaystyle \ delta}$ $\ delta$ . По границе объединения вероятность того, что либо $yj {\ displaystyle y_ {j}}$ $y_ {j}$ , либо $yk {\ displaystyle y_ {k}}$ $y_{k}$ не совпадают с соответствующими битами в $c {\ displaystyle c}$ $c$ не более $2 δ {\ displaystyle 2 \ delta}$ $2 \ delta$ . Если оба $yj {\ displaystyle y_ {j}}$ $y_ {j}$ и $yk {\ displaystyle y_ {k}}$ $y_{k}$ соответствуют $c {\ displaystyle c}$ $c$ , тогда будет применяться лемма 1, и, следовательно, будет вычислено правильное значение $xi {\ displaystyle x_ {i}}$ $x_ {i}$ . Следовательно, вероятность $xi {\ displaystyle x_ {i}}$ $x_ {i}$ правильно декодирована, как минимум $1-2 δ {\ displaystyle 1-2 \ delta}$ $1-2\delta$ . Следовательно, $ϵ = 1 2 - 2 δ {\ displaystyle \ epsilon = {\ frac {1} {2}} - 2 \ delta}$ $\ epsilon = \ frac {1} {2} - 2 \ delta$ и для $ϵ {\ displaystyle \ epsilon }$ $\ epsilon$ быть положительным, $0 ≤ δ ≤ 1 4 {\ displaystyle 0 \ leq \ delta \ leq {\ frac {1} {4}}}$ $0 \ leq \ delta \ leq \ frac {1} {4}$ .

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

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

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

См. также

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

Примечания

Ссылки

Amadei, М.; Manzoli, U.; Мерани, М. (2002), «О присвоении кодов Уолша и квазиортогональных кодов в системе DS-CDMA с несколькими несущими и множеством классов пользователей», Глобальная конференция по телекоммуникациям, 2002. GLOBECOM'02. IEEE, 1, IEEE, стр. 841–5, doi : 10.1109 / GLOCOM.2002.1188196, ISBN 0- 7803-7632-3 CS1 maint: ref = harv (ссылка )
Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход, Cambridge University Press, ISBN 978-0-521-42426-4 CS1 maint: ref = harv (ссылка )
Гурусвами, Венкатесан, 2009 г.), Список декодирования двоичных кодов (PDF) CS1 maint: ref = harv (ссылка )
Рудра, Атри, «Код Хэмминга и граница Хэмминга» (PDF), Примечания к лекциям