Тема-Проектирование цифрового автомата с жесткой логикой управляющего выполнением операции умножения двои.html

Работа добавлена на сайт samzan.net:

Министерство общего и профессионального образования

Обнинский Институт Атомной Энергетики

Национальный Исследовательский Ядерный Университет МИФИ

Факультет кибернетики

Кафедра КССТ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе по дисциплине
“Прикладная теория цифровых автоматов”

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

Выполнил:  студент 2 курса

группы ВТ-С22

Череватенко М.Л.

Руководитель: Подвысоцкий Р.Г.

Обнинск, 2009

ЗАДАНИЕ
на курсовое проектирование

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

Целевая установка: в универсальном базисе логических элементов (И-ИЛИ-НЕ) разработать функционально-логическую схему управляющего автомата.

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

Содержание работы.

1.  Знакомство с литературой.
2.  Разработка алгоритма выполнения операции.
3.  Синтез структуры операционного автомата.
4.  Синтез структуры управляющего автомата.
5.  Оформление пояснительной записки.

Отчетный материал

Пояснительная записка на _____ листах.

Графики и схемы на _____ листах.

Литература.

1.  Савельев А. Я. Прикладная теория цифровых автоматов. Учебник для вузов по специальности ЭВМ. М., Высшая школа, 1987.
2.  Майоров С. А., Новиков Г. И. Принципы организации цифровых машин. Л., Машиностроение, 1974.
3.  Глушков В.М. Синтез цифровых автоматов. М., Физматгиз, 1962.
4.  Методические указания к выполнению курсового проектирования по курсу “Прикладная теория цифровых автоматов”. Обнинск, ИАТЭ, 1990.

1.  Введение.

Развернутая постановка задачи.

Разработать функционально-логическую схему автомата Мура, управляющего выполнением операции умножения двоичных чисел в формате с фиксированной точкой ускоренным методом с обработкой разрядов множителя начиная с младших при неподвижном множимом (со сдвигом частных сумм). Структура операционного автомата – каноническая. Базис логических элементов – универсальный (И-ИЛИ-НЕ). При реализации памяти автомата использовать универсальные (RS) триггеры. Разрядность операндов и результата операции 16 бит, операнды и результат операции представлены в модифицированном обратном коде, разрядная сетка не переполняется.

1.  Основные понятия, определения и обозначения

2.1 Функция и структура операционного устройства. Принцип микропрограммного управления.

Операционное устройство – устройство, преобразующее цифровую информацию.

Строгое внешнее описание ОУ называется функцией операционного устройства. Это описание не затрагивает структуру ОУ, а только описывает его входы, выходы и преобразования сигналов на входе в сигналы на выходе.

Операционное устройство выполняет операции из набора F={f1,f2,…fk} над операндами из множества D с целью получения результатов, относящихся к множеству R. Акт работы операционного устройства состоит в вычислении {ri}=fi({di}), где {ri} и {di} – подмножества множеств D и R. Таким образом, функция операционного устройства определяется заданием тройки множеств <D, R, F>, где D={di, i=1,2…k} – множество входных слов или данных, R={ri, i=1,2…l} – множество выходных слов или результатов, F={fi, i=1,2…M} – множество операций, или функций.

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

Таким образом, принцип микропрограммного управления указывает направление функционального структурирования ОУ и содержит следующие положения:

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

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

Для графического изображения микропрограммы применяется содержательная граф-схема алгоритма – ориентированный граф с вершинами четырех классов – начальные (1 исходящая, 0 входящих дуг), конечные (0 исходящих, 1 входящая дуга), операторные (любое число входящих, одна исходящая дуга), условные (любое число входящих, 2 исходящих дуги). Начальная и конечная вершина соответствуют началу и концу микропрограммы. Операторная вершина описывает действия микропрограммы в 1 такте работы устройства. Внутри операторной вершины могут быть указаны только функционально совместимые микрооперации. В условных вершинах указываются логические условия, две исходящих дуги условной вершины соответствуют значениям логического условия. Корректной считается СГСА, удовлетворяющая следующим условиям:

1.  СГСА имеет одну начальную и одну конечную вершину;
2.  во вход любой вершины СГСА (кроме начальной), входит хотя бы одна дуга, исходящая из какой-либо другой вершины;
3.  из любого выхода любой вершины (кроме конечной) должна исходить одна дуга, ведущая к другой вершине графа.

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

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

2.2 Операционные автоматы.

Формально функция операционного автомата задается пятеркой множеств <D, R, S, Y, X>, где D – множество входных слов, R – множество выходных слов, S – множество внутренних слов, Y – множество микроопераций (соответствует управляющим сигналам), X – множество логических условий (соответствует осведомительным сигналам).

