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

 

библиоте

С И оп и ди

ИЗОБРЕТЕН ИЯ

Союз Советских

Соцывлыстыческик республик

<

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 15.08,77 (2I) 2516246/18-24 с нрисоединением заявки Рй(23)ПрноритетОпубликовано 25.11.79. Бюллетень М 43 (5! )М. Кл.

G 06 F 15/34

Госудврстееииый «ои«тот

СССР ио делом изооретоиий и от«ритой, (53) УД К 681,32 7 (088.8) Дата опубликования описания 28.11.79 (72) Автори изобретения

B. Lt. Гусев, B. Н. Морозов и Г. И. Кацман

Специальное конструкторское бюро "Виброприбор (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

КОЭФФИЦИЕНТОВ ФУРЬЕ

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

Известны специализированные процес5 соры, осуществляющие быстрое преобразование Фурье (БПФ) в реальном времени.

Как правило, эти процессоры содержат оперативные запоминающие устройства .10 (ОЗУ) в виде автономных блоков.

Эти ОЗУ содержат матрицу памяти, системы шин занесения, шин считывания, адресную систему с признаком операции, линейки усилителей считывания (в слу15 чае с МОЗУ) и т. д. (1).

Наиболее близким по технической сущности к предложенному является устройство для вычисления коэффициентов Фурье, содержащее арифметический блок, управляющий вход которого соединен с выходом генератора тригонометрических функ» ций, блок управления, т1 — разрядные регистры сдвига. Кроме того, известное устройство содержит тт регистров разной длины для обработки массива 2 выборок, 11

Блина каждого последующего регистра меньше прецыдущего в 2 раза, что опре деляет нужное двоичное расстояние между парами чисел, выбираемыми для обработки на текущей итерации: в устройстве реализован алгоритм Кули-Тычки. Совокупность этих g. регистров образует общий регистр сдвига, в котором последовательные выборки сигналов располагаются в двоичной последовательности от

0 до 2 — 1. Каждый из т1 регистров П входит в состав соответствующего модуля. Общее число модулей равно, таким образом, И. Схема каждого модуля содержит, помимо регистра, арифметический блок, 8 линий задержки, 4 из которых входят в состав арифметического блока, а остальные 4 установлены на входе и выходе этого блока, причем объем линий задержки равен объему соответствующего регистра сдвига. Кроме того, схема модуля содержит коммутацито

25 3

«:» c «С = в 8 точках, управляемую устройством

« управпе«ия (с функциями индексного устройства). В пределах времени обработки одного массива данных одновременно включенным бывает только один арифме-, тический блок. При «.« =9 дпя построения процессора потребуется 9 арифметических блоков, 72 линии задержки, общим объемом 2 (т. е. 512) и коммутация B

tl

