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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК я)з 606 Г 1 ГОСУДАРСТВЕН РЕ ПАТЕНТНОВЕДОМСТВО СССРГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ч ислительнойано в раэлички сигналов.ение быстроИзобретение от технике и может бы ных системах цифро Цель изобрете действия. яфиг.1 и 2 схема устройства; диаграммы управлносится к выч ть ис:юльзов вой обработ ия - повыш зображена структурн на фиг. 3 - временныющих сигналов.(71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции72) Ю,С.Каневский, М.К.Клименко.(56) Авторское свидетельство СССР М 1196894. кл, 6 06 Р 15/332, 1985.Авторское свидетельство СССРМ 1388891, кл, 6 06 Р 15/332, 1988.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки радиолока. ционных, сейсмических, гидроакустических, видео- и других сигналов. Известное устрой- стао имеет большие аппаратурные затраты, кроме того оно за один вычислительный цикл формирует только действительную или мнимую часть выходного отсчета. Изобретение привычислении действительной и мнимой части результата имеет вдвое большую производительность. так как вычисление реальной и мнимой части результата в уст,.Я 21725228 А 1 ройстве, выполняется за один проход, а в прототипе за два прохода, Устройство содержит М умножителей (М = 2 КТ 1/Т 2. где Т 1 - время срабатывания умножителя: Т 2 - временной интервал между поступлением двух входных отсчетов 2 Т 1Т 2: К - количество вычисляемых спектральных составляющих, К й; й - размер преобразования), по М/2 сумматоров первой и второй группы, по К регистров суммы первой и второй группы, М/2 регистров входных данных, М регистров операндов и (М+1)/2 триггеров и М блоков памяти коэффициентов. информационный вход устройства объединен с входом первого регистра входных данных, а вход последующего регистра подключен к выходу предыдущего, Выходы умножителей подключены к соответствующим входам сумматоров первой группы, выходы которых подключены к первым входам сумматоров второй группы. к вторым входам которых подключены выходы соответствующих регистров суммы первой группы. Выход первого регистра суммы является выходом устройства и подключен к входу первого регистра суммы второй группы. 3 ил. устройство гоиг.и 2) содержит в ычис. лительные модули 1.1-1,М/2, гдее) - целое число, содержащее первый 2.1 и второй 2.2 умножители, первый 3 и второй 4 сумматоры, входной регистр 5, первый 6.1 и второй 6.2 регистры операндов, триггер 7, первый 8 и второй 9 блоки регистров суммы, а М/2-й модуль содеожит дополнительно триггер 10,Кроме того, устройство содержит информационный вход 11. информационные входы 12, 13 и выход 14 модуля, информационный выход 15, информационные выходы 16-18 и входы 19-22 ьодуля. две группы из М/2 блоков постоянной памяти 23, счетчик 24, генератор тактовых импульсов 25, выход 26 синхронизации, управляющий вход 27, дешифратор 28 и элемент ИЛИ-НЕ 29.При реализации процедуры вычисления дискретного преобразования Фурье устройство вычисляет выражение видаИ - 1Х(1) - Г хп) ЧЧч". О11 ч -1, (1)о=огде х(п) - элементы исходной последовательности длины:Х(М) - элементы преобразованной последовательности;ЧЧч - весовые коэффициенты,Юч ЛеРассмотрим работу устройства для случая Т 2/Т 1 " 4, К - 8, й 12. Будем рассматоивать наиболее распространенный на практике случай, когда на вход устройства подается последовательность действительных отсчетов, 1 е. х(п) - йе х(п), 1 в х(п) - 0(где ВеА, гпА - соответственно действительная и мнимая части числа А). Следовательно, необходимо получить на выходе устройства , следующие результаты:ч-йеХ(1) -х(п) ВеЧЧч"; (2)л =ОВ - 1тХ(М)х(п)пЧи" .и =ОДля компактности будем обозначатьЧЧч" как ЧЧ". Пусть необходимо определить Х(1), Х(2), Х(4), Х(5), Х(6), Х(8), Х(9). Х(11).При описании работы устройства будем различать такт устройства. равный Т 2, и подтакт, равный Т 1. Такт устройства разбит на Т 2 Л 1 - 4 подтакта и обозначается А, В, Бе А-номертакта, В-номер подтакта, В-4.Начало такта совпадает с передним фронтом синхросигнала. поступающим с второго выхода счетчика 24 на второй тактовый вход модуля. На первый вход устройства подается с выхода элемента ИЛИ-НЕ 29 управляющая последовательность с периодом М, состояг;ая иэ одной "1" и (М) "0" (длительность как "0", так и "1" равна Т 2, а на второй управляющий вход устройства с выхода дешифратора 28 подается с периодом 1 ч последовательность, состоящая из одной "1" и(М) "0" (фиг. 3),Первый такт. 1.1, В регистр 5.1 принимается Х(0).5 1.3, На первый управляющий вход устройства подается "1",Второй такт, 2.1, В регистр 5,1 принимается Х(1), в регистр 5.2 - Х(0). Триггер 7.2устанавливается в единичное состояние.10 2.3. На четвертый управляющий входустройства подается "1", на второй - "0",Третий такт. 3.1. В регистр 6,4 принимается Х(0), в регистр 6.3 - Х(1. в регистр 5.1 -Х(2), триггер 7.2 сбрасывается в "0". триггер15 7,1 и 10 устанавливаются в "1". На вторыевходы умножителей 2.3 и 2.4 подаются коэффициенты йеЮ и. ВеРР соответственно.Сумматор 4.2 выполняет операцию "А+О" ив конце подтакта на вхор регистра 8,2 посту 20 пает х(о)йеЧР+ х(1)ВеЧЧ .3.2. В регистр 8.2.4 записываетсях(о)йеЧЧ + х(1)йеЮ, на вторые входы умножителей 2.3 и 2,4 подаются х(о)ЧЧ и 1 вЧЧ, Воконце портакта на вход регистра 8.2,4 посту 25 пает х(о)АЯЧЧО+ х(1)пйЧ.3.3. Содержимое регистра 8.2,4 переписывается в регистр 8.2.3. а в регистр 8.2.4записывается результат с выхода сумматора 4,2, На вхоуы умножителей 2.3 и 2.4 по 30 ступают йеЧ и йеЧЧ, На четвертыйоуправляющий входустройства подается "0",3,4. Производится соответствующая перезапись содержимого регистров 8.2.4.8.2.3 и 8.2.2. На вторые входы умножителей35 2,3 и 2.4 подаются 1 вЧЧ и 1 гпЧЧО.Четвертый такт. 4.1, В регистры 6.2 и 6,1принимаются Х(2) и Х(3), в регистр 5.1-Х(3),триггер 7.1 устанавливается в "0". производится перезапись информации в регистрах40 8,2,В дальнейшем описании работы устройства не будем специально оговаривать запись информации в регистры 8,1 и 8.2. таккак она производится в начале каждого под-45 такта. На вторые входы умножителей 2,1,2,2, 2.3, 2.4 подаются соответственно йеЧЧ,эйеЧЧ, йеЧЧ 4, йеЧЧ . В конце подтакта навыходе счмматооа 4.1 Формируется йеХ(1) -.х(о)йеИР+ х (1)Вел+ Х(2)йеЧЧ + Х(3)йеЧЧэ.50 4.2. На вторые входы умножителей 2,1, .2,2, 2,3 и 2.4 подаются соответственногпЧЧ, 1 вЧЧ, глЮ 4, 1 гпЧЧ,В конце подтакта на выходе сумматора4.1 формируется 1 глХ(1)4,3. На первые вхо 55 ды умножителей 2.1, 2,2, 2.3 и 2.4 подаютсясоответственно йеЧЧ, йечч, йеЧЧ, ВеЧЧ .б4 5 ОНа выходе сумматоров 4,1 и 4.2 формируется йеХ(2) и ВеХ(5). 4.4. На вторые входыумножителей 2.1, 2.2, 2,3 и 2,4 подаютсясоответственно 1 глЧЧ, 1 ач, 1 гпЧЧ . 1 гпЮ,б "4 5 ОНа выходах сумматоров 4.1 и 4.2 формируются соответствующие результаты.Пятый такт. 5.1. В регистр 5,1 принимается Х(4). На вторые входы умножителей 2.1,2.2, 2.3 и 2.4 поступают ВеЮ . ВеЮг, ВеЧЧЯеЧЧд. На выходах сумматоров 1,4 и 4.2 формируется ВеХ(4) и ВеХ(6). 5,2, На вторыевходы умножителей 2,1, 2.2, 2.3. 2,4 поступают 1 вЧЧО, 1 гпМР. 1 гпМР, гпту. На выходахсумматоров 4,1 и 4.2 формируется 1 гпХ(4),1 гпХ(6),5.3. На вторые входы умножителей 2.1,2,2, 2.3, 2.4 поступают ВеЧЧ, ВеЮ/, КеЧР,З 10ВеЧЧО. На выходах сумматоров 4.1 и 4.2 формируются ЯеХ(5), ЯеХ(8). На второй управляющий вход устройства подается м 1",5.4. На вторые входы умножителей 2.12,2, 2,3 и 2.4 поступают 1 гпЯ, пЮЧ, гпЮГ3 1 Ои АЯЧЧО.Шестой такт. 6.1. В регистры 5.1 и 5.2принимаются Х(5) и Х(4) соответственно.Триггер 7.2 устанавливается в единичноесостояние. На вторые входы умножителей6 о2.1, 2.2, 2.3 и 2,4 поступают ВеЮ, ВеЮ/ .ВеЧЧ, ВеЮР. На выходах сумматоров 4.1 и4.2 формируются ВеХ(6), ВеХ(9),6.2, На входы умножителей 2 поступаюткоэффициенты, необходимые для формирования 1 п 1 Х(6), 1 аХ(9).6.3. На входы умножителей 2.1, 2.2, 2,3и 2.4 поступают ВеЮlо, ВеЮ 14 ЯеЮ/", ВеЮ 1На выходах сумматоров 4,1, 4.2 формируются ЯеХ, ВеХ .6.4, На входы умножителей 2 поступают"0". На входы умножителей 2,1, 2,2, 2.3 и 2.4поступают ВеЮ . ВеЮ . ВеЧЧ, ВеИ/. С выЭ 6 5 4хода регистра 9.2.4 на второй вход сумматора 4,2 поступает ВеХ(1). Сумматор 4.2начинает выполнять операцию "А+В". Навыходах сумматоров 4.1 и 4.2 формируетсяВеХ(9) и ВеХ(1).7.2. На входы умно кителей 2 поступают1 гп части коэффициентов, поступающих вподтакте 7.1. Так как в четных подтактахвычисляется мнимая часть выходных счетов, действительная часть которых вычислялась ь предыдущем подтакте. то вдальнейшем описании работа устройства вэтих подтактах будет опускаться.7.3. Ка входы умножителей 2,1. 2.2. 2,3и 2.4 поступают ВеЮ, ВеЧЧ, ВеЮ, ВеЮ/,9 10 10 8на выходах сумматоров 4.1 и 4.2 формируется ВеХ(11), ВеХ(2), Восьмой такт, 8,1. В5.1 принимается соотвВеЧЧОов 4.1 такт. 13,1.вый отсчет нНа выходе 1 гпх(1). вхо с 13.2, На выходе 15 устройства23.3. На первый управляющий д у тства подается "1".Формула изобретения Устройство для вычисления дигкретного преобразования Фурье. содержащее М/2 45 (М - целое число) вычислительных модулей.дешифратор. элемент ИЛИ-НЕ. счетчик и генератор тактовых импульсов, выход которого подхлючен к первому твхтоеому входу 1.го Г - 1. М/2 вычислительного модуле и 50 счетному входу счетчика. информационныйвыход которого подключен к входу дешифратора, первый и вто ой информационные выходы /-го Ц " 1, М 2-1) вычислительного модуля подключены соответственно к пер вому и второму информационным входамО+1)-го вычислительного модуля, третий информационный и тактовый выходы которого подключены соответственно к третьему информационному и второму тактовым входам )-го вычислительного модуля, пе 1,алый ин 40,Рой Х(7), Триггер 7,1 сбрасыходы умножителей 2,1, 5 пают ВеЧЧУ, ВеЮ/6, Вел. ВеЮ 14, На выходах сумматоров 4.1 формируется ВеХ(1), ВеХ(4),8,3. На входы умножителей 2.1 2.2, 2, и 2.4 поступают ВвЧЧ . ВеЧЧ, Вериг.2На выходах сумматор и 4.2 формиру ется ВеХ(2), ЯеХ(5),Девятый такт. В регистр 5.1 принимается Х(8), Входные отсчеты Х(7), Х(6), Х(5), Х(4) умножаются на соответс вующие коэффициенты, необходимые для формирования 15 всех выходных отсчетов.Десятый такт, В регистры 5,1 и 5.2 принимаются Х(9) и Х(8) соответственно. Продолжаются вычисления с прежними входными отсчетами. 20 Одиннадцатый такт. В регистры 5.1, 6.3 и 6.4 принимаются Х(10), Х(9), Х(8) соответьг "твенно. На выход д умножителей 2,1, 2.2,3 6 9 2.3 и 2,4 поступе ют ЯеЮ . ЯеЯ, ВеЮ/, ВеЮР. На сумматорах 4.1 и 4.2 формируется 25 ВеХ(9), ВеХ(1):Двенадцатый такт. В регистры 5.1, 6.3 и 6,2 принимаются Х(11. (11), Х(10) соответственно, На входы умножителей 2,1 2.2, 2.3 и 2,4 поступают В лЧЧ, ВеЮl, ЯеЧЧ", ЯеЮР. В10 30 сумматоре 4.1 заканчиеэется формирование действительной части первого полного выходного отсчета ВеХ(1). который в начале тринадцатого такта появляется на выходе 15 устройства. 35 Тринадцатый В регистр 5,1 принимается пер ОВОГО ВХОДНОго массива Х(0). 15 устройстваВеХ(1),)-го вычислительного модуля, первый информационный вход первого вычислительного модуля является первым информационным входом устройства, причем каждый вычислительный модуль содержит входной регистр, два регистра операндов, два умножителя, два сумматора, два блока регистров суммы и триггер, при этом М/2-й вычислительный модуль содержит дополнительно второй триггер. в каждом вычислительном модуле выход входного регистра является первым информационным вьходом вычислительного модуля и подключен к информационному входу первого регистра операнда, выход которого подключен к первому входу первого умножителя, выход которого подключен к первому входу первого сумматора, выход которого подключен к первому входу второго сумматора, выход которого подключен к информационному входу первого блока регистров, тактовый вход которого соединен с тактовым входом второго блока регистров и подключен к первому тактовому входу вычислительного модуля, вторым и третьим информационными выходами, гактовым выходом и вторым тактовым входом которого являются соответственно выходы второго и первого блоков регистров, прямой выход триггера и информационный вход триггера, второй вход первого сумматора подключен к выходу второго умножителя, первый вход которого подключен к выходу второго регистра операнда. информационный вход которого соединен с информационным входом входного регистра и подключен к первому информационному входу вычислительного модуля, вторым и третьим информационными входами которого являются соответственно информационный вход второго блока регистров и второй вход второго сумматора, первый информационный вход первого вычислительного модуля является информаци блоков постоянной памяти каждая. и"ричем первый информационный выход счетчика подключен к третьему тактовому входу 1-го1;02) вычислительного модуля и является выходом синхронизации устройства, установочным входом которого является ус 10 тановочный вход счетчика, информационный выход которого подключен поразрядно к входам элемента ИЛИ-НЕ и к адресным входам 1-х блоков постоянной памяти первой и второй групп, выходы которых под 15 ключены сооответственно к первому и второму входам коэффициентов 1-го вычислительного модуля, выход элемента ИЛИНЕ порключен к второму тактовому входу М/2-го тыцислительного модуля, четвертый 20 тактовый вход которого подключен к выходу дешифратора, второй информационный выход М/2-го вычислительного модуля подключен к третьему информационномувходу М/2-го вычислительного модуля, третий ин 25 формационнйй выход первого вычислительного модуля является информационным выходом устройства и подключен к второму информационному входу первого вычислительного модуля, причем в каждом вычислительном модуле тактовые входы триггера и входного регистра подключены к третьему тактовому входу вычислительного модуля, первый и второй входы коэффициентов которого подключены к вторым входам соответст 35 40 венно первого и второго умножителей. инверсный выход триггера подключен к тактовым входам первого и второго операндов. а в М/2-м вычислительном модуле - к тактовому входу второго триггера, выход которого подключен к управляющему входу второго сумматора, информационный вход второго триггера подключен к четвертому тактовому входу М/2-го вычислительного модуля. онным входом устройства, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него введены двв группы из М/21725228 2г- йа МР. 3 Составитель М,КлименкоРедактор Л.Веселовская Техред М.Моргентал Корректор М.Кул Заказ 894 Тираж Подписное8 НИИПИ Государственного комитета по изобретениям и открытиям113035. Москва, Ж, Раущская наб 4/5 и ГКНТ СССР Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1