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

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