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

 

Изобретение относится к области цифровой обработки сигналов и может быть использовано при анализе речевых сигналов и двумерных изображений. Цель изобретения - упрощение устройства . Поставленная цель достигается за счет того, что в состав устройства входит М (М log, N, N - размер преобразования) коммутаторов, М арифметических блоков, блок постоянной памяти, две группь из М элементов задержки , две группы из М-1 элементов задержки, четыре сумматора, умножитель на (-1/-|3), умножитель на 3, три умножителя на (-1/2), три умножителя на 3, причем арифметический блок содержит десять элементов НЕ, четырнадцать сумматоров и восемь умножителей с соответствующими связями . 5 ил. 1(Л 00 о N3 ND -О N3

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) А1 (5D 4 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМЪГ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3951811/24-24 (22) 11.07.85 (46) 07 ° 04.87. Бюл. 11 13 (71) Одесский политехнический институт (72) М.Б. Свердлик, А.А. Назаренко, В.Л. Евсеев и С,П. Стоян (53) 681.32 (088.8) (56) Авторское свидетельство СССР

У 1107132, кл. G 06 F 15/332, 1982.

Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов.

М;: Мир, 1978. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С ОСНОВАНИЕМ 3 (57) Изобретение относится к области цифровой обработки сигналов и может быть использовано при анализе речевых сигналов и двумерных изображений.

Цель изобретения — упрощение устройства. Поставленная цель достигается за счет того, что в состав устройства входит М (М = log> N, N — размер преобразования) коммутаторов, М арифметических блоков, блок постоянной памяти, две группы из М элементов задержки, две группы из М-1 элементов задержки, четыре сумматора, умножитель на (-1/Г3), умножитель на 3, три умножителя на (-1/2), три умножителя на 3, причем арифметический блок содержит десять элементов НЕ, четырнадцать сумматоров и восемь умножителей с cooTHетствук)щими связями. 5 нл.

1 1302292

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

Целью изобретения является упро- 5 С щение устройства. о усткомвход 10 блокна

На фиг.1 приведена блок-схема ройства; на фиг.2 — схема работы мутаторов, на фиг.3 — блок-схема ного преобразователя, на фиг.4— схема выходного преобразователя; фиг.5 — блок-схема арифметическо блока.

Устройство содержит входной преобразователь 1, коммутатор 2, элемент 3 задержки на 2N/3 тактов,элемент 4 задержки на N/3 тактов, арифметический блок 5, элементы 6 и 7 задержки на N/9 тактов, элементы 8 и

9 задержки íà 2N/9 тактов, коммутатор

10, арифметический блок 11, элемент

12 задержки íà N/27 тактов, элемент

13 задержки на 2N/27 тактов, комму- 25 татор 14, элемент 15 задержки на

2N/3 (i=1,M), тактов, элемент 16 задержки на N/3 тактов, арифметический блок 17, элемент 18 задержки на

И/3 тактов, элемент 19 задержки 30 на 2N/3 тактов, коммутатор 20,элемент 21 задержки на 2 такта, элемент

22 задержки на 1 такт, арифметический блок 23, выходные преобразователи 2426, блок 27 постоянной памяти.

Входной преобразователь (фиг.3) содержит умножитель 28 на (- 1/ 13), сумматор 29, умножитель 30 на 3. Выходной преобразователь (фиг.4) содер1 40 жит умножитель 31 на (- — ), сумматор 32, умножитель 33 на -13.

Арифметический блок (фиг.5) содержит элементы НЕ 34-43, сумматоры

44-57 и умножители 58-65.

Устройство работает следующим образом.

Обрабатываемые отсчеты a+jb,где а — действительная часть отсчета,Ь мнимая часть, последовательно поступают во входной преобразователь.1 (фиг. 1), где осуществляется переход из обычной комплексной плоскости

C(j) в новую плоскость R(p) = А+Вр;

А,B G R), R означает реальные числа, а — комплексный кубический корень единицы. Причем А = а — Ь/ 3 а В =

= -2Ь/-K

Преобразование осуществляется слеующим образом.

Мнимая часть входного отсчета посупаег на умножитель на - 1/-ГЗ (фиг.З) выхода умножителя 28 полученный перанд на -1/ ГЗ Ь поступает на второй вход сумматора 29, на первый вход которого поступает действительная часть отсчета. После суммирования получают операнд А. С выхода умножителя 28 операнд — 1/-13.Ь поступает на умножитель 30, с выхода которого снимается операнд В. Преобразованные отсчеты через коммутатор 2 (фиг.1) загружаются в элемент

