Устройство для вычисления коэффициентов фурье

 

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

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

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

РЕСПУБЛИН.,SU„„ 1 2821

А1 а11 4 С 06 F 15 332

ОПИСАНИЕ ИЗО6РЕТЕНИЯ

Н ABTOPCKOIVIY СВИДЕТЕЛЬСТВУ

«1/

;; r

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3906612/24-24 (22) 07.06.85 (46) 07.01.87. Вюл. В 1 (72) В.В. Чернов (53) 681.32(088.8) (56) Авторское свидетельство СССР

Р 648989, кл. G 06 F 15/332, 1979.

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

У 1098004, кл. G 06 F 15/332, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТА ФУРЬЕ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для построения вычислительных устройств, использу- ющих алгоритм быстрого преобразования Фурье. Цель изобретения — увеличение точности вычислений. Цель доатигается за счет того, что устройство для вычисления коэффициентов Фурье состоит из арифметического блока, четырех блоков сдвига, четырех элементов И, двух регистров, элемента saдержки, двух счетчиков, трех сумматоров и соответствующих связей между узлами устройства. 4 ил.

1282156

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

Цель изобретения — увеличение точности вычисления.

Сущность предлагаемого изобретения заключается в том, что из всего масси-10 ва операндов текущей итерации вычислений, на которой было зафиксировано переполнение, сдвигаются только операнды, вызвавшие переполнение, остальные, как до переполнения, так и после 15 него, сдвигаются на следующей итерации. При этом, назначается дополнительная итерация после окончания вычислений по алгоритму БПФ, на которой сдвиги всех операндов массива вы- 20 равниваются, и которая представляет собой вывод результатов преобразования на внешнее устройство. Поэтому, в целом быстродействие устройства не теряется.

Повьппение точности вычислений предлагаемого устройства по сравнению с известным достигается за счет лучшего использования старшего разряда памяти операндов. Кроме того, весь мас- 3-0 сив операндов, кроме вызвавших переполнение, а их не более четырех,сдвигается на следующей итерации, т.е. сдвигаются результаты итерации вычислений, в то время как в известном 35 устройстве весь массив операндов сдвигается на игерации, на которой прогнозируется переполнение, т,е. сдвигают-! ся исходные данные для итерации вычислений. 40

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

Устройство содержит блоки 1-4 5р ,сдвига, арифметический блок 5, суммаI торы 6-8, счетчики 9 и 10 элементы

И 11-14, элемент 15 задержки„ реги стры 16 и 17. На фиг.1 обозначены:

Re M u Im M, Re А и Im А, Re В и Im В -55 реальная и мнимая части тригонометрического коэффициента, первого и второго операндов соответственно; Re X .и Im Х, Re Y u Im Y — реальная и мнимая части соответственно первого и второго операндов первого результата; Re А и Im А, Re В" и Im В реальная и мнимая части соответственно первого и второго операндов второго результата; порядок А, В, Х, Y —величина сдвига вправо операндов А, В, Х, Y- ТИ1, ТИ2 — тактовые импульсы первой и второй серий; ОЗУ вЂ” оперативное запоминающее устройство;

+1 — суммирующий вход счетчика. В соссостав арифметического блока (фиг. 2) входят умножители 18-21, сумматоры

22-27, элемент ИЛИ 28. На временных диаграммах работы устройства (фиг. 3) в качестве примера приведено возникновение переполнения в первом такте.

