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

 

Изобретение относится к области вычислительной техники и предназначено для спектрального анализа электрически сигналов, представленных в цифровой форме. Цель изобретения - повышение быстродействия. Устройство содержит элемент И-ИЛИ 1, входной коммутатор 2, блок памяти 3, выходной коммутатор 4,: арифметический блок 5, дешифратор адреса 6, дешифраторы чте-. ния 7,8, дешифратрры записи 9, 10, блок элементов ИЛИ 11,- блок коррекции 12, коммутатор адреса 13, блок элементов И 14, коммутатор адреса 15, элемент И 16, триггер режима 17, блоки элементов И-ИЛИ 18,19, регистры 20- 23, триггеры 24, 25, дешифратор адреса 26, элемент И-ИЛИ 27, счетчик операндов 28, счетчик итераций 29, дешифратор адреса 30, блок постоянной па- g мя ти 31. 5 ил . « М

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

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

РЕСПУБЛИК

11777 A1 (19) (11) ш 4 С 06 F 15/332

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

Н ASTOPCHOMY СВИДЕТЕЛЬСТВУ

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

f10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4185916/24-24 (22) 23.01.87 (46) 23.07.88. Бюл, У 27 (72) Г.В.Пивин, Ю.Н.Иртег ов, В.Б. Климов, Н.В.Полушкина, А.Ю.Скуратов, А.В.Солодилов и Ю.П.Щинов (53) 681.32 (088.8) (56) Авторское свидетельство СССР

Н 1056207, кл. G 06 F 15/332) 1983 °

