Помехоустойчивые коды

1. Зачем нужны помехоустойчивые коды

Любая передача данных по реальному каналу идёт с искажениями. Когда вы отправляете файл по Wi-Fi, сигнал проходит через стены, отражается, сталкивается с другими сигналами. Читая файл с жёсткого диска, головка может промахнуться мимо магнитного домена. Спутник на орбите получает удары космических частиц, которые переворачивают биты прямо в памяти.

В среднем ошибки случаются редко - примерно один бит на миллион или миллиард. Но при передаче большого фильма или фотографии таких битов миллиарды, и ошибка обязательно где-то возникнет.

Слайд 1 / 10

Что происходит при ошибке

Возьмём простое двоичное число и случайно перевернём один бит:

Было: 10110011 = 179 Стало: 10010011 = 147 Один бит изменился - число стало другим.

Без проверки получатель никогда не узнает, что данные искажены. Он просто прочитает 147 вместо 179 и продолжит работу с испорченной информацией. Результат предсказуем: программа зависнет, файл не откроется, банковский перевод уйдёт не туда.

🛰️

Космический пример Когда зонды «Вояджер» отправляли фотографии Юпитера и Сатурна на Землю в 1979-1989 годах, сигнал шёл через миллиарды километров и был слабее миллиардной доли ватта. Без помехоустойчивого кодирования ни одна фотография не дошла бы. Именно поэтому NASA использует коды с исправлением ошибок в каждом аппарате.

2. Основные понятия

Понятие 1

Избыточность

Специально добавленные данные, которые не нужны для смысла, но помогают проверить целостность. Пример: контрольные биты, CRC-суммы.

Понятие 2

Кодирование

Процесс преобразования исходных данных в код с избыточностью. Выполняется перед отправкой.

Понятие 3

Декодирование

Обратный процесс: приёмник проверяет код, при необходимости исправляет ошибки и восстанавливает исходные данные.

Понятие 4

Обнаружение ошибки

Приёмник понимает, что данные искажены, и запрашивает повторную передачу. Простой уровень защиты.

Понятие 5

Исправление ошибки

Приёмник сам восстанавливает исходные данные, не запрашивая повтор. Более сложный уровень защиты.

Ключевая идея. Чтобы можно было обнаружить или исправить ошибку, в данные добавляют избыточные биты. Дальше эти биты помогают понять, всё ли в порядке, а если нет - где именно ошибка.

3. Контрольный бит чётности

Самый простой способ обнаружения ошибок - бит чётности. К каждым 7 битам данных добавляют один дополнительный бит так, чтобы общее количество единиц в блоке было чётным (или нечётным - зависит от договорённости).

Слайд 2 / 10

Пример: кодирование 7 бит данных

Возьмём 7 бит данных: 1011001. В них четыре единицы. Число чётное, значит бит чётности должен быть 0.

1d1

0d2

1d3

1d4

0d5

0d6

1d7

0p

Итоговая посылка: 10110010. Единиц - четыре, чётное число. Всё в порядке.

Слайд 3 / 10

Пример: ошибка при передаче

Помеха перевернула третий бит:

1d1

0d2

0d3

1d4

0d5

0d6

1d7

0p

Теперь единиц три - нечётное число. Приёмник видит несоответствие и понимает: данные искажены. Ошибка обнаружена.

Приёмник: "Единиц нечётное количество - значит один бит испорчен. Что делать? Запросить повтор передачи."

Бит чётности обнаруживает одиночную ошибку, но не может её исправить - приёмник не знает, какой именно бит перевернулся. Если ошибок сразу две, бит чётности вообще пропустит повреждение: чётность сохранится, данные - нет.

⚠️

Слабые места бита чётности Одиночная ошибка обнаруживается. Двойная - пропускается (снова чётное число единиц). Тройная - снова обнаруживается. Бит чётности ничего не говорит о месте ошибки. Чтобы исправлять ошибки, нужны более сложные коды.

4. Код Хэмминга

Ричард Хэмминг работал в Bell Labs в 1940-е годы. Однажды программа на вычислительной машине выдала неверный результат из-за одной случайной ошибки в памяти. Хэмминга это разозлило, и он придумал код, который не только обнаруживает, но и сам исправляет одиночную ошибку.

Слайд 4 / 10

Идея кода Хэмминга (7,4)

Берём 4 бита данных и добавляем к ним 3 контрольных бита. Итого 7 бит на посылку. Отсюда название «(7, 4)»: из 7 бит - 4 полезных, 3 контрольных.

Контрольные биты ставятся на позиции, номера которых - степени двойки: 1, 2, 4:

p11

p22

d13

p44

d25

d36

d47

биты данных контрольные биты

Слайд 5 / 10

Как считаются контрольные биты

Каждый контрольный бит отвечает за свою группу позиций:

p1 проверяет позиции 1, 3, 5, 7 (где в двоичной записи номера младший бит = 1);
p2 проверяет позиции 2, 3, 6, 7 (второй бит = 1);
p4 проверяет позиции 4, 5, 6, 7 (третий бит = 1).

В каждой группе контрольный бит устанавливается так, чтобы сумма всех битов группы по модулю 2 была равна нулю (то есть число единиц - чётное).

