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

ГОСКОШЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ Таганрогский радиотехнический' институт

Г. " ОД

'' На правах рукописи

ВИШНЯКОВ Юрий Муссович

УДК 681.3.069

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ ПРОЕКТИРОВАНИЯ ДИСКРЕТНЫХ УСТРОЙСТВ ДЛЯ ИНТЕГРИРОВАННЫХ ИНСТРУМЕНТАЛЬНЫХ СИСТЕМ СО СКВОВНЬЫ ЦИКЛОМ ПРОЕКТИРОВАНИЯ

Специальности: 05.13.12 - Системы автоматизации

проектирования; 05.13.14 - Системы обработки информации и управления

Автореферат диссертации на соискание ученой степени доктора технических наук

Таганрог - 1993

Работа выполнена на кафедре математического обеспечения и применения ЭВМ Таганрогского радиотехнического института

Научный консультант:

действительный член АЕН РФ,

доктор технических наук, профессор Мелихов А.Н.

Официальные оппоненты: доктор технических наук, доктор технических наук, доктор технических наук,

профессор Зайцева E.H. профессор Фалькович М.А. профессор Алипов Н.В.

Ведущее предприятие - НПО "Алмаз", г. Москва

Защита состоится 1993 г. в 14.00 часов на засе-

дании специализированного совета Д 063.13.02 по защите диссертаций на соискание ученой степени доктора технических наук при Таганрогском радиотехническом институте имени В.Д.Калмыкова по адресу:

347915, Таганрог, пер. Некрасовский, 44, ауд. Д-406 С диссертацией можно ознакомиться в библиотеке института Автореферат разослан 41" Ыо^рл, 1993 г.

Ученый секретарь специализированного совета к.т.н., доцент

А.Н.Целых

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

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

В практике САПР сложилось два способа представления схем.

Байцер Б. Архитектура вычислительных комплексов.- М: Мир, т.1, 1975. С.498.

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

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

Третью проблему определяют требования к ИИС как к сложному комплексу математического, лингвистического, информационного, программного и технического обеспечения, который должен характеризоваться целостностью, гибкостью (многофункциональностью в плане настройки на технологические особенности кристаллов для БИС различного типа), открытостью (в плане модификации и развития). В настоящее время даже мощные интегрированные САПР типа кремниевой компиляции не отвечают в полной мере этим требованиям и остаются "вещью в себе", поскольку принцип открытости реализуется только в рамках конкретной САПР и только для узкого круга лиц -разработчиков данной системы, что диктует "кгкж-1хж" фирмы-изготовителя. А перенос проекта из одной системы в другую связан с большими трудностями, по трудоемкости сравнимыми с разработкой нового проекта. Кроме того, любая САПР имеет ограниченную область эффективного применения и может быть рассмотрена только как один из элементов, хотя и крупный, ИИС.

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

- разработка и исследование в теоретико-множественном аспекте в каждой конкретной предметной области новых эффективных способов представления объекта проектирования и манипуляции км в рамках сквозного проектирования;

- разработка программных средств, которые представляют функциональные элементы ИИС и реализуют эти способы;

- разработка языковых интерфейсов для сопряжения элементов ИИС как между собой, так и с пользователем.

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

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

Для достижения поставленной цели в диссертации формулируются и решаются следующие ссиохвие задачи:

1. В рамках системного проектирования-.

- разработать, расширив основные концептуальные понятия из области конечных распознавателей (KP), теоретико-множественные основы представления и преобразования дискретных устройств (ДУ) на базе конечных автоматов (КА) общего вида, обеспечивающих единстг.о представления и проводки ДУ на системном уровне проектирования по линии регулярный язык, система регулярных выражений (f'МО, система переходов (CID, недетерминированный конечный авто-

• - 6 -

мат (НКА), детерминированный конечный автомат (ДКА), минимизация;

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

2. В рамках логического проектирования:

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

- разработать интерактивную подсистему ИИС для автоматизированного проектирования ДУ на логическом уровне, одной из функций которой является поддержка АМ.

3. В рамках межуровневого языкового интефейса системно-логического и схемотопологического уровней проектирования:

- разработать язык структурного описания цифровых схем (ЯОС), который должен иметь признаки процедурного языка высокого уровня, допускать описание общих структурных свойств проектов и поддерживать их иерархическое представление;

- разработать принципы компиляции описаний проектов с ЯОС в объекты типовой САПР для последующего схемотопологического проектирования и выполнить разработку компилятора для САПР Р-САР;

- разработать технологию описания больших проектов на ЯОС, включающую процедуры настройки ЯОС и его компилятора на конкретный технологический базис элементов СБИС.

4. В рамках создания ИИС:

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

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

Четда иссяелршаиия базируются на теоретическом аппарате бу-

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

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

В диссертации получены следующие вовне паучвжз результаты:

1. В рамках системного проектирования:

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

- на КА общего вида обобщены понятия СП, НКА и ДКА, установлена их взаимосвязь и эквивалентные преобразования по линии: язык, СРВ, СП, НКА, ДКА, минимизация;

- разработан подход к построении приведенной СП РВ больших размерностей через обратную польскую запись (ОПЗ), отличительными чертами которого являются линейность и однозначность преобразования. Эти свойства обуславливают простую формализацию подхода и его ориентацию на машинную реализацию.

- предложено описание ДКА в виде Р-таблицы переходов/выходов, которое, обладая такой же выразительной мощностью, что и стандартный язык таблиц переходов/выходов, является более удобным при переходе к аналитическому представлению КА в виде системы булевых функций и последующим структурным моделям;

- разработана интерактивная подсистема для автоматизированного проектирования КА по линии "входной язык - СРВ - СП - НКА -ДКА - минимизация".

2. В рамках логического проектирования:

- разработана АМ ОБФ и ЧБФ, ориентированная на реализацию в ассоциативных аппаратных структурах;

- построена программная поддержка АМ;

- разработана аппаратная поддержка системы команд ассоциативной машины минимизации, которая может быть положена в основу соз-

дания ассоциативного сопроцессора-акселератора к ЭВМ для ускоренной обработки;

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

3. В рачках структурно-языкового интерфейса:

- разработан ЯОС, который имеет признаки процедурного языка высокого уровня и поддерживает иерархическое описание проектов;

- разработаны принципы компиляции программ с ЯОС в объекты типовой САПР для последующего схемотопологического сопровождения и построен компилятор для САПР P-CAD;

- разработаны технологии описания больших проектов на ЯОС, настройки компилятора на технологический базис элементов СБИС, создания библиотек элементов методом раскрутки, свертки проектов для осуществления функционально-логического моделирования.

Врокягческая ценность диссертационного исследования определяется тем, что:

1. Создана ИИС со сквозным циклом автоматизированного проектирования, получившая название PROJECT-CAD. Она охватывает системный, логический и схемотопологический уровни проектирования, позволяет на любом ив них провести интерактивную разработку проекта или его частей с последующей передачей на более низкий уровень. ИИС через ЯОС и его компилятор может замыкаться на типовые САПР. В данной версии ИИС в качестве типовой САПР выбрана мощная система автоматизированного проектирования P-CAD, являющаяся одной из распространенных в практической области САПР.

2. На базе ИИС PROJECT-CAD:

- разработан сопроцессор "FUZC0P-2.0" обработки нечеткой информации и нечетких знаний для IBM PC совместимых компьютеров на базовом матричном кристалле "Домбай ПВМ-4м";

- разработан микропроцессор обработки нечеткой информации на базовом матричном кристалле "Домбай ПВМ-4м";

- проведены исследования логических структур систем самоконтроля матричных коммутаторов на СБИС.

Результаты диссертационного исследования внедрены в организациях: НИИ многопроцессорных вычислительных систем г.Таганрога, п/о "Виброприбор" г.Таганрога, п/о "Измерительная техника" г.Калининграда, научно-исследовательской части Таганрогского радиотехнического института (ТРТИ) г.Таганрога, кафедре математическо-

го обеспечения и применении ЭВМ ТРТИ (учебный процесс).

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

Апробация работ. Основные положения, составляющие предмет диссертационного исследования, докладывались и обсуждались на II и III Всесоюзных симпозиумах "Проблемы создания преобразователей форм информации" в 1974 и 1976 гг. в Киеве; Всесоюзной конференции "Применение интегральных микросхем, микропроцессоров, микро- ЭВМ, микроэлектронной технологии в приборостроении 1979 г. в Орле; на VI Всесоюзной конференции "Развитие и использование аналого-цифровой вычислительной техники" в 1981 г. в Москве; IX Всесоюзном симпозиуме по проблеме избыточности в информационных системах в 1986 г. в Ленинграде; Межреспубликанском семинаре "Интеллектуальные САПР СБИС" в 1988 г. в Ереване; 34 Международном научном коллоквиуме в 1989 г. в г. Ильменау ГДР; Республиканской конференции "Применение кодов Фибоначчи в системах обработки и отображения информации" в 1990 г. в Виннице; Международной научно-технической конференции "Актуальные проблемы фундаментальных наук" в 1991 г. в Москве; Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР" в 1992 и 1993 г. в Геленджике; Региональных научно-технических конференциях, посвященных Дню радио, ежегодно с 1977 по 1892 г. в Ростове на Дону; Региональной научно-технической конференции молодых ученых "Разработка и применение средств вычислительной техники" в 1986 г. в Ростове на Дону; научно-технической и научно-методической конференции профессорско-преподавательского состава и сотрудников Таганрогского радиотехнического института ежегодно с 1973 по 1992 г. в Таганроге.

Публхгзщы. Результаты, полученные в диссертации, наши отражение в 69 печатных работах, среди которых одна монография, 19 авторских свидетельств, патентов и свидетельств Госфонда алгоритмов и программ, 35 статей и тезисов докладов в центральной печати, сборниках научных трудов и трудах Международных, Всесоюзных, Республиканских и Региональных симпозиумов, семинаров и конференций. Отдельные положения диссертации нашли отражение в 12 зарегистрированных во ВНИТЦ отчетах по НИР и двух учебных пособиях, изданных по плану Минвуза РСЯСР.

Структура и объем мюсеряаироввой рабом. Диссертация состоит из введения, шести разделов и заключения; изложена на 327 страницах машинописного текста и иллюстрируется рисунками и таблицами

на 33 страницах. Имеется список литературы (247 наименований) на 25 страницах. Общий объем диссертации 335 страниц.

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

В первом разделе проводится анализ проблемы системного проектирования, который проводится в рамках сквозного проектирования и охватывает проблему от регулярных языков н грамматик до представления проекта на языке минимизированных таблиц переходов/выходов. Отмечается, что сквозное проектирование законченное оформление получило в системном программировании при разработке компиляторов. Однако в этих рамках рассматривается только узкий класс КА -КР. При проектирован™ ДУ эти понятия получают новую теоретико-множественную интерперетацкю и содердак;;о. Крс:-.;э того здесь рассматривается Р-представление КА, которое обладает такой же выразительной мощность», как и язык таблиц выходов/переходов, и позволяет достаточно просто перейти к булевом1/ описании ДУ.

Зо втором и третьем разделах развивается АМ ЕФ, представляющая один из основных этапов структурного синтеза. Отличительная особенность АМ состоит в универсальной применимости к ОБФ и ЧБФ. При этом в отличии от традиционного подхода трудоемкость минимизации уменьшается с ростом степени неопределенности ЧБФ. Это свойство практически ориентирует АМ, поскольку шнкмизация сильно неопределенных ЧБФ очень вагна при введении в проектируемые устройства информационной избыточности, основанной на помехоустойчиво;.! кодировании. АМ в отличии от традиционного подхода позволяет одновременно строить сокращенную и все тупиковые ДНФ.

В четвертом разделе рассматривается аппаратная поддернка АМ в виде команд ассоциативной машины минимизации (АШ), которая может быть положена в основу построения сопроцессора к Ж!. Здесь показано, что все аппаратные решения являются регулярными структуры, что позволяет достаточно просто наращивать разрядность АлСЛ.

Пятый раздел посзящен языковому интерфейсу системно-логического и схемотоподогического уровней проектирования. Его представляют ЯОС и компилятор для ввода описаний в программную среду типовой САПР. Здесь проводится анализ известных языковых подходов и показывается, что современные промышленные САПР должны быть включены в КИС в качестве составных элементов. В разделе разрабатыва-

ются основные языковые конструкции и способ их трансляции в объекты типовой САПР. В качестве типовой САПР выбрана хоропо зарекомендовавшая себя в практическом отношении система Р-САР.

Шестой раздел представляет практическое приложение диссертационных исследований. Здесь разрабатывается и описывается пользовательский интерфейс ИИС, получившей название PROJECT-CAD, и на примерах иллюстрируется проводка проектов нэ всех этапах проектировали. Для ИКС разрабатываются ряд технологических приемов по быстрому созданию библиотек элементов и свертке проекта для обеспечения функционально-логического моделирования.

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

На защиту выносятся следующие основные научные положения:

1) теоретико-множественные оснозы сквозного автоматизированного проектирования ДУ на системном уровне;

