Системное автоматизированное проектирование
ЛЕКЦИЯ №1
Тема: "Системы автоматизированного проектирования и процесс
разработки радиоэлектронной аппаратуры"
ЦЕЛЬ ЗАНЯТИЯ:
1. Ознакомить с основными понятиями системного автоматизированного проектирования. Определить место сис-тем автоматизированного проектирования в процессе проектирования.
2. Изучить структуру системы автоматизированного обеспечения.
Время: 2 часа
Литература: Бутаков Е.А. и др. Обработка изображений на ЭВМ. М.: Радио и связь, 1987, стр. 119-124.
ОБЩИЕ СВЕДЕНИЯ О ПРОЕКТИРОВАНИИ
Предварительно остановимся на рассмотрении ряда понятий.
СИСТЕМА - целостное образование, состоящее из взаимосвязанных (взаимодействующих) компонент, (элементов, частей) и обладающее свойствами, не сводимыми к свойствам этих компонент и не выводимыми из них.
В приведенном определении зафиксировано основное свойство системы - ее целостность, единство, достигаемое через посредство определенных взаимосвязей (взаимодействий) элементов системы и проявляющееся в возникновении новых свойств, которыми элементы системы не обладают. Данное определение включает наиболее характерные особен-ности концепции системы.
Вместе с тем необходимо представлять, что реальные системы существуют в пространстве и во времени и следова-тельно, взаимодействуют с окружающей их средой и характеризуются теми или иными переменными во времени вели-чинами.
Важным шагом на пути от вербального к формальному определению системы является определение понятия моде-ли системы.
МОДЕЛЬ - (некоторой исходной системы) система, в которой отражаются по определенным законам те или иные стороны исходной системы.
Среди различных способов моделирования важнейшее место занимает моделирование с помощью средств матема-тики - математическое моделирование.
Формальное определение системы по существу сводится к определению соответствующей математической модели.
В основу построения математических моделей систем может быть положено следующее определение системы:
СИСТЕМА - определяется заданием некоторой совокупности базисных множеств (элементов, компонент системы), связанных между собой рядом отношений, удовлетворяющих тем или иным правилам (аксиомам) сочетания как элемен-тов множеств , так и самих отношений.
Последнее определение содержит необходимую основу для формализации. В простейших случаях это определение описывает систему как одно или несколько взаимосвязанных отношений, заданных на одном или нескольких множествах. В то же время данное определение допускает возможность нескольких вариантов таких представлений для одной и той же системы, а также использование их композиции. Последнее имеет место в случае необходимости многоаспектного мо-делирования системы.
ПРОЕКТИРОВАНИЕ - комплекс работ по исследованию, расчетам и конструированию нового изделия или нового процесса.
В основе проектирования - первичное описание - техническое задание.
Проектирование называют АВТОМАТИЗИРОВАННЫМ, если осуществляется преобразование первичного описа-ния при взаимодействии человека с ЭВМ, и автоматическим, если все преобразования выполняются без вмешательст-ва человека только с использованием ЭВМ.
СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ - организационно-техническая система, представ-ляющая собой подразделения проектной организации и комплекс средств автоматизированного проектирования.
Автоматизация приводит к существенному изменению методов проектирования.
Вместе с тем, сохраняются многие положения и принципы традиционного проектирования, такие как:
необходимость блочно-иерархического подхода,
деление процесса проектирования на этапы,
деление на уровни представления об объектах.
ВЗАИМОДЕЙСТВИЕ РАЗРАБОТЧИКОВ РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ С СИСТЕМОЙ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
Проектирование изделий радиоэлектронной аппаратуры представляет собой многоэтапный процесс (итеративный). В ходе проектирования последовательно уточняется и детализируется описание будущего изделия. Этот процесс пред-полагает наличие многих уровней описания. На рис.1 изображен процесс проектирования в виде совокупности основ-ных этапов и переходов между ними, показаны основные виды документации , получаемые при выполнении этапов.
Например, эскизный проект является результатом эскизного проектирования. С другой стороны, эскизный проект служит исходным документом для технического проектирования.
Переходы от одних этапов проектирования к другим в направлении сверху вниз естественны и соответствуют нормаль-ному ходу. Переходы в противоположных направлениях возникают, когда на последующих стадиях проектирования вы-является невозможность практической реализации решений, принятых на предшествующих этапах. Это заставляет проектировщиков пересматривать ранее принятые решения. Иногда ошибки проявляются на этапах изготовления серийной продукции или даже в ходе эксплуатации.
Последовательность прохождения этапов разработки изделия, цели и задачи, стоящие перед проектировщиками на отдельных этапах, состав проектной документации и требования к ней регламентированы соответствующими ГОСТами.
Кратко охарактеризуем основные этапы проектирования.
ПОДГОТОВИТЕЛЬНЫЙ ЭТАП.
Основная задача - изучение назначения изделия, условий эксплуатации и производств, на которых предполагается его изготовление. Цель этапа - разработка технического задания (ТЗ), в котором содержится информация о назначении , основных технических характеристиках, условиях эксплуатации, транспортировки и хранения.
ЭСКИЗНОЕ ПРОЕКТИРОВАНИЕ.
Основная задача - определение возможности разработки изделия в соответствии требованиям ТЗ. При этом опреде-ляют техническую основу изделия (физические элементы и детали), ориентировочную оценку состава и количест-ва оборудования, разрабатывают структуру, определяют технические характеристики изделия и устройств, входящих в его состав.
При этом может выявиться невозможность построения изделия, отвечающего требованиям ТЗ. В этом случае требуется корректировка ТЗ с последующим его утверждением заказчиком, либо дальнейшая разработка прекращает-ся.
ТЕХНИЧЕСКОЕ ПРОЕКТИРОВАНИЕ
Задачи :
- подробная разработка принципа работы изделия и всех его составных блоков;
- уточнение технических характеристик;
- разработка конструкции блоков, узлов и всего изделия;
- получение конструкторских характеристик;
- согласование взаимодействия всех составных частей изделия;
- разработка технологии их изготовления;
- определение технологии сборки и наладки, методики и программных испытаний.
В результате должно быть подготовлено производство опытного образца.
РАБОЧЕЕ ПРОЕКТИРОВАНИЕ
Основная задача - разработка технологической оснастки и оборудования для серийного выпуска изделия.
Внедрение систем автоматизированного проектирования (САПР) не изменяет сути процесса проектирования. Тем не менее, характер деятельности разработчика с внедрением САПР существенно меняется, так как разработка изделия в автоматизированном варианте предполагает согласованное взаимодействие оператора и ЭВМ. Это обеспечивает суще-ственное повышение производительности труда и повышение качества проекта.
В процессе автоматизированного проектирования на оператора возлагаются творческие функции. Как правило, это связано с выбором варианта решения, определения структуры, метода расчета и др. Эти функции трудно формализо-вать. Здесь опыт и талант конструктора, инженера определяют конечный результат.
ЭВМ поручают рутинную работу. Перечислим ее основные виды:
- хранение и накопление в машинном архиве сведений, необходимых разработчику;
- поиск и выдача информационных справок по запросам пользователя (типовые решения, характеристики узлов, рекомендации по применению, сведения об уровне запасов комплектующих материалов и др.);
- обеспечение редактирования текстовой конструкторской документации, создаваемой инженером;
- автоматическое вычерчивание графической документации (чертежи деталей, схемы электрические и др.);
- решение некоторых частных, хорошо алгоритмизированных задач, которые характерны для автоматизирован-ного проектирования определенного класса изделий. Примененительно к разработке радиоэлектронной аппаратуры хо-рошо алгоритмизированными задачами являются следующие:
- моделирование поведения того или иного узла по описанию его принципиальной электрической схемы при заданном входном воздействии,
- трассировка соединений на этапе конструирования платы печатного монтажа,
- расчет тепловых режимов узлов аппаратуры,
- построение последовательности обхода точек сверления платы и др.
..ПРОЦЕСС ПРОЕКТИРОВАНИЯ ИЗДЕЛИЙ ЭЛЕКТРОННОЙ ТЕХНИКИ
уровней),
- выделения аспектов описания объекта проектирования.
Уровни абстрагирования И РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ
Рассмотрим несколько подвопросов.
1. Уровни абстрагирования и аспекты описаний проектируемых объектов.
Большинство видов электронной техники и радиоэлектронной аппаратуры, а также большие и сверхбольшие инте-гральные схемы относятся к сложным системам.
Дадим определение сложной системы.
СЛОЖНАЯ СИСТЕМА - система, обладающая, по крайней мере, одним из перечисленных признаков:
а) допускает разбиение на подсистемы, изучение каждой из которых, с учетом влияния других подсистем в рам-ках поставленной задачи, имеет содержательный характер;
б) функционирует в условиях существенной неопределенности и воздействие среды на нее обусловливает слу-чайный характер изменения ее параметров или структуры;
в) осуществляет целенаправленный выбор своего поведения.
Процесс их проектирования характеризуется высокой размерностью решаемых задач, наличием большого числа возможных вариантов, необходимостью учета разнообразных факторов.
В основе проектирования сложных систем блочно-иерархический подход. Сущность блочно-иерархического состо-ит в уменьшении сложности решаемой проектной задачи. Это осуществляется за счет:
- выделения ряда уровней абстрагирования (иерархических различаются степенью детализации представлений об объекте.
Этапы нисходящего проектирования:
Компоненты объекта, рассматриваемые как элементы на некотором уровне с номером k, описываются как подсис-темы на соседнем уровне с номером k+1.
Относительно аспектов описания объекта.
Аспекты могут быть:
- функциональные,
- конструкторские,
- технологические.
а) Функциональные аспекты можно разделить на:
- системный,
- функционально- логический,
- схемотехнический,
- компонентный.
На системном уровне в качестве систем выделяют комплексы. Примерами комплексов могут быть ЭВМ, радиоло-кационная станция. В качестве элементов выделяют блоки (устройства) аппаратуры процессор, модем, передатчик.
На функционально-логическом уровне эти блоки рассматривают как системы, состоящие из элементов. Элемента-ми являются функциональные узлы - счетчики, дешифраторы, отдельные триггеры, вентили, усилители, модуляторы и др.
На схемотехническом уровне функциональные узлы описываются как системы, состоящие из элементов радио-электронных схем - транзисторов, конденсаторов, резисторов и др.
На компонентном уровне рассматриваются процессы, которые имеют место в схемных компонентах.
б) Конструкторскому аспекту присуща своя иерархия компонент. Она включает различные уровни описания рам, стоек, панелей, типовых элементов замены, дискретных компонент и микросхем, топологических фрагментов функциональных ячеек и отдельных компонент в кристаллах интегральных микросхем.
2. Операции, процедуры и этапы проектирования.
Процесс проектирования делится на этапы.
ЭТАП ПРОЕКТИРОВАНИЯ - условно выделенная часть процесса проектирования, состоящая из одной или не-скольких проектных процедур. Обычно этап включает процедуры, которые связаны с получением описания в рамках одного аспекта и одного или нескольких уровней абстрагирования. Иногда в процессе проектирования выделяют ту или иную последовательность процедур под названием "маршрут проектирования".
Этапы, в свою очередь, делятся на процедуры и операции.
ПРОЦЕДУРА - формализованная совокупность действий, выполнение которых заканчивается проектным решени-ем.
ПРОЕКТНОЕ РЕШЕНИЕ - промежуточное или окончательное описание объекта проектирования, необходимое и достаточное для рассмотрения и определения дальнейшего направления или окончательного проектирования.
При проектировании возможны различные последовательности выполнения процедур и этапов.
Различают два способа проектирования (два типа маршрутов):
- восходящее проектирование,
- нисходящее проектирование.
Восходящее проектирование (снизу-вверх) имеет место, если проектируются типовые объекты, предназначенные для использования в качестве элементов во многих объектах на более высоких уровнях иерархии (например, серийные микросхемы, стандартные ячейки матричных больших интегральных схем).
Нисходящее проектирование охватывает те уровни, на которых проектируются объекты, ориентированные на ис-пользование в качестве элементов в одной конкретной системе.
Проектированию свойственен итерационный характер. При этом приближение к окончательному варианту осуще-ствляется путем многократного выполнения одной и той же последовательности процедур с корректировкой исходных данных. Итерации могут охватывать различные части проектирования, включающие как несколько операций, так и не-сколько этапов.
ПРИМЕР 1.
- системотехническое проектирование (анализ тактико-технических требований на проектируемый комплекс, определение основных принципов функционирования, разработка структурных схем);
- схемотехническое проектирование ( разработка функциональных и принципиальных схем);
- конструкторское проектирование ( выбор формы, компоновка и размещение конструктивов, трассировка межсоединений, изготовление конструкторской документации);
- технологическое проектирование ( разработка маршрутной и операционной технологии, определение техноло-гической базы).
ПРИМЕР 2.
Этапы восходящего проектирования БИС:
- приборно-технологическое проектирование (выбор базовой технологии, выбор топологии компонентов, рас-чет диффузионного профиля);
- схемотехническое проектирование ( синтез принципиальной электрической схемы, оптимизация параметров элементов, статистический анализ применительно к типовым ячейкам БИС);
- функционально-логическое проектирование (синтез комбинационных схем, реализация памяти, синтез контро-лирующих и диагностических тестов);
- конструкторско-топологическое проектирование (размещение элементов, трассировка меж- соединений, про-верка соответствия топологической и электрической схем , расслоение, вычерчивание послойной технологии).
3. Классификация параметров проектируемых объектов.
В описаниях проектируемых объектов фигурируют переменные и их параметры. Среди переменных выделяют:
- фазовые переменные - характеризуют физическое или информационное состояние объекта.
Параметры разделяют на ряд групп. К их числу можно отнести следующие:
- внешние параметры - характеризуют свойства внешней по отношению к исследуемому объекту Сравнение нескольких полиномиальных и экспоненциальных функций
Таблица 1 позволяет сравнить скорости роста нескольких типичных среды;
Полиномиальные алгоритмы и труднорешаемые задачи
Разные алгоритмы имеют разную временную сложность и выяснение того, какие алгоритмы достаточно эффективны и какие совершенно не эффективны будет всегда зависеть от конкретной ситуации. Для решения этой задачи предлагается следующий подход - вводятся понятия:
•полиномиальный алгоритм;
•экспоненциальный алгоритм.
Полиномиальный алгоритм (полиномиальной временной сложности) - это алгоритм, временная сложность которого определяется выражением O[p(n)], где p(n) - полиномиальная функция, n - входная длина.
Алгоритм, временная сложность которого не поддается такой оценке называется экспоненциальным.
Различие между типичных полиномиаль-ными и экспоненциаль-ными алгоритмами про-является более убеди-тельно, если проанализи-ровать влияние увеличе-ния быстродействия ЭВМ на время работы алго-ритма. Таблица 2 показы-вает, насколько увеличит-ся размер задач, решае-мой за 1 час, если быст-родействие возрастет в 100 и 1000 раз. Видно, что для функции 2n увеличе-ние скорости вычислений в 1000 раз приводит лишь к тому, что размер зада-чи, решаемой на ней за 1 час возрастет на 10.
Выделено 2 класса трудно решаемости:
1.Для отыскания решения требуется экспоненциальное время.
2.Искомое решение настолько велико, что не может быть представлено в виде выражение, длина которого ограни-чена некоторым полиномом. Эти задачи в курсе рассматриваться не будут.
Первые результаты о трудно решаемых задачах были получены Тьюрингом. Он доказал, что некоторые за-дачи “неразрешимы” в том смысле, что вообще не существует алгоритма их решения. Некоторые задачи по теории ав-томатов, теории формальных языков и математической логики являются трудно решаемыми.
NP-полная задача - это задача, к которой сводится за полиномиальной время любая задача из класса NP-задач. Фундаментальные исследования и теорию NP-задач разработал С.Кук в 1971 году. Им определено понятие своди-мости за полиномиальное время. Если одна задача сводится за полиномиальное время к другой, то любой полиномиаль-ный алгоритм - решение другой задачи может быть превращен в полиномиальный алгоритм первой задачи.
Выделен класс задач распознавания свойств, которые могут быть решены за полиномиальное время на не-детерминированном вычислительном устройстве. Доказано, что любая задача из класса NP-задач может быть сведена к задаче выполнимой за полиномиальное время.
Существуют 6 основных классов NP-полных задач:
1. Задачи выполнимости.
2. Трехмерное сочетание.
3. Вершинное покрытие.
4. Поиск клики.
5. Гамильтонов цикл.
6. Разбиение.
- внутренние параметры - характеризуют свойства элементов ;
- выходные параметры - характеризуют свойства систем;
- ограничения выходных параметров.
ПРИМЕР 3.
Применительно к операционному усилителю:
а) переменные
- фазовые переменные - напряжение и токи всех ветвей (рассматриваются как функции времени или частоты);
б) параметры
- внешние параметры - напряжения источников питания, параметры входных сигналов и нагрузки, температура окружающей среды;
- внутренние параметры - номиналы резисторов, барьерные емкости и тепловые токи переходов в транзисторах, емкости конденсаторов;
- выходные параметры - коэффициент усиления на средних частотах, полоса пропускания, потребляемая мощ-ность, динамический диапазон;
- ограничения - верхние границы допустимых значений коэффициентов усиления, полосы пропускания, дина-мического диапазона.
Применительно к вычислительной системе:
а) переменные
- фазовые переменные - состояния отдельных устройств;
б) параметры
- внешние параметры - параметры входных источников заявок;
- внутренние параметры - емкости запоминающих устройств, быстродействие процессоров, число каналов;
- выходные параметры - производительность системы, коэффициент загрузки оборудования, вероятность реше-ния поступающих задач, средние длины очередей заявок на обслуживание;
- ограничения - нижние границы допустимых диапазонов значений производительности, коэффициентов загруз-ки оборудования, вероятности обслуживания заявок.
При блочно-иерархическом подходе внутренние параметры k -го уровня являются выходными параметры (k+1) -го уровня. При многоаспектном рассмотрении систем, включающих физически разнородные подсистемы, роль внешних переменных для данной подсистемы играют фазовые переменные других подсистем. Они влияют на рассматриваемую подсистему.
Внутренние параметры являются случайными величинами из-за разброса параметров комплектующих изделий, материалов и нестабильности условий изговления. Выходные параметры также имеют случайный характер следствие случайных значений внутренних параметров.
Задачи многовариантного анализа заключаются в определении изменений вектора Y при заданных изменениях век-торов X и Q.
К типовым процедурам многовариантного анализа относятся следующие:
- анализ чувствительности - оценка влияния внутренних и внешних параметров на выходные. При этом осущест-вляется расчет коэффициентов чувствительности;
- статистический анализ - оценка закона и (или) числовых характеристик распределения вектора Y при заданных статистических сведениях о распределении случайного вектора Х.
При синтезе выделяют процедуры параметрического и структурного синтеза. При параметрическом синтезе опре-деляются числовые значения параметров элементов при заданных структуре объекта и диапазоне возможного измене-ния внешних переменных. Если при этом ставится задача достижения экстремума некоторой целевой функции, то вы-полняется процедура оптимизации.
При оптимизации параметров определяются номинальные значения внутренних параметров, при оптимизации до-пусков - дополнительно допуски на внутренние параметры, при оптимизации технических требований решается задача оптимального назначения технических требований к выходным параметрам объекта.
В большинстве маршрутов проектирования процедуры синтеза и анализа находятся во взаимосвязи. На рис. 2 пока-зана схема типового маршрута проектирования.
После формирования ТЗ (исходного описания объекта проектирования) и выбора (синтеза) первоначального вари-анта структуры и значений параметров элементов следует анализ объекта. Если при анализе необходимо установить со-ответствие синтезированной структуры исходному описанию, то анализ называют верификацией проекта.
Различают верификацию параметрическую и структурную. При параметрической верификации устанавливается соответствие областей работоспособности двух сравниваемых вариантов объекта. Примером параметрической верифи-кации является процедура установления работоспособности типового элемента замены (ТЭЗа). При структурной вери-фикации проверяется соответствие структур объекта, представленных двумя различными описаниями. Пример струк-турной верификации - установление изоморфизма графов, которые описывают топологию и принципиальную электри-ческую схему типового элемента замены.
Обычно по результатам анализа принимается решение относительно улучшения первоначального варианта. Это выполняется путем изменения числовых значений параметров элементов. Данный процесс можно формализовать и представить как решение задачи параметрической оптимизации.
Если после завершения оптимизации требования ТЗ не выполнены, то принимается решение на изменение структу-ры. После этого осуществляется указанная последовательность операций.
Если не удается получить удовлетворительные результаты, ставится вопрос относительно коррекции ТЗ.
Полный и тщательный анализ требует больших материальных и временных затрат. Поэтому на первых итерациях в маршруте, показанном на рис.2, выполняют упрощенный анализ.
Использование сложных моделей, проведение параметрической верификации и всестороннего многовариантного анализа целесообразно лишь на завершающих итерациях.
Для функционального проектирования характерны большие затраты на анализ. Примерами подобных задач являют-ся такие как определения состава устройств вычислительной системы и способов их взаимодействия или задач разработки принципиальных электрических схем. Для этих задач обычно применяют эвристические способы синтеза структуры с перебором небольшого числа вариантов. Основные усилия затрачиваются на выполнение многовариантно-го анализа и оптимизации.
Если удается организовать приближенную оценку вариантов структуры на основе легко проверяемых критериев, то возможен просмотр большого числа вариантов структуры. Это дает возможность формализовать процесс решения за-дачи синтеза.
С подобным сталкиваются при решении коммутационно-монтажных задач конструкторского проектирования и за-дач функционально-логического проектирования комбинационных схем цифровой автоматики.
СТРУКТУРА САПР
Подсистемы САПР
проектирующих подсистем.
- подсистема проектирования деталей и сборочных единиц,
- подсистема проектирования топологии БИС ,
- подсистема технологического проектирования.
Примеры обслуживающих подсистем:
- подсистема графического отображения объектов проектирования,
- подсистема документирования,
- подсистема информационного поиска.
В зависимости от отношения к объекту проектирования проектирующие подсистемы делят на:
- объектно-ориентированные,- объектно-независимые.
В Выделяют подсистемы проектирующие и обслуживающие. Проектирующие подсистемы выполняют проектные процедуры и операции. Обслуживающие подсистемы предназначены для поддержания работоспособности объектно-ориентированных подсистемах выполняются процедуры и операции, непосредственно связанные с конкретным типом объектов проектирования; в объектно-независимых - унифицированные процедуры и операции.
Виды обеспечения САПР
В САПР выделяют следующие виды обеспечения:
- методическое,
- математическое,
- программное,
- техническое,
- лингвистическое,
- информационное,
- организационное.
Методическое обеспечение - документы , в которых определены состав, правила отбора и эксплуатации средств автоматизации проектирования.
Математическое обеспечение - совокупность математических методов и моделей, необходимых для выполнения процесса автоматизированного проектирования.
Программное обеспечение - совокупность программ, представленных в заданной форме, вместе с программной до-кументацией.
Техническое обеспечение - совокупность взаимосвязанных и взаимодействующих технических средств для ввода, хранения, переработки, передачи программ и данных, организации общения оператора с ЭВМ , изготовления проект-ной документации.
Информационное обеспечение - совокупность представленных в заданной форме сведений, необходимых для вы-полнения автоматизированного проектирования, в том числе описания стандартных проектных процедур, типовых проектных решений, типовых элементов, комплектующих изделий, материалов и др.
Организационное обеспечение - совокупность документов, определяющих состав проектной организации и ее подразделений, их функции, связи между ними и комплексом средств автоматизации.
Уровни САПР
Техническое обеспечение современных САПР имеет иерархическую структуру. Принято выделять следующие уровни:
- центральный вычислительный комплекс (ЦВК ),
- автоматизированные рабочие места ( АРМ ),
- комплекс периферийного программно-управляющего оборудования.
Центральный вычислительный комплекс предназначен для решения сложных задач проектирования. Представляет собой ЭВМ средней или высокой производительности с типовым набором периферийных устройств. Возможно расши-рение этого набора некоторыми средствами обработки графической информации. Для повышения производительно-сти в ЦВК могут использоваться многопроцессорные или многомашинные комплексы.
АРМы предназначены для решения сравнительно несложных задач и организации эффективного общения пользо-вателя САПР с комплексом технических средств. Включает в свой состав мини-ЭВМ и (или) микро-ЭВМ , графические и символьные дисплеи, координатосъемщики, устройства символьного и графического документирования и другие с со-ответствующим базовым и прикладным программным обеспечением. Для некоторых АРМ характерен интерактивный режим работы с обработкой графической информации.
Комплекс периферийного программно-управляющего оборудования предназначен для получения конструкторско-технологической документации и управляющих программ на машинных носителях для исполнительных технологических автоматов. В его составе исполнительное программно-управляющее оборудование , средства диалогового взаимодейст-вия. В составе ЭВМ с большим объемом внешней памяти. Подобные комплексы обычно называют технологическими. На данном оборудовании решаются задачи редактирования, тиражирования, архивного сопровождения документации и др.
Наличие указанных уровней приводит к соответствующей структуре программного и информационного обеспече-ния САПР. В результате уровни ЦВК, АРМ и ТК , первоначально выделяемые как уровни технического обеспечения, становятся уровнями САПР.
Существующие САПР делятся на одно-, двух- и трехуровневые. В одноуровневых САПР, построенных на основе ЦВК, выполняются процедуры, характеризующиеся высокой трудоемкостью вычислений при сравнительно малых объ-емах исходных данных. В одноуровневых САПР на основе АРМ выполняются процедуры, в которых объемы вычисле-ний и выпускаемой документации сравнительно невелики. В одноуровневых технологических комплексах содержание проектной документации определяется в результате неавтоматизированного проектирования, а изготовление ее авто-матизировано. При этом объем выпускаемой документации может быть большим.
В двухуровневых САПР возможны сочетания ЦВК-АРМ, ЦВК-ТК, АРМ-ТК.
В наибольшей степени возможности автоматизированного проектирования сложных объектов реализуются в трех-уровневых САПР, включающих ЦВК , АРМы и ТК.
Связь с гибким автоматизированным производством.
Автоматизированное проектирование изделий заканчивается изготовлением конструкторской документации и управляющих программ на машинных носителях. На завершающих этапах проектирования вносятся технологические дополнения и коррекции. Далее изготавливается пробный образец. После его анализа осуществляется аттестация проек-та. Это обеспечивается на основе введения автоматизированных производственных линий в состав технологического комплекса.
Аттестованные машинные носители с управляющими программами в дальнейшем копируются. На их основе вы-полняется перестройка исполнительного оборудования на изготовление другого изделия. Отмеченное является одним из основных условий реализации гибкого автоматизированного производства.
ВЫВОДЫ:
1. Рассмотрены основные этапы процесса проектирования радиоэлектронной аппаратуры. Показана необходимость автоматизации процессов проектирования.
2. Определены понятие системы автоматизированного проектирования, ее назначение, структура, связь с гибким автоматизированным производствам.
ЛЕКЦИЯ №2
Тема: “Вычислительные сети и АРМы”
НЕОБХОДИМОСТЬ СОЗДАНИЯ
Территориальное разнесение отдельных ЭВМ и комплексов САПР вызывает необходимость включения в состав технических средств аппаратуры сопряжения, передачи данных и телеобработки. При этом технические средства круп-ных САПР структурно объединяются в вычислительные сети. Преимущества организации вычислительных сетей САПР заключаются в следующем:
1 . Пользователи, работающие на аппаратуре в конкретном подразделении предприятия, получают доступ к базам данных и программным средствам, которые имеются в других территориально разнесенных узлах вычислительной сети. Это расширяет функциональные возможности САПР.
2. Появляется возможность оптимального распределения нагрузки между различными ЭВМ, а также возможность предоставления конкретному пользователю в случае необходимости значительных вычислительных ресурсов.
3. Повышается надежность функционирования технических средств САПР.
КЛАССИФИКАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ
Вычислительные сети САПР классифицируются по ряду признаков. В таблице 2 представлена эта классификация.
Признак классификации
вычислительных сетейТип связейПримечание
Топология
связейРадиальная (звездообразная)
Кольцевая
Радиально-кольцевая
Распределенная (децентрализо-ванная)Обычные двухуровневые САПР, в которых имеется центральный
вычислительный комплекс и несколько АРМов
Состав средств передачи данныхОднороднаяСостоит из программно-совместимых ЭВМ. Способ передачи
данныхС некоммутируемыми каналами
С коммутацией каналов
С коммутацией сообщений
С коммутацией пакетов
Со смешанной коммутацией
В сеансах связи образуются транзит-ные каналы между связываемыми узлами сети
Поэтапная передача сообщений через центры коммутации сообщений
Поэтапная передача пакетов информации определенной длины
Сочетание коммутации каналов сообщений, пакетов
Способ управленияЦентрализованная
ДецентрализованнаяУправление потоками данных осуществляется центральным узлом связи
Управление потоками данных распределено по узлам сети
Удаленность узловЛокальная
ДистанционнаяРасстояния между узлами ог-раничены заданной величиной L
Расстояния превышают вели-чину L
Устройства телеобработки, сопряжения и передачи данных
Эти устройства предназначены для организации связи с удаленными рабочими местами и для межмашинного об-мена данными в многоуровневых и сетевых САПР. Различают системы связи (телефонные и телеграфные каналы, релей-ные и кабельные линии), мультиплексоры передачи данных (МПД), аппаратуру передачи данных(АПД), абонентские пункты (АП) и интерфейсы (И).
устройства:
- КЭВМ - коллективная ЭВМ,
- ПК - персональный компьютер,
Мультиплексор передачи данных подключается к мультиплексному каналу ввода-вывода через стандартный интер-фейс и управляет передачей и частичной обработкой информации от ЭВМ на абонентские пункты и другие ЭВМ. Воз-можно снижение нагрузки на центральный процессор ЭВМ, если обработка выполняется частично в МПД. В этом слу-чае он ставится процессором телеобработки данных (процессором передачи данных).
Аппаратура передачи данных обеспечивает сопряжение мультиплексоров передачи данных и абонентских пунктов с каналами связи. Абонентские пункты передают ЭВМ и принимают от нее информацию.
Если абонентские пункты проводят предварительную обработку получаемых и передаваемых данных, их называют "интеллектуальными" абонентскими пунктами.
Аппаратура передачи данных включает следующие устройства:
- модемы и устройства преобразования сигналов,
- вызывные устройства для коммутируемых линий связи,
- устройства защиты от ошибок.
Модем (устройство модуляции и демодуляции) преобразует двоичные сигналы от мультиплексора или абонентско-го пункта в модулированные сигналы на несущей частоте для их передачи по линиям связи, а при приеме осуществ-ляют обратное преобразование (демодуляцию).
Абонентский пункт состоит из одного или нескольких периферийных устройств со специальным устройством управления. Устройство управления обеспечивает работу периферийных устройств, как автономную так и под управле-нием ЭВМ. Интерфейсы согласуют работу отдельных блоков по уровням логических сигналов и конструкциям разъе-мов. Аппаратура передачи данных бывает:
- низкоскоростная (со скоростями передачи информации - до 200 бит/сек (по стандартным телеграфным кана-лам),
- среднескоростная - до 4800 бит/сек (по каналам тональной частоты),
- высокоскоростная - более 4800 бит/сек (по широкополосным каналам).
РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ
Пример распределенной вычислительной сети САПР приведен на рис 4.
Распределенная сеть содержит локальную вычислительную сеть кольцевого типа, которая объединяет разнотипные ЭВМ и периферийные- ГД - графический дисплей,
- Д - алфавитно-цифровой дисплей,
- ГП - графопостроитель
- МПК - мультиплексор - концентратор,
- М - модем,
- Т - телефонный канал,
- ГАП - ЭВМ гибкого автоматизированного производства,
- УС - узел связи
Несколько входов в сеть объединены в мультиплексоре-концентраторе для передачи данных по выделенному теле-фонному каналу. На другой стороне канала МПК радиально соединяет ряд разнотипных ЭВМ, в том числе и ЭВМ гиб-кого автоматизированного производства.
Один из входов локальной вычислительной сети через модем имеет выход в телефонную сеть. При этом обеспечива-ется связь локальной вычислительной сети с любым абонентом, имеющим аналоговый выход. В этом случае возможна координация процессов проектирования и изготовления через коммутируемые каналы связи.
АВТОМАТИЗИРОВАННЫЕ РАБОЧИЕ МЕСТА ПРОЕКТИРОВЩИКОВ
НАЗНАЧЕНИЕ
Автоматизированное рабочее место (АРМ) проектировщика представляет собой комплекс технических средств, который обеспечивает оперативный и легкий доступ оператора к ЭВМ и помогает реализации итерационных циклов проектирования при диалоговом режиме работы.
АРМ позволяет обмениваться с ЭВМ информацией в графической форме.
Функционально АРМы могут использоваться в качестве основы автономных САПР или подсистем функционально-логического, схемотехнического, приборно-технологического, конструкторского проектирования различных САПР РЭА.
Комплексы АРМ могут быть использованы в качестве:
- одного из уровней многоуровневых САПР,
- рабочих мест на уровне ЦВК,
- технологических комплексов для адаптации конструкторского проекта к различному технологическому обору-дованию,
- одного из технологических маршрутов, включая совместную работу с управляющими ЭВМ технологического комплекса в режиме обратной связи,
- инструментальных комплексов для разработки системного и прикладного программного обеспечения для подсистем САПР.
Рассмотрим два режима работы АРМ: автономный и непосредственной связи с ЦВК.
В автономном режиме АРМ используются для решения отдельных проектных задач, не требующих высокой произ-водительности и большого объема оперативной памяти. Как правило, они связаны с редактированием графической и текстовой информации и ее документированием.
Примеры проектных задач:
- проектирование печатных плат и механических узлов с выпуском комплектов управляющих перфолент и доку-ментации;
- проектирование фотошаблонов микросхем СВЧ узлов и микрополосковых трактов;
- подготовка управляющих перфолент для станков с числовым программным управлением;
- проектирование конструктивов.
В режиме непосредственной связи с ЦВК технические программные средства АРМ играют роль интерактивно-графического комплекса САПР и обеспечивают выполнение проектных операций. Основное назначение АРМ в этом случае - обеспечение эффективного общения проектировщика со средствами автоматизации проектирования.
Примеры проектных задач:
- ввод и редактирование больших массивов входных данных и заданий;
- управление режимами работы САПР,
- отображение и редактирование результатов проектирования;
- выпуск технической документации;
- моделирование и оптимизация элементов и схем БИС;
- компоновка и трассировка плат печатного монтажа и микросборок;
- создание и пополнение банков данных.
ТЕХНИЧЕСКИЕ СРЕДСТВА АРМ
В АРМах технические средства группируются (см. рис.5) вокруг высокопроизводительной мини-ЭВМ. Она связана с периферийными устройствами, комплексами, уровнями или другими САПРами каналами высокой пропускной спо-собности.
К каналам через интерфейс типа "Общая шина" подключаются технические средства рабочих мест. Они состоят из текстовых и графических средств ввода-вывода. Возможно использование микро-ЭВМ с оперативным и внешними за-поминающими устройствами. Состав технических средств АРМов для решения задач проектирования приведен в табли-це 4.
- систему управления базой данных общего назначения;
- справочно-обучающую.
Развитие технологии проектирования и специального программного обеспечения связано с внедрением бригадного ме-тода. Его существо заключается в одновременной работе нескольких проектировщиков на с
КОМПЛЕКСИРОВАНИЕ АРМ
Состав базового программного обеспечения и технических средств АРМ позволяет использовать АРМ автономно или в нескольких вариантах сопряжения с другой аппаратурой.
АРМы с одним или несколькими рабочими местами могут объединяться в последовательный комплекс. Комплекс настраивается на решение одной или ряда последовательных на маршруте проектирования задач (рис.7.б).
Например, ввод задания на разработку печатных плат, синтаксический контроль и размещение элементов выпол-няют на первом АРМе и по каналу связи передают на второй АРМ. На нем проводится трассировка, корректировка и передача информации для изготовления комплекта конструкторской документации на третий АРМ.
Подобная маршрутно-специализированная конфигурация позволяет устранить непроизводительные затраты време-ни на смену магнитных носителей, загрузку систем и ограничить количество периферийных устройств.
Построение информационно-графических комплексов для САПР на базе АРМ (рис.7.а, б, в, г) расширяет возмож-ности и увеличивает эффективность применения САПР. НА ЦВК выполняются программные модули по директивам с АРМов, а ввод, контроль, вывод и редактирование производится пользователем на средствах АРМ.
В этом случае требуется удаленное размещение технических средств АРМ и ЦВК. Для этого используются устрой-ства сопряжения (групповые устройства сопряжения - ГУС и индивидуальные ИУС), телефонные каналы связи , муль-типлексоры и аппаратура передачи данных.
ПЕРСПЕКТИВЫ РАЗВИТИЯ АРМ
Дальнейшее развитие АРМ связано с:
- использованием новых технических средств,
- разработкой нового базового и прикладного программного обеспечения,
- развитием технологии автоматизированного проектирования,
- объединением АРМ в иерархические и сетевые структуры.
Широкое распространение получают профессиональные персональные ЭВМ с использованием процессоров 386 и 486 и специализированных, а также соответствующего программного обеспечения.
Параметры новых АРМ:
- быстродействие - 5-10 млн.оп/сек,
- объем внешней памяти - до 500 Мбайт,
- скорость обмена информацией по каналам связи - свыше 2 Мбайт/сек.
Рабочие места будут оборудованы цветными графическими дисплеями с регенерацией или растровыми с размера-ми экрана до 50 см по диагонали и проекционных с площадью экранов в несколько квадратных метров.
Базовое программное и лингвистическое обеспечения должны включать в себя:
- средства создания многомашинных сетевых и иерархических структур;
- мониторную систему;
- операционную систему реального времени;
вязанных друг с другом АРМами по разработке логики и схемотехники БИС, топологии БИС и печатных плат, конструкций узлов и блоков изделий РЭА.
КОМПЛЕКСИРОВАНИЕ ТЕХНИЧЕСКИХ СРЕДСТВ САПР
Комплектование технических средств САПР производится на основе следующих требований:
- полноты,
- унификации,
- расширяемости,
- резервируемости,
- экономичности разработки и эксплуатации,
- эксплуатационного удобства и технологичности.
Полнота технических средств означает наличие в САПР набора технических средств всех групп для выполнения опе-раций по всему циклу автоматизированного проектирования.
Унификация технических средств означает использование однотипных единиц оборудования для выполнения одних и тех же функций на различных уровнях САПР.
Расширяемость (открытость) технических средств означает возможность количественных и качественных измене-ний в составе технических средств по изменению требований к производительности и степени автоматизации проектиро-вания, а также появления новых более совершенных типов оборудования.
Резервируемость технических средств реализуется дублированием тех или иных средств и позволяет снизить влияние их сбоев и отказов на функционирование САПР. Избыток технических средств не только повышает живучесть САПР, но и является обязательным условием успешной обработки потока задач, интенсивность которого изменяется во времени.
Экономичность разработки технических средств позволяет удешевить создание и внедрение САПР за счет последо-вательного многоэтапного ввода оборудования и наращивания мощности САПР с небольшим опережением относи-тельно роста текущих потребностей.
Экономичность эксплуатации технических средств позволяет снизить непроизводительные потери за счет сочета-ния режимов реального времени с пакетной обработкой, коллективного использования рабочих мест.
Эксплуатационное удобство технических средств позволяет увеличить производительность разработчика и снизить уровень ошибок при взаимодействии оператора с ЭВМ за счет совершенства программно-аппаратного обеспечения.
Технологичность технических средств характеризуется степенью соответствия состава оборудования перечню проектных операций, свойственных применяемой технологии проектирования заданного объекта.
В соответствии с этими требованиями в последнее время признаны наиболее целесообразными САПР из унифици-рованных модулей. Они имеют достаточно развитые технические и базовые программные средства. В составе пери-ферийных модулей широкое распространение получили "интеллектуальные терминалы" и "инженерные графические станции", создаваемые на основе микропроцессорных вычислительных средств.
Выводы:
1. Рассмотрены назначение, структура САПР, технические средства.
2. Рассмотрены назначение, структура автоматизированных мест проектировщиков и их возможности по созданию аппаратуры.
3. Определены перспективы развития технических средств автоматизированного проектирования.
НЕЙРОСТРУКТУРЫ
ВВЕДЕНИЕ
Теоретические основы нейросетевого подхода к изучению процессов переработки информации в мозге были зало-жены Маккалоком и Питтсом .Они изучили модельную нейронную сеть, представляющую
собой совокупность элементов( названных формальными нейронами),обменивающихся между собой информацией с помощью направленных связей. Каждый из формальных нейронов представляет собой простой процессор, осуществ-ляющий суммирование сигналов, которые поступают на его входы. Его состояние характеризуется внутренней перемен-ной , принимающей значение 0 ( пассивное состояние), если сумма сигналов на входах меньше фиксированного порога, и 1 ( активное состояние, в котором нейрон способен посылать сообщения другим нейронам в сети ), если указанная сумма превышает порог. Авторами
показано, что сеть таких нейроподобных элементов в принципе способна выполнять различные логические функции и по своей вычислительной мощности сопоставима с вычислительными машинами фон
неймановского типа.
Позднее Ф. Розенблатт предложил архитектуру нейронной сети, получившую название персептрона . Это вызвало большой интерес, поскольку открывалась возможность создания технических устройств, способных решать интеллекту-альные задачи, такие как распознавание образов.
Основным элементом персептрона является пороговый вентиль, аналогичный формальному нейрону Мак-Коллака и Питтса. Он осуществляет суммирование с определенными весами сигналов, поступающих
от других нейронов, и переходит в состояние логической единицы(или наоборот, нуля), если эта сумма превышает пороговое значение.
В последние годы наблюдается рост активности в области теории и технической реализации искусственных нейрон-ных сетей, в идейном отношении близких к персептрону Розенблатта. В работах Андерсона, Гроссберга, Кохонена, Хопфилда и др., выполненных в конце 70-х - начале 80-х годов, были разработаны более сложные и гибкие архитектуры сетей, составленных из нейроподобных элементов, и изучены функциональные возможности таких систем. Следует отметить, что этот процесс происходил на фоне общего возрастания интереса к многопроцессорным системам(к кото-рым относятся в том числе и нейронные сети) и к реализации на них параллельных процессов обработки информации. Сочетание в архитектуре нейронных
сетей массированного параллелизма при обработке информации с использованием элементов-связей ( анало-гов синапсов в биологии ) на стадии обучения системы выделило нейронные сети в самостоятельный
класс многопроцессорных вычислительных устройств.
Здесь рассмотрим основные архитектуры нейронных сетей, их общие и функциональные свойства и наиболее рас-пространенные алгоритмы обучения сетей.
ОСНОВНЫЕ АРХИТЕКТУРЫ И ОСОБЕННОСТИ
Среди признаков, отличающих нейронные сети, часто называют массированный параллелизм при вычислениях, а также возможность программирования сетей путем обучения или адаптации. Выделяют
также локальность памяти каждого из нейронов.
ЭЛЕМЕНТЫ ИСКУССТВЕННЫХ НЕЙРОННЫХ СЕТЕЙ - НЕЙРОНЫ И СВЯЗИ
Нейронная сеть представляет собой совокупность элементов двух типов-процессоров, называемых нейронами, и элементов ( в общем случае также процессоров) - называемых связями между нейронами.
Нейрон - процессор специального вида, который имеет один выход и некоторое число входов (N) (рис.2.). Как правило, предполагается, что все нейроны выполняют одинаковую, сравнительно простую функцию
( либо существует небольшое число типов нейронов с различными функциями), например, сложение величин сигна-лов , i = 1,...,N , поступающих на его входы ( возможно, с некоторыми весами ). Выходной сигнал нейрона определяется с помощью суммы i вида
Между каждыми двумя нейронами в сети ( с номерами i и j)могут быть установлены две направленные связи: (ij) и (ji) (рис.4).В некоторых случаях, например в модели Хопфилда, эти связи считаются равными. Каждой связи в сети присваи-вается вес . Это можно выполнить двумя способами. В первом случае считается , что собственно связи между ней-ронами представляют собой пассивные проводники, параметры которых неизменны. В процессе обучения изменяются веса ( см. рис.1 ), с которыми суммируются входные сигналы на каждом нейроне. При этом нумерация входов всех нейронов предполагается согласованной с нумерацией нейронов в сети. При втором способе все входы в нейрон пред-полагаются эквивалентными, при обучении изменяются свойства связей ( например, их сопротивления, емкости или коэффициенты усиления входящих в них усилителей ). С точки зрения математического моделирования эти способы могут не различаться. Однако при технической реализации в зависимости от используемой технологии может оказаться предпочтительней один из указанных способов. Например, пороговый вентиль относится
к первому типу, а сеть из аналоговых усилителей с насыщением - ко второму.
ТИПЫ АРХИТЕКТУР
Модель, предложенная Хопфилдом, относится к типу бинарных (или как вариант, биполярных, когда, переменная, описывающая внутреннее состояние нейронов, может принимать и отрицательное значение, например +1 и -1), а ее обучение представляет собой вариант обучения с супервизором. Она основывается на некоторых аналогиях с физиче-скими системами, в частности, со спиновыми стеклами , а также с нелинейными динамическими системами, обладаю-щими подходящей структурой аттракторов в фазовом пространстве. Каждый такой аттрактор может рассматриваться как отдельная запись информации ( образа ) в памяти системы. Релаксация системы из произвольного начального со-стояния ( имеющего смысл предъявленного
стимула) к устойчивой точке представляет собой физическую аналогию восстановления информации по достаточной ее части - распознавания образов.
В модели Хопфилда состояние системы описывается N -мерным вектором V = ( ), где
= 0 или 1 - описывает состояние i-го нейрона. Состояние системы, которому соответствует
одна из вершин единичного гиперкуба в N- мерном пространстве, меняется во времени по следующему алгоритму. Ка-ждый нейрон изменяет свое состояние в случайный момент времени со средней скоростью w так, что в следующий момент случайно выбранный элемент с номером i принимает значения
= 1, если и
= 1, если (2)
Здесь - порог срабатывания i-го нейрона. В дальнейшем, как правило, предполагается, что для всех i либо =1/2.
В последнем случае выбор порогов соответствует переходу к "биполярным" нейронам, состояния которых описыва-ются спиновыми переменными . Поэтому в большинстве случаев можно
просто говорить о моделях (0,1) и (+_1), определяя тем самым возможные состояния элементов при нулевых порогах.
Для хранения образов памяти , s= 1,..., n используется матрица связей следующего вида:
, i-=j , (3)
В такой сети воздействие на i-нейрон будет определяться выражением для "силы"( являющейся аналогом мембранно-го потенциала в нейробиологии)
i-=j, = 0.
Для случайно выбранных векторов среднее значение члена в скобках равно нулю, если s-=s'. Тогда справедливо выражение:
принимает положительные значения при = 1 и отрицательные при =0.
Поэтому при пренебрежении шумом, даваемым членами с s-=s', состояние образов памяти устойчиво
( во всяком случае , при n < N ). Возможно появление дополнительных устойчивых состояний сети, не совпадающих с векторами памяти - "ложные образы ".
Динамика нейронной сети, описываемая уравнениями (2)-(3), имеет в качестве аттракторов только устойчивые ста-ционарные точки. В случае симметричной матрицы Т в системе возможно наличие
большого числа стационарных состояний. Теория дискретных сетей Хопфилда получила в последнее время
значительное развитие. Возможность введения функции, имеющей смысл энергии, уменьшающейся в процессе ре-лаксации начального состояния системы, позволила применить для исследования системы
хорошо разработанный аппарат статистической физики. В частности, введение сопряженной к энергии величины - эф-фективной "температуры" - позволило исследовать структуру устойчивых состояний и воз-
можности их изменения в процессе обучения .
Возможна реализация нейронной сети на аналоговых элементах (операционных усилителях). Это позволяет исполь-зовать их для решения задач комбинаторной оптимизации, коммивояжере, задаче о
раскраске карт, задаче оптимизации размещения электронных элементов на чипе.
б) СЕТЬ КОСКО
Коско предложил модель нейронной сети с синхронной динамикой, которая получила название двунаправленной ассоциативной памяти ( bidirectional associative memory, BAM). Она представляет инте-
рес для оптических реализаций нейронных сетей. В этой модели вся совокупность нейронов разделена на подмножества ( вообще говоря, различной мощности) - А и В . Сеть устроена таким образом, что
выходы нейронов подсети А связаны с входами нейронов подсети В и наоборот( см. рис. ). Матрица связей строится по правилу:
оно имеет вид суммы прямых произведений векторов памяти
Рис. Схема модели двунаправленной ассоциативной памяти Коско.
Динамика этой системы описывается парой уравнений
,
.
Так же, как и в случае модели Хопфилда, для ВАМ единственными аттракторами в фазовом пространстве являются устойчивые стационарные точки, называемые парой ( ). Эти точки достигаются
из произвольного начального состояния - пары векторов ( ).
Имеются модификации нейронной сети Коско:
- за счет введения матриц связи общего вида ( ассиметричных, удовлетворяющих принципу "детального баланса"),
- за счет введения ненулевых порогов, что позволяет увеличить число устойчивых состояний системы ( их число в общем случае N находится между 1 и 2 ).
в) ХЕММИНГОВА СЕТЬ
Хеммингова сеть представлена на рис. .
Она состоит из двух частей. Нижняя подсеть служит для формирования по входу - бинарному вектору длиной N - на-чального состояния для нейронов верхней подсети. Число нейронов в ней M.
Веса связей для нижней подсети и для верхней, а также пороги для нижней подсети устанавливаются по следующим правилам:
, = N/2 , i=1,...,N , j=1,..., M, (4)
.
Пороги для верхней подсети устанавливаются равными нулю. В выражении (4) - i-ый элемент j-го вектора па-мяти (число нейронов в среднем слое M совпадает с числом записанных образов).
Рис. Схематическое изображение хемминговой сети.
В данной сети выполняются итерации для нейронов верхней подсети
при начальном условии
.
Функция g в этих выражениях соответствует рис.3б, причем динамика чувствительна к выбору величины переход-ной области а. Процесс итераций продолжается до тех пор, пока выходы всех нейронов,
за исключением одного, не станут отрицательными.
Имеется другое название сети Хемминга - сеть с латеральным торможением ( явление латерального торможения широко распространено в нейрофизиологии).
г) ПЕРЦЕПТРОНЫ
Простейший персептрон состоит из одного слоя нейронов, соединенных связями с N входами. Соответствующая схе-ма представлена на рис. .
Веса связей обозначены , i=1,...,N , j=1,...,M (M - число нейронов - пороговых элементов в слое). Каждый из ней-ронов осуществляет нелинейное преобразование сигналов, поступающих на его вход, согласно выражению (1)
,(6)
где g - пороговая функция, изображенная на рис.3а, - входные значения, = 0,1 - переменные характеризующие выходы нейронов. Переменные могут принимать произвольные значения ( в частности, могут быть аналоговыми). Согласно ( 6 ), персептрон разделяет все N -мерное пространство входных переменных { } на классы посредством гиперплоскостей. Они определяются уравнениями вида:
Может существовать не более 2 таких классов. Веса связей и пороги могут быть фиксированными либо изменяться адаптивно. Простейший алгоритм адаптации был предложен Розенблаттом.
Рассмотрим случай, когда М=1.
В этом случае персептрон осуществляет разбиение множества всех входов на два класса
A ( y= +1 ) и B ( y= -1 ). Модификация весов связей (j= 1 ) производится после каждого вычисления
выхода нейрона в соответствии с выражением ( 6 ) при подаче на вход сети очередного вектора обучающей выборки:
где 0 < n <= 1, y (t) - состояние выхода нейрона при входном векторе x(t), для которого желаемым вектором является d(t). Если выход совпадает с желаемым вектором, связи не изменяются.
Розенблатт показал, что если входные векторы , принадлежащие поочередно одному из двух классов, разделимы в пространстве входов некоторой гиперплоскостью, то указанный алгоритм сходится.
Недостатком простых однослойных персептронов является невозможность построить сложную разделяющую гипер-поверхность в пространстве входов. Для того, чтобы это сделать, используют более
сложные модели - многослойные персептроны ( см. рис. ). В этих моделях вводятся "скрытые" слои нейронов, эле-менты которых не связаны непосредственно с входами и выходами системы.
Двухслойные персептроны позволяют формировать выпуклые оболочки в пространстве входов
(отвечающие тому или иному классу).
Трехслойные персептроны дают возможность построить области произвольной сложности. При этом ограничение только на число используемых в сети нейронов.
Однако, обучение таких сетей является весьма трудоемким процессом и для формирования необходимых матриц связей необходимо применять специальные алгоритмы.
АЛГОРИТМЫ ОБУЧЕНИЯ НЕЙРОННЫХ СЕТЕЙ
Возможность обучения является важнейшей отличительной особенностью нейросетевого подхода к построению систем обработки информации. Имеется большое число вариантов процедур обучения ней-
ронных сетей. Они могут быть разделены на два класса: обучение с супервизором и обучение без супервизора или самообучение. Использование того или иного алгоритма обучения в значительной мере
определяется архитектурой сети.
ОБУЧЕНИЕ С СУПЕРВИЗОРОМ
В этом случае формируется обучающая выборка - совокупность входных векторов { , s=1,...,N }, каждому из которых поставлен в соответствие определенный выходной вектор из множества
{ , p,...M }. Размерности входного N и выходного M векторов могут не совпадать. Процедура обучения произ-водится при заданной топологии связей между нейронами. При этом необходимо подобрать
их веса таким образом, чтобы при подаче на вход сети любого входного вектора из обучающей выборки на ее выходе формировался правильный выходной вектор.
Сеть, удовлетворяющая этому требованию, является обученной.
Одним из первых алгоритмов, предложенных для обучения персептронов еще в 60-х годах, был алгоритм Уидроу-Хоффа.
Рассмотрим его. Алгоритм предполагает выполнение последовательности шагов. Каждый шаг в свою очередь состоит из двух этапов.
ЭТАП 1. На вход сети подается один из векторов обучающей выборки. На выходе сети задается желаемый выходной вектор. Веса всех связей, соединяющих активные входные и выходные нейроны, увеличиваются на малую величину del.
ЭТАП 2. На вход сети подается тот же вектор из обучающей выборки. Нейронной сети предоставляется возможность в соответствии с имеющимися весами связей самой установить на выходе определенный вектор. Если нет соответствия между входным и выходным векторами, то веса связей, соединяющих активные входные и выходные нейроны, умень-шаются на ту же величину del.
Если сеть правильно установила выходной вектор, то обучение завершается. В противном случае - обучение продол-жается.
Принципиальная трудность, присущая рассматриваемому подходу, состоит в том, что для многих обучающих выбо-рок невозможно провести необходимое распределение связей между нейронами персептрона. Указанное ( невозмож-ность обучения произвольному набору образов) присуще, по-видимому, всем нейронным сетям. Обратное справедливо лишь для сетей, содержащих бесконечное число нейронов,
имеющих два слоя и если выполняются ограничения на характеристики выход-вход нейрона.
Даже при существовании искомого отображения проблема обучения нейронной сети сталкивается с серьезными трудностями. Они связаны с тем, проблема обучения нейронных сетей относится к классу
NP-сложных. Т.е. не существует алгоритма, который бы за полиномиальное время ( время, растущее с размером сети не быстрее полинома конечной степени) решил задачу требуемой модификации связей
сети. Поэтому , при практическом обучении нейронных сетей ( в частности, многослойных сетей) неизбежно исполь-зование различных эвристик, позволяющих за ограниченное время найти приближенное
решение задачи обучения.
Имеется достаточное количество эвристических методов, среди них наибольшее распространение получил метод "обратного распространения ошибки" ( back- propagation error, BPE ).
Алгоритм BPE представляет собой обобщение метода наименьших квадратов применительно к многослойным пер-септронам. В данном методе минимизируется среднеквадратичная ошибка между фактическим выходом персептрона и желаемым выходным вектором. Начальные веса и пороги принимаются равными случайно выбранным числам. Затем на вход сети последовательно подаются векторы из обучающей выборки и модифицируются связи между нейронами, начиная с последнего слоя.
Представим ценностную функцию в виде:
где V - фактические значения состояния нейронов, вычисленные с учетом текущих значений связей между нейрона-ми. В этом выражении сумма распространяется на нейроны последнего ( выходного) слоя.
Изменение весов связей на каждом шаге алгоритма производится по правилу:
где > 0 - параметр. Вычисляя производную в этом выражении, для выходного слоя нейронов получим:
.
Затем последовательно вычисляются изменения коэффициентов на предшествующих слоях.
Такой способ модификации связей в сети позволяет значительно сократить время, необходимое для обучения сети. Вообще , время обучения существенно зависит от требуемой сложности разбиения
пространства возможных входов сети на подклассы ( например, если построить несвязные области ).
3.2. ОБУЧЕНИЕ БЕЗ СУПЕРВИЗОРА
Подобный подход применим к нейронным сетям Гроссберга-Карпентера и Кохонена. Такие сети имеют другое на-звание - самоорганизующиеся сети. Процесс их обучения выглядит как процесс возникновения определенных свойств при взаимодействии системы с внешним миром. Сети такого типа наиболее близки по своим свойствам к неравновес-ным физическим, химическим или биологическим системам, в которых возможно образование диссипативных струк-тур. Распознание образов и обучение, по-видимому, тесно связаны с вопросом о коллективном поведении систем, включающим множество частиц.
Сущность обучения без супервизора можно пояснить следующим образом. Для этого рассмотрим динамическую систему, элементы которой ( нейроны) взаимодействуют между собой и термостатом.
Состояние i-го нейрона будем описывать непрерывной переменной m (t) ( t - время ), изменяющейся в интервале - m<= m <=+m .
Предположим также, что энергия системы является квадратичной функцией вида
( 7 )
Будем рассматривать величину
( 8 )
В дальнейшем al - параметр или лагранжиан взаимодействия системы, являющейся функционалом независимых переменных и .
Учитывая взаимодействие нейронов с термостатом, приводящее к появлению "сил трения" (m / gam ,
T/ gam ) из (8)получим динамические уравнения для и
( 9 )
( 10 )
Добавленные в эти уравнения нелинейные слагаемые (f, F) препятствуют неограниченному возрастанию абсолют-ных величин m и Т: в рамках лагранжевой схемы они могут быть включены в выражение (9 ) в виде потенциалов, бы-стро возрастающих вблизи точек + -m и + - T ( предельное значение для коэффициентов матрицы связей).
Величины и представляют собой ланжевеновские источники шума. В нейробиологии шум возни-кает вследствие несинаптических взаимодействий между нейронами и выделением нейромедиаторов. В электронных моделях нейронных сетей источником шума могут быть электрические флуктуации в цепях. В простейшем случае шум можно охарактеризовать введением эффективной температуры:
< > = < > ,< > = < > = 0 ,
где скобки обозначают усреднение по времени.
Уравнения (9) и (10) описывают существенно различные физические процессы, которые в рассматриваемом контек-сте можно назвать "обучением" и "распознаванием образов". Рассмотрим первое из них. Обучение состоит в том, что в (9) включается сильное внешнее поле, действующее в течение времени t . В результате того вектор m(t) принимает ста-ционарное значение fi , соответствующее "образу" с компонентами m . После "обучения" элементы матрицы , со временем в соответствии с уравнением (10), получат приращение ( при этом предполагается, что t значительно больше времени релаксации на внешнем поле вектора m к своему стационарному значению fi ). Процедуру обучения можно повторить многократно, используя образы fi , s=1,...,n. Считая, что до начала обучения = 0, после окончания этого процесса получим
,
где коэффициенты nu зависят от длительности обучения. Таким образом, уравнения (9) и (10) описывают процесс запоминания поступающей в систему информации в виде матриц связей хеббовского вида.
Ранее предполагалось, что до начала обучения нейронная сеть не содержит никакой информации, = 0. Можно рассмотреть противоположный случай, когда до начала обучения нейронная сеть имеет большое число устойчивых состояний. Предполагается, что доминируют глубокие энергетические минимумы, которые могут образовывать структуру дерева. Процедура обучения должна приводить к селекции образов . В процессе обучения заучиваемый об-раз задается в качестве начального состояния сети и эволюционирует к некоторому аттрактору, энергия которого уменьшается за счет синоптических изменений ( в частности, если время релаксации меньше времени обучения), а об-ласть притяжения смещается и увеличивается за счет
присоединения соседних областей. Таким образом, процесс селекции отличается от режима обучения, рассмотренно-го ранее тем что используется внешнее поле.
ОСНОВНЫЕ ФУНКЦИИ НЕЙРОННЫХ СЕТЕЙ
АССОЦИАТИВНАЯ ПАМЯТЬ И КАТЕГОРИЗАЦИЯ
Под ассоциативной памятью ( или памятью, адресуемой по содержанию) понимается способность системы нейро-нов, например, мозга млекопитающих восстанавливать точную информацию по некоторой
ее части. К этому определению близок процесс категоризации - отнесение предъявленного объекта к одному из клас-сов. Многие из предложенных в настоящее время сетей способны фактически осуществлять эти функции. При этом критерии, по которым осуществляется отнесение объектов к тому или иному классу ( распознавание) , различны в раз-ных моделях.
Рассмотрим в качестве примера модель Хопфилда.
Пусть сначала n=1 b и в матрице Т записан всего один образ fi . Скалярноe произведение произвольного вектора m и fi задается выражением (fi , m ) = N - 2 m, где m - хеммингово расстояние между векторами m и fi , равное чис-лу элементов, отличающих эти векторы. Подставляя это выражение в ( 7 ), получим следующее выражение для энергии:
.
Из данного выражения видно, что Е принимает минимальное значение при m=0. При этом вектор М совпадает с запи-санным образом либо, когда m=N ( в этом случае m совпадает с "негативом" ). Поэтому эволюция любого начального состояния системы заканчивается в состояниях m = fi .
В случае n = 2 выражение для энергии имеет вид
.
Здесь N - число позиций, в которых компоненты записанных в Т векторов совпадают: fi = fi , N- число несовпа-дающих компонент этих векторов, для которых fi =- fi , m и m - число компонент вектора m в первой и во второй группе нейронов соответственно, отличающих m от fi . Из последнего выражения видно, что система нейронов имеет четыре устойчивых состояния, отвечающих m = 0,N , m =0,N . При этом они совпадают с одним из векторов fi ,= fi .
Функцию категоризации могут осуществлять нейронные сети других типов, при этом каждая из сетей делает это по разному. Так, если сеть Хопфилда относит к одному устойчивому вектору все стимулы, попавшие в область его зоны притяжения, то сеть Хемминга относит каждый входной вектор к ближайшему вектору, записанному в память.
ВЫРАБОТКА ПРОТОТИПА И ОБОБЩЕНИЕ
Различные типы нейронных сетей допускают возможность их обучения для выполнения алгоритмов обработки вход-ной информации. При этом в обучающей выборке может не содержаться полного описания
предлагаемых алгоритмов.
Рассмотрим два примера:
- выработка прототипа в модели Хопфилда ( образование устойчивого образа в памяти, не содержавшегося среди обу-чаемых векторов),
- обобщение по индукции.
При увеличении числа образов в памяти минимальные значения энергии, вычисленные с помощью выражения (7) и соответствующие различным записанным векторам, могут начать сливаться.
Рассмотрим группу образов fi ( s=1,...,n) , получающихся при небольших случайных искажениях del некоторого вектора fi .
При изменении вектора fi на величину del происходит изменение энергии, соответствующей этому вектору, на ве-личину del E.
При и случайном искажении исходного вектора fi при построении группы об-разов может выполняться неравенство del E 0 и следовательно, исходный вектор отвечает минимуму энергии системы. В психологии образ, аналогичный fi ( т.е. являющийся в определенном смысле усреднением некоторого числа образов и остающийся в памяти человека наряду с действительно предъявлявшимися образами) , получил название прототипа.
Сущность обобщения по индукции можно понять на следующем примере. Предположим, что множество входов сети разделено на две части, кодирующие соответственно два "образа". Например, это могут быть два числа либо два изображения предметов. Выходной слой персептрона пусть содержит один бинарный нейрон. При обучении будем стремиться к тому , чтобы на выходе сети была 1, если образы на входе совпадают и 0 , в противном случае. Установле-но, что трехслойная сеть может быть обучена по указанному правилу, и способна определять совпадение образов на входе ( или симметрию входного вектора, что в данном случае одно и то же). Таким образом, сеть по индукции обуча-ется устанавливать совпадение двух
векторов, хотя при обучении явное определение понятия совпадение не приводилось. По этому же принципу можно обучить нейронную сеть складывать числа.
ЗАКЛЮЧЕНИЕ
Практические процедуры обучения нейронных сетей часто сталкиваются с невозможностью добиться от сети желае-мого поведения. Ранее упоминались некоторые проблемы такого рода:
- отсутствие сходимости процесса обучения персептронов,
- ложная память в модели Хопфилда.
Причины этого могут разделены на две группы.
1. Значительное время обучения нейронных сетей в сложных случаях.
2. Принципиальная невозможность получения необходимой структуры фазового пространства в заданной модели нейронной сети.
Область приложения нейронных сетей значительна и расширяется.
Этот процесс идет по ряду направлений. К их числу можно отнести следующие:
- поиск новых нелинейных элементов , которые могли бы реализовывать сложное коллективное поведение в ансамбле,
- разработка новых архитектур нейронных сетей, перспективных с точки зрения их реализации на электронной, опти-ческой и оптоэлектронной элементной базе,
- поиск областей приложения нейронных сетей в системах управления, робототехнике, системах обработки изобра-жений, распознавания речи.
ЛЕКЦИЯ №3
СИСТЕМА АВТОМАТИЧЕСКОГО ВВОДА ИНФОРМАЦИИ В ЭВМ
1. Необходимость создания системы автоматического ввода
Cоздатели САПР помимо выявления множества задач, решаемых системой, и распределения их между человеком и ЭВМ должны также на основе анализа требования пользователя определить способы общения человека с машиной. По-следнее предполагает выбор подходящих средств диалога и установление языков общения.
Продуманный выбор языка играет существенную роль в создании творческой обстановки для человека в процессе автоматизированного проектирования. Желательно, чтобы оператор, находящийся за терминалами АРМа, общался с системой в привычной для него форме представления информации. Всякая замена привычных и удобных языков на менее удобные приводит к снижению производительности труда.
В качестве языков общения естественно использовать языки изображений. Примерами подобных языков являются языки, образованные графическими документами (принципиальными, функциональными, электрическими схемами, схемами размещения элементов, эскизами топологии слоев печатного монтажа и др.).
Другие способы описания того, что изображено на графическом документе, затрудняют процесс восприятия информации человеком.
Очевидно, что и в случае, когда информация графического типа передается от человека к ЭВМ , этот процесс должен быть для человека столь же простым и легким. Однако наиболее распространенная в современных САПР тех-нология ввода графической информации представляет собой трудоемкую и длительную процедуру. Серийно выпус-каемые устройства, предназначенные для обеспечения процесса ввода в ЭВМ графической информации, позволяют делать это в полуавтоматическом режиме.
Полуавтоматические графические устройства ввода данных требуют, чтобы оператор при помощи специального устройства (щупа) обошел все характерные точки документа и сообщил машине характеристики этих точек.
Данный труд лишен признаков творчества и его обычно поручали оператору. Такое разделение труда между разра-ботчиком и оператором сколочного автомата нарушает единство творческого процесса и создает дополнительное звено в цепочке его общения с ЭВМ. Эта цепочка служит источником дополнительных ошибок, которые в дальнейшем необ-ходимо отыскивать и исправлять.
Проводились оценки трудоемкости процесса ввода графической информации в полуавтоматическом режиме ввода графической информации с чертежа печатной платы размером 150*300 мм, содержащей до 1500 контактных площадок и до 1200 соединяющих их линий. Время ввода информации в этом случае - 16 часов.
При этом предполагалось, что процесс включает также и редактирование изображения.
Альтернативой технологии считывания графической информации и использованием сколочных планшетов является технология, основанная на применении системы автоматического чтения изображения непосредственно с графического документа.
В этом случае достигается существенный выигрыш во времени ввода информации. Применительно к устройству ТС-6030 (автоматического считывания и кодирования графической информации) ввод осуществляется в 12 раз быстрее.
Рассмотрим различные аспекты построения системы автоматического чтения графической информации, требова-ние к документам, описания алгоритмов реализации основных этапов обработки изображений, а также обеспечения высокой достоверности считывания информации.
2.Требования к документам, автоматически считываемым системой
2.1. Общие сведения
Документ является носителем информации, которая должна быть введена в ЭВМ в качестве исходных данных для той или иной программы, входящей в пакет прикладных программ САПР.
Например, принципиальная электрическая схема определенного узла радиоаппаратуры может рассматриваться как исходные данные для таких программ, как моделирование, генерация диагностических тестов узла, алгоритмическое кон-струирование платы печатного монтажа, на которой будет реализован узел и др.
К документам, предназначенным для автоматического чтения, предъявляются противоречивые требования. С одной стороны, изображение на нем должно легко восприниматься человеком, а с другой - системой автоматического чтения. Это означает, в первую очередь, что условные графические обозначения, используемые как фрагменты изображения, должны быть привычными для человека.
В случае принципиальных электрических схем это условные графические обозначения элементов схемы, обозначе-ния электрических связей, символы и строки символов, регламентируемыми соответствующими ГОСТами.
Необходимо отметить, что документы, предназначенные для ввода в ЭВМ, как правило, изготавливаются человеком вручную. Вследствие этого изображение может существенно отличаться от идеального. Конкретные отклонения от иде-ального появляются, в частности, в том, что вместо прямой линии на эскизе, чертеже или схеме присутствует волнистая или встречаются "недоводы", "переводы" линий. Характер написания символов также изменяется в широких пределах. При этом часто их начертание значительно отличается от регламентируемого стандартами, однако человек не испыты-вает затруднений в восприятии информации.
В свою очередь системы автоматического чтения графической информации весьма чувствительны к отклонениям изображения от идеального. Это не означает, что они не могут правильно воспринимать изображения, содержащие де-фекты.
Однако следует отдавать отчет в том, что сложность систем, обладающих способностью игнорировать дефекты исполнения документа человеком и правильно считывать информацию, существенно выше по сравнению с системами, такими способностями не обладающими.
Конкретно это может трансформироваться в более высокие аппаратурные затраты или в увеличение затрат времени на реализацию алгоритмов обработки. Тем не менее никакая из технических систем сегодняшнего дня или ближайшего будущего не в состоянии конкурировать с человеческими способностями в восприятии реальных графических изобра-жений. Любой системе автоматического чтения можно предложить для обработки документ такого исполнения, что она не справится с его обработкой, в то время как человек легко прочитает этот документ.
На основе отмеченного можно сделать вывод о том, что документы, предназначенные для автоматического ввода должны удовлетворять ряду требований.
При разработке требований необходимо учитывать:
- технические характеристики растровой аппаратуры считывания,
- приемлемость требований к исполнению документа для конструктора его разрабатывающего,
- сложность и быстродействие алгоритмов обработки.
Опишем требования к изображениям на эскизах слоев топологии плат печатного монтажа.
Необходимость в считывании информации с эскизов слоев топологии плат печатного монтажа связана с автомати-зацией проектирования и изготовления их фотошаблонов.
Изображение на эскизе слоя топологии платы печатного монтажа состоит из условных графических обозначений контактных площадок для выводов навесных элементов (микросхем), границ областей металлизации требуемой формы, указателей трасс проложения печатных проводников. С помощью перечисленных изобразительных средств можно соз-дать рисунок топологии слоя любой платы.
Изображения символов можно создать средствами описания трасс печатного проводника. Особенностью эскиза яв-ляется то, что в нем применяется координатная сетка для метрической привязки элементов изображения. Шаг коорди-натной сетки равен 5 или 2.5 мм, если для исполнения эскиза слоя топологии выбран масштаб 4:1 или 2:1 соответственно. Метрическая привязка контактных площадок для условных графических обозначений осуществляется путем помещения центра условного графического обозначения в узел координатной сетки. Для остальной части изображения эскиза при-вязка производится лишь для точек излома линий рисунка. Такие точки должны быть помещены в узлы координатной сетки.
Рассмотрим,что представляют собой изобразительные средства для элементов рисунка на эскизах слоев топологии.
а) Контактные площадки
Контактные площадки круглой формы изображаются в виде крестов, центры которых совпадают с узлами коорди-натной сетки. Горизонтальный и вертикальный штрихи креста имеют длину 1 дискреты.
Различают контактные площадки нескольких типов в зависимости от диаметра области, которую они занимают. Это выполняется с помощью группы точек. Они помещаются в узлах координатной сетки и располагаются на сторонах ми-нимального по размеру квадрата из линий координатной сетки, который охватывает центр креста контактной площадки круглой формы. Размер стороны квадрата - 2 дискреты . Число точек в группе указывает тип координатной площадки.
а)б)в)г)
Рис. 1. Изображения контактных площадок круглой формы на эскизах слоев топологии.
Таблица 1.
Количество точекТипДиаметр, мм
1
2
3
4
5
6
72
3
7
4
8
31
802,125
2,5
2,75
3
3,25
3,5
4
Таблица 2
Число точекШирина проводни-ка
1
2
3
40,625
1,25
1,875
2,5
б) Печатные проводники
Печатные проводники изображаются на эскизе отрезками прямых линий четырех направлений: горизонтальное, верти-кальное и два диагональных, т.е. проходящие под углом 45 градусов к линиям координатной сетки. Горизонтальные и вертикальные отрезки проводятся только по линиям координатной сетки, а диагональные - через узлы координатной сет-ки.
Точки изломов, разветвлений линий, изображающих печатные проводники должны совпадать с узлами координат-ной сетки. В связи с тем, что ширина проводника на различных участках должна может отличаться, необходимо раз-делять изображение печатных проводников на участки однородности. При этом имеются в виду участки одинаковой ширины, они снабжаются указателями ширины.
Разделение изображения печатных проводников на участки однородности осуществляется с помощью указателей границ однородности. Они бывают условными и абсолютными. Условными могут служить излом проводника и разветв-ление проводника.
Абсолютный указатель границ однородности представляет собой отрезок прямой линии, имеющий длину 1 дискре-ту. Такой отрезок одним концом исходит из точки, лежащей на проводнике и являющейся границей изменения однород-ности. Граница изменения однородности обязательно должна располагаться в одном из узлов координатной сетки. На-правление проведения штриха абсолютного указателя границы однородности должно выбираться перпендикулярно к ориентации проводника в точке, из которой он исходит.
В случае, если в точке нарушения однородности проводник претерпевает излом или разветвляется, достаточно, что-бы штрих указателя границ однородности был перпендикулярен одной из ветвей проводника, подходящей к этой точке.
Указатель ширины представляет собой группу точек, размещаемых в разрыве линии печатного проводника. Число точек связано со значением ширины (табл.2). Если одна из точек группы заменена штрихом (длина 1 дискреты), направ-ленным перпендикулярно линии проводника, то тогда указатель ширины рассматривается как доминирующий, в про-тивном случае - как простой. Действие доминирующего указателя распространяется в обе стороны от него и прекра-щается при встрече с абсолютным указателем и при переходе через условный указатель, содержащий простой указатель ширины.
Действие простого указателя ширины, как и в случае доминирующего указателя, распространяется в обе стороны от него и прекращается при встрече с абсолютным указателем и при встрече с условным указателем, если по другую сто-рону указателя действует доминирующий указатель ширины.
На рис.2 показан фрагмент эскиза слоя топологии для печатного проводника и соответствующий ему фрагмент вида печатного проводника.
Рис. 2. Печатный проводник, а - фрагмент эскиза, б - фрагмент печатной платы.
Особенностью реальных плат печатного монтажа является то, что в большинстве случаев печатные проводники на них выполняются одной и той же ширины. С учетом этого обстоятельства любая указанная в табл.2 ширина может быть объявлена основной. Объявление ширины печатного проводника основного типа осуществляется пользователем перед сеансом ввода документа в форме соответствующего сообщения программе обработки изображения.
Аналогично для контактных площадок.
в) Области металлизации
Области металлизации изображаются системой замкнутых контуров. Контура могут быть внутренними либо внеш-ними. Это определяется указателем контура. В качестве его служит отрезок прямой линии длиной в 1 дискрету. Один из его концов должен находиться на линии контура в узле координатной сетки и составлять с ней угол 45 градусов. Свобод-ный конец указателя контура показывает область металлизации.
Линии контуров изображаются отрезками вертикальных, горизонтальных и диагональных линий, проходящих по ли-ниям координатной сетки. Любые отрезки должны начинаться и завершаться в узлах координатной сетки.
При разработке слоя топологии платы печатного монтажа конструктору часто приходится использовать типовые фрагменты изображения, которые сами могут быть достаточно сложными рисунками. Для упрощения задачи вводятся дополнительные средства изображения - элементы библиотечного типа.
Под ними подразумеваются группы элементов, форма и взаимное расположение которых фиксированы. Примера-ми таких групп могут служить ряд контактных площадок, микросхемы определенного типа или совокупность контактных площадок для разъема. На эскизе такие группы изображаются в виде площадки, вместо которой в конечный результат обработки эскиза подставляется подразумеваемая группа.
Для простоты изложения ограничимся примерами элементов библиотечного типа для изображения одного ряда контактных площадок микросхем с планарными выводами.
Рис. 3. Изображение области металлизации
Границы элементов библиотечного типа одного ряда контактных площадок имеют вид прямоугольника, ширина ко-торого равна 1 дискрете. Длина прямоугольника зависит от типа корпуса микросхем.
Рис . 4. Элементы библиотечного типа для контактных площадок (фрагмент эскиза).
Крайние контакты в группе контактных площадок изображаются короткими сторонами прямоугольников, осталь-ные предполагаются отстоящими от соседних на 1 дискрету. Если какие-либо смежные контакты группы соединены ме-жду собой, то такая связь изображается наклонным отрезком, проведенным внутри прямоугольника слева направо, сверху вниз и соединяющим узлы, лежащие на линиях координатной сетки, соответствующих соединяемым контактным площадкам.
При разработке требований к эскизам слоя топологии необходимо учитывать особенности аппаратуры растрового считывания. В частности разрешающая способность устройства накладывает ограничения на минимальную толщину линии изображения. При этом необходимо, что на интервале длины, равной минимальной толщине линии, укладыва-лось два отсчета устройства. Так, например, для аппаратуры растрового считывания ширина линии должна быть не ме-нее 0.5 мм.
Существенную роль играет цвет красителя, которым наносятся линии на документ. Большая часть устройств, предназначенных для считывания документов, способна воспринимать лишь черно-белые изображения. При использо-вании желтого, светло-оранжевого цветов они будут восприниматься как белый.
Возникает проблема восприятия координатной сетки.
Выходом из положения является применение системы базовых линий, снабженных координатной разметкой. Систе-ма базовых линий представляет собой прямоугольник, внутри которого заключено поле изображения документа. От каждой из базовых линий, перпендикулярно ей, внутрь прямоугольника, составленного из базовых линий, отходят риски длиной 5 мм. Расстояние между соседними рисками, расположенными на одной и той же базовой линии, равно шагу координатной сетки. Назначение рисок -обозначать линии координатной сетки.
Учет особенностей аппаратуры растрового ввода оказывает влияние и на выбор условных графических изображе-ний, применяемых на документе. В частности, принятая система обозначений для эскизов слоев топологии не допускает углов схождения линий, меньших 45 градусов. Это существенно уменьшает эффектзаплывания области, размещаемой внутри острого угла при его вершине. Последнее упрощает обработку изображений после растрового считывания. Предложенные для эскизов слоев топологии основные элементы изображения сконструированы из таких компонентов, как отрезки прямых. Причем эти прямые могут иметь только одно из четырех направлений, что создает существенные предпосылки для более простой алгоритмической обработки.
При формировании требований к эскизам слоев топологии конкретизация положения о том, что изготовление эски-за должно удовлетворять определенным требованиям, заставляет включать в их число пункты, дисциплинирующие ис-полнителя эскиза. При этом разрывы в линиях не должны превышать 1 мм, переводы линий не должны быть больше 1 мм, отрезки прямых не должны отклоняться от идеальных прямых более чем на 1 мм.
Отмеченное относительно эскизов слоев топологии плат печатного монтажа дает представление о том, каким дол-жен быть документ, предназначенный для автоматического чтения. Создание системы автоматического чтения для дру-гого типа документа в каждом случае требует, как отмечено ранее, специального рассмотрения.
Линии координатной сеткиБазовые линии
a
Поле изображения
cd
Риски
b
Базовые линииКрай листа бумаги
Рис. 5. Базовые линии на эскизе топологии
3. Экспериментальная система автоматического чтения эскизов
слоев топологии плат печатного монтажа
Экспериментальные системы автоматического чтения документов предназначены для отработки методов, алго-ритмов обработки изображений, вводимых в ЭВМ с реальных документов аппаратурой растрового ввода. Такой этап представляется естественным и необходимым, поскольку отсутствует единая методика создания подобных систем.
Рассмотрим одну из таких систем, предназначенную для чтения эскизов слоев топологии плат печатного монтажа.
3.1. Организация данных в памяти ЭВМ.
Графическая информация, считываемая с помощью фототелеграфного аппарата, вначале образует в памяти ЭВМ двумерную двоичную матрицу I , в которой единичные значения соответствуют зачерненным элементарным участкам растра изображения, а нулевые - белым участкам.
В процессе обработки исходная матрица I трансформируется в промежуточное описание, состоящее из матрицы линий и матрицы точек.
Каждый элемент матрицы линий и матрицы точек соответствует одному узлу координатной сетки изображения. Элементы матрицы линий являются 8-ми разрядными. Наличие единицы в каком-либо разряде указывает на прохожде-ние через узел координатной сетки линии, имеющей направление, закрепленное за данным разрядом (см. рис. 6)
Элемент матрицы линий
12345678
Рис. 6. Cтруктура записи элемента матрицы линий
Рис 6.1 Cтруктура записи, описывающей прямолинейный
отрезок печатного проводника.
Элементы матрицы точек указывают наличие точки на изображении в узле координатной сетки. Результат распо-знавания элементов платы представляется в виде массива описаний проводников и контактных площадок. Описание от-резка печатного проводника имеет формат, изображенный на рис. 7.
Тип печатного проводника определяется в соответствии с табл.1.
В первом 32-разрядном слове описания указывается номер узла координатной сетки (элемента матрицы линий), в котором находится один из концов прямолинейного отрезка проводника. Во втором слове - номер узла со вторым кон-цом отрезка (рис.7) .
Описание контактной площадки может иметь один из трех форматов, показанных на рис.7. Для контактной группы микросхемы описание представляется в формате 1, если большая сторона прямоугольника, изображающего группу, горизонтальна или в формате 2, если большая сторона прямоугольника, изображающего группу вертикальна. В форма-те 1 номер узла указывает на нижний конец отрезка единичной длины, изображающего контактную площадку, в форма-те 2 - на левый конец такого отрезка. Формат 3 используется для описания контактных площадок круглой формы.
Параметр "количество точек" определяет тип контактной площадки в соответствии с табл.2, а номер узла указывает на центр контактной площадки
Формат 1
012315161731
000. . .0Номер узла
Формат 2
012315161731
000. . .1Номер узла
Формат 3
02 331
Количество точекНомер узла
Рис.7. Структура записей описания контактных площадок
3.2. Этапы обработки эскиза платы
Процесс ввода и программной обработки эскиза платы печатного монтажа разбит на два этапа. На первом - выпол-няется ввод изображения и преобразование его в матрицы линий и точек, которые представляют собой более компакт-ное по сравнению с черно-белой мозаикой описание эскиза. На втором -осуществляется коррекция матриц линий и то-чек, распознавание элементов эскиза и построение выходного файла.
3.2.1. Формирование матриц линий и точек.
Охарактеризуем более подробно первичную обработку эскиза, т.е. процесс перехода от матрицы I к матрицам ли-ний и точек. Первичная обработка эскиза осуществляется в три этапа:
- обработка линий координатной сетки,
- обработка горизонтальных линий эскиза,
- обработка вертикальных и наклонных линий.
Программная обработка изображения базовых линий дает возможность получить информацию о положении линий сетки на поле изображения. Это позволяет на последующих этапах программной обработки производить корректировку значений координат точек изображения в случае перекоса при установке изображения.
Результатом обработки горизонтальных линий изображения должно быть их описание в матрице линий. Выделение горизонтальной линии изображения выполняется следующим образом. Двоичная матрица I делится на зоны. Каждая зона содержит три строки изображения. При этом положение центральной строки зоны определяется координатами па-ры горизонтальных рисок базовой линии, задающей соответствующую горизонтальную линию координатной сетки. Ка-ждая центральная строка вместе с примыкающими к ней соседними строками образует трехстрочную зону поиска горизонтальных линий. Поиск линии осуществляется по характеристике зоны, полученной в результате дизъюнкции вхо-дящих в эту зону строк. При этом минимальная длина линии считается равной расстоянию между двумя соседними рис-ками координатной сетки.
Для каждой из выделенных в зоне горизонтальных линий находится множество узлов координатной сетки, через которые проходят линии. Соответствующие этим узлам элементы матрицы линии снабжаются описанием горизонталь-ных линий.
В процессе поиска горизонтальных линий в зоне поиска могут обнаруживаться участки, содержащие отходящие в вертикальном или диагональном направлениях отрезки. Информация о них фиксируется соответствующим образом и используется на следующем этапе первичной обработки.
Описания вертикальных и наклонных линий изображения выполняются после анализа фрагментов изображения, со-держащих следы этих линий, обнаруженных на предыдущем этапе первичной обработки. Окрестность узла координат-ной сетки, близ которой были обнаружены следы линий, зондируется в шести направлениях: вверх, вниз, вверх и влево, вверх и вправо, вниз и влево, вниз и вправо от узла. Описания обнаруженных в окрестности данного узла отрезков ли-ний добавляется в соответствующий этому узлу элемент матрицу линий. В случае, если зондирование, инициированное следом линии, не обнаруживает вертикального или горизонтального отрезка, то это означает, что точка выявлена и не-обходимо внести изменения в матрицу точек.
3.2.2. Выделение множеств фрагментов изображений
На следующих этапах осуществляется выделение фрагментов изображений определенного типа и построение опи-саний для них.
Такими фрагментами являются условные графические изображения:
- контактных площадок круглой формы,
- библиотечных групп,
- областей металлизации,
- участков печатных проводников.
Распознавание перечисленных объектов основано на выделении локальных признаков их изображений, характерных для того или иного типа. Такими признаками являются:
- штрихи соответствующей длины и направления в изображении контактных площадок круглой формы,
- специфическое расположение штриха-указателя контура областей металлизации.
В результате обработки сжатого описания изображения платы, представленного в виде матриц линий и точек распозна-вание элементов изображения осуществляется в следующем порядке:
- контактные площадки,
- элементы библиотечного типа,
3.2.4. Результаты эксплуатации системы
1. При использовании масштаба документа 2:1 возникают неудобства. Они обусловлены трудностями изготовления эскиза человеком. Кроме того,
уровень ошибок, допускаемых системой, примерно в 3 раза выше,
чем при использовании масштаба 4:1.
2. При вводе эскизов размерами 250 х 400 мм, выполненных в масштабе 4:1 на листе миллиметровой бумаги с помощью черного фломастера, среднее - границы областей металлизации,
- печатные проводники.
Описания распознанных элементов представляются в виде таблиц. Они содержат информацию о типах элементов и их координатах на поле изображения эскиза.
По мере распознавания элементов изображения описание соответствующих линий и точек удаляется из матриц ли-ний и точек.
Для распознавания элементов библиотечного типа предварительно генерируется их описание в виде фрагмента матрицы линий. Поиск элементов на изображении платы осуществляется наложением построенного таким образом трафарета на матрицу линий эскиза. Распознанные элементы библиотечного типа описываются как множество контакт-ных площадок. Связи между соседними контактами представляются в виде печатных проводников длиной 1 дискрет ко-ординатной сетки.
После распознавания контуров зоны металлизации "покрываются" печатными проводниками, описание которых заносится в массив печатных проводников.
После удаления изображений контактных площадок, элементов библиотечного типа и границ областей металли-зации в матрицах линий и точек остается только изображение печатных проводников.
На нем выделяются прямолинейные участки печатных проводников, определятся их типы. Соответствующие опи-сания заносятся в массив печатных проводников.
3.2.3. Методы обеспечения достоверности
Предусмотрено несколько методов обеспечения высокой достоверности работы системы считывания изображе-ния. К их числу относятся следующие:
- на основе эвристических процедур,
- на основе генерации контрольного изображения.
Кратко рассмотрим существо этих методов.
1. В системе предусмотрены эвристические процедуры, основанные на отыскании предполагаемых мест потери штриха либо появления ложного штриха.
Система обращается к этим процедурам в случаях, когда не удается завершить построение того или иного типа фрагмента изображения. Она сообщает оператору о внесенных коррекциях.
2. Порождаемое системой контрольное изображение при безошибочном вводе и обработке должно выглядеть как исходное. Генерация контрольного изображения осуществляется с помощью матриц линий и точек. В случае обнару-жения несоответствий вносятся исправления. Их ввод осуществляется с помощью директив коррекции.
В директиве коррекции указываются координаты узла координатной сетки и предписывается либо удалить либо поместить линию или точку в этот узел. В случае, если корректировка касается линии, то в директиве должна содержаться информация о ее направлении.
число ошибок было равным 3-4. При этом оператор вносит исправления, относящиеся к 3-4 узлам
координатной сетки. Программная обработка на ЭВМ в среднем составляла величину 30 мин. Время сверки контрольно-го документа - 10 мин.
3. По сравнению со сколочными системами время ввода информации в ЭВМ сокрашалось в несколько раз. Однако программная обработка имеет узко специализированный характер. Это обусловлено жесткими требованиями, накла-дываемыми на линии изображения, а также отсутствием в программе средств распознавания символов.
ЛЕКЦИЯ №4
Тема: “Обработка изображений, автоматически считанных с документации”
4.1. Общие сведения
Обработка изображений представляет собой многоэтапный процесс информационного преобразования, в ходе ко-торого осуществляется последовательный переход от одной формы описания к другой.
В качестве дискретной первичной формы будем рассматривать черно-белую мозаику, получаемую в памяти ЭВМ.
Большая часть изображений черно-белых документов строится с помощью одних и тех же изобразительных средств(линий, символов),поэтому имеет смысл выделить специально этап обработки для получения описания отрез-ков линий. Они задаются координатами его концов и кодов символов с указанием координат их расположения на поле изображения.
Результирующая форма для универсального этапа, которую мы назовем дискретной вторичной формой, состоит из списка отрезков и списка символов.
Запись первого списка состоит из полей, предназначенных для задания координат концов отрезков.
Запись второго списка служит для координатной привязки символа к полю документа и указания кода символа.
Универсальный этап обработки должен обеспечить решение двух задач:
- отделение символов,
- разделение несимвольной части изображения на отдельные элементарные отрезки.
Указанные задачи являются разнородными, поэтому перед их решением целесообразно разложить изображение на символьную и несимвольную части. Каждая из частей подвергается специализированной обработке.
Рассмотрим задачу отделения символов.
4.2. Отделение символов в дискретной первичной форме
Предварительно определим понятие символа.
Назовем группой единиц множество единиц в одной строке матрицы, не разделенной нулями. Две группы единиц, лежащие в соседних строках изображения, с координатами концов по оси абсцисс a, b и c, d называются связными, ес-ли справедливо хотя бы одно из соотношений:
a ? c ? b;
a ? d ? b;
c - 1 = b;
d + 1 = a.
На рис.9.a приведены примеры связных групп единиц, а на рис. 9.б - несвязных. Под символом будем понимать множество связных групп единиц, для которых минимальный охватывающий их прямоугольник имеет размеры, принад-лежащие интервалам размеров символов по высоте и ширине (рис.10 ). Подобное определение символа создает риск отделения части несимвольной информации.
Сущность задачи отделения символов из исходной матрицы I, описывающей изображение в дискретной первичной форме, сводится к нахождению в исходной матрице фрагмента, который содержит символы. Далее каждый такой фраг-мент переписывается в отдельный кадр. Кадр представляет собой двоичную матрицу, размеры которой должны быть не меньше максимальных размеров символов. Затем, содержимое этих матриц анализируется в блоке распознавания.
Рис. 9.Отношение связности групп единиц:
a - связные группы; б - несвязные группы.
Рис. 10. Символ как фрагмент связных групп единиц
4.3. Алгоритм отделения
Выполняется однократный просмотр матрицы I .
При этом осуществляется :
1. Получение информации о том, что связные конфигурации по размерам не превышают размеры символов.
2. Проверка связности между группами единиц (на основе указанных соотношений).
3. Фиксация результатов.
Для фиксации результатов такого просмотра используются маски, каждая из которых представляет собой область прямоугольной формы, состоящую из единиц. При этом используется поле масок M. Поле масок представляет собой двоичную матрицу, совпадающую по размерам с исходным полем изображения I. При совмещении поля изображения с полем масок каждая маска покрывает фрагмент поля I, содержащий связную конфигурацию единиц.
Каждая маска для выделяемой с ее помощью конфигурации имеет минимальные размеры, т.е. играет роль мини-мального охватывающего прямоугольника.
Проверка метрических ограничений, накладываемых на связные конфигурации, называемые символами, осущест-вляется достаточно просто, когда в распоряжении имеется соответствующая маска.
Более подходящей для решения задачи разделения изображения на символьную и несимвольную части является по-лигональная форма описания изображения.
4.4. Полигональная форма.
4.4.1. Граничный контур
Введем понятие граничного контура.
Граничный контур - циклическая последовательность углов поворота границы между черной и белой областями.
Пусть граничный контур обозначен gi.
В граничный контур включаются только узлы, отличающиеся от 180 градусов.
Угол поворота граничного контура обозначим ai .
Угол поворота ai характеризуется следующим набором параметров:
- координаты центра угла - x(ai), y(ai) ;
- направления L1 (ai), L2 (ai) первого и второго луча;
- величина угла V (ai).
В граничном контуре углы упорядочены. Это осуществляется таким образом, что при обходе границы между чер-ным и белым область черного остается справа от направления движения.
Полигональная форма представляет собой совокупность граничных контуров.
На рис.11представлен фрагмент изображения.
12345678
а)
№ углаxyL1L2V
14509090
25390090
б)
Рис. 11. а) фрагмент изображения, б) таблица значений параметров элементов граничного контура.
Достоинства полигональной формы:
- не вносит искажений;
- позволяет выделять резкие изгибы границ черной и белой областей;
- требует меньшего объема памяти (по сравнению с дискретной первичной формой в 10 - 20 раз).
Вопросы построения полигональной формы не будем рассматривать.
4.4.2. Отделение символов
Задача отделения символов формулируется следующим образом: из полигональной формы отобрать те gi, которые описывают границу фрагмента изображения символа.
Изучение реальных изображений показывает, что фрагменты изображения символов более насыщены неоднород-ностями хода границы черно-белого, чем фрагменты изображений несимвольной части. Это дает возможность предло-жить достаточно простой критерий для сортировки границ контуров - gi, входящих в полигональную форму.
К символьным gi будем относить такой граничный контур, для любых двух соседних элементов ak, ak+1 которого вы-полняется условие
R (ak, ak+1) < D ,
где R (ak, ak+1) - расстояние между центрами углов ak, ak+1;
D - некоторая константа, определяемая максимальным линейным размером символа, допускаемым на документе.
Очевидно, что проверка любого gi на принадлежность его множеству символьных граничных контуров осуществля-ется за один проход.
Это не создает трудностей при построении соответствующего алгоритма.
ЛЕКЦИЯ №5
Тема: “Специализированная обработка изображений для эскизов слоев
топологии плат печатного монтажа”
Специализированная обработка изображений выполняется после универсальной обработки. Она зависит от типа до-кумента.
В процессе специализированной обработки выделяются отрезки такого типа, который имеется на документе.
Задачи специализированной обработки:
- обработка базовой линии,
- корректировка положения узловой точки по данным обработки базовой линии,
- выделение контактных площадок круглой формы,
- выделение контуров границ областей металлизации,
- отыскание областей библиотечных групп,
- обнаружение отрезков трасс печатных проводников,
- формирование файла для описания изображения.
Кратко рассмотрим отмеченные задачи.
1) Обработка базовой линии
Выполняется в два этапа:
- обнаружение базой линии;
- построение массива описания реального положения рисок базовой линии на поле документа.
На первом этапе при обнаружении базовой линии используется информация о том, что к базовой линии должны быть отнесены
- все вертикальные элементарные отрезки, имеющие крайнее правое и крайнее левое положения;
- все горизонтальные элементарные отрезки, имеющие крайнее правое и крайнее левое положения.
На втором этапе определяются координаты центра сечения рисок путем усреднения значений ординат концевых то-чек риски, для горизонтальной риски и путем усреднения значений абсцисс для вертикальной риски.
2) Корректировка положения узловых точек
При этом необходимо привязать к ближайшему узлу ряд точек, относительно которых установлено, что они долж-ны быть помещены в одном из узлов координатной сетки. Привязка точки осуществляется в два этапа, раздельно по оси ординат и оси абсцисс.
Рассмотрим привязку по оси ординат. Имеется горизонтальная линия координатной сетки. Она имеет проекции на ось ординат.
Значения yп и yл, являются ординатами правого и левого концов линии координатной сетки.
Документ имеет левый (правый) перекос, если для каждой горизонтальной линии координатной сетки выполняется условие
yп < yл , ( yп > yл ) .
На рис.12 приведена иллюстрация левого перекоса изображения.
Рис.12. Определение расстояния от точки на эскизе слоя топологии до горизонтальной линии координатной сетки
Определение номера горизонтальной линии координатной сетки, к которой должна быть привязана точка а с коор-динатами хa и ya осуществляется по правилу близости этой точки к линии координатной сетки.
При небольшом перекосе изображения в качестве расстояния от точки а до линии координатной сетки можно взять длину вертикального отрезка аb, где b - точка пересечения вертикального отрезка с линией координатной сетки. Точка а привязывается к той линии координатной сетки, расcтояние до которой минимально.
Суть привязки состоит в замене ya на значение ординаты, соответствующей этой линии координатной сетки.
Подобным образом осуществляется привязка произвольной точки по оси абсцисс.
3) Выделение контактных площадок
Выделение площадок круглой формы основано на обнаружении коротких отрезков, входящих в состав креста. Крест соответствует изображению площадки. Обнаружение креста инициирует процесс изучения области его расположения. При этом отыскиваются изображения точек, которые несут информацию о типе контактной площадки.
4) Выделение произвольных конфигураций типа контуров
Нахождение произвольных конфигураций типа контуров является основой для решения задач корректировки поло-жения узловой точки и выделения контактных площадок. При поиске осуществляется обход контура. Обнаружение кон-тура осуществляется тогда, когда возвращаются к исходному отрезку.
Для идентификации обнаруженного контура необходимо знать, является он внутренним или внешним.
Если при просмотре внутреннего контура встречается штрих, характерный для границы области металлизации, то это является основанием для его идентификации.
Изучение внутренних контуров также служит основой для отыскания границ библиотечных групп.
При удалении элементарных отрезков, входящих в состав контактных площадок круглой формы, границ областей металлизации и границ библиотечных групп на изображении остаются только печатные проводники.
Обработка этой части информации сводится к обнаружению указателей типа проводников в разрывах трасс печат-ных проводников и увязки их области действия с отрезками.
5) Генерация завершающего файла
Представляет собой процесс формирования записей, которые несут информацию о найденных обьектах, с после-дующим их включением в файл.
ЛЕКЦИЯ №6
Тема: “Основные проектные процедуры в САПР”
ВВЕДЕНИЕ
Достаточно очевидным является вывод относительно экспертного сопрождения подсистемы моделирования объек-та проектирования.
Рассмотрим множество операций, которые совершает коллектив проектантов над этой подсистемой.
На основе этого анализа представляется разумным установить, насколько поддается формализации инженерная дея-тельность в среде системы автоматизированного проектирования и существует ли возможность опираться на какие-то фундаментальные положения типа формула изобретения. Попутно целесообразно обобщить практический опыт в раз-личных предметных областях и на разных иерархических уровнях проектирования и сформулировать требования к экспертному сопровождению процедур.
ОСНОВНАЯ ЧАСТЬ
, если структура синтезируемого объекта оговорена либо ТЗ, либо единственными условиями физической реали-зуемости (единственный физический принцип, обеспечивающий выполнение ТЗ) .
В результате решения задачи синтеза может возникнуть счетное
Нестрогая классификационная схема проектных процедур представлена на рис.1. На схеме показаны основные про-ектные процедуры, их выбор продиктован следующими соображениями.
Для большинства объектов низшим уровнем проектирования можно считать компонентный.
Понятно, что объект проектирования на этом уровне имеет структурное и параметрическое описания. Композиция отдельных компонент на схемотехническом уровне имеет также двойное описание. То же можно наблюдать на различ-ных уровнях системы автоматизированного проектирования. Любая проектная процедура может быть классифициро-вана на структурную и параметрическую.
Техническое задание на объект проектирования - это всегда некорректно поставленная задача. Поэтому при техно-логии нисходящего проектирования, даже если возможно выполнение процедуры синтеза, проектных решений всегда может быть больше одного по структуре и значениям конструктивных параметров.
Уточнение ТЗ порождает необходимость выполнения процедуры анализа. Заметим, что при восходящем проекти-ровании процедура анализа той или иной гипотехнической структуры объекта проектирования становится едва ли не единственно возможной.
Если система автоматизированного проектирования построена по принципу генерации проектных решений, то процедура оптимизации является одной из основных. Даже в случае нисходящего проектирования в САПР, допускающе-го выполнение синтеза по ТЗ без генерации вариантов, уточнение значений конструктивных параметров осуществляется процедурами оптимизации.
Рис.1. Основные проектные процедуры в САПР
В процессе выполнения проектных процедур приходится всегда приводить в соответствие способ описания ТЗ, проектного решения (которое часто является ТЗ для более низкого уровня структуры проектирования) способу модель-ного представления объекта проектирования.
Преобразованию может быть подвергнуто либо ТЗ, либо собственно модельное представление.
Таким образом, процедура преобразования описаний как структуры так и параметров, является неотъемлемой ча-стью любой САПР.
Многие проектные решения принимаются в среде САПР в формализованном виде, зачастую на метаязыке системы. Поэтому для преобразования описания проектного решения (а иногда и ТЗ) используют процедуру идентификации про-ектного решения (ТЗ).
Множество рассмотренных проектных процедур не является замкнутым по номенклатуре и детализации описания. Однако можно утверждать, что для рассматриваемых здесь предметных областей оно достаточно полно детализирует процесс проектирования.
Последнее утверждение основывается на том, что в указанных предметных областях существует в той или иной ме-ре адекватное модельное представление объекта проектирования в виде некоторого оператора:
La : X ? Y ; a ? A,
здесь X и Y описывают множество входных и выходных сигналов .
Данное соотношение устанавливает связь между фазовыми переменными над множеством {A} конструктивных параметров a.
Теоретико-множественный анализ этого оператора и его отображения для модельного представления объекта про-ектирования показал, что существует счетное множество его преобразований, а также операций над ним: декомпозиция и композиция (преобразование) синтез и анализ. Операции над множеством {A} связаны с поиском единственного ai , которое определяет La .
Возможно также либо определение Y при определенных La {} ,{A} и X, либо La{} при заданных Y и X .
Поскольку Y и X зачастую инвариантны к классу объектов проектирования в данной САПР, неизбежно преобразо-вание описаний (представлений) Y , X , {A}. Формализм представления La {} требует решения задачи идентификации.
АНАЛИЗ ПРОЦЕДУР
1. Процедура анализа
Процедура анализа понимается как процесс представления выходных характеристик объекта проектирования при известных входных воздействиях или начальных условиях по какому-либо описанию объекта проектирования (модельно-му представлению). Одновариантный анализ проводится с целью установления соответствия входных характеристик тре-бованиям ТЗ. Многовариантный анализ направлен на установление в явном, наглядном виде связи между входными данными, характеристиками и конструктивными параметрами.
2. Процедура синтеза
Решение задачи синтеза обеспечивает получение описания объекта проектирования по ТЗ на объект в виде струк-туры и совокупности значений конструктивных параметров. Параметрический синтез проводится конечное множество проектных решений. Если решение одно, синтезируемый объект будем называть "оптимальным по ТЗ". Оптимизация конструктивных параметров приводит к полному описанию объекта проектирования.
Оптимизация допусков проводится с целью установления совокупности значений каждого конструктивного пара-метра по заданному теоретически обоснованному критерию. Оптимизация технических требований обеспечивает на-значение оптимальных (в смысле теоретически обоснованного критерия) требований к выходным характеристикам объ-екта проектирования.
3. Процедуры преобразования
Процедуры преобразования осуществляются над множеством лингвистических и математических переменных.
Их последовательность образует запись либо ТЗ, либо проектного решения, с целью:
а) обеспечить представление ТЗ на метаязыке конкретной САПР,
б) представить в форме, понятной проектанту, то или иное проектное решение, сформулированное на метаязы-ке системы,
в) обеспечить совместимость проектных процедур
Вторая группа преобразования выделена в отдельную процедуру идентификации. Если преобразование осуществ-ляется над неформальным описанием, то оно представимо на языке логики предикатов первого порядка.
Например, если для множества лексем, образующих определенную совокупность требований технического задания Ln, и множества критериев проектных решений Kp ввести предикат Q (Ln , Kp ), обозначающий факт однозначного соот-ветствия L и K любой лексемы li из множества {L} одной и только одной формальной записи критерия Ki p ?{K} , то со-ответствующая формула имеет вид:
(? lin ? Ln ) (? Kip ? Kp) ? Q(Ln, Kp).
Если преобразование не выполнимо за одну процедуру, но существуют две совместимые процедуры и результат преобразования не зависит от порядка их применения, то
(? lin ? Ln, ? Kip ? Kp) ? Q(Ln, Kp) Q (Ln-m , Kp).
Если в качестве терминов, входящих в формулу, используются математические переменные, то операция преобра-зования записывается математической формулой, которая реализуется алгоритмически.
Процедура преобразования, применяемая к тому или иному проектному решению, записанному в виде топологии объекта проектирования, может осуществляться либо объединением (композицией), либо декомпозицией. В свою оче-редь, композиция проектных решений имеет несколько модифицированных представлений и их множество счетно.
То же можно сказать относительно декомпозиции проектного решения. Здесь отметим, что процедура композиции характерна для восходящего проектирования, а декомпозиция - для нисходящего.
4. Процедура идентификации
Процедура идентификации осуществляется либо над множеством данных (из базы данных) когда ставится задача преобразования проектного решения, либо над множеством проектных решений, когда ставится задача занесения его в базу данных.
Указанные задачи, решаемые в соответствии с классифицируемыми процедурами, как отмечалось, сделаны относи-тельно объектов. Они имеют описание в виде цепочек формульных зависимостей (модельных представлений, реализуе-мых алгоритмически) либо цепочек термов, лексем, лингвистических переменных). Поэтому можно предположить, что множество перечисленных процедур факторизуется по классификационному признаку, связанному со способом опи-сания и реализации в среде САПР.
КЛАССИФИКАЦИЯ ПРОЦЕДУР
Каждая из перечисленных процедур может быть отнесена к одному из трех типов процедур:
- формальная,
- формализуемая,
- эвристическая.
Дадим несколько определений.
а) Формальная процедура - совокупность действий, которая порождает проективное (или счетное множество про-ектных решений) без участия проектанта. В этом случае проектант только формулирует задачу: назначает входные дан-ные и указывает критерий проектного решения.
б) Формализуемая процедура - процедура, которая может лишь частично формально описываться в виде какого-либо алгоритма, иногда даже реализующего численный метод, но исходные данные для нее требуют преобразования, а условия ее протекания, критерии проектных решений требуют уточнения не при переходе от одного объекта проектиро-вания к другому, но и процессе ее выполнения.
Проектант может влиять на условия протекания формализуемой и эвристической процедур, руководствуясь только лишь опытом, интуицией, здравым смыслом, причем как своим собственным, так и по выбору, и накопленным в данной САПР.
в) Эвристическая процедура - процедура, которая не поддается никакому формальному описанию, не может быть описана никаким алгоритмом и при определенных условиях не обеспечивает принятия проектного решения.
Приведем примеры процедур.
а) Формальные процедуры:
- анализ чувствительности модели проектирования, применяемой в теории автоматического регулирования,
- синтез оптимального фильтра (решение задачи Винера-Хопфа), когда критерий сформулирован в ТЗ,
- поиск безусловного экстремума целевой функции, сформулированной для задачи непосредственно в ТЗ.
Перечисленные процедуры позволяют оперировать со строгими математическими моделями, являются реализаци-ей конкретно поставленной задачи и инвариантны к критерию проектного решения.
б) Формализуемые процедуры:
- одновариантный анализ объекта проектирования на математической модели при отсутствии полной информа-ции о характере входных воздействий или при нечетко определенной области адекватности,
- синтез структуры объекта проектирования, не имеющего аналогов и прототипов, осуществляемый за счет ис-пользования сочетания различных физических принципов и компонент разной физической природы. "Суммарный" эф-фект не является простой суммой отдельных эффектов, возникающих от использования того или иного физического принципа,
- условная оптимизация значений конструктивных параметров с использованием многомерной целевой функ-ции (многокритериальная некорректно поставленная задача).
Отличительной чертой перечисленных формализуемых процедур является их "экстраполяционный" характер. Во всех указанных совокупностях действий "предсказывается" поведение объекта проектирования на основе гипотетиче-ской информации при ограничениях, которые основаны на фундаментальных физических принципах (закон сохране-ния энергии, не отрицательность времени и т.д.)
Формализуемые процедуры занимают "промежуточное" положение между формальными и эвристическими. С одной стороны, они используют математические модели, с другой стороны, характер их использования является экстра-поляционным.
Например, параметрическая оптимизация, осуществляется с изменением метода оптимизации. Изменение метода происходит в результате анализа как целевой функции, так и влияния ограничений на характер процесса оптимизации.
Видно , что проектная операция может быть только формальной (по определению). Поэтому можно говорить, что формальная проектная процедура всегда состоит из конечного числа проектных операций.
Эвристическая процедура не содержит проектных операций, а формализуемая состоит из несовместимых опера-ций. Их нельзя применять в любой последовательности и в любом сочетании, или их сечение нельзя заранее определить (предсказать).
ЛЕКЦИЯ №7
Тема: “Знания в вычислительных системах (САПР).
Формы представления и способы кодирования.”
ВВЕДЕНИЕ
Одним из первых обобщений, связанных с искусственным интеллектом в САПР, стала работа "Интеллектуальные системы автоматизированного проектирования больших и сверхбольших интегральных схем” В.А.Мищенко, Л.М. Го-родецкий и др. Радио и связь, 1988."
В ней излагаются концепции системы проектирования, "имитирующей деятельность конструктора в части накопле-ния информации об алгоритмах проектируемых схем, модификации исходных алгоритмов для получения необходимых требований технического задания, перебора имеющихся конструктивов для реализации конкретной схемы, решения за-дач оптимизации при синтезе, проверки корректности требований ТЗ в рамках знаний, заложенных в систему.
Понятно, что сформировать требования к "интеллектуальным САПР" независимо от предметной области довольно трудно.
В первую очередь эти вопросы привлекли внимание разработчиков интегральных схем. В этой предметной области в значительно большей степени возможно формализованное представление объекта проектирования, различных проект-ных процедур. Это справедливо, пока речь идет о проектировании алгоритмов, архитектуры и функционально-логической структуры интегральных схем. Как только степень детализации в описании объекта проектирования дос-тигает уровня, на котором требуется оперировать физическими величинами, и если речь идет о моделировании условий протекания физических процессов, то адекватное формализованное описание объекта и процесса проектирования ста-новится все более затруднительным.
Поэтому представляется разумным сопоставить возможности строгого и формализованного подходов к проектиро-ванию. Он заключается в "жесткой "организации программного обеспечения САПР, и чисто эвристического подхода, используемого в экспертных системах, которые функционируют либо на основе нечеткой логики, либо на стохастиче-ских методах обучения.
В радиоэлектронном приборостроении используются сочетания разнообразных физических эффектов. В этой об-ласти как и в оптическом приборостроении и автоматики распространены системы автоматизированного проектирова-ния с традиционной организацией программного обеспечения. Это связано, прежде всего, со значительными трудно-стями создания однородного математического описания систем, сочетающих резко отличающиеся по физической при-роде компоненты.
В данной лекции мы обращаем внимание на те проблемы, которые целесообразно решать за счет использования "жестких" и "мягких" компонент программного обеспечения САПР.
Обращено внимание на поиск точек соприкосновения формализованных и эвристических подходов на основе ана-лиза основных принципов организации и функционирования таких систем применительно к задачам исследования.
Слабые места в формализованном подходе и пути их усиления за счет использования экспертных оценок, опреде-ляющих как характер так и последовательность их применения в сочетании с модельным представлением различных объ-ектов проектирования, также будут рассмотрены.
Предполагается провести анализ способов модельного представления объектов проектирования, которые дают до-вольно строгую формализацию описания различных предметных областей. При этом сделан акцент на проблему адек-ватного описания.
ОБЩИЕ СВЕДЕНИЯ
Наиболее распространенным определением экспертной системы является утверждение о том, что это вычислитель-ная система, оперирующая знаниями специалистов в определенной предметной области и способная принимать реше-ния на уровне этих специалистов.
В этом определении остается неясным, что следует понимать под термином" знания" и что означает способность принимать решения вычислительной системой. Эта неясность возникает, если достаточно строго отнестись к термину "вычислительная система".
Если понимать ее как особым способом организованную совокупность программно-аппаратных средств, то спо-собность ЭВМ принимать решения представляется спорной.
Экспертная система, как всякая вычислительная система, ни в какой момент времени ее создания и функциониро-вания неотделима от пользователя и разработчика.
Первый существенный признак, позволяющий рассматривать экспертную систему как самостоятельный класс вы-числительных систем, заключается в том, что она не должна морально устаревать.
Большинство работ, посвященных экспертным системам, свидетельствует о том, что основу их архитектуры состав-ляет запас знаний о конкретной предметной области. При этом знания понимаются как совокупность правил, опреде-ляющих характер обработки данных, в результате применения которых может формироваться новая совокупность пра-вил.
В приведенных определениях используются понятия данные и знания.
а) ДАННЫЕ в вычислительных системах - закодированные образы объектов реального мира, имеющих количест-венную меру. Наличие количественной меры говорит о возможности сопоставления объектов.
В соответствии с принятым определением в дальнейшем термин "данные" и производные от него ("база данных", "управление базой данных" и др.) будет использоваться для обозначения любых констант (включая логические, строко-вые), переменных и функций, а также множеств, их объединяющих.
б) Опираясь на определение данных, можно сформулировать определение термина " знания ".
Необходимо отметь, что речь идет о знаниях в вычислительных системах, а не о знаниях вообще.
Если измеримость объектов реального мира вытекает из возможности их сопоставления, т.е. установления отноше-ний между ними, то среди этих отношений всегда можно выделить подмножество, которое объединяет закономерности. Такая возможность позволяет в дальнейшем оперировать термином "знания" в смысле образов отношений между изме-римыми объектами реального мира.
Если соотнести теперь определения данных и знаний, то становится ясным, что данные являются частным случа-ем знаний. В самом деле, измеримость объекта, т.е. существования данных об объекте предполагает его сопоставимость с каким-либо другим. Он условно принят за эталон. Это сопоставление позволяет установить отношения между объек-тами (например, равно, больше, одинаково по смыслу и т.п.).
Отношение, в свою очередь, может быть закодировано и представлено в вычислительной системе. Если результат этого сопоставления кодируется константами, переменными либо функциями, то речь идет о представлении данных.
Если же в вычислительной системе представляют (кодируют) способ и результат сопоставления и сущностью этой информации является отношение между данными, которое также может кодироваться константами, переменными и функциями, то такого рода данные в дальнейшем следует называть ЗНАНИЯМИ.
Наиболее распространенными формами представления знаний являются логические, семантические и продукцион-ные модели. Проведем анализ этих форм в сопоставлении с неформальным описанием знаний, составляющих основу инженерной деятельности. При этом будем различать формализуемые и эвристические способы построения моделей.
В инженерной деятельности используют формализованное описание объектов проектирования и проектных проце-дур. С появлением САПР - это используется во множестве формализованных проектных процедур и моделей объектов проектирования.
Объекты проектирования в сочетании со строгими методами оптимизации образуют жесткую структуру, измене-ния которой осуществляются разработчиками или специальными лицами, администрирующими информационную компоненту и сопровождающими систему автоматизированного проектирования. Они не являются специалистами в данной предметной области.
ЛОГИЧЕСКИЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ
Предварительно остановимся на изложении некоторых понятий формальной теории.
Формальная теория задана, если определены четыре множества B, F, A, R : S = {B, F, A, R}, где
B - счетное множество базовых символов (алфавит) теории S ;
F - подмножество выражений теории S (формулы теории );
A - выделенное множество формул, образующее аксиомы теории S (множество априорно истинных формул);
R - конечное множество отношений между формулами ( правила вывода).
Формальная теория S называется РАЗРЕШИМОЙ, если найдется единая процедура, которая позволяет узнать для любой данной формулы, существует ли ее вывод в S.
Формальная теория S называется НЕПРОТИВОРЕЧИВОЙ, если не существует такой формулы ai ? A, чтобы ai и ?ai были выводимы в S.
Теория исчисления предикатов определяется следующими множествами:
АЛФАВИТ:
знаки пунктуации (,) . ;
пропозициональные связки ?, ? ,? , ?
знаки кванторов ? , ?
символы переменных хk , k=1,2,...,n
символы функциональных букв fkn
символы предикатных букв Pk
ВЫРАЖЕНИЯ: множества выражений строятся над множеством символов алфавита с помощью термов и элемен-тарных формул.
ТЕРМЫ: символы переменной или константы, например X1,X2, ...,Xn или fk (X1,X2, ...,Xn)
ЭЛЕМЕНТАРНЫЕ ФОРМУЛЫ: совокупность предикатных букв, термов и знаков пунктуации, например,
Pk (X1,...,Xn)
ПРАВИЛЬНО ПОСТРОЕННЫЕ ФОРМУЛЫ: совокупность элементарных формул и пропозициональных связок, на-пример:
Pk (X1 ,...,Xn) = P1 (X1,...,Xn).
С помощью выражения (?X)D (A) обозначается область действия квантора всеобщности. Это означает: для любого X из D существует правильно построенная формула A.
С помощью выражения (?X)D (A) устанавливается существование такого X из D, для которого справедлива пра-вильно построенная формула.
Области значений правильно построенных формул кодируются таблицами истинности. Они устанавливают значе-ния 0 либо 1 ("ложь" либо "истина") формулам:
?A , A ? B, A ? B
НЕЧЕТКОЕ ОТНОШЕНИЕ определяется оператором R и операцией "?": R ? A = B, где A - входное нечеткое множе-ство, B - выходное нечеткое множество.
Не будем раскрывать данную запись на уровне системы алгебраических уравнений.
Если истинность обозначена для всех наборов интерпретаций, ее называют общезначимой, в противном случае она невыполнима.
Говорят, что формула A логически следует из формул B1,B2,...,Bi тогда и только тогда, когда интерпретация форму-лы B1,B2,...,Bi совпадает с интерпретацией A. (B1,B2,...,Bi ? A)
В этом случае B1,...,Bi - посылки, а A - заключение логического следования.
В сжатой форме это отношение обозначается как B1,B2,...,Bi => A
На практике имеет большое значение теорема дедукции, согласно которой A является логическим следствием B1,...,Bi тогда и только тогда когда формула B1,B2,...,Bi общезначима.
Известно использование исчисления предикатов для доказательства теорем. Методы доказательства теорем основы-ваются на том, что если формула исчисления предикатов общезначима, то возможна проверка ее общезначимости на основе исчисления предикатов.
Элементы исчисления предикатов используются для кодирования аксиоматики того или иного математического аппарата. Это позволяет использовать его в технологических приложениях для записи спецификаций программ и как следствие для аналитического преобразования формул, модельного представления объектов проектирования и описания проектных процедур, а также для проверки на корректность и полноту программных реализаций систем аналитических вычислений.
НЕЧЕТКИЕ МНОЖЕСТВА И НЕЧЕТКАЯ ЛОГИКА
Многие продукционные модели представления знаний опираются на аппарат нечетких множеств и нечеткой логики Л.Заде с лингвистическими, а не числовыми значениями истинности.
Рассмотрим некоторые основные понятия.
Установлено, что нечеткость возникает тогда, когда элемент w?W обладает некоторым свойством А, имеющим субъективную окраску (по мнению различных экспертов).
Функция принадлежности ?A( ) рассматривается как функция вещественного аргумента. Она определена на интер-вале [0,1].
Можно считать, что ?A: u -> [0,1] ставит в соответствие каждому u число ?A(u) из интервала [0,1], характеристическую степень принадлежности u подмножеству A. Нечеткое множество А будет обозначаться как объединение
А = ??A(ui) / ui, либо А = {?1 / u1 + ...+ ?n / u n}
В случае, когда множество непрерывно A = ??A(u) / u.
Определим понятие множества уровня ?.
МНОЖЕСТВО УРОВНЯ ? это четкое множество A? элементов универсального множества U, степень принадлеж-ности которых множеству А больше или равна ?:
A? = {u / ?A(u) > ?}, где ? - в общем случае может быть нечеткой константой.
ОБЪЕДИНЕНИЕ множеств по ?
??A = ?? ?A?
Операция ДОПОЛНЕНИЕ
?A = ?u(1- ?A(u))/u
Операция ОБЪЕДИНЕНИЕ
A ? B = ?u(?A(u) ? ?B(u)) /u
Операция ПЕРЕСЕЧЕНИЕ
A ? B = ?u(?A(u) ? ?B(u)) /u
Аппарат, построенный на моделях нечетких операндов, широко используется в процедурных способах представле-ния знаний. С его помощью осуществляется, в основном, эвристическое представление. Конкретные формы, в которых оно реализуется, зависят и от вычислительной среды, СУБД, от концептуальной модели базы знаний и от общей концеп-ции проекта той или иной системы.
СЕМАНТИЧЕСКИЕ СЕТИ
Семантические сети строятся с помощью ориентированных графов. Вершины сети соответствуют объектам, а дуги семантическим отношениям.
Среди объектов выделяют понятия, свойства и события.
Семантические отношения можно условно разделить на лингвистические, логические, теоретико-множественные и квантифицированные. Применительно к задачам организации вычислительной среды САПР лингвистические отношения относятся к средствам доступа. К логическим отношениям относятся отношения типа: дизъюнкция, конъюнкция и отри-цание.
Теоретико-множественные отношения рассматриваются как проявление категорий части и целого, затрагивают ие-рархическую структуру той или иной САПР в целом. Пример такой сети приведен на рис.1.
Семантические сети условно классифицируют на интенсиональные и экстенсиональные.
ИНТЕНСИОНАЛЬНАЯ сеть устанавливает те отношения между объектами, которые отличаются объективностью и повторяемостью.
ЭКСТЕНСИОНАЛЬНАЯ сеть кодирует отношения между конкретными фактами, объектами и событиями, т.е. ме-жду данными.
Наибольшее распространение семантические сети получили в концептуальных моделях баз данных и поэтому имеют распространение в САПР.
При использовании в САПР семантические сети применяются в семантическом анализе при организации диалога на предметном языке. Этот анализ проводится после морфологического и синтаксического разбора. Далее используется либо прямое преобразование синтаксических отношений в семантические с применением встроенных правил (фильт-ров), либо преобразование осуществляется на основе соответствий, указанных в моделях управления.
Рис.1. Пример сети, используемой для представления отношений между моделями и макромоделями объекта про-ектирования в САПР.
Однако, если предметная область САПР основана на описании естественных объектов, то размерность семантиче-ской сети становится необозримой. В этом случае предпочтительнее использование представления в виде фреймов.
ФРЕЙМЫ
Приведем определение фрейма.
ФРЕЙМ - поименованная семантическая сеть, являющаяся элементом множества, построенного на операции связи с помощью одного или нескольких узлов.
Подобное определение не противоречит с трактовкой фрейма как структуры данных, формализовано отображаю-щей объектно-субъективные отношения декларативным либо процедурным образом и содержащей постоянную часть или переменную. О последней говорят как о совокупности слотов ( переменная часть фрейма ).
Такая структура образуется множеством троек вида:
{ F, (S1, GS1, PS1), ..., ( Si, GSi, PSi), ..., (Sl, GSl, PSl) },
где F - имя фрейма , Si - имя слота, GSi - значение слота, PSi - процедура, связанная со слотом.
При работе с фреймами допустим любой уровень вложений, поскольку значением слота некоторого фрейма может быть любое имя фрейма.
Сеть фреймов реализует модель объекта проектирования на основе фрейма "преобразование" и отражает свойство объекта проектирования в целом и его отдельных компонент (узлов, звеньев, макромоделей - совокупности звеньев). Порядок инициализации процедур для преобразования данных определяется слотами параметров моделей.
На рис. 2 приведена сеть фреймов, реализующая модель объекта проектирования.
Рис. 2. Сеть фреймов, реализующая модель объекта проектирования в соответствии с иерархией, отображенной на рис.1.
Для инженерной деятельности характерны специфичные формы представления знания. Это связано со следующи-ми обстоятельствами:
1) c необходимостью описания последовательности принятия проектных решений в форме, удобной для представления в ЭВМ.
2) c отождествлением ТЗ на объект проектирования с той или иной последовательностью действий проектанта.
3) с оценкой корректности ТЗ и адекватности моделей объекта проектирования.
Первое требование возникает, если САПР строится целиком на основе базы знаний и не позволяет оперировать строгим математическими моделями объектов проектирования. Такой путь предполагает использование экспертных систем для накапливания знаний инженеров высокой квалификации и последующего их "тиражирования" в вычисли-тельных системах.
Второе требование также характерно для использования свойств экспертных систем в полном объеме, а также для САПР, называемых "интеллектуальными".
Третье требование возникает при необходимости построить САПР, адаптирующиеся к пользователю и развиваемые проектантами.
Наиболее интересным приложением для интеллектуальных САПР является построение обучаемых мониторов, на-зываемых интеллектуальными планировщиками. Подобные мониторы реализованы с использованием аппарата сетей Петри (которые мы здесь не рассматриваем).
МЕТОДЫ КОДИРОВАНИЯ
Рассмотренные способы представления знаний могут иметь самую различную программную реализацию в вы-числительных системах. Во многом эти способы зависят от характера отношений между данными, которые моделиру-ются знаниями.
В инженерной практике исторически сложилось два способа документирования проектных решений - текстовый и графический.
Наибольший интерес представляет графический способ документирования.
Технологические и пользовательские аспекты обработки графической информации в системах проектирования и конструирования изучены достаточно глубоко.
Двухуровневый характер кодирования таких изображений, как чертежи, графики позволяет сводить их описание к лексическим примитивам (линия, круг, точка и т.п.). Следовательно, представление знаний с помощью таких "кодов" так или иначе сводится к способам, уже рассмотренным ранее.
Особое место занимает графическая информация, кодируемая полутоновыми многоуровневыми изображениями реальных и искусственных объектов. Наиболее мощным арсеналом программно-аппаратных средств обработки, хране-ния и представления таких изображений располагает цифровая голография.
Использование этих средств позволяет не только решать задачи препарирования изображений и распознавания об-разов, но и строить обучаемые вычислительные системы.
ЛЕКЦИЯ №8
Тема: “Экспертная система для автоматизированного проектирования”
ВВЕДЕНИЕ
Экспертная система для решения задач автоматизированного проектирования является, в свою очередь, вычисли-тельной системой.
Она должна удовлетворять следующим требованиям:
1.Принимаемые с помощью системы решения должны соответствовать уровню эксперта-профессионала.
2.Cпособы принятия решений (метарассуждения) в любой момент времени должны воспроизводится в форме, понят-ной как эксперту, так и пользователю.
3.Система должна адаптироваться к пользователю за счет возможности менять как формулировки запросов и задач, так и последовательность их возникновения.
4.Cистема должна обладать возможностью использовать, приобретать и хранить общие и частные схемы рассуждения, построенные на не полностью достоверных данных и символьных преобразованиях.
5.В процессе жизненного цикла система должна обладать свойством ревизии данных и схем рассуждений.
ЗАДАЧИ, РЕШАЕМЫЕ ЭКСПЕРТНОЙ СИСТЕМОЙ
Перечислим задачи, которые способна решать экспертная система:
1.Задачи не могут иметь числовой интерпретации.
2.Цели, достигаемые при их решении, не могут быть представлены в виде целевой функции.
3.Комбинаторные методы перебора невозможны.
СТРУКТУРНАЯ СХЕМА ОБОБЩЕННОЙ ЭКСПЕРТНОЙ СИСТЕМЫ
Перечислим основные компоненты такой системы. К их числу относятся следующие:
1.Лингвистический процессор
2.Подсистема логического вывода.
3.База знаний.
4.Подсистема ревизии знаний.
5.Рабочая память.
На рис.1 показана структурная схема обобщенной экспертной системы.
Рис.1. Структура обобщенной экспертной системы.
Лингвистический процессор осуществляет связь остальных компонент с пользователем или экспертом на алгорит-мическом языке.
Подсистема логического вывода обеспечивает построение той или схемы рассуждения.
База знаний предназначена для хранения и обработки знаний, представленных логическими, продукционными либо семантическими моделями.
Подсистема ревизии знаний позволяет пользователю либо эксперту вмешиваться в процесс подготовки принятия решения за счет объяснения (отображения) промежуточных действий в системе.
Рабочая память обеспечивает хранение промежуточных данных и их обмен между компонентами системы.
В некоторых работах по искусственному интеллекту можно встретить несколько другое представление обобщенной экспертной системы, причем, принципиальным отличием может явиться наличие в структуре подсистемы приобрете-ния и интерпретации знаний. Однако в таких системах, как EURISKO, роль такой подсистемы выполняет подсистема ло-гического вывода совместно с подсистемой ревизии знаний, а в системе MYSIN ее невозможно выделить как отдельное программное средство. В системах, построенных по технологии "prototyping" - ИНТЕРЭКСПЕРТ (GURU), ЭКСПЕРТИЗА, т.е. на основе оболочек, также трудно выделить такой программный модуль, который обеспечивал бы приобретение знаний.
Рассмотрим подробнее структурные компоненты экспертной системы.
КОМПОНЕНТЫ ЭКСПЕРНОЙ СИСТЕМЫ
ЛИНГВИСТИЧЕСКИЙ ПРОЦЕССОР
Лингвистический процессор обеспечивает взаимодействие пользователя либо эксперта с программно-аппаратной частью экспертной системы путем преобразования (трансляции, конвертирования, интерпретации) предложений на проблемно-ориентированном (чаще на естественном) языке в предложения на внутреннем языке (метаязыке) и наобо-рот.
На рис.1 не показано, что в этих преобразованиях участвует база знаний, поскольку во многих экспертных системах лингвистические процессоры реализуются отдельным модулем, имеющим программно-аппаратный вид.
Достаточно общее название этой структурной единицы позволяет рассматривать под этим названием самые раз-личные программные и программно-аппаратные реализации. Они независимы от способа кодирования сообщения: ре-чевой ввод, ввод с алфавитно-цифровой клавиатуры, с сенсорного устройства и т.д.
В любом случае считается, что входными данными лингвистического процессора являются цепочки символов, представленных во внутреннем коде системы, а выходными - либо цепочки, синтезированные на языке деловой прозы для человека, либо цепочки на метаязыке системы.
Преобразование лексических единиц на естественном языке возможно в процедурной, декларативной или смешан-ной форме. Для декларативной формы характерно существование некоторого словаря и морфологический анализ сво-дится к сопоставлению соответствующих лексем.
Процедурный способ морфологического анализа основывается на определении последовательности операций, ко-торые необходимо осуществить для определения значений морфологических параметров. При этом под морфологией понимается система правил порождения слов.
База знаний, над которой строится лингвистический процессор, содержит словарь, множество фильтрующих про-цедур и семантическую сеть. С помощью словаря осуществляется представление знаний о словах (лексемах).
Фильтрующие процедуры реализуют правила анализа и синтеза лексем, а семантические сети кодируют смысло-вые структуры предметной области.
Структура основной части лингвистического процессора и взаимодействие его элементов условно представлены на рис.2.
Рис.2. Структура лингвистического процессора
В процессе анализа сообщения пользователя выделяются корни слов, идентифицируется совокупность корней по словарю, хранящемуся в рабочей памяти, проводится морфологический разбор и после семантического разбора поро-ждается сообщение на метаязыке системы.
При синтезе сообщения чаще всего используется множество формальных шаблонов, которые выбираются в соот-ветствии с семантикой сообщения и заполняются в соответствии с его морфологией и синтаксисом.
Лингвистический процессор систем ИНТЕРЭКСПЕРТ, ЭКСПЕРТИЗА позволяет осуществлять связь на естествен-ном языке и рассчитан на распознавание до 500 слов и команд. Процесс формирования интерфейса реализуется с по-мощью меню. Оно предлагается пользователю всякий раз, когда введенное предложение на естественном языке содер-жит слова, не содержаржащиеся в словаре процессора.
Меню предлагает пользователю варианты типа:
?"временное изменение",
?"постоянное изменение",
?"более длинная фраза",
?"игнорировать слово" ,
?"снять запрос".
В первом режиме составляется временное определение, которое хранится до следующего запроса. При этом нерас-познанное слово автоматически приводится в семантическое соответствие с синонимом из словаря в течение текущего запроса.
экспертной системе позволяет со временем снимать разграничения в функциях эксперта и пользователя.
Возможности наиболее распространенных в настоящее время экспертных систем в области ревизии знаний пока ограничены. В основном, пользователю объясняют причины запросов и раскрывают Во втором режиме проводится по-стоянное доопределение словаря соответствующим синонимом.
В третьем режиме синонимы вводятся уже не для отдельных слов, а для словосочетаний.
Четвертый режим позволяет пользователю понизить избыточность в сообщении, если какое-то слово в фразе, коди-рующей запрос, нераспознано процессором, а пятый позволяет прекратить бесплодные попытки разъяснить принципи-ально неопознанную фразу запроса.
Лингвистический процессор ИНТЕРЭКСПОРТ расширен на область графического представления данных в виде таблиц и графиков.
ПОДСИСТЕМА ЛОГИЧЕСКОГО ВЫВОДА
Подсистема логического вывода, предназначенная для генерации рекомендаций по решению прикладной задачи на основе информации, находящейся в базе знаний, строится на основе теории машины Поста.
На структурной схеме, показанной на рис.3, определены связи между компонентами этой подсистемы в соответст-вии с принципами функционирования машины Поста. Согласно наименованию, подсистема порождает правило на ос-нове импликации вида:
Ri : Ii ? Ri’, где Ri - правило продукции, извлекаемое из базы знаний, Ii - условие применения правила Ri,
R’ - порождаемое правило, которое может быть помещено либо не помещено в базу знаний.
Рис.3. Структура и принцип функционирования интерпретатора
В процессе решения той или иной задачи в подсистеме производится интерпретация (означивание) того или иного правила и выполнение действий, определяемых этим правилом. Выбор (идентификация) того или иного правила основан на сопоставлении условий Ii и в общем случае приводит к нескольким правилам одновременно. При этом возможно по-рождение порождается конфликтного набора.
Разрешение конфликтного набора осуществляется специальной процедурой, называемой селектором. В селекторе заложена определенная стратегия.
Для оперативного хранения промежуточных данных по условиям Ii, во многих системах предусматривается РАБОЧАЯ ПАМЯТЬ.
Например, в системе ИНТЕРЭКСПЕРТ, а точнее, в ее инструментальной среде, логический вывод осуществляется либо с помощью процедур, разработанных на уровне языка структурного программирования, либо с использованием эвристик, реализованных в среде.
Различают прямую и обратную аргументацию.
В первом случае каждое правило, занесенное с помощью средств, обрабатывается в последовательности от посылки к заключению. Если предложение, реализующее посылку, истинно, то правило инициируется и происходит переход к заключению. В противном случае возобновляется проверка истинности до момента, когда все правила не будут исчер-паны.
Во втором случае в машине логического вывода распознается то правило, в заключении которого содержится наи-более близкое к проблеме решение.
Если посылка правила не определена, производится перебор неизвестных переменных в посылке правила примени-тельно к новым условиям. Операции повторяются циклически до нахождения решения либо до определения неразреши-мости задачи.
Посылки к правилам формируются с помощью нечетких множеств, причем допускается использование нечетких чисел и лингвистических переменных. В инструментальной среде ИНТЕРЭКСПЕРТ вводятся в рассмотрение "факторы уверенности". Для них определена шкала в диапазоне от 0 до 100 . Допускается формулировка посылок четкими пере-менными, полями базы данных, статистическими переменными, переменными с индексами.
Доступ к машине логического вывода осуществляется двумя основными путями: путем предложения правила и пу-тем запроса на консультацию.
Первый путь реализуется предложением, имеющим форму:
правило: "имя правила"
ЕСЛИ : < предложение>
ТОГДА: < заключение >
Предложение реализуется выражением, которое связывает операнды и операции логических отношений. Заключе-ние строится из любого числа операндов, в состав которых входят переменные и коды операций.
Правило инициируется только после того, как будут установлены значения всех переменных, входящих в состав операндов и операций.
Таким образом, структура набора правил образуется предложениями: описания типов используемых переменных, правил, консультаций, объяснений правил (которые, вообще говоря, не обязательны), завершения набора и завершения текста набора правил.
С помощью специального редактора набора правил осуществляется построение, изменение состава и структуры и компиляция набора правил. После компиляции образуется исполнимая экспертная система, порожденная в оболочке системы. Программирование машины логического вывода, таким образом, формально мало чем отличается от обычно-го программирования. Отличие возникает при оперировании с нечеткими переменными и нечеткими условиями.
Основные типы переменных, определенные в среде: символьные, числовые, логические и неизвестные. Основные виды: ячейки, поля, рабочие переменные, фиксированные переменные среды.
Отдельный вид составляют нечеткие переменные, определяемые в рассматриваемой среде как и переменные набо-ра. Последние имеют нечеткие подмножества значений любого сочетания перечисленных типов. Каждое значение не-четкой константы определяется соответствующим значением функции принадлежности, определяемым в среде как "фактор уверенности".
Например, переменная набора
Y = {1/0.5; 2/0.5; 3/0.5}
в инструментальной среде записывается таким образом:
Y = {1 cf50, 2cf50, 3cf50}.
C использованием факторов уверенности осуществляется и формирование набора правил. Учет этих факторов вы-полняется путем введения факторов уверенности: посылки, заключения и переменной заключения.
Основные операторы, принятые в инструментальной среде операторы отношений:
?= - проверка на равенство ,
?<> - проверка на неравенство,
?>= - проверка на превышение или равенство,
?< - проверка на превышение,
?<= - проверка на нестрогое равенство,
?> - проверка на превышение,
?IN - проверка на соответствие одного элемента другому.
Операции в машине логического вывода могут описываться в выражениях, использующих действия над функциями принадлежности. Это могут быть:
?операция "И" и группируемые вокруг нее
min (a, b), ab, (ab+ min(a,b)/2), ab(2-max(a,b))
?либо операция "ИЛИ" и группируемые вокруг нее
max(a,b), (a+b-ab), (max(a,b (a+b-ab))/2).
Таким образом, в инструментальной среде можно реализовывать арифметику нечетких чисел и алгебру нечетких высказываний.
Аналогичным образом осуществляется функционирование машины логического вывода и в системе ЭКСПЕРТИЗА.
ПОДСИСТЕМА РЕВИЗИИ ЗНАНИЙ
Подсистема ревизии знаний является частью любой экспертной системы, так как она обеспечивает адаптацию поль-зователя к вычислительной системе. Поскольку всякая САПР так или иначе связана с вычислительной системой, то свой-ство эксперной системы по отображению промежуточных и окончательных решений позволяет эксперту менять состав продукционных правил, а пользователю состав и содержание запросов. Это свойство помогает разрешить многие про-блемы, стоящие перед разработчиками САПР и проектантами.
Благодаря такой подсистеме в развитых экспертных системах (например, в EURISKO) появляется возможность вли-ять на базу знаний и на стратегию управления продукционной системы, реализуемой в машине логического вывода.
В инженерной деятельности проектные решения выбираются на основе глубинных причинно-следственных связей. Они далеко не всегда имеют формальное или какое-либо формализованное представление. Поэтому понимание проек-тантом хода рассуждений в процессе консультации в содержимое базы знаний.
Несколько слов относительно состава и назначения базы знаний.
БАЗА ЗНАНИЙ
В экспертных системах знания могут представляться в декларативной, процедурной, управляющей формах и в виде метазнаний.
Декларативные знания представляются как факты, формируемые пользователями, процедурные - как правила, пред-ставляемые экспертами. Управляющие знания - набор стратегий, определяющих функционирование подсистемы логи-ческого вывода. Метазнания представляются пользователю и эксперту в процессе функционирования экспертной сис-темы. С их помощью раскрывается ее состояние, структура и схема рассуждения. Метазнания - основной источник раз-вития экспертной системы.
ПЕРСПЕКТИВЫ РАЗВИТИЯ САПР
На основе проведенного анализа структуры эксперной системы, можно утверждать, что такая вычислительная среда имеет прямое применение для инженерной деятельности как средство автоматизации проектных работ, если проектиро-вание ведется от прототипа, по восходящей технологии или на высших иерархических уровнях той или иной системы проектирования.
Однако, если объект проектирования можно формально описать, возникает потребность, с одной стороны, исполь-зовать приемы, характерные для инженерной деятельности, а с другой - привлечь знания математиков для использования формальных методов принятия решения.
Кроме того, дальнейшее развитие САПР, по мнению многих разработчиков, должно идти по пути создания вычис-лительных систем, которые "лояльны" к пользователю, легко тиражируются и обладают свойством развития.
В ближайшее время при построении САПР необходимо обеспечить решение следующих задач:
?обучение пользователя, которое сводится к обучению входным языкам, представлению справочной информации, адаптированной к характеру запроса, диагностике ошибок и сопровождению пользователя в процессе проектирова-ния;
?обучение САПР, предполагающее настройку системы на конкретную предметную область или класс проектных про-цедур;
?организация диалога в процессе проектирования с целью описания объекта проектирования, технологического зада-ния и заданий на выполнение проектных процедур;
?изготовление проектной и справочной документации, оформляющей проектные решения;
?контроль за функционированием системы и отображение статистических данных о количестве и качестве проектных решений.
Перечисленные задачи во многом совпадают с требованиями, которые предъявляются к обобщенной эксперной системе.
Дополнительно можно сформулировать две задачи:
?обеспечение возможности развития САПР в части совершенствования методов моделирования объектов проектиро-вания и расширения числа проектных процедур, основанных на формализованных методах;
?обеспечение возможности накопления и обмена опытом проектантов в единой вычислительной среде.
Эти задачи не могут решаться в среде экспертной системы, структуру которой мы рассмотрели. Ясно, что ее ориен-тация на обработку не формализуемых, эвристических данных, определяющая структуру и принципы функционирова-ния, не позволяет использовать ее для обработки моделей объектов проектирования, построенных на строгой или даже приближенной математической основе.
ВЫВОДЫ
1.Основное свойство вычислительных систем, называемых экспертными - менять свою структуру и содержание в про-цессе функционирования - отвечает основному требованию, предъявляемому к САПР - возможности адаптироваться к характеру проектных работ. Принцип обучаемости эксперных систем за счет изменений структуры и содержания должен сочетаться с принципом неизменной совокупности формализованных процедур, на котором строятся САПР с детерминированной структурой.
2.Реализация САПР, построенных на концепции развития с помощью проектантов, возможна на основе учета их мне-ний и опыта, накопленного в процессе проектных работ с применением технологических принципов, используемых при разработке экспертных систем. Способы учета экспертных оценок проектантов, методы сочетания формализуе-мых и эвристических алгоритмов связаны с предметной областью САПР в части моделирования объектов проекти-рования, организации диалога и принятия решений.
3.В зависимости от степени детализации описания объекта проектирования меняется сочетание эвристических и фор-мализованных способов представления знаний. Чем выше иерархический уровень САПР, тем в большей мере необ-ходимо использовать в качестве инструментальных средств вычислительные системы класса экспертных. На
уровнях, допускающих строгую формализацию в модельном представлении объекта проектирования, структура про-граммного обеспечения может выполняться на основе четких алгоритмов. Если объект проектирования не всегда имеет адекватное модельное представление на определенном иерархическим уровне, структура соответствующей САПР должна сочетать четкие и нечеткие алгоритмы.
4.Направления в разработке САПР:
?использование экспертных систем непосредственно для автоматизации проектных работ, не поддающихся форма-лизованному описанию (как правило, на высших иерархических уровнях);
?использование отдельных структурных компонент экспертной системы для интеллектуализации САПР с целью обеспечения большей лояльности к пользователю;
?разработка САПР с экспертными компонентами на основе сочетания формализованных и эвристических представ-лений знаний с целью обеспечения их развития пользователями и экспертами без участия разработчиков САПР.
ЛЕКЦИЯ №10
Тема: ”Процесс проектирования технологических операций”
1. Классификация моделей объектов проектирования
ОБЪЕКТ инженерного проектирования - материальный объект искусственной природы, который должен быть создан для разрешения определенной проблемы, возникающей или выделенной в одном из фрагментов действительно-сти.
В машиностроении в качестве объекта инженерного проектирования выступают технологические операции опреде-ленных классов.
Совокупность СВОЙСТВ объекта проектирования делится на внешние Y и внутренние Х свойства.
ВНЕШНИЕ свойства объекта проектирования разделяются на два подмножества:
- существенные (функциональные или свойства назначения) Yн, которые подлежат непосредственной реализации при использовании объекта по прямому назначению,
- утилитарные (нефункциональные) - Yу, присущие любому реальному объекту (объем, масса, стоимость и др.).
Справедливо соотношение: Y = Yн U Yу.
ВНУТРЕННИЕ свойства проектирования характеризуют физический, химический и др. процессы, а также техниче-скую форму его реализации как принцип действия данного объекта проектирования.
МОДЕЛЬ ОБЪЕКТА M(О) - приближенное описание какого-либо класса явлений, выраженное с помощью матема-тической символики.
Модели объектов проектирования классифицируют по ряду признаков:
- способу построения,
- степени полноты отображения рассматриваемых сторон объекта,
- степени общности в отношении к объекту,
- пригодности для целей прогнозирования,
- назначению.
Кратко рассмотрим каждую из групп моделей.
А. По способу построения различают модели семиотические (знаковые) и материальные (предметные ).
Семиотические модели предназначены для отображения с помощью знаков объектов различной природы, свойств этих объектов, а также различных отношений между объектами свойствами и значениями свойств.
Материальные (предметные) модели включают натурные (экспериментальные, лабораторные, опытные образцы объектов); геометрически подобные (пространственные макеты); физически подобные (модели, обладающие механиче-ским, кинематическим, динамическим и другими видами физического подобия с объектом); предметно-математические (созданными с помощью ЭВМ).
Б. По степени полноты отображения (представления) объекта модели могут быть полными - M(O); неполными (различ-ной степени неполноты по содержанию или объему) - M'(O), M"(O),..., Mn (O).
B. По степени общности в отношении к оригиналу выделяют модели описания Mo(O) (отображают характерные стороны объектов); модели-интерпретаторы Mi(O) (представляют отдельные объекты, входящие в состав некоторого класса и учи-тывают особенности их частной реализации); модели - аналоги Ma(O) (различные по форме представления, но равные между собой степени общности в отношении оригинала).
Г. По характеру воспроизводимых сторон объекта проектирования выделяют субстанциональные модели SbM(O) (ха-рактеризуют пространство возможных состояний объекта, примеры: справочники, описания типовых проектных реше-ний, технологических операций); функциональные модели FnM(O) (в отличие от моделей SbM(O) характеризуют объект только в аспекте определенных его отношений со средой или другими объектами. Отображают поведение объекта, его приспособленность к определенным воздействиям); структурные модели StrM(O) (характеризуют внутреннюю органи-зацию объектов); смешанные модели.
Д. По пригодности для целей прогнозирования модели относятся к пригодным и непригодным.
Е. По назначению модели могут быть целевыми и продуктивными.
Целевые модели Mц(O) призваны в явной форме отображать цель создания, назначение объекта проектирования.
Продуктивные модели Mпр(O), под ними понимается совокупность технической документации на объект.
2. Модельное представление технологических операций
По способу построения различают модели семиотические (знаковые) и материальные (предметные).
Семиотические модели предназначены для отображения с помощью знаков объектов различной природы, свойств этих объектов, а также различных отношений между объектами, свойствами и значениями свойств. Они делятся на язы-ковые (логико-лингвистические - символьные структуры, входящие в некоторую систему, логико-математические - упо-рядоченные знаковые цепочки); неязыковые (наглядно-образные, например, схемы, эскизы, чертежи).
Материальные модели включают:
- натурные (экспериментальные, лабораторные, опытные образцы объектов);
- геометрически подобные (пространственные макеты );
- физически подобные (модели, обладающие механическим, кинематическим, динамическим и другими видами физического подобия с объектом;
- предметно-математические, созданные на базе ЭВМ и воспроизводящими объекты в определенном масштабе времени и реализующими подобие объектов.
Рассмотрим логико-математические модели.
Логико-математические модели любых объектов M(O) обычно определяются как множества (М1,M2,...,Mk) с задан-ными наборами отношений (r1,r2,...,rm). При этом справедливо следующее выражение:
M (O) = <(M1,M2,...,Mk), (r1,r2,...rm)> .
(Под сигнатурой понимается набор идентификаторов (имен) отношений, входящих в состав модели, с указанием их арности.
Моделью Mk(О) в сигнатуре Om называют пару
В моделях технологических операций M(TO) будем квалифицировать множества (M1,M2,...,Mk) как базовые, если значения их элементов могут быть непосредственно интерпретированы как значения внешних или внутренних свойств технологических операций, значения свойств среды операции или свойств предметов последней.
Координатами элементов отношений (r1,r2,...,rm), входящих в M(TO), могут быть как элементы базовых множеств, так и элементы независимо определяемых, вложенных отношений.
Для описания схем связей координат в отношениях в M(TO), могут быть использованы передаточные функции, дифференциальные, разностные, регрессионные уравнения, табличные или словесные описания.
На рис.1. показан упрощенный образ реальных технологических операций.
В среде технологических операций, характеризуемой вектором Z, учитывать окрестностные условия Z0 и внешние усло-вия Zy. Тогда справедливо выражение вида Z = Z0 ? Zy.
В окрестностных условиях среды технологических операций выделим:
- предметы (материалы, полуфабрикаты, заготовки), состояние которых характеризуется составом и значениями ряда свойств (в общем случае как внешних, так и внутренних) т.е. вектором Z'0;
результаты технологических операций, состояние которых характеризуется вектором Z''0.
трудоемкости, материалоемкости, энергоемкости, фондоемкости операции); Y''у - показатели степени экологической безопасности.
В качестве внутренних свойств технологической операции X будем рассматривать:
Рис.1.1. Наглядная модель технологической операции и ее среды.
Внешние условия среды, описываемые вектором Zy, отображают условия функционирования средств технологиче-ского оснащения (оборудования, оснастки), реализующего данную технологическую операцию, условия, в которых пре-бывают предметы и результаты технологических операций (температура, влажность, запыленность окружающей среды, квалификация рабочих), а также тип производства, в котором используется данная технологическая операция (массовое, серийное, единичное, опытное).
В качестве внешних свойств технологических операций, характеризуемых вектором Y, выступают:
а) свойства назначения или функциональные Yн, в числе которых Y'н - главное свойство - способность преобразовы-вать предметы технологической операции в ее результат, т.е. Y'н : Z'0 -> Z''0 ; Y''0 - параметры производительности техноло-гической операции (оценивается показателями среднего значения и дисперсии процента выхода, цикла операции, ритма выпуска, такта выпуска, числа одновременно изготавливаемых единиц и др.).
2.б) утилитарные свойства Yу, в числе которых Y'у параметры ресурсоемкости технологической операции синтезиро-ван.
Известно, что Str-FnM(O) отображает внутренние свойства Х объекта на внешние Y (состав элементов объекта, со-став и схему его внутренних связей, а также свойства этих элементов и связей на внешние свойства объекта.
Модель Str-FnMo(O) характеризует пространство возможных состояний объектов определенного класса в границах своей применимости для всех допускаемых данной моделью значений X и Y.
Решение задачи проектирования в данном случае заключается в формировании Str-FnMi(O) проектируемого объ-екта. Это сводится к выбору значений ряда параметров, которые являются наилучшими в смысле выполнения условий задача проектирования передвижения в пространстве допустимых значений параметров X и Y в
Str-FnMo(O).
Решение задачи проектирования при использовании представлений (оценивается показателями- параметры, ха-рактеризующие естественный процесс (физический, химический, физико-химический) Xп и техническую форму или способ осуществления этого процесса Хф, выступающие в качестве принципа построения/действия данной технологиче-ской операции,
- режимы функционирования технологического оборудования X0, реализующие данную операцию.
При этом справедливо X = Xп ? Xф ? Xо.
В общем случае внутренние свойства технологических операций могут описываться в терминах, лишь косвенно ха-рактеризующих естественный процесс.
ФУНКЦИОНАЛЬНЫЕ модели ТO могут быть представлены описаниями базовых множеств, характеризующих важ-нейшие свойства предметов, результатов и самой технологической операции, а также описанием отношения отображе-ния предмета ТО на ее результат в форме передаточной функции:
FnM (ТО) ? Y ? Z , y ? Yп, z ? Zо.
СТРУКТУРНЫЕ модели ТО представляются описаниями базовых множеств, характеризующих только выделяемые внутренние свойства операции X = Xп ? Xф ? Xо.
Для отображения взаимосвязи внутренних свойств ТО обычно используются термины и условные обозначения той предметной области, к которой относится естественный процесс, выступающий в качестве принципа действия или по-строения технологической операции.
ФУНКЦИОНАЛЬНО-СТРУКТУРНЫЕ модели ТО представляются описаниями базовых множеств. Они характеризу-ют важнейшие свойства результата, предметов, свойства назначения и выделяемые внутренние свойства самой ТО. Так-же используются табличные или словесные описания отношения соответствия 'результат - предметы ТО' паре 'естестве-нный процесс - техническая форма реализации процесса ':
Fn - StrM (ТО) : Y х Z -> X, y ? Yн, z ? Zо, x ? Xп .
Cтруктурно-функциональные модели ТО представляются с помощью описаний базовых множеств, характеризую-щих все выделяемые внешние и внутренние свойства ТО, свойства ее результата, предметов, среды реализации, а также описаниями отображений внутренних свойств ТО, свойств предметов и внешних условий среды на внешние свойства ТО ее результата.
Обычно отношения, входящие в состав модели Str - FnM(ТО), представлены вектор - функциями, отображающими зависимость свойств:
- результата ТО Z"о от внутренних свойств ТО X, свойств предметов операций Z'о и внешних условий среды ТО Zу ;
- самой ТО Y = Yн ? Yу от внутренних свойств операции X = Xп U Xф U Xо и свойств среды Z = Zо ? Zу ;
тогда справедливо выражение:
Z"о = f(X, Z'о, Zу) ;
Str - FnM(ТО) = { Y = f(X, Z) ; z ? Z, y ? Y, x ? X.
Продуктивная модель ТО - операционная карта по ГОСТ ЕСТД.
3. Задача проектирования технологических операций в обобщенной постановке
Предварительно определим цель проектирования. Ее можно представить в следующем виде:
< Da, D*тр, Dусл > , где(1.1)
?Dа - предмет задачи проектирования,
?D*тр - желаемое состояние этого предмета,
?Dусл - условия, ограничения, которые должны быть выполнены в процессе перевода предмета задачи из его исходного состояния в требуемое.
По отношению к задаче проектирования компоненты интерпретируются следующим образом:
?Dа - заявка на объект проектирования. Эту заявку в задаче проектирования представляет целевая модель объекта про-ектирования - M(O)ц;
?D*тр - продукционная модель объекта проектирования;
?M(O)пр - комплект технической документации для изготовления или использования объекта в производственных усло-виях, которая отвечает требованиям определенных стандартов (ЕСКД, ЕСТД или др.);
?Dусл - условия реализации задачи или ограничения на временные, трудовые, материальные ресурсы Q, выделяемые для решения данной задачи проектирования.
Под ЗАДАЧЕЙ ПРОЕКТИРОВАНИЯ любых объектов, в том числе технологических операций, понимается задача построения модели объекта M(O)пр, для которого определена целевая модель M(О)ц и установлены условия или ресурсы решения задачи.
В обобщенной постановке задача проектирования может быть представлена в виде:
ЗП = < M(O)ц, M(O)пр, Q > = << Fn M'(O), Z', Y', X', G>, M(О)пр, Q > , (1.2)
где компоненты Z', Y', X', G являются в общем случае векторами.
Требования к функциональным свойствам объекта проектирования определены в форме модели Fn M (O) Yн ? Z.
Требования к условиям функционирования объекта проектирования Z' задаются допустимыми областями множе-ства возможных состояний среды (внешних Zy или окрестностных условий), а также продолжительностью функциониро-вания Yн".
Требования к свойствам объекта проектирования помимо Fn M (O) ограничивают:
a)допустимую область множества возможных значений внешних свойств объекта проектирования Y' для всех z ? Z;
b)допустимую область множества возможных значений внутренних свойств объекта Х' которые характеризуют прин-ципы его действия.
Границы допустимой области множества значений свойств объекта X' часто определяются ресурсами, необходи-мыми для изготовления или использования объекта проектирования.
Условия решения задачи проектирования задаются допустимой областью значений ресурсов Q, выделенных для использования в процессе проектирования объекта. В качестве таких ресурсов обычно рассматриваются продолжитель-ность решения, общая трудоемкость, полная стоимость решения задачи проектирования. При этом стоимость проекти-рования может выражаться не только в виде денежных расходов, но и в количестве дефицитных материалов, времени использования уникального оборудования и др.
Условия предпочтения в допустимой области множества возможных решений задачи проектирования определяют-ся:
1.Критерием эффективности, функцией ценности или качества объектов G, которые обобщенно характеризуют данный объект проектирования, а также параметров функционирования (Y", X", Z").
2.Оценочной функцией M, которая соотносит внешние и внутренние свойства объекта проектирования при z ? Z с затратами (ресурсами), необходимыми для реализации процесса проектирования. В общем случае
M : (Y?Х?Z) ? Q, и оценочная функция M характеризует затраты, определяемые в виде различных ресурсов (вре-менных, трудовых, материальных и т.п.), на создание объекта с данным набором свойств. Предпочтение может быть отдано проектному решению с таким набором внешних y ?Yи внутренних x ? X свойств, реализуемых при z ? Z, что M (?у,?х,?z ) ? M ( y, x, z ) для всех допустимых y ? Y, x ? X, z ? Z.
Таким образом, все многообразие задач проектирования любых объектов проектирования сводится к двум:
a)максимизировать эффективность G проектируемого объекта (допустимые затраты на процесс проектирования Q задаются в виде ограничений);
b)минимизировать затраты Q (временные, трудовые, материальные), необходимые для реализации процесса проекти-рования (требования к внешним Y, внутренним Х свойствам и условиям функционирования Z объекта проектирова-ния задаются в виде ограничений).
4. Модель процесса проектирования технологических операций
Обычно при решении человеком той или иной задачи обращают внимание на умение найти такую ясную точку зрения, при которой ее решение является достаточно простым.
Один из путей построения такой "ясной точки зрения" на рассматриваемую задачу основан на использовании ме-тода выбора представлений для решения задачи. Этот подход предполагает существование упорядоченного и относи-тельно устойчивого отношения предпочтения между тем, что понимается под типами представлений для решения задач, с одной стороны, и классами (наборами) методов решения задач, с другой.
Все множество представлений для решения задач инженерного проектирования может быть отнесено к трем основ-ным типам:
?выбору из перечислений,
?определению в пространстве состояний,
?сведению задачи к подзадачам.
Рассмотрим каждый из типов представлений.
1.Использование представлений на основе выбора из перечислений возможно при наличии множества готовых, ранее спроектированных объектов (систем, устройств, сборочных единиц, технологических операций), описания которых в форме SbMi(O) или FnMi(O) доступны проектировщикам.
Решение задачи проектирования при использовании представлений по типу выбора из перечислений реализуется по следующей схеме:
?поиск или построение перечислений в виде упорядоченных множеств {SbMi(O)}, {FnMi(O)} готовых проектных решений, соответствующих тем объектам, которые составляют предмет задачи проектирования;
?выделение на множествах потенциально возможных решений {SbMi(O)} или {FnMi(O)} подмножества допустимых и целесообразных решений;
?выбор одного из ранее существовавших, готовых объектов в качестве наиболее предпочтительного решения данной задачи проектирования.
Существующие объекты представляют собой решения других, ранее поставленных задач проектирования с иными условиями реализации, ограничениями и др. Это позволяет предположить, что использование представлений на основе выбора из перечислений имеет приоритет в тех случаях, когда требования к свойствам объекта проектирования задают-ся в виде ограничений. При этом целевая ориентация задачи проектирования направлена на минимизацию временных, трудовых, материальных ресурсов, реализуемых в процессе создания нового изделия и (или) освоения его в производст-ве.
Представление на основе выбора из перечислений широко используется при решении задач проектирования объ-ектов низких уровней : материал, деталь, простая сборочная единица, простая технологическая операция и цепочка тех-нологических операций.
Использование представлений на основе определения в пространстве состояний предполагает наличие или возмож-ность построения полной Str-FnMo(O) объектов того класса, к которому может быть отнесен конкретный объект данной задачи проектирования, а также существование готовых ранее спроектированных компонентов и (или) элементов, из ко-торых данный объект проектирования может быть по типу определения в пространстве состояний реализуется по сле-дующей схеме:
?заимствование или построение множества моделей {Str-FnMo(O)}, которые потенциально пригодны для формирова-ния частных Str-FnMi(O), отображающих отдельные структуры конкретного объекта;
?выбор или синтез полной, отображающей все выделяемые структуры, Str-FnMo(O), наилучшей в смысле конкретного объекта, условий реализации и ограничений данной задачи проектирования;
?построение модели Str-FnMi(O) проектируемого объекта.
3.Использование представлений на основе сведения задачи к подзадачам предполагает разбиение задачи на совокуп-ность подзадач. Их решение приводит к выполнению исходной задачи. Процесс этот применяют рекурсивно для порож-дения подзадач, до тех пор пока их решение не станет тривиальным.
Решение задачи проектирования в этом случае реализуется по следующей схеме:
?заимствование или построение множества моделей {Str-FnMo(O)}, потенциально пригодных для формирования Str-FnMi(O) конкретного объекта, составляющего предмет данной задачи проектирования (формирование множества возможных вариантов декомпозиции объекта проектирования на подобъекты);
?выбор модели Str-FnMo(O), наилучшей в смысле возможности построения соответствующей Str-FnMi(O) объекта данной задачи проектирования с учетом особенностей условий реализации задачи и ограничений;
?построение Str- FnMi(O) проектируемого объекта - параметризация, интерпретация Srt-FnMo(O), наилучшая в смыс-ле условий данной задачи проектирования.
Представления на основе сведения задачи к подзадачам используются тогда, когда из-за высоких уровней сложности проектируемых объектов или из-за отсутствия необходимых методов и средств задача проектирования не может быть решена на основе других типов представлений. Они используются и в тех случаях, когда целевая ориентация задачи про-ектирования предполагает максимизацию степени использования готовых проектных решений.
Следует отметить, что в общем случае на разных стадиях решения каждой конкретной задачи проектирования могут использоваться различные типы представлений:
?на высшем уровне решение по типу сведения задачи к подзадачам;
?на уровне составных единиц - по типу определения в пространстве состояний;
?на уровне элементов - по типу выбора из перечислений и т.п.
При вариантном проектировании возможен "конкурс" типов представлений, когда одна и та же задача проектиро-вания данного уровня решается параллельно, на основе различных типов представлений, а окончательный вывод вари-анта производится на уровне сопоставления результатов полученных решений.
Под ПРОЦЕССОМ РЕШЕНИЯ задачи проектирования будем понимать совокупность последовательно меняющихся состояний задачи, а значит, и моделей объекта проектирования.
Классификация моделей объекта проектирования позволяет отобразить предметную сторону структуры процесса проектирования (при реализации по одному варианту решения и рассмотрении в линейной проекции без учета возмож-ных итераций).
В этом случае процесс проектирования может быть представлен в следующем виде:
M(TO)ц ? {Fn - StrM(O)} ? {StrMok (O)} ? {Str Mik(O)} ?
? {Str - FnM (O)} ? Str - FnMi(O)G ? SbM'i(O) ? SbMi(O) ? M(O)пр.