3 задержки, через N/3 тактов коммутатор 2 совершает перекоммутацию по схеме, изображенной на фиг.2, и следующие N/3 отсчетов загружаются в элемент 4 задержки. Через 2N/3 тактов коммутатор совершает вторую перекоммутацию и последние N/3 отсчетов поступают непосредственно на третий вход арифметического блока 5,на первый и второй входы которого в это время поступают отсчеты с элементов

3 и 4 задержки, а на четвертый и пятый входы арифметического блока 27 постоянной памяти поступают поворачивающие множители C+pD, причем С = с-d/- 3, à D = — 2d/ 3, где С вЂ” дейI ствительная часть, а D — мнимая часть поворачивающего множителя,арифметический блок начинает вычисление первой итерации преобразования.

Действительная часть операнда А с действительного канала первого входа арифметического блока (фиг.5) поступает на первый вход трехвходового сумматора 46, на второй и третий вхо-ды которого с действительных каналов. второго и третьего входов арифметического блока поступают действительные части операндов А и А . На выходе канала действительной части операндов первого выхода арифметического блока получают сумму A1@Az+A>.

На входы трехвходового сумматора

47 с мнимых каналов первого, второго и третьего входов арифметического блока поступают мнимые части операндов В, В и В . На выходе канала мнимой части операндов первого выхода арифметического блока получают сумму В,+В +В . В поступает также на вход элемента НЕ 38, с выхода которого В поступает на вход сумматора 45, на первый вход которого пос3 130229 тупает А . С выхода сумматора 46 А —

В поступают на вход элемента НЕ 39, с выхода которого В -А поступают на вход трехвходового сумматора 48. В поступает также на вход элемента НЕ

37, с выхода которого-В поступает на вход трехвходового сумматора 48, на другой вход которого поступает А1.

На выходе трехвходового сумматора

48 получим сумму F = A -В +В -А А> 10 поступает также на вход элемента НЕ 35, с выхода которого А> поступает на вход трехвходового сумматора 49. С выхода элемента НЕ В поступает на вход сумматора 44, на другой вход ко- 15 торого поступает А

С выхода сумматора 44 А -В поступают на вход трехвходового сумматора

49, на другой вход которого поступает В,. На выходе трехвходового сум- 20 матора 49 получим сумму Е = В,+А—

-В -А . А поступает также на вход элемента НЕ 36, с выхода которого А поступает на вход трехвходового сумматора 50, на другой вход которого с выхода элемента НЕ 38 поступает В> а на другой вход — А<. На; выходе трехвходового сумматора 50 получим сумму Н = А,-А -В . С выхода сумматора 44 А — В поступают также на 30 вход элемента НЕ 37, с выхода которого  — А поступают на вход трехвходового сумматора 51, на другой вход которого с выхода сумматора 45 поступают А — В, а на другой вход — 35

В,. На выходе трехвходового сумматора 51 получают сумму С = В, +В -А +В .

Сумма с выхода трехвходового сумматора 48 поступает на вход умножи- 40 теля 58, на другой вход которого с канала действительной части операндов входа арифметического блока поступает С, . С выхода умножителя 58

С, F поступает на вход сумматора 52.. 45

Сумма Е с выхода трехвходового сумматора 49 поступает на вход умножителя

59, на другой вход которого с канала мнимой части операндов арифметического блока поступает D<,, с выхода ум-50 ножителя 59 D E поступает на вход элемента НЕ 40, с выхода которого

-D

На выходе сумматора, а также на выходе канала действительной части операндов второго выхода арифметического блока получают сумму С, F-П, Е. Сумма F поступает также на вход умножителя 60, на другой вход которого пос2 4 тупает D<. С выхода умножителя 60

D F поступает на вход сумматора 53.

D поступает также на вход элемента

НЕ 4 1, с выхода которого — D поступает на вход сумматора 57, на другой вход которого поступает С, . С выхода сумматора 57 С<-DI поступает на вход умножителя 61, на другой вход которого поступает сумма Е. С выхода умножителя 61 Е (С<-D,) поступает на вход сумматора 53, На выходе сумматора 53, а также на выходе канала мнимой части операндов арифметического блока получают сумму D,F + (С -Dy) E<.

Сумма Н с выхода трехвходового сумю матора 50 поступает на вход умножителя 62, на другой вход которого с канала действительной части операндов арифметического блока поступает С