С позиций теории автоматов входными сигналами ОА являются значения вектора (D, Y), выходными – значения вектора (X, R), состояниями – значения вектора (S1, S2, …, Sl). Таким образом элементами функции ОА являются:

1.  таблица спецификации слов микропрограммы, которая содержит описание входных, выходных и внутренних слов;
2.  список микроопераций, задающий множество микроопераций;
3.  список логических условий – задает логические условия.

Заданная функция ОА может быть реализована различным образом. Каноническая структура ОА строится путем прямой интерпретации его функции. Интерпретация функции ОА – замена функциональных терминов (микрооперации, слова, логические условия) элементами структурного базиса ОА (шины, регистры, комбинационные схемы).

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

Структурный базис операционного автомата состоит из следующий элементарных автоматов:

1.  Шины.
2.  Для передачи одного бита используется сигнальная линия – эл. цепь.
3.  Шина – организованная совокупность сигнальных линий, предназначенных для передачи слова информации.
4.  Для реализации микроопераций вида A:=B используется управляемая шина. Управляемая шина реализует следующее векторное уравнение: А=yB, где y – управляющий сигнал.
5.  Мультиплексор – организованная совокупность управляемых шин для передачи информации от нескольких источников одному приемнику. Функционирование описывается логическим уравнением, где yi – сигнал управления мультиплексором, Bi – слова-источники данных, А – слово-приемник данных.
6.  Регистры.
7.  Запоминающий элемент – устройство, предназначенное для хранения 1 бита информации.
8.  Совокупность запоминающих элементов, предназначенных для хранения слова информации, называется регистром. Часть регистра, предназначенная для хранения поля слова, называется подрегистром, и может рассматриваться как самостоятельный регистр.
9.  Комбинационные схемы.

Комбинационная схема является композицией логических элементов и реализует функцию .

Обозначение элементов структурного базиса операционного автомата:

Обозначение	Элемент
	Шина
	Управляемая шина (у - сигнал управления) реализует микрооперацию у:   В(1:n):=A(1:n);
	Мультиплексор на N входов реализует набор микроопераций
	Регистр с выделенными подрегистрами
	Комбинационная схема, вычисляющая значение функции Ф у:   S:=Ф(A,B,...,Z);

Каноническая структура ОА строится по следующим правилам:

1.  входным словам ставятся в соответствие входные полюсы структурной схемы;
2.  выходным словам ставятся в соответствие выходные полюсы структурной схемы;
3.  внутренним словам ставятся в соответствие регистры соответствующей разрядности;
4.  регистры при необходимости соединяются шинами с соответствующими входными и выходными полюсами;
5.  в регистрах при наличии полей в словах выделяются подрегистры;
6.  каждой микрооперации вида  ставится в соответствие комбинационная схема, выход которой управляемой шиной соединяется с регистром, хранящим слова результата (шина управляется соответствующим управляющим сигналом), а вход шинами соединяется с регистрами, хранящими слова операндов; микрооперации вида A:=B реализуются одной управляемой шиной;
7.  Каждому ЛУ вида  ставится в соответствие комбинационная схема, вход которой шинами соединяется с регистрами, хранящими слова операндов, а на выходе формируется соответствующий осведомительный сигнал; если ЛУ заключается в проверке разряда, то реализуется без комбинационной схемы.

2.3 Управляющие автоматы с жесткой логикой.

Функция управляющего автомата определяется набором микропрограмм M, описывающих процесс выполнения операций F в терминах микроопераций Y и логических условий X. С позиции теории автоматов значения векторов (F, X) и (Y) определяют входные и выходные сигналы УА, множество состояний которого достаточно для воспроизведения микропрограмм M.

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

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

Определение закона функционирования управляющего автомата Мура

Пусть микропрограмма задана в виде СГСА, и для ее интерпретации используется автомат Мура. Любую микропрограмму можно интерпретировать как автомат Мура со следующим законом функционирования:

где Q={q1, q2,… qN}—множество состояний автомата, t=0,1,… и Q(0)=q0 – начальное состояние автомата, X – множество ЛУ, Y – множество микроопераций.

Необходимый набор состояний автомата определяется путем отметки ГСА в следующем порядке:

1.  начальная и конечная вершины помечаются символом начального состояния q0;
2.  каждая операторная вершина отмечается единственным символом q1, q2, …;
3.  две различные операторные вершины не могут быть отмечены одинаковыми символами.

