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

11411

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - менные диаграммы работы устройства, на фиг. 3 - временные диаграммы управления первым коммутатором адресаf на фиг. 4 - временные диаграммы управления вторым коммутатором адреса; J5 на фиг. 5 - схема блока коррекции.

Устройство содержит элемент И-ИЛИ 1, входной коммутатор 2, блок 3 памяти, выходной коммутатор 4, арифме- |тический блок 5, дешифратор 6 адреса,20 |два дешифратора 7 и 8 чтения, два де- |шифратора записи 9 и 10, блок Л эле- |ментов ИЛИ, блок 12 коррек1щи, комму- татор 13 адреса, блок 14 элементов И, {коммутатор 15 адреса, элемент И 16, 25 {триггер 17 режима, блок элементов 18 |ИЧШИ, блок 19 элементов И-ИЛИ, ре-й гистры 20-23, триггеры 24 и 25, дешифратор 26 адреса, элемент И-ИЛИ 27, счетчик 28 операндов, счетчик 29зО

итераций, дешифратор 30 адреса, блок 31 постоянной памяти. I Блок 12 (фиг. 4) содержит элемен- |гы И 32 и 33, элементы ИЛИ 34, 35, лементы И-НЕ 36-39, элемент НЕ 40, . триггера 41-43.

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

Базовая операция такого алгоритма , состоит в том, что входных числа А И В объединяются для пол.учения выход- tibix чисел X и У следующим образом: дд

X. А,-

f А;- B,W,,

(1)

де k «

- комплексные числа. Согласно применяемого алгоритма 1|ПФ вычисления проводятся за Р loggN итераций. На каждой итерации 1 ыполняются N/2 базовых операций дли- 1 ельностью TBJ .

с

оJ5

0 5 О

Q

д

0

5

7772

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

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

TSO - ТОВР ., ОЗУ

где ТОР - время обращения к блоку

ОЗУ ОЗУ с чтением или записью, Tgp - время вьтопнения базовой

операции БПФ.

Устройство работает следукяцим образом.

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

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

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

314

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

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

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

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

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

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

774

В соответствии с временной диаграммой, представленной на фиг. А (на каждой итера1шн), с приходом i-ro

тактового импульса формируются адреса чтения операндов А и В. Адрес чтения операнда Д ,- формируется на п- разрядном счетчике 28 операндов, адрес чтения операнда В- формируется

одновременно в дешифраторе 26 адреса путем суммирования по mod 2 адреса чтения операнда А,- с закодированным номером соответствующей итерации. Сформированная пара адресов

чтения операндов Л; и В,- поступает одновременно на входы коммутатора 13 адреса и на соответствующие входы регистров 21 и 23.

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

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

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

двухразрядные коды определяют номера модулей блока 3 памяти, из которых одновременно производится считывание операндов-Aj ч В,-. При этом код 00 определяет первьп модуль, код 01 - второй модуль, 10 - третий модуль, 11 - четвертый модуль. На дешифратор 6 адреса соответственно поступают оставшиеся {п-2)-разрядные коды адресов чтения операндов А , и В- в следуюЩем виде:

п-1, п-2, n-3,,.,,3,1j

где (п-1) - старший разряд. Сигналы управления одновременно с выходов дешифраторов 7 и 8 поступают на входы дешифратора 6 адреса и на управляюш 1е входы выходного коммутатора 4, тем самым обеспечивается

(Считывание информации операндов А; и

В{ из выбранных модулей блока 3 памяти

и подача их на входы арифметического блока 5,

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

5

по i-му raKTOBONry импульсу, считывается кодовое значеьше соответствующего коэффициента Wj .

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

С приходом (i+2)-ro тактового импульса результаты выполнения базовой

ь«#

операции X - и У,- (над операндами А и В|) фиксируются в выкодных регистрах арифметического блока 5 и посту- пают на входы входного к оммутатора 2 для записи в модули блока 3 памяти. По этому не импульсу адреса из регистров 21 и 23 переписьшаются срот ветственно в регистры 20 и 22 и пос- тупают на входы коммутатора 15 адреса, на выходе которого формируются адреса записи результатов X , и У. .

Управление коммутатором 15 адреса обеспечивается сигналами с блока 19 элементов , задержан1й1ми на два такта на триггерах 25 к 24, в соотвествии с временными диаграммами.

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

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

При ЭТОМ код 00 определяет первый модуль, 01 - второй модуль, 10 - третий модуль, 11 - четвертый модуль, На входы дешифратора 6 адреса остав- 1шиеся ()-разрядные адреса записи результатов k,- и У,- поступакгг в следующем виде:

п-1, п-2, п-35,..53,1.

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

Сигналы управления с выходов дешифраторов 9 и 10 одновременно и соответственно поступают на входы де- (пифратора 6 адреса, а также на уп- равляющие входы входного коммутатора 2, что обеспечивает запись результа- гов X и У,- в выбранные модули записи блока 3 памяти по адресам, посту

ю

15 20

25 30

35

40

45

0

g

777 .6

пающим С ) выходов дешифратора 6 адреса. На этом цикл выполнения базовой операции онад операндами А ; и В- заканчивается. I

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

t-i

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

Устройство для выполнения быстрого - преобразования Фурье, содержащее блок памяти, арифметический блок, блок постоянной памяти, первьй дешифратор адреса, счетчик операндов и счетчик итераций, счетный вход которого подключен к выходу переноса счетчика операндов, информационный выход счетчика итераций подключен к первому входу первого дешифратора адреса, выход которого подключен к адресному входу блока постоянной памяти, выход которого подключен к входу задания коэффициента -арифметического блока, отличаю ще.еся тем, что, с целью повьшения быстродействия, в не- го введены первый и второй дешифраторы чтения, первый и второй дешифраторы записи, второй и третий дешифраторы адреса, первый и второй коммутаторы адреса, блок коррекции,, блок элементов ИЛИ, блок элементов И, первый и аторой блоки элементов И-ИЛИ, элемент И, первый, второй элементы И- ИЛИ, входной коммутатор, выходной коммутатор, триггер режима, первый, второй, третий и четвертый регистры, первый и второй триггеры, причем выход первого элемента ИЧ1ЛИ подключен к первому информационному входу входного коммутатора, выход которого подключен к информационному входу блока памяти, выход которого подключен к информационному входу выходного коммутатора, первый и второй выходы которого подключены к входам соответственно первого и второго операндов арифметического блока, первый и второй выходы результата которого подключены соответственно к второму информационному входу входного коммута- татора и первому входу первого элемента И-ИЛИ, второй вход которого явк MeTBepTONry входу второго дешифрато ра адреса и первому управляющему вхо ду входного кoм fyтaтopa, второй управляющий вход которого соединен с пятым входом второго дещифратора адр са и подключен к выходу второго дешифратора записи, вход которого подключен к второму выходу второго комляется информационным входом устройст- д мутатора адреса, третий и четвертый

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

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

к MeTBepTONry входу второго дешифратора адреса и первому управляющему входу входного кoм fyтaтopa, второй управляющий вход которого соединен с пятым входом второго дещифратора адреса и подключен к выходу второго дешифратора записи, вход которого подключен к второму выходу второго ком

5 О С

5

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

Изобретение относится к области вычислительной техники и предназначено для спектрального анализа электрически сигналов, представленных в цифровой форме. Цель изобретения - повышение быстродействия. Устройство содержит элемент И-ИЛИ 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 ил . « М

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

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

.два элемента И, четыре элемента И-НЕ, элемент НЕ, три триггера, при этом

о и второго блоков элементов Й-ИЛИ,

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

носа счетчика итераций подключен к второму входу элемента И, причем блок коррекции содержит два элемента ИЛИ,

.два элемента И, четыре элемента И-НЕ, элемент НЕ, три триггера, при этом

91411777

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

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

рого элемента ИЛИ, выход которого под I

ключей к тактовому входу первого триггера, инверсный выход которого подключен к информационному входу первого триггера и первому входу третьего эле мента И-НЕ, выход которого является ВТОРЫМ выходом блока коррекщи и под.1

I

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

И

10

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

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

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

и

mjM «ш яте ом ММ

Ll IL lllItI КП |.г2;.. J

- - Ш Ji i J

йиг.2

tijijmjiruinjmjijiJUTj ..

Фие,3

p-JumBp,

Фи&

r