Информационная технология проектирования моделей конечных автоматов

Поступила в редколлегию 30.08.2007

Вовк Александр Владимирович, аспирант кафедры прикладной математики ХНУРЭ. Научные интересы: теория вероятностей, случайные процессы. Адрес: Украина, 61100, Харьков, пр. Маршала Жукова, 45, кв. 16, тел. 716-16-88.

Дикарев Вадим Анатолиевич, д-р физ.-мат. наук, профессор каф. прикладной математики ХНУРЭ. Научные интересы: теория вероятностей, случайные процессы. Адрес: Украина, 61164, Харьков, пр. Ленина, 66, кв. 21, тел. 343-57-03.

Подгорбунский Никита Сергеевич, стажёр-исследователь кафедры прикладной математики ХНУРЭ. Научные интересы: теория вероятностей, случайные процессы. Адрес: Украина, 61195, Харьков, ул. Метростроителей, 15, кв. 23, тел. 716-02-70.

УДК 681.513

М.К. АЛЬ МАДИ, Д.Н. МОАМАР, Т.Ю. УТКИНА

ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ ПРОЕКТИРОВАНИЯ МОДЕЛЕЙ КОНЕЧНЫХ АВТОМАТОВ

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

Введение

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

Автоматы удобно описывать с помощью двух таблиц, одна из которых раскрывает функцию переходов у: ^ДХ) Q, а другая - функцию выходов j: ^ДХ) Y. Однако приведенная в циклограммах информация о причинно-следственных связях между исполнительными механизмами не позволяет формализовать процесс синтеза функций переходов и выходов, необходимых для построения моделей цифровых автоматов [1].

Целью данного исследования является разработка новой технологии преобразования исходной информации в последовательность операций управления технологическими процессами, что обеспечит сокращение трудоемкости разработки описаний цифровых автоматов. Решение данной задачи осуществляется в условиях, когда объектом управления является сложная техническая система, состоящая из заданного количества N исполнительных механизмов, положения которых контролируются датчиками. Так как обычно все механизмы имеют два конечных положения, то число датчиков равно 2^

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

- активизация механизма в заданный момент времени;

- контроль достижения механизмом первого конечного положения;

- задание продолжительности включенного состояния механизма и его выключение;

- контроль достижения механизмом второго конечного положения.

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

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

Необходимым условием корректности модели цифрового автомата должно быть наличие двух сигналов управления для каждого исполнительного механизма: включения Zi <='1' и выключения Zi <='0'. Удовлетворяющая данным условиям модель цифрового автомата позволит наглядно отобразить все причинно-следственные связи технологического процесса, что сократит ошибки при дальнейшем синтезе проекта автомата с помощью наиболее распространенных инструментальных средств.

При синтезе автоматов важным является исследование способов построения сложных автоматов. На этом этапе создают модель иерархического конечного автомата (Hierarchical Finite State Machine). Иерархическое представление удобно, когда нужно получить представление об общих принципах работы системы, а затем перейти к детальному анализу конкретных аспектов. Использование иерархического описания сложной системы облегчает ее восприятие. При этом понимание работы системы будет происходить сверху вниз по иерархии описания. Сначала пользователь знакомится с основными компонентами описываемой части модели и принципами их взаимодействия, а далее переходит к углубленному и более детальному описанию интересующего его компонента.

1. Структурно-функциональная модель цифрового автомата

Представим структурно-функциональную модель (МСФ) цифрового автомата в виде совокупности, состоящей из восьми компонентов:

МСФ = (Sw, Sc, U, Td, Tw, Tm, Ts, W), где Sw - состояния, в которых выполняются операции управления технологическим процессом; Sc - состояния, в которых выполняются контролирующие операции; U - условия переходов; Td - моменты фиксирования конечных состояний исполнительных механизмов; Tw - продолжительности активных состояний исполнительных механизмов; Tm - модельное время; Ts - суммарная продолжительность операций; W - операции управления технологическим процессом.

Данную модель удобно представить в виде направленного графа, в котором состояния контроля положения исполнительных механизмов обозначаются символом © . Состояния рабочих Sw и контролирующих Sc операций, отображающие происходящие события, располагаются не произвольно на плоскости, а на оси модельного времени. Условия переходов U и действия на переходах W объединяются операцией импликации U ^ W. Рабочие операции W выполняются над множеством сигналов управления Z = {Zi, ..., Zm} и относятся к логическим операциям, при выполнении которых выбранному управляющему сигналу присваивается единица или нуль (Zi < = '1' или Zi < = '0').