Теперь можно определить множество переходов автомата. Каждому переходу из состояния qi в состояние qj соответствует простой путь в ГСА вида . Путь называется простым, если не проходит ни через какую метку состояния кроме qi и qj – начальную и конечную.  – символ логического условия (предикатный символ) – соответствует условным вершинам, через которые проходит путь.

Условием выхода из начального состояния является наличие входного сигнала B.

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

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

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

Пусть задан закон функционирования автомата:

Канонический метод структурного синтеза сводит задачу структурного синтеза автомата к задаче синтеза комбинационной схемы, реализующей каноническую систему логических уравнений:

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

Процесс кодирования состояний автомата заключается в установлении соответствия между состояниями автомата qi и структурным состоянием запоминающей части автомата – упорядоченной последовательностью (a1, a2,…, ap) состояний запоминающих элементов. Число возможных способов кодирования очень велико. Проблема рационального кодирования состояний автомата является одной из трудных проблем структурной теории автоматов. При естественном способе кодирования состояния автомата кодируются двоичным кодом номера состояния. После того, как состояния автомата закодированы, строится структурная таблица переходов автомата, которая дополняет таблицу переходов кодами состояний и сигналами возбуждения, формируемыми на переходе (qi, qj).

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

Для уменьшения аппаратных затрат функции канонической системы минимизируются, и на их основе строится комбинационная часть УА.

2.4 Канонический метод структурного синтеза.

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

Канонический метод структурного синтеза оперирует с элементарными автоматами, разделяющимися на следующие два класса: элементарные автоматы с памятью (то есть автоматы, имеющие более одного внутреннего состояния) – элементы памяти или запоминающие элементы; автоматы без памяти (с одним внутренним состоянием) – комбинационные, или логические элементы.

Результатом композиции логических элементов являются автоматы без памяти – комбинационные схемы. Комбинационная схема характеризуется векторной функцией выходов, устанавливающей зависимость выходного сигнала y(x) от входного сигнала x(t) в один и тот же момент автоматного времени: y(t)=λ(x(t)). Основная задача структурного синтеза комбинационных схем заключается в построении автомата без памяти, имеющего заданную векторную функцию выходов, на основе композиции логических элементов из заданной системы логических элементов.

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

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

Справедлива следующая теорема о функциональной полноте:

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

Таким образом, система логических элементов И-ИЛИ-НЕ является функционально полной.

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

Полнота системы переходов автомата означает, что для всякой упорядоченной пары состояний этого автомата найдется входной сигнал, переводящий первый элемент этой пары во второй. Иначе говоря, если δ(a,x) – функция переходов автомата, то для полноты системы переходов в этом автомате необходимо и достаточно, чтобы для любой пары (a,b) его состояний уравнение b=δ(a,x) было бы разрешимым относительно входного сигнала x. Полнота системы переходов гарантирует корректность записи в память автомата.

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

Справедлива следующая теорема о структурной полноте:

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

Структурная схема всякого автомата, синтезированного в соответствии с каноническим методом структурного синтеза, имеет вид, изображенный на рис. 2.

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

– функция выходов автомата. Для автомата Мили , для автомата Мура . Функция выходов реализуется схемой выходов.

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

Схема выходов и схема обратных связей образуют комбинационную часть автомата.

1.  Неформальное описание алгоритма

Операция умножения относится к классу «длинных» операций, выполняемых за большое число тактов. С целью ускорения процесса умножения используются алгоритмические методы, основанные на формировании частичных произведений, получаемых умножением множимого на группу, состоящую из k соседних разрядов. При k=2 частичные произведения вычисляются следующим образом. Пара разрядов bi+1bi+2 множителя может иметь значения 00, 01, 10, 11. Первым трем наборам соответствуют частичные произведения 0, A, 2A (A – множимое). Набор 11 можно рассматривать в виде 11=100-1, и обрабатывать его следующим образом: запомнить единицу переноса в следующую пару разрядов, и считать частичное произведение равным –A. Если на предыдущем шаге был перенос, то к очередной паре обрабатываемых разрядов прибавляется 1. Таким образом алгоритм анализа множителей можно представить в виде следующей таблицы:

p0	bi+1bi+2	ЧП	p1
0	0 0	0	0
0	0 1	A	0
0	1 0	2A	0
0	1 1	-A	1
1	0 0	A	0
1	0 1	2A	0
1	1 0	-A	1
1	1 1	0	1

Здесь p0 – первоначальное значение флага переноса, bi+1bi+2 – анализируемая пара разрядов, ЧП – значение частичного произведения, p1 – новое значение флага переноса.

Пусть IA(0:15) – множимое, IB(0:15) – множитель, OC(0:15) – результат умножения.

