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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

(ГОУВПО «ВГТУ»)

Факультет информационных технологий и компьютерной безопасности

Кафедра автоматизированных и вычислительных систем

Специальность «Вычислительные машины, комплексы, системы и сети»

КУРСОВАЯ РАБОТА

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

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

Разработал А.П. Замогилин

Руководитель Ю.С. Акинина

Нормоконтроль провел Ю.С. Акинина

Воронеж 2013

Содержание

Введение

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

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

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

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

1.4 Исходные данные для курсового проектирования

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

2.1 Разработка (или Анализ) и разметка ГСА

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

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

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

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

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

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

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

Заключение

Список литературы

Введение

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

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

Основной целью курсового проектирования является закрепление знаний по дисциплине «Теория автоматов», путем их практического применения в работе. Курсовой проект требует применения широкого спектра знаний полученных в ходе обучения.

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

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

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

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

Рисунок 1.1 - Представление синтезируемого УА на уровне "черного ящика"

Словесно работу синхронного УА, представленного на уровне "черного ящика", можно описать следующим образом. На входы УА поступают входные сигналы х₁ … х_n, каждый из которых принимает одно из двух различимых значений, например, 1 или 0. На каждом i - ом шаге алгоритма работы, УА формирует некоторую совокупность Y_i выходных сигналов из множества y₁ … y_m, каждый из которых также может принимать одно из значений 1 или 0. Сигналы х₁ … х_n принято называть логическими условиями; сигналы y₁ … y_m - микрооперациями, а Y_i - микрокомандами. Переход на новый шаг алгоритма осуществляется только с приходом специального сигнала синхронизации (s). Выбор следующего шага алгоритма работы УА полностью предопределен его ГСА, а именно текущим шагом алгоритма и значениями одного или нескольких сигналов х₁ … х_n.

Выходные сигналы (микрооперации) y₁ … y_m могут иметь различную длительность: в одном случае они не могут быть больше длительности сигнала синхронизации, в другом - примерно равны интервалу времени между i-ым и (i+1)-ым шагами алгоритма работы УА, т.е. примерно равны периоду следования сигналов синхронизации. Иными словами, одни УА формируют выходные (короткие) сигналы непосредственно перед переходом на следующий шаг алгоритма, а другие формируют выходные (длинные) сигналы непосредственно после перехода на текущий шаг алгоритма и вплоть до перехода на последующий шаг алгоритма. Математической моделью управляющих автоматов, формирующих короткие выходные сигналы, является модель Мили, а для автоматов, формирующих длинные выходные сигналы - модель Мура.

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

Рис.1.2. Первый уровень структурной детализации УА в соответствии с моделями Мили и Мура

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

Блок памяти на своих выходах d₁ … d_r должен формировать двоичный код, который соответствует номеру текущего шага алгоритма УА, или, как принято говорить в теории автоматов, соответствует текущему внутреннему состоянию автомата. Предварительно все возможные внутренние состояния УА обозначаются некоторыми абстрактными символами (чаще всего какой-либо буквой с соответствующим индексом), которым затем ставятся в однозначное соответствие двоичные структурные коды. На входы блока памяти должны воздействовать сигналы f₁ … f_r, которые формируются ЛП и в совокупности образуют двоичный код, соответствующий структурному коду следующего внутреннего состояния УА. Совокупность одновременно формируемых сигналов f₁ … f_r принято называть функцией возбуждения блока памяти, а каждый отдельный сигнал f₁ … f_r - функциями возбуждения элементов памяти.

Задачей логического преобразователя является формирование выходных сигналов УА и функций возбуждения элементов памяти как некоторой системы логических функций, аргументами которых являются переменные x₁… x_n , d₁…d_r . Такую систему логических функций принято называть каноническими логическими уравнениями УА, которые и должны реализовываться логическим преобразователем (ЛП).

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

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

Математической моделью дискретного устройства является абстрактный автомат, определяемый как шестикомпонентный кортеж, или вектор [4 - 11]:

S = (Z, A ,W, д, л, a₁), (5.1)

у которого:

Z={z₁,…z_f…z_F} - множество входных сигналов автомата (входной алфавит);

A={a₁,…a_m…a_M} - множество состояний автомата (алфавит состояний);

W={w₁,…w_g…w_G} - множество выходных сигналов автомата (выходной алфавит);

д : A х Z A - функция переходов автомата, реализующая отображение D_д A х Z на A. Другими словами, функция д некоторым парам состояние - входной сигнал (a_m, z_f) ставит в соответствие состояние автомата a_s = д (a_m, z_f), a_s A;

