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

 

Ю. А. Грачев, И. Е. Петров, Л. В. Сабаев и Т. Н. Федоровская (72} Авторы изобретен и» (71} Заявитель (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ

ФУРЬЕ

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

Известно цифровое устройство, реализующее алгоритм быстрого преобразования Фурье (БПФ), состоящее из сумматоров, множительно1о устройства, запоминающих устройств, формирователя весовых коэффициентов f 11.

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

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

Известное устройство реализует алгоритм БПЭ с естественным порядком поступления входных выборок. Еля реализации БПФ пон поступлении входных выборок в двоично-инверс 1оМ представлении в этом же источнике представлен другой вариант устройства.

Целью изобретения является повьшиние надежности работы устройства путем осущ= твления контроля его работы при реализации двух апгоритмов БПФ.

Это достигается тем, что устройство содержит схему сравнения и два коммутатора, причем вход устройства соединен с первыми входами первого и второго элементов И-ИЛИ, вторые входы которых подключены к первой группе входов схемы сравнения, соответственно к пер-. вым входам первого и второго. коммутаторов и соответственно к выходам первого и второго блоков памяти, входы которых соединены соответственно с выходами первого и второго элементов И-ИЛИ, выходы первого и второго коммутаторов соединеиы соответственно с первыми и вторыми входами сумматора и сумматора-вычитателя, выход сумматора соединен с первыми

3 687449

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

На чертеже приведена структурная схема предлагаемого устройства. zo

Оно имеет блоки памяти 1, 2, 3, 4, 5, 6, сумматор 7, сумматор-вычитатель 8, блок умножения 9, блок 10 хранения весовых коэффициентов, вход 11, элементы И-ИЛИ 12, 13, 14, 15, 16, 17, 18, 19, коммутаторы 20, 21, схему срав- 25 ненни 22.

Устройство реализует два алгоритма БПФ: х. „(2к) = х. (к) + х- (к+ ) (2к + 1) fx (K) — x (к + ))% и ()

1+1

1 х(1+1)(к) = х ° (2K) + x; (2к + 1) х(;+1)(к+ ) fxÄ- (2к) — х;(2к+1))% а ®

М. где i — номер итерации (i 1 —; log N); к — номер выборки (к . Π—; N(2-1);

«7 « . &г щ (М

P —. весовой коэффициент, зависящий от номера выборки и номера итерации, 4о

При реализации алгоритма (3) входная последовательность поступает в естественном порядке; запись входной информации, состоящей и иэ 2 = 1ч комплексных выборок, в блоки 1 и 2 45 памяти осуществляется следующим образом: первые й/2 выборок через элемент И-ИЛИ 13 в блок памяти 1, последующие N/2 выборок (от

N/2 + 1 до N) через элемент И-ИЛИ 12 в блок

2 памяти, После записи входной информации начинается обработка ее цо алгоритму (1), Первая пара входных выборок хе (О) н

Йе (Й/2 + О) по одной считаются соответственно из блоков 1 и 2 памяти я через коммутаторы

20 и 2ll поступает на входы сумматора 7 и сум-, матора-вычнтателя 8, причем значение хо (И/2+0) на вход сумматора-вычитателя 8 поступает обратным кодом. С выхода сумматора 7 полученное значение х1(0) = хо (0) + хо (й/2 + О) через

4 элементы И-ИЛИ 14 и 15 записывается в блок 3 памяти. Значение с сумматора-вычитателя 8

fxp (О) — хе (N/2+0) ) поступает на первый I вход блока 9 умножения, одновременно на второй его вход из блока 10 хранения весовых коз фициентов поступает соответствующее значение (wP), результат с выхода блока 9 умножения х1(1) = fxp(О) — xp(N/2 + О)) wÐ через элементы И-ИЛИ 14 — 15 записывается вслед за х1(0) в блок 3 памяти. Затем вторая пара чисел аналогично описанному считывается из блоков 1 и 2 памяти и через коммутаторы 20 и 21 поступает на входы сумматора 7 и сумматора-вычитателя 8, конечный результат с выхода сумматора 7 и блока 9 умножения через элементы И-ИЛИ 14 и 15 записывается в блок 3 памяти, Так повторяется

N/4 тактов. Через И/4 тактов блок 3 памяти. о оказывается заполненным и следующая пара полученных результатов через элементы И-ИЛИ 14 и 16 записывается в блок 4 памяти. Так продолжается N/4 раз. После заполнения блока 4 заканчивается первая итерация. Во второй итерации считывание информации производится из блоков 3 и