Для хранения сумм частичных произведений выделяется слово C, разрядность которого равна удвоенной разрядности операндов плюс дополнительный разряд переполнения, т. е. всего 33 разряда. Необходимость удвоения разрядности связана с особенностью сложения чисел в обратном коде. При циклическом сложении единица переноса из старшего знакового разряда прибавляется к младшему цифровому разряду результата. При отбрасывании младших разрядов суммы частичных произведений может появиться погрешность, равная единице младшего разряда, поэтому младшие разряды необходимо учитывать при сложении. Введение дополнительного разряда переполнения связано с особенностью ускоренного метода сложения: сумма частичных произведений, получаемая в момент увеличения ее на удвоенное значение множимого, может содержать (n+2) цифровых разряда (где n – число цифровых разрядов операндов, в нашем случае n=30). Поскольку сумма может иметь отрицательный знак, для хранения и формирования которого необходим дополнительный разряд, сумма частичных произведений должен иметь не менее (n+3) разрядов, т. е. в данном случае 33 разряда.

Введём обозначения:

Условимся обозначать порядок  нумерации (старшинство) разрядов слева направо от 0 до k. A(m:n) – слово А, где m – номер младшего разряда слова, n – номер старшего разряда.. А(x) означает x-ый разряд слова.

 – логическая операция отрицания;

& – логическая операция И

 – логическая операция ИЛИ

[+] – операция циклического сложения;

. – операция конкатенации;

begin

A(0:32):= IA(0).IA.IA(0).… .IA(0); B:=IB; C(0:32):=0;

Cr(0:3):=0; P(0):=0;

if B(0)=1 then C:=C[+]A;

label:

if (B(14)&B(15)&P(0))(B(14)&B(15)&P(0)) then

begin C:=C[+]A; P(0):=0; end;

else if (B(14)&B(15)&P(0))(B(14)&B(15)&P(0)) then

begin C:=C[+]A(1:32).A(0); P(0):=0; end;

else if (B(14)&B(15)&P(0))(B(14)&B(15)&P(0)) then

begin C:=C[+]A; P(0):=1; end;

C:=C(0).C(0).C(0:30);

B:=B(0:13);

Cr:=Cr+1;

if Cr=7 goto label;

if B(14)&P(0) then C:=C[+]A;

else if B(14)&P(0) then C:=C[+]A;

OC:=C(1:16)+C(17);

end.

1.  Функция операционного устройства

Функция ОУ задается тройкой множеств {D,F,R} (см. п. 2.1). Для записи микропрограммы используем  язык функционального микропрограммирования. D и R (множество входных и выходных слов) определяем таблицей спецификации слов, а F (множество операций) зададим СГСА.

4. 1  Таблица спецификаций слов микропрограммы

Имя	Разрядность	Тип	Комментарий
IA	( 0:15 )	I	Множимое (входное)
IB	( 0:15 )	I	Множитель (входное)
A	( 0:32 )	L	Множимое (внутреннее)
B	( 0:15 )	L	Множитель (внутреннее)
C	( 0:32 )	L	Произведение (внутреннее)
OC	( 0:15 )	O	Результат (выходное)
Сч	( 0:2 )	L	Счётчик (внутреннее)
P	(0)	L	Признак переноса (внутреннее)

4. 2  Содержательная граф-схема алгоритма микропрограммы

Для графического изображения микропрограммы применяется содержательная граф-схема алгоритма. СГСА для указанной микропрограммы приведена на рис. 1.

1.  Функция операционного автомата

Функция операционного автомата задаётся (см. п. 2.2):

1. Таблицей спецификаций слов микропрограммы.

2. Списком микроопераций.

3. Списком логических условий.

Таблица спецификаций слов уже была определена при выделении функций операционного автомата (См. п. 4.1).

5. 1  Список логических условий

Идентификатор	Логическое условие
x1	B(0)=1
x2	(B(14)&B(15)&P)(B(14)&B(15)&P)=1
x3	(B(14)&B(15)&P)(B(14)&B(15)&P)=1
x4	(B(14)&B(15)&P)(B(14)&B(15)&P)=1
x5	Cr≠7
x6	B(14)&P=1
x7	B(14)&P=1

Идентификаторы логических условий xi являются также идентификаторами осведомительных сигналов.

5. 2  Список микроопераций

Идентификатор	Оператор
y1	A:= IA(0).IA.IA(0).… .IA(0);
y2	B:=IB;
y3	C:=0;
y4	Cr:=0;
y5	P:=0;
y6	C:=C[+]A;
y7	C:=C[+]A(1:32).A(0);
y8	C:=C[+]A
y9	P:=1;
y10	C:=C(0).C(0).C(0:30);
y11	B(2:15):=B(0:13);
y12	Cr:=Cr+1;
y13	OC:=C(1:16)+C(17);

