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

и подключен.к выходу переполнения второго счётчика операндов, счетный вход которого соединен с первбм входом первого элемента ИЛИ-НЕ и подключен к инверсному выходу первого триггера, прямой выход которого подключен к первому входу второго элемента ИЛИ-НЕ, второй вход которог соединен со вторым входом первого элемента ШШ-НЕ и подключен к выходу элемента ИЛИ, первый и второй входы которого подключены соответственно к выходу младшего разряда первого регистра итераций и информационному выходу первого счетчика операндов, выход переполнения которого подключен к счетному входу третьего триггера и входу третьего элемента И, выход которого подключен к тактовому входу первого регистра итераций информационный выход которого подключен к первому входу первого блока элементов И, первому информационному входу третьего блока коммутаторов и информационному входу первого коммутатора, выход которого подключен к инверсному входу третьего элемента И и D -входу третьего триггера, прямой выход которого подк/почен к первому входу первого элемента И, выходы первого и второго элементов И подключены ко вторым

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

Цель изобретения - повышение быстродействия.

На фиг. 1 представлена функциональная схема многоканального устройства быстрого преобразования Фурье с конвейерной обработкой операндов.

Устройство содержит блок 1 посто- янной памяти, арифметический блок (АБ) 2, блоки памяти 3 и 4, счетчик итераций 5, блок 6 сдвига, блоки

752 .

входам соответственно первого и второго блоков элементов И, выходы, которых подключены к управляющим входам соответственно первого и второго узлов вычисления инверсного кода, выход первого узла вычисления инверсного кода подключен к первому информационному входу третьего блока коммутаторов, выход KOTOpioro подключен к первым информационным входам первого и второго блоков ком- мутат оров, выходы которых подключены к адресным входам соответственно первого и второго блоков памяти, входы обращения которых подключены к выходам соответственно первого и второго элементов ИЛИ-НЕ, вторые информационные входы первого и второго блоков коммутаторов подключены к выходу четвертого блока коммутаторов, управляющий вход которого соединен с вторыми входами первого и второго элементов И, управляклцим входом третьего блока коммутаторов и подключен к прямому выходу первого триггера, прямой выход второго триггера подключен к управляющим входам первого и второго блоков коммутаторов , л информационный выход .счетчика итераций подключен к управляющему входу блока сдвига.

коммутаторов 7-10, узлы 11 и 12 вычисления инверсного кода, триггеры 13 и 14, коммутаторы 15 и 16, блоки 17 и 18 элементов И, регистры итераций 19 и 20 счетчики операндов 21 и 22, элемент И 23, элементы ШШ-НЕ 24 и 25, элементы и 26-28, элемент ШШ 29, узел синхронизации 30, триггеры 31-32.

Объем каждого из блоков 3 и 4 (оперативной) памяти составляет 2М К- М ячеек , где К 2 ( k 1, 2, .4.) - количество входных действительных последовательностей; (,2, ...)- количество отсчетов последовательности; К/2 1 2 (g О, 1, 2, ,..) - количество обрабатываемых комплексных массивов.

Объем блока 1 постоянной памяти .составляет N/2 ячеек хранения экспоненциальных коэффициентов.

Многоканальное устройство быстрого Преобразования Фурье с конвейерной обработкой операндов работает следующим образом.