2) теоретико-ьягаяественные основы ассоциативной минимизации булевых функций;

3) аппаратная поддержка ассоциативной ьетнимизации;

4) язык описания цифровых схем и способ компиляции описаний пробегов в объекты типовой САПР;

5) организация пользовательского интерфейса и технология разработки проектов в КИС со сквозным циклом автоматизированного проектирования.

СОДЕРЖАНИЕ РАБОТЫ

СгаЕвняэ. Обосновывается актуальность проблемы исследования.

Ргздая 1. Системный уровень проектирования. Автоматные модели

Системный уровень имеет четкие рамки и связан с представлением ДУ в виде модели КА. КА преобразует слова af Xм входного алфавита X-!Xi,X2,...,ХП> в слова выходного алфавита Y-<Yi,Ï2,...,Ym> 3f Y" и реализует автоматное отображение 0=-F(«) со свойствами: lal-IBl ; если tf-«iot2. F(oei«2)»DiB2 и Iofi I — 131 !, то F(«i)-Bi.

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

учетом этого СРВ КА общего вида выглядит следующие образом: ei; Y2- ег; ...; Ym- em;

Ym+i- X"\(lei l и le2l u. ..u le.nl); (1)

lei I n |ег1 п...n le^l = o. Поскольку иенду PB и поракдаемьш ш языком нет взаимно однозначного соответствия, то построение (1) всецело зависит от опыта и иятуищш разработчика и является далеко нетривиальной задачей.

Пусть задаю некоторое РВ е. Граф, кмевций начальную S и конечную Z вершины, связанные взвесенной дугой е, называется СП КР. При переходе из S в Z КР распознает цепочку at L.

Перенумеруем в СП катдого РВ (1) заключительные состояния и пометим их буквами выходного алфавита Y, а начальные - объединим в одно. Полученный граф представляет CII КА общего вида.

1.1. СП, дуги которой взвегекы элементарными РВ, назовем приведенной и будем обозначать через СЯя.

Пусть задана СПП некоторого РВ е. Введен на ней ряд понятий.

1.2. Беги из некоторого состояшш Q исходит Х-дуга в состояние Аь а из состояния Ai е состояние Аг и т.д. до ссстолпял Т, а из состояния Т нет исходящих ?.-дуг, то будем говорить, что состояние Q связано с состоянием Т линейным Х-путем.

1.3. Если из некоторого состояния Q исходит Х-дуга в состояние Ai, а из состояния Ai в состояние Аг и т.д. до состояния Ак, а из состояния Aj<. в состояние Q, то будем говорить, чго СОСТОЯШШ Q,Al,A2, . . . ,Ak входят в один кольцевой Х-путь.

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

1.4: Блоком состоянии (БС) для некоторого состоя-i::m Q назовем миссхество состояний, вкаочггочео само состояние Q н Есе состояния, входящие в Х-пути, исходящие из состояния Q. Если из состояния Q не исходит Х-путей, то EC(Q) предстазлен эиш состоянием Q. БС состояния Q будем обозначать через EC(Q).

tepc^assxa 1.0. Если из состояния Q исходят один или несколько линейных Х-путей единичной длины, то EC(Q) назовем проста Х-БС, в противном случае составным.

Введем на СПП функция разбора (ФР) ji, представляющую отобра-хекие {БС>хХ->БС. Затопаем ее в вцде EC«ji(EC(Q),Xi). Цепочка а допускается КА, если существует CP EC(Zi)=p.(BC(S),a), где S начальное состояние, a Zi заключительное состояние.

Тссреаа 1.1. Если описание КА в виде СРВ непротиворечиво, то и эквивалентная СП такке является непротиворечивой.

Пусть для каждого РВ (1) построены СПп. Введен проверочную-таблицу (ПТ), по которой одновременно будем строить ФР всех РВ. ПТ содержит т+1 столбец, где 1,2,...,т столбцы соответствуют буквам входного алфавита, а »столбец представляет БС, именующие строки. Множество строк ПТ разбито на группы, каждая из которых может содержать до .и строк по числу РВ. Группа строк представляет БС для всех РВ, полученных на некотором шаге построения ФР. В клетку пересечения строки и столбца будем записывать вычисленное значение ФР для данного БС и входной буквы.

Проверка непротиворечивости СРВ. Алгоритм:

1. Построить пустую ПТ, сформировать БС(31), БС(2г), .... ЕС(Зт) и поименовать ими первую группу строк;

2. Для всех букв XI( X вычислить ФР;

3. Образовать новую группу строк путем их поижнования новыми БС, полученными в п. 2 и не содержащими конечных состояний Z^■,

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

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

Рассмотрим модель КА в виде семерки (Х.Э.Р,г,У,р.,а), где алфавиты: X - входной, У - выходной, Б - состояний; множества: Р -начальных состоянии (Р сг Б), Ъ - заключительных состояний (г с Б); функции ц - переходов, а - выходов.

Функция а задает отображение г->У. Здесь букве У1 У соответствует подмножество состояний гСУ^с^, помеченных ею. Определим автоматное отображение: цепочка а допускается КА, если в диаграмме состояний найдется хотя бы один путь хотя бы из одного состояния Р1(- Р в одно из конечных состояний С!^ -(Ух), причем

¿04), где <1,2,.. ,п} и М. т.е. г(У1)-11(У,с(). Для недопустим! цепочки 8 имеет место 2(Упи-1)-д(У,в). Такую модель КА назовем НКА общего вида.

Рассмотрим эквивалентные преобразования на СПП, связанные с удалением Х-дуг. Пусть имеются состояние 0 и простой Х-БС(Ц)»{Ц,А1,А2,...,Ак>, который участвует в разборе цепочки ы. Цепочка и допустимая и для нее существует ФР ЕС(г1 )»ц.(БСС5) л1) • Представ™ о в виде катенации двух подцепочек с( и 3 «=аЗ, для каждой из, которых ФР имеют вид ЕС(<3)=»|х(БС(3),а); БС(г1)=д(БС(р),3). Пусть простой Х-БС(<3) содержит всего одно сос-

тояние Аь с состояние С связано исходящей Х-дугой. Из определения простого Х-БС следует, что ц(БС«3) ,В)=ц(БС(А1) ,В)-=БС(г1). Выполним следующие построения: разорвем дугу 1 и навесим на состояние о дуги, исходящие из состояния А^. Теперь БС(С})=С} и БС(А1)-А1. В результате замены разбор цепочки сохранился. По транзитивности рассуждения распространяются на простой Х-ЕС(Ц), содержащий более чем одно состояние Аь ' При удалении х-дуг исходящие из состояний А1,А2,...,Ак дуги навейивзются на состояние <Ц. Процедуру удаления Х-дуг в простом Х-ЕС назовем развязкой.

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

