Функциональное моделирование логических элементов на основе системы представления знаний SEMP-TAO
УДК 621.372
Ю.А. Загорулько, Г.В. Соколов
// Труды Международных конференций "Искусственные интеллектуальные системы" (IEEE AIS'02) и "Интеллектуальные САПР" (CAD-2003). Научное издание. - М.: Издательство физ.-мат. лит-ры, 2002.-609 с.
АННОТАЦИЯ
Работа посвящена разработке и анализу системы для обучения функциональному моделированию логических схем и элементов Старт-02 на основе интегрированной системы представления знаний Semp-TAO [Загорулько и др., 1996]. Прототипом системы Старт-02 послужила система Старт С90 [Соколов, 1990]. В Semp-TAO реализована концепция недоопределённых моделей [Нариньяни, 1986], что позволяет использовать метод недоопределённых вычислений для всестороннего моделирования задержек, заданных диапазоном значений (от ... до). Кроме того, применение Semp-TAO позволило усовершенствовать функциональные характеристики системы моделирования.
Abstract
The paper presents an approach to functional modeling of logical elements and circuits on the base of knowledge representation system (Semp-TAO). Start C90 system was a prototype of this modeling system (Start-02). The language of Semp-TAO has made it possible to improve qualitatively functional capabilities and simplify communication of a user (trainee) with the modeling system. In particular, a user can use the method of subdefinite computational model for modeling of delay defined by data interval, find optimal variants of circuits faster and more precisely, as well as make mutual understanding between users and programmers more easy. Examples procedures of elements under modeling that are realized in Semp-TAO system language are described. The modeling system is intended for training of students which study computer engineering.
Работа посвящена разработке и анализу системы функционального моделирования логических схем и элементов Старт-02 на основе интегрированной системы представления знаний Semp-TAO. Прототипом системы Старт-02 послужила система Старт С90[1]. Недостатки Старт-С90 проистекают из ограничений, присущих языку "C", на котором была реализована эта система. В Semp-TAO реализована концепция недоопределённых моделей (А.С. Нариньяни), что позволяет поставить задачу повышения функциональных возможностей Старт-02.. Например: использовать метод недоопределённых вычислений для всестороннего моделирования задержек, заданных диапазоном значений; быстрее и точнее находить оптимальные варианты схем; упростить исходную функциональную схему модели, служащую "языком" взаимопонимания между пользователем и программистом. Так как Старт-02 является средством обучения, основными требованиями к таким системам являются: минимальное время приобретения навыка работы с системой; прозрачность и ясность представления проекта; достаточная полнота функциональных возможностей системы.
Краткая характеристика системы моделирования Старт С90
Старт-С90 (прототип для Старт-02) является разработкой одного из авторов данной статьи [1]. Эта система предназначалась для обучения студентов цифровой технике при отсутствии у них навыков программирования. Эта проблема решалась путём программно-процедурного описания проекта, которое предполагает наличие библиотеки элементов (процедур, функций), из которых собирается модель схемы. Библиотека элементов ориентирована на символьное описание процесса преобразования сигналов в моделируемом устройстве. В процедурном языке предложения выполняются в том порядке, в котором они написаны, то есть требуется явное задание алгоритма исполнения программы модели. В состав библиотеки включены такие элементы как триггер, дешифратор, логические операции, общая шина, элемент задержки и др. Входные и выходные сигналы элементов могут принимать четыре значения (0, 1, неопределённое значение, бесконечное сопротивление). Сигналы могут быть единичные и векторные, заданной размерности n.
К недостаткам данной системы можно отнести ограничения, накладываемые языком реализации (C):
- необходимость явного указания в атрибутах вызова функций и процедур размерности (n) вектора сигналов (количество циклов обработки сигнала), манипулирование указателями (признак взятия адреса (&)) и др.;
- отсутствие вычислительного механизма для работы с интервальными данными для более адекватного моделирования задержек сигналов.
Кроме того, в данной системе отсутствуют средства для многооконного представления данных и манипулирования параметрами модели для быстрого изучения её свойств. Чтобы исключить выше указанные недостатки, авторами была предпринята разработка системы Старт-02 на основе Semp-TAO, как современной системы, предназначенной для создания экспертных систем и систем моделирования.
Краткая характеристика системы представления знаний Semp-TAO
Система Semp-TAO является одной из интегрированных программных систем, разработанных в РосНИИ ИИ и Институте Систем Информатики СО РАН [2]. В ней реализована концепция недоопределённых моделей, предложенная А.С. Нариньяни [3]. В системе интегрированы различные парадигмы программирования: логическая, объектно-ориентированная, функциональная, декларативная и программирование в ограничениях. Интегрированная система позволяет решать многоуровневые задачи в едином комплексе. Для задания модели такой предметной области как цифровая техника требуются и представления, и решения временных и пространственных задач разной степени иерархии.
Semp-TAO может работать как в статическом, так и в динамическом режиме моделирования. В статическом режиме жёсткая связь элементов и принцип монотонности изменения значений (допускающий лишь уточнение значений величин, но никак не их изменение) не позволяет перестраивать структуру модели в процессе работы программы. В то же время, системный подход к моделированию предполагает взаимно обратную связь воздействия изменений функций системы и внешней среды (желание пользователя) на изменение её структуры, и наоборот [4]. В Semp-TAO в динамическом режиме возможно прерывать ход моделирования, анализировать и выбирать различные альтернативные пути продолжения моделирования, изменяя функции и структуру модели с возможностью возврата в прерванную позицию.
Оболочка системы имеет стандартный вид (рис.1). Для моделирования есть потенциальная возможность создания многооконного пользовательского интерфейса.
Особенности языка Semp-TAO
В языке Semp-TAO [2] выделяются три основные группы типов данных – простые, составные и семантические.
Простыми типами являются числа (целые и вещественные), литеры, строки, атомы (неделимые строки) и т.п. Характерной особенностью языка является то, что значения простых типов могут быть недоопределенными, т.е. могут задаваться некоторой областью возможных значений (интервалом, перечислением). Составной тип – это кортеж, множество, структура.
К семантическим типам данных относятся объекты и бинарные отношения, из которых и строится семантическая сеть.
Язык включает в себя широкий спектр средств обработки знаний, таких как продукционные правила, процедуры, функции, операторы цикла и ветвления, итераторы forall и exist (forall x in Domain when [P(x)]: Q(x)). Итератор вырабатывает значение "истина", если на всех элементах x области значений Domain, удовлетворяющих предикату P(x), предикат Q(x) истинен. Предикаты P(x) и Q(x) – это логические выражения. P(x) может отсутствовать.
Наряду с операторами стандартного ввода/вывода в язык включены средства поддержки окон и графики, что позволяет создавать полноценные пользовательские интерфейсы.
Логическое моделирование схем средствами Semp-TAO
Разработка систем моделирования [5] есть непрерывный процесс. Старт-02 – это работа первого этапа на основе Semp-TAO. Этот этап включает в себя перевод библиотеки элементов на язык Semp-TAO, разработку средств моделирования задержек, заданных диапазоном значений, а также анализ полученных и предполагаемых в будущем преимуществ и недостатков.
На этом этапе работы методология построения алгоритма проекта по сравнению с системой Старт-С90 принципиально не изменилась. Представление модели (M) осуществляется в виде схемы операционных отношений, связывающих процессы с реализующими их процедурами.
M =<O, R, E>,
где O – объекты, R – отношения между объектами, E – среда моделирования (свойства Semp-TAO, способности обучаемого и обучающего). R включает в себя характеристические отношения ("иметь свойство", "состояние"), "причина-следствие", временные, пространственные и логические отношения.
Обучение студента сопровождается процессами анализа, оценки, прогнозирования и синтеза. Процессы анализа, оценки и прогнозирования сами по себе не изменяют значений результата моделирования, хотя они являются основой для процесса синтеза модели, который направлен на изменение значений свойств создаваемого объекта.
Формально взаимосвязь между предположением (G) обучаемого и фактическим следствием (S – результат моделирования) выражается через вероятность (P) влияния посылки на следствие [6].
для всех Gi (существует Sj | Rk (Gi, Sj, P)), Gi из G, Sj из S, 0 < P > 1,
где Rk – причинно-следственное отношение.
Достижение одного и того же состояния процесса (Pri) может осуществляться с помощью альтернативных процедур (Lj), реализующих процесс Pri [6].
для всех Pri (существует Lj | RI (Pri, Lj)), Pri из Pr, Lj из L, j = 1 … k,
где RI – инструментальное отношение (план процесса, библиотека процедур), Pr – множество процессов в моделируемой схеме, L – библиотека элементов.
Отсюда следует, что на усвоение материала обучаемым посредством моделирования влияют два параметра – вероятность (P) совпадения результата моделирования с предположением-посылкой и количество комбинаций альтернативных процедур (Ej), реализующих заданный процесс Pri.
Адаптация модели предметной области к инструментальным средствам моделирования заключается в установлении соответствия между множествами процессов (Pr) и комплексов проектных процедур (Lj).
Библиотека элементов
Библиотечные элементы выполнены в виде процедур и функций, которые строятся по модели конечного автомата:
Y = F (X, Z),
где Y – результат вычислений одного сигнала, F – вычислительная модель функции (функции переходов), X – входные данные, а Z – значения сигналов в предыдущем состоянии. Функции идеально подходят для символьного представления моделируемой схемы, так как в программе модели можно манипулировать функцией как отдельным сигналом, а на функциональной схеме – как отдельным элементом. Если входные данные (XV) или выходные (YV) элемента представляются вектором, то модель логического элемента выполняется в виде процедуры:
P (XV, Z, YV).
В теле самой процедуры могут быть использованы функции логических схем этой же библиотеки. Например, регистровая функция "разрешение" EnR (XV, E, YV) выполнена на основе функции "разрешение" для единичного сигнала – En (X, E), где E – управляющий сигнал "разрешение".
Ниже представлены модели функций и процедур для обеих сравниваемых систем в следующем порядке: функция элемента; представление функции в системе Старт-С90; представление в системе Старт-02 (Semp-TAO). В Старт-02 в атрибутах функций отсутствуют параметр n и знак взятия адреса (&), что упрощает представление модели.
"ИЛИ-НЕ": ilij(n,X,W) /* W – режим контроля */; IliN(XV) // Старт-02 Дешифратор: ndc(n,XV,YV,W); nDc(XV,YV). Триггер: ejc(D,C,&C_0,&Y,W); Ctg(D,C,C_0,Y).
Далее приводится фрагмент программы реализации функции IliN.
function IliN( inputs: tuple of integer (0..3)): integer (0..3)
begin var output: integer (0..3);
if (exist i in inputs: i=1) then output := 0;
elsif (forall i in inputs: i=0) then output := 1;
else WriteLn( "Ошибка – входы не 0..3");
end;
return output;
Работа с кортежами демонстрируется фрагментом программы счётчика на 4, выполненного на триггере со счётным входом (Sch).
var T1,T2 : LN := integer[0,0]; // где type LN = tuple of integer(0..3); type L = integer(0..3); var CC,NT : L; var C_1,Out_1,Out_2 : L:=0; var C_2 : L:= 1; ………………………………………… T1 := Sch (CC,C_1,Out_1); Out_1:=T1[1]; C_1:=T1[2]; // T1[1] – выход триггера NT:= N(T1[1]); // NT – инверсия сигнала T1, N – функция инверсии T2 := Sch (NT,C_2,Out_2); Out_2:=T2[1]; C_2:=T2[2]; NT:= N(T2[1]); ………………………………
Как видно из приведённых примеров, в программах на языке Semp-TAO вместо указателей и явного задания размерности вектора используются кортежи с неявным заданием его размерности. Определение размерности осуществляется с помощью функции вычисления мощности кортежа (#): while m <= #str loop…
Временное моделирование схем
Фактическое значение задержки элементов, как правило, имеет интервальное значение. Кроме того, эти величины зависят от направления смены состояний сигналов, что практически трудно учесть в модели вычислений задержек с помощью метода вычислений определённых данных. Наличие в системе Semp-TAO средств вычислений недоопределённых типов данных позволяет достичь более точного и адекватного моделирования задержек в схеме.
В системе Старт-С90 задержки задаются явно в атрибутах процедуры задержки delr(n,XV,T1,T0,TT,XV_), где T1 – значение задержки перехода из 0 в 1, T0 – из 1 в 0, а TT – текущее время (порядковый номер такта моделирования).
Система Semp-TAO позволяет организовать процесс моделирования задержек следующим образом. Модель строится по схеме вложенных циклов [Tm[Td]], то есть, каждый такт моделирования tm (отработка строки теста) содержит полный цикл Td отработки задержек в схеме. Такт td цикла Td может представлять собой как условную единицу задержки, так и физическую величину, например, 1 нсек. Количество тактов td в цикле Td должно гарантировать отработку всех задержек в схеме. Таким образом, время такта моделирования с отработкой задержек tmd определяется по формуле
tmd = tm + (n x td),
где n – количество тактов td в цикле Td.
Определение конкретной величины или диапазона величин задержки на выходе элемента от конкретного изменения его состояния осуществляется с помощью процедуры del (Y_,Y), где Y_ – предыдущее состояние сигнала.
function del( D_0,D: integer (0..20)): integer(0..20) // Функция "Таблица задержек сигнала в условных // единицах" begin var out: integer (0..20); if (D = D_0) then return 0; elsif ((D_0 = 1) & (D = 0)) then out:= 2..5; return out; // (2..5) – задержка при смене "1" в "0". elsif ((D_0 = 0) & (D = 1)) then out:=5..10; return out; elsif ((D_0 = 2) & (D = 1)) then out:=0..10; return out; ……………………………………………………………… elsif ((D_0 = 3) & (D = 2)) then out:=0..8; return out; else out:=0; return out; end; end;
В системе Semp-TAO имеются операции вычислений по нижнему (Low) и по верхнему (High) значению, что позволяет моделировать время задержки во всём диапазоне значений. Ниже приведены фрагменты программы моделирования задержек в счётчике по выше описанной методике вложенных циклов.
var T1z,T2z,T3z : LN := integer[0,0]; // Выходы счётчика после задержки
// циклы итераций прохода по тесту.
while ~ EndOfFile( InpFile ) loop // Такты моделирования – tm цикла Tm
var str: string := ReadLnFile( InpFile );
while z <= 20 loop // n – 20 тактов задержки – td цикла Td
T1 := Sch (CC,C_1,Out_1); // Т1 – Кортеж из двух составляющих: выхода
// триггера T1[1] и значения счётного входа T1[2], Sch- делитель на 2
T1zad:= Low(del(Out_1,T1[1])); // Low – минимальное значение
if (T1zad!= 0) then
if (z = T1zad) then z1 := z;
T1z[1] := T1[1]; // Выход Т1 после задержки
T1z[2] := T1[2]; Out_1:=T1z[1]; C_1:=T1z[2];
NT1:= N(T1z[1]); // инверсия выхода триггера T1
end;
else
Out_1:=T1[1]; C_1:=T1[2]; NT1:=N(T1[1]);
end;
T2 := Sch (NT1,C_2,Out_2);
T2zad:=High (del (Out_2,T2[1])); // High – максимум
if (T2zad != 0) then
if (z = (T2zad + z1)) then z2 := z;
На рис.2 приведены фрагменты результата работы этой программы, где С – счётный вход (тест), T1z, Т2z, Т3z – значение выходов трёх триггеров счётчика. На рис. 3 показано два триггера).
При обучении основам цифровой техники пользователь может видоизменять тесты и наблюдать результаты выполнения процедур, то есть наглядно изучать работу элементов, схем.
Наглядность и простота исходной функциональной модели схемы счётчика на 4 с задержками демонстрируется на рис.3. Такая схема одинаково хорошо "читается" как схемотехником, так и программистом.
Заключение
Система моделирования Старт-02 предназначена для использования в учебном процессе. Её реализация на основе системы Semp-TAO позволило на первом этапе разработки упростить исходное представление моделируемой схемы и расширить функциональные возможности системы , в частности: автоматизировать работу пользователя с параметризацией циклов (векторных сигналов); использовать метод недоопределённых вычислений для всестороннего моделирования задержек, заданных диапазоном значений. Строить многооконный интерфейс; быстрее и точнее находить оптимальные варианты схем благодаря расширенным возможностям по временному моделированию; сократить время анализа текущих проектных ситуаций, снизить уровень требований к профессиональной подготовке пользователей и облегчить взаимопонимание пользователей и программистов.
Литература
- Соколов Г.В. Имитационная система функционального проектирования и моделирования «Старт» С90// Сб. Методы теоретического и системного программирования/ Под ред. В.Е. Котова. – Новосибирск, 1991.
- Загорулько Ю.А., Попов И.Г. Представление знаний в интегрированной технологической среде Semp-TAO // Сб. Проблемы представления и обработки не полностью определенных знаний/ – М. – Новосибирск, RRIAI, 1996.
- Нариньяни А.С. Недоопределённость в системах представления и обработки знаний // Изв. АН СССР. Техн. кибернетика. – 1986, N5. – С. 3-28.
- Соколов Г.В. Роль метазнаний в системах поиска решений. // Интеллектуальные САПР/ Материалы Международной научно-технической конференции и молодежной научной конференции "Интеллектуальные САПР". – Таганрог: ТРТУ, 2000. – N2 (16). –391с.
- Иоффе М.И. Диагностирование логических схем. Алгоритмы моделирования и автоматического синтеза теста / М.: Наука, 1989, 158 с.
- Анисимов В.И. и др. Смысловая модель предметной области автоматизированного проектирования РЭА. // Управляющие машины и системы, 1990, N1, стр. 82-88.