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

 

ОП ИСАНИЕ

И ЗОБРЕТЕ Н ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

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

Республик (и) 509872 (61) Дополнительное к авт. свид-ву (51) М. Кл. С 06K 15/34

2 (22) Заявлено 05,04.74 (21) 2013419/18-24 с присоединением заявки № (23) Приоритет(43) Опубликовано Q5.04.76.Бюллетень № 13 (45) Дата опубликования описания 31 08.76

Государственный комитет

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

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

Ордена Октябрьской Революции Всесоюзный государственный проектноизыскательский и научно-исследовательский институт энергетических систелк и электрических сетей "Энергосетьпроект" (71) Заявитель (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

ПОСЛЕДОВАТЕЛЬНОСТИ С НУЛЕВЫМИ ЭЛЕМЕНТАМИ зом.

Изобретение относится к области вычислительной техники.

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

Однако в известных устройствах применяется метод вынислени& от последовательности, содержащей часть нулевых элементов, в котором использованы не все возможности для уменьшения времени вычислений. 15

Кроме того, в таких устройствах нулевая часть элементов должна бь:ть расположена в начальной части исходной последовательности.

Целью изобретения является повышение быстродействия устройства.

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

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

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

Устройство содержит входной блок пал яти 1, распределительный блок 2, блок 3 памяти, арифметический блок 4, блок 5 памяти тригонометрических функций, блок G инверсной перестановки, блок 7 умножения, вход 8 и выход 9 устройства.

Устройство работает следующим обре509872

1 nN1

A(Х СО п=0 . где k = О, 1, 2,..., (-11

Ели в матричной форме

А= Я) Х, 1 гдеА=(А,А,...,А ); о ..., X ) (13) 35

Х =(Х,Х о о

Ы (о (л) (л)

К) (.и Ы

g(N-1, (2) !

Ш (4) 6 N-1 2(И-1) (N-1)(И-1)

Оз ы (л .. а>

Ограничимся далее случаем, когда

N=21,P=0,1,2,..

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

F . F ... Г, (3 ) р-1 р-2" о

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

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

Для последовательности N равномерно расположенных элементов Х, 11 =

=- О, 1, 2,..., N -1. ДПФ определяется выражением о

Г=

1 й -1!! =O,X, ", Р-1 (4) Матрица, составленная из подматриц к = О, 1,".2-1

1 к (5.) -(а

1 — 0J

Х Ф О для N= О, 1,..., М-1

Х;-Одля Л=М, M+1, „) -1, где М удовлетворяет условию

< м < (6)

6+1

2, 2 1< (< p

Определим L -й шаг вычислительной процедуры в виде А = I " . А

1 где А = 1" Х; (7) (. = 1, 2,..., P-1.

Тогда результат P- g -1-го шага вычислительной процедуры можно записать в форме вектора А р q 1

Д,,,=(Х,,....,Х, „O..Î,XN,,X, „,О,...

2 2 (8), Л

N— -—

2 причем

hl,0, . (), N- — +и-1

Z 1

Хд=х = ". =Х вЂ” +П N- — +n я9 2

tl-=О,1, ", -1

Таким образом, вектор А можно р- Ю-1 образовать из вектора Х периодическим продолжением ненулевых элементов Х с где вместо нулевых элементов, как и в выражении (4 ), оставлены пропуски, Показатели степени, взятые в кружки, означают, что для получения показателя степени необходимо выполнить двойную инверсию над цифрой, записанной в кружке и представленной в двоичной форме (например, при 11 = 8 и К=Э= (011> имеет К

=<11 0)=-6) .

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

Рассмотрим теперь класс исходных последовательностей X, содержаших часть нулевых элементов, т. е. таких, как

509872 периодом

Фиг. t

N вместо выполнения

2 первых p- ) произведений (7).

Оставшаяся часть произведений (7) для i =р- ),..., р-1; может быть найдена с помощью классического метода быстрого преобразования Фурье. Как правило, операции пересылки быстры и потерей времени на их выполнение можно пренебречь.

Следовательно, выигрыш вычислительных затрат, который обеспечивает изоб- ретение, оказывается равным

P (На фиг. 2 показан направленный граф метода быстрого преобразования Фурье, реализующий описанную выше процедуру вы- 15 числений для IU = 8 и М =2. На этой фигуре сплошные линии со стрелками на концах означают умножение на Сд", линии без стрелок — сложение и пунктирные линии— операцию пересылки.

Наибольший интерес представляет случай, когда М ненулевых элементов расположены не в начале исходной последовательности и требуется вычислить ее

C)g

ДПФ. Эта задача легко сводится к уже рассмотренной с помощью дискретного àíà Io га теоремы сдвига.

П усть в последовательности из М элементов первые К элементов - HyIIene;e, следу-З1 ющие N — ненулевые и оставшиеся N -К-М также нулевые. Сдвинем эту последовательность на К элементов,так что ненулевые элементы расположатся, начиная с первого элемента всей последовательности. Затем по описанной выше методике вычислений находится ДПФ сдвинутой последовательности. Для получения ДПФ исходной последовательности достаточно полученный ряд умножить на EXP (27iI n k / N ), и= О, 1,... N -1.

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

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

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

Ар го

Х, е%,, 2 °

% ...

Х °

А °

\, 4 °

Составитель Г Дрешев

Техред g. Карандашова Корректор М. Лейзерман

РедактоР Л.утехина

Заказ 238/5 Изд. ра Я! g Тираж о - 4 Лодписиое

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

Москва, 1!3035, Раушская наб., 4

Москва, Енисейскпя ул., 2 "Гипроводхоз"