Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Шпаргалки по вычислительным сетям - файл 1.doc


Шпаргалки по вычислительным сетям
скачать (5160 kb.)

Доступные файлы (1):

1.doc5160kb.25.11.2011 11:55скачать

содержание
Загрузка...

1.doc

  1   2   3   4
Реклама MarketGid:
Загрузка...
Ответы на вопросы по сетям

  1. Уровни открытых вычислительных сетей. Интерфейс. Протокол

Реализация рассредоточенных и взаимодействующих процессов в сетях осуществляется на основе двух концепций, одна из которых устанавливает связи между процессами без функциональной среды между ними, а другая определяет связь только через функциональ­ную среду. В первом случае правильность понимания действий, про­исходящих в рамках соединяемых процессов взаимодействующих АС, обеспечивается соответствующими средствами теледоступа в составе сетевых операционных систем (СОС). Однако предусмотреть такие средства на все случаи соединения процессов нереально. Поэтому взаимодействующие процессы в сетях соединяются с помощью функ­циональной среды, обеспечивающей выполнение определенного сво­да правил — протоколов связи процессов. Обычно эти протоколы реализуются с учетом принципа пакетной коммутации, в соответствии с которым перед передачей сообщение разбивается на блоки — паке­ты определенной длины. Каждый пакет представляет собой независи­мую единицу передачи информации, содержащую, кроме собственно данных, служебную информацию (адреса отправителя и получателя, номер пакета в сообщении, информацию для контроля правильности принятых данных).

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

В соответствии с эталонной моделью ВОС абонентская система представляется прикладными процессами и процессами взаимодей­ствия АС (рис. 12.3). Последние разбиваются на семь функциональ­ных уровней. Функции и процедуры, выполняемые в рамках одного функционального уровня, составляют соответствующий уровневый протокол. Нумерация уровневых протоколов идет снизу вверх, а их названия указаны на рис. 1. Функциональные уровни взаимодей­ствуют на строго иерархической основе: каждый уровень пользуется услугами нижнего уровня и, в свою очередь, обслуживает уровень, расположенный выше. Стандартизация распространяется на прото­колы связи одноименных уровней взаимодействующих АС. Создание ТВС в соответствии с эталонной моделью ВОС открывает возмож­ность использования сети ЭВМ различных классов и типов. Поэтому сеть, удовлетворяющая требованиям эталонной модели, называется открытой.



Функциональные уровни рассматриваются как составные неза­висимые части процессов взаимодействия^ АС. Основные функции, реализуемые в рамках уровневых протоколов, состоят в следующем.

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

^ Канальный уровень определяет правила совместного использования физического уровня узлами связи. Главные его функции: управление передачей данных по информационному каналу (генерация стартово­го сигнала и организация начала передачи информации, передача ин­формации по каналу, проверка получаемой информации и исправле­ние ошибок, отключение канала при его неисправности и восстановле­ние передачи после ремонта, генерация сигнала окончания передачи и перевода канала в пассивное состояние) и управление доступом к пе­редающей среде, т.е. реализация выбранного метода доступа к обще­сетевым ресурсам. Физический и канальный уровни определяют ха­рактеристики физического канала и процедуру передачи по нему кад­ров, являющихся контейнерами, в которых транспортируются пакеты.

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

^ Транспортный уровень занимает центральное место в иерархии уровней сети. Он обеспечивает связь между коммуникационной под­сетью и верхними тремя уровнями, отделяет пользователя от физи­ческих и функциональных аспектов сети. Главная его задача — уп­равление трафиком (данными пользователя) в сети. При этом выпол­няются такие функции, как деление длинных сообщений, поступающих от верхних уровней, на пакеты данных (при передаче информации) и формирование первоначальных сообщений из набора пакетов, полу­ченных через канальный и сетевой уровни, исключая их потери или смещение (при приеме информации). Транспортный уровень есть гра­ница, ниже которой пакет данных является единицей информации, управляемой сетью. Выше этой границы в качестве единицы инфор­мации рассматривается только сообщение. Транспортный уровень обеспечивает также сквозную отчетность в сети.

^ Сеансовый уровень предназначен для организации и управления сеансами взаимодействия прикладных процессов пользователей (се­анс создается по запросу процесса пользователя, переданному через прикладной и представительный уровни). Основные функции: управ­ление очередностью передачи данных и их приоритетом, синхрониза­ция отдельных событий, выбор формы диалога пользователей (полу-дуплексная, дуплексная передача).

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

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

