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

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

Цель изобретения - повьппение быстродействия.

Дискретное преобразование Фурье X(k) исходного массива Х(1),

где 1 1, N, k 1, N, N ределяется формулой

2 оп-

N

ZI Х(1) ехр Т27(1

1) (k - D/N,

- -ЛРТ

(1)

или

X(k) XC(k) + TXS(k) N

z: i-i

- 1)(k -

n

XC(k) 21 X(I) cos 27-

KS(k)

21 X(I) sin 21Г (I r«

- 1) (k - D/N.

(4)

Формулы (3) и (4) показывают, чт в случае комплексных входных данных косинусные и синусные преобразования массива Х(1) вьшолняются в отдельности для реальной и мнимой ча- с:те й. Поэтому в дальнейшем полага- ют, что Х(1) содержит только вещественные числа.

Тогда вычисление XC(k) и XS(k) путем вычисления сумм и разностей

i: X(I) X(I) + X(I + M)2 ; (5)

z(i) x(i) - x(i + M/2),

I 1, M/2,

(6)

входной (выходной) массив

объема, М;

массив разностей; период нечетного транс- 55 форм4тного преобразования (НТП-N/R), R 2 , г

О, (LP - 3),

0

5

0

5

0

5 Q

сводится к нечетным трансформантным преобразованиям НТП-N/R.

Тогда косинус-коэффициенты спектра располагаются в выходном массиве в порядке возрастания номеров гармоник с первого адреса по адрес N/2 -f 1, а синус - коэффициенты гармоник спектра в порядке убывания номеров с адреса N/2 + 2 по адрес N.

Дпя определения произвольных НТП- N/R следует воспользоваться нечетными трансформантными преобразованиями более коротких периодов и трансформантным расширителем, состоящим из циклически повторяющихся двойных бабочек со спектральным расширением (СПР), исходя из установившейся терминологии.

Для стыковки H-Tn-N/2 и двух НТП- N/4 с циклически повторяющимися двой- ньгми бабочками с СПР при двоично- инверсном порядке адресов исходных данньк необходимо осуществить обмен данными.

Каждый из массивов разностей Z(I) разбивается на три части, одна из которых образует половину, а две остальных - по четверти объема исходного.

Математически нечетное трансфор- мантное преобразование описывается следующими формулами:

XC(R(2k+1) С 1ц(Н (2k+1)) +

+ C1л,2.(R(2k+1))+ j +...+Cl8(R (2k+1)) + + Z(1);

XS(R(2k+1)) 31„ (R (2k+1)) +

+ S1, (R(2k+1)) -I- (8) + ...+S1g (R{2k-H)) +

+ (-1) Z(M/4+1); I M 4P

C1u,o ((2k+1)N/M ZL Z(2IP)x

IM/P

cos(2ir(2l-1)x (9)

X (2k+1)/(M/P);

AI/4P

(2k+1)N/M Ц Z.(2IP) X

1 1

(10)

3U25708

X sin (27(2I-1)x

X (2k-t-1)(M/P));

(2k+1) -C1,p(M/4P+

-b(2k+1); C2k+1) Sl.p (M/4P+

/P + (2k-H)).

Здесь C1 M/p и Sljuip косинусные Й синусные нечетные трансформанты с периодом М/Р.

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

0(N) (LP-2)N, N 2t 8

причем из них 25% операций умножения и 75% операций сложения.

На фиг.1 представлена схема уст- ройства; на фиг.2 - схема блока синхронизации; на фиг.З - граф алгоритма.

Устройство для выполнения.дискретного, преобразования Фурье (фиг.1) со держит блок 1 памяти, коммутаторы 2-5 (операндов), регистр 6 (операндов) , блоки 7-9 регистров (операндов арифметический блок 10, умножитель 11, регистры 12 и 13 (слагаемых),бло 14 постоянной памяти, блок .15 синхронизации, информационный вход 16 устройства , информационный выход 17 устройства, выходы 18-40 блока синхронизации j входы (тактовый и запу- ска) 41 и 42 блока синхронизации.

Блок 15 синхронизации (фиг.2) со- держит элементы И-НЕ 43-48, счетчики 49 и 50, триггер 51, узлы 52 и 53 постоянн ой памяти, элементы И 54-56, элементы НЕ 57 и 58, регистр 59,элемент 60 задержки. I

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

Базовая операция 1:

Y ХО - Х1; ХО ХО + XI; Х1 Y;

10

15

20

25 30 , 35 40

. 45.

50

55

Y Х2 - ХЗ; Х2 Х2 + ХЗ; ХЗ Y.

Базовая операция 2; Y1 ХО - XI; ХО ХО + XI; Y2 - Х2 - ХЗ; Х2 Х2 + ХЗ; Y3 Х4 - Х5; Х4 Х4 + Х5; Y4 Х6 - Х7; Y6 Х6 - Х7; Р1 Y3 X СОО; Р2 Y4 X СОО; Z1 Р1 - Р2; Z2 Р1 Р2; XI Y1 + Z1; ХЗ Y1 - Z1; Х5 Z2 - Y2; Х7 Z2 - Y2;

Пазовая опеоация 3; Ml Х4 + Х5;

М2 Х6 + Х7;

Р1. М 1 X С1;

Р2 М2 X С2; .

РЗ Х5 X СЗ;

Р4 Х7 X С4;

Р5 Х4 X С5;

Р6 Х6 X С6;

Y1 Р1 - РЗ;.

514257086

Y2 PI - P5;Рассмотрим работу устройства при

выполнении трех базовых и оконеч- Y3 Р2 - Р4;ной операций. Припустим, что прис ем в регистры осуществляется в нача- Y4 Р2 - Р6;ле такта по приходу заднего фронта

синхроимпульсов 4

Z1 Y1 + Y3;Рассмотрим выполнение первой базовой операции.

22 Y2 - Y4;10 В превом такте по адресу АО,сформированному на выходе 18 блока 15

Y3 Y1 - Y3;. синхронизации, из блока 1 памяти считывается значение операнда.

Z4 Y2 втором такте по сигналу с выJ5 хода 20 блока 15 синхронизации ком- . Y ХО + Z1;мутатор 2 подключает выход блока 1

. памяти к входу регистра 6 и по сигХ4 ХО + Z1;налу с выхода 21 блока 15 синхронизации в регистр 6 принимается операнд

ХО .Y;. 20 ХО. Одновременно,по сигналу с выхода

24 блока 15 синхронизации коммутатор Y XI + Z2; 3 подключает выход регистра 6 к входу

блока 7 регистров и по сигналу с вы- Х5 XI - 2;хода 31 блока 15 синхронизации в блок

25 7 регистров принимается операнд ХО XI Y;по адресу ФО, сформированному на выходе 32 блока t5 синхронизации. Кроме

того, по адресу А1, сформированному

Y9. выходе 18 блока 15 синхронизации,

30 из блока 1 памяти считывается значе2 ус. операнда Х1.

В третьем такте по адресу А2,

сформированному на выходе 18 .блока

,15 синхронизации, из блока 1 памяти

считывается значение операнда Х2.

Одновременно по сигналу с выхода 20

блока 15 синхронизации коммутатор 2 подключает выход блЬка 1 памяти к ,

входу регистра 6 и по сигналу с выхо .Q да 21 блока 15 синхронизации в регистр 6 принимается операнд XI. Кро ме того, по сигналу с выхода 23 блока

Оконечная операция:15 синхронизации коммутатор 4 подключает выход регистра 6 к входу блоY1 ХО + XI лс регистров и по сигналу с выхода 28 блока 15 синхронизации в блок. Y1 ХО - XI;8 регистров принимается операнд Х1

по адресу ФО, сформированному на вы- Y2 Х2 + ХЗ;ходе 29 блока 15 синхронизации,

, - В четвертом такте по адресу A3, ХЗ Х2 - ХЗ; сформированному на входе 18 блока 15

синхронизации, из блока 1 памяти счиР1 XI X С01;тывается значение операнда ХЗ. Одног

временно по сигналу с выхода 20 бло- Р2 Y2 X С01;кд 15 синхронизации коммутатор 2

подключает выход блока 1 памяти к

ХО Р1 + Р2;входу регистра 6 к по сигналу с выхода 21 блока 15 синхронизации в ре- Х2 Р1 - Р2.гистр 6 принимается операнд Х2, а по

7 1

сигналу с выхода 24 блока l5 синхронизации коммутатор 3 подключает выход регистра 6 к входу блока 7 регистров и по I сигналу с выхода 31 блка 15 синхронизации в блок 7 регистров принимаетсяоперанд Х2,по адресу Ф1, сформированному на выходе 32 блока 15 синхронизации. Кроме того, по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 выполняет операцию i сложения над опрандами ХО и XI, считываемыми соответственно из блоков 7 и 8 регистро по адресам ФО, сформированым на выходах 33 и 30 блока 15 синхронизаци

В пятом такте по сигналу с выхо да 21 блока 15 синхронизации в ре- гистр 6 принимается операнд ХЗ, по сигналу с вых ода 23 блока 15 синхронизации коммутатор 4 подключает выход регистра 6 к входу блока В регистров и по сигналу с выхода 28 блка 15 синхронизации в блок 8 регистров принимается операнд ХЗ по адрес Ф1, сформированному на выходе 29 блока 15 синхронизации. Одновременно по сигналу с выхода 38 блока 15 синхронизации арифметический,блок 10 выполняет операцию вычитания над операндами ХО и XI, считываемыми соответственно из блоков 7 и 8 регистров по адресам ФО,сформированным на выходах 33 и 30 блока 15 синхронизации. Одновременно по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенного в четвертом тате сложения с выхода арифметического блока 10, этот же результат по сигналу с выхода 40 блока 15 синхро низац11и принимается в регистр 13 и записывается по сигналу с выхода 19 блока 15 синхронизации в блок 1 памяти по -адресу АО, сформированному на выходе 18 блока 15 синхронизации

В шестом такте по сигналу с выхода 38 блока 5 синхронизации арифметический блок 10 выполняет операцию сложения над операндами Х2 и ХЗ считываемыми соответственно из блоков регистров .7 и 8 по адресам Ф1 , сформированным на выходах 33 и 30 блока 15 синхронизации. Одновременно по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в пято такте операции вычитания с выхода арифметического блока 10, этот же

8

0

5

0

5

0

5

0

5

0

5

результат по сигналу с выхода 40 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода 19 блока 15 синхронизации в блок 1 памяти по адресу А1, сформированному на выходе 18 блока 15 синхронизац1-5и.

В седьмом такте по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 вьшолняет операцию вычитания над операндами Х2 и ХЗ, считываемыми соответственно из блоков регистров 7 и 8 по адресам Ф1, сформированным на выходах 33 и 30 блока 15 синхронизации. Одновременно по сигналу с вьгхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в шестом такте операции сложения с выхода арифметического блока 10, этот же результат по сигналу с выхрда 40 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода 9 блока 15 синхронизации в блок 1 памяти по адресу А2, сформированному на выходе 18 блока 15.

синхронизации.

1 .

В восьмом такте по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в седьмом такте операции вычитания с выхода 39 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода 19 блока 15 синхронизации в блок 1 памяти по адресу A3, сформированному на выходе 18 блока 15 синхронизации.

Аналогичным образом могут быть- рассмотрены выполнения второй, третьей базовых операций и оконечной операции. Так, например, при выполнении базовых операций 2 и 3 используются также умножитель 11, блок 14 постоянной памяти, коммутатор 5 и блок 9 регистров.

Вся работа устройства дискретного преобразования Фурье синхронизируется последовательностью тактовых импульсов, поступающих на вход 41 блока синхронизации и -одновременно на счетные входы счетчиков 49 и 50,, триггера 51, один из входов элемента И 54 и вход элемента НЕ 57. Сигналы, необходимые для работы, вырабатываются блоком 15 синхронизации

после поступления на вход 42 сигнала запуска в виде короткого импульса отрицательной полярности.

В результате по сигналам с выходов триггера 51 и элемента И 54 разблокируются счетчики 49 и 50 и на выходах узлов постоянной п амяти 52 и 53 появляются соответствующие сигналы управления.

Работа завершается и блок 15 синхронизации принимает исходное состояние прк поступлении импульса с выхода узла 52 постоянной памяти на вход триггера 51. При зтом сигналами с выходов триггера 51 и элемента И 54 блокируются счетчики 49 и 50.

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

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

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

15

Ш

20

2570810

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

25

30

35

40

45

50

. 2. Устройство по П.1, о т л и - ча-ющееся тем, что-блок синхронизации содержит два узла постоянной памяти, два счетчика, триггер, регистр, три элемента И, два элемента НЕ, элемент задержки, шесть элементов И-НЕ, информационный выход первого счетчика подключен к

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

И-НЕ, выход триггера подключен к входу обнуления первого счетчика и первому входу шестого элемента И-НЕ, выход которого подключен к второму установочному входу триггера, тактовый вход которого соединен со счетными входами первого и второго счетчиков, вторым входом первого элемента К, входом первого элемента НЕ и является тактовым входом блока, входом запуска которого является второй вход

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

д

5

0

5

0

вЫход второго элемента НЕ подключен к вторым входам второго, третьего элементов И, первого элемента И-НЕ и входу элемента задержки, выход которого подключен к вторым входам с второго по пятый элементов И-НЕ, пятый выход первого узла постоянной памяти подключен к третьему входу второго элемента И-НЕ, шестой выход первого узла постоянной памяти, выход второго элемента И-НЕ, восьмой выход второго узла постоянной памятИ; выход первого элемента НЕ, девятый, десятый и одиннадца тый выходы -второго узла постоянной памяти, выход пятого элемента И-НЕ, двенадцатый и тринадцатый выходы второго узла постоянной памяти, выход четвертого элемента И-НЕ, четырнадцатый и пятнадцатый выходы второго узла постоянной памяти,выход третьего элемента И-НЕ, шестнадцатый и семнадцатый выходы второго узла постоянной памяти, седьмой выход первого узла постоянной памяти, восемнадцатый выход второго узла постоянной памяти, выходы перв ого элемента И-НЕ и третьего элемента И,

девятнадцатый выход второго узла постоянной памяти, выходы второго элемента НЕ и второго элемента И являются выходами соответственно с первого по двадцать третий блока

синхронизации.

я(зг}

Изобретение относится к вычислительной технике и может быть использовано в аппаратуре радиоэлектронной и измерительной техники. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят блок памяти 1, коммутаторы 2-5, регистр 6, блоки регистров 7-9, арифметический блок 10, умножитель 11, регистры 12, 13, блок постоянной памяти 14, блок синхронизации 15, информационный вход 16 устройства, информационный выход 1 7 устройства,выходы 18-40 блока синхронизации,тактовый вход 41 и вход запуска 42 устройства. 1 з.п. , 3 ил. (Л