Файл: Теоретическая часть.docx

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 3

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 4

1.1 Понятие автомата и разновидности абстрактных автоматов 4

1.2 Алгоритм структурного синтеза конечного автомата 5

1.3 Обзор программных средств используемых для составления схем электрических принципиальных 6

1.4 Анализ технического задания и постановка задачи 7

1.5 Выводы по главе 8

2 ПРАКТИЧЕСКАЯ ЧАСТЬ 9

2.1 Выбор и характеристика элементной базы 9

2.2 Функциональная схема синтезируемого структурного автомата 12

2.3 Получение функций возбуждения и функции выхода 13

2.4 Минимизация функций возбуждения и функции выхода 15

2.5 Разработка схемы электрической принципиальной 16

2.6 Выводы по главе

3 ТЕСТИРОВАНИЕ СИНТЕЗИРОВАННОГО АВТОМАТА 17

3.1 Анализ способов тестирования автоматов 17

3.2 Непосредственное тестирование синтезированного структурного автомата 17

3.3 Выводы по главе 19

ЗАКЛЮЧЕНИЕ 20

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ 21

СПИСОК ЛИТЕРАТУРЫ2 2

Приложение А. Схема электрическая принципиальная2 3

Приложение Б. Перечень элементов2 4
ВВЕДЕНИЕ

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1 Понятие автомата и разновидности абстрактных автоматов

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

Конечным автоматом называется автомат, если конечны множества его входных и выходных алфавитов, а также его состояний.

Существуют 2 основных класса дискретных автоматов: автоматы Мура и автоматы Милли. В автомате Мура выходной сигнал зависит только от внутреннего состояния автомата, а в автомате Милли – и от состояния входов.

Также в зависимости от момента изменения сигнала на выходе относительно момента изменения состояния, различают автоматы 1-го и 2-го рода: если выходной сигнал появляется раньше изменения состояния автомата, то такой автомат называется автоматом 1-го рода; если выходной сигнал появляется позже изменения состояния автомата, то такой автомат называется автоматом 2-го рода.



а) б) в) г)

Рис. 1.1 – Дискретные автоматы: а) - Мура 1-го рода; б) – Мура 2-го рода;

в) – Милли 1-го рода; г) – Милли 2-го рода.
1.2 Алгоритм структурного синтеза конечного автомата

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

Согласно этому методу структурный синтез автомата проводится в такой последовательности:

1) кодирование входных, выходных сигналов и состояний автомата;

2) выбор элементов памяти;

3) запись уравнений функций выходов и возбуждения автомата;

4) построение структурной схемы автомата.

Составление таблицы переходов и выходов выполняется по графу состояний автомата. По существу, таблица переходов и выходов является табличной формой представления графа.

Кодирование состояний заключается в том, что каждому состоянию автомата (Q_i) ставится в соответствие состояние отдельных элементов памяти (q_i).

Составление кодированной таблицы переходов и выходов означает замену обозначения состояний вида Q_i их двоичными номерами. При этом обозначения выходных сигналов остаются без изменения.

Выбор элементов памяти. При каноническом методе структурного синтеза в качестве элементов памяти используют элементарные автоматы Мура, обладающие полной системой переходов и выходов. Такими автоматами являются триггеры D, T, R-S, J-K.

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

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

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

1.4 Анализ технического задания и постановка задачи

Граф переходов заданного автомата Милли представлен на рисунке 1.2.



Рис. 1.2 – Граф переходов заданного автомата Милли.
Содержание технического задания приведено в пп. 1.4.1 – 1.4.5:

1.4.1 Выполнить структурный синтез абстрактного автомата Мили на JK-триггерах и логических элементах.

1.4.2 Схему построить на микросхемах серии К555.

1.4.3 Синтезированный структурный автомат должен работать в синхронном режиме.

1.4.5 Предусмотреть в синтезированном структурном автомате установку синтезированного устройства в начальное состояние (Q0).

