Чем полезна контрольная сумма дополнения 1 для обнаружения ошибок?

Question

Контрольная сумма может быть сгенерирована простым добавлением битов. Чем полезен дополнительный шаг при приеме дополнения 1 с?

Я понимаю теорию. Я знаю, как рассчитать дополнение 1 с, и знаю, как добавление дополнений приводит к результату 1 с.

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

Answer 1

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

Причина, по которой мы делаем дополнение 1, состоит в том, что когда дополнение 1 добавляется к сумме всех значений, а результат обрезается до длины в битах машины (16 бит в приведенном выше примере), это все 1-х. Процессоры имеют функцию, позволяющую брать 1-е число, а взятие 1-го числа для всех - это все-0.

Причина: процессоры ненавидят работать с битами, за исключением тех порций, которые обычно используются. Таким образом, добавление двух 64-битных чисел может занять 1 цикл, но проверка всех битов этого числа по отдельности займет намного больше (в простом цикле, возможно, до 8x64 циклов). Процессоры также имеют возможность тривиально принимать 1 дополнения и обнаруживать, что результат последнего вычисления был нулевым, без проверки отдельных битов и ветвлений на их основе. По сути, это оптимизация, которая позволяет нам очень быстро проверять контрольные суммы. Поскольку большинство пакетов в порядке, это позволяет нам проверять контрольную сумму на лету и гораздо быстрее доставлять данные в пункт назначения.

Answer 2

Пример. У вас есть три слова в UDP-пакете, которые необходимо отправить.

0110011001100000
0101010101010101
1000111100001100

UDP на стороне отправителя выполняет 1-е дополнение суммы всех 16-битных слов.Сумма первых двух из этих 16-битных слов равна

0110011001100000
+
0101010101010101
--> 1011101110110101 

Добавление третьего слова к указанной выше сумме дает: Обратите внимание, что это последнее добавление имело переполнение, которое заключено в

--> 0100101011000010

Дополнение 1s получается путем преобразования всех 0s в 1s и преобразования всех 1s в 0s.

Таким образом, дополнение 1s к сумме 0100101011000010 равно 1011010100111101, которое становится контрольной суммой.На приемнике добавляются все четыре 16-битных слова, включая контрольную сумму.Если в пакет не внесено никаких ошибок, то ясно, что сумма в получателе будет 1111111111111111.Если один из битов равен 0, то мы знаем, что в пакет были внесены ошибки.

Answer 3

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

В этом столбце" Спросите доктора Математика " обсуждается, как вычислить дополнение 1 с (чаще всего для TCP / IP).

Answer 4

Дополнение (инверсия битов) контрольной суммы полезно как минимум двумя способами.

1. Упрощает процесс проверки контрольной суммы

Если, например, конечная контрольная сумма равна 56, дополнение будет 199. Сложите их вместе, и результат будет 255. Обоснование: при дополнении окончательной контрольной суммы конечный результат всегда будет 255, если включая цифра контрольной суммы в расчете суммы . Выполнение дополнения во второй раз с 255 даст 0, что для процессоров в то время было более эффективным способом подтверждения правильности контрольной суммы без необходимости сравнения двух чисел.

2. Позволяет обнаружить одну необнаружимую ошибку

Вычисление сообщения из n нулей дает контрольную сумму нуля. Это означает, что законное сообщение, состоящее из нулей, неотличимо от потери памяти или ситуации стирания, которая должна быть обнаружена как ошибка. Дополняя окончательную контрольную сумму 0 в этом случае, вместо этого получается 255, предотвращая сохранение результата с нулем.

Answer 5

Контрольная сумма очень важна для работы в сети, как упомянул partickmdnet.По сути, для каждой дейтаграммы, передаваемой в протоколе IP, существует контрольная сумма, которая была вычислена заранее и передана.Если хотя бы один бит поврежден и неправильно отправлен в части данных дейтаграммы, то контрольная сумма, вычисленная на принимающем маршрутизаторе, будет отличаться от той, которая указана в дейтаграмме.Это сообщает маршрутизатору, что датаграмма повреждена (либо данные, либо сама часть контрольной суммы), и маршрутизатор отбросит дейтаграмму.