Синтез синхронного управляющего автомата

 

 

 

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ

по дисциплине «Теория автоматов»

 

Тема проекта: "Синтез синхронного  управляющего автомата"

 

Студент группы

                                                       фамилия, имя, отчество

 

Номер варианта:

Технические условия: тип управляющего автомата – Мура; способ кодирования внутренних состояний автомата – первый эффективный способ структурного кодирования; тип триггерных схем – комбинированные синхронные двухтактные  D-триггеры; элементная база логического преобразователя – двухуровневая программируемая логическая матрица.

Содержание и объем проекта (графические  работы, расчеты и прочее): расчетно - пояснительная записка –21 страниц формата А4 (поясняющие текст, рисунки, расчеты, таблицы и т.п.); схема электрическая функциональная УА.

 

Сроки выполнения этапов: 1й-этап - _________;  2й-этап - ___________

Срок защиты курсового проекта: с ____________по _______________

 

Задание принял студент              ____________________                                                      Подпись, дата           Инициалы, фамилия

Руководитель                                ____________________

                                                         Подпись, дата             Инициалы, фамилия


 

ЗАМЕЧАНИЯ РУКОВОДИТЕЛЯ

 

Содержание

 

Введение

Одной из дисциплин для специальности  ”Вычислительные машины, комплексы, системы и сети” является "Теория автоматов", обязательным минимумом  содержания которой для дипломированного специалиста является [1]:

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

В качестве объекта проектирования выбран гипотетический синхронный управляющий  автомат (УА), реализующий под воздействием совокупности входных сигналов некоторый  алгоритм функционирования. Алгоритм функционирования задается в виде граф - схемы алгоритма (ГСА), который, по сути, однозначно определяет  закон одновременного формирования комбинации выходных сигналов УА из ограниченной их совокупности.

Согласно ГОСТ 22487-77 под проектированием  понимается процесс последовательного составления и детализации взаимосогласованных модельных описаний еще не существующего материального объекта. Таким образом, в результате проектирования объект проектирования еще не материализуется, а создается его прообраз на другой материальной основе (чертежи, схемы, текстовые документы и т.п.). Причем этот прообраз может быть необходим для дальнейшего проектирования, а может быть уже достаточным для материализации объекта проектирования.

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

  

 

1 Общие принципы построения и реализации синхронных управляющих автоматов (УА)

    1. Обобщенная структура и принцип функционирования синхронных управляющих автоматов

 

     Управляющий автомат (УА) генерирует последовательность управляющих сигналов из множества у1 . . . уm (сигналы у1 . . . уm называются микрооперациями, каждый из сигналов может принимать только одно из значений 1 или 0), предписанную микропрограммой У; и соответствующую значениям логическим условий х1...хn. При выполнении процессором пакета  микропрограмм на его входы последовательно подаются коды операции, которые соответствуют той или иной микропрограмме. На входы процессора

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

Переход на новый шаг алгоритма  осуществляется только с приходом специального сигнала синхронизации (S).

 

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

    1. Последовательность синтеза синхронных управляющих автоматов

В данном курсовом проекте синхронный управляющий автомат реализуется некоторым алгоритмом функционирования, который формально задаётся таким начальным языком описания как граф - схема алгоритма (ГСА).

 

ГСА - это  ориентированный связный  граф, включающий вершины четырёх  типов: начальную, конечную, операторную и условную (рисунок 3). Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. У начальной и операторной вершин по одному выходу, у условной - два выхода, помеченных символами 1 и 0. конечная вершина выходов не имеет.

 

     ГСА удовлетворяет  следующим условиям:

 

1) входы  и выходы вершин  соединяются  друг с другом  с помощью  дуг, направленных  всегда от выхода ко входу;

 

2) каждый выход соединён только  с одним входом;

 

3) любой  вход соединяется, по крайней  мере, с одним выходом;

 

4) любая  вершина ГСА лежит,  по крайней  мере, на одном  пути из начальной вершины  к конечной;

 

