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

 

Изобретение относится к технике цифровой обработки сигналов и может быть использовано в системах связи, при анализе речевых сигналов и двумерных изображений. Цель изобретения упрощение устройства. Поставленная цель достигается за счет того, что в состав устройства входят входной преобразователь I, выходные преобразователи 2, элементы задержки 3-7, коммутаторы 8, элементы задержки 9-13, арифметические блоки 14, входы 15 задания коэффициентов, блок синхронизации 16 -и соответствующие связи между узлами устройства. 1 з.п. ф-лы, 4 и л. i С/) со bo 4 сл О5 (ри.1

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

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

РЕСПУБЛИН (51)4 G 06 F )5/332

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

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

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4048989/24-24 (22) 04.04 ° 86 (46) 30.08.87, Бил. N - 32 (71) Одесский политехнический институт (72) M.Á.Ñâåðäëèê, А.А.Назаренко, В.Л.Евсеев и .С.П.Стоян (53) 681.32(088.8) (56) Цифровые диаметры и устройства обработки сигналов на интегральных микросхемах: Справочное пособие (Высоцкий Ф.Б., Алексеев В.И. и др.).

М.: Радио и связь, 1984.

Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. M.: Мир, 1978, с. 680-686, фиг. 10.36.

„„SU„, 1334156 А1 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С ОСНОВАНИЕМ 6 (57) Изобретение относится к технике цифровой обработки сигналов и может быть использовано в системах связи, при анализе речевых сигналов и двумерных изображений, Цель изобретения . упрощение устройства. Поставленная цель достигается за счет того, что в состав устройства входят входной преобразователь 1, выходные преобразователи 2, элементы задержки 3-7, коммутаторы 8, элементы задержки 9-13, арифметические блоки 14, входы 15 задания коэффициентов, блок синхрони- Я зации 16 и соответствующие связи между узлами устройства. 1 э.п. ф-лы, С::

56 2 ния получаем операнд А. С выхода умножителя 21 операнд - b13 поступает также на умножитель 22, с выхода которого снимается операнд В. Преобразованные операнды через коммутатор 8 (фиг. 1) загружаются в элемент 9 задержки, Через каждые (К-1)N/6 тактов, где К=2,6, коммутатор совершает перекоммутацию и следующие операнды загружаются в элементы 10-13 задержки, причем последние N/6 отсчетов поступают непосредственно на пятый вход арифметического блока 14, на первый

I шестой, второй, четвертый и третий входы которого в это время поступают операнды соответственно с элементов

9-13 задержки, а на седьмой — одиннадцатый входы арифметического блока с входов 15 поступают коэффициенты

Сф D, причем С=с-d/ 3, а D=-2d/СЗ, где С вЂ” действительная часть, а d —мнимая часть поворачивающего множителя.

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

Он реализует вычисление по правилу:

1 13341

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

Цель изобретения — упрощение устройства.

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

Устройство содержит входной преоб- 15 разователь 1, выходные преобразователи 2, элементы 3-7 задержки, коммутаторы 8, элементы 9-13 задержки (на SN/6 тактов 7 и 9, íà 4N/6 тактов 6 и 10, на ÇN/6 тактов 5 и ll на 2N/6 тактов 4 и 12 на N/6 тактов

3 и 13), арифметические блоки 14, входы 15 задания коэффициентов, блок

16 синхронизации.

Арифметический блок (фиг. 2) со- 25 держит узел 17 двухточечной базовой операции, узлы 18 трехточечной базовой операции, умножители 19 комплексных чисел.

Входной преобразователь (фиг. 3) содержит сумматор 20, умножитель 21

30 на 1/ 3 и умножитель 22 на 2.

Выходной преобразователь (фиг, 4) содержит сумматор 23, умножитель 24 на 1/2 и умножитель 25 на 3.

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

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

R(p)=IA+pBl А, е RJ, где R

F р=--М., — реальные числа; — комплексный кубический корень единицы, причем А=а-Ь/1 3," а Б=-2b/1 3.

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

Мнимая часть входного операнда поступает на умножитель 1 (фиг. 3)» выполняющий умножение на константу1/ 13. С выхода умножителя 21 полученный операнд — Ъ/К3 поступает на вход сумматора ?О, на другой вход которого поступает действительная часть входного операнда. После суммироваК(0)=И,+ -Ы,;

