Устройство для быстрого преобразования фурье

 

УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНА ФУРЬЕ, содержащее последовательно -соединенные генератор тактовых импульсов, счетчик адреса и блок постоянной памяти, блок постоянной памяти коэффициентов и К вычислительных блоков, каждый из которых состоит из первого и второго коммутаторов , первого, второго, третьего и четвертого узлов памяти и арифметического узла, информационные выходы первого и второго коммутаторов подключены к информационным входам соответственно первого и второго узлов памяти, управляющие, входы которых подключены к выходам соответственно первого и второго разрядов блока постоянной памяти, выходы третьего, четвертого, пятого и щестого разрядов которого подключены к управляющим входам соответственно третьего и четвертого узлов памяти, первого и второго коммутаторов -го (,K) вычислительного блока, первые информационные входы первого и второго коммутаторов j-го () 1,К-1) вычислительного блока подключены к информационным выходам соответственно первого и второго узлов памяти (j+1)-ro вычислительного блока, первый информационньм вход второго коммутатора К-го вычислительного блока подключен к информационному выходу первого узла памяти первого вычислительного блока, вторые информационные входы первого и второго коммутаторов

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (11) з(51) G 06 F 15/332 ч

QllHCAHI4E HSOEPETEHHR I

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ (21) 3643104/24-24 (22) 16.09.83 (46) 23. 12.84. Бюл. У 47 (72) Г.В.Зайцев и Н.F..Нагулин (53) 681.32(088.8) (56) 1. Л.Рабинер, .Б.Гоулд ° Теория и применение цифровой обработки сигналов. М., "Мир р 1978.

2. Авторское свидетельство СССР

