沃尔什转换

沃尔什转换（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$ 与 $-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$\oplus$7=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

H2=f0g2+f1g1 + f2g0 + f3g7 + f4g6 + f5g5 + f6g4+ f7g3

Logical convolution

h2 = f0g2 + f1g3 + f2g0 + f3g1 + f4g6 + f5g7 + f6g4+ f7g5

由上面可知，两者结果不一致

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