Код Хэмминга

[fat_crocodile]

Есть 10 типов людей: те, кто понимают двоичную систему счисления и те, кто нет.Я несколько раз про него читал и вроде бы даже один раз делал. Но каждый раз это было как-то непросто. То есть воспринималось как некоторая (хотя и не слишком сложная) магия, которую надо в правильном порядке сделать и тогда -- крэкс-пэкс-фэкс -- получаем в синдроме

Comments

[109]

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

[fat_crocodile]

Хеш на другом уровне работает. Это разные линии обороны. Хеш работает если у нас пакет по пути испортился и надо его целиком перезапросить. А эта штука например где-то внутри ECC, на уровне отдельного машинного слова.

И на уровне отдельного слова сильно дешевле не сделать. Хеш же на самом деле не даёт гарантию, он просто большой и вероятность маленькая, но это срабатывает, когда он 128 бит, например (тот же md5). Но тогда его надо прикреплять к пакету соответствующего размера. А сделать хеш на несколько бит -- я не знаю как.

Опять же проверять хеш надо для всего пакета, а это можно проверять например при каждом чтении памяти, аппаратно это считается довольно быстро. Если что кидаем прерывание "память испорчена" и умираем. Ну или исправляем, если у нас ECC.

Как-то так я вижу возможный сценарий использования.

[fat_crocodile]

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

По идее это то, что позволяет читать поцарапанный CD -- там избыточность раза в полтора, кажется. И они там ещё вроде бы перемешаны, потому что выпадают, конечно, именно обычно расположенные рядом, и значит нам надо как-то распределить ошибки по большей площади.

Но я про это всё только слухами.

[natalysan]

Спасибо требе, добрый человек!!!