나비 연산의 회전 인자 계산: 회전 인자는 WnkN(nk는 위 첨자, N은 아래 첨자), n은 원래 시퀀스의 특정 지점, k는 DFT 이후의 시퀀스(또는 FFT) 특정 지점에서 N은 변환된 지점의 개수입니다. WnkN=e^[-j*2pi*n*k/N], 이는 복잡한 지수항입니다.
do_fft 함수:
계산할 시퀀스의 길이가 2인 경우 두 위치는 x[0]+x[1] 및 x[0]-로 작성됩니다. x[1 각각 ] 그런 다음 반환합니다.
계산해야 하는 시퀀스의 전반부에서 do_fft 함수를 호출하세요.
계산해야 하는 시퀀스의 후반부 복사본에서 do_fft 함수를 호출하세요.
(int i=0; i x[i+length/2] *= Wi; 먼저 필요한 W를 결정해야 합니다. x[i] 및 x[i+length/2]는 x[i]+x[i+length/2] 및 x[i]-x[i+length/2]로 다시 작성됩니다. 각각 . 나비 매듭이라는 용어는 n점 이산 푸리에 연산에서 n점을 변환하기 위해 재귀적 방법을 사용하는 Cooley-Tukey 고속 푸리에 변환 알고리즘에서 여전히 가장 일반적으로 사용됩니다. 입력을 n=r*m으로 분해하고 입력 신호를 r점에서 m개의 신호 세트로 변환한 후 각각 r점 이산 푸리에 연산을 수행한다(즉, r점 DFT를 m번 수행한다). r점에서의 이산 푸리에 연산은 기본적으로 변환된 입력 신호에 회전 인자를 곱한 것이며 덧셈 연산은 나비매듭 구조로 이루어진다. (이상은 시간영역 추출법의 연산방식이다. 역연산은 먼저 나비매듭 구조에서 덧셈연산을 한 후, 회전계수를 곱하는 것인데, 이는 주파수영역 추출법의 연산방식이다.)