Работы по совершенствованию эталонной модели ВОС для ЛВС привели к декомпозиции уровней 1 и 2. Канальный уровень разделен на два подуровня: подуровень управления логическим каналом (пере­дача кадров между PC, включая исправление ошибок, диагностика работоспособности узлов сети) и подуровень управления доступом к передающей среде (реализация алгоритма доступа к среде и адреса­ция станций сети). Физический уровень делится на три подуровня: передачи физических сигналов, интерфейса с устройством доступа и подключения к физической среде.

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

Интерфейс – алгоритм обмена информации между соседними уровнями одной станции.

Протокол – алгоритм обмена информации между одноименными уровнями разных станций сети.
Примеры протоколов:

Х.21 – протокол физического уровня,

HDLC – канального,

Х.25 – транспортный, сетевой уровень и др.



  1. Асинхронные и синхронные режимы передачи (бит управления)

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

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

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

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

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

/*Дополнение из Олифера*/

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

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

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

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

В асинхронном режиме каждый байт данных сопровождается специальными сигналами «старт» и «стоп» (рис. 2.20, а). Назначение этих сигналов состоит в том, чтобы, во-первых, известить приемник о приходе данных и, во-вторых, чтобы дать приемнику достаточно времени для выполнения некоторых функций, связанных с синхронизацией, до поступления следующего байта. Сигнал «старт» имеет продолжительность в один тактовый интервал, а сигнал «стоп» может длиться один, полтора или два такта, поэтому говорят, что используется один, полтора или два бита в качестве стопового сигнала, хотя пользовательские биты эти сигналы не представляют.

Асинхронным описанный режим называется потому, что каждый байт может быть несколько смещен во времени относительно побитовых тактов предыдущего байта. Такая асинхронность передачи байт не влияет на корректность принимаемых данных, так как в начале каждого байта происходит дополнительная синхронизация приемника с источником за счет битов «старт». Более «свободные» временные допуски определяют низкую стоимость оборудования асинхронной системы.

При синхронном режиме передачи старт-стопные биты между каждой парой байт отсутствуют. Пользовательские данные собираются в кадр, который предваряется байтами синхронизации (рис. 2.20, б). Байт синхронизации — это байт, содержащий заранее известный код, например 0111110, который оповещает приемник о приходе кадра данных. При его получении приемник должен войти в байтовый синхронизм с передатчиком, то есть правильно понимать начало очередного байта кадра. Иногда применяется несколько синхробайт для обеспечения более надежной синхронизации приемника и передатчика. Так как при передаче длинного кадра у приемника могут появиться проблемы с синхронизацией бит, то в этом случае используются самосинхронизирующиеся коды.



Рис. 2.20. Асинхронная (а) и синхронная (б) передачи на уровне байт

  1. Энтропия. Пропускная способность симметричного канала с шумами.

Энтропия – это удельное количество информации, приходящееся на один элемент сообщения.

Энтропия – Ко­ли­чественная мера неопределенности, которая выражает как функция множества вероятностей каждого из возможных исходов.

Объект может содержать информацию, количество которой оценивается на основе логарифма

I = log2 m, где m – число состояний

Пример: среднее количество информации, приходящееся на одну букву алфавита:



Если вероятности появления различных букв алфавита неодинаковы, то можно говорить о распределении вероятности:



Канал связи с шумами:



Пусть источник двоичный, т.е. имеет два состояния 0 и 1. Энтропия зависит от вероятности встречаемости 0 и 1. Пусть они равновероятны, т.е. p0=p1=0.5, тогда энтропия источника сигнала (мера неопределенности)

H(X)=p0·log2 p0 + p1·log2 p1 = 1

q – вероятность искажения каждого передаваемого символа (одинакова для 0 и 1)



Такой канал связи называется – Двоичный симметричный канал с независимым распределением ошибки (каждая посылка не зависит от других)



Определим энтропию сигнала:

- энтропия приема сигнала Y при передаче сигнала X0, аналогично .

Общая энтропия:

При подстановке получим

p(X0) = p(X1) = 0.5

Энтропия – мера неопределенности – потеря информации из-за шумов

Потеря информации при передаче определяет пропускную способность канала связи:

, где C – скорость канала (пропускная способность без шумов)



Пример:

С = 100 bit/sec, q=0.01 – вероятность искажения

ΔI = 100(1-[0.99·log0.99+0.01·log0.01]) = 92 bit/sec (уменьшение )

Для различных пропускных способностей C3>C2>C1 будут различные вероятности искажения q3>q2>q1. Т.е. надо найти оптимальную скорость передачи.
Несимметричный канал с независимым распределением ошибок (q0 ≠ q1)



H(X) ≠ 1, H(X) = p0·log p0 + p1·log p1



  1. Энтропия. Пропускная способность канала со стиранием.

q – вероятность ошибки, w – вероятность стирания («сигнал не распознан»)



