Формирователь коэффициентов быстрого преобразования фурье

(прототип),-2 Бюл. У 22ев, Б.В.Зайцев,А.В.Рытов 8.8) Япон332, е сви С 06 ии 9 561981,детельстР 15/332 068 СССР980 НТОВ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) (57) ФОРГ 1 ИРОВАТЕЛЬ КОЭФФИЦИЕБЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий счетчик адреса, счетный вводкоторого является тактовым вводомформирователя, счетчик итераций, е элементов И 0 п= 1 о М, где М - максимальный размер преобразования) и блокпостоянной памяти, информационный выход которого является информационнымвыходом Формирователя, причем выход1-го (1=1,М) разряда счетчика адресаподключен к первому входу 1-го элемента И, о т л и ч а ю щ и й с ятем, что, с целью расширения областиприменения за счет Формирования коэфЯО 1161955 фициентов для преобразований различного размера, в него введены первый и второй мультиплексоры, первый и второй элементы задержки, выходы которых подключены к входам обнуления соответственно счетчиков итераций и адреса, выходы 1-х (1=1 ув) разрядов которых подключены к 1-м информационным входам соответственно первого и второго мультиплексоров, информационные выходы которых подключены к входам соответственно первого и второго элементов задержки, информационный выход второго мультиплексора является выходомокончания вычислений формирователя, а вход (п)-го разряда адреса блока постоянной памяти подключен к выходу 1-го элемента И, второй вход которого оодкдюоев к выходу 1-го разряда счетчика итераций, счетный вход последнего подключен к инфор- - мационномувыходу второго мультиплексора, управляющий вход которого соединен с управляющим входом первого мультиплексора и является входом задания размера преобразования ФормироваМййй теля.СФСИзобретение относится к вычислительной технике, может найти применение в спецпроцессорах быстрого преобразования Фурье (БПФ) и предназначено для формирования последовательности адресов тригонометрических коэффициентов В, выбираемых согласно алгоритма БПФ из блока постоянной памяти (ПЗУ). при переменном количестве точек М этого алгоритма. 10Известно устройство, выполняющее аналогичные операции, которое содержит счетчик адреса, регистр итераций, два матричных переключателя, группу элементов ИЛИ, сумматор, регистр 15 адреса, переключатель 1Недостатком этого устройства является наличие переключателей, сумматора, регистра адреса, усложняющих схему и приводящих к излишним аппарат ным затратам.Наиболее близким техническим решением к изобретению является адресное формирующее устройство для выполнения быстрого преобразования Фурье, 25 содержащее счетчик адреса, регистр итераций, блок постоянной памяти, Рэлементов И (Р) - числов разрядов счетчика адреса и регистра итераций, Р=0 о М, й - число точек БПФ), 30 причем первый и второй входы 1-го элемента И (1=1, , Р) подкгдочены соответственно к выходу 1-го разряда счетчика адреса и выходу (Р)-го разряда регистра итераций, выходы элементов И подключены к адресным входам блока постоянной памяти, а выход переноса счетчика адреса подключен к входу регистра итераций 23.Данньй формирователь прост, имеет 40 малый объем оборудования, но рассчитан на фиксированное количество точек 8.1Цель изобретения - расширение области применения за счет формирования коэффициентов для преобразований различного размера.Поставленная цель достигается тем, что в формирователь коэффициентов быстрого преобразования Фурье, содержащий счетчик адреса, счетный вход которого является тактовым вводом формирователя, счетчик итераций, щэлементов и (в=о щ, где М, - максимальный размер преобразования) 55 и блок постоянной памяти, информационный выход которого является информационным выходом формирователя, причем выход 1-го (1=1, М ) разряда счетчика адреса подключен к первому входу 1-го элемента И, введены первый и второй мультиплексоры, первый и второй элементы задержки, выходы которых подклюгчены к входам обнуления соответственно счетчиков итераций и адреса, выходы 1-х (1=1,а) разрядов которых подключены к 1-м информационным входам соответственно первого и второго мультиплексоров, информационные выходы которых подключены к входам соответственно первого и второго. элементов задержки, информационный выход второго мультиплексора является выходом окончания вычислений формирователя, а вход (в)-го разряда адреса блока постоянной памяти подключен к выходу 1-го элемента И, второй выход которого подключен к выходу 1-го разряда счетчика итераций, счетный вход последнего подключен к информационному выходу второго мультиплексора, управляющий вход которого соединен с управляющим входом первого мультиплексора и является входом задания размера преобразования формирователя.Нафиг. 1 изображена структурная схема предлагаемого устройства;,на фиг. 2 - граф алгоритма БПФ; на фиг. 3 - граф базовой операции БПФ; на фиг. 4 - пример организации блока постоянной памяти коэффициентов.Устройство содержит (двоичный) счетчик 1 адреса, .счетчик 2 итераций, в= 1 о й элементов И 3, блок 4 постоянной памяти, мультиплексоры 5 и 6, элементы 7 и 8 задержки, вход 9 задания размера преобразования, тактовый вход 10, информационный выход 11 (коэффициентов В) и выход 12 окончания вычислений, В блоке 4 постоянной памяти последовательно прошиты значения тригонометрических коэффициентовлМ =еоз(,гТ/неп)+ заэ /йвп)1 где л =0,1,/И,/2-1/;Мю - максимальное количество точекБПФ;м =3,14;,=АНа фиг, 2 показан граф алгоритмаБПФ для массива точек И =2 =8, Р=З.Здесь входной массив чисел обозначенХ. Е , выходной в . Г , Еи представлен в двоично-инверсном3 1161 порядке. Коэффициенты В БПФ обозначены как М Ф . Данное устройство( . позволяет формировать данные коэффициенты согласно графу алгоритма (фиг. 2).5На фиг, 3 приведен граф базовой операции БПФ для данного алгоритма, где А и В - входные комплексные числа;.Х и У - выходные комплексные 10числа;Ч - коэффициенты БПФ.П р и м е р. Организация блока 4 коэффициентов Й (фиг е 4 )Данные блок рассчитан на 8=32 и . обеспечивает формирование коэффициентов также для И =4, М =8 и Я=16. При программировании блока 4 значения и выбираются в пределах 0 - 15.Рассматривают работу устройства 20 на примере формирования коэффициентов Ф для восьмиточечного БПФ. В исходном состоянии счетчик 1 адреса и счетчик 2 итераций обнулены. На вход 9 поступает код двойки - 10, соответствующий выбранному значению Р. При этом навыходы мультиплексоров 5 и 6 поступают логические уровни с третьих разрядов счетчика адреса 1 и регистра 2 итера-З 0 ций. Все.элементы И 3 закрыты. На их выходе устанавливается адрес О.;. .00, который соответствует выбору из блока 4 постоянной памяти весово-. го коэффициента % .35По мере выполнения первой итера-. ции с приходом тактовых импульсов состояние счетчика 1 принимает значения 000, 001, 011,: а состояние счетчика 2 итераций 4 О остается неизменным 000. Поэтому все, элементы И остаются закрытыми, и на их выходе в течение первой итерации стоит адрес 0 ; 00, соответствующий коэффициентам Ю .45На первом такте второй итерации счетчик 1 адреса устанавливается в состояние 0100. Уровень "1" с третьего разряда счетчика 1 посту- . пает на третий вход мультиплексора 5,50 далее на вход счетчика 2 и устанавливает его в положение 001. Тот же сигнал с выхода мультиплексора 5 через элемент 7 задержки поступает на установочный вход счетчика 1 адреса и сбрасывает его в 000. При этом "1" в первом разряде счетчика 2 итераций разрешает прохождение 955 4М информации с выхода первого разряда счетчика 1 через первый элемент И 3 на (Р -1)-й разряд адресного входа блока постоянной памяти. На второй итерации под действием тактовых импульсов (ТИ) счетчик 1 устанавливается последовательно в положения ОЛ .00, 001, 010, 011, а счетчик 2 остается в положении 001. При этом на адресных входах блока 4 устанавливаются комбинации 000, 100, 000, 100. что соответствует выбору коэффициентов Ю, Щ, д(0 д 21На первом такте третьей итерации счетчик 1 адреса устанавливается в состояние 0100. с выхода третьего разряда счетчика 1 поступает через мультиплексор 5 на вход счетчика 2 итераций и устанавливает его в положение 011, счетчик 1 сбрасывается.в 000 сигналом, поступающим через элемент 7 задержки. При этом разрешается прохождение информации с первогои второго разрядов счетчика 1 и через первый и второй элементы И 3 на (Р -1)-й и (Р)-Я адресные входы блока 4.На третьей итерации счетчик проходит состояния 000, 001, 010 011, а счетчик 2 остается в положении О 1. При этом на адресных входах блоа 4 последовательно устанавливаются комбинации 000, 00, 010, 110, что соответствует выбору из блока постоянной памяти коэффициентов Ч 4, Щ 2, Щ 1, ЖДалее очередной импульс, поступающий на вход 10, устанавливает счетчик 1 в состояние О 100. С выхода третьего разряда счетчика "1" через мультиплексор 5 поступает на вход счетчика 2 и устанавливает его в состояние 0111. Этот же сигнал поступает на вход установки счетчика 1 и сбрасывает его в исходное состояние. "1" с выхода третьего разряда счетчика 2 итераций поступает на третий вход мультиплексора 6 и далее на выход 12 окончания вычислений. Этот же сигнал через элемент 8 задержки поступает на установочный вход счетчика 2 итераций и сбрасывает его в исходное состояние 000. На этом работа устройства заканчивается. Весь процесс генерации коэффициентов при и=8 осуществляется ба три итера ции. Выполнение каждой итерации про исходит за четыре такта.Аналогично устройство работает и при другом значении кода Р, т.е при другом значении количества точек БПФ. при этом на выходы мультиплексоров 5 и б поступают сигналы с соответствующих (Р)-х выходов счетчика 1 адреса и счетчика 2 итераций, что обеспечивает счет количества тактовых импульсов счетчиком 1161955на каждой итерации до Ч/2 и заполнение счетчика 2 единицами на последней Р-й итерации до И - 1.Применение предлагаемого устройст 5 ва сокращает количество оборудованияпо сравнению с аналогом и расширяетобласть применения по сравнению с прототипом, т.е. формирует тригонометрические коэффициенты для алгоритмов БПФ с переменным количеством 1 точек.1161955 51 Тираж 710НИИПИ Государственногопо делам изобрете 397 За Подписное комитета СССР ий и открытий ая наб., д. 4/ 13035, Моск 35, Ра Филиал ППП "Патент", г. Ужго