636_Nosov_V.I._Seti_radiodostupa_CH.1_

и от числа разрядов (символов) m в кодовом слове, включая и разряд четности. Величину рош можно найти по формуле

использование длинных кодовых слов ведет к росту вероятности необнаруженной ошибки.

Если одиночная ошибка в кодовом слове обнаружена, то ее маскирование после этого состоит в замене искаженного отсчета. Обычные методы, используемые для этого процесса, показаны на рисунке 3.4. На рисунке 3.4, а отмечено ошибочное значение отсчета. Самым плохим решением наверняка является его замена на нуль, т.е. выбрасывание отсчета с ошибочным значением (рисунок 3.4, б). Лучше, если вместо ошибочного отсчета будет использовано значение предыдущего отсчета (рисунок 3.4, в). Еще лучше будет, если его значение будет получено как интерполяция значений двух соседних отсчетов, например путем вычисления среднего значения (рисунок 3.4, г). Однако, все же разность между восстановленным и истинным значениями отсчета может быть заметной на слух и намного превысить шаг квантования.

Поскольку слух человека инерционен, то метод маскирования оказывается эффективным, если число ошибок не превышает одной-двух в секунду. Это условие выполняется при вероятности появления ошибки в канале рош = 10-5. При m = 9 в этом случае получаем, что вероятность необнаруженной ошибки р0 = 36 10-10, что примерно соответствует требуемому значению.

Увеличение рош до значения 10-4 ведет к резкому росту среднего числа ошибок в секунду до 20. Метод интерполяции первого порядка не обеспечивает полного маскирования ошибок полезным сигналом, они становятся уже заметными на слух. Можно считать, что изложенный выше метод маскирования применим, когда значение рош < 10-5.

3.3 Циклическая проверка четности с избыточностью

Циклическая проверка четности с избыточностью (cyclic redundancy check – CRC) — это один из наиболее широко используемых и надежных методов обнаружения ошибок. Принцип работы данного метода сводится к следующему: для блока из k бит (сообщения) передатчик генерирует так называемую контрольную последовательность кадра (frame check sequence — FCS) из (n-k) бит. При этом результирующая последовательность (состоящая из данных и FCS) должна делиться без остатка на заданную константу. На приемной стороне полученная последовательность делится на эту константу и, если деление не дало остатка приемник считает, что ошибки в процессе передачи отсутствовали.

92

Sn

Рис. 3.4 Маскирование ошибочных отсчетов: а) обнаруженная ошибка в значении отсчета sn ; б) замена ошибочного отсчета sn отсчетом с нулевым значением; в) коррекция (экстраполяция нулевого порядка) через замену ошибочного отсчета sn его предыдущим значением sn-1 ; г) интерполяция первого порядка путем вычисления среднего значения из предыдущего sn-1 и последующего sn+1 отсчетов.

Процедуру циклической проверки четности с избыточностью можно описать тремя способами: через арифметические действия по модулю 2; действия с полиномами; и цифровую логику.

3.3.1 Арифметика по модулю 2

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

3.5.

Определим следующие параметры:

T – n-битовый кадр, который необходимо передать;

D – k-битовый блок данных (сообщение); первые k бит кадра Т; F == (п - k:)-битовая контрольная последовательность кадра;

последние (п - k) бит к адра Т ;

P – (п - k + 1)-битовый предопределенный делитель.

93

Так как нужно, чтобы Т нацело делилось на Р, то очевидно, что Т должно иметь следующий вид

Умножая в (3.10) D на 2n-k, мы фактически сдвигаем его влево на (п - k) бит, и заполняем оставшееся место нулями. После добавления контрольной последовательности кадра F получаем n битовый кадр, т.е. Т. Необходимо, чтобы P было делителем Т. Рассмотрим деление 2n-kD на Р

Имеем частное и некоторый остаток от деления. Поскольку деление производилось по модулю 2, остаток должен быть, по крайней мере, на один бит короче делителя. Используем полученный остаток в качестве контрольной последовательности кадра, т.е. F. Тогда

Теперь необходимо проверить удовлетворяет ли R условию отсутствия остатка при делении Т на Р

Подставим уравнение (3.11) в (3.13) и получим

Поскольку сумма по модулю 2 двух одинаковых двоичных чисел дает в результате 0, то

Так как в последнем выражении остатка нет, то это доказывает, что T нацело делится на P.

Итак, проведенный анализ показал, что существует простой способ создания контрольной последовательности кадра – в качестве неѐ можно использовать остаток от деления 2n-kD на P, т.е. T = 2n-kD + R.

94

Рассмотрим пример для иллюстрации выводов, полученных в формулах

(3.1) – (3.6).

Дано:

1.Сообщение D – 1010001101 (10 бит);

2.последовательность P – 110101 (6 бит).

Определить:

1. 5-ти битовую контрольную последовательность кадра R.

Согласно значениям исходных данных задачи имеем n = 15, k = 10, (n-k) =

5.

Решение задачи.

Исходное сообщение D умножается на 25, что дает в результате последовательность 101000110100000. Полученную последовательность делим на P рисунок 3.6.

Полученный остаток складывается с 25D и в результате получается битовый кадр T = 101000110101110, который и передается.

При отсутствии ошибок в канале принятая последовательность Tr не отличается от переданной последовательности T. Приемная сторона осуществляет деление принятой последовательности кадра на заданную последовательность P рисунок 3.7.

Поскольку деление не дало остатка, ошибок в канале не было. Заданная последовательность Р на один бит длиннее контрольной

последовательности, а еѐ точный вид зависит от ожидаемого типа ошибок. Как минимум старший и младший биты заданной последовательности Р должны быть единицами.

95

Существует простой способ определения наличия одной или нескольких ошибок. Ошибка – это изменение значения бита, что эквивалентно применению операции исключающего ИЛИ к данному биту и двоичной единице (добавлению к биту единицы по модулю 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