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

(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 3 ны соответственно с первым и вторым тактовыми входами устройства. На фиг. 1 представлена блок-схем предлагаемого устройства; на фиг.2- алгоритм БПФ, реализуемый устройством. Устройство включает блок памяти состоящий из N регистров 2 сдвига, арифметический блок 3, блок 4 памяти коэффициентов, первые элементы И 5, вторые элементы И 6, элементы ИЛИ 7, Регистры сдвига 2 для общего слу чая V -точечного преобразования Фурье делятся на две группы, по N/2 в каждой группе. Два регистра 2 одной строки соответствуют графу одно го двухточечного БПФ алгоритма, изображенного на фиг. 2, и их нумерация соответствует нумерации горизонталей этого алгоритма. Регистры каждой группы соединены последовательно для передачи информации снизу вверх в арифметический блок 3 через элементы И 5, управляе мые серией тактовых импульсов ТИ 1. Параллельные выходы верхней пары регистров (О и К/2) подключены к ари метическому блоку 31 а выходы арифм тического блока 3 - к параллельным входам регистров с номерами ) и (N -1). Элементы И 6 соединяют регистры обеих групп для переупорядочивания информации в соответствии с алгорит мом фиг. 2. При этом последовательный выход регистра с номером чере соответствующие логические элементы И б и ИЛИ 7 соединен с последовательным входом регистра с номером j двоичный код которого образуется пу тем циклического сдвига на один разряд влево двоичного кода . Элементы И 6 управляются серией тактовых импульсов ТИ2. Для объединения выходов элементов И 5 и б служат э лементы ИЛИ 7 . Для работы устройства следует хранить в блоке 4 и подавать в ариф метическое устройство /2 пар коэффициентов вида 211к . 2ftK (,2,...,у). cosи am NN Перед началом работы выборки исходного сигнала размещаются в регистр х 2 устройства в соответствии со своими номерами.. Функционирование схемы осуществл ется под воздействием двух серий управляющих импульсов. Первая серия (ТИ1) включаетN/2 групп импульсов, по It в каждой группе. Под воздействи ем первой группы из tt импульсов осу ществляется сдвиг вверх на одну сту пень всех выборок сигнала, размещен Hbix в регистрах, и передача в арифметический блок 3 первой пары выбор сигнала. В то же время в арифметический блок 3 поступает первая пара коэффициентов, и в нем осуществляется первое двухточечное БПФ, результаты которого заносятся в регистры (11/2-1) и (N -1) по их параллельным входам. ЗаМ/2 подобных циклов завершается первая итерация БПФ над всеми выборками сигнала, после чего в схему поступает вторая серия из п импульсов ТИ2 для переупорядочивания информации в регистрах устройства в соответствии с алгоритмом БПФ (пунктирные линии на фиг. 2). Итерации повторяются2о j . В результате в регистрах устройства оказываются коэффициенты Фурье исходной последовательности выборок сигналу. Таким образом, применение модифицированного алгоритма БПФ, введение в устройство )il коммутирующих элементов, каждый из которых реализован на двух элементах И и одном элементе ИЛИ, и применение жестких связей между регистрами устройства выгодно отличает предложенное устройство от прототипа, так как число регистров памяти уменьшается вдвое, что сокращает объем используемого оборудования. Формула изобретения Устройство для реализации быстрого преобразования Фурье, содержащее блок памяти, арифметический блок и блок памяти коэффициентов, отличающееся тем, что, с целью сокращения оборудования блок памяти состоит из N регистров сдвига, элементов И, ИЛИ, причем параллельные входы ((/2-1)-го и (М -1)-го регистров сдвига соединены соответственно с первым и вторым выходом . арифметического блока, а параллель ные выходы нулевого и N/2 -го регистров сдвига соединены соответствен-г но с первым и вторым входом ари4 1етического блока, третий и четвертый входы которого соединены соответственно с выходами блока памяти коэффициентов, последовательный вход каждого регистра сдвига подключен к вЕЛХодам соответствующего элемента ИЛИ, а выход-к первым входам первого и второго соответствующих эле ментов И, выход первых элементов И каждого регистра сдвига, за исключением нулевого и W/2-го регистра сдвига, соединены с первыми входами элементов И предыдущих регистров сдвига, выход второгр элемента И i -го регистра сдвига соединен со вторым входом элемента ИЛИ j -го регистра сдвига, где J -двоичный код, полученный путем циклического сдвига разряд влево двоичного кода I , вторые входы всех первых и вторых элементов И соединены соот