Реферат: Сети ЭВМ и телекоммуникации

СЕТИ ЭВМ И ТЕЛЕКОММУНИКАЦИИ
СЕТИ ЭВМ И ТЕЛЕКОММУНИКАЦИИ 1

Вопрос №1. Аналоговые каналы передачи данных, модемы и способы модуляции; 1

Вопрос №2. Методы доступа и протоколы канального уровня локальных сетей 4

Вопрос№3. Способы контроля правильности передачи данных в компьютерных сетях; 5

Вопрос №4Алгоритмы сжатия данных в компьютерных сетях 7

Вопрос №5. Функции сетевого и транспортного уровней компьютерных сетей 9

Вопрос№6 Сетевые операционные системы 11

Вопрос №7.Web-технологии, языки и средства создания Web-приложений 13

Вопрос №8. Алгоритмы маршрутизации 15

Вопрос № 9. Протоколы TCP/IP 18

Вопрос № 10. Адресация канального и сетевого уровней. 20

Вопрос №11. Протоколы файлового обмена, электронной почты, telnet, http 22

Вопрос №12. Дистанционное управление и администрирование компьютерных сетей. 26

Вопрос №13. Эталонная модель взаимосвязи открытых систем. 29

Вопрос №14. Особенности технологий Frame Relay, АТМ и SDH 37

Вопрос №15. Сегментация компьютерных сетей на основе мостов, коммутаторов и маршрутизаторов. 41



^ Вопрос №1. Аналоговые каналы передачи данных, модемы и способы модуляции;
Аналоговые каналы передачи данных

Аналоговые и цифровые каналы

В зависимости от типа передаваемых сигналов различают два больших класса каналов связи цифровые и аналоговые.

^ Цифровой канал является битовым трактом с цифровым (импульсным) сигналом на входе и выходе канала. На вход аналогового канала поступает непрерывный сигнал, и с его выхода также снимается непрерывный сигнал (рис 1) Как известно, сигналы характеризуются формой своего представления

Рис 1.

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

^ Аналоговые каналы являются наиболее распространенными по причине длительной истории их развития и простоты реализации. Типичным примером аналогового канала является канал тональной частоты (ктч), а также групповые тракты на 12, 60 и более каналов тональной частоты. Телефонный канал КТСОП, как правило, включает многочисленные коммутаторы, устройства разделения, групповые модуляторы и демодуляторы. Для КТСОП этот канал (его физический маршрут и ряд параметров) будет меняться при каждом очередном вызове.

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

Классификация модемов

Модем - устройство преобразования кодов и представляющих их электрических сигналов при взаимодействии аппаратуры окончания канала данных и линий связи. Слово "модем" образовано из частей слов "модуляция" и "демодуляция", что подчеркивает способы согласования параметров сигналов и линий связи - сигнал, подаваемый в линию связи, модулируется, а при приеме данных из линии сигналы подвергаются обратному преобразованию (рис. 2.).

Рис. 2.

Строгой классификации модемов не существует и, вероятно, не может существовать по причине большого разнообразия как самих модемов, так и сфер применения и режимов их работы. Тем не менее можно выделить ряд признаков, по которым и провести условную классификацию. К таким признакам или критериям классификации можно отнести следующие: область применения; функциональное назначение; тип используемого канала; конструктивное исполнение; поддержка протоколов модуляции, исправления ошибок и сжатия данных. Можно выделить еще множество более детальных технических признаков, таких как применяемый способ модуляции, интерфейс сопряжения с DTE и так далее.

^ По области применения

Современные модемы можно разделить на несколько групп:

для коммутируемых телефонных каналов и для выделенных (арендуемых) телефонных каналов;

для физических соединительных линий:

модемы низкого уровня (линейные драйверы) или модемы на короткие расстояния (short range modems),

модемы основной полосы (. baseband modems);

для цифровых систем передачи (CSU/DSU);

для сотовых систем связи;

для пакетных радиосетей;

для локальных радиосетей.

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

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

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

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

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

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

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

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

