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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в технике цифровой обработки сигналов. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят два блока регистров сдвига 1, 2, два регистра 3, 4, коммутатор 5, сумматор-вычитатель 6, блок синхронизации 7 и соответствующие связи между узлами устройства. 4 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

„„SU„„1571610 А 1 (g1)g С 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОЩРЦТИЯМ

Г1РИ ГКНТ СССР

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

2 (54) УСТРОЙСТВО ДЛЯ ОРТОГОНАЛЬНОГО

ПРЕОБРАЗОВАНИЯ ПО УОЛИУ-АДАМАРУ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в технике цифровой обработки сигналов. Цель изобретения — повышение быстродействия.

Поставленная цель достигается sa счет того, что в состав устройства входят два блока регистров сдвига 1,2, два регистра 3,4, коммутатор 5, сумматор- эычитатель 6, блок синхронизации 7 и, соответствующие связи между узлами устройства. 4 ил.

1. (21) 4378819/24-24 (22) 15.02.88 (46) 15.06.90, Бюл. М2 22 (71) Х () Хозрасчетныи научно-исследовательский институт "Алгоритм" при Узб екском научно-производственном объединении "Кибернетика" (72) И.И.Исмагилов (53) 681, 32 (088. 8) (56) Гулямов С.С. и др. Малые вычислительные машины систем АСВРМ и СМЭВМ . и их применение для автоматизации научных исследований. Ташкент: Фан, 1985, с. 112, рис. 5.1.

Авторское свидетельство СССР

N 1234847, кл. С 06 F 15/332, 1984.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

Цель изобретения — повышение быстродействия устройства.

На фиг. 1 приведена функциональная схема устройства ортогонального преобразования по Уолшу-Адамару; ка фиг.2— функциональная схема блока синхронизации; на фиг. 3 — временная диаграмма блока синхронизации; на фиг. 4 -- графсхема преобразования по Уолшу-Адамару при N=8

Устройство содержит первый блок 1 регистров сдвига, второй блок 2 реги- 2р стров сдвига, первый регистр 3, второй регистр 4, коммутатор 5, сумматорвычитатель 6, блок 7 синхронизации и вход 8 запуска устройства.

Блок синхронизации (фиг.2) содер- 25 жит вход 8 запуска, одновибратор 10, элементы 1 1,12 задержки, генератор 13 тактовых импульсов, триггер 14, делители 15,16 частоты, формирователь 17 короткого импульса, элементы ИЛИ 18—

2О и выходы 21 — 25.

Блок синхронизации Формирует необходимые тактовые последовательности следующим образом. По коротко— му синхроимпульсу, поступающему по входу 9, срабатывает одновибратор 1 ), который Формирует стробирующий импульс разрешения записи данных в блоки 1,2 регистров сдвига. Задержанные синхроимпульсы с выходов элементов 4р

1 1,12 задержки используются для записи-исходных данных и объединяются в соответствующих элементах ИЛИ 19,2Р с тактовыми импульсами с выхода генератора 13 тактовых импульсов . Запуск 45 генератора 13 тактовых импульсов осуществляется импульсом с выхода элемента 12 задержки. Тактовые импульсы с выхода генератора 13 поступают на вход триггера 1.4 со счетным входом, 5р который формирует импульс управления, подаваемый на выход блока 25 синхронизации. Импульсы с выхода счетного триггера 14 поступают на вход первого делителя 15 частоты, который делит

N частоту следования импульсов на (-+2), N т.е. на его выходе имеет каждый (2+

+2)-й импульс входной последовательности. Второй делитель 16 частоты делит частоту входного сигнала на и, вследствие чего иа выходе этого делиБ теля будет п(-+2)-й импульс с выхода

2 триггера 14, По заднему фронту этого импульса формирователь 17 короткого импульса формирует импульс, который останавливает генератор 13. Таким образом генератор 13 сформирует такто вую последовательность из Il(N+4) импульсов, В начале кажцого цикла преобразования счетный триггер 14, делители

