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

ВВЕДЕНИЕ

	

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

	Выполняемые в АЛУ операции можно разделить на группы:

	- операции двоичной арифметики для чисел с фиксированной запятой;

	- операции двоичной арифметики для чисел с плавающей запятой;

	- операции десятичной арифметики;

	- операции индексной арифметики;

	- операции специальной арифметики;

	- операции над логическими кодами (логические операции);

	- операции над алфавитно-цифровыми полями.

	К арифметическим операциям относятся сложение, вычитание, умножение и деление. Группу логических операций составляют операции дизъюнкции (логическое ИЛИ) и конъюнкции (логическое И). Специальные арифметические команды включают нормализацию, арифметический сдвиг, логический сдвиг.

	Можно привести следующую классификацию АЛУ.

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

	По способу представления чисел различают АЛУ:

	- для чисел с фиксированной запятой;

	- для чисел с плавающей запятой;

	- для десятичных чисел.

	АЛУ для чисел с фиксированной запятой в свою очередь делятся на АЛУ с дробными и АЛУ с целыми числами.

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

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

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

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

	

	
1. Описание алгоритма вычисления

	

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

	

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

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

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

	

	Пусть    X = 10011101,      Y = 00111001,       X  Y = Z

	

	N такта

	Y H

	Y L

	J

	1

	0 0 0 0 0 0 0 0

	0 0 1 1 1 0 0 1

	0

	2

	1 0 0 1 1 1 0 1

	0 0 1 1 1 0 0 1

	0

	3

	0 1 0 0 1 1 1 0

	1 0 0 1 1 1 0 0

	1

	4

	0 1 0 0 1 1 1 0

	1 0 0 1 1 1 0 0

	1

	5

	0 0 1 0 0 1 1 1

	0 1 0 0 1 1 1 0

	2

	6

	0 0 1 0 0 1 1 1

	0 1 0 0 1 1 1 0

	2

	7

	0 0 0 1 0 0 1 1

	1 0 1 0 0 1 1 1

	3

	8

	1 0 1 1 0 0 0 0

	1 0 1 0 0 1 1 1

	3

	9

	0 1 0 1 1 0 0 0 

	0 1 0 1 0 0 1 1

	4

	10

	1 1 1 1 0 1 0 1

	0 1 0 1 0 0 1 1

	4

	11

	0 1 1 1 1 0 1 0

	1 0 1 0 1 0 0 1

	5

	12

	0 0 0 1 0 1 1 1

	1 0 1 0 1 0 0 1

	5

	13

	1 0 0 0 1 0 1 1

	1 1 0 1 0 1 0 0

	6

	14

	1 0 0 0 1 0 1 1

	1 1 0 1 0 1 0 0

	6

	15

	0 1 0 0 0 1 0 1

	1 1 1 0 1 0 1 0

	7

	16

	0 1 0 0 0 1 0 1

	1 1 1 0 1 0 1 0

	7

	17

	0 0 1 0 0 0 1 0

	1 1 1 1 0 1 0 1

	0

	18

	0 0 1 0 0 0 1 0

	1 1 1 1 0 1 0 1

	0

	

	Результат произведения Z = 0010001011110101 . Полученный результат нетрудно проверить. В десятичной системе будем иметь Х = 157, Y = 57. Тогда результат в десятичной системе будет равен Z = 8949. Таким образом, чтобы умножить два восьмиразрядных числа, необходимо произвести восемь раз сложение и восемь раз сдвиг.

	

	
