Обнаружение и коррекция ошибок

1.

Обнаружение и коррекция ошибок
ГБПОУ ЧЭнК им. С.М. Кирова Силантьева И.Г.
1

2.

2

3.

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

4.

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

5.

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

6.

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

7.

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

8.

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

9.

Циклический избыточный контроль (Cyclic
Redundancy Check, CRC) является в
настоящее время наиболее популярным
методом контроля в вычислительных сетях
Метод основан на представлении исходных
данных в виде одного многоразрядного
двоичного числа
9

10.

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

11.

11

12.

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

13.

Если
мы
контролируем
три
информационных бита, то разрешенными
4-битными кодами с дополнением до
нечетного количества единиц будут:
000 1,001 0, 010 0, 011 1, 100 0, 101 1, 110 1, 111 0
То есть всего 8 кодов из 16 возможных.
13

14.

Для того чтобы оценить количество
дополнительных битов, требуемых для
исправления ошибок, нужно знать так
называемое расстояние Хемминга между
разрешенными комбинациями кода
Расстоянием
Хемминга
называется
минимальное число битовых разрядов, в
которых
отличается
любая
пара
разрешенных кодов. Для схем контроля по
паритету расстояние Хемминга равно 2
14

15.

Коды Хемминга эффективно обнаруживают
и исправляют изолированные ошибки, то
есть отдельные искаженные биты, которые
разделены
большим
количеством
корректных битов
Однако
при
появлении
длинной
последовательности искаженных битов
(пульсации ошибок) коды Хемминга не
работают
15

16.

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

17.

17

18.

Методы кодирования и коррекции ошибок
позволяют создать в некоторой среде, например в
медных проводах кабеля, линию связи
Однако
для
эффективного
соединения
пользователей сети этого недостаточно. Нужно
образовать в этой линии отдельные каналы
передачи данных, служащие для коммутации
информационных потоков пользователей
Для того чтобы по одному кабелю или
беспроводному каналу связи могло одновременно
передаваться множество сигналов от разных
пользователей
используют
методы
мультиплексирования (уплотнения каналов).
18

19.

Мультиплексирование (multiplexing) – это
технология передачи данных нескольких
каналов
с
меньшей
пропускной
способностью по одному каналу с большей
пропускной способностью.
Задача мультиплексирования – выделить
каждому каналу связи время, частоту и/или
код с минимумом взаимных помех и
максимальным
использованием
характеристик общей среды передачи.
19

20.

В
компьютерных
сетях
используются
следующие
основные
виды
мультиплексирования:
частотное
мультиплексирование (Frequency
Division Multiplexing, FDM);
волновое мультиплексирование (Wave Division
Multiplexing, WDM);
временное мультиплексирование (Time Division
Multiplexing, TDM);
множественный доступ с кодовым разделением
(Code Division Multiple Access, CDMA)
20

21.

Мультиплексирование с разделением по
времени (Time Division Multiplexing, TDM) или
временное мультиплексирование заключается
в
поочередном
предоставлении
взаимодействующим системам всей полосы
пропускания канала на небольшой промежуток
времени. Технология TDM используется в
цифровых каналах связи.
Каждому входному каналу для передачи
блока
данных
выделяется
временной
промежуток, называемый тайм-слотом или
временным слотом.
21

22.

Существуют
два
типа
временного
мультиплексирования
–
синхронный
и
асинхронный.
В синхронном (Synchronous Time Division
Multiplexing) режиме время работы канала
делится на повторяющиеся циклы. Каждый
кадр TDM начинается с синхронизирующей
последовательности и включает n тайм-слотов
одинаковой
длительности.
Тайм-слоты
назначаются
всем,
подключенным
к
мультиплексору входным каналам, нумеруются
и располагаются в кадре TDM в строго
определенном порядке.
22

23.

23

24.

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

25.

Прозрачность
для протоколов верхних
уровней, т.к. он реализуется на физическом
уровне модели OSI.
В течение тайм-слотов можно передавать
разный тип трафика: данные, голос, видео.
Передаваемые блоки данных появляются на
приемной
стороне через одинаковые
промежутки времени и приходят с одним и
тем же временем запаздывания.
В связи с этим не требуется использование
буферов, т.к. поток данных передается и
принимается с одной скоростью.
25

26.

Альтернативой синхронному временному
мультиплексированию служит асинхронное
(Asynchronous
TDM,
ATDM)
или
статистическое (Statistical TDM).
Отправитель получает тайм-слот только в
том случае, если у него имеются данные для
передачи.
Тайм-слоты
не
имеют
фиксированной
длительности
(размер
передаваемого блока данных может быть
переменным), не привязываются к конкретному
входному каналу, а выделяются динамически,
согласно статистики их запросов.
26

27.

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

28.

28

29.

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

30.

