沃尔什函数

沃尔什函数（英语：Walsh function，或称Walsh system）可以被看作一个和连续类比系统的三角波相对应的系统，可以说是离散而且数位版本的三角波。和三角波不同，沃尔什函数只有部分连续。这个函数的值域只有 −1 和 +1 两个值。有了沃尔什函数当作基础，当我们要进行类似于傅立叶转换的沃尔什转换时，不需要做在虚数值域上的浮点数计算，而能够减少计算量与误差。

自然顺序（哈德码得顺序）和 序数顺序 （沃尔什顺序），大小皆为16。 前者通常称作沃尔什矩阵.
后者每行的符号变更是连续的，可以用于频谱分析。

不论是三角波，或是沃尔什函数都能透过周期性延伸至整个实数空间${\displaystyle \mathbb {R} }$。另外，傅立叶分析在数位系统所对应到的方波可以用沃尔什函数来表达。沃尔什函数，数列，和转换，在物理和工程上面，都有相当多的应用，特别在数位语音处理上面。他的主要应用包含语音辨识，在生物医学领域的影像处理，和其他领域。

历史上，许多种类的沃尔什函数都曾被使用，而一般来说都各有优劣。在下文中，使用Walsh-Paley函数来代表沃尔什函数。

定义

我们定义沃尔什函数的序列 ${\displaystyle W_{k}:[0,1]\rightarrow \{-1,1\}}$, ${\displaystyle k\in \mathbb {N} _{0}}$如下:

对于任何 ${\displaystyle k\in \mathbb {N} _{0}}$, ${\displaystyle x\in [0,1]}$ 令:

${\displaystyle k=\sum _{j=0}^{\infty }k_{j}2^{j},k_{j}\in \{0,1\}}$,   ${\displaystyle x=\sum _{j=1}^{\infty }x_{j}2^{-j},x_{j}\in \{0,1\}}$

使得只有有限多个非零的 k_j 和 x_j 等于 1, 也分别是整数 k 和实数 x的 二进制 表示。 根据定义

${\displaystyle W_{k}(x)=(-1)^{\sum _{j=0}^{\infty }k_{j}x_{j+1}}}$

特别得，${\displaystyle W_{0}(x)=1}$ 对于所有范围内的 x 都成立。

注意到 ${\displaystyle W_{2^{m}}}$ 正好是拉德马赫函数（英语：Rademacher system） r_m。 因此拉德马赫系统是沃尔什系统的一个子集合。 另外，每一个沃尔什函数都能透过拉德马赫函数的乘积得到。

${\displaystyle W_{k}(x)=\prod _{j=0}^{\infty }r_{j}(x)^{k_{j}}}$

性质

• 沃尔什函数是片段常数，

证明:

考虑

${\displaystyle k=\sum _{j=0}^{a}k_{j}2^{j},k_{j}\in \{0,1\}}$,

${\displaystyle x=\sum _{j=1}^{\infty }x_{j}2^{-j},x_{j}\in \{0,1\}}$

${\displaystyle y=\sum _{j=1}^{\infty }y_{j}2^{-j},y_{j}\in \{0,1\}}$

${\displaystyle W_{k}(x)=(-1)^{\sum _{j=0}^{a}k_{j}x_{j+1}}}$

考虑 ${\displaystyle x,y\in [r2^{-a},(r+1)2^{-a})}$

只要对于 j ≤ a， ${\displaystyle x_{j}=y_{j}}$

${\displaystyle W_{k}(x)=(-1)^{\sum _{j=0}^{a}k_{j}x_{j+1}}=(-1)^{\sum _{j=0}^{a}k_{j}y_{j+1}}=W_{k}(y)}$

因此 ${\displaystyle W_{k}(x)}$ 在 ${\displaystyle [r2^{-a},(r+1)2^{-a})}$ 中是常数。

• 沃尔什系统是一个 希尔伯特空间${\displaystyle L^{2}[0,1]}$的标准正交基，标准正交的定义如下:

${\displaystyle \int _{0}^{1}W_{k}(x)W_{l}(x)dx=\delta _{kl}}$,

证明:

当 k= l, ${\displaystyle \int _{0}^{1}W_{k}(x)W_{l}(x)dx=\int _{0}^{1}1dx=1}$

当 k ≠ l,