^ Локальные радиосети являются быстроразвивающейся перспективной сетевой технологией дополняющей обыкновенные локальные сети. Ключевым их элементом являются специализированные радиомодемы (адаптеры локальных радиосетей). В отличие от ранее упомянутых пакетных радиомодемов такие модемы обеспечивают передачу данных на небольшие расстояния (до 300 м) с высокой скоростью (2—10 Мбит/с), сопоставимой со скоростью передачи в проводных локальных сетях.

^ По методу передачи

По методу передачи модемы делятся на асинхронные и синхронные. Говоря о синхронном либо асинхронном методе передачи обычно подразумевают передачу по каналу связи между модемами. Однако передача по интерфейсу DTE—DCE также может быть синхронной и асинхронной. Как правило, синхронизация реализуется одним из двух способов, связанных с тем, как работают тактовые генераторы отправителя и получателя: независимо друг от друга (асинхронно) или согласованно (синхронно). Если передаваемые данные составлены из последовательности отдельных символов, то, как правило, каждый символ передается независимо от остальных и получатель синхронизируется вначале каждого получаемого символа. Для такого типа связи обычно используется асинхронная передача. Если передаваемые данные образуют непрерывную последовательность символов или байтов, то тактовые генераторы отправителя и получателя должны быть синхронизированы в течение длительного промежутка времени. В этом случае используется синхронная передача.

^ Асинхронный режим передачи используется главным образом тогда, когда передаваемые данные генерируются в случайные моменты времени, например пользователем. При такой передаче получающее устройство должно восстанавливать синхронизацию в начале каждого получаемого символа. Для этого каждый передаваемый символ обрамляется дополнительным стартовым и одним или более стоповыми битами. Такой асинхронный режим часто применяется при передаче данных по интерфейсу DTE—DCE. При передаче данных по каналу связи возможности применения асинхронного режима передачи во многом ограничены его низкой эффективностью и необходимостью использования при этом простых методов модуляции, таких как амплитудная и частотная..

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

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

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

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

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

По интеллектуальным возможностям

По интеллектуальным возможностям можно выделить модемы:

без системы управления;

поддерживающие набор АТ-команд;

с поддержкой команд V. 25bis;

с фирменной системой команд;

поддерживающие протоколы сетевого управления.

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

Наиболее распространенным набором команд, позволяющим управлять режимами установления соединения и автовызова, являются команды рекомендации ITU-T V. 25bis.

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

Промышленные модемы часто поддерживают протокол сетевого управления SMNP (Simple Manager Network Protocol), позволяющий администратору управлять элементами сети (включая модемы) с удаленного терминала.

По конструкции

По конструкции различают модемы:

внешние;

внутренние;

портативные;

групповые.

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

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

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

Способы модуляции

Амплитудная модуляция.

Рис. 3. Спектры модулирующего и

модулированного сигналов при АМ

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

V = Vm*sin(W *t+j )

с амплитудой Vm, частотой W и фазой j , то на выходе нелинейного элемента в модуляторе будут модулированные колебания

UАМ = Um*(1+m*sin(W *t+j ))*sin(v *t+y ),

где m = Vm/Um - коэффициент модуляции. На выходе модулятора в спектре сигнала присутствуют несущая частота v и две боковые частоты v +W и v -W . Если сигнал занимает некоторую полосу частот, то в спектре модулированного колебания появятся две боковые полосы, как это показано на рис. 3

При амплитудной модуляции во избежание искажений, называемых качанием фронта, нужно выполнение условия v >> W , где v и W - соответственно несущая и модулирующая частоты. Соблюдение этого условия при стандартной (для среднескоростной аппаратуры передачи данных) несущей частоте 1700 Гц не может обеспечить информационные скорости выше 300 бит/с.

^ Фазовая модуляция

(PSK - Phase Shift Keying) двумя уровнями сигнала (1 и 0) осуществляется переключением между двумя несущими, сдвинутыми на полпериода друг относительно друга. Другой вариант PSK изменение фазы на p /2 в каждом такте при передаче нуля и на 3/4*p , если передается единица.

