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

 

Изобретение относится к вычислительной технике и может быть использовано в аппаратуре спектрального анализа и синтеза сигналов . Цель изо.бретения - повышение быстродействия. Устройство содержит блоки сложения-вычитания, коммутатор и умножители комплексных чисел. 1 табл., 2 ил.

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

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

РЕСПУБЛИК

lsd)s G 06 F 15/332

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4891829/24 (22) 13.12.90 (46) 15,02.93. Бюл. ЬЬ 6 (71) Львовский научно-исследовательский радиотехнический институт (72) А.А.Мельник и M,Í,ßöèìèðñêèé . (56) Авторское свидетельство СССР

М 1569847, кл, G 06 F 15/332, 1989.

Авторское свидетельство СССР

М 1337904, кл. G 06 F 15/332, 1985.

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

Известно устройство быстрого действительного преобразования Хартли-Фурье, содержащее блок синхронизации, два счетчика адреса, блок постоянной памяти, четыре регистра, два умножителя, сумматорвычитатель, блок постоянной памяти и три коммутатора. В данном устройстве базовая операция алгоритма быстрого преобразования Хартли (БПХ) по основанию два выполняется за три такта. Недостаток известного устройства — низкое быстродействие.

Наиболее близким по технической сущности к изобретению является устройство для выполнения быстрого преобразования

