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

(51 4 С 06 Р 15/3 ПИСАНИЕ ИЗОБРЕТЕНИ МУ СВИДЕТЕЛЬСТВ ВТО Бил. У 32олитехнический инстисо М. 1 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Цифровые диаметры и устройстваобработки сигналов на интегральныхмикросхемах: Справочное пособие (Выцкий Ф.Б., Алексеев В.И. и др.).Радио и связь, 1984.Рабинер Л., Гоулд Б. Теория иприменение цифровой обработки сигналов, М,: Мир, 1978, с. 680-686,фиг. 10.36.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С ОСНОВАНИЕМ 6(57) Изобретение относится к техникецифровой обработки сигналов и можетбыть использовано в системах связи,при анализе речевых сигналов и двумерных изображений, Цель изобретенияупрощение устройства. Поставленнаяцель достигается за счет того, что всостав устройства входят входной преобразователь 1, выходные преобразователи 2, элементы задержки 3-7, коммутаторы 8, элементы задержки 9-13,арифметические блоки 14, входы 15 задания коэффициентов, блок синхронизации 16 и соответствующие связи между узлами устройства. 1 э.п. ф-лы,4 ил.56 2ния получаем операнд А. С выхода умножителя 21 операнд - ЬКЗ поступает также на умножитель 22, с выхода которого снимается операнд В, Преобразованные операнды через коммутатор 8 (Фиг, 1) загружаются в элемент 9 задержки, Через каждые (К)Б/6 тактов, где К=2,6, коммутатор совершает перекоммутацию и следующие операнды загружаются в элементы 10-13 задержки, причем последние Б/6 отсчетов посту-. пают непосредственно на пятый вход арифметического блока 14, на первый шестой, второй, четвертый и третий входы которого в это время поступают операнды соответственно с элементов 9-13 задержки, а на седьмой - одиннадцатый входы арифметического блока с входов 15 поступают коэффициенты СфР, причем С=с-й/3, а П=-2 й/13, где С - действительная часть, а й - мнимая часть поворачивающего множителя.Арифметический блок начинает вычисление первой итерации преобразования, Он реализует вычисление по правилу: где Кр=М,1 13341Изобретение относится к цифровойобработке сигналов и может быть использовано в системах связи, при анализе речевых сигналов и двухмерныхизображений,Цель изобретения - упрощение устройства,На фиг. 1 приведена блок-схемаустройства; на фиг. 2 - блок-схемаарифметического блока; на фиг. 3 -блок-схема входного преобразователя;на фиг. 4 - блок-схема выходного преобразователя.Устройство содержит входной преобразователь 1, выходные преобразователи 2, элементы 3-7 задержки, ком"мутаторы 8, элементы 9-13 задержки(на 5 Б/6 тактов 7 и 9, на 4 Ю/6 тактов 6 и 10, на ЗН/6тактов 5 и 11,на 2 Б/6 тактов 4 и 12 на Н/6 тактов3 и 13), арифметические блоки 14,входы 15 задания коэффициентов, блок16 синхронизации.Арифметический блок (фиг, 2) содержит узел 17 двухточечной базовойоперации, узлы 18 трехточечной базовой операции, умножители 19 комплексных чисел.Входной преобразователь (фиг. 3)содержит сумматор 20, умножитель 2130на 1/3 и умножитель 22 на 2,Выходной преобразователь (фиг, 4)содержит сумматор 23, умножитель 24на 1/2 и умножитель 25 на 3,Устройство работает следующим образом,Обрабатываемые операнды,а+Ь (а -действительная часть операнда; Ь -мнимая часть операнда) последовательно поступают во входной преобразователь 1 (Фиг. 1), где осуществляетсяпереход из обычной комплексной плоскости С(1) в новую плоскостьК(р)щА+рВ; А, ЕЕ Е), - реальные числа;- комплексный кубический корень единицы, причем А=а-Ь/ ГЗ," а В=-2 Ь/3.Преобразование осуществляется сле дующим образом.Мнимая часть входного операндапоступает на умножитель 1 (фиг. 3), выполняющий умножение на константу - 1/ 13, С выхода умножителя 21 полу ченный операнд - Ъ/К 3 поступает на вход сумматора 20, на другой вход которого поступает действительная часть входного операнда. После суммирова" К(0)=И,+ Ы,;Я (ш) =Р С +1,й 1+Д 11,0+Н(С -11)3,110 Мф 7 ь+Р 2+7)+НИ+02+ф)11+ф 1 (ф 2 З З) ф(С 2 2 9 )11 р 1 = ( - +С -С )+/(С - + -С )2 2 1 2 2 1 2 3 9операнды на выходах первогоузла трехточечной базовойоперации, а 1"1 +1 - ()+(+Н ) М +И= (1.-Н +1 +Н) + Р (Н,+1 2-Н 2-1.); М,+И,-(1.,;1.+Н;Н,)+, (Н;11, Н,)операнды на выходах второго узла трехточечной базовой операции,+/С=(А с+АЗ )+ (Во+В 2 ) 112 )Ь 2 - (А 2+А)+8(В 2+В );Р +С =(А +А)+р.(В +В,) - операнды на первых выходах узлов двухточечной базовой операции, а 1 +ин,=(А,-А)+с(В-В);,1 д 2+РН 2 (А 2-А )+ и(В 2-В К) 11 +)Н=(А -А,)+М(В -В) - операнды на вторых выходах этих узловА +фВ (1=0,5) - операнды на (3+1)-ивходе арифметического блока,Вычисление производится следующимобразом.ш= ф у 45 50 М 1) +Х (С -Э). зС первого входа арифметического блока операнд А + В, поступает на первый вход узла 17 (фиг, 2), на второй вход которого в это время с третьего входа арифметического блока поступает операнд А +рВ .Полученные операнды Р +иС, ц=1,3 с первых выходов узлов двухточечных базовых операций поступают на и-й . вход первого узла 18 трехточечной базовой операции (фиг. 2), а операнды Ь +С с вторых выходов узлов двухточечных базовых операций поступают на и -й вход второго узла 18 трехточечной базовой операции. На выходе канала действительной частоты операн-. дов первого выхода узла трехточечной базовой операции, а также на выходе канала действительной части операндов первого выхода арифметического блока получаем сумму М =РР +РНа выходе канала мнимой части опе рандов первого выхода узла трехточечной базовой операции получаем сумму и т.д.с 30Второй узел трехточечной базовой операции работает аналогично первому.Операнды с второго и третьего выходов первого и с первого - третьего выходов второго узлов трехточечных базовых операций (фиг. 2) поступают соответственно на первые входы первого - пятого комплексных умножителей, на вторые входы которых поступают с входа коэффициента устройства коэффициенты40 уричем действительная часть операндаМ с действительного канала первоговхода ю-го комплексного умножителяпоступает на первый вход умножителя18, на второй вход которого с каналадействительной. части .операндов второго входа комплексного умножителяпоступает С . На выходе канала действительной части операндов (ш+1)-говыхода арифметического блока получаем сумму М С+О ИНа выходе канала мнимой части опе рандов (ш+1)-го выхода арифметического блока получаем сумму Отсчеты с первого выхода арифметического блока 4 (фиг. ) поступают на первый вход коммутатора второго каскада 8, с второго - шестого выходов поступают соответственно черезэлементы 3-7 задержки второго каскада, на второй - шестой входы коммутатора 8 второго каскада, который осуществляет переключения с периодомМТопереключения Т = -- . Отсчеты с пер 36вого - пятого выходов коммутатора 8второго каскада поступают соответственно"через элементы 9-13 задержкивторого каскада на первый - пятыйвходы арифметического блока 14 второго каскада, с шестого выхода коммутатора 8 второго каскада отсчетынепосредственно поступают на шестойвход арифметического блока 14 второгокаскада, который начинает вычислятьвторую итерацию БПФ, Коэффициентыпоступают с входов задания коэффициентов на входы коэффициента арифметического блока 14, Работа арифметического блока 14 второго каскада аналогична работе арифметического блока14 первого каскада. С выходов арифметического блока 14 второго каскадаотсчеты поступают на элементы третьего каскада и так далее до М-го каскада, Порядок работы каждого иэ нихполностью аналогичен работе второгокаскада, отличается только частотапереключений коммутатора, Периодработы коммутатора для -го каскадасоставляет ЮТ,/6.Для последнего каскада период переключений коммутатора 8 равен Т,С выхода М-го арифметического блока 14 операнды поступают в выходные преобразователи 2, где осуществляется переход из новой плоскости К(р) в обычную комплексную плоскость С(1).Причем действительная часть а=А-В/2,а мнимая Ь=-13 В/2, Преобразованиеосуществляется следующим образом.Выходные операнды А+рВ поступают на входы выходных преобразователей(фиг. 4), причем В поступает на умно- житель 24 на -1/2,2 с выхода которого - В/2 поступает на вход умножителя 25 на 3 , с выхода которого снимается мнимая часть отсчета Ь=-1 ГЗВ/2, -В/2 с выхода умножителя 24 поступает также на второй вход сумматора 23, на первый вход которого поступает А, После суммирования получаем на выхо1. Устройство для вычисления быстрого преобразования Фурье с основанием 6, содержащее блок синхронизации, М (М 1 оя, У - размер преобразования)10 каскадов, каждый из которыг, кроме М-го,содержит коммутатор, первую и вторую группы иэ шести элементов задержки и ариФметический блок, а М-й каскад содержит коммутатор арийметиУ 15 ческий блок и группу из шести элементов задержки, причем в -м (з.=1, М) каскаде г-й (1=1,5) выход коммутатора подключен к входу г-го элемента задержки первой группы, выход которо-го подключен к входу г-го операнда20 арифметического блока, выход 6-го операнда (3=2,6) которого подключен к входу ( К)-го элемента задержки второй группы шестой выход коммутаУ 25 тора подключен к входу шестого операнда арифметического блока а в М-м каскаде г-й выход коммутатора подключен к входу 1-го элемента. задержки группы, выход которого подклгочен к входу г-го операнда арифметического,30 блока, вход шестого операнда которого подключен к шестому. выходу коммутатора, выход первого результата арифметического блока и выход г-го элемента задержки второй группы -го каскада подключены соответственно к первому и Я+1)-му информационным ходам коммутатора (+1)-го каскада, р-й выхоц (р 1,М) блока синхронизации подключен к управляющему входу коммутатора р-го каскада, вход кяэффициеггта арифметического блока р- го каскада является входом задания р-го коэффи" циента устройства, о т л и ч а ю щ е" е с я тем, что, с целью упрощения, оно содержит входной преобразователь и шесть выходных преобразователей, причем первый и второй информационные входы коммутатора первого каскада подключены соответственно к пер вому и второму выходам входного преобразователя, первый и второй входы которого являются входами соответственно реальной и мнимой частей входных отсчетов устройства, Б-ми (Б= 55 =1,Ь) выходами реальной и мнимой ча. -стей результата которого являютсясоответственно первый и второй выходы Б-го выходного преобразователя,5 1331де сумматора 23 действительную частьотсчета. Формула и зо брет ения5 56 6 первый и второй входы которого подключены к выходам соответственнореальной и мнимой частей Б-го резуль.тата арифметического блока М-го каскада, при этом входной преобразователь содержит сумматор, умножительна 2 и умножитель на 1/ ГЗ, выход которого подключен к входу умножителяна 2 и первому входу сумматора, выход которого является первым выходомвходного преобразователя, вторым выходом которого является выход умножителя на 2, а первым и вторым входами входного преобразователя являютсясоответственно второй вход сумматораи вход умножителя на. 1/113, причемБ-й выходной преобразователь содержит сумматор, умножитель на гЗ и умножитель на 1/2, выход которого подключен к входам умножителя на3 ипервому входу сумматора, выход которого является первым выходом Б-говыходного преобразователя, вторым выходом которого является выход умножителя на ГЗ, а первым и вторым входами Б-го выходного преобразователяявляются соответственно второй входсумматора и вход умножителя на 1/2,2, Устройство по и, 1, о т л и ч а ю щ е е с я тем, что арифметический блок каждого каскада содержит три узла двухточечной базовой операции, два узла трехточечной базовой операции и пять умножителей комплексных чисел, причем первый и второй входы первого узла двухточечной базовой операции подключены соответственно к входам первых операндов первого и второго узлов трехточечной базовой операции, входы вторых операндов которых подключены соответственно к первому и второму выходам второго узла двухточечной базовой операции, первый и второй выходы третьего узла двухточечной базовой операции подключены к входам третьего операнда соответственно первого и ,второго узлов трехточечной базовой операции, третий выход второго; второй выход первого, первый выход второго, третий выход первого и второй выход второго узлов трехточечной базовой операции подключены к первым входам соответственно первого, второго, третьего, четвертого и пятого умножителей комплексных чисел, выходы которых являются выходами соответственно второго, третьего, четверто334156 10 Оиг Составитель А.Барановдактор Е.Копча Техред Д,Попович Корректор С.Ше Подписноемитета СССР аказ 3964/4 Тираж 672 НИИПИ Государ по делам изо 3035, Москва, твенногоретений иЖ, Рауш к ая наб. Производственно-полиграфическое предприятие, г. Ужгород роектна го, пятого и нестого результатоварифметического блока, выходом первого результата которого являетсяпервый выход первого узла трехточечной базовой операции, первый входпервого, второй вход третьего, первый вход второго, второй вход первого, первый вход третьего и второйвход второго узлов двухточечной базовой операции являются входами соответственно первого, второго, третьего,четвертого, пятого и пестого операндов арифметического блока, входом коэффициента которого являются соединенные между собой вторые входы первого, второго, третьего, четвертого,пятого и шестого умножителей комплексных чисел.