Каскадное устройство быстрого преобразования фурье
Л.4Т,, Союз Советских
Социалистических
Республик
О П И С А- "Н- -"И-"Е
ИЗОБРЕТЕНИЯ
<п1723584
К АВТОУСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 200378 (21) 2592262/18-24 с присоединением заявки ¹ (23) ПриоритетОпубликовано 250380., Ьнзллет нь Э 11
Дата опубликования описания 25.0380 (51)М. Кл,2
С 06 Р 15/34
Государственный коиитет
СССР по делан изобретений и открытий (53) УДК 681 3 (088. 8) с
И.Г. Грибков, В.П. Кошелев, A.A. Мошков, И.Ф. Мусатов и Т.Л. Степукова (72) Авторы изобретения (71) Заявитель (54) КАСКАДНОЕ УСТРОЙСТВО БЫСТРОГО
ПРЕОБРАЗОВАНИЯ ФУРЬЕ
Изобретение относится к автома:гике и вычислительной технике и может быть использовано в цифровых вычислительных системах обработки информации.
Известно каскадное устройство быстрого преобразования Фурье, которое содержит группы арифметических блоков, блоков постоянной памяти, блоки памяти последовательного доступа (1).
Наиболее близким техническим ре- шением к изобретению является каскадное устройство быстрого преобразования Фурье, содержащее П последовательно соединенных блоков памяти и соответствующих им арифметических блоков (2) °
Недостатком обоих известных устройств является большое время от момента начала обработки одного исходного массива до завершения обработки и получения всех коэффициентов Фурье. Во многих случаях эа это время информация либо устаревает, либо возникают неудобства ее использования.
Цель изобретения - повьхаение быстродействия устройства.
Поставленная цель достигается тем, что каскадное устройство быстрого преобразования Фурье, содержащее П блоков памяти и П-1 арифметических блоков, причем первый вход и выход (-го (1 1- и — 1) блока памяти подключены соответственно к первому выходу и первому входу 1 -ro арифметического блока, содержит блоков формирования адресов и И - 2 коммутаторов, причем первый выход
4 -го (1 1-й) блока. Формирования адресов подключен к адресному входу
1 -го блока памяти, второй выход
1 -го (1 = 1 - ll- 1) блока формирования адресов - ко входу (j + 1) -го блока формирования адресов, вход первого коммутатора является входом устройства первый и второй выходы
1 -го (4 1 — и — 3) коммутатора подключены соответственно ко второму входу -ro арифметического блока и ко входу (з+ 1)-го коммутатора, первый и второй выходы (ll- -2) - го коммутатора — соответственно ко второму входу (й-2)— го и (П-1)-го арифметических блоков, второй выход j -го (1 =1- )з -1) арифметического блока подключен ко вто723584 рому входу (+1)-ro блока памяти, выход . П-го блока памяти — к третьему входу (и -1) -ro арифметического блока, третий выход которого является выходом устройства.
На Фиг. 1 показана функциональная схема устройства; на фиг. 2 порядок выполнения операций двухточечного преобразования Фурье для различных арифметических блокон при числе отсчетов информации N= 64;
Н„. и К„ (1 =1-6) указывают начало и конец вычислений в 1 -ом блоке.
Каскадное устройство быстрого преобразования Фурье содержит блоки 1 памяти, блоки 2 Формирования адресов, арифметические блоки
3, коммутаторы 4, вход 5 и выход
6. устройство работает следующим образом.
По шине 5 вводится исходная информация, которая через 1-ый коммутатор попадает в i --ый арифметический блок. Из 1-ro блока памяти выбирается константа весовой функции и производится умножение очередного операнда исходного массива.
Результат умножения записывается в некоторую ячейку 1 -ro блока памяти. Адресация памяти как для записи, так и для считывания производится соответстнующим блоком формирования адресов. Порядок включения коммутаторов, арифметических блоков, блоков формирования адресов обеспечинается блоком управления (на фиг. 1 не показан ).
Основной режим — выполнение задачи быстрого преобразования Фурье начинается, когда вся исходная ин-. формация, умноженная на весовую функцию, представлена в соответствующих зонах всех блоков памяти.
С этого момента начинается основной цикл работы. Из каждого 1.-ro блока памяти выбираются соответствующие операнды и константы и выполняется очередная типовая операция, например двухточечное преобразование Фурье;
q „- х „„- х„, „„ехр
ii+2. h,1 q tip j qt-"P (3, ).
Результат типовой операции, полученной в 1 -ом арифметическом блоке записывается в 1+1-ый блок памяти. Запись операндон пронодится по тем же адресам,, что и считывание, поэтому выработанные конкретные адреса для считывания операндов в
j-ом блоке формирования адресов передаются по соответствующим шинам
+1-ому блоку формирования адресов, где используются как адреса для организации записи результата операции в i --ом арифметическом блоке в (+1 блок памяти.
Предлагаемое устройство позволяет за счет однонременного начала параллельных вычислений с р(р= о й)гочz ками исходного массива (см. Фиг. 2, точки Н, ) закончить вычисление за время последовательчого выполнения самой длинной параллельной ветки, т. е. ветки Нр g — К- 1 и Н вЂ” К .
Первая из этих последовательностей состоит из двухточечных преобразований Фурье, вторая — из 2М двухточечных последовательностей. Последний арифметический блок реализует две последние параллельные ветки
15 и одновременно выполняет три типовых преобразования Фурье. Тем самым процесс с Н,и с Н> сводится к Н типовым тройным операциям. По времени эти операции не превышают одну
20 любую типовую операцию двухточечного преобразования Фурье, ввиду того, что на последних, указанных выше, параллельных ветках не применяется операция умножения. Действительно
25. 2 В
e,хр -j — — )=ехр -j — =О- =-j<, N ) 2 ехр -) )=ехр (- о) = - о=, 2 0 поэтому можно не использовать умножители, а обойтись сумматорамивычитателями., Можно показать, что время обраЗ5 ботки одного массива исходной информации в известном устройстве Т и в предлагаемом устройстве Т связаны соотношением
Т1 (46с я2 + (4Log 8+4) 44О = з = "Т Ы т 4 3
Например, при и =1024 В = 4ф=13, т. е. предложенное устройство в д5 13 раз оперативнее выполняет преобразование Фурье.
Формула изобретения
Каскадное устройство быстрого преобразования Фурье, содержащее П блоков памяти и П -1 арифметических блоков, причем первый вход и выход
1 -го (1 =1- П -1) блока памяти по) ключены соответственно к первому выходу и первому входу -ro арифметического блока, о т л и ч а ю— щ е е с я тем, что, с целью повыщения быстродействия, оно содержит
Qp П блоков формирования адресов и
П-2 коммутаторов, причем первый выход 1 -ro (1 =1- П) блока формирования адресов подключен к адресному входу 1 -ro блока памяти, второй выход i-го (1 =1- и — 1) блока фор723584
Фиг. 2
ПНИИПИ Заказ 929/15 Тираж 751 Подписное
Филиал ППП Патент, г. Ужгород,. ул. Проектная, 4 мирования адресов — ко входу ((+1)-го блока формирования адресов, вхоц первого коммутатора является входом устройства, первый и второй выходы
i -го ((= 1 — н — 3) коммутатора подключены соответственно ко второму входу -го арифметического блока и ко входу (1 + 1)-го коммутатора, первый и второй выходы (п-2)-го коммутатора — соответственно ко второму входу (n -2)-ro и (o-1)-го арифметических блоков, второй выход (-го ((=1-и — 1) арифметического блока подключен ко второму входу (1 +1)-го блока памяти, выход .П-го блока памяти — к третьему входу (h — 1)-го арифметического блока, третий выход которого является выходом устройства.
Источники информации, принятые во внимание при экспертизе
1. Зарубежная радиоэлектроника
Р 9, 1975.
2. Патент CILIA Р 3816729, кл. G 06 F 15/34, 1974 (прототип).
