0 引言

近年来，正交变换的理论和方法引起了科学界和工程界的广泛关注^[1~4]，在信号处理领域内得到了广泛应用。离散Walsh变换是信号处理领域中应用比较广泛的一种正交变换^{[1, 5]}。变换是信号处理系统的一种数学抽象。在数学上，可将变换看成一种算法或算子。离散正交变换算子的矩阵形式是正交矩阵。由于正交矩阵的逆矩阵的存在性，保证了信号的恢复或重建。另外，由于正交变换满足Parseval定理，保证了信号变换前后能量的守恒。原始信号经过正交变换后得到一组离散系数（谱系数），这组系数通常将原始信号的能量集中在少数系数上，减少了原始信号中各分量的相关性。虽然早在1923年Walsh已提出了完整的Walsh函数的数学理论^[6]，但Walsh变换真正被人们重视并付诸应用，则是在20世纪60年代快速算法^[7]提出以后。它在近代数字逻辑理论和技术中的应用则是在20世纪70年代^{[8, 9]}。目前，Walsh变换的理论和谱技术在计算机科学与技术、通信技术、图像压缩、密码学、近代数字逻辑理论，以及量子可逆逻辑电路等方面均获得了应用^{[2~4, 10]}。由于基函数的排序不同，Walsh变换具有以不同序表示的形式。本文讨论了以Hadamard序表示的离散Walsh变换，或称为Walsh-Hadamard变换，并导出了这种变换的一种并行算法。这种离散正交变换的算子形式可用Hadamard矩阵表示。由于Hadamard矩阵有简单的递推公式，因此这种Walsh变换的应用很广泛。

对于离散Walsh变换的谱系数的计算，虽然有相应的快速算法，但当问题的规模n 增加时，其计算时间将迅速（指数阶）增加，此时应采用并行计算方法来解决此问题。本文将一维Walsh变换转换为二维Walsh变换，并将其用两个一维离散Walsh变换的并行算法计算，导出了离散Walsh变换算法的一种并行算法及其快速并行算法。该算法使计算Walsh谱系数的算法的时间复杂度降低，并且这种算法为实数域上的矩阵运算，适合用高级语言编程实现。

1 布尔函数的分解和Walsh-Hadamard变换的并行算法 1.1 离散Walsh-Hadamard变换

