Кафедра К3 Прикладная математика, информатика
и вычислительная техника

1. Вводные сведения
   • Понятие «автомат», два аспекта этого понятия.
   • Дисциплина «Теория автоматов», цели и задачи её изучения.
2. Системы счисления
   • Системы счисления, позиционные, непозиционные, однородные, неоднородные, с постоянными весами разрядов, с непостоянными весами разрядов, код Грея, системы счисления специального назначения.
   • Перевод чисел из одной системы счисления в другую.
   • Два метода перевода чисел: табличный и расчетный.
   • Перевод целых чисел, перевод правильных дробей, перевод неправильных дробей, перевод в системы счисления с кратным основанием.
   • Выбор системы счисления для ЭВМ.
3. Логические основы цифровых автоматов
   • Определение логической переменной и логической функции.
   • Простые и сложные функции.
   • Основные элементарные логические функции: отрицание, конъюнкция, дизъюнкция, сложение по модулю два, равнозначность, стрелка Пирса, штрих Шеффера.
   • Эквивалентность и её примеры.
   • Основные законы и правила алгебры логики.
   • Понятие полноты (базиса), система логических функций.
   • Представление логических функций в базисе И, ИЛИ, НЕ.
   • Нормальные и совершенные нормальные конъюнктивные и дизъюнктивные формы.
   • Понятие минимального базиса.
   • Базис Шеффера.
   • Представление логических функций в базисе Шеффера.
   • Базис Пирса.
   • Представление логических функций в базисе Пирса.
   • Задача анализа и синтеза логических функций.
   • Геометрическое и числовое представление логических функций.
   • Понятия и определения: минтерм,ранг, покрытие, вхождение, импликанта, сокращенная нормальная форма, тупиковая форма.
   • Задача минимизации логических функций и ограничения при ее рассмотрении.
   • Методы минимизации логических функций.
   • Минимизация логических функций методом Квайна. Пример.
   • Минимизация логических функций методом Квайна мак Класки.
   • Минимизация с помощью карт Карно.
   • Не полностью определенные логические функции и их минимизация.
4. Арифметические основы цифровых автоматов
   • Способы представления чисел в ЭВМ. Форматы представления чисел с фиксированной запятой (точкой) и с плавающей запятой.
   • Диапазон и точность представления чисел.
   • Представление в ЭВМ чисел со знаком.
   • Прямой, обратный и дополнительный коды.
   • Алгебраическое суммирование чисел с фиксированной запятой с использованием обратного и дополнительного кодов.
   • Модифицированные коды.
   • Умножение правильных дробей, представленных в прямом, дополнительном, обратном кодах на два в степени +/- k.
   • 4 способа умножения чисел с фиксированной запятой, заданных в прямом коде.
   • Логические и аппаратные методы ускорения умножения. Умножение одновременно на два разряда множителя. Матричные схемы умножения.
   • Умножение в дополнительном коде с использованием корректирующего шага.
   • Умножение в дополнительном коде используя анализ двух смежных разрядов множителя.
   • Умножение в обратном коде.
   • Деление чисел с фиксированной запятой, заданных в прямом и дополнительном кодах.
   • Деление с восстановлением остатка и без восстановления.
   • Деление со сдвигом остатка и со сдвигом делителя.
   • Выполнение арифметических операций над числами с плавающей запятой.
   • Обоснование блокировок.
   • Машинный нуль и бесконечность.
   • Десятичные двоично-кодированные системы.
5. Абстрактные автоматы
   • Основные понятия и определения.
   • Конечный автомат, полностью определенный, частичный автомат, синхронный, асинхронный автомат.
   • Закон функционирования автоматов МИЛИ и МУРА.
   • Табличный и графический способы задания автоматов.
   • Эквивалентные автоматы.
   • Преобразование автомата МУРА в автомат МИЛИ и наоборот.
   • Совмещенная модель автомата (С автомат).
   • Задача минимизации автоматов.
   • Три основных вида соединения автоматов: последовательное, параллельное и с обратной связью.
   • Задача композиции и декомпозиции автоматов.
6. Структурные автоматы
   • Канонический метод структурного синтеза автоматов.
   • Теорема о структурной полноте.
   • Элементарные полные автоматы с одним и двумя входами.
   • Основные этапы и примеры структурного синтеза автоматов.
   • Состязания и гонки в автоматах.
   • Способы устранения критических состязаний.
   • Противогоночное кодирование состояний автомата.
   • Кодирование состояний и сложность комбинационных схем, реализующих функции выходов и возбуждения элементов памяти.
7. Микропрограммные автоматы
   • Принцип микропрограммного управления.
   • Модель дискретного преобразователя Глушкова.
   • Функции операционного и управляющего автоматов.
   • Задача проектирования операционного устройства.
   • Функциональная микропрограмма.
   • Язык функционального микропрограммирования.
   • Содержательный и закодированный графы микропрограммы.
   • Структурная организация операционных автоматов.
   • Структурный базис: шины, регистры, комбинационные схемы.
   • Каноническая структура операционного автомата.
   • Операционные элементы комбинационного и накапливающего типов.
   • Управляющие автоматы с жесткой логикой.
   • Интерпретация микропрограммы автоматами МИЛИ и МУРА.
   • Управляющие автоматы с программируемой логикой.
   • Микрокоманды.
   • Распределение микроопераций по полям микрокоманды.
   • Принудительная и естественная адресация микрокоманд.
