Циклические избыточные проверки

C yclic R edundancy C heck - CRC. Это наиболие часто используемые коды с проверкой на четность.

Пусть

K - длина последовательности битов данных,
L - длина CRC (число проверочных битов).

Удобно обозначать биты данных через , ,..., , и представлять последовательность в виде многочлена S(D):

При этом степени переменной D сохраняют порядок битов.

CRC представляется другим многочленом:

Тогда передаваемую информацию и CRC вместе можно представить многочленом:

Многочлен C(D), представляющий CRC определяется как

где - порождающий многочлен - многочлен степени L, который задает конкретный код CRC. Операция деления многочленов является обычным делением многочленов, но коэффициенты принимают только двоичные значения, а арифметические операции над коэффициентами выполняются по модулю 2 (1+1=0, 0-1=1).

Например:

Данные 101011

Порождающий многочлен 10011

получаем кодовое слово 1010110100

Поскольку степень многочлена g(D) не превышает L,то степень остатка не превышает L-1. Если степень C(D) получалась меньше, чем L-1, то соответствующие старшие оэффициенты ,... полагаются равными 0.

Вычисление CRC на практике обычно реализуется аппаратно.

Пусть z(D) - частное от деления на g(D).

Тогда = g(D)*z(D)+C(D).

Вычтем C(D) по модулю 2 из обеих частей этого равенства.
x(D) = + C(D) = g(D)z(D)
Таким образом, все кодовые слова делятся на g(D).
Например, в предыдущем примере:

Пусть x(D) передается, а принятая последовательность y(D) отличается от x(D) из-за ошибок в канале связи.

y(D) = x(D)+e(D),

где e(D) - многочлен, представляющий последовательность ошибок.

Несовпадения коэффициентов y(D) и x(D) отмечены в многочлене e(D) единичными коэффициентами.

Т.к. x(D) нацело делится на g(D), то остаток [ y(D)/g(D) ] = остаток [ e(D)/g(D) ]

Если ошибки не возникли e(D) = 0, остаток = 0.

Если остаток не равен нулю, то принятая последовательность содержит ошибки.

Возможен случай, когда e(D) № 0, а остаток = 0. Если e(D) является кодовым словом e(D) = g(D) z(D), то обнаружить ошибки нельзя. g(D) имеет по крайней мере 2 ненулевых члена ( и 1), следовательно g(D)z(D) тоже должно иметь min 2 ненулевых члена (z(D) № 0).

Пусть возникла одиночная ошибка .

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

Поскольку разница между степенями и 1 равна L, то степени старшего и младшего членов g(D)z(D) также отличаются по крайней мере на L (Z(D) № 0). Если e(D) - кодовое слово, то длина пакета ошибок не меньше L+1.

Пусть возникла двойная ошибка, например

не делится на g(D). e(D) нельзя обнаружить, если делится на g(D).

Для любого g(D) существует min число n, для которого делится на g(D) .

А для любого L>0 существуют примитивные многочлены, для которых .

Если g(D) - примитивный многочлен степени L, и если длина кадра меньше , то не может делиться на g(D). Все двойные ошибки обнаруживаются при этом. На практике для вычисления CRC используется порождающий многочлен g(D), который получается произведением примитивного многочлена степени L-1 и многочлена (D+1).

(D+1) позволяет обнаруживать любое нечетное число ошибок.

У такого кода минимальное расстояние >=4,

способность обнаруживать пакеты ошибок >=L,

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

Стандартные ЦИП -коды с L=16:

ЦИП-16

ЦИП-МККТТ (CRC-CCITT)

CRC-32 используется в протоколах обмена данными HDLC и ZMODEM:

Модификация CRC-CCITT:

Первые 16 бит кадра инвертируются при вычислении CRC, а при передаче не инвертируются. Инвертируется остаток для CRC. В приемном модуле первые 16 бит кадра инвертируются для повторного вычисления остатка, который затем инвертируется для сравнения с принятой CRC. При этом удается избежать нулевой последовательности, удовлетворяющей CRC (линия или модем неисправны). Тогда обнаруживаются такие ошибки, как добавление или удаление нулей из начала (конца) кадра.

