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

 

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

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

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

РЕСПУБЛИК

09) (11) ЗЫ1) G 06 F. 15/332

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ |

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

К АВТ0РСКОМУ СВИДЕТЕЛЬСТВУ (21) 3586975/24-24 (22) 29.04.83 (46) 15. 11.84.Бюл. В 42 (72) Ю.Г.Древс, A.Н.Баранов. и А.В. Казанский (71) Московский ордена Трудового

Красного Знамени инженерно-физический институт (53) 681.3(088.8)

/ (56) 1. Авторское свидетельство СССР .

N 913392, кл. С 06 F 15/332, 1980.

2. Казанский А.В. Анализ структур и функциональных схем процессоров быстрого преобразования Фурье. В сб.:

"Вопросы проектирования и эксплуатации АСУ и управляющих вычислительных комплексов". М., Знергоиздат, 1982, с. 90 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее два коммутатора, два арифметических блока, блок памяти и блок управления, состоящий из тактового генератора, счетчика .циклов, счетчика итераций и двух дешифраторов, причем выход тактового генератора в блоке управления подключен к входу счетчика .циклов, выход переполнения счетчика циклов подключен к входу счетчика итераций, информационные выходы счетчика циклов и счетчика инетарций подключены соответственно к первым и вторым входам первого и второго дешифраторов, выход первого дешифратора в блоке управления является первым выходом блока управления и подключен к адресному входу блока памяти, первый и второй выходы второго дешифратора в блоке управления явля-, ются вторым и третьим выходами блока управления и подключены к управляющим входам первого и второго коммутаторов соответственно, информационный вход и выход блока памяти являются входом и выходом устройства, выход блока памяти подключен к информационному входу первого коммутатора, выход второго коммутатора подключен к информационному входу блока памяти, отличающееся тем, что, с целью упрощения устройства и повышения его быстродействия, первый арифметический блок содержит четыре входных регистра, два сумматора, два

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

ЪФ коммутатора, выход первого входного регистра в первом арифметическом блоке соединен с первым входом первого сумматора и с суммирующим входом первого вычитателя, выход второго входного регистра в первом арифметическом блоке соединен с первым входом второго сумматора и суммирующим входом второго вычитателя, выход третьего входного регистра в первом арифметическом блоке соединен с вторым входом первого сумматора и с вычитающим входом первого вычитателя, выход фв четвертого входного регистра в первом арифметическом блоке соединен с вторым входом второго сумматора и. с вычитающим входом второго вычитателя, выходы первого сумматора и первого вычитателя в первом арифметическом блоке соединены с соответствую124323

1 щими информационными входами первого коммутатора в этом блоке, выходы второго сумматора и второго вычитателя в первом арифметическом блоке соединены с соответствующими информационными входами BTopoFO коммутатора в этом блоке, первый и второй выходы первого коммутатора в первом арифметическом блоке подключены к информационным входам первого и второго выходных регистров этого блока, первый и второй выходы второго коммутатора в первом арифметическом блоке, подключены к информационным входам третьего и четвертого выходных регистров этого блока, вьиоды всех выходных регистров первого арифмети-. ческого блока образуют его выход и подключены к первому информационному входу второго коммутатора, второй арифметический блок содержит четыре входных регистра, два сумматора, два вычитателя и четыре выходных регистра, причем информационные входы всех входных регистров второго арифметического блока образуют его информационный вход и подключены к второму выходу первого коммутатора, выход первого входного регистра во втором арифметическом блоке соединен с первым входом первого сумматора и суммирующим входом первого вычитarena, выход второго входного регистра so втором арифметичесхом блоке соединен с первым входом второго сумматора и с суммирующим входом второго вычитателя, выход третьего входного регистра во втором арифметическом блоке соединен с вторым входом второго сумматора и с вычитйющнм входом второго вычитателя, выход четвертого входного регистра во втором арифмети" ческом блоке соединен с вторым входом первого сумматора и с вычитающнм входом первого вычитателя, выходы первого и второго сумматоров, а также первого и второго вычитателей во втором арифметическом блоке соединены с информационными входами соответствующих выходных регистров этого блока, выходы которьи образуют выход второго арифметического блока и подключены к второму информационному входу второго коммутатора, блок управления содержит элемент ИЛИ и элемент И, причем выход счетчика итераций в блоке управления поразрядно подключен к входам элемента ИЛИ, выход которого, а также выход тактового генератора подключены к входам элемента И, третий выход второго дешифратора является четвертым выходом блока управления и подключен к управляющим входам первого и второго коммутаторов в первом арифметическом блоке, выход тактового генератора является пятым выходом блока управления и подключен к тактовым входам всех входных и выходных регистров в первом арифметическом блоке, выход элемента И является шестым вьиодом блока управления и подключен к тактовым входам всех входных и выходных регистров во втором арифметическом блоке °

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

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

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

