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

(191 (1 11 С 06 Г 15/312 НИЕ ИЗОБРЕТЕНИЯ О ЕТЕПЬСТВ ВТОРСИОМУ овательностей вх содержит второй памяти, причем идо четырех посл ных отсчетов, о блок оперативно ка управлетыи и шестов выходы ни тиресн с ат х к в ло ной к входу операнблока, причем АЦИ дов н зряднои ти СУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ.И ОТКРЫТИЙ(7) Научно-исследовательский инстут прикладных физических проблемим, акад, А,Н.Севченко(56) 1, Авторское свидетельство СР 548863, кл. 5 06 Г 15/332,1975.2. Авторское свидетельство СССВ 809198, кл. С 06 Г 5/332, 1979(54) (57) 1. УСТ 1 ОИСТВО Д 31 Я РЕАЭП 13БЕЗЪЗБ 11 ТОЧОГО АГ 011 ТМА БЫСТРОГОНРЕОБРАЗОВЛН 11 Я ФУРЬЕ, содержащееарифметический блок, блок постоявпамяти, первый блок оперативной имяти и блок управления, причем выход первого блока оперативной иами выход блока постоянной иамят подключены соответственно к входуоперандов и входу коэффициентов дрифметического блока, выход которогоподключен к информационному входупервого блока оперативной памяти,первый и второй выходы блока управления подключены к адресным входампервого блока оперативной памяти иблока постоянной памяти соответственно, третий выход блока управленияподключен к входу управления записьюсчитыванием первого блока оперативной памяти, четвертый выход блокауправления подключен к синхронизиРующему входу арифметического блока,о т л и ч а ю щ е е с я тем, что,с целью ловкаения быстродействия ирасширения функциональных возможностей устройства, состоящего в вычислении ире брдзовдния одновременно подключены соответственно к адому входу и входу управления заю-считыванием второго блока оиевной памяти, седьмой и восьмойды блока управления подключеныодам обращения первого и второгоов оперативной памяти соответсто, выход второго блока оперативпамяти подключенарифметического блок управления содержит узел си - хронизации, два триггера, и-ра ный счетчик (и=од М; 1 - объем вы 2борки), (и+1)-разрядный регистр итераций, узел элементов И, узел формирования инверсного кода, элемент и, два вычитателя, двд (и+1)-разрядных кольцевых регистра сдвига и узел блокировки, причем первый выход узла синхронизации подключен к счетному входу первого триггера, выход которого подключен к счетному входу второго триггера, первому входу элемента 11 и к информационным входам первых разрядов первого и второго кольцевых регистров сдвига, прямой выход второго триггера подключен к входу счетчика, вычитдющему входу первого вычитдтеля и к первому входу узла блокировки, инверсный выход вто рого триггера подключен к вычитающему входу второго вычитателя и к второму входу узла блокировки, параллельный выход счетчика подключен к первому информационному входу узла элементов Н, к информационному входу узла формирования инверсного кода и10 " б Об ь В,Гайковточка Коррект Сос тани Техред Т Редактор оз м ж 706 я наб д 1 илиал ИИИ "11 атент", г, Ужгород, ул. Проектна аказ 9308/43 Тир В 1111 ИИИ Государстве по делам изобрет 113035, Москва, д нного коми ений и Отк 35, Раущск Подписноеета СССРытий1056206 к третьему входу узла блокировки, выход переполнения счетчика подклю" чен к входу управления сдвигом регистра итераций, параллельный выход регистра итераций подключен к второ му информационному входу узла элементов И, выход первого разряда регистра итераций подключен к управляш щему входу узла элементов И, к вто" рому входу элемента 11 и к четвертому входу узла блокировки, выход (п+1) -го, разряда регистра итераций подключен к пятому входу узла блокировки, выход узла формирования инверсного кода подключен к суммирующим входам первого и второго вычитателей, выходы которых поразрядно подключены к информационным входам разрядов с вто рого по (и+1)-ый первого и второго кольцевых регистров сдвига соответственно, входы управления сдвигом первого и второго кольцевых регистров сдвига подключены соответственно к первому и второму выходам узла блокировки, выходы второго кольцевого регистра сдвига, узла элементов И, прямой выход второго тригге" ра, второй выход узла синхронизации, выход первого кольцевого регистра сдвига, инверсный выход второго трш гера, третий и четвертый выходы узла блокировки являются выходами блока управления с первого по восьмой соответственно.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что узел блокировки содержит элементы ИЛИ-НЕ, ИЛИ, НЕ, три сумматора по модулю два два элемента И-НЕ, шесть элементов И и триггер, причем вход элемента НЕ является четвертым входом узла блокировки и соединен с первыми входами первого сумматора по модулю два,Изобретение относится к автоматике и вычислительной технике и можетбыть использовано для решения задачспектрально-корреляционной обработкьпоследовательностей действительныхсигналов,Известно устройство для реализации быстрого преобразования Фурье,и элемента ШВ 1, второй вход первого сумматора по модулю два явля-ется пятым входом узла блокировки,входы элемента ИЦИ-НЕ с первого пои"ый являются соответствующими разрядами третьего входа узла блокиров-,ки, причем и-ый вход элемента ИЛИ-НЕсоединен с инверсным входом триггера, выход элемента НЕ подключенк первым входам первого и второгоэлементов И-НЕ, а также первого ивторого элементов И, выход элементаИЛИ-НЕ подключен к второму входу элемента ИЛИ, выход которого подключенк первым входам третьего и четвертого элементов И,вторые входы третьего ичетвертого элементов И являются соотвеъственно первым и вторым входами узлаблокировки, выход третьего элементаИ подключен к второму входу первогоэлемента И и к прямому выходу пятого элемента И, выход четвертого элемента И подключен к второму входувторого элемента И и к прямому входушестого элемента И, инверсные входыпятого и шестого элементов И подключенц к выходу первого сумматора по модулю два, выходы пятого и шестогоэлементов И являются соответственно.третьим и четвертым выходами узлаблокировки, прямой и инверсный вы"ходы триггера подключены к вторымвходам первого и второго элементовИ-НЕ соответственно, выходы первогои второго элементов И-НЕ подключены к первым входам второго и третьего сумматоров по модулю два, вторые входы которых подключены к выходам второго и первого элементов Исоответственно, вьходы второго итретьего сумматоров по модулю два являются соответственно вторым и первым выходами узла блокировки,содержащее узел реконфигурации счетчика, счетчик, регистр, группу эле" ментов ИЛИ и блок,выдачи адресов(1 .Недостатком известного устройства 5 является сложность построения, малоебыстродействие и отсутствие возможности формирования адресов значений экспоненциальных множителей, хранящихся в постоянной памяти и предназначенных для выполнения элементарных операций БПФ. Кроме того, без дополнительных аппаратурных затрат зто устройство не может реализовать алгоритм БПФ с замещением.Известно устройство для реализации алгоритма быстрого преобразования Фурье, содержащее блоки постоянной и оперативной памяти, ариф метический блок и блок управления, Выходы блока постоянной памяти и блока оперативной памяти подключены к входам арифметического блока, выходы блока управления - к управляющим входам блока постоянной памяти, блока оперативной памяти и арифметического блока 2.К недостаткам известного устройства следует отнести малую эффективность работы арифметического блока, поскольку основное время, требуемое для выполнения элементарной операций БПФ, затрачивается на запись и считывание операндов при обращении к блоку оперативной памяти. Кроме того, в ряде задач .спектрально-корреляционной обработки сигналов возникает необходимость одновременного вычисления преобразования Фурье трех и даже четырех последовательностей действительных чисел, что не может обеспечить известное устройство.Цель изобретения - повышение быстродействия и расширение функциональных возможностей устройства, состоя 35 щее в вычислении преобразования одновременно до четырех последователь- костей входных отсчетов.Поставленная цель достигается тем, что устройство для реализации безыз 40 быточного алгоритма быстрого преобразования Фурье, содержащее арифметический блок, блок постоянной памяти, первый блок оперативной памяти и блок управления, причем выход первого бло 45 ка оперативной памяти и выход блока постоянной памяти подключены соответственно к входу операндов и входу коэффициентов арифметического блока, выход которого подключен к информационному входу первого блока оперативной памяти, первый и второй выходы блока управления подключены к адресным входам первого блока оперативной памяти и блока постоянной па мяти соответственно, третий выход блока управления подключен к входу управления записью-считыванием первого блока оперативной памяти, четвертый выход блока управления подключен к синхронизирующему входу арифметического блока, содержит второйблок оперативной памяти, причем пятыйи щестой выходы блока управления подключены соответственно к адресномувходу и входу управления записью-считыванием второго блока оперативнойпамяти, седьмой и восьмой выходы блока управления подключены к входам обращения первого и второго блоков оперативной памяти соответственно, выход второго блока оперативной памяти подключен к входу операндов арифметического блока, причем блок управления содержит узел синхронизации,два триггера, и-разрядный счетчик(п=1 о, М; М - объем выборки),(п+1)разрядный регистр итераций, узел элементов И, узел Формирования инверсного кода, элемент И, два вычитателя,два (и+ 1)-разрядных кольцевых регистра сдвига и узел блокировки, причемпервый выход узла синхронизации подключен к счетному входу первого триггера, выход которого подключен к счетному входу второго триггера, первомувходу элемента И и к информационнымвходам первых разрядов первого и второго кольцевых регистров сдвига, прямой выход второго триггера подключенк входу счетчика, вычитающему входупервбго вычнтателя и к первому входуузла блокировки, инверсный выход второго триггера подключен к вычитающему входу второго вычитателя и к второму входу узла блокировки, параллельный выход счетчика подключен кпервому информационному входу узлаэлементов И, к информационному входуузла формирования инверсного кода ик третьему входу узла блокировки,выход переполнения счетчика подключен к входу управления сдвигом регистра итераций, параллельный выходрегистра итераций подключен к второму информационному входу узла элементов И, выход первого разряда регистра итераций подключен к управляющему входу узла элементов И, к второмувходу элемента И и к четвертому входуузла блокировки, выход (и+1)-го разряда регистра итераций подключен кпятому входу узла блокировки, выходузла Формирования инверсного кодаподключен к суммирующим входам первого и второго вычитателей, выходыкоторых поразрядно подключены к инфор 1056206мационным входам разрядов с второгопо (и+1)"ый первого и второго кольцевых регистров сдвига соответственно, входы управления сдвигом перяо 1 ои второго кольцевык регистров сдвига 5подключены соответственно к первомуи второму выходам узла блокировки,выходы второго кольцевого регистрасдвига, узла элементов И, прямой выход второго триггера, второй выходузла синхронизации, выход первогокольцевого регистра сдвига, инверсный выход второго триггера, третийи четвертый выходы узла блокировкиявляются выходами блока управления с, 15первого по восьмой соответственно,Кроме того, узел блокировки содержит элементы ШБ 1-НЕ, ИЛИ, НЕ, три сумматора по модулю два, два эле" 20 мента И-НЕ, шесть элементов И и триггер, причем вход элемента НЕ является четвертым входом узла блокировки и соединен с первыми входами первого сумматора по модулю два и элемента ,25 ИЛИ, второй вход первого сумматора по модулю два является пятым входом узла блокировки, входы элемента ИЛИНЕ с первого по и-ый являются соответствующими разрядами третьего вхо," да узла блокировки, причем и-ый вход элемента ИЛИ-НЕ соединен с инверсным входом триггера, выход элемента НЕ подключен к первым входам первого и второго элемента И-НЕ, а также первого и второго элементов И, выход элемента ИЛИ-НЕ подключен к второму входу элемента ИЛИ, выход которого подключен к первым входам тре" тьего и четвертого элементов И, вторые входы третьего и четвертого элементов И являются соответственно первым и вторым входами узла блокировки, выход третьего элемента И подключен к второму входу первого элемента И ид 45 к прямому выходу пятого элемента И, выход четвертого элемента И подключен к второму входу второго элемента И и к прямому входу шестого элемента И, инверсные входы пятого и шестого элементов И подключены к выходу первого сумматора по модулю два, выходы пятого и шестого элементов И являются соответственно третьим и четвертым выходами узла блокировки, прямой и инверсный выходы триггера подключены к вторым входам первого и второго элементов И-НЕ соответственно, выходы первого и второго элементов И-НЕ подключены к первым входамвторого и третьего сумматоров по модулю два, вторые входы которых подключены к выходам второго и первогоэлементов И соответственно, выходывторого и третьего сумматоров по модулю два являются "оответственно вто:рым и первым выходами узла блокировки.На фиг. 1 представлена функциональная схема устройства для реализации безызбыточного алгоритма быстрого преобразования Фурье; на фиг.2 функциональная схема блока управления; на фиг. 3 - функциональнаясхема узла блокировки,Устройство содержит арифметическийблок 1, блок 2 постоянной памяти,блоки 3 и 4 оперативной памяти,блок 5 управления, включающий узелэлементов И 6, регистр 7 итераций,счетчик 8, триггеры 9 и 10, узел 11синхронизации, узел 12 формированияинверсного кода, элемент И 13, узел,14 блокировки, вычитатели 15 н 16и кольцевые 17 и 18 регйстры сдвига. Узел блокировки содержит элементы И-НЕ 1 9, элементы И 20-22, сумматоры 23 по модулю два, элемент:;НЕ 24, сумматор 25 по модулю два,элемент И 11 И 26, триггер 27 и элемент ИЛИ-НЕ 28,"Устройство для реализации безызбыточного алгоритма БПФ работаетследующим образом.Четыре действительные последовательности входных отсчетов представляются как две комплексные, причем одна комплексная последовательность расположена в первом блоке 3оперативной памяти (ОП) в двоичноинверсном порядке, а другая - во втором блоке 4 ОП в прямом порядке. Блок 5 управления (БУ 7 вырабатывает коды адресов операндов, выбирае мых из первого 3 или второго 4 блоков ОП и поступающих в арифметический блок 1, предназначенный для вычисления элементарных операций БПФ вида А + ВР, где А и В - значения двух точек участвующих в преобразовании согласно направленному графу БПФ с постоянной структурой, а У - значения экспоненциальных множителей, хранящихся в блоке 2 постоянной памяти (ПП 1 и считываемых по кодам адресов также вырабатываемых БУ 5. При этом первый 3 и второй 4 блоки ОП работают в режимах считывание-запись и запись-считывание соответственноДва операнда А и,В выбираются иэ первого блока 3 ОП и подвергаются элементарному преобразовании БПФ в арифметическом блоке 1. Операнды С и О выбираются из второго 4 блока ОП и одновременно в первый блок 3 ОП переписываются операнды, ранее выбранные иэ второго 4 блока ОП и преобразован- О ные в арифметическом блоке 1. Далее преобразованные операнды А и В переписываются из арифметического блока 1 во второй блок 4 ОП операнды С и О подвергаются преобразованию, 5 , а из первого блока 3 ОП считываетсяеследующая пара операндов, Преобразованные операнды С и О эаносятся в первый блок 3 ОП, считываютсяоперанды из второго блока 4 ОП, а 2 О преобразованию подвергается. следующая после А и В пара операндов ит.д. Данный порядок обработки сохраняется для всех последующих выбираемых операндов, Таким образом, 25 первый 3 и второй 4 блоки ОП обмениваются информацией, причем во время обмена осуществляется вычисление элементарного преобразования БПФ. После окончания очередной итерации Бу перестраивается и обеспечивает выбор операндов из блоков ОП согласно изменяющемуся направлению графа БПФ. После завершения итераций БПФ осуществляется дополнительная итерация, необходимая при реализации безызбы 35 точного алгоритма, Вычисленные величины - спектры действительных последовательностей на положительных частотах последовательно считывают 40 ся с выхода арифметического блока 1, причем вначале считываются спектры последовательностей, представленных как действительная часть, а затем - спектры последовательностей, представленных как мнимая часть комп.. 45 лексных входных данных.Блок управления 5 устройства работает следующим образом.Перед началом вычислений регистр 7 итераций, счетчик 8 и триггеры 9 и 10 устанавливаются в нулевое состоякие. Выходы триггера 9 являются выходами блока управления и определяют режим работы первого 3 и второго 4 блоков ОП ("О" - считывание, "1" - 55 запись) . На управляющем входе узла 12 формирования инверсного кода ус,танавливается потенциал "О" и сигналы с выходов разрядов счетчика 8 поступают на суммирующие входы вычитателей 15 и 16 беэ инвертирования, навычитающих входах которых сигналы свыходов триггера 9 определяют соответственно режимы Перезапись кода в регистр" и Перезапись кода в регистр с вычитанием единицы". Низкий или высокий потенциалы на первом и втором выходах узла 4 блокирования определяют режимы работы регистров 17 и 8"Перезапись кода прямо" или "Перезапись кода с кольцевым сдвигом вправо на один разряд" соответственно. На третьем и четвертом выходах узла блокирования формируются сигналы запрещения обращения к блокам ОП (высокий потенциал) и разрешения обращения низкий потенциал), Запрещение обращения осуществляется при появлении на первом и шестом выходахБУ 5 кодов адресов, по которым вблоки ОП записываются первые два операнда на первой итерации БПФ, Длявсех остальных итераций 811 Ф сигналзапрещения обращения не вырабатывает.ся. Кроме того, при осуществлениидополнительной итерации перепаковкизапрвщается запись информации в ячейки блоков ОП,При поступлении тактовых импульсов на вход триггера 1 О его состояние, а также состояние триггера 9,счетчика 8 и регистра итераций 7 изменяется. Сигналы с выходов разрядовсчетчика 8 через узел 12 в прямом илиинверсном коде поступают на входывычитателей 15 и 16, где происходитвычитание единицы иэ младшего разряда кода адреса записи второго. блока 4 ОП, а затеи первого блока 3 ОП соответственно. Коды адресов с выходов разрядов вычитателей 15 и 16 поступают на информационные входы первого 7 и второго 18 регистров сдвига, Кроме того, на входы первых разрядов регистров 17 и 18 поступают сигналы с выхода триггера 10, состояние которого в зави симости от потенциалов на первом и втором выходах узла 14 блокирования записывается либо в первый разряд регистра на управляющем входе О"), либо в последний разряд регистра при сдвиге всей информации в сторону младших разрядов на одини разряд (на управляющем входе 1 ). При выполнении первой итерации БПФ на третьем и четвертом выходах узла 14блокирования появляются сигналы "1",запрещающие обращение к блокам ОП во время гейерирования кодов записи первых пар операндов. На после- дующих операциях БПФ сигнал запре щения обращения не вырабатывается,Коды адресов записи и считывания операндов для первого 3 и второго 4 блоков ОП приведены в табл.1.После окончания итераций БПФ на 10 выходе первого разряда регистра итераций 7 появляется .сигнал "1". При этом на управляющих входах регистров 17 и 18 формируется высокий потенциал, а иа третьем и четвер том выходах узла 14 в .сигналы запрещения записи в блоки ОП. В этом режиме осуществляется перепаковка информации, хранящейся в блоках ОП.Коды адресов считываемых операн п дов приведены в табл.2 (здесь, как и в табл.1, коды адресов соответствуют восьмиточечному направленному графу БПФ).Формирование кодов адресов обра щения к блоку 2 постоянной памяти(ПП) осуществляется группой узлов: узел элементов И б, счетчик 8 и регистр итераций 7, который работает в режиме занесения "1" в старший. раэ 1 ряд при сдвиге всей информации в сторону младших разрядов. Сдвиг и занесение информации, осуществляется по сигналу перехода состояния старшего разряда счетчика 8 из "1" в 1 лиДля восьмиточечного БПФ коды адресов обращения к блоку 2 ПП приведены в табл.З,Предложенное устройство для реа- . лизации безызбыточного алгоритма БПФ обладает широкими функциональными возможностями при увеличении быстродействия и высокой эффективности использования арифметического блока устройства. В сравнении с известными устройствами для случая совместной обработки группы действительных последовательностей данных предложенное устройство имеет повышенное в два раза быстродействие, что достигается полной синхронностью .работы блоков оперативной памяти и арифметического блока управления, При этом эффективность использования арифметического блока является максимальной.. - Режим работы Считывание Запись Считывание Запись 000 00 ОЗУКод 110 адреса Запись Режим работы Считы- Записьванне Считы-.вание ОЗУ.2 Код 001 000 110 адреса Продолжение табв 2.11 РежимСчитывание Запись Считывание Запись работы 010 011 ОЗУ 1 Код 101 100 адреса Запись СчитываСчиты- Записьванне Режим работы ние 01 010 ОЗУ 2 Код 100 101 адреса Таблица 3 Итерация 00 00 00 Коды адресов 01 00 00 обращения 10 . 10 00 10 00 к блоку 2 ПП