В процессе синтеза заданного автомата Милли необходимо:

- построить таблицы переходов/выходов по заданному графу автомата;

- закодировать множество входов;

- закодировать множество выходов;

- закодировать множество состояний;

- построить кодированную таблицу переходов – выходов;

- получить функции возбуждения для каждого триггера и функцию выхода;

- минимизировать функции возбуждения и функцию выхода. Минимизация данных функций может быть выполнена с помощью карт Карно (если функция содержит до 4-х переменных) или методом Квайна-Мак-Класки (если функция содержит больше 4-х переменных);

- составить функциональную схему проектируемого автомата, при этом, необходимо выделить три блока: блока управления, блок установки состояний и блок формирования выходного сигнала;

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

- рассчитать количество корпусов в схеме электрической принципиальной;

- оптимизировать количество корпусов микросхем;

- выполнить тестирование синтезированного структурного автомата;

- оформить общую схему электрическую принципиальную согласно ГОСТ;

- составить перечень элементов согласно ГОСТ.
1.5 Выводы по главе

В соответствии с техническим заданием необходимо разработать конечный структурный дискретный автомат Милли с логикой, заданной ГП, на JK-триггерах микросхем серии К555.
2 ПРАКТИЧЕСКАЯ ЧАСТЬ
2.1 Выбор и характеристика элементной базы

В качестве элементов, реализующих заданный автомат использованы микросхемы серии К555.

В качестве JK-триггеров могут быть использованы микросхемы К555ТВ9. Микросхема представляет собой двойной JK-триггер. Содержит 138 интегральных элементов. УГО микросхемы представлено на рисунке 2.1



Рис. 2.1 - УГО микросхемы К555ТВ9 (двойной JK-триггер).
Таблица истинности данной микросхемы представлена на рисунке 2.2.



Рис. 2.2 - Таблица истинности микросхемы К555ТВ9

(двойной JK-триггер).

Технические характеристики микросхемы К555ТВ9:

- номинальное напряжение питания: 5В ±5%;

- выходное напряжение низкого уровня: ≤ 0,5 В;

- выходное напряжение высокого уровня: ≥ 2,7В;

- ток потребления: ≤ 6 мА;

- входной ток низкого уровня по выводам 2, 3, 11, 12: ≤ |-0,4| мА;

- входной ток низкого уровня по выводам 1, 4, 10, 13, 14, 15: ≤ |-0,8| мА;

- входной ток высокого уровня по выводам 2, 3, 11, 12: ≤ 0,02 мА;

- входной ток высокого уровня по выводам 4, 10, 14, 15: ≤ 0,06 мА;

- входной ток высокого уровня по выводам по выводам 1, 13: ≤ 0,08 мА;

- потребляемая мощность: 31,5 мВт.

Д ля реализации функция «И» применены микросхемы К555ЛИ1, К555ЛИ3. Микросхемы К555ЛИ1 представляют собой 4 элемента 2И, а микросхемы К555ЛИ3 содержат 3 элемента 3И. УГО микросхемы К555ЛИ3 представлено на рисунке 2.3.


а) б)

Рис. 2.3 - УГО микросхем: а) - К555ЛИ1 (4 «2И»); б) - К555ЛИ3 (3 «3И»).
Технические характеристики микросхемы К555ЛИ3:

- номинальное напряжение питания: 5 В ± 5%;

- выходное напряжение низкого уровня: ≤ 0,5 В;

- выходное напряжение высокого уровня: ≥ 2,7 В;

- ток потребления при низком уровне выходного напряжения: ≤ 6,6 мА;

- ток потребления при высоком уровне выходного напряжения: ≤ 3,6 мА;

- потребляемая мощность: 27 мВт.

Для инвертирования сигналов применены микросхемы К555ЛН1. Микросхемы представляют собой 6 логических элементов НЕ. Содержат 84 интегральных элемента. УГО микросхемы представлено на рисунке 2.4.



