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

(Л

DO 00 00 00

со со

Изобретение относится к вычисли- |гельиой технике и может быть исполь- Ьовано в системах цифровой обработки сигналов в реальном масштабе времени

Цель изобретения - расширение функциональных возможностей устройства за счет выполнения фильтрации и разделения спектров.

На фиг, 1 представлена блок-схема устройства; на фиг. 2 - схема блока Синхронизации- на фиг. 3-5 - временные )циаграммы работы блока синхронизации выполнения команд БПФ,, разделения спектров и умножения комплексных Macривов; на фиг. 6 - временная диаграм- работы устройства; на фиг. 7 - |блок-схема блока управления сдвигом,

Устройство содержит,сдвигатель 1 Вещественной части числа, сдвигатель 2 мнимой части числа, умножители 3-6, промежуточные регистры 7 и 8, мультиплексоры 9-12 промежуточные регистры 13-16, сумматоры 17 и 18, выходные регистры 19 и 20, вьгх;оды 21 и 22 устройства, блок 23 управления сдвигом, входы 24 и 25 вещественной и мнимой частей весового коэффициента и блок

26синхронизации.

Блок 26 синхронизации имеет вход

27запуска, входы 28--31 задания ре

жима, двенадцать выходов 32-43 и

Содержит генератор 44 тактовых импуль ;сов, распределитель 45 импульсов, че- |тыре элемента 2И-ИЛИ 46-49, шесть эле 1ментов И 50-55, три RS-триггера 56- 58, два D-триггера 59 и 60 и элемент ИЛИ 61.

Блок управления сдвигом (фиг,7) содержит выход 62, преобразователи 63 и 64 дополнительного кода в прямой узел 65 постоянной памяти, элемент ИЛИ 66, а также регистры 67 и 68.

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

С приходом сигнала Пуск распределитель 45 формирует из двадцати двух тактовых импульсов последовательность. В соответствии с установленной на одном из входов 28-30 командой блок синхронизации вырабатывает управляюпц-ie сигналы 32-43 согласно временным диаграммам (фиг. 3-5 соответственно).

Устройство реализует алгоритм БПФ в соответствии с выражениями:

R,W. ;(1)

W; (2)

А.н . Б.,, A,

где А.

комплексные числа.

Для перемножения двух комплексных чисел В(; W необходимо выполнить четьфе операции умножения, одно сложение и одно вычитание:

Re В, W J ReB, - ReW,, I W, ; (3) ,. -Re W.+Re BC , . (4)

Приведенный алгоритм в предлагаемом устройстве выполняется следующим образом.

Подлежащие обработке комплексные операнды А: и W , а также значения

j

Q 5

0

п

5

0

5

весовых коэффициентов поступают на входы устройства. Вначале из ОЗУ считывается операнд Bi. и через сдвига- тели 1 и 2 реальная часть записывается в умножители 3 и 6, а мнимая часть - в умножители 4 и 5. На сдви- гателях осуществляется по сигналу 60 из блока 23 сдвиг операндов на один разряд или на два разряда вправо или передача операндов без сдвига. Значения весовых коэффициентов поступают на соответствующие входы умножителей 3-6 (на входы множителя). Второй операнд At записывается в регистры 7 и . 8 (реальная и мнимая части соответственно) , также пройдя через сдви- гатели 1 и 2.

На выходах блоков умножения формируются одновременно четыре произведения ReB -Re Wv , 1„,В) , Re W; , WL , которые через входы мультиплексоров 9-12 записыва- 5 ются в промежуточные регистры 13-16. Введение в устройство промежуточных регистров 13-16 позволяет выполнение операций умножения и сложения совместить во времени, i- т.е. результаты умножения операндов Bi и W,; суммируются согласно алгоритму, а новые операнды В и W,-,. перемножаются в умножителях. После выполнения первого суммирования на выходах сумматоров 17 и 18 формируются суммы согласно вьфажениям (3) и (4), которые записываются в регистры 14 и 16 через входы мультиплексоров 10 и 12, через первые входы мультиплексоров 9 и 11 содержимое регистров 7 и 8 (второй операнд) переписывается в регистры 13 и 15.

После вьшолнения операции вычитания на выходе сумматоров 17 и 18 формируются суммы:

ReB ReA,-(ReB;-ReW,-I,B, ,);(5) ., (1„,В.. ReW.+ReB,, ),(6) которые соответствуют операнду результата Bitf С выходов сумматоров

31388893

17 и 18 они записываются в регистры 2) произвести вычисление коэффи- 19 и 20, а затем в ОЗУ, После выпол- циентов Фурье от массива-размером N; нения третьего цикла суммирования на выходах сумматоров 17 и 18 формируются суммы:

ReAi., ReA, + (ReB, - ReW-I B -I W, ) ; (7) 1.;п L.A. +(I«B: - ReW +ReBi ) , (8)

3) произвести разделение спектров по следующему алгоритму:

(9)

B(j) ШЦА iN:i) .

B(N-j) iillAjNli) ,

