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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) (10 А 1 6 Р 15/3 БРЕТЕНИ ИСА 951811/24-21.07.85704.87, Бдесский пол В 13ехнический инсти А.А. Назаретоян тельство СССРР 15/332, 1982.Б. Теория и приаботки сигналов. адцать ожител относи и сигнал эями. 5 ил. ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ СКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С ОСНОВАНИЕМ 3(57) Изобретение тся к обласцифровой обработк ов и може быть использовано при анализе речевых сигналов и двумерных изображений.Цель изобретения - упрощение устройства. Поставленная цель достигаетсяза счет того, что в состав устройства входит М (М = 1 ояэ Я, М - размерпреобразования) коммутаторов, М арифметических блоков, блок постояннойпамяти, две группы из М элементов за"держки, две группы из Мэлементовзадержки, четыре сумматора, умножитель на (-1/3), умножитель на 3, триумножителя на (-1/2), три умножителяна 3, причем арифметический блок содержит десять элементов НЕ, четырн сумматоров и восемь умн ей с соответствующими свя1302292Изобретение относится к цифровой обработке сигналов и может быть ис- д пользовано при анализе речевых сигналов и двумерных изображений. тЦелью изобретения является упро С щение устройства. о уст- комвход блокна го На фиг.1 приведена блок-схема ройства; на фиг.2 - схема работы мутаторов, на фиг.3 - блок-схема ного преобразователя; на фиг.4 - схема выходного преобразователя; фиг,5 - блок-схема арифметическо блока. Устройство содержит входной преобразователь 1, коммутатор 2, элемент 3 задержки на 2 И/3 тактов,элемент 4 задержки на И/3 тактов, арифметический блок 5, элементы 6 и 7 задержки на И/9 тактов, элементы 8 и 9 задержки на 2 И/9 тактов, коммутатор 10, арифметический блок 11, элемент 12 задержки на И/27 тактов, элемент 13 задержки на 2 И/27 тактов, комму татор 14, элемент 15 задержки на 2 И/3 (х=1,М), тактов, элемент 16 задержки на И/3 тактов, арифметический блок 17, элемент 18 задержки на И/3 " тактов, элемент 19 задержки 30 на 2 И/3 тактов, коммутатор 20,элемент 21 задержки на 2 такта, элемент 22 задержки на 1 такт, арифметический блок 23, выходные преобразователи 24- 26, блок 27 постоянной памяти.Входной преобразователь (фиг.З) содержит умножитель 28 на (- 1/43) сумматор 29, умножитель 30 на 3. Выходной преобразователь (фиг.4) содерф 0 жит умножитель 31 на (- - ), сумматор 32, умножитель 33 на "13.Арифметический блок (фиг,5) содержит элементы НЕ 34-43, сумматоры 44-57 и умножители 58-65.Устройство работает следующим образом.Обрабатываемые отсчеты а+1 Ъ,где а - действительная часть отсчета,Ь мнимая часть, последовательно поступают во входной преобразователь 1 (фиг. 1), где осуществляется переход из обычной комплексной плоскости С(З) в новую плоскость К(р) =А+Вр; А,В б К, К означает реальные числа, а р - комплексный кубический корень единицы. Причем А = а - Ь/.5, а В = = -2 Ь/ ГЗ2Преобразование осуществляется слеующим образом,Мнимая часть входного отсчета посупаег на умножитель на - 1/-ГЗ (фиг.З)выхода умножителя 28 полученныйперанд на -1/ГЗ Ь поступает на второй вход сумматора 29, на первыйвход которого поступает действительная часть отсчета. После суммирования получают операнд А. Свыхода умножителя 28 операнд - 1/-ГЗ.Ьпоступает на умножитель 30, с выходакоторого снимается операнд В. Преобразованные отсчеты через коммутатор 2 (фиг,1) загружаются в элемент3 задержки, через И/3 тактов коммутатор 2 совершает перекоммутацию посхеме, изображенной на фиг.2, и следующие И/3 отсчетов загружаются вэлемент 4 задержки. Через 2 И/3 тактов коммутатор совершает вторую перекоммутацию и последние И/3 отсчетов поступают непосредственно на третий вход арифметического блока 5,напервый и второй входы которого в этовремя поступают отсчеты с элементов3 и 4 задержки, а на четвертый и пятый входы арифметического блока 27постоянной памяти поступают поворачивающие множители С+рР, причем С =с-й/.3, а 0 = - 2 й/-3, где С - действительная часть, а 0 - мнимая частьповорачивающего множителя,арифметический блок начинает вычисление первой итерации преобразования.Действительная часть операнда Ас действительного канала первого входа арифметического блока (фиг,5) поступает на первый вход трехвходовогосумматора 46, на второй и третий вхо.ды которого с действительных каналов,второго и третьего входов арифметического блока поступают действительные части операндов А и Аз, На выходе канала действительной части операндов первого выхода арифметического блока получают сумму А 1+А +Аз. На входы трехвходового сумматора 47 с мнимых каналов первого, второго и третьего входов арифметического блока поступают мнимые части операндов В В и В. На выходе канала мнимой части операндов первого выхода арифметического блока получают сумму В,+В+Вэ. Вз поступает также на вход элемента НЕ 38, с выхода которого В поступает на вход сумматора 45, на первый вход которого пос3 130229 тупает А. С выхода сумматора 46 А - В поступают на вход элемента НЕ 39, с выхода которого В -А з поступают на вход трехвходового сумматора 48. В поступает также на вход элемента НЕ 37, с выхода которого В поступает на вход трехвходового сумматора 48, на другой вход которого поступает А 1. На выходе трехвходового сумматора 48 получим сумму Р = А-В+В-А Аэ 10 поступает также на вход элемента НЕ 35, с выхода которого А поступает на вход трехвходового сумматора 49. С выхода элемента НЕ В поступает на вход сумматора 44, на другой вход ко торого поступает АС выхода сумматора 44 А -В поступают на вход трехвходового сумматора 49, на другой вход которого поступает В,. На выходе трехвходового сум матора 49 получим сумму Е = В,+А - -В-Аэ. А поступает также на вход элемента НЕ 36, с выхода которого А поступает на вход трехвходового сумматора 50, на другой вход которого с выхода элемента НЕ 38 поступает Вэ, а на другой вход - А. На; выходе трехвходового сумматора 50 получим сумму Н = А,-А -В. С выхода сумматора 44 А - В поступают также на 30 вход элемента НЕ 37, с выхода которого В - А поступают на вход трехвходового сумматора 51, на другой вход которого с выхода сумматора 45 поступают А - Вэ, а на другой вход - 35 В На выходе трехвходового сумматора 51 получают сумму С = В, +В-А+Вэ. Сумма с выхода трехвходового сумматора 48 поступает на вход умножи теля 58, на другой вход которого с канала действительной части операндов входа арифметического блока поступает С, . С выхода умножителя 58 С, Р поступает на вход сумматора 52 45 Сумма Е с выхода трехвходового сумматора 49 поступает на вход умножителя 59, на другой вход которого с канала мнимой части операндов арифметического блока поступает Р с выхода умО ножителя 59 Э,Е поступает на вход элемента НЕ 40, с выхода которого -ЭЕ поступает на вход сумматора 52, На выходе сумматора, а также на выходе канала действительной части операндов второго выхода арифметического блока получают сумму С, Р-П, Е. Сумма Р поступает также на вход умножителя 60, на другой вход которого пос 2 4тупает 0. С выхода умножителя 60 Р,Р поступает на вход сумматора 53. О, поступает также на вход элемента НЕ 4 1, с выхода которого - Р поступает на вход сумматора 57, на другой вход которого поступает С, . С выхода сумматора 57 С-Р, поступает на вход умножителя 61, на другой вход которого поступает сумма Е. С выхода умно- жителя 61 Е (С 1-П,) поступает на вход сумматора 53, На выходе сумматора 53, а также на выходе канала мнимой части операндов арифметического блока получают сумму 0,Р + (С-ЭГ) Е.Сумма Н с выхода трехвходового сумЮматора 50 поступает на вход умножителя 62, на другой вход которого с канала действительной части операндов арифметического блока поступает С С выхода умножителя 62 С Н поступает на вход сумматора 56. Сумма С с выхода трехвходового сумматора 51 поступает на вход умножителя 63, на другой вход которого с канала мнимой части арифметического блока поступает В. С выхода умножителя 63 0 С поступает на вход элемента НЕ 42, с выхода которого - Э С поступает на вход сумматора 56. На выходе сумматора, а также на выходе канала действительной части операндов арифметического блока получают сумму С Н - 0 С.Сумма Н поступает также на вход умножителя 64, на другой вход которого поступает й . С выхода умножителя 64 0 Н поступает на вход сумматора 55. Р поступает также на вход элемента НЕ 43, с выхода которого - Р поступает на вход сумматора 54, на другой вход которого поступает С . С выхода сумматора 54 С-Р поступает на вход умножителя 65, на другой вход которого поступает сумма С. С выхода 1умножителя 65 С (С -0 ) поступает на вход сумматора 55. На выходе сумматора, а также на выходе канала мнимой части операндов арифметического блока получают сумму Э,Н + (С 0 ) 6.Отсчеты с первого выхода арифметического блока 5 (фиг.1) поступают на первый вход коммутатора 10, с второго и третьего выходов поступают соответственно через элементы 6 и 8 задержки на второй и третий входы коммутатора 10, который осуществляет переключения в соответствии с фиг.2 с периодом переключения Т = . От 1302292счеты с первого и второго выходовкоммутатора 10 поступают соответственно через элементы 9 и 7 задержки напервый и второй входы арифметического блока 11, с третьего выхода коммутатора 10 отсчеты непосредственнопоступают на третий вход арифметического блока 11, который начинает вычислять вторую итерацию БПФ,Работа арифметического блока 11 10аналогична работе арифметическогоблока 5. С выходов арифметическогоблока 11 второго каскада отсчеты пос -тупают на элементы третьего каскадаи так далее до М-го каскада. Порядокработы каждого из них полностью аналогичен работе второго каскада. Отличается только частота переключенийкоммутатора. Период работы коммутатора для -го каскада составляет 20ит,/3 .Для последнего каскада период переключений коммутатора 20 равен Т.С выхода М-го арифметического блока 23 отсчеты поступают в выходныепреобразователи 24-26, где осуществляется переход из новой плоскостиК(р) в обычную комплексную плоскостьС(3). Причем действительная частьа = А - В/2, а мнимая часть Ь = -ЗВ/2,30Преобразование осуществляется следующим образом,Выходные отсчеты А + рВ поступаютна входы выходных преобразователей.Причем В поступает на умножитель 31 35на -1/2, с выхода которого - В/2 поступает на вход умножителя 33 на 3,с выхода которого снимается мнимаячасть отсчета Ь = - -ГЗ В/2. - В/2 с.выхода умножителя 31 поступает также на второй вход сумматора 32, напервый вход которого поступает А.После суммирования получают на выходесумматора 32 действительную часть отсчета а = А - В/2. 45Формула изобретенияУстройство для вычисления быстрого преобразования Фурье с основанием 3, содержащее М (М = 1 оя И, И - размер преобразования) коммутаторов, М арифметических блоков, блок постоянной памяти, первую и вторую группы из М элементов задержки в каждой, третью и четвертую группы из (М) элементов задержки в каждой, причем первый и второй выходы х-го (1=1,М) коммутатора подключены к входам 1.-х элементов задержки соответственно первой и второй групп, выходы которых подключены к входам соответственно первого и второго операндов -го арифметического блока, вход третьего операнда которого подключен к третьему выходу 1-го коммутатора, выходы первого, второго и третьего результатов 3-го (3=1,М) арифметического блока подключены соответственно к первому информационному входу (3+1)-го коммутатора, входу 3-го элемента задержки третьей группы и входу 1-го элемента задержки четвертой группы, выходы 3-х элементов задержки третьей и четвертой групп подключены соответственно к второму и третьему информационному входам (1+1)-го коммутатора, 1-й выход блока постоянной памяти подключен к управляющему входу 1-го коммутатора, а (1+М)-ый выход блока постоянной памяти подключенк входу задания коэффициентов 1-го арифметического блока, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит четыре сумматора, умножитель на (- 1/.ГЗ), умножитель на 3, три ум 1ножителя на (- в ) и три умножителя2на -3, выход умножителя на (- 1/43) подключен к первому входу первого сумматора и входу умножителя на З,выход которого объединен с выходом первого сумматора и подключен к информационному входу первого коммутатора,а второй вход первого сумматора и вход умножителя на (1/ ГЗ) объединены и являются информационным входом устройства, выход щ-го (щ=1,3) умножителя1на (- в ) подключен к первому входу2(щ+1)-го сумматора и входу щ-го умно- жителя на ГЗ, выход которого объединен с выходом (щ+1)-го сумматора и является щ-м выходом результата устройства, второй вход (щ+1)-го сумматора объединен с входом щ-го умножи 1теля на (- в ) и подключен к выходу2щ-го результата М-го арифметического блока, причем 1-й арифметический блок содержит десять элементов НЕ, четырнадцать сумматоров и восемь умножителей, при этом выход первого элемента НЕ подключен к первым входам первого и второго сумматоров,/выход первого сумматора подключен к входу второго элемента НЕ и первому входу третьего сумматора, выход которогоподключен к первым входам первого ивторого умножителей, выходы которыхподключены соответственно к входутретьего элемента НЕ и первому входучетвертого сумматора, второй вход которого подключен к выходу третьегоумножителя, первый вход которого соединен с первым входом четвертого умножителя и подключен к выходу второгосумматора, второй вход которого подключен к выходу четвертого элемента НЕ, вход которого соединен с первым входом пятого сумматора и подключен к выходу шестого сумматора, первыйвход которого соединен с первым входом седьмого сумматора и подключен квыходу пятого элемента НЕ, выход шестого элемента НЕ подключен к второмувходу седьмого сумматора, выход которого подключен к первым входам пятого 20и шестого умножителей, выходы которых подключены к первым входам соответственно восьмого и девятого сумматоров, вторые входы которых подключены соответственно к выходу седьмого элемента НЕ и выходу седьмого умножителя, первый вход которого подключен к выходу десятого сумматора,первый вход которого подключен к выходу восьмого элемента НЕ, выход вто- З 0рого элемента НЕ подключен к второмувходу пятого сумматора, выход которого подключен к второму входу седьмого умножителя и первому входу восьмого умножителя, выход которого подключен к входу седьмого элемента НЕ,первый.и второй входы одиннадцатого сумматора подключены к выходу четвертого умножителя и выходу третьего элемента НЕ, второй вход второго умножи-. 40теля подключен к выходу двенадцатогосумматора, первый вход которого подключен к выходу девятого элемента НЕ,выход десятого элемента НЕ подключенк второму входу третьего сумматора, 45второй вход четвертого умножителясоединен с вторым, входом двенадцатого сумматора, второй вход третьего умножителя соединен с входом девятогоэлемента НЕ, второй вход пятого умножителя соединен с вторым входом десятого сумматора, второй вход восьмого ,умножителя соединен с вторымвходом шестого умножителя и входомвосьмого элемента НЕ, третий входсумматора соединен с третьим входомтретьего сумматора и первым входомтринадцатого сумматора, второй и третйй входы которого соединены с входами соответственно первого и пятогоэлементов НЕ, третий вход седьмогосумматора соединен с третьим входомвторого сумматора и первым входом четырнадцатого сумматора, второй входкоторого соединен с вторым входомпервого сумматора и входом шестогоэлемента НЕ, а третий вход четырнадцатого сумматора соединен с входомдесятого элемента НЕ и вторым входомшестого сумматора, при этом вторыевходы первого, четвертого, пятого ишестого умножителей объединены и являются входом задания коэффициентаустройства, выходы тринадцатого и четырнадцатого сумматоров объединены иявляются выходом первого результатаарифметического блока, выходы четвер"того и одиннадцатого сумматоров объединены и являются выходом второгорезультата арифметического блока,выходы восьмого и девятого сумматоровобъединены и являются выходом третьего результата арифметического блока,третьи входы тринадцатого и четырнадцатого сумматоров объединены иявляются входом первого операндаарифметического блока, входы первого и шестого элементов НЕ объединены и являются входом второгооперанда арифметического блока,входы пятого и десятого элементовНЕ объединены и являются входомтретьего операнда арифметическогоблока.1302292 Фиг.Л фи иг. 5 оставнтель А. Барановехред А.Кравчук Корректор Т, Колб актор А. Шанд Заказ 1218/49 5 роизводственно-полиграфическое предприятие, г. Ужгоро Проектная Тираж 673 ВНИИПИ Государстве по делам изобрет 3035, Москва,. Ж"35Подписноеного комитета СССРний и открытийРаушская наб д.