Устройство синхронизации сигналов
Формализация описания конечного автомата (граф, таблицы переходов и выходов). Формирование функций выходов и функций возбуждения памяти автомата. Минимизация функций выходов и функций возбуждения памяти автомата, отображение результатов на картах Карно.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 01.01.2013 |
| Размер файла | 112,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
1. Анализ технического задания
Конечный автомат должен осуществлять синхронизацию информационных импульсов, поступающих в произвольные моменты времени, с ближайшим фронтом тактового импульса, начинающимся после поступления фронта информационного импульса. Длительность формируемого синхронизированного импульса равна периоду следования тактовых импульсов.
Максимальная длительность информационного импульса не ограничена.
Временная диаграмма работы автомата
X = {X0, X1, X2, X3}
|
x1 |
x2 |
||
|
X0 |
0 |
0 |
|
|
X1 |
0 |
1 |
|
|
X2 |
1 |
0 |
|
|
X3 |
1 |
1 |
Y = {Y0, Y1}
Y0 = 0, Y1 = 1
2. Формализация описания конечного автомата
Граф автомата
На основе построенного графа автомата получаем его таблицы переходов и выходов:
Таблица переходов автомата
|
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
||
|
X0 |
q0 |
q2 |
q2 |
q4 |
q4 |
q0 |
|
|
X1 |
q0 |
q1 |
q3 |
q3 |
q0 |
q0 |
|
|
X2 |
q2 |
q2 |
q2 |
q4 |
q4 |
q5 |
|
|
X3 |
q1 |
q1 |
q3 |
q3 |
q5 |
q5 |
Таблица выходов автомата
|
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
||
|
X0 |
Y0 |
Y0 |
Y0 |
Y1 |
Y1 |
Y0 |
|
|
X1 |
Y0 |
Y0 |
Y1 |
Y1 |
Y0 |
Y0 |
|
|
X2 |
Y0 |
Y0 |
Y0 |
Y1 |
Y1 |
Y0 |
|
|
X3 |
Y0 |
Y0 |
Y1 |
Y1 |
Y0 |
Y0 |
3. Минимизация памяти абстрактного автомата
Проведем минимизацию памяти конечного автомата:
Первый шаг:
р1= {B1, B2, B3, B4}
B1 = {q0, q1, q5}
B2 = {q2}
B3 = {q3}
B4 = {q4}
По таблице переходов строим таблицу разбиения р1 состояний автомата:
Разбиение р1 состояний автомата
|
B1 |
B2 |
B3 |
B4 |
||||
|
q0 |
q1 |
q5 |
q2 |
q3 |
q4 |
||
|
X0 |
B1 |
B1 |
B1 |
B3 |
B3 |
B1 |
|
|
X1 |
B1 |
B2 |
B1 |
B2 |
B1 |
B4 |
|
|
X2 |
B1 |
B1 |
B1 |
B3 |
B3 |
B1 |
|
|
X3 |
B2 |
B2 |
B1 |
B2 |
B4 |
B4 |
Второй шаг: р2= {C1, C2, C3, C4, C5, C6}
C1 = {q0}
C2 = {q1}
C3 = {q5}
C4 = {q2}
C5 = {q3}
C6 = {q4}
Поскольку число классов 2-эквивалентных состояний оказалось равно числу состояний автомата, то минимизация невозможна. В дальнейших расчетах будем пользоваться первоначальными таблицами переходов и выходов.
4. Выбор способа противогоночного кодирования
Существует две группы способов противогоночного кодирования:
1. Методы, позволяющие устранить все состязания. Используется «соседнее кодирование», когда всем соседним внутренним состояниям приписывают соседние кодовые комбинации, отличающиеся значением только 1 разряда. В случае использования таких методов может уменьшиться быстродействие, но зато устраняются все состязания.
2. Методы, устраняющие только критические состязания (состязания при которых в дальнейшей работе автомат не переходит из промежуточных состояний в состояние, предусмотренное алгоритмом функционирования)
Для упрощения схемы и увеличения быстродействия устраним только критические состязания.
Противогоночное кодирование осуществляется путем развязывания пар переходов.
Две пары двоичных наборов длины L - (б, в) и (г, д) называются развязанными, если i-ый разряд кода (1 ? i ? L) принимает одно значение на паре (б, в) и противоположное на паре (г, д).
5. Кодирование состояний автомата с устранением критических состязаний
Для исключения гонок в автомате пары состояний должны быть развязаны в каждом из массивов переходов, осуществляемых под действием одного и того же входного сигнала. Сформируем соответствующие массивы переходов:
Массивы переходов автомата
|
М0(по X0) |
М1(по X1) |
М2(по X2) |
М3(по X3) |
|
|
(q0, q0) (q1, q2) (q2, q2) (q3, q4) (q4, q4) (q5, q0) |
(q0, q0) (q1, q1) (q2, q3) (q3, q3) (q4, q0) (q5, q0) |
(q0, q2) (q1, q2) (q2, q2) (q3, q4) (q4, q4) (q5, q5) |
(q0, q1) (q1, q1) (q2, q3) (q3, q3) (q4, q5) (q5, q5) |
Для пар состояний, имеющих одинаковое состояние , не требуется развязывание.
Пары переходов автомата, подлежащие развязыванию
|
М0(по X0) |
М1(по X1) |
М2(по X2) |
М3(по X3) |
|
|
(q1, q2), (q3, q4)
(q1, q2), (q5, q0)
(q3, q4), (q5, q0)
|
(q1, q1), (q4, q0)
(q2, q3), (q4, q0) (q2, q3), (q5, q0)
|
(q0, q2), (q3, q4)
(q0, q2), (q5, q5)
|
(q0, q1), (q2, q3)
(q0, q1), (q4, q5)
|
Проведем сокращение таблицы пар переходов, подлежащих развязыванию:
Сокращенная таблица пар переходов автомата, подлежащих развязыванию
|
М0(по X0) |
М1(по X1) |
М2(по X2) |
М3(по X3) |
|
|
(q1, q2), (q3, q4) (q1, q2), (q5, q0) (q3, q4), (q5, q0) |
(q1, q1), (q4, q0) (q2, q3), (q4, q0) (q2, q3), (q5, q0) |
(q0, q2), (q3, q4) (q0, q2), (q5, q5) |
(q0, q1), (q2, q3) (q0, q1), (q4, q5) (q2, q3), (q4, q5) |
Развязывание пар переходов:
1. (q1, q2), (q3, q4) - по ф1 2. (q1, q2), (q5, q0) - по ф1 3. (q3, q4), (q5, q0) - по ф2
|
ф1 |
|||
|
q0 |
- |
||
|
q1 |
0 |
||
|
q2 |
0 |
||
|
q3 |
1 |
||
|
q4 |
1 |
||
|
q5 |
- |
||
|
ф1 |
|||
|
q0 |
1 |
||
|
q1 |
0 |
||
|
q2 |
0 |
||
|
q3 |
1 |
||
|
q4 |
1 |
||
|
q5 |
1 |
||
|
ф1 |
ф2 |
||
|
q0 |
1 |
1 |
|
|
q1 |
0 |
- |
|
|
q2 |
0 |
- |
|
|
q3 |
1 |
0 |
|
|
q4 |
1 |
0 |
|
|
q5 |
1 |
1 |
4. (q1, q1), (q4, q0) - по ф1
5. (q2, q3), (q4, q0) - по ф3 6. (q2, q3), (q5, q0) - по ф3
|
ф1 |
ф2 |
ф3 |
||
|
q0 |
1 |
1 |
1 |
|
|
q1 |
0 |
- |
- |
|
|
q2 |
0 |
- |
0 |
|
|
q3 |
1 |
0 |
0 |
|
|
q4 |
1 |
0 |
1 |
|
|
q5 |
1 |
1 |
- |
|
|
ф1 |
ф2 |
ф3 |
||
|
q0 |
1 |
1 |
1 |
|
|
q1 |
0 |
- |
- |
|
|
q2 |
0 |
- |
0 |
|
|
q3 |
1 |
0 |
0 |
|
|
q4 |
1 |
0 |
1 |
|
|
q5 |
1 |
1 |
1 |
7. (q0, q2), (q3, q4) - по ф2 8. (q0, q2), (q5, q5) - по ф4
|
ф1 |
ф2 |
ф3 |
|||
|
q0 |
1 |
1 |
1 |
||
|
q1 |
0 |
- |
- |
||
|
q2 |
0 |
1 |
0 |
||
|
q3 |
1 |
0 |
0 |
||
|
q4 |
1 |
0 |
1 |
||
|
q5 |
1 |
1 |
1 |
||
|
ф1 |
ф2 |
ф3 |
ф4 |
||
|
q0 |
1 |
1 |
1 |
0 |
|
|
q1 |
0 |
- |
- |
- |
|
|
q2 |
0 |
1 |
0 |
0 |
|
|
q3 |
1 |
0 |
0 |
- |
|
|
q4 |
1 |
0 |
1 |
- |
|
|
q5 |
1 |
1 |
1 |
1 |
9. (q0, q1), (q2, q3) - по ф3 10. (q0, q1), (q4, q5) - по ф4
|
ф1 |
ф2 |
ф3 |
ф4 |
||
|
q0 |
1 |
1 |
1 |
0 |
|
|
q1 |
0 |
- |
1 |
- |
|
|
q2 |
0 |
1 |
0 |
0 |
|
|
q3 |
1 |
0 |
0 |
- |
|
|
q4 |
1 |
0 |
1 |
- |
|
|
q5 |
1 |
1 |
1 |
1 |
|
|
ф1 |
ф2 |
ф3 |
ф4 |
||
|
q0 |
1 |
1 |
1 |
0 |
|
|
q1 |
0 |
- |
1 |
0 |
|
|
q2 |
0 |
1 |
0 |
0 |
|
|
q3 |
1 |
0 |
0 |
- |
|
|
q4 |
1 |
0 |
1 |
1 |
|
|
q5 |
1 |
1 |
1 |
1 |
11. (q2, q3), (q4, q5) - по ф3
Все пары переходов развязаны. Минимизизируем число элементов памяти.
Исключаем ф1 - не развязанными оказываются пары переходов (q1, q2), (q3, q4); (q1, q2), (q5, q0); (q1, q1), (q4, q0). Введем ф5 для развязывания этих пар:
|
ф2 |
ф3 |
ф4 |
ф5 |
||
|
q0 |
1 |
1 |
0 |
1 |
|
|
q1 |
- |
1 |
0 |
0 |
|
|
q2 |
1 |
0 |
0 |
0 |
|
|
q3 |
0 |
0 |
1 |
- |
|
|
q4 |
0 |
1 |
1 |
1 |
|
|
q5 |
1 |
1 |
1 |
1 |
Аналогично исключаем ф2 и вводим ф6
|
ф3 |
ф4 |
ф5 |
ф6 |
||
|
q0 |
1 |
0 |
1 |
1 |
|
|
q1 |
1 |
0 |
0 |
- |
|
|
q2 |
0 |
0 |
0 |
- |
|
|
q3 |
0 |
1 |
- |
0 |
|
|
q4 |
1 |
1 |
1 |
0 |
|
|
q5 |
1 |
1 |
1 |
1 |
и исключаем ф3. Пары, развязанные по ф3, развяжем по ф5: (q2, q3), (q4, q0); (q2, q3), (q5, q0); (q2, q3), (q4, q5) и по ф6: (q0, q1), (q2, q3):
|
ф4 |
ф5 |
ф6 |
||
|
q0 |
0 |
1 |
1 |
|
|
q1 |
0 |
0 |
1 |
|
|
q2 |
0 |
0 |
0 |
|
|
q3 |
1 |
0 |
0 |
|
|
q4 |
1 |
1 |
0 |
|
|
q5 |
1 |
1 |
1 |
В результате проведенной минимизации получена таблица кодирования состояний автомата, содержащая 3 переменных ф4, ф5, ф6. Для представления шести состояний требуется 3 элемента памяти, поэтому процесс минимизации окончен. Проведем перенумерацию переменных фi следующим образом: {ф4, ф5, ф6} {ф1, ф2, ф3}. В результате получаем таблицу, являющуюся результирующей таблицей кодирования состояний автомата:
|
ф1 |
ф2 |
ф3 |
||
|
q0 |
0 |
1 |
1 |
|
|
q1 |
0 |
0 |
1 |
|
|
q2 |
0 |
0 |
0 |
|
|
q3 |
1 |
0 |
0 |
|
|
q4 |
1 |
1 |
0 |
|
|
q5 |
1 |
1 |
1 |
Проведем проверку правильности противогоночного кодирования состояний автомата с устранением критических состязаний:
Значения разрядов кодов состояний, обеспечивающих развязывание пар переходов автомата
|
М0(по X0) |
Значения разрядов кодов состояний |
М1(по X1) |
Значения разрядов кодов состояний |
М2(по X2) |
Значения разрядов кодов состояний |
М3(по X3) |
Значения разрядов кодов состояний |
|
|
(q0, q0), (q1, q1) |
ф2 - 1100 |
(q0, q0), (q1, q1) |
ф2 - 1100 |
(q0, q2), (q3, q4) |
ф1 - 0011 |
(q0, q1), (q2, q3) |
ф3 - 0011 |
|
|
(q0, q0), (q2, q2) |
ф2,ф3 -1100 |
(q0, q0), (q2, q3) |
ф2,ф3 -1100 |
(q0, q2), (q4, q4) |
ф1 - 0011 |
(q0, q1), (q3, q3) |
ф1 - 0011 ф3 - 1100 |
|
|
(q0, q0), (q3, q4) |
ф1 - 0011 ф3 - 1100 |
(q0, q0), (q3, q3) |
ф1,ф2 -0011 ф3 -1100 |
(q0, q2), (q5, q5) |
ф1 - 0011 |
(q0, q1), (q4, q5) |
ф1 - 0011 |
|
|
(q0, q0), (q4, q4) |
ф1 - 0011 ф3 - 1100 |
(q1, q1), (q2, q3) |
ф3 - 1100 |
(q1, q2), (q3, q4) |
ф1 - 0011 |
(q0, q1), (q5, q5) |
ф1 - 0011 |
|
|
(q1, q2), (q3, q4) |
ф1 - 0011 |
(q1, q1), (q3, q3) |
ф1 - 0011 ф3 - 1100 |
(q1, q2), (q4, q4) |
ф1,ф2 -0011 |
(q1, q1), (q2, q3) |
ф3 - 1100 |
|
|
(q1, q2), (q4, q4) |
ф1,ф2 -0011 |
(q1, q1), (q4, q0) |
ф2 - 0011 |
(q1, q2), (q5, q5) |
ф1,ф2 -0011 |
(q1, q1), (q3, q3) |
ф1 - 0011 ф3 - 1100 |
|
|
(q1, q2), (q5, q0) |
ф2 - 0011 |
(q1, q1), (q5, q0) |
ф2 - 0011 |
(q2, q2), (q3, q4) |
ф1 - 0011 |
(q1, q1), (q4, q5) |
ф1,ф2 -0011 |
|
|
(q2, q2), (q3, q4) |
ф1 - 0011 |
(q2, q3), (q4, q0) |
ф2 - 0011 |
(q2, q2), (q4, q4) |
ф1,ф2 -0011 |
(q1, q1), (q5, q5) |
ф1,ф2 -0011 |
|
|
(q2, q2), (q4, q4) |
ф1,ф2 -0011 |
(q2, q3), (q5, q0) |
ф2,ф3 -0011 |
(q2, q2), (q5, q5) |
ф1,ф2,ф3 -0011 |
(q2, q3), (q4, q5) |
ф2 - 0011 |
|
|
(q2, q2), (q5, q0) |
ф2,ф3 -0011 |
(q3, q3), (q4, q0) |
ф2 - 0011 |
(q3, q4), q5, q5) |
ф3 - 0011 |
(q2, q3), (q5, q5) |
ф2,ф3 -0011 |
|
|
(q3, q4), (q5, q0) |
ф3 - 0011 |
(q3, q3), (q5, q0) |
ф2,ф3 -0011 |
(q4, q4), (q5, q5) |
ф3 - 0011 |
(q3, q3), (q4, q5) |
ф2 - 0011 |
|
|
(q4, q4), (q5, q0) |
ф3 - 0011 |
(q0, q1), (q2, q3) |
ф3 - 0011 |
(q3, q3), (q5, q5) |
ф2,ф3 -0011 |
Из приведенной таблицы видно, что все пары состояний автомата, подлежащие развязыванию для устранения критических состязаний, развязаны.
Составим таблицы переходов и выходов структурного автомата.
Таблица переходов структурного автомата
|
X\ q |
011 |
001 |
000 |
100 |
110 |
111 |
|
|
00 |
011 |
000 |
000 |
110 |
110 |
011 |
|
|
01 |
011 |
001 |
100 |
100 |
011 |
011 |
|
|
10 |
000 |
000 |
000 |
110 |
110 |
111 |
|
|
11 |
001 |
001 |
100 |
100 |
111 |
111 |
автомат карно память карта
Таблица выходов структурного автомата
|
X\ q |
011 |
001 |
000 |
100 |
110 |
111 |
|
|
00 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
01 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
10 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
11 |
0 |
0 |
1 |
1 |
0 |
0 |
Размещено на Allbest.ru
...Подобные документы
Построение таблицы поведения автомата и соответствующего графа. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции "пси". Определение булевой функции для реализации функции "фи". Составление логической схемы автомата.
курсовая работа [96,7 K], добавлен 27.04.2011Составление таблицы истинности. Получение уравнений функций алгебры логики для заданных выходов. Реализация схемы логического автомата на электромагнитных реле РП-23, на диодной матрице. Реализация структурной схемы логического автомата, на микросхемах.
курсовая работа [862,4 K], добавлен 12.12.2012Построение графа и таблицы поведения автомата. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции y. Определение булевой функции для реализации функции j. Составление логической схемы автомата, кодирование данных.
курсовая работа [200,4 K], добавлен 27.04.2011Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Нахождение пределов функций. Определение значения производных данных функций в заданной точке. Проведение исследования функций с указанием области определения и точек разрыва, экстремумов и асимптот. Построение графиков функций по полученным данным.
контрольная работа [157,0 K], добавлен 11.03.2015Основные свойства функций, для которых существуют пределы. Понятие бесконечно малых величин и их суммы. Предел алгебраической суммы, разности и произведения конечного числа функций. Предел частного двух функций. Нахождение предела сложной функции.
презентация [83,4 K], добавлен 21.09.2013Обзор таблицы производных элементарных функций. Понятие промежуточного аргумента. Правила дифференцирования сложных функций. Способ изображения траектории точки в виде изменения ее проекций по осям. Дифференцирование параметрически заданной функции.
контрольная работа [238,1 K], добавлен 11.08.2009Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Вычисление пределов гиперболических функций. Дифференцирование сложной функции. Разложение гиперболических функций по формуле Тейлора. Свойства неопределенного интеграла, интегрирование функций. Гиперболические функции комплексного переменного.
дипломная работа [2,8 M], добавлен 11.01.2011Запрещенные комбинации выходных сигналов. Методика получения минимальных ДНФ неполностью определенных переключательных функций. Импликантная матрица. Алгоритм получения минимальных конъюнктивных форм. Выходные сигналы на запрещенных комбинациях.
контрольная работа [54,9 K], добавлен 09.10.2008Частные случаи производной логарифмической функции. Производная показательной функции, экспоненты, степенной, тригонометрических функций. Производная синуса, косинуса, тангенса, котангенса, арксинуса. Производные обратных тригонометрических функций.
презентация [332,2 K], добавлен 21.09.2013Определение и простейшие свойства измеримой функции. Дальнейшие свойства измеримых функций. Последовательности измеримых функций. Сходимость по мере. Структура измеримых функций. теоремы о приближении измеримых функций.
курсовая работа [86,9 K], добавлен 28.05.2007Условия возникновения и особенности вычисления функций Матье, характеристика дифференциального уравнения Матье. Алгоритм решения задачи и алгоритмы вычисления радиальных функций эллиптического цилиндра. Определение точности результатов вычисления.
научная работа [73,8 K], добавлен 02.05.2011Производные функций, заданных в явном и неявном виде. Исследование функций методами дифференциального исчисления. Точки перегиба и экстремума, градиент функции. Объем тела, образованного вращением фигуры и ограниченной графиками функций, вокруг оси.
контрольная работа [77,3 K], добавлен 11.07.2013Вычисление пределов функций, производных функций с построением графика. Вычисление определенных интегралов, площади фигуры, ограниченной графиками функций. Общее решение дифференциального уравнения, его частные решения. Исследование сходимости ряда.
контрольная работа [356,6 K], добавлен 17.07.2008Понятие числовых функций с областью определения, аргумент и области их значений, свойства и графическое выражение. Определение четных и нечетных функций, периодичность тригонометрических функций. Свойства, используемые при построении их графиков.
презентация [22,9 K], добавлен 13.12.2011Аппроксимация функций методом наименьших квадратов. Описание программного средства: спецификация переменных, процедур и функций, схемы алгоритмов. Реализация расчетов в системе Mathcad. Порядок составления графика в данной среде программирования.
курсовая работа [808,9 K], добавлен 09.05.2011Нахождение экстремумов функций методом множителей Лагранжа. Выражение расширенной целевой функции. Схема алгоритма численного решения задачи методом штрафных функций в сочетании с методом безусловной минимизации. Построение линий ограничений.
курсовая работа [259,9 K], добавлен 04.05.2011Декартова система координат. Построение композиции отображений. Проверка полноты системы функций. Построение логической схемы однотактного триггера на заданном элементе памяти с использованием канонического метода структурного синтеза конечных автоматов.
контрольная работа [225,5 K], добавлен 18.02.2015Система линейных неравенств, определяющих треугольник. Доказательство базиса четырехмерного пространства и определение координат вектора. Исследование функций на периодичность, монотонность и экстремум. Площади фигуры, ограниченной графиками функций.
контрольная работа [174,5 K], добавлен 26.01.2010
