Устройство для быстрого преобразования Фурье Советский патент 1987 года по МПК G06F17/14 

1

Изобретение относится к вычислительной технике и может быть использовано при построении устройств, реализующих алгоритм быстрого преобразования Фурье (БПФ).

Цель изобретения - повышение быстродействия устройства для быстрого преобразования Фурье,

На фиг. 1 изображена функциональная схема устройства для быст рого преобразования Фурье; на фиг, 2 - функциональная схема вычислительного модуля; на фиг. 3 - функциональная схема арифметического блока; на фиг, 4 - функциональная схема блока синхронизации; на фиг, 5 - граф алгоритма БПФ с однородной структурой на всех итетрациях; на фиг, 6 - временная диаграмма выпол

нения базовых операций алгоритма БПФ; 20 ,,.,К) будет выполнять базовые опе1

, . . V IN

рации с номерами (j-l) --j + i,

1, N7к

На первой итерации алгоритма БПФ

фиг, 7) из блока 6-1-6-К памяти вычислительных модулей считываются операнды на выходные шины. В с.оответна фиг, 7 - временная диаграмма работы блоков памяти.

Устройство (фиг, 1) содержит вы- числительйые модули 1.-1,К,

Вычислительный модуль (фиг, 2) со- по управляющему сигналу считывания держит блок 2 синхронизации, коммута- от блока 2 управления (сигнал 65 на торы 3-1 - 3-К, арифметический блок 4, блоки 5 постоянной памяти, блоки 6, 1-6,К, 7,1-7.К памяти.

Арифметический блок (фиг, 3) со- 30 ствии со связями между вычислитель- держит регистры 8-15, блоки 16-18 пе- ными модулями 1-14-1-К, приведенными ремножения, блоки 19-22 суммирования, на фиг, 1, на входы j-ro вычислитель- блок 23 перемножения, блоки 24-27 ного модуля 1-j (,2,..,,К) при суммирования, регистры 28-35, этом по К шинам поступают К операнБлок 2 (фиг. 4) содержит элементы 35 яов из блоков 6-j памяти всех К вы- И 36-1-36-k, счетчик 37 адресов весо- числительных модулей, которые далее вых коэффициентов, элементы И 38 и 39, элемент НЕ 40, элементы И 41-1- -41-К, элемент ИЛИ 42, элементы И 43- -1-43-(т-1), элементы И 44-1-44-К, элементы И 45-1-45-К, элементы И 46- -1-46-К, дешифратор 47, D-триггер

пропускаются через коммутаторы 3-14- -3-К на входы арифметического блока 4 для выполнения базовой операции 40 алгоритма БПФ,

Арифметический блок 4, реализующий вычисления базовой операции алгоритма БПФ с основанием К, может строиться по любой из известных схем.

48, дешифратор 49, D-триггеры 50-1- -50-К, дешифратор 51, элемент НЕ 52,

счетчик 53 отсчетов, счетчик 54 ите- 45 Вариант построения арифметического

раций, сигналы 55-68 на выходах соответствующих блоков.

Устройство быстрого преобразования Фурье работает следующим образом.

Перед началом вычислений отсчеты входного сигнала (9), ,2,,.,,N-1, распределены последовательно группами по N/K отсчетов в блоки 6-1-6 К памяти всех вычислительных модулей так, что в i-M блоке памяти 6-i j-ro вычислительного модуля 1-i находятся N/K отсчетов входного сигнала с номерами

s (j-i)

+ |т(1-1) +Р.

i,j 1,Р; Р L, N/K

Устройство реализует вычисление по алгоритму БПФ основания К с однородной структурой, у которого адресация записи и считывания обрабатываемой информации не зависит от номера итерации (см, на фиг, 5 граф алгоритма БПФ с однородной структурой для , ), Вследствие однородности графа алгоритма БПФ связи между вычислительными блоками остаются фиксированными в процессе вычислений. Если пронумеровать базовые операции у графа алгоритма БПФ сверху вниз (фиг. 5), то j-й вычислительный модуль t-j (,2,.,.

1

, . . V IN

рации с номерами (j-l) --j + i,

1, N7к

На первой итерации алгоритма БПФ

фиг, 7) из блока 6-1-6-К памяти вычислительных модулей считываются операнды на выходные шины. В с.оответпо управляющему сигналу считывания от блока 2 управления (сигнал 65 на

35 яов из блоков 6-j памяти всех К вы- числительных модулей, которые далее

пропускаются через коммутаторы 3-14- -3-К на входы арифметического блока 4 для выполнения базовой операции 40 алгоритма БПФ,

Арифметический блок 4, реализующи вычисления базовой операции алгоритма БПФ с основанием К, может строиться по любой из известных схем.

блока 4 для показан на фиг, 3,

Регистры 8-15 арифметического блока 4 предназначены для приема и хранения входных операндов, поступающих

50 из блоков памяти для выполнения базовых операций алгоритма БПФ. Группы регистров 8-11 и 12-15 находятся в зависимости от номера выполняемой базовой операции поочередно в режимах

55 записи и хранения информации. Так, если для выполнения i-й базовой операции входные операции записываются в регистры 8-11 по управляющему сигналу записи от блоха 2 (сигнал 55 на

3-13

фиг. 6), то на следующем такте считывания информации из блоков памяти вычислительных модулей группа входных операндов для выполнения (i+0-й операции запишется в регистры 12-15 (по управляющему сигналу 56 на фиг. 6), а в это время регистры 8-11 используются для формирования результата i-й базовой операции. Затем для формирования результата (1+1)-й базовой операции используется содержимое регистров 12-15, а очередная группа входных операндов для выполнения (1+2)-й базовой операции записывается в регистры 8-11 и т.д.

При выполнении базовой операции алгоритма БПФ умножение входных о пе- рандов на весовые коэффициенты вида

W ехр (-1 -1), где I Гч, производится йа блоках 16-18 перемножения. Соответствующие значения весовых коэффициентов поступают из постоянного запоминающего устройства.

Блок 23 перемножения выполняет умножение на фиксированное значение мм

W

N -I И может быть реализован на

основе коммутаторов и инверторов. Суммарно-разностные операции выполняются на блоках 19-22, 24-27 сумми- рования.

Результаты базовых операций, формируемые на выходах блоков 24-27 суммирования, записываются поочередно в группы регистров 28-31 (по уп- равляющему сигналу 58 на фиг. 6) или в группы регистров 32-35 (соответственно по управляющему сигналу 59 на фиг. 6). Если результаты произвольной (1-1)-й базовой операции за- писываются в регистры 28-31, то на следующем такте производится перезапись их содержимого в блоки памяти вычислительного модуля, а в это время результаты следующей i-й базовой операции записываются в регистры 32- 35. Затем выполняется перезапись в блок памяти содержимого регистров 32 35, а в регистры 28-31 записываются результаты (+1)-й базовой операции и т.д.

При выполнении перезаписи результатов базовых операций в блоки памяти из группы регистров 28-31 или 32- 35 по одной общей щине (фиг. 3) по- очередно выход одного из регистров переводится из третьего состояния на момент записи его содержимого в блоки памяти. На фиг. 6 позициями 60-1

5

0

0 5 0

5

344

-60-4 обозначены управляющие сигналы последовательного перевода из третьего состояния выходов регистров 28-31, а позициями 61-1-61-4 - соответственно управляющие сигналы последовательного перевода из третьего состояния выходов регистров 32-35.

Согласно временной диаграмме выполнения базовых операций алгоритма БПФ конвейерного режима обработки информации одновременно производится запись входных операндов в регистры 8-11 или в регистры 12-15 дпя выполнения произвольной j-й базовой операции, вычисление (з-1)-й базовой операции с последующим запоминанием результатов вычислений в регистрах 28-31 или в регистрах 32-35 и запись в блоки памяти результатов (-2)-й базовой операции. Поскольку за время выполнения произвольной базовой операции (на фиг. 6 позицией 57 обозначены временные интервалы, затрачиваемые арифметическим блоком 4 на формирование результатов базовой операции) в блоки 7-14-7-К памяти записывается К операндов, а из блоков 6-1-6-К памяти вычислительных модулей 1-1-1-К считывается для выполнения следующей базовой операции лишь по одному операнду, то, следовательно, темп записи результатов вычислений, поступающих по одной щине в блоки 7-1-7-К памяти в К раз выше, чем темп считывания информации операндов в арифметический блок 4 из блоков 6-1-6-К памяти. На фиг. 6 позициями 62 и 63 обозначены соответственно частота записи и частота считывания информации из блоков памяти вычислительных модулей. Из-за начальной задержки конвейерной обработки информации, реализуемой в вычислительных модулях, начало записи в блоки памяти результатов вычислений задержано относительно начала считывания в арифметический блок входных операндов на 2Т, где Т - период считывания информации из блоков памяти, что, в свою очередь, эквивалентно задержке 2К периодов записи информации в блоках памяти. По этой причине на фиг. 7 управляющие сигналы записи 66-1-66 в блок памяти 7-1- -7-40К 4). сдвинуты на 8 периодов записи относительно управляющего сигнала 65 считывания из блоков 6-1-6-4 памяти. Результаты вычислений первой итерации алгоритма БПФ записываются

5

/ 5

последовательно по N/K операндов в блоки памяти вычислительных блоков J, первые N/K операндов записываются в блоки 7-1 памяти, следующие N/K операндов - блоки 7-2 памяти и т.д. При такой организации записи результатов вычислений в каждом блоке 7-i памяти j-ro вычислительного модуля 1-J (i,,2.,.,К) запоминаются операнды, которые, как следует из приведенных на фиг. 1 связей между вычислительными модулями, будут использоваться на следующем этапе вычислений в i-м вычислительном модуле -i по j-й входной шине. Это позволяет при выполнении следующей итерации алгорит;ма БПФ реализовать одновременное поступление операндов по всем К входным шинам вычислительных модулей и снизить в К раз темп обмена информацией между вычислительными модулями по сравнению с темпом записи из арифметического блока 4 в блоки памяти, осуществляемой по одной шине внутри вычислительных модулей.

Разная скорость следования информации внутри и между вычислительными модулями хорошо -согласуется с конструктивным построением аппаратуры. Поскольку информационные шины, свя- зываюшле вычислительные модули, обыно имеют существенно большую , чем шины внутри блоков, то соответственно темп следования информации внутри вычислительных блоков может быть значительно выше, чем темп обмена информацией между вычислительными модулями„

На второй итерации алгоритма БПФ производится считывания операндов из блоков 7-1-7-К памяти вычислителных модулей, а запись результатов вычислений - в блоки 6-1-6-К памяти (на фиг. 7 позицией 67 обозначен

управляюший сигнал считывания инфор- 45 итерации,

мации из вычислительных модулей 7-1- -7-К, а позициями 68-1-68-4 - управляющие сигналы записи информации в блоки 68-1-68-К памяти для .Чередование релшмов записи считывания блоков 6-1-6-К,7-1-7-К памяти выполняется и на последующих итерациях.

Окончательный результат - N коэффициентов дискретного преобразования Фурье входного сигнала записываются в блоки памяти вычислительных модулей после n/k итераций алгоритма БПФ.

Для выполнения вычислений по алгоритму БПФ в блок 5 постоянной па

5

0

мяти каждого вычислительного модуля записывается матрица весовых коэффициентов W, где W ;5-l. При

выполнении любой базовой операции из блока 5 постоянной памяти считывается строка матрицы W. Порядок адресов считывания строк матрицы в соответствии с алгоритмом БПФ формируется на выходах элементов И 36-1-36-k и счетчика 37 адресов весовых коэффициентов . Из алгоритма БПФ основания К с нормальным порядком входных отсчетов и двоично-инверсным порядком выходных отсчетов следует, что на произвольной i-й итерации базовые операции можно разбить на групп так, что в каждой из групп базовые операции имеют одни и те же значения весовых множителей.

Порядок следоваргия весовых, коэффициентов на любой итерации подчиняется правилу двоичной инверсии (см. фиг. 5 для ), Для фор5 мирования адресов строк матрицы весовых коэффициенто в соответствии с этим правилом используются сигналы разрядов счетчика 37 и сигналы с выходов элементов И 36-1-36-k при0 чем сигнал i-ro разряда счетчика 37 адресов весовых коэффициентов (, 2,.,.,n-2k) используется в качестве (n-k+l-i)-ro разряда адреса строки матрицы W, а в j-ro разряг да адреса строки матрицы W (j,2, , , . ,k) - сигнал с -j-ro элемента В 36-J.

Формирование адресов строк матрицы весовых коэффициентов W в зависи0 мости от номера итерации алгоритма БПФ управляется дешифратором 47, который вырабатывает ;я на своем i-м выходе (i 1, 2 3 . . , ,1п) логический уровень 1 на время прохождения i-й

Из алгоритма БПФ следует, что на (1,2,. , . ,т-1 )-й итеграции во всех вычислительных модулях одновременно выполняются базовые операции с одинаковыми весовыми 1-1Ножителями, а на т-й итерации в вычислительных модулях для выполнения базовых операций использ-уются разны(г группы весовых множителей. Для реализации считываВИЯ на т-й итерации в вычислительных модулях различных групп весовых коэффициентов, зависящих от номера вычислительного модуля, используются элементы И 36-1-36-k, на первые вхо7

ды которых подается сигнал с .т-го выхода дешифратора 47, а на второй вход i-го элемента И (,2,,,,,т) 36-1 подается (К+1-1)-й разряд двоичного хода, соответствующего номеру вычислительного модуля. Так, первому вычислительному модулю 11-12 соответствует двоичный код 000...00, второму вычислительному модулю 1-2 - двоичный код 000...00 и т.д. На т-й итерации сигнал с т-го выхода дешифратора 47 имеет логический уровень 1, и на выходы элементов И 36-1- -36-k пропускаются двоичные коды номеров вычислительных модулей. На ос- )5 тывания операндов в К раз меньше.

тальных (1,2,,..,ml)-х итерациях с т-го выхода дешифратора 47 на первые входы элементов И 36-1-36 поступает логический уровень О. При этом выходы элементов И 36-1-36-k находятся в нулевом состоянии и во всех вычислительных модулях из блоков постоянной памяти считываются одинаковые значения весовых коэффициентов. Для считывания в необходимом порядке в соответствии с алгоритмом БПФ строк матрицы W используются разряды счетчика 37. Перед началом вычислений каждой итерации алгоритма БПФ счетчик 37 адресов весовых коэффициентов устанавливается в jнулевое состояние. На 1-й итерации алгоритма БПФ счетчик 37 адресов весовых коэффициентов не изменяет своего состояния, поскольку на его счет- НЕ 40.

ном входе присутствует логический Для формирования управляющих им- 0. При этом для выполнения базо- пульсов записи в блоки 6-1-6-К па- вых операций во всех вычислительных мяти входы элементов И 44-1-44-К модулей используется строка матрицы подаются сигналы соответственно с весовых коэффициентов W. Во время выпол-.0 (l-K)-ro выхода дешифратора 49, а

нения 2-й итерации алгоритма БПФ на счетный вход счетчика адресов весовых коэффициентов 37 через элемент И 43-1 и элемент ИЛИ 42 пропускается

также сигнал с выхода 1-го разряда счетчика 53 отсчетов и сигнал 1-го разряда счетчика 54 итераций. Выходные сигналы дешифратора 49 пред- сигнал с (n-2k+)-ro разряда счетчи- 45 ставляют собой последовательно сдви- ка 53 отсчетов. В результате на 2-й нутые импульсы 1-го разряда счетчика итерации счетчик 37 адресов весовых отсчетов. Для их формирования на вхо- коэффициентов изменит свое состояние ды дешифратора 49 подаются сигналы К раз и сформируется К адресов строк (n-2k+l) - (n-k)-ro разряда счетчика весовых коэффициентов для выполнения 50 отсчетов. На выходах элементов И44-1-44-К при этом формируются управляющие сигналы записи (на фиг. 7 для - сигналы 66-1-66-4). Сдвиг начала записи в блоки 6-1-6-К памяти адресов весовых коэффициентов 37 про- 55 относительно начала считывания ин- пускается через элемент И (43-1-1) формации из блоков 7-1-7-К памяти на и элемент ИЛИ 42 сигнала с (n-ik+l)-ro задержку конвейера выполняется путем разряда счетчика отсчетов.соответствующего сдвига сигналов с

К групп базовых операций.

Аналогично для считывания на i-й итерации (,3,, .. ,т-О К строк матрицы W на счетный вход счетчика

3040348

Управление вычислительным процессом осуществляется по сигналам от блока 2 синхронизации. Все управляющие сигналы от блока 2 можно разбить с на две группы: сигналы управления выполнением базовых операций алгоритма БПФ в арифметическом блоке 4 (фиг. 6) и сигналы управления режимами записи-считывания блоком памяти (фиг. 7), to Считывание информации из блоков 6-1-6-К и 7-1-7-К памяти для выполнения базовых операций осуществляется соответственно по сигналам 65 и 67 (см. фиг. 7). Поскольку частота счичем частота записи, то для формирования импульсов записи в блоки памяти используется сигнал с 1-го разряда счетчика 53 отсчетов, а для формирования сигнала считывания - сигнал с (k-H)-ro разряда счетчика 53 отсчетов, где ,K. При формировании управляющего сигнала считывания из блоков 7-1-7-К памяти сигнал (k+l)-ro

разряда счетчика 53 отсчетов селектируется на элементе И 38 сигналом 1-го разряда счетчика 54 итераций, а для считывания из блоков 6-1-6-К памяти соответствующий управляющий

сигнал образуется путем селекции на элементе И 39 сигнала (k+l)-ro разряда счетчика 53 отсчетов инверсным сигналом 1-го разряда счетчика итераций, nocTynammjiM с выхода элемента

выхода дешифратора 49 на В-тригге pax и сигнала 1-го разряда счетчика итераций на-В триггере 48. При этом в качестве сдвигающих импульсов, подаваемых на С-входы D- триггеров 48,50-1-50-К, используется сигнал с (k+2)-ro разряда счетчика 53 отсчетов, за счет чего обеспечивается задержка на два интервала считывания из блоков памяти,

Формирование управляющих импульсов записи в блоки 7-1-7-К памяти осуществляется аналогичным образом на элементах И , подается сдинутый на начальную задержку кон- вейера инвертированный сигнал 1-го разряда счетчика 54 итераций с инверсного выхода D-триггера 48,

В качестве управляющего сигнала записи входных операндов в регистры В- и сигнала записи результатов выполнения базовой операции алгоритма БПФ в регистры 28-31 (на фиг, б соответственно сигналы 55 и 58) используется сигнал с выхода злемента И 46-К (), на вход которого подается сигнал с К-го выхода дешифратора 31 и проинвертированный сигнал (k+1) ГО разряда счетчика отсчетов, поступающий с выхода злемента НЕ 52, Аналогично в качестве сигналов записи информации в регистры 1215 и 32-35 (па фиг; 6 соответственно сигналы 56 и 59) используют сиг- нал с выхода элемента И 41-К, на входы которого подается сигнал с К-го выхода дешифратора 51 и непосредственно сигнал с выхода (k+l)-ro разряда счетчика 53 отсчетов.

Для управления последовательной перезаписью результатов базовой операции из регистров 28-31 блоки памяти (сигналы 60-1-60-4 на фиг, 6 для ) используются сигналы с выходов .дешифратора 51, которые селек- тируются проинвертированным на элементе НЕ 52 сигналом (К+1)-го разряда счетчика 53 отсчетов на элементах И 46-1-46-К. При формировании управляющих сигналов перезаписи инфор- мации из регистров 32-35 в блоки памяти (соответственно сигналы 6-1-61на фиг. 6) сигналы с выходов дешифратора 51 селектируются сигналом с (k+1)-го разряда счетчика 53 отсче- тов.

Наличие коммутаторов 3-1-3-К (фиг, 2) позволяет выполнять автономно каждому вычислительному модулю 1(,2,..,,К) БПФ размером N/K. В режиме автономной работы в каждом вычислительном модуле 1-i (,2,,.,,К коммутаторы 3-1-3-К пропускают сигналы с выходов внутренних блоков памяти на входы арифметического блока 4, и отсутствует обмен информацией межд вычислительными модулями 1-1-1-К. Пр этом описанное управление вычислительным процессом, рассчитанное на выполнение всем многопроцессорным устройством БПФ размером N, полность соответствует выполнению каждым вычислительным модулем в режиме автононой работы БПФ размером М,

Формула изобретения

1, Устройство для быстрого преобразования Фурье, содержащее К-2 ( - размер преобразования устройства) вычислительных модулей, каждый из которых содержит арифметический блок и четыре блока памяти, отличающее ся тем, что, с целью повыщения быстродействия, в каждый вычислительный модуль введены К коммутаторов, 2К-4 блоков памяти, блок синхронизации и блок постоянной памяти, причем информационные входы первой группы i-ro (i,K) коммутатора являются входами i-й группы вычислительного модуля, а выходы группы i-ro коммутатора подключены к соответствующим входам i-ro операнда арифметического блока, управляющие входы коммутаторов объединены и подключены к выходам первой группы блока синхронизации, входы группы весовых коэффициентов арифметического блока подключены к соответствующим выходам группы блока по стоянной памяти, адресные вхэды группы которого подключены к соответствующим выхо- дам второй группы блока синхронизации, информа дионные входы группы 2К блоков памяти объадинены и подключен к соответствующим информационным выходам группы арифметического блока, информационнз е выходы группы i-ro и (i+K)-ro блоков памяти объединены и подключены к соответствующим информационным входам второй группы i-ro коммутатора и являются выходами i-ой группы вычислительного модуля, управляющие входы груп;аы блоков памяти подключены к соотзетствующим выходам третьей группы блока синхронизации, входы блоков синхронизации группы

всех вычислительных модулей соответственно объединены и являются тактовыми входами труппы устройства, выходы и-ой группы V-ro вычислительно- го модуля (U,,К) подключены к соответствующим входам V-й группы U-ro вычислительного модуля.

товым входом блока, С-входы (K+1)D- триггеров объединены и подключены к выходу (k+2)-ro разряда счетчика j отсчетов, (с-й() подключен к 5 выходу (n-2k+t)-ro разряда счетчика отсчетов , t-й выход второго дешиф- ратора подключен к D-входу t-ro D-триггера, выход которого подключен к вторым входам (m+k+t-0 ro и (т+К+ +k+t-l)-ro элементов И, выходы которых являются соответственно выходами третьей группы блока, а третьи входы (m-f-k-l)-ro и (m+K+k+t-1 )-го элементов И подключены к выходу первого разряда счетчика отсчетов, первые входы m+K+t-1 элементов И подключены к выходу (К+1)-го D-триггера первые входы (m+K+k+t-l)-x элементов И подключены к инверсному выходу

10

2, Устройство по п. 1, отличающееся тем, что блок синхронизации содержит (4K+ra+k+l) элементов И, (,,K, , n log2N, N - размер преобразования вычислительного блока, элемент ИЛИ, два элемента НЕ, три дешифратора, K+1+D- f5 триггеров, счетчик отсчетов, счетчик итераций и счетчик адресов весовых коэффициентов, причем j-й (,p, ,,,m) вход первого дешифратора подключен к выходу j-ro разряда счет-20 (К+1)-го D-триггера, D-вход которого чика итераций, счетный вход которого подключен к 1-му разряду счетчика подключен к выходу переполнения счет- итераций, выходы (m+k+2K)-ro и (m+k+ чика отсчетов, (S+1)-й выход первого +2К+1)-го элементов И подключены к

(k+l)-My разряду счетчика отсчетов, 25 второй вход (m+k+2K+1)-го элемента И подключен к выходу первого элемента НЕ, вход которого объединен с вторым входом (m+k+2K)-ro элемента И и подключен к выходу первого разряда 30 счетчика итераций, t-й вход третьего дешифратора подключен к выходу t-ro

дешифратора (,т-1) подключен к первому входу S-ro элемента И, выход которого подключен к S-му входу элемента ИЛИ, выход которого подключен к счетному входу счетчика адресов весовых коэффициентов, выходы разрядов которого являются соответствующими выходами первой группы блока,второй вход q-ro элемента И (q разряда счетчика отсчетов, t-й выход 1,т-2) подключен к входу (n-(q+l)K+третьего дешифратора подключен к вто- +)-го разряда счетчика отсчетов,рым входам (m+k+2K+t+l)-ro и (m+k+ второй вход (т-1)-го элемента И под-35 -3K+t+I)-ro элементов И, выходы кото- ключен к входу k-ro разряда счетчикарых являются выходами третьей группы отсчетов, первые входы (т+1-1)-х элементов И (,k) объединены и подключены к т-му выходу первого дешифратора, а выходы (m-I-l)-x элементов40 динен с первыми входами (m+k+3K-i-t+ И являются соответствующими выходами+1)-х элементов И и подключен к выблока, первые входы (m+k+2K+t+l)-x элементов И подключены к выходу второго элемента НЕ, вход,которого объевторой группы блока, второй вход (т+1-1)-го элемента И является так товым входом блока, С-входы (K+1)D- триггеров объединены и подключены к выходу (k+2)-ro разряда счетчика j отсчетов, (с-й() подключен к 5 выходу (n-2k+t)-ro разряда счетчика отсчетов , t-й выход второго дешиф- ратора подключен к D-входу t-ro D-триггера, выход которого подключен к вторым входам (m+k+t-0 ro и (т+К+ +k+t-l)-ro элементов И, выходы которых являются соответственно выходами третьей группы блока, а третьи входы (m-f-k-l)-ro и (m+K+k+t-1 )-го элементов И подключены к выходу первого разряда счетчика отсчетов, первые входы m+K+t-1 элементов И подключены к выходу (К+1)-го D-триггера, первые входы (m+K+k+t-l)-x элементов И подключены к инверсному выходу

0

5 0 (К+1)-го D-триггера, D-вход которого подключен к 1-му разряду счетчика итераций, выходы (m+k+2K)-ro и (m+k+ +2К+1)-го элементов И подключены к

разряда счетчика отсчетов, t-й выход третьего дешифратора подключен к вто- рым входам (m+k+2K+t+l)-ro и (m+k+ -3K+t+I)-ro элементов И, выходы кото- рых являются выходами третьей группы динен с первыми входами (m+k+3K-i-t+ +1)-х элементов И и подключен к выблока, первые входы (m+k+2K+t+l)-x элементов И подключены к выходу второго элемента НЕ, вход,которого объеходу (К+1)-го разряда счетчика отсчетов ,

Изобретение относится к вычислительной технике и может быть использовано при построении устройств, реализующих алгоритм быстрого преобразования Фурье. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что устройство содержит вычислительные модули 1, каждый из которых со- держит блок синхронизации 2, коммутаторы 3-1-3-К, арифметический блок 4, блоки поС Тоянной памяти 5, блок па-: мяти 6-1-6-К, 7-1-7 К. 1 з.п. ф-лы, 7 ил. (Л оо о 4 О ОО 4

i2 i(

От г

шиг.

От г

Временной диаграмма дытлне я 6ajo56/jf о/герации алгоритма бПФ I Запись 8 рег1/стры(8}-{Т11 Sjfodmx Запись S регистрб1 г2)) onepoHdoSi-u дазоёой олге/кгции anepaHdoSfH)-i} дахбой а/ге/юции

51

58

jg.

письКОЗУизрегистро5(зг)(35} 3олис1, В ОЗУ из рег1/стро8(28}-(ЗП I К резуль оВ(1-2}-идозоВойonepff- езуль/пато {(-1)-иSajoSovаг7ерац(/и

бВ-З 60-1

В1-1 61-2V

;-4|6t - I rfJL

«

V ( «4,

§ 1

Составитель A, Баранов Редактор E, Копча Техред В.КадарКорректор М. Пожо

Заказ 1313/50 Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

N.