7. ЛВС Ethernet. Общая шина: Метод доступа.

ЛВС Ethernet: Метод доступа

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

В ЛВС Ethernet применяется метод CSMA/CD. Все рабочие станции подключены к общей шине. Действия, которые должны предприниматься для предотвращения одновременной передачи данных и для организации повторных передач регламентируются стандартом 802.3 IEEE (Разработан Международным институтом инженеров по электротехнике и радиотехнике).

При передаче данных согласно протоколу CSMA/CD станции выполняют 5 шагов:

1. Прослушивание до начала передачи. Станции непрерывно следят, не появился ли в сегменте сигнал "наличие несущей". Присутствие этого сигнала распознается по уровню напряжения и означает, что канал занят.

2. Задержка (ожидание), если канал занят. Если станция обнаружила, что канал занят, необходимо выждать некоторое время (время отсрочки), чтобы избежать появления коллизий.

3. Передача и прослушивание коллизий. Если канал свободен не менее, чем 9,6 мс, станция может начать передачу. пакет передается по кабельной системе в обоих направлениях.

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

Трансиверы (Tranceivers-transciever-приемопередатчик) - электрические устройства, внутренние (размещенные на сетевой плате Ethernet) или внешние (выполненные в виде отдельного устройства), предназначенные для физической передачи и приема данных из среды.

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

Сигнал затора (jam- замятие бумаги, ленты, перфокарт) - сообщение длиной не менее 32 бит, не определяется, но не может совпадать с контрольной последовательностью предыдущего переданного частично пакета.

Станции, вовлеченные в коллизию, увеличивают свои счетчики числа попыток передачи на 1.

4. При возникновении коллизий ожидание перед повторной передачей. Для выбора момента повторной передачи станция станция действует согласно алгоритма отступления.(момент начала новой попытки выбирается случайным образом).

5. Повторная передача или прекращение работы. Станция может попытаться начать передачу до 16 раз, прежде чем прекратит свои попытки.

Для приема данных активная станция, подключенная к сегменту, должна выполнить 4 шага:

1. Просмотр поступающих пакетов данных и обнаружение фрагментов. Если кадр имеет допустимую длину >=64 байт, то он не является фрагментом, порожденным коллизией.

2. Проверка адреса получателя. Если пакет адресован данной станции, является широковещательным сообщением (Например, сообщение об услугах NetWare) или имеет групповой адрес (адресовано определенной группе устройств), то станция переходит к 3 шагу.

3. Проверка целостности пакета данных, если пакет поступил на станцию-получатель.

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

Проверка контрольной последовательности кадра с помощиь CRC. Если CRC некорректна, проверяется выровненность пакета. Все пакеты должны содержать целое число байт и оканчиваться на 8-битовой границе.

Если CRC кадра некорректна, но кадр корректно выровнен, то считается, что имеет место ошибка контрольной последовательности.

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

Стандарт 802.3 содержит спецификации кабеля, пригодные для реализации ЛВС Ethernet.

· 10Base5 (толстый коаксиальный кабель)

· 10Base2 (тонкий коаксиальный кабель)

· 10BaseT (неэкранированная витая пара проводов) добавлена к стандарту в 1991г. Определяет сети с методом доступа CSMA/CD и топологией типа звезда. Сегментом считается кабель соединяющий станцию и концентратор.

	10Base5	10Base2	10BaseT
Максимальное число отводов на сегменте
Разделение узлов не более	5 сегментов и 4репитера	5 сегментов и 4репитера	5 сегментов и 4репитера
Максимальная длина сегмента	500м	185м
Общая длина сети	2500м	925м
Минимальное расстояние между трансиверами	2.5м	0.5м
Максимальная длина трансиверного кабеля	50м
Число концентраторов	не более 4
Максим расстояние между станцией и репитером	100м

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

· Поздней коллизией называется коллизия с пакетом, имеющим длину не менее 64 байт. Наличие таких коллизий свидетельствует о том, что сегмент длиннее, чем указано в спецификации.

· Считается, что станция уцправляет сегментом кабеля, если ею уже передано более 64 байт.