Материал: 636_Nosov_V.I._Seti_radiodostupa_CH.1_

Существует простой способ определения наличия одной или нескольких ошибок. Ошибка – это изменение значения бита, что эквивалентно применению операции исключающего ИЛИ к данному биту и двоичной единице (добавлению к биту единицы по модулю 2): 0+ 1 = 1, 1 + 1=0. Таким образом, ошибки в n-битовом кадре можно представить как n битовое поле с единицами в каждом ошибочном разряде. Полученный таким образом на приемной стороне кадр Тr можно записать в следующем виде

где T – переданный кадр; E – карта ошибок с единицами в местах появления ошибок; Tr – полученный кадр.

При наличии ошибки (Е ≠ 0) приемник не сможет ее обнаружить тогда и только тогда, когда Tr делится на Р (или, эквивалентно, Е делится на Р). Интуитивно можно предположить, что вероятность такого события мала.

3.3.2 Полиномы

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

96

(3.17)

T ( X ) X n k D( X ) R( X ).

Приведенные уравнения (3.17) аналогичны уравнениям (3.11) и (3.12). Используя предыдущий пример, приведенный в арифметике по модулю

2, получаем: последовательности D = 1010001101 соответствует полином D(X) = X9 + X7 + X3 + X2 + 1; последовательности Р = 110101 – полином Р(Х) = X5 + X4 + X2 + 1; последовательности R = 01110 – R(Х) = X3+ Х2 + X. Полиномиальное деление, соответствующее приведенному ранее рисунки 3.6, 3.7 двоичному делению, показано на рис. 3.8.

Ошибка не обнаружится только в том случае, если соответствующий полином Е(Х) делится на Р(Х). Можно показать [19], что при надлежащем выборе полинома Р(Х) выявляются такие ошибки:

Рисунок 3.8 Процесс получения остатка при полиномиальном делении

Кроме того, можно показать, что если все последовательности ошибок считать равновероятными, то для пакета ошибок длиной r + 1 вероятность

97

появления необнаруженной ошибки (т.е. вероятность того, что Е(Х) делится на Р(Х)) равна 1/2r – 1. Для пакета ошибок большей длины вероятность появления необнаруженной ошибки равна 1/2r, где r – длина контрольной последовательности кадра.

Наиболее широко используются четыре полинома Р(Х):

CRC-12 X12+X11+X3+X2+X+1

CRC-16 X16+X15+X2+1

CRC-CCITT X16+X12+X5+1

CRC-32 X32+X26+X23+X22+X16+X12+X10+X8+X7+X5+X4+X2+X+1

Система контроля ошибок CRC-12 используется для передачи потоков 6-битовых знаков; здесь генерируются 12-битовые контрольные последовательности кадров. Системы CRC-16 и CRC-CCITT применяются для передачи 8-битовых знаков в США и Европе, соответственно; здесь создаются контрольные последовательности длиной 16 бит. В большинстве случаев этих полиномов достаточно, чтобы иметь достаточно малую вероятность необнаруженной ошибки. В специальных случаях, когда требуется очень малая вероятность необнаруженной ошибки, может быть использована система контроля CRC-32.

3.3.3 Цифровая логика

Процесс циклической проверки четности с избыточностью можно представить (и как правило, он так и реализуется) как схему деления, состоящую из элемента исключающего ИЛИ и регистра сдвига. Регистр сдвига представляет собой строку 1-битовых ячеек памяти. Каждая ячейка имеет выходную шину, показывающую текущее хранимое значение, и входную шину. В дискретные моменты времени, которые называют тактами, хранимые в них значения ячеек памяти замещаются значениями, указанным во входной шине. Замена происходит синхронно во всем регистре, так что в результате хранимые значения ячеек регистра сдвигаются на один бит. Реализация схемы выглядит следующим образом.

1. Регистр, содержащий (n-k) ячеек памяти (по размеру контрольной последовательности кадра).

2.До (n - k) элементов исключающего ИЛИ.

3.Наличие или отсутствие элемента исключающего ИЛИ

соответствует наличию или отсутствию члена в полиноме-делителе Р(Х), исключая члены 1 и Xn-k.

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

сообщение D = 1010001101; D(X) = X9 + X7 + X3 + X2 + 1;

98

делитель Р = 110101; Р(Х) = Х5 + X4 + X2 + 1.

На рисунке 3.9 представлена реализация устройства формирования циклической проверки четности с избыточностью (CRC-5) для рассматриваемого примера.

Процесс начинается с очистки ячеек памяти регистра сдвига (все ячейки обнуляются). После этого передаваемое сообщение (делимое) 1010001101 побитно вводится в регистр, начиная со старшего бита.

В таблице 3.1 иллюстрируется пошаговая работа схемы рисунка 3.6 по мере введения отдельных битов.

B

Рисунок 3.9 Реализация устройства формирования кода CRC-5

Нулевой такт соответствует исходному состоянию. Строки таблицы содержат значения пяти ячеек регистра сдвига в соответствующие моменты времени. Кроме того, в строках таблицы приводятся значения на выходе трех схем исключающего ИЛИ. Последнее число в каждой строке – значение следующего входного бита, который станет доступен для работы на следующем этапе.

Таблица 3.1 Пошаговая работа устройства формирования кода CRC-5

99

Необходимо отметить, что операция исключающего ИЛИ влияет на значения ячеек С4, С2 и С0 при следующем сдвиге, что идентично рассмотренному ранее процессу двоичного деления. Процесс выполняется для всех битов передаваемого сообщения. Для получения корректности выходного сигнала используются два ключа. При вводе битов данных оба ключа находятся в положении А. В результате за первых 10 шагов входные биты подаются в регистр сдвига и также используются в качестве выходных битов. По окончании обработки последнего бита данных регистр сдвига содержит остаток деления R, выделенный серым цветом. При вводе последнего бита входных данных в регистр оба ключа устанавливаются в положение В.

В этом случае:

1)все логические однобитовые элементы памяти больше не изменяют значения битов;

2)за следующие 5 шагов на выход подаются 5 бит остатка от деления R.

Врезультате на выходе устройства CRC получается выходная последовательность 101000110101110 из n = k + R = 15 бит.

В приемнике используется аналогичная логика рисунок 3.10.

Детектор ошибки

Рис. 3.10 Реализация устройства детектирования кода CRC-5

Принятые биты последовательности n вводятся в регистр сдвига по мере поступления. Если ошибки отсутствуют, то после деления входных k бит на генераторный полином P(X) регистр сдвига будет содержать остаток от деления этой входной последовательности из k бит на генераторный полином, т.е. остаток от деления R. После этого со входа начинает поступать переданная последовательность остатка от деления R. Как следует из логики деления двоичных чисел рисунок 3.8, при делении двух одинаковых двоичных чисел получается 0, т.е. все ячейки памяти регистра сдвига будут в нулевом состоянии, что и свидетельствует об отсутствии ошибок в канале. При

100