UK 
EnglishТипова
Polski💻 Коди Ріда-Маллера
Інтерактивна візуалізація кодів виправлення помилок Ріда-Маллера, що використовуються у міжпланетному зв'язку.
Схожі симуляції
Про коди Ріда-Маллера
Коди Ріда-Маллера, представлені незалежно Девідом Маллером (1954) та Ірвінгом Рідом (1954), — це родина лінійних кодів виправлення помилок з винятково великими мінімальними відстанями Гемінга, що робить їх одними з найпотужніших кодів для каналів з високим рівнем шуму. Код Ріда-Маллера першого порядку R(1, m) кодує k = m + 1 інформаційних бітів у n = 2ᵐ бітів кодового слова за допомогою породжуючої матриці (2ᵐ) × (m+1), стовпці якої представляють усі 2ᵐ двійкові вектори; мінімальна відстань між будь-якими двома кодовими словами точно дорівнює 2^(m−1), тобто код може виправити до 2^(m−2) − 1 помилок. Найвідомішим практичним застосуванням стала передача перших кольорових фотографій Марса апаратом NASA «Марінер-9» у 1972 році з використанням R(1, 5): 32-бітне кодове слово, що переносило 6 бітів даних зображення через зашумлений далекокосмічний радіоканал.
Цей симулятор візуалізує весь конвеєр кодування: оберіть m (від 2 до 5), введіть повідомлення, спостерігайте множення на породжуючу матрицю над GF(2), а потім внесіть випадкові або пакетні помилки бітів і спостерігайте, як мажоритарно-логічний декодер відновлює вихідне повідомлення. Дисплей відстані Гемінга показує, наскільки отримане слово віддалене від кожного дійсного кодового слова, а крива BER (частота бітових помилок) відображає виправну здатність залежно від кількості помилок.
Часті запитання
Яка мінімальна відстань Гемінга R(1, m) і скільки помилок вона може виправити?
Код Ріда-Маллера першого порядку R(1, m) має мінімальну відстань Гемінга d = 2^(m−1). Код з мінімальною відстанню d може виявити до d − 1 помилок і виправити до ⌊(d−1)/2⌋ помилок. Для R(1, 5): d = 16, тож він може виправити до 7 помилок бітів у будь-якому отриманому 32-бітному слові. Для R(1, 4): d = 8, виправляє до 3 помилок у 16-бітному слові. Ця велика відстань відносно довжини блоку є винятковою — багато поширених кодів мають набагато менше співвідношення відстані до довжини.
Як працює мажоритарно-логічне декодування для R(1, m)?
Мажоритарний декодер Ріда 1954 року обчислює m+1 незалежних рівнянь перевірки парності для кожного з m+1 бітів повідомлення, кожне рівняння охоплює 2^(m−1) позицій отриманого слова. Якщо більше половини з 2^(m−1) оцінок збігаються (голосування більшістю), цей біт декодується як значення більшості. Оскільки мінімальна відстань дорівнює 2^(m−1), до 2^(m−2) − 1 помилок не можуть змінити результат голосування проти правильного біта. Це декодування виконується за O(m · 2ᵐ) операцій — лінійно щодо довжини блоку при фіксованому m — і достатньо просте для реалізації в апаратурі космічних апаратів початку 1970-х.
Які параметри (n, k, d) типових кодів Ріда-Маллера?
Для R(1, m): довжина блоку n = 2ᵐ, розмірність k = m + 1, мінімальна відстань d = 2^(m−1). Приклади: R(1,2) = (4, 3, 2) — код з одиночною перевіркою парності; R(1,3) = (8, 4, 4) — еквівалентний розширеному коду Гемінга; R(1,4) = (16, 5, 8); R(1,5) = (32, 6, 16) — код Марінера. Швидкість коду k/n = (m+1)/2ᵐ швидко спадає зі зростанням m: R(1,5) має швидкість 6/32 ≈ 0.19, тобто 81% переданих бітів — це надлишковість для виправлення помилок.
Як коди Ріда-Маллера використовувалися апаратом «Марінер-9»?
«Марінер-9», запущений у 1971 році і перший космічний апарат, що вийшов на орбіту іншої планети, використовував R(1, 5) для передачі зображень 64×64 пікселі з 64 рівнями сірого (6 бітів на піксель) через 100 мільйонів кілометрів. Кожен піксель кодувався як 32-бітне кодове слово; низхідний канал 37,5 кбіт/с з властивим йому шумом і перевертанням бітів виправлявся на землі перед реконструкцією зображення. Без виправлення помилок отримані зображення були б суттєво погіршені; завдяки виправній здатності R(1,5) науковці отримали достатньо чіткі зображення, щоб картографувати понад 7000 марсіанських об'єктів.
Яка повна ієрархія кодів Ріда-Маллера R(r, m)?
Загальний код Ріда-Маллера R(r, m) має параметри: n = 2ᵐ, k = Σᵢ₌₀ʳ C(m, i), d = 2^(m−r). Параметр r — це «порядок»: R(0, m) — простий код повторення (1 біт, швидкість 1/2ᵐ, максимальна відстань), R(1, m) — першого порядку (розглянуто вище), R(m−1, m) — розширений код Гемінга (швидкість (2ᵐ − 1)/2ᵐ, відстань 4), R(m, m) — тривіальний код без надлишковості. Кожен R(r, m) містить R(r−1, m) як підкод. Ця вкладена структура використовується в рекурсивних алгоритмах декодування та в побудові полярних кодів (Арикан, 2009), що застосовуються у стандартах 5G.
Чи використовуються коди Ріда-Маллера в сучасних системах зв'язку?
Класичні коди Ріда-Маллера широко не використовуються у сучасних високошвидкісних каналах через низьку швидкість коду (особливо першого порядку), яка марнує занадто багато пропускної здатності. Проте їхня математична структура є фундаментальною. Полярні коди — які використовуються в керуючих каналах 5G NR (TS 38.212) — доведено пов'язані з кодами Ріда-Маллера і мають спільну рекурсивну структуру; фактично R(1, m) є окремим випадком полярного коду. Коди Ріда-Маллера другого порядку використовуються в деяких послідовностях розширення CDMA, а RM(1, 5) залишається еталоном в академічних дослідженнях кодування каналів.
Як пакетна помилка впливає на декодування Ріда-Маллера?
Мажоритарно-логічне декодування для R(1, m) припускає, що помилки розподілені незалежно — воно виправляє будь-який шаблон з до t = 2^(m−2) − 1 помилок незалежно від позиції. Пакетна помилка (послідовні перевернуті біти) довжиною b впливає на b позицій отриманого слова; якщо b ≤ t, вона виправляється нормально. Якщо b > t, але пакет зосереджений в одному рівнянні перевірки парності, а не розподілений по всіх рівняннях, мажоритарне голосування все ще може спрацювати. Однак довгі пакетні помилки, що охоплюють багато рівнянь, можуть змінити результат голосування, спричиняючи збій декодування. Перемежування (перемішування бітів кодового слова між передачами) — стандартний спосіб пом'якшення для каналів зі сплесками помилок.
Який зв'язок між кодами Ріда-Маллера та булевими функціями?
Існує пряма бієкція: кожне кодове слово R(r, m) відповідає таблиці істинності булевої функції від m змінних з алгебричним степенем не більше r. Код першого порядку R(1, m) відповідає афінним булевим функціям (лінійні функції плюс константа). Цей зв'язок означає, що декодування R(1, m) еквівалентне наближенню довільної булевої функції найближчою афінною функцією — задача, центральна для теорії навчання (теорема Голдрейха-Левіна) і криптоаналізу (атаки на перетворення Уолша-Адамара на потокові шифри).
Як працює кодування за допомогою породжуючої матриці?
Для R(1, m) породжуюча матриця G розміром (m+1) × 2ᵐ має перший рядок з усіх одиниць (вектор усіх одиниць) і m додаткових рядків, де рядок i+1 — це двійкове представлення індексу стовпця j у бітовій позиції i («маскувальні» рядки). Щоб закодувати вектор повідомлення довжиною m+1 біт u, обчислюють кодове слово c = u · G над GF(2) (двійкова арифметика поля — додавання це XOR, множення це AND). Отримане 2ᵐ-бітне кодове слово є суперпозицією всіх нулів, усіх одиниць та XOR-комбінацій m «маскувальних» рядків, обраних бітами повідомлення.
Який зв'язок між кодами Ріда-Маллера та кодами Адамара?
Код Ріда-Маллера першого порядку R(1, m) і код Адамара довжини 2ᵐ тісно пов'язані: R(1, m) складається саме з тих рядків (та їхніх доповнень) матриці Адамара 2ᵐ × 2ᵐ. Код Адамара — це набір усіх 2^(m+1) векторів ±1 з рядків матриці, що збігається з 2^(m+1) кодовими словами R(1, m) (оскільки кожне повідомлення має одне кодове слово та його доповнення). Мажоритарно-логічне декодування R(1, m) еквівалентне обчисленню швидкого перетворення Уолша-Адамара, яке досягається за O(2ᵐ · m) = O(n log n) операцій.
Чи можуть коди Ріда-Маллера досягти межі пропускної здатності Шеннона?
Коди Ріда-Маллера першого порядку не досягають пропускної здатності Шеннона: їхня швидкість (m+1)/2ᵐ спадає до нуля зі зростанням m, тоді як коди, що досягають пропускної здатності, зберігають ненульову швидкість. Однак Рівз і Пфістер (2021) довели, що коди Ріда-Маллера вищих порядків R(r, m) з r/m → константа наближаються до пропускної здатності Шеннона на двійковому каналі стирання при m → ∞. Полярні коди (родина, пов'язана з RM) стали першими явно побудованими кодами, доведено здатними досягти пропускної здатності Шеннона на всіх симетричних двійкових каналах. Коди Ріда-Соломона (інша родина) наближаються до пропускної здатності на q-арних каналах.