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

 

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕО (ИХ

РЕСПУБЛИН (5114 G 06 F 15 332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCKOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНР11ТИЙ (21) 3795650/24-24, (22) 26.09.84 (46) 15.03.86. Бюл. 11 - 1О (72) Влад.С.Бабанский и Вит.С.Бабанский (53) 681.32(088.8) (56) Авторское свидетельство СССР

Р 1083200, кл. G 06 F 15/332, 1982.

Авторское свидетельство СССР

У 877555, кл. G 06 F 15/332, 1980. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТ РОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано при проведении спектраль„„SU„„1218395 А ного анализа цифровых сигналов в реальном масштабе времени. Целью изобретения является повышение быстродействия при обработке сигналов с переменной частотой среза, связанное с уменьшением количества арифметических операций. Устройство содержит блоки оперативной и постоянной памяти, блоки элементов И и KIH, блок счетчиков, управляемый делитель частоты и блок управления, который включает семь реверсивных счетчиков, четыре. элемента И-НЕ, четыре элемента НЕ, три одновибратора, узлы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и НЕ, элементы ИЛИ и элемент И. 10 ил

1 l

Изобретение относится к вычислительной технике и предназначено для спектрально>о анапиза электри— ческих сигналов, представленных в цифровой форме, в реальном масштабе времени. Применение устройства связано с цифровой обработкой электрических сигналов с изменяющейся во времени частотой среза, к которым относятся такие сигналы, как, например, речевой сигнал в аппаратуре связи, сигналы гидро,звуко- и радиолокации, навигации и телеметрии.

Целью изобретения является повышение быстродействия устройства при обработке сигналов с переменной частотой среза.

На фиг.l представлен алгоритм

БПФ; на фиг.2 — функциональная схема устройства; на фиг.3 — блок элементов И; на фиг.4 — блок счетчиков; на фиг.5 — блок элементов

ИЛИ; на фиг.6 — управляемый делитель частоты; на фиг.7 — блок управления; на фиг.8. — второй дешифратор; на фиг.9 — первый дешифратор; на фиг.10 — третий дешифратор.

Устройство для реализации БПФ содержит блок памяти 1, арифметический блок 2, блок постояннай памяти 3, блок элементов H 4, блок счетчиков

5, блок элеиентов ИЛИ 6, управляемый делитель частоты 7, блок управления 8, второй дешифратор 9, первый дешифратор 10, третий дешифратор 11. Вход 12 является информационным входом устройства, вход 13-- входом запуска, вход 14 — вход за; датчика частоты среза, вход i5 тактовый вход.

Блок 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

5 !

О

И-ill 19 и 40, элементы 11 41 и 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, элементы HE 88, элемент И-НЕ 89, одновибратор 90. Вход

91 является входом третьего дешифратора ll, а выходы 92-94 — выходами третьего дешифратора 11.

Вычисление БПФ по алгоритму, представленному на фиг.l, осуществляют следующим образом.

Вначале вычисляется БПФ от двух точек Х(0) и Х(8), затем от четырех точек Х(0) и Х(8), Х(4) и Х(12), но без повтора в вычислениях базовых операций от предьдущего числа точек

БПФ, затеи от восьми точек Х(0), Х(8), Х(4), Х(12), Х(2), Х(10), Х(6) Х(14), вычисляются только дополнительные базовые операции, которые возникают при переходе от четырехточечного БПФ к восьмиточечному, и затем от всех шестнадцати точек Х(0), Х(8),Х(41,Х(12),Х(2),Х(10),Х(6), Х(14), X(l), Х(9), Х(5), Х(13), Х(3), Х(11), Х(7), Х(15), но опять —таки вычисляются только дополнительные базовые операции, необходимые для шестнадцатиточечного БПФ без повторения ранее вычисленных базовых операций от васьмиточечного БПФ.

Базовые операции, которые вычисляются при переходе к следующему числу точек БПФ и названные как дополнительные, расположены в алгоритме БПФ (фиг. 1) виде "угла". На фиг. l базовые операции, входящие в соответствующий "угол", имеют одинаковое число окружностей. Число окружностей в базовой операции определяет номер "угла" алгоритма БПФ. Вы—

30

3 1218 числение БПФ по алгоритму, представленному на фнг.1, осуществляется путем вычисления углов, с последовательным увепичением номера угла начиная от единицы для двух точек и кончая номером угла и для N точек преобразования Фурье. Номер вычисляемого "угла" совпадает с номером наибольшей итерации, вычисляемой на этом "угле", и, следовательно, номер наибольшего "угла совпадает с числом итераций и для и точек БПФ (п = log N), соответствующим максимальной частоте среза f,р <

Конец вычисления БПФ определяется окончанием вычисления БПФ от числа точек, определяемых соответствующей частотой среза входного случайного сигнала в данный промежуток времени. Результаты по вычислению спектра после окончания вычисления

БПФ находятся (фиг.1) в верхних узлах алгоритма или начальных ячейках памяти устройства БПФ.

Количество значений спектраль25 ных составляющих равняется числу временных отсчетов, от которого получено БПФ для существующей в данный момент времени частоты среза входного случайного сигнала.

Так, для N-точечного БПФ, соответствующего максимальной частоте среза f,ð „, получим следующую последовательность вычисления БПФ и расположение спектральных составляющих.

Если частота среза f,ð в текущий промежуток времени совпадает с максимальной частотой среза f, „ „ то вычисление БПФ проводится по изложенному выше принципу, начиная от двух точек, затем четырех точек и закан- 40 чивается вычислением от N точек, на и=ц итерации, число спектральных составляющих равно И.

Если частота среза f в текущий промежуток времени в два раза мень- 45 ше по сравнению с максимальной частотой среза f „ „,вычисление БПФ заканчивается от N/2 точек на (п-1)-й итерации, спектральные составляющие находятся в начальных 50

N/2 узлах алгоритма или ячейках памяти устройства БПФ.

Аналогично, если частоты среза

Г р в четыре раза меньше максимальной частоты среза f, . получим, 55 что вычисление БПФ закайчивается от N/4 точек на (п-2)-й итерации, спектральные составляющие находятся

395 4 в начальных N/4 узлах алгоритма или ячейках памяти устройства БПФ.

Так продолжается и далее, например, если частота среза f,ð в восемь раз меньше максимальной частоты среза fñðìà » то вычисление БПФ заканчивается от N/8 точек íà (n-3)-й итерации, спектральные составляющие находятся в начальных Л/8 узлах ал-. горитма или ячейках памяти устройства БПФ.

Устройство работает следующим образом.

На вход 12 устройства (фиг.2) поступают выборки сигнала в двоично-. инверсном порядке, которые записываются в блоке 1 памяти. В блоке 3 записаны комплексные значения коэффициентов, расположенные в порядке следования своих номеров.

В арифметический блок 2 по входу из блока 1 оперативной памяти .поступает два значения операнда, по другому входу из блока 3 поступают значения комплексного коэффициента.

Арифметический блок 2 осуществляет вычисления двухточечного БПФ, результаты которого по выходу заносятся в блок 1 памяти на прежние адреса ячеек памяти.

Блок 4 обеспечивает подготовку начального значения адреса операнда для загрузки в блок 5 адреса первого операнда.

В блоке 5 выполняется вычисление последующего значения адреса первого операнда путем добавления единицы, сброса в нуль и предварительной записи.

В блоке 6 на основании значения адреса первого операнда и номера ите. рации определяется величина адреса второго операнда. Кроме этого,сигнал, поступающий на вход блока 6, осуществляет последовательную выда чу адресов первого и второго операндов на вход блока 1 памяти.

В делителе 7 вычисляется адрес коэффициента с помощью организации счета последующего адреса коэффициента по соответствующему разряду счетчика, определяемому номером итерации.

Блок 8 управления выполняет выдачу поСледовательности управляющих сигналов на соответствую@ щне блоки в процессе вычисления

БПФ.

12 18395

1О

Дешифратор 9 по номеру "угла" определяет число итераций и начальный адрес "угла".

Дешифратор 10 по номеру итерации определяет число базовых опера5 ций в базовом блоке БПФ.

Третий дешифратор 11 по числу оставшихся выполнить итераций на данном угле определяет число базовых блоков БПФ и сигналы управления при переходе к вычислению послед. ней итерации данного "угла".

Пример . Вычисление четвертого угла шестнадцатиточечного БПФ.

Начальный адрer. загрузки для четвертого угла, при входе в каждую итерацию равен восьми, число итераций равно четырем, на первых трех итерациях загружается начальный адрес восемь, на четвертой (последней) итерации в угле загружается всегда нулевой адрес. Число базовых блоков на первой итерации четыре, на второй итерации — два, на третьей и четвертой итерациях по одному базовому блоку.

Число базовых операций двухточечного БПФ в базовом блоке на первой итерации одна, на второй

30 итерации — две, на третьей итерации . четыре, на четвертой итерации — восемь базовых операций.

После окончания вычисления послед. ней базовой операции на третьем угле с выхода блока8 управления поступает сигнал, который в блоке 5 осуществляет запись начального значения адреса первого операнда, а в делителе 7 осуществляет сброс в нуль значения адреса коэффициента.

Этот сигнал с выхода блока 8 управления появляется всегда при начале вычислений нового базового блока.

На последней четвертой итерации на вход блока 5 с выхода третьего дешифратора поступает сигнал сброса в нуль адреса первого операнда, чем и осуществляется начальная установка адреса первого операнда для последней итерации в каждом угле.

По входу в блок 5 с выхода блока 4 поступает начальное значение адреса, записываемое в блоке 5 при начале вычислений нового базового блока сигналом с выхода блока 8 управления. Формирование начального значения адреса в блоке 4 выполняется на основании текущего значения адреса первого операнда, поступающего на его вход, и номера итерации, поступающего на другой вход. Начальное значение адреса при переходе с первой итерации каждого угла на вторую, со второй на третью и т.д. до предпоследней итерации угла формируется по номеру угла, поступающему на вход блока 4 с выхода первого дешифратора. управление формированием начального адреса осуществляется с выхода блока 8 управления по входу блока 4. Сигнал управления, поступающий на вход блока 4, осуществляет пропускание на выходе блока 4 начального значения адреса, соответствующего номеру угла, поступающего с выхода первого дешифратора на вход блока 4. Этот сигнал управления появляется каждый раз, когда выполняется переход с первой итерации на вторую, с второй — на третью и т.д. до предпоследней итерации данного угла включительно, т.е. когда происходит загрузка адреса в блоке 5 возникающая при вычислении первого базового блока на второй, третьей и т.д. до предпоследней итерации данного угла. Для остальных базовых блоков, входящих в итерацию данного угла, кроме первого базового блока, начальное значение адреса в блоке 4 формируется по текущему значению адреса первого операнда, поступающего на вход с выхода блока

5, и номеру итерации, поступающему на другой вход с выхода второго дешифратора.

Делитель 7 вычисляет адрес коэффициента для каждой базовой операции двухточечного БПФ. С выхода блока 8 управления на вход делителя 7 поступает сигнал сброса в нуль, это происхоидт каждый раз, когда начинаются вычисления в базовом блоке БПФ, что соответствует выбору коэффициента W из нулевой ячейки памяти блока 3. На вход делителя 7 поступает сигнал с выхода второго дешифратора, который управляет переключением счетного входа делителя.7. !

Под воздеиствием управляющего входа счетный вход в делителе 7 подключается к соответствующим разрядам счетчика для выполнения счета адреса последующего коэффициента в базовом блоке. Переключение счетного входа в делителе 7 осуще1218395 ствляется в зависимости от номера итерации, начиная со старших рядов счетчика для первой итерации и кончая самым младшим разрядом счетчика для последней итерации.

На вход блока 8 управления подается сигнал запуска, определяющий запуск устройства по вычислению БПФ.

На другой вход блока 8 управления по- 10 дается сигнал частоты среза, который определяет необходимое значение числа выполняемых итераций для слу . чайного входного сигнала в рассматриваемый промежуток времени. Сигнал

15 частоты среза на вход блока 8 управления должен поступить до момента времени, при котором вычисления

БПФ для соответствующего значения сигнала частоты среза, должны

20 быть закончены. Например, если сигнал частоты среза f< определяется. неравенством асср.Р2акс Еср c fuff

Х / где f«,m«f. соответствует вычислению семи итераций, то в этом случае сигнал частоты среза f > равен семи и должен поступить не позже конца вычисления последней базовой операции в седьмом угле вычисления БПФ.

Для сигналачастоты среза,определя- Зо емого неравенством Е

CP.Р2&КС р СР.И22КС

ff вычисления БПФ должны быть окончены на шестом угле, поэтому сигнал частоты среза, поступающий на вход блока 8 управления, равен шести и должен поступить не позже конца вычисления последней базовой операции в шестом угле.

Ан -логично» для f,f ffaKc fcf, с сР.22акс 4р сигнал частоты среза равен пяти, М ., „„, -*р- .р „»„СЯРЯЯЯ «»саяр»1

1р 2 среза равен четырем.

На третий вход 15 блока 8 управления поступают тактовые импульсы с периодом, равным времени выполнения базовой операции в арифметическом блоке 2.

На четвертый вход блока 8 управления с выхода дешифратора 10 подается сигнал, определяющий значение числа базовых операций в базовом блоке, которое зависит от номера итерации. На пятый вход блока 8 управления с выхода третьего дешифратора 11 поступает сигнал, определяющий значение числа базовых блоков на итерации. На шестой вход блока

8 управления с выхода третьего дешифратора ll поступает сигнал блокировки на последней итерации в угле, чтобы обеспечить формирование начального значения адреса в блоке 4 от текущего значения адреса первого операнда и номера итерации, при переходе к вычислению следующего угла

БПФ. На второй выход блока 8 управления поступает сигнал со счетчика угла, который в дешифраторе 9 распределяется по соответствующему разряду и определяет номер угла вычисления БПФ.

На третий выход блока 8 управления поступает сигнал с инкрементного счетчика итерации, который в дешифраторе 10 распределяется по соответствующему разряду и определяет номер итерации.

На четвертый выход блока 8 управления поступает сигнал с декрементного счетчика итерации, который в третьем дешифраторе 11 распределяется по соответствующему разряду и определяет число оставшихся выполнить итераций в узле вычисления

БПФ.

Результат вычисления БПФ для соответствующего значения сигнала частоты среза находится в ячейках блока 1 памяти, начиная с нулевой и кончая ячейкой с номером Рп . Величина Р2 определяется в зависимости от значения сигнала частоты cpess, дяя Е a»

Р»f асар„„, м

PTER = — -1;

f р м c f a S f »» а» =с — - 1

Формула изобретения

Устройство для реализации быстрого преобразования Фурье, содержащее блок памяти, первый выход которого подключен к входу операндов арифметического блока, выход результата которого подключен к информационному входу блока памяти, выход блока постоянной памяти подключен к входу коэффициентов арифметического блока, а информационный вход блока памяти является информационным входом устройства, блок управления и три дешифратора, о т л и ч аю щ е е с я тем, что, с целью повы

l218395

25 шения быстродействия при обработке сигналов с переменной частотой среза, в него введены блок элементов ИЛИ, блок элементов И, блок счетчиков и управляемый делитель частоты, вход задания коэффициента деления которого объединен с первыми входами блока элементов И и блока элементов ИЛИ и подключен к первому выходу первого дешифратора, выход второго дешифратора подключен к второму входу блока элементов И, выход которого подключен к информационному входу блока счетчиков, информационный выход которого подключен к третьему входу блока элементов

И и второму входу блока элементов

ИЛИ, выход которого подключен к адресному входу блока памяти, второй выход которого подключен к третьему входу блока элементов ИЛИ, выход управляемого делителя частоты подключен к адресному входу блока постоянной памяти, при этом блок управления содержит семь реверсивных счетчиков, три одновибратора, узел элементов ИСК1ПОЧАЮЦЕЕ ИЛИ, узел элементов НЕ, четыре элемента И-НЕ, четыре элемента НЕ, два элемента ИЛИ и

30 элемент И, выход которого подключен к первым входам первого, второго и третьего элементов И-НЕ и счетному входу первого реверсивного счетчика, вход сложения которого подключен к выходу первого одновибратора, вход запуска которого объединен с вторыми входами первого, второго и третьего элементов И-НЕ и подключен к выходу обнуления второго реверсивного счетчика, вход вычитания которого объединен с входом сложения третьего реверсивного счетчика и подключен к выходу второго одновибратора, вход запуска которого объединен с третьими входами первого и второго элементов И-НЕ и подключен к выходу обнуления четвертого ре.версивного счетчика, вход вычитания которого подключен к выходу обнуления пятого реверсивного счетчика, вход вычитания которого подключен к выходу третьего одновибратора, вход запуска которого объединен с четвертым входом первого элемента И-НЕ и подключен к выходу обну- 55 ления шестого реверсивного счетчика, вход вычитания которого подключен к выходу-обнуления седьмого реверсивного счетчика, счетный вход которого объединен со счетным входом шестого реверсивного счетчика и подключен к выходу первого элемента НЕ, вход которого подключен к выходу первого элемента И-НЕ, выход второго элемента И-НЕ подключен к входу второго элемента НЕ, выход которого подключен к счетным входам четвертого и пятого реверсивных счетчиков, выход третьего элемента И-НЕ подключен к входу обнуления третьего реверсивного счетчика и входу третьего элемента НЕ, выход которого подключен к счетному входу второго счетчика, информационный выход которого объединен с первым входом узла элементов ИСКЛЮЧАЛЦЕЕ

ИЛИ и подключен к информационному выходу первого реверсивного счетчика, первый, второй и третий выходы узла элементов ИСКЛЮЧАЮЩЕЕ ИЛИ подключены соответственно к первому входу первого элемента ИЛИ, первому и второму входам второго элемента ИЛИ, выход которого подключен к второму входу первого элемента

ИЛИ, выход которого подключен к первому входу элемента И, информационный выход (кроме первого разряда) пятого реверсивного счетчика объединен с информационным выходом четвертого реверсивного счетчика и подключен к входу узла элементов

НЕ,выход которого подключен к первому входу четвертого элемента -HE, выход которого подключен к входу четвертого элемента НЕ, а выход первого разряда пятого реверсивного счетчика подключен к второму входу четвертого элемента И вЂ” НЕ, при— чем второй вход элемента И является входом запуска устройства, входом задания частоты среза устройства является второй вход узла элементов ИСКЛЮЧАКЦЕЕ ИЛИ, вход вычитания седьмого реверсивного счетчика объединен со счетными. входами блока счетчиков и управляемого делителя частоты и является тактовым входом устройства, второй выход первого дешифратора подключен к информационным входам шестого и седьмого реверсивных счетчиков,первый и второй выходы третьего дешифратора подключены соответственно к входу обнуления блока счетчика и третьему входу четвертого элем н! 2)8395!

x(u)

Х(1) Х(12) Х(2) Х(1д)

Х(д) X(T4)

Х(1) Х(И) Х (15) та И-НЕ, а третий выход третьего дешифратора подключен к информацион ным входам четвертого и пятого реверсивных счетчиков, выход третьего одновибратора подключен к входу обнуления управляемого делителя частоты и входу разрешения записи блоx(u)

Х(8)

Х(Ф) Х(У)

Х(5)

x(a) Х(3)

Х(11)

Х(7) ка счетчиков, информационные выходы первого, второго и третьего реверсивных счетчиков подключены к входам соответственно второго, третьего и первого дешифраторов, а выход четвертого элемента И-НЕ подключен к четвертому входу блока элементов И.

x(l)

Х/З)

Х(Ц

Х(5)

x(n)

Х(7) к(Ю

Х(У)

Х(О)

Х(11) Х(12)

Х(18) х(и4!

2) 8395

Рис.2

l 218395! 2 l 8. 39 фее. У

I 2 IH39.) фиГ 7

Фиа. Ю

ВНИИПИ Заказ 1133/57 Тираж 673 Подписное

Филиал ППП "Патент", г.Ужгород,ул.Проектная,4