Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 10:42

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Вычисление быстрого преобразования Хартли на SEAforth40
СообщениеДобавлено: Сб дек 26, 2009 22:08 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Ср дек 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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб дек 26, 2009 22:10 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Ср дек 06, 2006 09:23
Сообщения: 660
Благодарил (а): 7 раз.
Поблагодарили: 25 раз.
Файл math.vf
Код:
: d*-shift ( x y -- pl ) \ учитываем только младшую часть
  * drop drop
  a@ $20000 # xor \ -- ph pl
  2/ 2/ 2/ 2/ 2/ 2/ 2/ 2/ ;

: negate not 1 # . + ;


Файл Hartley_test_.vf
Код:
{
считаем, что обрабатываем данные с ацп
28-0 27-2......21-14
18-1 27-3......21-15
}

v.VF +include" c7Gr01/romconfig.f"


0 VALUE in_
0 VALUE in_1
0 VALUE in_2
0 VALUE out_
0 VALUE out_1
0 VALUE out_2
$b5 VALUE rr

16 VALUE num \ количество отсчетов
0 VALUE v \ текущий отсчет Хартли спектра
include Fpmath.f
include coef0.vf

   num  0  icos VALUE c0
   num  1  icos VALUE c1
   num  2  icos VALUE c2
   num  3  icos VALUE c3
   num  4  icos VALUE c4


38 {node  \ ядро - "генератор" сигнала
0 org  here =p
  '-d-- # b!
  $100 # !b
  $100 # !b
  $0 # !b
  $0 # !b
 
  $0 # !b
  $0 # !b
  $0 # !b
  $0 # !b
 
  $0 # !b
  $0 # !b
  $0 # !b
  $0 # !b
 
  $0 # !b
  $0 # !b
  $100 # !b
  $100 # !b
node}


