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

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

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

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

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

вычислительных модулей 10.р (, А/2), каждый из которых состоит из (проходного) регистра 11.р, триггера 12.р, буферных регистров 13.2р-1 и 13.2р. (промежуточного) сумматора 14.р, сумматора (результата) 15.р, регистра (результата) 16.р, вспомогательный вычислительный модуль 8 состоит из триггера 17, буферного регистра 18, сумматора 19. регистра(результата) 20; вторую группу вычислительных модулей 21.р (,, М/2), каждый из которых состоит из (проходного) регистра 22.р, триггера 23.р. буферного регистра 24.р, буферного регистра 25.р. (промежуточного) сумматора 26.р. сумматора (результата) 27.р. регистра (результата) 28.р; входы задания режима 29 и 30, информационный выход 31; вспомогательный вычислительный модуль 9 состоит из сумматора 32. регистра (результата) 33, буON

|

СП 00

ферного регистра 34, триггера 35; шину 36 синхронизации; второй блок 37 постоянной памяти, умножитель 38.

Умножитель 38 (фиг. 5) состоит из блока 39 умножения, входа для признака J 40, выхода 41 для действительной части комплексного числа, выхода 42 для мнимой части комплексного числа, первого коммутатора 43, второго коммутатора 44, входа 45 для значения весового коэффициента, входа 46 для мнимой части комплексного числа, входа 47 для действительной части комплексного числа, блока 48 умножения.

Все сумматоры и умножитель выполняют операции над комплексными числами.

Устройство производит вычисление БПФ по алгоритму Винограда, который можно записать в следующем виде:

у СхВхАхХ,(1)

где Y - выходной вектор;

А - матрица, элементы которой принадлежат множеству { 1; 0; -1}

В - диагональная матрица, элементы которой либо чисто действительные, либо чисто мнимые;

С - матрица, элементы которой принадлежат подмножеству {1; 0: -1}

Работа устройства на примере . В этом случае выражение (1) примет следующую форму;

