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

) 0 51)5 (3 06 Р 15/3 ТТИЯМ ЬСТВУ ОСУДДРСТВЕННЫй НОМ ИЗОБРЕТЕНИЯМ И ОТН И ГКНТ СССР(56) Рабинер Л., Гоулд Б. Теория и ;применение цифровой обработки сигналов. М.: Мир, 1978.Авторское свидетельство СССР ,9 723582, кл. С 06 Р 15/332, 1978. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТ:РОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычисли тельной технике и может быть исполь зовано в системах цифровой обработки сигналов. Цель изобретения - уп" рощение устройства. Поставленная цель достигается за счет того, чтосостав устройства входят входной оммутатор 2, ариАметический блок 3, коммутатор 4 операндов, блоки 5-10,. блок 11 постоянной памяти, элементы И 12, счетчик 13, сдвиговый регистр 14, счетчик 15 итераций, блок ".16 постоянной памяти, коммутаторы 17.1-17,6, элементы НЕ 20, 21, элемент ИЛИ 23. 1 з.п.ф-лы, 22 ил.71619300 Составител А.Барановедактор М.Бланар Техред М.Моргентал Корректор Н.Ревская Тираж ГКНТ СС оизводственно-издательский комбинат "Патен ород, ул, Гагарина, 10 Заказ 50ВНИИПИ Государственно11303 комитета по изобре Москва, Ж, Рауш Подписноениям и открытиям пая наб., д, 4/5ЗО Изобретение относится к вьпгислительной технике и .может быть использовано в системах цифровой обработки сигналов,5Белью изобретения является упрощение устройства,На фиг, 1 и 2 приведена структурная схема устройства; на фиг, 3 -структурная схема арифметического 10,блока, на фиг,4-22 - диаграммы расположения операндов в блоках памятиустройства.Устройство (фиг.1 и 2) содержитинформационный вход 1, входной коммутатор 2, арифметический блок 3, коммутатор операндов 4, блоки 5-10 памяти, блок 11 постоянной памяти (весовых коэффициентов), 1 элементовИ 12.1-12, 1.(где 1 = 1 орЕ),счетчик 13 20(по модулю И), сдвиговый регистр 14,счетчик 15 итераций, блок 16 посто-,янной памяти, коммутаторы 17.1-17.6,тактовый вход 18, вход 19 установки, элементы НЕ 20 и 21, информационный выход 22 устройства, элементИЛИ 23, входы управления записью -считыванием 24. 1-24 гг блоков 5-10памяти, адресные входы 25.1-25.6блоков 5-10,памяти, выход 26 первого разряда счетчика 13,Арифметический блок 3 (фиг.З) содержит сумматор (действительной части)27, сумматор (мнимой части) 28, вычитатель (действительной части) 29,вычитатель (мнимой части) 30, коммутатор (разностей) 31 и 32, входыреальной 33 и мнимой 34 частей весового коэффициента, вычитатель 35,умножители 36 и 37, регистры 38 и 39,коммутаторы (выходные) 40 и 41, сум-матор 42.Рассмотрим работу отдельных узловустройстваАрифметический блок 3 устройства производит вычисление базовойоперации алгоритма БПФ за два такта. Входные операнды А и В в течение двух тактов подаются на одноименные. информационные входы. Весовойкоэффициент также в течение двух тактов поступает на соответствующие входы. В первом такте на управляющем входе нулевое значение. Сумматоры 27 и 28вычисляют КеС =-РеА + КеВ и 1 щС = 1 гА + 55+ 1 щВ соответственно, которые черезкоммутаторы 40 и 41 поступают на выход блока 3. Вычитатели 29 и 30 вычисляют КеС = КеА - КеВ и 1 щС = 1 пй -1 щВ соответственнп. При этом значение КеС = КеА - КеВ поступает на первый вход умножителя 36, а значение 1 щС = 1 пй - 1 щВ на первый вход умно- жители 37, На вторые входы умножителей 36 и 37 поступают значения соответственно.С приходом синхроимпульса на управляющем входе блока 3 появляется единичное значение. В регистрах 38 и 39 записываются значения (КеАВеВ)КеЯ и (1 пй - 1 гпВ)1 щЫ соответственно. На первые входы умножителей 36 и 37 поступают значения 1 пйщВ и КеА-КеВ соответственно, на вторых входах умножителей 36 и 37 - значения КеУ и 1 щЫ соответственно, на выходах умножителей 36 и 37 - значения (1 тпАщВ)1 щИ и (КеА-ВеВ)1 пИ соответственно, на вьгходе вычитателя 35 - значение КеЛ = (КеА-КеВ)КеИ- в (1 пйгпВ)1 тЮ, которое через коммутатор 40 поступает на выход действительной части блока 3, на выходе сумматора 42 - значение 1 щй = (1 гпА 1 щВ)РеЪт + (КеА-КеВ)1 п%, которое поступает через коммутатор 41 на выход мнимой части арифметического блока 3.Формирование весовых коэффициентов производится блоком 11 памяти и элементами 12,1-12.6.На итерациях алгоритма БПФ происходит подача нулей на вторые входы соответствующих элементов 12.1-12.6, что приводит к требуемому прорежи- . ванию весовых коэффициентов.Устройство производит вычисление алгоритма. БПФ по основанию 2 с прореживанием по частоте по грифу с постоянной конфигурацией.Будем рассматривать работу устройства на примере И = 16, На вход 18 поступает последовательность тактовых импульсов. На вход 19 установки поступает верхний логический уровень, который производит установку в нулевое состояние счетчика 13, регистра 14, Со старшего выхода регистра 14 поступает значение "Лог.0", которое обнуляет через элемент НЕ 21 счетчик 15 итерации и устанавливает на управляющем входе регистра 14 значение "Лог.1", разрешающее параллельное занесение информации в регистр. До поступления на вход 19 нижнего логического уровня все узлы нахопятся в описанном состоянии, По 5 16193сле поступления "Лог,О" на вход 19начинается этап загрузки входнойинформации в блоки памяти устройства. Входные отсчеты Х (и = О, И-)поступают последовательно на вход 1устройства. На входах элемента ИЛИ23 нулевое значение, поскольку регистр 14 находится в обнулении,На вход управления коммутатора 2 поступает "Лог.О" с выхода элемента23, разрешающий передачу информациис входа 1.В первые четыре такта на выходах25. 1-25.6 второй группы управляющихвыходов блока ПЗУ 16 - состояние100000 соответственно, которое разрешает работу блока 5 памяти. На управляющих входах коммутаторов 17.117.6 - значение соответственно 000000,20которые разрешают прохождение тактовых импульсов с первого входа коммутатора 17.1 на вод 24,1 блока 5 памяти. Через четыре такта входные отсчеты Х, Х, Х, Х записаны последовательно в блок 5 памяти. В следую-,щие четыре такта на входах 25.1-25.6блоков 5-10 памяти - значения 010000соответственно. На управляющих входахкоммутаторов 17.1-17.6 значения не 30меняются. При этом следующие четыреотсчета Х 4, Хз., Х, Х записаны вблок 6 памяти, В третьей четверке тактов на управляющих входах 25.1-25.6блоков 5-10 памяти - значения 00100035соответственно.На управляющих входах 17.1-17,6значения не меняются. Поэтому отсчеты ХЗ,Х, Х, Хи записаны в блок 7памяти. Аналогичным образом отсчеты Х, Х,Х 1 Хзаписаны в блок Япамяти. При этом на управляющих входах 25,1-25.6 блоков 5-10 памяти значения 000100 соответственно. На управляющих входах коммутаторов 17.1- 4517.6 значения не меняются,После выдачи импульса переноса свыхода счетчика 13 происходит запись всех единиц в регистр 14. Приэтом регистр 14 переходит в режим 50сдвига, а со счетчика 15 снимаетсясигнал обнуления.Таким образом, процесс загрузкивходной информации завершается иустройство переходит В вычисления БПФ,55Первая итерация,Расположение информации в блоках5-10 памяти показано на диаграмме(фиг.4). Условные обозначения блоков 00 6памяти соответствуют блокам 5-10 сверху вниз. Первые четыре такта на уп - равляющих входах 25, 1-25.6 блоков 5-10 памяти значения 10101, На управляющих входах коммутаторов 17. 1 - 17.6 значения 101000 соответственно, которые разрешают коммутаторам 17. 1 и 17.3 передачу информации с вторых входов, Поэтому блоки 5 и 7 памяти сдвигают информацию с частотой, равной половине тактовой, а блоки 9 памяти с частотой, равной тактовой. На первый управляющий вход коммутатора 4 приходит код, разрешающий передачу информации с первого входа на первый выход. На второй управляющий вход коммутатора 4 приходит код, разрешающий передачу информации с третьего входа на второй выход. Коммутатор 2 до конца вычислений передает информацию на выход с выхода арифметическо-, го блока 3. На всех диаграммах стрелками А И В условно показаны выходы бл,ков 5-10 памяти, подключенные через коммутатор.4 к соответствующим входам блока 3, Входной стрелкой на диаграммах показан результат У4 (где- номер итерации, 1 - номер операнда), записываемый в соответствующих блоках 5-10 памяти.Первый таку (фиг.4). На первом входе А арифметического блока 3 значение Хо, на втором - Хб, На выходе блока 3 значение У на входах весового коэффициента блока 3 установлено значение соответствующего поворачивающего множителя, которое поступает с соответствующих выходов блока 11 постоянной памяти.Второй такт (фиг,5). На входах А и В арифметического блока не меняется.Значение У, записано в первый регистр блока 9 памяти,Третий такт (фиг,6). На входах А и В блока 3 значения Х и Х соотственно. Записьинформации йроисхсдит последовательно в блок 9 памяти. На входах весового коэффициента блока 3 следующее значение поворачивающегомножителя.Четвертый такт (фиг.7). Все режимы блоков аналогичны предыдущим тактам. Происходящую попутно запись информации в блоки 5 и 7 памяти в дальнейшем учитывают и для простоты на диа-6 граммах свободные ячейки этих блоков заполняются нулями;В следующей четверке тактов навходах 25, 1-25,6 блоков 5 и 10 памятизначение 101001 соответственно. Науправляющих входах коммутаторов 17,117.6 значения 101000 соответственно.5Расположение операндов в этой четверке тактов показано на диаграммах(фиг.8-11),В тактах 9-12 (Аиг.12-15) информация на вход А блока 3 поступаетс выхода блока 6 памяти, на вход Вблока 3 - с выхода блока 8 памяти.Запись инАормации производится в блок5 памяти. На входах 25.1-25,6 управления блоков памяти 5-10 - значения11011. На входах управления коммутаторами 17.1-17.6 значения 010.100. Расположвние инАормации в этих тактах показано на фиг.12-15,20В тактах 13-16 (фиг.16-19) считывание информации производится также изблоков 6 и Я памяти, а запись производится в блок 7 памяти. На входах25.1-25,6 блоков 5-10 памяти значения 25011100. На управляющих входах коммутаторов 17.1-17.6 значения 010100 соответственно.Расположение операндов после первойитерации показано на Аиг.20. Послевьгцачи импульса переноса с выхода счетчика 13 в первый разряд регистра 14записывается нулевое значение. Счетчик 15 установлен в значение 01, Нулевое значение с первого выхода регистра 14 через элемент И 12.1 поступает35на младший адресный разряд блока 11постоянной памяти. Это приводит к двукратному прореживанию весовых коэААициентов на второй итерации вычисления БПФ.Вычисление второй итерации производится по такому же принципу, какописано.В первой четверке тактов на входыВ и А блока 3 информация поступает сблоков 9 и 5 памяти соответственно,а запись - в блок 6.Вторая четверка тактов отличается,только тем, что информация записывается в блок 8 памяти.В третьей четверке тактов на входыА и В блока 3 инАормация поступаетс выходсв блоков 10 и 7 памяти соответственно. Запись проводится в блок9 памяти,55Последняя четверка от предыдущейотличается только тем, что записьинформации проводится в блок 9 памяти. Расположение операндов в блоках 5-10памяти после второй итерации показано на диаграмме (фиг.21),Расположение информации в блоках5- 10 памяти после третьей итерациипоказано на диаграмме (Аиг,22),На четвертой итерации проводят выбор только тех блоков 5-10 памяти, изкоторых проводят считывание информации.Результаты четвертой итерации поступают на выход 22 устройства,С приходом импульса переноса свыхода счетчика 13 на последней итерации на последнем выходе регистра 14появляется нулевое значение, которое обнуляет через элемент НЕ 21счетчик 15 итераций и переводит в режим параллельной записи регистр 14.Коммутатор 2 при этом передает ин"формацию с первого входа, При этомпроисходит загрузка в блоки 5-10 памяти следующего массива,Формула изобретения1. Устройство для вычисления быстрого преобразования Фурье, содержащее арифметический блок, шесть блоков памяти, первый блок постоянной памяти, 1 (1 =, 1 о 8 И; где М - размер преобразования) элементов И, сдвиговый вегисстр, счетчик, выход г-го, г2,1 ф 1) разряда которого подключен к первому входу (-1)-го элемента ,И, выход которого подключен к (-1)- му адресному входу первого блока постоянной памяти, первый и второй выходы которого подключены к входам соответственно реальной и мнимой ча,стей коэфАициента ариАметического блока, первый тактовый вход которого соединен со счетным входом счетчика и является тактовым входом устройства, установочным входом которого является вход обнуления счетчика, выход переноса которого подключен к тактовому входу сдвиг оного регистра, выход 1-го (1 =1,1) разряда которого подключен к второму входу -го элемента И, последовательный вход сдвигового регистра является входом задания логического нуля устройства, входом задания логической единицы которого является параллельный вход сдвигового регистра, о т л и ч а юш е. е с я тем, что, с целью упрощения устройства, оно содержит дваэлемента НЕ, элемент ИЛИ, счетчик итерации, второй блок постоянной памяти, входной коммутатор, коммутатор операндов и шесть коммутаторовВ причем выходы блоков памяти с первого по шестой подключены к информационным входам соответственно с первого по шестой коммутаторы операндов, первый и второй выходы которого подключены к входам соответственно первого и второго операндов ариАметического блока, выход которого является информационным выходом устрсйства и подключен к первому информационному входу входного коммутатора, выход которого подключен к информационным вхоцам блоков памяти с первого по шестой, выход первого разряда счетчика подключен к первому инАсрмацисн ному входу ш-го (ш =1,6) коммутатора и второму тактовому входу ариАметическбго блока, выход первого разряда сдвигового регистра подключен к первому входу элемента ИЛИ, вьжсд като рого подключен к управляющему входу входного коммутатора, второй инАормационный вход которого является информационным входом устройства, установочный вход которого подключен к входу первого элемента НЕ, выход которого подключен к входу обнуления сдвигового регистра, выход (1+1)-го разряда которого подключен к второму входу элемента ИЛИ и входу второго элемента НЕ, выход которого подключен к входу управления сдвигом сдвигоного регистра и входу обнуления счетчика итераций, инАормяциснный выход которого подключен к первому адресному входу второго блока постоянной памяти, ш-й адресный и ш-й управляюший выходы которого подключены соответственно к адресному входу ш-го блока памяти и управляющему входу ш-го коммутатора, выход которого подключен к входу управления запись -считыванием, ш-го блока памяти, выход переноса счетчика подключен к счетному входу счетчика итераций, выходы (1-1)-гс и50 1-го разрядов счетчика подключены к второму адресному входу второго блока постоянной памяти, седьмой и восьмой управляющие входы которого подключены соответственно к первому и второму управляющим входам коммутя 55 тора операндов, а второй инАормяционный вход ш-го коммутатора подклачен к тактовому входу устройства.2, Устройство по п., о т л ич а ю щ е е с я тем, что гриАмет;ческий блок содержит три сумматора,три вычитателя, дна умножителя, днарегистра и четыре коммутатора, причем выходы первого и второго сумматоров подключены к первым информационным входам соответственно первого и второго коммутаторов, выходыкоторых образуют информяпионный выход арифметического блока, вход первого операнда котсрсгс образуетсоединенные между собой первые входыпервых сумматора и нычитятеляи соединенные между собой первые входы вторых сумматора и вычитателя, вторыевходы которых соединены между собойи образуют с ссединенньъи,между собой вторыми входами первых сумматораи вычитятеля вхОд второго Операндаарифметического блока, первым тактовым входом которого являются соединенные между собой первые тактовыевходы первого и второго регистр;н,выходы которых подключены к первымвходам третьих соответственно нычитателя и сумматора, выходы которыхподключены к вторым инАОрмяционнымвходам соответственно первого ивторого коммутаторов, управляющиевходы которых соединены с упранляющими входами третьего и четвертогокоммутаторов и являются вторым тактовым входом ариАметического блока,входами реальной и мнимой частейкоэффициента которого являются первые входы соответственно первого ивторого умножителей, выходы которыхподключены к инАормяционным нходамсоответственно первого и второгорегистров и вторым входам третьихсоответственно вычитателя и сумматора, выход первого нычитателя подключен к первым инАормационным входамтретьего и четвертого коммутаторов,выходы которых подключены к вторымвходам соответственно первого ивторого умножителей, а выход второго вычитателя подключен к вторыминАормационным входам третьего ичетвертого коммутаторов, 1619300