ID: 1020

Название работы: Особенности синтеза цифрового автомата

Категория: Курсовая

Предметная область: Коммуникация, связь, радиоэлектроника и цифровые приборы

Описание: Таблица кодирования внутренних состояний входных и выходных переменных. Построение комбинационного устройства для формирования управляющих сигналов на входах блока памяти. Построение комбинационного устройства для формирования выходных сигналов автоматов. Минимизация функций алгебры–логики по картам Карно.

Язык: Русский

Дата добавления: 2013-01-06

Размер файла: 249.5 KB

Работу скачали: 39 чел.

Московский государственный университет путей сообщения
(МИИТ)

кафедра: «Автоматика и телемеханика на железнодорожном транспорте»

Курсовой проект

по дисциплине: «Теория дискретных устройств автоматики и телемеханики»

на тему: «Особенности синтеза цифрового автомата»

Выполнил:

Студент группы АТС–211                      Попов И.Л.        

Принял преподаватель Антонов А.А.

Москва 2011

Содержание:

1.  Задача синтеза цифрового автомата
2.  Таблица переходов и выходов
3.  Граф работы автомата
4.  Структурная схема автомата
5.  Таблица кодирования внутренних состояний входных и выходных переменных
6.  Таблица функционирования цифрового автомата
7.  Задание функций алгебры–логики картами Карно
8.  Минимизация функций алгебры–логики по картам Карно
9.  Построение комбинационного устройства для формирования управляющих сигналов на входах блока памяти
10.   Построение комбинационного устройства для формирования выходных сигналов автоматов

11 Спецификация элементов

Список использованной литературы

1.  

1.  Задача синтеза цифрового автомата

Синтез автомата начинается в 3 этапа:

1.  Задается словесное описание алгоритма работы автомата
2.  На основе словесного описания алгоритма работы автомата разрабатывается формализованное задание алгоритма работы автомата. Применяются две формы задания алгоритма работы автомата:
3.  В виде таблицы переходов и выходов
4.  В виде графа работы автомата
5.  На основе формализованного задания алгоритма работы автомата с помощью специальной методики осуществляется построение принципиальной схемы автомата. На основании этой методики представляется возможным разработать жесткий алгоритм проектирования принципиальной схемы автомата. Этот алгоритм позволяет создать систему автоматизированного проектирования цифрового автомата.

В курсовом проекте будет осуществлена разработка принципиальной схемы, включая все этапы синтеза после того, как будет задано формализованное представление работы автомата.

1.  
   Таблица переходов и выходов

На основании анализа словесного описания алгоритма работы автомата установлено:

1.  Автомат имеет восемь внутренних состояний. Обозначим эти состояния A0, A1, A2, A3, A4, A5, A6, A7.
   1.  На вход автомата поступает четыре набора входных сигналов. Обозначим эти наборы X0, X1, X2, X3.
   2.  На выходе автомата действуют четыре набора выходных сигналов. Обозначим эти наборы Y0, Y1, Y2, Y3.
   3.  Если автомат находится в состоянии A7 и на вход поступает набор сигналов X0, то автомат перейдет в состояние A1, а на выходе будет набор Y3.
   4.  На основании словесного описания алгоритма работы автомата определено, в какое состояние перейдет автомат из состояния A7 при поступлении на вход наборов сигналов X1, X2, X3 и определено, какие при этом будут наборы сигналов на выходе. Таким образом была заполнена первая строка таблицы переходов и выходов.
   5.  Рассмотренная процедура была применена для остальных семи внутренних состояний. В результате была получена таблица переходов и выходов автомата (таблица 2.1)

Таблица 2.1

At	Xt  Yt
		X0	X1	X2	X3
A5	A1, Y3	A0, Y0	A5, Y2	A2, Y1
A6	A2, Y2	A7, Y1	A4, Y1	A4, Y2
A4	A3, Y1	A6, Y2	A3, Y0	A6, Y3
A3	A4, Y0	A5, Y3	A2, Y3	A0, Y0
A2	A5, Y1	A6, Y3	A1, Y0	A1, Y3
A1	A6, Y2	A4, Y2	A0, Y1	A3, Y2
A0	A7, Y3	A3, Y1	A6, Y2	A5, Y1
A7	A0, Y3	A1, Y0	A7, Y3	A7, Y0

1.  
   Граф работы автомата

