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

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

Иллюстрации

Показать все

Реферат

 

ФОРМИРОВАТЕЛЬ КОЭФФЩИЕНТОВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий счетчик адреса, счетный ввод которого является тактовым вводом формирователя, счетчик итераций, т-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