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

СОЮЗ СОВЕТСНИСОЦИАЛ ИСТИЧЕСНИРЕСПУБЛИН ЛО, 12821 94 С 06 Г 15 332 ОПИСАНИЕ ИЗОБРЕТЕН ф 3/3 жет быть использовано для вычислительных устройств, ющих алгоритм быстрого пр ния Фурье, Цель изобретен чение точности вычислений тигается за счет того, чт во для вычисления коэффиц состоит из арифметическог тырех блоков сдвига, четь тов И, двух регистров, эл держки, двух счетчиков, тр ров и соответствующих свяэ лами устройства. 4 ил. построения мента за ех сумматоей между узГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ АВТОРСКОМУ СВИДЕ(56) Авторское свидетельство СССР У 648989, кл. С 06 Г 15/332, 1979,Авторское свидетельство СССР У 1098004, кл. С 06 Г 15/332, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТА ФУРЬЕ(57) Изобретение относится к автоматике и вычислительной технике и моиспользу- еобразоваия - увелиЦель доао устройстиентов Фурье о блока, черех элеменИзобретение относится к автоматикеи вычислительной технике и может бытьиспользовано для построения вычислительных устройств, использующих алгоритм быстрого преобразования Фурье (БПФ).Цель изобретения - увеличение точности вычисления.Сущность предлагаемого изобретения заключается в том, что из всего масси 10 ва операндов текущей итерации вычислений, на которой было зафиксировано переполнение, сдвигаются только операнды, вызвавшие переполнение, остальные, как до переполнения, так и после 15 него, сдвигаются на следующей итерации. При этом, назначается дополнительная итерация после окончания вычислений по алгоритму БПФ, на которой сдвиги всех операндов массива вы равниваются, и которая представляет собой вывод результатов преобразования на внешнее устройство. Поэтому, в целом быстродействие устройства не теряется.Повьппение точности вычислений предлагаемого устройства по сравнению с известным достигается за счет лучшего использования старшего разряда памяти операндов. Кроме того, весь мас сив операндов, кроме вызвавших переполнение, а их не более четырех,сдвигается на следующей итерации, т.е. сдвигаются результаты итерации вычислений, в то время как в известном 35 устройстве весь массив операндов сдвигается на игерации, на которой прогнозируется переполнение, т,е. сдвигаются исходные данные для итерации вычислений. 40На фиг. 1 представлена функциональная схема устройства для вычисления коэффициента Фурье; на фиг, 2 - вариант реализации арифметического блока; на фиг, 3 - временные диаграм мы работы устройства; на фиг.4 - блок-схема алгоритма работы устройства. Устройство содержит блоки 1-4 50 ,сдвига, арифметический блок 5, сумматоры 6-8, счетчики 9 и 10, элементы И 11-14, элемент 15 задержки регистры 16 и 17. На фиг.1 обозначены: Ве Ии 1 ш И, Ке А и Хш А, Ке В и 1 ш В -55 реальная и мнимая части тригонометрического коэффициента, первого и второго операндов соответственно; Ке Х и Хш Х, Ке У и 1 ш У - реальная и мнимая части соответственно первогои второго операндов первого результата; Ке А и 1 ш А , Ке В" и 1 ш Вфреальная и мнимая части соответственно первого и второго операндов второго результата; порядок А, В, Х, Ъ.величина сдвига вправо операндов А,В, Х, У; ТИ 1, ТИ 2 - тактовые импульсы первой и второй серий; ОЗУ - оперативное запоминающее устройство;+1 - суммирующий вход счетчика. В соссостав арифметического блока (фиг. 2)входят умножители 18-21, сумматоры22-27, элемент ИЛИ 28. На временныхдиаграммах работы устройства (фиг, 3)в качестве примера приведено возникновение переполнения в первом такте.На фиг. 4 представлен алгоритм работыустройства, где обозначено с - содержимое, например ссчетчик 10)содержимое счетчика 10.Устройство работает следующим образом.В ОЗУ хранится входной массив комплексных операндов А , Ви тригонолфметрических коэффициентов 4 и выходной массив комплексных операндов,Х, У , где и = 0,1, , Н/2-1, иввеличйна массива - число точек БПФ,Далее в обозначениях операндов и тригонометрических коэффициентов величина и опущена. Каждый операнд представлен реальной частыс КеА, КеВ,КеХ, КеУ,.мнимой частью 1 шА, ХшВ,1 шХ, Хпй и величиной сдвига вправопорядок А, В, Х, 7. Входные и выходные операнды связаны соотношениемв комплексной форме: Х = А+ВЫ,У = А-ВМ или в действительной форме:КеХ=КеА+(КеВ КеУ-ХшВ ХшИ),1 шХ=1 шА+(КеВХшЧ+ХшВ КеЫ)КеУ=КеА-(КеВ КеН-ХшВ 1 шН),(1)ХшУ=-ХшА-(КеВ ХшИ+ХшВ КеЧ),В исходном положении порядки А и В равны нулю, счетчики 9 и 10, реги . стры 16 и 17 сброшены в нулевое состояние, элементы И 12 и 13 открыты логическим нулем, приходящим с выхода арифметического блока 5 через эле-. мент И 14.Тактовый импульс, приходящий повходу ТИ 1, проходит через элемент И12 и записывает в регистр адреса ОЗУинформацию, которая является адресомсчитываемых из ОЗУ и записываемых вОЗУ операндов и их порядков. По этому3 12821 адресу из ОЗУ считываются операнды КеВ, 1 шВ, КеА, 1 шА. поступающие соответственно на блоки 1-4 сдвигов, считываются порядки операндов В и А, поступающие на вычитающие входы сум маторов 6 и 7 соответственно, считываются части тригонометрического коэффициента КеИ, 1 шИ. Пройдя через блоки сдвигов, реальная и мнимая части операндов А и В сдвигаются вправо на 10 величины Сдвиг А = с счетчик 10 +регистр 17) - порядок А;Сдвиг В = ссчетчик 10+ срегистр 17- порядок В,На первой итерации вычислений "двиг А = О, сдвиг В = О. Далее КеИ, 1 шИ, КеВ 0 1 шВ (сдвинутые КеВ, 1 шВ) поступают на умножители 18-21, на выходах которых формируются соответственно произведения КеВ Кей, 1 шВ . 1 шИ, КеВ 1 пЯ, 1 шВ ф КаЫ.Выход умножителя 18 соединен с суммирующим входом сум матора 22, умножителя 19 - с вычитающим входом, умножителей 20 и 21 - с суммирующими входами сумматора 23.На выходе сумматоров 22 и 23 формируется разность КеВ КеУ - 1 шВ 1 шУ и1 )сумма КеВ 1 шУ + 1 шВ КеИ. Эти разность и сумма, а также КеА , 1 шА (сдвинутые КеА, 1 шА) поступают на сумматоры 24-27, выходы которых являются выходами операндов КеХ, 1 шХ, КеУ, 1 шУ, определяемых выражением (1).35 Если в процессе формирования сумм и разностей не происходит переполнения разрядной сетки (не возникает переноса из старшего разряда) ни одного из сумматоров 22-27, то операнды40 КеХ, 1 шХ, Ке 7, 1 шУ и их порядки - порядок Х, У, снимаемые с выхода счетчика 10, записываются в ОЗУ импульсом, проходящим через элемент И 13 по входу тактовых импульсов ТИ 2.45Если в одном из сумматоров 22-27 возникло переполнение, то оно, проходя через элемент ИЛИ 28 и элемент И 14, запрещает прохождение импуль сов ТИ 1 и ТИ 2 через элементы И 12 и 13, блокируя тем самым запись новой информации в регистр адреса ОЗУ и запись выходных операндов Х, У в ОЗУ.При этом считанные операнды в первом 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записывает выходные операнды Х, У иих порядки в ОЗУ. Далее импульс серии ТИ 1 через элемент И 12 записываетновый адрес в регистр адреса ОЗУ исбрасывает счетчик 10 в нулевое положение.После окончания итерации вычислений содержимое регистра 15 переписывается в регистр 17, а регистр16 сбрасывает в нулевое положениечерез .элемент 15 задержки. На следующей итерации сдвигаются операнды,невызвавшие переполнения на текущейитерации, а величина сдвига определяется содержимым регистра 17 и приходящим порядком операндов,Так как, величина сдвига на однойитерации не превышает двух, то разрядность сумматоров 6-8, счетчика 10,регистров 16 и 17 может быть взятаравная двум. Счетчик 9 фиксирует общее количество переполнений, Разрядность его равна числу итераций вычисления БПФ. Выход его является выходом масштабного коэффициента преобразования фурье.После окончания последней итерации вычисления по алгоритму БПф назначается дополнительная итерация.Приэтом блокируется прохождение сигналапереполнения через элемент И 14, аследовательно, и прохождение импульсов серии ТИ 1 на суммирующие входысчетчиков 9 и 10, На дополнительнойитерации считывание операндов происходит аналогично считыванию на предыдущих итерациях. Операнды проходят5 128215 блоки 1-4 сдвига, порядки их сравниваются и поступают в обход арифметиЭ ческого блока 5 на выходы КеА , 1 шАОКеВ , шВ, откуда выводятся на внешнее устройство. 5Формула изобретенияУстройство для вычисления коэффициента Фурье, содержащее четыре блока сдвига, два регистра, элемент за- щ держки, первый счетчик,и арифметический блок, входы. реальной и мнимой частей первого операнда и входы реальной и мнимой частей второго операнда которого подключены к выходам 15 соответственно первого, второго,третьего и четвертого блоков сдвига, информационные входы которых являются .соответственно входами реальной и мнимой частей первого и реальной и 2 О мнимой частей второго операндов устройства, выходом масштабирующего коэффициента которого является информационный выход первого счетчика, выход первого регистра подключен к информа ционному входу второго регистра,так" товый вход которого соединен с входом элемента задержки и является входом конца итерации устройства, выходами реальной и мнимой частей первого и 3 реальной и мнимой частей второго результатов базовой операции являются соответственно вьиоды реальной и мнимой частей первого и реальной и мнимой частей второго результатов арифметического блока, входы реальной и мнимой частей коэффициента которого являются входами соответственно реапьной и мнимой частей коэффициента устройства, а выход элемента задерж- щ ки подключен к установочному входу первого регистра, о т л. и ч а ю - щ е е с я тем, что, с целью увеличения точности, в него введены четыре 6 6элемента И, три сумматора и второйсчетчик, информационный выход которого является выходом порядка устройства и подключен к информационномувходу первого регистра и первому входу первого сумматора, выход которогоподключен к первым входам второго итретьего сумматоров, вторые входы которых являются входами порядков соответственно первого и второго операндов устройства, выход второго регистра подключен к второму входу первогосумматора, выход второго сумматораподключен к управляющим входам первого и второго блоков сдвига, выходтретьего сумматора подключен к управляющим входам третьего и четвертогоблоков сдвига, выход переполненияарифметического блока подключен к первому входу первого элемента И,выходкоторого подключен к первому входувторого элемента И и инверсным входомтретьего и четвертого элементов И,выход второго элемента И подключен ксчетным входам первого и второго счетчиков, выход третьего элемента И является выходом записи адреса памятиустройства и подключен к входу обнуления второго счетчика, выход четвертого элемента И является выходом записив память устройства, второй вход второго элемента И и прямой вход третьегоэлемента И являются первым тактовымвходом устройства, вторым тактовым .входом которого является прямой входчетвертого элемента И, а инверсныйвход первого элемента И является входом задания дополнительной итерацииустройства, выходы первого, второго,третьего и четвертого блоков сдвигаявляются соответственно выходами реальной и мнимой частей первого и реальнойи мнимой частей второго коэффициента фурье устройства.1282156 16 счетчик 910 апиа Ф реги аФ еса ИУ Редактор И. Шулла Составитель А, БараноТехред М.Ходанич ректор Е хма акаэ 7269/4 одписное изводственно-полиграфическое предприятие, г. Ужгород, ул. Проекты Тираж б 70 КИПИ Государственног по делам изобретений 35, Москва, Ж, Ра комитета СССР открытий ская наб., д.