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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПо ДЕЛДМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) Авторское свидетельство СССР Р 1083200, кл. 0 06 Г 15/332, 1982.Авторское свидетельство СССР Р 877555, кл. С 06 Р 15/332, 1980,(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано при проведении спектральЯО 1218395 А51)4 О 06 Р 15 332 ного анализа цифровых сигналов в реальном масштабе времени. Цельюизобретения является повышение быстродействия при обработке сигналовс переменной частотой среза, связанное с уменьшением количества арифметических операций. Устройство содержит блоки оперативной и постоянной памяти, блоки элементов И и ИЛИ,блок счетчиков, управляемый делитель частоты и блок управления,который включает семь реверсивныхсчетчиков, четыре. элемента И-НЕ, четыре элемента НЕ, три одновибратора, узлы элементов ИСКЛЮЧАЮЩЕЕ ИЛИи НЕ, элементы ИЛИ и элемент И. 10 ил)1 зобретение относится к вычислительной технике и предназначено для спектральноо анапиза электри - ческих сигналов, представленных в цифровой форме, в реальном масштабе времени. Применение устройства связано с цифровой обработкой электрических сигналов с изменяющейся во времени частотой среза, к которым относятся такие сигналы, как, например, речевой сигнал в аппаратуре связи, сигналы гидро,- звуко- и радиолокации, навигации и телеметрии.Целью изобретения является повышение быстродействия устройства при обработке сигналов с переменной частотой среза.На фиг.1 представлен алгоритм БПФ; на фиг.2 - функциональная схема устройства; на фиг.3 - блок элементов И; на фиг.4 - блок счетчиков; на фиг.5 - блок элементов ИЛИ; на фиг.6 - управляемый делитель частоты; на фиг,7 - блок управления; на фиг.8 - второй дешифратор; на фиг.9 - первый дешифратор; на фиг.10 - третий дешифратор.Устройство для реализации БПФ содержит блок памяти 1, арифметический блок 2, блок постояннай памяти 3, блок элементов И 4, блок счетчиков 5, блок элеиентов ИЛИ 6, управляемый делитель частоты 7, блок управления 8, второй дешифратор 9, первый дешифратор 1 О, третий дешифратор 11. Вход 12 является информационным входом устройства, вход 13 -входом запуска, вход 14 - вход за; датчика частоты среза, вход 15 - тактовый вход.Блок 4 элементов И содержит первые элементы И-НЕ 16, вторые элементы И-НЕ 17, третьи элементы И-НЕ 18, элементы И 19, элемент . НЕ 20. Входы 21-24 являются входаии блока 4, а выход 25 - выходом блока 4.Блок 5 счетчиков содержит счетчик 26, входы 27-30 являются входами блока 5, а выход 31 - выходом блока 5.Блок 6 элементов ИЛИ содержит элементы ИЛИ-НЕ 32 и элементы ИЛИ 33. Входы 34-36 являются входами блока 6, а выход 37 - выходом блока 6.Управляемый делитель частоты 7 содержит элементы И 38, элементы218 195 2 35 40 45 50 55 5 О 15 20 25 30 И-Е 19 и 40, элементы 1 4и 4.7,триггеры 43. Входы 44-46 являются входами блока 7, а выход 47выходом блока 7,Блок 8 управления содержит счет"чики 48-52, элементы И-НЕ 53-55,элементы НЕ 56-58, одновибраторы59-61, элемент И. 62, узел элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 63, элементыИЛИ 64, элемент И-НЕ 65, узел элементов НЕ 66, элемент НЕ 67, Входы68-73 являются входами блока 8, авыходы 74-78 - выходами блока 8.Дешифратор 9 содержит дешифратор79 со входом 80 и выходом 81.Дешифратор 10 содержит дешифратор 82 и элементы НЕ 83. Вход 84является входом дешифратора 10, авыходы 85-86 - выходами дешифратора 10.Третий дешифратор 11 содержитдешифратор 87, элементы НЕ 88, элемент И-НЕ 89, одновибратор 90, Вход91 является входом третьего дешифратора 11, а выходы 92-94 - выходами третьего дешифратора 1.Вычисление БПФ по алгоритму, представленному на фиг.1, осуществляютследующим образом.Вначале вычисляется БПФ от двухточек Х(0) и Х(8), затем от четырехточек Х(0) и Х(8), Х(4) и Х(12), нобез повтора в вычислениях базовыхопераций от предыдущего числа точекБПФ, затеи от восьми точек Х(0),Х(8), Х(4), Х(12), Х(2), Х(10), Х(6) Х(14), вычисляются только дополнительные базовые операции, которые возникают при переходе отчетырех- точечного БПФ к восьмиточечному, и затем от всех шестнадцати точек Х(0), Х(8),Х(4),Х(12),Х(2),Х( 10),Х(6), Х(,14), Х(1), Х(9), Х(5), Х(13), Х(3), Х(11), Х(7), Х(15), но опять - -.таки вычисляются только дополнительные базовые операции, необходимые для шестнадцатиточечного БПФ без повторения ранее вычисленных базовых операций от васьмиточечного БПФ.Базовые операции, которые вычисляются при переходе к следующему числу точек БПФ и названные как дополнительные, расположены в алгоритме БПФ ( фиг.1) виде "угла". На фиг. базовые операции, входящие в соответствующий "угол", имеют одинаковое число окружностей. Число окружностей в базовой операции определяет номер "угла алгоритма БПФ, Вы -20 30 3 1218числение БПФ по алгоритму, представленному на фнг.1, осуществляется путем вычисления углов , с носледовательным увепичением номера угланачиная от единицы для двух точеки кончая номером угла и для Б точек преобразования Фурье. Номер вычисляемого "угла" совпадает с номеромнаибольшей итерации, вычисляемой наэтом "угле", и, следовательно, номернаибольшего "угла совпадает с числом итераций и для м точек БПФ(п = 1 о 8 Ь), соответствующим максимальной частоте среза Г,рКонец вычисления БПФ определяется окончанием вычисления БПФ от числа точек, определяемых соответствующей частотой среза входного случайного сигнала в данный промежутоквремени. Результаты по вычислениюспектра после окончания вычисленияБПФ находятся (фиг.1) в верхних узлах алгоритма или начальных ячейкахпамяти устройства БПФ.Количество значений спектраль 25ных составляющих равняется числувременных отсчетов, от которого получено БПФ для существующей в данныймомент времени частоты среза входного случайного сигнала.Так, для Б-точечного БПФ, соответствующего максимальной частотесреза Г,р, получим следующую последовательность вычисления БПФ и расположение спектральных составляющих.Если частота среза Г,р в текущий 35промежуток времени совпадает с максимальной частотой среза Г, , товычисление БПФ проводится по изложенному выше принципу, начиная от двухточек, затем четырех точек и заканчивается вычислением от 11 точек,на и:ц итерации, число спектральныхсоставляющих равно И.Если частота среза Г.р в текущийпромежуток времени в два раза мень-45ше по сравнению с максимальной частотой среза Г,,вычисление БПФзаканчивается от 11/2 точек на(п)-й итерации, спектральныесоставляющие находятся в начальных 50Б/2 узлах алгоритма или ячейках памяти устройства БПФ.Аналогично, если частоты срезаГр в четыре раза меньше максимальной частоты среза Г, . получим, 55что вычисление БПФ закайчиваетсяот И/4 точек на (п)-й итерации,спектральные составляющие находятся 395 4в начальных Б/4 узлах алгоритма или ячейках памяти устройства БПФ.Так продолжается и далее, например, если частота среза Г,р в восемь раз меньше максимальной частоты среза Г,р то вычисление БПФ заканчивается от М/8 точек на (и)-й итерации, спектральные составляющие находятся в начальных Л/8 узлах ал-. горитма или ячейках памяти устройства БПФ.Устройство работает следующим образом.На вход 12 устройства (фиг,2) поступают выборки сигнала в двоично-, инверсном порядке, которые записываются в блоке 1 памяти. В блоке 3 записаны комплексные значения коэффициентов, расположенные в порядке следования своих номеров.В арифметический блок 2 по входу из блока 1 оперативной памяти .поступает два значения операнда, по другому входу из блока 3 поступают значения комплексного коэффициента. Арифметический блок 2 осуществляет вычисления двухточечного БПФ, результаты которого по выходу заносятся в блок 1 памяти на прежние адреса ячеек памяти.Блок 4 обеспечивает подготовку начального значения адреса операнда для загрузки в блок 5 адреса первого операнда.В блоке 5 выполняется вычислениепоследующего значения адреса первого операнда путем добавления единицы, сброса в нуль и предварительной записи.В блоке 6 на основании значения адреса первого операнда и номера ите рации определяется величина адреса второго операнда. Кроме этого,сигнал, поступающий на вход блока 6, осуществляет последовательную выда чу адресов первого и второго операндов на вход блока 1 памяти. В делителе 7 вычисляется адрес коэффициента с помощью организации счета последующего адреса коэффициента по соответствующему разряду счетчика, определяемому номером итерации.Блок 8 управления выполняет выдачу поСледовательности управляющих сигналов на соответствующне блоки в процессе вычисления БПФ.1 О Дешифратор 9 по номеру "угла"определяет число итераций и начальный адрес углаДешифратор 1 О по номеру итерации определяет число базовых опера 5ций в базовом блоке БПФ,Третий дешифратор 11 по числуоставшихся выполнить итераций наданном угле определяет число базовых блоков БПФ и сигналы управления при переходе к вычислению последней итерации данного "угла".П р и м е р , Вычисление четвертого угла шестнадцатиточечного БПФ.Начальный адрес загрузки длячетвертого угла, при входе в каждую итерацию равен восьми, числоВитераций равно четырем, на первыхтрех итерациях загружается начальныйадрес восемь, на четвертой (последней) итерации в угле загружаетсявсегда нулевой адрес, Число базовыхблоков на первой итерации четыре,на второй итерации - два, на третьей и четвертой итерациях по одномубазовому блоку,Число базовых операций двухточечного БПФ в базовом блоке напервой итерации одна, на второй30итерации - две, на третьей итерациичетыре, на четвертой итерации - восемь базовых операций.После окончания вычисления последней базовой операции на третьемугле с выхода блока 8 управления поступает сигнал, который в блоке 5осуществляет запись начальногозначения адреса первого операнда,а в делителе 7 осуществляет сброс внуль значения адреса коэффициента.Этот сигнал с выхода блока 8 управления появляется всегда при началевычислений нового базового блока.На последней чвтвертой итерациина вход блока 5 с выхода третьегодешифратора поступает сигнал сброса в нуль адреса первого операнда,чем и осуществляется начальная установка адреса первого операнда дляпоследней итерации в каждом угле.По входу в блок 5 с выхода блока 4 поступает начальное значениеадреса, записываемое в блоке 5 приначале вычислений нового базовогоблока сигналом с выхода блока 8 управления. Формирование начальногозначения адреса в блоке 4 выполняется на основании текущего значения адреса первого операнда, поступающего на его вход, и номера итерации, поступающего на другой вход. Начальное значение адреса при переходе с первой итерации каждого угла на вторую, со второй на третью и т.д. до предпоследней итерации угла формируется по номеру угла, поступающему на вход блока 4 с выхода первого дешифратора. управление формированием начального адреса осуществляется с выхода блока 8 управления по входу блока 4. Сигнал управления, поступающий на вход блока 4, осуществляет пропускание на выходе блока 4 начального значения адреса, соответствующего номеру угла, поступающего с выхода первого дешифратора на вход блока 4. Этот сигнал управления появляется каждый раз, когда выполняется переход с первой итерации на вторую, с второй - на третью и т.д. до предпоследней итерации данного угла включительно, т.е. когда происходит загрузка адреса в блоке 5 возникающая при вычислении первого базового блока на второй, третьей и т.д. до предпоследней итерации данного угла, Для остальных базовых блоков, входящих в итерацию данного угла, кроме первого базового блока, начальное значение адреса в блоке 4 формируется по текущему значению адреса первого операнда, поступающего на вход с выхода блока 5, и номеруитерации, поступающему на другой вход с выхода второго дешифратора.Делитель 7 вычисляет адрес коэффициента для каждой базовой операции двухточечного БПФ. С выхода блока 8 управления на вход делителя 7 поступает сигнал сброса в нуль, это происхоидт каждый раз, когда начинаются вычисления в базовом блоке БПФ, что соответствует выбору коэффициента У из нулевой ячейки памяти блока 3. На вход делителя 7 поступает сигнал с выхода второго дешифратора, который управляет переключением счетного входа делителя.7.Под воздействием управляющеговхода счетный вход в делителе 7подключается к соответствующим разрядам счетчика для выполнения счета адреса последующего коэффициента в базовом блоке. Переключениесчетного входа в делителе 7 осуществляется в зависимости от номера итерации, начиная со старших рядов счетчика для первой итерации и кончая самым младшим разрядом счетчика для последней итерации.На вход блока 8 управления подается сигнал запуска, определяющий запуск устройства по вычислению БПФ. На другой вход блока 8 управления по дается сигнал частоты среза, который определяет необходимое значение числа выполняемых итераций для слу . чайного входного сигнала в рассматриваемый промежуток времени. Сигнал15 частоты среза на вход блока 8 управления должен поступить до момента времени, при котором вычисления БПФ для соответствующего значения сигнала частоты среза, должны20 быть закончены. Например, если сигнал частоты среза Г, определяется неравенством с ср.макс сссрасср.максХ / где Г.,с соответствует вычислению семи итераций, то в этом случае сигнал частоты среза Гравен семи и должен поступить не позже конца вычисления последней базовой операции в седьмом угле вычисления БПФ.Для сигналачастоты среза,определя- ЗО емого неравенством Е сЕсрЕсс.оскс ср с.оскс вычисления БПФ должны быть окончены на шестом угле, поэтому сигнал частоты среза, поступающий на вход блока 8 управления, равен шести и должен поступить не позже конца вычисления последней базовой операции в шестом угле.Аналогично, для Есрмакс я-Еср с с.накс 40 сигнал частоты среза равен пяти,,р,с ср., а, яркая аартсасреза равен четырем.На третий вход 15 блока 8 управления поступают тактовые импульсы с периодом, равным времени выполнения базовой операции в арифметическом блоке 2.На четвертый вход блока 8 управления с выхода дешифратора О подается сигнал, определяющий значение числа базовых операций в базовом блоке, которое зависит от номера итерации. На пятый вход блока 8 управления с выхода третьего дешифратора 1 поступает сигнал, определяющий значение числа базовых блоков на итерации. На шестой вход блока 8 управления с выхода третьего дешифратора 11 поступает сигнал блокировкина последней итерации в угле, чтобы обеспечить формирование начального значения адреса в блоке 4 от текущего значения адреса первого операнда и номера итерации, при переходе к вычислению следующего угла БПФ. На второй выход блока 8 управления поступает сигнал со счетчика угла, который в дешифраторе 9 распределяется по соответствующему разряду и определяет номер угла вычисления БПФ.На третий выход блока 8 управления поступает сигнал с инкрементного счетчика итерации, который в дешифраторе 10 распределяется по соответствующему разряду и определяет номер итерации.На четвертый выход блока 8 управления поступает сигнал с декрементного счетчика итерации, который в третьем дешифраторе 11 распределяется по соответствующему разряду и определяет число оставшихся выполнить итераций в узле вычисления БПФ.Результат вычисления БПФ для соответствующего значения сигнала частоты среза находится в ячейках блока 1 памяти, начиная с нулевой и кончая ячейкой с номером г 1 . Величина ч определяется в зависимости от значения сигнала частоты срема, дяя Есрмакс сЕ,рс Гса сансасс М2ср "а"с С С рсмс:макст = - -1; асср.макс с 1 ср с 1 яСнанс, ссс: -- 1Ф о р м у л.а и з о б р е т е н и яУстройство для реализации быстрого преобразования Фурье, содержащее блок памяти, первый выход которого подключен к входу операндов арифметического блока, выход результата которого подключен к информационному входу блока памяти, выход блока постоянной памяти подключен к входу коэффициентов арифметического блока, а информационный вход блока памяти является информационным входом устройства, блок управления и три дешифратора, о т л и ч аю щ е е с я тем, что, с целью повы25 шения быстродействия при обработке сигналов с переменной частотой среза, в него введены блок элементов ИЛИ, блок элементов И, блок счетчиков и управляемый делитель частоты, вход задания коэффициента деления которого объединен с первыми входами блока элементов И и блока элементов ИЛИ и подключен к первому выходу первого дешифратора, выход второго дешифратора подключен к второму входу блока элементов И, выход которого подключен к информационному входу блока счетчиков, информационный выход которого подключен к третьему входу блока элементов И и второму входу блока элементов ИЛИ, выход которого подключен к адресному входу блока памяти, второй выход которого подключен к третьему входу блока элементов ИЛИ, выход управляемого делителя частоты подключен к адресному входу блока постоянной памяти, при этом блок управления содержит семь реверсивных счетчиков, три одновибратора, узел элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, узел элементов НЕ, четыре элемента И-НЕ, четыре элемента НЕ, два элемента ИЛИ и30 элемент И, выход которого подключен к первым входам первого, второго и третьего элементов И-НЕ и счетному входу первого реверсивного счетчика, вход сложения которого подключен к выходу первого одновибратора, вход запуска которого объединен с вторыми входами первого, второго и третьего элементов И-НЕ и подключен к выходу обнуления второго реверсивного счетчика, вход вычитания которого объединен с входом сложения третьего реверсивного счетчика и подключен к выходу второго одновибратора, вход запуска которого объединен с третьими входами первого и второго элементов И-НЕ и подключен к выходу обнуления четвертого ре.версивного счетчика, вход вычитания которого подключен к выходу обнуления пятого реверсивного счет чика, вход вычитания которого подключен к выходу третьего одновибратора, вход запуска которого объединен с четвертым входом первого элемента И-НЕ и подключен к выходу обну ления шестого реверсивного счетчика, вход вычитания которого подключен к выходу. обнуления седьмого реверсивного счетчика, счетный вход которого объединен со счетным входом шестого реверсивного счетчика и подключен к выходу первого элемента НЕ,вход которого подключен к выходупервого элемента И-НЕ, выход второго элемента И-НЕ подключен к входу второго элемента НЕ, выход которого подключен к счетным входамчетвертого и пятого реверсивныхсчетчиков, выход третьего элемента И-НЕ подключен к входу обнулениятретьего реверсивного счетчика и входу третьего элемента НЕ, выходкоторого подключен к счетному входу второго счетчика, информационныйвыход которого объединен с первымвходом узла элементов ИСКЛЮЧАЮЩЕЕИЛИ и подключен к информационномувыходу первого реверсивного счетчика, первый, второй и третий выходыузла элементов ИСКЛЮЧАЮЩЕЕ ИЛИ подключены соответственно к первомувходу первого элемента ИЛИ, первому и второму входам второго элемента ИЛИ, выход которого подключенк второму входу первого элементаИЛИ, выход которого подключен к первому входу элемента И, информационный выход (кроме первого разряда)пятого реверсивного счетчика объединен с информационным выходом четвертого реверсивного счетчика иподключен к входу узла элементовНЕ,выход которого подключен к первому входу четвертого элемента И-НЕ,выход которого подключен к входучетвертого элемента НЕ, а выход первого разряда пятого реверсивногосчетчика подключен к второму входу четвертого элемента И-НЕ, причем второй вход элемента И является входом запуска устройства, входом задания частоты среза устройства является второй вход узла элементов ИСКЛЮЧАКВ 1 ЕЕ ИЛИ, вход вычитания седьмого реверсивного счетчика объединен со счетными. входамиблока счетчиков и управляемого делителя частоты и является тактовымвходом устройства, второй выходпервого дещифратора подключен к информационным входам шестого иседьмого реверсивных счетчиков,первый и второй выходы третьего дешифратора подключены соответственнок входу обнуления блока счетчикаи третьему входу четвертого элемн1218395 2 Хф 4 з) Х(Ю) х(г) ХУ Ю) 9) ХФ х(7 Ф Х(7) Х(7 Ф та И-НЕ, а третий выход третьегодешифратора подключен к информационным входам четвертого и пятого реверсивных счетчиков, выход третьегоодновибратора подключен к входу обнуления управляемого делителя частоты и входу разрешения записи блоК(Р) Х(8) Х Х(РЗ) Х(3) х(л) ка счетчиков, информационные выходыпервого, второго и третьего реверсивных счетчиков подключены к входам соответственно второго, третьегои первого дешифраторов, а выходчетвертого элемента И-НЕ подключенк четвертому входу блока элементов И.