Для наглядности таблица переходов и выходов может быть представлена в виде графа. На чертеже указываются вершины, изображаемые кружочками, которые соответствуют внутренним состояниям автомата. Стрелками указывается, из какого состояния, в какое переходит автомат. Над стрелкой указывается набор сигналов, под действием которого осуществляется переход и набор сигналов на выходе автомата.

1.  
   Структурная схема автомата.

Цифровой автомат с памятью состоит из трех узлов:

Рис. 4. 1 JK – триггер

1.  Блок элементов памяти.
   Элемент памяти имеет два состояния, одно из которых условно называют «0», другое–«1». В качестве элементов памяти обычно используют триггеры.
   Триггер–это электронное устройство, которое скачкообразно может переходить из одного состояния в другое. Большое распространение получили JK – триггеры. Это устройство имеет два управляющих входа: J и K, вход синхронизации C и два выхода: Q и.

Если на выходе Q – «0», то триггер находится в состоянии «0», при этом на выходе  будет «1». Переключение триггера из одного состояния в другое происходит в момент подачи импульса синхронизации. В этот момент триггер переключается в состояние «0» или в состояние «1» в зависимости от того, какие сигналы действуют на управляющих входах. Внутренние состояния автомата в каждый момент состояния триггеров.

В проектируемом автомате в соответствии с полученной на основании словесного описания алгоритма работы автомата таблицей переходов и выходов содержится восемь внутренних состояний A0 – A7. чтобы задать восемь внутренних состояний необходимо иметь три триггера.

1.  Представляет собой комбинационное устройство (комбинационную схему) с помощью которого будут формироваться управляющие сигналы на входах элементов памяти. Эти сигналы должны обеспечить переключение триггеров в соответствии с таблицей переходов и выходов (в соответствии с графом работы автомата). Проектируемый автомат имеет четыре набора входных сигналов X0, X1, X2, X3. Чтобы задать эти четыре набора необходимо иметь две переменных x1 и x2. Переключение автомата (переход в новое состояние) зависит от того, какие сигналы поступают на вход автомата и какое внутреннее состояние имеет автомат в данный момент времени.
2.  Представляет собой комбинационную схему, с помощью которой формируются выходные сигналы. В проектируемом автомате имеется четыре набора выходных сигналов Y0, Y1, Y2, Y3. Для представления этих наборов достаточно иметь две логические переменные y1 и y2. Выходные сигналы формируются в зависимости от внутреннего состояния автомата, и от того, какие сигналы поступают на вход автомата. Такой автомат называют автоматом Мили. Если выходные сигналы формируются только под действием сигналов с элементов памяти, то автомат называется автоматом Мура. В нем будут отсутствовать цепи, отмеченные на рис. 4.2 звездочкой (*).

Рис. 4. 2 Структурная схема автомата

1.  
   Таблицы кодирования внутренних состояний, входных и выходных переменных автомата.

Для кодирования внутренних состояний автомата используется двоично-десятичный код, то есть номер состояния представляется в двоичной системе счисления.

Рассмотрим таблицу кодирования внутренних состояний (таблица 5.1):

Таблица 5.1

At	Qt
		Q3	Q2	Q1
A5	0	0	0
A6	0	0	1
A4	0	1	0
A3	0	1	1
A2	1	0	0
A1	1	0	1
A0	1	1	0
A7	1	1	1

В проектируемом автомате имеется четыре набора входных сигналов и для их представления достаточно двух переменных.

Таблица кодирования входных переменных (таблица 5.2):

Таблица 5.2

Xt	x2	x1
X0	0	0
X1	0	1
X2	1	0
X3	1	1

Проектируемый автомат имеет четыре набора выходных сигналов. Для их представления достаточно двух переменных

Таблица кодирования выходных переменных:

Таблица 5.2

Yt	y2	y1
Y0	0	0
Y1	0	1
Y2	1	0
Y3	1	1

В качестве элементов памяти Q1, Q2, Q3 принимаем JK – триггеры.

Таблица функционирования JK – триггеров (таблица 5.3):

Таблица 5.3

Qt → Qt+1	Jt	Kt
0 → 0	0	~
0 → 1	1	~
1 → 0	~	1
1 → 1	~	0

Если триггер в такте t находится в состоянии «0» и он должен остаться в такте t+1 в том же состоянии, то на J-вход нужно подать «0», а на K – любое значение («0» или «1»).

