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

Иллюстрации

Показать все

Реферат

 

О П И С А Н И Е (» 506883

ИЗОБРЕТЕН ИЯ

CoIo3 СО етских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 05.04.74 (21) 2013373/18-24 (51) М. Кл G 06F 15/34 с присоединением заявки ¹â€” (23) Приоритет—

Опубликовано 15.03.76 Бюллетень № 10

Дата опубликования описания 3.01.77

Государственный комитет, Совета Министров СССР оо делам изааретений и открытий (53) УДК 681.323 (088.8) (72) Автор изобретения (71) Заявитель

М. А. Рабинович

Ордена Октябрьской Революции Всесоюзный госу проектно-изыскательский и научно-исследовательск энергетических систем и электрических се

«ЭНЕРГОСЕТЪПРОЕКТ» (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ

ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЪЕ

Изобретение относится к вычислительной технике и может быть применено для вычисления дискретного преобразования Фурье (ДПФ) последовательности элементов.

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

Фурье, содержащие арифметический блок, соединенный с блоком памяти, вход которого подключен к выходу блока инверсной перестановки, входной блок памяти, соединенный со входом устройства, блок памяти тригонометрических функций, первый выход которого подключен ко входу арифметического блока. В известных устройствах обычно для вычисления коэффициентов ДПФ используются методы реализации быстрого преобразования

Фурье (БПФ) Однако при нахождении небольшого количества коэффициентов методы

БПФ оказываются экономически невыгодными, так как часть вычисленных коэффициентов отбрасывается за ненадобностью, но на их вычисление затрачивается дополнительное время.

Целью изобретения является повышение быстродействия устройства. В описываемом устройстве это достигается тем, что в него введены сумматор и блок умножения, входы которого соединены соответственно с выходом входного блока памяти и вторым выходом блока памяти тригонометрических функ2 ций, выход подключен ко входу блока инверсной перестановки, выход блока памяти через сумматор подключен к выходу устройства, что позволяет сократить непроизводительные затраты времени на вычисление коэффициентов.

На фиг. 1 представлена схема описываемого устройства; н а ф и г. 2 — направленный граф, поясняющий работу устройства при вы 0 числении определенного числа коэффициентов.

Устройство содержит входной блок памяти 1, блок 2 умножения, блок 3 памяти тригонометрических фу акций, блок 4 и инверсной

15 перестановки, блок 5 памяти, арифметический блок б, сумматор 7, вход 8 и выход 9.

Исходная последовательность элементов, от которой вычисляется часть коэффициентов преобразования Фурье, поступает в блок 1 и

20 затем на первый вход блока 2 умножения, на второй вход которого поступают значения тригонометрических функций из блока 3 памяти тригонометрических функций. Выход ной сигнал блока 2,поступает,в блак 4 ин25 версной перестановки, в котором выполняется перестановка поступающей последовательности элементов согласно двоичной инверсии номеров этих элементов. Упорядоченные таким образом элементы последовательности

3р поступают в блок 5 памяти и над этими элегде А = (АО,A»..., Ал i ) — вектор коэффициентов Фурье; х = (хо, х1 хх i ) — вектор исходной последовательности элементов.

О„О „О „О1О о)оо)1и2

О)ОО)24О4,, 2(,Ч вЂ” i) о Ло 1„2<у 1> „!Х < (2) 2Л;

„o)=е— матрица преобразования.

Ограничимся случаем У=2, р = О, 1, 2,...

Метод быстрого преобразования Фурье сводится к факторизации матриць: преобразования W и представлению ее с точностью до порядка расположения строк в виде

W = R0 Ri где

ЛО

Л1

R.—!

Л /

i=:0,1,, р — 1 (4) 1 (в — o)

Ч л, к=0,1, ...,2 — 1 (5) О) — 40

I . 1 и, вместо пропусков, в матрицах R; и л), под р азумев а ются нулевые элементы.