Определим пропускную способность канала со стиранием

H(X)=p0·log2 p0 + p1·log2 p1 = 1 (при равной вероятности «0» и «1», т.е. p0=p1=0.5 )

p(Y0/X0)=1-q-w p(Y1/X0)=q p(Y2/X0)=w

p(Y0/X1)=q p(Y1/X1)=1-w-q p(Y2/X1)=w

H(Y/X0) = -[(1-w-q)·log2(1-w-q) + w·log2 w + q·log2 q]

H(Y/X1) = H(Y/X0)

H(Y/X) = p0·H(Y/X0) + p1·H(Y/X1) = -[(1-w-q)·log2(1-w-q) + w·log2 w + q·log2 q]

Пропускная способность будет равна ∆I=[H(X)-H(Y/X)]·C, где C – скорость канала.

  1. Энтропия. Пропускная способность ненадёжного канала.

q – вероятность ошибки при передаче сигнала



Определим пропускную способность ∆I ненадёжного канала, учитывая, что

p(x0)+p(x1)+p(x2)=1

H(X) = p0·log2 p0 + p1·log2 p1 + p2·log2 p2

p(Y0/X0)=1-q p(Y1/X0)=q p(Y2/X0)=0

p(Y0/X1)=q p(Y1/X1)=1-q p(Y2/X1)=0

p(Y0/X2)=0 p(Y1/X2)=0 p(Y2/X2)=1

H(Y/X0) = -[(1-q)·log2(1-q) + q·log2 q]

H(Y/X1) = H(Y/X0)

H(Y/X2) = -[1·log2 1] = 0

H(Y/X) = p0·H(Y/X0) + p1·H(Y/X1) + p2·H(Y/X2) = -[(1-q)·log2(1-q) + q·log2 q] ·(p0+p1) =

= -[(1-q)·log2(1-q) + q·log2 q] ·(p0+p1)

Пропускная способность будет равна ∆I=[H(X)-H(Y/X)]·C, где C – скорость канала.


  1. Энтропия. Пропускная способность многопозиционного канала.

Многопозиционный канал отличается от двоичного тем, что может передавать не два значения (0 или 1), а m значений (0,1,2 ... m-1). Пусть q – вероятность ошибки при передаче сигнала.



Определим пропускную способность ∆I m-позиционного канала, учитывая, что

p(x0)+p(x1)+...+p(xm-1)=1

H(X) = p0·log2 p0 + p1·log2 p1 +...+ pm-1·log2 pm-1

p(Y0/X0)=1-q p(Y1/X0)=q/(m-1) ... p(Ym-1/X0)= q/(m-1)

p(Y0/X1)= q/(m-1) p(Y1/X1)=1-q ... p(Ym-1/X1)= q/(m-1)

... ... ... ...

p(Y0/Xm-1)= q/(m-1) p(Y1/Xm-1)= q/(m-1) ... p(Ym-1/Xm-1)=1-q

H(Y/X0)=H(Y/X1)=...= H(Y/Xm-1)= -[(1-q)·log2(1-q) + (m-1)·(q/(m-1))·log2 (q/(m-1))]

H(Y/X) = p0·H(Y/X0) + p1·H(Y/X1) + ... +pm-1·H(Y/Xm-1) = {пусть p0=p1=...=pm-1=1/m} =

= -[(1-q)·log2(1-q) + (m-1)·(q/(m-1))·log2 (q/(m-1))]

Пропускная способность будет равна ∆I=[H(X)-H(Y/X)]·C, где C – скорость канала.



  1. Статистические коды Шеннона-Фоно, Хаффмана.

Теория кодирования. Основные определения.

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

  • это совокупность условных символов или сигналов, обозначающих определенные сообщения;

  • это множество слов в некотором алфавите, поставленное во взаимооднозначное соответствие другому множеству.

Цель кодирования: представить информацию в более компактной форме для дальнейшей передачи и обработки; приспособить закодированную информацию к обработке на конкретном устройстве.

Условные сигналы, составляющие код, называются кодовыми комбинациями или кодовыми словами.

Число элементов или знаков, образующих кодовую комбинацию называют значимостью кода.

Разновидности кодов.

  1. По обнаружению ошибок: не обнаруживающие ошибки, обнаруживающие ошибки, обнаруживающие и исправляющие ошибки.

  2. По длине: равномерные (все комбинации имеют равную длину) m – основа кода, n – значимость, N = mn – число комбинаций; неравномерные.

  3. По обратимости: обратимые коды (кодовые комбинации различных сообщений различны, любая кодовая комбинация является началом другой); необратимые (кодовые комбинации различных сообщений могут быть одинаковы), этот код требует специальных разделительных знаков, которые ставятся между кодовыми комбинациями для правильного декодирования.

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

