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

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

Целью изобретения является упрощение устройства за счет снижения аппаратурных затрат.

На фиг. 1 - 8 изображена структурная схема устройства для вычисления быстрого преобразования Фурье.

Устройство (фиг. 1 - 8) содержит информационный вход 1, блок 2 буферной памяти, генератор 3 тактовых импульсов, счетчик (по модулю М) 4, блок 5 постоянной памяти, вторую общую информационную шину 6, шину 7 синхронизации, блок 8 постоянной памяти, первую группу вычислительных

блоков первого типа 9.р (,А), каждый из которых состоит из сумматора 10.р, регистра (результата) 11.р, буферного регистра 12.р, триггера 13.р, первую общую информационную шину 14, группу вычислительных блоков 15.р (,В), каждый из которых состоит из триггера 1б.р, коммутатора 17.р, группы буферных регистров 18.р, k (,A), сумматора 19,р, группы б уферных регистров 20.p.k. (,A), блок 21 постоянной памяти, блок 22 умножения, третью общую информационную шину 23, третью группу вычислительный блоков второго типа 24.р (,В), каждый из которых состоит из триггера 25.р, коммутатора 26.р, группы буферных регистров 27.p.k (,A), сумматора 28.р, группы буферных регистров 29.p.k (,A),

en j

ОЭ

четвертую общую информационную шину 30, группу вычитательных блоков первого типа 31.р (,А), каждый из которых состоит из сумматора 32, р„ реги стра (результата) 33.р, буферного регистра 34.р, триггера 35.р, выходы 36.р (,4) блока 5 постоянной памяти, двухразрядные выходы 37.р (р-1, 2х(А+В)) блока 8 постоянной памяти, блок 38 буферной памяти, информационный выход 39 всего устройства, блок 40 постоянной памяти, выходы 40 - 41.р (,2В) блока постоянной памяти.

Устройство вычисляет быстрое преоб разование Фурье по алгоритму Винограда с периодом в С отсчетов, где хВ (А и В - простые числа).

Рассмотрим работу устройства по- тактно. При описании работы устройства применены следующие сокращения: См - сумматор, Тр - триггер, Рг - регистр, ВВП - блок буферной памяти, ПЗУ (пронумерованный выход) - блок постоянной памяти, Ум - умножитель. Для конкретизации примем , , а период преобразования будет равен 15, число . С генератора поступают прямоугольные импульсы типа меандр. Будем полагать, что триггеры, регистры во всех вычислительных элементах срабатывают по переднему фронту синхросигнала (положительный перепад). Первые 15 тактов работы мы опускаем для счета, поскольку за это время входные отсчеты Х(р) (,15) в прямой последовательности поступают с входа 1 в ББП 2. После этого следуют три такта паузы, поскольку счетчик 4 работает по модулю . Со следующе- го такта входные отсчеты Х(р) в нужной нам последовательности поступают в первую общую информационную шину.

1такт. ББП 25 Х(0).

2такт. ББП (5); Рг 12.(Q);

ПЗУ 5 (36.1) См 10.1 Х(0).

л

ББП (10); ПЗУ 5 (36.1)Ф

Рг 12.(0); См 10.1-0; Тр 13. Рг 12.2«Х(5); См 10.(0)+Х(5); Рг 11.1 Х(0).

ББП (3); См 10.

Рг 12.(0); Рг 11. Тр 13. Рг 12.2-Х(5); См 10.(5); Рг 11.(0)+ +Х(5); Тр 13. Рг 12.3 Х(10); См (0)+Х(5)+ +Х(10).

-, to

-| 5

20 25JQ jj до

45

.

50

55

5такт. ББП (8); Рг 12.(3);

Рг 11. ПЗУ 5 (36.1)Г; См 10.1-Х(3); Рг 12.); См 10.(5); Рг 11.2-Х(5); Тр 13. Рг 12.(10); См Ю.(5)+Х(10); Рг 11.3 (Y(1))X(0)+X(5)+X(10)).

6такт. ББП (13); Рг 12.(3);

Рг 11.1-Х(3); ПЗУ 5 (36.1) Тр 13. См 10. Рг 12.(8); См 10.(3)+ +Х(8); Рг 11.(5); Рг 12.3 Х(10); См 10.(5)-Х(10); Рг 11.3(Y(2)X(5)+X(10)).

