Практическое занятие № 5

Тема: «Управление обменом, контроль и обнаружение ошибок сети Ethernet»

Цели: обобщить и систематизировать знания по теме «Базовые топологии локальных сетей.

Вид работы: фронтальный

Время выполнения: 2 часа

Краткие теоретические сведения

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

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

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

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

Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является в настоящее время наиболее популярным методом контроля в вычислительных сетях. Метод основан на рассмотрении исходных данных в виде одного многоразрядного двоичного числа. В качестве контрольной информации рассматривается остаток от деления этого числа на известный делитель R. Обычно в качестве делителя выбирается семнадцати- или тридцати трехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байт) или 32 разряда (4 байт). При получении кадра данных снова вычисляется остаток от деления на тот же делитель R, но при этом к данным кадра добавляется и содержащаяся в нем контрольная сумма. Если остаток от деления на R равен, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным.

Этот метод обладает более высокой вычислительной сложностью, но его диагностические возможности гораздо выше, чем у методов контроля по паритету. Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе бит. Метод обладает также невысокой степенью избыточности.

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

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

Для построения циклических кодов в качестве образующих полиномов используются неприводимые многочлены, т.е. такие многочлены, которые делятся без остатка только на себя и на единицу. Образующий полином может быть представлен в алгебраической форме либо в виде двоичного или восьмеричного числа. В последнем случае каждая восьмеричная цифра отображает три разряда. Например, для полинома двоичная запись имеет вид 101001, а соответствующая ему восьмеричная - 51. В таблице приведены выборочно неприводимые многочлены до 12-й степени включительно. Полиномы записаны в алгебраической форме и в виде восьмеричных чисел (для степеней - только в виде восьмеричных чисел).

Таблица 7 – Неприводимые многочлены

2	, 7	7	211,217,235
3	, 13	8	747,435,543
4	, 23	9	1055,1751
5	, 45	10	2033,3177
6	, 75	11	7413,4505
		12	15647,11015

При выборе полинома следует иметь в виду, что степень образующего полинома не может быть меньше числа проверочных элементов .

Из множества разновидностей циклических кодов для исправления и обнаружения пакетов ошибок наиболее широко используются коды с кодовым расстоянием , разработанные Боузом, Чоудхури и Хоквингемом (коды БЧХ). Эти коды обнаруживают и исправляют любое число ошибок.

Длину кодовой комбинации определяют по формуле , где -целое число.

Образующий полином находят как наименьшее общее кратное (НОК) минимальных нечетных полиномов.

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