Устройство для реализации быстрого преобразования фурье Советский патент 1986 года по МПК G06F17/14 

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

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

На фиг.1 представлен алгоритм БПФ; н,а фиг. 2 - функциональная схема устройства; на фиг.З - блок элементов И; на фиг.4 - блок счетчиков; на фиг.З - блок элементов ШШ; на фиг.6 - управляемый делитель частоты; на фиг.7 - блок управления; на фиг.8 - второй дешифратор; на фиг.9 - первый дешифратор на фиг.10 - третий дешифратор.

Устройство для реализации БПФ содержит блок памяти 1, арифметическ блок 2, блок постоянной памяти 3, блок элементов И 4, блок счетчиков 5 блок элементов ИЛИ 6, управляемый делитель частоты 7, блок управления 8, второй дешифратор 9, первый дешифратор 10, третий дешифратор II. Вход 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, элементы

183952

И-11К 39 и 40, элементы И 41 и мУ. триггеры 43. Входы 44-46 явлпю 1 - ся входами блока 7, а выход 47 - выходом блока 7.

с Блок 8 управления содержит счетчики 48-52, элементы И-НЕ 53-55, элементы НЕ 56-58, одновибраторы 59-61, элемент И 62, узел элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 63, элементы

IQ ИЛИ 64, элемент И-НЕ 65, узел элементов НЕ 66, элемент НЕ 67. Входы 68-73 являются входами блока 8, а выходы 74-78 - выходами блока 8. Дешифратор 9 содержит дешифратор

15 79 со входом 80 и выходом 81.

Дешифратор 10 содержит дешифратор 82 и элементы НЕ 83. Вход 84 является входом дешифратора 10, а выходы 85-86 - выходами дешифрато20 Ра 10.

Третий дешифратор 1 содержит дешифратор 87, элементы НЕ 88, элемент И-НЕ 89, одновибратор 90. Вход 91 является входом третьего дешиф25 ратора 11, а выходы 92-94 - выходами третьего дешифратора 11.

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

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

35 х(8), Х(4),.Х(2), Х(2), Х(10), Х(6) Х(14), вычисляются только дополнительные базовые операции, которые возникают при переходе от четырехточечного БПФ к восьмиточечному, и

затем от всех шестнадцати точек Х(0) Х(8),Х(4),Х(12),Х(2),Х(10),Х(6), XU4), Х(1), Х(9), Х(5), Х(13), Х(3), Х(11), Х(7), Х{15), но опять- -- таки вычисляются только дополнитель ные базовые операции, необходимые для шестнадцатиточечного БПФ без повторения ранее вычисленных базовых операций от восьмиточечного БПФ. Базовые операции, которые вычис50 ляются при переходе к следующему числу точек БПФ и названные как дополнительные, расположены в алгоритме БПФ (фиг.1) виде угла. На фиг.1 базовые операции, входящие в соот55 ветствующий угол, имеют одинаковое число окружностей. Число окружностей в базовой операции определяет номер угла алгоритма БПФ. Вы3

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

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

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

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

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

Если частота среза fcp в текущий промежуток времени в два раза мень- ше по сравнению с максимальной частотой среза f,

ср.моХс

вычисление БПФ

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

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

15

20

25

18395 .

в начальных N/4 узлах алгоритма

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

Так продолжается и далее, например, если частота среза в восемь раз меньше максиь1альной частоты среза fcp. вычисление БПФ заканчивается от N/8 точек на {п-3)-й итерации, спектральные составляющие находятся в начальных N/8 узлах ал- ,Q горитма или ячейках памяти устройства БПФ.

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

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

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

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

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

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

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

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

Блок 8 управления выполняет

55 вьщачу последовательности управляющих сигналов на соответствующие блоки в процессе вычисления БПФ.

30

Дешифратор 9 по номеру угла

определяет число итераций и началь- 1ШЙ адрес угла.

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

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

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

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

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

После окончания вычисления посленей базовой операции на третьем угле с выхода блокав управления поступает сигнал, который в блоке 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. I

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

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

г/

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

Для сигналачастоты среза,определяемого неравенством .МОКС

ц

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

Аналогично, .пс.,

8 , Ч . сигнал частоты среза равен пяти,

ср.макс ср.макс СИГНаЛ ЧаСТОТ

168

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

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

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

o

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

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

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

Результат вычисления БПФ для соответствующего значения сигнала частоты среза находится в ячейках блока 1 памяти, начиная с нулевой и кончая ячейкой с номером W . Величина нл определяется в зависимости от значения сигнала частоты среза, для f ср.маке fcp ftp.MQKC I N-tj : 2

0

0

5

.ср.макс , с ср. макс I -v-Z.

fср мдкс ftp

8. .Л

N

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

5

0

Устройство для реализации быстрого преобразования Фурье, содержащее блок памяти, первый выход которого подключен к входу операндов арифметического блока, выход результата которого подключен к информационному входу блока памяти, выход блока постоянной памяти подключен к входу коэффициентов арифметического блока, а информационный вход блока памяти является информационным входом устройства, блок управления и три дешифратора, отличающееся тем, что, с целью повышения быстродействия при обработке сигналов с переменной частотой среза, в него введены блок элементов ИЛИ, блок элементов И, блок счетчиков и управляемый делитель частоты, вход задания коэффициента деления которого объединен с первым входами блока элементов И и блока элементов ИЛИ и подключен к первому выходу первого дешифратора, выход второго дешифратора подключен к второму ходу блока элементов И, выход которого подключен к информационному входу блока счетчиков, информационный выход которого подключен к третьему входу блока элементо И и второму входу блока элементов ИЖ, выход которого подключен к адрсному входу блока памяти, второй выход которого подключен к третьему входу блока элементов ИЛИ, выход управляемого делителя частоты подключен к адресному входу блока постоянной памяти, при этом блок управления содержит семь реверсивных счетчиков, три одновибратора, узел элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, узел элементов НЕ, четыре элемента И-НЕ, четыре элемента НЕ, два элемента ИЛИ и элемент И, выход которого подключен к первым входам первого, второго и третьего элементов И-НЕ и счетному входу первого реверсивного счетчика, вход сложения которого подключен к выходу первого одновибратора, вход запуска которого объединен с вторыми входами первого, второго и третьего элементов И-НЕ и подключен к выходу обнуления второго реверсивного счетчика, вход вычитания которого объединен с входом сложени третьего реверсивного счетчика и подключен к выходу второго одновибратора, вход запуска которого объединен с третьими входами первого и второго элементов И-НЕ и подключён к выходу обнуления четвертого реверсивного счетчика, вход вычитания которого подключен к выходу обнуления пятого реверсивного счетчика, вход вычитания которого подключен к выходу третьего одновибратра, вход запуска которого объединен с четвертым входом nejpBoro элем та И-НЕ и подключен к выходу обнуления шестого реверсивного счетчика вход вычитания которого подключен к выходу-обнуления седьмого ревер0

5

0

5

0

5

0

5

0

5

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

1218395

ff

.2

4 0

47

JL