|
|
9 Циклический избыточный код CRC
9.1 Обнаружение ошибок
При передаче сообщений по низкокачественным каналам связи, возможно внесение искажений в эти сообщения, и поэтому необходимо предусмотреть методы, с помощью которых приемник сможет определить, были ли ошибки при передаче. При обнаружении ошибок, приемник может запросить повторную передачу сообщения. Для обнаружения применяются методы контрольных сумм. Передатчик подсчитывает некоторое значение, называемое контрольной суммой, являющееся функцией сообщения, и добавляет его в конец сообщения. Приемник использует ту же функцию для подсчета контрольной суммы, и сравнивает полученное значение с записанным в конце сообщения.
Существуют различные методы обнаружения ошибок, некоторые из которых преобразуют сообщение, дополняя его избыточной информацией. Методы CRC (Cyclic Redundancy Codes) относятся к методам, которые оставляют без изменения исходный текст сообщения, добавляя контрольную сумму в конец.
9.2 Основная идея CRC-алгоритмов
Корректность пакета по CRC, по длине и кратности целому числу байт производится после проверки адреса места назначения. Вероятность ошибки передачи при наличии crc контроля составляет ~2-32. При вычислении CRC используется образующий полином:
G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1.
Алгоритм вычисления CRC сводится к вычислению остатка от деления кода M(x), характеризующего кадр, на образующий полином G(x). CRC представляет собой дополнение полученного остатка R(x). CRC пересылается, начиная со старших разрядов
9.3 Полиномиальная арифметика
В CRC часто можно встретить термин "полиномиальный". Говорят, что данный CRC алгоритм использует некий полином, и.т.п. И, вообще, говорят, что CRC алгоритмы используют полиномиальную арифметику.
Делимое, делитель, частное и остаток рассматриваются не как положительные целые, а как полиномы с двоичными коэффициентами. То есть число записывается в виде двоичной строки, биты которой служат коэффициентами полинома. Например числу 23 (010111b) отвечает полином:
1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0, или проще:
x^4 + x^2 + x^1 + x^0
Мы можем осуществлять арифметические операции, понимая их как операции над полиномами. Например, умножим 13 (01101b) на 11 (01011b):
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =
(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
Для того, чтобы получить в ответе 143, мы должны в качестве x взять 2 и привести коэффициенты к двоичным, перенеся 1 из 3*x^3 в старшие разряды. Получаем:
x^7 + x^3 + x^2 + x^1 + x^0 , что соответствует 010001111b = 143
Можно придумать различные типы полиномиальной арифметики, определяя правила работы с коэффициентами. Для нас важна одна из схем - "полиномиальная арифметика по модулю 2", где все коэффициенты вычисляются по модулю 2, и отсутствуют переносы.
Возвращаясь к предыдущему примеру:
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =
(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 =
x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0
В дальнейшем мы не будем упоминать полиномиальное представление, поскольку это может только усложнить изложение, и будем говорить об эквивалентной системе, назывемой "двоичная арифметика без переноса".
Это обычная арифметика, просто основание системы счисления здесь выписано явно. Суть в том, что если мы не знаем х, то мы не можем производить переносы. Мы не знаем, что 3*x^3 это то x^4+x^3, потому что мы не знаем, что х = 2.
9.4 Двоичная арифметика без переноса
Как нетрудно заметить с отменой переноса исчезают и различия между сложением и вычитанием. Для каждой позиции есть 4 варианта:
0 + 0 = 0 - 0 = 0
0 + 1 = 0 - 1 = 1
1 + 0 = 1 - 0 = 1
1 + 1 = 1 - 1 = 0
То есть, фактически, сложение и вычитание в CRC-арифметике эквивалентны операции XOR, которая является обратной самой себе, и это очень удобно.
9.5 Особенности различных алгоритмов
В последнее время стали популярными сложные алгоритмы, далеко отстоящие от обычной схемы деления. В первую очередь это так называемая табличная реализация и ее модификации, цель которых в переходе от цикла по всем битам к циклу по большим порциям данных - байтам, словам, и.т.д. Особенности различных реализаций привели к новым модификациям самого алгоритма. Появились такие понятия как начальное и конечное значения.
Начальное (стартовое) значение записывается в аккумулятор перед началом генерации CRC. Алгоритм CRC16 инициализирует аккумулятор нулем, выполняя обыкновенную схему деления. Однако выбор нулевого стартового значения не самый удачный. Нетрудно видеть, что нули в начале сообщения являются "слепым пятном" алгоритма (т.е. их число не повлияет на значение контрольной суммы), и, в то же время, такие сообщения достаточно часто встречаются. Введение начального значения, которое с точки зрения схемы деления эквивалентно дописыванию в начало сообщения ненулевого значения позволяет обойти эту проблему.
Конечное значение просто складывается (XOR) с остатком деления.
Модификация CRC16/CITT использует стартовое значение FFFFh. Алгоритм CRC32 использует FFFFFFFFh в качестве начального и конечного значений.
10 Кодирование сигналов на физическом уровне
Для передачи информации по коммуникационным линиям данные преобразуются в цепочку следующих друг за другом битов (двоичное кодирование с помощью двух состояний: "0" и "1").
При цифровом кодировании дискретной информации применяют потенциальные и импульсные коды.
В потенциальных кодах для представления логических единиц и нулей используется только значение потенциала сигнала, а его перепады, формирующие законченные импульсы, во внимание не принимаются. Импульсные коды позволяют представить двоичные данные либо импульсами определенной полярности, либо частью импульса — перепадом потенциала определенного направления.
Существуют несколько наиболее распространненых кодов:
- Потенциальный код без возвращения к нулю (Non Return to Zero, NRZ)
- Метод биполярного кодирования с альтернативной инверсией AMI
- Потенциальный код с инверсией при единице(Non Return to Zero with ones Inverted, NRZI).
- Биполярный импульсный код
- Манчестерский код
- Потенциальный код 2В1Q
Рис. 11. Способы дискретного кодирования данных
10.1 Манчестерский код
В локальных сетях до недавнего времени самым распространенным методом кодирования был так называемый манчестерский код. Он применяется в технологиях Ethernet и Token Ring.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
При использовании материалов активная ссылка на источник обязательна.