л : A х Z W - функция выходов, реализующая отображение D A х Z на W, которая некоторым парам состояние - входной сигнал (a_m, z_f) ставит в соответствие выходной сигнал автомата w_g = л (a_m, z_f);

a₁ A - начальное состояния автомата.

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

Абстрактный автомат имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,… В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент времени t(0) автомат может находиться в начальном состоянии a(0) = a₁. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t) Z. В соответствии с функцией выходов он выдает в тот же момент времени t букву выходного алфавита w(t) = л (a(t)_, z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t +1) = д (a(t)_, z(t)), причем a(t +1) A, а w(t) W. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W. Иначе, если на вход автомата, установленного в начальное состояние a₁, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2), … - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1), w(2), … - выходное слово. Каждому входному слову соответствует определенное выходное слово, структура которого определяется функциями переходов и выходов.

Таким образом, на уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные слова. Структурной моделью нулевого уровня абстрактного автомата является модель, представленная на рис. 5.1.

Рис. 1.3 Структурная модель абстрактного автомата

Чтобы задать конечный автомат S, необходимо описать все компоненты вектора S = (Z, A ,W, д, л, a₁), т.е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Среди множества состояний может быть выделено начальное состояния автомата a₁, в котором автомат находится в момент t = 0.

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

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

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

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

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

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

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

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

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

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

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

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

в каждой условной вершине записывается один из элементов множества X={x₁, … , x_L} логических условий (разрешается в различных условных вершинах запись одинаковых элементов множества Х);

один из выходов условной вершины, помеченный “0” или “1”, может соединяться с ее входом, что недопустимо для операторной вершины; такие условные вершины будем иногда называть возвратными или ждущими;

в каждой операторной вершине записывается оператор (микрокоманда) Y_t - подмножество множества микроопераций Y={y_{1, …,} y_N}; допускается Y_t = 0; разрешается также запись в различных операторных вершинах одинаковых микрокоманд.

а), б) - начальная и конечная вершины; в) - операторная вершина;

г) - условная вершина.

Рис. 1.4 Графическое представление вершин ГСА.

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

Условия обязательно формулируются в виде вопроса, на который возможными ответами являются ДА или НЕТ.

Выполняемые операции каждого шага заносятся в операторные вершины ГСА, а условия перехода от одного оператора к другому - в условные вершины.

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

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

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

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

Известно два подхода к реализации логики управляющих автоматов (УА) - жесткая и гибкая логика управления.

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

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

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

1.4 Исходные данные для курсового проектирования

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

В задании на курсовой проект нам предлагается ГСА, представленная на рисунке

Рисунок 1.5. Граф схема алгоритма управляющего автомата типа Мили.

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

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

Правило разметки ГСА при реализации автомата по модели Мили:

-символом начального состояния а₁ отмечается вход вершины, следующей за начальной, а также вход конечной вершины ГСА;

-входы всех вершин, следующих за операторными, отмечаются различными символами а₂ …а_i …а_n;

-входы вершин ГСА, следующих за операторными, должны быть отмечены только одним единственным символом а_i.

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

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

Для циклически выполняемых алгоритмов за начальное состояние автомата может быть взято любое его допустимое состояние, которое выбирают произвольным образом и отмечают символом а₁. Все последующие состояния такого (не инициального) автомата отмечаются символами а₂ …а_i …а_n. В не инициальных автоматах за начальное его состояние может быть взято любое из допустимых состояний автомата. Для установки УА в выбранное начальное состояние необходимо также привести сигналом НУ элементы блока памяти в определенные исходные (начальные) состояния.

Рисунок 2.1. Размеченная схема автомата типа Мили.

После разметки ГСА выполняется описание УА с помощью расширенных таблиц переходов и выходов.

В процессе проектирования используют два типа таблиц - прямые и обратные. Оба типа таблиц содержат одинаковые переменные [5,7,8]:

а_m - состояние УА, из которого осуществляется переход за один такт автоматного времени;

а_s - состояние УА, в которое осуществляется переход за один такт автоматного времени;

X (а_m,а_s) - логическое условие перехода из а_m в а_s;

Y (а_m,а_s) - микрокоманда (подмножество микроопераций), выполняемая на переходе из а_m в а_s (для автомата типа Мили);

Y (а_m) - микрокоманда (подмножество микроопераций), выполняемая автоматом в состоянии а_m (для автомата типа Мура).

Каждая строка таблицы соответствует одному из путей перехода из одного состояния в другое, имеющемуся в ГСА.

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

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

Рассмотрению подлежат все пути переходов от отметок а _i к а _j.

Для автоматов допустимыми являются пути вида

a_i X(а_i, a_j) Y_k a_j (2.1)

