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

Изобретение относится к вычислительной технике, может найти применение в спецпроцессорах быстрого преобразования Фурье (БПФ) и предназначено для формирования последовательности адресов тригонометрических коэффициентов W/, выбираемых согласно алгоритма БПФ из блока постоянной памяти (ПЗУ), при переменном количестве точек N этого алгоритма. Известно устройство, выполняющее аналогичные операции, которое содержит счетчик адреса, регистр итераций два матричных переключателя, группу элементов ШШ, сумматор, регистр адреса, переключатель СС -Недостатком этого устройства явля ется наличие переключателей, суммато ра, регистра адреса усложняющих схе му и приводящих к излишним аппаратным затратам. Наиболее близким техническим решением к изобретению является адресное формирукмдее устройство для выпол нения быстрого преобразования Фурье, содержащее счетчик адреса, регистр итераций, блок постояниой памяти, Р-1 элементов И (Р-1) - числов разря дов счетчика адреса и регистра итера ций, число точек БПФ), Причем первый и второй входы I-ro элемента И (, ...., Р-1) подклйчены соответственно к выходу i-ro разр да счетчика адреса и выходу.(Р-1)-го разряда регистра итераций, выходы элементов И подключены к адресным вх дам блока постоянной памяти, а выход переноса счетчика адреса подключен к входу регистра итераций t27. Даннь1й формирователь прост, имеет малый объем оборудования, но рассчитан на фиксированное количество точек N. I Цель изобретения - расширение области применения за счет формирования коэффициентов для преобразований различного размера. Поставленная цель достигается тем что в формирователь коэффициентов быстрого преобразования Фурье, содержащий счетчик адреса, счетный вход которого является тактовым рводом формирователя, счетчик итераций, т-1 элементов и (m гДб максимальный размер преобразования) и блок постоянной памяти, информационный выход которого является информа ционным выходом формирователя, причем 552, выход i-ro (, N) разряда счетчика адреса подключен к первому входу i-ro элемента И, введены первый и второй мультиплексоры, первый и второй элементы задержки, выходы которых подключены к входам обнуления соответственно счетчиков итераций и адреса, выходы J-X (,т) разрядов которых подключены к J-M информационным входам соответственно первого и второго мультиплексоров, информационные выходы которых подключены к входам соответственно первого и второго элементов задержки, информационньй выход вторбго мультиплексора является выходом окончания вычислений формирователя, а вход (m-i)-ro разряда адреса блока постоянной памяти подключен к выходу 1-го элемента И, второй выход которого подключен к выходу 1-го разряда счетчика итераций, счетньй вход последнего подключен к информационному выходу второго мультиплексора, управляющий вход которого соединен с управляющим входом первого мультиплексора и является входом задания размера преобразования формирователя. Нафиг. 1 изображена структурная схема предлагаемого устройства;,на фиг 2 - граф алгоритма БПФ; на фиг. 3 - граф базовой операции БПФ; на фиг. 4 - пример организации блока постоянной памяти коэффициентов. . Устройство содержит (двоичный) счетчик 1 адреса, .счетчик 2 итераций, элементов ИЗ, блок 4 постоянной памяти, мультиплексоры 5 и 6, элементы 7 и 8 задержки, вход 9 задания размера преобразования, тактовый вход 10, информационный выход 11 (коэффициентов W) и выход 12 окончания вычислений. В бло.ке 4 постоянной памяти последовательно прошиты значения тригонометрических коэффициентов (2я/Ытп)+ sfn(2l/Nmfi) J где ,1,.../М /2-1/; N - максимальное количество точек БПФ; ,14; .J Я На фиг. 2 показан граф алгоритма БПФ для массива точек N , . Здесь входной массив чисел обозначен fg, ...,, выходной - FO , ..-., р7 и представлен в двоично-инверсном 3 порядке. Коэффициенты W БПФ обозначе ны как W.,. . ., W . Данное устройство позволяет формировать данные коэффициенты согласно графу алгоритма (фиг, 2). На фиг. 3 приведен граф базовой операции БПФ для данного алгоритма, где А и В - входные комплексные чис ла;. X и У - выходные комплексные числа; W - коэффициенты БПФ. Приме р. Организация блока 4 коэффициентов W(фиг, 4), Данные блок рассчитан на и обеспечивает формирование коэффициентов также для , N 8 и , При программировании блока 4 значения п выбираются в пределах О - 15. Рассматривают работу устройства на примере формирования коэффициентов W для восьмиточечного БПФ. В исходном состоянии счетчик 1 адреса и счетчик 2 итераций обнулены. На вход 9 поступает код двоики - 10, соответствующий выбранному значению Р-1, При этом на выходы мультиплексоров 5 поступают логические уровни с третьих разрядов счетчика адреса 1 и регистра 2 итера ций. Все.элементы И 3 закрыты. На их выходе устанавливается адрес 0,4. 00, который соответствует выбору из блока 4 постоянной памяти весового коэффициента W, По мере выполнения первой итерации с приходом тактовых импульсов состояние счетчика 1, принимает значения О ,,, 00, О ,,, 01, О ,,,11, а состояние счетчика 2 итераций остается неизменным О ,,, 00, Поэтому элементы И остаются закрытыми, и на их выходе в течение первой итерации стоит адрес О ,,, 00, соответствующий коэффициентам W, На первом такте второй итерации счетчик 1 адреса устанавливается в состояние О ,,,100, Уровень 1 с третьего разряда счетчика 1 поступает на третий вход мультиплексора 5 далее на вход счетчика 2 и устанавливает его в положение О ,,, 01, Тот же сигнал с выхода мультиплексора 5 через элемент 7 задержки поступает на установочный вход счетчика 1 адре са и сбрасывает его в О ,., 00, При этом 1 в первом разряде счетчи 1ка 2 итераций разрешает прохождение 554 информации с выхода первого разряда счетчика 1 через первый элемент И 3 на ()-й разряд адресного входа блока постоянной памяти. На второй итерации под действием тактовых импульсов (ТИ) счетчик 1 устанавливается последовательно в положения 0..00, О.,,01, О,,.10, 0...11, а . счетчик 2 остается в положении О,,,01, При этом на адресных входах блока 4 устанавливаются комбинации 00,,.О, 10,..О, 00,..О, 10...0. что соответствует выбору коэффициентов W,, W°, W . j . На первом такте третьей итерации счетчик 1 адреса устанавливается в состояние О..,100. 1 с выхода третьего разряда счетчика 1 поступает .через мультиплексор 5 на вход счетчика 2 итераций и устанавлива.ет его в положение О,,,11, счетчик 1 сбрасывается в 0. .,00 сигналом, поступающим через элемент 7 задержки. При этом разрешается прохождение инфор- , мации с первого и второго разрядов счетчика 1 и через первый и второй элементы И 3 на ()-й и (Р„-2)-й адресные входы блока 4, I ; , , . На третьей итерации счетчик 1 проходит состояния 0...00, О,..01, О,..10 0...11, а счетчик 2 остается в положении 0... 11, При этом на: адресных входах блоа 4 последовательно устанавливаются комбинации 00.,,О, 10,.,0, 01.,,0, 11..,0, что соответствует выбору из блока постоянной памяти коэффициентов W,W, W,W. Далее очередной импульс, поступающий на вход 10, устанавливает счетчик 1 в состояние О,,,100, С выхода третьего разряда счетчика 1 через мультиплексор 5 поступает на вход счетчика 2 и устанавливает его в состояние О,..111. Этот же сигнал поступает на вход установки счетчика 1 и сбрасывает его в исходное состояние. 1 с выхода третьего разряда счетчика 2 итераций поступает на третий вход мультиплексора 6 и далее йа выход 12 окончания вычислений. Этот же сигнал через элемент 8 задержки поступает на установочный вход счетчика 2 итераций и сбрасывает его в исходное состояние 0...00. На этом работа устройства заканчивается.Весь процесс генерации коэффициентов прИМ 8 осуществляется da три итерации. Выполнение каждой итерации происходит за четыре такта.

