- CORDIC은 FPU나 큰 조회 테이블 없이
sin, cos, tan 같은 삼각함수를 계산하기 위해, 복잡한 연산을 덧셈과 비트 시프트 중심으로 바꾸는 알고리듬임
- 이 방식은 고성능 시스템보다 임베디드 환경, 특히 성능이 낮은 마이크로컨트롤러와 FPGA에서 유용하며, 속도만으로 가치를 판단하기 어려움
- 부동소수점 대신 고정소수점을 쓰면
int32_t의 상위 16비트를 정수부, 하위 16비트를 소수부로 나눠 약 -32768.99997부터 32767.99997까지 표현할 수 있음
- 벡터를 목표 각도에 맞춰 점점 작은 각도로 회전시키고,
atan(2**-i) 테이블 16개와 x=39796 초기값을 쓰면 반복마다 곱셈을비트 시프트로 대체할 수 있음
- 예시 각도
0.9152를 16회 반복하면 sin(0.9152) 절대 오차는 0.00000956, cos(0.9152) 절대 오차는 0.0000434 수준까지 줄어듦
CORDIC이 잘 맞는 계산 환경
- CORDIC은
sin, cos, tan 같은 삼각함수를 저전력 하드웨어에서 계산하기 위한 알고리듬임
- FPU, 즉 부동소수점 연산 장치가 없거나 큰 조회 테이블을 쓰기 어려운 환경에서도 동작함
- 실제 연산은 단순한 덧셈과 비트 시프트 중심으로 구성됨
- 벡터 수학, 삼각법, 수렴, 컴퓨터 과학적 아이디어를 결합해 복잡한 함수를 단순 연산으로 근사함
- 고성능 하드웨어에서는 이 기법이 꼭 필요하지 않을 수 있음
- 주요 적용 대상은 임베디드 환경임
- 특히 성능이 낮은 마이크로컨트롤러와 FPGA에 적합함
- 더 빠른 하드웨어나 주변장치가 있을 수도 있지만, 속도만이 유용성의 유일한 척도는 아님
부동소수점을 피하는 고정소수점 표현
sin(x)처럼 -1.0에서 1.0 사이 값을 내는 함수도 반드시 부동소수점으로 표현할 필요는 없음- 고정소수점은 정수 타입 안에서 소수점 위치를 고정해 유리수를 나타냄
- 예시는
int32_t를 상위 16비트 정수부, 하위 16비트 소수부로 나눔
- 이 경우 범위는 대략
-32768.99997부터 32767.99997까지임
- 소수점 위치를 어디에 두느냐에 따라 정수부 범위와 소수부 정밀도를 맞바꿀 수 있음
- 값 자체는 여전히
int32_t이며, 프로그래머가 비트 배열에 추가 의미를 부여함
고정소수점 변환과 기본 연산
- 소수 정밀도가 16비트라면
42.01 같은 float 값에 (1 << 16)을 곱해 고정소수점 값으로 만들 수 있음
42.01 * (1 << 16)은 int32_t로 캐스팅하면 2753167이 됨- 다시 float로 바꾸려면
2753167 / (1 << 16)을 계산해 약 42.0099945를 얻음
- 부동소수점을 전혀 쓰지 않고
1.5 같은 값을 직접 인코딩할 수도 있음
- 정수부
1은 (1 << 16)으로 올림
- 소수부 절반은
0x0000과 0xffff 사이의 중간값인 0x7fff로 둘 수 있음
- 이 방식의 결과는 십진수
98303임
- 같은 스케일링 계수를 쓰는 값끼리는 덧셈과 뺄셈이 그대로 동작함
- 곱셈은 두 고정소수점 값을 곱한 뒤 결과를 스케일링 계수만큼 다시 오른쪽으로 시프트함
- 나눗셈은 피제수를 스케일링 계수만큼 미리 왼쪽으로 시프트한 뒤 제수로 나누면 추가 정밀도를 얻을 수 있음
벡터 회전으로 삼각함수 근사하기
- CORDIC은 “co-ordinate rotation digital computer”의 약자이며, 1950년대 중반에 만들어짐
- 핵심 아이디어는 단위원 위에서 벡터를 점점 작은 각도로 회전시켜, 목표 각도에 도달했을 때 벡터 성분이 사인과 코사인 값이 되게 하는 것임
- 이 과정은 이진 탐색과 비슷하게 진행됨
- 목표 각도를 향해 큰 각도로 이동함
- 목표를 지나쳤는지 확인함
- 이후 더 작은 각도로 시계 방향 또는 반시계 방향 회전을 반복함
- 예시로
sin(0.7)을 구할 때는 초기 벡터 (1, 0)와 목표 0.7 라디안에서 시작함
- 먼저
0.7853 라디안, 즉 45˚를 반시계 방향으로 회전함
- 남은 목표는
0.7 - 0.7853 = -0.0853이 됨
- 값이 음수이므로 다음에는
0.3926 라디안, 즉 22.5˚를 시계 방향으로 회전함
- 이후 남은 목표의 부호에 따라
0.1963 라디안 등 더 작은 각도로 방향을 바꿔가며 회전함
- 16회 반복하면 벡터가 원래 목표 각도에 거의 맞춰지고,
y는 sin(a), x는 cos(a)의 근사가 됨
회전 행렬에서 비싼 연산 줄이기
- 일반적인 벡터 회전은 사인과 코사인이 들어간 행렬 곱셈을 사용함
- CORDIC은 삼각 항등식을 이용해 회전 행렬을
tan(a) 중심으로 바꿈
- 처음에는
45˚, 22.5˚, 11.25˚처럼 정해진 회전 각도를 쓰므로 tan(a) 값을 미리 계산한 테이블로 둘 수 있음
- 이 테이블은 16개의
uint32_t만 필요해 64바이트임
- 비교 대상으로,
-1부터 1까지 4096개 값을 담는 최적화되지 않은 sin(x) 테이블은 16KiB가 필요하고 정밀도도 낮다고 봄
- 회전마다 앞에 붙는
cos(a) 항은 반복마다 생기지만, 모두 곱한 값은 상수로 수렴함
45˚, 22.5˚, 11.25˚ 식의 각도를 쓸 때 이 곱은 약 0.6366임- 이 상수를 모든 반복 뒤에 한 번 곱하면 됨
시프트와 덧셈만 남기는 각도 선택
- 곱셈을 없애려면
tan(a) 결과가 항상 2의 역거듭제곱이 되도록 각도를 고름
- 이를 위해 각 반복
i=0부터 15까지 atan(2**-i) 값을 담은 16개 엔트리 테이블을 만듦
- 실제 회전 각도는
45˚, 26.565˚, 14.036˚, 7.125˚ 등이 됨
- 각도가 정확히 절반씩 줄어들지는 않지만, 이 각도들을 사용해도 과정은 올바른 결과로 수렴함
tan(a) 곱셈은 반복 번호 i만큼의 비트 시프트로 바뀜cos(a) 항들의 곱도 새 각도 선택에 맞춰 다시 계산됨
- 값은 약
0.60725임
- 16비트 고정소수점으로는
39796이 됨
- 마지막에 곱하는 대신 초기 벡터의
x를 1이 아니라 39796으로 설정하면 됨
알고리듬 절차
- 사전 계산 단계에서는 각 엔트리가
atan(2**-i)인 테이블을 만들고, 각 값을 고정소수점으로 변환함
- 변환식은
atan(2**-i) * (1 << 16)임
sin이나 cos를 구할 때는 입력 각도도 고정소수점으로 바꿈
- 예시
0.9152는 0.9152 * (1 << 16) = 59978이 됨
- 초기 상태는 다음과 같음
x = 39796
y = 0
z = 59978
z는 벡터의 일부가 아니라 남은 목표 각도를 추적하는 값임z의 부호가 회전 방향을 결정함
z >= 0이면 반시계 방향으로 회전하고 z -= table[i]를 수행함z < 0이면 시계 방향으로 회전하고 z += table[i]를 수행함
- 각 반복은
x와 y에 대해 덧셈, 뺄셈, >> i 시프트만 사용함
if z >= 0:
x_next = x - (y >> i)
y_next = y + (x >> i)
z -= table[i]
else:
x_next = x + (y >> i)
y_next = y - (x >> i)
z += table[i]
x = x_next
y = y_next
예시 수렴 결과와 남은 주제
0.9152 라디안 예시에서는 첫 반복에서 z가 양수이므로 약 0.785 라디안만큼 반시계 방향으로 회전함- 두 번째 반복에서도
z가 양수여서 약 0.436 라디안 반시계 방향으로 회전하지만 목표를 지나침
- 세 번째 반복에서는
z가 음수가 되어 약 0.244 라디안만큼 시계 방향으로 회전함
- 네 번째 반복도
z가 음수여서 약 0.124 라디안 시계 방향으로 회전함
- 각도 변화가 작아질수록 벡터는 실제 결과 가까이에서 앞뒤로 움직이며 수렴함
- 16회 반복 뒤
y는 sin(0.9152)의 매우 가까운 근사가 됨
- 사인 절대 오차는
0.00000956임
x의 코사인 절대 오차는 0.0000434임
- 다루지 않은 주제도 남아 있음
- 관심 각도가 단위원의 1사분면이나 4사분면 밖에 있을 때 필요한 특별 처리
- CORDIC 변형으로 계산 가능한
tan, atan, asin, acos, sinh, cosh, tanh, sqrt, ln, e^x
- 로그와 지수 계산을 위해 설계된 관련 알고리듬 BKM
- 관련 내용을 Low Byte Productions YouTube channel에서 더 자세히 다룰 계획이 있음