离散沃尔什-哈达玛变换

R2026b

打开实时脚本

简介

此示例通过展示以下两个应用情形来说明如何使用沃尔什-哈达玛变换 (WHT) 及其部分属性：使用扩频的通信和 ECG 信号的处理。

WHT 适用于许多不同的应用情形，例如功率谱分析、滤波、处理语音和医疗信号、通信中的多路复用和编码、表征非线性信号、求解非线性微分方程以及逻辑设计和分析。

WHT 是一种次优非正弦正交变换，它将一个信号分解成一组称为沃尔什函数的正交矩形波形。该变换没有乘数并且是实数变换，因为沃尔什（或哈达玛）函数的振幅只有两个值，即 +1 或 -1。

沃尔什（或哈达玛）函数

沃尔什函数是值为 -1 或 +1 的矩形或方形波形。沃尔什函数的一个重要特征是列率，列率由每单位时间间隔的过零次数确定。每个沃尔什函数都有唯一的列率值。

可以通过多种方式生成沃尔什函数（请参阅 [1]）。此处我们使用 MATLAB® 中的 hadamard 函数来生成沃尔什函数。长度为 8 的沃尔什函数的生成结果如下。

N = 8;  % Length of Walsh (Hadamard) functions
hadamardMatrix = hadamard(N)

hadamardMatrix = 8×8

     1     1     1     1     1     1     1     1
     1    -1     1    -1     1    -1     1    -1
     1     1    -1    -1     1     1    -1    -1
     1    -1    -1     1     1    -1    -1     1
     1     1     1     1    -1    -1    -1    -1
     1    -1     1    -1    -1     1    -1     1
     1     1    -1    -1    -1    -1     1     1
     1    -1    -1     1    -1     1     1    -1

对称 hadamardMatrix 的行（或列）包含沃尔什函数。矩阵中的沃尔什函数不是按照其列率或过零次数的升序（即“列率顺序”）排列的，而是按照“哈达玛顺序”排列的。沃尔什矩阵在行或列上包含按列率顺序递增的沃尔什函数，该矩阵通过更改 hadamardMatrix 的索引获得，如下所示。

HadIdx = 0:N-1;                          % Hadamard index
M = log2(N)+1;                           % Number of bits to represent the index

列率索引（二进制格式）的每列均由位反转哈达玛索引（二进制格式）的列的模 2 加法给出。

binHadIdx = fliplr(dec2bin(HadIdx,M))-'0'; % Bit reversing of the binary index
binSeqIdx = zeros(N,M-1);                  % Pre-allocate memory
for k = M:-1:2
    % Binary sequency index 
    binSeqIdx(:,k) = xor(binHadIdx(:,k),binHadIdx(:,k-1));
