Устройство для выполнения преобразования Фурье Советский патент 1984 года по МПК G06F17/14 

входу 1-го сумматора в соответствующем блоке преобразования первого рода, выход i-ro сумматора и выход i-r вычитателя третьей группы являются выходами действительной и мнимой составляющих по i-My выходу соответствующего блока преобразования первого рода, каждый из блоков преобра зования второго рода 1-го яруса имеет две группы по выходов и содержит две группы по 2 сумматоров , четыре группы по вычктателей и четыре группы по 2 элементов взвешивания, причем суммирующие входы i-x вычитателей первой и второй групп являются соответственно входами действительной и мницой составляющих по i-му входу соответствующего блока преобразования второго рода, вычитаюпще входы i-x вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по ( + i)-My входу соответствующего блока преобразования второго рода, выход i-ro вычитателя первой группы через i-й злемент взвешивания первой груп пы подключен к пер.вому входу i-ro сумматора первой группы и к суммирую щему входу i-ro вычитателя третьей группы в соответствующем блоке прео разования второго рода, выход i-ro вычитателя первой группы через i-й элемент взвешивания второй группы подключен к первому входу i-ro сумма тора второй группы и к суммирующему входу i-ro вычитателя четвертой группы в соответствующем блоке прео разования второго рода, выход i-ro вычитателя второй группы через i-й злемент взвешивания третьей группы подключен к второму входу i-ro сумматора второй группы и к вычитающему входу i-ro вычитателя четвертой группь в соответствующем блоке преобразования второго рода, выход i-r вычитателя ВТОРОЙ группы через i-й элемент взвешивания четвертой группы подключен к второму входу i-ro сумматора первой группы и вычитающему входу i-ro вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход i--ro сумматора первой группы и выход i-ro вычитателя четвертой группы яв ляются выходами действительной и мни 1 7 мой составляющих по i-му выходу первой группы, а выход i-ro вычитателя третьей группы и выход i-ro сумматора второй группы являются выходами действительной и мнимой составляющих по i-му выходу второй группы соответствующего блока преобразования второго рода, выход i-ro сумматора в блоке преобразования первого рода, выход i-ro сумматора первой группы и i-ro вычитателя третьей группы в каждом блоке преобразования второго рода, а также выход i-ro сумматора первой группы в каждом суммирующем блоке 1-го яруса, кроме (п-1)-го яруса, подкл ючены к первым входам i-x (i ) или к вторым входам (i - 2 )-х (i 2 ) сумматоров первой группы соответствующих суммирующих блоков ()-ro яруса, причем выходы сумматоров д.р-го суммирующего блока 1-го яруса соединены с входами сумматоров ДД.П -го суммирующего блока (I + 1)-го яруса, выход i-ro вычитателя третьей группы в блоке преобразования первого рода, выходы i-ro вычитателя четвертой группы и i-ro сумматора второй группы в каждом блоке преобразования второго рода, а также выход i-ro сумматора второй группы в каждом суммирующем блоке 1-го яруса, кроме- (п-1)-го яруса, подключены к первым входам i-x (i - 2 ) или к вторым входам (i-2 )-х (i 2 ) сумматоров второй группы соответствующих блоков (Г+1)-го яруса, выходы i-x суммато-т ров первой и второй групп каждого суь№шрующего блока -го яруса, кроме jU. g-го суммирующего блока и кроме суммирующих блоков (п-1)-го яруса, подключены к суммирующим входам i-x (i i или вычитающим входам (i - (i ) вычитателей соответственно первой и второй групп в соответствующем блоке преобразования второго рода (1+1)-го яруса, выходы i-x сумматоров первой и второй групп g-ro суммирующего блока i-ro яруса, кроме (п-1)-го яруса, подключены к суммирующим входам i-x (i ) или вычитающим входам (i - )-х (i ) вычитателей соответственно первой и второй групп блока преобразования первого ряда ()-го яруса.

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

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

Наиболее близким техническим решением к изобретению является -устройст-J5 по во для выполнения преобразования Фурье, содержащее блоки преобразова ния первого рода и суммирующие блок сгруппированные в п ярусах (2 число входных отсчетов, определяюще размерность преобразования), причем выходы каждого блока преобразования первого рода и суммирующего блока предыдущего яруса соединены с входам соответствующего блока преобразования первого рода и суммирующего блока последующего яруса, входы бло ков первого яруса являются входами устройства, а выходы блоков последнего яруса являются выходами устрой ства 2 . Недостатком известных устройств является их сложность. Целью изобретения является упрощ ние устройства для выполнения преобразования Фурье. Поставленная цель достигается тем, что в устройство для выполнен11я преобразования Фурье, содержащее блоки преобразования первого рода и суммирующие блоки, сгруппированные в п ярусах (2 -размерность преобразо вания Фурье), причем каждый из блоков пр-еобразования первого рода и суммирующих блоков 1-го (I 0,1,.. п-1) яруса имеет 2 входов и выходов jH 2 входы блока преобразования первого рода первого яруса являются входами устройства и соединены с одноименными входами суммирую щего блока первого яруса, выходы всех блоков (п-1)-го яруса являются выходами устройства, введены блоки преобразования второго рода, причем на t-M ярусе содержится один блок преобразования первого рода, jit,g суммирующих блоков (f( 2/U()2 + 1,-2 1/2, fXM 1) блоков преобразования второго рода.

1084807

каждый суммирующий блок t-ro яруса

- Р- 1

содержит две группы по 2 сумматоров , причем входы i-ro (i 1 - 2 ) сумматора первой группы являются входами действительных составляющих по i-му и (2 + i-му входам соответствующего суммирующего блока, входы i-ro сумматора второй группы являются входами мнимых со- ставляющих по i-му и ( + i)-My входам соответствующего суммирующего блока, выходы i-x сумматоров первой и второй групп являются выходами действительной и мнимой составляющих i-му выходу соответствующего суммирующего блока, каждый блок преобразования первого рода 1-го яруса содержит 2 . сумматоров, три группы по 2 вычитателей и четыре группы по 2 элементов взвешивания , причем суммирующие входы 1-х вычитателей первой и второй групп являются соответственно входами действительной и мнимой составлякщих по i-му входу соответствующего блока преобразования первого рода, вычитающие входы i-x вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по (2 + i)-My входу соответствующего блока преобразования первого рода, выход i-ro вычитателя первой группы через i-й элемент взвещивания первой группы и через i-й элемент взвешивания второй группы подключен соответственно к первому входу i-ro сумматора и суммирующему входу i-ro вычитателя третьей группы в соответствующем блоке преобразования первого рода, выход i-ro вычитателя второй группы через i-й элемент взвещивания третьей группы и через i-й элемент взвешивания четвертой группы подключен соответственно к вычитающему входу i-ro вычитателя третьей группы и к второму входу i-ro сумматора в соответствующем блоке преобразования первого рода, выход i-rq сумматора и выход i-ro вычитателя третьей группы являются выходами действительной и мнимой составляющих по i-му выходу соответствующего блока преобразования первого рода, каждый из блоков преобразования второго рода -го яруса имеет две группы по 2 выходов и содержит две группы по 2 сумматоров, четыре группы по 2 вычитателей и четыре группы по 2 элементов взвешивания, причем суммирующие входы i-x вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по i-му входу соответствующего блока преобразования второго рода, вычитающие входы i-x вычитателей первой и второй групп являются соответственно входами действительно и мнимой составляющих по (2 + i)му входу соответствующего блока преобразования второго рода, выход i-ro вычитателя первой группы через i-й элемент взвешивания первой группы подключен к neffboMy входу i-ro сумматора первой группы и к суммирующему входу 1-го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход i-ro вычитателя первой группы через 1-й элемент взвешивания второй группы подключен к первому входу i-ro сумматора второй группы и к суммирующему входу i-ro вычитателя четвертой группы в соответствующем блоке преобразования второго рода, выход i-ro вычитателя второй группы через i-й элемент взвешивания третье группы подключен к второму входу Д-го сумматора второй группы и к вычитающему входу i-ro вычитателя четвертой группы в соответствующем блок преобразования второго рода, выход i-ro вычитателя второй группы через i-й элемент взвешивания четвертой группы подключен к второму входу i-ro сумматора .первой группы и к вычитающему входу i-ro вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход i-ro сумматора первой группы и выход i-ro вычитателя четвертой группы являются выходами действительной и мнимой составляющих по i-му выходу первой группы, а выход i-ro вычитателя третьей группы и выход i-ro сумматора, второй группы являются выходами действительной и мнимой составляющих по i-му выходу второй группы соответствующего блока преобразования второго рода, выход i-ro сумматора в блоке преобразования первого рода, выходы i-ro сумматора первой группы и i-ro вычитателя третьей группы в каждом блоке преобразования второго рода, а также выход i-ro сумматора первой группы в каждом суммирующем блоке 1-го яруса, кроме (п-1)-го яруса, подключены к первым

входам i-x (i ) или к вторым входам (i - )-х и d 2 - сумматоров первой группы соответствующих суммирующих блоков (1+1)-го яруса, причем выходы сумматоров ju.p-ro суъц ирукндего блока 1-го яруса соединены с входами сумматоров fjLp -го суммирующего блока (1+1)-го яруса, выход i-ro вычитателя- третьей группы в блоке преобразования первого рода, выходы i-ro вычитателя четвертой группы и i-ro сумматора второй группы в каждом блоке преобразования второго рода, а также выход i-ro сумматора второй группы в каждом суммирующем блоке -го яруса, .кроме (n-l)-ro яруса подключены к первым входам i-x (i $ ) или к вторым входам (i - 2 )-х (i ) сумматоров второй группы соответствующих суммирующих блоков (1+1)-го яруса, выходы i-x сумматоров первой и второй групп каждого сум-ирующего блока -го яруса, кроме суммирукицего блока и кроме суммирующих блоков (п-1)-го яруса, подключены к суммирующим входам i-x (i ) или вычитающим входам (i-2 )-x(i 2 ) вычитателей соответственно первой и второй групп в соответствующем блоке преобразования второго рода (1+1)-го яруса, выходы i-x сумматоров первой и второй групп р-го суммирующего блока 1-го яруса, кроме (n-l)-ro яруса, подключены к суммирующим входам i-x (i 2 ) или вычитающим входам (i - (i ) вычитателей соответственно первой 0 и второй групп Слока преобразования первого рода (1+1)-го яруса.

На фиг. 1 дана функциональная схема устройства для выполнения преобразования Фурье; на фиг. 2 - схема 5 блока преобразования первого родана фиг. 3 - схема суммирующего блока; на фиг. 4 - схема блока преобразования второго рода.

Устройство содержит блоки 1 преоб0 разования первого рода, суммирующие блоки 2, блоки 3 преобразования второго рода, группы 4 элементов взвешивания, сумматоры 5 и вычитатели 6.

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

Пусть через Х(о),...,X(i),..., Х(2-1), (О i ; ) обозначается последовательность значений из 2 комплексных функций (сигналов), над которыми требуется произвести преобразование Фурье. И пу.(т уерез Z(o) , Z(k), Z() (О v k 4 ) обозначается последовательность значений из 2 комплексньш функций (сигналов), получающихся в результате преобразования Фурье данных значений функций X(i), i 0,1,...,, Тогда соотношение, описьшающее дискретное преобразование Фурье (ДПФ) сигналов X(i) (i 0,1,...,), следующееt ,/ t 1 2 1 J Z() :Z X(i)e , 0,«. гЯ . (1) Вторая половина из 2 коэффициентов Фурье легко получается в результате следующих тривиальных преобразований вида Z(2 - k) Z(k), где Z(k) - k-й комплексный коэффициент преобразования Фурье, являющийся комплексно-сопряженнымk Z(k); Z() - ()-й комплексный коэффициент преобразова ния Фурье. Предлагаемое устройство предназначено для вычисления не менее 10 7 первых коэффициентов Фурье, включающих диапазон 0-2 значений аргумента k функции Z(k). Преобразование для Z(2 -k) не отражено в схеме предлагаемого устройства в силу его тривиальности и не влияет на сложность конструкции. Суммирование или вычитание (в зависимости от знака экспоненциального множителя) в соответствии с вьфажением (1) осуществляется на сумматорах 5 и вычитателях 6. Умножение на весовые коэффициенты, представляющие значение экспоненциального множителя, обеспечивается элементами 4 взвешивания. Для оценки положительного эффекта сравним общее число элементов взвешивания в известном устройстве. 2°- 2 2 2 + . 2 2 и предлагаемого устройства L 2 + 2 + + 3-2 -(п+1). Получаем что указывает на существенное упрощение конструкции.

УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блоки преобразования первого рода и суммирующие блоки, сгруппированные в п ярусах

r- r- - t-T d -fIJ

фиг.