벡터-라디ix FFT 알고리즘

벡터-라딕스 FFT 알고리즘은 다차원 고속 푸리에 변환(FFFT) 알고리즘으로, 일반 쿨리–의 일반화다.변환 치수를 임의 방사선으로 나누는 Tukey FFT 알고리즘.다차원(MD) 이산 푸리에 변환(DFT)을 연속적으로 작은 MD DFT로 세분화하여 궁극적으로 사소한 MD DFT만 평가하면 된다.^[1]

가장 일반적인 다차원 FFT 알고리즘은 한 인덱스에서 배열을 먼저 변환한 다음 다른 인덱스에서 FFT에서 더 많은 것을 보는 것을 의미하는 행-열 알고리즘이다.그 후 radix-2 직접 2-D FFT가 개발되었으며,^[2] 기존의 행-기둥 접근법에 비해 25%의 승수를 제거할 수 있다.그리고 이 알고리즘은 직사각형 배열과 임의 방사선으로 확장되었는데,^[3] 이것은 일반적인 벡터-라디믹스 알고리즘이다.

벡터-라디ix FFT 알고리즘은 행-벡터 알고리즘에 비해 복잡한 곱셈의 수를 크게 줄일 수 있다.For example, for a ${\displaystyle N^{M}}$ element matrix (M dimensions, and size N on each dimension), the number of complex multiples of vector-radix FFT algorithm for radix-2 is ${\displaystyle {\frac {2^{M}-1}{2^{M}}}N^{M}\log _{2}N}$, meanwhile, for row-column algorithm, it is $M{\displaystyle \frac{}{}}$ ${\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{M^{}}{}}$ ${\displaystyle \frac{{}^{}}{\mathrm{}}}$ ${\displaystyle {\log }_{}}$ ${\displaystyle {2\mathrm{}}_{}n}$ N ${\displaystyle {\frac {\m^{M}}\log _{$2}$N$ 그리고 일반적으로 이 알고리즘을 더 큰 레이디스와 더 높은 차원 어레이에서 작동할 때 곱셈에서 더 큰 절감을 얻는다.^[3]

전체적으로 벡터-라디칼리듬 알고리즘은 산술 연산이 약간 증가하더라도 더 나은 색인 체계를 가진 전통적인 DFT의 구조적 복잡성을 상당히 감소시킨다.그래서 이 알고리즘은 예를 들어 이미지 처리에서의 구현과 ^[4]고속 FFT 프로세서 설계에서의 구현과 같은 공학, 과학, 수학의 많은 애플리케이션에 널리 사용된다.^[5]

2-D DIT 케이스

쿨리와 마찬가지로-Tukey FFT 알고리즘, 2차원 벡터-라디ix FFT는 정규 2-D DFT를 "트위들" 인수로 곱한 더 작은 DFT의 합계로 분해함으로써 도출된다.

DIT(decimation-in-time) 알고리즘은 분해가 시간 $영역{\displaystyle }$ x ${\displaystyle$ x$}$에 기반함을 의미한다$.$ 자세한 내용은 Cooly–을 참조하십시오.Tukey FFT 알고리즘.

우리는 2-D DFT를 가정한다.

${\displaystyle X(k_{1},k_{2})=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x[n_{1},n_{2}]\cdot W_{N_{1}}^{k_{1}n_{1}}W_{N_{2}}^{k_{2}n_{2}},}$

where ${\displaystyle k_{1}=0,\dots ,N_{1}-1}$,and ${\displaystyle k_{2}=0,\dots ,N_{2}-1}$, and ${\displaystyle x[n_{1},n_{2}]}$ is a ${\displaystyle N_{1}\times N_{2}}$ matrix, and ${$$\displaystyle W_{N}=\exp(-j2\pi /N)}$.

단순성을 위해 ${\displaystyle {N\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$= ${\displaystyle {N\mathrm{}}_{}}$ ${\displaystyle 2{}_{}}$= N ${\displaystyle N_{1}=N_{2}=N}$및 radix-${\displaystyle }$( r ${\displaystyle \times }$ ${\displaystyle r}$) ${\displaystyle (r\time r$${\displaystyle }$/ ${\displaystyle r}$ ${\displaystyle N/r})$이 정수라고$$ 가정해 보자.

변수 변경 사용:

• ${\displaystyle n_{i}=rp_{i}+q_{i}}$, where ${\displaystyle p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;}$
• ${\displaystyle k_{i}=u_{i}+v_{i}N/r}$, where ${\displaystyle u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;}$

$여기$서 i${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle i=1$} 또는$$ $2{\displaystyle \mathrm{}}$ ${\displaystyle 2$ 2차원 DFT는 다음과 같이 기록할 수 있다.^[6]

${\displaystyle X(u_{1}+v_{1}}N/r,u_{2}+v_{2}N/r)=\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}\left[\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}x[rp_{1}+q_{1},rp_{1}+q_{1}]W_{N/r}^{1}^{1}u_{1}u_{1}:{1}W_{{{N/r}^{p_{2}u_{2}}\right]\cdot W_{{{N}^{{1}u_{1}}{1}+q_{2}u_{2}}:00}W_{r}^{q_{1}v_{1}:{1}:{1}:{1}:{1}W_{r}^{q_{2}v_{2}},}$

위의 방정식은 2-D DIT radix-${\displaystyle }$( ${\displaystyle r}$ ${\displaystyle \times }$ ${\displaystyle r}$) ${\displaystyle (r\time r)}$ $$"butterfly"(r\time r)의 기본 구조를 정의한다. (Cooley–의 1-D "butterfly" 참조)Tukey FFT 알고리즘)

${\displaystyle \mathrm{r}}$= 2 ${\$$displaystyle$ $r=2}$일$$때 방정식은 네 가지 합으로 나눌 수 있다: n ${\displaystyle {1\mathrm{}}_{}}$ ${\$}과$$ ${\displaystyle {n\mathrm{}}_{}}$ 2 ${\$$1}:{$}이$$ 짝수인$$ x 표본 위에 한 개, n $1{\displaystyle {}_{}}$ ${\$$displaystystyle$ $n_{$1}이 짝수이고, 이 중 ${\displaystyle {하나}_{}}$가 홀수인$$ 경우$n{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$${$$1}:{$1}은$$(는) ${\displaystyle {홀수}_{}}$이고 ${\displaystyle {n\mathrm{}}_{}}$ 2 {\displaystyle $n_$${1$}은(는$)$ 짝수이며$$,^[1] n 1 {\$displaystyle n_{$$1$}과$$ n ${\displaystyle {2\mathrm{}}_{}}$ ${\$2}} $모두$ 홀수인$$ 경우 다음과 같은 결과를 낳는다.

${\displaystyle X(k_{1},k_{2}=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{{N}^{k_{1}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}},}$

where ${\displaystyle S_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/2-1}\sum _{n_{2}=0}^{N/2-1}x[2n_{1}+i,2n_{2}+j]\cdot W_{N/2}^{n_{1}k_{1}}W_{N/2}^{$$n_{2}k_{2}.$$}$

2-D DIF 케이스

마찬가지로 소멸 빈도(DIF, 산드라고도 함)-Tukey 알고리즘) 알고리즘은 분해가 주파수 $영역{\displaystyle }$ X ${\displaystyle$ X$}$에 기반함을 의미한다. 자세한 내용은 Cooley–을 참조하십시오$.$Tukey FFT 알고리즘.

변수 변경 사용:

• ${\displaystyle n_{i}=p_{i}+q_{i}N/r}$, where ${\displaystyle p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;}$
• ${\displaystyle k_{i}=ru_{i}+v_{i}}$, where ${\displaystyle u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;}$

여기서 $i{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle i=1}$ 또는$$ $2{\displaystyle \mathrm{}}$ ${\displaystyle 2}$및 DFT 방정식은 다음과 같이 기록할 수 있다.^[6]

${\displaystyle X(ru_{1}+v_{1},ru_{2}+v_{2})=\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}\left[\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}x[p_{1}+q_{1{}N/r,p_{1}+q_{1}}{{N/r]W_{r}^{q_{1}v_{1}:{1}}W_{r}^{q_{2}v_{2}}\오른쪽]\cdot W_{{N}^{p_{1}v_{1}{1}v_{2}V_{2}}W_{{N/r}^{p_{1}{1}W_{1}{{1}W_{N/r}}^{p_{2}u_{2},2}},}$

기타 접근법

split-radix FFT 알고리즘은 1-D DFT에 유용한 방법임이 입증되었다.그리고 이 방법은 벡터-라디칼 FFT에 적용되어 분할 벡터-라디칼 FFT를 얻었다.^[6][7]

기존의 2-D 벡터-라디칼 알고리즘에서는 지수 $k{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2 ${\$}}을 4개의 그룹으로$$ 분해한다.

${\displaystyle {\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}\\X(2k_{1}+1,2k_{2}}&:&{\text{odd-even}\\X(2k_{1}+1,2k_{2}+1)&:&{\text{data-closed}\end{array}}}$

분할 벡터-라딕스 알고리즘에 의해 처음 3개 그룹은 변경되지 않고, 네 번째 홀수 그룹들은 추가로 다른 4개의 하위 그룹으로 분해되며, 총 7개의 그룹:

${\displaystyle {\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}\\X(2k_{1}+1,2k_{2}}&:&{\text{odd-even}\\X(4k_{1}+1,4k_{2}+1)&:&{\text{odd-odd}\\X(4k_{1}+1,4k_{2}+3)&:&{\text{odd-odd}\\X(4k_{1}+3,4k_{2}+1)&:&{\text{odd-odd}\\X(4k_{1}+3,4k_{2}+3)&:&{\text{data-closed}\end{array}}}$

즉, 2-DIT radix-${\displaystyle }$( ${\displaystyle 2}$ ${\displaystyle \times }$ ${\displaystyle 2}$) ${\displaystyle (2\time$2$)$방정식$$, S ${\displaystyle {11}_{}}$(${\displaystyle {k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}}$k ${\displaystyle {2\mathrm{}}_{}}$) W ${\displaystyle {}_{}^{}}$ ${\displaystyle k_{}^{}}$ ${\displaystyle {{1\mathrm{}}_{}}_{}^{}}$+ ${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {{2\mathrm{}}_{}}_{}^{}}$ ${\$의 네 번째 용어를 의미한다.$W_{N}^{k_{1}+k_{2$}}: 다음과 같이 된다$$.^[8]

${\displaystyle A_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}+A_{13}(k_{1},k_{2})W_{{N}^{k_{1}+3k_{2}}+A_{31}(k_{1},k_{2})W_{N}^{3k_{1}+k_{2}}}}+A_{33}(k_{1},k_{2})W_{N}^{3(k_{1}+k_{2}})},}$

where ${\displaystyle A_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/4-1}\sum _{n_{2}=0}^{N/4-1}x[4n_{1}+i,4n_{2}+j]\cdot W_{N/4}^{n_{1}k_{1}}W_{N/4}^{n_$${2}k_{2}}:}$

그런 다음 N DFT에 의한 2-D N은 위의 분해를 마지막 단계까지 연속적으로 사용하여 얻는다.

분할 벡터 라딕스 알고리즘은 벡터 라딕스 알고리즘과 비교했을 때, 일반적인 ${\displaystyle 1024}$ ${\displaystyle \times }$ $[\displaystyle 1024\times 1024}$ 어레이에$$ 대해 약 30%의 복합 승수와 약 동일한 개수의 복합 추가물을 절약한 것으로 나타났다.^[7]

참조