72 точках. Необходимо подчеркнуть, что «0 если выполнять задержку на триггерах, то суммарный объем памяти процессора составит 2 М, где Я- объем исходного массива чисел. С увеличением Ъ (а реально = 10 —; 13} приведенные коли- «5 чества будут возрастать. Помимо этого, в рассматриваемом процессоре применено постоянное запоминающее устройство синус-косинусных коэффициентов, ра бота которого определяется индексным устройством, вырабатывающим соответствующие адреса (21.

Однако данный быстродействующий процессор является громоздким и сложным.

Цель изобретения — упрощение устройства.

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

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

И записи, элемент HE и узел тактирования, выполненный на элементах И, ИЛИ, 35 причем первые входы элементов И узла тактирования сЬединены с шиной тактовых импульсов, второй вход первого элемента И узла тактирования — с единичным

40 выходом триггера, с первыми входами первого, второго, третьего и четвертого элементов И записи, второй вход второго алемента И. узла тактирования соединен со входом элемента НЕ, с первым

45 входом блока управления, со вторыми входами первого и второго элементов И записи и с первыми входами пятого и шестого элементов И записи, второй вход третьего алемента И узла тактирования

50 соединен с выходом элемента НЕ, с первыми входами седьмого и восьмого алементов И записи, вторыми входами третьего и четвертого элементов И записи, второй вход четвертого элемента И узла тактирования соединен с нулевым выходом триггера со вторыми входами пятого, шестого, седьмого и восьмого элементов И записи, выходы элементов И

25 4 узла тактирования соединены с первыми входами соответствующих элементов ИЛИ узла тактирования, вторые входы первого, второго, третьего и четвер ого элементов И узла тактирования соединены соответственно с выходами второго, четвертого, первого и третьего элементов И узла тактирования, выходы элементов

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

На фиг. 1 изображена структурная схема устройства; на фиг. 2 — граф для массива из 1 6 чисел алгоритма Стокхэма-Санди.

Устройство содержит регистры сдвига чисел 1 —: 4, арифметический блок 5, элементы И записи 6 —: 13, триггер 14, элемент HE 15, узел тактирования 16, элементы И 17 -, 20, элементы ИЛИ

2l - 24, блок управления 25, счетчик

26 объема —, регистр 27, элемент

ИЛИ 28, элементы И 29 —; 31, шину синхронизации 32, шину 33 сигнала окончания БПФ цикла, итерационные выходы

34 - 36 блока управления, генератор

37 тригонометрических функций, входы

38, 39 записи исходной информации в регистры, шину ТИ тактового импульса, шины выхода результата "Вых .

Предлагаемый процессор реализует алгоритмы Стокхэма-Санди. На фиг. 2 толстыми линиями обозначено умножение соответствующих чисел (при вершинах, откуда линии исходят) на единицу, а тонкими линиями - умножение соответствую99525 6

5 6 ших чисел иа тригонометрический Koýôôèциент 11(К-11 1»вЂ”

32Я где щ =Е,хр И

Я - объем обрабатываемого массива чисел (т. е. количество этих чисел);

p - номер итерации;

), — номер группы тонких линий, начиная от начала массива.

Так, например, на 1-с>й итерации (номера итераций проставлены сверху римскими цифрами) имеется только одна группа тонких линий (это числа в мас-. сиве с 9-го по 1 б-е), для которой трио гонометрический множитель равен % .

На второй итерации первая группа (r. е. числа с 5-го по 8-е) умножается на и, вторая группа чисел (с 13-го по

1 6-е) умножается на Ж+, на третьей итерации таких групп уже 4 (3 - 4, 7 - 8, 11 — 12, 15 - 16) и для них о соответственно имеем: Ф/,, щ 4 д", на четвертой итерации (.на последней) каждое число массива является группой, и здесь показатель степени 111 тригонометрического множителя меняется от 0 до 7. Естественно, что рассмотрен порядок изменения тригонометрических коэффициентов применительно к базовой операции алгоритма:

Таким образом, в отличие от алгоритма Кули-Тычки, данный алгоритм (Стекхэма-Санди) характеризуется естественным нарастанием показателя степени при 9/ внутри каждой итерации при смене групп чисел, возрастая каждый раз от 0 на одну и ту же величину. Эта особенность и позволяет применить в устройстве генератор, работающий по алгоритму (1). Здесь а(, есть та постоянная величина, на которую возрастает показатель степени при и которая задается в генераторе 37 соответствующей шиной (из числа 34 - . 36), на которой существует импульс, определенный текущей итерацией. Замечательной особенностью алгоритма является и то, что результаты базовой операции (т. е. Д„.+„ и3„ „) в массиве, формируемом для jq) итерации, всегда отстоят друг от друга на - )- чисел (т. е. на полмассива), Это

50 и дозволяет резко сократить число коммутаций в устройстве. Числа же А„ и

В„- для базовой операции берутся всегда из двух соседних групп чисел: число А„ берется иэ группы чисел, умножаемых на

1, а число В„- берется из следующей за ней группы чисел, умножаемых на @111. Если формировать массив для оче« редной итерации таким образом, чтобы числа А .1+ 1 и В, 4 записывались в разные регистры; то подавая на эти регистры тактовый импульс, можно сдвигать в арифметический блок нужные пары чисел одновременно.

В устройстве содержатся четыре регистра (1 -, 4), в каждый из которых можно записывать — чисел. При этом и каждый иэ регистров представляет собой два полурегистра, объемом -"-, включенных последовательно. Выход первого полурегистра включен на вход второго, причем на этот же вход второго полуре« гистра можно подавать числа с выхода соответствующих вентилей записи: 7, 9, 11, 13. В начале БПФ-цикла в регистры 1 и 3 заносится исходный массив чисел по шинам 38 и 39. Регистры 2 и 4 остаются свободными. При этом в регистр 1 заносится первая половина массива (первые. — чисел), а в регистр

Ц

3 — вторая половина массива, так что к началу первой итерации все числа А > сосредоточены в регистре 1, а все чисда В . — в регистре 3. Одновременно на л шину "Вых из регистра 1 (если число итераций четное) или из регистра 2 (ес« ли число итераций нечетное) выводится результат предыдущего цикла (как известно (lj, информативными при N чисй лах исходных являются только — чисел