Аналогично устройство работает и при другом значении кода Р-1, т.е. при другом значении количества точек БПФ. при этом на выходы мультиплексоров 5 и 6 поступают сигналы с соответст:вующих (Р-1)-х выходов счетчика 1 адреса и счетчика 2 итераций, что обеспечивает счет количества тактовых импульсов счетчиком

на каждой итерации до ь1/2 и заполнение счетчика 2 единицами на последней итерации доМ-1.

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

ФОРМИРОВАТЕЛЬ КОЭФФЩИЕНТОВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий счетчик адреса, счетный ввод которого является тактовым вводом формирователя, счетчик итераций, т-1 элементов И (m fo%-jN, где N - максимальный размер преобразования) и блок постоянной памяти, информационный выход которого является информационным выходом.формирователя, причем выход i-ro (,N) разряда счетчика адреса подключен к первому входу i-ro элемента И, отличающийся тем, что, с целью расширения области применения за счет формирования коэффициентов для преобразований различного размера, в него введены первый и второй мультиплексоры, первый и второй элементы задержки, выходы которых подключены к входам обнуления соответственно счетчиков итераций и адреса, выходы j-x (,m) разрядов которых подключены к у-м информационным входам соответственно первого и второго мультиплексоров, информационные выходы которых подключены к входам соответственно первого и второго элементов задержки, информациоиньгй выход второго мультиплексора является выходомокончания вычислений формирователя, а вход (т- i)ro разряда адреса блока постоянной памяти подW ключен к выходу i-ro элемента И, второй вход которого подключен к выходу 1-го разряда счетчика итераций, счетный вход последнего подключен к инфор мационному выходу второго мультиплексора, управляющий вход которого соединен с управлякяцим входом первого о мультиплексора и является входом задания размера преобразования формировасо теля. СП ел

Нонец вычислении

фиг.1

f/

Фиг. 3

Y