沃爾什轉換（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。

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

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

與阿達馬變換的關係
沃爾什轉換與阿達馬變換關係密切，兩者都可由只含有 +1 與 -1 的正交矩陣表示。在許多文獻與軟體實作中，兩者也常以沃爾什－阿達馬變換（Walsh–Hadamard transform）合稱。不過，若從信號處理的角度來看，沃爾什轉換通常特別強調沃爾什函數或沃爾什矩陣的排列方式；阿達馬變換則較常強調阿達馬矩陣本身的正交矩陣結構與遞迴生成方式。因此，兩者雖然在矩陣元素與正交性上十分相近，但在命名與應用脈絡上仍有差異。

在自然順序或阿達馬順序中，矩陣列向量通常依照遞迴生成的結構排列；而在沃爾什順序或序數順序（sequency ordering）中，列向量會依照符號變化次數排列。符號變化次數越少的列，其波形越接近低震盪的方波；符號變化次數越多的列，則可視為較高震盪程度的方波基底。這種排列方式使沃爾什轉換在頻譜分析中具有較直觀的解釋，因為sequency可被視為類似頻率的概念。離散傅立葉轉換是將信號展開為正弦波與餘弦波的組合，而沃爾什轉換則是將信號展開為一組正交方波基底的組合；因此，對於具有階梯狀、開關式或二值變化特徵的信號，沃爾什轉換有時可提供較簡單的表示方式。

另一方面，沃爾什轉換與傅立葉轉換也有明顯差異。傅立葉轉換的基底與傳統線性非時變系統中的正弦穩態響應有直接關係，因此常用於頻率響應與濾波器分析；沃爾什轉換雖然也具有正交性、能量守恆與快速演算法，但其摺積性質通常對應邏輯摺積，而非一般線性系統中的線性摺積或循環摺積。因此，沃爾什轉換較適合用於正交展開、資料表示、多工或特定數位訊號處理問題，而不一定適合直接取代傅立葉轉換來分析一般線性非時變系統。

CDMA中的同步條件與限制
在CDMA系統中，沃爾什碼可作為正交展頻碼。多個通道或使用者可分別乘上不同的沃爾什碼，接收端再以指定通道的碼序列進行內積或相關運算，以分離對應資料。若所有通道的碼片邊界與符號時間在接收端對齊，則不同沃爾什碼之間的內積為零，理想情況下可降低同一基地台內不同通道之間的干擾。這種作法常被用來說明正交碼分多址中「以不同正交碼區分不同通道」的基本概念。

然而，沃爾什碼的正交性仍依賴同步條件。若不同使用者或不同通道的碼片邊界沒有對齊，接收端計算出的相關值可能不再為零，因而產生多址干擾。無線通道中的多路徑傳播也可能使同一訊號以不同延遲抵達接收端，進一步破壞理想正交性。因此，沃爾什碼特別適合可維持同步的下行鏈路或同步多通道系統；在非同步上行鏈路中，通常還需要搭配同步機制、功率控制、通道估測、RAKE接收器或其他展頻碼設計來降低干擾。

在實際系統分析中，沃爾什碼的優點不只在於矩陣元素只有 +1 與 -1，也在於其正交碼集合容易產生，且可用簡單的加減法完成展頻與解展頻運算。對於長度為 N 的沃爾什碼，理想情況下可提供 N 個互相正交的碼通道。發送端將資料位元轉換為 +1 或 -1 後乘上對應碼序列，接收端再與相同碼序列做內積，即可依內積正負判斷傳送資料。若接收端使用其他正交碼進行內積，理想同步條件下會因正交性而得到零或接近零的結果。這也是沃爾什轉換與沃爾什碼在多工、通道化與數位通訊教學中常被使用的原因之一。

沃爾什轉換與沃爾什轉換矩陣的性質
（1）正交性質

沃爾什轉換矩陣的每個列是互相正交的，即如果m_0\ne 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有一樣的以下性質

正交性質

零交（zero-crossing）性質

線性運算性質

調變性質

巴斯瓦定理（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\oplus7=4

\begin{array}{lcr} 3& 0 1 1\\\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

相關條目
*阿达马矩阵
*Hadamard變換
*Hadamard矩陣

參考文獻
*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.

沃爾什轉換