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

 

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки радиолокационных , сейсмических, гидроакустических. видеои других сигналов. Известное устройство имеет большие аппаратурные затраты, кроме того оно за один вычислительный цикл формирует топько действительную или мнимую часть выходного отсчета. Изобретение при вычислении действительной и мнимой части результата имеет вдвое большую производительность, так как вычисление реальной и мнимой части результата в устройстве , выполняется за один проход, а в прототипе за два прохода. Устройство содержит М умножителей (М 2KTi/T. где Ti - время срабатывания умножителя: Т2 - временной интервал между поступлением двух входных отсчетов 2Ti Т2: К - количество вычисляемых спектральных составляющих. К N; N - размер преобразования), по М/2 сумматоров первой и второй группы, по К регистров суммы первой и второй группы, М/2 регистров входных данных, М регистров операндов и (М+1)/2 триггеров и М блоков памяти коэффициентов, информационный вход устройства объединен с входом первого регистра входных данных, а вход последующего регистра подключен к выходу предыдущего. Выходы умножителей подключены к соответствующим входам сумматоров первой группы, выходы которых подключены к первым входам сумматоров второй группы, к вторым входам которых подключены выходы соответствующих регистров суммы первой группы. Выход первого регистра суммы является выходом устройства и подключен к входу первого регистра суммы второй группы. 3 ил. сл С vj Ю (Я ГО ю 00

СОЮЗ СОВЕТСКИХ

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

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

ГОСУДАРСТВЕН.ГОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4811458/24 (22) 09.04.90 ю (46) 07.04.92. Бюл. М 13 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции

7?) Ю.С.Каневский, М.К.Клименко. .И;Лозинский и А.М.Сергиенко (56) Авторское свидетельство СССР

М 1196894. кл, G 06 F 15/332, 1985.

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

М 1388891, кл. G 06 F 15/332, 1988. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки радиолокационных, сейсмических, гидроакустических, видео- и других сигналов. Известное устройстао имеет большие аппаратурные затраты, кроме того оно за один вычислительный цикл формирует только действительную или мнимую часть выходного отсчета. Изобретение при вычислении действительной и мнимой части результата имеет вдвое большую производительность. так как вычисление реальной и мнимой части результата в устИзобретение относится к вычислительной технике и может быть ис:юльзовано в различных системах цифровой обработки сигналов.

Цель изобретения — повышение быстродействия. я фиг. 1 и 2 изображена структурная схема устройства; на фиг. 3 — временные диаграммы управляющих сигналов.

5U«, 1725228 А1 ройстве,выполняется за один проход, а в прототипе за два прохода. Устройство содержит M умножителей (М = 2KT1/Т2. где Т1 — время срабатывания умножителя: Т2 — временной MkTepF;Bll между поступлением двух входных отсчетов 2Т1 < Tg: К вЂ” количество вычисляемых спектральных составляющих, К N; N — размер преобразования), по M/2 сумматоров первой и второй группы. по К регистров суммы первой и второй группы, М/2 регистров входных данных, М регистров операндов и (У+1)/2 триггеров и М блоков памяти коэффициентов. информационный вход устройства объединен с входом первого регистра входных данных, а вход последующего регистра подключен к выходу предыдущего. Выходы умножителей подключены к соответствующим входам сумматоров первой группы, выходы которых подключены к первым входам сумматоров второй группы. к вторым входам которых подключены выходы соответствующих регистров суммы первой группы. Выход первого реГистра суммы является выходом устройства и подключен к входу первого регистра суммы второй группы. 3 ил.

Устройство (фиг. 1 и 2) содержит вычислительные модули 1.1-1,М/2. где . А — целое число, содержащее первый 2.1 и второй 2.2 умножители, первый 3 и второй 4 сумматоры, входной регистр 5. первый 6.1 и второй

6.2 регистры операндов, триггер 7, первый

S и второй 9 блоки регистров суммы, а М/2-й модуль содеожит дополнительно триггер 10.

1725228

Кроме того, устройство содержит информационный вход 11. информационные входы

12, 13 и выход 14 модуля. информационный выход 15, информационные выходы 16-18 и входы 19-22 ьодуля. две группы из M/2 блоков постоянной памяти 23, счетчик 24, генератор тактовых импульсов 25, выход 26 синхронизации, управляющий вход 27, дешифратор 28 и элемент ИЛИ-HE 29.

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

N-1

X(k) - g x(n) WNм". 0 (k «< N -1 ° (1)

