УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Российский патент 1994 года по МПК G06F15/332 

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

Предлагаемое устройство в своей работе использует процесс цифровой фильтрации, заключающийся в выполнении свертки
Y_s= X_jω_j, где Х_j - входные отсчеты;
ω_j - некоторые коэффициенты, и о выполнении округления полученного значения
Y*s

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

На фиг. 1 приведена функциональная схема устройства для быстрого преобразования Фурье; на фиг. 2 - вариант выполнения арифметичесокго блока; на фиг. 3 - вариант выполнения (n+1)-го арифметического блока.

Устройство содержит (фиг. 1) блок 1 определения вычетов, арифметические блоки 2.1-2(n+1), входную шину 3 данных, мультиплексор 4, блок 5 хранения коэффициентов, блок 6 восстановления результата, шину 7 адреса коэффициентов, управляющие шины 8, 9, 10, выходную шину 11 данных.

В состав i-го (i= ) арифметического блока (фиг. 2) входят блок 12 коммутации, блок 13 умножения, сумматор 14, регистр 15, выходная шина 16 блока 2, общая управляющая шина 17 блоков 12 коммутаций для арифметических блоков 2. р-1-2. n и управляющие шины регистров 15. i, шина 18 обнуления, шина 19 тактовых импульсов записи.

Арифметический блок 2. (n+1) (фиг. 3) влкючает блок 20 умножения, сумматор 21, регистр 22, блок 23 хранения констант, при этом блок 20 умножения, сумматор 21 и регистр 22 имеют такое же построение, как и в блоке 2. i, отличие составляет блок 23 хранения констант с управляющей шиной 24, являющейся частью адреса.

Блок 1 определения представляет собой n блоков определения вычетов поступающих отсчетов по соответствующим основаниям р_i(i= ) которые могут быть реализованы табличными методами на базе ППЗУ. В этом случае входные коды отсчетов являются адресами соответствующего кода вычетов, записанного в ППЗУ на этапе программирования. Аналогично поступает и блок 5 хранения коэффициентов, состоящий из n+1 блоков 5.1-5. n хранения коэффициентов по соответствующим основаниям р_i(i= ), а блок 5. n+1 блок хранит остатки от деления , например = 3. Требуемый коэффициент из n ППЗУ выбирается по адресу, поступающему по шине 7 адреса коэффициентов или шине 10.

Блоки 13. i умножения, сумматоры 14. i(i= ), выполняющие соответствующие арифметические действия умножения, сложения по соответствующим основаниям p_i(i= ) могут быть реализвоаны табличным методом на базе ППЗУ. В этом случае операнды для выполнения соответствующего арифметического действия будут адресом результата арифметического действия.

Блок 12. i коммутации для арифметических блоков 2. р+1-2. n является известным функциональным устройством, где выбор входной шины определяется номером на шине 17, например потенциал логического "0" на шине 17 всегда коммутирует первый вход на выход блока 12. i коммутации, а потенциал логической "1" - второй.

Блок 23 хранения констант может быть реализован с помощью ППЗУ. В этом случае операции, записанные в регистре 22 при появлении разрешающего сигнала на 24 входе, являются адресом результата арифметического действия.

Известным цифровым устройством является и мультиплексор 4. В зависимости от кода на адресной шине 9 управления один из входов коммутируется на выход.

Блок 6 восстановления результата реализует преобразование конечного результата процессов свертки и округления из непозиционной системы счисления в позиционную - он также может быть реализован табличным методом на базе ППЗУ. В этом случае входные данные являются адресом результата данного процесса преобразования. Считывание информации с блока 6 восстановления результата разрешается подачей списка на управляющий вход 8.

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

В исходном состоянии регистры 15. i обнулены, что производится подачей сигнала на шину 18. На управоляющие входы блоков 12. i коммутации (i= ) подается сигнал, под действием которого происходит коммутация блоков 12. i коммутации на соответствующие выходы данных блоков.

Под действием кода первого входного отсчета Х1 через время выборки адреса на n выходах блока 1 определения вычетов появляются коды вычетов входного отсчета Х₁ по соответствующим модулям: p_i(i= ) Х₁.

Через некоторое время, определямое задержкой на блоках коммутации, данные коды поступают на вход блока 13. i умножения. К этому времени на выходе блоков 5. i появляется значение первого коэффициента W₁, так как одновременно с коммутацией подается сигнал на вход 7, подается адрес первого коэффициента. Через время срабатывания блока 13. i умножения на его выходах появляется результат умножения Y_s,j W по соответствующим модулям, который подается на первый вход сумматора 14. i, на второй вход окторого подается код нуля с регистра 15. i, так как регистр был обнулен. В результате после сложения результат записывается в регистр 15. i по импульсу 19.

