Общие сведения и классификация методов обнаружения ошибок передачи данных

Задача обнаружения ошибок, возникающих в процессе передачи информационных кадров по каналам связи телекоммуникационных сетей, решается протоколами канального уровня [14].

Большинство методов обнаружения ошибок основаны на передаче в составе кадра избыточной информации, по которой можно судить с некоторой степенью вероятности о достоверности принятых данных. Такую информацию принято называть контрольной суммой. Контрольная сумма (КС) вычисляется как функция от основной информации, причем необязательно только путем суммирования. Принимающая сторона повторно вычисляет контрольную сумму кадра по известному алгоритму и в случае ее совпадения с контрольной суммой, вычисленной передающей стороной, делает вывод о том, что данные были переданы через сеть корректно.

Существует несколько распространенных методов обнаружения ошибок и соответствующих им алгоритмов вычисления контрольной суммы, отличающихся вычислительной сложностью и способностью обнаруживать искажения (рис. 2.23).

 

 

Рис. 2.23. Методы обнаружения ошибок

 

Контроль по паритету на четность (нечетность) является одним из наиболее простых методов контроля данных, обладает весьма слабыми возможностями по контролю. Позволяет обнаруживать только одиночные или нечетной кратности ошибки в проверяемых данных. Метод заключается в суммировании по модулю 2 всех бит контролируемой информации. Значение контрольного разряда r, добавляемого к информационному сообщению U = (u₀,.., u_m), формируется в соответствии с (11.1) при контроле на четность или (11.2) ‑ при контроле на нечетность.

Сформированный контрольный разряд r пересылается вместе с контролируемой информацией. При искажении при пересылке любого одного бита исходных данных (или контрольного разряда) результат повторного суммирования будет отличаться от принятого контрольного разряда, что говорит об ошибке.

 

(2.8)

 

(2.9)

 

Пример 1.

	Чет.	Нечет.
U = 100110111
U = 10011001

 

Контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод в настоящее время редко применяется в вычислительных сетях из-за его большой избыточности и невысоких диагностических возможностей.

Вертикальный и горизонтальный контроль по паритету представляет собой модификацию описанного выше метода. Его отличие состоит в том, что исходные данные рассматриваются в виде матрицы, строки которой составляют байты данных. Контрольный разряд подсчитывается отдельно для каждой строки и для каждого столбца матрицы (табл. 2.4). Этот метод обнаруживает большую часть двойных ошибок, однако обладает еще большей избыточностью. На практике почти не применяется.

Циклический избыточный контроль (Cyclyc Redundancy Check, CRC) является разновидностью использования блочных кодов. В настоящее время широко применяется для контроля передачи данных в компьютерных и телекоммуникационных сетях. Вертикальный и горизонтальный контроль по паритету приведены в табл. 2.4.

Таблица 2.4

 

Байты	0 р.	1 р.	2 р.	3 р.	4 р.	5 р.	6 р.	7 р.	Нечет.
Нечет.

 

Метод основан на представлении информационных кадров в виде единой совокупности двух блоков: информационной и проверочной последовательности двоичных символов (рис. 2.24). Наличие специальной проверочной последовательности позволяет не только выявлять факт искажения отдельных информационных разрядов, но и корректировать их.

 

Информационная последовательность

Проверочная последовательность

 

Рис. 2.24. Структура информационного кадра при циклическом контроле

Например, в кадре стандарта Ethernet, содержащего 8192 бита (1024 байта) в качестве контрольной последовательности используется остаток от деления этого числа на известный делитель P(x), представляющий собой порождающий полином. Обычно в качестве такого делителя выбирается семнадцати -или тридцати трехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байта) или 32 разряда (4 байта).

При получении кадра данных снова вычисляется остаток от деления на тот же делитель P(x), но при этом к данным кадра добавляется и содержащаяся в нем контрольная сумма. Если остаток от деления на P(x) равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным.

Метод циклического контроля обладает более высокой вычислительной сложностью, но его диагностические возможности гораздо выше, чем у методов контроля по паритету. Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе бит. Метод обладает также невысокой степенью избыточности. Например, для кадра Ethernet размером в 1024 байта контрольная информация длиной в 4 байт составляет только 0,4 %.

Рассмотрим пример использования метода циклического контроля.

Введем следующие обозначения:

1. U(x)=u_m-1x^m-1+ u_m-2x^m-2+…+ u₀x⁰ ‑ полином, определяющий информационную последовательность данных (m - разрядность данных);

2. P(x) =p_kx^k+ p_k-1x^k-1+…+ p₀x⁰ ‑ порождающий полином (k – разрядность проверочной последовательности);

3. F(x) = f_n-1x^n-1+ f_n-2xⁿ-² +...+ f₀x⁰ ‑ полином, определяющий кодовую комбинацию, передаваемую по каналу связи (n = m + k) - разрядность кодовой комбинации);

4. Q(x) = q_m-1x^m-1+ q_m-2 x^m-2+... + q₀ x⁰ ‑ частное от деления кодовой комбинации F(x) на порождающий полином P(x);

5. R(x) = r_k-1 x^k-1 + г_k-2х^k-2+…+ r₀х⁰ ‑ остаток от деления кодовой комбинации F(x) на порождающий полином P(x), образующий проверочную последовательность символов;

Алгоритм кодирования передаваемых данных при циклическом контроле:

1. Для формирования блоков информационных и проверочных символов исходная информационная последовательность U(x) сдвигается на k разрядов влево. Освободившиеся младшие разряды заполняются нулями. В дальнейшем их место займут проверочные символы. Аналитически данная операция может быть представлена выражением x^kU(x).

2. Сдвинутая последовательность информационных символов делится на порождающий полином Р(х).

3. Для формирования кодовой комбинации F(x), выдаваемой в канал связи, полученный в результате деления k - разрядный остаток R(x) добавляется к младшим разрядам сдвинутой последовательности информационных символов. Операция сложения выполняется по модулю 2: F(x) = x^k U(x) Å R(x).

 

Пример 2.

Формирование кодовой комбинации. Дано:

1. U(x) = x⁴ + x² + x + 1 = 10111 ‑ информационная последовательность (m=5).

2. P(x) = x⁴ + x + 1 = 10011 ‑ порождающий полином (k=4).

 

Решение:

1. Сдвиг информационной последовательности на k=4 разряда влево.

U(x) x⁴ = (x⁴ + x² + x + 1) x⁴ = x⁸ + x⁶ + x⁵ + x⁴ = 101110000.

2. Формирование проверочной последовательности путем деления U(x) x⁴ на порождающий полином Р(х). Проверочные символы определяются остатком отделения.

 

3. Формирование кодовой комбинации F(x).

 

Обнаружение ошибок при циклическом кодировании сводится к делению принятой кодовой комбинации на тот же порождающий полином, который использовался для кодирования. Если ошибок в принятой комбинации нет, то деление на порождающий полином производится без остатка. Наличие остатка свидетельствует о присутствии ошибок.

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

Однако обычно в телекоммуникационных сетях исправление ошибок при использовании циклических кодов не производится, а при обнаружении ошибок выдается запрос на повтор испорченной ошибками комбинации. Такие системы называются системами с обратной связью.