Слайд 6 / 10

Пример: кодируем 4 бита 1011

Данные: d1=1 d2=0 d3=1 d4=1 Позиции: 1 2 3 4 5 6 7 Что: p1 p2 d1 p4 d2 d3 d4 Группа p1 (позиции 1,3,5,7): p1 + d1 + d2 + d4 = p1 + 1 + 0 + 1 Хотим чётное число единиц -> p1 = 0 Группа p2 (позиции 2,3,6,7): p2 + d1 + d3 + d4 = p2 + 1 + 1 + 1 Сумма без p2 = 3 (нечётно) -> p2 = 1 Группа p4 (позиции 4,5,6,7): p4 + d2 + d3 + d4 = p4 + 0 + 1 + 1 Сумма без p4 = 2 (чётно) -> p4 = 0

Итоговое закодированное сообщение: 0110011.

01

12

13

04

05

16

17

5. Обнаружение и исправление ошибок

Теперь самое интересное - как приёмник находит и исправляет ошибку. Он проверяет те же три группы и записывает результаты в синдром - двоичное число из трёх бит.

Слайд 7 / 10

Синдром указывает на позицию ошибки

Пусть при передаче 0110011 помеха испортила позицию 5 - вместо 0 стало 1:

01

12

13

04

15

16

17

Проверка p1 (позиции 1,3,5,7): 0+1+1+1 = 3 (нечётно) -> бит s1 = 1 Проверка p2 (позиции 2,3,6,7): 1+1+1+1 = 4 (чётно) -> бит s2 = 0 Проверка p4 (позиции 4,5,6,7): 0+1+1+1 = 3 (нечётно) -> бит s3 = 1 Синдром: s3 s2 s1 = 101 = 5 (десятичное)

Синдром равен номеру позиции, где произошла ошибка! Номер 5 - значит ошибка в пятом бите. Инвертируем его и получим исходное 0110011.

✓

Магия кода Хэмминга Контрольные биты стоят на степенях двойки, а номер позиции с ошибкой собирается из результатов проверок, как из двоичных цифр. Если синдром равен нулю - ошибок нет. Если синдром не ноль - это номер испорченной позиции.

Слайд 8 / 10

Что если ошибок две?

Код Хэмминга (7,4) исправляет только одну ошибку в посылке. Если перевернулись сразу два бита, синдром укажет на позицию, где ошибки нет, и данные будут испорчены неправильным «исправлением».

Для защиты от двойных ошибок добавляют ещё один общий бит чётности - получается расширенный код Хэмминга (8,4). Он уже умеет обнаруживать двойные ошибки и исправлять одиночные.

Коды Хэмминга бывают разных размеров. Общее правило: для m информационных бит нужно k контрольных, где 2^k ≥ m + k + 1.

Код	Данных	Контрольных	Всего бит	Избыточность
Хэмминг (7,4)	4	3	7	+75%
Хэмминг (12,8)	8	4	12	+50%
Хэмминг (21,16)	16	5	21	+31%
Хэмминг (38,32)	32	6	38	+19%

Чем больше блок данных - тем меньше доля избыточности. Именно поэтому в реальных системах используют крупные блоки: избыточные биты на сотни полезных «стоят» дешевле, чем на каждые 4 бита.

6. CRC - контрольные суммы

Ещё один способ проверки целостности - CRC (Cyclic Redundancy Check, циклический избыточный код). Он работает не с отдельными битами, а сразу со всем блоком данных.

Слайд 9 / 10

Как работает CRC

Исходные данные рассматриваются как один длинный поток битов.
Этот поток делится (по правилам двоичной арифметики) на заранее выбранный полином-делитель.
Полученный остаток от деления - и есть CRC-сумма. Её обычно длиной 16 или 32 бита.
CRC-сумма отправляется вместе с данными.
Приёмник повторяет деление и сравнивает остаток: если совпадает - данные целы.

CRC работает как отпечаток пальца для блока данных. По нему нельзя восстановить данные, зато легко проверить, не изменились ли они. Пошагово это выглядит так:

Превращаем данные в длинное число. Все байты файла (или пакета, или сектора диска) выстраиваются в один длинный ряд нулей и единиц - как одна большая цифра. Например, текст «Привет» в кодировке Windows-1251 - это 48 бит, которые можно записать как одно огромное двоичное число.
Делим это число на заранее выбранный шаблон. Есть стандартные «делители» длиной 16 или 32 бита - их называют полиномами. Они выбраны математиками так, чтобы хорошо ловить типичные ошибки: перепутанные биты, потерянные куски, лишние нули. Деление идёт по правилам двоичной арифметики - без «в столбик с остатком в десятичной», но по той же логике.
Остаток от деления - и есть CRC. От целой части деления ничего не остаётся, важен только остаток. Он всегда короткий: 16 или 32 бита, независимо от того, был файл на 1 КБ или на 100 ГБ. Этот остаток и есть «отпечаток» данных - их CRC-сумма.
Отправляем данные вместе с отпечатком. К файлу или пакету приклеивают эти 16 или 32 бита и передают по сети или записывают на диск. Получатель знает: если данные не портились в пути, то остаток от деления будет точно такой же.
Получатель проверяет отпечаток. Он делает то же самое: делит полученные данные на тот же полином и смотрит на остаток. Совпал с присланным - данные целы. Не совпал - значит что-то испортилось в пути. Так приёмник узнаёт об ошибке, даже если сами данные выглядят как обычно.