end
SeqIdx = binSeqIdx*pow2((M-1:-1:0)');    % Binary to integer sequency index
walshMatrix = hadamardMatrix(SeqIdx+1,:) % 1-based indexing

walshMatrix = 8×8

     1     1     1     1     1     1     1     1
     1     1     1     1    -1    -1    -1    -1
     1     1    -1    -1    -1    -1     1     1
     1     1    -1    -1     1     1    -1    -1
     1    -1    -1     1     1    -1    -1     1
     1    -1    -1     1    -1     1     1    -1
     1    -1     1    -1    -1     1    -1     1
     1    -1     1    -1     1    -1     1    -1

离散沃尔什-哈达玛变换

长度为 N 的信号 x(t) 的正向和逆沃尔什变换对是

$y_{n} = \frac{1}{N} \sum_{i = 0}^{N - 1} x_{i} W A L (n, i), n = 1, 2, \dots, N - 1$

$x_{i} = \sum_{n = 0}^{N - 1} y_{n} W A L (n, i), i = 1, 2, \dots, N - 1$

已开发类似于库利-图基算法的快速算法来实现复杂度为 $O (N \log N)$ 的沃尔什-哈达玛变换（请参阅 [1] 和 [2]）。由于沃尔什矩阵是对称矩阵，因此正向和逆变换为相同的运算，除了缩放因子为 1/N。函数 fwht 和 ifwht 分别实现正向和逆 WHT。

示例 1 对沃尔什矩阵执行 WHT。预期结果是单位矩阵，因为对称沃尔什矩阵的行（或列）包含沃尔什函数。

whtWalshMatrix = fwht(walshMatrix)                % Fast Walsh-Hadamard transform

whtWalshMatrix = 8×8

     1     0     0     0     0     0     0     0
     0     1     0     0     0     0     0     0
     0     0     1     0     0     0     0     0
     0     0     0     1     0     0     0     0
     0     0     0     0     1     0     0     0
     0     0     0     0     0     1     0     0
     0     0     0     0     0     0     1     0
     0     0     0     0     0     0     0     1

示例 2 通过缩放和添加哈达玛矩阵的任意列来构造不连续信号。此信号是使用加权沃尔什函数形成的，因此 WHT 应返回非零值，这些值等于对应列率索引处的权重。在计算 WHT 时，ordering 指定为 "hadamard"，因为哈达玛矩阵（而不是沃尔什矩阵）用于获得沃尔什函数。

N = 8;
H = hadamard(N);                      % Hadamard matrix
% Construct a signal by adding a few weighted Walsh functions
x = 8.*H(1,:) + 12.*H(3,:) + 18.*H(5,:) + 10.*H(8,:);           
y = fwht(x,N,"hadamard")

y = 1×8

     8     0    12     0    18     0     0    10

WHT 是一种可逆变换，使用逆变换可以完美地恢复原始信号。原始信号和通过逆变换得到的信号之间的范数等于零，表明重构是完美的。

xHat = ifwht(y,N,"hadamard");
norm(x-xHat)

ans = 
0

沃尔什-哈达玛变换涉及使用一组矩形波形的扩展，因此它可用于涉及不连续信号的应用情形，这些不连续信号可以用沃尔什函数来轻松表示。下面是沃尔什-哈达玛变换的两种应用情形。

沃尔什变换应用情形

ECG 信号处理通常，我们需要记录患者在不同时刻的心电图 (ECG) 信号。这会产生大量数据，需要存储这些数据以供稍后进行分析、比较等。沃尔什-哈达玛变换适合 ECG 信号的压缩，因为它可提供诸多优点，例如快速计算沃尔什-哈达玛系数、所需存储空间更少（因为它仅存储那些具有大幅值的列率系数就足够了）和快速信号重构。

一个 ECG 信号及其对应的沃尔什-哈达玛变换的计算如下所示。

x1 = ecg(512);                    % Single ecg wave
x = repmat(x1,1,8);                 
x = x + 0.1.*randn(1,length(x));  % Noisy ecg signal
y = fwht(x);                      % Fast Walsh-Hadamard transform

tiledlayout("flow")
nexttile
plot(x)
xlabel("Sample index")
ylabel("Amplitude")
title("ECG Signal")
nexttile
plot(abs(y))
xlabel("Sequency index")
ylabel("Magnitude")
title("WHT Coefficients")

Figure contains 2 axes objects. Axes object 1 with title ECG Signal, xlabel Sample index, ylabel Amplitude contains an object of type line. Axes object 2 with title WHT Coefficients, xlabel Sequency index, ylabel Magnitude contains an object of type line.

从上图可以看出，大部分信号能量集中在较低的列率值上。出于研究目的，仅前 1024 个系数被存储并用于重构原始信号。截断较高的列率系数也有助于噪声抑制。原始信号和重新生成的信号如下所示。

y(1025:length(x)) = 0;            % Zeroing out the higher coefficients    
xHat = ifwht(y);                  % Signal reconstruction using inverse WHT  

figure
plot(x)
hold on
plot(xHat)
xlabel("Sample index")
ylabel("ECG signal amplitude")
legend(["Original Signal" "Reconstructed Signal"])

Figure contains an axes object. The axes object with xlabel Sample index, ylabel ECG signal amplitude contains 2 objects of type line. These objects represent Original Signal, Reconstructed Signal.

重新生成的信号非常接近原始信号。

为了重构原始信号，我们只存储前 1024 个系数和 ECG 信号长度。这表示压缩比约为 4:1。

req = [length(x) y(1:1024)];   
whos x req

  Name      Size              Bytes  Class     Attributes

  req       1x1025             8200  double              
  x         1x4096            32768  double

使用扩频的通信基于扩频的通信技术（如 CDMA）使用沃尔什码（从沃尔什函数派生）来扩展消息信号，并使用 WHT 变换来解扩消息信号。由于沃尔什码是正交的，任何沃尔什码信号对终端来说均为随机噪声，除非该终端使用相同的代码进行编码。下面我们演示扩展、确定用于扩展的沃尔什码并解扩以恢复消息信号的过程。

两个 CDMA 终端使用长度为 64 的两个不同的沃尔什码（也称为哈达玛码）来扩展各自的消息信号。扩展消息信号被方差为 0.1 的加性高斯白噪声破坏。

在接收机（基站）处，信号处理是非连贯的，并且接收到的长度为 N 的序列需要与 2^N 个沃尔什码字相关联，以提取各个发射机使用的沃尔什码。这可以通过使用快速沃尔什-哈达玛变换将接收的信号变换到列率域来高效完成。使用出现峰值的列率位置，可以确定使用的对应沃尔什-哈达玛码（或沃尔什函数）。下图显示在第一个和第二个发射机中分别使用列率（具有 ordering = "hadamard"）为 60 和 10 的沃尔什-哈达玛码。

load mess_rcvd_signals.mat
N = length(rcvdSig1);
y1 = fwht(rcvdSig1,N,"hadamard");
y2 = fwht(rcvdSig2,N,"hadamard");
figure
plot(0:63,y1,0:63,y2)
xlabel("Sequency index")
ylabel("WHT of the Received Signals")
title("Walsh-Hadamard Code Extraction")
legend(["WHT of Tx - 1 signal" "WHT of Tx - 2 signal"])

Figure contains an axes object. The axes object with title Walsh-Hadamard Code Extraction, xlabel Sequency index, ylabel WHT of the Received Signals contains 2 objects of type line. These objects represent WHT of Tx - 1 signal, WHT of Tx - 2 signal.

通过将接收到的信号乘以使用 hadamard 函数生成的对应沃尔什-哈达玛码，可以直接执行解扩（或解码）以提取消息信号。（注意，MATLAB® 中的索引从 1 开始，因此通过选择哈达玛矩阵中的列（或行）61 和 11 来获得具有列率 60 和 10 的沃尔什-哈达玛码。）

N = 64; 
hadamardMatrix = hadamard(N);
codeTx1 = hadamardMatrix(:,61);         % Code used by transmitter 1  
codeTx2 = hadamardMatrix(:,11);         % Code used by transmitter 2

用于恢复原始消息信号的解码运算是

xHat1 = codeTx1 .* rcvdSig1;            % Decoded signal at receiver 1
xHat2 = codeTx2 .* rcvdSig2;            % Decoded signal at receiver 2

接收机端的恢复消息信号如下所示，并与原始信号叠加以供比较。

tiledlayout("flow")
nexttile
plot(x1)
hold on
plot(xHat1)
legend(["Original Message" "Reconstructed Message"],Location="best")
xlabel("Sample index")
ylabel("Message signal amplitude")
nexttile
plot(x2)
hold on
plot(xHat2)
legend(["Original Message" "Reconstructed Message"],Location="best")
xlabel("Sample index")
ylabel("Message signal amplitude")

Figure contains 2 axes objects. Axes object 1 with xlabel Sample index, ylabel Message signal amplitude contains 2 objects of type line. These objects represent Original Message, Reconstructed Message. Axes object 2 with xlabel Sample index, ylabel Message signal amplitude contains 2 objects of type line. These objects represent Original Message, Reconstructed Message.

参考资料

K.G. Beauchamp, Applications of Walsh and Related Functions - With an Introduction to Sequency Theory, Academic Press, 1984
T. Beer, Walsh Transforms, American Journal of Physics, Vol. 49, Issue 5, May 1981

另请参阅

fwht | ifwht