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

11282156

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

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

Сущность предлагаемого изобретения

5 д

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

Повьшение точности вычислений предлагаемого устройства по сравнению с известным достигается за счет лучшего использования старшего разряда памнимая части соответственно первого и второго операндов первого результата; Re А и Im А , Re В и Im реальная и мнимая части соответственно первого и второго операндов второго результата; порядок А, В, X, Y - величина сдвига вправо операндов А, В, X, Y; ТИ1, ТИ2 - тактовые импульсы первой и второй серий; ОЗУ - оперативное запоминающее устройство; +1 - суммирующий вход счетчика. В сос- состав арифметического блока (фиг. 2) входят умножители 18-21, сумматоры 22-27, элемент ИЛИ 28. На временных 5 диаграммах работы устройства (фиг. 3) в качестве примера приведено возникновение переполнения в первом такте. На фиг. 4 представлен алгоритм работы устройства, где обозначено - содержимое, например : счетчик 10 содержимое счетчика 10.

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

В ОЗУ хранится входной массив кОми тригоно и выходной массив комплексных операндов, Х, Y. , где п 0,1,..., N/2-1, N 25

плексных операндов А , В j метрических коэффициентов W

h

величина массива - число точек БПФ.

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

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

Устройство содержит блоки 1-4 .сдвига, арифметический блок 5, сумматоры 6-8, счетчики 9 и 10, элементы И 11-14, элемент 15 задержки регистры 16 и 17. На фиг„1 обозначены:

Тактовый импульс, приходящий по

Re WHim W, Re Аи1т A, Re В и Im В -55 входу ТИ1, проходит через элемент И

реальная и мнимая части тригонометрического коэффициента, первого и второго операндов соответственно; Re X и Im X, Re Y и Im Y - реальная и

0

мнимая части соответственно первого и второго операндов первого результата; Re А и Im А , Re В и Im реальная и мнимая части соответственно первого и второго операндов второго результата; порядок А, В, X, Y - величина сдвига вправо операндов А, В, X, Y; ТИ1, ТИ2 - тактовые импульсы первой и второй серий; ОЗУ - оперативное запоминающее устройство; +1 - суммирующий вход счетчика. В сос- состав арифметического блока (фиг. 2) входят умножители 18-21, сумматоры 22-27, элемент ИЛИ 28. На временных 5 диаграммах работы устройства (фиг. 3) в качестве примера приведено возникновение переполнения в первом такте. На фиг. 4 представлен алгоритм работы устройства, где обозначено - содержимое, например : счетчик 10 содержимое счетчика 10.

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

В ОЗУ хранится входной массив кОми тригоно и выходной массив комплексных операндов, Х, Y. , где п 0,1,..., N/2-1, N 5

плексных операндов А , В j метрических коэффициентов W

h

величина массива - число точек БПФ.

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

(ReB ReW-ImB -ImW), (ReB ImW+ImB ReW), (ReBReW-ImBImW), ImY IniA- (ReB ImW-UmB ReW) .

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

Тактовый импульс, приходящий по

входу ТИ1, проходит через элемент И

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

312821

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

Сдвиг А счетчик 10 + регистр 17 - порядок А;

Сдвиг Б счетчик 10 ре- гистр 17 - порядок В.

На первой итерации вычислений гдвиг А О, сдвиг В 0. Далее ReW, ImW, ReB О ImB% (сдвинутые ReB, ImB) поступают на умножители 18-21, на выходах которых формируются соот ветст венно произведения ReB « ReW, ImB . ImW ReB ImW, ImB RaW.Выход умножителя 18 соединен с суммирующим входом сум- матора 22, умножителя 19 - с вычитающим входом, умножителей 20 и 21 - с суммирующими входами сумматора 23.На выходе сумматоров 22 и 23 формируется разность ReB ReW - ImB ImW и сумма ReB ImW + 1тВ - ReW. Эти разность и сумма, а также ReA , ImA (сдвинутые ReA, ImA) поступают на сумматоры 24-27, выходы которых являются выходами операндов ReX, ImX, ReY, ImY, определяемых выражением (1) Если в процессе формирования сумм и разностей не происходит переполнения разрядной сетки (не возникает переноса из старшего разряда) ни одного из сумматоров 22-27, то операнды ReX, ImX, ReY, ImY и их порядки - порядок X, Y, снимаемые с выхода счетчика 10, записываются в ОЗУ импульсом, проходящим через элемент И 13 по входу тактовых импульсов ТИ2.