Если триггер в такте t находится в такте «0», и он должен переключится в такте t+1, то в такте t на J-вход нужно подать «1», а на K – любое значение.

1.  
   Таблица функционирования цифрового автомата.

В таблице функционирования приводятся все комбинации входных сигналов, которые могут действовать на узле 2 (комбинационная схема для формирования управляющих сигналов на входах триггеров).

На вход этой схемы поступает пять переменных (см. структурную схему): Q3, Q2, Q1, x1, x2. при пяти переменных может быть число наборов K=25=32 набора. Внесем эти наборы в таблицу функционирования цифрового автомата

Набор переменных Q3, Q2, Q1 характеризует внутреннее состояние автомата в такте t. Для каждого набора состояний триггеров по таблице кодирования внутренних состояний можно определить внутреннее состояние автомата. Например: набор Q3Q2Q1=000 в соответствии с таблицей кодирования внутренних состояний свидетельствует, что автомат находится в состоянии A7.

На вход поступает набор переменных x2x1=00, который в соответствии с таблицей кодирования входных сигналов обозначен как X0. Итак, в такте t автомат находится в состоянии A7 и на вход поступает набор сигналов X0. В соответствии с таблицей переходов и выходов находим, что автомат должен перейти в такте t+1 в состояние A1,Y3. В соответствии с таблицей кодирования внутренних состояний автомата состоянию A1 будет соответствовать набор Q3Q2Q1=001. Выходному набору Y3 соответствует набор переменных y2y1=11.

В соответствии с заполненной таблицей видим, что триггер Q3 должен переключиться из состояния «0» в такте t в состояние «0» в такте t+1. Триггер Q2 в такте t+1 должен остаться в состоянии «0». Триггер Q1 в такте t+1 должен переключиться в состояние «1».

Для того чтобы произошли указанные переключения триггеров, в такте t на управляющие входы триггеров должны быть поданы сигналы в соответствии с таблицей функционирования JK-триггеров.

1.  
   Задание функций алгебры – логики картами Карно

Карта Карно представляет собой таблицу, которая содержит столько клеток, сколько имеется наборов функций алгебры – логики. Адрес клетки определяется через аргументы функции.

В карте Карно можно выделить горизонтальные ряды или строки, и вертикальные ряды или столбцы. Поскольку у нас 32 клетки, то мы их расположим в виде 4 строк и 8 столбцов. Для нумерации строк будем использовать переменные x2, x1; для нумерации столбцов – Q3, Q2, Q1. Номера строк и столбцов будем представлять в двоичной системе исчисления.

Карно предложил нумеровать строки и столбцы не в двоично–десятичном коде, а в коде Грея. В этом случае карта приобретает важные свойства, позволяющие записывать логическое выражение в форме, содержащей минимальное число членов, каждый из которых содержит минимальное число переменных.

Алгоритм получения комбинации в коде Грея:

1.  Десятичное число записывается в двоичной системе исчисления
2.  Кодовая комбинация в коде Грея записывается по следующему правилу: «Если в кодовой комбинации двоично–десятичного кода слева от рассматриваемого разряда стоит 0, то в этом разряде в кодовой комбинации кода Грея значение будет таким же, как и в кодовой комбинации двоично–десятичного кода. Если в кодовой комбинации двоично–десятичного кода слева от рассматриваемого разряда стоит 1, то в кодовой комбинации кода Грея записывается инверсное значение по сравнению со значением в этом же разряде в двоично–десятичном коде.

Таблица получения кода Грея для входных переменных (таблица 7.1)

№ набора	Двоичный код		Код Грея
		x2	x1	x2	x1
0	0	0	0	0
1	0	1	0	1
2	1	0	1	1
3	1	1	1	0

Таблица получения кода Грея для внутренних состояний (таблица 7.2)

№ набора	Двоичный код			Код Грея
		Q3	Q2	Q1	Q3	Q2	Q1
0	0	0	0	0	0	0
1	0	0	1	0	0	1
2	0	1	0	0	1	1
3	0	1	1	0	1	0
4	1	0	0	1	1	0
5	1	0	1	1	1	1
6	1	1	0	1	0	1
7	1	1	1	1	0	0

