沃尔什转换

✍ dations ◷ 2025-09-09 10:05: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}}}$

相关

557年
米奇老鼠米奇（俗称：米老鼠；英语：Mickey Mouse），引进时译米奇老鼠，是一个于1928年由华特·迪士尼和乌布·伊沃克斯于华特迪士尼工作室创作的迪士尼角色。米奇是一只拟人化的黑色大耳老鼠，且通
商业智能商业智能（Business Intelligence, BI），又称商业智能或商务智能，指用现代数据仓库技术、在线分析处理技术、数据挖掘和数据展现技术进行数据分析以实现商业价值。商业智能的概念
贝特朗-弗朗索瓦·马埃·德·拉布尔多内贝特朗-弗朗索瓦·马埃·德·拉布尔多内（Bertrand-François Mahé de La Bourdonnais），1699年2月11日生于法国圣马洛，1753年11月10日殁于巴黎，是一位法国海军军官和地方长官，服役
六三罢工1919年6月3日，北京军阀政府大规模逮捕爱国学生引起了上海等各地工人的爱国大罢工。1919年5月4日由北京学生发起，迅速发展到全国各地的五四爱国运动是一次空前伟大的反帝反封建
王承嫣王承嫣（英语：Lilu Wang，1989年11月7日－），艺名小蛮（Hsiao Man），是台湾女演员、女歌手和节目主持人。于2005年参加电视节目《我爱黑涩会》后被选中加入台湾女子组合黑Girl（前称黑涩会美
克劳伯格锡芬河坐标：51°02′30″N 7°09′28″E / 51.041683°N 7.157700°E / 51.041683; 7.157700克劳伯格锡芬河（德语：Klaubergsiefen），是德国的河流，位于该国西部，处于北莱茵-威斯特法伦州，属
萨穆·卡斯蒂列霍萨穆·卡斯蒂列霍（西班牙语：Samu Castillejo；1995年1月18日－）是一位西班牙足球运动员。在场上的位置是右边锋。他曾效力于西甲球队马拉加，现效力于西甲球队瓦伦西亚。他也代表西班牙国家青年足球队参赛。
癫痫日癫痫日或紫日（英语：Purple Day）是一场旨在提升公众对癫痫的了解的活动。从2008年开始，人们被鼓励在3月26日穿紫色服装。紫色和薰衣草色常常与癫痫相联系，所以比如说在这天可以戴条紫丝带。来自加拿大新斯科舍省的卡西迪·梅根受她自己与癫痫斗争的刺激，在2008年提出了癫痫日的想法。卡西迪的目标是让人们在谈论癫痫的过程中努力消除误解，并告诉患者们他们并不孤单。新斯科舍省癫痫协会（Epilepsy Association of Nova Scotia, EANS）在2008年加入这项活动以帮助发展Cas
艾惟诺艾惟诺（英语：Aveeno）是美国强生公司旗下的护肤品牌。1945年由Sidney与Albert Musher两兄弟创建。1999年被美国强生公司收购。2000年开始生产各个系列的婴儿用品。