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

(51)5 6 06 Р 15/332 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Ы Ь 3 )СлЗ Ц 3 Сл) ,)(71) Научно-исследовательский институтприкладных физических проблем им,А.Н,Севченко(56) Авторское свидетельство СССРМ 1290350, кл, 6 06 Р 15/332, 1987.Авторское свидетельство СССРч. 1042028, кл, 0 06 Г 15/332, 1983,(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57)Изобретение относится к вычислительнойтехнике и предназначено для использованияв высокоскоростных параллельно-конвейерныхпроцессорах быстрого преобразования Фурье Изобретение относится к области вычислительной техники и предназначено для использования в высокоскоростных параллельно-конвейерных процессорах быстрого преобразования Фурье (БПФ) Виноградовского типа, которые ориентированы на применение в компьютерной томографии, в частности в томографах для обследования высочно-нижне-челюстного сустава.Цель изобретения - повышение быстродействия устройства для вычисления дискретного преобразования Фурье.В предлагаемом устройстве для вычисления ДПФ может быть реализовано любое ДПФ вида ЯО 1732353 А 1 Виноградовского типа. Цель изобретения - повышение быстродействия устройства для вычисления дискретного преобразования Фурье (ДПФ). Поставленная цель достигается тем, что в устройстве обеспечивается реализация ДПФ любого объема, не превосходящего заданного значения, путем использования однократных модульных умножителей табличного типа, Устройство для вычисления ДПФ содержит блок преобразования двоичного кода в код модулярной системы счисления, два регистра константы сдвига, блок постоянной памяти константы сдвига, блок преобразования кода модулярной системы счисления в двоичный код, счетчик тактов, регистр номера шага, входные регистры, блок постоянной памяти коэффициентов, группы блоков постоянной памяти, блоки суммирования по модулям и блок задержки. 1 ил. Ыг - з 1Х.(ц) - х.(ц) вК" (1)Ц =0где Кг- - объем ДПФ, реализуемых на з-м шаге алгоритма Винограда, представляющем собой множитель исходного Й-точечного ДП Ф (К = К 1 М 2К г1); х(ц) = х, (ц) + )х (ц);х (а), х (о) - изменяются в симметричных отрезках (-Р, Р, Р - натуральное число;3 - 0,1,.,г 1, -наг - в = ехр( - )2 Э(ч - .,)Х-(ч) = х Я+ х (ч) - отсчеты выходного сигнала ДПФ, 1732353=О,1,., йАппроксимируем константы соз(2 йт/Кг-в) и з 1 п(2 тг т/Кг-з) соответственно дробями ч"вам /С 1 и ччзс И, числители которых вычисляются по правилам Юз = Осоз(2 7 г т/Кг-з) , Я," = С)з 1 п(2 л т/Кг-з) где с = О, 1 йг-в -1; 0 - натуральное число; через х обозначается ближайшее к х целое число. Выделив из множества а=(аоо,аоо и аО,йг - 1 - 1 ао,й - 1 - 1 а 1,0 а 1,0 " а 1,йу - г 1 ф 1 а 1,й - г 1в.", аг,0 аг.0, -, аг - 1 й 1 - 1, аг - 1, й 1 - 1 ) набор различных его элементов(ччо, а 1, , а Л) (а6 а;= О, 1 Л -1; аа, т = О, 1 ., Л -1; М 1, Л - объем набора), обозначив через аУ (З, О,Ч); аУ 1 (З,О,Ч),аУ 2 (З,О,Ч), Уо (З,О,Ч), у 1 (з,о,ч), уг (з,о,ч) Е. (О, 1, ., Л - 1 Ячислители дробей, аппроксимирующих соответственно константы-3 п(2 л Оч/Кг-з) = зп(2 л -ОчКг-з/Кг-в), СОЗ(2 ЯОЧ/йг) = СОЗ(2 КОЧ 1 К г-в/Кг-з), з 1 п(2 оч/йг)= зп(2 й оч 1 Ч"-ь/ Кг-з). Тогда согласно вышеизложенному искомый машинный аналог (2) можно записать в виде: Х= -- ," в(Я,о,ч) + - , ф(з,о,ч) Х= -- ," чу,(Я,О,ч) + - , ччч(з,ц,ч) , Ч=О 1,.й, (3)ГдЕ Х, ХО, Хч, ХЧ - МаНтИССЫ ОтСЧЕтОВ Хз (О), 4 (о), Хв (ч), Хз (ч) соответственно; 2" - масштаб (1 з - неотрицательное целое число),-в выираемый так, чтобы величина хо = ХО 2и хо = хоц 2не выходили за пределы отрезка (-Р,Р); через хИ обозначается некоторое целочисленное приближение к дроби хИ; х - целое число. Без нарушения общности действительные и мнимые составляющие отсчетов исходного К-точечно, го сигнала, а значит и величины хо(о) и хо(о)(3) полагаются целочисленными. Целочисленными являются также мантиссы хО, хц,Хч, Хч для всех з = О, 1 г, Следовательно, они являются элементами диапазона( - Р, - Р+1, , Р) и имеют порядок 1,=О5 Для реализации базовых соотношений(ГдЕ С = ВаХ (К 1, Кг, , Кг,10 На чертеже приведена структурная схема предлагаемого устройства для вычисления дискретного преобразования Фурье(ДПФ),Устройство для вычисления ДПФ содер 15 жит тактовый вход 1, вход 2 задания номерашага алгоритма, первый установочный вход3, информационный вход 4, четвертый 5,второй б и третий 7 установочные входы,регистр 8 номера шага разрядностью 1 о 92 г,20 входные регистры 9.1 - 9.2 ц разрядностью1 =), Ь бит(Ь; =оцгв; через=1х обозначается ближайшее к х справа целое число), блок 10 преобразования двоичного кода в код модулярной системысчисления, первый регистр 11 константысдвига, счетчик 12 тактов, группы блоков постоянной 13.1-13.К памяти, блок 14 задержки, блок 15 постоянной памяти константысдвига, блок 16 постоянной памяти коэффициентов, блоки 17.1 - 17,К суммирования соответственно по модулям в 1, вгвь блок18 преобразования кода модулярной системы счисления в двоичный код, второй регистр 19 константы сдвига, выходымантиссы 20 и порядка 21 устройства,Блок 10 осуществляет преобразованиеГЛ-битовых двоичных кодов мантисс хо и хо.з 1 л40 в модулярный код величин хо и хц . Данныйблок представляет собой известное устройство, выполняющее одно преобразованиеза Ти + 1 такт, где Ти = 1 оцгй;,и - числогрупп двоичных разрядов в преобразуемых45 А-битовых кодах ( Л - разрядность промасштабированных значений соответствующихмантисс), Обращение к блоку 10 можно производить ежетактно, Первый вход преобразователя 10 является информационным50 входом 4 устройства. Второй вход подключен к выходу регистра 11, а выход заведенна вход блока 14 задержки.Тактовый вход блока 10 объединен стактовыми входами регистров 8, 9.1-9,2 ц, 11и 19 блока 14 задержки, блоков 17.1 - 17.Ксуммирования, блока 18 преобразованиякода модулярной системы счисления в двоичный код со счетным входом счетчика 12тактов и подключен к тактовому входу 1 устройства.5 10 15 установки в нуль счетчика 12 объединен с 20 50 55 Блок 18 преобразования кода модулярной системы счисления в двоичный код является известным устройством конвейерного типа, осуществляющим одно преобразование за (Т+ 3) такта (Т =о 92 Щ, причем, обращение к преобразователю можно производить ежетактно. Блок 18 по информационным входам соединен с выходами блоков 17.1 - 17.К суммирования, Его выход является выходом 20 мантиссы устройства, при этом старшие б разрядов выхода заведены на первый адресный вход блока 15 постоянной памяти,Счетчик 12 тактов является (Тц + 1)-разРЯдным (Тч =1 о 92 ЦЦ и имеет два входа Установки в нуль. Наличие единичного сигнала на любом из них обнуляет содержимое счетчика в момент окончания тактового импульса на счетном входе счетчика. Первый вход входом разрешения записи регистра 8 номера шага и подключен к первому установочному входу 3 устройства, Второй вход установки в нуль объединен с входами разрешения записи регисров 9.1 - 9.2 ц и подключен к (2 ц + 1)-му выходу блока 16 постоянной памяти. Запись информации в регистры 9,1 - 9.2 ц осуществляется при наличии единичного сигнала на их входах разрешения записи, Выход счетчика 12 заведен на первый вход блока 16 постоянной памяти,Группа блоков 13,1( = 1, 2, , К) постоянной памяти состоит из 2 ц одинаковых блоков постоянной памяти емкостью (2) Л)Ь бит, В каждом из этих блоков постоянной памяти по адресу 1 + т 2 записывается вычет уа пц для всех у = О, 1, , гп, т = О, 1 Л, где через 1 А п обозначается наименьший неотрицательный вычет, сравнимый с величиной А по модулю щ. Первый адресный вход -го блока постоянной памяти группы 13.1 подключен к 1-му выходу регистра 9. 0 = 1, 2, , 2 ц), вторые адресные входы 1-х блоков постоянной памяти всех групп объединены и подключены к )-му выходу блока 16, а выход -го блока постоянной памяти подключен к одноименному входу блока 17,1,Блок 14 задержки представляет собой цепочку из 2 црегистров разрядностьюбит, Вход первого регистра подключен к первому выходу блока 14 задержки, а выход 1-го регистра является (1+ 1)-м выходом блока задержки ( = 1, 2, 2 ц), Выходы блока 14 задержки с первого по(2 ц)-й подключены к информационным входам соответственно регистров 9,1 - 9.2 ц. Обращение к блоку задержки может осуществляться ежетактно. 25 30 35 40 45 Блок 15 постоянной памяти кг ста:,ы сдвига облащет емкостью 2 ) 1 о 9 с 1 бит б = у - А+ 1). В его память по адресу х +12 записывается величина щахх), е) для всех х = О, 1 2 - 1 и 1 = О, 1, , с 1-1,бгде 1(х)-номер самой младшей цифры двоичного кода (хихб, , хо)2 числа х, удовлетворяющей условию х = х(х) при каждом 11(х), Второй адресный вход блока 15 подключен к выходу регистра 19, являющемуся выходом 21 порядка устройства, Информационные входы регистров 11 и 19 объединены и подключены к выходу блока 15. Вход разрешения записи регистра 11 и входы установки в нуль регистров 11 и 19 подключены соответственно к четвертому 5, второму 6 и третьему 7 установочным входам устройства. Запись в регистр 11 осуществляется при поступлении единичного сигнала на установочный вход 5 устройства, Запись в регистр 19 осуществляется ежетактно. Единичные сигналы на установочных входах 6 и 7 обнуляют содержимое соответственно регистров 11 и 19;Блок 11 поотояннои памяти обладает емкостью 2 оц 2 К+ тя+ 1) х 2 ц 1 о 9 Л + 1) .)В его память по адресу 1 ч + 2 тя + 1)з) записывается двухкомпонентный набор ве- личин уу у)-я из которых поступает на-й выход 0=1,2 ц) блока 16. Здесь у - номер нуля множества (качо, чч 1, , вЛ - 1), т,е. константы ччу =О, На (2 ц+1)-й выход блока 16 поступает из ячейки с вышеуказанным адресом величина (1 - 2 йг-Б - ч), которая обеспечивает для счетчика 12 подсчет числа тактов по подулю 2 йг-з, Второй адресный вход блока 16 постоянной памяти подключен к выходу регистра 8 номера шага, Информационный вход последнего подключен к входу 2 задания номера шага, Запись числа в регистр 8 осуществляется по окончанию такта при наличии единичного сигнала на входе разрешения записи,Блоки суммирования по модулю 17.1- 17,К являются известными устройствами. Они имеют (Тя + 1)-каскадную параллельно- конвейерную структуру, благодаря чему обращение к ним можно производить ежетактно,Работа предлагаемого устройства для вычисления ДПФ.Процесс выполнения ДПФ, описываемого выражением (3), можно разбить нава этапа. В ходе первого этапа мантиссы ХЮ-з, ХЧг-з, Х 3, Хо ДЕйСтВИтЕЛЬНЫХ И МНИ- мых составляющих отсчетов входного сигнала ДП Ф последовательно от такта к такту, начиная с нулевого, в указанном порядке 5 подаются на первый вход блока 10, на второй вход которого из регистра 11 ежетактно поступает константа сдвига Нз, отвечающая текущему (з-му) шагу алгоритма Винограда, Перед началом нулевого шага алгоритма 10 регистр 11 по сигналу 2 г = 1 с входа 6 устройства обнуляется (о = О), а на последнем (Ти + 2 йг-з + То + Т + 5)-м такте каждого шага в регистр 11 по сигналу 24 = 1, поступающему с входа 5 устройства, запи сывается константа, формируемая так, как это изложено ниже, на входе блока 15 постояннойой памяти. На (Ти+ 1)-м такте каждого на установочном, входе 3 устройства появляется сигнал 21 = 1, по которому в конце этого 20 такта в регистр 8 занесется значение з, поступавшее на вход 2 задания номера шага алгоритма, а содержимое счетчика 12 тактов обнуляется, С конца (Тр+ 1)-го такта, где Тр = 1 одт (и - число гнпп двоичных25 разрядов в преобразуемых, 1-битовых кодах, в блок 14 задержки с выхода блока 10 ежетактно начнут поступать модулярные ком л з л ды (МК) величин хмг-з, хчг-зхо, хо и 30 по истечении ( Ти+ 2 йг-з)-го такта полученные МК по единичному сигналу с (2 ц+1)-го выхода блока 16 передаются в регистры 9.1 - 9.2 йг-з, модулярный код (2 йг-з - 1+1)-го элемента последовательности запоминается в 35 регистре 9 л (1 = 1, 22 йг-з).Второй этап процесса реализации выражений (3) так же, как и первый, состоит из 2 йг-з тактов. В ходе (2 ч+ Ь)-го цикла, начинающегося с (Ти+ 2 йг-з+ 2 ч+ Ь)-го такта 40 (ч - ( О, 1, , Иг-з; Ь = (1, 2 на первый и второй входы группы блоков 13, ( = 1, 2, , К) подаются соответственно 2 с-компонентные наборы величинл ",гХоП 1 ХовпХЧг-з.1 в 45ХЧг-з В, В 2 йг, , ЯгяИГЬ (З, Ч), где Вг - 1-я цифра МК, записанного в регистре 9 л(1 = 2 йг-з+ 1,2 Мг-з+ 2, "., 2 с), В результате во входные регистры блоков 17. суммирования вычетов с выхода группы 50 блоков 13. постоянной памяти поступит набор вычетов1 ИхМу 2 - ь(з,о,ч)гпь хоЮуЗ - ь(з,о,ч)гпь ,ф 31ХВ-зЯу-Ь (3, йг-з, Ч)гп, 55ХЧг-з-Юуэ - (а,йг-.-1, Ч) пъ О, ,0для всех= 1, 2, , К и по окончании( Ти+ 2 йг-з + 2 ч + Ь + То + 1)-го такта блоки 17.1 - 17.К сформируют МК числа уч при Ь = 1и числа уч при и = 2 по правилу, Мг - з -уч = "), (ХцМ/у 1(З,О,Ч) + ХцИу(З,О,Чц=ОМг - з - 1,Уч =,Я (ХцИ/Уо(З,Ц,Ч) + ХцЯУ 1(З,Ц,Чц=ОПолученный МК на следующем такте поступает в блок 18 преобразования. Двоичные А-разрядные коды результатов масштабирования величин уч и уч на масштаб О, т.е, искомые мантиссы Хч и Хч действительной и мнимой составляющих ч-го комплексного отсчета выходного сигнала выполняемого ДПФ (формула (3) будут получены блоком 18 соответственно на (Ти+ 2 чг-з + 2 ч + +Тя + Т+ 5) = м и (Ти+ 2 йг-з + 2 ч + То+ Т + 6) = м тактах. Мантисса, полученная по истечении (Тр+ 2 Мг-з+ 2 ч+ Тя+ Т+ Ь+ 4)-го такта, снимается с выхода мантисс АУ в следующем такте. При этом ее б-битовая старшая часть дч вместе с содержимым регистра йбе подаются на адресные входы блока 12 и из его памяти по адресу дч + е 2 считывается величина гпахдч), е ), которая запоминается в регистре 19, В момент появления на выходе блока 18 преобразования мантиссы действительной части нулевого комплексного отсчета выходного сигнала первого из ДПФ, выполняемых на з-м шаге алгоритма Винограда (з = О, 1 г), т.е. по окончании (Ти+ 2 чг-з+ Тя+ Т+ 5)-го такта данного шага, регистр 19 обнуляется по сигналу 2 з = 1 с входа 7 устройства. Поэтому согласно вышеизложенному после выполнения последнего из ДПФ з-го шага на выходе блока 15 постоянной памяти сформируется константа СдВИГа з+1 дЛя (З+1)-ГО ШаГа, ПОЛуЧЕННая константа записывается как в регистр 19, откуда она поступает на выход 21 порядка устройства, так и по сигналу 24 = 1 в регистр 11. Действительные и мнимые составляющие всех отсчетов выходного сигнала исходного М-точечного ДПФ, вычисляемые в ходе заключительного шага алгоритма Винограда, имеют общий порядок: 1+ 2+ . + г,Заметим, что отдельные ДПФ объема Мг-з в описываемом устройстве осуществляются за Т(чг-з) = 4 йг-з+ Ти+ То+ Т+ 5 тактов. При этом реализация нового ДПФ данного объема может быть начата по истечении (2 йг-з)-го такта текущего преобразования, т.е. частота обращения к устройству на з-м шаге алгоритма Винограда состав10 1732353 50 55 ляет 1 = 1/2(2 й-:)Тмт, где Тмт - длительность модульного такта,Если, например, М-, = 4, то 1 = 1/8 Тмт, что существенно выше частоты обращения известного устройства, составляющей 1/13 Тмт. Поскольку предлагаемое устройство способно выполнять любое ДПФ объема, не превышающего ц, то сфера его применения существенно шире, чем у известного. Формула изобретения Устройство для вычисления дискретного преобразования Фурье, содержащее первый и второй регистры константы сдвига, блок постоянной памяти констант сдвига, блок преобразования кода модулярной системы счисления (МСС) в двоичный код и блок преобразования двоичного кода в код модулярной системы счисления, первый и второй информационные входы которого подключены соответственно к информационному входу устройства и выходу первого регистра константы сдвига, тактовый вход которого подключен к тактовому входу устройства и соединен с тактовыми входами блока преобразования двоичного кода в код модулярной системы счисления, второго регистра константы сдвига и блока преобразования кода модулярной системы счисления в двоичный код, выход которого. является выходом мантиссы устройства и подключен к первому адресному. входу блока постоянной памяти константы сдвига, второй адресный вход которого подключен к выходу второго регистра константы сдвига, выход которого является выходом порядка устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены регистр номера шага, счетчик тактов, блок постоянной памяти коэффициентов,2 о (о - объем преобразования) входных регистров, К групп блоков постоянной памяти (К - число оснований модулярной системы счисления) по 2 о блоков в каждой, К блоков суммирования по модулю соответственно в,пз 2, , вк, блок задержки, )-й ( = 1,2;.,) вы:лд которого подключен к информационному входу )-го входного регистра, -й (1 = ГК) выход которого подключен к первому адрес ному входу)-го блока постоянной памяти 1-йгруппы, выход которого подключен к )-му информационному входу блока суммирования по модулю п, выход которого подключен к 1-му информационному входу блока 10 преобразования кода модулярной системысчисления в двоичный код, выход блока преобразования двоичного кода в код модулярной системы счисления подключен к информационному входу блока задержки, 15 тактовый вход которого соединен с тактовыми входами всех входных регистров, тактовыми входами всех блоков суммирования по модулю, счетным входом счетчика тактов, тактовым входом регистра номера шага и 20 подключен к тактовому входу устройства,первый установочный вход которого подключен к установочному входу счетчика тактов и входу разрешения записи регистра номера шага, выход которого подключен к 25 второму адресному входу блока постояннойпамяти коэффициентов, М-й выход(М =1,2 ц) которого подключен к второму адресному входу М-го блока постоянной памяти -й группы, информационный выход счетчика 30 тактов подключен к первому адресному входу блока постоянной памяти коэффициентов, (2 ц + 1)-й выход которого подключен к входу обнуления счетчика тактов и входу разрешения записи )-го входного регистра, 35 выход блока постоянной памяти константсдвига подключен к информационным входам первого и второго регистров констант, сдвига, установочные входы которых подключены соответственно к второму и треть ему установочным входам устройства,четвертый установочный вход которого подключен к входу разрешения записи первого регистра константы сдвига, а вход задания номера шага устройства подключен к инфор мационному входу регистра номера шага.12 1732353 пп ктор Т.Палии дактор Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 1 аз 1584 ВНИИП оставитель Л,Василевичехред М.Моргентал Тираж Подписноеосударственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб 4/5