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

ПТЦА

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

78

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

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

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

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

По дисциплине

«Информационные основы вычислительных систем»

Ташкент - 2010г.

Введение

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

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

Рис.1 Структурная схема цифрового автомата

По способу формирования функции выходов автоматы делятся на автоматы Мили (Mealy) и Мура (Moore).

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

В любом устройстве обработки цифровой информации можно выделить два основных блока - операционный автомат (ОА) и управляющий автомат (УА).

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

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

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

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

Умножение чисел различными методами.

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

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

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

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

В зависимости от способа формирования суммы частичных произведений различают четыре основных метода выполнения умножения:

1) Умножение с младших разрядов множителя со сдвигом суммы частичных произведений вправо.

2) Умножение с младших разрядов множителя со сдвигом множимого влево при неподвижной сумме частичных произведений.

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

4) Умножение начиная со старшего разряда множителя со сдвигом множимого вправо при неподвижной сумме частичных произведений.

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

1-й алгоритм: Умножение, начиная с младших разрядов множителя, со сдвигом суммы частичных произведений вправо и при неподвижном множимом.

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

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

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

ПТЦА

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

78

Рис. 2.I способ умножения

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

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

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

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

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

В операционном автомате реализован набор микроопераций

у1) B:=CM(n+1). R1(B) - содержимое регистра множителя B(n) сдвигается вправо, (n+1) младший разряд сумматора заносится в старший, освобождая разряд регистра множителя;

у2) CM:=0 - сумматор обнуляется;

у3) CM:=R1(CM) - содержимое сумматора сдвигается вправо;

у4) CM:=CM+A - к содержимому сумматора прибавляется содержимое регистра множимого А(n);

у5) СЧТ:=СЧТ - 1 - содержимое счётчика уменьшается на 1;

у6) СЧТ:=n - в счётчик заносится число тактов n;

и набор логических условий (ЛУ)

x1) B(n) - множитель регистра В;

x2) СЧТ:=0 - счётчик обнуляется.

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

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

ПТЦА

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

78

Рис. 4. Содержательная ГСА умножения

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

В нашем примере будет так:

Y₁=y₂y₆; Y₂=y₄; Y₃=y₁y₃y₅

ПТЦА

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

78

Рис. 5. Функциональная ГСА умножения

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

- символом "а₁" отмечаются вход вершины следующим за начальным и вход конечной вершины;

- входы всех вершин, следующих за операторными, должны быть отмечены;

- если входы вершин отмечаются, то только одним символом;

- входы всех вершин, за исключением конечной, отмечаются различными символами.

ПТЦА

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

78

Рис. 6. Отмеченная ГСА умножения

3. Построение графа автомата и кодирование состояния автомата

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

ПТЦА

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

78

P₂

Рис. 7. Граф автомата Мили

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

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

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

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

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

5. Определение функций выходных сигналов и сигналов возбуждения

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

6. Построение функциональной схемы управляющего автомата.

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

ПТЦА

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

78

Заключение

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

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