環形摺積 與線性摺積 類似，皆是針對兩個函數的運算子。假設兩個函數分別為f 與g ，則摺積運算過程即為將其中一個函數(如f )經過翻轉後，對於每個位移量，將重疊的部份相乘累加起來(見下文定義)。不同的地方在於環形摺積的位移為環形位移，而線性摺積的位移為平移。摺積亦可以視為滑動平移 的推廣。
兩個函數的環形摺積定義為對一個或兩個函數做週期延伸 後之摺積 運算，而所謂的週期延伸是指原來的函數平移固定長度的整數倍再全部加起來所產生的新函數。
x (t )經過週期延伸後之函數可寫成下式:
x
T
(
t
)
=
d
e
f
∑
k
=
−
∞
∞
x
(
t
−
k
T
)
=
∑
k
=
−
∞
∞
x
(
t
+
k
T
)
.
{\displaystyle x_{T}(t)\ {\stackrel {\mathrm {def} }{=}}\ \sum _{k=-\infty }^{\infty }x(t-kT)=\sum _{k=-\infty }^{\infty }x(t+kT).}
其中T 為週期(即週期延伸中的固定長度)
對x(t) 與h(t) 計算環形摺積的運算(
x
(
t
)
⊗
h
(
t
)
{\displaystyle x(t)\otimes h(t)}
y
(
t
)
=
∫
t
o
t
o
+
T
h
T
(
τ
)
⋅
x
T
(
t
−
τ
)
d
τ
=
∫
−
∞
∞
h
(
τ
)
⋅
x
T
(
t
−
τ
)
d
τ
=
d
e
f
x
T
(
t
)
∗
h
(
t
)
,
{\displaystyle {\begin{aligned}y(t)&=\int _{t_{o}}^{t_{o}+T}h_{T}(\tau )\cdot x_{T}(t-\tau )\,d\tau \\&=\int _{-\infty }^{\infty }h(\tau )\cdot x_{T}(t-\tau )\,d\tau \quad {\stackrel {\mathrm {def} }{=}}\quad x_{T}(t)*h(t),\end{aligned}}}
其中* 表示線性摺積運算子
此兩定義的等價關係證明如下:
∫
−
∞
∞
h
(
τ
)
⋅
x
T
(
t
−
τ
)
d
τ
=
∑
k
=
−
∞
∞
[
∫
t
o
+
k
T
t
o
+
(
k
+
1
)
T
h
(
τ
)
⋅
x
T
(
t
−
τ
)
d
τ
]
=
∑
k
=
−
∞
∞
[
∫
t
o
t
o
+
T
h
(
τ
+
k
T
)
⋅
x
T
(
t
−
τ
−
k
T
)
d
τ
]
=
∑
k
=
−
∞
∞
[
∫
t
o
t
o
+
T
h
(
τ
+
k
T
)
⋅
x
T
(
t
−
τ
)
d
τ
]
=
∫
t
o
t
o
+
T
[
∑
k
=
−
∞
∞
h
(
τ
+
k
T
)
⋅
x
T
(
t
−
τ
)
]
d
τ
=
∫
t
o
t
o
+
T
[
∑
k
=
−
∞
∞
h
(
τ
+
k
T
)
]
⋅
x
T
(
t
−
τ
)
d
τ
=
d
e
f
∫
t
o
t
o
+
T
h
T
(
τ
)
⋅
x
T
(
t
−
τ
)
d
τ
QED
{\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{T}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{T}(t-\tau )\ d\tau \right]\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot x_{T}(t-\tau -kT)\ d\tau \right]\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot x_{T}(t-\tau )\ d\tau \right]\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\cdot x_{T}(t-\tau )\right]\ d\tau \\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\right]\cdot x_{T}(t-\tau )\ d\tau \\&\ {\stackrel {\mathrm {def} }{=}}\ \int _{t_{o}}^{t_{o}+T}h_{T}(\tau )\cdot x_{T}(t-\tau )\ d\tau \quad \quad {\mbox{QED}}\end{aligned}}}
上述為針對兩個連續信號(函數)的環形摺積之定義的說明，類似的，我們對於週期為N 的離散信號之環形摺積(
x
[
n
]
⊗
h
[
n
]
{\displaystyle x[n]\otimes h[n]}
x
N
[
n
]
∗
h
[
n
]
=
d
e
f
∑
m
=
−
∞
∞
h
[
m
]
⋅
x
N
[
n
−
m
]
=
∑
m
=
−
∞
∞
h
[
m
]
⋅
∑
k
=
−
∞
∞
x
[
n
−
m
−
k
N
]
.
{\displaystyle {\begin{aligned}x_{N}[n]*h[n]\ &{\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }h[m]\cdot x_{N}[n-m]\\&=\sum _{m=-\infty }^{\infty }h[m]\cdot \sum _{k=-\infty }^{\infty }x[n-m-kN].\,\end{aligned}}}
離散信號的環形摺積可以結合快速傅立葉變換 與摺積理論 做相當有效率的計算，然而，在實際上信號處理 或系統理論的應用，線性摺積運算較常被考慮也較有物理意義，於是，如果可將一個線性摺積的計算問題轉化為求算環形摺積，則一般當兩個輸入信號長度相距不遠時，往往計算量可以大為減少，增加了計算線性摺積的效率，至於線性摺積與環形摺積的關係以及如何利用環形折積與傅立葉變換 求得線性摺積結果，將於下文進一步討論。
線性摺積與環形摺積之比較
编辑
線性摺積
编辑
連續信號線性摺積
(
f
⋆
g
)
(
t
)
=
∫
f
(
τ
)
g
(
t
−
τ
)
d
τ
{\displaystyle (f\star g)(t)=\int f(\tau )g(t-\tau )\,d\tau }
離散信號線性摺積
(
f
⋆
g
)
[
m
]
=
∑
n
f
[
n
]
g
[
m
−
n
]
{\displaystyle (f\star g)[m]=\sum _{n}{f[n]g[m-n]}}
對於一個線性非時變 (LTI)之系統，輸出的信號y (n )可以經由輸入信號x (n )與系統的脈衝響應 h (n )的線性摺積而得。
也因此，在實際的應用上，線性摺積的運算較為具有物理意義，如數位濾波器 的濾波過程即為一個線性摺積的運算。
環形摺積
编辑
環形摺積定義如前文所述，運算上是將線性摺積的頭尾相連變成環形，觀念上可想像為一個輸入在內環，另一個輸入在外環，然後每一個輸出的求得皆是經由內環與外環對應位置的乘加。計算下一個輸出則將內環固定不動，外環圓周位移一格，再做對應位置之乘加得到此輸出，以此類推。(圓環上的點數即為週期延伸的週期T 或N )
不管是線性摺積或環形摺積均有反折、位移、相乘並求和的運算，但線性摺積的位移是平移，環形摺積的位移則是圓周位移。除此之外，線性摺積並不要求兩序列長度相等，若x (n )長度為M ，h (n )長度為N ，則其摺積輸出y (n )長度為M +N -1，而環形摺積則要求兩輸入序列等長(假設為L )，且摺積輸出的長度也為L 。一般情況下，兩等長序列的環形摺積與線性摺積的結果是不同的(因為環形週期序列產生的影響)，但當L ≥M +N -1時，兩者的結果相同。
右圖為一個實際範例，可比較相同的兩輸入信號，線性摺積與環形摺積輸出的差異。
如何利用快速傅立葉變換計算線性摺積
编辑
由以上討論知道一般的情況，線性摺積與環形摺積的輸出結果並不會相同，且一般線性摺積較實用而有意義。然而離散信號的處理上，由於環形摺積可以藉由快速傅立葉變換較有效率的求得，所以兩輸入信號的線性摺積，如何利用環形摺積與快速傅立葉變換得到，在信號處理及相關應用上是特別重要的。
我們根據摺積理論知道
y
[
n
]
=
x
[
n
]
⋆
h
[
n
]
=
∑
k
x
[
n
−
k
]
h
[
k
]
{\displaystyle y[n]=x[n]\star h[n]=\sum _{k}{x[n-k]h[k]}}
y
[
n
]
=
I
F
F
T
(
F
F
T
x
[
n
]
F
F
T
h
[
n
]
)
{\displaystyle y[n]=IFFT(FFT{x[n]}FFT{h[n]})}
然而FFT 的點數該如何選取呢？
因為FFT 與IFFT 的點數皆要是一樣的，且特別要注意的一點是:
y
1
[
n
]
=
I
F
F
T
L
(
F
F
T
L
x
1
[
n
]
F
F
T
L
h
1
[
n
]
)
{\displaystyle y_{1}[n]=IFFT_{L}(FFT_{L}{x_{1}[n]}FFT_{L}{h_{1}[n]})}
y
1
[
n
]
=
∑
k
=
0
N
−
1
x
[
(
(
n
−
k
)
)
L
]
h
[
k
]
{\displaystyle y_{1}[n]=\sum _{k=0}^{N-1}{x[((n-k))_{L}]h[k]}}
其中FFTL 為L 點FFT ；IFFTL 為L 點IFFT
((a ))L : a 除以L 的餘數
上式表示根據摺積理論與快速傅立葉變換，我們求得的是兩個輸入信號的環形摺積而不是線性摺積
y
[
n
]
=
x
[
n
]
⋆
h
[
n
]
=
∑
k
x
[
n
−
k
]
h
[
k
]
{\displaystyle y[n]=x[n]\star h[n]=\sum _{k}{x[n-k]h[k]}}
依據兩個輸入信號的長度，計算方法可分類如下:
x [n ] 與 h [n ] 皆為無限長信號
编辑
由於此種類在實際應用上相當少且較不實際，故在此不進一步討論
x [n ] 與 h [n ] 皆為有限長信號
编辑
假設x [n ]的範圍[n 1 ,n 2 ]，長度為N = n 2 -n 1 +1；h [n ]的範圍為[k 1 ,k 2 ]，長度K 為 k 2 -k 1 +1
在這個情況下，x [n ]與h [n ]的線性摺積為
y
[
n
]
=
∑
k
=
k
1
k
2
x
[
n
−
k
]
h
[
k
]
{\displaystyle y[n]=\sum _{k=k_{1}}^{k_{2}}{x[n-k]h[k]}}
容易以圖解推得y [n ]有值的範圍為[k 1 +n 1 , k 2 +n 2 ]，輸出長度為
k
2
+
n
2
−
k
1
−
n
1
+
1
=
N
+
K
−
1
{\displaystyle k_{2}+n_{2}-k_{1}-n_{1}+1=N+K-1}
於是如欲以快速傅立葉變換計算線性摺積，則傅立葉變換之點數M 要取N +K -1，不足部份補零，實作方法如下：
x
1
[
n
]
=
x
[
n
+
n
1
]
,
n
=
0
,
1
,
2
,
.
.
.
,
N
−
1
{\displaystyle x_{1}[n]=x[n+n_{1}],n=0,1,2,...,N-1}
x
1
[
n
]
=
0
,
n
=
N
,
N
+
1
,
N
+
2
,
.
.
.
,
M
−
1
M
=
N
+
K
−
1
{\displaystyle x_{1}[n]=0,n=N,N+1,N+2,...,M-1M=N+K-1}
h
1
[
n
]
=
h
[
n
+
k
1
]
,
n
=
0
,
1
,
2
,
.
.
.
,
K
−
1
{\displaystyle h_{1}[n]=h[n+k_{1}],n=0,1,2,...,K-1}
h
1
[
n
]
=
0
,
n
=
K
,
K
+
1
,
K
+
2
,
.
.
.
,
M
−
1
{\displaystyle h_{1}[n]=0,n=K,K+1,K+2,...,M-1}
y
1
[
n
]
=
I
F
F
T
M
(
F
F
T
M
x
1
[
n
]
F
F
T
M
h
1
[
n
]
)
{\displaystyle y_{1}[n]=IFFT_{M}(FFT_{M}{x_{1}[n]}FFT_{M}{h_{1}[n]})}
y
[
n
]
=
y
1
[
n
−
n
1
−
k
1
]
,
n
−
n
1
−
k
1
=
0
,
1
,
2
,
.
.
.
,
N
−
1
{\displaystyle y[n]=y_{1}[n-n_{1}-k_{1}],n-n_{1}-k_{1}=0,1,2,...,N-1}
x [n ] 為無限長信號，而h [n ] 為有限長信號
编辑
由於摺積運算的對稱性，此種類與x [n ] 為有限長信號，而h [n ] 為無限長信號的情況完全相同。
假設x [n ]的範圍[n 1 ,n 2 ]，長度為N = n 2 - n 1 + 1，h [n ]長度為無限長。
在此情況下，摺積輸出y [n ]每一點皆有值。但當我們只想求出y [n ]的其中一段時，依然可利用快速傅立葉變換實作。
如果我們希望算出y [n ]在範圍[m 1 ,m 2 ]之間的值，此段長度為 M = m 2 -m 1 +1，此時可圖解發現，在h [n ]中與我們關心的輸出範圍有關聯之h [n ]範圍為[m 1 -n 2 ,m 2 -n 1 ]，需要使用的FFT 點數為L =N +M -1 (M 為輸出信號關心的長度)
實作方法如下:
x
1
[
n
]
=
x
[
n
+
n
1
]
,
n
=
0
,
1
,
2
,
.
.
.
,
N
−
1
{\displaystyle x_{1}[n]=x[n+n_{1}],n=0,1,2,...,N-1}
x
1
[
n
]
=
0
,
n
=
N
,
N
+
1
,
N
+
2
,
.
.
.
,
L
−
1
L
=
N
+
M
−
1
{\displaystyle x_{1}[n]=0,n=N,N+1,N+2,...,L-1L=N+M-1}
h
1
[
n
]
=
h
[
n
+
m
1
−
n
2
]
,
n
=
0
,
1
,
2
,
.
.
.
,
L
−
1
{\displaystyle h_{1}[n]=h[n+m_{1}-n_{2}],n=0,1,2,...,L-1}
y
1
[
n
]
=
I
F
F
T
L
(
F
F
T
L
x
1
[
n
]
F
F
T
L
h
1
[
n
]
)
{\displaystyle y_{1}[n]=IFFT_{L}(FFT_{L}{x_{1}[n]}FFT_{L}{h_{1}[n]})}
y
[
n
]
=
y
1
[
n
−
m
1
+
N
−
1
]
,
n
−
m
1
+
N
−
1
=
N
−
1
,
N
,
.
.
.
,
L
{\displaystyle y[n]=y_{1}[n-m_{1}+N-1],n-m_{1}+N-1=N-1,N,...,L}
y 1 [n]後面M 個點) 區塊摺積
编辑
當計算摺積之兩信號長度相差很大時，利用快速傅立葉變換計算摺積是較沒有效率的，此時較有效率的方法是將較長的信號切成一段段的區塊，以此每一區塊對另一輸入信號進行摺積再合併，常見的區塊摺積 方法包括重疊-相加之摺積法 與重疊-儲存之摺積法 ，針對長度的不同，區塊長度的選取亦會影響計算的效率。
相關條目
编辑
Rabiner, Lawrence R.; Gold, Bernard. Theory and application of digital signal processing . Englewood Cliffs, N.J.: Prentice-Hall. 1975: pp 63–67. ISBN 0-13-914101-4 Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John A. Discrete-time signal processing . Upper Saddle River, N.J.: Prentice Hall. 1999. ISBN 0-13-754920-2 Jian-Jiun Ding, Advanced digital signal processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007. 
![{\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{T}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{T}(t-\tau )\ d\tau \right]\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot x_{T}(t-\tau -kT)\ d\tau \right]\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot x_{T}(t-\tau )\ d\tau \right]\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\cdot x_{T}(t-\tau )\right]\ d\tau \\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\right]\cdot x_{T}(t-\tau )\ d\tau \\&\ {\stackrel {\mathrm {def} }{=}}\ \int _{t_{o}}^{t_{o}+T}h_{T}(\tau )\cdot x_{T}(t-\tau )\ d\tau \quad \quad {\mbox{QED}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0369196a811f10816f012a488f5cb927b16c92f)
![{\displaystyle x[n]\otimes h[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ab17c537f15b04998873d6bf3bc0ce82cc0ffb7)
![{\displaystyle {\begin{aligned}x_{N}[n]*h[n]\ &{\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }h[m]\cdot x_{N}[n-m]\\&=\sum _{m=-\infty }^{\infty }h[m]\cdot \sum _{k=-\infty }^{\infty }x[n-m-kN].\,\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f81ad7a1b5be12a3820caec493049571d9d3e28)
![{\displaystyle (f\star g)[m]=\sum _{n}{f[n]g[m-n]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cec2c952ea144dd3dcf40474667422f4cdf09800)
![{\displaystyle y[n]=x[n]\star h[n]=\sum _{k}{x[n-k]h[k]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0eeaa19f1c53ae8ffd422c17e25274e04b668bc)
![{\displaystyle y[n]=IFFT(FFT{x[n]}FFT{h[n]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8324227ec55d15287b90e2bab42c0efe8f1ee87)
![{\displaystyle y_{1}[n]=IFFT_{L}(FFT_{L}{x_{1}[n]}FFT_{L}{h_{1}[n]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c550dd80f0ffae90d7d62124b9ebda38337b4aa6)
![{\displaystyle y_{1}[n]=\sum _{k=0}^{N-1}{x[((n-k))_{L}]h[k]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbe047e486a0cd5e207fb02c97f9ed6538312485)
![{\displaystyle y[n]=\sum _{k=k_{1}}^{k_{2}}{x[n-k]h[k]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6507e2b4ebb11c45af32b13c686cf9d7380741c0)
![{\displaystyle x_{1}[n]=x[n+n_{1}],n=0,1,2,...,N-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c55f9ce29678d0832e8f096e1a8e44da22de1c5)
![{\displaystyle x_{1}[n]=0,n=N,N+1,N+2,...,M-1M=N+K-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a5e027bd729edd86b84e8eb0a5d72f865a9a52f)
![{\displaystyle h_{1}[n]=h[n+k_{1}],n=0,1,2,...,K-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e199a9084b7ca558a4cd34f9b20eb4722930443)
![{\displaystyle h_{1}[n]=0,n=K,K+1,K+2,...,M-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddf128b1010f9477bc505bfd335e6e9070c7d3c2)
![{\displaystyle y_{1}[n]=IFFT_{M}(FFT_{M}{x_{1}[n]}FFT_{M}{h_{1}[n]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eccb8b6160f5a952c385d347dabc3689f235924b)
![{\displaystyle y[n]=y_{1}[n-n_{1}-k_{1}],n-n_{1}-k_{1}=0,1,2,...,N-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b58fe34be61f2bb111f247f517b610baf7ad4ebc)
![{\displaystyle x_{1}[n]=0,n=N,N+1,N+2,...,L-1L=N+M-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7b8911ebe11ebc34b75066cc28aec61b8ecb914)
![{\displaystyle h_{1}[n]=h[n+m_{1}-n_{2}],n=0,1,2,...,L-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b268ef7dec7c427b4f9f30d42d367492ffb8c863)
![{\displaystyle y[n]=y_{1}[n-m_{1}+N-1],n-m_{1}+N-1=N-1,N,...,L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fafafdc49e09c8989cc471cf2b7a986a69ba4d5e)