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

 

Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования Фурье в устройствах цифровой обработки сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается тем, что в состав устройства входят входной блок 3 памяти, блоки 4, 5 памяти, арифметический блок 6, блок 7 постоянной памяти, регистры 8, 9, накапливающие сумматоры 10, 11, блок 12 синхронизации, блок 13 памяти, блок 14 задержки и выходной арифметический блок 15. 6 ил.

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

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

РЕСПУБЛИК

„.SU„„16052

А1 щ)5 С 06 Р 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н двтоесном свидьтклмтвм

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4473556/24-24 (22) 04.07.88 (46) 07.11.90. Бюл. У 41 (72) Д.В.Корчев, О.И.Поваренко и Т.Н.Черная (53) 681.32 (088.8) (56) Патент Великобритании и 1407401, кл. G 06 F 15/332, опублик. 1975.

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

У 723582, кл. G 06 F 15/332, 1980. (54} УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычисли2 тельной технике и предназначено для выполнения алгоритма быстрого преобразования Фурье в устройствах цифровой обработки сигналов. Цель изобретения — упрощение устройства. Поставленная цель достигается тем, что в состав устройства входят входной блок

3 памяти, блоки 4, 5 памяти, арифметический блок 6, блок 7 постоянной памяти, регистры 8,9, накапливающие сумматоры 10, 11, блок 12 синхронизации, блок 13 памяти, блок 14 задержки и выходной арифметический блок 15.

6 ил.

\.1605256

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

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

На фиг.l представлена структурная схема устройства для вычисления быстрого преобразования Фурье; на фиг.2 — структурная схема выходного арифметического блока; на фиг.3— временная диаграмма управления входным блоком памяти; на фиг.4 — временная диаграмма записи в блок оперативной памяти; на фиг.5 — временная диаграмма считывания из блока оперативной памяти; на фиг.6 — временная диаграмма считывания из блока памяти результата и управляющих сигналов вы" ходного арифметического блока.

Устройство содержит (фиг.l) ин" формационный вход 1, информационный вход 2 второго канала, входной блок

3 памяти, блоки 4 и 5 оперативной памяти, арифметический блок 6, блок

7 постоянной памяти, регистры 8 и 9, накапливающие сумматоры 10 и ll,блок

12 .синхронизации, блок,)3 памяти результата, блок 14 задержки, выходной арифметической блок 15, информационный выход 16.

Выходной арифметический блок 15 (фнг.2) содержит мультиплексоры 17 "

20, сумматор 21, вычитатель 22, сумматор 23, вычитатель 24, тактовые входы 25 и 26.

Устройство работает следующим образом, Устройство вычисляет БПФ двух входных действительных массивов данных X(n) и 7(п) длиной 0 2" (r — 3 4 ..»). Действительные массивы представляются в виде одного комплексного с элементами K(n) = X(n) +

+ qY(n) (3 - i). Поступление входных данных осуществляется параллельно по двум каналам через входы

1 и 2 соответственно. Для примера выберем Н 8. В блоке 3 памяти производится предварительное накопление входных данных, поступающих в реальном масштабе времени по двум каналам. Отсчеты X(n) первого канала записываются в первые два пофблока, а отсчеты второго канала 7(п) - во вторые подблоки. Отсчеты с четными номерами О, 2, 4, 6 заносятся в первый и третий подблоки, а отсчеты с нечетными номерами 1, 3, 5, 7 — во второй и четвертый подблоки. Объем памяти каждого подблока равен m/2 действительных слов. Временная диаграмма записи информации приведена на фиг,3. Низкий уровень сигналов выбора подблоков соответствует записи операндов.

По окончании приема инеормации во входной блок 3 памяти производится ее перезагрузка в один из свободных блоков 4 или 5 памяти. При этом действительная часть X(n) входного массива Z(n) передается по шинам

КеА и ReB, а мнимая Y — по шинам

lш А и lm В . Операнды с четными

1 I номерами 0,2,4,6 будут передавать20 ся через шину А (PReA и lmA ), а с нечетными номерами l, 3, 5, 7 через шину В (ReB и 1mB ) ° Пусть информация заносится в блок 4 памяти. При этом блок 12 будет формировать ад25 ресные и управляющие сигналы,соответствующие режиму записи. Объем памяти каждого подблока блоков 4 и 5 памяти равен й/4 комплексных слов, Перезапись информации производится за О/2 = 4 такта, Подблоки памяти. входного блока .3 памяти переводятся в режим считывания и выдают информацию параллельно каждый на свой вь хоц. В первом такте производится запись нулевого и первого комплексных операндов в первые два подблока соответственно. Во втором такте запись второго и третьего комплексных операндов в первые два подблока со40 ответственно. В третьем такте производится запись четвертого и пятого .комппексных операндов во вторые два подблока соответственно. На четвертом такте аналогично записываются

45 шестой и седьмой операнды. Временная диаграмма процесса записи информации в блок 4 памяти приведена на фиг.4.

Нижние уровни сигналов выбора подбло-, ков соответствуют записи соответст50 вукнцих операндов. Последовательность адресов повторяется два раза.

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

При этом на вход блока 6 информация поступает по шинам А и В, а запись результата в свободный блок 5 памяти производится через шины А и В .Вы1

5256

10 !

5 160 числение базовых операций алгоритма

БПФ производится по основанию 2 с прореживанием по частоте. Блок 4 памяти переводится в режим считывания информации, а блок 5 памяти — записи.

