Split-radix FFT 알고리즘

split-radix FFT는 이산 푸리에 변환(DFT)을 계산하기 위한 고속 푸리에 변환(FFT) 알고리즘으로, 처음에 R에 의해 거의 인정받지 못했던 논문에 처음 설명되었다. 야브네(1968년)와 그 후 1984년 여러 저자에 의해 동시에 재발견되었다.(이들 중 두 명의 재창조자인 P에 의해 "split radix"라는 이름이 만들어졌다. 듀하멜과 H. 홀만.) 특히 스플릿 라디스는 쿨리-큐리-의 변종이다.레이더 2와 4의 혼합을 사용하는 Tukey FFT 알고리즘: 길이 N/2의 작은 DFT 1개와 길이 N/4의 작은 DFT 2개로 길이 N의 DFT를 재귀적으로 표현한다.

스플릿-라디ix FFT는 그 변동과 함께 오랫동안 N 크기의 DFT를 계산하기 위해 발표된 가장 낮은 산술 연산 카운트(필요한 실제 추가 및 승수의 총 정확한 수)를 달성하는 구별을 가지고 있었다. 원래의 스플릿-라딕스 알고리즘의 산술 카운트는 2004년에 개선되었다(N=64 [1][2]에 대한 손 최적화를 통해 J. Van Buskk의 미발표 작업에서 얻은 초기 이득으로), 스플릿 라딕스를 수정함으로써 여전히 새로운 최저 카운트를 달성할 수 있는 것으로 밝혀졌다(Johnson과 Frigo, 2007). 비록 산술 연산의 수가 컴퓨터에서 DFT를 계산하는 데 필요한 시간을 결정하는 유일한 요인(또는 필수적으로 지배적인 요인)은 아니지만, 가능한 최소 카운트의 문제는 오랜 이론적 관심사다. (현재 작업 카운트에 대한 엄격한 하한이 입증되지 않았다.)

스플릿-라디ix 알고리즘은 N이 4의 배수일 때만 적용할 수 있지만, DFT를 더 작은 DFT로 분해하기 때문에 원하는 대로 다른 FFT 알고리즘과 결합할 수 있다.

스플릿-라믹스

DFT는 다음 공식에 의해 정의된다는 점을 상기하십시오.

${\displaystyle X_{k}=\sum _{n=0}^{{N-1}x_{n}\오메가 _{N}^{nk}}}}}$

여기서 $k{\displaystyle }$ ${\$$displaystyle k}$은(는) $0{\displaystyle \mathrm{}}$ {\$displaystyle$ 0$}$에서${\displaystyle }N{\displaystyle }$ - 1$${\$displaystyle N-1}$에 이르는 $정수$이며 ${\displaystyle {\Omega }_{}}$ N$${\$displaystyle \omega_{N}$은 통합의 원시 뿌리를 나타낸다.

${\displaystyle \omega_{N}=e^{-{\frac {2\pi i}{N}}}}$

따라서: $\Omega {\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$= ${\displaystyle 1}$ ${\displaystyle \omega _{N}^{N}=1$

split-radix 알고리즘은 이 합계를 세 개의 작은 합산으로 표현함으로써 작동한다. (여기서, 우리는 스플릿-라디ix FFT의 "시간 내 소멸" 버전을 제공한다. 주파수 버전의 이중 소멸은 본질적으로 이러한 단계의 역순에 불과하다.)

First, a summation over the even indices ${\displaystyle x_{2n_{2}}}$. Second, a summation over the odd indices broken into two pieces: ${\displaystyle x_{4n_{4}+1}}$ and ${\displaystyle x_{4n_{4}+3}}$, according to whether the index is 1 or 3 modulo 4. 여기서 $n{\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\$은(는) 0 ~ $N{\displaystyle }$/ m${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle N/m-1}$ 사이의 인덱스를 나타낸다$$$.$ 그 결과 합계는 다음과 같다.

${\displaystyle X_{k}=\sum _{n_{2}=0}^{N/2-1}x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}}$

여기서 우리는 $\Omega {\displaystyle {}_{}^{}}$ ${\displaystyle N_{}^{}}$ m ${\displaystyle n_{}^{}}$ k${\displaystyle {}_{}^{}}$= ${\displaystyle {\Omega }_{}^{}}$ N${\displaystyle {}_{}^{}}$/ ${\displaystyle m_{}^{}}$ n ${\displaystyle k_{}^{}}$ ${\$라는 사실을 사용했다$.$ 이 세 가지 합은 라딕스-2(크기 N/2)와 라딕스-4(크기 N/4) 쿨리의 일부에 해당한다.Tukey steps. (근본적인 생각은 radix-2의 짝수 지수 보조변환기는 앞에 승화 요인이 없으므로 그대로 두어야 하며, radix-2의 홀수 지수 보조변환형은 2차 재귀분할을 결합하여 편익을 얻어야 한다는 것이다.)

이 더 작은 합계는 현재 길이가 정확히 N/2와 N/4인 DFT로 재귀적으로 수행된 후 재결합할 수 있다.

More specifically, let ${\displaystyle U_{k}}$ denote the result of the DFT of length N/2 (for ${\displaystyle k=0,\ldots ,N/2-1}$), and let ${\displaystyle Z_{k}}$ and ${\displaystyle Z'_{k}}$ denote the results of the DFTs of length N/4 (for ${\$$displaystyle$ k=0$,\ldots,N/4-1}.$ 그러면 출력 $X{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$는 다음과$$ 같다.

${\displaystyle X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}.}$

이후 k≥ N/4{\displaystyle k\geq N/4}k<>로 많은 계산을 공유하기를 하지만, 이것,;N/4{\displaystyle k<, N/4}이다. 우리는 k에 N/4을 추가하는 동안size-N/2 DFT에는 변함이 없습니다 만약 우리가 k.에 N/2를 더하면 특히size-N/4 DFTs,(왜냐하면 그들은 km그리고 4.9초 만의 정기이다)이 변하지 않고 불필요한 계산을 수행하는. 따라서 변화되는 것은 $\Omega {\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ k ${\$ ${\displaystyle {\Omega }_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle 3_{}^{}}$ k$${\$displaystyle \omega _{$N}^{$3k}}}}}$의 용어뿐이며, 트위들 인자로 알려져 있다. 여기, 우리는 다음과 같은 정체성을 사용한다.

${\displaystyle \omega_{N}^{K+N/4}=-i\omega_{N}^{k}}}$

${\displaystyle \omega_{N}^{3(k+N/4)}}=i\omega _{N}^{3k}}}$

