在数值分析 和泛函分析 领域中，离散小波变换 （Discrete Wavelet Transform，DWT）是小波被离散采样的小波变换 。与其他小波变换一样，它与傅里叶变换相比的一个关键优势是时间分辨率：它既能捕获频率信息，又能捕获位置（时间上的位置）信息。
第一個離散小波變換由匈牙利 數學家哈尔 發明，離散小波轉換顧名思義就是離散的輸入以及離散的輸出，但是這裡並沒有一個簡單而明確的公式來表示輸入及輸出的關係，只能以階層式架構來表示。
首先我們定義一些需要用到的信號及濾波器。
x[n]：離散的輸入信號，長度為N。
g
[
n
]
{\displaystyle g[n]}
h
[
n
]
{\displaystyle h[n]}
↓
{\displaystyle \downarrow }
舉例說明: 清楚規定以上符號之後，便可以利用階層架構來介紹如何將一個離散信號作離散小波轉換：
架構中的第1層(1st stage)
x
1
,
L
[
n
]
=
∑
k
=
0
K
−
1
x
[
2
n
−
k
]
g
[
k
]
{\displaystyle x_{1,L}[n]=\sum _{k=0}^{K-1}x[2n-k]g[k]}
x
1
,
H
[
n
]
=
∑
k
=
0
K
−
1
x
[
2
n
−
k
]
h
[
k
]
{\displaystyle x_{1,H}[n]=\sum _{k=0}^{K-1}x[2n-k]h[k]}
架構中的第2層(2nd stage)
x
2
,
L
[
n
]
=
∑
k
=
0
K
−
1
x
1
,
L
[
2
n
−
k
]
g
[
k
]
{\displaystyle x_{2,L}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]g[k]}
x
2
,
H
[
n
]
=
∑
k
=
0
K
−
1
x
1
,
L
[
2
n
−
k
]
h
[
k
]
{\displaystyle x_{2,H}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]h[k]}
可繼續延伸
⋮
{\displaystyle \vdots }
⋮
{\displaystyle \vdots }
架構中的第
α
{\displaystyle \alpha }
α
−
t
h
{\displaystyle \alpha -th}
x
α
,
L
[
n
]
=
∑
k
=
0
K
−
1
x
α
−
1
,
L
[
2
n
−
k
]
g
[
k
]
{\displaystyle x_{\alpha ,L}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]g[k]}
x
α
,
H
[
n
]
=
∑
k
=
0
K
−
1
x
α
−
1
,
L
[
2
n
−
k
]
h
[
k
]
{\displaystyle x_{\alpha ,H}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]h[k]}
注意：若輸入信號
x
[
n
]
{\displaystyle x[n]}
α
{\displaystyle \alpha }
x
α
,
L
[
n
]
{\displaystyle x_{\alpha ,L}[n]}
x
α
,
H
[
n
]
{\displaystyle x_{\alpha ,H}[n]}
N
2
α
{\displaystyle {\frac {N}{2^{\alpha }}}}
此時的輸入信號變成
x
[
m
,
n
]
{\displaystyle x[m,n]}
首先對n方向作高通、低通以及降頻的處理
v
1
,
L
[
m
,
n
]
=
∑
k
=
0
K
−
1
x
[
m
,
2
n
−
k
]
g
[
k
]
{\displaystyle v_{1,L}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]g[k]}
v
1
,
H
[
m
,
n
]
=
∑
k
=
0
K
−
1
x
[
m
,
2
n
−
k
]
h
[
k
]
{\displaystyle v_{1,H}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]h[k]}
接著對
v
1
,
L
[
m
,
n
]
{\displaystyle v_{1,L}[m,n]}
v
1
,
H
[
m
,
n
]
{\displaystyle v_{1,H}[m,n]}
x
1
,
L
L
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
L
[
2
m
−
k
,
n
]
g
[
k
]
{\displaystyle x_{1,LL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]g[k]}
x
1
,
H
L
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
L
[
2
m
−
k
,
n
]
h
[
k
]
{\displaystyle x_{1,HL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]h[k]}
x
1
,
L
H
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
H
[
2
m
−
k
,
n
]
g
[
k
]
{\displaystyle x_{1,LH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]g[k]}
x
1
,
H
H
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
H
[
2
m
−
k
,
n
]
h
[
k
]
{\displaystyle x_{1,HH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]h[k]}
經過(1)(2)兩個步驟才算完成2-D DWT的一個stage。
在討論複雜度之前，先做一些定義，當x[n]*y[n]時，x[n]之長度為N，y[n]之長度為L：
⇒
I
D
F
T
N
+
L
−
1
[
D
F
T
N
+
L
−
1
(
x
[
n
]
)
D
F
T
N
+
L
−
1
(
y
[
n
]
)
]
{\displaystyle \ \Rightarrow IDFT_{N+L-1}\left[DFT_{N+L-1}(x[n])DFT_{N+L-1}(y[n])\right]}
其中，
I
D
F
T
N
+
L
−
1
{\displaystyle \ IDFT_{N+L-1}}
D
F
T
N
+
L
−
1
{\displaystyle \ DFT_{N+L-1}}
(1)一維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution))：
3
2
(
N
+
L
−
1
)
log
2
(
N
+
L
−
1
)
≈
3
2
N
log
2
N
{\displaystyle {\frac {3}{2}}(N+L-1)\log _{2}{(N+L-1)}\approx {\frac {3}{2}}N\log _{2}N}
(2)當 N >>> L 時，使用 “分段卷积(sectioned convolution)”的技巧：
將x[n]切成很多段，每段長度為
N
1
{\displaystyle \mathbb {N} _{1}}
S
=
N
N
1
{\displaystyle S={\frac {N}{N_{1}}}}
N
>
N
1
>>
L
{\displaystyle N>N_{1}>>L}
則
x
[
n
]
∗
g
[
n
]
=
x
1
[
n
]
∗
g
[
n
]
+
x
2
[
n
]
∗
g
[
n
]
+
.
.
.
+
x
s
[
n
]
∗
g
[
n
]
{\displaystyle \ x[n]*g[n]=x_{1}[n]*g[n]+x_{2}[n]*g[n]+...+x_{s}[n]*g[n]}
x
[
n
]
∗
h
[
n
]
=
x
1
[
n
]
∗
h
[
n
]
+
x
2
[
n
]
∗
h
[
n
]
+
.
.
.
+
x
s
[
n
]
∗
h
[
n
]
{\displaystyle \ x[n]*h[n]=x_{1}[n]*h[n]+x_{2}[n]*h[n]+...+x_{s}[n]*h[n]}
複雜度為：
3
2
S
(
N
1
+
L
−
1
)
log
2
(
N
1
+
L
−
1
)
≈
3
2
S
N
1
log
2
(
N
1
+
L
−
1
)
≈
3
2
N
log
2
(
N
1
+
L
−
1
)
≈
3
2
N
log
2
N
1
{\displaystyle {\begin{aligned}{\frac {3}{2}}S(N_{1}+L-1)\log _{2}{(N_{1}+L-1)}&\approx {\frac {3}{2}}SN_{1}\log _{2}(N_{1}+L-1)\\&\approx {\frac {3}{2}}N\log _{2}(N_{1}+L-1)\\&\approx {\frac {3}{2}}N\log _{2}N_{1}\\\end{aligned}}}
在這裡要注意的是，當N>>L時，一維離散小波轉換之複雜度是呈線性的(隨N)，
O
(
N
)
{\displaystyle {\mathit {O(N)}}}
(3)多層(Multiple stages )的情況下：
1.若
x
a
,
H
[
n
]
{\displaystyle \ x_{a,H}[n]}
C
o
m
p
l
e
x
i
t
y
≈
(
N
+
N
2
+
N
4
+
N
8
+
.
.
.
+
2
)
3
2
log
2
N
1
=
(
2
N
−
2
)
3
2
log
2
N
1
≈
3
N
log
2
N
1
{\displaystyle {\begin{aligned}Complexity&\approx \left(N+{\frac {N}{2}}+{\frac {N}{4}}+{\frac {N}{8}}+...+2\right){\frac {3}{2}}\log _{2}N_{1}\\&=(2N-2){\frac {3}{2}}\log _{2}N_{1}\\&\approx 3N\log _{2}N_{1}\\\end{aligned}}}
2.若
x
a
,
H
[
n
]
{\displaystyle \ x_{a,H}[n]}
C
o
m
p
l
e
x
i
t
y
≈
(
N
+
2
N
2
+
4
N
4
+
8
N
8
+
.
.
.
+
N
2
2
)
3
2
log
2
N
1
=
(
N
log
2
N
)
3
2
log
2
N
1
{\displaystyle {\begin{aligned}Complexity&\approx \left(N+2{\frac {N}{2}}+4{\frac {N}{4}}+8{\frac {N}{8}}+...+{\frac {N}{2}}2\right){\frac {3}{2}}\log _{2}N_{1}\\&=(N\log _{2}N){\frac {3}{2}}\log _{2}N_{1}\\\end{aligned}}}
(4)二維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution))：
⇒
M
3
2
(
N
+
L
−
1
)
log
2
(
N
+
L
−
1
)
+
(
N
+
L
−
1
)
3
2
(
M
+
L
−
1
)
log
2
(
M
+
L
−
1
)
{\displaystyle \ \Rightarrow M{\frac {3}{2}}(N+L-1)\log _{2}{(N+L-1)}+(N+L-1){\frac {3}{2}}(M+L-1)\log _{2}{(M+L-1)}}
上式中，第一部分需要M個一維離散小波轉換並且每個一維離散小波轉換的輸入有N個點；第二部分需要N+L-1個一維離散小波轉換並且每個一維離散小波轉換的輸入有M個點。
C
o
m
p
l
e
x
i
t
y
≈
3
2
M
N
log
2
N
+
3
2
M
N
log
2
M
=
3
2
M
N
(
log
2
N
+
log
2
M
)
=
3
2
M
N
log
2
M
N
{\displaystyle {\begin{aligned}Complexity&\approx {\frac {3}{2}}MN\log _{2}N+{\frac {3}{2}}MN\log _{2}M\\&={\frac {3}{2}}MN(\log _{2}N+\log _{2}M)\\&={\frac {3}{2}}MN\log _{2}MN\\\end{aligned}}}
(5)二維離散小波轉換之複雜度，使用 “分段卷积(sectioned convolution)”的技巧：
假設原始尺寸為
M
×
N
{\displaystyle M\times N}
M
1
×
N
1
{\displaystyle M_{1}\times N_{1}}
C
o
m
p
l
e
x
i
t
y
≈
M
N
M
1
N
1
3
2
M
1
N
1
log
2
M
1
N
1
=
3
2
M
N
log
2
M
1
N
1
{\displaystyle {\begin{aligned}Complexity&\approx {\frac {MN}{M_{1}N_{1}}}{\frac {3}{2}}M_{1}N_{1}\log _{2}M_{1}N_{1}\\&={\frac {3}{2}}MN\log _{2}M_{1}N_{1}\\\end{aligned}}}
所以若是使用分段摺積，則二維離散小波轉換之複雜度是呈線性的(隨MN)，
O
(
M
N
)
{\displaystyle {\mathit {O(MN)}}}
(6)多層(Multiple stages )與二維的情況下：
首先x[m,n]的尺寸為
M
×
N
{\displaystyle M\times N}
1.若
x
a
,
H
1
[
n
]
,
x
a
,
H
2
[
n
]
,
x
a
,
H
3
[
n
]
{\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}
x
a
,
L
[
n
]
{\displaystyle \ x_{a,L}[n]}
t
o
t
a
l
c
o
m
p
l
e
x
i
t
y
=
(
M
N
+
M
N
4
+
M
N
16
+
.
.
.
)
3
2
log
2
M
1
N
1
≈
4
3
M
N
3
2
log
2
M
1
N
1
=
2
M
N
log
2
M
1
N
1
{\displaystyle {\begin{aligned}totalcomplexity&=\left(MN+{\frac {MN}{4}}+{\frac {MN}{16}}+...\right){\frac {3}{2}}\log _{2}M_{1}N_{1}\\&\approx {\frac {4}{3}}MN{\frac {3}{2}}\log _{2}M_{1}N_{1}\\&=2MN\log _{2}M_{1}N_{1}\\\end{aligned}}}
2.若
x
a
,
H
1
[
n
]
,
x
a
,
H
2
[
n
]
,
x
a
,
H
3
[
n
]
{\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}
t
o
t
a
l
c
o
m
p
l
e
x
i
t
y
=
(
M
N
+
4
M
2
N
2
+
16
M
4
N
4
+
.
.
.
)
3
2
log
2
M
1
N
1
=
[
M
N
log
2
(
m
i
n
(
M
,
N
)
)
]
3
2
log
2
M
1
N
1
{\displaystyle {\begin{aligned}totalcomplexity&=\left(MN+4{\frac {M}{2}}{\frac {N}{2}}+16{\frac {M}{4}}{\frac {N}{4}}+...\right){\frac {3}{2}}\log _{2}M_{1}N_{1}\\&=\left[MN\log _{2}(min(M,N))\right]{\frac {3}{2}}\log _{2}M_{1}N_{1}\\\end{aligned}}}
1.DWT通濾波器
g
(
n
)
{\displaystyle g(n)}
h
(
n
)
{\displaystyle h(n)}
2.滿足
h
(
n
)
{\displaystyle h(n)}
g
(
n
)
{\displaystyle g(n)}
3.滿足完整重建要條件，
(
G
1
(
z
)
H
1
(
z
)
)
=
2
d
e
t
(
H
m
(
z
)
)
(
H
(
−
z
)
−
G
(
−
z
)
)
{\displaystyle {\binom {G_{1}(z)}{H_{1}(z)}}={\frac {2}{det(H_{m}(z))}}{\binom {H(-z)}{-G(-z)}}}
d
e
t
(
H
m
(
z
)
)
=
G
(
z
)
H
(
−
z
)
−
H
(
z
)
G
(
−
z
)
{\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)}
4.若
g
(
n
)
{\displaystyle g(n)}
h
(
n
)
{\displaystyle h(n)}
d
e
t
(
H
m
(
z
)
)
=
G
(
z
)
H
(
−
z
)
−
H
(
z
)
G
(
−
z
)
=
α
z
k
{\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=\alpha z^{k}}
k
{\displaystyle k}
*為什麼k是奇數？
假設k为偶数，
z=-1
d
e
t
(
H
m
(
−
1
)
)
=
G
(
−
1
)
H
(
1
)
−
H
(
−
1
)
G
(
1
)
=
α
(
−
1
)
k
=
1
{\displaystyle det(H_{m}(-1))=G(-1)H(1)-H(-1)G(1)=\alpha (-1)^{k}=1}
z=1
d
e
t
(
H
m
(
1
)
)
=
G
(
1
)
H
(
−
1
)
−
H
(
1
)
G
(
−
1
)
=
α
(
1
)
k
=
1
{\displaystyle det(H_{m}(1))=G(1)H(-1)-H(1)G(-1)=\alpha (1)^{k}=1}
G
(
1
)
H
(
−
1
)
−
H
(
1
)
G
(
−
1
)
=
G
(
−
1
)
H
(
1
)
−
H
(
−
1
)
G
(
1
)
{\displaystyle G(1)H(-1)-H(1)G(-1)=G(-1)H(1)-H(-1)G(1)}
H
(
1
)
G
(
−
1
)
=
G
(
1
)
H
(
−
1
)
{\displaystyle H(1)G(-1)=G(1)H(-1)}
代回
d
e
t
(
H
m
(
−
1
)
)
=
G
(
−
1
)
H
(
1
)
−
H
(
−
1
)
G
(
1
)
=
0
{\displaystyle det(H_{m}(-1))=G(-1)H(1)-H(-1)G(1)=0}
顯然出現矛盾。
所以k必須為奇数。
1.Quadrature Mirror Filter(QMF)
H
(
z
)
=
G
(
−
z
)
{\displaystyle H(z)=G(-z)}
⟹
{\displaystyle \Longrightarrow }
h
(
n
)
=
(
−
1
)
n
g
(
n
)
{\displaystyle h(n)=(-1)^{n}g(n)}
G
1
(
z
)
=
G
(
z
)
z
−
k
{\displaystyle G_{1}(z)=G(z)z^{-k}}
⟹
{\displaystyle \Longrightarrow }
g
1
(
n
)
=
g
(
n
−
k
)
{\displaystyle g_{1}(n)=g(n-k)}
H
1
(
z
)
=
−
G
(
−
z
)
z
−
k
{\displaystyle H_{1}(z)=-G(-z)z^{-k}}
⟹
{\displaystyle \Longrightarrow }
h
1
(
n
)
=
(
−
1
)
n
−
k
+
1
g
(
n
−
k
)
{\displaystyle h_{1}(n)=(-1)^{n-k+1}g(n-k)}
d
e
t
(
H
m
(
z
)
)
=
G
(
z
)
H
(
−
z
)
−
H
(
z
)
G
(
−
z
)
=
2
z
k
{\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=2z^{k}}
k
{\displaystyle k}
2.Orthonormal Wavelet
G
(
z
)
=
G
1
(
z
−
1
)
{\displaystyle G(z)=G_{1}(z^{-1})}
⟹
{\displaystyle \Longrightarrow }
g
(
n
)
=
g
1
(
−
n
)
{\displaystyle g(n)=g_{1}(-n)}
H
(
z
)
=
−
z
k
G
1
(
−
z
)
{\displaystyle H(z)=-z^{k}G_{1}(-z)}
⟹
{\displaystyle \Longrightarrow }
h
(
n
)
=
(
−
1
)
n
g
1
(
n
+
k
)
{\displaystyle h(n)=(-1)^{n}g_{1}(n+k)}
H
1
(
z
)
=
−
z
k
G
1
(
−
z
−
1
)
{\displaystyle H_{1}(z)=-z^{k}G_{1}(-z^{-1})}
⟹
{\displaystyle \Longrightarrow }
h
1
(
n
)
=
(
−
1
)
n
g
1
(
−
n
+
k
)
{\displaystyle h_{1}(n)=(-1)^{n}g_{1}(-n+k)}
d
e
t
(
H
m
(
z
)
)
=
G
(
z
)
H
(
−
z
)
−
H
(
z
)
G
(
−
z
)
=
2
z
k
{\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=2z^{k}}
k
{\displaystyle k}
多數的wavelet屬於orthonormal wavelet。
壓縮、去除雜訊：使用低通濾波器，將小波轉換的高頻濾掉，即保留
x
1
,
L
L
[
m
,
n
]
{\displaystyle x_{1,LL}[m,n]}
邊緣偵測：使用高通濾波器，將小波的低頻濾掉，即保留
x
1
,
H
L
[
m
,
n
]
{\displaystyle x_{1,HL}[m,n]}
x
1
,
L
H
[
m
,
n
]
{\displaystyle x_{1,LH}[m,n]}
R语言小波分析wavelet （页面存档备份 ，存于互联网档案馆 ）作為 JPEG2000 的內部架構
模式辨認：由於可以利用低頻的部分得到原圖的縮略版，加上模式通常為整體的特性，藉由在縮略圖上進行工作，小波轉換可以有效減少尋找模式與比對模式的運算時間
濾波器設計：小波轉換保留部分時間資訊，可以據此資訊加上訊號的強度資訊，保留特定時點的資訊而同時去除雜訊
![{\displaystyle g[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c5e1d771a2385e9aeb71838a40425bb07c89525)
![{\displaystyle h[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89981bbbb05ffd469eeadb828c18359965985e46)
![{\displaystyle x_{1,L}[n]=\sum _{k=0}^{K-1}x[2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e89171201a089a787ca8eecf3cfcc0a997ca2687)
![{\displaystyle x_{1,H}[n]=\sum _{k=0}^{K-1}x[2n-k]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f25f3aaaa0a147dc3d27be4ffa8ec69966f512b)
![{\displaystyle x_{2,L}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/778ad7dd66c5fb41a730549fa7a229eb16187cbf)
![{\displaystyle x_{2,H}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a655d7ed52b22f9cdddc4212e23b84da4fd260f1)
![{\displaystyle x_{\alpha ,L}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b3237f86646ab171917e1d6fbab78eb53ad7496)
![{\displaystyle x_{\alpha ,H}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36145d18b7c0b1f46f34d3321d019964fb06b9c6)
![{\displaystyle x[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/864cbbefbdcb55af4d9390911de1bf70167c4a3d)
![{\displaystyle x_{\alpha ,L}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bee354c65204f381107da41675caf54fdd0f8af0)
![{\displaystyle x_{\alpha ,H}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a985602660a89b0b360223e0d07cd3e8c522b0c8)
![{\displaystyle x[m,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9745486e9c980ded7be564ca034810c0502193a5)
![{\displaystyle v_{1,L}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bb581d19be3dc84b6f66476669af51bb565f115)
![{\displaystyle v_{1,H}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adf51b66814e213300e947da548d3bdc2d77c4ea)
![{\displaystyle v_{1,L}[m,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2c2f9e57456cfe1f1bb72f65e453ddcd3e328b6)
![{\displaystyle v_{1,H}[m,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6aaed46292fa3e843bdcc62f065f819508c5965)
![{\displaystyle x_{1,LL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5699b1611ae488b196dfeb4b12a5ffbe17a7b756)
![{\displaystyle x_{1,HL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1bc0b122f88e2ec5cd699913f5291c491ac9a9f)
![{\displaystyle x_{1,LH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6657c6da1e42df215ace930f89aae0da4fa6b5f6)
![{\displaystyle x_{1,HH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f960b7f056492a876a7b6cc969b6cefa847de992)
![{\displaystyle \ \Rightarrow IDFT_{N+L-1}\left[DFT_{N+L-1}(x[n])DFT_{N+L-1}(y[n])\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cae7432bf7923ce1cc5af75a0704bf6f899b83d8)
![{\displaystyle \ x[n]*g[n]=x_{1}[n]*g[n]+x_{2}[n]*g[n]+...+x_{s}[n]*g[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/386358bc19aaec9a2e9d9ce37fd38aa709fc9a2b)
![{\displaystyle \ x[n]*h[n]=x_{1}[n]*h[n]+x_{2}[n]*h[n]+...+x_{s}[n]*h[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18d1b64eae8d11bb27fd38ae196e928c6af7c1bc)
![{\displaystyle \ x_{a,H}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0225fcdc0e72f90971baf21dbd5818de5e9789f)
![{\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0249304ddc40b1198b08d4b65deb69fc6119787e)
![{\displaystyle \ x_{a,L}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11c7a580e0467ccd1a109d8d7862ff79c29cd707)
![{\displaystyle {\begin{aligned}totalcomplexity&=\left(MN+4{\frac {M}{2}}{\frac {N}{2}}+16{\frac {M}{4}}{\frac {N}{4}}+...\right){\frac {3}{2}}\log _{2}M_{1}N_{1}\\&=\left[MN\log _{2}(min(M,N))\right]{\frac {3}{2}}\log _{2}M_{1}N_{1}\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b65707e601992cb38fc9457a407d6032250f84c)
![{\displaystyle X_{1,L}(z)={\frac {1}{2}}[X(z^{\frac {1}{2}})G(z^{\frac {1}{2}})+X(-z^{\frac {1}{2}})G(-z^{\frac {1}{2}})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1a5ca6b242399e9142d1785f12bed631cf884fa)
![{\displaystyle X_{1,H}(z)={\frac {1}{2}}[X(z^{\frac {1}{2}})H(z^{\frac {1}{2}})+X(-z^{\frac {1}{2}})H(-z^{\frac {1}{2}})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23fed8fd5871ec0be7b67dab6e1aa1f4e99825e5)
![{\displaystyle X_{0}(z)={\tfrac {1}{2}}[X(z)G(z)+X(-z)G(-z)]G_{1}(z)+{\tfrac {1}{2}}[X(z)H(z)+X(-z)H(-z)]H_{1}(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a41efe9f8250241456370898ec832227ac1daa37)
![{\displaystyle ={\tfrac {1}{2}}[G(z)G_{1}(z)+H(z)H_{1}(z)]X(z)+{\tfrac {1}{2}}[G(-z)G_{1}(z)+H(-z)H_{1}(z)]X(-z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53e7e0658a6da7ce7db107825eec36ddcd52b0b3)
![{\displaystyle x_{1,LL}[m,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d8608023ad34350b051b07146e3fcab335cc9cd)
![{\displaystyle x_{1,HL}[m,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9430d219a31ca6aec8230eb6d60ad8b972e2bf0)
![{\displaystyle x_{1,LH}[m,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a3c4a90c743b8f13b8c816d232197ab3884689b)