이번 글에서는 Addition, Multiplication 그리고 Division에 대해서 알아보겠다.
1. Addition
Unsigned Binary Integer에서의 덧셈(Addition)은 일반적인 decimal 숫자의 덧셈과 비슷하다. 각 자리에서부터 덧셈을 수행하고, 오버플로우가 발생하면 다음 자리로 전달하여 덧셈을 수행한다. 최종적인 결과 값은 MSB에서 발생한 Overflow와 n-bit data 값이 생성된다. 이를 수학적으로 풀어보면 modulo 2^n addition과 같다.
x + y 가 n-bit으로 표현 가능한 0<= x + y < 2^n 범위 안에 들어오면 (x + y) mod 2^n = x + y가 된다.
만약 이 범위를 벗어나 2^n <= x + y <= 2^(n+1) - 2 범위 안에 들어오면 overflow가 발생하고 (x+y) mod 2^n = (x+y) - 2^n이 된다.
2's complement Representation에서의 덧셈은 우선 Unsigned Binaray Integer 값으로 module-2^n addition을 수행한 후, 다시 2's complement Representation으로 변환하여 값을 해석하면 된다. 그런데 여기서 유의해야 할 점은 Overflow를 계산하는 방식이 조금 다르다. 2's complement Representation에서는 MSB로 부호를 표현하고 있기 때문이다. MSB를 제외한 나머지 Bit을 더했을 때 발생하는 Overflow가 부호를 나타내는 MSB에 영향을 주고 있기 때문이다.
덧셈을 수행하는 x, y와의 부호를 같을 때와 다를 때로 나눠서 생각해보자.
같은 경우는, x, y 모두 양수 거나 음수일 때를 의미한다. 모두 양수 일 때는 MSB를 제외한 나머지 Bit을 더 했을 때 Overflow가 발생했다면, 같은 부호이기 때문에 실제 Overflow가 발생한 것이다. 예를 들어 0111(7) + 0111(7)을 더하면 1110(14)이 된다. MSB는 부호를 나타내기 때문에, 1110은 -2로 표현되므로 Overfow가 발생한 것이다.
아래와 같이 모두 음수일 때는 MSB를 제외한 나머지 BIT들이 작을수록 더 작은 음수를 나타낸다.
000 :: 양수, 0
001 :: 양수, 1
010 :: 양수, 2
011 :: 양수, 3
100 :: 음수, -4
101 :: 음수, -3
110 :: 음수, -2
111 :: 음수, -1
또 다른 예제로 100(-4) + 101(-3)을 더하면 -7이지만, 결과 값으로는 1/001이다. 그런데 001은 1이므로 Overflow가 발생한 것이다. 양수와는 반대로 MSB를 제외한 나머지 Bit을 더 했을 때, Overflow가 발생하지 않는 다면, 실제 Overflow가 발생한 것이다.
모두 양수 Oveflow :: MSB를 제외한 나머지 Bit을 더 했을 때의 Overflow 발생 + MSB Overflow 발생하지 않음.
모두 음수 Overflow :: MSB를 제외한 나머지 Bit을 더 했을 때의 Overflow 발생하지 않음 + MSB Overflow 발생.
이를 일반화하면 두 부호가 같은 숫자를 더할 때의 Overflow는 MSB를 제외한 나머지 Bit을 더 했을 때의 Overflow 값과 MSB Overflow 값이 서로 다를 때이다.
서로 다른 경우는 x는 양수, y는 음수 혹은 y는 양수, x는 음수일 경우이다. 이 경우는 Overflow가 발생하는 상황이 없다.
우선 Unsigned Binary Adder를 하드웨어로 구현하면 아래와 같다.
2's complement Representation Binary Adder는 아래와 같다. 아래 표현과 같이 C4/C3가 서로 다를 때(XOR 연산) Overflow V가 생성된다.
2. Subtraction
뺄셈 연산의 경우, 별로의 Full Substractors를 사용하여 구현이 가능하지만, 2's complement Representation을 사용할 경우, 위와 같이 Adder의 Input 값에 XOR 연산 기를 두고, 부호에 따라 변환하는 형태로 구현이 가능하다. 예를 들어 x-y를 수행할 때, x+(-y)의 형태로 수행해도 동일하다. 2's complement Representation에서는 +y에서 -y로의 변환은 각 자릿수마다 0이면 1로, 1이면 0으로 변환을 수행한다. 이 bit 반전 동작은 XOR 연산으로 구현가능하다. XOR의 Input으로 하나는 y, 하나는 bit 반전 여부(반전을 수행하면 1, 아닐 경우 0)를 넣어주면 동작을 동일하게 수행할 수 있다.
다시 말하면, 2's complement Representation을 사용할 경우, 별도의 뺄셈 기를 만들 필요 없이, 덧셈기에 XOR 연산 기를 추가하여 수행할 수 있다.
3. Multiplication
Unsigned number 곱셈기의 경우, AND 연산 기와 Adder로 구현 가능하다. 예를 들어 2-bit인 [x1, x0]와 2-bit [y1, y0]를 곱한 다고 생각해 보자. 곱셈을 수행하면 아래와 같고, binary bit 단위의 곱셈은 AND로 표현 가능하고, 각 자릿수 별로 3-bit 덧셈기를 이용하여 덧셈을 수행하면 된다. < [p2, p1, p0] = [0, x1*y0, x0*y0] + [x1*y1, x0*y1, 0], p3 = carry bit>
x1 x0
y1 y0
x
---------------------------------------
0 x1*y0 x0*y0
+ x1*y1 x0*y1 0
---------------------------------------
p3 p2 p1 p0
그렇다면 2's complement presentation을 사용할 경우, 곱셈 기는 어떻게 구현할 수 있을까? 위의 2-bit 예제를 2's complement presentation이라 생각하고 다시 표현해 보자.
[x1, x0] = (-x1*2^1 + x0)
[y1, y0] = (-y1*2^1 + y0)
[x1, x0] * [y1, y0] = (-x1*2^1 + x0) * (-y1*2^1 + y0) = (-x1*y0*2^1 + x0*y0*2^0) - (-x1*y1*2^2 + x0*y1*2^1)으로 표현가능하다. 이를 자릿수를 나타내기 위해 아래와 같이 표현할 수 있다.
A = (-x1*y0*2^1 + x0*y0*2^0) = [x1*y0(Sign), x1*y0(Sign Extention), x1*y0(Sign Extention), x0*y0]
B = (-x1*y1*2^2 + x0*y1*2^1) = [x1*y1(Sign), x1*y1(Sign Extention), x0*y1, 0]
A-B로 표시될 수 있고, 이는 A+(-B)로 표현 가능하다. (-B)는 각 자릿수의 BIT 반전을 취한 후 +1을 수행하면 된다. 이를 표현하면 아래와 같다.
x1 x0
y1 y0
x
--------------------------------------------------
x1*y0 x1*y0 x1*y0 x0*y0
+ ~(x1*y1) ~(x1*y1) ~(x0*y1) 1 -- (a)
+ 0 0 0 1 -- (b)
--------------------------------------------------
p3 p2 p1 p0
이때, (a) 식을 [ ~(x1*y1), ~(x1*y1), ~(x0*y1), 0] + [0, 0, 0, 1]로 구분하고, [0, 0, 0, 1]를 (b)와 먼저 더 해 준다. 그러면 [0, 0, 1, 0]을 얻을 수 있다. 이를 다시 표현하면 아래와 같다.
x1 x0
y1 y0
x
--------------------------------------------------
x1*y0 x1*y0 x0*y0
+ ~(x1*y1) ~(x1*y1) ~(x0*y1) 0 -- (a)
+ 0 0 1 0 -- (b)
--------------------------------------------------
p3 p2 p1 p0
이렇게 되면 p0는 x0*y0이므로 4-bit adder가 아닌 3-bit adder를 사용하면 되므로 더 효율적으로 수행될 수 있다. 또한 +[0 0 1 0]과 bit inversion을 같이 생각해보면 2's complement representation으로 표현되므로, 위 adder로 구현된 substractor를 사용할 수 있다.
4. Division
Unsigned Binary Numbers의 나눗셈은 일반 decimal division과 동일하다. 피제수에 얼마나 많은 제수가 포함되어있는 지 확인을 한다. 나눗셈의 과정은 최상위 BIT부터 제수로 뺄셈을 수행하면서 다음 BIT로 이동하면서 수행된다.
예를 들어 [1, 1, 0, 1]을 [1, 0, 0]으로 나누면 아래와 같이 표현 할 수 있다.
1 1
1 0 0 | 1 1 0 1
- 1 0 0
-------------------
0 1 0 1
- 1 0 0
--------------------
1
몫은 [1, 1]이 되고 나머지는 [1]이 된다.
위 식을 자리수를 맞춰 다시 표현하면, 아래와 같다.
0 0 1 1
0 1 0 0 | 0 0 0 1 1 0 1 --- (0)
- 0 0 0 0 0 0 0
------------------------------ --- (1)
0 0 1 1 0 1
- 0 0 0 0 0 0
------------------------------ --- (2)
0 1 1 0 1
- 0 1 0 0 0
------------------------------- --- (3)
0 1 0 1
- 0 1 0 0
------------------------------- --- (4)
0 0 1
(0) R0 = [0, 0, 0, 1, 1, 0, 1]
(1) R1 = R0 - [0,1,0,0] * q3 * 2^(4-1) = [0, 0, 0, 1, 1, 0, 1] - [0, 0, 0, 0, 0, 0, 0] = [0, 0, 0, 1, 1, 0, 1]
(2) R2 = R1 - [0,1,0,0] * q2 * 2^(4-2) = [0, 0, 1, 1, 0, 1] - [0, 0, 0, 0, 0, 0] = [0, 0, 1, 1, 0, 1]
(3) R3 = R2 - [0,1,0,0] * q1 * 2^(4-3) = [0, 1, 1, 0, 1] - [0, 1, 0, 0, 0] = [0, 0, 1, 0, 1]
(4) R4 = R3 - [0,1,0,0] * q0 * 2^(4-4) = [0, 1, 0, 1] - [0, 1, 0, 0] = [0, 0, 0, 1]
여기서 q3,2,1,0 값은 q 값이 1이라고 가정하고 계산된 R 값이 0보다 크거나 같으면 q값을 1로 설정하고, 아니면 q값을 0으로 설정한다. 여기서 필요한 하드웨어는 위의 빨간색으로 표시된 부분에서의 뺄셈 연산(4개의 4-bit subtractor) 과 Q 값을 설정하는 로직이 필요하다.
그렇다면, 2's complement Representation에서의 division은 어떻게 수행할 까?
첫번째로 부호를 고려하지 않고 절대값 |x|, |y| 에 대해서 |x|를 |y|로 나눈다. 즉, |x| = |y| * q + r를 만족하는 q와 r값을 찾는다.
두번째로 x와 y값의 부호가 서로 다르면 q 값에 마이너스를 취한 -q 값을 몫으로 설정하고 아니면 q값으로 몫으로 설정한다.
세번째로 x 값이 0보다 작으면 r값에 마이너스를 취한 -r 값을 나머지로 설정하고 아니면 r 값으로 나머지로 설정한
다.
x와 y 값의 부호에 따라서 나눗셈이 어떻게 진행되는 지 살펴보자.
1. x >= 0, y >=0 ::나머지 r이 0보다 같거나 클 때까지 x에서 y만큼을 계속 뺄셈을 수행한다.
2. x >= 0, y <0 :: 나머지 r이 0보다 같거나 클 때까지 x에서 y만큼을 계속 덧셈을 수행한다.
2. x < 0 , y >=0 :: 나머지 r이 0보다 같거나 작을 때까지 x에서 y만큼을 계속 덧셈을 수행한다.
2. x < 0 , y < 0 :: 나머지 r이 0보다 같거나 작을 때까지 x에서 y만큼을 계속 뺄셈을 수행한다.
위의 조건에 따라서 R을 계산할 때, 제수 x 값을 더해야 하는 지, 빼야하는 지 결정된다. 또한, q 값은 1로 설정했을 때 계산된 R값과 이전 R 값의 부호가 같으면 1로 설정하고 다르면 0으로 설정한다. 위의 4가지 경우 모두 R 값의 부호가 변경되기 전까지 덧셈 및 뺄셈을 수행하기 때문이다.
아래 예제는 -7을 3으로 나누는 경우이다.
0 0 1 0
0 0 1 1 | 1 1 1 1 0 0 1 --- (0)
+ 0 0 0 0 0 0 0
------------------------------ --- (1)
1 1 1 1 0 0 1
+ 0 0 0 0 0 0 0
------------------------------ --- (2)
1 1 1 1 0 0 1
+ 0 0 0 0 1 1 0
------------------------------- --- (3)
1 1 1 1 1 1 1
+ 0 0 0 0 0 0 0
------------------------------- --- (4)
1 1 1 1 1 1 1
x = -7, y = 3 이므로 y 값을 계속 덧셈을 수행한다.
(0) R0 = [1, 1, 1, 1, 0, 0, 1]
(1) R1 = R0 - [0,0,1,1] * q3 * 2^(4-1) = [1, 1, 1, 1, 0, 0, 1] + [0, 0, 0, 0, 0, 0, 0] = [1, 1, 1, 1, 0, 0, 1]
(2) R2 = R1 - [0,0,1,1] * q2 * 2^(4-2) = [1, 1, 1, 1, 0, 0, 1] + [0, 0, 0, 0, 0, 0, 0] = [1, 1, 1, 1, 0, 0, 1]
(3) R3 = R2 - [0,0,1,1] * q1 * 2^(4-3) = [1, 1, 1, 1, 0, 0, 1] + [0, 0, 0, 0, 1, 1, 0] = [1, 1, 1, 1, 1, 1, 1]
(4) R4 = R3 - [0,0,1,1] * q0 * 2^(4-4) = [1, 1, 1, 1, 1, 1, 1] + [0, 0, 0, 0, 0, 0, 0] = [1, 1, 1, 1, 1, 1, 1]
여기서 q3,2,1,0 값은 q 값이 1이라고 가정하고 계산된 R 값이 이전 R 값의 부호가 같으면 q값을 1로 설정하고, 다르면 q값을 0으로 설정한다. 여기서 필요한 하드웨어는 위의 빨간색으로 표시된 부분에서의 뺄셈 연산(각 1개의 4/5/6/7-bit subtractor) 과 Q 값을 설정하는 로직이 필요하다.
[1] https://www.eeeguide.com/parallel-adder-and-subtractor/
[2] https://www.quora.com/How-many-full-and-half-adders-are-needed-for-4-bit-numbers
'IT_Study > CS_Study' 카테고리의 다른 글
| [Parallel Computing] (6) Processes and Threads (0) | 2024.04.17 |
|---|---|
| [Parallel Computing] (5) Floating Point Representations (0) | 2024.04.16 |
| [Parallel Computing] (4-2) Arithmetic Operation(1) (0) | 2024.04.14 |
| [Parallel Computing] (4-1) Binary Representation (2) | 2024.04.13 |
| [Parallel Computing] (3) Application - AI/LLM (0) | 2024.04.13 |
댓글