Код Адамара

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

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

Операція XOR
Тут білі поля позначають 0, а червоні — 1

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

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

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

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

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

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

Побудова

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

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

Побудова з використанням внутрішнього добутку

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

Примітки

1. (PDF). Архів оригіналу (PDF) за 20 Вересня 2018. Процитовано 27 Квітня 2018.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
2. See, e.g., Amadei, Manzoli та Merani, (2002)
3. See, e.g., Arora та Barak, (2009, Section 19.2.2).
4. See, e.g., Guruswami, (2009, с. 3).
5. Bose, R.C.; Shrikhande, S.S. (1959). A note on a result in the theory of code construction. Information and Control. 2 (2): 183—194. CiteSeerX 10.1.1.154.2879. doi:10.1016/S0019-9958(59)90376-6.
6. CDMA Tutorial: Intuitive Guide to Principles of Communications (PDF). Complex to Real. (PDF) оригіналу за 20 July 2011. Процитовано 10 листопада 2017.

Див. також

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