Устройство для быстрого преобразования Уолша-Адамара Советский патент 1990 года по МПК G06F17/14 

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

Цель изобретения - расширение класса решаемых задач за счет выполY, Yfi

X« +X,

X11 +X f. j

Y2t xai

Y22 ,

k«4

Y-IJ X,, X f j ; Yn X i x и

Y i X ч о -X

L23

14

aa

ито ий.

,

k«4

гэ;

14-J

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

В соответствии с предлагаемым алгоритмом для двумерного сигнала, который имеет отсчеты X.,,, Xf4, Xyj, XJ4,

X

Ц лц

x

4

41 4l 44-

на первом шаге вычисляются:

Y41 X41 +X434 Y42 - X42+X4 i Yo - -X 43} Y44 44}

сд

ОЗ О

ОЭ

со

00

Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа, цифровой обработки и сжатия изображений. Цель изобретения - расширение класса решаемых задач за счет выполнения двумерного преобразования Уолша-Адамара. Поставленная цель достигается за счет того, что в состав устройства входит первая и вторая группы соответственно из (N-1)-го и N каскадов преобразования первого типа N=LOG₂N

где N - размер вектора-строки (столбца), каскад преобразования второго типа, селектор импульсов, два счетчика, дешифратор, триггер, элемент И. 5 ил.

на втором шаге:

Z,,

1f

+Y

11

Z12 YII Y11

13 Y13 +YH-

Т4

Y13 Y14

- 11

YH+Y

21

Z14- Y41-Ya %li Y73+Y14

24 4.

21

a 14

14

Z4r Y41 +Y

41

41

42

Y41 Mj

i-Y

U43 t4}+Y44,

Z44 Y4J-Y44;

на третьем шаге:

Z

7 +7

11 31

К

гг

1г

+Z

Zj, +Z, ;

эг;

z

z,5+z35;

;

14 +Z34;

К 22

K13 ZZ3+Z43 ;

К 24 Z24+Z«,;

На четвертом шаге вычисляются коэффициенты двумерного преобразования

-м1 К-11 +KII i

С 9 К « +К

К,,

п

С,д К1Э+К С14 К14 +К

14

41

13 М;

,2г

кп

Ј23 К1Э

С24 К,4

На фиг.1 представлена структурная схема устройства для быстрого преоб,- разования Уолша-Адамара; на фиг.2 - граф быстрого двумерного преобразования Уолша-Адамара; на фиг.З и 4 - соответственно структурная схема селектора импульсов и временные диаграммы, поясняющие его работу; на фиг.З - временные диаграммы, поясняющие работу устройства.

Устройство для быстрого преобразования Уолша-Адамара содержит сумматоры 1, регистры 2 сдвига, сумматоры- вычитатели 3, коммутаторы 4, одноразрядный регистр 5 сдвига, селектор 6 импульсов, счетчик 7 (импульсов), дешифратор 8 (с импульсным выходом), триггер 9, элемент И 10, счетчик И (импульсов), информационный и тактовый входы 12 и 13 устройства, а также выходы одномерного 14 и двумерного 15 преобразователей.

Селектор 6 импульсов образуют эле мент И-НЕ 16 триггер 17f элемент И-НЕ 18,элемент НЕ 19 и элемент И 20.Селектор предназначен для выделения первого импульса из последовательности тактовых сигналов.

На временных диаграммах (фиг.4) показаны следующие сигналы: а - напряжение на тактовом входе 13 устройства; б - напряжение на выходе элемента И-НЕ 16; в - напряжение на выходе триггера 17; г - напряжение на выходе элемента НЕ 19; д - напряжение на выходе селектора.

На временных диаграммах (фиг.5) показаны следующие сигналы: U1 - напряжение на входе 13 устройства} Ut - напряжение на выходе селектора 6 импульсов; U3 - напряжение на управляющем входе коммутатора 4 первого каскада преобразования; U - напряжение на управляющем входе коммутатора 4

К,

71 -Z t

41 М1

К«-2

К4э z j-Z4j;

Уолша-Адамара:

Ј4.1 КЭ1 -K4t;

С„-K3Z-K4,;

С44 К34-К44.

n 5

д

0

5

0

второго каскада преобразования; 1)5 - напряжение на выходе триггера 9; Us - напряжение на выходе элемента И 10 U-, и Uj - напряжения на управляющих входах коммутатора 4 соответственно первого и второго дополнительных каскадов преобразования.

Временные диаграммы работы устройства показаны для размерности , а буквами обозначены, получаемые на каждом такте соответствующие значения.

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

