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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

3 511 С 06 F 15/332

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3587609/! 8-24 (22) 04.05.83 (46) 23.09.84. Бюл. ¹- 35. (72) А.Н. Карташевич, Г.Л.. Кухарев и А.И. Ходосевич (71) Специальное конструкторско-технологическое бюро с опытным производством при Белорусском государственном университете им. В.И. Ленина (53) 681. 32 (088. 8) (56) 1. Авторское свидетельство СССР № 752347, кл. С 06 F 15/31, 1978.

2. Авторское свидетельство СССР № 809198, кл. G 06 F 15/332, 1979 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

БЫСТРЫХ ПРЕОБРАЗОВАНИЙ В БАЗИСАХ

ДИСКРЕТНЫХ ОРТОГОНАПЬНЫХ ФУНКЦИЙ, содержащее арифметический блок, блоки оперативной и постоянной памяти, группу коммутаторов, регистр итераций.и счетчик операндов, причем информационные выходы блоков оперативной и постоянной памяти подключены соответственно к входам операндов и коэффициентов арифметического блока, информационный выход которого подключен к информационному входу блока оперативной памяти, адресный вход которого подключен к.выходам коммутаторов группы, параллельный выход регистра итераций подключен соответственно к управляющим входам коммутаторов группы, информационные входы коммутаторов группы, кроме выхода второго разряда — к параллельному выходу счетчика операндов, выход второго разряда которого подключен к

„„SU„„1115060 А входу управления записью — считыванием блока оперативной памяти, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем вычисления коэффициентов преобразований в базисе функций Фурье, Уолша, Хаара и комплексных прямоугольных функций, в него введены коммутатор, счетчик итераций, группа элементов

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

O входам коммутатора и регистра сдви- Е

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

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

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

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

Известно устройство для вычисления обобщенных дискретных функций, содержащее блок формирования адреса, основной и дополнительный блоки .памяти, арифметический блок, коммутатор, линию задержки, адресный счетчик и блок вычисления ядра обоб.щенных дискретных функций, причем блок формирования адреса содержит счетчик по модулю Р, триггер, счетчик по модулю S áëîê умножения на модуль Р, схему умножения модулей, два сумматора, счетчик микрошагов, счетчик по модулю Ц, и блок вычисления модуля S С11. 20

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

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

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

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

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

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

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

И, регистр сдвига, формирователь управляющих сигналов, причем параллельный выход счетчика операндов, исключая выходы первого и второго разрядов, подключен к информацион— ным входам коммутатора и регистра сдвига, выход коммутатора подключен к тактовому входу регистра итераций и счетному входу счетчика итераций, 30 параллельный выход которого подключен поразрядно к первым входам соответствующих элементов И группы и уп— равляющему входу регистра сдвига, выходы элементов И группы подклю- 35 чены соответственно к разрядам управляющего входа коммутатора, параллельный выход регистра сдвига подключен, исключая старший разряд, к адресному входу блока постоянной 40 памяти, вторые входы элементов И группы. объединены и являются первым входом задания режима устройства, причем формирователь управляющих сигналов содержит элемент ИЛИ-НЕ,4g первый и второй элементы И-НЕ, первый, второй, третий и четвертый элементы И, генератор тактовых импульсов, счетчик и формирователь импульсов, причем первые входы первых элементов И, И-НЕ и инверсный вход второго элемента И-НЕ объединены и подключены к старшему разряду параллельного выхода регистра сдвига, выход элемента ИЛИ-НЕ подключен к вторым входам первого и второго элемента И-HE и к инверсному вхсду четвертого элемента И, выход которого подключен к управляющему входу формирователя импульсов, первый выход которого подключен к вторым входам второго и третьего элементов И, первые входы которых подключены к выходам соответственно пер вого и второго элементов И-НЕ, выход генератора тактовых импульсов подключен к счетному входу счетчика, параллельный выход которого подключен к адресному входу формироваt теля импульсов, третьи входы первого элемента И-НЕ и третьего элемента И и. второй вход первого элемента И соединены с входом управления сдвигом регистра итераций и являются вторым входом задания режима устройства, прямой вход четвертого элемента И является третьим входом задания режима устройства, выход переполнения счетчика соединен со счетным входом счетчика операндов, второй и третий выходы формирователя импульсов и выходы первого, второго, третьего и четвертого элементов И подключены к входу синхронизации арифметического блока, вход элемента ИЛИ соединен с параллельным выходом, исключая старший разряд, регистра сдвига.