Я(m) =(Р С+ й.)+ (МЯ„+И„(С -D„H где >1, Ф =(F,+7<+F9)+g(G„+G +G9);

<(1999))(1229) I+pN =(F -F +G -G )+/ (С -F + -G )

9. 2 s к 2 9 1 а 9 9 операнды на выходах первого узла трехточечной базовой операции, а

N + 19 (+1. + )+ (H„+H+H );

N <+PN<= (L;H +L9+H9)+ P (H +L -Í -L9) 1Е+М119 (L)-Lq+H -H9)+ P(H;L +L9 H9) операнды на выходах второго узла трехточечной базовой операции, F +PG (А,+А9)+ (В,+В, );

1 +P Gр — (А +A9 ) +P(B +В );

F +pG =(А +A„)+p(R +В,) — операнды на первых выходах узлов двухточечной базовой операции, а

Lq+V?<=(Ао-А9)+ (В,-В );

1., +НН = (А -А9)+ и(В -В 9);

L>+ pH 9= (А -А, ) + (В <-Я „) — операндык на вторых выходах этих узлов

А +фВ (1=0,5) — операнды на (0+1)-и входе арифметического блока.

Вычисление производится следующим образом.

1334156

N С +G +G

О 1 2 3

С +pD, тч=1,5, 45