Последовательность X „X 14Х 13 ,.. . ,

Х HI

XNa,...,XN3,..., X мн отсчетов входного сигнала с информационного входа 12 поступает с частотой тактовых импульсов на вход коммутатора 1 и на вход сумматора-вычитателя 3 первого каскада преобразования. Одновременно тактовые сигналы с входа 13 ус.тройст- ва поступают в селектор 6, который выделяет из их последовательности первый импульс, а остальные пропускает на свой выход к счетному входу счетчика -7 и входу элемента И 10. Так как в исходный момент триггер 9 находится s состоянии О, то поступившие тактовые импульсы на выход элемента И J0 не проходят.

На управляющий вход коммутатора J поступает сигнал О с n-го выхода счетчика 7 и подключает информационный вход 12 к входу регистра 2 сдвига. За время действия сигнала О в регистр 2 записывается N/2 отсчетов (Хя X ,Ј ,. .. ,Х11Чи) , которые задерживаются в нем на 2 тактов.

В течение последующих N/2 тактов на управляющие входы коммутаторов 1 и 4 поступает сигнал 1, который переключает выход суммы сумматора-вычк51

тателя 3 на выход коммутатора 4, а ход регистра 2 сдвига подключает че рез коммутатор 1 к выходу разности умматора-вычитателя 3.. В результате а выход коммутатора 4 первого каска а выводятся сформированные суммы, а в регистр 2 записываются полученные разности. Затем, когда на управляющих входах коммутаторов 1 и 4 появля ется сигнал О, на выход коммутатора 4 выводится значения полученных разностей с выхода регистра 2, а в регистр 2 одновременно записываются входные отсчеты ( , ... ,Х 2Mtt) .

Как только счетчик 7 заполнится, на выходе дешифратора 8 появляется импульс, который устанавливает триггер 9 в состояние 1. В результате элемент И 10 открывается для прохожения тактовых импульсов, которые по1 ступают на счетный вход счетчика J1.

В К-м каскаде (К 2,п-1) в соответствии с графом преобразований фиг.2) последовательность промежуточных данных задерживается в регист ре 2 сдвига на 2 к так тов. Суммы в течение 2 к тактов вьюодятся на выход коммутатора 4, а разности через коммутатор J записываются в регистр 2 сдвига. На управляющие входы коммутаторов 1 и 4 действует сигнал J В течение следующих 2 тактов разности из регистра 2 сдвига выводятся на выход коммутатора 4 и одновременно регистр заполняется очередной группой из данных, поступающих4 на вход коммутатора 1 из (K-l)-ro каскада. При этом на управляющие вхо ды коммутаторов 1 и 4 действует сигнал О, а управление коммутаторами осуществляется с (п - К+1)-го выхода счетчика 7.

В n-м каскаде данные непосредственно поступают на вход регистра 2 сдвига, в котором задерживаются на один такт, а получаемые в сумматоре- вычитателе 3 суммы проходят на выход коммутатора 4, когда на его управляюем входе имеется сигнал . Одновременно разности записываются в регистр 5 сдвига, где также задерживаются на один такт и выводятся на выход коммутатора 4, когда на его управляющем входе имеется сигнал О,

подаваемый с первого выхода счетчика 7. Регистр 5 необходим для того, чтобы на выход n-го каскада не поступала ложная информация.

363986

С выхода n-го каскада данные поступают на вход j-го каскада преобразо- вания (j 1,п), который работает аналогичным образом. При этом задержка в регистре 2 сдвига осуществляетг, 2п-1

ся на L тактов, а управление коммутаторами 1 и 4 производится сигналами с (n-j+l)-ro выхода счетчика И.

1Q Последовательность коэффициентов двумерного преобразования в естественном порядке формируется на выходе коммутатора 4 n-го дополнительного каскада преобразования.

15 -В случае необходимости коэффициенты одномерного преобразования Уолша- Адамара снимаются с выхода 14 устройства.

Селектор 6 импульсов работает сле20 дующим образом.

В исходный момент триггер 17 находится в состоянии О и на его выходе присутствует сигнал О (фиг.4в), а на выходе элемента И-НЕ 18 находит25 ся сигнал 1 (Аиг.4г), который открывает элемент И-НЕ 16 для прохождения тактовых сигналов.

Как только первый тактовый импульс (фиг.4а) поступает на вход элемента

30 И-НЕ 16, на его выходе появляется

сигнал О (фиг.4б), который устанавливает триггер 17 в состояние 1й (фиг.4в). В результате на одном входе элемента И-НЕ 18 имеется сигнал

