PAGE47

Mnożenie liczb binarnych

Znane są 3 główne metody realizacji mnożenia:metoda przesuń i dodaj, metoda Booth’a i metoda macierzowa

Metoda przesuń i dodaj

Dla pomnożenia dwu liczb n-bitowych Y(mnożna) i X(mnożnik)sto$uje się układ rejestrów podłączonych do sumatora binarnego. Rejestr Q zawiera X, rejestr M zawiera Y. Rejestr A jest połączony z Q i rejestrem S. Rejestry M. A, Q sąn-bitowe. Rejestr S jest 1-bitowy i zawiera stale 1. Rejestr SAQ przechowuje wynik końcowy i częściowe wyniki w trakcie mnożenia.

Metoda jest wzorowana na ręcznym dziesiętnym mnożeniu. Metoda dodaje mnożną Y do siebie tyle razy ile wynosi X. Zawartość M jest dodawana do A dla kolejnych jedynek w X w rejestrze Q, począwszy od bitu najmniej znaczącego, z przesuwaniem całego rejestru SAQ o jedną pozycjęw prawo po każdym dodaniu M oraz po każdym wykryciu zerowego bitu mnożnika na zerowej pozycji rejestru Q.

	.W{n -1)	«(0)
	l Y	l
	M	1 ■
/M/ł-1) « J	O		0(0) 1
rrt—fi	^A i	H! 0	i 1
! t SAOC2/W 3aCf2n-*>	/ SACfrt	t SAOTił-O	t SAQ(0)

Algorytm mnożenia podany jest poniżej.

A = 0; 3 - 0 ;

X=Y:

Q»X;

o*i*> chen *=-M;

end if;

S=M(n-i) ;

for i in 1 to n loop

i£(OlO) = ' l' > chen A *14+A; end if;

—Inicialisc che registero A and S.

—M contains mulciplicand.

*-<? concair.3 mulciplier.

--Jf che zailCiplier is negative, chen —repiaca che concenC3 ot H and Q --wich cheir 2‘s comoiomanc.

—Ir. chis way che concenca of <j will —always ha posicive.

—Sec 5 egual co che sign of .1.

—Add che contenes of ff co A,

—0 ticces.

for j in 1 bo 2n locp -GAcrj;;

and loop: end loop;

.jT-01101 and K=l0lll

—Shifc 5AC regiscer l co che --righc. and don'c chanęe S.

— (Regcscer SAO bas 2n +1 bies --and is .cor.cacanation of che —chree regiacers S, A, and Q.

s	A	Q	Operauon
0	1X5000	01101	[flioaiization
1	10111	01101	Add M10 A
1	11011	10110	Shift n?ht
1	11101	11011	Shift nghi
1	:oioo	11011	Add M10 A
1	11010	01101	Shift nght
l	:ocoi	01101	Add M to A
t	11000	10110	Shift nęht
l	11100	01011	Shift ńghl(cc»iUl