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

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

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

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

Устройство (фиг. 1 и 2) содержит вычислительные модули 1.1-1.М/2. ГДР М - целое число, содержащее первый 2л и второй 2.2 умножители, первый 3 и второй 4 сумматоры, входной регистр 5. первый 6.1 и второй 6.2 регистры операндов, триггер 7. первый 8 и второй 9 блоки регистров суммы, а М/2-й модуль содержит дополнительно триггер 10.

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

Н И И Г П Э ФОНД

ЭКСПЕРТОВ

ИПП

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

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

Х(к) - 2 () wNkn- 0 k N -1. (1)

п 0

где х(п) - элементы исходной последовательности длины:

Х(к) - элементы преобразованной последовательности:

WNkn - весовые коэффициенты. WNkn 2rtnk

- N .

Рассмотрим работу устройства для случая Tz/Ti - 4, К 8. N 12. Будем рассматривать наиболее распространенный на практике случай, когда на вход устройства подается последовательность действительных отсчетов, t e.x(n)-Rex(n). 1тх(п)-0(где ReA, ImA - соответственно действительная и мнимая части числа А). Следовательно, необходимо получить на выходе устройства . следующие результаты:

ReX(k) - Ј Ф) ReWNnk: (2)

п 0

N- 1.

lmX(k)- Г x(n)lmVNn . n 0

Для компактности будем обозначать WNnk как W. Пусть необходимо определить Х(1). Х(2), Х(4). Х(5), Х(6). Х(8), Х(9). Х(11).