2. Разработка структурной схемы

	

	Разрабатываемое АЛУ будет иметь восьмиразрядный вход данных X, восьмиразрядный вход данных Y, шестнадцатиразрядный выход результата Z, вход начала вычисления START, выход готовности результата READY, вход принудительного сброса R и тактовый вход C (рис.2.1).

	

	Рисунок 2.1 Условное графическое изображение АЛУ.

	

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

	Исходными данными для разработки структурной схемы является алгоритм вычисления. В соответствии с заданным алгоритмом вычисления для его реализации как минимум потребуются два регистра для хранения и сдвига операндов. Для реализации счётчика потребуется три триггера. Для определения окончания вычисления необходима схема сравнения J с 0.

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

	Разработанная структурная схема показана на рис. 2.2. В этой схеме множитель Y и результат Z хранятся в одном сдвиговом 16-ти разрядном регистре RgY. Регистры RgХ и RgY имеют как прямые, так и инверсные выходы , что позволяет  уменьшить количество элементов в сумматоре. 

	

	Рисунок 2.2 Структурная схема АЛУ для умножения двоичных чисел.

	

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

	

	
3 Синтез Компонентов

	

	3.1 Синтез сумматора

	

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

	Таблица истинности полного двоичного сумматора приведена в табл.3.1, где а и b - слагаемые, S - сумма, P - перенос из предыдущего разряда. Рn – перенос в следующий разряд.

	

	Таблица 3.1

	а

	B

	P

	S

	Рn

	0

	0

	0

	0

	0

	0

	0

	1

	1

	0

	0

	1

	0

	1

	0

	0

	1

	1

	0

	1

	1

	0

	0

	1

	0

	1

	0

	1

	0

	1

	1

	1

	0

	0

	1

	1

	1

	1

	1

	1

	

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

	

	             S					          Pn

	

	

	

	

	

	

	

	

	

	

	

	

	

	0

	1

	0

	1

	

	

	0

	0

	1

	0

	P

	1

	0

	1

	0

	

	P

	0

	1

	1

	1

	

	a

	

	

	

	

	

	

	

	

	

	Рисунок 3.1 Карты Карно для полного сумматора.

	
                (3.1)

												(3.2)

	

	Полученные выражения  (3.1) и (3.2) приводим к заданной элементной базе:

	

	     (3.3)

			(3.4)

	

	По полученным выражениям строим схему полного сумматора (рис.3.2).

	

		

		Рисунок 3.2 Принципиальная схема полного сумматора.

	

	Нулевой разряд сумматора для экономии элементов построим по схеме полусумматора. Таблица истинности полусумматора представлена в табл.3.2.

	

	Таблица 3.2

	А

	B

	S

	Ро

	0

	0

	0

	0

	0

	1

	1

	0

	1

	0

	1

	0

	1

	1

	0

	1

	

	По таблице истинности получаем логические выражения:

	

			(3.5)

				(3.6)

	

	По  полученным  выражениям  строим  принципиальную  схему (рис.3.3).

	

	

	Рисунок 3.3 Принципиальная схема полусумматора.

	

	Потребляемую схемой мощность найдем по формуле:

	

	.                                                 (3.7)

	

	где N – количество логических элементов в схеме;

	– мощность, потребляемая одним элементом.

	Количество элементов в схеме равно 83 а мощность элемента – . Подставляя данные в формулу (3.7) получим:

	.

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

	

	,                                          (3.8)

	

	где – время срабатывания одного логического элемента;

	 – максимальный путь (количество последовательно пройденных элементов) формирования переноса в i-ом разряде;

	 – максимальный путь формирования результата в старшем разряде (3 элемента).

	Время срабатывания равно 4. Пути  для сумматора (разряды 1 – 7) и для полусумматора (разряд 0) равны трём. Тогда по формуле (3.8) получим:

	.

	

	3.2 Синтез регистров

	

	Для хранения и сдвига множителя Y и суммы S необходим шестнадцатиразрядный регистр сдвига. Для хранения множимого понадобится один восьмиразрядный регистр RgX.

	Структурная схема регистра сдвига показана на рис.3.4, из которого видно, что необходимо синтезировать одну комбинационную схему. Таблица истинности для этой схемы представлена в табл. 3.3, где значение управляющего сигнала W/S равное нулю соответствует режиму записи, а равное единице - режиму сдвига на один бит вправо за такт.

	


	Рисунок 3.4 Структурная схема регистра сдвига.

	

	Таблица 3.3

	D

	Q

	S

	J

	X

	0

	0

	0

	X

	1

	0

	1

	0

	X

	1

	0

	1

	X

	1

	1

	

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

	

				(3.9)

	

	

	Рисунок 3.5 Схема управления сдвигом.

	
