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

113022

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

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

Мнимая часть входного отсчета поступает на умножитель на - iX-ls (фиг.З) С выхода умножителя 28 полученный операнд на b поступает на второй вход сумматора 29, на первый вход которого поступает действительная часть бтсчета. После сумНа фиг.1 приведена блок-схема устройства; на фиг.2 - схема работы коммутаторов на фиг.З - блок-схема вход-fo мирования получают операнд А. С ного преобразователя; на фиг.4 -блок- выхода умножителя 28 операнд - схема выходного преобразователя; на фиг.З - блок-схема арифметического

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

20

блока.

Устройство содержит входной преобразователь 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 тактов, коммутатор 14, элемент 15 задержки на 2N/3 (,М), тактов, элемент 16 задержки на N/3 тактов, арифметический блок 17, элемент 18 задержки на N/3

на 2N/3 тактов, коммутатор 20,эле- c-d/, а D - 2d/ -, где С - дей25

поступает на умножитель 30, с выхода которого снимается операнд В. Преобразованные отсчеты через коммутатор 2 (фиг.1) загружаются в элемент 3 задержки, через N/3 тактов коммутатор 2 совершает перекоммутацию по схеме,изображенной на фиг.2, и следующие N/3 отсчетов загружаются в элемент 4 задержки. Через 2N/3 тактов коммутатор совершает вторую перекоммутацию и последние N/3 отсчетов поступают непосредственно на третий вход арифметического блока 5,на первый и второй входы которого в это время поступают отсчеты с элементов 3 и 4 задержки, а на четвертый и пятый входы арифметического блока 27 постоянной памяти поступают повора.тактов, элемент 19 задержки ЗО ивающие множители C+pjD, причем С

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

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

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

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

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

40

ствительная часть, а D - мнимая часть поворачивающего множителя,арифметический блок начинает вычисление пер- 35 вой итерации преобразования.

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

На входы трехвходового сумматора 50 47 с мнимых каналов первого, второго и третьего входов арифметического блока поступают мнимые части операндов В,, В и В,. На выходе канала мнимой части операндов первого выхо45

.)-.г ег да арифметического блока получают

A,B6RK К означает реальные числа, - г, т, т, т,

J г тг пл г к . 4-R -4-КR ттг г глгттга от татг-а-.

сумму BI+BJ +B. В поступает также на вход элемента НЕ 38, с выхода которого В поступает на вход сумматора 43, на первый вход которого пос- комплексный кубический корень Причем А а-Ь/-|3, аВ

единицы. -2Ь/43 .

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

Мнимая часть входного отсчета поступает на умножитель на - iX-ls (фиг.З) С выхода умножителя 28 полученный операнд на b поступает на второй вход сумматора 29, на первый вход которого поступает действительная часть бтсчета. После суммирования получают операнд А. С выхода умножителя 28 операнд -

мирования получают операнд А. С выхода умножителя 28 операнд -

поступает на умножитель 30, с выхода которого снимается операнд В. Преобразованные отсчеты через коммутатор 2 (фиг.1) загружаются в элемент 3 задержки, через N/3 тактов коммутатор 2 совершает перекоммутацию по схеме,изображенной на фиг.2, и следующие N/3 отсчетов загружаются в элемент 4 задержки. Через 2N/3 тактов коммутатор совершает вторую перекоммутацию и последние N/3 отсчетов поступают непосредственно на третий вход арифметического блока 5,на первый и второй входы которого в это время поступают отсчеты с элементов 3 и 4 задержки, а на четвертый и пятый входы арифметического блока 27 постоянной памяти поступают повора ивающие множители C+pjD, причем С

40

ствительная часть, а D - мнимая часть поворачивающего множителя,арифметический блок начинает вычисление пер- 35 вой итерации преобразования.

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

На входы трехвходового сумматора 50 47 с мнимых каналов первого, второго и третьего входов арифметического блока поступают мнимые части операндов В,, В и В,. На выходе канала мнимой части операндов первого выхо45

г, т, т, т,

к . 4-R -4-КR ттг г глгттга от татг-а-.

сумму BI+BJ +B. В поступает также на вход элемента НЕ 38, с выхода которого В поступает на вход сумматора 43, на первый вход которого поступает А,. С выхода сумматора 46 А,- Bj поступают на вход элемента НЕ 39, с выхода которого поступают на вход трехвходового сумматора 48. В поступает также на вход элемента НЕ 37, с выхода которого-В поступает на вход трехвходового сумматора 48, на другой вход которого поступает А, На выходе трехвходового сумматора 48 получим сумму F А,-В,,-А поступает также на вход элемента НЕ 35 с выхода которого А поступает на вход трехвходового сумматора 49. С выхода элемента НЕ Б поступает на вход сумматора 44, на другой вход которого поступает А.

