Устройство для вычисления коэф-фициЕНТОВ фуРьЕ Советский патент 1981 года по МПК G06F17/14 

(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ

ФУРЬЕ ственно с выходами второго, четвертого, первого и третьего элементов И узла тактирования, выходы элементов ИЛИ узла тактирования соединены с тактовыми входами соответствующих регистров сдвига, выходы которых соединены со входами арифметического блока, первый вьмод которого сое динен с третьими входами шестого, второго, -ВОСЬМОГО и четвертого элементов И записи, второй выход арифметического блока соединен с третьи ми входами пятого,первого,седьмого и четвертого И записи,выходы пятого, первого, седьмого и тр тьего- элементов И записи соединены информационными входами первых раз рядов соответствующих регистров сдвига, выходы шестого, второго, восьмого и четвертого элементов И записи соединены с информационными входами N/2+1 разрядов соответствующих регистров сдвига, счетный вход триггера соединен со вторым выходом блока управления, третья группа выходов которого соединена с управляющими входами генератора тригонометрических функций. В устройстве заложен алгоритм Стокхэма-Санди, что позволило резко сократить схему и выполнить ее односекционной. Это стало возможным бла годаря полупостоянству структуры гр фа Стокхэма, в каждом участке которого, характеризующая соответствующую итерацию,, операнды пар результа тов базовых операций располагаются с расстоянием в пол-массива аруг от друга; И этот порядок не меняется от итерации к итерации 12, Однако такое постоянство свойственно только правым (выходным) сторонам участков графа, описывающим режим занесения результатов в память, в то время как рисунок левой стороны от участка к участку меняется, т.е. меняется порядок выбора исходных операндов для базовых операций, и его нужно при смене итераций каждый раз организовывать заново. А это естественно, вносит усложнения в устройство. Нужно отметить, что рисунок левых сторон участков графа Стокхэема идентичен в той же части алгоритму Кули-Тьюки (с децимацией по времени), поэтому если применить для регис1гр.рвого БПФ алгоритм с полностью постоянной структурой участка его графа, то устройство неизбежно окажется проще, чем известное. Таким алгоритмом является алгоритм Синглетона, представлякедий собой полную противоположность алгоритму Кули-Тьюкн. Если структура участков графа Кули-Тьюки абсолютна непостоянна, и поэтому лучшей реализацией алгоритма является процессор с ОЗУ произвольной выборки, то для абсолютно постоянного графа Сингле- тона лучшей реализацией является . регистровый вариант. Алгоритмы Стокхэма-Санди есть нечто среднее между указанными двумя, а поэтому принципиально не могут дать предельно простой структуры устройства. - Цель изобретения - упрощение устройства. Указанная цель достигается тем, что в устройстве, содержащем четыре регистра сдвига, арифметический блок, формирователь тригонометрических коэффициентов, итерационный регистр, счетчик, узел тактирования, состоящий из четырех элементов И и четырех элементов ИЛИ, причем первые входы элементов И объединены и являются первым тактовым входом устройства, тактовый вход счетчика является вторым тактовым входом устройства, выход счетчика соединен со входом итерационного регистра, первый выход которого подключен ко входу формирователя тригонометрических коэффициентов, выход которого соеди11ен со входом задания коэффициентов арифметического блока,.первый и второй выходы которого соединены со входами соответственно первых п/2 и последних п/2 разрядов четырех регистров сдвига, выходы первого и третьего регистра сдвига объ-. единены, подключены к первому входу ари етического блока и являются первым выходом устройства, выходы второго и четве1 того регистра сдвига объединены, подключены ко второму входу ари 1 1етического блока и являются вторым выходом устройства, тактовые входы регистров сдвига соединены с выходами соответствующих элементов ИЛИ узла тактирования, причем тактовый вход формирователя тригонометрических коэффициентов является третим тактовым входом устройства, а второй выход итерационного регистра является выходом конца итерации итерационного регистра, прямой и инверсный выходы младаиего разряда счетчика подключены ко вторЕлм входам соответственно первого и второго элементов И узла тактирования, а прямой и инверсный выходы стараего разряда счетчика подключены ко вторым входам соответственно третьего и четвертого элементов И узла тактирования, выход. первого элемента И подключен к первым входам второго и четвертого элементов ИЛИ, выход второго элемента И подключен к первьм входам первого и третьего элементов ИЛИ, выход третьего элемента И подключен ко вторым входам третьего и четвертого элементов ИЛИ и управляющим входам первого и второго регистров сдвига, |а выход четвертого элемента И соединен со вторыми входами первого и второго элементов ИЛИ и управляющими входами третьего и четвертого регистров сдвигу, В предлагаемом устройстве значительно меньше функциональных элементов,чем в известном. Но проще оно прежде всего потому, что отпадает необходимость в адресном блоке, который в известном устройстве выполнял специальную функцию формирование массива чисел для пред стояцей итерации с учетом номера итерации и количества групп чисел в массиве. Наличие такой Функции в известном устройстве является следствием несовершенства графа Стокхэм В связи с тем, что в однородном граф Синглетона каждая пара чисел явшяется группой, и количество групп по стоянно для любой итерации, то така функция ceiMa по себе упраздняется в предлагаемом устройстве. Более того в связи с тем, что все разрядные вы ходы счетчика со второго по предпос ледний не используются, счетчик может быть заменен обычным счетчиковйм делителем с выходными импульсами в форме меандров и коэффициентом деления N. Это технологичней, так как резко сокращается количество вы водов в кристалле БИС. На фиг.1 приведена схема устройства на фиг.2 - пример алгоритма Синглетона. Устройство содержит п-разрядные регистры 1,2,3 и 4 сдвига (), выхода 5 и 6.регистров и соответственно первый и второй .входы арифметического блойа 7, арифметический блок 7, выходы 8 и 9 арифметического блока и соответственно Bxojoa записи первых (шина В) (шина 9 разрядов регистров, тактовые входы 10,11,12 и 13 регистров и соответст венно выходы узла 14 тактирования, узел 14 тактирования, формирователь тригонометрических коэффициентов, выход 16 формирователя 15 и соответ ственно третий вход блока 7, итерационный регистр 17, тактовый вход 18 итерационного регистра 17 и соот ветственно выход сигнала смены сос тояния счетчика 19, счетчик 19 с количеством разрядов , выход 20 итерационного регистра и соответ ственно шина окончания цикла НПФ, управляющие входы 21 и 22 регистров выходы 23 я 24 старшего разряда счетчика (прямой и инверсный); выходш 25 и 26 младшего разряда счет ЧШса (прямой и инверсный) элементы 27,28,29 и 30 И узла тактирования, элементы 31,32,33 и 34 ИЛИ узла так тирования. На фиг.2 показан пример алгоритма Синглетона для массива чисел объ емом . Здесь входной массив чисе представляется в двоично-инверсном виде, причем в регистре 1, куда за писывается первая половина массива сосредотачиваются все четные отсчеты, а в регистре 2, куда подается вторая половина массива - все нечетные. Эти полумассивы формируются во входном устройстве процессора (не показано} и вводятся в устройство одновременно с выводом из негр результата Обработки предыдущего массива. Номера итераций на графе обозначены вверху римскими цифрами. KoHTypttue (толстые) линии обозначают умножение соответствующего числа на единицу, а тонкие линии умножение числа на коэффициент г , где W exp -32ir/N) , ,т.е. целой части, чнслв, в свою очередь, АК порядковЁ1й номер числа в массиве, начиная от нулевого, совпгшакмций с количеством тактовых импульсов, прошедших от начала 1-ой итерации i i - номер итерации, для которой формируется тригонометрический коэффициент. Устройство работает следующим образом. В исходном состоянии счетчик 19 сброшен в Of в первый разряд обнуленного перед этим итерационного регистра 17 записана , а в регистры 1 и 2 занесен исходный числовой массив. Единичный потенциал щины 24 дает разршйение для непрерывного тактирования регистров 1 и 2 (тактовые импульсы через элемент 30 И и элементы 31 и 32 ИЛИ проходят на тактовые входы 10 и 11) и разрешение записи в регистры 3 и 4 (единичный потенциал приходит на управляющнй вход 22 регистров 3 и 4). В то же время нулевой потенциал шины 22 запрещает по управляющему входу 21 режим записи в регистры 1 и 2 и составляет возможность тактирования регистров 3 и 4 в зависимости от состояния младшего разряда (шины 25 и 26) счетчика 19. В итоге регистры 1 и 2 тактируются непрерывно, выталкивая в блок 7 пары операндов до полного своего опустсяиения. Регистр 3 и 4 тактируются выборочно, работая лишь.на запись, так как перед началом итерации они были пустыми. Запись в регистр происходит лишь при .наличии потенциала на. его управляющем входе и импульса на тактовом входе. Время итерации определяется промежутком между соредними сменами срстояния старшего разряда счетчика 19: ноля на единицу , либо единицы на ноль. Кс1ждая такая смена сопровождается выделением на шину 18 импульса, который перетгшкивает единичный сигнал регистра 17 в его следующий разряд. ОписанньЦ) расклад потенциалов соответствует нулевому состоянию старшего разряда счетчика 19. При его единичном состоянии потенциальная

