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

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

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

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

Код Адамара є прикладом лінійного коду на двійковому алфавіті, який перетворює повідомлення довжини на кодові слова довжини . Він відрізняється тим, що кожне ненульове кодове слово має вагу Геммінга[en] рівно , отже відстань коду також дорівнює . У стандартній нотації теорії кодування для блокових кодів, код Адамара є кодом , що означає лінійний код на двійковому алфавіті, що має довжину блока , довжину повідомлення (або розмірність) і найменшу відстань . Довжина блока дуже велика, порівняно з довжиною повідомлення, завдяки чому помилки можуть бути виправлені за значного шуму. Проколотий код Адамара - покращена версія коду Адамара; він є кодом , тому, має трохи кращу швидкість, зберігаючи відносну відстань , і таким чином переважає в практичних застосуваннях. Проколотий код Адамара збігається з кодом Ріда-Маллера[en] першого порядку на двійковому алфавіті.[4]

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

Код Адамара є локально декодовним[en] кодом, який дозволяє відновити частини початкового повідомлення з високою ймовірністю, якщо отримано лише невелику частину кодового слова. Це дозволяє застосовувати його в теорії обчислювальної складності та особливо при розробці ймовірнісних доведень[en]. Оскільки відносна відстань коду Адамара , як правило, можна сподіватися на відновлення за не більше ніж помилок. Однак, використовуючи спискове декодування[en], можна обчислити короткий список можливих повідомлень-кандидатів, поки в прийнятому слові пошкоджено менше ніж біт .

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

ПобудоваРедагувати

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

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

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

Коли дано двійкове повідомлення   довжини  , код Адамара кодує повідомлення у кодове слово   використовуючи функцію кодування  . Ця функція використовує внутрішній добуток   двох векторів  , який визначається таким чином:

 

Потім кодування Адамара   визначається як послідовність всіх внутрішніх добутків з  :

 

Як вже згадувалося вище, на практиці використовується проколотий код Адамара, оскільки власне код Адамара є дещо марнотратним. Це пояснюється тим, що, якщо перший біт   дорівнює нулю,   тоді внутрішній добуток не містить ніякої інформації про   і, отже, неможливо повністю розшифрувати   з цих позицій кодового слова. З іншого боку, коли кодове слово обмежене позицією, де   ще можна повністю розшифрувати  . Отже, є сенс обмежити код Адамара з цих позицій, що породжує проколотий код Адамара для  ; тобто,  .


ПриміткиРедагувати

  1. http://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 July 2011. Процитовано 10 November 2017. 

Див. такожРедагувати