Одна пара взаимодействующих устройств не
может монопольно захватить общий канал для
передачи, иначе возникло бы переполнение буфера
мультиплексора
(перегрузка
сети).
Для
предотвращения
переполнения
буферов
мультиплексоров
используются
специальные
методы управления потоком (flow control).
Обычно буферизированные блоки данных
передаются через выходной порт мультиплексора в
том порядке, в котором они поступили, т.е. «первым
пришел, первым ушел» (FIFO, First Input, First Output).
Однако можно организовать дифференцированную
или гарантированную передачу блоков данных.
30

31.

Статистический TDM используется в сетях с
коммутацией пакетов и в сетях с
коммутацией ячеек.
В отличие от синхронного TDM, он не
является прозрачным для протоколов, т.к.
он реализуется на канальном и более
высоких уровнях модели OSI. Конечные
узлы и сетевые устройства должны
поддерживать одни и те же протоколы.
31

32.

При частотном мультиплексировании или
мультиплексировании с разделением по
частоте (Frequency Division Multiplexing, FDM)
широкая полоса пропускания физического
канала F делится на n узких полос частот
f<<F, в каждой из которых создается
логический канал. Размеры частотных полос
f могут быть различными.
32

33.

Каждой взаимодействующей системе
назначается отдельный поддиапазон частот
(логический канал). Отправители могут
посылать
сигналы
одновременно.
Передаваемые по разным логическим
каналам сигналы накладываются на разные
несущие и поэтому в частотной области не
должны пересекаться.
33

34.

34

35.

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

36.

Мультиплексирование
со
спектральным
разделением (Wavelength Division Multiplexing,
WDM) или волновое мультиплексирование
используется в оптических каналах связи и
является
вариантом
частотного
мультиплексирования.
Технология WDM позволяет по одному оптическому
волокну одновременно и независимо передавать
два и более оптических сигнала, используя разные
длины волн. Эта технология также делает
возможной двунаправленную передачу сигналов
по одному волокну (передача на одной длине
волны, прием на другой длине волны).
36

37.

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

38.

38

39.

Частотное
(волновое)
и
временное
мультиплексирование может применяться
одновременно. В этом случае в физическом
канале выделяются частотные полосы. В любой
из этих полос каждой системе для передачи
данных
предоставляются
определенные
интервалы времени.
Примером комбинации частотного и
временного
мультиплексирования
служит
система сотовой связи GSM (Global System for
Mobile Communications).
39

40.

Мультиплексирование
с
кодовым
разделением (Code Division Multiplexing,
CDM) отличается от частотного и
временного мультиплексирования.
В данном методе все каналы используют
один и тот же спектр частот в одно и то же
время, но при этом каждый канал имеет
свой уникальный код.
40

41.

CDM основано на расширении спектра (Spread
Spectrum). Основная идея расширения спектра
заключается в преобразовании информационного
сигнала с узкой полосой пропускания в сигнал с
широкой полосой пропускания.
Достигается это модуляцией информационного
сигнала кодом расширения, который полностью
независим от информационного сигнала и имеет
большую полосу пропускания. В результате
модуляции мощность исходного сигнала не
изменяется, а распределяется по более широкой
полосе пропускания.
41

42.

42

43.

При CDM существует еще одно дополнительное
требование к кодам расширения: они должны быть
независимы друг от друга.
Код расширения уникален для каждого передатчика и
служит
для
идентификации
соединения.
Он
представляет собой последовательность из 8, 16, 32, 64 и
т.п. бит. Для получения сигнала с расширенным спектром
передатчик заменяет каждый бит исходного потока
данных на код расширения с помощью операции XOR
(исключающего ИЛИ). Далее такой шумоподобный
сигнал передается передатчиком в общий канал, через
который одновременно передаются сигналы от
множества других передатчиков.
43

44.

44

45.

Каждый
из
характеризуется
расширения.
передаваемых
сигналов
индивидуальным
кодом
Приемник
знает
код
расширения
передатчика, сигналы которого должен
принимать.
Это
позволяет
выделить
предназначенный ему сигнал из множества
получаемых сигналов. При этом сигналы
других передатчиков с другими кодами
расширения приемник воспринимает как
аддитивный шум.
45

46.

Повышенная защищенность и скрытность передачи
данных: не зная кода, невозможно получить сигнал, а в
ряде случаев – и обнаружить его присутствие.
Кодовое
пространство
несравненно
более
значительно по сравнению с частотной схемой
мультиплексирования, что позволяет без особых
проблем присваивать каждому передатчику свой
индивидуальный код.
Основной проблемой кодового мультиплексирования
до
недавнего
времени
являлась
сложность
технической реализации приемников и необходимость
обеспечения точной синхронизации передатчика и
приемника для гарантированного получения блока
данных.
46

47.

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