마침내 다음 단계에 도달하려면:

${\displaystyle X_{k}=U_{k}+\왼쪽(\omega _{N}^{K}Z_{k}+\omega _{N}^{3k}Z'_{k}\오른쪽),}$

${\displaystyle X_{k+N/2}=U_{k}-\left(\omega _{N}^{K}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}$

${\displaystyle X_{k+N/4}=U_{k+N/4}-i-left(\omega _{N}^{k}-\omega _{N}^{3k}Z'_{k}\right),}}$

${\displaystyle X_{k+3N/4}=U_{k+N/4}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\오른쪽),}$

위의 네 가지 식에서$$ $k{\displaystyle \mathrm{}}$ ${\displaystyle 0$$}$에서 N${\displaystyle }$/ ${\displaystyle 4\mathrm{}}$- ${\displaystyle 1}$까지 범위를$$ 지정할 경우$$ 출력 $X{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$$displaystyle X_{k$$}}$이(가$)$ 모두 제공됨

이러한 표현들이 배열되어 있기 때문에 우리는 나비라고 알려진 추가와 소급 쌍에 의한 다양한 DFT 산출물을 결합할 필요가 있다. In order to obtain the minimal operation count for this algorithm, one needs to take into account special cases for ${\displaystyle k=0}$ (where the twiddle factors are unity) and for ${\displaystyle k=N/8}$ (where the twiddle factors are ${\displaystyle (1\pm i)/{\sqrt {2}}}$ and can be mulTIP(tipleded more fast); 예를 들어, Sornsen 등(1986)을 참조하십시오. $\pm {\displaystyle }$ ${\displaystyle 1}$ ${\displaystyle \pm 1}$ 및$$${\displaystyle }$± ${\displaystyle i}$ ${\displaystyle \pm i}$에 의한 승수는 일반적으로 무료로 계산된다$$(추가사항을 소산하여 모든 부정을 흡수하거나 그 반대로).

이 분해는 N이 2의 검정력일 때 재귀적으로 수행된다. The base cases of the recursion are N=1, where the DFT is just a copy ${\displaystyle X_{0}=x_{0}}$, and N=2, where the DFT is an addition ${\displaystyle X_{0}=x_{0}+x_{1}}$ and a subtraction ${\displaystyle X_{1}=x_{0}-x_{1}}$.

이러한 고려사항으로 계산하면 4 ${\displaystyle N}$ ${\displaystyle {\log }_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle N}$- 6 ${\displaystyle N}$+ 8 $(\displaystyle 4N\log _{2}N-6N+8}$ 실제$$ 추가 및 승수가 2가 된다. 이 카운트는 홀수 2의 경우 나머지 인자 2(N을 4로 나눈 모든 분할 반지름 단계 이후)가 DFT 정의에 의해 직접 처리되거나(실제 추가 및 승수 4개) 라딕스-2 쿨리–에 의해 동등하게 처리된다고 가정한다.Tukey FFT 스텝.

참조

• Proc에서 R. Yavne, "분리형 푸리에 변환을 계산하는 경제적인 방법". AFIPS 폴 조인트 컴퓨터 콘센트 33, 115–125 (1968년)
• P. Duhamel과 H. 홀만, "Split-radix FFT 알고리즘", 일렉트로닉. 상트 20 (1), 14–16 (1984)
• M. 베터리와 H. J. 누스바우머, "작동 횟수를 줄인 간단한 FFT 및 DCT 알고리즘," 신호 처리 6(4), 267–278(1984).
• J. B. Martens, "Recursive cyclotomic factorization - 이산 푸리에 변환을 계산하기 위한 새로운 알고리즘," IEEE Trans. 음향, 음성, 신호 처리 32 (4), 750–761 (1984).
• P. Duhamel과 M. 베테르리, "패스트 푸리에 변환: 튜토리얼 리뷰와 최첨단 기술" (1990) 신호 처리 19, 259–299 (1990).
• S. G. 존슨과 M. 프리고, "산술 연산이 적은 수정된 스플릿-라믹스 FFT," IEEE Trans. 신호 처리. 55 (1), 111–119(2007)
• Douglas L. Jones, "Split-radix FFT 알고리즘", Connexions 웹 사이트(2006년 11월 2일).
• H. V. Sornsen, M. T. Heideman, C. S. Burrus, "Split-radix FFT, IEEE Trans"를 계산하는 중. 음향, 음성, 신호 처리 34(1), 152–156(1986).