[매드프로젝트 강좌] CORDIC - 02. 알고리즘-1

후.. 전 강좌에서는 CORDIC 내용보다 잡소리가 더 길었던 것 같은데 이번에는 제대로! 알고리즘을 파해쳐 보자.

CORDIC 알고리즘을 통해서 여러 어려운 연산들을 간단히 비트 쉬프트(bit shift), 가산, 감산, LUT(Look Up Table)을 통해서 처리할 수 있다.

CORDIC 알고리즘은 함수를 2차원 평면상의 벡터로 보고 반복되는 벡터 회전을 통하여 수렴한 해를 얻을 수 있는 반복 계산 해법이다. 이 알고리즘은 회전 모드와 벡터 모드의 두가지 모드가 존재한다.

회전 모드는 임의 벡터를 희망하는 가도까지 반복 회전시켜 목적 값에 수렴시키는 것이고
벡터 모드는 회전한 각도를 기록해 가면서 임의 벡터를 X축 까지 회전시키고 그 회전 각도와 원래의 벡터 크기를 해로 해서 얻는다.

좀 더 쉽게 설명하기 위해 그림과 수식을 첨부한다.

기본 아이디어는 아래와 같다.

그림참조 : http://en.wikibooks.org/wiki/Digital_Circuits/CORDIC

2차원에서 시작을 (1,0) 으로 하고 각도를 θ (theta) 라고 하면 우리는 임의의 좌표 (cosθ, sinθ )를 얻을 수 있다.

그림참조 : http://en.wikibooks.org/wiki/Digital_Circuits/CORDIC

한단계 더 나아가서 시작점을 (1,y)로 두고 y = 0일대까지 회전하면 각도는 tan^-1(y) 가 된다.

이를 바탕으로 임의 (x,y)에서 다른 임의의 점 (x',y')를 나타내면

x' = x*cos(θ ) - y*sin(θ )

y' = y*cos(θ ) + x*sin(θ )

로 (x',y')를 나타낼 수 있고 (헉헉...) 삼각함수 공식인 sin(θ )/cos(θ ) = tan(θ ) 에 의해서 다시 식을 바꾸면

x' = cos(θ )*[x - y*tan(θ )]

y' = cos(θ )*[y + x*tan(θ )]

가 되는 것이다. (헉헉... 먼가 어려워 보이지만 우리가 중학교 때 배웠던 삼각함수 공식들이다 .. 난 이전에 멀 공부한거니ㅠ)

일단 핵심이 되는 첫번째 공식을 얻었고 두번째 원리를 찾아보자.

사실 두번째는 나도 이해가 안가서 자료 그대로 올린다.(ㅠ 눙물.. )

 cos(θ )

- Reduces the magnitude of the vector

- If dont' multiply -> pseudo rotation

tan(θ )

- Rotates the vector

- Break θ  into a series of successively shrinking angles ai such that tan(ai) = 2^-i

으악.. 해석 안된다. 하지만 이해는 했다. 수학이 좋은게 참 세계 공용어라는거!!!

핵심은 

tan(ai) = 2^-i  or ai = tan^-1(2^-1)

이거다!!

이걸 해석하면 아래와 같다.

i를 증가시켜서 ai 를 점차 감소시키면 어떤 각도(θ )도 만들어 낼 수 있다는 것이 바로 위의 공식이 되시겠다. 식으로 다시 정리하면 

θ = ±a0±a1±a2 ..... ±a9

정확도는 아래 식에 의해서 

ai ≤ SNj=i+1 (ai+1)

10^-5 deg accuracy 이다.

위 식을 통해 예를 들어 설명하면 아래와 같다.

θ  = 30.0도 라고 가정했을 때 

a0 = 45.0 ( > 30.0 ) 30도 보다 크므로 다음 음수

45.0 - 26.6  = 18.4 ( < 30.0 ) 30도 보다 작으므로 다음 양수

18.4 + 14.0  = 32.4 ( > 30.0 ) 30도 보다 크므로 다음 음수

32.4 - 7.1  = 25.3 ( < 30.0 ) 30도 보다 작으므로 다음 양수

.

.

.

θ  = 30는 

45.0 - 26.6 + 14.0 - 7.1 + 3.6 + 1.8 - 0.9 + 0.4 - 0.2 + 0.1 = 약30.1 로 계산이 된다. 

그럼 위에 나온 첫번째 식과 두번째 원리를 이용하여 정리하면 

두번째 원리에 의해 

θ  = ±ai 

이므로 첫번째 식은 

x' = cos(ai)*[x - y*di*tan(ai)]

y' = cos(ai)*[y + x*di*tan(ai)]

di = ±1

가 되고 위에서 뽑아낸 기본 원리에 의해 

tan(ai) = 2^-i 

식을 한번 더 정리하면

x' = cos(ai)*[x - y*di*2^-i]

y' = cos(ai)*[y + x*di*2^-i]

di = ±1

가 된다. 여기서 cos(ai)를 Ki로 치환 하면

(참고 cos(ai) = cos(-ai) )

식은 다음과 같다.

x' = Ki*[x - y*di*2^-i]

y' = Ki*[y + x*di*2^-i]

Ki = cos(ai) = cos( tan^-1(2^-1) )

di = ±1

오메 힘들다... 드뎌 뽑아낸 식이 다음과 같은데 아직 끝난게 아니다. cos이 들어가는 Ki가 남아 있지 않은가?!

Ki = cos(ai) = cos(-ai)

이므로 매번 i값이 변할 때마다 계속 곱한다는 것을 수식으로 나타내면 

n이 무한대로 갔을 때 K 값은 하나의 상수로 나타 낼 수 있게 된다.

아 힘들다... 거의 다 왔다.

위의 것을 정리하는 최종 알고리즘은..........

다음 포스팅에서 계속 설명한다.