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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советскик Социалистических Республик(22) Заявлено 051277 (21) 2550924/18-24 с присоединением заявки М 9 С 06 Г 15/34 Государственный комитет СССР но делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯФУРЬЕ Изобретение относится к вычислительной технике и предназначено для спектрального анализа электрических сигналов, представленных в цифровой форме.Известно устройство, содержащее двухканальное арифметическое устройство, в котором последовательно осуществляются двухточечные преобразования входных выборок сигнала, хранимых в оперативной памяти (1),Недостатком устройства является то, что объем полупроводниковой памяти с произвольной выборкой вдвое превышает объем выборки ббрабатываемых входных сигналов, поскольку в этой памяти одновременно хранятся , входные величины и результаты вычислений. Данная память имеет достаточно сложную систему адресации для реализации.- алгоритмов занесения информации и ее передачи в Ау в. процессе обработки информации.Наиболее близким по структуре является ассоциативный параллельный процессор для быстрого преобразова-ния Фурье содержащий первый и второй регистры, регистр маски, память коэффициентов, матрицу ассоциативной памяти, состоящую из ф строк (гдеИ - количество точек в исходной последовательности отсчетов), каждаяиз которых состоит иэ десяти ячеек,соединенных своими установочнымивходами через регистр маски с выходами первого регистра, а выходамисо входами второго регистра, входыпятой и шестой ячеек соединены ссоответствующим номеру строки выходом памяти коэффициентов, первыйи второй коммутаторы (2).Недостатком устройства является то,что после каждого цикла вычислений 15 результат накапливается в этой жестроке. Это обусловлено тем, чтономера строк ассоциативной памяти,вкоторые записываются результаты очередной итерации, каждай раэ различны.20 Поэтому пересылки операндов осуществ"ляются с помощью коммутирующей матрицы,соединяющей шину связи с шиной разрешения записи соответствующих строкнакопителя.Размеры коммутирующей матрицысущественно зависят от числа выборок анализируемого сигнала и оп,.ределяются выражением30о=фоКИЕаличие большого числа коммутйр 1 йощих элементов и шин в коммутирукцей матрице является существеннымпрепятствием для ее микроминиатюри-.зацим. Кроме того, пересылка операндов после каждой итерации требует определенных затрат времении наличия специальных сигналов дляуправления коммутирующей матрицей,Цель изобретения - сокращениеобщего объема используемого оборудования и повышение быстродействия.Поставленная цель достигается тем,что в устройство, содержащее первый,и второй регистры, регистр маски,памяти коэффициентов, матрицу ассоциативной памяти состоящую из Ч/2..исходной последовательности отсчетов),каждая из которых состоит иэ десятиячеек, соединенных своими установочными входами через регистр маски свыходами первого регистра а выходами - со входами второго регистравходы пятой и шестой ячеек соединеныс соответствующим номеру строки выходом памяти коэффициентов, первыйи второй коммутаторы, дополнительновведены третий и четвертый коммутаторы, при этом вход первого коммутатора соединен с выходами первой,третьей, пятой, шестой, седьмой идесятой ячеек каждой строки, а выход - со входами седьмой, девятойячеек каждой строки и с первым выходом разрешения записи строкиматрицы ассоциативной памяти, входвторого коммутатора соединен свыходами второй, четвертой, пятой,шестой, восьмой и девятой ячееккаждой строки, а выход - со входамивосьмой и десятой ячеек и вторымвыходом разрешения записи строкиматрицы ассоциативной памяти, входтретьего коммутатора соединен свыходами восьмой и девятой ячееккаждой строки,а выход - с третьимвыходом разрешения записи строкиматрицы ассоциативной памяти, входчетвертого коммутатора соединен свыходами седьмой и десятой ячееккаждой строки, а выход - с четчертым выходом разрешения записистроки ассоциативной памяти, входы первой, второй, третьей, чет.вертой ячеек враждой строки соединены с соответствующими входами строки матрицы ассоциативной памяти.Математические действия, выполняемые по каждому двухточечномупреобразованию,Обозначим:Хк а + Ь О сов 8:гдеЗначения выходных выборок -.7 и 2в ъвычисляются Чледукщим образомУ:.,+ (а+)Ь)=х;+Р;(Х +)У )(фк+,)ЬД,у.:, (а -Ь):х;+р.+(х+р )(а -Ь.Объединяя мнимые и действительные части, получаем2 Х+О Х Ь УРФ (У +О Ч +Ь Х ) Х +к Р кР 1 ИР кР Р 4 Е1 р 2" х;+Фх +Ь У +)(У,+а У -Ь х):хЗначения ге и гщ пересылаются навходы для выполненйя над ними очередных итераций.На чертеже представлена схема15 устройства.Устройство содержит матрицу ассоциативной памяти, состоящую из "- одйнаковых строк 1, коммутаторы 2ИС-Нс 1 память 3 коэффициентов,2 О регистр 4 маски, первый регистр 5,второй регистр б,Устройство работает следующимобразом,Каждая строка 1 (ячейка памяти АПП)25 разделена на 10 ячеек: в первой ячейке хранится значение х 1, во второйу , в третьей хр, в четвертой - ув пятой - а, в шестой-вх, седьмая,восьмая, девятая и десятая ячейкирезервируются для промежуточных реЗО зультатов вычислений.В каждой итерации информация всехстрок обновляется. Значения г и гр1заменяются результатами вычисленийпредыдущих итераций, вводятся новые35 коэффициенты ак и ЬВ каждой итерации вычисления выполяются в следующем порядке.1-й этап. Одновременные умножения:(Ь) (у) - 8 ячейкаПосле выполнения первых трех этапов получаются промежуточные результаты, которые размещены в ячейках 50 7 - 10 тех же строк, где хранятсяисходные величины. Соответствующие пересылки промежуточных результатов вычислений осуществляются с помощью первого и второго коммутаторов.После завершения размещения промежуточных результатов. вычисленийв ячейках 7 - 10, выполняются ещедва этапа:4-й этап. Одновременные сложения7 ячейка + 10 ячейкау(ПС)8 ячейка + 9 ячейках (ПС )5-й этап. Одновременные вйчитания:9, ячейкаячейках(ОСа)10 ячейкаячейка-у (ПС )744598 Устройство для быстрого преобразования Фурьесодержащее первый и второй регистры, регистр маски, память коэффициентов,матрицу ассоциативной памяти, состоящую изстрок (где М - количество точек и исходной последовательности отсчетов), каждая из которых состоит из десяти ячеек, соединенных своими установочными входами через регистр маскис выходами первого регистра, а выходами - со входами второго регйстра, входы пятой и шестой ячеек соединены с соответствующим номеру строки выходом памяти коэффициентов, первый и второй коммутаторы, о т л и ч а ю щ еВ. - , - . -."; " " - . --- - е ММЮ Результаты операций, произведенных в процессе выполнения 4-го и 5-го этапов, размещаются н зонах у, х хе и у соответствующих строк ассоцйатинной памяти. Такое размещение результатов вычислений обеспечивается путем подключения раз решающих запись входбв этих ячеек, соответственно к выходам первого, второго, третьего и четвертого коммутаторов (1)С - ОС 4) .Одновременно с выполнением 5-го этапа любой из итераций в зоне а и Ь всех строк 1 вводятся новые значения коэффициентов ч", хранимые н постоянной памяти 3. После окончания 5-го этапа устройство готово к выполнению очередной итера- ЦИИКоэффициенты Фурье образуются в зонах х и у всех строк после завершения всех оу й итераций, аналогичных описанной.гФормула изобретения е с я тем, что, с целью повышениябыстродействия и сокращения обору-,дования, в него дополнительно введены третий и четвертый коммутаторы,при этом вход первого коммутатора соединен с выходами первой, треть"ей,пятой, шестой, седьмой и десятойячееккаждой строки, а выход - совходами седьмой, девятой ячеек каждой строки и с первым выходом раз- решения записи строки матрицы ассоциативной памяти, вход второго коммутатора соединен с выходами второй,четвертой, пятой, шестой, восьмой идевятой ячееккаждой строки, а выход - со входамИ восьмой и десятойячеек и вторым выходом разрешениязаписи строки матрицы ассоциативнойпамяти, вход третьего коммутаторасоединен с выходами восьмой и:девятой ячеек каждой строки, а выход 20 с третьим выходом разрешения записистроки матрицы ассоциативной памяти,,вход четвертого коммутатора соединенвыходами седьмой и десятой ячееккаждой строки, а выход - с четвер25 тым выходом разрешения записи строкиассоциативной памяти, входы первой,второй, третьей, четнертой ячеек1каждой строки соединены с соответствующими входами строки матрицы ассо"30 циативной памятиИсточники информации,принятые ва"внимание при экспертизе1.Топ)с 1 п А.Яачаде Л. Ап Арр 63. -са 1 хоп ой Соггейа 11 оп го Райег ЯузЗ 5 Ген). Тйе йай 1 о апй Ы.Е. Чадф,И 12, И 7, 1972.2. Прангишвили И.В. Однородныемикроэлектроннйе ассоциативные процес-соры. М., Советское радиоф, 1973744598 Составитель Н. Шелобановалинич Техред Л. Теслюк КоРректоР Г. Назароеее е вВ еаеЗаказ 3795/14 ЦНИИПИ Го по делам 113035, МоПодписиаеавееащ в тф 11 ород, ул. Проектная, 4Редактор А. Филиал ППП г Тираж ударственн изобретений ква, Ж,51о комитета СССР и открытий аушская наб., д. 4 Ыааав ее ее в аввев вее в