30. Методы доступа к среде.

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

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

Методы доступа: 1. Метод коллективного доступа с опознанием несущей и обнаружением коллизий. CSMA/CD: - все ПК «слушают» кабель. Если кабель свободный (нет несущей), то ПК начинает передачу, если есть несущая – передавать нельзя! – Если 2 ПК услышали, что несущей нет и начали передавать одновременно – возникает коллизия, которая распознается и передача прекращается. Последующая передача начинается через промежуток времени.

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

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

31. Сетевые архитектуры – комбинация стандартов топологий и протоколов, необходимых для создания работоспособной сети.

E thernet – 10 Мбит/сек (10 Base 2), 10 – скорость, Base – узкополосная передача, 2 – двойная длина. Тонкий Ethernet т.к диаметр кабеля = 5мм, Rволв =50 Ом, правило 5-4-3 (т.е. 5-сегментов, 4-репитера, 3- к трем сегментам м.б. подключены ПК). Технология использует топологию ШИНА. Расстояние между сегментами = 185 м. На сегмент может приходиться 30 ПК, метод доступа CSMA/CD.

10 Base 5 - Толстый Ethernet диаметр кабеля = 10мм, Rволв =50 Ом. Технология использует топологию ЗВЕЗДА. Расстояние между сегментами = 500 м. На сегмент может приходиться до 100 ПК, подключение происходит чрез транссервер. Симметричный 4-хпарный кабель, может быть до 6-ти различных категорий: тлф, со скоростью 4 Мбит/с, 10 Мбит/с, 16 Мбит/с, до 100 Мбит/с, >100 Мбит/с. метод доступа CSMA/CD. Существуют новые стандарты Ethernet, обеспечивающие передачу 100 Мбит/с: - 100VD-AnyLan, - 100 Base VD/

Среда передачи – витая пара, ОВ. Метод доступа – по приоритету запроса. Поддерживает Ethernet, Token Ring.

Тип кадра Ethernet

1. ф лаг, т.е. начало; 2. Адрес приемника; 3. Адрес отправителя; 4. Тип и длина (указывает прокол сетевого уровня IP и IPX); 5. Данные; 6. Контрольная последовательность кадра.

Token Ring (маркерное кольцо/символьное кольцо) Топология «звезда-кольцо». До 33-х хабов может включатся в кольцо и используется 2 типа кабеля (UTP-неэкранированная витая пара, STP – экранированная). Расстояние между хабами 152 м. При UTP - 72ПК, скорость передачи 16 Мбит/с, при STP –100ПК, скорость передачи 4 Мбит/с. Способ доступа- маркерный. Если сети одноранговые маркер генерирует первый ПК, начинающий работу.

Арифметическое кодирование

Свойства: - вероятность символов м.б. на каждом шаге различная; - незначительный запас памяти; - высокая скорость работы; - символ может соответствовать дробному количеству бит; - кодируется передаваемая последовательность сразу. Алгоритм сжатия: А={а1,а2..ак}, Р={Р(а1), Р(а2)…Р(ак)}, х={х1,х2…хк}.

В ычисление суммарных вероятностей: Q0=0, Q= Р(а1), Q2=Q1+ Р(а2), Qk=Qk-1+ Р(аk).

Разбиение единичного отрезка согласно суммарным вероятностям.

Количество двоичных символов необходимых для кодирования числа архива определяется по формуле: -log(δ_L)+1 = число архив, δ_L- длина последнего рассматриваемого участка.

d_j= d_j-1 + Q_i-1 δ _j-1, ; u_j= d_j-1 + Q_i δ _j-1; δ _j= u_j-d_j

где j-номер сообщения в кодируемом блоке, i – номер сообщения в исходном алфавите.

Декодирование: рассматривать на примере!

Сверточные коды

Сверточные коды (СК) относятся к непрерывным кодам. Здесь нет деления на кодовые комбинации как в блочных. Выходные элементы, в данном случае, зависят от ряда предшествующих информационных элементов. Можно сказать, что передаваемая последовательность является одним полубесконечным кодовым словом. Свёрточный код описывается тремя целыми числами (n, k,K). Отношение имеет такой же смысл скорости кода, как и для блочного, но n не определяет длину блока. В данном случае k элементов, поступающих в кодер, порождают n элементов на его выходе. K – длина кодового ограничения, оно определяется числом разрядов (ячеек памяти) в кодирующем регистре сдвига. Кодовое ограничение определяет мощность и сложность кода. Выходные элементы СК зависят не только от текущего входного элемента, но и от (K-1) предыдущих. Т.е. СК имеет память.

