当计算4x4块
[
L
4
]
{\displaystyle {\begin{bmatrix}L_{4}\end{bmatrix}}}
的SATD时,先使用下面的方法进行二维的阿达马变换:
[
L
4
′
]
=
[
H
4
]
×
[
L
4
]
×
[
H
4
]
{\displaystyle {\begin{bmatrix}L_{4}'\end{bmatrix}}={\begin{bmatrix}H_{4}\end{bmatrix}}\times {\begin{bmatrix}L_{4}\end{bmatrix}}\times {\begin{bmatrix}H_{4}\end{bmatrix}}}
然后计算
[
L
4
′
]
{\displaystyle {\begin{bmatrix}L_{4}'\end{bmatrix}}}
所有系数绝对值 之和并归一化 。
类似的,当计算8x8块
[
L
8
]
{\displaystyle {\begin{bmatrix}L_{8}\end{bmatrix}}}
的SATD时,先使用下面的方法进行二维的Hadamard变换:
[
L
8
′
]
=
[
H
8
]
×
[
L
8
]
×
[
H
8
]
{\displaystyle {\begin{bmatrix}L_{8}'\end{bmatrix}}={\begin{bmatrix}H_{8}\end{bmatrix}}\times {\begin{bmatrix}L_{8}\end{bmatrix}}\times {\begin{bmatrix}H_{8}\end{bmatrix}}}
然后计算
[
L
8
′
]
{\displaystyle {\begin{bmatrix}L_{8}'\end{bmatrix}}}
所有系数绝对值 之和并归一化 。
阿达马变换轉換主要型式為
2
k
{\displaystyle {\boldsymbol {2^{k}}}}
點的轉換矩陣 ,其最小單位矩陣 為 2x2 的阿达马变换矩陣,以下分別為二點、四點與如何產生
2
k
{\displaystyle {\boldsymbol {2^{k}}}}
點的阿达马变换轉換步驟。
W
2
=
[
1
1
1
−
1
]
{\displaystyle {\boldsymbol {W_{2}}}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}}
W
4
=
[
1
1
1
1
1
1
−
1
−
1
1
−
1
−
1
1
1
−
1
1
−
1
]
{\displaystyle {\boldsymbol {W_{4}}}={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\end{bmatrix}}}
產生
2
k
{\displaystyle {\boldsymbol {2^{k}}}}
點阿达马变换的步驟:
步驟一:
V
2
k
+
1
=
[
W
2
k
W
2
k
W
2
k
−
W
2
k
]
{\displaystyle {\boldsymbol {V_{2^{k+1}}}}={\begin{bmatrix}{\boldsymbol {W_{2^{k}}}}&{\boldsymbol {W_{2^{k}}}}\\{\boldsymbol {W_{2^{k}}}}&{\boldsymbol {-W_{2^{k}}}}\end{bmatrix}}}
步驟二: 根據正負號次序 (Sign change,正負號改變次數) 將矩陣 (Matrix) 內的列向量做順序上的重新排列。
V
2
k
+
1
⟶
W
2
k
+
1
{\displaystyle {\boldsymbol {V_{2^{k+1}}}}\longrightarrow {\boldsymbol {W_{2^{k+1}}}}}
V
4
=
[
W
2
W
2
W
2
−
W
2
]
=
[
1
1
1
1
1
−
1
1
−
1
1
1
−
1
−
1
1
−
1
−
1
1
]
,
W
4
=
[
1
1
1
1
1
1
−
1
−
1
1
−
1
−
1
1
1
−
1
1
−
1
]
.
{\displaystyle {\boldsymbol {V_{4}}}={\begin{bmatrix}{\boldsymbol {W_{2}}}&{\boldsymbol {W_{2}}}\\{\boldsymbol {W_{2}}}&{\boldsymbol {-W_{2}}}\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}},\quad {\boldsymbol {W_{4}}}={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\end{bmatrix}}.}
V
8
=
[
1
1
1
1
1
1
1
1
1
1
−
1
−
1
1
1
−
1
−
1
1
−
1
−
1
1
1
−
1
−
1
1
1
−
1
1
−
1
1
−
1
1
−
1
1
1
1
1
−
1
−
1
−
1
−
1
1
1
−
1
−
1
−
1
−
1
1
1
1
−
1
−
1
1
−
1
1
1
−
1
1
−
1
1
−
1
−
1
1
−
1
1
]
,
W
8
=
[
1
1
1
1
1
1
1
1
1
1
1
1
−
1
−
1
−
1
−
1
1
1
−
1
−
1
−
1
−
1
1
1
1
1
−
1
−
1
1
1
−
1
−
1
1
−
1
−
1
1
1
−
1
−
1
1
1
−
1
−
1
1
−
1
1
1
−
1
1
−
1
1
−
1
−
1
1
−
1
1
1
−
1
1
−
1
1
−
1
1
−
1
]
.
{\displaystyle {\boldsymbol {V_{8}}}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\end{bmatrix}},\quad {\boldsymbol {W_{8}}}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{bmatrix}}.}
∑
n
=
0
N
−
1
W
[
h
,
n
]
W
[
m
,
n
]
=
0
,
i
f
h
≠
m
.
{\displaystyle \sum _{n=0}^{N-1}W\left[{h,n}\right]W\left[{m,n}\right]=0,\quad \mathrm {if} \,h\neq m.}
其表示 Walsh-Hadamard 轉換矩陣 中,不同的列向量 (Row verctor) 做內積 (Inner product) 為零。
可簡單從 Walsh-Hadamard 轉換矩陣 中發現,其奇數列向量 呈現左右兩邊偶對稱 (Even symmetric)。反之,其偶數列向量 呈現左右兩邊奇對稱 (Odd symmetric)。
若
f
[
n
]
⇒
F
[
m
]
a
n
d
g
[
n
]
⇒
G
[
m
]
,
{\displaystyle f\left[{n}\right]\Rightarrow F\left[{m}\right]\,and\,\,g\left[{n}\right]\Rightarrow G\left[{m}\right],}
則
a
f
[
n
]
+
b
g
[
n
]
⇒
a
F
[
m
]
+
b
G
[
m
]
.
{\displaystyle a\,f\left[{n}\right]+b\,g\left[{n}\right]\Rightarrow a\,F\left[{m}\right]+b\,G\left[{m}\right].}
W
[
m
,
n
]
⋅
W
[
l
,
n
]
=
W
[
m
⊕
l
,
n
]
.
{\displaystyle W\left[{m,n}\right]\cdot W\left[{l,n}\right]=W\left[{m\oplus l,n}\right].}
範例:
0
⊕
0
=
0
,
0
⊕
1
=
1
,
1
⊕
0
=
1
,
1
⊕
1
=
0
,
{\displaystyle 0\oplus 0=0,\quad 0\oplus 1=1,\quad 1\oplus 0=1,\quad 1\oplus 1=0,}
其運算方式為布林代數 內的 XOR 邏輯閘。
δ
[
n
]
⇒
1
,
1
⇒
N
⋅
δ
[
n
]
.
{\displaystyle \delta \left[{n}\right]\Rightarrow 1,\quad 1\Rightarrow N\cdot \delta \left[{n}\right].}
其中,
δ
[
n
]
=
{
1
,
w
h
e
n
n
=
0
0
,
w
h
e
n
n
≠
0
.
{\displaystyle \delta \left[{n}\right]={\begin{cases}\,1,\quad \mathrm {when} \;n=0\\\,0,\quad \mathrm {when} \;n\neq 0\end{cases}}.}
若
f
[
n
]
⇒
F
[
m
]
,
{\displaystyle f\left[{n}\right]\Rightarrow F\left[{m}\right],}
則
f
[
n
⊕
k
]
⇒
W
[
k
,
m
]
F
[
m
]
.
{\displaystyle f\left[{n\oplus k}\right]\Rightarrow W\left[{k,m}\right]F\left[{m}\right].}
若
f
[
n
]
⇒
F
[
m
]
,
{\displaystyle f\left[{n}\right]\Rightarrow F\left[{m}\right],}
則
W
[
k
,
n
]
f
[
n
]
⇒
F
[
m
⊕
k
]
.
{\displaystyle W\left[{k,n}\right]f\left[{n}\right]\Rightarrow F\left[{m\oplus k}\right].}
若
f
[
n
]
⇒
F
[
m
]
,
∑
n
=
0
N
−
1
|
f
[
n
]
|
2
=
(
1
N
)
∑
n
=
0
N
−
1
|
F
[
m
]
|
2
.
{\displaystyle f\left[{n}\right]\Rightarrow F\left[{m}\right],\quad \sum _{n=0}^{N-1}\left|f\left[n\right]\right|^{2}=\left({\frac {1}{N}}\right)\sum _{n=0}^{N-1}\left|F\left[m\right]\right|^{2}.}
若
f
[
n
]
⇒
F
[
m
]
a
n
d
g
[
n
]
⇒
G
[
m
]
,
{\displaystyle f\left[{n}\right]\Rightarrow F\left[{m}\right]\,and\,\,g\left[{n}\right]\Rightarrow G\left[{m}\right],}
則
∑
n
=
0
N
−
1
f
[
n
]
g
[
n
]
=
(
1
N
)
∑
n
=
0
N
−
1
F
[
m
]
G
[
m
]
.
{\displaystyle \sum _{n=0}^{N-1}f\left[n\right]g\left[n\right]=\left({\frac {1}{N}}\right)\sum _{n=0}^{N-1}F\left[m\right]G\left[m\right].}
摺積 性質 (Convolution Property)
若
f
[
n
]
⇒
F
[
m
]
a
n
d
g
[
n
]
⇒
G
[
m
]
,
{\displaystyle f\left[{n}\right]\Rightarrow F\left[{m}\right]\,and\,\,g\left[{n}\right]\Rightarrow G\left[{m}\right],}
則
h
[
n
]
=
f
[
n
]
⋆
g
[
n
]
⇒
H
[
m
]
=
F
[
m
]
G
[
m
]
,
{\displaystyle h\left[{n}\right]=f\left[{n}\right]\star g\left[{n}\right]\Rightarrow H\left[{m}\right]=F\left[{m}\right]G\left[{m}\right],}
其中
⋆
{\displaystyle \star }
代表邏輯摺積 (Logical convolution)。
優點
僅需實數 運算 (Real operation) 。
不需乘法 運算 (No multiplication) ,僅有加減法運算。
有部分性質類似於離散傅立葉變換 (Discrete fourier transform) 。
順向轉換 (Forward transform) 與反向轉換 (Inverse transform ) 型式為相似式。
{
F
[
m
]
=
∑
n
=
0
N
−
1
W
[
m
,
n
]
f
[
n
]
(
Forward Type
)
f
[
n
]
=
(
1
N
)
∑
n
=
0
N
−
1
W
[
m
,
n
]
F
[
m
]
(
Inverse Type
)
,
{\displaystyle {\begin{cases}{\begin{matrix}F\left[m\right]&=&\sum _{n=0}^{N-1}W\left[{m,n}\right]f\left[n\right]&&({\mbox{Forward Type}})\\f\left[n\right]&=&\left({\frac {1}{N}}\right)\sum _{n=0}^{N-1}W\left[{m,n}\right]F\left[m\right]&&({\mbox{Inverse Type}})\end{matrix}}\end{cases}},}
其中
F
[
n
]
{\displaystyle F\left[n\right]}
與
f
[
n
]
{\displaystyle f\left[n\right]}
分別都為行向量 (Column vector) 。
缺點
廣義來說,其實阿达马变换轉換是 Jacket 轉換中的一項特例情況,其將
w
=
±
2
0
=
1
{\displaystyle w=\pm 2^{0}=1}
即可求得。
以下為四點的 Jacket 轉換:
J
4
=
[
1
1
1
1
1
−
w
w
−
1
1
w
−
w
1
1
−
1
−
1
1
]
,
w
h
e
r
e
w
=
±
2
k
.
{\displaystyle {\boldsymbol {J_{4}}}={\begin{bmatrix}1&1&1&1\\1&-w&w&-1\\1&w&-w&1\\1&-1&-1&1\end{bmatrix}},\quad where\ w=\pm 2^{k}.}
2
k
+
1
{\displaystyle {\boldsymbol {2^{k+1}}}}
點的 Jacket 轉換:
J
2
k
+
1
=
[
J
2
k
J
2
k
J
2
k
−
J
2
k
]
.
{\displaystyle {\boldsymbol {J_{2^{k+1}}}}={\begin{bmatrix}{\boldsymbol {J_{2^{k}}}}&{\boldsymbol {J_{2^{k}}}}\\{\boldsymbol {J_{2^{k}}}}&-{\boldsymbol {J_{2^{k}}}}\end{bmatrix}}.}