Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упорядочивание. Различные упорядочивания в преобразовании Уолша-Адамара.
|
|
Преобразование Уолша-Адамара наиболее известное среди несинусоидальных ортогональных преобразований. Оно широко применяется при обработке сигналов, поскольку может быть вычисленным только с использованием слжения и вычитания. При этом непрерывный сигнал представляется в виде ряда Уолша. Аналогично, как и для функций Уолша, так и для преобразований Уолша-Адамара существуют различные упорядочивания. Для преобразования наиболее часто применяются два упорядочивания: по Уолшу и по Адамару.
Оба случая рассмотрим на примере быстрого преобразования для N=8.
1. Упорядочивание по Адамару (природное упорядочивание).
Так как N=8, то имеется входная последовательность X=x(0)…x(7). Число итераций, необходимое для полного преобразования равно log2N. Для нашего случая log28 = 3.
Итерация №1.
x1(k)=x(k)+x(k+4), k=0, 1, 2, 3.
x1(k)=x(k-4)-x(k), k=4, 5, 6, 7.
Итерация №2.
x2(k)=x1(k)+x1(k+2), k=0, 1, 4, 5.
x2(k)=x1(k-2)-x1(k), k=2, 3, 6, 7.
Итерация №3.
x3(k)=x2(k)+x2(k+1), k=0, 2, 4, 6.
x3(k)=x2(k-1)-x2(k), k=1, 3, 5, 7.
Bx(k)=x3(k)/8; k=0, …, 7
Все выше изложенное можно описать на примере графов:
2. Упорядочивание по Уолшу (упорядочивание по частоте).
Так как N=8, то имеется входная последовательность X=x(0)…x(7). Число итераций, необходимое для полного преобразования равно log2N. Для нашего случая log28 = 3.
Первым шагом алгоритма является двоичное инвертирование входной последовательности и расположение ее в порядке увеличения двоично-инвертированных номеров.
x (000)=x(000) x (0)=x(0)
x (001)=x(100) x (1)=x(4)
x (010)=x(010) x (2)=x(2)
x (011)=x(110) x (3)=x(6)
x (100)=x(001) x (4)=x(1)
x (101)=x(101) x (5)=x(5)
x (110)=x(011) x (6)=x(2)
x (111)=x(111) x (7)=x(7)
В дальнейшем алгоритм схож с упорядочиванием по Адамару, однако имеются некоторіе отличия, связанніе с инверсией.
Итерация №1.
x1(k)=x(k)+x(k+4), k=0, 1, 2, 3.
x1(k)=x(k-4)-x(k), k=4, 5, 6, 7.
Итерация №2.
x2(k)=x1(k)+x1(k+2), k=0, 1.
x2(k)=x1(k-2)-x1(k), k=2, 3.
x2(k)=x1(k)-x1(k+2), k=4, 5.
x2(k)=x1(k-2)+x1(k), k=6, 7.
Итерация №3.
x3(k)=x2(k)+x2(k+1), k=0, 4.
x3(k)=x2(k-1)-x2(k), k=1, 5.
x3(k)=x2(k)-x2(k+1), k=2, 6.
x3(k)=x2(k-1)+x2(k), k=3, 7.
Bx(k)=x3(k)/8; k=0, …, 7
Все выше изложенное можно описать на примере графов:
|
|