Walsh变换的一种快速并行算法

Walsh变换的一种快速并行算法 A Fast Parallel Algorithm of the Walsh Transform 1 first-author 姜恩华，男，副教授，现从事数字信号处理与传输方面的研究。E-mail:jianghnhb@126.com 姜恩华，男，副教授，现从事数字信号处理与传输方面的研究。E-mail:jianghnhb@126.com jianghnhb@126.com 淮北师范大学 物理与电子信息学院，安徽 淮北 235000 淮北师范大学 物理与电子信息学院，安徽 淮北 235000 School of Electronic Information, Huaibei Normal University, Huaibei 235000, Anhui, China School of Electronic Information, Huaibei Normal University, Huaibei 235000, Anhui, China 在数字信号的逻辑处理基础上，利用布尔函数的分解方法，导出了离散Walsh变换的一种并行算法及其快速并行算法。对已有Walsh变换算法及本文算法的时间复杂度进行了分析，该分析表明本文算法时间复杂度有一定程度下降。当变量个数为20时,本文提出的Walsh并行算法速度是Walsh变换算法速度的2 9 倍,快速并行算法速度是快速Walsh变换算法速度的2 10 倍。本文提出的算法适用于高级语言编程实现。 Based on the logical processing of the digital signals, a parallel algorithm and its fast parallel algorithm of the Walsh transform have been developed by using decomposition method of the Boolean functions. The time complexities of the existing Walsh transform algorithms and the algorithms proposed in this paper were analyzed. It is shown that the time complexity of the algorithm in this paper has been reduced to a certain extent. When the number of variables is 20, the speed of Walsh parallel algorithm proposed in this paper is 2 9 times faster than the existing Walsh transformation algorithm. The speed of Walsh parallel fast algorithm proposed in this paper is 2 10 times faster than the existing Walsh transformation fast algorithm. The algorithm proposed in this paper is suitable for advanced language programming implementation. 布尔函数 Walsh⁃Hadamard变换 谱技术 并行计算 Boolean function Walsh-Hadamard transform spectral techniques parallel computing 姜恩华.Walsh变换的一种快速并行算法[J].武汉大学学报（理学版）,2019,65(6):576-580. DOI:10.14188/j.1671-8836.2019.06.007. 0　 引 言 1 近年来，正交变换的理论和方法引起了科学界和工程界的广泛关注 [ 1 1 , 2 2 , 3 3 , 4 4 ] ，在信号处理领域内得到了广泛应用。离散Walsh变换是信号处理领域中应用比较广泛的一种正交变换 [ 1 1 , 5 5 ] 。变换是信号处理系统的一种数学抽象。在数学上，可将变换看成一种算法或算子。离散正交变换算子的矩阵形式是正交矩阵。由于正交矩阵的逆矩阵的存在性，保证了信号的恢复或重建。另外，由于正交变换满足Parseval定理，保证了信号变换前后能量的守恒。原始信号经过正交变换后得到一组离散系数（谱系数），这组系数通常将原始信号的能量集中在少数系数上，减少了原始信号中各分量的相关性。虽然早在1923年Walsh已提出了完整的Walsh函数的数学理论 [ 6 6 ] ，但Walsh变换真正被人们重视并付诸应用，则是在20世纪60年代快速算法 [ 7 7 ] 提出以后。它在近代数字逻辑理论和技术中的应用则是在20世纪70年代 [ 8 8 , 9 9 ] 。目前，Walsh变换的理论和谱技术在计算机科学与技术、通信技术、图像压缩、密码学、近代数字逻辑理论，以及量子可逆逻辑电路等方面均获得了应用 [ 2 2 , 3 3 , 4 4 , 10 10 ] 。由于基函数的排序不同，Walsh变换具有以不同序表示的形式。本文讨论了以Hadamard序表示的离散Walsh变换，或称为Walsh-Hadamard变换，并导出了这种变换的一种并行算法。这种离散正交变换的算子形式可用Hadamard矩阵表示。由于Hadamard矩阵有简单的递推公式，因此这种Walsh变换的应用很广泛。 对于离散Walsh变换的谱系数的计算，虽然有相应的快速算法，但当问题的规模 n 增加时，其计算时间将迅速（指数阶）增加，此时应采用并行计算方法来解决此问题。本文将一维Walsh变换转换为二维Walsh变换，并将其用两个一维离散Walsh变换的并行算法计算，导出了离散Walsh变换算法的一种并行算法及其快速并行算法。该算法使计算Walsh谱系数的算法的时间复杂度降低，并且这种算法为实数域上的矩阵运算，适合用高级语言编程实现。 1　 布尔函数的分解和Walsh-Hadamard变换的并行算法 1 1.1　离散Walsh-Hadamard变换 2 像三角函数系一样，Walsh函数系是一个完备的正交函数系 [ 6 6 ] ，其中每个函数只取+1和 <math id="M1"><mtext>-</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 1两个值，其波形呈双极性矩形波波形。Hadamard矩阵可以由以Hadamard序排列的Walsh函数 <math id="M2"><mi mathvariant="normal">W</mi><mi mathvariant="normal">a</mi><msub><mrow><mi mathvariant="normal">l</mi></mrow><mrow><mi mathvariant="normal">H</mi></mrow></msub><mtext>(</mtext><mi>k</mi><mtext>,</mtext><mi>θ</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 17.18733406 4.48733330 的波形对归一化时间 θ （ θ 不一定是时间）的主值区间[0，1），以 N =2 n ( n 为正整数)等份均匀采样求得。例如，当 n =3时，对前8个 <math id="M3"><mi mathvariant="normal">W</mi><mi mathvariant="normal">a</mi><msub><mrow><mi mathvariant="normal">l</mi></mrow><mrow><mi mathvariant="normal">H</mi></mrow></msub><mtext>(</mtext><mi>k</mi><mtext>,</mtext><mi>θ</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 17.18733406 4.48733330 函数的波形以 N =8等份均匀采样，得到以Hadamard序排列的离散Walsh函数为 <math id="M4"><mi mathvariant="normal">W</mi><mi mathvariant="normal">a</mi><msub><mrow><mi mathvariant="normal">l</mi></mrow><mrow><mi mathvariant="normal">H</mi></mrow></msub><mtext>(</mtext><mi>k</mi><mtext>,</mtext><mi>m</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 18.28800011 4.48733330 ，其中， <math id="M5"><mi>k</mi><mtext>,</mtext><mi>m</mi><mtext>=</mtext><mn mathvariant="normal">0,1</mn><mtext>,</mtext></math> http://notExist.jpg http://notExist.jpg 18.54199982 2.87866688 <math id="M6"><mtext>⋯</mtext></math> http://notExist.jpg http://notExist.jpg 3.97933340 2.79399991 , N <math id="M7"><mtext>-</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 5.67266655 2.79399991 。将它们排列成一个8阶的矩阵，则得一个8阶的Hadamard矩阵 <math id="M8"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.23333359 3.72533321 ，利用矩阵的Kronecker乘积运算（也称直积运算），以符号“ <math id="M9"><mtext>⊗</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.55599999 ”表示这种运算，可将它表示为 <math display="block" id="M10"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>⊗</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>=</mtext><mtext>[</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mtext>⊗</mtext><mn mathvariant="normal">3</mn></mrow></msup></math> http://notExist.jpg http://notExist.jpg 38.94666672 4.99533367 式中 H 1 和 H 2 分别为2阶和4阶的Hadamard矩阵。利用递推公式可得2 n 阶Hadamard矩阵为 <math display="block" id="M11"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>=</mtext><mtext>[</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mtext>⊗</mtext><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 19.72733307 4.65666676 若把一个离散时间信号 f ( m )， m =0,1,…，2 n <math id="M12"><mtext>-</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 1， n 为正整数，看成相应的信号空间的一个点，即一个列向量 <math id="M13"><mi mathvariant="bold-italic">f</mi><mtext>=</mtext><mtext>[</mtext><mi>f</mi><mtext>(</mtext><mn mathvariant="normal">0</mn><mtext>)</mtext><mtext>,</mtext><mi>f</mi><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><mi>f</mi><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><msup><mrow><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 51.22333145 3.97933340 ，则得该信号的离散Walsh变换和离散Walsh反变换如下 <math display="block" id="M14"><mi mathvariant="bold-italic">S</mi><mtext>=</mtext><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>/</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>⋅</mtext><mi mathvariant="bold-italic">f</mi></math> http://notExist.jpg http://notExist.jpg 25.31533432 5.07999992 ， <math display="block" id="M15"><mi mathvariant="bold-italic">f</mi><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>⋅</mtext><mi mathvariant="bold-italic">S</mi></math> http://notExist.jpg http://notExist.jpg 15.57866669 4.57200003 式中 <math id="M16"><mi mathvariant="bold-italic">S</mi><mtext>=</mtext><mtext>[</mtext><mi>S</mi><mtext>(</mtext><mn mathvariant="normal">0</mn><mtext>)</mtext><mtext>,</mtext><mi>S</mi><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><mi>S</mi><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><msup><mrow><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 52.66266632 3.81000018 ，称为谱系数列向量，其中各分量称为谱系数。 1.2　布尔函数的分解 2 布尔（Boolean）函数即二值逻辑函数，简称逻辑函数，其变量和函数均在布尔集合{0，1}上取值。对于一个定义在变量集合 <math id="M17"><mi mathvariant="bold-italic">X</mi><mtext>=</mtext><mtext>{</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 30.05666542 4.48733330 上的 n 变量函数 <math id="M18"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 ，由Shannon展开定理，可导出它在布尔域上的最小项展开式为 <math display="block" id="M19"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mover><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>j</mi><mtext>=</mtext><mn mathvariant="normal">0</mn></mrow></munder></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></mover><msub><mrow><mi>c</mi></mrow><mrow><mi>j</mi></mrow></msub><msub><mrow><mi>m</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 25.65399933 9.39799976 定义 <math display="block" id="M20"><msubsup><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup><mtext>=</mtext><mfenced open="{" close="" separators="|"><mrow><mtable columnalign="left"><mtr><mtd><mover><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow><mo>¯</mo></mover><mtext> </mtext><mtext>,</mtext><mi mathvariant="normal">当</mi><msub><mrow><mi>e</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mn mathvariant="normal">0</mn></mtd></mtr><mtr><mtd><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext> </mtext><mtext>,</mtext><mi mathvariant="normal">当</mi><msub><mrow><mi>e</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≠</mtext><mn mathvariant="normal">0</mn></mtd></mtr></mtable></mrow></mfenced><mtext> </mtext><mtext>,</mtext><msub><mrow><mi>e</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>∈</mtext><mtext>{</mtext><mn mathvariant="normal">0,1</mn><mtext>}</mtext><mtext>,</mtext><mn mathvariant="normal">1</mn><mtext>≤</mtext><mi>i</mi><mtext>≤</mtext><mi>n</mi></math> http://notExist.jpg http://notExist.jpg 67.56400299 10.66799927 则得，最小项 <math id="M21"><msub><mrow><mi>m</mi></mrow><mrow><mi>j</mi></mrow></msub><mtext>=</mtext><msup><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mrow></msup><msup><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mrow></msup><mtext>⋯</mtext><msup><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></msup></math> http://notExist.jpg http://notExist.jpg 29.46399879 4.40266657 ， <math id="M22"><mi>j</mi></math> http://notExist.jpg http://notExist.jpg 1.10066664 3.64066648 为( e 1 e 2 <math id="M23"><mtext>⋯</mtext></math> http://notExist.jpg http://notExist.jpg 3.97933340 2.79399991 e n ) 2 （下标2表示二进制数）的十进制数表示，即 <math id="M24"><mi>j</mi><mtext>=</mtext><mtext>(</mtext><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>e</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 22.52133369 4.65666676 ， <math id="M25"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>j</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 26.41599846 4.14866638 ，与之相应的系数为 c j = <math id="M26"><mi>f</mi><mtext>(</mtext><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>e</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 22.85999870 4.65666676 。令 <math id="M27"><mi mathvariant="bold-italic">M</mi><mtext>=</mtext><mtext>[</mtext><msub><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>m</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>]</mtext></math> http://notExist.jpg http://notExist.jpg 37.16866684 5.24933338 ， C = <math id="M28"><mtext>[</mtext><msub><mrow><mi>c</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.48733330 4.48733330 , c 1 <math id="M29"><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>]</mtext></math> http://notExist.jpg http://notExist.jpg 15.74800014 4.31799984 ，则将（3）式写成矩阵形式为 <math display="block" id="M30"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mi mathvariant="bold-italic">M</mi><mtext>⋅</mtext><msup><mrow><mtext>[</mtext><mi mathvariant="bold-italic">C</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 27.43200111 3.97933340 在变量集合 X 上取划分 <math display="block" id="M31"><mtext>{</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>;</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>}</mtext><mtext>=</mtext><mtext>{</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>;</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">2</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 66.71733856 4.48733330 其中， <math id="M32"><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>⋃</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>=</mtext><mi mathvariant="bold-italic">X</mi></math> http://notExist.jpg http://notExist.jpg 19.98133469 4.23333359 ， <math id="M33"><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>⋂</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>=</mtext><mi mathvariant="normal">∅</mi></math> http://notExist.jpg http://notExist.jpg 20.99733353 4.57200003 ，以子集合 <math id="M34"><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.72533321 和 <math id="M35"><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.72533321 中的变量分别组成两组最小项： <math display="block" id="M36"><msub><mrow><mi>I</mi></mrow><mrow><mi>k</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>=</mtext><msubsup><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mrow></msubsup><msubsup><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mrow></msubsup><mtext>⋯</mtext><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mi>r</mi></mrow></msub></mrow></msubsup></math> http://notExist.jpg http://notExist.jpg 30.48000145 4.99533367 ， <math display="block" id="M37"><mi>k</mi><mtext>=</mtext><mtext>(</mtext><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>e</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>e</mi></mrow><mrow><mi>r</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 22.85999870 4.48733330 ， <math display="block" id="M38"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>k</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 26.75466537 3.89466667 <math display="block" id="M39"><msub><mrow><mi>S</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>=</mtext><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub></mrow></msubsup><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">2</mn></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">2</mn></mrow></msub></mrow></msubsup><mtext>⋯</mtext><msubsup><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow><mrow><msub><mrow><mi>e</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></msubsup></math> http://notExist.jpg http://notExist.jpg 36.83000183 4.99533367 ， <math display="block" id="M40"><mi>h</mi><mtext>=</mtext><mtext>(</mtext><msub><mrow><mi>e</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>e</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>e</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 30.05666542 4.48733330 ， <math display="block" id="M41"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>h</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 30.56466866 3.89466667 并令 <math id="M42"><mi>I</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>=</mtext><mtext>[</mtext><msub><mrow><mi>I</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><msub><mrow><mi>I</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>I</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>]</mtext></math> http://notExist.jpg http://notExist.jpg 58.92799759 5.24933338 ， <math id="M43"><mi>S</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>=</mtext><mtext>[</mtext><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>S</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>]</mtext></math> http://notExist.jpg http://notExist.jpg 64.34666443 5.24933338 ，则得 <math display="block" id="M44"><mi mathvariant="bold-italic">M</mi><mtext>=</mtext><mi>I</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>⊗</mtext><mi>S</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 32.00400162 4.74133348 由（5）式得该函数的最小项展开式为 <math display="block" id="M45"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mtext>[</mtext><mi>I</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>⊗</mtext><mi>S</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>]</mtext><mtext>⋅</mtext><msup><mrow><mtext>[</mtext><mi mathvariant="bold-italic">C</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 50.88466644 5.16466665 将矩阵 <math id="M46"><mi mathvariant="bold-italic">C</mi></math> http://notExist.jpg http://notExist.jpg 2.53999996 2.79399991 按划分式（6）重新排序为一个 <math id="M47"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>×</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 14.30866623 3.04799986 矩阵，称之为划分矩阵，如下 <math display="block" id="M48"><msub><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><mfenced open="[" close="]" separators="|"><mrow><mtable><mtr><mtd><msub><mrow><mi>c</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></mtd><mtd><msub><mrow><mi>c</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></mrow></msub></mtd><mtd><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr><mtr><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd></mtr><mtr><mtd><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></mrow></msub></mtd><mtd><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>c</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr></mtable></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 63.16133499 23.19866753 则得 <math display="block" id="M49"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mi>f</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>;</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>=</mtext><mi>I</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>⋅</mtext><mtext>[</mtext><mi>S</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mtext>)</mtext><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 66.46333313 4.91066647 若令 <math display="block" id="M50"><mtext>[</mtext><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>]</mtext><mtext>=</mtext><mi>S</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>⋅</mtext><mtext>[</mtext><msub><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 72.22066498 5.50333357 则得 <math display="block" id="M51"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mi>f</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>;</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 28.61733246 4.65666676 <math display="block" id="M52"><mtext> </mtext><mtext>=</mtext></math> http://notExist.jpg http://notExist.jpg 4.82599974 2.79399991 <math display="block" id="M53"><mtext>[</mtext><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>]</mtext><mtext>⋅</mtext><mtext>[</mtext><mi>I</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msup><mrow><mtext>)</mtext><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 63.66933441 5.50333357 亦即 <math display="block" id="M54"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mi>f</mi><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>;</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>=</mtext><mover><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>k</mi><mtext>=</mtext><mn mathvariant="normal">0</mn></mrow></munder></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></mover><msub><mrow><mi>f</mi></mrow><mrow><mi>k</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>⋅</mtext><msub><mrow><mi>I</mi></mrow><mrow><mi>k</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 61.97600174 8.88999939 （13）式即为原函数按照划分式（6）的Shannon展开（分解）式。 1.3　Walsh变换的并行算法 2 在数字信号逻辑处理中，常把一个 n 变量布尔函数 <math id="M55"><mi>f</mi><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 24.63800049 4.65666676 看作一个数字信号 f ( m )进行分析、设计或其他处理，其中， <math id="M56"><mi>m</mi><mtext>=</mtext><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 26.33133316 4.48733330 ， <math id="M57"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>m</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 28.10933304 3.89466667 。然而，对于数字逻辑研究领域中所涉及的上述问题，当函数中的变量数目增多时，这些问题在布尔空间直接解决是较困难的，而在Walsh谱空间解决则较有效。当从布尔空间变换到Walsh谱空间时，函数的取值作 <math id="M58"><mn mathvariant="normal">0</mn><mtext>→</mtext><mn mathvariant="normal">1,1</mn><mtext>→</mtext><mtext>-</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 24.12999916 2.87866688 变换，其运算为实数域上的乘法运算和加法运算。将函数 <math id="M59"><mi>f</mi><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 24.63800049 4.65666676 之值 <math id="M60"><msub><mrow><mi>c</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.21733332 3.72533321 以 <math id="M61"><mn mathvariant="normal">0</mn><mtext>→</mtext><mn mathvariant="normal">1,1</mn><mtext>→</mtext><mtext>-</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 24.12999916 2.87866688 变换，得到相应的值 <math id="M62"><msub><mrow><mi>a</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.55599999 3.72533321 ， <math id="M63"><mi>m</mi><mtext>=</mtext><mn mathvariant="normal">0,1</mn><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><mtext> </mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 34.12066650 3.81000018 。令列向量为 <math id="M64"><mi mathvariant="bold-italic">F</mi><mtext>=</mtext><mtext>[</mtext><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 35.13666534 5.50333357 ，则得该布尔函数的离散Walsh变换和离散Walsh反变换如下 <math display="block" id="M65"><mi mathvariant="bold-italic">S</mi><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>⋅</mtext><mi mathvariant="bold-italic">F</mi><mtext>,</mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mi mathvariant="bold-italic">F</mi><mtext>=</mtext><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>/</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>⋅</mtext><mi mathvariant="bold-italic">S</mi></math> http://notExist.jpg http://notExist.jpg 47.24399948 4.82599974 注意到，上述离散Walsh变换和离散Walsh反变换的矩阵形式是以数字信号的逻辑处理中的形式来定义的，（14）式中 <math id="M66"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 阶的Hadamard矩阵 <math id="M67"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.23333359 3.72533321 由下式定义： <math display="block" id="M68"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>=</mtext><mtext>[</mtext><mn mathvariant="normal">1</mn><mtext>]</mtext></math> http://notExist.jpg http://notExist.jpg 14.22399998 4.48733330 ， <math display="block" id="M69"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>=</mtext><mfenced open="[" close="]" separators="|"><mrow><mtable><mtr><mtd><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>-</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr></mtable></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 35.30599976 8.55133343 ， <math display="block" id="M70"><mtext>∀</mtext><mi>n</mi><mtext>≥</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 11.59933376 3.30199981 谱系数列向量 <math id="M71"><mi mathvariant="bold-italic">S</mi><mtext>=</mtext><mtext>[</mtext><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext>,</mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>S</mi></mrow><mrow><mtext>(</mtext><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext> </mtext><mi>n</mi></mrow></msub><mtext>,</mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 46.99000168 4.48733330 , <math id="M72"><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">12</mn><mtext>⋯</mtext><mi>n</mi></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 16.00200081 4.65666676 。 <math id="M73"><msub><mrow><mi>S</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 2.96333337 3.72533321 下标的取法如下：当 j =0时， <math id="M74"><msub><mrow><mi>S</mi></mrow><mrow><mi>j</mi></mrow></msub><mtext>=</mtext><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 11.26066685 3.72533321 ；当 <math id="M75"><mi>j</mi><mtext>≠</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 8.55133343 3.72533321 时， <math id="M76"><msub><mrow><mi>S</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 2.96333337 3.72533321 的一组下标为 <math id="M77"><mi>j</mi><mtext>=</mtext><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 31.83466721 4.65666676 中取值为1的变量的下标组合，例如 <math id="M78"><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 26.16199875 4.48733330 <math id="M79"><mtext>=</mtext><msub><mrow><mtext>(</mtext><mn mathvariant="normal">00</mn><mtext>⋯</mtext><mn mathvariant="normal">01</mn><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 20.23533440 4.48733330 表示 <math id="M80"><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.38666677 3.72533321 ， <math id="M81"><msub><mrow><mtext>(</mtext><mn mathvariant="normal">00</mn><mtext>⋯</mtext><mn mathvariant="normal">10</mn><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 16.25600052 4.48733330 表示 <math id="M82"><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 6.94266701 3.72533321 ， <math id="M83"><msub><mrow><mtext>(</mtext><mn mathvariant="normal">00</mn><mtext>⋯</mtext><mn mathvariant="normal">11</mn><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 16.08666611 4.48733330 表示 <math id="M84"><msub><mrow><mi>S</mi></mrow><mrow><mtext>(</mtext><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext> </mtext><mi>n</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 9.90599918 3.72533321 等。各阶谱系数的意义如下： <math id="M85"><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.38666677 3.72533321 称为0阶谱系数，它表示 <math id="M86"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 与常量的相关性（相似程度），若 <math id="M87"><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>=</mtext><mtext>+</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 15.07066631 4.06400013 （由于变换矩阵 <math id="M88"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.23333359 3.72533321 的正交性，其余的谱系数必均为0），表示 <math id="M89"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 为常量0；若 <math id="M90"><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>=</mtext><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 15.07066631 3.97933340 ，表示 <math id="M91"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 为常量1。事实上， <math id="M92"><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.38666677 3.72533321 表示函数 <math id="M93"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 中的常量0的个数与常量1的个数之差。 <math id="M94"><msub><mrow><mi>S</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 2.96333337 3.72533321 称为一阶谱系数，它表示 <math id="M95"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 与相应的变量 <math id="M96"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 2.79399991 3.72533321 的相关性，若 <math id="M97"><msub><mrow><mi>S</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mtext>+</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 14.64733315 4.06400013 ，则表示 <math id="M98"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 16.17133331 4.65666676 ；若 <math id="M99"><msub><mrow><mi>S</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 14.64733315 3.97933340 ，则表示 <math id="M100"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mover><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow><mo>¯</mo></mover></math> http://notExist.jpg http://notExist.jpg 16.67933464 4.31799984 ， <math id="M101"><mn mathvariant="normal">1</mn><mtext>≤</mtext><mi>i</mi><mtext>≤</mtext><mi>n</mi></math> http://notExist.jpg http://notExist.jpg 16.00200081 3.30199981 。其余的谱系数称为高阶谱系数，它们分别表示函数 <math id="M102"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 与相应的异或函数的相关性。例如 <math id="M103"><msub><mrow><mi>S</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.55599999 3.72533321 称为二阶谱系数， <math id="M104"><mi>i</mi><mtext>≠</mtext><mi>j</mi><mtext>,</mtext><mn mathvariant="normal">1</mn><mtext>≤</mtext><mi>i</mi><mtext>,</mtext><mi>j</mi><mtext>≤</mtext><mi>n</mi></math> http://notExist.jpg http://notExist.jpg 28.53266716 3.89466667 ，它们表示函数 <math id="M105"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 与相应的异或函数（ <math id="M106"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>⊕</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 9.48266697 4.40266657 ）的相关性。又如， <math id="M107"><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">12</mn><mtext>⋯</mtext><mi>n</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 7.36599970 3.72533321 称为 n 阶谱系数，它表示函数 <math id="M108"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 与异或函数（ <math id="M109"><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>⊕</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>⊕</mtext></math> http://notExist.jpg http://notExist.jpg 14.30866623 4.40266657 … <math id="M110"><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext>⊕</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 8.72066689 4.40266657 ）的相关性。 为了导出Walsh变换的并行算法，按照划分式（6），将列向量 <math id="M111"><mi mathvariant="bold-italic">F</mi></math> http://notExist.jpg http://notExist.jpg 2.62466669 2.79399991 重新排列为一个 <math id="M112"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>×</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 14.30866623 3.04799986 矩阵为 <math display="block" id="M113"><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><mfenced open="[" close="]" separators="|"><mrow><mtable><mtr><mtd><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></mrow></msub></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr><mtr><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd></mtr><mtr><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></mrow></msub></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr></mtable></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 64.34666443 23.19866753 令各子函数 <math id="M114"><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 43.68799973 5.24933338 的列向量分别为 <math display="block" id="M115"><mtable columnalign="left"><mtr><mtd><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>=</mtext><msup><mrow><mtext>[</mtext><mtable><mtr><mtd><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr></mtable><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup><mtext>,</mtext></mtd></mtr><mtr><mtd><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>=</mtext><msup><mrow><mtext>[</mtext><mtable><mtr><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></mrow></msub></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr></mtable><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup><mtext>,</mtext></mtd></mtr><mtr><mtd><mtext>⋮</mtext></mtd></mtr><mtr><mtd><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>=</mtext><msup><mrow><mtext>[</mtext><mtable><mtr><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></mrow></msub></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>+</mtext><mn mathvariant="normal">1</mn><mtext> </mtext></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>a</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd></mtr></mtable><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></mtd></mtr></mtable></math> http://notExist.jpg http://notExist.jpg 66.12466431 22.01333427 （17） 并令各个子函数 <math id="M116"><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 43.68799973 5.24933338 的Walsh谱系数列向量分别为 <math display="block" id="M117"><mi mathvariant="bold">S</mi><msub><mrow><mi mathvariant="bold">F</mi></mrow><mrow><mi>k</mi></mrow></msub><mtext>=</mtext></math> http://notExist.jpg http://notExist.jpg 10.15999985 3.72533321 <math display="block" id="M118"><mtext>[</mtext><mi mathvariant="normal">S</mi><msup><mrow><msub><mrow><mi mathvariant="normal">F</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msup><mtext>,</mtext><mi mathvariant="normal">S</mi><msup><mrow><msub><mrow><mi mathvariant="normal">F</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mi>n</mi></mrow></msup><mtext>,</mtext><mi mathvariant="normal">S</mi><msup><mrow><msub><mrow><mi mathvariant="normal">F</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msup><mtext>,</mtext><mi mathvariant="normal">S</mi><msup><mrow><msub><mrow><mi mathvariant="normal">F</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mtext>(</mtext><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext> </mtext><mi>n</mi></mrow></msup><mtext>,</mtext><mi mathvariant="normal">S</mi><msup><mrow><msub><mrow><mi mathvariant="normal">F</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">2</mn></mrow></msup><mtext>,</mtext><mtext>⋯</mtext></math> http://notExist.jpg http://notExist.jpg 62.90733337 4.65666676 , <math display="block" id="M119"><mi mathvariant="normal">S</mi><msup><mrow><msub><mrow><mi mathvariant="normal">F</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mtext>(</mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext> </mtext><mtext>(</mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">2</mn><mtext>)</mtext><mtext> </mtext><mtext>⋯</mtext><mi>n</mi></mrow></msup><msup><mrow><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 25.06133270 4.65666676 ， <math display="block" id="M120"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>k</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 26.75466537 3.89466667 （18）式中各子函数（ <math id="M121"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>k</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 26.75466537 3.89466667 ）的谱系数用上标表示。由Walsh变换的公式，得各子函数的Walsh变换式为 <math display="block" id="M122"><mi mathvariant="bold">S</mi><msub><mrow><mi mathvariant="bold">F</mi></mrow><mrow><mi>k</mi></mrow></msub><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msub><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 24.89200020 3.72533321 , <math display="block" id="M123"><mtext> </mtext><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>k</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext> </mtext></math> http://notExist.jpg http://notExist.jpg 28.19400024 3.89466667 或以矩阵形式表示为 <math display="block" id="M124"><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msub><mtext>⋅</mtext><mtext>[</mtext><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 28.87133217 4.65666676 其中子函数谱系数矩阵 <math id="M125"><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi></math> http://notExist.jpg http://notExist.jpg 4.65666676 2.79399991 为一个 <math id="M126"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup><mtext>×</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 14.30866623 3.04799986 矩阵，该矩阵的每一列对应一个子函数的谱系数列向量 <math id="M127"><mi mathvariant="bold">S</mi><msub><mrow><mi mathvariant="bold">F</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 5.67266655 3.72533321 。和（8）式相类比，利用Kronecker矩阵乘积的性质，将（14）式中第一式按照划分式（6）表示为 <math display="block" id="M128"><mi mathvariant="bold-italic">S</mi><mtext>=</mtext><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>⊗</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msub><mtext>)</mtext><mtext>⋅</mtext><mi mathvariant="bold-italic">F</mi></math> http://notExist.jpg http://notExist.jpg 32.59666443 4.74133348 并且按照划分式（6）将原函数 <math id="M129"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 的谱系数列向量 <math id="M130"><mi mathvariant="bold-italic">S</mi></math> http://notExist.jpg http://notExist.jpg 2.37066674 2.79399991 排列成一个 <math id="M131"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>×</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 14.30866623 3.04799986 矩阵为 <math display="block" id="M132"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><mfenced open="[" close="]" separators="|"><mrow><mtable><mtr><mtd><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi></mrow></msub></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mtext>(</mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>(</mtext><mtext> </mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">2</mn><mtext>)</mtext><mtext> </mtext><mtext>⋯</mtext><mi>n</mi></mrow></msub></mtd></mtr><mtr><mtd><msub><mrow><mi>S</mi></mrow><mrow><mi>r</mi></mrow></msub></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mi>r</mi><mtext> </mtext><mi>n</mi></mrow></msub></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mi>r</mi><mtext> </mtext><mtext>(</mtext><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mi>r</mi><mtext> </mtext><mtext>(</mtext><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>⋯</mtext><mtext> </mtext><mi>n</mi></mrow></msub></mtd></mtr><mtr><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd><mtd><mtext>⋮</mtext></mtd></mtr><mtr><mtd><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">1</mn><mtext> </mtext><mn mathvariant="normal">2</mn><mtext>⋯</mtext><mi>r</mi></mrow></msub></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">1</mn><mtext> </mtext><mn mathvariant="normal">2</mn><mtext>⋯</mtext><mi>r</mi><mtext> </mtext><mi>n</mi></mrow></msub></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">1</mn><mtext> </mtext><mn mathvariant="normal">2</mn><mtext>⋯</mtext><mi>r</mi><mtext> </mtext><mtext>(</mtext><mi>n</mi><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></mrow></msub></mtd><mtd><mtext>⋯</mtext></mtd><mtd><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">1</mn><mtext> </mtext><mn mathvariant="normal">2</mn><mtext> </mtext><mtext>⋯</mtext><mi>n</mi></mrow></msub></mtd></mtr></mtable></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 79.33266449 19.04999924 该矩阵的纵坐标和横坐标分别为 <math id="M133"><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>r</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 18.62666702 4.48733330 和 <math id="M134"><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mtext>+</mtext><mn mathvariant="normal">2</mn></mrow></msub><mtext>⋯</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 25.56933403 4.48733330 ，谱系数下标的编码方法如上所述。将（22）式用 <math id="M135"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.70933342 3.04799986 阶Hadamard逆矩阵 <math id="M136"><mtext>[</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msup><mtext>=</mtext><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>/</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>)</mtext><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 30.56466866 4.82599974 相乘，即将 <math id="M137"><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.72533321 的变量由谱域反变换到布尔域，作为子函数 <math id="M138"><msub><mrow><mi>f</mi></mrow><mrow><mi>k</mi></mrow></msub><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 9.22866726 4.65666676 所含原函数最小项的公因子 <math id="M139"><msub><mrow><mi>I</mi></mrow><mrow><mi>k</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 9.73666668 4.48733330 ， <math id="M140"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>k</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 26.75466537 3.89466667 ，剩余子函数谱系数矩阵的转置矩阵 <math id="M141"><msup><mrow><mtext>[</mtext><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 9.90599918 3.81000018 为 <math display="block" id="M142"><msup><mrow><mtext>[</mtext><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup><mtext>=</mtext><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>/</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>)</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 35.55999756 4.82599974 该转置矩阵 <math id="M143"><msup><mrow><mtext>[</mtext><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 9.90599918 3.81000018 的每一行对应一个子函数谱系数行向量，即 <math id="M144"><mtext>[</mtext><mi mathvariant="bold">S</mi><msub><mrow><mi mathvariant="bold">F</mi></mrow><mrow><mi>k</mi></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 10.24466705 4.65666676 ， <math id="M145"><mn mathvariant="normal">0</mn><mtext>≤</mtext><mi>k</mi><mtext>≤</mtext><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 26.75466537 3.89466667 。将（23）式两边左乘矩阵 <math id="M146"><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.97933340 3.72533321 ，则得 <math display="block" id="M147"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>⋅</mtext><msup><mrow><mtext>[</mtext><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 25.65399933 4.65666676 利用（20）式，则得 <math display="block" id="M148"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 30.98800087 3.72533321 利用Hadamard矩阵的性质，并利用（20）式及（23）式，即可推得 <math display="block" id="M149"><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>/</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>⋅</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 40.80933380 4.82599974 并且按照划分式（6）将原函数 <math id="M150"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 分解得到各个子函数 <math id="M151"><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>⋯</mtext><mtext>,</mtext><msub><mrow><mi>f</mi></mrow><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 43.68799973 5.24933338 的谱系数，可以利用（23）式由原函数 <math id="M152"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 的谱系数矩阵 <math id="M153"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 求得；利用（24）式，可以由各子函数的谱系数行向量构成的矩阵 <math id="M154"><msup><mrow><mtext>[</mtext><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 9.90599918 3.81000018 求得原函数 <math id="M155"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 的谱系数矩阵 <math id="M156"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 。（25）式和（26）式分别为Walsh变换并行算法公式和Walsh反变换并行算法公式，可以利用Hadamard矩阵直接计算得到,也可以利用快速Walsh变换算法实现。 1.4　Walsh变换的快速并行算法 2 求给定函数的Walsh谱系数的快速并行算法，可以由（20）式和（24）式，分别利用快速Walsh变换并行算法的迭代过程流图 [ 11 11 ] 通过两步计算实现。下面以一个简单的例子，说明该快速并行算法的一般步骤。 例1 求4变量布尔函数 <math id="M157"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext><mtext>=</mtext><mtext>∑</mtext><mtext>(</mtext><mn mathvariant="normal">0,1</mn><mtext>,</mtext><mn mathvariant="normal">2,4</mn><mtext>,</mtext></math> http://notExist.jpg http://notExist.jpg 34.88266754 4.74133348 <math id="M158"><mn mathvariant="normal">6,9</mn><mtext>,</mtext><mn mathvariant="normal">10,11,13</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 23.53733444 3.55599999 的Walsh谱系数。 计算步骤如下： 1） 取划分 <math id="M159"><mi mathvariant="bold-italic">X</mi><mtext>=</mtext><mtext>{</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>;</mtext><msub><mrow><mi mathvariant="bold-italic">B</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>}</mtext><mtext>=</mtext><mtext>{</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>;</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub><mtext>,</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">4</mn></mrow></msub><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 48.17533112 4.48733330 ， n =4， r =2。 2） 由函数 <math id="M160"><mi>f</mi><mtext>(</mtext><mi mathvariant="bold-italic">X</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.72066689 3.81000018 的函数值，按照上述划分排列成矩阵 <math id="M161"><msub><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.31799984 3.72533321 ，将矩阵 <math id="M162"><msub><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.31799984 3.72533321 的元素值 <math id="M163"><mn mathvariant="normal">0</mn><mtext>→</mtext><mn mathvariant="normal">1,1</mn><mtext>→</mtext><mtext>-</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 24.12999916 2.87866688 变换，得到谱域值矩阵 <math id="M164"><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.40266657 3.72533321 ，分别为 <math display="block" id="M165"><msub><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><mtable columnalign="right"><mtr><mtd><mtable columnalign="left"><mtr><mtd/></mtr><mtr><mtd/></mtr><mtr><mtd><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mtd></mtr><mtr><mtd><mn mathvariant="normal">00</mn><mtext> </mtext></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mn mathvariant="normal">01</mn><mtext> </mtext></mtd></mtr><mtr><mtd><mn mathvariant="normal">10</mn><mtext> </mtext></mtd></mtr><mtr><mtd><mn mathvariant="normal">11</mn><mtext> </mtext></mtd></mtr></mtable><mtable><mtr><mtd><mtable><mtr><mtd><mtable columnalign="left"><mtr><mtd><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">4</mn></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mtd></mtr><mtr><mtd><mn mathvariant="normal">00</mn><mtext> </mtext></mtd></mtr></mtable></mtd><mtd><mn mathvariant="normal">01</mn></mtd><mtd><mn mathvariant="normal">10</mn></mtd><mtd><mn mathvariant="normal">11</mn><mtext>    </mtext></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mfenced open="[" close="]" separators="|"><mrow><mtable columnalign="left"><mtr><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">0</mn></mtd></mtr><mtr><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">0</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">0</mn></mtd></mtr><mtr><mtd><mn mathvariant="normal">0</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd></mtr><mtr><mtd><mn mathvariant="normal">0</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">0</mn></mtd><mtd><mn mathvariant="normal">0</mn></mtd></mtr></mtable></mrow></mfenced></mtd></mtr></mtable><mover accent="false"><mo>→</mo><mrow/></mover></math> http://notExist.jpg http://notExist.jpg 52.06999969 25.39999962 <math display="block" id="M166"><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mfenced open="[" close="]" separators="|"><mrow><mtable columnalign="right"><mtr><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd></mtr><mtr><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd></mtr><mtr><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd></mtr><mtr><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mtext>-</mtext><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mn mathvariant="normal">1</mn></mtd></mtr></mtable></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 43.68799973 18.37266731 3） 计算 <math id="M167"><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>n</mi><mtext>-</mtext><mi>r</mi></mrow></msub><mtext>⋅</mtext><mtext>[</mtext><msub><mrow><mi mathvariant="bold-italic">F</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><msup><mrow><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 28.87133217 4.65666676 。其迭代过程流图如 图1 图1 所示。 图1 图1 中的连线表示对应的操作是将前行各元素与分别乘以“+1”（或“ <math id="M168"><mtext>-</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 1”）后的后行各元素相加形成新的（迭代后的）前行（或后行）。 4） 计算 <math id="M173"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub><mtext>=</mtext><msub><mrow><mi mathvariant="bold-italic">H</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>⋅</mtext><msup><mrow><mtext>[</mtext><mi mathvariant="bold">S</mi><mi mathvariant="bold">F</mi><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 25.65399933 4.65666676 。其迭代过程流图如 图2 图2 所示。 图2 图2 中， <math id="M174"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 的纵坐标和横坐标分别为 <math id="M175"><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>=</mtext><msub><mrow><mtext>(</mtext><mn mathvariant="normal">00,01,10,11</mn><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 41.74066544 4.48733330 和 <math id="M176"><mtext>(</mtext><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mn mathvariant="normal">4</mn></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>=</mtext><mtext>(</mtext><mn mathvariant="normal">00,01,10</mn></math> http://notExist.jpg http://notExist.jpg 32.93533325 4.48733330 ， <math id="M177"><msub><mrow><mn mathvariant="normal">11</mn><mtext>)</mtext></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 7.02733326 4.48733330 ，在矩阵 <math id="M178"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 中各元素的编码方法如上所述。 将矩阵 <math id="M183"><msub><mrow><mi mathvariant="bold-italic">S</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">e</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 进行矩阵的拉直运算，即得由（14）式第1式求得的谱系数列向量 <math display="block" id="M184"><mtable columnalign="left"><mtr><mtd><mi mathvariant="bold-italic">S</mi><mtext>=</mtext><mtext>[</mtext><mtext>-</mtext><mn mathvariant="normal">2</mn><mtext>,</mtext><mtext>-</mtext><mn mathvariant="normal">2</mn><mtext>,</mtext><mtext>-</mtext><mn mathvariant="normal">2,6</mn><mtext>,</mtext><mtext>-</mtext><mn mathvariant="normal">6,2</mn><mtext>,</mtext><mn mathvariant="normal">2,2</mn><mtext>,</mtext></mtd></mtr><mtr><mtd><msup><mrow><mtext>-</mtext><mn mathvariant="normal">2</mn><mtext>,</mtext><mtext>-</mtext><mn mathvariant="normal">10</mn><mtext>,</mtext><mtext>-</mtext><mn mathvariant="normal">2</mn><mtext>,</mtext><mtext>-</mtext><mn mathvariant="normal">2,2</mn><mtext>,</mtext><mn mathvariant="normal">2</mn><mtext>,</mtext><mtext>-</mtext><mn mathvariant="normal">6,2</mn><mtext>]</mtext></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup></mtd></mtr></mtable></math> http://notExist.jpg http://notExist.jpg 63.50000000 8.88999939 2　 算法的时间复杂度分析 1 2.1　Walsh变换算法的时间复杂度 2 设 N =2 n ， n 为变量个数（或问题的规模），计算 N = <math id="M185"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 点的Walsh谱系数，需做 <math id="M186"><msup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup></math> http://notExist.jpg http://notExist.jpg 4.31799984 3.13266659 次乘法， <math id="M187"><mi>N</mi><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 16.34066582 3.55599999 次加法，时间复杂度为 <math display="block" id="M188"><mi>Ο</mi><mtext>(</mtext><msup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mtext>+</mtext><mi>N</mi><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>)</mtext><mtext>=</mtext><mi>Ο</mi><mtext>(</mtext><mn mathvariant="normal">2</mn><mtext>⋅</mtext><msup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mtext>-</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 60.19799805 3.81000018 <math display="block" id="M189"><mtext>=</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 <math display="block" id="M190"><mi>Ο</mi><mtext>(</mtext><mn mathvariant="normal">2</mn><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>-</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext><mtext>≈</mtext><mi>Ο</mi><mtext>(</mtext><mn mathvariant="normal">2</mn><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 52.23933029 3.81000018 2.2 快速Walsh变换算法的时间复杂度 2 计算 N = <math id="M191"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 点的Walsh谱系数，需做 <math id="M192"><mi>N</mi><mtext> </mtext><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mi>N</mi></math> http://notExist.jpg http://notExist.jpg 12.78466702 4.57200003 次加、减法运算，时间复杂度为 <math display="block" id="M193"><mi>Ο</mi><mtext>(</mtext><mi>N</mi><mtext> </mtext><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext><mtext>=</mtext><mi>Ο</mi><mtext>(</mtext><mi>n</mi><mtext>⋅</mtext><mi>N</mi><mtext>)</mtext><mtext>=</mtext><mi>Ο</mi><mtext>(</mtext><mi>n</mi><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 56.21866608 4.91066647 2.3　Walsh变换并行算法的时间复杂度 2 设 r + q = n ， N 1 = <math id="M194"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.70933342 3.04799986 ， N 2 = <math id="M195"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 ，计算 N = <math id="M196"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 点的Walsh谱系数，需做 <math id="M197"><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msup><mrow><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msubsup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 26.83933258 4.65666676 次乘法， <math id="M198"><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 53.93266296 4.48733330 次加法。当 n 为偶数时，取 r = q = n /2，时间复杂度为 <math id="M199"><mi>Ο</mi><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msubsup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msubsup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>)</mtext><mtext>=</mtext><mi>Ο</mi><mtext>(</mtext><mn mathvariant="normal">4</mn><mtext>⋅</mtext><mroot><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">3</mn><mi>n</mi></mrow></msup></mrow><mrow/></mroot><mtext>-</mtext><mn mathvariant="normal">2</mn><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext><mtext>≈</mtext><mi>Ο</mi><mtext>(</mtext><mn mathvariant="normal">4</mn><mtext>⋅</mtext><mroot><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">3</mn><mi>n</mi></mrow></msup></mrow><mrow/></mroot><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 144.10266113 4.91066647 。当 n 为奇数时，取 r =（ n <math id="M200"><mtext>-</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 1）/2， q =（ n +1）/2，计算 N = <math id="M201"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 点的Walsh谱系数，时间复杂度为 <math display="block" id="M202"><mi>Ο</mi><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msubsup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msubsup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 47.58266830 4.65666676 <math display="block" id="M203"><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.11199999 3.55599999 <math display="block" id="M204"><mtext>+</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://notExist.jpg http://notExist.jpg 12.36133385 3.81000018 <math display="block" id="M205"><mtext>(</mtext><msub><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mtext>-</mtext><mn mathvariant="normal">1</mn><mtext>)</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 15.49400043 4.48733330 <math display="block" id="M206"><mtext>=</mtext><mi>Ο</mi><mtext>(</mtext><mn mathvariant="normal">3</mn><mroot><mrow><mn mathvariant="normal">2</mn></mrow><mrow/></mroot><mtext>⋅</mtext></math> http://notExist.jpg http://notExist.jpg 19.04999924 4.40266657 <math display="block" id="M207"><mroot><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">3</mn><mi>n</mi></mrow></msup></mrow><mrow/></mroot><mtext>-</mtext><mn mathvariant="normal">2</mn><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>)</mtext><mtext>≈</mtext></math> http://notExist.jpg http://notExist.jpg 26.24666595 4.65666676 <math display="block" id="M208"><mi>Ο</mi><mtext>(</mtext><mn mathvariant="normal">3</mn><mroot><mrow><mn mathvariant="normal">2</mn></mrow><mrow/></mroot><mtext>⋅</mtext><mroot><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">3</mn><mi>n</mi></mrow></msup></mrow><mrow/></mroot><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 25.06133270 4.65666676 2.4 Walsh变换的快速并行算法的时间复杂度 2 当 n 为偶数时，取 r=q=n /2，计算 N = <math id="M209"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 点的Walsh谱系数，需做 <math id="M210"><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mtext>+</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 31.15733337 4.91066647 次向量加、减法运算，时间复杂度为 <math display="block" id="M211"><mi>Ο</mi><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mtext>+</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 34.88266754 4.91066647 = <math display="block" id="M212"><mi>Ο</mi><mtext>(</mtext><mi>q</mi><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mtext>+</mtext><mi>r</mi><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 25.65399933 3.97933340 <math display="block" id="M213"><mtext>=</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 <math display="block" id="M214"><mi>Ο</mi><mtext>(</mtext><mi>n</mi><mtext>⋅</mtext><mroot><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></mrow><mrow/></mroot><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 17.94933319 4.65666676 当 n 为奇数时，取 r =（ n <math id="M215"><mtext>-</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 1）/2， q =（ n +1）/2，计算 N = <math id="M216"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></math> http://notExist.jpg http://notExist.jpg 2.87866688 3.04799986 点的Walsh谱系数，时间复杂度为 <math display="block" id="M217"><mi>Ο</mi><mtext>(</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mtext>+</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><msub><mrow><mi mathvariant="normal">g</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 34.54399872 4.91066647 <math display="block" id="M218"><mtext>=</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 2.79399991 <math display="block" id="M219"><mi>Ο</mi><mtext>(</mtext><mi>q</mi><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>q</mi></mrow></msup><mtext>+</mtext><mi>r</mi><mtext>⋅</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>r</mi></mrow></msup><mtext>)</mtext><mtext>=</mtext><mi>Ο</mi><mtext>(</mtext><mfrac><mrow><mn mathvariant="normal">3</mn><mi>n</mi><mtext>+</mtext><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">2</mn><mroot><mrow><mn mathvariant="normal">2</mn></mrow><mrow/></mroot></mrow></mfrac><mtext>⋅</mtext><mroot><mrow><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup></mrow><mrow/></mroot><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 58.41999817 8.88999939 已有Walsh变换算法与本文算法计算次数的比较，见 表1 表1 。 注： 标注*的算法是本文提出的 2 算法 2 n 10 20 Walsh变换 2×2 20 2×2 40 快速Walsh变换 10×2 10 20×2 20 Walsh变换并行 * 4×2 15 4×2 30 Walsh变换快速并行 * 10×2 5 20×2 10 algorithm and the exiting Walsh transformation algorithms 把变换的计算速度定义为每秒完成的计算次数，由 表1 表1 可以看出当变量个数 n =10时，本文导出的并行算法速度是Walsh变换算法速度的2 4 倍，当 n =20时，则为2 9 倍;当变量个数 n =10时，本文导出的并行快速算法速度是快速Walsh变换算法速度的2 5 倍，当变量个数 n =20时，则为2 10 倍。 3　 结 语 1 本文基于布尔函数的分解方法，导出了计算Walsh谱系数的一种并行计算方法及其快速并行算法。这两种算法降低了计算的时间复杂度，适用于高级语言编程计算,并且为Walsh变换的并行算法和并行快速算法的硬件实现提供了理论基础。 参考文献 PARK C S . Recursive algorithm for sliding Walsh Hadamard transform [J]. IEEE Transactions on Signal Processing , 2014 , 62 ( 11 ): 2827 - 2836 . DOI: 10.1109/TSP.2014.2316146 http://dx.doi.org/10.1109/TSP.2014.2316146 . Recursive algorithm for sliding Walsh Hadamard transform KARPOVSKY M G , STANKOVIC R S , ASTOLA J T . Spectral Techniques for Design and Testing of Computer Hardware [DB/OL].[ 2018-02-01 ]. http://www.bu.edu/reliable/publications/ http://www.bu.edu/reliable/publications/ . Spectral Techniques for Design and Testing of Computer Hardware MARTINA M , MASERA G . State metric compression techniques for Turbo decoder architectures [J]. IEEE Transactions on Circuits and Systems , 2011 , 58 ( 5 ): 1119 - 1128 . DOI: 10.1109/TCSI.2010.2090566 http://dx.doi.org/10.1109/TCSI.2010.2090566 . State metric compression techniques for Turbo decoder architectures PANG S Q , WANG J , WANG X N , et al . Application of orthogonal array and Walsh transform in resilient function [J]. Chinese Journal of Electronics , 2018 , 27 ( 2 ): 281 - 286 . DOI: 10.1049/cje.2017.09.011 http://dx.doi.org/10.1049/cje.2017.09.011 . Application of orthogonal array and Walsh transform in resilient function KARPOVSKY M G . Finite Orthogonal Series in the Design of Digital Devices [M]. New York : John Wiley , 1976 . Finite Orthogonal Series in the Design of Digital Devices WALSH J L . A closed set of orthogonal functions [J]. American Journal of Mathematics , 1923 , 45 : 5 - 24 . A closed set of orthogonal functions SHANKS J . Computation of the fast Walsh-Fourier transform [J]. IEEE Trans on Computers , 1969 , 18 ( 5 ): 457 - 459 . DOI: 10.1109/T-C.1969.222685 http://dx.doi.org/10.1109/T-C.1969.222685 . Computation of the fast Walsh-Fourier transform HURST S L . The Logical Processing of Digital Signals [M]. New York : Grame-Russak , 1978 . The Logical Processing of Digital Signals HURST S L , MILLER D M , MUZIO J C . Spectral Techniques in Digital Logic [M]. London : Academic Press Inc , 1985 . Spectral Techniques in Digital Logic MILLER D M . Spectral and Two-place Decomposition Techniques in Reversible Logic [DB/OL]. [ 2018-02-01 ]. https://ieeexplore.ieee.org/document/1186906/. DOI https://ieeexplore.ieee.org/document/1186906/. DOI :10.1109/MWSCAS.2002.1186906. Spectral and Two-place Decomposition Techniques in Reversible Logic 姜文彬 . 利用谱方法的多路选择器树形网络设计 [J]. 系统工程与电子技术 , 2001 , 23 ( 8 ): 92 - 97 . DOI: 1001-506X（2001）08-0092-06 http://dx.doi.org/1001-506X（2001）08-0092-06 . 利用谱方法的多路选择器树形网络设计 JIANG W B . Designing of multiplexer tree-type logic networks by spectral means [J]. Systems Engineering and Electronics , 2001 , 23 ( 8 ): 92 - 97 . DOI:1001-506X（2001）08-0092-06 (Ch) . Designing of multiplexer tree-type logic networks by spectral means 10.14188/j.1671-8836.2019.06.007 TP 33 A 1671-8836（2019）06-0576-05 JIANG Enhua.A Fast Parallel Algorithm of the Walsh Transform [J]. J. Wuhan Univ. （ Nat. Sci. Ed ）,2019,65(6):576-580. DOI:10.14188/j.1671-8836.2019.06.007(Ch). JIANG Enhua.A Fast Parallel Algorithm of the Walsh Transform [J].J. Wuhan Univ.（Nat. Sci. Ed）,2019,65(6):576-580. DOI:10.14188/j.1671-8836.2019.06.007(Ch). 姜恩华.Walsh变换的一种快速并行算法[J].武汉大学学报（理学版）,2019,65(6):576-580. DOI:10.14188/j.1671-8836.2019.06.001 姜恩华.Walsh变换的一种快速并行算法[J].武汉大学学报（理学版）,2019,65(6):576-580. DOI:10.14188/j.1671-8836.2019.06.001 国家自然科学基金资助项目(41275027， 11504121) 2018-03-02 2019-12-24 2020-05-21 武汉大学学报（理学版） 6 65