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

фие.1

3157

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

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

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

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

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

Блок синхронизации формирует необходимые тактовые последовательности следующим образом. По короткому синхроимпульсу, поступающему по входу 9, срабатывает одновибратор 10, который формирует стробирующий импульс разрешения записи данных в блоки 1,2 регистров сдвига. Задержанные синхроимпульсы с выходов элементов 11,12 задержки используются для записи исходных данных и объединяются в соответствующих элементах ИЛИ 19,20 с тактовыми импульсами с выхода генератора 13 тактовых импульсов. Запуск генератора 13 тактовых импульсов осуществляется импульсом с выхода элемента 12 задержки. Тактовые импульсы с выхода генератора 13 поступают на вход триггера 14 со счетным входом, который формирует импульс управления, подаваемый на выход блока 25 синхронизации. Импульсы с выхода счетного триггера 14 поступают на вход первого делителя 15 частоты, который делит

rNo.-n частоту следования импульсов на о

N т.е. на его выходе имеет каждый (+

0

5

6104

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

вследствие чего на выходе этого дели- ч эд

теля будет п(г+2)-й импульс с выхода

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

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

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

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

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

0

5

0

I

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

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

F-HN-f,(1)

где F - вектор-столбец коэффициентов Уолша-Адамара;

HN - матрица Уолша-Адамара размерности NxN; N 2,

где п - положительное целое.

5

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

, „ «)

F(S

W HN

I

...(5„.Н(5,-НИ) f), (2)

515

где . . .H(Nn), матрица размером

NxN;

S., - мономиальная матрица перестановки.

Л j

HN 1 н/г®, ,п, где 1 fj/i - единичная матрица порядка N/2; Н1 - матрица Адамара порядка 2;

.

Таким образом, вычислительная процедура (2) реализуется за п итераций, при этом каждая i-я итерация сводится к умножению вектора-столбца результатов f , на матрицу Н (w1 , что сводится к сложению или вычитанию соответствующих элементов промежуточного вектора f ,-., и переупорядочиванию элементов результирующего вектора f; умножением на мономиальную матрицу S . Суть перестановки заключается в разделении массива элементов вектора f на массивы четных и нечетных элементов и формировании переупорядоченного вектора ff путем последовательного расположения этих массивов, при этом массив нечетных элементов вектора f располагается в первой половине результирующего массива. Правило .перестановки можно задать следующим соотношением:

f.

ф

fj(2 (J-O + O, при j 1,N/2, f ,(2 -(j- ), при j N/2+1,N

Элементы матрицы S N определяются по формуле:

1, (i-1), при . N/2.

N/ 2

S ( 1, (i- f), при ,N,

О, иначе.

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

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

0

5

0

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

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

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

данных в регистры сдвига блока 1.

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

1 -(j-0-И, j 1, N/2,

-УС NN N M 2

30

35

40

45

50

где Q ,

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

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

то

2-1

, то

-логическое состояние на управляющем входе коммутатора;

-подключение М-го информационного входа коммутатора

к L-му выходу;

М 1,3, ,2-.

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

кN

сдвига блока 1 будут записаны сумм,

N а на нечетных регистрах сдвига - г

разностей.

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

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

По окончанию n-й итерации коэффи- циенты преобразования fj, ,N оказываются записанными на последовательных адресах в блоке 2 регистров сдвига и будут храниться там до следующего цикла преобразования.

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

Устройство для ортогонального преобразования по Уолшу-Адамару, содер- жащее первый и второй блоки из N+1

0

0

5

0

5

0 45

0

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

( при i - четном, j(N+i)/2

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

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

Фиг. 2

tfteJ

А + 8