Устройство для вычисления коэф-фициентов фурье

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистическик Республик(22) Заявлено 280379 (1) 2743465/18-24 (51)М, Кл. с присоединением заявки Ио С Об Г 15/332 Государственный комитет СССР по делам изобретений н открытий(72) Автор изобретения В,Д.Гусев Специальное конструкторское бюро "Виброприбор"производственного объединения "Виброприбрр"(54) УСТРОЙСТВО ДЛЯ ВИЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ФУРЬЕИзобретение относится к вычислительной технике для измерения спектров случайных функций и может бытьиспользовано при решении задач технической диагностики,Известны специализированные процедуры, выполняющие быстрое преобразование Фурье (БПФ) и содержащие,с целью ускорения анализа, регистрысдвига вместо обычных ОЗУ с произвольной выборкой 1).Однако данные процессоры сложны игромоздки. Их громоздкость определяется многосекционностью и обилием коммутаций, которые, в свою очередь, вызваны использованием алгоритма Кули-Тычки - самого неудобногодля регистрового исполнения процессора,Наиболее близким по техническомурешению к предлагаемому являетсяустройство для вычисления коэффициентов Фурье, содержащее арифметический.блок, управляющий вход которого соединен с выходом генератора тригонометрических функций, блок управления, И-разрядные регистры сдвига,триггер, элементы И записи, элементНЕ и узел тактирования, выполненныйна элементах И и ИЛИ, причем первые ЗО входы элементов И узла тактированиясоединены с шиной тактовых импульсов,второй вход первого элемента И узлатактирования - с единичным выходомтриггера, с первыми входами первого,второго, третьего и четвертого элементов И записи, второй вход второго элемента И узла тактирования соединен со входом элемента НЕ, с первым выходом блока управления, совторыми входами первого и второгоэлементов И записи и с первыми входами пятого и шестого элементов Изаписи, второй вход третьего элемента И узла тактированиясоединенс выходом элемента НЕ, с первыми входами седьмого и восьмого элементовИ записи, вторыми входами третьегои четвертого элементов И записи, второй вход четвертого элемента И узлатактирования соединен с нулевым выходом триггера, со вторыми входамипятого, шестого, седьмого .и восьмого элементов И записи, выходы элементов И узла тактирования соединены с первыми входами соответствующих элементов ИЛИ узла тактирования,вторые входы первого, второго, третьего и четвертого элементов ИЛИузла тактирования соединены соответ 813447ственно с выходами второго, четвер-.того, первого и третьего элементовИ узла тактирования, выходы элементов ИЛИ узла тактирования соединеныс тактовыми входами соответствующихрегистров сдвига, выходы которыхсоединены со входами арифметического блока, первый выход которого соединен с третьими входами шестого,второго, .восьмого и четвертого элементов И записи, второй выход арифМРгического блока соединен с третьими входами пятого, первого, седьмогои четвертого элементов И записи,выходы пятого, первого, седьмого н третьего элементов И записи воединены .с информационными входами первых разрядов соответствующих регистровсдвига, выходы шестого, второго,восьмого и четвертого элементовИ записи соединены с информационными входами И/2+1 разрядов соот-.ветствующих регистров сдвига, счетный вход триггера соединен со вторым выходом блока управления, третья группа выходов которого соединена с управляющими входами генератора тригонометрических функций.В устройстве заложен алгоритм Стокхэма-Санди, что позволило: резко сократить схему и выполнить ее односекционной. Это стало возможным благодаря полупостоянству структуры графа Стокхэма, в каждом участке которого, характеризующем соответствующую итерацию, операнды пар результатов базовьпс операций располагаются с расстоянием в пол-массива друг от друга: И этот порядок не меняется от итерации к итерации (2).Однако такое постоянство свойст- венно только правым (выходным) сторонам участков графа, описывающим режим занесения результатов в память, в то время как рисунок левой стороны от участка к участку меняется,т.е. меняется порядок выбора исходных операндов для базовых операций, и его нужно при смене итераций каждый раз организовывать заново. А это естественно, вносит усложненияв устройство,Нужно отметить, что рисунок,ле. вых сторон участков графа Стокхэема идентичен в той же части алгорйтму Кули-Тычки (с децимацией по времени), поэтому если применить для регисзгрового БПФ алгоритм с полностью. постоянной структурой участка его графа, то устройство неизбежно окажется проще, чем известное. Таким алгоритмом является алгоритм Синглетона, представляющий собой полную противоположность алгоритму Кули-Тычки. Если структура участков графа Кули-Тычки абсолютна непостоянна, и поэтому лучшей реализацией алгоритма является процессор с ОЗУ произвольной выборки, то для 5 0 35 26 25 30 35 40 50 60 65 абсолютно постоянного графа Синглетона лучшей реализацией являетсярегистровый вариант. Алгоритмы Стокхэма-Санди есть нечто среднее междууказанными двумя, а поэтому принципиально не могут дать предельно простой структуры устройства.Цель изобретения - упрощениеустройства,Указанная цель достигается тем,что в устройстве, содержащем четыререгистра сдвига, арифметический блок,формирователь тригонометрическихкоэффициентов, Итерационный регистр,счетчик, узел тактирования, состоящий из четырех элементов И и четы-.рех элементов ИЛИ, причем первыевходы элементов И объединены и являются первым тактовым входом устройства, тактовый вход счетчика является вторым тактовым входом устройства, выход счетчика соединен совходом итерационного регистра, первый выход которого подключен ковходу Формирователя тригонометрических коэффициентов, выход которогосоединен со входом задания коэффициентов арифметического блока,.первыйи второй выходы которого соединенысо входамИ соответственно первыхи/2 и последних и/2 разрядов четырех регистров сдвига, выходы первого и третьего регистра сдвига объ-,единены, подключены к первому входуарифметического блока и являютсяпервым выходом устройства, выходывторого и четвертого регистра сдвига объединены, подключены ко второму входу арифметического блока иявляются вторым выходом устройства,тактовые входы регистров сдвигасоединены с выходами соответствующих элементов ИЛИ узла тактирования,причем тактовый вход формирователятригонометрических коэффициентовявляется третим тактовым входомустройства, а второй выход итерационного регистра является выходомконца итерации итерационного регистра, прямой и инверсный выходымладаего разряда счетчика подключены ко вторым входам соответственнопервого и второго элементов И узлатактирования, а прямой и инверсныйвыходы старшего разряда счетчикаподключены ко вторым входам соответственно третьего и четвертого элементов И узла тактирования, выход,первого элемента И подключен к первым входам второго и четвертого элементов ИЛИ, выход второго элементаИ подключен к первым входам первого и третьего элементов ИЛИ, выходтретьего элемента И подключен ковторым входам третьего и четвертогоэлементов ИЛИ и управляющим входампервого и второго регистров сдвига,а выход четвертого элемента И соединен со вторыми входами первого ивторого элементов ИЛИ и управляющими входами третьего и четвертогорегистров сдвига,В предлагаемом устройстве значительно меньше функциональных эле-ментов,чем в известном. Но прощеоно прежде всего потому, что отпадает необходимость в адресном блоке, который в известном устройстве выполнял специальную функцию -Формирование массива чисел для предстоящей итерации с учетом номераитерации и количества групп чиселв массиве, Наличие такой функции визвестном устройстве является следствием несовершенства графа Стокхэма.В связи с тем, что в однородном графеСинглетона каждая пара чисел является группой, и количество груди постоянно для любой итерации, то таКаяфункция сама по себе упраздняется впредлагаемом устройстве. Более того,в связи с тем, что все разрядные выходы счетчика со второго по предпоследний не используются, счетчик может быть заменен обычным счетчиковым делителем с выходными импульсами в форме меандров и коэффициентомделения Н, Это технологичней, таккак резко сокращается количество выводов в кристалле БИС.На Фиг,1 приведена схема устройства; на Фиг,2 - пример алгоритмаСйнглетрна.Устройство содержит.п-разрядныерегистры 1,2,3 и 4 сдвига (п=п/2),выходы. 5 и б,регистров и соответственно первый и второй .входы арифметического блока 7, арифметическийблок 7, выходы 8 и 9 арифметического блока и соответственно входы записи первых (шнна 8) и +1 (шина 9)разрядов регистров, тактовые входы10,11,12 и 13 регистров и соответственно выходы узла 14 тактирования,узел 14 тактирования, формировательтригонометрических коэффициентов,выход 16 формирователя 15 и соответственно третий вход блока 7, итерационный регистр 17, тактовый вход .18 итерационного регистра 17 и соответственно выход сигнала смены состояния счетчика 19, счетчик 19 сколичеством разрядов 1 одБ, выход20 итерационного регистра и соответственно шина окончания цикла БПФ,управляющие входы 21 и 22 регистров,выходы 23 и 24 старшего разрядасчетчика (прямой и инверсный); выходы 25 и 26 младшего разряда счетЧИса (прямой и инверсный) элементы27,28,29 и 30 И узла тактированияэлементы 31,32,33 и 34 ИЛИ узла тактирования.На фиг.2 показан пример алгоритма Синглетона для массива чисел объемом И=8, Здесь входной массив чиселпредставляется в двоично-инверсномвиде, причем в регистре 1, куда за.б 5 ффпереталкивает единичный сигнал регистра 17 в его следующий разряд. Описанный расклад потенциалов .соответствует нулевому состоянию старшего разряда счетчика 19, При его единичном состоянии потенциальная писывается первая половина массива, сосредотачиваются все четные отсчеты, а в регистре 2, куда подается вторая половина массива - все нечетные, Эти полумассивы формируются во входном устройстве процессора (не показано) и вводятся в устройство одновременно с выводом из него результата обработки предйдущего массива. Номера итераций на графе 1 обозначены вверху римскими цифрами, Контурные (толстые) линии обозначают умножение соответствующего числа на единицу а тонкие линии -фмаумножение числа на коэффициент И ф, где Ю=ехр(-.ЗГ/ЩЬк Ау/21,т.е.целой части числами в свою очередь Ак - порядковый номер числа в массиве, начиная от нулевого, совпадающий с количеством тактовых импуль" сов, прошедших от начала 1-ой итерации, 1 - номер итерации, для которой Формируется тригонометрический коэффициент.Устройство работает следующимобразом.2 В исходном состоянии счетчик 19фсброшенф в фОфф, в первый разряд обнуленного перед этим итерационного регистра 17 записана ф 1 ф, а в регистры 1 и 2 занесен исходный 3 числовой массив. Единичный потенциал шины 24 дает разрешение для непрерывного тактирования регистров 1 и 2 (тактовые импульсы через элемент 30 И и элементы 31 и 32 ИЛИ проходят на тактовые входы 10 и 11) и разрешение записи в регистры 3 и 4 (единичный потенциал приходит науправляющий вход 22 регистров 3 и 4), В то же время нулевой потенциал шины 22 запрещает по управляющему входу 4 21 режим записи в регистры 1 и 2 исоставляет возможность тактирования регистров 3 и 4 в зависимости от состояния младшего разряда (шины 25 и 26) счетчика 19. В итоге регист ры 1 и 2 тактируются непрерывно,выталкиваяфф в блок 7 пары операндов до полного своего опустошения.регистры 3 и 4 тактируются выборочно, работая лишь на запись, так как пе О ред началом итерации они были пустыми. Запись в регистр происходит лишь при,наличии потенциала на его управляющем входе и импульса на тактовом входе. Время итерации определяется промежутком между соседними сменами состояния старшего разряда счетчика 19: фноляеф на ффединицу 1, либо единицыф 1 на фноль. Каждая такая смена сопровождается выделением на шину 18 импульса, который60б 5 картина устройства меняется на противоположную, Пара регистров 1 и 2й пара, 3 и 4 меняютсяролями, Каждаяитерация продолжается И/2 тактов,На тактовые входы регистровой пары,находящейся в режиме выдачи, приходитза итерацию И/2 импульсов, а навходы регистров занесения - и/2 импульсов каждому. Но так как записывается сразу по 2 числа, то к моменту окончания итерации регистры занесения оказываются полностью заполненными. При этом регистры выдающейпары работают одновременно, а регистры принимающей пары работают по оче реди, сменяясь с каждым тактом, Например, первым (от исходного состояния) тактовым импульсом по переднему фронту в арифметический блок 7 выталкивается первая пара операн дов для базовой операции, выполняемой в течение времени импульса, Результаты базовой операции (по шинам 8 и 9) заносятся в регистр 3 по заднему фронту этого импульса, так как он, будучи пропущенным через элемент 28 И, приходит на тактовый вход 12, Одновременно по заднему фронтупроисходит переключение младшегоразряда счетчика 19 в единицу,в результате чего на шине 25 появляется потенциал 1, а на шине 260, и. второй импульс приходит ужена тактовый вход 13 регистра 4, куда записывается очередная пара результатов. При этом регистр 3 не изменяет состояния. Третий импульсвновь приходит на тактовый вход 12,передвигает прежний результат в соседние разряды регистра 3 по направлению к выходу, а на их месте записывает новую пару и т.д.Формирователь 15 тригонометрических коэффициентов выдает на шину 16поток коэффициентов И"/2 с учетомколичества тактовых импульсов, поступающих на его вход, и с учетомномера итерации, задаваемого итерационным регистром 17. Об окончаниицикла БПФ свидетельствует сигнал,подаваемый регистром 17 на шину 20.К этомумоменту формируется массив спектральных компонентов в регистрах 3 .и 4, если число итерациичетное, или же - в регистрах 1 и 2,если - нечетное, Спектральные компоненты располагаются в порядке нарастания аргумента, начиная с меньшего, причем в верхнем регистре находятся все четные компоненты, а внижнем - все нечетные, которые ивыводятся из устройства парами заБ/2 тактов одновременно с нанесением в регистрынового исходного массива чисел,Формула изобретенияУстройство для вычисления коэффициентов Фурье, содержащее четыре регистра сдвига, арифметический блок,Формирователь тригонометрических коэффициентов, итерационный регистр,счетчик, узел тактирования, состоящий из четырех элементов И и четырехэлементов ИЛИ, причем первые входыэлементов И объединены и являютсяпервым тактовым входом устройства,тактовый вход счетчика является вторым тактовым входом устройства, выход счетчика соединен со входом итерационного регистра., первый выходкоторого подключен ко входу формирователя тригонометрических коэффициентов, выход которого соединенсо входом задания коэффициентов арифметического блока, первый и второйвыходы которого соединены со вхоцами соответственно первых п/2 и последних и/2 разрядов четырех регистров сдвига, выходы первого и третьего регистра сдвига объединены, под- Щ ключены к первому входу арифметического блока и являются первым выходом устройства, выходы второгои четвертого регистра сдвига объединены, подключены ко второму входуарифметического блока и являютсявторым выходом устройства, тактовыевходы регистров сдвига соединены свыходами соответствующих элементовИЛИ узла тактирования, причем тактовый вход формирователя тригонометрических коэффициентов являетсятретьим тактовым входом устройства,а второй выход итерационного регистра, является выходом конца итерацииитерационного регистра, о т л и З 5 ч а ю щ е е с я тем, что с цельюупрощения устройства, прямой иинверсный выходы младшего разрядасчетчика подключены ко вторым входам соответственно первого и второ О го элементов И узла тактирования,а прямой и инверсный выходы старшего разряда счетчика подключены ковторым входам соответственно третьего и четвертого элементов И узла 45 тактирования, выход первого элемента И подключен к первым входам второго и четвертого элемента ИЛИ, выход второго элемента И подключен кпервым входам первого и третьегоэлементов ИЛИ, выход третьего элемента И подключен ко вторым входамтретьего и четвертого элементов ИЛИи управляющим входам первого и второго регистров сдвига, а выход четвертого элемента И соединен со вто рыми входами первого и второго элементов ИЛИ и управляющими входамитретьего и четвертого регистровсдвига. Источники информации,принятые во внимание при экспертизе 1. Патент США Р 3816729,кл. 235-152; 1974. 2, Авторское свидетельство СССР по заявке Р 2516246,кл.6 06 Р 15/37,28,02,78 (прототип),813447 Вараиоозич стаэителзред И.т А,Наурск Редак Г. Рею аз 775/63 Тираа 745 ВИНИЮ Государствен по делам мэобрет 113035 Мосиаау 3 35, филиал ППП фП Подпнсного комитета СССРМй и откытиущская наб., д,4/5 город, ул.Проектная, 4