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

торов, блоков памяти и арифнетпче:кого блока в каждом из дополнительно введенных вычислительных блоков подключены к соответствуюш,им выходам блока управления, а соответствующие информационные ные входы арифметических блоков - к выходам блока формирования весовых коэффициентов, первый вход первого вычислительного блока является информационным входом устройства, второй вход первого вычислительного блока подключен к первому выходу /(-го вычислительного блока, первый и второй входы i-ro (.) вычислительного блока подключены соответственно к первому п второму выходам (i-1)-го вычислительного блока, третий и четвертый выходы г-го (t l-Х/2) вычислительного блока подключены к четвертому входу соответственно (2i-1)-го и 2t-ro вычислительного блока, третий и четвертый выходы i-ro (i(l+/(/2)-К.) вычислительного блока иодключены к третьему входу соответственно (21-К-1)-го и (2t-Л)-го вычислительного блока.

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

Устройство содержит К вычислительных блоков 1, блок 2 формирования весовых коэффициентов, устройство 3 управления, блоки 4 памяти, арифметические блокн 5, блоки 6 памяти, коммутаторы 7. В состав арифметического блока входят сумматоры 8, 9, блок 10 умножения, коммутаторы И.

Устройство осуществляет обработку N 2 дискретных значений входного сигнала. Каждый вычислительный блок обрабатывает одновременно М 2™ дискретных

N

значений М -

прпчем число вычислич А:

тельных блоков /-( быть выбрано исходя из требуемого быстродействия. Вся информация нредставляется комплексными числами. Емкость каждого блока памяти составляет комнлексных чисел. Входная информация (N - 2 выборок) поступает последовательпо на jiepBbiii вход вычислительного блока 1. После Л тактов сдвига в первый блок 4 памяти t-ro вычислительного блока 1 запишутся выборки с

номерами /с - (i-1) по (Ai/2)-i-1, во

же блока - второй блок 4 памяти

этого

Л После записи выборки с померами /2

всей входной информации начинается собственно процесс обработки ее по алгоритму БПФ. Обработка состоит из n log2A операций. В любой операции в каждом вычислительном блоке 1 нара комплексных чисел x(i) из первого блока памяти н

/ Л

xt j+ - из второго одновременно поступает на входы сумматоров 8 и 9 арифметического блока 5. На выходе сумматора 9 получается результат xij)+х . Результат, полученный на сумматоре 8 и рав„, .,; . ;V

ныи x(j) поступает на вход

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

Результаты с выхода сумматора 9 и с выхода блока 10 умножения последовательно одип за другим по управляющему синхроимпульсу от устройства 3 управленпя (УУ) записываются в третий и четвертый блоки 6 памяти в зависимости от номера /, причем в третий блок памяти записываются суммы и пзвешенные разности первой половины вычисленных результатов,

ттW

Б четвертый -- вторая половила. Носле -

тактов вычислений содержимое третьих и

четвертых блоков 6 памяти нереписывается в первые и вторые блоки 4 памяти соответствующих вычислительных блоков (через коммутаторы 7 но унравляющему синхроимпульсу от УУ 3). Это позволяет проводить обработку пнформации во всех последующих операциях апалогично описанной выше. Окончательны резу-п/гат - Л коэффициентов дискретного преобразователя Фурье - получается после операций записанным в третьи и четвертые блоки 6 памяти всех К вычислительных блоков I. Порядок записи результ га двоичпо-ипверсный по отпошепию к порядку записи входной информации.

Предложеиная стру1чтура, устройства позволяет значительно сократить время обработки, так как вместо комнлексных умножений и комплекспых сложений и вычитаний оно выполняет л2™- комплексных у.множений и столько же комплекспых сложений п вычитаний.

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

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

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

арифметических блоков - к выходам блока формирования весовых коэффициентов, первый вход первого вычислительного блока является информационны.-. входом устройства, второй вход первого вычислительного блока подключен к первому выход,у /С-го вычислительного блока, первый и второй входы i-ro (i 2-К) вычислительного блока подключены соответственно к первому и второму выходам (i-1)-го вычислительного блока, третий и четвертый выходы i-ro (t l-/С/2) вычислительного блока подключены к четвертому входу соответственно (2i-1)-го и 2г-го вычислительного

блока, третий и четвертый выходы 1-го (i(l+K/2)-К.) вычислительного блока подключены к третьему входу соответственно (2i-К-1)-го и (21-/С)-го вычислительного блока.

Источники информации,

принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 480079, кл. G 06F 15/34, 1975.

2.Патент Франции N° 2082030, кл. G 06F 15/00, 1975.