Процессор быстрого преобразования фурье

Союз СоветсимиСоциалист мчеснмиРеспубпмм ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и 928362(23) ПриоритетОпубликовано 15,05,82, Бюллетень ре 18Дата опубликования описания 15.05,82 Ц 06 Р 15/332 Гоеударотюиый омитет СССР ио делам изебретеиий и открытий(54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к специализированным вычислительным устройствам цифровой обработки сигналов, испопьзуюшим алгоритм быстрого преобразования Фурье (БПФ) и может быть использовано в звуко- и радиолокации, в технике связи и тепеметрии, дпя анализа биологических и сейсмических сигналов и в других обпастях техники, испопьзуюших спектрапьный и корреляционный анализ, а также"быструю" свертку.Известно устройство БПФ каскадного типа, которое имеет в каждом каскаде цифровые линии задержки одинаковой дпины Г 11.15Однако оно требует в каждом каскаде арифметический бпок, что при бопьших существенно увеличивает объем аппаратуры.Наиболее близким по структуре и тех 20 ническим характеристикам к предлагаемому явняется устройство, в котором каждый арифметический бпок состоит из входного переключателя, соединенного через 2цифровые пинии задержки с выходным перекпючатепем и вычислителем, а выходной перекпючатепь соединен как с вычитатепем, так и с сумматором. Кроме того,в каждый бпок входит умножитепь, одинвход которого соединен с выходом входного перекпючатепя, другой вход - с выходом блока памяти тригонометрическихкоэффициентов, а выход - со входами сумматора и вычитатепя Г 21.Недостатком этого устройства явпяется то, что умножитепи, входящие в состав каждого арифметического блока, явпяются спожными и бопьшими по объемуустройствами, что при больших М существенно увепичивает объем каскадногопроцессора БПФ в цепом,Цепь изобретения - сокращение объ-ема процессора БПФ каскадного типапри сохранении других качественных иколичественных характеристик,Поставленная цель достигается тем,что он содержит М/2 коммутаторов, причем выход ) -го ( ) = 1, 3, 5 ,) ариф=гт/2) умножителя, выход которого соединен с входом (гг 1+ 1)-го арифметического блока, причем управляющие входыМ/2 коммутаторов соединены с выходомсчетчика, при этом в 1 -ом ( 1 = 1, М)арифметическом блоке второй выход входного коммутатора подключен к вторымвходами сумматора и вычитателя.На чертеже показана функциональнаясхема процессора быстрого преобразова ния фурье,Устройство содержит вход 1 процессора, входной коммутатор 2, узел 3 задержки, сумматор 4, вычитатель 5 выходной коммутатор 6, коммутатор (коммутатор-инвертор) 7, умножитель 8, блок9 памяти коэффициентов, двоичный счетчик 10, выход 11 процессора.Устройство работает следующим образом.На каждый очередной входной отсчетустройство выдает выходной отсчет, приэтом операции. выполняемые устройствомоднозначно определяются двоичным счетчиком 10, работающим синхронно с входными отсчетами. Все операции производятся над комплексными числами. Каждый каскад выполняет базовую операцию,Фописываемую формуламиР35ЬК=сг сго -см -с 3К Мгде К:М/г . )П - номер каскада,М - размер преобразуемого массива.Входной коммутатор 2 направляет отсчеты со входа каскада в узел 3 задер -жки (будущие сгК ), либо на вычитатель5 и сумматор 4 (текущие д 11) и одновременно результаты Ьщ в узел 3 задержки, Выходной коммутатор 6 направляет на выход каскада хранящиеся в узле 3 задержки результаты Ьщ либо результаты с сумматора 4 (текущие Ьк )и одновременно из узла 3 задержки задержанные там с 1 к на вычитатель 5 исумматор 4,4 Коммутаторы 7, стоящие после ных каскадов, выполняют операцикгде ) =О, 1, 2, (2 - 1),и- номер нечетного каскада, послекоторого стоит данный коммутатор.Умножители 8, стоящие после четырехкаскадов, вьгполняют операцию умноженияна поворачивающие множители где =0, 1, 2, , (М),ф е 3 йг1 ЗР( л - двоично-инверсное значение по п- целая часть числа,Параметры М, , , Д определяются используемым алгоритмом и, наприРмер, могут принимать следующие значеМ: я г+/. Вариант 1 . =4.и -г. Вариант 3 (для й = 4096) 2 4 6 8 10 Мгг 256 1 16 1 1 Существует много других вариантовалгори тмов.Поворачивающие множители на умножитель 8 подаются из блока5 9283Значение индексаво всех формупах определяется значением с двоичного счетчика 10 (мпадшими разрядами этого счетчика, еспи максимапьное значениеменьше М ) .5В остальном работа процессора аналогична известному, В частности, при выпопнении прямого БПФ и естественном порядке спедоваиия,входных данных выходные отсчеты будут спедовать в двоично инверсном порядке. Длина узлов задержки при этом составпяет М/2, Н /4, и т,д начиная с 1-го каскада.Экономия аппаратуры предлагаемого процессора достигается за счет сокраше ния количества. умножителей. Скорость работы процессора будет опредепяться при этом скоростью работы одного каскада, а качество работы - числом двоичных разрядов в представпении входных данных щ и тригонометрических коэффициентов, как это имеет место в известном процессоре.Форму па изобретения 25Процессор быстрого преобразования фурье, содержаший М арифметических бпоков, счетчик, блок памяти, коэффициентов и М/2 умножитепей, причем выход-го арифметического блока, кроме последнего, соединен с входом (+ 1)-го арифметического бпока, а выход поспеднего арифметического блока является выходом процессора, вход-го арифметического блока, кроме первого, соединен с выходом (- 1 )-го арифметического блока, а вход первого арифметического блока является входом процессора, выход счетчика соединен с входом бпока памяти 4 О коэффициентов, выход которого соединен с первыми входами умножитепей, причем -й (- 1, М) арифметический бпок со 62ю.6держит входной коммутатор, выходнойкоммутатор, узпы задержки, сумматор ивычитатепт выход которого подкпючен кпервому входу входного коммутатора, первый выход которого соединен с входомузла задержки, выход которого подкпюченк первому входу выходного коммутатора,первый выход которого соединен с первым входом вычитатепя и первым входомсумматора, выход которого соединен свторым входом выходного коммутатора,второй выход которого является выходомарифметического блока, а второй входвходного коммутатора является входомарифметического бпока, причем управпяюшие входы входного и выходного коммутаторов соединены с выходом счетчика,отличаюшийся тем,что,сцепью сокрашения объема оборудования, онсодержит М/2 коммутаторов, причем выход-го ( ) - 1, 3, 5,) арифметического бпока соединен с входом М -го- + 1)/2 коммутатора, выход которого подкпючен к входу (+ )-го арифметического блока, выход п -го (п= 2,4, 6, ) арифметического блока соедиОнен с вторым входом 0 -го (1 =пЪ/2)умножитепя, выход которого соединен свходом (п+ 1)-го арифметического бпока, причем управляющие входы М/2 коммутаторов соединены с выходом счетчика,при этом в-м (- 1,М) арифметическом блоке второй выход входного коммутатора подкпючен к вторым входам сумматора и вычитатепя,Источники информации,принятые во внимание при экспертизе1. Патент СШ А Хс 37 468 4 8,кл, б 06 Г 15/32, опублик, 1973,О Н,)СгофпсИ 5., 6.А.%ог 15. А. Рре Ьпею Роогее ТгЫ 5 Еа гтрк, 1 И ТгспЬ1970, Ч. С, М 11, р.р. 1015-1019