Каскадное устройство для быстрого преобразования фурье
Изобретение относится к области вычислительной техники и может быть использовано для построения цифровых фильтров и анализаторов спектра, работающих в реальном времени. Цель изобретения - упрощение устройства. Устройство содержит ц Titfraeflofйт льно соединенных каскадов, каждый из которых содержит арифметический блок 1 , коммутатор 2, два элемента задержки 3, синхронизатор 4, формирователь 5 тригонометрических коэффициентов, коммутатор 6 и регистр 7. За счет реализации в устройстве формирования из выходной последовательности на коммутаторе 6 двух последовательностей отсчетов сигнала - ;етной и нечетной , выравнивания в регистре 7 временного положения четной и нечетной последовательностей сигналов и изменения порядка обработки операнс дов на первой и последующих операци (Л ях быстрого преобразования Фурье дос .тигается сокращение оборудования устройства . 5 ил.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСИИХ
РЕСПУБЛИК (50 4 С 06 F 15/331
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
1- б/Ы /й7СИОО
2-ри наскад и-ю мают
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITHA (21) 3603700/24-24 (22) 09.06.83 (46) 23.10.86. Бюл. В 39 (72) О.В. Григорьев, Б.Я. Фриде, В.А. Кравец, М.И. Дергачев и А.Я. Шпильберг (53) 681.32 (088.8) (56) Патент США Ф 3816729, кл. G 06 F 15/332, опублик. 1974.
Патент США 11 3892956, кл. G 06 F 15/332, опублик. 1975. (54) КАСКАДНОЕ УСТРОЙСТВО ДЛЯ БЬ1СТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники и может быть использовано для построения цифровых фильтров и анализаторов спектра, работающих в реальном времени. Цель изобретения — упрощение устройства.
„„SU„„265794 А 1
t 1
Устройство содержит -пбследовательно соединенных каскадов, каждый из которых содержит арифметический блок 1, коммутатор 2, два элемента задержки
3, синхронизатор 4, формирователь 5 тригонометрических коэффициентов, коммутатор 6 и регистр 7. За счет реализации в устройстве формирования из выходной последовательности на коммутаторе 6 двух последовательностей отсчетов сигнала — .етной и нечетной, выравнивания в регистре 7 временного положения четной и нечетной последовательностей сигналов и изменения порядка обработки операндов на первой и последующих операци. ях быстрого преобразования Фурье дос.тигается сокращение оборудования устройства. 5 ил.
1 265794
Изобретение относится к вычислительной технике и может быть использовано для построения цифровых фильтров и анализаторов спектра, работающих в реальном времени. 5
Целью изобретения является упрощение устройства.
На фиг. 1 представлена функциональная схема устройства; на. фиг.2 функциональная схема арифметического блока; на фиг. 3 — функциональная схема коммутатора, выполняющего стандартную для каскадного БПФ операцию "прямо — накрест"; на фиг.4 — функциойальная схема дополнительного коммутатора, разделяющего входную последовательность сигналов на две— четную и нечетную; на фиг.5 — функциональная схема синхронизатора.
Каскадное устройство БПФ (фиг.1) состоит из ll последовательно соединенных каскадов, каждый из которых содержит арифметический блок 1, коммутатор 2, два элемента 3 задержки, 25 синхронизатор 4, формирователь 5 тригонометрических коэффициентов, коммутатор 6 и регистр 7.
Арифметический блок 1 (фиг.2) содержит комплексный умножитель 8 и два комплексных сумматора 9.
Коммутатор 2 (фиг.3) выполняет стандартную для каскадного БПФ операцию прямо — накрест". Он содержит элемент НЕ 1О и логические элементы
2 И-ИЛИ 11. 35
Коммутатор 6 (фиг.4) обеспечивает разделение входной последовательности сигналов на две: четную и нечетную. Он содержит элемент НЕ 12 и два логических элемента 13.
Синхронизатор 4 (фиг.51 содержит генератор 14 тактовой последовательности импульсов, двоичный счетчик 15 и логические элементы 16 и 17.
Устройство фиг.l) работает сле- 4 дующим образом.
Последовательность входных отсчетов сигнала, следующая с частотой
F=2/R, в первом каскаде устройства при помощи коммутатора 6 и регистра
7 разделяется на две последовательности с частотой следования Fl,==1/R, причем одна последовательность содержит только четные отсчеты входного . сигнала, а другая — только нечетные.
Далее из этих последовательностей в первом же каскаде при помощи элементов 3 и коммутатора 2 формируются
- ®Е2В матрица порядка N, которая состоит из 1!/2 двухточечных
ДПФ и описывает порядок выборки операндов;
tH единичная матрица порядка 2 матрица двухточечного ДПФ;
al rz1-1
1", E
И 11 х4""г
9 8 i â диагональная матрица, определяющая умножение вектора промежуточных данных на весовые коэффициенты;
n = 1ОИ211д
1лз-Bg )D l- О, 11)» -11 1гг (0)
W =ехр (-j —, .
2 !! огг — мономиальная матрица двоичноинверсной перестановки порядка N.
Модифицировайный алгоритм БПФ получается из традиционного на основе матрицы (Г g Pll ), которая задарт разделение компонент выборки входного сигнала Х на четные и нечетные компоненты каждой ее половины. (1 ф P } ° X=jX, Х,...,Х„
Х1, Хг,..., Хю,, Х 1112
»
-)7 г1 гг пары операндов, отстоящих во времени друг от друга на N/2 тактов. С выходов арифметического блока 1 первого каскада операнды поступают на вход следующего каскада, где снова выполняется их переупорядочение, затем — следующая базовая операция и т.д.
В связи с тем, что последовательность операндов, поступающих на арифметические блоки 1, изменена, процесс вычисления дискретного преобразования Фурье ДПФ) должен быть организован по модифицированной процедуре алгоритма быстрого преобразования
Фурье (БПФ).
Стандартная процедура БПФ в матричной форме имеет вид
С = -SN|ÏD„, W ) Х, и
1-1 т ода «= (Х»,Х»,Х,,X„J — входная выборка сигнала
С= (С„,С,,,Сг, Д- выходные коэффициенты Фурье;
65794
Формула изобретения
Каскадное устройство для быстрого преобразования Фурье, содержащее
log 11 арифметических блоков, log<й коммутаторов и 2.1о И элементов за держки, причем выход (2;-1)-ro
30 (i-l, log N) элемента задержки подключен к первому информационному входу i --ro коммутатора, первый и второй выходы которого подключены соответственно к входу 2 -ro элемента 35 задержки и входу первого операнда з 12 где P — матрица идеальной пересТа- нй новки порядка N/2.
Модифицированный алгоритм имеет вид
С= SÄ(r а Рц(,1((43 щ,фц (,I t"„„I)
На выходе процессора БПФ коэффициенты Фурье С будут появляться в порядке, определяемом матрицеи
ps„(r., в Р„Ä )).
Любой из номеров спектральных отсчетов может быть получен из соответствующего двоичного номера входного отсчета сигнала путем помещения старшего разряда номера входного от. счета на место второго разряда; сдвига влево на один разряд всех разрядов, начиная со второго; поразрядной инверсии полученного двоичного слова; считывания результата.
i --го арифметического блока, выходы
21 -х элементов задержки подключены
I к входам второго операнда i -ro арифметического блока, выходы первого и второго операнда j-ro (j=l, log N.-1) арифметического блока подключены соответственно к входу (21 +1) -ro элемента задержки и второму информационному входу (j +1)-ro коммутатора, а выходы первого и второго операндов log N -ro арифметического блока являются выходами соответственно первого и второго операндов устройства, синхронизатор, i --й выход ко15 торого подключен к управляющему входу 1-го коммутатора, à (log N+1)-At выход синхронизатора подключен к тактовому входу формирователя тригонометрических коэффициентов, выход (-го коэффициента которого подключен к входу задания коэффициента i -ro арифметического блока, о т л и ч аю щ е е с я тем, что, с целью упрощения устройства, оно содержит регистр и (log > N+1)-й коммутатор, первый и второй выходы которого подключены соответственно к входу первого элемента задержки и информационному вх".ду регистра, выход которого подключен к второму информационному входу первого коммутатора, (log
Фиг.2
1265794 ая а1
4дрес
ФигХ
Составитель А. Баранов
Техред А.Кравчук
Редактор А. Ворович
Корректор А. Обручар
Заказ 5667/48
Тираж 671
ВПИИПИ Государственного комитета СССР
Iio e M H3o6peTpHHH и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Подписное
Производственно-полиграфическое предлриятие, г. Ужгород, ул. Проектная, 4
