Walsh 函数

Walsh 函数由方波脉冲序列组成（允许的状态为 和 1），使得跃迁可能只发生在单位时间步长的固定间隔处，初始状态始终为 ，并且这些函数满足某些正交关系。 特别是， 阶 Walsh 函数 由 Hadamard 矩阵 的行给出，当以所谓的“序数”顺序排列时（Thompson et al. 1986, p. 204; Wolfram 2002, p. 1073）。 存在 个长度为 的 Walsh 函数，如上图所示，针对 、2 和 3。

电气工程师，如 Frank Fowle，在 1890 年代使用 Walsh 函数来查找最小化串扰的导线换位，Walsh (1923; Wolfram 2002, p. 1073) 将其引入数学领域。

令人惊讶的是，连接 Walsh 函数 （同时用 0 替换 ），其中 是 上限函数，给出了 Thue-Morse 序列 (Wolfram 2002, p. 1073)。 的值由 显式给出，前几个值为 1, 2, 3, 6, 11, 22, 43, 86, 171, ... (OEIS A005578)。

Walsh 函数可以以多种方式排序，如上图所示 (Wolfram 2002, p. 1073)。 Walsh 函数的序数 定义为时间基一个周期内过零点数量的一半。 在序数顺序（左图）中，每行比前一行多一个颜色变化。 在自然（或 Hadamard）顺序（中图）中，Walsh 函数显示嵌套结构。 Dyadic（或 Paley）顺序（右图）与行的 格雷码 重新排序有关 (Wolfram 2002, p. 1073)。

具有不同序数的 Walsh 函数是正交的，函数 和 也是正交的。 两个 Walsh 函数的乘积也是 Walsh 函数。

Harmuth (1969) 指定偶 Walsh 函数 和奇 Walsh 函数 ，

			(1)
			(2)

其中 是序数。

将一组二维数据（表示为大小为 2 的幂的方阵）与相应的 Walsh 函数数组进行矩阵乘积称为 Walsh 变换 (Wolfram 2002, p. 1073)。 Walsh 变换可以特别有效地执行，从而产生所谓的快速 Walsh 变换。