^ Квадратурно-амплитудная модуляция

(QAM - Quadrature Amplitude Modulation, ее также называют квадратурно-импульсной) основана на передаче одним элементом модулированного сигнала n бит информации, где n = 4...8 (т.е. используются 16... 256 дискретных значений амплитуды). Однако для надежного различения этих значений амплитуды требуется малый уровень помех (отношение сигнал/помеха не менее 12 дБ при n = 4).

При меньших отношениях сигнал/помеха лучше применять фазовую модуляцию с четырьмя или восемью дискретными значениями фазы для представления соответственно 2 или 3 бит информации. Тогда при скорости модуляции в 1200 бод (т.е. 1200 элементов аналогового сигнала в секунду, где элемент - часть сигнала между возможными сменами фаз) и четырехфазной модуляции скорость передачи данных равна 2400 бит/с. Используются также скорости передачи 4800 бит/с (при скорости модуляции 1600 бод и восьмифазной модуляции), 9600 бит/с и более при комбинации фазовой и амплитудной модуляций.

^ Кодово-импульсная модуляция

(КИМ или PCM - Pulse Code Modulation) используется для передачи аналоговых сигналов по цифровым каналам связи.

Этот вид модуляции сводится к измерению амплитуды аналогового сигнала в моменты времени, отстоящие друг от друга на dt, и к кодированию этих амплитуд цифровым кодом. Величина dt определяется по теореме Котельникова: для неискаженной передачи нужно иметь не менее двух отсчетов на период колебаний, соответствующий высшей составляющей в частотном спектре сигнала. В цифровых каналах ISDN (Integrated Services Digital Network) за основу принята передача голоса с частотным диапазоном до 4 кГц, а кодирование производится восемью (или семью) битами. Отсюда получаем, что частота отсчетов (передачи байтов) равна 8 кГц, т.е. биты передаются с частотой 64 кГц (или 56 кГц при семибитовой кодировке).

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

Разновидностями КИМ являются дельта-модуляция (ДМ), дифференциальная ДМ (ДДМ) и адаптивная ДМ (АДДМ). В них передаются разности амплитуд А1 и А2 соседних отсчетов. При этом в ДМ А1 - амплитуда на входе модулятора, а А2 - амплитуда отсчета, которая соответствует переданному сигналу в предыдущем временном такте.
^ Вопрос №2. Методы доступа и протоколы канального уровня локальных сетей
Методы доступа

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

^ Коллизия в сети рис 1

Наибольшее распространение при проектировании и построении ЛВС получили два метода доступа, это:

Множественный доступ с контролем несущей и обнаружением коллизии (CSMA/CD - Carrier-Sense Multiple Access and Collision Defection).

^ Доступ с передачей маркера.

Множественный доступ с контролем несущей и обнаружением коллизии

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

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

Если канал свободен, начинает передачу пакета.

При обнаружении коллизии во время передачи прекращает передачу.

Через случайный промежуток времени все повторяется (т.е. осуществляется переход к п. 1).

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

CSMA/CD - состязательный метод, при котором РС конкурируют за право передачи данных по каналу. Он кажется достаточно громоздким, но современные CSMA/CD настолько быстры, что пользователи даже не замечают, что применяется состязательный метод.

^ Доступ с передачей маркера

Суть маркерного доступа заключается в том, что пакет особого типа (маркер) перемещается по замкнутому кругу, минуя по очереди все РС, до тех пор, пока его не получит тот, который хочет передать данные Алгоритм взаимодействия рабочих станций ЛВС при использовании маркерного метода заключается в следующем:

Передающая рабочая станция изменяет состояние маркера на занятое и добавляет к нему пакет данных.

Занятый маркер с пакетом данных проходят через все РС сети, пока не достигнет адресата.

После этого, принимающая РС посылает передающей сообщение, где подтверждается факт приема.

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

Маркерный доступ (занятый маркер)рис.2а Маркерный доступ (свободный маркер)рис.2б

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