В состояниях контроля Sc сравнивается текущее модельное время Tm с заданным значением времени, в которое выбранный исполнительный механизм должен перейти в конечное положение. Положения механизмов фиксирует множество датчиков D={d1, d2, ..., dk}. Если при Tm = Tdi i-й механизм не достиг конечного положения, то формируется флаг ошибки, например, Error:= 'А'. Каждому исполнительному механизму соответствует специально установленное значение флага ошибки, например, взятое из символов латинского алфавита. При фиксировании любой неисправности цифровой автомат переходит в состояние анализа отказов и по значению флага ошибки можно легко идентифицировать отказавший механизм, что уменьшает трудоемкость работ по восстановлению исполнительных механизмов.

2. Применение структурно-функциональной модели для синтеза системы

управления фасовочно-упаковочным автоматом

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

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

Номер цикла

Обозна^ чение цилиндра

Время, с

Датчик

Модель цифрового автомата, управляющего операциями первого цикла для фасовочно-упаковочной машины карусельного типа, которая имеет 10 исполнительных механизмов, приведена на рис. 1.

тш т-г1 т-игл т-гг т-ог-г

51 .32 .53 54 55 56

5к

е—о—е—ю—№—Ю—ю

г1<=Г 21<=У 21<='0' Т-02-1

17<- "в*

т-ог-г

тэ

Рис. 1. Модель цифрового автомата для первого цикла технологических операций На графе показаны три контролирующие операции, обеспечивающие фиксирование и сравнение моментов срабатывания датчиков D1, D2-1, D2-2 с заданными на циклограмме значениями.

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

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

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

В результате преобразования получается объединенная таблица, содержащая функции переходов и выходов, по которым можно построить граф-схему цифрового автомата в среде Active-HDL [3].

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

Рис. 3. Структура проекта и модель цифрового автомата

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

Выводы. Достоинство предлагаемой модели цифрового автомата заключается в том, что она позволяет определить требуемое количество состояний, соответствующих управляющим и контролирующим операциям. Предлагаемая технология позволяет преобразовать информацию, содержащуюся на циклограммах, в промежуточную форму, удобную для синтеза цифровых автоматов при помощи современных инструментальных средств. Список литературы: 1. Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2002. 224 с. 2. Шувалова Л.А. Методы абстрактного синтеза структуры и последовательности выполнения операций фасовочно-упаковочных машин // Вюник Хмельницького нацюнального утверситету. 2005. № 4. C. 55-58. 3. Про-ектування цифрових систем з використанням мови VHDL// В.В. Семенець, 1.В. Хаханова, В.1. Хаханов. Харюв: ХНУРЕ, 2003. 492 с.

Поступила в редколлегию 02.09.2007 Аль Мади Мудар Кадривич, аспирант Черкасского государственного технологического университета. Научные интересы: верификация моделей микросхем памяти. Адрес: Украина, 18006, Черкассы, бул. Шевченко, 460, тел. 8 0472 730271, e-mail: mudarinfo@yahoo.com. Моамар Диаа Надимович, аспирант Черкасского государственного технологического университета. Научные интересы: разработка алгоритмов управления цифровыми устройствами. Адрес: Украина, 18006, Черкассы, бул. Шевченко, 460, тел. 8 0472 730271, e-mail: diaamoamar@yahoo.com.

Уткина Татьяна Юрьевна, аспирантка Черкасского государственного технологического университета. Научные интересы: методы диагностирования полупроводниковых запоминающих устройств. Адрес: Украина, 18006, Черкассы, бул. Шевченко, 460, тел. 8 0472 730271, e-mail: utia_chdtu@yahoo.com.

УДК 621.327

В.В. БАРАННИК, И.В. ХАХАНОВА

КОМПАКТНОЕ ПРЕДСТАВЛЕНИЕ МАТРИЦ ЗНАКОВ КОМПОНЕНТ ТРАНСФОРМАНТ

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

1. Введение

Современные методы сжатия строятся на основе комплексных подходов к процессам сокращения избыточности изображений [1- 4]. Поэтому сжатое представление оцифрованных изображений включает в себя не только информационную часть, но и служебные части. Объем служебных данных может достигать 30 - 50% от общего объема кодового представления. Значит, дополнительное повышение степени сжатия неразрывно связано с обработкой массивов служебных данных.

В случае реализации технологии сжатия, основанной на dwt-преобразованиях, служебными данными являются массивы и двоичных данных, несущих информации о знаке компонент трансформант:

и={и;, i=1т, j=й, и; ] 6{0;1}; и _{0, ^ -0;

и'j {1, ^ У,j < 0,

где и;j - (1; j)-й элемент матрицы знаков; т,п - соответственно количество строк и столбцов в трансформанте; У1 j - (1; j)-я компонента трансформанты.