Вступ
За кожну мілісекунду між Землею та сусідніми галактиками шмигають трильйони і трильйони повідомлень.
Але передавати на такі величезні відстані непросто.
Набридливі сонячні спалахи, часові викривлення, сторонні сили і навіть помах крила космічного метелика можуть змінити випадковий біт під час передавання.
А тепер уявімо наслідки:
- Обвал Міжгалактичної біржі, коли «buy low» перетворюється на «sell now».
- Втрата звʼязку із системою Kepler Whirl, коли «save new worm hole» стає «cave new worm hole».
- Або занурення всесвіту в екзистенційний жах через заміну емодзі ковбоя 🤠 на емодзі клоуна 🤡.
Виявляти пошкоджені повідомлення не просто важливо, а критично.
Приймач повинен знати, коли щось пішло не так, ще до того, як станеться катастрофа.
Але як?
Науковці й інженери з усього всесвіту бʼються над цією проблемою цілу вічність.
Цілі космічні суперкластери штучного інтелекту перемелюють ці дані.
І ось одного дня знову зʼявляється легенда, давній і могутній метод, про який шепочуться на форумах із налагодження і бурмочуть інженери, які бачили занадто багато...
Біт парності!
Метод настільки простий і настільки потужний, що цілком може врятувати міжзоряний звʼязок.
Вказівки
Наше завдання - допомогти реалізувати
- передавач, який обчислює послідовність передавання, і
- приймач, який її декодує.
Біт парності - простий спосіб виявляти помилки під час передавання.
Передавачі і приймачі можуть передавати і приймати рівно вісім бітів за раз (разом із бітом парності).
Біт парності встановлюють так, щоб у кожному передаванні кількість одиничних бітів була парною, а сам біт парності завжди є першим бітом справа.
Тож якщо приймач отримує 11000001, 01110101 або 01000000 (тобто передавання з непарною кількістю одиничних бітів), він знає, що сталася помилка.
Проте повідомлення рідко бувають такими короткими, і коли вони довші, їх доводиться передавати послідовно.
Наприклад, розгляньмо повідомлення 11000000 00000001 11000000 11011110 (або C0 01 C0 DE у шістнадцятковому вигляді).
Оскільки кожне передавання містить рівно вісім бітів, воно може містити лише сім бітів даних і біт парності.
Тому біт парності потрібно вставляти після кожних семи бітів даних:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
Послідовність передавання для цього повідомлення має такий вигляд:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
Дані в першому передаванні послідовності (1100000) мають два одиничні біти (парна кількість), тож біт парності дорівнює 0.
Перше передавання стає 11000000 (або C0 у шістнадцятковому вигляді).
Дані в наступному передаванні (0000000) мають нуль одиничних бітів (знову парна кількість), тож біт парності знову дорівнює 0.
Друге передавання, відповідно, стає 00000000 (або 00 у шістнадцятковому вигляді).
Дані для наступних двох передавань (0111000 і 0001101) мають три одиничні біти.
Їхні біти парності встановлюють на 1, щоб у передаванні була парна кількість одиничних бітів.
Їх передають як 01110001 і 00011011 (або 71 і 1B у шістнадцятковому вигляді).
Останнє передавання (1110) містить лише чотири біти даних.
Оскільки за раз передають рівно вісім бітів, а біт парності є найправішим бітом, додають три нульові біти, а потім біт парності, щоб доповнити до восьми бітів.
Тепер це має такий вигляд (де _ позначає біт парності):
1110 000_
↑↑↑ (added 0 bits)
Знову маємо непарну кількість одиничних бітів, тож біт парності дорівнює 1.
Останнє передавання в послідовності стає 11100001 (або E1 у шістнадцятковому вигляді).
Уся послідовність передавання для цього повідомлення - 11000000 00000000 01110001 00011011 11100001 (або C0 00 71 1B E1 у шістнадцятковому вигляді).
