книги из ГПНТБ / Баранов, С. И. Синтез микропрограммных автоматов

С. И. Баранов

Синтез

микропрограммных

автоматов

і

S „Энергия“

Ленинградское отделение 1974

г.' •

Баранов С. И.

Б 24 Синтез микропрограммных автоматов. Л., «Энергия», 1974.

216 с. с пл.

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

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

Рецензент В. Б. Смолов

© Издательство «Энергия», 1974

С А М А Р И Й И О С И Ф О В И Ч БА РА Н О В

СИНТЕЗ М И К Р О П Р О Г Р А М М Н Ы Х АВТ О М АТ О В

Редактор Ю. В. Долгополова. Художественный редактор Г. А. Гудков. Технический редактор О. С. Житникова. Корректор М. Э. Орешенкова

Сдано в набор 14/IX 1973 г. Подписано к печати 15/11 1974 г. М-22213. Формат

Ленинградское отделение издательства «Энергия». 1920-11, Ленинград, Марсово поле. 1

Ленинградская типография № 4 Союзполпграфпрома при Государственном ко­ митете Совета Министров СССР по делам издательств, полиграфии и книж­ ной торговли. 196126, Ленинград, Ф-126, Социалистическая у.п., Ы.

-J

ПРЕДИСЛОВИЕ

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

В настоящей работе излагаются методы синтеза, позволяющие проектировать достаточно сложные микропрограммные автоматы с числом входных и выходных каналов и внутренних состояний по­ рядка нескольких сотен. От читателя не требуется предварительного знакомства с теорией автоматов: все необходимые определения и по­ нятия кратко изложены в первых трех главах. Чтобы облегчить ис­ пользование рассмотренной методики синтеза в инженерной практике, в работе приводится достаточно большое количество примеров. Нередко при выборе между наглядностью и строгостью изложения автор заставлял себя отдавать предпочтение наглядности. Сравни­ тельно небольшой объем книги, к сожалению, не позволил рассмотреть ряд вопросов теории цифровых автоматов и логических схем. Неудов­ летворенному читателю следует обратиться к широко известным мо­ нографиям М. А. Гаврилова, В. М. Глушкова, А. Д. Закревского, В. Г. Лазарева, А. Н. Мелихова, Д. А. Поспелова, Э. А. Якубайтиса и др. [5, 7, 9, 11, 16, 21, 231.

Эта книга представляет собой расширенный конспект лекций по теории цифровых автоматов, которые в течение ряда лет читались сту­

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

Отзывы и пожелания по книге просьба направлять по адресу: 192041, Ленинград, Марсово поле, д. 1, Ленинградское отделение из­ дательства «Энергия».

Автор

4

Глава первая

АБСТРАКТНЫЙ АВТОМАТ

1-1. Определение абстрактного автомата. Автоматы Мили и Мура

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

иW. В дальнейшем будут рассматриваться только конечные автоматы

итермин «конечный» почти всегда будет опускаться. Автомат назы­ вается полностью определенным, если D6 = Dx — А х Z. Иными словами, у полностью определенного автомата области определения функций б и К совпадают со множеством Л X Z — множеством все­ возможных пар вида (ат, zf). У частичного автомата функции б или X определены не для всех пар (ат, zf) £ Л X Z.

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

Абстрактный автомат (рис. 1-1) имеет один входной и один выход­ ной канал. В каждый момент ^ = 0 , 1, 2, . . . дискретного времени автомат находится в определенном состоянии а (t) из множества Л

1 Всякий конечный набор попарно различных символов можно рассматри­ вать как некоторый алфавит, буквы которого — указанные символы. Конечную' упорядоченную последовательность букв назовем словом в данном алфавите.

2 До главы 2 под термином «автомат» понимается абстрактный автомат.

5

состояний автомата, причем в начальный момент t = 0 он всегда на­ ходится в начальном состоянии а (0) = аг. В момент *, будучи в со­ стоянии а (*), автомат способен воспринять на входном канале сиг­

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

Мили и Мура. Закон функционирования автомата Мили задается уравнениями

1-2. Методы задания автоматов

Чтобы задать конечный автомат S, необходимо описать все эле­ менты множества S = \А, Z, W, б, К, оД, т. е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выхо­ дов. Среди множества состояний необходимо выделить состояние аѵ, в котором автомат находится в момент * = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный, графический и матричный.

Описание работы автомата Мили таблицами переходов и выходов иллюстрируется табл. 1-1 и 1-2. Строки этих таблиц соответствуют

Таблица 1-1 Таблица 1-2

6