На фиг. 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 и содержит четыре сумматора, четыре ре. гистра хранения результата, два коммутатора, два входных регистра хранения действительной и мнимой частей операнды, регистр синуса и

1II5060

10 о 20 (ПП) экспоненциального коэффициента W. Коэффициент W (отдельно значение синуса и косинуса) поступает

35 в АБ 3, выполняюн1ий элементарное преобразование вида А + В W, где

А и  — считываемые из блока 1 ОП комплексные операнды, представляемые как значения их действительных

40 и мнимых частей.

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

45 на вход элемента ИЛИ-НЕ (фиг. 2), сигнал "0" на выходе которого зада— ет режим работы АБ 3 "Полное комплексное умножение". При этом на выходах первого 13 и второго 14 эле50 ментов И вЂ” НЕ и четвертого 18 элемента И появляется сигнал "1", серия тактовых импульсов записи в регистры хранения АБ 3 проходит с первого выхода формирователя 21 импульсов на выходы второго 16 и третьего 17 элементов И и далее пос тупает на тактовые входы записи (отдельно) регистров хранения проорегистр косинуса для занесения значения кспоненциального коэффициента W, младшие разряды которых че.рез вентили подключены к управляющим входам соответственно первого, ь четвертого и второго, третьего сумматоров, а управляющие входы вентилей объединены.

Счетчик 6 операндов, регистр 5 итераций,. группа коммутаторов 4 содержат соответственно n + 1, 1 разрядов и в коммутаторов

Зх1(п = Iog < N, N — объем последовательности входных отсчетов), причем выход первого разряда счетчика 6 операндов подключен к вторым входам группы коммутаторов 4, выход (j + 1)-ro разряда, начиная с третьего разряда — к первому входу j — ro коммутатора, выход (1 + 2)-г разряда — к третьему входу j- ro коммутатор ., а выход третьего разря да счетчика 6 операндов подключен к третьему входу первого коммутатора. Первый управляющий вход j-го коммутатора подключен к выходу (j — 1)-ro разряда регистра 5 итераций, второй управляющий вход— к выходу j-го разряда, причем первый управляющий вход первого коммутатора и второй управляющий вход

И-го коммутатора подключены соответственно логическими потенциала11 1 tt lt tt

Счетчик 8 итераций и группа элементов И 9 содержат К = 1: og 2 п ра зрядов и элементов И с оот в етс т венно .

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

При реализации быстрого пр е обра з вания Фурье (БПФ) на вхоцах Х 1, Х2, ХЗ устройства установлен код 1 1 0, последовательность входных отсчетов расположена в блоке 1 оперативной памяти (ОП) в двоично-инверсном пор ке, а счетчики операндов 6 и . итераций 8 и регистр 5 итераций о бнул ены . Серия импульсов с второго выхода блока синхронизации 1 1 поступает на счетный вход счетчика 6 операндов, на выходах первого, третьег о и последующих разрядов которого формируется исходный двоичный код, а на выходе второг о . р а зр яда — сигнал управления записью-считыванием блока 1 ОП . На управляющем входе коммутатора 7 задан нулевой к од

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

Сигналы с параллельного выхода регистра 5 итераций, поступая на управляющие входы коммутаторов 4 группы, преобразуют исходный двоичный код с параллельного выхода счетчика 6 операндов в двоичный код адреса записи и чтения операн— дов для определенной итерации БПФ согласно графу преобразования с замещением и прореживанием по времени. Двоичный код с параллельного выхода счетчика 8 итераций поступает на управляющий вход регистра сдвига 10, который, в зависимости от номера итерации и начального кода адреса считывания пары операн-. дов, формирует коды адресов выборки из блока 2 постоянной памяти

1115060 изведения Re В cos W; Jm В. sin W и регистров хранения результатов произведения Re В ° з п W; Jm Р> °

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

= Re(B W) и Re В sin W + Jm В cos W -.

