Введение
Теория автоматов
П.И. Уваров
Теория автоматов
НГТУ каф ВСТ
Оглавление
Литература: 3
1. Теория автоматов. 3
1.1. Введение. 3
1.2. Постановка задачи «Теории автоматов». 3
1.3. Логические схемы в КА.. 5
1.4. Булевы функции. 7
1.5. Свойства булевых функций. 9
1.6. Нормальные формы представления БФ.. 10
1.6.1. Дизъюнктивные представления. 10
1.6.2. Конъюнктивные представления. 11
1.7. Реализация булевых функций. 11
1.8. Минимизация БФ.. 12
1.8.1. Постановка задачи минимизации БФ.. 12
1.8.2. Диаграммы Вейча. 13
1.8.3. Карты Карно. 16
1.8.4. Минимизация не полностью определённых БФ.. 17
1.9. Элементы памяти. 18
1.9.1. Классификация элементов памяти. 18
1.9.2. Внутренняя структура триггеров. 19
1.9.3. Основные типы базовых триггеров. 19
1.9.4. о. 19
Литература:
К.Фрике. Вводный курс цифровой электроники. М.: Техносфера, 2003 – 432с.
Угрюмов Е.П. Цифровая схемотехника. – СПб.: БХВ-Петербург, 2004.-528 с.: ил.
Теория автоматов / Ю.Г. Карпов –СПб.: Питер, 2002. – 224 с.: ил.
Организация ЭВМ. 5-у изд. / К. Хамахер, З. Вранешич, С. Заки. – СПб.: Питер; Киев: Издательская группа BHV, 2003.– 848 с.: ил. – (Серия «Классика computer science»)
Схемотехника ЭВМ – это свод правил и методик, позволяющий эффективно проектировать цифровые схемы и устройства любой сложности.
В основе построения любой цифровой (дискретной, бинарной...) схемы лежит умение:
1. Разделить проектируемую схему на функциональные блоки.
2. Разбить каждый функциональный блок на серию однотипных элементов.
3. Выделить в элементах базовую ячейку (элементарный блок – ЭБ).
4. Синтезировать ЭБ.
5. Мультиплицировать каждый ЭБ до соответствующего элемента.
6. Скомпоновать из элементов функциональные блоки.
7. Объединить схемы функциональных блоков в общую принципиальную схему.
8. Отладить работу схемы.
Формально первые три пункта можно объединить с четвёртым, но в действительности это невозможно из-за громадной длины таблиц, описывающих работу блоков и элементов. Реальный синтез можно выполнить только для ЭБ. Этот синтез представляет собой основу построения схем и выполняется в соответствии со сводом правил. Изучение и систематизация этих правил синтеза выполняется в курсе «Теория автоматов».
1.2. Постановка задачи «Теории автоматов»
В основе любой деятельности лежит преобразование и обработка информации. Информация имеет разнообразные представления и в общем преобразование (обработку) информации можно представить (рис.1.2.1) в виде существования:
· входного информационного потока (A);
· некоторого преобразователя информации (Ф);
· выходного информационного потока (B).
Преобразователь Ф формирует по определённым правилам выходной поток В, базируясь на данных потока А, т.е. выполняет преобразование А®В.
Потоки А и В могут иметь произвольный вид, например, быть аналоговыми, частотными и т.д. Конечно, можно выполнять преобразования информационных потоков (ИП) именно в том виде, в котором они представлены, но при этом преобразования носят частный характер и не отличаются сложностью и разнообразием. Отсутствует возможность накопления информации, сложно реализовать временные зависимости, входные и выходные ИП могут иметь различную природу.
Для решения этих проблем необходим некоторый универсальный преобразователь ИП А®В, в качестве которого используются цифровые преобразователи информации. Эти преобразователи представляются в виде конечных автоматов (КА) и их место в общем преобразовании показано на рис.1.2.2. Здесь преобразователь информации Ф разбит на три блока:
· Входной преобразователь (А®Х), приводящий входной ИП произвольного вида А в цифровой (бинарный) вид;
· Конечный автомат (КА) , выполняющий преобразование по установленным правилам бинарного потока Х в бинарный поток Y, т.е. выполняющий преобразование X®Y.
· Выходной преобразователь (Y®B), переводящий результирующий цифровой поток Y в выходной поток В.
КА в виду его цифровой (бинарной) природы обладает возможностями:
· логической обработки информации на основе алгебры логики (булевой алгебры);
· накопления информации об истории процесса;
· представления процесса обработки в виде алгоритмов;
· простотой технической реализации алгоритмов;
· относительной простотой отладки и наладки схемы КА.
Отметим, что, если потоки А и В цифровые с аналогичными параметрами, то входной и выходной преобразователи могут отсутствовать.
Структура самого КА представлена на рис.1.2.3. В КА можно выделить два основных блока:
· ЛС – логическая схема;
· ЭП – элементы памяти.
Основное назначение блока элементов памяти – хранение кода текущего состояния КА.
Блок логической схемы предназначен для:
· приёма входного ИП;
· выработки на основании информации о текущем состоянии КА и входного информационного потока:
o выходного информационного потока;
o значения новых состояний КА.
Работа КА синхронизируется во времени серией синхросигналов, которые представляют собой последовательность синхронизирующих импульсов (СИ). При поступлении одного СИ происходит переход в новое состояние КА и вырабатывается одно слово выходного ИП.
Существуют асинхронные КА, но они сложно синтезируемы, неустойчиво работают и не получили широкого распространения.