Рассмотренные выше методы доступа широко используются в современных сетевых технологиях. Они реализуются на аппаратном уровне в платах сетевых адаптеров того или иного сетевого стандарта. Первый из рассмотренных метод используется в сетевой технологии Ethernet, второй - в Token Ring и ArcNet.


^ Протоколы канального уровня локальных сетей

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

Протоколы канального уровня, обеспечивающие взаимодействие компьютера с сетью на самом низком, аппаратном уровне, во многом определяют топологию локальной сети, а также ее внутреннюю архитектуру. В настоящее время на практике достаточно часто применяется несколько различных стандартов построения локальных сетей, наиболее распространенными среди которых являются технологии Ethernet, Token Ring, Fiber Distributed Data Interface (FDDI) и ArcNet. На сегодняшний день локальные сети, построенные на основе стандарта Ethernet, являются наиболее популярными как в нашей стране, так и во всем мире. На долю сетей Ethernet приходится почти девяносто процентов всех малых и домашних локальных сетей, что не удивительно, поскольку именно эта технология позволяет строить простые и удобные в эксплуатации и настройке локальные сети с минимумом затрат. Именно поэтому в качестве основного рассматриваемого нами стандарта будет принята именно технология Ethernet. Протоколы канального уровня поддержки Ethernet,

как правило, встроены в оборудование, обеспечивающее подключение компьютера к локальной сети на физическом уровне. Стандарт Ethernet является широковещательным, то есть каждый подключенный к сети компьютер принимает всю следующую через его сетевой сегмент информацию — как предназначенную именно для этого компьютера, так и данные, направляемые на другую машину. Во всех сетях Ethernet применяется один и тот же алгоритм разделения среды передачи информации — множественный доступ с контролем несущей и обнаружением конфликтов (Carrier Sense Multiple Access with Collision Detection, CSMA/CD).В рамках технологии Ethernet сегодня различается несколько стандартов организации сетевых коммуникаций, определяющих пропускную способность канала связи и максимально допустимую длину одного сегмента сети, то есть расстояние между двумя подключенными к сети устройствами.
^ Вопрос№3. Способы контроля правильности передачи данных в компьютерных сетях;
Управление правильностью (помехозащищенностью) передачи информации выполняется с помощью помехоустойчивого кодирования. Различают коды, обнаруживающие ошибки, и корректирующие коды, которые дополнительно к обнаружению еще и исправляют ошибки. Помехозащищенность достигается с помощью введения избыточности. Устранение ошибок с помощью корректирующих кодов (такое управление называют Forward Error Control) реализуют в симплексных каналах связи. В дуплексных каналах достаточно применения кодов, обнаруживающих ошибки (Feedback or Backward Error Control), так как сигнализация об ошибке вызывает повторную передачу от источника. Это основные методы, используемые в информационных сетях.

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

^ Коды с обнаружением и исправлением ошибок.

Управление правильностью (помехозащищенностью) передачи информации выполняется с помощью помехоустойчивого кодирования. Различают коды, обнаруживающие ошибки, и корректирующие коды, которые дополнительно к обнаружению еще и исправляют ошибки. Помехозащищенность достигается с помощью введения избыточности. Устранение ошибок с помощью корректирующих кодов (такое управление называют Forward Error Control) реализуют в симплексных каналах связи. В дуплексных каналах достаточно применения кодов, обнаруживающих ошибки (Feedback or Backward Error Control), так как сигнализация об ошибке вызывает повторную передачу от источника. Это основные методы, используемые в информационных сетях.

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

^ Проверка на четность.

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

Для этого надо на приемной стороне (или при воспроизведении сигнала) сосчитать число единиц в кодовом слове. Если оно не является четным, то в канале произошла ошибка.

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

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

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

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

^ Код Хемминга

