Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf

Скачать файл (5,83Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 10.07.2024

Просмотров: 152

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

то справедливы	тождественные соотношения
	1 (V -М р )) =				Мр),	(4-75)
ft (х) fi (У) V ft (х) ft (У) =					fa (Ху) fb (х V У),	(4.76)
где а = 17; b =	i \] /; I, /	=	1 ,	2 ,	ft — 1 .
В справедливости их легко убедиться путем непосредственной
проверки. С учетом (4.75)		и (4.76) получим при нечетном ft
	0.5(*—1)
	Р =»	У	ft (ху) fk-i (X V у)
и при четном ft		1
и при четном ft			0.5(*-2)
		V	0.5(*-2)
Р	= /о ,5ft (* Р )	V	(V	ft (ХУ) fk-i (X V Р ).

При реализации схем R, С, Q и S, согласно (4.71) — (4.74), для сумматора требуется 3/г одновходовых и 3k + 3 двувходовых эле ментов.

Дальнейшее расширение рассматриваемой системы путем включе ния в нее функции

	щ х\ = f1	ПРИ	* < [0,5ft] — 1,
	(0	при х > [0,5ft] — 1
позволяет записать выражение для р в виде
	Р = h 0,5*] (ху) V		/[0,5*j (х V У) и (Я)-
Используя это	выражение,	а	также	выражения	(4.71) — (4.74),
можно построить	сумматор из	2 ^ + 3 одновходовых			и 2k +	6 дву
входовых элементов (k > 3).				(2.30) — (2.32). В [1]		пока
Рассмотрим теперь систему операций
зано, что для реализации функции х +				у (mod k) требуется 2k — 2

одновходовых и 2k — 1 двувходовых элементов. При построении схем Р, S, R и С, согласно выражениям

		Р =	W -')(*'“')( V (У1 4 ) (у'4		) ) ,
			i=1	\i=k-t	J
				s = qz1 V qxz,
				r = z(q2) (q2),
				c = p \ J r,
требуется еще 3		одновходовых и 5ft — 1 двувходовых элементов.
Система,	включающая			операции х + у (mod ft)	и (2.30), а также
константы 0,	1,	....	ft — 1, функционально полна (§ 2.4). Поскольку

123

эта система содержит операцию сложения по mod k, то для построе ния схем Q, S и С надо по одному элементу типа х + у (mod k). Если воспользоваться выражениями

г = г(д + 2)*,

где х 2 — хх, то для построения	сумматора при k > 3 необходимо
иметь 7k — 5 двувходовых элементов.
В модулярной системе операций при простом k схемы Р и R можно
строить по выражениям
Р =	/ \ у—о
1=1 \ /=о

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

Если модулярную систему операций дополнить функциями

то выражения для р и г можно записать так:

г = гft-., (q).
В этом случае для построения	сумматора при k > 3 требуется
2k одновходовых и 2k + 2 двувходовых элементов.
Включение в рассматриваемую систему операций
xt = j 1 при х = t,
[О при х ф 1 ,	(i = 1 , 2 ,	. . . , k —. 1)
дает возможность представить функции р и г		как

Для построения сумматора при k > 3 требуется 2k — 1 одновхо довых и ЗА — 1 двувходовых элементов.

124

Дополним теперь модулярную систему всеми одноместными опе рациями. Нетрудно проверить, что при k = 3 множество функций {к (х)}, для каждой из которых

р = хук (х +	у),
непустое (например, к (х) — 2х + 2.	При k = 5 и k = 7 всегда
можно найти такие функции / (х), <р (х)	и ф (х), для которых

Р = fi (ху'р (х + у) + ф {ху)).

Например, при k = 5 имеем

/х (х) =	J1 при хф О ,
		[О при х = О,

ф(х) =	2	при х£	{0 , 2 },
	О при х£		{0 , 2 },
ф (х) =		х + 1 (mod k).
В общем случае при любом k справедливо выражение
P = fi(U (х) U(y) + F(x + у) fx (U (х) + U (у))),
где, например,	1	при х >	[0,5/е],

	О	при х <	[0,5/г],
F(x) = 1	при х < [0,5^] — 1,
О	при х>[0,5&] — 1 .

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

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

ного сумматора требуется минимум оборудования	[11].	Сложность
n-разрядного сумматора может быть оценена по	числу L (k, п)
логических элементов, необходимых для его построения
L (к, п) = пЬ (к, 1) = [log, N] L(k, 1)	L (к,	1).

Постоянный множитель In N можно опустить, так как представляют интерес лишь экстремальные точки функции L {к, п). В этом случае

М М ) = - ^ - .

(4.77)

125

Подставляя в (4.77) полученные выше оценки сложности реали зации одноразрядного сумматора L (k , 1), убеждаемся, что в большинст ве неизбыточных базисных систем операций «-разрядный сумматор

нельзя построить из элементов, число	которых	меньше п (Ak +		В),
где А и В постоянные данного базиса. Так как величина А «			7	9,
то при реализации сумматора в таких	базисах	оптимальное	k — 2 .

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

Заметим,	что	применение	симметричного	кодирования цифр
{— t, — t +	1 , ...,	—1 , 0 , 1 , ...,	t — 1 , t), где	k = 2t + 1 , или дру

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

§ 4.10. М ногозначны е комбинационны е множ ительны е схемы

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

Рассмотрим вопросы синтеза много тактной и однотактной множительных схем, работающих в й-значном алфа вите [1 2 ].

			В многотактной схеме		(рис. 67)
			каждый разряд одного из сомножите
Сумма частичных произведений			лей X и Y < N, где N — некоторое
			большое число,	поочередно управляет
Рис. 67. Структура	многотактной
			параллельной обработкой всех			п раз
множительной схемы.
			рядов другого	сомножителя.		Умно-
П		П
жение X =* ^	на Y =	V уft1- 1 выполняется за п тактов. Здесь
i= 1	2, ...,	(=i			X	и Y.
xt, У{ £ Ek, (i = 1 ,		п) — количество разрядов чисел
Однотактная множительная схема осуществляет параллельную
обработку всех разрядов обоих сомножителей (рис. 68, п =					3).

126

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

Будем пользоваться обозначения ми, принятыми в §4.9, а также следую щими: и = х X у (mod й), w £ Ek~\ —

перенос при умножении х на у. Функ ции и и w реализуются соответствен

но блоками			U и W. На рис.	69 пока
заны	связи		между блоками U,		W,	Q,
Р, S,	R	и С внутри узлов		А	и	В
(рис.	67	и	68), первый из	которых

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

Рис. 68. Структура однотактной множитель ной схемы'при п = 3.

значный сумматор. Таким образом, построение множительных схем сводится к реализации двухместных функций u, w, q, р, г, s и с.

Рис. 69. Структура узлов А и В множительных схем.

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

j (лл а (« при x = s,

а ф О,

*10 при x=fcs,

атакже двухместные операции х V У и ху, удовлетворяющие условиям

127