5) в  каждой условной вершине  записывается один из элементов  множества Х={ х1...хn } логических условий  (разрешается в различных условных вершинах запись одинаковых элементов множества Х);

 

6) один  из выходов условной  вершины,  помеченный «0» или  « 1 »,  может соединяться с  её входом;

 

7) в  каждой операторной вершине  записывается  оператор (микрокоманда) У; - подмножество множества микроопераций У={ у1...уm } (разрешается запись в различных операторных вершинах одинаковых микрокоманд).

1.3 Современная элементная база для реализации логических преобразователей и блоков памяти УА

Структура управляющего автомата во многом зависит  от принципа его построения.

 

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

ЛП  представляет собой комбинационную схему. БП содержит r элементов памяти, которыми для синхронных автоматов  являются специально разработанные  синхронные элементарные автоматы с памятью, которые стали называть триггерами.

 

     Наибольшее  распространение  получили несколько  разновидностей  синхронных триггеров, которые  получили следующие наименования: RS - триггер, D - триггер, Т - триггер, JK - триггер. Отличаются данные триггеры количеством информационных и управляющих сигналов, а также способами записи в них хранимой информации.

 

     Блок  памяти на  своих выходах d1 . .dr должен формировать  двоичный код, который соответствует  номеру текущего шага алгоритма УА, или текущему внутреннему состоянию автомата. Предварительно все возможные внутренние состояния УА обозначаются некоторыми абстрактными символами, которым затем ставятся в однозначное соответствие двоичные структурные коды. На входы блока памяти должны воздействовать сигналы f1. . . fr, которые формируются ЛП и в совокупности образуют двоичный код, соответствующий структурному коду следующего внутреннего состояния УА. Совокупность одновременно формируемых сигналов f1 . . . fr принято называть функцией возбуждения блока памяти, а каждый отдельный сигнал f1. . . fr - функциями возбуждения элементов памяти.

 

     Задачей логического  преобразователя является формирование  выходных сигналов УА и функций  возбуждения элементов памяти  как некоторой системы логических функций, аргументами которых являются переменные х1, . . .хn, d1...dr. Такую систему логических функций принято называть каноническими логическими уравнениями УА, которые и должны реализоваться логическим преобразователем.

 

     В качестве элементного базиса для реализации ЛП выбрана двухуровневая программируемая логическая матрица (ПЛМ). Это обусловлено тем, что в настоящее время ПЛМ являются весьма доступными для широкого круга пользователей, высоко экономичными как для серийного, так и для разового производства изделий вычислительной техники, ориентированы на реализацию системы логических функций, представленных в дизъюнктивных нормальных формах (ДНФ).

 

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

 

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

 

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

 

2 Анализ ГСА синтезируемого УА и детализация его структурной схемы

2.1 Анализ и разметка ГСА

Задание:

Рисунок 6 - ГСА

 

 

Таблица 1 – Условия

 

Вариант

Тип УА

Способ кодирования

Тип синхронных триггеров

ГСА

Мили

Мура

Трив.

Эфф. 1

Эфф. 2

RS

D

T

JK

5

  

+

+

          

+

2.8


 

 

 

 

 

Таблица 2 - Микрооперации

 

 

Yi

микрооперации

y1

 y2

y3

y4

y5

y6

y7

Y1

1

0

1

0

0

1

0

Y2

0

0

0

0

1

0

1

Y3

0

0

1

0

1

0

1

Y4

0

1

1

0

0

0

0

Y5

1

0

0

1

1

0

1

Y6

0

1

0

1

0

0

0

Y7

1

1

0

1

0

1

1

Y8

1

0

1

0

1

1

1

Y9

0

0

0

1

0

0

1

Y10

0

1

0

0

1

0

0


 

 

Произведем разметку граф - схемы  алгоритма, руководствуясь следующими пунктами:

-символом начального состояния а1 отмечаются начальная и конечная операторные вершины;

