다차원 신호를 위한 빠른 알고리즘

다차원 신호^[1] 처리의 경우 1-D 디지털 신호 처리와 유사하게 Efficient 알고리즘이 있습니다.알고리즘의 효율성은 출력을 계산하는 데 필요한 계산 리소스의 양 또는 관심 있는 양으로 평가할 수 있습니다.이 페이지에서는 다차원 신호에 대한 매우 효율적인 두 가지 알고리즘에 대해 설명합니다.단순성과 설명을 위해 2-D 신호에 대해 설명합니다.그러나 M-D 신호에 대해서는 같은 이론이 유효합니다.각 알고리즘에 대한 정확한 계산 절감도 언급됩니다.

동기 및 응용 프로그램

디지털 시스템의 경우 입출력 관계를 설명하는 데 수학적 표현을 사용할 수 있고 알고리즘을 사용하여 이 관계를 구현할 수 있습니다.마찬가지로, 디지털 필터, 푸리에 변환, 히스토그램, 이미지 향상 등과 같은 다양한 변환을 구현하기 위해 알고리즘을 개발할 수 있습니다.이러한 입출력 관계 및 변환을 직접 구현하는 것이 반드시 이러한 관계를 구현하는 가장 효율적인 방법은 아닙니다.

사람들이 직접 구현을 통해 입력에서 산출물을 계산하기 시작했을 때, 그들은 더 효율적인 방법을 찾기 시작했습니다.이 Wiki 페이지는 다차원 신호 및 시스템에 대한 효율적이고 빠른 알고리즘을 보여주는 것을 목표로 합니다.다차원(M-D) 신호는 M 독립 변수의 함수로 모형화할 수 있으며, 여기서 M은 2보다 크거나 같습니다.이러한 신호는 연속 신호, 이산 신호 또는 혼합 신호로 분류할 수 있습니다.연속 신호는 일련의 값에 걸쳐 독립적인 변수의 함수로 모델링할 수 있습니다. 예를 들어, 공간을 이동하는 오디오 파형, 서로 다른 시간에 측정되는 3D 공간파 등입니다.반면에 이산 신호는 정수 집합과 같은 점 집합에만 정의된 함수로 모델링될 수 있습니다.이미지는 본질적으로 공간적인 2D 이산 도메인 신호의 가장 간단한 예입니다.

빠른 알고리즘의 맥락에서 아래의 예를 고려해 보십시오.

우리는 다음과 같이 주어진 A를 계산할 필요가 있습니다.

A = αθ + αθ + βθ + βθ 여기서 α, β, γ는 복소 변수입니다.

A를 계산하려면 4개의 복잡한 곱셈과 3개의 복잡한 추가가 필요합니다.위의 방정식은 다음과 같이 단순화된 형태로 쓸 수 있습니다.

A = (α + β) (γ + γ)

이 양식에는 1개의 복잡한 곱셈과 2개의 복잡한 추가만 필요합니다.

따라서 A를 계산하는 두 번째 방법은 A를 계산하는 첫 번째 방법에 비해 훨씬 효율적이고 빠릅니다.이것이 디지털 신호 처리 분야에서 빠른 알고리즘의 발전에 대한 동기입니다.결과적으로, 많은 실제 응용 프로그램은 빠른 계산을 위해 이러한 효율적인 알고리즘을 사용합니다.

문제 설명 및 기본 사항

선형 이동 불변 시스템(LSI)을 나타내는 가장 간단한 형태는 임펄스 응답을 통해 표현됩니다.이러한 LSI 이산 도메인 시스템의 출력은 입력 신호와 시스템의 임펄스 응답의 컨볼루션에 의해 제공됩니다.이것은 수학적으로 다음과 같이 표현됩니다.

$\"displaystyle y\left(n_{1}, n_{2}\right)=\sum _{l_{1}=-\infty }^{+\infty}x(l_{1}, l_{2})h(n_{1}-l_{2})$