Каждая клетка карты Карно соответствует набору переменных, который соответствует пересечению строки и столбца. В эту клетку карты Карно проставляется значение функции, соответствующее рассматриваемому набору переменных.

Карта Карно для J3 (таблица 7.3)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	1	1	0	0	~	~	~	~
01	1	1	0	0	~	~	~	~
11	1	0	1	0	~	~	~	~
10	0	0	1	0	~	~	~	~

Карта Карно для K3 (таблица 7.4)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	~	~	~	~	0	0	1	1
01	~	~	~	~	1	0	1	1
11	~	~	~	~	1	0	1	0
10	~	~	~	~	1	0	0	0

Карта Карно для J2 (таблица 7.5)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	0	0	~	~	~	~	0	0
01	1	1	~	~	~	~	1	0
11	0	1	~	~	~	~	1	0
10	0	1	~	~	~	~	1	0

Карта Карно для K2 (таблица 7.6)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	~	~	0	~	0	0	~	~
01	~	~	1	~	0	1	~	~
11	~	~	0	~	1	0	~	~
10	~	~	1	~	1	0	~	~

Карта Карно для J1 (таблица 7.7)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	1	~	~	1	1	~	~	1
01	0	~	~	1	1	~	~	0
11	0	~	~	1	0	~	~	0
10	0	~	~	1	1	~	~	0

Карта Карно для K1 (таблица 7.8)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	~	1	1	~	~	1	0	~
01	~	0	1	~	~	0	1	~
11	~	1	1	~	~	0	0	~
10	~	1	1	~	~	0	1	~

Карта Карно для y2 (таблица 7.9)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	1	1	0	0	1	1	1	0
01	0	0	1	1	0	0	1	1
11	0	1	0	1	0	0	1	1
10	1	0	1	0	1	1	0	0

Карта Карно для y1 (таблица 7.10)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	1	0	0	1	1	1	0	1
01	0	1	1	0	1	0	0	1
11	1	0	0	1	1	0	0	1
10	0	1	1	0	0	1	1	0

1.  Минимизация функций алгебры – логики по картам Карно

В карте Карно можно выделить две главные оси симметрии, которые делят карту на две части. В каждой половине можно выделить вспомогательную ось симметрии.

На основании карты Карно можно записать логическое выражение, которое будет содержать минимальное число членов и минимальное число переменных. Каждая клетка карты Карно соответствует набору пяти переменных. Наборы переменных, отличающиеся значением одной переменной, которая в один набор входит в прямом виде, а в другой – в инверсном могут склеиваться. В результате склеивания двух наборов получается импликанта.

Правила склеивания конситуент по карте Карно:

1.  Склеиваются конситуенты, расположенные рядом.
2.  Могут склеиваться конситуенты, расположенные симметрично относительно главных и вспомогательных осей карты Карно.
3.  Могут склеиваться конситуенты, число которых равно 2, 4, 8 и 16.

Исходные карты Карно в некоторых клетках содержат знак "~" (тильда), это означает, что соответствующая функция не полностью определена. При минимизации функция доопределяется, то есть вместо знака тильда (~) ставится 1 или 0. Выбор того или иного значения производится исходя из того, чтобы при объединении клеток можно было бы получить контур, в который входит максимально возможное число единиц.

Правила записи МДНФ функций алгебры – логики:

1.  Выбирается контур по карте Карно.
2.  Выбирается одна из переменных функции.
3.  Рассматривается значение этой переменной во всех клетках, входящих в контур.
4.  Если значение переменной во всех клетках контура одно и тоже, то это значение переменной будет входить в импликанту.
5.  Если значение переменной в одной из клеток контура изменяется по сравнению со значением соседней клетки, то эта переменная не входит в состав импликанты.

Минимизация МДНФ для J3 (таблица 8.1)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	1	1	0	0	~	~	~	~
01	1	1	0	0	~	~	~	~
11	1	0	1	0	~	~	~	~
10	0	0	1	0	~	~	~	~

J3 МДНФ=

                                       Минимизация МКНФ для K3 (таблица 8.2)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	~	~	~	~	0	0	1	1
01	~	~	~	~	1	0	1	1
11	~	~	~	~	1	0	1	0
10	~	~	~	~	1	0	0	0

К3 МКНФ=

Минимизация МДНФ J2 (таблица 8.3)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	0	0	~	~	~	~	0	0
01	1	1	~	~	~	~	1	0
11	0	1	~	~	~	~	1	0
10	0	1	~	~	~	~	1	0

