Арифметическое устройство для процессора быстрого преобразования фурье
Изобретение относится к вычислительной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени. Цель изобретения - повышение быстродействия . Поставленная цель достигается за счет того, что в состав устройства входят умножители 1-4, коммутаторы 5-9, триггер 10, сумматоры 11,12,13, вычитатели 14,15,16, сумматоры-вычитатели 17,18, регистры 19-22 и элемент НЕ 23. 4 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РеспуБлик (si)s G 06 F 15/332
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И-ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. (21) 4677176/24 (22) 20.03.89 (46) 28.02.91, Бюл. М 8 (71) Специальное конструкторско-технологическое бюро "Модуль" Винницкого политехнического института (72) Ю.Н.Бочков, П.В.Козлюк и В.Я.Сохнич (53) 681.32(088.8) (56) Авторское свидетельство СССР
ЬЬ 1101858, кл, G 06 F 15/332, 1984.
Авторское свидетельство СССР
N. 1242986, кл. G 06 F 15/332, 1986.
„„5U„„1631556 А1 (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО
ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени, Цель изобретения — повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят умножители 1 — 4, коммутаторы 5 — 9, триггер
10, сумматоры 11,12,13, вычитатели
14,15,16, сумматоры-вычитатели 17,18, регистры 19 — 22 и элемент НЕ 23, 4 ил.
1631556 1.з орс i апис: v t пш. и!сн N вычислительной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени, Цель изобретения — повышение быстродействия устройства при обработке комплексно-сопряженных входных данных, Аналитическое выражение алгоритма вычисления коэффициентов преобразования Фурье комплексно-сопряженных входных данных можно представить в виде
n — 1 n — 2
F=(П CkTk П g)X, k =о где Г = (fo, f1, f2, „Ä fè-1) — вектор коэффит циентов преобразования Фурье;
X — вектор входных данных, обладающих свойством комплексного сопряжения, которое можно выразить соотношением
XI = X*N-;
I =- 1У4/2 — 1, где * — символ комплексного сопряжения;
Хо, Хм/г являются чисто вещественными числами;
N — размерность преобразования.
Оставшиеся члены выражения (1) описываются формулами;
С =1 и " 1 1/1/ге1 "; (2)
Тк — " " 1@V2k+1 (3)
Я, = If® Mg " Ртг" k (4) где I — единичная матрица размерности;
W2 — матрица преобразования Фурье размерности два; а — символ кронекеровского произведения матриц;
I — символ траспонирования;
1/ k+1
I к 0 о о и — k — 1
M п — k г
О
n — k — 1
g 0 0...0 g
g*g. 0,О О (5) О 0 О g О
О О О...g g где Π— диагональная матрица, содержащая чисто вещественные диагональные коэффициенты:
P — матрица идеальной перестановки;
S — правоциркулярная матрица вида
Злемент q матрицы S описывается выражением g = 1 + j (к, где а — число, равное основанию используемой системы счисления; j = К- 1
5 Вычисление преобразования Фурье по формуле (1) выполняется в два этапа. На первом этапе производится умножение входного вектора Х на блочно-диагональные матрицы 6 . Результатом данного эта10 па является вектор промежуточных данных
Х. элементы которого являются вещественными числами.
На втором этапе алгоритма (1) осуществляется выполнение итераций вычисления, 15 аналогичных классическому алгоритму быстрого преобразования Фурье, с той лишь разницей, что все операнды и коэффициенты являются чисто вещественными числами, Основой вычислительных затрат на пер-.
20 вом этапе вычисления является процедура умножения промежуточного вектора данных X или части его на матрицу S вида (5), при этом результат данного умножения обозначается вектором У, а элементы его
25 представляются в виде
У; =gX;+g X (6) где < > m означает приведение числа по модулю m;
m — размерность матрицы S;
Х и Х Обозначим Х через 8, а Х <-1>m через С в результате выражение (6) примет вид РеУ = ReB + ReC - а(imB - ImC); ImУ =!mВ+ ImС+гк(ReВ - ReС), (7) где Im u Re — обозначают мнимую и вещественную части числа. Соотношение (7) следует трактовать как аналитическое выражение базовой операции первого этапа алгоритма (1) вычисления преобразования Фурье, На втором этапе вычисления по формуле (1) вы пол н я ется последовател ь ность операций типа "бабочка": 45 A. Х + Х.,„. Ан1 = Х вЂ” X;+ 1 di, (8) где А, А - 1 — результаты выполнения операции типа "бабочка"; di — элемент вещественной диагональной матрицы 0; Хь Х;+1 — элементы некоторого промежуточного вектора данных, Объединение четырех операций (8) (по две операции с двух соседних итераций вычисления) при N = 4 позволяет получить укрупненную базовую операцию, для выполнения которой потребуется четыре выходных операнда Х1,X2,Хз и Х4 и три ксзффициЕнта d1,d2 и дЗ. 1631556 ",0 30 40 На фиг.1 дана функциональная схема предлагаемого устройства; на фиг,2 — граф вычисления быстрого преобразования Фурье для N = 16; на фиг.3 и 4 — структуры базовых операций в соответствии с выражениями (7) и (8), Устройство (фиг.1) содержит умножители 1 — 4, коммутаторы 5 — 9, триггер 10, сумматоры 11 — 13, вычитатели 1-; — 16, сумматоры-вычитатели 17 и 18, регистры 19 — 22, элемент НЕ 23, входы 24-30, тактовый вход 31, вход 32 задания режима и информационные входы 33 — 36, Устройство работает следующим образом (фиг,2 — 4), В соответствии с графом вычисления дискретного преобразования Фурье (фиг.2) вначале выполняется последовательность базовых операций фиг,3. Для этого на вход 32 устройства подается сигнал уровня "0", который поступает на адресные входы коммутаторов 5 и 6 и переводит их в режим передачи данных с первых входов на выходы. Кроме того, сигнал уровня "0" поступает на вход управления первого сумматора-вычитателя 17 и переводит его в режим вычитания данных, Приход указанного сигнала на вход элемента НЕ 23 инвертирует его, в результате сигнал высокого уровня с выхода элемента НЕ 23 поступает на вход управления второго сумматора-вычитателя 18 и переводит его в режим ".ложения операндов, На первом такте работы устройства на входы 24 и 25 подаются вещественные части первого и второго операндов базовой операции фиг.3, а на входы 27 и 28 поступают мнимые части первого и второго операндов соответственно. Через время, равное времени выполнения операции сложения и времени распространения сигнала через коммутатор, на выходах сумматора 11 и вычитателя 14 формируются результаты сложения и вычитания вещественных частей первого и второго операндов фиг,3, что обеспечивается подачей на сумматор 11 и вычитатель 14 вещественной части первого операнда с входа 24, а на другие входы первого сумматора 11 и первого вычитателя 14 с входа 25 устройства через вход первого коммутаторов 5 — вещественной части второго операнда. Аналогично на выходах сумматоров-вычитателей 17 и 18 формируются разность и сумма мнимых частей первого и второго операндов фиг.3 соответственно. Это позволяет к концу первого такта работы устройства на входы регистров 19 и 20 подать сумму и разность вещественных частей первого и второго операндов, а на входы регистрое 21 и 22 — разность и сумму мнимых частей первого и второго операндов базовой операции фиг.3. По приходу тактового импульса на тактовые входы указанных регистров происходит запись в них операндов, находящихся на входах, а на входы 24,25.27 и 28 поступают входные операнды базовой операции фиг.3 аналогично описанному. Кроме того, по приходу тактового импульса на тактовый вход триггера 10 на его выходе устанавливается сигнал уровня "О", поступивший на его вход в первом такте работы устройства. Сигнал уровня "0" с выхода триггера 10 поступает на управляющие входы коммутаторов 7,8 и 9 и переводит их в режим передачи данных с их входов на выходы, Это позволяет на втором такте работы устройства на выходе сумматора 13 получить результат сложения суммы мнимых частей, поступающей на вход сумматора 13 с выхода регистра 22 через вход коммутатора 9, и разности вещественных частей, поступающей на вход сумматора 13 с выхода регистра 20 через вход коммутатора 7. Код разности ве гцест вен н ых частей входных операндов поступает на вход коммутатора 7 со сдвигом на K разрядов, определяемых величину тривиального множителя а . На выходе вычитате: : 15 формируется разность суммы вещественных частей первого и второго операндов базовой операции фиг.3 поступающей на вход вычитателя 15 с выхода регистра 19, и разности мнимых частей первого и второго операндов, поступающей на вход вычитателя 15 с выхода регистра 21 через вход коммутатора 8. При этом на входе коммутатора 8 осуществляется умножение операнда на множитель а в соответствии со структурой базовой операции фиг.3. Таким образом, к концу второго такта работы устройства на выходах сумматора 13 и вычитателя 15 формируются соответственно мнимая и вещественная части результата выполнения базовой операции фиг,3, которые поступают на выходы 34 и 35 устройства, а на входы регистров 19 — 22 подаются промежуточные результаты выполнения базовой операции, По положительному перепаду очередного тактового импульса на входы 24,25,27 и 28 устройства поступают новые значения исходных операндов базовой операции фиг.3, в регистры 19 — 22 заносятся промежуточные результаты базовой операции, а с выходов 34 и 35 устройства считываются резул ьтаты вычислений. 1631556 35 По приходу последующих тактовых импульсов описанные выше действия повторяются по аналогии вплоть до окончания выполнения первого этапа вычислений по алгоритму (1). На последнем такте выполнения базовой операции фиг.3 на входах регистров 19— 22 находятся промежуточные результаты выполнения данной базовой операции. С приходом очередного тактового импульса указанные промежуточные данные записываются в регистры 19-22; на выходы 34 и 35 устройства подаются мнимая и вещественная части выходного операнда базовой операции фиг.3, а на входы 24 и 25 поступают первый и второй операнды базовой операции фиг.4, на входы 26-29 устройства — соответственно первый коэффициент, третий и четвертый операнды, второй коэффициент базовой операции фиг.4, Кроме того,на вход 32 устройства подается сигнал уровня "1", который поступает на управляющие входы коммутаторов 5 и 6, вход элемента НЕ 23, вход управления сумматора-вычитателя 17 и вход триггера 10. Это приводит к установлению коммутаторов 5 и 6 в режим передачи данных с входа на выход, сумматора-вычитателя 17 — e режим сложения операндов, а сумматора-вычитателя 18 — в режим вычитания. В умножителях 1 и 2 осуществляется умножение второго и пятого операндов базовой операции фиг.4 на первый и второй коэффициенты соответственно. Результаты названных умножений с выходов умножителей 1 и 2 через входы коммутаторов 5 и 6 поступают на входы сумматора 11, вычитателя 14 и сумматоров-вычитателей 17 и 18. При этом на входы сумматора 11 и вычитателя 14 поступает первый операнд базовой операции фиг.5 входа 24 устройства, а на входы сумматоров-вычитателей 17 и 18 приходит третий операнд базовой операции фиг.4 с входа 27 устройства, что позволяет на выходах сумматора 11 и вычитателя 14, а также сумматоров-вычитателей 17 и 18 получить промежуточные результаты выполнения базовой операции фиг.4. В то же время на выходах 34 и 35 устройства формируются результаты выполнения базовой операции фиг.3. Длительность рассматриваемого такта работы устройства отличается от длительности предыдущих тактов работы устройства на первом этапе алгоритма (1) и равна: Ь сл + 1ум + 1к ГдЕ tcn, 1у, тк — ВрЕМя ВЫПОЛНЕНИЯ ОПЕрацИИ сложения, умножения и распространения сигнала через коммутатор. Таким образом, через время, равное t<, после прихода последнего тактового импульса на вход 31 устройства поступает очередной тактовый импульс, по которому происходит запись промежуточных результатов вычисления базовой операции фиг.4 в регистры 19 — 22, выдача результатов выполнения базовой операции фиг,3 на выходы 34 и 35 устройства, подача на входы 24 — 29 устройства входных операндов (по аналогии с описанным выше), а на вход 30 устройства— третьего коэффициента базовой операции фиг,4. Кроме того, сигнал уровня "1" с входа 31 устройства записывается в триггер 10 и поступает на управляющие входы коммутаторов 7,8 и 9, что переводит их в режим передачи данных с входов на выходы. В результате последнего структура устройства настраивается на выполнение базовой операции фиг,4, что позволяет через время, равное на выходах сумматоров 12 и 13, а также на выходах вычитателей 16 и 15, получить результаты выполнения базовой операции фиг.4. При этом в умножителях 3 и 4 получаются результаты умножения третьего и четвертого промежуточных результатов базовой операции фиг.4 на третий коэффициент, Указанные результаты умножения через входы коммутаторов 8 и 9 поступают на входы сумматора 12, вычитателя 15 и сумматора 13, вычитателя 16 соответственно. На другие входы сумматора 12 и вычитателя 15 поступает промежуточный результат с выхода регистра 19, а на входы сумматора 13 и вычитателя 16 подается промежуточный результат вычисления с выхода регистра 20 через вход коммутатора 7. По приходу очередного тактового импульса на вход 31 устройства на входы 33-36 устройства поступают результаты выполнения базовой операции согласно фиг.4, в регистры 19-22 заносятся промежуточные результаты выполнения базовой операции фиг.4, а на входы 24-30 устройства поступают исходные операнды названной базовой операции. На последующих этапах работы устройство выполняет базовые операции фиг.4, после этого может быть переведено в режим выполнения базовой операции фиг.3. Формула изобретения Арифметическое устройство для процессора быстрого преобразования Фурье, содержащее первый, второй, третий и четвертый умножители, два сумматора, два вычитателя, два сумматора-вычитателя, два коммутатора и четыре регистра, причем выход первого коммутатора подключен К первым входам первых сумматора и 1631556 10 телей, а выходы вторых сумматора и вычитателя являются соответственно первым и вторым информационными выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены третий, четвертый и пятый коммутаторы, третий сумматор, третий вычитатель, триггер и элемент НЕ, выход которого подключен к управляющему входу второго сумматора-вычитателя, выход первого сумматора подключен к информационному входу первого регистра, выход которого подключен к первым входам вторых сумматора и вычитателя, выход первого вычитателя подключен к информационному входу второго регистра, выход которого подключен к первому информационному входу и со сдвигом на К разрядов (К вЂ” целое число) к второму информационному входу третьего коммутатора, выход которого подключен к первым входам третьих сумматора и вычитателя, выходы которых являются соответственно третьим и четвертым информационными выходами устройства, первым информационным вхбдом которого являются соединенные между собой вторые входы первых сумматора и вычитателя, выход первого сумматора-вычитателя подключен к информационному входу третьего регистра, выход которого со сдвигом на К разрядов подключен к первому информационному входу четвертого коммутатора и первому входу третьего умножителя, выход которого подключен к второму информационному входу четвертого коммутатора, выход которого подключен к вторым входам вторых сумматора и вычитателя, выход первого умножителя подключен к первому информационному входу первого коммутатора. вто10 30 равляющим входам третьего, четвертого и 35 пятого коммутатора, управляющие входы 25 рой информационный вход которого соединен с первым входом первого умножителя и является вторым информационным входом устройства, третьим информационным входом которого являются соединенные между собой вторые информационные входы первого и второго сумматоров-вычитателей, выход второго сумматора-вычитателя подключен к информационному входу четвертого регистра, выход которого подключен к первому информационному входу пятого коммутатора и первому входу четвертого умножителя, выход которого подключен к второму информационному входу пятого коммутатора, выход которого подключен к вторым входам третьих сумматора и вычитателя, выход второго умножителя подключен к первому информационному входу второго коммутатора, второй информационный вход которого соединен с первым входом второго умножителя и является четвертым информационным входом устройства, первым и вторым входами коэффициента которого являются вторые входы соответственно первого и второго умножителей, вторые входы третьего и четвертого умножителей соединены между собой и являются третьим входом коэффициента устройства, тактовым входом которого являются соединенные между собой тактовые входы первого, второго, третьего и четвертого регистров и тактовый вход триггера, выход которого подключен к уппервого и второго коммутаторов, первого сумматора-вычитателя, вход элемента НЕ и установочный вход триггера соединены между собой и являются входом задания режима устройства. 1631556 р а ® чъ 1 ъ (> ъ 1ъ I Ьс Ьс Ьс 1 М Ьс М Ьс 1631556 Фиг. 3 Фиг. 4 Составитель А.Баранов Редактор А.Лежнина Техред М.Моргентал Корректор М.Шароши Заказ 548 Тираж 403 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101