28 {node  0 org 
\ входной порт врегистре -b ; выходной -a;

: 8transit @b !a : 7transit @b !a @b !a
@b !a
@b !a  @b !a
@b !a  @b !a ;

: a!b! ( a# b# -- ; a= b= ) b! a! ;

: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: negate not 1 # . + ;

  here =p

\ ----перестановка----------------
    '--l- # '-d-- # a!b!
    @b \ -- f0
    7transit
    '---u # a!
    8transit

\ ----перый этап------------------
  '---u # b! +bat

\ ----второй этап-----------------
  '--l- # dup a!b! +bat

\ ----третий этап-----------------
  +bat \ --f0

\ ----четвертый этап--------------
\ работаем с числами одинарной точности
\ т.е. просто отбрасываем старшую часть
\ --f0 a=l; b=l;
  @b \ -- f0 f8

  include bat.vf
  . '-d-- # b! @b \ останов ядра - только для режима симуляции

node}

27 {node

: 3transit @b !a
: 2transit @b !a : transit> @b !a ;
: transit< @a !b ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;
  include math.vf

: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;
\ входной порт врегистре -b ; выходной -a;


  here =p
\ ----перестановка----------------
  'r--- # '--l- # a!b!
  3transit
  @b \ -- f2
  3transit
\ ----перый этап------------------
  '---u # dup a!b! +bat
\ ----второй этап-----------------
  '--l- # dup a!b! -bat
\ ----третий этап-----------------
'r--- # b! \ a=l ; b=r
  transit>
  transit<
  'r--- # a! +bat \ a=r b=r
\ ----четвертый этап--------------
\ -- f2 ; a=r b=r
  '--l- # a! \ -- f2 ; a=l b=r
  transit>      \ -- f2 ; a=l b=r
  @b @b \ -- f2 f10 f14
  . + \ -- f2 f10+f14
  c2 # d*-shift \ -- f2 [f10+f14]*c2
  include bat.vf
\ -- H2 H10

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции

node}

26 {node
: 4transit @b !a @b !a
: 2transit @b !a : transit> @b !a ;
: transit< @a !b ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;

  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;

\ входной порт врегистре -b ; выходной -a;

  here =p
\ ----перестановка----------------
  '--l- # 'r--- # a!b!
  transit>
  @b \ -- f4
  4transit

\ ----перый этап------------------
  '---u # dup a!b! +bat

\ ----второй этап-----------------
  '--l- # dup a!b! +bat

\ ----третий этап-----------------
  'r--- # dup a!b! -bat \ a=r b=r
  '--l- # b! transit> \ a=r b=l ; transit @b>>!a ;
  transit<

\ ----четвертый этап--------------
\ -- f4 ; a=r b=l ;
  transit>
  @b  \ -- f4 f12 ; a=r b=l ;
  2transit \ -- f4 f12 ; a=r b=l ;
  include bat.vf
\ -- H4 H12

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции

node}

25 {node

: 3transit @b !a
: 2transit @b !a : transit> @b !a ;
: transit< @a !b ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;
  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;
\ входной порт врегистре -b ; выходной -a;

  here =p

\ ----перестановка----------------
  'r--- # '--l- # a!b!
  3transit
  @b \ -- f6
  transit>

\ ----перый этап------------------
  '---u # dup a!b! +bat

\ ----второй этап-----------------
  '--l- # dup a!b! -bat

\ ----третий этап-----------------
  -bat

\ ----четвертый этап--------------
\ -- f6 ; a=l ; b=l
  'r--- # b! \ -- f6 ; a=l ; b=r
  2transit
  @b dup !a @b dup !a \ -- f6 f10 f14; a=l ; b=r
  negate + c2 # d*-shift     \ -- f6 [f10-f14]*c2; a=l ; b=r
  include bat.vf  \ -- H6 H14

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции

node}
           
24 {node

: 3transit @b !a @b !a @b !a ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;

  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
\ входной порт врегистре -b ; выходной -a;

  here =p

\ ----перестановка----------------
  '--l- # 'r--- # a!b!
  @b \ -- f8
  3transit

\ ----перый этап------------------
  '---u # dup a!b! +bat

\ ----второй этап-----------------
  '--l- # dup a!b! +bat

\ ----третий этап-----------------
  +bat

\ ----четвертый этап--------------
\ -- f8; a=l; b=l
  'r--- # a! \ -- f8; a=r; b=l;
  dup !a \ -- f8; a=r; b=l;
  3transit

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции

node}

23 {node

: 2transit @b !a : transit> @b !a ;
: transit< @a !b ;
\ : a!b! ( a# b# -- ; a= b= ) b! a! ;
: negate not 1 # . + ;

  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;

\ входной порт врегистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
  'r--- # '--l- # b! a!
  transit>
  @b \ -- f10
  transit>
\ ----перый этап------------------
  '---u # dup a! b! +bat
\ ----второй этап-----------------
  '--l- # dup a! b! -bat
\ ----третий этап-----------------
'r--- # b! \ a=l ; b=r
  transit>
  transit<
  'r--- # a! +bat \ a=r b=r
\ ----четвертый этап--------------
\ -- f10 ; a=r; b=r;
  '--l- # a! \ -- f10 ; a=l; b=r;
  transit>
  dup !a \  -- f10 ; a=l; b=r;
  transit>

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции

node}

22 {node
: transit> @b !a ;
: transit< @a !b ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;

  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;

\ входной порт врегистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
  '--l- # 'r--- # a!b!
  @b \ -- f10
  transit>
\ ----перый этап------------------
  '---u # dup a!b! +bat
\ ----второй этап-----------------
  '--l- # dup a!b! +bat
\ ----третий этап-----------------
  'r--- # dup a!b! -bat \ a=r b=r
  '--l- # b! transit> \ a=r b=l ; transit @b>>!a ;
  transit<
\ ----четвертый этап--------------
\ -- f12 ; a=r ; b=l
  dup !a
  transit>

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции

node}

21 {node
: a!b! ( a# b# -- ; a= b= ) b! a! ;
  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;

\ входной порт врегистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
  'r--- # '--l- # a!b!
  @b \ -- f10
\ ----перый этап------------------
  '---u # dup a!b! +bat
\ ----второй этап-----------------
  '--l- # dup a!b! -bat
\ ----третий этап-----------------
  -bat
\ ----четвертый этап--------------
\ -- f14; a=l; b=l;
  dup !a
  . '-d-- # b! @b       \ останов ядра - только для режима симуляции

node}
\ --------------------------------------------------------------------------
\ ---- нечетные номера------------------------------------------------------

18 {node  0 org 
: 7transit
@b !a @b !a
@b !a  @b !a @b !a
@b !a  @b !a ;

: a!b! ( a# b# -- ; a= b= ) b! a! ;

include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;

\ входной порт в регистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
    '--l- # '---u # a!b!
    @b \ -- f1
    7transit
\ ----первый этап------------------
  '---u # dup a!b! -bat
\ ----второй этап-----------------
  '--l- # dup a!b! +bat \ -- f(2,1)
\ ----третий этап-----------------
\ -- f; a=l;b=l;
  dup push \ -- f ; r: -- f
  @b @b . + rr # d*-shift \ -- f [5+7]*r ; r: -- f
  dup dup xor dup . +  drop .
  + \ f3
  pop  \ f3 f
  dup !b !b
\  . '-d-- # b! @b
\ ----червертый этап------------
\ -- f1 ; a=** ; b=l
  @b c1 # d*-shift \ -- f1 f9*c1  ; a=** ; b=l\
  @b c3 # d*-shift      \ -- f1 f9*c1 f15*c3 ; a=** ; b=l
  +                     \ -- f1 f9*c1+f15*c3 ; a=** ; b=l
  include bat.vf

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

17 {node

: 3transit @b !a : 2transit @b !a : transit> @b !a ;

include math.vf
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;
\ входной порт в регистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
  'r--- # '--l- # b! a!
  3transit
  @b \ -- f2
  3transit
\ ----первый этап------------------
  '---u # dup a! b! -bat

\ ----второй этап-----------------
  '--l- # dup a! b! -bat

\ ----третий этап-----------------
  'r--- # b! 2transit          \ -- f(2,3)
  @b @b . + rr # d*-shift \ -- f [5+7]d*r ; r: -- f
  dup dup xor dup . +  drop .  \ очищаем бит переноса
  + \ f3
  'r--- # '--l- # b! a! 2transit \ a=r; b=l;
\  . '-d-- # b! @b

\ ---четвертый этап--------------
  '--l- #  'r--- # b! a!
\ -- f3 ; a=l ; b=r
  2transit
  @b c3 # d*-shift \ -- f1 f11*c1  ; a=** ; b=l\
  @b c1 # d*-shift      \ -- f1 f11*c1 f13*c3 ; a=** ; b=l
  +                     \ -- f1 f11*c1+f13*c3 ; a=** ; b=l
  include bat.vf
\ -- H3 H11

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

16 {node

  include math.vf
: negate not 1 # . + ;
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;
\ входной порт в регистре -b ; выходной -a;


  here *cy =p
\ ----перестановка----------------
  '--l- # 'r--- # b! a!
  @b !a \ transit>
  @b \ -- f4
  @b !a @b !a @b !a @b !a \ 4transit

\ ----первый этап------------------
  '---u # dup a! b! -bat

\ ----второй этап-----------------
  '--l- # dup a! b! +bat \ --f(2,5)

\ ----третий этап-----------------
  dup \ -- f f ; a=l ; b=l
  'r--- # a! !a   \ -- f a=r; b=l
  @b !a \ transit>
  dup !a
  @b !a \ transit> \ -- f a=r; b=l
  dup @b \ -- f5 f5 f7
  a@ push
  . + rr # d*-shift  negate  \ -- f5 -r*[f5+f7]
  dup dup xor dup . +  drop . \ очищаем бит переноса
  pop a!
  @a . + \ -- f5 -r*[f5+f7]+f3 ; a=r;b=l
  over !b
  @a !b \ transit<
\  . '-d-- # b! @b

\ ---четвертый этап--------------
  'r--- # '--l- # b! a!
\ -- f5 ; a=r; b=l
  @b !a @b !a \ 2transit
  a@ push
  @b dup !a c1 # d*-shift
  pop a!
  @b dup !a c3 # d*-shift
  negate + \ -- f5 c1*f11-c3*f13 ; a=**; b=l
  include bat.vf
\ -- H5 H13

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

15 {node
: 3transit @b !a @b !a @b !a ;

  include math.vf
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;
\ входной порт врегистре -b ; выходной -a;

  here *cy =p

\ ----перестановка----------------
  'r--- # '--l- # b! a!
  3transit
  @b \ -- f6
  @b !a \ transit>

\ ----первый этап------------------
  '---u # dup a! b! -bat

\ ----второй этап-----------------
  '--l- # dup a! b! -bat

\ ----третий этап-----------------
  dup negate over \  -- f -f f a=l; b=l
  !b !b  \ -- f
  dup !b
  @b negate + rr # d*-shift
  @b . + \
\  . '-d-- # b! @b

\ ---четвертый этап--------------
  '--l- # 'r--- # b! a!
\ -- f7; a=l; b=r
  a@ dup push push
  @b dup !a c3 # d*-shift \ -- f7 f9*c3; a=**; b=r
  pop a!
  @b dup !a c1 # d*-shift \ -- f7 f9*c3 f15*c1; a=**; b=r
  negate + \ -- f7 f9*c3-f15*c1; a=**; b=r
  pop a!
  @b !a @b !a \ 2transit
  include bat.vf
\ -- H7 H15
  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

14 {node

: 3transit @b !a
@b !a  @b !a ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;

  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;

\ входной порт врегистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
  '--l- # 'r--- # a!b!
  @b \ -- f8
  3transit

\ ----первый этап------------------
  '---u # dup a!b! -bat

\ ----второй этап-----------------
  '--l- # dup a!b! +bat

\ ----третий этап-----------------
\ -- f; a=l;b=l;
  dup push \ -- f ; r: -- f
  @b @b . + rr # d*-shift \ -- f [5+7]*r ; r: -- f
  dup dup xor dup . + drop .
  + \ f3
  pop  \ f3 f
  dup !b !b
\  . '-d-- # b! @b

\ ---четвертый этап--------------
  'r--- # '--l- # a!b!
\ -- f9 ; a=r; b=l;
  dup !a
  3transit

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

13 {node

: 2transit @b !a : transit> @b !a ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;

  include math.vf
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;

\ входной порт врегистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
  'r--- # '--l- # a!b!
  transit>
  @b \ -- f10
  transit>

\ ----первый этап------------------
  '---u # dup a!b! -bat

\ ----второй этап-----------------
  '--l- # dup a!b! -bat

\ ----третий этап-----------------
  'r--- # b! 2transit              \ -- f(2,3)
  @b @b . + rr # d*-shift \ -- f [5+7]d*r ; r: -- f
  dup dup xor dup . +  drop . \ очищаем бит переноса
  + \ f3
  'r--- # '--l- # a!b! 2transit
\  . '-d-- # b! @b

\ ---четвертый этап--------------
  '--l- # 'r--- # a!b!
\ -- f11 ; a=l; b=r
  transit>
  dup !a
  transit>
 
  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

12 {node

: transit> @b !a ;
: transit< @a !b ;
: a!b! ( a# b# -- ; a= b= ) b! a! ;

  include math.vf
: +bat ( f1 -- f1+f2; @b=f2 -- ; -- !a=f1  ) @b over !a . + ;
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;
\ входной порт врегистре -b ; выходной -a;

  here *cy =p

\ ----перестановка----------------
  '--l- # 'r--- # a!b!
  @b \ -- f10
  transit>

\ ----первый этап------------------
  '---u # dup a!b! -bat

\ ----второй этап-----------------
  '--l- # dup a!b! +bat

\ ----третий этап-----------------
  dup \ -- f f ; a=l ; b=l
  'r--- # a! !a   \ -- f13 a=r; b=l
  transit> dup !a transit> \ -- f13 a=r; b=l
  dup negate @b \ -- f13 -f13 f15
  a@ push
  . + rr # d*-shift  \ -- f13 r*[-f13+f15]
  dup dup xor dup . +  drop . \ очищаем бит переноса
  pop a!
  @a . + \ -- f13 r*[-f13+f15]+f9 ; a=r;b=l
  over !b
  transit<
\  . '-d-- # b! @b

\ ---четвертый этап--------------
\ -- f12 ; a=r; b=l;
  transit>
  dup !a
 
  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

11 {node
: a!b! ( a# b# -- ; a= b= ) b! a! ;
  include math.vf
: -bat ( f1 -- f1-f2; @b=f2 -- ; -- !a=f1  ) dup !a negate @b . + ;
\ входной порт врегистре -b ; выходной -a;

  here *cy =p
\ ----перестановка----------------
  'r--- # '--l- # a!b!
  @b \ -- f10
\ ----первый этап------------------
  '---u # dup a!b! -bat
\ ----второй этап-----------------
  '--l- # dup a!b! -bat
\ ----третий этап-----------------
  dup negate over \  -- f -f f a=l; b=l
  !b !b  \ -- f
  dup !b
  @b negate + rr # d*-shift
  @b . + \
\  . '-d-- # b! @b
\ ---четвертый этап--------------
  '--l- # dup a!b!
  dup !a
\ -- f15

  . '-d-- # b! @b       \ останов ядра - только для режима симуляции
node}

   reset     \ reset prepares the system to run the code in the Simulator
             \ enter  simulate  or  sim   to start the simulator
   cr
\   14 13 12 11 watch4    1 setstep
   28 27 26 25 watch4    1 setstep
   sim



Временные параметры вычислений следующие:
- вычисление коэффициента Хартли спектра ~ 1150 тактов или около 620000 преобразований в секунду.

Распараллелив вычисления на 4-м этапе скорость преобразования можно еще несколько поднять.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб дек 26, 2009 22:13 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Ср дек 06, 2006 09:23
Сообщения: 660
Благодарил (а): 7 раз.
Поблагодарили: 25 раз.
Наиболее загруженное по коду ядро - ядро номер 16:

Код:
RAM Node 16

: d*-shift
000 31JS 134CA call CA  *
001 NNR8 3A28F drop drop a@ @p+
002 QLAK 20000
003 MIIS 387C2 xor 2/ 2/ .
004 IIIS 307C2 2/ 2/ 2/ .
005 III0 307C5 2/ 2/ 2/ ;
006 J8SK 33DB0 not @p+ . +
007 ALAG 00001
008 0000 15555 ;
: negate
009 J8SK 33DB0 not @p+ . +
00A ALAG 00001
00B 0000 15555 ;
: +bat
00C AQFS 00F2A @b over !a .
00D K000 3D555 + ;
: -bat
00E OF3G 25A49 dup !a call 9  negate
00F ASK0 009F5 @b . + ;
010 88US 05DA2 @p+ @p+ b! .
011 AK40 00175
012 AKG0 001D5
013 VAFS 2BF2A a! @b !a .
014 AAFS 01F2A @b @b !a .
015 AFAS 01A02 @b !a @b .
016 FAF8 0BF2F !a @b !a @p+
017 AK20 00145
018 OVUS 24AA2 dup a! b! .
019 31BC 1340E call E  -bat
01A 8OVS 04DAA @p+ dup a! .
01B AK40 00175
01C U3B4 2960C b! call C  +bat
01D O8VS 25DAA dup @p+ a! .
01E AKG0 001D5
01F FAFO 0BF2B !a @b !a dup
020 FAFO 0BF2B !a @b !a dup
021 ARTS 00EBA @b a@ push .
022 K8SS 3DDB2 + @p+ . .
023 ALS0 000B5
024 31AK 13400 call 0  d*-shift
025 31BG 13409 call 9  negate
026 OOMO 24DE3 dup dup xor dup
027 SKNS 2C1EA . + drop .
028 PVBS 26A0A pop a! @a .
029 KQES 3CF22 + over !b .
02A BE88 03B17 @a !b @p+ @p+
02B AKG0 001D5
02C AK40 00175
02D UVAS 28A02 b! a! @b .
02E FAFS 0BF2A !a @b !a .
02F RTAO 22803 a@ push @b dup
030 F8SS 0BDB2 !a @p+ . .
031 ALN0 000ED
032 31AK 13400 call 0  d*-shift
033 PVAO 26A03 pop a! @b dup
034 F8SS 0BDB2 !a @p+ . .
035 AL6S 00062
036 31AK 13400 call 0  d*-shift
037 31BG 13409 call 9  negate
038 KQQS 3CF82 + over over .
039 31BG 13409 call 9  negate
03A KTSK 3C8B0 + push . +
03B PS8S 26912 pop . @p+ .
03C AK80 00115
03D UAAK 29F00 b! @b @b +
03E 31VG
03F 31VG


В среднем же загрузка RAM задействованных ядер порядка 70-80%.

Литература:


1. Брейсуэлл Р. Преобразование Хартли: пер. с англ. - М.: Мир, 1990.-175с.
2. SEAforth 40C18 Device Data Sheet. [Электронный ресурс] - Режим доступа: http://www.intellasys.net/templates/tri ... aSheet.pdf, свободный. - Яз. Англ.
3. IntellaSys - SEAforth 40C18. / http://www.intellasys.net/index.php?opt ... &Itemid=75.
4. New VentureForth Programmers Guide. / http://www.intellasys.net/index.php?opt ... &Itemid=68.
5. Александр Калачев. Процессоры семейства SEAforth. // Журн. Компоненты и технологии. - 2009. - №4. - С. 66-73.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB