Устройство для реализации быстрых преобразований в базисах дискретных ортогональных функций Советский патент 1984 года по МПК G06F17/14 

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

5060

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

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРЫХ ПРЕОБРАЗОВАНИЙ В БАЗИСАХ ДИСКРЕТНЫХ ОРТОГОНАПЬНЫХ ФУНКЦИЙ, содержащее арифметический блок, блоки оперативной и постоянной памяти, группу коммутаторов, регистр итераций, и счетчик операндов, причем информационные вьрсоды блоков оперативной и постоянной памяти подключены соответственно к входам операндов и коэффициентов арифметического блока, информационный выход которого подключен к информа- ционному входу блока оперативной памяти, адресный вход которого подключен к.выходам коммутаторов группы, параллельный выход регистра итераций подключен соответственно к управляюпа1м входам коммутаторов группы, информационные входы коммутаторов группы, кроме выхода второго разряда - к параллельному выходу счетчика операндов, выход второго разряда которого подключен к входу управления записью - считыванием блока оперативной памяти, о т.личающееся тем, что, с. целью расширения функциональньк возможностей устройства путем вычисления коэффициентов преобразований в базисе функций Фурье, Уолша, Хаара и комплексных прямоугольных функций, в него введены коммутатор, счетчик итераций, группа элементов И, регистр сдвига и формирователь управляющих сигналов, причем параллельный выход счетчика операндов, исключая выходы первого и второго разрядов, подключен к информационным входам коммутатора и регистра сдвига , выход коммутатора подключен к (Л тактовому входу регистра итераций с и счетному входу счетчика итераций, параллельный выход которого подклю§ чен поразрядно к первым входам соответствуюпсих элементов И группы и управляющему входу регистра сдвига, выходы элементов И группы подключены соответственно к разрядам управляющего входа коммутатору, паел раллельный выход регистра сдвига подключен, исключая старший разряд, Од к адресному; входу блока постоянной памяти, вторые входы элементов И группы объединены и являются первым входом задания режима устройства, причем формирователь управляющих сигналов содержит элемент ШТИ-НЕ, первый и второй элементы И-НЕ, первый, второй, третий и четвертый элементы И, генератор тактовых импульсов, счетчик и формирователь импульсов, причем первые входы первых элементов И, И-НЕ и инверсный вход вто

I

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

Известно устройство для вычисления обобщенных дискретных функций, содержащее блок формирования адреса, основной и дополнительный блоки памяти, арифметический блок, коммутатор, линию задераски, адресный счетчик и блок вычисления ядра обобщенных дискретных функций, причем блок формирования адреса содержит счетчик по модулю Р, триггер, счетчик по модулю БД блок умножения на модуль Р, схему зп ножения модулей, два сумматора, счетчик микрошагов , счетчик по модулю Я и блок вычисления модуля S СП.

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

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

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

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

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

Поставленная цель достигается тем, что в устройство, содержащее арифметический блок, блоки оперативной и постоянной памяти, группу коммутаторов, регистр итераций и счет3чик операндов, причем информационные выходы блоков оперативной и пос тоянной памяти подключены соответст венно к входам операндов и коэффици ентов арифметического блока, информационный выход которого подключен к информационному входу блока оперативной памяти, адресный вход кото рого подключен к выходам коммутатор группы, параллельный выход регистра итераций подключен соответственно к управляющим входам коммутаторов группы, информационные входы коммутаторов группы подключены, кроме выхода второго разряда, к параллельному выходу счетчика операндов, выход второго разряда которого подключен к входу управления записью-считыванием блока опера тивной памяти, введены коммутатор, счетчик итераций, группа-элементов И, регистр сдвига, формирователь управляющих сигналов, причем параллельный выход счетчика операндов, исключая вьтходы первого и второго разрядов, подключен к информационным входам коммутатора и регистра сдвига, выход коммутатора подключен к тактовому входу регистра итераций и счетному входу счетчика итераций, параллельный выход которого подключен поразрядно к первым входам соот ветствующих элементов И группы и уп равляющему входу регистра сдвига, выходы элементов И группы подключены соответственно к разрядам управляющего входа коммутатора, параллельный выход регистра сдвига подключен, исключая старший разряд, к адресному входу блока постоянной памяти, вторые входы элементов И группы-объединены и являются первым входом задания режима устройства, причем формирователь управляющих сигналов содержит элемент ИЛИ-Н первый и второй элементы И-НЕ, первый, второй, третий и четвертый элементы И, генератор тактовых импульсов, счетчик и формирователь импульсов, причем первые входы первых элементов И, И-НЕ и инверсный вход второго элемента И-НЕ объедине ны и подключены к старшему разряду параллельного выхода регистра сдвига, выход элемента ИЛИ-НЕ подключен к вторым входам первого и второго элемента И-НЕ и к инверсному входу четвертого элемента И, выход кото60рого подключен к управляющему входу формирователя импульсов, первый выход которого подключен к вторым входам второго и. третьего элементов И, первые входы которых подключены к выходам соответственно пер вого и второго элементов И-НЕ, выход генератора тактовых импульсов подключен к счетному входу счетчика, параллельный выход которого подключен к адресному входу формирователя импульсов, третьи входы первого элемента И-НЕ и третьего элемента И и. второй вход первого элемента И соединены с входом управления сдвигом регистра итераций и являются вторым входом задания режима устройства, прямой вход четвертого элемента И является третьим входом задания режима устройства, выход переполнения счетчика соединен со счетным входом счётчика операндов, второй и третий выходы формирователя импульсов и выходы первого, второго, третьего и четвертого элементов И подключены к входу синхронизации арифметического блока , вход элемента ИЛИ соединен с параллельным выходом, исключая старший разряд, регистра сдвига. На фиг. 1 изображена блок-схема предлагаемого устройства; на фиг. 2 - блок-схема формирователя управляющих сигналов. Устройство содержит блоки оперативной 1 и постоянной 2 памяти, арифметический блок 3, группу коммутаторов 4, регистр 5 итераций, счетчик 6 операндов, коммутатор 7, счетчик 8 итераций,группу элементов И 9, регистр 10 сдвига и формирователь 11 управляющих сигналов . Формирователь управляющих сигналов содержит элемент ИЛИ-НЕ 12, первый 13 и второй 14 элементы И-НЕ, первый 15, второй 16, третий 17 и четвертый 18 элементы И, генератор 19 тактовых импульсов, счетчик 20, формирователь 21 импульсов. Арифметический блок (АБ) 3 выполнен аналогично известному, предназначен для вьтолнения элементарного преобразования вида А + В «W и содержит четыре сумматора, четыре регистра хранения результата, два коммутатора, два входных регистра хранения действительной и мнимой частей операнды, регистр синуса и регистр косинуса для занесения зна чения кспоненциального коэффициен та W, .младшие разряды которых через вентили подключены к управляющим входам соответственно первого, четвертого и второго, третьего сумматоров, а управляюп(ие входы вентилей объединены. Счетчик 6 операндов, регистр 5 итераций,, группа коммутаторов А содержат соответственно У + 1 , и- 1 разрядов и п коммутаторов 3t1 (п , N - объем последовательности входных отсчетов), причем выход первого разряда счетчика 6 операндов подключен к вторым входам группы коммутаторов 4, выход (J + 1)-го разряда, начиная с третьего разряда - к первому вхо ду j-ro коммутатора,выход (i.+ 2)разряда - к третьему входу j-rp коммутатор, а выход третьего разр да счетчика 6 операндов подключен третьему входу первого коммутатора. Первый управляющий вход j-ro коммутатора подключен к выходу (j-1)-ro разряда регистра 5 итераций, второй управляющий вход к выходу j-ro разряда, причем первый управляющий вход первого комму татора и второй управляющий вход 10-го коммутатора подключены соответственно логическими потенциалами 1 и О. Счетчик 8 итераций и группа эле ментов И 9 содержат К Iog2n разрядов и элементов И соответственно. Устройство работает следующим о разом. При реализации быстрого преобра вания Фурье (БПФ) на входах XI, Х2 ХЗ устройства установлен код 110, последовательность входных отсчето расположена в блоке 1 оперативной памяти (ОП) в двоично-инверсном по ке, а счетчики операндов 6 и.итера ций 8 и регистр 5 итераций обнулены. Серия импульсов с второго выхо да блока синхронизации 11 nocTjmaет на счетный вход 6 операндов, на выходах первого, третье го и последующих разрядов которого формируется исходный двоичный код, а на выходе второго разряда - сигнал управления записью-считыванием блока 1 ОП. На управляющем входе коммутатора 7 задан нулевой код (элементы И 9 группы закрыты) и сигнал переполнения с выхода старшего разряда счетчика 6 операндов поступает на счетный вход счетчика 8. итераций и тактовый вход регистра 5 итераций. При этом на выходах разрядов счетчика 8 итера1ЩЙ формируется двоичный код номера итераций, а в регистр 5 итераций со стороны младшего разряда заносится едини- . ца со сдвигом ранее записанной информации в сторону старших разрядов. Сигналы с параллельного выхода регистра 5 итераций, поступая на управляющие входы коммутаторов 4 группы, преобразуют исходный двоичный код с параллельного, выхода счетчика 6 операндов в двоичный код адреса записи и чтения операндов для определенной итерации БПФ согласно графу преобразования с замещением и прореживанием по времени. Двоичный код с параллельного выхода счетчика 8 итераций поступает на управляющий вход регистра сдвига 10, который, в зависимости от номера итерации и начального кода адреса считывания .пары операн-дов, формирует коды адресов выборки из блока 2 постоянной памяти (ПП) экспоненциального коэффициента W. Коэффициент W (отдельно значение синуса и косинуса) поступает в АБ 3, выполняющий элементарное преобразование вида А + B-W, где А и В - считываемые из блока 1 ОП комплексные операнды, представляемые как значения их действительных и мнимых частей. Двоичный код с параллельного выхода регистра 10 сдвига также поступает на вход формирователя 11 уп-. равляющих сигналов, а именно на вход элемента ИЛИ-НЕ (фиг. 2), сигнал О на выходе которого задает режим работы АБ 3 Полное комплексное умножение. При этом на выходах первого 13 и второго 14 элементов И-НЕ ичетвертого 18 элемента И появляется сигнал 1, серия тактовых импульсов записи в регистры хранения АБ 3 проходит с первого выхода формирователя 21 импульсов на выходы второго 16 и третьего 17 элементов И и далее пос«тупает на тактовые входы записи (отдельно) регистров хранения про7

изведения Re В-cos W; Jm В- sin W и регистров хранения цезультатов произведения Re B«sin W, Jm Вcos W соответственно. С второго выхода формирователя 21 импульсов н тактовые входы регистров синуса и косинуса АБ 3 поступает серия импульсов, сдвигающая информацию в сторону младшего разряда, а сигнал 1 с выхода четвертого элемента И 18 разрешает прохождение через вентили информации с выходов младших разрядов регистров синуса и косинуса на первые входы управления сумматоров.

Сигнал с третьего выхода формирователя 21 импульсов управляет коммутаторами, причем в такте умножения к одному из информационных входов сумматоров через коммутаторы подключаются выходы входных ре гистров операндов и вычисляются произведения ReB-cos W, ReB« sin W, Jm В cos W и Jm В«sin W, в такте перекрестного сложения на этот же вход сумматоров поступают через коммутаторы результаты произведения с выходов соответствующих регистров хранения, выполняются операции вида Re В-cos W - Jm В-sin W Re(B«W) и Re В-sin W + Jm B-cos W Jm (), и результаты суммирования Re() и Jm() заносится в соответствующие регистры хранения по приходу отдельного импульса записи с первого выхода формирователя 21 импульсов, а в такте выполнения операции вида А + BW входы сумматоров подключены через коммутаторы к входным регистрам операндов, где к ЭТО14У моменту времени занесено значение отсчета А, и на информационных выходах сумматоров последовательно формируются для записи в блок 1 ОП действительные и мнимые части величины В A-B«W, а затем величины А A+B Сигнал с выхода старшего разряда регистра 10 сдвига,определяюпщй (в зависимости от логического состояния О или 1) знак заносимой в регистры синуса и косинуса АБ 3 информации, поступает на вход формирователя 11 управляющих сигналов и через первый элемент И подаеся на входы управления сумматоров. I

В момент формирования кода адреса значений экспоненциального ко5060

эффициента с показателями Он /2 на выходе элемента ИЛИ-Е1Е 12 появляется сигнал 1, который задает режим работы ЛВ 3 Умножение на 5 тривиальный множитель. При этом на выходе четвертого элемента И 18 появляется сигнал О, поступающий в АБ 3 и блокирующий прохождение информации через элементы И с выходов младших разрядов регистров синуса и косинуса на первые входы управления сумматоров. На первом выходе формирователя 21 импульсов вместо серии тактовых импульсов записи появляется одиночный импульс, который проходит на тактовые входы записи либо регистров хранения результатов произведения Re В-cos WJ, Jm W (на входе Х5 формирователя управляющих 11 сигналов потенциал О), либо регистров хранения результатов произведения Re В-sin WJ Jm Вsin fl (на входе Х5 - потенциал 1)i Значение операндов (отдельно 5 действительная и мнимая части)

переписывается из входных регистров через сумматоры в соответствующие регистры хранения по приходу данного имлульса записи и умножение на тривиальный множитель завершается.Далее осуществляются перекрестное сложение и операция вида А + BV/. которые анологичны режиму Полное комплексное умножение

L

при реализации преобразования в базисе комплексных прямоугольных функция (БП КПФ) на входах XI, Х2, ХЗ установлен код 010, входные отсчеты расйоложены в блоке 1 ОП в двоично-инверсном порядке, а формирование кодов адресов при записи и считывании операндов блока 1 ОП для всех итераций осуществляется аналогично БПФ. В базисе КПФ функции синуса и -косинуса принимают только целые значения -О, +1, -1, и режим работы АБ 3 Полное комп|Лексное умножение изменяется так, что в этом случае элементы И на выходах младших разрядов регистров синуса и косинуса АБ 3 заблокированы (на выходе четвертого элемента И 18 потенциал О), а умножение операнда В на величину (+1) или (-1) осуществляется путем пересылки значения действительной и мнимой частей операнда В через сумматоры в соответствующие регистры хранения (при этом на их тактовые входы

9

записи поступают через второй 16 и третий 17 элементы И одиночные и myльcы с /гервого выхода формирователя 21 импульсов) с учетом знака комплексной функции. Перекрестное сложение и операция вида A+BW при БП КПФ вьтолняются аналогично БПФ. Кроме того, режим работы АБ 3 Умножение на тривиальный множитель остается без изменений.

При реализации преобразования в базисе Уолш-образных функций (БАУ) на входах XI, Х2, ХЗ устанавливается код 000. Входная информация, предназначенная для обработки, переупорядочена по закону либо двоично-разрядной инверсии, либо по коду Грея, в зависимости от вида Уолщ-образной периодический функции. Разряды регистра 5 итераций устанавливаются в логическое состояние 1, причем в регистр со стороны старшего разряда по приходу тактового импульса осуществляется запись нулевой информации. Формирование кодов адресов считыванияи записи операндов блока 1 происхо.дит аналогично БПФ.с учетом того, что в данном случае изменяется на правлениё граф преобразования, т.е. последняя итерация БПФ аналогична первой итерации БПУ, и т.д.

АБ 3 работает только в режиме Умножение на тривиальный множитель

10

115060

причем импульс записи с первого выхода формирователя 21 импульсов проходит через второй элемент И 16 только на тактозый вход записи ре5 гистров хранения результатов произведения Re Bcos W и Jm Bcos W, затем осуществляется перекрестное сложение Re W - Jm В -s-in W Re B; Re В-sin W + Jm В-cos W

10 Jm B-cos W 1 sin W 0 и операрация вида A +. Б.

При реализации преобразования в базисе Хаар-образных функций (БПФ) на входах XI, Х2 и ХЗ. устанавливаот15 ся код 001. Расположение входных данных в блоке 1 СП и работа АБ 3 в режиме Умножение на тривиальный множитель, аналогичны БПУ. Группа элементов И 9 пропускает двоичный

20 код с выходов разрядов счетчика 8 . итераций на управляющий вход коммутатора 7, выход которого на j-й (J О, ..., п-1) итерации подключается к выходу (n-j)-ro разряда

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

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

фи&1

Фиг-г