n=0 где x(n) — элементы исходной последовательности длины:

X(k) — элементы преобразованной последовательности:

WN "— весовые коэффициенты, WN "27Cnk

-!— е

Рассмотрим работу устройства для случая T2/T> -4, К- 8. N 12. Будем рассматоивать наиболее распространенный на практике случай, когда на вход устройства подается последовательность действительных отсчетов. 1 е. x(n) - Re x(n). Im x(n) - 0 (где

ReA, ImA — соответственно действительная и мнимая части числа А). Следовательно, необходимо получить на выходе устройства, следующие результаты:

N- I

ReX(k) - g x(n) ReWN"; (2) л =О и-1

ImX(k) X x(n)ImVN" k. л =0

Для компактности будем обозначать

WN" как М/ ". Пусть необходимо определить X(1), Х(2), Х(4), Х(5), Х(6), Х(8), Х(9). Х(11).

При описании работы устройства будем различать такт устройства. равный Т2. и подтакт, равный Т1. Такт устройства разбит на

Т2/T> - 4 подтакта и обозначается А. В. Бе

А-номертакта, В-номер подтакта, В-1-4.

Начало такта совпадает с передним фронтом синхросигнала. поступающим с второго выхода счетчика 24 на второй тактовый вход модуля. На первый вход устройства подается с выхода элемента ИЛИ-HE 29 управляйщая последовательность с периодом М, состояг;ая иэ одной "1" и (М-1) "0" (длительность как "0", так и "1" равна Т2, а на второй управляющий вход устройства с выхода дешифратора 28 подается с периодом N noследовательность, состоящая из одной "1" и (N-1) "0" (фиг. 3).

Первый такт. 1.1. В регистр 5.1 принимается Х(0).

5 1.3. На первый управляющий вход устройства подается "1".

Второй такт. 2.1. В регистр 5.1 принимается Х(1), в регистр 5.2 — Х(0). Триггер 7.2 устанавливается в единичное состояние.

10 2.3. На четвертый управляющий входустройства подается "1", на второй — "0"..

Третий такт. 3.1. В регистр 6.4 принимается Х(0), в регистр 6.3 — Х(1). в регистр 5.1—

Х(2), триггер 7.2 сбрасывается в "0". триггер

15 7.1 и 10 устанавливаются в "1". На вторые входы умножителей 2.3 и 2.4 подаются коэффициенты ReW u. ReWo соответственно.

Сумматор 4.2 выполняет операцию "А+О"-и . в конце подтакта на вход регистра 8.2 посту20 пает х(о)йеИР + x(1)ReW .

3.2. В регистр 8.2.4 записывается

x(o)ReW + x(1)ReW, на вторые входы умножителей 2.3 и 2.4 подаются x(o)W и ImW . В о конце портакта на вход регистра 8.2.4 посту25 пает x(o)ImW + x(1)lmW .

3.3. Содержимое регистра 8.2.4 переписывается в регистр 8.2.3. а в регистр 8.2.4 записывается результат с выхода сумматора 4.2, На вхоуы умножителей 2.3 и 2.4 по30 ступают ReV u ReW . На четвертый о управляющий входустройства подается "0", 3,4. Производится соответствующая перезапись содержимого регистров 8.2.4.

8.2.3 и 8.2.2. На вторые входы умножителей

35 2,3 и 2.4 подаются ImW u lmW .

Четвертый такт. 4.1. В регистры 6.2 и 6.1 принимаются Х(2) и Х(3), в регистр 5.1-Х(3), триггер 7.1 устанавливается в "0". производится перезапись информации в регистрах

40 82.

B дальнейшем описании работы устройства не будем специально оговаривать запись информации в регистры 8.1 и 8.2. так как она производится в начале каждого под-

45 такта. На вторые входы умножителей 2.1, 2.2. 2.3, 2.4 подаются соответственно ReW . э

ReW, ReW44, ReW . В конце подтакта на выходе счмматооа 4.1 формируется ReX(1) -.

x(o)ReW + х (1)ReW + Х(2)йеФ/ + X(3)ReW .

50 4.2. На вторые входы умножителей 2.1, .

2.2. 2.3 и 2.4 подаются соответственно

ImW, ImW ImW4, ImW

В конце подтакта на выходе сумматора

4.1 формируется ImX(1) 4.3. На первые вхо55 ды умножителей 2.1, 2.2, 2.3 и 2.4 подаются соответственно ReW, Веча, ReW ReW .

6 . 4 5 0

На выходе сумматоров 4.1 и 4.2 формируется ReX(2) и ReX(5). 4.4. На вторые входы умножителей 2.1, 2.2, 2.3 и 2.4 подаются соответственно ImW, ImVv . ImW . ImW .

6 ° 4 5 0

1725228

На выходах сумматоров 4.1 и 4.2 формируются соответствующие результаты.

Пятый такт. 5.1. В регистр 5.1 принимается Х(4). На вторые входы умножителей 2.1, 2.2, 2.3 N 2.4 поступают ReW . ReVI, ReW йеФ . На выходах сумматоров 1.4 и 4.2 формируется ReX(4) и ReX(6). 5.2. На вторые входы умножителей 2.1, 2.2, 2.3. 2.4 поступают ImW,!гпМР. ImW, ImWO. На выходах сумматоров 4.1 и 4.2 формируется ImX(4), ImX(6).

5.3. На вторые входы умножителей 2.1, 2.2, 2.3, 2.4 поступают ReW, ReW, ReW .

Э 10

ReW0. На выходах сумматоров 4.1 и 4.2 формируются ReX(5), ReX(8). Нэ второй управляющий вход устройства подается м1".

S.4. На вторые входы умножителей 2.1

2.2, 2.3 и 2.4 поступают ImW, ImW,! гпФГ

Э 10 и ImW .

Шестой такт. 6.1. В регистры 5.1 и 5.2 принимаются Х(5) и Х(4) соответственно.

Триггер 7.2 устанавливается в единичное состояние. На вторые входы умножителей

6 о

2.1, 2.2, 2.3 и 2.4 поступают ReW . ReW .

ReW9, ReW . На выходах сумматоров 4.1 и

4.2 формируются ReX(6). ReX(9).

fi.2. На входы умножителей 2 поступают коэффициенты, необходимые для формирования- lmX(6), ImX(9).

6.3. На входы умножителей 2.1, 2.2, 2.3

2.4 ReWî ReW4 ReWII ReWо

На выходах сумматоров 4.1. 4.2 формируются ReX . ReX .

6.4, На входы умножителей 2 поступают .Im части коэффициентов. поступающих в подтакте 6.3.

Седьмой такт. 7.1. В регистр 5.1 принимается Х(6), в регистр 6.3 и 6.4 — Х(5) и Х(4) соответственно. Триггер 7.1 устанавливается в "1", а триггеры 7.2 и 10 сбрасываются в

"0". На входы умножителей 2.1, 2.2, 2.3 и 2.4 поступают ReW . ReW . ReW, ReW . С вы3 6 5 4 хода регистра 9.2.4 на второй вход сумматора 4.2 поступает ReX(1). Сумматор 4.2 начинает выполнять операцию "А+В". На выходах сумматоров 4.1 и 4.2 формируется

ReX(9) и ReX(1).

7.2. На входы умно кителей 2 поступают

Im части коэффициентов, поступающих в подтакте 7.1. Так как в четных подтактах вычисляется мнимая часть выходных счетов, действительная часть которых вычислялась ь предыдущем подтакте. то в дальнейшем описании работа устройства в этих подтактах будет опускаться.

7.3. Ка входы умножителей 2.1. 2.2. 2.3 и 2.4 поступают ReW, ReW, ReW, ReW, 9 10 10 8 на выходах сумматоров 4.1 и 4.2 формируется ReX(11), ReX(2), Восьмой такт, 8.1. В

5.1 принимается соотве

Х(7). Триггер 7.1 сбрасы ходы умножителей 2.1, 5 пают ReW, ReW6, ЯеЮР. ReW4 На выходах сумматоров 4.1 формируется ReX(1), ReX(4).

8.3. На входы умножителей 2.1 2.2, 2. 1 и 2.4 поступают ReW . ReW . ReW ° ReW".

На выходах сумматоров 4.1 и 4.2 формиру10 ется ReX(2), ReX(5), Девятый такт. В регистр 5.1 принимается Х(8), Входные отсчеты Х(7), Х(6). Х(5), Х(4) умножаются на соответсувующие коэффициенты, необходимые для формирования

15 всех выходных отсчетов.

Десятый такт. В регистры 5.1 и 5.2 принимаются Х(9) и Х(8) соответственно. Ilpoдолжаются вычисления с прежними . входными отсчетами.

20 Одиннадцатый такт. В регистры 5.1. 6.3 и 6.4 принимаются Х(10), Х(9), X(8} соответьг

"твенно. На выход д умножителей 2.1, 2.2.

3 6 9

2.3 и 2.4 поступе ют ReW . ReW . ReW .

ReW8. На сумматорах 4.1 и 4.2 формируется

25 ReX(9), ReX(1):

Двенадцатый такт. В регистры 5.1. 6.3 и

6.2 принимаются Х(11). (11). Х(10) соответственно. На входы умножителей 2.1 2.2, 2.3 и

2.4 поступают R W ° ReW . ReW . ReW . В

30 сумматоре 4.1 заканчиеэется формирование действительной части первого полного выходного отсчета ReX(1). который в начале тринадцатого такта появляется на выходе

15 устройства.

35 Тринадцатый такт. 13,1. В регистр 5,1 принимается первый отсчет нового входного массива Х(0). На выходе 15 устройства

Re X(1).

13.2, На выходе 15 устройства ImX(1).

40, 23.3. На первый управляющий вход устройства подается "1".

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

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

45 (М вЂ” целое число) вычислительных модулей. дешифратор. элемент ИЛИ-НЕ. счетчик и генератор тактовых импульсов, выход которого подхлючен к первому твхтоеому входу

1-го (I - 1. М/2) вычислительного модуле и

50 счетному входу счетчика. информационный выход которого подключен к входу дешифратора. первый и вто ой информационные выходы J-го Ц 1, М 2-1) вычислительного модуля подключены соответственно к пер55 вому и второму информационным входам ()+1)-го вычислительного модуля. третий информационный и тактовый выходы которого подключены соответственно к третьему информационному и второму тактовым входам