${\displaystyle k=\sum _{j=0}^{a}k_{j}2^{j},k_{j}\in \{0,1\}}$,

${\displaystyle l=\sum _{j=0}^{b}l_{j}2^{j},l_{j}\in \{0,1\}}$,

不失一般性，令 a ≥ b，

${\displaystyle \int _{0}^{1}W_{k}(x)W_{l}(x)dx}$

${\displaystyle =2^{-a}\sum _{r=0}^{2^{a}-1}W_{k}(r2^{-a})W_{l}(r2^{-a})}$

${\displaystyle =2^{-a}\prod _{i=0}^{a-1}{1/2\sum _{r_{a-i-i}=0}^{1}{(-1)^{(k_{i}+l_{i})r_{a-1-i}}}}}$

因为 k ≠ l ，一定存在 i 使得 ${\displaystyle k_{i}}$ ≠ ${\displaystyle l_{i}}$，假设 ${\displaystyle k_{i_{0}}}$ ≠ ${\displaystyle l_{i_{0}}}$，

那么 ${\displaystyle k_{i_{0}}+l_{i_{0}}=1}$，那么

${\displaystyle 2^{-a}\prod _{i=0}^{a-1}{1/2\sum _{r_{a-i-i}=0}^{1}{(-1)^{(k_{i}+l_{i})r_{a-1-i}}}}=0}$

因此得到 ${\displaystyle \int _{0}^{1}W_{k}(x)W_{l}(x)dx=0}$ 对于 k ≠ l。 Q.E.D.

而基的定义是, 对于所有的 ${\displaystyle f\in L^{2}[0,1]}$, 我们让 ${\displaystyle f_{k}=\int _{0}^{1}f(x)W_{k}(x)dx}$ 那么

${\displaystyle \int _{0}^{1}(f(x)-\sum _{k=0}^{N}f_{k}W_{k}(x))^{2}dx{\xrightarrow[{N\rightarrow \infty }]{}}0}$

对于所有的 ${\displaystyle f\in L^{2}[0,1]}$, 序列 ${\displaystyle \sum _{k=0}^{\infty }f_{k}W_{k}(x)}$ 收敛到 ${\displaystyle f(x)}$ 对于几乎所有的 ${\displaystyle x\in [0,1]}$.

• 沃尔什函数 都有种对称性，一定是偶函数或者奇函数。

• 沃尔什系统(Walsh-Paley) 会形成一个 Schauder basis（英语：Schauder basis） 在${\displaystyle L^{p}[0,1]}$,   ${\displaystyle 1<p<\infty }$。注意到，与 Haar system不同，而与三角波系统相似，这个基并不是unconditional，他在${\displaystyle L^{1}[0,1]}$中也不是一个 Schauder basis。

• 沃尔什系统${\displaystyle \{W_{k}\},k\in \mathbb {N} _{0}}$是一个连续离散的群组和 ${\displaystyle \coprod _{n=0}^{\infty }\mathbb {Z} /2\mathbb {Z} }$ 同构，

费米子沃尔什系统

费米子 沃尔什系统是一个以"量子"版本的沃尔什系统。与后者不同，他包含了运算操作，而非函式。然而，两种系统有许多相同的重要功能，像是都是一个希尔伯特空间的标准正交基，或是在相对应空间的 Schauder basis（英语：Schauder basis）。在费米子沃尔什系统的元素被称做 "沃尔什操作元"。

和沃尔什-阿达玛转换的关系

• 二点阿达玛矩阵：

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

• 四点阿达玛矩阵：

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

• 八点阿达玛矩阵：

${\displaystyle {\boldsymbol {W_{8}}}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\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{bmatrix}}.}$

这些阿达玛转换的矩阵，其中每一行，都是一个沃尔什函数。

而阿达玛转换式子如下:

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

而得到阿达玛矩阵的方法如下:

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}}}$转换成为${\displaystyle W_{2^{k+1}}}$

优缺点比较

沃尔什函数和正余弦函数的比较，也可以看成沃尔什转换和傅立叶转换的比较:

优点

• 只有实数运算，不需要做复数运算。
• 仅有0或1，因此不需乘法运算 (No multiplication) ，仅有加减法运算。
• 有部分性质类似于离散傅立叶变换 。
• 适合频谱分析。
• 沃尔什转换顺向转换 (Forward transform) 与沃尔什转换逆向转换 (Inverse transform ) 非常相似。

