Практическая работа Определение оптимальной связывающей сети
Работа добавлена на сайт bukvasha.net: 2015-10-29Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Содержание
Введение. 4
1 Теоретическая часть. 6
1.1 Территориальная сеть связи. 6
1.1.1 Разновидности каналов связи. 6
1.1.2 Виды передачи данных. 8
1.2 Оценка качества функционирования систем связи. 10
1.2.1 Пропускная способность канала связи. 11
1.2.2 Причины потерь информации в системе связи. 13
1.2.3 Типы кабелей, применяемых в компьютерных сетях. 16
1.3 Этапы повышения помехоустойчивости данных. 18
1.3.1 Кодирование передаваемых данных. 19
1.3.2 Методы обнаружения искажений информации. 25
1.3.3 Дополнительные возможности повышения помехоустойчивости. 27
2 Практическая работа. 28
2.1 Определение оптимальной связывающей сети, согласно расстоянию и объему передаваемой / получаемой информации между звеньями сети. 28
2.2 Определение оптимальной связывающей сети при оптимизации по критерию быстроты прохождения информационного пакета. 33
2.3 Определение оптимальной связывающей сети при условии минимизации потерь информации по каналу связи. 34
2.4 Расчет энтропии и количества информации в сообщении. 39
2.5 Кодирование сообщения в вид, соответствующий 9-ричной системе счисления 41
2.6 Итоговый выбор оптимального маршрута. 44
Заключение. 47
Список использованных источников. 49
Введение
Обеспечение высокой помехоустойчивости устройств, построенных с использованием ЭВМ – одна из основных проблем, решаемых разработчиками средств вычислительной техники и систем управления. Повышение степени интеграции электронных средств и снижение энергетической мощности полезных сигналов с другой стороны, приводит к тому, что выделение полезных сигналов на фоне действующих помех становится сложной схемотехнической и программно-алгоритмической задачей. Особую сложность эта задача приобретает для систем, работающих в условиях воздействия помех, аналитический и статистический учет которых по различным причинам затруднен. Существенное влияние оказывает также факт физической удаленности ЭВМ от управляемого объекта.
Совершенствование средств управления энергоемкими установками происходит в направлении перехода от релейно-контактной элементной базы к электронной, что приводит к необходимости разработки специальных мер защиты элементов интегральной электроники от электромагнитных помех, поскольку энергия помехи, не приводящая к срабатыванию ранее применявшихся электромагнитных реле, превышает порог срабатывания современных больших и сверхбольших интегральных схем во много раз.
Одновременно следует отметить, что возникающие от грозовых разрядов, аварийных и коммутационных процессов в мощной системе электроснабжения или в мощной тяговой сети импульсные помехи могут вызвать не только ложное срабатывание аппаратуры, но и ее полное или частичное разрушение.
Таким образом, проблема обеспечения надежности и устойчивости работы управляющих систем со встроенными ЭВМ в условиях весьма многочисленных, разнообразных по физической природе, частотным характеристикам и энергетическому спектру помех, является актуальной и своевременной задачей, требующей для своего решения особых, нетрадиционных подходов.
Задачи данной курсовой работы заключаются:
– в анализе мешающих влияний в каналах связи при передаче и преобразовании информации;
– в теоретическом исследовании основ теории программной и аппаратной помехоустойчивости;
– в изучении методов составления рациональных маршрутов на примере организации передачи пакетных файлов между запланированными узлами.
1. Теоретическая часть
1.1 Территориальная сеть связи
Территориальная сеть связи (ТКС) – это географически распределенная сеть передачи данных (СПД), обеспечивающая оперативный и надежный обмен информацией между абонентами сети. Общепринятое название обменной информации – сообщение. Главные показатели эффективности ТКС – верность и время доставки информации. Они зависят от пропускной способности каналов связи, числа и способов соединения каналов связи между абонентами, протоколов информационного обмена, и ряда других факторов.
В ТКС используются телефонные, телеграфные, телевизионные, спутниковые сети связи. В качестве линий связи применяются кабельные линии связи (от простейших телефонных до специальных коаксиальных и волоконно-оптических), радиорелейные линии связи, и радиолинии. Среди кабельных линий связи наилучшие показатели имеют световоды. Они имеют высокую пропускную способность передачи данных (сотни мегабит в секунду), и нечувствительны к внешним электромагнитным полям при отсутствии собственных электромагнитных излучений.
1.1.1 Разновидности каналов связи
Линия связи состоит из физической среды, по которой передаются информационные сигналы, и аппаратуры передачи данных. Синоним термина – канал связи. Основной тип сигналов – электрические и электромагнитные.
В зависимости от среды передачи данных линии связи разделяются на проводные (воздушные), кабельные (в том числе волоконно-оптические) и радиоканалы наземной и спутниковой связи.
Проводные линии связи представляют собой открытые провода без изоляции и экранов. Они имеют низкую помехозащищенность и используются, в основном, для передачи телефонных и телеграфных сигналов.
Кабели представляют собой несколько проводников, заключенных в экранирующую и изолирующую оплетки. В компьютерных сетях применяются три типа кабелей: кабели на основе скрученных пар медных проводов, коаксиальные и волоконно-оптические кабели.
Радиоканалы имеют передатчики и приемники радиоволн, и отличаются друг от друга частотным диапазоном, который определяет дальность радиосвязи. Для компьютерной связи используется диапазоны УКВ и СВЧ, но для организации каналов в этих диапазонах необходима прямая видимость между передатчиком и приемником, или ретрансляция.
Выделяют три основных разновидности каналов связи:
- симплексный, при связи приемника с передатчиком по одному каналу, с однонаправленной передачей информации (например, в телевизионной и радиовещательной сетях);
- полудуплексный, когда два узла связи соединены одним каналом, по которому информация передается попеременно то в одном направлении, то в противоположном (в информационно-справочных и запросно-ответных системах);
- дуплексный, позволяет передавать данные одновременно в двух направлениях за счет использования четырехпроводной линии связи (два провода для передачи, два других – для приема данных), или двух полос частот.
Для повышения достоверности передачи данных основной канал может снабжаться дополнительным (обратным) каналом небольшой пропускной способности (на 1-2 порядка меньше основного), который используется для передачи служебной информации. По этому каналу передаются, например, сигналы подтверждения приема блоков данных и запросы на повторную передачу блоков при обнаружении ошибок.
Различают также выделенные (некоммутируемые) и коммутируемые на время передачи информации каналы связи. При использовании выделенных каналов связи приемопередающая аппаратура узлов связи постоянно соединена между собой. Этим обеспечивается высокая степень готовности системы к передаче информации, более высокое качество связи. Для коммутируемых каналов связи, создаваемых только на время передачи фиксированного объема информации, характерна небольшая стоимость, однако при этом имеют место потери времени на установление связи между абонентами (блокировки по приоритету и очередности).
Системы телеобработки информации являются специализированными системами телекоммуникаций. Основная цель систем телеобработки данных (СТД) – обеспечить прием данных непосредственно с мест их получения и выдачу результатов обработки к местам использования. При этом нет необходимости в промежуточных носителях данных, повышается оперативность взаимодействия с ЭВМ, повышается скорость и эффективность работы системы, для которой производится обработка данных. Телеобработка позволяет использовать мощные ЭВМ с большими базами данных. С помощью линий связи к таким ЭВМ может подключаться значительное число пользователей, что обеспечивает высокий уровень загрузки и использования ЭВМ.
Значительная протяженность линий связи затрудняет возможность обмена отдельными сигналами между ЭВМ и оконечным оборудованием. Поэтому взаимодействие ЭВМ и оконечного оборудования организуется с помощью сообщений – блоков данных, передаваемых в виде единого целого. Сообщения имеют специальную структуру, обеспечивающую представление в них наряду с собственно данными служебной информации, необходимой для идентификации сообщения и защиты данных от искажений. Возможность взаимодействия абонентов с ЭВМ только посредством сообщений вносит определенную специфику в организацию программного обеспечения телеобработки.
1.1.2 Виды передачи данных
В сетях ТКС информация передается в аналоговой форме. Это единственно возможный способ передачи информации по каналам связи. При передаче цифровых данных выполняется цифро-аналоговое и аналого-цифровое преобразование (ЦАП и АЦП) модемами на выходных и входных узлах связи. Для безошибочной передачи цифровых данных работа принимающего модема должна быть синхронизирована с работой передающего. Для этого используются два вида передачи данных: асинхронная и синхронная.
Асинхронная передача реализуется по символьно-ориентированной схеме. Каждая передаваемая последовательность состоит из стартового бита, за которым следуют информационные символы, и завершается стоповым битом. Асинхронный режим передачи используется для низкоскоростных устройств и устройств, у которых отсутствует буфер.
Синхронная передача применяется для высокоскоростной передачи данных. При символьно-ориентированной синхронной передаче блоку передаваемых символов предшествует один или несколько синхронизирующих символов. При побитно-ориентированной синхронной передаче в передаваемый блок данных перед сообщением включается флаг - специальная битовая последовательность.
В зависимости от вида передачи данных используются соответственно синхронные и асинхронные модемы. Синхронная передача может проводиться только синхронными модемами, асинхронная может выполняться и с помощью синхронных модемов.
Применяется и гибридная схема передачи – изохронная. Каждый символ в ней сопровождается стартовым и стоповым битами, а работа передающего и приемного модемов синхронизируется с помощью интервалов между передаваемыми символами.
Пересылка данных в ТКС осуществляется последовательной передачей битов сообщения от источника к пункту назначения. Физически информационные биты передаются в виде модулированных или импульсно-кодовых электрических сигналов, которые зачастую называют цифровыми. Модулированные сигналы менее чувствительны к искажениям, обусловленным затуханием в передающей среде. Импульсно-кодовые сигналы могут иметь одно или конечный набор значений в пределах определенного тактового интервала.
1.2 Оценка качества функционирования систем связи
Формирование сигналов для передачи по линии связи осуществляется аппаратурой передачи данных (Data Circuit terminating Equipment). Примерами DCE являются модемы. Подготовка данных для передачи осуществляется оконечным оборудованием данных (Data Terminal Equipment). Для усиления сигнала, проходящего через линию, а также для организации совместного использования линий связи (мультиплексирования и коммутации) может использоваться дополнительное оборудование.
Хотя сами сигналы в линиях связи всегда являются аналоговыми (непрерывными или кусочно-непрерывными), в зависимости от способа передачи данных линии связи делятся на цифровые и аналоговые. В цифровых линиях данные представляются сигналами, имеющими конечное число состояний, информация заключена в значениях сигнала в определенные моменты времени, причем сигнал может принимать конечное число значений. В аналоговых линиях используются сигналы с непрерывным диапазоном своих значений.
При передаче данных в аналоговой форме сигналы имеют более узкий спектр, поэтому их используют в линиях связи с узкой полосой пропускания, например в телефонных сетях. Цифровые сигналы имеют высокую скорость передачи данных, но более широкий спектр.
Основные характеристики канала связи – пропускная способность и достоверность передачи данных. Пропускная способность канала (количество информации, передаваемое в единицу времени) оценивается числом бит данных, передаваемых по каналу за единицу времени (в бит/с). Достоверность передачи данных оценивается по интенсивности битовых ошибок (Bit Error Rate), определяемой вероятностью искажения передаваемого бита данных. Величина BER для каналов связи без дополнительной защиты от ошибок составляет 10-4-10-6. Основная причина искажений – воздействие помех на линию связи. Помехи, как правило, носят импульсный характер и имеют тенденцию к группированию – образованию пачек помех, искажающих сразу группу соседних бит в передаваемых данных.
1.2.1 Пропускная способность канала связи
Пропускная способность канала связи определяется полосой частот и помехоустойчивостью канала. Полоса частот, в которой амплитудно-частотная характеристика (АЧХ) линии связи имеет значение не ниже заданного (например, по уровню 0.5) называется полосой пропускания. Полоса частот DF = fв-fн, где fн и fв – нижняя и верхняя границы частот, определяет диапазон частот, эффективно передаваемых по линии. Полоса частот зависит от типа линии и ее протяженности. Проводные линии связи имеют полосу частот примерно 10 кГц, кабельные – 100 кГц, коаксиальные – 100 МГц, радиорелейные – 1000 МГц, волоконно-оптические – 100 ГГц. Коротковолновая радиосвязь для передачи данных использует диапазон частот от 3 до 30 МГц.
Помехоустойчивость линии зависит от мощности помех, создаваемых в линии внешней средой или возникающих в самой линии. Обычно для уменьшения помех проводники экранируют или скручивают. Наименее помехоустойчивыми являются радиолинии, хорошей помехоустойчивостью обладают кабельные линии, отличной – волоконно-оптические линии, не восприимчивые к электромагнитному излучению.
Пропускная способность канала зависит от ширины полосы частот линии связи и отношения мощностей сигнала и шума. Математически эта связь описывается формулами Шенона (1) и Найквиста (2). Максимальная пропускная способность канала, построенного на основе линии с полосой частот DF и отношением сигнал-шум Рс/Рш, составляет (бит в секунду):
| Сmax = DF log2(1+ Рс/Рш). | (1) |
Значение (1+Рс/Рш) определяет число уровней сигнала, которое может быть воспринято приемником. Так, если отношение Рс/Рш>3, то единичный сигнал может переносить четыре значения – 2 бита информации.
| С=F log2(M), | (2) |
где М – число различимых состояний сигнала.
Практическая пропускная способность канала зависит от способа физического кодирования информации. При этом стремятся выбрать способ кодирования таким, чтобы максимально использовать возможности линии. Возможность применения на линии того или иного способа кодирования определяется полосой пропускания и затуханием сигнала. Затухание – это отношение амплитуд входного и выходного сигналов на заданной частоте для определенной длины линии связи, выражается в децибелах и вычисляется по формуле:
| A=20log10(Aвых/Aвх). | (3) |
При передаче данных широко используются двоичные сигналы, принимающие значения 0 и 1. Минимальная длительность такта, с которой могут передавался сигналы по каналу с полосой частот DF, равна Tmin = 1/(2DF). Если вероятность искажения символов 0 и 1 из-за помех одинакова и равна p, то число двоичных символов, которые можно безошибочно передать по каналу в секунду:
| C = 2DF[1 + p log2 p + (1-p) log2(1-p)]. | (4) |
Это выражение определяет пропускную способность двоичного канала. Величина в квадратных скобках определяет долю двоичных символов, которые передаются по каналу с частотой 2DF без искажений. Если помехи отсутствуют, вероятность искажения символа р=0 и пропускная способность C=2DF. Если вероятность искажения р=0,5, то пропускная способность С=0. Если по каналу передается сообщение длиной n двоичных символов, то вероятность появления в нем m ошибок:
| P(n, m)= | (5) |
Телефонный канал имеет полосу пропускания 3,1 кГц (диапазон частот 0,3-3,4 кГц). Коммутируемый телефонный канал обеспечивает скорость передачи данных С=1200 бит/с, некоммутируемый – до 9600 бит/с (коммутируемая сеть – когда тракт передачи информации создается по запросу абонента на время передачи сообщения, некоммутируемая – когда тракт передачи информации обеспечивается постоянным соединением между определенными абонентами и нет необходимости в коммутации).
1.2.2 Причины потерь информации в системе связи
Основной задачей системы связи является обеспечение максимальной скорости передачи при высоком качестве функционирования и экономичности системы. Под качеством функционирования при этом понимается минимизация потерь информации, что в конечном итоге трансформируется в обеспечение высокой верности передачи.
Рассмотрим основные причины, приводящие к возможным потерям информации в системе связи. Они иллюстрируются схемой, представленной на рисунке
Рисунок 1 –
Основные причины потерь информации в системе связи
На вход системы связи поступает поток сообщений, который далее может быть либо принят для передачи, либо не принят в связи с занятостью запоминающих или входных устройств системы связи
. Поток сообщений, принятый для передачи, преобразуется в поток сигналов, предназначенных для передачи по каналу. Будим полагать используемые в системе связи каналы дискретными и в качестве сигналов рассматривать последовательности символов кода. При этом преобразовании также могут возникать определенные потери информации, вызванные ненадежностью в основном кодирующих устройств и каналообразующей аппаратуры.
Поток символов, поступивший из канала к приемнику может быть принят и не принят по причине неисправности аппаратуры или по причине ее занятости приемом других информационных потоков. Однако даже если поток был принят приемником, под действием помех в канале связи могут возникать такие ошибки, которые делают невозможным достоверное выявление информации. Последнее имеет место, если введенной в информацию избыточности оказалось недостаточно для исправления ошибок, возникших под действием помех в канале связи.
Таким образом, из потока сообщений,
поступающих на входы системы связи, формируется некоторый поток потерянных сообщений. Независимо от места возникновения потерь информации основными причинами потерь являются помехи в каналах связи, неисправность аппаратуры и перегрузка обслуживающих или запоминающих устройств.
Количественная оценка каждого из этих явлений может быть осуществлена с помощью теории вероятностей. Данное обстоятельство и позволяет сформировать единый информационный подход к оценке качества функционирования системы связи. Способность системы обеспечивать передачу информации с заданной верностью при воздействии помех в канале связи называют помехоустойчивостью.
Наличие неисправности в аппаратуре приводит к ее неработоспособности. Под надежностью любой информационной системы понимают свойство системы выполнять свои функции, сохраняя во времени значения установленных эксплуатационных показателей в заданных пределах. При оценке качества системы связи необходимо учитывать возможность возникновения сбоев и отказов. Под сбоем обычно понимается самоустраняющийся отказ, приводящий к кратковременному нарушению работоспособности. Под отказом понимают нарушение работоспособности аппаратуры.
Проблема надежности отличается от проблемы помехоустойчивости тем, что в случае отказа повторение одной и той же операции во времени не позволит обнаружить и исправить ошибку. Вместе с тем в системах с последовательными кодами одиночный отказ элемента может привести к неодиночной ошибке в выходном сигнале. Однако при соответствующем проектировании информационных систем основные методы обеспечения помехоустойчивой передачи информации могут быть применены к задаче конструирования надежных технических устройств. Также как и для повышения помехоустойчивости, для увеличения надежности необходимо вводить избыточность. В частности, с небольшими изменениями можно использовать большинство результатов теории кодирования при введении аппаратурной кодовой избыточности.
Проблема помехоустойчивости в определенной степени является противоречивой по отношению к проблеме надежности. Если для увеличения помехоустойчивости необходимо увеличивать избыточность передаваемой информации, то это приводит к усложнению системы и если вводимая избыточность не рассчитывалась на исправление ошибок, возникших из-за неисправности аппаратуры, то снижается надежность. Только оценивая помехоустойчивость и надежность единым критерием, можно оценить общую эффективность построения системы связи. Свойство системы в отношении помехоустойчивости и надежности можно связать с количеством информации, проходящим через систему.
Расчет вероятности потерь по причине отказа в обслуживании можно вести исходя из известных в теории массового обслуживания соотношений.
Снижение этих потерь также может быть осуществлено путем введения избыточности в обслуживании. Она позволяет уменьшать время обслуживания информационных потоков, что в ряде случаев очень важно в связи с тем, что в задачах, связанных с оперативным управлением, регулированием или контролем, существенную роль играет старение информации, поэтому задержки могут оказаться эквивалентными
потере информации.
Значительную сложность представляет выбор между избыточностью в информации и избыточностью в обслуживании. Информационная избыточность приводит к увеличению времени обслуживания каждого сообщения. Поэтому для компенсации потерь, связанных с отказом в обслуживании, вносится избыточность в обслуживании (увеличивают объем памяти буферных запоминающих устройств; число декодеров и другое). Это усложняет аппаратуру и снижает надежность.
Поэтому серьезной задачей является определение оптимальных соотношений по всем видам избыточности. Комплексный информационный подход к оценке потерь информации с учетом всех сторон функционирования технических средств позволяет добиться наивысшей эффективности работы
системы связи
.
1.2.3 Типы кабелей, применяемых в компьютерных сетях
В компьютерных сетях применяются кабели, соответствующие стандартам. Наиболее употребительным является международный стандарт ISO/IEC 11801.
В стандартах должны быть регламентированы следующие основные характеристики кабелей:
- затухание (в дБ/м);
- устойчивость кабеля к внутренним источникам помех;
- импеданс (волновое сопротивление);
- уровень внешнего электромагнитного излучения в проводнике.
Для оценки перекрестных наводок, возникающих при использовании пары проводов в кабеле для передачи и приема, используется показатель NEXT (Near End Cross Tolk), рассчитываемый по формуле 20log10(Aвых/Aвх), где Aвых и Авх – амплитуды выходного и наведенного входного сигналов.
Импеданс (волновое сопротивление) – эффективное входное сопротивление кабеля для переменного тока. При изменении напряжения реакция системы зависит не только от нагрузки на удаленном конце кабеля, а от эффективного сопротивления, которое определяется погонной емкостью и индуктивностью кабеля. Если нагрузка на кабеле не совпадает с его волновым сопротивлением (кабель рассогласован), то в кабеле возникают отражения сигнала от нагрузки (вплоть до возникновения стоячей волны при большом сопротивлении нагрузки), что приводит к невозможности передачи данных. Для обеспечения согласования необходимо, чтобы кабели в сети и концевые нагрузки имели одинаковое волновое сопротивление.
Уровень внешнего электромагнитного излучения в проводнике характеризует помехозащищенность кабеля, то есть степень ослабления внешних помех от различных источников (линий электропередачи, средств связи, оргтехники и бытовой техники, электромоторов).
Наиболее широкое применение находят следующие типы кабелей.
Неэкранированная витая пара UTP является наиболее употребительной в локальных сетях и подразделяется по категориям. Кабели категории 3 и 4 имеют рабочий диапазон до 16 и 20 МГц, предназначены для передачи данных со скоростью до 10 и 15 Мбит/с. Кабели категории 5 - наиболее распространенный вид, ориентированы на рабочий диапазон до 100 МГц. Кабели категорий 6 и 7 имеют рабочий диапазон 200 и 600 МГц и лучшие характеристики затухания и помехозащищенности, но используются редко из-за своей дороговизны. Волновое сопротивление кабелей витой пары составляет 100 Ом. Все кабели выпускаются в 4-парном исполнении.
Экранированная витая пара STP имеет лучшие характеристики по сравнению с неэкранированной. Основным стандартом, определяющим параметры кабелей данного типа, является стандарт фирмы IBM, в котором кабели разделены на девять типов.
Коаксиальные кабели широко используются не только в компьютерных сетях, но и для передачи ВЧ телевизионных сигналов.
Кабель RG-8 и RG-11 – «толстый» коаксиальный кабель, имеет волновое сопротивление 50 Ом и внешний диаметр
Кабели RG-58/U (сплошной тонкий проводник), RG-58 A/U (многожильный проводник) и RG-58 C/U, RG-59 – тонкие коаксиальные кабели с волновым сопротивлением 50 Ом.
Волоконно-оптические кабели (ВОК) состоят из центрального проводника света (волокна), окруженного другим проводником – оболочкой. Оболочка обладает меньшим показателем преломления, чем сердцевина, поэтому излучение не выходит за пределы волокна.
Различают одномодовое волокно (очень тонкого диаметра), с полосой пропускания сотни гигагерц, и многомодовое волокно, с более широким сердечником и меньшей полосой пропускания (500-800 МГц). В многомодовом волокне из-за относительно больших размеров электромагнитная волна высокой частоты может распространяться в нескольких режимах (модах), с разными скоростями, что приводит к искажениям передачи информации. Поэтому верхняя граничная частота такого волокна ограничена нижней частотой возникновения высших мод.
В качестве источников света в ВОК используют светодиоды и полупроводниковые лазеры. Для передачи информации используется свет с длиной волны 850-1300 нм.
1.3 Этапы повышения помехоустойчивости данных
Для передачи данных используются способы с максимальным использованием свойств каналов по скорости и достоверности передачи данных.
Данные первоначально предоставляются последовательностью прямоугольных импульсов. Для их передачи без искажения требуется полоса частот от нуля до бесконечности. Реальные каналы имеют конечную полосу частот, с которой необходимо согласовать передаваемые сигналы. Согласование обеспечивается, во-первых, путем модуляции – переноса сигнала на заданную полосу частот и, во-вторых, путем кодирования – преобразовании данных в вид, позволяющий обнаруживать и исправлять ошибки, возникающие из-за помех в канале связи.
1.3.1 Кодирование передаваемых данных
Искажение информации может происходить по различным причинам от помех или шумов, которые могут быть вызваны различными обстоятельствами, такими, как неисправность ЭВМ, отклонение от стандартов напряжения сети или влажности помещения, внешние помехи и другое.
Поэтому одной из важнейших проблем теорий кодирования является проблема обнаружения и исправления ошибок, возникающих при передаче информации. Различают три вида ошибок, возникающих по различным причинам:
1) погрешности в данных;
2) методические погрешности;
3) неисправности в работе ЭВМ.
Ошибки первого и второго вида система контроля не сможет исправить самостоятельно, их надо учесть заранее.
В задачи помехоустойчивого кодирования входит обнаружение и исправление ошибок третьего вида. Эта цель достигается введением избыточной информации. Избыточность информации можно получить аппаратными (схемными), логическими и информационными средствами. Существует несколько десятков разнообразных методов распознавания и коррекции ошибок кодирования, предназначенных для каналов связи с различными характеристиками помех.
Сформулируем три глобальные проблемы кодирования:
1) создание шифра кодирования;
2) создание специальных корректирующих кодов для поиска и исправления ошибок, возникающих в результате передачи и хранения информации;
3) минимизация избыточной информации для успешной коррекции и сокращения потерь в скорости передачи сообщения.
Один из самых эффективных путей кодирования основан на применении основной теоремы Шеннона для каналов без шума. Согласно первой теореме Шеннона, если канал передачи не содержит собственных помех, то, возможно, так закодировать сообщение, чтобы среднее число элементов кода (двоичных символов), приходящихся на один элемент кодируемого алфавита, было минимальным. Это так называемое эффективное статистическое кодирование.
Первая теорема Шеннона утверждает, что вероятность ошибок при передаче информации сколь угодно мала, если энтропия S множества передаваемых сообщений меньше пропускной способности канала связи С, определяемой как наибольшее число бит, которые возможно передавать по этому каналу связи за единицу времени.
Для каналов связи с помехами справедлива вторая теорема Шеннона (прямая теорема кодирования), согласно которой всегда существует способ кодирования, такой, что информация может быть передана с какой угодно высокой достоверностью при большой длине передаваемых слов, если скорость передачи не выше пропускной способности канала связи. Вторая теорема Шеннона доказывает принципиальную возможность помехоустойчивого кодирования.
Первый классификационный признак – коды бывают блочными или непрерывными. При блочном кодировании передаваемые двоичные сообщения сгруппированы в блоки, которыми кодируются знаки (или группы знаков) первичного алфавита. В блоке присутствуют информационные и проверочные биты. Если все кодовые комбинации имеют одинаковую длину, код называется равномерным; если нет – неравномерным. При декодировании удобнее (проще) иметь дело с равномерным кодом, поэтому именно он, как правило, используется в помехоустойчивом кодировании. Непрерывные (синонимы: цепные, сверточные, рекуррентные) коды представляют собой непрерывную последовательность бит, не разделяемую на блоки (информационные и проверочные биты в них чередуются по определенному правилу). Блочное кодирование удобно использовать в тех случаях, когда исходные данные по своей природе уже сгруппированы в какие-либо блоки или массивы. При передаче по радиоканалам чаще используется сверточное кодирование, которое лучше приспособлено к побитовой передаче данных. Кроме этого, при одинаковой избыточности сверточные коды, как правило, обладают лучшей исправляющей способностью.
Рисунок 2 – Классификация помехоустойчивых кодов
Второй классификационные признак, относящийся как к блочным, так и к непрерывным кодам, подразделяет коды на разделимые и неразделимые. Разделимыми называются коды, в которых информационные и проверочные биты располагаются в строго определенных позициях. В неразделимых кодах такой определенности нет, что затрудняет их кодирование и декодирование. Поэтому практический интерес представляют в основном разделимые коды, а из неразделимых – только коды с постоянным весом.
Третий классификационный признак относится только к блочным разделимым кодам – они подразделяются на систематические (линейные) и несистематические. Двоичный код является линейным, если сумма по модулю 2 (mod2) двух кодовых слов также является кодовым словом этого кода. В линейных кодах проверочные биты являются результатом линейных операций над информационными разрядами. В несистематических (нелинейных) кодах информационные и проверочные биты либо вообще не имеют связи, либо эта связь нелинейна – такие коды применяются крайне редко.
Наиболее часто в линиях связи используются блочные линейные коды, называемые (n, k)-коды, к которым относятся циклические, коды Хемминга, матричные канонические и ряд других.
При цифровом кодировании дискретной информации применяют потенциальные и импульсные коды. В потенциальных кодах для представления логических единиц и нулей используется только значение потенциала сигнала. Импульсные коды позволяют представить двоичные данные либо импульсами определенной полярности, либо перепадом потенциала определенного направления.
При выборе метода цифрового кодирования к нему предъявляют следующие требования:
- наименьшая ширина спектра результирующего сигнала (узкий спектр сигналов позволяет добиваться высокой скорости передачи данных);
- возможность синхронизации между передатчиком и приемником (как правило, в сетях применяются самосинхронизирующиеся коды, сигналы которых позволяют передатчику автоматически определять тактовую частоту передачи информационных битов, например, по резким перепадам сигналов);
- возможность распознавания ошибок (распознавание и коррекция ошибок реализуется средствами логического кодирования, или используется избыточность физических кодов).
В самосинхронизирующихся кодах каждый переход уровня сигнала от высокого к низкому уровню или наоборот используется для подстройки приемника. Лучшими считаются коды, которые обеспечивают переход уровня сигнала не менее одного раза в течение интервала времени на приеме одного информационного бита.
Потенциальный код без возвращения к нулю (NRZ - Non Return to Zero) – 0 и 1 кодируются различными уровнями сигнала. Это наиболее простой способ кодирования, но имеет постоянную составляющую в спектре. При передаче длинных серий одноименных битов (единиц или нулей) уровень сигнала остается неизменным для каждой серии, что снижает качество синхронизации и надежность распознавания принимаемых битов.
Рисунок 3 – Иллюстрация самосинхронизирующихся кодов
Потенциальный код с возвращением к нулю (Return to Zero) – код, аналогичный NRZ, с возвращением к нулю на середине каждого тактового интервала. Имеет большее число переходов уровня сигнала, чем сигнал в коде NRZ.
Биполярное кодирование с альтернативной инверсией (AMI) – 0 кодируется нулевым потенциалом, а 1 – положительным или отрицательным ненулевым, причем потенциал каждой следующей единицы противоположен по знаку предыдущей. Спектр кода не содержит постоянной составляющей. Используется три уровня сигналов, что требует увеличения мощности передатчика. Обладает хорошими синхронизирующими свойствами при передаче серий единиц и прост в реализации. Недостатком кода является ограничение на плотность нулей в потоке данных, поскольку длинные последовательности нулей ведут к потере синхронизации.
Манчестерский код (Phase Encode, фазовое кодирование) – наиболее популярный код, применяемый в локальных сетях. При манчестерском кодировании информация передается перепадами потенциала, происходящими в середине такта. Единица кодируется перепадом от низкого уровня к высокому, а ноль наоборот. В начале каждого такта может происходить, а может и не происходить служебный перепад (он происходит, если в предыдущем такте передаваемый бит имел то же значение, что и в текущем.). Манчестерский код обеспечивает изменение уровня сигнала при представлении каждого бита и не имеет постоянной составляющей.
Логическое кодирование – это предварительное изменение передаваемой информации с целью сделать ее более удобной для передачи. Например, путем логического кодирования избавляются от длинных последовательностей нулей и единиц.
Избыточное кодирование – вариант логического кодирования, при котором к основной информации добавляется дополнительная. При этом передаваемая последовательность бит разбивается на порции, называемые символами, и каждый символ заменяется на новый, имеющий большее количество бит, чем исходный. Например, логический код 4В/5В заменяет исходные символы длиной 4 бита на символы длиной 5 бит. При этом возникает 16 «запрещенных» символов, прием которых свидетельствует об ошибке связи и появляется возможность исправления ошибок передачи.
Применение самосинхронизирующихся кодов обеспечивает побитовую синхронизацию, но для обнаружения начала и окончания потока бит и его разделения на байты (побайтовая синхронизация) необходимы специальные методы.
В асинхронных протоколах для низкоскоростного взаимодействия с периферийными устройствами каждый байт (или группа бит фиксированной длины) предваряются специальным набором старт-бит и завершаются стоп-битами.
В синхронных протоколах данные передаются большими блоками произвольной длины (кадрами). Кадр предваряется преамбулой – фиксированной последовательностью бит. После преамбулы начало и конец кадра обозначаются стартовыми и стоповыми ограничителями (флагами). Для того чтобы при возникновении внутри поля данных последовательности бит, совпадающей со стоповым ограничителем, не нарушался порядок приема кадра, существуют специальные методы, например, передача в заголовке кадра (имеющего фиксированную длину) сведений о длине поля данных.
1.3.2 Методы обнаружения искажений информации
Для повышения помехоустойчивости каналов передачи информации разработаны специальные методы, сокращающие влияние шумов. Несмотря на то, что каналы связи весьма разнообразны, а помехи специфичны, существуют общие способы борьбы с ними.
Необходимо максимально снизить уровень помех и максимально повысить уровень полезного сигнала, то есть увеличить отношение сигнал/шум. Увеличение отношения сигнал/шум может достигаться за счет представления информации в виде импульсов, четко выделяемых на фоне помех.
Борьба с помехами уменьшает, но не исключает вероятность появления ошибок. Что бы их учесть или ликвидировать вводятся различные способы кодирования, которые учитывают вероятность ошибок и при их обнаружении, либо их устраняют, либо выдают соответствующее сообщение. К таковым кодам относятся корректирующие коды, систематические коды и контроль по четности.
Корректирующие коды – класс кодов, обладающих свойством обнаруживать с заданной точностью и исправлять возникающие ошибки с целью повышения помехоустойчивости информационных систем при передаче, хранении и обработке дискретной информации.
Для организации работы корректирующих кодов используется введение принципа избыточности информации, за счет чего основная информация приобретает помехоустойчивые свойства. Но для расположения такой избыточной информации необходимо ввести дополнительные разряды, которые заполняются соответствующим кодом.
Систематические коды. Такие коды состоят из двух частей, первая часть содержит k – контролирующих разрядов, вторая часть содержит m – информационных разрядов. Причем m+k=n – число разрядов в информационном слове. Корректирующая способность такого кода численно равна вероятности обнаружения и исправления ошибки.
При передаче двоичных сообщений ошибка может заключаться только в замене 0 на 1 или 1 на 0. Складывая (по модулю 2) соответствующие разряды оригинала и полученного сообщения поразрядно, можно установить ошибки. Если получили 0, то ошибок нет, если получили 1, то ошибка есть. Причем видно, что те разряды, которые в сумме дают 1, то ошибка именно в этом разряде. Передав повторно полученное ошибочное сообщение, согласно двойной инверсии получим верное сообщение.
Остается установить, каким образом перееденное сообщение сравнивается с оригиналом, который остался в первоначальном месте. На этот счет есть первая часть сообщения, которая имеет информации о передуваемом слове, например, наличие в нем единиц – вес сообщения. Если вес сообщения не совпадает с весом полученного слова, то произошла ошибка.
Несмотря на простоту в использовании двоичных кодов, они обладают серьезным недостатком за счет значительной разницы в наборах цифр между двумя соседними значениями. Для уменьшения вероятности ошибки в двоичных кодах используют код Грея, в котором каждые две позиции отличаются только одним разрядом, то есть на 1 бит. Поэтому выходной сигнал может быть представлен лишь одним из двух состояний – истинным или ложным.
Для обнаружения однократной ошибки и ее исправления применяется контроль по четности, который заключается в том, что сумма двоичных единиц в машинном слове, включая контрольный разряд, должна иметь определенную четность, то есть быть либо всегда четной, либо всегда нечетной.
Рассмотренные коды дают информации об одной ошибке. Но ошибок может быть несколько. Причем исправление одной из них, может привести к появлению дополнительных ошибок. Существуют на этот счет другие возможности, которые основаны на иных принципах работы. Например, в методе циклического избыточного контроля (CRC) в качестве контрольной информации используется остаток от деления двоичного числа, которое представляют собой исходные данные, на известный делитель. Как правило, делитель выбирается таким, чтобы остаток составлял 2 или 4 байта. При приеме остаток прибавляется к принятым данным и полученное число делится на тот же делитель. Равенство итогового остатка нулю свидетельствует о правильности приема.
Восстановление потерянных кадров проводится путем их повторной передачи. При передаче с установлением логического соединения каждый блок данных нумеруется и для подтверждения его получения приемник посылает передатчику специальный блок данных – положительную или отрицательную квитанцию. Если передатчик не получил квитанции или получил отрицательную квитанцию, он проводит повторную передачу.
1.3.3 Дополнительные возможности повышения помехоустойчивости
Для повышения качества функционирования технических средств можно использовать многократное повторение однотипных блоков, сигналов, для получения требуемой помехоустойчивости или надежности. Такую избыточность называют избыточностью повторения.
Еще одной возможностью повышения помехоустойчивости является использование статистики сообщений. Например, если при передаче текста отдельные буквы в словах приняты неверно, то ошибки в отдельных буквах не означают невозможности правильно прочесть слово, в котором произошла ошибка. Ошибка в одной букве может образовать такое сочетание букв, которое вообще не является словом данного языка. Поэтому обычно заменяют принятую невозможную комбинацию букв ближайшей возможной. На этом принципе восстановления основаны некоторые современные помехоустойчивые системы.
2 Практическая работа
2.1 Определение оптимальной связывающей сети, согласно расстоянию и объему передаваемой / получаемой информации между звеньями сети
На рисунке 4 представлена схема размещения пунктов А-М и дано расстояние между ними.
Объём информации для передачи из пункта А в каждый пункт и получаемых из них, дано в таблице 1. Технический объём передаваемого пакета сообщений не должен превышать 2,5 Гб информации. Необходимо организовать передачу информационных сообщений между всеми пунктами согласно расстоянию и объему передаваемой / получаемой информации между ними.
Рисунок 4 – Схема размещения пунктов А-М
Таблица 1 – Объём информации для передачи из пункта А в каждый пункт и получаемых из них
| Пункты | Б | В | Г | Д | Е | Ж | З | И | К |
| Получение | 375 | 405 | 275 | 585 | 510 | 560 | 435 | 390 | 465 |
| Возврат | 100 | 235 | 375 | 140 | 280 | 400 | - | 70 | 245 |
Представив кратчайшую связывающую сеть, группируем пункты с учетом передаваемого / получаемого объёма информации, и максимального объёма информационного пакета:
Таблица 2 – Сгруппированные пункты по маршрутам
| Маршрут 1 | Маршрут 2 | ||||
| Пункт | Объём передаваемой / получаемой информации | Пункт | Объём передаваемой / получаемой информации | ||
| Б | 375 | 100 | Г | 275 | 375 |
| В | 405 | 235 | Д | 585 | 140 |
| З | 435 | | Ж | 560 | 400 |
| К | 465 | 245 | И | 390 | 70 |
| Е | 510 | 280 | | | |
| Итого: | 2190 | 860 | Итого: | 1810 | 985 |
Этот этап расчетов имеет целью связать все пункты каждого маршрута, начиная с пункта А, замкнутой линией, которой соответствует кратчайший путь объезда этих пунктов. С этой целью проводятся специальные расчеты, один из методов которых, называемый «методом треугольников», приводится ниже.
Таблица 3 – Симметричная матрица маршрута 1
| | A | 7,0 | 11,3 | 15,7 | 14,3 | 8,5 |
| | 7,0 | Б | 4,3 | 8,7 | 7,3 | 1,5 |
| | 11,3 | 4,3 | В | 4,7 | 11,0 | 5,2 |
| | 15,7 | 8,7 | 4,7 | З | 6,3 | 7,2 |
| | 14,3 | 7,3 | 11,0 | 6,3 | К | 5,8 |
| | 8,5 | 1,5 | 5,2 | 7,2 | 5,8 | Е |
| ∑ | 56,8 | 28,8 | 36,5 | 42,6 | 44,7 | 28,2 |
Для каждого маршрута строим таблицу, называемую симметричной матрицей. Для маршрута 1 она приведена в таблице 3. По главной диагонали в ней размещены пункты, включаемые в маршрут. Цифры в клетках показывают кратчайшие расстояния между ними.
Начальный маршрут строим для трех пунктов матрицы А, З, К, имеющих наибольшие значения величины, показанной в итоговой строке.
Для включения последующих пунктов в маршрут выбираем из оставшихся пунктов в таблице пункт, имеющий наибольшую сумму, например, В. Затем необходимо определить между какими пунктами начального маршрута его следует вставить. Для этого следует поочередно вставлять пункт В между каждой соседней парой пунктов АЗ, ЗК, КА.
При этом для каждой пары пунктов необходимо найти величину приращения маршрута (∆) по формуле:
| ∆kp = Cki + Cip – Ckp , | (6) |
где С – расстояние;
i – индекс включаемого пункта;
k – индекс первого пункта из пары;
p – индекс второго пункта из пары.
При включении пункта В между первой парой пунктов АЗ определяем размер приращения ∆АЗ: ∆АЗ = САВ + СВЗ – САЗ= 11,3 + 4,7 – 15,7 = 0,3
Для пунктов ЗК приращение маршрута при включении пункта В равно:
∆ЗК = СЗВ + СВК – СЗК = 4,7 + 11,0 – 6,3 = 9,4
Для пунктов КА соответственно: ∆КА = СКВ + СВА – СК = 11 + 11,3 – 14,3 = 8
Из полученных значений выбираем минимальное значение ∆АЗ = 0,3 и между соответствующими пунктами вставляем пункт В. Получаем маршрут АВЗКА.
Выбираем в таблице 4 еще не включенный в маршрут пункт Б.
∆АВ = САБ + СБВ – САВ = 7,0 +4,3 – 11,3 = 0
∆ВЗ = СВБ + СБЗ – СВЗ = 4,3 + 8,7 – 4,7 = 8,3
∆ЗК = СЗБ + СБК – СЗК = 8,7 + 7,3 – 6,3 = 9,7
∆КА = СКБ + СБА – СКА = 7,3 + 7,0 – 14,3 = 0
Так как наименьшей величиной является ∆АВ (∆КА логически не подходит), пункт Б включаем между АВ и получаем маршрут АБВЗКА.
Выбираем в таблице 3 еще не включенный в маршрут пункт Е.
∆АБ = САЕ + СЕБ – САБ = 8,5 + 1,5 – 7,0 = 3,0
∆БВ = СБЕ + СЕВ – СБВ = 1,5 + 5,2 – 4,3 = 2,4
∆ВЗ = СВЕ + СЕЗ – СВЗ = 5,2 + 7,2 – 4,7 = 7,7
∆ЗК = СЗЕ + СЕК – СЗК = 7,2 + 5,8 – 6,3 = 6,7
∆КА = СКЕ + СЕА – СКА = 5,8 + 8,5 – 14,3 = 0
Так как наименьшей величиной является ∆КА, пункт Е включаем между КА и получаем окончательный порядок объезда пунктов первого маршрута АБВЗКЕА.
Можно утверждать, что полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов маршрута 1.
По маршруту 2 проводим аналогичные расчеты, исходные данные для которых представлены в таблице 4.
Таблица 4 – Симметричная матрица маршрута 2
| | A | 4,7 | 8,6 | 6,1 | 9,8 |
| | 4,7 | Г | 3,9 | 8,9 | 7,9 |
| | 8,6 | 3,9 | Д | 5,0 | 4,0 |
| | 6,1 | 8,9 | 5,0 | Ж | 3,7 |
| | 9,8 | 7,9 | 4,0 | 3,7 | И |
| ∑ | 29,2 | 25,4 | 21,5 | 23,7 | 25,4 |
Начальный маршрут строим для трех пунктов матрицы А, Г, И, имеющих наибольшие значения величины, показанной в итоговой строке.
∆АГ = САД + СДГ – САГ = 8,6 + 3,9 – 4,7 = 7,8
∆ГИ = СГД + СДИ – СГИ = 3,9 + 4,0 – 7,9 = 0
∆ИА = СИД + СДА – СИА = 4,0 + 8,6 – 9,8 = 2,8
Подставив первоначально пункт Д, получаем маршрут АГДИА.
∆АГ = САЖ + СЖГ – САГ = 6,1 + 8,9 – 4,7 = 10,3
∆ГД = СГЖ + СЖД – СГД = 8,9 + 5,0 – 3,9 = 10,0
∆ДИ = СДЖ + СЖИ – СДИ = 5,0 + 3,7 – 4,0 = 4,7
∆ИА = СИЖ + СЖА – СИА = 3,7 + 6,1 – 9,8 = 0
Окончательный порядок объезда пунктов второго маршрута АГДИЖА.
Проанализировав порядок приема / передачи информации в каждом отдельном пункте при последовательном объезде пунктов маршрута (таблица 5), делаем вывод, что данный подход к маршрутам 1 и 2 не нарушает требование к поставленной задачи.
Таблица 5 – Порядок приема / передачи информации при последовательном объезде пунктов маршрута 1
| Пункт | Объём передаваемой / получаемой информации | Пункт | Объём передаваемой / получаемой информации | ||||
| | пришло | передано | получено | | пришло | передано | получено |
| Б | 2190 | 375 | 100 | Г | 1810 | 275 | 375 |
| В | 1915 | 405 | 235 | Д | 1910 | 585 | 140 |
| З | 1745 | 435 | | И | 1465 | 390 | 70 |
| К | 1310 | 465 | 245 | Ж | 1145 | 560 | 400 |
| Е | 1090 | 510 | 280 | А | 985 | | |
| Б | 860 | | | | | | |
| A | 860 | | | | | | |
На рисунке 5 представлена оптимальная связывающая сеть, согласно расстоянию и объему передаваемой / получаемой информации между звеньями сети.
Рисунок 5 – Схема движения по маршрутам 1 и 2.
2.2 Определение оптимальной связывающей сети при оптимизации по критерию быстроты прохождения информационного пакета
На рисунке 6 для всех линий связи указаны пропускные способности в
| | (7) |
где
с – пропускная способность линии связи,
Соответственно для линии связи между пунктами А и Б время передачи информации в 1 Гб:
На рисунке 7 для всех линий связи указано реальное время передачи в с, выделена оптимальная связывающая сеть, при условии оптимизации по критерию быстроты прохождения информационного пакета по каналу связи.
Рисунок 6 – Заданные пропускные способности всех линий
Рисунок 7 – Оптимальная связывающая сеть, при оптимизации по критерию быстроты прохождения информационного пакета по каналу связи
2.3 Определение оптимальной сети при условии минимизации потерь информации по каналу связи
Потери от объёма информации определяются искажениями при передаче условного сообщения (таблица 6), в котором 1 символ соответствует 5 Мб информации для передачи по каналу связи.
Таблица 6 – Искаженность при передаче условного сообщения
| Исходный текст | Текст после передачи |
| Понятие информация является одним из фундаментальных в современной науке вообще и базовым для информатики и теории информации. Её как и вещество, и энергию считают в качестве важнейшей сущности мира. | Полятие информация являттся одеим из фхдаментальных в совреянной нагке вообщеди базовшм для инпорматики и теории инфо.мации. 7Её как и веэество, и энергтю считадт в качнстве ваонейлей сукност1 ми7а. |
Для наглядности представления количества верной / искаженной информации составим таблицу 7, где каждый символ пронумерован в порядке передачи информации, что позволит определить потери от объёма информации для каждого узла:
| | (8) |
где m – число ошибок;
n – число символов.
Функциональная зависимость потерь информации с расстоянием передачи информации:
| | (9) |
На основании формул 8 и 9, составлена таблица 8 расчета итоговых значений потерь информации:
| | (10) |
На рисунке 8 определена оптимальная связывающая сеть при условии минимизации потерь информации по каналу связи, для всех линий связи указано итоговое значение потерь информации в процентах.
Рисунок 8 – Оптимальная связывающая сеть при условии минимизации потерь информации по каналу связи
Таблица 7 – Нумерация ошибок относительно передаваемого текста
| N | Объем информациии, МБ | текст | ошибка | N | Объем информациии, МБ | текст | ошибка | N | Объем информациии, МБ | текст | ошибка |
| 1 | 5 | п | | 31 | 155 | е | н | 61 | 305 | я | м |
| 2 | 10 | о | | 32 | 160 | и | | 62 | 310 | е | |
| 3 | 15 | л | н | 33 | 165 | м | | 63 | 315 | н | |
| 4 | 20 | я | | 34 | 170 | | | 64 | 320 | н | |
| 5 | 25 | т | | 35 | 175 | и | | 65 | 325 | о | |
| 6 | 30 | и | | 36 | 180 | з | | 66 | 330 | й | |
| 7 | 35 | е | | 37 | 185 | | | 67 | 335 | | |
| 8 | 40 | | | 38 | 190 | ф | | 68 | 340 | н | |
| 9 | 45 | и | | 39 | 195 | х | у | 69 | 345 | а | |
| 10 | 50 | н | | 40 | 200 | н | | 70 | 350 | г | у |
| 11 | 55 | ф | | 41 | 205 | д | | 71 | 355 | к | |
| 12 | 60 | о | | 42 | 210 | а | | 72 | 360 | е | |
| 13 | 65 | р | | 43 | 215 | м | | 73 | 365 | | |
| 14 | 70 | м | | 44 | 220 | е | | 74 | 370 | в | |
| 15 | 75 | а | | 45 | 225 | н | | 75 | 375 | о | |
| 16 | 80 | ц | | 46 | 230 | т | | 76 | 380 | о | |
| 17 | 85 | и | | 47 | 235 | а | | 77 | 385 | б | |
| 18 | 90 | я | | 48 | 240 | л | | 78 | 390 | щ | |
| 19 | 95 | | | 49 | 245 | ь | | 79 | 395 | е | |
| 20 | 100 | я | | 50 | 250 | н | | 80 | 400 | д | пробел |
| 21 | 105 | в | | 51 | 255 | ы | | 81 | 405 | и | |
| 22 | 110 | л | | 52 | 260 | х | | 82 | 410 | | |
| 23 | 115 | я | | 53 | 265 | | | 83 | 415 | б | |
| 24 | 120 | т | е | 54 | 270 | в | | 84 | 420 | а | |
| 25 | 125 | т | | 55 | 275 | | | 85 | 425 | з | |
| 26 | 130 | с | | 56 | 280 | с | | 86 | 430 | о | |
| 27 | 135 | я | | 57 | 285 | о | | 87 | 435 | в | |
| 28 | 140 | | | 58 | 290 | в | | 88 | 440 | ш | ы |
| 29 | 145 | о | | 59 | 295 | р | | 89 | 445 | м | |
| 30 | 150 | д | | 60 | 300 | е | | 90 | 450 | | |
Продолжение таблицы 7
| N | Объем информациии, МБ | текст | ошибка | N | Объем информациии, МБ | текст | ошибка | N | Объем информациии, МБ | текст | ошибка |
| 91 | 455 | д | | 121 | 605 | м | | 151 | 755 | е | |
| 92 | 460 | л | | 122 | 610 | а | | 152 | 760 | р | |
| 93 | 465 | я | | 123 | 615 | ц | | 153 | 765 | г | |
| 94 | 470 | | | 124 | 620 | и | | 154 | 770 | т | и |
| 95 | 475 | и | | 125 | 625 | и | | 155 | 775 | ю | |
| 96 | 480 | н | | 126 | 630 | . | | 156 | 780 | | |
| 97 | 485 | п | ф | 127 | 635 | 7 | пробел | 157 | 785 | с | |
| 98 | 490 | о | | 128 | 640 | Е | | 158 | 790 | ч | |
| 99 | 495 | р | | 129 | 645 | е | | 159 | 795 | и | |
| 100 | 500 | м | | 130 | 650 | | | 160 | 800 | т | |
| 101 | 505 | а | | 131 | 655 | к | | 161 | 805 | а | |
| 102 | 510 | т | | 132 | 660 | а | | 162 | 810 | д | ю |
| 103 | 515 | и | | 133 | 665 | к | | 163 | 815 | т | |
| 104 | 520 | к | | 134 | 670 | | | 164 | 820 | | |
| 105 | 525 | и | | 135 | 675 | и | | 165 | 825 | в | |
| 106 | 530 | | | 136 | 680 | | | 166 | 830 | | |
| 107 | 535 | и | | 137 | 685 | в | | 167 | 835 | к | |
| 108 | 540 | | | 138 | 690 | е | | 168 | 840 | а | |
| 109 | 545 | т | | 139 | 695 | э | щ | 169 | 845 | ч | |
| 110 | 550 | е | | 140 | 700 | е | | 170 | 850 | н | е |
| 111 | 555 | о | | 141 | 705 | с | | 171 | 855 | с | |
| 112 | 560 | р | | 142 | 710 | т | | 172 | 860 | т | |
| 113 | 565 | и | | 143 | 715 | в | | 173 | 865 | в | |
| 114 | 570 | и | | 144 | 720 | о | | 174 | 870 | е | |
| 115 | 575 | | | 145 | 725 | , | | 175 | 875 | | |
| 116 | 580 | и | | 146 | 730 | | | 176 | 880 | в | |
| 117 | 585 | н | | 147 | 735 | и | | 177 | 885 | а | |
| 118 | 590 | ф | | 148 | 740 | | | 178 | 890 | о | ж |
| 119 | 595 | о | | 149 | 745 | э | | 179 | 895 | н | |
| 120 | 600 | . | р | 150 | 750 | н | | 180 | 900 | е | |
Продолжение таблицы 7
| N | Объем информациии, МБ | текст | ошибка |
| 181 | 905 | й | |
| 182 | 910 | л | ш |
| 183 | 915 | е | |
| 184 | 920 | й | |
| 185 | 925 | | |
| 186 | 930 | с | |
| 187 | 935 | у | |
| 188 | 940 | к | щ |
| 189 | 945 | н | |
| 190 | 950 | о | |
| 191 | 955 | с | |
| 192 | 960 | т | |
| 193 | 965 | 1 | и |
| 194 | 970 | | |
| 195 | 975 | м | |
| 196 | 980 | и | |
| 197 | 985 | 7 | р |
| 198 | 990 | а | |
| 199 | 995 | . | |
Таблица 8 – Расчет итоговых значений потерь информации
| Пункт | Li, км | δ(L), % | Объем Информации (полученной), МБ | n, число символов | m, число ошибок | δ(I), % | δ∑,% |
| АБ | 7,0 | 6,32 | 375 | 75 | 6 | 8,00 | 10,20 |
| БВ | 4,3 | 4,34 | 405 | 81 | 7 | 8,64 | 9,67 |
| БЕ | 1,5 | 2,36 | 510 | 102 | 9 | 8,82 | 9,13 |
| ВЕ | 5,2 | 4,99 | 510 | 102 | 9 | 8,82 | 10,14 |
Продолжение таблицы 8
| Пункт | Li, км | δ(L), % | Объем информациии (полученной), МБ | n, число символов | m, число ошибок | δ(I), % | δ∑,% |
| ВЗ | 4,7 | 4,63 | 435 | 87 | 7 | 8,05 | 9,28 |
| ЕЗ | 7,2 | 6,47 | 435 | 87 | 7 | 8,05 | 10,33 |
| ЕК | 5,8 | 5,43 | 465 | 93 | 8 | 8,60 | 10,17 |
| ЕД | 3,5 | 3,77 | 585 | 117 | 9 | 7,69 | 8,57 |
| ЗК | 6,3 | 5,80 | 465 | 93 | 8 | 8,60 | 10,37 |
| КИ | 4,1 | 4,20 | 390 | 78 | 6 | 7,69 | 8,76 |
| АГ | 4,7 | 4,63 | 275 | 55 | 4 | 7,27 | 8,62 |
| ГБ | 3,2 | 3,56 | 375 | 75 | 6 | 8,00 | 8,76 |
| ГД | 3,9 | 4,06 | 585 | 117 | 9 | 7,69 | 8,70 |
| ДИ | 4,0 | 4,13 | 390 | 78 | 6 | 7,69 | 8,73 |
| ИЖ | 3,7 | 3,91 | 560 | 112 | 9 | 8,04 | 8,94 |
| АЖ | 6,1 | 5,65 | 560 | 112 | 9 | 8,04 | 9,82 |
2.4 Расчет энтропии и количества информации в сообщении
Для расчета энтропии сообщения «Отчет выполнен студентом вечернего факультета специальности информационно измерительная техника и технологии Шаманаевым Александром Викторовичем», разложим текст сообщения посимвольно:
Таблица 9 – Расчет реальной энтропии сообщения
| N | i | Pi, частотность букв русского языка | m, число символов | PilogPi | H(Si)=m·Pi·logPi |
| 1 | _ | 0,125 | 13 | -0,38 | 4,88 |
Продолжение таблицы 9
| N | i | Pi, частотность букв русского языка | m, число символов | PilogPi | H(Si)=m·Pi·logPi |
| 2 | О | 0,09 | 13 | -0,31 | 4,06 |
| 3 | Е | 0,067 | 14 | -0,26 | 3,66 |
| 4 | А | 0,062 | 11 | -0,25 | 2,74 |
| 5 | И | 0,062 | 12 | -0,25 | 2,98 |
| 6 | T | 0,053 | 11 | -0,22 | 2,47 |
| 7 | H | 0,053 | 13 | -0,22 | 2,92 |
| 8 | Ё | 0,047 | 1 | -0,21 | 0,21 |
| 9 | C | 0,045 | 4 | -0,20 | 0,81 |
| 10 | P | 0,04 | 5 | -0,19 | 0,93 |
| 11 | B | 0,038 | 5 | -0,18 | 0,90 |
| 12 | Л | 0,035 | 6 | -0,17 | 1,02 |
| 13 | К | 0,028 | 4 | -0,14 | 0,58 |
| 14 | М | 0,026 | 7 | -0,14 | 0,96 |
| 15 | Д | 0,025 | 2 | -0,13 | 0,27 |
| 16 | П | 0,023 | 2 | -0,13 | 0,25 |
| 17 | У | 0,021 | 2 | -0,12 | 0,23 |
| 18 | Я | 0,018 | 1 | -0,10 | 0,10 |
| 19 | Ы | 0,016 | 2 | -0,10 | 0,19 |
| 20 | З | 0,015 | 1 | -0,09 | 0,09 |
| 21 | Ь | 0,013 | 3 | -0,08 | 0,24 |
| 22 | Ъ | 0,013 | 0 | -0,08 | 0,00 |
| 23 | Б | 0,013 | 0 | -0,08 | 0,00 |
| 24 | Г | 0,012 | 2 | -0,08 | 0,15 |
| 25 | Ч | 0,011 | 3 | -0,07 | 0,21 |
| 26 | Й | 0,01 | 0 | -0,07 | 0,00 |
| 27 | Х | 0,009 | 2 | -0,06 | 0,12 |
| 28 | Ж | 0,007 | 0 | -0,05 | 0,00 |
| 29 | Ю | 0,006 | 0 | -0,04 | 0,00 |
| 30 | Ш | 0,006 | 1 | -0,04 | 0,04 |
| 31 | Ц | 0,004 | 2 | -0,03 | 0,06 |
| 32 | Щ | 0,003 | 0 | -0,03 | 0,00 |
| 33 | Э | 0,003 | 0 | -0,03 | 0,00 |
| 34 | Ф | 0,002 | 2 | -0,02 | 0,04 |
| Σ,N | 144 | Σ, Hреальн | 31,11 | ||
Идеальные сообщения, имеющие максимальную энтропию, оптимальны в том смысле, что в них на один символ (элемент, уровень квантования) приходится наибольшее количество информации.
Hоптим = n·log(N) = 34·log(144) = 73,38
В реальных сообщениях символы всегда коррелированны (после запятой не появляется точка, после гласной мягкий знак), вследствие чего количество информации, приходящееся на один символ будет меньше, чем в идеальных. Соотношение реальных и оптимальных сообщений выражается посредством коэффициента сжатия:
Количество информации в сообщении:
T = n·H(S) = 34·31,11[бит] = 1057,74[бит] = 132,23[байт]
2.5 Кодирование сообщения в вид, соответствующий 9-ричной системе счисления
Преобразуем исходное сообщение «Отчет выполнен студентом вечернего факультета специальности информационно измерительная техника и технологии Шаманаевым Александром Викторовичем» в вид, соответствующий десятеричной системе счисления, в 2 этапа:
1) представим исходный текст в кодировке 1251 согласно таблице 10;
2) переведем получившийся код в десятичную систему по схеме Горнера.
Таблица 10 – Кодировка 1251
Переведем полученный код из 10-тичной системы счисления в 9-ричную по следующему алгоритму:
1) выписываем степени 9 до тех пор, пока значение очередной степени не станет больше заданного числа в 10-тичной;
2) задавшись вопросом: «сколько раз входит следующая за найденной степень в 10-тичное число», фактически делим десятичное число на степень;
3) записываем результат деления и остаток;
4) задаемся вопросом: «сколько раз входит следующая степень в остаток?»;
5) повторяем пункты 3-5 до последней степени (нулевой).
На примере сообщения «Отчет», результаты кодирования представлены в табличном виде:
Таблица 11 – Перевод в десятичную систему по схеме Горнера
| N | Символ | Кодировка 1251 | Перевод в десятичную систему по схеме Горнера | |
| | | A | | B |
| 1 | О | 206 | A1·256+A2 | 52978 |
| 2 | т | 242 | B1·256+A3 | 13562615 |
| 3 | ч | 247 | B2·256+A4 | 3472029669 |
| 4 | е | 229 | B3·256+A5 | 888839595506 |
| 5 | т | 242 | | |
Таблица 12 – Перевод сообщения из 10-тичной системы счисления в 9-ричную
| N | Степени 9-ки по убыванию | Результат деления | Остаток | ||||
| | | A | | B | C | | D |
| 1 | 913 | 2541865828329 | D1/A1 | 0 | 0 | 10-я кодировка | 888839595506 |
| 2 | 912 | 282429536481 | D1/A2 | 3,15 | 3 | D1-A2·C2 | 41550986063 |
| 3 | 911 | 31381059609 | D2/A3 | 1,32 | 1 | D2-A3·C3 | 10169926454 |
| 4 | 910 | 3486784401 | D3/A4 | 2,92 | 2 | D3-A4·C4 | 3196357652 |
| 5 | 99 | 387420489 | D4/A5 | 8,25 | 8 | D4-A5·C5 | 96993740 |
| 6 | 98 | 43046721 | D5/A6 | 2,25 | 2 | D5-A6·C6 | 10900298 |
| 7 | 97 | 4782969 | D6/A7 | 2,28 | 2 | D6-A7·C7 | 1334360 |
| 8 | 96 | 531441 | D7/A8 | 2,51 | 2 | D7-A8·C8 | 271478 |
| 9 | 95 | 59049 | D8/A9 | 4,60 | 4 | D8-A9·C9 | 35282 |
| 10 | 94 | 6561 | D9/A10 | 5,38 | 5 | D9-A10·C10 | 2477 |
| 11 | 93 | 729 | D10/A11 | 3,40 | 3 | D10-A11·C11 | 290 |
| 12 | 92 | 81 | D11/A12 | 3,58 | 3 | D11-A12·C12 | 47 |
| 13 | 91 | 9 | D12/A13 | 5,22 | 5 | D12-A13·C13 | 2 |
| 14 | 90 | 1 | D13/A14 | 2,00 | 2 | D13-A14·C14 | 0 |
Полученный 9-ричный код сообщения «Отчет»: 3128222453352.
Таблица 13 – Представление сообщения в 10 и 9-ричном коде
| Элемент сообщения | 10-ричный код сообщения | 9-ричный код сообщения |
| Отчет | 888839595506 | 3128222453352 |
| выполнен | 16355930281165579757 | 130865628108677286345 |
| студентом | 4463171909616711954156 | 44708642175072085238681 |
| вечернего | 4185535126835237872622 | 42223868162571185145055 |
| факультета | 1156406422627600226972384 | 15442542318130453184816017 |
| специальности | 19168232093295705318366530106088 | 552151665715117770313273384072584 |
| информационно | 18454577756904481487242486738414 | 533305037672482087574545307538654 |
| измерительная | 18452711132937414971464784666879 | 533258846566304535545566323775602 |
| техника | 68369788785191648 | 408054288284404255 |
| и | 59392 | 100421 |
| технологии | 1147054714330139494443241 | 15337123843716354681217634 |
| Шаманаевым | 1024180299876492225215468 | 13750146588465073813045006 |
| Александром | 233227754723435834271395564 | 4007784700567531714161523332 |
| Викторовичем | 60321672210578118669606839788 | 1372313613034778417552174102713 |
2.6 Итоговый выбор оптимального маршрута
Независимо от оптимизации связывающей сети по условию минимизации потерь информации (рисунок 8), чтобы не перегружать объемом передаваемой информации ветвь АГ, группируем пункты по маршрутам согласно таблице 4.
Анализ маршрута 1 (пункты А, Б, В, З, К, Е):
- оптимальная связывающая сеть при условии минимизации потерь информации (рисунок 8) не эффективна при оптимизации по критерию быстроты прохождения информационного пакета по каналу связи (рисунок 7);
- оптимальная связывающая сеть при условии оптимизации по критерию быстроты прохождения информационного пакета не эффективна по причине того, что маршруты как прямой передачи (от пункта А к пунктам Б, В, Е,З,К), так и обратной объемом 860 Mб, совпадают;
- оптимальная связывающая сеть согласно расстоянию и объему передаваемой / получаемой информации (рисунок 5) наиболее эффективна, так как не содержит дестабилизирующих ветвей по помехоустойчивости или пропускной способности.
Анализ маршрута 2 (пункты А, Г, Д, И, Ж):
- оптимальная связывающая сеть согласно расстоянию и объему передаваемой / получаемой информации (рисунок 5) не эффективна, так как содержит дестабилизирующую ветвь ЖА по параметру пропускной способности;
- оптимальная связывающая сеть при условии минимизации потерь информации (рисунок 8) не эффективна, так как содержит дестабилизирующую ветвь ЖА по параметру пропускной способности;
- оптимальная связывающая сеть при условии оптимизации по критерию быстроты прохождения информационного пакета (рисунок 7), с учетом удаленности пункта Ж (соответственно повышенных потерь информации) не эффективна;
- воспользовавшись соединением пунктов маршрута 2 по типу «звезда» (в таблице 14 приведен анализ порядка приема / передачи информации в каждом отдельном пункте), можно добиться наибольшей эффективности.
С учетом общего анализа маршрутов 1 и 2 оптимальная связывающая сеть выбрана согласно рисунку 9.
Таблица 14 – Порядок приема / передачи информации при соединении по типу «звезда»
| В прямом направлении | Обратный путь | ||||
| пункт | пришло | передано | пункт | пришло | получено |
| Г | 1810 | 275 | Ж | | 400 |
| Д | 1535 | 585 | И | | 70 |
| И | 950 | 390 | Д | 470 | 140 |
| Ж | 950 | 560 | Г | 610 | 375 |
| А | | | А | 985 | |
Рисунок 9 – Оптимальная связывающая сеть
Заключение
Требования сегодняшнего дня диктуют внедрение мультисервисных сетей, способных эффективно передавать разнородный трафик, включающий данные, голос и видео. Задачи по эффективной передаче информации стоят как перед небольшим офисом, так и перед крупным холдингом. Последний может обладать достаточно сложной территориально-распределенной организационной и иерархической структурой.
Главным требованием, предъявляемым к сетям, является выполнение сетью ее основной функции – обеспечение пользователям потенциальной возможности доступа к разделяемым ресурсам всех компьютеров, объединенных в сеть. Все остальные требования – производительность, надежность, совместимость, управляемость, защищенность, расширяемость и масштабируемость – связаны с качеством выполнения этой основной задачи.
Хотя все эти требования весьма важны, часто понятие «качество обслуживания» (Quality of Service, QpS) компьютерной сети трактуется более узко – в него включаются только две самые важные характеристики сети – производительность и надежность.
Между показателями производительности и надежности сети существует тесная связь. Ненадежная работа сети очень часто приводит к существенному снижению ее производительности. Это объясняется тем, что сбои и отказы каналов связи и коммуникационного оборудования приводят к потере или искажению некоторой части пакетов, в результате чего коммуникационные протоколы вынуждены организовывать повторную передачу утерянных данных. Так как в локальных сетях восстановлением утерянных данных занимаются как правило протоколы транспортного или прикладного уровня, работающие с тайм-аутами в несколько десятков секунд, то потери производительности из-за низкой надежности сети могут составлять сотни процентов.
Даже при тонкой настройке сети оптимальное сочетание ее параметров (в строгом математическом понимании) получить невозможно, да и не нужно. Нет необходимости затрачивать колоссальные усилия по нахождению строгого оптимума, отличающегося от близких к нему режимов работы на величины такого же порядка, что и точность измерений трафика в сети. Достаточно найти любое из близких к оптимальному решений, чтобы считать задачу оптимизации сети решенной. Такие близкие к оптимальному решения обычно называют рациональными вариантами, и именно их поиск интересует на практике администратора сети или сетевого интегратора.
