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

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