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

 

Изобретение относится к вычислительной технике и предназначено для построения устройств обработки сигналов , работающих в реальном масштабе времени. Цель изобретения - повышение быстродействия устройства при обработке вещественных входных данных . Поставленная цель достигается за счет того, что устройство содержит сумматоры 1-4. вычитатели 5-8, умножители 9-12, коммутаторы 13-17, регистры 18-21, триггер 22. 4 ил.

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

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

РЕСПУБЛИК

А1

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4677170/24 (22) 20.03 ° 89 (46) 28 ° 02.91.Бюл. 9 8 (71) Специальное конструкторскотехнологическое бюро "Модуль" Винницкого политехнического института (72) И.Н.Бочков, П.В. Козлюк, В.Я.Сохнич и А.Ф.Гаджала (53) 681.32 (088.8) (56) Авторское свидетельство СССР

М 1101853, кл. G 06 F 15/332, 1984.

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

Р 1242986, кл. С 06 Г 15/332 1986.

„„SU „„1631555 (51)5 G 06 F 15/332

2 (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ

ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ

ФУРЬЕ (57) Изобретение относится к вычислительной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени. Цель изобретения — повышение быстродействия устройства при обработке вещественных входных данных. Поставленная цель достигается за счет того, что устройство содержит сумматоры 1-4. вычитатели 5-8, умно— жители 9-12, коммутаторы 13-17, регистры 18-21, триггер 22. 4 ил.

1б 31555 где F — - вектор коэффициентов преобразования Фурье;

Х - вектор вещественных входных данных; и= 1оя Б;

N - размерность преобразования;

n-k-2 k+2 T k+2.

6К = 12 gP2 9 H2 ) (2)

Т = 12® Ч

k h-k (3) и- -

С = 12® а®12 (4) 30 — единичная матрица; — матрица идеальной перестановки;

Ь

I2 о

k i

T — символ транспонирования;

q-k-<

И-"

D2 матрица дискретного преобразования Фурье порядка два; символ кронекеровского произ- 45 ведения матриц; диагональная матрица, содержащая чисто вещественные коэффициенты; провоциркулянтная матрица вида:

q q+0...,.ОО о q q ...оо (5) 55

° ° ° ° ° °

О 0 О... qq

Ф

q+О 0... Oq

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

Цель изобретения - повышение быстродействия устройства, Устройство выполняет базовые операции алгоритма быстрого преобразования Фурье, который в случае обработки вещественных входных данных может быть представлен аналитически соотношением: ю-г и-

Г = (0 9„)(0 Т„С„)Х, (» к О

Ф вЂ” символ комплексного сопряжения.

Элемент q-матрицы S записывается в виде:

q = 1 + 3М» где 3

06 — число равное основанию используемой системы счисления.

Вычисление преобразования Фурье в соответствии с формулой (1) выпол= няется в два этапа, Первый этап заключается в умножении входного вектора

Х данных на произведение слабозаполненных матриц С и Т . Поскольку матрицы С и Т k содержат чисто вещественные элементы, то на первом этапе все операнды являются чисто вещественным числом. Структура вычисления данного этапа вычисления аналогична структуре вычисления известного алгоритма вычисления быстрого преобразования Фурье по основанию два. Это позволяет выделить базовую операцию для первого этапа вычисления вида:

А,= Х, + Х; (6) где А, А „, — результаты выполнения

4% базовой операции;

Х,, Х вЂ” исходные операнды;

d — элемент диагональной мат1 рицы D.

На втором этапе вычисления дискретного преобразования Фурье в соответствии с (1) выполняется умножением блочно-диагональных матриц Ок

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

ReY, = ReB + ReC-gglmB-ImC)

ImY = g(ReB-ReC)+ImB + ImC, (7) где Re u Im обозначают соответственно вещественную и мнимую части числа;

В, С вЂ” исходные операции, являются элементами вектора Х .

Для выполнения базовой операции (7) потребуется выполнить шесть операций -типа сложения и две операции

1631555 тривиального умножения на константу

<9, которая выполняется путем сдвига кода на К разрядов, На Ьиг.1 изображена функциональная схема устройства; на фиг.2 — граф вычисления по алгоритму (1) для