2 результата). Занесение (выдача) чисел в регистры осуществляется за — — так« и

2 тов, и эти тактовые импульсы считаются счетчиком 26. В момент переполнения счетчика 26 (соответствует окончанию занесения в регистры 1 и 3 исходного массива чисел) на шине 32 синхронизации появляется импульс (переполнения), который записывает в первый разряд регистра 27 единицу и устанавливает в единичное состояние триггер 14. Элементы И 8, 9, 12 и 13 отпираются, элементы И 6, 7, 10 и 11 запираются.

Начинается 1-я итерация, которая продолжается — тактов (до появления слеН

2 дующего импульса переполнения на шине 32). Выход первого разряда регист-. ра 27 подключен к первому входу эле7 (i 9(э5 мепта 29 И, ко второму пхо, iy которого подключен старший разряд o÷åò÷èIIà 26.

Так как вес старшего разряда счет ьчка э - N ,. Ь равен —,, то потенциал с га ршего разряда счетчика 26 за время наполне-. ния счетчика (до появления следуюгцего и лпупьса переполнения па шине 32) изменится два раза (один раз — нулевой, один раз — единичный) . В нулевом состоянии на выходе блока управления су- !0 ществует единица, в результате чего " элементы И 8 и 9 остаются открытыми, и через них проходят числа с выходов арифметического блока 5 на запись одновременно в первый и второй полурегистры >5 регистра 2. Это — числа А — резуль1+4 таты базовой операции. Применительно к фиг. 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 дующей итерации. В единичном состоянии на выходе блока управления существует ноль, который запирает элемент 18 И, а также — элементы И 8, 9, при этом на выходе элемента 15 HE появляется единица, которая открывает элемент 19 И, элементы И 1 2 и 1 3, в результате числа

40 с выхода арифметического блока 5 поступают на запись в регистр 4: числа с 5-го по 8-е записываются во второй полуре, гистр (через элементы И 13), а числа

1 3 по 1 6 — в первый полурегистр (через элементы И 12 ). При этом регистр 4

45 тактируется импульсами с выхода элемента 24 ИЛИ, который, в свою, очередь, пропускает эти импульсы с выхода элемента 1 9 И. По окончании единичного состоя.ния блока управления 25 в регистре 4

50 записывается непрерывный ряд чисел: 5, 6, 7, 8, 1 3, 14, 1 5, 1 6 (применительно к примеру на фиг. 2), который состоит только из чисел В -, причем в этом

1+1 ряду имеются все чйспа В ° массива дпя

1+1 следующей итерации.

3а все время первой итерации регистры

1 и 3 безостановочно,тактируются по це г, 8 по цлм: элемент 1. 7 И вЂ” элемент 2

ИЛИ и элемент 17 И -:элемент 23 ИЛИ соответственно, в то время как регистры

2 и 1 тактируются лишь тогда, когда в них происходит запись чисел. Поэтому, к моменту окончания первой итерации регистры 1 и 3 оказываются свободными, а регистры 2 и 4 заполняются числами.

В момент окончания итерации на шине

32 появляется импульс, который переключает в нулевое состояние триггер 14, в результате чего элементы И 8, 9, 12, 13 запираются, а элементы И 6, 7, 10, ll открываются, элемент 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). QJIsr осуществления базовой операции в продолжении второй итерации в арифметический блок сдвигаются числа .соответственно парами: 1 и 5, 2 и 6, 3 и 7, 4 и 8, 9 и

13, 10 и 14, 11 и 15, 12 и 16 (применительно к фиг. 2). Gagee, вторая итерация оканчивается, регистры 2 и 4 очищаются, регистры 1 и 3 заполняются чисне меняются.

C} 6сЭ95 лами, вырабатывается импульс переполнения на шине 32, г, ri.ep 14 переходит в единичное состояние, единичный потенциал в регистре 27 переходит в 3 разряд, при этом потенциал на выходе элемента 28 ИЛИ онредел,. тся инверсным состоянием разряда счетчика с весом

М/16 и все повторяется снова, как описано выше. По окончании всех итераций на шину 33 выходит единичный сиг- 10 нал с выхода последнего разряда регистра 27. Это и есть сигнал окончания

