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

На фиг.1 показана структурная cxe-js Р°и вход сумматора-вычитателя 9 и ма устройства; на фиг. 2 --алгоритм через второй 12 мультиплексор на другой вход сумматора 14. Синхронизатор 1 одновременно с передачей в счетчик 4 сигнала для формирования адре- 20 са первого операнда подает управляю(быстрого преобразования Фурье (БПФ), реализованный в устройстве.

Устройство содержит синхронизатор 1, счетчик 2 адреса, блок 3 постоянной памяти, счетчик 4 адреса, вхрд- ной регистр 5, регистр 6, входной регистр 7, блок 8 памяти, сумматор- вычитатель 9, умножитель 10, первый 11 и второй 12 мультиплексоры, первый 13 и второй 14 сумматоры, третий мультиплексор 15, информационные вход 16 и выход 17.

Граф алгоритма БПФ приведен для исходного массива длиной в 16 значений. На фиг„2 используются следующие обозначения: входная последовательность 18, выходная последовательность

щие сигналы в сумматор-вычитатель 9, переводя его в режим суммирования операндов, и на входы мультиплексоров 11 и 12 для коммутации выходов вход25 ных регистров 5 и 7 на входы сумматора 14. Сумматор-вычитатель 9 осуществляет сложение операндов, поступающих на его входы, а сумматор 14 - вычитание второго операнда из перво30 го. С выходов сумматора-вычитателя 9 и сумматора )4 результаты поступают соответственно на четвертый и второй входы мультиплексора 15. До сигналам с синхронизатора 1 эти данные после30 го. С выходов сумматора-вычитателя 9 и сумматора )4 результаты поступают соответственно на четвертый и второй входы мультиплексора 15. До сигналам с синхронизатора 1 эти данные после19, коэффициентов Фурье, операции 20, дозательно передаются в блок 8 памяприменяемые в алгоритме.

Устройство работает следующим образом.

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

На этапе ввода по сигналам синхронизатора 1 счетчик 4 адреса формирует и передает на блок 8 памяти по- дс следовательность адресов, по которым в него записывается исходная информация, поступающая через мультиплексор 15 с входа 16.

Этап вычисления коэффициентов Фурье включает несколько шагов. На первом шаге в соответствии с алгоритмом выполняются операции сложения и вычитания отсчетов. Синхронизатор 1 перети я фиксируются по адресам операндов, считанных из него в начале выполнения шага. Аналогично происходит обработка остальных пар отсчетов 40 на первом шаге алгоритма.

Выполнение второго шага включает только операции сложения-вычитания и происходит в целом подобно первому шагу. Однако в данном случае используются другие коды адресов, задаваемые по командам синхронизатора 1 из счетчика 4 в блок 8 памяти (в данном случае из блока 8 памяти в соответствии с алгоритмом так же, как и на предыдущем шаге, выбираются такие пары операндов, над которыми надо производить операции сложения и вычитания). Кроме того, на данном шаге

50

Выполнение второго шага включает только операции сложения-вычитания и происходит в целом подобно первому шагу. Однако в данном случае используются другие коды адресов, задаваемые по командам синхронизатора 1 из счетчика 4 в блок 8 памяти (в данном случае из блока 8 памяти в соответствии с алгоритмом так же, как и на предыдущем шаге, выбираются такие пары операндов, над которыми надо производить операции сложения и вычитания). Кроме того, на данном шаге

дает в счетчик 4 сигнал, по которому присутствуют операнды, над которыми