(10)

B(N-j) iillAjNli) ,

которые соответствуют операнду результата А . С выходов сумматоров 17 и Ю де A(J) и A(N-j)-исходные комплекс.-(

1В они записываются в регистры 19 и 20, а затем в ОЗУ. .

На временной диаграмме (фиг.6) показано взаимодействие устройств по этапам вычислений:

1 этап - считывание из ОЗУ операндов В и W в умножители 3-6; II этап - считывание операндов AI

ные числа;

знак комплексного сопряженного числа; B(j) и B(N-j)- комплексные числа результата операции.

4) произвести объединение масси- ВОВ по алгоритму выражений (1) и- (2). Таким образом, для обработки дейв регистры 7 и 8, начало 20 ствительных массивов необходимо про- умножения операндов извести вычисление по формулам (9)

и (10). При выполнении этой операции устройство работает следующим образом. На входы весового коэффициента

III этап - считьгоание операндов В (2) и W (2), завершение умножения и перепись реус

зультатов умножения в-ре- - постоянно поступают следующие зна- гистры 13-16;чения: ReW: 1, , с тем, чтобы

IV этап - считывание операнда А(2) организовать передачу первого опе- в регистры 7 и 8, начало ранда через умножители без введения умножения операндов Bt(2) дополнительных связей в устройство. W(2), обработка операн-30 Первый операнд А(j ) считывается доз в сумматорах согласно из ОЗУ, и через сдвигатели 1 и 2 ре- выражениям (3)-(6), альная часть поступает в умножители V этап - считывание операндов В 3 и 6, а мнимая - в умножители 4 и 5, (3) и W(3), заверщение Второй операнд A(N-j) через сдвигате- умножения и перепись ре- 35 ли 1 и 2 записьшается в промежуточ- зультатов умножения в ре ные регистры 7 и 8. После вьшолнения гистры 13-16, обработка умножения на выходах умножителя 3 операндов в сумматорах будет ReA(j), а на выходе умножителя согласно выражениям (7) 5 - (j). Затем вьтолняется пере- и (8), запись результатов 40 пись содержимого регистров 7 и 8 в базовой операции в ОЗУ регистры 13 и 15 через мультиплексоры 9 и 11 соответственно. Результаты умножения с выходов умножителей 3 и 5 переписываются через мульи т.д.

Таким образом, начиная с I этапа считывание операндов из ОЗУ, умножение операндов, суммирование и запись 45 типлексоры 10 и 12 в регистры 14 и результатов в, ОЗУ производятся од- 16 соответственно. Результаты алге- новременно. Это позволяет обеспечить высокое быстродействие устройства.

. браического суммирования с выходов

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

суммирования на выходах сумматоров 17 и 18 образуются суммь :

ReB(N-j)-ReA(j)-ReA(N-j) (11)

вительных массивов чисел. При обработке действительных массивов необходимо:. . 1) произвести упаковку (преобразование)-входного массива, заключающую- 55 ся в том, что нечетные отсчеты записываются в действительную часть комплексного числа, а четные - в мнимую часть комплексного числа

(N-j)(j)-H,,A(N-j). (12).

Эти значения переписываются в выходные регистры 19 н 20, л затем записываются в ОЗУ.

2) произвести вычисление коэффи- циентов Фурье от массива-размером N;

3) произвести разделение спектров по следующему алгоритму:

(9)

B(j) ШЦА iN:i) .

B(N-j) iillAjNli) ,

(10)

A(J) и A(N-j)-исходные комплекс

ные числа;

знак компле сопряженног -j)- комплексны результата ции.

(N-j)(j)-H,,A(N-j). (12).

Эти значения переписываются в выходные регистры 19 н 20, л затем записываются в ОЗУ.

Таким образом, доп элнительная операция, необходимая для обработки действительных массивов, выполняется на tOM же самом оборудовании, что и базовая операция БПФ, Операция умножения комплексных массивов выполняется при получении команды на входе 30. Йреобразование операндов осуществляется в соответствии с вьфажениями СЗ) и (4), Утфавляющие сигналы вырабатываются в соответствии с времен- «ой диаграммой на фиг.5 По сигналу 32 на входы умножителей :записьшаются- входные операнды (первый операнд Через сдвигатели,- а второй - по входу W). Результаты перемножения через входы мультиплексоров 9-12 (по фигналам 34 и 35 ушравления) перепи- бываются в регистры 13-16 (36 и 37). ра сумматоре 17 фор1 шруется разность |)перандов (38), а на сумматоре 18 - умма (39). Результаты операции записываются в регистры 19 и 20 - дей йтвительная и мнимая части соответственно (сигнал 40).

Все операции в устройстве выполняются над операндами, представленными IB дополнительном коде с фиксированной запятой.

