ТЕОРИЯ АВТОМАТОВ Направление «Программная инженерия» (бакалавр) Курс IIIСеместр 5 Форма обучения очная Лекции:18 Лабораторные работы:18 Выполняемые задания:Расчётно-графическая работа Самостоятельная работа: Всего часов: 108 Итоговый контроль: Диф-зачёт. Отв. за преп. дисциплины: доцент В. А. Афанасьев 1/10Теория автоматов

Цели и задачи курса Целью дисциплины является 1. Изучение и практическое освоение общих методов синтеза цифровых схем на основе их представления в виде автоматов (с памятью и без), а также методов синтеза управляющих автоматов на алгоритмическом и функциональном уровнях. 2. Моделирование схем автоматов (с памятью и без) в среде программного комплекса Multisim Основные разделы (модули) курса: Введение. Синтез цифровых автоматов без памяти (комбинационных схем) на логических элементах разной степени интеграции. Общая теория конечные цифровых автоматов с памятью. Триггерные устройства как элементарные автоматы Мура. Структурные автоматы асинхронного и синхронного типов. Принцип микропрограммного управления и обобщенная структура операционных устройств. Синтез микропрограммных автоматов с жёсткой логикой. Связи с другими дисциплинами основной образовательной программы: Дисциплина ТЕОРИЯ АВТОМАТОВ опирается на знания, полученные студентами в курсах: ЭЛЕКТРОНИКА, СПЕЦИАЛЬНЫЕ ГЛАВЫ МАТЕМАТИКИ (раздел МАТЕМАТИЧЕСКАЯ ЛОГИКА), АРХИТЕКТУРА СРЕДСТВ ВТ. «Остаточные» знания данной дисциплины будут использованы в курсах: МОДЕЛИРОВАНИЕ, КОНСТРУИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ. 2/10 Теория автоматов

Литература Основная 1. Карпов Ю. Г. Теория автоматов: учебник для вузов.– СПб.: Питер, с.:ил (1 эка) 2. Бойко В. И. и др. Схемотехника электронных систем. Цифровые устройства. - СПб.:БХВ - Петербург, с. (33 экз) 3. Бойт К. Цифровая электроника. Пер. с нем. - М.: Техносфера, с.(3 экз) 4. Угрюмов Е. П. Проектирование элементов и узлов ЭВМ: Учеб. пособие для вузов. – М.: Высшая Школа, с.: ил. (16 экз) 5. Пухальский Г.И., Новосельцева Т. Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. -М.: Радио и связь, с.: ил. (3 экз) 6. Скляров В. А. Синтез автоматов на матричных БИС / Под. Ред. С. И. Баранова. – Минск: Наука и техника, с.: ил. (1 эка) 7.Учебно-методические материалы по курсу на кафедральном сервере. Дополнительная (отсутствует в библиотеке НГТУ) 8. Вашкевич Н. П. Синтез микропрограммных управляющих автоматов. Учебное пособие. Издание Пенз. Полит. Инс-та, 1990, 114 с. 9. Потемкин И. С. Функциональные узлы цифровой автоматики. – М.: Энергоатомиздат, с.: ил. (1 экз) 10. Угрюмов Е. П. Цифровая схемотехника. - СПб.: БХВ – Санкт-Петербург, 2000.( 2005 г. - второе издание, расширенное и дополненное) – 528 с.: ил. 11. Уэйкерли Дж. Проектирование цифровых устройств. В 2-х т. Пер. с англ. - М.: Постмаркет, Новиков Ю. В. Основы цифровой схемотехники. М.: Мир, с. 3/10Теория автоматов

Модуль 1. Введение. Цифровые устройства обработки информации 1. Представление информации физическими сигналами.Представление информации 2. Два типа цифровых устройств обработки информации – комбинационные схемы и автоматы с памятью.Два типа цифровых устройств 3. Логические элементы (ЛЭ) и соглашения.Логические элементы 4/10Теория автоматов. Модуль 1

Представление информации физическими сигналами Цифровой автомат (ЦА) – цифровое устройство для хранения, передачи и преобразования информации по заданному алгоритму. Информация в цифровом устройстве представляется в двоичном алфавите с использованием символов 1 и 0. Аналог этих символов – электрические сигналы с хорошо различимыми уровнями, один из которых условно называют высоким (H – уровень), а другой низким (L – уровень). В цифровых устройствах сигналы изменяются не непрерывно, а лишь в дискретные моменты времени t n = nT, где n = 0, 1, 2 …, а T – интервал дискретизации Предполагается (на рисунке), что сигналы переключаются только в пределах такта между моментами t n и t n+1. Чтобы не ссылаться на значение Т, вводится понятие автоматного времени t = t n / T = 0, 1, 2, … 5/10Теория автоматов. Модуль 1 CLK U ВЫХ Моменты фиксации Такт Т t=t n /T Последовательный код 1011 Возможное изменение сигнала в некоторой точке схемы ЦА.