В первом 3 и втором 4 блоках хранится 2 К комплексных массивов объемом М выборок (каждый массив формируется из двух действительных последовательностей fa, 5 и ,

так что Refx; aiV, Dm {х;

ГЪ;1 выборки внутри массивов распо- ложены в двоично-инверсном порядке, массивы занесены в блоки 3 и 4 также в двоично-инверсном порядке.

На входе X1 устройства устанавливается двоичный код числа обрабатываемых массивов одного блока 3 или 4.

В начальном состоянии первый 19, второй 20 регистры итераций, счетчик итераций 5, первый 31, второй 32, третий 13 и четвертый 14 триггеры первый 21 счетчик операндов обнулены а разряды второго 22 счетчика операндов установлены в состояние логическая 1.

Узел синхронизации 30 генерирует серию тактовых импульсов, поступающих на счетный вход первого триггера 31. На выходе первого триггера 31 и выходах разрядов первого 21 и второго 22 счетчиков формируется исходный код адресов обращения к первому и второму блокам 3 и 4. На прямом и инверсном выходах второго триггера 32 формируется сигнал считьтание-за- пись информации для первого блока 3 и сигнал запись-считывание для второго блока 4. Кроме того, сигнал с прямого выхода второго триггера 32 является управляющим для первого 7 и второго 8 блоков коммутаторов, причем по сигналу О на въ{ходах . коммутаторов блоков 7 и 8 пЗявляет- ся информация с первых входов, а по сигналу 1 - со вторых входов. Сигналы с выходов переполнения первого 21 и второго 22 счетчиков операндов через третий 27 и четвертьй 28

211752

элементы И поступают на тактовые входы первого 19 и второго 20 регистров итераций соответственно. При . этом информация, хранимая в регист5 pax 19 и 20, сдвигается на один

разряд в сторону старших разрядов, а в младший разряд заносится 1. Состояние разрядов регистров 19 и 20 итераций управляет коммутаторами

10 соответствующих блоков 9 и 10 коммутаторов так, что на их выходах формируются коды адресов при записи и считывании операндов первого и второго блоков 3 и 4 для выполняемой

15 итерации БПФ.

Сигнал с выхода переполнения второго счетчика 22 олерандов поступает на тактовый вход счетчика 5 итераций, двоичный код на выходах разрядов которого управляет сдвигом исходного кода, поступающего на информационный вход блока 6 сдвига с выходов элементов узла 12. Сдвинутый исходный код на выходе блока 6 сдвига является адресом экспоненци- апьнйго множителя W , которьй хранится в блоке 1. Значения синуса и косинуса, являющиеся мнимой и действительной частями экспоненты W, поступают .на вход экспонент АБ 2 и хранятся в регистрах синуса и косинуса АБ-2, На информационный вход операндов АБ 2 и интервале времени Т поступают выборки из первого

блока 3 (на входе управления записью- считыванием первого блока 3 потенциал О, причем вначале считьюается. второй операнд В пары операндов А ; и В). Выборки операндов А и В хранятся: во входных регистрах операндов АБ 2, В следующий интервал времени Т операнды А и В подвергаются элементарному преобразованию вида AiB W , во входные регистры

операндов заносятся выборки С,р из второго блока 4, а в регистры синуса и косинуса АБ 2 - величина W . В интервале времени Т, преобразованные операнды А и В поступают в выходные регистры АБ 2 и записьшаются во второй блок 4 (при этом на его входе управления записью-считыванием потенциал 1), операнды С и D подвергаются элементарному преобразованию, а во входные регистры операндов АБ 2 заносятся выборки Е и F из первого блока 3. В интервале времени Тц преобразованные операнды С и

D поступают на хранение в первый блок 3, orfepaHflbi Е и f подвергаются преобразованию, а из второго блока считываются и поступают во входные регистры АБ 2 операнды Т , Н , причем в регистры синуса и косинуса АБ 2 заносятся очередные значения

экспоненты

соответствующие

элементарному преобразованию над Очередной парой операндов согласно графу БПФ с замещением, двоично-инверсным порядком отсчетов на входе и прореживанием по времени.

В таблице приведены адреса обращения к первому и второму блокам 3 и,4, блоку 1 и очередность обрабатываемых массивов по 16 комплексных выборок каявдый.

При выполнении последней fn -ой итерации БПФ на выходах (п1-1)-ых разрядов первого 19 и второго 20 регистров итераций устанавливается 1, которая через (К + 1)-ые входы первого 15 и второго 16 коммутаторо поступает на информационные входы третьего 13 и четвертого 14 триггеров и блокирует входы первого 19 и второго 20 ре гистров итераций. Сигналы переполнения с выходов первого 21 л второго 22 счетчиков операндов перебрасьтают триггеры 13 и 14 в состояние логической 1 и начинается дополнительная итерация распаковки массивов. При этом сигнал 1 i

разрешает прохождение серии импульсов с выхода первого тригг ера 31 на вторые входы элементов И блоков 17 и 18. серии импульсов через

первые В (, 2, ...,т-1) элементов блоков 17 и 18 проходят на первые управляющие входы элементов первого 11 и второго 12 узлов и инвертируют исходный код первых разрядов первого 21 и второго 22 счетчиков операндов (инвертирование осуществляется сигналом 1 на выходе первого 31 триггера во время формирования кода адреса второго операнды из пары операндов А и В). Сигналы с выходов разрядов (т, 1, ...,п-2,ц -1) счётчиков 21 и 22 не инвертируются, поскольку нулевое состояние разрядов (т, т-н

+ 1, .. .,п-2,и -1) первого 19 и второго 20 регистров итераций блокируют элементы (Im, m+1,..., n -2, n-1) блоков 17 и 18, с выходов которых на управлякицие входы соответству- кяцих элементов узлов 11 и 12 также поступает сигнал О. Коды адресов обращения к первому и второму блокам 3 и 4 при вьтолнении распаковки приведены в таблице. Сигнал 1 с выхода четвертого триггера 14 поступает на второй управляющий вход АБ 2, выполняющий элементарное преобразование вида.

Элемент ИЖ 29, первый 24 и второй 25 элементы ИЛИ-НЕ предназначены для формирования сигналов запрещения обращения первого и второго блоков 3 и 4 при записи информации из / обнуленных выходных регистров АБ 2 в блоки 3 и 4 на месте первой пары операндов во время выполнения первой итерации БПФ.

ё

я)

ш

w

91

О

А

е

Составитель А. Баранов Редактор Т. Парфенова Техред А.Бабинец Корректор Л. Патай

Заказ 642/54

Тираж 673

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ШШ Патент, г. Ужгород, ул. Проектная, 4

Подписное