7такт. ББП (6); Рг 12.(3);

Рг 11.1-0; См 10. Рг 12.2 Х(8); См 10.(8); Рг 11.2 Х(3)+Х(8); Тр 13. Тр 13. Рг 12.(13); См 10.3-Х(3)Х(8)+Х(13); Рг 11.3(Y(3)X(5)-X(10). Дальше работа группы вычислительных блоков 9 продолжается по описанному алгоритму. Управляющие сигналы поступают на сумматоры вычислительных блоков 9 таким образом, что на выходе первой группы получаем результат, равносильный умножению двух матриц (суммирование в скобках во второй матрице происходит по модулю 15):

1 1 П Гх(р) 1

О 1 1 х Х(р+5) LO 1 1J Lx(p+10)J где Х(р) - входные отсчеты сигнала, ,3,6,9,12.

Работу группы вычислительных блоков 15.р рассмотрим, начиная с 5-го такта.

5такт. Рг 11.(1) (это значение и

все последующие поступают на вторую общую информационную шину 6 для группы вычислительных блоков 15, поэтому в дальнейшем вместо знака Рг 11.3 будет 111 6, что означает шина 6); ПЗУ 5 (36.2) (при 1 на управляющем входе коммутаторы 17.р группы 15 (условное обозначение К 1.р) передают информацию с первых входов; К 17.( См 19.1 -Y(1).

6такт. ПЗУ 5 (36.2)Г; 111 (2Ь

К 17.(2); Рг 18.1.(1); См 19.(2); Рг 20.1.(1).

7такт. ПЗУ 5 (36.2) 111 (3);

К 17.(3); Рг 18.1.(2); Рг 18.1.(1); См 19.1-т(3);

5157161

Рг 20.1.(2); Pr 20.1.2 -Y(1).

такт. ПЗУ 5 (36.2) ПЗУ 40

(41.1)Г; Тр 16. См 19. Pr 20.1.(3); Рг 20.1.(2); Рг 20.1.3 Y(1); К 17.2-7(4); См 19.2 Y(1)+Y(4).

такт. Тр 16. См 19. ю

Рг 20.1. Рг 20.1.(3); Рг 20.1.(2); К 17.(5); Рг 20.2.(1) +Y(4); См 19.2 Y(2)+Y(5); Pr 18.2.(4).

0такт. Тр 16. Рг 20.1. ,5

Рг 20.1,(3); К 17.(6); Рг 20.2.(2)+Y(5); Рг 20.2.(1)+Y(4); См 19.2 Y(3)+Y(6); Pr 18.2.(5); Рг 18.2.(4).20

1такт. Тр 16. ПЗУ 40 (41.р/р

1,5/) Тр 16. Рг 20.1. К 17.2-7(4); Рг 20.2.(3)+Y(6); Рг 20.2.(2)+Y(5); Рг 20.2.3 25 Y(1)+Y(4); См 19.2-7(4); Рг 18.2.1-7(6); Рг 18.2.2 7(5); Рг 18.2.(4); К 17.(7); См 19.(1)+7(4)+ +7(7). .30

2такт. Рг 20.1. К 17.(5);

Рг 20.2.(4)j Рг 20.2.2 7(3)+7(6); Рг 2Q.2.(2)+ +7(5); См 19.2-7(5); Рг 18.2.(4); Рг 18.2.2-7(6); Рг 18.2.(5); К 17.3-7(8); 3 Рг 18.3.(7); CM 1.(2)+ +Y(5)+Y(3); Pr 20.3.(0 + +Y(4)+Y(7); Тр 1б..

3такт. Тр 1б. Рг 20.1. 4Q

К 17.2-7(6); Рг 20.2.(5); Рг 20.2.(4); Рг 20.2.3 7(3)+7(6); См 19.(6); Рг 18.2.(5); Рг 18.2.2 7(4); Рг 18.2.(6); К ., 17.(9); Рг 18.3.(8); Рг 18.3.2-7(7); См 19.3 713)+7(6)+7(9); Рг 20.3.1 -Y(2j+Y(5)+Y(8)j Рг 20.3.2 7(1)+7(4)+7(7).50

4такт ПЗУ 40 (41.,5/)

Тр 16, Тр 16,

К 17.(4); Рг 20.1.

Рг 20.2.(6); Рг 20.2.2

7(5); Рг 20.2.(4); См « 19.7.2-7(4); Рг 18.2.1-7(6) ; Рг 18.2.2-7(5); Рг 18.3.2 7(8); Рг 18.2.(4); К 17.3-7(7); Рг 18.3.(9);

Рг 18.3.3-7(7); См 19.3 -Y(4)+Y(7); Рг 20.3.(3)+ +7(6)+7(9); Рг 20.3.(2)+ +7(5)+Y(8); Pr 20.3.3-7(1)+ +7(4)+Y(7); К 17.4-7(10); См 19.(1)+Y(4)+Y(7)+T(10).

5такт. Тр 16, Рг 20.1.

К 17.(5); Рг 18.2.(4); Рг 18.2.2-7(6); Рг 18.2.3 -7(5); См 19.(5); Рг . 20.2.(4); Рг 20.2.(6); Рг 20.2.(5); К 17.3-7(8); Рг 18.3.(7); Рг 18.3.2 Y(9); Рг 18.3.(8); См 19.(5)+Y(8); Рг 20.3.1 7(4)+Y(7); Рг 20.3.(3)+ +Y(6)+Y(9); Pr 20.3.(2)+ +Y(5)+Y(8); К 17.4-7(11); Рг 18.4.(10); См 19.4 -У(2)+7(5)+7(8)+7(11); Рг 20.4.(1)+7(4)+7(7)+7(10).

6такт. Тр 16. Рг 20.1.

К 17.2-7(6); Рг 18.2.(5); Рг 18.2.2-7(4); Рг 18.2.3 7(6); См (6); Рг 20.(5); Pr 20.2.(4); Рг 20.2.(6); К 17.(9); Рг 18.3.(8); Рг 18.3.2 -7(7); Рг 18.3.3-7(9); См 19.3-7(6)+7(9); Рг.20.3.1- -7(5)+7(8); Рг 20,3.(4)+ +Y(7); Pr 20.3.(3)+Y(6)+ +7(9); К 17.(12); Рг 18.(11); Рг 18.4.(10); См 19.(3)+Y(6)+Y(9)+Y(12); Рг 20.4.(2)+Y(5)+Y(8)+ +7(11); Рг 20.4.(1)+Y(4)+ +7(7)+7(10).

7такт. ПЗУ 4.0 (41 .р/р-1 ,5/)Г;

Тр 16. Тр 1б, Рг 20.1. К 17.2-7(4); Рг 18.2.(6); Рг 18.2.2 -7(5); Рг 18.2.(4); См 19.(4); Рг 20.2.(6); Рг 20.2.(5); Рг 20.2.3 7(4); См 19.3-7(4)-7(7); К 17.3-7(7); Рг 18.3.1-7(9); Рг 18.3.2-7(7); Рг 20.3.1 7(6)+У(9); Рг 20.3.(5)+ +7(8); Рг 2Q.3.(4)+Y(7); К 17.4-7(10); Рг 18.4.1 -7(12); Рг 18.4.(11); Рг 18.4.(10); См 19.4 Y(4)+Y(7)+Y(10);.Pr 20.4.1 Y(3)+Y(6)+Y(9)+Y(12); Pr 20.4.(2)+Y(5)+Y(8)+Y(11); Рг 20.4.3-7(1)+7(4)+7(7)+ +7(10); К 17.(13); См

19.5«Y(1)+Y(4)-i-Y(7)+Y(10) + +Y(13).

8такт. Tp 16, Рг 20.1.

К 17.(5); Рг 1802.(4); Рг 18. 2.(6)5 Рг 18.2,3 ); См 19.2«Y(5); Рг 20.2.1-Y(4); Рг 20.2.(6); Рг 20.2.(5)j К 17.(8); Рг 18.3.); Рг 18.3.2 Y(9); Рг 18.3.(8); См 19.(5)-Y(8); Рг 20.3.1 Y(4)-Y(7)j Рг 20.3.(6) + +Y(9); Рг 20.3.3-Y(5)+Y(8); К 17.(11); Рг 18.4.1 (10); Рг 18.4.2 Y(12); Рг 18.4.(11); См 19.4 Y(5)+Y(8)+Y(11); Рг 20.4.1 Y(4)+Y(7)+Y(10); Рг 20.4.2 -Y(3)+Y(6)+Y(9)+Y(12)S Рг - 20.4.(2)+Y(5)+Y(8)-fY(11); К 17.(14); Рг 18.5.1 Y(13);Y(2)+Y(5)+Y(8)+Y(11) + +Y(14)CM 19.5,

9такт. Tp 16. Pr 20.1,

Pr 18.2.(5); Pr 18.2.2 -Y(4); Pr 18.2.(6); К 17.(6); CM 19.(6); Pr1 20.2.(5); Pr 20.2.2 Y(4); Pr 20.2.(6); К 17.(9); Pr 18.3.(8); Pr 18.3.(7); Pr 18.3.3 Y(9); CM 19.(6)-Y(9); Pr 20.3.(5)-Y(8); Pr 20.3.(4)-Y(7); Pr 20.3.3 Y(6)+Y(9); К 17.(12); Pr 18.4.(11); Pr 18.4.2 Y(10); Pr 18.4.(12); Pr 18.4.(11)i Pr 18.4.2 Y(10); Pr 18.4.(12); CM 19.(6)+Y(9)+Y(12); Pr 20.4.(5)+Y(8)+Y(11); Pr 20.4.(4)+Y(7)+Y(10); Pr 20.4.(3)+Y(6)+Y(9)+ +Y(12); К 17.(15); Pr 18.5.(14); Pr 18.5.2 Y(13); CM 19.(3)-fY(6) + +Y(9)+Y(12)+Y(15). Дальше работа группы вычислительых блоков 15.р продолжается по опианному алгоритму. Управляющие сигалы на сумматоры 19.р поступают таим образом, что на выходе группы 15 олучаем результат, равносильный уможению матриц:

; ; ; 1 ; ) +

3 510

15

20

25

30

35

40

45

50

55

18

где Y(p) - значения, поступающие на общую информационную шину 6 (р-1,6,11).

С информационного выхода вычислительного блока 15,5 значения поступают на вход блока 22 умножения, на другой вход которого приходят с ПЗУ 21 значения весовых коэффициентов и признаков. После умножения в блоке 22 умножения значения поступают в третью общую информационную шину 23.

Группа вычислительных элементов 24.р работает аналогично группе вычислительных блоков 15.р (,5). Управляющие сигналы на сумматоры 28.р поступают таким образом, что на выходе получаем значения, которые были бы получены при умножении двух матриц:

Y(p) Y(p+1) Y(p+2) Y(p+3) Y(p+4) LY(p+5)

где Y(p) - значения, поступающие на третью общую информационную шину 23 (,7,13). С информационного выхода вычислительного блока 24.5 значения поступают на четвертую общую информационную шину 30,

Группа вычислительных блоков З1.р (,3) работает аналогично группе вычислительных блоков 9.р, для которой алгоритм описан выше. Управляющие сигналы поступают на сумматоры 32.р таким образом, что на выходе вычислительных блоков получаем значения, которые были бы получены при умножении двух матриц:

X(k) x(k+1) Lx(k+2)

где X(k) - значения, поступающие на

четвертую общую информационную шину 30 (,4,7, 10,13).

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

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

Устройство для вычисления быстрого преобразования Фурье, содержащее

tгенератор тактовых импульсов и первую группу из А (Л - простое число) вычислительных блоков первого типа, причем информационный выход 1-го (, А-1) вычислительного блока первого типа группы подключен к первому информационному входу (1+1)-го вычислительного блока первого типа группы, первый вход синхронизации ко- торого подключен к выходу синхронизации 1-го вычислительного блока первого типа группы, при этом вычислительный блок первого типа группы содержит сумматор, триггер, регистр результата и буферный регистр, выход которого подключен к первому информационному входу сумматора, второй информационный вход которого является первым информационным входом вычисли- тельного блока первого типа, вторым информационным входом которого является информационный вход буферного регистра, тактовый вход которого соединен с тактовым входом триггера и является первым входом синхронизации вычислительного блока первого типа, вторым входом синхронизации которого является вход синхронизатора сумматора, выход которого подключен к ннфор- мационному входу регистра результата, выход которого является информационным выходом вычислительного блока первого типа, отличающееся тем, что, с целью упрощения, оно со- держит счетчик, два блока буферной памяти, четыре блока постоянной памяти, блок умножения, вторую группу из А вычислительных блоков первого типа, первую и вторую группы из В (В - прос тое число; - размер преобразования) вычислительных блоков второго типа, причем информационный выход j-го (, B-1) вычислительного блока второго типа группы подключен к первому информационному входу (j+ +1)-го вычислительного блока второго типа, первый вход синхронизации которого подключен к выходу синхронизации j-ro вычислительного блока второ- го типа группы, при этом выход генератора тактовых импульсов подключен к счетному входу счетчика, информационный выход которого подключен к адресным входам первого, второго, третьего и четвертого блоков постоянной памяти и первого и -второго блоков буферной памяти, выходы с первой по четвертый первого блока постоянной памяти подключены к первым входам синхронизации соответственно первого вычислительного блока первого типа первой группы, первых вычислительных блоков второго типа первой и второй групп и первого вычислительного блока первого типа второй группы, К-й (,А) выход второго блока постоянной памяти подключен к второму входу синхронизации К-го вычислительного блока первого типа первой группы, (К+А)-й и (К+А+В)-й выходы второго блока постоянной памяти подключены к вторым входам синхронизации К-х вычислительных блоков второго типа соответственно первой и второй групп, а (К+А+2В)-й выход второго блока постоянной памяти подключен к второму входу синхронизации К-го вычислительного блока первого типа второй группы, 1-й и (1+В)-н ( выходы третьего блока постоянной паг мяти подключены к третьим входам синхронизации 1-х вычислительных блоков второго типа соответственно первой и второй групп, выход четвертого блока постоянной памяти подключен к первому входу блока умножения, выход которого подключен к второму информационному входу (К-го вычислительного блока второго типа второй группы, выход Б-го вычислительного блока второго типа которой подключен к второму информационному входу 1-го вычислительного блока первого типа второй группы, выход А-го вычислительного блока первого типа которой подключен к информационному входу первого блока буферной памяти, выход которого является информационным выходом устройства, информационным входом которого является информационный вход второго блока буферной памяти, выход которого подключен к второму информационному входу 1-го вычислительного блока первого типа первой группы, информационный выход А-го вычислительного блока первого типа которой подключен к второму информационному входу К-го вычислительного блока второго типа первой группы, информационный выход В-го вычислительного блока второго типа которой подключен к второму входу блока умножения, причем вычислительный блок второго типа группы содержит триггер, коммутатор, сумматор, первую; вторую группы из А последовательно соединенных буферных

Г/

Изобретение относится к вычислительной цифровой технике и может быть использовано в системах цифровой обработки сигналов. Цель изобретения - упрощение устройства. Это достигается за счет того, что в состав устройства входят генератор тактовых импульсов,счетчик, четыре блока постоянной памяти, блок умножения, два блока буферной памяти, две группы из A (A - простое число) вычислительных блоков первого типа, каждый из которых содержит буферный регистр, регистр результата, сумматор и триггер, две группы из B /B - простое число

A^.B=N - размер преобразования/ вычислительных блоков второго типа. Каждый из них содержит коммутатор, триггер, сумматор, две группы из А буферных регистров. 8 ил.

W.

rtl

372& 0)

Фь&.1

I п±

ш

W.A тг

1440

±

П.1

ПА

Л

6

-

J

Фиг. 2

4/.1

20J.A

Ш.К

О

,//.

16Л

J

gJ

//

J7/fs/

Г

П8

i

26Л

П/.1

22

23

(

}58

-м

Ы.1

-....

2

ФиеЛ

. i

2S1A

... .-ъШ.А

о

1

25Л

ZT

фиг 5

U

С

.

Я7

--J

Риг. б

л/)

J7f

J/7

-

-

. э ЈЛ

гтллр

J

л/

Л/

30 -

qbe.8