👽 Как защититься от космических лучей? Часть 2

Итак, как нам дешево защититься от космических лучей? Возьмём 11 бит данных:

1️⃣ 1️⃣ 0️⃣ 0️⃣ 1️⃣ 0️⃣ 1️⃣ 1️⃣ 0️⃣ 1️⃣ 1️⃣

Космический луч может испортить один бит. Как найти и исправить конкретный бит?

Первое что приходит в голову — разбить на группы и проверить чётность каждой. Но тогда мы знаем только в какой группе сбой, а не какой бит флипнулся. КПД те же 50%.

Идея которую я изложу дальше была предложена Ричардом Хэммингом ажно в 1950 году. И была она настолько универсальна и крута, что используется до сих пор!

🟢 Решение — сетка 4×4

Суть немного похожа на сканворды. Дело в том, что если мы как-то сможем расположить данные так чтобы они проверялись не только по вертикали, но и по горизонтали, то на пересечении жтих вертикалей и горизонталей мы сможем находить нашу ошибку.

Но как это сделать? Во первых нашу линейку битов мы расположим в виде матрицы:


❓ ❓ ❓ 1️⃣

❓ 1️⃣ 0️⃣ 0️⃣

❓ 1️⃣ 0️⃣ 1️⃣

1️⃣ 0️⃣ 1️⃣ 1️⃣

Вопросики — контрольные биты на позициях-степенях двойки. Работают так же они будут позволять проверять четность. Но алгоритм тут чуть хитрее. Ибо каждыйц проверочный бит будет отвечать не за один столбец или одну строку, а сразу за две! Как это показано на пояснительном дикпике 1.

Теперь вычислим значения вопросиков:

К1: 1+1+0+1+0+1+1 = 5, нечётное → К1 = 1
К2: 1+0+0+1+1+1 = 4, чётное → К2 = 0
К4: 1+0+0+1+0+1+1 = 4, чётное → К4 = 0
К8: 1+0+1+1+0+1+1 = 5, нечётное → К8 = 1

Получилось что нам нужно хранить 16 бит вместо 11. КПД — 69%. Но на самом деле, чем больше бит нам нужно проверить, тем эффективнее будет этот алгоритм!

Готово! Защищённая последовательность:

1️⃣ 1️⃣ 0️⃣ 1️⃣

0️⃣ 1️⃣ 0️⃣ 0️⃣

1️⃣ 1️⃣ 0️⃣ 1️⃣

1️⃣ 0️⃣ 1️⃣ 1️⃣

☄️ Космический луч бьёт в позицию 3

Бит в правом верхнем углу переворачивается:
1 → 0.

1️⃣ 1️⃣ 0️⃣ 0️⃣

0️⃣ 1️⃣ 0️⃣ 0️⃣

1️⃣ 1️⃣ 0️⃣ 1️⃣

1️⃣ 0️⃣ 1️⃣ 1️⃣

Как найти нужный бит?

Прогоняем 4 проверки:

🟨 К1 (столбцы 1,3): сумма 5, нечётное → сбой!
🟦 К2 (столбцы 2,3): сумма 3, нечётное → тоже сбой!

Обе группы указывают на столбец 3. Ошибка одна — значит она там. Столбцы 1 и 2 чистые ✓

🟩 К4 (строки 1,3): сумма 4, чётное → ок ✓
🟧 К8 (строки 2,3): сумма 6, чётное → ок ✓

Строка 0, столбец 3 → позиция 3! Переворачиваем бит. Починено.

💡 Можно ещё проще: складываем номера сбойных групп. 1 + 2 = 3. Номер битого бита.

⁉️ Интерактивная визуализация:

Короче, на мощностях тележного редактора такие визуальные штуки объяснять довольно сложно. Но я заморочился и потратил вечерок на вайбкодинг визуализации. Поглядите ее. Там это все прям по шажочкам разложено и можно потыкать в разные биты и поиграться с космическими лучами. ГДЕ ЕЩЕ ВАМ ДАДУТ ПОИГРАТЬСЯ С КОСМИЧЕСКИМИ ЛУЧАМИ???

➡️ОТКРОЙ МЕНЯ ⬅️

Ну а в следующем посте, расскажу, как это работает применительно к нам и почему именно до 2021 года мы могли с уверенностью все валить на космические лучи. А сейчас уже не с такой уверенностью

#инженерныештучки #кодхэмминга #помехоустойчивость