▲

GN⁺: CORDIC 알고리즘이 내 머릿속에 고정적으로 자리 잡은 이유

 (github.com/francisrstokes)
3P by neo 6달전 | favorite | 댓글 1개

CORDIC 알고리즘이 내 마음속에 무상으로 사는 이유

Fixed Point를 사용하여 Floating Point 회피

  • Floating Point가 아닌 Fixed Point를 사용하면 실수를 표현할 수 있음
  • 32비트 정수형을 사용하여 상위 16비트는 정수부, 하위 16비트는 소수부로 나누어 사용
  • 이를 통해 약 -32768.99997 부터 32767.99997 까지 표현 가능
  • 프로그래머가 부호점의 위치를 지정하여 정밀도를 조절할 수 있음
  • Float를 Fixed Point로 변환하려면 2^16을 곱한 후 int32_t로 캐스팅
  • Fixed Point를 Float로 변환하려면 2^16으로 나누기
  • 덧셈과 뺄셈은 그대로 동작하며, 곱셈과 나눗셈은 Scaling Factor를 조절해주어야 함

CORDIC 알고리즘 개요

  • CORDIC은 "Co-ordinate Rotation Digital Computer"의 약자로, 1950년대 중반에 개발됨
  • 단위원 위의 벡터를 점진적으로 작은 각도로 회전시켜 사인과 코사인 값을 구하는 방법
  • 이진 탐색과 유사하게 목표 각도에 가깝도록 큰 각도로 이동한 후, 시계 방향 또는 반시계 방향으로 각도를 절반씩 줄여가며 수렴
  • 최대 회전 각도를 90도(π/2 radian)로 하고, 16번 반복하여 목표 각도에 가깝게 수렴
  • 수렴된 벡터의 y값은 대략 sin(a)이고, x값은 대략 cos(a)임

상수 곱셈만 사용하도록 행렬 단순화

  • 회전 행렬에는 사인, 코사인, 탄젠트 함수가 포함되어 있어 계산이 복잡함
  • 탄젠트 함수는 고정된 각도로 회전하므로 미리 계산하여 테이블에 저장 가능 (64바이트 정도)
  • 코사인 항은 모든 반복에서 발생하지만, 수렴값이 상수(약 0.6366)이므로 마지막에 한 번만 곱해주면 됨

Shift와 Add 연산만 사용하기

  • 탄젠트 함수에 사용되는 각도를 아크탄젠트 함수를 사용하여 2^-i 값으로 선택
  • 이를 통해 곱셈 대신 비트 시프트 연산으로 대체 가능
  • 코사인 항의 수렴값도 다시 계산하여 약 0.60725가 되며, 초기 벡터의 x값으로 설정
  • CORDIC 알고리즘의 각 반복은 다음과 같이 단순화됨
    • z가 0 이상이면 반시계 방향으로 회전 (x에서 y>>i 빼기, y에 x>>i 더하기)
    • z가 0 미만이면 시계 방향으로 회전 (x에 y>>i 더하기, y에서 x>>i 빼기)
    • 테이블에서 각도 값을 빼거나 더해 z 업데이트
  • 이를 통해 상수 곱셈과 비트 시프트, 덧셈 연산만으로 삼각 함수 계산이 가능해짐

GN⁺의 의견

  • CORDIC은 임베디드 시스템이나 FPGA 등 제한된 하드웨어 자원을 가진 환경에서 유용하게 활용될 수 있는 알고리즘으로 보임. 특히 부동소수점 연산이 지원되지 않는 경우 고려해볼만한 방법.
  • 탄젠트 함수의 각도를 전략적으로 선택하여 곱셈을 비트 시프트로 대체하는 아이디어가 인상적. 수학적 통찰과 컴퓨터 아키텍처에 대한 이해가 결합된 좋은 사례.
  • 삼각함수 뿐 아니라 로그, 지수, 제곱근 등 다양한 함수 계산에도 활용될 수 있다는 점도 흥미로움. 관련 알고리즘인 BKM도 함께 살펴보면 좋을 듯.
  • 다만 최신 하드웨어에는 이미 FPU가 내장되어 있는 경우가 많고, 고정소수점 연산을 사용할 경우 정밀도 손실이 발생할 수 있으므로 적용 시 주의가 필요해보임.
  • 비슷한 계산을 많이 수행해야 하는 시스템이라면 CORDIC 전용 하드웨어 설계를 고려해볼 수도 있을 것 같음.
▲
neo 6달전  [-]
Hacker News 의견

  • CORDIC 알고리즘은 FPGA뿐만 아니라 게임 개발이나 분산 물리 시뮬레이션 등에도 활용 가능함. 부동 소수점 계산은 플랫폼 간 결정론적 동작을 보장하기 어려운데, 고정 소수점 물리 엔진을 구현하고 CORDIC으로 삼각 함수를 구현하는 것이 한 가지 해결책이 될 수 있음.

  • CORDIC은 사인, 코사인 뿐만 아니라 로그, 지수, 제곱근, 벡터 크기, 극좌표-직교좌표 변환, 벡터 회전 등 다양한 연산에 활용 가능함. 사원수(쿼터니언)를 이용하면 CORDIC 기반 연산을 더 효율적이고 정확하게 수행할 수 있을 것으로 보임.

  • 고등학교 예비 미적분 수업에서 계산기의 삼각함수 구현에 대해 배웠는데, 테일러 급수가 아니라 사실은 CORDIC이었다는 것을 알고 TI Basic으로 직접 구현해 본 경험담 공유.

  • 2023년 현재 STM32G4 같은 저가형 MCU에도 FPU가 내장되어 있어서 고정 소수점 대신 부동 소수점을 자유롭게 쓸 수 있음. 하지만 G4에는 전용 하드웨어로 구현된 CORDIC 주변장치도 있는데, 이는 부동 소수점 정밀도 손실을 피하기 위한 것으로 보임.

  • 22.75° 회전은 45° 회전 후 -22.5° 회전과 같다는 설명에 오류가 있는 것 같음. 22.5°가 맞는 것 같음.

  • Meagher의 옥트리 시스템은 정수 곱셈/나눗셈 없이 정수 연산만으로 구현되었음. 이는 옥트리 표현을 위한 빠르고 주문 제작된 VLSI 그래픽 가속 하드웨어 제작을 용이하게 함.

  • CORDIC은 각도에 대한 Farey 수열(또는 mediant, naive 분수 합)과 비슷한 개념으로 볼 수 있음.

  • CORDIC은 4비트 CPU를 탑재한 빈티지 프로그래머블 HP 계산기에서도 구현되었음. 사인 함수의 테일러 전개를 이용한 근사법도 프로그래밍 가능함.

  • 이 글이 마음에 들었다면 수학 알고리즘을 예제와 함께 설명한 도널드 커누스의 명저 "The Art of Computer Programming"을 읽어보는 것도 좋음.

  • CORDIC은 예전 DSP 분야에서 큰 인기를 끌었던 알고리즘임.

  • 멋진 알고리즘이며, 낮은 성능의 하드웨어에서 신경망을 실행하는 데에 유용할 것 같음.

답변달기