Зарегистрирован: Ср дек 06, 2006 09:23 Сообщения: 660 Благодарил (а): 7 раз. Поблагодарили: 25 раз.
|
Автор: Калачев Александр
Дата публикации: 2009.12.26
Вычисление быстрого преобразования Хартли на SEAforth40
Введение
Алгоритмы быстрого преобразования Хартли строятся приблизительно на тех же принципах, что и преобразования Фурье. Много точечные преобразования также строятся на основе 2-, 3- или 4-точечных преобразований, т.н. <бабочек>.
16-ти точечное БПХ
Для примера рассмотрим 16-точечное быстрое преобразование Хартли.
Преобразование входной последовательности f(t) начинается с её перестановки в двоично-инверсном порядке. f(t)>F(0,t). Далее элементы последовательности подвергаются трем этапам преобразований.
1й этап F(0,0)+F(0,1)->F(1,0) F(0,0)-F(0,1)->F(1,1) F(0,2)+F(0,3)->F(1,2) F(0,2)-F(0,3)->F(1,3)
F(0,4)+F(0,5)->F(1,4) F(0,4)-F(0,5)->F(1,5) F(0,6)+F(0,7)->F(1,6) F(0,6)-F(0,7)->F(1,7) F(0,8)+F(0,9)->F(1,8) F(0,8)-F(0,9)->F(1,9) F(0,10)+F(0,11)->F(1,10) F(0,10)-F(0,11)->F(1,11)
F(0,12)+F(0,13)->F(1,12) F(0,12)-F(0,13)->F(1,13) F(0,14)+F(0,15)->F(1,14) F(0,14)-F(0,15)->F(1,15)
2й этап F(1,0)+F(1,1)->F(2,0) F(1,2)+F(1,3)->F(2,1) F(1,0)-F(1,1)->F(2,2) F(1,2)-F(1,3)->F(2,3)
F(1,4)+F(1,5)->F(2,4) F(1,6)+F(1,7)->F(2,5) F(1,4)-F(1,5)->F(2,6) F(1,6)-F(1,7)->F(2,7)
F(1,8)+F(1,9)->F(2,8) F(1,10)+F(1,11)->F(2,9) F(1,8)-F(1,9)->F(2,10) F(1,10)-F(1,11)->F(2,11)
F(1,12)+F(1,13)->F(2,12) F(1,14)+F(1,15)->F(2,13) F(1,12)-F(1,13)->F(2,14) F(1,14)-F(1,15)->F(2,15)
3й этап F(2,0)+F(2,4)->F(3,0) F(2,1)+rF(2,5)+rF(2,7)->F(3,1) F(2,2)+F(2,6)->F(3,2) F(2,3)-rF(2,7)+rF(2,5)->F(3,3)
F(2,0)-F(2,4)->F(3,4) F(2,1)-rF(2,5)-rF(2,7)->F(3,5) F(2,2)-F(2,6)->F(3,6) F(2,3)+rF(2,7)-rF(2,5)->F(3,7)
F(2,8)+F(2,12)->F(3,8) F(2,9)+rF(2,13)+rF(2,15)->F(3,9) F(2,10)+F(2,14)->F(3,10) F(2,11)-rF(2,15)+rF(2,13)->F(3,11)
F(2,8)-F(2,12)->F(3,12) F(2,9)-rF(2,13)-rF(2,15)->F(3,13) F(2,10)-F(2,14)->F(3,14) F(2,11)+rF(2,15)-rF(2,13)->F(3,15)
4й этап F(3,0)+F(3,8)->> F(4,0)=H(0) F(3,1)+F(3,9)c1+F(3,15)c3->>F(4,1)=H(1) F(3,2)+F(3,10)c2+F(3,14)c2->>F(4,2)=H(2) F(3,1)+F(3,11)c3+F(3,13)c1->>F(4,3)=H(3)
F(3,4)+F(3,12)->> F(4,4)=H(4) F(3,5)-F(3,13)c3+F(3,12)c1->>F(4,5)=H(5) F(3,6)-F(3,14)c2+F(3,11)c2->>F(4,6)=H(6) F(3,7)-F(3,15)c1+F(3,10)c3->>F(4,7)=H(7)
F(3,0)-F(3,8)->> F(4,8)=H(8) F(3,1)-F(3,9)c1-F(3,15)c3->>F(4,9)=H(9) F(3,2)-F(3,10)c2-F(3,14)c2->>F(4,10)=H(10) F(3,1)-F(3,11)c3-F(3,13)c1->>F(4,11)=H(11)
F(3,4)-F(3,12)->> F(4,12)=H(12) F(3,5)+F(3,13)c3-F(3,12)c1->>F(4,5)=H(5) F(3,6)+F(3,14)c2-F(3,11)c2->>F(4,6)=H(6) F(3,7)+F(3,15)c1-F(3,10)c3->>F(4,7)=H(7)
где r=1/sqrt(2); с1= cos(2pi/16)=0,924; с2= cos(2pi*2/16)=0,707; с3= cos(2pi*3/16)=0,383.
Как видно из приведенных выше соотношений, основная вычислительная нагрузка идёт на операции типа сложения/вычитания и выборку значений из памяти, особенно на первых трех этапах.
Будем предполагать, что отсчёты входного сигнала последовательно принимаются одним из ядер процессора (из внешнего или внутреннего АЦП, или, например, из памяти).
Применим конвейерную схему распараллеливания - каждое ядро или группа ядер заняты вычислением результатов отдельного этапа преобразования, с распараллеливанием операций по эта-пам. Выделим для проведения вычислений группу средних ядер процессора, тем самым снижая нагрузку на периферийные ядра.
Диаграмма потоков данных двоично-инверсной перестановки для 16-ти ядер выглядит сле-дующим образом:
Код: f(t) 0 2 4 6 8 10 12 14 0------------>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 1-------------+-------+-------+-------+------>¦ ¦ ¦ ¦ 2---------------------------->¦ ¦ ¦ ¦ ¦ ¦ 3-----------------------------+-------+-------+-------+------>| ¦ 4-------------------->¦ ¦ ¦ ¦ ¦ ¦ ¦ 5---------------------+-------+-------+-------+------>¦ ¦ ¦ 6------------------------------------>¦ ¦ ¦ ¦ ¦ 7-------------------------------------+-------+-------+-------+------>¦ 8------------¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 9-----------¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 10---------¦¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 11--------¦¦¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 12-------¦¦¦¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 13------¬¦¦¦¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 14-----¬¦¦¦¦¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 15----¬¦¦¦¦¦¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦¦¦¦¦¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦¦¦¦¦¦¦v v v v v v v v ¦¦¦¦¦¦¦¦ ¦¦¦¦¦¦¦¦1 3 5 7 9 11 13 15 ¦¦¦¦¦¦¦>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦¦¦¦¦+-+-------+-------+-------+------>¦ ¦ ¦ ¦ ¦¦¦¦¦+----------------->¦ ¦ ¦ ¦ ¦ ¦ ¦¦¦¦--------------------+-------+-------+-------+------>| ¦ ¦¦¦------------>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦--------------+-------+-------+-------+------>¦ ¦ ¦ ¦ ----------------------------->¦ ¦ ¦ ¦ ¦ L-------------------------------+-------+-------+-------+------>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ | v V v v v v v v v Для первого этапа имеем следующее: Код: (0) (2) (4) (6) (8) (10) (12) (14) ¦<-¬ ¦<-¬ ¦<-¬ ¦<-¬ ¦<-¬ ¦<-¬ ¦<-¬ ¦<-¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ --- ¦ --- ¦ --- ¦ --- ¦ --- ¦ --- ¦ --- ¦ --- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+] ¦ ¦ [+] ¦ ¦ [+] ¦ ¦ [+] ¦ ¦ [+] ¦ ¦ [+] ¦ ¦ [+] ¦ ¦ [+] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ v ¦ ¦ v ¦ ¦ v ¦ ¦ v ¦ ¦ v ¦ ¦ v ¦ ¦ v ¦ ¦ v ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ (1) ¦ ¦ (3) ¦ ¦ (5) ¦ ¦ (7) ¦ ¦ (9) ¦ ¦(11) ¦ ¦(13) ¦ ¦(15) ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦--¦ ¦ ¦--¦ ¦ ¦--¦ ¦ ¦--¦ ¦ ¦--¦ ¦ ¦--¦ ¦ ¦--¦ ¦ ¦--¦ ¦[neg] ¦[neg] ¦[neg] ¦[neg] ¦[neg] ¦[neg] ¦[neg] ¦[neg] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ L->¦ L->¦ L->¦ L->¦ L->¦ L->¦ L->¦ L->¦ [+] [+] [+] [+] [+] [+] [+] [+] | | | | | | | | v v v v v v v v Для второго этапа: Код: (0) (2) (4) (6) (8) (10) (12) (14) ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<-------+ ¦<-------+ ¦<-------+ ¦<-------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [neg] ¦ [neg] ¦ [neg] ¦ [neg] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦------->¦ ¦------->¦ ¦------->¦ ¦------->¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+] [+] [+] [+] [+] [+] [+] [+] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ v v v v v v v v
(1) (3) (5) (7) (9) (11) (13) (15) ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<-------+ ¦<-------+ ¦<-------+ ¦<-------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [neg] ¦ [neg] ¦ [neg] ¦ [neg] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦------->¦ ¦------->¦ ¦------->¦ ¦------->¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+] [+] [+] [+] [+] [+] [+] [+] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ v v v v v v v v Для третьего этапа: Код: (0) (2) (4) (6) (8) (10) (12) (14) ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-------+ ¦ ¦<------+-------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [neg] ¦ ¦ ¦ [neg] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦-------+------>¦ ¦ ¦-------+------>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+] ¦ [+] ¦ [+] ¦ [+] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-------+ ¦ ¦<------+-------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [neg] ¦ ¦ ¦ [neg] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦-------+------>¦ ¦ ¦-------+------>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+] ¦ [+] ¦ [+] ¦ [+] | | | | | | | |
(1) (3) (5) (7) (9) (11) (13) (15) ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-------+ ¦ ¦<------+-------+ ¦ ¦<------¬-------¬-------+ ¦<------¬-------¬-------+ | ¦ ¦ ¦ | ¦ ¦ ¦ [+] ¦<------+ [neg] [+] ¦<------+ [neg] | ¦<------¬-------¬ | ¦<------¬-------¬ [r*] | [neg] ¦ [r*] | [neg] ¦ | [+] ¦<------+ | [+] ¦<------+ [+] | ¦ ¦ [+] | ¦ ¦ ¦ [r*] [+] ¦ ¦ [r*] [+] ¦ ¦ | ¦ ¦ ¦ | ¦ ¦ ¦ [+] [r*] ¦ ¦ [+] [r*] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ +-------+------>¦ ¦ +-------+------>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+] ¦ ¦ ¦ [+] ¦ ¦ ¦ ------->¦ ¦ ¦ [neg] ¦ ¦ ¦ | [neg] ¦ ¦ +------>¦ ¦ ¦ ¦ [+] ¦ ¦ ¦ [+] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [r*] ¦ ¦ ¦ [r*] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ +-------+-------+------>¦ +-------+-------+------>¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ | | | [+] | | | [+] | | | | | | | | И заключительный четвертый этап: Код: (0) (2) (4) (6) (8) (10) (12) (14) ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-------+-------+-------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+-bat] ¦ ¦<------+-------+-------+--------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-----[dup]-----+-------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-----[dup]-----+-------+--------+--------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+] [+-bat] [+] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+-bat] ¦ [+-bat] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
(1) (3) (5) (7) (9) (11) (13) (15) ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-------+-----[dup]-----+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [c1*] ¦ ¦ [c3*] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<------+-------+-----[dup]-----+-------+--------+--------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [c3*] ¦ ¦ [c1*] ¦ ¦ ¦ ¦ ¦ ¦<----[dup]-----+-------+-------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [c3*] [c1*] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦<----[dup]-----+-------+-------+--------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [c1*] [c3*] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ [+-bat] [+-bat] [+-bat] [+-bat] ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ В результате в ядре с номером 0 хранятся коэффициенты Хартли 0 и 8; в 1-м - 1 и 9; во 2-м - 2 и 10; в 3-м - 3 и 11; в 4-м - 4 и 12; в 5-м - 5 и 13; в 6-м - 6 и 14; в 7-м - 7 и 15. Для примера рассмотрена реализация БПХ на средних 16-ти ядрах SEAforth40, при этом ядра 28-21 соответствуют четным индексам (0==28, 2==27, и т.д.), а ядра 18-11 нечетным индексам (1==18, 3==17, и т.д.). Ядро 38 работает генератором сигнала - выдает 16ть последовательных отсчетов. При создании кода учитывались следующие ограничения - работаем в формате с фиксирован-ной точкой одинарной точности. Масштабирование - $100 ==1. Файл coef0.vfКод: : 2pi_k/N ( N k -- ; f: -- 2pi_k/N ) s>f s>f f/ pi 2.e f* f* ; : icos ( N k -- icos ) 2pi_k/N cos ; IMMEDIATE
|
|