Устройство для формирования адресов процессора быстрого преобразования фурье

 

Изобретение относится к вычислительной технике и может быть использовано в составе процессора БПФ. Цель изобретения заключается в расширении области применения за счет реализации формирования адресов в алгоритмах простых множителей, Винограда, полиномиальных преобразований. Для этого устройство содержит суммирующие счетчики 1, 2, группу из L суммирующих счетчиков 5, преобразователь 7 кодов, комбинационный сумматор 9 и регистр 10 адреса, дешифратор 3, группу мультиплексоров 4, группу блоков 6 умножения, мультиплексор 8 и группу регистров 11. 2 ил.

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

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

РЕСПУБЛИН щ) G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ASTOPCKOMY СВИДЕТЕЛЬСТВУ

Фиг. 1

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

ПО ИЗОБРЕТЕНИЯМ И О ЩРЫТИЯМ

ПРИ ГКНТ СССР (21) 4461565/24-24 (22) 15,07.88 (46) 07.11.90. Бюл. У 41 (71) Таганрогский радиотехнический институт им, В,Д,Калмыкова (72) К.Г.Иваненко и Л.В.Лысенко (53) 681.32 (088.8) (56) Авторское свидетельство СССР

Р 1298765, кл, С 06 F 15/332, 1986.

Авторское свидетельство СССР

М 1320804, кл. G 06 F 15/332, 1986. (54) УСТРОЙСТВО ДЛЯ ФОРЬИРОВАНИЯ

АДРЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ. (57) Изобретение относится к вычис„„SU„„160525 A 1

2 лительной технике и может быть использовано в составе процессора БПФ, Цель изобретения заключается в расширении области применения за счет реализации формирования адресов в алгоритмах простых множителей, Винограда полиномиальных преобразований.Для этого устройство содержит суммирующие счетчики 1, 2, группу из L суммирующих счетчиков 5, преобразователь 7 кодов, комбинационный сумматор 9 и регистр 10 адреса, дешифратор 3, группу мультиплексоров 4,группу блоков 6 умножения, мультиплексор 8 и группу регистров 11. 2 нл.

1605255

Изобретение относится к вычислительной технике и может быть использовано в составе процессора быстрого преобразования Фурье (БПФ).

Цель изобретения — расширение области применения устройства за счет реализации формирования адресов в алгоритмах простых множителей, Винограда.и полиномиальных. преобразований.

На фиг.! представлена структурная схема устройства, выполняющего формирование адресов процессора БПФ,реализующего алгоритм Винограда; на фиг. 2 — временная диаграмма работы устройства.

В состав вычислительного устройства, выполняющего формирование адресов процессора БПФ, реализующего алгоритм Винограда, входят первый суммируюшуй счетчик 1, второй суммирующий счетчик 2, дешифратор З,группа мультиплексоров 4, группа суммирующих счетчиков 5, группа блоков 6 умножения, преобразователь 7 кодов, мультиплексор 8, комбинационный сумматор 9, регистр 1О адреса, группа регистров 11, вход 1-2 сопровождения данных устройства, выход 13 устройства, входы 14.1-14,L постоянного коэффициента устройства.. !

Устройство предназначено для формирования адресов процессора, реализующего алгоритм Винограда преобразования Фурье (АВПФ). Алгоритм Винограда основан на представлении

Ь матрицы Н 1 1 Н - точечного диск"

Е=! е ретного преобразования Фурье (ШЕФ), где !1Š— взаимно простые числа, в виде прямого произведения матриц

Ы вЂ” точечных ДПФ е

У !! ® 1.! ® Ят,Щ и сведении вычисления 11Е - точечных

ДПФ к вычислению круговых сверток с использованием арифметики в кольце полиномол. Короткие НŠ— точечные последовательности вычисляются по алгоритму Рейдера, позволяющему существенно сократить число вычислитель/ ных операций, Алгоритм Винограда объединяет короткие последовательности в гнездовую структуру, Адреса операндов для алгоритма

Винограда определяются на входе по китайской теореме об остатках (КТО):

М и= — — -"n Т ° mod M (1) — m е е"

Э 7

В=1

5 rpe М = 11 шŠ— размер преобразования;

Е= m — взаимно простые модули; и - вычет и по модулю ш

И

10 - — — -"Т= 1 modm е

Последовательность адресов на выходе . определяется по формуле

И

15 и = ъ — — — и ° mod M (2) ш с=1 е е

Реализация АВПФ состоит из Ь этапов, на каждом из которых адреса операндов определяются по формуле (1), Различается лишь порядок следования членов формулы (1). Так, на первом этапе t изменяется от 1 до L, на вто-, ром — от 2 до Ь и далее до 1, на третьем от 3 до Ь и далее до 2 и т.д. Такую процедуру реализует кольцевая структура из Ь счетчиков по взаимно простым модулям. На f-м этапе реализации АВПФ Е-й счетчик группы является первым по порядку рабо30 ты, (1+1)-й — вторым и т.д. На счетный вход первого по порядку работы счетчика группы поступают импульсы сопровождения данных, на счетные входы остальных счетчиков группы сигналы с выходов переполнения предыдущих счетчиков группы. Данным процессом управляют первый 1 и второй 2 счетчики и дешифратор 3.

