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

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее два коммутатора, два арифметических блока, блок памяти и блок управления, состоящий из тактового генератора, счетчика циклов, счетчика итераций и двух деп ифраторов, причем ВЫХ.ОД тактового генератора в блоке управления подключен к входу счетчика .циклов, выход переполнения счетчики циклов подключен к входу счетчика итераций, информационные выходы счетчика циклов и счетчика инетарций подключены соответственно к первым и вторым входам первого и второго дешифраторов, выход первого дешифратора в блоке управления является первым выходом блока управления и подключен к адресному входу блока памяти, первый и второй выходы второго дешифратора в блоке управления явля- . ются вторым и третьим выходами блока управления и подключены к управляющим входам первого и второго коммутаторов соответственно, информационный вход и выход блока памяти являются входом и выходом устройства, выход блока памяти подключен к информационному входу первого коммутатора, выход второго коммутатора подключен к информационному входу блока памяти, отличающееся тем, что, с целью упрощения устройства и повышения его быстродействия, первый арифметический блок содержит ч-етыре входных регистра, два сумматора, два вьгаитателя, два коммутатора и четыре выходных регистра,причем информационные входы всех входных регистров первого арифметического блока образуют его информационный вход и подключены к первому выходу первого коммутатора, выход первого входного регистра в первом арифметическом блоке соединен с первым входом первого сумматора и с суммирующим входом перЮ lib вого вычитателя, выход второго входного регистра в первом арифметическом блоке соединен с первым входом Ю С jQ второго сумматора и суммирующим входом второго вычитателя, выход третьего входного регистра в первом арифметическом блоке соединен с вторым входом первого сумматора и с вычитающим входом первого вычитателя, выход четвертого входного регистра в первом арифметическом блоке соединен с вторым входом второго сумматора и- с вычитающим входом второго вычитателя, выходы первого сумматора и первого вычитателя в первом арифметическом блоке соединены с соответствую

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

Известно устройство для вычисления быстрого преобразования Фурье (БПФ), содержащее блок управления, арифметический блок, коммутаторы с соответ:твующими связями межДУ блоками lj

Данное устройство выполняет алгоритмы БПФ упрощенным методом, однако

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

