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

Номер патента: 1425708

Авторы: Арро, Герм, Смолянский

ZIP архив

Текст

425708 сводится к нечетным трансформантнымпреобразованиям НТП-й/Н.Тогда косинус-коэФфициенты спектра располагаются в выходном массивев порядке возрастания номеров гармоник с первого адреса по адресЯ/2 + 1, а синус - коэффициенты гармоник спектра в порядке убывания но меров с адреса Ю/2 + 2 по адрес М.Для определения произвольных НТПИ/К следует воспользоваться нечетными трансформантными преобразованиями более коротких периодов и транс формантным расширителем, состоящимиз циклически повторяющихся двойных"бабочек" со спектральным расширением(СПР), исходя из установившейсятерминологии,20 Для стыковки НТП-М/2 и двух НТПИ/4 с циклически повторяющимися двойными "бабочками" с СПР при двоичноинверсном порядке адресов исходныхданных необходимо осуществить обмен 25 данными.Каждый из массивов разностей Е(1)разбивается на три части, одна изкоторых образует половину, а две остальных - по четверти объема исход ногоееМатематически нечетное трансформантное преобразование описываетсяследующими формулами:ХС(К(Ж+1) = С 1(К (2 с+1 + Т 2 и 11(4) Формулы (3) и (4) показывают, что в случае комплексных входных данных косинусиые и синусные преобразования массива Х(1) выполняются в отдельности для реальной и мнимой частей. Поэтому в дальнейшем полага ют, что Х(1) содержит только вещественные числа.Тогда вычисление ХС(1 с) и Х 8(с) путем вычисления сумм и разностей 452= Х(1) = Х(1) + Х(1 + М)2; (5)= О, (1,Р - 3) Изобретение относится к вычислительной технике и может быть использовано в радиоэлектронной и измерительной технике.Цель изобретения - повышение быстродействия.Дискретное преобразование Фурье Х(1 с) исходного массива Х(1), 1 /.Р где 1 = 1, И, с = 1, И, М = 2, определяется формулой й ХЬ) =, Х(1) ехр Е 1) Х - 1)/Х/ у где Т = - 1(6) 1 = 1, М/2,где Х(1) - входной (выходной) массивобъема, М;Е(1) - массив разностей;М=К/К - период нечетного трансформтного преобразования+(2 с+1) ) . У 2 = Х 2 - Х 3 Здесь С 1 р и 811 - косинусные и синусные нечетные трансформанты с периодом М/Р.Общее количество арифметических операций для НТП - может быть определено по формуле Х 2 Х 2 + ХЗ,УЗ = Х 4 - Х 5; Х 4 = Х 4 + Х 5; 20О(Н) = (ЬР)Б, И8 (13) У 4 = Хб - Х 7; Уб = Хб " Х 7 УЗ х СОО;74 х СОО; Р 2 Е 1 = Р 1 - Р 2; Е 2 = Р 1 + Р 2; х 1 = ю + г 1; ХЗ У 1 Е 1 х 5 = г 2 - 72; Х 7 = Е 2 - 72; Базовая опеоация 3: М 1 = Х 4 + Х 5; М 2 = Хб + Х 7; Р 1=М 1 хС 1; д рУстройство для выполнения дискретного преобразования фурье выполняет50 четыре типовые операции: три базовые операции и одну оконечную операцию.Базовая операция 1: Р 2 = М 2 х С 2; РЗ = Х 5 х СЗ;Р 4 = Х 7 х С 4; Р 5 = Х 4 х С 5; У=ХО-Х 1; 55 Рб =Хбх Сб; ХО = ХО + Х 1; У 1 = Р 1 - РЗ;,Х 1 = У; причем из них 253 операций умноженияи 757 операций сложения,На фиг.1 представлена схема устройства; на фиг.2 - схема блока синхронизации; на фиг.З - граф алгоритма.Устройство для выполнения,дискретного, преобразования фурье (фиг.1) содержит блок 1 памяти, коммутаторы2-5 (операндов), регистр 6 (операндов), блоки 7-9 регистров (операндов),арифметический блок 10, умножитель11, регистры 12 и 13 (слагаемых), блок 3514 постоянной памяти, блок .15 синхронизации, информационный вход 16 устройства, информационный выход 17устройства, выходы 18-40 блока синхронизации; входы (тактовый и запуска) 41 и 42 блока синхронизации.Блок 15 синхронизации (фиг.2) со-,держит элементы И-НЕ 43-48, счетчики49 и 50, триггер 51, узлы 52 и 53постоянной памяти, элементы И 54-56, 45,элементы НЕ 57 и 58, регистр 59,элемент 60 за е жки.Т 2 Р 1-Р 5; ТЗ = Р 2 - Р 4; Т 4 щ Р 2 - Рб;21 Т 1 + ТЗ; 22 Т 2 - Т 4; ТЗ Т 1 - ТЗ; Е 4 Т 2 + Т 4; Т ХО + 21; Х 4 = ХО + 21; ХОТ;Т = Х 1 + Е 2;Х 5 -. Х 1 - Д 2;Х 1 Т;Т = ЕЗ - Х 2;Хб "- ЕЗ + Х 2; Х 2 =Х 5; Х 5 Т = Е 4 - Х 31 Х 7 = 24 + ХЗ; ХЗ "- Х 4; Х 4Те Т 1 =ХО+Х 1; Т 1 = ХО - Х 11 Т 2 = Х 2 + ХЗ; ХЗ = Х 2 ХЗ; Р 1 =Х 1 хС 01; Р 2 = Т 2 х С 01; ХО=Р 1+Р 2; Х 2 = Р 1-Р 2. Оконечная операция; 5 10 5 20 25 30 35 40 45 50 55 Рассмотрим работу устройства привыполнении трех базовых и оконечной операций. Припустим, что прием в регистры осуществляется в начале такта по приходу заднего фронтасинхроимпульсов.Рассмотрим выполнение первой базовой операции.В превом такте по адресу АО,сформированному на выходе 18 блока 15синхронизации, из блока 1 памяти считывается значение операнда,Во втором такте по сигналу с выхода 20 блока 15 синхронизации ком- .мутатор 2 подключает выход блока 1памяти к входу регистра 6 и по сигналу с выхода 21 блока 15 синхронизации в регистр б принимается операндХО. Одновременно,по сигналу с выхода24 блока 15 синхронизации коммутатор3 подключает выход регистра 6 к входублока 7 регистров и по сигналу с выхода 31 блока 15 синхронизации в блок7 регистров принимается операнд ХОпо адресу ФО, сформированному на выходе 32 блока 15 синхронизации. Крометого, по адресу А 1, сформированномуна выходе 18 блока 15 синхронизации,из блока 1 памяти считывается значение оп ер аида Х 1,В третьем такте по адресу А 2,сформированному на выходе 18 .блока15 синхронизации, из блока 1 памятисчитывается значение операнда Х 2.Одновременно по сигналу с выхода 20блока 15 синхронизации коммутатор 2подключает выход блбка 1 памяти квходу регистра б и по сигналу с выхода 21 блока 15 синхронизации в регистр б принимается операнд Х 1. Кроме того, по сигналу с выхода 23 блока15 синхронизации коммутатор 4 подключает выход регистра 6 к входу бло 1ка 8 регистров и по сигналу с выхода 28 блока 15 синхронизации в блок8 регистров принимается операнд Х 1по адресу ФО, сформированному на выходе 29 блока 15 синхронизации.В четвертом такте по адресу АЗ,сформированному на входе 18 блока 15синхронизации, из блока 1 памяти считывается значение операнда ХЗ. Одно-.временно по сигналу с выхода 20 блока 15 синхронизации коммутатор 2.подключает выход блока 1 памяти квходу регистра б и по сигналу с выхода 21 блока 15 синхронизации в регистр б принимается операнд Х 2, а посигналу с выхода 24 блока 15 синхронизации коммутатор 3 подключает выход регистра б к входу блока 7 регистров и посигналу с выхода 31 бло 5 ка 15 синхронизации в блок 7 регистров принимается операнд Х 2,по адресу Ф 1, сформированному на выходе 32 блока 15 синхронизации. Кроме того, по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 выполняет операциюсложения над операндами ХО и Х 1, считываемыми соответственно иэ блоков 7 и 8 регистров по адресам ФО, сформированым на выходах 33 и 30 блока 15 синхронизации.В пятом такте по сигналу с выхода 21 блока 15 синхронизации в регистр 6 принимается операнд ХЗ, по сигналу с выхода 23 блока 15 синхронизации коммутатор 4 подключает выход регистра 6 к входу блока 8 регистров и по сигналу с выхода 28 блока 15 синхронизации в блок 8 регистров принимается операнд ХЗ по адресу 25 Ф 1, сформированнбму на выходе 29 блока 15 синхронизации. Одновременно по сигналу с выхода 38 блока 15 синхронизации арифметический, блок 10 выполняет операцию вычитания над операндами ХО и Х 1, считываемыми соответственно из блоков 7 и 8 регистров по адресам ФО,сформированным на выходах 33 и 30 блока 15 синхронизации. Одновременно по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенного в четвертом такте сложения с выхода арифметического блока 10, этот же результат по сигналу с выхода 40 блока 15 синхро 40 низации принимается в регистр 13 и записывается по сигналу с выхода 19 блока 15 синхронизации в блок 1 памяти по адресу АО, сформированному на выходе 18 блока 15 синхронизации.В шестом такте по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 выполняет операцию сложения над операндами Х 2 и ХЗ, считываемыми соответственно из блоков регистров .7 и 8 по адресам Ф 1, сформированным на выходах 33 и 30 блока 15 синхронизации. Одновременно по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в пятом такте операции вычитания с выхода арифметического блока 10, этот же результат по сигналу с выхода 40 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода 19 блока 15 синхронизации в блок 1 памяти по адресу А 1, сформированному на выходе 18 блока 15 синхронизацииВ седьмом такте по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 выполняет операцию вычитания над операндами Х 2 и ХЗ, считываемыми соответственно из блоков регистров 7 и 8 по адресам Ф 1, сформированным на выходах 33 и 30 блока 15 синхронизации, Одновременно по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в шестом такте операции сложения с выхода арифметического блока 10, этот же результат по сигналу с выхрда 40 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода 9 блока 15 синхронизации в блок 1 памяти по адресу А 2, сформированному на выходе 18 блока 15, синхронизации.1В восьмом такте по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в седьмом такте операции вычитания с выхода 39 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода19 блока 15 синхронизации в блок 1 памяти по адресу АЗ, сформированному на выходе 18 блока 15 синхронизации.Аналогичным образом могут быть рассмотрены выполнения второй, третьей базовых операций и оконечной операции. Так, например, при выполнении базовых операций 2 и 3 используются также умножитель 11, блок1 14 постоянной памяти, коммутатор 5 и блок 9 регистров. Вся работа устройства дискретного преобразования Фурье синхронизируется последовательностью тактовых импульсов, поступающих на вход 41 блока синхронизации и одновременно на счетные входы счетчиков 49 и 50,. триггера 51, один из входов элемента И 54 и вход элемента НЕ 57. Сигналы, необходимые для работы, вырабатываются блоком 15 синхронизациипосле поступления на вход 42 сигнала, запуска н виде короткого импульса отрицательной полярности.Н результате по сигналам с вы 5 ходов триггера 51 и элемента И 54 разблокируются счетчики 49 и 50 и на выходах узлов постоянной памяти 52 и 53 появляются соответствующие сигналы управления. 10Работа завершается и блок 15 синхронизации принимает исходное состояние прк поступлении импульса с выхода узла 52 постоянной памяти на вход триггера 51. При этом сигналами 15 с выходов триггера 51 и элемента И 54 блокируются счетчики 49 и 50. Формула изобретения201, Устройство для вычисления дискретного преобразования Фурье, содержащее первый и второй коммутаторы, первый, второй и третий регистры,умножитель и арифметический блок, вы ход которого подключен к информационному входу первого регистра, выход которого подключен к информационному входу второго регистра и первому информационному входу первого комму- З 0 татора, второй информационный вход которого подключен к выходу третьего регистра, информационный вход которого подключен к выходу нгорого коммутатора, первый информационный ,вход которого подключен к выходу умножителя, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены первый, второй и третий блоки регистров, блок .постоянной памяти, блок синхронизации и блок памяти, выход которого подключен к второму информационному входу второго коммутатора и является информационным ныходом устройства, информационным нходом которого является первый информационный вход блока памяти, выход третьего регистра подключен к первым информационным входам третьего и четвертого коммутаторов, вторые информационные входы которых подключены к выходу первого регистра, выходы первого и третьего коммутаторов подключены к информационным входам соответственно первого и нторого блоков регистров, выходы которых подключены к нходам соответственно первого и второго операторон арифметического. блока, выход четвертого коммутатора подключей кинформационному входу третьего блока регистрон, выход которого подключен к первому информационному входуумножителя, второй информационныйвход котораго подключен к выходублока постоянной памяти, выход второго регистра подключен к второмуинформационному входу блока памяти,адресный нход и вход управления записью-считыванием которого подключены соответственно к первому и второму выходам блока синхронизации, стретьего по седьмой выходы которогоподключены соответственно к управляющему входу второго коммутатора, входу записи третьего регистра, управляющим входам первого, третьего ичетвертого коммутаторов, восьмой,девятый .и десятый выходы блока синхронизации подключены соответственнок входу записи, первому и второмуадресным входам третьего блока регистров, вход записи первый и второйадресные входы второго блока регистров подключены соответственно к одиннадцатому, дненадцатому и тринадцатому выходам блока синхронизации,четырнадцатый, пятнадцатый и шестнадцатый выходы которого подключенысоответственно к входу записи, пер-,вому и второму адресным входам перво-:го блока регистров, первый и второйадресные входы блока постоянной памяти подключены соответственно к семнадцатому и восемнадцатому выходамблока синхронизации, девятнадцатый,и двадцатый выходы которого подключены к входам записи соответственноприема и выдачи информации умножителя, двадцать первый, двадцать второй и двадцать третий выходы блокасинхронизации подключены к входамсинхронизации соответственно арифметического блока, первого и второго регистрон, тактовый вход и входзапуска блока синхронизации являются соответственно тактовым входом ивходом запуска устройства,. 2. Устройство по п,1, о т л и - ч а ю щ е е с я тем, что .блок синхронизации содержит дна узла постоянной памяти, дна счетчика, триггер, регистр, три элемента И, дна элемента НЕ, элемент задержки, шесть элементов И-НЕ, информационный выход первого счетчика подключен кадресному входу первого узла постоянной памяти, с первого по четвертый выходы которого подключены соответственно к первому установочному вхо 5 ду триггера, первому входу первого элемента И, к первому и второму разрядам информационного входа регистра, выход которого подключен к адресному входу второго узла постоянной памяти,1 О выходы с первого по седьмой которого подключены к первым входам соответственно второго и третьего элементов И, с первого по пятый элементов И-НЕ, выход триггера подключен к входу обнуления первого счетчика и первому входу шестого элемента И-НЕ, выход которого подключен к второму установочному входу триггера, тактовый вход которого соединен со счетными 20 входами первого и второго счетчиков, вторым входом первого элемента И, входом первого элемента НЕи является тактовым входом блока, входом запуска которого является второй вход25 шестого элемента И-НЕ, выход первого элемента И подключен к входу обнуления второго. счетчика, информационныйвыход которого подключен к остальным разрядам информационного входа регистра, вход записи которого соединен с входом второго элемента НЕ и под-.ключен к выходу первого элемента НЕ,вЬход второго элемента НЕ подключенк вторым входам второго, третьегоэлементов И, первого элемента И-НЕ ивходу элемента задержки, выход которого подключен к вторым входам с второго по пятый элементов И-НЕ, пятыйвыход первого узла постоянной памятиподключен к третьему входу второгоэлемента И-НЕ, шестой выход первогоузла постоянной памяти, выход второгоэлемента И-НЕ, восьмой выход второгоузла постоянной памяти, выход первого элемента НЕ, девятый, десятый иодиннадцатый выходы второго узлапостоянной памяти, выход Пятого элемента И-НЕ, двенадцатый и тринадцатыйвыходы второго узла постоянной памяти, выход четвертого элемента И"НЕ,четырнадцатый и пятнадцатый выходывторого узла постоянной памяти, выходтретьего элемента И-НЕ, шестнадцатый и семнадцатый выходы второгоузла постоянной памяти, седьмой выход первого узла постоянной памяти,восемнадцатый выход второго узлапостоянной памяти, выходы первогоэлемента И-НЕ и третьего элемента И,девятнадцатый выход второго узлапостоянной памяти, выходы второгоэлемента НЕ и второго элемента И являются выходами соответственно спервого по двадцать третий блока1425708 с(н) к(2 к(7 с( Ы к т 1).к О)Х 26)к б) 8 Ы) ъ(2) утя Редактор3Заказ 47 49 , Ти ВНИИПИ Гос по делам 3035, .Москвж 704 арственногзобретений Ж, Рауш Подписное СССРЙ ,д.4 Л комнте откры кая на

Смотреть

Заявка

4213589, 18.03.1987

СПЕЦИАЛЬНОЕ КОНСТРУКТОРСКОЕ БЮРО ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ИНСТИТУТА КИБЕРНЕТИКИ АН ЭССР

АРРО ИЛЬМАР ОТТОВИЧ, ГЕРМ ЭДУАРД ИОГАННЕСЕВИЧ, СМОЛЯНСКИЙ ЛЕОНИД ЭДУАРДОВИЧ

МПК / Метки

МПК: G06F 17/14

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

Опубликовано: 23.09.1988

Код ссылки

<a href="https://patents.su/8-1425708-ustrojjstvo-dlya-vychisleniya-diskretnogo-preobrazovaniya-fure.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для вычисления дискретного преобразования фурье</a>

Похожие патенты