Walsh-Hadamard转换

在数位信号处理 ( Digital signal processing ) 大型集成电路算法的领域中， Walsh-Hadamard 转换是一种简单且重要的算法 (Algorithm) 之一，主要能针对频谱做快速的分析。

范例：

八点 Walsh-Hadamard 转换：

建构 Walsh-Hadamard 转换

Walsh-Hadamard 转换主要型式为 点的转换矩阵，其最小单位矩阵为 2x2 的 Walsh-Hadamard 矩阵，以下分别为二点、四点与如何产生 点的 Walsh-Hadamard 转换步骤。

■ 二点 Walsh-Hadamard 转换：

■ 四点 Walsh-Hadamard 转换：

■ 产生 点 Walsh-Hadamard 的步骤：

步骤一：

步骤二： 根据正负号次序 (Sign change) 将矩阵 (Matrix) 内的列向量座顺序上的重新排列。

范例

优缺点比较

优点：

■ 仅需实数运算 (Real operation) 。

■ 不需乘法运算 (No multiplication) ，仅有加减法运算。

■ 有部分性质类似于离散傅立叶转换 (Discrete fourier transform) 。

■ 顺向转换 (Forward transform) 与反向转换 (Inverse transform ) 型式为相似式的。

其中 与 分别都为行向量 (Column vector) 。

缺点：

■ 其收敛速度较离散余弦变换慢，因此对于频谱分析的效果较差。

■ 其加减法量较离散傅立叶转换、离散余弦变换多。

特性

■ 正交性

其表示 Walsh-Hadamard 转换矩阵中，不同的列向量 (Row verctor) 做内积 (Inner product) 为零。

■ 奇偶函数性质

可简单从 Walsh-Hadamard 转换矩阵中发现，其奇数列向量呈现左右两边偶对称(Even symmetric)。反之，其偶数列向量呈现左右两边奇对称(Odd symmetric)。

■ 线性关系

若

则

■ 逻辑相加性质

范例：

其运算方式为布林代数内的 XOR 逻辑门。

■ Special 函数

其中，

■ 平移性质

若

则

■ 调变性质

若

则

■ Parseval定理 (Parseval's Theorem)

若

若

则

■ 折积性质 (Convolution Property)

若

则

其中 代表逻辑折积 (Logical convolution)。

应用范围

其 Walsh-Hadamard 转换主要为一种非常适合应用于频域分析 (Spectrum analysis) ，去执行快速之分析。可惜的是对于折积性质是一种逻辑折积，与离散傅立叶变换上之折积性质截然不同。因此，较折积上无法取代离散傅立叶变换。

以下主要应用范围：

■ 带宽降低 (Bandwidth reduction) 。

■ CDMA (Code division multiple access)。

其主要是一种调变 (modulation) 与解调 (Demodultion) 之技术。

■ 资讯编码 (Information coding)。

■ 特征识别 (Feature extraction)。

■ 心电图分析 (ECG signal analysis in medical signal processing)。

■ Hadamard 频谱量测 (Hadamard spectrometer)。

■ 避免量化误差 (Avoiding quantization error)。

由于 Walsh-Hadamard 转换输入输出皆为整数，因此不会有量化误差的问题。

Jacket 转换

广义来说，其实 Walsh-Hadamard 转换是 Jacket 转换中的一项特例情况，其将 即可求得。

以下为四点的 Jacket 转换：

■ 点的 Jacket 转换：

参考文献

■ Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.

■ H. F. Harmuth,“Transmission of information by orthogonal functions,”1970.

■ Moon-Hu. Lee,“A new reverse Jacket transform and its fast algorithm,”IEEE Trans. Circuits Syst.-II, vol. 47, pp.39-46, 2000.