15, 16 частоты, устанавливаются в исходное состояние путем подачи импульса с выхода элемента 11 задержки на их управляющие входы.

В качестве импульсов разрешения записи промежуточных результатов преобразования с первого блока 1 пегистров сдвига во второй блок 2 регистров сдвига импользуются импульсы с выходов делителя 15 частоты, которые объединяются с выходным импульсом одновибратора 1 ) на элементе ИЛИ 18 °

На фиг. 3 представлены диаграммы работы блока 7 синхронизации.

На диаграммах 1 и 2 представлены соответственно сикхроимпульс, посту" пающий на вход запуска устройства, импульс с выхода элемента 12 задержки. !

На диаграммах 4-7 показаны соответственно сигналы с выходов генератора 13, триггера 14, делителя 15 частоты, делителя 16 частоты и формирователя 17 короткого импульса.

На диаграмме 3 показан стробирующий импульс с выхода одновибратора 10.

В соответствии с используемым -алгоритмом над входной выборкой данных, представляемой вектор-столбцом f размерностью N, производится следующее преобразование:

F=-Н„.f (1) где F — вектор-столбец коэффициентов

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

Н вЂ” матрица Уолша-Адамара размерК ности NxN;

И = 2", где п -положительное целое.

Преобразования Уолша-Адамара производятся итерационно за и итераций по формуле:

