Устройство для вычисления быстрого преобразования Фурье с основанием 6 Советский патент 1987 года по МПК G06F17/14 

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

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

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

Устройство содержит входной прёоб- разователь 1, выходные преобразователи 2, элементы 3-7 задержки, ком- мутаторы 8, элементы 9-13 задержки (на 5N/b тактов 7 и 9, на 4N/6 тов 6 и 10, на 3N/6 тактов 5 и 11, на 2N/6 тактов 4 и 12 на N/6 тактов 3 и 13), арифметические блоки 14, входы 15 задания коэффициентов,блок 16 синхронизации.

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

Входной преобразователь (фиг. содеркнт сумматор 20, умножитель на 1/V3 и умножитель 22 на 2.

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

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

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

R(/H){A+.B; А, BeRJ,.

где R - реальные числа; w - комплексный кубический корень единицы, прнчем -Ь/УЗ,- а B -2b/Vl. Преобразование осуществляется еле дующим образом.

Мнимая часть входного операнда поступает на умножитель 1 (фиг. 3),, выполняющий умножение на константу 3) 21

. 4)

24

1/УЗ. с выхода умножителя 21 полученный операнд - Ь/УЗ поступает на вход сумматора 20, на другой вход которого поступает действительная част входного операнда. После суммирова

0

5

g

ния получаем операнд А. С выхода умножителя 21 операнд - ЪУЗ поступает также на умножитель 22, с выхода которого снимается операнд В, Преобразованные операнды через коммутатор 8 (фиг.. 1) загружаются в элемент 9 за- держки. Через каждые (K-)N/6 тактов, где ,6, коммутатор совершает перекоммутацию и следующие операнды загружаются в элементы 10-13 задержки, причем последние N/6 отсчетов поступают непосредственно на пятый вход арифметического блока 14, на первый шестой, второй, четвертый и третий входы которого в это время поступают операнды соответственно с элементов 9-13 задержки, а на седьмой - одиннадцатый входы арифметического блока с входов 15 поступают коэффициенты , причем С с-а/Уз, а D -2d//3, где С - действительная часть, а d - мнимая часть поворачивающего множителя . Арифметический блок начинает вычисление первой итерации преобразования. Он реализует вычисление по правилу:

0

g

50