Два типа цифровых устройств обработки – комбинационные схемы и автоматы с памятью По принципу функционирования, т.е. способу формирования выходных сигналов в течение временного такта, цифровые устройства подразделяются на два типа: комбинационные схемы и автоматы. 6/10Теория автоматов. Модуль 1 Комбинационные схемы характеризуются однозначной зависимостью между словами Х(t) и Y(t) для каждого дискретного момента времени t. Реализуемый в этих схемах способ обработки информации называется комбинационным, т. к. результат зависит только от комбинации входных сигналов и вырабатывается сразу при подаче входной информации. В комбинационных схемах отсутствует память, их ещё называют автоматы без памяти. Автоматы обладают памятью, поэтому в этих схемах для определения выходного слова Y(t) требуется знание не только входного слова X(t) в этот же момент времени, но и состояние элементов памяти схемы, которое, в свою очередь, определяется входными сигналами в предыдущие моменты времени. Другой отличительный признак: в комбинационной схеме нет замкнутых контуров (от выхода ко входу), в последовательностной схеме они есть. Цифровая схема X = {x 1, x 2, …, x n } Y = {y 1, y 2, …, y m } y j = {0, 1} x i = {0, 1} X(t)X(t) Y(t)Y(t)

Логические элементы (ЛЭ) Логические элементы (ЛЭ) - элементы, входящие в состав электронных цифровых устройств и выполняющие простейшие логические операции над двоичными переменными. ЛЭ отличаются характером реализуемых функций (\/, /\, …) и числом входов. Число входов соответствует числу аргументов булевой функции. Различают схемы 3-х уровней: структурная, функциональная и принципиальная. 7/10Теория автоматов. Модуль 1 & & 2И-НЕ & Конъюнктор 1 Дизъюнктор 1 Инвертор =1 Элемент М2 & & 1 2И-ИЛИ-НЕ 1 2ИЛИ-НЕ Метка операции Графическое изображение функциональной схемы цифрового устройства выполняется с использованием стандартизованных изображений ЛЭ, определённых ГОСТ Все ЛЭ, принадлежащие одной и той же электрической схеме, должны принадлежать одной и той же серии или набору.

Определение серии ЛЭ 8/10Теория автоматов. Модуль 1 Серия ЛЭ включает функционально полный набор ЛЭ, объединенных общими электрическими, конструктивными и технологическими параметрами. Технологические параметры определяются видом транзисторной логики или способом соединения транзисторов в пределах одного логического элемента. Виды транзисторной логики: транзисторно-транзисторная логика (ТТЛ), ТТЛ с диодами Шоттки (ТТЛШ), эмиттерно-связанная логика (ЭСЛ). Широкое распространение получили также микросхемы на МОП -транзисторах разного типа проводимости (КМОП -структуры) и т. д. Конструктивные параметры, как правило, задаются параметрами корпуса (форма корпуса, расположение выводов, расстояние между выводами и т. д.) интегральной микросхемы (ИМС), в котором и помещается полупроводниковый чип с логическими элементами. Электрические параметры задаются значениями уровней сигнала, быстродействием, помехоустойчивостью и рассеиваемой мощностью.

Логические соглашения Существуют 2 рода логических соглашений в зависимости от того, каким уровнем электрического сигнала (H - или L- уровнем) кодируется логическая единица. Если логическая «1» кодируется H- уровнем, то это положительная логика, если L-уровнем, то это отрицательная логика. Пример. Пусть таблица истинности ЛЭ задана с использованием H- и L- уровней, тогда соответствующие ей таблицы истинности для положительной и отрицательной логики будут представлены ниже. 9/10Теория автоматов. Модуль 1 X1X1 X2X2 Y LLL LHL HLL HHH Таблица истинности X1X1 X2X2 Y=X1 X Положительная логика X1X1 X2X2 Y=X1 ˅ X Отрицательная логика Соответствие для основных операций: И ИЛИ, И-НЕ ИЛИ-НЕ, М2

Контрольные вопросы 1. Дайте определение двум типам цифровых устройств: - комбинационная схема, - цифровой автомат. 2. Назовите ГОСТ на изображения ЛЭ на функциональных схемах. 3. Дайте определение серии логических элементов. 4. Назовите 2 рода логических соглашений, использующихся при кодировании двоичных символов. 10/10Теория автоматов. Модуль 1