3.5. Умножение чисел, представленных в форме с плавающей запятой

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

Пример 3.6. Перемножить числа и .

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

Запишем машинные изображения чисел:

; ;

;

Знак результата . Тогда машинное изображение мантиссы произведения: .

Одновременно с умножением мантисс производится сложение порядков.

.

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

; .

Если в разрядной сетке под мантиссу отведено только семь разрядов, то после округления результата получим:

.

3.6. Ускорение операции умножения

Методы ускорения операции умножения делятся на аппаратурные и логические.

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

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

Рассмотрим способ умножения на два разряда множителя, начиная с младших разрядов и учетом предыдущего (умножение по алгоритму Бута).

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

Рисунок 3.1. Разбиение множителя на триады

Правила преобразования множителя представлены в табл.3.1.

Таблица 3.1

Разряды множителя			Выполняемая операция
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 +А +А +2А -2А -А -А 0

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

Пример 3.7.Умножить числа и используя алгоритм Бута.

5. Цифровые автоматы

5.1. Основные понятия

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

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

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

Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов – конечные множества.

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

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

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

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

Пусть имеется цифровой автомат с одним входом (рис. 5.1)

Рис.5.1. Абстрактный автомат с одним входом и одним выходом

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

1) конечное множество X входных сигналов (входной алфавит автомата)

;

2) конечное множество Y выходных сигналов (выходной алфавит автомата)

;

3) произвольное множество Q состояний автомата

;

4) начальное состояние автомата как элемент множества Q

;

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

6) функция (функция выходов автомата).

В начальный момент времени автомат находится в состоянии . В каждый момент времени t автомат способен принять входной сигнал и выдать соответствующий выходной сигнал . Таким образом, через понятие «абстрактный автомат» реализуется некоторое отображение множества слов входного алфавита X в множество слов выходного алфавита Y.

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

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

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

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

Автоматы классифицируются по двум основным признакам.

1. Объем памяти. Памятью автомата называют число его состояний. Автоматы Поста (или Тьюринга) являются бесконечными автоматами, т.к. имеют неограниченную память на ленте. Конечными автоматами являются отдельные части ЭВМ или вся машина.

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

В теории автоматов наиболее полно описаны синхронные автоматы. В зависимости от способа определения выходного сигнала в синхронных автоматах существует две возможности:

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

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

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

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

(5.1)

,

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

(5.2)

,

Автоматы первого рода с функцией выходов (5.1) называются автоматами Мили 1 рода, а автоматы второго рода с функцией выходов (5.2) – автоматами Мили 2 рода.

Отличие системы уравнений (5.1) и (5.2) состоит в том, что выходное состояние определяется входным и внутренним состоянием автомата также в момент времени t.

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

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

- множество состояний;

- входной алфавит;

- выходной алфавит типа 1;

- выходной алфавит типа 2;

- функция переходов, реализующая отображение

в Q.

- функция выходов, реализующая отображение

на Y.

- функция выходов, реализующая отображение

на U.

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

Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают сигналы входного алфавита X, и двумя выходами, на которых появляются сигналы из выходных алфавитов Y и U (рис. 5.2).

Рисунок 5.2. Совмещенная модель автомата с одним входом и двумя выходами

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

, , (5.3)

Выходной сигнал вырабатывается все время, пока автомат находится в состоянии . Выходной сигнал выдается во время действия входного сигнала при нахождении автомата в состоянии . От С-автомата легко перейти к автоматам Мили или Мура.