Аналогия. Представьте, что вы отправили другу книгу. Чтобы он убедился, что она дошла целиком, вы заранее считаете «контрольное число»: например, сумму номеров всех страниц. Друг, получив книгу, тоже складывает номера страниц. Если его сумма совпала с вашей - книга цела. Если нет - где-то страница потерялась или вклеилась лишняя.

CRC гораздо надёжнее бита чётности. 32-битная CRC обнаруживает практически любую ошибку в блоке до нескольких гигабайт. Именно CRC (точнее, CRC-32) используется в ZIP, PNG, Ethernet и в проверке целостности жёстких дисков.

📦

Знакомый пример Когда вы скачиваете большой файл и видите рядом с ним что-то вроде SHA-256: a3f5... - это тоже контрольная сумма, только криптографическая. Алгоритм надёжнее CRC и защищает не только от случайных ошибок, но и от подмены злоумышленником. Именно по такому принципу работают подписи дистрибутивов Linux и обновлений Windows.

7. Где это применяется

Помехоустойчивые коды окружают нас везде. Вы сталкиваетесь с ними каждый день, не задумываясь.

Слайд 10 / 10

Применения в повседневной жизни

Область	Что используется
Wi-Fi, Ethernet, USB	CRC-32 в каждом пакете
Мобильная связь 4G/5G	Турбо-коды и LDPC-коды
Жёсткие диски и SSD	Коды Рида-Соломона в каждом секторе
CD, DVD, Blu-ray	Коды Рида-Соломона с чередованием
QR-коды	Коды Рида-Соломона
Космос (NASA, SpaceX)	Свёрточные и турбо-коды
Архивы ZIP, изображения PNG	CRC-32 для проверки целостности
Банковские транзакции	Криптографические хеши + CRC

QR-код - особенно наглядный пример. Если вы закрасите маркером часть квадрата, смартфон всё равно прочитает код: оставшихся данных хватает для восстановления утраченного. Именно поэтому в QR-кодах используются разные уровни защиты: L (7%), M (15%), Q (25%) и H (30%) - какой процент площади можно повредить, и код всё ещё прочитается.

🎯

Общая идея Все помехоустойчивые коды работают по одному принципу: добавить избыточность так, чтобы получить возможность проверить и восстановить исходные данные. Разница только в математике: где-то достаточно одного бита, где-то нужны полиномиальные преобразования, а где-то - сложные алгебраические структуры вроде кодов Рида-Соломона.

8. Домашнее задание

Задачи разной сложности - от простых до уровня олимпиад. Первые три можно решить на бумаге, четвёртую и пятую - через логику кодов Хэмминга, шестую - для самых настойчивых.

Задачи для самостоятельного решения

Бит чётности. Даны 7 бит данных: 1101010. Посчитайте бит чётности, если договорились использовать чётную чётность. Какое закодированное сообщение (8 бит) будет передано?
Обнаружение ошибки. Пришла посылка из 8 бит: 11010101. Используется чётная чётность. Была ли ошибка при передаче? Ответ объясните - сколько единиц в посылке и что это означает.
Кодирование Хэмминга. Закодируйте 4 бита данных 1010 с помощью кода Хэмминга (7,4). Посчитайте три контрольных бита и запишите итоговое 7-битное сообщение. Опишите каждую группу отдельно.
Исправление ошибки. Получено закодированное сообщение 1011011 (7 бит). Известно, что использовался код Хэмминга (7,4) с чётной чётностью. Проверьте все три группы, найдите синдром. Определите номер испорченной позиции. Какое исходное сообщение было передано?
Расчёт избыточности. Для блока из 1024 бит данных применяется код Хэмминга. Сколько контрольных бит нужно добавить? (Подсказка: используйте условие 2^k ≥ m + k + 1, где m - число информационных бит.) Чему равна доля избыточности в процентах? Сравните с избыточностью кода (7,4) - какой блок выгоднее и почему?
Задача со звёздочкой. В QR-кодах используется четыре уровня защиты: L (7%), M (15%), Q (25%) и H (30%). Эти проценты означают, что при уровне H можно повредить до 30% площади кода, и он всё ещё прочитается. Подумайте и объясните: почему не всегда есть смысл использовать самый высокий уровень H? Сравните его с уровнем L. Что теряется при повышении уровня защиты и что приобретается? Приведите пример ситуации, где лучше выбрать каждый из уровней.

📌

Подсказки Бит чётности равен 1, если количество единиц в блоке нечётное, и 0, если чётное (при чётной чётности). Контрольные биты Хэмминга встают на позиции 1, 2, 4 в посылке из 7 бит. Каждый отвечает за свою группу позиций. Синдром собирается из трёх бит-результатов проверки и указывает на номер испорченной позиции в двоичной записи.