沃尔什转换

沃尔什转换的转换式为

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

其中${\displaystyle W[m,n]}$ 是沃尔什转换矩阵的第（m,n）个元素。 举例来说，一个8点沃尔什转换的转换矩阵如下：

${\displaystyle 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}}}$ 

后面会解释沃尔什转换矩阵是如何产生，而沃尔什转换的反转换式为

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

注意到正转换式与反转换式只差了一个常数，这是由于沃尔什转换矩阵的反矩阵就是自己的转置矩阵乘上一个常数的缘故。

${\displaystyle 2^{k}}$ 点的沃尔什矩阵可以用下面的递回方式产生：

起始值${\displaystyle k=1}$ （2点沃尔什转换矩阵）

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

假设我们已经有一个${\displaystyle 2^{k}}$ 点的沃尔什转换矩阵${\displaystyle W_{2^{k}}}$  则我们可以借由下面的方法来产生${\displaystyle 2^{k+1}}$ 点的沃尔什转换矩阵${\displaystyle W_{2^{k+1}}}$ 

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

Step 2 根据变号次数把${\displaystyle V_{2^{k+1}}}$ 的列（row）重新排列成为${\displaystyle W_{2^{k+1}}}$ 

以下举一个使用4点沃尔什转换矩阵产生8点沃尔什转换矩阵的例子：

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

${\displaystyle 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}}}$ 

接着对${\displaystyle V_{8}}$ 的列做排序即可得上面的${\displaystyle W_{8}}$ 。

在不同的应用上，我们较常使用的沃尔什矩阵的列的排列顺序也不同，以下以一个表来区分：

若使用二进制来表示各种顺序的列的编号，则双积顺序的二进制编号是序数顺序的格雷码编码，而自然顺序的二进制编号是双积顺序的位元反转。

（1） 正交性质

沃尔什转换矩阵的每个列是互相正交的，即如果${\displaystyle m_{0}\neq m_{1}}$ 则${\displaystyle \sum _{n=0}^{N-1}W[m_{0},n]W[m_{1},n]=0}$ 

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

${\displaystyle 2^{k}}$ 点沃尔什转换矩阵的每个列的变号次数都不相同，分别为变号0次到变号${\displaystyle 2^{k}-1}$ ，这个性质是沃尔什转换可以用来做频谱分析的原因之一，不同的变号次数相当于不同的频率。

（3） 奇偶性质

沃尔什转换矩阵（沃尔什顺序）中，编号为偶数的列是偶对称，编号为奇数的列是奇对称。（有第0列）

（4） 线性性质

若${\displaystyle f[n]\Rightarrow F[m]}$ ，${\displaystyle g[n]\Rightarrow G[m]}$ ，（${\displaystyle \Rightarrow }$ 表沃尔什转换）则有${\displaystyle af[n]+bg[n]\Rightarrow aF[m]+bg[m]}$ 。

（5） 加法性质

${\displaystyle W[m,n]W[l,n]=W[m\oplus l,n]}$ ，${\displaystyle \oplus }$ 表示逻辑互斥或（exclusive or）

（6） 平移性质

若${\displaystyle f[n]\Rightarrow F[m]}$ 则${\displaystyle f[n\oplus k]\Rightarrow W[k,m]F[m]}$ 

（7） 调变性质

若${\displaystyle f[n]\Rightarrow F[m]}$ 则${\displaystyle W[k,n]f[n]\Rightarrow F[k\oplus m]}$ 

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

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

（9） 折积性质

若${\displaystyle f[n]\Rightarrow F[m]}$ ，${\displaystyle g[n]\Rightarrow G[m]}$ ，则${\displaystyle \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]}$ ，在这里${\displaystyle \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）。

由于一个${\displaystyle 2^{k}}$ 点沃尔什转换矩阵可以由${\displaystyle 2^{k-1}}$ 点的沃尔什转换矩阵堆叠后做变号与排序产生，因此一个${\displaystyle 2^{k}}$ 沃尔什转换可以由做两次${\displaystyle 2^{k-1}}$ 的沃尔什转换及一些加减法和排序产生，可以得到一个类似快速傅立叶变换的蝴蝶结构。

1. 运算数值皆为实数不存在复数
2. 不需要应用到乘法运算
3. 频谱分析( spectrum analysis)
4. 正向转换跟反向转换结构相似
   • Forward :${\displaystyle F[m]=\textstyle \sum _{n=0}^{N-1}\displaystyle f[n]W[m,n]}$ 
   • Inverse : ${\displaystyle f[m]=1/N\textstyle \sum _{n=0}^{N-1}\displaystyle F[n]W[m,n]}$ 
5. 跟DFT有一样的以下性质
   1. 正交性质
   2. 零交（zero-crossing）性质
   3. 线性运算性质
   4. 调变性质
   5. 巴斯瓦定理（Parseval's Theorem)

沃尔什转换适合做频谱分析，但未必适合做折积

因此不适合分析线性非时变系统(LTI system)

证明:

• Linear convolution (standard form of convolution)

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

• Circular convolution

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

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

• Logic convolution

${\displaystyle 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"

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

${\displaystyle {\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点沃尔什转换${\displaystyle 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.