Код Адамара

Код Адамара — завадостійкий код, який використовується для виявлення і корекції помилок під час передавання повідомлень через дуже шумні й ненадійні канали. У 1971 році код було використано для передавання на Землю фотографій Марса з космічного зонда NASA «Марінер-9».^[1]

Через його унікальні математичні властивості код Адамара використовується не тільки інженерами, але й інтенсивно вивчається в теорії кодування, математиці та теоретичній інформатиці.

Код Адамара названо на честь французького математика Жака Адамара. Він також відомий під назвами код Волша, сімейство Волша,^[2] і код Волша — Адамара^[3] на визнання внеску американського математика Джозефа Леонарда Волша.

Код Адамара є прикладом лінійного коду на двійковому алфавіті, який перетворює повідомлення довжини ${\displaystyle k}$ на кодові слова довжини ${\displaystyle 2^{k}}$. Він відрізняється тим, що кожне ненульове кодове слово має вагу Геммінга рівно ${\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}$. Довжина блока дуже велика, порівняно з довжиною повідомлення, завдяки чому помилки можуть бути виправлені за значного шуму. Проколотий код Адамара — покращена версія коду Адамара; він є кодом ${\displaystyle [2^{k},k+1,2^{k-1}]_{2}}$, тому, має трохи кращу швидкість, зберігаючи відносну відстань ${\displaystyle 1/2}$, і таким чином переважає в практичних застосуваннях. Проколотий код Адамара збігається з кодом Ріда — Маллера першого порядку на двійковому алфавіті.^[4]

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

Код Адамара є локально декодовним кодом, який дозволяє відновити частини початкового повідомлення з високою ймовірністю, якщо отримано лише невелику частину кодового слова. Це дозволяє застосовувати його в теорії обчислювальної складності та особливо при розробці ймовірнісних доведень. Оскільки відносна відстань коду Адамара ${\displaystyle {\frac {1}{2}}}$, як правило, можна сподіватися на відновлення за не більше ніж ${\displaystyle {\frac {1}{4}}}$ помилок. Однак, використовуючи спискове декодування, можна обчислити короткий список можливих повідомлень-кандидатів, поки в прийнятому слові пошкоджено менше ніж ${\displaystyle {\frac {1}{2}}-\epsilon }$ біт.

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

Хоча всі коди Адамара ґрунтуються на матрицях Адамара, побудова може дещо відрізнятися, залежно від наукового напрямку, автора і призначення. Інженери, які використовують коди для передавання даних і теоретики кодування, аналізуючи екстремальні властивості кодів, як правило, потребують якомога вищої швидкості коду, навіть якщо побудова буде математично менш елегантною.

З іншого боку, для багатьох застосувань кодів Адамара в галузі теоретичної інформатики досягнення оптимальної швидкості є не таким важливим, тому надається перевага простішим способам їх побудови, оскільки тоді вони можуть бути проаналізовані більш елегантно.

Коли дано двійкове повідомлення ${\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}}}$.

• Матриці Адамара