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

(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ N -ТОЧЕЧНОГО ПРЕОБРАЗШАНИЯ ФУРЬЕ

Изобретение относится к автоматике . и вычислительной технике и может быть исшльзовано в системах цифровой обработки сигналов. Известно устройство для вычисления дискретного преобразования Фурье, содер жащее блок памяти с произвольным обра щением и централизованный процессор, подключенньгй к соответствующим ячейкам блока памяти 1| . . Недостаток известного устройства дазкое быстродействие. Наиболее близким техническим решением к данному изобретению является устройство для вычисления дискретного пр еобразования Фурье, содержащее анало го-цифровой преобразователь блоков регистров сдвига, тактс)вый генератор арифметических блоков, и постоянное запоминающее устройство, причем первый блок регистров сдвшпа со стоит ИЗ одного регистра емкостью 4 чи сел, второй - из двух регистров емкостью W/2 чисел и т.д. . Последний блок состоит из Д регистров, по одному числу каждый. Входы арифметических блоков соединещл с входами и выходами со«. ответствуюших блоков регистров сдвига и с выходом постоянного запоминакяцего устройства. Такая структура позволяет повысить быстродействие вычислителя, поскольку в данном случае в интервале времени между двумя, последними отсчетами наиболее загруженное арифметическое устройство, подключенное к последнему блоку регистров, выполняет N/4 операций над комплексными числами. Однако, это устройство отличается большой сложностью. Цель изобретения - .упрощение устройства. Ыель достигается тем, что устройство для вычис щния N -точечного преобразования Фурье, содержащее аналого-цифровой преобразователь, к синхронизирующему входу которого подключен выход первого тактового генератора, арифметический блок, блок памяти, адресный вход котороГО подключен к адресному выходу блока управлениями четыре блока регистров, содержит блок буферных регистров, второй Тактовый генератор и коммутатор, причем выход аналого-цифрового преобразователя подключен к информационному входу блока буферных регистров, синхронизирующий вход которого подключен к первому выходу синхро шзации .коммутатора, а выход - к первому информационному ВХОДУ коммутатора, сишфонизирующий вход первого и второго блока регистров подключен ко второму входу сигофонизации KOMwIyraTopa, информационный вход первого блока регистров подключен к первому информационному выходу коммутатора, а выход - ко второму информационному входу коммутатора и к информационному входу второго блока регистров, выход второго блока регистрсв подключен к третьему информационному входу коммутатора, синхронизирующий вход третьего и четвертого блока регистров подключен к третьему синхронизирующему выходу коммутатора, информационный вхо третьего блока регистров - ко второму информационному выходу коммутатора, а выход - к четвертому информационному входу коммутатора и к информационному входу четвертого блока регистров, выход четвертого блока решстров подключен к пятому И1фэрмационному входу коммутатора, первый вход синхронизации коммутатора подключен к выходу первого тактового генератора, второй и третий входы синхронизации коммутатора подключены к выходам сиюфонизации блока утьравления, четвертый вход синхронизации коммутатора подключен к выходу второго тактового генератора, первый, второй и третий входы арифметического блока под ключены соответственно к выходу блока памяти, третьему и четвертому информационным выходам коммутатора, выход результата арифметического блока - к ш стому ии|юрмациоЕШЮму входу коммутато ра, а управляющий выход - к сигнальному ВХОДУ блока управления, выход управ ления коммутации блока управления подключен к управляющему входу коммутатора. На чертеже представлена схема УС1 ройства для вычисления Н -точечного преобразО вашш Фурье. Устройство содержит ааалого-црфрофой преобразователь 1, первый тактовый генератор 2, блок буферных регистров 3 емкостью М чисел, имеющий синхронизирующий 4 и информационный 5 входы и выход 6, первый 7, второй 8, третий 9 и четвертый 10 блоки регистров емкостью по Ы /2 чисел каждый с соответствутаШими синхронизирующими 11-14 и информационными 15-18 входами и выходами 19-22, коммутатор 23, имеющий шесть информационных входов 24-29 и четыре входа синхронизации 30-33, а также четыре И1фэрмационных выхода 34-37, три выхода синхронизации 38-40 и управляюгйий вход 41, второй тактовый генератор 42, блок утхравления 43, снабженный сигнальным входом 44, а также выходами сиюфонизации 45,46 и адресными выходами 47 и выходом управления коммутациями 48, арифметический блок 49, имеющий входы операндов 5О-52, выход результата 53 и управляющий выход 54, блок памяти 55 в виде постоянного запоминающего устройства с адресным входом 5 6 к выходом 57. Устройство работает следующим образом. Входной аналоговый сигнал поступает на вход аналого-цифрового преобразователя 1 и преобразуется в последовательность цифровых отсчетов, формирующихся с частотой первого тактов /го генератора 2 . На первом этапе блок управления 43 формирует на своем управляющем выходе 48 первый код, который, поступая на управляющий вход 41 коммутатора 23, определяет соединение входа синхронизации 30 последнего с выходом синхронизации 38 . Остальные цепи коммутатора при этом разорваны. В результате синхронизирующий вход 4 блока буферных регистров 3 оказывается подключенным к выходу первого тактового генератора 2 и последовательность цифровых отсчетов загружается через информационный вход 5 в блок буферных решстров с частотой аналого-цифрового преобразования. После того, как все М ячеек блока буферных регистров оказываются заполненными отсчетами входной реализации, наступает второй этап работы устройства, ще устройство управления генертрует на выходе 48 второй код. Вследствие этого блок буферных регистров и первый и второй блоки решстров оказываются соециненнымЕ последовательно по -выходам и информационным входам, а их синхронизирующие входы - подключёнными к выходу BTOpoix) тактового генератора 42, частота которого подобрана так, чтобы в интервале между последним отсчетом данной и первым отсчетом последующей реализаций содержимое (N отсчетов) блока буферных рег-истров переписа лось в первый и второй блоки регистров, имеющие емкость по N /2 отсчетов. На следующем этапе устанавшшается третий режим работьц Блок управления генерирует на своем выходе 48 третий код, что определяет подключение первого тактового генератора 2 к синхронизирующему входу 4 блока буферных регистров, после чего последний готов к нриему следуюшей реализации входного сигнала. При этом выходы 19, 20 последних ячеек первого и второго блоков регистров оказываются подключенными к входам операндов 51, 52 арифметического блока 49. Блок управления формирует на выходе сишфонизахии 45 два импульса, которые подаются через коммутатор 23 на синхронизирующие входы 11,12 первого и второго блоков регистров и обеспечивают последовательйую пересылку отсчетов с номерами 1,2 на вход операнда 51, а отсчетов с номерами Vi/2 -l,N/2 +2 на вход операнда 5 2 арифметического блока 49. При этгом отсчеты с номерами 1,2 представляются как действительная и мнимая части комплексного отсчета К. , а отсчеты с номерами Ц/1 +1 и N/2 4-2 как действительная и мнимая части комплексного отсчета X. - +1. На адресном выходе 47 блока управления формируется код адреса, который, поступая на адресный вход 56 постоянного запомина ющего устройства 55, определяет появление на выходе 57 значения первого вектора поворота W. Это значение поступает на вход операнда 5 О арифметического блока, которое, выполнив необходимые действия, последовательно выдает на выход результата 53 действительные и мнимые части результатов вычислений .. /, Одновременно с вьщачей каждого из этих чисел арифметический блок вырабатывает на своем управляющем выходе 54 сипшлы, поступающие на сигнальный вход 44 блока управления. Синхронное этими сигналами блок управления с необходимой задержкой вырабатывает на своем выходе синхронизении 46 импульсы для сдвигв в регистрах третьего и четвертого блоков регистров, поступающие на их обьеднневные синхронизирукицие входы 13, 14. Поскольку при этом ииформшшонный вход 17 третьего блока решстров подключен, через коммутатор к выходу результата 53 арифметического блока, дейстнтельные и мнимые части чисел Z,; последово тельно загружают в третий блок регист , ров с частотой появления результатов на выходе арифметического блока. Кроме того, при появлении сигналов на сигнальном входе 44 блока управления 11роисходит формирование на его выходе синхронизации 45 двух импульсов для сдвигов в регистрах первого и второго блоков регисть. ров. Эти импульсы подаются через комму Р 23 на синхронизирующие входы 11, 12 первого и второго блока регистров, обеспечивает последовательную пере- сылку очередной пары отсчетов из первого блока реп1стров на вход операнда 5 л очередной пары отсчетов из второго блока регистроь - на вход операнда 52. Описанная процедура повторяется - раз, пока не произойдет заполнение третьего и последсвательнс соединенного с ним eTw блоков регистров и очистка первого и второго блоков репютров. Существенно, что числа 1 , Z,.,. при этом располагаются в третьем и четвертом блоках регистров таким образом, что | их ячейках, имеющих одинаковые номера, пары операндов размещаются в последе вательности, необходимой для вычисления следующего этапа а 1« ритма быстрого преобразования Фурье, рри котором устанавливается четвертый режим работы устройстВ этом режиме блок управления 43 формирует на управляющем выходе 48 четвертый код, который, поступая на вход 41 коммутатора,обеспечивает необходимую перекоммутацию блоков. Вследствие такой перекоммутации выходы 21 и 22 последних ячеек третьего и четвертого блоков регистров, в которых содержатся числа /(/(Д +1 оказываются подключенными к входам операндов 51 и 52 арифметического блока. Эти числа, поступая в ариф- « ческий блок совместно со значением. Р поворота Л/ .являются операн вычисления величин tl v -7 -W 7 -f-l 4 г I г 4 и S которые последовательно записываются в первый блок регистров по информацио1шому ходу 15. При этом блок управле1гая 43, пригшмая по своему сипшльному входу 44 импульсы, вырабатывает импульсы для первого и второго блоков регистррв сдвига для первого и второго блоков регистров - CHHXpoiTHO с появлением каждого из Ч1гоел , У„ , а на выходе син хронизации 46, связанном с синхронизи:ру1оШ;ймйвходами третьего и четвертого блоков регистров 9, 10 - при появлении числа VT. Вследствие этого, после эа писи чисел У последовательно в первый блок регистров, его входная ячейка освобо(ждается для приема нового значения Уг , а в выходные ячейки третьего и четвертого блоков регистров сйШгаются опёравдь для вычисления этого значения. Одновременно на адресном выходе 47 блока управления формируется код адреса для выборки из постояиного запоминающего устройства 55 значения вектора поворота . которы подается на вход операнда 50 арифметйчесуого блока. Описанная процедура продолжается до заполне1шя первого и послёд75ватепьно соёдаёв)аного с ним второго блоков регистров и очистки третьего и четвертого блоков реластров. Затем блок управления вновь переводит все блоки на третий режим работы, а первый и второй блоки решстров снова меняются ролями третьим и чет ерты1у1 блоками. После (1 Н ) - 1 смен третьего и четвертого режимов в первом и втором блоках регистров содержатся значения коэффициентов Фурье, Предлагаемое устройство значительно проще известного, поскольку требует меныиего числа арифметических блоков и суммарной информационной емкости блоков ретестров,, Формула изобрё т е н и я Устройство для вычисления N -точечного преобразования Фурье, содер(жащее аналого-цифровой преобр(а ЗО8а 1ель, зЧюнизируютему входу которохЧ) подключен выход первого тшгтового генератора, арифметический блок, блок памяти, адресный вхс которохю подключён fc адрес ному выходу блока упраЫюния и четыре блока peittcTfpo, о т и и Ч а ю щ ёе с я тем, что, с цель упрошення устьройства, оно содержит блок буферных регистров, второй тактовый генератор и коммутатор, причём выход аналого-цифрового преобразователя подключен к информационному входу блока буферных регистров, синзсронизирующий вход которого подключен к первому выходу синхронизации коммутатор1а, а выход - к первому информационному входу коммутатора, синхронизирующий вход первого и второго блока ретестров тодключен ко второму выходу синхронизации коммутатора, информационный вход первого блока регистров подклю. чен к первому И1 ормац ионному выходу коммутатора, а выход - ко второму информационному входу коммутатора и к инфор-мтионному входу второго блока регистров, вьхход второго блока регистров подкшочен к третьему информационному вхо дУ коммутатора, синхронизирующий вход третьего и четвертого блока регистров подключен к третьему синхронизирующему выходу коммутатора, информщ ионный вход третьего блока регестров - ко второму и формационному выходу коммутатора, в . ход - к челвертому информйционному входу коммутатора и к информационному вхо-. ду четвертого блока регистров, вь1ход чети вертого блока регистров подключен к пятому информационному входу коммутатора. первый ккод синхронизации коммутатора подключен к выходу первого тактового гэ- нератора, второй и третий входы синхронизадии Коммутатора дадключены к выходам сиюфонизацин блока управления, четвертый вход синхрони:зации коммутатора подключён к выходу второго тактового генератора, первый, второй и третий входы арифметического блока подключеша ссхэтветствешр к выходу блоШ: naistera, TifreirtieJviy и четвертому ннфо|)йациошым выходам коммутатора, выход результата арифметического блока к шестому информтионному входу коммутатора, а управляющий выход - к сигнальному входу блока управления, выход управления коммутации блока у1фавлёния подключен к управляющему коммутатх)Источники информации, тфйнйтые во внимание vpz экспертизе 1,Акцептованная заявка Великобритаййи М 1330471, кл. Q 4 А, 1971. 2,Патент США 6 3816729, кл. 235-156, 1974 (тфототин).