НАУКА и ОБРАЗОВАНИЕ

УДК 681.31

Россия, МГТУ им. Н.Э. Баумана

irudakov@yandex.ru

При анализе и проектировании структур сложных  дискретных устройств  таких, как микропроцессорные и робототехнические системы, системы управления технологическими процессами, комплексные автоматизированные системы  используется блочно-иерархический метод [1], который предусматривает расчленение процесса проектирования на ряд последовательных уровней и сведение задачи большей размерности к совокупности задач значительно меньшей размерности.

Метод анализа дискретных устройств, формализованных логической сетью, в рамках иерархических уровней проектирования  недостаточен, так как не позволяет учитывать такие характеристики дискретного устройства как, например, временные параметры элементов, входящих в модель, а, следовательно, выполнять надежную верификацию проекта. В работах по многоуровневому анализу [2, 3, 4] используется принцип рассмотрения  схемы устройства с разной степенью детализации. Предлагаемый в работе метод декомпозиции [5] модели сложной структуры, формализованной в виде функционального блока, позволяет выполнить анализ правильности функционирования сложного дискретного устройства путем автоматического перехода на более низкий иерархический уровень.

Для декомпозиции сложной дискретной структуры необходимо выбрать ортогональное множество разбиений [5].

Поставим в соответствие каждому разбиению  функцию , такую, что , т.е. значение функции  на паре  равно блоку , в котором содержится состояние .

Образуем на множествах A и Z соответственно разбиения  и , так что:

1.      и  находятся в одном блоке разбиения , если и только если для любого  справедливо: ,  иначе

2.      и  находятся в одном блоке разбиения , если и только если для любого  справедливо: ,  иначе

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

Построим логическую сеть  , для чего определим все компоненты кортежа N.

1. Полагаем .

2. Полагаем .

3. Построим функциональные блоки , т.е. определим базис сети.

a.     Полагаем .

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

                   (1)

Здесь  и  соответственно внутренний и внешний входные алфавиты блока .

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

Определим разбиение  следующим образом:

,

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

В блоке  полагаем , а  определяется согласно равенствам (1).

c.     Определим функцию переходов функционального блока .

Пусть  соответственно блоки разбиений . Если , т. е.  (СП-разбиение), то

.

Таким  образом, значение функции переходов  равно блоку разбиения , содержащему . Здесь  функция переходов декомпозируемого блока .

Если же , то

4. Построим функции соединения функционального блока ; иначе (в терминах разбиений) .

Пусть . Образуем множество , такое, что . Таким образом, в  попадают только те векторы из , у которых пересечение всех компонентов не пусто. Такое пересечение  имеет место, так как компоненты  блоки разбиений, т.е. множества.

Функция  реализует отображение . Значение  определим следующим образом:

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

На множестве  функция  не определена.

5. Определим множество входных функций следующим образом:

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

6. Построим выходную функцию сети , иначе (в терминах разбиений) .

Пусть . Образуем множество , такое, что . Таким образом, в  попадают только те векторы из , у которых пересечение всех компонентов не пусто.

Функция  реализует отображение . Значение  определим следующим образом:

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

На множестве  функция  не определена.

В работе [5] показано, что построенная таким образом сеть реализует исходный функциональный блок .

Разбиения  и  однозначно определяется разбиением  ;  показывает, какие блоки воздействуют на автомат , а  определяет классы неразличимых автоматом  букв входного алфавита .

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

Рассмотрим алгоритм декомпозиции на примере модели сложного дискретного устройства, функционирование которого задано в табличном виде (таблица 1).

Таблица 1.

Пример функционирования дискретного устройства, заданного в виде.

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

Множество состояний данного устройства , входной алфавит устройства , выходной алфавит .

В качестве множества ортогональных разбиений возьмём множество , где

В результате декомпозиции получаем логическую сеть, представленную на рисунке 1.

Рисунок 1. Логическая сеть сложного дискретного устройства.

Стоит отметить, что в результате декомпозиции  сформировались следующие состояния:

Разработанный алгоритм и основные сущности, связанные с предметной областью, были реализованы в виде .NET-библиотеки, что позволяет использовать её в составе программных комплексов, предназначенных для анализа дискретных систем.

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

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

Литература

1.               Норенков И.П. Основы автоматизированного проектирования: Учеб. для  вузов.-М.: Изд-во МГТУ им. Н.Э. Баумана, 2000.- 360 с.

2.               Воротников С.А. Информационные устройства робототехнических систем. Уч. пособие – .-М.: Изд-во МГТУ им. Н.Э. Баумана, 2005.- 384 с 

3.               Рудаков И.В., Смирнов А.А. Исследование сложных дискретных систем на базе агентного метода. Статья. Вестник МГТУ им. Н.Э. Баумана – Сер. Приборостроение.-М.: МГТУ, 2009.-№3-С. 33-41.

4.               Рудаков И.В., Давудпур М. Алгоритм декомпозиции формальной модели функционального блока дискретного устройства. Статья. Вестник МГТУ им. Н.Э. Баумана – Сер. Приборостроение.-М.: МГТУ, 2006.-№1-С. 90-98

5.               Рудаков И.В., Давудпур М. Декомпозиционный метод  исследования дискретных устройств. Статья. Информационные технологии.-М.2006.-№2-С.44-49