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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

4 (s l ) G 06 F 15/332

ОПИСАНИЕ ИЭОБРЕТЕНИ

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

llO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (?1) 3670982/24-24 (22) 08. 12. 83 (46) 15.06.85. Бюл. У 22 (72) С.Б.Цакоев, Б.В.Зайцев, В.В.Чернов и А.В.Рытов (53) 681.32(088.8)

{56) 1. Патент Японии Р 56-26068, кл, G 06 F 15/332, 1981.

2. Авторское свидетельство СССР .Р 723582, кл. С 06 F 15/332, 1980 (прототип). (54) (57) ФОРГ1ИРОВАТЕЛЬ КОЭФФИЦИЕНТОВ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий счетчик адреса, счетный ввод которого является тактовым вводом формирователя, сче тчик итераций, m-1 элементов И (rn= Ь N, где М вЂ” максимальный размер преобразования) и блок постоянной памяти, информационный выход которого является информационным выходом формирователя, причем выход

i-ro (i=1,М) разряда счетчика адреса подключен к первому входу i-го элемента И, отличающийся тем, что, с целью расширения области применения за счет формирования коэф4

„„Я0„„1161955 фициентов для преобразований различного размера, в него введены первый и второй мультиплексоры, первый и второй элементы задержки, выходы которых подключены к входам обнуления соответственно счетчиков итераций и адреса, выходы j-x (j =1,m) разрядов которых подключены к 1 -м информационным входам соответственно первого и второго мультиплексоров, информационные выходы которых подключены к входам соответственно первого и второго элементов задержки, информационный выход второго мультиплексора является выходом окончания вычислений формирователя, а вход (m- i)-ro разряда адреса блока постоянной памяти подключен к выходу i — го элемента И, второй вход которого подключен к выходу

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

1161955

Изобретение относится к вычислительной технике, может найти применение в спецпроцессорах быстрого преобразования Фурье (БПФ) и предназначено для формирования последовательности адресов тригонометрических коэффициентов W выбираемых согласно алгоритма БПФ из блока постоянной памяти (ПЗУ). при переменном количестве точек N этого алгоритма. 10

Известно устройство, выполняющее аналогичные операции, которое содержит счетчик адреса, регистр итераций, два матричных переключателя, группу элементов ИЛИ, сумматор, регистр адреса, переключатель 1. .

Недостатком этого устройства является начичие переключателей, сумматора, регистра адреса, усложняющих схему и приводящих к излишним аппарат- 20 ным затратам.

Наиболее близким техническим решением к изобретению является адресное формирующее устройство для выполнения быстрого преобразования Фурье, 25 содержащее счетчик адреса, регистр итераций, блок постоянной памяти, Р-1 элементов И (Р-1) — числов разрядов счетчика адреса и регистра итераций, Р=1о М, N — число точек БПФ), причем первый и второй входы j-го элемента И (i=1, ..., Р-1) подключены соответственно к выходу l-ro разряда счетчика адреса и выходу (Р-1)-ro разряда регистр итераций, выходы 35 элементов И подключены к адресным входам блока постоянной памяти, а выход переноса счетчика адреса подключен к входу регистра итераций f23.

Данный формирователь прост, имеет 40 малый объем оборудования, но рассчитан на фиксированное количество точек 8.

Цель изобретения — расширение области применения за счет формирова-4 ния коэффициентов для преобразований различного размера.

Поставленная цель достигается тем, что в формирователь коэффициентов быстрого преобразования Фурье, содер-50 жащий счетчик адреса, счетный вход которого является тактовым вводом формирователя, счетчик итераций, щ-1 элементов и (в= о 5r, где М— максимальный размер преобразования) H и блок постоянной памяти, информационный выход которого является информационным выходом формирователя, причем выход -го (1=1, N ) разряда счетчика адреса подключен к первому входу i --ro элемента И, введены первый и второй мультиплексоры, первый и второй элементы задержки, выходы которых подклюг чены к входам обнуления соответственно счетчиков итераций и адреса, выходы 1-х (=1,v) разрядов которых подключеныы к 1-м информационным входам соответственно первого и второго мультиплексоров, информационные выходы которых подключены к входам соответст— венно первого и второго. элементов задержки, информационный выход второго мультиплексора является выходом окончания вычислений формирователя, а вход (т- 1)-го разряда адреса блока постоянной памяти подключен к выходу 1-ro элемента И, второй выход которого подключен к выходу 1-ro разряда счетчика итераций, счетный вход последнего подключен к информационному выходу второго мультиплексора, управляющий вход которого соединен с управляющим входом первого мультиплексора и является входом задания размера преобразования формирователя.

На фиг. 1 изображена структурная схема предлагаемого устройства;,на фиг. 2 — граф алгоритма БПФ; на фиг. 3 — граф базовой операции БПФ; на фиг. 4 — пример организации блока постоянной памяти коэффициентов.

Устройство содержит (двоичный) счетчик 1 адреса, .счетчик 2 итераций, m- =Po@ N элементов И 3, блок 4 постоянной памяти, мультиплексоры 5 и 6, элементы 7 и 8 задержки, вход 9 задания размера преобразования, тактовый вход 10, информационный выход 11 (коэффициентов Nf) и выход 12 окончания вычислений. В блоке 4 постоянной памяти последовательно прошиты значения тригонометрических коэффициентов и

