- •Теория автоматов (часть I) Конспект лекций
- •Оглавление
- •1. Введение
- •2. Задачи анализа и синтеза
- •3. Абстрактный управляющий автомат
- •4. Синтез абстрактных автоматов
- •5. Синхронный автомат
- •6. Асинхронные автоматы
- •7. Автоматы Мили и Мура
- •8. Способы задания автоматов
- •8.1 Табличный способ задания автоматов
- •8.2. Задание автомата с помощью графа
- •8.3. Матричный способ задания автоматов
- •9. Переход от автомата Мили к автомату Мура и обратно
- •10. Этапы синтеза автоматов
- •11. Минимизация числа внутренних состояний автомата
- •12. Минимизация полностью определённых автоматов.
- •13. Совмещённая модель автомата (c-автомата )
- •14. Структурный синтез автомата
- •14.1. Канонический метод структурного синтеза автомата
- •14.2. Структурный синтез с-автомата
- •15. Кодирование состояний автомата
- •15.1. Метод противогоночного кодирования состояний автомата
- •15.2. Соседнее кодирование состояний автомата
- •15.3. Кодирование состояний автомата для минимизации комбинационной схемы
- •16. Элементарные автоматы памяти
- •17. Синтез автоматов на плм и пзу
- •Рекомендуемая литература
16. Элементарные автоматы памяти
RS-триггер – элемент памяти с двумя входами S – set, R – reset.
Основной недостаток - инверсное значение входных и выходных сигналов, нет защиты от аппаратных гонок.
Для того чтобы использовать данный триггер и устранить гонки применяют систему двухтактную, т.е. добавляют ещё один каскад.
R |
S |
Тn |
Тn+1 |
b1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
b2 |
1 |
1 |
1 |
1 |
b3 |
? |
Граф такого автомата:
2. D-триггер.
D |
Тn |
Тn+1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
3.Т-триггер
Т |
Тn |
Тn+1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Методы унитарного кодирования
При унитарном кодировании в любом коде - только 1 единица.
При этом коды 00..001 и 00..010 являются соседними
Сдвиговый регистр:
Граф сдвигового регистра:
Использование схем на основе двоичного счетчика и дешифратора
17. Синтез автоматов на плм и пзу
ПЛМ – программируемая логическая матрица.
Рассмотрим структуру микросхемы ПЛМ.
Данная микросхема легко программируется на основе канонических уравнений комбинационной схемы структурного автомата.
ПЗУ – постоянное запоминающее устройство.
Микросхема ПЗУ обычно содержит следующие входы и выходы.
Программа ("прошивка") для реализации автоматом на основе ПЗУ требуемого алгоритма имеет вид таблицы соответствия входных и выходных сигналов автомата. Программа записывается электрическим способом и обычно имеется возможность перезаписи программ в микросхему – ЭППЗУ.
Рекомендуемая литература
Основная литература
1. Карпов, Юрий Глебович. Теория автоматов: Учеб. для вузов / Карпов, Юрий Глебович. - М.: Питер, 2003, 2002. - 208c.: ил. - Библиогр.: с. 204. (количество в библиотеке - 24 экз).
2. Молчанов, Алексей Юрьевич. Системное программное обеспечение: Учеб. / Молчанов, Алексей Юрьевич. - СПб.: Питер, 2003. - 396c.: ил. - Библиогр.: с. 386. (количество в библиотеке - 20 экз).
3. Мельцов, Василий Юрьевич. Синтез микропрограммных управляющих автоматов. Учебное пособие / Мельцов, Василий Юрьевич, Фадеева, Татьяна Рафаиловна. – Киров: ВятГУ, 2000,-56с. (количество в библиотеке - 55 экз).
Дополнительная литература
4. Акулов, Олег Анатольевич. Информатика: базовый курс: Учеб. / Акулов, Олег Анатольевич, Медведев, Николай Викторович. - М.: Омега-Л, 2004. - 552c. - (Учебник для технических вузов). - Библиогр.: с. 545-546. (количество в библиотеке - 3 экз).
5. Калиш, Георгий Германович. Основы вычислительной техники: Учеб. пособие / Калиш, Георгий Германович. - М.: Высш. шк., 2000. - 271c. (количество в библиотеке - 2 экз).
6. Лысиков, Борис Григорьевич. Арифметические и логические основы цифровых автоматов: Учеб. / Лысиков, Борис Григорьевич. - 2-е изд., перераб. и доп. - Минск: Вышейш. шк., 1980. - 335c. (количество в библиотеке - 24 экз).
7. Савельев, Александр Яковлевич. Прикладная теория цифровых автоматов: Учеб. / Савельев, Александр Яковлевич. - М.: Высш. шк., 1987. - 272c. (количество в библиотеке -24 экз).
8. Лазарев, Владимир Георгиевич. Синтез управляющих автоматов / Лазарев, Владимир Георгиевич, Пийль, Елена Ивановна. - 3-е изд., перарб. и доп. - М.: Энергия, 1989. - 328c. (количество в библиотеке - 2 экз).
9. Сапожников, Валерий Владимирович. Методы синтеза надежных автоматов / Сапожников, Валерий Владимирович, Сапожников, Владимир Владимирович. - Л.: Энергия, 1980. - 93c. (количество в библиотеке - 11 экз).
10. Соловьев, Валерий Васильевич. Проектирование цифровых систем на основе программируемых логических интегральных схем / Соловьев, Валерий Васильевич. - М.: Горячая линия-Телеком, 2001. - 636c. (количество в библиотеке - 3 экз).
11. Глушков, Виктор Михайлович. Логическое проектирование дискретных устройств / Глушков, Виктор Михайлович, Капитонова, Юлия Владимировна, Мищенко, Андрей Тихонович; АН УССР, Ин-т кибернетики. - Киев: Наук. думка, 1987. - 263c.: ил. (количество в библиотеке - 4 экз).
13. Рейуорд-Смит, В. Дж. Теория формальных языков: Вводный курс / Рейуорд-Смит, В. Дж. - М.: Радио и связь, 1988. - 127c. (количество в библиотеке - 1 экз).