a_i Y_k a_j (2.2)

a_i X(a_i, a_j) a_j . (2.3)

Каждому пути на ГСА вида (2.1) ставится переход УА из состояния а_i в состояние а_j под действием комбинации входных сигналов X(a_i,a_j) с выдачей выходного сигнала Y_k.

Для пути перехода вида (2.2) считают, что X(a_i,a_j) = 1, т.е. реализуется безусловный переход. На переходе вида (2.5) выходной сигнал полагается равным Y_o (пустой оператор). Поскольку в автоматах Мура выходной сигнал определяется текущим состоянием автомата, то рассмотрению подлежат переходы вида:

a_i X(а_i, a_j) a_j , (2.4)

выполняемые под действием входных сигналов X(a_i,a_j), а также переходы, являющиеся частным случаем , при входном сигнале равном 1, переходы вида:

а_i, a_j . (2.5)

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

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

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

детализация блока памяти;

составление расширенной структурной таблицы переходов и выходов;

канонический синтез логического преобразователя;

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

Структура прямой таблицы переходов и выходов представлена в таблице 2.1

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

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

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

В самом простейшем случае величина находится на основе следующего соотношения:

= 1 + int ( log₂ ( -1)),

где - мощность множества кодируемых символов абстрактного алфавита;

int (w) - целая часть (w).

В том случае, когда алгоритм функционирования синтезируемого автомата задан в виде граф-схемы алгоритма (ГСА), то структурного кодирования абстрактных символов входного и выходного алфавитов не производят. Это обусловлено тем, что при описании работы автомата в виде ГСА каждое логическое условие x_i = {1,0} и каждый выходной сигнал y_j = {1,0}, то есть уже имеют двоичное кодирование.

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

тривиальное кодирование;

эффективное кодирование (1-й способ);

эффективное кодирование (2-й способ).

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

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

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

При данном кодировании количество двоичных разрядов (т. е. число элементов памяти), необходимых для структурного кодирования, определяется также как и при тривиальном кодировании. Затем по таблице переходов, графу автомата или расширенной таблице переходов определяется количество вхождений в каждое из состояний автомата (например, из графы а_s в таблицах 5.1 и 5.2). Состояния автомата, т. е. соответствующие им символы абстрактного алфавита, упорядочиваются в порядке убывания числа вхождений в каждое состояние. То состояние автомата, в которое имеется максимальное число вхождений, кодируется двоичным кодом, содержащем одну единственную единицу в каком - либо двоичном разряде. Последующие состояния автомата кодируются кодами, также содержащими одну единственную единицу, но отличающимися между собой. По мере исчерпания таких кодов для кодирования используются структурные коды, содержащие по две единицы в каких - либо разрядах. Эти коды также должны быть различны между собой. Затем используются структурные коды, содержащие по 3, 4 … единицы, до тех пор, пока все состояния автомата не окажутся закодированными.

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

Закодированные при помощи первого эффективного способа абстрактные символы представлены в таблице 2.2

Таблица 2.2 - Кодирование внутренних состояний.

Абстрактные символы	Структурные коды
		d3	d2	d1	d0
	a1	0	1	1	0
	a2	1	0	1	0
	a3	0	0	1	0
	a4	0	1	0	0
	a5	0	1	0	1
	a6	1	0	0	0
	a7	0	0	1	1
	a8	0	0	0	1
	a9	1	0	0	1

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

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

Для синхронных автоматов с жесткой логикой блок памяти, как правило, строится на комбинированных синхронных двухтактных триггерах T, D, RS или JK. На рисунке 2.2 представлено УГО комбинированного синхронного двухтактного D - триггера, при помощи которого нам предложено реализовывать блок памяти.

Рис. 2.2 Комбинированный синхронный двухтактный D - триггер

В таблице 2.2 представлена таблица истинности комбинированного синхронного двухтактного D - триггера.

Таблица 2.3 - Таблица истинности комбинированного синхронного двухтактного D - триггера.

R	S	C	D	Q	Q+
0	0	0	*	0/1	0/1
0	0		0	0/1	0
0	0		1	0/1	1
0	1	*	*	0	1
0	1	*	*	1	1
1	0	*	*	0	0
1	0	*	*	1	0
1	1	*	*	0/1	*

В таблице 2.3 используемые символы обозначают следующее:

0/1 - нулевое или единичное состояния входов и выходов;

* - безразличное состояние входа или запрещенное состояние выхода;

­ - фронт сигнала синхронизации;

Q - текущее состояние триггера;

Q⁺ - следующее состояние триггера.