Рис. 2.4 - УГО микросхемы К555ЛН1 (6 «НЕ»).
Технические характеристики микросхемы К555ЛН1:

- номинальное напряжение питания: 5 В ± 5%;

- выходное напряжение низкого уровня: ≤ 0,5 В;

- выходное напряжение высокого уровня: ≥ 2,7 В;

- ток потребления при низком уровне выходного напряжения: ≤ 6,6 мА

- ток потребления при высоком уровне выходного напряжения: ≤ 2,4 мА

- потребляемая мощность: 23,63 мВт.

Для реализации функций «ИЛИ» применены микросхемы К555ЛЛ1. Микросхемы представляют собой 4 логических элемента 2ИЛИ. Содержат 88 интегральных элементов. УГО микросхемы представлено на рисунке 2.5.



Рис. 2.5 - УГО микросхемы К555ЛЛ1 (4 «2ИЛИ»).

2.2 Функциональная схема синтезируемого структурного автомата

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



Рис. 2.5 - Структурная схема синтезируемого автомата.
Автомат построен на двух комбинационных схемах – КС1 и КС2, и двоичных элементах памяти П, число которых равно N (числу состояний). В качестве элементов используются триггеры; совокупности двоичных значений их выходов γ₁, …, γ_N образуют двоичные векторы, кодирующие состояния. На основе векторов X (x₁, …, x_M) и Г (γ₁, …, γ_N), поступивших на входы КС1 в момент t дискретного времени, последняя формирует сигналы возбуждения элементов памяти (τ₁, …, τ_N), переводящие автомат в новое состояние в момент t+1. КС2 служит для формирования выходных сигналов на основе векторов X и Г (для автомата Мили).
2.3 Получение функций возбуждения и функции выхода

Разрядность выходной шины – 1 (один выход). Для кодирования трех слов входного алфавита a, b, c необходимо r количество входов (разрядность входной шины):

. (2.1)

В соответствии с заданным ГП (рис. 1.2) составлена таблица переходов и выходов – табл. 2.1.

Таблица 2.1 - Таблица переходов и выходов

Входы			Состояния и выходы
	x1	x2	Qt = Q0	Qt = Q1	Qt = Q2	Qt = Q3
a	0	0	Q1, 0	Q2, 1	Q2, 0	Q1, 0
b	0	1	Q2, 0	Q3, 0	Q3, 1	Q2, 0
c	1	0	Q3, 0	Q0, 1	Q0, 1	Q0, 1

Кодирование состояний автомата заключается в сопоставлении каждому состоянию автомата состояний элементов памяти. Их количество определяется в зависимости от состояний автомата N = 4. Тогда количество элементов памяти составляет:

. (2.2)

Пусть q₁ – обозначение первого элемента памяти, q₂ – обозначение второго элемента памяти. Тогда для состояний автомата:

Q0: = 00; Q1: = 01; Q2: = 10; Q3: = 11.

Таблица переходов и выходов в соответствии с принятым кодированием преобразуется в кодированную таблицу переходов (таблица 2.2):
Таблица 2.2 - Кодированная таблица переходов и выходов.

Входы			Состояния и выходы
	x1	x2	Qt = Q0	Qt = Q1	Qt = Q2	Qt = Q3
						q1q2
			00	01	10	11
a	0	0	01, 0	10, 1	10, 0	01, 0
b	0	1	10, 0	11, 0	11, 1	10, 0
c	1	0	11, 0	00, 1	00, 1	00, 1

Функции возбуждения элементов памяти строятся на основе таблицы переходов и таблицы истинности триггеров (в данном случае JK-триггеров), которые являются основой памяти конечного автомата.

JK-триггер это триггер с двумя сигнальными и одним синхронным входами. Принцип действия JK-триггера аналогичен RSC-триггеру, но JK-триггеры не имеют запрещенных комбинаций. Характеристическая таблица JK-триггера представлена в табл. 2.3.
Таблица 2.3 - Характеристическая таблица JK-триггера.