Фурье, содержащее две группы блоков памят((, сумматор, вычитатель и умножитель комплексных чисел, два элемента задержки, три коммутатора, два счетчика, дешифратор, регистр, блок элементов И, блок постоянной памяти и блок синхронизации., Я2, 1795473 А1 (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО

ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯЯ ХАРТЛ И-ФУРЬ Е (57) Изобретение относится к вычислительной технике и может быть использовано в аппаратуре спектрального анализа и синтеза сигналов. Цель изобретения — повышение . быстродействия. Устройство содержит блоки сложения-вычитания, коммутатор и умножители комплексных чисел. 1 табл., 2 ил.

Устройство реализует алгоритм БПФ по основанию два с прореживанием по частоте.

Для выполнения N-точечного БПФ необходимо выполнить N/2logzN итераций. Недостаток известного устройства — низкое быстродействие.

Цель изобретения — повышение быстродействия, Поставленная цель достигается тем, что в арифметическое устройство для выполнения быстрого преобразования Хартли-Фурье (БПХФ), содержащее два блока сложения-вычитания, коммутатор и умножитель комплексных чисел, причем выход первого блока сложения-вычитания соединен с первым входом умножителя комплексных чисел, дополнительно введены четыре блока сложения-вычитания и второй умножитель комплексных чисел, причем первый и второй входы третьего, четвертого, пятого и шестого блоков сложения-вычитания соединены с входами устройства с первого по восьмой соответственно, а их первые выходы соединены с выходами устройства с первого по четвертый соответственно, выходы

1795473 которого с пятого по восьмой соединены с первым и вторым выходами первого и второго умножителей комплексных чисел соответственно, вторые входы которых соединены с первыми выходами коммутатора и второго блока сложения-вычитания соответственно, а их третьи и четвертые входы соединены с входами задания фазовых множителей устройства, управляющий вход устройс-.ва соединен с управляющим входом коМмутатора; второй выход которого соединен с первым входом второго блока сложения-вычитания, первый и второй входы коммутатора соединены с вторыми выходами первого и второго блоков сложения-вычитания соответственно, первые входы которых соединены с вторыми выходами третьего и шестого, а вторые входы — с вторыми выходами четвертого и пятого блоков сложения-вычитания соответственно.

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

"существенные отличия", Сопоставимый анализ с прототипом показывает, что заявляемое устройство отличается наличием новых блоков: умножителя комплексных чисел и четырех блоков сложения-вычитания, а также наличием новых связей, что делает его соответствующим критерию "новизна".

Схема арифметического устройства для выполнения БПХФ показана на фиг. 1. На фиг. 2 представлен граф алгоритма БПХ по расщепленному основанию два-четыре с прореживанием по частоте на основе предложенной базовой операции, Устройство содержит информационные входы 1-8, управляющий вход 9, входы 10-13 задания фазовых множителей, блоки 14-19 сложения-вычитания, коммутатор 20, умножители 21, 22 комплексных чисел, информационные выходы 23-30.

Входы устройства 1, 3, 5, 7 соединены с первыми входами соответственно блоков

14, 15, 16, .17 сложения-вычитания, а входы

2, 4, 6, 8 — с вторыми входами соответственно блоков 14, 15, 16, 17, первые выходы которых соединены с выходами 23, 24, 25, 26 устройства соответственно, вторые выходы блоков 14, 15 сложения-вычитания соединены соответственно с первым и вторым входами блока 18, вторые выходы блоков 17, 16 соединены соответственно с.первым и вторым входами блока 19, первый выход которого соединен с вторым входом умножителя 22, первый вход которого соединен с выходом коммутатора 20, входы которого соединены с вторыми выходами блоков 18, 19, а второй его выход соединен с вторым входом умножителя 21, первый вход которого соединен с первым выходом блока 18, первые и вторые выходы умножителей 21, 22 соединены соответственно с выходами

27, 28, 29, 30 устройства, входы 10, 11, 12, 13 которого соединены соответственно с третьими и четвертыми входами умножите10 лей 21, 22, управляющий вход коммутатора

20 соединен с входом 9 устройства.

Базовая операция алгоритмов БПХ и .БПФ по расщепленному основанию два-четыре с прореживанием по частоте описыва"5 ется следующей системой уравнений; а =а+е;Ь =b+f;d =d+h;c =c+g; г! =(а — е)+(Ь вЂ” f); q> =(а — е) — (Ь вЂ” f);

- r = (d — h) — (с — g); qa = (d — h) + (c — g); е = г!С1ч + (Yqi+ Угз) ы; f = к. 1

20 = г1Яи — (Yqq + Yg)CN, g" = (Угз+ Yq1)CQ + цзЗр

= (Yrç+ Yqi)SNз — ЦзС1ч где а, Ь, с, d, e, f, g, h — входы устройства; а, Ь, с, сГ, е, Г, g, h — выходы устрой25 ства;

Y — значение сигнала на управляющем входе коммутатора (Y = О, 1).

Здесь С1! = соз(2 кг/N), 31ч = з!п(2 лг/К), Устройство работает следующим обра30 эом

По информационным входам 1-8 в устройство поступают входные числа. По входам 10-13 поступают фазовые множители.

На блоках 14-19 сложения-вычитания, каж35 дый из которых содержит сумматор и вычитатель, выполняются операции сложения и вычитания в соответствии с выражением: ! =I+m; m =! — m, 1 . 1

40 где I, m —; l, m — выходы блока, .! 1

Коммутатор 20 пропускает поступающие на его входы данные прямо или накрест в зависимости от значения сигнала Y на

45 входе 9 устройства, Если Y = О, то данные идут прямо, если Y = 1 — накрест.

На умножителях 21, 22 комплексных чисел выполняются операции умножения поступающих из блоков 18, 19 и коммутатора

50 20 чисел на фазовые множители в соответствии с выркажениями:

I1=ICg Я K I =!С зк+ Я

m = Б1ч — mCN; m = ISg — mCg где гп — входы умножителей;

i, m — выходы умножителей;

С1ч, 31ч - фазовые множители, поступающие по входам 10-13.

Первое выражение реализуется на умножителе 21, второе — на умножителе 22, 1795473

Порядок выполнения алгоритмов БПХ и

БПФ на основе предложенной базовой операции определяется графом алгоритма, На фиг, 2 показан граф алгоритма БПХ по расщепленному основанию два-четыре с про- 5 реживанием по частоте для N = 32.

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

N, используемых для вво@а фазовых множителей Си, Ям, Си к, Sx

Для К = 1,N/8-1 эти множители принимают значения Сы = cos(2 ЛК/К), Sg = 15 к к

=з!п(2тг К/М), Си = соз(2л ЗК/М), Ям

= sIn(2 л ЗК/N), а для К = О при N «8 (третья цифра равна размерности преобразования

N они соответственно равны: О, 1, - 2/2 и

2/2. На последнем этапе преобразования на некоторые входы подаются нули (обозначены 0), а некоторые выходы не используются. На этом этапе с помощью базовой

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

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

1, О, 4, а вторые О, О, 2, которые реализуются с фазовыми множителями, равными 1 для четырехточечного преобразования, и 1/2, для двух двухточечных, Порядок связей между входами и выходами базовых операций показан на фиг. 2. Быстродействие предложенного арифметического устройства для выполнения

БПХФ определяется как сумма времени выполнения одного умножения комплексных чисел и двух сложений, что только на одну операцию сложения больше, чем в устройстве-прототипе, что несущественно, В таблице приведено количество базовых операций при выполнении N — точечного (N

=2, и =5,12) алгоритма БПХ на предложенном устройстве и устройстве-прототипе, а также выигрыш по быстродействию. При выполнении алгоритма БПФ выигрыш по быстродействию аналогичен. ны с первым и вторым выходами первого и второго умножителей комплексных чисел соответственно, вторые входы которых соединены с первым выходом коммутатора и выходом суммы второго блока сложения-вычитания соответственно, третьи и четвертые входы первого и второго умножителей комплексных чисел соединены соответственно с первого по четвертый входами задания фазовых множителей устройства, уп равляющий вход устройства соединен с управляющим входом коммутатора, второй выход которого соединен с первым входом второго блока сложения-вычитания, первый и второй информационные входы коммутатора соединены с выходами разности первого и второго блоков сложения-вычитаний соответственно, первые входы которых соединены i выходами разности третьего и шестого, а вторые входы — с выходами разности четвертого и пятого блоков сложения-вычитания соответственно.

1795473

?9

1795473

Х д

Хя сто .И .Хя

Х 3

Х/

% 3

Х

Хд

Хф

Хц

Ъ х х, хг3

xgg х«

+26 х

Xgf х,@ до З1

Ни и

" о

Hg( (3

Составитель А,Мельник

Редактор Т.Иванова - Техред М.Моргентау Корректор И.Шмакова

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 432 Тираж Подписное

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

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