(О

0

5

f(0)M,,;м,

f(m).MJ)+N,(,i

где (Р,+Р2+1з) + И(С,,+С);

M, (Р,-С -Гз+Сз)-.(С, ) ;

, (F. -F,+G,-Gp+/(GrVF5-Gp операнды на выходах первого узла трехточечной базовой операции, а

Мз (Ь,+Ц+Ьз) + (Н,+Н,+Нз) ;

(L-H+L+Нз) + (Н,) ;

Mj+fiNj(I,i-Lj+H -Hj)-+/.(H-Ь2 +Ьз-Нэ) - операнды на выходах второго узла трехточечной базовой операции,

F., (АО+АЗ)+.(ВО+ВЗ);

()+MBj+Bp;

()+(,) - операнды на первых выходах узлов двухточечной базовой операции, а

,(А,-А)+(ВР-ВЗ);,

(A2-Ap + ,u(Bj-B j) ;

(,)+((,) - операнды на вторых выходах этих узлов.

55 Aj+jttB j(,5) - операнды на (2+1)-м входе арифметического блока.

f

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

i 3 13

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

Полученные операнды , ,3 с первых выходов узлов двухточечных базовых операций поступают на п-й , вход первого узла 18 трехточечной базовой операции (фиг. 2), а операнды L +/itG с вторых выходов узлов двухточечных базовых операций поступают на п-й вход второго узла 18 трехто- чечной базовой операции. На выходе канЁша действительной частоты операндов первого выхода узла трехточечной базовой операции, а также на выходе канала действительной части операн- дов первого выхода арифметического блока получаем сумму

.

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

.

, .

Второй узел трехточечной базовой

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

, ,5,

тричем действительная часть операнда М с действительного канала первого . входа м-го комплексного умножителя 5 поступает на первый вход умножителя 18, на второй вход которого с канала действительной части операндов второго входа комплексного умножителя поступает С. На выходе канала дей- 50 ствительной части операндов ( выхода арифметического блока получаем сумму

м„-с„+в„.к„.

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

(.

Q 5 Q

5

0

5

0

5 0

5

56

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

NTo переключения Т гг- . Отсчеты с пер JO

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

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

С выхода М-го арифметического блока 14 операнды поступают в выходные преобразователи 2, где осуществляется переход из новой плоскости R(,L ) в обычную комплексную плоскость C(j). Причем действительная часть а А-В/2, а мнимая В/2. Преобразование

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

Выходные операнды поступают

на входы выходных преобразователей (фиг. 4), причем Б поступает на умножитель 24 на -1/2,2 с выхода которого - В/2 поступает на вход умножителя 25 на УЗ , с выхода которого снимается мнимая часть отсчета Ь -УЗВ/2. -В/2 с выхода умножителя 24 поступает также на второй вход сумматора 23, на первый вход которого поступает А. После суммирования получаем на выходе сумматора 23 действительную часть отсчета.

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

1. Устройство для вычисления быстрого преобразования Фурье с основанием 6, содержащее блок синхронизации, М (.N - размер преобразования) каскадов, каждый из которы, кроме М-го,содержит коммутатор, первую и вторую группы из шести элементов задержки и арифметический блок, а М-й

10

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

каскад содержит коммутатор, арифмети--, ми входного преобразователя являются

чёский блок и группу из шести элемен- тов задержки, причем в i-м (, М-1) каскаде j-й (,5) выход коммутатора подключен к входу j-ro элемента задержки первой группы, выход которого подключен к входу j-ro операнда арифметического блока, в.ыход ,Е--го операнда (,6) которого подключен к входу (E-l)-ro элемента задержки второй группы, шестой выход коммутатора подключен к входу шестого операнда арифметического блока, а в М-м .каскаде j-й выход коммутатора подключен к входу j-ro элемента задержки группы, выход которого подключен к входу j-ro операнда арифметического, блока, вход шестого операнда которого подключен к шестому.выходу коммутатора, выход первого результата арифметического блока и выход элемента задержки второй группы i-ro каскада подключены соответственно к первому и (j + информационным входам коммутатора (i+l)-ro каскада, р-й выход (,М) блока синхронизации подключен к управляющему входу комг-гутато- ра р-го каскада, вход коэффициента арифметического блока р-го каскада является входом задания р-го коэффициента устройства, о т л и ч а ю щ е- е с я тем, что, с целью упрощения, оно содержит входной преобразователь и шесть выходньтх преобразователей, причем первый и второй информационные входы коммутатора первого-каскада подключены соответственно к первому и второму выходам входного преобразователя, первый и второй входы которого являются входами- соответственно реальной и мнимой частей вход- ных отсчетов устройства, 8-м:и (S 1,6) выходами реальной и мнимой частей результата которого являются соответственно первый и второй выходы S-ro выходного преобразователи,

25

соответственно второй вход сумматора и вход умножит€;ля на l/v3, причем S-й выходной преобразователь содержит сумматор, умножитель на v3 и умножитель на 1/2, выход которого под- ключей к входам умножителя на тЗ и первому входу сумматора, выход которого является первым выходом S-ro выходного преобразователя, вторым вы ходом которого является выход умножителя на /3, а первым и вторым входами S-ro выходного преобразователя являются соответственно второй вход сумматора и вход умножителя на 1/2,

30 2. Устройство по п. 1, отличающееся тем, что -арифметический блок каждого каскада содержит три узла двухточечной базовой опера- 11,ии, два узла трехточечной базовой

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

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

50 операции, третий выход второго; вто- . рой выход первого, первый выход второго, третий выход первого и второй выход второго узлов трехточечной базовой операции подключены к первьм

g5 входам соответственно первого, второго, третьего, четвертого и пятого умножителей комплексных чисел, выходы которых являются выходами соответ ственно вторрго, третьего, четверто0

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

5

соответственно второй вход сумматора и вход умножит€;ля на l/v3, причем S-й выходной преобразователь содержит сумматор, умножитель на v3 и умножитель на 1/2, выход которого под- ключей к входам умножителя на тЗ и первому входу сумматора, выход которого является первым выходом S-ro выходного преобразователя, вторым выходом которого является выход умножителя на /3, а первым и вторым входами S-ro выходного преобразователя являются соответственно второй вход сумматора и вход умножителя на 1/2,

0 2. Устройство по п. 1, отличающееся тем, что -арифметический блок каждого каскада содержит три узла двухточечной базовой опера- 11,ии, два узла трехточечной базовой

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

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

0 операции, третий выход второго; вто- . рой выход первого, первый выход второго, третий выход первого и второй выход второго узлов трехточечной базовой операции подключены к первьм

g5 входам соответственно первого, второго, третьего, четвертого и пятого умножителей комплексных чисел, выходы которых являются выходами соответственно вторрго, третьего, четверто

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

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

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

f4

Фиг.З

Редактор Е.Копча

Составитель А.Баранов Техред и.Попович

Заказ 3964/46 Тираж 672Подписное

ВНИШТИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35,. Раушская наб,, д. 4/5

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

ФигЛ

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