a17 (4)

Mnożenie liczb binarnych

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

Metoda przesuń i dodaj

Dla pomnożenia dwu liczb n-bitowych Y(mnożna) i X(mnożnik)stosuje 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.

Mn-1) ^ł i	U[n-1) l Y	M(0) i	0(0) * 1
	u	1
	m o t	Q(n-1) ł
|s|—H !	A ! I-	H !	0 ! I
f~f	/	t	1
SAQ(2n\ SAQ(2n—1)	SAOlri)	SAC(n- 11	SAQ( CU

L i«ruvu.U.

Algorytm mnożenia podany jest poniżej.

A = 0 ; S = 0 ;

M = Y;

Q=X;

if «3(n-l) = •!•) then Af=-M;

Q = -Q; era if;

= M(n-l) ;

i m 1 to n loop it(Q(0) ='l') tthen A = M+A; er.d if;

Ml (/)

—Initialize the registers A and 5.

—M contains multiplicand.

—Q contains multiplier.

—If the multiplier is negative, then —replace the contents of M and Q —with their 2's complement.

—In this way the contents of Q will —always be positive.

—Set S ecual to the sign of M.

—Add the contents of M to A,

—Q tcr.es.

for j in 1 to 2n loop

SAQ(j-l) =SACfj; ; end loop;

and loop;

X=01101 and 7= 10111

—Shift SAQ register 1 to the —rignt, and don't change S.

— (Register SAQ has 2n-rl bits —and is concatenation of the —chree registers S, A, and Q.

S	A	Q	Operation
0	00000	01101	Imnaiizanon
t	10111	01101	Add M to A
I	11011	10110	Shift rigł»
1	11101	11011	Shift nght
1	10100	11011	Add M to A
1.	11010	01101	Shift ngiu
1	10001	01101	Add if to A
1	11000	10110	Shift nght
1	11100	01011	Shift right Cresuit)