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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРеспуБлик 55 9) Я ,Д. 1)5 6 06 32 РЕТЕНИ ВТОРСКОМУ ТЕЛЬСТВУ о-техноло- нницкого Я,Сохни СР СР 86. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ И(71) Специальное конструкторсгическое бюро "Модуль" Вполитехнического института(56) Авторское свидетельство ССЬЬ 1101858, кл, 0 06 Р 15/332, 19Авторское свидетельство ССМ 1242986, кл. 6 06 Е 15/332, 1(54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРА ЗОВАНИЯ ФУРЬЕ(57) Изобретение относится кной технике и предназначенония устройств обработкработающих в реальном масшЦель изобретения - повышенствия. Поставленная цель дсчет того, что в состав устроумножители 1 - 4, коммутатор10, сумматоры 11,12,13,14,15,16, сумматоры-вычитатегистры 19 - 22 и элемент НЕ 23 вычислительдля построеи сигналов, табе времени, ие быстродейостигается за йства входят ы 5 - 9, триггер вычитатели ли 17,18, ре- ,4 ил.1.моореспас: о носисн к вычислительной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени,Цель изобретения - повышение быстродействия устройства при обработке комплексно-сопряженных входных данных,Аналитическое выражение алгоритма вычисления коэффициентов преобразования Фурье комплексно-сопряженных входных данных можно представить в виде и - 1 и - 2 Р=( П Ст П 6)Х, 1( к+1к 0 и - к - 1М п - к2 0 0- 1 -2 где О - диагональная матрица, содержащая чисто вещественные диагональные коэффициенты:Р - матрица идеальной перестановки;Я - правоциркулярная матрица вида 9, 0 00 99 9. 0 , 0 О(5) 0 0 09 9 где Г = (то, т 1, т 2, тч) - вектор коэффитциентов преобразования Фурье;Х - вектор входных данных, обладающих свойством комплексного сопряжения,которое можно выразить соотношениемХ = Хи-,1=- 1,МП,где- символ комплексного сопряжения;Хо, Хчу 2 являются чисто вещественными числами;К - размерность преобразования.Оставшиеся члены выражения (1) описываются формулами;С= 2 л "эЮ/26 2 к, (2)Тк -" " 1 ф Ч к + "(3)6 =26 М Р 2" к, (4)где 1 - единичная матрица размерности;Ю 2 - матрица преобразования Фурьеразмерности два;а - символ кронекеровского произведения матриц;- символ траспонирования; Злемент г матрицы Я описывается выражением 9 = 1 +а, где а - число, равное основанию используемой системы счисления;=. К 5 Вычисление преобразования Фурье поформуле (1) выполняется в два этапа. На первом этапе производится умножение входного вектора Х на блочно-диагональные матрицы 6 . Результатом данного эта па является вектор промежуточных данныхХ, элементы которого являются вещественными числами.На втором этапе алгоритма (1) осуществляется выполнение итераций вычисления, 15 аналогичных классическому алгоритму быстрого преобразования Фурье, с той лишь разницей, что все операнды и коэффициенты являются чисто вещественными числами,Основой вычислительных затрат на пер вом этапе вычисления является процедураумножения промежуточного вектора данных Х или части его на матрицу 5 вида (5), при этом результат данного умножения обозначается вектором У, а элементы его 25 представляются в видеУ = 9 Х + 9 Хгщ, (б)гдеп означает приведение числа по модулю п;30гл - размерность матрицы Я;Х и Х ;-,п - элементы вектора Х.Обозначим Х через В, а Х ь 1 гп через Св результате выражение (б) примет вид Реу = ВеВ + йеС - а( щВ - еС);пУ =пВ+ тС+а(йеВ - КеС), (7)где п и йе - обозначают мнимую и вещественную части числа.Соотношение (7) следует трактовать каканалитическое выражение базовой операции первого этапа алгоритма (1) вычисленияпреобразования Фурье,На втором этапе вычисления по формуле(1) выполняется последовательность операций типа "бабочка":45 А. Х + Х.,.Ан = Х - Х;+ 1 сь (8)где Аь А- результаты выполнения операции типа "бабочка";с - элемент вещественной диагональ 50 ной матрицы О;Хь Х;+ - элементы некоторого промежуточного вектора данных,Объединение четырех операций (8) (подве операции с двух соседних итераций вычисления) при К = 4 позволяет получитьукрупненную базовую операцию, для выполнения которой потребуется четыре выходных операнда Х 1,Х 2,Хз и Х 4 и трикоэффициента 01,о 2 и дз, 16315565 15 20 25 30 35 40 45 50 55 На фиг,1 дана функциональная схема предлагаемого устройства; на фиг,2 - граф вычисления быстрого преобразования Фурье для й = 16; на фиг.З и 4 - структуры базовых операций в соответствии с выражениями (7) и (8),Устройство (фиг.1) содержит умножители 1 - 4, коммутаторы 5 - 9, триггер 10, сумматоры 11 - 13, вычитатели 1, - 16, сумматоры-вычитатели 17 и 18, регистры 19 - 22, элемент НЕ 23, входы 24-30, тактовый вход 31, вход 32 задания режима и информационные входы 33 - 36,Устройство работает следующим образом (фиг,2 - 4),В соответствии с графом вычисления дискретного преобразования Фурье фиг.2) вначале выполняется последовательность базовых операций фиг,З.Для этого на вход 32 устройства подается сигнал уровня "0", который поступает на адресные входы коммутаторов 5 и 6 и переводит их в режим передачи данных с первых входов на выходы. Кроме того, сигнал уровня "О" поступает на вход управления первого сумматора-вычитателя 17 и переводит его в режим вычитания данных, Приход указанного сигнала на вход элемента НЕ 23 инвертирует его, в результате сигнал высокого уровня с выхода элемента НЕ 23 поступает на вход управления второго сумматора-вычитателя 18 и переводит его в режим ".ложения операндов,На первом такте работы устройства на входы 24 и 25 подаются вещественные части первого и второго операндов базовой операции фиг.З, а на входы 27 и 28 поступают мнимые части первого и второго операндов соответственно. Через время, равное времени выполнения операции сложения и времени распространения сигнала через коммутатор, на выходах сумматора 11 и вычитателя 14 формируются результаты сложения и вычитания вещественных частей первого и второго операндов фиг,З, что обеспечивается подачей на сумматор 11 и вычитатель 14 вещественной части первого операнда с входа 24, а на другие входы первого сумматора 11 и первого вычитателя 14 с входа 25 устройства через вход первого коммутаторов 5 - вещественной части второго операнда.Аналогично на выходах сумматоров-вычитателей 17 и 18 формируются разность и сумма мнимых частей первого и второго операндов фиг,З соответственно. Это позволяет к концу первого такта работы устройства на входы регистров 19 и 20 подать сумму и разность вещественных частей первого и второго операндов, а на входы регистрое 21 и 22 - разность и сумму мнимых частей первого и второго операндов базовой операции фиг.З,По приходу тактового импульса на тактовые входы указанных регистров происходит запись в них операндов, находящихся на входах, а на входы 24,25.27 и 28 поступают входные операнды базовой операции фиг,З аналогично описанному.Кроме того, по приходу тактового импульса на тактовый вход триггера 10 на его выходе устанавливается сигнал уровня "0", поступивший на его вход в первом такте работы устройства, Сигнал уровня "0" с выхода триггера 10 поступает на управляющие входы коммутаторов 7,8 и 9 и переводит их в режим передачи данных с их входов на выходы,Это позволяет на втором такте работы устройства на выходе сумматора 13 получить результат сложения суммы мнимых частей, поступающей на вход сумматора 13 с выхода регистра 22 через вход коммутатора 9, и разности вещественных частей, поступающей на вход сумматора 13 с выхода регистра 20 через вход коммутатора 7,Код разности ве гцест вен н ых частей входных операндов поступает на вход коммутатора 7 со сдвигом на К разрядов, определяемых величину тривиального множителя а, На выходе вычитател 15 формируется разность суммы вещественных частей первого и второго операндов базовой операции фиг.З, поступающей на вход вычитателя 15 с выхода регистра 19, и разности мнимых частей первого и второго операндов, поступающей на вход вычитателя 15 с выхода регистра 21 через вход коммутатора 8, При этом на входе коммутатора 8 осуществляется умножение операнда на множитель а в соответствии со структурой базовой операции фиг.З. Таким образом, к концу второго такта работы устройства на выходах сумматора 13 и вычитателя 15 формируются соответственно мнимая и вещественная части результата выполнения базовой операции фиг,З, которые поступают на выходы 34 и 35 устройства, а на входы регистров 19 - 22 подаются промежуточные результаты выполнения базовой операции,По положительному перепаду очередного тактового импульса на входы 24,25,27 и 28 устройства поступают новые значения исходных операндов базовой операции фиг.З, в регистры 19 - 22 заносятся промежуточные результаты базовой операции, а с выходов 34 и 35 устройства считываются резул ьтаты вычислений.30 По приходу последующих тактовых импульсов описанные выше действия повторяются по аналогии вплоть до окончания выполнения первого этапа вычислений по алгоритму (1).На последнем такте выполнения базовой операции фиг.З на входах регистров 19 - 22 находятся промежуточные результаты выполнения данной базовой операции. С приходом очередного тактового импульса указанные промежуточные данные записываются в регистры 19-22; на выходы 34 и 35 устройства подаются мнимая и вещественная части выходного операнда базовой операции фиг.З, а на входы 24 и 25 поступают первый и второй операнды базовой операции фиг.4, на входы 26-29 устройства - соответственно первый коэффициент, третий и четвертый операнды, второй коэффициент базовой операции фиг.4,Кроме того,на вход 32 устройства подается сигнал уровня "1", который поступает на управляющие входы коммутаторов 5 и 6, вход элемента НЕ 23, вход управления сумматора-вычитателя 17 и вход триггера 10.Это приводит к установлению коммутаторов 5 и 6 в режим передачи данных с входа на выход, сумматора-вычитателя 17 - в режим сложения операндов, а сумматора-вычитателя 18 - в режим вычитания. В умножителях 1 и 2 осуществляется умножение второго и пятого операндов базовой операции фиг.4 на первый и второй коэффициенты соответственно. Результаты названных умножений с выходов умножителей 1 и 2 через входы коммутаторов 5 и 6 поступают на входы сумматора 11, вычитателя 14 и сумматоров-вычитателей 17 и 18.При этом на входы сумматора 11 и вычитателя 14 поступает первый операнд базовой операции фиг.5 входа 24 устройства, а на входы сумматоров-вычитателей 17 и 18 приходит третий операнд базовой операции фиг.4 с входа 27 устройства, что позволяет на выходах сумматора 11 и вычитателя 14, а также сумматоров-вычитателей 17 и 18 получить промежуточные результаты выполнения базовой операции фиг.4.В то же время на выходах 34 и 35 устройства формируются результаты выполнения базовой операции фиг.З.Длительность рассматриваемого такта работы устройства отличается от длительности предыдущих тактов работы устройства на первом этапе алгоритма (1) и равна:Ь сл + 1 ум + к,где 1 сл, Туев, Ск - время выполнения операции сложения, умножения и распространения сигнала через коммутатор,5 10 15 20 25 Таким образом, через время, равное Ь, после прихода последнего тактового импульса на вход 31 устройства поступает очередной тактовый импульс, по которому происходит запись промежуточных результатов вычисления базовой операции фиг.4 в регистры 19 - 22, выдача результатов выполнения базовой операции фиг,З на выходы 34 и 35 устройства, подача на входы 24 - 29 устройства входных операндов (по аналогии с описанным выше), а на вход 30 устройства - третьего коэффициента базовой операции фиг,4. Кроме того, сигнал уровня "1" с входа 31 устройства записывается в триггер 10 и поступает на управляющие входы коммутаторов 7,8 и 9, что переводит их в режим передачи данных с входов на выходы. В результате последнего структура устройства настраивается на выполнение базовой операции фиг,4, что позволяет через время, равное на выходах сумматоров 12 и 13, а также на выходах вычитателей 16 и 15, получить результаты выполнения базовой операции фиг.4. При этом в умножителях 3 и 4 получаются результаты умножения третьего и четвертого промежуточных результатов базовой операции фиг,4 на третий коэффициент, указанные результаты умножения через входы коммутаторов 8 и 9 поступают на входы сумматора 12, вычитателя 15 и сумматора 13, вычитателя 16 соответственно. На другие входы сумматора 12 и вычитателя 15 поступает промежуточный результат с выхода регистра 19, а на входы сумматора 13 и вычитателя 16 подается промежуточный результат вычисления с выхода регистра 20 через вход коммутатора 7.По приходу очередного тактового импульса на вход 31 устройства на входы 33-36 устройства поступают результаты выполнения базовой операции согласно фиг.4, в регистры 19-22 заносятся промежуточные результаты выполнения базовой операции фиг.4, а на входы 24-30 устройства поступают исходные операнды названной базовой операции.На последующих этапах работы устройство выполняет базовые операции фиг.4, после этого может быть переведено в режим выполнения базовой операции фиг,З,Ф о рмул а изобретения Арифметическое устройство для процессора быстрого преобразования Фурье, содержащее первый, второй, третий и четвертый умножители, два сумматора, два вычитателя, два сумматора-вычитателя, два коммутатора и четыре регистра, причем выход первого коммутатора подключен К первым входам первых сумматора ителей, а выходы вторых сумматора и вычитателя являются соответственно первым и вторым информационными выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены третий, четвертый и пятый коммутаторы, третий сумматор, третий вычитатель, триггер и элемент НЕ, выход которого подключен к управляющему входу второго сумматора-вычитателя, выход первого сумматора подключен к информационному входу первого регистра, выход которого подключен к первым входам вторых сумматора и вычитателя, выход первого вычитателя подключен к информационному входу второго регистра, выход которого подключен к первому информационному входу и со сдвигом на К разрядов (К - целое число) к второму информационному входу третьего коммутатора, выход которого подключен к первым входам третьих сумматора и вычитателя, выходы которых являются соответственно третьим и четвертым информационными выходами устройства, первым информационным входом которогО являются соединенные между собой вторые входы первых сумматора и вычитателя, выход первого сумматора-вычитателя подключен к информационному входу третьего регистра, выход которого со сдвигом на К разрядов подключен к первому информационному входу четвертого коммутатора и первому входу третьего умножителя, выход которого подключен к второму информационному входу четвертого коммутатора, выход которого подключен к вторым входам вторых сумматора и вычитателя, выход первого умножителя подключен к первому информационному входу первого коммутатора, вто 10 30 равляющим входам третьего, четвертого и35 пятого коммутатора, управляющие входы 40 15 20 25 рой информационный вход которого соединен с первым входом первого умножителя и является вторым информационным входом устройства, третьим информационным входом которого являются соединенные между собой вторые информационные входы первого и второго сумматоров-вычитателей, выход второго сумматора-вычитателя подключен к информационному входу четвертого регистра, выход которого подключен к первому информационному входу пятого коммутатора и первому входу четвертого умножителя, выход которого подключен к второму информационному входу пятого коммутатора, выход которого подключен к вторым входам третьих сумматора и вычитателя, выход второго умножителя подключен к первому информационному входу второго коммутатора, второй информационный вход которого соединен с первым входом второго умножителя и является четвертым информационным входом устройства, первым и вторым входами коэффициента которого являются вторые входы соответственно первого и второго умножителей, вторые входы третьего и четвертого умножителей соединены между собой и являются третьим входом коэффициента устройства, тактовым входом которого являются соединенные между собой тактовые входы первого, второго, третьего и четвертого регистров и тактовый вход триггера, выход которого подключен к уппервого и второго коммутаторов, первого сумматора-вычитателя, вход элемента НЕ и установочный вход триггера соединенымежду собой и являются входом заданиярежима устройства.1631556Фиг Фиг Составитель А.Баранов эктор А.Лежнина Техред М,Моргентал Корректор М.Шароши аказ 548 Тираж 403 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., 4/5Производственно-издательский комоинат "Патент", г, Ужгород, ул,Гагарина