CORDIC: shift와 덧셈으로 30도 회전을 쫓아가는 방법

벡터를 30도 돌리려면 sine과 cosine을 구하고 곱셈을 해야 할 것 같다. 그런데 회로의 각 단계가 하는 일이 shift와 덧셈뿐이어도 회전을 근사할 수 있다. CORDIC은 원하는 각도를 한 번에 만드는 대신, 크기가 줄어드는 작은 회전을 차례로 더한다. 곱셈기를 아끼는 대신 반복 횟수, 내부 정밀도, 크기 보정이라는 조건을 받아들이는 방식이다.

AMD의 CORDIC 제품 가이드 PG105는 이 작은 회전을 atan(2^-i) 각도의 micro-rotation으로 설명한다. 동일한 기본 연산을 여러 단계로 펼친 구조와 한 단계를 되풀이하는 구조도 구분한다. 아래 계산은 그 원리를 보기 위한 이상적인 수치 예이며, 특정 IP 설정의 실측 출력은 아니다. AMD CORDIC PG105, Functional Description 및 Architecture

tan 값이 2의 거듭제곱이면 생기는 일

원래 회전식은 x'=x cosθ−y sinθ, y'=y cosθ+x sinθ다. cosθ를 밖으로 묶으면 안쪽은 x−y tanθ와 y+x tanθ가 된다. tanθ=2^-i인 각도를 선택하면 y나 x에 곱하는 부분을 이진 shift로 바꿀 수 있다. 남은 공통 cosθ는 매 단계에서 생략하고 나중에 보정한다.

남은 목표 각도를 z라고 하고 회전 방향 d를 +1 또는 −1로 정하자. 여기서는 z가 양수이면 d=+1, 음수이면 d=−1인 부호 규칙을 쓴다. 한 단계의 관계는 다음과 같다.

x_next = x - d × y × 2^-i
y_next = y + d × x × 2^-i
z_next = z - d × atan(2^-i)

x_next와 y_next는 모두 같은 이전 단계의 x, y에서 계산한다. 소프트웨어에서 x부터 덮어쓰고 바뀐 x를 y 식에 사용하면 다른 연산이 된다. 회로에서도 두 출력의 데이터 의존성을 이 관계대로 만들어야 한다. 각도 상수 atan(2^-i)는 미리 준비할 수 있어 실행 중에 매번 삼각함수를 계산할 필요가 없다.

입력 벡터 (1,0), 목표 30도를 놓고 세 단계만 해 보자. i=0에서 atan(1)=45도이므로 양의 회전을 선택한다. 좌표는 (1,1), 남은 각도는 −15도가 된다. 목표를 지나쳤으니 i=1에서는 음의 회전을 선택한다. atan(1/2)는 약 26.565도이고, 좌표는 (1.5,0.5), 남은 각도는 약 11.565도다.

i=2에서는 다시 양의 방향으로 약 14.036도를 돌린다. 좌표는 (1.375,0.875), 남은 각도는 약 −2.471도다. 이 벡터의 방향은 약 32.471도다. 아직 30도에 도달하지 않았지만, 더 작은 회전으로 남은 각도를 줄여 가는 과정이 보인다. 목표를 넘었다고 앞 계산을 버리는 것이 아니라 다음 작은 회전의 부호를 바꾼다.

방향은 맞아 가는데 길이는 커진다

여기에는 생략한 cosθ의 비용이 숨어 있다. i번째 단계의 좌표 길이는 sqrt(1+2^-2i)배가 된다. 세 단계의 증가율을 곱하면 약 1.6298006이다. 위 좌표의 길이 sqrt(1.375²+0.875²)도 같은 값이다. 회전만 했다면 길이가 1이어야 하는데 그렇지 않다.

이 증가율은 해당 원형 회전의 반복 단계에 의해 정해져 방향 선택에 의존하지 않는다. 충분히 많은 표준 단계에서는 약 1.64676에 접근한다. 따라서 시작 벡터의 길이를 미리 줄이거나, 출력에 그 역수를 곱하는 방법으로 보정할 수 있다. 세 단계짜리 예에 무한 반복의 역수를 그대로 쓰면 정확한 세 단계 보정이 되지는 않는다.

PG105도 원형 회전 등의 결과에 스케일 팩터가 붙으며 이를 상쇄하는 선택 기능을 설명한다. ‘CORDIC으로 sine과 cosine을 계산했다’는 말만으로 출력이 이미 단위 길이인지 알 수 없다. 선택한 기능과 보정 설정을 함께 확인해야 한다. AMD CORDIC PG105, CORDIC Scale Factor

더 많은 반복만으로 해결되지 않는 부분

이상적인 식은 실수를 다루지만 실제 회로의 x, y, z는 유한 폭이다. shift에서 잘리는 하위 비트, 각도 상수의 양자화, 중간 좌표가 커지는 범위를 고려해야 한다. 반복을 늘리더라도 내부 폭이 부족해 작은 변화가 저장되지 않으면 기대한 정밀도를 얻지 못한다. 입력 자체의 오차도 반복으로 사라지지 않는다.

큰 각도도 별도 문제다. 선택한 회전 집합에는 수렴 범위가 있고, 원 전체를 다루려면 사분면 이동 같은 사전·사후 처리가 필요할 수 있다. PG105는 coarse rotation 옵션으로 입력 범위를 넓히는 방식을 제공한다. 앞의 30도 예는 그 처리를 논의하지 않아도 되는 작은 각도이지만, 이를 그대로 모든 입력 각도의 동작으로 확대할 수 없다.

회로 면적과 입력 처리 간격의 교환도 있다. 한 shift-add 단계를 재사용하면 여러 사이클에 걸쳐 한 벡터를 처리한다. 각 반복을 별도 단계로 펼치고 레지스터를 배치하면 여러 벡터를 겹쳐 처리할 수 있지만 단계 수만큼 회로가 필요하다. 완료까지의 사이클 수와 새 입력을 받는 간격은 서로 다른 지표다. 인터페이스의 대기까지 포함하면 실제 완료 시점은 추가로 변한다.

CORDIC의 재미는 삼각함수가 단순해진다는 데서 끝나지 않는다. 계산을 작은 회전의 누적으로 바꾸면서 정확도와 회로 구조를 함께 선택할 수 있다는 데 있다. shift와 add로 방향을 만들 수 있다는 사실에 스케일 보정, 수렴 범위, 비트 폭을 붙여야 비로소 원하는 회전의 답이 된다.