- •Теория автоматов. Уровни представления эвм.
- •Операционные элементы. (оэ)
- •Процессор гса:
- •Достоинства и недостатки.
- •Операционное устройство для выполнения операций алгебраического сложения двоичных чисел.
- •Суммирование при использовании прямого кодирования.
- •Суммирование чисел при использовании обратного кода.
- •Дополнительный код.
- •Модифицированный код.
- •Пример суммирования.
- •Конечные автоматы.
- •Теория конечных автоматов
- •Способы задания функций переходов.
- •Автоматы ( с выходным преобразователем)
- •Способы задания автоматов
- •Способы задания автомата Миля
- •Преобразование автоматов из Миля в Мура и обратно Понятие эквивалентности автоматов
- •Преобразование Мура в Миля
- •Техника преобразований.
- •Обратный переход. Построение Мура для заданного Миля.
- •Частичные или не полностью определенные автоматы.
- •Синтез конечных автоматов.
- •Абстрактный синтез конечных автоматов.
- •Построение дерева входных последовательностей.
- •Структурный этап синтеза автоматов.
- •Основные этапы структурного синтеза.
- •Типы памяти.
- •Основные типы триггеров.
- •Пример структурного синтеза синхронного автомата.
- •`Временная диаграмма.
- •Этап минимизации автомата при абстрактном синтезе. Минимизация полностью определенного автомата.
- •Алгоритмы минимизации на основе треугольной матрицы.
- •Минимизация числа состояний частичного автомата.
- •Минимизация частичного автомата.
- •Абстрактный этап синтеза конечного автомат. (неканонический метод).
- •Алгоритм перехода от граф схемы микропрограммы к автомату Мура.
- •Учет взаимодействия проекционного и управляющего автоматов. Алгоритм получения.
- •Алгоритм получения частичного автомата.
- •Множество входных значений.
- •Кодирование состояний синхронного автомата.
- •Кодирование соседними кодами.
- •Минимизация числа переключений элементов памяти.
- •Универсальный способ кодирования (для синхронного автомата).
- •Автомат с дешифратором.
- •Асинхронные автоматы.
- •Этапы синтеза асинхронного автомата.
- •Реализация асинхронного rs триггера на логических элементах.
- •Установочные входы в триггерах.
- •Синхронные элементы памяти.
- •Требования, предъявляемые к синхросигналу.
- •Синтез синхронного rs триггера.
- •Синтез триггера с задержкой.Реализация асинхронного t триггера.
- •Исключение состязаний элементов памяти в синхронных автоматах.
- •Структура автоматов на плм и пзу.
- •Явление рисков в комбинационных узлах.
- •Исключение влияние рисков.
- •Построение схем без риска.
- •Алгоритм построения схемы без рисков по днф.
- •Алгоритм построения схемы без риска.
- •Автоматы, языки и грамматики.
- •Задача распознавания цепочек языка.
- •Классификация грамматик по Хомскому.
- •Примеры построения грамматик.
- •Грамматика для выполнения арифметических операций.
- •Соответствие конечных автоматов и автоматных грамматик.
- •Этапы для заданной автоматной грамматики.
- •Этапы для заданной автоматной грамматики.
- •Недетерминированные конечные автоматы.
- •Преобразование недетерминированного автомата в детерминированный.
- •Преобразование некоторых типов грамматики к автоматному ввиду.
- •Алгоритм получения правил, не содержащих правил вывода нетерминальных символов.
- •Построение распознавателей и преобразователей.
- •Построение распознавателей.
- •Алгоритм построения преобразователя.
Автомат с дешифратором.
Схема имеет минимальное число элементов памяти и обладает положительными свойствами, характерными для унитарного кодирования.
Каждому состоянию соответствует два кода с минимальным и максимальным числом разрядов, недостаток схемы – дополнительные затраты виде дешифратора.
Два кода, предписанных одному состоянию, связаны между собой функцией дешифратора.
При кодировании состояний предполагаем наличие дешифратора.
В данном случае 24 (2 входа, 4 выхода)
Каждому состоянию соответствует два входа.
При записи функции возбуждения в данном случае аргументами являются YiиXi, а переходы триггера 00 ; 01 ; 10 ; 11 рассматриваются относительноqi/
Рассмотрим DиRSтриггера:
В качестве элемента памяти используется 2 Dтриггера.
На Dподаем 1 при переходе 01 ; 11
01 01 11 01 11
D1 = Y0⌐X v Y0X v Y1⌐X v Y2⌐X v Y3⌐X = Y0 v ⌐X (Y1 v Y2 v Y3)
12 14 24 32 44
01 01 11 11
D2 = Y1X v Y1⌐X v Y3X v Y3⌐X = Y1 v Y3
23 24 43 44
Далее RSтриггер (R1– сброс 1 разряда)
10 10 00
R1 = Y1X v Y3X v Y2X
23 43 31
01 01 11 11 01
S1 = Y0⌐X v Y2⌐X v Y1⌐X v Y3⌐X v Y0X = ⌐X (Y0 v Y2) v Y0X
12 32 24 44 14
10 10 00
R2 = Y2X v Y2⌐X v Y0⌐X = Y2
31 32 12
01 01 01 11 11
S2 = Y0X v Y1⌐X v Y1X v Y3X v Y3⌐X = Y0X v Y1
14 24 23 43 44
Асинхронные автоматы.
Ранее рассматривались:
т.е.раньше неявно присутствовал синхроимпульс.
Наличие синхроимпульса позволяло осуществлять переход, при отсутствии его автомат остается в текущем состоянии.
По существу синхроимпульс является дополнительным входным сигналом. Входные сигналы можно разделить в зависимости от наличия синхроимпульса:
Синхронизируемое
С – синхроимпульс
Пример :
Разновидностью данного сигнала является импульсный сигнал
Потенциальный сигнал
Новое входное значение появляется после изменений предыдущего значения, т.е. длительности 0 и 1 могут быть разными.
Асинхронным автоматомназывается автомат, изменение состояния которого могут происходить в произвольные моменты времени, и эти моменты времени определяются сменой входного сигнала.
Тип автомата определяется типом входного сигнала.
Если входной сигнал потенциален, то автомат асинхронный, в противном случае – синхронный. При асинхронной реализации автомата для обеспечения устойчивой его работы все его состояния должны быть устойчивыми (аналогично петли СИ в синхронном автомате).
Состояние Siназываетсяустойчивым, если при переходе в это состояние под воздействием входного сигналаPkавтомат остается в этом состоянии до тех пор, пока входной сигнал не станет отличаться отPk.
Автомат будет асинхронным, если уже на абстрактном уровне все его состояния - устойчивы.
Пример асинхронного автомата:
Составим таблицу переходов:
W |
S/X1X2 |
00 |
01 |
10 |
11 |
0 |
S1 |
S1 |
S1 |
S3 |
S2 |
0 |
S2 |
S1 |
S2 |
S2 |
S2 |
1 |
S3 |
S1 |
S2 |
S3 |
S2 |
0 – устойчивое состояние (петля)
Проверка устойчивости:
S1S3 (двигаемся по строке, а потом по столбцу)
Для проверки является ли автомат асинхронным (по таблице переходов) вначале выделяем переходы соответствующие петлям вокруг состояний.
В каждой строке с номером Iобводим состояниеSi, затем проверяется устойчивость переходов из каждого состояния.
Например переход S1S3проверяется следующим образом :
Смотрится в строке с текущем состоянием под воздействием входного сигнала в какое состояние он должен перейти (горизонтальное движение стрелки)
Затем в столбце соответствующим данному сигналу ищется состояние, в которое переходит автомат, но отмеченное кружком (движение вертикальное).
Если все переходы попадают в отмеченное состояние, то все состояния устойчивы и автомат может быть асинхронным.