沃尔什转换

✍ dations ◷ 2025-08-02 14:27:46 #沃尔什转换

沃尔什转换（Walsh Transform）是在频谱分析上作为离散傅立叶变换的替代方案的一种方法。

在频谱分析上最常用的一种方法是使用离散傅立叶变换，然而，即使已经有许多快速的算法来实现离散傅立叶变换，仍然具有一些实现上的缺点，举例来说，在离散傅立叶变换中，资料向量必须乘上复数系数的矩阵加以处理，而且每个复数系数的实部和虚部是一个正弦及余弦函数，因此大部分的系数都是浮点数，也就是说在做离散傅立叶变换处理的时候，我们必须做复数而且是浮点数的运算，因此计算量会比较大，而且浮点数运算产生的误差会比较大。

而在沃尔什转换中，资料向量需要乘上的矩阵是一个实数的矩阵，而且这些矩阵的系数是1或是–1，因此所有的系数都是绝对值大小相同的整数，这使得我们不需要作浮点数的乘法运算，更进一步，只需要使用加法来实现沃尔什转换，这使的沃尔什转换在运算复杂度上远小于离散傅立叶变换。

使用离散傅立叶变换相当于把信号拆解成在不同频率的正弦函数与余弦函数的分量，而使用沃尔什转换相当于把信号拆解成在许多不同震荡频率的方波上，因此，除非所要分析的信号拥有类似方波组合的特性，使用沃尔什转换作频谱分析的效果会比使用离散傅立叶变换分析的效果要差，这是降低运算复杂度所要付出的代价。

沃尔什转换的转换式为

${displaystyle F=sum _{n=0}^{N-1}fW}$ ${displaystyle F=sum _{n=0}^{N-1}fW}$

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

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

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

${displaystyle f={frac {1}{N}}sum _{n=0}^{N-1}FW}$ ${displaystyle f={frac {1}{N}}sum _{n=0}^{N-1}FW}$

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）正交性质

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

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

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

（3）奇偶性质

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

（4）线性性质

若 ${displaystyle fRightarrow F}$ ${displaystyle fRightarrow F}$ ， ${displaystyle gRightarrow G}$ ${displaystyle gRightarrow G}$ ，（ ${displaystyle Rightarrow }$ $Rightarrow$ 表沃尔什转换）则有 ${displaystyle af+bgRightarrow aF+bg}$ ${displaystyle af+bgRightarrow aF+bg}$ 。

（5）加法性质

${displaystyle WW=W}$ ${displaystyle WW=W}$ ， ${displaystyle oplus }$ $oplus$ 表示逻辑互斥或（exclusive or）

（6）平移性质

若 ${displaystyle fRightarrow F}$ ${displaystyle fRightarrow F}$ 则 ${displaystyle fRightarrow WF}$ ${displaystyle fRightarrow WF}$

（7）调变性质

若 ${displaystyle fRightarrow F}$ ${displaystyle fRightarrow F}$ 则 ${displaystyle WfRightarrow F}$ ${displaystyle WfRightarrow F}$

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

若 ${displaystyle fRightarrow F}$ ${displaystyle fRightarrow F}$ 则 ${displaystyle sum _{n=0}^{N-1}|f|^{2}={frac {1}{N}}sum _{n=0}^{N-1}|F|^{2}}$ ${displaystyle sum _{n=0}^{N-1}|f|^{2}={frac {1}{N}}sum _{n=0}^{N-1}|F|^{2}}$

（9）折积性质

若 ${displaystyle fRightarrow F}$ ${displaystyle fRightarrow F}$ ， ${displaystyle gRightarrow G}$ ${displaystyle gRightarrow G}$ ，则 ${displaystyle sum _{l=0}^{N-1}fg=sum _{l=0}^{N-1}gfRightarrow FG}$ ${displaystyle sum _{l=0}^{N-1}fg=sum _{l=0}^{N-1}gfRightarrow FG}$ ，在这里 ${displaystyle sum _{l=0}^{N-1}fg=sum _{l=0}^{N-1}gf}$ ${displaystyle sum _{l=0}^{N-1}fg=sum _{l=0}^{N-1}gf}$ 代表逻辑折积（logical convolution）。

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

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

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

