Комп'ютерні науки · Теорія інформації
Червень 2026 · 14 хв читання · Теорія кодування · Шеннон · ECC · Останнє оновлення: 22 червня 2026 р.

Коди корекції помилок: як захистити дані у зашумленому світі

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Кожен канал, що передає цифрову інформацію — оптоволоконна лінія, канал зв'язку з космічним апаратом, подряпаний компакт-диск, комірка флеш-пам'яті — зазнає впливу шуму. Проте фотографії на вашому телефоні, повідомлення, які ви надсилаєте, і дані, отримані від зондів за мільярди кілометрів, приходять бездоганно точними. Причина — коди корекції помилок: хитра надлишковість, яка дозволяє приймачу не просто виявити пошкодження, а й точно відновити початкове повідомлення. Ця стаття простежує розвиток галузі від дивовижної теореми Клода Шеннона 1948 року — яка довела, що майже ідеальний зв'язок через зашумлений канал можливий — через практичні коди, що побудували цифровий світ, аж до квантових кодів, які лежать в основі майбутніх комп'ютерів.

1. Теорема Шеннона про кодування для зашумленого каналу

У 1948 році Клод Шеннон заснував теорію інформації та довів результат, що здавався майже парадоксальним: кожен канал зв'язку має максимальну швидкість — свою пропускну здатність C — нижче якої інформацію можна передавати з настільки малою ймовірністю помилки, наскільки завгодно, незалежно від того, наскільки зашумлений канал.

Пропускна здатність каналу (біт на використання каналу): C = max_p(x) I(X ; Y) (максимізована взаємна інформація) Двійковий симетричний канал, ймовірність переходу p: C = 1 − H(p), де H(p) = −p·log₂(p) − (1−p)·log₂(1−p) Канал AWGN (Шеннон-Хартлі): C = B · log₂(1 + S/N) біт за секунду де B = смуга пропускання (Гц), S/N = відношення сигнал/шум

Теорема має дві половини. Частина про досяжність стверджує, що для будь-якої швидкості R < C існують коди, що дають як завгодно малу помилку. Обернена частина стверджує, що для R > C надійний зв'язок неможливий — помилки не можна звести до нуля. Доказ Шеннона був неконструктивним: він гарантував існування хороших кодів (фактично випадкових кодів), не пояснюючи інженерам, як побудувати практичні. Наступні десятиліття стали довгими пошуками кодів, що наближаються до межі Шеннона за реалізованого кодування й декодування.

Виявлення проти корекції: Виявити, що сталася помилка, легко — один біт парності ловить будь-яке перевертання одного біта. Виправити її вимагає достатньо структурованої надлишковості, щоб визначити, який саме біт перевернувся. Це складніша й цінніша задача, якій присвячена решта статті.

2. Коди Хеммінга та SECDED

Річард Хеммінг, розчарований релейними комп'ютерами, що зупинялися при кожній виявленій помилці, винайшов 1950 року перший практичний код, що виправляє помилки. Код Хеммінга(7,4) кодує 4 інформаційні біти у 7-бітове кодове слово, додаючи 3 біти парності, розміщені у позиціях-степенях двійки.

Розташування кодового слова (позиції 1..7): p1 p2 d1 p4 d2 d3 d4 парність p1 охоплює позиції 1,3,5,7 парність p2 охоплює позиції 2,3,6,7 парність p4 охоплює позиції 4,5,6,7 Декодування: обчисліть 3-бітовий синдром s = (s4 s2 s1). s = 000 → помилки немає s ≠ 000 → його двійкове значення Є позицією перевернутого біта → поверніть його назад.

Геніальність у тому, що синдром безпосередньо вказує місце помилки. Загальний код Хеммінга має параметри:

Для m бітів парності: n = 2^m − 1, k = 2^m − 1 − m Мінімальна відстань d_min = 3 → виправляє 1 помилку АБО виявляє 2. Контекст межі Синглтона/Хеммінга: код з d_min = 2t+1 виправляє t помилок.

Додавання ще одного загального біта парності дає SECDED — Single Error Correction, Double Error Detection (виправлення однієї помилки, виявлення двох; d_min = 4). Коди SECDED захищають ECC-пам'ять практично в кожному сервері: вони безшумно виправляють одноразові збої (спричинені космічними променями та електричним шумом) і сигналізують про невиправні подвійні помилки, перш ніж вони пошкодять дані.

3. Коди Ріда-Соломона: CD та QR-коди

Коди Хеммінга виправляють розсіяні одиночні помилки. Але реальні пошкодження часто трапляються пакетами — подряпина на CD, кавова пляма на QR-коді, загасаючий радіозв'язок. Коди Ріда-Соломона (RS), розроблені 1960 року, працюють із символами (групами бітів) над скінченним полем GF(2^m), а не з окремими бітами, що робить їх ідеальними для пакетних помилок.

Код RS(n, k) над GF(2^m): n − k = 2t символів парності → виправляє до t символьних помилок (або до 2t стирань, коли позиції помилок відомі) Кодування: k символів повідомлення розглядаються як коефіцієнти полінома m(x); кодове слово — це m(x), обчислений у n точках (або m(x)·x^(n−k) mod g(x)). Один пошкоджений символ = одна помилка незалежно від того, скільки його бітів перевернулося, тому RS дуже ефективно обробляє пакети розміром до повного символу.

