Код Адамара
З Вікіпедії, безкоштовно encyclopedia
Код Адамара — завадостійкий код, який використовується для виявлення і корекції помилок під час передавання повідомлень через дуже шумні й ненадійні канали. У 1971 році код було використано для передавання на Землю фотографій Марса з космічного зонда NASA «Марінер-9».[1]
Через його унікальні математичні властивості код Адамара використовується не тільки інженерами, але й інтенсивно вивчається в теорії кодування, математиці та теоретичній інформатиці.
Код Адамара названо на честь французького математика Жака Адамара. Він також відомий під назвами код Уолша, сімейство Уолша,[2] і код Уолша–Адамара[3] на визнання внеску американського математика Джозефа Леонарда Уолша[en].
Код Адамара є прикладом лінійного коду на двійковому алфавіті, який перетворює повідомлення довжини на кодові слова довжини . Він відрізняється тим, що кожне ненульове кодове слово має вагу Геммінга[en] рівно , отже відстань коду також дорівнює . У стандартній нотації теорії кодування для блокових кодів, код Адамара є кодом , що означає лінійний код на двійковому алфавіті, що має довжину блока , довжину повідомлення (або розмірність) і найменшу відстань . Довжина блока дуже велика, порівняно з довжиною повідомлення, завдяки чому помилки можуть бути виправлені за значного шуму. Проколотий код Адамара — покращена версія коду Адамара; він є кодом , тому, має трохи кращу швидкість, зберігаючи відносну відстань , і таким чином переважає в практичних застосуваннях. Проколотий код Адамара збігається з кодом Ріда-Маллера[en] першого порядку на двійковому алфавіті.[4]
Як правило, коди Адамара ґрунтуються на побудованих Сильвестром матрицях Адамара, але термін «код Адамара» також використовується для позначення кодів, побудованих з довільних матриць Адамара, які не обов'язково є Сильвестрового типу. В загальному випадку, такий код не є лінійним. Такі коди було вперше побудовано Р. Ч. Бозе[en] і Ш. Ш. Шриханде[en] у 1959 році.[5] Якщо — розмір матриці Адамара, то код має параметри , отже, це не обов'язково лінійний двійковий код з кодових слів з довжиною блока і мінімальною відстанню . Схеми побудови і розшифровки, описані нижче, застосовні для довільного , але властивість лінійності та ідентичності з кодом Ріда-Маллера досягається лише, якщо є степенем 2 і якщо матриця Адамара еквівалентна матриці, побудованій методом Сильвестра.
Код Адамара є локально декодовним[en] кодом, який дозволяє відновити частини початкового повідомлення з високою ймовірністю, якщо отримано лише невелику частину кодового слова. Це дозволяє застосовувати його в теорії обчислювальної складності та особливо при розробці ймовірнісних доведень[en]. Оскільки відносна відстань коду Адамара , як правило, можна сподіватися на відновлення за не більше ніж помилок. Однак, використовуючи спискове декодування[en], можна обчислити короткий список можливих повідомлень-кандидатів, поки в прийнятому слові пошкоджено менше ніж біт.
У каналах телефонного зв'язку з множинним доступом з кодовим поділом (CDMA) код Адамара називають кодом Волша, і використовують для визначення індивідуальних каналів зв'язку. Зазвичай в літературі з CDMA кодові слова називають «кодами». Кожен користувач використовує різні кодові слова, або «коди», для модуляції свого сигналу. Оскільки кодові слова Волша є математично ортогональні, то сигнал, кодований за Волшем, сприймається мобільним терміналом[en] стандарту CDMA як випадковий шум, якщо термінал використовує пароль, відмінний від використаного для кодування вхідного сигналу.[6]