Особенностью комбинированных триггерных схем является то, что наряду с наличием у них синхронно управляемых информационных входов, присутствуют также и входы асинхронной установки S и R триггеров в единичное “1” и нулевое “0” состояния. Входы асинхронной установки триггеров обозначены на УГО отдельными от синхронных входов зонами. Входы асинхронной установки необходимы для приведения триггеров в некоторые исходные (начальные) состояния, которые в совокупности соответствуют начальному состоянию синтезируемого синхронного управляющего автомата. Сигнал, подаваемый на входы асинхронной установки триггеров для приведения их в начальные состояния, принято называть сигналом сброса (Reset) или начальной установки (Н.У.). Сигнал начальной установки должен воздействовать только на один из асинхронных входов (S или R) каждого триггера. Не задействованные для начальной установки входы триггеров должны быть подключены к дополнительному сигналу, который является постоянным и пассивным для данного типа триггера. Для представленных триггеров асинхронные сигналы S и R являются активными, если имеют уровень логической “1”, и пассивны - если имеют уровень логического “0”.

Для реализации блока памяти заданы комбинированные синхронные двухтактные D - триггеры. Реализованная схема блока памяти представлена на рисунке 2.3.

Рисунок 2.3 - Электрическая функциональная схема блока памяти.

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

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

Исходными данными для составления расширенных структурных таблиц переходов и выходов являются таблицы 2.1 и 2.2 и данные, полученные в результате структурного кодирования состояний автомата (например, данные таблицы 2.3).

Расширенные структурные таблицы переходов и выходов отличаются от таблиц 2.1 и 2.2 введением дополнительных граф, содержащих информацию о структурном коде состояния автомата в текущий момент времени К(а_m), о структурном коде автомата в последующий момент времени К(а_s), а также структурный код функции возбуждения блока памяти F(а_m,а_s), который должен формироваться логическим преобразователем для подготовки перехода автомата из состояния а_m в состояние а_s. В зависимости от используемых триггерных схем функция возбуждения F(а_m,а_s) определяется различным образом. Наиболее просто функция возбуждения определятся для D и T -триггеров. При использовании D - триггеров функция возбуждения блока памяти находится на основании следующего уравнения:

F(а_m,а_s) = К(а_s). (3.1)

Из уравнения (6.5) следует следующая система уравнений:

f₁ = d₁(а_s)

f₂ = d₂(а_s)

…. (3.2)

f_r = d_r(а_s)

Для исходного синхронного управляющего автомата расширенная таблица переходов и выходов представлена в таблице 3.1.

Таблица 3.1 - Расширенная таблица переходов и выходов

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

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

Составление логических уравнений для функций возбуждения блока памяти F(а_m,а_s) сводится к составлению совокупности логических уравнений для каждой отдельной функции возбуждения элементов памяти (f₁ … f_r). Логические уравнения записываются как дизъюнкция конъюнкций структурного кода исходного состояния автомата K( a_m) и комбинации входных сигналов X (а_m,а_s) по тем строкам таблиц 6.6, 6.7, в которых в соответствующем столбце f_i присутствует значение, равное 1.

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

f₁ = d₃ *d₂ *d₁ * 1 + d₃ *d₂ *d₁ * x₂ + ….., (3.3)

f₂ = d₃ *d₂ *d₁ * x₁ + d₃ *d₂ *d₁ * x₂ + d₃ *d₂ *d₁ * x₃ * x₄ + ….., (3.4)

f₃ = d₃ *d₂ *d₁ * x₁ + d₃ *d₂ *d₁ * x₁ + ….. (3.5)

В уравнениях (3.3 - 3.5) знаки конъюнкции могут не записываться, так же как и 1-ое значение условия перехода.

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

Функции выходов:

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

Минимизация в широком смысле слова -- такое преобразование логических выражений, которое упрощает их в смысле некоторого критерия. Целью минимизации одиночных логических функций является сокращение ранга и числа элементарных конъюнкций, входящих в исходную ДНФ логической функции. В результате минимизации по таким критериям могут быть получены кратчайшие и/или минимальные тупиковые дизъюнктивные нормальные формы, обеспечивающие минимальную структурную сложность при реализации логической функции в элементных базисах И, ИЛИ, НЕ; И-НЕ; ИЛИ-НЕ и прочее.

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

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