На фиг. 4 представлен алгоритм работы устройства, где обозначено > — содержимое, например (счетчик 10 содержимое счетчика 10.

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

В ОЗУ хранится входной массив кдмплексных операндов А, В „ и тригонол метрических коэффициентов (4„и выходной массив комплексных операндов, X» Y, где n = 0,1,..., N/2-1, N— величйна массива — число точек БПФ.

Далее в обозначениях операндов и тригонометрических коэффициентов величина и опущена. Каждый операнд представлен реальной часты- ReA, ReB, ReX, ReY,.ìíèìîé 1астью ImA, ImB, ImX, ImY и величиной сдвига вправо порядок А, В, Х, Y. Входные и выходные операнды связаны соотношением в комплексной форме: Х = A+BW, Y = -BW или в действительной форме:

ReX=ReA+(ReB ReW-ImB . ImW), ImX=ImA+ (ReB ° ImW+ImB ReW) „

ReY=ReA-(ReB ReW-ImB ТшН), (1)

Тпй=-ImA-(ReB ImW+ImB ReW) .

В исходном положении порядки А и

В равны нулю, счетчики 9 и 10, реги стры 16 и 17 сброшены в нулевое состояние, элементы И 12 и 13 открыты логическим нулем, приходящим с выхода арифметического блока 5 через эле-. .мент И 14.

Тактовый импульс, приходящий по входу ТИ1, проходит через элемент И

12 и записывает в регистр адреса ОЗУ информацию, которая является адресом считываемых из ОЗУ и записываемых в

ОЗУ операндов и их порядков. По этому

3 12821 адресу из ОЗУ считываются операнды

ReB, ImB, ReA, ImA. поступающие соответственно на блоки 1-4 сдвигов, считываются порядки операндов В и А, поступающие на вычитающие входы сум- S маторов 6 и 7 соответственно, считываются части тригонометрического коэффициента ReW, ImW. Пройдя через блоки сдвигов, реальная и мнимая части операндов А и В сдвигаются вправо на 10 величины

Сдвиг А = < счетчик 10 + < регистр 17> — порядок А;

Сдвиг В = < счетчик 10 > + — порядок В.

На первой итерации вычислений

"двиг А = О, сдвиг В = О. Далее ReM, ImW, ReB О ImB (ñäâèíóòûå ReB, ImB) поступают на умножители 18-21, на выходах которых формируются соответственно произведения ReB ReW, ImB . ImW, ReB ImW, ImB КаЫ.Выход умножителя

18 соединен с суммирующим входом сум- 25 матора 22, умножителя 19 — с вычитающим входом, умножителей 20 и 21 — с суммирующими входами сумматора 23.На выходе сумматоров 22 и 23 формируется разность ReB ReW — ImB . ImW u

I I сумма ReB ImW + ЕшВ ReW. Эти разность и сумма, а также ReA, ImA (сдвинутые ReA, ImA) поступают на сумматоры 24-27, выходы которых являются выходами операндов ReX, ImX, ReY, ImY, определяемых выражением (1).35

Если в процессе формирования сумм и разностей не происходит переполнения разрядной сетки (не возникает переноса из старшего разряда) ни одного из сумматоров 22-27, то операнды

ReX, ImX, ReY, ImY и их порядки — порядок Х, У, снимаемые с выхода счетчика 10, записываются в ОЗУ импульсом, проходящим через элемент И 13 по входу тактовых импульсов ТИ2.

Если в одном из сумматоров 22-27 возникло переполнение, то оно, проходя через элемент ИЛИ 28 и элемент

И 14, запрещает прохождение импуль- 50 сов ТИ1 и ТИ2 через элементы И 12 и

13, блокируя тем самым запись новой информации в регистр адреса ОЗУ и запись выходных операндов Х, Y в ОЗУ.

При этом считанные операнды в первом 55 такте (фиг. 3) продолжают считываться и во 2 такте. При этом импульс переполнения открывает элемент И 1 1.

Очередной импульс серии ТИ1,проходя

56 4 через элемент И 11, прибавляет к о держимому счетчиков 9 и 10 единицу.

Содержимое счетчика 10 (в данном случае 01), проходя через сумматоры

8, 7 и 6, поступает на управляющие входы блоков сдвига 1-4. При этом операнды, прошедшие через блоки,сдвигаются вправо (в данном случае на один разряд). Если переполнение на выходе арифметического блока 5 не пропадает, в с етчики 9 и 10 добавляется еще единица и операнды сдвигаются на 2 разряда вправо. Из выражения (1) можно заключить, что величина сдвига на одной итерации не превышает двух. Эта величина (содержимое счетчика 10) переписывается по установочным входам в регистр 16. После сдвига операндов переполнение на выходе арифметического блока 5 пропадает и элементы

И 12 и 13 открываются. Очередной импульс серии ТИ2 через элемент И 13 записывает выходные операнды Х, Y u их порядки в ОЗУ. Далее импульс серии ТИ1 через элемент И 12 записывает новый адрес в регистр адреса ОЗУ и сбрасывает счетчик 10 в нулевое положение.После окончания итерации вычислений содержимое регистра 15 переписывается в регистр 17, а регистр

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

Так как, величина сдвига на одной итерации не превышает двух, то разрядность сумматоров 6-8, счетчика 10, регистров 16 и 17 может быть взята равная двум. Счетчик 9 фиксирует общее количество переполнений. Разрядность его равна числу итераций вычисления БПФ. Выход его является выходом масштабного коэффициента преобразования Фурье.

После окончания последней итерации вычисления по алгоритму БПФ назначается дополнительная итерация.При этом блокируется прохождение сигнала переполнения через элемент И 14, а следовательно, и прохождение импульсов серии ТИ1 на суммирующие входы счетчиков 9 и 10. На дополнительной итерации считывание операндов происходит аналогично считыванию на предыдущих итерациях. Операнды проходят

5 128215 блоки 1-4 сдвига, порядки их сравниваются и поступают в обход арифмети1 h ческого блока 5 на выходы ReA, ImA

Il Ъ

ReB, Im8, откуда выводятся на внешнее устройство. 5

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

Устройство для вычисления коэффициента Фурье, содержащее четыре блока сдвига, два регистра, элемент за- щ держки, первый счетчик,и арифметический блок, входы. реальной и мнимой частей первого операнда и входы реальной и мнимой частей второго операнда которого подключены к выходам 15 соответственно первого, второго,третьего и четвертого блоков сдвига, информационные входы которых являются .соответственно входами реальной и мнимой частей первого и реальной и gp мнимой частей второго операндов устройства, выходом масштабирующего коэффициента которого является информационный выход первого счетчика, выход первого регистра подключен к информа- 25 ционному входу второго регистра,тактовый вход которого соединен с входом элемента задержки и является входом конца итерации устройства, выходами реальной и мнимой частей первого и Зр реальной и мнимой частей второго результатов базовой операции являются соответственно выкоды реальной и мнимой частей первого и реальной и мнимой частей второго результатов арифметического блока, входы реальной и мнимой частей коэффициента которого являются входами соответственно реапьной и мнимой частей коэффициента устройства, а выход элемента задерж- 4р ки подключен к установочному входу первого регистра, о т л. и ч а ющ е е с я тем, что, с целью увеличения точности, в него введены четыре

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

1282156

1282156

1И2

16 счетчик 910!

Лапиа Ф gems аФ гса ИУ

Фиг.д

Фиа 4

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

Техред М.Ходанич

Редактор И. Шулла

Корректор Е. Сирохман

Заказ 7269/49 Тираж б70 Подписное

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

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

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