디지털신호처리 - Chapter 12: The Fast Fourier Transform; Speed and Precision Comparisons

12장: 고속 푸리에 변환 속도 및 정밀도 비교 DFT가 상관에 의해 계산될 때(표 12-2에서와 같이) 프로그램은 각각 N 포인트를 통해 실행되는 두 개의 중첩 루프를 사용합니다. 즉, 총 연산 횟수는 N 곱하 기 N 에 비례합니다 . 따라서 프로그램을 완료하는 데 걸리는 시간은 다음과 같이 지정됩니다. 여기서 N 은 DFT의 포인트 수이고 k DFT 는 비례 상수입니다. 사인 및 코사인 값이 중첩 루프 내 에서 계산되면 k DFT 는 100MHz의 Pentium에서 약 25마이 크로초와 같습니다. 사인 값과 코사인 값 을 미리 계산 하여 조회 테이블에 저장하면 k DFT 가 약 7마이크로초로 떨어집니다. 예를 들어, 1024 포인트 DFT는 포인트당 약 25초 또는 거의 25밀리초가 필요합니다. 느리다! 이 동일한 전략을 사용하여 FFT의 실행 시간을 도출할 수 있습니다. 비트 반전에 필요한 시간은 무시할 수 있습니다. 각 Log 2 N 단계에는 N /2 버터플라이 계산이 있습니...