Multiplication algorithm(3)

이번에는 multiplier X가 음수인 경우를 알아보겠습니다.

 

두 수의 부호비트가 모두 1일 때에는 이전의 계산법과 조금 달라집니다.

수식으로 풀어보겠습니다.

어떠한 승수(multiplier) X가 음수일 때 X는 다음과 같이 표현할 수 있습니다.

 

$$X = -x_{x-1}2^{n-1} + \tilde{X}$$

 

이 때 $\tilde{X} = \sum_{j=0}^{n-2} x_{j}2^{j}$입니다.

쉽게 표현해보면 X = 1101(-3)일 때 X = 1000 + 101을 의미합니다.

이전 (1), (2)에서 표현한 product U를 $\tilde{X}$를 이용해 표현하면 다음과 같습니다.

 

$$U = \tilde{X} · A  = (X + x_{n-1} · 2^{n-1}) · A = X · A + A · x_{n-1} · 2^{n-1}$$

 

위의 식을 X · A의 식으로 전개하면 다음과 같습니다.

 

$$X · A = U - A · x_{n-1} · 2^{n-1}$$

다르게 말하면 $x_{n-1}$, X의 부호비트가 1이면 U의 최상위의 절반에서 A를 빼는 동작을 수행해야 됩니다.

 

 예시를 들어 전개해보겠습니다.

A = -5, X = -3으로 정하겠습니다.

A와 X를 2의 보수로 취해주면 각각 다음과 같습니다.

 

$$A = 1011, X = 1101$$

$x_{2}$까지는 연산 방식이 같습니다.

하지만 $x_{3} == 1$인 경우가 발생합니다.

이 경우 correction step이 되어 A를 빼는 동작이 수행됩니다.

A를 빼기 위해 2의 보수를 취해주면 0101이 되어 U에 더해지게 됩니다.

위의 과정을 거쳐 나온 최종 U(product)는 000_1111이 되어 15가 됩니다.