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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Социалистических

Республик (i>3 005070 (61) Дополнительное к авт. сеид-ву(22) Заявлено 140781 (21) 3317089/18-24 с присоединением заявки ¹â€” (23) Приоритет - (зим.кл.

6 06 Г 15/332

Государственный комитет

СССР но делам изобретений и открытий ($3) УДК681. 32 (088.8) Опубликовано 150383. Бюллетень №10

Дата опубликования описания 150383

О.С. Романов, Г.A. Кухарев, Л.Г. овааенкд, - - - Ь - = (72) Авторы (54) УСТРОЙСТВО. ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ПОСЛЕДОВАТЕЛЬНОСТИ

С НУЛЕВЫМИ ЭЛЕМЕНТАМИ

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

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

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

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

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

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

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

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

1005070 нен с входом распределительного бло ка, выход которого подключен к первому входу блока умножения, выход которого является выходом устройства, второй вход блока умножения . соединен с первым выходом блока памяти коэффициентов, второй выход которого подключен к входу задания коэффициентов арифметического блока, первый выход блока управления соединен а управляющим входом распре- 10 делительного блока, второй, третий, четвертый и пятый выходы блока управления соединены с управляющим входом соответственно блока входной памяти, арифметического блока, блока t5 памяти и блока памяти коэффициентов, введен блок выделения ненулевых эле- ментов, содержащий два элемента И, элемент НЕ, триггер и группу элементов И, выходы которых соединены с входами блока входной памяти входы первого элемента И являются информационными входами устройства, причем выход первого элемента И подключен к входу элемента НЕ 25 триггера, выход элемента НЕ соединен с вторым входом триггера, выход которого соединен с первым входом второго элемента И, выход которого подключен к первым входам элементов И группы, вторые входы которых объединены с со. ответствующими входами первого элемента И, причем второй вход второго элемента И подключен к первому выходу блока управления, а выход триггера соединен с входом запуска блока синхронизации, блок синхронизации содержит генератор, шифратор, дешифратор, первый и второй счетчик адреса, выход генератора является первым выходом блока синхронизации и соеди- 4О нен с входами дешифратора, первого и второго счетчиков адреса и первым входом шифратора, второй вход которого является входом запуска блока синхронизации, выходы шифратора, дешиф- 45 ратора, первого и второго счетчиков адреса являются соответственно вторым, третьим, четвертым и пятым выходами блока синхронизации.

На фиг. 1 представлена блок-схема устройства; на фиг. 2 — направленный граф, реализующий процедуру вычислений для последовательности иэ N=9 элементов содержащей M=3 ненулевых 55 элементов, сдвинутых относительно начала последовательности на =3 элемента (три первых элемента нуле211 . вые); 00 =exp(-j — ); на фиг. 3

° г . Ф

- 60 функциональная схема блока выделения ненулевых элементов; на фиг. 4 функциональная схема распределительного блока; на фиг. 5 — функциональная схема блока управЛения.

- 65

Предлагаемое устройство содержит последовательно соединенные вход уст. ройства, блок 1 выделения ненулевых элементов, блок 2 входной памяти, арифметический блок 3, блок 4 памяти, распределительный блок 5, блок 6 умножения, выход которого является выходом устройства, а также блок 7 управления и блок 8 памяти тригонометрических коэффициентов. Блок 1 выделения ненулевых элементов содержит и-входовой элемент И 9 (и-разрядность входных отсчетов) с инверсными входами, элемент НЕ 10, триггер 11, 2-входовой элемент И 12, группу 13 из и 2-входовых элементов И. Распределительный блок содержит счетчик 14, дешифратор 15, матрицу 16 элементов И, группу 17 элементов ИЛИ, блок управления включает в себя задающий генератор 18, шифратор 19, дешифратор 20, счетчик 21 адресов блока памяти и счетчика 22 адресов блока памяти тригонометрических коэффициен.тов.

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

И ненулевых элементов последовательности (М И, где.N=r — длина всей последовательности, r, m — целые, больше единицы) выделяются в блоке 1 с помощью элементов 9 и 10 триггера 11, сигнал с единичного выхода которого открывает элемент 12 и поступает в блок 7 на вход шифратора 19. По управляющим сигналам с блока 7 осуществляется запись через элементы И 13 ненулевых элементов во входной блок памяти. Далее арифметический блок 3 выполняет стандартные арифметические операции (" базовые" операции 2-, 3- или 4точечных ДПФ в зависимости от величины основания r) сложения и умножения ненулевых элементов на тригонометрические коэффициенты, поступающие из блока 8 памяти тригонометрических коэффициентов. Арифметические операции и выдача коэффициентов из блока 8 осуществляется по управляющим сигналам, поступающим на соответствующие входы блоков 3 и 8 с шифратора 19 блока 7 управления, а адреса коэффициентов определяются выходом счетчика 22 адресов блока памяти тригонометрических коэффициентов, подключенным к адресному входу блока 8. По управляющим сигналам с выходов шифратора 19 и дешифратора 20 блока 7 результаты вычислений из блока 3 записываются в блок 4 памяти по адресам, определяемых выходом счетчика 21 блока 7 управления. По сигналам с дешифратора 20 блока 7 полученные данные считываются из блока 4 памяти в арифметический блок 3 для продолже1005070

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

60. ния вычислений по алгоритму быстрого преобразования Фурье над М эле-. ментами. После выполнения всех вычислений М результатов из блока 4 памяти подают через распределительный блок 5 на блок 6 умножения. Каждый i-й результат (1=1+M) из блока 4 памяти подают на вход блока.6 умножения в течение N/М тактов периодически через М тактов. Ненулевой i-й элемент подается на блок 6 умножения через i-й столбец элементов И матрицы 16 и группу 17 элементов ИЛИ.

На первые входы каждого i-го столбца элемента И подается сигнал с соответствующего i-го выхода дешифратора 15, который появляется периодически через М тактов й/М раз. На другой вход блока 6 умножения по управляющим сигналам с блока 7 управления подаются соответствующие фазовые коэффициенты из блока 8 памяти тригонометрических коэффициентов, значения которых определяются числом (й-М1с 17/О) начальных нулевых элементов входной последовательности данных., а адреса определяются содержимым счетчика 22 блока 7 управления. с

Реализуемое устройством преобразование последовательности данных вида т

Х вЂ” (0,0, "> О,Х-р Х-р.,." Х. . м О,о,.",0) содержащей Ф нулевых начальных элементов (N-М / ЪО), М ненулевых элемен тов и М- Г-M конечных нулевых элементов (при и г"", М=гс1 ; с1, m — целых и больших единицы)., определяется следующим соотношением т где Х -Pt„X<+< --xz+м л.3 - вектор размером И 1, определяющий И ненулевых элементов последовательноi

С = Сф (е1 С < СМ, ) . — вектор коэффициентов Фурье;

1.= p,1,-1,...11г - вектор из й/М единиц;

1 — единичная матрица порядка И;

- символ кронекеровского произведения матриц; фй -(n " Е...®Оф- Э 0 ) - диагональная матрица (порядка й) фазовых множителей;

K - значение 1-ro (1ß О, m-1) разряда при представлении в г-ичной системе счисления; с о =цс

0„° «1 1 а9 (а„, а,,..., );

Щ exp(-) г /r); W J rg-19Е„91, слабоэаполненные матрицы порядка М, содержащие только г и ненулевых элементов;

Š— матрица дискретных экспоненцйальных функций порядка r.

Рассмотрим более подробно, каким образом новые признаки позволяют повысить быстродействие устройства rio сравнению с известными техническими решениями. Так как во входной блок памяти записываются не все N элементов входной последовательности, а только М ненулевых элементов (И<М), то время формирования адресов и время записи считывания данных в этот блок сократится по сравнению с образцом в N/M раз. Далее. поскольку вычисление коэффициентов Фурье в

15 арифметическом блоке производится только от И нулевых элементов, то количество в алгоритме БПФ сократится в m/g раз (при N=r1r, М=Мгт, m,g,r — целые, больше единицы),а количество стандартных арифметических операций (" бабочек" ) сократит ся в й/И раз.

Таким образом, общее сокращение времени вычислений окажется равным р5 М т/Иц раз. Соответственно в

N.m/M,g раз сократится и время на обмен данными между арифметическим блоком и блоком памяти при занесении в последний нромежуточных реЗО . зультатов и коэффициентов Фурье после последней итерации алгоритма быстрого преобразования Фурье.

Кроме того, данное устройство позволяет выполнять обработку .данных по мере их поступления по М дискрет, не ожидая накопления полного объема (М дискрет) исходных данных, как в аналогах, что снижает требования к быстродействию вычислительных средств или позво4 ляет при одинаковом с аналогом быстродействии арифметического блока обрабатывать большее число дискрет за .один и тот же промежуток времени.

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

Я управляющим входом распределитель1005070

С

Со

С

Хо

О °

Хв

Св

О

Св ного блока, второй, третий, четвертый и пятый выходы блока управления

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

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

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

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

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

9 509872, кл. G 06 F 15/332, 1976.

2. Авторское свидетельство СССР по заявке 9 2913447/18-24, кл. G 06 F 15/332 (прототип).

1005070

1G05070

Фиг,5

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

Редактор К. Волощук Техред N,Tåïåð

Корректор Е.Рошко

Подписное

Филиал ППП "Патент", r. Ужгород, Закаэ 1901/65 Тираж 704

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

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