$h(n_{1},n_{2})$ 서 h $h(n_{1},n_{2})$ 1 $h(n_{1},n_{2})$ $h(n_{1},n_{2})$ $){displaystyle$ h $(n_{1}, n_{2}}$ 는 $h(n_1,n_2)$ 시스템의 임펄스 응답입니다.

특정 지점( $y(0,0)$ ( $y(0,0)$ $,$ $y(0,0)$ ) {\ $displaystyle$ y $(0, 0$ $)}$ 에서 출력 값을 얻으려면 입력 $(l1, l2)$ 와 $x(l_{1},l_{2})$ 임펄스 $응답$ h $(-l1, -l2$ 의 여러 값을 곱해야 합니다.물론 이는 입력의 지원 영역과 임펄스 응답에 따라 달라집니다.여기서 주목해야 할 핵심은 1개의 출력 값을 얻기 위해 매우 많은 복잡한 곱셈과 추가를 수행해야 한다는 것입니다.

2-D 입력 신호의 $M\times M$ 가 $M\times M$ M × $M\times M$ ({\ $displaystyle$ M\ $times$ M}이고 $M\times M$ 시스템의 임펄스 응답의 $N\times N$ 가 $N\times N$ N × $N\times N$ ({n} $displaystyle$ N $\times$ N)이라고 $N\times N$ 가정하면 모든 출력 값을 얻으려면 $M^{2}N^{2}$ $M^{2}N^{2}$ N $^{2}$ N $^{2$ }} $회$ 곱셈을 $M^{2}N^{2}$ 해야 합니다.시스템의 일부 특성을 활용할 수 있는 경우 출력을 효율적으로 계산할 수 있습니다.

우리는 관심 신호의 이산 푸리에 변환을 계산해야 할 때 유사한 시나리오를 접합니다.

2-D DFT의 직접 계산은 단순히 이중 합계의 평가입니다.

$\"표시 스타일 X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{1}}^{n_{1}k_{1}}W_{N_{2}}^{n_{2}k_{2}}}$ $표시({style}{text})0\leq k_{1}\leq N_{1}-1{\text{ and }}0\leq k_{2}\leq N_{2}-1}$

${\style{text{where}}W_{N}\equiv{text{exp}}\left(-j{\frac{2\pi}{N}\right)} 표시$

직접 계산에 의해 이 2-D DFT를 평가하는 데 필요한 복잡한 곱셈 및 복잡한 추가의 총 $N_{1}^{2}N_{2}^{2}$ 는 $N_{1}^{2}N_{2}^{2}$ $N2$ {{ $1}^{2} N_{2}^{2$ 입니다. 그러나 이는 순진한 접근법입니다.우리는 이미 고속 푸리에 변환(FFT) 알고리듬을 사용하여 $N^{2}$ 보다 $N^{2}$ 적은 $N포인트 1-D DFT를$ 계산할 수 있다는 $N^{2}$ 것을 알고 있습니다.다음 섹션에서 설명한 것처럼 2D 이상의 DFT를 계산하기 위한 고속 푸리에 변환도 개발할 수 있습니다.

다차원 신호를 위한 빠른 알고리즘

DFT 평가를 위한 열기둥 분해법

이전 방정식의 DFT $X\left(k_{1},k_{2}\right)$ X ( $X\left(k_{1},k_{2}\right)$ 1 $X\left(k_{1},k_{2}\right)$ $X\left(k_{1},k_{2}\right)$ 2 $X\left(k_{1},k_{2}\right)$ ) \ $displaystyle$ X $\left(k_{1}, k_{2}\right)$ 도 $X\left(k_{1},k_{2}\right)$ 다음과 같은 형태로 쓸 수 있습니다.

$\"표시 스타일 X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}\left[\sum_{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}\right]W_{N_{1}}^{n_{1}k_{1}}$

G $G\left(n_{1},k_{2}\right)$ 1 $G\left(n_{1},k_{2}\right)$ $G\left(n_{1},k_{2}\right)$ 2 $){$ G $\left(n_{1}, k_{2}\right)}$ 가 $G\left(n_{1},k_{2}\right)$ 괄호 안의 양을 나타내며 다음과 같이 주어진다.

$G\left(n_{1},k_{2}\right)=\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}$

$X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}G\left(n_{1},k_{2}\right)W_{N_{1}}^{n_{1}k_{2}$

이 방법을 사용하면 $DFT$ X ${displaystyle$ X $}$ 를 $x$ 여러 개의 1-D DFT로 계산할 수 있습니다.즉, G ${displaystyle$ G $}$ 의 $g$ 각 열은 x ${displaystyle$ x $x$ $n_{1}$ 1{{ $displaystyle n_{1}}$ = $n_{1}$ 상수)의 해당 열의 1-D DFT로 간주할 수 있습니다.그리고 X ${displaystyle$ X $}$ 의 $x$ 각 행은 G ${displaystyle$ G $G$ 의 해당 행의 1-DFT입니다( $n_{2}$ 2 {{ $displaystyle n_{$ 2}} = $n_{2}$ 상수).따라서 우리는 2-D DFT를 행 DFT와 열 DFT로 분해하여 계산하고 있습니다.

M차원 신호의 M-D DFT를 평가하는 데에도 동일한 원리가 사용됩니다.

이제 이 접근 방식을 사용하여 얻을 수 있는 계산 비용 절감에 대해 이야기해 보겠습니다. $N_{1}N_{2}(N_{1}+N_{2})$ $N_{1}N_{2}(N_{1}+N_{2})$ + $){displaystyle$ N_ ${1}N_{2}(N_{1}+N_{2})}$ 개의 $N_{1}N_{2}(N_{1}+N_{2})$ 복잡한 추가와 곱셈이 $N_{1}N_{2}(N_{1}+N_{2})$ 한 것으로 관찰되었습니다.또한, 이러한 각 1-D DFT를 1-D FFT를 사용하여 계산하면, 복소 곱셈의 수는 N 1 $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$ $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$ $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$ 2 $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$ ⁡ $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$ $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$ N $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$ 2 2 {\ $displaystyle N_{1} N_{2}$ {\ $frac {log _{2} N_{2}}}(으$ )로 더 줄어들 수 있습니다.

벡터 Radix 고속 푸리에 변환

1-D FFT와 마찬가지로 2-D 신호의 경우 시간 소멸을 달성할 수 있습니다.길이가 2의 거듭제곱인 신호의 1-D DFT는 두 개의 반 길이 DFT로 표현될 수 있으며, 이들 각각은 다시 4분의 1 길이 DFT 등의 조합으로 표현될 수 있습니다.

2-D 신호의 경우 $(N_{1}{\text{ x }}N_{2})$ ( $N1$ x $)$ {{ $1}{\$ text{ $x}}N_$ ${2$ $}}$ DFT를 $(N_{1}{\text{ x }}N_{2})$ ${\frac {N_{1}}{2}}{\text{ x }}{\frac {N_{2}}{2}}$ 의 ${\frac {N_{1}}{2}}{\text{ x }}{\frac {N_{2}}{2}}$ ${\frac {N_{1}}{2}}{\text{ x }}{\frac {N_{2}}{2}}$ 로 표현할 수 있습니다. ${\text{x}}{\frac{N_2$ }} DFT ${\frac {N_{1}}{2}}{\text{ x }}{\frac {N_{2}}{2}}$ (N1_{ $2$ $})$ {\text ${$ $N_{2}$ $}}$ DFT( $N1$ }) {nstylease $}$ {n1 $}$ {n2 $N_{1}$ $}Display$ } { $stylease$ } {n1}입니다.2)의 거듭제곱단순성을 위해 $N_{1}=N_{2}=N$ $N_{1}=N_{2}=N$ = ${displaystyle$ N_ ${1$ }= $N_{2$ }= $N$ 을(를) 가정합니다.DFT 이중 합계는 네 개의 개별 합계로 분해될 수 있습니다. 하나는 $({$ 과 $n_{1}$ $({$ displaystyle $n_{2})$ 가 $n_{2}$ $모두$ $짝수$ 인 x $({$ displaystylex}) $x$ 에 $x$ 대한 것입니다. $n_{1}$ 는 $n_{1}$ n1({ $displaystyle n_{$ 1 $n_{1}$ })이고 $($ 2 $n_{2}$ })입니다. $({$ 이 $n_{1}$ 홀수이고 $({$ 가 $n_{2}$ 짝수이며 $({$ 과 $n_{1}$ $({$ 가 $n_{2}$ 홀수인 마지막 하나입니다.

이는 다음과 같이 기록됩니다.

 $X\left(k_{1},k_{2}\right)=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}}$

어디에

$S_{00}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}x(2m_{1},2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

$S_{01}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}x(2m_{1},2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

$S_{10}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}x(2m_{1}+1,2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

$S_{11}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}x(2m_{1}+1,2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

모든 $S_{00}S_{01}S_{10}$ $S_{00}S_{01}S_{10}$ $S_{00}S_{01}S_{10}$ $S_{00}S_{01}S_{10}$ {{ $00} S_{01} S_{10}$ 및 $S_{11}$ {{ $displaystyle S_{11}$ 은 $S_{00}S_{01}S_{10}$ $S_{11}$ $(k_{1},k_{2})$ ( $(k_{1},k_{2})$ , $) {displaystyle (k_{1,k_{$ 2 $(k_{1},k_{2})$ $})$ 에 있는 주기적이고 수평 및 수직 ${\frac {N}{2}}$ ${\frac {N}{2}}$ ${$ 입니다 ${\frac {N}{2}}$ 이 사실과 $W_{N}^{N/2}=-1,$ / $W_{N}^{N/2}=-1,$ $=$ - $,$ {\ $displaystyle$ W_ ${N$ }^{ $N/2$ }=-1 $,}$ 이라는 $W_{N}^{N/2}=-1,$ 사실을 사용하여 다음과 같은 정체성을 얻을 수 있습니다.

$X\left(k_{1},k_{2}\right)=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}}$

$X\left(k_{1}+{\frac {N}{2},k_{2}\right)=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}}$

$X\left(k_{1},k_{2}+{\frac{N}{2}}\right)=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}}$

$X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)=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}}$

위 방정식은 4개의 DFT 점 $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ + $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ + $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ X $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ + $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ + $)$ X\ $left(k_{1}, k_{2}\right) X\left(k_{1}+{\frac{N2}},$ K( $k2$ ), K $(k2$ )\right(k2)\x $($ )\x( $k2$ )\x1)\x(k2)\left(k2)\left(k1), $4개$ 의 점 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $,$ k $(k_{1},k_{2})$ 2 ) \ \ $displaystyle (k$ 1, $(k_{1},k_{2})$ 2 ) \ displaystyle (k $1,$ $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ k $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ ) $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ (K 1, $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 2 ) ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 1, K 2 ) ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 1, K 1 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ K 1 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ K 1 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ K 1, K 2) $(K$ 1, K 1) ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 1, K 1) $(K$ 1, K 1, K 1, K 2) ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 1, K 1, K 1, 10) K 1, K 1 $(k_{1},k_{2})$ , $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 1, 2 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ (K 1, 2) ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 1 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 2 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ ( $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ 1, 10 $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ ( $(k_{1},k_{2})$ $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ 1) $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $S_{01}(k_{1},k_{2})$ $S_{10}(k_{1},k_{2}){\text{ and }}$ $S_{00}(k_{1},k_{2})$ ${11}(k_{1},k_{2$ $){displaystyle$ S_ ${00}(k_{1},k_{2})}$ 는 $S_{00}(k_{1},k_{2})$ $)$ 스타일 $\({{2}회$ $S_{ij}$ $)\frac{N}\}$ 회 S_{ $J}$ 디스플레이 $\left({\frac {N}{2}}\times {\frac {N}{2}}\right)$ $S_{ij}$ ( $S_{ij}$ $)$ $Displaystystyleft$ )Displaystyleft{ $J}$ 일 수 있습니다.

따라서 $N\times N$ × $N\times N$ \ $displaystyle$ N \ $times$ N DFT는 $N\times N$ ${\frac {N}{2}}\times {\frac {N}{2}}$ 의 N ${\frac {N}{2}}\times {\frac {N}{2}}$ 2 × ${\frac {N}{2}}\times {\frac {N}{2}}$ \ $displaystyle$ { N { $2}$ \ $times$ { $N}$ DFT로 ${\frac {N}{2}}\times {\frac {N}{2}}$ 표현될 수 있음을 알 수 있습니다.

1-D 사례에서 유추하면, 아래 그림에 묘사된 계산은 $나비({$ $displaystyle$ ${text{butterfly}}$ 또는 ${\text{butterfly}}$ 더 $radix-(2\times 2){\text{ butterfly}}$ 는 $radix-(2\times 2){\text{ butterfly}}$ - $(2×$ butterfly {\ $text{butterfly}}$ 라고 불립니다.

각 버터플라이는 입력으로부터의 출력을 계산하기 위해 3개의 복잡한 곱셈과 8개의 복잡한 덧셈이 필요합니다.그리고 $k1$ $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ $k1, k2)$ 의 X ${$ $displaystyle$ X $}$ 의 $X$ $모든$ 샘플을 계산하려면, $S_{01}(k_{1},k_{2}),$ $S_{10}($ $k_$ ${1$ $},$ $k_{2}){\text$ ${$ $and }S_{11}(k_$ ${1$ $},k_{$ $2})}$ 의 $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ ${\frac {N^{2}}{4}}$ ${\frac {N^{2}}{4}}$ $계산$ 이 필요합니다 $.$

이 소멸 절차는 N ${displaystyle$ N $}$ 이 $N$ (가) 2의 거듭제곱일 때 $로그$ 2 $\log _{2}N$ ⁡ ${displaystyle \log_{2}N}$ 회 $\log _{2}N$ $\log _{2}N$ 됩니다.소멸의 각 단계는 N ${\frac {N^{2}}{4}}$ 나비로 ${\frac {N^{2}}{4}}$ ${\frac {N^{2}}{4}}$ 되어 $있습니다.$ 그리고 각각의 나비는 3개의 복소 곱셈과 8개의 복소 덧셈을 포함하므로 $(N\times N)$ ( $(N\times N)$ × N $)$ \" $표시$ 스타일 ( $N\times$ N $)}-$ 점 $(N\times N)$ $(2\times 2)$ 기수 ( $(2\times 2)$ × $)$ \" $표시$ 스타일 (2 \ $times$ 2)\" FFT를 계산하는 $동안$ 수행해야 하는 복소 $(2\times 2)$ 곱셈의 수는 다음과 같습니다.

${\times2}표시 스타일 C_{vectorRadix(2\times2)}=timesfrac{3N^{2}}{4}}\log_{2}N}$

참고 항목

레퍼런스

^ Bose, N.K., ed. (1985). Multidimensional Systems Theory, Progress, Directions and Open Problems in Multidimensional Systems. Dordrecht, Holland: D. Reidel Publishing Company.
^ Richard E의 신호 처리를 위한 빠른 알고리즘.Blahut, 캠브리지 대학 출판부 2010
^ ^a ^b ^c ^d 댄 E. 더전, 러셀 M.Merseau, "다차원 디지털 신호 처리", 프렌티스-홀 신호 처리 시리즈, ISBN 0136049591, 1983.

[1] Bose, N.K., ed. (1985). Multidimensional Systems Theory, Progress, Directions and Open Problems in Multidimensional Systems. Dordrecht, Holland: D. Reidel Publishing Company.

[fa-2] Richard E의 신호 처리를 위한 빠른 알고리즘.Blahut, 캠브리지 대학 출판부 2010

[dm-3] 댄 E. 더전, 러셀 M.Merseau, "다차원 디지털 신호 처리", 프렌티스-홀 신호 처리 시리즈, ISBN 0136049591, 1983.

[1]

Search

다차원 신호를 위한 빠른 알고리즘

네임스페이스

더

목차

동기 및 응용 프로그램

문제 설명 및 기본 사항

다차원 신호를 위한 빠른 알고리즘

DFT 평가를 위한 열기둥 분해법

벡터 Radix 고속 푸리에 변환

참고 항목

레퍼런스