-все операторные вершины отмечаются  различными символами а2 …аi …аn;

-каждая операторная вершина  ГСА должна быть отмечена только  одним индивидуальным символом  аi.

В результате разметки ГСА по указанным правилам удается определить множество внутренних состояний УА  А = { а1, …аi ,…аn }, а также мощность этого множества, которая равна IАI = n.

 

 

 

 


 


 

 

 


 

 

 




 



 


 

 

 

 

 

 

 

 

 

Рис 7 – Размеченная ГСА

2.2 Структурное кодирование внутренних состояний УА

По исходным данным граф - схемы  алгоритма сигналов автомата составим таблицу переходов и выходов, которая будет отражать переходы автомата из состояния am в as под действием входного сигнала X(am,as).

 

 

Таблица 4 – Структурная таблица переходов

 

am, Y(am)

K(am)

as

K(as)

X(am,as)

F(am,as)

Q3

Q2

Q1

Q0

Q3

Q2

Q1

Q0

f3

f2

f1

f0

a1

y1y3y6

0

0

1

0

a2

0

0

1

1

x3

0

0

1

1

a3

0

1

0

0

0

1

0

0

a2

y5y7

0

0

1

1

a4

1

0

1

0

x2

1

0

1

0

a5

0

1

0

1

0

1

0

1

a3

y3y5y7

0

1

0

0

a8

0

0

0

1

x1

0

0

0

1

a9

1

0

0

0

1

0

0

0

a4

y2y3

1

0

1

0

a2

0

0

1

1

0

0

1

1

a3

0

1

0

0

0

1

0

0

a7

0

1

1

1

0

1

1

1

a5

y1y4y5y7

0

1

0

1

a6

0

1

1

0

1

0

1

1

0

a6

y1y3y5y6y7

0

1

1

0

a1

0

0

1

0

1

0

0

1

0

a7

y1y3y5y6y7

0

1

1

1

a5

0

1

0

1

0

1

0

1

a6

0

1

1

0

x2

0

1

1

0

a7

0

1

1

1

x2x5

0

1

1

1

a8

y2y4

0

0

0

1

a8

0

0

0

1

x3

0

0

0

1

a10

1

0

0

1

1

0

0

1

a9

y1y2y4y6y7

1

0

0

0

a8

0

0

0

1

x6x1

0

0

0

1

a9

1

0

0

0

x6

1

0

0

0

a10

1

0

0

1

1

0

0

1

a10

y1y3y6

1

0

0

1

a1

0

0

1

0

1

0

0

1

0


 

 

2.3 Детализация блока  памяти УА


 




 

 




 



 









 


 


 





 


 


 


 

 


 

 

Рисунок 8 – Детализированный блок памяти

3 Структурный синтез логического  преобразователя УА

3.1 Разработка расширенной структурной  таблицы переходов и выходов  УА

После разметки ГСА, оказалось, что множество состояний следующее:

A = {a1, …, a10}

Мощность множества равна:

|A| = 10

Потребное количество триггеров равно:

