Определение оптимальной связывающей сети (стр. 5 из 10)
Для организации работы корректирующих кодов используется введение принципа избыточности информации, за счет чего основная информация приобретает помехоустойчивые свойства. Но для расположения такой избыточной информации необходимо ввести дополнительные разряды, которые заполняются соответствующим кодом.
Систематические коды. Такие коды состоят из двух частей, первая часть содержит 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.