зливаються в ті ж елементи пам'яті, з яких прочитувалися початкові для даної базової операції операнди.
Відомо багато різновидів алгоритмів БПФ [8]. Аналіз алгоритмів показує, що обчислення БПФ розділяються на ряд ітерацій, число ітерацій logrN. Нз кожній ітерації виконується N/r базових операцій, в яких беруть участь всі N відліків, розбитих на N/r груп по r відліків в кожній. Так, в базових операціях 1-й ітерації беруть участь групи з r відліків, віддалених друг від друга на N/r відліків. На 2-й ітерації в базових операціях беруть участь групи відліків, віддалених друг від друга на N/r2 відліків, і т. д. На останній ітерації беруть участь групи r відліків, що поряд стоять.
Якщо представити номер відліку п числом з підставою r:n=kL-1rL-1+ . . .+k1r1+k0r0, (3.21)
де ki=0, 1, ..., r-l;i=0, 1, ..., L—1; A=IogrN, то коди групи відліків, що беруть участь в базовій операції на j-и ітерації (j = 1, 2 ..., L), виходять зміною коефіцієнта kL-i від 0 до r-1 в коді номера будь-якого відліку, інші розряди кодів співпадають. Значення кодів відліків, що беруть участь в різних базових операціях на j-й ітерації, будуть відрізнятися значеннями інших розрядів коду.
Для прикладу в табл. 3.1, 3.2 наведені групи відліків, що беруть участь в базових операціях при виконанні алгоритму БПФ з N=64 і підставами 2 і 4 відповідно. Номери відліків при г=2 представляються 6 - розрядними війковими кодами
n=k525+k424+k323+k222+k121+k020
де ki = 0, 1; i=0, ..., 5.
Номери відліків при г=4 представляються 3-розрядними четвертними кодами
n = k222 + k121 + k020
де ki=0, 1, 2, 3; i=0, I, 2.
В табл. З.2 поряд із четвертинними кодами в дужках наведені їхні двійкові еквіваленти. Порядок виконання базових операцій на кожній ітерації може бути довільним.
Основна задача вузла управління – формування адрес прочитування операндів з ОЗУ і ПЗП коефіцієнтів поворотних множників і адрес запису результатів обчислень в ОЗУ. Алгоритм формування адрес ОЗУ залежить від алгоритму формування групи звітів, що беруть участь в базовій операції послідовності виконання базових операцій і структурної побудови ЦВ. При коефіцієнті розпаралелювання ОЗУ К=1 адреси зберігання операндів співпадають з їхніми номерами n (3.21) і алгоритм формування адрес прочитується з ОЗУ можна представити в наступним вигляді:
Асч (i) = rL-j( i mod r) + (i ÷ r) mod rL-j+ [rL-j+1 (i ÷ rL-j+1 )] mod N, (3.22)
де j=(i ÷ N)+1 - номер ітерації; i=0, 1, ..., (N(L - 1) - номер формованої адреси; r - основа БПФ; N - довжина БПФ; L=logr N — кількість ітерацій;
amod b-a по модулю b.
Алгоритм формування адрес запису Азп(i) результатів виконання базових операцій з Асч(i) з точністю до затримки в АУ: Aзп(i) =Асч(i-i0).
На мал. 3.12 наведена структурна схема вузла, що реалізує алгоритм (3.22) при r=2, N=64.
Для формування адрес прочитування використовуються розряди 1—6 лічильника. Перший розряд лічильника реализует функцію imod2. Множення 26-j(imod2) здійснює привласненням відповідної ваги розряду l лічильника у моормуючому адресі Асч. Так першому лічильнику не першійітерації при множенні 25(imod2) привласнюється вага розряду 6, на другій ітерації – розряду 5 і т. д. До розряду 1 на останній ітерації.

+1
1
2
3
R
4
5
6
7
8
9
Б
З
Y
A
D
R
З
RC
6 Aсч
fт
Початкова
установка
Розряди лічильника, починаючи з другого, реализують функцію i÷2. Обчислення по алгоритму (i÷2)mod 26-j реализується привласненням у формованій адресі прочитування відповідних терезів розрядам лічильника, починаючи з другого. На першій ітерації розрядам лічильника з другого по шостий представляються вага з першого по п'ятий відповідно. При виконанні другої ітерації розрядам лічильника з другого по п'ятий привласнюються вага з першого по четвертий і т д. На п'ятій ітерації розряду 2 лічильника привласнюється вага розряду 1. на шостій ітерації значення функції (i÷2) mod 1 рівне 0. Розряди 7 – 9 формують номер ітерації без одиниці (j -1) і реалізують функцію (i÷64).
Обчислення по алгоритму [27-j(i÷27-j)] mod64 реалізується використанням відповідних розрядів лічильника. На 1-й ітерації значення функції [26(i÷26)] mod64 рівне 0. На 2-й ітерації розряд 6 лічильника є розрядом 6 адреси прочитування. На 3-й ітерації розряди 6 і 5 лічильника є розрядами 6 і 5 Асч відповідно і т, д. На шостій ітерації розряди лічильника з другого по шостий відповідають розрядам Асч також з другого по шостий.
Комутація розрядів лічильника залежно від номера ітерації здійснюється за допомогою мультиплексорів . в табл 3.3 наведені номери розрядів лічильника, що підключаються
Таблиця 3.3
До виходу мультиплексора залежно від коду управління (номер ітерації), що поступає з розрядів 7-9 лічильника. Початкова адреса формується установкою в 0 лічильника і вихідного регістра. По кожному тактовому імпульсу сформована адреса записується в регістр і тим самим формується наступна адреса прочитування. Реалізація структурної схеми рис 3.12 при використанні ІС серії 133 забезпечується трьома ІС 133ИЕ7, шістьма ІС 133КП5, однією ІС 133ИР13.
Для виконання кожної базової операції на АУ необхідно подати r-1 поворотний коефіцієнт Wp, де W==e-2j?/N при прямому БПФ і W=e2j?/N при зворотному БПФ. Для алгоритму БПФ з проріджуванням за часом значення р пов'язані з номерами відліків п з (3.21), беруть участь у виконанні базової операції на j-й ітерації, наступним співвідношенням:
EMBED Equation.3
де j=1 ..., r-1 - номер поворотного коефіцієнта, що бере участь в базовій операції; ki - розряди r-ого кода номерів операндів з (3.21).
Наприклад, для N=64 і r=2 на 1-й ітерації значення р(1) для всіх груп відліків рівне 0, на 2-й ітерації р(1}=k524= =k5N/4, т. д.
EMBED Equation.3
На третій ітерації
EMBED Equation.3
і т д.
Алгоритм формування адрес ПЗП коефіцієнтів визначається алгоритмом виклику груп відліків і порядком розташування в ПЗП поворотних коефіцієнтів.
Для ПЗП з часом прочитування ?сч<Тбо/r поворотні коефіцієнти можуть бути розташовані в порядку Wk, де k=0 ... ... .N-1 - адреса ПЗП. При виклику відліків з ОЗУ згідно (3.22) алгоритм формування адрес ПЗП
AСЧ ПЗУ(i)=rL-1(imodr)rij-1[Aсч(i)÷rL-j+1]
де j — номер ітерації; Асч(i) —адрес прочитування з ОЗУ; rila — r-чна інверсія l молодших розрядів r-ого кода а.
Таблиця 3.4
Для ПЗП з часом прочитування ?сч ? T6о /r и ?сч < T6о необхідне розпаралелювання ПЗП. Тоді за однією адресою зберігаються Wk,W2k, ..., W(r-1)k. При виклику відліків з ОЗУ по алгоритму (3.22) алгоритм формування адрес ПЗП
EMBED Equation.3 (3.23)
Спрощена структурна схема вузла, реализуємого алгоритму (3.23) для N=64 і г=2 наведена на мал. 3.13. Формування Асч ПЗУ (i) здійснюється комутацією розрядів Асч (i) згідно табл. 3.4. В таблиці показані розряди Асч , що підключаються до виходів мультиплексора, який реализуеться на п'яти ІС 133КП5.
Рис. 3.13 Спрощена структурна схема вузла формування адреси читання з ПЗУ коефіцієнтів повертаючих множників при N=64, г=2, K=1
C
1
2
3
D
4
5
6
5
fт
5
RG
3
Y
A
MS
5 Aсч ПЗУ
5
j-1
ФУ управління множенням на частотну характеристику. Алгоритм множення на частотну характеристику полягає в множенні результатів виконання БПФ на відліки частотної характеристики фільтра. ФЕ управління множенням на частотну характеристику аналогічний ФУ управлення множенням на коректуючу функцію (мал. 3.11).
ФУ управління ОБПФ. Алгоритм ОБПФ відрізняється від алгоритму БПФ тільки значенням W, тому ФЕ управління ОБПФ аналогічний ФЕ управління БПФ. Для управління БПФ і ОБПФ може використовуватися один функціональний вузол.
Рис. 3.13 Упрощенная структурная схема узла формирувания адреса считывания из ПЗУ коэфициентов поворачивающих множителей при N=64, г=2, K=1
ФЕ управління видачею інформації. При послідовній видачі результатів обробки алгоритм прочитування інформації . з ОЗУ можна представити у вигляді наступного виразу:
А1сч(i) = А2сч(i) = … =AKcч(i)=Al + i ÷ K,
де А1 — початкова адреса прочитування; К—коэффициент розпаралелювання ОЗУ.
Вузол формування адрес прочитування ОЗУ реалізується двійковим лічильником і суматором. На мал. 3.14 наведена спрощена структурна схема для N=64, К=2. Реалізація структурної схеми мал. 3.14 забезпечується при використанні двох ІС 133ИЕ7 і по одній ІС 133ИМ2, 133ИМЗ, 133ИР13.
Порядок режимів роботи ЦВ залежить від вмісту інформації (команди управління)керівника, приходить на вузол управління ВУ. Послідовність режимів роботи ЦВ записується в ПЗП програм вузла управління ВУ. Залежно від команди, що прийшла, вибирається та область ПЗП програм, яка містить необхідну послідовність режимів, т. д. команда управління служить як би адресою осередку ПЗП, в якому зберігається 3-й з необхідної послідовності режимів. Після виконання чергового режиму адреса ПЗП програм збільшується на одиницю і встановлюється наступний режим роботи ЦВ і т. д.