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

и второй коммутаторы, регистр сдвига, в каждьй вычислительный блок введен переключатель, а в каждый арифметический узел введен элемент НЕ, при- , чем информациоиньш выход регистра сдвига подключен к первому информа ционному входу первого коммутатора, информационный выход которого соединен с информационным выходом второго кoм fyтaтopa и с первьм информационньм входом первого коммутатора К -го вычислительного блока, второй информационный вход первого коммутатора соединен с первым информационным входом второго коммутатора, с информащ онным входом регистра сдвига и является первым информационным входом устройства,вторым информационным входом которого является второй информационнМ вход второго коммутатор а, управляющие входы первого и второго комм /таторов подключены к выходам соответственно восьмого и девятого разрядов блока постоянной памяти, выход десятого разряда которого подключен к управляющему входу переключателя (р Тд вычислительного блока, информационные выходы первого и второго узлов памяти р -го вычислительного блока подключены соответственно к первому и второму информационным входам переключателя р-го вычислительного блока, первьй и второй информационные выходы которого подключены соответственно к второму входу умножителя и вторым входам сумматора и вычитателя арифметического узла вычислительного блока, выход вычитателя арифметического узла подключен к входу элемента НЕ арифметического узла, выход которого подключен к вторым информационным входам первого и второго коммутаторов арифметического узла.

УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНА ФУРЬЕ, содержащее последовательно -соединенные генератор тактовых импульсов, счетчик адреса и блок постоянной памяти, блок постоянной памяти коэффициентов и К вычислительных блоков, каждый из которых состоит из первого и второго коммутаторов, первого, второго, третьего и четвертого узлов памяти и арифметического узла, информационные выходы первого и второго коммутаторов подключены к информационным входам соответственно первого и второго узлов памяти, управляющие, входы которых подключены к выходам соответственно первого и второго разрядов блока постоянной памяти, выходы третьего, четвертого, пятого и щестого разрядов которого подключены к управляющим входам соответственно третьего и четвертого узлов памяти, первого и второго коммутаторов -го (,K) вычислительного блока, первые информационные входы первого и второго коммутаторов j-го () 1,К-1) вычислительного блока подключены к информационным выходам соответственно первого и второго узлов памяти (j+1)-ro вычислительного блока, первый информационньм вход второго коммутатора К-го вычислительного блока подключен к информационному выходу первого узла памяти первого вычислительного блока, вторые информационные входы первого и второго коммутаторов

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

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

Наиболее близким по технической сущности к изобретению является устройство быстрого преобразования Фурье, содержащее блок управления, блок формирования весовых коэффициентов и , где f - целое число () вычислительных блоков, каждый из которых состоит из коммутаторов, блоков памяти и арифметического блока, причем управляющие входы коммутаторов подключены к выходам блока управления, а информационный вход арифметического блока - к выходу блока формирования весовых коэффициентов. -Это устройство реализует граф алгоритма БПФ с однородной структурой, .при которой адресация записи и считьшания обрабатьшаемых чисел не зависит от номера интеграции. Вследствие однородности графа алгоритма БПФ связи между К вычислительными блоками остаются фиксированными в процессе вычислений Zj .

Недостатком этого устройства является низкое быстродействие и избыточный объем памяти при вычислении пре- образования Фурье действительного входного сигнала.Цель изобретения - повьшение быстродействия устройства для быстрого преобразования Фурье.

Цель достигается тем, что в устройство для быстрого преобразования Фурье, содержащее последовательно соединенные генератор тактовых импульсов, счетчик адреса и блок постоянно памяти, блок, постоянной памяти коэффициентов и k вычислительных блоков, каждыйиз которых состоит из первого и второго коммутаторов, первого,второго, третьего и четвертого узлов памяти и арифметического узла, инфор мационные выходы первого и второго коммутаторов подключены к информационным входам соответственно первого и второго узлов памяти, управляющие входы которых подключены к выходам соответственно первого и второго раз рядов блока постоянной памяти, выходы третьего, четвертого, пятого, и шестого разрядов которого подключены к управляющем входам соответствен но третьего и четвертого узлов памяти, первого и второго коммутаторов 1-го i (,К) вычислительного блока, первые информационные входы первого и второго коммутаторов j-ro (,k-1 вычислительного блокг подключены к информационным выходам соответственно первого и второго узлов памяти (j+1)-ro вычислительного блока, первый информационный вход второго коммутатора k -го вычислительного блока подключен к информационному выходу первого узла памяти первого вычислительного блока, вторые информационные входы первого и второго коммутаторов (2т-1)-го (,k./2) вычис11ительного блока подключены к информационным выходам третьих узлов памяти соответственно ,т-го и (m+k/2)-ro вычислительных блоков, вторые информационные входы второго и первого коммутаторов 2f-ro ( ,k/2) вычислительного блока подключены к информационным выходам четвертых узлов памяти соответственно f-ro и (f+k/2)-r вычислительных блоков, а арифметичес кий узел 5-г6 ( 1,k) вычислительного блока содержит умножитель, сумма- тор, вычитатель и первьй и второй коммутаторы, при этом выход умножителя подключен к первь1м входам соответственно вычитателя и сумматора, вькод которого подключен к первым HH формационным входам первого и второго коммутаторов, информационные выхо ды коФорых подключены к информационным входам соответственно третьего и четвертого блоков памяти 5-го вычислительного блока, первый вход умножителя арифметического узла 5-го вычислительного блока подключен к выходу 5 -го разряда блока постоянной памяти коэффициентов, управляющие входы первого и второго коммутаторов арифметических узлов вычислительных блоков подключены к выходу седьмого разряда блока постоянной памяти, введены первый и второй коммутаторы, регистр сдвига, в каждый вычислительный блок введен переключатель, а в каждый арифметический узел введен элемент НЕ, причем информационный выход регистра сдвига подключен к пер вому информационному входу первого коммутатора, информационный выход которого соединен с информационным выходом второго коммутатора и с первым информационным входом первого коммутатора k-ro вычислительного бло.ка, второй информацибнный вход первого коммутатора соединен с первым информационным входом второго коммутатора, с информационным входом регистра сдвига и является первым информационным входом устройства, вторьм информационньм входом которого является второй информационный вход второго коммутатора, управляющие входы первого и второго коммутаторов подключены к выходам соответственно восьмого и девятого разрядов блока постоянной памяти, выход десятого разряда которого подключен к .управляющему входу переключателя р-го (,k). вычислительного блока, информационные выходы первого и второго узлов памяти р-го вычислитель-ного блока подключены соответственно к первому и второму информационным, входам переключателя р-го вычислительного блока, первый и второй информационные выходы которого подключены соответственно к второму входу умножителя и вторым входам сумматора и вычислителя арифметического узла вычислительного блока, выход вычитателя арифметического узла подключен к входу элемента НЕ арифметического узла, выход которого подключен к вторым информационным входам первого и второго коммутаторов арифметического узла. На фиг.1 приведена функциональная схема устройства, на фиг.2 - функциональная схема вычислительного блока на фиг.3 - функциональная схема арифметического узла, на фиг.4 - граф алгоритма БПФ действительной последовательности для , на фиг.5 - базо вая операция алгоритма БПФ действительной последовательноети на фиг.6 функциональная схема переключателя, На фиг.7 - функциональная схема блок управления/ на фиг.8 - временная диаграмма работы блока управления. Устройство содержит коммутатор 1, регистр 2 сдвига, коммутатор 3, вычислительные блоки , блок 5 постоянной памяти коэффициентов, блок 6 управления. Вычислительный блок (фиг.2) содер жит узлы 7 памяти, арифметический узел 8, переключатель 9, узлы 10 памяти и коммутаторы 11. Арифметический узел (фиг.З) содер жит умножитель 12, вычитатель 13, сумматор 14, элемент НЕ 15, коммутаторы 16. Блок управления (фиг.7-) содержит генератор 17 тактовых импульсов,счет чик 18 адреса, блок 19 постоянной памяти. Устройство работает следующим образом. В режиме обработки действительного сигнала при записи входной информации первая половина входной действительной последовательности (п) длительности , ., где k - целое, поступает на регистр 2, имеющий длину N/2 слов, и через коммутатор 3 на первый вход k-ro вычислительного блока. Вторая половина информации поступает через коммутатор 1 непосредственно на первый вход k-го вычислительного блока. В результате на этот вход одновременно поступают выборки входного сигнала x(t) и x(i+ +N/2) (i 0-R/2-1), которые при обработке рассматриваются соответственно как действительная и мнимая части комплексного числа y(i), где y(i)x(i)+jx(i+N/2); N/2-1, . Таким образом, с помощью коммутаторов 1 и 3 регистра 2 входная дейст вительняя последовательность длины N преобразуется в комплексную после- 50 довательность длины N/2. В случае обработки комплексного сигнала вся входная информация, пред- ставляняцая собой последовательноств комплексных чисел, поступает через коммутаторы 1 и 3 непосредственно на первый вход k-ro вычислительного блочса. При загрузке входной информации коммутаторы 11 вычислительных блоков (4-1,...,4-k)-пропускают сигналы, поступающие на входы вычислительных блоков (4-1,...,4-k) (независимо от того является входная последовательность действительной или комплексной) . При этом узлы памяти 7 всех вычислительных блоков соединяются последовательно, образуя цепочку для загрузки входной последовательности. После N/2 тактов сдвига в первьй узел 7 памяти (нижний на фиг.2) i-ro вычислительного блока (4-i) () запишутся выборки y(k) с номерами k с - (i-V) по ji-1,во второй узел 7 памяти этого же блока (верхний на фиг.2) - выборки с номерами k+rj, где . После записи всей входной информа ции начинается собственно процесс ее обработки. Граф алгоритма БПФ действительной последовательности для представлен на фиг.4, а базсшая операция этого алгоритма -.на фиг.З. Однородность графа позволяет установить фиксированные связи между вычислительными блоками (4-1, 4-2, ..., 4-k). Отметим следующую особенность графа f фиг. 4 j. Результирующие значения спектральных составляющих x(k) (k 1-N/2-1) получаются в результате выполнения log2 N-1 итераций. Для получения значений х(0) и x(N/2) необходимо дополнительносоответственно сложить и вычесть действительную и мнимую части числа А (граф на фиг.4). Поскольку при решении практических задач эти точки находятся на краях анализируемого диапазона частот, то их вычисления, как правило, не требуется. На любой итерации в каждом вычислительном блоке обрабатываемые величины y(k) из первого узла 7 памяти, и y(k+N/4) из второго узла 7 памяти (k 0-N/4-1) одновременно поступают на вход переключателя 9. Если базовая операция над этой-парой комплексных чисел выполняется со значением весового множителя, равным W, то пере1шючатель 9 осуществляет, перестановку мнимой части числа y(k) и действительной части числа y(k+N/4) в-соответствии с алгоритмом (фиг.З). Схема, осуществляющая указанную перестанов- Biy, может быть построена на основе двух коммутаторов (фиг.6), Сигналы с выхода переключателя поступают на соответствующие входы арифметического узла 8. Комплексное число y(k+N/4 поступает на вход умножителя 12, на .другой вход которого из блока 5 постоянной памяти коэффициентов поступает соответствующее значение весово го множителя W, зависящее от номера выборки и от номера итерации. Таким образом, на выходе умножите ля 12 получается значение произведения y(k+N/4)-W . Это число с выхода умножителя 12 подается на входы вычи тателя 13 и сумматора 14, на другие входы которых одновременно подается число y(k) с выхода переключателя 9. На выходе сумматора 14 получается результат y(k)+y(k+N/4)W . Результат,; полученньш на выходе вычитателя 13 и равный y(k)-y(k+N/4)W , поступает на вход элемента НЕ 15, который выполняет операцию комплексного сопряжения, числа, так что на его выходе получается число y(k)-v(k+j)W J Результаты с выхода сумматора 14 и элемента НЕ 15 последовательно оди за другим по управляющему синхроимпульсу от блока 6 управления через коммутаторы 16.записываются в третий (верхний на фиг.2) и четвертый (нижНИИ на фиг.2) узлы 10 памяти в зависимости от номера отсчета обрабатыва емой последовательности, причем в третий узел 10 памяти записываются взвешенные сумма и разности первой половины вычислительных результатов, в четвертьй - вторая половина. М„ После т тактов вычислении содержимое третьих и четвертых узлов 10 памяти переписывается соответственно в первые и вторые узлы 7 памяти соот ветствукнцих блоков (через коммутатор 11 по управляющему синхроимпульсу с блока 6 управления. Это позволяет проводить обработку информации во всех последующих итерациях аналогично описанной. Блок 6 управления может быть построен по любой из известных схем в зависимости от задач, для решения ко торых используется устройство быстро го преобразования Фурье. Один из возможнэк вариантов построения блока 6 управления приводит ся на фиг.7. Блок 6 управления состо 1 728 ит из генератора 17 тактовых импульсов, сигнал от которого подается на счетчик 18 адреса. В зависимости от состояния счетчика на выходе блока 19 постоянной памяти формируются необходимые управляющие сигналы. Нафиг.9 показан вид управляющих, сигналов, которые формируются на выходе блока 19 для управления переключателем 9 (в режиме обработки действительного сигнала), коммутаторами 11, 16 и управ- ляющие сигн.алы на запись и считывание узлов 7 и 10 памяти. По управляющему сигналу на коммутатор 11 (сигнал q на фиг.9) в режиме входной информации пропускаются сигналы, поступакяцие на входы вычислительных блоков (4-1-4-k) для записи в узлы 7 памяти (по управлякяцему сигналу 8 на фиг.8), Далее при выполнении вычислений коммутаторы 11 пропускают сигналы, поступающие, на входы всех вычислительных блоков. Процесс вычислений на калодой итерации можно разбить на два этапа. На первом этапе по управляющему сигналу считывания (сигнал b на фиг.9) производится считывание информации из первого и второго узлов 7 памяти и выполняются базовые операции в арифметическом узле 8. На этом же этапе первая половина результатов вычислений, получаемых на выходе арифметического узла: 8, по управляющему сигналу записи (сигнал 2 на-фиг.8) записывается в третий узел 10 памяти, а вторая половина записывается в четвертый узел 10 памяти по управляющему сигналу 9 на фиг.8. Коммутация информации между третьим и четвертым узлами 10 памяти осуществляется коммутаторами 16 по управляющему сигналу на фиг.8. Поскольку за время считывания числа из блока 7 памяти в один из узлов 10 памяти должны записываться два числа, то частота записи в узлы 10 памяти должна; быть в 2 раза больше, чем частота считывания из узла 7 памяти (фиг.8). На втором этапе производится перезапись результатов вычислений из узлов 10 памяти в узлы 7 памяти в соответствии со схемой фиг.1. При этом управляющий сигнал считывания из уз.лоБ 10 памяти имеет такой же вид, как и сигнал записи в узлы 7 памяти (сигнал fi на фиг.8). По управляющему сигналу (сигнал к на фиг.8) на переключателе 9 в режиме обработки действительной последовательности выполняется перестановка мнимой части числа y(k) и действительной части числа y(k+), (,-|- поступающих на переключатель 9 из узлов 7 памяти при вьшолнении базовы операций со значением весового мно-жителя W°, Так на первой итерации будет осуществляться перестановка каждой пары чисел y(k), y(k+r) (k IN . 0- 7 -1) поскольку на этой итераци все базовые операции вьшолняются со значением весового множителя W°. В соответствии с графом на фиг.4 с уве личением номера итерации на единиц число базовых операций с весовым множителем W° уменьшается в 2 раза/ поэтому во столько же раз должно уменьшаться число перестановок, осуществляемых переключателем 9. На основании приведенного изложения и временной диаграммы фиг.8 производится запись информации в блок 1 для получения необходимых управляющих сигналов. Причем для формировани каждого сигнала необходимо N+Lj ячее памяти, где m - число итераций алгоритма БПФ, . В блоке 19 информация распределяется по ячейкам памяти следукнцим образом: в разряде, предназначенном для формирования управлянщего сигнала на коммутаторы 1 в ячейки памяти с адресами ,1,.„ N-1 записывается 1, а в остальные О, в разряде, предназначенном для формирования управлякицих сигналов за писи блоков 7 памяти и считьгоания блоков 9 памяти, в ячейки памяти с адресами 41-1, 41-2(,2,...N/4), 41-2+н4+ (k+1) L , 41-1 (k-1) L ( i 1 (,2,..,j, ,2,...m) записывает СЯ 1, a в остальные - О. В разряде, предназначенном для формирования управлякиЦего сигнала считывания блокозз 7 памяти, в ячейки памяти с адресами 4i-2+N-«-(m-1)L,, 4i-H-N+(m-1)L ( ,g)() .записывается 1, а в остальные - О, в разряде, предназначенном для формирования управляющего сигнала записи третьего блока 10 памяти, в ячейки памяти с адресами 2i+1+N+(k+1)L(, L/4-1; ) записывается 1, а в остальные - О, в разряде, предназначенном для формирования управляющего сигнала .записи четвертого блока 10 памяти, в ячейки памяти с адреса2i+1+N+W(k-1).L (, L/4-1; , ю) записывается 1, а в остальные , в разряде, предназначенном для формирования управляющего сигнала коммутаторами 16, в ячейки памяти с адресами i+ (п-1) L+N,( ,N/4-1; ) записывается 1, а в остальные , в разряде, предназначенном дляформирования зпправляющего сигнала переключателем 9, в ячейки памяти с адресами (k-1)L,N+1+(k-1)L,..., N+(k-1)-L+L/2 -1 (,ra) записывается 1, а в остальные - О. Б случае обработки комплексной последовательности по внешней команде вся входная информация поступает через коммутаторы 1 и 3 непосредственно на первый вход k-ro вычислительного блока. По этой же команде перестановка мнимой части числа y(k) и действительной части числа y(k-rN/4) переключателем 9 не производится и не выполняется операция комплексного сопряжения числа на выходе вычитателя 13. Окончательный результат N/2 коэффициентов дискретного преобразования Фурье входного сигнала пол.учается после П--1 итераций, записанными в третьи и четвертые узлы 10 памяти k вычислительных блоков. Порядбк записи результатов вычисления преобразования Фурье действительной входной последовательности отличается от нормального и является стандартным для такого типа графов. Таким образом, .использование предлагаемого изобретения позволит сократить более чем в 2 раза время обработки действительного сигнала и вдвое уменьшить объем памяти вычислительных блоков. При этом уменьшается стоимость устройства и повьш1ается его надежность.

4

см

I

«S

omS

i

tti

З

13

/2

отЗ

n

Фиг.2

отб

i

ffW

/5

16

/c/

16 -

Т

от В

ШГ1Щ

Х(1)фт

X(2)WO) X(3)JX(11)

)((12) X(5)j(13)

x(6)wW

X(7)J(15)

/7

19

fu2j