像三角函数系一样，Walsh函数系是一个完备的正交函数系^[6]，其中每个函数只取+1和-1两个值，其波形呈双极性矩形波波形。Hadamard矩阵可以由以Hadamard序排列的Walsh函数Wal_H (k，θ)的波形对归一化时间θ（θ 不一定是时间）的主值区间[0，1），以N=2ⁿ （n 为正整数）等份均匀采样求得。例如，当n=3时，对前8个Wal_H (k，θ)函数的波形以N=8等份均匀采样，得到以Hadamard序排列的离散Walsh函数为Wal_H (k，m)，其中，k，m = 0，1，⋯，N-1。将它们排列成一个8阶的矩阵，则得一个8阶的Hadamard矩阵H₃，利用矩阵的Kronecker乘积运算（也称直积运算），以符号“⊗”表示这种运算，可将它表示为

式中H₁和H₂分别为2阶和4阶的Hadamard矩阵。利用递推公式可得2ⁿ阶Hadamard矩阵为

(1)

若把一个离散时间信号f（m），m=0，1，…，2ⁿ-1，n 为正整数，看成相应的信号空间的一个点，即一个列向量f= [ f (0)，f (1)，⋯，f (2ⁿ-1)]^T，则得该信号的离散Walsh变换和离散Walsh反变换如下

(2)

式中S= [S (0)，S (1)，⋯，S (2ⁿ-1)]^T，称为谱系数列向量，其中各分量称为谱系数。

1.2 布尔函数的分解

布尔（Boolean）函数即二值逻辑函数，简称逻辑函数，其变量和函数均在布尔集合{0，1}上取值。对于一个定义在变量集合X= {x₁，x₂，⋯，x_n}上的n 变量函数f (X)，由Shannon展开定理，可导出它在布尔域上的最小项展开式为

(3)

定义

(4)

则得，最小项为（e₁e₂⋯e_n）₂（下标2表示二进制数）的十进制数表示，即j = ，与之相应的系数为c_j =f (e₁，e₂，⋯，e_n)。令 则将（3）式写成矩阵形式为

(5)

在变量集合X上取划分

(6)

其中，B₁ ∪ B₂ = X，B₁ ∩ B₂ = ∅，以子集合B₁和B₂中的变量分别组成两组最小项：

并令则得

(7)

由（5）式得该函数的最小项展开式为

(8)

将矩阵C按划分式（6）重新排序为一个矩阵，称之为划分矩阵，如下

(9)

则得

(10)

若令

(11)

则得

(12)

亦即

(13)

（13）式即为原函数按照划分式（6）的Shannon展开（分解）式。

1.3 Walsh变换的并行算法

在数字信号逻辑处理中，常把一个n 变量布尔函数f (x₁，x₂，⋯，x_n)看作一个数字信号f（m）进行分析、设计或其他处理，其中，m = (x₁ x₂⋯x_n)₂，0 ≤ m ≤ (2ⁿ - 1)。然而，对于数字逻辑研究领域中所涉及的上述问题，当函数中的变量数目增多时，这些问题在布尔空间直接解决是较困难的，而在Walsh谱空间解决则较有效。当从布尔空间变换到Walsh谱空间时，函数的取值作0 → 1，1 → -1变换，其运算为实数域上的乘法运算和加法运算。将函数f (x₁，x₂，⋯，x_n)之值c_m以0 → 1，1 → -1变换，得到相应的值a_m，m = 0，1，⋯，(2ⁿ - 1)。令列向量为F= [a₀，a₁，⋯，a₂n_-1]^T，则得该布尔函数的离散Walsh变换和离散Walsh反变换如下

(14)

注意到，上述离散Walsh变换和离散Walsh反变换的矩阵形式是以数字信号的逻辑处理中的形式来定义的，（14）式中2ⁿ 阶的Hadamard矩阵H_n 由下式定义：

(15)

谱系数列向量S= [S₀，S_n，S_n-1，S_(n-1) n，S_n-2，⋯, S₁₂⋯n]^T。S_j下标的取法如下：当j=0时，S_j= S₀；当j ≠ 0时，S_j的一组下标为j = (x₁ x₂⋯x_{n - 1}x_n)₂中取值为1的变量的下标组合，例如(x₁ x₂⋯x_{n - 1}x_n)₂ = (00⋯01)₂表示S_n，(00⋯10)₂表示S_{n - 1}，(00⋯11)₂表示S_{(n- 1)} n 等。各阶谱系数的意义如下：S₀称为0阶谱系数，它表示f (X)与常量的相关性（相似程度），若S₀ =+2ⁿ （由于变换矩阵H_n 的正交性，其余的谱系数必均为0），表示f (X)为常量0；若S₀ = -2ⁿ，表示f (X)为常量1。事实上，S₀表示函数f (X)中的常量0的个数与常量1的个数之差。S_i称为一阶谱系数，它表示f (X)与相应的变量x_i的相关性，若S_i= +2ⁿ，则表示f (X)= x_i；若S_i= -2ⁿ，则表示f (X)= x_i，1 ≤ i ≤ n。其余的谱系数称为高阶谱系数，它们分别表示函数f (X)与相应的异或函数的相关性。例如S_ij称为二阶谱系数，i ≠ j，1 ≤ i，j ≤ n，它们表示函数f (X)与相应的异或函数（x_i⊕x_j）的相关性。又如，S₁₂⋯n 称为n 阶谱系数，它表示函数f (X)与异或函数（x₁⊕x₂⊕… ⊕x_n）的相关性。

为了导出Walsh变换的并行算法，按照划分式（6），将列向量F重新排列为一个2^r × 2^n-r矩阵为

(16)

令各子函数f₀ (B₂)，f₁ (B₂)，⋯，f_{2^r- 1} (B₂)的列向量分别为

(17)

并令各个子函数f₀ (B₂)，f₁ (B₂)，⋯，f_{2^r- 1} (B₂)的Walsh谱系数列向量分别为

(18)

（18）式中各子函数（0 ≤ k ≤ (2^r - 1)）的谱系数用上标表示。由Walsh变换的公式，得各子函数的Walsh变换式为

(19)

或以矩阵形式表示为

(20)

其中子函数谱系数矩阵SF 为一个2^{n- r} × 2^r 矩阵，该矩阵的每一列对应一个子函数的谱系数列向量 SF_k。和（8）式相类比，利用Kronecker矩阵乘积的性质，将（14）式中第一式按照划分式（6）表示为

(21)

并且按照划分式（6）将原函数f (X)的谱系数列向量S排列成一个矩阵为

(22)

该矩阵的纵坐标和横坐标分别为(x₁ x₂⋯x_r)₂和(x_{r + 1} x_{r + 2}⋯x_n)₂，谱系数下标的编码方法如上所述。将（22）式用2^r 阶Hadamard逆矩阵[H_r]^-1 = (1/2^r) ⋅ H_r 相乘，即将B₁的变量由谱域反变换到布尔域，作为子函数f_k(X)所含原函数最小项的公因子I_k(B₁)，0 ≤ k ≤ (2^r - 1)，剩余子函数谱系数矩阵的转置矩阵[SF]^T为

(23)

该转置矩阵[SF]^T的每一行对应一个子函数谱系数行向量，即[SF_k]^T，0 ≤ k ≤ (2^r - 1)。将（23）式两边左乘矩阵H_r，则得 S_re = H_r ⋅ [SF]^T（24）利用（20）式，则得

(25)

利用Hadamard矩阵的性质，并利用（20）式及（23）式，即可推得

(26)

并且按照划分式（6）将原函数f (X)分解得到各个子函数的谱系数，可以利用（23）式由原函数f (X)的谱系数矩阵S_re求得；利用（24）式，可以由各子函数的谱系数行向量构成的矩阵[SF]^T求得原函数f (X)的谱系数矩阵S_re。（25）式和（26）式分别为Walsh变换并行算法公式和Walsh反变换并行算法公式，可以利用Hadamard矩阵直接计算得到，也可以利用快速Walsh变换算法实现。

1.4 Walsh变换的快速并行算法

求给定函数的Walsh谱系数的快速并行算法，可以由（20）式和（24）式，分别利用快速Walsh变换并行算法的迭代过程流图^[11]通过两步计算实现。

下面以一个简单的例子，说明该快速并行算法的一般步骤。

例1   求4变量布尔函数f (X)= Σ(0, 1, 2, 4, 6, 9, 10, 11, 13)的Walsh谱系数。

计算步骤如下：

1）取划分X= {B₁；B₂}= {x₁，x₂；x₃，x₄ }，n= 4，r=2。

2）由函数f (X)的函数值，按照上述划分排列成矩阵C_re，将矩阵C_re的元素值0 → 1，1 → -1变换，得到谱域值矩阵F_re，分别为

3）计算SF = H_n-r ⋅ [F_re]^T。其迭代过程流图如图 1所示。图 1中的连线表示对应的操作是将前行各元素与分别乘以“ +1”（或“-1”）后的后行各元素相加形成新的（迭代后的）前行（或后行）。

4）计算S_re = H_r ⋅ [SF]^T。其迭代过程流图如图 2所示。图 2中，S_re的纵坐标和横坐标分别为(x₁ x₂)₂ = (00，01，10，11)₂和(x₃ x₄)₂ = (00，01，10，11)₂，在矩阵S_re中各元素的编码方法如上所述。

将矩阵S_re进行矩阵的拉直运算，即得由（14）式第1式求得的谱系数列向量

2 算法的时间复杂度分析 2.1 Walsh变换算法的时间复杂度

设N=2ⁿ，n 为变量个数（或问题的规模），计算N=2ⁿ 点的Walsh谱系数，需做N²次乘法，N (N - 1)次加法，时间复杂度为

2.2 快速Walsh变换算法的时间复杂度

计算N=2ⁿ 点的Walsh谱系数，需做N log₂ N 次加、减法运算，时间复杂度为

2.3 Walsh变换并行算法的时间复杂度

设r+q=n，N₁=2^r，N²=2^q，计算N=2ⁿ 点的Walsh谱系数，需做(N₁ N² ₂ + N² N² ₁)次乘法，(N₁ N² (N² - 1)+ N² N₁ (N₁ - 1))次加法。当n 为偶数时，取r=q=n/2，时间复杂度为。当n 为奇数时，取r =（n-1）/2，q=（n+1）/2，计算N=2ⁿ 点的Walsh谱系数，时间复杂度为

2.4 Walsh变换的快速并行算法的时间复杂度

当n 为偶数时，取r=q=n/2，计算N =2ⁿ 点的Walsh谱系数，需做(2^q log₂ 2^q + 2^r log₂ 2^r)次向量加、减法运算，时间复杂度为

当n 为奇数时，取r=（n-1）/2，q=（n+1）/2，计算N=2ⁿ 点的Walsh谱系数，时间复杂度为

已有Walsh变换算法与本文算法计算次数的比较，见表 1。

把变换的计算速度定义为每秒完成的计算次数，由表 1可以看出当变量个数n=10时，本文导出的并行算法速度是Walsh变换算法速度的2⁴倍，当n =20时，则为2⁹倍；当变量个数n=10时，本文导出的并行快速算法速度是快速Walsh变换算法速度的2⁵倍，当变量个数n=20时，则为2¹⁰倍。

3 结语

本文基于布尔函数的分解方法，导出了计算Walsh谱系数的一种并行计算方法及其快速并行算法。这两种算法降低了计算的时间复杂度，适用于高级语言编程计算，并且为Walsh变换的并行算法和并行快速算法的硬件实现提供了理论基础。