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

описднию изоБрктСНиЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) 1, Л.РабинерБ.Гоулд. Теория и применение цифровой обработки сигналов. 1 р 1 "Мирр 1978.2, Авторское свидетельство СССР У 660057, кл. С 06 Р 15/332, 1976 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ БЫСТРОГО11 РЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее последовательно соединенные генератортактовых импульсов, счетчик адресаи блок постоянной памяти, блок постоянной памяти коэффициентов и 1 вычислительных блоков, каждый из которыхсостоит из первого и второго коммутаторов, первого, второго, третьегои четвертого узлов памяти и арифметического узла, информационные выходыпервого и второго коммутаторов подключены к информационным входам соответственно первого и второго узловпамяти, управляющие, входы которыхподключены к выходам соответственнопервого и второго разрядов блока постоянной памяти, выходы третьего,четвертого, пятого и шестого разрядов которого подключены к управляющим входам соответственно третьего ичетвертого узлов памяти, первого ивторого коммутаторов-го (1 =1,1)вычислительного блока, первые информационные входы первого и второгокоммутаторов-го (1=1, -1) вычислительного блока подключены к информационным выходам соответственно первого и второго узлов памяти (1+1)"го вычислительного блока, первый информационный вход второго коммутатора 1;-го вычислительного блока подключен к информационному выходу первого узла памяти первого вычислительного блока, вторые информационные входы первого и второго коммутаторов (2-1)-го (щ= =1, 1 /и) вычислительного блока подключены к информационным выходам третьих узлов памяти соответственно м-го и (М+ -)-го вычислительных блоков2у вторые информационные входы второго и первого коммутаторов 21)-го (1=1, М 2 ) вычислительного блока подключены к информационным выходам четвертых узлов памяти соответственно 1 -го и а (1 11 -го вычислительных блоков, а арифметический узел р -то т 5 - ГК) ви- Я числительного блока содержит умножи- р тель, сумматор, вычитатель и первый и второй коммутаторы, при этом выход умножителя подключен к первым входамсоответственно вычитателя и сумматора, выход которого подключен к первым информационным входам первого и второго коммутаторов, информационные выходы которых подключены к информационным входам соответственно третьего и четвертого блоков памяти 5-го вычислительного блока, первый вход умножителя арифметического узла 5-го вычислительного блока подключен к выходу б -го разряда блока постоянной памяти коэффициентов, управля- ВЫ ющие входы первого и второго коммутаторов арифметических узлов вычислительных блоков подключены к выходу седьмого разряда блока постоянной памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения его быстродействия, в него введены первый1130872 Составитель А,БарановРедактор С.Патрушева Техред З,Палий Корректор О.Тигор Подписное Филиал ППП "Патент", г.ужгород, ул .Проектная, 4 Заказ 9612/36 Тираж 698ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д.4/51130872 и второй коммутаторы, регистр сдвига, в каждый вычислительный блок введен .1переключатель, а в каждый арифметический узел введен элемент НЕ, причем информационный выход регистра сдвига подключен к первому информа" ционному входу первого коммутатора, информационный выход которого соединен с информационным выходом второго коммутатора и с первым информационным входом первого коммутатора 1 -го вычислительного блока, второй информационный вход первого коммутатора соединен с первым информационным входом второго коммутатора, с информаци" онным входом регистра сдвига и является первым информационным входом устройства, вторым информационным входом которого является второй информационнйй вход второго коммутатора, управляющие входы первого и второго коммутаторов подключены к выходам соответИзобретение относится к вычислительной технике, в частности к устройствам для спектрального анализасигналов, представленных в цифровойформе, и может быть использовано 5для вычисления спектра сигналов и нхфильтрации, в частности области всвязи, навигации, телеметрии и другихобластях техники.Известны многопроцессорные цифровые устройства быстрого преобразования Фурье, реализующие метод вычислений по алгоритму быстрого преобразования Фурье (БПФ), позволяющие вычислить Б коэффициентов дискретного пре. образования Фурье временной последовательности по И выборкам входногосигнала, Эти устройства содержат блоки памяти, арифметические блоки, блокпамяти коэффициентов и работают в реальном масштабе времени Я ,Наиболее близким по техническойсущности к изобретению является устройство быстрого преобразования Фурье, содержащее блок управления, блок 5форирования весовых коэффициентов и1 с=2, где 7 - целое число (1741 ор Х),вычислительных блоков, каждый из коственно восьмого и девятого разрядов блока постоянной памяти, выходдесятого разряда которого подключенк управляющему входу переключателя-го(р = ,Ц) вычислительного блока,информационные выходы первого и второго узлов памяти-го вычислительного блока подключены соответственнок первому и второму информационнымвходам переключателя р-го вычислительного блока, первый и второй информационные выходы которого подключены соответственно к второму вхо;ду умножителя и вторым входам сумматора и вычитателя арифметическогоузла вычислительного блока, выходвычитателя арифметического узла подключен к входу элемента НЕ арифметического узла, выход которого подключен к вторым информационным входампервого и второго коюутаторов арифметического узла. торых состоит из коммутаторов, блоков памяти и арифметического блока, причем управляющие входы коммутаторов подключены к выходам блока управления, а информационный вход арифметического блока - к выходу блока формирования весовых коэффициентов. Это устройство реализует граф алгоритма БПФ с однородной структурой, .при ко-. торой адресация записи и считывания обрабатываемых чисел не зависит от номера интеграцииВследствие однородности графа алгоритма БПФ связи между ( вычислительными блоками остаются фиксированными в процессе вычислений 2,Недостатком этого устройства явля-. ется низкое быстродействие иизбыточный объем памяти при вычислении преобразования Фурье действительного входного сигналаЦель изобретейия - повьппение быстродействия устройства для быстрого преобразования Фурье.Цель достигается тем, что в устройство для быстрого преобразования Фурье содержащее последовательно соединенные генератор тактовых импульвыходу 5 -го разряда блока постоянной памяти коэффициентов, управляющие входы первого и второго коммутаторов арифметических узлов вычислительных блоков подключены к выходу седьмого разряда блока постоянной памяти, введены первый и второй коммутаторы, регистр сдвига, в каждый вычислительный блок введен переключатель, а в .каждый арифметический узел введен з 11308 сов, счетчик адреса и блок постоянной памяти, блок постоянной памяти коэффициентов и 1 вычислительных блоков, каждыйиз которых состоит из первого и второго коммутаторов, первого,второго, третьего и четвертого узлов памяти и арифметического узла, информационные выходы первого и второго коммутаторов подключены к информационным входам соответственно первого 10 и второго узлов памяти, управляющие входы которых подключены к выходам соответственно первого и второго разрядов блока постоянной памяти, выходы третьего четвертого, пятого и 15 шестого разрядов которого подключены к управляющим входам соответственно третьего и четвертого узлов памяти, первого и второго коммутаторов 11-го : 1,К) вычислительного блока, 20 первые информационные входы первого и второго коммутаторов 1-го (.=1,-1) вычислительного блока подключены к информационным выходам соответственно первого и второго узлов памяти .25 (+1)-го вычислительного блока, первый информационный вход второго коммутатора 1 -го вычислительного блока подключен к информационному выходу первого узла памяти первого вычислительного блока, вторые информационные входы первого и второго коммутаторов (2 ш)-го (оп=1,М./2) вычислительного блока подключены к информационным выходам третьих узлов памятисоответственно т-го и (ш+1 с/2)-го вычислительных блоков, вторые информационные входы второго и первого коммутаторов 2-го (1=1,с/2) вычислительного блока подключены к информа ционным выходам четвертых узлов памяти соответственно 1-го и ( 1+1/2)-го вычислительных блоков, а арифметический узел 5-го ( =1,Е) вычислительного блока содержит умножитель, сумма тор, вычитатель и первый и второй .коммутаторы, при этом выход умножителя подключен к первым входам соответственно вычитателя и сумматора, выход которого подключен к первым инФормационным входам первого и второго коммутаторов, информационные выходы ко 1 орых подключены к информационным входам соответственно третьего и четвертого блоков памяти Б-го вычислительного блока, первый вход умножителя арифметического узла 5 -го вычислительного блока подключен к 72 4 элемент НЕ, причем информационный выход регистра сдвига подключен к первому информационному входу первого коммутатора, информационный выход которого соединен с информационным выходом второго коммутатора и с первым информационным входом первого коммутатора К-го вычислительного блока, второй информационный вход первогО коммутатора соединен с первым информационным входом второго коммутатора, с информационным входом регистра сдвига и является первым информационным входом устройства, вторым информационным входом которого является второй информационный вход второго коммутатора, управляющие входы первого и второго коммутаторов подключены к выходам соответственно восьмого и девятого разрядов блока постоянной памяти, выход десятого разряда которого подключен к,управляющему входу переключателя р-го (р=1,1 с) вычислительного блока, информационные выходы первого и второго узлов памяти р-го вычислительного блока подключены соответственно к первому и второму информационным, входам переключателя р-го вычислительного блока, первый и второй инФормационные выходы которого подключены соответственно к второму входу умножителя и вторым входам сумматора и вычислителя арифметического узла вычислительного блока, выход вычитателя арифметического узла подключен к входу элемента НЕ арифметического узла, выход которого подключен к вторым информационным входам первого и второго коммутаторов арифметического узла.На фиг.1 приведена функциональная схема устройства; на фиг.2 - функциональная схема вычислительного блока, на фиг.З - функциональная схема арифметического узла," на фиг.4 - граф алгоритма БПФ действительной последовательности для Я=16, на фиг.5 - базо7 11308 ку, может быть пост.роена на основе двух коммутаторов (фиг.6). Сигналы с выхода переключателя 9 поступают на соответствующие входы арифметического узла 8. Комплексное число уЬ+М/4) поступает на вход умножителя 12, на .другой вход которого из блока 5 постоянной памяти коэффициентов поступает соответствующее значение весового множителя Ч, зависящее от номера 1 О выборки и от номера итерации.Таким образом, на выходе умножителя 12 получается значение произведения у(1+И/4) У . Это число с выхода умножителя 12 подается на входы вычи тателя 13 и сумматора 14, на другие входы которых одновременно подается число у(к) с выхода переключателя 9. На выходе сумматора 14 получается результат уЬ)+уЬ+Н/4) Я . Резуль8тат,. полученный на выходе вычитателя 13 и равный уЬ)-уЬ+Б/4)М, поступает на вход элемента НЕ 15, который выполняет операцию комплексного сопряжения,числа, так что на его выхо де получается числоу Ь) -ч %+4 ) И, 3,й, РРезультаты с выхода сумматора 14 и элемента НЕ 15 последовательно один за другим по управляющему синхроимпульсу от блока 6 управления через 1коммутаторы 16 записываются в третий (верхний на фиг.2) и четвертый (нижний на фиг.2) узлы 10 памяти в зависимости от номера отсчета обрабатываемой последовательности, причем в35 третий узел 10 памяти записываются взвешенные сумма и разности первой половины вычислительных результатов, в четвертый - вторая половина.МПосле - тактов вычислений содер2жимое третьих и четвертых узлов 10 памяти переписывается соответственно в первые и вторые узлы 7 памяти соответствующих блоков (через коммутатор 45 11 по управляющему синхроимпульсу с блока 6 управления. Это позволяет проводить обработку информации во всех последующих итерациях аналогично описанной;50Блок 6 управления может быть построен по любой из известных схем в зависимости от задач, для решения которых используется устройство быстро-. го преобразования Фурье.55Один из возможных вариантов построения блока 6 управления приводится на фиг7, Блок 6 управления состо 72 8ит из генератора 17 тактовых импульсов, сигнал от которого подается на счетчик 18 адреса, В зависимости от состояния счетчика на выходе блока 19 постоянной памяти формируются необходимые управляющие сигналы. На фиг.9 показан вид управляющих сигналов, которые формируются на выходе блока 19 для управления переключателем 9 (в режиме обработки действительного сигнала), коммутаторами 11, 16 и управляющие сигнзлы на запись и считывание узлов 7 и 10 памяти.По управляющему сигналу на коммутатор 11 (сигнал а на фиг.9) в режиме входной информации пропускаются сигналы, поступающие на входы вычислительных блоков (4-1-4-к) для записи в узлы 7 памяти (по управляющему сигналу оо на фиг.8),. Далее при выполнении вычислений коммутаторы 11 пропускают сигналы, поступающие.на входы всех вычислительных блоковПроцесс вычислений на каждой итерации можно разбить на два этапа. На первом этапе по управляющему сигналу считывания (сигнал Ь на фиг.9) производится считывание информации из первого и второго узлов 7 памяти и выполняются базовые операции в арифметическом узле 8, На этом же этапе первая половина результатов вычислений, получаемых на выходе арифметического узла 8, по управляющему сигналу записи (сигнал г на.фиг.8) записывается в третий узел 10 памяти, а вторая половина записывается в четвертый узел 10 памяти по управляющему сигналу 3 на фиг.8. Коммутация информации между третьим и четвертым узлами 10 памяти осуществляется коммутаторами 16 о управляющему сигналу на фиг.8. Поскольку за время считывания числа из блока 7 памяти в один из узлов 10 памяти должны записываться два числа, то частота записи в узлы 10 памяти должна быть в 2 раза больше, чем частота считывания из узла 7 памяти (фиг.8). На втором этапе производится перезапись результатов вычислений из узлов 10 памяти в узлы 7 памяти в соот- ветствии со схемой фиг.1. При этом управляющий сигнал считывания из узлов 10 памяти имеет такой же вид, как и сигнал записи в узлы 7 памяти (сигнал 6 на фиг.8).9 1130По управляющему сигналу (сигналжна фиг.й) на переключателе 9 в режиме обработки действительной последовательности выполняется перестановкамнимой части числа у(к) и действи-,тельной части числа уй+-), В=О1)ипоступающих на переключатель 9 изузлов 7 памяти при выполнении базовыхопераций со значением весового мно. 10жителя Ы. Так на первой итерациибудет осуществляться перестановка8каждой пары чисел уЬ), у(к+-) Ь=9=0- - -1) поскольку на этой итерацииР 4 й1 Свсе базовые операции выполняются созначением весового множителя И . Всоответствии с графом на фиг.4 с увеличением номера итерации на единицучисло базовых операций с весовым 20множителем И уменьшается в 2 разапоэтому во столько же раз должноуменьшаться число перестановок, осу ществляемых переключателем 9,На основании приведенного изложения и временной диаграммы Фиг.8 производится запись информации в блок 19для получения необходимых управляющих сигналов. Причем для формированиякаждого сигнала необходимо И+Ь ячеек 30памяти, где ш - число итераций алгоритма БПФ, 1=И/к. В блоке 19 информация распределяется по ячейкам памяти следующим образом: в разрядепредназначенном для формирования управляющего сигнала на коммутаторы 11,в ячейки памяти с адресами =0,1Ызаписывается "1", а в остальные -"0", в разряде, предназначенном дляформирования управляющих сигналов за писи блоков 7 памяти и считыванияблоков 9 памяти, в ячейки памяти садресами 41-1, 4 хИ=1,2,И/4),4 х+И+-+ Ос+1) , 4 з.-1+И+-+ Ос) Ь(3. ф=(1=1,2,-, 1 с=1,2. ш) записывается "1", а в остальные - "0".В разряде, предназначенном дляФормирования управляющего сигналасчитывания блоков 7 памяти, в ячейки памяти с адресами 4 з.-2+И+(ш)Ь4.-1+Я+(ш)фЬ (1.=1,-) Ос=1,ш).запи 9сывается "1", а в остальные - "О". 872 10 в разряде, предназначенном для формирования управляющего сигнала записи третьего блока 10 памяти, в ячейкипамяти с адресами 2+1+И+В+1)Ь(1=1, Ь/4-1, 1=1,щ) записывается "1", а в остальные - "0", в разряде, предназначенном для Формирования управляющего сигнала .записи четвертого блока10 памяти, в ячейки памяти с адреса.ю тми 2 х+1+Н+-+Ь)ф Ь (1=1, Ь/4-1; 1 с=1,ш) записывается "1", а в остальные -"О", в разряде, предназначенном дляФормирования управляющего сигналакоммутаторами 16, в ячейки памяти садресами 1+(и)Ь+И(=О,Б/4-1; 1 с=1,ш)записывается "1"., а в остальные -"О", в разряде, предназначенном дляФормирования управляющего сигналапереключателем 9, в ячейки памяти садресами 1=И+И)Ь, И+1+Ос)ЬК+(1 с) Ь+Ь/2 -1 (к=1,ш) записывается "1", а в остальные - "0",В случае обработки комплексной последовательности по внешней командевся входная информация поступает через коммутаторы 1 и 3 непосредственнона первый вход -го вычислительногоблока. По этой же команде перестановка мнимой части числа уЬ) и действительной части числа у(к+И/4) переключателем 9 не производится и не выполняется операция комплексного сопряжения числа на выходе вычитателя 13.Окончательный результат М/2 коэфФициентов дискретного преобразованйя Фурье входного сигнала получается после иитераций, записанными в третьи и четвертые узлы 10 памяти К вычислительных блоков, ПорядЬк записи результатов вычисления преобразования Фурье действительной входной последовательности отличается от нормальногои является стандартным для такоготипа графов,Таким образом,использование предлагаемого изобретения позволит сократить более чем в 2 раза время обработки действительного сигнала и вдвое уменьшить объем памяти вычислительных блоков. При этом уменьшается стоимость устройства и повышается его йадежность.