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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Сфвз СоветскихСоциалистическихРеспублик 1 ю 1 005070(61) Дополнительное к авт. сеид-ву(22) Заявлено 14 Р 781 (21) 3317089/18-24с присоединением заявки Мо -(23) Приоритет РЦМ Кд з ю О 06 Г 15/332 Государственный комитет СССР но делам изобретений и открытийОпубликовано 150383. Бюллетень Йо 10 Дата опубликования описания 150383 О.С. Романов, Г.А. Кухарев, Л.Г. овааенкд,"фг .(54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ПОСЛЕДОВАТЕЛЬНОСТИ С НУЛЕВЫМИ ЭЛЕМЕНТАМИИзобретение относится к области цифровых вычислительных машин, конкретно к устройствам для анализа (синтеза) сложных математических функций и может быть использовано для выполнения быстрого преобразования Фурье.Известно устройство для выполнения быстрого преобразования Фурье содержащее последовательно соединенные входной блок памяти., распределительный блок, блок памяти, блок инверсной перестановки, блок умножения,.выход которого является выхот(ом устройства, а вход устройства подключен к входу входного блока памяти, а также арифметический блок соединенный с блоком памяти и блок памяти тригонометрических коэффициентов, выходы которых соединены с выходами арифметического блока. и. блока умножения 1.Недостатком данного устройства является то, что оно не обеспечивает требуемого быстродействия при выполнении преобразования фурье- последовательности с нулевыми элементами.Наиболее близким к изобретению является устройство для быстрого преобразования Фурье-последовательности с нулевыми элементами, содержащее последовательно соединенные вход устройства, входной блок памяти, распределительный блок, блок памяти, блок умножения, выход которо. го является выходом устройства, а также арифметический блок, соединенный с блокомпамяти, блок памяти тригонометрических коэффициентов, выходы которого подключены к входам блока умножения и арифметического блока, и блок синхронизации, подключейный к управляющим входам всех блоков устройства (,2).Недоставком известного устройства является то, что оно:также не обеспечивает требуемого быстродействия при вычислении быстрого преобразования фурье-последовательности с нулевыми элементами.Цель изобретения - повышение быст. родействия устройства.Поставленная цель достигается тем, что в устройство, содержащее блок входной памяти, выход которого соединен с информационным входом .арифметического блОка, вход-выход которого подключен к выходу-входу блока памяти, выход которого соедннен с входом распределительного бло ка, выход которого подключен к первому входу блока умножения, выход которого является выходом устройства, второй вход блока умножения . соединен с первым выходом блока памяти коэффициентов, второй выход которого подключен к входу задания коэффициентов арифметического блока, первый выход блока управления соединен а управляющим входом распре делительного блока, второй, третий, четвертый и пятый выходы блока управления соединены с управляющим входом соответственно блока входной памяти, арифметического блока, блока 15 памяти и блока памяти коэффициентов, введен блок выделения ненулевых эле- ментов, содержащий два элемента И, элемент НЕ, триггер и группу элементов И, выходы которых соединены с 2 О входами блока входной памяти входы первого элемента И являются информационными входами устройства, причем выход первого элемента И подключен к входу элемента НЕ и первому входу 25 триггера, выход элемента НЕ соединен с вторым входом триггера, выход которого соединен с первым входом второго элемента И, выход которого подключен к первым входам элементов И группы, вторые входы которых объединены с со ответствующими входами первого элемента И, причем второй вход второго элемента И подключен к первому выходу блока управления, а выход триггера соединен с входом запуска блокасинхронизации, блок синхронизациисодержит генератор, шифратор, дешифратор, первый и второй счетчик адреса, выход генератора является первымвыходом блока синхронизации и соеди Онен с входами дешифратора, первого ивторого счетчиков адреса и первымвходом шифратора, второй вход которого является входом запуска блока синхронизации, выходы шифратора, дешифратора, первого и второго счетчиковадреса являются соответственно вторым,третьим, четвертым и пятым выходамиблока синхронизации.50На фиг. 1 представлена блок-схемаустройства; на фиг. 2 - направленный граф, реализующий процедуру вычислений для последовательности иэ К=9 элементов содержащей М=З ненулевых 55 элементов, сдвинутых относительно начала последовательности на=3 элемента (три первых элемента нуле 2 ГС. 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 адресов блока памяти тригонометрических коэффициен.- тов.Устройство работает следующим образом.И ненулевых элементов последовательности (МИ, где.й=г - длина всей последовательности, г, в - целые, больше единицы) выделяются в блоке 1 с помощью элементов 9 и 10 триггера 11, сигнал с единичного выхода которого открывает элемент 12 и поступает в блок 7 на вход шифратора 19. По управляющим сигналам с блока 7 осуществляется запись через элементы И 13 ненулевых элементов во входной блок памяти. Далее арифметический блок 3 выполняет стандартные арифметические операции (" базовые" операции 2-, 3- или 4- точечных ДПФ в зависимости от величины основания г) сложения и умножения ненулевых элементов на тригонометрические коэффициенты, поступающие из блока 8 памяти тригонометрических коэффициентов. Арифметические операции и выдача коэффициентов из блока 8 осуществляется по управляющим сигналам, поступающим на соответствующие входы блоков 3 и 8 с шифратора 19 блока 7 управления, а адреса коэффициентов определяются выходом счетчика 22 адресов блока памяти тригонометрических коэффициентов, подключенным к адресному входу блока 8. По управляющим сигналам с выходов шифратора 19 и дешифратора 20 блока 7 результаты вычислений из блока 3 записываются в блок 4 памяти по адресам, определяемых выходом счетчика 21 блока 7 управления. По сигналам с дешифратора 20 блока 7 полученные данные считываются из блока 4 памяти в арифметический блок 3 для продолже.1005070 тгде Хо,=РСХ с+" Х с+в с.3 - векторразмером М 1, определяющий М ненулевых элементовпоследовательности ХеС=СрС 1,ССй 3 - векторкоэффициентов Фурье;1.= 11111 Г - вектор из й/Мединиц;1 й, - единичная матрица порядка М;- символ кронекеровского произведения матриц;ф(Сф 1 -(О"еО Э О,о) - диагональная матрица (порядка й)фазовых множителей;К - значение 1-го (16 О, щ)разряда при представлении Свг-ичной системе счисления;с о .-л, сО б 1 ад(ц,ау,Э к )Щ; ехР(-) /г); Чс" гдЕг 91,.- слабоэаполненные матрицы порядка М, содержащие только гй ненулевых элементов; 45 Формула изобретения 55 60 65 управляющим входом распределитель. ния вычислений по алгоритму быстрого преобразования Фурье над М элементами. После выполнения всех вычислений М результатов из блока 4памяти подают через распределительный блок 5 на блок б умножения, Каждый 1-й результат (1=1+М) из блока 4памяти подают на вход блока б умножения в течение й/М тактов периодически через М тактов. Ненулевой 1-йэлемент подается на блок 6 умножения через 1-й столбец элементов Иматрицы 16 и группу 17 элементов ИЛИ.На первые входы каждого 1-го столбца элемента И подается сигнал ссоответствующего 1-го выхода дешифратора 15, который появляется периодически через М тактов й/М раз. Надругой вход блока б умножения поуправляющим сигналам с блока 7управления подаются соответствующиефазовые коэффициенты из блока 8 памяти тригонометрических коэффициентов, значения которых определяютсячислом (й-МИ 7/О) начальных нулевых элементов входной последовательности данных., а адреса определяются содержимым счетчика 22 блока 7управления. Реализуемое устройством преобразование последовательности данных видатЯ "-(.оо" ОХ,Хс+,."к ,О,о;",бЗ содержащей с нулевых начальных элементов (й-М/10), М ненулевых элемен тов и й-Г-М конечных нулевых элементов (при й=гсе, М=гс 1; д, щ - целых и больших единицы)., определяется следующим соотношением Е 1. - матрица дискретных экспоненцйальных функций порядка г,Рассмотрим более подробно, какимобразом новые признаки позволяют повысить быстродействие устройства посравнению с известными техническимирешениями. Так как во входной блокпамяти записыЬаются не все й элементов входной последовательности, атолько М ненулевых элементов (Мй) 0 то время формирования адресов и время записи считывания данных в этотблок сократится по сравнений с образцом в й/М раз, Далее, посколькувычисление коэффициентов Фурье в 15 арифметическом блоке производитсятолько от М нулевых элементов, токоличество в алгоритме БПФ сократится в щ/д раз (при й=гфф М=Мг 9,щ,д,г - целые, больше единицы),аколичество стандартных арифметических операций (" бабочек ) сократит ся в й/М раз.Таким образом, общее сокращениевремени вычислений окажется равным р 5 йщ/М.д раз, Соответственно вй.щ/М,д раз сократится и время на об.мен данными между арифметическимблоком и блоком памяти при занесении в последний нромежуточных реЗо зультатов и коэффициентов Фурьепосле последней итерации алгоритмабыстрого преобразования Фурье.Кроме того, данное устройствопозволяет выполнять обработку .данных по мере их поступления по Мдискрет, не ожидая накопления полного объема (й дискрет) исходныхданных, как в аналогах, что снижает требования к быстродействиювычислительных средств или позво ляет при одинаковом с аналогом быстродействии арифметического блока обрабатывать большее число дискрет за.один и тот же промежуток времени. 1. Устройство для быстрого преобразования Фурье-.последовательности с нулевыми элементами, содержащееблок входной памяти, выход которогосоединен с информационным входом арифметического блока, вход-выходкоторого подключен к выходу-входублока памяти, выход которого соединен с входом распределительного блока, выход которого подключен к первому входу блока умножения, выход которого является выходом устройства,второй вход блока умножения соединен с первым выходом блока памятикоэффициентов, второй выход которогоподключен к входу задания коэффициентов арифметического блока, первыйвыход блока управления соединен сного блока, второй, третий, четвертый и пятый выходы блока управления,соединены с управляющим входом соответственно блока входной памяти,арифметическогв блока, блока памятии блока памяти коэффициентов, о тл в ч а ю щ е е с я тем, что, сцелью увеличения быстродействия,в него введен блок выделения иену"левых элементов, содержащий два элемента И, элемент НЕ, триггер и группу. элементов И, выходы которых соединены с входами блока входной памяти, входы первого элемента И являются информационными входами устройства, причем выход первого элемен та И подключен к входу элемента НЕи первому входу триггера, выход элемента НЕ соединен с вторым входомтриггера, выход которого сбединен спервым входом второго элемента И 20выход которого подключен к первымвходам элементов И группы, вторые вхо 1дя которых объединены с соответствую-.щими входами первого элемента И,причем второй вход второго элемента 25И подключен к первому выходу блока управления, а выход триггера соединен с входом запуска блока синхронизации.2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок синХронизации содержит генератор, шифратор, дешифратор, первый и второй счетчики адреса, выход генератора является первым выходом блока синхронизации и соединен с входом дешифратора, первого и второго счетчиков адреса и первым входом шифратора, второй вход которого является входом запуска блока синхронизации, выходы шифратора, дешифратора, первого и второго счетчика адреса являются соответственно вторым, третьим, четвертым и пятым выходами блока синхронизации.Источники информации(принятые во внимание при экспертизе1. Авторское свидетельство СССРР 509872, кл. С 06 Г 15/332, 1976.2, Авторское свидетельство СССРпо заявке Ф 2913447/18-24,кл. С 06 Г 15/332 (прототип).11605070 иг,Составитель А. БараноВолощук Техред М.Тепер Корректор Е.Рош ак одписное а 4/5 илиал ППП "Патент", г. Ужгород,01/65 Тираж 704ВНИИПИ ГосударствЕнного комитета ССпо делам иэобретений и открытий3035, Москва, Ж, Раушская наб.,