Устройство для реализации быстрых преобразований

 

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

СОЮЗ GOBETCHHX

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (gg g G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ г Л.

+ue 7

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4157149/24-24 (22) 05, 12,86 (46) 15.08.88. Бюл. У 30 (71) Специальное конструкторско-технологическое бюро с опытным производством при Белорусском государственном университете им. В.И.Ленина (72) А.Н.Карташевич и М.С.Курлянд (53) 681.32(088,8) (56) Авторское. свидетельство СССР

Р 752347, кл. G 06 F 15/332, 1978.

Авторское свидетельство СССР

В 1292005, кл. G 06 F 15/332, 1985. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРЬИ ПРЕОБРАЗОВАНИЙ (57) Изобретение относится к области вычислительной техники и может быть

„„SU„„1416981 А1 использовано при решении задач фильтрации и идентификации сигналов. Цель изобретения — расширение функциональных возможностей путем вычисления быстрых преобразований в базисах дискретных ортогональных функций по смешанному основанию. Поставленная цель достигается за счет того,. что в состав устройства входят блок памяти 1, блок постоянной памяти 2, арифметический блок 3, блок коммутаторов

4, регистр сдвига 5, счетный блок 6, счетчик итераций 7, коммутатор 8, блок элементов 9, генератор тактовых импульсов 10, адресной счетчик 11, сумматор 12, регистр 13, умножитель

14 и коммутатор 15. 2 ил.

1416981

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

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

На фиг.1 изображена структурная схема устройства; на фиг.2 — схема счетного блока.

Устройство (фиг.1) содержит блок 1 15 (оперативной) памяти, блок 2 постоянной памяти, . арифметический блок 3, блок 4 коммутаторов, регистр 5 сдвига, счетный блок 6, счетчик 7 итераций, первый коммутатор 8, блок 9 элементов П

И, генератор 10 тактовых импульсов, адресный счетчик 11, сумматор 12, регистр 13 (хранения), умножитель 14 (комплексных чисел) и второй коммутатор 15. На фиг.1 обозначены также входы Х1-Х4 устройства и выход У1 устройства.

Блок 6 (фиг.2) представляет собой последовательную цепочку из и (и— в общем случае число основания; в случае, когда основание одно для всех итераций, и = log N) пересчетных узлов.

Пересчетный узел содержит k-разрядный двоичный счетчик 16 (1 = 1оя гцд,,35 г „„с — максимальное из используемых в устройстве оснований), двоичный код на выходе которого выражает r-ичную разрядную цифру в двоичном коде, и узел сравнения на группе из k эле- 40 ментов исключающее ИЛИ 17 и k-входовом элементе ИЛИ 18.

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

При реализации быстрого преобразо-45 вания в базисе дискретных экспоненциальных функций (ДЭФ) на входах Х1, Х2 Х4 устройства установлен код 101.

На вход Х3 поданы двоичные коды г„, ° °

Исходный массив длительностью И занесен в инверсном порядке. В исходном состоянии блок 6, счетчик 7 итераций, адресный счетчик 11, регистр

5 сдвига и регистр 13 хранения обну- 5 лены.

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

На управляющем входе. коммутатора

8 задан. нулевой код (элементы И блока 9 закрыты) и к счетному входу счетчика итераций 7 и тактовому входу регистра сдвига 5 подключен выход старшего r-ичного разряда блока 6 °

При этом на выходах двоичных разрядов счетчика 7 . итераций формируется двоичный код номера итерации, а в ре" гистр 5 сдвига со стороны младшего разряда заносится "1" со сдвигом ранее записанной информации в сторону старших разрядов.

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

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

12 и регистра 13 хранения кода.-адреса множителей, извлекаемых из блока

2 постоянной памяти.

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

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

В режиме записи арифметический блок 3 производит элементарные преобразования над полученными ранее произведениями и заносит в блок 1 оперативной памяти на место ранее извлеченных операндов новые операнды согласно алгоритму замещения.

1416981

Экспоненциальные,множители хранятся в блоке 2 постоянной .памяти, отдельно синусы и косинусы, причем область, в которой хранятся множители для выбранных r1 rz r„ опреде5 ляется управляющим входом блока 2 постоянной памяти, комплексные операнды хранятся в блоке 1 оперативной памяти отдельно как значения их действительной и мнимой частей.

Регистр 13 хранения обнуляется переходом сигнала записи-считывания из низкого логического уровня в высокий. 15

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

После окончания первой итерации ( сигналом старшего разряда блока 6 в регистре 5 сдвига происходит сдвиг информации в сторону старших разрядов с занесением "1" в младший разряд, содержимое счетчика 7 итераций увеличивается на единицу, второй коммутатор 15 меняет двоичные коды оснований

35 для каждого разряда блока 6 и устройство переходит к выполнению следующей итерации преобразования.

При реализации быстрого преобразования в базисе функций ВиленкинаПонтрягина (ВПФ) на входах Xi, Х2, Х4 устройства устанавливается код

000.

Исходный массив длительностью И занесен при этом в блок 1 оперативной памяти в прямом порядке.

Таким образом, при выполнении преобразования в базисе ВПФ работа устройства отличается от работы при выполнении преобразования в базисе ДЭФ только порядком расположения исходной информации в блоке 1 оперативной памяти, отсутствием операции умножения на экспоненциальные множители в режиме считывания и работой регистра 5 сдвига.

В данном случае в исходном состоянии разряды регистра 5 сдвига уста-.. навливаются в состояние "i" причем в старший разряд регистра по приходу тактового импульса на тактовый вход осуществляется запись нулевой информации со сдвигом ранее записанной информации в сторону младших разрядов.

При реализации быстрых преобразований в базисе функций усеченного преобразования Виленкина-Понтрягина (УВПФ) на входах Х1, Х2, Х4 устройства установлен код 010. Исходный массив длительностью Ы занесен в блок

1 оперативной памяти в прямом порядке.

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

Двоичный код с выхода счетчика 7 итераций через блок 9 элементов И (на вход Х2 подана "1") поступает на управляющий вход первого коммутатора 8.

В результате на первой итерации к тактовым входам регистра 5 сдвига и счетчика 7 итераций подключен выход старшего разряда блока 6. На последующих итерациях номер разряда блока

6, выход переноса которого коммутатором 8 подключается к тактовым входам регистра 5 сдвига и счетчика 7 итераций, уменьшается на единицу от итерации к итерации.

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

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

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

Редактор А.Orap Техред Л.Олийнык Корректор С.Черни

Заказ 4065/46 Тираж 704 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

Входу счетчИка итераций и тактовому

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

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