Для исключения переполнения и по- Вьшения точности вычислений в устройстве используется условное масшта- |бирование, при котором на каждой ите- )рации производится оценка величины |у1одуля комплексных операндов на вы- оде арифметического блока. Если |сотя бы один операнд имеет модуль больше или равный 0,5, то на следую- ей итерации производится сдвиг вход- ittbix операндов на один разряд вправо. Если все операнды имеют модули меньше 0,25, то производится сдвиг всех Входных операндов на следующей итерации на один разряд влево. Если.все операнды имеют модули меньше 0,5, Но имеется хотя бы один операнд, модуль которого больше или равен 0,25, то выходные операнды поступают на выход арифметического блока без сдвига. При выполнении этих условий обеспечивается выполнение вычислений без переполнения разрядной сетки.

Блок управления сдвигом (фиг.7) .работает следующим образом.

На входы преобразователей 63 и 64 поступают старшие 5 разрядов веще- ственной и мнимой частей результатов вычислений. С помощью преобразова

5

0

телей 63 и 64, производится преобразование их в прямой код (для сокращения объема ПЗУ). С выхода преобразователей старшие разряды мантиссы действительной и мнимой частей, имеющие вес 0,5, заводятся непосредственно на входы f элемента ИЖ 66, выход которого поступает на вход старшего разряда регистра 67.

Остальные четьфе разряда преобразователей 63 и 64 заведены на адресные входы блока ПЗУ. В первый разряд блока 65 по адресам, которые соответствуют кодам мантисс действительной и мнимой частей числа, у которых модуль больше или равен 0,5,.записан код 1, а по остальным адресам записан код О. Первый разряд ПЗУ заведен на третий вход элемента ИЛИ. Во второй разряд блока ПЗУ по соответ- .ствующим адресам, при которых модуль больше или равен 0,25, но меньше 0,5, записан код 1. а по остальным 5 адресам записан код О.

В третий разряд блока ПЗУ по соот- . ветствующим адресам, при которых модуль комплексного числа, меньше 0,25, записан код 1, а по остальным адресам записан код О. С выхода ПЗУ второй и третий разряды заведены на вход регистра 67, причем регистр 67 построен так, что в случае установки в единичное состояние старшего разряда происходит установка в нулевое состояние всех младших цо отношению к нему разрядов.

Таким образом, во вре.мя текущей итерации в регистр по сигналу 41 могут быть установлены следующие коды: 1000 или 010, или 001. По окончании итерации по сигналу 42 содержимое регистра 67 переписьшается в регистр 68 и затем регистр 67 обнуляется по сигналу 43. Регистр 68 управляет сдвигателями 1 и 2.

0

5

0

5

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

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

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

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

888938 . выходы которых подключены к информационным .входам соответственно третьего и четвертого регистров, выходы

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

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

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

25 регистров подключены к вторым информационным входам соответственно пер- . ВОГО и третьего мультиплексоров, де- сятьй выход блока синхронизации подключен к управляющим входам первого и

Изобретение относится к области вычислительной техники и может быть использовано в системах цифровой обработки сигналов в реальном масштабе времени. Цель изобретения - расширение функциональных возможностей за счет выполнения фильтрации и разде- 1ления спектров. Поставленная цель достигается за счет того, что устройство содержит сдвигатели 1,2, умножители 3-6, регистры 7,8, мультиплексоры 9-12, регистры 13-16, сумматоры 17,18, выходные регистры 19, 20, блок управления сдвигом 23 и блок синхронизации 26. 1 з.п.ф-лы, 7 ил.

жителей, вход запуска устройства под-30 третьего мультиплексоров и первым

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

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

управляющим входам второго и четвертого мультиплексоров, вторые управляющие входы которых подключены к двенадцатому выходу блока синкрони- gg зации, первый, второй и третий входы задания режима которого подключены соответственно к входам задания режима с первого по третий устройства. 2. Устройство по п. 1, о т л ита ИЛИ, выход которого подключен к первому информационному входу первого регистра, выход которого подклюи вторым входами которого являются входы :соответственно первого и второго пре- gg образователей дополнительного кода я прямой, выходы которых подключены соответственно к первому и второму адресным входам узла постоянной памяти, выход которого подключен к тречающееся тем, что блок управ- ления сдвигом содержит элемент ИЛИ, два регистра, «узел постоянной памяти и два преобразователя дополнительного кода в прямой, выходы старших разряг дов которых подключены соответствен- но к первому и второму входам элемен- чен к информационному входу второго регистра, выход которого является вы ходом блока управления сдвигом, первым

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

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

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

мяти, выход которого подключен к тре91388893

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

фиг2

31

4 4Ъ 32

Л 54

55

S6 57

55 39 «/ - «3

п п п п п п п п п п п п I „ Ш1.г:

и

п п

Г1Л1

и

п

п

п

п.

и

фие

п

п

п

п.

и

3/

Л

зи ЗВ S6 37 38 3S

fO)

Сч1 Сч2

Счд СчЦ

Ум1

I

Ш

2

ВИНИПИ Заказ 2589

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

Сч5

Счб

/н2

ИмЗ

Z J I 4 5 I tf

г

Зап1 Запг ЗапЗ

S Фцв.6

У1

W

Фиг.7

Тираж 704

Подписное