С выхода сумматора 44 поступают на вход трехвходового сумматора 49, на другой вход которого поступает В, . На выходе трехвходового сум-

матора 49 получим сумму Е А,

-В.-А,

В, поступает также на вход элемента НЕ 36, с выхода которого А поступает на вход трехвходового сумматора 50, на другой вход которого с выхода элемента НЕ 38 поступает Вз, а на другой вход -А,. На ; выходе трехвходового сумматора 50 лолучим сумму Н А,. С выхода сумматора 4.4 AJ - В 4 поступают также на вход элемента НЕ 37, с выхода которого Bj - Aj поступают на вход трехвходового сумматора 51, на другой вход которого с выхода сумматора 45

Сумма Н с выхода трехвходового сумматора 50 поступает на вход умножителя 62, на другой вход которого с канала действительной части операндов арифметического блока поступает С. С выхода умножителя 62 поступает на вход сумматора 56. Сумма G с выхода трехвходового сумматора 51 поступает на вход умнояонтеля 63, на другой вход которого с канала мнимой части арифметического блока поступает D. С выхода умножителя 63 поступает на вход элемента НЕ 42, с выхода которого -DjG поступает на вход сумматора 56. На выходе сумматора, а также на выходе канала действительной части операндов арифметического блока получают сумму - .

Сумма Н поступает также на вход умножителя 64, на другой вход которо- поступают А, - В, а на другой вход- 35 го поступает Dj. С выхода умножителя В,. На выходе трехвходового суммато- 64 поступает на вход сумматора 55. ра 51 получают сумму G В,. D поступает также на вход элеменСумма с выхода трехвходового сумматора 48 поступает на вход умножителя 58, на другой вход которого с канала действительной части операндов входа арифметического блока поступает С, . С выхода умножителя 58 С,F поступает на вход сумматора 52. Сумма Е с выхода трехвходового сумматора 49 поступает на вход умножителя 59, на другой вход которого с канала мнимой части операндов арифметичеста НЕ 43, с выхода которого - D поступает на вход сумматора 54, на дру40 гой вход которого поступает С. С выхода сумматора 54 поступает на вход умножителя 65, на дру гой вход которого поступает сумма G. С выхода умножителя 65 G (Cj-D,) поступает на

5 вход сумматора 55. На выходе сумматора, а также на выходе канала мнимой части операндов арифметического блока получают сумму + (.) G.

Отсчеты с первого выхода арифмети- кого блока поступает D, ,. с выхода уы-еп ,. г /, ,

зи ческого блока 5 (фиг.1) поступают на ножителя 59 D,E поступает на вход

элемента НЕ 40,, с выхода которого -D,E поступает на вход сумматора 52. На вь1ходе сумматора, а также на выходе канала действительной части операндов второго выхода арифметического блока получа.ют сумму C,F-D,E. Сумма F поступает также на вход умножителя 60, на другой вход которого поспервый вход коммутатора 10, с второго и третьего выходов поступают соответственно- череэ элементы 6 и 8 задержки на второй и третий входы ком- 5 мутатора 10, который осуществляет переключения в соответствии с фиг.2 с

периодом переключения Т

NTa

9

Оттупает D,. С выхода умножителя 60 D,F поступает на вход сумматора 53. D, поступает также на вход элемента НЕ 41, с выхода которого - D, поступает на вход сумматора 57, на другой вход которого поступает С, . С выхода сумматора 57 C,-D, поступает на вход умножителя 61, на другой вход которого поступает Е. С выхода умножителя 61 Е (C,-D,) поступает на вход сумматора 53. На выходе сумматора 53, а также на выходе канала мнимой части операндов арифметического блока получают сумму + (,-) Е.

Сумма Н с выхода трехвходового сумматора 50 поступает на вход умножителя 62, на другой вход которого с канала действительной части операндов арифметического блока поступает С. С выхода умножителя 62 поступает на вход сумматора 56. Сумма G с выхода трехвходового сумматора 51 поступает на вход умнояонтеля 63, на другой вход которого с канала мнимой части арифметического блока поступает D. С выхода умножителя 63 поступает на вход элемента НЕ 42, с выхода которого -DjG поступает на вход сумматора 56. На выходе сумматора, а также на выходе канала действительной части операндов арифметического блока получают сумму - .

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

вход сумматора 55. На выходе суммаческого блока 5 (фиг.1) поступают на

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

периодом переключения Т

NTa

9

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

Работа арифметического блока 11 аналогична работе арифметического блока 5, С выходов арифметического блока 11 второго каскада отсчеты поступают на элементы третьего каскада

задержки соответственно первой и вто рой групп, выходы которых подключены к входам соответственно первого и вт рого операндов i-ro арифметического блока, вход третьего операнда которо го подключен к третьему выходу i-ro коммутатора, выходы первого, второго