Наиболее близким к изобретению является устройство для вычисления

ВПФ, содержащее два арифметических блока, блок памяти, блок управления и два коммутатора, причем первый и второй выходы первого коммутатора соединены с информационными входами соответственно первого и второго арифметических блоков, информацнон3 1124 ные выходы которых подключены соответственно к первому и второму входам второго коммутатора, выход которого соединен с информационным входом блока памяти, информационный выход которого подключен к входу первого коммутатора, первый выход блока управления подключен к адресному входу блока памяти, второй выход блока управления соединен с. тактовыми 10 входами арифметических блоков, третий и четвертый выходы блока управления соединены с управляющими входами соответственно первого и второго . коммутаторов, информационный вход и выход блока памяти является соответственно информационным входом и выходом устройства. Данное устройство также выполняет БПФ по упрощенному адгоритму. (2) .

Однако арифметические блоки, хотя и учитывают специфические особенности коэффициентов применяемого упрощения алгоритма, выполнены по универсальной схеме, позволяющей осущест- 25 влять любую базовую операцию упрощенного алгоритма БПФ и поэтому имеют сложную структуру. Устройство выполняет упрощенный алгоритм с параметром ц =«/4, но в ряде случаев может бытд допущена и более низкая методическая погрешность вычислений. Более того, применение эффективного по . быстродействию сглаживания в частотной области результатов упрощенных алгоритмов БПФ позволяет значитель35 но повысить методическую точность .вычисления спектра упрощенными методами и, тем самым, определяют рацио- нальность применения упрощенных алл 40 горитмов с параметром It =и/2 (вместо

К=(/4) с учетом затрат аппаратуры и быстродействия.

Цель изобретения — упрощение устройства и повышение его быстродейст- 45 вия е . Поставленная цепь достигается тем, что в устройстве для вычисления

БПФ, содержащем два коммутатора, два арифметических блока, блок памяти 50 и блок управления, еостоящий из тактового генератора, счетчика циклов, счетчика итераций и двух дешифраторов, причем выход тактового генератора в блоке управления подключена 55 к входу счетчика циклов, выход переполнения четчика циклов подключен к входу счетчика итераций, информа323 4 ционные выходы счетчика циклов и счетчика итераций подключены соответственно к первым и вторым входам первого и второго дешифраторов, выход первого дешифратора в блоке управления является первым выходом блока управления и подключен к адресному входу блока памяти, первый и второй выходы второго дешифратора в блоке управления являются вторым и третьим выходами блока управления и подключены к управляющим входам первого и второго кслм„гаторов соответ-. ственно, информационный вход и выход блока памяти являются входом и выходом устройства, выход блока памяти подключен к информационному входу первого коммутатора, выход второго коммутатора подключен к информационному входу блока памяти, первый арифметический блок содержит четыре входных регистра, два сумматора, два вычитателя, два коммутатора и четыре выходных регистра, причем информационные входы всех входных регистров первого арифметического блока образуют его информационный. вход и подключены к первому выходу первого коммутатора, выход первого входного регистра в первом арифметическом блоке соединен с первым входом первого сумматора и с суммирующим входом первого вычитателя, выход второго входного регистра в первом арифметическом блоке соединен с первым входом второго сумматора и с суммирующим входом второго вычитателя, выход третьего входного регистра в первом арифметическом блоке соединен с вторым входом первого сумматора и с вычитающим входом первого вычитателя, выход четвертого входного регистра в первом арифметическом блоке соединен с вторым входом второго сумматора и с вычитающим входом второго вычитателя, выходы первого сумматора и первого вычитателя в первом арифметическом блоке соединены с соответствующими инфсриационными входами первого коммутатора в этом блоке, выходы второго сумматора и второго вычитателя в первом арнфметическом блоке соединены с соответствующими информационными входами второго коммутатора в этом блоке, первый и второй выходы первого коммутатора в первом арифметическом блоке подключены к информационным входам

1124323

5 первого и второго выходных регист" ров. этого блока, первый и второй выходы второго коммутатора в первом арифметическом блоке подключены к . информационным входам третьего и чет- 5 вертого выходных регистров этого блока, выходы всех выходных,регистров первого арифметического блока образуют его.выход и подключены к первому информационному входу второ- 10 го коммутатора, второй арифметический блок содержит четыре . входных регистра, два,сумматора, два вычитателя и четыре выходных регистра, причем информационные входы всех 15 входных регистров второго арифметического блока образуют его информа-. ционный вход и подключены к .второму выходу. первого коммутатора, выход ( первого входного регистра во втором арифметическом блоке соединен с первым входом первого сумматора и суммирующим входом первого вычитателя, выход второго входного регистра во втором арифметическом блоке соединен с первым входом второго сумматора и с суммирующим входом второго вычита-. теля, выход третьего входного регистра во втором арифметическом блоке соединен с вторым входом второго сум-ЗО матора и с вычитающим входом второго вычитателя, выход четвертого входного регистра во втором арифметическом блоке соединен с вторым входом первого сумматора и с вычитающим вХодом 35 первого вычитателя, выходы первого и второго сумматоров, а также первого и второго вычитателей во втором арифметическом блоке соединены с ин-. формационными входами соответствую- 40 щих выходных регистров этого блока, выходы которых образуют выход второго арифметического блока и подключены к второму информационному входу второго коммутатора, блок управления . содержит элемент ИЛИ и элемент И, причем выход счетчика итераций в блоке управления поразрядно подключен к входам элемента ИЛИ, выход которого, а также выход тактового генератора подключены к входам элемента И, третий выход второго дешифратора является четвертым выходом блока управ-. ления и подключен к управляющим входам первого и второго коммутаторов 55 в первом арифметическом блоке, выход тактового генератора является пятым выходом блока управления и подключен к тактовым входам всех входных и выходных регистров в. первом арифметическом блоке, выход элемента И является шестым выходом блока управления и подключен к тактовым входам всех входных и выходных регистров .во втором арифметическом блоке.

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

Устройство содержит коммутатор l, арифметические блоки 2 и 3,, коммутатор 4, блок 5 оперативной памяти, блок 6 управления.

Блок 6 управления содержит тактовый генератор 7, счетчик 8. циклов, счетчик 9 итераций, элемент ИЛИ 10, дешифратор 11 адреса памяти, дешиф" ратор 12 адреса коммутаторов, элемент И 13., Арифметический блок 2 содержитвходные регистры 14 — 17, сумматоры

18 и 19, вычитатели 20 и 21, коммутаторы 22 и 23, выходные регистры

24 — 27.

Арифметический блок 3 содержит входные регистры 28 — 31, вычитатель

32, сумматоры 33 и 34, вычитатель 35, выходные регистры 36 — 39. Счетчик 8 циклов блока 6 управления имеет разрядность m=log N-1, а счетчик итераций — m=log

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

Устройство работает следующим образом.

Реализуется упрощенный алгоритм

БПФ с параметром а6 =П/2 с замещением -1 . г4„|,i

V() t х(в) exp j .— (j k =o ц -1

n=-о 2 1. " ) чаются соответственно значения разности вещественных и мнимых частей, т.е. R

Hs выходов дешифратора 12 адреса коммутаторов блока 6 управления, коммутаторы 22 и 23.осуществляют засыпку результатов арифметических действий

1О в соответствующие выходные регистры

24-27, в которых хранятся соответственно реальная и мнимая части соответственно первого и второго операнда результата базовой операции. Та15 ким образом, Осуществляется базовая операция первого ((II,õ ° 1, ).1(1х 1„т, (ReX-R,v} >j (I X - ? ) или третьего типов.,(R,Õ-R,Ч). (?Х-I„Y), ; (QeX+ Rey)+j(I111X y I V) Аналогичным образом находится результат базовой операции второго типа. Реальные и мнимые части первого и второго операндов поступают соответственно во входные регистры 28-31 арифметического блока 3. В результате, на выходе вычитателя 32 находится К4Х-К 71 на выходе сумматора 33

Х+ Я У, на выходе сумматора 34

ItzX+I«Y, а на выходе вычитателя 35—

1 Х-11еу. Далее результаты записываются в выходной регистр 36 . По окончании вычислений базовых операций результаты переписываются через коммутатор 4 в блок 5 памяти по тем же адресам, по которым они быпи считаны. Вычисления прекращаются по выполнении.log N итераций.

Блок 6 управления работает следующим образом.

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

Импульс переполнения с выхода этого счетчика 8 циклов поступает на тактовый вход счетчика 9 итераций, код . которого определяет номер текущей итерации. Таким образом, коды счетчи ка циклов и счетчика итераций полностью определяют номер базовой операции алгоритма.БПФ. Эти коды дешиф7 1124323 где X(k) — результат БПФ;

X(n) — последовательность входных отсчетов;

Aj — ближайшее целое к А.

Анализ структуры. алгоритма БПФ с параметром показывает, что в базовой операции, которйя записывается следующим образом:

:". Х=Х+Y W

1 (=Х- (° %1 где Х, У и Х, У вЂ” соответственно входные и выходные операнды;

W — - поворачивающие множители, коэффициенты 111 могут принимать толька при разных значениях "1н1

11 11

1 1 Ф

-1 . При этом весь этот набор коэффициентов реализуется на всех итера- 20 циях алгоритма БПФ, кроме начальной с номером "0".

Устройство реализует описанный алгоритм, при этом арифметический блок 2 реализует базовые операции 25 первого и третьего типа (с коэффициентом " 1" и "-1"), а арифметический блок 3 выполняет базовую операцию только второго типа(умножение íà j ).

Работа предлагаемого устройства

30 осуществляется следующим образом.

По адресам, формируемым блоком 6 .управления, необходимые. для каждой конкретной базовой операции пары комплексчых операндов через коммута- З5 тор 1, считываются во входные ре".истры 14-17 и 28-31 соответственно арифметических блоков 2 и 3. При этом во входные регистры 14 и 15 считываются соответственно реальная и мнимая час- 0 ти первого комплексного операнда базовой операции первого или.третьего типа, а во входные регистры 16 и 17 соответственно реальная и мнимая части второго комплексного операнда, не-45 обходимого для базовых операции этого типа. Во входные регистры 28, 29 и

30, 31 арифметического блока 3 записываются соответственно реальные и мнимые части соответственно первого и второго операндов,"используемых в базовой операции второго типа. На выходе сумматора 18 арифметического блока 2 находится величина R Х+К 7 е е где R — вещественная часть числа, на выходе сумматора 19 — I X+I Y

111 М где I> мнимая часть. Аналогично на выходах вычитателей 20 и 21 полу9 .11 руются дещифраторами 11 и 32 адреса, которые определяют соответственно адреса операндов,в блоке 5 памяти и коммутаторов 1, 4 и 22, 23. Непосредственно с выхода генератора 7 блока

6 управления тактовые сигналы поступают на тактовые входы входных и выходных регистров арифметического блока 2, синхронизируя прием и выдачу информации для этого блока. Если код счетчика 9 итераций нулевой, то на выходе элемента ИЛИ присутствует уро"вень логического нуля, и тактовые. импульсы не проходят иа тактовые входы входных и выходных регистров арифметического блока 3. Таким образом, арифметический блок 3 на начальной итерации не функционирует.

24323 10

Базовых итераций второго типа ровно столько, сколько базовых операций первого и третьего Фнпа вместе взятых. Значит арифметические блоки работают на.кахдой итерации без ожиданняе

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

1р БПФ позволит существенно упростить конструкцию устройства (практически в 2-4 раза), поскольку вместо двух универсальных арифметических блоков используются два разнотнпных, cne>5 . циализированных аналогичных блока, или при равных с прототипом затратах оборудования в такое хе число раз повысить быстродействие.

1124323

1124323

Составитель В;Байков

Редактор Л.Алексеенко Техред А.Бабинец Корректор С.черни т

Заказ 8282/39 Тираж 698 Подписное

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

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

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