Ж =сиз(,2У/йып)+j s(n(2T(/Яп п )

1 где и =0,1,.../И„,/2-1/;

8 — максимальное количество точек

БПФ; м =3,14;

1 = 1f-1

На фиг. 2 показан граф алгоритма

БПФ для массива точек И =2 =8, Р=З.

Здесь входной массив чисел обозначен

1 е е ° ВЫХОДНОЙ FO и представлен в двоично-инверсном

3 1161955 4 порядке. Коэффициенты Ч/ БПФ обозначе- информации с выхода ны как Ф,..., Фз . Данное устройство(. счетчика 1 через пе позволяет формировать данные коэффи- на (Р -1)-й разряд циенты согласно графу алгоритма блока постоянной и (фиг. 2). итерации под действ

На фиг. 3 приведен граф базовой пульсов (ТИ) счетч операции БПФ для данного алгоритма, . ется последовательн где А и  — входные комплексные чис- О. ..00, 0...01, О... ла; счетчик 2 остается

Х и У вЂ” выходные комплексные 10 При этом на адресны числа; устанавливаются ком

W — коэффициенты БПФ. 10...0, 00...0, 10..

Пример. Организация блока 4 ствует выбору коэфф коэффициентов 5/ (< )HI i 4) ° щ0

Данные блок рассчитан на N =32 и

На первом такте обеспечивает формирование коэффициентов также для И =4, М =8 и N=16. счетчик 1 адреса ус в состояние 0...100.

При программировании блока 4 значетретьего разряда сч ния и выбираются в пределах О - 15. через мультиплексор

Рассматривают работу устройства 2б ка 2 итераций и уст на примере формирования коэффициентов 9I для восьмиточечного БПФ. в положение О... 11, В исходном состоянии счетчик 1 адреса и счетчик 2 итераций обнулены. На вход 9 поступает код двойки — 10, соответствующий выбранному значению P-1. При этом на выходы мультиплексоров 5 и:6 поступают логические уровни с третьих разрядов счетчика адреса 1 и регистра 2 итера-З0 ций. Все.элементы И 3 закрыты. На их выходе устанавливается адрес О.;. .00, который соответствует выбору из блока 4 постоянной памяти весово-. о го коэффициента % . 35

По мере выполнения первой итера-. ции с приходом тактовых импульсов состояние счетчика 1 принимает значения О ... 00, О ... 01, 0- ... 11,:. а состояние счетчика 2 итераций 4О остается неизменным О ... 00. Поэтому все элементы И остаются закрытыми, и на их выходе в течение первой итерации стоит адрес О ;.. 00, соответствующий коэффициентам Ж . .45

На первом такте второй итерации счетчик 1 адреса устанавливается в состояние О ... 100. Уровень "1" с третьего разряда счетчика 1 посту- . пает на третий вход мультиплексора 5,50 далее на вход счетчика 2 и устанавливает его в положение О . ° . 01. Тот. же сигнал с выхода мультиплексора 5 через элемент 7 задержки поступает на установочный вход счетчика 1 адре-55 са и сбрасывает его в О ... 00.

При этом "1" в первом разряде счетчика 2 итераций разрешает прохождение первого разряда рвый элемент И 3 адресного входа амяти. На второй ием тактовых им к 1 устанавпивао в положения

10, 0...11, а в положении 0...01. х входах блока 4 бинации 00...0, .О. что соответ HåHTðB 5(o у третьей итерации танавливается

"1" с выхода етчика 1 поступает

5 на вход счетчианавливает его счетчик 1 сбрасывается.в 0...00 сигналом, поступающим через элемент 7 задержки. При этом разрешается прохождение информации с первого и второго разрядов счетчика 1 и через первый и второй элементы И 3 на (Рщ-1)-й и (Р -2)-Я адресные входы блока 4.

На третьей итерации счетчик проходит состояния 0...00, 0...01, 0...10 0...11, а счетчик 2 остается в положении О... 11. При этом на адресных входах блоа 4 последовательно устанавливаются комбинации 00...0, !

0...0, 01...0, 11...0, что соответствует выбору из блока постоянной памяти коэффициентов Фl, Щ2, Щ, 9(.

Далее очередной импульс, поступающий на вход 10, устанавливает счетчик 1 в состояние О... 100. С выхода третьего разряда счетчика "1" через мультиплексор 5 поступает на вход счетчика 2 и устанавливает его в состояние 0...111. Этот же сигнал поступает на вход установки счетчика 1 и сбрасывает его в исходное состояние.

"1" с выхода третьего разряда счетчика 2 итераций поступает на третий вход мультиплексора 6 и далее на выход 12 окончания вычислений. Этот же сигнал через элемент 8 задержки поступает на установочный вход счетчика 2 итераций и сбрасывает его в исходное состояние 0...00. На этом работа устройства заканчивается. Весь процесс генерации коэффициентов при N=S осуществляется 5а три итерации. Выполнение каждой итерации про. исходит за четыре такта.

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

1161955 на каждой итерации до hl/2 и заполнение счетчика 2 единицами на последней P-й итерации до И вЂ” 1.

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

1 точек.

1 61955

fo Ф б 5

Фи8. 2

Составитель А. Баранов

Редактор Е. топча Техред Н. Кастелевич Корректор А. Тяско

Заказ 3970/51 Тираж 710 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r.Ужгород, ул.Проектная, 4