Устройство для быстрого преобразования уолша-адамара

(51)5 С 06 Р 15/33 ГОСУДАРСПО ИЭОБПРИ ГНН ЕННЫЙ КОМИТЕТЕТЕКИЯМ И ОТКРЫТИЯМ ССР ОПИСАНИЕ ИЗОБРЕТЕН ТЕПЬСТ К АВТОРСКОМ л. 11" 2нической кибе т СР19 тельство СС6 Р 15/332,ДЛЯ БЬСТРОГО ПРЕАДАМАРАтносится к автной технике и 5. Бею маоалСЬ МУ41 Т 21 = Х 21+Х 2 э-э 722 Х гг+Х т- х,-х; 24= Х 22-.Х 24.,Х+Х,Х,2 +Х,Х 1 э 1Х,Х 4, +Х 4 э, Х 4 г+Х 441 Х-Х 4 ,Х 42-Х 44,на втором 1 421 1 42 ф Э 44У 22 Е 2 Е =Ум212Е 1 э У 1 э214 У 1 242= У 4 Э244= 7(71) Институт техки АН БССР(54) УСТРОЙСТВОРАЗОВАНИЯ УОЛРА(57) Изобретение отике и вычислитель Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа, для цифровой обработки и сжатия изображенийПель изобретения - расширение класса решаемых задач за счет выполжет быть использовано для спектраль"ного и корреляционного анализа, цифровой обработки и сжатия изображенж . Цель изобретения - расширениекласса решаемых задач за счет выполнения двумерного преобразования Уолша-Адамара. Поставленная цель достигается за счет того, что в составустройства входит первая и втораягруппы соответственйо из (и)-го ии каскадов преобразования первоготипа (и = 1 о 82 Н где М " размер вектора-строки (столбца), каскад преобразования второго типа, селектор импульсов, два счетчика, дешифратор,триггер, элемент И, 5 ип. нения быстрого двумерного преобраэо" вания Уолша-Адамара.В соответствии с предлагаемым горитмом для двумерного сигнала, который имеет отсчеты Х, Х Х Х,4, Х 211 Хгр Х 2 э 1 Х 24 вф 1 Х 411 Х 42 Х 4 у Х 44 на первом шаге вычисляются:1536398 на третьем шаге: КмКч=К 1 э=К,211 +Е э 1 1 Е+г; г+Е;21 о+Еэ сэ К 1= 2,+Е, Кл Еы+Еи 1 К э= Е э+2 1 э 1 К= г+Е ; К 41К =К 4 эК 44 211 241 1 Ей 24 Егэ-Ем 1 ЕмУолша-Адамара: На четвертом шаге вычисляются коэффициенты двумерного преобразования С 11 = К 1+КС 1= К 1-КСи - Кц+К, С - К -КС 1 э = К 1 э+Кээ Сз= К 1 эС = К 1,1+К,1, С,1= К 1-КНа фиг,1 представлена структурнаясхема устройства для быстрого преоб,разования Уолша-Адамара; на фиг,2граф быстрого двумерного преобразования Уолша-Адамара; на фиг,3 и 4соответственно структурная схема селектора импульсов и временные диаграммы, поясняющие его работу; нафиг.5 - временные диаграммь.1 поясняющие работу устройства: 25Устройство для быстрого преобразования Уолша-Адамара содержит сумматоры 1, регистры 2 сдвига, сумматорывычитатели 3, коммутаторы 4, одноразрядный регистр 5 сдвига, селектор бимпульсов, счетчик 7 (импульсов), дешифратор 8 (с импульсным выходом),триггер 9, элемент И 10, счетчик 11(импульсов), информационный и такто,вый входы 12 и 13 устройства, а такжевыходы одномерного 14 и двумерного 15 35преобразователей,Селектор б импульсов образуют элемент И-НЕ .16 триггер 17 элемент И-НЕ18,элемент НЕ 19 иэлемент И 20.Селектор40предназначен для выделения первогоимпульса из последовательности тактовых сигналов.На временных диаграммах (фиг,4) показаны следующие сигналы: а - напряжение на тактовом входе 13 устройст 45. ва; б - напряжение на выходе элемента И-НЕ 16; в - напряжение на выходетриггера 17; г - напряжение на выходеэлемента НЕ 19; д - напряжение на выходе селектора.На временных диаграммах (фиг,5)показаны следующие сигналы. "Б - напряжение на входе 13 устройства, 11 -напряжение на выходе селектора 6 импульсов; Б з - напряжение на управляю 55шем входе коммутатора 4 первого каскада преобразования; Б- напряжениена управляющем входе коммутатора 4 1 Э С 41 Кэ 1 К 41 эИэ С1м 1 С 43 К ээ Ксэ141 Си" К-К,второго каскада преобразования; Увнапряжение на выходе триггера 9; О -напряжение на выходе элемента И 10,Б и 11 Э - напряжения на управляющихвходах коммутатора 4 соответственнопервого и второго дополнительных каскадов преобразования.Временные диаграммы работы устройства показаны дпя размерности МфИ= 44, а буквами обозначены, получаемые на каждом такте соответствукппиезначения.Устройство работает следующим образом.Последовательность Х 1 Х 1 Х 1 эХ, ХХ э,Х Х 11 .ХХ н э,Х Иотсчетов входного сигнала с информационного входа12 поступает с частотой тактовых импульсов на входкоммутатора 1 и навход сумма то ра-вычита тел я 3 пе рвогокаскада преобразования. Одновременнотактовые сигналы с входа 13 устройства поступают в селектор 6, которыйвыделяет иэ их.последовательностипервый импульс, а остальные пропуска 1ет на свой выход к счетному входусчетчика 7 и входу элемента И 10. Таккак в исходный момент триггер 9 находится в состоянии "О", то поступившиетактовые импульсы на выход элементаИ 10 не проходят,На управляющий вход коммутаторапоступает сигнал "О" с п-го выходасчетчика 7 и подключает информационный вход 12 к входу регистра 2 сдвига. За время действия сигнала 0 врегистр 2 записывается И/2 отсчетов(ХХ,Х,1), которые задерживаются в нем на 2тактов.В течение последующих И/2 тактовна управляющие входы коммутаторов 1и 4 поступает сигнал "1", который переключает выход суммы сум 11 атора-вычитателя. 3 на выход коммутатора 4, авход регистра 2 сдвига подключает через коммутатор 1 к выходу разностисумматора-вычитателя 3, В результатена выход коммутатора 4 первого каскада выводятся, сформированные суммы, ав регистр 2 записываются полученныеразности, Затем, когда на управляющих входах коммутаторов 1 и 4 появляется сигнал "0", на выход коммутатора 4 выводится значения полученныхразностей с выхода регистра 2, а врегистр 2 одновременно записываютсявходные отсчеты (х, х 22 ююх 2 нп)Как только счетчик 7 заполнится,на выходе дещифратора 8 появляетсяимпульс, который устанавливает триггер 9 в состояние "1", В результатеэлемент И 10 открывается.для прохождения тактовых импульсов, которые поступают на счетный вход счетчика 11,В К-м каскаде (К = 2,п) в соответствии с графом преобразований( фиг.2) последовательность промежуточных данных задерживается в регистре 2 сдвига на 2 пф тактов. Суммы втечение 2 " " тактов выводятся на выход коммутатора 4, а разности черезкоммутатор 1 записываются в регистр2 сдвигаНа управляющие входы коммутаторов 1 и 4 действует сигнал "1",кВ течение следующих 2" тактов .разности из регистра 2 сдвига выводятсяна выход коммутатора 4 и одновременно регистр заполняется очереднойгруппой из 2 "данных, поступающихна вход коммутатора .1 из (К) -гокаскада. При этом на управляющие входы коммутаторов 1 и 4 действует сиг",нал 0, а управление коммутаторамиосуществляется с (и - К+1)-го выходасчетчика 7В и-м каскаде данные непосредственно поступают на вход регистра 2сдвига, в котором задерживаются наодин такт, а получаемые в сумматоревычитателе 3 суммы проходят на выходкоммутатора 4, когда на его управляющем входе имеется сигнал "1", Одновременно разности записщваются в регистр 5 сдвига, .где также задерживаются на один такт.и выводятся на вы"ход коммутатора 4, когда на его уп-.равляющем входе имеется сигнал 011 Иподаваемый с первого выхода счетчика 7, Регистр 5 необходим для того,чтобы на выход и-го каскада не поступала ложная информация, 30 сигнал "0" (фиг.4 б), который устанавливает триггер 17 в состояние "1"(фиг, 4 в), В ре зуль та те на одном входе элемента И-НЕ 18 имеется сигнал(с выход тригор 17), а на другом." "О" (с выхода элемента И-НЕ 16),Поэтому на выходе элемента И-НЕ 18по-прежнему присутствует сигнал "1"(Фиг.4 г), а на выходе элемента НЕ 19- 40 сигнал 0 который закрывает элементИ 20 (фиг.4 д) для прохождения первогоимпульса (фиг.4 е). Как только первьпимпульс заканчивается, на выходе элемента И-НЕ 18 устанавливается "0", 45 который закрывает элемент И-НЕ 16, ана выходе элемента НЕ 19 появляетсясигнал "1" (фиг.4 д), которьп открывает элемент И 20 для прохождения последующих тактовых импульсов (фиг,4 е), 50 Так происходит выделение первого импульса из последовательности тактовыхсигналов селектором 6. 5 10 15 20 25 С выхода и-го каскада данные поступают на вход 1-го каскада преобразо-вания (1 = 1,п), который работаетаналогичным образом. При этом задержка в регистре 2 сдвига осуществляет 2 й-ся на 2тактов, а управление коммутаторами 1 и 4 производится сигналами с (и+1)-го выхода счетчика 11.Последовательность коэффициентов двумерного преобразования в естествен-:ном порядке Формируется на выходе коммутатора 4 и-го дополнительного каскада преобразования.,В случае необходимости коэффициенты одномерного преобразования УолшаАдамара снимаются с выхода 14 устройства.Селектор 6 импульсов работает следующим образом,В исходный момент триггер 17 находится в состоянии "0" и на его выходе присутствует сигнал ".0" (Фиг,4 в),а на выходе элемента И-НЕ 18 находится сигнал "1" (Фиг,4 г ), которьп открывает элемент И-НЕ 16 для прохождения тактовых сигналов,Как только первый тактовый импульс(фиг,4 а) поступает на вход элемента И-НЕ 16, на его выходе появляется Формула изобретенияУстройство для быстрого преобразования Уолша-Адамара, содержащее первьй счетчпс, первую группу из (и) на (и = 1 оя Н, Х - размер вектора-строки) каскадов преобразования15363первого типа и каскад преобразования второго типа, выход которого является выходом одномерного преобразования устройства, информационным входом ко 5 торого является информационный вход первого каскада преобразования первого этапа первой группы, выход 1-го Ц = 1,п) каскада преобразования первого типа подключен к информапион ному входу Ц +1)-го каскада преобразования первого типа первой группы, а выход (и)-го каскада преобразования первого типа первой группы подключен к информационному входу каска да преобразования второго типа, управляющий вход которого подключен к выходу первого разряда первого счетчика, выход (и+1) -го (1. = 1,п) разряда которого подключен к управляющему входу 1-го каскада преобразования первого типа первой группы, причем 1-й каскад преобразования первого типа содержит первый и второй коммутаторы, сумматор вычитатель и 25 регистр сдвига, выход которого подключен .к первому входу сумматора-вычитателя, выходы суммы и разности которого подключены к первым информационным входам соответственно перво го и второго коммутаторов, выходы которых подключены соответственно к выходу каскада и информационному входу регистра сдвига, выход которого подключен к второму информационному входу первого коммутатора, второй вход сумматора-вычитателя соединен с вторым информационным входом второго коммутатора и является информационным входом каскада, управляющим вхо дом которого являются соединенные между собой управляющие входы первого и второго коммутаторов, при этом каскад преобразования второго типа содержит первый и второй регистры сдви-. 45 га, коммутатор и сумматор-вычитатель, выходы суммы и разности которого подключены соответственно к первому информационному входу коммутатора и информационному входу первого регистра50 сдвига, выход которого подключен к 98второму информационному входу коммутатора, выход которого является выходом каскада, информационным входом которого являются соединенные между собой первый вход сумматора-вычитателя и информационный вход второго регистра сдвига, выход которого подключен к второму входу сумматора-вычитателя, а управляющий вход коммутатора является управляющим входом каскада, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемьм задач за счет выполнения двумерного преобразования Уолша-Адамара, в него введены селектор импульсов, дешифратор, триггер, элемент И, второй счетчйк и вторая группа из п каскадов преобразования первого типа, причем выход 1-го каскада преобразования первого типа второй группы подключен к информационному входу (+1)- го каскада преобразования первого типа второй группы, а выход и-го каскада преобразования первого типа второй группы является выходом двумерного преобразования устройства, тактовым входом которого является вход селектора импульсов выход которого подключен к первому входу элемента И и счетному входу первого счетчика, выход К-го разряда которого подключен к 1-му= 1,п) входу дешифратора; выход которого подключен к первому установочному входу триггера, выход которого подключен к второму входу элемента И, выход которого подключен к счетному входу второго счетчика, выход 1-го разряда которого подключен к управляющему входу 1-го каскада преобразования первого типа второй группы, выход каскада преобразования второго этапа подключен к информационному входу первого каскада преобразования первого типа второй группы, тактовые входы всех регистров сдвига всех каскадов преобразования первого и второго типов подключены к тактовому входу устройства, установочным входом которого является второй установочный вход триггера.Хд 8 тг Хд Гшаг Гулаг 1536398 Уют153 б 398 Составитель А, Барановедактор Л, Пчолинская Техред М. Ходанич Корректор М.Ма акаэ 11 ираж 5 Подписное и ГКНТ СССР изводственно в издательск комбинат Патент , г, Ужгород,гарина, 101 Государственног 113035