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

 

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

С0103 СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ в

Ф

Ф Ql

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21 4490067/24 (22) 03.10,88 (46) 23.04.91. Бюл. N 15 (71) Житомирский филиал Киевского политехнического института (72) Д.В. Корчев, Ю.С. Каневский, И.А. Коноплицкий и В.И. Лозинский (53) 681. 32(088. 8) (56) Авторское свидетельство СССР

N 1196894, кл. 6 06 F 15/332, 1985.

Авторское свидетельство СССР

¹ 1474673, кл. 6 06 F 15/332, 18.05.87. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к цифровой вычисли "ельной технике, предназначено для вычис ения быстрого преобразования

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

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

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

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

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

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

А+М 2) первый демультиплексор б, второй демультиплексор 7. вспомогательные вычислительные модули 8 и 9. первую группу. Ж» 1644158 А1 изобретения — упрощение устройства, Поставленная, цель достигается за счет того, что устройство имеет генератор тактовых импульсов. счетчик, дешифратор, блок постоянной памяти. два демультиплексора, два вспомогательных вычислительных модуля, две группы Bbl4исли1ельных модулей.

Каждый вычислительный модуль первой группы содержит два регистра, триггер, два буфферных регистра, сумматор. Первый вспомогательный вычислительный модуль содержит триггер, буферный регистр, сумматор и регистр. Каждый вычислительный модуль второй группы содержитдва регистра, триггер, два буферных регистра, два сумматора. Второй вспомогательный вычислительный модуль содержит сумматор, регистр, буферный регистр, триггер, блок постоянной памяти и умножитель. 5 ил. вычислительных модулей 10.р (р=1, А/2), каждый из которых состоит из(проходного) регистра 11.р, триггера 12.р, буферных регистров 13.2р — 1 и 13.2р, (промежуточного) сумматора 14.р, сумматора (результата)

15,р, регистра (результата) 16.р, вспомогательный вычислительный модуль 8 состоит из триггера 17, буферного регистра 18, сумматора 19. регистра (результата) 20; вторую гоуппу вычислительных модулей 21.р (р=1, M/2), каждый из которых состоит из (проходного) регистра 22.р. триггера 23,р. 6уферного регистра 24.р, буферного регистра

25.р. (промежуточного) сумматора 2б.р. сумматора (результата) 27.р. регистра (результата) 28,р; входы задания режима 29 и 30. информационный выход 31, вспомогательный вычислительный модуль 9 состоит из сумматора 32. регистра (результата) 33, бу1644158 ферного регистра 34, триггера 35; шину

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

Умножитель 38 (фиг, 5) состоит из блока

39 умножения, входа для признака "J" 40, 5 выхода 41 для действительной части комплексного числа, выхода 42 для мнимой части комплексного числа, первого коммутатора

43, второго коммутатора 44, входа 45 для значения весового коэффициента, входа 46 10 для мнимой части комплексного числа, входа 47 для действительной, части комплексного числа, блока 48 умножения.

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

Устройство производит вычисление

БПФ по алгоритму Винограда, который можно записать в следующем виде: у = С.х Вх Ах Х, (1) где Y — выходной вектор; 20

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

 — диагональная матрица, элементы которой либо чисто действительные, либо чисто мнимые: 25

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

Работа устройства на примере А=4. В этом случае выражение (1) примет следующую форму: 30 1 000" !

0011

0100 . 001-1

x(o}l

X(1).

X(2)

X(3) 0010 10-1,.У (0)

Y (1)

Y(2)

Y(3) группы модулей 10.р. Управляющие сигналы на сумматоры 26.k и 27.k (k=1, 2) поступают в соответствии с матрицей С.

Если при другом значении числа А число

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

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

45 в буферный регистр 18 (34). Дальше работа групп модулей происходит по описанному выше алгоритму, Умножитель 38 работает следующим об50 разом.

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

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

Пусть триггеры 12.р, (23.k), проходные регистры 11,р (22,k), регистоы 16.р (28 К 2Я и 33, результата, где (р=1, А/2; k 1 М/2), срабатывают по переднему фронту синхросигнала (положительный перепад), а буферные регист ы 13.р (24.К 25;k). 18 и 34, где

{р=1, А; k=1, M 2) срабатывают по заднему фронту синхросигнала (отрицательный перепад).

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

Рассмотрим работу первой группы модупеи 10.р (p=1, А72) потактио. При описании работы применяются следующие сокращения: Pr — регистр, См — сумматор, Ум — умножитель, ПЗУ вЂ” блок постоянной памяти, Дш — дешифратор, Дм — демультиплексор, Тр — триггер, Вх — вход, Вых — выход, Первый такт. Вх 1=Х(0)

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

4=иОи

Третий такт. Вх 1=Х(2):Рг 11.1=Х(1):Рг

1 1, 2 = Х(0): Д ш 4 =" 1 "; P r 1 3. 4 = X(0); P г

13.3=Х(1):Дм 6=и1и (на втором выходе):См

14,2=Х(0)+Х(1): См 15,2=Х(0)+Х(1).

Четвертый такт. Вх 1=Х(3):Дш 4=и0":Дм

6=иО":Тр 12,2=и1";Рг 11,1=Х(2):Рг

13.4=Х(0);Рг 13.3=Х(1):См 14.2=X(0)-Х(1):См

15,2=Х(0) — Х(1):Рг 13,2=Х(2):Рг 13.1=Х(3):См

14.1=Х(2)+Х(3):Рг 16,2=Х(0)+Х(1):См

15.1=Х(0)+Х(1)+Х(2)+Х(3).

Пятый такт. Вх 1=Х1(0) (индекс 1 значит отсчет следующего периода): регистры

13.1-13.4 сохраняют значения предыдущего такта, Дш 4=и0": Дм 6=иОи:Тр=12.2=и0":См

14,2=Х(0): См 15,2=Õ(0): См 14.1=Х(2)-Х(3):Рг

16.2=Х(0) — Х(1): См 15.1=Х(0) —,Х(1)+Х(2) — Х(3): P r

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

С выхода регистра 16.1 значения поступают на первый вход умножителя 38. на второй вход которого приходят значения с

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

Работа второй группы модулей 21,k(k=1, M/2) происходит аналогично работе первой

1644158

20

40

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

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

Устройство для вычисления быстрого преобразования Фурье, содержащее первую группу из А/2 (А — целое число) вычислительных модулей, первый блок постоянной памяти, дешифратор, счетчик и генератор тактовых импульсов, выход которого подключен к первым тактовым входам всех вычислительных модулей первой группы и счетному входу счетчика, информационный выход которого подключен к адресному входу первого блока пос гоянной памяти и входу дешифратора, первый информационный выход i-ro (i=1, A/2 — 1) вычислительного модуля первой группы подключен к первому информационному входу (i+1)-го вычислительного модуля первой группы, второй информационный и тактовый выходы которого подключены соответственно к второму информационному.и второму тактовому входам I-го вычислительного модуля первой группы. при этом каждый вычислительный модуль содержит два регистра, триггер, два буферных регистра и два сумматора, выход первого регистра подключен к информационному входу первого буферного регистра и является первым информационным выходом вычислительного модуля, первым информационным входом ко торого являются соединенные между собой информационные входы второго буферного регистра и первого регистра, тактовый вход которого соединен с тактовым входом второго регистра и подключен к первому тактовому входу вычислительного модуля, тактовым выходом которого является выход триггера, тактовый вход которого является вторым тактовым входом вычислительного модуля, вторым информационным выходом которого является выход второго регистра, информационный вход которого подключен к выходу первого сумматора, первый и второй информационные входы которого подключены соответственно к выходу второго сумматора и второму информационному входу вычислительного модуля, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит два демультиплексора, умножитель, второй блок постоянной памяти, два вспомогательных вычислительных модуля и вторую группу из М/2 (M) — целое число) вычислительных модулей, причем выход генератора тактовых импульсов подключен к первым тактовым входам всех вычислительных модулей второй группы и первого и второго вспомогательных вычислительных модулей, первый и второй выходы дешифратора подключены к информацио ным входам соответственно первого и второго демультиплексоров, первые выходы которых подкл очены к вторым тактовым входам соответственно первого и второго вспомогательных вычислительных модулей, тактовые выходы которых соединены с вторыми входами соответсгвенно первого и второго демультиплексоров и подключены к вторым тактовым входам соответственно А/2-rî вычислительного модуля первой гауппы и M/2го вычислительного модуля второй группы, первые информационные выходы которых подключены к информационным входам соответственно первого и вгорого вспомогагельных вычислительных модулей, информационные выходь, ко1орых подключены к вторым информационным входам соответственно А/2-го вычислительного модуля первой группы и М/2-го вычислительного модуля второй группы, первый ингрормацггонныи выход )-го jj= l, М72 — 1) вычислительного модуля второй группы подключен к первому информационному входу (j j-1)-го вычислительного модуля второй группы. второй информационный и тактовый выходы которого подключены соответственно к второму информационному и тактовому входам i-ro вычислительного модуля второй группы, выход первого вычислительного модуля первой группы подключен к первому входу умножителя, выход которого подключен к первому информационному входу первого вычислительного модуля второй группы. второй информационныи выход которого является информационнь м выходом устройства, информационным входом котооого является первый информационныи вход первого вычислительного модуля первой группы, BTOрой вход умножителя подкл.ючен к выходу первого блока постояннои памяти, информационный выход счетчика подключен к адресному входу второго блока постоянной памяти, I-й (I=1, А/2) и (I+A/2)-й.выходы которых подключены соответственно к третьему и четвертому тактовым входам!-го вычислительного модуля первой группы, mй (m=A 1, А- М/2) и (m+M/2)-й выходы второго блока постоянной памяти подключены соответственно к третьему и четвертому тактовым входам (m — А)-го вычислительного модуля второй группы, (А М 1)-й и (А+М+2)-й выходы второго блока постоянной памяти подключены K третьим тактовым входам соответственно первого и второго вспомога1644158 тельных вычислительных модулей, управляющие входы первого и второго демультиплексоров являются входом задания режима устройства, причем в каждом вычислительном модуле первый и второй информационные входы второго сумматора подключены к выходам соответственно первого и второго буферных регистров, тактовые входы которых подключены к второму тактовому входу вычислительного модуля, третьим и четвертым тактовыми входами которого являются входы синхронизации соответственно первого и второго сумматоров, при этом каждый вспомогательный вычислительный модуль содержит триггер, регистр, сумматор и буферный регистр, выход которого подключен к первому информационному входу сумматора, выход которого подключен к информационному входу регистра, выход и тактовый вход которого являются соответственно информационным выходом

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

1644158

1644158

Составитель А.Баранов

Техред M,Mîðãåíòàë Корректор Т. Колб

Редактор Е.Вагап

Заказ 1242 Тираж 416 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101