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

Ob

со 00

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

fpue.i

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

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

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

Устройство (фиг.1) содержит блок 1 15 гистр 5 сдвига со стороны младшего

разряда заносится 1 со сдвигом р нее записанной информации в сторону старших разрядов.

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

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

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

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

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

1:

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

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

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

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

5 гистр 5 сдвига со стороны младшего

0 5

0

5 0

5

0

5

разряда заносится 1 со сдвигом ранее записанной информации в сторону старших разрядов.

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

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

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

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

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

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

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

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

постоянной памяти, после чего в арифметическом блоке 3 производятся элементарные, преобразования и в блок 1 25 оперативной памяти заносятся очередные Ti новых операндов на место ранее извлеченных.

После окончания первой итерации сигналом старшего разряда блока 6 в регистре 5 сдвига происходит сдв.иг информации в сторону старших разрядов с занесением 1 в младший разряд, содержимое счетчика 7 итераций увеличивается на единицу, второй коммутаПри выполнении преобразования в базисе УВПФ работа устройства отличается от работы устройства при выполнении преобразования в базисе ВПФ тем, что количество выполняемых элементарных преобразований уменьшается с увеличением номера итерации. Это осуществляется следующим образом. Двоичный код с выхода счетчика 7 ите раций через блок 9 элементов И (на вход Х2 подана 1) поступает на уп равляювщй вход первого коммутатора 8 В результате на первой итерации к тактовым входам регистра 5 сдвига и счетчика 7 итераций подключен выход старшего разряда блока 6. На последующих итерациях номер разряда блока 6, выход переноса которого коммутатором 8 подключается к тактовым входам регистра 5 сдвига и счетчика 7

30

тор 15 меняет двоичные коды оснований итераций, уменьшается на единицу от

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

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

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

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

В данном случае в исходном состоянии разряды регистра 5 сдвига уста-..

10

15

25

169314

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

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

При выполнении преобразования в базисе УВПФ работа устройства отличается от работы устройства при выполнении преобразования в базисе ВПФ тем, что количество выполняемых элементарных преобразований уменьшается с увеличением номера итерации. Это осуществляется следующим образом. Двоичный код с выхода счетчика 7 итераций через блок 9 элементов И (на вход Х2 подана 1) поступает на уп- равляювщй вход первого коммутатора 8. В результате на первой итерации к тактовым входам регистра 5 сдвига и счетчика 7 итераций подключен выход старшего разряда блока 6. На последующих итерациях номер разряда блока 6, выход переноса которого коммутатором 8 подключается к тактовым входам регистра 5 сдвига и счетчика 7

20

30

итерации к итерации.

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

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

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

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

Фиг. г

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