С выхода умножителя 62 С Н поступает на вход сумматора 56. Сумма G с выхода трехвходового сумматора 51 поступает на вход умножителя 63, на другой вход которого с канала мнимой части арифметического блока поступает

13 д. С выхода умножителя 63 0 С поступает на вход элемента НЕ 42, с выхода которого — D С поступает на вход сумматора 56. На выходе сумматора, а также на выходе канала действительной части операндов арифметического блока получают сумму С Н вЂ” 0 С.

Сумма Н поступает также на вход умножителя 64, на другой вход которого поступает П . С выхода умножителя

64 D Н поступает на вход сумматора 55.

D поступает также на вход элемен2 та НЕ 43, с выхода которого — D поступает на вход сумматора 54, на другой вход которого поступает С . С выхода сумматора 54 С -D поступает на вход умножителя 65, на другой вход которого поступает сумма G. С выхода

I умножителя 65 G (С -D ) поступает на вход сумматора 55. На выходе сумматора, а также на выходе канала мнимой части операндов арифметического блока получают сумму Э,Н + (С 0 ) С.

Отсчеты с первого выхода арифметического блока 5 (фиг.1) поступают на первый вход коммутатора 10, с второго и третьего выходов поступают соответственно ° через элементы 6 и 8 задержки на второй и третий входы коммутатора 10, который осуществляет переключения в соответствии с фиг.2 с

ХТ. периодом переключения Т„ = . От1302292 счеты с первого и второго выходов коммутатора 10 поступают соответственно через элементы 9 и 7 задержки на первый и второй входы арифметического блока 11, с третьего выхода ком— мутатора 10 отсчеты непосредственно поступают на третий вход арифметического блока 11, который начинает вычислять вторую итерацию БПФ.

Работа арифметического блока 11 аналогична работе арифметического блока 5. С выходов арифметического блока 11 второго каскада отсчеты пос— тупают на элементы третьего каскада и так далее до М-ro каскада. Порядок работы каждого из них полностью аналогичен работе второго каскада. Отличается только частота переключений коммутатора. Период работы коммутатора для х-го каскада составляет 20

Ит,/3 .

Для последнего каскада период переключений коммутатора 20 равен Т

С выхода M-го арифметического блока 23 отсчеты поступают в выходные преобразователи 24-26, где осуществляется переход из новой плоскости

R(p) в обычную комплексную плоскость

С()). Причем действительная часть а = А — В/2, а мнимая часть b = -3B/2.30

Преобразование осуществляется следующим образом.

Выходные отсчеты А + рВ поступают на входы выходных преобразователей.

Причем В поступает на умножитель 31 35 на -1/2, с выхода которого — В/2 поступает на вход умножителя 33 на 3, с выхода которого снимается мнимая часть отсчета Ь = — --ГЗ В/2. — В/2 с. выхода умножителя 31 поступает так- 40 же на второй вход сумматора 32, на первый вход которого поступает А.После суммирования получают на выходе сумматора 32 действительную часть отсчета а = А — В/2. 45

Формула изобретения

Устройство для вычисления быстрого преобразования Фурье с основанием 3, содержащее M (M = 1оя И, И вЂ” размер преобразования) коммутаторов, М арифметических блоков, блок постоянной памяти, первую и вторую группы из М элементов задержки в каждой, третью и четвертую группы из (M-1) элементов задержки в каждой, причем первый и второй выходы i-ro (i=1 Ì) коммутатора подключены к входам i-x элементов задержки соответственно первой и второй групп, выходы которых подключены к входам соответственно первого и второго операндов i-ro арифметического блока, вход третьего операнда которого подключен к третьему выходу i-ro коммутатора, выходы первого, второго и третьего результатов j-ro (j=1,M-1) арифметического блока подключены соответственно к первому информационному входу (j+1)-го коммутатора, входу

j-го элемента задержки третьей группы и входу j-го элемента задержки четвертой группы, выходы j-х элементов задержки третьей и четвертой групп подключены соответственно к второму и третьему информационному входам (j+1)-го коммутатора, i-й выход блока постоянной памяти подключен к управляющему входу i-го коммутатора, а (i+M)-ый выход блока постоянной памяти подключен к входу задания коэффициентов i-го арифметического блока, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит четыре сумматора, умножитель на (- 1/-ГЗ), умножитель на 3, три ум1 ножителя на (- †) и три умножителя