Рассмотрим простейший сверточный код (2.1.3). В данном случае каждому входному элементу будет соответствовать 2 выходных, полученных посредством суммирования текущего и (K-1=3-1) двух предыдущих элементов. Коэффициенты связи ячеек с сумматорами: g₀=(11) – нулевая ячейка связана и с 1 и со 2 сумматором; g₁=(01) – первая ячейка связана и со 2 сумматором; g₂=(11) – вторая ячейка связана и с 1 со 2 сумматором.

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

Например:

Полиномиальное представление связи.

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

Таблица соответствия содержимого ячеек регистра и выходного вектора

И мпульсная характеристика кодера – реакция на единицу, за которой следует все нули.

Для кода 2.1.3:

1 00→11

010→01

001→11 11011100…00

000→00

……………

000→00

Н апример: На вход кодера поступает последовательность 1 0 1

Диаграмма состояний кодера

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

Диаграмма состояний кодера и ретчатая диаграмма.

Оценка исправляющей способности сверточного кода

Для блочных кодов исправляющая способность есть номинальное количество ошибок в блоке длиной n, которое может быть гарантированно исправлено. Данная способность однозначно определяется кодовым расстоянием: Для СК исправляющая способность не может быть задана так однозначно. Данная способность определяется через просвет или свободное расстояние кода по аналогичной формуле: Причём, при декодировании по принципу максимального правдоподобия СК способен исправить заданное количество ошибок в пределах нескольких длин кодовых ограничений («несколько» - это от 3 до 5 К). Точное значение зависит от распределения ошибок. Просветом или свободным расстоянием называется минимальный вес пути, начинающегося и заканчивающегося в нулевом состоянии.

1) 100 d=5

2) 1100 d=6

3) 10100 d=6

Для рассматриваемого кода (2.1.3) минимальный просвет df =5, значит он может исправить две любые ошибки.

Декодирование сверточных кодов.

Алгоритм декодирования Витерби

Задача декодирования сверточного кода заключается в выборе пути вдоль решетки наиболее похожего на принятую последовательность. В нашем случае (2,1,3) каждому информационному элементу соответствует кодовое слово из n=2 элементов. Каждый путь вдоль решетки складывается из ветвей соединяющих узлы. Каждой ветви решетки соответствует кодовое слово из двух бит. Каждую ветвь на каждом периоде можно пометить расстоянием Хемминга между полученным кодовым словом и кодовым словом, соответствующим ветви. Складывая расстояния Хемминга ветвей, составляющих путь, получим метрику соответствующего пути.

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

В каждый момент времени в решетке существует состояний в каждое из которых может войти два пути. Таким образом, всего 8 путей. После принятия решения остается 4 выживших.

1. с равниваем 11 и 00, т.к. отличие в 1, записываем «1» расстояние Хемминга.

2. 10 с 11→1

3. 00 и 00, различий нет, но на предыдущем этапе расстояние=1=>1

4. 00 и 11, различаются на 2+предыдущий=>3

Передаваемая последовательность (все «0»), принимаемая последовательность (в 1 и 3 «1»-ошибки)

С истематические и несистематические сверточные коды.

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

И нтеративные коды.

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

Принцип кодирования: 1. Сообщение источника кодируется кодом (К1,r1); 2. К2 слов в первой ступени запишем как строки матрицы. Столбцы матрицы являются К2 информационными элементами для 2-й ступени. 3. Дописываем проверочные элементы для 2-й ступени К2,r2. r2=n2-K2. 4. Получаем блок n1xn2 элементов, где всего символов n1•n2, из них информационные К1•К2.

Скорость передачи данных в этом случае будет определяться К1•К2=l.

Декодирование интеративных кодов.

1 . С помощью первой ступени обнаруживают и исправляют ошибки; 2. После принятия всего кода исправляют ошибки по столбцам кодом второй ступени. При этом исправляют только те ошибки, которые не были исправлены кодом 1-й ступени. d∑=d1•d2. Интеративный код позволяет исправлять все одиночные ошибки.

Каскадные коды

Принцип кодирования: - информационные символы разбиваются по К2 блока по К1 символов в каждом; - этим К2 добавляют r2 проверочных символа r2=n2-k2.

