Процессор быстрого преобразования фурье

 

Изобретение относится к вычислительной технике и может быть использовано для цифровой обработки сигналов и спектрального анализа. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят арифметический блок 1, коммутатор данных 2, блок управления 3, коммутатор управления 4, формирователи адреса 5 - 7, блок 8 буферных регистров, коммутатор констант 9, блоки памяти 10 - 12, блок 13 постоянной памяти, элемент НЕ 14, регистры 15 - 26. 7 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ф

l с (21) 4496646/24 (22) 20.10.88 (46) 30.07.91. Бюл. N. 28 (71) Институт кибернетики с вычислительн ым центром Научно-и роизводствен ного объединения "Кибернетика" АН УЗССР (72) С,Г.Поваренкин и Т.M.Ìàãðóïoa (53) 681,32 (088,8) (56) Авторское свидетельство СССР

М 1119027, кл. G 06 F 15/332, 1984.

Авторское свидетельство СССР

М 1086438, кл. G 06 F 15/332, 1984., Ы,, 1667101 А1 (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано для цифровой обработки сигналов и спектрального анализа. Цель изобретения — повышение быстродействия. Поставленная цель достигается за счет toro, что в состав устройства входят арифметический блок 1, коммутатор 2 данных, блок 3 управления, коммутатор 4. управления, формирователи

5 — 7 адреса, блок 8 буферных регистров, коммутатор 9 констант, бЛоки 10 — 12 памяти, блок 13 постоянной памяти, элемент НЕ 14, регистры 15 — 26. 7 ил.

1667101

Изобретение относится к вычислительной технике и может быть использовано для решения задач цифровой обработки сигналов и спектрального анализа.

Цель изобретения — повышение быстродействия прОцессора.

На фиг.1 представлена схема процессо ра БПФ; на фиг,2 — схема арифметического блока; на фиг.3 — схема коммутатора данных

,(пример реализации); на фиг.4 — функцио, нальная схема блока управления; на фиг.5—, функциональная схема коммутатора управ ления; на фиг.б и 7 — функциональные схемы, формирователей адреса 5 и 6 соответственI HO

Процессор БПФ (фиг,1) содержит ариф метический блок 1, коммутатор 2 данных, блок 3 управления, коммутатор 4 управления, формирователи 5 — 7 адреса, блок 8 бу ферных регистров, коммутатор 9 констант, блоки 10-12 памяти, блок 13 постоянной

1 памяти, элемент НЕ 14, регистры 15-26, Арифметический блок 1 (фиг.2) содержит первый 27 и второй 28 конвейерные умножители, сумматор-вычитатель 29, сумматор 30, вычитатель 31, линию 32 задержки, мультиплексор 33 арифметического

:блока, первый 34, второй 35 и третий 36 регистры арифметического блока.

Коммутатор 2 данных (фиг.3) содержит первый 37, второй 38, третий 39, четвергый 40 и пятый 41 мультиплексоры коммутатора ,данных.

Блок 3 управления (фиг,4) содержит первый 42, второй 43, третий 44, четвертый 45, и пятый 46 счетчики, тактовый генератор 47, первый 48, второй 49 и третий 50 регистры сдвига; формирователь 51 сигналов управления, первую 52 и вторую 53 линии задержки, первый 54, второй 55 и третий 56 триггеры; первый 57, второй 58, третий 59, четвертый 60 и пятый 61 элементы ИЛИ; элемент И 62; элемент И вЂ” НЕ 63, первый 64, второй 65, третий 66 и четвертый 67 формирователи кода. Кроме того, на фиг,4 обозначены информационный выход 43о и выход

431 переноса счетчика 43, информационный выход 45о счетчика 45, выход 46о переноса счетчика 46, выход 47о тактового генератора

47, выход 49о регистра 49 сдвига, первый

50о, второй 50> и третий 50z выходы регистра 50 сдвига, выход 53о линии 53 задержки, выход 55о триггера 55, выход 56о триггера

56, выход 63о элемента И-НЕ 63, Коммутатор 4 управления (фиг.5) содержит муЛьтиплексоры 68 — 76.

Формирователь адреса 5 (фиг.б) содержит мультиплексоры 77 числом, нэ единицу меньшим числа разрядов информационного выхода счетчика 42 блока 3 управления (фиг,4).

Формирователь адреса 6 (фиг.7) содержит мультиплексоры 78 по числу разрядов информационного выхода счетчика 42 блока

3 управления (фиг.4) и элемент НЕ 79, Устройство работает следующим образом, Процессы вычисления коэффициентов

Фурье, вывода вычисленной последовательности коэффициентов Фурье и ввода последовательности подлежащих обработке входных данных совмещены во времени.

При этом один из блоков 10 — 12 памяти (фиг,1) является источником входных операндов арифметического блока 1 (т.е. результатов предыдущей итерации БПФ или введенных извне подлежащих обработке данных), другой блок памяти является приемником выходных операндов блока 1 (т,е. результатов текущей итерации БПФ), à оставшийся блок памяти обеспечивает вывод вычисленных коэффициентов Фурье и ввод новой последовательности исходных данных для обработки.

Коммутатор 2 дает возможность коммутировать выходы любого из блоков 10 — 12 памяти на информационные входы регистров 15, 16, 24 и 25, являющихся фиксаторами входных операндов арифметического блока; коммутировать выходы любого из блоков 10-12 на информационные входы регистров 19 и 20, являющихся фиксаторами выходных данных процессора, а также коммутировать выходы блока 8 и информационные входы процессора на информационные входы любого из блоков 10 — 12 памяти.

Таким образом, коммутатор 2 данных позволяет коммутировать блоки 10-12 памяти так, что любой из блоков 10-12 может быть источником входных операндов блока

1, приемником выходных операндов блока 1 или осуществлять ввод-вывод данных. По окончании некоторой итерации БПФ, если только она не последняя, блок памяти — приемник выходных операндов блока 1, перекоMмутируется так, что становится источником входных операндов блока 1, а блок памяти — источник операндов перекоммутируется так, что становится приемником операндов. Если завершенная итерация является последней в БПФ, то блок памяти— приемник выходных операндов блока 1 переключается на ввод-вывод, блок памяти, осуществлявший ввод-вывод, становится источником входных операндов блока 1, блок памяти — источник операндов становится приемником выходных операндов блока 1, 1667101

10 ное поле перемычек) 15

25

50

Арифметический блок 1 реализует выполнение базовой операции алгоритма

БПФ. Блок 13 хранит весовые коэффициенты, необходимые для вычисления коэффициентов Фурье, Коммутатор 9 коммутирует реальную и мнимую части весовых коэффициентов во время работы процессора. Формирователи 5-7 адреса реализуют необходимый для выполнения БПФ алгоритм адресации блока 13, блока памяти— источника входных операндов арифметического блока 1, и блока памяти — приемника выходных операндов блока 1 соответственно.

Коммутатор 4 предназначен для коммутации адреса и сигналов управления блоков

10 — 12 памяти. Это необходимо, поскольку в процессе работы каждый из блоков 10-12 может быть источником входных операндов блока 1, приемником выходных операндов блока 1 или осуществлять ввод-вывод, и алгоритм их адресации и управления соответственно меняется.

Блок 3 управления управляет работой арифметического блока 1, коммутатора 2 данных, коммутатора 4, коммутатора 9, блока 8, осуществляет счет операндов арифметического блока 1 и счет итераций БПФ и подает код номера операнда на входы формирователей 5 — 7 и код номера итерации на входы формирователей 5 и 6 (на основе этих кодов формируются адреса для блока 13 и блоков памяти — источника и приемника операндов блока 1); осуществляет счет и синхронизацию данных ввода-вывода и адресацию блока памяти, осуществляющего ввод-вывод; формирует сигналы управления блоками 10-12 памяти; формирует сигналы синхронизации арифметического блока 1, блока 8, регистров 15-26.

Блок 8 буферных регистров и регистры

15 — 26 предназначены для буферизации данных и адресов и обеспечивают конвейеризацию работы процессора, Элемент НЕ

14 предназначен для формирования сигнала синхронизации регистров 24 — 26 в противофазе с синхронизацией регистров 15 и 16.

Тактовый генератор 47 (фиг.4), входящий в состав блока 3, синхронизирует работу блока 3 и основных блоков всего процессора, т.е. синхронизирует работу регистров 17 и 18 (фиг,1), арифметического блока 1, блока 8, тех иэ регистров 21 — 23, в которых буферизуется адрес тех из блоков памяти 10-12, которые в данном БПФ являются источником входных операндов и приемником выходных операндов арифметического блока 1.

В дальнейшем один период выходного сигнала генератора 47 будем называть тактом работы процессора или просто тактом.

Счетчик 42 осуществляет счет операндов в пределах одной итерации БПФ, а счетчик 44 — число итераций БПФ. Число состояний счетчиков 42 и 44 равно соответственно длине обрабатываемой последовательности входных данных процессора и числу итераций БПФ и определяется кодом, поступающим на информационные входы этих счетчиков с выходов формирователей соответственно 64 и 65(в качестве формирователей 64-67 может использоваться наборСчетчик 45 необходим для управления коммутаторами 2 и 4 процессора (фиг.1) при окончании вычисления коэффициентов

Фурье для одной последовательности входных данных процессора и переходе к обработке следующей введенной последовательности входных данных.

Число состояний счетчика 45 (фиг.4) определяется поступающим на его информационные входы кодом с выхода формирователя бб и равно двум для четного числа итераций БПФ и трем для нечетного числа итераций. Регистр 48 сдвига на своем втором выходе задерживает сигнал переноса счетчика 42 на величину, равную начальной задер>кке конвейера вычислений, т.е. на время разгона конвейера — время с момента начала итерации, необходимое для того, чтобы первые результаты вычислений попали в блок памяти — приемник выходных операндов арифметического блока 1 (фиг.1).

Поскольку второй выход регистра 48 сдвига (фиг.4) через элемент ИЛИ 57 связан с входом разрешения записи счетчика 42, то число состояний пары счетчик 42 — регистр

48 сдвига равно (N+d), где N — длина последовательности входных данных (т.е. размерность БПФ); d — начальная задержка конвейера, выраженная в тактах работы процессора. Таким образом, время цикла работы пары счетчик 42 — регистр 48 соответствует длительности одной итерации

БПФ, которая исчисляется с момента подачи адреса на адресный вход блока памяти — источника входных операндов до момента приема последних выходных операндов арифметического блока 1 блоко л памяти— приемником операндов.

Первый выход регистра 48 задерживает сигнал переноса счетчика 42 на один такт меньше, чем второй выход. Поскольку сигнал с первого выхода регистра 48 разрешает счет счетчика 44, этот счетчик в процессе работы переключается на один такт раньше, чем срабатывает в режиме записи счетчик

1667101

20

30 N+ б п

42. Это обусловлено необходимостью буферизации для повышения быстродействия всех сигналов, в том числе и сигналов управления коммутаторами 2 и 4 (фиг,1), а также необходимостью опережающего изменения сигналов управления мультиплексорами 68, 69, 71, 72, 74 и 75 коммутатора 4 (фиг.5), коммутирующими адрес блоков 10 — 12, (фиг,1) и строб записи адреса в регистры 21 — 23. по отношению к изменению сигна,лов управления коммутатором 2 и мульти плексорами 70, 73 и 76 коммутатора 4 (фиг.5) при переходе от одной итерации БПЗ к следующей и от последней итерации теку, щего БПФ к первой итерации следующего

БПФ.

Указанное опережающее изменение, позволяет совместить во времени прием по, следних выходных операндов блока 1 (фиг,1)

;, в текущей итерации блоком памяти — прием, ником и подачу адреса первого входного ,,операнда блока 1 для следующей итерации, на информационный вход того из регистров, 21 — 23, который соответствует указанному блоку памяти — приемнику. Это позволяет, исключить потерю лишнего такта при пере ходе от одной итерации к следующей и, ана логично, при переходе от последней итерации текущего БПФ к первой итерации следующего БПФ.

Счетчик 43 блока 3 (фиг.4) осуществляет счет данных ввода-вывода и адресацию того из блоков 10-12 (фиг,1), который в текущем

БПФ реализует функцию ввода-вывода.

Число состояний .счетчика 43 (фиг,4) равно длине обрабатываемой последовательности входных данных, т,е. размерности БПФ.

Счетчик 46 делит частоту выходного сигнала генератора 47 на величину, равную где )А(—. наименьшее целое число, большее или равное А;

N — размерность БПФ;

d — число тактов начальной задержки конвейера;

m = logz N — число итераций алгоритма

БПФ.

Коэффициент деления, т.е, число состояний счетчика 46, определяется выходным кодом формирователя 67. Поскольку сигнал переноса счетчика 46 разрешает срабатывание счетчика 43 в режиме счета, та число состояний пары счетчик 46 — счетчик 43 не меньше величины(К+0) m, т.е, числа состояний системы счетчик 42 — регистр 48— счетчик 44, которое равно числу тактов работы процессора, необходимомудлл выпалнения одного БПФ, 35

Таким образом, при данной реализации блока 3 время ввода-вывода не меньше времени вычисления коэффициентов Фурье для одной последовательности входных данных и сигнал окончания ввода-вывода с выхода переноса счетчика 43, задержанный регистром 50 сдвига до. его выхода 50о, используется для переключения процессора на выполнение следующего БПФ, т.е. для разрешения переключения в режиме счета счетчика 45 и разрешения установки счетчиков 42 и 44 в режиме записи в исходное состояние, а сигнал переноса счетчика 43, задержанный до выхода 501 регистра 50— для начальной установки триггера 55 в состояние "1", которое разрешает работу счетчика 42 в режиме счета и, через один такт появившись на выходе триггера 56, разрешает формирование элементов И 62 импульсов записи в блок памяти — приемник выходных операндов арифметического блока 1 (фиг.1), По окончании вычисления текущей последовательности коэффициентов Фурье, т.е. по сигналу переноса счетчика 44 (фиг,4), . задержанного на один такт триггером 54, триггер 55 устанавливается в состояние "0" и блокирует работу в режиме счета счетчика

42 и через один такт блокирует формирование элементамИ 62 импульсов записи в блок памяти — приемник выходных операндов блока 1 (фиг.1), т.е. блокирует начало вычисления следующей последовательности коэффициен ros Фурье до окончания текущей операции ввода-вывода.

Формирователь 51 (фиг.4) предназначен для формирования сигналов управления коммутаторами 2 и 4 (фиг.1), а линии 52 и 53 задержки (фиг.4) задерживают эти сигналы на необходимое число тактов; линия 53 задерживает сигналы управления коммутатором 2 на два такта; линия 52 задерживает сигналы управления мультиплексорами 70, 73 и 76 коммутатора 4 (фиг.5) на два такта, а сигналы управления мультиплексорами 68, 69, 71, 72, 74 и 75 — на один такт.

Элемент ИЛИ 57 блока 3 (фиг.4) предназначен для трансляции на вход разрешения записи счетчика 42 сигналов с второго выхода регистра 48, с входа блока 3 и с выхода 50о регистра 50.

Элемент ИЛИ 58 предназначен для трансляции на вход разрешения записи счетчика 44 сигналов с его выхода переноса, с входа блока 3 и с выхода 50о регистра 50.

Элементы ИЛИ 59, 60 и 61 предназначены для трансляции на входы разрешения записи счетчиков соответственно 45, 46 и 43 сигналов с их выходов переноса и с входа блока 3 управления. Таким образом, в дан1667101.

10.

45 совместно с сигналами с информационного выхода счетчика 44 используются для управ-. ления формирователем 5 (фиг,1).

Арифметический блок 1 обеспечивает вычисление коэффициентов Фурье по базовым формулам алгоритма БПФ:

ReAi = ReAi-1 + (ReBi-1 . ReW — ImBi-i lmW), (1) ImAi = ImAi-1+ (ReBi ImW+ I Bi-) ЯеВ/), {2) ЯеВ = ReA;-1(йеВ;-1 ReW — вВ -1 lmW), (3) ImBi= ImAi-1 — (ReBi-t 1 дЯ+ I Bi-1 ReW, (4) 55 ной реализации блока 3 внешнее управляющее устройство имеет возможность установить все счетчики блока 3 в исходное состояние, подав сигнал логической "1" на управляющий вход процессора, т,е. на вход 5 блока 3 управления.

Сигналы с выходов 501 и 502 регистра 50 блока 3 (фиг.4), а также сигналы с выхода переноса счетчика 46 и с выхода регистра 49 используются для синхронизации входных 10 и выходных данных процессора. Сигнал с выхода регистра 49 сдвига используется, кроме того, для синхронизации региатров

19 и 20 (фиг,1), а также для управления записью того из блоков 10 — 12 памяти, который 15 реализует в данном БПФ функцию вводавывода. Таким образом, регистры 49 и 50 сдвига (фиг.4), задерживающие сигналы с выходов переноса счетчиков 46 и 43 соответственно, предназначены для формиро- 20 вания многофазных сигналов управления процессором.

Сигнал с выхода элемента 63 предназначен для синхронизации того из регистров

21 — 23 (фиг.1), в котором буфериэуется адрес 25 того из блоков 10-12 памяти, который в текущем БПФ реализует функцию ввода-вывода.

Сигнал с выхода младшего разряда счетчика 42 (фиг,4), который в каждом такте 30 работы процессора меняет свое значение на противоположное, предназначен для управления арифметическим блоком 1 (фиг.1), блоком 8, коммутатором 9, а также для синхронизации регистров 15 и 16 и через эле- 35 мент ИЕ 14 — для синхронизации регистра

26, Сигналы с информационного выхода счетчика 42 (фиг,4) используются для управления формирователем 7 (фиг.1), а совместно с сигналами с информационного выхода 40 счетчика 44 (фиг.4) — для управления формирователем 6 {фиг.1). Сигналы с информационного выхода счетчика 42 (фиг.4), эа исключением его выхода младшего разряда, где i — номер текущей итерации БПФ, i =

=0,1...(m — 1);

m = logz N (N — число элементов в обрабатываемой входной последовательности данных);

А,  — комплексные числа;

W —. комплексный весовой коэффициент;

ReA и 1п1А — соответственно реальная и мнимая части комплексного числа А, Пропускная способность блоков 10-12 памяти (фиг.1) такова, что за один такт работы процессора блок памяти — источник входных операндов арифметического блока 1, может выдать два операнда (реальную и мнимую части операнда А или реальную и мнимую части операнда В по выражениям (1}-(4)), а блок памяти — приемник выходных операндов блока 1, может принять два операнда (оставшийся блок памяти обслуживает on ерации ввода-вывода). Поэтому для достижения сбалансированности пропускной способности блоков 10 — 12 памяти и арифметического блока 1 структура последнего выбрана такой, чта для полной его занятости достаточно за один такт работы процессора загружать блок 1 из блока памяти — источника операндов через коммутатор

2, двумя входными операндами и реальной и мнимой частями весового коэффициента, при этом каждый такт с выходов блока 1 в блок 8 поступают два операнда, а с выходов блока 8 в блок памяти — приемник операндов через коммутатор 2, также поступают два операнда, Таким образом, загрузка блоков 10 — 12 памяти и арифметического блока

1 является сбалансированной, ни один иэ указанных блоков в процессе работы не простаивает вхолостую.

Арифметический блок 1 {фиг,2) является конвейерным и регистры 34 — 36 являются фиксаторами ступеней конвейера. Умножители 27 и 28 выполнены конвейерными для того, чтобы задержка распространения любой ступени конвейера не превышала суммы задержек распространения сумматора и регистра. В результате максимальная частота синхронизации арифметического блока 1 определяется задержкой распространения сумматора, а не задержкой комбинационного матричного умножителя, которая для лучших матричных умножителей почти в два раза больше задержки сумматора.

Таким образом, применение в блоке 1 конвейерных умножителей вместо матричных позволило почти в два раза повысить частоту сигнала синхронизации и, соответственно, темп прохождения данных через блок 1.

1667101

10

Сумматор-вычитатель 29 при подаче на его управляющий вход сигнала логического ."0" выполняет функцию суммирования, а при подаче логической "1" — функцию вычигания, Состояние управляющего входа бло, ка 1 и. соответственно, состояние

, управляющего входа сумматора-вычитателя

,29 меняется на противоположное в каждом такте работы процессора, поэтому если в некотором 1-м такте работы процессора на управляющий вход сумматора-вычитателя

29 подается логический "0", то в (I+1)-м такте — логическая "1", Тогда в I-м такте работы процессора на выходе сумматора-вычитателя 29 сформируется операнд, соответствующий выражению (ReB lmW+1 В . ReW), (5) а в (I+1)-м такте — операнд, соответствующий выражению (ReB . ReW - ImB ImW), (6)

, где ReB и Im — операнды, подаваемые со ответственно на входы блока 1 в течение двух тактов работы процессора; (I M)-го и (I — У+1)-го (М вЂ” число ступеней кон вейерн ых умножителей 27 и 28);

lmW — весовой коэффициент, подавае мый на вход блока 1 в (I — М)-м такте и подаваемый на вход блока 1 в (I — M+1)-м такте ! работы процессора

ReW — весовой коэффициент, подаваемый на вход блока 1 в (I — М)-м такте и подаваемый на вход блока 1 в (I — M+1)-м такте работы процессора.

Аналогично тому, как операнды Re В и

ImB удерживаются на входах блока 1 s течение двух тактов, так и операнды ReA u ImA удерживаются соответственно на вхсдах блока 1 в течение двух тактов работы процессора, причем в течение первого из этих двух тактов через мультиплексор 33 на ин,формационный вход линии 32 задержки проходит операнд ImA, а в течение второго такта — операнд ReA (мультиплексор 33 управляется тем же сигналом, что и сумматорвычитатель 29). Линия 32 задерживает последовательность указанных операндов на число тактов, соответствующее числу ступеней конвейерных умножителей 27 и 28 для того, чтобы эта последовательность, поступающая далее на входы сумматора 30 и вычитателя 31, была сфазирована во времени с последовательностью операндов по выражениям (5) и (6), поступающих с выхода регистра 34 на другие входы сумматора 30 и вычитателя 31.

Таким образом, в соответствии с выражениями (1) — (4) и с описанным алгоритмом работы блока 1 последовательность «перандов на выходах сумматора 30 и вычитателя

31 (фиг,2) и, соответственно, на первом и втором выходах блока 1 (фиг.1) следующая: первый выход: ImA, ReA ImA, ReA „, второй выход: ImB, ReB, ImB, ReB ...

Но формат представления данных в блоках 10 — 12 памяти и алгоритм адресации этих блоков таковы, что требуют поступления на первый и второй информационные входы блока памяти — приемника операндов, следующей последовательности данных: первый вход: ReA, ReB, ReA, ReB „. второй вход: lmA, ImB, lmA, lmB ...

Перепаковку выходной последовательности операндов блока 1 (фиг.1) в требуемую входную последовательность блока памяти — приемника выходных операндов блока 1, осуществляет блок 8. Управление процессом перепаковки осуществляется тем же сигналом, что и управление арифметическим блоком 1 (т.е, сумматором-вычитателем 29 и мультиплексором 33 (фиг.2)), который каждый такт меняет свое значение на противоположное, Таким образом, последовательность операндов на выходах блока 8 (фиг.1) соответствует требуемой для подачи на информационные входы блока памяти — приемника операндов, Блок13 постоянной памяти(фиг.1) предназначен для хранения весовых коэффициентов, необходимых для выполнения преобразования Фурье, причем первый вход блока 13 соответствует мнимой части коэффициента, а второй выход — реальной

N части коэффициента. Блок 13 хранит — ee2 совых коэффициентов, необходимых для выполнения БПФ над последовательностью входных данных длиной N. Коэффициенты размещены в блоке 13 в порядке убывания адреса, поскольку в данной реализации процессора адресация всех блоков памяти осуществляется в обратном порядке, т.е, все счетчики, используемые для формирования адреса, являются вычитающими, и определяется следующим выражением:

-I (— )

N

W= 1 где j — мнимая единица.

Для реализации одной базовой операции алгоритма БПФ в соответствии с выражениями (1) — (4) необходим один комплексный весовой коэффициент, причем примененный в процессоре арифметический блок 1 выполняет базовую операцию

БПФ за два такта, в первом из которых на входы блока 1 должны подаваться соответственно мнимая и реальная части коэффи-, циента, а в следующем такте

1667101

5

40

55 соответственно реальная и мнимая части коэффициента. Для перекоммутации реальной и мнимой частей весовых коэффициентов в процессе вычислений предназначен коммутатор 9.

Для реализации алгоритма БПФ в нуле- вой его итерации при выполнении всех базовых операций (1) — (4) используется весовой коэффициент Wo; в первой итерации — повторяющаяся последовательность коэффициентов W, W во второй итерации — повторяющаяся последовательность

1/1/о WN/8 W 4 W последней итерации для нулевой базовой операции используется коэффициент W, для первой базовой операции — коэффициент W и т.д., для (— — 1 базовой операции

N — коэффициент W . Указанный алгоритм адресации весовых коэффициентов обеспечивает формирователь адреса 5 (фиг.1, фиг.6), На управляющие входы мультиплексоров 77 подается код номера итерации (в инверсном виде) с информационного выхода счетчика 44 блока 3 (фиг.4), а на информационные входы — код номера базовой операции БПФ (в инверсном виде) в пределах текущей итерации. Как видно из фиг.6, в нулевой итерации БПФ на выходах всех мультиплексоров 77 будут находиться логические "1", т.е. код (— — 1), адресующий

2 весовой коэффициент W; в первой итерации БПФ на выходах мультиплексоров 77

N N будут чередоваться коды (— — 1) и (— — 1), 2 4 адресующие весовые коэффициенты соответственно W u W в последней итерао N/4, ции БПФ код на выходе мультиплексоров 77 будет меняться при каждой смене номера

N базовой операции от (— — 1) до О. адресуя

2 о N/2-1 все весовые коэффициенты от Ф/ до W

Формирователи адреса 6 и 7 (фиг.1) реализуют алгоритм адресации соответственно блока памяти — источника входных операндов, и блока памяти — приемника выходных операндов арифметического блока

1. Этот алгоритм адресации обеспечивает подачу входных операндов блока 1 и прием выходных операндов блока 1 в порядке, реализующем граф БПФ, Описанный алгоритм работы процессора для нечетного и четного числа итераций

БПФ достигается путем соответствующей коммутации адресных и управляющих входов блоков 10 — 12 памяти (фиг.1) коммутатором 4 и коммутации информационных входов и выходов блоков 10 — 12 коммутатором 2. Этот алгоритм реализуется при подаче сигналов на управляющие входы мультиплексоров 37-41 коммутатора 2 (фиг.3) и сигналов на управляющие входы мультиплексоров 68-76 коммутатора 4 (фиг.5).

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

Процессор быстрого преобразования

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

1667101

16 являются соответственно первый и второй информационные входы коммутатора данных, третий и четвертый информационные входы которого подключены соответственно к первому и второму выходам блока бу- 5 ферных регистров, первый и второй информационные входы которых подключены соответственно к первому и второму входам результата арифметического блока, второй тактовый выход блока управления 10 подключен к первому информационному входу коммутатора управления, тактовым входам второго и третьего регистров и входу синхронизации блока буферных регистров, управляющий вход которого соединен с так- 15 товыми входами шестого и седьмого регистров, управляющим входом коммутатора констант и подключен к первому тактовому выходу блока управления первый управляю1 щий выход которого подключен к управляю- 20 щему входу коммутатора данных, пятый, шестой и седьмой выходы которого подключены к информационным входам соответственно первого, второго и третьего блоков памяти, выходы которых подключены соот- 25 ветственно к пятому, шестому и седьмому (, информационным входам коммутатора данных, третий тактовый выход блока управления подключен к тактовым входам восьмого и девятого регистров и второму информационному входу коммутатора управления, выходы с первого по девятый которого

t подключены соответственно к информа ци он ному и та кто вому входам десятого регистра, входу управления записью/считыванием первого блока памяти, информационному и тактовому входам одиннадцатого регистра, входу управления записью/считыванием второго блока памяти, информационному и тактовому входам двенадцатого регистра и входу управления записью/считыванием третьего блока памяти, выходы десятого, одиннадцатого и двенадцатого регистров подключены к адресным входам соответственно первого, второго и третьего блоков памяти, второй управляющий выход блока управления подключен к управляющему входу коммутатора управления, третий и четвертый информационные входы которого подключены к выходам соответственно второго и третьего формирователей адреса, 1667101

16671 01

1667101

1667101

Составитель А.Баранов

Редактор С.Лисина Техред М.Моргентал Корректор И,Муска

Заказ 2526 Тираж 411 Подписное

ВЙИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101