На каждом f-м этапе на счетный вход первого счетчика 1 поступают импульсы сопровождения данных и после прихода (H-1)-ro импульса формируется сигнал его переполнения, который

45 поступает на счетный вход второго счетчика 2, увеличивая его содержимое на единицу. Таким образом, счет,— чик 2 является счетчиком итерации или этапа. На Й-м этапе 2-й выход дешифратора 3 находится в активном состоянии, т.е. на Г-м выходе — логический нуль, который поступает на управляющий вход 8-го мультиплексора

4 группы, разрешает прохождение на его выход информации с его первого входа, т.е. импульсов сопровождения данных. Остальные выходы дешифратора

3 - пассивны и находятся в логической единице, поэтому на выходы всех

5 1605255 мультиплексоров 4 группы, кроме 1-го, проходит информация с их вторых входов, т.е. информация с выходов переполнения предыдущих счетчиков 5 груп5 пы.

При этом E-й счетчик 5 группы подсчитывает по модулю п импульсы сопС ровождения данных. При достижении

6-м счетчиком 5 группы значения 10 (n8 1) формируется сигнал переполнения, который переводит (1+1)-й счетчик 5 группы в очередное состояние.

Аналогично при достижении ((+1)-м счетчиком значения (пС„ -1) формиру- 15 ется его сигнал переполнения, который переводит в следующее состояние (+2)-й счетчик и т.д, На каждом такте очередное значение f-го счетчика 5 группы умножается на постоянную величину С

И

Т, т.е. на f-м умножителе

"Е С

6 группы, и результат умножения поступает на f-й регистр-фиксатор 11.

На следующем такте это значение че— рез мультиплексор 8 поступает на сумматор 9, где суммируется с предыдущим значением адреса, хранящимся в регистре 10, Сумма, представляющая 30 собой очередной адрес, записывается в регистр 10 адреса, Управление мультиплексором 8 осуществляет преобразователь 7 кодов (фиг.2)..

Закон функционирования преобразователя кодов, Если состояние первого счетчика 5 группы ненулевое, открыт первый канал. Если состояние первого счетчика 5 группы нулевое, а второ- 40 го ненулевое, открыт второй канал.

Если состояние двух первых счетчиков нулевое, а третьего — ненулевое, открыт третий канал и т.д. Сумматор

9 является сумматором по модулю И.

Таким образом,. на каждом такте устройство формирует адрес согласно формулам (1) или (2).

Формула и з о б р е т е н и я суммирующего счетчика соединена с группой входов дешифратора, о т л ич ающе е с я тем, что, с целью расширения области применения устройства за счет реализации формирования адресов в алгоритмах простых множителей, Винограда и полиномиальньгх: преобразований, в него дополнительно введены второй суммирующий счетчик, группа из L суммирующих счетчиков (где L — количество взаимно простых сомножителей, на которое разлагается входной массив преобразования И =

= И,.И . M>...5!p...M1, преобразователь кодов, комбинационный сумматор и регистр адреса, причем выход переполнения первого суммирующего счетчика соединен со счетным входом второго суимирующего счетчика, Й-й выход дешифратора, где Г = 1,Ь, соединен с управляющим входом f-го мультиплексора группы, инйормационный выход которого соединен со счетным входом

Е-го суммирующего счетчика группы, выход переполнения которого соединен с первым информационным входом (I +

+ 1)-ro мультиплексора группы, выход переполнения L-ro суммирующего счетчика группы соединен с первым управляющим входом первого мультиплексора группы, группа выходов У-го суммирующего счетчика группы соединена с группой входов множителя E-ro блока умножения и с Е-й группой входов преобразователя кодов, i-я группа выходов которой, где l i glog

i-ми управляющими входами мультиплексора, группа выходов которого соединена с первой группой входов комбинационного сумматора, группа выходов которого соединена с группой входов регистра адреса, группа выходов кото45 рого соединена с второй группой входов комбинационного сумматора, группа выходов Й-го блока умножения соединена с группой входов Й-ro регистра группы, группа выходов которого соедине50 на с 2-й группой информационных вхоУстройство для формирования адресов процессора быстрого преобразо-. вания Фурье, содержащее первый суммирующий счетчик, дешифратор, группу мультиплексоров, группу блоков умножения, группу регистров, мультиплексор, причем группа выходов первого дов мультиплексора, вход сопровождения данных устройства соединен со счетным входом первого суммирующего счетчика, с вторыми информационными входами всех мультиплексоров группы, с входом синхронизации Х-го регистра группы и с входом синхронизации регистра адреса, группа выходов ре1605255 гистра адреса соединена с информационным выходом устройства, группа входов множимого E-ro блока умножения соединена с входом E.-ro постоянного коэффициента устройства.. 8ых.

f""80., ГЧ

ЧИКА В9

2-иуграЯ бх

ЩЯОЯИПЛВКСО

Редактор Н,Тупица

Заказ 3455 Тираж 567 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

Вью. 2-го ест гика гр дых 1-гд Эви группы д . Вых. г-8006

Вьгх. 2-го дан

8руМыб

Вы.2-га аде

f-й ад.й

iYg needs

Составитель Ю.Ланцов

Техред М.Дидык Корректор Т.Палий