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

(54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Изобретение относится к специапизиро ванным вычиспительным устройствам ци(})ровой обработки сигналов, испогаьзующим алгоритм быстрого преобразования Фурье (БПФ) и может быть использовано в звуко- и радиолокации, в технике связи и телеметрии, для анализа биологических и сейсмических сигналов и в других областях техники, использующих спектральный и корреляционный анализ, а также быструю свертку. Известно устройство БПФ каскадного типа, которое имеет в каждом каскаде цифровые линии задержки одинаковой длины 11, Однако оно требует в каждом каскаде арифметический блок, что при больших существенно увеличивае.т объем аппаратуры. Наиболее близким по структуре и техническим характеристикам к предлагаемому является устройство, в котором каж дый арифметический блок состоит из вход ного переключателя, соединенного через цифровые линии задержки с выходным переключателем и вычислителем, а выходной переключатель соединен как с вы итатепем, так и с сумматором. Кроме того, в каждый блок входит умножитель, один вход которюго соединен с выходом входного переключателя, другой вход - с выходом блока памяти тригонометрических коэффициентов, а выход - со входами сумматора и вычитателя 2. Недостатком этого устройства является то, Ч7О умножители, входящие в состав каждого арифметического блока, являются сложными и большими по объему устройствами, что при больших N существенно увеличивает объем каскадного процессора БПФ в целом. Цель изобретения - сокращение объ ема процессора БПФ каскадного типа при сохранении других качественных и количественных характеристик. Поставленная цель достигается тем, что он содержит М/2 коммутаторов, причем выход j -го ( j 1.3, 5 ...) арифметического блока соединен с входом к-го (K(j--l)/2 коммутатора, выход которого подключен к входу { j + 1 )-го арифметическогого блока, выход гп -го (т 2, 4, 6 ...) арифметического блока соединен с вторым входом 6 -го ( Р №/2) умножителя, выход которого со единен с входом (т+ 1)-го арифметичес кого блока, причем управляющие входы М/2 коммутаторов соединены с выходом счетчика, при этом в i -ом ( i 1, М арифметическом блоке второй выход вход ного коммутатора подключен к вторым входами сумматора и вычитателя. На чертеже показана функциональная схема процессора быстрого преобразова йия Фурье. Устройство содержит вход 1 процессо ра, входной коммутатор 2, узел 3 задержки, сумматор 4, вычитатепь 5 выходной коммутатор 6, коммутатор (коммутатор-инвертор) 7, умножитель 8, бпо 9 памяти коэффициентов, двоичный счетчик 10, выход 11 процессора. Устройство работает следующим образом. На каждый очередной входной отсчет устройство выдает выходной отсчет, при этом операции-выполняемые устройством однозначно определяются двоичным счетчиком IP, работающим синхронно с вход ными отсчетами. Все операции производятся над комплексными числами. Каждый каскад выполняет базовую операцию описываемую формулами ГЬ,.а.а° ,. -й. .|,-. i 0. 1, 2, ... ( 0, 1, 2, ... { П - номер каскада, N- размер преобразуемого массива. Входной коммутатор 2 направляет от счеты со входа каскада в узел 3 задер жки (будущие ), либо на вычитатель 5 и сумматор 4 (текущие cttn) одновременно результаты Аз в узел 3 задержки. Выходной коммутатор 6 направляет на выход каскада хранящиеся в узле 3 задержки резугпэтаты Ъ пибо результаты с сумматора 4 (текущие Ь ) и одновременно из узла 3 задержки задержанные там d, на вычитатель и и сумматор 4. утаторы 7, стоящие после кадов, выполняют операцию fei , tXPVI o,,(l,...- il {-Я- -Ь,при i-/-iN ( 1). О, 1, 2, номер нечетного каскада, после которого стоит данный коммутатор. жители 8, стоящие поспе четырех в, выполняют операцию умножения рачивающие множители ( (N- 1), О, 1, 2, ||modT v.,R , двоично-инверсное значение по целая часть числа. метры М,, , Р определяпользуемым алгоритмом и, напригут принимать следующие значеM rN/a iСуществует много других варипитов оритмов. Поворачивающие множители па умноель 8 подаются из блока П. Значение индекса i во всех формупах оп хэдепяется значением с двоичного счет чика 1О (мпадшими разрядами этого счетчика, ecmi максимальное значение i меньше N ). В остальном работа процессора аналогична известному. В частности, при выпопнении прямого БПФ и естественном порядке следования,входных данных выхо ные отсчеты будут следовать в двоичноинверсном порядке. Длина узпов задержки при этом составляет N/2, N/4, и т.д., начиная с 1-го каскада. Экономия аппаратуры предлагаемого процессора достигается за счет сокраше- ния количества, умножителей. Скорость работы процессора будет определяться при этом скоростью работы одного каска да, а качество работы - числом двоичных разрядов в представлении входных данных и тригонометрических коэффициентов, как это имеет место в известном процессоре Формула изобретения Процессор быстрого преобразования Фурье, содержащий М арифметических блоков, счетчик, блок памяти, коэффициентов и jM/2 умножите пей, причем выход i-го арифметического блока, кроме последнего, соединен с входом (i + 1)-го арифметического блока, а выход последнего арифметического блока является вы ходом процессора, вход i -го арифметического блока, кроме первого, соединен с выходом ( i - 1 )-го арифметического блока, а вход первого арифметического блока является входом процессора, выход счетчика соединен с входом бпока памят коэффициентов, выход которого соединен с первыми входами умножителей, причем i-и ( i - 1, М) арифметический, блок со 9 2 держит входной коммутатор, выходной коммутатор, узпь задержки, сумматор и вычитатель, выход которого подключен к первому входу входного коммутатора, первый выход которого соединен с входом узла задержки, выход которого подключен к первому входу выходного коммутатора, первый выход которого соединен с первым входом вычитателя и первым входом сумматора, выход которого соединен с вторым входом выходного коммутатора, второй выход которого является выходом арифметического блока, а второй вход входного коммутатора является входом арифметического блока, причем управляющие входы входного и выходного коммутаторов соединены с выходом счетчика, отличающийся тем, что, с целью сокращения объема оборудования, он содержит М/2 коммутаторов, причем выход j -го ( J- 1, 3, 5, ...) арифметического блока соединен с входом V. -го -(j + 1)/2 коммутатора, выход которого подключен к входу ( j + j-)-ro арифметического блока, выход (гп 2, 4, 6, ...) арифметического блока соединен с вторым входом 2 -го (S ггу,/2) умножителя, выход которого соединен с входом (т + 1)-го арифметического блока, причем управляющие входы AV2 коммутаторов соединены с выходом счетчика, при этом в 1 -м (i - 1,М) ари( ческом блоке второй, выход входного коммутатора подключен к вторым входам сумматора и вычитателя. Источники информации, принятые во внимание при экспертизе 1. Патент США № 3746848, кл. G Об F 15/32, опублик. 1973. a.H.UGrocigincV.,G.A.WorV.s. А. asi Trdns urm, itEE Trcins p.p. 1O15-1O19 197O, V. C-19, № 11, (прототип).

Оч