J2 МДНФ=

Минимизация МКНФ K2 (таблица 8.4)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	~	~	0	~	0	0	~	~
01	~	~	1	~	0	1	~	~
11	~	~	0	~	1	0	~	~
10	~	~	1	~	1	0	~	~

К2 МКНФ

Минимизация МДНФ для J1 (таблица 8.5)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	0	~	~	1	1	~	~	1
01	0	~	~	0	1	~	~	0
11	0	~	~	0	1	~	~	0
10	1	~	~	1	0	~	~	0

J1 МДНФ=

Минимизация МКНФ для K1 (таблица 8.6)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	~	1	0	~	~	1	1	~
01	~	0	0	~	~	1	0	~
11	~	0	1	~	~	0	0	~
10	~	0	1	~	~	0	1	~

К1 МКНФ=

Минимизация МДНФ для y2 (таблица 8.13)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	1	1	0	0	1	1	1	0
01	0	0	1	1	0	0	1	1
11	0	1	0	1	0	0	1	1
10	1	0	1	0	1	1	0	0

y2 МДНФ

                                       Минимизация МДНФ для y1 (таблица 8.8)

Q3Q2Q1 x2x1	000	001	011	010	110	111	101	100
00	1	0	0	1	1	1	0	1
01	0	1	1	0	1	0	0	1
11	1	0	0	1	1	0	0	1
10	0	1	1	0	0	1	1	0

y1 МДНФ =

9 Построение комбинационного устройства для формирования управляющих сигналов на входах блока памяти

9.1 Построение схем на элементах И–НЕ

Исходной формой функции алгебры–логики является МДНФ. Это логическое выражение выражается через функцию И–НЕ. Для представления функции алгебры–логики в функциях И–НЕ необходимо осуществить двукратное инвертирование с использованием правила Шеннона.

9.2 Построение схем на элементах ИЛИ–НЕ

Исходной формой функции алгебры–логики является МКНФ. Это логическое выражение необходимо представить через функцию ИЛИ–НЕ. Для этого осуществляется двукратное инвертирование.

10. Построение комбинационного устройства для формирования выходных сигналов автоматов

Схема строится с использованием мультиплексоров.

Мультиплексор (коммутатор) представляет собой комбинационное устройство, имеющее k управляющих входов и n информационных входов,

где n = 2 k, один вход синхронизации и один выход.

Основное назначение мультиплексора – осуществлять коммутацию входных линий. При подаче на управляющие входы комбинаций переменных, которые могут быть представлены двоичным числом, происходит соединение информационного входа, десятичный номер которого соответствует двоичному коду переменных, подаваемых на управляющие входы.

Мультиплексор может быть использован для построения комбинационной схемы (для реализации ФАЛ). Если число переменных ФАЛ соответствует числу управляющих входов мультиплексора, то эти переменные подаются на управляющие входы мультиплексора, а на информационные входы подаются значения ФАЛ при соответствующих наборах переменных.

Если число переменных больше, чем число управляющих входов мультиплексора, то осуществляется разложение ФАЛ.

11. Спецификация элементов

Рис. 10. 1 Типы логических элементов

Спецификация элементов (таблица 12.1)

Обозначение в схеме	Тип элемента	ФАЛ	Кол–во корпусов	Число элементов в корпусе	Число входов элемента
DD1	К1ЛБ333	И–НЕ	1	4	2
DD2; DD3; DD4; DD5	КР1561ЛА9	И–НЕ	4	3	3
DD11	КР151ЛА1	И–НЕ	1	2	4
DD10; DD12	К131ЛА2	И-НЕ	2	1	8
DD14	К555ЛЕ1	ИЛИ–НЕ	1	4	2
DD6; DD8; DD9	КР1554ЛЕ1	ИЛИ–НЕ	3	3	3
DD7; DD15	КР1554ЛЕ9	ИЛИ–НЕ	2	1	4
DD13	К1ЛБ472	ИЛИ-НЕ	1	1	8

Список использованной литературы

1.  Антонов А.А. Курс лекций
2.  Сапожников В.В., Кравцов Ю.А. «Теория дискретных устройств железнодорожной автоматики»
3.  Справочник по интегральным элементам под редакцией Тарабрина