Устройство для быстрого преобразования Фурье последовательности с нулевыми элементами Советский патент 1982 года по МПК G06F17/14 

Изобретение относится к вычислительной технике и может быть использовано для выполнения быстрого преобразования. Фурье. Известны устройства для выполнения быстрого преобразования Фурье, содержащие арнфметический блок, входной блок памяти, блок памяти, блок памяти тригонометрических коэффициентов и блок управления 1 и 2). Однако в этих устройствах не используются возможности для уменьшения времени вычислений при преобразовании последовательностей, содержащих часть нулевых элементов. Кроме того, в этих устройствах ненулевая часть элементов должна быть расположена в начальной части исходной последовательности. Наиболее близким к предлагаемому является устройство для быстрого преобразования Фурье последовательности с нулевыми элементами, содержащее арифметический блок, входной блок памяти, блок памяти, блок умножения, блок памяти тригонометрических коэффициентов и блок инверсной перестановки 3 Недостатком известного устройства является то, что в нем использованы не все возмож кости для уменыиения времени вычислении быстрого преобразования Фурье последовательности с нулевыми элементами, так как под-, ключение блока инверсной перестановки к выходу блока памяти в схеме распределительного блока обуславливают длительное время ал иереадресацшо и пересылку полной последовательности, содержащей часть нулевых элементов. Цель изобретения - повьш1енне быстродействия устройства. Поставленная цель достигается тем, что в устройство, содержащее блок умножения, арифметический блок, блок синхронизации, блок .памяти результатов, блок памяти коэффициентов, входной блок памяти, информационный вход которого является входом устройства, выход блока памяти результатов соединен с первым информационным входом арифметического блока, первый информационный вход блока памяти результатов соединен с выходом арифметического блока, второй информационный вход которого подключен к первому выходу блока памяти коэффициентов. второй выход которого соединен с первым информационным входом блока умножения, выход которого является выходом устройства, выход блока синхронизации соединён со входами синхронизации входного блока памяти, блока умножения, арифметического блока, блока памяти результатов и блока памяти коэффициентов, дополнительно введен распределительный блок, информационный вход и вход синхронизации которого соедийен соответственно с выходом входного блока памяти и с выходом блока синхронизации, информационный выход и адресный выход распределительного блока соединены соот ветственно со вторым информационным входом и с адресным входом блока памяти ре-зультатов, выход которого соединен со вторым информационным входом блока умножения. Кроме того, распределительный блок содержит счетчик, дешифратор, матрицу элементов И, группу элементов ИЛИ, причем вход синхронизации блока соединен со входом счетчика, выход которого соединен с адресным выходом блока и со входом дешифратора, выходы которого соединены с первыми входами элементов И соответствующих столбцов матрицы элементов И, разряды информационного входа блока соединены со вторыми вхо дами элементов И соответствующих строк матрицы элементов И, выходы элементов И каждой строки матрицы элементов И соедине ны с соответствующими входами соответствую щег-о элемента ИЛИ группы, выходы элементо ИЛИ группы соединены с соответствующими разрядами информационного выхода блока. На фиг. 1 представлена блок-схема устройства; на фиг. 2 - распределительный блок, функциональная схема. Устройство содержит входной блок 1 памя ти, блок 2 синхронизации, распределительный блок 3, блок 4 памяти результатов, арифмети ческий блок 5, содержащий сумматор 6 и умножитель 7, блок 8 памяти коэффициентов и блок 9 умножения. Распределительный блок 3 содержит счетчик 10, дешифратор 11, матрицу 12 элементов И, группу 13 элементов ИЛИ. Устройство работает следующим образом. М ненулевых элементов последовательности от которой вычисляется преобразование Фурье поступают во входной блок 1 памяти и затем переупорядочиваются в отличие от извест ного устройства, в котором переупорядочиванию подвергается целиком весь массив из N отсчетов. Следовательно, при М «Ы в устро стве затрачивается гораздо меньще времени иа формирование адресов инверсных перестановок и обмен данных при выполнении этих перестановок. Далее распределительный блок 3 осуществляет продолжение ненулевой части последовательности, получаемой на выходе блока инверсной перестановки, на всю последовательность в блок 4 памяти результатов. Каждый переупорядоченный элемент из блока 1 записывается в помощью распределительного блока 3 в массив ячеек блока 4 памяти результатов. Адреса ячеек памяти определяются содержимым счетчика 10, разрядность которого соответствует длине входной последовательности N, на счетный вход которого поступают тактовые сигналы записи. С помощью дешифратора 11 на выход распределительного блока 3 передаются ненулевые отсчеты и производится дополнение входной последовательности нулевыми отсчетами. В отличие от известного устройства, в котором распределение ненулевых отсчетов в блок 4 памяти результатов производится по сложной адресации ячеек, начиная с первого элемента с периодом, равным минимальной степени двух не превосходящих число ненулевых элементов, запись в массив ячеек производится последовательно сначала первого элемента, затем - второго и тд. до последнего ненулевого элемента. Это позволяет сократить время на переадресацию ячеек памяти и упростить конструкцию распределительного блока 3. Арифметический блок 5 выполняет стандартные арифметические операции сложения и умножения- над элементами исходной последовательности, . хранящимися в блоке 4 памяти результатов и значениями тригонометрических коэффициентов, взятых из блока 8 памяти тригонометрических коэффициентов. После заверщения вычислений полученные коэффициенты Фурье поступают в блок 9 умножения, на второй вход которого подаются значения тригонометрических коэффициентов из блока 8, значения которых определяются числом начальных нулевых элементов входной последовательности данных. Предлагаемое устройство позволяет повысить быстродействие за счет сокращения времени на формирование адресов и обмен данных при перестановках в занесении в блок памяти, а также .упростить конструкцию распределительного блока. Формула изобретения 1. Устройство для быстрого преобразования Фурье последовательности с нулевыми элементами, содержащее блок умножения, арифметический блок, блок синхронизации, блок памяти результатов, блок памяти коэффициентов, входной блок памяти, информадаонный

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

96631

2.Устройство по п. 1,отлнчаюш е е с я тем, «гто распределительный блок содержит счетчик, дешифратор, матрицу элементов И, группу элементов ИЛИ, причем

у вход синхронизации блока соединен со входом счетчика, выход которого соединен с адресным выходом блока и со входом дешифратора, выходы которого соединеиы с первыми входами элементов И соответствующих

столбцов матрицы элементов И, разряды кнформациошюго входа блока соединены со

вторыми входами элементов И соотвегсгвуюших строк матрицы элементов И, выходы элементов И каждой строки матрицы элементов И

IS соединены с соответствуюидакш входами соответствующего элемента ИЛИ группы, выходы элементов ИЛИ групга 1 соединены с соответствующими разрядами информационного выхода блока.

М

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

1.Патент США К 3920978,кл.235-156, 1975. 2.Патент США Vf 4138730,кл.364-726, 1979.

3.Авторское свидетельство СССР № 509872, кл. G 06 F 15/34, 1976 (прототип).

гг

//

////У

/еГ/

a/f