Многоканальное устройство для быстрого преобразования фурье с конвейерной обработкой операндов

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК ((9(SU(((1 1 (51) 4 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3771632/24-24 (22) 18.07.84 (46) 15.02.86. Бюл. К - 6 (71) Научно-.исследовательский институт прикладных физических проблем им.А.Н.Севченко (72) А.Ф,Романов, В.P.Òóìñêàÿ, Л.В.Шестаков, А.Н.Карташевич и А.И.Ходосевич (53) 681.32(088.8) (56) Авторское свидетельство СССР

Р 809198, кл. С 06 F 15/332, 1979.

Авторское свидетельство СССР

Ф 1056206, кл. С 06 F 15/332, 1983. (54)(57) МНОГОКАНАЛЬНОЕ УСТРОЙСТВО

ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

С КОНВЕЙЕРНОЙ ОБРАБОТКОЙ ОПЕРАНДОВ, содержащее блок постоянной памяти, выход которого подключен ко входу коэффициентов арифметического блока, информационный выход которого подключен к информационным входам первого и второго блоков памяти, выходы которых подключены ко входу операндов арифметического блока, вход синхронизации которого подключен к первому выходу узла синхронизации, второй выход которого подключен к счетному входу первого триггера, прямой выход которого подключен к счетному входу второго триггера, прямой выход которого подключен ко входу управления записью — считыванием первого блока памяти и счетному входу первого счетчика операндов, информационный выход которого подключен к информационному входу узла вычисления инверсного кода, инверсных выход второго триггера подключен ко входу управления записью-считыванием второго блока памяти, перBbliI регистр итераций, о т л и ч аю щ е с я тем, что, с целью повышения быстродействия, в него введены первый, второй, третий и четвертый блоки коммутаторов, блок сдвига, счетчик итераций, второй узел вычисления инверсного кода, первый и второй элементы ИЛИ-НЕ, элемент ИЛИ, первый и второй блоки элементов И, первый и второй коммутаторы, третий и четвертый триггеры, второй регистр итераций и второй счетчик операндов, информационный выход которого подключен к информационному входу вто- Е рого узла вычисления инверсного ко.— да, выход которого подключен к первому информационному входу четвер- С того блока коммутаторов и информационному входу блока сдвига, выход которого подключен к адресному входу блока постоянной памяти, вход обращения которого соединен с входом ,синхронизации приема коэффициентов арифметического блока, первым входом второго элемента И и подключен к прямому выводу четвертого триггера, 2-вход которого соединен с инверсным входом четвертого элемента И и подключен к выходу второго коммутатора, информационный вход которого соединен с первым входом второго блока элементов И, вторым информационным входом четвертого блока коммутаторов и подключен к выходу второго регистра итераций, тактовый вход которого подключен к выходу четвертого элемента И, вход которого соединен со счетным входом четвертого триггера, счетным входом счетчика итераций

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

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

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

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

Устройство содержит блок 1 посто- !5 янной памяти, арифметический блок (АБ) 2, блоки памяти 3 и 4, счетчик итераций 5, блок 6 сдвига, блоки входам соответственно первого и второго блоков элементов И, sbrxop» которых подключены к управляющим входам соответственно первого и второго узлов вычисления инверсного кода, выход первого узла вычисления инверсного кода подключен к первому информационному входу третьего блока коммутаторов, выход которого подключен к первым информационным входам первого и второго блоков коммутаторов, выходы которых подключены к адресным входам соответственно первого и второго блоков памяти, входы обращения которых подключены к выходам соответственно первого и второго элементов ИЛИ-НЕ, вторые информационные входы первого и второго блоков коммутаторов подключены к выходу четвертого блока коммутаторов, управляющий вход которого соединен с вторыми входами первого и второго элементов И, управляющим входом третьего блока коммутаторов и подключен к прямому выходу первого триггера, прямой выход второго триггера подключен к управляющим входам первого и второго блоков коммутаторов, а информационный выход счетчика итераций подключен к управляющему входу блока сдвига. коммутаторов 7-10, узлы 11 и 12 вычисления инверсного кода, триггеры

13 и 14, коммутаторы 15 и 16, блоки

17 и 18 элементов И, регистры итераций 19 и 20, счетчики операндов 21 и 22, элемент И 23, элементы ИЛИ-HE

24 и 25, элементы И 26-28, элемент

ИЛИ 29, узел синхронизации 30, триггеры 31;32.

Объем каждого из блоков 3 и 4 (оперативной) памяти составляет.

2МК @ячеек; гдеК 2 (k= 1, 2, ... ) — количество входных действительных последовательностей;

М 2 (и) = 1, 2, ...) — количество, f11 отсчето последовательности; М/2 =

=L 2 (8=0, 1, 2, ...) — коли1211752 чество обрабатываемых комплексных массивов.

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

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

В первом 3 и втором 4 блоках хранится 2 К комплексных массивов (х; „ объемом М выборок (каждый массив формируется из двух действительных последовательностей (a„ 3 и :, I так что Re (х; = (a;$, 3m I x; ) ь

=-(b;j выборки внутри массивов расположены в двоично-инверсном порядке, массивы занесены в блоки 3 и 4 также в двоично-инверсном порядке.

На входе XI устройства устанавливается двоичный код числа обрабатываемых массивов одного блока 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 блоков коммутаторов причем по сигналу "0" на выходах коммутаторов блоков 7 и 8 появляется информация с первых входов, а по сигналу "1" — со вторых входов. Сигналы с выходов переполнения первого

21 и второго 22 счетчиков операндов через третий 27 и четвертый 28 элементы И поступают на тактовые входы первого 19 и второго 20 регистров итераций соответственно. При этом информация, хранимая в регистрах 19 и 20, сдвигается на один разряд в сторону старших разрядов, а в младший разряд заносится "1".

Состояние разрядов регистров 19 и 20 итераций управляет коммутаторами !

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

Сигнал с выхода переполнения второго счетчика 22 операндов поступает на тактовый вход счетчика 5

20 итераций, двоичный код на выходах разрядов которого управляет сдвигом исходного кода, поступающего на информационный вход блока 6 сдвига

- с выходов элементов узла 12. Сдви25 нутый исходный код на выходе блока 6 сдвига является адресом экспоненциального множителя е, который хранится в блоке 1. Значения синуса и косинуса, являющиеся мнимой и действительной частями экспоненты

Ф, поступают .на вход экспонент АБ 2 и хранятся в регистрах синуса и косинуса АБ-2. На информационный вход операндов АБ 2 и интервале времени

Т1 поступают выборки из первого

35 блока 3 (на входе управления записьюсчитыванием первого блока 3 потенциал "0", причем вначале считывается. второй операнд В пары операндов А и В). Выборки операйдов А и В

4о хранятся во входных регистрах операндов АБ 2. В следукяций интервал времени Т операнды А и В подвергаются элементарному преобразованию вида A B N, во входные регистры

45 операндов заносятся выборки <,9 из второго блока 4, а в регистры синуса и косинуса AS 2 — величина W и

В интервале времени Т> преобразованные операнды A и Ь поступают в вы50 ходные регистры АБ 2 и записываются во второй блок 4 (при этом íà его входе управления записью-считыванием потенциал "1"), операнды С и Э подвергаются элементарному преобразова55 нию, а во входные регистры операндов

АБ 2 заносятся выборки Е и F из ,первого блока 3 ° В интервале времени Тч преобразованные операнды С и

1211752

1О

20

Э поступают на хранение в первый блок 3, операнды E и подвергаются преобразованию, a из второго блока 4 считываются и поступают во входные регистры АБ 2 операнды У, Н, причем в регистры синуса и косинуса

АБ 2 заносятся очередные значения

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

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

При выполнении последней п -ой итерации БПФ на выходах (m -1)-ых разрядов первого 19 и второго 20 регистров итераций устанавливается

1", которая через (k + 1)-ые входы первого 15 и второго 16 коммутаторов 25 поступает на информационные входы третьего 13 и четвертого 14 триггеров и блокирует входы первого 19 и второго 20 регистров итераций. Сигналы переполнения с выходов первого 30

21 л второго 22 счетчиков операндов

"перебрасывают" триггеры 13 и 14 в состояние логйческой "1" и начинается дополнительная итерация распаковки массивов. При этом сигнал "1"

3 разрешает прохождение серии импульсов с выхода первого триго ера 31 на вторые входы элементов И блоков 17 и 18. Данные серии импульсов через первые 8 (<-1, 2, ...,rn -1) элементов блоков 17 и 18 проходят на первые управляющие входы элементов первого 11 и второго 12 узлов и инвертируют исходный код первых разрядов первого 21 и второго 22 счетчиков операндов (инвертирование осуществляется сигналом "1" на выходе первого 31 триггера во время формирования кода адреса второго операнды из пары операндов А и В).

Сигналы с выходов разрядов (rn, и +

+1, ..., n -2,n -1) счетчиков 21 и 22 не инвертируются, поскольку

"нулевое" состояние разрядов (m, rn+

+ 1, ..., h -2,> -1) первого 19 и второго 20 регистров итераций блокируют элементы (le rn +1, n -2, и-1) блоков 17 и 18, с выходов которых на управляющие входы соответствующих элементов узлов 11 и 12 также поступает сигнал "0". Коды адресов обращения к первому и второму блокам

3 и 4 при выполнении распаковки приведены в таблице. Сигнал "1" с выхода четвертого триггера 14 поступает на второй управляющий вход

АБ 2, выполняющий элементарное преобразование вида.

Элемент ИЛИ 29, первый 24 и второй 25 элементы ИЛИ-НЕ предназначены для формирования сигналов запрещения обращения первого и второго блоков

3 и 4 при записи информации из

"обнуленных" выходных регистров АБ 2 в блоки 3 и 4 на месте первой пары операндов во время выполнения первой итерации БПФ. оо ооо ооо оо оооо оо оо о

О оо оо о оо т е о оо оо оо о оо о о о оо о» оо о оо оо оо со о

I o) о оо оо с о

° ° оо о» со оо ооо оо

It

1 со

Ю оо!

I Ю>

1 о оо о о

D оо о оо оо оо оOD о о

D о оо ооо оо оо о» оо со о о о о оо оо о о ооо оо о» оо ооо оо о

D о оо оо оо о» оо оо о» о

D о оо о оо

1 I3 з lt о о о оо оо оо оо оо о оо т- оо ооо оо о

D о. оо оо оо оо оо о оо оо о оо оо оо оо

L о оо ом

$I 8

I C фч IC

46 4

12I)752

38

В

L ь хаю о 8

3 t4

4 1 3 II I

1211752 оо сч

»о о о

-о о о

-о о

»о о»

-о о о

-о о}

»о

«о о»

»о оо»

И

If о оо» о»

3 о о» о оо» оо

»о

» о» о» о

-о о— оо о оо о» о о» о о» оо оо оо оо оо оо оgo оо

° » о оо оо

»» о оо оо о оо о о о оо оо

l.3 о

-.Ю, о|, о » о». о»

-о ооо

»о о о» о»

»о о-о

-о о о оо»о о

»» оо о оо

»

»» оо оо о»

1211752

»о

«о

«о о»

» .-о »о о» о»

«о

» о) о» о о» о о» оо»

° о о-о ц оо-. о-о ооо о о о» оо оо о» со о о

go оо

»»

yi г o

1211752

Заказ 642/54

Тираж 673

Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Составитель А. Баранов

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