Если в одном из сумматоров 22-27 возникло переполнение, то оно, проходя через элемент ИЛИ 28 и элемент И 14, запрещает прохождение импуль- сов ТИ1 и ТИ2 через элементы И 12 и 13, блокируя тем самым запись новой информации в регистр адреса ОЗУ и запись выходных операндов X, Y в ОЗУ, При этом считанные операнды в первом такте (фиг. 3) продолжают считываться и во 2 такте. При этом импульс переполнения открывает элемент И 11. Очередной импульс серии ТИ1,проходя

fO

15

5 .

0

5

0

564

через элемент И 11, прибавляет к содержимому счетчиков 9 и 10 единицу. Содержимое счетчика 10 (в данном случае 01), проходя через сумматоры 8, 7 и 6, поступает на управляющие входы блоков сдвига 1-4. При этом операнды, прошедшие через блоки,сдвигаются вправо (в данном случае на один разряд). Если переполнение на выходе арифметического блока 5 не пропадает, в сметчики 9 и 10 добавляется еще единица и операнды сдвигаются на 2 вправо. Из выражения (1) можно зак- лючитд), что величина сдвига на одной итерации не превышает двух. Эта величина (содержимое счетчика 10) пе- реписывается по установочным входам в регистр 16. После сдвига операндов переполнение на выходе арифметического блока 5 пропадает и элементы И 12 и 13 открываются. Очередной импульс серии ТИ2 через элемент НО записьтает выходные операнды X, Y и их порядки в ОЗУ. Далее импульс серии ТИ1 через элемент И 12 записывает новый адрес в регистр адреса ОЗУ и сбрасывает счетчик 10 в нулевое положение.После окончания итерации вычислений содержимое регистра 6 переписывается в регистр 17, а регистр 16 сбрасывает в нулевое положение через .элемент 15 задержки. На следующей итерации сдвигаются операн;(ы,не вызвавщие переполнения на текущей итерации, а величина сдвига определяется содержимым регистра 17 и приходящим порядком операндов.

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

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

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

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

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

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

JBToporo элемента И и инверсным входом Третьего и четвертого элементов И, выход второго элемента И подключен к

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

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

вход первого элемента И является входом задания дополнительной итерации устройства, выходы первого, второ го.

мнимой частей коэффициента которого являются входами соответственно ре- апьной и мнимой частей 1соэффициента

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

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

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

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

JBToporo элемента И и инверсным входом Третьего и четвертого элементов И, выход второго элемента И подключен к

0 вому входу первого элемента И,выход которого подключен к первому входу 25 счетным входам первого и второго счет- чиков,выход третьего элемента И яв-

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

/4

Rev/

3mw

Переполнение I

ReK

ш

Jw/r.

Key,

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

W/Л

Конец итерацаи. л

Re A

47

JfnA

Res i JmB

Порядок( ПорядокУ

fPuz.1

(Риг. 2

CSpoc cvemuuKoSg, W регистроб 16,17

Запаса о рсгистр айреса Ощ сорос ctfemtJUKa fO

Пересы/iKa -счетчик регистр f6

Порегистри адреса

Ideas A cvemvux/(l + f-pesucmpf7 -fjoflffL док A,В

H6cvemuuK3, fff(

Запись Х,Уи порядка Х УдОЗУ

Пере сьмка -рееаспр 6 регистр //

Нет

Запись о регистр адреса о ЗУ, сорос cvemvuKa Ю

Вшбод масштабного коэффа иемтгсг на , онещнее устройстоо

( Конец J

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

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

Техред М.Ходанич Корректор Е. Сирохман

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

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

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

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