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

(594 С АНИЕ ИЗОБРЕТЕНИЯСКОМУ СВИДЕТЕЛЬСТВУ 18енина политех 50-летия Велиистической ре.Кравец,и Б.А.НекраБ. Теория и аботки сигн тво СССР/332, 1982 ОСУДАРСТВЕНКЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(;71) Киевский орденанический институт им.кой Октябрьской социалволюции(54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯБЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к областивычислительной техники и макет бытьиспользовано при построении специализированных устройств, выполняющихалгоритм быстрого преобразованияфурье по основанию 4. Цель изобретения - повьвнение быстродействия. Всостав устройства входит умножителькомплексных чисел, шестнадцать регистров и четыре сумматора с соответствующими связями между ними. 1 ил.2315131ственно н регистры множимого и множителя умножителя комплексных чисел1.1-1,8 (здесь.и далее будем считать,что прием в регистры осущестнляетсяв начале такта по фронту синхроимпульса). На ныходах матричных умножителей 1.13-1.16 появляются резульХ. д Р(1)1 + Р(1 + 1) 1 ++ Р(1 + 2)(-1) + Р(з. + 3) 3,где Р(1) " Х, И, з = Г-Т,х" - исходные отсчеты;И - весовые коэффициенты,Х - результаты выполненияэлементарной операции БПФВыражение (1) может быть представлено в виде: КеХ,КеР(з) + КеР( + 2) ++ КеР( + 1) - КеР(з. + 3)11 тпХ, = ТлпР(з.) + 1 тпР(з. + 2)1С 1 шР(1 + 1) + 1 птР(1 + 3)3;1 птх. йптР(1) 1 шР(1 + 2-КеР(з. + 1) - КеР(1 + 3)3,В первом такте работы устройстваосуществляется прием операнда х(1)и весового коэффициента М;соответ 1Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, выполняющих алгоритм быстрого преобразования Фурье (БПФ) по основанию 4.Целью изобретения является повышение быстродействия устройства.На чертеже представлена структурная схема предлагаемого устройства.Арифметическое устройство для быстрого преобразования Фурье содержит умножитель 1 комплексных чисел, состоящий из регистров 1.1-1.8, умножителей 1.9"1, 12, регистров 1. 13- 1.16 и сумматоров 1.17-1.18, регистры 2-7, сумматоры 8-9, регистры 10- 19, сумматоры 20-21, тактовый вход 22 устройства.Арифметическое устройство процессора БПФ выполняет элементарную операцию алгоритма БПФ по основанию 4Ъ вида: О 15 20 25 таты произведения соответствующих частей комплексных чисел; КеХ,КеИ,;, 1 тпх(х) 1 пЯ ,; Кех(д) 1 пЮ;, 1 тпх(д) Кем которые во втором такте принимаются в промежуточные регистры 1.13-1.16. Во втором такте в регистры 1.1-1.8 принимаются операнды х(з. + 2), И., , Сумматор 1.17 всегда выполняет операцию вычитания, а сумматор 1.18 - сложения и, следовательно, на выходах сумматоров 1.17 и 1.18 присутствуют величины:КеР(з) = Кех(з.) КеИ;- 1 вх(1)1 тпИ;, ; 1 птР(д) = Кех(з.) 1 шЫ , ++ 1 вх КейВ третьем такте в регистры 1.1- 1,8 принимаются операнды х(з. + 1) и Н, в регистры 1.13-1.16 - произве- дения Кех(д + 2) КЮ , 1 вх(з. + 2) х1 пЯ Кех(х + 2) 1 пЛ 41 птх( + 2) КеИ;н регистр 2 - величина КеР,н регистр 4 - величина 1 тпР(1).В четвертом такте в регистры 1.1- 1.8 принимаются операнды х(з + 3) и И , в регистры 1. 13-1. 16 - произведения Кех( + 1) И; 1 шх(з. + + ) 1 пй., ; Кех(з. + 1) 1 вУ.,+,+ 41 1 тпх(з. + 1) КеИ., , и регистр 3 - величина КеР( з. + 2); в регистр 3- величина 1 шР(з. + 2), в регистр 6 - из регистра 2 величина КеР(з.), в регистр, 7 - из регистра 4 величина 1 птР(з.), сумматоры 8 и 9 выполняют операцию сложения. В пятом такте в регистры 1.1-1.8 принимаются исходные операнды для выполнения следующей базовой операции х(х + 4) и У ;, в регистры 1.13- 1.16 - произведения Кех(з + 3) КеУ ;1 вх(х + 3) 1 пЯ , Кех( + 3) 1 шМ 1 птх(з + 3)- КеЧ , в регистр 2 - величина КеР(х + 1),н регистр 4 " величина 1 вР( + 1), в регистр 1 О - величина тКеР(з.) + КеР(з. + 2)1, в регистр 15 - величина Г 1 вР(з.) + 1 тпР(з.+ + 2 И, сумматоры 8 и 9 выполняют операцию вычитания.Арифметическое устройство для быстрого преобразования Фурье, содержащее умножитель комплексных чи 3 123В шестом такте в регистры 11-1.8принимаются операнды х(1 + 6) . и Ув регистры 1.13"1.16 - произведенияКех( + 4) КеИ., ; 1 пи( + 4) 1 пИ,Кех(з. + 4)1 пЯ., ; 1 тпх(з. + 4) КеЫ. ;в регистр 3 - величина КеР(1 + 3),в регистр 4 - величина 1 шР(1 + 3), врегистр 6 - величина КеР(1 + 1), врегистр 7 - величина .1 пзР( + 1),в регистр 12 - величина 1 КеР(1) - 1 О- КеР(1 + 2)1, в регистр 17 - величина 11 пзР(з) - 1 пзР(д + 2) . Сумматоры 8 и 9 выполняют операцию сложения.В седьмомтакте в регистры 1.1- 151.8 принимаются операнды х( + 5) иИ, , в регистры 113-1.16 - произ+5,з фведения Кех(з. + 6) КеН;, .; 1 шх(1 ++ 3)з . Сумматоры 8 и 9 выполняют операцию вычитания, сумматор 1 О - сложение содержимого регистров 1 О и 12,сумматор 21 - сложение содержимогорегистров 15 и 17, В результате навыходе сумматора 20 получаем Кех(1),а сумматора 21 - 1 тпх(з.).В восьмом такте в регистры 1,11.8 принимаются операнды х(1 + 1) иН; , в регистры 1.13-1.16 - произведения Кех(з. + 5) КеУ;,и 1 тпх(з. ++ 7) КеУ;, , в регистр 2 принимает 513 4ся величина КеР(1 + 5), в регистр 4 - величина 1 шР(з + 5), в регистр 10 - величина ГКеР(з. + 4) + КеР( + 6)3, в регистр 15 - величина 11 тпР(з. + 4)+ + 1 шР(з. + 6)1, сумматоры 8 и 9 выполняют операцию вычитания, сумматор 20 выполняет вычитание содержимого регистров 18 и 14, сумматор 21 - сложение содержимого регистров 19 и 13, В результате на выходах сумматоров 20 и 21 получаем величины Кех(1 + 1) и 1 пи( + 1) соответственно.На десятом такте в регистры 11- 1.8 принимаются операнды х(з. + 10), И, , в регистры 1,13-1,16 - произведения Кех(1 + 8) КеЮ;,и , 1 шх(+ + 8) 1 пЮп.; Кех(д + 8) 1 пйп 1 тпх(з. + 8) КеИ , в регистр 3 принимается величийа КеР(1 + 7)в регистр 5 - величина 1 пзР(з. + 7), в регистр 6 - величина КеР(1 + 5), в регистр 7 - величина 1 тпР( + 5),в регистр 12 - величина КеР(1 + 4) - КеР(1 + 6 И, в регистр 17 - величина. Г 1 шР(1 + 4) - 1 шР(1 + 6)3, суйматоры 8 и 9 выполняют операцию сложения, сумматор 20 выполняет сложение содержимого регистров 18 и 14,сумматор 21 - вычитание содержимогорегистров 19 и 13. В результате навыходах сумматоров 20 и 21 получаемвеличины Кех(1 + 3) и 1 пи(ь + 3) соответственно. На одиннадцатом .такте в регистры 1.1-1.8 принимаются операнды х( + + 9) и И ;, в регистры 1.13-1.16- произведения Кех(1 + 9) КеМ з 1 пи(1 + 9) 1 пЛ 4 Кех(з.+ Й1 пй.; 1 шх(1 + 9) КеУп , в регистр 2 принимается величйна КеР(1+ + 8), в регистр 4 - величина 1 шР(з. + + 8), в регистр 11 - величина КеР( + 5) + КеР(т + 7 Ц, в регистр 16 - величина ГЕшР(з. + 5) + 1 шР( + 7)3, сумма-.оры 8 и 9 выполняют операцию вычитания, сумматоры 20 и 21 - операцию сложения соДержимого регистров 10 и 12, 15 и 17 соответственно,В результате на выходе получаем х(д + 4).Далее работа устройства продолжается аналогичным образом. Формула изобретения123 1513 Закаэ 2653/53 Тираж 671 Подписно В иэводств. -полиграф. пред-е, г, Ужгород, ул. Проектна сел, первый, второй, третий и четвертый входы которого являются входамисоответственно реальной и мнимой частей операнда и реальной и мнимойчастей коэффициента устройства, первый, второй, третий и четвертый сумматоры, выходы третьего и четвертогосумматоров являются выходами соот"ветственно реальной и мнимой частейоперандов устройства, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, и него введенышестнадцать регистров, выход реаль,ной части умножителя комплексных чисел подключен к информационным входам первого и второго регистров, выходы которых подключены соответственно к первому входу первого сумматора и информационному входу третьего регистра, выход которого подключенк второму входу первого сумматора, выход которого подключен к информационным входам четвертого, пятого,шестого и седьмого регистров, выходыкоторых подключены соответственно кпервому входу третьего сумматора,первому входу четвертого сумматора,информационному входу восьмого регистра и второму входу четвертогосумматора, выходмнимой части умножителя комплексных чисел подключенк информационным входам девятого идесятого регистров, выходы которыхподключены соответственно к первомувходу второго сумматора и информа ционному входу одиннадцатого регистра, выход которого подключен к второму входу второго сумматора, выходкоторого подключен к информационнымвходам двенадцатого, тринадцатого, 15 четырнадцатого и пятнадцатого регистров, выходы которых подключены соответственно к первому входу третьего сумматора, информационному входушестнадцатого регистра, второму вхо О ду третьего сумматора и первому входу четвертого сумматора, выходы шестнадцатого и восьмого регистров подключены к вторым входам соответственно третьего и четвертого суммато ров, а тактовые входы шестнад.цати регистров обьединены, иявляются тактовым входом устройства.