CSD 표현법이란?
CSD표현법은 non-zero digits의 수를 최소화 하는 방법으로 고안된 숫자 표현 체계이다.
하드웨어 구현과 DSP 분야에서 매우 유용하게 사용된다.
특히 디지털 곱셈기를 보다 효율적으로 구현하는 우아한 방법이 된다.
우리가 알고 있는 곱셈 연산에서는, AxB에서 B의 1이 있는 자리수 갯수만큼 A를 더하게 되는데.. CSD를 사용하면 이러한 연산양을 줄일 수 있다.
이번 포스팅인 부스 알고리즘과 비슷하게, 숫자를 2의 승수만으로 표현하는 것이다.
예를 들어 A를 11110와 곱하고 싶다면 A를 4번 더해야할텐데
11110을 100000 - 10으로 표현한다면 A를 5bit shift 한 것과 1bit shift 한 것의 차이만 구하면 된다.
CSD의 목적은 0이 아닌 숫자의 갯수가 최소가 되는 표현을 만드는 것이다.
CSD는 따라서 3진수 시스템을 사용하는데, -1이라는 새로운 숫자를 사용한다.
Basic Concept of CSD
규칙 1 ) 각 digit에 대한 value로 -1, 0, 1 ternary 표현이 가능하다. (일반 이진 표현 체계에서는 0, 1밖에 없었는데 말이죠?! )
규칙 2) Nonzero digit이 두 개 이상 연속으로 나올 수 없다. 예를 들면 1-1, -11, 11 등 0이아닌 수가 연속으로 나올 수 없다.
그렇기때문에 Nbit CSD number 에서 나타날 수 있는 nonzero의 갯수는 N/2를 내림한 것이다. (ex, 11bit이면 최대 5개 0이 아닌 수 등장 가능 )
Nbit에서 표현 가능한 가장 큰 숫자는
2^(N-1) + 2^(N-3) + 2^(N-5) + … + 2 = (2^(N+1)) /3 이 된다. ^^ (등비수열의 합)
예시)
110111001을 CSD로 변환해보자.
CSD term의 목표는 연속된 non-zero term을 없애는 것.
110111001에서 첫번째 연속된 1은 11_1000 term이다. 이 term은 SPT(signed-power-of-twos) code로 표현하면
100_0000 - 1000으로 나타낼 수 있음. 따라서 11100-1000 이 된다. 여기서 -는 뺄셈 연산이 아니라 -1에 대한 부호표현이다. ( 해당 자릿수에 대한 값이 -1이므로, (2^3)* -1 이란 뜻이다.
그 다음 연속된 1은 1_1100_0000 term이다. 이는 SPT code로 표현하면, 10_0000_0000 - 100_0000이 된다. 따라서 100-100-1001 이 CSD 표현식이다.
이를 decimal로 풀어보자. 2^9 - 2^6 - 2^3 + 1 = 512 - 64 - 8 + 1 = 441
원래 표현식 110111001(2) = 441 과 같은 값을 갖는다.
CSD의 수학적 표현

ㅎㅎ 티스토리 블로그에서는 수식 작성이 어려워서.. ㅜㅜ 손필기로 대체합니다.
CSD에서는 이진 숫자체계 표현과는 다르게 자릿수마다 1, 0, -1 세 값을 가질 수 있다.