Дискретное преобразование Уолша-Адамара

Введение

Этот пример показывает, как использовать Преобразование Уолша-Адамара (WHT) и некоторые его свойства путем демонстрирования двух приложений: коммуникации с помощью спектра распространения и обрабатывая сигналов ECG.

WHTs используются во многих различных приложениях, таких как анализ спектра мощности, фильтрация, обработка речи и медицинских сигналов, мультиплексирования и кодирования в коммуникациях, характеризуя нелинейные сигналы, решая нелинейные дифференциальные уравнения, и логическую структуру и анализ.

WHT является субоптимальным, несинусоидальным, ортогональным преобразованием, которое разлагается, сигнал в набор ортогональных, прямоугольных форм волны вызвал функции Уолша. Преобразование не имеет никаких множителей и действительно, потому что амплитуда Уолша (или Адамар) функции имеет только два значения, +1 или-1.

Уолш (или Адамар) функции

Функции Уолша являются прямоугольными или квадратными формами волны со значениями-1 или +1. Важная характеристика функций Уолша является sequency, который определяется от количества нулевых пересечений на интервал единицы времени. Каждая функция Уолша имеет уникальное sequency значение.

Функции Уолша могут быть сгенерированы во многих отношениях (см. [1]). Здесь мы используем функцию hadamard в MATLAB®, чтобы сгенерировать функции Уолша. Длина восемь функций Уолша сгенерирована можно следующим образом.

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 содержат функции Уолша. Функции Уолша в матрице не располагаются в увеличивающемся порядке их sequencies или количестве нулевых пересечений (т.е. 'sequency порядок'), но располагаются в 'Порядке Адамара'. Матрица Уолша, которая содержит функции Уолша вдоль строк или столбцов в увеличивающемся порядке их sequencies, получена путем изменения индекса hadamardMatrix можно следующим образом.

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

Каждый столбец индекса sequency (в двоичном формате) дан 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

Дискретное преобразование Уолша-Адамара

Прямая и обратная пара Преобразования Уолша для сигнала x (t) длины N

$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$

Алгоритмы FAST, подобные алгоритму Cooley-Tukey, были разработаны, чтобы реализовать Преобразование Уолша-Адамара со сложностью O (NlogN) (см. [1] и [2]). Поскольку матрица Уолша симметрична, и прямые и обратные преобразования являются идентичными операциями за исключением масштабного коэффициента 1/N. Функции fwht и ifwht реализуют форварда и обратный 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 должен возвратить ненулевые значения, равные весам в соответствующих sequency индексах. При оценке WHT ordering задан как 'Адамар', потому что матрица Адамара (вместо матрицы Уолша) используется, чтобы получить функции Уолша.

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, потому что это предлагает преимущества, такие как быстрое вычисление коэффициентов Адамара Уолша, менее необходимое пространство памяти, поскольку это достаточно, чтобы сохранить только те sequency коэффициенты большими значениями и быструю реконструкцию сигнала.

Сигнал 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
figure
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')

Как видно в вышеупомянутом графике, большая часть энергии сигнала сконцентрирована в ниже sequency значения. В целях расследования только первые 1 024 коэффициента хранятся и используемый, чтобы восстановить исходный сигнал. Усечение выше sequency коэффициенты также помогает с подавлением шумов. Оригинал и воспроизведенные сигналы показывают ниже.

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

Воспроизведенный сигнал очень близко к исходному сигналу.

Чтобы восстановить исходный сигнал, мы сохранили только первые 1 024 коэффициента и длину сигнала 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, преобразовывает к despread их. Поскольку коды Уолша являются ортогональными, любой закодированный Уолшом сигнал появляется как случайный шум к терминалу, если тот терминал не использует тот же код для кодирования. Ниже мы показываем процесс распространения, определяя коды Уолша, используемые для распространения и despreading, чтобы восстановить сигнал сообщения.

Два терминала CDMA распространяют свои соответствующие сигналы сообщения с помощью двух различных кодов Уолша (также известный как коды Адамара) длины 64. Сигналы сообщения распространения повреждаются аддитивным белым Гауссовым шумом отклонения 0.1.

В получателе (базовая станция) обработка сигналов является некогерентной, и полученная последовательность длины N должен коррелироваться с 2^N кодовые комбинации Уолша, чтобы извлечь коды Уолша, используемые соответствующими передатчиками. Это может быть эффективно сделано путем преобразования полученных сигналов к sequency области с помощью быстрого Преобразования Уолша-Адамара. Используя sequency местоположение в, который происходит пик, может быть определен соответствующий код Адамара Уолша (или функция Уолша) используемый. График ниже показов, что коды Адамара Уолша с sequency (с ordering = 'Адамар') 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,'r')
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')

Despreading (или декодирующий), чтобы извлечь сигнал сообщения может быть выполнен прямым способом путем умножения полученных сигналов соответствующими кодами Адамара Уолша, сгенерированными с помощью функции hadamard. (Обратите внимание на то, что индексация в MATLAB® запускается от 1, следовательно коды Адамара Уолша с sequency 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,'r')
legend('Original Message','Reconstructed Message','Location','Best')
xlabel('Sample index')
ylabel('Message signal amplitude')
subplot(2,1,2)
plot(x2)
hold on
plot(xHat2,'r')
legend('Original Message','Reconstructed Message','Location','Best')
xlabel('Sample index')
ylabel('Message signal amplitude')

Ссылки

К.Г. Беочамп, приложения Уолша и связанных функций - с введением в теорию Sequency, Academic Press, 1984
T. Бир, преобразования Уолша, американский журнал физики, издания 49, выпуска 5, май 1981

Документация

Дискретное преобразование Уолша-Адамара

Введение

Уолш (или Адамар) функции

Дискретное преобразование Уолша-Адамара

Приложения преобразования Уолша

Ссылки

Документация Signal Processing Toolbox

Поддержка