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

КОНТРОЛЬНАЯ РАБОТА

"Разработка операционной части автомата"

Введение

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

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

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

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

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

Многие люди слишком привыкли пользоваться техникой и совсем забыли о важности знаний самих процессов. Для образованного специалиста необходимо знать - «что находится внутри и как это работает».

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

1. Арифметические операции

1.1 Ускоренное умножение

автомат умножение кодирование триггер

Особенности реализации ускоренного умножения в ЭВМ

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

Для фиксации этой суммы на каждом шаге необходимо использовать 2n-разрядный процессор, n-разрядного операнда.

Перед началом операции необходимо осуществить сброс этого регистра (установить в «ноль»).

На каждом шаге умножения анализируется определенный разряд множителя, и если он равен единице, то на этом шаге производится сложение СЧП с множимым. Если разряд множителя равен нулю, то сложения на данном шаге производится.

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

Реализацию умножения принципиально можно начинать как от младшего, так и от старшего разряда множителя.

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

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

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

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

Способы (схемы) реализации умножения

1. Умножение, начиная с младших разрядов множителя со сдвигом множимого влево.

2. Умножение, начиная с младших разрядов множителя со сдвигом СЧП вправо.

3. Умножение, начиная со старших разрядов множителя со сдвигом множимого вправо.

4. Умножение, начиная со старших разрядов множителя со сдвигом СЧП влево.

Анализ схем:

1. В схемах умножения со сдвигом множимого для его представления требуется 2n-разрядный регистр.

2. А в схеме умножения, начиная с младших разрядов множителя со сдвигом СЧП вправо для представления множимого требуется n-разрядный регистр.

3. А в схеме умножения, начиная со старших разрядов множителя со сдвигом множимого вправо необходимо использовать 2n-разрядный сумматор, связанный по входу с регистром множителя.

4. Четвертая схема требует 2n-разрядного сумматора.

5. Вторая схема - n-разрядного.

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

1.2 Автомат, выполняющий ускоренное умножение

Упрощенная схема операционного устройства для реализации умножения по второму способу «умножение, начиная с младших разрядов множителя со сдвигом СЧП вправо».

В схеме умножения, начиная с младших разрядов множителя со сдвигом СЧП вправо для представления множимого требуется n-разрядный регистр.

2. Коды выполнения операций

2.1 Прямой код

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

знак:

«+» соответствует 0

«-» соответствует 1

В цифровых разрядах пишется модуль положительного или отрицательного числа.

[X]_пк - обозначим таким образом изображение числа «X» в прямом коде.

Рассмотрим диапазоны представляемых чисел:

X_+min = 0,000….0 - изображение положительного нуля

X_+max = 0,111….1 = 1 - 2^-n

X_-min = 1,111….1 = - (1-2^-n)

X_-max = 1,000….0 - изображение отрицательного нуля.

Таким образом, нуль имеет двоякое изображение.

Замечания:

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

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

3. [X]_пк * [Y]_пк = sign Z. |Z|

|Z| = |X|*|Y|

sign Z = sign X sign Y или S_z = S_x S_y

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

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

Вследствие ряда неудобств в ЭВМ операции вычитания, сложения чисел с разными знаками и деления в прямом коде практически не выполняются.

2.2 Автомат МИЛИ и его кодировка

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

Автомат Мили можно описать пятеркой (Q, X, Y, f, g), где Q - множество состояний автомата, X - множество входных символов, Y - множество выходных символов, q=f (Q, X) - функция состояний, y=g (Q, Y) - функция выходных символов.

Кодировка автомата Мили:

Вершина (операторная или логическая), стоящая после вершины «Начало», а также вход вершины «Конец» помечается символом S1, вершины, стоящие после операторных помечаются символом Sn (n=2,3.).

3. Триггер - элемент памяти

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