= Jm (BiW), и результаты суммирования Re(B W) и Jm(B W) заносится в соответствующие регистры хранения по приходу отдельного импульса записи с первого выхода формирователя 21 импульсов, а в такте выполнения операции вида А + В W входы сумматоров подключены через коммутаторы к входным регистрам операндов, где к этому моменту времени занесено значение отсчета А, и на информационных выходах сумматоров последовательно формируются для записи в блок 1 ОП действительные и мнимые части величины В

= А-В W, а затем величины А = А+В W

Сигнал с выхода старшего разряда регистра 10 сдвига, определяющий (в зависимости от логического состояния "О" или "1") знак заносимой в регистры синуса и косинуса

АБ 3 информации, поступает на вход формирователя 11 управляющих сигналов и через первый элемент И подается на входы управления сумматоров.

В момент формирования кода адре.са значений экспоненциального коэффициента с показателями 0 и Ж /2 на выходе элемента ИЛИ-HE 12 появляется сигнал "1, который задает режим работы AB 3 "Умножение на

5 тривиальный множитепь". При этом на выходе четвертого элемента И 18 появляется сигнал 0", поступающий в АБ 3 и блокирующий прохождение информации через элементы И с выходов младших разрядов регистров синуса и косинуса на первые входы управления сумматоров. На первом выходе формирователя 21 импульсов вместо серии тактовых импульсов

15 записи появляется одиночный импульс, который проходит на тактовые входы записи либо регистров хранения результатов произведения Re В cos

Jm В cos W (на входе Х5 формировате20 ля управляющих 11 сигналов потенциал "О"), либо регистров хранения результатов произведения Re В ° sin W;

Jm В sin W (на входе X5 — потенциал

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

При реализации преобразования в базисе комплексных прямоугольных функция (БП КПФ) на входах Х1, Х2, ХЗ установлен код 010, входные отсчеты расположены в блоке 1 ОП в двоично-инверсном порядке, а формирование кодов адресов при записи и считывании операндов блока l ОП

40 для всех итераций осуществляется аналогично БПФ. В базисе КПФ функс ции синуса и косинуса принимают только целые значения -О, +1, -1, и режим работы АБ 3 "Полное комп45,лексное умножение" изменяется так, что в этом случае элементы И на

50 выходах младших разрядов регистров синуса и косинуса АБ 3 заблокированы (на выходе четвертого элемента И 18 потенциал "0"), а умножение операнда В на величину (+1) или (-1) осуществляется путем пересыл5S ки значения действительной и мнимой частей операнда В через сумматоры в соответствующие регистры хранения (при этом на их тактовые входы

115060

9 1 записи поступают через второй 16 и третий 17 элементы И одиночные импульсы с,первого выхода формирователя 21 импульсов) с учетам знака комплексной функции. Перекрестное сложение и операция вида A+BeW при БП КПФ выполняются аналогично

БПФ. Кроме того, режим работы АБ 3

"Умножение на тривиальный множитель" остается без изменений.

При реализации преобразования в базисе Уолш-образных функций (БАУ) на входах Х1, Х2, Х3 устанавливается код 000. Входная информация, предназначенная для обработки, переупорядочена по закону либо двоично-разрядной инверсии, либо по коду Грея, в зависимости от вида

Уолш-образной периодический функции. Разряды регистра 5 итераций устанавливаются в логическое состояние "1", причем в регистр со стороны старшего разряда по приходу тактового импульса осуществляется запись нулевой информации. Формирование кодов адресов считывания и записи операндов блока 1 происхо.дит аналогично БПФ .с учетом того, что в данном случае изменяется направление. граф преобразования, т.е. последняя итерация БПФ аналогична первой итерации БПУ, и т.д.

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

"Умножение на тривиальный множитель", причем импульс записи с первого выхода формирователя 21 импульсов проходит через второй элемент И 16 только на тактовый вход записи регистров хранения результатов произведения Re Buncos W u Jm В cos W, затем осуществляется перекрестное сложение Re В cos W — Jm В sin W =

Re В; Re В sin W + Jm В cos W =

10 .= Jm В.cos W = 1, sin W = 0 и операрация вида А + В.

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

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

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

Фурье, Хаара, Уолша и комплексных прямоугольных функций.! 115060

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

Редактор А. Шишкина Техред М. Кузьма КоРРектоР, В. Гирняк

Заказ 6772/36 Тираж 698 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4