Работа устройства реализуется в конвейерном режиме, т. е. в момент поступления кода входного отсчета Х на входы соответствующих блоков 13. i умножения, код второго отсчета подается на входную шину 3 данных и далее весь процесс повторяется аналогично выше описанному (по шине 7 подается адрес второго коэффициента W₂ и т. д. ). Процесс выполнения свертки реализуется до тех пор, пока N-м тактовым импульсом не будет записан результат вычисления свертки Y= Y′s

Этап округления начинается по завершении последней (N-й) операции умножения по модулю p_i в соответствующих блоках 13. i, на управляющие входы блоков 12. j коммутации (j= ) подается сигнал, под действием которого происходит коммутация информационного входа мультиплексора 4 на вход коммутатора 12. i, а также подается сигнал на соответствующие управляющие входы 9 мультиплексора и на блок 5. n+1 хранения констант, при этом вступает в работу мультиплексор 4, подключая к коммутаторам 12. j(j= ), а также к первому входу блока 20 умножения первый канал. Значение вычисленной свертки y_s,i подается на первые входы блока 13. i (i= ) умножения через блоки 12. i коммутации, на второй вход которого с подачей определенного адреса на шину 10 с выхода блока 5. i выдается С_к+1 , а на выходе блока 5. n+1-K. k+1, далее производится сложение в сумматоре 14. j (j= ) со значением Y_s,j (j= ). Далее процесс повтоярется в конвейерном режиме с подачей другого управляющего сигнала на управляющую шину 9 мультиплексора 4, на информационный выход подключается второй каналы и т. д. до р. После прохождения р тактов производится анализ необходимости коррекции полученного результата, т. е. происходит накопление в 2. n+1 арифметическом блоке в регистре 22. На (p+1)-м такте поступает разрешающий сигнал 24 на вход блока 23 хранения констант, на выходе которого появляется результат необходимости коррекции K_k+j, с приходом р+1 на вход мультиплексора на выход его подается результат коррекции K_k+j и происходит сложение с полученными результатами. На вход блоков умножения в этом случае подается код 1 (единицы).

После выполнения всей процедуры округления в регистрах 15. i остается результат выполнения всего алгоритма Y (i= ).

Для преобразования результата из непозиционной в позиционную систему счисления подается сигнал на блок 6 восстановления результата. Через время срабатывания этого блока на выходе появляется искомый результат.

Устройство для быстрого преобразования Фурье относится к области цифровой обработки сигналов и может быть использовано при реализации алгоритмов спектрального анализа, цифровой фильтрации устройств с заданными временными характеристиками на специализированных вычислительных устройствах. Упрощение устройства достигается введением в устройство, содержащее блок 1 определения вычетов, n арифметических блоков 2.1 - 2. n, блок 5 хранения коэффициентов, блок 6 восстановления результата, мультиплексора 4 и (n + 1)-го арифметического блока, а также соответствующих связей между введенными и имеющимися блоками. Преимущество данного устройства заключается в возможности реализовать алгоритм вычисления свертки и процедуру округления на одном позиционном процессоре с использованием канала коррекции округления. 3 ил.

УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блок определения вычетов, n арифметических блоков (где n - число модулей), блок хранения коэффициентов, блок восстановления результата, причем входная шина данных устройства соединена с входом блока определения вычетов, i-й выход которого соединен с информационным входом i-го арифметического блока (где i = 1,2, . . . , n - 2), (n - 1)-й и n-й выходы блока определения вычетов соединены с первыми информационными входами (n - 1)-го и n-го арифметических блоков соответственно, управляющие входы с первого по n-й арифметических блоков соединены соответственно с первого по n-й выходами блока хранения коэффициентов, с первого по n-й адресные входы которого соединены с шиной адреса коэффициентов устройства, выходы (n - 1)-го и n-го арифметических блоков соединены с первым и вторым информационными входами блока восстановления результата, выход которого соединен с выходной шиной данных устройства, отличающееся тем, что устройство дополинетльно содержит мультиплексор и (n + 1)-й арифметический блок, управляющий вход которого соединен с (n + 1)-м выходом блока хранения коэффициентов, (n + 1)-й вход которого соединен с первой управляющей шиной устройства, вторая и третья управляющие шины которого соединены с управляющими входами блока восстановления результата и мультиплексора соответственно, выходы i-го и (n + 1)-го арифметических блоков соединены соответственно с i-м и (n - 2)-м информационными входами мультиплексора, выход которого соединен с вторыми информационными входами (n - 1)-го и n-го арифметических блоков и информационным входом (n + 1)-го арифметического блока.