${\displaystyle {\begin{cases}{\begin{matrix}F\left[m\right]&=&\sum _{n=0}^{N-1}W\left[{m,n}\right]f\left[n\right]&&({\mbox{Forward}})\\f\left[n\right]&=&\left({\frac {1}{N}}\right)\sum _{n=0}^{N-1}W\left[{m,n}\right]F\left[m\right]&&({\mbox{Inverse}})\end{matrix}}\end{cases}},}$

其中 ${\displaystyle F\left[n\right]}$ 与 ${\displaystyle f\left[n\right]}$ 分别都为行向量 (Column vector) 。

缺点

• 收敛速度较慢。
• 其加减法总量较多。
• 折积上性质无法取代离散傅立叶变换

应用

• 在数学上的应用，可以再任何需要数字表示的时候使用，如沃尔什转换。另外，也存在一个快速沃尔什转换，和沃尔什转换相比会有更高的效率。一些沃尔什转换的应用如下:
  • 带宽降低 (Bandwidth reduction) 。
    • 在微处理器的硬件限制之下，沃尔什转换能够代替傅立叶转换执行带宽降低的功能。
  • CDMA (Code division multiple access)。
    • 举例而言，如果要把 [1 0 1] 和 [0 1 1] 要传输，可以选两个沃尔什函数，如[1,1,1,1,1,1,1,1] 和 [1,1,1,1,-1,-1,-1,-1]
    • 1. 把 0转成 -1， [1 0 1] 看作 [1 -1 1]，[0 1 1] 看作 [-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]
    • 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]
    • 4. 把上面两者相加，成为 [0,0,0,0,2,2,2,2,0,0,0,0,-2,-2,-2,-2,2,2,2,2,0,0,0,0]。
    • 5. 解调时，把 [0,0,0,0,2,2,2,2,0,0,0,0,-2,-2,-2,-2,2,2,2,2,0,0,0,0] 和 第一个沃尔什函数分三段内积，得到[8,-8,8]，得知第一个讯号是 [1 0 1]
    • 6. 解调时，把 [0,0,0,0,2,2,2,2,0,0,0,0,-2,-2,-2,-2,2,2,2,2,0,0,0,0] 和 第二个沃尔什函数分三段内积，得到[-8,8,8]，得知第二个讯号是 [0 1 1]
  • 资讯编码 (Information coding)。
  • 特征识别 (Feature extraction)。
    • 沃尔什函数的对称性使得他很适合拿来抽取一些几何的规律。
    • 折积(convolution)在CNN中被拿来抽取图形的资讯有很好的效果，而相类似的沃尔什函数也有不错的效果。
  • 心电图分析 (ECG signal analysis in medical signal processing)。
    • 利用沃尔什函数的快速转换能够压缩ECG讯号，随着沃尔什函数系数的减少，压缩率也会提高。
  • 频率调整 (frequency modulation)
  • 形状分析 (shape analysis)。

• 沃尔什函数还被应用在雷达天文上来缓解不同天线讯号电子串扰的问题。这些在被动LCD的平面中，可以使得不同的传输讯号的相关性最低。

参见

• 沃尔什转换
• 阿达马矩阵
• 阿达马变换
• Exclusive or
• 约瑟夫·L·沃尔什

外部链接

• Walsh functions at MathWorld （页面存档备份，存于互联网档案馆）
• Walsh functions at Stanford Exploration Project （页面存档备份，存于互联网档案馆）
• Walsh functions I. Orthonormality and completeness （页面存档备份，存于互联网档案馆）

参考资料

• Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2016.
• 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.
• Alexandridis, N. A., and A. Klinger. "Walsh orthogonal functions in geometrical feature extraction." IEEE Transactions on Electromagnetic Compatibility 3 (1971): 18-25.
• Hutchinson, N. "Bandwidth reduction for speech transmission using a sixteen-bit microprocessor." Journal of microcomputer applications 5.2 (1982): 119-128.
• Kulkarni, P. K., Vinod Kumar, and H. K. Verma. "ECG data compression using fast Walsh transform and its clinical acceptability." International journal of systems science 28.8 (1997): 831-836.
• Romanuke, V. V. "On the Point of Generalizing the Walsh Functions to Surfaces." Bulletin of KhNU. Technical Sciences 6.1 (2007): 187-193.