Код Адамара

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

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

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

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

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

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

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

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

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

Побудова

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

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

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

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

Примітки

http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf
See, e.g., Amadei, Manzoli та Merani, (2002)
See, e.g., Arora та Barak, (2009, Section 19.2.2).
See, e.g., Guruswami, (2009, с. 3).
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. doi:10.1016/S0019-9958(59)90376-6. Проігноровано невідомий параметр |citeseerx= (довідка)
CDMA Tutorial: Intuitive Guide to Principles of Communications. Complex to Real. Архів оригіналу за 20 липня 2011. Процитовано 10 листопада 2017.

Див. також

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] ttp://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf

[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. doi:10.1016/S0019-9958(59)90376-6. Проігноровано невідомий параметр |citeseerx= (довідка)

[6] CDMA Tutorial: Intuitive Guide to Principles of Communications. Complex to Real. Архів оригіналу за 20 липня 2011. Процитовано 10 листопада 2017.