картина устройства меняется на противоположную. Пара регистров 1 и 2 и пара, 3 и 4 меняются ролями. Каждая итерация продолжается N/2 тактов. На тактовые входы регистровой пары, находящейся в режиме выдачи, приходитза итерацию N/2 импульсов, а на входы регистров занесения - п/2 импульсов каждому. Но так как записывается ср.азу по 2 числа, то к моменту окончания-итерации регистры занесения оказываются полностью заполненным. При этом регистры выдающей пары работают одновременно, а регистры принимающей пары работают по очереди, сменяясь с каждым тактом. Например, первым (от исходного соетояния) тактовым импульсом по переднему фронту в арифметический блок 7 выталкивается первая пара операндов для базовой операции, выполняемой в течение времени импульса. Результаты базовой операции (по шин-ам 8 и 9) заносятся в регистр 3 по заднему фронту этого импульса, так как он, будучи пропущенным через элемент 28 И, приходит на тактовый вход 12, Одновременно по заднему фронту происходит переключение младшего разряда счетчика 19 в единицу, в результате чего на шине 25 появляется потенциал , а на шине 26 О, и. второй импульс приходит уже на тактовый вход 13 регистра 4, куда записывается очередная пара результатов. При этом регистр 3 не изменяет состояния. Третий импульс вновь приходит на тактовый вход 12, передвигает прежний результат в соседние разряды регистра 3 по направлению к выходу, а на их месте з.аписывает новую пару и т.д.

