ББК 32.973.2 А22 УДК 681.32.069:681.3.02 " Автоматизированное проектирование цифровых Д22 устройств / С. С. Бадулин, Ю. М. Барнаулов, В. А. Бердышев и др.; Под ред. С. С. Бадулина.—М.: Радио и связь, 1981.—240 с., ил.— (Проектирова- ние радиоэлектронной аппаратуры на интегральных [микросхемах). В пер.: 1 р. 30 к. асснотрены вопросы логического проектирования цифровых уст- 1т.„,„„„^,,,, ^^пмяп1,нм1' методы синтеза дискретных устройств, ---- г\^_ ройств. Приведены формальные методы синтеза дискретен^ J,.^^.. их логического моделирования и построения проверяющих тестов. иовное внимание уделено практическим методам, алгоритмам и про- граммам, а также принципам автоматизации этих процессов Для специалистов в области разработки средств цифровой техники и систем автоматизированного проектирования. Может быть полезна Ос- и систем студентам вузов 30502-143 А ————————4—81 (С. р.) 046(01)-81 240ГзОСОООО ББК 32.973.2 6Ф7.3 ? ?. гй=, "в. ?: STK Г: -S,^ с*: hSX Я; &. Й=, В. И. Мазнев. Редколлегия: Алсксенко А. Г., Бадулин С. С., Букреев И. И., Васенков А. А., Высоцкий Б. Ф. (отв. редактор), Гальперин Е. И. (зам. отв. редактора), Грозно- ва В. И., Конев Ю. И., Якубовский С. В. Рецензенты: докт. техн. наук П. П. Пархоменко, докт. техн. наук Ю. Н. Бар- маков, канд. техн. наук Л. С. Бутнева, В. Л. Кишкин. Редакция литературы по радиоэлектронике. Издательство «Надио и связь», 1981 г. ПРЕДИСЛОВИЕ Настоящая книга является одной из книг серии «Проектирование радиоэлектронной аппаратуры на интегральных микросхемах» и по- священа вопросам логического проектирования цифровых устройств. Характерными особенностями современной аппаратуры являются высокое насыщение ее вычислительными устройствами разного назна- чения, развитая логическая структура, широкое применение инте- гральных микросхем и многослойного печатного монтажа, высокая степень интеграции блоков и узлов. Разработать такую аппаратуру в сжатые сроки традиционными «ручными» методами невозможно. По- этому и возникла настоятельная необходимость перехода на принпи- пиально новые методы проектирования и производства радиоэлектрон- ной аппаратуры с помощью вычислительных машин, математических средств, программных автоматов. Автоматизация процессов проекти- рования и изготовления элементов и узлов радиоэлектронной аппара- туры стала одной из важнейших народнохозяйственных задач. В настоящее время процесс проектирования сложного цифрового устройства базируется на интуиции и опыте разработчиков, исполь- зующих в основном эвристические методы. Этот процесс можно пред- ставить в виде нескольких этапов синтеза: блочного (структурное про- ектирование), логического и технического (конструкторского, тополо- гического). На этапе блочного синтеза разрабатывается структурная схема устройства. Все устройство разбивается на отдельные функциональ- ные блоки. Определяются задачи, решаемые каждым блоком. Намеча- ется общий план обмена информацией между ними. Уточняются ал- горитмы работы отдельных блоков. Этот этап является наиболее слож- ным для автоматизации. Практически рабочих алгоритмов, позволяю- щих решать и автоматизировать задачи блочного синтеза, пока не существует. Поэтому процесс блочного синтеза проводится в основном интуитивно. Единственным средством, используемым в настоящее вре- мя для автоматизации на этом этапе, является моделирование. На этапе логического синтеза разрабатываются принципиальные схемы блоков. В настоящее время существуют алгоритмы, позволяю- щие практически полностью автоматизировать процесс проектирова- ния на этом этапе. Этап технического синтеза объединяет, как известно, вопросы раз- мещения микросхем на поле печатной платы (ячейки), трассировки со- единений, изготовления конструкторской и технологической докумен- тации, управляющих перфолент для производственных автоматов. В книге рассмотрены вопросы, относящиеся к этапу логического проектирования цифровой аппаратуры. В общем процессе создания аппаратуры этот этап, технически сложный, требует высокой квали- фикации специалистов. С другой стороны, теория синтеза цифровых устройств в настоящее время в достаточной степени уже разработана. Поэтому и естественно ожидать здесь значительного экономического эффекта от автоматизации. Основное внимание в книге уделено практическим методам и ал- горитмам машинного проектирования цифровой аппаратуры и построе- нию системы логического проектирования на их основе. Авторы глубоко благодарны докт. техн. наук, проф. П. П. Пархо- менко, докт. техн. наук Ю. Н. Бармакову, канд. техн. наук Л. С. Бутневой и инженеру В. Л. Кишкину за большое внимание к работе и ценные замечания, способствовавшие улучшению содержания и структуры книги. ВВЕДЕНИЕ Работы по автоматизации проектирования в нашей стране и и рубежом начали развиваться с конца 50-х годов, когда была создана техническая база — организовано серийное производство цифровых вычислительных машин. Естественно, что автоматизация коснулась прежде всего проектирования самих вычислительных машин. Эта объясняется рядом причин, из которых отметим следующие. Во-пер- вых, сложность вычислительных систем требует участия большого числа специалистов в процессе проектирования, что при ручных ме- тодах разработки приводит к большому числу ошибок, выявление я устранение которых становится серьезной проблемой. Во-вторых, бы- стрый технический прогресс в этой области привел к тому, что время, необходимое для проектирования, подготовки документации и произ- водства вычислительных машин стало соизмеримым с временем их морального старения. В-третьих, специалисты в области вычислитель- ной техники были лучше других подготовлены к использованию ЭВМ для автоматизации своего труда, так как процессы создания систем машинного проектирования и систем математического обеспечения (разработка формальных языков, трансляторов, программирование логических задач) имеют много общего. Первоначально решались отдельные задачи автоматизации проек- тирования [1—5], для которых к тому времени были созданы теоре- тические основы. Однако уже с начала 60-х годов была осознана не- обходимость в комплексном подходе. К тому времени относится и на- чало работ по созданию систем машинного проектирования как ЭВМ, так и других дискретных устройств обработки информации. Появилась также необходимость в более строгой формализации процесса проек- тирования, выявились и различные подходы. В данной книге будем придерживаться разбиения всего процесса проектирования на четыре этапа: системное, логическое, техническое и технологическое. На первом этапе разрабатывается общая архитек- тура проектируемой машины, уточняются ее характеристики, струк- тура и алгоритмы входящих в нее устройств, а также выбирается эле- ментная база. На втором каждое устройство по алгоритму его функцио- нирования представляется в виде структуры, компонентами которой является выбранная элементная база, а также проводится построение тестов проверки и поиска дефектов. На третьем этапе решаются зада- чи привязки полученной структуры к конструкции: компоновка, раз- мещение и трассировка, а также составляется конструкторская доку- ментация. На четвертом выпускается документация, необходимая для изготовления разрабатываемых устройств, и управляющие перфолен- ты для производственных автоматов. Так как предметом настоящей книги является логическое проек- тирование, остановимся на нем более подробно. Уже с самого начала развития работ в этой области наметились два направления, одно из которых основано на методах анализа, другое — на методах синтеза. В качестве примера реализации первого направления приведем систе- му моделирования цифровых устройств [б], разработанную в середине 60-х годов. Входным языком этой системы является язык МОДИС (моделирование дискретных систем), позволяющий описывать алго- ритмы работы проектируемых устройств на уровне функциональных узлов (регистров, счетчиков, дешифраторов) и базовых элементов. Система была предназначена для определения реакции проектируемо- го устройства на заданные входные сигналы, что. давало возможность разработчику проверять правильность построения функциональной схемы, выявлять запрещенные ситуации, проверять работу устройства при тех или иных неисправностях и анализировать эффективность конт- рольных программ. Система позволяла моделировать устройства сред- ней величины — типа специализированного вычислительного устрой- ства. Программы моделирования были реализованы на ЭВМ типа М-220. В этой системе, как и в других, основанных на методах анализа, соб- ственно проектирование, т. е. создание вариантов функциональных и логических схем и выбор приемлемого варианта, остается за разработ- чиком. Система является инструментом, с помощью которого можно быстро и объективно оценить вариант спроектированного устройства, и, таким образом, заменяет макетирование. В качестве примера реализации второго направления можно при- вести малую систему автоматизации синтеза цифровых автоматов [7], работа которой основана на каноническом методе структурного син- теза [8]. Система состояла из 17 программ и диспетчера. В ней впер- вые были объединены все этапы синтеза: абстрактный (построение таблиц переходов и выходов, минимизация числа внутренних состоя- ний), структурный (кодирование внутренних состояний автомата, построение функций возбуждения и выходов), комбинационный (ми- нимизация булевых функций и построение функциональных схем), надежностный (учет нагрузочных свойств элементов). Алгоритм ра- боты синтезируемого автомата задавался либо таблицей переходов и выходов, либо отображениями, либо микропрограммой. Система осу- ществляла построение функциональных схем автоматов на элементах И—НЕ и триггерах со счетным входом. Все первые программы, в том числе и программы упомянутых си- стем, были составлены в машинных кодах. Трудности отладки и сты- ковки программ поставили вопрос о необходимости создания языка программирования достаточно высокого уровня и трансляторов с не- го, ориентированных на решение задач логического проектирования. Важным этапом в этом направлении стало создание языка ЛЯПАС [9] и его последующих модификаций. Наиболее близкий к нему язык АПЛ [10], разработанный в США, не получил в нашей стране широ- кого распространения. Из отечественных языков, ориентированных на решение задач автоматизации проектирования цифровой аппара- туры, отметим также язык ПРОЕКТ [б], построенный на основе язы- ка АЛГОЛ-60, в котором в качестве переменных можно использовать двоичные векторы и последовательности символов. На основе программирующей системы с входным языком ЛЯПАС-71 для ЭВМ М-220 в 1972 г. была создана система синтеза асинхронных цифровых автоматов, позволяющая проектировать ячейки, содержа- щие управляющие автоматы, комбинационные схемы и разработанные вручную узлы [111. Эта система была информационно совместима с си- стемой технического проектирования и имела символьные вход и вы- ход. В системе синтеза имелся также архив, хотя и недостаточно раз- витый. Исходными данными для нее являлись: таблицы переходов и выходов или микропрограммы для автоматов; системы булевых функ- ций в интервальной форме или в форме алгебраических выражений для комбинационных схем; таблицы соединений для схем, разработанных вручную; таблица межблочных соединении для устройства в целом. Синтез асинхронных автоматов осуществлялся в базисе ЛОГИКА-2 на элементах И—НЕ либо И—НЕ и И—ИЛИ—НЕ. В качестве эле- ментов памяти использовались триггеры с раздельными входами, ко- торые строились из логических элементов, для чего в них вводились обратные связи. Аналогично синтезировались комбинационные схемы. Результаты синтеза записывались в архив, где хранились описания остальных блоков устройства. Системой решались также задачи раз- биения устройства на ячейки (критерий — минимальное число ячеек), компоновки базовых элементов в микросхемы и формирования комплек- та перфокарт в форме, необходимой для ввода в систему технического проектирования. Несмотря на некоторые нежелательные ограничения (число интервалов системы булевых функций, суммарное число вход- ных полюсов и внутренних переменных и др.) система была близка к тому, чтобы удовлетворить запросы разработчиков. К концу 60-х годов подавляющее большинство систем логического проектирования развивалось в рамках более общих систем, включаю- щих и другие этапы проектирования. Из таких систем рассмотрим си- стемы ПРОЕКТ [12], ALERT (131 и ЕСАП [14], первые две основаны на методах синтеза, последняя на моделировании. Система ПРОЕКТ (рис. 1) предназначена для проверки и отработки новых принципов построения систем автоматизированного проектирования. Основной ее особенностью является универсальность, что позволяет использо- вать различные алгоритмы проектирования, расширять состав средств программирования и проектировать устройства различных классов. Исходные данные на проектируемое устройство задают в виде алгоритма его функционирования на языке данных, в качестве кото- рого используют совокупность языков АЛГОРИТМ (для описания функциональных свойств устройства) и СТРУКТУРА (для описания его структурных свойств). Эти алголоподобные языки позволяют описывать проектируемые устройства (идеализированную логиче- скую модель) на любом уровне иерархии. Процесс проектирования за- ключается в постепенном дроблении устройства на все более и более мелкие компоненты (направление процесса показано на рис. 1 штри- ховыми стрелками). Проектирование осуществляется в режиме диало- га последовательным выполнением директив разработчика. 7 На первом этапе описание устройства моделируется на тестах, со- ставляемых вручную, для отработки алгоритма и устранения ошибок в его записи. С алгоритмической точки зрения устройство в целом мож- но представить в виде композиции блоков (подустройств), относящих- ся к одному из следующих типов: операционные, управляющие, функ- циональные. Операционные блоки — это узлы, содержащие регистры, управляющие — схемы управления с памятью, а функциональные — комбинационные схемы. Такое разделение обусловлено тем, что ал- горитмы синтеза для различных блоков обладают своей спецификой. На этапе блочного синтеза из первичного описания последовательно выделяют операционные, управляющие и функциональные блоки до тех пор, пока все устройство не будет представлено в виде их компо- зиции. Далее проводят синтез функциональных, операционных и управ- ляющих блоков. Однако некоторые особенности системы не позволяют непосредственно применять классические алгоритмы синтеза. Напри- мер, функциональный блок может иметь многоразрядные входные и выходные переменные. Тогда его синтез осуществляют в два этапа. На первом выполняют поразрядное разбиение, в результате которого функциональный блок преобразуется в структуру из простых функцио- нальных блоков. На втором этапе для всех простых компонент син- тезируют (классическим способом) комбинационные схемы. Аналогич- ная особенность имеет место и для управляющих блоков. Работой системы ПРОЕКТ управляет разработчик с помощью ди- ректив. Каждая директива является именем той или иной программы проектирования, которая вызывается на рабочее поле оперативной памяти с помощью управляющей программы. Система выполняет произвольную последовательность директив из числа имеющихся в наличии. Как видно из рис. 1, исходные данные и конечные результаты директив проектирования сохраняются в архи- ве данных. При этом принят стандартный формат внутреннего алго- ритмического и структурного описаний в виде деревьев. Каждому устройству в системе ПРОЕКТ соответствует массив, имя которого совпадает с именем этого устройства. Этот массив делится на нефик- сированное число разделов, из которых первые пять (алгоритм, струк- тура, таблица идентификаторов, раздел характеристик, раздел типов имен) являются стандартными. В разделе характеристик хранятся описания входных и выходных переменных и их характеристики, а в Директиды разработчика Управляющая npospaHmi — ^^^~" Нивелирование ») Елочный синтез ,' ' 1' , г Рис. I разделе типов men устанавливается соответствие г>;ежлу идентифика- торами и их типами. Другие разделы вводятся и используются в за- висимости от конкретных методик проектирования. При создании системы ПРОЕКТ большое внимание было уделедо языкам программирования: была предпринята попытка осуществить последовательное расширение языка, являющегося базисным. В ка- честве такого языка был выбран автокод ЭВМ. М-220. Идея расширения заключается здесь в том, что каждая модификация языка содержит в себе язык предыдущего уровня в качестве подмножества. Вместе с тем такое расширение содержит подмножество предложений более высоко- го уровня, которыми можно пользоваться независимо от остальной части языка. В целом система ПРОЕКТ предоставляет разработчику достаточ- но много возможностей: проектирование устройства по частям, раз- деление по времени (например, моделирование за несколько подходов), работу в режиме диалога, возможность неограниченного пополнения директив проектирования. Система содержит 1,5 млн. машинных ко- манд и реализована на двухмашинном комплексе М-220 и БЭСМ-6 с развитой системой периферийных устройств. Система ALERT была создана фирмой IBM в рамках более общей системы, включающей также построение схем из базовых элементов и техническое проектирование. Исходными данными для системы ALERT является алгоритм функционирования проектируемого уст' ройства на языке АПЛ. Так как этот язык достаточно высокого уров- ня и предназначен для программирования логических задач, оказалось возможным использовать его для описания дискретных устройств, На первом этапе происходит трансляция исходного описания во вну- треннее представление, используемое во всех последующих алгорит' мах. На втором и третьем этапах (называемых выбором дешифраторов и макрогенерацией) из исходного описания выделяют комбинационные схемы. На четвертом (этапе последовательностного анализа) выделяют и объединяют в группы микропрограммы с учетом их выполнения по времени. На пятом этапе все переменные, которые должны сохранят^ свое значение на время более одного такта, заменяют триггерами с раз- дельными входами. Кроме автоматической процедуры подстановки триггеров можно заранее объявить некоторые переменные триггера- ми, например при замене многоразрядной переменной регистром. Шестой этап заключается в построении функций, реализующих мик' ропрограммы. На седьмом и восьмом все полученные описания объе- диняют в единую систему булевых функций, которая и является ре- зультатом работы системы ALERT. Затем система логического синтеза осуществляет минимизации системы булевых функций и построение схемы из соответствующих базовых элементов, а система технического проектирования решает задачи компоновки, размещения и трассировки, а также формирует документацию для производства. Специализированная система автоматизации проектирования ЕСАП ориентирована на проектирование ЕС ЭВМ Методика логиче- ского проектирования, заложенная в систему (здесь она называется 9 математическим проектированием), заключается в последовательном моделировании описания ЭВМ на различных уровнях иерархии, начи- ная с самого высокого. При этом переход с уровня на уровень осущест- вляется разработчиком вручную с помощью определенных приемов преобразования описаний. В качестве входного используется язык ОСС, который к настоящему времени имеет свыше десятка модифика- ций и позволяет описывать как алгоритм функционирования устройст- ва, так и его схему (структуру), В основу построения системы модели- рования положен модульный принцип. В языке предусмотрены модули трех типов: алгоритмические, схемно-алгоритмические и схемные. Каждый модуль представляет собой законченное описание, которое может быть независимо промоделировано на ЭВМ. Язык ОСС содержит набор средств для описания параллельно про- текающих процессов, широкий набор операций и типов переменных. Характерной особенностью его является табличное представление опе- раторов. Это позволяет отказаться от некоторых служебных слов, сделать описание более компактным и доступным для понимания, а также одновременно является удобной формой документации. Особен- ностью является также методика получения формального описания моделируемых устройств. В целом математическое обеспечение системы ЕСАП представляет собой совокупность функциональных программ и диспетчера, управ- ляющего их работой. В системе имеется также архив данных, в котором хранятся описания типовых узлов, чертежей соединений, описания панелей и т. д. Основное внимание в системе уделено логическому мо- делированию, программам технического проектирования и выдаче документации (например, автоматическое вычерчивание схем алго- ритмов) . В настоящей книге отражен опыт авторов, накопленный при со- здании в содружестве с рядом организаций (Севастопольский прибо- ростроительный институт, Институт технической кибернетики АН БССР и др.) системы автоматизированного проектирования. Принятая в системе (рис. 2) методика проектирования характери- зуется разделением алгоритмов на независимые группы: моделирова- ния работы устройств; синтеза устройств; структурных преобразова- ний; построения тестов проверки и поиска дефектов. Каждой из этих групп соответствует своя подсистема, связь между которыми осуш.ест- Исхпвные ванные Чех ffa пВи тнь ые | i/'w е \ \ ульп паты Исходные данные Блок директивного дпраИлЕншк МОДЕЛИРОВАНИЕ ' ' страктярА Результаты СИНТЕЗНе 3 xoSH лниь / АРХИВ —>!j"b Результаты ТЕСТЫ не 4 1 к ' У.-.. Рис. 2 10 вляется через общий архив данных. Управление системой реализуется с помощью директив. Рассмотрим процесс проектирования цифрового устройства этой системой. Разработчик представляет проектируемое устройство в ви- де схемы, компонентами которой могут быть упраляющие блоки (автоматы), типовые функциональные решения (ТФР), блоки, разра- ботанные вручную,, и т. д., т. е. самые различные узлы радиоэлектрон- ной аппаратуры. Эта схема описывается на формальном языке СТРУКТУРА, принятом в системе в качестве единого средства описа- ния структуры устройства с произвольной степенью детализации. Алгоритмы функционирования каждой компоненты представляются на алгоритмическом языке, в качестве которого используется модифи- цированный язык АЛГОРИТМ системы ПРОЕКТ. Описание в целом вводится в подсистему МОДЕЛИРОВАНИЕ и проверяется по тестам разработчика. В результате получаются отлаженные описания ал- горитмов отдельных компонент и структуры всего устройства. Далее алгоритмы управляющих блоков (задаваемые микропрограммами) поступают в подсистему СИНТЕЗ, где осуществляется синтез схем в базовых элементах, которые и записываются в АРХИВ. Описания остальных блоков на языке СТРУКТУРА через соответствующий транслятор также вводятся в АРХИВ. После того как в АРХИВе системы найдены схемы всех блоков и описание структуры устройства в целом, вступает в действие под- система СТРУКТУРА. С ее помощью устройство разбивается на ячей- ки, формируются схемы отдельных ячеек с учетом их конструктивных особенностей и т. д. Наконец, подсистема ТЕСТЫ автоматически строит тестовые по- следовательности для проверки и поиска дефектов сформированных ячеек и выдает соответствующую документацию. В целом система представляет собой совокупность методик, ал- горитмов, программ, инструкций и форм документов, обеспечиваю- щих автоматизированное построение структуры дискретных уст- ройств совместно с тестами проверки и поиска дефектов и выдачу необходимой документации по исходному формальному заданию раз- работчика. В системе используется единый язык описания данных, который позволяет представить алгоритмы функционирования и структуру дискретных устройств на произвольном структурном уров- не. Для обеспечения единой программной реализации системы принят проблемно-ориентированный язык ЛЯПАС-М, позволяющий эффек- тивно программировать логико-комбинаторные задачи. Все програм- мы системы выполнены на ЭВМ БЭСМ-6. Планируется перевод си- стемы на ЭВМ серии РЯД. В настоящее время с помощью системы проектируются устройства на элементной базе ЛОГИКА-2, однако предусмотрена возможность расширения элементной базы. Для об- легчения проектирования созданы каталог и библиотека ТФР, явля- ющиеся основными компонентами при построении дискретных уст- ройств. Система допускает решение ряда задач с помощью алфавитно- цифрового дисплея типа ВИДЕОТОН. Для обеспечения гибкости си- стемы, т. е. возможности оперативной замены отдельных алгоритмов и синтеза, включения новых этапов проектирования, расширения сер- висных программ, в системе использованы единые форматы данных, обеспечивающие информационную совместимость отдельных программ. Большинство программ системы снабжены синтаксическим и семанти- ческим контролем, что облегчает обнаружение и поиск ошибок в ис- ходных данных. Центральное место в системе занимает АРХИВ, в котором хранят- ся программы, исходные данные и результаты проектирования. АРХИВ делится на текущий и долговременный. В текущем хранятся исходные данные на проектируемое устройство, промежуточные дан- ные и результаты проектирования. В долговременном архиве хранят- ся описания ТФР, микросхем, базовых элементов и программы си- стемы. При создании системы предусмотрена ее совместимость с системой технического проектирования. Для этого ее выходные данные пред- ставлены в форматах, принятых для входа в систему технического проектирования. Система обеспечивает проектирование ячеек разме- ром до 200 микросхем и построение тестов для них. Количество внеш- них контактов ячейки 200, количество контрольных гнезд не превы- шает 128. Список литературы 1. Архангельская А. А., Лазарев В. Г., Рогинский В. Н. Машина для синтеза контактных схем.— Проблемы передачи информации/ АН СССР.— М.: 1959, вып. 1 2. Стогний А. А. О минимизации булевых функций на электронных вычисли- тельных машинах.— В кн.: Вопросы вычислительной техники.— Киев; Техника, 1961. 3. Loberman H., Weinberger A. Formal procedures for connecting terminals with a minium total wire length.— J. Ass. Commut. Machin, 1957, v. 4, № 4. 4. LeeC.Y. An algorithm for path connection and its application.—IRETrans., 1961, v. EC-10, №3. 5. Линский В. С. Алгоритмическое проектирование вычислительных цифровых устройств.— М.: ВЦ АН СССР, 1963. 6. Применение вычислительных машин для проектирования цифровых уст- ройств/Под ред. Н. Я. Матюхина.— М.: Сов. радио, 1968. 7. Малая система проектирования схем цифровых автоматов/Ф. И. Андон, И. И. Брона, Е. А. Войтова и др.— В кн.: Вопросы теоретической кибернети- ки.— Киев, 1965. 8. Глушков В. М. Синтез цифровых автоматов.— М.: Физматгиз, 1962. 9. Закревский А. Д. ЛЯПАС — логический язык представления алгоритмов синтеза. — Материалы научных семинаров по теоретическим и прикладным вопросам кибернетики.— Киев, 1964. 10. Iverson К. Е. A programming language.— N. Y., London, 1963. It. Синтез асинхронных автоматов на ЭВМ/Под ред. А. Д. Закревского.— Минск: Наука и техника, 1975. 12. Глушков В. М., Капитонова Ю. В., Летичевский А. А. Автоматизация про- ектирования вычислительных машин.— Киев: Наукова думка, 1975. 13. Friedman Т. D., lang Shi-Chin. Methods used in a automatic logic design ge- nerator (ALERT).— IEEE Trans, 1969, v. EC-18, № 17. 14. Юрин О. Н. Единая система автоматизации проектирования ЭВМ.— M.I Сов. радио, 1976. 15. Закревский А. Д., Торопов Н. Р. Система программирования ЛЯПАС.— — Минск: Наука и техника, 1978. U Глава первая ПРОГРАММИРУЮЩАЯ СИСТЕМА ПРОЛОГ ДЛЯ ЭВМ БЭСМ-6 1.1. ЯЗЫК ПРОГРАММИРОВАНИЯ И ОСОБЕННОСТИ МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ Система логического проектирования представляет собой большую многоуровневую иерархическую систему, предназначенную для обра- ботки структур данных, отображающих сложные внутренние связи между компонентами проектируемой цифровой аппаратуры. Обра- ботка структур данных, представляемых в виде символьных и двоич- ных наборов, значительно отличается от традиционных числовых рас- четов и пока еще недостаточно оснащена удобными и мощными средст- вами программирования. Постоянное развитие технологической и элементной базы, методов и средств проектирования цифровой аппаратуры связано с непрерыв- ным совершенствованием и модернизацией системы логического про- ектирования. Отсюда вытекают следующие повышенные требования к математическому обеспечению этой системы: — эффективная реализация большого комплекса программ, одно- временно не помещающихся в оперативной памяти ЭВМ; — развитые архивная система и система редактирования и отлад- ки, включая диалоговые возможности общения с ЭВМ; — модульность построения системы, позволяющая заменять одни блоки другими и подключать новые по мере развития системы проек- тирования; — возможность использования системы проектирования на ЭВМ различных типов. В таких традиционных областях использования ЭВМ, как науч- ные и экономические расчеты, уже давно используются программирую- щие системы, созданные на базе языков АЛГОЛ, ФОРТРАН, КОБОЛ, ПЛ/1 и др. Несмотря на неоспоримые достоинства, эти средства плохо приспособлены для создания больших иерархических комплексов программ специальной ориентации. Использование их в качестве ос- новы системы логического проектирования влечет за собой большие затраты на разработку мониторной и архивной систем, а также па- кета программ для решения логических задач, описываемых на язы- ках типа автокода. Все это резко снижает многие качественные и тех- нологические показатели, в том числе и эффективность разрабатывае- мой системы логического проектирования [I]. Теоретические и алгоритмические аспекты логического проекти- рования в настоящее время разработаны весьма основательно. Име- 13 ется и большой задел алгоритмов отдельных этапов проектирования. Однако практическое использование системы логического проектиро- вания зависит от таких ее показателей, как технологичность, гибкость, способность к модернизации и дальнейшему совершенствованию. Не- обходимым условием, обеспечивающим такие возможности, является использование единого достаточно мощного и гибкого средства про- граммирования, в качестве которого авторами был использован Ло- гический Язык Представления Алгоритмов Синтеза — ЛЯПАС-М [2]. Простой синтаксис языка, отсутствие описателей, модульность и др. делают язык ЛЯПАС-М легким для изучения, наглядным и компакт- ным при представлении алгоритмов, что позволяет создавать быстро- действующие эффективные системы. Использование языка ЛЯПАС, ориентированного на решение логи- ко-комбинаторных задач, дает при равном времени разработки про- грамм существенный выигрыш в быстродействии по сравнению с язы- ком АЛГОЛ. Это обусловлено как более быстрым выполнением от- дельных адекватных вычислений, так и более разумной и экономичной организацией данных и самих программ. Аналогичные результаты сравнения и с языками ФОРТРАН и ПЛ/1, Язык ЛЯПАС-М содержит большое число операций обмена с внеш- ними устройствами, архивных операций, операций над массивами и управления распределением оперативной памяти ЭВМ. К последним относятся образование комплекса (занятие Памяти) и отказ от комплек- са (освобождение памяти). Эти операции позволяют программисту эф- фективно использовать оперативную память, управляя ее автомати- зированным распределением. Рассмотрим реализованную на ЭВМ БЭСМ-6 программирующую систему (ПС), ориентированную на решение задач Логического ПРО- ектированйя, — ПРОЛОГ. Построенная на базе языка ЛЯПАС-М, она была использована в качестве основного инструмента создания всей системы логического проектирования, что обеспечило как до- статочно быструю и эффективную разработку отдельных-программ си- стемы, так и их объединение в сложный взаимодействующий комплекс. Отличительной чертой данной программирующей системы является принцип программно-информационной независимости модулей, из которых строится программа, и динамическая обработка управляющих и информационных связей между ними. Вся программа, представляю- щая собой независимый модуль, образуется из отдельных более про- стых модулей — двухполюсников с одним входом и одним выходом. Межмодульная связь также описывается на языке ЛЯПАС-М. Для этого используется специальный класс операций — макрооперации, реализация которых обеспечивается соответствующими программны- ми модулями. Разделение в описаниях модулей и макроопераций опе- рандов на входные и выходные позволяет сделать программные моду- ли полностью независимыми. В программных модулях информационная и постоянная программная части разделены. Информационная часть представляет собой базис- ный информационный модуль (БИМ), объединяющий переменные и характеристики комплексов. Унификация БИМов позволяет лю- 14 бому программному модулю взаимодействовать с лю5ым и даже с не- сколькими БИМами. В этом случае суть информационной связи меж- ду модулями заключается в передаче значений соответствующих параметров из БИМа в БИМ, а управляющей связи — в последова- тельной передаче управления от модуля к модулю. Обработка меж- модульных связей в динамическом режиме позволяет автоматически синтезировать систему прикладных программ из отдельных модулей в той конфигурации, которая требуется в данной реализации вычисли- тельного процесса. Мониторная система, входящая в состав ПС ПРОЛОГ, обеспечи- вает динамический обмен программными и информационными модуля- ми между оперативной и внешней памятью. Работа ПС становится возможной, если в оперативном запоминаю- щем устройстве (ОЗУ) помещается хотя бы один программный модуль, находящийся в данный момент в активной фазе, и необходимые для него информационные модули и массивы. В процессе выполнения от- дельных этапов вычислений в системе организуется вызов новых-про- граммных модулей, удаление при необходимости пассивных модулей и резервирование места для возникающих информационных массивов. Если ресурсы ОЗУ для размещения очередного программного или ин- формационного модуля исчерпаны, происходит перераспределение па- мяти, позволяющее использовать освободившиеся участки. Подобная организация вычислительного процесса позволяет реа- лизовать на ЭВМ большие системы программ, содержащие отдельные подсистемы с переменной иерархической структурой и не помещаю- щиеся одновременно в ОЗУ. При этом весь процесс вычислений авто- матически разделяется на ряд последовательных или циклических фаз. Необходимо только, чтобы ресурсы, требуемые для выполнения каж- дой отделытой фазы, не превышали ресурсов данной ЭВМ. Архивная система и соответствующие операции, входящие в состав языка ЛЯПАС-М, позволяют резко уменьшить объем работ, связан- ных с организацией хранения программных и информационных масси- вов на внешних устройствах: магнитных барабанах (МБ), лентах (МЛ), дисках (МД). Система редактирования, реализованная в режиме разделения вре- мени на базе дистанционных терминалов, во много раз ускоряет про- цесс отладки программ. Каждая программа, написанная на языке ЛЯПАС-М (Л-модуль), после трансляции приобретает некоторую стандартную форму. Транс- ляция Л-модулей происходит независимо друг от друга. Все получае- мые в результате трансляции машинные программы (М-модули) мо- гут свободно перемещаться в ОЗУ, допускают рекурсивные обращения и использование в системах разделения времени. Единая стандартная форма М-модулей на всех уровнях мониторной системы позволяет в принципе строить при помощи базовой системы программирования не только прикладные системы программ, но и операционные системы самих ЭВМ. При необходимости М-модули можно записать в архив программ. За один сеанс работы системы можно транслировать не- сколько Л-модулей, получать сообщения о всех ошибках и передавать 15 управление одному из модулей, который должен быть объявлен голов- ным специальной директивой. Головной модуль, как и другие, может находиться либо в заказе (комплект перфокарт или массив в архиве операционной системы ЭВМ), либо в архиве программ базовой системы. Программирующей системой ПРОЛОГ управляют с помощью спе- циальных директив, позволяющих задавать различные режимы работы транслятора, архивной системы и системы в целом. Система позволяет управлять процессами отладки программ и решения задач с термина- ла, оснащенного дисплеем, что значительно повышает эффективность работы пользователя. За один сеанс связи с ЭВМ можно получить на дисплее сообщения о всех ошибках в программе, внести исправления в исходный текст программы, заменить модули, ранее записанные в архив программ, новыми и выполнить другие операции. В языке программирования ЛЯПАС-М предусмотрен специальный оператор обмена с дисплеем, что позволяет отлаживать алгоритм не- посредственно в режиме диалога и включать возможность диалога в разрабатываемые программы. Таким образом, язык ЛЯПАС-М и программирующая система ПРОЛОГ обеспечивают быстрое и качественное создание эффективных сисюм логического проектирования. 1.2. ОПИСАНИЕ ВЕРСИИ ЯЗЫКА ЛЯПАС-М При разработке ПС ПРОЛОГ была принята версия языка ЛЯПАС-М, описанная в [21. Однако в нее были внесены некоторые изменения и дополнения, связанные с более широкими возможностя- ми устройств отображения информации, имеющимися в составе БЭСМ-6, а также были учтены требования, возникшие при создании на ее базе системы логического проектирования. Несколько по-другому трактуется семантика макроопераций, понятия комплекс и подком- плекс. В составе ПС ПРОЛОГ предусмотрен предтранслятор, который можно использовать для перекодировки информации с исходной вер- сии языка ЛЯПАС-М в реализованную в системе. 1.2,1. Программа Программа состоит из заголовка, последовательности операций и признака конца. Операции выполняются в том порядке, в каком они входят в про- грамму. Этот порядок (называемый стандартным) может нарушаться при выполнении операций перехода, позволяющих передавать управ- ление в «особые точки» программы. «Особые точки» разбивают програм- му на предложения и обозначаются символом П, за которым следует номер предложения, задаваемый в виде натурального числа, не боль- шего 10s — 1. В программе допускается не более 512 предложений. Операция состоит из символа операции (оператора) и списка операндов (последний может отсутствовать). Основные операции язы- 16 ка (логические, арифметические и некоторые другие) используют в ка- честве неявного операнда собственную переменную т, значение ко- торой перед выполнением операции будем обозначать т", а после вы- полнения операции — т+. Собственная переменная т не входит в текст программы в явном виде и обычно выступает в качестве левого операнда операций. После особой точки т+ считается неопределенным. Символы, обозначающие операторы и операнды, выбираются из сим- вольного набора языка. 1.2.2. Символьный набор Программа в языке ЛЯПАС-М представляет собой последователь- ность символов, выбираемых из следующей совокупности, отображае- мой на современных устройствах ввода и вывода информации: 0 1 2 3456789+-/,.-i„t ( ) X = ; I 1 * • • ^ < > :АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩ bIb3K^DFGIJLNQRSUVWZ-s$> \/ А ==' -^ — sss % О _ ! . Знак ,_, обозначает пробел между символами. Ука- занная совокупность символов образует алфавит Л. 1.2.3. Операнды Операнды в программе могут представлять три типа базисных ве- личин: логические векторы, символы, числа или их последователь- ности. Логические векторы—это векторы, компоненты которых мо- гут принимать значения 0 или 1. Число компонент т может быть 40 или 48. Символы—это элементы алфавита Л. Числа —это действи- тельные числа, которые могут быть положительными и отрицательны- ми, целыми и дробными. Следует учитывать диапазон и точность пред- ставления чисел в БЭСМ-6. Числа могут находиться в пределах ± (Ю-19 ... 1019) или быть нулем. В программе в качестве операндов могут выступать переменные, константы, комплексы, элементы и мощности комплексов. Переменные. Переменные обозначаются в программе латинскими буквами А ... Z. В ходе выполнения программы они могут изменять свои значения. Для фиксирования результата очередной элементарной операции используется собственная переменная т (т+). Константы. Значения констант представлены непосредственно в тексте программы. Логические векторы можно обозначать натураль- ными, логическими или единичными константами, символы — сим- вольными, числа — действительными константами. Натуральные константы — обычные выражения натуральных чи- сел в десятичной системе в диапазоне от 0 до 2'"—1, например 0, 5, 589635. Натуральное число, соответствующее натуральной константе, опи- сывает логический вектор в двоичной системе счисления. В программе два натуральных числа, расположенные рядом, разделяются точкой, например 4.1. 17 бивать множество неисправностей на несколько подмножеств, обрабатываемы)! поочередно. После того как тест на первое подмножество неисправностей постро- ен, он моделируется на остальных подмножествах. Проверенные неисправности исключаются, производится новое разбиение оставшихся неисправностей на под- множества, и процедура повторяется. Мощность подмножеств определяется ре- сурсами памяти ЭВМ. 2. Значительную часть неисправностей, возникающих на этапе производства ЦЯ, составляют короткие замыкания (КЗ). Наиболее вероятны КЗ между сосед- ними проводниками. Моделью неисправности типа КЗ является фиктивный эле- мент (И либо ИЛИ в зависимости от схемотехники), включенный в место замы< кания. Моделирование схемы с КЗ и построение тестов проверки КЗ можно осу- ществить, незначительно изменив используемые алгоритмы. 3. Полноту проверки можно повысить, применяя более адекватные методы моделирования и построения тестов. Однако 100%-ная проверка ЦЯ произволь- ной структуры автоматическим тестом не реальна. Чтобы обеспечить полную про- верку, необходимо учитывать требования диагностики еще на этапе проектиро- вания ЦЯ, т. е. разрабатывать контролепригодные структуры. 4. Представляется весьма эффективной разработка средств диалога между пользователем и системой. Диалоговая система построения тестов обеспечит, с одной стороны, оценку интуитивных решений пользователя, а с другой — кор- рекцию результатов, обусловленную неадекватностью алгоритмов. Список литературы 1. Основы технической диагностики/В. В. Карибский, П. П. Пархоменко, Е. С. Согомонян, В. Ф. Халчев; Под ред. П. П. Пархоменко.— М.; Энергия, 1976. 2. Гольдман Р. С., Чипулис В. П. Техническая диагностика цифровых уст- ройств.— М.: Энергия, 1976. 3. Roth J. P., Bouricius W. G., Schneider P. R. Programmed algorithms to com- pute tests to detect and distinguish between failures in logic circuits.— IEEE Trans., 1967, v. EC-16, № б, р. 567—580. 4. Бессонов А. А., Стешкович Н. Т., Турчина Е. Д. Автоматизация построения контролирующих тестов.— Л.: Энергия, 1976. 5. Лазаряк Э. А. О задаче построения тестов для дискретных устройств с об- ратными связями.— Вопросы радиоэлектроники. Сер ЭВТ, 1976, вып. 7, с, 3—7. 6. Голубева Г. А. Подбор эффективных случайных тестов. — Автоматизиро- ванные системы контроля.—Труды ИНЭУМ, 1971, вып. 15, с. 101—110. 7. Seshu S. On an improved diagnosis program. — IEEE Trans., 1966, v. EC-14, № 1, p. 76—79. 8. Hardie F. H., Suhocki. R. J. Design and use of fault simulation for Saturn com- puter design.— IEEE Trans., 1967, v. EC-16, № 4, p. 412—429. 9. Вейцман И. Н., Жук В. Е., Флеров А. Б. Вероятностная система синтеза контролирующих тестов на логические схемы.— Вопросы радиоэлектроники. Сер. ЭВТ, 1971, вып. 6, с. 22—26. 10.. Автоматизированная система построения тестов функционального и диаг- ностического контроля логических схем/В. В. Балашов, Н. Ш. Муллина, Л. В. Никитина и др.— М.: ИТМ и ВТ, 1976. 11. Биргер А. Г., Бояршннов А. В., Гурвич Е. Т. и др. Автоматизированная си- стема контроля и диагностики цифровых ячеек. —Обмен опытом в радиопро- • мышленности, 1978, вып. 4-5, с. 40—46. 12. Чжен Г., Мэннинг Е., Метц Г. Диагностика отказов цифровых вычислитель- ных систем: Пер. с англ./Под ред. И. Б. Михайлова.— М.: Мир, 1972. 13. Putzolu G. R., Roth J. P. A heuristic algorithm for testing of asynchronou» circuits. — IEEE Trans., 1971, v. C-20, № 6, p. 639—647. 14. Breuer M. A. The effects of races, delays and delay faults on test generation. — IEEE Trans., 1974, v. C-23, № 10, p. 1078—1092. 15. Майорове. А., Немолочнов О. Ф., Усвятский А. Е. и др. Система автомати- зации синтеза контролирующих тестов для последовательностных схем.— 232 Тезисы докладов 3 Всесоюзного совещания по технической диагностике. Минск, 19/5.— М., 1975, с. 125—127. 16. Шукурян Ю. Г., Лазарян Э. А., Халатяи Р. С. и др. Комплекс программ ге- нерации тестов для типовых элементов замены.— Тезисы докладов 3 Все- союзного совещания по технической диагностике, Минск 1975.—М 1975 с. 149—150. '' ' 17. Вознесенский С. С., Воробьев В. М., Раздобреев А. X. и др. Автоматизация диагностирования дискретных устройств, построенных на больших интег- ральных схемах.— Тезисы докладов 7 Всесоюзного совещания по проблемам управления, Минск, 1977. — Минск, 1977, т. 2, с, 328—331. 18. Гробман Д. М., Сергеев Б. Г., Филинов Е. Н. Автоматизированная систем» контроля цифровых схем.— Тезисы докладов 7 Всесоюзного совещания па проблемам управления, Минск, 1977. — Минск, 1977 т 2 с 320—323 19. Chang Н. Y., Smith G. W., Waldorf R. W. LAMP: System description,—Bell Syst. Techn. J., 1974, v. 53, № 8, p. 1431—1449. 20. Чипулис В. П. О проверке схем при сочетании неисправностей.— Автома- тика и телемеханика, 1972, №9, с. 173—174. 21. Вейцман И. Н., Синельников В. Е., Флеров А. Б. Диагностирование неис- правностей в блоках вычислительных устройств.— Вопросы оалиоэлектпо- пики. Сер. ЭВТ, 1973, вып. 8, с. 46—59. v v v 22. Кузнецов С. С. Реализация алгоритма построения тестов для схем с памятью с использованием комбинационных моделей различной адекватности.—06- мен опытом в радиопромышленности, 1978, вып. 4-5, с. 92—97. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Автомат: абстрактный 50 асинхронный 52, 63 •— тактируемый 53 Мили 51 Мура 51 с ортогональными входами 54 синхронный 52 структурный 195 частичный 50 Адекватность моделирования 129 Активизация пути 176, 194 Алгоритм: дедуктивный 167 раскрытия структуры 116 формирования кодировочной схемы ячейки 118 Алфавит моделирования 131 Архив 11 Архивы данных 46, 100, 112 Базис: модели 132 элементный 132 Библиотека: временная 38, 40 программ 39 стандартных программ 31 элементов 171 Блок 104 Вектор: активности 191 логический 18, 31 . Время автоматное 49 Генерация: модели 133 случайных входных наборов 179 Глубина: поиска 175 реализации 30, 41 Датчик случайных чисел 179 Дешифрация результатов проверки 175 Диаграмма временная 62" Директивы 11, 36, 44 моделирования 172 Длина теста 174 D-алгоритм 182 0-куб неисправности 186 — элемента 184 Емкость комплекса 19, 29 234.- Загрузчик 36, 38 Задержка элемента 145 модельная 146 номинальная 130 Заказ 16, 36 Интервал: , входной 74 модельных задержек 159 Итерации: Зейделя 138 простые 136 «Кандидат в тесты» 177, 218 Каталог 38, 40 - оперативный 40 структур 112 Качество теста 174 , Класс неисправностей 131, 174 Компиляция 141 Комплекс 14, 24, 38 Константы системные 17, 29 Контроль выполнения операций 37 Корректность микропрограмм 76 Корреляция: временная 160 значений сигналов 160 Куб: ' логический 183 элемента вырожденный 183 Л-модуль 15, 28, 35, 38 Макрооперация 14, 29, 41 Масштаб времени 146 Метод: ' обратного прослеживания нспгг" ностей 169 структурного синтеза каноннчс. 70 Эйхельбергера 155 Микрокоманда 51, 58 Микрооперация 55, 58 Микропрограмма автомата 54 Микросхема 104, 108 Моделирование: асинхронное 145 i— троичное 159 двоичное 139 — в троичном алфавите 154 интерпретативное 141 — событийное 144 итеративное 136 компилятивное 141, 144 1B« логическое 129 многозначное 153 неисправностей 162 одиночное 140 параллельное 140 синхронное 145 событийное 142,166 троичное 155, 159 Модель: асинхронная итеративная 201 математическая 129 объекта диагностирования неявная 131 сигнала 131 структурная 130 функциональная 130 элемента 131 явная 130 Монитор 36, 38, 43 Модуль: базисный информационный (БИМ) 14, 29 вызывающий 30, 38 головной 16 подчиненный 30, 38, 41 М-модуль 15, 35, 38 Неадекватность троичного моделиро- вания 156 Независимость модулей 15 Неисправность 131 константная 131 кратная 131 неустойчивая 174 одиночная 131 • параметры 168 подозреваемая 175 устойчивая 174 ; Область памяти 137 «Обрыв обратных связей» 137 Операнд 17, 29 Оператор 16 Очередь будущих событий 149 Параметры: входные 21, 28 выходные 28 Паспорт заказа 39, 41 Переменная: внутренняя 79 входная 56 выходная 56 обобщенная 162 общая 106 собственная 17, 19 Перфолента управляющая 222 Подкомплекс 25 Подсистема СИНТЕЗ 46, 49 - СТРУКТУРА 46, 100 Подсхема; комбинационная входная 137 — выходная 137 сильносвязаныая 138 Последовательность установочная 163 Предложение 16 Преобразователь автомата логиче- ский 81 Проверка: исправности 174 корректности 181 устройства 175 Проектирование логическое 14, 48 Программа 14, 16 Процедура импликации 188 Псевдовход 195 Псевдовыход 195 Распределение памяти оперативно- динамическое 40, 44 Режим работы диалоговый 44, Связь информационная 14 Сеть логическая 130 Сигнал выходной длительный 67 • Система: ^ архивная 15, 40 диагностического матобеспечения аптоматизированная 205 построения проверяющих тестов 210 программирующая 13, 31, 36 управления директивная 47 Словарь диагностический 223 Состояние: • внутреннее 50, 79 входное 50 выходное 50 Состязания 129 Список: неисправностей 135 непроверенных неисправностей 221 Средства диагностирования 222 Стратегия случайного поиска 180 Структура общая 164 Схема итеративная комбинационная !95 Сходимость моделирования 132 Таблица: выходов 50, 74 — неисправностей 225 диагностическая 222 наборов неисправностей 225 неисправностей 223 переходов 50, 74 функций неисправностей 223 Такт моделирования 146 Тест: поиска неисправностей 174 проверяющий 129, 174 235 Точки особые 16_ Транслятор 32, 37 Узел 104 Уплотнение памяти 43 Уравнение обобщенное 163 Условие 54 — входное 68 Устойчивость состояний 52 Форматы данных 71, 109 функция: возбуждения 50, 71, 79^ выходов 71, 79 переходов 50 стандартная 31 Эквивалентность неисправностей 13в Элемент 104 Элементы базовые 104 Язык программирования базовый 13, 81 Ячейка 46, 104 ОГЛАВЛЕНИЕ Предисловие ........................ • Введение ......................... 8 Список литературы .................... 12 Глава первая. ПРОГРАММИРУЮЩАЯ СИСТЕМА ПРОЛОГ ДЛЯ ЭВМ | БЭСМ-6 ........................ 13 1.1. Язык программирования и особенности математического обеспечения системы логического проектирования . . . . 13 1.2. Описание версии языка ЛЯПАС-М ............ 16 1.2.1. Программа .................... 16 1 1.2.2. Символьный набор ............... 17 1.2.3. Операнды .................... 17 1.2.4. Элементарные операции ............. 19 1.2.5. Структура программ и макрооперации ...... 28 1.2.6. Методические указания для обеспечения совмести- мости ...................... 31 1.3 Принципы построения транслятора ........... 32 . .4. Состав и работа программирующей системы ПРОЛОГ 36 1.4.1. Трансляция Л-модулей .............. 37 1.4.2. Организация библиотеки программ и архивов данных 39 1.4.3. Организация счета и оперативно-динамическое рас- пределение памяти ................... 40 1.4.4. Организация обмена с ВЗУ ........... 43 1.4.5. Диалоговый режим работы ............ 44 Список литературы .................. 48 Глмачпврая. СИСТЕМА ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ ДИСК- РЕТНЫХ УСТРОЙСТВ ................ 46 2.1. Структура и организация управления системой логичес- кого проектирования ..... ............. 46 2.2. Подсистема СИНТЕЗ . . ............... 43 2.2.1. Математическая модель управляющего блока .... 49 2.2.2. Метод синтеза ..... .............. 69 2.2.3. Форматы данных подсистемы СИНТЕЗ ....... 71 2.2.4. Алгоритмы синтеза управляющих блоков . .... 73 2.3. Подсистема СТРУКТУРА . .............. 100 2.3.1. Структурная схема подсистемы СТРУКТУРА . . . 100 2.3.2. Способы описания структуры устройств. Язык СТРУК- ТУРА ......................... 103 2.3.3. Внутренний формат данных. ........... 109 2.3.4. Организация поиска и храненш структур в архи- вах данных .......... .......... 112 2.3.5. Алгоритмы обработки структур . . ....... 116 2.4. Пример проектирования реального устройства ..... 118 Список литературы ................ 128 237 Г.шва. третья. МОДЕЛИРОВАНИЕ ДИСКРЕТНЫХ УСТРОЙСТВ НА ЛОГИЧЕСКОМ УРОВНЕ ............... 129 3.1. Общие вопросы моделирования .. ........... 129 3.2. Описание структуры устройства . . . ........ 133 3.3. Анализ структуры и преобразование описания ..... 136 8.4. Двоичное моделирование исправного устройства без учета задержек ...........' ... .......... 139 3.4.1. Параллельное моделирование . . ......... 140 3.4.2. Метод компиляции . . .............. 141 3.4.3^ Событийное моделирование ............. 142 8.5. Двоичвое моделирование исправного устройства с учетом задержек .............,......•••• 145 3.5.1. Сквозное моделирование ...,.,...,,.. 147 3.5.2. Событийное компилятивное моделирование .... 148 3.5.^. Событийное интерпретативное моделирование. . . . 148 8.бЛ Методы многозначного моделирования . ......... 153 •' 3.6.1. Моделирование установочных последовательностей 153 3.6.2. Троичное мод|лировалие .............. 155 3.6.3. ^-троичное моделирорачи® • ........... 157 3.6.4. Асинхгонное троичное моделирование с нарастающей неопред"л-ннсстыо ................... 159 3.6.5. Пути дальнейшего повышения адекватности модели- рования ... ..................... 160 3.7. Методы моделирования неисправных устройств ..... 162 3.7.1. Параллельное компилятивное моделирование неис- правностей ....................... 162 3.7.2. Дедуктивный алгоритм . { ............ 167 3.8. Выбор метода моделирования .... .......... 170 3.9. Вопросы организации системы моделирования . ..... 171 Список литературы ................... 172 Глава четвертая. АВТОМАТИЗАЦИЯ ТЕСТОВОГО ДИАГНОСТИРО- ВАНИЯ ........................ 174 4.1. Основные понятия .................... 174 4.2. Методы построения тестов. .,............<• 176 4.2.1. Общая характеристика методов ........... 176 4.2.2. Алгоритмы случайного поиска . ......... 179 4.2.3. D-алгоритм построения тестов для комбинационных схем ......................... 182 4.2.4. Метод активизации путей для устройств с памятью 194 4.3. Проектирование автоматизированной системы диагности- ческого матобеспечения ................. 205 4.4. Система построения проверяющих тестов. ........ 210 4.4.1. Описание программ СППТ ... ........ 212 4.4.2. Входная и выходная документация ........ 220 4.4.3. Диагностические словари и поиск неисправностей в ЦЯ . . . . . .................... 223 4.4.4. Организация работы СППТ ............ 228 4.4.5. Результаты эксплуатации и перспективы развития СППТ ....... . . ............... 230 Список литературы . ................ 232 Предметный указатель .................. 234 Сергей Степанович Бадулин, Юрий Максимович Барнаулов, Вильям Алексеевич Бердышев, Александр Герцович Биргер, Игорь Геннадиевич Борисов, Анатолий Михайлович Грузных, Евсей Томович Гурвич, Герман Гаврилович Колгатин, Сергей Сергеевич Кузнецов, Ирина Павловна Либман, Вячеслав Ильич Мазнев АВТОМАТИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ ЦИФРОВЫХ УСТРОЙСТВ Под редакцией С. С. Бадулина Редактор Э. М. Горелик Художественный редактор Н. А. Игнатьев Художник В. В. Волков Технический редактор И. Л. Ткачеико Корректор О. И. Галанова ИБ № 14S (С. р.) Сдано в набор 15.09.80. Подписано в печать 20.05.81. Т-08382. Формат GOXSO'/ie. Бумага кн.-журнальная. Гарнитура литературная. Печать высокая. ^•"•Л: л^'0' о ^•-чзД- •я- 17'37- Усл. кр.-отт. 15.0. Тираж 25000 экз. Изд №19535. Зак.2112. Цена 1 р. 20 к. • k г Издательство '«Радио и связь», Москва, Главпочтамт, а/я 693 Московская типография № 4 Союзполиграфпрома при Государственном комитете OLOP по делам издательств, полиграфии и книжной торговли. 129041, Москва Ь. Переяславская ул., д. 46. В серии «ПРОЕКТИРОВАНИЕ РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ НА ИНТЕГРАЛЬНЫХ МИКРОСХЕМАХ» Вышли в свет книги: Основы проектирования микроэлектронной аппаратуры, под ред. Б. Ф. Вы- соцкого, 1977 г. Аналоговые и цифровые интегральные схемы, под ред. С. В. Якубовского, 1979 г. Аналого-цифровые преобразователи, под ред. Г. Д. Бахтиарова, 1980 г. Микропроцессорные БИС и микро-ЭВМ. Построение и применение, под ред. А. А. Васенкова,1980 г. Автоматизация проектирования цифровых устройств, под ред. С. С. Баду- лина, 1981 г. Выйдут в свет книги: Моделирование и оптимизация на ЭВМ радиоэлектронных устройств, под ред. 3. М. Бененсона, 1981 г. Автоматизированное проектирование устройств СВЧ, под ред. В. В. Ни" Кольского,1982 г. Компоновка и конструкции микроэлектронной аппаратуры, под ред. В. Ф. Высоцкого, В. Б. Пеетрякова, О. А. Пятлина, 1982 г. Радиопередающие устройства, под ред. О. А. Челнокова, 1982 г, Радиоприемные устройства, под ред. Л. Г. Барулина, 1983 г. Вторичные источники питания, под ред. Ю. И. Конева, 1983 г, Пьезоэлектрические устройства фильтрации и обработки сигналов, под ред. Б. Ф. Высоцкого, В. В. Дмитриева, 1984 г. Цифровые фильтры, под ред. Б. Ф. Высоцкого, 1984 г. Автоматизация процессов конструкторского проектирования и технической подготовки производства микроэлектронной аппаратуры, под ред. Ю. X. Вермишева, 1985 г. Радиокомпоненты, под ред. В. Б. Лярского, 1985 г. тирования. Параметрами этой директивы могут быть номера новых (ранее не использованных) архивов, в которые по этой директиве бу- дет внесена служебная информация. Директивы ВВОД и ВЫВОД осуществляют соответственно ввод и вывод исходных данных и ре- зультатов. Директива КАТАЛОГ позволяет вывести на экран дисплея или распечатать содержимое заданного архива системы логического проектирования. Выдаваемая информация содержит имена и номера структур, записанных в данный архив. Директива КОНЕЦ прекраща- ет работу системы. Вторая группа объединяет такие директивы, как ЗАПИСАТЬ, СЧИТАТЬ, ЗАМЕНИТЬ, ВОССТАНОВИТЬ и др., которые позво- ляют записывать в архив новые структуры, заменять структуры, на- ходящиеся в архивах, восстанавливать содержимое архивов с перфо- карт и т. д. К третьей группе относятся, например, директивы ТРАНСЛИРО- ВАТЬ, СИНТЕЗИРОВАТЬ, РАСКРЫТЬ, ФОРМИРОВАТЬ, МОДЕ. ЛИРОВАТЬ. Директива ТРАНСЛИРОВАТЬ обеспечивает преобра- зование текста на языке СТРУКТУРА во внутреннее представление. Директива СИНТЕЗИРОВАТЬ позволяет по описанию алгоритма рабо- ты управляющего блока построить схему автомата в базовых элементах во внутреннем представлении. По директиве РАСКРЫТЬ происхо- дит преобразование структуры устройства, состоящего из сложных компонент, в структуру из базовых элементов. Директива ФОРМИ- РОВАТЬ переводит внутреннее представление ячейки в базовых эле- ментах в кодировочную схему, которая является результатом работы системы логического проектирования и служит исходным заданием для этапа технического конструирования. Как уже указывалось, системой проектирования управляет ин- терпретатор директив, который по мере анализа очередной директивы обращается к реализующим ее макрооперациям. При этом выполнение большинства директив требует вызова одной из подсистем системы логического проектирования. Информационную связь между подси- стемами достаточно легко организовать, используя порожденные ком- плексы (п. 1.4.3). В этом случае перед обращением к очередной под- системе не требуется определять параметры комплексов, в которых будут находиться результаты ее работы. Все эти параметры вычисляют- ся по мере выполнения очередного этапа внутри подсистемы. Каждая из подсистем проектирования, в свою очередь, состоит из ряда модулей, связь между которыми устанавливается по мере их реализации. Голов- ным модулем всей системы является модуль ЛОГИКА, который и осу- ществляет функции интерпретатора. Все модули системы логического проектирования, предварительно оттранслированные, записаны в библиотеке ПС ПРОЛОГ (п. 1.4.4). ,*| Для запуска системы на счет необходимо в паспорте заказа (п. 1.4.2) г указать имя задачи ЛОГИКА, а в качестве параметров одной из биб- лиотек — параметры библиотеки, содержащей все модули системы логического проектирования. Необходимо также указать параметры системной библиотеки ПС ПРОЛОГ, модули которой также потребуют- ся для Функционирования системы. Работа системы логического проектирования начинается с 'того, что ПС ПРОЛОГ вызывает модуль ЛОГИКА в ОП и передает ему уп- равление. По мере реализации директив этот модуль обращается к со- ответствующим макрооперациям. ПС ПРОЛОГ выполняет эти макро- операции с помощью соответствующих модулей. Так, при выполнении директив проектирования в ОП первоначально размещаются головныа модули соответствующих подсистем проектирования, которые и уп- равляют выполнением заданного директивой этапа. Благодаря методам оперативно-динамического распределения па- мяти (п. 1.4.3) при выполнении некоторой повторяющейся последо- вательности директив все необходимые модули располагаются в ОП или при исчерпании ее ресурсов в оперативной библиотеке на МБ. Это придает системе необходимую гибкость и возможность быстро адаптироваться к выбранной стратегии. 2.2. ПОДСИСТЕМА СИНТЕЗ 2.2.1. Математическая модель управляющего блока Поведение любого дискретного устройства определяется измене- нием во времени некоторых физических, величин на его входе, выхода и внутри самого устройства. Для рассматриваемых устройств такими величинами являются потенциалы на входных и выходных полюсах, а также в некоторых внутренних точках схемы. В дальнейшем будем называть их входными, выходными и внутренними переменными. Основной особенностью функционирования дискретных устройств является то, что на оси времени могут быть выделены интервалы, на которых все эти переменные сохраняют постоянное значение и кото- рые называются тактами работы дискретного устройства. Значения переменных в эти интервалы и определяют алгоритм работы проекти- руемого устройства. Поставив в соответствие последовательности тактов рял натураль- ных чисел, получим дискретное автоматное время, с которым мы в дальнейшем и будем иметь дело. Таким образом, в каждый момент ав- томатного времени (такт) входные, выходные и внутренние перемен- ные имеют вполне определенные значения. Набор входных (выходных) переменных в некоторый момент автоматного времени будем называть входным (выходным) состоянием устройства или буквой его входного (выходного) алфавита. Часто, особенно когда модель привязывается к конкретному уст- ройству, вместо термина «буква входного (выходного) алфавита» используется термин «входной (выходной) сигнал». Совокупность всех возможных для данного устройства входных (выходных) состояний (букв) составляет входной (выходной) алфавит устройства. Аналогич- но, набор внутренних переменных в некоторый момент автоматного времени называется внутренним состоянием устройства в этот момент времени, а все различные внутренние состояния составляют множест- 49 Ч(у,,...,у ) во внутренних состояний уст- ————'"' ройства или его внутренний алфавит. При использовании рис. 2.2 термина «внутреннее состоя- ние» часто слово «внутреннее» опускают. Таким образом, для определения моделей управляющих блоков будем использовать такие параметры, как автоматное время, входные, выходные и внутренние состояния, входные и выходные переменные, которые являются абстрактными отражениями реальных свойств ап- паратуры. При описании моделей будем двигаться сверху вниз, т. е. от моделей более высокого уровня к моделям более низкого (чем ниже уровень модели, тем больше реальных свойств она отражает). Наиболее общей моделью управляющего блока является абстракт- ный автомат, представляющий собой совокупность шести объектов: — множества входных состояний (входной алфавит) Х = [х^, х^, ...}', — множества выходных состояний (выходной алфавит) Y == {г/ц ^, -}; — множества (внутренних) состояний (алфавит внутренних со- стояний) S = [s^, $a, ... }; — функции переходов 6, реализующей отображение Х Х S в 5; — функции выходов л, реализующей отображение Х Х S в У; — начального состояния автомата s^ (: 5. Если функции бил заданы на всем множестве Х Х S, то авто- мат называется полностью определенным, в противном случае — ча- стичным. Абстрактный автомат можно представить в виде «черного ящика» с одним входом и одним выходом (рис. 2.2). В каждый момент автомат- ного времени t на автомат, находящийся в некотором состоянии s (t), поступает буква входного алфавита х (t). В этот же момент времени на выходе автомата наблюдается буква выходного алфавита у (t). В сле- дующий момент времени автомат перейдет в новое состояние s {t + 1), определяемое функцией переходов. Тогда поведение произвольного автомата можно качественно описать уравнениями s (t + 1) = б [s (0, х (t)}, у (0 = л [s (0, х (01. (2.1) Для задания конкретного автомата необходимо иметь формальные средства, т. е. язык описания алгоритма его работы. Наиболее прос- тым, ставшим уже классическим описанием являются таблицы пере- ходов (табл. 2.1) и выходов (табл. 2.2). Строкам таблиц соответствуют внутренние состояния, а столбцам — буквы входного алфавита. На пересечении строк и столбцов таблицы переходов расположены соот- ветствующие значения функции переходов, а таблицы выходов — значения функции выходов. Табл. 2,1 и 2.2 описывают частичный авто- мат, о чем говорят прочерки. Например, для (Si, x^) функции перехо- дов и выходов не определены. По этим таблицам можно найти реакцию автомата на любую последовательность букв входного алфавита (вход- ное слово). Так, если на автомат, находящийся в начальном состоянии s,, в моменты времени /i, t^, ty, t^, ^ поступают буквы х^, х^, Ху, х-^, л"», 50 Таблица 2.1 Таблица 2.2 t/i I 1/1 У» S2 I t/2 I —— I • Sg 1 Уз\ Уз S4 I 1/2 Vl\ УЗ 1 «I y-i s» I V\ л *1 ^'i <:. л. S| Ч S4 S.; ь; 54 - '3 5б ^ '4 S4 -^G s. s& ss, — г S.2 •'S s^ — 5 . 'ь Рис. 2.3 то последовательность его состояний будет Si, Sg, Se, Sa, Sj, s,„ а выход- ными буквами г/i, г/д, уд, у^, у^. Отличие частичного автомата от полностью определенного состо- ит в том, что последний реагирует на все множество входных слов, а первый — только на часть этого множества. Ту часть множества входных слов, на которой поведение автомата не определено, будем называть множеством запрещенных слов. Для реальной аппаратуры этому г^ножеству принадлежат такие входные последовательности, которые не должны появляться при ее функционировании. Исходя из сказанного очевидно, то там, где в таблице переходов стоит прочерк, в таблице выходов также должен стоять прочерк. Кроме того, прочер- ки в таблице выходов могут стоять также и там, где в таблице пере- ходов имеется определенное состояние. В автомате, описываемому табл. 2.1 и 2.2, такой факт имеет место для состояния Sg и входной бук- вы Х4. На практике это означает, что если на'автомат, находящийся в состоянии Sg, подана буква х^, на выходе может появиться любая буква выходного алфавита. Очень удобным средством изображения моделей автоматов являют- ся направленные графы. Каждая вершина графа отождествляется с некоторым состоянием автомата, а дуги — с парами букв входного и выходного алфавитов, состояния автомата записывают внутри круж- ков, соответствующих вершинам графа. Входы указывают над соот- ветствующими дугами, за ними в скобках следуют буквы выходного алфавита. Пример графа автомата, соответствующего табл. 2.1 и 2.2, представлен на рис. 2.3. Перейдем теперь к классификации автоматов. Прежде всего, авто- маты различают по виду функции выходов. Автомат, описываемый уравнениями (2.1), называется автоматом Мили. В том случае, когда функция выхода не зависит от входного сигнала, т. е. s (t + 1) = б Is (t), х (Q1, у (0 = Х [s (Q, (2.2) модель называется автоматом Мура. 51 Рис. 2.4 По характеру работы автоматы делятсй на син- хронные и асинхронные [2]. Введем определение устойчивого состояния. Состояние s/ называется устойчивым, если из соотношения б (s;, х^) == s, при любых s; и Xf,, для которых оно справед- ливо, следует соотношение б (s/, х^) = Sj. На графе автомата это отражено следующим образом: Таблица 2.3 Таблица 2.4 каждой дуге, входящей в вершину, соответствует петля устойчивости, отмеченная тем же входным сигналом (рис. 2.4). Аналогично определение и устойчивого выходно- го сигнала. Выходной сигнал у; называется устойчивым в состоянии s/, если из соотношений К (s;, х^) == yi и б (s;, л-д) == s/ следует со- отношение К (Sj, Xh) == yi при всех s;, x^, для которых справедливы первые два равенства. Например, для автомата, описываемого гра- фом на рис. 2.3, выходной сигнал г/а в состоянии 4 устойчив. к X s "k 5 "h S; ^ Si Уе s} s; S} Уе Асинхронным будем называть авто- мат, у которого все состояния и. вы- ходные сигналы устойчивы (нормаль- ные таблицы). В таблицах переходов (табл. 2.3) это соответствует тому, что любой переход из состояния s; в со- стояние S] дублируется переходом из состояния SJ в состояние s,. Аналогич- ный факт имеет место и для выходных сигналов (табл. 2.4). Автомат, не яв- ляющийся асинхронным, называется синхронным. При проектировании цифровой аппаратуры в настоящее время ши- роко используют системы потенциальных элементов и тактирующие сигналы. При этом в зависимости от выбранных элементов памяти ис- пользуют модели как синхронных, так и асинхронных автоматов. Особенности функционирования и синтеза асинхронных автоматов в таких системах позволяют выделить их в весьма важный подкласс асинхронных тактируемых автоматов. На функционирование асинхронных автоматов наложим следующие ограничения: — входной алфавит Х разбивается на два подмножества Т аб л и ца 2.5 g X X, "1 "3 x\ ^ *з ^ 1 2 4 1 1 1 1 1 2 2 — 4 2 2 2 2 3 0 — 1 3 3 n 3 4 3 4 4 4 4 4 4 X'^[x{,X2,...,x'i} и X"={x'{,x,,..„x'k}. При подаче на автомат какой-либо бук- вы x'i существует хотя бы один переход его в новое состояние. Такие буквы вход- ного алфавита будем называть основны- ми. Любая буква х", (/== 1, 2, ..., k) не вызывает переходов автомата, и на выхо- де появляется пустой сигнал (табл. 2.5). Такие буквы можно назвать безразлич- ными; 52 Дд'———•- S(s,.^. ..,s,s —^fff—^yi—"Hi, tf tf ts tli tff tg Рис. 2.5 Рис. 2.6 — запрещается подача на вход автомата последовательностей, в ко- торых любые две рядом расположенные буквы являются различными буквами множества X'. Все буквы множества X" по своему действию эквивалентны, поэтому при их написании будем опускать индекс. Тогда допустимая входная последовательность имеет, например, вид -V^... Х'[^ Х Xf^ Х Х{^ Х ...X Xi^ Х X/ Х Х/^Х{ Х ... Здесь разрешается повторение одинаковых букв неограниченное чис- ло раз. Асинхронный автомат, удовлетворяющий обоим ограничениям, бу- дем называть асинхронным тактируемым. Отметим, что обычно при задании алгоритма его работы таблицами переходов и выходов столб- цы, соответствующие буквам, входящим в множество X", опускаются. В реальных устройствах тактирующие сигналы позволяют органи- зовать совместную работу составляющих их блоков в едином времени. Поэтому можно сказать, что тактирующие сигналы вводят в устройст- во автоматное время. Управляющие блоки реагируют на входные сиг- налы только при наличии тактирующих сигналов, т. е. в интервалы времени (f-i, t^), (<э, tn), (/.„ Q, ... (рис. 2.5). В эти интервалы управляю- щие блоки изменяют свои внутренние состояния и выдают выходные сигналы. Если считать, что входное состояние автомата определяется входными и тактирующим сигналами, то входные состояния в интер- валы (Л, t^), (ty, t^}, (/a, ^)> ••• можно отнести к множеству X', а в ин- тервалы (^, tg)' (t.^, t;), ... — к множеству X". Так как в интервалы, задающие множество X", состояние блоков не изменяется и с них не снимаются выходные сигналы, то мы получаем модель асинхронного тактируемого автомата. Мы рассмотрели абстрактный автомат, который изображался в виде «черного ящика» с одним входом и одним выходом (рис. 2.2). Более полно реальные характеристики дискретных устройств ото- бражаются моделью абстрактного автомата со структурными вход- ным и выходным сигналами. Такой автомат также представляет со- бой «черный ящик», но с га входами х^, Ху,, ..., л-„ и k выходами г/i, г/г, ..., Vh (РИС. 2.6). При этом отличие от абстрактного автомата на рис. 2.2 заключается в том, что в качестве букв входного и выходного алфавитов используются двоичные наборы значений входов (х^Ху,... Хп) и выходов (t/i;/2 ••• : : =<знак логической операции >]<знак оператора перехода>Кразделитель>-|-<вспомогательный символ> <знак логической операции >::==/\ IV «<знак оператора перехода >::=;> (разделитель) : : == :|;|.|)|(| — | —|, .— — символ пробела 53 Список литературы 1. Баранов С.1И. Синтез микропрограммных автоматов.—Л.: Энергия, 1979. 2. Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов.— М.: Энергия, 1978. 3. Глушков В. М. О применении абстрактной теории автоматов для минимиза- ции микропрограмм.— Изв. АН СССР. Техн. кибернетика, 1964, № 1. 4. Глушков В. М. Синтез цифровых автоматов.— М.: Физматгиз, 1962. б. Мищенко А. Т. Формализация синтеза автоматов с учетом характеристик сигналов и элементов; Канд. дис. ИК АН УССР. — Киев, 1970. 6. Глушков В. М., Капитонова Ю. В., Летичевский А. А. Автоматизация проектирования вычислительных машин.—Киев: Наукова думка, 1975. 7. Закревский А. Д. Алгоритмы синтеза дискретных автоматов.— М.: Наука, 1971. 8. Ландау И. Я. Применение ЦВМ для проектирования ЦВМ.—M.! Энергия, 1974. 9. Проектирование цифровых вычислительных машин/Под ред. С.А. Майорова. — М.: Высшая школа, 1972. 10. Майоров С. А., Новиков Г. И. Принципы организации цифровых машин.— Л.: Машиностроение, 1974. 11. Синтез асинхронных автоматов на ЭВМ/Под ред. А. Д. Закревского.—Минск: Наука и техника, 197В. 12. Гаврилов М. А., Девятков В. В., Пупырев Е. И. Логическое проектирование дискретных автоматов.'—М.: Наука, 1977. 13. Захаров В. Н., Поспелов Д. А., Хозацкий В. Е. Системы управления.—M.I Энергия, 1977. 14. Яблонский С. В. Функциональные построения в fe-значной логике.— Труды математического института им. В. А. Стеклова, 1958, т. 51, с. 5—142. 15. Мищенко А. Т. О формальном синтезе объединенного автомата. — Кибернет- тика, 1969, № 4. Глава третья МОДЕЛИРОВАНИЕ ДИСКРЕТНЫХ УСТРОЙСТВ НА ЛОГИЧЕСКОМ УРОВНЕ 3.1. ОБЩИЕ ВОПРОСЫ МОДЕЛИРОВАНИЯ При изготовлении и эксплуатации цифровых ячеек требуется имет» средства проверки правильности их функционирования Одним из та- ких средств являются проверяющие тесты. При построении н анало» зе тестов широкое применение находит моделирование на логическом уровне. Логическое моделирование заключается в построении математи- ческой модели исследуемого устройства —• системы соотношений, опи- сывающей поведение этого устройства с заданной точностью, и посл^ дующем анализе поведения этой модели по ее реакции на входные воз- действия. Далее для краткости вместо терминов «логическое модели" рова.ние» и «математическая модель» будем употреблять термины «мо- делирование» и «модель» соответственно. С помощью моделирования в системе автоматизированного проек- тирования дискретных устройств (ДУ) решаются следующие задачи: — проверка правильности логического функционирования ДУ; — проверка временных характеристик ДУ; — проверка функционирования цепей установки ДУ в начальное состояние; — анализ состязаний и рисков сбоя; — определение полноты тестов; — определение диагностических свойств тестов. Существует много различных методов и алгоритмов моделирова-, ния. Рассмотрим некоторые из них, представляющие наибольший инте- рес. При этом особое внимание будем уделять программной реализа- ции и сравнительной эффективности алгоритмов моделирования. Основны.-.iii характеристиками алгоритмов моделирования явля- ются адекватное гь, быстродействие и объем памяти, необходимый при реализации. Под адекватностью понимается степень соответствия ре- зультатов моделирования истинному поведению исследуемого ДУ. Для комбинационных ДУ алгоритмы моделирования гарантируют полную адекватность с установившя-лися значениями сигналов. По- ведение последовательностных ДУ в общем случае неоднозначно из-за ^ неопределенности начальных состоянии и состязаний между сигнала- ми, что усложняет задачу моделирования таких ДУ. Как будет пока- зано далее, неоднозначность учшывается в разной с'.епени различ- ными методами моделирования Ещг труднее а.^кватио моделировать переходные процессы, однако для большинства пракгцчески важных 5 аак. 2112 129 Язык описания входных воздействий. Он, как и язык описания схемы, дол- жен быть компактным и удобным В простейшем случае входная последователь- ность задается явным перечислением значений на вкодах схемы для каждого набора поочередно Часто более удобен другой вариант, где для каждого набора указываются номера входных контактов, на которых произошла смена сигнала. Чрезвычайно полезно обеспечить возможность компактного описания периоди- чески повторяющихся входных сигналов. Директивы моделирования. Они служат для управления процессом модели- рования, позволяя задавать алгоритм моделирования, начальные условия, фор- маты вывода, параметры моделирования и т. д. Развитый язык директив значи- тельно увеличивает ценность системы моделирования как инструмента разработ- чика аппаратуры. Например, директивы используются: — для задания начального состояния схемы; — для задания максимального числа итераций (тактов); — для введения «нестандартных» неисправностей; — для сравнения результатов моделирования с ожидаемыми результатами и выдачи сообщений о возможных расхождениях. Режим диалога. Он позволяет полно использовать возможности моделиро- вания, представляя возможность наблюдать на экране дисплея за ходом модели- рования и вмешиваться в процесс моделирования, корректируя неадекватности, вызванные несовершенством известных методов. Кроме того, при диалоговом ре- жиме можно с помощью директив изменять ход моделирования в зависимости от полученных результатов. Вопросы общения с системой, организации базы данных, связи систем моде- лирования и построения тестов с системами конструкторского проектирования подробно рассмотрены в [33]. Список литературы 1. Основы технической диагностики/В. В. Карибский, П. П. Пархоменко, Е. С. Согомонян, В. Ф. Халчев; Под ред. П. П. Пархоменко.—М.: Энергия, 1976. 2. Миллер Р. Теория переключательных схем. В. 2-х т.: Пер с англ. —М.: Наука, 1970. 3. Биргер А. Г., Бояршииов А. В., Гурвич Е. Т. и др. Автоматизированная сис- тема контроля и диагностики цифровых ячеек.— Обмен опытом в радиопро- мышленности, 1978, вып. 4-5, с. 40—46. 4. Гольдман Р. С., Чипулис В. П. Техническая диагностика цифровых уст- ройств.— М.: Энергия, 1976. 5. Теория и методы автоматизации проектирования вычислительных систем: Пер. с англ./Под ред. М. Брейера; Пер. под ред. Л. Д. Райкова.— М.: Мир, 1977. 6. Putzolu G. R., Roth J. P. A heuristic algorithm for testing of asynchronous circuits.— IEEE Trans., 1971, v. C-20, №6, p. 639—647. 7. Гетманский И. М. Ускорение моделирования асинхронных логических схем. — Труды ИНЭУМ, 1972, вып. 23 (Автоматизация проектирования и контро- ля УВМ), с. 34—36. 8. McCluskey Е., Clegg E. W. Fault equivalence in combinational logic networks. — IEEE Trans.. 1971, v. C-20, № 11, p. 1286—1293. 9. Ноткин Р. Г. Об одной задаче, возникающей при построении контролирую- щих тестов для логических сетей.— Автоматика и телемеханика, 1975, № 6, с. 126—131. 10. Биргер А. Г. Использование отношения подобия между неисправностями при построении проверяющих тестов цифровых устройств.— Автоматика и телемеханика, 1977, № 9, с. 150—157. 11. Чжен Г., Мэннинг Е., Метц Г. Диагностика отказов цифровых вычисли- юльных систем: Пер. с англ./Под ред. И. Б. Михайлова.— М.: Мир, 1972. 12. Гурвич Е. И., Куликовская Т. П. Метод анализа тестов цифровых устройств с помощью логического моделирования.— В кн.: Применение ВМ для проек- тирования цифровых устройств. — М.: Сов. радио, 1969, с. 81—98. 172 13. Голубева Г, А.. Гробман Д. М., Киселева ;А, Н. и др. Автоматизация програм- много контроля ЦВМ.— В кн.: Диагностика неисправностей вычислитель- ных машин.— М.: Наука, 1965, с. 60—61. 14. Hardie F. H.| Suhocki R. J. Design and use of fault simulation for Saturn com- puter design.— IEEE Trans., 1967. v. EC-16, № 4, p. 412—429. 15. Case P. W., Graff H. M., Griffith L. E. et al. Solid logic design automation.— — IBMJ. Res. Dev,, 1964, v. 8, №2. p. 127—140. 16. Ulrich С. Exclusive simulation of activity in digita' networks.—Comm, ACM, 1969, v. 12, №2, р. 102—110. 17. Майорове. А., Немолочнов О. Ф., Колесник А. П, Асинхронное событийное моделирование логических схем цифровых устройств.—Управляющие систе- мы и машины, 1973, № 2, с. 126—131. 18. Eichelberger E. В. Hazard detection in combinational and sequential swit- ching circuits.— IBM J, Res. Dev., 1965, v. 9, № 2, p. 90—99. 19. Биргер А. Г. Применение моделирования в автоматизированной системе построения тестов.— Обмеч опытом в радиопромышленности 1978, вып 4-5, с. 97—101. 20. Chappell S. G., Elmendorf С. H., Schmidt L. D. LAMP: Logic-circuit simu- lators.— Bell Syst. Techn. J., 1974, v. 53. № 8, p. 1451—1476. 21- Chang H. Y., Smith G. W., Waldorf R. B. LAMP: System description.— Bell Syst. Techn. J., 1974, v. 53, №8, p. 1431—1449. 22 Бродский М. А. Моделирование логических схем с учетом задержек эле- ментов.— Труды ИНЭУМ, 1975. вып 49 (Контроль цифровых схем), с. 13— —20. 23. Синельников В. Е. Алгоритм анализа состязаний в дискретных последова- тельностных устройствах.— Известия вузов СССР. Электромеханика, 1975, № 11, с. 1234—1241. 24. Poage J.F. Derivation ot optimum tests to detect faults in combinational circuits.—In: Mathematical theory of automata.—"New ' York; Polytechnic Press, 1963, p. 483—528. 25. Пархоменко П. П. Диагноз технического состояния дискретных устройств методом выделения подозреваемых неисправностей. Комбинационные уст- ройства. Устойчивые неисправности. — Автоматика и телемеханика. 1971, № 6, с. 126—137. 26. Иголинский В. Г. Аналитические методы построения контрольных таблиц неисправностей для реальных логических сетей.— Техническая кибернети- ка, 1969, № 6, с. 17—25. 27. Ермилов В. А. Метод отбора существенных неисправностей для диагностики цифровых схем. Общие выражения для неисправностей, возможных при эксперименте. — Автоматика и телемеханика, 1971, № 1, G. 97—106. 28. Armstrong D. B. A deductive method for simulation faults in logic circuit». — IEEE Trans., 1972, v. C-21, № 5, p. 464—471. 29. Chappell S. G., Chang H. Y., Elmendorf C. H., Schmidt L. D. A comparison of parallel and deductive simulation techniques.— IEEE Trans., 1974, v G- 23, № 11, p. 1132—1139. 30 Nakamura A., Nose Ju., Yamakava S. High speed generation ot fault-location data for logic circuits.— Proc. IF IP Congress, Stockholm, 1974 v. 1, p 112— 117. 31. Убар Р. Р. Анализ диагностических тестов для комбинационных логичес- ких схем методом обратного прослеживания неисправностей.-- Автоматика и телемеханика, 1977, № 8, с. 168—176. 32. Akers S. B. On a theory of Boolean functions. — SIAM J., 1959, v. 7, № 4, p. 487—498. 33. Автоматизация проектирования вычислительных систем. Языки, моделиро- вание и базы данных: Пер. с англ./Под ред. М. Брейера. Пер. под ред. Л. Д. Райкова, — М.: Мир 1979.