У 660057, кл. G 06 F 15/332, 1976 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее последовательно соединенные генератор тактовых импульсов, счетчик адреса и блок постоянной памяти, блок постоянной памяти коэффициентов и k вычислительных блоков, каждый из которых состоит из первого и второго коммутаторов, первого, второго, третьего и четвертого узлов памяти и арифметического узла, информационные выходы первого и второго коммутаторов подключены к информационным входам соответственно первого и второго узлов памяти, управляющие. входы которых подключены к выходам соответственно первого и второго разрядов блока постоянной памяти, выходы третьего, четвертого, пятого и шестого разрядов которого подключены к управляющим входам соответственно третьего и четвертого узлов памяти, первого и второго коммутаторов (-ro (1 =1,k) вычислительного блока, первые информационные входы первого и второго коммутаторов -го (1=1,g -1) вычисли1 тельного блока подключены к информационным выходам соответственно первого и второго узлов памяти (1+1)-ro вычислительного блока, первый информационный вход второго коммутатора

h-го вычислительного блока подключен к информационному выходу первого узла памяти первого вычислительного блока, вторые информационные входы первого и второго коммутаторов (2ш-1)-го (re=

=1, k / ) вычислительного блока подключены к информационным выходам третьих узлов памяти соответственно m-го и (М+ -)-го вычислительных блоков

k 2 у вторые информационные входы второго и первого коммутаторов 2 -ro (0=1, 4 I2 ) вычислительного блока подключены к информационным выходам четвертых узлов памяти соответственно (, -го и а (l> h(2,) -го вычислительных блоков, а арифметический узел р -то тр- i,K) ви- Q) числительного блока содержит умножи- у тель, сумматор, вычитатель и первый и второй коммутаторы, при этом выход умножителя подключен к первым входам соответственно вычитателя и сумматора, выход которого подключен к первым информационным входам первого и второго коммутаторов, информационные выходы которых подключены к информационным входам соответственно третьего и четвертого блоков памяти

5-ro вычислительного блока, первый вход умножителя арифметического узла -у-го вычислительного блока подключен к выходу 5 -го разряда блока постоянной памяти коэффициентов, управля- еВ ющие входы первого и второго коммутаторов арифметических узлов вычислительных блоков подключены к выходу седьмого разряда блока постоянной памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения его быстродействия, в него введены первый

1130872 и второй коммутаторы, регистр сдвига, в каждый вычислительный блок введен .

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

Известны многопроцессорные цифровые устройства быстрого преобразования Фурье, реализующие метод вычислений по алгоритму быстрого преобразования Фурье (БПФ}, позволяющие вычислить N коэффициентов дискретного пре- 1> . образования Фурье временной последовательности no N выборкам входного сигнала. Эти устройства содержат блоки памяти, арифметические блоки, блок памяти коэффициентов и работают в ре- 20 альном масштабе времени Я .

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

k=2, где f — целое число (1 741од Х), вычислительных блоков, каждый из коственно восьмого и девятого разрядов блока постоянной памяти, выход десятого разряда которого подключен к управляющему входу переключателя

Р-го(= 3,g) вычислительного блока, информационные выходы первого и второго узлов памяти Р -ro вычислительного блока подключены соответственно к первому и второму информационным входам переключателя p-ro вычислительного блока, первый и второй информационные выходы которого подключены соответственно к второму вхо;, ду умножителя и вторым входам сумматора и вычитателя арифметического узла вычислительного блока, выход вычитателя арифметического узла подключен к входу элемента НЕ арифметического узла, выход которого подключен к вторым информационным входам первого и второго коююутаторов арифметического узла. торых состоит из коммутаторов, блоков памяти и арифметического блока, причем управляющие входы коммутаторов подключены к выходам блока управления, а информационный вход арифметического блока — к выходу блока формирования весовых коэффициентов. Это устройство реализует граф алгоритма

БПФ с однородной структурой, .при ко-: торой адресация записи и считывания обрабатываемых чисел не зависит от номера интеграции ° Вследствие однородности графа алгоритма БПФ связи между I(вычислительными блоками остаются фиксированными в процессе вычислений (2) .

Недостатком этого устройства явля-. ется низкое быстродействие и избыточный объем памяти при вычислении преобразования Фурье действительного входного сигнала

Цель изобретейия — повышение быстродействия устройства для быстрого преобразования Фурье.

Цель достигается тем, что в устройство для быстрого преобразования

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

-памяти и арифметического узла, информационные выходы первого и второго коммутаторов подключены к информационным входам соответственно первого 10 и второго узлов памяти, управляющие входы которых подключены к выходам соответственно первого и второго разрядов блока постоянной памяти, выходы третьего, четвертого, пятого и 15 шестого разрядов которого подключены к управляющим входам соответственно третьего и четвертого узлов памяти, первого и второго коммутаторов

> -ro (1 = 1,К) вычислительного блока, 20 первые информационные входы первого и второго коммутаторов j-го (j=1,k-1) вычислительного блока подключены к информационным выходам соответственно первого и второго узлов памяти .25 (j+1)-ro вычислительного блока, первый информационный вход второго коммутатора k -го вычислительного блока подключен к информационному выходу первого узла памяти первого вычислительного блока, вторые информационные входы первого и второго коммутаторов (2m-1)-го (тп=1,k./2) вычислительного блока подключены к информационным выходам третьих узлов памяти соответственно .тп-го и (m+k/2)-го вычислительных блоков, вторые информационные входы второго и первого коммутаторов 21-го (1=1,k/2) вычислительного блока подключены к информа- 40 ционным выходам четвертых узлов памяти соответственно f-го и (7+k/2)-го вычислительных блоков, а арифметический узел 5-го (=1,k) вычислительного блока содержит умножитель, сумма- 45 тор, вычитатель и первый и второй .коммутаторы, при этом выход умножителя подключен к первым входам соответственно вычитателя и сумматора, выход которого подключен к первым ин-50 формационным входам первого и второго коммутаторов, информационные выходы которых подключены к информационным входам соответственно третьего и четвертого блоков памяти 5-ro вычислительного блока, первый вход умножителя арифметического узла 5 --го вычислительного блока подключен к

72 4 элемент НЕ, причем информационный выход регистра сдвига подключен к первому информационному входу первого коммутатора, информационный выход которого соединен с информационным выходом второго коммутатора и с первым информационным входом первого коммутатора k-го вычислительного блока, второй информационный вход первогО коммутатора соединен с первым информационным входом второго коммутатора, с информационным входом регистра сдвига и является первым информационным входом устройства, вторым информационным входом которого является второй информационный вход второго коммутатора, управляющие входы первого и второго коммутаторов подключены к выходам соответственно восьмого и девятого разрядов блока постоянной памяти, выход десятого разряда которого подключен к .управляющему входу переключателя р-ro (р=1,k) вычислительного блока, информационные выходы первого и второго узлов памяти р-ro вычислительного блока подключены соответственно к первому и второму информационным. входам переключателя р-го вычислительного блока, первый и второй информационные выходы которого подключены соответственно к второму входу умножителя и вторым входам сумматора и вычислителя арифметического ysла вычислительного блока, выход вычитателя арифметического узла подключен к входу элемента НЕ арифметического узла, выход которого подключен к вторым информационным входам первого и второго коммутаторов арифметического узла.

На фиг.1 приведена функциональная схема устройства; на фиг.2 — функциональная схема вычислительного блока, на фиг.З вЂ” функциональная схема арифметического узла," на фиг.4 — граф алгоритма БПФ действительной последовательности для N=16 на фиг.5 - базо1130872 вая операция алгоритма БПФ действи-тельной последовательности на фиг.6функциональная схема переключателя; на фиг.7 — функциональная схема блока управления, на фиг.Я вЂ” временная диа- 5 грамма работы блока управления.

Устройство содержит коммутатор 1, регистр 2 сдвига, коммутатор 3, вычислительные блоки 41-4, блок 5 постоянной памяти коэффициентов, блок

6 управления.

Вычислительный блок (фиг.2) содержит узлы 7 памяти, арифметический узел 8, переключатель 9, узлы 10 памяти и коммутаторы 11 ° 35

Арифметический узел (фиг.3) содержит умножитель 12, вычитатель 13, сумматор 14, элемент НЕ 15, коммутаторы 16.

Блок управления (фиг.7) содержит генератор 17 тактовых импульсов, счетчик 18 адреса, блок 19 постоянной памяти.

Устройство работает следующим образом.

В режиме обработки действительного сигнала при записи входной информации первая половина входной действительной последовательности х(п) длительности N-2,, где k — целое, 0 к поступает на регистр 2, имеющий длину N/2 слов, и через коммутатор 3 на первый вход k-го вычислительного блока. Вторая половина информации поступает через коммутатор 1 непос- з редственно на первый вход k-го вычислительного блока. В результате на этот вход одновременно поступают выборки входного сигнала x{i) и x(i+

+N/2) (i=0-И/2-1), которые при обра- 40 ботке рассматриваются соответственно, как действительная и мнимая части комплексного числа y(i), где

y(i)m(i)+jx(i+N/2);

;=0 - И/2-1, )= 1:1 .

Таким образом, с помощью коммута..торов 1 и 3 регистра 2 входная действительная последовательность длины

N преобразуется в комплексную после- 0 довательность длины N/2.

В случае обработки комплексного сигнала вся входная информация, представляющая собой последовательность комплексных чисел, поступает через коммутаторы 1 и 3 непосредственно на первый вход k-ro вычислительного бло1 ка.

При загрузке входной информации коммутаторы 11 вычислительных блоков (4-1,...,4-k) .пропускают сигналы, поступающие на входы вычислительных блоков (4-1,...,4-k) (независимо от того является входная последовательность действительной или комплексной). При этом узлы памяти 7 всех вычислительных блоков соединяются последовательно, образуя цепочку для загрузки входной последовательности.

После N/2 тактов сдвига в первый узел 7 памяти (нижний на фиг.2) д-го вычислительного блока (4-i) (i=1-k) запишутся выборки y(k) с номерами

k с — (x-1) по ->-1,во второи узел

М °, М °

7 памяти этого же блока (верхний на фиг.2) — выборки с номерами k+, где

И 2й- -

И

После записи всей входной информации начинается собственно процесс ее обработки.

Граф алгоритма БПФ действительной последовательности для N=16 представлен на фиг.4, а базовая операция этого алгоритма †. на фиг.5.

Однородность графа позволяет установить фиксированные связи между вычислительными блоками (4-1, 4-2, 4-k).

Отметим следующую особенность графа(фиг.4 ).Результирующие значения спектральных составляющих x(k) (k=1-Н/2-1) получаются в результате выполнения 1о8 N-1 итераций, Для получения значений х(0) и

x(N/2) необходимо дополнительно соответственно сложить и вычесть действительную и мнимую части числа А (граф на фиг.4), Поскольку при решении практических задач эти точки находятся на краях анализируемого диапазона частот, то их вычисления, как правило, не требуется.

На любой итерации в каждом вычислительном блоке обрабатываемые величины у (k) из первого узла 7 памяти и

y(k+N/4) из второго узла 7 памяти (1=0-N/4-1) одновременно поступают на вход переключателя 9 ° Если базовая операция над этЮ парой. комплексных чисел выполняется со значением весового множителя, равным M, то переключатель 9 осуществляет. перестанов.ку мнимой части числа y(k) и действительной части числа y(k+N/4) в соответствии с алгоритмом (фиг.5). Схема, осуществляющая указанную перестанов7 11308 ку, может быть пост.роена на основе двух коммутаторов (фиг.6). Сигналы с выхода переключателя 9 поступают на соответствующие входы арифметического узла 8. Комплексное число y(k+N/4) поступает на вход умножителя 12, на .другой вход которого из блока 5 постоянной памяти коэффициентов поступает соответствующее значение весового множителя W, зависящее от номера 10 выборки и от номера итерации.

Таким образом, на выходе умножителя 12 получается значение произведения y(k+N/4) W . Это число с выхода умножителя 12 подается на входы вычи- 15 тателя 13 и сумматора 14, на другие входы которых одновременно подается число y(k) с выхода переключателя 9.

На выходе сумматора 14 получается результат уОс)+у(1с+Н/4) W . Резуль- 20