Аудіо-CD використовує багатошарову схему під назвою CIRC (Cross-Interleaved Reed-Solomon Code), яка перемежовує два RS-коди так, що суцільна подряпина розподіляється по багатьох кодових словах, кожне з яких тоді бачить лише невеликий, виправний пакет. CD може повністю виправити дефектну доріжку завдовжки до приблизно 2,5 мм. QR-коди також використовують Рід-Соломон, із чотирма рівнями надлишковості, що обираються (L/M/Q/H), відновлюючи до близько 30% пошкодженого символу — саме тому частково закритий чи стилізований QR-код усе одно сканується. Та ж сама родина кодів захищала дані, надіслані зондами «Вояджер».

4. CRC: поліноміальне виявлення помилок

Не кожна ситуація потребує корекції; часто швидке, надійне виявлення з подальшою повторною передачею дешевше. Циклічний надлишковий код (CRC) — робочий кінь виявлення помилок, що зустрічається в кадрах Ethernet, ZIP-файлах, жорстких дисках і незліченних мережевих протоколах.

Розглядайте повідомлення як поліном M(x) над GF(2) (біти = коефіцієнти). Оберіть твірний поліном G(x) степеня r. Передача: T(x) = M(x)·x^r − [ M(x)·x^r mod G(x) ] так, щоб T(x) точно ділилося на G(x). Приймач обчислює R(x) mod G(x): залишок = 0 → припускаємо, що помилки немає залишок ≠ 0 → виявлено помилку, запит на повторну передачу

Сила CRC полягає у вдалому виборі G(x). Ретельно спроєктований генератор степеня r гарантує виявлення: усіх одиночних помилок, усіх подвійних помилок, будь-якої непарної кількості помилок (якщо G(x) має множник (x+1)) і будь-якого пакета помилок довжиною не більше r бітів. Популярний CRC-32, що використовується в Ethernet, виявляє всі пакети завдовжки до 32 бітів і переважну більшість довших, з ймовірністю невиявленої помилки близько 2⁻³² для випадкового пошкодження — і все це обчислюється лише операціями зсуву та XOR в апаратному забезпеченні.

5. LDPC та коди, що наближаються до межі пропускної здатності

Півстоліття межа Шеннона залишалася ціллю, якої жоден практичний код не міг досягти. Прорив стався з появою турбо-кодів (1993) та повторним відкриттям кодів з малою щільністю перевірки на парність (LDPC), які спочатку винайшов Роберт Галлагер 1962 року, але їх обчислення були нездійсненними, доки сучасне обладнання не наздогнало ідею.

Код LDPC визначається розрідженою матрицею перевірки на парність H — такою, що має дуже мало одиниць у кожному рядку та стовпці. Ця розрідженість — ключ: вона дозволяє декодеру використовувати ефективний ітеративний алгоритм поширення переконань (обміну повідомленнями) на графі Таннера коду, обмінюючись ймовірнісними оцінками між вузлами змінних (бітами) та вузлами перевірки (обмеженнями парності), доки вони не зійдуться до найімовірнішого кодового слова.

Умова кодового слова: H · cᵀ = 0 (над GF(2)) H розріджена → граф Таннера розріджений → поширення переконань дешеве й паралельне. Продуктивність: добре спроєктовані коди LDPC працюють у межах ~0,0045 дБ від межі Шеннона для каналу AWGN — практично досягаючи пропускної здатності.

Коди LDPC зараз захищають Wi-Fi (802.11n/ac/ax), канали даних 5G, 10-гігабітний Ethernet, супутникове мовлення DVB-S2 та контролери сучасних SSD. Через шістдесят років після того, як Шеннон довів, що коди, які досягають межі пропускної здатності, повинні існувати, інженери нарешті їх побудували — і вони працюють на чипі у вашій кишені.

6. Квантова корекція помилок

Квантові комп'ютери стикаються зі складнішою задачею, ніж будь-який класичний канал. Кубіти декогерують, їх не можна копіювати (теорема заборони клонування забороняє просте копіювання, на якому засновані класичні коди повторення), і вони зазнають не лише перевертань бітів (помилки X), а й перевертань фази (помилки Z) — а вимірювання кубіта для перевірки руйнує його суперпозицію.

Квантова корекція помилок (QEC) вирішує все це одночасно. Хитрість полягає в тому, щоб розподілити інформацію одного логічного кубіта серед багатьох заплутаних фізичних кубітів, а потім вимірювати ретельно обрані оператори парності (стабілізатори), які виявляють, чи сталася помилка — і якого типу — не вимірюючи самі закодовані дані.

9-кубітний код Шора (1995): захищає 1 логічний кубіт за допомогою 9 фізичних кубітів, виправляючи довільну помилку одного кубіта (перевертання біта Й фази). Поверхневий код: кубіти на 2D-решітці; вимірювання стабілізаторів виявляють помилки як дефекти синдрому. Рівень логічної помилки спадає експоненційно з відстанню коду d, ЗА УМОВИ, що рівень фізичної помилки нижче порогу (~1% для поверхневого коду).

Ця теорема порогу є квантовим аналогом результату Шеннона: якщо фізичні кубіти достатньо якісні — нижче порогової частоти помилок — то як завгодно надійні квантові обчислення можливі шляхом масштабування коду. Поверхневий код, з його скромною зв'язністю та високим порогом, є провідним кандидатом і лежить в основі планів кожного великого проєкту з квантових обчислень. Від реле Хеммінга до заплутаних кубітів — та сама ідея живе: структурована надлишковість перетворює зашумлений світ на надійний.

🧮
Симулятор коду Хеммінга
Перевертайте біти у кодовому слові та спостерігайте, як синдром вказує та виправляє помилку
 🔢
Дослідник контрольної суми CRC
Виконайте поліноміальне ділення над GF(2) і перевірте, які помилки ловить генератор
 📡
Симулятор коду Ріда-Мюллера
Досліджуйте коди, що захищали передачі з глибокого космосу від «Марінера» й далі