N = 16; на фиг.3 и 4 — структуры базовых операций по формулам (6) и (7) соответственно.

Устройство содержит сумматоры 1-4, вычитатели 5-8, умножители 9-12, коммутаторы 13- t7, регистры 18-21, триггер 22, входы 23-29 устройства, вход задания режима 30 устройства, тактовый вход 31 устройства, информационные выходы 32 — 35 устройства.

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

Выполнение алгоритма (1) быстро- 20 го преобразования Фурье рассматривается на примере для N 16 (см.фиг.2).

На первом этапе вычисления в соответствии с Ьиг.2 выполняется последовательность базовых операций по

Ьиг.3. Для этого на вход 30 устройства подается сигнал уровня "1", который поступает на управляющие входы коммутаторов 13 и 14 и переводит их в режим передачи данных с их входов на выходы.

Одновременно с приходом первого тактового импульса на вход 31 устройства HG входы 23 24,25 и 27 устройства подаются операнды базовой операции по Ьиг.3 а на входы 26 и 28 устройства — коэЬЬициенты данной базовой операции.

Поступление на входы сумматора 1 и вычитателя 5 первого и третьего операндов с входов 23 и 25 устройства соответственно позволяет получить на выходах сумматора 1 и вычитателя 5 сумму и разность первого и третьего операндов базовой операции по фиг.3. 45

При этом результатом с выхода вычитателя 5 поступает на вход умножителя 9, на другой вход которого подается первый коэффициент базовой опера= ции по Ьиг.3, что позволяет осуществить умножение разности первого и третьего операндов на первый коэффициент d< результат которого поступает через вход коммутатора 13 на вход регистра 20. В то же время результат сложения первого и третьего операндов с выхода сумматора 1 подается на вход регистра 18. Аналогично описанному на вход регистра 19 поступает сумма второго и четвертого операндов базовой операции по фиг.3 с выхода сумматора 2, а на вход регистра 21 подается разность второго и четвертого операндов, полученная на выходе вычитателя 6 и умноженная на второй коэффициент и в умножителе 10.

Через время

+ t + с где t — время выполнения операции с сложения; — время выполнения операций умножения; — время распространения сигнак ла через коммутатор, на вход 31 устройства поступает второй тактовый импульс, по которому осуществляется запись результатов вычисления в регистры 18-21, а сигнал уровня "1", поступающий с входа 30 на вход триггера 22, поступает на выход последнего. Сигнал высокого уровня с выхода триггера 22 поступает на управляющие вхоцы коммутаторов 15-17 и переводит их в режим передачи данных с входов на выходы. По приходу второго тактового импульса на входы 23

27 устройства поступают также очередные исходные операции для базовой операции по Ьиг.3, а на выход умножителя 7 †. второй выходной операнд данной базовой операции, являющийся результатом умножения кода, полученного на выходе вычитателя 7, на третий коэффициент d> базовой опера ции по фиг.3.

Операнды с выходов регистров 20 и

21 поступают на входы сумматора 4 н вычитателя 8 соответствечно, а также через входы коммутаторов 16 и 15 на входы вычитателя 8 и сумматора 4 ° В результате этого на выходе сумматора

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

8, поступает на вход умножителя 12, где осуществляется его умножение на коэффициент d9 в соответствии со структурой базовой операции по фиг.3.

К концу второго такта работы уст— ройства на выходы 32-35 устройства поступают выходные операнды с выходов соответственно сумматора 30 умножителя 11, сумматора 4 и умножи" теля 12 через вход коммутатора 17.

1631555

Кроме того на входах регистров 18-21 по аналогии с описанным формируются промежуточные операнды для данных, поступивших на входы 23-28 устройст5 ва на втором такте.

По приходу третьего тактового импульса на вход 31 устройства на выходы 32-35 устройства передаются результаты выполнения базовой операции по фиг.3, в первый — четвертый регистры 18-21 записываются промежуточные результаты, а на входы 23-29 подаются очередные значения входных операндов для базовой операции по фиг.3.

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