(оГ Гюоо1 10011

01 оо

001-1

Y(1) Y(2) Y(3)

где ЈT.

Подобные разложения можно найти для различных А.

Пусть триггеры 12.р, (23.к), проходные регистры 11.p(22,k), регистрыJ6.p (28.к, 2Q и 33, результата, где (, А/2; , M/2), срабатывают по переднему фронту синхросигнала (положительный перепад), а буфер- ные регистры 13.р (24.k, 25.k), 18 и 34, где (, A; , M/2) срабатывают по заднему фронту синхросигнала (отрицательный перепад).

Входные отсчеты поступают на инфор- мационный вход 1.

Рассмотрим работу первой группы модулей Ю.р (, А/2) потактно. При описании работы применяются следующие сокращения: Рг - регистр, См - сумматор, Ум - умножитель, ПЗУ - блок постоянной памяти, Дш - дешифратор. Дм - демультип- лексор, Тр - триггер, Вх - вход, Вых - выход.

Первый такт. Вх (0)

Втврой такт. Вх 1-Х(1): Рг 11.1-Х(0):Дш

0

5

0

5

0

5

0

5

0

5

Третий такт. Вх (2):Рг 11.(1):Рг 11.(0);Дш 4 13.4 Х(0):Рг 13.(1):Дм (на втором выходе):См 14.(0)+Х(1):См 15.(0)+Х(1).

Четвертый такт. Вх (3):Дш 12.2 11.(2):Рг 13.(0);Рг 13.(1):См 14.(0)-Х(1):См 15.(0)-Х(1):Рг 13.(2):Рг 13.(3):См 14.(2)+Х(3):Рг 16.2 Х(0)+Х(1):См 15.1 Х(0)+Х(1 )+Х(2)+Х{3).

Пятый такт. Вх (0) (индекс 1 значит отсчет следующего периода): регистры 13.1-13.4 сохраняют значения предыдущего такта, Дм . 14.(0): См 15.(0): См 14.(2)-Х(3):Рг 16.(0)-Х(1):См15.(ОЬХ(1)+Х(2)-Х(3):Рг 16.1 Х(0)+Х( 1 )+Х(2)+Х(3).

Начиная с шестого такта, работа первой группы модулей происходит по описанному выше алгоритму. Управляющие сигналы на сумматоры 14.1, 14.2,15,1 и 15.2 поступают в соответствии с матрицей А.

С выхода регистра 16.1 значения поступают на первый вход умножителя 38, на второй вход которого приходят значения с ПЗУ 37. С выхода умножителя 38 умноженные значения поступают на первый информационный вход модуля 21.1.

Работа второй группы модулей 21 ,k(,

М/2) происходит аналогично работе первой группы модулей Ю.р. Управляющие сигналы на сумматоры 26.k и 27.k (, 2) поступают в соответствии с матрицей С.

Если при другом значении числа А число М окажется больше числа А (это определяется алгоритмом Винограда), то в работе первой группы модулей делается пауза на определенное количество тактов, определяемое разницей чисел М и А.

Если число А (М) - нечетное, то на де- мультиплексор 6 (7) поступает управяющий логический сигнал, который логическую 1 с дешифратора 4 подает на вход триггера 17 (35) и запись первого значения происходит в буферный регистр 18 (34). Дальше работа групп модулей происходит по описанному выше алгоритму.

Умножитель 38 работает следующим образом.

С регистра 16.1 на вход 47 поступает действительная часть комплексного числа, а на вход 46 - мнимая часть комплексного числа, на вход 45 приходит с ПЗУ 37 значение весового коэффициента. Блоки умножения 48 и 39 производят операцию умножения и через коммутатор 43 действительная часть комплексного числа попадает на выход 41, а мнимая часть через коммутатор 44 - на выход 42. Если необходимо значение, содержащееся в регистра 16.1,

умножить на j, то с ПЗу 37 на вход 40 приходит соответствующий управляющий сигнал, и коммутаторы 43и 44 меняют местами дей ствительную и мнимую части комплексного числа.

Формула изобретения Устройство для вычисления быстрого преобразования Фурье, содержащее первую группу из А/2 (А - целое число) вычислительных модулей, первый блок постоянной памяти, дешифратор, счетчик и генератор тактовых импульсов, выход которого подключен к первым тактовым входам всех вычислительных модулей первой группы и счетному входу счетчика, информационный выход которого подключен к адресному входу первого блока постоянной памяти и входу дешифратора, первый информационный выход 1-го (. А/2-1) вычислительного модуля первой группы подключен к первому информационному входу (iM)-ro вычислительного модуля первой группы, второй информационный и тактовый выходы которого подключены соответственно к второму информационному и второму тактовому входам i-ro вычислительного модуля первой группы.при этом каждый вычислительный модуль содержит два регистра, триггер, два буферных регистра и два сумматора выход первого регистра подключен к информационному входу первого буферного регистра и является первым информационным выходом вычислительного модуля, первым информационным входом Koioporo являются соединенные между собой информационные входы второго буферного регистра и первого регистра, тактовый вход которого соединен с тактовым входом второго регистра и подключен к первому тактовому входу вычислительного модуля, тактовым выходом которого является выход триггера, тактовый вход которого является вторым тактовым входом вычислительного модуля, вторым информационным выходом которого является выход второго регистра, информационный вход которого подключен к выходу первого сумматора, первый и второй информационные входы которого подключены соответственно к выходу второго сумматора и второму информационному входу вычислительного модуля, отличающееся тем, что. с целью упрощения устройства, оно содержит два демультиплексора, умножитель, второй блок постоянной памяти, два вспомогательных вычислительных модуля и вторую группу из М/2 (М) - целое число) вычислительных модулей, причем выход генератора тактовых импульсов подключен к

первым тактовым входам всех вычислительных модулей второй группы и первого и второго вспомогательных вычислительных модулей, первый и второй выходы дешифра- тора подключены к информационным входам соответственно первого и второго демультиплексоров, первые выходы которых подключены к вторым тактовым входам соответственно первого и второго вспомо0 отельных оычислительных модулей, тактовые выходы которых соединены с вторыми входами соответственно первого и второго демультиплексоров и подключены к вторым тактовым входам соответственно А/2-го вы5 числительного модуля первой гоуппы и М/2- го вычислительного модуля второй группы, первые информационные выходы которых подключены к информационным входам соответственно первого и второго вспомога0 гельных вычислительных модулей, информационные выходы которых подключены к вторым информационным входам соответственно А/2-го вычислительного модуля первой группы и М/2-го вычисли5 тельного модуля второй группы,первый ин- формационный выход j-го (j-1 M/2-1) вычислительного модуля второй группы подключен к первому информационному входу (jM)-ro вычислительного модуля вто0 рой группы второй информационный и тактовый выходы которого подключены соответственно к второму информационному и тактовому входам i-ro вычислительного модуля второй группы, выход первого вы5 числительного модуля первой группы подключен к первому входу умножителя выход которого подключен к первому информационному входу первого вычислительного модуля второй группы. второй

0 информационный выход которого является информационным выходом устройства, информационным входом котооого является первый информационный вход первого вычислительного модуля первой группы, вто5 рой вход умножителя подключен к выходу первого блока постоянной памяти, информационный выход счетчика подключен к адресному входу второго блока постоянной памяти, 1-й (М. А/2) и (14-А/2)-й выходы

0 которых подключены соответственно к третьему и четвертому тактовым входам 1-го вычислительного модуля первой группы, т- й (, А-М/2) и (т+М/2)-й выходы второго блока постоянной памяти подключены

5 соответственно к третьему и четвертому тактовым входам (т-А)-го вычислительного модуля второй группы, ()-й и {А+М+2}-й выходы второго блока постоянной памяти подключены к третьим тактовым входам соответственно первого и второго вспомогательных вычислительных модулей, управляющие входы первого и второго демультип- лексоров являются входом задания режима устройства, причем в каждом вычислительном модуле первый и второй информационные входы второго сумматора подключены к выходам соответственно первого и второго буферных регистров, тактовые входы которых подключены к второму тактовому входу вычислительного модуля, третьим и четвертым тактовыми входами которого являются входы синхронизации соответственно первого и второго сумматоров, при этом каждый вспомогательный вычислительный модуль содержит триггер, регистр, сумматор и буферный регистр, выход которого подключен к первому информационному

5

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

Изобретение относится к цифровой вычисли гельиой технике, предназначено для вычис )ения быстрого преобразования Фурье и может быть использовано в системах цифровой обработки сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство имеет генератор тактовых импульсов счетчик, дешифратор, блок постоянной памяти, два демультиплексора. два вспомогательных вычислительных модуля, две группы вычислительных модулей. Каждый вычислительный модуль первой группы содержит два регистра , триггер, два буфферных регистра, сумматор. Первый вспомогательный вычислительный модуль содержит триггер , буферный регистр, сумматор и регистр. Каждый вычислительный модуль второй группы содержит два регистра, триггер, два буферных регистра , два сумматора. Второй вспомогательный вычислительный модуль содержит сумматор, регистр, буферный регистр, триггер, блок постоянной памяти и умножитель. 5 ил. Ё

Фиг.1

|5.ПЦШ

4i I.A ле л /лI

E ДЛ-Т

31

С ул. Jg

1

,5A+Z21.1

5A t/

Zlntt.

,5 MM

28 „1г

/,

5А+Н

п

26 пП Г

4i

25/й

lf5

л

Ь8

W

4/ ..

33

-

4

ы

W