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

(71) Завтел 54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯФУРЬЕ изобрет быстрог матор-в блок и,ентов, эл 1 рножен блокаом сум Изобретение олюсится к области вычислительной техники и прсдназначено для использо. ванин в аппаратуре, осуществляющей спектральную обработку электрических сигналов в реальном масштабе времени.Известно цифровое устройство, реализующее5 алгоритм быстрого преобразования Фурье (БПФ), состоящее из сумматоров, множительноо устрой. ства, запоминающих устройств, формирователя весовых коэффициентов 11) .1 ОНедостатком его является отсутствие конт.роди правильности работы устройства, а также то, что оно работает только по одному, наперед заданному алгоритму. 1 олее близким техническим решением к нию является устройство для реализации о лреобразования Фурье, содержащее сум. ычитатель, блок умножения, сумматор, мяти, блок хранения весовых козффициеменгы И ИЛИ, причем входы блока ия соединены соответственно с выходом ранения весовых коэффициентов и выхо матора-вычитателя 12 . Известное устройство реализует алгоритм БП с естественным порядком поступления входных выборок. Для реализации БПФ пон поступлении входных выборок в двоично-инверсном представлении в этом же источнике представлен другой вариант устройства.Целью изобретения является повьшиние надежности работы устройства цутем осущтвления контроля его работы при реализации двух алгоритмов БПФ.Это достигается тем, что устройство содер. жит схему сравнения и два коммутатора, причем вход устройства соединен с первыми входами первого и второго элементов И-ИЛИ, вторые входы которых подключены к первой группе входов схемы сравнения, соответственно к первым входам первого и второго, коммутаторов и соответственно к выходам первого и второго блоков памяти, входы которых соединены соответственно с выходами первого и второго элементов И ИЛИ, выходы первого и второго коммутаторов соединекы соответственно с первыми и вторыми входами сумматора и сумматора-вы. читателя, выход сумматора соединен с первыми3 687449 входами третьего, четвертого, пятого н шестого элементов И-ИЛИ и с первым входом иэ второй группы входов схемы сравнения, выход сумматора вычитателя через блок умножения соеди. нен со вторыми входами третьего и четвертого элементов И-ИЛИ, первыми входами седьмого и восьмого элементов И.ИЛИ, вторым входом из второй группы входов схемы сравнения, вход четвертого элемента ИИЛИ соединен с вторыми, входами пятого, шестого, седьмого и восьмого, 10 элементов И-ИЛИ, выходы которых через соответствующие блоки памяти соединены соответ ственно; вторыми, третьими, четвертыми и пятыми входами первого и второю коммутаторов, . выход третьего элемента И ИЛИ является инфор . 15 мационным выходом устройства, выход схемы сравнения является контрольным выходом устройства.На чертеже приведена структурная схема предлагаемого устройства. 20Оно имеет блоки памяти 1, 2, 3, 4, 5, 6, сумматор 7, сумматор.вычитатель 8, блок умно жения 9, блок 10 хранения весовых козффици ентов, вход 11, элементы И-ИЛИ 12, 13, 14, 15, 16., 17, 18, 19, коммутаторы 20, 21, схему срав. 25ненни 22.Устройство реализует два алгоритма БПФ:х. (2 к) =х (к)+х (к+ )х(2 к + 1) х(к) - х (к + - Ц%и РИ)1+1х(1+1)(к) = х (2 к) + х(2 к + 1)х(щ)(к+)(х(2 к) - х;(2 к+1)1 ВаМ где- номер итерации (= 1 - ;09 й);к - номер выборки ( к . О - ; И(2-1);35С 1 мЬгщ Мр - весовой коэффициент, зависящий отномера выборки и номера итерации 40При реализации алгоритма (1) входная последовательность поступает в естественном по. рядке; запись входной информации, состоящейПиз 2 = 1 ч комплексных выборок, в блоки 1 и 2 45 памяти осуществляется следующим образом: первые й/2 выборок через элемент И ИЛИ 13 в блок памяти 1, последующие й/2 выборок (от Й/2 + 1 до й) через элемент И.ИЛИ 12 в блок 2 памяти, После записи входной информации 50 начинается обработка ее цо алгоритму (1),Первая пара входных выборок хо (О) и хо(Й/2 + О) по одной считаются соответственно из блоков 1 и 2 памятия через коммутаторы 20 и 21 поступает на входы сумматора 7 и сум,55 матора-вычнтателя 8, причем значение хо (Й/2+О) на вход сумматора-вычнтателя 8 поступает обрат. ным кодом. С выхода сумматора 7 полученное значение х, (0) = х, (0) + хо(й/2 + 0) через 4элементы И.ИЛИ 14 и 15 записывается в блок 3памяти, Значение с сумматора-вычитателя 81 хо (О) - хо (й/2+0) 3 поступает на первыйвход блока 9 умножения, одновременно на вто.рой его вход из блока 10 хранения весовых ко.э фициентов поступает соответствующее значение(в), результат с выхода блока 9 умножениях, (1) = 1 хо (О) - хо (М/2 + О) 3 в через элементы И.ИЛИ 14 - 15 записывается вслед за х, (О)в блок 3 памяти. Затем вторая пара чисел анало.гично описанному считывается из блоков 1 и 2памяти и через коммутаторы 20 и 21 поступаетна входы сумматора 7 и сумматора-вычитателя 8,конечный результат с выхода сумматора 7 и бло.ка 9 умножения через элементы И.ИЛИ 14 и 15записывается в блок 3 памяти, Так повторяетсяй/4 тактов, Через И/4 тактов блок 3 памяти. 0оказывается заполненным и следующая пара полученных результатов через элементы И ИЛИ 14и 16 записывается в блок 4 памяти, Так продол.жается й/4 раз. После заполнения блока 4 заканчивается первая итерация, Во второй итерации счи.тывание информации производится из блоков 3 и4 памяти через соответствующие коммутаторы 20и 21. Весь процесс идет аналогично описанному,только запись полученных результатов первыеИ/4 тактов через элементы И-ИЛИ 14 и 17 после.довательно один за другим идет в блок 5 памяти,а вторые Н/4 тактов через элементы И-ИЛИ 14и 18 в блок б памяти. В третьей итерации (н впоследующих нечетных итерациях) информациясчитывается одновременно из блоков 5 и 6 памяти, а записывается последовательно в блоки 3 и4 памяти, а в четных итерациях они меняютсяместами (т,е. считывание идет из блоков 3 и 4памяти, а запись в блоки 5 и 6 памяти,По окончании последней итерации считывание информации через элемент И.ИЛИ 19 с выходов сумматора 7 и блока 9 умножения поступает на выход устройства в двоично-инверсномпо отношению к естественному порядку.При работе по алгоритму (2) входная инфор.,мация поступает в двоично инверсном. порядке,запись входной информации идет поочередно поодному слову в блоки 1 и 2 памяти. Первая пара чисел, считываемых из блоков 1 и 2 памяти, через коммутаторы 20 и 21 обрабатывается в соответствии с формулами (2) аналогично алгоритму 1, Полученные результаты с выхода сумматора 7 в первой итерации ( ив остальных нечетных итерациях) через элемент И. ИЛИ 15 записываются в блок 3 памяти, а в чет. ных итерациях в блок 5 памяти через элемент И-ИЛИ 17. Запись результатов с выхода блока 9 умножения в нечепых итерациях через элемент И-ИЛИ 16 идет в блок 4 памяти, а в четных итерациях через элемент И.ИЛИ 18 - в блок б памяти. Считывание информации во всех итера.5 б 8744циях иэ блоков 3 и 4 памяти идет последовательно по два числа из каждого блока памятив кчение М/4 тактов через коммутаторы 20 и, 21.Аналогично в других итерациях идет считывание нэ блоков 5 и б памяти. Окончательныйрезультат, как и в алгоритме (1), поступает навыход устройства с выходов сумматора 7 и бло.ка 9 умножения через элемент И-ИЛИ 19,Входная информация в режиме контроли 10через элементы И.ИЛИ 12 и 13 с выходов блоков1 и 2 памяти записывается на входы этих же бло.,ков. После реализации прямого преобразованйяФурье но алгорйтму:(1) или (2) осуществляется+ 2 Ф - 45обратное преобразование Фурье %= Е и ),но по другому алгоритму, т.е, если прямое преобразование осуществляется по алгоритму (1),обратное преобразование будет осуществлятьсяпо алгоритму (2), так как результат прямого20преобразования оказывается записанным в блоки памяти в двоично-инверсном по отношению квходному порядке.Результат прямого преобразования оказывается записанным либо в блоки 3 и 4 памяти,либо в блоки 5 и б памяти (в зависимости отчисла итераций). Поэтому для обратного преоб.разовання Фурье в первой итерации информациясчитывается из этих блоков в соответствии снеобходимым алгоритмом через коммутаторы 20и 21. В последней итерапии информация с выходов сумматора 7, блока 9 умножения и с выхо-,дов блоков 1 и 2 памяти поступает,на схемусравнения, Результат сравнения поступает на контрольный выход устройства,35 Формула изобретения Устройство для реализации быстрого преоб.раэования Фурье, содержащее сумматор-вычита- ".тель, блок умножения, сумматор, блоки памяти,блок. хранения весовых коэффициентов, элемен 9 6ты И-ИЛИ, причем входы блока умножения соединены соответственно с выходом блока хра.Эпения весовых коэффициентов и выходом сумматора.вычитателя, о т л и ч а ю щ е е с я тем,что, с целью повышения надежндсти работы уст.ройства вработе, оно содержит схему сравненияи два коммутатора, причем вход устройства со.единен с первыми входами первого и второгоэлементов И-ИЛИ, вторые входы которых подключены к первой группе входов схемы сравне.ния, соответственно к первым входам первогои второго коммутаторов и соответственно к вы.ходам первого и второго блоков памяти, входыкоторых соединены соответственно с выходамипервого и рторого элементов И ИЛИ, выходыпервого и второго коммутаторов соединены соответственно с первыми и вторымн входами сум.матора и сумматора;вычитателя, выход суммато .ра соединен с первыми входами третьего, четвер.того, пятого и шестого элементов И.ИЛИ й с первым входом из второй группы входов схемысравнения, выход сумматора-вычитателя черезблок умножения соединен со вторыми входамитретьего и четвертого зяементов ИИЛИ, первыми входами седьмого н восьмого элементовИ-ИЛИ, вторым входом из второй группы входов схемы сравнения, выход четвертого элемента И-ИЛИ соединен с вторыми входами пятаго,шестого, седьмого и восьмого элементов И-ИЛИ,выходы которых через соответствующие блокипамяти соединены соответственно с вторыми,третьими, четвертымп и пятыми входами первого и второго коммутаторов, выход третьего эле.мента И.ИЛИ является информационным выхо.,дом устройства, выход схемы сравнения является контрольным выходом устройства.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР Р 421994,кл. 6 Об Р 15/34, 1974.2, Патент Франции Ио 2082030, 6 Об Р 15/00,1971.