 Информация & документация |
|---|
Контроль правильности передачи
При передаче информации по некачественным и/или разделяемым каналам связи возможны ошибки, то есть искажения передаваемой информации. Эти ошибки необходимо выявлять и исправлять.
Контроль приемником информации может быть побайтным и пакетным. Побайтный метод предполагает, что каждый передаваемый байт дополняется битом четности (или нечетности), то есть в случае, когда количество единиц в передаваемом информационном байте четное, то бит равен "0", а если нечетное - то "1". Метод может применяться как при байтовой передаче, так и при пакетной передаче. Вероятность того, что ошибка не будет обнаружена, довольно велика. К этому может привести наличие четного количества ошибок в информационных битах, а также одновременное искажение информационного и контрольного битов.
Пакетный метод сводится к тому, что в конце каждого передаваемого пакета добавляется контрольная сумма (длиной 8, 16 или 32 бита), которая включает в себя информацию обо всех информационных битах пакета. Метод подсчета контрольной суммы выбирается так, чтобы, с одной стороны, ее просто было вычислить, а с другой стороны, чтобы она достаточно надежно выявляла ошибки. Обычно используются контрольные суммы трех видов.
a) Сумма по модулю 2 всех байтов (слов) пакета, т.е. вычисление идет по правилам: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0. При этом однократные ошибки (то есть одна ошибка на пакет) обнаруживаются с вероятностью 100%, двукратные (две ошибки на пакет) - с вероятностью 7/8 (так как в случае, когда две ошибки попадают в один и тот же разряд, они не могут быть обнаружены). Надо также учесть, что бывают еще и пачки ошибок (искажения нескольких битов), которые данным методом выявляются довольно плохо. Такая сумма легко и быстро считается программным путем, так как соответствующая команда вычисления суммы по модулю 2 имеется практически у всех микропроцессоров.
b) Арифметическая сумма всех байтов (или слов) пакета. При ее вычислении отбрасываются старшие разряды для сохранения заданной разрядности контрольной суммы (обычно 8 или 16). Однократные ошибки обнаруживаются с вероятностью 100%. Вероятность необнаружения двукратных ошибок в наихудшем случае составляет 1/8 * 1/4 = 1/32. Такая наихудшая ситуация наблюдается, когда в каждом из 8 разрядов всех байт пакета или в каждом из 16 разрядов всех слов пакета присутствует половина логических единиц и половина логических нулей. При этом двукратные ошибки не выявляются, когда в одном разряде один из битов из "0" переходит вследствие ошибки в "1", а другой бит в этом же разряде из "1" переходит в "0", что не изменяет общей суммы. Арифметическая сумма также легко и быстро вычисляется программно.
c) Циклическая контрольная сумма. Ее применение вызвано стремлением повысить качество контроля, то есть увеличить вероятность обнаружения ошибок. Эту сумму нельзя так же просто, как предыдущие вычислить программно, однако надежность данного метода контроля неизмеримо выше. Этот метод часто называют "циклическим контролем по избыточности" (сокращенно CRC - Cyclic Redundancy Check). Смысл его состоит в следующем.
Циклическая контрольная сумма.
Весь пакет рассматривается как N-разрядное двоичное число, где N - количество бит в пакете. Для вычисления контрольной суммы это число делится на некоторое постоянное число, выбранное специальным образом (но делится не просто, а по модулю 2). Частное от этого деления отбрасывается, а остаток используется в качестве контрольной суммы.
Как видим, этот метод не так прост, как предыдущие два. Но мы не будем углубляться в его математическое обоснование. Данный метод выявляет однократные ошибки с вероятностью 100%, а любое другое количество ошибок с вероятностью примерно P = (1 - 2^-n), где n - количество разрядов контрольной суммы (однако это верно только при условии, что N>>n). Например, при n = 8 данная вероятность составит P = 0.996, для n = 16 она будет P = 0.999985.
А теперь кратко поясним, что такое деление по модулю 2. Пусть пакет (последовательность бит) имеет следующий вид: 101111001110 (для простоты берем небольшую разрядность). В качестве делителя (называемого обычно полиномом) возьмем 10011. Как он выбирается? Это число должно делиться без остатка только на единицу и на само себя (то есть это должно быть простое число в смысле деления по модулю 2). Разрядность полинома берется на единицу большая, чем требуемая разрядность контрольной суммы (остатка от деления). Так, чтобы был 8-разрядный остаток, надо брать 9-разрядный полином. В нашем случае полином 5-разрядный, следовательно остаток будет 4-разрядный. Для получения 8-разрядного остатка можно использовать полиномы 100011101 = 4358, а также 5438, 5518, 7278.