F=(S„H g ... (Sg. Н „(Sg Н ". ), (2) 5 l5 где Н()=Н()=...=Н(„"1, матрица размером

NxN;

S — мономиальная матрица перестаH новки. (I1

Нн 1ниВН i 1 и где 1 ((— единичная матрица порядка N/2;

Н2 — матрица Адамара порядка 2;

Н,—

Таким образом, вычислительная процедура (2) реализуется за п итераций, при этом каждая i-я итерация сводится к умножению вектора-столбца результатов f;-„ на матрицу Н „, что сводит(s) ся к сложению или вычитанию соответствующих элементов промежуточного вектора f; и переупорядочиванию

f элементов результирующего вектора f умножением на мономиальную матрицу S .

Суть перестановки заключается в разделении массива элементов вектора f.

1 на массивы четных и нечетных элементов и формировании переупорядоченного вектора f путем последовательно— ( го расположения этих массивов, при этом массив нечетных элементов вектора f. располагается в первой полови1 не результирующего массива. Правило ,перестановки можно задать следующим соотношением: й; (2 (j-1)+1), при 1=1,И/2, Е; (2 (j — -), при j =N/2+1, N

1(3) (3) Элементы матрицы Sр2 определяются по формуле: при i=1 N/2

N. при i= — +1,N, 1, j =1+2 (i-1), 1, j=2(i- -)

О, иначе.

S.,=

1! 1

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

Устройство рассчитано на естественный порядок входных данных. Однако в устройство при перезаписи данных с первого блока 1 регистров сдвига на второй блок 2 регистров сдвига осуществляется переупорядочение данных по правилу (3), вследствие чего требует- ся переупорядочение исходных данных при записи в первый блок 1 регистров сдвига. Необходимо их переупорядочить

71610

2 (j -1) +1, j =1, N/2, 2 (j — -), j =-+1,N, N . N где

И Е, 5

6 таким образом, чтобы после перезаписи во,второй блок 2 регистров сдвига они оказались в естественном порядке, т.е. перед началом вычислений N отсчетов сигнала находятся на последовательных адресах i=1,N в блоке 2 регистров сдвига.

После прихода синхроимпульса на управляющий вход 8 устройства на входы разрешения записи первого и второго блоков 1,2 поступают стробирунщие импульсы с выходов блока 7 синхронизации.

Первый тактовый импульс, поступающий на вход блока 1 регистров сдвига с выхода блока 7 синхронизации, произведет параллельную запись исходных данных и регистры сдвига блока 1 °

Вследствие того, что i вход (i=1 Я) группы (параллельного ввода информации) блока 1 регистров сдвига подключен к j ìó информационному входу устройства исходные данные запишутся в регистры сдвига блока 1 в переупорядоченном виде. Первый тактовый импульс с выхока блока 7 синхронизации перепишет переупорядоченные исходные данные в блок 2 регистров сдвига, в котором они окажутся в регистрах с порядковыми номерами i-=1,N в естественном порядке за счет соответствующего соединения выходов блока 2 регистров сдвига и входов блока 2 регистров сдвига.

После этого устройство. готово к началу вычислений ортогонального преобразования выборки исходных данных размерности N °

За первые N тактов первой итерации

N отсчетов сигнала сдвигаются на выход О-го регистра сдвига блока 2, поступают на вход регистра 3 и первый информационный вход коммутатора 5. Работу коммутатора можно описать следующим правилом:

1- 1

Х ((О, то

2 — 1

3 2 — логическое состояние на управляющем входе коммутатора; — подключение M-го информационного входа коммутатора к 1.-му выходу;

157161 1

М =1,3, I,"1,2., Первый f, и второй f отсчета (и далее каждый нечетный и четный отсчеты) в течение двух тактов благо5 даря задержкам на регистрах 3,4 будут одновременно поступать на информационные входы сумматора-вычитателя, режим которого. по управляющему входу меняется с каждым тактом. Сумма f, +

+f в третьем такте первой итерации преобразована и последующие суммы в нечетных тактах первой итерации записываются в блок 1 регистров сдвига под действием тактовых импульсов на

его входе . Разность f -f в четвертом такте первой итерации преобразования (и последующие разности в четных тактах итерации) запишутся в блоке 1 регистров сдвига. Таким образом, 20 к началу (N+4) такта первой итерации преобразования на нечетных регистрах

N сдвига блока 1 будут записаны — сумм, 1 а на нечетных регистрах сдвига

2 разностей.

Такая работа соответствует графику преобраэова,ния (фиг. 4). B (N+4) -м такте первой итерации преобразования

30 на вход разрешения записи, вход блока 2 регистров сдвига подается стробирующий импульс с выхода блока 7 син,хронизации, вследствие чего (11+4)-м тактовым импульсом на входе блока 2 регистров сдвига данные перепишутся в блок 2.

На второй и последующих итерациях устройство работает аналогично.

По окончанию п-й итерации коэффи- 40 циенты преобразования (f;), i=1,N оказываются записанными на последовательных адресах в блоке 2 регистров сдвига и будут храниться там до следующего цикла преобразования. 45

Формул а и з о б р е те н и я

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

i-ro (i=1,N) регистра сдвига первого блока регистров сдвига является j --M

i 1 (j =- — +1 при i — четном, j =(N+i) /2 при i — нечетном) информационным входом устройства, а выход i-ro регистра сдвига первого блока регистров сдвига подключен к информационному входу

j-го регистра сдвига второго блока регистров сдвига, выход первого регистра сдвига которого подключен к первому информационному входу коммутатора и информационному входу первого регистра, выход которого подключен к второму информационному входу ком-, мутатора и информационному входу второго регистра, выход которого подключен к третьему информационному входу коммутатора, первый и второй выходы которого подключены соответственно к первому и второму информационным входам сумматора-вычитателя, выход которого подключен к информационному входу (N+1) — rc регистра сдвига первого блока регистров сдвига, четвертый и пятый выходы блока синхронизации подключены соответственно к тактовому входу второго регистра и управляющему входу коммутатора.

gs

ФО8. 2 д

157161 )

Fy г б

4 4+8 в --- а-в

Составитель А.Баранов

Редактор О.Спесивых Техред М,Дндык Корректор В. Кабаций

Заказ 1514 Тираж 567 Подписное

ВНИИНИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Броиэводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 101