и третьего результатов j-ro (,M-1 арифметического блока подключены со- 0 ответственно к первому информационно му входу (j+1)-ro коммутатора,входу j-ro элемента задержки третьей группы и входу j-ro элемента задержки четвертой группы, выходы j-x элемени так далее до М-го каскада. Порядок тов задержки третьей и четвертой

работы каждого из них полностью аналогичен работе второго каскада. Отличается только частота переключений коммутатора. Период работы коммутатора для i-ro каскада составляет .

25

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

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

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

C(j), Причем действительная часть -,

а- А - В/2, а мнимая часть b -ЗВ/2.30 на -(Т, выход умножителя на (- )

целью упрощения устройства, оно содержит четыре сумматора, умножитель на (- 1/S3), умножитель на 3, три ум, К

ножителя на (- -) и три умножителя

подключен к первому входу первого сумматора и входу умножителя на 3,выход которого объединен с выходом первого сумматора и подключен к информа- 35 ционному входу первого коммутатора,а второй вход первого сумматора и вход умножителя на (1/4з) объединены и являются информационным входом устройства, выход ш-го (,3) умножителя

40 / Ц

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

(т+1)-го сумматора и входу т-го умножителя на -{З, выход которого объединен с выходом (т+1)-го сумматора и 45 является т-м выходом результата устройства, второй вход (т+1)-го сумматора объединен с входом т-го умножи, К . Устройство для вычисления быстрого теляна (- j) и подключен к .выходу

преобразования Фурье с основанием 3, Q т-го результата М-го арифметического содержащее М (М log,N, N - размер блока, причем i-й арифметический блок преобразования) коммутаторов, М арифметических блоков, блок постоянной

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

Выходные отсчеты А + njB поступают на входы выходных преобразователей. Причем В поступает на умножитель 31 на -1/2, с выхода которого - В/2 поступает на вход умножителя 33 на , с выхода которого снимается мнимая часть отсчета b - -{з В/2. - В/2 с. выхода умножителя 31 поступает также на второй вход сумматора 32, на первый вход которого поступает А.После суммирования получают на выходе сумматора 32 действительную часть отсчета а А - В/2.

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

содержит десять элементов НЕ, четырнадцать сумматоров и восемь умножипамяти, первую и вторую группы из М элементов задержки в каждой, третью и четвертую группы из (М-1) элементов задержки в каждой, причем первый и второй выходы 1-го (,М) коммутатора подключены к входам i-x элементов

; с13022926

задержки соответственно первой и второй групп, выходы которых подключены к входам соответственно первого и второго операндов i-ro арифметического блока, вход третьего операнда которого подключен к третьему выходу i-ro коммутатора, выходы первого, второго

и третьего результатов j-ro (,M-1) арифметического блока подключены со- ответственно к первому информационному входу (j+1)-ro коммутатора,входу j-ro элемента задержки третьей группы и входу j-ro элемента задержки четвертой группы, выходы j-x элементов задержки третьей и четвертой

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

-,

на -(Т, выход умножителя на (- )

целью упрощения устройства, оно содержит четыре сумматора, умножитель на (- 1/S3), умножитель на 3, три ум, К

ножителя на (- -) и три умножителя

т-го результата М-го арифметического блока, причем i-й арифметический блок

содержит десять элементов НЕ, четырнадцать сумматоров и восемь умножителеи, при этом выход первого элемен- та НЕ подключен к первым входам первого и второго сумм аторов,/выход первого сумматора подключен к входу второго элемента НЕ и первому входу третьего сумматора, выход которого

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

сумматора, второй вход которого под- tO третьего сумматора и первым входом

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

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

мента НЕ, второй вход второго умножит 40 ари4метического блока, входы пертеля подключен к выходу двенадцатого сумматора, первый вход которого под- ключен к выходу девятого элемента НЕ, выход десятого элемента НЕ подключен к второму входу третьего сумматора, второй вход четвертого умножителя соединен с вторым.входом двенадцатого

сумматора, второй вход третьего умножителя соединен с входом девятого элемента НЕ, второй вход пятого умножителя соединен с вторым входом десятого сумматора, второй вход восьмого .умножителя соединен с вторым входом шестого умножителя и входом восьмого элемента НЕ, третий вход сумматора соединен с третьим входом

5

0

5

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

того и одиннадцатого сумматоров объединены и являются выходом второго результата арифметического блока,выходы восьмого и девятого сумматоров

объединены и являются выходом треть-

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

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

ю

CVI

tl

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

«

f5

CO

i

tf

ir

P

29

32

JJ

Фиг.З

fuz. Ч

Составитель А. Баранов Редактор А. Шандор Техред А.Кравчук Корректор. Колб

Заказ 1218/49 Тираж 673Подписное

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

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

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

фиг. 5