Описание алгоритмов с помощью диаграммы состояний

Способы описания алгоритмов функционирования узла коммутации

Лекция 2

Системы счисления

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

Наиболее распространенной является десятичная система счисления. Она использует десять символов – 0,1,2,3,4,5,6,7,8,9. Вес первого (самого правого) символа числа умножается на 10⁰, следующего – на 10¹ и т.д. Например, десятичное число 3567 представляется как 3∙ 10³ + 5∙ 10² + 6∙ 10¹ + 7∙ 10⁰ = 3567.

Цифровые вычислительные устройства используют двоичную систему счисления (двоичный код). Она использует два символа – 0 и 1. Вес первого (самого правого) символа числа умножается на 2⁰, следующего – на 2¹ и т.д. Например, десятичное число 3567 в двоичном коде представляется как 1∙ 2¹¹ + 1∙ 2¹⁰ + 0∙ 2⁹ + 1∙ 2⁸ + 1∙ 2⁷ + 1∙ 2⁶ + 1 ∙2⁵ + 0 ∙2⁴+ 1 ∙2³ + 1 ∙2² + 1 ∙2¹ + 1 ∙2⁰ = 110111101111₂ = 2048 + 1024 + 256 + 128 + 64 + 32 + 8 + 4 + 2 + 1 = 3567.

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

Табл. 1.1 – Соответствие кодов различных систем счисления

Десятичный код	Двоичный код	Восьмеричный код	Шестнадцатеричный код
			A
			B
			C
			D
			E
			F

Задание. Выполнить лабораторную работу 1 (Побитовые операции).

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

Хорошим правилом описания алгоритмов является его представление во всех трех формах – в виде SDL-диаграммы, временной диаграммы и текстового описания.

Описание сложных алгоритмов удобно описывать в виде диаграммы состояний, используя язык спецификаций и описания (S pecification and D escription Language, S DL), используя Рекомендацию ITU-T Z.100.

SDL опирается на идею расширенной машины с конечным числом состояний (Finite State Machines, FSM). FSM представляет собой аппаратно-программный автомат, действующий по принципу воздействие-ответ. Для обработки любого процесса используются четыре устройства (рис. 2.1): входной порт (Input port), FSM, таймеры (Timer) и входные данные (Variable).

		Рис. 2.1. Расширенная FSM

Во входном порту образуется очередь входных сигналов (Input signal), которые там хранятся до момента их взятия в обработку FSM. Входные сигналы (воздействия) от разных источников обрабатываются FSM в порядке их поступления. Каждый входной сигнал имеет вид дискретного сообщения, содержащее имя и входные данные. Для каждого состояния FSM хранит список ожидаемых сообщений. Если входное сообщение соответствует списку ожидаемых сообщений, то FSM в соответствии с входными данными производит транзакцию, т.е. необходимые действия (например, генерирует выходной сигнал источнику/ам воздействий) для перехода в следующее состояние. Если входное сообщение отсутствует в списке, то оно игнорируется. Если во входном порту сообщения отсутствуют, то FSM остается в прежнем состоянии. Для исключения “зависания” процесса FSM таймирует время ожидания поступления очередного сообщения. Поведение FSM в зависимости от входных сообщений отображается в виде диаграммы состояний.

Диаграмма состояний использует следующие основные символы.

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

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

Символ Input (ввод) обозначает внешнее воздействие. Имеет лист стимулов, каждый стимул имеет список сигналов. В теле символа содержится имя воздействия.

Символ Label (Соединитель) используется для соединения различных символов при ограниченном формате листа. Имеет свое имя.

Символ Procedure Call (Обработка вызова) обозначает действия, выполняемые ПО для обслуживания вызова. В теле символа содержится краткое описание действия.

Символ Comment (комментарий) используется для дополнительных пояснений, не поместившихся в теле символа.

Символ Decision (Решение) используется при ветвлении процесса в зависимости от данных. В теле символа содержится вопрос. Положительный ответ обозначается Yes (Да), отрицательный ответ обозначается No (Нет).

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

Символ сохранения данных для обработки в другом состоянии. В теле символа содержатся сохраняемые параметры.

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

Порядок выполнения операций во времени – сверху-вниз. Одна из сторон взаимодействия располагается слева, другая – справа. Описание действия и значения таймеров прилагается в текстовом формате.

SDL-диаграммы широко применяются при описании алгоритма функционирования узлов коммутации в сетях связи интегрального обслуживания (Integrated Services Digital Network, ISDN) в виде Рекомендаций сектора стандартизации электросвязи Международного союза электросвязи (International Telecommunication Union - Telecommunication sector, ITU-T).

В узле ISDN используются четыре уровня. Первые четыре верхних уровня образуют подсистему пользователя (ISDN User Part, ISUP) и изображены в виде одной подсистемы управления вызовом (Call Control). Блок-схема обслуживания соединений представлена на рис. 2.2.

		Рис. 2.2. Стек протоколов соединения на абонентском участке

Например, алгоритм функционирования третьего уровня в виде SDL-диаграмм и текстового описания представлен в Рекомендации ITU-T Q.931 (рис. 2.3).

	Рис. 2.3. Установление соединения в ISDN (стр.192)

Дата добавления: 2014-11-25