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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК А 332 ИЙ САНИЕ ИЗОБРЕТЕНИ ВТОРСН В ЕТЕЛЬСТВ о уп ло вао тцель можн во слера раз ГОСУДАРСТВЕННЫЙ КОМИТЕТ СПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(71) Специальное конструкторско-технологическое бюро с опытным производ ством при Белорусском государственно университете им. В.И. Ленина(56) 1. Авторское свидетельство СССР У 752347, кл. С 06 Р 15/31, 1978.2. Авторское свидетельство СССР У 809198, кл. С 06 Р 15/332, 1979 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИБЫСТРЫХ ПРЕОБРАЗОВАНИЙ В БАЗИСАХДИСКРЕТНЫХ ОРТОГОНАПЬНЫХ ФУНКЦИЙ,содержащее арифметический блок,блоки оперативной и постоянной памяти, группу коммутаторов, регистритераций.и счетчик операндов, причем информационные выходы блоковоперативной и постоянной памяти подключены соответственно к входамоперандов и коэффициентов арифметического блока, информационный выход которого подключен к информационному входу блока оперативнойпамяти, адресный вход которого подключен к.выходам коммутаторов группы, параллельный выход регистра итераций подключен соответственно куправляющим входам коммутаторовгруппы, информационные входы коммутаторов группы, кроме выхода второго разряда - к параллельному выходу счетчика операндов, выход второго разряда которого подключен к,ЯО 11150 вх ду равления записью - счить нием б ка оперативной памяти, л и ч а ю щ е е с я тем, что, сю расширения функциональныхостей устройства путем вычи ния коэффициентов преобразований в базисе функций Фурье, Уолша, Хаа и комплексных прямоугольных функций, в него введены коммутатор, счетчик итераций, группа элементов И, регистр сдвига и формирователь управляющих сигналов, причем параллельный выход счетчика операндов, исключая выходы первого и второгорядов, подключен к информационньпц входам коммутатора и регистра сдвига, выход коммутатора подключен ктактовому входу регистра итераций и счетному входу счетчика итераций параллельный выход которого подключен поразрядно к первым входам соответствуюи 1 их элементов И группы и управляющему входу регистра сдвига, выходы элементов И группы подключены соответственно к разрядамуправляющего входа коммутатора, параллельный выход регистра сдвига.подключен, исключая старший разряд,к адресному входу блока постояннойпамяти, вторые входы элементов Игруппы объединены и являются первымвходом задания режима устройства,причем формирователь управляющихсигналов содержит элемент ИЛИ-НЕ,первый и второй элементы И-НЕ, первый, второй, третий и четвертый элементы И, генератор тактовых импульсов, счетчик и формирователь импульсов, причем первыевходы первых элементов И, И-НЕ и инверсный вход вто 11 рого элемента И-НЕ подключены к старшему разряду параллельного выхода регистра сдвига, выход элемента ИЛИНЕ подключен к вторым входам первого и второго элементов И-НЕ и к инверсному входу четвертого элемента И, выход которого подключен к управляющему входу формирователя импульсов, первый выход которого под ключен к вторым входам второго и третьего элементов И, первые входы которых подключены к выходам соответственно первого и второго элементов И-НЕ, выход генератора тактовых импульсов подключен к счетному входу счетчика, параллельный выход которого подключенк адресному входу формирователя импуль" сов, третьи входы первого элемента 15060И-НЕ и третьего элемента И и второй вход первого элемента И соединены с входом управления сдвигомрегистра итераций и являются вторымвходом задания режима устройства,прямой вход четвертого элемента Иявляется третьим входом заданиярежима устройства, выход переполнения счетчика соединен со счетнымвходом счетчика операндов, второйи третий выходы формирователя импульсов и выходы первого, второго, третьего и четвертого элементов И подключены к входу синхронизации арифметического блока, вход элементаИЛИ соединен с параллельным выхо.дом, исключая старший разряд, регистра сдвига, 1Изобретение относится к цифро-вой вычислительной технике и может быть использовано при решении задач фильтрации и идентификации сигналов. 5Известно устройство для вычисления обобщенных дискретных функций, содержащее блок формирования адреса, основной и дополнительный блоки памяти, арифметический блок, коммутатор, линию задержки, адресный счетчик и блок вычисления ядра обоб.щенных дискретных функций, причем блок формирования адреса содержит счетчик по модулю Р, триггер, счет чик по модулю 8 блок умножения на модуль Р, схему умножения модулей, два сумматора, счетчик микро- шагов, счетчик по модулю Ц, и блок вычисления модуля Я 11. 20Недостатками этого устройства являются большие аппаратурные затраты и ограниченные функциональные возможности, состоящие в вычислении только коэффициентов преобразования Фурье-Уолша и коэффициентов дискретного преобразования Фурье.Наиболее близким по технической сущности к предлагаемому является устройство для реализации быстрого 30 преобразования Фурье, содержащее оперативную память, арифметический 2блок, постоянную память и блок управления, первый и второй выходы которого подключены к адресным входам, соответственно, блоков оперативной и постоянной памяти, выходы которых подключены соответственно к входам операндов и коэффициентов арифметического блока, третий выход блока управления подключен к входу синхронизации арифметического блока, выход которого подключен к информационному входу блока оперативной памяти, причем блок управления содержит счетчик операндов, регистр хранения и схему инверсии кода 23.Недостатком известного устройства являются ограниченные функциональные возможности, состоящие в вычислении только коэффициентов преобразования Фурье последовательности входных отсчетов.Целью изобретения является расширение функциональных возможностей устройства путем вычисления коэффициентов преобразований в базисе функций Фурье, Хаара, Уолша и комплексных прямоугольных функций,Поставленная цель достигается тем, что в устройство, содержащее арифметический блок, блоки оперативной и постоянной памяти, группу коммутаторов, регистр итераций и счетчик операндов, причем информационые выходы блоков оперативной и постоянной памяти подключены соответственно к входам операндов и коэффици ентов арифметического блока, информационный выход которого подключенк информационному входу блока оперативной памяти, адресный вход которого подключен к выходам коммутатороргруппы, параллельный выход регист О 25 ра итераций подключен соответственно к управляющим входам коммутато ров группы, информационные входыкоммутаторов группы подключены,кроме выхода второго разряда, к 15параллельному выходу счетчика операндов, выход второго разряда которого подключен к входу управления записью-считыванием блока оперативной памяти, введены коммутатор, 20счетчик итераций, группа. элементовИ, регистр сдвига, формировательуправляющих сигналов, причем параллельный выход счетчика операндов,исключая выходы первого и второгоразрядов, подключен к информацион -ным входам коммутатора и регистрасдвига, выход коммутатора подключенк тактовому входу регистра итерацийи счетному входу счетчика итераций, 30параллельный выход которого подключен поразрядно к первым входам соответствующих элементов И группы и управляющему входу регистра сдвига,ВыхоДы элементоВ И ГРУппы поДключены соответственно к разрядам управляющего входа коммутатора, параллельный выход регистра сдвигаподключен, исключая старший разряд,к адресному входу блока постоянной 40памяти, вторые входы элементов Игруппы объединены и являются первым входом задания режима устройства, причем формирователь управляющих сигналов содержит элемент ИЛИ-НЕ,45первый и второй элементы И-НЕ, первый, второй, третий и четвертыйэлементы И, генератор тактовых импульсов, счетчик и формировательимпульсов, причем первые входы первых элементов И, И-НЕ и инверсныйвход второго элемента И-НЕ объединены и подключены к старшему разрядупараллельного выхода регистра сдвига, выход элемента ИЛИ-НЕ подключенк вторым входам первого и второгоэлемента И-НЕ и к инверсному вхсдучетвертого элемента И, выход которого подключен к управляющему входу формирователя импульсов, первый выход которого подключен к вторым входам Второго и. третьего элементов И, первые входы которых подключены к выходам соответственно пер вого и второго элементов И-НЕ, выход генератора тактовых импульсов подключен к счетному входу счетчика, параллельный выход которого подключен к адресному входу формирователя импульсов, третьи входы первого элемента И-НЕ и третьего элемента И и. второй вход первого элемента И соединены с входом управления сдвигом регистра итераций и являются вторым входом задания режима устройства, прямой вход четвертого элемента И является третьим входом задания режима устройства, выход переполнения счетчика соединен со счетным входом счетчика операндов, второй и третий выходы формирователя импульсов и выходы первого, второго, третьего и четвертого элементов И подключены к входу синхронизации арифметического блока, вход элемента ИЛИ соединен с параллельным выходом, исключая старший разряд, регистра сдвига.На фиг. 1 изображена блок-схема предлагаемого устройства, на фиг. 2 - блок-схема формирователя управляющих сигналов.Устройство содержит блоки оперативной 1 и постоянной 2 памяти, арифметический блок 3, группу коммутаторов 4, регистр 5 итераций, счетчик 6 операндов, коммутатор 7, счетчик 8 итераций,группу элементов И 9, регистр 10 сдвига и формирователь 11 управляющих сигналов.формирователь управляющих сигналов содержит элемент ИЛИ-НЕ 12, первый 13 и второй 14 элементы И-НЕ, первый 15, второй 16, третий 17 и четвертый 18 элементы И, генератор 19 тактовых импульсов, счетчик 20, формирователь 21 импульсов.Арифметический блок (АБ) 3 выполнен аналогично известному, предназначен для выполнения элементарного преобразования вида А + В У и содержит четыре сумматора, четыре ре гистра хранения результата, два коммутатора, два входных регистра хранения действительной и мнимой частей операнды, регистр синуса и(ПП) экспоненциального коэффициента И. Коэффициент И (отдельно значение синуса и косинуса) поступает 35 в АБ 3, выполняюн 1 ий элементарноепреобразование вида А + Б У, гдеА и В - считываемые из блока 1 ОПкомплексные операнды, представляемые как значения их действительных 40 и мнимых частей.Двоичный код с параллельноговыхода регистра 10 сдвига также наступает на вход формирователя 11 уп-,равляющих сигналов, а именно 45 на вход элемента ИЛИ-НЕ (фиг. 2),сигнал "0" на выходе которого зада -ет режим работы АБ 3 "Полное комплек.сное умножение". При этом на выходах первого 13 и второго 14 эле ментов И - НЕ и четвертого 18 элемента И появляется сигнал "1", серия тактовых импульсов записи врегистры хранения АБ 3 проходит спервого выхода формирователя 21 55 импульсов на выходы второго 16 итретьего 17 элементов И и далее поступает на тактовые входы записи(отдельно) регистров хранения проо регистр косинуса для занесения значения кспоненциального коэффициента Ч, младшие разряды которых через вентили подключены к управляющим входам соответственно первого,ьчетвертого и второго, третьегосумматоров, а управляющие входывентилей объединены,Счетчик 6 операндов, регистр 5итераций,. группа коммутаторов 4содержат соответственно о + 1,1 разрядов и в коммутаторовЗх 1(п = 1 оц,2 М, И - объем последовательности входных отсчетов),причем выход первого разряда счетчика 6 операндов подключен к вторым входам группы коммутаторов .4,выход (1 + 1)-го разряда, начинаяс третьего разряда - к первому входу 1 - го коммутатора, выход (1 + 2)-гразряда - к третьему входу 3-гокоммутатор ., а выход третьего разряда счетчика 6 операндов подключен к третьему входу первого коммутато-ра. Первый управляющий вход 1-го коммутатора подключен к выходу (1 - 1)-го разряда регистра 5 итераций, второй управляющий вход - к выходу 3-го разряда, причем первый управляющий вход первого коммутатора и второй управляющий вход И-го коммутатора подключены соответственно логическими потенциала 1 1 1 11 д 11Счетчик 8 итераций и группа элементов И 9 содержат К = 1:оя 2 п разрядов и элементов И соответственно.Устройство работает следующим об разом.При реализации быстрого преобраз вания Фурье (БПФ) на вхоцах Х 1, Х 2, ХЗ устройства установлен код 110, последовательность входных отсчетов расположена в блоке 1 оперативнойпамяти (ОП) в двоично-инверсном пор ке, а счетчики операндов 6 и.итераций 8 и регистр 5 итераций обнулены. Серия импульсов с второго выхода блока синхронизации 11 поступает на счетный вход счетчика 6 операндов, на выходах первого, третьего и последующих разрядов которого формируется исходный двоичный код, а на выходе второго. разряда - сигнал управления записью-считыванием блока 1 ОП. На управляющем входе коммутатора 7 задан нулевой код 51525Зо(элементы И 9 гр уппы за крыты) и сигнал переполнения с выхода старшего разряда счетчика б операндов поступает на счетный вход счетчика 8 итераций и тактовый вход регистра 5 итераций. При этом на выходах разрядов счетчика 8 итераций формируется двоичный. код номера итераций, а в регистр 5 итераций со стороны младшего разряда заносится "единица" со сдвигом ранее записанной информации в сторону старших разряСигналы с параллельного выхода регистра 5 итераций, поступая на управляющие входы коммутаторов 4 группы, преобразуют исходный двоичный код с параллельного выхода счетчика 6 операндов в двоичный код адреса записи и чтения операндов для определенной итерации БПФ согласно графу преобразования с замещением и прореживанием по времени. Двоичный код с параллельного выхода счетчика 8 итераций поступает на управляющий вход регистра сдвига 10, который, в зависимости от номера итерации и начального кода адреса считывания пары операндов, формирует коды адресов выборки из блока 2 постоянной памятирмирования кода адреспоненциального комомент ачений са изведения Ке В соя И; .1 в В з 1 п Нй регистров хранения результатовпроизведения Ке Взп И; Зщ Рсоя И соответственно, С второговыхода формирователя 21 импульсов натактовые входы регистров синуса икосинуса АБ 3 поступает серия импульсов, сдвигающая информациюв сторону младшего разряда, а сигнал "1" с выхода четвертого элемента И 18 разрешает прохождениечерез вентили информации с выходовмладших разрядов регистров синусаи косинуса на первые входы управления сумматоров,Сигнал с третьего выхода формирователя 21 импульсов управляет коммутаторами, причем в такте умножения к одному из информационныхвходов сумматоров через коммутаторы подключаются выходы входных регистров операндов и вычисляютсяпроизведения КеВ соз У; КеВ. зхп Ы,Зш В соз Ы и 3 ш Взп И, в тактеперекрестного сложения на этот жевход сумматоров поступают черезкоммутаторы результаты произведения с выходов соответствующих регистров хранения, выполняются операции вида Ке В соз У - Лш В зп И == Лш (В 11), и результаты суммирования Ке(В У) и Зш(В У) заноситсяв соответствующие регистры хранения по приходу отдельного импульсазаписи с первого выхода формирователя 21 импульсов, а в такте выполнения операции вида А + В И входысумматоров подключены через коммутаторы к входным регистрам операндов, где к этому моменту времени занесено значение отсчета А,и на информационных выходах сумматоров последовательно формируются для записи в блок 1 ОП действительные и мнимые части величины В = А-ВфУ, а затем величины А = А+В И Сигнал с выхода старшего разряда регистра 10 сдвига, определяющий (в зависимости от логического состояния "0" или "1") знак заносимой в регистры синуса и косинуса АБ 3 информации, поступает на вход формирователя 11 управляющих сигналов и через первый элемент И подается на входы управления сумматоров.эффициента с показателями 0 и Ж /2 на выходе элемента ИЛИ-НЕ 12 появляется сигнал "1, который задает режим работы ЛВ 3 "Умножение на 5 тривиальный множитель". При этом на выходе четвертого элемента И 18 появляется сигнал О", поступающий в АБ 3 и блокирующий прохождение информации через элементы И с выходов младших разрядов регистров синуса и косинуса на первые входы управления сумматоров. На первом выходе Формирователя 21 импульсов вместо серии тактовых импульсов 15 записи появляется одиночный импульс, который проходит на тактовые входы записи либо регистров хранения результатов произведения Ке В соз Ю Лш Всоз Ы (на входе Х 5 формировате ля управляющих 11 сигналов потенциал "О"), либо регистров хранения результатов произведения Ке В з 1 п У; ,1 в Вфз 1 п Ы (на входе Х 5 - потенциал "1"). Значение операндов (отдельно 25 ействительная и мнимая части) переписывается из входных регистров через сумматоры в соответствующие регистры хранения по приходу данного импульса записи и умножение на тривиальный множитель завершается. Далее осуществляются перекрестное сложение и операция вида А + В 1 которые анологичны режиму "Полное комплексное умножение При реализации преобразования 35в базисе комплексных прямоугольныхфункция (БП КПФ) на входах Х 1, Х 2,Х 3 установлен код 010, входныеотсчеты расположены в блоке 1 ОПв двоично-инверсном порядке, а формирование кодов адресов при записии считывании операндов блока 1 ОПдля всех итераций осуществляетсяаналогично БПФ. В базисе КПФ функсции синуса и косинуса принимают 45только целые значения -О, +1, -1,и режим работы АБ 3 "Полное комп,лексное умножение" изменяется так,что в этом случае элементы И на 50выходах младших разрядов регистров синуса и косинуса АБ 3 заблокированы (на выходе четвертого элемента И 18 потенциал "0"), а умножениеоперанда В на величину (+1) или(-1) осуществляется путем пересыпки значения действительной и мнимойчастей операнда В через сумматорыв соответствующие регистры хранения (при этом на их тактовые входы115060 10 9 1записи поступают через второй 16и третий 17 элементы И одиночныеимпульсы с,первого выхода формирователя 21 импульсов) с учетом знака комплексной функции. Перекрестное сложение и операция вида А+Вфлапри БП КПФ выполняются аналогичноБПФ. Кроме того, режим работы АБ 3"Умножение на тривиальный множитель" остается без изменений.При реализации преобразования вбазисе Уолш-образных функций (БАУ)на входах Х 1, Х 2, ХЗ устанавливается код 000. Входная информация,предназначенная для обработки, переупорядочена по закону либо двоично-разрядной инверсии, либо по коду Грея, в зависимости от видаУолш-образной периодический функции. Разряды регистра 5 итерацийустанавливаются в логическое состояние "1", причем в регистр со стороны старшего разряда по приходутактового импульса осуществляетсязапись нулевой информации. Формирование кодов адресов считывания изаписи операндов блока 1 происхо.дит аналогично БПФ .с учетом того,что в данном случае изменяется направление. граф преобразования, т,е.последняя итерация БПФ аналогичнапервой итерации БПУ, и т,д,АБ 3 работает только в режиме"Умножение на тривиальный множитель",причем импульс записи с первоговыхода формирователя 21 импульсовпроходит через второй элемент И 16только на тактовый вход записи регистров хранения результатов произведения Ке Весов И и 3 ш Весов У,затем осуществляется перекрестноесложение Ке В соз И в ,1 ш В з 1 п И =Ке В; Ке В з 1 п У + Лш Весов У = 10 .= Зш Васоз М = 1, з 1 п Ы = 0 и операрация вида А + В.При реализации преобразования вбазисе Хаар-образных функций (БПФ)на входах Х 1,. Х 2 и ХЗ устанавливаст ся код 001. Расположение входныхданных в блоке 1 ОП и работа АБ 3в режиме "Умножение на тривиальныймножитель.аналогичны БПУ. Группаэлементов И 9 пропускает двоичный 20 код с выходов разрядов счетчика 8итераций на управляющий вход коммутатора 7, выход которого на 1-й(1 = О, , и) итерации подключается к выходу (и)-го разряда 25 счетчика 6 операндов, и при этомформируются коды адресов записии считывания операндов для случаяреализации графа усеченного преобразования.З 0 Предлагаемое устройство позволяетвычислять коэффициенты преобразований в различных базисах дискретныхортогональных функций, а.именноФурье, Хаара, Уолша и комплексныхпрямоугольных функций.1115060 ектоР, В. Гирняк 6772/36 Тираж 698 ВНИИПИ Государственного комитета ССС по делам изобретений и открытий 3035, Москва,. 3-35, Раушская наб. д.