Код Адамара - это код исправления ошибок, названный в честь Жака Адамара, который используется для обнаружения и исправления ошибок при передаче сообщений по очень шумным или ненадежным каналам. В 1971 году этот код использовался для передачи фотографий Марса обратно на Землю с космического зонда НАСА Mariner 9 . [1] Благодаря своим уникальным математическим свойствам, код Адамара не только используется инженерами, но также интенсивно изучается в теории кодирования , математике и теоретической информатике . Код Адамара также известен под названиями кода Уолша , семья Уолш ,[2] и код Уолша – Адамара [3] с признанием американского математика Джозефа Леонарда Уолша .
Код Адамара | |
---|---|
Названный в честь | Жак Адамар |
Классификация | |
Тип | Линейный блочный код |
Длина блока | |
Длина сообщения | |
Показатель | |
Расстояние | |
Размер алфавита | |
Обозначение | -код |
Дополненный код Адамара | |
---|---|
Названный в честь | Жак Адамар |
Классификация | |
Тип | Линейный блочный код |
Длина блока | |
Длина сообщения | |
Показатель | |
Расстояние | |
Размер алфавита | |
Обозначение | -код |
Код Адамара является примером линейного кода длинынад двоичным алфавитом . К сожалению, этот термин несколько неоднозначен, поскольку в некоторых источниках предполагается длина сообщения. в то время как другие предполагают длину сообщения . В этой статье первый случай называется кодом Адамара, а второй - расширенным кодом Адамара .
Код Адамара уникален тем, что каждое ненулевое кодовое слово имеет вес Хэмминга ровно, что означает, что расстояние кода также. В стандартных обозначениях теории кодирования для блочных кодов код Адамара является-код, то есть это линейный код над двоичным алфавитом , имеет длину блока , длина сообщения (или размер), и минимальное расстояние . Длина блока очень велика по сравнению с длиной сообщения, но, с другой стороны, ошибки можно исправить даже в очень шумных условиях.
Расширенный код Адамара - это немного улучшенная версия кода Адамара; это-code и, следовательно, имеет немного лучшую скорость при сохранении относительного расстояния, и поэтому предпочтение отдается в практических приложениях. В теории коммуникации это просто называется кодом Адамара, и это то же самое, что и код Рида – Маллера первого порядка по двоичному алфавиту. [4]
Обычно коды Адамара основаны на построении Сильвестра матриц Адамара , но термин «код Адамара» также используется для обозначения кодов, построенных из произвольных матриц Адамара , которые не обязательно относятся к типу Сильвестра. В общем, такой код не является линейным. Такие коды были впервые построены RC Bose и SS Shrikhande в 1959 году. [5] Если n - размер матрицы Адамара, код имеет параметры, что означает, что это необязательно линейный двоичный код с 2 n кодовыми словами с длиной блока n и минимальным расстоянием n / 2. Схема построения и декодирования, описанная ниже, применима к общему n , но свойство линейности и отождествление с кодами Рида – Маллера требует, чтобы n было степенью 2 и чтобы матрица Адамара была эквивалентна матрице, построенной методом Сильвестра.
Код Адамара - это локально декодируемый код, который обеспечивает способ восстановления частей исходного сообщения с высокой вероятностью, просматривая только небольшую часть полученного слова. Это дает начало приложениям в теории сложности вычислений и, в частности, в разработке вероятностно проверяемых доказательств . Поскольку относительное расстояние кода Адамара равно 1/2, обычно можно только надеяться исправить не более 1/4 доли ошибки. Однако, используя декодирование списка , можно вычислить короткий список возможных сообщений-кандидатов, если их меньше, чем бит в полученном слове повреждены.
В связи с множественным доступом с кодовым разделением каналов (CDMA) код Адамара называется кодом Уолша и используется для определения индивидуальных каналов связи . В литературе CDMA принято называть кодовые слова «кодами». Каждый пользователь будет использовать другое кодовое слово или «код» для модуляции своего сигнала. Поскольку кодовые слова Уолша являются математически ортогональными , кодированный Уолшем сигнал появляется как случайный шум для мобильного терминала с поддержкой CDMA , если только этот терминал не использует то же кодовое слово, которое использовалось для кодирования входящего сигнала . [6]
История
Код Адамара - это название, которое чаще всего используется для этого кода в литературе. Однако в современном использовании эти коды с исправлением ошибок называются кодами Уолша-Адамара.
Для этого есть причина:
Жак Адамар не изобретал сам код, но он определил матрицы Адамара около 1893 г., задолго до того , как первый код коррекции ошибок , то код Хэмминга , был разработан в 1940 - х годах.
Код Адамара основан на матрицах Адамара, и хотя здесь можно использовать множество различных матриц Адамара, обычно для получения кодовых слов кода Адамара используется только построение матриц Адамара, построенное Сильвестром .
Джеймс Джозеф Сильвестр разработал свою конструкцию матриц Адамара в 1867 году, которая фактически предшествует работе Адамара по матрицам Адамара. Следовательно, название кода Адамара оспаривается, и иногда код называют кодом Уолша , в честь американского математика Джозефа Леонарда Уолша .
Расширенный код Адамара использовался во время миссии Mariner 9 1971 года для исправления ошибок передачи изображения. Слова данных, используемые во время этой миссии, были длиной 6 бит, что представляло 64 значения в градациях серого .
Из-за ограничений качества юстировки передатчика в то время (из-за проблем с доплеровским контуром слежения) максимальная полезная длина данных составляла около 30 бит. Вместо использования кода повторения использовался код Адамара [32, 6, 16].
С помощью этой схемы можно исправить ошибки до 7 бит на слово. По сравнению с кодом с 5 повторениями , свойства исправления ошибок этого кода Адамара намного лучше, но его скорость сопоставима. Эффективный алгоритм декодирования был важным фактором при принятии решения об использовании этого кода.
Используемая схема получила название «Зеленая машина». Он использовал быстрое преобразование Фурье, которое может увеличить скорость декодирования в три раза. С 1990-х годов использование этого кода космическими программами более или менее прекратилось, и сеть дальнего космоса НАСА не поддерживает эту схему исправления ошибок для своих антенн размером более 26 метров.
Конструкции
Хотя все коды Адамара основаны на матрицах Адамара, конструкции тонко различаются для разных областей науки, авторов и использования. Инженеры, использующие коды для передачи данных, и теоретики кодирования , анализирующие экстремальные свойства кодов, обычно хотят, чтобы скорость кода была как можно более высокой, даже если это означает, что конструкция становится немного менее элегантной с математической точки зрения.
С другой стороны, для многих приложений кодов Адамара в теоретической информатике не так важно достижение оптимальной скорости, и, следовательно, более простые конструкции кодов Адамара предпочтительнее, поскольку их можно анализировать более элегантно.
Строительство с использованием внутренних продуктов
Когда дано двоичное сообщение длины , код Адамара кодирует сообщение в кодовое слово с использованием функции кодирования Эта функция использует внутренний продукт двух векторов , который определяется следующим образом:
Тогда кодирование Адамара определяется как последовательность всех внутренних продуктов с:
Как упоминалось выше, на практике используется расширенный код Адамара, поскольку сам код Адамара несколько расточителен. Это потому, что если первый бит равно нулю, , то внутренний продукт не содержит никакой информации о , а значит, невозможно полностью расшифровать только с этих позиций кодового слова. С другой стороны, когда кодовое слово ограничено позициями, где, все еще можно полностью декодировать . Следовательно, имеет смысл ограничить код Адамара этими позициями, что приводит к расширенному кодированию Адамара; это,.
Построение с использованием образующей матрицы
Код Адамара является линейным кодом, и все линейные коды могут быть сгенерированы с помощью порождающей матрицы. . Это матрица такая, что справедливо для всех , где сообщение рассматривается как вектор-строка, а произведение вектор-матрица понимается в векторном пространстве над конечным полем . В частности, эквивалентный способ написать определение внутреннего продукта для кода Адамара возникает с использованием матрицы генератора, столбцы которой состоят из всех строк. длины , это,
где это -й двоичный вектор в лексикографическом порядке . Например, порождающая матрица кода Адамара размерности является:
Матрица это -матрица и порождает линейный оператор .
Генераторная матрица расширенного кода Адамара получается ограничением матрицык столбцам, первая запись которых равна единице. Например, порождающая матрица для расширенного кода Адамара размерности является:
потом является линейным отображением с .
Для общего , порождающая матрица расширенного кода Адамара является проверочной матрицей для расширенного кода Хэмминга длины и размер , что делает расширенный код Адамара дуальным кодом расширенного кода Хэмминга. Следовательно, альтернативным способом определения кода Адамара является его матрица проверки на четность: матрица проверки на четность кода Адамара равна порождающей матрице кода Хэмминга.
Построение с использованием общих матриц Адамара
Адамара коды получаются из п матрицу с размерностью п матрица Адамара H . В частности, 2 п кодовых слов кода являются строки H и строки - H . Чтобы получить код над алфавитом {0,1}, к элементам матрицы применяется отображение −1 ↦ 1, 1 ↦ 0 или, что то же самое, x ↦ (1 - x ) / 2. То, что минимальное расстояние кода равно n / 2, следует из определяющего свойства матриц Адамара, а именно, что их строки взаимно ортогональны. Это означает, что две различные строки матрицы Адамара различаются ровно в n / 2 позициях, и, поскольку отрицание строки не влияет на ортогональность, любая строка H отличается от любой строки -H также в n / 2 позициях, кроме случаев, когда строки соответствуют, и в этом случае они различаются n позициями.
Чтобы получить расширенный код Адамара выше с помощью , выбранная матрица Адамара H должна быть типа Сильвестра, что дает длину сообщения.
Расстояние
Расстояние кода - это минимальное расстояние Хэмминга между любыми двумя различными кодовыми словами, т. Е. Минимальное количество позиций, на которых различаются два различных кодовых слова. Поскольку код Уолша – Адамара является линейным кодом , расстояние равно минимальному весу Хэмминга среди всех его ненулевых кодовых слов. Все ненулевые кодовые слова кода Уолша – Адамара имеют вес Хэмминга ровно по следующему аргументу.
Позволять быть ненулевым сообщением. Тогда следующее значение в точности равно доле позиций в кодовом слове, равных единице:
Тот факт, что последнее значение ровно называется принципом случайной суммы . Чтобы убедиться в его истинности, без ограничения общности предположим, что. Тогда, при условии, что значения, событие эквивалентно для некоторых в зависимости от а также . Вероятность того, что происходит точно . Таким образом, фактически все ненулевые кодовые слова кода Адамара имеют относительный вес Хэмминга, и, следовательно, его относительное расстояние равно .
Относительное расстояние расширенного кода Адамара равно также, но у него больше нет того свойства, что каждое ненулевое кодовое слово имеет вес точно поскольку все s вектор - кодовое слово расширенного кода Адамара. Это потому, что вектор кодирует в . Кроме того, всякий раз, когда ненулевой, а не вектор , снова применяется принцип случайной субсуммы, и относительный вес точно .
Локальная декодируемость
Локально декодируемый код представляет собой код , который позволяет один биты исходного сообщение , чтобы быть восстановлен с высокой вероятностью лишь глядя на небольшую часть полученного слова.
Код есть -запрос локально декодируемый, если бит сообщения,, можно восстановить, проверив бит полученного слова. Более формально код,, является -локально декодируемый, если существует вероятностный декодер, , такие что (Примечание:представляет собой расстояние Хэмминга между векторами а также ) :
, подразумевает, что
Теорема 1. Код Уолша – Адамара является-Локально декодируемый для всех .
Лемма 1: для всех кодовых слов в коде Уолша – Адамара, , , где представляют биты в в должностях а также соответственно, и представляет бит в позиции .
Доказательство леммы 1.
Позволять быть кодовым словом в соответствующий сообщению .
Позволять быть образующей матрицей .
По определению, . Из этого,. Построением, . Следовательно, путем подстановки.
Доказательство теоремы 1.
Для доказательства теоремы 1 построим алгоритм декодирования и докажем его правильность.
Алгоритм
Ввод: полученное слово
Для каждого :
- Выбирать равномерно наугад
- Выбирать такой, что где является побитовое исключающее из а также .
Вывод: сообщение
Доказательство правильности
Для любого сообщения, , и получил слово такой, что отличается от на самое большее доля бит, может быть декодирован с вероятностью не менее .
По лемме 1 . С а также выбираются равномерно, вероятность того, что самое большее . Аналогично вероятность того, что самое большее . Согласно оценке объединения , вероятность того, что либо или же не совпадают соответствующие биты в самое большее . Если оба а также соответствуют , то будет применяться лемма 1, а значит, собственное значение будет вычислено. Следовательно, вероятность декодируется правильно, по крайней мере . Следовательно, и для быть позитивным, .
Следовательно, код Уолша – Адамара имеет вид локально декодируемый для
Оптимальность
Для k ≤ 7 линейные коды Адамара оказались оптимальными в смысле минимального расстояния. [7]
Смотрите также
- Последовательность Задова – Чу - улучшение по сравнению с кодами Уолша – Адамара
Заметки
- ^ http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf
- ^ См, например, Амадей, Manzoli & Merani (2002)
- ^ См., Например, Arora & Barak (2009 , раздел 19.2.2).
- ^ См., Например, Guruswami (2009 , стр. 3).
- ^ Bose, RC; Шриханде, СС (1959). «Заметка о результате в теории построения кода». Информация и контроль . 2 (2): 183–194. CiteSeerX 10.1.1.154.2879 . DOI : 10.1016 / S0019-9958 (59) 90376-6 .
- ^ «Учебное пособие по CDMA: интуитивно понятное руководство по принципам связи» (PDF) . Сложный в Реальный. Архивировано 20 июля 2011 года (PDF) . Проверено 10 ноября 2017 года .
- ^ Джефф, Дэвид Б .; Буюклиев, Илия, Оптимальные двоичные линейные коды размерности не больше семи , архивировано из оригинала 2008-08-08 , получено 21.08.2007
Рекомендации
- Amadei, M .; Manzoli, U .; Мерани, М.Л. (2002), «О назначении кодов Уолша и квазиортогональных кодов в системе DS-CDMA с несколькими несущими и несколькими классами пользователей», Глобальная конференция по телекоммуникациям, 2002. GLOBECOM'02. IEEE , 1 ., IEEE, стр 841-5, DOI : 10,1109 / GLOCOM.2002.1188196 , ISBN 0-7803-7632-3
- Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, ISBN 978-0-521-42426-4
- Гурусвами, Венкатесан (2009), Расшифровка списка двоичных кодов (PDF)
- Рудра, Атри, "Код Хэмминга и оценка Хэмминга" (PDF) , Конспекты лекций