Вход		Состояния
J	K		Qt	Qt+1
0	*		0	0
1	*		0	1
*	1		1	0
*	0		1	1

На основании таблицы переходов 2.2 и характеристической таблицы JK-триггера 2.3 получается таблица возбуждения JK-триггеров – табл. 2.4.
Таблица 2.4 - Таблица возбуждения JK-триггеров.

Входы

Состояния и выходы

x1

x2

Qt = Q0 (00)

Qt = Q1 (01)

Qt = Q2 (10)

Qt = Q3 (11)

q1 =0

q2 =0

q1 =0

q2 =1

q1 = 1

q2 = 0

q1 = 1

q2 = 1

J1

K1

J2

K2

J1

K1

J2

K2

J1

K1

J2

K2

J1

K1

J2

K2

a

0

0

0

*

1

*

1

*

*

1

*

0

0

*

*

1

*

0

b

0

1

1

*

0

*

1

*

*

0

*

0

1

*

*

0

*

1

c

1

0

1

*

1

*

0

*

*

1

*

1

0

*

*

1

*

1

Тогда функции возбуждения первого триггера q₁:

; (2.3)
функции возбуждения второго триггера q₂:

; (2.4)

функция выхода (по табл. 2.2):

. (2.5)
2.4 Минимизация функций возбуждения и функции выхода

Карты Карно для обоих триггеров представлены в табл. 2.5-2.8.
Табл. 2.5 – Карта Карно J₁ Табл. 2.6 - Карта Карно K₁

q1q2 x1x2	00	01	11	10
00	0	1	0	0
01	1	1	0	0
11	0	0	0	0
10	1	0	0	0

q1q2 x1x2	00	01	11	10
00	0	0	1	0
01	0	0	0	0
11	0	0	0	0
10	0	0	1	1

Табл. 2.7 – Карта Карно J₂ Табл. 2.8 - Карта Карно K₂

q1q2 x1x2	00	01	11	10
00	0	1	0	0
01	0	0	1	0
11	0	0	0	0
10	0	1	1	0

q1q2 x1x2	00	01	11	10
00	1	0	0	0
01	0	0	0	1
11	0	0	0	0
10	1	0	0	0

Тогда по Картам Карно (табл. 2.5 – 2.8):

; ; (2.6)

; . (2.7)

Карта Карно для функции выхода представлена в таблице 2.9.

q1q2 x1x2	00	01	11	10
00	0	1	0	0
01	0	0	0	1
11	0	0	0	0
10	0	1	1	1

Табл. 2.9 – Карта Карно y
. (2.8)
2.5 Разработка схемы электрической принципиальной

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

В соответствии с (2.6), для формирования функции возбуждения 1-го триггера необходимо 3 элемента «ИЛИ» и 11 элементов «И».

В соответствии с (2.7), для формирования функции возбуждения 2-го триггера необходимо 3 элемента «ИЛИ» и 11 элементов «И».

В микросхемах К555ЛИ3 содержится 3 элемента «3И», а в микросхемах К555ЛИ1 – 4 элемента «2И».Таким образом, необходимо 3 микросхемы К555ЛИ3, 3 микросхемы К555ЛИ1 и 3 микросхемы К555ЛЛ1.

Схема электрическая принципиальная синтезированного автомата представлена в приложении А, перечень элементов – в приложении Б.

По положительному фронту импульса синхронизации С значения логических условий Х на входе автомата запоминаются на триггерах Тx_i. Значения логических условий с выходов этих триггеров и текущее состояние автомата a_m используются для вычисления выходов У – микрокоманд, вырабатываемых автоматом на переходе из состояния a_m в состояние a_s. Дешифратор состояний DC имеет вход разрешения V: при V=1 дешифратор выдает на одном из своих выходов значение «1», при V = 0 – на всех выходах DC логический «0». Это означает, что при С = 0 (а значит и V = 0), все выходные сигналы автомата У равны нулю. Автомат вырабатывает микрокоманды только при С = 1.
2.6 Выводы по главе

