Main Content

离散沃尔什-哈达玛变换

简介

此示例通过展示以下两个应用情形来说明如何使用沃尔什-哈达玛变换 (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) 的正向和逆沃尔什变换对是

yn=1Ni=0N-1xiWAL(n,i),n=1,2,,N-1

xi=n=0N-1ynWAL(n,i),i=1,2,,N-1

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

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

y1 = fwht(walshMatrix)                % Fast Walsh-Hadamard transform
y1 = 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

subplot(2,1,1)
plot(x)
xlabel('Sample index')
ylabel('Amplitude')
title('ECG Signal')
subplot(2,1,2)
plot(abs(y))
xlabel('Sequency index')
ylabel('Magnitude')
title('WHT Coefficients')

从上图可以看出,大部分信号能量集中在较低的列率值上。出于研究目的,仅前 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,'r')
xlabel('Sample index')
ylabel('ECG signal amplitude')
legend('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')

通过将接收到的信号乘以使用 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

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

subplot(2,1,1)
plot(x1)
hold on
plot(xHat1)
legend('Original Message','Reconstructed Message','Location','Best')
xlabel('Sample index')
ylabel('Message signal amplitude')
subplot(2,1,2)
plot(x2)
hold on
plot(xHat2)
legend('Original Message','Reconstructed Message','Location','Best')
xlabel('Sample index')
ylabel('Message signal amplitude')

参考资料

  1. K.G. Beauchamp, Applications of Walsh and Related Functions - With an Introduction to Sequency Theory, Academic Press, 1984

  2. T. Beer, Walsh Transforms, American Journal of Physics, Vol. 49, Issue 5, May 1981

另请参阅

|