2 на - 3, выход умножителя на (- 1/ 3) подключен к первому входу первого сумматора и входу умножителя на З,выход которого объединен с выходом первого сумматора и подключен к информационному входу первого коммутатора,а второй вход первого сумматора и вход умножителя на (1/.ГЗ) объединены и являются информационным входом устройства, выход m-го (m=1,3) умножителя

1 на (- †) подключен к первому входу

2 (m+1)-го сумматора и входу m-ro умножителя на - 3, выход которого объединен с выходом (m+1)-го сумматора и является тп-м выходом результата устройства, второй вход (m+1)-го сумматора объединен с входом m-ro умножи1 ° теля на (- — ) и подключен к выходу

m-ro результата M-го арифметического блока, причем i-й арифметический блок содержит десять элементов НЕ, четырнадцать сумматоров и восемь умножителей, при этом выход первого элемента НЕ подключен к первым входам первого и второго сумматоров, /выход первого сумматора подключен к входу второго элемента НЕ и первому входу третьего сумматора, выход которого

1302292 подключен к первым входам первого и второго умножителей, выходы которых подключены соответственно к входу третьего элемента НЕ и первому входу четвертого сумматора, второй вход ко- 5 торого подключен к выходу третьего умножителя, первый вход которого соединен с первым входом четвертого умножителя и подключен к выходу второго сумматора, второй вход которого под- 10 ключен к выходу четвертого элемента НЕ, вход которого соединен с первым входом пятого сумматора и подключен к выходу шестого сумматора, первый вход которого соединен с первым вхо- f5 дом седьмого сумматора и подключен к выходу пятого элемента НЕ, выход шестого элемента НЕ подключен к второму входу седьмого сумматора, выход которого подключен к первым входам пятого 20 и шестого умножителей, выходы которых подключены к первым входам соответственно восьмого и девятого сумматоров, вторые входы которых подключены соответственно к выходу седьмого элемента НЕ и выходу седьмого умножителя, первый вход которого подключен к выходу десятого сумматора, первый вход которого подключен к выходу восьмого элемента НЕ, выход вто- З0 рого элемента НЕ подключен к второму входу пятого сумматора, выход которого подключен к второму входу седьмого умножителя и первому входу восьмого умножителя, выход которого подклю- 35 чен к входу седьмого элемента НЕ,первый.и второй входы одиннадцатого сумматора подключены к выходу четвертого умножителя и выходу третьего элемента НЕ, второй вход второго умножи-. 40 теля подключен к выходу двенадцатого сумматора, первый вход которого подключен к выходу девятого элемента НЕ, выход десятого элемента НЕ подключен к второму входу третьего сумматора, 45 второй вход четвертого умножителя соединен с вторым. входом двенадцатого сумматора, второй вход третьего умножителя соединен с входом девятого элемента НЕ, второй вход пятого умножителя соединен с вторым входом десятого сумматора, второй вход восьмого,умножителя соединен с вторым входом шестого умножителя и входом восьмого элемента HE третий вход сумматора соединен с третьим входом третьего сумматора и первым входом тринадцатого сумматора, второй и третйй входы которого соединены с входами соответственно первого и пятого элементов НЕ, третий вход седьмого сумматора соединен с третьим входом второго сумматора и первым входом четырнадцатого сумматора, второй вход которого соединен с вторым входом первого сумматора и входом шестого элемента НЕ, а третий вход четырнадцатого сумматора соединен с входом десятого элемента НЕ и вторым входом шестого сумматора, при этом вторые входы первого, четвертого, пятого и шестого умножителей объединены и являются входом задания коэффициента устройства, выходы тринадцатого и четырнадцатого сумматоров объединены и являются выходом первого результата арифметического блока, выходы четвер" того и одиннадцатого сумматоров объединены и являются выходом второго результата арифметического блока,выходы восьмого и девятого сумматоров объединены и являются выходом третьего результата арифметического блока, третьи входы тринадцатого и четырнадцатого сумматоров объединены и являются входом первого операнда арифметического блока, входы первого и шестого элементов НЕ объединены и являются входом второго операнда арифметического блока, входы пятого и десятого элементов

НЕ объединены и являются входом третьего операнда арифметического блока.

1302292

1302292

Фиг. Ф

Составитель А. Баранов

Редактор А. Шандор Техред А.Кравчук Корректор Т, Колб

Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва,. Ж-35, Раушская наб., д. 4/5

Заказ 1218/49

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,4