Устройство для вычисления коэффициентов фурье Советский патент 1979 года по МПК G06F17/14 

Изобретение касается вычислительной техники, предназначается для измерения спектров случайных функций и может быть использовано при решении задач технической диагностики. Известны специализированные процес соры, осуществляющие быстрое преобразование Фурье (БПФ) в реальном времен Как правило, эти процессоры содержат оперативные запоминающие устройства (ОЗУ) в виде автономных блоков. Эти ОЗУ содержат матрицу памяти, системы шин занесения, шин считывания адресную систему с признаком операции, линейки усилителей считывания ( в случае с МОЗУ) и т. д. l. Наиболее близким по технической сущ ности к предложенному является устройство для вычисления коэффициентов Фурь содержащее арифметический блок, управ- лягощий вход которого соединен с выходом генератора тригонометрических функ ций, блок управления, Т - разрядные регистры сцвига. Кроме TOIX, известное устройство содержит п регистров разной длины для обработки массива 2 выборок, Длина каждого последующего регистра меньше предыдущего в 2 раза, что определяет нужное двоичное расстояние между парами чисел, выбираемыми для обработки на текущей итерации: в устройстве реализован алгоритм Кули-Тьюки. Совокупность этих я. регистров образует общий регистр сдвига, в котором последовательные выборки сигналов располагаются в двоичной последовательности от О до 2 - 1. Каждый из П регистров входит в состав соответствующего модуля. Общее число модулей равно, таким образом, И . Схема каждого модуля содержит, помимо регистра, арифметичес- кий блок, 8 линий задержки, 4 из которых входят в состав арифметического блока, а остальные 4 установлены на входе и выходе этого блока, причем объем линий задержки равен объему соответствующего регистра сдвига. Кроме того, схема модуля содержит коммутацию в S точках, управляемую устройством Упра&пения (с функциями 1шдексного устройства), В пределах времепи обработки одного массива aaiiHbix одновременно включенным бывает только один арифметический блок. При И 9 для построения процессора потребуется 9 арифметически блоков, 72 линии задержки, общим объемом 2 (т. е. 512) и коммутация в 72 точках. Необходимо подчеркнуть, что если выполнять задержку на триггерах, то суммарный объем памяти процессора составит 2N, где М -.объем исходного массива чисел. С увеличением Т1 (а реально Л 10 4 13) приведенные количества будут возрастать. Помимо этого, в рассматриваемом процессоре применено постоянное запоминающее устройство синус-косинусных коэффициентов, работа которого определяется индексным устройством, вырабатывающим соответствующие адреса 2. Однако данный быстродействующий процессор является громоздким и сложным. Цель изобретения - упрощение устрой ства. Для этого устройство, содержащее арифметический блок, управляющий вход которого соединен с выходом генератора тригонометрических функций, блок управления, У1 раарядные регистры сдвига до- полнительно содержит триггер, элементы И записи, элемент НЕ и узел тактирования, выполненный на элементах И, ИЛИ, причем первые -входы элементов И узла тактирования сЬедирюны с шиной тактовы импульсов, второй вход первого элемента И узла тактирования - с единичным выходом триггера, с первыми входами первого, второго, третьего и четвертого элементов И записи, второй вход второго элемента И узла тактирования соединен со входом элемента НЕ, с,первым входом блока управления, со вуорыми входами первого и второго элементов И записи и с первыми входами пятого и шестого элементов И записи, второй вхо третьего элемента И узла тактирования соединен с выходом элемента НЕ, с пер выми входами седьмого и восьмого элементов И записи, вторыми входами трет его и четвертого элементов И записи, второй вход четвертого элемента И узла тактирования соединен с нулевым выходом триггера со вторыми входами пятого, шестого, седьмого и восьмого элементов И записи, выходы элементов И 6 5- 4 уапа Т1зктировання хоодинены с первыми входами соответствующих элементов ИЛИ узла тактирования, вторые входы первого, второго, третьего и четвертого элементов И узла тактирования соединены соответственно с выходами второго,четвертого, первого и.третьего элементов И узла тактирования, выходы элементов ИЛИ узла тактирования соединены с тактовыми входами соответствующих регистров сдвига, выходы которых соединены со входами арифметического блока, первый выход которого соединен с третьими входами шестого, второго, восьмого и четвертого элементов И записи, второй выход арифметического блока соединен с третьими входами пятого, первого, седьмого и четвертого элементов И записи, выходы пятого, первого, седьмого и третьего элементов И записи соединены с информационными входами первых разрядов соответствующих регистров сдвига выходы шестого, второго, восьмого и четвертого элементов И записи соединены с информационными входами (п/2+1) разрядов соответствующих регистров -сдвига, счетный вход триггера соединен со вторым выходом блока управления, третья группа выходов которого соединена с управляющими входами генератора тригонометрических функций. На фиг. 1 изображена структурная схема устройства; на фиг. 2 - граф для массива из 16 чисел алгоритма Стокхэма-Санди. Устройство содержит регистры сдвига чисел i 4, арифметический блок 5, элементы И записи 6 .f 13, триггер 14, элемент НЕ 15, узел тактирования 16, элементы И 17 - 20, элементы ИЛИ 21 -i- 24, блок управления 25, счетчик 26 объема -g- , регистр 27, элемент ИЛИ 28, элементы И 29 т 31, шину синхронизации 32, шину 33 сигнала окончания БПФ цикла, итерационные выходы 34 36 блока управления, генератор 37 тригонометрических функций, входы 38, 39 записи исходной информации в регистры, шину ТИ тактового импульса, шины выхода результата Вых. Предлагаемый- процессор реализует алгоритмы Сгокхэма-Оанди. На фиг. 2 толстыми линиями обозначено умножение соответствующих чисел (при вершинах, откуда линии исходят) на единицу, а тонкими линиями - умножение соответствую- 5 щих чисел на тригонометрический коэфф циент . NU-O Vi j р где vjV-exp 1 / N - объем обр)абатываемого мас сива чисел (т. е. количеств этих чисел); Р - номер итерации; ц - номер группы тонких линий, ,начиная от начала массива. Так, например, на 1-ой итераяии (номера итераций проставлены сверху римскими цифрами) имеется только одна группа тонких линий (это числа в маесиве с 9-го по 16-), для которой три гонометрический множитель равен NW . На второй итерации первая группа (т. е числа с 5-го по 8-е) умножается на yfJ°, вторая группа чисел (с 13-го по 16-е) умножается на W , на третьей итерации таких групп уже 4(3-4, 7 - 8, 11 - 12, 15 - 16) и для них соответственно имеем: V°,i/,Wtw на четвертой итерации (на последней) каждое число массива является группой и здесь показатель степени VYl тригонометрического множителя меняется от О до 7. Естественно, что рассмотрен по- рядок изменения тригонометрических коэффициентов применительно к базовой операции алгоритма: B,--A--B,-W Таким образом, в отличие от алгоритма Кули-Тьюки, данный алгоритм (Стекхэма-Санди) характеризуется есте твенным нарастанием показателя степени при V/ внутри каждой итерации при смене групп чисел, возрастая каждый раз от О на одну и ту же величину. Эта особенность и позволяет применить в устройстве генератор, работающий по алгоритму (3J. Здесь оС есть та постоянная величина, на которую возрастает показатель степени при у и которая задается в генераторе 37 соответствующей шиной (из числа 34 36), на которой существует импульс, определенный текущей итерацией. Замечательной особенностью алгоритма является и то, что результаты базовой операции ( т. е.А. иВ;4.х) в массиве, формируемом для j-t-l итерации, всегда отстоят друг от друга на - чисел (т. е. на полмассива). Это 256 иПозволяет резко сократить число коммутаций в устройстве. Числа же и для базовой операции берутся всегда из двух соседних групп чисел: число берется из группы чисел, умножаемых на 1, а число В берется из следующей за ней Группы чисел, умножаемых на . Если формировать массив оля очередной итерации таким образом, чтобы числа А записывались в разные perncTpbij то подавая на эти ре-; гистры тактовый импульс, можно сдви- гать в арифметический блок нужные пары чисел одновременно. В устройстве содержатся четыре регистра (1 4- 4), в каждый из которых можно записывать - чисел. При этом каждый из регистров представляет собой два полурегистра, объемом - , включенных последовательно. Выход первого полурегистра включен на вход второго, причем на этот же вход второго полуре- гисгра можно подавать числа с выхода соответствующих вентилей записи: 7, 9, 11, 13. В начале БПФ-цикла в регистры 1 и 3 заносится исходный массив чисел по шинам 38 и 39. Регистры 2 и 4 остаются свободными. При этом в регистр 1 заносится первая половяна массива (первыа- чисел), а,в регистр 3 - вторая половина массива, так что к началу первой итерации все числа А сосредоточены в регистре 1, а все чис- да В- - в регистре 3. Одновременно на шину Вых из регистра 1 (если число итераций четное) или из регистра 2 (если число итераций нечетное) выводится результат предыдущего цикла (как известно i, информативными при N числах исходных являются только -g- чисел результата). Занесение (выдача) чисел в регистры осуществляется за - - тактов, и эти тактовые импульсы считаются счетчиком 26, В момент переполн - НИН счетчика 26 (соответствует окончанию занесения в регистры 1 и 3 исходного массива чисел) на шине 32 синхронизации появляется импульс (переполнения) , который записывает в первый разряд регистра 27 единицу и устанавливает в единичное состояние триггер 14. Элементы ИВ, 9, 12 и 13 отпираются, элементы И 6, 7, 1О и 11 запираются. Начинается 1-я итерация, которая продолжается - тактов (до появления следующего импульса переполнения на щи- не 32). Выход первого разряда регистра 27 подключен к первому входу эле7(50 мепта 29 И, ко второму входу которо о подключен cxapiuufi разряд счетчика 26. Так как вес старшего разряда счетчика 2G равен - , то потенциал старшего разряда счетчика 20 за время наполле-, ия счетчика (до появления следующего импульса переполнения на шине 32) изменится два раза (один, раз нулевой, один раз - единичный). В нулевом состоянии на выходе блока управления сушествует единица, в результате чего элементы И 8 и 9 остаются открытыми, и через них проходят числа с выходов арифметического блока 5 на запись одновременно в первый и второй полурегистры регистра- 2. Это - числа А . - результаты базовой онерадии. Применительно к фиг. 2 это числа с 1-го по (они за пишутся во второй иолурегистр через вентили 9) и с 9-го но 12-е (запишутся в первый, полурегистр через элемент И 8). При этом на тактовые входы регистра 2 ; проходят импульсы с выхода элемента 22 ИЛИ, который, в свою очередь, пропускает эти импульсы с выхода элемента 18 И. По окончании нулевого состояния г блока управления 25 в регистре 2 записывается непрерывный ряд чисел: 1, 2 , 3, 4, 9, 10, 11, 12 (применительно к примеру на фиг, 2), который состоит толь ко из чисел А , причем в этом ряду имеются все числа А - массива для еле дующей итерации. В едини шом состоянии на выходе блока управления существует ноль, который запирает элемент 18 И, а также - элементы И 8, 9, при этом на выходе элемента 15 НЕ появляется единица, которая открывает элемент 19 И, элементы И 12 и 13, в результате числа с выхода арифметического блока 5 поступают на запись в регистр 4: числа с по записываются во второй полуре ; гистр (через элементы И 13), а числа 13 по 16 в первый полурегистр (через элементы И 12 ). При этом регистр 4 тактируется импульсами с выхода элемен та 24 ИЛИ, который , в свою, очередь, пропускает эти импульсы с выхода элеме та 19 И. По окончании единичного состо ния блока управления 25 в регистре. 4 записывается непрерывный ряд чисел: 5, 6, 7, 8, 13, 14, 15, 16 (применительн к примеру на фиг. 2), который состоит только из чисел В - , причем в этом ряду имеются все числа В- массива дл следующей итерации. За §се время первой итерации регистр 1 и 3 безостановочно,тактируются по це Го Оо почкам; элемент 17 11 элемент 2 L и элемент 17 И - элемент 23 ИЛИ соответственно, в то время как регистры 2 и 4 тактируются лишь тогда, когда в них происходит запись чисел. Поэтому, к моменту окончания первой итерации ре гистры 1 и 3 оказываются свободными, а регистры 2 и 4 заполняются числами. 8момент окончания итерации на шине 32 появляется импульс, который переключает в нулевое состояние триггер 14, в результате чего элементы И 8, 9, 12, 13 запираются, а элементы И 6, 7, 10, 11 открываются, элемент 17 И запирается, а элемент 20 И отпирается, что обуславливает постоянное тактирование регистров 2 и 4 по цепочкам: элемент 20 И элемент 22 ИЛИ и элемент 20 И - элемвнт 24 ИЛИ соответственно. Регистр 1 тактируется лишь тогда, когда на выходе узла 25 (выход элемента 28 ИЛИ) присутствует единица, а регистр 3 когда присутствует ноль. То есть регистры 1, 3 и 2, 4 меняются ролями. Одновременно импульс на |1аине 32 передвигает в регистре 27 единичный потенциал во второй разряд, который управляет элементом ЗО И по первому входу. Ко второму входу элемента 30 И подключается следующий за старшим разряд счетчика 26 с весом N/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, 1О и 14, 11 и 15, 12 и 16 (применительно к фиг. 2). Далее, -вторая итерация оканчивается, регистры 2 и 4 очищаются, регистры 1 и 3 заполняются чис90лами, вырабатывается импульс переполнения на шине 32, т; ттер 14 переходи в единичное состояние, единичный потенциал в регистре 27 переходит в 3 разряд, при этом потенциал на выходе эле- ментя 28 ИЛИ определи-:тся инверсным состоянием разряда счетчика с весом Kl/16 и все повторяется снова, как описано выше. По окончании всех итераций на шину 33 выходит единичный сягнал с выхода последнего разряда регист ра 27. Это и есть сигнал окончания БПФнцикла. При этом результаты БПФцикла располагаются либо в регистре 1 (если число итераций четное), либо в ре гистре 2 (если число итераций нечетное в естественном порядке (свойство алгоритма Стокхэма анди), причем другой регистр (либо 2, либо 1) будет обязательно свободным. Поэтому объединение регистров по выходу ничуть не мешает как при БПФ-пикле сдвигу нужных пар чисел в блок 5, так и при считывании конечного массива спектральных составляющих FQ -т- FJK на шину Выход(Вых. Итак, если сравнить три устройства, реализующих БПФ в реальном масштабе времени, и в качестве сравниваемых взять: процессор с ОЗУ, процессор по схеме прототипа и предлагаемое устройство, то процессор в прототипе превосхо дит процессор с ОЗУ по быстродействию, но получается при этом очень сложным и громоздким, насыщенным коммутацией. Предлагаемое же устройство, превосходя в такой же степени процессор с ОЗУ по быстродействию, конструктивно оказывае ся в несколько раз проще процессорапрототипа, ибо содержит всего один ариф метический блок вместо 9,. как в прототипе ( в общем случае - по числу итера ций), 8 точек коммутации вместо 72, как в прототипе ( в общем случае зави сит от числа итераций). Под- точкой ком мутации в предлагаемом устройстве под разумевается элемент И записи (из числа в 4- 11). Объем же триггерной памят одинаков у процессора-прототипа и у пре лагаемого процессора и равен 2 N. При этом предлагаемое устройство тем более экономичней процессора-прототипа, чем больше массив обрабатываемых данных, потому что с увеличением массива данны увеличивается число итераций, а значит и количество арифметических блоков и коммутаций в процессоре-прототипе. В предлагаемом же устройстве количества этих блоков (т. е. число арифметиР. 510 ческих блоков и число точек коммутации) не меняются. Формула изобретения Устройство для вычисления коэф4ИциентоБ Фурье, содержащее арифметический блок, управляющий вход которого соединен с выходом генератора тригонометрических функций, блок управления, «-разрядные регистры сдвига, о т л и ча ю щ е е с я тем, что, с це;1ью упрощения устройства, оно содержит триггер, элементы И записи, элемент НЕ и узел тактирования, выполненный на элементах И, ИЛИ, причем первые входы элементов И узла тактирования соединены с шкной тактовых импульсов, второй вход первого элемента И узла тактирования - с единичным выходом триггера, с первыми входами первого, второго, третьего и четвертого элементов И записи, второй вход второго элемента И узла тактирования соединен со входом элемента НЕ, с первым выходом блока управления, со вторыми входами первого и второго элементов И записи и с первыми входами пятого и шестого элементов И записи, второй вход третьего элемента И узла тактирования соединен с выходом элемента НЕ, с первыми входами седьмого и восьмого элементов И записи, вторыми входами третьего и четвертого элементов И записи, второй вход четвертого элемента И уата тактирования соединен с нулевым выходом тригтера, со вторыми входами пятого, шестого , седьмого и восьмого элементов И записи, выходы элементов И узла тактирования соединены с первы- ми входами соответствующих элементов ИЛИ узла таютирования, вторые входы первого, второго, третьего и четвертого элементов ИЛИ узла тактирования со единены соответственно с выходами второго, четвертого, первого и третьего элементов И узла тактирования, выходы элементов ИЛИ узла тактирования .соединены с тактовыми входами соответствующих регистров сдвига, выходы которых соединены со входами арифметического блока, первый выход которого соединен с третьими входами шестого, второго, восьмого и четвертого элементов И записи, второй выход арифметического блока соединен с третьими входами пятого, первого, седьмого и четвертого элемента И записи, выходы пятого, первого.