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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК др С 06 Р НОМИТЕТ СССР НИЙ И ОТНРЬТИ ГОСУДАРСТВЕННЫПО ДЕЛАМ ИЗОБ ЗОБРЕТЕ ЕЛЬСТВУ(54)(57) ТВО ЛЛ УР ЬЕ(71) Киевский ордена Ленина полинический институт им. 50-летияВеликой Октябрьской социалистичекой революции(прототип) 1. АРИФМЕТИЧЕСКОЕ УСТРОЙС Я БЫСТРОГО ПРЕОБРАЗОВАНИЯ Ф , содержащее три входных регистра, умножитель, два регистра, два коммутатора, сумматор, четыре выходных регистра и блок синхронизации, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия, информационные выходы первого и второго входных регистров под ключены соответственно к первому информационному входу первого коммутатора и первому входу умножителя, выход которого подключен к информационному входу первого регистра, информационный выход которого подключен к информационному входу второго регистра, информационный выход которого подключен к первому входу сумматора, выход которого подключен к первому информационному входу второго коммутатора и информационным входам первого, второго, третьего и четвертого выходных регистров, информационные выходы которых обьединены и подключены к второму информационному входу второго коммутатора и второму информационному входупервого коммутатора, выход которогоподключен к второму входу сумматора,второй вход умножителя подключен кинформационному выходу третьего вход.ного регистра, информационный входкоторого является первым информационным входом устройства, вторым информационным входом которого являются информационные входы первого ивторого входных регистров, первыйвыход блока синхронизации подключенк тактовым входам первого и второгорегистров и третьего входногорегистра, второй и третий выходы блока синхронизации подключены к тактовым входам соответственно первого ивторого входньм регистров, четвертыйи пятый выходы блока синхронизацииподключены к управляющим входамсоответственно первого и второгокоммутаторов, шестой вьмод блокасинхронизации подключен к входу синхронизации сумматора, седьмой, восьмой, девятый и десятый выходы блокасинхронизации подключены к входамсинхронизации приема соответственно.первого, второго, третьего и четвертого выходных регистров, входы синхронизации выдачи которых подключены соответственно к одиннадцатому,двенадцатому, тринадцатому и четырнадцатому выходам блока синхронизации, вьмод второго коммутатора являеется информационным выходом устройства. 2. Устройство по п.1, о т л и ю щ е е с я тем, что блок син низации содержит узел постоянно1149275 памяти, элемент ИЛИ, дешифратор,счетчик и генератор тактовых импульсов, выход которого подключенк счетному входу счетчика, выходыпервого, второго и третьего разрядовкоторого подключены соответственнок первому, второму и третьеу разрядам адресного входа узла постояннойпамяти, выходы первого, второго,третьего, четвертого, пятого, шестого и седьмого разрядов которогоявляются соответственно одиннадцатым, двенадцатым, тринадцатым, четырнадцатым, шестым, седьмым и пяИзобретение относится к вычислительной технике и может быть использовано при построении устройств, реализующих алгоритм быстрого преобразования Фурье (БПФ),Известно устройство, выполняющееоперации с комплексными числами,которое содержит регистры действительной и мнимой частей сомножителей, формирователи поразрядных произведений, комбинационно-накапливающие сумматоры, блок перевода в дополнительный кодОднако это устройство требуетбольшого объема оборудования, 15Наиболее близким по техническойсущности к изобретению является устройство дпя быстрого преобразования Фурье, содержащее четыре входных регистра чисел, два входных регистра весового коэффициента, множительный блок, два регистра слагаемых, сумматор, два коммутатора, четыре регистра результатов и устройство управления 2,25Недостатки известного устройствабольшие затраты оборудования, атакже множество входов и выходов,что требует распараллеливания памяти, а это, в свою очередь, приводит 30к увеличению внешних связей и усложнению адресации, либо к необходимости установки распределителя данных на входе устройства.Целью изобретения является повыше З 5ние быстродействия. тым выходами блока синхронизации,выходы второго и третьего разрядовсчетчика подключены соответственно кпервому и второму входам дешифратора, первый, второй, третий и четвертый выходы которого являются соответственно девятым, десятым, седьмым и восьмым выходами блока синхронизации, первым выходом которогоявляется вьход элемента ИЛИпервый и второй входы которогоподключены соответственно к второму и четвертому ныходам дешифратора. Поставленная цель достигается тем, что в арифметическом устройстве для быстрого преобразования Фурье, содержащем три входных регист. ра, умножитель, два регистра, два коммутатора, сумматор, четыре выходких регистра и блок синхронизации, информационные выходы первого и второго входных регистров подключены ответственно к первому информационному входу первого коммутатора и первому входу умножителя, выход которого подключен к информационному входу первого регистра, информационный выход которого подключен к информационному входу второго регистра, информационный выход которого подключен к первому входу сумматора, выход которого подключенк первому информационному входу второго коммутатора и информационным входам первого, второго, третьего и четвертого выходных регистров, информационные выходы которых объединены и подключе ны к второму информационному входу второго коммутатора и второму информационному входу первого коммутатора, выход которого подключен к вто рому входу сумматора, второй вход умножителя - к информационному выходу третьего входного регистра, инФормационный вход которого является первым информационным входом устройства, вторым информационным входом которого являются информационные входы первого и второго входных ре149275 Входное слово Выходное слово 1 О О 0 О О О О О 1 О О 1 1 1 О О 1 О 1 1 1 О 1 1 1 О 0 0 0 1 1 1 0 0 0 1 0 0 0 О 1 0 1 О 0 0 1 0 1 1 0 О 0 О 1 О 0 О О О О О 1 О 1 0 0 О 0 0 1 О 1 0 1 0 О 0 О 0 1 О 1 0 0 О 0 О О О 1 О О 1 О О 1 1 0 О О О 1 0 О О 0 0 1 0 гистров, первый выход блока синхронизации подключен к тактовым входам первого и второго регистров и третьего входного регистра, второй и третий выходы блока синхронизации - к тактовым входам соответственно первого и второго входньк регистров, четвертый и пятый выходы блока синхронизации - к. управлякнцим входам соответственно первого и второго коммутаторов, шестой выход блока синхронизации - к входу синхронизации сумматора, седьмой, вось. мой, девятый и десятый выходы блока синхронизации - к входам синхронизации приема соответственно первого, второго, третьего и четвертого выходных регистров, выходы синхронизации выдачи которых подключены соответственно к одиннадцатому, двенадцатому, тринадцатому и четырнадцатому выходам блока синхронизации, вькод второго коммутатора является информационньв выходом устройства.Блок синхронизации содержит узел постоянной памяти, элемент ИЛИ, дешифратор, счетчик и генератор тактовых импульсов, выход которого подключен к счетному входу счетчика, выходы первого, второго и третьего разрядов которого подключены соответственно к первому, второму и третьему разрядам адресного входа узла постоянной памяти, выходы первого, второго, третьего, четвертого, пятого, шестого и седьмого разрядов которого являются соответственно 5 0 15 20 25 30 35 одиннадцатым, двенадцатым, тринадца тым, четырнадцатьвк, шестым, четвертым и пятым выходами блока, выходы второго и третьего разрядов счетчика подключены соответственно к первому и второму входам дешифратора, первый, второй, третий и четвертый выходы которого являются соответственно девятым, десятым, седьмым и восьмым вьг ходами блока, первым выходом которого является выход элемента ИЛИ, первый и второй входы которого под-, ключены соответственно к второму и четвертому выходам дешифратора.На фиг.1 представлена структурная схема предлагаемого устройства, на фиг,2 - структурная схема одного из возможных вариантов построения блока синхронизации, на фиг.З - временная диаграмма, иллюстрирующая работу предлагаемого устройства.Арифметическое устройство для быстрого преобразования Фурье содержит (фиг.1) два входных регистра 1 и 2 чисел, входной регистр 3 весово. го коэффициента, умножитель 4, регистры 5 и 6, сумматор 7, коммутатор 8 (слагаемых), выходные регистры 9-12 (результатов), выходной коммутатор 13 и блок 14 синхронизации. Последний содержит (фиг.2) генератор 15 тактовых импульсов, счетчик 16 тактов, дешифратор 17, узел 13 постоянной памяти и элемент ИЛИ 19.Таблица кодировки постоянного запоминающего устройства имеет следующий вид.Устройство выполняет базовую операцию алгоритма быстрого преобразования фурье по основанию 2:1;8+с дКе;В,С;-1 С, 1 а;1 8 -РеС 1 а 1 Сагде В;, ., - исходные отсчеты,А А, - преобразованные отсчеты; 15% - весовой коэффициент;Яколичество отсчетов висходном массиве,е - действительная часть,1, - мнимая часть числа.Рассмотрим работу устройства при выполнении базовой операции, Будем считать, что прием информации в ре 25 гистры осуществляется в момент прихода заднего фронта синхроимпульса,На временной диаграмме показана работа устройства по тактам, Импульсы, показанные незаштрихованными прямоугольниками, никакой смысловой нагрузки не несут, они подаются в промежуток времени, необходимый для загрузки устройства. Заштрихованные прямоугольники показывают 35 импульсы, необходимые для работы устройства. Первые пять тактов являются холостыми, т.е. во время этих тактов полезная информация на выход не подается, но в дальнейшем вначале каждо го такта при непрерывном поступлении данных на вход устройства на выходе появляются соответствующие результаты, цикл работы устройства составляет четыре такта. В конце 5 первого такта по сигналу с выхода блока 14 синхронизации во входной ре. гистр 1 чисел принимается действительная часть В С;исходного Отсчета С;, во входной регистр весового коэф О фициента 3 - действительная часть В М весового коэффициента %1Во втором такте выполняется умножение в умножителе 4 и произведение К С; К М по сигналу иэ блока 14 при. 55 нимается в регистр 5. По этому же сигналу в регистр 3 принимается мнимая часть Е И весового коэффициента Ъ, а по сигналу иэ блока 14в регистр 2 чисел - действительнаячасть В В; исходного отсчета В,В третьем такте выполняется умножение, и произведение К С, Епо сигналу с блока 14 принимается врегистр 5, по этому же сигналу в регистр б принимается произведениеВ, С, Ве Ф, и в регистр 3 - мнимаячасть 1 Ъ весового коэффициента Мl,во входной регистр 1 чисел по сигналу с блока 14 принимается мнимаячасть 1 С исходного отсчета С;,В четвертом такте в умножителе4 выполняется умножение, и произведение 1 С 1 Ф по сигналу из блока14 принимается в регистр 5 слагаемых,по этому же сигналу в регистр 6 принимается произведение ВеС; 1 В, аво входной регистр 3 - действительная часть к 4 весового коэффициентаА . По сигналу из блока 14 вовходной регистр 2 принимается мнимаячасть 1 В; исходного отсчета В.Коммутатор 8 по сигналу из блока 14подключает к входу сумматора 7 выходвходного регистра 2 чисел. Сумматор7 по сигналам из блока 14 выполняетоперацию сложения в первой половинечетвертого такта, а операцию вычитания - во второй половине. Соответстве":, сумма В В + К С; К,1; посигнал;. из блока 14 принимается в регистр 9 в середине четвертого такта,а разность К В, - В С К И - по сигналу из блока 14 в конце четвертоготакта в регистр 10,В пятом такте в умножителе 4 выполняется умножение, и произведениеЕ С К 17 по сигналу из блока 14принимается в регистр 5 произведение ЕС; Е М по этому же сигналупринимается в регистр 6, а во входной регистр 3 - действительная частьВе ф" э ВО Входной регистр 1 по сигналу из блока 14 принимается действительная часть В С следующегоисходного отсчета С+ Коммутатор 8по сигналу иэ блока 14 подключает квходу сумматора 7 выход входного регистра 2, Сумматор 7 по сигналам изблока 14 выполняет операцию сложенияв первой полонине пятого такта иОперацию вычитания - во второй половине, Соответственно, в серединепятого такта сумма Е В; + КеС; Е Упо сигналу иэ блока 14 принимаетсяв регистр 11, а в конце пятого тактаразность 1 В; - К С, 1 М по сигналу из блока 14 принимается в регистр 12,В шестом такте в умножителе 4 выполняется умножение и проиэведение К,С, Ке М/ по сигналу из блока 14 принимается в регистр 5, в регистр 6 по этому сигналу принимается произведение 1, С; Кеа, а в регистр 3 - мнимая часть 1 бвесового коэффициента. Во второй регистр 2 по сигналу из блока 14 принимается действительная часть ВВ;, исходного отсчета В; . Коммутатор 8 по сигналу из блока 14 подключает к выходу сумматора 7 объединенный выход регистров 9-12 результатовСумматор 7 по сигналам из блока 14 выполняет операцию вычитания в первой половине шестого такта и операцию сложения - во второй, В первой половине шестого такта по сигналу из блока 14 иэ регистра 9 выдается сумма К В, +К С,. К М, и после выполнения вычитания на выходе сумматора появляется действительная часть преобразованного отсчета КеА,=В В;+ +К С К 14-1 С; 1,И, которую по сигналу иэ блока 14 коммутатор 13 по дает на выход устройства и которая по сигналу иэ блока 14 запишется в регистр 9. Последняя запись не является необходимой для функционирования устройства, Она введена с целью упрощения блока 14. Во второй половине шестого такта по сигналу иэ блока 14 иэ регистра 10 выдается разность Н В, - КС Ре Ф, и в конце такта по сигналу из блоха 14 в регистр 10 принимается сумма К Ай 1 - КВ-КС КУ +1 С; 1 ИВ седьмом тахте в умножителе 4 выполняется умножение, и произведение К С 1 Ъ по сигналу из блока 14 принимается в регистр 5, в регистр 6 по этому же сигналу - произведение Р С; К 4, а во входной регистр 3 - мнимая часть 1% весового коэффициента В+, Во входной регистр 1 по сигналу иэ блока 14 принимается мнимая часть 1, С; исходного отсчета С, . Коммутатор 8 по сигналу из блока 14 подключает к выходу сумматора 7 объединенный выход регистров 9-12 результатов. Сумматор 7 по сигналам из блока 14 выполняет операцию сложения и операцию вычитания соответственно в нервой и второй половинах седьмоготакта. В первой половине седьмоготакта по сигналу из блока 14 иэ регистра 11 выдается сумма 1 В,++КеС;, 1 У, и после выполнения сложения на выходе сумматора появляется мнимая часть преобразованного от+КеС 1 ф 1 +1 С Ке 1 фкоторую по сигналу иэ блока 14 коммутатор 13 подает на выход устройства и которая по сигналу из блока 14запишется в регистр 11.Последняя запись не является необходимой для функционирования устройства, она введена с целью упрощения блока 14.Во второй половине седьмого такта по сигналу из блока 14 иэ регистра 2 выдается разность В -Я Сц 20 и в конце такта по сигналу из блока14 в регистр 12 принимается разность3,-3,С, 1 а -,С, 1, Ю 1,йВ восьмом такте в умножителе 4выполняется умножение, и произведение 1 Г;1,В " по сигналу иэ блока14 поднимается в регистр 5, врегистр 6 по этому же сигналу принимается произведение 1 С 1 Ы, а ЗО в регистр 3 - действительная частьК Фф весового коэффициента В", Вовходной регистр 2 по сигналу из блока 14 принимается мнимая часть 8;,.,исходного отсчета В. Коммутатор 8 д по сигналу иэ блока 14 подключаетк входу сумматора 7 выход входногорегистра 2 чисел Сумматор 7 выполняет операции сложения и вычитанияв первой и второй половинах такта 40 соответственно. В первой половиневосьмого такта по сигналу из блока14 (по заднему фронту) в регистр 9пРинимается сумма В В, +В СК в",еем еиз регистра 1 О на выход устройства 45 по сигналу иэ блока 14 выдается действительная часть ВА,. Коммутатор13 по сигналу иэ блока 14 пропускает ее на выход устройства. Во второй половине восьмого такта по сигна Ьо лу из блока 14 в регистр 10 принимается разность В В;РеС; В а",В первой половине девятого тактапо сигналу иэ блока 14 в регистр11 принимается сумма 1,В;-КС КИ 5 по сигналу из блока 14 из регистра12 на выход устройства выдается мнимая часть 1 А;,преобразованного отсчета А;и по сигналу иэ блока 14во второй половине в регистр 12принимается разность Работа остальных элементов устройства аналогична рассмотреннойдля пятого такта,Далее работа всего устройствааналогична,Таким образом, по сравнениюс известным предлагаемое устройство более быстродейственно, оно имеет четыре такта работы при непрерывном 5 поступлении данных (такт работы устройства есть такт работы умножителя), в то время как известное устройство имеет шесть тактов работы (такт работы устройства есть такт работы умножителя),,У 1 с В У В В УВ1 Уе Сс ,1 тСг 1 Рева1 1 твгы 1 17 евг,ех в тйсгг юев1 т Вг геИ"5 гИ" ХеФ"г ЮФ" 1 т Иг С Фн" Ыг"йй" Ьйглггг Ь,",ееи" Вед;,щ"ее г,гчгс.ы атее ф.ги Й его ее юерректор В.Бутяг 1895/35 В НИИПИ а ло035, И Филиал ППП "Патент" г, Ужгород, ул. Проектная, 4 Тираж 710осударственноголам изобретенийква, Ж, Рауш 1 ; в, -,еес 1 вгцС 1 тл;.са Подлиснокомитета СССРи открытийская наб д. 4/5