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

 

1. АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее три входных регистра , умножитель, два регистра, два коммутатора, сумматор, четыре выходных регистра и блок синхронизации , отличающееся тем, что, с целью повьппения быстродействия , информационные выходы первого и второго входных регистров подключены соответственно к первому информационному входу первого комму татора и первому входу умножителя, выход которого подключен к информационному входу первого регистра, информационный выход которого подключен к информационному входу второго регистра, информационный выход которого подключен к первому входу сумматора, выход которого подключен к первому информационному входу второго коммутатора и информационным входам первого, второго, третьего и четвертого выходных регистров, информационные выходы которых объединены и йодключены к второму информационному входу второго коммутатора и второму информационному входу первого коммутатора, выход которого подключен к второму входу сумматора, второй вход умножителя подключен к информационному выходу третьего входного регистра, информационный вход которого является парвьм информационным входом устройства, вторым информационным входом которого являются информационные входы первого и второго входных регистров, первый выход блока синхронизации подключен к тактовым входам первого и второго с S регистров и третьего входного регистра , второй и третий выходы бло (Л ка синхронизации подключены к тактовым входам соответственно первого и второго входных регистров, четвертый и пятый выходы блока синхронизации подключены к управляющим входам соответственно первого и второго коммутаторов, шестой выход блока синхронизации подключен к входу синхронизации сумматора, седьмой, восьмой , девятый и десятый выходы блока синхронизации подключены к входам синхронизации приема соответственно/ первого, второго, третьего и четвертого выходных регистров, входы синхронизации выдачи которых подключены соответственно к одиннадцатому, двенадцатому, тринадцатому и четырнадцатому выходам блока синхронизации , вькод второго коммутатора являг ется информационным выходом устройства . 2. Устройство по П.1, о т л и ч ающе еся тем, что блок синхронизации содержит узел постоянной

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

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

РЕСПУБЛИК (19) (11) 4(5Р С 06 F 15/332

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTMA

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3655320/24-24 (22) 24.10.83 (46) 07.04.85. Бюл. 9 13 (72) Ю.М.Зорин, Ю.С.Каневский, В,И.Лозинский и И-.Ю.Потехин (71) Киевский ордена Ленина политехнический институт им. 50-летия

Великой Октябрьской социалистической революции (53) 68 1,32(088,8) (56) 1. Авторское свидетельство СССР

Р 399859, кл. С 06 F 7/38, 1972.

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

М- 736113, кл. С 06 F 15/332, 1976 (прототип) (54) (57) 1. АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ЛЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ

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

2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок синхронизации содержит узел постоянной

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

Ф „

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

Однако это устройство требует большого объема оборудования, t5

Наиболее близким по технической сущности к изобретению является устройство дпя быстрого преобразования Фурье, содержащее четыре входных регистра чисел, два входных ре- _#_ гистра весового коэффициента, множительный блок, два регистра слагаемых, сумматор, два коммутатора, четыре регистра результатов и устройство управления (2), 25

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

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

Поставленная цель достигается тем, что в арифметическом устройстве для быстрого преобразования

Фурье, содержащем три входных регистра, умножитель, два регистра, два коммутатора, сумматор, четыре выходких регистра и блок синхронизации, информационные выходы первого и втор-ro входных регистров подключены . ответственно к первому информационному входу первого коммутатора и первому входу умножителя, выход которого подключен к информационному входу первого регистра, информационный выход которого подключен к информационному входу второго регистра, информационный выход которого подключен к первому входу сумматора, выход которого подключен к первому информационному входу второго коммутатора и информационным входам первого, второго, третьего и четвертого выходных регистров, информационные выходы которых объединены и подключе ны к второму информационному входу второго коммутатора и второму информационному входу первого коммутатора, выход которого подключен к вто. рому входу сумматора, второй вход умножителя — к информационному выходу третьего входного регистра, информационный вход которого является первым информационным входом устройства, вторым информационным входом которого являются информационные входы первого и второго входных ре149275

Входное слово Выходное слово

I 0 0

0 0 0

0 0

0 1 0

0 t 1

1 0 0

1 0 1

1 1 0

1 1 1

0 0 0 0

1 1 1 0

0 0 1 0

0 0 0 1

0 1 О 0

0 1 0 1

1 0 0 0

0 1 0

0 0 0 0

0 0 1

0 1 0 0

0 0 0

1 0 1 0

1 0 0

0 0 0 1

0 1 0

0 0 0 0

0 0 1

0 0 1 0

0 1 1 0

0 0 0

1 0 0 0

0 0 1 0 гистров, первый выход блока синхронизации подключен к тактовым входам

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

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

t0

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

На фиг.1 представлена структурная схема предлагаемого устройства, на фиг.2 — структурная схема одного из возможных вариантов построения блока синхронизации, на фиг.З вЂ” временная диаграмма, иллюстрирующая работу предлагаемого устройства.

Арифметическое устройство для быстрого преобразования Фурье содержит (фиг.1) два входных регистра 1 и 2 чисел1 входной регистр 3 весово. го коэффициента, умножитель 4, регистры 5 и 6, сумматор 7, коммутатор 8 (слагаемых), выходные регистры 9-12 (результатов), выходной коммутатор 13 и блок 14 синхронизации.

Последний содержит (фиг.2) генератор

15 тактовых импульсов, счетчик 16 тактов, дешифратор 17, узел 18 постоянной памяти и элемент ИЛИ 19.

Таблица кодировки постоянного запоминающего устройства имеет следующий вид.

1149275

Устройство выполняет базовую операцию алгоритма быстрого преобразования Фурье по основанию 2: ; ° В;+p д ; еЬ - С фl

11еС; Е W -1 С, 11еg где В;, C, — исходные отсчеты, А,, А;„ — преобразованные отсчеты; 1 hl — весовой коэффициент; 2è.

-1 —

N — количество отсчетов в исходном массиве, е — действительная часть;

Е, — мнимая часть числа.

Рассмотрим работу устройства при выполнении базовой операции. Будем считать, что прием информации в ре25 гистры осуществляется в момент прихода заднего фронта синхроимпульса.

На временной диаграмме показана работа устройства по тактам, Импульсы, показанные незаштрихованными прямоугольниками, никакой смысловой нагрузки не несут, они подаются в промежуток времени, необходимый для загрузки устройства. Заштрихованные прямоугольники показывают 35 импульсы, необходимые для работы устройства. Первые пять тактов являются холостыми, т.е. во время этих тактов полезная информация на выход не подается, но в дальнейшем вначале каждо- 40 го такта при непрерывном поступлении данных на вход устройства на выходе появляются соответствующие результаты, цикл работы устройства составляет четыре такта. В конце первого такта по сигналу с выхода блока 14 синхронизации во входной регистр 1 чисел принимается действительная часть R С;исходного отсчета

С;, во входной регистр весового коэф-И фициента 3 — действительная часть

Н W весового коэффициента 4

Во втором такте выполняется умножение в умножителе 4 и произведение

R С R

R,С, Ве 4, и в регистр 3 — мнимая часть Е„, Ъ весового коэффициента Мl, во входной регистр 1 чисел по сигналу с блока 14 принимается мнимая часть Е C„ исходного отсчета С;.

В четвертом такте в умножителе

4 выполняется умножение, и произведе ние I С„ I Ф по сигналу из блока

14 принимается в регистр 5 слагаемых, по этому же сигналу в регистр 6 принимается произведение R C; Е Vl, а во входной регистр 3 — действительная часть к A весового коэффициента

Ч . По сигналу из блока 14 во входной регистр 2 принимается мнимая часть 1 В; исходного отсчета В„.

Коммутатор 8 по сигналу из блока 14 подключает к входу сумматора 7 выход входного регистра 2 чисел. Сумматор

7 по сигналам из блока 14 выполняет операцию сложения в первой половине четвертого такта, а операцию вычитания — во второй половине. Соответстве cy a Р В + R С Ке14 по сигнал. из блока 14 принимается в ре. гистр 9 в середине четвертого такта, а разность R В,,— R С; R W — по сигналу из блока 1 в конце четвертого такта в регистр 10.

В пятом такте в умножителе 4 выполняется умножение, и произведение

I Ñ R W по сигналу из блока 14 принимается в регистр 5,,произведение Е„„С;. I W по этому же сигналу принимается в регистр 6, а во входной регистр 3 — действительная часть

R ф" . Во входной регистр 1 налу из блока 14 принимается действительная часть R C„ „, следующего исходного отсчета С„ <. Коммутатор 8 по сигналу иэ блока 14 подключает к входу сумматора 7 выход входного регистра 2. Сумматор 7 по сигналам из блока 14 выполняет операцию сложения в первой полонине пятого такта и операцию вычитания — во второй половине. Соответственно, в середине пятого такта сумма Х В; + КеС; I W по сигналу иэ блока 14 принимается в регистр 11, а в конце пятого такта

1149275 разность I Â; — R С, I W по сигналу из блока 14 принимается и регистр

12.

В шестом такте в умножителе 4 выполняется умножение и проиэнедение Я,С„, Кр W по сигналу из блока 14 принимается в регистр 5, в регистр 6 по этому сигналу принимается произведение 1,„С; Rgw, а в регистр 3 — мнимая часть 1„W весового коэффициента. Во второй регистр 2 по сигналу из блока 14 принимается действительная часть R B;, исходного отсчета В;„. Коммутатор 8 по сигналу из блока 14 подключает к выходу сумматора 7 объединенный выход регистров 9-12 результатов ° Сумматор 7 по сигналам из блока 14 выполняет операцию вычитания в первой половине шестого такта и операцию сложения — во второй. В первой половине шестого такта по сигналу из блока 14 иэ регистра 9 выдается сумма К В; +К С;. К W, и после выполнения вычитания на выходе сумматора появляется действительная часть преобразованного отсчета КеА,=К В;+

+КеС Ке!4 I C;"Ii W KoTop по сигналу иэ блока 14 коммутатор 13 по. дает на выход устройстна и которая по сигналу иэ блока 14 запишется в регистр 9. Последняя запись не является необходимой для функционирования устройства, Она введена с целью упрощения блока 14. Во второй половине шестого такта по сигналу иэ блока 14 иэ регистра 10 выдается разность R В, — R C, .Ре 9I и н конце такта по сигналу из блоха 14 в регистр 10 принимается сумма R А.

& 141

=RB-RC RW +I С; IW

В седьмом тахте в умножителе 4 выполняется умножение, и произведение К С,ц1,„ Ъ" по сигналу из блока

14 принимается в регистр 5, в регистр 6 по этому же сигналу — произведение R С;„ К ф", а но входной регистр 3 — мнимая часть W весового коэффициента W" . Во входной регистр 1 по сигналу иэ блока 14 принимается мнимая часть I С;,, исходного отсчета С„, . Коммутатор 8 по сигналу из блока 14 подключает к выходу сумматора 7 объединенный выход регистров 9-12 результатов.

Сумматор 7 по сигналам из блока 14 выполняет операцию сложения и операцию вычитания соответственно в ервой и второй полонинах седьмого такта. В первой половине седьмого такта по сигналу из блока 14 иэ регистра 11 выдается сумма I B,+

+КеС;.? У, и после выполнения сложения на выходе сумматора появляется мнимая часть преобразованного от+Ко С !1 + которую по сигналу иэ блока 14 коммутатор 13 подает на выход устройства и которая по сигналу из блока 14 запишется в регистр 11.

Последняя запись не является необходимой для функционирования устройства, она введена с целью упрощения блока 14.

Во второй половине седьмого такта по сигналу из блока 14 иэ регистра 2 выдается разность В -R С"! ф

ll1 q Q « tel 1 и в конце такта по сигналу из блока

14 в регистр 12 принимается разность %3 ЗеС а С R,W «-! A

В восьмом такте н умножителе 4 выполняется умножение, и произведение С;„1,„ W " по сигналу иэ блока

14 поднимается в регистр 5, в регистр 6 по этому же сигналу принимается произведение I С,„ I W, а

ЗО в регистр 3 — действительная часть

К Ф " несовогo коэффициента A . Во входной регистр 2 по сигналу из блока 14 принимается мнимая часть 8;„ исходного отсчета В,, . Коммутатор 8 д по сигналу иэ блока 14 подключает к входу сумматора 7 выход входного регистра 2 чисел.. Сумматор 7 выполняет операции сложения и вычитания в первой и второй половинах такта

40 соответственно. В первой половине восьмого такта по сигналу из блока

14 (по заднему фронту) в регистр 9 принимается сумма К В, +В С ° Re В", е « е м е из регистра 10 на выход устройства

45 по сигналу иэ блока 14 выдается действительная часть R A Коммутатор

13 по сигналу иэ блока 14 пропускает ее на выход устройства. Во второй половине восьмого такта по сигна. о лу из блока 14 в регистр 10 принимается разность R В,„-РеС;„R w "

В первой половине девятого такта по сигналу иэ блока 14 в регистр

11 принимается сумма 1„,В;К С;„К И по сигналу из блока 14 из регистра

12 на выход устройства выдается мни мая часть I А;,<преобразованного отсчета А;„и по сигналу иэ блока 14

11492?5

1О во второй половине в регистр 12 принимается разность.

Работа остальных элементов устройства аналогична рассмотренной для пятого такта.

Далее работа всего устройства аналогична.

Таким образом, по сравнению с известным предлагаемое устройство более быстродейственно, оно имеет четыре такта работы при непрерывном

5 поступлении данных (такт работы устройства есть такт работы умножителя), в то время как известное устройство имеет шесть тактов работы (такт работы устройства есть такт работы умножителя), 1149275 фиг. 2

1149275

2 J Ф 8 К 7 8 Я 10

I 8е 8(1 югС7 1 8е87 i Impair rl 18е Се,е

Е2Х 8 а ру 8«r

Ре8 r

Im 8r

O и "1 дуй" Imb" eW"r AW"I Im И"

Рей М Ыс Iver InCiimeг I 8Щ ееД; Щ ее<, /,м" 1т б ее(е

r rvi еев .I Рею .е б юю < °

Ре wi.1

ХЕД ФСЕ <СИ 8Е4i 8e8i АТЕЕi,„РЕiд r geAi,g

fe8i+leCi eе И"

pe8r r ReliнХей " 8eAI,8

e8r -4Х(",ее И" Рей;;,, 8е8е. 8ег(.,eever

Im8i ee<(ЪИ" Im>i . In i eel r Im A" !

ЮиЯ1/

rm8, РЕГ,У И I I

t 1

Ar8I 2

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

Техред Т.Фанта Корректор В.Бутяга

Редактор В, Данко

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

Заказ 1895/35 Тираж 710 Подлисное

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

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