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

)5 6 Об Р 15/33 ИЗОБРЕТЕН ВТОРСКОМУ ИДЕТЕЛ ЬСТВ 2(54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯЯ ХАРТЛ И-ФУРЬ Е(57) Изобретение относится к вычислительной технике и может быть использовано в ап пара- туре спектрального анализа и синтеза сигналов, Цель изобретения - повышение быстродействия. Устройство содержит блоки сложения-вычитания, коммутатор и умножители комплексных чисел. 1 табл., 2 ил.. (56) Авторское свидетельство СССРМ 1569847, кл, 6 06 Р 15/332, 1989,Авторское свидетельство СССРМ 1337904, кл. 6 06 Р 15/332, 1985,Изобретение относится к области вычислительной техники и может быть использовано в аппаратуре спектрального анализа и синтеза сигналов.Известно устройство быстрого действительного преобразования Хартли-Фурье, содержащее блок синхронизации, два счетчика адреса, блок постоянной памяти, четыре регистра, два умножителя, сумматорвычитатель, блок постоянной памяти и три коммутатора. В данном устройстве базовая операция алгоритма быстрого преобразования Хартли (БПХ) по основанию два выполняется за три такта. Недостаток известного устройства - низкое быстродействие,Наиболее близким по технической сущности к изобретению является устройство для выполнения быстрого преобразования Фурье, содержащее две группы блоков памяти, сумматор, вычитатель и умножитель комплексных чисел, два элемента задержки, три коммутатора, два счетчика, дешифратор, регистр, блок элементов И, блок постоянной памяти и блок синхронизации,Устроиство реализует алгоритм БПФ по основанию два с прореживанием по частоте. Для выполнения М-точечного БПФ необходимо выполнить й/2 о 92 М итераций. Недостаток известного устройства - низкое быстродействие.Цель изобретения - повышение быстродействия, Поставленная цель достигается тем, что в арифметическое устройство для выполнения быстрого преобразования Хартли-Фурье (БПХФ), содержащее два блока сложения-вычитания, коммутатор и умно- житель комплексных чисел, причем выход первого блока сложения-вычитания соединен с первым входом умножителя комплексных чисел, дополнительно введены четыре блока сложения-вычитания и второй умно- житель комплексных чисел, причем первый и второй входы третьего, четвертого, пятого и шестого блоков сложения-вычитания соединены с входами устройства с первого по восьмой соответственно, а их первые выходы соединены с выходами устройства с первого по четвертый соответственно, выходы ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССРкоторого с пятого по восьмой соединены с первым и вторым выходами первого и второго умножителей комплексных чисел соответственно, вторые входы которых соединены с первыми выходами коммутатора и второго блока сложения-вычитания соответственно, а их третьи и четвертые входы соединены с входами задания фазовых множителей устройства, управляющий вход устройс;ва соединен с управляющим входом коМмутатора; второй выход которого соединен с первым входом второго блока сложения-вычитания, первый и второй входы коммутатора соединены с вторыми выходами первого и второго блоков сложения-вычитания соответственно, первые входы которых соединены с вторыми выходами третьего и шестого, а вторые входы - с вторыми выходами четвертого и пятого блоков сложения-вычитания соответственно,При изучении других вариантов технических решений в данной области техники признаки, отличающие заявляемое устройство от прототипа, не были выявлены, что обеспечивает его соответствие критерию "существенные отличия",Сопоставимый анализ с прототипом показывает, что заявляемое устройство отличается наличием новых блоков: умножителя комплексных чисел и четырех блоков сложения-вычитания, а также наличием новых связей, что делает его соответствующим критерию "новизна".Схема арифметического устройства для выполнения БПХФ показана на фиг. 1. На фиг. 2 представлен граф алгоритма БПХ по расщепленному основанию два-четыре с прореживанием по частоте на основе предложенной базовой операции,Устройство содержит информационные входы 1-8, управляющий вход 9, входы 10-13 задания фазовых множителей, блоки 14-19 сложения-вычитания, коммутатор 20, умно- жители 21, 22 комплексных чисел, информационные выходы 23-30,Входы устройства 1, 3, 5, 7 соединены с первыми входами соответственно блоков 14, 15, 16, 17 сложения-вычитания, а входы 2, 4, 6, 8 - с вторыми входами соответственно блоков 14, 15, 16, 17, первые выходы которых соединены с выходами 23, 24, 25, 26 устройства соответственно, вторые выходы блоков 14, 15 сложения-вычитания соединены соответственно с первым и вторым входами блока 18, вторые выходы блоков 17, 16 соединены соответственно с.первым ивторым входами блока 19, первый выходкоторого соединен с вторым входом умно- жителя 22, первый вход которого соединенс выходом коммутатора 20, входы которого соединены с вторыми выходами блоков 18,19, а второй его выход соединен с вторымвходом умножителя 21, первый вход которого соединен с первым выходом блока 18,5 первые и вторые выходы умножителей 21,22 соединены соответственно с выходами27, 28, 29, 30 устройства, входы 10, 11, 12, 13которого соединены соответственно стретьими и четвертыми входами умножите 10 лей 21, 22, управляющий вход коммутатора20 соединен с входом 9 устройства.Базовая операция алгоритмов БПХ и.БПФ по расщепленному основанию два-четыре с прореживанием по частоте описыва 15 ется следующей системой уравнений;а =а+е;Ь =Ь+1;д =д+Ь;с =с+д;г =(а - е)+(Ь - т); ц =(а - е) - (Ь - );гз=(д - Ь) - (с - д); сз =(д - Ь)+(с- д);е =гСч +(Уц 1+Угз)Яч; 1 =20 = г 1 Яч - (Усс+ УфСч,д = (У з+ Уя)Ср + цзЗр; Ь == (Угз + Уч)Яч - цэСчгде а, Ь, с, д, е, 1, д, Ь - входы устройства;а, Ь, с, д, е, Г, д, Ь - выходы устрой 25 ства;У - значение сигнала на управляющемвходе коммутатора (У = О, 1),Здесь См= соз(2 юг/М), Яч= зп(2 лг/К),Устройство работает следующим обра 30 эом,По информационным входам 1-8 в устройство поступают входные числа. По входам 10-13 поступают фазовые множители.На блоках 14-19 сложения-вычитания, каж 35 дый из которых содержит сумматор и вычитатель, выполняются операции сложения ивычитания в соответствии с выражением: 1=1+а;в = - гл, 1, 140где, пч - входы блока;1, в - выходы блока,, 1Коммутатор 20 пропускает поступающие на его входы данные прямо или накреств зависимости от значения сигнала У на 45 входе 9 устройства, Если У = О, то данныеидут прямо, если У = 1 - накрест.На умножителях 21, 22 комплексных чисел выполняются операции умножения поступающих из блоков 18, 19 и коммутатора 50 20 чисел на фазовые множители в соответствии с выркажениями:к, - зк зк.а = Бч - щСч: е =Яи - еСчгде гп - входы умножителей;1, в - выходы умножителей;Сч, М - фаэовые множители, поступающие по входам 10-13.Первое выражение реализуется на умножителе 21, второе - на умножителе 22,1795473 25 Порядок выполнения алгоритмов БПХ и БПФ на основе предложенной базовой операции определяется графом алгоритма, На фиг, 2 показан граф алгоритма БПХ по расщепленному основанию два-четыре с про реживанием по частоте для й = 32.Базовая операция на графе обозначена прямоугольником, внутри которого первая цифра указывает значение управляющего сигнала У, вторая и третья в порядке сверху 10 вниз определяют значения параметров К и й, используемых для ввозлка фазовых множителей Си, Яи, Си, Яи1Для К = 1,М/8-1 эти множители принимают значения Сы = сов(2 лК/К), Яи = 15К К =зп(27 г К/М), Си = соз 2 л ЗК/М), Ям = зп(2 л ЗК/М), а для К = 0 при И 8 (третья цифра равна размерности преобразования М они соответственно равны: О, 1, - 2/2 и 2/2. На последнем этапе преобразования на некоторые входы подаются нули (обозначены О), а некоторые выходы не используются. На этом этапе с помощью базовой Формула изобретения Арифметическое устройство для выполнения быстрого преобразования ХартлиФурье, содержащее первый и второй блоки сложения-вычитания, коммутатор и умно- житель комплексных чисел, причем выход первого блока сложения-вычитания соеди-. нен с первым входом умножителя комплексных чисел, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в нег". дополнительно введены с третьего по шестой блоки сложения-вычитания и второй умножитель комплексных чисел, причем первый и второй входы третьего, четвертого, пятого и шестого блоков сложения-вычитания соединены с входами операндов устройства с первого по восьмой соответственно, а их выходы суммы соединены с выходами результата устройства с первого по четвертый соответственно, выходы результата которого с пятого по восьмой соединеоперации реализуются четырехточечные и пары двухточечных преобразований. Первые иэ них обозначены тройкой параметров 1, О, 4, а вторые О, О, 2, которые реализуются с фазовыми множителями, равными 1 для четырехточечного преобразования, и 1/2, для двух двухточечных, Порядок связей между входами и выходами базовых операций показан на фиг. 2.Быстродействие предложенного арифметического устройства для выполнения БПХФ определяется как сумма времени выполнения одного. умножения комплексных чисел и двух сложений, что только на одну операцию сложения больше, чем в устройстве-прототипе, что несущественно, В таблице приведено количество базовых операций при выполнении Ь 1 - точечного (М =2, и =5,12) алгоритма БПХ на предложенном устройстве и устройстве-прототипе, а также выигрыш по быстродействию, При выполнении алгоритма БПФ выигрыш по быстродействию аналогичен,ны с первым и втор м выходами первого и второго умножителей комплексных чисел соответственно, вторые входы которых соединены с первым выходом коммутатора и выходом суммы второго блока сложения-вычитания соответственно, третьи и четвертые входы первого и второго умножителей комплексных чисел соединены соответственно с первого по четвертый входами задания фазовых множителей устройства, уп равляющий вход устройства соединен с управляющим входом коммутатора, второй выход которого соединен с первым входом второго блока сложения-вычитания, первый и второй информационные входы коммутатора соединены с выходами разности первого и второго блоков сложения-вычитаний соответственно, первые входы которых соединены с выходами разности третьего и шестого,а вторые входы - с выходами разности четвертого и пятого блоков сложения-вычитания соответственно.1795473 х орректор И.Шмаков Т,Ивано ктор аз 4 ВН тиям ори ГККТ СССР до Д6 Хт Я 13 Хф Хц Ъ Составитель А,МельникТехред М.Моргентад Тираж ПодписноПИ Государственного комитета по изобретениям и откры113035, Москва, Ж-З 5, Раушская наб., 4/5 изводственно-издательский комбинат Патент", г, Ужгород, ул.Гагарина, 101 21 3 ,Ц