Устойчивые состояния можно принять в качестве логической информации 0 и 1. В таком случае триггер можно использовать в качестве запоминающего устройства, которое хранит один разряд числа, представленного в двоичном коде. Состояние триггера определяется по выходному сигналу. При этом говорят, что триггер установлен, если на его выходе присутствует 1, и сброшен, - если 0. В триггерах с прямым управлением активным уровнем считается уровень логической 1, а в триггерах с инверсным управлением - уровень логического 0. После переключения триггера входной активный уровень может быть снят, но триггер продолжает оставаться в том состоянии, которое он приобрел под воздействием этого сигнала. Для удобства-использования триггеры имеют два выхода, один из которых называют прямым Q, а другой - инверсным . Если триггер установлен (в состоянии 1), на его прямом выходе будет логическая 1, а на инверсном - логический 0. Помимо информационных входов, обозначаемых буквами R, S.J, К', D. Т, триггеры могут содержать и вспомогательные (управляющие) входы, например, предварительной установки или вход синхронизации С. Триггеры, которые реагируют на информационные сигналы только при наличии сигнала синхронизации, называют синхронными. В отличие от них асинхронные триггеры реагируют на информационные сигналы в момент их поступления. Синхронные триггеры, в свою очередь, могут быть со статическим и динамическим управлением. Для того чтобы синхронный триггер со статическим управлением смог воспринимать сигналы на информационных входах, на его входе синхронизации С должна поступить 1. Синхронный триггер со динамическим управлением реагирует на информационные сигналы только в момент изменения сигнала на С-входе от 0 до 1 (прямой динамический С-вход), либо от 1 до 0 (инверсный динамический С-вход). На рис. 1 а, б показаны соответственно обозначения синхронного триггера с прямым и инверсным динамическим управлением. Для синхронного триггера со статическим управлением иногда используют обозначение С-входа, показанное на рис. 1 в, но чаще всего у С-входа вообще не ставят никаких специальных значков. По функциональным возможностям различают:

- триггер с раздельной установкой состояний 0 и 1 (RS-триггер);

- триггер со счетным входом (T-триггер);

- триггер задержки с приемом информации по одному входу (D-триггер);

- универсальный триггер с информационными входами К и J (JK-триггер).

3.1 Т-триггер

Т-триггер (рис. 1 в,) изменяет свое состояние на противоположное при поступлении на вход Т запускающего импульса. Т-триггеры называют триггерами со счетным входом. В интегральном исполнении Т-триггеры не выпускаются, так как они легко получаются из RS-, JK- или D-триггеров.

3.2 Таблица истинности Т-триггера и структура (схема) Т-триггера

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

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

Результат преобразований реализуется схемой (рис. 2). Если Y содержит больше нулей чем единиц, то логическая сумма записывается для нулей.

4. Автоматы

Операционный автомат (ОА) служит для хранения слов информации, выполнения набора микроопераций и вычисления значений логических условий, т.е. операционный автомат является структурой, организованной для выполнения действий над информацией. На вход ОА подаются входные данные D1 которые в соответствии с алгоритмом операции преобразуются в выходные данные D0. Кроме того, ОА вырабатывает множество {х} осведомительных сигналов (логических условий) для управляющего автомата.

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

Часто операционное устройство может выполнять несколько различных операций (например, арифметико-логическое устройство может выполнять четыре арифметических действия и несколько логических операций над входными словами).Исполнителем алгоритмов называется некоторая биологическая, техническая или смешанная структура, способная исполнять (покомандно или программно) некоторый класс алгоритмов в некоторой операционной среде (некотором множестве допустимых «инструментов» и «команд»). Наиболее используемые типы исполнителя алгоритмов - человек или автомат (компьютер).

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

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

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

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

Для компьютера с памятью 512 мегабайт основной памяти может быть характерна регистровая память в 64 мегабайта.

Виды автоматов

Функционирование конечного автомата происходит в дискретные моменты времени t = 0, 1, 2,…, T. Изменение состояния автомата, то есть переход из текущего состояния в новое состояние , может быть осуществлено либо до выдачи выходного сигнала , либо - после выдачи этого сигнала. В связи с этим, выделяют два типа конечных автоматов - автоматы Мили и автоматы Мура, которые различаются законами функционирования автоматов.

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

Пример. Пример конкретного автомата Мура приведен выше (автомат для газировки).

Автомат - Мили

Приведем абстрактный пример автомата Мили: Х = {х₁, х₂}, У = {у₁, у₂, у₃}, S = {s₀, s₁, s₂, s₃, s₄, s₅}, функции перехода и выхода f зададим таблицами соответствий:

Граф управляющего автомата

Граф автомата Мили строится по отмеченной ГСА следующим образом. Проставляются вершины графа, соответствующих состояниям автомата. Определяется дуги графа автомата выходящие из вершины а_i. При этом каждой дуге графа ставится в соответствие путь точки из а_i на ГСА через единственную операторную вершину в любую точку а_j, причем . Исключение составляют дуги, идущие к конечной или начальной вершины.

Кодирование состояний управляющего автомата

Кодирование состояния автомата заключается в установлении взаимно-однозначного соответствия между множеством состояний автомата и множеством элемента памяти.

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

Обратная структурная таблица переходов

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

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

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

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

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

При включении вычислительного устройства триггеры автомата устанавливаются в произвольное состояние. Для перевода автомата в начальное состояние используется сигнал «ПУСК».

Заключение

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

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

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

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

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

Многие люди слишком привыкли пользоваться техникой и совсем забыли о важности знаний самих процессов. Для образованного специалиста необходимо знать - «что находится внутри и как это работает».

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

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