Принципиальная схема, построенная по выражению (3.9), приведена на рис.3.5.

	Восьмиразрядный регистр для хранения Х будет представлять собой восемь JK – триггеров  с объединенными тактовыми входами.

	Мощность, потребляемую регистрами, определим по формуле

	

	,                                            (3.10)

	

	где , – количество триггеров в регистрах RgX и RgY соответственно;

	 – мощность, потребляемая триггером (12 мВт).

	 - мощность, потребляемая схемой управления сдвигом (8 мВт).

	Подставив численные значения в формулу (3.10), получим:

	.

	Время предустановки регистра равно времени предустановки триггера , а время задержки – времени задержки триггера .

	

	3.3 Синтез счётчика

	

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

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

	

	Таблица 3.4

	N

	Q2

	Q1

	Q0

	D2

	D1

	D0

	0

	0

	0

	0

	0

	0

	1

	1

	0

	0

	1

	0

	1

	0

	2

	0

	1

	0

	0

	1

	1

	3

	0

	1

	1

	1

	0

	0

	4

	1

	0

	0

	1

	0

	1

	5

	1

	0

	1

	1

	1

	0

	6

	1

	1

	0

	1

	1

	1

	7

	1

	1

	1

	0

	0

	0

	

			(3.11)

				(3.12)

		(3.13)

	

	Приводим данные выражения к заданному базису:

	

							(3.14)

							(3.15)

				(3.16)

	