Случай 1. Пусть задан простой Х-БС(Ц)-<С},А1,А2,... ,Ак>, в котором одно или несколько состояний являются конечными и представляют выходную букву Уь т.е. {АР1,АР2,. ■. ,АРк> с Пусть существует цепочка ы, для которой имеет место функцзгя разбора вида БС(А1)=д(БС(Н), где А^ является конечным состоянием. Представим цепочку о в виде катенации ы=«Х. Тогда для функции разбора справедливо следующее БС(А1)=^(БС(5) ,и)=р.(ц(БС(3) ,<*) ,Х). Но поскольку (!>=с«Х=с(, то и д(ВС(Б) ,о)=(1(БС(3) ,с<). Итак, при развязке Х-ЕС(Ц) состояние 0 надо сделать конечным по букве У1.

Случай 2. Пусть задан составной Х-БС(Б) и Э является начальны;.! состоянием СПп. Выделим простой Х-БС(Ц)={0,А1,А2,•••,Ак} в Х-ЕС(З). По определен»® Х-БС Х-пути ведут из состояния 5 в состояния Аь Аг,... ,Ак. Пусть имеется неюэторая цепочка ш, разбираемая данным КА и существует функция разбора вида ЕС^ )-|1(БС(3) , где 6 а путь разбора проходит через одно из А4. Тогда

справедливо соотношение р.(БС(3) ,и)=ц(БС(А,) ,ы) и при развязке простого Х-ЕС(О) состояния А1,А2,...,Ак сделать начальными.

Пусть в кольцевой Х-путь включены состояния АьАг.....Ак и

существует цепочка и, для которой БС(г1)=у.(БС.(3),и) и 2(У,). Пусть разбор проходит через одно из состояний Аь Тогда цепочку можно представить в виде катенации ш=и8, для которой существует 5Р БС(А1)-д(БС(3),с() и г(У^=ц(БС(А,),е). В силу определения БС Есе БС(АI) одинаковы. Отсюда состояния (ч в смысле разбора являются эквивалентными и их можно стянуть в эквивалентное состояние А с сохранением всех исходящих и входящих дуг состояний. Если в кольцевом Х-пути имеется хотя бы одно состояние, являющееся начал!, ным (конечным), то и эквивалентное состояние необходимо еде-

лать начальным (конечным). В дальнейшем процедуру замены кольцевого Х-пути одним состоянием назовем сжатием.

- Алгоритм удаления Х-дуг в СПп:

1. Сжать все кольцевые Х-пути;

2. Выполнить развязку всех составных. Х-БС.

Выход: диаграмма состояний эквивалентного НКА.

Традиционную в структурном синтезе автоматную модель назовем

ДКА. ДНА задается в виде семерки (X',S',P',Z',Y',|i',;0, где алфавиты: Х*-входной, Y'-выходной, S'-состояний; Р'-начальное состояние Р* S; Z-множество заключительных состояний (Z'cz 5'); функции ji-переходов и а-выходов, реализующие отображения S'*X'->3 и Z*->Y' соответственно.

Построим ДКА, эквивалентный НКА по разбору входного языка. По определению Х'=Х и Y'=Y. Определим S' через подмножества алфавита S: если в НКА <Si,S2,.. .Si>- cZ. S, то эквивалентное подмножеству состояние ДКА обозначим через [S1S2...S1). Если в НКА P={Si,S2,...Si> , то в ДКА Р'= [S1S2...S1]. Множестви Z' составляют состояния, в имена которых включено Zjf Z. Если в НКА M(<Si,S2,...Sb>,T)-{Ri,R2»...Ri>, то для ДКА M'(iSiS2...Si],T) = [R1R2...Ri). 'Построенный ДКА допускает тот же язык, что и НКА.

Пусть задан некоторый ДКА. Свяжем событие Xi с присутствием на входе буквы Xj, а событие Sj - с пребыванием КА в состоянии Sj. Составное событие AiP , связанное с пребыванием КА хотя бы в одном из состояний Ske, из которого возможен переход в состояние Sp по входной букве Xi, имеет вид A;P-(Ski+ Sk2+ ...+ Skn), а составное событие, состоящее в переходе КА из состояния события AiP в состояние Sp по входной букве Xj, имеет вид Xi & AiP. Тогда система событий So,Si,..,Sn-i -задает функционирование КА в целом и представляет аналитическое описание КА.

Построим таблицу переходов/выходов ДКА, в которой элемент (i,j) представляет состояния, задающие переход по букве Xj в состояние-Si. Эту таблицу назовем Р-представлением. Р-представление и стандартная таблица переходов/выходов взаимно однозначны. Однако Р-представление представляет компактную запись системы событий, где каждое - соответствует одной строке р-представления. Переход от Р-представления к структурному описанию включает кодирование алфавитов, построение системы сечений, системы булевых функций и оптимизацию структуры.

Построение СПп по РВ связано с раскрытием скобок и учетом

приоритетов операций. • Поэтому обработка достаточно сложных РВ не однозначна и затруднительна в машинной реализации. Ее решение возможно на пути введения ОГО РВ. Для этого определим операции: * - сцепления (катенации); I - или; > - итерации (одноместная), соответствующая итерация Клини; приоритеты символов: (,< - приоритет. О ; ),> - 1; I - 2; * -.3. Соотношение приоритетов * и I оче-. видно. В то же время приоритеты итерационных скобок нуждается в обосновании. Для этого введем мегаграшатику вС<РВ>], языком которой являются цепочки, представляющие РВ. Она имеет вид: <РВ>:: =Ч<РВ--)-1 (<РВ>) <РВ> ::= <РВ>*<РВ> I <РВ>КРВ> <РВ>' ::- 0 I \ | XI _ Здесь <РВ> - нетерминал, соответствующий определению РВ, является начальным символом грамматики, 0,\,Хх,(,),{,>,* - терминальные символы ( XI (■ X). Первое правило устанавливает парность итерационных и круглых скобок, а рекурсия определяет их "парную вложенность. Таким образом цепочки, не отвечающие порождающим правилам, не принадлежат языку грамматики й[<РВ>). Отсюда счет парности скобок по алгоритму Дёйкстры для итерационных и круглых скобок независим и скобкам нужно назначить одинаковые приоритеты. Теперь на ОПЗ РВ алгоритм Дейкстры переносится без изменений.

Под "вычислением" ОПЗ РВ будем понимать построение СПп- Для этого введём вспомогательные • объекты типа имен состояний СИЧьОг,...> и переменных [МИ!,Иг,...}. Интерпретация,^ зависит от формы представления СП (графовая или в- матричная). Для • больших размерностей графовое представление не наглядно, поэтому • •.определяются матричное представление и операции над ним.

- Ргад-ая 2. Ассоциативная минимизация. Сокращенная ДНФ * Пусть (а,-,-!.. .а1ао)> множество п-разрядных двоичных наборов, Х-<Хп-1,...,Х1,Хо> алфавит булевых переменных и на г задана БФ Г(Хп-1..г..Х1,^о). Здесь аьXI ( Е; Е-{0,1>. БФ соответствует-" множество ДНФ, 'а поиск простейших' из них представляет основную задачу структурного синтеза-и называется минимизацией.

Разобьем Т на непересекающиеся подмножества , !?о и Б. На г задана ЧБФ, если: Ип)-1 при г^ 1?1; ИпУ-О при г.х( Ро; неопре-делена при г^Б. К1Ш?о называют•множеством разрешенных наборов, 5 - запрещенных. ЧБФ связана с табличным заданием БФ и Играет '.важную роль в структурном синтезе.

Свродалеикв 2.3. Разметочным- множеством М назовем совокуп-

ность всех способов разметки разрядов n-разрядного набора из Z.

Определение 2.4. Разметка m(r) размечает г разрядов набора, то она имеет ранг г.

Если гл(г) размечает разряды li,l2,-.-.ir » то это запишем как m(r) = (li, 1г.. - -, ir)- Здесь ijf <0,1,2,... ,п-1>. Выделим вМ подмножества Mö.Mi,... ,МГ,...,МП так, чтобы в Мг входили только разметки ранга г. В дальнейшем Мг назовем г-ранговым разметочным множеством. Мо представлено пустой разметкой е.

Определенно 2.5.' Ядром Я(т(г)) разметки m(r)-(ii,l2 ...ir) назовем совокупность интервалов П(ал,aiг,•••» ац-) с. Z, номера координат которых представляют разметку т(г).

Свойство 2.2. Все попарно склеивающиеся конионкции локализованы в пределах одного и того же ядра.

Теорема 2.1. Если заданы разметки inj (r)-(Ji,З2. ■ ■ ■ »J'r) и nu(p)-(ii,i2,■ • • Лр) таким образом, что г<р и di-ii; 32-ii; •••;

jr=ii , Ui.i2.....ip). то конъюнкции ядра (г)) совместно

поглощают все конионкции ядра Я(пц(р)), или, что одинаково, разметка mj (г) поглощает разметку thj (р).

Теорема 2.2. Если задано г-ранговое разметочное множество, то ядро Я(ш(г)) разметки m(r)»(ii,i2»•••.ir) представляет минимальное и единственное покрытие куба Z интервалами üfii-,I2,...,ir)-Определение 2.6. Ортогональным дополнением конъюнкции К назовем лобую склеивающуюся с ней конъюнкцию К*.

Определение 2.7. S-окрестностью конъюнкции К (S(k)), назовем все ортогональные дополнения конъюнкции К.

Введем на М отношение простого поглощения (->). Размет!» mi(r) -> nij(p), если р-г+1 и H(mi(r)) поглощает ядро fl(ntj(p)). Сопоставим ■> ориентированный граф, узлы которого соответствуют разметкам. Разметка mi(г) располагается выше разметки mj(р), если г<р. Если mi(r)->mj(p), то из.узла mi(r) ведет дуга в узел mj(p). Начальный узел (корень) соответствует разметке е; г-ярус •-. г-ранговому разметочному множеству Мг. Граф не имеет циклов.

Введем множество. П0ГЛ0ЩАаИЕ(ш^ (г))-{mi (р) I mj (r)->«nj (p) и г<р>, где mt(p) это разметка, поглощаемая разметкой mj(г).

Алгоритм: построить отношение простого поглощения ->; построить транзитивное замыкание ->*■; из «>•»■ для разметки rnj (г) выбрать пары, в которых mj(r) является левой компонентой. Правые компоненты образуют множество ПОГЛОЩАЕМЫЕ(mj(г)).

На Z определим БФ f подмножествами Ri, Ro и S. БФ имеет сок-

ращенную ДНФ Dc-Ii+l2+.•.+1Р, где Ij - простая импликанта.

Теорема 2.3. Если h - простая импликанта принадлежит ядру Я(ш(г)) разметки ш(г) - Cii.i2.---.ir). тс S-окрестность этой импликанты не содержит других простых импликант БФ f.

Следствие 2.1. Если [-простая импликанта, то S-окрестность S(I) этой импликанты состоит только из недопустимых конъюнкций.

Теорема 2.4. Если ядро Я(т(г)) состоит только из конъюнкций, поглощаемых импликантами ранга р (р<г), простых импликант ранга г и S-окрестностей этих конъюнкций и импликант, то ядро любой разметки m(q)f ПОГЛСЦАЕШЕ(т(г)) не содержит простых импликант.

Разметку т(г) назозем концевой.

Следствие 2.2. - Если в ядре Я(т(г)) имеется импликанта I с S-окрестностью S(I), то.для любого Я(ш(р)), где т(р)£ ПОГЛОЩАЕМЫЕ (т (г) ), порождения S(I) не являются импликаитами.

Определен!® 2.9. Концевым разметочным множеством БФ f (M(f)) назовем множество всех ее концевых разметок.

Слсадствяа 2.3. Если M(f) - концевое .разметочное множество БФ f, то для всех mi(r)£ M(f) множество ГОГЛСИДЕШЕ(mi(г)) простых импликант не содержат.

Определение 2.10. В графе простого поглощения путь от корня до концевой вершины назовем импликантным, а подграф, представляющий только импликантные пути - импликантным графом.

Все простые импликанты БФ f могут располагаться только в ядрах разметок импликантного графа.

Общий подход к построению сокращенной ДНФ Dc БО заключается, в построении импликантного графа, начиная от корня. Вначале заводятся два пустых списка Q и. М. Алгоритм:

Для каждой разметки mt из.импликантного графа (t-0,1,...):

1. Все простые импликанты ядра Я (rot)' разместить в список-Q;

~2. Если m(t) концевая разметка, то.внести ее в список М.

Выход: Д содержит простые импликанты, М - концевые разметки.

Поиск тем быстрее заканчивается,' чем больше доля RiUS в кубе Z. Тогда простая -импликанта располагается ближе * корню графа.

Сконструируем общий алгоритм поиска со1фащенной ДНФ БФ f. Для этого свяжем с каждым набором из Ri два признака. Первый из них назовем меткой'А, а второй - меткой В. Метку А будем использовать для выбора очередного набора из Ri для анализа,. а метку В - для определения концевых признаков разметки. Алгоритм:

1. Положить м>0 и Q-0;

2. Для каждой разметки п^ОИ ПОГЛОЩАЕМЫЕ(пц (р)), где

1=1,2.....п и 1=1,2.....С (1-старший индекс, I-младший индекс), пц(р)( М и р<1 выполнить:

2.1. Снять метки А и В в Д;

2.2. Каждый набор г 1?1, для которого г(П) л Я(пцЛ1))сГ П(, (где интервалу ГЦ соответствует конъюнкции ^С Ц), и его Б-окрестность отметить метками А и В;

2.З.. Шзюлнять пока не все наборы в !?1 отмечены метками А: а) выйашггь очередной непомеченный меткой А набор г£ На и сделать его компарандом. Отметить компаранд-г и Все ассоциативно равные ему по разметке пч С 1) наборы в )?1 метками А;, в) если в 1?о отсутствуют наборы, ассоциативно равные компаранду по разметке гтц:(1), то отметить метками В компаранд- и его 3-окрестность, а также все ассоциативно равные ему наборы в . Дополнительно отметить 3-окрестность компаранда меткой А.

2.4. Если в [?1 все наборы отмечены метками В-, то разместить разметку тсШ в список концевых разметок М.

Раздел 3. Ассоциативное построение тупиковых ДНФ

Существует два традиционных похода к поиску тупиковых ДНФ на ' множестве простых импликант БФ,- Первый основан на испытании членов и состоит из последовательности шагов, на каждом из которых из ДНФ предыдущего шага, удаляется одна конъюнкция. Второй -обобщает идею импликантных матриц и состоит в следующем, с пыбо-ром импликанты !<1 из множества импликант связывается.элементарное событие В^ Событие Aj-Bjl+Bj2+.. .Взг для. каждого набора г^^. представляет §го покрытие хотя бы одной импликйнтой, а составное событие А=А1Ао...Ач - покрытие всех наборов 1?1. Преобразуя Л. получим А=У(В]хВуг-..Взр), где каждой конъюнкции соответствует тупиковая ДНФ вида Кл+К]2+.- ■ • +КЗР,. а все они.представляют тупиковые ДНФ. При переходе от ОБФ к ЧБФ метод испытания членов резко усложняется, метод импликантных матриц изменений не претерпевает.

Модифицируем метод импликантных матриц применительно к ЛМ так. чтобы одновременно проводилось построение сокращенной и тупиковых ДНФ. Представим исходное событие А в виде скобочного выражения

11 1 2 2 2 т Ш/ . т

А-(В1+Вг+. . .+Ва1)(В1 +В2+.. .+Вч2). . .'(В1 +В2+...+ Бда) (2)

а. .-

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

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

Определение 3.2. Кортеж ранга п. являющийся элементом прямого произведении п-множеств, назовем частичным произведением (ЧП), а матричное представление прямого произведения, строками которого являются ЧП. назовем массивом частичных произведений (МЧП).

Пусть в моменты времени 1=<0,1,2.....Ьк) А модифицируется

пополнением первичных множеств. Каждому А(0 соответствует скобочное представление и МЧП. причем А(О)=0 и АС^) - конечное значение А, к вычислению МЧП которого мы стремимся. Цель - построить рекурсивную последовательность действий Г, ■ которая вычисляет МЧП в виде МЧПа+1)=г(МЧП(Ш.

Пусть на шаге Ь получено скобочное представление вида А(и = (А1) (Аг) ■.. (а1+аг+.. .+ад,)... (Ащ), где (А;) означает скобку, представляющую элементы из Аь МЧП имеет следующий вид

В а: С В а2 С

В

Здесь В а] С обозначает некоторое множество цепочек вида (р1а3р2I

B, рг(- С > и называется окружением элемента а^. Для всех элементов а0 £ А1 подцепочки Р1 и рг одинаковы. Пусть на шаге 1+1 ко множеству А^ добавляется элемент к. Скобочному выражению А(Ь+1 ) = (Ах) (Аг)... (а^аг-ь.. .+ас,,+к)... (Ар) соответствует новый МЧП, который получается дописыванием к МЧП(О цепочек вида ВкС.

Ассоциативное пополнение МЧП. В МЧП(и первое ЧП сделаем ком-парандом (им может быть и любое другое ЧП). первичное множество А1 пополняется элементом к. Алгоритм:

1. Выделить 1-й разряд в МЧП;

C. Выделить и отметить компаранд. Найти и отметить все ЧП, ассоциативно равные компаранду по Ьму разряду;

3. Заменить во всех отмеченных ЧП 1-й разряд на элемент к и вновь образованные ЧП приписать к МЧП(Ь);

4. Если к открывает первичное множество, то он дописывается в соответствующий разряд ко всем ЧП.

Выход: МЧПа+1).

Введем меру избыточности МЧП. Пусть скобочное выражение АС^)

включает т первичных множеств с мощностями Ь\Л2.....Мощность

МЧП равна ^Ьг-■■1т. Пусть после сжатия МЧП остается к ЧП, представляющих тупиковые ДНФ. Тогда - избыточностью назовем величину 1=(1-к)/1*100Х, которая может составлять существенную величину.

Исследуем возможность совмещения пополнения и сжатия ¡/(ЧП. В АМ при поиске сокращенной ДНФ переменная В] может выявиться только один раз, но-пополнить несколько скобок.

Пусть на шаге I сформирован МЧП, соответствующий скобочному выражению А(1)«(А1)...(А))(А1+1)...(А1+т+1)...(Ак), а на таге 1+1 элемент 1 пополняет множества с номерами 1,1+1,...,1+ш+1. Тогда в МЧП (Ь+1) все ЧП из группы А1...111...Ак поглотят совместно ЧП из вновь образованных групп, после чего он принимает вид />1 ... А( А1+1... А1+т+1... Ак А1 ... 1 1 ... 1 ... Ак

Полное окружение элемента а^1 (а^,1(- АО, могло представить в виде двух частей: А}.. .ajAi.fi..-А1+т+1.. .Ак и А1.. .а3р.. .Ак, где р представляет цепочки, содержащие хотя бы один элемент 1.

Ояродакзмгэ 3.4. Часть окружения элемента а^, ЧП которого содержат р-подцепочки, будем называть р-окружением.

Ерли аз=1,- то его р-окружение стягивается в группу ЧП вида А1...11...1...Ак.

Сградзгэггл 3.5. т-кратную переменную ч (ет=2,3,...) , выявляемую на некотором шаге АМ в первичных множествах Aii.A12.Ai3..., назовем переменной и обозначим в виде Ь(4111,12,13.••)■

Опрэдасипя 3.8. Группу ЧП, в которую стягивается р-окружение Ь-элемента , назовем точкой поглощения (Сточкой). .

Тег^еаа 3.5. Если множества А1,А1+1,...,А1+т-1 пополняются Ь-переменной, то все р-окружения любого элемента а(- А^, где . И,1+1;...,1+т-1>, поглощаются Ь-точкой (доказательство опущено).

Пусть на шаге Ь Ь-переменная 1 пополнила т множеств А¡,А1+1, ....Ацщ-! и выполнены ассоциативное пополнение и удаления р-ок-' ружений. На шаге t+l ^переменная ч пополняет п множеств.

Случай 1. Ь-переменная ч выявляется в тех же первичных множествах, что и ^переменная 1. МЧП пополнится группой ЧП, представляющих 1-точку и примет вид:

А1-. •А1А1+1А1+2.. .Ац.т+1.. .Ак А1-..1 1 1 ...А1+т+1...Ак А1-..ЧЧ «1 —Ац.т+1.. Ак

Случай 2. Ь-переменная д частично выявляется в тех же первичных множествах, что и Ь-переменная 1. МЧП принимает вид: А1... А1.. .А1+Щ-2 А14ц1-1А4+тА1+щ+1- •»Ак А1— 1 1 ... 1 А1+тА1+т+1...Ак • — А1-. .4 Ч Ч <1 ...Ак А1...1 1 ... 1 ч Ч ...Ак

Случай 3.- Ь-переменная ц выявляется во множествах, ' отличных от и-переменной 1. Выполняется простое ассоциативное пополнение.

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

Для ш-кратных ' -переменных построим правила ассоциативного пополнения, при выполнении которых МЧП не содержит избыточных ЧП.

Определение 3.9. Будем говорить, что" Ь(д11,1+1,...,1+т-1) покрывает Ь(£13,3+1,...,З+п-1), если {3,3+1.•••,3+п-1>£Г {1,1+1,...,1+т-1> или входит в Ц^13,3+1,... ,З+п-1), если {1,1+1,...,1+т-1>с <3.3+1.•••.3+п-1>. В противном случае частично покрывает, если {3,3+1,... ,3+п-1>пи,1+1,.... Д+т-1-}1<0.

Пусть на шаге I сформирован не содержащий р-окружений МЧП(и вида А1-. .А1А1+1.. .А1+Щ-1.. .Ак. а на шаге. 1+1 А1,Ац-1',... ,А,+т-1 пополнились Ь-переменной Ь(1I1,1+1,...,1+т-1). Алгоритм формирования МЧП(1+1):

1. Выделить первое ЧП в качестве компаранда и отметить его;

2. Отметить в МЧП все ЧП ассоциативно равные компаранду по разрядам 1,1+1.....1+гп-1;

3. Отметить в МЧП все ЧП, Ь-группы которых частично покрываются Ь-группой Ц1П, 1+1,...,1+111-1);'

4. Во отмеченных ЧП провести замену разрядов 1,1+1,...,1+т-1 на Ь-элементы 1 и новые ЧП дописать 'к МЧП(и.

Выход: МЧП(1+1).

Выполнение п.З представляет . нетривиальную задачу, поэтому включение ассоциативности в алгоритм требует доработок. Введем таблицу для накопления Ь-групп по типу стека (Ь-таблица). Массив, в котором будем формировать компаранды, назовем массивом компа-рандов (МК).-Он создается на данном шаге и строится по алгоритму:

1. Выделить первое '31 в МЧП, которое будем считать порождающим и разместить его схематично над Ь-таблицей;

2. Ь-переменную поместить в Ь-таблицу и сделать текущей;

3. Из порождающего ЧП выделить разряды, ' покрываемые текущей Ь(1I1,1+1,...,1+ш-1),• переписать их в МК-для формирования первого

компаранда;

4. В L-таблице отметить все L-переменные, частично поглощао-щиеся L(1Ii,i+1,...,i+m-1);

5. Для каждой отмеченной L-переменной L-таблицы образовать ноеый компаранд из первого в МК, для чего выделить общие разряды для- текущей L(1 li, i+1,..., i+m-1) и отмеченной; за\шшгть в выделенных разрядах в первом ко?шаранде значение разрядов па основание отмеченной L-группы.

Теперь ассоциативное пополнение выглядит следующим образом:

1. L-перемеину» поместить в L-таблицу и построить !Ж;

2. Отметить в МЧП ЧП, ассоциативно равные ксмпарачдам из (Ж;

3. Во Есех отмеченных ЧП произвести замену разрядов i.1+1.•■•,i+m-1 на 1-элемента и новые ЧП дописать к старому МЧП.

Пусть в ке:<юторый момент времени появляется L-переменная L(gli,i+1,... ,i+p-l,n,n+l,... ,n+t-l) и Ап-Ar+i-. .-=An+t-i-i3. Введем понятие пустого элемента (X), а мпсдество, содержащее только пустой элемент назовем А-множеством. Обозначим его через Д--Ш. А-множества будем различать . An-множество содержит элемент Хп; Лп+1-множество содержит элемент Ап+1; An+t-i-множество содержит элемент Xn+t-i; прячем Xn^Xn+i; Xn+i?<Xn+2; ...; Xn+t-2*Xn-tt-i. В дальнейшем будем считать, что Х-элемент в МЧП имеет индекс позиции, в которой он встречается. Если в А-множестве выявился элемент б, то оно превращается в одноэлементное множество. А в новом МЧП можно все л-элементы заменить на L-элемент g.

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

Рездзя 4. Аппаратная поддержка системы команд ассоциативной машины минимизации.

Разработка аппаратной поддержки системы команд AK7.I предполагает создание однородных регулярных структур, для которых наращивание разрядности проводится путем простого добавления.

Введем функцию Ti результата ассоциативной операции i-ro разряда ячейки памяти. Назовем ее разрядной функцией (РФ). Вектор РЗ можно представить з виде <Гп-1,••.,Г1,Го>=Г'(<компаранд>,<раз-метка>,<память>). Введем также функцию установа (ФУ) тегового

признака Ф-?и(Гп-1,...,Г1,Го), которую переопределим рекуррентно Ф1-Ф', если 1-0; Ф'-ГЧФц^.Г!), если 0<Кп; при 1=п соответствует начальному условию. Теперь. ФР соответствует каскадная схема 'мехразрядного переноса, в которой Ф^ выступает частной функцией установа для 1-го каскада.

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

В разделе для каждой ассоциативной команды АШ разметки, сравнения на равенство, разметочного поглощения, выделения З-ок-г рестностей, импликантного поглощения проводится синтез и анализ схемных решений РФ и ФУ с учетом треСонагл'.й ассоциативности, регулярности, преемственности и прозрачности, рассматривается их их совместная реализация в виде универсальных аппаратных структур. Структуры являются однородными в последовательности связей разрядов и просты в реализации. Стругаурные синтез и анализ построены на базе аппарата ассоциативной минимизации.

Рсзкка б. Языковые средства структурного описания проектов.

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

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

Переход к ИКС со сквозным проектированием, в которой типовые САПР явлшэтся составными элементы, распирдет взгляд на языковое описание и требует рассматривать его в кстлексто ¡'ог.туроЕневого ;штерфейса системно-лопмеского и схемотополсгкчэского уровней. Анализ структурного и функционального в проектировании показывает, что они соотносятся как синтаксическое и семантическое в прогрЕ'дпфоваяии. Отсюда естественное решение состоит в выделении структурных свойств проектов, построении языковых средств их описания и сохранении за типовой САПР функциональней и схемотополо-гической интерпретации. Такси подход предполагает трансляцию структурного списания в объекты типовой С/УТР, саслячая ее состяз-нкм элементом в среду JSC. Теперь структургга-яэиковое описа::;:э приобретает глобально-универсальный характер.

Структурно-языковые средства должны допускать иерархическое описание прсеетов, однозначное восстановление схемы по описания и прссту» приг,лз|су к объектам типовой САПР. Язык долден быть грамматически стропаш, допускать использование в качестве объектного пейса дли более высоких уровнен проектирования и выступать в роли средства сборки проектов из отдельных частей. Этим требованиям в удовлетворяет развивае-мй язык описания цифровых схем (ЯОС).

Ко:яюнент в ЯСС отождествляется со схемой по типу, черного ящика, ¡rue от входы X«<Xo,Xi,... ,Хл> н выходы Y=<Yo,Yi,...,Yn> и реализует соответствие Y=F(X). Он 1гзэет уникальное имя, как правило, связанное с реализуемым соответствием F. Интерпретация компонента - изнутри это схема, из вне - символ. Такой подход обеспечивает поддержу иерархического описания проектов.

Для списания компонентов служит следующая конструкция SYMBOL <имя ко!.ш.> С ,LIBRARY[»<k03$.npefln. >П,ВСКХ-'бул.форм.']); <описание узлов> BEGIN

<тело компояента> END;

Компонент может быть библиотечным или описанным в иерархии программы. В первом случае ему соответствует запись в библиотеке компилятора LIBRARY. Для размещения компонента в библиотеку заголов-

ке описания употребляется параметр LIBRARY. Во втором случае ключевой параметр LIBRARY опускается и компонент создается в пределах данного проекта. Исключения компонента из библиотеки проводится при значении параметра LIBRARY-DELETE. Непосредственно в файле конфигурации компилятора чаяно гадать замену библиотечного элемента новыи из программы или проигнорировать такое замещение. Коэффициент предпочтения и ключевой параметр BOOL требуются при работе процессора покрытий, использующего библиотеку компилятора.

Описания входных, выходных и локальных углов осуществляется декларативными предложения фориата <типхсписок узлов», где <тип> ::- INPUT I OUTPUT I LOCAL.

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

<имя1 узла> - <имя2 узла> - <имяЗ узла> - ... <m.«N узла> Все иуена являются равноправными синонимами эквивалентного узла. Функциональное присваивание включает в схему одновыходной компонент и гадает связанные с ним узлы других компонентов. В правой части инструкции задается список входных узлов, а в левой - выходной узел. Формат функционального присваивания имеет вид <имя узла> - <имя компонента» < список узлов-» Полное присваивание аналогично функциональному и применяется для ыноговыходных компонентов. Оно имеет следующий фориат <список узлов> - <имя компонента»«список узлов> Определения синонима эквивалентного узла, объединяющего несколько входов и выходов компонентов, осуществляется инструкцией

<групповое имя> » RENAME(<список имен узлов>) Пример 1 Пример 2 Пример 3

Y1 - К1( ); Y2 - К2( ); Y3 - К3( ); Z - K4(Y1,Y2,Y3);

Y1 - Y2 - Y3 - X; Y1 - К1( ); Y2 - К2С ); Y3 - К3( ); Z - К4 (X);

Y1 - Y2 - Y3 - X; Y - RENAME(Y1.Y2.Y3) Y1 - К1( ); Y2 - К2( ); Y3 - К3( ); Z - К4(Х);

В Р-САЛ элемент представляется в виде графического образа, (файл <имя компонента».БУМ) и поведенческой модели (файл <имя

компонента.FML). При моделировании компоненту назначаются задержи переднего и заднего фронтов и логическая сила. Для этого используется два предложения, первое из которых задает так называемые PCL-атрибуты и имеет вид

PCL_LIST = (delay l, delay 2, strange 1, strange 2) Здесь старые PCL-атрибуты компонента заменятся ка новые. Другое предложение переопределяет поведенческую модель

MDL_ID = «параметр моделирования> где параметр моделирования определяет конкретный тип модели.

Программа проекта состоит из описания иерархии и главного модуля и имеет следующий формат

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

Разработка принципов компиляции интерпретируется на примере разработга компилятора к САПР P-CAD, которат представляет характерные черты типовой САПР и широко используется в практике. Здесь проектирование проводится в интерактивном режиме с помощью специализированного графического редактора PCCAPS. PCCAPS работает с пользовательской и библиотечной базами данных и представлен символьным и схемном процессорами. Для компонентов пользователь вводит информацию о номерах контактов, задержках сигналов и привязывает графическое изображение к функциональной модели. К простым компонентам создается поведенческое описание на специальном языке Схема проекта строится из компонентов и запоминается в базе данных. Из нее извлекаются информация для работы других программ.

Алгоритм компиляции совмещен с лексическим и синтаксичэским анализами. Базами данных компилятора являются: <имя>.ОСЗ - входной файл исходной программ; LIBRARY • библиотека компонентов компилятора; T_C0MP0NENT - таблица компонентов; Т_INP1N - таблица входных узлов; T_OUTPIN - таблица выходных узлов; T_EQ - таблица эквивалентных узлов; T_VERT_GOR - таблица вертикалей и горизонталей; Т_(.'ЕТ - таблица цепей; T_WTHVER - таблица размеров сечений вертикальных каналов; T_WTHGOR - таблица размеров сечений горизонтальных каналов; Т_Х - таблица координат точек привязки ярусов компонентов; T_Y - таблица координат точек привязки горизонтачей компонентов; <имя>.СМО - выходной файл объектной программы.

Общий алгоритм компиляции: из исходной программы считывается последовательно предложения. Из описаний и инструкций присваивания создаются и пополняются базы данных LIBRARY, T_CCMPONENT, T_INPIN, TJDUTPIN, T_EQ. По прочтению предложения END происходит передача управления на создание таблицы цепей T_NET на основе ранее созданных баз данных. Таблица T_NET используется для создания цепей в P-CAD. После этого управление передается второму этапу компиляции, на котором создается графический образ компонента или проекта. Здесь вычисляются размеры сечений вертикальных и горизонтальных каналов для прокладки цепей, размеры компонентов и их компоновка в пространстве, после чего создаются графический образы компонентов и схемы проекта. Каждый компонент и весь проект в целом проходят последовательно все этапы компиляции. По прочтению символа конца исходной программы (точки) компилятор создает объектный код, который размещается в файл <имя проектам CMD, представляющий пакетное задание для PCCAPS.

Раздел в. Интегрированная инструментальная система со сквозным циклом автоматизированного проектирования PROJECT-CAD.

ИИС PROJECT-CAD представлена рядом специализированных процессоров, увязанных по информационным и управляющим связям, многоуровневой библиотечной базой данных для хранения и модификации отдельных решений и языковым интерфейсом, обеспечивающим включение типовой САПР в среду проектирования. Система открыта пользователю на любом уровне проектирования и в интерактивном режиме поддерживает разработку проекта или его частей. Пользовательский интерфейс ИИС ориентирован на предметную область каждого уровня И' снабжен подсистемой контекстной помощи с элементами обучения.

Системный уровень представляют"четыре специализированных процессора, обеспечивающие разработку проекта по линии "вхсдной язык -> СРВ -> СП -> НКА -> ДКА". Логический уровень представлен редактирующими процессорами, обеспечивающими интерактивный ввод и редактирование проектов на языке таблиц переходов/выходов и граф-схем алгоритмов, процессором минимизации, подсистемами кодирования и минимизации БФ, процессорами формульно-скобочных преобразований, покрытий и сборки проекта. Языковый интерфейс образуют ЯОС и компилятор, обеспечивающий трансляцию описаний проектов в объекты САПР P-CAD, которая поддерживает функциональную и схемо-топологическую интерпретацию проекта.

Быстрая и качественная разработка больших проектов требует

создания ряда технологических приемов. В ИИС к ним относятся "раскрутка" и "свертка". Под раскруткой понимается ряд действий по созданию библиотек элементов кристаллов с помощью ЯОС, а свертка проекта связана с переводом составных элементов в примитивы путем конвертации описания проекта на ЯОС в программу на ИЛ. и выполняется для моделирования проекта при превышении ограничений в САПР на количество элементов и связей между ними.

Занмченив. Настоящий этап характеризуется переходом от программных систем, автоматизирующих разработку проектов на отдельных этапах, к ИИС со сквозным циклом проектирования на системном, логическом и схемотопологическом уровнях, где принятие решений и определение линии проектирования лежит на разработчике, а выполнение рутинно-формальных преобразований и сопровождение объекта проектирования - на программных средствах. На пути создания ИИС должен быть решен ряд проблем. Первая состоит в реализации сквозного проектирования на системном уровне. Вторая - в обеспечении целостности, гибкости и открытости ИИС. Третья - в организации интерфейса системно-логического и схемотопологического уровней проектирования. Далее в заключении приводятся основные выводы и научные результаты диссертационного исследования, которое выполнено в рамках данной проблематики.

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

1. Построено описание КА общего вида в виде СРВ, в которую наряду с известным условием полноты введено условие непротиворечивости. Обобщено понятие СП на КА общего вида, введены понятия блока состояний и функции разбора, а также построены формальные процедуры проверки СРВ на непротиворечивость. Обобщено понятие НКА на КА общего вида и построены процедуры преобразования СП в эквивалентный НКА. Построены процедуры преобразования НКА в ДКА, представляющий исходное задание для структурного синтеза. Введенные понятия позволяют выполнить сквозное проектирование по линии "входной я зык-> СРВ-> СП-> НКА-> ДКА-> минимизация".

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

дов/выходов, однако более удобно при переходе к аналитическому представлению КА в виде системы БФ и структурным моделям.

3. Предложен подход к построению приведенной СП РВ черев ОПЗ, отличительными чертами которого являются линейность и однозначность преобразования, а также ориентация на машинную реализацию.

4. Показано, что традиционный подход в минимизации БФ хотя и позволяет обосновать ряд ключевых понятий, тем не. менее неудобен для практического использования. На структурированном по классам множестве Ъ введены понятия разметки, разметочной совокупности, ядра, 5-окрестность. Построено отношение простого поглощения и его транзитивное замыкание. Доказан ряд положений, позволяющих выяснить распределение простых импликант БФ на множестве ядер разметок. Определено понятие импликантного графа. Его уьлы представляют разметки, ядра которых содержат простые импликанты. На импликантном графе сформулирован метод поиска простых импликант, который тем быстрее заканчивается, чем больше степень неопределенности ЧБФ или чем больше единичных значении содержит ОБФ. В традиционном подходе эти зависимости являются обратными.

5. Исследован традиционный подход к построению тупиковых ДНФ, в рамках которого известные направления сводятся к обобщенному методу испытания членов и обобщенному методу импликантных матриц. Поставлена задача одновременного ассоциативного построения сокращенной и тупиковых ДНФ, для чего она сведена к модели прямого произведения множеств, в котором элементы представляют произведения булевых переменных без отрицаний. Для прямого произведения введены структура хранения в виде МЧП, ЧП, р-окружение, ассоциативное пополнение, на базе которых построены ассоциативные процедуры вычисления безизбыточного МЧП.

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

7. Сформулированы основные требования к межуровневому интерфейсу системно-логического и схемотопологического этапов проектирования, который представляет структурно-языковые средства описания и компиляторы описаний в объекты типовой САПР. В рамках подхода разработан ЯОС, включающий основные черты процедурных языков высокого уровня и допускающий иерархическое описание проектов. Программы ЯОС линейны, легко верифицируемы, а синтаксические конструкции близки понятийному уровню разработчика. Кроме того

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

Разработаны принципы компиляции описаний на ЯОС в объекты типовой САПР на примере компилятора для САПР P-CAD. Для этого проведен анализ состава и функций P-CAD; разработаны соглашения о графическом представлении компонентов, способах их компоновки в cxewy и прокладке цепей; базы данных и основной алгоритм компиляции, который включает три этапа: заполнение баз данных, определение цепей и построение графического образа проекта. Построенные P-CAD по структурному описанию схемы проектов структурированы в последовательности связей компонентов и прохождения информации.

9. Построена действующая версия ИИС со сквозным циклом проектирования PROJECT-CAD, на базе которой выполнен ряд разработок. Для ИИС PROJECT-CAD разработана технология создания библиотек типовых элементов по методу раскрутки и свертка проектов для обеспечения возможности моделирования в среде P-CAD.

Научные результаты, полученные в диссертации, используются при выполнении хоздоговорных и госбюджетных научно-исследовательских работ, выполняемых на кафедре математического обеспечения и применения ЭВМ, разработках НИИ многопроцессорных вычислительных систем и учебном процессе ТРТИ.

Основные результаты диссертации опубликованы в работах:

1. Вжняков Ю.М. Инструментарий разработчика СБИС. Монография. Таганрог: ТРТИ, 1993. 179 с.

2. Вишняков Ю.М. Ассоциативная параллельная минимизация. //Материалы Республиканской конференции "Применение кодов Фибоначчи в системах обработки и отображения информации. Винница, ВПИ, 1990.

3. Вишняков Ю.М. Параллельный поиск оптимальных покрытий в условиях частично неопределенной информации //Материалы 34 Международного научного коллоквиума 23-27.10.1989. Секция В 4.2 Высшая техническая школа, Ильменау, ГДР. 1989.

4. Вишняков Ю.М. Параллельный поиск сокращенных дизъюнктивных нормальных форм частично определенных булевых функций. //Известия АН Арм. ССР (серия ТН), 1990. T. XLIII. N1. С.28-31

5. Вишняков Ю.М. САПР информационно избыточных помехоустойчивых вычислительных устройств. //Материалы Межреспубликанского семинара "Интеллектуалькые САПР СБИС", Ереван, 1988. С.109-110

6. Вишняков Ю.М. Синтез комбинационных схем на высокоизбыточ-

ных кодах. //Материалы Республиканской конференции "Проектирование высокопроизводительных преобразователей формы информации, Киев, 1986.

7. Мелихов А.Н., Вишняков Ю.М. Языковые средства структурного описания цифровых схем. //Материалы Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР". Таганрог, 1992. С.22-23.

8. Визшяков Ю.М. Частичные булевые функции и кодовая избыточность в .вычислительных системах. //Многопроцессорные вычислительные структуры: межзед. темат. науч. сб. Таганрог, 1989. Вып.11(XX). С.44-47

9. Вишняков Ю.М., Попов Д.И. Ассоциативная параллельная минимизация булевых функций //Материалы Междунар. и.т. конференции. Актуальные проблемы фунд. наук. М., ГКНТ СССР, ГК НО СССР. Московский ТТУ им. И.Э. Баумана, 1991, сб. докл. Т.2. С.39-41.

10. Вишняков Ю.М. Автоматная Р-модель дискретного устройства. //Синтез алгоритмов сложных систем: межвуз. сб., Таганрог, ТРТИ, 1986. Вып. 6. С.105-108

11. Вишняков Ю.М., Калачев В. А. Теоретические основы САПР помехоустойчивых дискретных устройств на основе парафазной логики. //Интеллектуальные САПР. Материалы Межреспубликанского семинара "Интеллектуальные САПР СБИС". Ереван, 1988. С.55-56.

12. Вишняков Ю.М., Попов Д.И., Моргачев Р.В. АРМ разработчика помехоустойчивых цифровых устройств. //Материалы Республиканской конференции "Применение кодов Фибоначчи в системах обработки и отображения информации. Винница, ВПИ, 1990.

13. Вишняков Ю.М. Синтез асинхронных дискретных устройств //Методы построения алгоритмических моделей сложных систем: межвуз. сб., Таганрог, 1986. Вып. 6. С.142-145

14. Вишняков Ю.М. Использование микропроцессоров для построения помехоустойчивых АЦ-преобразователей. //Материалы Всесоюзной конференции "Применение интегральных микросхем, микропроцессоров, микроэвм, микроэлектр. технологии в приборостроении". Орел,.1979.

15. Стахов А.П., Вишняков Ю.М. О повышении информационной надежности аналого-цифровых преобразователей следящего типа. //Материалы II 1-го Всесоюзного симпозиума "Проблемы создания преобразователей формы информации". Киев, Наукова думка, 1976.

16. Мелихов А.Н., Вишняков Ю.М. Компьютерная технология обучения на базе персональных ЭВМ. //Материалы 35-го Международного

научного коллоквиума, 22-25.10.1990. Секция АВг, Высшая техническая школа, Ильыенау, ГДР, 1990.

17. Вишяков Ю.М., Мелихов. А. Н. Использование естественной избыточности переходов для повышения достоверности функционирования дискр. устр. Материалы IX симпозиума по проблеме избыточности в информ. сист. Ленинград, ЛИАП, 1986. Ч.З. С.130-134.

18. Вишнякоь Ю.М., Калачев В.А. Избыточность и надежность вычислительных систем. //Автоматизация проектирования электронной аппаратуры: медвуз, сб. Вып. 1. Таганрог, 1982. С.143-145.

19. Вишняков Ю.М., Калачев В.А. Аспекты введения избыточности в вычислительные системы. Материалы Всесоюзной конференции" Оптимизация технических систем", Винница, 1979.

20. Стахов А.П., Вишняков D.M., Соляниченко H.A. Об одной способе минимизации переключательных функций, заданных на нормальных Р-кодах Фибоначчи. //Вопросы преобразования информации: ыежвуа. науч. сб. Таганрог, ТРТИ, 1977.

21. Вишяков Ю.М., Онопко В.Л. Об одном подходе и проектированию помехоустойчивых программируемых АЦП. //Материалы YI Всесоюзной конференции "Развитие и использование аналого-цифровой вычислительной техники". М., 1981.

22. Стахов А.П., Вишняков Ю.М. О некоторых свойствах параллельных "фибоначчиевых" счетчиков. //Статистический анализ, моделирования процессов и систем: межвуз. научн. сб. Таганрог, ТРТИ. 1977.

23. Стахов А.П.. Галалу В.Г., Вишняков Ю.М. Оценка помехоустойчивости алгоритмов ац-преобразования. //Вопросы преобразования информации: межвуз. науч. сб. Таганрог, ТРТИ. 1S77.

24. Стахов А.П.. Виввяков Ю.М. О быстродействии "фибоначчиевых" асинхронных счетчиков импульсов. //Статистический анализ, моделирования процессов и систем: межвуз. науч. сб. Таганрог, TP«. 1976.

25. Браткевич В.В., Галалу В.Г., Вишняков Ю.М.. Лужецкий В.А. Двухканальный Оыстродействуирй помехозациценный аналого-цифровой преобразователь. // "АЦ и ДА преобразователи: межвед. тем. науч. сб., Таганрог, ТРТИ. 1974. Вып.1. С.164-180.

26. Браткевич В.В., Галалу В.Г.. Вишняков Ю.М.. Лужецкий В.А. Оценка помехоустойчивости некоторых алгоритмов ац-преобразования. // "АЦ и ЦА преобразователи: межвед. тем. науч. сб., Таганрог. ТРТИ. 1974. ВЫП.1. С.177-180.

27. Вишняков Ю.М., Аваков С.Ю. Использование естественной избыточности переходов для контроля дискретных устройств. //Синтез алгоритмов сложных систем: межвед. сб. Таганрог, 1984. Вып.5. С.106-108.

28. Вишняков Ю.М., Аваков С.Ю. Об одной модели асинхронного автомата. //Материалы Региональной научно-технической конференции молодых ученых и специалистов "Разработка и применение средств вычислительной техники". Таганрог, 1986. С.49-50.

29. Вишняков Ю.М., Мелихов А.Н., Азаков С.Ю. Динамический контроль дискретных устройств. //Вопросы технической диагностики, межвуз. сб. Ростов н/Д: РИСИ, 1984. С.127-131.

30. Вишняков Ю.М., Селянкин В.В., Попов Д.И., Моргачев Р.В. Компилятор языка описания схем. //Материалы Региональной научно-технической конференции, посвященной дна Радио: тезисы докладов. Ростов-на-Дону, 1991. С.40-41.

31. Вишняков Ю.М., Селянкин В.В., Попов Д.И., Моргачев Р.В. Язык и компилятор описания цифровых схем. //Материалы научно-технической и научно-методической конференции, посвященной 40-лети» ТРТИ: тезисы докладов. Таганрог, 1992. С.29-30.

32. Вишняков Ю.М., Селянкин В.В., Попов Д.И., Моргачев Р.В. Язык описания цифровых схем. //Материалы Региональной научно-технической конференции, посвященной дню Радио: тезисы докладов. Ростов-на-Дону, 1992. С.42-43.

33. Вишняков Ю.М. Инструментальная поддержка процесса проектирования средств вычислительной техники. //Материалы научно-технической и научно-методической конференции, посвященной 40-летию ТРТИ: тезисы докладов, Таганрог, 1992. С.29-30

34. Вишняков Ю.М. Инструментальные средства разработчика вычислительных систем . //Материалы Региональной научно-технической конференции, посвященной дню Радио: тезисы докладов. Ростов на Дону, 1992. С.40-41

35. Вишняков Ю.М., Захаревич В.Г., Мелихова 3.А. Информационно-советующая система управления мартеновским скрап-процессом. //Известия СКНЦ ВШ. Сер. "Технические науки". 1983. N 2. С.60-63.

36. Вишняков Ю.М., Аваков С.Ю. Устройство контроля для пересчетных схем. //Системы сбора и обработки измерительной информации. Таганрог, 1985. Вып.6. С.116-121.

37. Вишняков Ю.М. Системное программирование. Конечные распознаватели: Учебное пособие по плану Минвуза РОХСР. Таганрог:

ТРТИ, 1991. 74 с.-

33. Вишняков Ю.М. Системное программирование. Ассемблеры и Макрогенераторы:■ Учебное пособие по плану Минвуза РСФСР. Таганрог: ТРТИ, 1S85. 65с.

39. Вишняков Ю.М., Попов Д.И. Автоматизированный обучающий модуль. Ассоциативная параллельная минимизация булевых функций. Per. номер ОФАП 148.7СХХ3.233 ГОСФАП 50910000328.

40. Вишняков Ю.М. и др. A.c. ЧССР N 253293 "Многокаскадный счетчик с контролем" от 4.05.88.

41. Вишняков Ю.М. и др. Двоичный счетчик с последовательным переносом. A.C.N 577682. Бюлл. N 39, 25.10.77.

42. Вишняков Ю.М. и др. Патент ГДР N 252305 "Многокаскадный . счетчик с контролем" от 16.12.87 (по заявке П.Р).

43. Вишняков Ю.М. и др. Положительное решение о выдаче патента патентного ведомства ПНР от 28.06.79 N 199745. Официальный, бюллетень ПНР N 9/78 от 19.07.77..

44. Вишняков Ю.М. и др. Способ приведения р-кодов Фибоначчи Патент США N 4187500.

45. Вишняков и др. Способ приведения р-кодов Фибоначчи. Патент Англии N 1543302, опубликован 06.06.79.

46. Вишняков Ю.М. и др. Устройство для приведения р-кодов Фибоначчи к минимальной форме. A.c.N 2359460. Бюллетень информации N7. Вып. 104, 1978.

47. Вишняков Ю.М., Аваков С.Ю. A.c. ГДР N 260019 "Счетное устройство с контролем" от 01.02.89.

48. Вишняков Ю.М., Аваков С.Ю. Счетное устройство с контролем. A.c. N 1285591. Бюллетень N 3, 23.01.87

49. Вишняков Ю.М., Аваков С.Ю. Устройство для контроля счетчика импульсов. A.c. N 1043668. Бюллетень N 35, 29.03.83

50. Вишняков Ю.М., Аваков.С.Ю. Счетное устройство с контролем" а.с. ЧССР N 260019 от 14.02.89.

51. Вишняков Ю.М., Калачев В.В., Калачева Е.И. АОМ "Конечные распознаватели", per. номер ОФАП 148.7000.260 ГОСФАП 509.10000.340

52. Вишняков Ю.М., Калачев В.В., Калачева Е.И. АОМ "Конечные распознаватели", per. номер ОФАП 148.7000.261 ГОСФАП 509.10000.339.

53. Вишняков Ю.М., Мелихов А.И., Кривоносова Л.Ю. АОМ "Прямые методы трансляции. Трансляция операторов", per. номер ОФАП

148.7000.266 ГООФАП 509.10000.347.

54. Вишняков Ю.М., Мелихов А.И., Мешвилиани А.Д. ЛОМ "Прямые методы трансляции. Трансляция процедур и описаний", per. номер ОФАП 148.7000.265 ГООФАП 509.10000.346.

55. Вишняков Ю.М., Мелихов А.И., Пилипушко Е.М. Автоматизированный обучающий модуль. Ассоциативная параллельная минимизация булевых функций. Свидетельство о регистрации в реестре программ для ЭВМ ГК СССР по ВТ и информатике N6 от 14.11.89

56. Вишняков Ю.М., Мелихов А.И., Райкова И.В. Автоматизированный обучающий модуль. Конечные автоматы. Per. номер ОФАП 148.7000.264 ГООФАП 509.10000.345.

57. Мелихов А.И., Вишняков Ю.М., Аваков С.Ю. Многокаскадный счетчик с контролем. A.c. N 1156251. Бюлл. N18, 15.05.85.

Среди работ , опубликованных в соавторстве, автором диссертации получены следующие результата: [7,31,323 - сформулировань требования к интерфейсу на базе структурно-языкового подхода; tl5,21-26,44-463 - разработаны методы логического проектирования информационно-избыточных ац-преобразователей; СИЗ - предложен концепция КИС; [9,12,39,55,] - разработаны ассоциативная минимизация БФ и ее программная реализация; [16,35] - сформулировань требования к пользовательскому интерфейсу информационных систем; [17-20,27,29,40-43,47-503 - разработано структурное проектирования ДУ, в т.ч. с учетом информационной избыточности; [28] - предложено Р-представление конечного автомата; [51-53,56] - сформулированы подходы к системному проектированию ДУ.