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

1

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

Цель изобретения - уменьшение пог решности при вычислении спектра.

Базовая операция для УДПФ имеет вид. д,

X

Y X-Y-W 5, где кП - блютайшее целое от деления . 21Tk HaotN, причем соответствует номеру )ициен- та операции обычного БПФ; exp(--j(x ,).

При использов ании интерполятора формула принимает вид

X X + ()е,(2)

Y X - (YVOg,

11Ъ. (3)

где

причем

{Yl 0; {(nO;.,4™) )/2,.

к1

(YI-OO (4)

(Y1.J),((, (.5). где 1 - требуемое число шагов интерполяции;i - шаг интерполяции;

- ближайшее меньшее целое от деления на о.М2 ;

Lk;,j- ближайшее большее целое от деления 2Trk на txiN2 .

На фиг. 1 представлена блок-схема устройства, на фиг. 2 - блок-схема блока вычисления целой части; на фиг. 3 - блок-схема арифметического блока; па фиг. 4 - блок-схема интерполятора; на фиг. 5 - временные диаграммы работы.

Устройство (фиг.1) содержит входные регистры 1-4, коммутатор 5, блок 6 памяти, регистры 7 i-i 8, блок 9 памяти константы, блок 10 вычисления целой части числа, сумматор-вычи- татель 11, арифметический блок 12, сумматор 13, интерполятор 14 и коммутатор 15.

Блок IО вычисления целой части (фиг. 2) содержит регистр 16, логический элемент ИЛИ 17, сумматор 1 8 и коммутатор 19.

Арифметический блок 12 (фиг.З) содержит регистры 20 и 21, сумматор 22, регистры 23-26, коммутатор 27 и сумматор-вычитатель 28.

Интерполятор 14 (фиг. 4) содержит коммутатор 29, регистр 30 сдви788882

га, логические элементы 31 и 32 сов- надениЯ; регистры 33 и 34, сумматор , 35 и логический элемент ИЛИ 36.

Устройство дг;я выполнения базовой 5 онера1,ии быстрого преобразования Фурье работает следуюгцим образом. Управляюи№П-ш сигналами У( У в регистры 1-4 записываются действительные и мнимые части операндов

JO

X и У, после чего устройство реали15

зует выполнение базовой операции (2/ с учетом (з - (5 . С выходов регистров 3 и 4 входные операнды побайтно подают на младшие разряды адреса блока 9 памяти через коммутатор 5, Который управляется сигналами У, и 26.

Блок 6 намяти выдает номер коэф2Q фициента k, который поступает на регистр 16 блока вычисления целой части 10 и записывается управляющим сигналом Уд. На начальных итерациях алгоритма БПФ, когда не требуется

25 округления k, т.е. все шaдшиe разряды равны О, коммутатор 19 подключает старшие разряда регистра 16 к второму входу сумматора 13. При этом на выходе логического элемента

30 ЮТ- 36 в интерполяторе 14 вырабатывается потенциал логического О, который управляет коммутатором 15. На втором выходе блока вычисления целой части вырабатывается код интерполяции (младшиа разряды регистра 1 б). Если требуется интерполяция результатов произведений второго операнда на синусно-косинусные коэффициенты, т.е. в младших разрядах сутствуют логические ед н1ицы, то включается в работу сумматор 18. На один вход сумматора 18 подаются старшие разряды k с регистра 16 (что соответствует ближайшему меньшему дело му от деления 2 H k на ciN,, а на младший разряд второго входа - выход логического элемента ИЛИ 17. На выходе , сумматора 18 получается блгокайшее целое от деления 2 ii K на У,N, которое

JQ подключается к второму входу сумматора 13 через коммутатор 19. На соот- ветствуюишй разряд первого входа сумматора 13 подается управляющий сигнал Уд ,, а его выход подается на стар шие разряды адреса блока 9 памяти, причем нри У|5 О осуществляется извлечение результатов произведения входных операндов на действительные коэффициенты, а при Уг 1 - на мни35

мые. С выхода блока 9 памяти результаты подаются на регистры 20 и 21 арифметического блока.

Арифметический блок 12 при пода-- че управляющих импульсов и У,, выполняет математическую операцию

Re(TO) (W) +(™) (Y%7)

.( /2«j Zm(Y) () 4-(W)/2 (Yw ) + + (YV/ ) /2«,

где (YW)- реззшьтат умножения старшего байта операнда Y на

« 5

( - результат т-пшжепия младшего байта операнда Y на W;

означает, что берется мпй- мая часть числа.

С выхода арифметического блока 12 если не .требуется интерполяция, действительная и мнимая части произведения поступают на регистры 7 и 8 произведений через коммутатор 15; если требуется интерполяция, то промежуточные результаты подаются lui второй вход коммутатора 29 интерполятора 14. В регистр 30 сдвига сигналом записывается код интерполяции, поступающий с младших разрядов регистра 16 блока вычисления целой части. Под воздействием сигнала У, код интерполяции начинает сдвигаться в сторону старших разрядов. Старший разряд регистра 30 сдвига подается на ин}зерсньм вход логического элемента 31 совпадения и на нря мой вход логического элемента 32 совпадения. На вторые входы логических элементов совпадения подается сигнал записи У. На входы регистров 33 и 34 поступают операнды с выхода ком- м татора 29, который работает в зависимости от сигнала управления У. С выходов регистров 33 и 34 операнды поступают на сумматор 35. С выхода сумматора 35 онеранды через коммутатор 29 поступают на входы регистров 33 и 34 и в зависимости от CTapaiero разряда кода интерполяции записьтаются в один из них.

Когда заканчршается интерполяция, т.е. обнулен регистр 30 сдвига, операнды через коммутатор 15 подаются на регистры 7 и 8 произведениз.

С выходов регистров 1, 2, 7 и 8 операнды поступают на сумматор-вы2788884

читате;1ь 1 I , который работает как /сумматор при У,о О и как вычитатель при У|о 1 . С выхода сумматора-вы- читателя 1 1 снимаются pesyjHiTaTbi вы- 5 числений по алгоритму (2).

Совокупность управляющих сигналов У, -У для случая четырех шаговс, интерполяции показана на фиг. 5.

15

0

5

0

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

Устройство для выполнения базовой операции быстрого преобразования Фурье, содержащее первый, второй, третий и четвертый входные регистры, информационные входы которых являются соответственно входами реальной : И МНИМОЙ частей первого операнда и реальной и мнимой частей второго операнда устройства,выходы первого авто-. рого входных регистров подключены соот- ветственн.о к первому и второму входам сумматора-вычитателя, вы ходы суммы и разности которого являются выходами соответственно первого и второго операндов устройства, выхода третьего и четвертого входных регистров подклю гены соответственно к первому и второму информационным входам первого коммутатора, выход второго коммутатора подключен к ин- формационньм входам пятого и шестого регистров, выходы которых подключены соответственно к третьему и четвертому входам сумматора-вычитателя, выход блока памяти константы подключен к.входу блока вычисления целой части числа, о т л и ч а ю щ е е - с я тем, что, с целью повышения точности, в него введены блок памяти, apиф eтичecкIШ блок, сумматор и интерполятор, информационный выход ко- jToporo подключеп к первому информационному входу второго коммутатора, второй информационный вход которого объединен с информационным входом интерполятора и подключен к выходу арифметического блока, вход которого подключен к выходу блока памяти, первый и второй адресные входы которого подключены соответственно к выходу первого коммутатора и выходу сумматора, первый вход которого подключен к информационному выходу блока вычисления целой части числа, выход младшего разряда которого под- . ключей к тактовому входу интерполятора, выход окончания интерполяции которого подключен к управляющему

5

0

5

0

5

5

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

6

U

10

го

78888 -6

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

15

20

/ /

J

Фив. 1

JU

.2

-7

Фиг.З

.

.

y J lJTU Lnj LTLrLn.

n

П

-LJ LJ-1

Л

J 1 I

njlJlJTrLTLTLn

ПП

титлrinjiji

гиишлп лллл

Фмг.5

Изобретение относится к автоматике и вычислительной технике, в ;- частности к цифровой обработке сигналов, и может быть испо льзовано в устройствах спектрального анализа.-Цель изобретения - уменьшение погрешности при вычислении спектра. Поставленная цель достигаетс я за счет того, что устройство содержит четыре входных регистра, два регистра, два коммутатора, сумматор-вычислитель, блок памяти, блок памяти констант, сумматор, блок вычисления целой части, интерполятор, арифметический блок, который состоит из шести регистров, сумматора, коммутатора и сумматора- вычнтателя. 5 ил.. i (Л С ГчЭ 00 ОС 00 оо