Иллюстрированный самоучитель по локальным сетям

Циклические коды (CRC)

Циклические коды – это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды Хэмминга, но: целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправ ления ошибок, определяемой параметром d0, по сравнению с кодами Хэм минга (для которых dQ=3 или d0=4). Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров.

Основные свойства и само название циклических кодов связаны с те!\ что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвиг некоторого исходного кодового слова:

Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) g(x) или их корней. Кроме того, вводятся понятия полинома исходного сообщения.

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

Рассмотрим последовательность кодирования на примере циклического кода (7.4.3), имеющего g(x) = х3 + х + 1:

  1. информационная часть сообщения записывается в виде полинома:

    Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

    В рассматриваемом примере k = 4 и для сообщения 0111 получаем:

    Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

  2. и(х) умножается хг, что соответствует циклическому сдвигу исходного сообщения на г разрядов влево:

    Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

  3. полученный многочлен делится на g(x):

    Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

    Где с(х) – полином – частное с максимальной степенью (k-1); R(x) – полином – остаток с максимальной степенью (г-1); (+) – обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ).

Кодированное сообщение представляется в виде:

Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

…то есть на месте младших, освобожденных после домножения на хг, разрядов, записываются проверочные разряды.

Для рассматриваемого примера:

Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

Таким образом, в данном случае А(х) = (х3 + х4 + х3) (+) х = х5 + х4 + х3 + х. Передаваемое кодированное сообщение в обычной двоичной форме имеет вид:

Иллюстрированный самоучитель по локальным сетям › Алгоритмы сети Ethernet/Fast Ethernet › Циклические коды (CRC)

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.