Принцип декодирования: - Сначала декодируются все блоки внутреннего двоичного кода. При этом исправляются все ошибки малой кратности в столбцах; - затем внешнего, при этом исправляются ошибки оставшиеся после внутреннего декодирования.

1. Основные параметры и определения. Информация. Сообщение. Основные характеристики источника дискретных сообщений и канала ПДС. (Количество информации в сообщении, энтропия, бит и бод, скорость передачи информации, пропускная способность канала.)

2. Виды сигналов. Основные определения, относящиеся к цифровым сигналам данных. (Информационный параметр, элемент ЦСД, значащие позиция, момент, интервал, единичный элемент и интервал.)

3. Структура системы передачи дискретных сообщений. Назначение элементов структуры СПДС.

4. Непрерывный канал связи. Основные характеристики. Требования к каналам, предназначенным для передачи дискретных сигналов.

5. Дискретный канал непрерывного времени (КПТ). Краевые .искажения Ли дробления. Механизмы их возникновения.

6. Методы регистрации сигналов. Структурные схемы методов регистрации. Сравнение методов.

7. Дискретный канал. Определение ошибок кратности t в принятой последовательности из n элементов. Причины возникновения памяти канала.

8. Расширенный дискретный канал. Основные характеристики. Методы повышения верности. Понятие о корректирующих кодах. Кодовое расстояние и его связь с обнаруживающей и исправляющей способностью кода.

9. Внешние и внутренние параметры системы ПДС. Выбор наилучшей системы. Информационная эффективность. Частотная и энергетическая эффективность.

10. Эффективное (статистическое) кодирование. Назначение. Понятие префиксного кода. Метод Хаффмена. Достоинства и недостатки эффективного кодирования.

11. Методы сопряжения источника дискретного сигнала с дискретным каналом. Методы наложения, скользящего индекса с подтверждением, стаффинга.

12. Линейные (групповые) коды. Построение кода Хеминга. Производящая матрица. Правила получения проверочных разрядов. Структурная схема кодера.

13. Обнаружение и исправление ошибок в групповых кодах. Понятие синдрома. Определение ошибочного разряда. Структурная схема декодера.

14. Циклические коды. Алгоритмы построения циклических кодов. Получение разрешенной кодовой комбинации. Построение кодера ЦК.

15. Циклические коды. Определение ошибочного разряда в кодовой комбинаций ЦК. Структурные схемы декодеров ЦК.

16. Синхронизация в системах ПДС. Назначение. Виды синхронизации. Классификация систем синхронизации по элементам. Оценка времени поддержания синхронизма в системах с автономным генератором.

17. Устройство системы синхронизации с добавлением и вычитанием импульсов. Структурная схема. Принцип работы.

18. Расчет параметров поэлементной синхронизации: Погрешность синхронизации, время синхронизации, время поддержания синхронизма, вероятность срыва синхронизма.

19. Перекодирование. Линейные коды используемые в сетях передачи данных. Логическое кодирование и скремблирование.

20. УПС. Назначение. Методы преобразования спектра с использованием несущей: АМ, ЧМ, ФМ. Связь ширины спектра канала и максимальной скорости модуляции. Структурные схемы, реализующие данные методы.

21. Относительная фазовая модуляция. Формирование ОФМ – сигнала. Когерентный и некогерентный прием. Многопозиционная и амплитудно-фазовая модуляция.

22. Адаптация в СПДС. Назначение и преимущества адаптивных систем. Виды систем с обратной связью. Структурная схема и алгоритм работы СПДС и ИОС. Преимущества и недостатки.

23. СПДС с РОС-ОЖ. Структурная схема и алгоритм работы, время ожидания. Явления сдвига и борьба с ними.

24. Расчет вероятности неправильного приема и скорости передачи в системах ПДС с РОС-ОЖ.

25. Интерфейс RS-232. Понятие интерфейса и порта. Ресурсы порта, линия запроса, прерывания, базовый адрес ввода/вывода. Назначение УАПП. Конфигурирование СОМ-порта.

26. Современные модемы: назначение, виды, основные возможности и параметры. Протоколы современных модемов. Подключение модема к компьютеру. Телекоммуникационное программное обеспечение.

27. Устройства регистрирования ЛВС. IP-адресация.

28. Сети ПД. Компьютерные сети.

29. Архитектура взаимодействия открытых систем.

30. Методы доступа к среде.

31. Сетевые архитектуры Ethernet, Token Ring.