Идентификаторы микроопераций уi являются также идентификаторами управляющих сигналов.

1.  Структура операционного автомата

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

1.  Функция управляющего автомата

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

ГСА для данного алгоритма приведена на рис. 3.

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

8. 1  Список переходов управляющего автомата

Множество состояний определим путём разметки ГСА в соответствии с введенными в п. 2.3 правилами. Далее составим список переходов управляющего автомата.

,

, , , ,

, , ,

, , , , , ,

8. 2  Граф переходов управляющего автомата

По списку переходов строится граф переходов управляющего автомата (см. рис. 4).

8. 3  Кодирование состояний автомата и определение сигналов возбуждения.

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

q0	0000
q1	0001
q2	0010
q3	0011
q4	0100
q5	0101
q6	0110
q7	0111
q8	1000
q9	1001

Таким образом, для построения памяти автомата понадобится 4 триггера.

Далее составим структурную таблицу управляющего автомата:

№ перехода	Исх. со-стояние	Код исх. состоян.	Условие перехода	Вых. сигналы	След. со-стояние	Код след. состоян.	Сигналы возбужд.
0	q0	0000		–	q0	0000	-
1					q1	0001	S4
2	q1	0001		y1, y2, y3, y4, y5	q2	0010	S3, R4
3					q3	0011	S3
4					q4	0100	S2, R4
5					q5	0101	S2
6					q6	0110	S2, S3, R4
7	q2	0010		y6	q3	0011	S4
8					q4	0100	S2, R3
9					q5	0101	S2, R3, S4
10					q6	0110	S2
11	q3	0011		y5, y6	q6	0110	S2, R4
12	q4	0100		y5, y7	q6	0110	S3
13	q5	0101		y8, y9	q6	0110	S3, R4
14	q6	0110		y10, y11, y12	q3	0011	R2, S4
15					q4	0100	R3
16					q5	0101	R3, S4
17					q6	0110	-
18					q7	0111	S4
19					q8	1000	S1, R2, R3
20					q9	1001	S1, R2, R3, S4
21	q7	0111		y8	q9	1001	S1, R2, R3
22	q8	1000		y6	q9	1001	S4
23	q9	1001		y13	q0	0000	R1, R4

8. 4  Каноническая система логических уравнений.

Теперь можно составить каноническую систему логических уравнений:

8. 5  Минимизация системы канонических уравнений.

После минимизации получим следующие уравнения для сигналов возбуждения:

8. 6  Функционально-логическая схема управляющего автомата.

По упрощенной системе канонических уравнений строится функционально-логическая схема управляющего автомата (см. рис. 5).

Рис. 2

Запоминающая

часть

омбинационная

часть

Вх. cигнал X

Вых. cигнал Y

Сигнал возбуждения D

Состояние автомата Q

Рис. 1

Управляющий автомат

Операционный автомат

Данные D

Результаты R

Управляющие сигналы y

Осведомительные сигналы x

1. Nfng des 20. Jhrhunderts gemcht hben
2. Становление и современное развитие криминологии
3.  Изменение трудовой функции работника по распоряжению работодателя является- перемещением перево
4. Отчет по проекту
5. Тема- САЕсенин Пороша 3 класс подготовила учитель начальных классов МОУ Котельниковс
6. Повышение эффективности деятельности коммерческих банков
7. Лабораторная работа ’3 Формирование производственной программы предприятия Рассмотрим процесс пост
8. воєнного комунізму та базувалася на впровадженні елементів ринкової економіки
9. IN ldquo;Choose job you love nd you will never hve to work dy in your liferdquo;
10. Ф.И.О.- Кочергин Олег Вениаминович 2.html
11. Смысл жизни
12. Беллона выступает категорически против нефтегазовых проектов в Арктике
13. История и основные тенденции развития психологии в России
14. ЛЕКЦИЯ ’4. СРЕДСТВА ВЛИЯЮЩИЕ НА ИММУННУЮ СИСТЕМУ.html
15. Сердца- экстракт даваны ветивер.
16. Русская философия 19 века до 50 годов испытывала сильное влияние немецкой классической философии
17. Шире круг Толерантность означает уважение принятие и правильное понимание богатого многообразия к
18. Сальмонеллёз профилактика внутрибольничной инфекции
19. Основные понятия институциональной экономики
20. Контрольная работа Информация как объект гражданских прав

Материалы собраны группой SamZan и находятся в свободном доступе