сливаются в те же ячейки памяти, из которых считывались исходные для данной базовой операции операнды.
Известно много разновидностей алгоритмов БПФ [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 — номер итерации; Aсч(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.11).
C
1
2
3
D
4
5
6
5
fт
5
RG
3
Y
A
MS
5 Aсч ПЗУ
5
j-1
ФУ управления ОБПФ. Алгоритм ОБПФ отличается от алгоритма БПФ только значением W, поэтому ФУ управления ОБПФ аналогичен ФУ управления БПФ. Для управления БПФ и ОБПФ может использоваться один функциональный узел.
Рис. 3.13 Упрощенная структурная схема узла формирувания адреса считывания из ПЗУ коэфициентов поворачивающих множителей при N=64, г=2, K=1
ФУ управления выдачей информации. При последовательной выдаче результатов обработки алгоритм считывания информации . из ОЗУ можно представить в виде следующего выражения:

А1сч(i) = А2сч(i) = … =AKcч(i)=Al + i ÷ K,
где A1 — начальный адрес считывания; К—коэффициент распараллеливания ОЗУ.
Узел формирования адресов считывания ОЗУ реализуется двоичным счетчиком и сумматором. На рис. 3.14 приведена упрощенная структурная схема для N=64, К=2. Реализация структурной схемы рис. 3.14 обеспечивается при использовании двух ИС 133ИЕ7 и по одной ИС 133ИМ2, 133ИМЗ, 133ИР13.
Порядок режимов работы ЦВ зависит от содержимого управляющей информации (команды управления), .приходящей на узел управления УУ. Последовательность режимов работы ЦВ записывается в ПЗУ программ узла .управления УУ. В зависимости от пришедшей команды выбирается та область ПЗУ программ, которая содержит требуемую последовательность режимов, т. е. команда управления служит как бы адресом ячейки ПЗУ, в которой хранится 3-й из требуемой последовательности режимов. После выполнения очередного режима адрес ПЗУ программ увеличивается на единицу и устанавливается следующий режим работы ЦВ и т. д. Таким образом, организацию последовательности выполнения алгоритмов работы ЦВ можно рассматривать как последовательный перебор адресов ПЗУ программ, начиная с адреса, определяемого командой управления. Эта задача реализуется с помощью счетчика программ, считающего количество выполненных режимов и устанавливаемого в начальное состояние командой управления. Упрощенная структурная схема части ФУ управления УУ, управляющей последовательностью режимов, приведена на рис. 3.15. Команда управления преобразуется в шифраторе в начальный адрес ПЗУ программ, который по команде «Прием заданыя> записывается в двоичный счетчик. Счетчик меняет свое состояние после окончания очередного режима. Сформированный на счетчике адрес выбирает из ПЗУ программ код режима, который управляет работой формирователей адресов ОЗУ, ПЗУ коэффициентов, различных команд управления блоками ЦВ.