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

1.4 Т,. Союз Советских Социалистических Республик(22) Заявлено 200378 (21) 2592262/18-24с присоединением заявки Мо(51)М, Кл,2 С 06 Р 15/34 Государственный коиитет СССР по делан изобретений и открытий(54)КАСКАДНОЕ УСТРОЙСТВО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к автомагике и вычислительной технике и может быть использовано в цифровых вычислительных системах обработки информации.Известно каскадное устройство быстрого преобразования Фурье, которое содержит группы арифметических блоков, блоков постоянной памяти, блоки памяти последовательного доступа 1).Наиболее близким техническим ре- шением к изобретению является каскадное устройство быстрого преобраэо" вания фурье, содержащее )1 последовательно соединенных блоков памяти и соответствующих им арифметических блоков 2),Недостатком обоих известных устройств является большое время от момента начала обработки одного исходного массива до завершения обработки и получения всех коэффициентов фурье. Во многих случаях эа это время информация либо устаревает, либо возникают неудобства ее использования.Цель изобретения " повьхаение быстродействия устройства. Поставленная цель достигается тем, что каскадное устройство быстрого преобразования Фурье, содержащее й блоков памяти и Парифметических блоков, причем первый вход и выход-го ( 1 1- й - 1) блока памяти подключены соответственно к первому выходу и первому входу 1 -го арифметического блока, содержит и блоков Формирования адресов и И - 2 коммутаторов, причем первый выход 4 -го (1 ш 1-Й) блока Формирования адресов подключен к адресному входу 1 -го блока памяти, второй выход 1 "го , 1 "- 1 - П) блока формирования адресов " ко входу ( 1 + 1) -го блока Формирования адресов, вход первого коммутатора является входом устройства первый и второй выходы 1 -го (1 1 - и - 3) коммутатора подключены соответственно ко второму входу-го арифметического блока и ко входу (1+ 1)"го коммутатора, первый и второй выходы ( Й - 2) - го коммутатора - соответственно ко второму входу (й) - го и (й)-го арифметических блоков, второй выход 1-го ( 1 =1- й -1) арифметического блока подключен ко втоРезультат типовой операции, полученной в 1 -ом арифметическом блоке записывается в 1+1-ый блок памяти. Запись операндов проводится по тем же адресамчто и считывание, поэтому выработанные конкретные адреса для считывания операндов в 1-ом блоке формирования адресов передаются по соответствующим шинам1 +1-ому блоку формирования адресов, где используются как адреса для организации записи результата рому входу (+1)-го блока памяти,выход . и-го блока памяти - к третьему входу ( и -1) -го арифметического блока, третий выход которогоявляется выходом устройства,На Фиг. 1 показана функциональная схема устройства; на фиг. 2порядок выполнения операций двухточечного преобразования Фурье дляразличных арифметических блоковпри числе отсчетов информации К= 64;Н и К ( 1 =1-6) указывают начало иконец вычислений в 1-ом блоке.Каскадное устройство быстрогопреобразования Фурье содержит блоки 1 памяти, блоки 2 Формирования адресов, арифметические блоки3, коммутаторы 4, вход 5 и выход6. устройство работает следующим образом.По шине 5 вводится исходная инФормация, которая через 1-ый коммутатор попадает в 1-ый арифметический блок. Из 1-го блока памяти выбирается константа весовой функции и производится умножение очередного операнда исходного массива. Результат умножения записывается в некоторую ячейку 1 -го блока памяти. Адресация памяти как для записи, так и для считывания производится соответствующим блоком формирования адресов. Порядок включения коммутаторов, арифметических блоков, блоков формирования адресов обеспечивается блоком управления (на фиг. 1 не показан ).Основной режим - выполнение задачи быстрого преобразования Фурье начинается, когда вся исходная ин-. формация, умноженная на весовую функцию, представлена в соответствующих зонах всех блоков памяти. С этого момента начинается основной цикл работы. Из каждого 1.-го блока памяти выбираются соответствующие операнды и константы и выполняется очередная типовая операция, напримердвухточечное преобразование Фурье;= Х- Х1 ЕХР,в, 1 П, ЕхР 1 - ,операции в 1-ом арифметическомблоке в 1+1 блок памяти.Предлагаемое устройство позволяетза счет одновременного начала параллельных вычислений с р(Р=ГоК)гочгками исходного массива (см. Фиг, 2,точки Н, ) закончить вычисление завремя последовательчого выполнениясамой длинной параллельной ветки,т, е. ветки Нр 1 - К и Н - Кр,РПервая из этих последовательностейсостоит из двухточечных преобразований Фурье, вторая - из 2 М двухточечных последовательностей. Последний арифметический блок реализуетдве последние параллельные ветки 15 и одновременно выполняет три типовых преобразования Фурье. Тем самымпроцесс с Н ,и с НР сводится к Нтиповым тройным операциям, По времени эти операции не превышают одну 20 любую типовую операцию двухточечногопреобразования Фурье, ввиду того,что на последних, указанных выше,параллельных ветках не применяетсяоперация умножения. Действительно 25ехр -1 )=ехр (-о 1:1-о:1, 2 ж О поэтому можно не использовать умножители, а обойтись сумматорамивычитателями.,Можно показать, что время обра ботки одного массива исходной информации в известном устройстве Т и в предлагаемом устройстве Т 2 связаны соотношением Например, при й =1024 В = 4 ф:13, т. е. предложенное устройство в45 13 раз оперативнее выполняет преобразование Фурье. Формула изобретения 50Каскадное устройство быстрого преобразования Фурье, содержащее П блоков памяти и и -1 арифметическихблоков, причем первый вход и выход1 -го ( 1 =1- И -1) блока памяти поЪключены соответственно к первому выходу и первому входу-го арифметического блока, о т л и ч а ю -щ е е с я тем, что, с целью повыщения быстродействия, оно содержит 60 П блоков формирования адресов ип-.2 коммутаторов, причем первый выход 1 -го ( 1 =1- П) блока формирования адресов подключен к адресному входу 1 -го блока памяти, второй у 5 выход 1-го ( 1 =1- и - 1) блока фор723584ф г.г Подписн раж ИПИ Заказ 92 оектная, 4 Патент, г. Ужгород филиал П мирования адресов - ко входу +1)-го блока формирования адресов, вхоц первого коммутатора является входом устройства, первый и второй выходы( -го= 1 - и - 3) коммутатора подключены соответственно ко второму входу 1 -го арифметического блока и ко входу (1 + 1)-го коммутатора, первый и второй выходы ( й)-го коммутатора - соответственно ко второму входу ( п -2)-го и ( о)-го арифметических блоков, второй выход(-го=1- И - 1) арифметического блока подключенко второму входу( Н - 1)-го арифметического блока,третий выход которого является выходом устройства.Источники информации,принятые во внимание при экспертизе1, Зарубежная радиоэлектроникаР 9, 1975. 2. Патент США Р 3816729,кл. С 06 Р 15/34, 1974 (прототип).