8. Учебный стенд «Altera DE 2-115» и средства автоматизации проектирования.
   • Структура стенда «Altera DE 2-115» и программируемой логической интегральной схемы (ПЛИС) «CYCLON IY».
   • САПР «QUARTUS II». Ввод проектов, верификация проектов, реализация проектов в кристалле ПЛИС.
   • Основы языка VHDL.
   • Объекты языка: сигнал, переменная, константа.
   • Интерфейс и архитектура объекта.
   • Поведенческий, структурный и смешанные стили описания архитектуры.
   • Последовательные и параллельные операторы.
   • Функции и процедуры.
   • Библиотеки и пакеты.
   • Верификация HDL описаний.
   • Приложение ModelSim. Создание нового проекта, добавление новых файлов, моделирование в ModelSim.

Основная литература:

1. Савельев А. Я. Прикладная теория цифровых автоматов. Учебник для вузов — М.: Высшая школа, 1987 — 272 стр. (http://en.bookfi.net/book/587942)
2. Самофалов К. Г. и др. Прикладная теория цифровых автоматов. — К.: Вища школа. Головное издательство 1987 — 375 стр. (http://en.bookfi.net/book/482488)
3. Ефремов Н. В. Логические основы цифровых автоматов. Учебное пособие — 3-е изд. — М.: МГУЛ, 2008 — 40 стр.
4. Цилькер Б. Я., Орлов С. А. Организация ЭВМ и систем. Учебник для вузов — СПб.: Питер, 2007 — 667 стр. (http://en.bookfi.net/book/720223)

Дополнительная литература:

5. Бибило П. Н. Основы языка VHDL. Изд. 3-е. доп. — М.: Издательство ЛКИ. 2007. — 328 с. (https://rusneb.ru/catalog/000199_000009_000689580/)
6. Грушвицкий Р. И., Мурсаев А. X. Угрюмов Е. П. Проектирование систем на микросхемах с программируемой структурой. 2-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2006. — 736 с. (http://bookre.org/reader?file=636500)
7. Амосов В. В. Схемотехника и средства проектирования цифровых устройств. — СПб.: БХВ — Петербург, 2007. — 560 с. (https://www.razym.ru/tehnicheskaya/electronika/259217-amosov-v-shemotehnika-i-sredstva-proektirovaniya-cifrovyh-ustroystv-2012.html).

Учебные и учебно-методические пособия:

8. Ефремов Н. В. Теория автоматов: учебно-методическое пособие — Москва: Издательство МГТУ им. Н.Э. Баумана, 2019. — 78,
9. Ефремов Н. В. Проектирование операционных устройств в кристалле ПЛИС с использованием языка VHDL в САПР QUARTUS II: учебно-методическое пособие — Москва: Издательство МГТУ им. Н.Э. Баумана, 2019. — 73,
10. Ефремов Н. В. Введение в систему автоматизированного проектирования Quartus II. Учебное пособие. — М.: ГОУ ВПО МГУЛ, 2011. — 147 с.
11. Ефремов Н. В., Бородин А. А. Инструментальные средства проектирования и отладки цифровых систем на программируемом кристалле фирмы «Altera». Учебное пособие. — М.: ФГБОУ ВПО МГУЛ, 2012. — 151 с.
12. Теория автоматов. Лабораторный практикум: учебное пособие / Под ред Б.Н. Ковригина. М.: НИЯУ МИФИ, 2012. 192 с. (https://rusneb.ru/catalog/000199_000009_006743688/)
13. Ковригин Б. Н. Введение в инструментальные средства проектирования и отладки цифровых устройств на ПЛИС: Учебно-методическое пособие. М.: МИФИ, 2006. — 192 с. (https://studfile.net/preview/6290352/)

Нормативные документы

14. IEEE Standard VHDL Language Reference Manual, IEEE Std 1076 — 1993. (https://edg.uchicago.edu/~tang/VHDLref.pdf)

Ресурсы информационно-телекоммуникационной сети «Интернет» и другие электронные информационные источники

1. Электронно-библиотечная система издательства «Лань» (электронная учебная, методическая и научная литература по тематике дисциплины)
2. Электронные издания Издательства МГТУ им. Н.Э. Баумана (электронная учебная, методическая и научная литература по тематике дисциплины)
3. Электронный каталог библиотеки МГУЛ (учебная, методическая и научная литература по тематике дисциплины)
4. Электронная образовательная среда МФ (для обеспечения учебно-методическими материалами, проверки знаний студентов по различным разделам дисциплины, подготовленности их к проведению и защите лабораторных работ)