35 1 (с выхода триггера 17), а на другом - О (с выхода элемента И-НЕ 16), Поэтому на выходе элемента И-НЕ 18 по-прежнему присутствует сигнал (фиг.4г), а на выходе элемента НЕ 19 40 сигнал О, который закрывает элемент И 20 (фиг.4д) для прохождения первого импульса (фиг.4е). Как только первый импульс заканчивается, на выходе элемента И-НЕ 18 устанавливается О,

45 который закрывает элемент И-НЕ 16, а на выходе элемента НЕ J9 появляется сигнал 3 (фиг.4д), который открывает элемент И 20 для прохождения последующих тактовых импульсов ((Ьиг.4е).

50 Так происходит выделение первого им-о пульса из последовательности тактовых сигналов селектором 6.

Формула изобретения 55 Устройство для быстрого преобразования Уолгаа-Адамара, содержащее первый счетчик, первую группу из (п-1) на (п 1оргН, N - размер вектора-строки) каскадов преобразования

первого типа и каскад преобразования второго типа, выход которого является выходом одномерного преобразования устройства, информационным входом которого является информационный вход первого каскада преобразования первого этапа первой группы, выход j-го (j ,п-2) каскада преобразования первого типа подключен к информапионному входу (j-5-1)-го каскада преобразования первого типа первой группы, а выход (n-J)-ro каскада преобразования первого типа первой группы подключен к информационному входу каскада преобразования второго типа, уп- равляющий вход которого подключен к выходу первого разряда первого счетчика, выход (n-i+l)-ro (i l,n-l) разряда которого подключен к управ- ляющему входу 1-го каскада преобразования первого типа первой группы, причем i-й каскад преобразования первого типа содержит первый и второй коммутаторы, сумматор вычитателъ и регистр сдвига, выход которого подключен к первому входу сумматора-вы- читателя, выходы суммы и разности которого подключены к первым информационным входам соответственно перво- го и второго коммутаторов, выходы которых подключены соответственно к выходу каскада и информационному входу регистра сдвига, выход которого подключен к второму информационному входу первого коммутатора, второй вход сумматора-вычитателя соединен с вторым информационным входом второго коммутатора и является информационным входом каскада, управляющим вхо- до дом которого являются соединенные между собой управляющие входы первого и второго коммутаторов, при этом каскад преобразования второго типа содержит первый и второй регистры сдви-45 га, коммутатор и сумматор-вычитатель, выходы суммы и разности которого подключены соответственно к первому информационному входу коммутатора и информационному входу первого регистра ,-п сдвига, выход которого подключен к

0 5 0

5

о 5 п

второму информационному входу коммутатора, выход которого является выходом, каскада, информационным входом которого являются соединенные между собой первый вход сумматора-вычитателя и информационный вход второго регистра сдвига, выход которого подключен к второму входу сумматора-вычитателя, а управляющий вход коммутатора является управляющим входом каскада, отличающееся тем, что, с целью расширения класса решаемых задач за счет выполнения двумерного преобразования Уолша-Адамара, в него введены селектор импульсов, дешифратор, триггер, элемент И, второй счетчик и вторая группа из п каскадов преобразования первого типа, причем, выход 1-го каскада преобразования первого типа второй группы подключен к информационному входу (i+1)- го каскада преобразования первого типа второй группы, а выход n-го каскада преобразования первого типа второй группы является выходом двумерного преобразования устройства, тактовым входом которого является вход селектора импульсов выход которого подключен к первому входу элемента И и счетному входу первого счетчика, выход k-ro разряда которого подключен к k-му (k 1,п) входу дешифратора, выход которого подключен к первому установочному входу триггера, выход которого подключен к второму входу элемента И, выход которого подключен к счетному входу второго счетчика, выход k-ro разряда которого подключен к управляющему входу k-ro каскада преобразования первого типа второй группы, выход каскада преобразования второго этапа подключен к информационному входу первого каскада преобразования первого типа второй группы, тактовые входы всех регистров сдвига всех каскадов преобразования первого и второго типов подключены к тактовому входу устройства, установочным входом которого является второй установочный вход триггера.

12

Тшад

Хил«

Щ

Фцз.1 Ж итогИ шаг

Ж шаг.

us.г

4-I

IL

, I

i I

T i . i i

Ч1-I111- t

K&SIOK /1J

Фиа.3

+ t

4-I

, I

Фиа4

S

Составитель А.Баранов Редактор Пчолинская Техред М.ХоданичКорректор М.Максимишинец

Заказ ПОТираж 556 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

in

4

sJ

S°