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

.В. Солодилов Ю,П.Щ видетельство СССР 06 Р 15/332, 1983.973, В 3, с. 32-38, ДЛЯ В ЪП 10 ЛНЕНИЯ БЫСТ УРЪЕосится к област и предназначенализа электриавленных в цифОСУДАРСТВЕКНЫЙ КОМИТЕТ СССР110 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИ А ВТОРСНОЮУ Н,ур, А нов (53) 681.32 (088,8) (56) Авторское с У 1056207, кл, САвтометрия, 1 (54) УСТРОЙСТВО РОГО ПРЕОБРАЗОВАНИЯ Ф (57) Изобретение отн вычислительной техни но для спектрального чески сигналов, пред ровои форме. Цель изобретения - повышение быстродействия. Устройство содержит элемент И-ИЛИ 1, входной коммутатор 2, блок памяти 3, выходнойкоммутатор 4, арифметический блок 5,дешифратор адреса 6, дешифраторы чте",ния 7,8, дешифратрры записи 9, 1 О,блок элементов ИЛИ 11, блок коррекции12, коммутатор адреса 13, блок элементов И 14, коммутатбр адреса 15, элемент И 16, триггер режима 17, блокиэлементов И-ИЛИ 18,19, регистры 2023, триггеры 24, 25, дешифратор адреса 26, элемент И-ИЛИ 27, счетчик операндов 28, счетчик итераций 29, дешиф"ратор адреса 30, блок постоянной па"мяти 31. 5 ил1 де 1 = ф(Ь - комплексные числа.Согласно применяемого алгоритма3 ПФ вычисления проводятся за Р =1 оя И итераций, На каждой итерации2выполняются М/2 базовых операций длительностью Т о 55 Изобретение относится к вычислительной технике и предназначено дляспектрального анализа электрическихсигналов, представленных в цифровойформе.Цель изобретения - повьппение быстродействия устройства.На фиг, 1 представлена функциональ, ная схема устройства, на фиг, 2 - вре 10,менные диаграммы работы устройства;на фиг, 3 - временные диаграммы управпения первым коммутатором адресана фиг. 4 - временные диаграммы уп;равления вторым коммутатором адреса; 15на фиг, 5 - схема блока. коррекции.Устройство содержит элемент И-ИЛИ1, входной коммутатор 2, блок 3 па,мяти, выходной коммутатор 4, арифметический блок 5, дешифратор 6 адреса, 20,два дешифратора 7 и 8 чтения, два де,шифратора записи 9 и 10, блок 11 элементов ИЛИ, блок 12 коррекции, коммутатор 13 адреса, блок 14 элементов И,коммутатор 15 адреса, элемент И 16, 25триггер 17 режима, блок элементов 18ИЛИ, блок 19 элементов И-ИЛИ, ре-гистры 20-23, триггеры 24 и 25, дефратор 26 адреса, элемент И-ИЛИ 27,четчик 28 операндов, счетчик 29 З 0тераций, дешифратор 30 адреса,лок 31 постоянной памяти.Блок 12 (фиг. 4) содержит элеменгы И 32 и 33, элементы ИЛИ 34, 35,лементы И-НЕ 36-39, элемент НЕ 40,григгера 41-43.В устройстве реализуется алгоритмПФ с прореживанием по времени сзамещением, по отношению 2, с объеМом выборки Ы, двоичной инверсией навыходе,Базовая операция такого алгоритма,Состоит в том, что входных числа А, И В объединяются для получения выходсных чисел Х и У следующим образом: В соответствии с временной диаграммой (фиг. 3) в устройстве в каждом такте одйовременно выполняются следующие операции: обращение к двум модулям блока памяти с чтением пары операндов А; и В;, выполнение базо1вой операции над операндами А; и В;, и запись результатов Хи1-2 Уот выполнения базовой операцииФнад операндами А;, и В; в два других модуля блока памяти.Указанное совмещение работы блоков памяти и арифметического блока сохраняется на протяжении выполнения всего алгоритма БПФ. При этом для достижения максимального параллелизма работы блоков в предлагаемом устройстве выполнены следующие условия: Т- Тр.,ОЗУгде То - время обращения к блокуОЗЧ ОЗУ с чтением или записью,Т - время выполнения базовойоперации БПФ.Устройство работает. следующим образом,В исходном состоянии триггер 17режима сигналом через вход элементаИЛИ устанавливается в единичное состояние (прямой выход) и переводитустройство в режим ввода информации.При этом входной массив через элемент И-ИЛИ 1, открытый по входу единичным сигналом с прямого выходатриггера 17 режима, поступает на информационный вход входного коммутатора 2. В последнем обеспечиваетсяраспределение операндов по модулямблока 3 согласно сигналам управленияс выхода дешифратора 9 записи.Массив входной информации вводится синхронно по адресам записи, которые формируются последовательно наи-разрядном счетчике 28 операндов,где и = 1 оя Я. Входные тактовые импульсы поступают на вход счетчикаоперандов с входа через первый входэлемента И-ИЛИ 27 и блок 12 коррекции (прохождение входных импульсовчерез блок 12 коррекции не показано).С выхода счетчика 28 операндов и-разрядные адреса записи через блок 14элементов И, открытый по входу .сигналом с прямого выхода триггера 17 режима, и вход блока 11 элементов ИЛИпоступают на вход дешифратора 6 адреса, Последний управляется по входусигналами управления с выхода дешифратора 9 записи. Выбор номера модуля блока 3 памяти, н который. записывается операнд входной информации по соот 5 ветствующему адресу записи, осуществляется в дешифраторе 9 записи, на вход которого подаются п-й и второй разряды сформированного адреса запи-, си (и - старший разряд) . При этом каждой двухразрядной комбинации указанньм разрядов соответствует единичный сигнал на одном из его четырех выходов, который обеспечивает прохождение на выбранный модуль операндов входной информации с входного коммутатора 2 и соответствующих им (п) разрядные адреса записи с дешифратора 6 адреса, При этом код 00 определяет первый модуль блока памяти, 01 - второй, 10 - третий, 11 - четвертый.По окончании ввода информации через И тактовых импульсов единичный сигнал с вьмода счетчика 28 операндов поступает на вход триггера 17 режима и переводит его в нулевое состояние. При этом единичный сигнал с ин- . версного выхода триггера 17 режима пе". реключает устройство в режим вычисления алгоритма БПФ, 30Работа устройства на этапе вычисления БПФ осуществляется по тактовым импульсам, поступавцим на вход счетчика 28 операндов с входа устройства через вход элемента 27 и через блок 12 коррекции.В исходном состоянии счетчик 28 операндов находится в единичном положении, а счетчик 29 итераций в нулевом.40На каждой итерации по тактовым импульсам выполняется Б/2 базовьм операций в соответствии с выражением (1).После подсчета В/2 тактовых импуль,сов на первой итерации счетчик 28 . 45 операндов устанавливается в исходное состояние, а в счетчик 29 итераций добавляется "1". С приходом очередных тактовых импульсов аналогично осуществляется вычисление алго ритма БПФ на второй итерации. Аналогично производятся вычисления наФвсех Р итерациях, С приходом последнего И/2 тактового импульса на Р-й итерации на выходе счетчика 29 итераций вырабатывается сигнал, который переводит триггер 17 режима в единичное состояние, т.е. переводит .устройство в режим ввода информации. В соответствии с временной диаграммой, представленной на Фнг, 4 (на каждой итерации), с приходом -го тактового импульса Формируются адреса чтения операндов А; и В;, Адрес чтения операнда А; формруется на и- разрядном счетчике 28 операндов, адрес чтения операнда В; формируется одновременно в дешифраторе 26 адреса путем суммирования по вод 2 адреса чтения операнда 1; с закодированным номером соответствующей итерации. Сформированная паря адресов чтения операндов А; и В; поступает одновременно на входы коммутатора 13 адреса и на соответствующие входы регистров 21 и 23.Управление коммутатором 13 адреса обеспечивается блоком 18 элементов И-ИЛИ по временным диаграммам, представленным на Фиг. 4, С выхода коммутатора 13 адреса и-разрядные адреса чтения операндов А; и В; монтажным способом распределяются следующим образом: и-й и второй разряды сформированных адресов чтения поступают соответственно на входы дешифраторов 7 и 8, Сформированные таким образом двухразрядные коды определяют номера модулей блока 3 памяти, из которых одновременно производится считываниеоперандов А; и В;. При этом код 00 определяет первый модуль, код 01 второй модуль, 10 - третий модуль, 11 - четвертый модуль. На дешифратор 6 адреса соответственно поступают оставшиеся (п)-разрядные, коды адресов чтения операндов А;и В; в следующем виде:ип 2 и 3е,3,1,где (и) - старший разряд.Сигналы управления одновременно с выходов дешифраторов 7 и 8 поступают на входы дешифратора 6 адреса и на управляющие входы выходного коммутатора 4, тем самым обеспечиваетсяф считывание информации операндов А; и В; из выбранных модулей блока 3 памяти и подача их на входы арифметического блока 5,Одновременно со считыванием операндов А; и В; из блока 3 памяти на вход арифметического блока 5 из блока постоянной памяти по адресу сформированному на дешифраторе 30 адреса5 1411 по 1.-му тактовому импульсу, считывается кодовое значение соответствую 1 Кщего коэффициента И .С приходом (+1)-го тактового имВ пульса в арифметическом блоке 5 выполняется базовая операция над опе 0рандами А; и В; и осуществляется запись адресов чтения этих операндов соответственно в регистры 21 и 23. 10С приходом (+2)-го тактового импульса результаты выполнения базовойь о Ф операции Х; и У (над операндами А и Ф ) Фиксируются в выходных регистрах арифметического блока 5 и посту пают на входы входного коммутатора 2 для записи в модули блока 3 памяти. По этому же импульсу адреса из регистров 21 и 23 переписываются соответственно в регистры 20 и 22 и пос тупают на входы коммутатора 15 адреса, на выходе которого формируются адреса записи результатов 1; и у 1,Управление коммутатором 15 адреса ,обеспечивается сигналами с блока 19 25 элементов И-ИЛИ, задержанными на два ,такта на триггерах 25 и 24, в соответствии с временными диаграммами.На выходе коммутатора 15 адреса сформированная пара адресов записи ЗО представляется следующим образом: и-й и второй разряды каждого адреса поступают соответственно на дешифраторы 9 и 10.СФормированные двухразрядные коды определяют номера модулей блока 3 памяти, в которые обеспечивается запись результатов Х; и У;,40При этом код 00 определяет первый модуль, 01 - второй модуль, 10 - тре-. тий модуль, 11 - четвертый модуль.На входы дешифратора 6 адреса оставшиеся (и)-разрядные адреса записи 4 В результатов Х; и У; поступают в следующем виде:п, п, п3,1,50где Ь) - старший разряд.Сигналы управления с выходов дешифраторов 9 и 10 одновременно и соответственно поступают на входы де 1 пифратора б адреса, а также на управляющие входы входного коммутатора 2, что обеспечивает запись результагов Х; и У; в выбранные модули запи-си блока 3 памяти по адресам, посту 777пающим с: выходов дешифратора 6 адреса, На этом цикл выполнения базовой операции .над операндами Аи В1 заканчивается.Совмещение аналогичных циклов выполнения базовой операции на протяжении вычисления всего алгоритма БПФ согласно временным диаграммам, представленным на Фиг. 2, обеспечивает полное совмещение работы арифметического блока 5 и блока 3 памяти. При этом в каждом такте работы устройства одновременно со считыванием операндов А; и В; осуществляется вьполнение базовой операции БПФ над операндами А;и В , а также производится запись результатов Х и У; выполнения базовой операции над операнцами А; и В;Формула из обретенияУстройство для выполнения быстрого преобразования Фурье, содержащее блок памяти, арифметический блок, блок постоянной памяти, первый дешифратор адреса, счетчик операндов и счетчик итераций, счетный вход которого подключен к выходу переноса счетчика операндов, информационный выход счетчика итераций подключен к первому входу первого дешифратора адреса, выход которого подключен к адресному входу блока постоянной памяти, выход которого подключен к входу задания коэффициента арифметического блока, о т л и ч а ю щ е,е с я тем, что, с целью повьппения быстродействия, в него введены первый и второй дешифраторы чтения, первый и второй дешифраторы записи, второй и третий дешифраторы адреса, первый и второй коммутаторы адреса, блок коррекции блок элементов ИЛИ, блок элементов И, первый и второй блоки элементов И-ИЛИ, элемент И, первый, второй элементы ИИЛИ, входной коммутатор, выходной коммутатор, триггер режима, первый, второй, третий и четвертый регистры, первый и второй триггеры, причем выход первого элемента И-ИЛИ подключен к первому информационному входу входного коммутатора, выход которого подключен к информационному входу блока памяти, выход которого подключен к информационному входу выходного коммутатора, первый и второй выходы ко1411777 8 15 20 25 30 45 50 торого подключены к входам соответственно первого и второго операндов арифметического блока, первый и второй выходы результата которого подключены соответственно к второму инФормационному входу входного коммутататора и первому входу первого элемента И-ИЛИ, второй вход которого является информационным входом устройства, входом задания режима которого является первый вход элемента И, выход которого подключен к первому установочному входу триггера режима, прямой выход которого подключен к третьему входу первого элемента И-ИЛИ и первому входу второго элемента ИИЛИ, выход которого подключен к первому входу блока коррекции, первый выход которого подключен к первому информационному входу первого коммутатора адреса, первый выход которого подключен к входу первого дешифратора чтения, выход которого подключен к первому управляющему входу выходного коммутатора и первому входу второго дешифратора адреса, второй вход которого соединен с вторым управляющим входом выходного коммутатора и подключен к выходу второго дешифратора чтения, вход которого подключен к второму выходу первого коммутатора адреса, третий выход которого подключен к третьему входу второго дешифратора адреса, первый, второй и третий выходы которого подключены соответственно к адресному входу, входу записи и входу считывания блока памяти инверсный выход триггера ре 1жима подключен к четвертому входу4 первого элемента И-ИЛИ и второму входу второго элемента И-ИЛИ, третий и четвертый входы которого являются соответственно первым и вторым тактовыми входами устройства, информационный выход счетчика операндов подключен к первым входам первого и второго блоков элементов И-ИЛИ первому входу блока элементов И, информационному входу первого регистра, первому входу третьего дешифратора адреса, второму информационному входу первого коммутатора адреса и второму входу блока коррекции, второй выход которого подключен к первому информа ционному входу второго коммутатора адреса, первый выход которого подключен к первому входу первого дешифратора записи, выход которого подключен к четвертому входу второго дешифратора адреса и первому управляющему входу входного коммутатора, второй уп. равляющий вход которого соединен с пятым входом второго дешифратора адреса и подключен к выходу второго дешифратора записи, вход которого подключен к второму выходу второго ком - мутатора адреса, третий и четвертый выходы которого подключены соответственно к первому входу блока элементов ИЛИ и шестому входу второго дешифратора адреса, седьмой вход которого подключен к выходу блока элементовИЛИ, второй вход которого подключенк выходу блока. элементов И, второйвход которого подключен к инверсномувыходу триггера режима, информационный выход счетчика итераций подключенк второму входу третьего дешифратораадреса, первый выход которого подключен к третьему входу блока коррекции,третий. выход которого подключен к второму входу первого дешифратора адреса и счетному входу счетчика операндов, выход старшего разряда которого подключен к второму установочному входу триггера режима, второй выход третьего дешифратора адреса подключенк третьему информационному входу первого коммутатора адреса и информационному входу второго регистра, выходкоторого подключен к информационному входу третьего регистра, выход которого подключен к второму информационному входу второго коммутатора адреса,третий информационный вход которогоподключен к выходу четвертого регистра, информационный вход которого подключен к выходу первого регистра, третий выход третьего дешифратора адресаподключен к третьему входу первого дешифратора адреса и вторым входам первого и второго блоков элементов Я-ИЛИ,выходы которых подключены соответст-,венно к управляющему входу первого.коммутатора адреса и тактовому входупервого триггера, выход которого подключен к тактовому входу второго триггера, прямой и инверсный выходы которого подключены соответственно к первому и второму управляющим входам второго коммутатора адреса, выход переноса счетчика итераций подключен к второму входу элемента И, причем блоккоррекции содержит два элемента ИЛИ,два элемента И, четыре элемента И-НЕ,элемент НЕ, три триггера, при этом9 14117 выход первого элемента ИЛИ подключен к первому входу первого элемента И-НЕ, выход которого подключен к входу элемента НЕ, выход которого является пер- вым выходом блока коррекции, выход первого элемента И подключен к первому входу второго элемента И-НЕ выход ко-торого подключен к первому входу вто"рого элемента ИЛИ, выход которого подОключен к тактовому входу первого триг гера, инверсный выход которого подключен к информационному входу первого триггера и первому входу третьего эле-мента И-НЕ, выход которого является ,вторым выходом блока коррекции и подгключен к тактовому входу второго триггера, инверсный выход которого подключен к Э-входу второго триггера, пер :ному входу четвертого элемента И-НЕ и77 1 О тактовому входу третьего триггера,инверсный выход которого подключен кР-входу третьего триггера, прямой выход которого подключен к второму вхоцу четвертого элемента И-НЕ, выход которого подключен к второму входу второго элемента ИЛИ, второй вход второго элемента И-НВ подключен к выходувторого элемента И, первый вход которого соединен с вторым входом третьего элемента И-НЕ и является первымвходом блока коррекции, вторым входомкоторого являются соединенные междусобой вторые входы второго элементаИ и первого элемента И-НЕ, соответствующие входы первых элементов ИЛИ иИ соединены между собой и являютсятретьим входом блока коррекции, третьим выходом которого является прямойвыход первого триггера.1411777 оставитепь А. Баранов ехред А.Кравчук Корр тор М.Васильева актор Н.Бобк раж 704 ПодписноеГосударственного комитета елам изобретений и открыт сква, Ж, Раушская наб. Заказ 36 по 113035, И