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

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

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

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

Наиболее близким к изобретению является устройство Для быстрого

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

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

15 блоков устройства С2Д.

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

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

Поставленная цель достигается

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

30 блока памяти, выход которого соеди ней с входом распределительного блока, выход которого подключен к первому входу блока умножения, выход которого является выходом устройст ва, второй вход блока умножения соединен с первым выходом блока памяти коэффициентов, второй выход которого подключен к входу задания коэффициентов арифметического блока, первый выход блока управления соединен с управляющим входом распределительного блока, второй, третий, четвертый и пятый выходы блока управления соединены с управляющим входом соответственно блока входной памяти, арифметического блока, блока памяти и блока памяти коэффициентов, введен блок выделения ненулевых элементоЕ, содержащий два элемента И элеменч, НЕ, триггер и группу элементов И, выходы которых соединены с входами блока входной памяти входы первого элемента И являются информационными входами устройства, причем выход первого элемента И подключен к входу элемента НЕ и первому входу триггера, выход элемента НЕ соединен с вторым входом триггера, выход кото рого соединен с первым входом второг элемента И, выход которого подключен к первым входам элементов И группы, вторые вхЬги которых объединены с со ответствующими входами первого элемента И, причем второй вход второго элемента И подключен к первому выходу блока управления, а выход триггера соединен с входом запуска блока синхронизации, блок синхронизации содержит генератор, шифратор, дешифратор, первый и второй счетчик адреса, выход генератора является первым выходом блока синхронизации и соединен с входами дешифратора, первого и второго счетчиков адреса и первым входом шифратора, второй вход которо го является входом запуска блока син хронизации , Ъыходы шифратора, дешифратора, первого и второго счетчиков адреса являются соответственно втopы третьим, четвертым и пятым выходами блока синхронизации. На фиг. 1 представлена блок-схема устройства} на фиг. 2 - направленный граф, реализующий процедуру вычислений для последовательности из элементов; содержащей ненулевых элементов, сдвинутых относительно начала последовательности на С 3 элемента (три-первых элемента нулевые) tUp exp(-j-i ) ; на фиг. 3 - . г функциональная схема блока выделения ненулевых элементов} на фиг. 4 функциональная схема распределительного блока} на фиг. 5 - функциональная схема блока управления. Предлагаемое устройство содержит последовательно соединенные вход устройства, блок 1 выделения ненулевых элементов, блок 2 входной памяти, арифметический блок 3, блок 4 памяти, распределительный блок 5, блок 6 умножения, выход которого является выходом устройства, а также блок 7 управления и блок 8 памяти тригонометрических коэффициентов. Блок 1 выделения ненулевых элементов содержит п-входовой элемент И 9 (п-разрядность входных отсчетов) с инверсными входами, элемент НЕ 10, триггер 11, 2-входовой элемент И 12, группу 13 из п 2-входо1вых элементов И. Распределительный блок содержит счетчик 14, дешифратор 15, матрицу 16 элементов И, группу 17 элементов ИЛИ, блок управления включает в себя задающий генератор 18, шифратор 19,-дешифратор 20, счетчик 21 адресов блока памяти и счетчика 22 адресов блока памяти тригонометрических коэффициент тов. Устройство работает следующим образом. I М ненулевых элементов последовательности {MISN, где. - длина всей последовательности, г, m - целые, больше единицы) выделяются в блоке 1 с помощью элементов 9 и 10 триггера 11, сигнал с единичного выхода которого открывает элемент 12 и поступает в блок 7 на вход шифратора 19. По управляющим сигналам с блока 7 осуществляется запись через элементы И 13 ненулевых элементов во входной блок памяти. Далее арифметический блок 3 выполняет стандартные арифметические операции (базовые операции 2-, 3- или 4точечных ДПФ в зависимости от величины основания г) сложения и умножения ненулевых элементов на тригонометрические коэффициенты, поступающие из блока 8 памяти тригонометрических коэффициентов. Арифметические операции и выдача коэффициентов из блока 8 осуществляется по управляющим сигналам, поступаюп1им на соответствующие входы блоков 3 и 8 с шифратора 19 блока 7 управления, а адреса коэффициентов определяются выходом счетчика 22 адресов блока памяти тригонометрических коэффициентов, подключенным к адресному входу блока 8. По управляющим сигналам с выходов шифратора 19 и дешифратора 20 блока 7 результаты вычислений из блока 3 записываются в блок 4 памяти по адресам, определяе1 ых выходом счетчика 21 блока 7 управления. По сигналам с дешифратора 20 блока 7 полученные данные считываются из блока 4 памяти в арифметический блок 3 для продолже :ния вычислений по алгоритму быстрого преобразования Фурье над М эле ментами. После выполнения всех вычислений М результатов из блока4 памяти подают через распределительный блок 5 на блок 6 умножени$. Каж дый i-й результат () из блока памяти подают на вход блока б умножения в течение N/M тактов периодически через М тактов. Ненулевой i-й элемент подается на блок 6 умножения через i-й столбец элементов И матрицы 16 и группу 17 элементов ИЛИ На первые входы каждого i-ro столбца элемента И подается сигнал с соответствующего i-ro выхода дешифратора 15, который появляется периодически через М тактов N/M раз. На другой вход блока б умножения по управляющим сигналгил с блока 7 управления подаются соответствующие фазовые коэффициенты из блока 8 памяти тригонометрических коэффициентов, значения которых определяются числом {N-MiiC7/0) начальных нулевых элементов входной последователь ности данных., а адреса определяются содержимым счетчика 22 блока 7 управления. Реализуемое устройством преобразование последовательности данных вида Х(,Со,о,-ч О.У-с..-Ч4-м-.°°- содержащей Т нулевых начальных элементов (N-M7/t O), М ненулевых элеме тов и N-T-M конечных нулевых элемен тов (при , q, m - целых и больших единицы), определяется следующим соотношением ..). И где .3 - вектор размером М-1, определяющий М ненулевых элементов пбследовательности Хо I . Y 0 .0, ,Ci. . ,С 3 -вектор коэффициентов Фурье; ,1,1 , . . . 13 - вектор из N/M единиц; I j - единичная матрица порядка М X - символ кронекеровского произведения матриц; ) (, . .giDy.© ) - ди агональная матрица (порядка N) .. фазовых множителей; - К - значение i-ro (ieO m-1) разряда при представлении Т в г-йчной системе счисления; Oj. -dlag(u;;.,..., .. tWr -exp(-J /г); Wt Irg-i®EK«Tj:слабозаполненные матрицы поряд ка М, содержащие только rtN нену , левых элементов; Е - матрица дискретных экспоненциальных функций порядка г. Рассмотрим более подробно, каким образом новые признаки позволяют повысить быстродействие устройства по сравнению с известными техническими решениями. Так как во входной блок памяти записыЬаются не все N элементов входной последовательности, а только М ненулевых элементов (), то время формирования адресов и время записи считывания данных в этот блок сократится по сравнению с образцом в N/M раз. Далее, поскольку вычисление коэффициентов Фурье в арифметическом блоке производится только от М нулевых элементов, то количество в алгоритме БПФ сократится в m/g раз (при Nsr, , m,g,г - целые, больше единицы),а количество стандартных арифметических операций (бабочек) сократится в N/M раз. Таким образом, общее сокращение времени вычислений окажется равным N%m/M,g раз. Соответственно в N,m/M-.g раз сократится и время на обмен данными между арифметическим блоком и блоком памяти при занесении в последний промежуточных результатов и коэффи11иентов Фурье после последней итерации алгоритма быстрого преобразования Фурье. Кроме того, данное устройство позволяет выполнять обработку .данных по мере их поступления по М дискрет., не ожидая накопления пол ного объема (N дискрет) исходных данных, как в аналогах, что снижает требования к быстродействию вычислительных средств или позволяет при одинаковом с аналогом быстродействии арифметического блока обрабатывать большее число дискрет за один и тот же промежуток времени. Формула изобретения 1. Устройство для быстрого преобразован : я Фурье-последовательности с нулевыми элементами, содержащее блок входной памяти, выход которого соединен с информационным в;содом , арифметического блока, вход-выход которого подключен к выходу-входу блока памяти, выход которого соединен с входом распределительного блока, выход которого подключен к первому входу блока умножения, выход которого является выходом устройства, второй вход блока умножения соединен с первым выходом блока памяти коэффициентов, второй выход которого подключен к входу задания коэффициентов арифметического блока, первый выход блока управления соединен с управляющим входом распределительного блока, второй, третий, четвертый и пятый выходы блока управления I соединены с управляющим входом соответственно блока входной памяти, арифметического блока, блока памяти и.блока памяти коэффициентов, отличающееся тем, что, с целью увеличения быстродействия, в него введен блок выделения ненулевых элементов, содержащий два элемента И, элемент НЕ, триггер и группу элементов И, выходы которых соединены с входами блока входной памяти, входы первого элемента И являются информационными входами устройства, причем выход первого элемен та И подключен к входу элемента НЕ и первому входу триггера, выход элемента НЕ соединен с вторым входом триггера, выход которого Соединен с первым входом второго элемента И, выход которого подключен к первым входам элементов И группы, вторые вх ды которых объединены с соответствую щими входами первого элемента И, причем второй вход второго элемента И подключен к первому выходу блока управления, а выход триггера соединен с входом запуска блока синхронизации. 2. Устройство по п.1, отличаю щ а е с я тем, что блок синхронизации содержит генератор, шифратор дешифратор, первый и второй счетчики адреса, выход генератора является первым выходом блока синхронизации и соединен с входом дешифратора, первого и второго счетчиков адреса и первым входом шифратора, второй вход которого является входом запуска блока синхронизации, выходы шифратора, дешифратора, первого и второго счетчика адреса являются соответственно вторым, третьим, четвертым и пятым выходами блока синхронизации. Источники информации; принятые во внимание при экспертизе 1.Авторское свидетельство СССР 509872, кл. G Об F 15/332, 1976. 2.Авторское свидетельство СССР по заявке № 2913447/18-24, кл. G 06 F 15/332 (прототип).

Фие. /

О

Ф9( С

т Со

с,

«Pi/гЛ

16

Фиг. 5

- i

-