На основе заданного графа состояний автомата получены таблицы переходов, состояний и выходов. Поучены функции возбуждения JK-триггеров в соответствии с таблицей переходов, а также функция выхода. На основе карт Карно произведена минимизация указанных функций. Составлена схема электрическая принципиальная и перечень элементов.

3 ТЕСТИРОВАНИЕ СИНТЕЗИРОВАННОГО АВТОМАТА
3.1 Анализ способов тестирования автоматов

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

Проверку работоспособности автомата произведена моделированием.
3.2 Непосредственное тестирование синтезированного структурного автомата

Для проверки работоспособности синтезированного дискретного автомата была собрана его схема в пакете NI Multisim. Общий вид представлен на рисунке 3.1.



Рис. 3.1 – Собранная схема синтезированного автомата в пакете NI Multisim.

Схема тестирования соответствует схеме электрической принципиальной с той лишь разницей, что для удобства применены элементы 4И и 3ИЛИ. В схеме тестирования, также как и на схеме принципиальной, присутствуют 2 шины – шина возбуждения триггеров и шина входов. Входы x1 и x2 имитируются переключателями, подключенными к источнику постоянного напряжения. Для индикации состояния выхода автомата y а также текущих состояний q1, q2 в схеме подключен индикаторы.

Работа автомата при подаче1-го тактового импульса – переход из Q0 в состояние Q1 представлено на рисунке 3.2.



Рис. 3.2 – Состояние автомата «Q1».
Из рисунка видно, что горит индикатор q2 – достигнуто состояние «Q1», индикатор y (выход автомата) – не активен.

Работа остальных состояний автомата тестировалась аналогично, результат – успешно.
3.3 Выводы по главе

В главе представлено моделирование работы синтезированного автомата в пакете NI Multisim. Результаты проверки успешные.

ЗАКЛЮЧЕНИЕ
В работе синтезирован структурный конечный автомат Милли на основании заданного графа переходов. Автомат реализован на JK-триггерах. Составлены его функциональная схема, таблицы переходов и выходов, таблицы возбуждения JK-триггеров. Получены функции возбуждения и выходов, с помощью карт Карно произведена их минимизация.

На основании синтезированных и минимизированных функции возбуждения и выходов составлена структурная схема заданного автомата на элементах логики – на JK-триггерах и на элементах «И-НЕ» с последующим воплощением на микросхемах серии К555.

Правильность синтезированного автомата подтверждена моделированием его работы его состояний.

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ
КС - комбинационные схемы (автоматы, выходы которых зависят только от входов и не зависят от состояний автомата);

БФ - булевая функция;

ТИ - таблица истинности;

ЭЗ - элементы задержки (регистры);

ФЭЗ - функциональные элементы задержки (таймеры);

УА - управляющий автомат;

СБФ - система булевых функций;

АБВП - автоматы без выходного преобразователя;

ГП – графы переходов;

ГАС – графо-аналитическая схема;

КТПВ – кодированная таблица переходов и выходов;

БФП – блок формирования переходов;

БФК – блок формирования команд.

СПИСОК ЛИТЕРАТУРЫ
1. Петров И.В. Программируемые контроллеры. Стандартные языки и приемы прикладного проектирования / Под. ред. проф. В.П. Дьяконова. – М.: СОЛОН-Пресс, 2004. – 256 с.: ил. – (Серия «Библиотека инженера»).

2. Шило В.Л. Популярные цифровые микросхемы: Справочник. – М.: Радио и связь, 1987. – 352 с.: ил. – (Массовая радиобиблиотека. Вып. 1111).

ПРИЛОДЖЕНИЕ А