8 тат,. полученный на выходе вычитателя

13 и равный y(k)-y(k+N/4) W, поступает на вход элемента НК 15, который выполняет операцию комплексного сопряжения,числа, так что на его выходе получается число (v(k)-v(k+<) W, 1 . н. е

Результаты с выхода сумматора 14 и элемента НЕ 15 последовательно один за другим по управляющему синхроимпульсу от блока 6 управления через

1 коммутаторы 16. записываются в третий (верхний на фиг.2) и четвертый (нижний на фиг.2) узлы 10 памяти в зависимости от номера отсчета обрабатываемой последовательности, причем в

5 третий узел 10 памяти записываются взвешенные сумма и разности первой половины вычислительных результатов, в четвертый — вторая половина.

После — тактов вычислений содер- 40

2 жимое третьих и четвертых узлов 10 памяти переписывается соответственно в первые и вторые узлы 7 памяти соответствующих блоков (через коммутатор 45

11 по управляющему синхроимпульсу с блока 6 управления. Это позволяет проводить обработку информации во всех последующих итерациях аналогично описанной.

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

Один из возможных вариантов построения блока 6 управления приводится на фиг ° 7. Блок 6 управления состо72 8 ит из генератора 17 тактовых импульсов, сигнал от которого подается на счетчик 18 адреса. В зависимости от состояния счетчика на выходе блока 19 постоянной памяти формируются необходимые управляющие сигналы. На фиг.9 показан вид управляющих сигналов, которые формируются на выходе блока 19 для управления переключателем 9 (в режиме обработки действительного сигнала), коммутаторами 11, 16 и управляющие сигнвлы на запись и считывание узлов 7 и 10 памяти.

По управляющему сигналу на коммутатор 11 (сигнал g на фиг.9) в режиме входной информации пропускаются сигналы, поступающие на входы вычислительных блоков (4-1-4-Е) для записи в узлы 7 памяти (по управляющему сигналу о на фиг.8),. Далее при выполнении вычислений коммутаторы 11 пропускают сигналы, поступающие.на входы всех вычислительных блоков..

Процесс вычислений на каждой итерации можно разбить на два этапа. На первом этапе по управляющему сигналу считывания (сигнал b на фиг.9) производится считывание информации из первого и второго узлов 7 памяти и выполняются базовые операции в арифметическом узле 8. На этом же этапе первая половина результатов вычислений, получаемых на выходе арифметического узла 8, по управляющему сигналу записи (сигнал на-фиг.8) записывается в третий узел 10 памяти, а вторая половина записывается в четвертый узел 10 памяти по управляющему сигналу 8 на фиг.8. Коммутация информации между третьим и четвертым узлами 10 памяти осуществляется коммутаторами 16 о управляющему сигналу на фиг.8. Поскольку sa время считывания числа из блока 7 памяти в один из узлов 10 памяти должны записываться два числа, то частота записи в узлы 10 памяти должна быть в

2 раза больше, чем частота считывания из узла 7 памяти (фиг.8).

На втором этапе производится перезапись результатов вычислений из узлов 10 памяти в узлы 7 памяти в соот ветствии со схемой фиг.1. При этом управляющий сигнал считывания из узлов 10 памяти имеет такой же вид, как и сигнал записи в узлы 7 памяти (сигнал 6 на фиг.8).

9 1130

По управляющему сигналу (сигналж на фиг.8) на переключателе 9 в режиме обработки действительной последовательности выполняется перестановка мнимой части числа y(k) и действи-, тельной части числа у(1с+-), (k=o, 1), и поступающих на переключатель 9 из узлов 7 памяти при выполнении базовых операций со значением весового мно-" 1б жителя Ы . Так на первой итерации будет осуществляться перестановка

М каждой пары чисел y(k), y(k+-) (k=

=О- — -1} поскольку на этой итерации

Э 1-ñ" ! все базовые операции выполняются со значением весового множителя M, В соответствии с графом на фиг.4 с увеличением номера итерации на единицу число базовых операций с весовым 20 множителем M уменьшается в 2 раза, поэтому во столько же раз должно уменьшаться число перестановок, осу ществляемых переключателем 9.

На основании приведенного изложс — 25 ния и временной диаграммы фиг.8 производится запись информации в блок 19 для получения необходимых управляющих сигналов. Причем для формирования каждого сигнала необходимо И+Ь„ ячеек И памяти, где ш — число итераций алгоритма БПФ, 1=N/k. В блоке 19 информация распределяется по ячейкам памяти следующим образом: в разряде„ предназначенном для формирования управляющего сигнала на коммутаторы .II, в ячейки памяти с адресами i=0 1,..., N-1 записывается "1", а в остальные—

"0", в разряде, предназначенном для формирования управляющих сигналов за-40 писи блоков 7 памяти и считывания блоков 9 памяти, в ячейки памяти с адресами 4i-1, 4i-2(i=1,2,...N/4), 4i-2+N+-+(k+1), 4i-1+N+-+(k-1)1 (i:=

l.

=(i=1 2,...-, k=1 2,...m) записывается "1", а в остальные — "О".

В разряде, предназначенном для формирования управляющего сигнала считывания блоков 7 памяти, в ячей ки памяти с адресами 4i-2+N+(m-1)L,, 4

4i-1+И+(ш-1) Ь (i=1,— ) (k=I,m) . запи\ сывается "1", а в остальные - "О".

872 10

I в разряде, предназначенном для формирования управляющего сигнала записи третьего блока 10 памяти, в ячейки памяти с адресами 2i+1+N+(k+1)L(i=1, L/4-1, k=1,m) записывается "f", а в остальные — "0", в разряде, предназначенном для формирования управляющего сигнала .записи четвертого блока

10 памяти, в ячейки памяти с адресаL ми 2х+1+Н+-+(k- I ) ° L (i=1 Ь/4-1 ° k=1

m) записывается "1", а в остальные—

"О", в разряде, предназначенном для формирования управляющего сигнала коммутаторами 16, в ячейки памяти с адресами 1.+(п-l)Ь+И(д.=О,N/4-1; k=I,m) записывается "1"., a в остальные—

"0", в разряде, предназначенном для формирования управляющего сигнала переключателем 9, в ячейки памяти с адресами i=N+(k-1)>Ь, N+1+(k-1)L,..., К+(k-I). L+L/2 -1 (k=f,m) записывается "I", а в остальные — "О".

В случае обработки комплексной последовательности по внешней команде вся входная информация поступает через коммутаторы 1 и 3 непосредственно на первый вход k-го вычислительного блока. По этой же команде перестановка мнимой части числа у(К) и действительной части числа y(k+N/4) переключателем 9 не производится и не выполняется операция комплексного сопряжения числа на выходе вычитателя 13.

Окончательный результат N/2 коэффициентов дискретного преобразованйя

Фурье входного сигнала получается после и-1 итераций, записанными в третьи и четвертые узлы 10 памяти k вычислительных блоков. Порядбк записи результатов вычисления преобразования

Фурье действительной входной последовательности отличается от нормального и является стандартным для такого типа графов.

Таким образом„,использование предлагаемого изобретения позволит сократить более чем в 2 раза время обработки действительного сигнала и вдвое уменьшить объем памяти вычислительных блоков. При этом уменьшается стоимость устройства и повышается его йадежность.

1130872

1130872.1130872 х(П) /x(e

x0)+ix(s)

)((2ЯХ(10)

xp) )х(1) ) х(ю) х ()

x(s)< /х (13)

x(s)ii x (re) у(ур)х(щ х(4) х(2)

z(g

Х(1) хп) X(3)

x($) Я Х Х= РеА+, геВ Я (тА+ я6)

° °

У= геЛ- геВ- М (i A - jirnA), при Ю=д

Nf.,х=,4+И(кд

К

g = " Рg rpurgO

2;5

11 30872

1130872

Составитель А. Баранов

Редактор С.Патрушева Техред З.Палий

Корректор О.Тигор

Подписное

Филиал ППП "Патент", г.ужгород, ул .Проектная, 4

Заказ 9612/36 Тираж 698

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5