Устройство для быстрого преобразования уолша-адамара
Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа, цифровой обработки и сжатия изображений. Цель изобретения - расширение класса решаемых задач за счет выполнения двумерного преобразования Уолша-Адамара. Поставленная цель достигается за счет того, что в состав устройства входит первая и вторая группы соответственно из (N-1)-го и N каскадов преобразования первого типа N=LOG<SB POS="POST">2</SB>N где N - размер вектора-строки (столбца), каскад преобразования второго типа, селектор импульсов, два счетчика, дешифратор, триггер, элемент И. 5 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН (5 ) 5 С 06 F 15/332
ОПИСАНИЕ- ИЗОБРЕТЕНИЯ
Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ
Yif
У»2
У, У»4
» на втором
У4» Х «+ 4Z
У42 = Х42+Х44»
У»з = Х4,-Х4, Y44= Х42-Х 44»
У.2»= Х2»+Х2з
У22 Х 22+Х
Х 2 1 -Х 1 3.»
Y 4= Х22 —.Х24 х„„+х„;
Х»t+Х 4»
Х1» — »3»
Х,2-Х „„3. шаге .
Z4f
4»
43 г„=
У4» +У4 »
У4< У»2»
У»» У44»
У43 У 44» г2 = У24+У22»
Z12- У2 У2ф»
У Э+У2»
24 Yt» 4»
У»1 +У»2»
У»2»
Yt3+Y»4
У„-У„;
Z = г
Z» 3
С4
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР (21) 4414083/24-24 (22) 25.04.88 (46) l5,01.90, Бюл..Р 2 (71) Институт технической кибернетики АН БССР (72) P Х.Садыхов, А,Г.Мачнев» С.А.Золотой и Б.Х.Абдурахманов (53) 68),32 (088.8) (56) Патент США Р 3792355, кл. H 04 J 3/18, 1 979.
Авторское свидетельство СССР
Р 1265795, кл. G 06 F IS/332, )985. (54) УСТРОЙСТВО ДЛЯ БЬ!СТРОГО ПРЕОБРАЗОВАНИЯ УОЛРА-АДАМАРА (57) Изобретение относится к автоматике и вычислительной технике и моИзобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа, для цифровой обработки и сжатия изображений.
Пель изобретения — расширение класса решаемых задач за счет выпол„„SU„„3536398 А1
2 жет быть использовано для спектраль" ного и корреляционного анализа, цифровой обработки и сжатия изображенж. Цель изобретения — расширение класса решаемых задач за счет выполнения двумерного преобразования Уолша-Адамара. Поставленная цель достигается за счет того, что в состав устройства входит первая и вторая группы соответственно из (n-I)-го и и каскадов преобразования первого типа (n = log2N где N " размер вектора-строки (столбца), каскад преобразования второго типа, селектор импульсов, два счетчика, дешифратор, триггер, элемент И, 5 ип. нения быстрого двумерного преобраэо" вания Уолша-Адамара.
В соответствии с предлагаемым алгоритмом для двумерного сигнала, который и еет отсчеты Х„, Хи, Xfs» Х»4, q»» Х2Р Х У 44 ° ° ° . » Х4»» 4у Х»У Х» на первом шаге вычисляются:
1536398 на третьем шаге:
К11 =
Kfi=
К1э=
К, Z11+Z91 1
ZÄÄ+Z„;
Z„„+Z„„;
Z f4+ZZ4 »
К2 22 + 4
К22= Z22+Z421
К 23 Zts+Z43 1
К 24 2 24+» 44 э
K,—
K41 =
К43
К 44
Zt1 Zef 1
z„„-z„„;
Z2>-Zqqq q,„
24 44 1
Уолша-Адамара:
На четвертом шаге вычисляются коэффициенты двумерного преобразования
Cf„= K,„+K2, C, K Ê
С11 — К 22+К22
С1з = К1 +К2 ; С2З= К, -К
К14+К24, С24= К14-К
На фиг,1 представлена структурная схема устройства для быстрого преоб, разования Уолша-Адамара; на фиг,2 граф быстрого двумерного преобразования Уолша-Адамара; на фиг.3 и 4 — . 0 со о тв ет с твенно с т рук турн ая схема с електора импульсов и временные диаграммы, поясняющие его работу; на фиг.5 — временные диаграммь1„поясняю щие работу устройства: 25
Устройство для быстрого преобразо вания Уолша-Адамара содержит сумматоры 1, регистры 2 сдвига, сумматоры.вычитатели 3, коммутаторы 4, однораз рядный регистр 5 сдвига, селектор 6 0 импульсов, счетч ик 7 (импульсов), де шифратор 8 (с импульсным выходом), триггер 9, элемент И 10, счетчик 1) (импульсов), информационный и такто,вый входы 12 и 13 устройства, а также выходы одномерного 14 и двумерного 15 35 преоб ра зов ателей.
Селектор б импульсов образуют элемент И-НЕ 16 триггер 17„ элемент И-НЕ
18, элемент НЕ 1 9 и элемент И 20.Селектор
40 предназначен для выделения первого импульса из последовательности тактовых сигналов.
На временных диаграммах (фиг,4) показаны следующие сигналы: а — напряжение на тактовом входе 13 устройст45 . ва; б — напряжение на выходе элемента И-НЕ 16; в — напряжение на выходе триггера 17; г — напряжение на выходе элемента HE 19; д — напряжение на выходе селектора.
На временных диаграммах (фиг,5) показаны следующие сигналы: U — на1 пряжение на входе 13 устройства, U2— напряжение на выходе селектора 6 импульсов, U1 — напряжение на управляю55 щем входе коммутатора 4 первого каскада преобразования, U 4 — напряжение на управляющем входе коммутатора 4
21 .э С41 КЗ1 К41 э
221 С42.= К З2 К41 1
° » ° м1 С4э К зз К4З °
241 С44 К 34 К 44 ° второго каскада преобразования; U>— напряжение на выходе триггера 9; U — напряжение на выходе элемента И 1 О, U и U — напряжения на управляющих входах коммутатора 4 соответственно первого и второго дополнительных каскадов преобразования.
Временные диаграммы работы устройства показаны дпя размерности N-N
= 4 ° 4, а буквами обозначены, получаемые на каждом такте соответствукппие значения.
Устройство работает следующим образом.
Последовательность Х,„Х,2Х,З,..., Х2 Х Х ° Х ° ° Х fuff
Х „2 „° . ° „Х 1,..., Х мяотсчетов входного сигнала с информационного входа
12 поступает с частотой тактовых импульсов на вход коммутатора 1 и на вход сумматора-вычитателя 3 первого каскада преобразования. Одновременно тактовые сигналы с входа 13 устройства поступают в селектор 6, который выделяет иэ их.последовательности первый импульс, а остальные пропуска1 ет на свой выход к счетному входу счетчика 7 и входу элемента И 10. Так как в исходный момент триггер 9 находится в состоянии "0", то поступившие тактовые импульсы на выход элемента
И 10 не проходят, На управляющий вход коммутатора поступает сигнал "0" с п-го выхода счетчика 7 и подключает информационный вход 12 к входу регистра 2 сдвига. За время действия сигнала "011 в регистр 2 записывается N/2 отсчетов (Х „Х,2, ° ° . 1Õ f „12), которые задерживаются в нем на 2 тактов.
В течение последующих N/2 тактов на управляющие входы коммутаторов 1 и 4 поступает сигнал "1 ", который переключает выход суммы сумматора-вычи1536398 тателя. 3 на выход коммутатора 4, а вход регистра 2 сдвига подключает через коммутатор 1 к выходу разности сумматора-вычитателя 3. В результате на выход коммутатора 4 первого каскада выводятся. сформированные суммы, а в регистр 2 записываются полученные разности, Затем, когда на управляющих входах коммутаторов 1 и 4 появляется сигнал "0", на выход коммутатора 4 выводится значения полученных разностей с выхода регистра 2, а в регистр 2 одновременно записываются входные отсчеты (Х, Х l2 Х „,я) ..
Как только счетчик 7 заполнится, на выходе дещифратора 8 появляется импульс, который устанавливает триггер 9 в состояние "1". В результате элемент И 10 открывается для прохождения тактовых импульсов, которые поступают на счетный вход счетчика 11.
В К-м каскаде (К = 2,n-l) в соответствии с графом преобразований (фиг.2) последовательность промежуточных данных задерживается в регистре 2 сдвига на 2 "" тактов. Суммы в течение 2" " тактов выводятся на выход коммутатора 4, а разности через коммутатор 1 записываются в регистр
2 сдвига ° На управляющие входы коммутаторов 1 и 4 действует сигнал "1". к
В течение следующих 2" тактов .разности из регистра 2 сдвига выводятся на выход коммутатора 4 и одновременно регистр заполняется очередной группой из 2" данных, поступающих на вход коммутатора 1 из (К-1)-ro каскада. При этом на управляющие входы коммутаторов 1 и 4 действует сиг, нал "0, а управление коммутаторами осуществляется с (и — К+1)-го выхода счетчика 7 ..
В и-м каскаде данные непосредственно поступают на вход регистра 2 сдвига, в котором задерживаются на один такт, а получаемые в сумматоревычитателе 3 суммы проходят на выход коммутатора 4, когда на его управляющем входе имеется сигнал "1". Одновременно разности записюваются в регистр 5 сдвига, .где также задерживаются на один такт.и выводятся на выход коммутатора 4, когда на его уп-. равляющем входе имеется сигнал 0
11 1т подаваемый с первого выхода счетчика 7. Регистр 5 необходим для того, чтобы на выход n-ro каскада не поступала ложная информация.
30 сигнал "0" (фиг.4б), который устанавливает триггер 17 в состояние "1" (фиг.4в), В результате на одном входе элемента И-EIE 18 имеется сигнал
35 "1" (с выхода триггера 17), à íà другом.- "О" (с выхода элемента И-НЕ 16), Поэтому на выходе элемента И-НЕ 18 по-прежнему присутствует сигнал "1" (фиг.4г), а на выходе элемента НЕ 1940 сигнал 0", который закрывает элемент
И 20 (фиг.4д) для прохождения первого импульса (фиг.4е). Как только первьп» импульс заканчивается, на выходе элемента И- IE 18 устанавливается "0", который закрывает элемент И-HE 16, а на выходе элемента НЕ 19 появляется сигнал "1" (фиг.4д), которьп» открывает элемент И 20 для прохождения последующих тактовых импульсов (фиг,4е) .
50 Так происходит выделение первого импульса из последовательности тактовых сигналов селектором 6.
5
С выхода n-ro каскада данные поступают на вход 1-ro каскада преобразования (j = I,n), который работает аналогичным образом. При этом задержка в регистре 2 сдвига осуществляет2n-) ся на 2 тактов, а управление коммутаторами 1 и 4 производится сигналами с (n-j+1)-го выхода счетчика 11.
Последовательность коэффициентов двумерного преобразования в естествен-: ном порядке формируется на выходе коммутатора 4 n-ro дополнительного каскада преобразования. ,В случае необходимости коэффициенты одномерного преобразования УолшаАдамара снимаются с выхода 14 устройства.
Селектор 6 импульсов работает следующим образом.
В исходный момент триггер 17 находится в состоянии "0" и на его выходе присутствует сигнал ".0" (ф»»г,4в), а на выходе элемента И-HE 18 находится сигнал "1" (h»»r.4г), которьп» открывает элемент И-НЕ 16 для прохождения тактовых сигналов.
Как только первый тактовый импульс (фиг.4а) поступает на вход элемента
И-НЕ 16, на его выходе появляется
Формула изобретения
Устройство для быстрого преобразования Уолша-Адамара, содержащее первый счетч»пс, первую группу из (и-1) íà (n = log N, N — размер вектора-строки) каскадов преобразования
7 15363
I первого типа и каскад преобразования второго типа, выход которого является выходом одномерного преобразования устройства, информационным входом ко5 торого является информационный вход первого каскада преобразования первого этапа первой группы, выход j -го (j = 1,п-2) каскада преобразования первого типа подключен к информапион- 10 ному входу () +1)-ro каскада преобразования первого типа первой группы, а выход (n-1) -ro каскада преобразования первого типа первой группы подключен к информационному входу. каска- 15 да преобразования второго типа, управляющий вход которого подключен к выходу первого разряда первого счетчика, выход (п-i.+1) -го (i = 1,n-1) разряда которого подключен к управляющему входу 1. †.го каскада преобразования первого типа первой группы, причем i-й каскад преобразования первого типа содержит первый и второй коммутаторы, сумматор вычитатель и 25
perистр сдвига, выход которого подключен .к первому входу сумматора-вычитателя, выходы суммы и разности которого подключены к первым информационным входам соответственно перво- 30
ro и второго коммутаторов, выходы которых подключены соответственно к.выходу каскада и инФормационному входу регистра сдвига, выход которого подключен к второму информационному вхо- 5 ду первого коммутатора, второй вход сумматора-вычитателя соединен с вторым информационным входом второго коммутатора и является информационным входом каскада, управляющим вхо- 0 дом которого являются соединенные между собой управляющие входы первого и второго коммутаторов, при этом каскад преобразования второго типа содержит первый и второй регистры сдви-. 45 га, коммутатор и сумматор-вычитатель, выходы суммы и разности которого подключены соответственно к первому информационному входу коммутатора и информационному входу первого регистра
50 сдвига, выход которого подключен к
98 второму информационному входу коммутатора, выход которого является выходом каскада, информационным входом которого являются соединенные между собой первый вход сумматора-вычитателя и информационный вход второго регистра сдвига, выход которого подключен к второму входу сумматора-вычитателя, а управляющий вход коммутатора является управляющим входом каскада, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемьм задач за счет выполнения двумерного преобразования Уолша-Адамара, в него введены селектор импульсов, дешифратор, триггер, элемент И, второй счетчик и вторая группа из п каскадов преобразования первого типа, причем выход i-го каскада преобразования первого типа второй группы подключен к информационному входу (i+1)го каскада преобразования первого типа второй группы, а выход и-го каскада преобразования первого типа второй группы является выходом двумерного преобразования устройства, тактовым входом кото рого является вход селектора импульсов выход которого подключен к первому входу элемента И и счетному входу первого счетчика, выход
k-го разряда которого подключен к
k-му (k = 1,n) входу дешифратора; выход которого подключен к первому установочному входу триггера, выход которого подключен к второму входу элемента И, выход которого подключен к счетному входу второго счетчика, выход k-ro разряда которого подключен к управляющему входу k-го каскада преобразования первого типа второй группы, выход каскада преобразования второго этапа подключен к информационному входу первого каскада преобразования первого типа второй группы, т ак тов ые входы в с ех ре r ис т ров с дв ига всех каскадов преобразования первого и второго типов подключены к тактовому входу устройства, установочным входом которого является второй установочный вход триггера.
l536398 11
XQ
Xg
1Ч
Хо х» хг5
Х
К31 Ì
x „
ХЧ1
Х91 х„ х,„
Гшаг
Eclat
E ы г
)536398
I 536398
Со с та в итель А. Б а рано в
Техред N.Õoäàíè÷
Редактор Л.Пчолинская
Корректор N. Макснмишииец
Заказ 1) 0 Тираж 556 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно †издательск комбинат "Патент", г. Ужгород, ул. Гагарина, 101