|
|
Однобитовые ошибки.
Ошибка такого рода означает, что E=1000...0000. Мы можем гарантировать, что ошибки этого класса всегда будет распознаны при условии, что в G по крайней мере 2 бита установлены в "1". Любое произведение G может быть сконструировано операциями сдвига и сложения, и, в тоже время, невозможно получить значение с 1 единичным битом сдвигая и складывая величину,имеющую более 1 единичного бита, так как в результате всегда будет присутствовать по крайней мере 2 бита.
Двухбитовые ошибки.
Для обнаружения любых ошибок вида 100...000100...000 (то есть когда E содержит по крайней мере 2 единичных бита) необходимо выбрать такое G, которые бы не имело множителей 11, 101, 1001, 10001, и так далее. Мне не совсем ясно, как этого можно достигнуть (у меня нет за плечами чисто математического образования), однако, Tanenbaum уверяет, что такие полиномы должны существовать, и приводит в качестве примера полином с единичными битами в позициях 15, 14 и 1, который не может быть делителем ни одно числа меньше 1...1, где "..." 32767 нулей.
Ошибки с нечетным количество бит.
Мы может перехватить любые повреждения, когда E имеет нечетное число бит, выбрав полином G таким, чтобы он имел четное количество бит. Чтобы понять это, обратите внимание на то, что 1) CRC умножение является простой операцией XOR постоянного регистрового значения с различными смещениями; 2) XOR – это всего навсего операция реключения битов;и 3) если Вы применяете в регистре операцию XOR к величине с четным числом битов, четность количества единичные битов в регистре останется неизменной. Например, начнем с E=111 и попытаемся сбросить все 3 бита в "0" последовательным выполнением операции XOR с величиной 11 и одним из 2 вариантов сдвигов (то есть, "E=E XOR 011" и "E=E XOR 110"). Это аналогично задаче о перевертывании стаканов, когда за одно действие можно перевернуть одновременно любые два стакана. Большинство популярных CRC полиномов содержат четное количество единичных битов. (Замечание: Tanenbaum также утверждает, что все ошибки с нечетным количеством битов могут быть выявлены, если в качестве G выбрать произведение 11.)
Пакетные ошибки.
Пакетная ошибка выглядит как E=000...000111...11110000...00,
то есть E состоит из нулей за исключением группы единиц где то в середине. Эту величину можно преобразовать в E=(10000...00)(1111111...111), где имеется z нулей в левой части и n единиц в правой. Для выявления этих ошибок нам необходимо установить младший бит G в 1. При этом необходимо, чтобы левая часть не была множителем G. При этом всегда, пока G шире правой части, ошибка всегда будет распознана. Более четкое объяснение этого явления ищите у Tanenbaum, я же затрудняюсь это сделать. Кроме того, Tanenbaum уверяет, что вероятность пакетной ошибки с шириной, большей чем W, равна (0.5)W.
На этом мы завершим раздел, посвященный искусству выбора полиномов.
Приведу несколько популярных полиномов:
16 битные: (16,12,5,0) [стандарт "X25"]
(16,15,2,0) ["CRC 16"]
32 битные: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
|
|
