Устройство для вычисления быстрого преобразования фурье

(я)5 О 06 Е 153 ПИСАНИЕ ИЗОБРЕТЕНИЯ ИДЕТЕЛ ЬСТВ К АВТОРСКОМ(57) Изобретение относ ной технике и предназн ния алгоритма быстро Фурье по основанию 4 в вой обработки сигнало - повышение быстроде ная цель достигается состав устройства входя дули 1.п.щ первого тип блоки 3.1-3,М постоян управления, генератор сов и соответствующие устройства. 7 ил. мер процессорного модуля в даннои группе, че 1 вертое - номер функционального элемента в данном процессорном модуле.Устройство (фиг.1) содержит процессорные модули 1.п,щ первого типа, входной блок 2, блоки 3.1 - З,М постоянной памяти, блок 4 управления, генератор 5 тактовых импульсов, адресные входы 6. блоков ЗЛ.Кроме того, устройство содержит (фиг,2) . процессорные модули второго типа 7.п.щ и элементы 8.п задержки (и = 2,4).Процессорный модуль первого типа (фиг.З) содержит арифметические блоки 9,п.гп, элементы 10.п.т задержки, узел 11.п,щ постоянной памяти, элементы 12.п.я,р (р = 1,4) задержки, коммутаторы 13,п.гп.р, умножитель 14.п,п.Процессорный модуль второго типа (фиг,4) содеожит регистры 15.п.в, арифметический блок 16.п.п 1 и регистр 17.п,п 1. ния Фур циф ГОСУДАРСТВ ВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Рабинер Л., Гоулд Б, Теория и и рименение цифровой обработки сигналов. М.: "Мир", 1978, с.674.Авторское свидетельство СССР ЬЬ 1508233, кл. 6 06 Е 15/332, 1988.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к вычислитель- технике и предназначено для выполнеалгоритма быстрого преобразования ье (БПФ) по основанию 4 в устройствах ровой обработки сигналов. Цель изобретения - повышение быстродействия,На фиг.1, 2 приведена структурная схема устройства; на фиг.З - структурная схема процессорного модуля первого типа; на фиг.4 - структурная схема процессорного модуля второго типа; на фиг.5 - структурная схема арифметического блока; на фиг.6 - структурная схема блока ввода; на фиг.7 - структурная схема блока управления.В числовых позициях на фиг.1, 3 приняты следующие обозначения; первое число обозначает функциональную принадлежность, второе - номер группы, третье - ноится к вычислительачено для выполнего преобразования устройствах цифров. Цель изобретения йствия. Поставленза счет того, что в т процессорные моа, входной блок 2, ной памяти, блок 4 5 тактовых импульсвязи между узлами, ул, Гагарина аз 4307 ТиражВНИИПИ Государственного комитета по113035, Москва, ЖПодписноебретениям и открытиям при ГКНТ ССаушская наб 415Арифметический блок (фиг.5) содержит коммутаторы 18,п,л 1,р, 19,п.а,р, арифметические узлы 20 плп,р, 21,п.тр, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 22.п.гп.р,Блок ввода (фиг.6) содержит аналогоцифровой преобразователь 23, элемент ИЛИ-НЕ 24, О-триггерь 25,п (и = 1,4), регистры 26,п.Блок управления содержит (фиг.7) счетчик 27, дешифраторы 28.гп (гп == 1,%Р),Регистры 26.п и триггерц 25.п срабатывают по положительному фронту синхроимпульса, все остальные регистры - по отрицательному фронтуРассмотрим работу устройства М =- 64, У = 3. В этом случае каждая линейка состоит из двух процессорных модулей первого типа, Элементы 12 и, 1.р, 10,п, 1.р задержки содержат четыре регистра, элементы 12.п, 2,р, 10,п, 2 р задержки содержат по одному регистру. Счетчик 27 - двоичный шестиразрядный, соединен с двумя дешифраторами 28.1 и 28.2,В первую четверть первого такта в регистр 26.1 записывается отсчет Х/О, во вторук четверть в регистр 26,2 записывается отсчет Х/1, в третью четверть такта в регистр 26.3 записывается отсчет Х/2, в последнюю четверть первого такта в регистр 26.4, записывается отсчет Х/3, В дальнейшем блок ввода работает аналогичным образом, и с целью упрощения его работа не описывается.8Рассмотрйм работу первого процессорного модуля 1.1.1 первой группы,В следующие четыре такта(2 - 5) на входную шину этого процессорного модуля поступают первые входные отсчеты Х/О, Х/4, Х/8, Х/,12, На управляющем входе коммутатора 13,1.1,1 - верхний логический уровень, На управляющих входах остальных коммутаторов процессорного модуля - нижний логический уровень, При верхнем логическом уровне коммутатор 13.1.1.1 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1.1.1 задержки,В следующие четыре такта(6 - 9) на входную шину этого процессорного модуля поступают входные отсчеты Х/16, Х/20, Х/24, Х/28, На уп равля ющем входе коммутатора 13.1.1.2 - верхний логический уровень. На управляющих входах остальных коммутаторов процессорного моцуля - нижний логический уровень. При верхнем логическом уровне коммутатор 13,1,1.2 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12,1.2 задержки и поступают на второй вход арифметического 10 15 20 25 30 35 40 45 50 55 блока 9.1.1.1, Коммутатор 13,1,1.1 принимает информацию с второго входа, Поэтому первые отсчеты циклически сдвигаются в элементе 12.1.1.1 задержки и поступают на первый вход арифметического блока 9,1,1.1. На управляющие входы арифметического блока 9.1.1.1 поступают нижние логические уровни, что соответствует операции А + В,где А и В - операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10,1.1.1 задержки заносятся четыре соответствующие суммы Х/О + Х/16, Х/14+ Х/20, Х/8 + Х/24, Х/12 + Х/28.В следующие четыре такта (10-13) на входную шину этого процессорного модуля поступают входные отсчеты Х/32, Х/36, Х/40, Х/44. На управляющем входе коммутатора 13,1.1,3 - верхний логический уровень. На управляющих входах остальных коммутаторов процессорного модуля - нижний логический уровень. При верхнем логическом уровне коммутатор 13,1,1.3 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1.1.3 задержки и поступают на второй вход арифметического блока 9.1.1.2, Коммутаторы 13,1.1.1 и 13.1.1.2 принимают информацию с второго входа. Поэтому первые и вторые четыре отсчета циклически сдвигаются в элементах 12,1,1.1 и 12,1.1.2 задержки и поступают на первый и второй входы арифметического блока 9,1.1.1 соответственно. На управляющие входы арифметического блока 9,1.1,1 поступают верхний и нижний логические уровни соответственно, что соответствует операции А + В, где А и В - операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.1 задержки заносятся четыре соответствующие суммы Х/О + )Х/16, Х/4+ )Х/20, Х/8+)Х/24, Х/12+ )Х/28. На управляющие входы арифметического блока 9.1.1.2 поступают нижниелогические уровни, что соответствует операции (А+ В) + С, где А+ В и С - операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.2 задержки заносятся четыре соответствующие суммы Х/О+ Х/16+ Х/32, Х/4+ Х/20+ Х/36, Х/8 + Х/24+ Х/40, Х/12 + Х/28+ Х/44.В следующие четыре такта.(14 - 17) на входную шину этого процессорного модуля поступают входные отсчеты Х/48, Х/52, Х/56, Х/60, На управляющем входе коммутатора 13,1,1.4 - верхний логический уровень. На управляющих входах остальных коммутаторов процессорного модуля - нижний логический уровень, При верхнем логическом уровне коммутатор 13.1.1.4принимает Информацию со своего первого, входа поэтому эти четыре отсчета последовательно записываются в элемент 12.1.1.4 задержки поступают на второй вход арифметического блока 9.1.1.3. Коммутаторы 13.1.1,1, 13.1,1.2 и 13,1,1.3 принимают информацию с второго входа. Поэтому первые, вторые, третьи четыре отсчета циклически сдвигаются в элементах 12.1.1.1, 12.1.1.2, 12.1.1.3 задержки. На управляющие входы арифметического блока 9.1.1.2 поступают верхние логические уровни, что соответствует операции (А+)В) - С, где А+ ) В и С - операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10,1,1.2 задержки заносятся четыре соответствующие суммы Х/О + )Х/16- Х/32, Х/4 + )Х/20 - Х/36, Х/8 + )Х/24- Х/40, Х/12+)Х/28- Х/60. На управляющие входы арифметического блока 9.1,1.3 поступают нижние логические уровни; что соответствует операции (А+ В + С+ 0), где А+ В + С и О - операнды на первом и втором входах соответственно, За эти четыре такта на первый вход умножителя 14,1.1 последовательно поступают суммыХ/О+ Х/16+ Х/32 + Х/48,Х/4+ Х/20+ Х/36+ Х/52,Х/8+ Х/24+ Х/40+ Х/56,Х/12+ Х/28+ Х/44+ Х/60,На второй вход умножителя 14.1.1 поступает значение ЧЧ 640, где Юд и = - ехр(-) 2 кп /М),На вход второго процессорного модуля группы поступают четыре первых результата первой итерации алгоритма БПФ. На управляющие входы арифметического блока 9.1.1.1 поступают верхние логические уровни, что соответствует операции А - В, где А и В - операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.1 задержки заносятся четыре соответствующие разности Х/О - Х/16, Х/4- Х/20, Х/8- Х/24, Х/12- Х/28.В следующие четыре такта (18, 19, 20, 21) на входную шину этого процессорного модуля поступают первые четыре отсчета следующего входного массива, На управляющем входе коммутатора 13.1.1,1 - верхний логический уровень. На управляющих входах остальных коммутаторов процессорного модуля - нижний логический уровень. При верхнем логическом уровне коммутатор ,13.1.1.1 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1.1.1 задержки. Коммутаторы 13,1.1.2, 13,1.1.3 и 13.1.1.4 принимают информацию с второго входа. Поэтому вторые, третьи, 5 четвертые четыре отсчета циклически сдвигаются в элементах 12,1,1,2, 12.1.1,3, 12.1.1,4 задержки поступают на вторые входы арифметических блоков 9.1,1.1, 9.1,1.2, 9,1,1,3 соответственно, На управляющие 10 входы арифметического блока 9.1,1.2 поступают нижние логические уровни, что соответствует операции (А - В) + С, где А - В и С - операнды на первОм и втором входах соответственно. За эти четыре такта в элемент 15 10,1.1.2 задержки заносятся четыре соответствующие суммы Х/О - Х/16+ Х/32,Х/4 - /Х/20 + Х/36,20 Х/8- Х/24+ Х/40Х/12 -)Х/28 - Х/60На управляющие входы арифметическо го блока 9.1.1.3 поступают нижний и верхний логические уровни соответственно, что соответствует операции (А + ) В - С) - О, где А+)В -С и)0 - операнды на первом и втором входах соответственно. За эти четыре такта на первый вход умножителя 14,1,1 последовательно поступают суммы;Х/О+ )Х/16 Х/32 )Х/4835 Х/4+)Х/20 - Х/36 О )Х/52,Х/8+ Х/24 - Х/40 -)Х/56,Х/12 + )Х/28 - Х/44 - /Х/60.40оНа второй вход умножителя 14,1.1 поступают значения О/чО, Ю 44, О/648, Юб 412.На вход второго процессорного модуля группы поступают четыре вторых результа та первой итерации алгоритма БПФ, На управляющие входы арифметического блока 9.1,1,1 поступают нижний и верхний логические уровни соответственно, что соответствует операции А - В, где А и В - операнды на первом и втором входах соответственно, За эти четыре такта в элемент 10,1,1.1 задержки заносятся четыре соответствующих разности Х/О - )Х/18, Х/4 - )Х/20. Х/8- )Х/24, Х/12 - ) Х/28.В следующие четыре такта (22 - 25) навходную шину этого процессорного модуля поступают вторые четыре отсчета следующего входного массива. На управляющем входе коммутатора 13.1.1.2 - верхний логический уровень. На управляющих входах ос 169708510 Х/О-)Х/16- Х/32 Х/4-)Х/20 - Х/26 тальных коммутаторов процессорного модуля - нижний логический уровень. При верхнем логическом уровне коммутатор 13.1,1.2 принимает информацию с своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1,1,1 задержки. Коммутаторы 13.1.1.1., 13.1.1,3 и 13,1,1.4 принимают информацию с второго входа. Поэтому первые, третьи, четвертые отсчеты циклически сдвигаются в , элементах 12,1,1.1, 12.1.1,3, 12.1.1.4 задер, жки, На управляющие входь 1 арифметиче. , ского блока 9,1,1.2 поступают верхние , логические уровни, что соответствует опе.раци(А-В)- С, где А-)В и С - операнды напервом и втором входах соответственно. Заэти четыре такта в элемент 10.1.1,2 задерж.ки заносятся четыре соответствующие сум- мы Х/8 - )Х/24 - Х/40, Х/12 - х/28 - Х/60.На управляющие входы арифметического блока 9.1.1,3 поступают верхние логические уровни, что соответствует операции (А - В + С) - О, где А - В + С и О - операнды на первом и втором входах соответственно, За эти четыре такта на первый входумножителя 14.1,1 последовательно поступают суммы Х/О- Х/16-Х/32- Х/48, Х/4-Х/24+ Х/36- - Х/52, Х/8- Х/24+ Х/40 - Х/56 Х/12 - Х/28+ + Х/44 - Х/60,На второй вход умножителя 14.1.1 псступают значения В/640, Я 648, Я 6416, Л 6424 На вход второго процессорного модуля группы поступают четыре третьих результата первой итерации алгоритма БПФ,В следующие четыре такта (26 - 29) на входную шину этого процессорного модуля поступают третьи четыре отсчета следующего входного массива, На управляющем входе коммутатора 13.1,1.3 верхний логический уровень. На управляющих входах остальных коммутаторов процессорногО модуля - нижний логический уровень, При верхнем логическом уровне коммутатор 13.1.1.3 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1,1.3 задержки. Коммутаторы 13,1,1.1, 13,1.1.2 и 13,1.1.4 принимают информаци 1 о с второго входа. Поэтому первые, вторые, четвертые четыре отсчета циклически сдвигаются в элементах 12,1.1.1, 12.1.1,2, 12,1,2,4 задержки, На управляющие входы арифметического блока 9.1,1,3 поступакт 20 25 30 35 40 45 50 55 верхний и нижний логические уровни, что соответствует операции (А -)В - С)+ )О, где А-)В - С и)0 - операнды на первом и втором входах соответственно, За эти четыре такта на первый вход умножителя 14.1,1 последовательно поступают суммы Х/О - )Х/16- Х/32+)Х/48, Х/4-)Х/20+ Х/52, Х/8-)Х/24- Х/40+ )Х/56, Х/12 - )Х/28 - Х/44+ )Х/60,На второй вход умножителя 14.1.1 поступают значения Э/640, Ю 6412, О/6424, Х 6446. На вход второго процессорного модуля группы поступают четыре последних результата первой итерации алгоритма БПФ.Дальнейшая работа первого процессорного модуля группы продолжается по описанному выше алгоритму.Рассмотрим работу второго процессорного модуля 1,1,2 первой линейки, начиная с четырнадцатого такта,Четырнадцатый такт. На входе процессорного модуля значение У/О = (Х/О+ Х/16+ + Х/32+ Х/48) М/640, которое через коммутатор 13.1.2.1 поступает на вход элемента задержки 12,1,2,1,Пятнадцатый такт, На входе процессорного модуля значение У/64 О = (Х/4+ Х/20+ + Х/36+ Х/52) Я 640, которое через коммутатор 13.1.2.2 поступает на вход элемента 12.1.2,2 задержки, Значение У/О через коммутатор 13.1.2.1 поступает снова на вход элемента 12.1.2.1 задержки, На управляющие входы поступают нижние логические уровни. Арифметический блок 9.1.2.1 выполняет операцию А+ В. На его выходе - значение У/О+ У/4.Шестнадцатый такт. На входе процессорного модуля значение 3-8 = Х/8+ Х/24+ + Х/40+ Х/56, %640, которое через коммутатор 13.1,2.3 поступает на вход элемента 12.1.2.3 задержки. На управляющие входы поступают верхний и нижний логические уровни соответственно. Арифметический блок 9.1.2,1 выполняет операцию А+)В. На его выходе - значение У/О+ )У/4, Арифметический блок 9.1.2.2 выполняет операцию (А+ В)+ С. На его выходе - значение У/О+ +У/4+ У/8.Семнадцатый такт. На входе процессорного модуля У/12 - Х/12+ Х/28+ Х/44+ + Х/60) Ю 640, которое через коммутатор 13,1.2.4 поступает на вход элемента 12.1.2,4 задержки. На одни управляющие входы поступают верхние логические уровни, на другие - нижние логические уровни, Арифметический блок 9.1,2,1 выполняет операцию А - В. На его выходе - значение У/О - -У/4, Арифметический блок 9,1,2,2 выполняет операцию (А+ )В/ - С). На его выходе - значение У/О + )У/4 - У/8. Арифметический блок 9,1.2.3 выполняет операцию (А+ ) В+ С)++ О. На его выходе - значение У/О + У/4 ++У/8 + У/12, которое поступает на первыйвход умножителя 14.1.2, на второй вход которого поступает значение ЧЧбаО, На выходеумножителя 14.1,2 - первый результат второй итерации алгоритма БПФ.Последовательность смены управляющих сигналов на втором процессорном модуле группы аналогична смене на первомпроцессорном модуле, но в четыре раза быстрее, Поэтому его дальнейшая работа соответствует уже описанному алгоритму. Сблока 11,1.2 постоянной памяти поступаеткоэффициент ЧЧбаО, С выхода умножителя14,1.2 снимаются результаты второй итерации алгоритма БПФ.Вторая, третья и четвертая группы устройства работают аналогично первойгруппе, последовательность смены управляющих сигналов на этих группах такая же, 20как и на первой группе, Отличие для второйгруппы заключается в том, что на вход второй группы поступают отсчеты Х/1, Х/5,Х/9, Х/13, Х/18, Х/21, Х/25, Х/29, Х/33,Х/37, Х/41, Х/45, Х/49, Х/53, Х/57, Х/61, с 25выхода блока 11.2.1 постоянной памяти последовательно поступают коэффициенты1/ЧбаО, ЧЧбаО, ЧЧбаО, ЧЧба 01 ЧЧба 1, ЧЧба 5, ЧЧба 9,ЧЧба 13, В/ба 2, В/ба 10; В/ба 18, ЧЧба 26, В/ба 3,В/ба 15, ЧЧба 27, В/ба 39, с выхода блока 11,2,2 30постоянной памяти - коэффициенты В/баО,В/ба 4, ЧЧба 8, ЧЧба 12. Отличие для третьейгруппы заключается в том, что нэ вход этойгруппы поступают отсчеты Х/2, Х/6, Х/10,Х/14, Х/18, Х/22, Х 26, Х/30, Х/34, Х/38, 35Х/42, Х/46, Х/50, Х/54, Х/58, Х/62, с выхода блока 11.3.1 постоянной памяти последовательно поступают коэффициенты В/баО,ЧЧбаО, ЧЧбаО, В/баО, В/ба 2, ЧЧба 6, ЧЧба 10, ЧЧба 14,В/ба 4, В/ба 12, В/баг 0, В/баг 8, В/ба 6, ЧЧба 18, 40В/ба 39, ЧЧба 42, с выхода блока 11,3,2 постоянной памяти - коэффициенты ЧЧбаО, ЧЧба 8,В/ба 16, В/ба 24. Отличие для четвертой группы заключается в том, что на вход этой группы поступают отсчеты Х/3, Х/7, Х/11, Х/15, 45Х/19, Х/23, Х/27, Х/31, Х/35, Х/39, Х/43,Х/47, Х/51, Х/55, Х/59, Х/63, с выхода блока 11,4.1 постоянной памяти последовательно поступают коэфициенты ЧЧбаО, ЧЧбаО,В/баО, ЧЧбаО, В/ба 3, ЧЧба 7, ЧЧба 11, ЧЧба 15, В/баб, 50В/ба 14, В/ба 22, ЧЧба 30, ЧЧба 9, ЧЧба 21, В/ба 33,В/ба 45, с выхода блока 11.4.2 постояннойпамяти - коэффициенты В/баО, ЧЧба 12,В/ба 24, В/ба 36,Рассмотрим работу вычислительной матрицы, начиная с семнадцатого такта,Семнадцатый такт, На вход процессорного модуля 7;1,1 поступает результат второй итерации алгоритма БПФ 2(0) = (у(0) + + у(4) + у(8) + у(12 В/баО, который является операндом В для арифметического блока 16.1.1. Операндом А для этого арифметического блока является "0", На управляющих входах этого арифметического блока постоянно нижний логический уровень, что соответствует операции А + В. На выходе арифметического блока 16.1.1 - значение 2(0).Восемнадцатый такт. На вход процессорного модуля 1.1,1 поступает результат второй итерации алгоритма БПФ. 2(4) = = (У/О + ) У/4 - У/8 - ) У/12) ЧЧбаО, который .является операндом В для арифметического блока 16.1,1. Операндом А для этого арифметического блока является "0", На выходе арифметического блока 16.1.1 - значение 2(4). На вход процессорного модуля 7.1,2 поступает результат второй итерации алгоритма БПФ 2(0) = (У/О + У/4 + У/8 + + У/12) ЧЧбаО, который является операндом В для арифметического блока 16.1.2, Операндом А для этого арифметического блока является 2(0), На управляющих входах этого арифметического блока постоянно нижние логические уровни, что соответствует операции А+ В. На выходе арифметического блока 16.2.1 - значение 2(0) + 2(1).Девятнадцатый такт, На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ 2(8) = (У(О) - У(4) + У(8) - У(12) В/баО, который является операндом В для арифметического блока 16.1.1, Операндом А для этого арифметического блока является "0". На выходе. арифметического блока 16.1.1. - значение 2(8). На вход процессорного модуля 7,1.2 поступает результат второй итерации алгоритма БПФ 2(4) = (У(0) = )У(8) = )У(11 В/баО, который является операндом В для арифметического блвкэ 16.1,2. Операндом А для этого арифметического блока является "0", На выходе арифметического блока 16.1.2 - значение 2(4). На вход процессорного модуля 7,2,1 поступает результат второй итерации алгоритма БПФ 2(5) =(У(1)+)У(5) - У(9)+)У/13) ЧЧба 4, который является операндом В для арифметического блока 16,2,1, Операндом А для этого арифметического блока является значение 2(4), На управляющих входах этого арифметического блока постоянно верхний и нижние логические уровни, что соответствует операции А + В. На выходе арифметического блока 16.2.1 - значение 2(4) + 2(5). На вход процессорного модуля 7.2.2 поступает результат второй итерации алгоритма БПФ 2(1) = (У/1 + У/5 + У/9 + У/13)В/баО, который, является операндом В для арифметического блока 16.2.2. Операндом А для этого арифметического блока является значение 2(0), На управляющих входах этогоарифметического блока постоянно верхний и нижний логические уровни соответственно, что соответствует операции А+ В, На выходе арифметического блока 16.2.2 - значение 2(0) + Е(1). На вход процессорного модуля 7.1,2 поступает результат второй итерации алгоритма БПФ Е(4) = (У/О+ + )У/4 - У/8 - У/12)Яв 40, который является операндом В для арифметического блока 16.1.2, Операндом А для этого арифметиче,ского блока является "0". На вход процес. ,сорного модуля 7.1,3 поступает результат второй итерации алгоритма БПФ Е(О) =-. .= (У/О + У/4 + У/8 + У/12)ЯуО, который является операндом В для арифметическогоблока 16,1.3. Операндом А для этого арифметического блока является "0". На управляющих входах этого арифметического блока постоянно нижние логические уровни, что соответствует операции А + В. На выходе арифметическогдо блока 16,1.3 значение 2.(0), На вход процессорного модуля 7.3,1 поступает результат второй итерации алгоритма БПФ Е(2) = (У/2 + У/6+ У/10 ф + У/14)Юб 40, который является операндом В для арифметическогр блока 16,3,1. Операндом А для этого арифметического блока является Е(0) + Е(1). На управляющих входах этого арифметического блока постоянно нижние логические уровни, что , соответствует операции А+ В. На выходе , арифметического блока 16.3.1 значение Е(0) + 2(1) + 7(2) + 7(3).Двадцатый такт. На вход процессорного модуля 7.4.1 поступает значение 7(4) = (У/4+ У/8+ У/12+ У/16) ЯваО.На выходе арифметического блока 16.4,1 - значение 2(0) + 2(1) + Е(2) + Е(3).С целью упрощения дальнейшая работа вычислительной матрицы не описывается.Отметим, что на втором столбце матрицы вычисляется значение Е + Д) - 1) - Л( + 2)- - )Е( +3), на третьем столбце значение Е = Е(+1) + Е(+2) - (+3), на четвертом столбце значение Е - Е(+1) - У(+2)+ Щ+3), В соответствии с данными операциями на управляющих входах арифметических блоков процессорных модулей матрицы постоянно выставлены следующие логические уровни:О - О,0 - О,0 - О,0-00-0,1-0,1 - 1,01,0-0,1-1,20 25 30 в 35 40 45 50 55 0 - О,1-1,0 - О,0-1,1 - 1,1 - О,Начиная с двадцать первого такта на выходе процессорного модуля 7.4.1 последовательно получаются следующие коэффициенты БПФ: Е(0), Е(4), Е(12),Е(1), Е(5), Е(9), Г(13), Е(2), Е(6), Е(10), Е(14), Е(3), Е(7), Е(11), Е(1 5).Начиная с двадцать второго такта на выходе процессорного модуля 7.4.2 последовательно получаются следующие коэффициенты БПФ: Г(16), Е(20), Е(24), Е(28), Г(17), Е(21), Е(25), Е(29), Е(19), Г(22), Е(26), Г(30), Е(19), Е(23), Е(27), Е(31),Начиная с двадцать третьего такта на выходе процессорного модуля 7.4,3 последовательно получаются следующие коэффиценты БПФ; Е(32), Е(36), Г(40), Г(44), Е(33), Г(27), Е(41), Г(45), Е(34), Г(38), Г(42), Е(46), Е(35), Е(39), Е(43), Е(47).Начиная с двадцать четвертого такта на выходе процессорного модуля 7.4.4 последовательно получаются следующие коэффициенты БПФ; Е(48), Е(52), Е(56), Г(60), Е(49), Е(53), Е(57), Г(61), Г(50), Г(54), Е(58), Г(62), Г(51), Е(55), Е(59), Г(63).Рассмотрим работу устройства в том случае, когда каждая группа процессорных второго типа содержит по одному элементу. В этом случае матрица этих процессорных модулей вырождается в столбец, Поскольку все предыдущие узлы работают аналогично, опишем работу одного столбца процессорных модулей второго типа.Первая четверть семнадцатого такта. На вход процессорного модуля 7.1,1 поступает результат второй итерации алгоритма БПФ Е(0) = (у(0) + у(4) + у(8) + у(12 Ю 640, который является операндом В для арифметического блока 16,1.1. Операндом А для этого арифметического блока является "0". На управляющие входы этого арифметического блока поступает нижний логический уровень, что соответствует операции А+ В. На выходе арифметического блока 16,1,1 - значение Е(0).Вторая четверть семнадцатого такта. На вход процессорного модуля 7.1,1 поступает результат второй итерации алгоритма БПФ Е(0), который является операндом В для арифметического блока 16,1,1, Операндом А для этого арифметического блока является "О". На выходе арифметического блока 16.1.1 - значение Е(0). На вход процессорного модуля 7,2.1 поступает результат второй итерации алгоритма БПФ Е(1) = (у(1) + у(5)+ у(9) + у(13 Юбд 0, который является операндом В для арифметического блока 16.2.1. Операндом А для этого арифметического блока является значение Е(0). На уравляющие входы этого арифметического блока поступают нижниЕ логические уровни, что соответствует операции А + В. На выходе арифметического блока 16,2.1 - значение 7(0) + (1),Третья четверть семнадцатого такта. На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ Е(0), который является операндом В для арифметического блока 6.1;1. Операндом А для этого арифметического блока является "0". На выходе арифметического блока 16.1.1 - значение Е(0). На вход процессорного модуля 7,2.1 поступает результат второй итерации алгоритма БПФ 2(1), который является операндом В для арифметического блока 16,2,1. Операндом А для этого арифметического блока является значение,ЦО). На управляющих входах этого арифметического блока - верхний и нижний логические уровни соответственно, что соответствует операции А+) В. На выходе арифметического блока 16.2.1 - значение Е(0) + )Е(1). На вход процессорного модуля 7.3,1 поступает результат второй итерации алгоритма БПФ 2(2) = (У(2) + У/6 + П 10 + У/14)Юва 0, который является операндом В для арифметического блока 16.3.1, Операндом А для этого арифметического блока является Е(0) + Е(1). На управляющих входах этого арифметического блока нижние логические уровни, что соответствует операции А + В. На выходе арифметического блока 16,3.1 - значение Е(0) + Е(1) + 7(2).Последняя четверть семнадцатого такта. На вход процессорного модуля 7.4.1 поступает значение 2(3) = (у(3) + у(11) = = у(15 И/640. На выходе арифметического блока 16.4.1 - значение 2(0)+ Е(1)+ 2(2)+ Щ,С целью упрощения дальнейшая работа вычислительной матрицы не описывается. Отметим, что на выходе линейки появляются значения 2 + Л(+1) + 2(+2) +Е(+3), 2 + +Д+1) - Е(+2) - Д+3), 2 - 2(+1) + 2(+2)- -2(+3), 7 - Щ+1) - Е(+2)+)Е(+3), В соответствии с данными операциями на входах арифметических блоков 16.п.1 (и = 1,4) появляются следующие логические уровни:Начиная с последней четверти семнадцатого такта на выходе процессорного модуля 7.4.1 последовательно получаются следующие коэффициенты БПФ: Е(0), Е(16), Е(32), Е(48), Е(4), Г(20), Е(36), Г(52), Е(8), Е(24), Е(40), Г(56), Е(12), Г(28), Е(44), Е(6), Е(1), Е(17), Е(33), Е(49), Е(5), Е(21), Е(27), Е(53), Е(9), Е(25), Г(41), Е(57), Г(13), Е(29), Е(45), Е(61), Е(2), Е(18),Е(34), Е(50), Е(6), Г(22), Г(38), Е(54), Е(10), Е(26), (Е 42), Г(58), Е,14), Г(30), Е(46), Е(62), Е(3). Г(19), Г(35), Г(56), Е(7), Г(23), Г(39), Е(55), Е(11), Г(27), Г(43), Е(59), Е(15), Е(31), Е(47), Е(63).В этом случае синхронизация элементов 8,2-8,4 и 7,п.1 осуществляется непосредственно с выхода генератора 5 тактовых импульсов,10 Формула изобретенияУстройство для вычисления быстрогопреобразования Фурье, содержащее первую группу из М) (М = о 94 ч, й - размер преобразования) процессорных модулей 15 первого типа, Мблоков постоянной памяти, блок управления и генератор тактовых импульсов, выход которого подключен к тактовому входу блока управления, -ый ( = 1, М) управляющий выход которого подклю чен к первому управляющему входу -го процессорного модуля первого типа первой группы, второй управляющий вход которого подключен к выходу -го блока постоянной памяти, адресный вход которого подключен к -му адресному выходу блока управления, выход -го ( = Т, М) процессорного модуля первого типа первой группы подключен к информационному входу +1-го процессорного модуля первого типа первой группы, 30 причем процессорный модуль первого типасодержит шесть элементов задержки, три арифметических блока, умножитель и четыре коммутатора, выход первого.коммутатора подключен к входу первого элемента задержки, выход которого подключен к первому информационному входу первого арифметического блока, выход которого подключен к входу второго элемента задержки, выход которого подключен к первому 40 информационному входу второго арифметического блока, выход которого подключен к входу третьего элемента задержки, выход которого подключен к первому информационному входу третьего арифметического 45 блока, выход которого подключен к первомувходуумножителя, выход которого является выходом процессорного модуля первого типа, первым управляющим входом которого являются объединенные между собой управляющие входы с первого по четвертый коммутаторов выход К-го (К = 2,4) коммутатора подключен к второму информационному входу К-го арифметического блока и входу К+2-го элемента задержки, выход которого подключен к первому информационному входу К-го коммутатора, вторые информационные входы всех коммутаторов подключены к информационному входу процессорного модуля первого типа, к второмууправляющему входу которого подключены1697085 00 00 управляющие входы всех арифметических блоков, отличающееся тем,что,с целью повышения быстродействия, в него введены вторая, третья и четвертая группы из Мпроцессорных модулей первого типа в каждой группе, блок ввода, три блока задержки и четыре группы из 1:х (1 - целое число) процессорных модулей второго типа в каждой группе, при этом первый и второй управляющие входы 1-го процессорного модуля первого типа К-ой группы подключены соответственно к 1-му управляющему выходу блока управления и выходу 1-го блока постоянной памяти, выход 1-го процессор. ного модуля первого типа К-ой группы подключен к информационному входу,1+ 1 го процессорного модуля первого типа К-ой группы, первый информационный вход К- го процессорного модуля второго типа 1-ой , ( = 1 Я.) группы подключен к первому выходу (К)-процессорного модуля второго типа 1- 1-ой группы, второй информационный вход К-го процессорного модуля второго типа К. ой группы подключен к второму выходу 1-го процессорного модуля второго типа К-ой группы, выход М-го процессорного модуля первого типа первой группы подключен к первому информационному входу первого процессорного модуля второго типа первой групы, выход М-го процессорного модуля первого типа К-ой (К = Г 3) группы подключен к входу К-го блока задержки, выход которого подключен к первому информаци. онному входу первого процессорного моду. ля второго типа К-ой группы, второй выход 1-го процессорного модуля второго типа четвертой группы является 1-ым информационным выходом устройства, информационным входом которого является информационный вход блока ввода, 1-ый выход которого подключен к информационному входу первого процессорного модуля первого типа К-ой группы, выход генератора тактовых импульсов подключен к тактовому входу входного блока, при этом в каждый процессорный модуль первого типа введен блок постоянной памяти, выход которого под ключен к второму входу умножителя, адресный вход блока постоянной памяти 1-го процессорного модуля первого .типа 1-ой группы подключен к 1-му адресному выходу блока управления, при этом процессорный 10 модуль второго типа содержит два регистраи арифметический блок, первый информационный вход которого соединен с информационным входом первого регистра и является первым информационным входом 15 процессорного модуля второго типа, вторым информационным входом, первым и вторым выходами которого являются соответственно второй информационный вход арифметического блока, выход первого ре гистра и выход второго регистра, информационный вход которого подключен к выходу арифметического блока, тактовые входы первого и второго регистров всех процессорных модулей второго типа подключены к 25 тактовому выходу блока управления, причем входной блок содержит четыре регистра, элемент ИЛИ-НЕ, четыре Р-триггера и аналого-цифровой преобразователь, выход которого подключен к информационному входу 1-го регистра, выход которого является 1-ым выходом входного блока, тактовым входом которого являются соединенные между собой тактовые входы всех О-триггеров и аналого-цифрового преобразователя, информационный вход которого является информационным входом входного блока, выход 1-го О-триггера подключен к тактовому входу 1-го регистра, выход Я-го (Б.= 1,3) Р-триггера подключен к Я-му входу элемента ИЛИ-НЕ, выход которого подключен к информационному входу первого 0-грйггера, выход К-го О-триггера подключен к информационному входу К-го О-триггера, 1697085