Процессор быстрого преобразования фурье

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ Союз Советских Социалистических Республик(22) Заявлено 29.0179 (21) 2717845/18-24с присоединением заявки йо 6 Об Р 15/31 Государственный комитет СССР по делам изобретений и открытий(23) Приоритет Опубликовано 15,1230, Бюллетень Мо 46 Дата опубликования описания 15.1280(71) Заявитель Ордена Ленина институт кибернетики АН Украинской ССР(54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Процессор быстрого преобразования Фурье относится к вычислительной технике и может быть использован при решении задач гармонического анализа, где необходимо выполнять прямое или обратное преобразование Фурье Функций, заданных дискретными отсчетами, а также при цифровой обработке сигналов в реальном масштабе времени.В известном процессоре 11 дискретные отсчеты хранятся в оперативном запоминающем устройстве (ОЗУ), а сомножители матрицы преобразований - в постоянном запоминающем устройстве 15 (ПЗУ) .Вычисление спектра происходит поэтапно.При этом дискретные векторы отсчетов попарно выбираются из ОЗУ и 20 после умножения на соответствуюцие коэФфициенты преобразования записываются в ОЗУ по тем же адресам.Наиболее близким по технической сущности к предлагаемому является 25 специализированный процессор для быстрого решении задач гармонического анализа, состоящий из арифметического устройства, оперативного запоминающего Устройства (ОЗУ), пос тоя нного запоминающего устройства (ПЗУ), регистра адреса ОЗУ, регистра адреса ПЗУ, формирователя сигналов прирацений регистров, счетчика отсчетов, счетчика итераций и устройства управления и сопряжения сЭВМ (2)Повышенное число арифметических операций при вычислении спектра, который для действительного Сигнала сиМметричен относительно ординат и все его отсчеты комплексно сопряжены, вследствие чего для дальнейшего использования результатов преобразования Фурье достаточно половины отсчета спектра. Вычисление всего спектра приводит к уменьшению быстродействия процессора.Цель изобретения - повышение быстродействия.Поставленная цель достигается тем, что процессор быстрого преобразования Фурье, содержащий арифметическое устройство, блок памяти, блок постоянной памяти, регистр адреса памяти, регистр адреса постоянной памяти, счетчик отсчетов, счетчик итераций, устройство управления, Формирователь сигналов приращений регистров, первый и второй выход которого подклю60 В 5-й итерации опускаются вычисления гармоник с 99 9-25, 10-26, 11-17, 12-28, 13-29, 14-30 и 15-31.Исходные данные для вычислений гармоник 5-21, 6-22. и 7-.23 расположены - 65 в ячейках памяти 20, 21, 12-13 и чен ко входам соответственно регистра адреса памяти и регистра адреса постоянной памяти, выход которого соединен со входом блока постоянной памяти, выход которого подключен к первому входу арифметического устройства, ныход которого соединен с первым уходом устройства управления, первый выход которого подключен к .первому входу блока памяти, выход которого соединен со вторым входом арифметического устройства и вторым входом устройства упранления, второй выход которого подключен ко входу счетчика отсчетов, первый выход которого соединен с первым входом формирователя сигналон приращений регистров, второй вход которого подключен к выходу счетчика итераций, вход которого подключен ко второму выходу счетчика отсчетов, выход регистра адреса яамяти соединен со вторым входом блока памяти, а третий вход устройства управления является тактовым входом процессора, н него введены узел Формирования дополнительного кода, блок сравнения и дополнительный регистр адреса, группа выходов которого соединена со входами первой группы блока сравнения, первый выход которого подключен к третьему входу формирователя сигналов приращений регистров, третий выход которого подключен ко жоду дополнительного регистра адреса, группа выходов регистра адреса памяти подключена ко входам второй группы блока сравнения, второй выход которого соединен со входом устройства формирования дополнительного кода, выход которого соединен с третьим входомблока памяти.На чертеже схематически изображено устройство.Устройство состоит из арифметичес- кого устройства 1, блока 2 памяти, блока 3 постоянной памяти, регистра 4 адреса памяти, регистра 5 адреса постоянной памяти, формирователя б сигналов приращений регистров, счетчика 7 отсчетов, счетчика 8 итераций, устройства 9 управления, узла 10 формирования дополнительного кода, ,блока 11 сравнения и дополнительного регистра 12 адреса.Устройство работает следующим образом.Через устройство 9 с ЭВИ поступают сигналы, включающие счетчик 7 отсчетов и счетчик 8 итераций. В зависимости от кодов на выходах этих счетчиков формирователь б подает сигналы на регистр 4, регистр 5 и дополнительный регистр 12, которые Формируют адреса обращения к блокам 2 и 3 согласно графу БПФ, При этом приращение дополнительного регистра 12 отстает на один период от приращения 4,т.е, регистр 12 постоянно повторяет коды предыдущей итерации. Блок сра внения выделяет в каждой итерации номера гармоник, расположенных во 2 и4 кнадрантах. Если код одного из этихадресов появится на регистре 4 илина регистрах 4 и 12 однонременно, то 5 на втором выходе блока 11 образуется сигнал запрета арифметическихопераций и происходит выборка следукщих отсчетов. При появлении указанных кодов только на регистре 12, на 1 О первом выходе блока 11 возникаетсигнал, по которому устройство образования дополнительных кодов 10 формируют адреса памяти н дополнительном коде.Рассмотрим работу процессора на 15 примере 0=32 отсчетов. Согласно гра"фу БПФ для 0=8 порядок формированияадресов обращения к ОЭУ и ПЗУ показан по 4 итерации в таблице.Иэ таблицы видно, что коды каждой 2 О пари адресов ОЗУ, необходимых длявыполнения элементарной операциипреобразования Фурье, различаютсятолько в одном разряде, адреса (условно обозначенном 7 Г). Причем положение этого разряда меняется в кажжой итерации. Коды старших разрядонадреса ОЗУ до разрядай, прочитанныен обратном порядке, показывают номер гармоники.Начиная с 3 итерации, вычисляются 30 гармоники, расположенные но 2-м и4-мквадрантах, значения которых всилу симметрии спектра действительного сигнала можно соответственнонайти в 3-м и 1-м квадрант,х. Так 35 гармоники с Р 3-7 но 2-м и 4-м квадрантах имеют симметрично располо-.женные гармоники соответственно сР 5-1. В связи с этим, гармоники 3-7можно не вычислять, а для образова ния гармоник более высокого порядкав последующих итерациях исходнымиможно брать гармоники с Р 5-1, адреса которых являются дополнительнымикодами номеров гармоник 3-7. Поэтомув 3-й итерации вычисления гармоник 45 3-7 опускаются.В 4-й итерации опускаются вычисления гармоник с 99 5-13, 6-14, 7-15.Однако для вычисления гармоник с99 3-11 необходима гармоника 3 из 50 3-й итерации, оценки которой размещены в ячейках ОЗУ 24, 26, 25 и 27.Так как гармоники 3-7 не. вычислялисьв 3-й итерации, то исходными данными для вычисления гармоник 3-11 ян ляется гармоника 5, оценки которойрасположены в ячейках памяти 20, 22,21 и 23. Коды адресов этих ячеек памяти являются дополнительными кодаминомеров вычисляемых гармоник.788114 Адрес ОЗУ Адрес ПЭУ Гармоника, Р 0000-0001000001-0001100-100-0011000101-00111 0-2 0-16 00000-10000 00000-01000 00000-01000 0-8 0-8 0-16 00000-10000 1-3 8-24 01000-11000 4-12 00100-0100 4-12 00100-01100 2-10 00010-01010 2-10 00010-01010 4-6 8-24 01000-11000 5-7 4-20 00100-10100 8-10 01000-01010 9-11 01001-01011 4-20 00100.-10100 6-14 00110-01110 12-28 01100-11100 12-14 01100-01110 6-14 00110-01110 12-28 01100-11100 13-15 011-01-01111 00001-01001 00001-01001 1-9 2-18 00010-10010 16-18 10000-10010 2-18 00010-10010 17-19 10001-10011 1-9 5-13 00101-01101 10-26 01010"11010 20-22 10100-10110 5-13 00101-01101 10-26 01010-11010 21-23 10101-10111 6-22 001100-10110 24-26 11000-11010 6-22 00110-10110 25-27 11001-11011 3-11 00011-01011 3-11 00011-01011 7-15 00111-01111 14-30 01110-11110 28-30 11100-11110 7-15 00111-01111 14-30 01110-11110 29-31 11101-11111 Формула изобретения 28-29. Адреса этих ячеек формируются в дополнительном коде, образованном от номеров гармоник. Таким образом, предлагаемое устройство за счет сокращения избыточных операций, связанных с вычислением комплексно-сопряженных гармоник,Процессор быстрого преобразования Фурье, содержащий арифметическое устройство, блок памяти, блок постоянной памяти, регистр адреса памяти, регистр адреса постоянной памяти, счетчик отсчетов, счетчик итераций, устройство управления, формирователь сигналов приращений регистров, первый и второй выход которого подключен ко входам соответственно регистра адреса памяти и регистра адреса постоянной памяти, выход которого соединен со входом блока постоянной памяти, выход которого подключен к первому входу арифметического устройства, выход которого соединен спервым входом устройства управления, первый выход которого подключен к первому входу блока памяти, выход которого соединен со вторым входом арифметического устройства и вторым входом устройства управлепозволяет уменьшить время преобразования Фурье и, тем самым, увеличить быстродействие процессора. Пос кольку все гармоники спектра сигнала попарно сопряжены, то предлагаемое устройство в 2 раза увеличиваетскорость преобразования и быстродействие процессора. ния, второй выход которого подкЛюченко входу счетчика, отсчетов, первый 45 выход которого соединен с первьмвходом формирователя сигналов приращений регистров, второй вход которого подключен к выходу счетчикаитераций, вход которого подключен 50 ко второму выходу счетчика отсчетов,выход регистра адреса памяти соединен со вторым входом блока памятй,а третий вход устройства управленияявляется тактовым входом процессо"ра, о т л и ч а ю щ и й с я тем,что, с целью повышения быстродействия, в него введены узел формирования дополнительного кода, блок сравнения и дополнительный регистр адреса, группа выходов которого соеди- фО иена со входами первой группы блокасравнения, первый выход которогоподключен к третьему входу формирователя Сигналов приращений регистров, третий выход которого подклю чен ко входу дополнительного регист"788114 ра адреса, группа выходов регистра адреса памяти подключена ко входам второй группы блока сравнения, второй выход которого соединен со входом устройства формирования дополнительного кода, выход которого соединен с третьим входом блока памяти. Составитель А. БарановКорректор В. Бутяга Редактор А. долиниЧ Техред М,Рейвес аж 751ударственного к ам изобретений и осква, Ж, Рауш Тир аказ 83 атент, г. Уагород, ул. Проектная, 4 П Фил 57 ВНИИПИ по д 113035Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР М 467356, кл. 6 06 Р 15/341978, 2.Электроника , 1968, 9 13,т 41 (прототип). Подпомитета СССткрытийская наб