Время выполнения одного этапа БПФ составляет (п/2 + п ) тактов, где и р — количество тактов выполнения одной базовой операции. В первый такт считываются нулевой и четвертый операнд из первого и третьего подблоков соответственно по шинам А и В, Они поступают на входы арифметического блока 6, который выполняет базовую операцию за и< тактов. Во втором такте производится считывание первого и пятого комплексного операндов из второго и четвертого подблоков соответственно. В третьем такте— второго и шестого из первого и третьего подблоков. В четвертом— третьего и седьмого из второго и четвертого подблоков соответственно.Адреса и управляющие сигналы формируются блоком 12. Временная диаграмма приведена на фиг.5. По каждому адресу производится считывание пары операндов сперва из первого и третьего нодблоков, затем — из второго и четвертого подблоков. Через ng тактов после начала выполнения этапа

БПФ на выходах блока 6 будут последовательно появляться пары результатов, которые по шинам А и В записываются в блок 5 памяти.

Блок 12 формирует последовательность управляющих сигналов для блока

5 памяти, Запись информации в блок

5 осуществляется аналогично записи информации в блок 4 при загрузке из входного блока 3. Задержка-работы блоков 4 и 5 памяти составляет по тактов. Временная диаграмма записи информации в блок 5 аналогична диаграмме, приведенной на фиг.4.

После записи последней пары результатов из блока 6 в блок 5 памяти начинается новый этап вычисления

БПФ. Режим работы блоков 4 и 5 меняется. Информация считывается из блока 5, а заносится в блок 4 по описанным выше алгоритмам. Количество этапов определяется log

11 вычисления БПФ составляет г(— — +

+ п ) тактов. Описанный алгоритм работы устройства продолжается до последнего этапа вычислений.

l!a последнем этапе по сигналу с выхода блока 12 на шины А и В " будут поступать накопленные в блоке 3 отсчеты новой выборки, которые заносятся в свободный блок 4 или 5. Дру- . гой блок памяти будет выдавать информацию на блок 6 для выполнения последнего этапа. Таким образом,производится совмещение во времени загрузки информации и выдачи результа(((I тов, которые по шинам А и В поступают в блок 13 памяти результата.Последний переводится в режим записи, а управление им осуществляется блоком

12, Временная диаграмма работы блока 13 памяти результата соответствует фиг.4. Адресные сигналы на входы поступают параллельно и одинаково согласно алгоритму работы предыдущих блоков 4 и 5 памяти в режиме записи.

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

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

15 в режиме выдачи результатов приведена на фиг.6. Все управляющие сигналы формируются блоком 12. На одном из адресных входов блока 13 памяти прямая последовательность адресов, на другом адресном входе .- инверсная последовательность адресов. Смена адресов производится через каждые два такта считывания. На первом такте считывается Z(0)(Z(n) — результат

БПФ комплексного массива из первого подблока и Z (7) из четвертого под- . блока. Операнд 2 (О) с первого выхода 13 памяти результата поступает на первый вход выходного арифметического блока 15. На один управляюший вход поступает нижний управляющий уровень, а на другой управляющий вход поступает верхний управляющий уровень. При этом на выходах сумматоров 21 и 23 будут значения КеХ(О) и

ReY(0) соответственно. На выходах вычитателей 22 и 24 будут значения

1,Х(0) = О и 1„,7(0). С приходом синх1605256 роимпульса значение 2(7) запишется в блок 14 задержки.

Во втором такте иэ второго подблока на второй выход блока 13 памяти результата поступает значение Z (6), на первый выход этого же блока 15 значение Z (1) из третьего подблока.

Управляющие сигналы на входах 25 и

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

15 находятся в нижнем уровне, при этом все мультиплексоры 17 - 20 передают информацию с первых входов.

На первый вход выходного арифметического блока 15 поступает значение

Z (1), а на второй — значение Z (7) с выхода блока 14 задержки, После выполнения соответствующих суммирований и вычитаний на выходе сумматора 21 будет значение ReX(1), на выходе вычитателя 22 — 1 X(l) на выходе сумматора 23 — Ре7(1) на выходе вычитателя 24 - 1ш7(1) . Будем полагать, что все выходные результаты промасштабированы соответствующим 25 образом. На третьем такте из первого подблока считывается Е (2), а из четвертого подблока Z (5). На входы выходного арифметического блока 15 поступают Z (2) и Z (6),,записанные 30 в блок 14 задержки на предыдущем такте. С выходов сумматоров 21 и 23 снимают значения ReX(2) и ReY(2), а с выходов вычитателей — 1 X(2) и

1„; (2). На четвертом такте из второго подблока считывается значение

Z (4),,из третьего подблока — Z (3).

На входах выходного блока 15 значения Z (3) и Z (5). На выходах 16 блока 15 значения ReX(3), ReY(3), 40

1 Х(3), 1 7(3). В пятом такте на второй вход блока 15 поступает значение Z (4) иэ блока 14 задержки.

На входе 26 блока 15 остается нижний уровень, а на входе 25 устанавлива- 45 ется верхнее значение управляющего сигнала. При этом мультиплексоры

17 и 19 будут передавать информацию с второго входа. На выходах сумматоров "1 и 23 будут значения ReX(4) 50 и ReY(4), а на выходах вычитателей

22 и 24 — 1„Х(4) = 0 и 1,„7(4) = О.

После выдачи последних результатов блок 12 переводится в режим ожидания приема новых результатов в блок 13 памяти результата, Формула и з о б р е т е н и я

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

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

:информационный вход которого соединен с первым информационным входом

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

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

1605256

ЯдР6ГЯ

Фиг д

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

Техред g . Пндык

Корректор И.Максимишинец

Редактор Н.Тупица

Заказ 3455 Тираж 569 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101