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

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

Цель изобретения - расширение области применения за счет обеспечения возможности изменения размерности преобразования.

На фиг.1 приведена функциональная схема устройства; на фиг.2 приведена временная диаграмма приема и продвижения информации в процессе обработки по устройству.

Устройство содержит п вычислительных блоков 1i-1n. где п logaN, N - максимальная размерность преобразования, блок 2 синхронизации, тактовый вход 3, вход 4 сброса, регистры 5-7, умножители 8 памяти 9 коэффициентов, элемент НЕ 10, D-триггер

11, арифметические узлы 12, 13 памяти 14 кодов операций, первый элемент И 15, второй элемент И 16, элементы 17, 18 задержки, мультиплексоры 19, 20, коммутаторы 21, счетчик 22, второй информационный выход 23, первый информационный выход 24.

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

Устройство работает следующим образом. При поступлении на вход 4 устройства импульса начала обработки триггер 11 и счетчик 22 адреса устанавливаются в нулевое состояние. Следующим тактовым импульсом, поступающим на вход 3 устройства, триггер 11 устанавливается в

С

о ю ч

о

со о

единичное состояние. Одновременно с тактовым импульсом на входы регистров 5 и 6 поступает первое информационное слово. По заднему фронту тактового импульса на выходе элемента И 15 формируется импульс, по которому на регистр 5 принимается первое информационное слово, а на счетчике 22 устанавливается первый адрес, По второму тактовому импульсу триггер 11 переключается в нулевое состояние. По заднему фронту тактового импульса на выходе элемента И 16 формируется импульс, записывающий в регистр 6 второе информационное слово. В следующем такте информационное слово с регистра 5 переписывается в регистр 7, с регистра 6 записывается в (комплексный) умножитель 8, а в регистр 5 принимается следующее информационное слово. Одновременно на умножитель 8 с памяти коэффициентов 9 принимается значение соответствующего тригонометрического коэффициента.

Адресное пространство памяти 9 коэффициентов и памяти 14 кодов операций состоит из младшей и средней частей. Младшая часть управляется с выхода счетчика (адреса) 22. Старшая часть указывает величину размера обрабатываемого массива и задается с входа 2 устройства, Максимальный размер обрабатываемого массива определяется выражением N 2П, где п - количество блоков или этапов выполнения быстрого преобразования Фурье (БПФ). Тогда количество разрядов старшей части равно целой большей части от log2N. Количество разрядов младшей части адресного пространства определяется выражением

loQ2 2 за счет распараллеливания входной информации на два канала.

Информация в памяти 9 и в памяти 14 кодов операций записана таким образом, что при подходе соответствующего отсчета или уже обработанного отсчета к определенному узлу устройства на него поступают необходимое значение тригонометрического коэффициента и код операции.

В следующем такге с регистра 7 и умножителя 8 информационные слова принимаются на арифметические узлы 12 и 13. С выхода арифметического узла 12 значение A+W В поступает на элемент 17 задержки, а с выхода устройства 13 значение A-W В поступает на коммутатор 21,

Мультиплексоры 19 и 20 принимают информацию или с элементов 17и 18задержки сортветственно или с арифметического узла 12 и коммутатора 21 соответственно, Управление мультиплексорами осуществляется с памяти 14.

Коммутатор 21 выполняет стандартную для потолочного процессора БПФ операцию прямо-накрест.

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

тригонометрических коэффициентов и управляющих сигналов. При этом, если размерность преобразования меньше, в обработке задействованы не все блоки. Блоки, не задействованные в обработке, но через которые проходит информация, работают следующим образом. На (комплексный) умножитель 8 с выхода памяти 9 коэффициентов поступает значение коэффициента, равное 1, т.е. умножитель выполняет умножение на 1. На арифметические устройства с первого и второго выходов памяти 14 поступает код операции, указывающий на пропуск информации: для арифметического узла

12 - пропуск на выход информации, поступающей на второй вход, для арифметического узла 13 - пропуск на выход информации, поступающей на первый вход. На мультиплексор 19 с памяти 14 поступает

управляющий сигнал, по которому он пропускает на выход информацию с арифметического узла 12, минуя элемент 17 задержки. Коммутатор 21 по сигналу от памяти 14 осуществляет передачу информации прямо.

Мультиплексор 20 передает информацию с первого выхода коммутатора 21, минуя элемент 18 задержки,

Формула изобретения ° Устройство для вычисления быстрого преобразования Фурье, содержащее п вычислительных блоков (п log2N, N - максимальная размерность преобразования), блок синхронизации, счетчик и первый ре- гистр, причем первый информационный вход к-го вычислительного блока (k ) соединен с первым информационным выходом (k- 1)-го вычислительного блока, второй информационный выход которого соеди- 5 нен с вторым информационным входом k- го вычислительного блока, первый и второй информационные выходы п-го вычислительного блока являются соответственно первым и вторым информационными выходами устройства, первый выход блока

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

Щи г. 2.

Изобретение относится к вычислительной технике и может быть использовано для построения цифровых фильтров и анализаторов спектра, работающих в реальном масштабе времени. Цель изобретения - расширение области применения за счет обеспечения возможности изменения размерности преобразования. Устройство для этого содержит п вычислительных блоков(п log2N, N - максимальная размерность преобразования), блок синхронизации и счетчик, при этом каждый вычислительный блок содержит умножитель, два арифметических узла, два узла задержки, два мультиплексора, коммутатор, память коэффициентов и память коэффициентов кодов операций. 2 ил