Код Шеннона-Фано.

Изначально считается, что буквы статистически не связаны между собой. В результате код получается неравномерным и обратимым.

Код строится следующим образом: символы алфавита сообщений выписываются в таблицу в порядке убывания их вероятностей, затем они разделяются на две (для bin кода) группы так, чтобы суммы вероятностей каждой группы были, по возможности, одинаковыми. Всем буквам верхней половины в качестве первого символа присваивается 0, а второй половине – 1. Каждая их полугрупп в свою очередь разбивается на две подгруппы с одинаковыми вероятностями и т. д. Процесс повторяется до тех пор, пока в любой подгруппе не останется по одной букве.

Пример. Закодировать следующий алфавит, состоящий из 5 букв: A = {A1, ..., A5} с помощью bin кода, причем вероятности букв следующие:

P(A1) = 1/4

P(A2) = 1/4

P(A3) = 1/4

P(A4) = 1/8

P(A5) = 1/8

Ai

P(Ai)










A1

0,25

0

0




A2

0,25

1

A3

0,25

1

0

A4

0,125




1

0

A5

0,125




1


Рассмотрим преимущества кода Шеннона-Фано по сравнению с другими кодами.




код Ш-Ф

равномерный код

A1

00

000

A2

01

001

A3

100

010

A4

110

011

A5

111

100

Пусть нужно передать 1000 знаков, тогда:

по равномерному коду: V = 3*1000 = 3000,

по Ш-Ф:




A1

A2

A3

A4

A5

Часть

250

250

250

125

125

Значимость

2

2

2

3

3

i

500

500

500

375

375

V = 500 + 500 + 500 + 375 + 375 = 2250.

Для оценки эффективности неравномерного кода применяется не длина отдельных слов, а их средняя длина:

, где

n – общее число сообщений,

li – длина кодового обозначения для сообщения Ai,

P(Ai) – вероятность.



По методу Ш-Ф получается, что чем более вероятно сообщение, тем быстрее оно образует самостоятельную группу и тем более коротким кодом оно будет представлено. Это обстоятельство обеспечивает высокую экономичность кода Ш-Ф.

Примечание:

1. Теорема. Для самого экономичного bin равномерного кода в случае n-буквенного алфавита исходных сообщений, длина k кодовых комбинаций должна удовлетворять следующему неравенству:

.

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

3. При передаче длинных сообщений можно построить более выгодный bin код. Для этого неоьходимо отказаться от побуквенного кодирования, а вместо этого использовать т. н. блоковые коды, в которых кодовые обозначения сопоставляются блокам, состоящим из фиксированного числа последовательности букв. Метод Ш-Ф выгоден при блочном кодировании.

Код Хаффмана.

Код Хаффмана близок к коду Ш-Ф, но является более экономичным. Относится к неравномерным обратимым кодам.

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

Алгоритм. Буквы алфавита A выписываются в основной столбец по убыванию вероятностей. Две последние буквы объединяются в одну вспомогательную букву и получяется новый алфавит A1 из алфавита A путем однократного сжатия последней буквы. Затем вероятности букв, не участвующих в объединении и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей. Процесс сжатия алфавита Ai повторяется до тех пор, пока не получится единственная вероятность буквы = 1, при этом условимся приписывать буквам ai 0 и 1.

Пример. A = {0,05; 0,2; 0,4; 0,2; 0,05; 0,1}.

A3

0,4

0

0,4

0

0,4

0

0,4

0

0,6

1

A2

0,2

10

0,2

10

0,2

10

0,4

11

0,4

0

A4

0,2

111

0,2

111

0,2

111

0,2

10







A6

0,1

1101

0,1

1101

0,2

110













A1

0,05

11001

0,1

1100



















A5

0,05

11000

























A1 → 11001

A2 → 10

A3 → 0

A4 → 111

A5 → 11000

A6 → 1101



Кодирование некоторого алфавита по методам Ш-Ф и Х не является однозначно определенной процедурой. Например, можно при кодировании поменять местами 0 и 1. Можно построить более существенно отличный код Х, когда вновь полученная вероятность ставится в ряд на первое место с такими же по величине вероятностями.

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

  1. Частотная модуляция. Частотный детектор.


Частотные модуляторы

G - генератор

УДЧ – управляемый делитель частоты

ФНЧ – фильтр низких частот

> - усилитель

Форм. – формирователь



ФЦАП – функциональный цифро-аналоговый преобразователь

УНЧ – усилитель низких частот

  1   2   3   4



Скачать файл (5160 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru