沃爾什轉換

沃爾什轉換（Walsh Transform）是在頻譜分析上作為離散傅立葉變換的替代方案的一種方法。

在頻譜分析上最常用的一種方法是使用離散傅立葉變換，然而，即使已經有許多快速的演算法來實現離散傅立葉變換，仍然具有一些實現上的缺點，舉例來說，在離散傅立葉變換中，資料向量必須乘上複數係數的矩陣加以處理，而且每個複數係數的實部和虛部是一個正弦及餘弦函數，因此大部分的係數都是浮點數，也就是說在做離散傅立葉變換處理的時候，我們必須做複數而且是浮點數的運算，因此計算量會比較大，而且浮點數運算產生的誤差會比較大。

而在沃爾什轉換中，資料向量需要乘上的矩陣是一個實數的矩陣，而且這些矩陣的係數是1或是–1，因此所有的係數都是絕對值大小相同的整數，這使得我們不需要作浮點數的乘法運算，更進一步，只需要使用加法來實現沃爾什轉換，這使的沃爾什轉換在運算複雜度上遠小於離散傅立葉變換。

使用離散傅立葉變換相當於把信號拆解成在不同頻率的正弦函數與餘弦函數的分量，而使用沃爾什轉換相當於把信號拆解成在許多不同震盪頻率的方波上，因此，除非所要分析的信號擁有類似方波組合的特性，使用沃爾什轉換作頻譜分析的效果會比使用離散傅立葉變換分析的效果要差，這是降低運算複雜度所要付出的代價。

轉換公式

沃爾什轉換的轉換式為

$F[m]=\sum _{n=0}^{N-1}f[n]W[m,n]$

其中 $W[m,n]$ 是沃爾什轉換矩陣的第（m,n）個元素。舉例來說，一個8點沃爾什轉換的轉換矩陣如下：

$W_{8}={\begin{pmatrix}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{pmatrix}}$

後面會解釋沃爾什轉換矩陣是如何產生，而沃爾什轉換的反轉換式為

$f[m]={\frac {1}{N}}\sum _{n=0}^{N-1}F[n]W[m,n]$

注意到正轉換式與反轉換式只差了一個常數，這是由於沃爾什轉換矩陣的反矩陣就是自己的轉置矩陣乘上一個常數的緣故。

沃爾什轉換矩陣的產生

$2^{k}$ 點的沃爾什矩陣可以用下面的遞迴方式產生：

起始值 $k=1$ （2點沃爾什轉換矩陣）

$W_{2}={\begin{pmatrix}1&1\\1&-1\\\end{pmatrix}}$

假設我們已經有一個 $2^{k}$ 點的沃爾什轉換矩陣 $W_{2^{k}}$ 則我們可以藉由下面的方法來產生 $2^{k+1}$ 點的沃爾什轉換矩陣 $W_{2^{k+1}}$

Step 1 定義 $V_{2^{k+1}}={\begin{pmatrix}W_{2^{k}}&W_{2^{k}}\\W_{2^{k}}&-W_{2^{k}}\\\end{pmatrix}}$

Step 2 根據變號次數把 $V_{2^{k+1}}$ 的列（row）重新排列成為 $W_{2^{k+1}}$

以下舉一個使用4點沃爾什轉換矩陣產生8點沃爾什轉換矩陣的例子：

$W_{4}={\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{pmatrix}}$

$V_{8}={\begin{pmatrix}W_{4}&W_{4}\\W_{4}&-W_{4}\\\end{pmatrix}}={\begin{pmatrix}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{pmatrix}}$

接著對 $V_{8}$ 的列做排序即可得上面的 $W_{8}$ 。

在不同的應用上，我們較常使用的沃爾什矩陣的列的排列順序也不同，以下以一個表來區分：

序數順序（沃爾什順序）	雙積順序（培力順序）	自然順序（哈德碼得順序）	$W[m,n]$
Sequency Ordering(Walsh Ordering)	Dyadic Ordering(Paley Ordering)	Natural Ordering（Hadamard Ordering）
較常用於信號處理	較常用於控制工程	較常用於數學
第0列	第0列	第0列	${\begin{pmatrix}1&1&1&1&1&1&1&1\\\end{pmatrix}}$
第1列	第1列	第4列	${\begin{pmatrix}1&1&1&1&-1&-1&-1&-1\\\end{pmatrix}}$
第2列	第3列	第6列	${\begin{pmatrix}1&1&-1&-1&-1&-1&1&1\\\end{pmatrix}}$
第3列	第2列	第2列	${\begin{pmatrix}1&1&-1&-1&1&1&-1&-1\\\end{pmatrix}}$
第4列	第6列	第3列	${\begin{pmatrix}1&-1&-1&1&1&-1&-1&1\\\end{pmatrix}}$
第5列	第7列	第7列	${\begin{pmatrix}1&-1&-1&1&-1&1&1&-1\\\end{pmatrix}}$
第6列	第5列	第5列	${\begin{pmatrix}1&-1&1&-1&-1&1&-1&1\\\end{pmatrix}}$
第7列	第4列	第1列	${\begin{pmatrix}1&-1&1&-1&1&-1&1&-1\\\end{pmatrix}}$

若使用二進位來表示各種順序的列的編號，則雙積順序的二進位編號是序數順序的格雷碼編碼，而自然順序的二進位編號是雙積順序的位元反轉。

沃爾什轉換與沃爾什轉換矩陣的性質

（1）正交性質

沃爾什轉換矩陣的每個列是互相正交的，即如果 $m_{0}\neq m_{1}$ 則 $\sum _{n=0}^{N-1}W[m_{0},n]W[m_{1},n]=0$

（2）零交（zero-crossing）性質

$2^{k}$ 點沃爾什轉換矩陣的每個列的變號次數都不相同，分別為變號0次到變號 $2^{k}-1$ ，這個性質是沃爾什轉換可以用來做頻譜分析的原因之一，不同的變號次數相當於不同的頻率。

（3）奇偶性質

沃爾什轉換矩陣（沃爾什順序）中，編號為偶數的列是偶對稱，編號為奇數的列是奇對稱。（有第0列）

（4）線性性質

若 $f[n]\Rightarrow F[m]$ ， $g[n]\Rightarrow G[m]$ ，（ $\Rightarrow$ 表沃爾什轉換）則有 $af[n]+bg[n]\Rightarrow aF[m]+bg[m]$ 。

（5）加法性質

$W[m,n]W[l,n]=W[m\oplus l,n]$ ， $\oplus$ 表示邏輯互斥或（exclusive or）

（6）平移性質

若 $f[n]\Rightarrow F[m]$ 則 $f[n\oplus k]\Rightarrow W[k,m]F[m]$

（7）調變性質

若 $f[n]\Rightarrow F[m]$ 則 $W[k,n]f[n]\Rightarrow F[k\oplus m]$

（8）巴斯瓦定理（Parseval's Theorem）

若 $f[n]\Rightarrow F[m]$ 則 $\sum _{n=0}^{N-1}|f[n]|^{2}={\frac {1}{N}}\sum _{n=0}^{N-1}|F[m]|^{2}$

（9）摺積性質

若 $f[n]\Rightarrow F[m]$ ， $g[n]\Rightarrow G[m]$ ，則 $\sum _{l=0}^{N-1}f[l]g[((n\oplus l))_{N}]=\sum _{l=0}^{N-1}g[l]f[((n\oplus l))_{N}]\Rightarrow F[m]G[m]$ ，在這裡 $\sum _{l=0}^{N-1}f[l]g[((n\oplus l))_{N}]=\sum _{l=0}^{N-1}g[l]f[((n\oplus l))_{N}]$ 代表邏輯摺積（logical convolution）。

快速沃爾什轉換

由於一個 $2^{k}$ 點沃爾什轉換矩陣可以由 $2^{k-1}$ 點的沃爾什轉換矩陣堆疊後做變號與排序產生，因此一個 $2^{k}$ 沃爾什轉換可以由做兩次 $2^{k-1}$ 的沃爾什轉換及一些加減法和排序產生，可以得到一個類似快速傅立葉變換的蝴蝶結構。

沃爾什轉換的優點

運算數值皆為實數不存在複數
不需要應用到乘法運算
頻譜分析( spectrum analysis)
正向轉換跟反向轉換結構相似
- Forward : $F[m]=\textstyle \sum _{n=0}^{N-1}\displaystyle f[n]W[m,n]$
- Inverse : $f[m]=1/N\textstyle \sum _{n=0}^{N-1}\displaystyle F[n]W[m,n]$
跟DFT有一樣的以下性質
1. 正交性質
2. 零交（zero-crossing）性質
3. 線性運算性質
4. 調變性質
5. 巴斯瓦定理（Parseval's Theorem)

應用

沃爾什轉換適合做頻譜分析，但未必適合做摺積

因此不適合分析線性非時變系統(LTI system)

證明:

Linear convolution (standard form of convolution)

$\textstyle \sum _{n=0}^{N-1}\displaystyle f[n]g[n-l]$

Circular convolution

$\textstyle \sum _{n=0}^{N-1}\displaystyle f[n]g[(n-l)_{N}]$

但是在Walsh Transform中Convolution Property 代表著"logic convolution"

Logic convolution

$h[n]=f[n]*g[n]=\textstyle \sum _{n=0}^{N-1}\displaystyle f[n]g[(n\oplus l]=\textstyle \sum _{n=0}^{N-1}\displaystyle f[n\oplus l]g[l]$

* 代表 "Logic convolution"

$\oplus$ 代表 "logic addition" (similar to XOR) ,for example 3 $\oplus$ 7=4

${\begin{array}{lcr}3&011\\\oplus 7&111\end{array}}$

XOR(1,0)=XOR(0,1)=1

XOR(0,0)=XOR(1,1)=0

以訊號處理的角度,Circular convolution 可以滿足 Linear convolution ,即可分析LTI系統

假使Logic convolution 與 Circular convolution 結果不一致則無法分析 LTI系統

舉例來說:

當N=8
Circular convolution

H[2]=f[0]g[2]+f[1]g[1] + f[2]g[0] + f[3]g[7] + f[4]g[6] + f[5]g[5] + f[6]g[4]+ f[7]g[3]

Logical convolution

h[2] = f[0]g[2] + f[1]g[3] + f[2]g[0] + f[3]g[1] + f[4]g[6] + f[5]g[7] + f[6]g[4]+ f[7]g[5]

由上面可知，兩者結果不一致

CDMA 領域

主要應用在多工，其中CDMA為主要應用
若使用N點沃爾什轉換，則可以對N個通道做多工
而且使用沃爾什轉換的好處是不需要同步
其他正交轉換則需要同步

舉例：CDMA使用沃爾什轉換做多工的方法
假設現在有兩組資料要傳，分別是[1,0,1],[1,1,0]
並且使用8點沃爾什轉換 $W_{8}$ 的第一行與第二行來當作通道一與通道二的正交基底
1.將0變為-1
[1,0,1]→[1,-1,1]
[1,1,0]→[1,1,-1]
2.調變
對於第一組資料拿通道一來調變
第一組資料為[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,-1,-1,-1,-1, -1,-1,-1,-1,1,1,1,1]
3.相加
[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]
→[2,2,2,2,0,0,0,0,0,0,0,0,-2,-2,-2,-2,0,0,0,0,2,2,2,2]

解調
1.如果使用N點沃爾什轉換，則把接收的訊號每隔N點拆開來
[2,2,2,2,0,0,0,0,0,0,0,0,-2,-2,-2,-2,0,0,0,0,2,2,2,2]
→[2,2,2,2,0,0,0,0], [0,0,0,0,-2,-2,-2,-2], [0,0,0,0,2,2,2,2]
2.將每段訊號與通道做內積
若大於0,則解調為1
若小於0,則解調為0
對於通道一
[2,2,2,2,0,0,0,0]·[1,1,1,1,1,1,1,1]=8 → 1
[0,0,0,0,-2,-2,-2,-2]·[1,1,1,1,1,1,1,1]=-8 → 0
[0,0,0,0,2,2,2,2]·[1,1,1,1,1,1,1,1]=8 → 1
通道一接收的資料為[1,0,1]
對於通道二
[2,2,2,2,0,0,0,0]·[1,1,1,1,-1,-1,-1,-1]=8 → 1
[0,0,0,0,-2,-2,-2,-2]·[1,1,1,1,-1,-1,-1,-1]=8 → 1
[0,0,0,0,2,2,2,2]·[1,1,1,1,-1,-1,-1,-1]=-8 → 0
通道二接收的資料為[1,1,0]

其他應用

Bandwidth reduction
High resolution
Information coding
Feature extraction
ECG(心電圖) signal (in medical signal processing) analysis
Hadamard spectrometer
Avoiding quantization error

參考文獻

Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
H. F. Harmuth,“Transmission of information by orthogonal functions,”1970.
Moon-Hu. Lee,“A new reverse Jacket transform and its fast algorithm,”IEEE Trans. Circuits Syst.-II, vol. 47, pp.39-46, 2000.
K.G.Beauchamp, "Walsh Functions and Their Applications," Academic Press,1975.
H. F. Harmuth, "Transmission of Information by Orthogonal Functions," Springer, 1969.