Автомат Милли. Теоретическая часть
 Скачать 0.78 Mb.
|
|
ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 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) построение структурной схемы автомата. Составление таблицы переходов и выходов выполняется по графу состояний автомата. По существу, таблица переходов и выходов является табличной формой представления графа. Кодирование состояний заключается в том, что каждому состоянию автомата (Qi) ставится в соответствие состояние отдельных элементов памяти (qi). Составление кодированной таблицы переходов и выходов означает замену обозначения состояний вида Qi их двоичными номерами. При этом обозначения выходных сигналов остаются без изменения. Выбор элементов памяти. При каноническом методе структурного синтеза в качестве элементов памяти используют элементарные автоматы Мура, обладающие полной системой переходов и выходов. Такими автоматами являются триггеры 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 (числу состояний). В качестве элементов используются триггеры; совокупности двоичных значений их выходов γ1, …, γN образуют двоичные векторы, кодирующие состояния. На основе векторов X (x1, …, xM) и Г (γ1, …, γN), поступивших на входы КС1 в момент t дискретного времени, последняя формирует сигналы возбуждения элементов памяти (τ1, …, τN), переводящие автомат в новое состояние в момент t+1. КС2 служит для формирования выходных сигналов на основе векторов X и Г (для автомата Мили). 2.3 Получение функций возбуждения и функции выхода Разрядность выходной шины – 1 (один выход). Для кодирования трех слов входного алфавита a, b, c необходимо r количество входов (разрядность входной шины):  . (2.1)В соответствии с заданным ГП (рис. 1.2) составлена таблица переходов и выходов – табл. 2.1. Таблица 2.1 - Таблица переходов и выходов
Кодирование состояний автомата заключается в сопоставлении каждому состоянию автомата состояний элементов памяти. Их количество определяется в зависимости от состояний автомата N = 4. Тогда количество элементов памяти составляет:  . (2.2)Пусть q1 – обозначение первого элемента памяти, q2 – обозначение второго элемента памяти. Тогда для состояний автомата: Q0:  = 00; Q1:  = 01; Q2:  = 10; Q3:  = 11.Таблица переходов и выходов в соответствии с принятым кодированием преобразуется в кодированную таблицу переходов (таблица 2.2): Таблица 2.2 - Кодированная таблица переходов и выходов.
Функции возбуждения элементов памяти строятся на основе таблицы переходов и таблицы истинности триггеров (в данном случае JK-триггеров), которые являются основой памяти конечного автомата. JK-триггер это триггер с двумя сигнальными и одним синхронным входами. Принцип действия JK-триггера аналогичен RSC-триггеру, но JK-триггеры не имеют запрещенных комбинаций. Характеристическая таблица JK-триггера представлена в табл. 2.3. Таблица 2.3 - Характеристическая таблица JK-триггера.
На основании таблицы переходов 2.2 и характеристической таблицы JK-триггера 2.3 получается таблица возбуждения JK-триггеров – табл. 2.4. Таблица 2.4 - Таблица возбуждения JK-триггеров.
Тогда функции возбуждения первого триггера q1:  ; (2.3)функции возбуждения второго триггера q2:  ; (2.4)функция выхода (по табл. 2.2):  . (2.5)2.4 Минимизация функций возбуждения и функции выхода Карты Карно для обоих триггеров представлены в табл. 2.5-2.8. Табл. 2.5 – Карта Карно J1 Табл. 2.6 - Карта Карно K1
Табл. 2.7 – Карта Карно J2 Табл. 2.8 - Карта Карно K2
Тогда по Картам Карно (табл. 2.5 – 2.8):  ;  ; (2.6) ;  . (2.7)Карта Карно для функции выхода представлена в таблице 2.9.
 . (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. Схема электрическая принципиальная синтезированного автомата представлена в приложении А, перечень элементов – в приложении Б. По положительному фронту импульса синхронизации С значения логических условий Х на входе автомата запоминаются на триггерах Тxi. Значения логических условий с выходов этих триггеров и текущее состояние автомата am используются для вычисления выходов У – микрокоманд, вырабатываемых автоматом на переходе из состояния am в состояние as. Дешифратор состояний 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). ПРИЛОДЖЕНИЕ А  ПРИЛОЖЕНИЕ Б  | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0
1
0
1
1
0
x1x2
1