1 1 Р;+1 (С.-М °! з

С первого входа арифметического блока операнд А + В, поступает на первый вход узла 17 (фиг. 2), на второй вход которого в это время с тре5 тьего входа арифметического блока поступает операнд А +pB .

Полученные операнды F„ +pG» ц=1,3 с первых выходов узлов двухточечных базовых операций поступают íà и-й . вход первого узла 18 трехточечной базовой операции (фиг. 2), а операнды

L +pG с вторых выходов узлов двухточечных базовых операций поступают на и -й вход второго узла 18 трехточечной базовой операции. На выходе канала действительной частоты операн-. дов первого выхода узла трехточечной базовой операции, а также на выходе канала действительной части операндов первого выхода арифметического блока получаем сумму

1Nio=FF1++F ++F

На выходе канала мнимой части опе- 25 рандов первого выхода узла трехточечной базовой операции получаем сумму и т.д. с. „30

Второй узел трехточечной базовой операции работает аналогично первому.

Операнды с второго и третьего выходов первого и с первого — третьего выходов второго узлов трехточечных базовых операций (фиг. 2) поступают соответственно на первые входы первого — пятого комплексных умножителей, на вторые входы которых поступают с входа коэффициента устройства коэффициенты

40 уричем действитедьная часть операнда

М с действительного канала первого

tn входа ю-ro комплексного умножителя поступает на первый вход умножителя

18, на второй вход которого с канала действительной. части .операндов второго входа комплексного умножителя поступает С . Ha выходе канала действительной части операндов (m+1)-го выхода арифметического блока получаем сумму

М С+О И

На выходе канала мнимой части one- 55 рандов (m+1)-го выхода арифметического блока получаем сумму

Отсчеты с первого выхода арифметического блока !4 (фиг. 1) поступают на первый вход коммутатора второго каскада 8, с второго — шестого выходов поступают соответственно через элементы 3-7 задержки второго каскада, на второй — шестой входы коммутатора 8 второго каскада, который осуществляет переключения с периодом

NTo переключения Т = — — . Отсчеты с пер36 вого — пятого выходов коммутатора 8 второго каскада поступают соответственно-через элементы 9-13 задержки второго каскада на первый — пятый входы арифметического блока 14 второго каскада, с шестого выхода коммутатора 8 второго каскада отсчеты непосредственно поступают на шестой вход арифметического блока 14 второго каскада, который начинает вычислять вторую итерацию БПФ. Коэффициенты поступают с входов задания коэффициентов на входы коэффициента арифметического блока 14. Работа арифметического блока 14 второго каскада аналогична работе арифметического блока

14 первого каскада. С выходов арифметического блока 14 второго каскада отсчеты поступают на элементы третьего каскада и так далее до М-го каскада. Порядок работы каждого иэ них полностью аналогичен работе второго каскада, отличается только частота переключений коммутатора, Период работы коммутатора для i-го каскада составляет NT /6 .

Для последнего каскада период переключений коммутатора 8 равен Т„, С выхода М-го арифметического блока 14 операнды поступают в выходные преобразователи 2, где осуществляется переход из новой плоскости R(p) в обычную комплексную плоскость C(j).

Причем действительная часть а=А-В/2, а мнимая b=-1 3 В/2, Преобразование осуществляется следующим образом.

Выходные операнды A+pB поступают на входы выходных преобразователей (фиг. 4), причем В поступает на умножитель 24 на -1/2,2 с выхода которого — В/2 поступает на вход умножителя 25 на V3, с выхода которого снимается мнимая часть отсчета b=-1ГЗВ/2, -В/2 с выхода умножителя 24 поступает также на второй вход сумматора 23, на первый вход которого поступает А, После суммирования получаем на выхо56 6 первый и второй входы которого под1. Устройство для вычисления быстрого преобразования Фурье с основанием 6, содержащее блок синхронизации, M (M log. N — размер преобразования) I 10 каскадов, каждый из которы, кроме

И-го,содержит коммутатор, первую и вторую группы иэ шести элементов задержки и арифметический блок, а M-й каскад содержит коммутатор арийметиУ 15 ческий блок и группу из шести элементов задержки, причем в i-м (i-=1, И-1) каскаде j-й (j=l 5) выход коммутатора подключен к входу j-го элемента задержки первой группы, выход которо- „ го подключен к входу j-го операнда

20 арифметического блока, выход .В-го операнда (ь=2,6) которого подключен к входу (i-1)-ro элемента задержки второй группы шестой выход коммута9 25 тора подключен к входу шестого операнда арифметического блока„ а в И-м каскаде 1-й выход коммутатора подключен к входу j-го элемента. задержки группы, выход которого подключен к входу j-ro операнда арифметического, 30 блока, вход шестого операнда которого подключен к шестому. выходу коммутатора, выход первого результата арифметического блока и выход j-го элемента задержки второй группы i-го каскада подключены соответственно к первому и (1+1)-му информационным ходам коммутатора (i+1)-го каскада, р-й выход (р 1,И) блока синхронизации подключен к управляющему входу коммутатора р-го каскада, вход коэффициента арифметического блока р- ro каскада является входом задания р-го коэффициента устройства, о т л и ч а ю щ ее с я тем, что, с целью упрощения, оно содержит входной преобразователь и шесть выходных преобразователей, причем первый и второй информационные входы коммутатора первого каскаpа подключены соответственно к пер- 50 вому и второму выходам входного преобразователя, первый и второй входы которого являются входами- соответственно реальной и мнимой частей входных отсчетов устройства, S-ми (S= 55

=1„6) выходами реальной и мнимой ча.— стей результата которого являются соответственно первый и второй выходы S-го выходного преобразователя, 5 133Ц1 де сумматора 23 действительную часть отсчета.

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

5 ключены к выходам соответственно реальной и мнимой частей S-го результата арифметического блока M-ro каскада, при этом входной преобразователь содержит сумматор, умножитель на 2 и умножитель на 1/ ГЗ, выход которого подключен к входу умножителя на 2 и первому входу сумматора, выход которого является первым выходом входного преобразователя, вторым выходом которого является выход умножителя на 2, а первым и вторым входами входного преобразователя являются соответственно второй вход сумматора и вход умножителя на. 1/113, причем

S-й выходной преобразователь содержит сумматор, умножитель на 1 3 и умножитель на 1/2, выход которого подключен к входам умножителя на ГЗ и первому входу сумматора, выход которого является первым выходом S-ro выходного преобразователя, вторым выходом которого является выход умножителя на б, а первым и вторым входами S-го выходного преобразователя являются соответственно второй вход сумматора и вход умножителя на 1/2, 2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что -арифметический блок каждого каскада содержит три узла двухточечной базовой операции, два узла трехточечной базовой операции и пять умножителей комплексных чисел, причем первый и второй входы первого узла двухточечной базовой операции подключены соответственно к входам первых операндов первого и второго узлов трехточечной базовой операции, входы вторых операндов которых подключены соответственно к первому и второму выходам второго узла двухточечной базовой операции, первый и второй выходы третьего узла двухточечной базовой операции подключены к входам третьего операнда соответственно первого и ,второго узлов трехточечной базовой операции, третий выход второго; второй выход первого, первый выход второго, третий выход первого и второй выход второго узлов трехточечной базовой операции подключены к первым входам соответственно первого, второго, третьего, четвертого и пятого умножителей комплексных чисел, выходы которых являются выходами соответственно второго, третьего, четверто!

334156

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

Редактор E.Копча Техред И.Попович

Корректор С.Шекмар

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

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

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

Заказ 3964/46

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

ro, пятого и нестого результатов арифметического блока, выходом первого результата которого является первый выход первого узла трехточечной базовой операции, первый вход первого, второй вход третьего, первый вход второго, второй вход первоI го, первый вход третьего и второй вход второго узлов двухточечной базовой операции являются входами соответственно первого, второго, третьего, четвертого, пятого и пестого операндов арифметического блока, входом коэффициента которого являются соединенные между собой вторые входы первого, второго, третьего, четвертого, пятого и шестого умножителей комплексных чисел.