이산 월시-아다마르 변환(Discrete Walsh-Hadamard Transform)

소개

이 예제에서는 스펙트럼 확산을 사용하는 통신과 심전도 신호 처리의 두 가지 응용 사례를 통해 월시-아다마르 변환(WHT)과 그 속성을 사용하는 방법을 보여줍니다.

WHT는 파워 스펙트럼 분석은 물론, 필터링, 음성 신호와 의료 신호 처리, 통신에서의 다중화 및 코딩, 비선형 신호 특성화, 비선형 미분 방정식 풀이, 논리적 설계와 분석 같은 다양한 응용 분야에서 활용됩니다.

WHT는 신호를 월시 함수(Walsh function)라고 하는 일련의 직교하는 사각 파형으로 분해하는 준최적(Suboptimal) 비정현파 직교 변환입니다. 월시(또는 아다마르) 함수의 진폭이 두 값 +1 또는 -1뿐이므로 이 변환은 실수이며 승수가 없습니다.

월시(또는 아다마르) 함수

월시 함수는 진폭이 -1 또는 +1 값인 직사각 파형이거나 정사각 파형입니다. 월시 함수의 중요한 특성은 단위 시간 간격당 영점교차 개수에 따라 결정되는 시퀀시(Sequency)입니다. 각 월시 함수마다 고유한 시퀀시 값이 있습니다.

월시 함수는 다양한 방법으로 생성할 수 있습니다([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

이산 월시-아다마르 변환(Discrete Walsh-Hadamard Transform)

길이가 N인 신호 x(t)에 대한 월시 정변환과 역변환 쌍은 다음과 같습니다.

복잡도 $\mathit{O}\left(\mathit{N}\log \mathit{N}\right)$의 월시-아다마르 변환을 구현할 수 있도록 쿨리-튜키(Cooley-Tukey) 알고리즘과 유사한 고속 알고리즘이 개발되었습니다([1]과 [2] 참조). 월시 행렬은 대칭 행렬이므로, 스케일링 인자가 1/N인 경우를 제외하고 순방향 변환 연산과 역방향 변환 연산이 동일합니다. 함수 fwht와 ifwht는 각각 순방향 WHT와 역방향 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는 각 시퀀시 인덱스의 가중치에 해당하는 0이 아닌 값을 반환합니다. 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가 가역 변환이기 때문에, 역변환을 사용하여 원래 신호를 완벽하게 복원할 수 있습니다. 원래 신호와, 역변환으로 얻는 신호 사이의 노름은 0이며, 이는 완벽한 복원을 의미합니다.

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

ans = 0

월시-아다마르 변환은 일련의 사각 파형을 사용한 확장을 포함하므로 월시 함수로 쉽게 표현될 수 있는 불연속 신호를 사용하는 응용 분야에 유용합니다. 다음은 월시-아다마르 변환의 두 응용 사례입니다.

월시 변환 응용 사례

심전도 신호 처리 환자의 심전도(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개 계수와 심전도 신호 길이만 저장했습니다. 이는 약 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의 가산성 백색 가우스 잡음(AWGN)에 의해 손상됩니다.

수신기(기지국)에서의 신호 처리가 일관되지 않으므로, 길이 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부터 시작하기 때문에, 시퀀시 60과 10의 월시-아다마르 코드는 아다마르 행렬의 열(또는 행) 61과 11을 선택해 가져온 것입니다.

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')

참고 문헌