证明:

${displaystyle textstyle sum _{n=0}^{N-1}displaystyle fg}$ ${displaystyle textstyle sum _{n=0}^{N-1}displaystyle fg}$

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

${displaystyle h=f*g=textstyle sum _{n=0}^{N-1}displaystyle fg=textstyle sum _{n=0}^{N-1}displaystyle fg}$ ${displaystyle h=f*g=textstyle sum _{n=0}^{N-1}displaystyle fg=textstyle sum _{n=0}^{N-1}displaystyle fg}$

* 代表 "Logic convolution"

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

${displaystyle {begin{array}{lcr}3&011\oplus 7&111end{array}}}$

相关

卡罗莱纳文加罗林语是一种南岛语言，起源于加罗林群岛，但主要为北马里亚纳群岛居民所使用。加罗林人将该语言与英语一起作为常用语言。世界上约有3,100名母语人士。
查特胡奇县查塔胡其县 (Chattahoochee County, Georgia)是美国乔治亚州西部的一个县级行政单位，西邻阿拉巴马州。面积651平方公里。根据美国2000年人口普查估计，共有人口14,882人。2005
联合国纪念墓园联合国军：来源：联合国纪念墓园（韩语：재한유엔기념공원，英语：United Nations Memorial Cemetery in Korea，缩写为UNMCK）座落于韩国釜山广域市南区，埋葬联合国军在韩战中的阵亡士兵。
断线脂鲤断线脂鲤（拉丁语学名：）是辐鳍鱼纲脂鲤目脂鲤亚目鲑脂鲤科断线脂鲤属中的一个种。它们生活在刚果河流域，尤其是在雨林河流中。它们可以达到12厘米长。性成熟的雄鱼尾鳍中间延长。
徒然草《徒然草》（日语：徒然草／つれづれぐさ），吉田兼好法师著，日本中世文学随笔体的代表作之一，跟清少纳言著作的《枕草子》和鸭长明著作的《方丈记》同被誉为日本三大随笔之一。一般认
林赖三郎林赖三郎（日语：はやしらいざぶろう，1878年9月6日－1958年5月7日），原名三轮赖三郎，为日本刑法学者、政治家、教育家，曾任检事总长、大审院院长以及司法大臣。荣誉为正二位勲一等法学
万德·阿比姆博拉万德·阿比姆博拉，（约鲁巴语：Wándé Abímbọ́lá，1932年6月26日－），尼日利亚学者，约鲁巴语言文学教授伊费大学（现在的奥巴费米·阿沃洛沃大学）原副校长，还曾担任尼日利亚联邦共和国参议院多数党领袖。生于尼日利亚奥约，1963年阿比姆博拉于伊巴丹大学学院获历史学学位。1966年获西北大学语言学硕士学位，1971年获拉各斯大学约鲁巴文学博士学位。1976年成为全职教授。他的学术背景植根于口头传统，在受到正规教育之前，他是伊法诵经和口头艺术的学徒。他还为一些美国大学，如印第安纳大学、阿默斯特
卡尔洛瓦茨县卡尔罗巴丘卡县（Karlovačka županija）是克罗地亚中部的一个县，西北邻斯洛文尼亚，东南邻波黑。面积3,622平方公里，2001年人口141,787，2011年人口128,899。首府卡尔洛瓦茨。下分五市、十七镇。县议会有44席。
廷·耶德瓦伊廷·耶德瓦伊（克罗地亚语：Tin Jedvaj；1995年11月28日－）是一位克罗地亚足球运动员。在场上的位置是后卫。现效力于俄超球队莫斯科火车头。他也代表克罗地亚国家足球队参赛。
马尔科·阿塞尔马尔科·阿塞尔（芬兰语：Marko Asell，1970年5月8日－），芬兰男子摔跤运动员。他曾代表芬兰参加1996年和2000年夏季奥林匹克运动会摔跤比赛，其中1996年奥运会获得一枚银牌。