j-го вычислительного модуля. пе .алый ин1725228

15

25

j-го вычислительного модуля, первый информационный вход nepaoro вычислительного модуля является первым информационным входом устройства, причем каждый вычислительный модуль содержит входной регистр, два регистра операндов, два умножителя, два сумматора, два блока регистров суммы и триггер, при этом М/2-й вычислительный модуль содержит дополнительно второй триггер. в каждом вычислительном модуле выход входного регистра является первым информационным вьходом вычислительного модуля и подключен к информационному входу первого регистра операнда, выход которого подключен к первому входу первого умножителя, выход которого подключен к первому входу первого сумматора, выход которого подключен к первому входу второго сумматора, выход которого подключен к информационному входу первого блока регистров, тактовый вход которого соединен с тактовым входом второго блока регистров и подключен к первому тактовому входу вычислительного модуля, вторым и третьим информационными выходами, гактовым выходом и вторым тактовым входом которого являются соответственно выходы второго и первого блоков регистров, прямой выход триггера и информационный вход триггера, второй вход первого сумматора подключен к выходу второго умножителя, первый вход которого подключен к выходу второго регистра операнда. информационный вход которого соединен с информационным входом входного регистра и подключен к первому информационному входу вычислительного модуля, вторым и третьим информационными входами которого являются соответственно информационный вход второго блока регистров и второй вход второго сумматора, первый информационный вход первого вычислительного модуля является информационным входом устройства, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него введены двв группы из М/2 блоков постоянной памяти каждая. и"ричем первый информационный выход счетчика подключен к третьему тактовому входу 1-го (I 2) вычислительного модуля и является выходом синхронизации устройства, установочным входом которого является установочный вход счетчика. информационный выход которого подключен поразрядно к входам элемента ИЛИ-НЕ и к адресным входам l-x блоков постоянной памяти первой и второй групп, выходы которых подключены сооответственно к первому и второму входам коэффициентов 1-го вычислительного модуля, выход элемента ИЛИНЕ порключен к второму тактовому входу

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

М/2-го вычислительного модуля, третий информационнйй выход первого вычислительного модуля является информационным выходом устройства и подключен к atopoMy информационному входу первого вычислительного модуля, причем в каждом вычислительном модуле тактовые входы триггера и входного регистра подключены к третьему тактовому входу вычислительного модуля, первый и второй входы коэффициентов которого подключены к вторым входам соответственно первого и второго умножителей, инверсный выход триггера подключен к тактовым входам первого и второго операндов. а в М/2-м вычислительном модуле — к тактовому входу второго триггера, выход которого подключен к управляющему входу второго сумматора, информационный вход второго триггера подключен к четвертому тактовому входу М/2-ro вычислительного модуля.

ЮЮВ Э O еев

+1725228 .28

Составитель M,Êëèìåíêî

Редактор Л.Веселовская Техред M.Ìîðãåíòàë Корректор М.Куль

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

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

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

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