В коде Хемминга вводится понятие кодового расстояния d (расстояния между двумя кодами), равного числу разрядов с неодинаковыми значениями. Возможности исправления ошибок связаны с минимальным кодовым расстоянием dmin. Исправляются ошибки кратности r = ent (dmin-1)/2 и обнаруживаются ошибки кратности dmin-1 (здесь ent означает “целая часть”). Так, при контроле на нечетность dmin = 2 и обнаруживаются одиночные ошибки. В коде Хемминга dmin = 3. Дополнительно к информационным разрядам вводится L = log2K избыточных контролирующих разрядов, где K - число информационных разрядов, L округляется до ближайшего большего целого значения. L-разрядный контролирующий код есть инвертированный результат поразрядного сложения (т.е. сложения по модулю 2) номеров тех информационных разрядов, значения которых равны 1.

П р и м е р 1. Пусть имеем основной код 100110, т.е. К = 6. Следовательно, L = 3 и дополнительный код равен

010 # 011 # 110 = 111,

где # - символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь вместе с основным кодом будет передан и дополнительный. На приемном конце вновь рассчитывается дополнительный код и сравнивается с переданным. Фиксируется код сравнения (поразрядная операция отрицания равнозначности), и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100010, то рассчитанный в приемнике дополнительный код равен инверсии от 010 # 110 = 100, т.е. 011, что означает ошибку в 3-м разряде.

П р и м е р 2. Основной код 1100000, дополнительный код 110 (результат инверсии кода 110 # 111 = 001). Пусть принятый код 1101000, его дополнительный код 010, код сравнения 100, т.е. ошибка в четвертом разряде.

^ Циклические коды. К числу эффективных кодов, обнаруживающих одиночные, кратные ошибки и пачки ошибок, относятся циклические коды (CRC - Cyclic Redundance Code). Они высоконадежны и могут применяться при блочной синхронизации, при которой выделение, например, бита нечетности было бы затруднительно.

Один из вариантов циклического кодирования заключается в умножении исходного кода на образующий полином g(x), а декодирование - в делении на g(x). Если остаток от деления не равен нулю, то произошла ошибка. Сигнал об ошибке поступает на передатчик, что вызывает повторную передачу.

^ Образующий полином есть двоичное представление одного из простых множителей, на которые раскладывается число Xn-1, где Xn обозначает единицу в n-м разряде, n равно числу разрядов кодовой группы. Так, если n = 10 и Х = 2, то Xn-1 = 1023 = 11*93, и если g(X)=11 или в двоичном коде 1011, то примеры циклических кодов Ai*g(Х) чисел Ai в кодовой группе при этом образующем полиноме можно видеть в следующей табл.1.

Таблица 1


Число 

Циклический код 

Число 

Циклический код 

0 

0000000000.

13 

0010001111

1 

0000001011

14

0010011010

2 

0000010110

15 

0010100101 

3 

0000100001

16

0011000110

5

0000110111

18 

0011000110 

6 

0001000010

19 

0011010001 

.....

........

.......

.......
Основной вариант циклического кода, широко применяемый на практике, отличается от предыдущего тем, что операция деления на образующий полином заменяется следующим алгоритмом: 1) к исходному кодируемому числу А справа приписывается К нулей, где К - число битов в образующем полиноме, уменьшенное на единицу; 2) над полученным числом А*(2К) выполняется операция О, отличающаяся от деления тем, что на каждом шаге операции вместо вычитания выполняется поразрядная операция "исключающее ИЛИ": 3) полученный остаток В и есть CRC - избыточный К-разрядный код, который заменяет в закодированном числе С приписанные справа К нулей, т.е.

С= А*(2К)+В.

На приемном конце над кодом С выполняется операция О. Если остаток не равен нулю, то при передаче произошла ошибка и нужна повторная передача кода А.

Пример. Пусть А = 1001 1101, образующий полином 11001. Так как К = 4, то А*(2K)=100111010000. Выполнение операции расчета циклического кода показано на рис. 3.

Рис. 3. Пример получения циклического кода

Положительными свойствами циклических кодов являются малая вероятность необнаружения ошибки и сравнительно небольшое число избыточных разрядов.

Общепринятое обозначение образующих полиномов дает следующий пример:

g(X) = X 16 + X 12 + X 5 + 1,

что эквивалентно коду 1 0001 0000 0010 0001. Этот полином используется в протоколе V.42 для кодирования кодовых групп в 240 разрядов с двумя избыточными байтами. В этом протоколе возможен и образующий полином для четырех избыточных байтов