Автометрия, 1973, 9 3, с. 32-38, (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАИИЯ ФУРЪЕ (57) Изобретение относится к области вычислительной техники и предназначено для спектрального анализа электрически сигналов, представленных в цифр ов ой форме. Цел ь из об р ет ения — и овышение быстродействия. Устройство содержит элемент И-ИЛИ 1, входной коммутатор 2, блок памяти 3, выходной коммутатор 4, арифметический блок 5, дешифратор адреса 6, дешифраторы чте-, ния 7,8, дешифратрры записи 9, 10, блок элементов ИЛИ 11, блок коррекции

12, коммутатор адреса 13, блок элементов И 14, коммутатбр адреса 15, элемент И 16, триггер режима t7, блоки элементов И-ИЛИ 18,19, регистры 2023, триггеры 24, 25, дешифратор адреса 26, элемент И-ИЛИ 27, счетчик операндов 28, счетчик итераций 29, дешифратор адреса 30, блок постоянной па" ф мяти 31. 5 ил °

14 11 777

1де k - ")29/N;

В

Ь вЂ” комплексные числа.

Согласно применяемого алгоритма

ВПФ вычисления проводятся за P =

log N итераций. На каждой итерации

2 выполняются N/2 базовых операций длит ельностью Т о

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

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

На фиг. 1 представлена функциональ, ная схема устройства на фиг. 2 — вре10

,менные диаграммы работы устройства; на фиг. 3 — временные диаграммы уп| равления первым коммутатором адреса", на фиг. 4 — временные диаграммы уп:,равления вторым коммутатором адреса; на фиг. 5 — схема блока. коррекции.

Устройство содержит элемент И-ИЛИ f входной коммутатор 2, блок 3 па,мяти, выходной коммутатор 4, арифметический блок 5, дешифратор 6 адреса, 20, два дешифратора 7 и 8 чтения, два де,шифратора записи 9 и 10, блок 11 эле ментов ИЛИ, блок 12 коррекции, комму татор 13 адреса, блок 14 элементов И, коммутатор 15 адреса, элемент И 16, 25 триггер 17 режима, блок элементов 18

ИЛИ, блок 19 элементов И-ИЛИ, ре° ° гистры 20-23, триггеры 24 и 25, дефратор 26 адреса, элемент И-ИЛИ 27, четчик 28 операндов, счетчик 29 30

° ° тераций, дешифратор 30 адреса, лок 31 постоянной памяти.

Блок 12 (фиг. 4) содержит элемен гы И 32 и 33, элементы ИЛИ 34, 35, лементы И-НЕ 36-39, элемент НЕ 40, григгера 41-43 ..

В устройстве реализуется алгоритм ПФ с прореживанием по времени с замещением, по отношению 2, с объеМом выборки N, двоичной инверсией на 4п выходе.

Базовая операция такого алгоритма, Состоит в том, что входных числа А, И В объединяются для получения выходс

Ных чисел Х и У следующим образом: с в j(Х,.=A,. + ВР,.;

° 1

Y(A; — В(У

В соответствии с временной диаграммой (фиг. 3) в устройстве в каждом такте одйовременно выполняются следующие операции: обращение к двум модулям блока памяти с чтением пары операндов А; и В;, выполнение базо

1 вой операции над операндами А; „и

В;, и запись результатов Х ° и

1-

У ° от выполнения базовой операции

Ф над операндами А;, и В; в два других модуля блока памяти.

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

Тбо Тоьр )

03У где Т„, — время обращения к блоку

Оз ОЗУ с чтением или записью, Т о — время выполнения базовой операции БПФ.

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

В исходном состоянии триггер 17 режима сигналом через вход элемента

ИЛИ устанавливается в единичное состояние (прямой выход) и переводит устройство в режим ввода информации.

При этом входной массив через элемент И-ИЛИ 1, открытый по входу еди ничным сигналом с прямого выхопа триггера 17 режима, поступает на информационный вход входного коммутатора 2. В последнем обеспечивается распределение операндов по модулям блока 3 согласно сигналам управления с выхода дешифратора 9 записи.

Массив входной информации вводится синхронно по.адресам записи, которые формируются последовательно на и-разрядном счетчике 28 операндов, где n = log N. Входные тактовые импульсы поступают на вход счетчика операндов с входа через первый вход элемента И-ИЛИ 27 и блок 12 коррекции (прохождение входных импульсов через блок 12 коррекции не показано) .

С выхода счетчика 28 операндов и-разрядные адреса записи через блок 14 элементов И, открытый по входу.сигналом с прямого выхода триггера 17 режима, и вход блока 11 элементов ИЛИ поступают на вход дешифратора 6 адреса. Последний управляется по входу

1411777 сигналами управления с выхода дешифратора 9 записи. Выбор номера модуля блока 3 памяти, н который. записывается операнд входной информации по соот5 ветствующему адресу записи, осуществляется в дешифраторе 9 записи, на вход которого подаются и-й и второй разряды сформированного адреса запи-, си (и — старший разряд). При этом каждой двухразрядной комбинации указанньм разрядов соответствует единичный сигнал на одном из его четырех выходов, который обеспечивает прохождение на выбранный модуль операндов входной информации с входного коммутатора 2 и соответствующих им (и-2) разрядные адреса записи с дешифратора

6 адреса. При этом код 00 определяет первый модуль блока памяти, 01 — вто- 20 рой, 10 — третий, 11 — четвертый.

По окончании ввода информации через N тактовых импульсов единичный сигнал с вьмода счетчика 28 операндов поступает на вход триггера 17 ре- 25 жима и переводит его в нулевое состояние. При этом единичный сигнал с ин- . версного выхода триггера 17 режима пе". реключает устройство в режим вычисления алгоритма БПФ. 30

Работа устройства на этапе вычисления БПФ осуществляется по тактовым импульсам, поступакицим на вход счетчика 28 операндов с входа устройства через вход элемента 27 и через блок

12 коррекции.

В исходном состоянии счетчик 28 операндов находится в единичном положении, а счетчик 29 итераций в нулевом.

На каждой итерации по тактовым импульсам выполняется N/2 базовьм операций в соответствии с выражением (1).

После подсчета N/2 тактовых импуль.сов на первой итерации счетчик 28 . 45 операндов устанавливается в исходное состояние, а в счетчик 29 итераций добавляется "1". С приходом очередных тактовых импульсов аналогично осуществляется вычисление алго- 50 ритма БПФ на второй итерации. Аналогично производятся вычисления на

Ф всех P итерациях. С приходом последнего N/2 тактового импульса íà P-й итерации на выходе счетчика 29 итераций вырабатывается сигнал, который переводит триггер 17 режима в единичное состояние, т.е. переводит устройство в режим ввода информации.

В соответствии с временной диаграммой, представленной на фнг. 4 (на каждой итерации), с приходом i-ro тактового импульса формируются адреса чтения операндов А; и В;. Адрес чтения операнда А; формируется íà иразрядном счетчике 28 операндов, адрес чтения операнда В; формируется одновременно в дешифраторе 26 адреса путем суммирования по mod 2 адреса чтения операнда А; с закодированным номером соответствующей итерации. Сформированная паря адресов чтения операндов А; и В; поступает одновременно на входы коммутатора 13 адреса и на соответствующие входы регистров 21 и 23.

Управление коммутатором 13 адреса ооеспечивается блоком 18 элементов

И-ИЛИ по временным диаграммам, представленным на фиг. 4. С выхода коммутатора 13 адреса и-разрядные адреса чтения операндов А; и В; монтажным способом распределяются следующим образом. и-й и второй разряды сформированных адресов чтения поступают соответственно на входы дешифраторов

7 и 8, Сформированные таким образом двухразрядные коды определяют номера модулей блока 3 памяти, из которых одновременно производится считывание

I операндов. А; и В; . При этом код 00 определяет первый модуль, код 01 второй модуль, 10 — третий модуль, i 1 — четвертый модуль. На дешифратор

6 адреса соответственно поступают оставшиеся (n-2) -разрядные, коды адресов чтения операндов А; и В; в следующем виде: п-1, п-2, п-3,...,3,1, где (n-1) — старший разряд.

Сигналы управления одновременно с выходов дешифраторов 7 и 8 поступают на входы дешифратора 6 адреса и на управляющие входы выходного коммутатора 4, тем самым обеспечивается г считывание информации операндов А; и

В; из выбранных модулей блока 3 памяти и подача их на входы арифметического блока 5, Одновременно со считыванием операндов А; и В; из блока 3 памяти на вход арифметического блока 5 из блока постоянной памяти по адресу, сформированному на дешифраторе 30 адреса

5 1411 по i-му тактовому импульсу, считывается кодовое значение соответствую° )( щего коэффициента M .

С приходом (i+1)-ro тактового им(В пульса в арифметическом блоке 5 выполняется базовая операция над опе0 рандами А; и В; и осуществляется запись адресов чтения этих операндов соответственно в регистры 21 и 23. 10

С приходом (i+2)-ão тактового импульса результаты выполнения базовой ь о операции Х; и У (над операндами А

1 и Й ° ) фиксируются в выходных регист.рах арифметического блока 5 и посту- 15 пают на входы входного коммутатора 2 г для записи в модули блока 3 памяти.

По этому же импульсу адреса из регистров 21 и 23 переписываются соот ветственно в регистры 20 и 22 и пос- 20 тупают на входы коммутатора 15 адреса, на выход е которого формируют ся

Ф адреса записи результатов 1; и У..

Управление коммутатором 15 адреса

,обеспечивается сигналами с блока 19 25 ,, элементов И-ИЛИ, задержанными на два

,такта на триггерах 25 и 24, в соответствии с временными диаграммами.

На выходе коммутатора 15 адреса сформированная пара адресов записи 30 представляется следующим образом: и-й и второй разряды каждого адреса поступают соответственно на дешифраторы 9 и 10.

Сформированные двухразрядные коды определяют номера модулей блока 3 памяти, в которые обеспечивается запись результатов Х; и У; . ,1

При этом код 00 определяет первый модуль, 01 — второй модуль, 10 — тре-тий модуль, 11 — четвертый модуль.

На входы дешифратора 6 адреса оставшиеся (n-2)-разрядные адреса записи 4r результатов Х; и У; поступают в следующем виде:

IT»1, п»2, п-3, ° . °,3, 1

50 где (n-1) — старший разряд.

Сигналы управления с выходов дешифраторов 9 и 10 одновременно и соответственно поступают на входы дешифратора 6 адреса, а также на управляющие входы входного коммутатора

2, что обеспечивает запись результа\ гов Х; и У; в выбранные модули запи- си блока 3 памяти по адресам, посту777 пающим с: выходов дешифратора 6 адреса. На этом цикл выполнения базоУ вой операции .над операндами А ° и В

1 1 заканчивается.

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

А; и В; осуществляется вьпголнение базовой операции БПФ над операндами А; и Вг „, а также производится запись результатов Х и У; выполнения базовой операции над операнцами А; и

В;

Формула изобретения

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

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

20

30

35 входу третьего- регистра, выход кото45

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

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

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

9 14117 выход первого элемента ИЛИ подключен к первому входу первого элемента И-НЕ, выход которого подключен к входу элемента НЕ, выход которого является пер-> вым выходом блока коррекции, выход первого элемента И подключен к первому входу второго элемента И-НЕ выход ко торого подключен к первому входу вто рого элемента ИЛИ, выход которого под-1О

I I ! ключен к тактовому входу первого триг гера, инверсный выход которого подключен к информационному входу первого триггера и первому входу третьего эле- мента И-НЕ, выход которого является, вторым выходом блока коррекции и под I ключен к тактовому входу второго триг( гера, инверсный выход которого подключен к D-входу второго триггера, пер- 20

:ному входу четвертого элемента И-НЕ и

lO тактовому входу третьего триггера, инверсный выход которого подключен к

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

И и первого элемента И-НЕ, соответствующие входы первых элементов ИЛИ и

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

1411777

/up7ep

2ФМР.

Литер.

Ривер Р-/ итар.

1ижр.

2umep.

Уилл.

4aimep. р--) ивер, 1411777

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

Техред А, Кравчук Корректор М,Васильева

Редактор Н.Бобкова

Заказ 3656/46 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4