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

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

Целью изобретения является повыше- ние точности вычислений.

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

Устройство содержит входной регистр 1, мультиплексор 2, арифметический блок 3, блок 4 постоянной памяти коэффициентов, преобразователи 5 и 6 модифицированного дополнительного кода в прямой, блок 7 постоянной памяти, элемент ИЛИ 8, регистры 9 и 10, реверсивный счетчик 11, регистр 12, второй мультиплексор 13, блок 14 синхронизации.

На фиг. 2 представлен вариант аппаратной реализации преобразователя 5 на пять разрядов.

Преобразователь кода 5 служит для преобразования К старших разрядов мантиссы числа. Преобразование выполняется по следуюш,ему алгоритму

А|5, АН, Ai3 - А, Ai5,Ai4,A:3-А,; А|5, AM, Ai3-А,- при Ai5,Ai4,A:3-А,, где 3НА - знак числа ( соответствует отрицательным числам); А|5,...,А,- - разряды мантиссы числа (Ais- старший разряд).

Блок содержит элемент НЕ 15, пять элементов НЕ 16 и пять элементов 2И-ИЛИ- - НЕ 17.

Блок синхронизации (фиг. 3) содержит генератор 18, распределитель 19 импульсов, элемент ИЛИ 20, элемент И 21, ждущий мультивибратор 22, сдвиговый регистр 23, элемент И 24, элемент ИЛИ 25, элементы И 26-30, RS-триггер 31, счетчик 32 и элемент ИЛИ 33.

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

5

5

0

0

е

0

5

0

5

0

ся сдвиг всех входных операндов на один разряд влево. Если все операнды имеют модули меньше 0,5, но имеется хотя бы один операнд, модуль которого больше или равен 0,25, то входные операнды поступают на вход арифметического блока без сдвига и выходные операнды выдаются из блока без сдвига. При выполнении этих условий обеспечивается работа арифметического блока без потери информации.

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

Как известно, модуль комплексного числа определяется выражением:

|А,-| V(ReA;)2+(ImA/)2, где А, - комплексное число; ReA, - действительная часть.числа А,; ImA, - мнимая часть числа А,.

Из анализа этого выражения видно.

При значении |ReA;| 0,5 модуль комплексного, числа 0,5 независимо от значения ImA,.

При значении |1тА,,5 модуль комплексного .числа 0,5 независимо от значения ReA,.

При других значениях ReA,- и |1тА,| выполнение неравенства |А,,5 зависит как от значений реальной, так и мномой частей комплексного числа. С целью экономии оборудования оценка величины модуля комплексного числа производится приближенно по анализу К старших разрядов действительной и мнимой частей числа. Рассмотрим работы устройства при .

В исходном состоянии все регистры установлены в ноль. В счетчик 11 записывается код, равный (log2N-1), где N - размер обрабатываемого массива. Значение log2N численно равно числу итераций БПФ. На управляющий вход мультиплексора 2 входных операндов на первой итерации подан потенциал, соответствующий передаче операндов без сдвига. Операнды, участвующие в вычислениях в соответствующей последовательности, необходимой для алгоритма БПФ, через регистр операндов 1 подаются на вход мультиплексора 2 и без сдвига поступают на первый вход арифметического блока 3. На второй вход блока поступают весовые коэффициенты из блока 4. С арифметического блока 3 операнды подаются на вход мультиплексора 13, который настраивается на первой итерации со сдвигом на 1 разряд вправо. На выходе мультиплексора 13 производится оценка величины модуля операндов, вычисленных на текущей итерации. Вначале с помощью преобразователей 5 и 6 производится преобразование их в прямой код, что позволяет сократить объем блока ПЗУ. Для этого на управляющие входы преобразователей 5 и 6 подключены знаковые разряды соотетственно действительной и мнимой частей операнда. При единичном значении знакового разряда производится инвертирование кода мантиссы операндов, поданных на вход преобразователя 5 или 6. При нулевом значении знакового разряда производится передача кода мантиссы без инвертирования. С выхода преобразователей 5 и 6 кода старшие разряды мантиссы действительной и мни мой частей, имеющие вес 0,5, заводятся непосредственно на входы элемента 8, выход которого поступает на вход старщего разряда регистра 9.

Остальные четыре разряда преобразователей кодов 5 и 6 заведены на адресные входы блока 7. В первый разряд блока 7 по адресам, которые соответствуют кодам мантисс действительной и мнимой части числа, у которых модуль больше или равен 0,5, записан код 1, а по остальным адресам записан код 0.

Во второй разряд блока 7 по адресам, которые соответствуют кодам мантисс действительной и мнимой частей числа, у которых модуль болыле или равен 0,25, записан код 1, а по остальным адресам - 0.

Таким образом за время текущей итерации в регистре 9 могут быть установлены следующие коды: 11 или 01, или 00. По окончании первой итерации содержимое регистра 9 переписывается в регистр 10, причем второй разряд регистра 9 переписывается с инверсией. Затем регистр 9 обнуляется. Таким образом, на время текущей итерации в регистре в регистре 10 могут быть установлены следующие коды: 10 или 00, или 01. При наличии в регистре 10 кода 10 входные операнды поступают через мультиплексор 2 на арифметическое устройство без сдвига, выходные операнды сдвигаются на один разряд вправо, и происходит вычитание единицы из счетчика 11. При наличии в регистре 10 кода 01 происходит сдвиг входной последовательности на один разряд влево, выходные операнды поступают на выход устройства без сдвига, и на счетчике 11 происходит прибавление единицы. При наличии в регистре 10 кода 00 входная и выходная последовательности передаются без. сдвига, и состояние счетчика 11 не изменяется.

Далее этот процесс повторяется на каждой итерации. На последней итерации содержимое счетчика 11 переписывается в регистр 12. После завершения вычислений по алгоритму БПФ в регистре 12 находится код, значение которого соответствует масштабу вычисленного спектра. Этот код передается в устройство последующей обработки, где он будет учитываться при даль- нейщих вычислениях.

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

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

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

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

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

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

бык г ип

бй/Х М20

бй/хУ си1,ш

СШ... CU16

10 12 14 16 2 f 6

Счит.

Запись

дык.6

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

I

4)ui.i

10 12 Jif 16

3 I V

ZTT

3

6oft/uc/renL/ff

Фиг. 5

Редактор С. Патрушева Заказ 3804/45

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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

Техред И. ВересКорректор Г. Решетник

Тираж 672Подписное

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов в реальном масштабе времени. Цель изобретения повышение точности вычислений. Поставленная цель достигается за счет того, что в состав устройства для вычисления коэффициентов Фурье входит входной регистр 1, мультиплексор 2, арифметический блок 3, блок 4 постоянной памяти коэффициентов, преобразователи 5, 6 модифицированного дополнительного кода в прямой блок 7 постоянной памяти, элемент ИЛИ 8, регистры 9, 10, реверсивный счетчик 11, регистр 12, мультиплексор 13 и блок синхронизации 14. Устройство работет с числами, представленными с фиксированной запятой. Для масштабирования вычислений используется алгоритм условного масштабирования, причем сдвиг операндов в сторону младших разрядов производится после выполнения вычислений. 6 ил. S (Л 00 со 05 О ьо со