в последнем формируется и передается на блок 8 памяти код адреса первого операнда, представляющего собой некоторый i-й входной отсчет (,1,...

не требуется выполнять какие-либо преобразования (с номерами N/2 и N/4 Эти отсчеты не считываются из блока 8 и не подвергаются обработке.

щие сигналы в сумматор-вычитатель 9, переводя его в режим суммирования операндов, и на входы мультиплексоров 11 и 12 для коммутации выходов входных регистров 5 и 7 на входы сумматора 14. Сумматор-вычитатель 9 осуществляет сложение операндов, поступающих на его входы, а сумматор 14 - вычитание второго операнда из первого. С выходов сумматора-вычитателя 9 и сумматора )4 результаты поступают соответственно на четвертый и второй входы мультиплексора 15. До сигналам с синхронизатора 1 эти данные последозательно передаются в блок 8 памяти я фиксируются по адресам операндов, считанных из него в начале выполнения шага. Аналогично происходит обработка остальных пар отсчетов на первом шаге алгоритма.

Выполнение второго шага включает только операции сложения-вычитания и происходит в целом подобно первому шагу. Однако в данном случае используются другие коды адресов, задаваемые по командам синхронизатора 1 из счетчика 4 в блок 8 памяти (в данном случае из блока 8 памяти в соответствии с алгоритмом так же, как и на предыдущем шаге, выбираются такие пары операндов, над которыми надо производить операции сложения и вычитания). Кроме того, на данном шаге

присутствуют операнды, над которыми

не требуется выполнять какие-либо преобразования (с номерами N/2 и N/4). Эти отсчеты не считываются из блока 8 и не подвергаются обработке.

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

Помимо процедур, выполняемых на первом и втором шагах, вводятся две дополнительные вычислительные процедуры.

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

Данная процедура является основной для последнего n-го шага алгоритма (выполняется над N-4 операндами). Кроме того, она присутствует в 1шагах с номерами 3,4,...,п-1 и выполняется в каждом из них над 2 операндами, где k - номер шага. , Устройства при выполнении этой процедуры функционирует следующим образом.

По сигналам с синхронизатора 1 счетчик 4 последовательно формирует коды адресов, по которым из блока 8 памяти считывается очередная пара операндов и записывается во входные регистры 5 и 7 (отсчитываемые операнды а,Ь выбираются такими, над которыми должна быть выполнена пара операций a+cb и a-cb. Для представленного на фиг.2 алгоритма при на третьем шаге это отсчеты с номерами 8 и JO, J2 и J4; на четвертом (последнем) шаге -4и5; 6и7и т.д.). Одновременно по сигналам из синхронизатора 1 счетчик 2 адреса фомирует и передает на блок 3 постоянной памяти код адреса, по которому из него считываются и фиксируются в регистре значения соответствующего весового коэффициента. С выхода регистра 6 код коэффициента передается на вход первого множителя 10, на второй вход которого передается содержимое входного регистра 7. Результат умножения подается на второй вход сумматора 13 и через мультиплексор 12 на первый вход сумматора 14. На другие входы сумматоров 13 и 14 чере мультиплексор 11 подается код one- ранда с выхода первого входного регистра 5. В сумматоре 13 происходит сложение, а в сумматоре 14 вычитание

IS

20

25

10

764884

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

Вторая вычислительная процедура описывается парой выражений вида (a-b)+2cb и (a-b)-2cb. Отличие ее выполнения от первой процедуры заключается в том, что мультиплексор 11 подключает на входы сумматоров 13 и 14 не входной регистр 5 а сумматор- вычитат ель 9, который переводится в режим вычитания синхронизатором 10 Кроме того, с выхода блока 3 постоянной памяти считывается значение удвоенного весового коэффициента. Результаты выполнения процедуры из сумматоров 13 и 14 через мультиплексор 14 передаются в блок 8 памяти и фиксируются в нем о Аналогично производится обработка и остальных пар операндов. На этом заканчивается обработка устройством третьего шага алгоритма.

Последующие шаги, вплоть до (п-1) го подобны третьему шагу алгоритма и выполняются в целом так же, как описано выше, но с другими значениями весовых коэффициентов и операндов. На последнем шаге алгоритма над отсчетами с номерами О,1 выполняется пара операций вида а+b, а-Ь, которая характерна для первого шага. Над отсчетами с номерами 2 и 3 операций не производится. Над остальными парами операндов производятся операции, аналогичные первой вычисли- ,тельной процедуре алгоритма с номерами 3,4,...,п-1,

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

Выдача результатов и восстановление требуемого порядка следования выходных отсчетов производится на этапе вывода. Счетчик 4 по сигналам из синхронизатора 1 формирует коды адресов, в порядке, обеспечивающем считывание из блока 8 и выдачу на выход 17 коэффициентов преобразования Фурье в нормальной последовательности, т„е.

а0,а,,...,а N/2, b,,b,...,b N/2.

30

35

40

45

50

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

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

Изобретение относится к цифровой вычислительной технике и может быть использовано в системах и устройствах цифровой обработки информации в качестве преобразователей временной последовательности действительных отсчетов входного сигнала в частотную последовательность. Цель изобретения - повышение быстродействия устройства (за счет совмещения по времени выполнения операций в шагах алгоритма, начиная с третьего). Поставленная цель достигается за счет того, что в состав устройства входят синхронизатор 1, счетчик адреса 2, блок постоянной памяти 3, счетчик адреса 4, входной регистр 5, регистр 6, входной регистр 7, блок памяти 8, сумматор-вычислитель 9, умножитель 10, мультиплексоры 11, 12, сумматоры 13, 14, мультиплексор 15, информационные вход 16 и выход 17. 2 ил.

мой выходы которого подключены к так- 25 МУ информационному входу сумматора-вытовым входам соответственно первого и второго входных регистров, умножитель, два сумматора, первый, второй и третий мультиплексоры, выходы которых подключены соответственно к первому входу первого сумматора, пер- ,вому входу второго сумматора и информационному входу блока памяти, выходы первого и второго сумматоров подключены соответственно к первому, второму информационным входам третьчитателя, выход которого подключен к четвертому информационному входу третьего мультиплексора и второму информационному входу первого мульти- плексора, выход которого подключен к второму входу второго сумматора, второй вход первого сумматора подключен к выходу умножителя, а управляющий вход сумматора-вычитателя подключен к одиннадцатому выходу синхро

низатора,

К

г . к т Т

-J.f..JiEalIL J

/

/

Фие.2