Наиболее близким к изобретению является устройство для вычисления ВПФ, содержащее два арифметических блока, блок памяти, блок управления и два коммутатора, причем первый и второй выходы первого коммутатора соединены с информационными входами соответственно первого и второго арифметических блоков, информацион3ные выходы которьк подключены соответственно к первому и второму входам второго коммутатора, выход которого соединен с информационным входом блока памяти, информационный вы ход которого подключен к входу первого коммутатора, первый выход блока управления подключен к адресному входу блока памяти, второй выход бло ка управления соединен с. тактовыми входами арифметических блоков, третий и четвертый выходы блока управления соединены с управляющими входа ми соответственно первого и второго коммутаторов, информационный вход и выход блока памяти является соответственно информационным входом и выходом устройства. Данное устройство также выполняет БШ по упрощенному алгоритму z , Однако арифметические блоки, хотя и учитывают специфические особенности коэффициентов применяемого упрощения алгоритма, выполнены по универ сальной схеме, позволяющей осуществлять любую базовую операцию упрощен ного алгоритма БГИ и поэтому имеют сложную структуру. Устройство выполняет упрощенный алгоритм с параметром о. н/4, но в ряде случаев может быт допущена и более низкая методическая погрешность вычислений. Более того, применение эффективного по быстродействию сглаживания в частотной области результатов упрощенных алгоритмов БПФ позволяет значительно повысить методическую точность вычисления спектра упрощенными методами и, тем самым, определяют рациональность применения упрощенных алгоритмов с параметром et (вместо ) с учетом затрат аппаратуры и быстродействия. изобретения - упрощение уст ройства и повышение его быстродейст вия. Поставленная цепь достигается тем, что в устройстве для вычисления БПФ, содержащем два коммутатора, два арифметических блока, блок памяти и блок управления, состоящий из так тового генератора, счетчика циклов, счетчика итераций и двух дешифраторов, причем выход тактового генератора в блоке управления подключена к входу счетчика циклов, выход пере полнения счетчика циклов подключен к входу счетчика итераций, информа234ционные выхода счетчика циклов и счетчика итераций подключены соответственно к первым и вторым входам первого и второго дешифраторов, выход первого дешифратора в блоке управления является первым выходом блока управления и подключен к адресному входу блока памяти, первый и второй выходы второго дешифратора в блоке управления являются вторым и третьим выходами блока управления и подключены к управляюш;им входам перврго и второго Kc.JMi гаторов соответственно, информационный вход и выход блока памяти являются входом и выходом устройства, выход блока памяти подключен к информационному входу первого коммутатора, выход второго коммутатора подключен к информационному входу блока памяти, первый арифметический блок содержит четыре входных регистра, два сумматора, два вычитателя, два коммутатора и четыре выходных регистра, причем информагщонные входы всех входных регистров первого арифметического блока образуют его информационный вход и подключены к первому выходу первого коммутатора, выход первого входного регистра в первом арифметическом блоке соединен с первым входом первого сумматора и с суммирукяцим входом первого вычитатепя, выход второго входного регистра в первом арифметическом блоке соединен с перв1 1м входом второго сумматора и с суммирующим входом второго вычитателя, выход третьего входного регистра в первом арифметическом блоке соединен с вторым входом первого сумматора и с вычитакндим входом первого вычитателя, выход четвертого входного регистра в первом арифметическом блоке соединен с вторым входом второго суммато- . ра и с вычитающим входом второго вычитателя, выходы первого сумматора и первого вычитателя в первом арифметическом блоке соединены с соответствующими инфсрмациокными входами первого коммутатора в этом блоке, выходы второго сумматора и второго вычитателя в первом арифметическом блоке соединены с соответстВУЮ1ЦИМИ информащюнными входами второго коммутатора в этом блоке, первый и второй выходы первого коммутатора в первом арифметическом блоке подключены к информационным входам первого и второго выходных регистров этого блока, первый и второй выходы второго коммутатора fe первом арифметическом блоке подключены к информационным входам третьего и чет вертого выходных регистров этого блока, выходы всех выходных ,|)егистров первого арифметического блока образуют его вьпсод и подключены к первому информационному входу второго коммутатора, второй арифметический блок содержит четыре-, входных регистра, два .сумматора, два вычитателя и четыре выходных регистра, причем информационные входа всех входных регистров второго арифметического блока образуют его информационный вход и подключены к второму вькоду первого коммутатора, выход первого входного регистра во втором арифметическом блоке соединен с первым входом первого сумматора и суммирующим входом первого вычитателя, выход второго входного регистра во втором арифметическом блоке соединен с первым входом второго сумматора и с суммирующим входом второго вычитателя, выход третьего входного регист ра во втором арифметическом блоке соединен с вторым входом второго сум матора и с вычитающим входом второго вычитателя, выход четвертого входного регистра во втором арифметическом блоке соединен с вторым входом перво го сумматора и с вычитающим взводом первого вычитателя, выходы первого и второго сумматоров,-а также первого и второго вычитателей во втором арифметическом блоке соединены с ин-г формационными входами соответствующих выходных регистров этого блока, выходы которых образуют выход второго арифметического блока и подключены к второму информацирнному входу второго коммутатора, блок управления содержит элемент ИЛИ и элемент И, причем вькод счетчика итераций в бло ке управления поразрядно подключен . к входам элемента РШИ, выход которого, а также выход тактового генерато ра подключены к входам элемента И, третий.выход второго дешифратора является четвертым выходом блока управ ления и подключен к управляющим входам первого и второго коммутаторов в первом арифметическом блоке, выход тактового генератора является пятым выходом блока управления и подключен .1 3« к тактовым входам всех входных и выходных регистров э первом арифметическом блоке, выходэлемента И является шестым выходом блока управления и подключен к тактовым входам всех входных и выходных регистров во втором арифметическом блоке. На фиг.1-4 представлены функциональные схемы предлагаемого устройства для вычисления быстрого преобразования Фурье,,блока управления, inepBoro и второго арифтиметических блоков соответственно. Устройство содержит коммутатор 1, арифметические блоки 2 и 3,, коммутатор 4, блок 5 оперативной памяти, блок 6 управления. Блок 6 управления содержит тактовый генератор 7, счетчик 8, циклов, счетчик 9 итераций, элемент ИПИ 10, дёпшфратор 11 адреса памяти, дешифратор 12 адреса коммутаторов, элемент И 13. Арифметический блок 2 содержит входные регистры 14 - 17, сумматоры 18 и 19, вычитатели 20 и 21, коммутаторы 22 и 23, выходные регистры 24 - 27. ... Арифметический блок 3 содержит входные регистры 28 - 31, вычитатель 32, сумматоры 33 и 34, вычитатель 35, выходные регистры 36 - 39. Счетчик 8 циклов блока 6 управления имеет разрядность m logjrN-1, а счетчик итераций - т 1о§21о§2М, где N - размерность вычисляемого быстрого преобразования Фурье. Поскольку предлагаемое устройство реализует алгоритмы с замещением, то адреса первого и второго коммутаторов 1 и 4 одинаковы на каждой базовой операции, поэтому соответствующие выходы блока управления можно объединить. Если же необходимо вьтолнять ашгорнтмы без замещения, то коммутаторы 1 и 4 адресуются по разным выходам блока управления, который в этом случае содержит не один, а два параллельно соединенный дешифраторов адреса коммутаторов. Устройство работает следующим образом. Реализуется упрощенньм алгоритм БПФ с параметром Л П/2 с замещением 4(.,M.Ve. k«0,N4 где X(k) - результат БПФ; Х(п) - последовательность входных отсчетов; А - ближайшее целое к А. Анализ структуры алгоритма БПФ с параметром показывает, что в базовой операции, котОрйя Записывается следукнцим образом: . Г X X + 4.W, ; VrX-4.W, где X, У и X, У - соответственно входные и выходные операнды; W - поворачивающие множители, коэффициенты W могут принимать только при разных значениях 1, j, -1. При этом весь этот набор коэффициентов реализуется на всех Итерациях алгоритма БПФ, кроме начальной с номером О. Устройство реализует описанный алгоритм, при этом арифметический блок 2 реализует базовые операции первого и третьего типа (с коэффициентом Г и -1), а арифметический блок 3 выполняет базовую операцию только .второго типа (умножение на . Работа предлагаемого устройства осуществляется следующим образом. По адресам, формируемым блоком 6 управления, необходимые для каждой конкретной базовой операции пары комплексных операндов через коммутатор 1, считываются во входные рехистры 14-17 и 28-3,1 соответственно ариф метических блоков 2 и 3. При этом во входные регистры 14 и 15 считываются срответственно реальная и мнимая час ти первого комплексного операнда базовой операции первого или.третьего типа, а во входные регистры 16 и 17, с.оответственно реальная и мнимая час ти второго комплексного операнда, не обходимого для базовых операций этог типа. Во входные регистры 28, 29 н 30, 31 арифметического блока 3 записьтаются соответственно реальные и мнймь1е части соответственно первого и второго операндов, используемых в базовой операции второго типа. На вьпсоде сумматора 18 арифметического блока 2 находится величина RgX+RgY, где Rg - вещественная часть числа, на в.ыходе сумматора 19 - , где Ijy, - мнимая часть. Аналогично на выходах вычитаталей 20 и 21 получаются соответственно значения разности вещественных и мнимых частей, т.е. RjX-RgY и . В соответствии с типом базовой операции, который определяется сигналом с одного из выходов дешифратора 12 адреса коммутаторов блока 6 управления, коммутаторы 22 и 23.осуществляют засыпку результатов арифметических действий в соответствующие выходные регистры 24-27, в которых хранятся соответственно реальная и мнимая части соответственно первого и второго операнда результата базовой операции. Таким образом, Осуществляется базовая операция первого j(RgX.(), j(ReX-PeY)jUmX-Im) или третьего типов :(ReX-M)i(l,,,), |()vj(). Аналогичным образом находится результат базовой операции второго типа. Реальные и мнимые части первогои .второго операндов поступают соответственно во входные регистры 28-31 арифметического блока 3. В результате, на выходе вычитателя 32 находится RgX-RgY, на выходе сумматора 33 КеУ на выходе сумматора 34 RgX+If y, а на выходе вычитателя 35 l X-Ctgy. Далее результаты записываются в выходной регистр 36. По окончании вычислений базовых операций результаты -переписываются через коммутатор 4 в блок 5 памяти по тем же адресам, по которым они быпи считаны. Вычисления прекращаются по выполнении. log«N итераций. Блок 6 управления работает следующим образом.. Генератор 7 генерирует последовательность тактовых импульсов, которые подсчитьгоаются счетчиком 8. циклов, код которого определяет номер базовой операции на каждой итерации. Импульс переполнения с выхода этого счетчика 8 циклов поступает на тактовый вход счетчика 9 итераций, код . которого определяет номер текущей итерации. Таким образом, коды счетчи- ка циклов и счетчика итераций полностью определяют номер базовой операции алгоритма БПФ. Эти коды дешиф9,1 руются дешифраторами 11 и 12 адреса, которые определяют соответственно адреса операндов ,в блоке 5 памяти и коммутаторов 1, 4 и 22, 23. Непосредственно с вькода генератора 7 блока 6 управления тактовые сигналы поступают на .тактовые входы входных и выходных регистров арифметического блока 2, синхронизируя прием и вьщачу информации для этого блока. Если код счетчика 9 итерадай нулевой, то на выходе элемента ШШ присутствует уро вень логического нуля, и тактовые импульсы не проходят на тактовые входы входных и выходных регистров арифметического блока 3. Таким образом, арифметический блок 3 на началь ной итерации не функционирует.

- i310 Базовых итердций второго типа ровно столько, сколько базовых операций первого и третьего Фипа вместе взятых. Значит арифметические блоки работают на кахздой итерации без ожидания. Таким образом, предлагаемое выполнение устройства для вычисления БПФ позволит существенно упростить конструкцию устройства (практически в 2-4 раза), поскольку вместо двух универсальных арифметических блоков используются два разнотипных, специализированных аналогичных блокаj или при равных с прототипом затратах оборудования в такое же число раз повысить быстродействие.

Фиг. J