r = ]log2|A|[ = ]log210[ = 4

 

Таблица 3 – Состояния автомата

 

Qn

Q3

Q2

Q1

Q0

Кол-во вхождениий

am

a8

0

0

0

1

3

a1

0

0

1

0

2

a2

0

0

1

1

2

a3

0

1

0

0

2

a5

0

1

0

1

2

a6

0

1

1

0

2

a7

0

1

1

1

2

a9

1

0

0

0

2

a10

1

0

0

1

2

a4

1

0

1

0

1


 

 

3.2 Составление логических уравнений  для выходных сигналов и функций  возбуждения триггеров

Составление логических уравнений  для функций  возбуждения блока  памяти F(аm,аs) сводится к составлению  совокупности логических уравнений для каждой отдельной функции возбуждения элементов памяти (f1 … fr). Логические уравнения записываются как дизъюнкция конъюнкций структурного кода исходного состояния автомата K(am) и комбинации входных сигналов X (аm,аs) по тем строкам таблицы, в которых в соответствующем столбце fi  присутствует значение, равное 1.

 

 

 

 

    Для автомата типа  Мура, представленного  расширенной  структурной таблицей 5, логические  уравнения для функций возбуждения  элементов памяти будут иметь  следующий вид:

 

= x2+ + + x6 + +

 

= + + + + + + + x2 + x2x5

 

= x3 + x2 + + + + + + x2 + x2x5 +

 

= x3 +  + x1+ + + + + x2x5+ + x3+ + x6x1+

3.3 Минимизация логических уравнений

 x2   

      

 x3    x2

     x2x5

x1   

     x3

     x6x1

     x6

     

    

 

 

В итоге, получим:

 

= + + + +

 

= + + + + + + +

 

= + + + + + + + + + + +

 

= + + + + + + + + +

 

 

    Для автомата типа Мура логические уравнения  функций выходов (yi) формируется на основе графы am, Y (аm) соответствующей структурной таблицы. Функции выходов для автомата типа Мура представляют собой дизъюнкции только конъюнкций структурного кода исходного состояния автомата K( am) по тем строкам структурной таблицы, в которых присутствует выходной сигнал yi. Логические уравнения для функций выходов автомата типа Мура не содержат символов входных переменных. Логические уравнения составляются для всех выходных сигналов.

 

     Функции выхода для автомата Мура будут иметь вид:

 

= +Z3+Z10+Z11+Z12+Z13+Z14+Z17+Z18+Z19+Z20

 

= Z7+Z8+Z9+Z15+Z16 +Z17+Z18+Z19

 

= Z2+Z3+Z5+Z6+Z7+Z8+Z9+Z11+Z12+Z13+Z14+Z20

 

=Z11+Z15+Z16+Z17+Z18+Z19

 

=Z1+Z4+Z5+Z6+Z10+Z11+Z12+Z13+Z14

 

=Z2+Z3+Z11+Z12+Z13+Z14+Z17+Z18+Z19+Z20

 

=Z1+Z4+Z5+Z6+Z10+Z11+Z12+Z13+Z14+Z17+Z18+Z19

 

 

4  Разработка и оформление схемы электрической функциональной синтезированного синхронного УА

Схема электрическая функциональная синтезируемого УА состоит из объединённых схем функциональных блока памяти и  логического преобразователя, реализованного на двухуровневой программируемой логической матрице (ПЛМ).

 

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

 

 

Заключение

 

 

В рамках данного курсового проекта  конечной целью проектирования является синтез (разработка) схемы электрической  функциональной заданного синхронного  управляющего автомата. Элементным базисом  для синтеза являются двухуровневая программируемая логическая матрица (ПЛМ) с требуемыми характеристиками и комбинированными синхронными D-триггерами.

Кроме того, в ходе выполнения курсовой работы:

— синтезировали синхронный управляющий автомат.

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

— продемонстрировали практические возможности по использованию математических моделей  конечных автоматов типа Мура для структурной и функциональной последовательной детализации проектируемых управляющих автоматов;

— закрепили методы логического синтеза и минимизации комбинационной части (логического преобразователя) проектируемого УА;

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

— Получили практические навыки использования способов структурного  кодирования  синхронных УА;

—  изучили принципы построения, работы, программирования, минимизации и практического применения двухуровневых программируемых логических матриц при проектировании управляющих автоматов;

 

 

 

 

 

 

 

 

 

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

  1. Тюрин С.В. Практикум по теории автоматов: синтез синхронного управляющего автомата. Учеб. пособие. Воронеж:  Воронеж. гос. техн. ун-т, 2004. 84 с.
  2. Ю.Г. Карпов. Теория автоматов. Питер, 2003-208с.
  3. Савельев А.Я. Прикладная теория цифровых автоматов. - М.: Высш. шк., 1987. - 272с.