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

библиотекаС И оп и АиИЗОБРЕТЕН ИЯ Союз СоветскихСоцывлыстыческикреспублик 11 699525 К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(5)М. Кл. нрисоединениеве заявки РЙ23)Приоритетоеудврстееиицй оитет СССР ио делом изооретеии и отритойпубликовано 25.11 79. Бюллетень Ле 43 Дата опубликования описания 28,11.79. И. Кацма й. Гусев, В, Н о ециальное конструкторское бюро "Виброприбо 71) Заявитель) УСТРОЙСТВО ДЛЯ ВЫЧ КОЭФФИЦИЕНТОВ ФУРЛЕНИЯ му соотоме то- ацию Изобретение касается вычислительн техники, предназначается для измерения спектров случайных функций и может быть использовано при решении задач технической диагностики.Известны специализированные процессоры, осуществляющие быстрое преобразование Фурье ( БПФ) в реальном времени Как правило, эти процессоры содержат оперативные запоминающие устройства (ОЗУ) в виде автономных блоков.Эти ОЗУ содержат матрицу памяти, системы шин занесения, шин считывания, адресную систему с признаком операции, линейки усилителей считывания ( в случае с МОЗУ) и т. д, 11.Наиболее близким по технической сущности к предложенному является устройство для вычисления коэффициентов фурье, содержащее арифметический блок, управляющий вход которого соединен с выходом генератора тригонометрических функ ций, блок управления, тт - разрядные регистры сдвига, Кроме того, известное устройство содержит 11 регистров разной длины для обработки массива 2 выборок,ттДлина каждого последующего регистра меньше прецыдущего в 2 раза, что опре деляет нужное двоичное расстояние между 5парами чисел, выбираемыми для обработки на текущей итерации: в устройстве реализован алгоритм Кули-Тычки. Сов купность этих те, регистров образует общий регистр сдвига, в котором послвдо 10вательные выборки сигналов располагаются в двоичной последовательности от 0 до 2 - 1. Каждый из т 1 регистровЪвходит в состав соответствующего модуля. Общее число модулей равно, таким образом, т 1. Схема каждого модуля содержит, помимо регистра, арифметический блок, 8 линий задержки, 4 из которых входят в состав арифметического блока, а остальные 4 установлены на входе и выходе этого блока, причем бьем линий задержки равен объе етствующего регистра сдвига. К о, схема модуля содержит комму25 3 69 9:-,в 8 точках, управляемую устройством1управления (с функциями индексного устройства), В пределах времени обработкиодного массива данных одновременновключенным бывает только один арифме-,тический блок. Г 1 ри и =9 для построенияпроцессора потребуется 9 арифметическихблоков, 72 линии задержки, общим объемом 2 (т. е. 512) и коммутация ви72 точках. Необходимо подчеркнуть, что 10если выполнять задержку на триггерах,то суммарный объем памяти процессорасоставит 2 М, где Я- объем исходногомассива чисел, С увеличением Ъ (а реально= 10 - ; 13) приведенные количества будут возрастать. Помимо этого,в рассматриваемом процессоре применено постоянное запоминающее устройствосинус-косинусных коэффициентов, работа которого определяется индексным 20устройством, вырабатывающим соответствующие адреса 21,Однако данный быстродействующийпроцессор является громоздким и сложным,Цель изобретения - упрощение устройства,Для этого устройство, содержащееарифметический блок, управляющий входкоторого соединен с выходом генератора30тригонометрических функций, блок управления,п-разрядные регистры сдвига дополнительно содержит триггер, элементыИ записи, элемент НЕ и узел тактирования, выполненный на элементах И, ИЛИ,35причем первые входы элементов И узлатактирования сЬединены с шиной тактовыхимпульсов, второй вход первого элемента И узла тактирования - с единичным40выходом триггера, с первыми входамипервого, второго, третьего и четвертогоэлементов И записи, второй вход второго элемента И узла тактирования соединен со входом элемента НЕ, с первым45входом блока управления, со вторымивходами первого и второго элементов Изаписи и с первыми входами пятого ишестого элементов И записи, второй входтретьего элемента И узла тактирования50соединен с выходом элемента НЕ, с первыми входами седьмого и восьмого элементов И записи, вторыми входами третьего и четвертого элементов И записи,второй Вход четвертого элемента И узла тактирования соединен с нулевым выходом триггера со вторыми входами пятого, шестого, седьмого и восьмого элементов И записи, выходы элементов И 25 4 узла тактирования соединены с первымивходами соответствующих элементов ИЛИ узла тактирования, вторые входы первого, второго, третьего и четвер ого элементов И узла тактирования соединены соответственно с выходами второго, четвертого, первого и.третьего элементов И узла тактирования, выходы элементов ИЛИ узла тактирования соединены с тактовыми входами соответствующих регистров сдвига, выходы которых соединены со входами арифметического блока, первый выход которого соединен с третьими входами шестого, второго, восьмого и четвертого элементов И записи, второй выход арифметического блока соединен с третьими входами пятого, первого, седьмого и четвертого элементов И записи, выходы пятого, первого, седьмого и третьего элементов И записи соединены с информационными входами первых разрядов соответствующих регистров сдвига выходы шестого, второго, восьмого и четвертого элементов И записи соединены с информационными входами ( п/2+1) разрядов соответствующих регистров сдвига, счетный вход триггера соединен со вторым выходом блока управления, третьяогруппа выходов которого соединена с управляющими входами генератора тригонометрических функций.На фиг. 1 изображена структурная схема устройства; на фиг. 2 - граф для массива из 1 6 чисел алгоритма Стокхэма-Санди.Устройство содержит регистры сдвигачисел 1 - : 4, арифметический блок 5,элементы И записи 6 - : 13, триггер 14,элемент НЕ 15, узел тактирования 16,элементы И 17 -, 20, элементы ИЛИ21 - 24, блок управления 25, счетчик26 объема - , регистр 27, элементйИЛИ 28, элементы И 29 - ; 31, шинусинхронизации 32, шину 33 сигнала окончания БПФ цикла, итерационные выходы34 - 36 блока управления, генератор37 тригонометрических функций, входы38, 39 записи исходной информации врегистры, шину ТИ тактового импульса,шины выхода результата "Вых",Предлагаемый процессор реализует алгоритмы Стокхэма-Санди. На фиг. 2 толстыми линиями обозначено умножение соответствующих чисел (при вершинах, откуда линии исходят) на единицу, а тонкими линиями - умножение соответствую99525 6 5 6 ших чисел на тригонометрический коэффициент МК-О 3 2 Ягде 91 =СхрЯ - объем обрабатываемого массива чисел (т. е. количествоэтих чисел);Р - номер итерации;), - номер группы тонких линий,начиная от начала массива.Так, например, на 1-сй итерации(номера итераций проставлены сверху римскими цифрами) имеется только одна группа тонких линий (это числа в массиве с 9-го по 1 б-е), для которой трио гонометрический множитель равен %, На второй итерации первая группа (т. е. числа с 5-го по 8-е) умножается на Я , вторая группа чисел (с 13-го по 1 6-е) умножается на %+, на третьей итерации таких групп уже 4 ( 3 - 4, 7 - 8, 11 - 12, 15 - 16) и для нихосоответственно имеем: %, 7, щ, ь, на четвертой итерации (.на последней) каждое число массива является группой, и здесь показатель степени 1 и тригонометрического множителя меняется от О до 7. Естественно, что рассмотрен порядок изменения тригонометрических коэффициентов применительно к базовой операции алгоритма: Таким образом, в отличие от алгоритма Кули-Тычки, данный алгоритм (Стекхэма-Санди) характеризуется естественным нарастанием показателя степени при Ю внутри каждой итерации при смене групп чисел возрастая каждый раз от О на одну и ту же величину, Эта особенность и позволяет применить в устройстве генератор, работающий по алгоритму (1), Здесь а( есть тя постоянная величина, на которую возрастает показатель степени при % и которая задается в генераторе 37 соответствующей шиной (из числа 34 А 36), на которой существует импульс, определенный текущей итерацией, Замечательной особенностью алгоритма является и то, что результаты базовой операции ( т. е А 1 иВ) в массиве, формируемом для ф итерации, всегда отстоят друг от друга на )- чисел (т, е. на полмассива), Это2 5 1 О 15 20 25 30 35 40 4550 и позволяет резко сократить число коммутаций в устройстве, Числа же А и В для базовой операции берутся всегда из двух соседних групп чисел: число А берется иэ группы чисел, умножаемых на 1, а число Вберется из следующей за ней группы чисел, умножаемых на )111, Если формировать массив для оче редной итерации таким образом, чтобы числя А + и Взаписывались в разные регистры; то подавая на эти регистры тактовый импульс, можно сдвигать в арифметический блок нужные пары чисел одновременно.В устройстве содержатся четыре регистра (1 -, 4), в каждый из которых можно записывать - чисел. При этомйкаждый иэ регистров представляет собой два пслурегистра, объемом ."-, включенных последовательно. Выход первого пслурегистра включен на вход второго, причем на этот же вход второго полуре гистра можно подавать числа с выхода соответствующих вентилей записи: 7, 9, 11, 13. В начале БПФ-цикла в регистры 1 и 3 заносится исходный массив чисел по шинам 38 и 39, Регистры 2 и 4 остаются свободными. При этом в регистр 1 заносится первая половина массива (первые. - чисел), а в регистрМ3 - вторая половина массива, так что к началу первой итерации все числа А сосредоточены в регистре 1, а все чисда В - в регистре 3. Одновременно налшину "Вых из регистра 1 (если число итераций четное) или из регистра 2 (ес ли число итераций нечетное) выводится результат предыдущего цикла (как известно 1), информативными при М чисй лах исходных являются только - чисел2 результата), Занесение (выдача) чисел в регистры осуществляется за - - такй2 тов, и эти тактовые импульсы считаюгся счетчиком 26, В момент переполнения счетчика 26 (соответствует окончанию занесения в регистры 1 и 3 исходного массива чисел) на шине 32 синхронизации появляется импульс (переполнения), который записывает в первый разряд регистра 27 единицу и устанавливает в единичное состояние триггер 14, Элементы И 8, 9, 12 и 13 отпираются, элементы И 6, 7, 10 и 11 запираются. Начинается 1-я итерация, которая продолжается - тактов (до появления слеН2дующего импульса переполнения на шине 32). Выход первого разряда регист-. ра 27 подключен к первому входу эле7 1,995 мепта 29 И, ко второму входу которого подключен старший разряд счетчика 26. Так как вес старшего разряда счет гика ) - й, Ь равен - то потенциал старшего разряда счетчика 26 за время наполнения счетчика (до появления следуюгцего импульса переполнения па шине 32) изменится два раза (один раз - нулевой, один раз - единичный), В нулевом состоянии на выходе блока управления су ществует единица, в результате чего " элементы И 8 и 9 остаются открытыми, и через них проходят числа с выходов арифметического блока 5 на запись одновременно в первый и второй полурегистры 5 регистра 2. Это - числа А - резуль 1+1таты базовой операции, Применительно к фиг. 2 это числа с 1-го по 4-е (опи запишутся во второй иолурегистр через вентили 9) и с 9-го по 1 2. (запишутся в 20 первый полурегистр через элемент И 8), При этом на тактовые входы регистра 2 проходят импульсы с выхода элемента 22 ИЛИ, который, в свою очередь, пропускает эти импульсы с выхода элемента 18 И, По окончании нулевого состояния блока управления 25 в регистре 2 записывается непрерывный ряд чисел; 1, 2 3, 4, 9, 10, 11, 12 (применительно к примеру на фиг. 2), который состоит толь-)0 ко из чисел А 1, причем в этом ряду имеются все числа А 1 1 массива для сле-1+1дующей итерации. В единичном состоянии на выходе блока управления существует ноль, который запирает элемент 18 И, а также - элементы И 8, 9, при этом на выходе элемента 15 НЕ появляется единица, которая открывает элемент 19 И, элементы И 12 и 13, в результате числа40 с выхода арифметического блока 5 поступают на запись в регистр 4: числа с 5-го по 8-е записываются во второй полуре, гистр (через элементы И 13), а числа 13 по 16 - в первый полурегистр (через элементы И 12 ). При этом регистр 445 тактируется импульсами с выхода элемента 24 ИЛИ, который, в свою, очередь, пропускает эти импульсы с выхода элемента 1 9 И. По окончании единичного состояния блока управления 25 в регистре 450 записывается непрерывный ряд чисел: 5, 6, 7, 8, 13, 14, 15, 16 (применительно к примеру на фиг, 2), который состоит только из чисел В, причем в этом1+ 1ряду имеются все чйсла Вмассива для1+1следующей итерации.За все время первой итерации регистры 1 и 3 безостановочно,тактируются по цек (8по цлм: элемент 1.7 И - элемент 21ИЛИ и элемент 17 И -:элемент 23 ИЛИсоответственно, в то время как регистры 2 и 1 тактируются лишь тогда, когда в них происходит запись чисел, Поэтому, к моменту окончания первой итерации регистры 1 и 3 оказываются свободными, а регистры 2 и 4 заполняются числами. В момент окончания итерации на шине 32 появляется импульс, который переключает в нулевое состояние триггер 14, в результате чего элементы И 8, 9, 1 2, 13 запираются, а элементы И 6, 7, 10, 11 открываются, элемент 17 И .запирается, а элемент 20 И отпирается, что обуславливает постоянное тактирование регистров 2 и 4 по цепочкам; элемент 20 И - элемент 22 ИЛИ и элемент 20 И - элемент 24 ИЛИ соответственно. Регистр 1 тактируется лишь тогда, когда на выхо де узла 25 (выход элемента 28 ИЛИ) присутствует единица, а регистр 3- когда присутствует ноль. То есть регистры 1, 3 и 2, 4 меняются ролями. Одновременно импульс на,нине 32 передвигает в регистре 27 единичный потенциал во второй разряд, который управляет элементом 30 И по первому входу. Ко второму входу элемента 30 И подключается следующий за старшим разряд счетчика 26 с весом М/8, поэтому за время второй итерации на выходе адресного узла 25 потенциал меняется четыре раза (два раза будет существовать ноль, два раза - единица). Поэтому запись чисел с выхода блока 5 осуществляется в течение 2-х тактов (применительно к фиг. 2); вначале в регистр 1 (числа 1 и 2 записываются во второй полурегистр через элементы И 7, числа 9 и 10, записываются в первый полурегистр через элементы И 6), затем в регистр 3 (числа 3 и 4 записываются во второй полурегистр через элементы И 11, а числа 11 и 12 в первый полу- регистр через элементы И 10), затем запись вновь производится в регистр 1 (записываются числа 5, 6 и 13, 14), после чего - в регистр 3 (записываются числа 7, 8 и 15, 16). Для осуществления базовой операции в продолжении второй итерации в арифметический блок сдвигаются числа соответственно парами: 1 и 5, 2 и 6, 3 и 7, 4 и 8, 9 и 13, 10 и 14, 11 и 15, 12 и 16 (применительно к фиг, 2), Далее, вторая итерация оканчивается, регистры 2 и 4 очищаются, регистры 1 и 3 заполняются чисне меняются. сг 6 Я 3; лами, вырабатывается импульс переполнения на шине 32, т, ггер 14 переходит в единичное состояние, единичный потенциал в регистре 27 переходит в 3 разряд, при этом потенциал на выходе элемента 28 ИЛИ определ,:тся инверсным состоянием разряда счетчика с весом М/16 и все повторяется снова, как описано выше. По окончании всех итераций на шину 33 выходит единичный спг нал с выхода последнего разряда регистра 27. Это и есть сигнал окончания БПф-цикла, При этом результаты БПФ- цикла располагаются либо в регистре 1 (если число итераций четное), либо в ре гистре 2 (если число итераций нечетное) в естественном порядке (свойство алгоритма Стокхзма-Санди), причем другой регистр (либо 2, либо 1) будет обязательно свободным. Поэтому объединение 20 регистров по выходу ничуть не мешает как при БПФ-цикле сдвигу нужных пар чисел в блок 5, так и при считывании конечного массива спектральных составляющих г - ; г на шинуВыход ("Вых,О15Итак, если сравнить три устройства, реализующих БПФ в реальном масштабе времени, и в качестве сравниваемых взять: процессор с ОЗУ, процессор по схеме прототипа и предлагаемое устрой 30 ство, то процессор в прототипе превосходит процессор с ОЗУ по быстродействию, но получается при этом очень сложным и громоздким, насыщенным коммутацией, Предлагаемое же устройство, превосходя в такой же степени процессор с ОЗУ по быстродействию, конструктивно оказывается в несколько раз проще процессора- прототипа, ибо содержит всего один ариф 40 метический блок вместо 9, как в прототипе ( в общем случае - по числу итераций), 8 точек коммутации вместо 72, как в прототипе ( в общем случае зависит от числа итераций). Под точкой ком 45 мутации в предлагаемом устройстве подразумевается элемент И записи (из числа 6 -, 11), Объем же триггерной памяти одинаков у процессора-прототипа и у предлагаемого процессора и равен 2 Й . При этом предлагаемое устройство тем более экономичней процессора-прототипа, чем больше массив обрабатываемых данных, потому что с увеличением массива данных увеличивается число итераций, а значит и количество арифметических блоков и коммутаций в процессоре-прототипе, В предлагаемом же устройстве количества этих блоков (т. е, число арифмети ) 1 Сгческих блоков и число точек коммутации) формула изобретения Устройство для вычисления коэффициентов Фурье, содержащее арифметический блок, управляющий вход которого соединен с выходом генератора тригонометрических функций, блок управления, и-разрядные регистры сдвига, о т л и ч аю щ е е с я тем, что, с целью упрощения устройства, оно содержит триггер, элементы И записи, элемент НЕ и узел тактирования, выполненный на элементах И, ИЛИ, причем первые входы элементов И узла тактирования соединены с шиной тактовых импульсов, второй вход первого элемента И узла тактирования - с единичным выходом триггера, с первыми вхо дами первого, второго, третьего и четвертого элементов И записи, второй вход второго элемента И узла тактирования соединен со входом элемента НЕ, с первым выходом блока управления, со вторыми входами первого и второго элементов И записи и с первыми входами пятого и шестого элементов И записи, второй вход третьего элемента И узла тактирования соединен с выходом элемента НЕ, с первыми входами седьмого и восьмого элементов И записи, вторыми входами третьего и четвертого элементов г 1 записи, второй вход четвертого элемента И узла тактирования соединен с нулевым выходом грггггера, со вторыми входами пятого, шестого, седьмого и восьмогоэлементов И записи, выходы элементов И узла тактирования соединены с первы-ми входами соответствующих элементов ИЛИ узла тактирования, вторые входы первого, второго, третьего и четвертого элементов ИЛИ узла тактирования со единены соответственно с выходами второго, четвертого, первого и третьего элементов И узла тактирования, выходы элементов ИЛИ узла тактирования соединены с тактовыми входами соответствующих регистров сдвига, выходы которых соединены со входами арифметического блока, первый выход которого соединен с третьими входами шестого, второго, восьмого и четвертого элементов И записи, второй выход арифметического блока соединен с третьими входами пятого, первого, седьмого и четвертого элемента И записи, выходы пятого, первого,11 69 седьмого н третьего элементов И запи-си соединены с информационными входами первых разрядов сс 1 ответству 1 ощих регистров сдвига, выходы шестого, второ 1 О, восьмого и четвертого элементов И записи соединены с информационными входами (п/2 + 1) разрядов соответствующих регистров сдвига, счетный вход триггера соединен со вторым выходом блока уп 9 Г 25 О 11 а 11 ления, третья группа выходов которого соединена с управня 1 Ощими входамигенератор 11 тригоцометрических фуцкний,Источники информации,принятые во вьц 1 манне нрн экспертизе1. Г 1 атент С 11 И3803391,кл. 340 - 165, 1974.2. Патент США3816729,кл. 340 - 165, 1975.