§ 7.8. Реализация нечеткими автоматами временных соотношений*)

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

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

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

Пример 7.8. Пусть на каком-либо из этапов синтеза получена диаграмма переходов синтезируемого автомата, представленная на рис. 7.3. На ней показаны только те переходы, которые необходимо реализовать технологически. Если для кодированпя множества внутренних состояний синтезируемого автомата мы будем использовать двухпозиционный код, то, как это следует из диаграммы переходов, нам не удастся избавиться от состязаний. Однако пусть нам, например, известно, что из двух триггеров, которые будут использоваться для записи текущего состояния автомата в реальной схеме, переходный процесс в одном из них протекает значительно быстрее, чем в другом. Слова «значительно быстрее», которые мы только что использовали, должны пониматься качественно. Пока мы не предполагаем никакой количественной оценки этих слов. Будем для удобства считать, что «значительно быстрее» перекидывается триггер, используемый для кодирования первой позиции в коде состояния. Опишем теперь процедуру выбора кодов состояний. Если состояние q, закодировать кодом 11, то при переходе в состояние с кодом 00 в качестве промежуточного состояния возникнет код состояния 01. При переходе же от кода 00 к коду 11 — возникнет код промежуточного состояния 10. Учитывая это, а также особенности исходной диаграммы переходов, можно предложить следующее кодирование состояний gt — 00, дг — 01, д* —

—10 тп q, — И. На рис. 7.4 показана результирующая диаграмма переходов автомата.

Из этой диаграммы видно, что функция переходов автомата будет реализовываться всегда правильно за исключением перехода 11-^10-^00. Однако из-за того, что первый триггер перекидывается «значительно быстрее» второго триггера, то автомат с подобным кодированием состояний будет работать «почти всегда правильно». Отметим, что инженер-практик, имеющий априорную информацию о скорости срабатывания триггеров, подобную вышеприведенной информации, выберет кодирование такого же типа.

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

 

тиями, как «значительно быстрее», «ранее чем», «вскоре после этого» и т. п. Опишем элементы логики такого типа.

Через и будем обозначать некоторый временной интервал, отсчитываемый в абсолютном или относительном физическом времени. Если нас будут интересовать границы интервала U, то этот же интервал будет записываться как (мі, р<). В отличие от обычного понимания событий, происходящих во времени, мы будем трактовать их как нечеткие события. Нечеткое событие на интервале ti будет обозначаться как <а, U, Ца(іі)>. Здесь а — наименование события, U — временной интервал, а \ia{U) — функция принадлежности события а временному интервалу U.

Вместо    будем использовать специальные нечеткие кван

торы типа «в подавляющем большинстве случаев», «почти всегда», «часто», «примерно в половине случаев», «редко», «почти никогда», «в исключительных случаях». Эти кванторы (их список, конечно, можно продол/кпть, но мы для краткости не будем этого делать) будем обозначать как >|® (і = 1, 2, 3, 4, 5, 6, 7). Таким образом, запись вида >|^а(^г) содержательно будет трактоваться так: событие а происходит в интервале h почти всегда. Кроме указанных размытых кванторов в нашей логике будут использоваться различные операторы типа: «ранее», «до», «после того как произошло а» и т. п. Будем рассматривать временную логику в специальной секвенциальной форме, удобной для щ)иложений к теории автоматов.

7.8.2. Секвенциальные автоматы. В [3] приводится следующее определение секвенциального автомата. Секвенциальным автоматом называется совокупность секвенций следующего вида:

