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

Изобретение относится к вычислительной технике и предназначено для спектрального анализа электрических сигналов, представленных в цифровой форме, в реальном масштабе времени. Применение изобретения связано с цифровой обработкой электрических сигналов с изменяющейся во времени частотой среза, к которым относятся такие сигналы, как, например, речевой сигнал в аппаратуре связи, сигна лы гидро-,звуко-и радиолокации, нави гации и телеметрии. По основному авт.св. 615488 известно устройство для реализации быстрого преобразования Фурье, содержащее блок памяти, состоящий из N регистров сдвига, арифметический блок, блок памяти коэффициентов, первые и вторые элементы И и элементы ИЛИ,- причем параллельные входы /N - 1)-го и (N -1)-го регистров сдвига соединены соответственно с первым и вторым выходами арифметичес кого блока, а параллельные выходы - N нулевого и - -го регистров сдвига соединены соответственно с первым и вторым,входс1ми арифметического блока третий и четвертый вх,оды которого соединены соответственно с выходами блока памяти коэффициентов, последовательный вход каждого регистра сдви га подключен к выходам соответствующе1го элемента ИЛИ, а выход - к первым входам первого и второго соответствующих элементов И, выходы первых элементов И каждого регистра сдвига, за исключением нулевого и -J- -го регистров сдвига, соединены с первыми входами элементов ИЛИ предвдущих регистров сдвига,выход элемента И i-ro регистра сдвига соединен с вторым входом элемента ИЛИ J-го ренистра сдвига, где j - двоичный код, полученный путем цикли ческого сдвига на один разряд влево двоичного кода i, вторые входы всех первых и вторжк элементов И соединены соответственно с первым и вторым тактовыми входами устройства El. Недостатком известного устройства является ограниченное быстродействие которое не повышается с понижением частоты среза сигнала, в результате чего отсутствует возможность работы устройства с повышенным быстродействием для реально существующих сиг.налов. Цель изобретения - повышение , быстродействия устройства при обработке сигналов с переменной частотой среза. Поставленная цель достигается тем, что в устройство для реализации быстрого преобразования Фурье введены счетчик, реверсивный счетчик, элемент НЕ, четыре элемента ИЛИ и два элемента И, причём выход переноса бчетчика соединен с вычитающим входом реверсивного счетчика, выход первого разряда которого подключен к входу элемента НЕ, выход которого соединен с первым входом первого элемента ИЛИ, выход которого соединен с первым входом второго элемента ИЛИ, выход которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с первыми входами первого и второго элементов И, выходы которых соединены с первым и вторым тактовыми входами устройства, соответственно выход второго разряда реверсивного счетчика подключен к второму входу первого элемента ИЛИ, выходы третьего-и четвертого разрядов реверсивного счетчика соединены соответственно с первым и вторым выходами четвертого элемента ИЛИ, выход которого подключен к второму входу второго элемента ИЛИ, второй вход первого элемента И является первым тактовым входом устройства, второй вход второго элемента И объединен с тактовым входом счетчика и является вторым тактовым входом устройства, а второй вход третьего элемента ИЛИ является входом задания частоты среза устройства. На фиг. 1 изображена функциональная схема предлагаемого устройства; на фиг. 2 - пример реализации блока вычисления предпоследней итерации и блока отключения. Устройство-для реализации БПФ сигналов с переменной частотой среза содержит блок 1 памяти, состоящий из N регистров 2 сдвига, арифметический блок 3, блок 4 памяти коэф- . фициентов, элементы И 5 первой группы, элементы И 6 второй группы, элементы ИЛИ 7, блок 8 отключения, блок 9 вычиЬления предпоследней итерации, первый 10 и второй 11 входы устройства и вход 12 задания частоты среза. Блок а отключения содержит эле- мент ИЛИ 13 и элементы И 14 и 15. Блок 9 вычисления предпоследней итерации содержит счетчик 16, реверсивный счетчик 17, элементы НЕ 18 и ИЛИ 19-21. Устройство работает следукядим образом. В арифметический блок 3 по первому и второму входам из нулевого и регистров 2 сдвига поступают выборки сигнала,а по третьему и 4eTJ вертому входам из блока 4 памяти коэффициентов поступают коэффициенты вида, cos (2JrVN) Sin (2 ffc/N) и (,-| -1) Арифметический блок 3 осуществля ет вычисление двухточечного БПФ, результаты которого с первого и вто ( -1)и :РОГО ВЫХОДОВ ЗЗНОСЯТСЯ В (N-l)-e регистры 2 сдвига по. их параллельным входам. Одновременно на этапе вычисления двухточечного БПФ в арифметическом блоке 3 под действием тактовых импульсов ТИ 1/ поступающих с выхода блока 8 отключения на вторые входы всех первых элементов И 5, выполняется сдвиг вверх на одну ступень всех выборок сигнала, размещенных в регистрах 2 сдвига и к моменту времени записи результата из арифметического блока N 3 в ( - 1) и (N -1)-е регистры 2 2 сдвига выборки сигнала из этих реги ров 2 сдвига перезаписи в предаадущи (-2 - 2) и (N . - 2)-е регистр 2 сдвига соответственно, поэтому потери информации в регистрах 2 сдвига не происходит. Этот этап вычисления происходит на каждой ите, : - ; Ы . рации раз. После выполнения каж дой итерации в соответствии с алго.ритмом ВПФтребуется выполнить переупорядочивание информации, кото рое осуществляется под действием тактовых импульсов ТИ 2, поступающих с второго выхода блока 8 отключения на вторые входы всех вторых элементов И б. При этом последова тельный выход регистра 2 сдвига с номером i через соответствующие вто рые элементы И б и элементы ИЛИ 7 соединен с последовательным входом регистра 2 сдвига с номером j, двоичный код которого образуется путем циклического сдвига на один разряд влево двоичного кода ii Элементы ИЛ 7 выполняют объединение выходов соответствующих первых и вторых элементов И 6 и тем самым обеспечивеиозг поступление данных на последователь ный вход регистра 2 сдвига в режиме сдвига инфо1 1ации вверх и в режиме переупрядочивания информации. Отличительной особенностью азлич ныхЯчеек, состоящих из регистра 2сдвига, первого и второго элементов И 5 и 6 соответственно и элемента : ИЛИ 7, является отсутствие в нулево N И ячейках первых элементов И N И в ( -1) и (Ы-1)-й ячейках эле2, . . ментов ИЛИ 7, которое является след ствием самого алгоритма БПФ. Rufi вы полнени-я перезаписи информации в. регистрах 2 сдвига с п разрядами требуется п тактовых импульсов/ поэтому тактовые импульсы как ТИ 1, так и ТИ 2 состоят из групп по п импульсов в каждой группе. Для вычисления БПФ последовательно поступает серия из групп тактовых импульсов ТИ 1, затем одна группа тактовых импульсов ТИ 2 и далее процесс повторяется m раз,где m(,N),число итераций. Результаты вычисления БПФ содер-жатся в регистрах 2 сдвига в двоичноинверсном порядке. В процессе вычисления БПФ после вычисления предпоследней (т-1)-й итерации в верхней : половине (О-(-у -1))-х регистров 2 сдвига возникает результат, который соответствует вычислению БПФ от вы-iборок сигнала прореженных во времени, т.е. от четных выборок. Этот результат получается за счет вычисления БПФ с числом точек преобразования в два раза меньшим, .чем исходное число точек БПФ. Такой промежуточный результат вычисления БПФ также представлен в двоично-инверсном порядке, В нижней половине (М-1))-х регистров 2 сдвига содер-жится результат вычисления БПФ от нечетных выборок сигнала тоже в явоично-гинверсном порядке. Проредсивание выборок сигнала по времени Эквивалентно понижению частоты дискретизации аналогового сигнала, поэтсму для сигналов с переменной во времени частотой среза возможно и достаточно выполнять вычисление БПФ до конца предпоследней (т-1)-й итерации при условии, если частота среза сигнала становится меньше половины исходной частоты среза. Такая ситуация возникает в случае, когда аналоговый сигнал дискретизирован из расчета на максимально возможную частоту среза сигнал.а. Тогда возможно при наличии сигнала половинной частоты среза после вычисления предпоследней (га-1)-й ите- . рации БПФ получить спектр Фурьесигнала, полностью без какойлибо погрешности наложения спектра представляет этот сигнал в частотной области. Момент времени поступления .сигнала половинной частоты среза в устройстве для реализации БПФ сигналов с переменной частотой среза возможен в период времени вычисления БПФ, но этот сигнал должен поступить к моменту времени окончания вычисления предпоследней (т-1)-й итераЦии Спектр Фурье-сигнала, полученный после вычисления предпоследней (т-IJ-й итерации БПФ, полученной при поступлении сигнала половинной частоты среза, имеет такую же разреагиощую полосу частот, как и спектр, который получался бы после вычисления и последней (т)-й итерации от всех четных и нечётных выборок сигнала. Поэтому с точки зрени равноценности получаемого спектра нет отличия между Ъпектром Фурье, получаемым на предпоследней {т-1)-й итерации БПФ при утвердительном значении сигнала половинной частоты среза, и спектром Фурье, получаемом на последней (т) -и итерации БП4 при отрицательном значении сигнала половинной час тоты.среза. Отличие состоит в том, что спектр Фурье, вычисленный на предпоследней (гаг1)-й итерации, получается раньше во времени по отношению к спектру Фурье, вычисленному на последней (т)-и итерации. В устройстве для реализации БПФ сигналов с переменной частотой среза для определения предпоследней (т-1)-й итерации используется блок 9 вычисления предпоследней (т-1)-й итерации, который осуществляет под счет групп тактовых импульсов ТИ 2, т.е. подсчет числа итераций. При подсчете итераций в блоке 9 вычисли НИН предпоследней итерации, когда заканчивается выполнение предпослед ней (т-1)-й итерации, на его выходе появляется сигнал, которалй поступает на четвертый вход блока 8 отключения. В блоке 8 отключения происходит отключение подачи тактовых импульсов ТИ 1 и ТИ 2, в том случае когда одновременно присутствует сигнал половинной частоты среза и сигнал на выходе блока 9 вычисления предпоследней (т-1)-й итерации. В противном случае при отсутствии хот бы одного из этих сигналов тактовые импульсы проходят без изменения.с первого 10 и второго 11 тактовых входов блока 8 отключения на его первый и второй выходы соответствен но. Конец вычисления БПФ наступает после окончания поступления тактовы импульсов ТИ 1 и ТИ 2 либо после вы числения предпоследней (т-1)-и итерации в случае утвердительного зна чения сигнала половинной частоты среза,, либо после вычисления послед ней (т)-и итерации при отрицательно значении половинной частоты среза. Результаты спектра Фурье, вычисленные по алгоритму БПФ, в случае, когда j )процесс вычисления заканчивается на предаосяедней (ш-1)-й итерации, рас полагаются в двоично-инверсном порядке в верхней половине (0-()) регистров сдвига, когда же выполняется и последд(няя (т)-я итерация, то да результаты занимают полностью все регистры 2 сдвига и тоже располагается в двоично-инверсном порядке. .. В блоке 9 вычисления предпоследней (т-1)-и итерации выполняется деление тактовой последовательности импульсов ТИ 2 на (D1), подсчет числа итераций, оставшихся выполнить до концавычисления НПФ , и выделение предпослё; ней итерации. Деление тактовой последовательности ТИ 2 на осуществляется счетчиком 16, в результате чего получается последовательность им1 ульсов выполненных итераций БПФ, которая подсчитывается реверсивным счетчиком 17, куда предварительно записано общее число всех итераций (т) БПФ. Вычитание числа поступающих импульсов выполненных итераций от их общего значения (т), выполняемое в реверсивном счетчике 17, позволяет получить значение оставшихся выполнить итераций. Этот результат и отражается на выходе реверсивного счетчика. Элементы 18-21 фиксируют на счетчике 17 оставшуюся невыполненной последнюю (1п)-ю итерацию, что свидетельствует об окончании вычисления предпоследней (гп-1)-й итерации, т.е. когда значение в счетчике 17 равно единице, на выходе элемента ИЛИ 21 и, следовательно, на выходе блока 9 вычисления предпоследней (т-1)-и итерации появляется сигнал логического нуля, КОТО1Ж1Й соответствует окончанию вычис.пения предпоследней (т-1)-й итерации. В блоке 8 отключения с помощью элемента ИЛИ 13 выполняется объединение двух сигналов: с выхода блока 9 вычисления предпоследней (т-1)-и итерации и с входа 12 задания частоты среза. Выход элемента ИЛИ 13 далее управляет отключением тактовых импульсов ТИ 1 и ТИ 2, подавае- мах соответственно на первый 10 и второй 11 входы устройства через элементы И 14 и 15. Технико-экономическая эффективг ность предлагаемого устройства заключается в повышении быстродействия при вычислении БПФ для сигналов с переменной частотой среза за счет окончаная вычисления ВПФ на предпоследней (т-1)-й итерации при поступлений сигнала половинной частоты среза. Для сигналов, например, имеющих во времени равномерную плотность распределения частоты среза, имеем, что за промежуток времени t сигнал половину времени (0,5й) имеет частоту среза меньшую половины исходной частоты среза, поэтому вычисление БПФ в данные интерватш времени выполняется только до конца предпоследней (т-1)-и итерации, быстродействия при вычислении БПФ только до конца предпосл ней (т-1)-и ите- . рации заключается в невыполнении последней (т)-и итерации и равно г1 1 -± 1 1 Л -гп-- Повышение быстродействия устройства для данного закона распределения Частоты среза сигнала равняется ,51f j. m - Для примера восьмиточечного БПФ повышение быстродействия равняется 0,,6% ,5 0,,6%), для случ 1024 точек преобразования БПФ ,0 f Г ff tl 0.5 0,05 5%), 10 Оценивая дополнительные аппаратурные затраты, следует, что для блока 9 вычисления предпоследней (т-1)-й итерации и для блока 8 отключения требуются всего две микросхемы К155ИЕ7, одна микросхема К155ЛЛ1, один элемент НЕ из микросхемы К155ЛН1 и два элемента 2И из микросхемы К155ЛИ1. Дополнительные аппаратурные затраты по сравнению с общим объемом оборудования, необходимым для вычисления БПФ, являются совершенно иезначительными, однако введение дополнительных узлов позволяет увеличить быстродействие предлагаемого устройства на 5 - 15%.

УСТРОЙСТВО;ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ПО авт.СВ. 615488, отличающееся тем, что, с целью увеличения быстродействия при обработке сигналов с переменной частотой среза, в него введены счетчик, реверсивный счетчик, элемент НЕ, четыре элемента ИЛИ и два элемента И, причем выход переноса счетчика соединен с вычитгоовдим входом реверсивного счетчика, выход первого разряда которого подключен к входу элемента НЕ, выход которого соединен с первым входом первого элемента ИЛИ, выход которого соединен С первым входом второго элемента ИЛИ, выход которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с первыми входами первого и второго элементов И, выходы KOTOjxjx соединены соответственно с первым и вторым тактовыми входами устройства, выход второго разряда реверсивного счетчика подключен к второму входу первого элемента ИЛИ, выходы третьего и четвертого разрядов реверсивного счетчика соединены соответственно с первьил и йторым входами четвертого элемента ИЛИ, выход которого подключен к второму входу второго элемента ИЛИ, второй вход первого элемента И является так товым входом устройства, второй вход второго элемента И-объединен с тактовым входом счетчика и является вторым 2 тактовым входом устройства, а второй вход третьего элемента ИЛИ является i входом задания частоты среза устройства.