Схема такого счётчика показана на рис. 3.6.

	

	

	Рисунок 3.6 Схема параллельного счетчика.

	

	Мощность, потребляемую схемой, определим по формуле

	

	.                                 (3.17)

	

	Подставляя численные значения, получим:

	.

	Максимальное время задержки счетчика в параллельном режиме будет равно сумме времени задержки КС и времени задержки триггера:

	

	.                                     (3.18)

	Максимальный путь сигнала в КС – 2 элемента. Тогда по формуле (3.18):

	.

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

	

	3.5 Синтез устройства управления

	

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

	При синтезе цифрового автомата необходимо определить   разрядность   регистра   состояний   и   синтезировать комбинационные схемы КС1 и КС2.

	Построение автомата Мура начинается с создания графа, описывающего работу схемы. Граф, описывающий работу разрабатываемого устройства управления, представлен на рис.3.8

	

	

	Рисунок 3.8 Граф переходов устройства.

	

	Далее определяем разрядность регистра состояний по формуле:

	

	n = ]log2N[ 			                             (3.19)

	

	где n - разрядность регистра состояния;

	N - количество состояний в графе.

	В нашем случае получим n = 2. Таким образом, для реализации регистра состояний потребуется два триггера.

	По графу строим таблицу состояний цифрового автомата (табл. 3.5).

	

	Таблица 3.5

	Q(t)

	Оповещающ. сигналы

	Управляющие сигналы

	Q(t+1)

	Q1

	Q0

	U0

	U1

	V1

	V2

	V3

	V4

	V5

	D1

	D0

	0

	0

	0

	X

	0

	0

	0

	0

	1

	0

	0

	0

	0

	1

	X

	0

	0

	0

	0

	1

	0

	1

	0

	1

	X

	X

	1

	1

	0

	0

	0

	1

	0

	1

	0

	X

	0

	0

	0

	1

	1

	0

	1

	0

	1

	0

	X

	1

	0

	0

	1

	1

	0

	0

	0

	1

	1

	X

	X

	0

	0

	0

	0

	0

	0

	0

	
Обозначения управляющих сигналов:

	V1 – запись информации в регистр RgX;

	V2 – сброс регистра RgY;

	V3 – запись информации в регистр RgY;

	V4 – разрешение работы счётчика;

	V5 – сигнал готовности результата Ready;

	По таблице истинности определим функции, описывающие работу КС1 и КС2, и приведем их к заданному элементному базису. Для КС2:

	

	;                                    		        (3.20)

	;                   		      	        (3.21)

	.              			          		        (3.22)

	Для КС1:                        

	                    ;      		        (3.23)

	.                                                   (3.24)

	

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

	Для реализации цифрового автомата потребуется 13 логических элементов и 2 триггера. Таким образом, мощность потребления определим по формуле

	

	.                                   (3.25)

	

	Подставляя численные значения, получим:

	
.

	

		

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

	

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

	

	,                                                         (3.26)

	.                                                         (3.27)

	

	По формулам (3.26), (3.27) определим:

	

	,

	.

	

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

	

	,  .

	
4. ПРОВЕРКА РАСЧЕТНЫХ ПАРАМЕТРОВ НА СООТВЕТСТВИЕ КОНСТРУКТИВНЫМ ТРЕБОВАНИЯМ

	

	4.1 РАСЧЕТ ТАКТОВОГО СИГНАЛА

	

	Временная диаграмма тактового сигнала представлена на рисунке 4.1.

	

	

	Рисунок 4.1 Временная диаграмма тактового сигнала.

	

	Устройство управления (триггеры регистра состояния) тактируются по фронту, а операционная часть – по спаду (тактовый сигнал на входы триггеров операционной части подаются через элементы 2И-НЕ). Таким образом, длительность активной фазы сигнала  будет определяться быстродействием устройства управления, а фазы  – быстродействием операционной части и комбинационной схемы КС1.

	Определяющим фактором длительности вычислений устройства управления является готовность управляющих сигналов. Поэтому интервал времени  будет определяться временем задержки срабатывания схемы КС2, временем предустановки регистра и временем задержки регистра:

	

	.                                        (4.1)

	

	Подставим в формулу (4.1) численные значения входящих величин, определенные выше:

	.

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

	

	.                                   (4.2)

	

	Подставив численные значения, получим:

	.

	Теперь нетрудно определить период тактового сигнала:

	

	.

	

	4.2 ОПРЕДЕЛЕНИЕ МАКСИМАЛЬНОГО ВРЕМЕНИ ВЫЧИСЛЕНИЯ

	

	Максимальное время вычисления определим по формуле

	

	,                                                    (4.3)

	

	где – максимальное количество тактов.

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

	 или .

	Полученное значение меньше заданного ограничения 2 мкс.

	

	4.3 ОПРЕДЕЛЕНИЕ ПОТРЕБЛЯЕМОЙ МОЩНОСТИ

	

	Потребляемая устройством мощность будет равна сумме мощностей, потребляемых всеми ее составными частями (регистры X и Z, счетчик, сумматор, схема сравнения, три логических элемента 2И-НЕ и устройство управления):

	

	.                        		(4.4)

	

	Подставляя численные значения, получим потребляемую устройством мощность:

	.

	Реальная потребляемая мощность оказалась меньше заданного ограничения 1000 мВт.

	

	
ЗАКЛЮЧЕНИЕ

	

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

	Разработанное устройство имеет по 8 входов для множителя Y0 – Y7 и множителя X0 – X7, вход разрешения начала счета START с активным уровнем "1", вход принудительного сброса с активным уровнем "1" и вход синхронизации с тактированием по фронту импульса; 16 выходов результата Z0 – Z15 и выход готовности результата READY с активным уровнем "1".

	Максимальное время счета .

	Потребляемая мощность .

	

	
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

	

			Курс лекций по дисциплине "Техническое обеспечение и внешние устройства ЭВС". / Под ред. А.В. Тютякина – ОрелГТУ, 2000.

			Курс лекций по дисциплине "Расчет и конструирование элементов ЭВС". / Под ред. И.И. Неврова – ОрелГТУ, 2000.

			Курс лекций по дисциплине "Аналоговая и цифровая электроника". / Под ред. А.А. Рабочего – ОрелГТУ, 1999.