Пусть требуется определить первые М коэффициентов А;, i=0 1, ..., М вЂ” 1, где М удовлет1во1ряет условию

3 ментами и значениями тригонометрических функций из блока 3 арифметический блок 6 выполняст стандартные арифметические операции типа умножения и сложения. К выходным каналам блока 5 памяти подключен сумматор 7, число каналов которого равно отношению количества элементов исходной последовательности к минимально возможной целой положительной степени двух, равной или превосходящей число требуемых коэффициентов преобразования Фурье.

Аргумент тригонометрических функций, поступающих на второй вход блока 2, зависит от сдвига требуемых коэффициентов относительно нулевого коэффициента и в том случае, когда искомая часть коэффициентов расположена начиная с нулевого элемента, блок 2 не участвует в работе.

Дискретное преобразование Фурье последовательности х„, n=0,1,..., Л = 1 равномерно расположенных элементов дается выражением

А W x, (1)

1 )1

506883

4 (М"

2О - -1 2О (6) Введем -й шаг вычислительной процедуры в виде

5 в„;= Rp. ° в где Вр i= R„ i x (7)

i=2,3, ..., р

Если на q-м шаге будет найден вектор

В,, „= (bo, b» ..., b;: 1 ), то за оставшиеся р — q шагов будет найден вектор В„ = А =

= (АрА)Ал .i ) такой, что р -q- 1

А,-- Ь лп,;

/=о

i=0,1, ..., М вЂ” 1 (8) 15 и затем выполняются описанные выше вычисления. Требуемые М коэффициентов дискретного преобразования Фурье будут расположены начиная с нулевого элемента.

Формула изобретения

Устройство для вычисления коэффициентов дискретного преобразования Фурье, содержащее арифметический блок, соединен55 ный с блоком памяти, вход которого подклюТаким образом, в том случае, когда тре20 буется определить только первые М коэффициентов, последние р — д вычислительных шагов в классическом методе быстрого преобразования Фурье можно вычислять по формуле (8). При этом на вычисление вектора А

25 из Вр, потребуется N операций комплексного сложения, вместо примерно — У (р — V) арифметических комплексных операций типа сложения и умножения при обычном методе

Зр вычисления.

На фиг. 2 показан направленный граф рассмотренного выше метода для N=8 и

М=2. Здесь перестановку входных элементов согласно двоичной инверсии их номеров сле35 дует провести перед началом вычислений, затем необходимо выполнить один шаг классического метода быстрого преобразования

Фурье и, наконец, вычислить суммы (8).

Сплошные линии на фиг. 2 обозначают опе40 рации сложения, линии со стрелками на концах — операцию умножения, Показатели степени, взятые в 1кружки, оз1начают, что для получения показателя степени при o) необходимо выполнить двоичную инверсию над номе45 ром, стоящим в кружке.

Тот случай, когда требуется вычислить последовательность коэффициентов, расположенных подряд начиная с к-го номера сводится к уже рассмотренному с помощью ди5р скретного аналога теоремы сдвига, При этом, исходная последовательность элементов должна быть умножена на ехр

506883

9 иг 1

Д1 х,. х, Составитель Н. Жеренов

Техред Т. Колесова

Корректор H. Аук

Редактор Л. Тюрина

Заказ 4907 Изд. № 1192 Тираж 864 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, 7К-35, Раушская наб., д. 4/5

МОТ, Загорский филиал

5 чен к выходу блока инверсной перестановки, входной блок памяти, соединенный со входом устройства, блок памяти тригонометрических функций, первый выход которого подключен ко входу арифметического блока, отличаюгцееся тем, что, с целью повышения быстродействия, в него введены сумматор и

6 блок умножения, входы которого соединены соответственно с выходом входного блока памяти и вторым выходом блока памяти тригонометрических функций, выход подключен ко входу блока инверсной перестановки, выход блока памяти через сумматор подключен к выходу устройства.