Устройство для формирования тригонометрических коэффициентов быстрого преобразования фурье
О П И С А Н И Е,00 7, ИЗОБРЕТЕНИЯ
Союз Советских
Социалистических
Республик ф, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (б3) Дополнительное к авт. саид-ву— (22) Заявлено 29.0781 (21) 3318689/18-24
« с присоединением заявки ¹(И) М. Кт.
6 06 F .15/33, Государственный комитет
СССР яо делам изобретений и открытий (23) Приоритет
Опубликовано 150383, Бюллетень ¹ 10
Дата опубликования описания1503ВЗ
153) УДК 681 ° 3 (088.8) (72) Автор изобретения (73) Заявитель
««Ъ««И «««ъ J
« (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ТРИГОНОМЕТРИЧЕСКИХ
КОЭФФИЦИЕНТОВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
Изобретение относится к автомати ке и вычислительной технике и предназначено для использования в составе специализированных процессоров быСтрого преобразования Фурье (БПФ) при цифровой обработке сигналов.
Известны генераторы значений тригонометрических функций, обеспечиваю щие получение коэффициентов за счет функциональных преобразований кода аргумента ) 1.).
Однако эти устройства имеют слож —ную конструкцию, низкое быстродействие, а также не обеспечивают формирование коэффициентов в последовательности, предусматриваемой алгоритмом
БПФ.
Наиболее близким к -изобретению является устройство для формирования тригонометрических :коэффициентов
БПФ, содержащее счетчик, блок постоянной памяти, блок управления, а также логический блок p2).
Счетчик в известном устройстве должен обеспечивать счет с переменным приращением, зависящим от номера выполняемого слоя БПФ. Следствием этого является сложная конструкция как самого счетчика, так и логического блока, управляющего приращением.
Цель изобретения — упрощение устройства.
Поставленная цель достигается тем, что в устройство для формирования тригонометрических.,коэффициентов быстрого-преобразования Фурье, содержащее счетчик, блок постоянной.памяти, выход которого является выходом дробной части тригонометрического коэффициента устройства, и блок уп равления, введены триггер,, сумматор, блок преобразования прямого кода в инверсный и элемент И, причем вход первого слагаемого сумматора является информационным входом устройства, выходы разрядов с первого по (n-2)-й сумматор (и — число слоев быстрого преобразования Фурье) подключены к входам занесения в одноименные разряды счетчика, выход (n-1)-го разряда сумматора подключен к входу занесения в п-ый разряд счетчика и к информационному входу триггера, вход занесения в (n- 1)-й разряд счетчика подключен к источнику единичного сигнала, выходи разрядов с первого по (n-2)-й счетчик
-подключены к входам одноименных разрядов второго слагаемого сумматора и через блок преобразования прямого
1005071 кода в инверсный к адресным входам блока постоянной памяти, инверсный выход (и-1)-ro разряда счетчика является выходом целой части тригонометрического коэффициента устройства„ выход n-ro разряда счетчика подключен к входу (и-1)-го разряда второго слагаемого сумматора, инверсный выход триггера подключен к первому входу элемента И, выход которого является знаковым выходок устройства, вход начальной установки устройства подключен к установочным входам счетчика и триггера, а также к первому входу блока управления, второй вход которого является 15 тактовым входом устройства, третий вход блока управления подключен к прямому выходу триггера, первый выход блч1ка управления подключен к управляющему входу занесения счетчика, к синхронизирующему входу триггера и к второму входу элемента И, второй выход блока управления подключен к входу переноса сумматора и к управляющему входу блока преобразования прямого кода в инверсный, третий и четвертый выходы блока управления подключены к суммирующему и вычитающему входам счетчика соответственно, кроме того, блок управления состоит из триггера, сумматора по модулю два, первого и второго элементов И, формирователя импульсов, причем устайовочный и счетный входы триггера в блоке управления являют 35 ся первым и вторым входами блока управления, прямой выход триггера в блоке управления является первым . выходом блока управления и подключен к первому входу сумматора по модулю два, второй вход которого является третьим входом блока управления, выход сумматора по модулю два является вторым выходом блока управления и подключен к первому инверсному входу первого элемента H и к пер- 45 вому входу второго элемента И, счетный вход триггера в блоке управления соединен с входом формирователя импульсов, выход которого подключен к вторым входам первого и второго эле- 5Q ментов И,инверсный выход триггера в блоке управления подключен к третьему входу второго элемента И, выходы первого и второго элементов Й являются третьим и четвертым выходами 55 блока управления.
На чертеже представлена функциональная схема устройства для формиро-. .вания тригонометрических коэффициентов быстрого преобразования Фурье. о
Устройство содержит и-разрядный счетчик 1, (и-1)-разрядный сумматор 2, триггер 3, элемент И 4, блок управления 5, блок б преобразования прямого кода в инверсный, блок 7 пос- gg тоянйой памяти, выход 8 целой части тригонометрического коэффициента, ийформационный вход 9, выход 10 дробной части тригонометрического коэффициента, знаковый выход 11, вход 12 начальной установки, тактовый вход 13. Блок 5 управления состоит из триггера 14, сумматора по модулю два 15, элементов И 16 и 17, формирователя импульсов 18.
В предлагаемом устройстве формирование тригонометрических коэффициентов осуществляется в следующей последовательности .
1. Производится первоначальная установка устройства: триггера 3 (RG=1), счетчика (СТ=О), триггера 14 (CS l).
2. Формируется очередной результат (действительная или мнимая часть очередного коэффициента): знак результата 286 CS; целая часть С=CT (и- 1); дробная часть считывается из ПЗУ по адресу
СТ если РК=1
PA=
СТ,если РК=О.
Далее по тактовому импульсу (ТИ) подготавливается формирование следующего результата:
3. С5 СЬ., 4. Если CS=i то:
C T(n-1) «=CT(n)
CTз =СТ+ 05.4.РК
RG:=CT(n-l)
CT(n)з=Ст(п-1)
СТ(п-1):=-1
5. СТ+1, если PK=0
СТ: С Т- l, если РК C S--1
СТ вЂ” в остальных случаях. б. Переход к пункту 2, где СТ вЂ” содержимое и-разрядного счетчика;
CT(i) — содержимое i-го разряда счетчика; ст =(ст »
mod -2" — содержимое и-2 младших разрядов счетчика;
СТ обратный код от CT
+ — операция сложения по модулю два;
CS - сигнал на первом выходе блока управления; единичное значение сигнала CS означает формирование дей-. ствительной части коэффициента
PK=RG+CS - сигнал на втОром выходе блока управления, означает прямой код адреса ПЗУ;
0S — код, соответствующий номеру выполняемого слоя БПФ.
На выходе устройства после его первоначальной установки по тактовым
1005071 импульсам формируются поочередно сначала действительная часть первого коэффициента, затем его мнимая часть. затем действительная часть второго коэффициента, .затем его мнимая часть и т.д, В счетчике 1 и сумматоре 2 выполняются п.п. 4 и 5 приведенного алгоритма, причем выполнение микроопераций CT(n- 1): =СТ(и); CT(n): CT(n-1) и CT(n-1): 1 обеспечивается соединением выхода п-го разряда счетчика 1 с входом (n-1)-ro разряда второго слагаемого сумматора 2, выхода (и- 1)-го разряда этого сумматора с входом и-го разряда этого счетчика и подачей на вход (и-1)-ro разряда счетчика 1 постоянного уровня логической единицы.,Ввиду того, что значение n-ro разряда суммы CT+0S+PIt. в алгоритме не используется, сумма- 30 тор выбран (n-1)-разрядным.
В ПЗУ 7 записаны 2" значений четверти периода синусоидальной
2и -1 Х функции от S I n0 до S I n (— 2)
Формирователь 18 формирует короткий импульс по заднему фронту каждого ТИ.
Устройство работает следующим образом. 30
Вначале на вход 12 устройства подается импульс первоначальной установки ПУ, по которому в.нулевое состояние устанавливается счетчик 1 и в единИчное .состояние триггеры
3 и 14.
На вход 9 устройства подается код, соответствующий номеру выполняемого
I слоя БПФ. В первом слое БПФ подается код 111. ° ..1, во втором 011....1, в третьем код 1011....1 и т.д.,Такой код может быть получен например с инверсных выходов итерационного сдвигового регистра процессора БПФ. На первом выходе блока управления 5 фор-45 мируется сигнал CS=,1, на втором сигнал РК=О, а на выходе устройства, в соответствии с п.2 алгоритма его функционирования, число +1,000, являющееся действительной частью первого 5О тригонометрического коэффициента.
При этом на выходе 8 устройства формируется целая часть числа С=СТ(и-1), на выходе 10 — его дробная часть,.а на выходе 11 - знак Z RG CS. 55
Для получения мнимой части первого коэффициента на вход 13 устройства подается первый тактовый импульс ТИ1.
По его переднему фронту в соЬтветствии с пунктом 3 алгоритма счетный 6О триггер 14 устанавливается в нулевое состояние, а на выходе элемента И 17 по заднему фронту ТИ1 вырабатывается сигнал вычитания единицы из содержимого счетчика 1, после чего содержи- 65 мое счетчика 1 становится равным
111.. ° .1.
На выхоце сумматора по модулю два 15 вырабатывается управляющий сигнал PK=.1, на выходе сумматора 2 формируется код, равный коду на входе 9 устройства, а на адресный вход
ПЗУ поступает адрес RA = 000...0 в соответствии с п.2 алгоритма функционирования устройства, На выход устройства поступает число +0,000, являющееся мнимой частью первого коэффициента.
Для получения действительной части второго коэффициента на вход
12 устройства подается второй тактовый импульс ТИ2, по которому счетный триггер переходит в единичное состояние. По переднему фронту сигнала CS=1 с.выхода этого триггера в (и-1)-й. разряд счетчика 1 зано сится число 1, а в остальные разряды — число с выхода сумматора 2. Код с выхода старшего разряда сумматора запишется также в триггер 3, причем за счет задержки в выходных цепях сумматора 2, а также и во входных цепях счетчика 1 и триггера 3. в триггер 3 и в счетчик 1 заносится код,существовавший на выходе сумматора перед подачей ТИ на вход 13 устройства.
В первом слое БПФ в счетчик занесется число 111....1, к которому затем по сигналу с третьего выхода блока управления 5 прибавляется единица, и содержимое счетчика становится равным 000...0. Во втором слое в счетчик 1 заносится число 011...1, а на третьем и четвертом выходах блока управления 5 сигналы не вырабатываются.
В триггер 3 во втором слое БПФ по ТИ2 занесется число О, а при вы-. полнении других слоев БПФ число 1.
На выходах 8, 10 и 11 устройства формируется действительная часть второго коэффициента: число +1,000 в первом слое БПФ, +0,000 во втором
+0,707 в третьем и т.д.
Далее устройство работает аналогичным образом. Сигналы на входах и выходах блоков устройства при поступлении первых четырех ТИ в разных слоях БПФ приведены в таблице. После выполнения каждого слоя BIIC в устройстве устанавливаются сигналы СТ=О, С5=1 и .36=1, поэтому подавать сигнал начальной установки в начале каждого слоя при выполнении БПФ нет необходимости.
Достоинства предлагаемого устройства выражаются в отсутствии сложного логического блока, управляющего приращением адресов ПЗУ, вырабатываемых счетчиком.
1005071
I и
I 3 63
1 Р\
О о о
М
Н1
О О о о
О О
М о
+ +.о о о о о о
Ь
Н1 Ю
+ + о о
Ю с
\ 4
+ о о о о о о
М о о
+. 1
О О о о о. о
М
4 4
+ + о
Ю
Ю
М н
+ о I о о о
Ъ о о
+ + о о о о ъ с
О О
I о,о
° ° о о о о о о о о о о о о о о о о о о о о о о о о о: о е а о о о о о о о о о о о о о, °
° ° ° о о о о о о о о о
D о
Ю о о о о о о о о о
О . Н4
1 fkf. и н
Ф н
Н4 Н н о
Н3 Н4 Н н! н н н! н н
\ 1 н н
Н3 Н Н
Н3 Н
° °
Н1 Н н
Н4 Н н н
Н4 н
Н3 н
Ю н н
Н3 Н н
Н4 Н о
Н Н4 Н
Ф ч н
Н 4 Н о о
4 4 О (Ч .1 Q
I в3 ц а 43 ос хн
Я ff3
333 Е
Н4 Н
Н4 Н н и о ю о
Ц 1 4 3
0S
1 3 ха
331 I» 3» о
°, ° о
Ю
Ю о о н н н н
Ю н н1 н н н
Ю ю н . о
Н3 Н4
Н4 Н! о о
4 О о о о о о
1 tA
I М
1 Х и
1 Э
1 Ц
I 333
ï3 а
3» > I hC
1 1 CL
3 .43 I ! х о
1 3 1
) н ) н3 н!
1 + + н н
l + I
1 о
I
О 4 О
O 4 О
o e e о о
1 х 1 < ъ . I Я 4Э
I 333
О» О о н о н» ,1
I ! ю
I.
1 1
1 Ф" хин
333 и
1
I Ю
1 Н (3 3 e C
Н 4Ч 4 CI
>, x х м ж.
Д Е» Е» Е-4 Е»
1 1 о х
1 Nt
1 413 N
1 ЙFI 3 И
I Э Э
1 н
Эн
Ф и в3
1 Х
К М о ! х
1 Ф
I
3 %
1 If» о
I 4
I U
I!
I 1
1 н4
1 I
1 с
Н4
I + 1
1, I
I
1
1 !
I
1 1 и н в н
1 1
О 4 О
° °
О 4 О о ч о
О 3 О
О 3 О н н н н
1 + 1 + ь о
Ю
О
I I в о в н
1 I о
° ° о о о о о о
° . ° о о о о о о о !
I I
Н4 в Н в Ю
I !
Н О 3 O Н
<ч м
>в М Х Х Ж
И Е» Е» Е» Е»
10050071
Ю
CO
4»Ъ с о
+ о ь о
% 4 о о ь о ъ-4 " 4 о о о о о о о о о о
%-4
% 4
Ф 4 о т 4 4
» 4
»-4
C)
» Ч 4 %-4
Ф
Ф4 Ч о о г4 т-4
° «4 %4
1 .
I .
l.i
1!
1
1. !.; !
»
1 l
I
1
I
I й
1 -(s
I!
I I ! Ф
1»»с4 и ф
I (И ! or, 1 ХР»
I 3
I II3 -.
I.C)
C) .о с 4
%4 -4 о 4
Г4 » 4 о
CI
%-4 4 »Ч . с.4
О а-4
О 4 о о о. о
»4 » 1
М 1
g и
Ф
Ц (((Ю» о» 1
И I
Ръ
c(I 1
М 1 о
Х I
3 1
Ф I
»»4.
I I
1 1
I 1
1 а 1
1 I ! Ф 1 о 1 ! Д 1
4 l (1
1
1 !
1
4С о
N Р»»((O! s( хон
Х ° (Я (5o
Ц ! ОД((Е(1(.(й
Е (а."О
Ж а Г ц I
X l i о
»4I PI о, *(=
Д (ОЭ
I III C(I .I
Ф
1 0» о н ! Ц»(I
1 1 (ШО
4")
1 М 1
I OrsI
I ХМР»
1 До»9 о о и
О О 4( о о в с с с о о
+ + + (» о (с с о
+ о о ь о
% 4 с-4
% ( о
D ч-4
1 + о
I г » м я » Е4
1005071
Формула изобретения
1. Устройство для формирования тригонометрических коэффициентов быстрого преобразования Фурье, со-,, держащее счетчик<, блок постоянной памяти, выход которого является выходом дробной части тригонометрического коэффициента устройства, и блок управления, о т л и ч а ю— щ е е с я тем, что, с целью упрощения устройства, оно содержит триггер, сумматор, блок преобразования прямого кода в инверсный и элемент И, причем вход первого слагаемого сумматора является информационным входом устройства, выходы разрядов с первого по (n-2)-й сумматора (n — число слоев быстрого преобразования Фурье) подключены к входам занесения в одноименные разряды счетчика, выход (n-1)-ro . 20 разряда сумматора подключен к входу занесения в и-й разряд счетчика и к информационному входу триггера, вход занесения в (и-1)-й разряд счетчика подключен к источнику еди- 25 ничного сигнала, выходы разрядов с первого по (n-2)-й счетчика подключены к входам одноименных разрядов второго слагаемого сумматора и через блок преобразования прямого кода в инверсный к адресным входам блока постоянной памяти, инверсный выход (и-1)-го разряда счетчика является выходом целой части тригонометрического коэффициента устройства, выход и-го разряда счетчика подключен к входу (n-1)-го разряда второго слагаемого сумматора, инверсный выход триггера подключен к первому входу элемента И, выход которого является знаковым выходом устройства, вход начальной установки устройства подключен к установочным входам счетчика и триггера, а также к первому входу блока управления, второй вход которого является тактовым входом устройства, третий вход блока управления подклю:ен к прямому выходу триггера, первый выход блока управления подключен к управляющему входу занесения счетчика, к синхронизирующему входу триг гера и к второму входу элемента И, второй выход блока управления подключен к входу переноса сумматора и к управляющему входу блока преобразования прямого кода в инверсный, ретий и четвертый выходы блока управления подключены к суммирующему и вычитающему входам счетчика сооттственно.
2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок управления состоит из триггера, сумматора по модулю два, первого и второго элементов И, формирователя импульсов, причем установочный и счетный входы триггера в блоке управления являются первым и вторым входами блока управ-... ления, прямой выход триггера в блоке управления является первым выходом блока управления и подключен к первому входу сумматора по модулю два, второй вход которого является третьим входом блока управления, выход сумматора по модулю два является вторым выходом блока управления и подключен к первому инверсному входу первого элемента. И и к первому входу второго элемента И, счетный.,вход триггера в блоке управления соединен с входом формирователя импульсов, выход которого подключен к вторым вход дам первого и второго элементов И, инверсный выход триггера в блоке управления подключен к третьему входу второго элемента И, выходы первого и второго элементов И являются третьим и четвертым выходами блока управления.
Источники информации, принятые во внимание при экспертизе
1. Аппаратурная реализация дискретного преобразования Фурье. М., "Энергия", 1978, с. 80-81, рис, 23-26
2. Клан, Шайвли и др. Специализированный процессор для быстрого решения задач гармонического анализа.—
Электроника, 19б8, том. 41, 9 13, с. 5-б,,фиг. 2.
1005071
Составитель В. Байков
Редактор К. Волощук Техред T.Õàòî÷êà Корректор Е. Рошко
Заказ 1901/65 Тираж 704 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4