БПФ-цикла. При этом результаты БПФцикла располагаются либо в регистре 1 (если число итераций четное), либо в ре- 15 гистре 2 (если число итераций нечетное) в естественном порядке (свойство алгоритма Стокхзма-Санди), причем другой регистр (либо 2, либо 1) будет обязательно свободным. Поэтому объединение 0 регистров по выходу ничуть не мешает как при БПФ-цикле сдвигу нужных пар чисел в блок 5, так и при считывании конечного массива спектральных составляющих F —; $ на шину Выход ("Вых . о 15

Итак, если сравнить три устройства, реализующих БПФ в реальном масштабе времени, и в качестве сравниваемых взять: процессор с ОЗУ, процессор по схеме прототипа и предлагаемое устрой30 ство, то процессор в прототипе превосходит процессор с ОЗУ по быстродействию, но получается при этом очень сложным и громоздким, насыщенным коммутацией.

HpegnaraeMoe же устройство, превосходя в такой же степени процессор с ОЗУ по быстродействию, конструктивно оказывается в несколько раз проще процессорапрототипа, ибо содержит всего один ариф40 метический блок вместо 9, как в прототипе (в общем случае — по числу итераций), 8 точек коммутации вместо 72, как в прототипе (в общем случае зависит от числа итераций). Под точкой ком45 мутации в предлагаемом устройстве подразумевается элемент И записи (из числа 6 -, 11). Объем же триггерной памяти одинаков у процессора-прототипа и у предлагаемого процессора и равен 2 Й . При этом предлагаемое устройство тем более экономичней процессора-прототипа, чем больше массив обрабатываемых данных, потому что с увеличением массива данных увеличивается число итераций, а значит и количество арифметических блоков и коммутаций в процессоре-прототипе. В предлагаемом же устройстве количества этих блоков (т. е. число арифметио Г) 1С ческих блоков и число точек коммутации) Формула изобретения

Устройство для вычисления коэффициентов Фурье, содержащее арифметический блок, управляющий вход которого соединен с выходом генератора тригонометрических функций, блок управления, и-разрядные регистры сдвига, о т л и ч аю щ е е с я тем, что, с целью упрощения устройства, оно содержит триггер, элементы И записи, элемент НЕ и узел тактирования, выполненный на элементах

И, ИЛИ, причем первые входы элементов

И узла тактирования соединены с шиной тактовых импульсов, второй вход первого элемента И узла тактирования — с единичным выходом триггера, с первыми вхо» дами первого, второго, третьего и четвертого элементов И записи, второй вход второго элемента И узла тактирования соединен со входом элемента НЕ, с первым выходом блока управления, со вторыми входами первого и второго элементов И записи и с первыми входами пятого и шестого элементов И записи, второй вход третьего элемента И узла тактирования соединен с выходом элемента

НЕ, с первыми входами седьмого и восьмого элементов И записи, вторыми входами третьего и четвертого элементов И записи, второй вход четвертого элемента

И узла тактирования соединен с нулевым выходом григ гера, со вторыми входами пятого, шестого, седьмого и восьмого элементов И записи, выходы элементов

И узла тактирования соединены с первыми входами соответствующих элементов

ИЛИ узла тактирования, вторые входы первого, второго, третьего и четвертого элементов ИЛИ узла тактирования со единены соответственно с выходами второго, четвертого, первого и третьего элементов И узла тактирования, выходы элементов ИЛИ узла тактирования соединены с тактовыми входами соответствующих регистров сдвига, выходы которых соединены со входами арифмртического блока, первый выход которого соединен с третьими входами шестого, второго, восьмого и четвертого элементов И записи, второй выход арифметического блоКа соединен с третьими входами пятого, первого, седьмого и четвертого элемента И записи, выходы пятого, первого, 11 69 седьмого и третьего элел.ентов И запи- си соединены с информационными входами первых разрядов соответствующих регистров сдвига, выходы шестого, второ о, восьмого и четвертого элементов И записи соединены с информационными входами (п/2 + 1) разрядов соответствующих регистров сдвига, счетный вход триггера соединен со вторым выходом блока уп9525 равления, третья группа выходов которого соединена с упрагпяющими входами

t"å .åpàòoðï тригоцометри ческих функций.

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

1. Патент СПИ № 3803391, кл. 340 — 165, 1974.

2. Патент США ¹ 381 6729, кл. 340 — 165, 1975.

ЦНИИПИ Заказ 7229/53

Тираж 780 ПодписноеФилиал ППП Патент, г. Ужгород, ул. Про ектная,4