Симулятор корректирующего кода
Каждое сообщение, которое проходит по проводу, по воздуху или через поцарапанный диск, набирает ошибки: биты меняются с 0 на 1 и обратно. Корректирующий код добавляет несколько тщательно подобранных дополнительных битов, чтобы получатель мог найти и исправить повреждение, не запрашивая данные заново. Введите четыре бита данных, посмотрите, как код Ричарда Хэмминга превращает их в семь, инвертируйте любой бит и смотрите, как три пересекающихся круга указывают прямо на ошибку. Затем отправьте целое сообщение через канал с шумом и сравните, что приходит с кодом и без него. Введите четыре бита данных, например 1011, и приложение добавит три бита чётности, чтобы получилось 7-битное кодовое слово Хэмминга. Щёлкните любой бит в кругах или в строке, чтобы инвертировать его, как это сделал бы шум; щёлкните ещё раз, чтобы вернуть его обратно. В каждом круге должно быть чётное число единиц: круги, где проверка не проходит, указывают на ошибочный бит, и декодер инвертирует его обратно. Включите дополнительный бит чётности, чтобы увидеть, как две ошибки обнаруживаются, а не исправляются неверно. Ниже отправьте текст через канал с шумом с кодом и без него.
Как это работает
- Введите четыре бита данных и посмотрите на семибитное кодовое слово с тремя битами чётности — в кругах и в строке.
- Щёлкайте по битам, чтобы инвертировать их, и смотрите, какие круги не проходят проверку, куда указывает синдром и восстанавливает ли декодер слово.
- Включите дополнительный бит чётности, затем отправьте сообщение через канал с шумом и сравните результаты с кодом и без него.
Как код Хэмминга находит ошибку
Семь битов пронумерованы от 1 до 7. Биты 1, 2 и 4 — это биты чётности, а четыре бита данных стоят на позициях 3, 5, 6 и 7. Бит чётности 1 делает чётным число единиц на позициях 1, 3, 5 и 7 — тех, чей номер в двоичной записи оканчивается на 1; бит 2 делает то же для позиций 2, 3, 6 и 7, а бит 4 — для 4, 5, 6 и 7. Если нарисовать это в виде трёх пересекающихся кругов, каждый бит окажется ровно в тех кругах, которые его проверяют. Когда один бит инвертируется, число единиц в содержащих его кругах становится нечётным. Прочитайте не прошедшие проверки как двоичное число — синдром, — и вы получите позицию ошибочного бита.
Что даёт один дополнительный бит
При двух инвертированных битах синдром указывает на третий, ни в чём не повинный бит, и декодер делает только хуже. Это исправляет восьмой бит, который делает чётным число единиц во всём слове: одна ошибка меняет общую чётность, а две оставляют её чётной, хотя некоторые круги не проходят проверку. Расширенный код, известный как SECDED — исправление одиночных и обнаружение двойных ошибок, — исправляет одну ошибку и надёжно обнаруживает две, так что получатель может запросить этот блок заново. Именно этот код используется в памяти ECC серверов. В канале с шумом код превращает множество разрозненных ошибок в немногие, если только две инверсии редко попадают в один блок.
Часто задаваемые вопросы
Почему биты чётности стоят на позициях 1, 2 и 4?
Потому что это степени двойки, и в двоичной записи каждой из них ровно одна единица. Бит чётности 2ᵏ проверяет каждую позицию, в двоичном номере которой стоит 1 в разряде k. Инвертированный бит на позиции 6 = 110 в двоичной записи нарушает проверки 2 и 4 и не трогает 1, а не прошедшие проверки складываются в 110 — саму эту позицию.
Сколько стоит защита?
Код (7,4) передаёт 7 битов на каждые 4 бита данных, то есть со скоростью 4/7: 75 % сверху. Расширенный код передаёт 8 битов на 4 — вдвое больше. Более длинные коды Хэмминга дешевле: 15 битов несут 11 битов данных, 31 — 26. Современные коды, такие как LDPC и полярные коды, применяемые в Wi-Fi и 5G, очень близко подходят к наилучшей скорости, возможность которой Клод Шеннон доказал в 1948 году.
Что происходит при трёх ошибках?
Обычный код Хэмминга можно обмануть полностью: любые два кодовых слова различаются как минимум в трёх битах, поэтому три инверсии могут превратить одно допустимое кодовое слово в другое, и ни одна проверка не будет нарушена. Приложение сообщает об этом как о незамеченной ошибке. Реальные системы делают такие случаи редкими, выбирая код, достаточно сильный для данного уровня шума.
Где используются корректирующие коды?
Почти везде, где цифровые данные передаются или хранятся: в компьютерной памяти ECC, жёстких дисках и SSD, на CD, DVD и Blu-ray, в QR-кодах, которые остаются читаемыми даже с оторванным куском, в мобильных телефонах и Wi-Fi, в цифровом телевидении и в сообщениях от космических зондов вроде «Вояджера», которые до сих пор присылают данные из-за пределов Солнечной системы.
Отправляется ли куда-нибудь моё сообщение?
Нет. Канал с шумом моделируется в вашем браузере, а ваше сообщение и настройки остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор