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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик и 1 734707фи ф(22) Заявлено 06. 10,77(21) 2530578/18-24с присоединением заявки РЙ -до делам кэооретеиий к открытки(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ1Изобретение относится к вычислительной технике и может быгь использованов системах и устройствах цифровой обработки информации в качестве преобразователей временной последовательностиотсчетов входного сигнапа в частотнуюпоследовательность, и наоборот,Известно устройство Я для быстрого преобразования фурье (БПФ), содержащее блок оперативной памяти, блок10констант, устройство умножения комплексных чисел, блок сложения-вычитания,устройство управления.Наиболее близким техническим решением к предложенному является устройст 15во для реализации БПФ 2, содержащее блок управления, выходы которогоподключены соответственно к управляющим входам входного регистра, первогои второго промежуточных регистров, регистра хранения комплексных чисел,адресного блока, выход которого черезблок памяти подключен ко входу вьтходного регистра, Первая и вторая группы 2выходов выходного регистра соответственно черж первый и второй промежуточные регистры соединены со входами сумматора-вычитатепя, первая группа выходов которого через третий промежуточный регистр соединена с первой группой входов первого блока умножения. Вторая группа выходов сумматора-вычитателя через четвертый промежуточный регистр соединена с первой группой входов входного регистра и с первой группой выходов устройства. Эгорая группа входов входного регистра является группой юсодов устройства. Выход регистра хранения комплексных чисел соединен со второй группой входов первого блока умножения, первая группа выходов входного регистра соединена с информационными входами блока памяти.Крометого, известноеустройствосодержитблокхраненияконстант, к которому предъявляются требования как по обь му хранимой памяти, так и по временивыборки.5 734707Известное устройство имеет сложнуюсхему.Целью изобретения является упрощение устройства,Цель Изобретения достигается тем,что в предложенное устройство введенысдвиговый регистр и второй блок умножения, причем первая и вторая группывходов сдвигового регистра подключенысоответственно к третьей группе выходоввыходного регистра и второй группе выходов входного регистра. Управляющийвход сдвигового регистр соединен ссоответствующим выходом блока управления, выход сдвигового регистра соединен со входом регистра хранения комплексных чисел. Первая группа выходов первого блока умножения через второй блокумножения подключена к третьей группевходов входного регистра четвертаягруппа входов которого ивторая группавыходов первого блока умножения подклю.чены ко второй группе выходов устройства. 35 40 45 50 55 На фиг. 1 показана структурная схемаустройства; на фиг. 2 - приведен графалгоритма БПФ на фиг. 3 -схема реализации графа алгоритма БПФ,Устройство (фиг. 1) содержит сдвиговый 1 и выходной 2 регистры, блокпамяти 3, регистр 4 хранения комплекснь 1 х чисел, промежуточные регистры5-8, первый блок умножения 9 сумматор-вычитатель 10, второй блок умножния 11, адресный блок 12, входной регистр 13, блок управления 14, первуюи вторую группы выходов 15, 16, группу входов 17, управляюшие.выходы 1822 блок управления.граф алгоритма БПФ (фиг. 2) приведен для исходного массива длиной в16 значений. На фиг. 2, в частности,показаны индексы исходного массива23, индексы выходного массива 24,операции умножения на 1 25, различные итерации 26 графа.Устройство реализует, например,алгоритм БПф (см. фиг. 2) в последовательности, изображенной на фиг. 3.Такая последовательность вычисленияхарактеризуется тем, что в процессвычисления втягиваются ячейки операндов памяти последовательно, причем довключения в вычисление новых двухоперандов все вычисления идут с операндами, которые уже участвовали ввыччслении на предыдуших этапах. 5 10 15 20 25 6Кроме того, номер константы всегда соответствует номеру первого операнда в двухточечном преобразовании фурье первой итерации.Из сказанного можно сделать вьвод: вместе с исходными данными в памятьснужно записывать и константы. Это всегда можно сделать, так как исходные операнды имеют меньшую разрядность, нежели разрядная сетка промежуточных вычислений. Так, например, реальным является -.хранение вместе с опе Мрандами с номерами 1, 1 -- одной конД.станты с номером 1 в последних четырех разрядах каждого числа (мнимого и действительного), При шестнадцатиразрядной сетке 12 разрядов занимает исходная информация, что вполне достаточно.Такое .хранение констант позволяет формировать очередную константу по мере вовлечения новых исходных данных в вычислительный процесс путем выделения четырех поспедних разрядов в каждом новом операнде. С очередной константой проводятся вычисления, которые не требуют участия ячеек с операндами, в которых содержатся последующие константы, поэтому промежуточные результаты вычислений не стирают последуюшие константы до того времени, когдаони будут изъяты, Для обработки новсго массива данных требуется занововвести константы. Устройство работает следующим образом. Ввод и вывод информации из устройства проводятся одновременно, по входам 17 вводится новый исходный массив, по выходам 15, 16 выводится результат. В процессе ввода новой информации из последних двух операндов константы выделяются сразу, как только эти операнды записываются во входной регистр 13, последние разряды подаются в сдвиговый регистр. После окончания записи исходного массива в сдвиговом регистре хранится половина разрядов константы.Процесс вычисления начинается с выработки в адресном блоке 12 данньк адресов двух первых операндов, которые последовательно выбираются в выходной регистр 2. Управляющие сигналы по выходам 21 и 18 организуют соответственно запись последних разрядов в сдвиговый регистр и непропускание последних разрядов в промежуточные регистры 573 д 707 и 6, После принятия последних разрядовпервого операнда по выходу 21 передаетсясигнал сдвига на требуемое число разрядов, последние разряды второго опранца заканчивают формирование констан-.ты в сдвиговом регистре, и она передается в регистр 4 хранения комплексньцсчисел, откуда она поступает в блок умножения 9 (комплексных чисел). К моменту принятия два операнда (комплексныечисла), записанные в промежуточных регистрах 5 и 6, попадают в сумматор-вычитатель 10, где осуществляется сложениекомплексных чисбл, результат операциипередается через регистр 7 в бпок 9, гдеумножается на сформированную константу. Во время умножения комплексныечисла, записанные в регистрах 5 и 6,в сумматоре-вычитателе 10 вычитаются,результат записывается в промежуточный20регистр 8, далее передается во входнойрегистр 13 и по адресу адресного блока(данных) 12 записывается в блок памяти 3. Далее результат умножения запи 25сывается во входной регистр 13, а затемв блок памяти устройства.На этом первый шаг алгоритма БПФзаканчивается. Последовательность операции, описанная здесь, относится к шагус константой 1 . После всех операцийс этой константой проводятся операциийс константами, номера которых 1 -- .В этом случае используются те же константы, что и на предыдущих шагах,35однако результат дополнительно умножается на мнимое числоЯ =(в блоке 11 умножения. Функции этого блокасводятся к перекоммутации выхода блока умножения и смене знака: допустим,выход блока 9 умножения С 1 + ) Ь , выходблока 11 умножения на мнимое число -- Ь +О , что делается перекоммутацией информационных шин и сменой знака у мнимой части "в" комплексногочисла.Введение блока 11 позволяет хранить вдвое меньшее число констант ииспользовать свойство констант: Устройство для реализации быстрого преобразования Фурье, содержащее блок управления, выходы которого подключены соответственно к управляюцшм входам входного регистра, первого и второго промежуточных регистров, регистра хранения комплексных чисел, адресного блока, выход которого через блок памяти .подключен ко входу выходного регистра, первая и вторая группы выходов которого соответственно через первый и второй промежуточные регистры соединены со входами сумматора-вычитателя, первая группа выходов которого через третий промежуточный регистр соединена,- (;"1ехе -1ер(-3 ф)ее(-Х е ):уер(Ж) Необходимость дополнительного умножения нав данном выражении учитывается блокомумножения на мнимое число. Управляюши,. сигналы, передаваемые по выходам 19 и 20, соответственно служат: первый - для передачи последних разрядов при вводе двух последних операндов в сдвиговом регистре и для подключения в различные моменты временной диаграммы необходимых входов к входному р"гистру (выборки) второй - для передачи сигналов запйси в регистр хранения комплексных чисел из сдвигового регистра подготовленной новой константы.Описанная последовательность работы различных частей устройства выполняется во всех режимах, причем в процессе выполнения шагов второй и следующих итераций, когда выделения констант не происходит, сигналы по выходу 21 блокируют запись в сдвиговый регистр информации, а сигналы по выходу 18 открывают последние разряды промежуточных регистров для приема информации их выходного регистра (выборки).Предложенное устройство при принятой организации вычислительного процесса работает без блоков долговременной памяти, наличие которых требует соответственно собственного адресного блока констант. В результате сокращается оборудование устройства и увеличивается его надежность. Преимушества предложенного устройства проявляются при многоканальной обработке информации, когда используется много устройства для реализации БПФ. В этом случае достаточно на все устройства иметь один источник констант, из которого эти константы передаются в каждое из устройств для реализации БПФ. Формула изобретения7 7347с первой группой входов первого блокаумножения, вторая группа выходов сумматора-вычитателя через четвергый промежуточный регистр соединена с первойгруппой входов входного регистра и спервой группой выходов устройства,вторая группа входов входного регистраявляется группой входов устройства, выход регистра хранения комплексных чисел соединен со второй группой входовпервого блока умножения, первая группа выходов аходного регистра соединена с информаиионными водами блокапамяти, о т л и ч а ю пт е е с я тем,что, с келью упрощения устройства, оно 15содержит сдвиговый регистр и второйблок умноженйя, причем первая и втораягруппы входов сдвигового регистра подклкьчены соответственно к третьей группе,выходов выходного регистра и второй 20 07 8группе выходов аходного регистра, управляющий вход сдвигового регистра соединен с соответствующим выходом блока управления, выход сдвигового регистра соединен со входом регистра хранения комплексньк чисел, первая группа выходов первого блока умножения через второй блок умножения подключена к третьей группе входов входного регистра, четвертая группа входов которого и вторая труппа вътходов первого блока умножения подключены ко второй группе выходов устройстваИсточники информации,принятые во внимание при экспергиэе 1. Авторское свидетельство СССР И 9 421994 в кл+ 906 , 15/34 в 1874. 2, Зарубежная электроника, 1973,М 2, с. 45 (прототип).