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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа, цифровой обработки и сжатия изображений. Цель изобретения - расширение класса решаемых задач за счет выполнения двумерного преобразования Уолша-Адамара. Поставленная цель достигается за счет того, что в состав устройства входит первая и вторая группы соответственно из (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