- •Теория автоматов. Уровни представления эвм.
- •Операционные элементы. (оэ)
- •Процессор гса:
- •Достоинства и недостатки.
- •Операционное устройство для выполнения операций алгебраического сложения двоичных чисел.
- •Суммирование при использовании прямого кодирования.
- •Суммирование чисел при использовании обратного кода.
- •Дополнительный код.
- •Модифицированный код.
- •Пример суммирования.
- •Конечные автоматы.
- •Теория конечных автоматов
- •Способы задания функций переходов.
- •Автоматы ( с выходным преобразователем)
- •Способы задания автоматов
- •Способы задания автомата Миля
- •Преобразование автоматов из Миля в Мура и обратно Понятие эквивалентности автоматов
- •Преобразование Мура в Миля
- •Техника преобразований.
- •Обратный переход. Построение Мура для заданного Миля.
- •Частичные или не полностью определенные автоматы.
- •Синтез конечных автоматов.
- •Абстрактный синтез конечных автоматов.
- •Построение дерева входных последовательностей.
- •Структурный этап синтеза автоматов.
- •Основные этапы структурного синтеза.
- •Типы памяти.
- •Основные типы триггеров.
- •Пример структурного синтеза синхронного автомата.
- •`Временная диаграмма.
- •Этап минимизации автомата при абстрактном синтезе. Минимизация полностью определенного автомата.
- •Алгоритмы минимизации на основе треугольной матрицы.
- •Минимизация числа состояний частичного автомата.
- •Минимизация частичного автомата.
- •Абстрактный этап синтеза конечного автомат. (неканонический метод).
- •Алгоритм перехода от граф схемы микропрограммы к автомату Мура.
- •Учет взаимодействия проекционного и управляющего автоматов. Алгоритм получения.
- •Алгоритм получения частичного автомата.
- •Множество входных значений.
- •Кодирование состояний синхронного автомата.
- •Кодирование соседними кодами.
- •Минимизация числа переключений элементов памяти.
- •Универсальный способ кодирования (для синхронного автомата).
- •Автомат с дешифратором.
- •Асинхронные автоматы.
- •Этапы синтеза асинхронного автомата.
- •Реализация асинхронного rs триггера на логических элементах.
- •Установочные входы в триггерах.
- •Синхронные элементы памяти.
- •Требования, предъявляемые к синхросигналу.
- •Синтез синхронного rs триггера.
- •Синтез триггера с задержкой.Реализация асинхронного t триггера.
- •Исключение состязаний элементов памяти в синхронных автоматах.
- •Структура автоматов на плм и пзу.
- •Явление рисков в комбинационных узлах.
- •Исключение влияние рисков.
- •Построение схем без риска.
- •Алгоритм построения схемы без рисков по днф.
- •Алгоритм построения схемы без риска.
- •Автоматы, языки и грамматики.
- •Задача распознавания цепочек языка.
- •Классификация грамматик по Хомскому.
- •Примеры построения грамматик.
- •Грамматика для выполнения арифметических операций.
- •Соответствие конечных автоматов и автоматных грамматик.
- •Этапы для заданной автоматной грамматики.
- •Этапы для заданной автоматной грамматики.
- •Недетерминированные конечные автоматы.
- •Преобразование недетерминированного автомата в детерминированный.
- •Преобразование некоторых типов грамматики к автоматному ввиду.
- •Алгоритм получения правил, не содержащих правил вывода нетерминальных символов.
- •Построение распознавателей и преобразователей.
- •Построение распознавателей.
- •Алгоритм построения преобразователя.
Реализация асинхронного rs триггера на логических элементах.
В качестве элемента памяти воспользуемся асинхронным Dтриггером.
Приведем таблицу переходов Dтриггера:
0
0 0 т.е. значениеDпишется над стрелкой.
1
0 1
0
1 0
1
1 1
Следовательно
Это абстрактный закодированный автомат, представленный RSтриггер.
Код состояния совпадает со значением выходного сигнала Q.
RS/q |
00 |
01 |
11 |
10 |
0 |
0 |
1 |
-- |
0 |
1 |
1 |
1 |
-- |
0 |
Нарисуем карты Карно
|
|
|
------------R | |
|
|
------------S |
| |
|
0 |
1 |
-- |
0 |
Q - |
1 |
1 |
-- |
0 |
тогда Q = S v ⌐RQ = ⌐⌐(S v ⌐RQ) = ⌐(⌐S * ⌐(RQ))
или
|
|
|
------------R | |
|
|
------------S |
| |
|
0 |
1 |
-- |
0 |
Q - |
1 |
1 |
-- |
0 |
тогда Q = (Q v S) ⌐R = ⌐(⌐(Q v S) v R)
Подавая различные разрешенные комбинации на входы триггера, убеждаемся что второй выход является ⌐Q. На запрещенных комбинациях на прямом и инверсных выходах мы получаем одно и тоже, либо 0, либо 1 все зависит от использованной элементной базы.
Рассмотрим 1 триггер (с инверсными входами).
Временная диаграмма:
T⌐SQ=τ(задержка)
T⌐S⌐Q= 2τ
При появлении ⌐S= 0, сигнал поступает на верхний элемент и на триггер и устанавливаетQв 1 и лишь затем ⌐Qстановится равным 0.
Аналогично при появлении ⌐R= 0 вначале устанавливается ⌐Qв 1, а затемQв 0.
Рассмотрим второй триггер:
T (S ⌐Q) = T (R Q) = τ
T (S Q) = T (R ⌐Q) = 2 τ
Установочные входы в триггерах.
Функционально вход RиR0, а такжеSиS0аналогичны, однако в схемах наRSвходы заводят функции возбуждения аR0S0выводят наружу в качестве установочных, на которые перед началом функционирования автомата полают сигнал, устанавливающий автомат в состояниеS0.
Синхронные элементы памяти.
Синхронизация позволяет исключить влияние временных смещений входных сигналов триггера и позволяет обеспечить одновременность изменений выходных сигналов элементов памяти.
Требования на синхросигнал:
Предположим, что триггер Qнаходится в 0 и подаетсяJ=K= 1.
Триггер должен перейти в 1, однако если Jпоявится раньше чемK, при отсутствии синхросигнала, он установит триггер в 1.
Появление через ∆ сигнала K=1 установит 11 на входах и триггер сбросится.
Наличие синхросигнала позволяет триггеру реагировать только в момент синхросигнала, когда J=K=1 и в этом случае триггер перейдет 01 один раз.
Так как синхросигнал поступает на все триггеры одновременно, то все они реагируют и выдают сигнал на выходе одновременно.
Требования, предъявляемые к синхросигналу.
Синхросигнал должен появиться после входного сигнала
Синхросигнал должен заканчиваться раньше синхросигнала:
Синтез синхронного rs триггера.
В качестве основы используем асинхронные RSтриггеры:
Так как данный вид триггера получен на элементах «или - не», то и комбинационный узел реализуем на тех же самых элементах.
CD/Q |
00 |
01 |
11 |
10 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
получим:
CD/Q |
00 |
01 |
11 |
10 |
0 |
*0 |
*0 |
01 |
*0 |
1 |
0* |
0* |
0* |
10 |
|
|
|
------------С | |
|
|
------------D |
| |
|
* |
* |
0 |
* |
Q - |
0 |
0 |
0 |
1 |
|
|
|
------------С | |
|
|
------------D |
| |
|
0 |
0 |
1 |
0 |
Q - |
* |
* |
* |
0 |
R = C⌐D = ⌐(⌐C v D)
S = CD v ⌐(⌐C v ⌐D)
Условное обозначение:
Временная диаграмма:
В момент времени t0сигналR0непосредственно воздействует через установочные входы наRSтриггер.
В момент t1 появляется сигналR1 , однако триггер был в нуле и следовательно изменений не произошло.
В момент t2 появляется сигналS, который устанавливает ⌐Qв 0, а затемQв 1.
Повторный сигнал ⌐Sвt3 лишь подтверждаетQ= 1, а ⌐Q= 0.
В момент времени t4 появившийся сигналRсбрасывает триггер.
t(⌐СQ=1) = 3 τ
t(⌐СQ=0) = 2 τ
max (t(⌐СQ)) = 3 τ