Каскадное устройство быстрого преобразования фурье Советский патент 1980 года по МПК G06F17/14 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых вычислительных системах обработки ИНфОрМсЩИИ . Известно каскадное устройство быстрого преобразования Фурье, которое содержит группы арифметических блоков, блоков постоянной ти, блоки пгиляти последовательного доступа Ij. Наиболее близким техническим ре шением к изобретению является каск ное устройство быстрого преобразования Фурье/ содержащее П последовательно соединенных блоков памя и соответствующих им арифметически блоков 2. Недостатком обоих известных устройств является большое время от момента начала обработки одного исходного массива до завершения обработки и получения всех коэффициентов Фурье. Во многих случаях з зто время информация либо устарева ет, либо возникают неудобства ее использования. . Цель изобретения - повыиение быстродействия устройства Поставленная цель достигается тем, что каскадное, устройство быстрого преобразования Фурье, содержащее (1 блоков памяти и n-l арифметических блоков, причем первый вход и выход i-ro ( 1 1- и - 1) блока памяти подключены соответственно к первому выходу и первому входу -i -го арифметического блока/ содержит м блоков формирования адресов и h - 2 коммутаторов, причем первый выход i -го (i 1-П) блока формирования адресов подключен к адресному входу i -го блока памяти/ второй выход 1 -го ( 1 1 - П- 1) блока формирования адресов - ко входу (i 1)-го блока формирования адресов/ вход первого коммутатора является входом устройства первый и второй выходы 1-го (Н 1 -и- 3) коммутатора подключены соответственно ко второму входу i -го арифметического блока и ко входу (i+ 1)-го коммутатора, первый и второй выходы (П- 2) - го коммутатора - соответственно ко второму входу (h-2)го и (H-l)-ro арифметических блоков, второй выход т-го (1 1- П-1) арифметического блока под1с.гаочен ко второму входу (-i +1)-го блока памяти, выход . п-го блока памяти - к третьему входу ( п-1) -го арифметического блока, третий выход которого является выходом устройства.

На фиг. 1 показана функциональная схема устройства на фиг. 2 порядок выполнения операций двухточечного преобразования Фурье для различных арифметических блоков при числе отсчетов информации N 64 и ( ) указывают начало и конец вычислений в 1-ом блоке.

Каскадное устройство быстрого преобразования Фурье содержит блоки 1 памяти, блоки 2 формирования адресов, арифметические блоки 3, коммутаторы 4, вход 5 и выход 6.

Устройство работает следующим образом.

5 вводится исходная информация, которая через i-ый коммутатор попадает в i-ый арифметический блок. Из 1-го блока памяти выбирается константа весовой функции и производится умножение очередного операнда исходного массива. Результат умножения записывается в некоторую ячейку -i -го блока памяти. Адресация памяти как для записи, так и для считывания производится соответствующим блоком формирования адресов. Порядок включения коммутаторов, арифметических блоков блоков формирования адресов обеспечивается блоком управления (на фиг. 1 не показан .).

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

- } ,

,,i-r n+ai-i P

ыу

f

пЛ.

H-V2 n.i-V г

Результат типовой операции, полученной в i-ом арифметическом блоке записывается в i -ьХ-ый блок памяти. Запись операндов проводится по тем же адресам,, что и считывание, поэтому выработанные конкретные адреса для считывания операндов в

i-OM блоке формирования адресов передаются по соответствующим шинам

i +1-ОМУ блоку формирования адресов, где используются как адреса для организации записи результата

операции в i-ом арифметическом блоке в 1+1 блок памяти.

Предлагаемое устройство позволяет за счет одновременного начала параллельных вычислений ср (p )T04ками исходного массива (см. фиг. 2, точки Н ) закончить вычисление за время последовательного выполнения самой длинной параллельной ветки, т. е. ветки Нр. - Кр и Нр - Кр. Первая из этих последовательностей состоит из двухточечных преобразований Фурье, вторая - из 2N двухточечных последовательностей. Последний арифметический блок реализует две последние параллельные ветки и одновременно выполняет три типовых преобразования Фурье. Тем самым процесс с Нр и с Нр сводится к N типовым тройным операциям. По времени эти операции не превышают одну 0 любую типовую операцию двухточечного преобразования Фурье, ввиду того, что на последних, указанных выше, параллельных ветках не применяется операция умножения. Действительно

V)(2)

p() i,

поэтому можно не использовать умножители, а обойтись сумматорами в ычи тат елями...

Можно показать, что время обработки одного массива исходной информации в известном устройстве Т и в предлагаемом устройстве Tj связаны соотношением

т (4e,ogf2N-H) 4eog2Ntn 4--- V.

Например, при В - ;tl3, т. е. предложенное устройство в 45 13 раз оперативнее выполняет преобразование Фурье.

Формула изобретения

Каскадное устройство быстрого преобразования Фурье, содержащее h блоков памяти и И-1 арифметических блоков, причем первый вход и выход i-ro ( П-1) блока памяти подключены соответственно к первому выходу и первому входу -i -го арифметического блока, отличающееся тем, что, с целью повыщения быстродействия, оно содержит

0 Ч блоков формирования адресов и

11-т2 коммутаторов, причем первый выход i -го ( i 1-11) блока формирог вания адресов подключен к адресному входу 1-го блока памяти, второй

5 выход i-ro ( -j 1-п- 1) блока формирования адресов - ко входу (i+l)-r блока формирования адресов, вход первого коммутатора является входом устройства, первый и второй выходы -i -го ( ti-3) коммутатора подключены соответственно ко второму входу 1 -го арифметического блока и ко входу (i-f-l)-ro коммутатора, первый и второй выходы ( ц-2)-го коммутатора - соответственно ко второму входу ( п-2)-го и ( п-1)-го арифметических блоков, второй выход i-ro (1 -1-h -1) арифметического

блока подключен ко второму входу ( 1+1)-го блока памяти, выход ,п-го блока памяти - к третьему входу (h-l)-ro арифметического блока, третий выход которого является выходом устройства.

Источники информации, принятые во внимание при экспертизе

1. Зарубежная радиоэлектроника 9, 1975.

2.Патент США № 3816729,

кл. G 06 F 15/34, 1974 (прототип).