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

УЗБЕКСКОЕ АГЕНТСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ

Ташкентский университет информационных технологий

Факультет "Информационные технологии"

Курсовая работа

По предмету "Информационные основы вычислительных систем"

Ташкент - 2010 г.

ЗАДАНИЕ

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

2. Исходные данные: Операции умножения чисел c фиксированной запятой, элементы памяти D-триггер, автомат Мура

3. Содержание работы: функциональные схемы, граф-схема алгоритма, объем и содержание расчетно-пояснительной записки на листах формата А4

4. Период сдачи работы:

1	2	3	4
14.09	12.10	26.10	9.11
28.09			23.11

Аннотация

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

Курсовая работа выполнена объемом в 26 листов в формате А4.

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

- граф-схемы алгоритма в количестве 4 шт

- функциональные схемы 1 шт.

- таблицы 1 шт.

Содержание

Введение

1. Алгоритм выполнения операции умножения

2. Умножение чисел с фиксированной запятой в прямом коде

3. Элементы памяти. Д-триггер

4. Автомат Мура

5. Построение автомата Мура на элементе Д-триггера операции умножения с фиксированной запятой в прямом коде

5.1 Структура операционной части автомата

5.2 Содержательная граф-схема алгоритма операции умножения

5.3 Функциональная ГСА выполняемой операции

5.4 Отмеченная ГСА выполняемой операции

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

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

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

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

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

Заключение

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

Введение

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

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

Абстрактный цифровой автомат А определяется совокупностью пяти объектов

А { Х, S, Y, },

где

Х = { Х_i } - i - множество входных сигналов автомата А ( входной алфавит автомата А );

S = { S_j } - j - множество состояний автомата А ( алфавит состояний автомата А);

Y = { Y_l } - l - множество входных сигналов автомата А ( выходной алфавит автомата А );

- функция переходов автомата А, задающая отображение (Х * S ) S;

- функция выходов автомата А, задающая либо отображение (Х * S ) Y, либо отображение S Y.

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

Буквами _{1,2…..к сост} обозначены выходы элементов памяти; U_1, U_2……. U_{к сост} - булевые функции возбуждения элементов памяти; ₁ ……. _{к вых} обозначены выходные каналы автомата, где k _вых - число выходных каналов автомата.

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



Рис.3.Декомпозиция устройства обработки цифровой информации

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

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

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

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

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

1. Алгоритм выполнения операции умножения

Умножение начинается от младших разрядов множителя. Очередная цифра множителя вырабатывается путем сдвига множителя на один разряд вправо. Если цифра множителя имеет значение 1, то сумма частичных произведений увеличивается на значение множимого. При нулевом значении цифры множителя суммирование не производится. После каждого умножения на один разряд множителя сумма частичных произведений сдвигается на один разряд вправо. Множимое сохраняет постоянное положение. Длина сумматора составляет (2n+l) двоичный разряд. В данном варианте умножения суммирование происходит только в (n + 1) разряде сумматора. При сложении младшие n разрядов суммы не изменяют своего значения. За счет использования разрядов регистра множителя, освобождающихся при сдвиге множителя, длина сумматора может быть уменьшена до (n+ 1)-го двоичного разряда. В этом случае младшие разряды суммы частичных произведений, спадающие с л-го разряда сумматора при сдвиге суммы, передаются в старший разряд регистра множителя. По окончании операции умножения n старших разрядов произведения будут представлены в сумматоре и n младших разрядов -- в регистре множителя.

2. Умножение чисел с фиксированной запятой в прямом коде

В современных ЭВМ арифметико-логическое устройство не является самостоятельным схемотехническим блоком. Оно входит в состав микропроцессора, на котором строится компьютер. Однако знание структуры и принципов работы АЛУ весьма важно для понимания работы компьютера в целом. Для лучшего понимания этих вопросов проведем синтез арифметического устройства, предназначенного для выполнения только одной операции - умножения чисел с фиксированной запятой, заданных в прямом коде, со старших разрядов множителя. В ходе этого процесса также обратим внимание на особенности использования рассмотренных выше основных схемотехнических элементов ЭВМ. Синтез АЛУ проходит в несколько этапов. Сначала необходимо выбрать метод, по которому предполагается выполнение операции, и составить алгоритм соответствующих действий. Исходя из алгоритма и формата исходных данных, следует определить набор составляющих АЛУ элементов. Затем требуется определить связи между элементами, установить порядок функционирования устройства и временную диаграмму управляющих сигналов, которые должны быть поданы на АЛУ от устройства управления.

Пусть операнды имеют вид:

[X]_пк = x₀x₁x₂…x_n

[Y]_пк = y₀y₁y₂…y_n

где x₀, y₀ - знаковые разряды.

Операция умножения чисел с фиксированной запятой, заданных в прямом коде, со старших разрядов множителя выполняется по следующей формуле:

Sign Z = Sign X Sign Y

|Z| = y₁*|X|*2^-1+ y₂*|X|*2^-2 +…+y_n*|X|*2^-n

[X]_пк = 0.1101 ; Sign X = 0

[Y]_пк = 1.1011 ; Sign Y = 1

Sign Z = 0 1 = 1

|X| = 0. 1 1 0 1

|Y| = 0. 1 0 1 1

y₁y₂y₃y₄

+0.00000000 |Z| = 0

y₁ = 1 0.01101000 1*|X|*2^-1

+0.01101000 |Z| = |Z| + |X|*2^-1

y₂ = 0 0.00000000 0*|X|*2^-2

+0.01101000 |Z| = |Z| + 0

y₃ = 1 0.00011010 1*|X|*2^-3