g(X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5 + X 4 + X 2 + 1.
^ Вопрос №4Алгоритмы сжатия данных в компьютерных сетях
Арифметические методы Принципы арифметического кодирования были разработаны в конце 70-х годов В результате арифметического кодирования строка символов заменяется .[действительным числом больше нуля и меньше единицы. Арифметическое кодирование позволяет обеспечить высокую степень сжатия, особенно в случаях, когда сжимаются данные, где частота появления различных символов сильно варьируется. Однако сама процедура арифметического кодирования требует мощных вычислительных ресурсов, и до недавнего времени этот метод мало применялся при сжатии передаваемых данных из-за медленной работы алгоритма. Лишь появление мощных процессоров, особенно с RISC-архитектурой, позволило создать эффективные устройства арифметического сжатия данных.

Метод словарей. Алгоритм, положенный в основу метода словарей, был впервые описан в работах израильских исследователей Якова Зива и Абрахама Лемпеля, которые впервые опубликовали его в 1977 г. В последующем алгоритм был назван Lempel-Ziv, или сокращенно LZ.. В его основе лежит идея замены наиболее часто встречающихся последовательностей символов (строк) в передаваемом потоке ссылками на "образцы", хранящиеся в специально создаваемой таблице (словаре).

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

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

Выбирается первый символ сообщения и заменяется на его код.

Выбираются следующие два символа и заменяются своими кодами. Одновременно этой комбинации двух символов присваивается свой код. Обычно это номер, равный числу уже использованных кодов. Так, если алфавит включает 8 символов, имеющих коды от 000 до 111, то первая двух символьная комбинация получит код 1000, следующая - код 1001 и т.д.

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

Процесс продолжается до исчерпания исходного текста.

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

Сколько двоичных разрядов нужно выделять для кодирования? Ответ может быть следующим: число разрядов R на каждом шаге кодирования равно числу разрядов в наиболее длинном из использованных кодов (т.е. числу разрядов в последнем использованном порядковом номере). Поэтому если последний использованный код (порядковый номер) равен 13=1101, то коды А всех комбинаций должны быть четырехразрядными при кодировании вплоть до появления номера 16, после чего все коды символов начинают рассматриваться как пятиразрядные (R=5).

Таблица 1


Исходный текст

0.00.000. 01. 11. 111.1111. 110. 0000.00000. 1101. 1110.

LZ-код

0.00.100.001.0011.1011.1101. 1010.00110.10010.10001.10110.

R 

2 3 4

Вводимые коды

- 10 11 100 101 110 111 1000 1001 1010 1011 1100
Пример. Пусть исходный текст представляет собой двоичный код (первая строка таблицы 1), т.е. символами алфавита являются 0 и 1. Коды этих символов соответственно также 0 и 1. Образующийся по методу Лемпеля-Зива код (LZ-код) показан во второй строке таблицы 1. В третьей строке отмечены шаги кодирования, после которых происходит переход на представление кодов А увеличенным числом разрядов R. Так, на первом шаге вводится код 10 для комбинации 00 и поэтому на следующих двух шагах R=2, после третьего шага R=3, после седьмого шага R=4, т.е. в общем случае R=K после шага 2K-1-1.

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

Алгоритм LZW

Непосредственным предшественником алгоритма LZW явился алгоритм LZ78, опубликованный в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel-Ziv-Welch).

^ Как работает LZW

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

Коды, которые алгоритм LZW помещает в выходной поток, могут быть произвольной длины, но должны содержать больше бит, чем одиночный символ. Первые 256 кодов по умолчанию представляют собой стандартную таблицу символов. Оставшиеся коды соответствуют строкам, которые обрабатывает алгоритм. Простые реализации алгоритма работают с кодами 12-битной длины. Это означает, что коды 0-255 соответствуют одиночным байтам, а коды 256-4095 соответствуют подстрокам.

Достоинства и недостатки

LZW сжатие отлично работает с файлами, содержащими