На последнем такте выполнения базовой операции ло фиг.3 на входах регистров 18-21 формируются промежуточные операнды, которые по приходу очередного импульса записываются в 25 указанные регистры. Пфи этом на вход 30 устройства поступает сигнал уровня "0", который переводит коммутаторы 13 и 14 в режим передачи данных с соответствующих входов на выходы. Кроме того, по тактовому импульсу на входы 23 и 24 устройства подаются вещественная и мнимая части первого операнда базовой операции по фиг ° 4, на входы 25 и 27 устройства поступают вещественная и мнимая части второго операнда базовой операции по фиг.4, на вход 29 устройства поступает третий коэффициент базовой операции по фиг.3. Это позво- 40 ляет к концу данного такта работы устройства на выходах сумматора 1 и

2 получить суммы вещественных и мнимых частей входных операндов в соответствии со структурой вычисления ба4ъ зовой операции по фиг.4, коды которых подаются на входы регистров 18 и 19 соответственно, а на выходах вычитателей 5 и 6 формируются разности вещественных и мнимых входных операндов, которью поступают через

50 входы коммутаторов 13 и 14 на входы регистров 20 и 2t.

Соединение, д-х разрядов выходов вичитателей 5 и 6 с (i+k)-ми разрядами входов коммутаторов 13 и 14 позволяет осуществтить умножение операндов поступающих на входы указанных коммутаторов на тривиальный множитель (6 .

По приходу очередного тактового импульса на вход 31 устройства на входы 32-33 устройства поцаются результаты выполнения базовой операции по фиг.3, в регистры 18-21 заносятся промежуточные результаты вычис— ления базовой операции по фиг.4, а на входы 23 — 27 устройства поступают исходные операнды базовой операции по фиг.4 ° Кроме того, сигнал уровня "0" с входа триггера 22 по тактовому импульсу поступает на его выход, что переводит коммутаторы

15 — 17 в режим передачи данных с соответствующих входов на выходы. Это разрешает прохождение кода с выхода регистра 19 через вход коммутатора 15 на вход сумматора 4, на другой вход которого подается код промежуточного результата с выхода регистра

20, что позволяет на выходе сумматора 4 сформировать код мнимой части результата выполнения базовой операции по фиг.4. На выходе вычитателя 8 образуется вещественная часть результата базовой операции по фиг.4 как результат вычитания данных, поступающих на вход вычитателя 8 с выхода регистра 18 через вход коммутатора 16.

Код вещественной части результата выполнения базовой операции по фиг.4 поступает через вход коммутатора 17 .на выход 35 устройства.

На данном такте работы устройства на входах регистров 18-21 формируются промежуточные результаты выполнения базовой операции по фиг.4. Таким образом максимальная задержка сигналов на данном такте вычисления

+ 2,, 2 С о по истечении которого на вход 31 устройства поступает очередной тактовый импульс, по которому на выходы

34 и 36 устройства подаются коды мнимой и вещественной части результата базовой: операции по фиг.4, в регистры 18-21 заносятся промежуточные результаты выполнения базовой операции по фиг.4, à íà входы 23,24, 25 и 27 устройства подаются очередные исходные операнды базовой операции по фиг.4.

Дальнейшие вычисления по данной базовой операции выполняются в устройстве по описанной схеме.

163 I 555

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

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

Фурье, содержащее первый, второй и третий сумматоры, первый, второй третий вычитателя, первый, второй, третий и четвертый регистры, первый, второй, третий и четвертый умножители, первый и второй коммутаторы, 10 причем выход первого регистра подключен к первым входам третьих сум- матора и вычитателя, а выход третьего сумматора является первым информационным выходом устройства, о т л и ч а- t5 ю щ е е с я тем, что, с целью повы шения быстродействия при обработке вещественных данных, в него введены четвертые сумматор и вычитатель, триггер, третий, четвертый и пятый 20 коммутаторы, причем выход первого сумматора подключен к информационному входу первого регистра, тактовый вход которого соединен с тактовыми входами триггера, второго, третьего и четвертого регистров и является, тактовым входом устройства, первым информационным входом которого являются соединенные между собой первые входы первого сумматора и перво- З0

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

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

1631555

Фиг.3

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

Редактор Л.Пчолинская Техред Л.Сердюкова Корректор Л.Пилипенко

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

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

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

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