+0.10000010 |Z| = |Z| + |X|*2^-3

y₄ = 1 0.00001101 1*|X|*2^-4

0.10001111 |Z| = |Z| + |X|*2^-4

Алгоритм вычисления:



Рис.4. Алгоритм операции умножения чисел с фиксированной запятой, заданных в прямом коде, со старших разрядов множителя

Каждой переменной, представленной в алгоритме, в схеме должен соответствовать элемент хранения. Разрядность модуля произведения равна сумме разрядностей сомножителей. Умножение двоичного числа на 2^-i обеспечивается сдвигом этого числа вправо на соответствующее количество разрядов. Переход к анализу очередного разряда множителя (i = i + 1) может быть обеспечен сдвигом регистра множителя на один разряд в сторону старших разрядов.

3. Элементы памяти. D-триггер

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

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

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

D-триггер

Символ D-триггера с дополнительными асинхронными входами S и R

D	Q(t)	Q(t+1)
0	0	0
0	1	0
1	0	1
1	1	1



D-триггер (D от англ. delay -- задержка)^[15][16][17] -- запоминает состояние входа и выдаёт его на выход. D-триггеры имеют, как минимум, два входа: информационный D и синхронизации С. Сохранение информации в D-триггерах происходит в момент прихода активного фронта на вход С. Так как информация на выходе остаётся неизменной до прихода очередного импульса синхронизации, D-триггер называют также триггером с запоминанием информации или триггером-защёлкой. Рассуждая чисто теоретически, D-триггер можно образовать из любых RS- или JK-триггеров, если на их входы одновременно подавать взаимно инверсные сигналы.

D-триггер в основном используется для реализации защёлки. Так, например, для снятия 32 бит информации с параллельной шины, берут 32 D-триггера и объединяют их входы синхронизации для управления записью информации в защёлку, а 32 D входа подсоединяют к шине.

4. Автомат Мура

автомат триггер операционный сигнал

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

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

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов:

где S, X, Y и д -- соответствуют определению автомата типа Мили, а м является отображением вида: м: S > Y, с зависимостью состояний и выходных сигналов во времени уравнением:

.

Особенностью автомата Мура является то, что символ y(t) в выходном канале существует все время пока автомат находится в состоянии s(t).

Для любого автомата Мура существует автомат Мили, реализующий туже самую функцию. И наоборот: для любого автомата Мили существует соответствующий автомат Мура.

5. Построение автомата Мура на элементе D-триггера операции умножения с фиксированной запятой в прямом коде.

5.1 Структура операционной части автомата

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

Рис.5. Структура операционной части автомата

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



x1) B(n) ; x2) СЧТ = 0;

5.2 Содержательная граф-схема алгоритма операции умножения

Содержательная граф - схема алгоритма операции умножения приведена на рис.6.

Рис.6. Содержательная граф-схема алгоритма операции умножения

5.3 Функциональная ГСА выполняемой операции

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

Функциональная граф-схема алгоритма операции умножения приведена на рис.7.

Рис.7. Функциональная граф-схема алгоритма операции умножения

5.4 Отмеченная ГСА выполняемой операции

При синтезе управляющего автомата на базе автомата Мура получение отмеченной ГСА производится по следующим правилам:

-Все операторные вершины должны быть отмечены;

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

На рис.8. приведена отмеченная ГСА, в случаи синтеза управляющего автомата Мура.

рис.8. Отмеченная ГСА синтеза управляющего автомата Мура.

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

Граф автомата Мура строится по отмеченной ГСА следующим образом. Проставляются вершины графа,соответствующих состояниям автомата. Каждому пути перехода ставится в соответствие переход автомата из состояния а_i в состояние под воздействием входного сигнала P(a_i, a_j), в пути перехода a_ia_j - переход из a_i в a_j под воздействием сигнала единицы.

На рис.9. приведен граф автомата Мура



Рис.9. граф автомата Мура

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

Кодирование состояния автомата заключается в установлении взаимно-однозначного соответствия между множеством состояний автомата и множеством элемента памяти. В моей задаче используется в качестве элементов памяти T- триггеры, которые буду обозначать Т_1,Т₂. Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния с кодом 0101 в состояние с кодом 1001, то это означает, что триггер T₁ переходит из состояния "0" в состояние "1" триггер T₂ - из состояния "1" в состояние "0. В нашем примере для автомата Мура имеем четыре состояний, следовательно достаточно иметь два триггера, т.е.



5.7 Составление структурных таблиц переходов

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

В таблице 1 приведена обратная структурная таблица автомата Мура.

Исходное состояние	Код исходного состояния	Состояние перехода	Код состояния перехода	Входные сигналы	Сигналы возбуждения
а4	11	а1	00		R1 R2
a1	00	a2	01		S2
а2 а4	01 11	a3	10	Х1	R2 S1 R1 R2 S1
а2 а3 а4	01 10 11	a4	11	Х1	R1 S1 S2

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

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

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

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

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

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

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

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

рис.10 . функциональная схема автомата Мура

Заключение

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

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

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

1. Б.Я. Цилькер, С.А., Орлов. Организация ЭВМ и систем: Учебник для вузов. - СПб: Питер,2004.

2. Методические указания для выполнения курсовой работы по дисциплине "ИНФОРМАЦИОННЫЕ ОСНОВЫ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ".

3. А.Я. Савельев. Основы информатики. Учеб. для ВУЗов- М.: Изд-во МГТУ им А.Э. Баумана, 2001.

4. Конспект лекции по ИОВС.

5. http://ru.wikipedia.org/

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