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

Изобретение относится к вычислительной технике и может быть исполь зовано в системах обработки дискрет ной информации, радио и гидролокации, медицинской и другой аппаратуре, где используются цифровая фильтрация и спектральный анализ„ .Целью изобретения является повышение быстродействия На. фиг. 1 представлена функциональная схема уст.ройства для выполнения быстрого преобразования Фурье; на фиг, 2 - временньсе диаграммы, поясняющие работу устройства. Устройство (фиг. 1) содержит первый регистр коэффициента, первый входной регистр 2, первый умножитель 3, первый регистр 4 произведения, второй регистр 5 коэффициента, второй входной регистр 6,второй умножитель 7, второй регистр 8 произведения, генератор 9 тактовых импульсов, триггер 10, третий входной регистр 11, сумматор-вычита-тель 12. Устройство для выполнения быстрого преобразования Фурье работает следующим образом. Арифметические действия, выполняемые в ходе базовой операции, включая умножение на поворачивающий множитель W, можно записать в действительной форме следующим образом ReC (ReC. , ImW, ), (1) ReAi HReA.+(ReC; ReW-ImC-. ImW; ), (2) ImC; (ReCi ImW +ImC- ReV, ) , (3) ImA ImA.-f (ReCi ImW-+ImCf ReW. ), (4) где A;,C - входные комплексные опе ранщ,; А ,С - выходные комплексные операнды; Vi - комплексный коэффициент Re - действительная часть комплексного числа; Im - мнимая часть комплексно го числа, Для простоты изложения изобретения предполагается, что запись данных в регистры 1, 2, 4, 5, 6, 8. 11 и переключение триггера 10 прои ходит за бесконечно малое время, а задержка, вносимая умножителями 3 и 7 и сумматором-вычитателем 12,, не превьпаает длительности синхронизирующего импульса на выходе генера.тора 9 тактовых импульсов. 1 В предлагаемом устройстве сумматор-вычитатель 12 функционирует в соответствии с таблицей, где высокий уровень сигнала обозначен как 1, анизкий - О, В начальный момент на вход синхронизации устройства поступает сигнал высокого уровня. Этот сигнал запрещает работу генератора 9 тактовых импульсов и триггера 10. При этом на выходе генератора 9 тактовых импульсов и на прямом выходе триггера 10 устанавливается сигнал низкого уровня. Во время прихода первого операнда (ReCo) на вход задания операнда устройства, на входе синхронизации устройства устанавливается сигнал низкого уровня, тем самым разрешается работа генератора 9 тактовых импульсов и триггера: ГО. При этом частота генератора 9 тактовых импульсов такова, что один из операндов ReC-, , ImC-, ReA, ImA., поступает на вход задания операнда устройства за половину периода тактовых импульсов, а каждый из коэффициентов ReW-,, ImW;, - за один па- . риод тактовых импульсов. Взаимное расположение так.товых импульсов, операндов и коэффициентов показано на фиг. 2. IДалее, до окончания преобразования всего массива входных операндов, устройство работает следующим образом. В момент прихода операнда ReC; на вход за,дания операнда устройства триггер 10 под-воздействием, отрицательного фронта тактового импульса, поступающего с выхода генератора 9 так говых импульсов, устанавливается в нулевое состояние, т.е. инверсный выход триггера 10 устанавливается в состояние логической единицы.

Регистры 1, 2, 4, 5, 6, 8, 11 записывают данные, поступающие на их D-входы, по положительному фронту на С-входах.Следовательно, при подаче операнда ReC на вход устройства и переключении триггера 10 в нулевое состояние, на выходе регистра 2 установится значение ReC (фиг. 1 и 2).

В момент формирования логической единицы генератором 9 тактовых импульсов, на вход реальной части поступает коэффициент ReV , на вход мнимой части 1т1 , на вход задания операнда - ImA-,, которые записываются в регистры 1, 5 и П соответственно по положительному фронту тактового импульса, поступающего с выхода генератора 9 тактовых импульсов .

Отрицательный фронт тактового импульса переключает триггер 10 в единичное состояние, т.е. на прямом выходе триггера 10 формируется логическая единица. Положительный перепад на неинверсном выходе триггера 10 записывает в регистр 6 операнд ImC , поступающий в этот момент на вход устройства.

В момент формирования генератором 9 второго тактового импульса просходит запись операнда ReA, потупающего по входу устройства. Таке происходит запись сформировавшихся к этому времени произведений ReVJ-j и ImC.- ImW в регистры 4 8 соответственно.

В первом такте сумматор-вычитатель производит действия согласно соотнощению СП, во втором - согласно соотношению (.). В результате этого на выходе устройства формируются новые значения ReCI и ReA. . В тот момент, когда сумматор-вычитатель формирует величины ReC| и ReA| , регистры 1 и 5 принимают коэффициенты ImV. и ReV, соответственно. Ка выходах умножителей 3 и 7 формируются произведения ReC,- ImW и ImCj ReW; (фиг. 1 и 2).

Б этот момент сумматор-вычитатель заканчивает формирование ReC; и ReA и по положительному фронту тактово- го импульса произведения ReC ImW и ImC- ReW; записываются в регист67431

ры 4 и 8 соответственно. А в регистр 1 1 по этому же сигналу записывается операнд ImA. , поступающий по входу устройства. В результате этого 5 на третьем такте сумматор-яьтчитатель формирует на выходе устройства величину ImC. , на четвертом такте IiTiAi .

Затем функционирование устройст10 ва повторяется и вычисляются следующие значения ReC , ReA., ImC, и ImAj 4, (фиг. 2).

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

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

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

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

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

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

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

267431ft

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

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

ffxffd7

&ЫХ. блока Э Вых. и блока W вых.одлока ш В ход Г Вход2 ВлодЗ

Выл. SitOKo 2 Вых. блока В Вых. блоков Вых. блока 7 Вых. блока Л/д-. блока 8

Вых. блока 11 Boixod