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

О П И С А Н И Е (щ 506883ИЗОБРЕТЕН ИЯ Сбюз Советских Социалнсгицескии РеспубликАВТОРСКОМУ СВИДЕТЕЛЬСТВУ 61) Дополнительное к 22) Заявлено 05.04,74 вт, сви 1) 2013373/18-2 1) М,КлО 5/3 исоединением заявки У осударственный комитет,Совета Министров СССРоо делам изааретенийи открытийДата опубликования описания 3.01.77М, А. РабиновичОрдена Октябрьской Революции Всесоюзный госупроектно-изыскательский и научно-исследовательсэнергетических систем и электрических сЭНЕРГОСЕТЪПРОЕКТ 54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭффИЦИЕНТ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЪЕ 2 Изобретение относится к вычислительной технике и может быть применено для вычисления дискретного преобразования Фурье (ДПФ) последовательности элементов.Известны устройства для вычисления коэффициентов дискретного преобразования Фурье, содержащие арифметический блок, соединенный с блоком памяти, вход которого подключен к выходу блока инверсной перестановки, входной блок памяти, соединенный со входом устройства, блок памяти тригонометрических функций, первый выход которого подключен ко входу арифметического блока, В известных устройствах обычно для вычисления коэффициентов ДПФ используются методы реализации быстрого преобразования Фурье (БПФ) Однако при нахождении небольшого количества коэффициентов методы БПФ оказываются экономически невыгодными, так как часть вычисленных коэффициентов отбрасывается за ненадобностью, но на их вычисление затрачивается дополнительное время.Целью изобретения является повышение быстродействия устройства, В описываемом устройстве это достигается тем, что в него введены сумматор и блок умножения, входы которого соединены соответственно с выходом входного блока памяти и вторым выходом блока памяти тригонометрических функций, выход подключен ко входу блока инверсной перестановки, выход блока памяти через сумматор подключен к выходу устройства, что позволяет сократить непроизводительные затраты времени на вычисление коэффициентов.На фиг, 1 представлена схема описываемого устройства; на фиг. 2 - направленный граф, поясняющий работу устройства при вы.10 числении определенного числа коэффициентов.Устройство содержит входной блок памяти 1, блок 2 умножения, блок 3 памяти тригонометрических фуакций, блок 4 иинверсной 5 перестановки, блок 5 памяти, арифметический блок б, сумматор 7, вход 8 и выход 9.Исходная последовательность элементов,от которой вычисляется часть коэффициентов преобразования Фурье, поступает в блок 1 и 20 затем на первый вход блока 2 умножения,на второй вход которого поступают значения тригонометрических функций из блока 3 памяти тригонометрических функций. Выход ной сигнал блока 2,поступает,в блак 4 ин версной перестановки, в котором выполняется перестановка поступающей последовательности элементов согласно двоичной инверсии номеров этих элементов, Упорядоченные таким образом элементы последовательности з 0 поступают в блок 5 памяти и над этими элегде А =(Ао,А, А 1 ) - вектор коэффициентов Фурье;х = (х 0, х( хх 1 ) - вектор исходной последовательности элементов.=е -матрица преобразования.Ограничимся случаем У=2, р = О, 1, 2 Метод быстрого преобразования Фурье сводится к факторизации матрицы преобразования % и представлению ее с точностью до порядка расположения строк в видеР=Р 0 Л где ЛОЛ 1 Л ( 0, к=0,12 - 1 (5) О) - 40 Л . / и, вместо пропусков, в матрицах Я; и л(, подр азумев а ются нулевые элементы.Пусть требуется определить первые М коэффициентов А;, (=0,1, , М - 1, где М удовлет(во(ряет условию 3ментами и значениями тригонометрических функций из блока 3 арифметический блок 6 выполняст стандартные арифметические операции типа умножения и сложения. К выходным каналам блока 5 памяти подключен сумматор 7, число каналов которого равно отношению количества элементов исходной после. довательности к минимально возможной целой положительной степени двух, равной или превосходящей число требуемых коэффициентов преобразования Фурье.Аргумент тригонометрических функций, поступающих на второй вход блока 2, зависит от сдвига требуемых коэффициентов относительно нулевого коэффициента и в том случае, когда искомая часть коэффициентов расположена начиная с нулевого элемента, блок 2 не участвует в работе.Дискретное преобразование Фурье последовательности х , п=0,1, , Л= 1 равномерно расположенных элементов дается выражениемА ЧГх, (1)(6) Введем (-й шаг вычислительной процедуры ввиде5В(= Л.,В(,гдеВ(=Р( х (7)(=2,3, ,рЕсли на д-м шаге будет найден векторВ, = (Ь 0, Ь( ",Ь,. 1), то за оставшиесяр - (1 шагов будет найден вектор В =А"=(8) 15 и затем выполняются описанные выше вычисления, Требуемые М коэффициентов дискретного преобразования Фурье будут расположены начиная с нулевого элемента. Формула изобретения Устройство для вычисления коэффициентов дискретного преобразования Фурье, содержащее арифметический блок, соединен ный с блоком памяти, вход которого подклюТаким образом, в том случае, когда требуется определить только первые М коэффициентов, последние р - д вычислительных шагов в классическом методе быстрого преобразования Фурье можно вычислять по формуле (8). При этом на вычисление вектора А 25из Вр, потребуется Л 1 операций комплексного сложения, вместо примерно - Л( (Р - ч) арифметических комплексных операций типа сложения и умножения при обычном методе З 0 вычисления.На фиг, 2 показан направленный графрассмотренного выше метода для У=8 и М=2. Здесь перестановку входных элементов согласно двоичной инверсии их номеров сле дует провести перед началом вычислений, затем необходимо выполнить один шаг классического метода быстрого преобразования Фурье и, наконец, вычислить суммы (8).Сплошные линии на фиг. 2 обозначают опе рации сложения, линии со стрелками на концах - операцию умножения, Показатели степени, взятые в 1 кружки, оз 1 начают, что для получения показателя степени при о) необходимо выполнить двоичную инверсию над номе ром, стоящим в кружке.Тот случай, когда требуется вычислитьпоследовательность коэффициентов, расположенных подряд начиная с к-го номера сводится к уже рассмотренному с помощью ди скретного аналога теоремы сдвига, При этом,исходная последовательность элементов должна быть умножена на ехрМ506883 авитель Н. ЖереиОв Техред Т, Колесова ктор Л, Тюрина рекгор 11, Аук Изд, Мо 1192 Тираж 864 ИПИ Государственного комитета Совета Министров по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5аказ 4 ПодппснССР МОТ, Загорский филиал 5чен к выходу блока инверсной перестановки, входной блок памяти, соединенный со входом устройства, блок памяти тригонометрических функций, первый выход которого подключен ко входу арифметического блока, отличающееся тем, что, с целью повышения быстродействия, в него введены сумматор и 6блок умножения, входы которого соединены соответственно с выходом входного блока памяти и вторым выходом блока памяти тригонометрических функций, выход подключен 5 ко входу блока инверсной перестановки, выход блока памяти через сумматор подключен к выходу устройства.