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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 9) П) с 5 о 06 332 ОПИСАНИЕ ИЗОБРЕТЕН ВИДЕТЕПЬСТВУ ВТОР СКО ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистическойреволюции(56) 1. Авторское свидетельство СССРР 399859, кл. 6 06 Г 7/38, 1971.2. Авторское свидетельство СССРР 736113, кл.06 Г 15/332, 1977(54)(57) 1. АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯФУРЬЕ, содержащее два входных регистра чисел, входной регистр весового коэффициента, множительныйблок, два регистра слагаемых, сумматор, коммутатор, четыре регистрарезультатов и блок управления, о тл и ч а ю щ е е с я тем, что, сцелью упрощения устройства, блокуправления содержит генератор синхроимпульсов, счетчик тактов, дешифратор, элемент ИЛИ и блок памяти,причем информационные входы входныхрегистров чисел объединены и являются первым входомустройства, выход первого входного регистра чиселсоединен с первым входом множитель- .ного блока, второй вход которогосоединен с выходом регистра весовогокоэффициента, информационный входкоторого является вторым входом устройства, выход множительного блокасоединен с информационным входомпервого регистра слагаемых, выход.ходом второго регистра слагаемы,выход которого соединен с первыминформационным входом сумматора, выход которого соединенс информационными входами регистров результатов, выходы которых объединены между собой и соединены с первым информацнонным входом коммутатора, второй информационный вход которого соединен с выходом второго входного регистра чисел, выход коммутатора соединен с вторым информационным входом сумматора, выход генератора синхроимпульсов блока управления соединен со счетным входом счетчика тактов, выходы которого соединены с адресными входами блока памяти, кроме того, выходы младших разрядов счетчика тактов соединены с входами дешифратора, первый, второй, третий и четвертый выходы которого соединены с входами приема и входом. э выдачи первого, второго, третьего и четвертого регистров результатов соответственно, второй и четвертый выходы дешифратора соединены с вхо- Сдами приема первого и второго. входных регистров чисел соответственно, а также с входами элемента ИЛИ, выход которого соединен с входами приема первого и второго регистров слагаемых и регистра весового коэффициента, первый выход блока памяти соединен с управляющим входом сумматора, второй выход блока памяти соединен с управляющим входом коммут атор а. 2. Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что, с целью. обеспечения равномерной выдачи резул татов, оно содержит дополнительно четыре выходных регистра, информационные входы которых объединены и, соединены с выходом сумматора, вход приема первого выходного регистра и вход выдачи четвертого выходного регистра соединены с третьим выходом блока памяти, вход выдачи первого выходного регистра и вход приема четвертого выходного регистра соединены с четвертым выходом блока1101835 памяти, входы приема второго и чет-вертого выходных регистров соединенысоответственно с пятым и восьмгмвыходами блока памяти, входы выдаИзобретение относится к вычислительной технике и может быть использовано при построении устройств,реализующих алгоритм быстрого преобразования фурье (БПФ),Известно устройство, выполняющееоперации с комплексными числами.Устройство содержит регистры действительной и мнимой частей сомножителей,формирователи поразрядных произведений, комбинационно-накапливающиесумматоры, блок перевода в дополнительный код ЯОднако это устройстно требуетбольшого объема оборудования.Наиболее близким к изобретению потехнической сущности является устройство для быстрого преобразованияФурье, содержащее четыре входных регистра чнсел и дна входных регистравесового коэФФициента, входы которыхявляются входами устройства, множи"тельный блок, сумматор, коммутаторслагаемых, коммутатор сомножителей,дна регистра слагаемых, четыре регистра произведений и блок управления, первый выход которого соединен с управляющим входом коммутатораслагаемых, второй выход - с управляющим входом коммутатора сомножителей, выходы регистров весовогокоэффициента соединены с первымидвумя информационными входами коммутатора сомножителей, выходы которогссоединены с входами множительногоблока, выходы которого соединены свходами регистров произведений, выходы которых соединены с первымичетырьмя информационными входами коммутатора слагаеьых, другие четыреинформационных входа которого соединены с выходами входных регистровчисел, выходы коммутатора слагаеьихсоединены с входами сумматора, выход которого соединен с выходомустройства и с входами регистровслагаемых, выходы которых соединеныс третьими и четвертыми информацион-.ными входами регистра сомножителей 2 .Недостатками известного устройст- .ва являются большие затраты оборудования и множество входов, что требует распараллеливания памяти, аэто,в свою очередь, приводит к увеличению внешних связей и усложчи второго и третьего выходных регистров соединены соответственно сшестым и седьмым выходами блокапамяти. нению адресации либо к необходимости установки распределителя данныхна входе устройства.Целью изобретения является упрощение устройства.Поставленная цель достигаетсятем,что в арифметическом устройстведля быстрого преобразонания Фурье,содержащем два входных регистрачисел, входной регистр весовогокоэффициента, множительный блок,два регистра слагаеьых, сумматор,коммутатор, блок управления и четыре регистра результатов, блок управления содержит генератор синхроимпульсов, трехразрядный счетчик тактов, дешифратор, элемент ИЛИ имикропрограммный блок памяти, причеминформационные входы входных ре гистров чисел объединены и являютсяперным входом устройства, выход перУного нходного регистра чисел соединен с первым входом множительного блока, второй вход которого соединен с выходом регистра весового коэффициента, информационный вход которого является вторым входом устройстна, выход множительного , блока соединен с информационным входом первого регистра слагаемых, выход которого соединен с информа ционным входом второго регистра слагаемых, выход которого соединен с первым информационным входом сумматора, выход которого соединен с ин формационными входами регистров результатонвыходы которых объединены между собой и соединены с пер- вым информационным входом коммутатора, второй информационный вход которого соединен с выходом второго входного регистра чисел, выход коммутатора соединен с вторым информационным входом сумматора, выход генератора импульсов блока управлениясоединен со счетным входом счетчика тактов, выходы которого соединены с адресными входами блока памяти, кроме того, выходы младших разрядов счетчика тактов соединены свходами дешифратора, первый, второй,третий и четвертый выходы которого соединены с входом приема и входом выдачи первого, второго, третьего и четвертого регистров результатов соответственно, второй и четвертыйвыходы дешифратора соединены с входами приема первого и второго входных регистров чисел соответственно, а также с входами элемента ИЛИ, выход которого соединен с входами приема первого и второго регистров слагаемых и регистра весового коэффициента, первый выход блока памяти соединен с управляющим входом сумматора, второй выход блока памяти соединен с управляющим 30 входом коммутатора.Кроме того, с целью обеспечения равномерной выдачи результатов устройство дополнительно содержит четыре выходных регистра, информаци онные входы которых объединены и соединены с выходом сумматора, вход приема первого выходного регистра и вход выдачи четвертого выходного регистра соединены с третьим выходом блока памяти, вход выдачи первого выходного регистра и вход приема четвертого выходного регистра соединены с четвертым выходом блока памяти, входы приема второго и четвертого выходных регистров соединены соответственно с пятым и восьмым выходами блока памяти, входы выдачи второго и третьего выходных регистров соединены соответственно с шестым и седьмым выходами блока памяти.На фиг.1 представлена структурная схема устройства; на фиг. 2 - структурная схема устройства, обеспечивающего равномерную выдачу результа тов; на фиг. 3 - структурная схема блока управления; на фиг. 4 - вре - менная диаграмма, иллюстрирующая работу устройства; на фиг. 5 блок-схема алгоритма функциониро вания блока управления.Арифметическое устройство для быстрого преобразования Фурье содержит два входных регистра 1 и 2 чисел, инФормационные входы которых 45 объединены и являются первым входом устройства, входной регистр 3 весового коэффициента, информационный вход которого является ь.орым входом устройства. Выходы входного регистра 1 чисел и входного регистра 3 весового коэффициента соединены соответственно с первым и вторым входами множительного блока 4, выход которого подключен к информационному входу первого регистра 5 слагаемых, 55 Выход регистра 5 слагаемых соединен информационным входом второго регистра 6 слагаемых. Выход регистра 6 слагаемых подключен к первому информационному входу сумматора 7, к вто рому информационному входу которого подключен выход коммутатора 8, информационные входы регистров 9-;12 результатов объединены между собой и соединены с выходом сумматора 7. 65 Выходы регистров 9-;12 результатовобъединены между собой и являютсявыходом всего устройства, крометого, выходы регистров 9-;12 результатов соединены с первым информационным входом коммутатора 8, второй информационный вход которогосоединен с выходом входного регистра 2 чисел.Выходы блока 13 управления подключены к управляющим входам всехрегистров, сумматора 7 и коммутатора 8.Арифметическое Устройство длябыстрого преобразования фурье,обеспечивающее равномерную выдачурезультатов, содержат дополнительно четыре выходных регистра 14-.17,информационные входы которых объединены между собой и подключены к выходу сумматора 7, а выходы выходных регистров 14-;17, также объединенные между собой, являются выходом 18 всего устройства.Входы управления приемом и выдачей информации выходных регистров14-:17 соединены с соответствующимивыходами блока 13 управления, Сумматор 7 представляет собой сумматор-вычитатель, который имеет входуправления выполняемой операцией,Непосредственное объединение выходов регистров результатов допустимо, если в качестве этих регистровиспользовать регистры с тремя состояниями на выходе.Блок 13 управления (Фиг, 3) содержит генератор 19 синхроимпульсов, выход которого подключен ксчетному входу трехразрядного счетчика 20 тактов.Первый (младший) и второй выходысчетчика 20 соединены с соответствующими входами дешифратора 21, крометого, первый, второй и третий выходы счетчика 20 подключены к соответствующим входам микропрограммногоблока 22 памятиВторой и четвертый выходы дешифратора 21 соединены с двумя входами элемента ИЛИ 23, выход которогоявляется выходом 24 блока 13 управления,Первый, второй, третий и четвертый выходы дешифратора 21 являются, соответственно выходами 25-28 блока 13 управления, а первый и второй выходы блока 22 памяти являются выходами 29 и 30. Выход 25 подключен к синхровходу приема и к входу управления выдачей информации регистра 11, выход 26 соединен с синхровходами приема регистров 1 и 12 и с входом управления выдачей информации регистра 12, выход 27 подключен к синхровходу приема и к входу управления выдачей регистразность 60 ра 9,выход 28 соединен с синхронходами приема регистров 2 и 10 и свходом управления выдачей информации регистра 10, выход 29 подключенк управляющему входу сумматора 7, а.выход 20 - к управляющему входу коммутатора 8.При введении четырех выходныхрегистрой" 14-;17 в блоке 13 управления блок 22 памяти содержит на шесть выходон больше, причем выход 31 0блока памяти соединен с синхронходомприема регистра 14 и с входом управления выдачей регистра 17, выход 32соединен с синхронходом приема регистра 16 и с входом управления 15выдачей регистра 14, выход 33 подключен к синхровходу приема регистра 15,выход 34 подключен к входу управления выдачей регистра 15,выход 35 соединен с входом управления выдачей регистра 16, авыход 36 - с синхровходом приема , регистра 17.На фиг.5 приняты следующие условные обозначения:251- -1-й-такт, -й-полутакт; С - ре з ул ьт ат н а выходе сумматора 7;БПФ - момент выдачи результатовпреобразования с указаниемкакой, именно результат вы-.дает ся;Рг 1 2 - входные регистры чисел 1 и 2; Рг 3 - регистр весоного коэффициента 3;Рг 5 - первый регистр слагаеьих 5 Ргб - второй регистр слагаемых б; Рг 9-, 12 - регистры результатов 9-. 12; МО - результат на выходе множительного блока 4;Рг 14-;17 - выходные регистры 14-;17, 40Устройство выполняет базовую операцию алгоритма быстрого преобразования Фурье по основанию 2 РеА;:йеВ,КеС; Реа,с, 1,а 1 А;-.1,В РеС, 1 й 1 С, КеЪ РеА;+=Яе В;- РеС" Рейф 1 С, 1,% 1 А,:1,8-Рес, 1 Д 1 С .Реа исходные отсчеты;55преобразованные отсчеты,весовой коэффициент,Ю1 н количество отсчетов висходном массиве;действительная частьчисла;мнимая часть числа. Рассмсррим работу устройства при выполнении базовой операции, Считаем, что прием информации в регистры осуществляется в момент прихода э аднего фронта синхроимпульса.В конце первого такта по сигналу с выхода 25 блока 13 управления во входной регистр 1 чисел принимается действительная часть ВеС; исходного отсчета С во входной регистр 3 весового коэффициента по сигналу с выхода 24 - действительная, часть ВеМ несоного коэффициента ХВо втором такте выполняется умножение в множительном блоке 4 и произведение КЕ С,1 гМ по сигналу с выхода 24 принимается н регистр 5. По этому же сигналу в регистр 3 принимается мнимая часть 3, Ж весового коэффициента Ф,а по сигналу с выхода 28 в регистр 2 чисел принимается дейстнительная часть е В; исходного отсчета В,.В третьем такте выполняется умножение и произведение 8 еб;3,а по сигналу с выхода 24 принимается в регистр 5; по этому же сигналу в регистр 6 принимается произведение ес, Ре ч и в регистр 3 - мнимая часть 3% весового коэффициента %, во входной регистр 1 чисел по сигналу с выхода 26 принимается мнимая часть 3 С; исходн ого от счет а С, .В четвертом такте н множительном блоке 4 выполняется умножение и произведение 3 С, 1%по сигналу с выхода 24 принимается в регистр 5 слагаемых, по этому же сигналу в регистр б принимается произведение кем; 1 ч/, а во нходной регистр 3 - действительная часть Зебр весового коэффициента В . По сигналу с выхода 28 во входной регистр 2 принимается мнимая часть 3, Э; исходного отсчета В;. Коммутатор 8 по , сигналу с выхода 30 подключает к входу сумматора 7 выход входного регистра 2 чисел. Сумматор 7 по сигналам с выхода 29 выполняет операцию сложения н перной половине четвертого такта, а операцию вычитания но второй половине, Соответственно сумма РеВ йесйеа по сигналу с выхода 27 принимается н регистр 9 н середине четвертого такта, а Реб еС, е по сигналУ 1 с выхода 28 и конце четвертого такта принимается и регистр 10.В пятом такте н множительном блоке 4 выполняется умножение и произнеденис 1,с, 1 еВпо сигналу с выхода 24 принимается в регистр 5, проиэведение 1,с Ре В по этому сигналу принимается в регистр 6, а во входнойрегистр 3 - действительная часть Рва, Во входной регистр 1 по сигналу с выхода,26 принимается действительная часть 8 аС; следующего исходного отсчета С. Коммутатор 8 по сигналу с выхода 30 подключает 5 к входу сумматора 7 выход входного регистра 2. Сумматор 7 по сигналам с выхода 29 выполняет операцию сложения в первой половине пятого такта и операцию вычитания - во второй 10 половине. В середине пятого такта сумма Ь,йеС 1,а по сигналу с выхода 25 принимается врегистр 11, а в конце пятого такта разность ,Э,- Вас, а" по сигналу с выхода 26 принимается в регистр 12.В шестом такте в множительном блоке 4 выполняется умножение и произведени РеС; РеФф" по сигналу с выхода 24 принимается в регистр 5, в регистр б по этому же сигналу принимается произведение Е;. РеЭ а в регистр 3 - мнимая частьафГ весового коэффициента й" . Во входной регистр 2 по сигналу с выхода 28 принимается действительная часть 9 е 8;,исходного отсчета В . Коммутатор 8 по сигналу с выхода 30 подключает к входу сумматора 7 объединенный выход регистров 9-;12 результатов. Сумматор 7 по сигналам с выхода 29 выполняет операцию вычитания в первой половине шестого такта и операцию сложения - во второй. В первой половине шестого такта по сигналу с выхода 27 из регистра 9 выдается сумма РеВ; Яес; РеФ и в середине такта по этому же сигналу (по заднему фронту) в регистр 9 принимается разность Яе;-. Яе 8 ЯеС; РеВ- -1 С"1 а, Во второй половине шес того такта по сигналу с выхода 28 из регистра 10 выдается разность 8 еВ;.РеС; Не% и в конце такта по этому же сигналу в регистр 10 принимается сумма Йе;= Реб,-йеС; Реа+ 45С;1 а.В седьмом такте в множительном блоке 4 выполняется умножение и произведение РеС;1% по сигналу с выхода 24 принимается в регистр 5, в регистр б по этому же сигналу принимается произведение Яес;РеМ 11) а во входной регистр 3 - мнимая часть 1 Юф весового коэффициента аф . Во входной регистр 1 по сигналу с выхода 26 принимается мнимая часть исходного отсчета С; . Коммутатор 8 по сигналу с выхода 30 подключает к входу сумматор 7 объединенный выход регистров 9-:12 результатов. Сумматор 60 7 по сигналам с. выхода 29 выполняет операцию сложения и операцию вычитания соответственно в первой и второй половинах седьмого такта. В пер вой половине седьмого такта по сиг налу с выхода 25 из регистра 11 выдается сумма 1,8; РеС; 1, а и всередине такта по этому же сигналув регистр 11 принимается сумма1 А;.1,8; Яес; ,а 1 С; Ре а, Во второй половине седьмого такта посигналу с выхода 26 из регистра 12выдается разность. ЬеС; 1 е и в конце такта по этому же сигйалу в регистр 12 принимается разность 1 А;1 щВ;- Рес, ,с Рею.В восьмом такте в множительном блоке 4 выполняется умножение и произведение 1 с;, . 1,Ф "+ по сигналу с выхода 24 принимается в регистр 5, в регистр б по этому же сигналу принимается произведениеРеС; 1, Ф(", а в регистр 3 - действительная часть Речф весового коэффициента Ф" . Во входной регистр 2 по сигналу с выхода 28принимается мнимая часть 1 8; исходного отсчета В; . Коммутатор 8 по сигналу с выхода 30 подключаетк входу сумматора 7 выход входного регистра 2 чисел. Сумматор 7 выполня. ет операции сложения и вычитания в первой и второй половинах тактасоответственно, В первой половине восьмого такта из регистра 9 на выход устройства выдается действительная часть Ре Ф преобразованного. А, по сигналу с выхода 27 и по этому же сигналу (по заднему фронту) в регистр 9 принимается сумма Ре 8,+ +ЯеС;Яеа ф . Во второй половине восьмого такта из регистра 10 на выход устройства по сигналу с выхода 28 выдается действительная часть Ре А;,и по этому же сигналу в.регистр 10 принимается разность Ре 8;-Рес;йеаф.В первой половине десятого такта по сигналу с выхода 25 из регистра 11 на выход устройства выдается мнимая часть4, преобразованного отсчета А; и по этому же сигналув регистр 11 принимается сумма 1,8;,И е С;, 1,аф. Во вт орой половине девятого такта по сигналу с выхода 26 из регистра 12 на выход устройства выдается мнимая часть 1 В; преобразованного отсчета А;и по этому же сигналу в .регистр 12 принимается разность 1,8- РеС;1,чуф . Работа остальнйх элементов устройства аналогичнаописанной для пятого такта.Далее работа всего устройства аналогична.При введении четырех выходных регистров 14 ф 17 работа устройства отличается только в тактах 6-9, относящихся к записи преобразованных отсчетов и выдаче их на выход устройства. А именно, в середине шестого такта действительная часть Ре 4;преобразованного отсчета А; принимается не в регистр 9,а в регистр 14,соответственно ЙВ 4,.,1 Ь, к 11;. принимаются в регистры 15-17. Тогдавыдачу преобразованных отсчетовможно выполнять независимо от промежуточных вычислений, причем равномерно, т.е. по одному результатуза один такт. Например, в седьмомтакте на выход устройства выдаетсяйеД, в восьмом -Яе Д; , вцевятом - 1 А, в десятом - 1 Аб середине десятого такта в регистр 14 принимается Ке 1;, и далеественно в десятом и одиннадцатом тактах в регистры 15-17, а в одиннадцатом такте можно уже выдавать Яе А; в двенадцатом КеВ,и т.д.Таким образом, по сравнению сизвестным устройством предлагаемоепри той же производительности имеет.на три регистра и один коммутаторменьше, причем известное устройствовключает сложные многовходовые коммутаторы, а предлагаемое - простой 10 двухвходовой. Кроме того, известноеустройство имеет шесть входов, тогда как предлагаемое устройство только два, что существенно уменьшаетчисло внешних связей и позволяет 15 работать с линейно организованной1101835 1 бПФ=РИ 6 1 3 гЪцы: Р 17 1 ГРгИ:С РГ 16= С гРг 17=1 6 ПЮщРр А в Подписноео комитета СССРий и открытийРаушская наб д. 4/5 47 б 9/33 Тираж 699 ВНИИПИ Государственно по делам изобрете 113035, Москва, Ж, Зак ППП "Патент", г.ужгород, ул. Проектная ил СоставительФедоро актор В.Иванова Техред С. Легеза Корректор В.Бутяга