Циклическая проверка избыточности: одиночная и двойная битовая ошибка

Question

Нашел это в книге Forouzan (Data Communications and Networking 5E). Но не могу понять логику этого.

1. Это в контексте изолированных двухбитовых ошибок.

Многочлен x^15 + x^14 +1 не может делить ошибку типа x^t + 1, если t меньше 32768. Это означает, что этим генератором может быть обнаружено кодовое слово с двумя изолированными ошибками, которые расположены рядом друг с другом или на расстоянии до 32768 бит.

2. Также в контексте однобитовых ошибок, почему нам нужно специально иметь коэффициент x^0 как 1, насколько я понимаю, если в полиноме генератора g(x) есть более одного члена, мы должны иметь возможность обнаруживать любой отдельный битовые ошибки. Разве не должно быть достаточно иметь любые два члена в генераторе (x^i + x^j, i и j не равны нулю и i не равны j), чтобы обнаружить любую однобитовую ошибку x^k?

Скажите, пожалуйста, в чем я ошибаюсь.

Answer 1

Максимальная длина сообщения, гарантированно обнаруживающая 2-битную ошибку с x^15 + x^14 + 1, составляет 32767 бит. В случае 32768-битного сообщения, если бит [32767] и бит [0] ошибочны, CRC будет такой же, как и при отсутствии ошибок.

Если x^i является наименьшим ненулевым членом и i!= 0, то это то же самое, что CRC с меньшим на i битами, сдвинутыми влево i битами. Это не связано с возможностью обнаружения одиночной битовой ошибки. Для неотраженного CRC, CRC со смещением влево может использоваться кодом, предназначенным для большего полинома CRC, за которым следует сдвиг вправо. Например, "сдвиг влево" x^15 + x^14 + 1 на 17 бит до x^32 + x^31 + x^17, и использовать этот сдвинутый многочлен с существующим 32-битным кодом CRC (начальное значение CRC также будет необходимо сдвинуть влево на 17 бит), затем после вычисления CRC сдвиньте вправо на 17 бит, чтобы получить 15-битный CRC.

Answer 2

Что касается вашего второго вопроса, да, вам нужны только два ненулевых члена в полиноме, чтобы обнаружить однобитную ошибку. Однако, как отмечает @rcgldr, если последний ненулевой член не равен x⁰, то есть 1, то результирующий CRC эквивалентен сдвигу полинома вниз, так что 1 является последним ненулевым членом.

Например, полином "CRC" x¹⁵+ x⁹ приводит к 15-битному "CRC", где младшие девять битов всегда равны нулю, а старшие шесть битов - это фактический CRC, который вы получаете из полинома x⁶+1.. Я заключил CRC в кавычки, потому что по этой причине действительный многочлен CRC всегда должен иметь член x⁰. x¹⁵+x⁹ не является допустимым полиномом CRC.

В пределе полином CRC x+1 приводит к однобитовой CRC, которая является проверкой четности битов в сообщении. Это всегда обнаруживает однобитную ошибку. Если это все, что вам нужно, то все, что вам нужно, - это проверка четности.