Компьютерные сети. 6-е изд.

Илл. 3.8. Чередование битов четности для обнаружения последовательностей ошибок

С помощью чередования код, обнаруживающий (или исправляющий) изолированные ошибки, преобразуется в код, обнаруживающий (или исправляющий) пакеты ошибок. На илл. 3.8 мы видим, что при возникновении таких пакетов длиной n = 7 ошибочные биты находятся в разных столбцах. (Последовательность ошибок не предполагает, что все биты в ней неправильные; подразумевается, что ошибки есть как минимум в первом и последнем битах. На илл. 3.8 из семи сбойных битов на самом деле изменено значение только четырех.) В каждом из n столбцов повреждено будет не больше одного бита, поэтому биты четности в них помогут выявить ошибку. В данном методе n бит четности в блоках из kn бит данных применяются для обнаружения одной последовательности ошибок длиной n бит или меньше.

Последовательность ошибок длиной n + 1 не будет обнаружена, если будут инвертированы первый и последний биты, а все остальные останутся неизменными. Если в блоке при передаче возникнет длинная последовательность или несколько коротких, вероятность того, что четность любого из n столбцов случайным образом окажется верной, равна 0,5. Следовательно, возможность необнаружения ошибки будет равна 2–n.

Второй тип кода для обнаружения ошибок — с использованием контрольной суммы (checksum) — весьма напоминает группу кодов, применяющих биты четности. Под «контрольной суммой» часто подразумевают любую группу контрольных битов, связанных с сообщением, независимо от способа их вычисления. Группа битов четности — также пример контрольной суммы. Однако существуют и другие, более надежные варианты, основанные на текущей сумме битов данных в сообщении. Контрольная сумма обычно помещается в конец сообщения, в качестве дополнения функции суммирования. Таким образом, ошибки можно обнаружить путем суммирования всего полученного кодового слова: битов данных и контрольной суммы. Если результат равен нулю, значит, ошибок нет.

Один из примеров такого кода — 16-битная контрольная сумма, используемая во всех пакетах IP при передаче данных в интернете (см. работу Брейдена и др.; Braden et al., 1988). Она представляет собой сумму битов сообщения, поделенного на 16-битные слова. Так как данный метод работает со словами, а не с битами (как при использовании битов четности), то ошибки, оставляющие четность неизменной, все же изменяют значение суммы, а значит, могут быть обнаружены. Например, если бит младшего разряда в двух разных словах меняется с 0 на 1, то проверка четности этих битов не выявит ошибку. Однако добавление к 16-битной контрольной сумме двух единиц даст другой результат, и ошибка станет очевидной.

Контрольная сумма, применяемая в интернете, вычисляется с помощью обратного кода или арифметики с дополнением до единицы, а не как сумма по модулю 216. В арифметике обратного кода отрицательное число представляет собой поразрядное дополнение своего положительного эквивалента. Большинство современных компьютеров использует арифметику с дополнением до двух, в которой отрицательное число является дополнением до единицы плюс один. В арифметике с дополнением до двух сумма с дополнением до единицы эквивалентна сумме по модулю 216, причем любое переполнение старших битов добавляется обратно к младшим битам. Такой алгоритм обеспечивает едино­образный охват данных битами контрольной суммы. Иначе могут быть добавлены два старших бита, вызвать переполнение и потеряться, не изменив контрольную сумму. Но есть и еще одно преимущество. Дополнение до единицы имеет два представления нуля: все нули и все единицы. Таким образом, одно значение (например, все нули) указывает, что контрольной суммы нет и дополнительное поле для этого не требуется.

Десятилетиями существовало мнение, что фреймы, для которых вычисляется контрольная сумма, содержат случайные значения битов. Анализ алгоритмов вычисления контрольных сумм всегда проводился с учетом именно такого предположения. Изучение фактических данных, выполненное Партриджем и др. (Partridge et al., 1995), показало, что данное предположение неверно. Следовательно, нераспознанные ошибки проскальзывают в некоторых случаях намного чаще, чем считалось ранее.

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

Более эффективный алгоритм — контрольная сумма Флетчера (Fletcher, 1982). Он включает компонент, отвечающий за позицию: произведение данных и соответствующей позиции добавляется к текущей сумме. Это обеспечивает более точное обнаружение изменений в положении данных.