오늘은 맑음

High Speed Multiplication 곱셈 알고리즘을 더욱 빨리 수행하고 더욱 적은 자원을 사용해서 연산하는 방법에 대해 알아보자. multiplicand(피승수/A) x multiplier(승수/X) = product(결과물/U)를 연산할 때 parital product는 X에 존재하는 1의 개수만큼 반복된다. 이 과정에서 많은 시간이 소비되며 중간의 partial product를 구성하기 위해 많은 register가 사용된다. 따라서 위의 단점을 극복하기 위해 나온 연산방법이 Booth's algorithm이다. 만약 X가 15인 경우 1111로 표기되며 덧셈 연산을 4번 반복해야한다. 하지만 다음과 같이 표기하게 되면 어떻게 될까 1111 = 1_0000 - 0_0001 15 = 16 - ..

이진수 수의 표현 소수점 자리수를 표현하는 방법 1장에서 언급했듯이 어떠한 n비트의 양수 X는 다음과 같이 표현될 수 있다. $$X = \sum_{i=0}^{n-1} x_{i}r_{i}$$ 여기서 r은 radix(기수)이다. 위는 양수를 표현하는 방법이므로 소수점을 가진 양의 실수를 표현하기 위해서는 n비트를 정수부(integral part)와 실수부(fractional part)로 나누어야 한다. n digit을 갖는 어떠한 수를 k digit을 갖는 정수부(integral part)와 m digit을 갖는 실수부(fractional part)로 나누면 다음과 같이 표현된다. $$(x_{k-1}, x_{k-2}, ... , x_{1}, x_{0} · x_{-1}, x_{-2}, ... , x_{-m})..

이진수 수의 표현 우리가 익히 알고있는 이진수(binary)란 0과 1로 표현된 수를 의미합니다. 어떠한 n이라는 길이를 가진 이진수(binary)를 표현하게 되면 다음과 같습니다. $$(x_{n-1}, x_{n-2}, ... , x_{1}, x_{0})$$ 각각의 자리수(digit)은 0과 1로 표현되며 위의 수를 정수(integer)형태로 표현하면 다음과 같습니다. $$X = x_{n-1}2^{n-1} + x_{n-2}2^{n-2} + ... + x_{1}2 + x_{0} = \sum_{i=0}^{n-1} x_{i}2^{i}$$ 이진수(binary)의 i번째 자리수$x_{i}$의 비중(weight)는 기수(radix)의 i승의 값을 의미합니다. 우리가 실생활에서 사용하는 10진수 표현법과 동일하지만 ..

이번에는 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 ·..

이번에는 multiplicand A가 음수인 경우의 곱셈 과정을 살펴보겠습니다. 이번에는 A = -5, X = 3인 경우 연산을 진행해보겠습니다. A는 음수이므로 2의 보수(2's complement)로 변환한 후 연산이 진행됩니다. -5를 2의 보수로 변환하면 다음과 같습니다. -5 = 1011 연산을 수행하면 위와 같습니다. 전체적인 과정은 양수 x 양수와 같으나 차이점이 있다면 shift할 때 MSB를 부호로 채워줍니다. 따라서 결과는 1110001이 되며 보수 형태를 다시 바꿔주게 되면 다음과 같습니다. 1110001 => 1110000 => 1001111 따라서 -15가 나오게 됩니다.

곱셈은 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,..