При описании работы устройства будем различать такт устройства, равный Tj. и под- такт, равный Ti. Такт устройства разбит на T2/Ti - 4 подтакта и обозначается А. В. где А-номер такта, В-номер подтакта, В- f-4. Начало такта совпадает с передним фронтом синхросигнала, поступающим с второго выхода счетчика 24 на второй тактовый вход модуля. На первый вход устройства подается с выхода элемента ИЛИ-НЕ 29 управляющая последовательность с периодом М. состоящая из одной 1 и (М-1) О (длительность как О, так и 1 равна Т2. а на второй управляющий вход устройства с выхода дешифратора 28 подается с периодом N последовательность, состоящая из одной Г и (N-1) О (фиг. 3).

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

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

Третий такт. 3.1. В регистр 6.4 принимается Х(0), в регистр 6.3 - Х(1). в регистр 5.1 - Х(2), триггер 7.2 сбрасывается в О, триггер

5 7.1 и 10 устанавливаются в Г. На вторые вход.ы умножителей 2.3 и 2.4 подаются коэффициенты ReW1 и ReW° соответственно. Сумматор 4.2 выполняет операцию в конце подтакта на вход регистра 8.2 посту0 naeTx(o)ReW° + x(1)ReW

5 2.3 и 2.4 подаются ImW2 и lmW°.

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

0 8.2.

В дальнейшем описании работы устройства не будем специально оговаривать запись информации в регистры 8.1 и 8.2. так как она производится в начале каждого под5 такта. На вторые входы умножителей 2.1. 2.2,2.3,2.4 подаются соответственно ReW3. ReW2, ReW4. ReW°. В конце подтакта на выходе cvMMSTooa 4.1 Формируется ) -. - x(o)ReW°+ x (l)ReW1 + X(2JReW2 + XftlReW3.

0 4.2. На вторые входы умножителей 2.1. 2.2, 2.3 и 2.4 подаются соответственно ImW3, ImW2. ImW4. ImW0.

В кокце подтактэ на выходе сумматора 4.1 формируется 1тХ(1)4.3. На первые вхо5 ды умножителей 2.1, 2.2. 2.3 и 2.4 подаются соответственно ReWG. ReW4. ReW5. ReW°. На выходе сумматоров 4.1 и 4.2 формируется ReX(2) и ReX(5). 4.4. На вторые входы умножителей 2.1. 2.2. 2.3 и 2.4 подаются соответственно ImW6. ImW4. ImW5. ImW0.

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

Пятый такт. 5.1. В регистр 5.1 принимается Х(4). На вторые входы умножителей 2.1, 2.2. 2.3 и 2.4 поступают ReW°. ReW8. ReW6, На выходах сумматоров 1.4 и 4.2 формируется ReX(4) и ReX(6). 5.2. На вторые входы умножителей 2.1. 2.2. 2.3. 2.4 поступают IrnW0, ImW8. IrnW6, IrnW0. На выходах сумматоров 4.1 и 4.2 формируется 1тХ(4), 1тХ(6).

Шестой такт. 5.1. В регистры 5.1 и 5.2 принимаются Х(5) и Х(4) соответственно. Триггер 7.2 устанавливается в единичное состояние. На вторые входы умножителей 2.1. 2.2. 2.3 и 2.4 поступают ReW6. ReW°. ReW9. ReW°. На выходах сумматоров 4.1 и 4.2 формируются ReX(6). ReX(9).

Седьмой такт. 7.1. В регистр 5.1 принимается Х(6). в регистр 6.3 и 6.4 - Х(5) и Х(4) соответственно. Триггер 7.1 устанавливается в 1. а триггеры 7.2 и 10 сбрасываются в О. На входы умножителей 2.1,2.2.2.3 и 2.4 поступают ReW3. ReW6. ReW5. ReW4. С выхода регистра 9.2.4 на второй вход сумматора 4.2 поступает ReX(1). Сумматор 4.2 начинает выполнять операцию А+В. На выходах сумматоров 4.1 и 4.2 формируется ReX(9) и ReX(1).

Восьмой такт. 8.1. В регистры 6.1. 6.2 и

сумматоров 4.1 формируется ReX(1). ReX(4).

и 2.4 поступают ReW2. ReW°. ReW1. ReW8.

На выходах сумматоров 4.1 и 4.2 формиру10 ется ReX(2). ReX(5).

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

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

0 Одиннадцатый такт. В регистры 5.1. 6.3 и 6.4 принимаются Х(10). Х(9). Х(8) соответственно. На выходы умножителей 2.1. 2.2. 2.3 и 2.4 поступгют ReW3. ReW6. ReW9. ReW8. На сумматорах 4.1 и 4,2 формируется 5 ReX(9), ReX(1):

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

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

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

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

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

5 (М - целое число) вычислительных модулей, дешифратор, элемент ИЛИ-НЕ, счетчик и генератор тактовых импульсов, выход которого подключен к первому тактовому входу 1-го (1 1, М/2) вычислительного модуля и

0 счетному входу счетчика, информационный выход которого подключен к входу дешифратора, первый и второй.информационные выходы )-го 0 1. М/2-1) вычислительного модуля подключены соответственно к пер5 вому и второму информационным входам 0+1)-го вычислительного модуля, третий информационный и тактовый выходы которого подключены соответственно к третьему информационному и второму тактовым входам J-го вычислительного модуля, инj-ro вычислительного модуля, первый информационный вход первого вычислительного модуля является первым информационным входом устройства, причем каждый вычислительный модуль содержит входной регистр, два регистра операндов, два умножителя, два сумматора, два блока регистров суммы и триггер, при этом М/2-й вычислительный модуль содержит дополнительно второй триггер, в каждом вычислительном модуле выход входного регистра является первым информационным выходом вычислительного модуля и подключай к информационному входу первого регистра операнда, выход которого подключен к первому входу первого умножителя, выход которого подключен к первому входу первого сумматора, выход которого подключен к первому входу второго сумматора, выход которого подключен к информационному входу первого блока регистров, тактовый вход которого соединен с тактовым входом второго блока регистров и подключен к первому тактовому входу вычислительного модуля, вторым и третьим информационными выходами, тактовым выходом и вторым тактовым входом которого являются соответственно выходы второго и первого блоков регистров, прямой выход триггера и информационный вход триггера, второй вход первого сумматора подключен к выходу второго умножителя, первый вход которого подключен к выходу второго регистра операнда, информационный вход которого соединен с информационным входом входного регистра и подключен к первому информационному входу вычислительного модуля, вторым и третьим информационными входами которого являются соответственно информационный вход второго блока регистров и второй вход второго сумматора, первый информационный вход первого вычислительного модуля является информационным входом устройства, отличающе- е с я,тем, что, с целью повышения быстродействия, в него введены две группы из М/2 блоков постоянной памяти каждая, причем

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

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

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

|2ц /л-у-у. ......

JlJTJTJTJlJ-lJlJnjTJT

qpw3