Методический материал и пример выполнения задания №1

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

Графом называется некоторая совокупность точек и связывающих их линий.

Точка графа называются вершинами, а линии – дугами. Граф математически обозначается как G (N, V), где N – конечное множество вершин мощностью n, а V-конечное множество дуг мощностью m.

Рисунок 1 - Ориентированный граф

Вершины можно обозначить строчными буквами (i, j, k, l, s) либо цифрами (1,2,3,4,5) (рисунок 1), а дуги соответственно парами {(i, j), (j, k), (k, l), …} либо {(1,2), (2,3), (3,4), …}, где первый индекс определяет начало, а второй – конец дуги.

Граф, в котором задается направление дуг, называется ориентированным (Б), а в противном случае – неориентированным (А). Неориентированные дуги называются ребрами.

Между двумя вершинами, соединенными дугой (ребром), существует отношение смежности (для ориентированного графа вершины i и j смежны, если дуга начинается в i и направлена в j).

Между вершиной и соединенными с ней дугами (ребрами) существует отношение инцидентности.

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

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

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

Одним из наиболее распространенных дискретных представлений графа является матрица смежностей. Эта матрица A= [ ] размером n x n элементов, которые могут принимать значения:

= 1, если в графе G существует дуга (ребро) между вершинами i и j;

= 0, в противном случае.

Матрица смежностей графа, приведенного на рисунке 1, имеет вид

A=

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

Если перенумеровать в произвольном порядке дуги (ребра) графа G и поставить эти номера в соответствие номерам строк некоторой матрицы B=[ ], а номера столбцов оставить по-прежнему соответствующим номерам вершин графа, то такой матрице можно отобразить отношение инцидентности элементов графа G. Элементы матрицы могут принимать значения {0,1}.

Перенумеруем дуги для рассматриваемого графа: (i, j) - 1; (j, k) - 2;

(k, l) - 3; (l, s) - 4; (s, i) - 5; (s, j) - 6; (s, k) - 7. Тогда матрица инцидентности будет иметь вид:

B=

Задание №2

Осуществить процедуру кодирования сигналов в системе связи с ИКМ.

Порядок выполнения:

1. Вычертить схему кодера взвешивающего типа.

2. Выполнить кодирование отсчетов согласно вариантам заданий, приведенным в таблице 1.

Исходные данные

Таблица 1

3. Результаты поэтапного кодирования первого амплитудного отсчета занесите в таблицу 2.

Таблица 2

S_КВ = │I_АИМ│- ∑│I_ЭТ│

4. Определить ошибку квантования.

5. Результаты кодирования остальных отсчетов занесите в таблицу 3

Таблица 3