Синтез комбинационных и конечных автоматов (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. П. ОГАРЁВА»

ФАКУЛЬТЕТ ЭЛЕКТРОННОЙ ТЕХНИКИ

Кафедра «АВТОМАТИКА»

М. В. ИЛЬИН

с. с. КАПИТОНОВ

Б. И. ПЕТРОВ

Синтез комбинационных

и конечных автоматов

Лабораторный практикум

и контрольные работы

по курсу "Электронные цепи и микросхемотехника"

САРАНСК

2012

УДК 62-52(076)

ББК Б534

Рецензент:

, доктор технических наук, профессор кафедры системотехники Саратовского государственного технического университета им.

Авторы-составители: заведующий кафедрой «Автоматика», канд. техн. наук, , доцент кафедры «Автоматика», канд. техн. наук, , преподаватель кафедры «Автоматика» , доцент кафедры «Автоматика» .

Б534

Синтез комбинационных и конечных автоматов: лабораторный практикум / Н. Н. Беспалов, М. В. Ильин, , . — Саранск : Ковылк. тип., 2012. — 39 с.

ISBN ___________

Содержатся теоретические сведения и методические указания к выполнению комплекса лабораторных работ по курсу «Электронные цепи и микросхемотехника», связанных с синтезом комбинационных и конечных автоматов. Предназначено для студентов направлений подготовки «Электроника и наноэлектроника», «Инфокоммуникационные технологии и системы связи», «Электроэнергетика и электротехника» и «Приборостроение». Однако данным пособием смогут пользоваться студенты и других специальностей связанных с электротехникой, электроникой и радиотехникой.

Печатается по решению научно-методического совета Мордовского государственного университета им. ёва.

УДК 621.373.132.049.77(076)

ББК Б534

ISBN ___________

© , , 2012

Посвящается памяти старейшего преподавателя кафедры «Автоматика», нашего друга и учителя Бориса Ивановича Петрова.

ПРЕДИСЛОВИЕ

Настоящий лабораторный практикум содержит описания третьей и четвёртой из комплекса лабораторных работ, которые проводятся при изучении студентами дневной и заочной форм обучения импульсных и цифровых цепей в рамках курса «Электронные цепи и микросхемотехника».

Основной целью данной работы является изучение комбинационных и конечных автоматов.

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

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

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

Отчёт по работе должен содержать изучаемые схемы, выполненное предварительное расчетное задание и полученные результаты. Отчет должен быть оформлен аккуратно на листах стандартного размера А4, а также представлен в электронном виде.

Порядок прохождения данной лабораторной работы следующий.

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

2. Перед очередным занятием каждый студент сдает коллоквиум по текущей работе. Если студент не готов к работе или не выполнил предварительное расчетное задание, то он к работе не допускается.

3. На следующем занятии после выполнения работы, студент должен предъявить оформленный отчёт по выполненной работе и защитить работу.

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

Все лабораторные работы по изучаемому курсу рассчитаны на четырехчасовое занятие в аудитории и четырехчасовую домашнюю подготовку.

1 КОМБИНАЦИОННЫЕ АВТОМАТЫ

1. 1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

,

где некоторый оператор преобразования входных переменных X (элементы множества) в выходные Y (элементы множества ).

Задача логического проектирования (синтеза) КА, реализующего требуемый оператор преобразования входных переменных в выходные, состоит в определении оптимальной структуры автомата для заданного перечня логических элементов (заданной элементной базы). Оптимальной будем считать структуру автомата, содержащую минимальное число данных элементов.

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

Задание оператора независимо от его формы (наиболее распространенной является табличная форма) заключается в определении перечня входных и выходных переменных автомата и установлении связей между ними.

В процессе структурного синтеза определяется структурная схема автомата. Научной основой этого этапа является аппарат алгебры логики (алгебры Буля), который позволяет перейти к представлению оператора преобразования в виде логических уравнений и затем упростить последние в соответствии с потребностями структуры КА.

Применение алгебры логики к задачам синтеза КА обусловлено аналогией понятий и категорий этой алгебры и двоичной системы счисления. В алгебре логики рассматриваются переменные, которые могут принимать только два значения, обозначаемых символами 0 и 1. В дальнейшем переменные величины будем обозначать буквами латинского алфавита.

Алгебра Буля описывается рядом правил, или аксиом, с помощью которых определены различные операции над элементами этой алгебры. Она представляет собой множество элементов (, а, b, с, …), для которых определены отношения эквивалентности и три операции: дизъюнкция (логическое сложение, операция ИЛИ), конъюнкция (логическое умножение, операция И) и отрицание (инверсия, операция НЕ). Отношение эквивалентности обозначается знаком «=»; операция дизъюнкции знаками + ,V; операция конъюнкции обозначается точкой, которую можно опускать (, или знаками ; операция инверсии обозначается чертой над переменными (например: ).

Для всех элементов алгебры Буля отношение эквивалентности удовлетворяет следующим свойствам:

1) рефлексивности: ;

2) симметричности: если , то ;

3) транзитивности: если и , то .

Алгебра логики определяется следующей системой аксиом [1]:

если

если (1)

Следует отметить, что если в аксиомах (1)(5), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, а так же элементов 0 и 1, то в аксиоме из одного выражения получится второе. Это свойство называется принципом двойственности.

Операции И, ИЛИ, НЕ удовлетворяют следующим законам.

1. Идемпотентные законы:

2. Коммутативные законы:

3. Ассоциативные законы:

4. Дистрибутивные законы:

5. Законы отрицания:

6. Законы двойственности (теорема де Моргана):

7. Закон двойного отрицания:

. (12)

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

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

1. Законы поглощения:

2. Законы склеивания:

3. Законы обобщенного склеивания:

В качестве примера докажем справедливость первого из тождеств (16), используя теоремы (9 и 10):

Так как правая часть тождеств 13 — 16 проще левой, то их можно использовать для упрощения сложных логических выражений.

Рассмотрим еще три логические операции.

1. Операция штрих Шеффера (операция И-НЕ), которая обозначается косой чертой и определяется соотношением:

2. Операция стрелка Пирса (операция ИЛИ-НЕ), которая обозначается символом и определяется соотношением:

3. Операции сумма по модулю два (ИСКЛЮЧАЮЩЕЁ ИЛИ, логическая неравнозначность), которая обозначается символом и определяется соотношением:

Операции штрих Шеффера и стрелка Пирса не являются ассоциативными [4]. Для них справедливы соотношения:

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

Можно показать, что для операции ИСКЛЮЧАЮЩЕЁ ИЛИ справедливы следующие тождества:

Переключательной функцией называется двоичная переменная , значения которой зависят от двоичных переменных (аргументов) . Каждому из возможных наборов аргументов, поставлено в соответствие определенное значение . Функции считаются различными, если значения отличаются по крайней мере для одного набора аргументов. При аргументах полное число Р их наборов:

P=2P. (22)

Так каждому из наборов могут соответствовать два значения (0 или 1) , то общеё число N различных функций аргументов равно:

N=2. (23)

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

Функция может быть задана или представлена различными способами. Наиболее употребительны табличный и алгебраический. При первом способе функция представляется в виде таблицы, в которую вписываются все возможные наборы аргументов в порядке возраста­ния их номеров, и для каждого набора устанавливается значение функции 0 или 1 [3].

В таблице 1 представлена функция y для трех двоичных переменных а, b, с.

Таблица 1.

Номер набора	a	b	c	y
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	1
6	1	1	0	0
7	1	1	1	1

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

Если в каждую конъюнкцию входят все переменные (или их отрицания), то такая конъюнкция называется минтермом (конституэнтой 1).

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

Функция, представленная в таблице 1, запишется в виде:

Функцию можно представить также в виде логического произведения элементарных логических сумм. Если в логическую сумму входят все переменные или их отрицания, то такая сумма называется макстермом (конституэнтой 0). Функция, представленная в виде конъюнкции макстермов, носит название совершенной конъюнктивной нормальной формы — СКНФ. Запись функции, представленной в таблице 1, в СКНФ имеет вид:

Используя законы двойственности, можно из СДНФ получить СКНФ и наоборот.

В теории переключательных функций особо важную значимость имеет теорема разложения: любую функцию можно разложить по переменной в форме:

Из этого выражения, используя принцип двойственности, можно получить двойственную теорему разложения:

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

С теоремой разложения связаны тождества:

Тождества (26) являются мощным средством для упрощения логических выражений. Пусть требуется упростить функцию:

Используя первое из тождеств (26) относительно , получим:

Выражение под знаком инверсии можно упростить, используя четвертое выражение тождеств:

.

Реализации логической функции должна предшествовать операция упрощения формулы (минимизация функции), т. е. получение такой формы функции, которой соответствует логическая схема с минимальным числом элементов. Эта форма называется оптимальной, или минимальной, дизъюнктивной нормальной формой.

Исходной формой функции при минимизации является её СДНФ. Разработано несколько методов минимизации функций. В методе Квайна минимизация осуществляется в два этапа. На первом этапе получают сокращенную ДНФ, пользуясь понятиями смежных минтермов и импликант. Основной операцией упрощения является операция склеивания. Смежными называются минтермы, отличающиеся формой вхождения в них лишь одного аргумента. Например, смежными являются минтермы:

и , , и

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

Конъюнкции, получаемые в результате склеивания двух смежных минтермов, называются импликантами.

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

Импликанты, которые не склеиваются с другими, называются простыми, или первичными. Простые импликанты и минтермы, которые не имели смежных им для склеивания, входят в результирующую ДНФ функции — так называемую сокращенную ДНФ.

На втором этапе минимизации производят устранение из сокращен­ной ДНФ избыточных импликант. Для иллюстрации смысла последних рассмотрим пример минимизации функций:

Сопоставляя поочередно все минтермы (первый с последующим, затем второй с последующими и т. д.), можно установить, что в этой функции склеиваются первый и второй, первый и третий, третий и четвертый минтермы, так что после склеивания получим:

Каждая из появившихся в результате импликант является простой, а функция — сокращенной ДНФ.

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

Простые импликанты, не влияющие на значение функции, называют избыточными. ДНФ функции, которая получается в результате устранения из сокращенной ДНФ всех избыточных импликант, носит название тупиковой ДНФ. В рассмотренном примере тупиковая ДНФ имеет вид:

В общем случае может существовать несколько тупиковых ДНФ, эквивалентных исходной СДНФ функции.

Искомая оптимальная (минимальная) ДНФ совпадает с той из тупиковых ДНФ, которая содержит минимальное число аргументов (букв). Для облегчения поиска тупиковых ДНФ были разработаны различные усовершенствования метода Квайна. Если число аргументов не более 4 — 6, минимизация СДНФ легко выполняется методом Вейча-Карно, основан­ным на табличном представлении значений минтермов в виде карт Карно, представляющих собой прямоугольные таблицы, разделенные вер­тикальными и горизонтальными линиями на клетки, общеё число которых равно числу минтермов. В каждую ячейку заносится значение одного минтерма, причем смежные минтермы располагается в соседних клетках. Соседними считаются клетки, имеющие общие стороны, а также распо­ложенные на краях одних и тех же строк и столбцов карты. Такое рас­положение минтермов обеспечивается принятым способом образования наборов аргументов, соответствующих различным клеткам карты.