컴퓨터구조론 (숭실대 강의 Multiply)

Arithmetic for computers

음수 표현 방법 3가지 (지금은 1개로 통용되었다)

32 bits can only represent 2의 32승 numbers Signed Magnitude -> -0이 존재. 부호만 존재 (최상위 존재가 부호비트)
Represent -x as 2’s complement of X
Represent -x as 1’s complement of X

곱셈 알고리즘

ex) 2 x 3 = 6

초기 Product는 0000 0000 이다. Multiplier 0011 이다. 즉 승수의 가장 오른쪽 비트가 1이므로 Multiplicand(피승수)와 Product를 더해준다. Multiplicand는 0000 0010이다.
그러면 Product는 0000 0010이 된다.
1. shif left Multiplicand ->피승수를 left 1bit 해준면 0000 0100이 된다.
Multiplier를 오른쪽으로 밀어준다. 그러면 0001 이 된다.

이 과정을 한번더 반복해준다.

Multiplier가 0001 . 승수의 가장 오른쪽 비트가 1이므로 피승수와 product를 더해준다.
Multiplicand 0000 0100과 product 0010을 더하면 0000 0110이 된다.
Multiplicand를 왼쪽으로 한비트 밀면 0000 1000이 된다.
Multiplier를 오른쪽으로 한비트 밀면 0000이 되므로 나머지는 변하지 않는다.

(이 과정 속에서 Iteration이 돌 때마다 Multiplicand는 왼쪽으로 한 비트씩 계속 이동한다)

-> 이 과정 낭비.

두 번째 버전

Mutiplier는 0011이므로 오른쪽이 1이니까 Multiplicand와 Product를 더한다 Multiplicand는 0010이다. 그런데, Multiplicand하고 product의 윗 부분 0000 만을 더한다.
그렇게 되면 Product는 0010 0000이 된다.
이전에는 Multiplicand를 shift left hand 했는데, 이번에는 Product를 shift right 한다. (상대적으로 같은 효과) 그러면 Product는 0001 0000이 된다.
그 다음에 Multiplier를 오른쪽으로 shift right 해주면 0001이 된다.

이 과정을 한번 더 해준다.

Multiplier가 0001 이므로 Multiplicand와 Product를 더하면
0011 0000이 된다.
Product를 shift right하면 0001 1000이 된다.
Multiplier를 shift right 하면 0000이 된다. -> Multiplicand와 shift를 더하지 않는다.
shift product right를 해준다 -> 0000 1100이 된다. -> Multiplicand와 shift를 더하지 않는다.
Multiplier를 shift right 하면 0000 0110이 된다.

최종 버전 (우리 교재 프린트에 있는 버전)

처음에 Multiplier 가 4비트, 4 번째 loop

iteration 1 : Multiplier는 4비트만 의미있음 (초기 값이니까) 처음에 product 오른쪽 0000 비트 비어있다. (의미없다 위 네비트만 의미있다.)

iteration 2 : 그 다음 Multiplier 3비트 (왜냐하면 한 비트 밀었으니까) 처음에 product 오른쪽 한비트 밀었으므로 오른쪽 3비트가 비어 있다.

iteration 3 : shift해서 2개만 남았는데, 오른쪽 2비트만 비어있고

iteration 4 : shift 1 자리만. 오른쪽 1개만 비어있음.

즉 product register의 오른쪽 절반에 multiplier를 두면, 하나 빠져나갈 때, 중간결과 하나씩 늘어나니까 딱딱 맞아 떨어진다는 것이다. 별도의 레지스터, 별도의 시프터 필요 없다. 그래서 Multipler register를 없애고 저기에 시작한 것이다.

Multiplicand는 0010, Product 0000 0011이다. product 아래 쪽에 Multiplier가 있으므로, 1로 끝나니까 두개를 더하자!
두개 더하면 0010 0011이 된다.
그리고 나서 shift product right을 해주자. 그러면 0001 0001이 된다.

이 과정을 반복한다

Product가 0001 0001이므로 오른쪽이 1로 끝난다 그러므로 Multiplicand와 product를 더하자
0011 0001이 된다.
그리고 나서 shift product right을 해준다. 그러면 0001 1000이 된다.
0001 1000이니까 오른쪽이 0으로 끝나므로 muliplier와 product를 더하지 않는다.
shift product right만 해주면 0000 1100이 된다.
역시 0000 1100이니까 오른쪽이 0으로 끝나므로 muliplier와 product를 더하지 않는다.
그리고 나서 shift product right을 해주면 0000 0110이 된다!

곱하기 하는데 걸리는 시간은 데이터에 따라 달라진다!

proper gation delay는 조금 차이난다. 별 차이는 안남

두 번째 같이 하드웨어와 같이 보여주는 예제

ex) 100111 x 011011

마지막 버전 알고리즘으로 이걸 계산할 때 몇번 할까?

add : 1이 네개니까 더하기 네번
sub : 뺴기는 하지도 않지.(다음배울 부쓰알고리즘은 하니까 넣어놓음)
shift right : loop 한번 돌 때마다 한번이니까. 6비트 곱하기 6비트니까 6번
shift left : 안하지

따라서 이렇게 된다.

이건 부호가 없는 알고리즘

Booth’s Algorithm -> 부호가 있는 2’s complement의 곱하기 알고리즘.

B multiplicand A multiplier

a를 곱하는 건데. 힌자리 위로 올리고 -> 즉 b x a1해서 2의 1승했다는 거고, 맨 밑에거는 그렇게 되고.

a2로 테스트 할 때는 2의 사승?

A가 011110이라고 할 때

B 곱하기 영곱하기 이의 영승 비 곱하기 일곱하기 이의 일승 비곱하기 이곱하기 이의 사승 비곱하기 일곱하기 이의 삼승 비곱하기 일곱하기 이의 사승 비곱하기 0곱하기 이의 오승 -> 이렇게 연산한 것

즉 30 을 16+8+4+2로 본것이다. 그런데 조금 다른 시각에서 보면은 1111이 4개 연속으로 되어있는데, 그것보다 하나 윗자리 일이 있고 마지막 자리에 일이 있다. 즉 1000000 -000010을 빼면 똑같은 값이 나온다. 즉 빼기로 볼 수 있다. 2의 5승 뺴기 이의 1승으로 볼 수도 있다.

multiplcand, multiplier가 양수이든 음수이든 상관 없이 부호 있는 정수에 적용해도 그대로 적용된다는 점이다.

밑에서 부터 두개씩 본다. 1이 시작하는 시점에서는 빼기, 1이 끝나는 시점에서는 더하기를 하자.

11이 나오면 00이 나오면 아무것도 안한다 10이 나오면 빼기를 한다. 01이 나오면 더하기를 한다.

product register -> 64비트. flipflop으로 0하나 채운 뒤에 본다.

Arithmetic shift right the product register