沃尔什转换

沃尔什转换（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.