1. Код с проверкой на четность.

2. Код с контрольными суммами.

3. Циклический избыточный код.

Чтобы понять, в каких ситуациях обнаружение ошибок эффективнее их исправления, рассмотрим первый из перечисленных кодов. К отправляемым данным присоединяется единственный бит четности (parity bit), который выбирается так, чтобы число единичных битов в кодовом слове было четным (или нечетным). Это аналогично вычислению бита четности в виде суммы по модулю 2 для битов данных (или применению операции XOR). Например, если отправляется комбинация 1011010 и число единиц должно быть четным, то в конце добавляется ноль и последовательность превращается в 10110100. Если же число единиц должно быть нечетным, то комбинация превращается в 10110101. Расстояние Хэмминга у кода с единственным битом четности равно двум, так как любая однобитовая ошибка меняет четность кодового слова на неправильную. Это означает, что данный код позволяет распознавать однобитовые ошибки.

Рассмотрим канал с изолированными ошибками, возникающими с вероятностью 10–6 на бит. Такое значение может показаться очень небольшим, но для длинного кабельного канала, в котором распознавать ошибки довольно сложно, оно в лучшем случае считается допустимым. Типичные LAN характеризуются вероятностью ошибки 10–10. Пусть блок данных состоит из 1000 бит. Как видно из представленного выше уравнения (3.1), чтобы создать код, исправляющий однократные ошибки в 1000-битном блоке, потребуется 10 контрольных битов. Для 1 Мбит данных это составит 10 000 проверочных бит. Чтобы просто обнаружить одиночную однобитную ошибку, достаточно одного бита четности на блок. На каждые 1000 блоков будет выявляться одна ошибка, и придется переслать повторно еще один блок (1001 бит), чтобы исправить ее. Таким образом, суммарные накладные расходы на обнаружение ошибки и повторную передачу составят всего 2001 бит на 1 Мбит данных против 10 000 бит, необходимых для кода Хэмминга.

Проблема данной схемы в том, что если к блоку добавлять всего один бит четности, то гарантированно распознаваться будет только одна однобитовая ошибка в блоке. В случае возникновения длинной последовательности ошибок вероятность обнаружения ошибки будет всего лишь 0,5, что абсолютно неприемлемо. Этот недостаток может быть исправлен, если рассматривать каждый посылаемый блок как прямоугольную матрицу n бит шириной и k бит высотой (принцип ее построения был описан выше). Если вычислить и отправить один бит четности для каждой строки, то можно гарантированно обнаружить до k однобитных ошибок (если в каждой строке будет не больше одной ошибки).

Однако можно сделать кое-что еще, чтобы повысить уровень защиты от последовательностей ошибок, — биты четности можно вычислять в порядке, отличном от того, в каком данные отправляются по каналу связи. Этот способ называется чередованием (interleaving). В нашем примере мы будем вычислять бит четности для каждого из n столбцов, но биты данных будут отправляться в виде k строк в обычном порядке: сверху вниз и слева направо. В последней строке отправим n бит четности. На илл. 3.8 порядок пересылки показан для n = 7 и k = 7.

Илл. 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, причем любое переполнение старших битов добавляется обратно к младшим битам. Такой алгоритм обеспечивает едино­образный охват данных битами контрольной суммы. Иначе могут быть добавлены два старших бита, вызвать переполнение и потеряться, не изменив контрольную сумму. Но есть и еще одно преимущество. Дополнение до единицы имеет два представления нуля: все нули и все единицы. Таким образом, одно значение (например, все нули) указывает, что контрольной суммы нет и дополнительное поле для этого не требуется.