При реализации системы логических функций на программируемой логической матрице наиболее эффективен метод группой минимизации, который легко реализуется и гарантирует минимизацию площади ПЛМ, занимаемой на кристалле интегральной схемы. Простейший метод групповой минимизации состоит в следующем: в системе логических уравнений для функций возбуждения и функций выходов отыскиваются группы одинаковых элементарных конъюнкций. Для каждой группы одинаковых элементарных конъюнкций вводится фиктивная переменная с каким - либо индексом (например, Z₁, … Z_s). Далее все исходные логические уравнения переписываются в терминах фиктивных переменных. Затем на ПЛМ реализуют элементарные конъюнкции, соответствующие каждой фиктивной переменной и их дизъюнкции в соответствии с уравнениями, содержащими фиктивные переменные. Данный метод групповой минимизации существенно уменьшает число промежуточных шин в ПЛМ и, таким образом, потребную площадь кристалла ПЛМ. Следует отметить, что для автомата типа Мили данный метод групповой минимизации более эффективен, чем для автомата типа Мура.

Таблица 3.3 - Минимизация логических функций

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

f₀ = Z₃ + Z₇+ Z₈+ Z₁₁+ Z₁₄+ Z₁₅+ Z₁₆+ Z₁₇

f₁ = Z₁ + Z₂+ Z₃+ Z₄+ Z₅

f₂ = Z₂ + Z₆+ Z₇+ Z₁₀+ Z₁₂+ Z₁₃

f₃ = Z₁ + Z₉+ Z₁₀+ Z₁₆+ Z₁₇+ Z₁₈

y₁ = Z₁ + Z₃+ Z₇+ Z₁₀+ Z₁₈

y₂ = Z₂+ Z₃ + Z₄+ Z₆+ Z₈+ Z₁₀+ Z₁₁+ Z₁₂+ Z₁₃+ Z₁₄+ Z₁₅+ Z₁₆+ Z₁₇

y₃ = Z₂ + Z₉+ Z₁₆+ Z₁₇

y₄ = Z₁ + Z₃+ Z₈+ Z₉+ Z₁₀+ Z₁₁+ Z₁₄+ Z₁₅+ Z₁₈

y₅ = Z₂+ Z₄ + Z₆+ Z₇+ Z₈ + Z₁₁+ Z₁₂+ Z₁₃+ Z₁₄+ Z₁₅+ Z₁₆+ Z₁₇

y₆ = Z₁ + Z₃+ Z₇+ Z₉+ Z₁₀+ Z₁₈

y₇ = Z₁+ Z₂ + Z₃+ Z₄+ Z₆+ Z₇+ Z₉+ Z₁₀+ Z₁₂+ Z₁₃+ Z₁₆+ Z₁₇+ Z₁₈

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

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

Рисунок 4.1 - 1 Схема электрическая функциональная незапрограммированной ППЛМ

Как видно из рис.4.1 ППЛМ состоит из блока инверторов (DD₁...DD_S) входных логических переменных (X₁...X_S) и двух матриц. Матрица И реализует на шинах Z₁...Z_q элементарные конъюнкции с любым набором прямых и инверсных значений логических переменных X₁...X_S, а матрица ИЛИ реализует элементарные дизъюнкции с элементарными конъюнкциями, сформированными на шинах Z₁...Z_q. Результат операций дизъюнкции формируется на выходных шинах Y₁...Y_t. Матрицы И и ИЛИ представляют собой систему ортогональных проводников, в узлах пересечения которых располагаются полупроводниковые элементы, реализующие с резисторами нагрузки операции И и ИЛИ. Операцию И реализуют при помощи диодов, а операцию ИЛИ - при помощи триодов.

Электрическое подключение диодов и триодов к соответствующим ортогональным проводникам осуществляется через специальные перемычки P_i (P_j), некоторые из которых при программировании ППЛМ удаляются (пережигаются) в соответствующих узлах.

Схема функциональная электрическая представленная в ПРИЛОЖЕНИИ.

Заключение

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

Список литературы

1. С. В. Тюрин, А. И. Фрид Практикум по теории автоматов: синтез синхронных управляющих автоматов: учеб. пособие; Воронеж. гос. техн. ун-т. Уфимск. гос. авиац. техн. ун-т - Уфа, 2008. - 105 с.

2. Выполнение электрических схем по ЕСКД: Справочник / С.Т. Усатенко, Т.К. Каченюк, М.В. Терехова. - М.: Изд-во стандартов, 1992. - 316 с.

3. Глушков В.М. Синтез цифровых автоматов. - М.: Физматгиз, 1962. - 467с.

4. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, 1979. - 232 с.

5. Савельев А.Я. Прикладная теория цифровых автоматов. - М.: Высш. шк., 1987. - 272с.

12. Миловзоров В.П. Элементы информационных систем. - М.: Высш. шк., 1989. - 440 с. 13. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. - М.: Радио и связь, 1990. - 304 с.

6. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. - М.: Энергоатомиздат, 1989. - 328 с.

Размещено на Allbest.ru

...