Multiplication algorithm(1)

곱셈은 multiplicand(피승수/A) x multiplier(승수/X) = product(결과물/U)로 이루어진다.

 

디지털 회로에서 어떻게 곱셈이 이루어지는지 알아보겠습니다.

---

$$X = x_{n-1}x_{n-2}...x_{1}x_{0}$$

$$A = a_{n-1}a_{n-2}...a_{1}a_{0}$$

 

 이 때 $x_{n-1}$과 $a_{n-1}$은 각 수의 부호 비트입니다.

 곱셈 알고리즘은 단계(step) j에서 승수(multiplier)비트 $x_{j}$가 검출되고 결과물 $x_{j}A$가 $P^{(j+1)}$로 표기되는 부분 합(partial sum)에 더해지는 n-1단계(step)로 구성됩니다.

 

$$P^{(j+1)} = (P^{(j)} + x_{j} * A) * 2^{-1}; j = 0, 1, 2, ..., n-2$$

 

 이 때 첫 번째 단계 $P^{(0)} = 0$입니다.

$(P^{(j)} + x_{j} * A)$를 $2^{-1}$로 곱하게 되면 우측으로 1번 산술 시프트가 이루어지며 이는 $P^{(j+1)}$에서 자리수를 맞춰주기 위함입니다.

이로 인해 $x_{(j+1)}$는 $x_{(j)}$에 비해 2배가 되며 n-1 단계의 수식을 전개하면 다음과 같습니다

 

$$P^{(n-1)} = (P^{(n-2)} + x_{n-2} · A) · 2^{-1}$$

$$= P^{(n-3)} + x_{n-3} · A) · 2^{-1} + x_{n-2} · A) · 2^{-1} + x_{n-2} · A) · 2^{-1}$$

$$= (x_{n-2}2^{-1} + x_{n-3}2^{-2} + ... + x_{0}2^{-(n-1)}) · A$$

$$            = (\sum_{j=0}^{n-2} x_{j}2^{-(n-1-j)}) · A$$

 

만약 X와 A가 모두 양수라면 최종 결과물 U는 다음과 같습니다.

 

$$U = 2^{n-1} · P^{(n-1)} = (\sum_{j=0}^{n-2}x_{j}2^{j})A = X ·A$$

---

X와 A가 모두 양수일 때 곱셈 과정을 살펴보겠습니다.

A = 5, X = 3인 경우 두 수를 이진수로 나타내면 다음과 같습니다.

A = 0101, X = 0011

곱셈 과정을 전개해 보겠습니다.

 

첫 0번째 단계에서는 $P^{(0)}$는 0이 됩니다.

X의 0번째 비트 $x_{0}$이 1이므로 $P^{(1)}$에 A를 더해줍니다.

더해준 이후 $2^{-1}$을 곱해주게 되므로 우측으로 시프트가 이루어집니다.

다음 1번째 단계 역시 0번째 단계와 같이 동작을 수행합니다.

2번쨰 단계에서는 X의 2번째 비트가 0이므로 Add 과정 없이 shift만 수행이 됩니다.

 

따라서 결과값은 000_1111이 되어 15가 나왔습니다.