4 памяти через соответствующие коммутаторы 20 и 21. Весь процесс идет аналогично описанному, только запись полученных результатов первые

N/4 тактов через элементы И-ИЛИ 14 и 17 последовательно один за другим идет в блок 5 памяти, а вторые N/4 тактов через элементы И-ИЛИ 14 и 18 в блок б памяти. В третьей итерации (н в последующих нечетных итерациях) информация считывается одновременно из блоков 5 и 6 памяти, а записывается последовательно в блоки 3 и

4 памяти, а в четных итерациях они меняются местами (т.е. считывание идет из блоков 3 и 4 памяти, а запись в блоки 5 и 6 памяти.

По окончании последней итерации считывание информации через элемент И-ИЛИ 19 с выходов сумматора 7 и блока 9 умножения поступает на выход устройства в двоично-инверсном по отношению к естественному порядку.

При работе по алгоритму (2) входная инфор, мация поступает в даоично-инверсном-порядке, запись входной информации идет поочередно по одному слову в блоки 1 и 2 памяти.

Первая пара чисел, считываемых из блоков

1 и 2 памяти, через коммутаторы 20 и 21 обрабатывается в соответствии с формулами (2) аналогично алгоритму 1. Полученные результаты с выхода сумматора 7 в первой итерации (и в остальных нечетных итерациях) через элемент ИИЛИ 15 записываются в блок 3 памяти, а в четных итерациях в блок 5 памяти через элемент

И-ИЛИ 17. Запись результатов с выхода блока

9 умножения в нечетных итерациях через элемент И-ИЛИ 16 идет в блок 4 памяти, а в четных итерациях через элемент И-ИЛИ 18 — в блок б памяти. Считывание информации во всех итера5 68744 циях иэ блоков 3 и 4 памяти идет последовательно по два числа из каждого блока памяти в учение N/4 тактов через коммутаторы 20 и, 21.

Аналогично в других итерациях идет считывание нэ блоков 5 и 6 памяти. Окончательный результат, как и в алгоритме (1), поступает на выход устройства с выходов сумматора 7 и блока 9 умножения через элемент И-ИЛИ 19.

Входная информация в режиме контроли 1о через элементы И-ИЛИ 12 и 13 с выходов блоков

1 и 2 памяти записывается на входы этих же бло- . ..ков. После реализации прямого преобразованйя Фурье но алгоритму:(1) или (2) осуществляется

+> 2(c обратное преобразование Фурье (= и ), но по другому алгоритму, т.е. если прямое llpeобразование осуществляется по алгоритму (1), обратное преобразование будет осуществляться по алгоритму (2), TSK как результат прямого

20 преобразования оказывается записанным в блоки памяти в двоично-инверсном по отношению к входному порядке.

Результат прямого преобразования оказывается записанным либо в блоки 3 и 4 памяти, либо в блоки 5 и 6 памяти (в зависимости от числа итераций). Поэтому для обратного преобразования Фурье в первой итерации информация считывается из этих блоков в соответствии с необходимым алгоритмом через коммутаторы 20 и 21. В последней итерации информация с выходов сумматора 7, блока 9 умножения и с вь хо-, дов блоков 1 и 2 памяти поступает,на схему сравнения, Результат сравнения поступает на конт, рольный выход устройства.

Ä5

Формула изобретения

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

9 6 ты И-ИЛИ, причем входы блока умножения соединены соответственно с выходом блока храJ пения весовых коэффициентов и выходом сумматора-вычитателя, о т л и ч а ю щ е е с я тем, что, с целью повышения надежндсти работы устройства в работе, оно содержит схему сравнения и два коммутатора, причем вход устройства соединен с первыми входами первого и второго элементов И-ИЛИ, вторые входы которых подключены к первой группе входов схемы сравнения, соответственно к первым входам первого и второго коммутаторов и соответственно к выходам первого и второго блоков памяти, входы которых соединены соответственно с выходами первого и Рторого элементов И-ИЛИ, выходы первого и второго коммутаторов соединены со. ответственно с первыми и вторымн входами сумматора и сумматора;вычитателя, выход суммато . ра соединен с первыми входами третьего, четвертого, пятого и шестого элементов И-ИЛИ и с первым входом из второй группы входов схемы сравнения, выход сумматора-вычитателя через блок умножения соединен со вторыми входами третьего и четвертого элементов И-ИЛИ, первыми входами седьмого н восьмого. элементов

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

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

1. Авторское свидетельство СССР Р 421994, кл. G 06 F 15!34, 1974.

2, Патент Франции У 2082030, G 06 F 15/00, 1971.