Здесь й = 1, 2, ..., ге; d=l, 2, ..., т\ —слова из входного алфавита, Yi — слова из выходного алфавита, S^, — кодовые слова для кодирования внутренних состояний автомата. Запись Ф [— 'ф, где ф и ip есть функции алгебры логики, называется секвенцией и обладает следующим смыслом: если на некотором наборе аргументов ф обращается в единицу, то на этом наборе также обращается в единицу. Секвенциальный автомат реализуется с помощью специальной секвенциальной структуры. Для примера на рис. 7.5 показана подобная реализация для секвенциального автомата, заданного следующим секвенциальным описанием (у реализуемого автомата функция выхода совпадает с функцией перехода) :

7.8.3. Нечеткие секвенциальные автоматы. Обобщим теперь понятие секвенциального автомата за счет введения в структуру секвенций нечетких временных кванторов, рассмотренных выше. Будем говорить, что нам задан секвенциальный автомат с нечетким входом, если секвенциальное задание автомата имеет вид [34];

При этом секвенция вида [- ifi

будет пониматься нами в следующем смысле; на интервале со степенью достоверности, определяете т

Sion квантором > функция ф

принимает единичное значение, с этой же степенью достоверности на этом интервале if) также принимает единичное значение. Вид кванторов

М * может быть различным для различных строк задания секвенциального описания. Если индекс К у квантора отсутствует, то это означает, что принимает единичное значение с достовер-

ностью    в любой момент физического времени.

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

Если индекс у квантора отсутствует, то это означает, что в любой момент времени автомат с достоверностью >| будет находиться в состоянии Sj.

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

Если указания на временные интервалы у кванторов отсутствуют, то это означает, что в любой момент времени автомат пере-

ходит в одно из указанных в правой части секвенций состояний с заданной достоверностью.

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

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

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

Отметим, что при практических расчетах кванторы >|* оцениваются некоторыми числовыми оценками. Вид этих оценок существенно зависит от конкретного вида задачи. Однако как показано в [4], существует довольно устойчивое понимание этих оценок у человека. Это позволяет, не слишком огрубляя результаты, переходить от качественного описания работы нечеткого автомата к описанию его функционирования с использованием числовых оценок кванторов. При этом в случае оценок нечетких кванторов конъюнкции и дизъюнкции событий соответствуют операции взятия минимума и максимума от этих оценок. В качестве примера проведем анализ временных процессов в автомате, представленном автоматным графом на рис. 7.6.

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

надлежности времени срабатывания элементов памяти интервалу t соответственно равны: fXi(i) = 0,5; (і2(і) = 0,9; fx,(0=l- Под временем срабатывания элемента памяти здесь подразумевается время перехода элемента из состояния О в состояние 1 или обратно. Предполагается, что эти времена одинаковы для одного

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

Как видно из графа рис. 7.6, переходы автомата связаны с изменением состояний одного или двух элеліентов памятп. Для переходов, связанных с изменением состояний двух элементов памяти, необходимо выбрать минимум оценки функции принадлежности для этих элементов. Таким образом, в данном автомате все переходы могут быть разделены на три группы: «выполнимые во всех случаях», «выполнимые в подавляющем большинстве случаев» и «выполнимые примерно в половине случаев». Если работу автомата описывать на языке секвенций, то секвенции, описывающие переходы двух последних групп, должны содержать размытые кванторы >|^ и соответственно. На рис. 7.6 эти кванторы приписаны соответствующим дугам. На графе не указаны переходы, которые должны быть добавлены в связи с неодновременным переключением элементов памяти.

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

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

На основании правил перехода от системы секвенций к графу, изложенных в [3], нетрудно получить граф автомата, представленный на рис. 7.7. Для этого необходимо иметь в виду, что

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

Из графа рис. 7.7 видно, что переходы, описываемые секвенциями левой части исходной системы (без кванторов), связаны с изменением состояния одного элемента памяти. В связп с чем работа автомата в этой части сомнений не вызывает. Рассмотрим пятую секвенцию исходной системы, описывающую нечеткие переходы. Эти переходы показаны на графе рис. 7.7 пунктиром.

Пусть появление входного слова 'if на автомат, находящийся в состоянии с кодом 010, вызывает изменение состояний двух элементов памяти и s,. Причем элемент Sj должен изменить свое состояние с 1 на О, а элемент s, — с О на 1. Поскольку элемент S, является более быстродействующим, в подавляющем большинстве случаев автомат перейдет в состояние с кодом 011. Этот переход справедливо взвешен квантором >|^. Переход в состояние с кодом 001, взвешенный квантором >{’, действительно будет иметь место лишь в редких случаях одновременного изменения состояний двух элементов памяти (случай переключения элемента памяти раньше элемента Sj мы исключаем).

Рассмотрим последнюю секвенцию системы. Появление входного слова а на автомат, находящийся в состоянии с кодом 100, вызовет изменение состояний всех трех элементов памяти. Причем элемент s, будет стремиться изменить свое состояние с 1 на О, а элементы Sj и Ss — с О на 1. По условиям быстродействия элементов памяти автомат в большинстве случаев перейдет в состояние с кодом 101. Отмеченные на графе рис. 7.7 переходы в состояния с кодами 001 и 010 будут выполняться довольно редко (преідполагается, что на быстродействие элементов памяти впешние условия и процессы старения влияют различным образом) и поэтому должны быть взвешены квантором (т. е. так, как указано на графе рис. 7.7, а не так, как в исходной системе секвенций).