Формирователь 15 тригонометрических коэффициентов выдает н.а шину 16 поток коэффициентов с учетом количества тактовых импульсов, поступающих на его вход, и с учетом номера итерации, задаваемого итерационным регистром 17. Об окончании цикла БПФ свидетельствует сигнал, подаваемый регистром 17 на шину 20.

К этому моменту формируется массив спектральных компонентов в регистрах 3 .и 4, если число итерации четное, или же - в регистрах 1 и 2, если - нечетное. Спектральные компоненты располагаются в порядке нарас ания аргумента, начиная с меньшего, причем в верхнем регистре находятся все четные компоненты, а в нижнем - все нечетные, которые и выводятся из устройства парами за N/2 тактов одновременно с нанесением в регистрынового исходного маесива чисел.

формула изобретения

Устройство для вычисления коэффициентов Фурье, содержащее четыре регистра сдвига, арифметический блок

формирователь тригонометрических коэффициентов, итерационный регистр, счетчик, узел тактирования, состоящий из четырех элементов И и четыре элементов ИЛИ, причем первые входы элементов И объединены и являются первым тактовым входом устройства, тактовый вход счетчика является вторым тактовым входом устройства, выход счетчика соединен со входом ите рационного регистра., первый выход которого подключен ко входу формирователя тригонометрических коэффициентов, выход которого соединен со входом задания коэффициентов ариметического блока, первый и второй выходы которо.го соединены со входами соответственно первых п/2 и последних п/2 разрядов четырех регистров сдвига, выходы первого и третьего регистра сдвига объединены, подключены к первому входу арифметического блока и являются первым выходом устройства, выходы второго и четвертого регистра сдвига объединены, подключены ко второму входу арифметического блока и являются вторым выходом устройства, тактовые входы регистров сдвига соединены с выходами соответствующих элементов ИЛИ узла тактирования, причем тактовый вход формирователя тригонометрических коэффициентов является третьим тактовым входом устройства, а второй выход итерационного регистjja, является выходом конца итерации итерационного регистра, о т л и ч а ю щ е е с я тем, что с целью упрощения устройства, прямой и инверсный выходы младшего разряда счетчика подключены ко вторым входам соответственно первого и второго элементов И узла тактирования, а прямой и инверсный выходы старшего разряда счетчика подключены ко вторым входам соответственно третьего и четвертого элементов И узла тактирования, выход первого элемента И подключен к первым входам второго и четвертого элемента ИЛИ, выход второго элемента И подключен к Первым входам первого и третьего элементов ИЛИ, выход третьего элемента И подключен ко вторым входам третьего и четвертого элементов ИЛИ и управляющим входам первого и второго регистров сдвига, а выход четвертого элемента И соединен со вторыми входами первого и второго элементов ИЛИ и управляющими входами третьего и четвертого регистров сдвига.

Источники информации, принятые во внимание при экспертизе

1.Патент США № 3816729, кл. 235-152-, 1974.

2.Авторское свидетельство СССР по заявке № 2516246,кл.С 06 F 15/37 28.02.78 (прототип).

t(

ff