Расчет энтропии и количества информации в сообщении

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

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

       Борьба  с помехами уменьшает, но не исключает вероятность появления ошибок. Что бы их учесть или ликвидировать вводятся различные способы кодирования, которые учитывают вероятность ошибок и при их обнаружении, либо их устраняют, либо выдают соответствующее сообщение. К таковым кодам относятся корректирующие коды, систематические коды и контроль по четности.

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

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

       Систематические коды. Такие коды  состоят из двух частей, первая часть содержит  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. Объём информации для передачи из пункта А в каждый пункт и получаемых из них

       Представив  кратчайшую связывающую сеть, группируем пункты с учетом передаваемого / получаемого объёма информации, и максимального объёма информационного пакета:

2. Сгруппированные пункты по маршрутам

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

3. Симметричная матрица маршрута 1

 

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

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

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

       При этом для каждой пары пунктов необходимо найти величину приращения маршрута  (∆)  по формуле:

   где С – расстояние;

          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